4

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 是无用的？

4

1 回答 1

6

__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 位 CPU 上保证 4 字节对齐，在 64 位 CPU 上保证 8 字节对齐。

例如，节点指针可能类似于0xF724315C，在二进制文件中以...1100.

这意味着任何指向 a的指针的最后两位struct rb_node都是零。因此，开发人员决定将这两个位用于其他用途（这里是颜色。）

我们在以下宏中看到了这一点：

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

要获得父节点，可以使用与低两位相加的宏。

于 2013-06-25T03:44:05.270 回答