aboutsummaryrefslogtreecommitdiffstats
path: root/tools/testing/radix-tree/idr-test.c (follow)
AgeCommit message (Collapse)AuthorFilesLines
2018-10-21ida: Convert to XArrayMatthew Wilcox1-5/+3
Use the XA_TRACK_FREE ability to track which entries have a free bit, similarly to how it uses the radix tree's IDR_FREE tag. This eliminates the per-cpu ida_bitmap preload, and fixes the memory consumption regression I introduced when making the IDR able to store any pointer. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-09-29xarray: Replace exceptional entriesMatthew Wilcox1-3/+3
Introduce xarray value entries and tagged pointers to replace radix tree exceptional entries. This is a slight change in encoding to allow the use of an extra bit (we can now store BITS_PER_LONG - 1 bits in a value entry). It is also a change in emphasis; exceptional entries are intimidating and different. As the comment explains, you can choose to store values or pointers in the xarray and they are both first-class citizens. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
2018-09-29idr: Permit any valid kernel pointer to be storedMatthew Wilcox1-0/+63
An upcoming change to the encoding of internal entries will set the bottom two bits to 0b10. Unfortunately, m68k only aligns some data structures to 2 bytes, so the IDR will interpret them as internal entries and things will go badly wrong. Change the radix tree so that it stops either when the node indicates that it's the bottom of the tree (shift == 0) or when the entry is not an internal entry. This means we cannot insert an arbitrary kernel pointer as a multiorder entry, but the IDR does not permit multiorder entries. Annoyingly, this means the IDR can no longer take advantage of the radix tree's ability to store a single entry at offset 0 without allocating memory. A pointer which is 2-byte aligned cannot be stored directly in the root as it would be indistinguishable from a node, so we must allocate a node in order to store a 2-byte pointer at index 0. The idr_replace() function does not take a GFP flags argument, so cannot allocate memory. If a user inserts a 4-byte aligned pointer at index 0 and then replaces it with a 2-byte aligned pointer, we must be able to store it. Arbitrary pointer values are still not permitted; pointers of the form 2 + (i * 4) for values of i between 0 and 1023 are reserved for the implementation. These are not valid kernel pointers as they would point into the zero page. This change does cause a runtime memory consumption regression for the IDA. I will recover that later. Signed-off-by: Matthew Wilcox <willy@infradead.org> Tested-by: Guenter Roeck <linux@roeck-us.net>
2018-08-21test_ida: check_ida_destroy and check_ida_allocMatthew Wilcox1-66/+4
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 <willy@infradead.org>
2018-08-21test_ida: Convert check_ida_conv to new APIMatthew Wilcox1-46/+10
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 <willy@infradead.org>
2018-08-21test_ida: Move ida_check_maxMatthew Wilcox1-28/+0
Convert to new API and move to kernel space. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-08-21test_ida: Move ida_check_leafMatthew Wilcox1-27/+0
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 <willy@infradead.org>
2018-08-21idr-test: Convert ida_check_nomem to new APIMatthew Wilcox1-6/+7
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 <willy@infradead.org>
2018-08-21ida: Start new test_ida moduleMatthew Wilcox1-3/+19
Start transitioning the IDA tests into kernel space. Framework heavily cribbed from test_xarray.c. Signed-off-by: Matthew Wilcox <willy@infradead.org>
2018-05-25idr: fix invalid ptr dereference on item deleteMatthew Wilcox1-0/+7
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> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2018-02-26idr: Fix handling of IDs above INT_MAXMatthew Wilcox1-0/+52
Khalid reported that the kernel selftests are currently failing: selftests: test_bpf.sh ======================================== test_bpf: [FAIL] not ok 1..8 selftests: test_bpf.sh [FAIL] He bisected it to 6ce711f2750031d12cec91384ac5cfa0a485b60a ("idr: Make 1-based IDRs more efficient"). The root cause is doing a signed comparison in idr_alloc_u32() instead of an unsigned comparison. I went looking for any similar problems and found a couple (which would each result in the failure to warn in two situations that aren't supposed to happen). I knocked up a few test-cases to prove that I was right and added them to the test-suite. Reported-by: Khalid Aziz <khalid.aziz@oracle.com> Tested-by: Khalid Aziz <khalid.aziz@oracle.com> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2018-02-06idr: Make 1-based IDRs more efficientMatthew Wilcox1-2/+5
About 20% of the IDR users in the kernel want the allocated IDs to start at 1. The implementation currently searches all the way down the left hand side of the tree, finds no free ID other than ID 0, walks all the way back up, and then all the way down again. This patch 'rebases' the ID so we fill the entire radix tree, rather than leave a gap at 0. Chris Wilson says: "I did the quick hack of allocating index 0 of the idr and that eradicated idr_get_free() from being at the top of the profiles for the many-object stress tests. This improvement will be much appreciated." Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2018-02-06idr: Remove idr_alloc_extMatthew Wilcox1-0/+17
It has no more users, so remove it. Move idr_alloc() back into idr.c, move the guts of idr_alloc_cmn() into idr_alloc_u32(), remove the wrappers around idr_get_free_cmn() and rename it to idr_get_free(). While there is now no interface to allocate IDs larger than a u32, the IDR internals remain ready to handle a larger ID should a need arise. These changes make it possible to provide the guarantee that, if the nextid pointer points into the object, the object's ID will be initialised before a concurrent lookup can find the object. Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2018-02-06IDR test suite: Check handling negative end correctlyMatthew Wilcox1-0/+1
One of the charming quirks of the idr_alloc() interface is that you can pass a negative end and it will be interpreted as "maximum". Ensure we don't break that. Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2018-02-06idr test suite: Fix ida_test_random()Matthew Wilcox1-2/+2
The test was checking the wrong errno; ida_get_new_above() returns EAGAIN, not ENOMEM on memory allocation failure. Double the number of threads to increase the chance that we actually exercise this path during the test suite (it was a bit sporadic before). Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2017-03-07ida: Free correct IDA bitmapMatthew Wilcox1-3/+31
There's a relatively rare race where we look at the per-cpu preallocated IDA bitmap, see it's NULL, allocate a new one, and atomically update it. If the kmalloc() happened to sleep and we were rescheduled to a different CPU, or an interrupt came in at the exact right time, another task might have successfully allocated a bitmap and already deposited it. I forgot what the semantics of cmpxchg() were and ended up freeing the wrong bitmap leading to KASAN reporting a use-after-free. Dmitry found the bug with syzkaller & wrote the patch. I wrote the test case that will reproduce the bug without his patch being applied. Reported-by: Dmitry Vyukov <dvyukov@google.com> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2017-03-07radix tree test suite: Add tests for ida_simple_get() and ida_simple_remove()Rehas Sachdeva1-0/+19
Assert that ida_simple_get() allocates an id in the passed range or returns error on failure, and ida_simple_remove() releases an allocated id. Signed-off-by: Rehas Sachdeva <aquannie@gmail.com> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2017-03-07radix tree test suite: Add test for idr_get_next()Rehas Sachdeva1-0/+25
Assert that idr_get_next() returns the next populated entry in the tree with an ID greater than or equal to the value pointed to by @nextid argument. Signed-off-by: Rehas Sachdeva <aquannie@gmail.com> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2017-02-13radix tree test suite: Build separate binaries for some testsMatthew Wilcox1-0/+11
To allow developers to run a subset of tests, build separate multiorder and idr-test binaries which will run just the tests in those files. Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> Reviewed-by: Rehas Sachdeva <aquannie@gmail.com>
2017-02-13ida: Use exceptional entries for small IDAsMatthew Wilcox1-1/+92
We can use the root entry as a bitmap and save allocating a 128 byte bitmap for an IDA that contains only a few entries (30 on a 32-bit machine, 62 on a 64-bit machine). This costs about 300 bytes of kernel text on x86-64, so as long as 3 IDAs fall into this category, this is a net win for memory consumption. Thanks to Rasmus Villemoes for his work documenting the problem and collecting statistics on IDAs. Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
2017-02-13Reimplement IDR and IDA using the radix treeMatthew Wilcox1-0/+342
The IDR is very similar to the radix tree. It has some functionality that the radix tree did not have (alloc next free, cyclic allocation, a callback-based for_each, destroy tree), which is readily implementable on top of the radix tree. A few small changes were needed in order to use a tag to represent nodes with free space below them. More extensive changes were needed to support storing NULL as a valid entry in an IDR. Plain radix trees still interpret NULL as a not-present entry. The IDA is reimplemented as a client of the newly enhanced radix tree. As in the current implementation, it uses a bitmap at the last level of the tree. Signed-off-by: Matthew Wilcox <willy@infradead.org> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> Tested-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Tejun Heo <tj@kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>