💮

Zircon のスピンロック実装(x86-64編)

2021/09/15に公開

並行プログラミング入門3.2.1Compare and Swap3.3.1 スピンロック を読んで触発されたので、Zircon のスピンロックについて紹介します。

事前知識

スピンロックとは

https://ja.wikipedia.org/wiki/スピンロック

関連する x86-64 命令

lock cmpxchg

スピンロックで排他処理の肝となる、lock プレフィックスと cmpxchg (compare and exchange) 命令です。

lock プレフィックスをつけた命令は、メモリアクセスを排他的に行うことができます。
(マルチコア環境で、他コアからのメモリアクセスを禁止します)

cmpxchg は、値の比較と交換を排他的に行います。
スピンロックで共有変数を比較し、値をセットする際に使用します。

  • lock プレフィックス

    添えられた命令の実行中に、プロセッサの LOCK#信号をアサートさせる(アトミック命令にする)。

    マルチプロセッサ環境では,LOCK#信号がアサートされている間,そのプロセッサが共有メモリを排他的に使用できるようになります。

    LOCK — Assert LOCK# Signal Prefix

  • cmpxchg 命令

    AL、AX、EAX、または RAX レジスタの値と第 1 オペランド(デスティネーション・オペランド)を比較します。

    2 つの値が等しい場合は、第 2 オペランド(ソースオペランド)がデスティネーションオペランドにロードされます。

    それ以外の場合は、デスティネーション・オペランドが AL、AX、EAX、または RAX レジスタにロードされます。

    この命令は,LOCK プレフィックスを付けて使用することで,アトミックに実行することができます。

    フラグへの影響

    ZF フラグは、デスティネーション・オペランドとレジスタ AL、AX、EAX の値が等しい場合にセットされ、そうでない場合はクリアされます。

    CMPXCHG — Compare and Exchange

    疑問:デスティネーションオペランドがレジスタの場合、lock プレフィックスは不要?
    おそらく不要

  • Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2 [1]

pause

スピン・ウェイト・ループのパフォーマンスを向上させます。スピン・ウェイト・ループを実行すると、プロセッサはループを抜けるときにメモリ順序違反の可能性を検出するため、パフォーマンスが低下します。

PAUSE 命令は、コード・シーケンスがスピン・ウェイト・ループであるというヒントをプロセッサに与えます。

プロセッサはこのヒントを利用してメモリ順序違反を回避し、プロセッサの性能を大幅に向上させます。

このため、すべてのスピンウェイトループに PAUSE 命令を配置することが推奨されます。

PAUSE 命令のもう一つの機能は、スピンループ実行時にプロセッサが消費する電力を削減することです。

プロセッサはスピンウェイトループを非常に高速に実行することができるため、リソースを待つ間に大量の電力を消費します。そのため、スピンしているリソースが利用可能になるのを待つ間、プロセッサは大量の電力を消費します。

スピンウェイトループに PAUSE 命令を挿入することで、プロセッサの消費電力を大幅に削減することができます。

PAUSE — Spin Loop Hint

関連する Clang/GCC built-in 関数

コンパイラが提供する関数です。Fuchsia のソースコードのなかでは定義されていません。

参考:

下記の引数、戻り値の型 type は、1、2、4、8、16 バイトのいずれか。

__atomic_compare_exchange_n()

bool __atomic_compare_exchange_n(
    type *ptr, type *expected, type desired,
    bool weak, int success_memorder, int failure_memorder)

共有変数 *ptr*expected が等値である場合に、success メモリオーダーで共有変数を desired で置き換えます。
等値なければ failure メモリオーダーで *expected を共有変数で置き換えます。

手順をコードで示すと次のようになります。

if (*ptr == *expected) {
  *ptr = desired;
} else {
  *expected = *ptr;
}

success_memorderfailure_memorder に関係なく、この「if 文の条件比較」と「*ptr への代入、もしくは *expected への代入」を排他的に行います。

