kernel/linux.git/lib/generic-radix-tree.c, branch v6.12.80

lib/generic-radix-tree.c: add preallocation

2024-09-09T13:41:47+00:00

Signed-off-by: Kent Overstreet

lib/generic-radix-tree.c: genradix_ptr_inlined()

2024-09-09T13:41:47+00:00

Provide an inlined fast path Signed-off-by: Kent Overstreet

lib/generic-radix-tree.c: Fix rare race in __genradix_ptr_alloc()

2024-08-14T02:56:50+00:00

If we need to increase the tree depth, allocate a new node, and then race with another thread that increased the tree depth before us, we'll still have a preallocated node that might be used later. If we then use that node for a new non-root node, it'll still have a pointer to the old root instead of being zeroed - fix this by zeroing it in the cmpxchg failure path. Signed-off-by: Kent Overstreet

lib/generic-radix-tree.c: Make nodes more reasonably sized

2024-03-14T01:22:26+00:00

this code originally used the page allocator directly, but most code shouldn't do that - PAGE_SIZE varies with architecture, and slab is faster. 4k is also on the large side for typical usage, 512 bytes is a better choice for typical usage that might be somewhat sparse. Signed-off-by: Kent Overstreet

lib/generic-radix-tree.c: Add peek_prev()

2023-10-19T18:47:33+00:00

This patch adds genradix_peek_prev(), genradix_iter_rewind(), and genradix_for_each_reverse(), for iterating backwards over a generic radix tree. Signed-off-by: Kent Overstreet

lib/generic-radix-tree.c: Don't overflow in peek()

2023-10-19T18:47:33+00:00

When we started spreading new inode numbers throughout most of the 64 bit inode space, that triggered some corner case bugs, in particular some integer overflows related to the radix tree code. Oops. Signed-off-by: Kent Overstreet

lib/generic-radix-tree.c: add kmemleak annotations

2019-10-14T22:04:00+00:00

Kmemleak is falsely reporting a leak of the slab allocation in sctp_stream_init_ext(): BUG: memory leak unreferenced object 0xffff8881114f5d80 (size 96): comm "syz-executor934", pid 7160, jiffies 4294993058 (age 31.950s) hex dump (first 32 bytes): 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ backtrace: [<00000000ce7a1326>] kmemleak_alloc_recursive include/linux/kmemleak.h:55 [inline] [<00000000ce7a1326>] slab_post_alloc_hook mm/slab.h:439 [inline] [<00000000ce7a1326>] slab_alloc mm/slab.c:3326 [inline] [<00000000ce7a1326>] kmem_cache_alloc_trace+0x13d/0x280 mm/slab.c:3553 [<000000007abb7ac9>] kmalloc include/linux/slab.h:547 [inline] [<000000007abb7ac9>] kzalloc include/linux/slab.h:742 [inline] [<000000007abb7ac9>] sctp_stream_init_ext+0x2b/0xa0 net/sctp/stream.c:157 [<0000000048ecb9c1>] sctp_sendmsg_to_asoc+0x946/0xa00 net/sctp/socket.c:1882 [<000000004483ca2b>] sctp_sendmsg+0x2a8/0x990 net/sctp/socket.c:2102 [...] But it's freed later. Kmemleak misses the allocation because its pointer is stored in the generic radix tree sctp_stream::out, and the generic radix tree uses raw pages which aren't tracked by kmemleak. Fix this by adding the kmemleak hooks to the generic radix tree code. Link: http://lkml.kernel.org/r/20191004065039.727564-1-ebiggers@kernel.org Signed-off-by: Eric Biggers Reported-by: Reviewed-by: Marcelo Ricardo Leitner Acked-by: Neil Horman Reviewed-by: Catalin Marinas Cc: Kent Overstreet Cc: Vlad Yasevich Cc: Xin Long Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/generic-radix-tree.c: make 2 functions static inline

2019-09-26T00:51:39+00:00

When building with W=1, we get some warnings: l CC lib/generic-radix-tree.o lib/generic-radix-tree.c:39:10: warning: no previous prototype for 'genradix_root_to_depth' [-Wmissing-prototypes] 39 | unsigned genradix_root_to_depth(struct genradix_root *r) | ^~~~~~~~~~~~~~~~~~~~~~ lib/generic-radix-tree.c:44:23: warning: no previous prototype for 'genradix_root_to_node' [-Wmissing-prototypes] 44 | struct genradix_node *genradix_root_to_node(struct genradix_root *r) | ^~~~~~~~~~~~~~~~~~~~~ They're not used anywhere else, so make them static inline. Link: http://lkml.kernel.org/r/46923.1565236485@turing-police Signed-off-by: Valdis Kletnieks Cc: Kent Overstreet Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

generic radix trees

2019-03-12T17:04:02+00:00

Very simple radix tree implementation that supports storing arbitrary size entries, up to PAGE_SIZE - upcoming patches will convert existing flex_array users to genradixes. The new genradix code has a much simpler API and implementation, and doesn't have a hard limit on the number of elements like flex_array does. Link: http://lkml.kernel.org/r/20181217131929.11727-5-kent.overstreet@gmail.com Signed-off-by: Kent Overstreet Cc: Alexey Dobriyan Cc: Al Viro Cc: Dave Hansen Cc: Eric Paris Cc: Marcelo Ricardo Leitner Cc: Matthew Wilcox Cc: Neil Horman Cc: Paul Moore Cc: Pravin B Shelar Cc: Shaohua Li Cc: Stephen Smalley Cc: Vlad Yasevich Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds