Red black node's struct alignment in linux kernel

Question

The defination of rb_node in linux kernel is as follow:

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)

My question is about __rb_parent_color, of which the last bit is the color and the rest is a pointer to its parent.

I learned someone say the last 2 bit of __rb_parent_color is useless because of aligned(sizeof(long)) , but why?

Is not sizeof(struct rb_node *) 4 or Is not sizeof(unsigned long) 4? Even they are not equal, should aligned in Byte and if not aligned there will be at least one whole Byte is useless?

Answer 1

__attribute__((aligned(sizeof(long)))) tells the compiler to ensure that the size of struct rb_node is always going to be at least a multiple of sizeof(long). See GCC docs.

That point is somewhat irrelevant though (because the pointers are at least sizeof(long). And looking at the source, you left out the most important part:

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

---

The key to this implementation working, is that struct rb_nodes will always be allocated on addresses that are at least 4-byte aligned. This is guaranteed:

4-byte alignment is guaranteed on 32-bit cpus, 8-byte alignment on 64-bit cpus.

For example, a node pointer might be like 0xF724315C, which in binary ends in ...1100.

That means that the last two bits of any pointer to a struct rb_node will be zero. Because of this, the developers decided to use those two bits for something else (here, the color.)

We see this in the following macro:

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

To get the parent node, one uses that macro which ands off the lower two bits.