Cargoでgitレポジトリ内にある一部crateを依存に追加する

はじめに

Cargo で crates.io に登録されていない crate を指定するには、git や path で指定できます。 git のレポジトリに複数の crate が存在する場合には、左辺に依存する crate 名を指定すると、レポジトリ内から該当 crate を依存関係に追加できます。

# atsamd レポジトリ内の wio-terminal crate を依存に追加
wio-terminal = { git = "https://github.com/jessebraham/atsamd.git", branch = "wio-terminal" }

経緯

最近、Wio Terminal x Rust で遊んでいたところ、 Wio Terminal で使用している SoC の HAL crate を開発している atsamd レポジトリに Wio Terminal の BSP を追加するプルリクが出されました。

github.com

fork 先を clone して examples あたりにコードを追加すれば試せるのですが、Cargo.toml で fork 先から追加された wio-terminal crate だけ引っ張ってきてアプリケーション書けないかな、と考えました。

ちなみに、atsamd レポジトリには、各 SoC の PAC (Peripheral Access Crate) や、atsamd-hal crate、各ボードの BSP crate が集められています。

$ tree -L 2
.
├── boards
│   ├── arduino_mkrvidor4000
│   ├── arduino_mkrzero
│   ├── arduino_nano33iot
# ...
│   ├── trellis_m4
│   ├── trinket_m0
│   ├── wio_terminal  # fork 先のこれだけ持ってきたい
│   └── xiao_m0
├── hal
│   ├── Cargo.toml
│   ├── README.md
│   └── src
# ...
├── pac
│   ├── atsamd11c
│   ├── atsamd21e
# ...
│   ├── atsamd51p
│   ├── atsame54p
│   └── README.md
# ...
└── update.sh

Cargo.toml

atsamd レポジトリ内の atsamd51p crate と wio-terminal crate を引っ張ってきたい場合、次のように書くと意図通り動きました。

[dependencies]
atsamd51p = { git = "https://github.com/jessebraham/atsamd.git", branch = "wio-terminal" }
wio-terminal = { git = "https://github.com/jessebraham/atsamd.git", branch = "wio-terminal" }
panic-halt = "0.2"

解説

解説、というか、The Cargo Book を見ると書いてありました。

doc.rust-lang.org

Cargo will fetch the git repository at this location then look for a Cargo.toml for the requested crate anywhere inside the git repository (not necessarily at the root - for example, specifying a member crate name of a workspace and setting git to the repository containing the workspace).

ということで、fetch してきたレポジトリ内から、指定した Cargo.toml を一生懸命探してくれるようです (root ディレクトリに置いてある必要がなく、メンバー crate も指定できる) 。

Rust no-stdのasync完全理解を目指そう!

はじめに

この記事はRust Advent Calendar 2019の17日目として書きました。

組込みRust界の神japaricさんがno-std環境でasyncを使うPoCレポジトリを公開しています。

github.com

理解できるかどうか非常に自信がありませんが、これは見てみるしかありません!

後日正式な記事が書かれるそうなので、それを待ったほうが得策かもしれません!

引用の領域超えている気がしますので、一応ライセンス表記します。 今回解説するレポジトリは、MIT license、もしくは、Apache License, Version 2.0、でライセンスされています。

目次

自分なりのまとめ

  • 組込みのno-std環境で使えるasync-awaitのproof of conceptを紹介するよ (nightlyは必要だけどね!)
  • cooperativeスケジューラ (executor) は割り込みハンドラから完全に隔離するよ
  • なので割り込みハンドラで実行されるリアルタイム性が要求されるコードの予測性を損なわずに、cooperativeなコードを実行できるよ
  • そのために、executor#[global_allocator]とは違う専用のメモリアロケータを使うよ
  • 現在Rustのcollectionはglobal_allocatorを使うようにハードコーディングされているので、collectionを書き直す必要があるよ

つまるところ、async-awaitを使うと、リアルタイムタスクの最悪実行時間が計算しずらくなるため、割り込みコンテキストと完全に分離できるように、async-awaitno-std環境で使えるようにした、という話のようです。 現在のところ、no-std環境はCortex-Mに限定されています。

実装も覗いてみましたが、手続きマクロ以外は割と読めそうな感じです。

ツール

nightlyツールチェインと、Cortex-M3向けのクロスビルド環境が必要です。

$ rustup override set nightly
$ rustup update
$ rustup target add thumbv7-none-eabi

後、実行環境として、qemu-system-armを使います。

$ cargo run --example async-await --features="nightly"

README

まずなにはともあれ、プロジェクトのREADMEを見てみましょう。 と思ったらREADMEだけで1100行あるではありませんか! これは前途多難な予感です…。

Goal

Real Time For the Masses (RTFM) と一緒に使えるリアルタイムアプリケーション向けのcooperativeスケジューラを作ることが目標のようです。 cooperativeスケジューラは最悪実行時間の解析が難しくなります。

Background

Asynchronous code

皆さんご存知のようにRust 1.39 からasync / await の機能が安定化しました。

非同期コードはexecutorによって実行されることを意味します。 executorは標準ライブラリでは提供されていませんが、async-stdtokioといったマルチスレッドexecutor crateがあります。

async fnインスタンスtaskになり、executorがスケジューリング、実行します。

// toolchain: 1.39.0
// async-std = "1.2.0"

use async_std::task;

fn main() {
    // schedule one instance of task `foo` -- nothing is printed at this point
    task::spawn(foo());

    println!("start");
    // start task `bar` and drive it to completion
    // this puts the executor to work
    // it's implementation defined whether `foo` or `bar` runs first or
    // whether `foo` gets to run at all
    task::block_on(bar());
}

async fn foo() {
    println!("foo");
}

async fn bar() {
    println!("bar");
}
$ cargo run
start
foo
bar

サンプルコード内のコメントによると、タスクの実行順序はexecutorの実装依存なのですね。 勉強になります!

executorはタスクを協調的に実行します。 最も単純な場合、.awaitに到達するまでタスクを実行し、実行をブロックする必要がある場合はそのタスクをサスペンドし、別のタスクをresumeします。

Some implementation details

シンタックス的には、ジェネレータは、サスペンションポイント (yield) を含む、クロージャのような (|| { .. }) ものです。

// toolchain: nightly-2019-12-02

