tkokamoの日記

HPCの研究開発なのでそんなことをかきたい

RCU(Read Copy Update)をちゃんと知る（1）-1　ほんとの概要

はじめに

ファイルシステムのrcu-walkを理解するためにRCUの勉強から始めようと思ったので書留ます。
RCUとはざっくりこんなものだ、と分かっている前提での記録です。
予想している流れとしては、

  • 概要（概要）← 今回
  • Linuxでの実装
  • rcu-walk（RCUの応用先）

と考えています。原稿も無いので、次回がいつになるかわかりません（社内勉強会でrcu-walkを語ろうと思っているので完遂はすると思われます）

今回は、wikipediaとかよんでで「？」となった当たりを捕捉。

RCUとは？

図を用いた簡単な理解

複数のタスクで共有するデータの参照/更新をきちんと行う場合、大抵は適切に排他区間をロックによって設けてそれを実現します。
理想的には、タスク間で共有するデータの参照/更新をロックフリーで行えるとよいのですが、一般的にそのようなことを実現する方法は考えられていません。
しかし、特定のデータ構造（※）の参照/更新については、ロックフリーでそれを行うことができます。
RCU（Read Copy Update）とはそのような手法です。

（※）リード・コピー・アップデート - Wikipedia によるとRCUの応用範囲も研究の対象らしいです。


では、RCUはどのようにロックフリーにデータの参照/更新を実現しているのか、ということを知るために以下の図を用いて考えてみます。

f:id:tkokamo:20170816144144p:plain

上図は単方向リストによって構築されているツリー構造を表しています。
（1）ノードAはノードBおよびノードCを指しています。
（2）Cの更新を行いたいタスクは、Cのコピーを作成しそれに対してデータの更新を行います。仮にCを参照中のタスクが他に存在していても、更新を行うタスクはコピー先に対して更新を行うため、参照中のタスクに対して中途半端な状態が見えることがありません。
（3）C'の更新が終わり他のタスクから参照されても問題ない状態になった時、AがもともとCを指していたポインタをC'を指すように更新します。逆に言うと、この時点でCはツリー構造から削除される（※）ことになります。
このため、データを参照するタスクは古いCか新しいC'を参照するのみで、中途半端な状態を参照することは起きません。ポインタから外されたCは参照者が居なくなった時点で解放（※）されます。
（※）リード・コピー・アップデート - Wikipedia には「削除と再利用のフェーズを分ける」とありますが、これは「removal and reclaim」の和訳が適切ではなく「削除と解放（回収）のフェーズを分ける」ということと理解しています。

日本語で詰まったところ

更新前の古いデータCは、Cを参照するタスクが居なくなった時点で解放（reclaim）されます。古いデータを参照するタスクは、新しいデータC'がツリーに追加された後（つまりremoval後）には新規に現れません。（removal後のタスクはC'を参照することになる。）
古いデータの解放タイミングを知るために参照側の把握が必要であり、これがRCUの参照側クリティカルセクションという概念に繋がっているのではないかと考えています。
仮にCを参照するタスクが長いことスリープしたりすると、古いデータがメモリ上にずっと残ってしまうことになります。この期間が長いと、その間にC'が更新されC'‘になり、世代が異るデータがメモリに置かれることとなり容量効率が悪いです。そのため、参照者はスリープやブロックをせず極力参照時間を短く抑える必要があります。
日本語訳で少し不明瞭だった言葉にgrace period（猶予期間）がありますが、これは古いデータCが削除後（AのポインタがC'に更新された後）に回収されるまでの期間を表しています。
参照時間を短くする努力というのは、すなわちgrace periodを短くする努力ということになります。

おわりに

概要ということでかなりざっくりと、主に自分がよくわからんと思ったところを書きとどめました。
次回からLinuxにおける実装を見てみようと思いますが、大体以下の部分を調べていきたいかと思います。

カーネルスタックがvmalloc領域になったことの確認

Linux 4.9からカーネルスタックにvmalloc領域が用いられるようになった。
v3.10系とv4.10系で以下のモジュールをロードしてみて、実際に確認してみた。
ディストリはCentOS7.2

stack_test.c

#include <linux/module.h>
#include <linux/kernel.h>

static int __init stack_test_module_init( void )
{
        int sp; 
        printk( KERN_INFO "int sp is @ %p\n", &sp );
        return 0;
}


static void __exit stack_test_module_exit( void )
{
}

module_init( stack_test_module_init );
module_exit( stack_test_module_exit );

MODULE_DESCRIPTION( "stack_test" );
MODULE_LICENSE( "GPL2" );

