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

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) { node_t *new_node = (node_t*)malloc(sizeof(node_t)); new_node->data = x; new_node->next = head; pthread_mutex_lock(&stack_lock); head = new_node; pthread_mutex_unlock(&stack_lock); }

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

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

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を使って成功するまで無限ループするコードを書けばロックが要らない！

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

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

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

CASを使ってみよう CASのお陰で衝突しても破綻しない xを読み出す(1) xを読み出す(1) 読んだ値に +1 値が1なら2へCAS スレッドB xを読み出す(1) 読んだ値に +1 値が1なら2へCAS 失敗したので再挑戦 xを読み出す(2) 値が2なら3へCAS xを読み出す(1) 読んだ値に +1 値が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 CAS CAS CAS A Head B C D Ｆｆ 失敗した！ 失敗した！

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

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 CAS C D B

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

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

SEGV

よく言われる解決策 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

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

だが SEGV

Lock-free Stack pop TagによるABA避けをした実装 返却したメモリ->next; を読む！ D C B A 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; } 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; } D head C OSへ返却 B A 返却したメモリ->next; を読む！

SEGV

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

解決策: Hazard Pointer free前に他のスレッドがそれを使ったら待機する どこのポインタが捨てられたら困るかを共有する 固定長のグローバルな配列を用意する 1スレッドが1要素使う free前に他のスレッドがそれを使ったら待機する volatile node_t *h_ptr[THREADS]; // global int lock_free_pop() { for (;;) { h_ptr[tid] = head; memory_fence(); 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;) if (tid == i) {++i; continue} else if (h_ptr[i] != h_ptr[tid]) ++i; else sched_yield(); free(h_ptr[tid]); return data; }

Hazard pointer Lock-free Stack pop volatile node_t *h_ptr[THREADS]; // global int lock_free_pop() { for (;;) { h_ptr[tid] = head; memory_fence(); 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;) if (tid == i) {++i; continue} else if (h_ptr[i] != h_ptr[tid]) ++i; else sched_yield(); free(h_ptr[tid]); return data; } volatile node_t *h_ptr[THREADS]; // global int lock_free_pop() { for (;;) { h_ptr[tid] = head; memory_fence(); 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;) if (tid == i) {++i; continue} else if (h_ptr[i] != h_ptr[tid]) ++i; else sched_yield(); free(h_ptr[tid]); return data; } D head C B 解放されないので安心 A 他の全てのスレッドが抜けるのを待つ

patented US 20040107227 2010年に放棄されたとwikipediaにはあるが…

解決策：Pass the buck 和訳するなら「なすりつけ法」 hazard pointerのようにglobalなhazard_ptr配列を最初に定義するとエントリ数の需要の動的な増減に耐えられない 利用する時だけhazard_ptr配列のどこを自分のスレッドが使ってよいかをCASで取り合う技法 patented: US7194495 B2 status: 認定 と書いてあるので確実に危険

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

RCU Lock-free Stack push rcu_read_lockによってrcuクリティカルセクションを記述する そのセクション内のスレッドはプリエンプションされない 余計な共有メモリを必要としないしread側の負荷はかなり小さい 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 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; } 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 head 他の全てのスレッドが抜けるのを待つ C B A 解放されないので安心！

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

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

解決策: Quiescent-State-Based-Reclamation グローバルなカウントを増やして、それをみんなが観測した後ならfreeしてOK read側はglobal_countを読むだけ 更新が無ければキャッシュラインがSステートに落ちるので最速 write時は更新したglobal_counterが他の全スレッドに読まれるまで待機する uint64_t global_count = 0; uint64_t local_count[THREADS] = {0}; int lock_free_pop() { node_t *old_head; for (;;) { local_count[TID] = global_count; old_head = head; node_t *next_head = old_head->next; if (CAS(&head, old_head, new_head)) { int data = old_head->data; local_count[TID] = add_and_fetch(global_count); for (int i=0; i < THREADS;) if (local_count[TID] <= local_count[i]) ++i; // 読まれた場合だけiが進む free(old_head); return data; }

速い！ 参照するメモリ数nに対してO(1)のメモリフェンスで済む Making Lockless　Synchronization Fast:　Performance Implications of　Memory Reclamation

解決策: Quiescent-State-Based-Reclamatfion 利点: 特許は取られてなさげ read側は高速 欠点: すべてのスレッドが定期的にglobal_countを読む前提がある 状況によっては結構大規模な改修になる read側のクリティカルセクションがネストした場合、外側のセクションは保護対象外になってしまう ネスト版のEpoch Based Reclamationもあるけど今回は時間の都合で話せない

まとめ とても簡単なLock-free StackひとつとってもC言語上でスレッドセーフにするのは非常に大変 デバッグの難しさ 特許の罠 可変スレッド数対応 メモリバリア厳しい Mutex使え