If an IDR contains a single entry at index==0, the underlying radix tree
has a single item in its root node, in which case
__radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in
addition to returning NULL).
However, the tree itself is not empty, i.e. the tree root doesn't have
IDR_FREE tag.
As a result, on an attempt to remove an index!=0 entry from such an IDR,
radix_tree_delete_item doesn't return early and calls
__radix_tree_delete with invalid parameters which are then dereferenced.
Reported-by: [email protected]
Signed-off-by: Roman Kagan <[email protected]>
---
lib/radix-tree.c | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index da9e10c827df..10ff1bfae952 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
void *entry;
entry = __radix_tree_lookup(root, index, &node, &slot);
- if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
- get_slot_offset(node, slot))))
+ if (!entry && (!is_idr(root) || !node ||
+ node_tag_get(root, node, IDR_FREE,
+ get_slot_offset(node, slot))))
return NULL;
if (item && entry != item)
--
2.17.0
On 10/05/2018 21:16, Roman Kagan wrote:
> If an IDR contains a single entry at index==0, the underlying radix tree
> has a single item in its root node, in which case
> __radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in
> addition to returning NULL).
>
> However, the tree itself is not empty, i.e. the tree root doesn't have
> IDR_FREE tag.
>
> As a result, on an attempt to remove an index!=0 entry from such an IDR,
> radix_tree_delete_item doesn't return early and calls
> __radix_tree_delete with invalid parameters which are then dereferenced.
>
> Reported-by: [email protected]
> Signed-off-by: Roman Kagan <[email protected]>
> ---
> lib/radix-tree.c | 5 +++--
> 1 file changed, 3 insertions(+), 2 deletions(-)
>
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index da9e10c827df..10ff1bfae952 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
> void *entry;
>
> entry = __radix_tree_lookup(root, index, &node, &slot);
> - if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
> - get_slot_offset(node, slot))))
> + if (!entry && (!is_idr(root) || !node ||
> + node_tag_get(root, node, IDR_FREE,
> + get_slot_offset(node, slot))))
> return NULL;
>
> if (item && entry != item)
>
I cannot really vouch for the patch, but if it is correct it's
definitely stuff for stable. The KVM testcase is only for 4.17-rc but
this is a really nasty bug in a core data structure.
Cc: [email protected]
Should radix-tree be compilable in userspace, so that we can add unit
tests for it?...
Paolo
On Fri, May 11, 2018 at 1:54 AM, Paolo Bonzini <[email protected]> wrote:
> On 10/05/2018 21:16, Roman Kagan wrote:
>> If an IDR contains a single entry at index==0, the underlying radix tree
>> has a single item in its root node, in which case
>> __radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in
>> addition to returning NULL).
>>
>> However, the tree itself is not empty, i.e. the tree root doesn't have
>> IDR_FREE tag.
>>
>> As a result, on an attempt to remove an index!=0 entry from such an IDR,
>> radix_tree_delete_item doesn't return early and calls
>> __radix_tree_delete with invalid parameters which are then dereferenced.
>>
>> Reported-by: [email protected]
>> Signed-off-by: Roman Kagan <[email protected]>
>> ---
>> lib/radix-tree.c | 5 +++--
>> 1 file changed, 3 insertions(+), 2 deletions(-)
>>
>> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
>> index da9e10c827df..10ff1bfae952 100644
>> --- a/lib/radix-tree.c
>> +++ b/lib/radix-tree.c
>> @@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
>> void *entry;
>>
>> entry = __radix_tree_lookup(root, index, &node, &slot);
>> - if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
>> - get_slot_offset(node, slot))))
>> + if (!entry && (!is_idr(root) || !node ||
>> + node_tag_get(root, node, IDR_FREE,
>> + get_slot_offset(node, slot))))
>> return NULL;
>>
>> if (item && entry != item)
>>
>
> I cannot really vouch for the patch, but if it is correct it's
> definitely stuff for stable. The KVM testcase is only for 4.17-rc but
> this is a really nasty bug in a core data structure.
>
> Cc: [email protected]
>
> Should radix-tree be compilable in userspace, so that we can add unit
> tests for it?...
Good point.
For my education, what/where are the tests that run as user-space code?
On Fri, May 11, 2018 at 07:40:26AM +0200, Dmitry Vyukov wrote:
> On Fri, May 11, 2018 at 1:54 AM, Paolo Bonzini <[email protected]> wrote:
> > On 10/05/2018 21:16, Roman Kagan wrote:
> >> If an IDR contains a single entry at index==0, the underlying radix tree
> >> has a single item in its root node, in which case
> >> __radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in
> >> addition to returning NULL).
> >>
> >> However, the tree itself is not empty, i.e. the tree root doesn't have
> >> IDR_FREE tag.
> >>
> >> As a result, on an attempt to remove an index!=0 entry from such an IDR,
> >> radix_tree_delete_item doesn't return early and calls
> >> __radix_tree_delete with invalid parameters which are then dereferenced.
> >>
> >> Reported-by: [email protected]
> >> Signed-off-by: Roman Kagan <[email protected]>
> >> ---
> >> lib/radix-tree.c | 5 +++--
> >> 1 file changed, 3 insertions(+), 2 deletions(-)
> >>
> >> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> >> index da9e10c827df..10ff1bfae952 100644
> >> --- a/lib/radix-tree.c
> >> +++ b/lib/radix-tree.c
> >> @@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
> >> void *entry;
> >>
> >> entry = __radix_tree_lookup(root, index, &node, &slot);
> >> - if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
> >> - get_slot_offset(node, slot))))
> >> + if (!entry && (!is_idr(root) || !node ||
> >> + node_tag_get(root, node, IDR_FREE,
> >> + get_slot_offset(node, slot))))
> >> return NULL;
> >>
> >> if (item && entry != item)
> >>
> >
> > I cannot really vouch for the patch, but if it is correct it's
> > definitely stuff for stable. The KVM testcase is only for 4.17-rc but
> > this is a really nasty bug in a core data structure.
> >
> > Cc: [email protected]
> >
> > Should radix-tree be compilable in userspace, so that we can add unit
> > tests for it?...
>
> Good point.
>
> For my education, what/where are the tests that run as user-space code?
Actually there are userspace tests for it under tools/tests/radix-tree,
but I didn't manage to get them to build. Looks like the recent
introduction of a spin_lock in the radix_tree structure (for XArray
work?) broke them.
Roman.
On 11/05/2018 07:57, Roman Kagan wrote:
>>> Should radix-tree be compilable in userspace, so that we can add unit
>>> tests for it?...
>> Good point.
>>
>> For my education, what/where are the tests that run as user-space code?
> Actually there are userspace tests for it under tools/tests/radix-tree,
> but I didn't manage to get them to build. Looks like the recent
> introduction of a spin_lock in the radix_tree structure (for XArray
> work?) broke them.
Oh cool, at least it means it was a good suggestion. :)
Paolo
It'd be nice if you cc'd the person who wrote the code you're patching.
You'd get a response a lot quicker than waiting until I happened to
notice the email in a different forum.
Thanks for finding the situation that leads to the bug. Your fix is
incorrect; it's legitimate to store a NULL value at offset 0, and
your patch makes it impossible to delete. Fortunately, the test-suite
covers that case ;-)
Andrew, can you take this through your tree for extra testing?
--- >8 ---
From: Matthew Wilcox <[email protected]>
If the radix tree underlying the IDR happens to be full and we attempt
to remove an id which is larger than any id in the IDR, we will call
__radix_tree_delete() with an uninitialised 'slot' pointer, at which
point anything could happen. This was easiest to hit with a single entry
at id 0 and attempting to remove a non-0 id, but it could have happened
with 64 entries and attempting to remove an id >= 64.
Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by: [email protected]
Debugged-by: Roman Kagan <[email protected]>
Signed-off-by: Matthew Wilcox <[email protected]>
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index da9e10c827df..4dd4fbc7279c 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -2036,10 +2036,12 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
unsigned long index, void *item)
{
struct radix_tree_node *node = NULL;
- void __rcu **slot;
+ void __rcu **slot = NULL;
void *entry;
entry = __radix_tree_lookup(root, index, &node, &slot);
+ if (!slot)
+ return NULL;
if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
get_slot_offset(node, slot))))
return NULL;
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 1c18617951dd..410ca58bbe9c 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -254,6 +254,13 @@ void idr_checks(void)
idr_remove(&idr, 0xfedcba98U);
idr_remove(&idr, 0);
+ assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == 0);
+ idr_remove(&idr, 1);
+ for (i = 1; i < RADIX_TREE_MAP_SIZE; i++)
+ assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == i);
+ idr_remove(&idr, 1 << 30);
+ idr_destroy(&idr);
+
for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
struct item *item = item_create(i, 0);
assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
--- original email ---
If an IDR contains a single entry at index==0, the underlying radix tree
has a single item in its root node, in which case
__radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in
addition to returning NULL).
However, the tree itself is not empty, i.e. the tree root doesn't have
IDR_FREE tag.
As a result, on an attempt to remove an index!=0 entry from such an IDR,
radix_tree_delete_item doesn't return early and calls
__radix_tree_delete with invalid parameters which are then dereferenced.
Reported-by: [email protected]
Signed-off-by: Roman Kagan <[email protected]>
---
lib/radix-tree.c | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index da9e10c827df..10ff1bfae952 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
void *entry;
entry = __radix_tree_lookup(root, index, &node, &slot);
- if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
- get_slot_offset(node, slot))))
+ if (!entry && (!is_idr(root) || !node ||
+ node_tag_get(root, node, IDR_FREE,
+ get_slot_offset(node, slot))))
return NULL;
if (item && entry != item)
On Fri, May 18, 2018 at 10:50:25AM -0700, Matthew Wilcox wrote:
> It'd be nice if you cc'd the person who wrote the code you're patching.
> You'd get a response a lot quicker than waiting until I happened to
> notice the email in a different forum.
I sent it to someone called "Matthew Wilcox <[email protected]>".
Also I cc'd that guy when I only started to point the finger at IDR as
the suspected culprit in that syzcaller report. I thought it was him
who wrote the code...
> Thanks for finding the situation that leads to the bug. Your fix is
> incorrect; it's legitimate to store a NULL value at offset 0, and
> your patch makes it impossible to delete. Fortunately, the test-suite
> covers that case ;-)
How do you build it? I wish I had it when debugging but I got linking
errors due to missing spin_lock_init, so I decided it wasn't up-to-date.
Thanks,
Roman.
P.S. I'll forward your message to all the recepients of my patch, to let
them know it's wrong and you have a better one.
On Thu, May 10, 2018 at 10:16:34PM +0300, Roman Kagan wrote:
> If an IDR contains a single entry at index==0, the underlying radix tree
> has a single item in its root node, in which case
> __radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in
> addition to returning NULL).
>
> However, the tree itself is not empty, i.e. the tree root doesn't have
> IDR_FREE tag.
>
> As a result, on an attempt to remove an index!=0 entry from such an IDR,
> radix_tree_delete_item doesn't return early and calls
> __radix_tree_delete with invalid parameters which are then dereferenced.
>
> Reported-by: [email protected]
> Signed-off-by: Roman Kagan <[email protected]>
> ---
> lib/radix-tree.c | 5 +++--
> 1 file changed, 3 insertions(+), 2 deletions(-)
>
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index da9e10c827df..10ff1bfae952 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
> void *entry;
>
> entry = __radix_tree_lookup(root, index, &node, &slot);
> - if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
> - get_slot_offset(node, slot))))
> + if (!entry && (!is_idr(root) || !node ||
> + node_tag_get(root, node, IDR_FREE,
> + get_slot_offset(node, slot))))
> return NULL;
>
> if (item && entry != item)
Turned out Matthew didn't receive my messages; now that he's found this
patch elsewhere he's responded with a correct fix:
----- Forwarded message from Matthew Wilcox <[email protected]> -----
Date: Fri, 18 May 2018 10:50:25 -0700
From: Matthew Wilcox <[email protected]>
To: Roman Kagan <[email protected]>
Cc: Andrew Morton <[email protected]>, [email protected]
Subject: Re: [PATCH] idr: fix invalid ptr dereference on item delete
It'd be nice if you cc'd the person who wrote the code you're patching.
You'd get a response a lot quicker than waiting until I happened to
notice the email in a different forum.
Thanks for finding the situation that leads to the bug. Your fix is
incorrect; it's legitimate to store a NULL value at offset 0, and
your patch makes it impossible to delete. Fortunately, the test-suite
covers that case ;-)
Andrew, can you take this through your tree for extra testing?
--- >8 ---
From: Matthew Wilcox <[email protected]>
If the radix tree underlying the IDR happens to be full and we attempt
to remove an id which is larger than any id in the IDR, we will call
__radix_tree_delete() with an uninitialised 'slot' pointer, at which
point anything could happen. This was easiest to hit with a single entry
at id 0 and attempting to remove a non-0 id, but it could have happened
with 64 entries and attempting to remove an id >= 64.
Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by: [email protected]
Debugged-by: Roman Kagan <[email protected]>
Signed-off-by: Matthew Wilcox <[email protected]>
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index da9e10c827df..4dd4fbc7279c 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -2036,10 +2036,12 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
unsigned long index, void *item)
{
struct radix_tree_node *node = NULL;
- void __rcu **slot;
+ void __rcu **slot = NULL;
void *entry;
entry = __radix_tree_lookup(root, index, &node, &slot);
+ if (!slot)
+ return NULL;
if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
get_slot_offset(node, slot))))
return NULL;
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 1c18617951dd..410ca58bbe9c 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -254,6 +254,13 @@ void idr_checks(void)
idr_remove(&idr, 0xfedcba98U);
idr_remove(&idr, 0);
+ assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == 0);
+ idr_remove(&idr, 1);
+ for (i = 1; i < RADIX_TREE_MAP_SIZE; i++)
+ assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == i);
+ idr_remove(&idr, 1 << 30);
+ idr_destroy(&idr);
+
for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
struct item *item = item_create(i, 0);
assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
--- original email ---
If an IDR contains a single entry at index==0, the underlying radix tree
has a single item in its root node, in which case
__radix_tree_lookup(index!=0) doesn't set its *@nodep argument (in
addition to returning NULL).
However, the tree itself is not empty, i.e. the tree root doesn't have
IDR_FREE tag.
As a result, on an attempt to remove an index!=0 entry from such an IDR,
radix_tree_delete_item doesn't return early and calls
__radix_tree_delete with invalid parameters which are then dereferenced.
Reported-by: [email protected]
Signed-off-by: Roman Kagan <[email protected]>
---
lib/radix-tree.c | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index da9e10c827df..10ff1bfae952 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -2040,8 +2040,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
void *entry;
entry = __radix_tree_lookup(root, index, &node, &slot);
- if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
- get_slot_offset(node, slot))))
+ if (!entry && (!is_idr(root) || !node ||
+ node_tag_get(root, node, IDR_FREE,
+ get_slot_offset(node, slot))))
return NULL;
if (item && entry != item)
----- End forwarded message -----
On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:
> If the radix tree underlying the IDR happens to be full and we attempt
> to remove an id which is larger than any id in the IDR, we will call
> __radix_tree_delete() with an uninitialised 'slot' pointer, at which
> point anything could happen. This was easiest to hit with a single entry
> at id 0 and attempting to remove a non-0 id, but it could have happened
> with 64 entries and attempting to remove an id >= 64.
>
> Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
> Reported-by: [email protected]
> Debugged-by: Roman Kagan <[email protected]>
> Signed-off-by: Matthew Wilcox <[email protected]>
Neither of the changelogs I'm seeing attempt to describe the end-user
impact of the bug. People like to know that so they can decide which
kernel version(s) need patching, so please always remember it.
Looknig at the sysbot report, the impact is at least "privileged user
can trigger a WARN", but I assume there could be worse,
as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed,
yes?
On Fri, May 18, 2018 at 03:31:38PM -0700, Andrew Morton wrote:
> On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:
> > If the radix tree underlying the IDR happens to be full and we attempt
> > to remove an id which is larger than any id in the IDR, we will call
> > __radix_tree_delete() with an uninitialised 'slot' pointer, at which
> > point anything could happen. This was easiest to hit with a single entry
> > at id 0 and attempting to remove a non-0 id, but it could have happened
> > with 64 entries and attempting to remove an id >= 64.
> >
> > Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
> > Reported-by: [email protected]
> > Debugged-by: Roman Kagan <[email protected]>
> > Signed-off-by: Matthew Wilcox <[email protected]>
>
> Neither of the changelogs I'm seeing attempt to describe the end-user
> impact of the bug. People like to know that so they can decide which
> kernel version(s) need patching, so please always remember it.
The problem is that it could be user-triggerable a dozen different
ways.
> Looknig at the sysbot report, the impact is at least "privileged user
> can trigger a WARN", but I assume there could be worse,
> as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed,
> yes?
I thought if I used the Fixes: tag it would automatically get picked up.
Did I misunderstand? I can imagine many different parts of the kernel
that use the IDR could trigger such a warning (although syzbot should
probably have tripped over them before now) so I wouldn't downplay
it to "only privileged users".
On Fri, May 18, 2018 at 11:23:08PM +0300, Roman Kagan wrote:
> On Fri, May 18, 2018 at 10:50:25AM -0700, Matthew Wilcox wrote:
> > It'd be nice if you cc'd the person who wrote the code you're patching.
> > You'd get a response a lot quicker than waiting until I happened to
> > notice the email in a different forum.
>
> I sent it to someone called "Matthew Wilcox <[email protected]>".
> Also I cc'd that guy when I only started to point the finger at IDR as
> the suspected culprit in that syzcaller report. I thought it was him
> who wrote the code...
I didn't get them ;-( Sorry.
> > Thanks for finding the situation that leads to the bug. Your fix is
> > incorrect; it's legitimate to store a NULL value at offset 0, and
> > your patch makes it impossible to delete. Fortunately, the test-suite
> > covers that case ;-)
>
> How do you build it? I wish I had it when debugging but I got linking
> errors due to missing spin_lock_init, so I decided it wasn't up-to-date.
Yeah, I inadvertently broke it with commit
f6bb2a2c0b81 ("xarray: add the xa_lock to the radix_tree_root")
Andrew has a patch to fix it in his tree. All you need is:
+++ b/tools/include/linux/spinlock.h
@@ -8,6 +8,7 @@
#define spinlock_t pthread_mutex_t
#define DEFINE_SPINLOCK(x) pthread_mutex_t x = PTHREAD_MUTEX_INITIALIZER;
#define __SPIN_LOCK_UNLOCKED(x) (pthread_mutex_t)PTHREAD_MUTEX_INITIALIZ
ER
+#define spin_lock_init(x) pthread_mutex_init(x, NULL);
#define spin_lock_irqsave(x, f) (void)f, pthread_mutex_lock(x)
#define spin_unlock_irqrestore(x, f) (void)f, pthread_mutex_unlock(x)
> Thanks,
> Roman.
>
> P.S. I'll forward your message to all the recepients of my patch, to let
> them know it's wrong and you have a better one.
Thanks!
On Fri, May 18, 2018 at 03:31:38PM -0700, Andrew Morton wrote:
> On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:
>
> > If the radix tree underlying the IDR happens to be full and we attempt
> > to remove an id which is larger than any id in the IDR, we will call
> > __radix_tree_delete() with an uninitialised 'slot' pointer, at which
> > point anything could happen. This was easiest to hit with a single entry
> > at id 0 and attempting to remove a non-0 id, but it could have happened
> > with 64 entries and attempting to remove an id >= 64.
> >
> > Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
> > Reported-by: [email protected]
> > Debugged-by: Roman Kagan <[email protected]>
> > Signed-off-by: Matthew Wilcox <[email protected]>
>
> Neither of the changelogs I'm seeing attempt to describe the end-user
> impact of the bug. People like to know that so they can decide which
> kernel version(s) need patching, so please always remember it.
That's my fault, Matthew may not have seen the original discussion among
the KVM folks.
> Looknig at the sysbot report, the impact is at least "privileged user
> can trigger a WARN", but I assume there could be worse,
Unfortunately it is worse: the syzcaller test boils down to opening
/dev/kvm, creating an eventfd, and calling a couple of KVM ioctls. None
of this requires superuser. And the result is dereferencing an
uninitialized pointer which is likely a crash.
> as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed,
> yes?
Well the specific path caught by syzbot is via KVM_HYPERV_EVENTD ioctl
which is new in 4.17. But I guess there are other user-triggerable
paths, so cc:stable is probably justified.
Thanks,
Roman.
On Sat, May 19, 2018 at 09:26:36AM +0300, Roman Kagan wrote:
> On Fri, May 18, 2018 at 03:31:38PM -0700, Andrew Morton wrote:
> > On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:
> >
> > > If the radix tree underlying the IDR happens to be full and we attempt
> > > to remove an id which is larger than any id in the IDR, we will call
> > > __radix_tree_delete() with an uninitialised 'slot' pointer, at which
> > > point anything could happen. This was easiest to hit with a single entry
> > > at id 0 and attempting to remove a non-0 id, but it could have happened
> > > with 64 entries and attempting to remove an id >= 64.
> > >
> > > Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
> > > Reported-by: [email protected]
> > > Debugged-by: Roman Kagan <[email protected]>
> > > Signed-off-by: Matthew Wilcox <[email protected]>
> >
> > Neither of the changelogs I'm seeing attempt to describe the end-user
> > impact of the bug. People like to know that so they can decide which
> > kernel version(s) need patching, so please always remember it.
>
> That's my fault, Matthew may not have seen the original discussion among
> the KVM folks.
>
> > Looknig at the sysbot report, the impact is at least "privileged user
> > can trigger a WARN", but I assume there could be worse,
>
> Unfortunately it is worse: the syzcaller test boils down to opening
> /dev/kvm, creating an eventfd, and calling a couple of KVM ioctls. None
> of this requires superuser. And the result is dereferencing an
> uninitialized pointer which is likely a crash.
>
> > as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed,
> > yes?
>
> Well the specific path caught by syzbot is via KVM_HYPERV_EVENTD ioctl
> which is new in 4.17. But I guess there are other user-triggerable
> paths, so cc:stable is probably justified.
We have around 250 calls to idr_remove() in the kernel today. Many of
them pass an ID which is embedded in the object they're removing, so
they're safe. Picking a few likely candidates:
drivers/firewire/core-cdev.c looks unsafe; the ID comes from an ioctl.
drivers/gpu/drm/amd/amdgpu/amdgpu_ctx.c is similar
drivers/atm/nicstar.c could be taken down by a handcrafted packet
On Sat, 19 May 2018 07:14:45 -0700 Matthew Wilcox <[email protected]> wrote:
> On Sat, May 19, 2018 at 09:26:36AM +0300, Roman Kagan wrote:
> > On Fri, May 18, 2018 at 03:31:38PM -0700, Andrew Morton wrote:
> > > On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <[email protected]> wrote:
> > >
> > > > If the radix tree underlying the IDR happens to be full and we attempt
> > > > to remove an id which is larger than any id in the IDR, we will call
> > > > __radix_tree_delete() with an uninitialised 'slot' pointer, at which
> > > > point anything could happen. This was easiest to hit with a single entry
> > > > at id 0 and attempting to remove a non-0 id, but it could have happened
> > > > with 64 entries and attempting to remove an id >= 64.
> > > >
> > > > Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
> > > > Reported-by: [email protected]
> > > > Debugged-by: Roman Kagan <[email protected]>
> > > > Signed-off-by: Matthew Wilcox <[email protected]>
> > >
> > > Neither of the changelogs I'm seeing attempt to describe the end-user
> > > impact of the bug. People like to know that so they can decide which
> > > kernel version(s) need patching, so please always remember it.
> >
> > That's my fault, Matthew may not have seen the original discussion among
> > the KVM folks.
> >
> > > Looknig at the sysbot report, the impact is at least "privileged user
> > > can trigger a WARN", but I assume there could be worse,
> >
> > Unfortunately it is worse: the syzcaller test boils down to opening
> > /dev/kvm, creating an eventfd, and calling a couple of KVM ioctls. None
> > of this requires superuser. And the result is dereferencing an
> > uninitialized pointer which is likely a crash.
> >
> > > as-yet-undiscovered impacts. So I'm thinking a cc:stable is needed,
> > > yes?
> >
> > Well the specific path caught by syzbot is via KVM_HYPERV_EVENTD ioctl
> > which is new in 4.17. But I guess there are other user-triggerable
> > paths, so cc:stable is probably justified.
>
> We have around 250 calls to idr_remove() in the kernel today. Many of
> them pass an ID which is embedded in the object they're removing, so
> they're safe. Picking a few likely candidates:
>
> drivers/firewire/core-cdev.c looks unsafe; the ID comes from an ioctl.
> drivers/gpu/drm/amd/amdgpu/amdgpu_ctx.c is similar
> drivers/atm/nicstar.c could be taken down by a handcrafted packet
OK, thanks, I sprinkled some of the above words into the changelog ad
added cc:stable.
From: Matthew Wilcox <[email protected]>
Subject: idr: fix invalid ptr dereference on item delete
If the radix tree underlying the IDR happens to be full and we attempt to
remove an id which is larger than any id in the IDR, we will call
__radix_tree_delete() with an uninitialised 'slot' pointer, at which point
anything could happen. This was easiest to hit with a single entry at id
0 and attempting to remove a non-0 id, but it could have happened with 64
entries and attempting to remove an id >= 64.
Roman said:
The syzcaller test boils down to opening /dev/kvm, creating an
eventfd, and calling a couple of KVM ioctls. None of this requires
superuser. And the result is dereferencing an uninitialized pointer
which is likely a crash. The specific path caught by syzbot is via
KVM_HYPERV_EVENTD ioctl which is new in 4.17. But I guess there are
other user-triggerable paths, so cc:stable is probably justified.
Matthew added:
We have around 250 calls to idr_remove() in the kernel today. Many
of them pass an ID which is embedded in the object they're removing,
so they're safe. Picking a few likely candidates:
drivers/firewire/core-cdev.c looks unsafe; the ID comes from an ioctl.
drivers/gpu/drm/amd/amdgpu/amdgpu_ctx.c is similar
drivers/atm/nicstar.c could be taken down by a handcrafted packet
Link: http://lkml.kernel.org/r/[email protected]
Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by: [email protected]
Debugged-by: Roman Kagan <[email protected]>
Signed-off-by: Matthew Wilcox <[email protected]>
Cc: <[email protected]>
Signed-off-by: Andrew Morton <[email protected]>
---
lib/radix-tree.c | 4 +++-
tools/testing/radix-tree/idr-test.c | 7 +++++++
2 files changed, 10 insertions(+), 1 deletion(-)
diff -puN lib/radix-tree.c~idr-fix-invalid-ptr-dereference-on-item-delete lib/radix-tree.c
--- a/lib/radix-tree.c~idr-fix-invalid-ptr-dereference-on-item-delete
+++ a/lib/radix-tree.c
@@ -2034,10 +2034,12 @@ void *radix_tree_delete_item(struct radi
unsigned long index, void *item)
{
struct radix_tree_node *node = NULL;
- void __rcu **slot;
+ void __rcu **slot = NULL;
void *entry;
entry = __radix_tree_lookup(root, index, &node, &slot);
+ if (!slot)
+ return NULL;
if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
get_slot_offset(node, slot))))
return NULL;
diff -puN tools/testing/radix-tree/idr-test.c~idr-fix-invalid-ptr-dereference-on-item-delete tools/testing/radix-tree/idr-test.c
--- a/tools/testing/radix-tree/idr-test.c~idr-fix-invalid-ptr-dereference-on-item-delete
+++ a/tools/testing/radix-tree/idr-test.c
@@ -252,6 +252,13 @@ void idr_checks(void)
idr_remove(&idr, 3);
idr_remove(&idr, 0);
+ assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == 0);
+ idr_remove(&idr, 1);
+ for (i = 1; i < RADIX_TREE_MAP_SIZE; i++)
+ assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == i);
+ idr_remove(&idr, 1 << 30);
+ idr_destroy(&idr);
+
for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
struct item *item = item_create(i, 0);
assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
_