Rust Atomic compare and swap 2018 editionのRISC-Vソース〜LLVMを添えて〜 #Rust

はじめに

本記事は、Rust Advent Calendar 2018の22日目として書かれました。
タイトルは少しふざけていますが、内容は真剣です。ぜひ楽しんでいって下さい。

事の発端あるいは茶番

2018年11月初旬

僕「RustでRISC-VをターゲットにOS自作するの楽すぎ！至高！」
僕「UARTデバイスを複数threadから安全にアクセスできるようにするぞ！」
僕「これ、Writing an OS in Rustでやったところだ！lazy_staticとかspin crate使えば良いんでしょ？」

Cargo.toml

...
[dependencies]
spin = "0.4.10"

僕「よし、Cargo.tomlも書いたし、簡単な実装もした。いざ！」

$ cargo build
   Compiling spin v0.4.10
error[E0599]: no method named `compare_and_swap` found for type `core::sync::atomic::AtomicBool` in the current scope
   -->
    |
157 |         while self.lock.compare_and_swap(false, true, Ordering::Acquire) != false
    |                         ^^^^^^^^^^^^^^^^

error[E0599]: no method named `compare_and_swap` found for type `core::sync::atomic::AtomicBool` in the current scope

僕「core::sync::atomic…。めっちゃ辛そうなところでエラー出るやん・・・」
僕「なんか納得いかんから調べたろ」

この記事 is 何？

Rust core libraryのcore::sync::atomic::Atomic*.compare_and_swap関数を解析した経過と結果を記したものです。それ以外のことは出てきません。
途中からLLVMに突入しますので、C++成分がそれなりに混じっています。RISC-Vのアセンブリソースコードも少々あります。RISC-Vのアセンブリは難しくないので大丈夫です。

今回、この記事に関わる調査を行ったおかげで、次の知見を得ることができました。

Rust標準ライブラリのソースコードリーディング勘所を少し
Rust compilerとLLVMとの関係性を少し
LLVMのコード生成処理を少し

一番大きかった収穫は、Rust言語処理系のソースコードリーディングが楽しい、ということです。これは、コード自体の品質が高いこともありますが、コメントやテストコードが充実しているため、読み進めやすいからだと思います。自分自身でもこのようなリテラシーの高いコードを書いて行こう、という気持ちになれて、非常に良い刺激を得ることができました。
やりたいことができない、がスタート地点でしたが、結果として前よりもっとRustが好きになりました。

つまり、この記事の趣旨は、広めよう！Rust言語処理系リーディングの輪！ ということです。

以降、本記事は次の流れで展開します。

プロセッサのAtomicなデータ更新 (compare and swapとは？)
Rust core library解析
Rust compiler解析
LLVMコード生成部解析

プロセッサのAtomicなデータ更新

排他制御の一種です。近代のプロセッサでは、マルチスレッドにおいて、Atomicなメモリ操作が行えるロードストア命令が用意されています (確かMIPS R3000とかにはなかったと思います)。
ARMプロセッサにおけるロックフリーなデータ更新、に詳しく書かれています。以降のコード例で引用させて頂いています。ありがとうございます。

排他制御の必要性について、簡単に説明します。よく銀行取引の例をみかける、あれです。
プロセッサレベルでも同様で、スレッドAとスレッドBが、共有メモリにアクセスする場合に、スレッドAがデータ更新している途中で、スレッドBがデータを更新してしまうと、データの整合性がなくなってしまいます。
シングルコアプロセッサでは、単に割り込みを禁止すれば良いのですが、マルチコアプロセッサにおいては、他のプロセッサが共有データを変更していないこと、を保証する必要があります。
そこで、近代の命令セットアーキテクチャではAtomicなメモリ操作命令、というものを持っています。Atomicとは、その操作を行っている間、別の操作に割り込まれないことを意味します。

典型的な排他制御では、spin lockやMutexのように、共有データにロックをかけることで、排他制御します。ロックがかかっている間は、他スレッドの共有データへのアクセスを禁止します。
ロックがかかっている間、他スレッドは待ち状態になってしまうため、パフォーマンス低下に繋がる恐れがあります。

そこで、プロセッサではロックを使用せずに、Atomicな共有データアクセスをするための命令を備えています。
この命令には、2つの方法があります。

compare and swap (cas)
load link/store condition (ll/sc)

RISC-Vでは、ll/scではなく、load reserved/store conditional (lr/sc)というニーモニックになっています。

compare and swap

x86ではcmpxchgという名前の命令です。x86のアセンブリを説明するのは大変心が折れるので、C言語の擬似コードで見ていきます(ARMプロセッサにおけるロックフリーなデータ更新からの引用です)。
あるメモリアドレスptrの現在値が、古い値oldと等しければ、新しい値oldをptrに書き込みます(古い値も新しい値もメモリ上にある)。新しい値を書き込んだ場合、1を返します。

