実践的低レイヤプログラミング

はじめに

学校で習わないが(習う学校もある)、現実に必要になるプログラミング技術に、低レイヤプログラミングなどと呼ばれるものがある

厳密な定義は聞いたことがないし、おそらく存在しないとは思うが、大体のみんなの共通認識として、 「高級プログラミング言語を使わないプログラムを書き、OSで抽象化されないデバイスの機能を使う」といったような認識があると思う。

筆者の経験から言わせてもらうならば、低レイヤプログラミングに関する知識は、プログラミングにおいてあらゆる場面で、常に、少しずつ役立てられる知識だと言えると思う。

普段はRubyやPHPなどを書いてる人であったとしても、メモリが足りなくなった場合や、デバッガを使っている場合、性能が足りなくなった場合など、 厳しい環境におかれた時に低レイヤプログラミングに関する知識が必ず役に立つ場面が来ると信じている。

また、役に立つかどうかは置いておいても、「プログラムはどのように動いているのか」を知ることは、知的好奇心を満たし、 その知識を駆使すれば、コンピュータの挙動を手中に収めた全能感を楽しむことができることだろう。

多くのプログラム初心者が、 「#include <stdio.h> ってなになのか?」「何故 print "Hello World" というプログラムを実行すると、画面に"Hello World"と出るのか?」 と、いった点について、多かれ少なかれ疑問を持ちながら、モヤモヤとした気持ちでプログラムを書いたことがあるはずだ。

しかし、残念ながら、これらに関する知識は体系立てられているとは言えず、 また、低レイヤプログラミングがターゲットとする領域では、 アドホックな方法で、場当たり的に実装されたものがそのままデファクトスタンダードになってしまう例が数多くあり、 なんらかの一般的な理論を勉強するよりは、実装ごとの事情を勉強する必要があるのが現実である。

それでも、現実にある多くの事情、デバイス、実装などを眺めていれば、そこはかとなく存在する一般的な概念を読みとることができるはずで、 それらの多くを実際に経験した筆者は、おそらく多くの人より、なんらかの普遍的な知識を獲得しているだろうという自信はある。

この文章は、筆者が書ける限りの、色々なデバイスの色々な事情について、書けるかぎり書いていこうというものである。 普遍的な知識を表現することは難しいが、色々なレイヤの事情を通して、なんらかの共通する概念を習得する人がひとりでも増えれば幸いである。

この文章の状態について

2018/10 現在、書きかけの状態です。とりあえず今は読みやすさよりも情報量増やすほうに注力しているので、読みやすさはあとまわしになっています。 ひとくぎり付いたら、推敲したり、体裁整えたり、図を入れたりしようと思います。

更新状況は https://github.com/tanakamura/pllp/tree/gh-pages から確認ください。 また @tanakmura で何か追加で言い訳などを書いている場合もあります。

気が向いたらリアルタイム更新を 配信 しています。

環境

なんらかの方法で Linux、GCC、binutils の環境を用意することを強くお勧めする。実機でもVMでもWSLでも構わない。(もしかすると実機でしかできないこともやるかもしれないが)

Windowsにも、優れた開発環境はあるが、少し道を踏みはずした低レイヤプログラミングをする場合、ぱぱっと色々なコマンドを組みあわせて変なことができる Linux環境のほうがかなり使いやすい。道をはずしたプログラミングをするなら、Linux環境に慣れておくにこしたことはないと思う。

また、場合によってはARMなどの、PC以外の環境にも触れたいと思っているが、Linuxならば、その場合にもインターフェースが共通して使えるので、心強い。

巨大なライブラリなどは必要ない。C言語で書いた Hello World がコンパイルできる程度の環境があれば十分である。ついでにgdbも使えるようになっているとよい。

PC以外に、Raspberry Pi、Zybo などを使っていくかもしれない。手元にある人は使ってみてほしい。

アセンブリ、C言語、リンカ、ローダ、機械語、ABI

アセンブリ言語はご存知だろうか?ご存知のかたは、どの程度ご存知であろうか。 もし、あなたが、共有ライブラリロード時のリロケーションの処理が何なのか説明できる程度に、色々なことを知っているならば、もう、この章は飛ばしてもらってかまわない。(というかそもそもこの文章読む意味あるか?)

