idr: fix invalid ptr dereference on item delete
Subsystems (2)
Matthew Wilcox
maintainerIt'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.
lib/radix-tree.c +3 -1
@@ -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 ;
tools/testing/radix-tree/idr-test.c +7 -0
@@ -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.
--- lib/radix-tree.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)
lib/radix-tree.c +3 -2
@@ -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)
Quoted 3 lines · 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.
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...
Quoted 4 lines
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.
Matthew Wilcox
maintainerQuoted 9 lines · Roman Kagan
Quoted 3 lines · 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.
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.
Quoted 7 lines
Quoted 4 lines
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)
Quoted 5 lines
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!
Andrew Morton
maintainerQuoted 11 lines · 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?
Matthew Wilcox
maintainerQuoted 8 lines · Andrew Morton
Quoted 7 lines · 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.
Quoted 8 lines
Quoted 4 lines
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.
Quoted 4 lines
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".
Quoted 9 lines · Andrew Morton
Quoted 7 lines · 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.
Quoted 8 lines
Quoted 4 lines
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.
Quoted 2 lines
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.
Quoted 2 lines
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.
Matthew Wilcox
maintainerQuoted 30 lines · Roman Kagan
Quoted 9 lines · Andrew Morton
Quoted 7 lines · 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.Quoted 8 lines
Quoted 4 lines
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.
Quoted 2 lines
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.
Quoted 6 lines
Quoted 2 lines
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_EVENTDioctl 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
Andrew Morton
maintainerQuoted 38 lines · On Sat, 19 May 2018 07:14:45 -0700 Matthew Wilcox <[email protected]> wrote:
Quoted 30 lines · Roman Kagan
Quoted 9 lines · Andrew Morton
Quoted 7 lines · 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.Quoted 8 lines
Quoted 4 lines
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.
Quoted 2 lines
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.Quoted 6 lines
Quoted 2 lines
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_EVENTDioctl which is new in 4.17. But I guess there are other user-triggerable paths, so cc:stable is probably justified.
Quoted 7 lines
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.clooks unsafe; the ID comes from an ioctl.drivers/gpu/drm/amd/amdgpu/amdgpu_ctx.cis similardrivers/atm/nicstar.ccould 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
---
lib/radix-tree.c | 4 +++- tools/testing/radix-tree/idr-test.c | 7 +++++++ 2 files changed, 10 insertions(+), 1 deletion(-)
lib/radix-tree.c renamed from lib/radix-tree.c~idr-fix-invalid-ptr-dereference-on-item-delete +3 -1
@@ -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 ;
tools/testing/radix-tree/idr-test.c renamed from tools/testing/radix-tree/idr-test.c~idr-fix-invalid-ptr-dereference-on-item-delete +7 -0
@@ -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);
_