int CAS(void *ptr, void *old, void *new) {
  if (memcmp(ptr, old) == 0) {
    memcpy(ptr, new); // Set new value to ptr
    return 1;
  }
  memcpy(old, ptr);
  return 0;
}

使い方を見ると理解しやすいと思うので、ARMプロセッサにおけるロックフリーなデータ更新の例をさらに引用します。

void AtomicOp(int *ptr)
{
    while(1)
    {
        const int OldValue = *ptr;  // ★1
        const int NewValue = UpdateData(OldValue); //Update old value to new value

        // If the result is the original value, the new value was stored.
        if(CAS(ptr, &OldValue, &NewValue))  // ★2
        {
            return;
        }
    }
}

上記コードを説明します。あるアドレスptrから、古い値OldValueを読み込み、新しい値NewValueを計算します。
compare and swap命令では、ptrに格納されている値がOldValueと等しいときに、NewValueをptrに書き込みます。NewValueを書き込んだ時、結果は1に、それ以外のときは0になります。
compare and swap命令実行時、ptrに格納されている値がOldValueと等しい、ということは、★1から★2の間にデータが変更されていない、ということになります。これは、他のスレッドから値が書き換えられていないことを意味します。実際は擬陽性の問題があり、OldValue⇨AnotherValue⇨OldValueという変更があった場合に、検出できません。
もし、データが書き換えられていた場合は、データ更新は行われず、もう1度OldValueを読み込むところからやり直します。

ll/scまたはlr/sc

ARMやRISC-Vがサポートしている命令です。こちらの命令では、ll (load link)/sc (store conditional)というロードストア命令をペアで使います。
ll命令で、 「このアドレスのデータ、予約しといて」 ということで、reservedフラグをつけておきます。sc命令で値を更新する際、 「予約しといたアドレスのデータ、まだ予約されてる？されてるんやったら更新しといて！」 ということをやります。データが別スレッドにより更新されている場合は、 「何ィ？予約しといて言うのに、他の人が触ったぁ！？じゃあ、もっかい予約するから、今度こそ取っといてな。頼むでほんま。」 となります。

RISC-Vのlr/scについては、RISC-V specificationsの7. "A" Standard Extension for Atomic Instructions, Version 2.0に記載があります。

RISC-V命令セットで、compare and swapではなくlr/scを採用する理由は、擬陽性(ABA)問題と、必要となるオペランド数によるところが大きいです。
compare and swapでは、ソースオペランドが3つ(ptr, OldValue, NewValue)必要になります。それに対して、lr/scでは、2オースオペランドで済みます。
これは、データパスを単純に保つ上で重要であるため、RISCプロセッサの選択として、納得のいくものです。

Both compare-and-swap (CAS) and LR/SC can be used to build lock-free data structures. After
extensive discussion, we opted for LR/SC for several reasons: 1) CAS suffers from the ABA
problem, which LR/SC avoids because it monitors all accesses to the address rather than only
checking for changes in the data value; 2) CAS would also require a new integer instruction format
to support three source operands (address, compare value, swap value) as well as a different
memory system message format, which would complicate microarchitectures;

他2つの理由も併記されているので、興味がある方は、specificationをご参照下さい。

lr/scを使って、compare and swap機能を実現する場合、次のようなアセンブリコードになります。

# a0 holds address of memory location                  -> ptr
# a1 holds expected value                              -> old
# a2 holds desired value                               -> new
# a0 holds return value, 0 if successful, !0 otherwise -> return
cas:
    lr.w t0, (a0)     # Load original value.
    bne t0, a1, fail  # Doesn’t match, so fail.
    sc.w a0, a2, (a0) # Try to update.
    bnez a0, cas      # Retry if store-conditional failed.
    jr ra # Return.
fail:
    li a0, 1          # Set return to failure.
    jr ra # Return.

このように、RISC-Vに備わっているlr/sc命令を組み合わせることでcompare and swapが実現できるため、spin crateをコンパイルしようとしたときに、Atomic*型にcompare_and_swap関数が実装されていない、というのは不自然であると考えました。
そこで、実装がどうなっているのか気になったため、調査を行うこととしました。

Dive into the Rust Error Message

改めて、エラーコードを再掲載します。やはり何事も基本はエラーメッセージを解析するところからです。

$ cargo build
   Compiling spin v0.4.10
error[E0599]: no method named `compare_and_swap` found for type `core::sync::atomic::AtomicBool` in the current scope
   -->
    |
157 |         while self.lock.compare_and_swap(false, true, Ordering::Acquire) != false
    |                         ^^^^^^^^^^^^^^^^

error[E0599]: no method named `compare_and_swap` found for type `core::sync::atomic::AtomicBool` in the current scope

