赤黒木 linux kernel における実装

https://ietoa.blogspot.jp/2017/05/blog-post.html において、赤黒木の理論上の話を書いたが linux kernel の実装においてはどのようになっているか書き留める。

 linux kernel において、プロセスに割り当てるメモリ空間は用途ごとに分けられ、それぞれが　vm_area_struct 構造体で表される。
 vm_area_struct は主に unsigned long vm_start、unsigned long vm_end といった、メモリアドレスの区間を表す値を持っている。
 linux では一つのプロセスにおける vm_area_struct の個数が多い場合を想定し、 vm_start の値による赤黒木で vm_area_struct の集合を取り扱うことにしている。
 赤黒木の linux におけるノード表現 linux では以下の構造体で node を表している。 [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)))); 
rb_right, rb_left で右、左の子ノードを表し、__rb_parent_color で親ノードとそのノードの色を表している。
少し、トリッキーだが rb_node は 4 byte 以上の境界に並べられることを想定しており、アドレスの下位の 2 bit は 0 となることを想定してる。
そこで最下位 bit に対して黒、赤を表す 1 bit を埋め込む実装となっている。
 ここで rb_node は値に対する情報を持っていないことを不自然に思うだろう。 ここで linux ではちょっとトリッキーな手法を用いている。 値の情報をもつ vm_area_struct が rb_node をメンバーとしてもつという構造をしている。
しかしこれだと rb_node から、その rb_node をもつ vm_area_struct をどのように参照するのか？ 答えは container_of マクロを使い、オフセットの差し引きを計算することで求めるという手法が取られている。
具体的には http://qiita.com/satoru_takeuchi/items/3769a644f7113f2c8040 が詳しい。 linux ではこのようにして、値の実装と赤黒木の実装を分離している。
次回では赤黒木の挿入、削除の実装について書く。 高速化のためか、以前に説明した場合分けと異なっており説明を要するためである。