Ticket spinlockメモ φ(.. )メモシテオコウ

Linuxカーネルのspinlockがどんなロジックで動いているのかなと思ってarch/x86/include/asm/spinlock.hを見ていたらTicket spinlockというのが出てきたのでメモ〆(.. )カリカリッ!!

概要は英語のWikipediaで見つけました。
これによるとTicket spinlockは2個の整数の変数を使い、1つはqueueチケット、もう一つはdequeueチケットと呼びます。初期値は両方とも0です。
処理の流れとしては下のようになります。
1.queueの値を読みインクリメントする
2.インクリメント前のqueueの値とdequeueと比較し、queue == dequeueなら誰もロックを確保していないのでロック確保に成功
3.ロックの確保に失敗した場合はqueue == dequeueになるまでスピンして待つ
4.クリティカルセクションを抜ける時にdequeueの値をインクリメントする

上記の流れをスレッドA、スレッドB、スレッドCが行うと大体こんな感じでしょうか。

1.スレッドAがqueueの取得とインクリメントし、queue == dequeueをチェック
→ 0 == 0なのでロック確保成功
2.スレッドBがqueueの取得とインクリメントし、queue == dequeueをチェック
→ 1 == 0なのでロック確保失敗
3.スレッドCがqueueの取得とインクリメントし、queue == dequeueをチェック
→ 2 == 0なのでロック確保失敗
4.スレッドAがクリティカルセクションを抜ける時にdequeueをインクリメント
→ dequeue=1になる
5.スレッドCがqueue == dequeueをチェック
→ 2 == 1なのでロック確保失敗
6.スレッドBがqueue == dequeueをチェック
→ 1 == 1なのでロック確保成功
7.スレッドCがqueue == dequeueをチェック
→ 2 == 1なのでロック確保失敗
8.スレッドBがクリティカルセクションを抜ける時にdequeueをインクリメント
→ dequeue=2になる
9.スレッドCがqueue == dequeueをチェック
→ 2 == 2なのでロック確保成功
10.スレッドCがクリティカルセクションを抜ける時にdequeueをインクリメント
→ dequeue=3になる
11.スレッドDがqueueの取得とインクリメントし、queue == dequeueをチェック
→ 3 == 3なのでロック確保成功

Wikipediaの記事で公平と言っているのはロックの確保は先着順で行われることになるので、優先度の低いプロセスが優先度の高いプロセス達にロックの取得で負けつづけることもないということかな。

さて、このTicket spinlockをLinuxカーネルで見てみましょう。arch/x86/include/asm/spinlock.hにて__ticket_spin_lock()が定義されています。

  37/*
  38 * Ticket locks are conceptually two parts, one indicating the current head of
  39 * the queue, and the other indicating the current tail. The lock is acquired
  40 * by atomically noting the tail and incrementing it by one (thus adding
  41 * ourself to the queue and noting our position), then waiting until the head
  42 * becomes equal to the the initial value of the tail.
  43 *
  44 * We use an xadd covering *both* parts of the lock, to increment the tail and
  45 * also load the position of the head, which takes care of memory ordering
  46 * issues and should be optimal for the uncontended case. Note the tail must be
  47 * in the high part, because a wide xadd increment of the low part would carry
  48 * up and contaminate the high part.
  49 */
  50static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
  51{
  52        register struct __raw_tickets inc = { .tail = 1 };
  53
  54        inc = xadd(&lock->tickets, inc);
  55
  56        for (;;) {
  57                if (inc.head == inc.tail)
  58                        break;
  59                cpu_relax();
  60                inc.head = ACCESS_ONCE(lock->tickets.head);
  61        }
  62        barrier();              /* make sure nothing creeps before the lock is taken */
  63}

Linuxの場合、チケットはqueueに該当するのがtail、dequeueはheadですかね。

queueを読んでインクリメントするのが54行目のxaddでこれはqueueの値をインクリメントし、インクリメント前のqueueの値を返します。と言っても返ってくるのは__raw_tickets構造体ですが。
そして、forループの最初でqueue == dequeueかチェックして、ロックの確保ができたらループを抜けます。

arch/x86/include/asm/spinlock_types.hはこのような構造体になってます。

  20typedef struct arch_spinlock {
  21        union {
  22                __ticketpair_t head_tail;
  23                struct __raw_tickets {
  24                        __ticket_t head, tail;
  25                } tickets;
  26        };
  27} arch_spinlock_t;

cpu_relax()はarch/x86/include/asm/processor.hにありますが、まあ予想通りですね。

 657/* REP NOP (PAUSE) is a good thing to insert into busy-wait loops. */
 658static inline void rep_nop(void)
 659{
 660        asm volatile("rep; nop" ::: "memory");
 661}
 662
 663static inline void cpu_relax(void)
 664{
 665        rep_nop();
 666}
 667

ロックを解放するときは __ticket_spin_unlock()です。

  79static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
  80{
  81        __add(&lock->tickets.head, 1, UNLOCK_LOCK_PREFIX);
  82}

queueに使う変数名の違いとかはありますが、処理としてはWikipediaの説明と同じ感じになります。