netbsd currentのmutex lockについて(その2)
[adaptive lockについて]
mutex_vector_enter()の後半はadaptive lockである。
apaptive lockの処理を簡単にまとめる。
ロックが獲得できるまでループを行う。ループの中の処理はおおまかに分けて以下の処理となる。
処理1.mutexにまだ持ち主が居ない場合の処理
if (!MUTEX_OWNED(owner)) { /* * Mutex owner clear could mean two things: * * * The mutex has been released. * * The owner field hasn't been set yet. * * Try to acquire it again. If that fails, * we'll just loop again. */ if (MUTEX_ACQUIRE(mtx, curthread)) break; owner = mtx->mtx_owner; continue; }
まずmutex所持スレッドがいないか調べる。
mutex処理スレッドがいないケースではコメントのとおり以下の事象が考えられる。
o mutexがすでに解放された。
o mutex_ownerのowner bitにまだロック獲得スレッドのアドレスをセットしていない
もしmutex獲得スレッドがいないのならmutexのロック取得を試みる。
(MPな場合、先のMUTEX_OWNEDからMUTEX_ACQUIREの間に他のプロセッサにMUTEX_ACQUIREされmutexがとられる可能性があるため)
if (MUTEX_ACQUIRE(mtx, curthread))
mutexが獲得できたらループを抜ける。そうでない場合、現時点でのmutex所有スレッドを記録したうえで再度mutexのとりなおしを再度試みる。
なお、MUTEX_ACQUIREの実装は以下[MUTEX_ACQUIRE実装]で述べる。
[MUTEX_ACQUIRE実装]
static inline int MUTEX_ACQUIRE(kmutex_t *mtx, uintptr_t curthread) { int rv; uintptr_t old = 0; uintptr_t new = curthread; MUTEX_INHERITDEBUG(old, mtx->mtx_owner); MUTEX_INHERITDEBUG(new, old); rv = MUTEX_CAS(&mtx->mtx_owner, old, new); MUTEX_RECEIVE(mtx); return rv; }
MUTEX_INHERITDEBUGはマクロ第二引数のowner変数に存在するlock debug bitのみを引き継がせるマクロである。つまり、lock debug bitのコピーを行うということである。
ここで、mutex_ownerのビット構成は以下のとおりとなっている。
bit0 ... 該当ロックがSPIN LOCKかどうか bit1 ... WAITER bit.該当mutex取得待ちのスレッドがいるかどうかを指す。 bit2 ... lock debug機能が有効かどうか bit3 ... 特に用途なし。 bit4 - bit31 owner(ロック所有スレッド構造体のアドレスのbit4 - bit31)
MUTEX_CASの「CAS」は「compare and swap」の略である。
これは、メモリアドレス、古い値、新しい値の3つを使う。もし、メモリアドレスに保存したある値が、指定された古い値ならば、それを新しい値に置き換え、そうでない場合は、何もしない。そして、この処理が成功したかどうかをプログラムに返す。CPUはこれをアトミックに実装する必要がある。 (http://ja.wikipedia.org/wiki/Lock-free%E3%81%A8Wait-free%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A00)
う〜ん、x86の場合だとMUTEX_CASの実体はatomic_cas_ulong()なのだが、実体が見つからない....。
netbsd manを調べ、MUTEX_CASの役割は上記のCAS定義のとおりで正しいことを確認した。
MUTEX_RECEIVEはメモリバリアで、例えばx86の場合はmembar_consumer()。x86の場合、membar_consumerも実体がみつからない。
要するにメモリに置かれたownerが未だ0(デバッグビットを考慮しない場合)なら、まだロックを確保していないということだから、ロック取得に成功したことになる。
処理2.adaptiveだが、特別にSPINで待つケースかを判定
if (mutex_onproc(owner, &ci)) { LOCKSTAT_START_TIMER(lsflag, spintime); count = SPINLOCK_BACKOFF_MIN; for (;;) { SPINLOCK_BACKOFF(count); owner = mtx->mtx_owner; if (!mutex_onproc(owner, &ci)) break; } LOCKSTAT_STOP_TIMER(lsflag, spintime); LOCKSTAT_COUNT(spincnt, 1); if (!MUTEX_OWNED(owner)) continue; }
MPな環境の場合、いずれかのプロセッサでmutex所持スレッドが動作中(onproc)か調べる。
動作中なら、adaptiveにも関わらずSPINする。理由は「動作中なら、ownerがmutexをすぐに解放すると推定できるから」である。
ただし、SPINしている最中にもmutex所持スレッドが実行中かを調べ、もし実行中でなくなった場合SPINを中断する。
また、SPINのループから抜けた時点でmutex所持スレッドが変わっている場合はmutex取得処理をやり直す。
処理3.turnstileの有無を調査
ts = turnstile_lookup(mtx);
次に確保しようとしているmutex lockに対応したturnstileを検索する。
turnstileとは、優先度継承に必要なデータ構造である。詳細は次回述べる。
処理4.Waiter Bitをたて、mutexの解放を待っているスレッドがいることを記録する。
/* * Once we have the turnstile chain interlock, mark the * mutex has having waiters. If that fails, spin again: * chances are that the mutex has been released. */ if (!MUTEX_SET_WAITERS(mtx, owner)) { turnstile_exit(mtx); owner = mtx->mtx_owner; continue; }
ここでWcurlwpの変化がこのCPUから見えるようになる前に。aiter Bitをたてる。要は、対象となるロックの解放を待っているスレッドが居る旨を記録することである。
waiter bitをたてることに失敗した場合、再度adaptive lockの取得をやり直す。
処理5.MPな環境での注意点。
if ((membar_consumer(), mutex_onproc(owner, &ci)) || (membar_consumer(), !MUTEX_HAS_WAITERS(mtx))) { turnstile_exit(mtx); owner = mtx->mtx_owner; continue; }
(ソース引用部にはコメントを載せていない)
また、このあと.....うわコメント長い。
訳は全訳を見てほしいが、要するに「Waiter Bit」をたてた直後に別のCPUで動いているスレッドがmutex_exit()を呼び出すことでWaiter Bitをクリアしてしまい、結果として「Waiter Bitをたてたつもりが知らないところでクリアされていた」問題への対処である。
[コメント全訳] mutex_exit()はinterlockingな命令なしにmutexを解放できる。その結果、以下の事象が起こり得る。(訳注:「以下の事象」とはMUTEX_SET_WAITERS()でwaiter bitをたてた直後に別のCPUからmutex_exit()によってwaiter bitが落とされることを指す。) (先に説明した競合とは別に)もう一つ起こり得る競合がある。(上記の状態で)第三のCPUがmutex解放直後にmutexを取得する可能性である。adaptive mutexは最初にspin mutexを行うため、これはそんなに心配する必要がない。必要なことはWaiter Bitのセットを保証することである。 ロックなしに解放ができるように、ここでいくつかの仮定をおく必要がある。 (訳注：通し番号は訳者が付与した) (1)mutexの解放は単なるアトミックでない/ロックしていない操作で行うことができる。(あるひとつのCPU上では依然atomicでなければいけない,例えば割り込まれる場合やプリエンプトされる場合である。) (2)所与の時間において、MUTEX_SET_WAITERSがシステム中1つのCPUのみで実行中であること。これはturnstile chain lockによって保証される。 (3)MUTEX_SET_WAITERS()とロックの解放処理のみが非ゼロなowner field（訳注：既にmutexが誰かに獲得された状態のmutex_owner)を変更できること。 (4)MUTEX_SET_WAITERSが成功した結果が中間バッファに反映されない(実メモリに反映され),そしてシステム内の他の全てのCPUからすぐにその反映が見えること (5)mutexを保持しているlwpがスイッチングされた場合、curlwpが変わる前にwriteのメモリバリア(store fence)を発行する。curlwpの変化がこのCPUから見えるようになる前に、mutex_exit()によるWaiter Bitのいかなる上書きも完了することを保証する。 (6)curlwpをセットする前に、そしてlwpの再開をする前に、mi_switch()はwriteのメモリバリア(store fence)を発行する。 (7)curcpu()->ci_biglock_wantedを設定する前に、そしてそれをクリアする前に、_kernel_lock()はwriteのメモリバリアを発行する。 このことにより、ci_biglock_wantedの変更が見えるようになる前に、mutex_exit()によるWaiters Bitのいかなる上書きも完了する事を保証する。 (Waiters bitのフィールドをセットした後の時点となる今、)read のメモリバリアを発行し、mutex所持スレッドの状態を再度チェックする。 いくつかの想定できる結果は以下のとおり。(以下は考えられる結果の全てではない) 1.onprocかどうかのチェックがtrueの場合。mutexを所持しているスレッドが再度動作している。ロックはすぐに解放されるかもしれないのでspinで待たないといけない。重要なのはwaiters flagの値を信用できないということである。 2.onprocかどうかのチェックがfalseの場合。mutexを所持しているスレッドは動作していない。MUTEX_SET_WAITERS()によって行われた変更をmutex_exit()がblatしたかどうかのチェックをする機会を持っていることになる。 3.onprocかどうかのチェックがfalseの場合。mutexを所持しているスレッドは動作しているかしていない。チェックの最中のいずれかのポイントでコンテキストスイッチングされた。再度我々はWaiters Bitがまだセットされて居るか、もしくは上書きされたかを調べる機会がある。 4.onprocかどうかのチェックがfalseの場合。mutexを所持しているスレッドはいずれかのCPU上で動作しているが、big lockを欲しがっている。この場合はwaiters fieldのチェックをすればよい。 5.waiter bitのチェックが失敗。mutexが解放されてwaiter bitがクリアされ、他のlwpがロックを所持している。 6.waiter bitのチェックが失敗。mutexが解放された。 もしwaiters bitがセットされていない場合、sleepするのは安全ではない。 決して目覚めることがないかもしれないためである。
処理6.ブロックし、mutexの空きを待つ。
turnstile_block(ts, TS_WRITER_Q, mtx, &mutex_syncobj);
turnstile_block()でmutexの解放を待つ。
そして、ブロック終了後、再度mutexのownerを取得してループの先頭に戻る。
