linux.git/include/linux/rbtree.h, branch v7.1-rc4

rbtree: Provide rbtree with links

2026-02-27T15:40:16+00:00

Some RB tree users require quick access to the next and the previous node,
e.g. to check whether a modification of the node results in a change of the
nodes position in the tree. If the node position does not change, then the
modification can happen in place without going through a full enqueue
requeue cycle. A upcoming use case for this are the timer queues of the
hrtimer subsystem as they can optimize for timers which are frequently
rearmed while enqueued.

This can be obviously achieved with rb_next() and rb_prev(), but those
turned out to be quite expensive for hotpath operations depending on the
tree depth.

Add a linked RB tree variant where add() and erase() maintain the links
between the nodes. Like the cached variant it provides a pointer to the
left most node in the root.

It intentionally does not use a [h]list head as there is no real need for
true list operations as the list is strictly coupled to the tree and
and cannot be manipulated independently.

It sets the nodes previous pointer to NULL for the left most node and the
next pointer to NULL for the right most node. This allows a quick check
especially for the left most node without consulting the list head address,
which creates better code.

Aside of the rb_leftmost cached pointer this could trivially provide a
rb_rightmost pointer as well, but there is no usage for that (yet).

Signed-off-by: Thomas Gleixner 
Signed-off-by: Peter Zijlstra (Intel) 
Link: https://patch.msgid.link/20260224163431.668401024@kernel.org

rbtree: inline rb_last()

2025-11-27T22:24:30+00:00

This is a very small function, inlining it saves cpu cycles in TCP by
reducing register pressure and removing call/ret overhead.

It also reduces vmlinux text size by 122 bytes on a typical x86_64 build.

Before:

size vmlinux
   text    data     bss     dec     hex filename
34811781        22177365        5685248 62674394        3bc55da vmlinux

After:

size vmlinux
   text	   data	    bss	    dec	    hex	filename
34811659	22177365	5685248	62674272	3bc5560	vmlinux

[ojeda@kernel.org: fix rust build]
  Link: https://lkml.kernel.org/r/20251120085518.1463498-1-ojeda@kernel.org
Link: https://lkml.kernel.org/r/20251114140646.3817319-3-edumazet@google.com
Signed-off-by: Eric Dumazet 
Signed-off-by: Miguel Ojeda 
Reviewed-by: Kuan-Wei Chiu 
Cc: Jakub Kacinski 
Cc: Neal Cardwell 
Cc: Paolo Abeni 
Cc: Alice Ryhl 
Cc: Stehen Rothwell 
Signed-off-by: Andrew Morton

rbtree: inline rb_first()

2025-11-27T22:24:30+00:00

Patch series "rbree: inline rb_first() and rb_last()".

Inline these two small helpers, heavily used in TCP and FQ packet scheduler,
and in many other places.

This reduces kernel text size, and brings an 1.5 % improvement on network
TCP stress test.


This patch (of 2):

This is a very small function, inlining it saves cpu cycles by reducing
register pressure and removing call/ret overhead.

It also reduces vmlinux text size by 744 bytes on a typical x86_64 build.

Before:

size vmlinux
   text	   data	    bss	    dec	    hex	filename
34812525	22177365	5685248	62675138	3bc58c2	vmlinux

After:

size vmlinux
   text	   data	    bss	    dec	    hex	filename
34811781	22177365	5685248	62674394	3bc55da	vmlinux

[ojeda@kernel.org: fix rust build]
  Link: https://lkml.kernel.org/r/20251120085518.1463498-1-ojeda@kernel.org
Link: https://lkml.kernel.org/r/20251114140646.3817319-1-edumazet@google.com
Link: https://lkml.kernel.org/r/20251114140646.3817319-2-edumazet@google.com
Signed-off-by: Eric Dumazet 
Signed-off-by: Miguel Ojeda 
Reviewed-by: Kuan-Wei Chiu 
Cc: Jakub Kacinski 
Cc: Neal Cardwell 
Cc: Paolo Abeni 
Cc: Alice Ryhl 
Cc: Stehen Rothwell 
Signed-off-by: Andrew Morton

rbtree: add rb_find_add_cached() to rbtree.h

2025-01-13T13:53:18+00:00

