Rustで組込みプログラミングや自作OS作成をするには

「Rustで始める自作組込みOS入門」という本というかドキュメントの公開を始めました。

はじめに - Rustで始める自作組込みOS入門

これは以前からつくっていたErkOSという自作OSでの経験を元にして、どうやったらRustで自作組込みOSの最初の一歩を踏み出せるか、というものをドキュメントにしたものです。
このドキュメントはこの前の技術書展の告知が来たあたりから構想を練っていて、すきま時間にちまちまと書き進めていたものですが、とりあえず、プロセスの切り替えっぽいところまでの説明を終えることができたので公開しました。

組込みでRustをやる話や自作OSを書く話というのは先駆者がたくさんいて、僕自身もそれらの資料を参考にしつつ書き進めて来ました。
一応、それらの既存のものとは差別化はしているつもりではあるものの、既存のものを完全に上回るというものではないです。内容もまだまだ足りない。

以前、RustでOSを書くプロジェクトもろもろでいくつかOSを書く際に参考になりそうなプロジェクトをまとめましたが、情報も古くなってきたので、改めて参考になるプロジェクトを紹介していきたいと思います。

Redox

Redox - Your Next(Gen) OS - Redox - Your Next(Gen) OS
The Redox official website

RustでデスクトップOSを書くというプロジェクト。完成度はかなり高く、GUIツールなどもすべてRustで書き直す、とかなり本格的。
最近のブログポストによると実際のハードウェアで動くための課題はかなりクリアできているようで、
今はコンパイラそのものを改良してRedox上でRedoxをビルドすることを目指しているらしい。

このRedoxプロジェクトから派生したクレートも役に立つものが多い

Tock

Tock Embedded Operating System
Tock is a safe, multitasking operating system for low-power, low-memory microcontrollers.

Rustで書かれたCortex-M向けの組込みOS。SOSPで論文を出していいたりとOSそのもの構造も興味深い。
かつてはRustコンパイラに手を加えたりするものが主流でしたが、このTockはnightlyコンパイラだけでコンパイルできるのも特徴。

最近、Googleが発表したOpenSKというUSBのセキュリティキーのオープンな実装を発表したが、そこで使われているのもこのTockです。

Rust Embeddedグループ

GitHub - rust-embedded/wg: Coordination repository of the embedded devices Working Group
Coordination repository of the embedded devices Working Group - GitHub - rust-embedded/wg: Coordination repository of the embedded devices W…

Rustにはいくつかの公式ワーキンググループがあって、そのうちの１つがこのEmbeddedワーキンググループです。
各種ドキュメントや組込み開発で使えるクレートを公開しています。
主にCortex-MやCortex-A、RISC-Vをターゲットにしています。

The Embedonomiconは一からベアメタルプログラミングするための手引になっていてとても参考になります。

RaspberryPiを使ったOS開発のチュートリアルはGICv2にも対応しているようなので、Cortex-Aで自作OSしたい人は参考になるかもしれません。

OS開発ということにフォーカスしているわけではないですが、個々のコンポーネントを書く際はかなり参考になります。

Rust OSDev

Rust OSDev
Operating System Development in Rust. Rust OSDev has 26 repositories available. Follow their code on GitHub.

非公式グループですが、OSを書く、ということに焦点を置いたグループです。
こちらはx86系のアーキテクチャをたーゲットにしています。

UEFIのアプリケーションを書くのに便利なuefiクレートなど、x86系の自作OSに役立つクレートを多く出しています。

特にこのグループのメンバーの一人であるPhilippさんの自作OSブログは内容が充実していて、自作OSでのテストの書き方やヒープアロケータのデザインと実装といった他のアーキテクチャでも使える項目の解説も充実しています。

Writing an OS in Rust
This blog series creates a small operating system in the Rust programming language. Each post is a small tutorial and includes all needed co…

日本語の資料

今まで紹介したものはほとんどが英語のものでしたが、日本語のリソースとして@LDScellさんがEmbeddedグループのドキュメントの和訳を公開している他、
「組込み/ベアメタルRustクックブック」という資料を公開しています。

組込み/ベアメタルRustクックブック（電子版） - emb-sabi - BOOTH
こちらで公開している内容と同じものです。 https://tomoyuki-nakabayashi.github.io/embedded-rust-techniques/ Rustを組込みで使うためのテクニック集です。 HTML版での閲覧をお勧めしています。HTML版を開くには、…

論文紹介：Firecracker: Lightweight Virtualization for Serverless Applications

元論文：https://www.usenix.org/conference/nsdi20/presentation/agache

2018年末、AWS Lambdaを提供するためのシステムとしてFirecrackerという仮想マシンモニター（VMM）がオープンソースとして公開されて注目を集めました。

Firecracker – サーバーレスコンピューティングのための軽量な仮想化機能 | Amazon Web Services
私の好きなAmazonリーダーシッププリンシプルの1つはCustomer Obsessionです。 私たちがA […]

この論文は、その中身を解説・評価する論文です。

論文概要

USENIX協会主催のNSDIで発表されました。
USENIXはもともとはUnix User Groupという団体でしたが、現在はシステムやネットワーク、セキュリティなどの会議やワークショップを開催しています。
そのなかでもNSDIはネットワーク系の会議としてトップクラスの会議の１つです。
書いている人たちはAWSの中の人のようです。

AWS Lambdaとは、いわゆるサーバーレスコンピューティングといわれるサービスで、イベントの発生ごとに実行されるアプリケーションを設定しておくと、サーバーの設定無しでアプリケーションを実行して応答を返してくれる、というものです。
このアプリケーションを動かすのに使われているフレームワークで使われているのがFirecrackerです。

この論文ではFirecrackerのことをVMMと呼んでいますが、KVMやXenのような「VMM」ではありません。これはちょっと私も混乱したポイントなのですが、ここでのVMMとは各ゲストOSに対してのサンドボックスを提供するためのコンポーネントというような位置づけです。
KVMとQEMUの組み合わせでは、QEMUがこのVMMに相当します。
このブログではVMMをこの論文の使い方にそうように使いますが、私は普段はVMMという言葉をXenやKVMのようなフレームワークに対して使っている（ハイパーバイザと同義の意味で使っている）ので、他の記事とは使い方が異なることに注意してください。
ちなみにFirecrackerはRust製です。

背景・動機

AWS Lambdaをつくるにあたり、以下のような性質を持つ仮想化フレームワークが必要とされました

  • 独立性：複数の関数が同一のハードウェアで走ってもセキュアであること（互いに干渉したり、権限昇格のようなことが起きない）
  • オーバーヘッドと密度：たくさんの関数が同一ハードウェアで動かせるよう、少ないオーバーヘッドで動かせること
  • パフォーマンス：ネイティブ実行に近い速度が出せること
  • コンパチビリティ：任意のLinuxバイナリやライブラリがコード変更や再コンパイルなしで動かせること
  • 高速な切り替え：古い関数実行をクリーンアップし、新しい関数を実行が素早く行えること
  • ソフトアロケーション：CPUやメモリのオーバーコミットが可能なように、関数は必要なリソースしか使わないようにする

現状の類似した独立した環境を提供する既存のものとして、コンテナ・仮想化・言語のVMを使った独立化を挙げています。
Dockerでお馴染みのコンテナは、seccomp-bpfでシステムコールを制限するという形でセキュリティを担保してますが、200を超えるLinuxのシステムコールを制御しなければならず、Linuxのシステムコールのバグの危険性もあります。
Xenなどを使ったハードウェア仮想化は、ゲストOSに完全独立な仮想のCPUを与えるという方法ですが、カーネルまるまるを使うとスタートアップの時間がかかり、メモリのオーバーヘッドも大きいため、密度を上げることが難しいことで知られています。
また、仮想化のフレームワークそのもののコード量が多いことも問題です（trusted computing base、すなわちTCBが大きい）。
Java Virtual Machine（JVM）などの言語のVMは、言語や機能が限定されるため、これも条件を満たしません。

そこで、Firecrackerの取る方法は仮想化のアプローチをベースとしたものになっています。
有名なKVMとQEMUを使った仮想化ではQEMUが非常にコードの大きな部分を占めていて、これを減らすことができればTCBも減らすことができます。
FirecrackerではこのQEMUを置き換えるというものになっています。

Firecrackの構造

