品川准教授のブログ

東京大学で准教授をしています。主に研究分野(OSや仮想化などのシステムソフトウェア)に関連したことを気まぐれに書きます。

国際会議 OSDI 2020

14th USENIX Symposium on Operating Systems Design and Implementation で個人的に興味のある論文の一覧です。概ね興味の順番にソートしてあります。

最近のシステム系国際会議は分野が発散してきているので、興味のある分野に絞ったリストを作ることが必要そうです(それでも数が多いですが)。

目次


概要

  • バーチャル会議
  • 投稿数???本、採択数??本、採択率??%

論文リスト

OS系

安全なオペレーティングシステムにおける隔離と通信

(Isolation, and Communication in a Safe Operating System) www.usenix.org

Theseus:OSの構造と状態管理の実験

(Theseus: An Experiment in OS Structure and State Management)
学会ページ: https://www.usenix.org/conference/osdi20/presentation/boos
論文(著者版): https://www.yecl.org/publications/boos2020osdi.pdf
コード: https://github.com/theseus-os/Theseus

Rust で書かれた実験的OSである Theseus の経験を報告している。OSのモジュール性を向上させるために、コンポーネント間で持つ状態の数を減らし、OSの機能の多くをコンパイラに移動させることを目指している。

近年のシステムソフトウェアでは (state spill)https://doi.org/10.1145/3064176.3064205 というあるコンポーネント内に他のコンポーネントからの影響が永続的に残ってしまうという状況がしばしば起こっている。これにより、フォールトトレラントやライブアップデートなどで問題が発生する。例えば、Android の system service で state spill が発生すると、その system service が落ちたときに、それを使っていないアプリも巻き添えにして落ちてしまうことがある。

システムを進化可能かつ高可用性にすることは、ハードウェアの冗長化は高くつくが信頼性は必要といった環境においては特に重要な機能である。しかし、例えばソフトウェアアップデートなどでダウンタイムが発生したり、状態が失われて復旧に時間がかかるなど、実際にはシステムが落ちないようにすることは難しい。

この論文では、state spill の問題に対処するために、Rust を使って一からOSを書く試みをしている。Rust の ownership model は、コンポーネント間で隔離をしつつゼロコストでコンポーネント間の状態転送がおこなえるなど、この目的に適している。著者らの最初の実験的試みにより、2つのことが分かった。1つ目は、state spill を軽減するためにはOSの構造を考え直す必要があるということである。これは、state spill はOSがどのようにモジュール化されているかに大きく依存しているからである。2つ目は、Rust のようなモダンな言語は、単に安全なOSコードを書くためだけでなく、OSの動作のある種の正確性不変条件を静的に保証するためにも使えるということである。

実験の結果得られたものは Theseus OS である。Theseus の1つ目の貢献は、多くの小さなコンポーネントからなる新しい OS 構造を持っていて、実行時の永続的な境界が明確に定義されていることである。これにより、コンポーネントの動的進化や障害回復を容易にしている。

Theseus の2つ目の貢献は、OSの実行環境を実装言語のランタイムモデルにマッチングさせ、言語レベルの機構を用いてOS自体を実装するという、「言語内」OS設計アプローチに貢献していることである。言語内設計により、コンパイラがコードの挙動の理解においてギャップがないようにOSコードに安全性チェックを適用することが可能になるほか、セマンティックエラーを実行時の障害からコンパイル時のエラーへと移行させることができる。言語内設計は、安全性を超えてコンパイラがOSのセマンティック不変条件を静的にチェックし、リソース管理を行うことを可能にしている。

カーネル仮想マシンのためのジャスト・イン・タイム・コンパイラの仕様、実装及び検証

(Specification, implementation, and verification of just-in-time compilers for an in-kernel virtual machine) www.usenix.org

OSの抽象化はFPGA上で意味があるか?

(Do OS abstractions make sense on FPGAs?) www.usenix.org

PipeSwitch: ディープラーニングアプリケーションのための高速なパイプラインコンテキストスイッチング

(PipeSwitch: Fast Pipelined Context Switching for Deep Learning Applications) www.usenix.org


高速化

高速でスケーラブル、柔軟なストレージ仮想化のためのFPGA支援による仮想デバイスエミュレーション機構

(An FPGA-assisted Virtual Device Emulation Mechanism for Fast, Scalable, and Flexible Storage Virtualization) www.usenix.org

単一サーバによる100Gbps侵入防止の実現

(Achieving 100Gbps Intrusion Prevention on a Single Server) www.usenix.org

ネットワークファンクションのためのシンプルで高速なNICドライバモデル

(A Simpler and Faster NIC Driver Model for Network Functions) www.usenix.org

Frenzy:マルチテナントネットワーク用のプログラマブルな高性能NIC

(Frenzy: A Programmable High-Performance NIC for Multi-tenant Networks) www.usenix.org

hXDP:FPGA NICでの効率的なソフトウェアパケット処理

(hXDP: Efficient Software Packet Processing on FPGA NICs) www.usenix.org


セキュリティ・バグ

マッピングされていない投機コントラクトを使用したトランジェント実行攻撃の効率的な軽減

(Efficiently Mitigating Transient Execution Attacks using the Unmapped Speculation Contract) www.usenix.org

Gauntlet: プログラマブルパケット処理のためのコンパイラにおけるバグ発見

(Gauntlet: Finding Bugs in Compilers for Programmable Packet Processing) www.usenix.org

本番環境のクラウドVMの中断を回避するための予測的で適応的な障害の軽減

(Predictive and Adaptive Failure Mitigation to Avert Production Cloud VM Interruptions) www.usenix.org

本番環境での失敗を防ぐためのコンテキストにおける構成変更のテスト


(Testing Configuration Changes in Context to Prevent Production Failures) www.usenix.org

グローバルからローカルの休止へ:マルチスレッドプロセスのウェイトフリーコードパッチング

(From Global to Local Quiescence: Wait-Free Code Patching of Multi-Threaded Processes) www.usenix.org


ストレージ

Assise: 分散ファイルシステムにおけるNVMコロケーションによる性能と可用性

(Assise: Performance and Availability via NVM Colocation in a Distributed File System) www.usenix.org arXiv

CrossFS: レイヤ横断型ダイレクトアクセスファイルシステム

(CrossFS: A Cross-layered Direct-Access File System) www.usenix.org

LinnOS: 予測不可能なフラッシュストレージにおける予測可能性

(LinnOS: Predictability on Unpredictable Flash Storage) www.usenix.org

AGAMOTTO:あなたの永続メモリアプリケーションはどのくらい永続的ですか?

(AGAMOTTO: How Persistent is your Persistent Memory Application?) www.usenix.org

ストレージシステムは分散システム(従ってそれらをそのように確認すべし!)


(Storage Systems are Distributed Systems (So Verify Them That Way!)) www.usenix.org


大規模システム

クラウドプラットフォームにおける資源収穫VMに対するSLOの提供

(Providing SLOs for Resource-Harvesting VMs in Cloud Platforms) www.usenix.org

CacheLibキャッシングエンジン:大規模な設計と経験

(The CacheLib Caching Engine: Design and Experiences at Scale) www.usenix.org

Protean:大規模なVM割り当てサービス

(Protean: VM Allocation Service at Scale) www.usenix.org

Twine: 共有インフラのためのクラスタ管理システムの進化

(Twine: Evolving a Cluster Management System for Shared Infrastructure) www.usenix.org (Facebookブログ)

部分ネットワーク分断に対する汎用フォールトトレラント技術に向けて

(Toward a Generic Fault Tolerance Technique to Partial Network Partitioning) www.usenix.org


クラスタ

クラスタースケジューリング改善のためのジョブ間依存関係明確化


(Unearthing inter-job dependencies for better cluster scheduling) www.usenix.org Talk

ディープラーニングワークロードのための不均一性を意識したクラスタースケジューリングポリシー

(Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads) www.usenix.org Microsoft Research

国際会議 EuroSys 2020