使い方:

  • 誰にもロックされていないとき(*ptr == expected)、自分がロックを取得し(*ptr = desired)、true を返す

    Zircon スピンロック実装では、expected は 0、desired は自身を表す ID(CPU 番号+1)

  • 誰かがロックを取得しているとき(*ptr != expected)、誰がロックを取得しているかを知り(*expected = *ptr)、false を返す

    *ptr にセットされているのは、ロックを取得した人の ID(CPU 番号+1)

  • 引数

    • type *ptr
      現在の共有変数の値

    • type *expected
      *ptr と比較する値。
      誰もロックを取得していないときの *ptr の値

    • type desired
      ロックを取得したときに *ptr に書き込む値

    • bool weak

      weak compare_exchange(見かけ上の失敗が起こりうる)では true、strong compare_exchange(見かけ上の失敗は起こらない)では false となります。多くのターゲットは strong compare_exchange のみを提供し、weak パラメータを無視します。疑わしい場合は strong variation を使用してください。

      __atomic Builtins (Using the GNU Compiler Collection (GCC))

      clang 7.0.1-8+deb10u2 x86_64-pc-linux-gnu では、weaktrue でも false でも同じバイナリが出力された

    • int success_memorder
      Zircon スピンロック実装では __ATOMIC_ACQUIRE を指定する。

    • int failure_memorder
      Zircon スピンロック実装では __ATOMIC_RELAXED を指定する。

  • 戻り値

    • bool
      *ptr == *expected の結果。
      true の場合、ロックを取得できた。
      false の場合、ロックを取得できなかった。

Zircon のスピンロック実装では、__atomic_compare_exchange_n()lock cmpxchg にコンパイルされます。

__atomic_load_n()

type __atomic_load_n(type *ptr, int memorder)

memorder で指定されたメモリオーダーにしたがって、共有変数のアドレス ptr から値をアトミックに読み込みます。

  • 引数

    • type *ptr
      アトミックに読み込む共有変数のアドレス
    • int memorder
      Zircon スピンロック実装では __ATOMIC_RELAXED を指定する。
  • 戻り値

    • type
      アトミックに読み込んだ共有変数の値

Zircon のスピンロック実装では、__atomic_load_n()mov にコンパイルされます。

Pentium 以降のプロセッサでは、64 ビットバウンダリにアラインされたクワッドワードの読み書きはアトミックに実行されることが保証されています。

8.1.1 Guranteed Atomic Operations, Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3

__atomic_store_n()

void __atomic_store_n (type *ptr, type val, int memorder)

memorder で指定されたメモリオーダーにしたがって、共有変数 *ptrval でアトミックに置き換える。

  • 引数

    • type *ptr
      アトミックに書き込む共有変数のアドレス
    • type val
      アトミックに書き込む値
    • int memorder
      Zircon スピンロック実装では __ATOMIC_RELEASE を指定する。

Zircon のスピンロック実装では、__atomic_store_n()mov にコンパイルされます。

__ATOMIC_ACQUIRE

Creates an inter-thread happens-before constraint from the release (or stronger) semantic store to this acquire load. Can prevent hoisting of code to before the operation.

release 操作による書き込みと acquire 操作による読み込みの間に、スレッド間の先行発生制約happens-before constraint)を作成する。
当該操作の実行前に、コードを巻き上げる(code hoisting)ことを防ぐ。

__atomic Builtins (Using the GNU Compiler Collection (GCC))

__ATOMIC_RELEASE

Creates an inter-thread happens-before constraint to acquire (or stronger) semantic loads that read from this release store. Can prevent sinking of code to after the operation.

release 操作による書き込みと acquire 操作による読み込みの間に、スレッド間の先行発生制約happens-before constraint)を作成する。
当該操作の実行後に、コードを降下する(code sinking)ことを防ぐ。

__atomic Builtins (Using the GNU Compiler Collection (GCC))

__ATOMIC_RELAXED

Implies no inter-thread ordering constraints.

スレッド間の順序制約がないことを意味します。

__atomic Builtins (Using the GNU Compiler Collection (GCC))

_mm_pause()

void _mm_pause(void)

コードシーケンスがスピンウェイトループであることのヒントをプロセッサに提供する。これにより、スピンウェイトループの性能と消費電力を改善することができます。

_mm_pause Intel® Intrinsics Guide

ロック取得が失敗した場合、パフォーマンスを向上させるためには、トランザクションを迅速に中止する必要があります。これは、_mm_pause で行うことができます。

