[PATCH] idr: fix invalid ptr dereference on item delete

[PATCH] idr: fix invalid ptr dereference on item delete

[Roman Kagan]

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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
Signed-off-by: Roman Kagan <rkagan@virtuozzo.com>
---
 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

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Paolo Bonzini]

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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
> Signed-off-by: Roman Kagan <rkagan@virtuozzo.com>
> ---
>  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: stable@vger.kernel.org

Should radix-tree be compilable in userspace, so that we can add unit
tests for it?...

Paolo

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Dmitry Vyukov]

On Fri, May 11, 2018 at 1:54 AM, Paolo Bonzini <pbonzini@redhat.com> 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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
>> Signed-off-by: Roman Kagan <rkagan@virtuozzo.com>
>> ---
>>  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: stable@vger.kernel.org
>
> 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?

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Roman Kagan]

On Fri, May 11, 2018 at 07:40:26AM +0200, Dmitry Vyukov wrote:
> On Fri, May 11, 2018 at 1:54 AM, Paolo Bonzini <pbonzini@redhat.com> 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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
> >> Signed-off-by: Roman Kagan <rkagan@virtuozzo.com>
> >> ---
> >>  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: stable@vger.kernel.org
> >
> > 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.

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Paolo Bonzini]

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

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Roman Kagan]

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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
> Signed-off-by: Roman Kagan <rkagan@virtuozzo.com>
> ---
>  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 <willy@infradead.org> -----

Date: Fri, 18 May 2018 10:50:25 -0700
From: Matthew Wilcox <willy@infradead.org>
To: Roman Kagan <rkagan@virtuozzo.com>
Cc: Andrew Morton <akpm@linux-foundation.org>, linux-kernel@vger.kernel.org
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 <mawilcox@microsoft.com>

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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
Debugged-by: Roman Kagan <rkagan@virtuozzo.com>
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
Signed-off-by: Roman Kagan <rkagan@virtuozzo.com>
---
 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 -----

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Matthew Wilcox]

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 <mawilcox@microsoft.com>

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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
Debugged-by: Roman Kagan <rkagan@virtuozzo.com>
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
Signed-off-by: Roman Kagan <rkagan@virtuozzo.com>
---
 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)

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Roman Kagan]

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 <mawilcox@microsoft.com>".
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.

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Matthew Wilcox]

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 <mawilcox@microsoft.com>".
> 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!

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Andrew Morton]

On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <willy@infradead.org> 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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
> Debugged-by: Roman Kagan <rkagan@virtuozzo.com>
> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

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?

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Matthew Wilcox]

On Fri, May 18, 2018 at 03:31:38PM -0700, Andrew Morton wrote:
> On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <willy@infradead.org> 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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
> > Debugged-by: Roman Kagan <rkagan@virtuozzo.com>
> > Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> 
> 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".

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Roman Kagan]

On Fri, May 18, 2018 at 03:31:38PM -0700, Andrew Morton wrote:
> On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox <willy@infradead.org> 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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
> > Debugged-by: Roman Kagan <rkagan@virtuozzo.com>
> > Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> 
> 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.

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Matthew Wilcox]

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 <willy@infradead.org> 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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
> > > Debugged-by: Roman Kagan <rkagan@virtuozzo.com>
> > > Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> > 
> > 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

Re: [PATCH] idr: fix invalid ptr dereference on item delete

[Andrew Morton]

On Sat, 19 May 2018 07:14:45 -0700 Matthew Wilcox <willy@infradead.org> 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 <willy@infradead.org> 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: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
> > > > Debugged-by: Roman Kagan <rkagan@virtuozzo.com>
> > > > Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> > > 
> > > 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 <mawilcox@microsoft.com>
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/20180518175025.GD6361@bombadil.infradead.org
Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree")
Reported-by: syzbot+35666cba7f0a337e2e79@syzkaller.appspotmail.com
Debugged-by: Roman Kagan <rkagan@virtuozzo.com>
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
Cc: <stable@vger.kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 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);
_