国際会議 EuroSys 2020 (The European Conference on Computer Systems) のメモです。EuroSys は SOSP, OSDI に次ぐシステムソフトウェア系のトップカンファレンスです。

※1 随時更新していますが、スローペースです。
※2 興味の程度によって分量に差があります。
※3 ざっと眺めただけですので、内容も間違っているかもしれません。

目次


概要

  • バーチャル会議(slack + Discord + YouTube + Zoom)
  • 投稿数234本、採択数43本、採択率18.4%
  • 2 round review

2020年4月28日(火)

Session 1: Kernel – Efficient data structures – Security – Programming Languages and Verification

TLBシュートダウンを邪魔するな!

(Don’t shoot down TLB shootdowns! ) Nadav Amit, Amy Tai, Michael Wei (VMware Research Group)

[Paper] [Video]

複数コアのTLBをフラッシュするTLBシュートダウンを高速化する話。主に以下の4つの手法を用いる。

  • 並行フラッシュ: 従来は自コアでTLBフラッシュしてから他コアにTLBフラッシュを送っていたのに対し、先に他コアにTLBフラッシュのIPIを送ってから自コアでTLBフラッシュして平行処理にする(30年前に提案済みだが忘れられていた)
  • キャッシュライン統合: 従来はSMPに関する情報とTLBフラッシュに関する情報が共有メモリ上の別々のデータ構造に置かれていてコア間の情報共有時にキャッシュミスやミスアラインによるTLBミスが発生していたのに対し、SMP情報とTLBフラッシュのデータ構造をまとめてキャッシュラインを統合することでキャッシュミスを減らす
  • 早期応答: 従来はIPIを受け取ったらTLBフラッシュしてから応答IPIを返していたのに対し、先に応答IPIを返してからTLBフラッシュする
  • コンテキスト内フラッシュ: 従来はKPTIのカーネルテーブルをフラッシュしてからすぐにユーザテーブルをフラッシュしていたのに対し、ユーザテーブルのフラッシュを当該プロセスにコンテキストスイッチするまで遅らせておいてまとめてフラッシュする。

他にも以下の最適化をおこなう。

  • Userspace-safe batching
  • Avoid TLB flushes on Copy-on-Write
  • TLB flushes in virtualization

Mousse: 野生環境でのプログラムの選択的シンボリック実行のためのシステム

(Mousse: A System for Selective Symbolic Execution of Programs with Untamed Environments) Nadav Amit, Amy Tai, Michael Wei (VMware Research Group)

[Paper] [Video]

制御された仮想環境ではなくデバイスドライバやカスタムハードウェアなどを含むような仮想環境ではない「野生(Untammed)」環境においてシンボリック実行をおこなう話。

実環境、高性能、使いやすさの3つを目標として、以下の3つのソリューションを使う。

  • プロセスレベルSSE(選択的シンボリック実行): VMを使わずユーザレベルプロセスで対象プログラムとSSEエンジンの両方を動かす
  • 実行環境を意識した並行性: 実行環境の知識を持ったソフトウェア層である呼び出しが実行環境の状態を変更するかどうかを判断して、並行実行できる場合は複数のパスを並行して実行する
  • 分散実行: サーバと連携して複数の物理デバイスで実行パスを並列検査する

5つのAndroid OSのサービスで実験して、実行環境を意識した平行性により実行時間が最大59%削減、分散実行では最大63%削減した。

NUMAシステム上でのRCUのためのHTMに基づく更新側同期

(An HTM-Based Update-side Synchronization for RCU on NUMA systems) SeongJae Park (Amazon), Paul E. McKenney (Facebook), Laurent Dufour (IBM Linux Technology Center), Heon Y. Yeom (Seoul National University)

[Paper] [Video]

Keystone: トラステッド実行環境を構築するためのオープンフレームワーク

(Keystone: An Open Framework for Architecting Trusted Execution Environments) Dayeol Lee, David Kohlbrenner, Shweta Shinde, Krste Asanovic, Dawn Song (UC Berkeley) [Paper] [Video]

ハードウェアエンクレーブを用いた忘却型協調分析

(Oblivious Coopetitive Analytics Using Hardware Enclaves ) SeongJae Park (Amazon), Paul E. McKenney (Facebook), Laurent Dufour (IBM Linux Technology Center), Heon Y. Yeom (Seoul National University)

[Paper] [Video]


2020年4月29日(水)

Session 2: Kernel – Efficient data structures – Programming Languages and Verification

Sponsored by Microsoft

Ipanemaによる証明可能なマルチコアスケジューラ: ワークコンサーベーションの応用

(Provable Multicore Schedulers with Ipanema: Application to Work Conservation) Baptiste Lepers (University of Sydney), Redha Gouicem (Sorbonne University/LIP6/Inria), Damien Carver (Sorbonne University/Inria/LIP6), Jean-Pierre Lozi (Oracle Labs), Nicolas Palix (Université Grenoble Alpes), Virginia Aponte (CNAM), Willy Zwaenepoel (University of Sydney and EPFL), Julien Sopena (LIP6 (UPMC/CNRS) – Inria), Julia Lawall (Inria/LIP6), Gilles Muller (INRIA), Jean-Pierre Lozi (Oracle Labs / Université Nice Sophia Antipolis)


To be continued...

国際会議 SOSP 2019

2019年10月28日~30日にカナダで開催されたシステムソフトウェア系の最高峰の国際会議 The 27th ACM Symposium on Operating Systems Principles (SOSP 2019) で発表された論文の中で個人的に興味のあるものをリストアップしています。

※1 随時更新していますが、スローペースです。
※2 興味の程度によって分量に差があります。
※3 ざっと眺めただけですので、内容も間違っているかもしれません。

目次


概要

  • 参加者580名くらい
  • 投稿数276本、採択数38本、採択率14%
  • 査読数: 3 (1st round) + 2 or 3 (2nd round) + α
  • 査読プロセス: 投稿276本 -> (online discussion ) -> 81本 -> (1.5-day in-person PC meeting) -> 38本

Session 1: Machines, Learning

省略


Session 2: It Must Be Secure

Teechain: 非同期ブロックチェーンアクセスによる安全な決済ネットワーク
(Teechain: A Secure Payment Network with Asynchronous Blockchain Access)

Joshua Lind (Imperial College London), Oded Naor (Technion), Ittay Eyal (Technion), Florian Kelbert (Imperial College London), Emin Gun Sirer (Cornell University), Peter Pietzuch (Imperial College London) https://doi.org/10.1145/3341301.3359627doi.org https://arxiv.org/pdf/1707.05454.pdf

ビットコインなどのブロックチェーンで、Trusted Execution Environment(TEE)を使ってオフチェーンのトランザクションを非同期かつ安全に実行できるレイヤ2の決済ネットワーク Teechain を提案している。

ベースとなるブロックチェーンへのアクセスを意図的に遅延させることで資金を盗む攻撃を防ぐために、Intel SGX などの TEE で動作する「金庫」を作り、一時的に担保資金を確保しておくことで、2者間で非同期かつ安全に取引ができる。

TEE だけでは foreshadow などによって攻撃される可能性があるので、複数人の「委員会」を構成して矛盾が生じたら元の blockchain にフォールバックする。

Notary: 安全なトランザクション承認のためのデバイス
(Notary: A Device for Secure Transaction Approval)

Anish Athalye (MIT CSAIL), Adam Belay (MIT CSAIL), Frans Kaashoek (MIT CSAIL), Robert Morris (MIT CSAIL), Nickolai Zeldovich (MIT CSAIL)

https://doi.org/10.1145/3341301.3359661doi.org https://pdos.csail.mit.edu/papers/notary:sosp19.pdf

ビットコインの決済などユーザの重要な承認事項を安全に伝えるために、小さなディスプレイとボタンの付いた専用 USB スティックを使って、複数の承認エージェントを安全に動作させるリセットベースの切り替え手法(reset-based switching)を提案している。

エージェントコードとカーネルを物理的に分離した SoC 上で実行したり、ハードウェアの RTL レベルので設計及びソフトウェアの検証などをおこなうとともに、エージェント切替時にハードウェアの完全リセットをおこなってCPUやRAMなどが検証された初期状態になるようにすることで、カーネルのバグやサイドチャネル攻撃などによるエージェント間の漏洩が起きないことを保証している。ARM と RISC-V に基づく実機を実際に作って有効性を検証している。

エージェントはオフラインでインストールすることを想定→正しいアプリだけがインストールされる。 TCBは4000行→formal verificationも可能だろう。


Session 3: Systems: Still Buggy

CrashTuner: メタ情報解析によるクラウドシステムのクラッシュ回復バグの検出
(CrashTuner: Detecting Crash Recovery Bugs in Cloud Systems via Meta-info Analysis)

Jie Lu (The Institute of Computing Technology of the Chinese Academy of Sciences), Chen Liu (The Institute of Computing Technology of the Chinese Academy of Sciences), Lian Li (The Institute of Computing Technology of the Chinese Academy of Sciences), Xiaobing Feng (The Institute of Computing Technology of the Chinese Academy of Sciences), Feng Tan (Alibaba Group), Jun Yang (Alibaba Group), Liang You (Alibaba Group)

https://doi.org/10.1145/3341301.3359645doi.org

TBA

変曲点仮説:障害の根本原因を突き止めるための原理的デバッグ手法
(The Inflection Point Hypothesis: A Principled Debugging Approach for Locating the Root Cause of a Failure)

Yongle Zhang (University of Toronto), Kirk Rodrigues (University of Toronto), Yu Luo (University of Toronto), Michael Stumm (University of Toronto), Ding Yuan (University of Toronto)

https://doi.org/10.1145/3341301.3359650doi.org

拡張可能ファジングフレームワークによるファイルシステムのセマンティックバグの発見
(Finding Semantic Bugs in File Systems with an Extensible Fuzzing Framework)

Seulbae Kim (Georgia Institute of Technology), Meng Xu (Georgia Institute of Technology), Sanidhya Kashyap (Georgia Institute of Technology), Jungyeon Yoon (Georgia Institute of Technology), Wen Xu (Georgia Institute of Technology), Taesoo Kim (Georgia Institute of Technology)

https://doi.org/10.1145/3341301.3359662doi.org

https://gts3.org/~sanidhya/pubs/2019/hydra.pdf

原理的にはファイルシステムの任意の種類のバグを発見できる拡張可能 fuzzing フレームワーク HYDRA を提案している。

HYDRA は fuzzing のための構成要素として、入力ミューテータ、フィードバックエンジン、libOSベースの実行機構、テストケースを最小化したバグ再生成器などを提供している。これにより、開発者がバグを発見するためのコアロジックの作成に集中できる。実際に、クラッシュ不整合、POSIX違反、ロジックアサーション違反、メモリエラーの4つのバグを発見するチェッカーを作って有効性を確認した。その結果、Crash Hoare logic を使ってそのようなバグは存在しないことを証明したとされていた FSCQ においてさえ1個のバグを発見したほか、4個のPOSIX違反を含むLinuxファイルシステムの新しいバグを91個発見した。

ファジングでメモリエラーだけでなく、セマンティックバグも見つけられるのがIEEE S&P論文との違い。 セマンティックはクラッシュしないので従来のファジングで見つけずらい。 チェッカーでチェックして、フィードバックする。

効率的でスケーラブルなスレッド安全性違反の検証 --- テスト中に数千個の並行バグを発見
(Efficient and Scalable Thread-Safety Violation Detection --- Finding thousands of concurrency bugs during testing)

Guangpu Li (University of Chicago), Shan Lu (University of Chicago), Madanlal Musuvathi (Microsoft Research), Suman Nath (Microsoft Research), Rohan Padhye (Berkeley)

https://doi.org/10.1145/3341301.3359638doi.org

https://www.microsoft.com/en-us/research/uploads/prod/2019/09/sosp19-final193.pdf

(Best Paper Award)

マイクロソフトで実際に使われている並行バグ発見器 TSVD を提案している。

従来手法のようにランダムに遅延を挿入するなどコストの高い同期解析を採用するのではなく、スレッドセーフでないメソッドの呼び出し行動を同期を使わずに軽量に監視して、バグが疑われるポイントを動的に特定する。その後、対応する遅延を挿入してプログラムをスレッドセーフでない動作に誘導し、その能力を学習し、次のテスト時にもその学習結果を活用する。実際にマイクロソフトの数千のプロジェクトで1000以上のスレッドセーフ違反を発見した。


Session 4: Keeping Things Private

省略


Session 5: It Must Be Correct

Serval によるシステムコードの自動検証のためのシンボリック評価の拡張
(Scaling Symbolic Evaluation for Automated Verification of Systems Code with Serval)

Luke Nelson (University of Washington), James Bornholt (University of Washington), Ronghui Gu (Columbia University), Andrew Baumann (Microsoft Research), Emina Torlak (University of Washington), Xi Wang (University of Washington) https://doi.org/10.1145/3341301.3359641doi.org https://www.cs.utexas.edu/~bornholt/papers/serval-sosp19.pdf (Best Paper Award)

システムソフトウェアのためのシンボリック評価を用いた自動検証器を開発するためのフレームワーク Serval を提案している。

Serval では、まず対象となるCPUの命令セットのインタプリタRosette というシンボリック実行をするための専用言語で記述し、それを検証器へと格上げ("lift")する。実際に RISC-V や x86-32、LLVM、BPF の検証器を生成した。それらはシンプルで簡単に理解できるうえ、Rosette の特徴も利用できる。さらに検証器間での再利用や相互運用も容易になる。パス爆発の問題に対処するために、symbolic profiling の技術を用いてボトルネックとなる箇所を特定し、symbolic optimizations によってドメイン固有の知識を使ってシンボリック実行の性能を向上させる。 既存のシステムにどれだけ適用可能か検証するために、Coq で検証された x86 上で動作するセキュリティモニタ CertiKOS や、Dafny で検証された ARM の TrustZone を使ったセキュリティモニタ Komodo に対して適用して、それらが Serval の対象となりうることを確認した。

Perennial による並行でクラッシュセーフなシステムの検証
(Verifying Concurrent, Crash-safe Systems with Perennial)

Tej Chajed (MIT CSAIL), Joseph Tassarotti (MIT CSAIL), Frans Kaashoek (MIT CSAIL), Nickolai Zeldovich (MIT CSAIL) https://doi.org/10.1145/3341301.3359632doi.org https://people.csail.mit.edu/nickolai/papers/chajed-perennial.pdf

並行かつクラッシュセーフなシステムを検証するフレームワーク Perennial を提案している。

並行実行するシステムを検証する既存のフレームワーク Iris をベースにして、回復リース、回復補助、バージョン化メモリの3つの技術を導入して拡張した。開発と導入を容易にするために、Go言語のサブセット Goose を作って、Go スレッドやデータ構造、POSIXファイルシステムAPI を Perennial のモデルに変換できるようにした。実際に、Perennial と Goose を使って、クラッシュセーフで並行実行可能なメールサーバを実装した。

AtomFS ファイルシステムを検証するためのヘルパを用いた並行関係論理の使用
(Using Concurrent Relational Logic with Helpers for Verifying the AtomFS File System)

Mo Zou (Shanghai Jiao Tong University), Haoran Ding (Shanghai Jiao Tong University), Dong Du (Shanghai Jiao Tong University), Ming Fu (Huawei Technologies Co. Ltd), Ronghui Gu (Columbia University), Haibo Chen (Shanghai Jiao Tong University) https://doi.org/10.1145/3341301.3359644doi.org https://www.cs.columbia.edu/~rgu/publications/sosp19-zou.pdf

アプリケーションに線形化されたインターフェースを提供する、形式検証され細粒度で並行な初めてのファイルシステムAtomFS を提案している。

著者らの観測によると、線形性の証明に際して最も難しいのはパス間依存性である。パス間依存性は、rename のようなたった一つの操作でも他の操作のパス一貫性を損なうものであり、扱いが非常に難しい。この論文では、ヘルパ付き並行関係論理(Concurrent Relational Logic with Helpers: CRL-H)という検証された並行ファイルシステムを構築するためのフレームワークを提案している。

検証の専門知識を使わないソフトウェアネットワーク機能の検証
(Verifying Software Network Functions with No Verification Expertise)

Arseniy Zaostrovnykh (EPFL), Solal Pirelli (EPFL), Rishabh Iyer (EPFL), Matteo Rizzo (EPFL), Luis Pedrosa (EPFL), Katerina Argyraki (EPFL), George Candea (EPFL) https://doi.org/10.1145/3341301.3359647doi.org https://dslab.epfl.ch/pubs/vigor.pdf

性能と生産性を維持しつつ、正しいことが保証されているソフトウェアネットワークミドルボックスを構築・実行するためのソフトウェアスタックおよびツールチェーンである Vigor を提案している。


Session 7: The Revolution Will Be Distributed

分散ストレージのバックエンドとしてのファイルシステムの不適合: 10年に渡るCephの進化からのレッスン
(File Systems Unfit as Distributed Storage Backends: Lessons from 10 Years of Ceph Evolution)

Abutalib Aghayev (Carnegie Mellon University), Sage Weil (Red Hat Inc.), Michael Kuchnik (Carnegie Mellon University), Mark Nelson (Red Hat Inc.), Gregory R. Ganger (Carnegie Mellon University), George Amvrosiadis (Carnegie Mellon University) https://doi.org/10.1145/3341301.3359656doi.org https://www.pdl.cmu.edu/PDL-FTP/Storage/ceph-exp-sosp19.pdf

分散ファイルシステム Ceph の経験から新しく作り直したバックエンドストレージ BlueStore を提案している。

従来のファイルシステムの問題点としては、(1) ゼロオーバーヘッドのトランザクション機構を作ることが困難、(2) ローカルレベルでのメタデータの性能が分散レベルでの性能にも大きく影響を与える点、(3) 新しいストレージハードウェアをサポートするのが苦痛なほど遅い点、がある。BluStore はユーザ空間で動作してI/Oスタックを完全にコントロールすることで、空間効率の良いメタデータやデータチェックサム、イレイジャーコード化されたデータの高速な更新、インライン圧縮、性能のばらつきの低減、ローカルファイルシステムの性能上の欠点の回避などを実現している。


Session 8: Net Work

Snap: ホストネットワーキングへのマイクロカーネルアプローチ
(Snap: a Microkernel Approach to Host Networking)

Michael Marty (Google), Marc de Kruijf (Google), Jacob Adriaens (Google), Christopher Alfeld (Google), Sean Bauer (Google), Carlo Contavalli (Google), Michael Dalton (Google), Nandita Dukkipati (Google), William C. Evans (Google), Steve Gribble (Google), Nicholas Kidd (Google), Roman Kokonov (Google), Gautam Kumar (Google), Carl Mauer (Google), Emily Musick (Google), Lena Olson (Google), Erik Rubow (Google), Michael Ryan (Google), Kevin Springborn (Google), Paul Turner (Google), Valas Valancius (Google), Xi Wang (Google), Amin Vahdat (Google) https://doi.org/10.1145/3341301.3359657doi.org

TBA

Taiji: エッジにおける大規模インターネットサービスのためのグローバルユーザトラフィックの管理
(Taiji: Managing Global User Traffic for Large-Scale Internet Services at the Edge)

David Chou (Facebook), Tianyin Xu (UIUC), Kaushik Veeraraghavan (Facebook), Andrew Newell (Facebook), Sonia Margulis (Facebook), Lin Xiao (Facebook), Pol Mauri Ruiz (Facebook), Justin Meza (Facebook), Kiryong Ha (Facebook), Shruti Padmanabha (Facebook), Kevin Cole (Facebook), Dmitri Perelman (Facebook) https://doi.org/10.1145/3341301.3359655doi.org

TBA


Session 9: The Persistence Of Memory

KVell: 高速な永続キーバリューストアの設計と実装
(KVell: the Design and Implementation of a Fast Persistent Key-Value Store)

Baptiste Lepers (University of Sydney), Oana Balmau (University of Sydney), Karan Gupta (Nutanix Inc.), Willy Zwaenepoel (University of Sydney and EPFL) https://doi.org/10.1145/3341301.3359628doi.org

TBA

RECIPE: 並行DRAMインデックスの永続メモリインデックスへの変換
(RECIPE: Converting Concurrent DRAM Indexes to Persistent-Memory Indexes)

Se Kwon Lee (University of Texas at Austin), Jayashree Mohan (University of Texas at Austin), Sanidhya Kashyap (Georgia Tech), Taesoo Kim (Georgia Tech), Vijay Chidambaram (University of Texas at Austin and VMware Research) https://doi.org/10.1145/3341301.3359635doi.org

並行DRAMインデックスを永続メモリのためのクラッシュ整合性のあるインデックスに変換する原理的なアプローチである RECIPE を提案している。

ユーザ空間NVMファイルシステム ZoFS における性能と保護
(Performance and Protection in the ZoFS User-space NVM File System)

Mingkai Dong (Shanghai Jiao Tong University), Heng Bu (Shanghai Jiao Tong University), Jifei Yi (Shanghai Jiao Tong University), Benchao Dong (Shanghai Jiao Tong University), Haibo Chen (Shanghai Jiao Tong University)
https://dl.acm.org/authorize?N695045
https://www.cs.utexas.edu/~vijay/papers/sosp19-recipe.pdf

ユーザ空間からでも安全に管理できる不揮発メモリ(NVM)上のファイルシステム ZoFS を提案している。

NVM上のファイルシステムをユーザレベルで管理すると、カーネルアクセスのオーバーヘッドを削減できるため高速化出来るが、従来のNVM向けファイルシステムでは、ファイルシステムを保護するためにメタデータの管理はカーネルレベルで行わなければいけなかった。

ZoFSでは、ファイルのパーミッションはめったに変わらないことに着目して、ファイルのパーミッションが同じファイルをまとめて置いておくNVMページの集まりである coffer という新しい抽象化を導入し、coffer 単位でプロセスに割り当てることでユーザ空間からメタデータの操作をおこなえるようにする。coffer のプロセスへの割当自体はカーネルが管理することでセキュリティは担保しつつ、一旦割り当てたらメタデータを含むファイルシステムの操作をユーザレベルで完結できるようにする。プロセスのバグによってファイルシステムが破損する stray write が発生する可能性を減らすために、Intel MPK を用いてメタデータを変更する瞬間だけページの書き込み権限を与えることで、通常動作時にメタデータが破壊される可能性を減らす。

実験の結果、ZoFS は LevelDB のレイテンシを最大82%削減し、SQLiteスループットを最大31%向上させることが出来た。

SplitFS: 永続メモリのためのファイルシステムにおけるソフトウェアオーバーヘッドの削減
(SplitFS: Reducing Software Overhead in File Systems for Persistent Memory)

Rohan Kadekodi (University of Texas at Austin), Se Kwon Lee (University of Texas at Austin), Sanidhya Kashyap (Georgia Tech), Taesoo Kim (Georgia Tech), Aasheesh Kolli (Penn State University and VMware Research), Vijay Chidambaram (University of Texas at Austin and VMware Research) https://arxiv.org/pdf/1909.10123.pdf

最先端のシステムと比べてもソフトウェアオーバーヘッドを大幅に削減した永続メモリ(Persistent Memory: PM)のためのファイルシステム SplitFS を提案している。

SplitFS はユーザ空間のライブラリファイルシステムと既存のカーネルのPMファイルシステムの間の責任をうまく分割している。ユーザ空間のファイルシステムは、データ操作を処理するために、POSIXファイルシステムを横取りし、ファイルをメモリマップし、読み込みや更新をプロセッサのロード・ストア命令で処理する。メタデータ操作はカーネルのPMファイルシステムext4 DAX)でおこなう。SplitFS は relink という、ファイルのある領域を別のファイルの領域へ物理的なデータ移動なしに行う機能を追加して、ファイルの追加やアトミックなデータ操作をサポートする。さらに、SplitFS は3つの一貫性モデル(POSIX, sync, strict)を提供する。SplitFS は NOVA と比べてソフトウェアのオーバーヘッドを最大4倍、ext4 DAX と比べて17倍削減できた。LevelDB で YCSB を走らせたベンチマークなどで、アプリケーションの性能が ext4 DAX や NOVA と比べて最大2倍向上した。


Session 11: The Final Session

Linuxのコア操作の性能進化の分析
(An Analysis of Performance Evolution of Linux's Core Operations)

Xiang (Jenny) Ren (The University of Toronto), Kirk Rodrigues (The University of Toronto), Luyuan Chen (The University of Toronto), Camilo Vega (The University of Toronto), Michael Stumm (The University of Toronto), Ding Yuan (The University of Toronto) https://doi.org/10.1145/3341301.3359640doi.org

Linux カーネルは過去7年で基本性能がどんどん遅くなって。select() は2年前と比べて最大100%の性能低下。要因はセキュリティ強化、新機能、設定ミス。

セキュリティ対策による性能低下は、Meltdown 対策の KPTI で recv() が最大63%、Spectre v2 対策の Retpoline でpoll() が最大89%、SLAB freelist dandomization で epoll() が最大41%、usercopy の強化で select() が最大18%。

新機能による性能低下は、fault around(page fault 発生時に周辺ページもついでにマップする)で page fault が最大54%、cgroup で munmap が最大81%、transparent huge table デフォルト無効化で read() が最大83%、userspace page fault handling でfork()が4%。

設定ミスによる性能低下は、forced context tracking(reduced scheduling-clock ticks 開発のためのデバック機能)無効化し忘れで最大100%、TLB layout change で munmap() が最大50%。CPU idle power-state support はHaswell上の select() で31%の性能向上があるが、LTS に backport されていない。

上記の11個の要因中8つはカーネルの reconfiguration で、残り3つは簡単なパッチで回避可能。その結果、Redis, Apache, Nginx benchmark の性能がそれぞれ 56%, 33%, 34% まで改善した。

パッチ1: Spectre 対策の retpoline は indirect jump を予測不能にするので、indirect jump をよく使う select や poll が著しく性能低下する。対策は、セキュリティに問題のない if文+ direct jump への置き換え。

パッチ2: KPTI は TLB flush のコストが重い。PCID を使って最適化可能だが、それでも切り替えに 400-500 サイクルはかかる。PCID は CR3 に格納されており、CR3 の書き込み自体 200 サイクルかかる。

ShortCut: ほとんど決定的なコード領域の高速化
(ShortCut: Accelerating Mostly-Deterministic Code Regions)

Xianzheng Dou (University of Michigan), Peter M. Chen (University of Michigan), Jason Flinn (University of Michigan) https://doi.org/10.1145/3341301.3359659doi.org

TBA

Shuffling によるスケーラブルで実用的なロッキング
(Scalable and Practical Locking with Shuffling)

Sanidhya Kashyap (Georgia Tech), Irina Calciu (VMware Research Group), Xiaohe Cheng (Hong Kong University of Science and Technology), Changwoo Min (Virginia Tech), Taesoo Kim (Georgia Institute of Technology) https://doi.org/10.1145/3341301.3359629doi.org https://gts3.org/~sanidhya/pubs/2019/shfllock.pdf

この論文では、ロックアルゴリズムの性能に影響を与える4つの支配的要素を特定し、ロックのクリティカルパスを遅くすることなく、それらの要素を動的に調節する手法 shuffling を提案している。

ロックは高性能マルチコアシステムソフトウェアにおける重要な構成要素だが、環境が異なるとうまく性能が出ない。例えば、spinlock を NUMA で使うとキャッシュラインが頻繁に行き来することになり、一方NUMA-awareなロックはシングルスレッドの性能が出ない。この論文では、ロックの性能を与える4つの要素として、1) 異なるキャッシュ間のキャッシュライン移動、2) スレッド競合のレベル、3) コアのオーバーサブスクリプション、4) メモリフットプリントを挙げている。これに対して、shuffling ではロックの取得/開放のフェーズをロックの順番のポリシーから切り離し、クリティカルパスではない所でポリシーに基づくロック待ちのスレッドの順番入れ替えをおこなう。

ブログの引越

ブログを引っ越すことにしました。

 

新ブログ:https://utshina.hatenablog.jp/

旧ブログ:http://d.hatena.ne.jp/shina_ecc/

 

主に研究分野(OSや仮想化、セキュリティなどのシステムソフトウェア)に関することを記述します。

品川研究室 のホームページもよろしくお願いします。

mruby を Linux カーネル内で動作させる

mruby を Loadable Kernel Module (LKM) として Linux カーネル内動作させて printk する方法をメモしておきます。

1年以上前に書きかけていたものを完成させたので、mrubyのバージョンが古いです。最近のバージョンだとどうなるのかは分かりません。

mruby のビルド

まず GitHub から mruby のソースコードをダウンロードします。今回試したのは f65a39f4d19b1de019b0b805ccfb081757e5b7b5 (Wed Sep 18 20:00:35 2013 -0700) です。

$ git clone https://github.com/mruby/mruby.git
$ cd mruby
$ git checkout f65a39f4d19b1de019b0b805ccfb081757e5b7b5

次にカーネル内で動作するバージョンをクロスビルドするための設定を追加します。これにより、ホスト上で動く通常の mruby とは別に、build/kernel 以下にカーネル内動作用の mruby がビルドされます。

$ cat >> build_config.rb
MRuby::CrossBuild.new('kernel') do |conf|
  toolchain :gcc

  conf.cc.flags << "-Iinclude/kernel -mcmodel=kernel -mno-red-zone -mfpmath=387 -mno-sse -mno-sse2 -mno-mmx -mno-3dnow -msoft-float -fno-asynchronous-unwind-tables -fno-omit-frame-pointer"
  conf.cc.defines << %w(DISABLE_STDIO)
  conf.cc.defines << %w(DISABLE_FLOAT)
  conf.cc.defines << %w(MRB_INT64)
end
(ctrl-d)

次にカーネル内で動作させるためのヘッダファイルを作成します。

stdlib.h は必要最小限のものに置き換えます。これにより浮動小数点関係のエラーが減ります。

$ mkdir include/kernel
$ cat > include/kernel/stdlib.h
typedef unsigned long size_t;
void free(void *ptr);
void *realloc(void *ptr, size_t size);
int abs(int j);
unsigned long int strtol(const char *nptr, char **endptr, int base);
unsigned long int strtoul(const char *nptr, char **endptr, int base);
void exit(int status);
#define EXIT_SUCCESS 0
#define EXIT_FAILURE (-1)
void abort(void);
int atoi(const char *nptr);
# define strtod(p,e) strtol(p,e,10)
(ctrl-d)

stdarg.h は vsnprintf 関係のものだけを gcc の builtin 関数で記述します。

$ cat > include/kernel/stdarg.h
typedef unsigned long size_t;
typedef __builtin_va_list __gnuc_va_list;
typedef __gnuc_va_list va_list;
#define va_start(v,l) __builtin_va_start(v,l)
#define va_end(v)     __builtin_va_end(v)
#define va_arg(v,l)   __builtin_va_arg(v,l)
int vsnprintf(char *str, size_t size, const char *format, va_list ap);
(ctrl-d)

浮動小数点は使わないので、全部ごまかします。

$ cat > include/kernel/math.h
# define fmod(x,y) (x)
# define pow(x,y) (x)
# define log10(x) (x)
# define floor(x) (x)
# define ceil(x) (x)
# define isinf(x) 0
# define isnan(x) 0
(ctrl-d)

内部のfloat型(mrb_float)をlongで置き換えます。

$ cat > value.h.patch
--- include/mruby/value.h.orig  2013-09-19 13:24:11.378647350 +0900
+++ include/mruby/value.h       2013-09-19 16:15:33.647687793 +0900
@@ -7,7 +7,13 @@
 #ifndef MRUBY_VALUE_H
 #define MRUBY_VALUE_H

-#ifdef MRB_USE_FLOAT
+#if defined(DISABLE_FLOAT)
+  typedef long mrb_float;
+# define double long
+int sprintf(char *str, const char *format, ...);
+# define mrb_float_to_str(buf, i) sprintf(buf, "%d", i)
+# define str_to_mrb_float(buf) strtol(buf, NULL, 10)
+#elif defined(MRB_USE_FLOAT)
   typedef float mrb_float;
 # define mrb_float_to_str(buf, i) sprintf(buf, "%.7e", i)
 # define str_to_mrb_float(buf) strtof(buf, NULL)
(ctrl-d)
$ patch -p0 < value.h.patch

浮動小数点演算をしているところを片っ端から潰します。計算結果のことはここでは考えません。

$ cat > numeric.c.patch
--- src/numeric.c.orig  2013-09-19 13:24:11.389647270 +0900
+++ src/numeric.c       2013-09-19 16:34:56.098316936 +0900
@@ -209,7 +209,7 @@
       if (m < 0) {
         m -= 1;
       }
-      n = n / pow(10.0, m);
+      n = n / pow((mrb_float)10.0, m);
       m = 0;
     }
     else {
@@ -222,15 +222,15 @@

     /* puts digits */
     while (max_digit >= 0) {
-      mrb_float weight = pow(10.0, m);
-      digit = (int)floor(n / weight + FLT_EPSILON);
+      mrb_float weight = pow((mrb_float)10.0, m);
+      digit = (int)floor(n / weight + (mrb_float)FLT_EPSILON);
       *(c++) = '0' + digit;
       n -= (digit * weight);
       max_digit--;
       if (m-- == 0) {
         *(c++) = '.';
       }
-      else if (m < -1 && n < FLT_EPSILON) {
+      else if (m < -1 && n < (mrb_float)FLT_EPSILON) {
         break;
       }
     }
@@ -324,7 +324,7 @@
   mrb_float div;
   mrb_float mod;

-  if (y == 0.0) {
+  if (y == (mrb_float)0.0) {
     div = str_to_mrb_float("inf");
     mod = str_to_mrb_float("nan");
   }
@@ -336,7 +336,7 @@
       div = (x - mod) / y;
     if (y*mod < 0) {
       mod += y;
-      div -= 1.0;
+      div -= (mrb_float)1.0;
     }
   }

@@ -457,7 +457,7 @@

   d = (mrb_float)mrb_fixnum(num);
   /* normalize -0.0 to 0.0 */
-  if (d == 0) d = 0.0;
+  if (d == 0) d = (mrb_float)0.0;
   c = (char*)&d;
   for (hash=0, i=0; i<sizeof(mrb_float);i++) {
     hash = (hash * 971) ^ (unsigned char)c[i];
@@ -615,10 +615,10 @@

   mrb_get_args(mrb, "|i", &ndigits);
   number = mrb_float(num);
-  f = 1.0;
+  f = (mrb_float)1.0;
   i = abs(ndigits);
   while  (--i >= 0)
-    f = f*10.0;
+    f = f*(mrb_float)10.0;

   if (isinf(f)) {
     if (ndigits < 0) number = 0;
@@ -630,13 +630,13 @@
     else number *= f;

     /* home-made inline implementation of round(3) */
-    if (number > 0.0) {
+    if (number > (mrb_float)0.0) {
         d = floor(number);
-        number = d + (number - d >= 0.5);
+        number = d + (number - d >= (mrb_float)0.5);
     }
-    else if (number < 0.0) {
+    else if (number < (mrb_float)0.0) {
         d = ceil(number);
-        number = d - (d - number >= 0.5);
+        number = d - (d - number >= (mrb_float)0.5);
     }

     if (ndigits < 0) number *= f;
@@ -662,8 +662,8 @@
 {
   mrb_float f = mrb_float(num);

-  if (f > 0.0) f = floor(f);
-  if (f < 0.0) f = ceil(f);
+  if (f > (mrb_float)0.0) f = floor(f);
+  if (f < (mrb_float)0.0) f = ceil(f);

   if (!FIXABLE(f)) {
     return mrb_float_value(mrb, f);
(ctrl-d)
$ patch -p0 < numeric.c.patch

make して build/kernel/lib/libmruby.aがビルドできればOKです。その他のコンパイルエラーは放置します。

$ make
...
AR    build/kernel/lib/libmruby.a
ar: /home/shina/mruby-kernel/mruby/build/kernel/lib/libmruby.a を作成しています
...

ホスト環境での mruby での Hello World

まずはホスト環境(Linux)で mruby の動作を確認します。host というディレクトリを mruby の隣に作って試します。

$ cd ..
$ mkdir host
$ cd host

下記の main.c は mruby の実行環境を呼び出すプログラムです。今回は "Kernel" というモジュールと "printk" というクラスメソッドを用意します。実体は printf しているだけです。

$ cat > main.c
#include "mruby.h"
#include "mruby/proc.h"
#include "mruby/string.h"

extern uint8_t code[];

static mrb_value
kernel_printk(mrb_state *mrb, mrb_value self)
{
        mrb_value retval;
        mrb_value str;

        mrb_get_args(mrb, "S", &str);
        printf("%s", RSTRING_PTR(str));
        retval.value.i = 0;
        return retval;
}

int
main(int argc, char **argv)
{
        mrb_state *mrb;
        struct RClass *kernel;
        mrb_value ret;

        mrb = mrb_open();
        kernel = mrb_define_module(mrb, "Kernel");
        mrb_define_class_method(mrb, kernel, "printk",
                                kernel_printk, ARGS_REQ(1));

        ret = mrb_load_irep(mrb, code);
        return ret.value.i;
}
(ctrl-d)

次に実行する ruby のプログラム hello.rb を用意します。Kernel クラスの printk メソッドを呼び出すだけです。

$ cat > hello.rb
Kernel.printk "Hello World!\n"
(ctrl-d)

ビルドするための Makefile です。先ほどビルドした mruby のホスト環境を使います。mrbc は ruby のコードを mruby のバイトコード(のC言語の配列表現)に変換するプログラムです。

$ cat > Makefile
CFLAGS = -I../mruby/include -g
LDFLAGS = -lm
OBJS = main.o hello.o
LIBS = ../mruby/build/kernel/lib/libmruby.a

main: $(OBJS) $(LIBS)
	$(CC) $(OBJS) $(LIBS) $(LDFLAGS) -o $@

hello.c: hello.rb
	../mruby/bin/mrbc -Bcode $<
(ctrl-d)

make して実行して動作を確認します。

$ make
cc -I../mruby/include -g   -c -o main.o main.c
../mruby/bin/mrbc -Bcode hello.rb
cc -I../mruby/include -g   -c -o hello.o hello.c
cc main.o hello.o ../mruby/build/kernel/lib/libmruby.a -lm -o main
$ ./main
Hello World!

Linux カーネル内での mruby での Hello World

次に Linux で動作するカーネルモジュールを作成します。kernel というディレクトリを mruby の隣に作って試します。

$ cd ..
$ mkdir kernel
$ cd kernel

まずはカーネルモジュールの初期化・終了をおこなうコードです。

$ cat > lkm.c
#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/ctype.h>

extern int mruby_main(void);

static int lkm_init(void)
{
        printk(KERN_INFO "LKM: init\n");
        return mruby_main();
}

static void lkm_exit(void) {
        printk(KERN_INFO "LKM: exit\n");
}

module_init(lkm_init);
module_exit(lkm_exit);

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("mruby");
MODULE_AUTHOR("Takahiro Shinagawa");
(ctrl-d)

次に mruby を呼び出すコードです。先ほどのホストで動作するものとほとんど同じです。

$ cat > main.c
#include <linux/kernel.h>
#include "mruby.h"
#include "mruby/irep.h"
#include "mruby/string.h"

extern uint8_t code[];

static mrb_value
kernel_printk(mrb_state *mrb, mrb_value self)
{
        mrb_value retval;
        mrb_value str;

        mrb_get_args(mrb, "S", &str);
        printk(KERN_INFO "mruby: %s\n", RSTRING_PTR(str));
        retval.value.i = 0;
        return retval;
}

int
mruby_main(void)
{
        mrb_state *mrb;
        struct RClass *kernel;
        mrb_value ret;

        mrb = mrb_open();
        kernel = mrb_define_module(mrb, "Kernel");
        mrb_define_class_method(mrb, kernel, "printk",
                                kernel_printk, ARGS_REQ(1));

        ret = mrb_load_irep(mrb, code);
        printk("mruby: ret = %d\n", ret.value.i);
        return 0;
}
(ctrl-d)

次に libc をエミュレーションするライブラリです。必要最低限しかエミュレーションしていないので、ちゃんと定義されていない関数が呼び出されたら正常に動作しないでしょう。

$ cat > libc.c
#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>

typedef unsigned long size_t;
void *realloc(void *ptr, size_t size);
void free(void *ptr);

typedef int jmp_buf[6];
int setjmp(jmp_buf env);
void longjmp(jmp_buf env, int val);

int * __errno_location(void);
const unsigned short * * __ctype_b_loc (void);

long int strtol(const char *nptr, char **endptr, int base);
unsigned long int strtoul(const char *nptr, char **endptr, int base);

void abort(void);
void exit(int status);


void *realloc(void *ptr, size_t size)
{
	return krealloc(ptr, size, GFP_KERNEL);
}

void free(void *ptr)
{
	kfree(ptr);
}

int _setjmp(jmp_buf env)
{
	return __builtin_setjmp(env);
}

void longjmp(jmp_buf env, int val)
{
	__builtin_longjmp(env, 1);
}

int * __errno_location(void)
{
	static int errno;
	return &errno;
}

const unsigned short * * __ctype_b_loc (void)
{
	printk("%s\n", __FUNCTION__);
	return NULL;
}

const unsigned short * * __ctype_tolower_loc (void)
{
	printk("%s\n", __FUNCTION__);
	return NULL;
}

const unsigned short * * __ctype_toupper_loc (void)
{
	printk("%s\n", __FUNCTION__);
	return NULL;
}

int isspace(int c)
{
	return (c == 0x20) | (0x09 <= c && c <= 0x0d);
}

int isdigit(int c) 
{
	return ('0' <= c && c <= '9');
}

int isupper(int c)
{
	return ('A' <= c && c <= 'Z');
}

int islower(int c)
{
	return ('a' <= c && c <= 'z');
}

int isalpha(int c)
{
	return isupper(c) || islower(c);
}

long int strtol(const char *nptr, char **endptr, int base)
{
	printk("%s: %s\n", __FUNCTION__, nptr);
	return 0;
}

unsigned long int strtoul(const char *nptr, char **endptr, int base)
{
	printk("%s: %s\n", __FUNCTION__, nptr);
	return 0;
}

void abort()
{
	printk("%s\n", __FUNCTION__);
}

void exit(int status)
{
	printk("%s\n", __FUNCTION__);
}
(ctrl-d)

最小限のヘッダファイルを作成します。

$ cat > stdint.h
typedef unsigned char uint8_t;
(ctrl-d)
$ echo > inttypes.h

最後に Makefile です。上記のコードに加えて、先ほど hello.rb をバイトコードに変換したものと、mruby のライブラリをリンクします。

$ cat > Makefile
ccflags-y += -DDISABLE_STDIO -I$(PWD)/../mruby/include -I$(PWD)
obj-m := mruby.o
mruby-objs := lkm.o main.o libc.o ../host/hello.o ../mruby/build/kernel/lib/libmruby.a

all:
        make -C /lib/modules/$(shell uname -r)/build M=$(PWD) CFLAGS_MODULE=$(CFLAGS) modules

clean:
        make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean
(ctrl-d)

make すると少し警告が出ますが、mruby.ko が生成されるはずです。

$ make
...
$ ls mruby.ko
mruby.ko

出来たカーネルモジュールをロードすると、カーネルのログに Hello World! が出力されるはずです。

$ sudo insmod mruby.ko
$ dmesg | grep mruby
...
[   75.744877] mruby: Hello World!
[   75.744879] mruby: ret = 0

GitHub にコードを置きました.https://github.com/utshina/mruby-lkm

ツールキットを使わずに UEFI アプリケーションの Hello World! を作る

UEFI アプリケーションを作成するためのツールキットには、EDK IIgnu-efi などがあります。しかし、EDK II は複雑すぎて中身の構造が分かりにくく、とっつきにくい印象があります。また、gnu-efi は wrapper 経由で関数を呼び出さなければならないなど、標準的な UEFI アプリケーションのソースコードと若干異なるものになってしまうのが気になります。

そこで、UEFI の勉強も兼ねて、これらのツールキットを使わずに、本当に最小限の Hello World を表示するだけのアプリケーションを作ってみました。

開発環境は Linux です。必要な物は PE32+ executable を作るためのクロスコンパイラです。私は Fedora を使っているので、下記のコマンドでインストールできました。他のディストリビューションを使っている場合は、適宜探してインストールしてみてください。

yum install mingw64-gcc

実際に作成してみたソースコード(main.c)は以下のとおりです。定義はコンソール出力に必要な物だけに絞っており、かなり端折ってあります。その代わり、見える部分の定義はなるべく UEFI の仕様書のとおりになるようにしてみました。

#define IN
#define EFIAPI
#define EFI_SUCCESS 0

typedef unsigned short CHAR16;
typedef unsigned long long EFI_STATUS;
typedef void *EFI_HANDLE;

struct _EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL;
typedef
EFI_STATUS
(EFIAPI *EFI_TEXT_STRING) (
    IN struct _EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL  *This,
    IN CHAR16                                   *String
    );

typedef struct _EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL {
    void             *a;
    EFI_TEXT_STRING  OutputString;
} EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL;

typedef struct {
    char                             a[52];
    EFI_HANDLE                       ConsoleOutHandle;
    EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL  *ConOut;
} EFI_SYSTEM_TABLE;

EFI_STATUS
EFIAPI
EfiMain (
    IN EFI_HANDLE ImageHandle,
    IN EFI_SYSTEM_TABLE *SystemTable
    )
{
    SystemTable->ConOut->OutputString(SystemTable->ConOut, L"Hello World!\n");
    while(1);
    return EFI_SUCCESS;
}

EfiMain がエントリーポイントです。この関数に渡される EFI_SYSTEM_TABLE 型の SystemTable が各種システム・サービスへのポインタとなっています。その中に EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL 型の ConOut というデータがあり、オブジェクト指向のような関数テーブルとなっています。この中の OutputString という関数を呼び出すと、コンソールに文字列を出力することが出来ます。出力する文字列は Unicode なので、文字列の定義に L を付けます。

上記の main.c をコンパイルするための Makefile は以下のとおりです。

CC = x86_64-w64-mingw32-gcc
CFLAGS = -shared -nostdlib -mno-red-zone -fno-stack-protector -Wall \
         -e EfiMain

all: main.efi

%.efi: %.dll
	objcopy --target=efi-app-x86_64 $< $@

%.dll: %.c
	$(CC) $(CFLAGS) $< -o $@

qemu: main.efi OVMF.fd image/EFI/BOOT/BOOTX64.EFI
	qemu-system-x86_64 -nographic -bios OVMF.fd -hda fat:image

image/EFI/BOOT/BOOTX64.EFI:
	mkdir -p image/EFI/BOOT
	ln -sf ../../../main.efi image/EFI/BOOT/BOOTX64.EFI

OVMF.fd:
	wget http://downloads.sourceforge.net/project/edk2/OVMF/OVMF-X64-r15214.zip
	unzip OVMF-X64-r15214.zip OVMF.fd

clean:
	rm -f main.efi

ロスコンパイラとして x86_64-w64-mingw32-gcc を指定しています。他のディストリビューションでは名称が異なるようですので、適宜修正してください。

このクロスコンパイラを使って、まず普通の PE 形式のファイル main.dll を作ります。余計なものをリンクしないように、-nostdlib を付けています。また、エントリポイントとして EfiMain を指定しています。

生成された main.dll は Windows 等で使われる DLL などと同じ形式になっているので、objcopy を使って subsystem が 10 になるように変換して、UEFI アプリケーションとして認識されるようにします。


生成された main.efiqemu を使って実行してみます。

まず、qemu 用の UEFIファームウェアである OVMF.fd を入手します。http://tianocore.sourceforge.net/wiki/OVMF から最新のファームウェアをダウンロードできます。執筆時点では、r15214 でした。先ほどの Makefile を使うと自動的に入手できます。

make OVMF.fd

次に先ほどの Makefile を使って qemu を起動します。

make qemu

-nographic を指定することで、グラフィックスモードは使わずに、コンソールから起動するようにしています。-biosUEFIファームウェアのファイルを指定しています。-hda fat:image とすることで、image ディレクトリ以下を FAT フォーマットの仮想ディスクとして見えるようにしています。image 以下には EFI/BOOT/BOOTX64.EFI というファイル名で生成された EFI ファイルを置いておくことで、仮想マシンの起動時に自動的に EFI アプリケーションが実行されるようにしています。

うまくいけば、Hello World! と表示されて停止するはずです。Ctrl-a x で qemu を抜けましょう。

Boot Failed. EFI Floppy
Boot Failed. EFI Floppy 1
Boot Failed. EFI DVD/CDROM
Hello World!
QEMU: Terminated

GitHub にコードを置きました.https://github.com/utshina/uefi-simple

OS &amp; システムソフトウェアの一流国際会議

OSやシステムソフトウェアをメイントピックとする著名な国際会議を4つ紹介します。

SOSP (ACM Symposium on Operating Systems Principles)

概要

OSやシステムソフトウェアの分野における世界最高峰の国際会議。名称は "Operating Systems" だが、分散システム、ネットワーク、ストレージ、セキュリティ、組み込み等に関するシステムソフトウェア全般を幅広く扱う。

  • 2年に1回しか開催されない(下記のOSDIと交互に開催)
    • 第1回は1967年、2011年に第23回
  • 最近7回(1999年~2011年)の平均採択率は 17% (154本/885本)
1999 2001 2003 2005 2007 2009 2011
投稿 90 85 128 155 131 139 157 885
採択 19 17 22 20 25 23 28 154
採択率21.1%20.0%17.2%12.9%19.1%16.5%17.8%17.4%
  • 2011年の査読は3ステージ制
    • double blind、論文1本につき3~8名の査読者、査読総数719、最終的にはコアPCメンバー13名で採択を決定
  • 内容の濃い論文
    • レターサイズ14ページ程度
  • 高い被引用数
論文数被引用数平均被引用数H-index
ACM Digital Library (2013年1月現在)609 (-82※) 22,31536.64-
Microsoft Academic Search のデータ (2013年1月現在)41321,28751.573

ACMのデータは関連ワークショップ論文を含む。

論文

※「会議ページ」からは論文やスライド、ビデオ等が無料でダウンロード可能

OSDI (USENIX Symposium on Operating Systems Design and Implementation)

概要

SOSP と並ぶOSやシステムソフトウェアの分野における超一流国際会議。SOSP が徹底した "evaluation" により完全に完成した(≒終了した)仕事が多いのに対し、OSDI は(比較的)設計・実装の面白さを重視した論文が多い。

  • 2年に1回しか開催されない(上記の SOSP と交互に開催)
    • 第1回は1994年、2012年に第10回
    • 歴史は比較的浅いものの、ACM SIGOPSと連携しており、当初よりレベルの高い論文が多い。
  • 最近7回(2000年~2012年)の平均採択率は 15.5% (188本/1,211本)
2000 2002 2004 2006 2008 2010 2012
投稿 111 150 193 150 193 199 2151,211
採択 24 27 27 27 26 32 25 188
採択率21.6%18.0%14.0%18.0%13.5%16.0%11.6%15.5%
  • 2010年の査読は3ラウンド制
      • 第1ラウンドは査読者2名(約35本がreject)、第2ラウンドは査読者3名(約80本がreject)、第3ラウンドは査読者2~3名(ボーダーラインの論文が協議の末reject)、残った論文をPC会議の前半で全て一通り議論してaccept・acceptable・questionableに分類、accept・acceptableグループを採択にしたのち、PC会議の後半で残りの"questionable"論文の採択を議論、PC会議後さらに"heavier"なPCメンバーによるメール投票で数本を追加採択。
  • 内容の濃い論文
    • レターサイズ14~16ページ程度
  • 高い被引用数
論文数被引用数平均被引用数H-index
ACM Digital Library (2013年1月現在)2217,81735.37-
Microsoft Academic Search のデータ (2013年1月現在)23615,63166.2370
論文

EuroSys (The European Conference on Computer Systems)

概要

2006年に誕生したばかりで歴史は浅いが、当初より高いレベルを保っている一流国際会議。異常にレベルの高い SOSP や OSDI を補完する受け皿として、普通のトップカンファレンスとしての地位を確立しつつある。

  • 毎年開催される
    • 第1回は2006年、2012年に第7回
  • 最近7回(2006年~2012年)の平均採択率は 17.9% (185本/1,036本)
2006 2007 2008 2009 2010 2011 2012
投稿 144 131 131 149 141 161 1791,036
採択 29 29 24 25 27 24 27 185
採択率20.1%22.1%18.3%16.8%19.1%14.9%15.1%17.9%
  • 2012年の査読は3ラウンド制
    • 第1ラウンドは査読者3名以上(96本が次のラウンドへ)、第2ラウンドは査読者2名以上、評価の分かれた論文は第3ラウンドで更なる査読、査読総数750
    • 査読コメントに対する著者の反論機会あり
    • 全ての採択論文にはPCメンバーによるシェパードが付く
  • 内容の濃い論文
    • レターサイズ14ページ程度
  • 高い被引用数
論文数被引用数平均被引用数H-index
ACM Digital Libraryのデータ(2013年1月現在)382(-197※)3,1848.34-
Microsoft Academic Search のデータ(2013年1月現在)1783,35618.8530

ACMのデータは関連ワークショップ論文を含む。

論文

USENIX ATC (Annual Technical Conference)

概要

近年アカデミックな論文発表の場として定着してきた一流国際会議。EuroSys と並んで SOSP や OSDI に通らなかった論文の受け皿として成長してきた。EuroSys に落ちた論文を投稿できるように日程調整等がされるときもある。

  • 団体としての USENIX は "The Advanced Computing Systems Association" とも称される
    • "Unix User Group" が起源とされるが、近年は「UNIXユーザ会」的な印象は薄れている
    • 特に Technical Conference は、2000年以降くらいから急速にアカデミックな論文発表の場としての格が上昇し、EuroSys に次ぐ1流(1.5流?)国際会議としての地位を確立している
  • 近年は年に1回開催される
    • Winter と Summer の年2回開催されていた時期もある
    • "Annual" と付くようになったのは 1996 年頃から
    • Technical Conference 自体は1980年代始めから開催されていたようである
    • 開催回数が不明確なため、正式名称は "2012 USENIX Annual Technical Conference" のように年を記載する
  • 最近7回(2006年~2012年)の平均採択率は 15.1% (182本/1,202本)
2006 2007 2008 2009 2010 2011 2012
投稿 153 170 176 191 147 180 1851,202
採択 21 24 28 28 22 27 32 182
採択率13.7%14.1%15.9%14.7%15.0%15.0%17.3%15.1%
  • 2012年の査読は3ラウンド制
    • 第1ラウンドは査読者2人、第2ラウンドでは3人目の査読者が付く場合があり、第3ラウンドでは4,5人目の査読者が付く場合がある
    • 全ての採択論文にはPCメンバーによるシェパードが付く
  • 内容の濃い論文
    • レターサイズ12~14ページ程度
  • 高い被引用数
論文数被引用数平均被引用数H-index
Microsoft Academic Search のデータ(2013年1月現在)1,47141,03527.9093
論文