Makefile

obj-m := stack_test.o

ROOTDIR  := /usr/src/kernels/`uname -r`/
PWD   := $(shell pwd)

default:
    $(MAKE) -C $(ROOTDIR) M=$(PWD) modules

clean:
    rm -f *.o *.ko

上記コードをmakeして、ロードした結果それぞれ以下のメッセージが/var/log/messagesに出力される。

v3.10系

Mar 30 21:00:24 localhost kernel: int sp is @ ffff88018c22fd4c


v4.10系

Mar 30 20:37:21 localhost kernel: int sp is @ ffffc90003607c7c


x86_64のメモリマップは、LinuxのソースのDocumentation/x86/x86_64/mm.txtによると

Virtual memory map with 4 level page tables:

0000000000000000 - 00007fffffffffff (=47 bits) user space, different per mm
hole caused by [48:63] sign extension
ffff800000000000 - ffff87ffffffffff (=43 bits) guard hole, reserved for hypervisor
ffff880000000000 - ffffc7ffffffffff (=64 TB) direct mapping of all phys. memory ★v3.10系のスタックはここ
ffffc80000000000 - ffffc8ffffffffff (=40 bits) hole
ffffc90000000000 - ffffe8ffffffffff (=45 bits) vmalloc/ioremap space ★v4.10系のスタックはここ
ffffe90000000000 - ffffe9ffffffffff (=40 bits) hole
ffffea0000000000 - ffffeaffffffffff (=40 bits) virtual memory map (1TB)
... unused hole ... 
ffffec0000000000 - fffffc0000000000 (=44 bits) kasan shadow memory (16TB)
... unused hole ... 
ffffff0000000000 - ffffff7fffffffff (=39 bits) %esp fixup stacks
... unused hole ... 
ffffffef00000000 - ffffffff00000000 (=64 GB) EFI region mapping space
... unused hole ... 
ffffffff80000000 - ffffffffa0000000 (=512 MB)  kernel text mapping, from phys 0
ffffffffa0000000 - ffffffffff5fffff (=1526 MB) module mapping space
ffffffffff600000 - ffffffffffdfffff (=8 MB) vsyscalls
ffffffffffe00000 - ffffffffffffffff (=2 MB) unused hole

となり領域が異なることが分かる。

何がうれしいか？

v3.10系のカーネルスタックが置かれていた領域は開始アドレスの違いこそあれ、物理メモリがそのまま連続してマッピングされている。
この領域の良い点の1つは、メモリ割り当て/解放の速度が高速であることである。（仮想アドレスに対応する物理アドレスが予めわかっているため、ページテーブルの設定やTLBのフラッシュが必要ない）
一方で、物理的に連続したメモリを確保出来無い時はメモリ割り当てが失敗してしまうなどの欠点も存在する。

従来のカーネルでは、カーネルスタックとしてこの領域を用いており、各タスクに対し一定（最近は16KiBになったっぽい）のスタックを割り当てていた。
恐らく、カーネルの開発者はカーネルスタックを食い尽くさないように身長にコードを設計する必要があった。
というよりは、必要となるデータ構造のメモリ領域をスラブを用いてプールしておいたり、動的に確保することでスタックを食い尽すことを回避していたのだろう。

一方、v4.10系のカーネルスタックが置かれているvmalloc領域は、物理メモリが非連続的に仮想アドレスにマッピングされている。
非連続的なマッピングであるため、物理連続なメモリを確保できないからと言って、メモリ割り当てが失敗することはない。（基本的には）
しかし、割り当て/解放のたびにページテーブルをいじったりするので、vmalloc領域のメモリ確保/解放は遅い。（頻繁に呼ばれる処理で毎回この領域の獲得/解放を行うのはやめなければならない）
この領域をカーネルスタックに用いた場合、v3.10まで存在したスタックの限界というものが、かなり緩和されることとなる。
カーネル開発者は、スタックの枯渇に神経質になることもなく、また割り込みがネストしてしまいスタックを食い尽すという心配から解放されるようだ。 ※7/1 勘違いでした。

おわりに

思い立って10分ほどで記事を書いたので、大分大雑把な説明になってしまっている。
今後は、v4.9以降スタックオーバーフローが起きたときにどう回復しているのかなど、もう少し見ていきたい。

7/1 追記

Ubuntuではカーネルアドレス空間のレイアウトを少しいじっていることが分かった。 → カーネル空間のASLR的なものっぽい。

CentOS 7.2は上で示したレイアウトどおりっぽい

