C言語で苦しむロックフリー入門（仮

C言語で苦しむロックフリー入門 （仮） 熊崎宏樹

なんか来た • モノ好きにも程ってもんが…

C言語 • CPUの息遣いを感じられる良い言語 • ロックフリーなプログラムを書くには避けては通れな いsafe mamory reclamation問題に一番ダイレクトに 衝突する言語 • スペースの都合上、スライド上のコードはグローバ ル変数モリモリだけど真似しちゃダメ • メモリ確保も絶対成功する前提で書いてるけど真似 しちゃダメ • ほんとはキャストが必要な部分もスペースの都合で 省略

Stackについて • 最初に入れた物が最後に出てくるデータ構造 • 積み重ねるようなデータの持ち方をするから Stackと呼ばれる • 今回話すstackがサポートするメソッドはpush() とpop()のみとする

Stackについて • void push(int x): x を上に積む。関数は何も返 さない物とする。 • int pop(): 最後に積んだ値を取ってくる。 push(1); push(2); push(3); int x = pop(); // => x=3 int y = pop(); // => y=2 int z = pop(); // => z=1

C言語での実装 •構造体定義 •線形リストでスタック構造を表現 typedef struct node{ int data; node* next; } node_t; node_t *head = NULL;

C言語での実装 void push(int x) { // 初期化して node_t *new_node = (node_t*)malloc(sizeof(node_t)); new_node->data = x; new_node->next = head; //挿入 head = new_node; }

C言語での実装 int pop() { // 獲得して node_t *got_node = head; node_t *next_head = got_node->next; int value = got_node->data; free(got_node); // 解放して return value; // 返却 }

並行処理実装 • 近年CPUコアは(中略)マルチスレッド(後略) void* work(void*) { for (int i = 0; i < 100; ++i) { push(i); } } int main(void) { pthread_t t1, t2; pthread_create(&t1, NULL, work, NULL); pthread_create(&t2, NULL, work, NULL); pthread_join(&t1); pthread_join(&t2); }

C言語での並行push実装 void push(int x) { pthread_mutex_lock(&stack_lock); node_t *new_node = (node_t*)malloc(sizeof(node_t)); new_node->data = x; new_node->next = head; //挿入 head = new_node; pthread_mutex_unlock(&stack_lock); }

C言語での並行pop実装 int pop() { pthread_mutex_lock(&stack_lock); node_t *got_node = head; node_t *next_head = got_node->next; int value = got_node->data; free(got_node); // 解放して pthread_mutex_unlock(&stack_lock); return value; // 返却 }

ちょろい！

Mutexでだいたい良い • ぶっちゃけStackでなら一番パフォーマンスが 出る並行処理実装

Mutexなしでできるのでは？

Mutexなしでできるのでは？ • Compare And Swap命令を使えばできる！

Compare And Swap • 指定したアドレスxが指定した値yだったら新しい値z で書き換えるまでを不可分に行えるCPU命令 int CAS(void** x, void* y, void* z) { if (*x == y) { **x = *z; return 1; } else { return 0; } }

CASスピン • CASを使って成功するまで無限ループする コードを書けばロックが要らない！

CASの使い方例 int x = 0; void add_unsafe() { ++x; } int x = 0; void add_cas() { for (;;) { // spin int old_x = x; if (CAS(&x, old_x, x+1)) { break; } } }

Lockを用いないとどうなるか • 複数スレッドが同時に行うと x==1 スレッドA スレッドB 1.xを読み出す(1) 1.xを読み出す(2) 2.読んだ値に +1 2.読んだ値に +1 3.xを保存する(1) 3.xを保存する(3) OK! x==3

Lockを用いないとどうなるか • 複数スレッドが同時に行うと破綻する場合がある x==1 スレッドA スレッドB 1.xを読み出す(1) 1.xを読み出す(1) 2.読んだ値に +1 2.読んだ値に +1 3.xを保存する(2) 3.xを保存する(2) 数が合わない x==2

CASを使ってみよう • CASのお陰で衝突しても破綻しない x==1 スレッドA スレッドB 1. xを読み出す(1) 2. 読んだ値に +1 3. 値が1なら2へCAS 4. 失敗したので再挑戦 5. xを読み出す(2) 6. 読んだ値に +1 7. 値が2なら3へCAS 1. xを読み出す(1) 2. 読んだ値に +1 3. 値が1なら2へCAS 数が合う！ x==3

Lock-free Stack push
void lock_free_push(int x) {
node_t *new_node =
(node_t*)malloc(sizeof(node_t));
new_node->data = x;
do {
node_t *old_head = head;
new_node->next = head;
} while (!CAS(&head, old_head, new_node));
}

Lock-free Stack Push • CASによってリトライができるので衝突もセーフ

Lock-free Stack ↓ポインタ A Head CAS 「Headが指している物を指したノードを作ってCAS」

Lock-free Stack A B C CAS CAS CAS Head D 失敗した！

Lock-free Stack A B また失敗した！ C CAS Head CAS D

Lock-free Stack A Head CAS C B D

Lock-free Stack pop int lock_free_pop() { node_t *old_head; for (;;) { old_head = head; node_t *next_head = old_head->next; if (CAS(&head, old_head, new_head)) { int data = old_head->data; free(old_head); return data; } } }

Lock-free Stackからpop A Head CAS C D B

Lock-free Stack ABA problem • CASは「値が一致した場合に成功する」事まで しか確認しない。運悪く一致してしまった場合 に事故る。

Lock-free StackのABA D HeadがAを指してた HeadをAからBに書 からBに書き換えれ き換えるぞー！ るぞー！やったー！ うおおおおおー Head C push(x)しよっと もう1回pop()しよっと Aをpop()しよっと メモリはAでいいや B A

よく言われる解決策 • Tagを付ければ解決するよ[1] • LL/SCを使ってもいいね[1] – LL/SCはx86系CPUでは使えない • Double WordのCASを使って、2word目をカウ ンタに使うとカウンタに充分なビット数が割け るので安心 – そもそも2wordのatomicなreadが無いじゃん。 でもpushとpopの両方で増やしたら大丈夫になっ たわ[2] [1]2004 Maged M. Michaelら ABA Prevention Using Single-Word Instructions1 [2]The difficulty of lock-free programming: a bug in lockfree stack

• http://mdf356.blogspot.jp/2015/06/the-difficulty-of-lock-free-programming.html

Lock-free StackのABA D HeadがAを指してた HeadをAからBに書 けどTag値が1じゃな き換えるぞー！ くて4だからやり直し うおおおおおー Head1 Head4 Head3 Head2 C push(x)しよっと もう1回pop()しよっと Aをpop()しよっと メモリはAでいいや B A 大丈夫ぽい！？

大丈夫じゃねーよ！！！

Lock-free Stack pop • TagによるABA避けをした実装 int lock_free_pop() { node_t *old_head; for (;;) { old_head = head; node_t *next_head = old_head->next; if (CAS(&head, old_head, new_head)) { int data = old_head->data; free(old_head); return data; } } } OSへ返却 D head C B A 返却したメモリ->next; を読む！ int lock_free_pop() { node_t *old_head; for (;;) { old_head = head; node_t *next_head = old_head->next; if (CAS(&head, old_head, new_head)) { int data = old_head->data; free(old_head); return data; } } }

そもそも別の解決策しかない • メモリを適当なタイミングでfree()するのは事故の もと – そもそもpop()だけをlockで守る解決策もある • この問題はガベージコレクションでのある言語で は発生しない – 全てのスレッドが参照しなくなってからfree()されるか ら • よし！同一の状況をCでも再現しよう – 参照カウンタ？ • 参照時のカウンタ更新コストで死ぬ

解決策: Hazard Pointer
node_t *h_ptr[THREADS];
int lock_free_pop() {
for (;;) {
hzd_ptr[tid] = head;
if (head != h_ptr[tid]) continue;
node_t *next_head =
h_ptr[tid]->next;
if (CAS(&head, h_ptr[tid], new_head)){
int data = h_ptr[tid]->data;
for (int i=0; i<THREADS; ++i)
free(old_head);
return data;
}
}
}

解決策：RCU • Read-Copy-Updateの略でRCU • カーネル空間内で、参照頻度の割に更新頻 度が極端に低いデータをロックなしで保護す る為に使っているアルゴリズム • 書き換え側のコストがすごい事になったりす るが実用上の問題はない

RCU Lock-free Stack push • rcu_read_lockによって rcuクリティカルセクショ ンを記述する – そのセクション内のス レッドはプリエンプショ ンされない int lock_free_pop() { node_t *old_head; for (;;) { rcu_read_lock(); old_head = head; node_t *next_head = old_head->next; if (CAS(&head, old_head, new_head)) { int data = old_head->data; rcu_read_unlock(); synchronize_rcu(); free(old_head); return data; } } }

RCU Lock-free Stack pop • RCUでメモリ解放を遅延 int lock_free_pop() { node_t *old_head; for (;;) { rcu_read_lock(); old_head = head; node_t *next_head = old_head->next; if (CAS(&head, old_head, new_head)) { int data = old_head->data; rcu_read_unlock(); synchronize_rcu(); free(old_head); return data; } } } 他の全てのス レッドが抜けるの を待つ D C B A 解放されないので安心！ head int lock_free_pop() { node_t *old_head; for (;;) { rcu_read_lock(); old_head = head; node_t *next_head = old_head->next; if (CAS(&head, old_head, new_head)) { int data = old_head->data; rcu_read_unlock(); synchronize_rcu(); free(old_head); return data; } } }

RCU: Grace Period • rcuクリティカルセクション内ではプリエンプショ ンしなくなる – 実を言うとプリエンプションしても良い版の実装も存 在するが詳細はまだ追ってない • synchronize_rcuで他のスレッドが最低1回ずつ プリエンプションするのを待つ – 古いheadを観測して走ってるスレッドを邪魔しない

RCU: Grace Period • プリエンプションを禁じるような操作をユーザ 空間で気軽に使われると危険が危ない – そもそもユーザに使わせるべきではない • つまりカーネル空間ならではの解決法であり、 ユーザ空間では別の方法が必要