低レイヤプログラミングにおいて、機械語は第一級言語だと言っていい。機械語に関する理解なく、低レイヤプログラミングにチャレンジするのは、筆や鉛筆等を持たないで絵を描くのと似たようなものだ。

この章の目的は

の二点だ。

できる限り、わかりやすい説明を試みるが、かなり重いテーマなので、筆者の説明不足などにより、全てを正しく理解するのは難しいかもしれない。 その場合でも、次からの章を断片的に理解することはできるので、よくわからなければ、次の章へ進んでもらってもかまわない。 この文章全体を読み終えるくらいに、第一章が理解できるぐらいのペースでもよいと思う。

また、C言語への理解がまだ浅い人は、別のC言語の書籍、解説ページを用意して、そちらと交互に読んでいくものよいかもしれない。 ポインタなどがわからないという人も、その背後にある機械語を理解すれば、いくらか理解しやすくなることもある。C言語の文法などは基本的に説明しないので、 よくわからなければ、C言語の本に戻っていただいてもかまわない。多分、両方をちょっとずつ理解していくのがいいと思う。

x86_64 プログラミング入門 (一旦終了)

x86_64 機械語入門 (書きかけ)

Intel マニュアルの読みかた

ARMv7 プログラミング入門

リンカ (書きかけ)

C言語とアセンブリ

ABI, Calling Convention (呼び出し規約)

システムコール(OS呼び出し)

libc 自作

インタプリタ/コンパイラ

binutils

ここまで as,readelf,objdump などのツールを使ってきたが、これらのツールは、Linux では、 binutils と呼ばれるパッケージに含まれている。

binutils には、有用なツールが含まれているので、そのうちいくつかを簡単に紹介しておこう。

objdump

readelf

c++filt

addr2line

objcopy

おまけ : shellcode,PIC,PIE,ASLR

バス、メモリ、周辺IO、MMIO

Linux デバイスドライバ

低レイヤプログラミングを習得するためにLinux デバイスドライバについて学習するのは良い方法かもしれない。

普段は、様々な問題からプログラマを守ってくれるOSではあるが、 道を外したプログラミングをする場合、このOSの保護が邪魔になる場合がある。

OSの保護を回避する手段として、「OSなし(ベアメタル)プログラミング」という世界がある。 これは、非常に楽しいプログラミングではあるが、場合によってはprintfで数値を画面に出力したり、mallocでメモリを確保するだけでも かなりの苦労を伴う手法である。

そこで、別の方法として、Linuxデバイスドライバを書くという方法もある。

Linuxデバイスドライバまわりの開発環境は、非常によく整備されていて、 printf ぐらい気軽に文字列を出力できるし、mallocぐらい気軽にメモリを割り当てられるし、 プログラムにミスがあってエラーが出れば、エラーが発生した箇所を教えてくれる機能が付いている。 「Linuxデバイスドライバ」という、優れた書籍があるのも嬉しい点だ。

また、Linuxデバイスドライバについて深く学ぶと、演習で使うようなtoy OSにはない、 現実世界で広く使われるOSに必要なものを肌で感じられるようになるというメリットもある (例えば、toyOSではCPUの速度に迫るような高速な周辺デバイスのことは考えられていないなど)。 あと現実的な話をしてしまうと、Linuxドライバを書いてほしい/修正してほしいという仕事は世の中にたくさんあり、 Linuxドライバが書けるようになっていると、職にあぶれないという点も見逃せない。

この章では、本文書の説明で使える程度の範囲内で、Linuxデバイスドライバの書きかたについて説明していく。 より詳しい使いかたに興味がある人は、書籍や、Linuxのソースコードを参照してほしい。

GPIOデバイスドライバ (みんな大好きLチカプログラミング)

UART による通信

ベアメタルプログラミング

低レイヤプログラミングに興味がある人なら、OS自作や、ベアメタルプログラミングに手を出したことがある人も多いのではないだろうか。