use core::{pin::Pin, ops::Generator};

fn main() {
    let mut g = || {
        println!("A");
        yield;
        println!("B");
        yield;
        println!("C");
    };

    let mut state = Pin::new(&mut g).resume();
    println!("{:?}", state);
    state = Pin::new(&mut g).resume();
    println!("{:?}", state);
    state = Pin::new(&mut g).resume();
    println!("{:?}", state);
}

セマンティクス的には、ジェネレータはyield間の状態マシンで、外部からresumeされることで状態遷移します。 ふむふむ。

executorは状態マシンのリストを持っていて、全ての状態マシンが完了になるまで、resumeし続けます。 各状態マシンは異なるサイズで違うコードを実行するので、トレイトオブジェクト (Box<dyn Generator>) としてリストされます。

これはサンプルコードを見ると理解しやすいです。

fn executor(mut tasks: Vec<Pin<Box<dyn Generator<Yield = (), Return = ()>>>>) {
    let mut n = tasks.len();
    while n != 0 {
        for i in (0..n).rev() {
            let state = tasks[i].as_mut().resume();
            if let GeneratorState::Complete(()) = state {
                tasks.swap_remove(i); // done; remove
            }
        }

        n = tasks.len();
    }
}

なるほど。タスク (状態マシン) をVec<Box<dyn Generator>>として受け取り、各タスクのresumeを呼ぶ。 状態が完了になると、Vecからswap_removeする、と。

Idea

アプローチとしては、非同期コードを#[idle]もしくはfn mainに隔離します。 その理由は

  • 協調的タスクには終了しないものと、短期間で終了するもがあるため、終了しない#[idle]タスクでexecutorを動かすのが賢明である
  • executorで必要となる動的メモリ確保は、#[idle]に制限されます。#[idle]内ではリアルタイムでないアロケータを使用し、通常のタスクは動的メモリ確保をしないようにします。アロケータを#[idle]内で排他的に使用することで、mutexなどの排他制御が不要になります。

ふむ、よくわからないので、もう少し先を見てみましょう。

Implementation

実装には2つのコンポーネントがあります。「スレッドモード」アロケータと「スレッドモード」executorです。 「スレッドモード」はARMの「スレッドモード」を意味しています。

アロケータとexecutorは、「スレッドモード」でのみ利用できます。 ARMの「ハンドラモード」ではアロケータとexecutorにアクセスできません。

「ハンドラモード」は主に割り込みや例外を処理するためのモードです。

Cortex-Mで、リセットハンドラは「スレッドモード」で実行されます。

RTFMアプリでは、#[init]#[idle]は「スレッドモード」で実行します。

TM (Thread-Mode) allocator

TMアロケータはseparate allocatorです。ん?どういうことでしょう? #[global_allocator]で定義されているものとは、独立アロケータです。ああ、そういうこと。

理想的には、RFC #1398で提案されているallocator-genericコレクションをAllocトレイトを通じて使えると良いのですが、Allocトレイトは安定化していませんし、allocator-genericコレクションは存在していません。

あー、なるほど。C++のようにカスタムアロケータが設定できるコレクションが提案されているのですね?(要確認) 今のコレクションは、#[global_allocator]を使うようにハードコーディングされています。

TMアロケータはstableで実装できますが、コレクションはそうではないようです。 Rcで使用するcore::intrinsics::abortがunstableであるなどの理由で。 stableではコレクションの型強制もできないようです。Box<impl Generator>は使えないため、Box<dyn Generator>を使います。

// toolchain: 1.39.0

use cortex_m_tm_alloc::allocator;
use tlsf::Tlsf;

#[allocator(lazy)]
static mut A: Tlsf = {
    // `MEMORY` is transformed into `&'static mut [u8; 64]`
    static mut MEMORY: [u8; 64] = [0; 64];

    let mut tlsf = Tlsf::new();
    tlsf.extend(MEMORY);
    tlsf
};

TMアロケータをAという名前で定義します。Aは実行時に[TLSF]アロケータを初期化します。

Aアロケータのハンドラはgetコンストラクタで取得します。 getコンストラクタは、Option<A>を返します。「スレッドモード」で呼び出すとSomeヴァリアントが、「ハンドラモード」で呼び出すとNoneが帰ります。 Aは、CopyAllocトレイトを実装したサイズ0の型です。SendSyncトレイトは実装していないため、インスタンスを割り込み / 例外ハンドラに渡すことができません。

な、なるほど…。

#[entry]
fn main() -> ! {
    hprintln!("before A::get()").ok();
    SCB::set_pendsv();

    if let Some(a) = A::get() {
        hprintln!("after A::get()").ok();
        SCB::set_pendsv();

        // ..
    } else {
        // UNREACHABLE
    }

    // ..
}

#[exception]
fn PendSV() {
    hprintln!("PendSV({:?})", A::get()).ok();
}
$ cargo run
before A::get()
PendSV(None)
after A::get()
PendSV(None)

PendSVハンドラ内では、A::get()してもNoneになっています。 #[entry]内では、Someヴァリアントが得られていますね(2回めのPendSVに突入していることから)。

if let Some(a) = A::get() {
    // ..

    let mut xs: Vec<i32, A> = Vec::new(a);

    for i in 0.. {
        xs.push(i);
        hprintln!("{:?}", xs).ok();
    }
}

一度アロケータインスタンスを取得すれば、コレクションの初期化時にアロケータのコピーを渡すことで、アロケータを使用できます。 アロケータはサイズ0の型なので、スタックサイズは増えません。

if let Some(a) = A::get() {
    // ..

    let mut xs: Vec<i32, A> = Vec::new(a);

    for i in 0.. {
        xs.push(i);
        hprintln!("{:?}", xs).ok();
    }
}

グローバルアロケータと同様に、TMアロケータもOut Of Memoryになる可能性があります。 その場合、#[oom]アトリビュートを使って定義されたOut Of Memoryハンドラが呼ばれます。

#[alloc_oom::oom]
fn oom(layout: Layout) -> ! {
    hprintln!("oom({:?})", layout).ok();
    debug::exit(debug::EXIT_FAILURE);
    loop {}
}
$ cargo run
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
oom(Layout { size_: 32, align_: 4 })

$ echo $?
1

TM (Thread-Mode) executor

TM executorはTMアロケータに依存しています。