まず、エラーメッセージはそのまま、compare_and_swap関数がない、というものです。
一応、E0599というError Indexも確認しておきましょう。
Rust Compiler Error Indexには、サンプルコードを含めた、Rust compilerのエラー解説があります。

This error occurs when a method is used on a type which doesn't implement it:
Erroneous code example:
```rust
struct Mouth;

let x = Mouth;
x.chocolate(); // error: no method named chocolate found for type Mouth
// in the current scope
```

残念ながら、今回は役に立ちそうもありません。

Dive into the Rust core library

Atomic*であれば何でも良いので、一旦、AtomicBoolの実装を解析していきましょう。
これはRust core libraryの中にあります。

libcore/sync/atomic.rs

#[cfg(target_has_atomic = "8")]
impl AtomicBool {
...
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[cfg(target_has_atomic = "cas")]
    pub fn compare_and_swap(&self, current: bool, new: bool, order: Ordering) -> bool {
        match self.compare_exchange(current, new, order, strongest_failure_ordering(order)) {
            Ok(x) => x,
            Err(x) => x,
        }
    }

いきなり重要なアトリビュートが見つかります。
#[cfg(target_has_atomic = "cas")]、この部分ですね。casは、compare_and_swapの略で、命令セットの記述で頻繁に用いられます。target tripleがcasをサポートしていない場合は、関数が定義されないことになります。
このtarget_has_atomicがどこでどのように定義されているか、を追いかけます。
現在のRustでは、2つのRISC-Vアーキテクチャがサポートされています。

riscv32imc_unknown_none_elf.rs
riscv32imac_unknown_none_elf.rs

余談ですが、RISC-Vでは、命令セットを任意の組み合わせで拡張できるようになっています。
rv32は、32 bitアーキテクチャを意味しており、その後に、i, m, a, c, f, dといった、どのような命令をサポートしているか、の情報が続きます。
i -> 整数、m -> 整数乗除算、a -> Atomic、c -> 16 bit圧縮命令、f -> 単精度浮動小数点、d -> 倍精度浮動小数点、といった感じです。

Rustでサポートしている1つ目は、Atomic命令をサポートしないrv32imcです。こちらをターゲットにする場合は、compare and swapがなくても納得です。
target tripleを見ても、atomic_casがfalseになっています。

librustc_target/spec/riscv32imc_unknown_none_elf.rs

pub fn target() -> TargetResult {
...
        options: TargetOptions {
            linker: Some("rust-lld".to_string()),
            cpu: "generic-rv32".to_string(),
            // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86005
            max_atomic_width: None, //Some(32),
            atomic_cas: false,  // atomic_casはdisableされている
            features: "+m,+c".to_string(),
...
        },

これに対して、Atomic命令をサポートするrv32imac(aの追加がAtomic命令サポートの意味)では、compare and swapが使えても良さそうです。
上述したとおり、lr/scでcompare and swapが実現できるためです。

librustc_target/spec/riscv32imac_unknown_none_elf.rs

pub fn target() -> TargetResult {
...
        options: TargetOptions {
            linker: Some("rust-lld".to_string()),
            cpu: "generic-rv32".to_string(),
            max_atomic_width: Some(32),
            atomic_cas: false, // incomplete +a extension
            features: "+m,+a,+c".to_string(),
...
        },

何やら、// incomplete +a extensionなる不穏なコメントがあります(筆者が追記したものではなく、元々ソースコードに存在するコメントです)。
ここのatomic_casがfalseなので、compare_and_swapのアトリビュートで弾かれている、と考えるのが自然です。

さて、これではRISC-Vでは、compare and swapが使えなくても不思議ではありません。めでたしめでたし。とは、なりません！
先ほどから説明している通り、lr/scの組み合わせでcompare and swapが実現できるはずなのです！徹底的に行きましょう！

atomic_cas: falseがtarget_has_atomic = "cas"に変換される過程も追いたいところですが、一旦先に進みましょう。

compare_and_swap関数では、compare_exchangeに処理を移譲して、その結果がOk/Err、どちらでもその中身を返しています。

libcore/sync/atomic.rs

    // 再掲載
    #[cfg(target_has_atomic = "cas")]
    pub fn compare_and_swap(&self, current: bool, new: bool, order: Ordering) -> bool {
        match self.compare_exchange(current, new, order, strongest_failure_ordering(order)) {
            Ok(x) => x,
            Err(x) => x,
        }
    }

compare_exchangeの中身に移ります。

libcore/sync/atomic.rs

impl AtomicBool {
    #[inline]
    #[stable(feature = "extended_compare_and_swap", since = "1.10.0")]
    #[cfg(target_has_atomic = "cas")]
    pub fn compare_exchange(&self,
                            current: bool,
                            new: bool,
                            success: Ordering,
                            failure: Ordering)
                            -> Result<bool, bool> {
        match unsafe {
            atomic_compare_exchange(self.v.get(), current as u8, new as u8, success, failure)
        } {
            Ok(x) => Ok(x != 0),
            Err(x) => Err(x != 0),
        }
    }

unsafeなatomic_compare_exchangeが出てきましたね。これは、機械語が近そうな予感がします。
次に、atomic_compare_exchangeを確認していきましょう。
これは、Atomic系で共通するジェネリック関数として定義されています。

libcore/sync/atomic.rs

#[inline]
#[cfg(target_has_atomic = "cas")]
unsafe fn atomic_compare_exchange<T>(dst: *mut T,
                                     old: T,
                                     new: T,
                                     success: Ordering,
                                     failure: Ordering)
                                     -> Result<T, T> {
    let (val, ok) = match (success, failure) {
        (Acquire, Acquire) => intrinsics::atomic_cxchg_acq(dst, old, new),
        (Release, Relaxed) => intrinsics::atomic_cxchg_rel(dst, old, new),
        (AcqRel, Acquire) => intrinsics::atomic_cxchg_acqrel(dst, old, new),
        (Relaxed, Relaxed) => intrinsics::atomic_cxchg_relaxed(dst, old, new),
        (SeqCst, SeqCst) => intrinsics::atomic_cxchg(dst, old, new),
        (Acquire, Relaxed) => intrinsics::atomic_cxchg_acq_failrelaxed(dst, old, new),
        (AcqRel, Relaxed) => intrinsics::atomic_cxchg_acqrel_failrelaxed(dst, old, new),
        (SeqCst, Relaxed) => intrinsics::atomic_cxchg_failrelaxed(dst, old, new),
        (SeqCst, Acquire) => intrinsics::atomic_cxchg_failacq(dst, old, new),
        (_, AcqRel) => panic!("there is no such thing as an acquire/release failure ordering"),
        (_, Release) => panic!("there is no such thing as a release failure ordering"),
        _ => panic!("a failure ordering can't be stronger than a success ordering"),
    };
    if ok { Ok(val) } else { Err(val) }
}

AcquireやReleaseを説明し始めると長くなってしまうので、簡単な紹介だけに留めます。
基本的な考え方は、どの程度ロードストア命令の順番入れ替えを許容するか、です。
Acquire指定の命令を実行する際、後続のメモリアクセス命令は、Acquire指定の命令より先に実行することはできません。
Release指定の命令の実行する際、先行のメモリアクセス命令は、Release指定の命令より後に実行することはできません。

compare and swapは、compare_exchangeを経て、cxchgと略されています。
intrinsics、の意味を知らなかったので、google先生に聞いてみます。
本来備わっている、固有の、本質的な という意味のようです。わかったような、わからないような気がするため、もう少し調べてみました。

What are intrinsics?

Normally, "intrinsics" refers to functions that are built-in

なるほど。built-inで、コンパイラが最適化したコードを生成できる機能であることを意味するようです。腑に落ちました。
これは、LLVMのintrinsicに関係あることが推測できます。
最終的にはLLVMに関係がありそうですが、まだRustのコードで見るところがあります。atomic.rsでは、use intrinsicsとしています。こいつは何者でしょうか？

libcore/sync/atomic.rs

use intrinsics;

Rust doc std::intrinsics

The corresponding definitions are in librustc_codegen_llvm/intrinsic.rs.

お、LLVM codegenへの言及がなされています。
これは、本格的にLLVMが原因で、RISC-Vでspinが使えない予感がします。
src/libcore/intrinsics.rsに進みましょう。

src/libcore/intrinsics.rs

extern "rust-intrinsic" {
    // NB: These intrinsics take raw pointers because they mutate aliased
    // memory, which is not valid for either `&` or `&mut`.

    /// Stores a value if the current value is the same as the `old` value.
    /// The stabilized version of this intrinsic is available on the
    /// `std::sync::atomic` types via the `compare_exchange` method by passing
    /// [`Ordering::SeqCst`](../../std/sync/atomic/enum.Ordering.html)
    /// as both the `success` and `failure` parameters. For example,
    /// [`AtomicBool::compare_exchange`][compare_exchange].
    ///
    /// [compare_exchange]: ../../std/sync/atomic/struct.AtomicBool.html#method.compare_exchange
    pub fn atomic_cxchg<T>(dst: *mut T, old: T, src: T) -> (T, bool);

externされているだけなので、FFIっぽいな、と思いましたが、the bookを見るとどうやら違うようです。

The Book intrinsics

intrinsicsは特別なABI rust-intrinsic を用いて、FFIの関数で有るかのようにインポートされます。

じゃあ実体はどこにあるねん？と思ったら、ソースコードの先頭に書いてありました。

The corresponding definitions are in librustc_codegen_llvm/intrinsic.rs.

ということで、次はrustcです。