Firecrackerの設計方針として、既存のモジュールを再実装するのは基本的に避け、できる限りLinux内のコンポーネントを利用するというものがあります。
これは実装コストを下げるというのと、サービスを運用する際、Linuxの知識がそのまま使えるというものがあります。

FirecrackerはKVMのインフラに乗っかりつつ、QEMUに変わるVMMとして実装し、その上で小さな仮想マシン（MicroVM）を動かすという設計になっています。
VMMはChrome OSのVMMであるcrossvmをベースにコードを削ったりリファクタリングして、現在は完全に別物として実装されています。

Firecrackerはデバイスとして、ネットワークやディスクなどのブロックデバイス、シリアルポートとi8042（PS/2キーボードコントローラ）のみをサポートしています。
このうち、ネットワークドライバとブロックデバイスドライバはvirtioをそのまま使うことでコスト削減に貢献しています

Firecrackerのプロセスを操作するインターフェースとしてREST APIを提供しています。これなら様々な言語から操作することが用意で、それこそcurlなどのコマンドラインツールでも操作可能になるからです。

各VMの独立性を保つためには、プロセスごとのレートリミットをつける必要があります。Firecrackerでは1秒ごとのオペレーション数をAPIから設定することができます。

セキュリティのためのJailerというものも実装されています。これはFirecrackerそのものが使えるインターフェースを制限し、ゲストがVMMの脆弱性をつくことを難しくするためのものです。

評価

大量のVMを走らせるという実験を、QEMUと最近Intelが発表したRust製VMMであるCloud Hypervisorとの比較をおこなっています。

まず、起動時間です。QEMUよりかはパフォーマンスがいいのですが、Cloud Hypervisorには若干劣ります。一方で、メモリのオーバーヘッドはFirecrackerが3MB程度なのに対して、Cloud Hypervisorが13MBなので、こちらはFirecrackerに軍配が上がります。
次にIO性能ですが、実装がいろいろ足りていないため、QEMUにも負けている部分がいろいろあるようです。

さて、はじめに掲げた目標は達成できているでしょうか？

  • 独立性：仮想化を用い、サイドチャネルの対策もした
  • オーバーヘッドと密度：大量のVMを低いオーバーヘッドで動かせることを確認した
  • パフォーマンス：改善の余地はあるが、十分なパフォーマンスを達成
  • コンパチビリティ：変更していないLinuxカーネルを動かせた
  • 高速な切り替え：起動時間が十分に短い
  • ソフトアロケーション：20倍のオーバーサブスクリプションをテストしたが問題なし

ということで、全部満たしていそうです。

感想

仮想化フレームワークとしてUnikernelを以前紹介したが、こちらはよりコンパチビリティを意識したアプローチになっていている一方、きちんとVMの密度を上げられているというのは面白いと思いました。
KVMのフレームワークに詳しくなくVMMという単語の使い方に困惑しましたが、調べてみると結構こういう意味で使っている場合が多いようでややこしいですね…っｇ

Rustでコマンドラインツールを開発する

コマンドラインツールをつくる際、今まではPythonやRubyなどのスクリプト言語をつかうことが多かった。
スクリプト言語はコンパイルする必要がなく、普通のシェルスクリプトよりかは書きやすいし、外部のライブラリも組込みやすい。
Java・ScalaなどのJVM系言語はC言語系よりかは書きやすいが、JVMの起動の時間が気になってしまいあまり向いていないように思われる。

しかしながら、スクリプト言語での開発にも問題はある。
動的に型がついて危ない、というのは小さくなりがちなちょっとしたツールでは比較的無視しやすいのでいいとする。
一番厄介なのは、実行環境のバージョン違いである。特にプロセス呼び出しで、同じ言語の他のツールを呼び出したりすると突然エラーを吐いたりすることがあった。

この前、社内でコマンドラインツールを書く機会があり、試しにRustで書いてみることにした。
一度コンパイルしてしまいバイナリにしてしまえば、バージョンの違いに苦しむことはないであろう。
変更のたびコンパイルする必要があるとはいえ、一度コンパイルさえしてしまえば高速に動作する。
実はRustの公式ワーキンググループの中にコマンドラインインターフェース（CLI）のためのチームがあり、ドキュメント・ライブラリが整備されている。

Command-line interfaces (CLI) working group
A language empowering everyone to build reliable and efficient software.

ドキュメントは優秀で、コマンドライン引数の処理やエラーハンドリングなどでどういうクレートを使えばいいかを紹介してくれている。

Getting started - Command Line Applications in Rust

特にstructoptをつかったコマンドライン引数の処理は非常に簡単。シリアライズでお馴染みのserdeみたいに構造体にアトリビュートをつけていくと、コマンドライン引数を構造体に簡単に落とし込める。ヘルプメッセージなども簡単につくれるし、サブコマンドの定義なども柔軟に対応可能。

変更のたびコンパイルする手間であるが、cargo runコマンドを使うことである程度緩和できる。cargo runは変更がない限りは特にはコンパイル処理を行わないのでオーバーヘッドは小さい。
ただし、生で叩くのは面倒なので、以下のようなシェルスクリプトのラッパーを経由して呼び出すことにした。

1
2
3
4
script_path=$(readlink -f "$0")
manifest_path="$(dirname "$script_path")/Cargo.toml"

RUSTFLAGS=-Awarnings cargo run -q --release --manifest-path=$manifest_path -- "$@"

RUSTFLAGSはコンパイル時の警告を消すためにつけている。これをプロジェクトのルートディレクトリにおいておき、このスクリプトへのシンボリックリンクをパスの通っているところに配置すればコマンドラインから簡単に実行できる。
初回時のみ無言でコンパイルを行うが、その後はインクリメンタルにビルドしてくれるので、無言の期間は比較的短くてすむはずである。
もちろん、このようなスクリプトを使わずともバイナリのシンボリックリンクを置くとかでもよいが、そこはお好みで。

Rustで循環参照を含むグラフをArc/Rcを使ってつくる

Rustで循環参照を含む場合の処理はかなり面倒くさい。
基本的にミュータブルな参照は同時に1つしか持てないのだが、例えば双方向連結リストの場合、あるノードに対してその前のノードとその後ろのノードから参照される必要があるので、この場合どうにかしてミュータブルな参照以外の方法で前後のノードへのアクセス方法を確保する必要がある。

ということで、前回のRust LT会でそのテーマで発表した方がいらっしゃった

Graph in Rust with unsafe
- Rust でグラフ構造むずかしい… - 試行錯誤の過程を書きました - unsafe 使いましたが、unsafe こわい - メモリープールを実装してみました - ヤバいところあったら教えて！

ここで用いられている方法はunsafeを使い、生ポインタとTyped Arenaという動的に同じ生存区間のメモリを確保できるライブラリを使う、または自作のメモリプールを使うというものである。
しかし、できればunsafeは使いたくない。さらにいうとstdだけで実現できると嬉しい。

Typed Arenaを使う方法は結構有名で、こちらのブログでも紹介されている

