4. 红黑树节点结构：struct rb_node 详解
在 Linux 内核进程调度器的红黑树实现中，struct rb_node 是构成红黑树的基本单元。每个等待运行的进程（调度实体）都通过嵌入一个 rb_node 结构体来组织到红黑树中。该结构体的设计极其精巧，尤其是 __rb_parent_color 字段，它通过一个字段同时存储了父节点指针和节点颜色信息，极大地节省了内存空间。
4.1 struct rb_node 结构定义
内核中 struct rb_node 的定义位于 include/linux/rbtree.h，其核心结构如下：
struct rb_node {
unsigned long __rb_parent_color; // 父节点指针 + 颜色位
struct rb_node *rb_right; // 右孩子指针
struct rb_node *rb_left; // 左孩子指针
} __attribute__((aligned(sizeof(long))));
关键设计思想：利用指针地址的低位对齐特性（long 类型指针地址最低 2 位始终为 0），将红黑树的颜色信息（红/黑）存储在最低位，从而用一个字段同时承载父节点指针和颜色标记。
4.2 __rb_parent_color 字段的巧妙设计
该字段是红黑树节点设计的精髓所在。它通过位操作实现了“一字段两用”：
| 位域 | 用途 | 说明 |
|---|---|---|
| Bit 0（最低位） | 颜色标记 | 0 表示红色（Red），1 表示黑色（Black） |
| Bit 1 ~ Bit 63 | 父节点指针 | 存储父节点的实际地址（右移 1 位后的值） |
这种设计依赖于一个前提：所有 struct rb_node 结构体在内存中都是按 sizeof(long) 对齐的。在 64 位系统上，这意味着地址的最低 3 位（bit 0、1、2）始终为 0，因此最低位可以安全地用于存储颜色信息。
4.3 核心操作宏与内联函数
内核提供了一组宏和内联函数来操作 __rb_parent_color 字段，这些操作是红黑树插入和查找算法的基础：
// 从 __rb_parent_color 中提取父节点指针（清除最低位）
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
// 从 __rb_parent_color 中提取颜色值（仅保留最低位）
#define rb_color(r) ((r)->__rb_parent_color & 1)
// 判断节点是否为红色
#define rb_is_red(r) (!rb_color(r))
// 判断节点是否为黑色
#define rb_is_black(r) rb_color(r)
// 设置节点颜色为红色（将最低位置 0）
static inline void rb_set_red(struct rb_node *rb) {
rb->__rb_parent_color &= ~1;
}
// 设置节点颜色为黑色（将最低位置 1）
static inline void rb_set_black(struct rb_node *rb) {
rb->__rb_parent_color |= 1;
}
// 设置父节点指针（保留颜色位不变）
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) {
rb->__rb_parent_color = (rb->__rb_parent_color & 3) | (unsigned long)p;
}
// 同时设置父节点和颜色
static inline void rb_set_parent_color(struct rb_node *rb,
struct rb_node *p, int color) {
rb->__rb_parent_color = (unsigned long)p | color;
}
位运算技巧解析：宏
rb_parent(r) 使用 & ~3 而不是 & ~1，这是因为在 64 位系统上，为了兼容性，内核会清除最低 2 位（bit 0 和 bit 1）。实际上，颜色信息只占用 bit 0，bit 1 保留未使用，但清除 bit 1 可以确保指针的正确性。
4.4 字段设计的内存节省效果
这种设计带来的内存节省在进程调度器的大规模红黑树中非常显著：
| 对比项 | 传统设计（分开存储） | 内核设计（合并存储） | 节省量 |
|---|---|---|---|
| 父节点指针 | 8 字节（64 位） | 8 字节（与颜色共用） | 0 |
| 颜色字段 | 4 字节（int） | 0 字节（嵌入指针低位） | 4 字节 |
| 节点总大小 | 28 字节（含 padding） | 24 字节（3 个指针） | 4 字节 |
| 100 万节点总内存 | ~28 MB | ~24 MB | ~4 MB |
注意事项：直接使用
rb_parent(r) 宏时，必须确保传入的节点指针 r 不为 NULL。如果节点是根节点，其父节点指针为 NULL（即 __rb_parent_color 的低位仅包含颜色信息，高位为 0）。内核代码中通常通过 RB_EMPTY_ROOT 等宏来检查根节点。
4.5 节点结构内存布局示意图
下图展示了 struct rb_node 在 64 位系统中的内存布局，以及 __rb_parent_color 字段的位分配情况：
4.6 插入操作中的颜色与父节点操作流程
在红黑树插入过程中，__rb_parent_color 字段的更新是核心操作之一。以下流程图展示了插入一个新节点时，该字段的初始化与调整过程：
4.7 查找操作中的颜色与父节点使用
在查找操作中，__rb_parent_color 字段主要用于以下场景：
- 父节点回溯：当需要从当前节点向上回溯到父节点时，使用
rb_parent(node)宏提取父节点指针。 - 颜色判断：在插入后的修复过程中，需要频繁判断叔父节点、祖父节点的颜色，通过
rb_is_red()和rb_is_black()宏快速获取。 - 根节点检测：当
rb_parent(node) == NULL时，说明当前节点是树的根节点。
性能优势：由于颜色信息直接存储在指针的低位，读取颜色和父节点指针都只需要一次内存访问（读取
__rb_parent_color 字段），然后通过位运算即可分离出所需信息。相比分开存储需要两次内存访问，这种设计在缓存友好性和指令流水线效率上都有明显优势。
4.8 与其他红黑树实现的对比
| 实现方案 | 节点大小（64位） | 颜色存储方式 | 内存访问次数 | 典型应用 |
|---|---|---|---|---|
| Linux 内核实现 | 24 字节 | 嵌入父节点指针低位 | 1 次（读取后位运算） | 进程调度器、内存管理 |
| 传统教科书实现 | 28 字节 | 独立的 int 或 enum 字段 | 2 次（指针 + 颜色） | 教学示例、通用库 |
| C++ STL map 实现 | 32 字节 | 独立的 bool 字段（含 padding） | 2 次（指针 + 颜色） | 用户态通用容器 |
通过这种精巧的位域设计，Linux 内核在保持红黑树完整功能的同时，将每个节点的内存开销降低了约 14%，这对于需要管理数十万甚至数百万调度实体的进程调度器来说，是一个非常重要的优化。