// toolchain: nightly-2019-12-02

use cortex_m_tm_alloc::allocator;
use cortex_m_tm_executor::executor;

#[allocator(lazy)]
static mut A: Tlsf = { /* .. */ };

executor!(name = X, allocator = A);

TMアロケータ同様に、TM executorも「スレッドモード」のみでハンドラを取得できます。 getコンストラクタはTM executorとTMアロケータを返します。 TM executorもCopyトレイトを実装しますが、SendSyncは実装しません。

executorはタスクをspawnするのに使います。 spawnは、具体的なジェネレータを受け取り、Box化し、内部キューに格納します。 spawn自体は、ジェネレータ / タスクコードを実行しません! タスクを実行するにはblock_on APIを使います。

ふむ?とりあえずサンプルコードを見てみますか。

|> examples/tasks.rs

#[entry]
fn main() -> ! {
    if let Some((x, _a)) = X::get() {
        x.spawn(move || {
            hprintln!(" A0").ok();
            yield;

            hprintln!(" A1").ok();
            // but of course you can `spawn` a task from a spawned task
            x.spawn(|| {
                hprintln!("  C0").ok();
                yield;

                hprintln!("  C1").ok();
            });
            yield;

            hprintln!(" A2").ok();
            // NOTE return value will be discarded
            42
        });

        let ans = x.block_on(|| {
            hprintln!("B0").ok();
            yield;

            hprintln!("B1").ok();
            yield;

            hprintln!("B2").ok();
            yield;

            hprintln!("B3").ok();

            42
        });

        hprintln!("the answer is {}", ans).ok();
    }

    debug::exit(debug::EXIT_SUCCESS);

    loop {}
}

上記コードを実行した結果は、次のようになります。

$ cargo run --example tasks --features="nightly"
B0
 A0
B1
 A1
B2
  C0
 A2
B3
the answer is 42

もう一度サンプルコードに戻ってみると、下のジェネレータをexecutor Xspawnした時点では、まだ非同期コードは実行されません。

#[entry]
fn main() -> ! {
    if let Some((x, _a)) = X::get() {
        x.spawn(move || {
            hprintln!(" A0").ok();
            yield;

            hprintln!(" A1").ok();
            // but of course you can `spawn` a task from a spawned task
            x.spawn(|| {
                hprintln!("  C0").ok();
                yield;

                hprintln!("  C1").ok();
            });
            yield;

            hprintln!(" A2").ok();
            // NOTE return value will be discarded
            42
        });

続く、block_onでジェネレータが与えられると、実行を開始します。 B0出力後、yieldすると、先ほどspawnしたタスクに制御が移り、A0が出力されます。

        let ans = x.block_on(|| {
            hprintln!("B0").ok();
            yield;

            hprintln!("B1").ok();
            yield;

            hprintln!("B2").ok();
            yield;

            hprintln!("B3").ok();

            42
        });

        hprintln!("the answer is {}", ans).ok();
    }

A1ではさらにタスクをspawnしていますが、その時点では実行されておらず、B2出力後のyieldで制御が移ってきます。 C0後にyieldすると、A2を出力するコードに制御が移っていますね。

block_onで実行したジェネレータからは、戻り値 (42) を受け取っています。

でもC1が実行されていませんね?

そう、block_onはspawnしたタスク全てが完了になることを保証しません。 単に、引数で渡されたジェネレータが完了になるまで、実行を進めるだけです。

block_onをネストするとデッドロックする可能性があるため、TM executorではネストしたblock_on呼び出しはパニックになるよう、実装されています。

#[r#async] / r#await!

block_onをネストできないとすると、ジェネレータをどうやったら完了状態にできるのでしょうか? r#await!マクロを使います。ジェネレータを返す関数を簡単に書くために#[r#async]アトリビュートもあります。

例として、割り込みハンドラから非同期にデータを受け取りたいとします。#[r#async]を使って次のように書くことができます。 まずは、ジェネレータを簡単に書くためのアトリビュートです。

use core::ops::Generator;

use heapless::{
    spsc::Consumer, // consumer endpoint of a single-producer single-consumer queue
    ArrayLength,
};
use gen_async_await::r#async;

#[r#async]
fn dequeue<T, N>(mut c: Consumer<'static, T, N>) -> (T, Consumer<'static, T, N>)
where
    N: ArrayLength<T>,
{
    loop {
        if let Some(x) = c.dequeue() {
            break (x, c);
        }
        yield
    }
}

// OR you could have written this; both are equivalent
fn dequeue2<T, N>(
    mut c: Consumer<'static, T, N>,
) -> impl Generator<Yield = (), Return = (T, Consumer<'static, T, N>)>
where
    N: ArrayLength<T>,
{
    || loop {
        if let Some(x) = c.dequeue() {
            break (x, c);
        }
        yield
    }
}

dequeueはジェネレータを返す関数で、ジェネレータでは割り込みハンドラのProducerからデータが送られてくるとSomeになるから、そこで値を返して、yieldしています。 んー?ジェネレータが複雑な型になったりすると有り難いのかな…?

アプリケーションは次のように書けます。

#[entry]
fn main() -> ! {
    static mut Q: Queue<i32, consts::U4> = Queue(i::Queue::new());

    let (p, mut c) = Q.split();

    // send the producer to an interrupt handler
    send(p);

    if let Some((x, _a)) = X::get() {
        // task that asynchronously processes items produced by
        // the interrupt handler
        x.spawn(move || loop {
            let ret = r#await!(dequeue(c)); // <- ★
            let item = ret.0;
            c = ret.1;
            // do stuff with `item`
        });

        x.block_on(|| {
            // .. do something else ..
        });
    }

    debug::exit(debug::EXIT_SUCCESS);

    loop {}
}

うーん、難しい。dequeue(c)はジェネレータを返しているので、x.spawnの引数もジェネレータになると。

std_async::sync::Mutex?

std_asyncでは、2つのタスク間でメモリを共有したい場合、MutexRwLockを使います。 task::spawn APIの引数はSendトレイトを実装したジェネレータです。 std_asyncのジェネレータはマルチスレッドで動作し、並行実行される可能性があるからです。

use async_std::{sync::Mutex, task};

fn main() {
    let shared: &'static Mutex<u128> = Box::leak(Box::new(Mutex::new(0u128)));

    task::spawn(async move {
        let x = shared.lock().await;
        println!("{}", x);
    });

    task::block_on(async move {
        *shared.lock().await += 1;
    });
}

TM executorは必ず同じコンテキストで動作し、タスクは1つずつ順番に実行されます。 そのためspawnの引数はSendを実装する必要がありません。 そのため、タスク間でデータを共有する際、Mutexの代わりに、単にRefCellCellを使うことができます。

あ、そうですね。

use core::cell::RefCell;

#[entry]
fn main() -> ! {
    static mut SHARED: RefCell<u64> = RefCell::new(0);

    if let Some((x, _a)) = X::get() {
        let shared: &'static _ = SHARED;

        x.spawn(move || loop {
            hprintln!("{}", shared.borrow()).ok();
            yield;
        });

        x.block_on(move || {
            *shared.borrow_mut() += 1;
            yield;
            *shared.borrow_mut() += 1;
            yield;
        });
    }

    debug::exit(debug::EXIT_SUCCESS);

    loop {}
}

うん、これはよくわかる。

実装を覗いてみよう

さて、ここまでがREADMEです (長い…) 。

r#await! / #[r#async]

r#await!マクロは、わりと読めます。

|> gen-async-await/src/lib.rs

/// `e.await` -> `r#await(e)`
// expansion is equivalent to the desugaring of `($g).await` -- see
// rust-lang/rust/src/librustc/hir/lowering/expr.rs (Rust 1.39)
// XXX Does `$g` need to satisfy the `: Unpin` bound? -- I think not because `$g` is drived to
// completion so any self-referential borrow will be over by the time this macro returns control
// back to the caller. This is unlike `futures::select!` which partially polls its input futures.
// Those input futures may be moved around and then passed to a different `select!` call; the move
// can invalidate self-referential borrows so the input future must satisfy `Unpin`
#[macro_export]
macro_rules! r#await {
    ($g:expr) => {
        match $g {
            mut pinned => {
                use core::ops::Generator;
                loop {
                    match unsafe { core::pin::Pin::new_unchecked(&mut pinned).resume() } {
                        core::ops::GeneratorState::Yielded(()) => {}
                        core::ops::GeneratorState::Complete(x) => break x,
                    }
                    yield ()
                }
            }
        }
    };
}

ジェネレータのステートマシンに沿った動作をしているようです。

#[r#async]アトリビュートですが、修行をサボっていたせいで未だに手続きマクロがいまいち読めません! が、関数の戻り値型をimpl Generator型にし、関数内の処理をジェネレータにしているっぽいです。

/// `async fn foo() { .. }` -> `#[r#async] fn foo() { .. }`
// NOTE the built-in `async fn` desugars to a generator and wraps it in a newtype that makes it
// `!Unpin`; this is required because `async fn`s allow self-referential borrows (i.e. `let x = ..;
// let y = &x; f().await; use(y)`). AFAICT, self referential borrows are not possible in generators
// (as of 1.39) so I think we don't need the newtype
#[proc_macro_attribute]
pub fn r#async(args: TokenStream, item: TokenStream) -> TokenStream {
    if !args.is_empty() {
        return parse::Error::new(Span::call_site(), "`#[async]` attribute takes no arguments")
            .to_compile_error()
            .into();
    }

    // snip

    let block = &item.block;
    quote!(
        #(#attrs)*
        #vis fn #ident #generics (
            #inputs
        ) -> impl core::ops::Generator<Yield = (), Return = #output> #(+ #lts)*
        #where_clause
        {
            move || #block
        }
    )
    .into()

