userspace RCU(QSBR)の使い方と解説

http://lttng.org/urcu|Userspace RCU
という大変クールなプロジェクトがあります。

「RCU(リードコピーアップデート)をユーザースペースで行うもの」という事で、そこだけ聞くとなんのこっちゃという感じ。

リードコピーアップデートって何よ

リードコピーアップデートそのものの正しい説明はWikipedia*1 でも読んでもらうとして、Wikipediaを読むのすら面倒な人の為に説明すると「みんなで共有してるデータをfree()しても良いタイミングを見極める技術」です。

特定の構造体をみんなで共有して書き換えたりしたいな → Lockとればよくね?
すごく頻繁にアクセスするし読み出しの方が多いからLockはやだな → Read-Write Lockでよくね?
Read-Write LockだとAtomic命令多すぎてパフォーマンスでないな → Lock無くしてデータをポインタで包んで書き換えの時だけ複製して差し替えればよくね?
読んでる最中のデータを他の奴が差し替えた後にこっちが読みかけのを勝手にfree()しやがるからSEGVするな → じゃあfree()の実行を遅延させればSEGVは避けられるんじゃね?

「じゃあ削除を遅延ってどれぐらい遅延させればいいのよ?」
が本題。長い道のりだった。

カーネル空間では古くから問題になっていた物で、その解決策としてRCUというものが使われている。
大雑把に説明すると

  • 大事なデータを読み出してる間にはプリエンプションを禁じる
  • データを削除する際にはそのスレッドをyieldし続けて他のスレッドに自分の載ってるプロセッサを貸し出す。他のスレッド全部が最低1度でも自分のCPUコアに載った事を確認したら消して良し(何故なら大事なデータを読みかけのスレッドはプリエンプションされないので、自分のCPUコアに載ってこない。載ってきたなら読みかけでない証拠)

という物。これは読み出し側に一切のペナルティが無くて素晴らしい。でも、カーネル空間内だからこそプリエンプションを禁じるとかスレッドのマイグレーションを検知するとかが出来るわけで、ユーザー空間で真似できる代物ではない。*2

そこで、アルゴリズムの力でユーザー空間でこれに近いものを実現しようぜってのがUserspace RCU。
個々のアルゴリズムを学ぶとおもしろいんだけど、日本語のドキュメント少なすぎて笑えるので日記に書こうと思った所存。

使ってみる

複数の実装を選べて、性能の特性や挙動が微妙に違うのだけど、目的はどれもおよそ一緒。
今回は僕の好きなQSBRを例に挙げて説明する。QSBRは他のアルゴリズムと比べて、Reader-Sideのパフォーマンスとスケーラビリティに優れる。*3

ロックフリーアルゴリズムではガベージコレクタに頼ったアルゴリズムが多くて、Javaで実装出来たものがCだと普通には実装できないことが多い。
そこでこういう方法でオブジェクトの寿命をちゃんと守ってあげると正しく使えるようになる。

インストール

urcuライブラリのインストールは何の変哲もない./configure && make && sudo make installで終わるので特に書くことはない。

使い方例

#include <urcu-qsbr.h>
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#include <stdint.h>

int** global_array;
int array_length;

void* reader(void*) {
  // 配列内の適当な位置を読んで合計値を算出するだけのスレッド
  int local_sum = 0;
  int i;
  for (i = 0; i < 1000; ++i) {
    rcu_quiescent_state();
    // URCUで保護されているので安心してポインタの中身を参照できる
    local_sum += *global_array[rand() % array_length];
  }

  rcu_thread_offline();  // 処理が終わったので他のスレッドにこのスレッドを無視しろと伝える
  printf("my local sum is %d finish!\n", local_sum);
}

void* writer(void*) {
  // 配列内の適当な位置を適当な値にCASして回るだけのスレッド
  int i;
  for (i = 0; i < 1000; ++i) {
    rcu_quiescent_state();
    int* new_value = (int*)malloc(sizeof(int));
    *new_value = rand() % 100;
    int target = rand() % array_length;
    int* old_value;
    for (;;) {  // CASスピン
       old_value = global_array[target];
       if (__sync_bool_compare_and_swap_8(&global_array[target], (intptr_t)old_value, (intptr_t)new_value)) {
          break;
       }
    }
    synchronize_rcu();  // 他のスレッドのquiescent_stateが経過するのを待つ
    free(old_value);  // RCUが無かったらこの行は危険
  }

  rcu_thread_offline();  // 処理が終了したので他のスレッドにこのスレッドの状態を無視しろと明示
  printf("writer finish\n");
}

