kernel/linux.git/tools/testing/radix-tree, branch v4.19.237

idr: Fix idr_get_next race with idr_remove

2019-11-24T07:19:11+00:00

commit 5c089fd0c73411f2170ab795c9ffc16718c7d007 upstream. If the entry is deleted from the IDR between the call to radix_tree_iter_find() and rcu_dereference_raw(), idr_get_next() will return NULL, which will end the iteration prematurely. We should instead continue to the next entry in the IDR. This only happens if the iteration is protected by the RCU lock. Most IDR users use a spinlock or semaphore to exclude simultaneous modifications. It was noticed once the PID allocator was converted to use the IDR, as it uses the RCU lock, but there may be other users elsewhere in the kernel. We can't use the normal pattern of calling radix_tree_deref_retry() (which catches both a retry entry in a leaf node and a node entry in the root) as the IDR supports storing entries which are unaligned, which will trigger an infinite loop if they are encountered. Instead, we have to explicitly check whether the entry is a retry entry. Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree") Reported-by: Brendan Gregg Tested-by: Brendan Gregg Signed-off-by: Matthew Wilcox (Oracle) Signed-off-by: Greg Kroah-Hartman

test_ida: check_ida_destroy and check_ida_alloc

2018-08-22T03:54:21+00:00

Move these tests from the userspace test-suite to the kernel test-suite. Also convert check_ida_random to the new API. Signed-off-by: Matthew Wilcox

test_ida: Convert check_ida_conv to new API

2018-08-22T03:54:20+00:00

Move as much as possible to kernel space; leave the parts in user space that rely on checking memory allocation failures to detect the transition between an exceptional entry and a bitmap. Signed-off-by: Matthew Wilcox

test_ida: Move ida_check_max

2018-08-22T03:54:20+00:00

Convert to new API and move to kernel space. Signed-off-by: Matthew Wilcox

test_ida: Move ida_check_leaf

2018-08-22T03:54:20+00:00

Convert to new API and move to kernel space. Take the opportunity to test the situation a little more thoroughly (ie at different offsets). Signed-off-by: Matthew Wilcox

idr-test: Convert ida_check_nomem to new API

2018-08-22T03:54:20+00:00

We can't move this test to kernel space because there's no way to force kmalloc to fail. But we can use the new API and check this works when the test is in userspace. Signed-off-by: Matthew Wilcox

ida: Start new test_ida module

2018-08-22T03:54:20+00:00

Start transitioning the IDA tests into kernel space. Framework heavily cribbed from test_xarray.c. Signed-off-by: Matthew Wilcox

radix tree test suite: Enable ubsan

2018-08-22T03:31:20+00:00

Add support for the undefined behaviour sanitizer and fix the bugs that ubsan pointed out. Nothing major, and all in the test suite, not the code. Signed-off-by: Matthew Wilcox

radix tree test suite: Fix compilation

2018-08-22T03:31:20+00:00

An include of xarray.h was added to lib/idr.c without updating the test suite. Signed-off-by: Matthew Wilcox

idr: fix invalid ptr dereference on item delete

2018-05-26T01:12:10+00:00

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: Debugged-by: Roman Kagan Signed-off-by: Matthew Wilcox Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds