livaの雑記帳

ドイツでのインターンシップの話 〜1.成り行き編〜

※最近ドイツでインターンしていて(twitter見てる人には僕がておくれてるようにしか見えないのかもしれないけど)、その近況報告兼、もしかしたら今後ドイツに来るかもしれない人向けの記事です。参考になるかは分からんけど

いろいろあって(家が無かったりとか)忙しいので、小分けにしつつ細々と書いていこうかと思います。

インターンの基本情報

会社:NEC Laboratories Europe GmbH

メンター:みっちーさん(@michiohjp

場所:ハイデルベルク,ドイツ

期間:4月中旬から9月末まで

内容:システム系(デバドラ書いたりとか?)

きっかけ

バイト先の上司に「俺はこの会社を辞める。お前の事なぞ知らん、どこか遠くへ売り飛ばす。」と言われたから。

冗談はさておき、日本の某所で研究系のアルバイトをしてたのですが、2018年末辺りに上司に突然呼び出され、「私はこの会社を辞めます。君の今後の身の振り方を考えましょう」と言われました。

ちょうどその頃みっちーさんの方でもインターンの学生を募集していて、上司(お互い知り合い)が「めっちゃ良い環境だよ」「みっちーの所に送り込んだ学生は皆強くなって返ってくるんだよね」とか「俺の方が行きたい」とかいろいろ言ってて、そこまで言われると行かないという選択肢を選ぶのが勿体なく思えてきたんですよね。前日までは「海外とか絶対行きたくねぇ」とか思ってたのに不思議なものです。

NLEってどんなとこ

NLE(NEC Laboratories Europe)のシステム系のチームは素人の僕目線でも結構研究業績が凄くて、たぶんここ最近で一番大きなので言うと、SOSPに通してたりします。

ちなみに、みっちーさんには以前偶然一度お会いした事があるのですが、その際にpublication listとかを見て、「日本人でこんな人存在するんだ...てかNECって日本企業じゃん、マジか...」と驚愕した記憶があります。(そういう意味もあって、インターンの話が出る前からちょっとNLEには興味があった)

あ、NLEの社風はほぼヨーロッパ企業です。NLEの中にいて日本企業である事を感じるのはロビーに「和」とか「創造」と描かれた書道作品が置いてあったり、メールの署名にカタカナの名前が併記されてたりするくらい。じゃなかったらシステム系の研究が強いわけないよね。

とりあえずまとめてきな

海外に行くのって言葉や慣習の面で結構ストレス溜まるって言いますが、メンターが日本人だとだいぶ安心感あるので、first stepとして凄く良いなぁ、っていうのを最近めっちゃ実感してます。

ドイツ来てから孤独感を感じた事が全然無いのには自分でも驚きです。いやまあこれは海外とか国内とか関係無く、面倒見の良い上司に当たるかどうかな気もしますけどね。

seccamp2019(課題)

このページは、セキュリティ・キャンプ2019 OS開発ゼミ 最先端OS談義のテーマの説明と、その課題です。

目次:

テーマ概要

簡単に言うと、

下の方の課題文を読んでみて、(解けるかどうかはさておき)「面白そう!」と思える人にはオススメなので、是非一度課題文を眺めてみてください。

テーマの趣旨

恐らくこのページを読んでる人は、既にOSに興味がある人だと思います。

そんな皆さんに、

  • OSという世界がどれだけ広いかを知ってもらいたい。
  • 自分でアイディアを考え、それを形にする力を身に着けてほしい。

というのがこのテーマの趣旨です。

OSの世界がどれだけ広いかを知る事は、皆さんの考え方の幅を広げる事でしょう。考え方が広がれば、「こういう機能が未来のOSにあれば良いのではないか」という事を考えられるようになるはずです。しかもアイディアの質も、考え方が広がる前と比べ、格段に向上します。

それってとてもワクワクする事だと思いませんか?

そもそも誰だお前

東京大学情報理工学系研究科の博士課程1年生で、普段はOSの研究をしています。(研究室HPは→PFLab

あと、最近はNEC欧州研究所でインターンをしていて、ドイツにいます。

普段どんな事を考えているかとかは過去のブログ記事を見てもらえれば。

キャンプ中にどんな事をやるの

今の所以下のような感じをイメージしてます。(変わるかもしれないけど)

  1. 事前学習中に低レイヤープログラミングに関する基礎を身につけ
  2. 当日は議論を繰り返し
  3. まあ多少は座学とかも混ぜつつ
  4. OSの最先端の世界を学び
  5. 学んだ事も元に自分で何かしらのアイディアを考えてもらい
  6. その簡易版を実装する

みたいな感じです。

このテーマを応募するために何をすれば良いか

エントリーページから応募してください。

  • トラック選択でY-I OS開発ゼミを選ぶ。(必須)
  • ゼミ共通問題にできるだけ答える。(必須)
  • テーマ別問題で「最先端OS談義」の問題(以下に記載)に答える。(必須)
  • もし他にも興味があるテーマがある場合は、そのテーマの問題にも答える(任意)

「最先端OS談義」のテーマの応募審査に通過できなくても、他のテーマで通過できる可能性があるので、興味があるテーマの問題も解いてみる事をオススメします。

本テーマへの参加に求められるスキル

  • C言語で簡単なコードを書けるだけのコーディングスキル(OSゼミ共通問題がある程度解けていればOK)
  • 「◯◯について自分の意見を述べよ」と言われた時に、最低限何かしら(頓珍漢な事でも良いので)を言える事
  • OSについて深く考え、自分の意見やアイディアを練る事が好きな事
  • 他者の意見を尊重できる事(強く否定したりするのは絶対ダメ)

これらのスキルが自分には全く無いな(こういうスキルに興味が無いな)、と思う場合: OSゼミ内の別のテーマへの回答も検討してみてください。もしかしたらあなたともっと相性の良いテーマが見つかるかも。

こういうスキルを身に着けたいけど、自分にはまだ十分では無いかも・・・と思う場合: 「今はそういうスキルは無いけれど、キャンプまでにできるようにします!」は大歓迎です。講師としては、「たとえ今はスキル不足でも、この人だったらキャンプ前に/キャンプ中に/キャンプ後にこれくらい伸びるだろうな」と思えれば、高く評価します。ただし、そういう所が上手く伝わるように応募用紙を書く事だけは忘れないでくださいね?

応募課題

2つのテーマからどちらか選び、そのテーマの問いに全て答えてください。

答えられない問いがある場合: 無回答=即アウトではないですが、できるだけ頑張って答えてみましょう。また、ある程度他の問いの答えでリカバーする事が可能です。(その辺は柔軟に採点します)

問いに対する解答以外でも、皆さんなりに考えたアイディア等を書いてもらえれば、加点します。ただし、「アイディアを書けば書くほど加点される」というわけでも無いので、問いに答えた上で、余力があれば書く、くらいが良いかもしれません。

テーマ1:広帯域I/O

データセンターにおけるネットワークトラフィックはますます膨大になり、ソフトウェアはその膨大なトラフィックを効率よく捌く事が求められている。

read(2)やwrite(2)といった古来から存在するシステムコールカーネル空間とデータ空間の間のデータコピーを必要とするが、広帯域な通信においては、このデータコピーがボトルネックとなりうる。Intel DPDK(よく分からない人はGoogleで調べてみよう)に代表されるような、アプリケーションがネットワークデバイスを専有し、双方がカーネルを経由せずに直接通信するソフトウェアモデルは、データがカーネルを経由しないためデータコピーを必要とせず、これに起因するパフォーマンス低下の問題を解決する事が可能である。

問1:なぜread(2)やwrite(2)ではデータコピーが必要なのだろうか?

問2:なぜIntel DPDKのようなモデルではデータコピーが必要無いのだろうか?(カーネルを経由しないとなぜデータコピーが必要無いのだろうか?)

問3:Intel DPDKのようなモデルはどのような状況に適し、逆にどのような状況に適さないだろうか?

問4:このテーマに関連した事を自分で調べ、自由に論ぜよ。

テーマ2:仮想化・抽象化

他者に干渉されないコンピューティング資源を獲得する手段を提供する、というのはシステムソフトウェアにおける重要な課題である。この課題はコンピュータ釈明期から存在し、そして今も常に形を変えて存在し続けている。

最も馴染み深い物がプロセスであろう。現代のノンプリエンプティブマルチタスクOSにおいて、プロセスは他のプロセスを気にせずCPU資源を使用する事ができる。つまり、時間が経てば少なくとも何時かは処理が終了できるだろう、という事を期待できる。もしあるプロセスの実行を他のプロセスが完全に止める事ができてしまうなら、それはシステム全体の停止に繋がる可能性があり、大きな問題であるが、そのような事が現代のOSで起きる事は少ない。(まあ厳密には無いわけではないし、そもそもユーザーの体感的にあるプロセスが非常に重いと感じるならばその時点で問題なのだが)もう少し分かりやすい例を挙げるとすれば、あるプロセスのメモリは、共有メモリ等の明示的な物を除くと、他のプロセスから書き換える事はできない。つまり、プロセスは自身のメモリ資源を他者に干渉される事は無い。プロセスのこうした特徴は、OSが資源を仮想化する事によって実現されている。

仮想化と聞いて、仮想マシンを思い浮かべた人も多いかもしれない。これも仮想化の一つであり、本質的な考えは同じである。物理的なマシンの上に、仮想的なマシンを作り上げる事で、ある仮想マシン上のOS(ゲストOS)は、他のゲストOSから干渉を受けない。例えば、仮想マシンが他の仮想マシンのメモリを自由に書き換えられたら大問題である。仮想マシンの重要性は、クラウドコンピューティングの登場により、ますます高まった。

コンテナはプロセスにおける資源の隔離を更に拡張したものであり、コンテナ全体としての資源の制限(CPU利用率、メモリ使用率、etc...)や、ファイルシステムの分離等によって、資源をより柔軟に隔離する事が可能である。当然、コンテナ間での資源の干渉も起こらない。

仮想マシンクラウドコンピューティングの登場により、コンテナはdockerというエコシステムの登場により、爆発的に普及した。そして今後、これらとは全く異なる新しい仮想化手法が現れる可能性もある。システムソフトウェアの仕事は、上位のレイヤーに対し(OSならアプリケーションへ、ハイパーバイザならゲストOSへ)、仮想化(あるいは抽象化)された資源を提供する事であるから、より良いシステムソフトウェア(OS)を考えるうちに、新しい仮想化手法に巡り合う事があるかもしれない。

問1:PC用OSではプロセスを提供する事がほぼ必須だが、組み込みOS等では必ずしもプロセスを実装しているとも限らない。なぜだろうか?仮想化の必要性という観点から回答せよ。

問2:「仮想マシンの重要性は、クラウドコンピューティングの登場により、ますます高まった。」とあるが、なぜだろうか?仮想化の必要性という観点から回答せよ。

問3:コンテナと仮想マシンがそれぞれどういう状況に適しているかはググればすぐに出てくると思うが、「なぜその状況に適しているのか」を資源の仮想化という観点から説明せよ。

補足

テーマ1は、テーマ2を読んだ後の方が解きやすいと思います。

一見、テーマ2の方がテーマ1よりも難しく感じるかもしれませんが、テーマ1は問4を結構深掘りする必要があり、そのためには関連する技術項目を常に仕入れられるようにアンテナを広げられているか、或いはDPDK等を起点として自分で調べられるか、が問われるので、意外とテーマ1も難しいかもしれません。たぶん同じくらいの難易度なんじゃないかなぁ。

受かる確率を上げるためには

一言解答はダメ

問題に対する解答として一言だけ書く、というのはあまりオススメしません。

採点は、「問いの内容をどれだけ深く理解、或いは考察してるか」という観点で行います。簡潔に記述する事は大事なスキルではありますが、少なくとも本テーマの問題に対する解答としては、「私はこんなに理解してますよ!こんなにいろいろ考えましたよ!どう?凄いでしょ?」とアピールするくらいのつもりで書いてみる事をオススメします。

要するに早口オタクトークが読みたい

論理的に書く

自分の意見を書く時は、「私はこう思う」だけではダメで、「私はこう思う、なぜなら〜」と理由や根拠をきちんと述べましょう。その方が読んでる側が「なるほどね〜」と納得しやすくなるので。

根拠も、できるだけ皆に納得してもらえるような根拠を持ってくるのがベターですね。まあちょっと難しいかもしれませんが、チャレンジしてみましょう。(完璧でなくても、努力の跡が見えれば、それだけで十分評価できるので)

年齢による傾斜を意識しよう

仮に全く同じ内容で大学生と高校生が応募してきた時、僕は高校生の方を評価します。高校生の方が今後の伸びしろが大きいように感じるからです。

なので、自分はちょっと年齢制限ギリギリだな〜と思う人は、高校生に負けないような知識や考察力を解答の中で示してくださいね!

え、それだと大学生並に強い高校生には勝てないって?うーん、まあ良くある話ではあるけど・・・・とりあえずベストを尽くす事が大事なんじゃないかな。

加点ポイントを沢山作る

採点の際、僕は減点はしません。(他のテーマではどうかわかりませんが)

なので、書ける部分はいっぱい書いてください。まあ、いっぱい書いたからといって点数が増えるとも一概には言えないのですが、書いてくれた方が加点ポイントがつく確率は上げられると思います。

加点する部分は、上にも書きましたが、「問いの内容をどれだけ深く理解、或いは考察してるか」です。

自作OSでは価値を生み出せないと思っていた過去の自分へ

結論を先に書くと、「インプット不足」。

 

 

 

 

 

自作OSをやっていた頃は、「イマドキ自作OSなんてやっても、もう既にLinuxあるし、意味ないんじゃないかなぁ」みたいな事を良く思ってたんですよね。

 

「自作OSをやる意味」として考えられるのは2つあると思っていて、

 

  • 自分の技術力強化=素振り
  • 既存OSにない価値の提供

 

かなと。まあ前者は良いとして、後者は「Linuxで十分じゃね?」という話。

 

この話は高校生の頃からだいぶ悩んでいて、学部生の頃もずっと悩んでいたんですよね。「既存OSにない価値」として具体例を挙げてる人もいたけど、何かしっくりこないというか、モヤモヤするというか、「それ、あなた以外に価値だと認める人ってそんな多くなんじゃないかなぁ」的な事を思ったりして、自分自身の自作OSのモチベーションにはできなかった。

 

これ、某緑の本とか読んでOS楽しそうと思った人が、その後モチベを保てなくなって離脱する原因の一つでもあるのかな、とか思うんですよ。僕は頑固だったのでずっとやってたけど、この悩みがある間はずっと黒い霧の中にいる気分でした。

 

僕は大学院入ってから霧がサッと晴れた気分になったんですが、何が大きかったかというと、論文をたくさん読んだ事でした。論文読めば、世界では沢山の研究者が日々OSの研究をしてて、新しい価値を生み出している事が分かるわけです。0からOSを作って、既存のOSには実現し得ない事を成し遂げている人たちもいる。「Linuxで十分じゃね?」みたいに思ってた自分の視野の狭さを知って恥ずかしくなった反面、いかにOSという世界が幅広くて面白いかで胸がワクワクしたのを覚えています。

 

もちろん、別に論文を読むだけが答えではないでしょう。Linux以外にもいろんなOSありますからね。Linuxだって昔と今じゃ全然違うので、その歴史を辿るだけで様々な情報が手に入るはずです。

 

でもやはり、「OSという世界の深淵(魅力/奥深さ/可能性)に触れてみたい」と思う人は、論文を読んでみる事を僕はおすすめします。論文を沢山読む事は「非常に手っ取り早く、立体的な視野から、その領域を深掘りできる」事だと思っているので。コスパ最高だなぁ、的な。

 

マジで高校生くらいの時に論文を少しでも読んでおけば、もっと楽しかっただろうなぁ、って思ってます。大学生の時に先輩に「論文読んでおいた方が良いよ」と言われてたのに読まなかった人間なんで、こんな事言ってもしょうがないんですけどね。当時は「論文って何か難しそうだなぁ、読むの面倒くさいなぁ」とか思ったんだもん。

 

どんな論文読めば良いかは、とりあえずこの辺りから始めてみれば良いのではないでしょうか。

raphine.hatenablog.com

OSDIの論文は、発表スライドや論文PDFがリンク貼った先からダウンロードできるので、非常に良いですよね。発表スライドあれば、英語苦手でも何となく雰囲気掴めるし。契約してなくても論文が落とせるのも、高校生とかに優しくて非常に良い。

 

もしも「論文読みました、感想シェアしましょう」みたいなのとかあればお気軽にお声がけください。

 

(ネタ)ユーザー空間だけでプリエンプションする

今回の話を一言でまとめると:ユーザー空間のみでプリエンプティブマルチタスキングをしたい衝動に駆られ、ptraceを用いてスタックやRIPを操作する事で実装した。

 

 

※初学者向けの補足

今回の話の基礎部分は、武内さんの本の第4章「プロセススケジューラ」の辺りを読むと(説明が分かりやすいので)理解しやすいかもしれません。コンテキストスイッチって何???みたいな人向け。

  

 

また、より高度な内容に興味があれば、以下の資料が参考になると思います。プリエンプション???みたいな人向け。

https://www.pf.is.s.u-tokyo.ac.jp/wp-content/uploads/2018/05/OS_06.pdf

 

 

 

みんな大好きプリエンプション

皆さん、ユーザー空間でプリエンプションして、実行中のタスクを切り替えたりしたいですよね!したくないですか???

 

初歩的な解説:

最近のOSは、一つのCPUの上で複数のタスクを切り替えながら動かす事でタスクを並行動作させる(マルチタスク)事ができます。この時、「アプリケーションが明示的にタスクの中断ポイントを用意してないにも関わらず」タスクを中断し、別のタスクを再開する事ができます。(アプリケーション作る時に、「ここで別のプロセスに切り替えよう」なんて意識しないですよね?)この「アプリケーションの協力を得る事なく、タスクを中断する」事がプリエンプションです。

大事なのは、「アプリケーションの協力を得る事なく」という部分です。協力を得ていたら、それはプリエンプションではありません。

 

LinuxだとプリエンプションはLinuxカーネルが行うわけですが、やっぱりカーネルなんかに依存せず、ユーザー空間だけで実現したいじゃないですか。

 

というわけで、性能とか二の次で良いのでなんとかして実装したい、というのが今回のお話です。

 

やりたい事

userland_contextswitch_test/worker.cc at master · liva/userland_contextswitch_test · GitHub


上のリンクで反転しているコードを並行動作させたい、とします。

numberを1づつインクリメントするworker1と、numberを100づつインクリメントするworker2の両方を、適当なタイムスライスで切り替えながら動かしたい、みたいな。

 

実行時のnumberの変化はこんな感じです。

f:id:liva_h:20181112015855p:plain

最初worker1が動いて、0〜3までインクリメントした後、worker2に切り替わって、103〜303までインクリメント、worker1に切り替わり、303から306までインクリメント・・・・みたいな、単純なマルチタスクです。

 

シグナルで実装できるんじゃね?説

とりあえず実行中のプログラムの中断はシグナルハンドラでできるので、シグナルハンドラから戻る前に戻り先アドレスをいじる事ができれば、別のタスクに飛べるだろ、どうせ戻り先アドレスなんてスタックに積まれてるんじゃろ?みたいな事を最初は思ったわけですが・・・。

 

sigreturn(2)とかいろいろ調べてるとこのページにたどり着きました。

stackoverflow.com

できなくは無いけど、未定義動作だからやっちゃダメだよ、と。

まあ正直言って未定義動作だろうがなんだろうが、動くんならいいんじゃねみたいな気持ちはあるんですが、そんな事言ってるとtwitterの怖い人達に怒られてしまうので、この案はボツ。

 

ちなみにブログ書きながら調べてて見つけたんですが、sigreturn oriented programmingなんていう攻撃手法があるんですね。セキュリティ詳しくないから今始めて知った。

それこそセキュリティ界隈の人たちにとってみれば、「未定義動作でも良いから脆弱性突けたら勝ち」みたいな所ありますよね。楽しそう。

 

レジスタの値を自由に書き換えたい

別にシグナルとか使わなくても、レジスタを強制的に変更する事さえできれば、コンテキストスイッチは実現できるんですよね。

レジスタってどうやったら自由に弄れるかなぁ、、、って考えた所、「ああ、gdbでできるじゃん!」と。

で、別にgdb使う必要は無いので、gdbのベースとなってるptrace(2)を使う事にしました。

 

ptraceって何ができるの

特定のプロセスに対し、シグナルをキャッチしたり、システムコールの発行をキャッチしたり、レジスタやメモリを覗いたり、書き込んだりできます。

 

以下のブログが、ptraceの使い方を具体的に示してくれていて、分かりやすいです。

th0x4c.github.io

 

ptraceを使えば、worker1を中断し、レジスタを書き換える事でworker2を再開する、みたいな事ができます。

 

f:id:liva_h:20181112075812p:plain

 

worker1が動いている間、worker2の全てのレジスタをdispatcherが保持しておき、切り替えの際は、worker1のレジスタを退避、保持していたworker2のレジスタを書き戻せばOKです。TSS(Task State Segment)ですかね?

 

 

タスク切り替えはアプリケーションプロセスで

まあ正直これでも良いんですが、dispatcherの実装はできるだけ小さくしたいです。

dispatcherに最低限必要なのは、ripを変更する事です。それと、変更前のripを保存しておかなければいけないので、スタック辺りにripを保存する必要もありますね。そうするとrspとripのみを変更すれば良いという事になります。

 

dispatcher側のレジスタ操作はこのようになります。

userland_contextswitch_test/dispatcher.cc at master · liva/userland_contextswitch_test · GitHub

これハードウェアで実装すると、割り込みって言うんですが。

 

raxなどの汎用レジスタの退避、ripやスタックの切り替えは、アプリケーションプロセスに用意した特殊なルーチン(handler)が行う事になります。

f:id:liva_h:20181112081305p:plain

レジスタの退避

userland_contextswitch_test/int.S at master · liva/userland_contextswitch_test · GitHub

 

ripとスタックの切り替え

userland_contextswitch_test/int.S at master · liva/userland_contextswitch_test · GitHub

 

後者のコードでは、next_worker(定義)という構造体に格納されているripとrspを読み込み、同時に現在のコンテキストの再開時のripとrspをnext_workerに保存しています。

 

next_workerは最初worker2で初期化されており、専用のスタックも割り当てられています。

 

ちなみに、handlerの先頭にはnopを2つ挿入しています。これはアプリケーションプロセスがシステムコールを発行している時にhandlerを呼び出そうとすると、Linuxカーネルがシステムコールからの復帰時にripを-2するからだそうで、それを回避するためのものです。

 

dispatcherのインターフェース

アプリケーションプロセスはdispatcherにhandlerの先頭アドレスを伝えなければいけません。ptraceのお陰で、dispatcherはint $3(デバッグ例外)を受け取る事ができるので、int $3が投げられた時のebxの値をdispatcher側が保持する事にしました。これはlidtですかね

 

アプリケーションプロセスからdispatcherの呼び出し

userland_contextswitch_test/worker.cc at master · liva/userland_contextswitch_test · GitHub

dispatcher側のコード

userland_contextswitch_test/dispatcher.cc at master · liva/userland_contextswitch_test · GitHub

 

定期的なプリエンプション

何時どのタイミングでプリエンプションし、タスクを切り替えるかは大事な話です。単純なOSのスケジューラは一定周期でタスクを切り替えますが、今回もその方針で実装する事にしました。

 

100ミリ秒ごとにtimeoutをデクリメントし、timeoutがゼロになったらhandlerを呼び出します。timeoutのデフォルト値は30なので、handlerは3秒おきに呼ばれる事になりますね。タイマ割り込みかな?

 

リエントラントと割り込み禁止

worker1及びworker2ではstd::coutでnumberを出力しています。このstd::coutの最中にhandlerが呼び出されたらどうなるでしょうか?もしかしたらworker1のstd::coutが中断された状態で、worker2のstd::coutが呼び出されるかもしれません。

このような事が起きても上手く動く関数の事を「リエントラントな関数」と呼ぶのですが、残念なことにstd::coutのリエントラント性は仕様では保証されていません。

そこで、std::cout実行中はhandlerが呼ばれないようにします。raxに2や3を代入した状態でアプリケーションプロセスがint $3を実行する事により、dispatcher側にhandlerの制御について通知します。

なぜ僕はclistiを実装しているのか

 

お疲れ様でした

ここまで説明してきた事を実装すると、アプリケーションプロセス、dispatcherを合わせて、およそ500行くらいで「worker1とworker2の並行処理」が実現できます。

 

ところで途中途中でセルフツッコミしてたんですが、dispatcherはどう見てもCPUの機構をソフトウェアで再実装(エミュレーション)していますよね。うん、まあそういう事もある。

OSDI 2010〜2018の中で個人的に面白かった論文を雑に一言づつ紹介

システム系のトップ学会の一つである、OSDI (USENIX Symposium on Operating Systems Design and Implementation)の論文を2010年まで一通り眺めてみたので、その中で個人的に面白かった物をまとめてみる。

 

一通り眺めたといっても、全て読んだわけではないので、見逃してる論文もたぶんある。あと、英語力低くて趣旨を取り違えてる論文もあると思うけど、寛大な心で見逃してもらえると有り難いです。

(こういう系の話、少し間違えると「おめーここ間違ってるじゃねーか!」ってマサカリが飛んでくる印象があって、あんまり書きたくないんですよね)

 

2018

LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation

https://www.usenix.org/conference/osdi18/presentation/shan

一つのマシンに全てのI/Oを積むのは辛い(PCIeレーン足りなかったり)、データセンター内の隣のマシンのI/Oを透過的に参照できると嬉しい。

それを実現するためのOSの抽象化モデルを提案、実装した論文。抽象化の際は、GPU、ストレージ、メモリ、CPUといった各リソースをコンポーネント単位に分割して(メモリとCPUも分割してる!)、コンポーネント間がネットワーク越しに通信する事で、リソースの柔軟な運用を可能にした。


Arachne: Core-Aware Thread Management

https://www.usenix.org/conference/osdi18/presentation/qin

アプリケーションにはスループット指向の物、レイテンシ指向の物等様々な物が存在するが、大前提としてOSはアプリの事が分からないので、例えばアプリがどれだけのCPUコアリソースを必要とするか分からない。
そこで、CPUコアリソースの調停者を作り、調停者と協調するアプリケーションは調停者管理下のコアで専有的に1コア1カーネルスレッドで動作できるようにした。管理外のコアでは既存のアプリケーションが従来の仕組みで動作する他、管理対象のコアは動的に増減可能。
調停者はユーザーランドで動くので、Linuxに変更を加える必要もなし。


wPerf: Generic Off-CPU Analysis to Identify Bottleneck Waiting Events

https://www.usenix.org/conference/osdi18/presentation/zhou

マルチスレッドアプリケーションでは、CPUの使用率が低いにも関わらずスループットが出ない、という事例が存在する。分かりやすく書くと、ボトルネックとなるスレッドがI/O待ち等でブロックしてサボってる(最適化すればより多くの処理をできるはずなのに、やってない)みたいなケースが該当する。既存の性能解析ツールでは「一番ヒマしている」スレッドを見つける事はできるが、必ずしもそれが実際のボトルネックのスレッドとは限らないので、こういう事例の解析は難しい。
これを解決するため、スレッド間の依存関係のグラフ解析等をする、新しい性能解析ツールを作った。

※1. 問題設定が面白いと思ったが、解決手法までは興味が無かったので、その辺は割愛

※2. SOSP2017でこれの前段の研究が出てる。見逃してた。これから読む。

 

 

2016

Machine-Aware Atomic Broadcast Trees for Multicores

 

https://www.usenix.org/conference/osdi14/technical-sessions/presentation/zellweger

コア間の通信コストはコア間インターコネクトやメモリの構成によって大きくばらつく。(コアAとコアBの通信コストと、コアAとコアCの通信コストが異なる事は良くある。分かりやすい例だと、AとBが同じNUMAノード内に属していて、AとCが異なるNUMAノードに属している場合とか)なので、データをブロードキャストする場合、NUMA越しの通信は極力少なくするなどといった最適化が必要になる。しかし、このような最適化はアーキテクチャ固有であるため、これまでの全てのCPUへの対応に加え、新しい世代のCPUが出る度に再度チューニングする必要があり、最適化コストが非現実的なレベルで高い。
そこで、CPUのスペックシート情報、スペックシートには乗ってない細かいデータを取るためのマイクロベンチマーク、そしてヒューリスティックな最適化を行う事で、自動的に最適なブロードキャスト順序を生成するアルゴリズムを開発した。


2014

Arrakis: The Operating System is the Control Plane

https://www.usenix.org/conference/osdi14/technical-sessions/presentation/peter

OSによるI/Oの仲介は、ネットワーク通信を始めとした広帯域、低遅延I/Oに追いつけなくなりつつあるので、もうカーネルがI/Oデータ処理のルーティングをするのを諦め(?)て、ハードウェアに任せちゃいましょうよ、という話。

このOSでは、アプリケーションが広帯域I/Oデバイスを直に触れるようにした。デバイスはI/O仮想化によって隔離されているので、アプリケーションが直にデバイスを触ってもシステムに影響を及ぼす事は無い。デバイスドライバや、プロトコルスタック層は、アプリケーションにリンクされるライブラリ(ライブラリOS)によって提供される。これによってOSはI/Oデータ処理から解放(遅いI/Oについては引き続きOSが仲裁するものの)され、デバイスのアクセス権やリソース制限といった管理業務のみを行うようになる、というのが提案されているモデルである。

 

Decoupling Cores, Kernels, and Operating Systems

https://www.usenix.org/conference/osdi14/technical-sessions/presentation/zellweger

今後ヘテロジニアスメニーコアアーキテクチャの普及が予想されるが、そのようなアーキテクチャでは電源効率のため、一部のコアを「頻繁に」動的にon/offする事になると考えられる。しかし、既存のアーキテクチャは、コアの動的なon/offを高速に行う事を想定していない。

そこで、コア単位のOSのステート、及びアプリケーションのステートをカーネルから分離したOSモデルを提案した。これによりコアの動的なon/offを高速に行えるようになった他、その応用として、カーネルのライブアップデートや、それまで動いてたカーネルをより低消費電力なコア上でマイグレーションする事を可能にした。

 

2012

Dune: Safe User-level Access to Privileged CPU Features

https://www.usenix.org/conference/osdi12/technical-sessions/presentation/belay

今のアプリケーションはRing3で動くが、Ring0上で動けるようになるとハードウェアを直接制御できるので嬉しい。具体的には、ガーベージコレクションの際にページのdirty bitを直接参照できるのでどのメモリを回収すべきか(回収しないべきか)を高速に判断できるとか、web browserやモバイルアプリケーションといった、untrustedなコードをsandbox上で走らせたい場合にring3上で走らせれば良いだけなので低オーバーヘッドになる、等である。

そこでVt-xを用いてプロセスをアイソレーションするLinuxカーネルモジュールを開発した。プロセスはRing0で動き、システムコール呼び出し時はsyscallでは無く、vmcallを用いてRing -1のLinuxを呼び出す。Linuxカーネルへの変更は不要で、かつアプリケーションもライブラリをリンクしてdune_init()を呼び出すコードを追加するだけなので、ほぼ無変更で適用可能。(標準libcだとシステムコールを呼び出す際にsyscallを経由した後vmcallを呼ぶ事になるので、syscallを省略したければ改造版libcを再コンパイルする必要あり)


2010

An Analysis of Linux Scalability to Many Cores

https://www.usenix.org/conference/osdi10/analysis-linux-scalability-many-cores

2008年、2009年と「メニーコアでOSをスケールさせるためにはカーネルの設計を大きく変えるべきだ!」的な論文が盛り上がっていたが、「いや、別にLinuxもちゃんと同期周りをきちんと改善すればスケールするでしょ、はい解散」と言った論文。

メニーコアだとスピンロックのコストが高すぎるので、できるだけコア毎の構造に分割し、ロックを取らないようにするとか、リファレンスカウンタの厳密性を緩和して同期コストを下げるとか、ボトルネックとなっている細かい同期コストを修正していきましたよ、という話

FlexSC: Flexible System Call Scheduling with Exception-Less System Calls

https://www.usenix.org/conference/osdi10/flexsc-flexible-system-call-scheduling-exception-less-system-calls

システムコールを頻繁に呼び出すのはアプリケーションの性能低下の原因になるため、システムコールの呼び出し回数を減らしたい。システムコールのコストが高いのに加え、キャッシュを汚染してしまうためにアプリケーションコードそれ自体のIPCも低下するからである。

そこで、システムコール処理をバッチする(システムコールが呼び出された瞬間はsyscall()を発行せず、バッファに呼び出し情報を記載しておく)事を提案した。これは同期的なシステムコールを、インターフェースを変える事無く非同期的(aio的な)に扱う事を意味する。また、pthread互換なM:Nスレッドモデルのスレッドライブラリを実装した。このスレッドライブラリのユーザースレッドのスケジューリングは、ユーザースレッドがシステムコールを発行したら次のスレッドに切り替える事を繰り返し、実行できるユーザースレッドがなくなった時点でカーネル空間に遷移、まとめてシステムコールを実行する、という物である。

更に、システムコールバッチ処理する事により、システムコールを処理するコアとシステムコールを呼び出すコアを分離する事ができる。(システムコールは割り込みでは無く、コア間の通信となる)これにより、システムコール処理専用コア、アプリケーションロジック処理専用コアという分離が可能になり、キャッシュのヒット率も向上する上にカーネル空間とユーザー空間の遷移コストも削減できる。

おまけ:satさんイチオシ(かどうかは知らない)

 

 

宣伝

ここに書かれている内容に興味がある方、「もっと良いアイディアで問題解決をしたい!」と思う方は、東京大学大学院情報理工学系研究科コンピュータ科学専攻加藤研究室東京大学情報基盤センター品川研究室(情報理工システム情報学専攻と兼担)がオススメです。
これはあまり一般には知られてない情報なんですが、大学院からだと比較的入りやすいらしいですよ?

alpine linuxのminirootfsからqemuで起動する話

小さくて便利で皆大好きalpine linux

docker触ってたら一度くらい使った事ありますよね?(個人の意見です)

このalpine linuxではminirootfsというものが提供されています。これはalpineのファイルシステムをtar.gzに圧縮して固めたもので、公式サイトいわく、コンテナやchrootする時に使う事を想定されているようです。

このminirootfsは2MBしかなく、数十MBもあるインストールISOと違って、ものすごく軽量です。これなら、この軽量なminirootfsを使ってファイルシステムを構築すれば軽量なんじゃないかと思い、(ちょうど軽量なLinux環境をqemuで立ち上げたかったので)やってみました、というのが今回の話です。

別にminirootfsとか使わなくても、これとか使ってVMイメージを作れば十分軽量なんじゃないかと言われればそれまでなんですけどね・・・。
 

 

kernelを準備する

minirootfsにはカーネルが無いので、適当なバージョンのソースコードを引っ張ってきて、ビルドしましょう。僕はモジュールとかを適切にrootfsに展開するのが面倒になり、全てkernelにstatic buildしてしまいました。

ここで得られたbzImageをqemuのオプションで渡します。

 

qemuでどうやって起動するか

qemuからはこんな感じで起動しようと思います。

 

$ qemu-system-x86_64 -kernel bzImage -initrd rootfs -append "root=/dev/ram rdinit=/bin/sh console=ttyS0,115200" -net nic -net user,hostfwd=tcp::2222-:22 -serial stdio -display none

 

-kernelオプションで先程のbzImageを指定、initramfsとしてrootfs(minirootfs)を指定、出力はシリアルポート、initramfsで起動したまま、シェルを立ち上げる(カーネルパラメータオプションの rdinit=/bin/sh)、みたいなのを想定しています。

 

initramfsをrootとしてしまうのは完全に手抜き(別にinitramfsでの起動でも僕が本当にやりたい事は達成できるので)です。この上でファイルシステムに何か書き込んでも、当然qemuを終了したら吹き飛びます。まあ気になる人はちゃんとハードディスクイメージにするか、適当にNFSマウントでもすれば良いのではないでしょうか。

 

とりあえずこれをやるために必要な事として、rootfsを準備しなきゃいけません。次からこれを準備していきます。

 

rootfsの準備

initramfsのファイルフォーマットはcpioです。minirootfsはtar.gzで落ちてくるので、展開した後、cpioにしなければいけません。

そして展開しようとすると、デバイスファイルが展開できなくてこけます。

 

なので、fakerootを使いましょう。

 

$ fakeroot && tar xf ../alpine-minirootfs-3.8.0-x86_64.tar.gz && 

find | cpio --quiet -o -H newc | gzip -9 > ../rootfs

tarでカレントディレクトリにminirootfsを展開した後、cpioコマンドで固め、gzip圧縮しています。

 

確かこれだけで/bin/shは起動するはず

 

initを起動したい

シェルが立っただけだと、何もサービスが使えないので、使い物にならないです。わかりやすい例で言えばネットワークとか。

というわけで、initスクリプトを起動しましょう。

 

$ qemu-system-x86_64 -kernel bzImage -initrd rootfs -append "root=/dev/ram rdinit=/sbin/init console=ttyS0,115200" -net nic -net user,hostfwd=tcp::2222-:22 -serial stdio -display none

rdinit=/sbin/initにすると、initスクリプトが起動します。

 

これで起動すると、以下のようなエラーが出てしまいます。シェルすら出ません。辛い。

can't open /dev/tty1: No such file or directory

 

/dev/tty1というデバイスファイルがない、というエラーですね。

minirootfs内の/etc/inittabには以下のような行があり、ここで/dev/tty1を参照していますが、その時までに/dev/tty1が作成されていないため、このようなエラーが出るわけです。

tty1::respawn:/sbin/getty 38400 tty1

 

バイスファイルを準備したい


/dev/tty1を生やす簡単な方法を探すと、こんなのが出てきます。

 

kernhack.hatenablog.com

 

initramfsのinitと同様に、以下のようなコマンドを実行すればデバイスファイルやその他諸々が整備されるはずです。

mount -t proc proc /proc -o nosuid,noexec,nodev
mount -t sysfs sys /sys -o nosuid,noexec,nodev
mount -t devtmpfs dev /dev -o mode=0755,nosuid
mount -t tmpfs run /run -o nosuid,nodev,mode=0755


なので例えばこんな感じの事を/etc/inittabの最初でやれば、解決します。

 

::sysinit:mount -t proc proc /proc -o nosuid,noexec,nodev

 

最初はこれで解決していたのですが、途中でもっと綺麗なやり方がある事に気づく事になります。ひとまずこれで解決した、という体で話を進めさせてください。

 

そもそも/etc/inittabの編集ってどうやれば良いんだ!という方もいらっしゃるかもしませんが、それはtarで展開した後、/etc/inittabで編集し、cpioに食わせれば良いだけですよ。

 

シリアルでログイン画面が出てこない。

これだけだと、エラーは出なくなりますが、まだログイン画面には到達できません。/etc/inittabでは以下の行がコメントアウトされているためです。

 

ttyS0::respawn:/sbin/getty -L ttyS0 115200 vt100

 

まあそりゃ今はシリアルで画面出力しているから、シリアルコンソールに対応するデバイスファイルを設定しなきゃ駄目ですね。

 

ログインしたい

ログイン画面出ただけではどうしようもないので、ユーザー作りましょう。

 

cpioに固める前に、アカウント情報をファイルシステム上に乗っけます。(cpioに固めた後はファイルシステムに手出しできないので。ログインもできてないですし)

minirootfsの展開先にchrootし、minirootfs上のadduserコマンドでユーザーを作れば、minirootfs上にアカウント情報が作成されます。

$ chroot . addgroup alpine

$ chroot . adduser -S -s /bin/sh -G alpine alpine

$ chroot . addgroup alpine wheel

$ chroot . sh -c "echo '%wheel ALL=(ALL) NOPASSWD: ALL' >> /etc/sudoers"

 

alpineユーザーを作り、ついでにwheelにも追加します。wheelはパスワード無しでsudoできるようにします。

 

sudoするためにはminirootfs上にsudoコマンドが無いといけないので、sudoをapkでインストールします。僕はsshサーバーを立てたかったので、ついでにdropbearと、dropbearを自動起動するためにopenrcも入れました。

 

$ chroot . apk add --no-cache --initdb sudo dropbear openrc

 

これだけで終わりと言いたい所ですが、手元だとpermissionエラーでログインできませんでした。minirootfsを展開後に、/(minirootfsのroot)を755に設定する必要があるようです。

 

/etc/network/interfacesの設定

これで無事ログインできたのですが、"rc-service dropbear start"ってしてdropbearを起動しようとすると、「/etc/network/interfacesがナイヨ」と怒られます。

 

というわけで、/etc/network/interfacesを整備しましょう。

 

auto lo

iface lo inet loopback

 

auto eth0

     iface eth0 inet dhcp

こうすると、ifconfigでloとeth0が見えるようになります。でも相変わらず通信できません。ていうか、それ以前にdropbearを起動する事でnetworkingが起動するってどういう事よ、最初からnetworkingは起動しててよ、みたいな気になりますよね。

 

openrcの設定

なので、openrcがinitを自動起動してくれるようにします。

$ chroot . rc-update add dropbear default

$ chroot . rc-update add networking boot

これが上手く動けば良いんですが、後者はなぜかSEGVして動きませんでした。コードを読むと、bootの時だけ何か特殊な処理が走るっぽいんですよね。その中でコケてるらしい。もしかしたらdocker環境上で実行したのが悪かったのかもしれません。

 

で、コードいわく、こいつはシンボリックリンクを貼る以上の事をやってなさそうなので、自分でやります。こんな感じ。

 

$ chroot . ln -s /etc/init.d/networking /etc/runlevels/boot

 

/etc/runlevels/bootは存在しないので、事前に作っておく必要があります。

 

なんかnetworkingとdropbearの設定をするんだったら、ついでに他のサービスも全部立てとこうぜ、みたいな気持ちになったので、alpineのVMイメージの設定と比較して、全部設定する事にしました。

 

$ chroot . install -d /etc/runlevels/boot /etc/runlevels/default /etc/runlevels/sysinit /etc/runlevels/shutdown /etc/runlevels/nonetwork

$ chroot . ln -s /etc/init.d/acpid /etc/runlevels/default

$ chroot . ln -s /etc/init.d/bootmisc /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/crond /etc/runlevels/default

$ chroot . ln -s /etc/init.d/devfs /etc/runlevels/sysinit

$ chroot . ln -s /etc/init.d/dmesg /etc/runlevels/sysinit

$ chroot . ln -s /etc/init.d/dropbear /etc/runlevels/default

$ chroot . ln -s /etc/init.d/hostname /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/hwclock /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/hwdrivers /etc/runlevels/sysinit

$ chroot . ln -s /etc/init.d/killprocs /etc/runlevels/shutdown

$ chroot . ln -s /etc/init.d/loadkmap /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/mdev /etc/runlevels/sysinit

$ chroot . ln -s /etc/init.d/modules /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/mount-ro /etc/runlevels/shutdown

$ chroot . ln -s /etc/init.d/networking /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/savecache /etc/runlevels/shutdown

$ chroot . ln -s /etc/init.d/swap /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/sysctl /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/syslog /etc/runlevels/boot

$ chroot . ln -s /etc/init.d/urandom /etc/runlevels/boot

 

※これは最終系のコードで、後の話でapkによってインストールされるサービスも登場しています。

 

これによって、devfsサービスが自動起動するようになり(/etc/inittabの最初の、"::sysinit:/sbin/openrc sysinit"の中で起動される)、先程のmount文は不要になりました。

 

アドレスが割当らない

さて、これでdropbearを手動で起動しなくても良くなりましたし、networkingも最初から起動するようになりました。でも相変わらずssh接続ができません。ネットワークが死んでます。


しかもこれ、何か変なんですよね。ifconfig走らせるとIPv6アドレスは何か割当たってるっぽいし、udhcpc走らせるとちゃんとIPアドレスは振ってくる。でもifconfigにinet addr(IPv4アドレス)は割当らないみたいな。

なんでじゃなんでじゃって言いながら調べてたら、これが見つかり、「ふんふん、busyboxがudhcpcのサンプルスクリプトを提供してるのか、でもminirootfsには無いな」となり、じゃあサンプルスクリプトコピペするか、なんて思いながらググってたらこんなのを見つけました。

 

Alpine Linux packages

 

どうやらbusybox-initscriptsをインストールすると、/usr/share/udhcpc/default.scriptが手に入るらしい!!

 

$ chroot . apk add --no-cache --initdb busybox-initscripts

 

ちゃんとifconfigするとIPv4アドレスも割り当たるようになったし、apkでパッケージもダウンロードできるようになりました。めでたしめでたし。