30 May, 2018
1 commit
-
commit 7a4deea1aa8bddfed4ef1b35fc2b6732563d8ad5 upstream.
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 packetLink: 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
Signed-off-by: Greg Kroah-Hartman
02 Nov, 2017
1 commit
-
Many source files in the tree are missing licensing information, which
makes it harder for compliance tools to determine the correct license.By default all files without license information are under the default
license of the kernel, which is GPL version 2.Update the files which contain no license information with the 'GPL-2.0'
SPDX license identifier. The SPDX identifier is a legally binding
shorthand, which can be used instead of the full boiler plate text.This patch is based on work done by Thomas Gleixner and Kate Stewart and
Philippe Ombredanne.How this work was done:
Patches were generated and checked against linux-4.14-rc6 for a subset of
the use cases:
- file had no licensing information it it.
- file was a */uapi/* one with no licensing information in it,
- file was a */uapi/* one with existing licensing information,Further patches will be generated in subsequent months to fix up cases
where non-standard license headers were used, and references to license
had to be inferred by heuristics based on keywords.The analysis to determine which SPDX License Identifier to be applied to
a file was done in a spreadsheet of side by side results from of the
output of two independent scanners (ScanCode & Windriver) producing SPDX
tag:value files created by Philippe Ombredanne. Philippe prepared the
base worksheet, and did an initial spot review of a few 1000 files.The 4.13 kernel was the starting point of the analysis with 60,537 files
assessed. Kate Stewart did a file by file comparison of the scanner
results in the spreadsheet to determine which SPDX license identifier(s)
to be applied to the file. She confirmed any determination that was not
immediately clear with lawyers working with the Linux Foundation.Criteria used to select files for SPDX license identifier tagging was:
- Files considered eligible had to be source code files.
- Make and config files were included as candidates if they contained >5
lines of source
- File already had some variant of a license header in it (even if
Reviewed-by: Philippe Ombredanne
Reviewed-by: Thomas Gleixner
Signed-off-by: Greg Kroah-Hartman
08 Mar, 2017
11 commits
-
Michael's patch to use the default make rule for linking and the patch
from Rehas to use -m32 if building a 32-bit test-suite on a 64-bit
platform don't work well together.Reported-by: Rehas Sachdeva
Signed-off-by: Matthew Wilcox -
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
Signed-off-by: Matthew Wilcox -
Changing the CFLAGS in the Makefile didn't always lead to a
recompilation because the OFILES didn't depend on the Makefile.
Also, after doing make clean, grep would still complain about
a missing map-shift.h; we need -s as well as -q.Signed-off-by: Matthew Wilcox
-
Currently the radix tree test suite doesn't build with toolchains that
use --as-needed by default, for example Ubuntu's:cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -lpthread -lurcu main.o ... -o main
/usr/bin/ld: regression1.o: undefined reference to symbol 'pthread_join@@GLIBC_2.17'
/lib/powerpc64le-linux-gnu/libpthread.so.0: error adding symbols: DSO missing from command line
collect2: error: ld returned 1 exit statusThis is caused by the custom makefile rules placing LDFLAGS before the
.o files that need the libraries.We could fix it by using --no-as-needed, or rewriting the custom rules.
But we can also just drop the custom rules and move the libraries to
LDLIBS, and then the default rules work correctly - with the one caveat
that we need to add -fsanitize=address to LDFLAGS because that must be
passed to the linker as well as the compiler.Signed-off-by: Michael Ellerman
Signed-off-by: Matthew Wilcox -
Add option 'make BUILD=32' for building 32-bit binaries.
Signed-off-by: Rehas Sachdeva
Signed-off-by: Matthew Wilcox -
Signed-off-by: Rehas Sachdeva
Signed-off-by: Matthew Wilcox -
Signed-off-by: Rehas Sachdeva
Signed-off-by: Matthew Wilcox -
Add performance benchmarks for radix tree insertion, tagging and deletion.
Signed-off-by: Rehas Sachdeva
Signed-off-by: Matthew Wilcox -
Assert that radix_tree_clear_tags() clears the tags on the passed node and
slot. Assert that the case where the radix tree has only one entry at index
zero and the node is NULL, is also handled.Signed-off-by: Rehas Sachdeva
Signed-off-by: Matthew Wilcox -
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
Signed-off-by: Matthew Wilcox -
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
Signed-off-by: Matthew Wilcox
14 Feb, 2017
20 commits
-
Add config option "SHIFT=" to Makefile for building test suite
with any value of RADIX_TREE_MAP_SHIFT between 3 and 7 inclusive.Signed-off-by: Rehas Sachdeva
[mawilcox@microsoft.com: .gitignore, quieten grep, remove on clean]
Signed-off-by: Matthew Wilcox -
If the -l flag is set, run the tests for 100 seconds each instead of
the normal 10 seconds.Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva -
The last of the memory leaks in the test suite was a couple of places in
the split/join testing where I forgot to free the element being removed
from the tree.Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva -
None of the malloc'ed data structures were ever being freed. Found with
-fsanitize=address.Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva -
If item_insert() or item_insert_order() failed to insert an item, they
would leak the item they had just created. This was causing runaway
memory consumption while running the iteration_check testcase, which
proves that Ross has too much memory in his workstation ;-)Make sure to free the item on error. Found with -fsanitize=address.
Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva -
I was looking for a memory scribble and instead found a pile of memory
leaks. Ensure no more occur in future.Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva -
Chaining through the ->private_data member means we have to zero
->private_data after removing preallocated nodes from the list.
We're about to initialise ->parent anyway, so we can avoid zeroing it.Signed-off-by: Matthew Wilcox
-
Make the output of radix tree test suite less verbose by default and add
-v and -vv command line options for increasing level of verbosity.Signed-off-by: Rehas Sachdeva
Signed-off-by: Matthew Wilcox -
To help track down where memory leaks may be, add the ability to turn
on/off printing allocations, frees and delayed frees.Signed-off-by: Matthew Wilcox
-
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
Reviewed-by: Rehas Sachdeva -
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
-
When we preload the IDA, we allocate an IDA bitmap. Instead of storing
that preallocated bitmap in the IDA, we store it in a percpu variable.
Generally there are more IDAs in the system than CPUs, so this cuts down
on the number of preallocated bitmaps that are unused, and about half
of the IDA users did not call ida_destroy() so they were leaking IDA
bitmaps.Signed-off-by: Matthew Wilcox
-
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
Signed-off-by: Matthew Wilcox
Tested-by: Kirill A. Shutemov
Cc: Konstantin Khlebnikov
Cc: Ross Zwisler
Cc: Tejun Heo
Signed-off-by: Andrew Morton -
radix-tree.c doesn't use these CONFIG options any more.
Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva -
Instead of specifying how to build find_bit.o from lib/find_bit.o,
use vpath to tell make where to find find_bit.c.Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva -
Many of the definitions in the radix-tree kernel.h are redundant with
others in tools/include, or are no longer used, such as panic().
Move the definition of __init to init.h and in_interrupt() to preempt.hSigned-off-by: Matthew Wilcox
-
The tools/include export.h contains everything we need.
Signed-off-by: Matthew Wilcox
-
Move the pieces we still need to tools/include and update a few implicit
includes.Signed-off-by: Matthew Wilcox
-
The radix tree hasn't used a mempool since the beginning of git history.
Remove the userspace mempool implementation.Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva -
Changing tools/include/asm/bug.h showed a missing dependency in the
Makefile.Signed-off-by: Matthew Wilcox
Reviewed-by: Rehas Sachdeva
28 Jan, 2017
2 commits
-
The definition of WARN_ON being used by the radix tree test suite was
deficient in two ways: it did not provide a return value, and it stopped
execution instead of continuing. This version of WARN_ON tells you
which file & line the assertion was triggered in.Signed-off-by: Matthew Wilcox
-
By adding __set_bit and __clear_bit to the tools include directory, we
can share the bitops code. This reveals an include loop between kernel.h,
log2.h, bitmap.h and bitops.h. Break it the same way as the kernel does;
by moving the kernel.h include from bitops.h to bitmap.h.Signed-off-by: Matthew Wilcox
16 Dec, 2016
1 commit
-
[ This resurrects commit 53855d10f456, which was reverted in
2b41226b39b6. It depended on commit d544abd5ff7d ("lib/radix-tree:
Convert to hotplug state machine") so now it is correct to apply ]Patch "lib/radix-tree: Convert to hotplug state machine" breaks the test
suite as it adds a call to cpuhp_setup_state_nocalls() which is not
currently emulated in the test suite. Add it, and delete the emulation
of the old CPU hotplug mechanism.Link: http://lkml.kernel.org/r/1480369871-5271-36-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox
Tested-by: Kirill A. Shutemov
Cc: Konstantin Khlebnikov
Cc: Ross Zwisler
Cc: Matthew Wilcox
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
15 Dec, 2016
4 commits
-
This file was used to implement call_rcu() before liburcu implemented
that function. It hasn't even been compiled since before the test suite
was added to the kernel. Remove it to reduce confusion.Link: http://lkml.kernel.org/r/1481667692-14500-5-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox
Cc: Kirill A. Shutemov
Cc: Konstantin Khlebnikov
Cc: Ross Zwisler
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
We have a check that setting a tag on a single entry at root succeeds,
but we were missing a check that clearing a tag on that same entry also
succeeds.Link: http://lkml.kernel.org/r/1481667692-14500-4-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox
Cc: Kirill A. Shutemov
Cc: Konstantin Khlebnikov
Cc: Ross Zwisler
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
radix_tree_join() was freeing nodes with a non-zero ->exceptional count,
and radix_tree_split() wasn't zeroing ->exceptional when it allocated
the new node. Fix this by making all callers of radix_tree_node_alloc()
pass in the new counts (and some other always-initialised fields), which
will prevent the problem recurring if in future we decide to do
something similar.Link: http://lkml.kernel.org/r/1481667692-14500-3-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox
Cc: Kirill A. Shutemov
Cc: Konstantin Khlebnikov
Cc: Ross Zwisler
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
The kmem_cache_alloc implementation simply allocates new memory from
malloc() and calls the ctor, which zeroes out the entire object. This
means it cannot spot bugs where the object isn't properly reinitialised
before being freed.Add a small (11 objects) cache before freeing objects back to malloc.
This is enough to let us write a test to catch it, although the memory
allocator is now aware of the structure of the radix tree node, since it
chains free objects through ->private_data (like the percpu cache does).Link: http://lkml.kernel.org/r/1481667692-14500-2-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox
Cc: Kirill A. Shutemov
Cc: Konstantin Khlebnikov
Cc: Ross Zwisler
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds