kernel/linux.git/include/linux/idr.h, branch v6.6.132

Fix termination state for idr_for_each_entry_ul()

2023-11-20T10:59:35+00:00

[ Upstream commit e8ae8ad479e2d037daa33756e5e72850a7bd37a9 ] The comment for idr_for_each_entry_ul() states after normal termination @entry is left with the value NULL This is not correct in the case where UINT_MAX has an entry in the idr. In that case @entry will be non-NULL after termination. No current code depends on the documentation being correct, but to save future code we should fix it. Also fix idr_for_each_entry_continue_ul(). While this is not documented as leaving @entry as NULL, the mellanox driver appears to depend on it doing so. So make that explicit in the documentation as well as in the code. Fixes: e33d2b74d805 ("idr: fix overflow case for idr_for_each_entry_ul()") Cc: Matthew Wilcox Cc: Chris Mi Cc: Cong Wang Signed-off-by: NeilBrown Signed-off-by: David S. Miller Signed-off-by: Sasha Levin

lib/idr.c: document that ida_simple_{get,remove}() are deprecated

2020-10-16T18:11:20+00:00

These two functions are deprecated. Users should call ida_alloc() or ida_free() respectively instead. Add documentation to this effect until the macro can be removed. Signed-off-by: Stephen Boyd Signed-off-by: Andrew Morton Reviewed-by: Tri Vo Cc: Greg KH Cc: Jonathan Corbet Cc: Matthew Wilcox Link: https://lkml.kernel.org/r/20200910055246.2297797-2-swboyd@chromium.org Signed-off-by: Linus Torvalds

lib/idr.c: document calling context for IDA APIs mustn't use locks

2020-10-16T18:11:20+00:00

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 Signed-off-by: Andrew Morton Reviewed-by: Greg Kroah-Hartman Cc: Tri Vo Cc: Jonathan Corbet Cc: Matthew Wilcox Link: https://lkml.kernel.org/r/20200910055246.2297797-1-swboyd@chromium.org Signed-off-by: Linus Torvalds

radix-tree: Use local_lock for protection

2020-05-28T08:31:09+00:00

The radix-tree and idr preload mechanisms use preempt_disable() to protect the complete operation between xxx_preload() and xxx_preload_end(). As the code inside the preempt disabled section acquires regular spinlocks, which are converted to 'sleeping' spinlocks on a PREEMPT_RT kernel and eventually calls into a memory allocator, this conflicts with the RT semantics. Convert it to a local_lock which allows RT kernels to substitute them with a real per CPU lock. On non RT kernels this maps to preempt_disable() as before, but provides also lockdep coverage of the critical region. No functional change. Signed-off-by: Sebastian Andrzej Siewior Signed-off-by: Ingo Molnar Acked-by: Peter Zijlstra Link: https://lore.kernel.org/r/20200527201119.1692513-3-bigeasy@linutronix.de

Merge tag 'xarray-5.4' of git://git.infradead.org/users/willy/linux-dax

2019-11-08T16:46:49+00:00

Pull XArray fixes from Matthew Wilcox: "These all fix various bugs, some of which people have tripped over and some of which have been caught by automatic tools" * tag 'xarray-5.4' of git://git.infradead.org/users/willy/linux-dax: idr: Fix idr_alloc_u32 on 32-bit systems idr: Fix integer overflow in idr_for_each_entry radix tree: Remove radix_tree_iter_find idr: Fix idr_get_next_ul race with idr_remove XArray: Fix xas_next() with a single entry at 0

idr: Fix integer overflow in idr_for_each_entry

2019-11-03T11:36:43+00:00

If there is an entry at INT_MAX then idr_for_each_entry() will increment id after handling it. This is undefined behaviour, and is caught by UBSAN. Adding 1U to id forces the operation to be carried out as an unsigned addition which (when assigned to id) will result in INT_MIN. Since there is never an entry stored at INT_MIN, idr_get_next() will return NULL, ending the loop as expected. Signed-off-by: Matthew Wilcox (Oracle)

idr: introduce idr_for_each_entry_continue_ul()

2019-07-02T02:15:46+00:00

Similarly, other callers of idr_get_next_ul() suffer the same overflow bug as they don't handle it properly either. Introduce idr_for_each_entry_continue_ul() to help these callers iterate from a given ID. cls_flower needs more care here because it still has overflow when does arg->cookie++, we have to fold its nested loops into one and remove the arg->cookie++. Fixes: 01683a146999 ("net: sched: refactor flower walk to iterate over idr") Fixes: 12d6066c3b29 ("net/mlx5: Add flow counters idr") Reported-by: Li Shuang Cc: Davide Caratti Cc: Vlad Buslov Cc: Chris Mi Cc: Matthew Wilcox Signed-off-by: Cong Wang Tested-by: Davide Caratti Signed-off-by: David S. Miller

idr: fix overflow case for idr_for_each_entry_ul()

2019-07-02T02:15:46+00:00

idr_for_each_entry_ul() is buggy as it can't handle overflow case correctly. When we have an ID == UINT_MAX, it becomes an infinite loop. This happens when running on 32-bit CPU where unsigned long has the same size with unsigned int. There is no better way to fix this than casting it to a larger integer, but we can't just 64 bit integer on 32 bit CPU. Instead we could just use an additional integer to help us to detect this overflow case, that is, adding a new parameter to this macro. Fortunately tc action is its only user right now. Fixes: 65a206c01e8e ("net/sched: Change act_api and act_xxx modules to use IDR") Reported-by: Li Shuang Tested-by: Davide Caratti Cc: Matthew Wilcox Cc: Chris Mi Signed-off-by: Cong Wang Signed-off-by: David S. Miller

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 220

2019-05-30T18:29:55+00:00

Based on 1 normalized pattern(s): distributed under the gnu gpl license version 2 extracted by the scancode license scanner the SPDX license identifier GPL-2.0-only has been chosen to replace the boilerplate/reference in 1 file(s). Signed-off-by: Thomas Gleixner Reviewed-by: Allison Randal Reviewed-by: Alexios Zavras Reviewed-by: Steve Winslow Reviewed-by: Kate Stewart Cc: linux-spdx@vger.kernel.org Link: https://lkml.kernel.org/r/20190528171439.854676954@linutronix.de Signed-off-by: Greg Kroah-Hartman

ida: Convert to XArray

2018-10-21T14:46:33+00:00

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