Jul  1 19:30:19 localhost kernel: vmalloc_start = ffffc90000000000 # VMALLOC_START
Jul  1 19:30:19 localhost kernel: vmalloc_end = ffffe8ffffffffff # VMALLOC_END
Jul  1 19:30:19 localhost kernel: page_offset = ffff880000000000 # PAGE_OFFSET ストレートマップの開始

Ubuntu 17.04は微妙に異なる。

Jul  1 19:27:49 ubuntu kernel: [22205.401374] vmalloc_start = ffffb58cc0000000 # VMALLOC_START
Jul  1 19:27:49 ubuntu kernel: [22205.401375] vmalloc_end = ffffd58cbfffffff # VMALLOC_END
Jul  1 19:27:49 ubuntu kernel: [22205.401376] page_offset = ffff892280000000 # PAGE_OFFSET

### 再起動後、変わっている。
Jul  1 20:08:18 ubuntu kernel: [   45.508327] vmalloc_start = ffffb6a340000000
Jul  1 20:08:18 ubuntu kernel: [   45.508328] vmalloc_end = ffffd6a33fffffff
Jul  1 20:08:18 ubuntu kernel: [   45.508328] page_offset = ffff9cc740000000

カーネルスタックのオーバーフローによる権限昇格とかが問題になることがしばしばあるので、ASLRで防ぐっていうのりですかね。 参考：

Kernel address space layout randomization [LWN.net]

Xen on KVM (1)

KVMの上でXen(HVM)を動かそうとした時になかなか、解決方法がわからなかったので記録しておく。

とは言っても、まだXenの上でDom Uは動かして無いんですが、、、。

Dom 0が動くまでの道のりは以下の通り

動作環境はホストがUbuntu 14.04、ゲストがUbuntu 12.04

  1. Linuxの/etc/modprobe.d/qemu-system-x86.confを編集し、ネステッドEPTを行う設定にする
  2. virt-managerから(あるいはVMのxmlをいじる)、仮想CPUの設定をホストと一緒にする
  3. VMを作り、その上でXenのビルド、インストールを行う。
  4. Xen がエラーを起こして起動しないので、仮想CPUの設定変更
  5. Xenは動いたがDom0のロード中にloop modules loadedでとまるので、virtioを用いないようにするに変更する

これでDom0の起動までは行えた。大変だったのは4, 5に気付くまで、、、。

1. /etc/modprobe.d/qemu-system-x86.confの編集

ハイパーバイザの上までは、通常ハードウェアによる仮想化支援が届かない。これを有効にするために以下のように編集する。

#echo 'options kvm_intel nested=1' > /etc/modprobe.d/qemu-system-x86.conf

qemu-system-x86.confはUbuntuでのファイルでcentOSなどはkvm.confを編集。

2. VMのCPUの設定をホストと一緒にする。

virt-managerを起動し 起動するVMを開き、メニューから[view]>[Details]を選び、ProcessorのConfiguration項目のModelを自分の物理マシンのCPUにし、Copy host CPU configutationをクリックすることで、VMのCPUの設定をホストと同じにできる。

3. Xenのビルドとか

aptで入れても、コンパイルしていれてもおk

4. VMのCPU設定でx2apicをdisableにする

さぁ、起動とおもって動かしたら起動しない。。。色々調べたら、2.でも触れたConfigurationのでx2apicが有効になっていることが問題らしい。x2apicをdisableにすることで解決。
x2apicはNehalemから採用された割り込みコントローラらしい。有効だとなぜ動かなくなるのか謎、、、だがとりあえず解決したので気にしない。

ここまでは調べて出てきた。

5. Dom0のロード中にloop modules loadedでとまる

いつもののりでvirtio、virtio、、、と無意識に設定してたのが落とし穴だった。良く考えたらxenに準仮想化のフロントエンドドライバなんてないの当たり前。ということで、すべてvirtioを用いない設定にすることで解決。
めでたしめでたし



とりあえず、まだ起動してログインができただけの段階なので色々頑張っていきたい。

virtio(vhost)の概要

48-146407
kvmなどの仮想化環境において、ゲストOSのネットワークやディスクI/Oを早くするために、virtioと呼ばれる準仮想化ドライバドライバを用いることがある。
今回は、あまり技術的に細かい部分には突っ込まず、なぜゲストOSのI/Oが遅いのか、なぜvirtioを用いると速くなるのか簡単に整理してみた。

virtio(vhost)の反映の仕方(virt-manager)

virtio-net(vhost-net)の場合

virt-managerを開いてvirtioを反映させたいVMをを開く。VMのコンソールのメニューで[表示]→[詳細]を選択し、NICのデバイスモデルをvirtioにし、適用を押せばよい。この時、すでにVMが起動している場合、一度シャットダウンしてからでないと反映されない。

