Re: [PATCH] idr: fix invalid ptr dereference on item delete
On Sat, 19 May 2018 07:14:45 -0700 Matthew Wilcox 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 > > > 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+35666cba7f0a337e2...@syzkaller.appspotmail.com > > > > Debugged-by: Roman Kagan > > > > Signed-off-by: Matthew Wilcox > > > > > > 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 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.gd6...@bombadil.infradead.org Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree") Reported-by: syzbot+35666cba7f0a337e2...@syzkaller.appspotmail.com Debugged-by: Roman Kagan Signed-off-by: Matthew Wilcox Cc: Signed-off-by: Andrew Morton --- 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 r
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 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+35666cba7f0a337e2...@syzkaller.appspotmail.com Debugged-by: Roman Kagan Signed-off-by: Matthew Wilcox 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+35666cba7f0a337e2...@syzkaller.appspotmail.com Signed-off-by: Roman Kagan --- 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
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 ". 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
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+35666cba7f0a337e2...@syzkaller.appspotmail.com > Signed-off-by: Roman Kagan > --- > 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 ----- Date: Fri, 18 May 2018 10:50:25 -0700 From: Matthew Wilcox To: Roman Kagan Cc: Andrew Morton , 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 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+35666cba7f0a337e2...@syzkaller.appspotmail.com Debugged-by: Roman Kagan Signed-off-by: Matthew Wilcox 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 r
Re: [PATCH] idr: fix invalid ptr dereference on item delete
On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox 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+35666cba7f0a337e2...@syzkaller.appspotmail.com > Debugged-by: Roman Kagan > Signed-off-by: Matthew Wilcox 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
On Fri, May 18, 2018 at 03:31:38PM -0700, Andrew Morton wrote: > On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox 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+35666cba7f0a337e2...@syzkaller.appspotmail.com > > Debugged-by: Roman Kagan > > Signed-off-by: Matthew Wilcox > > 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
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 ". > 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
On Fri, May 18, 2018 at 03:31:38PM -0700, Andrew Morton wrote: > On Fri, 18 May 2018 10:50:25 -0700 Matthew Wilcox 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+35666cba7f0a337e2...@syzkaller.appspotmail.com > > Debugged-by: Roman Kagan > > Signed-off-by: Matthew Wilcox > > 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
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 > > 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+35666cba7f0a337e2...@syzkaller.appspotmail.com > > > Debugged-by: Roman Kagan > > > Signed-off-by: Matthew Wilcox > > > > 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
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+35666cba7f0a337e2...@syzkaller.appspotmail.com > Signed-off-by: Roman Kagan > --- > 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: sta...@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
On Fri, May 11, 2018 at 1:54 AM, Paolo Bonzini 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+35666cba7f0a337e2...@syzkaller.appspotmail.com >> Signed-off-by: Roman Kagan >> --- >> 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: sta...@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
On Fri, May 11, 2018 at 07:40:26AM +0200, Dmitry Vyukov wrote: > On Fri, May 11, 2018 at 1:54 AM, Paolo Bonzini 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+35666cba7f0a337e2...@syzkaller.appspotmail.com > >> Signed-off-by: Roman Kagan > >> --- > >> 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: sta...@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
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