しかし、現在のPCのマザーボードには、昔のOSに匹敵するような巨大なソフトウェアが搭載されているのが普通で、 もっと小さなハードウェアで実行されるベアメタルプログラムと比較すると、まだ厚いレイヤーの上で動くソフトウェアしか作れないという問題がある。 PCベアメタルプログラミングに手を出したことがある人も、BIOSコールを使って、HDDにアクセスしたり、 UEFIサービスを使って、ファイルシステムにアクセスするとき、「これは何か求めていたものとは違うのではないか?」と思いながらプログラムを書いていたはずだ。

ここでは、PCよりもレイヤーの薄いZyboを使って、ベアメタルプログラミングにチャレンジしていこうと思う。 (ちなみにRaspberry Piも、大きめのファームウェアを持っていて、ARMがブートするのは、色々な初期化が終わったあとだ)

ブートとは

SPI flash

クロック

DRAMコントローラ

ファームウェア、BIOS、UEFI

おまけ : デバイスツリー

OSを支える技術

現代の低レイヤプログラミングを把握するためには、OSの動作の理解が必要不可欠だ。

OSといえば、Windows,Linux,OSXなどが有名で、とても巨大なものというイメージを持っている人もいるかもしれない。

しかし、OSのコア技術は大昔のコンピュータからそれほど変わっておらず、Linuxの最初のバージョン(0.01 : メモリ保護、プロセススケジュール、ファイルシステム等を含む) の C ソースの行数は約6000行と考えれば、個人の余暇で十分把握できる程度の規模しかないというのがわかるだろう。

OS 自体のつくりかたや、Linuxの読解の解説は、優れた書籍がたくさんあるので、ここではあまり触れないようにして、 この章では、OS自作初心者向けの本には書かれていない、SMPやメモリ属性の話と、それに必要な基礎的な知識について書いていく。

割り込み

CPUの外側に装着されたデバイスは、CPUとは非同期に(CPUの動作とは独立して別に)動作しているものが大半である。

CPU上で動くプログラムは、このCPUとは独立して動く外部デバイスの動作の完了をなんらかの方法で知る必要がある。

この外部デバイスの完了を知る方法には、大きく分けて、ポーリング(polling)割り込み (interrupt) のふたつの方法がある。

ポーリングは、CPU上で動作するソフトウェアから、外部デバイスのレジスタやメモリの状況を確認する方法だ。前に書いた(TODO:まだ書いてない) UARTの 処理では、プログラムのループ中で、UARTデバイスのレジスタを読んで、そのビットを確認して終了を判定していた。

このポーリングは、プログラムはわかりやすくなるが、外部デバイスの動作が完了するまで、CPUは他のことができず、CPU時間を無駄にしてしまう。 (ただし、デバイス完了を受け取るまでの時間は短くすることができるので時間を短くするためにポーリングを使うことはたまにある。例えば後で述べるInfinibandでは、ポーリングを使うほうが一般的だ)

この外部デバイスの動作を待っているあいだに、CPUに別のことをさせたい場合、CPUの消費電力を減らすためにCPUの動作を停止させたい場合、外部デバイスから、動作の完了を通知をする仕組みがあると嬉しい。

割り込みは、外部デバイスから強制的にCPU上に分岐を発生させて、CPUの処理を変えさせる仕組みだ。 この割り込みを使うことで、CPUは外部デバイスの動作の完了を待つ間、別の処理をしたり、CPUを低消費電力状態に遷移させたりすることができる。

この章では、この割り込みについて説明していく。

割り込みの使いかた

割り込み自体は、極端に言えば外部からプログラムカウンタをずらすだけの単純な仕組みなので、色々な使いかたができるのだが、 ここでは通常のOSで使われる一般的な使いかたを時計アプリを例に説明しておく。

タイマーデバイスが付いたCPUを使って時計アプリを作るとしよう。(実際のアプリでは表示処理も割り込みを使うので、あまり正しくないが、それは忘れておく)

このCPUに付いているタイマーデバイスのレジスタを読めば現在時刻が取得できるとする。