collections

初期化時に任意のアロケータが指定できるコレクションです。 例えばVecなら次のような感じです。

|> collections/src/vec.rs

pub struct Vec<T, A>
where
    A: Alloc,
{
    allocator: A,
    cap: usize,
    len: usize,
    ptr: Unique<T>,
}

impl<A, T> Vec<T, A>
where
    A: Alloc,
{
    // `new`で`Alloc`トレイトを実装するAを引数として渡す
    pub fn new(allocator: A) -> Self {
        let cap = if mem::size_of::<T>() == 0 {
            usize::max_value()
        } else {
            0
        };

        Self {
            allocator,
            cap,
            len: 0,
            ptr: Unique::empty(),
        }
    }
    // snip

cortex-m-tm-alloc

Cortex-Mのスレッドモードでのみ使用できる「スレッドモードアロケータ」です。 get()を呼んだ際、スレッドモードならアロケータインスタンスを、そうでなければNoneが得られるのでした。

Cortex-Mを知っていれば、実装は素直です。SCBのICSRの値を読み込んで、スレッドモードならSomeを、そうでなければNoneを返しています。

|> cortex-m-tm-alloc/src/lib.rs

    pub unsafe fn get() -> Option<Self> {
        if cfg!(not(cortex_m)) {
            return None;
        }

        const SCB_ICSR: *const u32 = 0xE000_ED04 as *const u32;

        if SCB_ICSR.read_volatile() as u8 == 0 {
            // Thread mode (i.e. not within an interrupt or exception handler)
            Some(Private {
                _not_send_or_sync: PhantomData,
            })
        } else {
            None
        }
    }

allocatorアトリビュートの実装は歯が立たなかったです。出直します。

cortex-m-tm-executor

Executorの実装を見てみます。

アロケータとタスク配列、実行中かどうかを示すフラグをフィールドに持ちます。

|> cortex-m-tm-executor

pub struct Executor<A>
where
    A: Alloc + Copy,
{
    allocator: A,
    /// Spawned tasks
    tasks: UnsafeCell<Vec<Pin<Task<A>>, A>>,
    running: Cell<bool>,
}

まず、spawnです。 タスクをヒープ領域に作って、タスク配列に追加するだけです。 なので、spawn()を呼んだだけではタスクが実行されなかったわけですね。

impl<A> Executor<A>
where
    A: Alloc + Copy,
{
    // snip
    pub fn spawn<T>(&self, g: impl Generator<Yield = (), Return = T> + 'static) {
        // this alternative to `GenDrop` produces larger heap allocations
        // let g = || drop(r#await!(g));
        let task: Task<A> = Box::new(GenDrop { g }, self.allocator);
        unsafe {
            (*self.tasks.get()).push(task.into());
        }
    }
}

一方、block_onでは、ジェネレータが完了状態になるまで、タスク配列内のタスクを単純に順番に実行していることがわかります。

    pub fn block_on<T>(&self, g: impl Generator<Yield = (), Return = T>) -> T {
        self.running.set(true);

        pin_mut!(g);

        loop {
            // move forward the main task `g`
            if let GeneratorState::Complete(x) = g.as_mut().resume() {
                self.running.set(false);
                break x;
            }

            let n = unsafe { (*self.tasks.get()).len() };
            for i in (0..n).rev() {
                let s = {
                    let task: TaskMut =
                        unsafe { (*self.tasks.get()).get_unchecked_mut(i).as_mut() };
                    task.resume()
                };

                if let GeneratorState::Complete(()) = s {
                    // task completed -- release memory
                    let task = unsafe { (*self.tasks.get()).swap_remove(i) };
                    drop(task);
                }
            }
        }
    }

ジェネレータの実装について少し。 結果を破棄するGenDropジェネレータが実装されています。 resumeするとGeneratorStateが返ります。

GeneratorState::Completeになると、値をdrop()していることがわかります。

impl<G> Generator for GenDrop<G>
where
    G: Generator<Yield = ()>,
{
    type Yield = ();
    type Return = ();

    fn resume(self: Pin<&mut Self>) -> GeneratorState<(), ()> {
        match G::resume(self.g()) {
            GeneratorState::Yielded(()) => GeneratorState::Yielded(()),
            GeneratorState::Complete(x) => {
                drop(x);
                GeneratorState::Complete(())
            }
        }
    }
}

終わりに

完全に理解できなかったァ…。 とは言え、かなり理解は深まりました。

ただ、アプリケーションはともかく、実行エンジン作るのは、かなり大変そうですね…。

技術書典7でRustが関連する本/サークル一覧メモ

はじめに

随時、更新します。抜けや、間違いがあればご連絡下さい。

techbookfest.org

既刊ですが、私も「組込み/ベアメタルRustクックブック」を頒布しますので、よろしくお願いします(宣伝)。

新刊

い35C: esproject(エスプロジェクト)

techbookfest.org

く54D: OtakuAssembly

techbookfest.org

RustでOSやコンテナをネタにした内容が含まれるそうです。

け04D: ヤバイテックトーキョー

techbookfest.org

Writing a (micro)kernel in Rust in 12 days - 2.5th day - by nullpo-head 「Rustでマイクロカーネル書くやつのつづきやります」

こ31D: 井山梃子歴史館

techbookfest.org

Rustを用いてゲームエンジンを作ります.近年話題のEntity Component Systemがどのように実装されるのかを見ていき,またRustでどのようにグラフィックを扱えばよいのかを解説します.

こ32D: Team Jackalope

techbookfest.org

RustではじめるOpenGLSDL + OpenGL + Dear ImGuiによるGUIアプリ。

し41D: ふがふが(フガフガ)

techbookfest.org

  • M5Stackではじめる組み込みRust
  • 【委託】SePIA timers本

Rustの低レイヤ部分に興味がある人

せ34D: 肉と鍋(ニクトナベ)

techbookfest.org

既刊

VxWorksの脆弱性「URGENT11」のテクニカルホワイトペーパーを読む①

はじめに

7月末にVxWorks脆弱性発見が公開されました。

armis.com

日本語関連記事

VxWorksは組込み機器では非常に有名なRTOSで、20億以上のデバイスに搭載されています。 今回の脆弱性URGENT11で影響を受けるデバイスは2億個以上であると報告されています。

脆弱性を報告したARMISが公開している上のページでは、医療機器やルータで任意コードを実行するエクスプロイトデモ動画が掲載されています。

URGENT11では11個の脆弱性が報告されています。Wind Riverセキュリティアドバイザリによると、その中の3つは、CVEのレーティングが9.8と非常に脅威度が高いものとなっています。

URGENT11 テクニカルホワイトペーパー

本記事では、ARMISが公開している脆弱性のテクニカルホワイトペーパーを読み、自分なりにまとめてみます。 今回は、レーティングが9.8のもののうち、リモート (LAN内) から任意コード実行が可能なCVE-2019-12256Stack overflow in the parsing of IPv4 packets’ IP optionsに関する部分を読んでみます。

ホワイトペーパーに掲載されているコードスニペットでは一部解析できない部分があり、コードスニペットの解析では、一部推測が混じっています。

最終的には、「C言語で安全なコード書くの大変!」というお話になります。 ZenやRustのような配列 (またはスライス) が配列要素数情報を持っている言語であれば、(少なくとも)DoSまでは脅威度が下げられたように見えます。

URGETN11のホワイトペーパーではスタックオーバーフローと記載されていますが、スタックバッファオーバーフローなのではないかと疑っています。記事内では元のホワイトペーパーのままスタックオーバーフローとしています。

URGETN11

過去に発見されたTCP/IPスタックの脆弱性と同様のものが、ソースコードがクローズドなRTOSにもないかどうか、を研究しています。 研究にあたっては、ダウンロード可能なファームウェア (デバッグ情報付きのELF) を逆コンパイルしている、とあります。

概要

複数のSRR (Source Record Route) オプションを含む不正なIPパケットを送信すると、攻撃者が意図的にスタックオーバーフローを起こすことができ、任意コードが実行できます。これは適切な長さチェックを行わずに、SRRオプションをスタック上に確保したバッファにコピーすることに起因しています。

バックグラウンド情報

SRR (Source Record Route)

ja.wikipedia.org

ソース・ルーティングとは、ネットワーク通信において、データの送信者が送信先のみでなく中継地点をも指定する経路制御方式のことである。

通ってきたルート情報をオプション内に記録していきます。オプションヘッダが3バイトあり、その後ろに、通ってきたルートのIPv4アドレスが記録されます。

記録できるルート情報は最大9件です。IPv4のオプションフィールドが (固定部分を除き) 最大で40バイトなので、オプションヘッダ (3バイト) + ルート情報 (4バイト×9 = 36バイト) まで、ということなのでしょう。

ICMPエラーパケット

IPパケットを処理している間にエラー状態になった場合 (不正なIPパケットを受け取った場合) 、ICMPエラーパケットを返信します。この場合、不正なIPパケットとは、送信先に到達できないパケットである不正なオプションフィールドを含んでいる、などが挙げられます。

ICMPエラーパケットには、不正なIPパケットのコピーが含まれる場合が多いです。

はい、嫌な予感がしますね!

脆弱性

1つのIPパケットに複数のSRRオプションが含まれている状態は、エラーとして検出されます。しかし、脆弱性のあるVxWorksの不正IPパケット検出ロジックでは、そのエラーを検出する前に別のエラーを検出した場合、複数のSRRオプションが含まれていることを認識しないまま、不正IPパケットをコピーしてICMPエラーパケットを作成します。

ICMPエラーパケットとして確保されているオプションフィールドは、スタックに確保されている40バイトです。この領域に対して、最大で40バイトの大きさになるSRRオプションを複数回コピーしてしまい、スタックオーバーフローが発生します。

コード

ファームウェアのバイナリから逆コンパイルしたコードスニペットがホワイトペーパー内に掲載されています。

不正なIPパケットを受け取った場合、下のipnet_icmp4_send関数からICMPエラーパケットを送信します。

int ipnet_icmp4_send(Ipnet_icmp_param *icmp_param, Ip_bool is_igmp)
{
    Ipnet_icmp_param *icmp_param;
    Ipcom_pkt *failing_pkt;
    struct Ipnet_copyopts_param options_to_copy;
    // スタックに確保された40バイトの配列
    struct Ipnet_ip4_sock_opts opts;
    // ...
    // 問題のオプションをコピーする関数を呼び出す
    ipnet_icmp4_copyopts(icmp_param, &options_to_copy, &opts, &ip4_info);
    // ...
}

Ipnet_ip4_sock_opts構造体の定義が掲載されていないので詳細は不明ですが、ホワイトペーパー内では、これは40バイトの配列である、と解説されています。

int ipnet_icmp4_copyopts(Ipnet_icmp_param *icmp_param,
                         struct Ipnet_copyopts_param *copyopts_param,
                         struct Ipnet_ip4_sock_opts *opts, void *ip4_info)
{
// ...
    while ( 1 ) {
        current_opt = ipnet_ip4_get_ip_opt_next( /* ... */ );
        // ...
            if ( opt_type == 0x83 || opt_type == 0x89 ) {
                // IPオプションがSRR (LSRRもしくはSSRR)
                srr_ptr_offset = 39;
                srr_opt = (srr_opt_t *)&opts->opts[opts->len];
                // ポインタオフセットは最大で39バイト目までしか指さないようにしているが、
                // このオフセットが現在のオプション内で有効であるかどうか、は検証されていない
                if ( (int)current_opt[2] <= 39 )
                    srr_ptr_offset = current_opt[2];
                offset_to_current_route_entry = srr_ptr_offset - 5;
                // ...
                // オプション内に記録されているIPアドレスを逆順に1つずつコピーする。
                while ( offset_to_current_route_entry > 0 ) {
                    memcpy((char *)srr_opt + srr_opt->length, current_route_entry, 4);
                    current_route_entry -= 4;
                    offset_to_current_route_entry -= 4;
                    srr_opt->length += 4;
                }
                // 最新 (自身) のルート情報を追加する
                memcpy((char *)srr_opt + srr_opt->length, &icmp_param->to, 4);
                srr_opt->length += 4;
                total_opts_len = opts->len + srr_opt->length;
            }
        }
    }
...
}

