国際会議 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)
複数コアの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)
制御された仮想環境ではなくデバイスドライバやカスタムハードウェアなどを含むような仮想環境ではない「野生(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)
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)
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 ざっと眺めただけですので、内容も間違っているかもしれません。
目次
- 概要
- Session 1: Machines, Learning
- Session 2: It Must Be Secure
- Session 3: Systems: Still Buggy
- CrashTuner: メタ情報解析によるクラウドシステムのクラッシュ回復バグの検出 (CrashTuner: Detecting Crash Recovery Bugs in Cloud Systems via Meta-info Analysis)
- 変曲点仮説:障害の根本原因を突き止めるための原理的デバッグ手法 (The Inflection Point Hypothesis: A Principled Debugging Approach for Locating the Root Cause of a Failure)
- 拡張可能ファジングフレームワークによるファイルシステムのセマンティックバグの発見 (Finding Semantic Bugs in File Systems with an Extensible Fuzzing Framework)
- 効率的でスケーラブルなスレッド安全性違反の検証 --- テスト中に数千個の並行バグを発見 (Efficient and Scalable Thread-Safety Violation Detection --- Finding thousands of concurrency bugs during testing)
- Session 4: Keeping Things Private
- Session 5: It Must Be Correct
- Serval によるシステムコードの自動検証のためのシンボリック評価の拡張 (Scaling Symbolic Evaluation for Automated Verification of Systems Code with Serval)
- Perennial による並行でクラッシュセーフなシステムの検証 (Verifying Concurrent, Crash-safe Systems with Perennial)
- AtomFS ファイルシステムを検証するためのヘルパを用いた並行関係論理の使用 (Using Concurrent Relational Logic with Helpers for Verifying the AtomFS File System)
- 検証の専門知識を使わないソフトウェアネットワーク機能の検証 (Verifying Software Network Functions with No Verification Expertise)
- Session 7: The Revolution Will Be Distributed
- Session 8: Net Work
- Session 9: The Persistence Of Memory
- KVell: 高速な永続キーバリューストアの設計と実装 (KVell: the Design and Implementation of a Fast Persistent Key-Value Store)
- RECIPE: 並行DRAMインデックスの永続メモリインデックスへの変換 (RECIPE: Converting Concurrent DRAM Indexes to Persistent-Memory Indexes)
- ユーザ空間NVMファイルシステム ZoFS における性能と保護 (Performance and Protection in the ZoFS User-space NVM File System)
- SplitFS: 永続メモリのためのファイルシステムにおけるソフトウェアオーバーヘッドの削減 (SplitFS: Reducing Software Overhead in File Systems for Persistent Memory)
- Session 11: The Final Session
概要
- 参加者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
変曲点仮説:障害の根本原因を突き止めるための原理的デバッグ手法
(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
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
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
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
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 II や gnu-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.efi を qemu を使って実行してみます。
まず、qemu 用の UEFI のファームウェアである OVMF.fd を入手します。http://tianocore.sourceforge.net/wiki/OVMF から最新のファームウェアをダウンロードできます。執筆時点では、r15214 でした。先ほどの Makefile を使うと自動的に入手できます。
make OVMF.fd
次に先ほどの Makefile を使って qemu を起動します。
make qemu
-nographic を指定することで、グラフィックスモードは使わずに、コンソールから起動するようにしています。-bios で UEFI のファームウェアのファイルを指定しています。-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 & システムソフトウェアの一流国際会議
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,315 | 36.64 | - |
Microsoft Academic Search のデータ (2013年1月現在) | 413 | 21,287 | 51.5 | 73 |
※ACMのデータは関連ワークショップ論文を含む。
- 著名システムの初期の論文もしばしば掲載される
- 日本人が第一著者の論文は3本?
論文
※「会議ページ」からは論文やスライド、ビデオ等が無料でダウンロード可能
- SOSP: ACM Digital Library
- SOSP 2011: ACM Digital Library, 会議ページ
- SOSP 2009: ACM Digital Library, 会議ページ
- SOSP 2007: ACM Digital Library, 会議ページ
- SOSP 2005: ACM Digital Library
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 | 215 | 1,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ラウンド制
- 内容の濃い論文
- レターサイズ14~16ページ程度
- 高い被引用数
論文数 | 被引用数 | 平均被引用数 | H-index | |
---|---|---|---|---|
ACM Digital Library (2013年1月現在) | 221 | 7,817 | 35.37 | - |
Microsoft Academic Search のデータ (2013年1月現在) | 236 | 15,631 | 66.23 | 70 |
- 著名システムに関する論文もしばしば掲載される
- 日本人が第一著者の論文は1本?
論文
- OSDI: USENIX OSDI Conferences
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 | 179 | 1,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,184 | 8.34 | - |
Microsoft Academic Search のデータ(2013年1月現在) | 178 | 3,356 | 18.85 | 30 |
※ACMのデータは関連ワークショップ論文を含む。
論文
- EuroSYS: ACM Digital Library
- EuroSys 2012: ACM Digital Library
- EuroSys 2011: ACM Digital Library
- EuroSys 2010: ACM Digital Library
- EuroSys 2009: ACM Digital Library
USENIX ATC (Annual Technical Conference)
概要
近年アカデミックな論文発表の場として定着してきた一流国際会議。EuroSys と並んで SOSP や OSDI に通らなかった論文の受け皿として成長してきた。EuroSys に落ちた論文を投稿できるように日程調整等がされるときもある。
- 団体としての USENIX は "The Advanced Computing Systems Association" とも称される
- 近年は年に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 | 185 | 1,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,471 | 41,035 | 27.90 | 93 |
- 日本人が第一著者の論文は2000年以降は2本?
論文
- USENIX: USENIX Proceedings
- USENIX ATC 2012: Technical Sessions
- USENIX ATC 2011: Technical Sessions
- USENIX ATC 2010: Technical Sessions
- USENIX ATC 2009: Technical Sessions