このタイマーデバイスを使って、ポーリングを使って時計アプリを作ると、大体以下の疑似コードで示すような感じになる。

  void get_current_time(time_t *cur) {
      *cur = *(time_t*)(TIMER_REG_ADDR);  // タイマーのレジスタから値を読んでくる
  }

  void timer_app() {
    while (1) {
      time_t cur;
      get_current_time(&cur);  // 時刻を取得
      display_time(&cur);      // 表示を更新
    }
  }

ここで、display_time の表示更新処理は消費電力が多いので、あまり使いたくないとしよう。そうすると、プログラムは以下のようになる。

  void get_current_time(time_t *cur) {
      *cur = *(time_t*)(TIMER_REG_ADDR);  // タイマーのレジスタから値を読んでくる
  }

  void timer_app() {
    timer_t prev;
    get_current_time(&prev);
    while (1) {
      time_t cur;
      get_current_time(&cur);  // 時刻を取得
      if (cur != prev) {       // 前回と時刻が変化したときだけ処理
        display_time(&cur);    // 表示を更新
        prev = cur;
      }
    }
  }

このとき、時計が秒単位で表示されるアプリケーションだった場合、表示が更新されるのは1秒間に一回だけだ。 現代のCPUは、命令単位の処理時間は1nsecとかそれ以下、小さくて比較的遅いコンピュータでもusec単位以下になっており、 このアプリケーションのCPU時間の大半は、タイマーレジスタの値を読んで、その値を比較するだけに消費されてしまう。 これは、CPUの電力の無駄遣いだ。

ここで、割り込みを使えば、CPU処理の消費電力も下げることができる。

多くのタイマーデバイスは、一定時間ごとにCPUに割り込みを入れる機能を持っている。 また、多くのCPUは、割り込みが来るまでCPUを停止させて消費電力を減らす機能を持っている。

これを組み合わせて、「タイマーから割り込みが来るまで、CPUを低消費電力状態に移す」というようにプログラムを書きかえる。

  void get_current_time(time_t *cur) {
      *cur = *(time_t*)(TIMER_REG_ADDR);  // タイマーのレジスタから値を読んでくる
  }

  void timer_interrupt_handler() { // 割り込みハンドラ (CPUに割り込みが入ったら、プログラムカウンタをここへ設定する)
      time_t cur;
      get_current_time(&cur);  // 時刻を取得
      display_time(&cur);    // 表示を更新
  }

  void timer_app() {
    init_timer_interrupt();    // タイマデバイスの割り込み設定
    init_interrupt();          // CPU側の割り込み設定

    timer_t prev;
    get_current_time(&prev);
    while (1) {
      wait_for_interrupt();    // 割り込みが来るまでCPUを低消費電力状態に入れる
    }
  }

大体このようになる。

定義なしで使っている処理について、もう少し説明しよう。

wait_for_interrupt() は、OS無し環境ではCPU毎に専用の命令になると考えてもらってよい。 x86 では mwait、ARMv7 では wfi という命令がそれに対応する。 mwait 命令は、実際に使うときはmonitor命令と組み合わせて使う。monitor,mwait 命令の詳細は、機会があれば書こう。

次に init_timer_interrupt() だ。 現実のタイマデバイスには、割り込みの方法を指定できるものが多い。特に設定したいものは、割り込みの間隔だ。

上のアプリケーションでは、表示を一秒ごとに更新したいので、タイマデバイスには、一秒ごとに割り込みを入れてもらうと都合が良いだろう。 init_timer_interrupt は、「一秒ごとに割り込みを入れるように設定する」処理だと思ってもらってよい。 (ただし、現実世界のコンピュータでは、"一秒とは何か"、というのはそんなに単純な問題ではないので、 "一秒"という指定はちょっと考えないといけない。これについてはRTCのところで説明しよう)

続いて、init_interrupt()。 上のプログラムは、タイマから割り込み要求がきたら、時刻を取得して、それを表示に反映するプログラムだ。 そのプログラムを実現するには、割り込みとその処理(上のプログラムではtimer_interrupt_handler関数)を関連付ける設定が必要になる。 init_interrupt はその「割り込みがきたらどうするかを設定する」処理だ。

