Production Case Study: Intrusive Augmented Red-Black Trees in the Linux Kernel CFS & VMA Manager

Three Kernel Engineering Breakthroughs in Linux rbtree.h

1. Intrusive Embedding & container_of(ptr, type, member)

In C++ std::map or Java TreeMap, inserting an object allocates a heap wrapper containing left, right, parent, color, and a pointer/copy of the payload. In Linux, struct rb_node contains only three unsigned long words (24 bytes): __rb_parent_color, rb_right, and rb_left. It is embedded directly inside the domain struct (and a single domain struct can embed multiple rb_node fields to participate in multiple trees simultaneously with zero heap allocations!). Given a struct rb_node *node, the macro rb_entry(node, struct task_struct, run_node) subtracts the compile-time offsetof(struct task_struct, run_node) in zero CPU instructions (folded into the base-displacement addressing mode mov rax, [rdi - 0x48])!

2. rb_root_cached: $O(1)$ rb_first() for the CFS vruntime Scheduler

The Linux Completely Fair Scheduler (CFS, introduced in 2.6.23 by Ingo Molnar) orders runnable tasks by their virtual runtime (vruntime in nanoseconds). On every context switch (thousands of times per second per core), CFS must pick the task with the smallest vruntime. Walking down the left spine in $O(\log N)$ on every context switch would waste precious cycles. Instead, Linux uses struct rb_root_cached, which stores rb_root alongside a cached pointer rb_leftmost. Whenever a new node is inserted and never branches right on its way down, rb_leftmost is updated in $O(1)$—making pick_next_task_fair() a single $O(1)$ pointer read!

3. Augmented Interval Gap Tree (rb_subtree_gap) in vm_area_struct

When a process calls mmap() to allocate an unmapped virtual address region of length $L$, the kernel used to scan the linked list of Virtual Memory Areas (VMAs) in $O(N)$ time. Since Linux 3.6, struct vm_area_struct embeds an Augmented Red-Black Tree (rbtree_augmented.h) where each VMA node maintains rb_subtree_gap: the maximum contiguous free virtual address gap anywhere in its subtree, computed via custom rotation callbacks (RB_DECLARE_CALLBACKS_MAX) to find a suitable address hole in $O(\log N)$ time! *(Note: In Linux 6.1+, VMA tracking has also introduced the RCU-safe B-tree-like Maple Tree alongside rbtree_augmented used in DRM/interval-tree subsystems.)*

Implementation: Linux-Style Intrusive Augmented RB-Node & container_of

// C11 / C++20: Linux Kernel-Style Intrusive RB-Node with Tagged Parent-Color & container_of
#include <cstddef>
#include <cstdint>

struct alignas(8) rb_node {
    uintptr_t __rb_parent_color; // Bit 0: 0 = RED, 1 = BLACK; Bits [63:2] = parent pointer
    rb_node* rb_right = nullptr;
    rb_node* rb_left  = nullptr;

    rb_node* parent() const noexcept {
        return reinterpret_cast<rb_node*>(__rb_parent_color & ~uintptr_t(3));
    }
    bool is_black() const noexcept { return (__rb_parent_color & 1U) != 0; }
    void set_parent_and_color(rb_node* p, int color) noexcept {
        __rb_parent_color = reinterpret_cast<uintptr_t>(p) | (color & 1U);
    }
};

struct rb_root_cached {
    rb_node* rb_node_root = nullptr;
    rb_node* rb_leftmost  = nullptr; // O(1) access to minimum element
};

#define rb_entry(ptr, type, member)     reinterpret_cast<type*>(reinterpret_cast<char*>(ptr) - offsetof(type, member))

// Example Domain Object: Runnable Task Entity with Zero-Allocation Intrusive Node
struct TaskEntity {
    uint64_t pid;
    rb_node run_node;      // Co-located in the same cache line as vruntime!
    uint64_t vruntime;
};

inline TaskEntity* pickNextTaskO1(const rb_root_cached& rq) noexcept {
    if (!rq.rb_leftmost) return nullptr;
    return rb_entry(rq.rb_leftmost, TaskEntity, run_node);
}