ここの翻訳になります
原文は2015年に書かれたものなので現在のRustの仕様と異なることが書いてある場合があります
本文章はGithubで管理されています
この翻訳は7割方間違っているので信用しないでください
Alex Light(alexander_light@brown.edu)
Advisor: Tom Doeppner
Reader: Shriram Krishnamurthi
Brown University, Department of Computer Science
この論文はRustでのUnixライクなOSカーネルの実装でわかった成功と失敗の体験を説明するものである。
CS167/9のために書かれたWeenix OSの基礎デザインと大量の低レベルな処理をサポートするコードを使って、協調的にスケジュールされた複数のカーネルプロセスをサポートする基本的なカーネル、基本的なデバイスのドライバーと仮想ファイルシステムの端緒を作ることができた。
Rust言語とその方安全システムで助けになったことといくつかの妨げ、このカーネルのRustとCの実装とのパフォーマンス比較について書き残しておく。
また、Rust言語とWeenixプロジェクトの概要も含める。
1971年に初めて作られて以来UNIX OSはソフトウェア開発に定着した。世界のOS開発と一般的なソフトェア開発への貢献の一つはそれを書くために作られたC言語だ。リリースされてから数十年、Cは相対的に小さくしかし最先端のプログラミング言語設計とチェックを変えられ、大きく進歩した。unixのほぼすべてのOSカーネルがCまたはC++のような言語で書かれていたという成功に感謝する。これはC以降の言語設計の進歩がさらに表現豊かで検証可能な領域の大部分が成功することを意味している。
このプロジェクトのゴールはRustを用いてunixライクなOSを作るのを試みることにある。私の知る限りでは、これは本気で試みられたことはないか、現在までに誰も成果を上げていないプロジェクトだ。これにより実現可能性とRustのような高水準言語でカーネルを作ることの利便性を見出すことができた。同様に目的に合わせて言語の改善点を見つけることができる。
さらにＣ以外の言語を通して調べたunixの基礎デザインがどれだけ保持しているか評価することが認められることになるだろう。最後に、私たちは完成されたカーネル検証のタスクを扱ったRustの洗練された型安全なシステムをさらに体験することになるだろう。カーネル高速化のさらに高水準なパーツをやりはじめるのを認めてもらうために、私はCS169で実装されたWeenix OSでの成果をベースにした。これでOS開発に特化したものではない、メモリアロケートといったたくさんの低レベルのカーネル部分を実装しなくてよくなった。
Weenix OSはx86ベースの教育用OSとして1998年にブラウンのCS167 OSコースで作られた。
現在CS169選択コースの学生たちはCS167に多くのWeenixによるunix-like OS由来の高レベルな部分で実装している。
学生たちはOSブートと実行のCコードを取得するために必要なコード、及びメモリ管理、デバッグプリントシステム、そして基礎的なlibc実装をこのプロジェクトで開始している。これを元にCS169の学生たちはかなり完成されたunix OSの実装を続けている。 プロジェクトと、それをサポートするコードはほとんどがCで、pythonとシェルスクリプトをOSの実行とテストのために書いた。
このプロジェクトは複数に分割されていて、いわゆるプロセス、ドライバー、VFS、S5FS、そしてVMからなる。プロセスはUnixライクなプロセスモデルな親子関係プロセスと初期化プロセスをシンプルなスケジューラと原始的な同期により実装されている。ドライバはTTYドライバ、ユーザ入力とハードディスクを使用する(最低限の)ATA相互接続ドライバに大きく分割してされている。VFSは、抽象型仮想ファイルシステムで、テストのためにRamFSと呼ばれるram-backedファイルシステムの提供を採用している。S5FSはS5ファイルシステムと呼ばれているsysv-fsファイルシステムのバージョンの一つで、非揮発性ストレージを提供するために実装されている。最後にVMは仮想メモリとユーザースペースにより実装されている。これらはまた多くの最終的なOSをテストできるユーザースペースを提供してきた。
Rust言語は比較的新しいシステムプログラミング言語で、Mozilla Foundationにより作られている。Rustは一般的に小さく高いパフォーマンスの低レベル層や組込プログラミング環境としてのCを使いやすく置き換えるために設計された。Mozilla FoundationはRustを使用してRustコンパイラ(Rustc)やServoと呼ばれる実験的なウェブブラウザといったいくつかの公式プロジェクトにRustを使用している。それはまた、Mozillaの有名なFirefoxブラウザをRust実装し始めることを近い将来に計画している。Rustは現在Github上で開発している。プロジェクトは非常に人気で開かれており、千人のコントリビュータがいるがそのほとんどはMozillaと関係がない。
Rust自身は手続き指向型プログラミング言語でCのようなシンタックスになっている。それは包括的な型システムや、データ"ライフタイム"システムとメモリ確保のための小さなランタイムとコンパイル時のスレッド安全性を採用している。具体的にRustはデータが他のオブジェクトによって使用されたときに予想外の変更されないことを保障するために所有権とライフタイム追跡システムを使用している。加えて、ライフタイム追跡システムはダングリングポインタができない言語を保障するために使用している。Rustのランタイムは分離可能な多くのパーツで構成されている。それはシンプルなアウトオブメモリもしくは致命的なエラーを回復する、求められた(そして最も基礎的な)機能だ。その最たる例の内にReenixが含まれていて、ヒープメモリの確保のためのインターフェースを提供する。ランタイムの他のすべての機能はOSの実行、ディスク入出力、プロセス間通信そしてスレッド作成、その他もろもろを一貫性のあるインターフェースとして提供するためにある。
Rustのシンタックスも同様だが、ほかのCライクなプログラミング言語とは少し違う。言語機能を説明するために図を使用して説明しよう、図1にはRustでの基礎的なクイックソート実装が含まれている。Rustのシンタックスとセマンティクスのすべての詳細はオンライン上のdoc.rust-lang.orgで見つけることができる。
最も顕著な違いはRustには式と文にいくつかの違いがみられるということだ。Rustの式ではいくつかのコード片がyieldな値であることだ。構文上、ほかの手によって値が作られることはない。
/// 基本的なクイックソート実装
/// 型ジェネリッククイックソート。 ‘T‘はソート対象の型で全体を順序付けなければならない。
/// (‘Ord‘ traitを実装すること) listで渡され、要素をソートしたソート済みlistを返す。
/// この過程のlistはmutableで変更可能であると言える。
pub fn quicksort (mut lst: Vec) -> Vec {
// ピボットから要素を取り出し、listが空なら何も返さない(そしてelse句へ行く)。
// そうでなければlistから最初の要素を取り除き、返す。
if let Some(pivot) = lst.pop() {
// ピボット周辺のlistを分ける。listを反復する(into_iter function)そして二つのlistに分ける。
// パーティション関数は二つのlistを返す。1番目のlistは全ての要素が状態がすべてtrueのもの、2番目の
// listは全てfalseのものである。
let (less, more): (Vec<_>, Vec<_>) = lst.into_iter().partition(|x| x < &pivot);
// ピボットより小さいlistの半分を再帰的にソートする。これはいずれ返されるlistとなる。
let mut res = quicksort(less);
// ソート済みのlistの半分の小さい方の最後の要素をピボットにする。これは'res'listにピボットを追加することである。
res.push(pivot);
// 半分に分けた大きい方のlistをソートし、ソート済みの小さい方のlistとピボットに追加する。
// extendは'res'listに 与えられたlistの全てを追加する。
res.extend(quicksort(more));
// 現在のソート済みlistを返す。ここではreturnが必要ないことを注意すること。
// 単純にこの行は'res'と書くだけでいい (’;’が必要なことは注意する)
// 関数が最後の式の値を返すのは(このif-elseのように)分岐の最後の値(Vec)を取ることと同等だろう。
return res;
} else {
// lst.pop()により、listが返されなかった場合emptyでなくてはならないのでempty list をここに記述する。
// returnは必要ではなくこれはブロック内の最後の式とこのブロックがfunction内で最後の式であることを注意すること。
// vec!は標準的なマクロで、Vecを作成する。
vec![]
}
}
fn main() {
// ソートするlistを作成する。vec!はマクロでリストされた要素のvecを作成する。
let lst = vec![3,1,5,9,2,8,4,2,0,3,12,4,9,0,11];
println!("unsorted: {:?}", lst);
// quicksortを呼び出す。これはlstの所有権を放棄する。
println!("sorted: {:?}", quicksort(lst));
}
**図1:**Rustでのquick sort
/// トレイト。構造体と列挙体はこれを実装できる。
pub trait Id {
/// 要求される関数。 全ての実装するものはこの関数について定義を提供しなければならない。でなければ型チェックで失敗する。
/// ’staticは文字列が静的に確保されていることを要求されているという意味だ。
fn username(&self) -> &’static str;
/// 既定実装付きの関数。返される文字列は少なくともIdが有効な間使用可能でなくてはならない。
/// ’aは返されるstrが少なくとも’self’が使える間使えなくてはならないということを意味する。
/// 型チェックはこれが正しいことを保障する。
fn screenname <’a>(&’a self, _board: &str) -> &’a str { self.username() }
}
/// 構造体。 deriveは与えられたトレイトの規定実装を提供する。
/// 特定のトレイトはこの方法で実装されるだろう。
#[derive(Debug, Eq, PartialEq)]
pub struct Account { name: &’static str, msgs: Vec, }
// Id taritの実装。
//既定の実装では’screenname’が実装する必要ではないことを注意すること。
impl Id for Account {
fn username(&self) -> &’static str { self.name }
}
// Accountに関連する関数を直接実装
impl Account {
pub fn get_messages(&self) -> &[u64] { &self.msgs[..] }
}
#[derive(Debug, Eq, PartialEq)]
pub enum Commenter {
/// データ付き列挙体の値
User(Account),
/// データなしの列挙体の値
Anon,
}
/// Idトレイトの実装
impl Id for Commenter {
fn username(&self) -> &’static str {
// 値別のアクションを選択する。
match *self {
Commenter::User(ref a) => a.username(),
Commenter::Anon => "Anon",
}
}
}
**図2:**Rustのtraitとtype
全ての関数内は図1の14,17行目と40行目のような、(1)let変数を除いて変更可能である、ということを除けば一般的な式で、(2)ループ構造、(3)式または構文のあとにセミコロンが置かれる。カーリー括弧に分割されたブロック({})は最後の式の値を使える式であることに注意してほしい。if-elseやmatchブロックは同じような式だ。例として図1でのif-elseブロックは9行目から開始されている Vec<T> 型の式だ。Rustはブロックで開始し、関数内の最上位の最後の式の値を暗黙的にreturnされている式にすることを採用した(図1内の8行目から開始されるif-elseだ)。が、図1のうちの一つは未だに ’return <value>;’ の形式をとっている。これは図2の45-47行目のようにmatchの戻り値が関数である場合にも見て取れる。さらに、これは図1の23行目を単純に’res’とプログラムを同じ意味で変えることを意味している。
他に顕著なCとの違いとしては、Rustが既定で完全なimmutableであることだ。オブジェクトをmutableにするには図1の14行目のようにmutで宣言しなければならない。これと同じように関数の引数も図1の5行目の第一引数のようにmutを記述しなければならない。この延長でポインタも既定でimmutableになっていて、mutableに使用するには &mut で宣言されなければならない。
RustはCと同様に構造体と列挙体の宣言構文を持っている。主な違いとして、列挙体はデータと関連付けることができるということがある。図2の33行目にあるように列挙体の定義はそのうちの一つのようにAccountタイプに関連付けられてデータを持っている。このデータは図2の45行目のようにmatch式で使われることができる。Rustはまたトレイトもあり、Javaのインターフェースと同等で、規定の関数定義と関連づけることができる。トレイトを使うことによってCよりも容易にジェネリック関数を作ることができる。例えば、図1のクイックソート実装は、オブジェクトは並び変えられるOrdトレイトだけを実装している必要があり、全て並び替えられる。図2の2-10行目のIdトレイトは16行目のAccountタイプと33行目のCommenterタイプで実装されているのがわかる。列挙体と構造体はトレイトを通してか、直接メソッドを持つことができる。Commenterトレイトは図2の28行目で実装されたget messages関数を持っている。Rustはオブジェクトハンドルをトレイトのポインタとして割り当てられた場合に仮想メソッドテーブル(vtables)を通して透過的な関数再帰呼び出しができる。これはまたジェネリックコードを容易に書くことができ、C言語よりも簡単に実装を隠すことができる。
Rustも匿名関数を宣言することがサポートされている。匿名関数はパイプ(|)によって囲まれた引数リストに続く式で宣言される。型アノテーションも同様にこれらの通常関数がオプションで認められる。戻り値と引数の型は書かれていない場合、推論される。図1の12行目で匿名関数が使われている。この行ではアイテムがpivotよりも小さいかどうかを見分けるために使われているので、partition関数はアイテムリストを二つのリストに分けることができる。
図1もRustマクロシステムを利用している。Rustマクロはコンパイル時間に構文抽象化ツリー(AST:abstract syntax tree)のコード片に変形されるのではなく、ソースコードのテキストにCマクロが行うことをしている。
マクロはおそらくDSL(Domain Specific Language)かrustcのコンパイラプラグインで実装されている。
二つのシステムは名前衝突と使用されているコンテキストから独立している場合にのみ衛生的なマクロの生成を許可している。マクロDSLはコンパイル時計算を超えてのパターンマッチを許可せず、明確なquasiquote operatorを持たない。しかしながら、コンパイラのプラグインはこれらのことを行う。
マクロは名前の終わりにエクスクラメーションマーク(!)で識別され、構文かネストされた式どちらかに展開されるだろう。図1の28行目と30行目で引数で与えられた Vec<T> フィールドを作成するvec![...]マクロを利用した。
Rustもかなり厚くパターンマッチングをサポートしている。図1の8行目と12行目にあるlet構文はオブジェクトとタプル構成部品の中で"破壊"可能なものの一つだ。12行目でpartition関数によって返された二つのタプルを破壊し、二つのリストにした。同行でも Vec<> をpartition関数のvariantを使ってコンパイラに伝えるために特定する必要がある。これについて、enumでも同様にできるが、図1の8行目ifかletどちらか使わなければならないか、図2の45-48行目のusernameようにmatch構文で全てを異なるものにできる。
もうひとつRustの主要な機能として所有権があげられる。一般的に、すべてのオブジェクトはスコープを抜けるときに破棄の責任がある。所有権は(ポインタの使用なしで)オブジェクトが"値として"他の関数に渡されるか、関数から返り値として戻される時に移譲されることができる。この方法で移譲される場合オブジェクトは新しいオーナーに移動されるということだ(ただし、実際のメモリは移動するかもしれないし、移動しないかもしれない)。一度所有権が移譲されると、オブジェクトの元のオーナーは直接的に移動されたオブジェクトを使うことはできず、何かしたければ新しいオーナーのポインタを入手しなければならない。所有権の移譲は図1の38行目でlstの所有権が変数quicksort関数に渡される時に見ることができる。もしこの行の後でlst変数を利用を試みた場合、コンパイラはlst変数は移動されたと言って防ぐだろう。quicksort関数で自身の変数の参照所有権は28行目でreturnする時に移譲されている。オブジェクトのフィールドは所有しているオブジェクトに所有されている。この所有権の木を生成し、現在のスレッドのスタックフレームか、静的に確保されたオブジェクトがルートになる。
当然、参照カウントポインタ、弱参照そしてミューテックスはシステム上の例外扱いとなる。
これらの型は全てunsafeに振舞うよう実装されており、Rustの型チェックと型安全システムを無視するように許可されている。スレッド間でデータを共有するのはオーナーなしでは難しい。さらに、このようにデータ共有する場合、全ての参照を最低でも使用されている間有効な状態を保つ必要が明確に必要になってくる。この問題については小節2.4について議論する。
Rustの型チェッカーかなり標準的な型インターフェースを備えた静的型付け言語チェッカーだ。一つ興味深いのはRustの型チェッカーの機能は複数の方向性がある型インターフェースであるということだ。それは関数の別型は引数と(宣言された)戻り値の型二つに基づかれて使うことを選ぶ。図1での例として、lessとmoreは二つともVecかそうでなければ型チェッカーはpartition関数を使うために決定できないので、指定する必要がある。図1の12行目でしたように、型システムが型を提供しなければならない場所で、アンダースコア(_)を使うことができる。図1の14行目にあるように、これは常にlet構文で型が提供されていない場合の既定の動作だ。
他のRustの主要な機能として、データのライフタイムに考慮するRustチェッキングシステムがある。Rustはいつでもライフタイムにおいて、オブジェクトはチェッキングシステムによって自動的に作る。オブジェクトのライフタイムは生成されてから破壊されるまでを指す。オブジェクトのライフタイムは値によって移動する場合に変更することができるそうでなければ定数だ。ライフタイムには図2で見せたようにほかのジェネリックのような名前が与えられるか、特別な’staticライフタイムの一つとして使う。ライフタイムの名前は常に、対になっていないシングルクォート(’)でマークされる。Rustの借用チェッカーRustプログラム中の全てのオブジェクトライフタイムが一貫していることを確認する。オブジェクトのために作られ、いつでも同じオブジェクトに向けられたライフタイムを保持するポインタによって働く。Rustはポインタなしで最低でも(所有権を移譲する)移動できないオブジェクトのポインタが生きてる間、向けたオブジェクトのライフタイムが生き残るのを確実にする。例えば、図２の9行目で返された文字列のライフタイムがscreenname関数で呼ばれたオブジェクトのライフタイムと同一であることを指定している。コンパイラはどんなときでも作ったオブジェクトが破壊された後、この関数から返された文字列を使用するのを防ぐだろう。ライフタイムはまた型に組み込まれており、構造体と列挙体の内部のポインタで可能にする。これらすべてのチェックは純粋にコンパイル時に行われ、実行時にオーバーヘッドがかからない。
Rustは必要ならこれらのチェックを回避することが可能だ。それを実施するにはunsafeな環境で使う。unsafeな環境である間、いくつかのつうじょうではRustの型安全システムで禁じられたことを可能にする。それらには生メモリの逆参照や、型キャストを検査しないで行うなどがある。