6.55 x86-Specific Memory Model Extensions for Transactional Memory

CPU がサポートしている場合、アセンブラ命令の pause にコンパイルされます。

Zircon のスピンロック関数

  • arch_spin_lock()
    ロックを取得するまでループする関数

  • arch_spin_trylock()
    一度だけロック取得を試みる関数

  • arch_spin_unlock()
    取得したロックを解放する関数

仕様:

  • 共有変数は lock->value
  • 共有変数が 0 の時、誰もロックしていない
  • 共有変数が 0 以外の時、誰かがロックしている
    • 共有変数にはロックを取得した CPU の CPU番号+1 がセットされる。これで、誰がロックを取得しているかがわかる
      (CPU 番号は 0 から始まるため、誰もロックしていない状態と区別するために、1 を足す)

arch_spin_lock()

zircon/kernel/arch/x86/spinlock.cc
 1: void arch_spin_lock(arch_spin_lock_t *lock) TA_NO_THREAD_SAFETY_ANALYSIS {
 2:   struct x86_percpu *percpu = x86_get_percpu();
 3:   unsigned long val = percpu->cpu_num + 1;
 4:
 5:   unsigned long expected = 0;
 6:   while (unlikely(!__atomic_compare_exchange_n(&lock->value, &expected, val, false,
 7:                                                __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))) {
 8:     expected = 0;
 9:     do {
10:       arch::Yield();
11:     } while (unlikely(__atomic_load_n(&lock->value, __ATOMIC_RELAXED) != 0));
12:   }
13:   percpu->num_spinlocks++;
14: }

