#
af73483f |
| 21-Dec-2023 |
Matthew Wilcox (Oracle) <willy@infradead.org> |
ida: Fix crash in ida_free when the bitmap is empty
The IDA usually detects double-frees, but that detection failed to consider the case when there are no nearby IDs allocated and so we have a NULL
ida: Fix crash in ida_free when the bitmap is empty
The IDA usually detects double-frees, but that detection failed to consider the case when there are no nearby IDs allocated and so we have a NULL bitmap rather than simply having a clear bit. Add some tests to the test-suite to be sure we don't inadvertently reintroduce this problem. Unfortunately they're quite noisy so include a message to disregard the warnings.
Reported-by: Zhenghan Wang <wzhmmmmm@gmail.com> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
2a15de80 |
| 26-Aug-2023 |
Ariel Marcovitch <arielmarcovitch@gmail.com> |
idr: fix param name in idr_alloc_cyclic() doc
The relevant parameter is 'start' and not 'nextid'
Fixes: 460488c58ca8 ("idr: Remove idr_alloc_ext") Signed-off-by: Ariel Marcovitch <arielmarcovitch@g
idr: fix param name in idr_alloc_cyclic() doc
The relevant parameter is 'start' and not 'nextid'
Fixes: 460488c58ca8 ("idr: Remove idr_alloc_ext") Signed-off-by: Ariel Marcovitch <arielmarcovitch@gmail.com> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
show more ...
|
#
fc82bbf4 |
| 10-Jul-2022 |
Linus Torvalds <torvalds@linux-foundation.org> |
ida: don't use BUG_ON() for debugging
This is another old BUG_ON() that just shouldn't exist (see also commit a382f8fee42c: "signal handling: don't use BUG_ON() for debugging").
In fact, as Matthew
ida: don't use BUG_ON() for debugging
This is another old BUG_ON() that just shouldn't exist (see also commit a382f8fee42c: "signal handling: don't use BUG_ON() for debugging").
In fact, as Matthew Wilcox points out, this condition shouldn't really even result in a warning, since a negative id allocation result is just a normal allocation failure:
"I wonder if we should even warn here -- sure, the caller is trying to free something that wasn't allocated, but we don't warn for kfree(NULL)"
and goes on to point out how that current error check is only causing people to unnecessarily do their own index range checking before freeing it.
This was noted by Itay Iellin, because the bluetooth HCI socket cookie code does *not* do that range checking, and ends up just freeing the error case too, triggering the BUG_ON().
The HCI code requires CAP_NET_RAW, and seems to just result in an ugly splat, but there really is no reason to BUG_ON() here, and we have generally striven for allocation models where it's always ok to just do
free(alloc());
even if the allocation were to fail for some random reason (usually obviously that "random" reason being some resource limit).
Fixes: 88eca0207cf1 ("ida: simplified functions for id allocation") Reported-by: Itay Iellin <ieitayie@gmail.com> Suggested-by: Matthew Wilcox <willy@infradead.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
3b674261 |
| 16-Oct-2020 |
Stephen Boyd <swboyd@chromium.org> |
lib/idr.c: document calling context for IDA APIs mustn't use locks
The documentation for these functions indicates that callers don't need to hold a lock while calling them, but that documentation i
lib/idr.c: document calling context for IDA APIs mustn't use locks
The documentation for these functions indicates that callers don't need to hold a lock while calling them, but that documentation is only in one place under "IDA Usage". Let's state the same information on each IDA function so that it's clear what the calling context requires. Furthermore, let's document ida_simple_get() with the same information so that callers know how this API works.
Signed-off-by: Stephen Boyd <swboyd@chromium.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Reviewed-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Cc: Tri Vo <trong@android.com> Cc: Jonathan Corbet <corbet@lwn.net> Cc: Matthew Wilcox <willy@infradead.org> Link: https://lkml.kernel.org/r/20200910055246.2297797-1-swboyd@chromium.org Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
a219b856 |
| 02-Apr-2020 |
Matthew Wilcox (Oracle) <willy@infradead.org> |
ida: Free allocated bitmap in error path
If a bitmap needs to be allocated, and then by the time the thread is scheduled to be run again all the indices which would satisfy the allocation have been
ida: Free allocated bitmap in error path
If a bitmap needs to be allocated, and then by the time the thread is scheduled to be run again all the indices which would satisfy the allocation have been allocated then we would leak the allocation. Almost impossible to hit in practice, but a trivial fix. Found by Coverity.
Fixes: f32f004cddf8 ("ida: Convert to XArray") Reported-by: coverity-bot <keescook+coverity-bot@chromium.org> Reviewed-by: Kees Cook <keescook@chromium.org> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
show more ...
|
#
5a74ac4c |
| 02-Nov-2019 |
Matthew Wilcox (Oracle) <willy@infradead.org> |
idr: Fix idr_get_next_ul race with idr_remove
Commit 5c089fd0c734 ("idr: Fix idr_get_next race with idr_remove") neglected to fix idr_get_next_ul(). As far as I can tell, nobody's actually using th
idr: Fix idr_get_next_ul race with idr_remove
Commit 5c089fd0c734 ("idr: Fix idr_get_next race with idr_remove") neglected to fix idr_get_next_ul(). As far as I can tell, nobody's actually using this interface under the RCU read lock, but fix it now before anybody decides to use it.
Fixes: 5c089fd0c734 ("idr: Fix idr_get_next race with idr_remove") Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
show more ...
|
#
5c089fd0 |
| 14-May-2019 |
Matthew Wilcox (Oracle) <willy@infradead.org> |
idr: Fix idr_get_next race with idr_remove
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
idr: Fix idr_get_next race with idr_remove
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 <bgregg@netflix.com> Tested-by: Brendan Gregg <bgregg@netflix.com> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
show more ...
|
#
457c8996 |
| 19-May-2019 |
Thomas Gleixner <tglx@linutronix.de> |
treewide: Add SPDX license identifier for missed files
Add SPDX license identifiers to all files which:
- Have no license information of any form
- Have EXPORT_.*_SYMBOL_GPL inside which was use
treewide: Add SPDX license identifier for missed files
Add SPDX license identifiers to all files which:
- Have no license information of any form
- Have EXPORT_.*_SYMBOL_GPL inside which was used in the initial scan/conversion to ignore the file
These files fall under the project license, GPL v2 only. The resulting SPDX license identifier is:
GPL-2.0-only
Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
show more ...
|
#
1cf56f9d |
| 09-Apr-2018 |
Matthew Wilcox <willy@infradead.org> |
radix tree: Remove radix_tree_update_node_t
The only user of this functionality was the workingset code, and it's now been converted to the XArray. Remove __radix_tree_delete_node() entirely as it
radix tree: Remove radix_tree_update_node_t
The only user of this functionality was the workingset code, and it's now been converted to the XArray. Remove __radix_tree_delete_node() entirely as it was also only used by the workingset code.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
#
f32f004c |
| 04-Jul-2018 |
Matthew Wilcox <willy@infradead.org> |
ida: Convert to XArray
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,
ida: Convert to XArray
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>
show more ...
|
#
f8d5d0cc |
| 07-Nov-2017 |
Matthew Wilcox <willy@infradead.org> |
xarray: Add definition of struct xarray
This is a direct replacement for struct radix_tree_root. Some of the struct members have changed name; convert those, and use a #define so that radix_tree us
xarray: Add definition of struct xarray
This is a direct replacement for struct radix_tree_root. Some of the struct members have changed name; convert those, and use a #define so that radix_tree users continue to work without change.
Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
show more ...
|
#
3159f943 |
| 03-Nov-2017 |
Matthew Wilcox <willy@infradead.org> |
xarray: Replace exceptional entries
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 bi
xarray: Replace exceptional entries
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>
show more ...
|
#
66ee620f |
| 25-Jun-2018 |
Matthew Wilcox <willy@infradead.org> |
idr: Permit any valid kernel pointer to be stored
An upcoming change to the encoding of internal entries will set the bottom two bits to 0b10. Unfortunately, m68k only aligns some data structures t
idr: Permit any valid kernel pointer to be stored
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>
show more ...
|
#
1df89519 |
| 18-Jun-2018 |
Matthew Wilcox <willy@infradead.org> |
ida: Change ida_get_new_above to return the id
This calling convention makes more sense for the implementation as well as the callers. It even shaves 32 bytes off the compiled code size.
Signed-of
ida: Change ida_get_new_above to return the id
This calling convention makes more sense for the implementation as well as the callers. It even shaves 32 bytes off the compiled code size.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
#
b03f8e43 |
| 18-Jun-2018 |
Matthew Wilcox <willy@infradead.org> |
ida: Remove old API
Delete ida_pre_get(), ida_get_new(), ida_get_new_above() and ida_remove() from the public API. Some of these functions still exist as internal helpers, but they should not be ca
ida: Remove old API
Delete ida_pre_get(), ida_get_new(), ida_get_new_above() and ida_remove() from the public API. Some of these functions still exist as internal helpers, but they should not be called by consumers.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
#
5ade60dd |
| 20-Mar-2018 |
Matthew Wilcox <willy@infradead.org> |
ida: Add new API
Add ida_alloc(), ida_alloc_min(), ida_alloc_max(), ida_alloc_range() and ida_free(). The ida_alloc_max() and ida_alloc_range() functions differ from ida_simple_get() in that they t
ida: Add new API
Add ida_alloc(), ida_alloc_min(), ida_alloc_max(), ida_alloc_range() and ida_free(). The ida_alloc_max() and ida_alloc_range() functions differ from ida_simple_get() in that they take an inclusive 'max' parameter instead of an exclusive 'end' parameter. Callers are about evenly split whether they'd like inclusive or exclusive parameters and 'max' is easier to document than 'end'.
Change the IDA allocation to first attempt to allocate a bit using existing memory, and only allocate memory afterwards. Also change the behaviour of 'min' > INT_MAX from being a BUG() to returning -ENOSPC.
Leave compatibility wrappers in place for ida_simple_get() and ida_simple_remove() to avoid changing all callers.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
#
50d97d50 |
| 21-Jun-2018 |
Matthew Wilcox <willy@infradead.org> |
ida: Lock the IDA in ida_destroy
The user has no need to handle locking between ida_simple_get() and ida_simple_remove(). They shouldn't be forced to think about whether ida_destroy() might be call
ida: Lock the IDA in ida_destroy
The user has no need to handle locking between ida_simple_get() and ida_simple_remove(). They shouldn't be forced to think about whether ida_destroy() might be called at the same time as any of their other IDA manipulation calls. Improve the documnetation while I'm in here.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
show more ...
|
#
b94078e6 |
| 08-Jun-2018 |
Matthew Wilcox <mawilcox@microsoft.com> |
lib/idr.c: remove simple_ida_lock
Improve the scalability of the IDA by using the per-IDA xa_lock rather than the global simple_ida_lock. IDAs are not typically used in performance-sensitive locati
lib/idr.c: remove simple_ida_lock
Improve the scalability of the IDA by using the per-IDA xa_lock rather than the global simple_ida_lock. IDAs are not typically used in performance-sensitive locations, but since we have this lock anyway, we can use it. It is also a step towards converting the IDA from the radix tree to the XArray.
[akpm@linux-foundation.org: idr.c needs xarray.h] Link: http://lkml.kernel.org/r/20180331125332.GF13332@bombadil.infradead.org Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> Reviewed-by: Andrew Morton <akpm@linux-foundation.org> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Daniel Vetter <daniel.vetter@ffwll.ch> Cc: Tejun Heo <tj@kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
4b0ad076 |
| 26-Feb-2018 |
Matthew Wilcox <mawilcox@microsoft.com> |
idr: Fix handling of IDs above INT_MAX
Khalid reported that the kernel selftests are currently failing:
selftests: test_bpf.sh ======================================== test_bpf: [FAIL] not ok 1..8
idr: Fix handling of IDs above INT_MAX
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>
show more ...
|
#
b1a8a7a7 |
| 21-Feb-2018 |
Rasmus Villemoes <linux@rasmusvillemoes.dk> |
ida: do zeroing in ida_pre_get()
As far as I can tell, the only place the per-cpu ida_bitmap is populated is in ida_pre_get. The pre-allocated element is stolen in two places in ida_get_new_above,
ida: do zeroing in ida_pre_get()
As far as I can tell, the only place the per-cpu ida_bitmap is populated is in ida_pre_get. The pre-allocated element is stolen in two places in ida_get_new_above, in both cases immediately followed by a memset(0).
Since ida_get_new_above is called with locks held, do the zeroing in ida_pre_get, or rather let kmalloc() do it. Also, apparently gcc generates ~44 bytes of code to do a memset(, 0, 128):
$ scripts/bloat-o-meter vmlinux.{0,1} add/remove: 0/0 grow/shrink: 2/1 up/down: 5/-88 (-83) Function old new delta ida_pre_get 115 119 +4 vermagic 27 28 +1 ida_get_new_above 715 627 -88
Link: http://lkml.kernel.org/r/20180108225634.15340-1-linux@rasmusvillemoes.dk Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Acked-by: Matthew Wilcox <mawilcox@microsoft.com> Cc: Eric Biggers <ebiggers@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
show more ...
|
#
6ce711f2 |
| 30-Nov-2017 |
Matthew Wilcox <mawilcox@microsoft.com> |
idr: Make 1-based IDRs more efficient
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
idr: Make 1-based IDRs more efficient
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>
show more ...
|
#
72fd6c7b |
| 28-Nov-2017 |
Matthew Wilcox <mawilcox@microsoft.com> |
idr: Warn if old iterators see large IDs
Now that the IDR can be used to store large IDs, it is possible somebody might only partially convert their old code and use the iterators which can only han
idr: Warn if old iterators see large IDs
Now that the IDR can be used to store large IDs, it is possible somebody might only partially convert their old code and use the iterators which can only handle IDs up to INT_MAX. It's probably unwise to show them a truncated ID, so settle for spewing warnings to dmesg, and terminating the iteration.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
show more ...
|
#
7a457577 |
| 28-Nov-2017 |
Matthew Wilcox <mawilcox@microsoft.com> |
idr: Rename idr_for_each_entry_ext
Most places in the kernel that we need to distinguish functions by the type of their arguments, we use '_ul' as a suffix for the unsigned long variant, not '_ext'.
idr: Rename idr_for_each_entry_ext
Most places in the kernel that we need to distinguish functions by the type of their arguments, we use '_ul' as a suffix for the unsigned long variant, not '_ext'. Also add kernel-doc.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
show more ...
|
#
460488c5 |
| 28-Nov-2017 |
Matthew Wilcox <mawilcox@microsoft.com> |
idr: Remove idr_alloc_ext
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()
idr: Remove idr_alloc_ext
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>
show more ...
|
#
e096f6a7 |
| 28-Nov-2017 |
Matthew Wilcox <mawilcox@microsoft.com> |
idr: Add idr_alloc_u32 helper
All current users of idr_alloc_ext() actually want to allocate a u32 and idr_alloc_u32() fits their needs better.
Like idr_get_next(), it uses a 'nextid' argument whic
idr: Add idr_alloc_u32 helper
All current users of idr_alloc_ext() actually want to allocate a u32 and idr_alloc_u32() fits their needs better.
Like idr_get_next(), it uses a 'nextid' argument which serves as both a pointer to the start ID and the assigned ID (instead of a separate minimum and pointer-to-assigned-ID argument). It uses a 'max' argument rather than 'end' because the semantics that idr_alloc has for 'end' don't work well for unsigned types.
Since idr_alloc_u32() returns an errno instead of the allocated ID, mark it as __must_check to help callers use it correctly. Include copious kernel-doc. Chris Mi <chrism@mellanox.com> has promised to contribute test-cases for idr_alloc_u32.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
show more ...
|