Adds rb_find_add_cached() as a helper function for use with red-black
trees. Used in btrfs to reduce boilerplate code.

And since it's a new helper, the cmp() function will require both
parameter to be const rb_node pointers.

Suggested-by: Josef Bacik 
Signed-off-by: Roger L. Beckermeyer III 
Acked-by: Peter Zijlstra (Intel) 
Reviewed-by: Qu Wenruo 
Signed-off-by: Qu Wenruo 
Reviewed-by: David Sterba 
Signed-off-by: David Sterba

rbtree: provide rb_find_rcu() / rb_find_add_rcu()

2024-09-05T14:56:15+00:00

Much like latch_tree, add two RCU methods for the regular RB-tree,
which can be used in conjunction with a seqcount to provide lockless
lookups.

Signed-off-by: Peter Zijlstra (Intel) 
Signed-off-by: "Peter Zijlstra (Intel)" 
Signed-off-by: Peter Zijlstra (Intel) 
Reviewed-by: Oleg Nesterov 
Reviewed-by: "Masami Hiramatsu (Google)" 
Link: https://lore.kernel.org/r/20240903174603.3554182-7-andrii@kernel.org

include/linux/rbtree.h: replace kernel.h with the necessary inclusions

2022-06-17T02:58:20+00:00

When kernel.h is used in the headers it adds a lot into dependency hell,
especially when there are circular dependencies are involved.

Replace kernel.h inclusion with the list of what is really being used.

Link: https://lkml.kernel.org/r/20220603171012.48880-1-andriy.shevchenko@linux.intel.com
Signed-off-by: Andy Shevchenko 
Cc: Matthew Wilcox 
Signed-off-by: Andrew Morton

rbtree: Split out the rbtree type definitions into

2021-08-17T15:36:48+00:00

So we have this header dependency problem on RT:

 -  needs the definition of 'struct rb_root_cached'.
 -  includes , which includes .

That works nicely for non-RT enabled kernels, but on RT enabled kernels
spinlocks are based on rtmutexes, which creates another circular header
dependency, as  will require .

Split out the type definitions and move them into their own header file so
the rtmutex header can include just those.

Signed-off-by: Sebastian Andrzej Siewior 
Signed-off-by: Thomas Gleixner 
Signed-off-by: Peter Zijlstra (Intel) 
Signed-off-by: Ingo Molnar 
Link: https://lore.kernel.org/r/20210815211303.542123501@linutronix.de

rbtree, sched/deadline: Use rb_add_cached()

2021-02-17T13:07:44+00:00

Reduce rbtree boiler plate by using the new helpers.

Make rb_add_cached() / rb_erase_cached() return a pointer to the
leftmost node to aid in updating additional state.

Signed-off-by: Peter Zijlstra (Intel) 
Signed-off-by: Ingo Molnar 
Acked-by: Davidlohr Bueso

rbtree: Add generic add and find helpers

2021-02-17T13:07:31+00:00

I've always been bothered by the endless (fragile) boilerplate for
rbtree, and I recently wrote some rbtree helpers for objtool and
figured I should lift them into the kernel and use them more widely.

Provide:

partial-order; less() based:
 - rb_add(): add a new entry to the rbtree
 - rb_add_cached(): like rb_add(), but for a rb_root_cached

total-order; cmp() based:
 - rb_find(): find an entry in an rbtree
 - rb_find_add(): find an entry, and add if not found

 - rb_find_first(): find the first (leftmost) matching entry
 - rb_next_match(): continue from rb_find_first()
 - rb_for_each(): iterate a sub-tree using the previous two

Inlining and constant propagation should see the compiler inline the
whole thing, including the various compare functions.

Signed-off-by: Peter Zijlstra (Intel) 
Signed-off-by: Ingo Molnar 
Reviewed-by: Michel Lespinasse 
Acked-by: Davidlohr Bueso

docs: Add rbtree documentation to the core-api

2020-04-21T16:29:19+00:00

This file is close enough to being in rst format that I didn't feel
the need to alter it in any way.

Signed-off-by: Matthew Wilcox (Oracle) 
Acked-by: Michel Lespinasse 
Link: https://lore.kernel.org/r/20200401173343.17472-1-willy@infradead.org
Signed-off-by: Jonathan Corbet