SRRオプションは次のデータ構造になっており、lengthはオプションのバイト数で、pointerroute dataのオフセットです (オプション開始位置から数えるので、4から始まります) 。pointer (コード中のsrr_ptr_offset) はlength以下でなければならないはずですが、上記コードではそれがチェックされていません。

Loose Source and Record Route
+--------+--------+--------+---------//--------+
|    0x83| length | pointer| route data |
+--------+--------+--------+---------//--------+

脆弱性をつくには、次のようなIPオプションフィールドを送信します。

type length pointer type length pointer
0x83 3 0x27 (39) 0x83 3 0x27 (39)

これでルート情報が欠落しているLSRRオプションが2連続で続くことになります。実際にはルート情報はありませんが、pointer0x27 (39)を指しているので、9番目のルート情報が格納されている位置から逆順に、ルート情報をコピーしようとします

このとき、コピー先はmemcpy((char *)srr_opt + srr_opt->length, current_route_entry, 4);から、srr_optです。srr_optは、40バイトの配列であるoptsどこかを指すポインタです。opts->lenを更新するコードが掲載されていないのですが、一番外側のwhileループが回るごとにオプションの長さ分加算されていると推測できます。

srr_opt = (srr_opt_t *)&opts->opts[opts->len];

上述の脆弱性をつくオプションフィールドをwhile文で1つずつ処理し、2つ目のオプションを処理する際には、opts->len340になっていると考えられます (オプションフィールドのlengthで更新していれば3、コピーしたオプションフィールドの長さで更新していれば40) 。そこを起点に、40バイトしか確保していない領域に、さらに最大で40バイトのコピーが発生します。

