📚

Compare and Swap によるスピンロック実装

2021/09/24に公開

aarch64 の CAS（Compare and Swap）命令を使ったスピンロックの実装について紹介します。
Zircon のスピンロック実装（aarch64 編）の番外編となります。

CASA

Compare and Swap word or doubleword in memory は、32 ビットのワードや 64 ビットのダブルワードをメモリから読み出し、第 1 レジスタに保持されている値と比較します。
比較結果が等しければ，第 2 レジスタの値がメモリに書き込まれます。書き込みが行われた場合、読み出しと書き込みはアトミックに行われ、読み出しと書き込みの間にメモリ位置の他の変更が行われることはありません。

CASA と CASAL は、Acquire のセマンティクスでメモリからロードします。

（中略）
このアーキテクチャでは、比較が失敗しても、データの読み取りによってその場所に関連する排他的モニターがクリアされます。

— C6.2.43 CAS, CASA, CASAL, CASL, Arm® Architecture Reference Manual Armv8, for Armv8-A architecture profile

CASA は、CAS に Load-Acquire を追加した命令です。

Load-Acquire
CASA 命令に続く命令は、必ずこの命令が終了した後に実行されることを保証する。
（アウトオブオーダーによる実行順序の変更を抑制する）

使い方

casa  w1, w2, [x0]

w1 レジスタの値と x0 レジスタが参照する値を比較する
- 値が一致した場合
  - w2 レジスタの値を、x0 レジスタの参照先に書き込む
変更される前の x0 レジスタ参照先の値を、w1 レジスタに書き込む
x0 レジスタ参照先の物理アドレスをアイコンしている他 CPU の global exclusives monitor をクリアする。
（他 CPU で WFE 命令で待機している場合、起床させる）
詳細は、こちらを参照

C 言語風に書くと、次のようになります。

// uint32_t w1
// uint32_t w2
// uint64_t* x0
uint32_t old = *x0;
if (w1 == *x0) {
  *x0 = w2;
}
w1 = old;

ARM によるスピンロックのリファレンス実装

仕様：

共有変数 lock が 0 の時、誰もロックを取得していない
共有変数 lock が 1 の時、ロックは取得されている

/*
 * Acquire lock using Compare and Swap instruction.
 *
 * Compare for 0 with acquire semantics, and swap 1. If failed to acquire, use
 * load exclusive semantics to monitor the address and enter WFE.
 *
 * void spin_lock(spinlock_t *lock);
 */
func spin_lock
    mov   w2, #1
1:  mov   w1, wzr
2:  casa  w1, w2, [x0]
    cbz   w1, 3f
    ldxr  w1, [x0]
    cbz   w1, 2b
    wfe
    b     1b
3:
    ret
endfunc spin_lock

    mov   w2, #1

w2 レジスタに 1 をセットします。
共有変数にセットするレジスタです。

1:  mov   w1, wzr

w1 レジスタに 0 をセットします。
wzr はゼロレジスタで、読み込むと 0 を返します。
共有変数と比較するレジスタです。

2:  casa  w1, w2, [x0]

前述の通りです。
x0 は関数 spin_lock() の第一引数（共有変数のアドレス）が入ります。

w1 には、書き換え前の x0 の値が入ります。
つまり、ロック取得成功時は w1 には 0（書き換え前に誰もロックを取得していなかった）が入ります。

    cbz   w1, 3f

w1 レジスタが 0 の時（ロック取得に成功したとき）、3 にジャンプします。

    ldxr  w1, [x0]

共有変数の値（x0 の参照先）を w1 に読み込みます。
ldxr（Load Exclusive Register）命令により、実行中 CPU の global exclusives monitor に x0 アドレスの物理アドレスをアイコンします。

    cbz   w1, 2b

共有変数の値が 0 の時（誰もロックを取得していないとき）、2 にジャンプします。
（再度、ロック取得を試みる）

wfe

共有変数の値が 0 以外の時（誰かがロックを取得しているとき）、低電力状態で待機します。
前述のリファレンス実装の spin_unlock() で stlr によるロックが解放される（共有変数に書き込みが発生する）と復帰します。

    b     1b

1 にジャンプします。
（ロックが解放されたので、再度ロック取得を試みる）
w1 レジスタを 0 クリアする必要がるので、2 ではなく 1 へジャンプします。

3:
    ret

呼び出し元関数へ戻ります。

フローチャート

LDAXR、STXR との比較

CASA 命令を使わない場合、共有変数の読み込みと書き込みを排他的に行うために、次のように LDAXR と STXR が必要になります。

    mov     w2, #1
    sevl
1:  wfe
2:  ldaxr   w1, [x0]
    cbnz    w1, 1b
    stxr    w1, w2, [x0]
    cbnz    w1, 2b
    ret

本記事の実装では LDXR を使っていますが、これは低電力のための WFE に必要なためです。
低電力を考えない場合、LDXR は不要で CASA のみで実装できます。
これは、おそらく次のような実装になると思います。

func spin_lock
    mov   w2, #1
    mov   w1, wzr
1:  casa  w1, w2, [x0]
    cbz   w1, 3f
2:  ldr   w1, [x0]
    cbz   w1, 1b
    b     2b
3:
    ret
endfunc spin_lock

C 言語風に書くと、次のようになります。

// uint64_t* x0
while(1) {
  // Compare and Swap
  if (0 == *x0) {
    *x0 = 1;
    break;
  }

  while(*x0);
}

Compare and Swap 部分にコストがかかるので毎回実行せず、while(*x0); でロックが開放されるのを待ってから、ロック取得を試みます。

補足

/*
 * When compiled for ARMv8.1 or later, choose spin locks based on Compare and
 * Swap instruction.
 */

CAS 命令は、ARMv8.1 から追加されました。

CASA

使い方

ARM によるスピンロックのリファレンス実装

フローチャート

LDAXR、STXR との比較

補足

Discussion