Rustのasync/awaitを使ったecho serverの実装
rust 1.39でasync/await構文が安定化されます． 巷で話題の機能ですが，asycn/await何も分からん...ということで話題に乗り遅れないためにasync/awaitを利用してecho serverを実装してみます．
echo server
async/awaitを使用する前に，まずは通常のecho serverを作成してみます（ソース）． あえてstd::netを使わないで実装しています．
主処理は以下のようになっています．
fn handle_client(stream: TcpStream) -> io::Result<()> { let mut buf = [0u8; 1024]; loop { let n = syscall!(read( stream.0, buf.as_mut_ptr() as *mut libc::c_void, buf.len() ))?; if n == 0 { break; } // NOTE: write() possibly writes less than n bytes. So we should check the return value to // check how many bytes written but omit it here for simplicity. syscall!(write( stream.0, buf.as_ptr() as *const libc::c_void, n as usize ))?; } Ok(()) } fn main() -> Result<(), Box<dyn std::error::Error>> { let addr = Ipv4Addr::new(127, 0, 0, 1); let port = 8080; let listner = TcpListener::bind(addr, port)?; for stream in listner.incoming() { let stream = stream?; handle_client(stream)?; } Ok(()) }
さて，一見良さそうなこのecho serverですが，致命的な問題があります．…そうです，一度に一コネクションしか対応できません．
問題の直接的な原因はクライアント処理をwhileループ内で実施していることですが，それとは別にI/O処理(listen()/accept()/read()/write())がブロックするというのもあります．
ブロックするというのは，処理が完了するまでシステムコールがリターンしない（結果としてスレッドが停止する）という意味です．
例えば，クライアントのパケットを読もうとしてread()をしても，その時点ではクライアントからのパケットが到着していないということは十分ありえます．ブロックする場合はパケット到着までそのスレッドはスリープすることになります．
この間もし別のクライアントからの接続要求が先に来たとしても，そのスレッドはそれを優先的に処理することはできません．
multi-thread版 echo server
上記問題を解決する方法はいくつかありますが，単純にはクライアントごとにスレッドを立ち上げれば良いです（ソース）．
for stream in listner.incoming() { let stream = stream?; std::thread::spawn(move || { handle_client(stream).unwrap(); }); }
多くの場合，これで上手くいくと思います． そして，これで問題が無いのであればあえて他の手法を利用する必要は特にないと思います． よくスレッドの生成コスト云々言われますが，本当にそこがボトルネックになっているでしょうか? 適当にスレッドプールを用意することもできます．
...が，そうするとここで話が終わってしまうので以下で別の方法を説明します．
ノンブロッキングI/O (O_NONBLOCK)
Linuxでは，ソケットのfile descriptorにO_NONBLOCK属性を付与すると，そのソケットに対するアクセスがnon-blockingになります．
具体的には，ソケットに対してread()やwrite()した際に，I/O処理がすぐに完了できない場合（クライアントからパケットが到着していない場合や，書き込みバッファが一杯の場合など）は，OSが処理可能になるまで待つ代わりに，errnoにEWOULDBLOCKやEAGAINが設定されすぐにリターンします．
そのためスレッドは別の処理を実行することができます．
echo serverの例で言うと，これを使って以下のように1スレッドで複数コネクションが扱えます．
(擬似コード)
loop { // handle client 1 match read(fd1, ...) { Ok(n) => {...} Err(WOULDBLOCK) => , ... } // handle client 2 match read(fd2, ...) { Ok(n) => {...} Err(WOULDBLOCK) => , ... } .... }
ただし，この方法はユーザ空間でポーリングしていることになり，CPU利用的には非効率です． そこで次で説明するepollを利用します．
(ちなみに，ここで説明した意味でのノンブロッキング版 echo serverは実装していないのでソースはないです．)
epoll版 echo server
epoll(7)を利用すると，複数のfile descriptorを監視し，いずれかのfile descriptorが準備完了になった時点で通知を受け取ることができます．
epollの使い方はざっと以下のようになります．
epoll_create()でepollを作成epoll_ctl(EPOLL_CTL_ADD)を使ってイベントを登録- このとき，
EPOLLINで入力待ち，EPOLLOUTが出力待ちの設定
- このとき，
epoll_wait()で登録したイベントのいずれかが準備完了になるまで待つ- epollから通知を受けたらそのfile descriptorに対して処理する
epoll版のメイン処理は以下のようになります（ソース）．
fn main() -> Result<(), Box<dyn std::error::Error>> { let addr = Ipv4Addr::new(127, 0, 0, 1); let port = 8080; let mut epoll = Epoll::new(32)?; let listner = TcpListener::bind(addr, port)?; let mut clients: HashMap<RawFd, ClientState> = HashMap::new(); epoll.add_event(listner.0, EpollEventType::In)?; loop { let nfd = epoll.wait()?; for i in 0..nfd { let fd = epoll.events[i].u64 as RawFd; if fd == listner.0 { /* Accept a new connection */ let client = listner.accept()?; client.setnonblocking()?; epoll.add_event(client.0, EpollEventType::In)?; clients.insert( client.0, ClientState { stream: client, buf: [0u8; 1024], buf_cursor: 0, }, ); } else if clients.contains_key(&fd) { /* Handle a client */ let events = epoll.events[i].events as i32; let client_state = clients.get_mut(&fd).unwrap(); if (events & libc::EPOLLIN) > 0 { /* read */ let n = syscall!(read( fd, client_state.buf.as_mut_ptr() as *mut libc::c_void, client_state.buf.len() ))?; client_state.buf_cursor = n as usize; if n == 0 { epoll.del_event(fd)?; clients.remove(&fd); break; } epoll.mod_event(fd, EpollEventType::Out)?; } else if (events & libc::EPOLLOUT) > 0 { /* write */ syscall!(write( fd, client_state.buf.as_ptr() as *const libc::c_void, client_state.buf_cursor ))?; epoll.mod_event(fd, EpollEventType::In)?; } else { unreachable!(); } } else { unreachable!(); } } } #[allow(unreachable_code)] Ok(()) }
epollを利用する場合はメインのイベントループ内で複数のコネクションを扱います．
ここではlisten()のソケットと，accept()したソケットの双方をepollで待っていて，どちらかが処理完了になったらそれを処理します．
epoll_wait()している間はスレッドはスリープするので，無駄なCPUを利用しません．
ここではepollの適当なラッパーを作成して利用していますが，実際にepollを使う場合はmioが利用できます． mioはLinux以外にもBSDやWindowsに対応した，ノンブロッキングネットワーク処理のためのライブラリです．（epollはLinuxの機能で，mioはBSDではkqueue, WindowsではIOCPという機能を利用しています）．mioは後述のtokioやasync-stdでも利用されています．
(補足) epollのレベルトリガとエッジトリガ
epollを利用するにあたり，ソケットにO_NONBLCOKを設定する必要は必ずしもありません．
O_NONBLOCK属性の有無に関わらずepoll_wait()は登録したdescriptorのいずれかが準備完了になったらそれを通知します．
epoll_wait()にはレベルトリガ（デフォルト）とエッジトリガモードがあります．
この違いはイベントの通知がイベント発生時にのみ生じるかどうかです．
例えば，epoll_wait()して2048byteのデータが読み込み可能になったとします．
このときread()で1024byteだけ読みだした場合，レベルトリガでは再びepoll_wait()するとまた読み出し可能であることを通知しますが，エッジトリガモードだと通知しません．
エッジトリガモードは通常O_NONBLOCKなdescriptorと合わせて利用します．
エッジトリガモードで読み出し可能であることを検出したら，プログラムはEWOULDBLOCKが返ってくるまでread()をしてデータを読みだします．この方が逐一readの度にepoll_wait()する必要がなく，効率的です．
readに関して使い方をまとめると，以下のようになると思います．
- レベルトリガ =>
read()のたびに逐一epoll_wait()する．さもないとread()がブロックすることがある． - レベルトリガ +
O_NONBLOCK=>epoll_wait()からリターンしたら，EWOULDBLOCKが返るまでread()する．あるいは，逐一epoll_wait()をすることもできる． - エッジトリガ => これは使用しない．さもないとデータを取りこぼす可能性がある．
- エッジトリガ +
O_NONBLOCK=>epoll_wait()からリターンしたら，EWOULDBLOCKが返るまでread()する．
また，epollの前身であるselectには，もしselectが準備完了を通知しても，実際には準備完了でないという spurious wakeup *1 が生じる可能性がありました．
この場合，O_NONBLOCKが指定されていなければread()はブロックすることになります．
epollで同様の問題が生じるのかはmanページは何も記述が無いですが，安全のためにはO_NONBLOCKを指定するのが吉かと思います．
epollは複数スレッドから同じepoll fdに対してepoll_wait()することも可能ですが（主にロードバランシング用途），この場合もエッジトリガモードを利用する必要があります．
さもなければ，複数のスレッドが同じfdに対してwake upする可能性があります．
また，実際にはエッジトリガモード (EPOLLET)を使うだけでは駄目で，他にもいろいろと嵌りどころがあります（参考）．
マルチスレッドでepoll fdを共有して扱うのは非常に難しいので，避けられるなら避けた方が良いです．
なお，mioはデフォルトはエッジトリガモードで動作するようになっています(例)．
async/await版 echo server
ようやく本題．
epollを利用したecho serverではイベントループ内で各コネクションを処理していました． これを最初に作成したecho serverのように処理できないか? ということで登場するのがasync/awaitです．
async/await + αを利用すると，以下のようなecho serverが作成できます（ソース）．
async fn handle_client(stream: TcpStream) -> io::Result<()> { let mut buf = [0u8; 1024]; info!("(handle client) {}", stream.0); loop { let n = stream.read(&mut buf).await?; if n == 0 { break; } stream.write(&buf[..n]).await?; } Ok(()) } fn main() { init_log(); let (executor, spawner) = new_executor_and_spawner(); let spawner_clone = spawner.clone(); let mainloop = async move { let addr = Ipv4Addr::new(127, 0, 0, 1); let port = 8080; let listner = TcpListener::bind(addr, port)?; let incoming = listner.incoming(); while let Some(stream) = incoming.next().await { let stream = stream?; spawner.spawn(handle_client(stream)); } Ok(()) }; spawner_clone.spawn(mainloop); drop(spawner_clone); executor.run(); }
以下いくつかポイントを説明します．なお，基本的なところはasync-bookを読むと分かりやすいです．
std::future::Future
rustの非同期処理の肝になるのがstd::future::Futureトレイト（および，std::task::Pollです．
これは以下のように定義されます．
pub trait Future { type Output; fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output>; } pub enum Poll<T> { Ready(T), Pending, }
Futureはpoll()されると，処理が実行できるのなら処理を実行してPoll::Ready(T)を返し，そうでなければPoll::Pendingをリターンします．pendingのfutureは後で再びpollします．
ここでPin<T>は自身がmoveしない/or moveしても問題ないことを保証するためのもで，またContextは後述のfutureのwake upに利用されます．
accept()に関するfutureは以下のように定義できます．
struct AcceptFuture<'a>(&'a TcpListener); impl<'a> Future for AcceptFuture<'a> { type Output = Option<io::Result<TcpStream>>; fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> { match self.0.accept() { Ok(stream) => { stream.setnonblocking()?; Poll::Ready(Some(Ok(stream))) } Err(ref e) if e.kind() == io::ErrorKind::WouldBlock => { REACTOR.add_event((self.0).0, EpollEventType::In, cx.waker().clone())?; Poll::Pending } Err(e) => Poll::Ready(Some(Err(e))), } }
ここで，
accept()が成功か，あるいはEWOULDBLOCK以外のエラーであれば，それをそのまま返す- そうでなければ（
EWOULDBLOCKの場合），reactorにfile descriptorの監視を依頼して，Poll::Pendingを返す．
reactorに関しては後述します．
Executor
futureはpoll()しないと何も処理してくれません．futureを実行するものをexecutorと呼びます．
executorをどう作成するか，というのはいろいろと設計の余地がありますが，今回はasync-bookに書かれた方法と同じ手法を利用しています． executorはキューを持っていて，そのキューに入ってきたfutureを順に実行します．
（本当はfuturesクレートは使わない予定でしたが，流石に辛くなったのでBoxFutureとArcWakeは使いました．）
Reactor
ソケットIOがEWOULDBLOCKになったとき，どこかでepoll_wait()してそのソケットを監視する必要があります．
このIOの準備状態を監視するものをreactorと呼びます．
今回はreactor用のスレッドを立ち上げて，そこでepoll_wait()しています．これはasync-stdと同様の方法です．
なので，このasync/await版のecho serverは実は2スレッドで動作しています．
なお，epollは監視対象のdescriptorが何も無い状態でepoll_wait()を開始することができ，epoll_wait()しているスレッド外からepoll_ctl(EPOLL_CTL_ADD)で監視するdescriptorを追加できます．
epoll_wait()から通知を受けたらどうするか? というとこれはもともとpoll()されたときのContextに入っていたwakerを利用して，executorに対して準備完了となったfutureを追加します．これもasync-bookと同様の手法を利用しています．
全体の動作は簡単に図にすると以下のようになります（ちょっと無理して図にしている点があります）．
executorとreactorの設計はこうしなければならないと決まっている訳ではありません． executorとreactorを1スレッドで動作させることも十分ありえます． futureがSendでなければローカルなexecutorが，一つ一つのfutureの計算処理が割と重いのであれば，パフォーマンスを出すにはマルチスレッドなexecutor/reactorが必要になります．
async/await構文
ここまでasync/await構文に触れていないので，結局何なんだという話ですが，async fn () -> R {...} はfn () -> impl Future<Output=R> {...}とだいたい同じになります．
要するに，コンパイラがstd::future::Futureを実装したstructを作成してくれるということです．
また，.awaitを利用すると，async関数内で別のfutureの実行完了を待つことができます．
つまり，poll()したときに，.awaitしているfutureがPoll::Pendingを返したらそこで処理が中断され，再びpoll()したらそこから処理が再開されるようになります．
これによって，自分でいちいちFutureを実装する必要が無くなります（本当にコアの部分に関しては実装する必要がありますが）．
他にも借用権周りで従来できなかった記述ができるようになっているようです．
もう少し具体例をいうと，例えば今回作成したasync fn handle_client(stream: TcpStream) -> io::Result<()>を呼び出して，let client = handle_client(stream);とすると，下で定義したようなstructが得られます（なお，例で示してるだけで，実際にコンパイラが出力したコードではないです）．
struct handle_client_future { stream: TcpStream, buf: [0u8; 1024], ... } impl Future for handle_client future { type Output = io::Result<()>; fn poll(...) -> Poll::<Self::Output> { ... } } fn handle_client(stream: TcpStream) -> handle_client_future { return handle_client_future { stream: stream, ... } }
このことがわかると，let client = handle_client(stream);しただけではfutureが生成されるだけなので，誰かがpollしないとfutureが実行されないということが理解できます．
futureの実行はexecutorでおこないます．
epollの挙動
async/await版のecho serverと，その前に作成したepoll版echo serverでは，以下の点でepollの使い方が異なります．
- epoll版
- コネクション設立時に
epoll_ctl(EPOLL_CTL_ADD)でfdを登録 epoll_ctl(EPOLL_CTL_MOD)を利用して，in/outの待ちを切り替える
- コネクション設立時に
- async/await版
- read/writeの度に逐一
epoll_ctl(EPOLL_CTL_ADD)/epoll_ctl(EPOLL_CTL_DEL)を実行
- read/writeの度に逐一
async/await版の方が2倍多くシステムコールが発行されることになります．
これはread().awaitやwrite().awaitごとに独立したfutureが生成されることに起因しています．
これを減らすには構成を変更する必要がありますが，ちょっと工夫が必要な気がします．
async/awaitの実際
async/awaitに対応したライブラリが続々出ています．通常はこれらを利用することになると思います．
例えば，async-stdというrustのstdの非同期版を目指すライブラリを利用すればecho serverは以下のように書けます（examples/tcp-echo.rs）．
use async_std::io; use async_std::net::{TcpListener, TcpStream}; use async_std::prelude::*; use async_std::task; async fn process(stream: TcpStream) -> io::Result<()> { println!("Accepted from: {}", stream.peer_addr()?); let (reader, writer) = &mut (&stream, &stream); io::copy(reader, writer).await?; Ok(()) } fn main() -> io::Result<()> { task::block_on(async { let listener = TcpListener::bind("127.0.0.1:8080").await?; println!("Listening on {}", listener.local_addr()?); let mut incoming = listener.incoming(); while let Some(stream) = incoming.next().await { let stream = stream?; task::spawn(async { process(stream).await.unwrap(); }); } Ok(()) }) }
他の非同期処理ライブラリとしてはかの有名なtokio*2やもうちょっと上位の(?)runtime，no_std向けのembrioなどがあります．
まとめ
rustのasync/await構文は非同期処理を簡潔に記述する上で非常に重要な一方で，それだけでは非同期処理は実現できません． async/awaitをつければ勝手に非同期化されるような魔法のキーワードでもありません．
実際に利用する際は何かライブラリ（ランタイム）が必要になります． そして，ランタイムのアルゴリズム（executorやreactorの動作）はライブラリが柔軟に選択できるような設計になっています． 逆にいえば，アプリケーションのコードは多少なりともライブラリに依存する形になります．
個人的にasync/awaitの利点は，パフォーマンス的な側面もありますが，これまでのイベントループやコールバックで書いていた処理が分かりやすく書くことができるようなるというのが大きいと思っています． 一方で，rustは言語自体にはランタイムを（ほぼ）持たないという選択をしているため，現状async/await実行のためのランタイムライブラリが乱立状態にあり，あまりまとまっていない印象を受けます． 例えばtokioとasync-stdが共存できるのか，ぱっと見ただけでは分かりません（簡単にはできないような気がします）． またどんなときに何を使うべきかというのもはっきりしていないように思います． このあたりは今後rust 1.39が出てから徐々に解決されていくのかなと期待します．
async/awaitに見せかけたepollの文章でした
参考文献
- RFC
- ドキュメント
- ライブラリ
- その他
- epoll
*1:Under Linux, select() may report a socket file descriptor as "ready for reading", while nevertheless a subsequent read blocks. This could for example happen when data has arrived but upon examination has wrong checksum and is discarded. There may be other circumstances in which a file descriptor is spuriously reported as ready. Thus it may be safer to use O_NONBLOCK on sockets that should not block. - http://man7.org/linux/man-pages/man2/select.2.html
*2:ちなみに読み方はﾄｷｵじゃなくてﾄｰｷｮｰっぽい
x2APICとinterrupt remapping
以前IOAPICやMSI/MSI-Xを利用するデバイスでx2apicを利用するにはinterrupt remapingを利用すると書きました．
今回実際のマッピングを調べることがあったので，ここに要点をまとめます． 図はVT-dのドキュメントからの引用です．
前提
Interrupt RemappingのサポートはVT-dレジスタのExtended Capability Registerの3bit目(IR: Interrupt Remapping support)で示されます．
VT-dレジスタのアドレスはACPIのDMARのDRHDに記載されています．
またVT-dレジスタのGlobal Command Register (18h)のIRE: Interrupt Remapping Enableを利用してInterupt remapingを有効化します．
Interrupt Remappingの設定
Interrupt Remappingを利用するには，以下の設定が必要です．
デバイス側
MSI/MSI-Xを利用するデバイスは，割り込みを生成するときに，以下に示す"Remappable Format Interrut Request"でMSIを設定します．
通常のMSIと異なり，割り込みアドレスに割り込みベクタ番号やdestination IDはエンコードされていません．Interrupt indexで次に説明するInterrupt remapping table entryのインデックスを指定します．
（ここから分かるように，Interrupt Remappingを利用する場合には，デバイスの方の割り込み設定も適切に設定する必要があります．デバイス設定に透過でinterrupt remappingを利用することはできません．）
IRTE (Interrupt Remapping Table Entry)
IRTEで実際の変換の内容を設定します．IRTEにはinterrupt remapping用と，posted interrupts用の二種類存在します．
interrupt remappingを利用する場合は，以下のようなエントリになります．
IRTEのベースアドレスはVT-dレジスタのInterrupt Remapping Table Address Register (0B8h)に格納されています．
Invalidation
IRTEエントリのキャッシュの無効化はInvalidation Queueを用いておこないます．
確認
x2APICを有効にしたLinuxマシンでMSIの設定とRITEエントリを確認しました．
% sudo lspci -vvv -s 05:00.0
05:00.0 Non-Volatile memory controller: OCZ Technology Group, Inc. RD400/400A SSD (rev 01) (prog-if 02 [NVM Express])
...
Capabilities: [b0] MSI-X: Enable+ Count=8 Masked-
Vector table: BAR=0 offset=00002000
PBA: BAR=0 offset=00003000
MSI-X ベクタテーブル
% for j in `seq 0 1 64`; do; for i in `seq $((($j+1)*16-4+8192)) -4 $(($j*16+8192))`; sudo ./pcimem /sys/devices/pci0000:00/0000:00:1d.0/0000:05:00.0/resource0 $i w | tail -n1 | cut -d':' -f 2 | tr '\n' ' '; echo ; done 0x0 0x0 0x0 0xFEE00258 0x0 0x0 0x0 0xFEE00378 0x0 0x0 0x0 0xFEE00398 0x0 0x0 0x0 0xFEE003B8 ...
左がMessage data, 一番右がMessage Addressです． 上からそれぞれ利用するIRTEのインデックスは18, 27, 28, 29です．
IRTE
適当なカーネルモジュール書いて確認したら以下のようになりました．
[ 2459.161111] vtd: irta = 0x0000000460500000, eime = 1, s = 2^15 [ 2459.161112] vtd: 0 000000010083002d, 0000000000040500 [ 2459.161112] vtd: P: 1 [ 2459.161113] vtd: FPD: 0 [ 2459.161113] vtd: Destination mode: 1 [ 2459.161113] vtd: Redirection Hint: 1 [ 2459.161114] vtd: Trigger Mode: 0 [ 2459.161114] vtd: Delivery Mode: 1 [ 2459.161114] vtd: AVAIL: 0 [ 2459.161115] vtd: VECTOR: 131 [ 2459.161115] vtd: Destination ID: 1 [ 2459.161115] vtd: SID: 0x500
ここで，最初の行がInterrupt Remapping Table Address Registerの値で，eime=1なのでx2APICモードです． その下がIRTEの中身です．
参考文献
複数の仮想ページに同じ物理ページをマッピングする方法 (Linux)
小ネタ．
Linuxで複数の仮想ページを一つの物理ページにマッピングする方法です．
連続した仮想ページを全て同じ物理ページにマッピングしたいということがあって，原理的にはページテーブルで同じ領域を指すだけです．でもユーザ空間からはどうするんだっけ?と思ったらそういえばspectreのPOCでそんなことやっていたなと思い出したのでそれを参考に作ってみました．
#define _GNU_SOURCE #include <assert.h> #include <fcntl.h> #include <stdint.h> #include <stdio.h> #include <string.h> #include <sys/mman.h> #include <sys/stat.h> #include <sys/types.h> #include <unistd.h> void *map(int num_pages) { int fd, pagesize = getpagesize(); void *area; char *start, *end, *p, *q; size_t length = pagesize * num_pages; // reserve virtual address space area = mmap(NULL, length, PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0); assert(area != MAP_FAILED); assert(munmap(area, length) == 0); // create temp file whose size is a pagesize fd = open("/tmp", O_TMPFILE | O_RDWR, 0600); assert(fd != -1); assert(ftruncate(fd, pagesize) == 0); // mmap each virtual page to the same physical page start = area; end = start + length; for (p = start; p < end; p += pagesize) { q = mmap(p, pagesize, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_SHARED | MAP_FIXED | MAP_POPULATE | MAP_NORESERVE, fd, 0); assert(p == q); } assert(close(fd) == 0); return area; }
仕組みとしてはサイズがページサイズのファイルをopen（ここではtempfileを作成）し，そのfdに対してmmapするだけです．mmapの第一引数で仮想アドレスが指定できます．
ここでは連続した仮想アドレスを同じページにmmapするということをしています． ここで問題となるのは，空いている仮想アドレス空間が確保できるかどうかという点です． ユーザが適当に仮想アドレスを決めた場合，すでにそのアドレスが使用されている可能性があります（mmapは失敗する）．
そこでここでは最初に必要な仮想アドレス空間の領域をmmapしています．
mmapの第一引数をNULLにすればOSが適当な領域を見つけてくれます．
また，MAP_NORESERVE指定することで，物理ページの割り当てなしに領域の確保が可能です．
使用可能なアドレスが分かったら，その領域にmmapするために一旦unmapしてあとは先述の方法でmmapしていきます．
本当に同じアドレスにマッピングされているかは/proc/self/pagemapから確認できます（ちなみにproc/self/pagemapの参照にはCAP_SYS_ADMIN（root権限）が必要です）．
static uintptr_t virt_to_phys(void *virt) { long pagesize = getpagesize(); int fd = open("/proc/self/pagemap", O_RDONLY); assert(fd != -1); off_t ret = lseek(fd, (uintptr_t)virt / pagesize * sizeof(uintptr_t), SEEK_SET); assert(ret != -1); uintptr_t entry = 0; ssize_t rc = read(fd, &entry, sizeof(entry)); assert(rc > 0); assert(entry != 0); assert(close(fd) == 0); return (entry & 0x7fffffffffffffULL) * pagesize + ((uintptr_t)virt) % pagesize; } int main() { int pagesize = getpagesize(); int i, num_pages = 100; char *p = map(num_pages); for (i = 0; i < num_pages; i++, p += pagesize) { printf("%016llx, %016llx\n", (unsigned long long)p, (unsigned long long)virt_to_phys(p)); } return 0; }
実行結果
% sudo ./a.out 00007f6e950f7000, 0000000fe7773000 00007f6e950f8000, 0000000fe7773000 00007f6e950f9000, 0000000fe7773000 00007f6e950fa000, 0000000fe7773000 00007f6e950fb000, 0000000fe7773000 00007f6e950fc000, 0000000fe7773000 00007f6e950fd000, 0000000fe7773000 00007f6e950fe000, 0000000fe7773000 ...
上記コードはここにあります．
American Fuzzy Lop (AFL)の構造
AFLとは
American Fuzzy Lop (AFL)はファジングツールの一つです．
ファジングとはプログラムの脆弱性検査手法の一つで，簡単に言ってしまえばあるプログラムをランダムな引数で実行することを繰り返して，プログラムがクラッシュするような入力を探そうという方法です． なんとも場当たり的な対応で心許ない気もしますが，実際には洗練されたアルゴリズムを利用することで一般に良く機能します．
世の中ファジングツールは数多く存在しますが，AFLはその利用の簡単さと，何よりも何百何千というバグを実際に見つけている運用実績で有名です． 最近は更新が止まっているようですが，AFLはコードが簡潔にまとまっており，AFLを参考に作られてたファジングツールも多く存在します．
AFLの技術的詳細はAFLの作者がtechnical_details.txtにまとめています． これを読むとAFLの概要は分かりますが，実際のコードに関する情報はあまりないように思うので，ここに簡単に書いてみます．
対象のAFLのバージョンは2.52bです． AFLはとりあえず実際に動かしてみた方が以下の文章の理解が進むと思います（とても簡単に利用できます）．
ソースの概要
まず，AFLのソースディレクトリには，afl-xxx.cというファイルがありますが，特にメインになるのは，
afl-gcc.c,afl-as.c,afl-as.hafl-fuzz.c
です．前者をファジング対象のプログラムのコンパイルに利用，後者を実際のファジングに利用します．
その他のものはAFLの補助ツールになります． 引数なしで実行すればそれぞれのツールのhelpが見れます． ここでは各ツールの詳細は省略して，上記の主処理部分をみていきます．
コンパイル処理 / カバレッジ計算
AFLはcoverage-based fuzzingあるいはgray-box fuzzingなどと呼ばれるファジング手法に分類されます． これは，ある入力でプログラムを実行したときのコードカバレッジを測定し，その情報を利用して次の入力を決定していく手法です．
AFLでは条件付分岐を区切りとしたコードのまとまり単位でカバレッジを計算します(branch coverage)． このために，AFLはコンパイル時にカバレッジ計算のコードをプログラムに挿入します． 例えば，以下のようなプログラムがあった場合，
if (...) {
...
}
...
afl-gccでコンパイルすると，以下のようになります．
__log_coverage()
if (...) {
__log_coverage()
...
}
__log_coverage()
...
AFLはこのcode instrumentationを，アセンブラの段階でおこないます．
afl-gccはgccの単純なラッパーで，アセンブラとしてafl-asを呼び出します．
afl-asはadd_instrumentation()で，出力されたアセンブリを行ごとに処理して，条件付ジャンプ命令 (jから始まる命令)の直後にカバレッジ計算のコードを挿入します．
この辺り，構文解析している訳ではないので処理がかなりシンプルです．
カバレッジ計算のコードの本体は，afl-as.hで以下のように定義されています．
このコードは，適当にレジスタの退避をして，rcxにコンパイル時に生成した値を入れたあとに，__afl_maybe_logを呼び出します．
static const u8* trampoline_fmt_64 = "\n" "/* --- AFL TRAMPOLINE (64-BIT) --- */\n" "\n" ".align 4\n" "\n" "leaq -(128+24)(%%rsp), %%rsp\n" "movq %%rdx, 0(%%rsp)\n" "movq %%rcx, 8(%%rsp)\n" "movq %%rax, 16(%%rsp)\n" "movq $0x%08x, %%rcx\n" # ここの部分($0x%08xはフォーマッタ)にfprintf()で乱数が挿入される "call __afl_maybe_log\n" "movq 16(%%rsp), %%rax\n" "movq 8(%%rsp), %%rcx\n" "movq 0(%%rsp), %%rdx\n" "leaq (128+24)(%%rsp), %%rsp\n" "\n" "/* --- END --- */\n" "\n";
afl_maybe_logはmain_payload_64内で定義されます．
technical_details.txtに書いてある通り，AFLのカバレッジの計算は以下のようになります．
cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;
ここでまず，共有メモリ(shared_mem)領域は，後述のafl-fuzzがプログラムを実行する際に確保して，環境変数経由（SHM_ENV_VAR）でファジング対象のプログラムと共有します．
この共有メモリ上に，プログラムがどこにアクセスしたのかを記録していきますが，AFLでは上記のように，("今の場所" ^ "直前の場所">>1)をキーとして利用します．
つまり，AFLではある地点から別の地点への遷移を記録していきます．
直前の場所の値をシフトをする理由はA -> B と B -> A の遷移や，A -> A と B -> B の遷移を区別するためです．
ドキュメントでは遷移 A -> B は (A, B)と，タプルとして表現されています．
AFLでは，A -> B -> C と A -> C -> B の遷移は区別されます．
一方で，時系列情報は含まれていないので，A -> B -> C -> A と B -> C -> A -> B は同じカバレッジとして扱われることになります．
AFLで使用する共有メモリのサイズは64KBです．当然ながらキーが衝突する可能性がありますが，AFLは衝突は無視します（単純に同じ遷移として扱う）． ドキュメントには以下のように分岐の数が10kを超えるプロジェクトでも衝突確率が10%前後ということが書いてあります．
Branch cnt | Colliding tuples | Example targets
------------+------------------+-----------------
1,000 | 0.75% | giflib, lzo
2,000 | 1.5% | zlib, tar, xz
5,000 | 3.5% | libpng, libwebp
10,000 | 7% | libxml
20,000 | 14% | sqlite
50,000 | 30% | -
カバレッジの測定には，コスト（スピードや必要メモリ量）と精度の関係にトレードオフがあります． 今回カバレッジを測定する目的は，ファジング実行時の入力選択のアルゴリズムで利用するからであって，それに十分であれば厳密にカバレッジ情報を取得する意味はありません． AFLでは経験的にファジングにいい感じのカバレッジ測定をおこないます．
なお，AFLにはLLVMの中間言語レベルでcode instrumentationするafl-clang-fastや，ソースコードがないプログラムのために，QEMUのuser mode emulationを利用してカバレッジを計算するqemu-mode（ただし遅い）もあります．
ファジング処理
ファジングの本体であるafl-fuzz.cをみていきます．
main関数はおおまかには以下のようになっています．
int main(int argc, char** argv) { // 初期化処理 ... setup_shm(); ... read_testcases(); ... perform_dry_run(use_argv); ... // ファジング処理 while (1) { cull_queue(); ... skipped_fuzz = fuzz_one(use_argv); ... } ...
初期化処理
いくつか主要な処理を以下で説明します．
なお，AFLは一旦中断したファジングを再開することができるので，そのための処理もおこなっています（ここでは説明は省略）．
setup_shm()
カバレッジ計算用の共有メモリを確保して，それを環境変数に設定します．
EXP_ST void setup_shm(void) { ... shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600); ... shm_str = alloc_printf("%d", shm_id); if (!dumb_mode) setenv(SHM_ENV_VAR, shm_str, 1); ... trace_bits = shmat(shm_id, NULL, 0); ... }
trace_bitsが作成した共有メモリで，これにカバレッジの情報が記録されます．
この共有メモリのサイズはu8 [65536]です．
trace_"bit"という名称ですが，実際には遷移(A,B)のタプルの出現回数を8bitで計数します．
ちなみにdumb_modeはコンパイル時のcode instrumentationを使用しないモードです（当然効率は落ちる）．
read_testcases()
inputで指定したディレクトリから全てのテストケースを読み込みます． AFLでは，以下のqueueでテストケースを管理します． queueのエントリはファイルの情報の他に，そのファイルに対するファジングの情報を保持しています．
struct queue_entry { u8* fname; /* File name for the test case */ u32 len; /* Input length */ u8 cal_failed, /* Calibration failed? */ trim_done, /* Trimmed? */ was_fuzzed, /* Had any fuzzing done yet? */ passed_det, /* Deterministic stages passed? */ has_new_cov, /* Triggers new coverage? */ var_behavior, /* Variable behavior? */ favored, /* Currently favored? */ fs_redundant; /* Marked as redundant in the fs? */ u32 bitmap_size, /* Number of bits set in bitmap */ exec_cksum; /* Checksum of the execution trace */ u64 exec_us, /* Execution time (us) */ handicap, /* Number of queue cycles behind */ depth; /* Path depth */ u8* trace_mini; /* Trace bytes, if kept */ u32 tc_ref; /* Trace bytes ref count */ struct queue_entry *next, /* Next element, if any */ *next_100; /* 100 elements ahead */ };
perform_dry_run()
static void perform_dry_run(char** argv) { struct queue_entry* q = queue; ... while (q) { ... res = calibrate_case(argv, q, use_mem, 0, 1); ... q = q->next; } ... }
ファジングを始める前にinputのtest caseを使ってターゲットプログラムを実行します．
これの目的は，test caseのカバレッジ情報を取得することの他に，inputにクラッシュするようなテストケースがないか（AFLはクラッシュするテストケースは，ファジングの入力候補としては利用しません）や，test caseがタイムアウトしてしまわないか（この場合は，afl-fuzzに与えたタイムアウト条件が厳しすぎるかもしれない）などを調べるためです．
実際にプログラム実行を担当するのは後述のcalibrate_case()です．
calibrate_case()
static u8 calibrate_case(char** argv, struct queue_entry* q, u8* use_mem, u32 handicap, u8 from_queue) { ... // forkserverの初期化 if (dumb_mode != 1 && !no_forkserver && !forksrv_pid) init_forkserver(argv); ... for (stage_cur = 0; stage_cur < stage_max; stage_cur++) { ... // ターゲットの実行 fault = run_target(argv, use_tmout); ... // カバレッジのbitmapのハッシュ値の比較 cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST); if (q->exec_cksum != cksum) { u8 hnb = has_new_bits(virgin_bits); if (hnb > new_bits) new_bits = hnb; if (q->exec_cksum) { u32 i; for (i = 0; i < MAP_SIZE; i++) { // 最初のトレース結果と異なるbitmapの箇所はマークする // この情報はstatsに使用 if (!var_bytes[i] && first_trace[i] != trace_bits[i]) { var_bytes[i] = 1; stage_max = CAL_CYCLES_LONG; } } var_detected = 1; } else { // 一番最初の実行結果は`first_trace`に保存 q->exec_cksum = cksum; memcpy(first_trace, trace_bits, MAP_SIZE); } } } ... }
まず，この関数を最初に実行した場合は，init_forkserver()で後述のfork serverの初期化をおこないます．
その後，ループで複数回ターゲットプログラムを実行し，コードのカバレッジや実行時間を測定します． 複数回実行する理由は，プログラムによっては同じ入力でも実行する度にコードパスや実行時間が変化する可能性があるからです（例えば内部で何か乱数に応じた処理をしている場合など）．
run_target()を実行すると，trace_bitsに実行したカバレッジのbitmapが格納されます．
その後，前に実行したtrace_bitsのハッシュ値と，新規に得られたtrace_bitsのハッシュ値が異なる場合は，has_new_bits(virgin_bits)で新規のパスがカバレッジのbitmapに含まれているかを確認します．
virgin_bitsは最初全て1のglobalなbitmapです．
has_new_bits()はtrace_bitsに今まで観測しいていない情報が含まれているかを調べ，もしあったらvirgin_bitsを更新します．
has_new_bits()はtrace_bitsに新しいタプル（遷移）が含まれていたら2を，すでにタプルは観測済みだが計数結果が更新された場合は1を返します．
run_target()およびfork server
run_target()はファジング対象のプログラムを実行します．
fork serverを使う方法と使わない方法がありますが，ここでは使う場合を説明します．
まず，そもそもの話として，ファジング対象のプログラムをどうやって実行するのかという話があります． 代表的な方法はfork+execveを使用してファジング対象のプロセスを生成して実行する方法で，AFLもデフォルトでこの方式を利用します． この方式はターゲットのプログラムの修正が必要がなく，簡単に利用できる一方で，fork+execveはオーバヘッドが大きいことで知られており，また，そもそもプログラムの初期化に時間がかかり，ファジングしたい箇所に到達するまでに時間がかかるということもあります．
別の方法として，もしファジングしたい処理が関数として呼び出し可能であれば，それをファジングするプロセスから呼び出すという方法が考えられます． この方式はファジング対象のプログラムを呼び出すための処理を自分で書く必要がありますが，fork+execveや初期化のオーバヘッドが無く，高速にファジング対象を実行することができます．ただし，何か関数がグローバルな状態に依存するような場合は注意が必要です． クラッシュ時の対応も別途考える必要があります． 例えばLibFuzzerはデフォルトでこの方式でファジングをします． AFLも，"persistent mode"という名称でこの機能をサポートしています．
さて，前述のようにAFLではデフォルトではfork+execveでプロセスを実行しますが，少しでもオーバヘッドを削減するために，fork serverという仕組みを利用します．
これは，fork+execveでターゲットプログラムを実行しますが，ターゲットプログラムはエントリポイント（正確には最初にカバレッジを記録する箇所）でファジング側の指示を待つために停止します．
その後，ファジング側の指示を受信すると，ターゲットプログラムはその止まっていた箇所から新たにfork()して，子プロセスが処理を続けます．
こうすることで，execveやダイナミックリンクのオーバヘッドを避けてターゲットプログラムを実行することができます．
ファジングプロセスとの通信やforkするためのコードはafl-gccでコンパイルした際に仕込みます．
AFLはinit_forkserver()でforkしたのち，メモリ制限などをかけた上でexecveでターゲットプログラムを起動します．
このとき，dup(2)を使って制御通信用のfile descriptorを用意しています．
EXP_ST void init_forkserver(char** argv) { ... forksrv_pid = fork(); ... if (!forksrv_pid) { struct rlimit r; /* Umpf. On OpenBSD, the default fd limit for root users is set to soft 128. Let's try to fix that... */ if (!getrlimit(RLIMIT_NOFILE, &r) && r.rlim_cur < FORKSRV_FD + 2) { r.rlim_cur = FORKSRV_FD + 2; setrlimit(RLIMIT_NOFILE, &r); /* Ignore errors */ } if (mem_limit) { r.rlim_max = r.rlim_cur = ((rlim_t)mem_limit) << 20; setrlimit(RLIMIT_AS, &r); /* Ignore errors */ } /* Dumping cores is slow and can lead to anomalies if SIGKILL is delivered before the dump is complete. */ r.rlim_max = r.rlim_cur = 0; setrlimit(RLIMIT_CORE, &r); /* Ignore errors */ /* Isolate the process and configure standard descriptors. If out_file is specified, stdin is /dev/null; otherwise, out_fd is cloned instead. */ setsid(); dup2(dev_null_fd, 1); dup2(dev_null_fd, 2); if (out_file) { dup2(dev_null_fd, 0); } else { dup2(out_fd, 0); close(out_fd); } /* Set up control and status pipes, close the unneeded original fds. */ if (dup2(ctl_pipe[0], FORKSRV_FD) < 0) PFATAL("dup2() failed"); if (dup2(st_pipe[1], FORKSRV_FD + 1) < 0) PFATAL("dup2() failed"); close(ctl_pipe[0]); close(ctl_pipe[1]); close(st_pipe[0]); close(st_pipe[1]); close(out_dir_fd); close(dev_null_fd); close(dev_urandom_fd); close(fileno(plot_file)); /* This should improve performance a bit, since it stops the linker from doing extra work post-fork(). */ if (!getenv("LD_BIND_LAZY")) setenv("LD_BIND_NOW", "1", 0); /* Set sane defaults for ASAN if nothing else specified. */ setenv("ASAN_OPTIONS", "abort_on_error=1:" "detect_leaks=0:" "symbolize=0:" "allocator_may_return_null=1", 0); /* MSAN is tricky, because it doesn't support abort_on_error=1 at this point. So, we do this in a very hacky way. */ setenv("MSAN_OPTIONS", "exit_code=" STRINGIFY(MSAN_ERROR) ":" "symbolize=0:" "abort_on_error=1:" "allocator_may_return_null=1:" "msan_track_origins=0", 0); execv(target_path, argv); /* Use a distinctive bitmap signature to tell the parent about execv() falling through. */ *(u32*)trace_bits = EXEC_FAIL_SIG; exit(0); } ... }
ターゲットプログラム側の処理はafl-as.hで定義されています．
run_target()では，init_forkserver()で用意したfile descriptorを利用してターゲットのプロセスにメッセージを送ることで実際のファジングを開始します．
static u8 run_target(char** argv, u32 timeout) { ... s32 res; /* In non-dumb mode, we have the fork server up and running, so simply tell it to have at it, and then read back PID. */ // ターゲットプログラム側に処理実行をリクエスト if ((res = write(fsrv_ctl_fd, &prev_timed_out, 4)) != 4) { if (stop_soon) return 0; RPFATAL(res, "Unable to request new process from fork server (OOM?)"); } if ((res = read(fsrv_st_fd, &child_pid, 4)) != 4) { if (stop_soon) return 0; RPFATAL(res, "Unable to request new process from fork server (OOM?)"); } if (child_pid <= 0) FATAL("Fork server is misbehaving (OOM?)"); ... // 実行結果のstatus codeをターゲットプログラムから受信する if ((res = read(fsrv_st_fd, &status, 4)) != 4) { if (stop_soon) return 0; RPFATAL(res, "Unable to communicate with fork server (OOM?)"); } ... classify_counts((u64*)trace_bits); }
run_target()では最後にclassify_counts()という関数を読んでいますが，この関数はカバレッジの計数結果を以下の8つに分類します．
1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+
つまり，AFLでは例えばあるA -> Bという遷移を5回実行したものと，6回実行したものは区別しません．
これは例えばたくさんループ処理するような場合で，少しだけループ回数が変わってもそれは別のパスとは考えないということになります．
このfork serverを応用すると，プログラムの途中まで処理を進めておいて，ファジングを開始したい箇所まできたら実行を中断し，あとはafl-fuzzの指示に応じてfork()してファジングするということが考えられます．
AFLはこの"deferred mode"をサポートしており，LLVMを利用してinstrumentationする場合に利用できます（参考: llvm_mode）．
ちなみに，fork serverを使ってもファジングを実行する度にforkはすることになります． AFLはマルチコアでのファジングをサポートしていますが，fork（や結果の同期）が遅くてスケールしにくいということが研究で指摘されています[1]．
- [1] Wen Xu et al., Designing New Operating Primitives to Improve Fuzzing Performance, https://taesoo.kim/pubs/2017/xu:os-fuzz.pdf, CCS'17.
Culling
AFLはキューの先頭から一つ一つ順番に入力を選択し，ファジングをしていきます． そして，ファジングによって新しいカバレッジを持つを入力が得られたらそれをキューに新規に追加します．
AFLは一度追加したエントリを削除することはしませんが，効率良くファジングを実行するために，エントリの中で特に有力そうなものをfavoredとして優先的に処理するようにチェックします．
この処理をcullingと呼び，cull_queue()および，update_bitmap_score() (この関数はcalibrate_case()から呼ばれる)がその処理を実行します．
アルゴリズムはtechnical_details.txtの4 Culling the corpusに書いてあります．
ざっくりというと，AFLは (プログラムの実行時間) * (入力のサイズ)をスコアとして，それぞれのカバレッジのbitに対して，そのスコアが最も小さいものをfavoredであるとします．
culling処理は新規に入力がキューに追加される度にに実行されます．
ファジング処理
fuzz_one() がファジング処理の本体です．
AFLは遺伝的アルゴリズムをベースとして，おおまかには以下のようにファジング処理をおこないます．
fuzz_one(){
1. favoredなtest caseが存在するかを確認
2. calibration
3. input trimming
4. performance scoreの計算
5. deterministic phase
- bitflip
- interest
- dctionary
6. non-deterministic phase
- havoc
- splice
}
AFLは，ファジングで使用する入力を一つキューから選択した後，その入力に対して，ある変換を適用+ファジング対象のプログラムを実行する，ということを複数回おこないます．
そして，得られたカバレッジが今まで観測してたことのないパスを含んでいた場合にのみ，その新しい入力をキューに追加します．
名前が紛らわしいかもしれまんせんが，fuzz_one()では一回だけ入力を改変して実行する，ということをおこなっている訳ではありません．
一般的な遺伝的アルゴリズムでは，世代ごとにどんどん個体が入れ替わっていきますが，AFLでは積極的にtest caseを入れ替えることはしません． 実験的にその方が結果が良いようです．
以下でそれぞれの処理を説明します．
favoredなtest caseが存在するかを確認
前述したculling処理で，キューのエントリはそれぞれfavoredであるかどうかチェックされています． もしfavoredでない場合は，一定確率に応じてその入力に対するファジングをスキップします．
calibration
perform_dry_runで実行したcalibrationと同じです．
事前のcalibrate_case()が失敗した場合，もう一度ここでcalibrationを試みるようです．
それでもcalibrationに失敗したら，このtest caseについてはファジングを諦めます．
input trimming
ファジングの入力はサイズが小さい方が，一般にターゲットプログラムの実行時間が短くなるので望ましいです．
fuzz_one()ではこの後なんどもファジングをしていくので，その前に入力のファイルサイズの削減を試みます．
これは単純に適当の連続領域を削除して，実行のカバレッジのハッシュ値が同じであったら実行結果が同じと判断するという戦略になっています．
なお，afl-tmin.cにもう少し良いアルゴリズム（ただし時間がかかる）が実装されています．
performance scoreの計算
平均実行時間などからperformance scoreを計算します． この値は後述のhavoc stageで入力の改変のパラメータとして利用されます． （実行時間が長いと，havoc stageの回数を減らす）．
Deterministic / Non-deterministic phase
ここからいよいよファジングを実行していきます．
AFLが施す入力に対する変換は，決定的なもの(deterministic)と，非決定的なものの二種類に分けられます． 決定的な処理にはbitflipであったり，事前に与えたdictionaryの情報を使った書き換えなどをします． この決定的な処理によって，効率よく入力のmagic number領域や，データ領域を推定することができます． 非決定的な処理は，一般の遺伝的アルゴリズムに近い，ランダムな変換処理をおこないます．
この処理はAFLで一番重要とも言える処理ですが，具体的なアルゴリズムは参考文献に詳しく書いてあるので，そちらを参照してください．
一度deterministic phaseをおこなうと，キューのpassed_detが1になるので，それに対しては今後deterministic phaseはおこなわなくななります．
common_fuzz_stuff()
deterministic phase, non-deterministic phaseともに，common_fuzz_stuff()という関数で実際のファジング処理を実行します．
この関数は前述のrun_target()でターゲットプログラムを実行したのち，save_if_interesting()で実行結果を確認します．
EXP_ST u8 common_fuzz_stuff(char** argv, u8* out_buf, u32 len) {
...
fault = run_target(argv, exec_tmout);
...
queued_discovered += save_if_interesting(argv, out_buf, len, fault);
...
}
save_if_interesting()は前述したhas_new_bits()で実行結果が新しいコードパスを含んでいるかどうかを調べ，そうであればキューに新規にエントリを追加します．
また，このタイミングでcalibrate_case()でcalibrationもおこないます．
/* Check if the result of an execve() during routine fuzzing is interesting, save or queue the input test case for further analysis if so. Returns 1 if entry is saved, 0 otherwise. */ static u8 save_if_interesting(char** argv, void* mem, u32 len, u8 fault) { ... if (!(hnb = has_new_bits(virgin_bits))) { if (crash_mode) total_crashes++; return 0; } ... add_to_queue(fn, len, 0); ... res = calibrate_case(argv, queue_top, mem, queue_cycle - 1, 0); ... }
ここでは省略していますが，もしクラッシュした場合は，その旨を記録します．
まとめ
AFLの構造について簡単に説明しました． ソースを見ればわかる通り，AFLは効率的なファジングのために様々なヒューリスティクスの塊となっています． ファジングのアルゴリズム本体以外にも，どう効率よくファジングをするかという工夫が随所に入っており，非常に面白いと思います．
最近はAFLよりももっと活発に開発され，より効率の良いとされるファジングツールもありますが，AFLは非常に使いやすく，まだまだ十分有用だと思います．
AFLの拡張
最後にAFLを拡張したものについて，いくつか紹介します，
近年AFLをベースにしたファジングツールの研究・開発が多く存在します． ソースが公開されていて著名なものには以下のようなものがあります（他にもあります）．
- aflfast
- Marcel Boehme et al., Coverage-based Greybox Fuzzing as Markov Chain, CCS'16
- AFLのシード選択方法（スケジューラ）の改善
- driller
- Nick Stephens et al., Driller: Augmenting Fuzzing Through Selective Symbolic Execution, NDSS'16
- AFLとSymbolic executionの組み合わせ
- aflgo
- Marcel Boehme et al., Directed graybox fuzzing, CCS'17
- FairFuzz
- Caroline Lemieux et al., FairFuzz: A Targeted Mutation Strategy for Increasing Greybox Fuzz Testing Coverage, ASE'18
- aflsmart
- Van-Thuan Pham et al., Smart Greybox Fuzzing, https://arxiv.org/abs/1811.09447, 2018.
- AFLをgrammar（ファイルの構造）awareに拡張
- winafl
- Windows用のAFL fork
AFL以外にもファジングツールは多く存在します． 例えばgithubで検索すればたくさん見つかります． AFLは一般のユーザランドアプリケーションが対象ですが，最近は他の用途に特化したもの，例えばネットワークプロトコルや，Javascriptエンジン，さらにはカーネル向けのものなど，様々なものが開発されています．
参考文献
- AFLのdocs
- 作者のBlog
- AFLのmutation戦略について
- Michal Zalewski, Binary fuzzing strategies: what works, what doesn't, https://lcamtuf.blogspot.com/2014/08/binary-fuzzing-strategies-what-works.html
- shimasyaro, American Fuzzy Lop internals, http://shimasyaro.hatenablog.com/entry/2018/03/26/184415
- 貴重な日本語でのAFLのmutation戦略の解説．詳しい．
- rk700, AFL内部实现细节小记, http://rk700.github.io/2017/12/28/afl-internals/
- rk700, AFL文件变异一览, http://rk700.github.io/2018/01/04/afl-mutations/
- 中国語だけどgoogle 翻訳すれば割と読める．わかりやすい．
- その他
- Brendan Dolan-Gavitt, Fuzzing with AFL is an Art, http://moyix.blogspot.com/2016/07/fuzzing-with-afl-is-an-art.html
- AFLの構造というよりかは，AFLを使用する場合（というか一般にファジングをする場合に）気をつけるべき点やテクニックが書いてある
- Brendan Dolan-Gavitt, Fuzzing with AFL is an Art, http://moyix.blogspot.com/2016/07/fuzzing-with-afl-is-an-art.html
NVDIMMとACPI
DIMMに刺せる不揮発性メモリ(NVDIMM*1 )はACPIからどのように扱われるかというメモ．
TL;DR
ACPIのNFIT (NVDIMM Firmware Interaface Table)に情報が入っています．
QEMUでのエミュレーション
QEMUのNVDIMMエミュレーションで確認します．
今回は以下のようなオプションで試しました．
-machine pc,nvdimm \
-m 16G,slots=2,maxmem=32G \
-object memory-backend-file,id=mem1,share,mem-path=/home/work/vm/nvdimm-2,size=4G,align=128M \
-device nvdimm,memdev=mem1,id=nv1,label-size=2M \
...
オプションの詳細は上記のQEMUのドキュメントを確認ください． 詳細は確認していませんが，どうもQEMU的には最初hotplug可能なメモリスロットを用意しておいて，そこにNVDIMMのデバイスを接続するという形態を取っているようです．
mem-pathで指定したパスに，指定したサイズだけのファイルが作成されます．
これでLinuxを起動すると，自動でNVDIMMが認識されます．
$ dmesg | grep pmem [ 7.284102] pmem0: detected capacity change from 0 to 4160749568 $ ls /dev/pmem0 /dev/pmem0
ACPIの情報は以下のように確認できます（iaslはubuntuならsudo apt install acpica-toolsで入ります）．
% sudo cp /sys/firmware/acpi/tables/NFIT . % sudo iasl -d NFIT % cat NFIT.dsl /* * Intel ACPI Component Architecture * AML/ASL+ Disassembler version 20180105 (64-bit version) * Copyright (c) 2000 - 2018 Intel Corporation * * Disassembly of NFIT, Tue Apr 2 06:10:17 2019 * * ACPI Data Table [NFIT] * * Format: [HexOffset DecimalOffset ByteLength] FieldName : FieldValue */ [000h 0000 4] Signature : "NFIT" [NVDIMM Firmware Interface Table] [004h 0004 4] Table Length : 000000E0 [008h 0008 1] Revision : 01 [009h 0009 1] Checksum : 40 [00Ah 0010 6] Oem ID : "BOCHS " [010h 0016 8] Oem Table ID : "BXPCNFIT" [018h 0024 4] Oem Revision : 00000001 [01Ch 0028 4] Asl Compiler ID : "BXPC" [020h 0032 4] Asl Compiler Revision : 00000001 [024h 0036 4] Reserved : 00000000 [028h 0040 2] Subtable Type : 0000 [System Physical Address Range] [02Ah 0042 2] Length : 0038 [02Ch 0044 2] Range Index : 0002 [02Eh 0046 2] Flags (decoded below) : 0003 Add/Online Operation Only : 1 Proximity Domain Valid : 1 [030h 0048 4] Reserved : 00000000 [034h 0052 4] Proximity Domain : 00000000 [038h 0056 16] Address Range GUID : 66F0D379-B4F3-4074-AC43-0D3318B78CDB [048h 0072 8] Address Range Base : 0000000440000000 [050h 0080 8] Address Range Length : 00000000F8000000 [058h 0088 8] Memory Map Attribute : 0000000000008008 [060h 0096 2] Subtable Type : 0001 [Memory Range Map] [062h 0098 2] Length : 0030 [064h 0100 4] Device Handle : 00000001 [068h 0104 2] Physical Id : 0000 [06Ah 0106 2] Region Id : 0000 [06Ch 0108 2] Range Index : 0002 [06Eh 0110 2] Control Region Index : 0003 [070h 0112 8] Region Size : 00000000F8000000 [078h 0120 8] Region Offset : 0000000000000000 [080h 0128 8] Address Region Base : 0000000000000000 [088h 0136 2] Interleave Index : 0000 [08Ah 0138 2] Interleave Ways : 0001 [08Ch 0140 2] Flags : 0000 Save to device failed : 0 Restore from device failed : 0 Platform flush failed : 0 Device not armed : 0 Health events observed : 0 Health events enabled : 0 Mapping failed : 0 [08Eh 0142 2] Reserved : 0000 [090h 0144 2] Subtable Type : 0004 [NVDIMM Control Region] [092h 0146 2] Length : 0050 [094h 0148 2] Region Index : 0003 [096h 0150 2] Vendor Id : 8086 [098h 0152 2] Device Id : 0001 [09Ah 0154 2] Revision Id : 0001 [09Ch 0156 2] Subsystem Vendor Id : 0000 [09Eh 0158 2] Subsystem Device Id : 0000 [0A0h 0160 2] Subsystem Revision Id : 0000 [0A2h 0162 1] Valid Fields : 00 [0A3h 0163 1] Manufacturing Location : 00 [0A4h 0164 2] Manufacturing Date : 0000 [0A6h 0166 2] Reserved : 0000 [0A8h 0168 4] Serial Number : 00123456 [0ACh 0172 2] Code : 0301 [0AEh 0174 2] Window Count : 0000 [0B0h 0176 8] Window Size : 0000000000000000 [0B8h 0184 8] Command Offset : 0000000000000000 [0C0h 0192 8] Command Size : 0000000000000000 [0C8h 0200 8] Status Offset : 0000000000000000 [0D0h 0208 8] Status Size : 0000000000000000 [0D8h 0216 2] Flags : 0000 Windows buffered : 0 [0DAh 0218 6] Reserved1 : 000000000000 Raw Table Data: Length 224 (0xE0) 0000: 4E 46 49 54 E0 00 00 00 01 40 42 4F 43 48 53 20 // NFIT.....@BOCHS 0010: 42 58 50 43 4E 46 49 54 01 00 00 00 42 58 50 43 // BXPCNFIT....BXPC 0020: 01 00 00 00 00 00 00 00 00 00 38 00 02 00 03 00 // ..........8..... 0030: 00 00 00 00 00 00 00 00 79 D3 F0 66 F3 B4 74 40 // ........y..f..t@ 0040: AC 43 0D 33 18 B7 8C DB 00 00 00 40 04 00 00 00 // .C.3.......@.... 0050: 00 00 00 F8 00 00 00 00 08 80 00 00 00 00 00 00 // ................ 0060: 01 00 30 00 01 00 00 00 00 00 00 00 02 00 03 00 // ..0............. 0070: 00 00 00 F8 00 00 00 00 00 00 00 00 00 00 00 00 // ................ 0080: 00 00 00 00 00 00 00 00 00 00 01 00 00 00 00 00 // ................ 0090: 04 00 50 00 03 00 86 80 01 00 01 00 00 00 00 00 // ..P............. 00A0: 00 00 00 00 00 00 00 00 56 34 12 00 01 03 00 00 // ........V4...... 00B0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ................ 00C0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ................ 00D0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ................
ちなみに，Proximity DomainがNUMAドメインの情報です．
(補足) SRATとの関連
ACPIのSRAT (System Resource Affinity Table)に，NUMAノードの情報や，メモリの物理アドレス，サイズなどの情報が格納されています．このテーブルはNUMAなマシンでないと存在しないかもしれません．
Linuxでは以下のようにしてSRATのMemory Affinityの情報が確認できます． 先ほどと同じQEMU上のゲストで実行すると以下のようになります．
% sudo cp /sys/firmware/acpi/SRAT . % sudo iasl -d SRAT % cat SRAT.dsl | grep -A13 "Memory Affinity" | grep -B10 -A3 "Enabled : 1" [1B0h 0432 1] Subtable Type : 01 [Memory Affinity] [1B1h 0433 1] Length : 28 [1B2h 0434 4] Proximity Domain : 00000000 [1B6h 0438 2] Reserved1 : 0000 [1B8h 0440 8] Base Address : 0000000000000000 [1C0h 0448 8] Address Length : 00000000000A0000 [1C8h 0456 4] Reserved2 : 00000000 [1CCh 0460 4] Flags (decoded below) : 00000001 Enabled : 1 Hot Pluggable : 0 Non-Volatile : 0 [1D0h 0464 8] Reserved3 : 0000000000000000 [1D8h 0472 1] Subtable Type : 01 [Memory Affinity] [1D9h 0473 1] Length : 28 [1DAh 0474 4] Proximity Domain : 00000000 [1DEh 0478 2] Reserved1 : 0000 [1E0h 0480 8] Base Address : 0000000000100000 [1E8h 0488 8] Address Length : 00000000BFF00000 [1F0h 0496 4] Reserved2 : 00000000 [1F4h 0500 4] Flags (decoded below) : 00000001 Enabled : 1 Hot Pluggable : 0 Non-Volatile : 0 [1F8h 0504 8] Reserved3 : 0000000000000000 [200h 0512 1] Subtable Type : 01 [Memory Affinity] [201h 0513 1] Length : 28 [202h 0514 4] Proximity Domain : 00000000 [206h 0518 2] Reserved1 : 0000 [208h 0520 8] Base Address : 0000000100000000 [210h 0528 8] Address Length : 0000000340000000 [218h 0536 4] Reserved2 : 00000000 [21Ch 0540 4] Flags (decoded below) : 00000001 Enabled : 1 Hot Pluggable : 0 Non-Volatile : 0 [220h 0544 8] Reserved3 : 0000000000000000 [228h 0552 1] Subtable Type : 01 [Memory Affinity] [229h 0553 1] Length : 28 [22Ah 0554 4] Proximity Domain : 00000000 [22Eh 0558 2] Reserved1 : 0000 [230h 0560 8] Base Address : 0000000440000000 [238h 0568 8] Address Length : 0000000440000000 [240h 0576 4] Reserved2 : 00000000 [244h 0580 4] Flags (decoded below) : 00000003 Enabled : 1 Hot Pluggable : 1 Non-Volatile : 0 [248h 0584 8] Reserved3 : 0000000000000000
で，ここのMemory Affinity StructureにNonVolatileというフィールドがあります．
なのでこのフィールドからもNVDIMMかどうか判定できるのでは? という気がしますが，とりあえずQEMUでは上記のようにNonVolatileな領域はありません（一番最後のフィールドがアドレス的にNVDIMMデバイスが追加されるhotplug可能領域だと思います)．
これはQEMUがhotplug可能領域にNVDIMMデバイスを指すという構成を取っているからであり，他のデバイスでは異なるのかもしれません．よく分かりません．
とりえず，NVDIMMの情報を取得するにはNFITを見るのが確実そうです．
(補足) Linuxでのエミュレーション
Linuxはブートオプションでmemmap=16G!16Gなどとすると，LinuxはDRAMのアドレス16Gから始まる16GBの領域をPMEMの領域として管理するようになります（パラメータの詳細はこちら
*2）.
これはACPI的には何も変化しておらず，あくまでLinuxがメモリの一部の領域をNVDIMMとして扱っていることになります．
このことは/sys/firmware/acpi/tables以下にNFITがないことからも分かります．
参考文献
- ACPI Specification (v6.0以降), https://uefi.org/specifications
- Tiffany Kasanicky, Managing Persistent Memory, https://www.snia.org/sites/default/files/SDC/2017/presentations/Solid_State_Stor_NVM_PM_NVDIMM/Kasanicky_Tiffany_Managing_Persistent_Memory.pdf, SNIA SDC'17, 2017.
- hikalium, 自作OSでできる！NVDIMMのつかいかた, https://hikalium.hatenablog.jp/entry/2018/12/17/234735, 2018.
クロスプラットフォームなハイパーバイザ Intel HAXM
HAXM (Hardware Accelerated Execution Manager)はIntelが作成しているハイパーバイザです．もとはAndroid Emulatorのバックエンドとして開発が開始されたもののようです． 以下のような特徴があります．
- KVMのようなインタフェース
- QEMUのサポート
- クロスプラットフォーム
- VT-xのみ
- BSDライセンス
細かい違いは当然ありますが，HAXMはKVMやHypervisor.Frameworkのようなインタフェースを提供します． Windowsではデバイスドライバ，Macではkernel extension, Linuxではカーネルモジュールとして実装されており，それに対してioctlでやりとりすることになります．
HAXMはもともとWindowsとMacがサポート対象でしたが，気づいたら昨年にLinuxのサポートが追加されていたので，今回試してみました．
ドキュメント
HAXMといえばドキュメントが全く無くて一体どうやって使うんだという感じでしたが，Linuxサポート追加と同時期にドキュメントも（少し）追加されて，人間に多少は優しくなりました．
特に，HAXMのAPIに関するドキュメントはここにあります．
Linuxでの利用
インストール
マニュアルに従ってインストール(make && make install)するだけです．簡単．
インストールが完了すると，/dev/HAXというデバイスが作成されています．
Linuxではこのデバイスに対してioctlでやりとりすることになります．
QEMUからの利用
QEMUのHAXMサポートはもともとWindows用に前からありましたが，Linux向けの対応は昨年の11月と比較的最近に入ったので，おそらく自分でQEMUをコンパイルする必要があると思います．
./configure --enable-haxをつけてコンパイルします．
QEMUからHAXMを利用する場合は起動オプションとして-accel haxをつけます (KVMの場合は-accel kvm)．
とりあえず，Ubuntuなゲストは普通に起動しました．
ちなみに，原因は調査していませんが，vcpuを17個以上作成しようとするとsegvしました
(2019-3-23追記: QEMUのソースの中で最大のvCPU数が16個になっていました)．
また，-cpu hostはKVMでないと使用できないようです．
KVMとHAXMの共存（同時実行）はできません．
HAXMを使ってVMを起動すると，以下のようなデバイスが作成されます．
/dev/hax_vm/vm00 /dev/hax_vm00/vcpu0
それぞれVMやvCPUの設定に利用します．
性能比較
KVMとHAXMで簡単なベンチマークを取ってみました． いま手元にNAS Parallel Benchmarks (NPB)の評価スクリプトがあったので，それを利用しました． vcpu数は16，メモリは32GB, KVMはVMCS shadowing及びAPICVや準仮想化機能を有効にしています． ホストのLinuxは5.0, HAXM及びQEMUは現時点のmasterのものを利用しています．
左側のグラフは実行時間のグラフ，右側はKVMを基準とした相対値のグラフ（数字はKVMの実行時間）です．3回実行の中央値をプロットしています． NPBは基本的にOpenMPを利用した数値計算のベンチマークであまりI/Oは関係ないので，今回は単純に計算中に生じたタイマ割り込みなどのVMEXITのハンドリングの速度差が出るのかと思いますが，HAXMの方が20%程度遅いベンチマークが結構あります．
機能・性能的にはやはりKVMの方がいろいろと上のようです． コードを軽くみた感じ，VMCS ShadowingやAPICVなどの機能や，KVMの準仮想化機能のようなものは入っていないように思います． ネステッドのサポートも現時点ではありません．
本当はもっといろんなマイクロベンチマークや，sysbenchなどの結果を比較をして，速度低下の要因が特定できるとよいのですが，まぁそれはまたの機会に．
APIについて
- System IOCTLs
HAX_IOCTL_VERSIONHAX_IOCTL_CAPABILITYHAX_IOCTL_SET_MEMLIMITHAX_IOCTL_CREATE_VM
- VM IOCTLs
HAX_VM_IOCTL_VCPU_CREATEHAX_VM_IOCTL_ALLOC_RAMHAX_VM_IOCTL_ADD_RAMBLOCKHAX_VM_IOCTL_SET_RAMHAX_VM_IOCTL_SET_RAM2HAX_VM_IOCTL_NOTIFY_QEMU_VERSION
- VCPU IOCTLs
HAX_VCPU_IOCTL_SETUP_TUNNELHAX_VCPU_IOCTL_RUNHAX_VCPU_IOCTL_SET_MSRSHAX_VCPU_IOCTL_GET_MSRSHAX_VCPU_IOCTL_SET_FPUHAX_VCPU_IOCTL_GET_FPUHAX_VCPU_SET_REGSHAX_VCPU_GET_REGSHAX_VCPU_IOCTL_INTERRUPT
EPTの細かい設定だったり，VMCALLの追加だったりは直接ソースをいじる必要があるみたいです． コンパイル自体はKVMより楽だと思います．
所感
QEMUが対応していてマルチプラットフォームかつBSDライセンスなハイパーバイザはHAXMだけだと思います． 個人的にはIntel CPUに新しい機能が入った時に，リファレンス実装的な感じでその機能のサポートがHAXMに入るといろんなプロジェクトで参考にできて便利になるなと思いました． 現状は特別機能的なアドバンテージがある訳ではないようですけれども．
IntelといえばIoT向けのARCN hypervisorも作っていて，Intel的にHAXMの優先度がどうなのかはよく分かりませんが，今後も開発続くと良いですね．
KVMの準仮想化機能
KVMにはいくつか準仮想化インタフェースが存在します． KVMはHWによる仮想化支援機構を利用してゲストを実行するので，準仮想化機能を使用しなくても任意のOSが実行できますが，準仮想化機能を利用することでVMのパフォーマンスを向上できる場合があります．以下のような機能があります．
- Paravirtualized clock
- Asynchronous page fault
- Paravirtualized EOI
- Paravirtualized spin lock
- Paravirtualized tlb shootdown
- Paravirtualized send IPI
当然といえば当然ですがLinuxはKVMの準仮想化機能をサポートしているので，KVM上でLinuxを実行する際はこれらの機能が利用可能です．
以下，x86についての話です．Linux v4.20, QEMU v3.10のコードをベースにしています．
KVM準仮想化機能の確認
KVM上のゲストはcpuid命令を利用してKVMの準仮想化機能が利用できるかどうかを調べることができます． 以下がKVMのcpuidに関するドキュメントです．
KVMではcpuidの0x40000000と0x40000001を利用して情報をゲストに伝えます． 本来この領域はcpuid的にはreserved領域です． cpuid 0x40000001のeaxにKVMの準仮想化機能のどれが利用可能化のフラグが格納されています．
cpuidの値はcpuidコマンドを利用して取得できます．(Ubuntuの場合はapt install cpuid)
% cpuid
...
hypervisor_id = "KVMKVMKVM "
hypervisor features (0x40000001/eax):
kvmclock available at MSR 0x11 = true
delays unnecessary for PIO ops = true
mmu_op = false
kvmclock available a MSR 0x4b564d00 = true
async pf enable available by MSR = true
steal clock supported = true
guest EOI optimization enabled = true
stable: no guest per-cpu warps expected = true
...
ただし，このcpuidコマンドはこの記事執筆段階ではKVMのfeatures全てに対応していません．
例えば，上の出力例からはparavirtualized spinlockやparavirtualized TLB shootdown等の有効無効は分かりません．
cpuid -rを実行すると実際のレジスタの値が確認できるのでこれを使用するのが確実です．
% cpuid -r ... 0x40000000 0x00: eax=0x40000001 ebx=0x4b4d564b ecx=0x564b4d56 edx=0x0000004d 0x40000001 0x00: eax=0x01000afb ebx=0x00000000 ecx=0x00000000 edx=0x00000000 ...
また，一部機能はMSRを利用してデータをやりとりします．MSRに関しては以下にドキュメントがあります．
以下でKVMが提供する準仮想化インタフェースについて簡単に説明します．
Paravirtualized clock
- 関連するFeature
KVM_FEATURE_CLOCKSOURCEKVM_FEATURE_CLOCKSOURCE2
カーネルのclocksourceとして準仮想化クロックを提供します．いわゆるkvm-clockです．
kvm-clockはMSRを利用してホストにメモリアドレスを通知し，ホストがそのメモリに必要に応じて時刻を書き込むことで時刻を取得する仕組みです．
利用するMSRのアドレスはKVM_FEATURE_CLOCKSOURCEとKVM_FEATURE_CLOCKSOURCE2で異なりますが，多分KVM_FEATURE_CLOCKSOURCEはdeprecatedです．
clocksourceは以下のように確認できます．
$ cat /sys/devices/system/clocksource/clocksource0/available_clocksource kvm-clock tsc hpet acpi_pm $ cat /sys/devices/system/clocksource/clocksource0/current_clocksource kvm-clock
kvm-clockが利用可能な環境であればkvm-clockが利用されるようになっています．
なお，頻繁にclocksourceにアクセスするような場合はkvm-clockアクセスのオーバヘッドが無視できなくなるようなので，注意が必要です:
- Sven Vermeulen, Comparing performance with sysbench: performance analysis, 2013, http://blog.siphos.be/2013/04/comparing-performance-with-sysbench-part-3/
- Takaaki Fukai, kvm-clock に時間を尋ねるのは間違っているだろうか, 2015, https://www.slideshare.net/DeepTokikane/kernel-vmkvmclock
余裕があればkvm-clockについてはもう少し調べたいと思っています．
Asynchronous page fault
- 関連するFeature
KVM_FEATURE_ASYNC_PF,KVM_FEATURE_ASYNC_PF_VMEXIT
これはゲスト的にはpage faultではないがhost側でpage faultした際，そのpage fault処理中にゲストのvCPUが別の処理を実行することを可能にする機能です．
Asynchronous page fault (APF)に関しては以下が詳しいです．
- Asynchronous page faults, 2010, https://www.linux-kvm.org/images/a/ac/2010-forum-Async-page-faults.pdf
- KVM日記 - Asynchronous page fault解析, 2011, http://d.hatena.ne.jp/kvm/20110702/1309604602
また，KVM_FEATURE_ASYNC_PF_VMEXITという機能がありますが，これはnested virtualization時にL1のKVMに対してL2のAPFを#PF VMEXITとして伝える機能のようです．
Paravirtualized EOI
- 関連するFeature
KVM_FEATURE_PV_EOI
割り込みが発生した際，OSはAPICのEOI (End of Interrupt)レジスタに書き込むことで割り込み処理の完了を通知します． 仮想環境においてはAPICは仮想化されているので，ゲストがEOIにアクセスするとVMEXITが発生します．
PV-EOIはこのVMEXITを削減する機能です．
KVM_FEATURE_PV_EOIが利用可能な場合，特定のMSRにゲストのメモリアドレスを書き込む- ホストは割り込みをゲストに挿入する際，ゲストのEOIレジスタへの書き込みが必要なければMSRが指すメモリの最下位ビットに1をたてる
- ゲストは割り込み時処理時にホストが書き込んだ内容をチェックして，その値が1ならばビットをクリアする．EOIにはアクセスしない
- 必要であればあとでホストがそのフラグを確認して処理をおこなう．（実際のEOI書き込みをおこなうなど）
ちなみにこれはVT-xにあるAPICvとは別の機能です． APICvを利用することでAPICレジスタそのものがHW的に仮想化され多くの場合VMEXITなしでアクセスできるようになります． APICvに関しては以下に参考になります．
- Jun Nakajima, Reviewing Unused and New Features for Interrupt/APIC Virtualization, 2012, https://blog.linuxplumbersconf.org/2011/wp-content/uploads/2012/09/2012-lpc-virt-intel-vt-feat-nakajima.pdf
- Jun Nakajima, Enabling Optimized Interrupt/APIC Virtualization in KVM, 2012, https://www.linux-kvm.org/images/7/70/2012-forum-nakajima_apicv.pdf, 2012
TODO: PV-EOIとAPICvの現在の使われ方の調査
Paravirtualized spin lock
- 関連するFeature
KVM_FEATURE_PV_UNHALT
この機能を利用すると，ゲストのあるvCPUがspinlockを獲得しようとする際，ある一定時間spinしてもlockが獲得できなければ一旦そのvCPUはスリープします．
別のvCPUがlockを解放した際，もしlock待ちでsleepしているvCPUがいたら，そのvCPUをhypercall（KVM_HC_KICK_CPU）で起こします．（実際の動作はもう少し複雑）
これにより，スピン時間を他のvCPUの処理に当てることができる他，Lockを待っているvCPUがうまくスケジューリングされないという問題(Lock Waiter Preemption)も改善できます．
仮想化環境においてスピンロックを以下に効率よくハンドリングするかというのは仮想化における課題の一つで，ここ十年ほど研究が盛んにおこなわれています． VMのspinlockの話はまた別途記事にしようと思います．
Paravirtualized TLB flush
- 関連するFeature
KVM_FEATURE_PV_TLB_FLUSH
- 導入時期
- Linux 4.16 (2017)
x86ではコア間でTLBのコヒーレンシが保たれません． すなわち，あるコアでページテーブルを変更した場合，別のコアからもそのページテーブルを利用する場合はそのコアのTLBを明示的にフラッシュする必要があります． これをTLB shootdownと呼びます．
LinuxではTLB shootdownはIPIを用いておこないます． TLB shootdown IPIを送信したコアは，別のコアからの応答を待ちます． しかしながら，仮想化環境では以下のような問題があります．
- あるvCPUがIPI送信時に実際に動作しているとは限らない
- 結果としてIPIの応答が遅くなる．最悪の場合IPIを送信したvCPUがスケジューリングされてしまい，より遅延が増大する
そこで，Paravirtualized TLB flushは以下のように動作します．
- 現在実行中のvCPUに対してはIPIを送信する
- それ以外のvCPUに対しては次回vCPUがスケジューリングされたときに最初にTLBフラッシュするようにハイパーコールでハイパーバイザに指示する
現在どのvCPUが実行中かどうかはMSR_KVM_STEAL_TIMEから分かります．
以下に開発者による説明があります．
- Wanpeng Li, Torwards a more Scalable KVM Hypervisor, KVM Forum 2018, https://events.linuxfoundation.org/wp-content/uploads/2017/12/Update_Wanpeng-LI_Torwards-a-more-Scalable-KVM-Hypervisor.pdf
もともと仮想化環境でTLB shootdownが性能的に問題になるというのは，いくつかの研究でも報告されていました．
- K.T.Raghavendra, et al., Paravirtualization for Scalable Kernel-Based Virtual Machine (KVM), IEEE CCEM'12, https://ieeexplore.ieee.org/document/6354619
- J.Ouyang, et al., Shoot4U: Using VMM Assists to Optimize TLB Operations on Preempted vCPUs, VEE'16, https://dl.acm.org/citation.cfm?id=2892245
また，2012年には実際にLKMLでもアイディアが提示されています．
2012年の段階で何故入らなかったのか詳しい議論は追っていませんが，コア数の多いサーバの普及が進んだことで最近はこれらの問題がより鮮明になってきているのではないかと思います．
完全な予想ですがクラウド事業者はこの辺りはパッチ当てて運用してたんじゃないかなぁというような気もします．
Paravirtualized IPI
- 関連するFeature
KVM_FEATURE_PV_SEND_IPI
- 導入時期
- Linux 4.19 (2018)
x2APICでIPIを送信する際，ICRというレジスタにアクセスしますが，これはVMEXITが発生します． x2APICでIPIを送信する方法は，physical modeとcluster modeの二種類あり，後者の場合は複数のCPUに一斉にIPIを送ることができます． しかし，実際には前者が主に用いられているようです． この場合，複数のvCPUにIPIを送信する度にVMEXITが発生します．
Paravirtualized IPIでは直接ゲストから逐一IPIを送る代わりに，ハイパーコール（KVM_HC_SEND_IPI）でvCPUに対するIPIをハイパーバイザに依頼します．
これにより一回のVMEXITで複数のvCPUにIPIを送ることができます．
この機能に関しても前述のPV TLB Flushと同じ以下の資料に説明があります．
- Wanpeng Li, Torwards a more Scalable KVM Hypervisor, KVM Forum 2018, https://events.linuxfoundation.org/wp-content/uploads/2017/12/Update_Wanpeng-LI_Torwards-a-more-Scalable-KVM-Hypervisor.pdf
Paravirtualized driver
いわゆるvirtioドライバです．準仮想化というとこのことを思い浮かべる方も多いかもしれません． 複雑な実際のデバイスのエミュレーションをする代わりに，仮想化環境での動作に十分なインタフェースを提供して仮想環境でのI/Oを高速化しようというのが基本的な考えです． また，ホストとゲスト間の共有メモリを利用してデータ転送を効率化することもあります．
以下のようなドライバがあります．
これらのデバイスはvirt-managerのインタフェース等からvirtioドライバを追加して，必要に応じてドライバをインストールすれば使えるようになると思います．
KVMのvirtioデバイスの処理に関してはまた別途書こうと思います．
Linuxでの取り扱い
Linuxはブート時にハイパーバイザ上で動作しているかどうかを確認し，ハイパーバイザ上で動作していた場合はそれに応じた初期化処理を実施します．
ハイパーバイザの検知
arch/x86/kernel/setup.c:setup_arch() => kernel/cpu/hypervisor.c:init_hypervisor_platform()
ここでコールバック関数を利用してハイパーバイザの検知をしますが，KVMの場合はarch/x86/kernel/kvm.cで定義されています． 0x40000000のCPUIDが"KVMKVMKVM"であればKVM上で動作していると判断します．
準仮想化機能の利用
初期化時に，kvm_para_has_feature()を使ってそのfeatureが利用できるか確認し，もし利用できたらそれを使うように設定しています．
例えば，PV tlb flushの設定はkvm_setup_pv_tlb_flush()でおこなわれています．
ブートオプションで特定の準仮想化機能をオフにできるような感じにはなっていないように見えます．
QEMUでの取り扱い
前回説明したように，KVMにおけるcpuid命令はKVM_SET_CPUID ioctlで制御されます．
これを変更することで，ゲストに特定の準仮想化機能を見せないことが可能です．
コードの正確な確認はできていませんが，基本的にQEMUはホストが対応している機能はゲストに見せているような気がします．
QEMUで特定の機能をオフにしたい場合は，-cpu host,-kvm-pv-tlb-flushなどと指定すれば対応するCPUIDのfeature flagがクリアされると思います．
QEMUが利用するオプションについてはこちらで分かります．
またQEMUのオプションで-cpu host,kvm=off (libvirt的には<kvm><hidden state="on"></kvm>)をすると0x40000000のCPUIDはKVMを隠蔽するので，結果としてKVMの準仮想化機能は利用できなくなります．
まとめ
KVMの準仮想化機能について簡単に説明しました． 2018年にはPV TLB ShootdownやPV Send IPIなどが導入されました． 比較的最近の変更なので，現時点で利用するには自分でカーネル（とQEMU）をコンパイルする必要があるかもしれません． 多コアかつ過剰にオーバコミットしている環境で特に効果があると思われます．