ここでコピーされる内容は、オプションフィールドに続く任意のデータです

ということで、上位に戻って、ipnet_icmp4_sendoptsを突き抜けてデータを書き込まれ、スタック上のリターンアドレスが、書き込まれた任意コードの先頭アドレスに書き変われば攻撃成功、なはずです。

int ipnet_icmp4_send(Ipnet_icmp_param *icmp_param, Ip_bool is_igmp)
{
    Ipnet_icmp_param *icmp_param;
    Ipcom_pkt *failing_pkt;
    struct Ipnet_copyopts_param options_to_copy;
    // スタックに確保された40バイトの配列
    struct Ipnet_ip4_sock_opts opts;

新しいプログラミング言語なら?

一番の直接的な問題点は、pointerオフセットが有効なlengthの範囲内であるかどうか検証していないこと、でしょう。ここはロジックレベルの実装ミスであり、プログラミング言語レベルでは防ぎようがありません。

int ipnet_icmp4_copyopts( /* ... */ )
{
// ...
                srr_ptr_offset = 39;
                srr_opt = (srr_opt_t *)&opts->opts[opts->len];
                // ポインタオフセットは最大で39バイト目までしか指さないようにしているが、
                // このオフセットが現在のオプション内であるかどうか、は検証されていない
                if ( (int)current_opt[2] <= 39 )
                    srr_ptr_offset = current_opt[2];

最終防衛線は、optsが確保しているメモリの範囲外アクセスを検出することです。

// ...
                srr_opt = (srr_opt_t *)&opts->opts[opts->len];
// ...
                    memcpy((char *)srr_opt + srr_opt->length, current_route_entry, 4);
// ...

ZenやRustのような言語であれば、opts->optssrr_opt配列要素数を型の一部として持つ配列 (へのポインタ) 、もしくは、スライスになります。このような言語であればopts->opts[opts->len]で範囲外アクセスを行った場合や、スライスのコピー操作により範囲外アクセスを防ぐことが可能です。

どちらの言語でもunsafeC言語のmemcpyと同等のコピー関数がありますが、そのような関数を使うと、もちろんC言語と同じ結果になります。

次のコードは、かなり問題を単純化した例をZenで書いたものです。

const std = @import("std");

fn copy_opts(opts: *[]u8) void {
    const length: usize = 38;
    // `opts`の38番目から42番目の要素を指すスライスを取得して、書き換えようとする
    var entry = opts.*[length..length + 4];
    std.mem.copy(u8, entry, [_]u8{ 1, 2, 3, 4 });
}

pub fn main() void {
    var opts: [40]u8 = [_]u8{0} ** 40;
    copy_opts(&opts[0..]);
}

このコードは、パニックで停止します。copy_opts関数の引数optsが40個の要素しか持たないことがわかっているため、それを超える範囲のスライスを作ろうとすると、実行時にパニックが発生します。

index out of bounds
main.zen:5:23: 0x2250b6 in copy_opts (main)
    var entry = opts.*[length..length + 4];
                      ^

お次はRustで書いたものです。

fn copy_opts(opts: &mut [u8]) {
    let length: usize = 38;
    // `opts`の38番目から42番目の要素を指すスライスを取得して、書き換えようとする
    let entry = &mut opts[length..length+4];
    entry.copy_from_slice(&[1, 2, 3, 4]);
}

fn main() {
    let mut opts: [u8; 40] = [0; 40];
    copy_opts(&mut opts);
}

このコードも、パニックで停止します。

thread 'main' panicked at 'index 42 out of range for slice of length 40', src/libcore/slice/mod.rs:2555:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

パニック発生時にパニックを捕捉してハンドリングすることも可能です。

マルウェアを送り込まれた上で動作し続けることに比べると、システムが定義されたパニック状態に陥る方が、かなり被害が軽減できるでしょう。 このような最終防衛線がプログラミング言語レベルで用意されていることが、いかに大切かわかりますね!

技書博出展レポート〜初めての同人誌執筆で組込みRustの本を頒布しました〜

はじめに

記憶の新しいうちに、経緯などをまとめておきます。 自分用メモの側面が強いですが、今後初めて同人誌を頒布される方の参考になると嬉しいです。

f:id:tomo-wait-for-it-yuki:20190721132625p:plain
表紙

BOOTHで物理本と電子版を販売しているので、もし良ければお買い求め下さい。 (物理本は倉庫への搬送作業は完了しており、入荷待ちです)

sabizen.booth.pm

経緯

4月下旬、@hidemi_ishihara さんから出展のお誘いがありました。

組込みRustで書くことに決めて、今まで翻訳した組込みRustのドキュメントや、自分でこれまでやってきたことをクックブックとしてまとめることにしました。 クックブックにしたのは理由があり、急に執筆ができなくなっても読める内容になっている形式で執筆を進めたかったからです。 第二子の出産予定日が6月初旬だったため、この判断は良かったと思います。

性格的にギリギリにやるのは性分ではないこともあり、手持ちで書籍化できそうなものが、組込みRustかZephyrしかなかった、というのもありますが。 (Zephyrはそこまで思い入れないですからねぇ…)

執筆の進行

gitの履歴を見てみると、4/29にレポジトリを作っていました。 2週間後の5月中盤には、頒布した内容の半分は書けています。 この頃は、平日は1時間前後、休日は2〜3時間執筆していました。

ここまでは順調でしたが、まさかの第二子が3週間早く産まれてきてしまう、というハプニングに見舞われます! ガクッと執筆ペースが落ちて、残り半分の内容を埋めるのに6週間ほどかかっています。 この頃は、平日30分時間が取れれば良い方で、休日も2時間執筆できれば万々歳でした…。

7月に入り、組版作業に入ることを決めました。 この時点で、まだ書きたかった内容を全て切り捨てました。

初めてなので、どのくらい製本すれば良いかわかりませんでした。 とりあえずtwitterランドの住人に聞いたろ、ということで、聞いてみると、100イイねついたので、100冊刷ることにしました。

製本をどこに頼もうか調べていたところ、@hidemi_ishihara さんから、いつもポプルスさんで印刷している、という情報を得ました。 調べる時間がもったいないので、「じゃあ、そこで!」ということにして、早速アカウント作って見積もりと製本予約をしました。

ということで、組版作業を都合2週間ほどやっていました。 こんなに時間がかかったのは少し理由があって、mdbookというRust製のドキュメントビルダーで原稿を執筆していました。 mdbookには未完成品ですがEPUB形式で出力する機能があります。 mdbookから出力されたEPUB形式の原稿を、calibreという電子書籍エディタで編集していました。

慣れないCSSをいじったり、なぜかPDF出力するときにコードブロックの強調が消えてしまうバグと不毛な争いをしていました。 ということで、2週間前に組版を始めたのも、良い判断でした。

表紙作成もこの辺りの期間にやりました。 割と面倒で、時間かかりました。

7/12には入稿を済ませて、一段落つきました。

当日まで

不安しかねぇ!

というのも、初めての同人誌執筆(厳密にはD論という名の同人誌製本していますが)で会場直接搬入なので、実物が読めたものになっているかどうか、わかりません!

当初より今回の本は、組込みRustの知名度向上のため、価格を安くしてばら撒く作戦でした。 さらにmdbookは静的なページを作るツールなので、HTML版も合わせて配れば、安いし誰も怒らないでしょ!みたいな開き直りをすることで、心の安寧を保ちました。

その裏で、名刺を自炊したり、ダウンロードカード作ったりしていました。

後、twitterやブログで必死の宣伝活動していました。 どこかの記事で、技書博は集客1000人を目指している、と聞いて、来場者の10%もこんなニッチな本を買うわけがない!という焦りがありましたね。

値段は500円にしたので、とりあえず500円玉を30枚、お釣りとして用意しました。

当日

とにかく本のできを見て、一安心しました。 これなら500円でも怒られはしないでしょ!というクオリティになっていました。 少し上下左右の余白取りすぎた気がしますが、文字が詰まっている圧迫感も感じないので、悪くない気がします。 読者の皆様からの感想をお待ちしております。

@hidemi_ishihara さんに導かれるまま、見本誌にカバーかけたり、スペースの準備をしました。 カッターナイフも何度かお借りしました。カッターナイフ、意外と要るで?

午前中は、全然売れなかったです! 11時〜12時の間の売上は3冊でした。 内心すごい焦燥感に駆られていました。

イベント自体は、ゆっくりスペースを回れて、著者とお話しする余裕が十分にあるので、良い感じだなぁ、と思いました。 物が売れない焦燥感を除けば!

13時以降、徐々に売上が伸びていき、14時〜15時くらいの間に20冊近く販売できました。 最終的には、53冊頒布しました。

一般入場者が640名ほどとのことなので、このニッチなジャンルで53冊はだいぶ頑張った方ではないでしょうか笑 ゆっくり見れたり、話した結果ご購入下さった方もいらっしゃったので、購入する側としても満足度が高かったのかもしれません。

中には、「Rustはやったことないのだけど、気になるし、安いから買います(意訳)」という方や「Rust勉強してからまた来ます」、と言って下さった方も複数名いらっしゃったので、狙いは良かったと思います。

頒布時間終了後、40冊はBOOTHさんに入庫することにしました。 スーツケース持ってきておけば、持って帰って技術書典7で頒布できたなぁ、と思いましたが、後の祭りですね。 荷物軽くするために、リュック1つで行ったのが間違いでした…。

技術書典7では、また50冊くらい刷ることにします。

お金の話

100冊製本して、約37,500円でした。 ばらまきたいので、1冊500円で頒布することにしました。

現状、BOOTHでの売上も含めて、なんとか損益分岐点に到達しました! お買上げ、ありがとうございます! Boostまでして下さる方もいらっしゃって、非常にありがたいことです。

今回は、赤字にさえならなければ勝ちなので、満足です!

今後について

HTML版は、適宜更新していこうと考えています。 時間不足でバッサリ切ってしまった部分が残っているので、そちらの加筆も行う予定です。 組版はぼちぼち手間がかかるので、PDF版および紙版の更新は余裕があれば、やります。

読者の皆様からフィードバックがあれば、加筆修正する大きなモチベーションになるため、フィードバックをお待ちしております。

7/27(土) 技書博で組込み/ベアメタルRustクックブックを販売します!

はじめに

宣伝です!

来週開催される技術書同人誌博覧会にて、組込み/ベアメタルRustクックブックを販売します。 A-9 AQUAXISさんのブースにご一緒させて頂きます。 ブース主の石原ひでみさんはFPGAの薄い本とMarkdown組版の本を、みつきんさんはNuttxの本を頒布されます。

f:id:tomo-wait-for-it-yuki:20190721132625p:plain
表紙

販売情報

価格は、500円です。 PDF版とHTML版がデフォルトで含まれます。 当日の会場にてお買い上げいただくと、先着で100名様に、紙媒体をお渡しします。 1冊のご購入につき、紙媒体を1冊まで、お渡しします。

当日お越し頂けなかった方にも、後日何らかの形でPDF版とHTML版が入手できる手段を用意します。

目次は、次の通りで、表紙込で78ページです。

  • はじめに
  • 環境構築
  • ベアメタルテクニック
    • no_std
    • panic
    • print!マクロ
    • リンカ
    • アセンブリ
    • メモリアロケータ
    • entryポイント
  • ツール
  • ライブラリ / フレームワーク
    • heapless
    • no_stdクレート
    • svd2rust
    • RTFM
    • Tock
    • testing
  • FFI
  • 組込みLinux
    • ビルド/テスト
    • Yocto
  • あとがき

正直なところ、HTML版が一番見やすいので、HTML版に500円払う気持ちで購入して頂けると嬉しいです。

ところで

100イイねついたから、100部刷ったので、買って下さいね!(切実)

LLVM IRファイルを読み込む

はじめに

ファイルに出力されたLLVM IRをC++で読み込んで遊んでみます。

環境

$ clang++ --version
clang version 8.0.1-svn360950-1~exp1~20190517004233.70 (branches/release_80)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
$ llvm-config --cxxflags --ldflags --system-libs --libs core
-I/usr/lib/llvm-8/include -std=c++11  -fno-exceptions -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS
-L/usr/lib/llvm-8/lib 
-lLLVM-8

LLVM IRファイルの読み込み

アプリケーションの引数にLLVM IRファイルパスを指定する想定です。

#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IRReader/IRReader.h>
#include <llvm/Support/SourceMgr.h>

int main(int argc, char** argv) {
    if (argc < 2) {
        llvm::errs() << "Expected an argument - IR file name\n";
        exit(1);
    }

    llvm::LLVMContext Context;
    llvm::SMDiagnostic Err;
    auto module = llvm::parseIRFile(argv[1], Err, Context);

    if (!module) {
        Err.print(argv[0], llvm::errs());
        return 1;
    }

    return 0;
}

llvm::parseIRFileに、ファイルパスを与えるだけで、llvm::Module (のunique_ptr) を得ることができます。

下のコマンドでLLVM IRファイルが読み込めます。

clang++ main.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o ir_reader
./ir_reader main.ll

少し内部を覗く

main.llにはmain関数があり、いくつか命令があります。 そのオペコードを表示してみます。

次のようなコードで実現できました。

    auto func = module->getFunction("main");
    std::cout << "function name: " << func->getName().data() << std::endl;
    for (auto &bb: *func) {
        auto i = 0;
        for (auto &instr: bb) {
            std::cout << "%" << i << ": " << instr.getOpcodeName() << std::endl;
            i++;
        }
    }
$ ./ir_reader main.ll 
function name: main
%0: alloca
%1: bitcast
%2: call
%3: getelementptr
%4: load
%5: call
%6: ret

お手軽ですね!