この記事ははてなエンジニア Advent Calendar 2023 の27日目の記事です。はてなのアドベントカレンダーはまだまだ続きます!
26日目の記事は 
id:masayosu さんの EKS Pod Identity を活用するメリットでした。
赤黒木とは
赤黒木は平衡二分探索木の１種で、各ノードが赤か黒の色に塗り分けられていることが特徴の１つです。
(Wikipedia の赤黒木のページの画像)
この記事では赤黒木に詳しい必要はないので、説明は wikipedia の赤黒木のページに任せます。
Linux カーネルでは、CFS スケジューラで用いられたりしています。
Linux の赤黒木のノード
Linux カーネルの赤黒木の実装を見ていきます。この記事では特に赤黒木のノードに注目します。
include/linux/rbtree_types.h (v6.6) にある rb_node が赤黒木のノードを表す構造体です。
struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); /* The alignment might seem pointless, but allegedly CRIS needs it */
まず、rb_node 構造体は３つのフィールドを持っています。
__rb_parent_color- 木の親と自身の色 (赤か黒) の情報
- 下記で詳しく見ていきます。
*rb_right- 右側の子ノードへのポインタ
*rb_left- 右側の子ノードへのポインタ
次に、 __attribute__((aligned(sizeof(long)))) という部分はコンパイラにアライメント境界を伝えるキーワードです。
下記で詳しく見ていきます。
コミットログを追う
コミットログを読んで rb_node 構造体の理解を深めます。
v6.6 では rb_node 構造体は include/linux/rbtree_types.h に定義されていますが、v5.15 まで include/linux/rbtree.h ファイルに定義されていました1。
なので、include/linux/rbtree.h の Git のコミットログを追います。
v2.6.12-rc2
Linux カーネルのソースコードが Git で管理されるのは v2.6.12-rc2 からです。
そこで v2.6.12-rc2 から見ていきます。
include/linux/rbtree.h (v2.6.12-rc2)
struct rb_node { struct rb_node *rb_parent; int rb_color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; };
v6.6 と大きく異なるのは、v2.6.12-rc2 の時点では __rb_parent_color フィールドは存在せず、 *rb_parent と rb_color にフィールドが別れている点です。
v2.6.18
v2.6.18 で v6.6 とほとんど同じコードになります。
include/linux/rbtree.h (v2.6.18)
struct rb_node { unsigned long rb_parent_color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); /* The alignment might seem pointless, but allegedly CRIS needs it */
赤黒木に関するコミットはいくつかありますが、その中でも２つのコミットを見てみます。
[RBTREE] Merge colour and parent fields of struct rb_node.
We only used a single bit for colour information, so having a whole machine word of space allocated for it was a bit wasteful. Instead, store it in the lowest bit of the 'parent' pointer, since that was always going to be aligned anyway.
このコミットで *rb_parent と rb_color が rb_parent_colour というフィールドにまとまります。
struct rb_node { - struct rb_node *rb_parent; - int rb_color; + unsigned long rb_parent_colour; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; };
親へのポインタ ( *rb_parent ) の最下位1ビット (LSB) に色情報 ( rb_color ) を格納することでメモリの無駄遣いを防ぐことができるということがコミットメッセージに書いてあります。
なぜ、ポインタの LSB に色情報を格納できるのでしょうか。
それは、親へのポインタは偶数アドレスに配置されるので、LSB は必ず0になるからです。ポインタが偶数アドレスになる理由は、rb_node 構造体がアライメントされてメモリに配置されるからです。
このようなポインタの使い方を Tagged pointer と呼ぶらしいです。
ちなみに、colour というのは typo ではなくイギリス英語のスペルです。v2.6.18 のリリースまでにアメリカ英語の color に変更されました2。
[RBTREE] Add explicit alignment to sizeof(long) for struct rb_node.
Seems like a strange requirement, but allegedly it was necessary for struct address_space on CRIS, because it otherwise ended up being only byte-aligned. It's harmless enough, and easier to just do it than to prove it isn't necessary... although I really ought to dig out my etrax board and test it some time.
__attribute__ というコンパイラにアライメント境界を伝えるキーワードが追加されます。
+} __attribute__((aligned(sizeof(long)))); + /* The alignment might seem pointless, but allegedly CRIS needs it */
通常、コンパイラはこのコードが無くてもアライメントするはずですが、 CRIS ではそれがうまくいかないらしいということがコミットメッセージでわかります。
__attribute__ は GCC の構文3で、構造体と共用体に属性を付与できます。aligned は属性の１つで、アラインメントの境界を指定できます。64ビットアーキテクチャでは long 型は8バイトなので、8バイトアライメントされるはずです。
CRIS というのは Axis Communications 社の開発しているアーキテクチャのことだと思います4。
まとめ
Linux カーネルの赤黒木の実装に見る Tagged Pointer を用いた最適化の話でした。
この記事ははてなエンジニア Advent Calendar 2023 の27日目の記事でした。
明日の記事は 
id:SlashNephy さんです。