ロックを取得するまでループする関数です。

  • 引数 arch_spin_lock_t *lock

    zircon/kernel/arch/x86/include/arch/spinlock.h
    typedef struct TA_CAP("mutex") arch_spin_lock {
      unsigned long value;
    } arch_spin_lock_t;
    
    • lock->value が共有変数
    • TA_CAP("mutex") の説明はこちら
 1: void arch_spin_lock(arch_spin_lock_t *lock) TA_NO_THREAD_SAFETY_ANALYSIS {
  • TA_NO_THREAD_SAFETY_ANALYSIS の説明はこちら
 2:   struct x86_percpu *percpu = x86_get_percpu();
 3:   unsigned long val = percpu->cpu_num + 1;
  • val は CPU 番号(0..)+ 1。
    ロック取得成功時に、この値を共有変数 lock->value にセットする
  • 将来、arch_curr_cpu_num() に書き換わると思われる。
    現在のアセンブラ 2 命令 movq %gs:0, %rcx; movl 88(%rcx), %edx が、1 命令 movl %gs:88, %edx になるので
 5:   unsigned long expected = 0;
  • expected = 0 は、lock->value と比較する値。
    ロックが空いている(lock->valueが 0 である)ことを期待することから、変数名 expected にしていると思われる
 6:   while (unlikely(!__atomic_compare_exchange_n(&lock->value, &expected, val, false,
 7:                                                __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))) {
  • ロック取得に成功するまで、ループを回し続ける

  • unlikely 属性
    コンパイラに最適化のヒントとして、条件 !__atomic_compare_exchange_n() が真(関数の戻り値がfalse)となる確率が低いことを伝える。
    __atomic_compare_exchange_n()false を返すのは、expected != lock->value(ロック取得に失敗した)時。
    つまり、ロック取得に失敗する確率は低いと想定している

  • ロック取得失敗時、expected には、lock->value の値が入るので、ポインタ &expected を渡している

  • __atomic_compare_exchange_n() では、lock->valueexpected を比較し、

    • 一致した場合、lock->valueval をセットし、true を返す(ロック取得成功)
    • 一致しなかった場合、expectedlock->value をセットし、false を返す(ロック取得失敗)
  • __ATOMIC_ACQUIRE__ATOMIC_RELAXED については前述の通り

 8:     expected = 0;
  • expected には、比較時の lock->value の値が入る。
    ここではロックが誰かに取得されているので、 0 以外の値が入っている。よって 0 に初期化しなおす
 9:     do {
10:       arch::Yield();
11:     } while (unlikely(__atomic_load_n(&lock->value, __ATOMIC_RELAXED) != 0));
  • arch::Yield()。実体は _mm_pause() で、pause 命令にコンパイルされる
    ビジーウェイトで CPU を回すと消費電力が高くなるので、緩和処置として puase を実行している

  • lock->value が 0 になったら、do-while ループを抜け、6 行目のループで再度、ロック取得を試みる。
    毎回 __atomic_compare_exchange_n() でロック取得を試みず __atomic_load_n() を間に挟む理由は、コストがかかるため。

    毎回 XCHG 命令を実行しながらループするのは得策ではない。一度 XCHG 命令を実行してだめだった場合、単にロック変数を読むだけのループに移行し、値が変化したときに再度 XCHG 命令を実行すべきということになる。

    スピンロック - Wikipedia

13:   percpu->num_spinlocks++;
  • percpu->num_spinlocksは、保持しているスピンロックの数を表す。
    ここでは、ロックを取得できたのでインクリメントしている
  • percpu は CPU コアごとに確保される。
    よって他コアとの排他制御を考慮しないでインクリメントできる

アセンブラ

llvm-objdump -D -C --no-leading-addr --no-show-raw-insn out/default/kernel_x64/zircon.elf
<arch_spin_lock(arch_spin_lock*)>:
 1:  pushq   %rbp
 2:  movq    %rsp, %rbp
 3:  movq    %gs:0, %rcx
 4:  movl    88(%rcx), %edx
 5:  incl    %edx
 6:  xorl    %eax, %eax         // 0xffffffff802d3732
 7:  lock
 8:  cmpxchgq        %rdx, (%rdi)
 9:  je      0xffffffff802d3747 <arch_spin_lock(arch_spin_lock*)+0x27>
10:  pause                      // 0xffffffff802d373b
11:  movq    (%rdi), %rax
12:  testq   %rax, %rax
13:  je      0xffffffff802d3732 <arch_spin_lock(arch_spin_lock*)+0x12>
14:  jmp     0xffffffff802d373b <arch_spin_lock(arch_spin_lock*)+0x1b>
15:  incl    92(%rcx)           // 0xffffffff802d3747
16:  popq    %rbp
17:  retq

llvm-objdump オプション

  • -D 全セクションをディスアセンブルする
  • -C シンボル名をデマングルする
    デマングルしない場合、void arch_spin_lock(arch_spin_lock_t *)_Z14arch_spin_lockP14arch_spin_lock になる
  • --no-leading-addr 行頭のアドレスを表示しない
  • --no-show-raw-insn 命令のバイト列を表示しない
 1:  push   %rbp
 2:  mov    %rsp,%rbp

Function prologue
ベースポインタをスタックへ退避後、スタックポインタで更新します。

 3:  movq    %gs:0, %rcx

CPU コア固有情報 struct x86_percpu のアドレスは、各 CPU の gs レジスタに格納されています。
%gs:0gs レジスタ値 + オフセット 0 を表します。
%gs:0 が表す struct x86_percpu の先頭メンバー struct x86_percpu *direct自身へのアドレス
よって、アドレス %gs:0 から読み込んだ値は struct x86_percpu の先頭アドレスとなります。

gs レジスタを CPU 固有情報の格納に使用する理由:

オペレーティングシステムは新しい SWAPGS 命令を使用して、ユーザーモードの GS セグメントと、カーネルモードの GS セグメントを切り替え、GS セグメント経由でカーネルモードの RSP をロードする。

x64 - Wikipedia

新しい 64 ビットモード命令の SWAPGS は、GS ベースのロードに使用できる。
SWAPGS は、KernelGSbase MSR から得られるカーネルデータ構造ポインタと GS ベースレジスタを交換する。その後、カーネルは、通常のメモリ参照で、GS プリフィックスを使用してカーネルデータ構造にアクセスできる

インテル ® エクステンデッド・メモリ 64 テクノロジ・ソフトウェア・デベロッパーズ・ガイド 第 1 巻

 4:  movl    88(%rcx), %edx
 5:  incl    %edx

88(%rcx) は、struct x86_percpu の先頭から 88 バイト目のメンバー cpu_num_t cpu_num を表します。
edx レジスタに percpu->cpu_num + 1 の値を格納します。
edx レジスタは変数 val を表します。
vallong 型で 64bit ですが、cpu_num_tuint32_t 型なので、32bit レジスタ edx を使用しているのでしょうか。オーバーフローしない?)

 6:  xorl    %eax, %eax

eax レジスタを 0 クリアする。
eax レジスタは変数 expected を表す。

 7:  lock
 8:  cmpxchgq        %rdx, (%rdi)
  • lock プレフィックス
    他 CPU による、rdi レジスタが格納するアドレス(&(lock->value))へのメモリアクセスは排他的に行われる

  • rdx レジスタ(CPU 番号+1)
    上位 32 ビット:0
    下位 32 ビット:edx レジスタ(変数 val = CPU 番号+1)

  • rdi レジスタ(&(lock->value)
    arch_spin_lock() の第一引数 arch_spin_lock_t *lock アドレスを格納。
    lock->valuearch_spin_lock 構造体の先頭メンバー変数なので、&(lock->value)lock は同じアドレス

  • cmpxchgq 命令
    rax レジスタ(expected)と rdi レジスタの指す値(lock->value)を比較

    • 一致すると rdi レジスタの指す値(lock->value) に rdx レジスタ値(val)をセット。ZF フラグを立てる
      読み込んだ共有変数 lock->value が 0 であり、自身のCPU番号+1を書き込めた、つまりロックを取得できた

    • 一致しないと rax レジスタ(expected)に rdi レジスタの指す値(lock->value)をセット

      読み込んだ共有変数 lock->value が 0 でなかった、つまり(すでに誰かがロックを取得しているので)ロックを取得できなかった

 9:  je      0xffffffff802d3747 <arch_spin_lock(arch_spin_lock*)+0x27>

ZF フラグが立っている(ロックを取得できた)場合、do-while ループを抜けます。
15 行目にジャンプします。

10:  pause

ZF フラグが立っていない(ロックを取得できなかった)場合、do-while ループに入ります。
このとき、pause 命令で消費する電力を削減します。

11:  movq    (%rdi), %rax

rdi レジスタが指す値 lock->valuerax レジスタに読み込む。
__atomic_load_n() は単なるメモリ読み出し movq 命令に置き換わっています。

12:  testq   %rax, %rax

rax レジスタ(lock->value)が 0 の時、ZF フラグを立てる。
命令の意味としては、rax レジスタと rax レジスタの論理積をとり、0 の場合に ZF フラグ立てる。

Computes the bit-wise logical AND of first operand (source 1 operand) and the second operand (source 2 operand) and sets the SF, ZF, and PF status flags according to the result. T

TEST - Logical Compare, Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2

13:  je      0xffffffff802d3732 <arch_spin_lock(arch_spin_lock*)+0x12>

ZF フラグが立っている場合(lock->value == 0 の場合)、6 行目にジャンプ。
cmpxchgq でロック取得を再度試みます。

14:  jmp     0xffffffff802d373b <arch_spin_lock(arch_spin_lock*)+0x1b>

ZF フラグが立っていない場合(lock->value != 0 の場合)、10 行目にジャンプ。
lock->value が 0 になるまでループを繰り返します。

15:  incl    92(%rcx)

struct arch_spin_lock 構造体の先頭から 92 バイト目にある uint32_t num_spinlocks メンバーをインクリメントします。

16:  popq    %rbp
17:  retq

Function epilogue
ベースポインタをスタックから復帰し、呼び出し元にジャンプします。

arch_spin_trylock()

zircon/kernel/arch/x86/spinlock.cc
 1: bool arch_spin_trylock(arch_spin_lock_t *lock) TA_NO_THREAD_SAFETY_ANALYSIS {
 2:   struct x86_percpu *percpu = x86_get_percpu();
 3:   unsigned long val = percpu->cpu_num + 1;
 4:
 5:   unsigned long expected = 0;
 6:
 7:   __atomic_compare_exchange_n(&lock->value, &expected, val, false, __ATOMIC_ACQUIRE,
 8:                               __ATOMIC_RELAXED);
 9:   if (expected == 0) {
10:     percpu->num_spinlocks++;
11:   }
12:
13:   return expected != 0;
14: }

一度だけロック取得を試みる関数です。

  • 引数 arch_spin_lock_t *lock
    こちらを参照

  • 戻り値

    • false ロック取得に成功。
      一般的に、ロック取得時は true を返すのが自然な気がしますが、なぜ false を返すのか
    • true ロック取得に失敗
 1: bool arch_spin_trylock(arch_spin_lock_t *lock) TA_NO_THREAD_SAFETY_ANALYSIS {
  • TA_NO_THREAD_SAFETY_ANALYSIS の説明はこちら
 2:   struct x86_percpu *percpu = x86_get_percpu();
 3:   unsigned long val = percpu->cpu_num + 1;
 5:   unsigned long expected = 0;

arch_spin_lock() と同様。

 7:   __atomic_compare_exchange_n(&lock->value, &expected, val, false, __ATOMIC_ACQUIRE,
 8:                               __ATOMIC_RELAXED);

一度だけロック取得を試みます。

  • __atomic_compare_exchange_n() では、lock->valueexpected を比較し、

    • 一致した場合、lock->valueval をセットし、true を返す(ロック取得成功)
    • 一致しなかった場合、expectedlock->value をセットし、false を返す(ロック取得失敗)
 9:   if (expected == 0) {
10:     percpu->num_spinlocks++;
11:   }

expected が 0 となるのは、lock->value が 0 のとき、つまりロック取得成功時。
このとき、スピンロック保持数 percpu->num_spinlocks をインクリメントします。

13:   return expected != 0;
  • ロック取得 成功 時(expected == 0)、false を返す
  • ロック取得 失敗 時(expected != 0)、true を返す

アセンブラ

llvm-objdump -D -C --no-leading-addr --no-show-raw-insn out/default/kernel_x64/zircon.elf
<arch_spin_trylock(arch_spin_lock*)>:
 1:  pushq   %rbp
 2:  movq    %rsp, %rbp
 3:  movq    %gs:0, %rcx
 4:  movl    88(%rcx), %edx
 5:  incl    %edx
 6:  xorl    %eax, %eax
 7:  lock
 8:  cmpxchgq        %rdx, (%rdi)
 9:  jne     0xffffffff802d377e <arch_spin_trylock(arch_spin_lock*)+0x1e>
10:  incl    92(%rcx)
11:  testq   %rax, %rax         // 0xffffffff802d377e
12:  setne   %al
13:  popq    %rbp
14:  retq
 1:  pushq   %rbp
 2:  movq    %rsp, %rbp

Function prologue

 3:  movq    %gs:0, %rcx
 4:  movl    88(%rcx), %edx
 5:  incl    %edx

val = percpu->cpu_num + 1
詳細は arch_spin_lock() を参照。

 6:  xorl    %eax, %eax

expected = 0
詳細は arch_spin_lock() を参照。

 7:  lock
 8:  cmpxchgq        %rdx, (%rdi)

__atomic_compare_exchange_n()
lock->value == expected つまり lock->value == 0 の時、ロック取得成功で、ZF フラグを立てます。
詳細は arch_spin_lock() を参照。

 9:  jne     0xffffffff802d377e <arch_spin_trylock(arch_spin_lock*)+0x1e>

ZF フラグが立っていない場合(ロック取得に失敗した場合)、11 行目にジャンプします。

10:  incl    92(%rcx)

ZF フラグが立っている場合(ロック取得に成功した場合)、percpu->num_spinlocks++
詳細は arch_spin_lock() を参照。

11:  testq   %rax, %rax

戻り値の準備。
rax レジスタ(expected)を判定。

  • 0 の時、ZF フラグを立てる
  • 0 以外の時、ZF フラグを立てない
12:  setne   %al

戻り値を al レジスタ(raxレジスタの下位 1 バイト)にセット。

  • ZF フラグが立っていないとき(expected != 0のとき)、al レジスタに 1 をセット
    ロック取得に失敗したとき、trueを返す
  • ZF フラグが立っているとき(expected == 0)、al レジスタに 0 をセット
    ロック取得に成功したとき、falseを返す

Set byte if not equal (ZF=0)

Sets the destination operand to 0 or 1 depending on the settings of the status flags (CF, SF, OF, ZF, and PF) in the EFLAGS register.

SETcc - Set Byte on Condition, Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2

13:  popq    %rbp
14:  retq

Function epilogue

arch_spin_unlock()

zircon/kernel/arch/x86/spinlock.cc
1: void arch_spin_unlock(arch_spin_lock_t *lock) TA_NO_THREAD_SAFETY_ANALYSIS {
2:   x86_get_percpu()->num_spinlocks--;
3:   __atomic_store_n(&lock->value, 0UL, __ATOMIC_RELEASE);
4: }

取得したロックを解放する関数です。

  • 引数 arch_spin_lock_t *lock
    こちらを参照
1: void arch_spin_unlock(arch_spin_lock_t *lock) TA_NO_THREAD_SAFETY_ANALYSIS {
  • TA_NO_THREAD_SAFETY_ANALYSIS の説明はこちら
2:   x86_get_percpu()->num_spinlocks--;

CPU 固有のデータから、保持しているスピンロックの数をデクリメントします。
x86_get_percpu() で取得する構造体は CPU コアごとに用意されているので、値を変更する際に他コアとの排他制御が不要です。

3:   __atomic_store_n(&lock->value, 0UL, __ATOMIC_RELEASE);

__atomic_store_n() により、アトミックに lock->value に 0 を書き込みます。
__ATOMIC_RELEASE については、前述の通り。
サフィックスULunsigned longを表します。

アセンブラ

llvm-objdump -D -C --no-leading-addr --no-show-raw-insn out/default/kernel_x64/zircon.elf
<arch_spin_unlock(arch_spin_lock*)>:
1:  pushq   %rbp
2:  movq    %rsp, %rbp
3:  movq    %gs:0, %rax
4:  decl    92(%rax)
5:  movq    $0, (%rdi)
6:  popq    %rbp
7:  retq
1:  pushq   %rbp
2:  movq    %rsp, %rbp

Function prologue

3:  movq    %gs:0, %rax
4:  decl    92(%rax)

x86_get_percpu()->num_spinlocks--
詳細は arch_spin_lock() を参照。

5:  movq    $0, (%rdi)

lock->value = 0
$0 は即値。

疑問:arch_spin_lock()arch_spin_trylock()cmpxchg による lock->value の読み込み、書き込みと競合するか?
しない。lock プレフィックスのおかげで、メモリ lock->value への読み込み・書き込みは排他されるため。

6:  popq    %rbp
7:  retq

Function epilogue

付録

lock プレフィックス

添えられた命令の実行中に、プロセッサの LOCK#信号をアサートさせる(アトミック命令にする)。

マルチプロセッサ環境では,LOCK#信号がアサートされている間,そのプロセッサが共有メモリを排他的に使用できるようになります。

ほとんどの IA-32 およびすべての Intel 64 プロセッサでは、LOCK#信号がアサートされていなくてもロックが発生することがあります。

詳細は、「IA32 アーキテクチャの互換性」の項を参照してください。

LOCK プレフィックスは、以下の命令のうち、デスティネーションオペランドがメモリオペランドである命令のみに付加することができます。ADD、ADC、AND、BTC、BTR、BTS、CMPXCHG、CMPXCH8B、CMPXCHG16B、> DECXCHG16B、DECXCHG16B、DECXCHG16B、DECXCHG16B。CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, XCHG です。

これらの命令に LOCK 接頭辞が使用されている場合、ソースオペランドがメモリオペランドの場合,未定義オペコード例外 (#UD) が発生することがあります。

また,上記以外の命令で LOCK 接頭辞を使用した場合も,未定義オペコード例外が発生します。未定義オペコード例外が発生します。

XCHG 命令は,LOCK 接頭辞の有無にかかわらず,常に LOCK# 信号をアサートします。

LOCK プレフィックスは,共有メモリ環境でメモリ位置のリードモディファイ・ライト操作を行う BTS 命令と一緒に使用されるのが一般的です。

LOCK プレフィックスの整合性は、メモリフィールドのアラインメントの影響を受けません。

メモリロックは 任意にアラインメントのずれたフィールドに対してもメモリロックが行われます。

この命令の動作は、64 ビット以外のモードでも 64 ビットモードでも同じです。

LOCK - Assert LOCK# Signal Prefix, Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2

cmpxchg

AL、AX、EAX、または RAX レジスタの値と第 1 オペランド(デスティネーション・オペランド)を比較します。

2 つの値が等しい場合は、第 2 オペランド(ソースオペランド)がデスティネーションオペランドにロードされます。

それ以外の場合は、デスティネーション・オペランドが AL、AX、EAX、または RAX レジスタにロードされます。RAX レジスタは 64 ビットモードでのみ使用可能です。

この命令は,LOCK プレフィックスを付けて使用することで,アトミックに実行することができます。

プロセッサのバスとのインターフェイスを簡素化するためにデスティネーションオペランドは、比較の結果に関係なく書き込みサイクルを受け取ります。

比較に失敗した場合はデスティネーションオペランドが書き戻され、そうでない場合はソースオペランドがデスティネーションに書き込まれます。(プロセッサは、ロックされた書き込みを行わずにロックされた読み出しを行うことはありません。)

64 ビットモードでは、この命令のデフォルトの演算サイズは 32 ビットです。

REX.R を使用すると,追加のレジスタ(R8 ~ R15)にアクセスできます。REX.W を使用すると 64 ビットになります。

データのエンコード方法については、本章冒頭の概要図をご参照ください。

CMPXCHG - Compare and Exchange, Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2

pause

スピン・ウェイト・ループのパフォーマンスを向上させます。スピン・ウェイト・ループを実行すると、プロセッサはループを抜けるときにメモリ順序違反の可能性を検出するため、パフォーマンスが低下します。

PAUSE 命令は、コード・シーケンスがスピン・ウェイト・ループであるというヒントをプロセッサに与えます。

プロセッサはこのヒントを利用して を利用してメモリ順序違反を回避し、プロセッサの性能を大幅に向上させます。

このため、すべてのスピンウェイトループに PAUSE 命令を配置することが推奨されます。

PAUSE 命令のもう一つの機能は、スピンループ実行時にプロセッサが消費する電力を削減することです。

プロセッサはスピンウェイトループを非常に高速に実行することができるため、リソースを待つ間に大量の電力を消費します。そのため、スピンしているリソースが利用可能になるのを待つ間、プロセッサは大量の電力を消費します。

スピンウェイトループに PAUSE 命令を挿入することで、プロセッサの消費電力を大幅に削減することができます。

この命令は、Pentium 4 プロセッサで導入されましたが、すべての IA-32 プロセッサと下位互換性があります。

それ以前の IA-32 プロセッサでは、PAUSE 命令は NOP 命令のように動作します。Pentium 4 および Intel Xeon プロセッサでは、PAUSE 命令を遅延として実装しています。

遅延時間は有限で、プロセッサによってはゼロになることもあります。

この命令は、プロセッサのアーキテクチャの状態を変更しません(つまり、本質的には遅延のノーロップ操作を行います)。

この命令の動作は、64 ビット以外のモードでも 64 ビットモードでも同じです。

PAUSE - Spin Loop Hint, Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2

TA_* マクロ

TA_* マクロは、Clang Thread Safety Analysis を使った静的解析です。
詳しくは、こちらの記事をご覧ください。

zircon/kernel/arch/x86/include/arch/spinlock.h
void arch_spin_lock(arch_spin_lock_t *lock) TA_ACQ(lock);
bool arch_spin_trylock(arch_spin_lock_t *lock) TA_TRY_ACQ(false, lock);
void arch_spin_unlock(arch_spin_lock_t *lock) TA_REL(lock);

TA_ACQ(lock)

__attribute__((acquire_capability(lock)))展開されます

TA_TRY_ACQ(false, lock)

__attribute__((try_acquire_capability(false, lock)))展開されます
...

TA_REL(lock)

__attribute__((release_capability(lock)))展開されます

TA_CAP("mutex")

__attribute__((capability("mutex")))展開されます

TA_NO_THREAD_SAFETY_ANALYSIS

__attribute__((no_thread_safety_analysis))展開されます

脚注
  1. マニュアルは Intel 記法。AT&T 記法とは SRC と DST が逆になっている。 ↩︎

Discussion