f:id:tkokamo:20140818193231p:plain

システムのバージョンに依存すると思われるが、virtioを適用していても実際にはvhost-netを用いている可能性がある。これらの違いについては後述するが、確認をしたい場合には、ターミナルから以下のコマンドを実行して

$ ps ax | grep vhost
 4964 ?        Sl     0:04 qemu-system-x86_64 -enable-kvm /*途中省略*/ vhost=on,vhostfd=25 /*省略*/

vhost=onとなっていればvhost-netを使っていることになる。

通常のOSとゲストOSのI/Oの違い

通常のOSにおけるI/OとゲストOSにおけるI/Oの違いを最初に考えてみる。

f:id:tkokamo:20140819010811p:plain

　上の図で、通常のOSでは、アプリケーションがシステムコールを行なうと(①)、カーネルに制御が移る。そして、カーネルが処理を行なった後(③)で、アプリケーションに戻ってくる(④)。
　これと同じ処理を仮想化環境(kvmの場合を考える)で行なおうとすると非常に大変になってくる(上手の右)。まず通常のOSと同様にゲストOS上のアプリケーションが(ゲストOSの)システムコールを行なうと(①)、ゲストカーネルに制御が移る。この時、ネットワークのI/Oの場合であれば、ゲストカーネルがネットワークコントローラのレジスタを書き換えようとする(②)。しかし、ゲストOSが勝手にハードウェアをいじることができてしまうと、勝手にホストのシステムの状態を変えることができてしまうので、危険である。そのため、CPUが例外を発生させ、KVMに制御を移す(③)。KVMでは、ゲストOSのI/Oを処理する時のデバイスのエミュレーションは、qemuによって行なうので、KVMからqemuに対して制御が移る(④)。qemuは、例外の発生の原因に応じてデバイスのエミュレーションを行なうが、このときの⑤～⑧の処理の流れは、通常のOSの場合の処理と概ね同じである。qemuは、デバイスのエミュレーションを行なった後にkvmに制御を戻し(⑨)、kvmはゲストカーネルに処理を戻す(⑩)。最後に、ゲストOSのアプリケーションに戻ってくることで処理が完了する(⑪)。
　kvmでは、仮想化環境を構築するために、CPUによる仮想化支援機構を用いている。ここでは細かく言及しないが、この仮想化支援機構によって、ゲストOSのモード(VMX non root mode)とVMMのモード(VMX root mode)に切り替えながら処理を行なうことで、従来の仮想化支援を用いない場合に比べて、比較的容易に仮想化環境を構築することができる。上図では、ゲストOSとホスト間を行き来している数だけ状態の切り替えが生じている。この状態の切り替えには1000サイクル程度かかる(ハイパーバイザの作り方～ちゃんと理解する仮想化技術～ 第１１回 virtioによる準仮想化デバイス その１「virtioの概要とVirtio PCI」)。実際のネットワークなどのI/Oでは、複数回デバイスのレジスタに書き込みを行なう必要があり、この度に①～⑪までの処理を行なう必要があるので、オーバーヘッドが非常に多い。

virtioとvhost

このオーバーヘッドを削減するために、virtio、そしてvhostという方法が考えられている。
　virtioでは、qemuとゲストOS間で共有メモリを用意し、一定のデータを溜める。そして、実際に処理を行なう時に、VMMに制御を移し処理を行なうことで、VMX non root modeとVMX root modeのモードの遷移数を減らし、オーバーヘッドの削減を実現している。その一方で、virtioでは、デバイスのエミュレーションにqemuを用いている。そのため、実際にデータの処理を行なう場合に、userlandとkernellandで状態の遷移が起きる(上の図では④～⑨)ため、性能の低下を招く懸念がある。
　これに対し、vhostではゲストOSとホストのカーネル間で共有メモリを用いることで、qemuを介さず処理を行なうことで、virtioに比べ更なる実行速度の改善を図っている。

性能比

　実際にどの程度性能が上がるかが
https://www.nic.ad.jp/ja/materials/iw/2012/proceedings/d1/d1-Asama.pdf
に示されている。
　準仮想化ドライバを用いない場合とvirtio-netを用いた場合ではTCPの送信で17～20倍、UDPの送信で9～12倍という高い速度改善が見られる(受信についても、十分に速度が改善している)。
　一方、virtio-netとvhost-netでは概ねvhost-netの方が高いスループットを示しているが、そうでもないものもある。

今後、細かい部分に触れることができればいいなぁ