Linux内核中的红色黑色节点的结构对齐

Question

Linux内核中rb_node的定义如下:

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r)   ((r)->rb_parent_color & 1)
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)

我的问题是__rb_parent_color,其中最后一位是颜色,其余是指向其父级的指针.

我学到有人说最后2位__rb_parent_color因为没用aligned(sizeof(long)),但为什么呢？

不是sizeof(struct rb_node *)4还是不是sizeof(unsigned long)4？即使它们不相等,也应该aligned在Byte中如果没有对齐那么至少有一个整个Byte是无用的？

Answer 1

__attribute__((aligned(sizeof(long))))告诉编译器确保大小struct rb_node始终至少是其倍数sizeof(long).请参阅GCC文档.

这一点有点无关紧要(因为指针至少是这样sizeof(long).看看来源,你遗漏了最重要的部分:

/* The alignment might seem pointless, but allegedly CRIS needs it */

这个实现工作的关键是,struct rb_nodes将始终分配在至少4字节对齐的地址上.这是有保证的:

在32位cpus上保证4字节对齐,在64位cpus上保证8字节对齐.

例如,节点指针可能类似0xF724315C,以二进制结尾...1100.

这意味着任何指向a的指针的最后两位struct rb_node将为零.因此,开发人员决定将这两个位用于其他东西(这里是颜色).

我们在下面的宏中看到了这一点:

#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

要获得父节点,可以使用该宏,并使用较低的两位.