Changes in generic-radix-tree.c

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

Sun, 11 Aug 2024 03:14:44 +0000

lib/generic-radix-tree.c: add preallocationSigned-off-by: Kent Overstreet List of files: /linux-6.15/lib/generic-radix-tree.c

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

Mon, 17 Jun 2024 23:00:33 +0000

lib/generic-radix-tree.c: genradix_ptr_inlined()Provide an inlined fast pathSigned-off-by: Kent Overstreet List of files: /linux-6.15/lib/generic-radix-tree.c

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

Sun, 11 Aug 2024 01:04:35 +0000

lib/generic-radix-tree.c: Fix rare race in __genradix_ptr_alloc()If we need to increase the tree depth, allocate a new node, and thenrace with another thread that increased the tree depth before us, we'llstill 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 apointer to the old root instead of being zeroed - fix this by zeroing itin the cmpxchg failure path.Signed-off-by: Kent Overstreet List of files: /linux-6.15/lib/generic-radix-tree.c

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

Fri, 08 Mar 2024 03:32:06 +0000

lib/generic-radix-tree.c: Make nodes more reasonably sizedthis code originally used the page allocator directly, but most codeshouldn't do that - PAGE_SIZE varies with architecture, and slab isfaster.4k is also on the large side for typical usage, 512 bytes is a betterchoice for typical usage that might be somewhat sparse.Signed-off-by: Kent Overstreet List of files: /linux-6.15/lib/generic-radix-tree.c

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

Tue, 12 Sep 2023 05:17:22 +0000

lib/generic-radix-tree.c: Add peek_prev()This patch adds genradix_peek_prev(), genradix_iter_rewind(), andgenradix_for_each_reverse(), for iterating backwards over a genericradix tree.Signed-off-by: Kent Overstreet List of files: /linux-6.15/lib/generic-radix-tree.c

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

Sat, 13 Feb 2021 01:11:25 +0000

lib/generic-radix-tree.c: Don't overflow in peek()When we started spreading new inode numbers throughout most of the 64bit inode space, that triggered some corner case bugs, in particularsome integer overflows related to the radix tree code. Oops.Signed-off-by: Kent Overstreet List of files: /linux-6.15/lib/generic-radix-tree.c

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

Mon, 14 Oct 2019 21:11:54 +0000

lib/generic-radix-tree.c: add kmemleak annotationsKmemleak is falsely reporting a leak of the slab allocation insctp_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 itspointer is stored in the generic radix tree sctp_stream::out, and thegeneric 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.orgSigned-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 List of files: /linux-6.15/lib/generic-radix-tree.c

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

Wed, 25 Sep 2019 23:46:23 +0000

lib/generic-radix-tree.c: make 2 functions static inlineWhen building with W=1, we get some warnings:l CC lib/generic-radix-tree.olib/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-policeSigned-off-by: Valdis Kletnieks Cc: Kent Overstreet Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds List of files: /linux-6.15/lib/generic-radix-tree.c

ba20ba2e - generic radix trees

Tue, 12 Mar 2019 06:31:14 +0000

generic radix treesVery simple radix tree implementation that supports storing arbitrarysize entries, up to PAGE_SIZE - upcoming patches will convert existingflex_array users to genradixes. The new genradix code has a muchsimpler API and implementation, and doesn't have a hard limit on thenumber of elements like flex_array does.Link: http://lkml.kernel.org/r/20181217131929.11727-5-kent.overstreet@gmail.comSigned-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 List of files: /linux-6.15/lib/generic-radix-tree.c