void array_init() {
  // int*の配列に適当な値を保持したint*を置いていく
  int i;
  array_length = 100;
  global_array = (int**)malloc(array_length * sizeof(int*));
  for (i = 0; i < array_length; ++i) {
    global_array[i] = (int*)malloc(sizeof(int));
    *global_array[i] = rand() % 100;
  }
}
void array_destroy() {
  // 上記の配列を解放する
  int i;
  for (i = 0; i < array_length; ++i) {
    free(global_array[i]);
  }
  free(global_array);
}

int main(void) {
  const int threads = 10;
  int i;
  pthread_t reader_thread[threads];
  pthread_t writer_thread[threads];

  // 配列初期化
  array_init();

  // スレッドを開始
  for (i = 0; i < threads; ++i) {
    pthread_create(&reader_thread[i], NULL, reader, NULL);
    pthread_create(&writer_thread[i], NULL, writer, NULL);
  }

  // 終わるのを待つ
  for (i = 0; i < threads; ++i) {
    pthread_join(reader_thread[i], NULL);
    pthread_join(writer_thread[i], NULL);
  }

  // 配列破棄
  array_destroy();

  printf("all threads finish\n");
}

実行例

$ gcc qsbr_test.cpp -lurcu-qsbr -lpthread -g
$ valgrind ./a.out
==14076== Memcheck, a memory error detector
==14076== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==14076== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==14076== Command: ./a.out
==14076==
my local sum is 52455 finish!
writer finish
my local sum is 53090 finish!
writer finish
writer finish
my local sum is 53159 finish!
my local sum is 50037 finish!
my local sum is 52187 finish!-
writer finish
writer finish
my local sum is 46717 finish!
my local sum is 45657 finish!
writer finish
writer finish
my local sum is 52845 finish!
writer finish
my local sum is 52102 finish!
writer finish
my local sum is 46073 finish!
writer finish
all threads finish
==14076==
==14076== HEAP SUMMARY:
==14076== in use at exit: 0 bytes in 0 blocks
==14076== total heap usage: 10,121 allocs, 10,121 frees, 47,280 bytes allocated
==14076==
==14076== All heap blocks were freed -- no leaks are possible
==14076==
==14076== For counts of detected and suppressed errors, rerun with: -v
==14076== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

no leaks are possible の文字が燦々と輝いてますね。素晴らしい。

解説

どうやってこんなのを実現してるかというと、スレッドローカルなストレージにカウンタを置くことで解決してます。
QSBR(Quiescent State Based Reclamation)の名前の通り、Quiescent State(=静止状態)の有無を他のスレッドに対して通知できれば良いのです。

適当な実装を書くならこんな感じ。ただし擬似コードなのでコンパイル通らないし、同時に1スレッドしかsynchronize_rcuできないけれどコンセプトを示すには充分です。

int global_counter = 0;
__thread local_counter = 0;

void rcu_quiescent_state() {
  // 他のスレッドに自分が一旦静止状態に入った事を明示
  local_counter = gloabal_counter;
}

void synchronize_rcu() {
  int old_counter = global_counter;
  ++gloabal_counter;  // ここでカウンタの値を増やす(※)
  local_counter = global_counter;
  for (他のスレッドのそれぞれのlocal_counterを見て回る) {
    if (個々のlocal_counter <= old_counter) {
      continue;  // まだ仕事中らしいのでquiescent_stateを待つ
    }
  }
  // ここに至ったという事は全てのlocal_counterは上の※で増やしたカウンタを観測した。
  // つまり自分がsynchronize_rcuを呼んでから、他のスレッドが最低1回はrcu_quiescent_state()を呼び出した事を意味する
  // つまり1回でも静止状態に入ったので自分以外に到達不能になったデータは消して良いことがわかった。
}

簡単ですね。
他のスレッドから特定のデータを到達不能にした後、到達不能なスレッドがそのアドレスに触らない事を保証できるようになるのを待つわけです。
この待ち期間を猶予期間(grace period)と呼びます。


他のスレッドが最低1回でもQuiescent Stateを宣言するのを待ちます。

厳密にはこれを使うとアルゴリズムはlock-freeではなくなるのですが、実用上充分な速度とスケーラビリティが出ます。
readが多数を占める処理の場合、rcu_quiescent_stateはキャッシュラインがSharedステートに落ちたglobal_counterを読み続ける事になるのでL1キャッシュに当たり続ける事が期待されます。
May god lock-free you!

*1:http://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC%E3%83%89%E3%83%BB%E3%82%B3%E3%83%94%E3%83%BC%E3%83%BB%E3%82%A2%E3%83%83%E3%83%97%E3%83%87%E3%83%BC%E3%83%88

*2:プリエンプション禁止なんて物騒な物をほいほいとユーザー空間で使えるようにしちゃったら誤用・悪用された時のダメージ半端ない。

*3:僕の読んだことのある実装例では、読み出し側のオーバーヘッドはメモリ読み書き一回ずつとメモリバリア1回で済んでる。しかも書き換えが起こって無ければキャッシュラインすら汚さない優れもの。