一般的なCPUでは、DRAM上に置かれた割り込みベクタ (interrupt vector)と呼ばれる割り込みと対応したテーブルを設定して、 そこに入れてある値を割り込み発生時のプログラムカウンタの位置に設定するものが多い。

init_interrupt() を簡単に書くと

  void timer_interrupt_handler();

  // タイマから来る割り込みを識別する番号
  // タイマの実装の方法によって変わる
  // CPUが同じであっても、基盤の実装方法によって変わることがある
  #define TIMER_INTERRUPT (9) 

  void init_interrupt() {
      // 割り込み時に処理をする命令が置かれたアドレス
     uintptr_t handler_addr = (uintptr_t)timer_interrupt_handler;

     // 割り込みベクタが置かれたアドレス。
     // フォーマットやベクタのアドレスは、CPUによって大きく変わる
     // このCPUではテーブルがメモリアドレス0番地に置かれているとする
     uintptr_t *int_vector = (uintptr_t*)0;

     // 割り込みベクタのタイマ割り込みに対応するエントリに
     // 割り込み時に使う命令が置かれたアドレスを設定する
     int_vector[TIMER_INTERRUT] = handler_addr;
  }

大体このようになる。

割り込み時に実行する処理や関数を、割り込みハンドラ(interrupt handler) と呼ぶ。 ここでは、timer_interrupt_handler がタイマ割り込みの割り込みハンドラになる。 init_interrupt() の処理は、「タイマ割り込みのハンドラのアドレスを割り込みベクタに設定する」 とかスラスラ言えるようになれば、君も立派な組み込みプログラマだ。

ARMv7 の割り込み

さて、上の例ではいくらか詳細を省いていたが、実際のCPUではどうなっているか詳しく見ていこう。

できればx86の割り込みで説明したいのだが、x86 の割り込みは本質とは関係ない複雑さがあって初学者には向いていないので、 ここでは ARMv7 を使って解説していくことにしよう。

(書きかけ)

割り込みコントローラ

ARMv7 の例では、コア内から、ソフトウェア割り込みを発生させていた。今度はCPUコアの外から割り込みを発生させてみよう。

一般的なシステムでは、CPUコアの外から割り込みを発生させる場合、CPUコアとデバイスの間に、割り込みコントローラ(interrupt controller) という専用のデバイスを入れることが多い。

CPUコア内で発生する割り込みは、CPU設計時に確定するが、CPUコア外部の割り込み発生要因は、CPU設計時に確定しない。 さらに、割り込みの入れかたも、デバイスによってさまざまである。

割り込みコントローラは、これらの複数のデバイスから来る割り込みをCPUの割り込み信号に変換して、調停する役割を持つ。

この節では、この割り込みコントローラについて説明していこう。

(書きかけ)

シングルコア CPU での割り込み

マルチコア CPU での割り込み

Cortex-A53 の割り込み

現代のOSでの割り込み

メモリ保護

仮想化

デバッガ

DMA

キャッシュ

メモリ

高速デバイスの世界

かつて、コンピュータというのは、高速なCPUと、中速なメモリ、低速なI/O から構成されていた。

しかし、近年は、CPUの速度向上がかなり停滞してきているのに対し、 周辺I/Oデバイスの速度向上は止まるどころか、高速なデバイスが次々に投入され、 その性能は、CPUに迫るか、それを大きく上まわるものも登場してきた。

遅いと言われていたストレージは、家庭用の物でもusec単位で処理が実行されており、 100GbpsイーサやInfinibandの帯域はCPUのmemsetに迫るぐらいになり、 GPUの演算スループット性能およびメモリ帯域はCPUの何倍も大きくなってきている。

ここでは、現代の高速デバイスが、どのように接続され、ユーザからどのように使うのかといった点について解説していきたいと思う。

PCI Express

イーサネット

Infiniband

USB

GPU

ストレージ

SATA, AHCI

NVMe

ネットワーク

TCP/IP

ファイルシステム

i2c

FPGA

RTC

ヒープ、malloc、GC

チューニング

低レイヤプログラミングに関する書籍