Rustでグラフを表現するにはTyped Arenaが便利 - 簡潔なQ
概要: Rustでグラフのように相互参照を含むデータ構造を表現するには、Typed Arenaという方法が適している。これについて説明する 整数による表現 グラフの表現方法で、最も簡単なのは、ノードを整数で表し、グラフのデータを別に持つ方法である。 fn main() { let…

ただし、この方法の弱点はメモリを開放する手段がないので、一度ノードをつくってしまうとグラフ全体が生存している間は削除してもメモリが開放されない。
ライフタイムの管理も難しく、設計をうまくしてあげる必要もある。

他の方法としてはRc/Arcを使う方法がある。

Rustの `Arc` を読む(1): Arc/Rcの基本 - Qiita
概要: Rustの Arc 型の実装は宝の宝庫です。そこで、これを隅から隅まで解説してみます。 第1回「Arc/Rcの基本」では、実際に Arc のソースを読む前に Arc/Rc の使い方を解説します。 第1回 Arc/Rcの...

Rcは参照カウンタ付きのスマートポインタでArcはそのスレッド安全版である。この方法ではRc/Arcのアクセスのための実行時オーバーヘッドおよび参照カウンタ分のメモリオーバーヘッドが発生するが、
代わりにライフタイムは比較的自由に管理でき、ノードのメモリも参照がなくなると自動的に開放してくれる。

注意点としてはRustはメモリリークに関しての保証はないため、Rcで循環参照をつくってしまうとメモリリークを起こすことになる。
そのため、ノード間の連結は弱参照Weakで実現し、ノード全体の強参照を保持する親構造体を持つことで、この問題を解決する。
この場合、ノードのコンストラクタは直接呼ぶのではなく、親構造体のメソッド呼び出しとして実態をもらうことになる。
また、ノード内部構造は晒したくないので、ユーザーが触るノード構造体の実態はノード内部構造体への弱参照のラッパになる。

弱参照から内部の値にアクセスするのは失敗する可能性があるので、ノードのメソッドは常にResult型で返してあげる必要がある。
また、ノード内部になんらかの値を保持させる場合、そこへのアクセスも少々厄介になる。
今回は、内部値への直接の参照を返すことは諦め、代わりにクロージャーを渡してもらうことにより、内部値の読み込み及び変更を実現した。
実際の実装は以下の通りである。先述のqnighy氏のブログにあった実装をベースにして、ノードの削除、子要素の取得、内部値の読み書きを追加したものである。
Arcを使っているのでスレッド安全でもある。

synchronous graph
synchronous graph. GitHub Gist: instantly share code, notes, and snippets.

削除や値の読み書きに対応するために変更した点について説明していく。
ノードの削除はGraphの持っている強参照を削除しないとメモリが開放されないため、Graphのメソッドとして実装した。
強参照がVecのどこに格納されているかを指定するため、NodeInnerに位置を持っておき、それをもとに削除することにした。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pub fn remove_node(&self, node: &Node<T>) -> Result<(), GraphError> {
    let mut lock = self.0.lock().unwrap();
    let rc = node.0.upgrade().ok_or(GraphError::NodeDead)?;
    let id = rc.lock().unwrap().id;
    if id < lock.nodes.len() {
        let tar_node = lock.nodes[id].0.take();
        if tar_node.is_none() {
            Err(GraphError::InvalidNode)
        } else {
            lock.nodes[id].1 = lock.next;
            lock.next = id;
            Ok(())
        }
    } else {
        Err(GraphError::InvalidNode)
    }
}

Vecから特定の要素を削除するのはそこそこにめんどくさく、またそれにより他のノードのインデックスがずれると困るので、強参照をもつVecはOption型で値を持っておき、削除された場合はNoneに置き換えることにした。

1
2
3
4
5
6
7
8
#[derive(Debug, Clone)]
struct GraphInner<T> {
    nodes: Vec<(Option<Arc<Mutex<NodeInner<T>>>>, usize)>,
    next: usize,
}

#[derive(Debug, Clone)]
pub struct Graph<T>(Arc<Mutex<GraphInner<T>>>);

削除が頻繁に起こるとVecがNoneで埋め尽くされてしまうので、Noneになった箇所は再利用できるようにした。そのために、グラフには次のNoneの位置を持たせておき、各ノードにはその次のNoneの位置をもたせることで、
Noneの連結リストを構成することで要素の再利用を行うようにしている。VecにNoneが存在しない場合、末尾に要素を追加する。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pub fn new_node(&self, value: T) -> Node<T> {
    let mut lock = self.0.lock().unwrap();
    let next = lock.next;
    let inner = NodeInner {
        value,
        neighbors: Vec::new(),
        id: next,
    };
    
    let node = Arc::new(Mutex::new(inner));
    if next < lock.nodes.len() {
        let node_weak = Node(Arc::downgrade(&node));
        lock.nodes[next].0.replace(node.clone());
        lock.next = lock.nodes[next].1;
        node_weak
    } else {
        let node_weak = Node(Arc::downgrade(&node));
        lock.nodes.push((Some(node.clone()), next + 1));
        lock.next += 1;
        node_weak
    }
}

ただし、あくまで強参照用の要素の再利用であって、ノードそのもののメモリ領域の再利用はしていないので、メモリ効率は改善の余地があると思われる。

ノードの値の読み書きであるがArcやMutexで囲われているので、そのまま参照を返すことはできない。
そこで、内部値の参照を受け取って処理をする関数をもらう、というメソッドをつくっておくことにした。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn read<V, F>(&self, f: F) -> Result<V, GraphError> where F: Fn(&T) -> V {
    let rc = self.0.upgrade().ok_or(GraphError::NodeDead)?;
    let lock = rc.lock().or(Err(GraphError::LockFailure))?;
    let result = f(&lock.value);
    Ok(result)
}

pub fn write(&self, val: T) -> Result<(), GraphError> {
    let rc = self.0.upgrade().ok_or(GraphError::NodeDead)?;
    let mut lock = rc.lock().or(Err(GraphError::LockFailure))?;
    lock.value = val;
    Ok(())
}

pub fn modify<F>(&self, f: F) -> Result<(), GraphError> where F: Fn(&mut T) {
    let rc = self.0.upgrade().ok_or(GraphError::NodeDead)?;
    let mut lock = rc.lock().or(Err(GraphError::LockFailure))?;
    f(&mut lock.value);
    Ok(())
}

注意点としては、渡す関数中で同一ノードへのアクセスを試みると、Mutexが衝突してデッドロックないしLockFailureが返ってしまう。
Nodeはノードの実態への弱参照であるため、複製が可能であるためにコンパイルそのものは通ってしまう。
また、弱参照であるために、削除されたノードである可能性が常に存在するため、すべてのメソッドはResult型で返ってくる。

弱点・TODO

強参照は1つしかないため、ノードの実態のメモリリークはないが、Arcの参照カウンタのための領域は弱参照が残り続けている限り開放されない。
ノード削除の際、他のノードとの連結情報までは削除をおこなっていないため、連結情報としてその弱参照は生き続ける可能性があるし、そもそもNode型自体は複製可能なので、別の箇所で弱参照が生き続けることもありえる。
一応、ノードの子要素の無効な弱参照は適宜消してあげる関数はつくっておいたが、どこで呼び出すかが問題となる。

また、異なるGraphのノードを識別できていないため、remove_nodeに別のグラフのノードを渡してあげることで挙動がおかしくなる危険性がある。
対策としてはノードになんらかのGraphの識別子をもたせ、それをチェックすることになると思われる（GraphInnerへの弱参照とか？）。

あとは、隣接ノード情報周りは作り込みが甘いので、もうちょっとなんとかしたい。

また、スレッド安全性を捨てればArcがRcになり、Mutexも取れるので実行時オーバーヘッドがマシになると思われるので、そのバージョンもつくってみたい。
あと、オーバーヘッドがどうのとか言っているが、ちゃんとパフォーマンス計測はしていないので、他のバージョンもつくってやってみたい。

進捗ダメです。

X11環境でIMEの仮入力の情報を取得する

LinuxのX11向けのGUIアプリケーションでテキスト入力を扱いたい場合、IMEの存在を意識しなければならない（特に日本人ならば）。
IMEなしならば、キーボードイベントを見て、そのキーのアルファベットをプリントするだけで済むが、IMEが存在する場合、IMEから送られてくる文字列をきちんと処理する必要がある。
そのためには、X11のIMEフレームワークであるXIMの仕様を知る必要がある。

これらの仕様について解説し、実際のコードも紹介している記事はすでにある。

A Brief Intro to Input Method Framework, Linux IME, and XIM | EKG<T>

上記の記事を参考にしたと思われる日本語の記事もある。

XIM(X Input Method)日本語入力の流れ - Qiita
2018年3月 作成 「X Window Systemの日本語入力はどうなっているんだろう？」 そう考えた筆者が、日本語入力の流れを調べてみました。 　C言語、X11プログラミングに関する文章です。 　使用OS:ubuntu16.0...

しかし、実はこれらの記事ではIME内で確定した文字列の情報しか取得しておらず、IME内でまだ確定していない仮入力状態の文字列（例えば変換前の元のひらがな）は取得できていない。
仮入力の文字列を取得できていないと、それらの文字列は当然描画できないし、例えば変換前の文字列を使った入力補完なんかも実装できない。
ある程度ちゃんとしたX11アプリケーションではこれらがちゃんとできていることからも想像がつく通り、XIMではこれらの状態を渡すインターフェースがある。

先述のブログのコードのうち、IMとの通信のためのコンテキスト構造体であるXICをつくっているところを見てみよう。

1
2
3
4
5
XIC ic = XCreateIC(xim,
                    /* the following are in attr, val format, terminated by NULL */
                    XNInputStyle, XIMPreeditNothing | XIMStatusNothing,
                    XNClientWindow, win,
                    NULL);

XNInputStyleの値としてXIMPreeditNothing | XIMStatusNothingを指定している。このXIMPreeditNothingというところが仮入力状態をどう扱いたいかをしてするものである。
XIMPreeditNothingは仮入力状態を渡すことなく動いてしまう。そのため、代わりにXIMPreeditCallbackを指定しなければならない。
このオプションを使う場合、クライアント側に仮入力の状態が変化した際のコールバックをXNPreeditAttributesとして渡してあげる必要がある。
コールバックにはXNPreeditStartCallback、XNPreeditDoneCallback、XNPreeditDrawCallback、XNPreeditCaretCallbackの4つがある。

  • XNPreeditStartCallback: 仮入力がスタートしたときに呼ばれる
  • XNPreeditDoneCallback: 仮入力が終了したときに呼ばれる
  • XNPreeditDrawCallback: 仮入力状態の文字が更新されたときに呼ばれる。呼び出されたときに変化した文字列の情報が渡されてくる。
  • XNPreeditCaretCallback: 入力カーソルの位置が変わったときに呼ばれる。呼び出されたときに入力カーソルの位置の変化情報が渡されてくる。

これらをXVaNestedList型としてXNPreeditAttributesとしてXCreateICに渡す必要がある。各コールバックはXIMCallback構造体へのポインタとして定義される必要がある。
XIMCallback構造体の定義は以下の通りである。

1
2
3
4
typedef struct {
    XPointer client_data;
    XIMProc callback;
} XIMCallback;

XPointerはchar *、つまり汎用のポインタで、XIMProcの定義は

1
2
3
4
5
typedef void (*XIMProc)(
    XIM,
    XPointer,
    XPointer
);

となっている。第一引数はXIM型となっているが、こちらのドキュメントではXIC型となっている。どちらが正しいかわからないが、今回はこれは使わないのでスルー。
第二引数はXIMCallbackのclient_dataが渡されてきて、第三引数にはコールバックの種類によって必要な情報がサーバー側から送られてくる（以後、call_dataと呼ぶ）。XPointer型を適宜キャストして使うことになる。

XNPreeditStartCallbackではcall_dataにはNULLが渡されてくる。XIMProc型の関数の返り値はvoidとなっているが、実際はこのコールバックは仮入力文字列の長さの上限を返さなければならない。-1とした場合、上限はない。
今回はこのように定義する。

1
2
3
4
5
6
7
8
9
static int preedit_start_callback(
    XIM xim,
    XPointer client_data,
    XPointer call_data)
{
    printf("preedit start\n");
    // no length limit
    return -1;
}

XNPreeditDoneCallbackもcall_dataはNULLが渡されてくる。今回は仮入力中の文字列を出力したいだけなので、特に何もしないでいいだろう。

1
2
3
4
5
6
7
static void preedit_done_callback(
    XIM xim,
    XPointer client_data,
    XPointer call_data)
{
    printf("preedit done\n");
}

XNPreeditDrawCallbackが仮入力文字列に変化が起きた場合の処理である。call_dataはXIMPreeditDrawCallbackStruct構造体として渡されてくる。

1
2
3
4
5
6
typedef struct _XIMPreeditDrawCallbackStruct {
    int caret;		/* Cursor offset within pre-edit string */
    int chg_first;	/* Starting change position */
    int chg_length;	/* Length of the change in character count */
    XIMText *text;
} XIMPreeditDrawCallbackStruct;

仮入力中のすべての文字が渡されてくるのではなく、変化した文字列の情報が渡されてくる。
chg_firstからchg_length文字数分がtextに変化したという感じである。
ただし、筆者の環境のIMEはchg_firstに常に0が渡されて、textに仮入力中の文字全部が渡されるような動作をした。
しかし、仕様の上では一部しか渡されてこない可能性もあるので、一応注意して実装する。
なお、文字数のカウントはバイト数ではなく、システムの文字コード（通常はUTF-8のはず）で解釈した場合の文字の数であることに注意。

XIMText型として文字列の情報が渡されてくる

1
2
3
4
5
6
7
8
9
typedef struct _XIMText {
    unsigned short length;
    XIMFeedback *feedback;
    Bool encoding_is_wchar;
    union {
	char *multi_byte;
	wchar_t *wide_char;
    } string;
} XIMText;

encode_is_wcharのとき、wide_charとして文字列が来るが、今回はmulti_byteで来る場合のみ扱う（gtkでも対応していない）。
lengthはここでもバイト数ではなく、実際の文字の数である。
XIMFeedbackは各文字の装飾に関する情報だが、今回は割愛する。
なお、textはNULLになる場合があり、それはchg_firstからchg_lengthまでの文字が削除されたことを意味する。
C言語にはマルチバイト文字をいい感じに扱うライブラリがないため、真面目に仮入力中の文字すべてを正しく把握しようとすると結構面倒そうなので、今回は来た情報だけを標準出力に吐くだけにしておく

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void preedit_draw_callback(
    XIM xim,
    XPointer client_data,
    XIMPreeditDrawCallbackStruct *call_data)
{

    printf("callback\n");
    XIMText *xim_text = call_data->text;
    if (xim_text != NULL)
    {
        printf("Draw callback string: %s, length: %d, first: %d, caret: %d\n", xim_text->string.multi_byte, call_data->chg_length, call_data->chg_first, call_data->caret);
    }
    else
    {
        printf("Draw callback string: (DELETED), length: %d, first: %d, caret: %d\n", call_data->chg_length, call_data->chg_first, call_data->caret);
    }
}

最後のXNPreeditCaretCallbackはcall_dataとして以下のような構造体として情報が来る。

1
2
3
4
5
typedef struct _XIMPreeditCaretCallbackStruct {
    int position;		 /* Caret offset within pre-edit string */
    XIMCaretDirection direction; /* Caret moves direction */
    XIMCaretStyle style;	 /* Feedback of the caret */
} XIMPreeditCaretCallbackStruct;

カーソルのポジションと移動した方向、カーソルの表示の際の装飾情報が渡されてくる。文字列は変化していないので、文字列に関する情報はない。
以下のようなコールバック関数を定義しておく。

1
2
3
4
5
6
7
8
9
10
11
static void preedit_caret_callback(
    XIM xim,
    XPointer client_data,
    XIMPreeditCaretCallbackStruct *call_data)
{
    printf("preedit caret\n");
    if (call_data != NULL)
    {
        printf("direction: %d position: %d\n", call_data->direction, call_data->position);
    }
}

さて、これらをXICをつくるときのパラメータとして渡すために、XVaNestedListとして渡すには以下のようにする。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
XIMCallback draw_callback;
draw_callback.client_data = NULL;
draw_callback.callback = (XIMProc)preedit_draw_callback;
XIMCallback start_callback;
start_callback.client_data = NULL;
start_callback.callback = (XIMProc)preedit_start_callback;
XIMCallback done_callback;
done_callback.client_data = NULL;
done_callback.callback = (XIMProc)preedit_done_callback;
XIMCallback caret_callback;
caret_callback.client_data = NULL;
caret_callback.callback = (XIMProc)preedit_caret_callback;
XVaNestedList preedit_attributes = XVaCreateNestedList(
    0,
    XNPreeditStartCallback, &start_callback,
    XNPreeditDoneCallback, &done_callback,
    XNPreeditDrawCallback, &draw_callback,
    XNPreeditCaretCallback, &caret_callback,
    NULL);

今回はclient_dataを使わないので、NULLを渡しておいた。ポインタで渡しているだけなので、XIMCallbackがXICの生存中にちゃんと生きていなければならないことには注意
そして、XICをつくる部分のコードを以下のように書き換える。

1
2
3
4
5
XIC ic = XCreateIC(xim,
                   XNInputStyle, XIMPreeditCallbacks | XIMStatusNothing,
                   XNClientWindow, win,
                   XNPreeditAttributes, preedit_attributes,
                   NULL);

完成品はこちら

Example code to use preedit callbacks in XIM
Example code to use preedit callbacks in XIM. GitHub Gist: instantly share code, notes, and snippets.

実行例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
preedit start
callback
Draw callback string: あ, length: 0, first: 0, caret: 1
callback
Draw callback string: あい, length: 1, first: 0, caret: 2
callback
Draw callback string: あいう, length: 2, first: 0, caret: 3
callback
Draw callback string: あいうえ, length: 3, first: 0, caret: 4
callback
Draw callback string: あいうえお, length: 4, first: 0, caret: 5
delievered string: あいうえお
callback
Draw callback string: (DELETED), length: 5, first: 0, caret: 0
preedit done
preedit start
callback
Draw callback string: お, length: 0, first: 0, caret: 1
callback
Draw callback string: おｎ, length: 1, first: 0, caret: 2
callback
Draw callback string: おの, length: 2, first: 0, caret: 2
callback
Draw callback string: おのｒ, length: 2, first: 0, caret: 3
callback
Draw callback string: おのれ, length: 3, first: 0, caret: 3
callback
Draw callback string: おのれｎ, length: 3, first: 0, caret: 4
callback
Draw callback string: おのれの, length: 4, first: 0, caret: 4
callback
Draw callback string: おのれのｆ, length: 4, first: 0, caret: 5
callback
Draw callback string: おのれのふ, length: 5, first: 0, caret: 5
callback
Draw callback string: おのれのふｇ, length: 5, first: 0, caret: 6
callback
Draw callback string: おのれのふが, length: 6, first: 0, caret: 6
callback
Draw callback string: おのれのふがｋ, length: 6, first: 0, caret: 7
callback
Draw callback string: おのれのふがく, length: 7, first: 0, caret: 7
callback
Draw callback string: おのれのふがくｗ, length: 7, first: 0, caret: 8
callback
Draw callback string: おのれのふがくを, length: 8, first: 0, caret: 8
callback
Draw callback string: 己の富嶽を, length: 8, first: 0, caret: 0
callback
Draw callback string: 己の富嶽を, length: 5, first: 0, caret: 2
callback
Draw callback string: 己の富嶽を, length: 5, first: 0, caret: 0
callback
Draw callback string: おのれの富嶽を, length: 5, first: 0, caret: 0
callback
Draw callback string: 己の富嶽を, length: 7, first: 0, caret: 0
callback
Draw callback string: 己の富嶽を, length: 5, first: 0, caret: 2
callback
Draw callback string: 己の富岳を, length: 5, first: 0, caret: 2
callback
Draw callback string: 己のフガクを, length: 5, first: 0, caret: 2
callback
Draw callback string: 己の不学を, length: 6, first: 0, caret: 2
delievered string: 己の不学を
callback
Draw callback string: (DELETED), length: 5, first: 0, caret: 0
preedit done

リファレンス

一応、以上の仕様は以下のドキュメントにあるのだが、かなり古く読みにくい

概念的な話はこちら。正直、読み方がわからなかった

The Input Method Protocol
This specifies a protocol between IM library and IM (Input Method) Server for internationalized text input, which is indepedent from any spe…

こっちはXlibの実装の解説ではあるが、レイアウトがメチャクチャである

Xlib − C Language X Interface

結局GTKの実装を参照するほうが楽であったが、GTK4（まだリリースはされていない）の最新版ではなんとXIMのサポートが削除されている。

Remove the XIM input method (!1195) · Merge requests · GNOME / gtk · GitLab
It's old and busted, and mostly broken in weird ways when it comes to extended input devices. All that XIM does, these days, is make a mess …

GTK3までならちゃんと生きているので、そちらを参考にすると良い

modules/input/gtkimcontextxim.c · 3.24.13 · GNOME / gtk · GitLab
GTK is a multi-platform toolkit for creating graphical user interfaces.

論文紹介：Efficient scalable thread-safety-violation detection: finding thousands of concurrency bugs during testing

元論文: https://dl.acm.org/doi/10.1145/3341301.3359638

並行システムをテストし、スレッド安全性の違反を効率よく見つけるという論文です。
並行システムの検証・テストというトピック自体はかなり有名で様々な方法がすでに提唱はされています。
しかし、この論文のポイントは実際のMicrosoft製品のビルドシステムの過程にこのテストシステムを実際に組込み、いくつものバグをちゃんと発見した、というところです。

論文概要

このブログではおなじみのシステム系論文のトップカンファレンスSOSPで発表されたものです。
SOSPではこのような検証やバグ発見のようなどうやったら安全なシステムを構築できるかのようなセクションがあり、こういうタイプの論文も一定数あります。
筆頭著者のGuanpu Li氏はシカゴ大学所属で、Microsoft Researchとカルフォルニア大学の方々も著者に含まれています。

この論文では、TSVD（Thread-Safety-Violation Detector）という並行システムのバグ発見システムを提案しています。
並行システムはバグ発見や再現が難しいことが知られていて、並行システムの安全性検証・テストは古くからあるテーマです。
しかし、並行システムは状態数が多い・様々な並行化モデルが存在しているなどの理由から、実製品できちんと用いるというのは難しいというのが多くの既存手法の抱える問題でした。
TSVDのすごいところはMicrosoftの実際の製品のビルドシステムに統合し、ちゃんといくつものバグを発見できたところです。

動機・目的

TSVDはテスト実行の際に適当な遅延を埋め込むことでデータ競合を実際に発生させることで、動的にバグを見つけるというのが大まかな仕組みです。
データ競合を検出すると、その命令までのスタックトレースを出力します。
似たような手法は存在しているのですが、TSVDは現実世界のアプリケーションのビルドに組み込んで使えるように様々な工夫をし、パフォーマンスを高めています。
また、実際に競合を発生させることで検出するので、false-positiveは原則起こらないという特徴もあります。

TSVDでは並行システムのバグの内、Thread-safety violationの発見に特化しています。Thread-safety violationとは、要はデータ競合で、並列にアクセスされることが想定されていないデータ構造に同時にアクセスすることで起きる不整合です。
この論文では複数のスレッドから並行に呼び出すことのできるメソッド以外のメソッド呼び出しを指します。
この論文では例としてKey-ValueストアのためのDictionaryクラスへの追加と読み込みを同時に行うことを上げています。
Dictionaryクラスが２分探索木のようなデータ構造で実装されている場合、読み込みをしている途中で追加処理によって現在探索中のノードの枝が変化するなどされれば、本来見つかるはずのノードに辿り着けない、といったことです。
これはデータ競合の全てのケース、というわけではないですが、このように対象を限定することがハイパフォーマンスの理由のひとつになってます。

データ競合の検出手法として広く知られているもののひとつとしてHappen-Before（HB）分析というものがあります。
これは全ての同期命令を集めて、実際にどの命令が並行に実行される可能性があるかというものを分析するものです。
しかし、forkやjoinが頻繁に行われる場合、状態数が爆発し、また先行研究ではjoinするタイミングに制約があるなど、広く用いるには難しいという問題があります。

アルゴリズム

まず、データ競合の起こりうるメソッド呼び出し（TSVD pointsと呼んでいる）を静的解析で列挙し、これを特殊なcall命令に置き換えます。
この命令はスレッドID、オブジェクトID、メソッドIDをもとに、このメソッド呼び出しにディレイを必要に応じて差し込み、データ競合の検出もおこないます（別スレッドから同一オブジェクトに対して同時にメソッド呼び出しが発生し、かつどちらかが書き込み命令だった場合は競合とみなす）。
単なるメソッド呼び出し自体は相当数あり、そこにランダムに遅延を発生させるだけではデータ競合を発見させるのは難しいです。
そこで、TSVDはデータ競合が発生しそうな箇所を絞り込み、効率よく遅延を差し込むような工夫をしています。

まず、データ競合になりうるメッソド呼び出しが近い時間で行われた箇所を危険と判断します。
つまり、異なるスレッドから同じオブジェクトへのアクセスが一定時間内に行われたかを調べ、その2箇所をdangerous pairとして管理します。

また、これらのdangerous pairは並列に実行されないとデータ競合は起きません。そのため、各TSVD pointsについて、これらの実行履歴を一定数持っておき、それらの中に異なるスレッドからの実行が存在する場合、そのTSVD pointは並列に実行されていると判断します。
dangerous pairの内片方が並行実行されている場合、遅延を差し込むようにします。

dangerous pairのすべてがデータ競合を起こす訳ではないので、これを更に絞り込む必要があります。
まず、Happen-before（HB）関係、つまり片方の命令はもう片方の命令より常に先に実行される関係を推論するといことで絞り込みます。
ある同一オブジェクトの実行履歴に注目し、dangerous pair(loc1, loc2)が以下を満たす場合、HB関係にあるとみなしてリストから除外します。

  1. loc1の直前に遅延が差し込まれた
  2. loc2のスレッド上で過去同一オブジェクトへのメソッド実行を行った箇所loc0が存在する
  3. loc0の終了時間はloc1前に差し込まれた遅延の終了時間より前である
  4. 上記の条件を満たす遅延が一定回数以上存在している

また、各pair毎にprobabilityを設定しておき、遅延を挟むごとにprobabilityを下げる、とすることで、同一箇所に過剰に遅延を設定するということを防ぎます。

これらの遅延挿入アルゴリズムはテストを実行しながら同時に実行できる、というのがポイントのひとつです。
これにより、遅延挿入箇所の決定のための独立したテスト実行は不要なので、テスト時間の短縮になります。
もちろん、複数回テストを実行させ、前回のテスト情報を次回に引き継ぐこともできます。

実装については、.NETアプリケーション（C#やF#のプログラム）に限定されますが、理論的には他のタイプのアプリケーションにも使えるとしています。
また、実装はGithub上で公開されています。

GitHub - microsoft/TSVD: TSVD is a tool for quickly finding thread-safety violations (e.g., data races) in .NET applications.
TSVD is a tool for quickly finding thread-safety violations (e.g., data races) in .NET applications. - GitHub - microsoft/TSVD: TSVD is a to…

評価

1,657のMicrosoftで実際に開発しているアプリケーションのビルドプロセスに組込み、1,134箇所のバグを発見できたとしています。
false-positiveは存在しなく、いくつかのバグは実際のプロダクション環境で問題を引き起こしているものであったとしています。

これらのバグの見つかったアプリケーションの内1000のモジュールとスモールベンチマークを用いて、他の手法とのパフォーマンスの比較も行っています。
実行時のオーバーヘッドは平均で33％ほどで、既存手法と比べてもかなり少なく、発見できたバグの数も上でした。

この手法にはいくつかチューニングすべきパラメータが存在します（dangerous pairを決めるための間隔、HB関係を決定させるための回数など）。
これらについても、各パラメータとそれを増減させた際のバグ検出数とそのオーバーヘッドを調べて分析しています。

まとめ・感想

TSVDというMicrosoftの製品から並行実行時のデータ競合を検出した手法の紹介をしました。

実は以前、並行プログラムのバグを検出するというテーマで研究していた時期があって、それだけに興味深い論文でした。
この手の話はどちらかというと綺麗なモデルを組んで論理的に検証する話が多く、それが故に制約も多く、実世界に持ち出すという話はあまり見ることがありませんでした。
論文全体的にあまり難しい論理の話はないのですが、やはり現実のアプリケーションで少ないコストでバグを見つけられた、というのはインパクトが大きかったのだと思います。
Microsoftは少し前に安全性の観点からRustを推すブログを発表していたりと近年、この手の安全性の分野に力を入れているように見えます。

ところで、今回の対象としているようなバグはRustで書いていれば起きなかったのでしょうかね

2019年の振り返り

今年は以前より取り組んできた組込みシステム上でのRustプログラミングで一定の成果が出せた。
他、ブログも去年より色々書けたし、Twitterのフォロワー数も伸びてきた。

今年の成果

ブログ記事

今年はこの記事を除いて12本のブログ記事を書いた。内2本は英語版をMediumに投稿した。
去年は9本だったので、アウトプットの数は増えてきている。
また、その関連で各種LT会などに参加して、何回か発表もした。

自作OSプロジェクト

今年、一番の成果はRustで組込みOSを書くという個人プロジェクトでとりあえず基本的な形が出来上がり、それを公開できたことだ。

GitHub - garasubo/erkos: A prototype embedded operating system written in Rust
A prototype embedded operating system written in Rust - GitHub - garasubo/erkos: A prototype embedded operating system written in Rust

一応、今も機能追加を進めていて、以前のブログからだと簡易的なプロセス間通信が実装できた。
今はイーサーネットドライバの実装に着手し始めているが、まだ基本的なデバイスの初期化をようやく理解し始めたところなので、まだまだ時間はかかりそう。
去年のまとめではOLEDモジュールドライバの実装をしたいと言っていたが、それは流れてしまった。
正直、この先どういう機能を実装すべきか、というのは結構悩んでいて、というのは自分があまり実際の組込みOSに深く触れたことがないので、どういう機能がどういう構造であるべきなのか、というのがいまいち実感がわかない。
一旦、自作OSから離れて、既存の組込みOSで遊んでみる、というのはありなのかなあとぼんやりと計画はしている。

OSS活動

OSSのコントリビュートもちょくちょく始めるようにした。
組込みRust関連で気がついたことがあったときにPRを送った他、仕事でOSSのコントリビューションを業務時間内にやってもよい、と言われたのでRust製のブラウザエンジンのServoを触り始めている。

GitHub - servo/servo: The Servo Browser Engine
The Servo Browser Engine. Contribute to servo/servo development by creating an account on GitHub.

ブラウザエンジン開発はもちろん、デスクトップのGUIアプリの開発自体ほとんど経験がないので、学ぶべき内容は多い。
そのため、現状だと仕様書とにらめっこする時間の方が圧倒的に長く、今年は数行程度の簡単な修正しかできてないが、来年はもうちょっと大きめの変更もできるようになりたい。
今はIME周りの実装がまだまだ甘い、ということに気がついたのだが、これを修正するのはかなり大変そうで困っている。

競技プログラミング

競技プログラミングもちょくちょく参加するようにした。
AtCoderのBeginner Contestをメインで参加するほか、AtCoder Problemsという外部サービスに問題のおすすめ機能がついたので、そのオススメ問題を単体で解く、ということをした。

AtCoder Problems

この推薦システムは結構優秀で頭の体操にはちょうどいいレベルの問題をちゃんと出してくれて、とても重宝している。
このサイトを運営してくださっている@kenkooooさんと、この推薦アルゴリズムを実装してくれた@pepsin_amylaseに圧倒的感謝。
その他、チームnegainoidoとしてICFPCに出て、一人チームとしてISUCONに出場した。
前者は去年と比べメンバーが一人欠けた状態だったものの、去年レベルの順位をとれたのでトータルとしてはよかったのかなあと思ったが、ISUCONは惨敗だったので悔しい。
SECCONはそもそも予選があることに気がつかず、参加できなかったという大失態を犯した。

心がけてたこと

仕事外でのインプット・アウトプットを増やす、というのが去年からの継続してきた目標なのだが、それに加えて心がけていたこととして

  • SNS等での反応を必要以上に狙わない
  • 「精進」はしない
    ということに実は気を配っていた。

これは仕事以外のこういう活動というのをどうしてやっているか、というと一番の理由は自分がやりたいと思った分野であるわけで、それを見失ってしまうと精神衛生上よくないと思ったから。
そう考えると、SNS等で反応を貰いたい、という気持ち自体があるのはいいのだが、その優先順位があがりすぎると、そもそもマイナーな低レイヤー系のことをやめろ、という話になりかねないし、そもそも目立つ記事を書くみたいな分野は僕が得意な分野ではない。
「精進」という言葉については、なんとなく「つらいことに耐え抜いて努力する」という感じがして、楽しくないならやめればいいわけだし、自分は「精進」といえるほど努力するタイプでもない。
あと、つらいことに耐えるというのが目的になり始めると、その先の見返りへの欲求みたいなのも自然と大きくなる気がしたので、あまりにも気がすすまないときは素直に休むことにした。なので今年は「精進」していません。
とはいっても、もうちょっと生産ペースは上げていきたいなあ。

来年について

Rustでの組込み自作OSは一定の成果は上げられたので、これについてはまとまったドキュメントを書いて、機会があれば製本して技術書典あたりで販売したいと思っている。
自作OS作成そのものについては、イーサーネットドライバ周りをある程度作り込んだら、先述のとおり一回戦略を立て直すために別の既存のプロジェクトを触るという方向になると思う。

ブログ記事も平均月一ペースで書けたので、来年はこれに加えて英語版も増やしていきたい。

なお、今年から始まったGithub Sponsoredに登録成功したので、もし自分の活動を支援してくださる方がいらっしゃるならば是非お願いします。

Sponsor @garasubo on GitHub Sponsors
Support garasubo’s open source work

This Week in Rustで振り返る今年のRust

これはRustその2 Advent Calendar 20197日目の記事です。
去年も参加したRust Advent Calendarなのですが、今年はその3まであるようですね。Rustの人気が年々盛り上がっている証拠でしょうか。

This Week in Rust

This Week in Rustとは、毎週Rust関連のブログ記事やRustコンパイラへの変更などを紹介してくれるニュースレターです。
すべて英語の記事なので、正直読むのがしんどいのですが、気になったタイトルがあったら読むようにしています。
今回は今年のThis Week in Rustで紹介された記事からいくつかピックアップして紹介して、今年のRustコミュニティの動向を振り返ってみようと思います。
なお、選んだ記事は自分の興味にものすごく影響を受けているため分野は偏り気味です。

Rustで既存プロダクトを置き換える話

C/C++やPythonで書かれたプロジェクトをRustで置き換えるという話をかなり見るようになりました。

We rewrote our IoT platform in Rust and got away with it
At Dwelo, we’ve written the code for our IoT gateways in Rust. It’s fast, it’s reliable, and it’s secure. But we didn’t start with Rust…

Pythonで書かれていたIoTプラットフォームをRustで置き換えたという話です。
スケールさせるためにより高速な言語に置き換えねばならなかったこと、様々な技術的負債が溜まってしまったという状況で、Rustに置き換えるという選択をとったようです。
当然、C/C++も候補に入りましたが、nullポインタやキャストのバグなど、言語の性質上起こり得るバグをPart2で紹介し、
Part3でRustならそれが起こらないことを説明しています。

Oreboot (PDF)

CorebootというオープンソースのブートローダーをRustで書き直すOrebootというプロジェクトの紹介です。
Rustを選んだ理由から現在のOrebootの設計・進捗状況を説明しています。現状はQEMUのArmやRISC-Vのボードで動いているようです。

How to make your C codebase rusty: rewriting keyboard firmware keymap in Rust
Recently, my colleague introduced me to QMK 1, an open-source keyboard firmware. Like many non-trivia C projects, macro is heavily used ever…

自作キーボードでおなじみのキーボード用ファームウェアのQMKをRustで書き直す話です。
C言語で書かれたものをどうRustで表現するか、RustとC言語を連携させるテクニックがまとまっていていいと思いました。

組込み分野での応用

Rust Embeddedグループが去年発足したように、組込み分野への応用はRustの用途として注目されている分野のひとつです。

Apache MynewtというリアルタイムOSを用いて、STM32 Blue Pillというマイクロコントローラ上でRustのアプリを動かす話です。
なぜC言語ではなくRustがいいのかというところから、実際にどのようにしてプロジェクトに組み込むのかまで詳しく説明されています。

C言語のとの併用

Rustの魅力のひとつはC言語と互換性をもたせることができるため、Cで書かれたライブラリを呼び出したり、逆にC言語側からRustのライブラリを呼び出すこともできます。

Rust as the new C. Part 1: building and combining native libs into C API
Evaluating Rust as the common denominator of modern development

RustのプロジェクトにC言語のライブラリをどのように取り込むか、という話です。
LMDB、Blosc、SQLiteという現実のライブラリをプロジェクトに取り込んでみて、ビルドの設定の仕方、機能の呼び出し方などを解説しています。

安全性

Microsoftが、多くのバグがメモリの安全性の問題に由来しているため、その解決策のひとつとしてRustを提案しているというブログが公開されました。

A proactive approach to more secure code – Microsoft Security Response Center

続くブログでは、なぜRustがC/C++の代わりとして注目しているかが説明されています。

Why Rust for safe systems programming – Microsoft Security Response Center

C/C++のように低レベルでのパフォーマンスコントロールができる一方で、C/C++より強力な安全性の保証をしてくれます。
また、メモリ関連の安全性を犯しにくい、型システムも強力で表現力が高いことなども理由に挙げられています。

Amazonも去年、FirecrackerというRust製のVMMをオープンソースプロジェクトとして公開し注目されましたが、様々な大企業がRustに注目しだしている、ということがわかります。

async/await

今年のRustの変更で一番大きな注目を集めたのはasync/awaitの追加でしょう。それに関連する記事もいくつか紹介はされていました。
が、自分自身がasync/awaitの仕様をまったく追えていないので、今回は紹介しないでおきます。

Rustは進歩が早く、まだまだ学ぶことが多いですが、来年もRustをやっていきたいと思います。

論文紹介：An analysis of performance evolution of Linux's core operations

元論文：https://dl.acm.org/citation.cfm?id=3359640

論文概要

SOSPという2年に一度のシステム系国際会議のトップカンファレンスのものです。トップカンファレンスだけあって毎回新しい手法をとんでもない実装量でこなす、みたいなとてつもない論文が多い印象なのですが、この論文は地道にLinuxのパフォーマンスの変化を観察し、その原因を探っていくという結構変わり種な論文な気がしました。

Linux 3.0から3.19、4.0から4.20までのカーネルを用いてマイクロベンチマークで性能測定をして性能変化の原因を調査し、アプリケーションベンチマークでその変化が実アプリケーションに与える影響を調べましたという論文です。
実は、システムコールやコンテキストスイッチなどのカーネルのオペレーションのレイテンシは段々と大きくなっているということがわかりました。
これらの原因はセキュリティの強化、機能の追加、さらにはカーネルのコンフィグの設定ミスが原因であると突き止めました。
また、これらのパフォーマンス低下を緩和させるパッチや、コンフィグの設定を変えることでパフォーマンス低下を避けられることも示しています。

パフォーマンス低下の原因

この論文で紹介されていた11の原因を簡単に見ていきます

セキュリティの強化

CPUの脆弱性として話題になったMeltdownの対策として導入されたKPTIにより、マイクロベンチマークの性能は22％低下しています。
KPTI以前ではアドレス空間をカーネルとユーザー間で共有していたのですが、KPTIの導入により異なるページテーブルを使うようになりました。
その影響で、特権モードの切り替えのたびにTLBフラッシュが発生したため性能が大きく低下することとなりました。
その後、process context identifire (PCID)を利用することで、TLBフラッシュの範囲を限定することである程度この性能低下は緩和されましたが、PCID書き込みのためのシステムレジスタアクセスのオーバーヘッドも実はかなり大きく、一部のベンチマークでは逆にさらにスコアが下がることになってしまいました。

Spectreの対策として導入されたRetpolineのパッチも性能に影響を与えています。Retpolineは間接分岐を書き換えることで分岐予測を誤らせるものですが、その影響で分岐予測が上手く働かず性能が低下してしまいます。
著者らはselectシステムコールの性能低下に注目し、selectの中で31個もの間接分岐があることに注目し、これらを普通の分岐に書き換えることによって性能低下を抑えることに成功しています。

SLABのフリーリストのランダム化も影響を与えています。SLABとは同じサイズのメモリ領域のリストを持っておきそれをカーネルオブジェクトのメモリアロケーションに使うというものですが、そのメモリ領域の順番をランダム化させておくことにより、万が一バッファオーバーフローなどの脆弱性があったときでも目的のオブジェクトを攻撃者にアクセスさせにくくさせることができます。
しかし、これはフリーリストのランダム化にかかる時間と離れたメモリ領域へのアクセスが増えることによるキャッシュミスの増加というオーバーヘッドを発生させてしまいます。

同じくバッファオーバーフローを利用した攻撃の対策として導入されたhardened usercopyもオーバーヘッドを生んでいます。これはユーザー空間とカーネル空間間のコピーを行う際、カーネルのポインタを毎回チェックして不正なアクセスがないか検査するというものです。
このオーバーヘッド影響はどのようなデータタイプにアクセスするかによって異なります。

新しい機能導入

fault-aroundはページフォルト時に対象となったページへのマッピングだけではなく、その周辺のページについてもマッピングしておくことで、ページフォルトの数を減らそうというものです。
この変更はページアクセスの局所性を仮定したものですが、大きなファイルへのアクセスはランダムに行われがちでむしろ逆効果なのです。big-pagefaultというテストではこの変更により54%の性能低下が起きました。

control group (cgroup) メモリコントローラーはcgroup毎のメモリ使用を管理する機能です。この機能はDockerなどのコンテナ型仮想化のために導入されたものです。
この変更によりそれぞれのページがcgroup毎に割り当てられ、ページのアロケーション・デアロケーション毎にオーバーヘッドが発生します。

Transparent Huge Page (THP)は2MBのページを割り当てた後、必要に応じて別スレッドで4KBの通常のページに分割していくというものです。これはページテーブルのサイズを小さくし、TLBミスを少なくする効果があります。
しかし、2MB毎にページを割り当ててしまうことでフラグメンテーションが発生し、一部のベンチマークでは性能が低下します。

Virtual machine monitor(VMM)などのために導入されたユーザー空間ページフォルトハンドリングは、ページフォルト時のエラーハンドリングをユーザー空間で行えるようにしたものです。
これはページフォルト時にそのページがユーザー空間で処理されるべきものなのかをチェックする必要があるため、オーバーヘッドを生みます。

コンフィギュレーションの変更

Forced Context Tracking (FCT)はデバッグ用の機能で、CPUの利用率をトラッキングしたりするのに使われます。これが一部のバージョンで有効になってしまっていたため、パフォーマンスがその間は低下していました。

Linux 3.14で導入されたパッチで、second-level TLBのサイズの認識ができるようになりました。それ以前だとサイズの認識ができなかったため、不必要なTLBフラッシュが発生していました。この機能が利用できるようになったのは、second-level TLBを積んだHaswellファミリーのプロセッサがリリースされてから6ヶ月もあとのことでした。

CPU Idle Power-Stateサポートは、CPUをアイドル状態にする際のアイドル状態のレベルをコントロールするものです。このパッチが充てられる前は常にもっともレベルの高いアイドル状態に突入し、復帰までの時間がかかるためオーバーヘッドが余計にかかってしまっていました。
しかし、Xeonプロセッサ上でこのパッチがLTSカーネルで利用できるようになるまで時間がかかってしまい、導入前の間はオーバーヘッドが大きくなってしまっていました。

まとめ・感想

カーネルのオペレーションがだんだんと遅くなっていて、適切なパフォーマンスチューニングでそれらが緩和できることを示しました。
しかし一方で、このようなパフォーマンスチューニングは非常にコストがかかり、Linuxのように大量の変更が日々されているなかでこのようなことを行うのは難しいということも認めています。
実際、Googleのデータセンター用のカーネルは100人以上のエンジニアによってパフォーマンスチューニングが行われているそうです。

OS開発の世界は厳しい！

ISUCON9予選に参加しました

ISUCONというウェブアプリケーションを高速化させるというコンテストに参加しました。

ISUCON9 まとめ : ISUCON公式Blog
予選 参加チーム数 598組　合計 1561名（学生 258名） ・2019年9月7日(土) 　321組 , 755名（学生 124名） ・9月8日(日)　 　277組 , 680名（学生 134名） 本選 ・2019年10月5日(土) 　32組 86名 （学生 20名）　 …

去年も参加しましたが、結果は惨敗でした。
今年もチーム名「ガラスボッチ」で参加しましたが、メンバーは僕一人でした。看板に偽りなし。使用言語はNodejs（Typescript）です。
今回は事前に準備を仕込む時間をあまり取れなくまた、メンバー一人ということもあり、結果はGoの初期実装にすら劣るとかいう悲惨な結果でした。

本戦中にやったこと

基本的にはMySQLのN+1クエリ問題の解消とCategoryをメモリにキャッシュすることくらいです。
マルチサーバー化も試みたのですが、アップロードの画像データの扱いと、MySQLの設定で躓いて手を出せませんでした。

本番中はalpでアクセスログを解析してボトルネックを探りつつ改善という方針で行きました。
本番環境へのデプロイはrsyncコマンドを用いてやりました。リモートのgitレポジトリを仲介させるのは面倒くさい。
環境のセットアップとして前回用いたansibleスクリプトに少々手を加えておいて、必要なツールがすぐに入るようにしておきました。

敗因分析

Nodejsの初期実装でのスコアは500程度なのに対して、Go言語での初期実装のスコアは2000ほどありました。
確かにGo言語のほうが一般に実行速度が速いのですが、それにしては遅すぎると思い分析してみました。
alpでの結果を見てみるとNodejsの場合、/items/<id>.json（getItemメソッド）が時々10倍以上のレベルで遅くなっていることがわかりました。
この関数ではSQLの呼び出しくらいしか動作が重くなりそうなものはなく、初期実装でのSQL文に大きな差はありません。
原因はNodejsはデフォルトではシングルプロセスで動作していることにありました。clusterでマルチプロセス化したところ性能が安定してGo並のパフォーマンスになることが確認できました。
普段、ブラウザで動くフロントエンドのJavascriptしか触っていなかったため、このへんの知識が欠落していたのは痛かったです。

マルチサーバー化に失敗した原因ですが、MySQLのユーザー権限設定はIPアドレスベースで行えることを忘れていて、デフォルトではlocalhostからのアクセスしか容認していなかったからでした

MySQL :: MySQL 5.7 Reference Manual :: 13.7.1.4 GRANT Statement

また、画像ファイルのアップロードですが、画像アップロードと提供をするサーバーを1つに絞ってしまうか、nginxのtry_filesをつかうことで回避が可能かと思われます

Module ngx_http_core_module

今回はnetdataでCPU使用率がかなり厳しいことが分かっていたので、マルチサーバー化できなかったのは痛手でした。練習不足ですね。

外部APIを用いて通信している部分もあるのですが、そのうち多くは不要な呼び出しだったらしく、そこにも手を回す必要がありました。
サーバーをhttp2対応させることでもパフォーマンスが向上できたようです。http2対応は考えたのですが、効果がどれほどか自信がなく後回しにしてました。nginxの設定をいじり、アプリケーション側の初期設定を変えて、あと必要に応じてリクエストハンドラの型を変更すればできたので、とりあえずやっておいたほうがよかったかもしれません。

また、bycryptによるパスワード認証が重い、という問題もあります。 実際、ログイン部分の初期実装のレスポンスタイムは他のAPIと比べて高く、特にNodejsの場合、Goに比べてさらに2倍ほど遅い。
問題の制約として「パスワードを平文で保存する」ことが禁止されていました。
この解決策としては、ログイン専用サーバーをつくってしまい、CPU負荷を分散するという方法が想定解の1つだったようですが、運営の意図的にはシーザー暗号レベルの軽量なハッシュ関数での保存も想定解だったようです。
ただし、この「平文で保存する」という文言はかなり曖昧で、何を持って平文保存ではないかが明確でなく、「平文に適当な文字を足して格納する」という方法をとったために失格になりかけたチームがありました。
暗号理論などの世界で「平文ではない」とは「平文とは一致しない」だけで十分らしいですが、問題の文脈、すなわちウェブアプリケーションの開発においてカジュアルに「平文で保存しない」といわれたら、「DBのデータが盗まれても大丈夫なような暗号化を施せ」なのかなと自分は考えて、暗号のアルゴリズムを変えるにしても同程度の攻撃耐性を持つものにしか変えられないだろうと考えていました。
シーザー暗号のようなアルゴリズムの場合、DBから例えば”abcdefghijk…”といったパスワードがどうハッシュ化されているかを確認する、といった方法で簡単に平文が取得できてしまうという点で、「平文で保存する」と同等なのではという判断です。
結局は今回は運営が謝罪して、この制約による失格は全て取り消されましたが、競技者側からするとルールが曖昧な場合、実装の単純さや効果の大きさをとりギリギリを攻めるか、十分に安全をとって最適化を諦めるかは難しい判断です。
ISUCONに限らず、競技のルールにはどうしても曖昧性の残り、最後は運営の主観的な采配になってしまうのは仕方のないことだとは思うのですが、今後はもう少しルールを明確化する・（競技性を失わない範囲で）ルールの一部を事前公開してFAQを募るなど、不公平感のない対策があるといいと思いました。

NodejsでISUCONに勝てるか

今回、予選参加者のうちNodejsを使っているチームはそこそこいたようですが、決勝にはどのチームをいけていません。決勝に進んだチームではGo言語が圧倒的です。
以前からISUCONはGo言語が有利ということは言われていて、前回予選では他の言語を用いたチームもかなり健闘していたのですが、今回はGo言語の強さが色濃く出たのかなあという印象を受けました。
bycryptの実行速度はおそらくGoが有利だっただろうし、Nodejsの場合、ISUCONでよく用いられるメモリ上へのキャッシュ化もマルチプロセスするとプロセス間でキャッシュが共有できなくなるので厳しいのかなと思います。
私の場合は極端な準備不足だったし、メンバーも一人のみという舐めきった構成だったのでまずはそこをなんとかしなければなのですが…
（今年の予選1位と2位は一人チームだったらしいですが、よほど実装力に自信がない限り一人で勝つのは無理でしょう）

来年開催されるかは未定のようですが、開催されるのであればRustかScalaでの初期実装があるとうれしい