HYPER ORIGINALITY IIにエンジニアとして参加しました
HYPER ORIGINALITY IIへ技術サイドとして参加しました。
作品としてのコンセプトは下記HPをご参照ください
HYPER ORIGINALITY II
製作物としては、サーバサイドはRubyとNode.js、クライアントサイドはJQueryで構築しました。
一言で言うとリアルタイム画像共有サービスです。PCからもスマホからもアクセス可能です。
PC用IF R.G.B. Intaractive Image Grid
モバイル用IF HOII WEB UPLOADER
PC用のページを展覧会場（新宿眼科画廊）のスクリーンに表示しています。スマホからアップロードされた画像がスクリーン上にリアルタイムに表示され、アップロードされた画像は作品として展示物の一部となります。
新宿眼科画廊
12月11日（水）まで展覧会は開催しておりますので、興味がある方はぜひいらしてください。
Titanium Mobileでscanditモジュールを使う
Titanium MobileでQRコードの読み取りをやってみました。
環境
Titanium Studio 2.1
Android 4.0
scanditにサインインして確認メールのURLからダウンロードページに行きます。
そこからzipファイルをダウンロードできます。
Titanium Mobileでモジュールを有効にするときはプロジェクト直下のディレクトリにzipファイルを配置します。
この状態でビルドすると自動的にzipファイルが展開されてプロジェクトにモジュールがインストールされます。
あとはscanditのホームページにサンプルのコードが載っているのでプロジェクトのapp.jsにコピーします。
さらにtiapp.xmlにscanditのモジュールを追加して、scanditにサインインした時に付与されるIDをサンプルの「--- ENTER YOUR SCANDIT SDK APP KEY HERE --- SIGN UP AT WWW.SCANDIT.COM」って書いてあるところを置き換えればよいです。
しかしこのままだとAndroidの場合QRコードのスキャンができません。AndroidではQRコードの読み取りはデフォルトでOFFになっているので、有効にしないといけないのです。
picker.setQrEnabled(true);
これでQRコードのスキャンができるようになりました。scanditはQRコードらしき物体を画面内から検出してくれてファインダーが移動してくれるので、多少角度がついていても読み取ってくれます。
左上の懐中電灯をタップするとライトをつけることもできます。
しかしながら、stopScanning()を使おうとするとエラーがでてしまいます。
謎です。stopScanning()の実行に成功された方教えてください。APIの例のまま使ってるだけなんですけどね。。
一部動かせなかった部分もあるんですが、スキャン自体の動作は担保できました。バーコードスキャンのライブラリはそもそも絶対数が少ないので、ある程度使えてTitanium用にビルドされたものがあるだけでもラッキーでした。
FUSEで遊んでみました
これは「カーネル/VM Advent Calendar2012」17日目の記事です。
今回はFUSEを使って画像の中にデータを記録していくファイルシステムを作ってみました。
基本的にファイルシステムを作るときはシステムコールの実装になります（これはOS直書きのファイルシステムでもFUSEでも一緒です）。
ただ、FUSEの場合はシステムコールを直接フックするわけではなく、カーネルモジュールとglibcを間に挟んでいます。FUSEのすばらしいところはユーザランドでFSが書けるのところで、豊富なライブラリを遠慮なくリンクできるのです。
しかもRubyやPHP、Pythonなど主要なLLでのバインディングも充実しているのでLLでファイルシステムを書くことができるわけです。RubyやPHPなどのLLを使う場合はさらに言語のエクステンションを間に挟むことになります。
実装はRuby + FUSE + Imlib2です。ソースはgithubにあります。画像の1ピクセル（R・G・B）3バイトにデータを格納する仕組みです。
スクリプトを実行するとデフォルトの設定なら自動でデスクトップにマウントされます。
環境：Linux 2.6.32-5-amd64 [debian squeeze]
./base.rb "マウントポイントのパス" hoge.yml
マウントされたファイルシステムをnautilusで表示させたスクリーンショットです。ディレクトリも作ることができます。
FUSEはオンメモリのファイルシステムなのでアンマウントするとデータが消えてしまいます。なのでYAMLにデータを保存して永続性を担保しています。この辺はfusefsをインストールした段階でサンプルも入っているのでそちらを参考にしました。
nautilusで開くと上のスクリーンショットのような状態になります。nautilusには「画像のデータである」と返しているのでnautilusは画像データと判断してサムネイルを表示しています。
ファイルブラウザで見る限り一見画像に見えますが、実体はテキストなので通常のテキストエディタで開くことができますし、コンパイルすることができます。
上の画像は以下のソースをコンパイルしたものです。透過的な実装というやつです。
#include<stdio.h> int main(int argc, char *argv[]) { puts("笑い男、それがお前の正体か"); return 0; }
今回は縦200×横182ピクセルのサイズの画像を扱っています。
テキストにすると上記のソースは120バイト程の内容なので、そのまま画像に格納すると120 / 3 = 40で、横が182ピクセルなので画像のピクセル上1行の4分の1もいかない程度のデータ量ですがコンパイルすると標準ライブラリをリンクしている都合上、バイナリのサイズが大きくなっている様子が可視化できます。
画像の中にピクセルの中にデータを保存しているのでノイズ（というかデータ）が多く入っています。
ただ現状、拡張子がついているとnautilusは拡張子の辞書を見に行って、辞書に登録された拡張子ならファイルの内容まで見に行かずにアイコンを決定してしまうという課題があります。
なのでtest.cというファイルを作ると画像形式の内容をnautilusに返してもC言語のソースと判断されてアイコンが目的の画像にはならないということです。
ファイルの拡張子というものはあったらあったで不便ですが、無いとそれはそれで不便なものですね。
FUSEは色んな言語のバインディングがリリースされててアイディア勝負でサクッとファイルシステムが作れるので面白かったです。
apache-passengerで動かすsinatra環境のよさげな設定
自宅サーバでsinatraアプリを動かすことにしたので、既存のslimアプリとバッティングしない設定を試した時のメモです。
/var/www/slimにslimアプリがあるとします。slimアプリもsinatraアプリも
http://www.hoge.jp/slim/
http://www.hoge.jp/sinatra/
のようなパスでアプリを起動させるところを目指します。
環境：Linux debian 3.2.0-3-amd64 [debian wheezy]
apacheはすでにインストール済みとします。
・sinatraアプリの開発環境のインストール
#apt-get install ruby rubygems #gem install sinatra
sinatraをapacheで動かすためにpassengerをインストールします。
#gem install passenger
passengerをインストールします。
#passenger-install-apache2-module
足りないものがあればコンソールに表示されるので、追加でインストールします。
・apacheの設定
PassengerRootとPassengerRubyの箇所をmods-enabled/passenger.conに設定します。
<IfModule mod_passenger.c> RackBaseURI /sinatra PassengerRoot /var/lib/gems/1.9.1/gems/passenger-3.0.18 PassengerRuby /usr/bin/ruby1.9.1 </IfModule>
sinatraアプリに必要なファイルを作成します。アプリのファイルはapp.rbにします。今回アプリのファイルは
#cd /var/www/sinatra #mkdir public #mkdir tmp #touch app.rb
sinatraアプリはプロジェク直下のpublicディレクトリをDocumentRootに設定しないといけないのですが、その設定をしてしまうと他のアプリに影響がでることが多々あるかと思います。
sinatra
├── app.rb
├── config.ru
├── log.txt
├── public
└── tmp
そこでpublicディレクトリのシンボリックリンクを/var/wwwに以下に張って対応します。
#cd /var/www #ln -s "リンク先" sinatra
これだけじゃ動かないのでRackBaseURLを設定します。私は上述のmods-enabled/passenger.confに設定しました。
さらにsinatraアプリの直下にconfig.ruを配置します。このファイルはpassengerが自動で読んでくれます。
require './app.rb' run Sinatra::Application
以上でApacheを再起動すれば
http://www.hoge.jp/sinatra
でsinatraアプリにアクセスできます。
ちなみに、リンクさえApacheが読めるところに貼ってやれば、実際のソースファイルの場所はどこでもOKです。
clistを使ってカーネル側とユーザ側で通信させてみました
以前の記事で作成したカーネル側の循環リストライブラリ（clist）を使って、実際にカーネル空間とユーザ空間でデータ通信をしてみました。
LinuxカーネルではftraceやSystemTapなどのトレーサが使えます。両者とも非常にすばらしいツールなのですが、リングバッファを使用しているので
- ある程度長い期間で一連のデータを発生順序を保証してトレースするには不向き
- テキストI/Fなので、二次的な可視化にはパーサが必要
という課題もあるように思います。
ということで、発生順序を保証しつつ長い期間でトレースするためにclistを使い、Excelやその他の可視化ツールで扱いやすいように、バイナリ形式でトレースしたデータを通信する仕組みを考えました。
clistはカーネルツリーに仕込んであって、ビルド済みという前提です（仕込み方はコチラ）。通信にはキャラクタデバイスとシグナルを使うことにしました。
カーネル側では
- カーネルイベントが発生する箇所で循環リストへオブジェクトがpushされる
- ドライバコード内で定期的に循環リストをポーリングして、データが溜まっていたら一時メモリにpullする
- ユーザアプリにシグナルを投げる
ユーザ側では
- ドライバ側にioctl(2)して自分のPID、シグナル番号、その他必要な設定情報を登録する
- カーネルからシグナルが届くとシグナルハンドラ内でドライバからデータをread(2)し、ファイルにwrite(2)する
カーネル側もユーザ側もコード内で冒頭の「イベント固有の設定」の箇所を変更すればそのまま適用可能なコードになっています。
まずはカーネル側のコードです。キャラクタデバイスを作成するのと、システムコールの実装があります。全部だと長いので本質的な部分だけ載せておきます。
環境：Linux debian 3.0.0-amd64 [debian wheezy]
clist_benchmark.c
#include <linux/module.h> #include <linux/kernel.h> #include <linux/timer.h> #include <linux/proc_fs.h> /* alloc_chrdev_region */ #include <linux/sched.h> #include <asm/uaccess.h> /* copy_from_user, copy_to_user */ #include <linux/cdev.h> /* cdev_init */ #include <linux/ioctl.h> /* _IO* */ #include <linux/cpumask.h> /* cpumask_weight() */ #include <linux/clist.h> /* 自作循環リストライブラリ */ #define MODNAME "clist_benchmark" #define MINOR_COUNT 1 enum signal_status{ SIG_READY, SIGRESET_REQUEST, SIGRESET_ACCEPTED, MAX_STATUS }; /* ユーザからデバイス初期化時に送られるデータ構造 */ struct ioc_submit_spec{ int pid; int signo, flush_period; int nr_node, node_nr_composed; int dummy; }; struct signal_spec{ /* ユーザ空間とシグナルで通信するための管理用構造体 */ enum signal_status sr_status; int signo, flush_period; struct siginfo info; struct task_struct *t; struct timer_list flush_timer; }; static char *log_prefix = "module[clist_benchmark]"; static dev_t dev_id; /* デバイス番号 */ static struct cdev c_dev; /* キャラクタデバイス用構造体 */ static struct clist_controller *clist_ctl; static struct signal_spec sigspec; /* プロトタイプ宣言 */ extern int send_sig_info(int sig, struct siginfo *info, struct task_struct *p); static int clbench_open(struct inode *inode, struct file *filp); static int clbench_release(struct inode* inode, struct file* filp); static ssize_t clbench_read(struct file* filp, char* buf, size_t count, loff_t* offset); static long clbench_ioctl(struct file *flip, unsigned int cmd, unsigned long arg); /* システムコールを担当する関数たち */ static struct file_operations clbench_fops = { .owner = THIS_MODULE, .open = clbench_open, .release = clbench_release, .read = clbench_read, .write = NULL, .unlocked_ioctl = clbench_ioctl, /* kernel 2.6.36以降はunlocked_ioctl */ }; /********************************************************** * * イベント固有の設定 * 扱うイベントに合わせて変更が必要な箇所 * **********************************************************/ /* 注意！ ・ユーザ空間とやりとりするオブジェクトはパッディングが発生しない構造にすること ・この構造体のメンバのsizeof()の合計がsizeof(struct object)と一致するようにすること 取得したいイベントにあわせてこの構造体とclbench_add_object()を作成する */ struct object{ unsigned long i_ino; long long ppos; long sec, usec; }; /* balance_tasks()@sched.cで呼び出される関数 ロードバランスが行われている箇所で呼び出される @p ロードバランスされたtask_structのアドレス @src_cpu 最も忙しいCPU番号 @this_cpu ロードバランス先のCPU番号 ※カーネルイベントが補足される箇所にこの関数を挿入する */ void clbench_add_object(unsigned long i_ino, long long ppos) { struct object obj; struct timeval t; if(sigspec.sr_status != SIG_READY){ /* シグナルを送信できる状態かどうか */ return; } do_gettimeofday(&t); obj.i_ino = i_ino; obj.ppos = ppos; obj.sec = (long)t.tv_sec; obj.usec = (long)t.tv_usec; /* この関数はフック先でしか実行されていないので、エラー処理は行っていない */ clist_push_one((void *)&obj, clist_ctl); } EXPORT_SYMBOL(clbench_add_object); /********************************************************** イベント固有の設定ここまで **********************************************************/ （以下省略）
次にユーザ側のコードです。キャラクタデバイスへのioctl(2)とシグナルを受ける設定、シグナルハンドラ内でキャラクタデバイスにread(2)/write(2)しています。こちらは比較的短いので、すべてのコードを載せておきます。
clbench_listener.c
#include <stdio.h> #include <stdlib.h> /* calloc(3) */ #include <unistd.h> /* open(2), sleep(3) */ #include <sys/types.h> #include <signal.h> /* getpid(2) */ #include <fcntl.h> #include <sys/ioctl.h> /********************************************************** * * イベント固有の設定 * 扱うイベントに合わせて変更が必要な箇所 * **********************************************************/ #define DEVICE_FILE "/dev/clbench" #define FLUSH_PERIOD 1500 /* デバイス側でCLISTに対してポーリングする周期（ミリ秒で指定） */ #define CLIST_NR_NODE 10 /* CLISTでのノード数 */ #define CLIST_NODE_NR_COMPOSED 100 /* CLISTで1ノードに含まれるオブジェクト数 */ #define READ_NR_OBJECT 250 /* デバイスファイルに読みにいく際の最大オブジェクト数 */ /* 注意！ ・ユーザ空間とやりとりする構造体はパッディングが発生しない構造にすること ・この構造体のメンバのsizeof()の合計がsizeof(struct object)と一致するようにすること ・この構造体の定義はドライバ側のものと同一であること */ struct object{ unsigned long i_ino; long long ppos; long sec, usec; }; /********************************************************** イベント固有の設定ここまで **********************************************************/ #define IO_MAGIC 'k' #define IOC_USEREND_NOTIFY _IO(IO_MAGIC, 0) /* ユーザアプリ終了時 */ #define IOC_SIGRESET_REQUEST _IO(IO_MAGIC, 1) /* send_sig_argをリセット要求 */ #define IOC_SUBMIT_SPEC _IOW(IO_MAGIC, 2, struct signal_spec *) /* ユーザからのパラメータ設定 */ struct ioc_submit_spec{ int pid; int signo, flush_period; int nr_node, node_nr_composed; int dummy; /* padding防止のための変数 */ }; int dev, out; /* ファイルディスクリプタ */ int count; void *buffer; /* カーネルからのシグナルのハンドラ関数 @sig シグナルハンドラの仕様 */ void clbench_handler(int sig) { ssize_t size; /* カーネルのメモリを読む */ size = read(dev, buffer, sizeof(struct object) * READ_NR_OBJECT); /* ファイルに書き出す */ write(out, buffer, (size_t)size); printf("read(オブジェクト数): %d\n", (int)(size / sizeof(struct object))); count += (int)(size / sizeof(struct object)); lseek(dev, 0, SEEK_SET); } int main(int argc, char *argv[]) { int nr_wcurr, signo, nr_picked, grain; struct sigaction act; struct ioc_submit_spec submit_spec; ssize_t size; dev = open(DEVICE_FILE, O_RDONLY); out = open("./output.clbench", O_CREAT|O_WRONLY|O_TRUNC); buffer = (struct object *)calloc(READ_NR_OBJECT, sizeof(struct object)); /* デバイスの準備 */ submit_spec.pid = (int)getpid(); submit_spec.signo = SIGUSR1; submit_spec.flush_period = FLUSH_PERIOD; submit_spec.nr_node = CLIST_NR_NODE; submit_spec.node_nr_composed = CLIST_NODE_NR_COMPOSED; ioctl(dev, IOC_SUBMIT_SPEC, &submit_spec); /* シグナルハンドリングの準備 */ act.sa_handler = clbench_handler; act.sa_flags = 0; sigemptyset(&act.sa_mask); sigaction(SIGUSR1, &act, NULL); /* SIGTERMをブロックするための設定 */ sigaddset(&act.sa_mask, SIGTERM); sigprocmask(SIG_BLOCK, &act.sa_mask, NULL); /* シグナルが届くまでmainスレッドは無限ループ */ while(1){ if(sigwait(&act.sa_mask, &signo) == 0){ /* シグナルが受信できたら */ if(signo == SIGTERM){ puts("main:SIGTERM recept"); break; } } } /*** *** *** シグナルを受信するとここに到達する *** *** ***/ /* カーネル側に終了通知を送る */ ioctl(dev, IOC_USEREND_NOTIFY, &nr_wcurr); printf("wcurr_len:%d\n", nr_wcurr); /* clist_pull_end()でpull残しがないように大きい方でメモリを確保 */ if(nr_wcurr >= READ_NR_OBJECT){ /* 一端freeして、再度calloc */ free(buffer); buffer = calloc(nr_wcurr, sizeof(struct object)); grain = nr_wcurr; } else{ /* bufferをそのまま使うのでcalloc無し */ grain = READ_NR_OBJECT; } /* grainだけひたすら読んでread(2)が0を返したらbreakする */ while(1){ /* カーネルのメモリを読む */ size = read(dev, buffer, sizeof(struct object) * grain); if(size == 0){ /* ここを通るということはclist_benchmark側がSIGRESET_ACCEPTEDになったということ */ break; } /* ファイルに書き出す */ write(out, buffer, (size_t)size); printf("read(オブジェクト数): %d\n", (int)(size / sizeof(struct object))); count += (int)(size / sizeof(struct object)); lseek(dev, 0, SEEK_SET); } putchar('\n'); /* ベンチマーク結果を出力 */ puts("------------ベンチマーク結果---------------"); printf("入出力オブジェクト総数：%d\n", count); printf("読み込み粒度（オブジェクト数）：%d\n", READ_NR_OBJECT); printf("clistのノード数：%d\n", 10); printf("clistのノードに含まれるオブジェクト数：%d\n", 100); /* リソース解放 */ free(buffer); close(out); close(dev); }
clist_benchmark.cのclbench_add_object()を実装してイベントを取得可能な箇所へフックをかけるのですが、今回はページキャッシュのミスを計測することにしました。フックはdo_generic_file_read()にかけました。ページキャッシュミスについては以前の記事にあります。
mm/filemap.c
■追加ここから■ #ifdef CONFIG_CLBENCH extern void clbench_add_object(unsigned long i_ino, long long ppos); #endif ■追加ここまで■ static void do_generic_file_read(struct file *filp, loff_t *ppos, read_descriptor_t *desc, read_actor_t actor) { struct address_space *mapping = filp->f_mapping; struct inode *inode = mapping->host; struct file_ra_state *ra = &filp->f_ra; pgoff_t index; pgoff_t last_index; pgoff_t prev_index; unsigned long offset; /* offset into pagecache page */ unsigned int prev_offset; int error; index = *ppos >> PAGE_CACHE_SHIFT; prev_index = ra->prev_pos >> PAGE_CACHE_SHIFT; prev_offset = ra->prev_pos & (PAGE_CACHE_SIZE-1); last_index = (*ppos + desc->count + PAGE_CACHE_SIZE-1) >> PAGE_CACHE_SHIFT; offset = *ppos & ~PAGE_CACHE_MASK; for (;;) { struct page *page; pgoff_t end_index; loff_t isize; unsigned long nr, ret; cond_resched(); find_page: page = find_get_page(mapping, index); if (!page) { page_cache_sync_readahead(mapping, ra, filp, index, last_index - index); page = find_get_page(mapping, index); if (unlikely(page == NULL)){ ■追加ここから■ #ifdef CONFIG_CLBENCH clbench_add_object(inode->i_ino, *ppos); #endif ■追加ここまで■ goto no_cached_page; } }
ここまでやってカーネルをビルド＆起動します。起動したらmknode(1)でデバイスファイルを作成しclbench_listenerを起動するとイベントの計測が開始されます。
イベント計測を終了したい時にclbench_listenerにSIGTERMシグナルを送ります。そうするとclist内に残っているオブジェクトを読みきって、終了します。左がclbench_listenerの画面で右がカーネルログです。
clbench_listenerが正常に終了するとオブジェクト列が書き出されたファイルが作成されます。今回の場合output.clbenchという名前です。
イベント計測中に動かすプログラムについてやoutput.clbenchの解析は別エントリで書こうと思います。一応今回はなんとか動くものを作りました、ということで。
xconfigとgconfigを使ってみました
GUIベースのカーネル設定ツール(ようは.configに書いてあるカーネルコンポーネントのn/m/yを切り替えるGUIフロントエンド)を使ってみたのでそのことについてのメモです。
この記事を9割くらい書き終わった段階でid:meechさんの記事*1を見つけてしまいました。二番煎じですが、気にせず書きます。いいですよね。ソフトウェアのバージョンもあがってますし。
今まではカーネルビルドの際は.configファイルを直接手で編集してました。しかし、その方法だと複数の自作ドライバを組み込んだカーネルをデバッグする際に結構記述（漏れ|ミス）が発生します。
ということでGUIベースの設定ツールを探すとxconfigとgconfigという2つのツールがあることが分かりました。さっそくセットアップして使ってみます。makeはカーネルツリーのトップで実行します。
環境：Linux debian 3.0.0-1-amd64 [debian wheezy]
まずxconfigの方はGUIライブラリがQTなので開発用ライブラリをインストールします。qt4だと今回の環境ではダメでした。
#apt-get install qt3-dev
$make xconfig
xconfigの方は3つのペインでできていて、左側のペインからドライバを探して選択すると右上のペインに展開した結果が表示されます。その中から項目を選択すると右下のペインに詳細が表示されます。
項目の横にはチェックボックスがあり、クリックするごとに変わります。「 」がn、「●」がm、「レ点」がyを意味しています。
必要なだけ変更したらEdit->Saveをクリックすれば変更が反映されたconfigファイルが出力されます。
次はgconfigです。こちらはgtkベースでさらにフレームワークでgladeを使ってあるので必要なパッケージをインストールします。gconfigの方がインストールするパッケージは多いです。すでにインストール済みの方は別ですが・・・
#apt-get install gtk+-2.0 glib-2.0 libglade2-dev
$make gconfig
gconfigは2つのペインからできており、上側のペインで項目を選択すると下側のペインに詳細が表示されます。
xconfig同様、項目の左側にチェックボックスがあり、n/m/yを切り替えることができます。チェックボックスをダブルクリックするか、Valueの値をシングルクリックることで切り替えることができます。「 」がn、「ー」がm、「レ点」がyを意味しています。
こちらも必要なだけ変更したらFile->Saveでconfigファイルを出力しておきましょう。
ちなみにxconfigもgconfigも項目名はKconfigのtristateから、詳細はhelpから読み取っているようです。例えば上のIntelのGM500ドライバの例でいくと以下のKconfigから詳細情報を読み取ることになります。
drivers/gpu/stub/Kconfig
config STUB_POULSBO tristate "Intel GMA500 Stub Driver" depends on PCI depends on NET # for THERMAL # Poulsbo stub depends on ACPI_VIDEO when ACPI is enabled # but for select to work, need to select ACPI_VIDEO's dependencies, ick select BACKLIGHT_CLASS_DEVICE if ACPI select VIDEO_OUTPUT_CONTROL if ACPI select INPUT if ACPI select ACPI_VIDEO if ACPI select THERMAL if ACPI help Choose this option if you have a system that has Intel GMA500 (Poulsbo) integrated graphics. If M is selected, the module will be called Poulsbo. This driver is a stub driver for Poulsbo that will call poulsbo.ko to enable the acpi backlight control sysfs entry file because there have no poulsbo native driver can support intel opregion.
※まとめ
「GUIの完成度の高さ、操作が直感的にできるかどうか」としてはgconfigの方が上かなあと思いました。
＃僕がGNOMEユーザだということもあるかもしれませんが
ただ、xconfigがEdit->Findでキーワード検索ができる点は機能的に勝っているかなと思います。
*1:「make *config 〜カーネルいじっちゃお!〜Add Star」http://d.hatena.ne.jp/meech/20101212/1292165676
ページキャッシュのミスはどこで起きているのか
あけましておめでとうございます。これは「カーネル/VM Advent Calendar2011」35日目の記事です。そして2012年一発目の記事になります。
この記事ではページキャッシュミスについて書きます。ページキャッシュとDB（主にtmpfsと絡めたお話）についてはid:naoyaさんの記事*1が有名かと思います。
ディスクIOは遅いので、メモリ上にデータをキャッシュしている。それがページキャッシュである。読みたいファイルのデータがページキャッシュ上にあればディスクまで読みにいかずページキャッシュから読んで返す、これで高速化できる。
ページキャッシュは基数ツリー（radix tree）というデータ構造で管理されていて、エントリはページ単位（4096バイト）である。
だと言うことは知識として得ています。ただ「ページキャッシュ機構が透過的に働く」という表現が抽象的で書籍やWebの説明ではよく分からないわけです。なんとなくモヤッとした理解でとどまってしまいます。
ということで、ユーザアプリでread(2)が発行された際にページキャッシュミスが発生するロジックがLinuxカーネルのソースでどうなっているか、若干深めに追ってみたいと思います。
システムコールを担当する関数達は以下のようになっています。ファイルシステムはext4でカーネルソースのバージョンは3.0です。read(2)が発行されるとdo_sync_read()が呼ばれることを示しています。
const struct file_operations ext4_file_operations = { .llseek = ext4_llseek, .read = do_sync_read, .write = do_sync_write, .aio_read = generic_file_aio_read, .aio_write = ext4_file_write, .unlocked_ioctl = ext4_ioctl, （以下省略）
do_sync_read()はfs/read_write.cにあります。
ssize_t do_sync_read(struct file *filp, char __user *buf, size_t len, loff_t *ppos) { struct iovec iov = { .iov_base = buf, .iov_len = len }; struct kiocb kiocb; ssize_t ret; init_sync_kiocb(&kiocb, filp); kiocb.ki_pos = *ppos; kiocb.ki_left = len; kiocb.ki_nbytes = len; for (;;) { ret = filp->f_op->aio_read(&kiocb, &iov, 1, kiocb.ki_pos); if (ret != -EIOCBRETRY) break; wait_on_retry_sync_kiocb(&kiocb); } if (-EIOCBQUEUED == ret) ret = wait_on_sync_kiocb(&kiocb); *ppos = kiocb.ki_pos; return ret; }
for文の中でaio_read()を呼んでいます。これはまさしく、上のfile_operations構造体でいう所のgeneric_file_aio_read()のことです。ということでread(2)が発行されるとdo_read_sync()経由でgeneric_file_aio_read()が呼ばれることになります。
generic_file_aio_read()はmm/filemap.cにあります。
ssize_t generic_file_aio_read(struct kiocb *iocb, const struct iovec *iov, unsigned long nr_segs, loff_t pos) { struct file *filp = iocb->ki_filp; ssize_t retval; unsigned long seg = 0; size_t count; loff_t *ppos = &iocb->ki_pos; struct blk_plug plug; count = 0; retval = generic_segment_checks(iov, &nr_segs, &count, VERIFY_WRITE); if (retval) return retval; blk_start_plug(&plug); /* coalesce the iovecs and go direct-to-BIO for O_DIRECT */ if (filp->f_flags & O_DIRECT) { （省略） } count = retval; for (seg = 0; seg < nr_segs; seg++) { read_descriptor_t desc; loff_t offset = 0; /* * If we did a short DIO read we need to skip the section of the * iov that we've already read data into. */ if (count) { if (count > iov[seg].iov_len) { count -= iov[seg].iov_len; continue; } offset = count; count = 0; } desc.written = 0; desc.arg.buf = iov[seg].iov_base + offset; desc.count = iov[seg].iov_len - offset; if (desc.count == 0) continue; desc.error = 0; do_generic_file_read(filp, ppos, &desc, file_read_actor); retval += desc.written; if (desc.error) { retval = retval ?: desc.error; break; } if (desc.count > 0) break; } out: blk_finish_plug(&plug); return retval; }
2番目にでてくるif文ですが、O_DIRECTとはOSのページキャッシュに頼らず自前でキャッシュを持つ構造をしているRDBなどのシステムが使うopen(2)のオプションなので、今回は無視します。これはカーネル2.4以降で実装されたものらしいです。
generic_file_aio_read()はext4だけではなくext3やbtrfs、fuseでもfile_operations構造体*2に含まれています。
ブロックデバイス上のファイルに対してread(2)を発行する時はファイルシステムの種類に関わらずページキャッシュにファイルデータが存在するか確認しにいっていて、その部分のコードは統一されているということですね。
続いてfor文に移りますが、この中でdo_generic_file_read()が呼ばれています。これは同じくmm/filemap.cにある関数です。
static void do_generic_file_read(struct file *filp, loff_t *ppos, read_descriptor_t *desc, read_actor_t actor) { struct address_space *mapping = filp->f_mapping; struct inode *inode = mapping->host; struct file_ra_state *ra = &filp->f_ra; pgoff_t index; pgoff_t last_index; pgoff_t prev_index; unsigned long offset; /* offset into pagecache page */ unsigned int prev_offset; int error; index = *ppos >> PAGE_CACHE_SHIFT; prev_index = ra->prev_pos >> PAGE_CACHE_SHIFT; prev_offset = ra->prev_pos & (PAGE_CACHE_SIZE-1); last_index = (*ppos + desc->count + PAGE_CACHE_SIZE-1) >> PAGE_CACHE_SHIFT; offset = *ppos & ~PAGE_CACHE_MASK; for (;;) { struct page *page; pgoff_t end_index; loff_t isize; unsigned long nr, ret; cond_resched(); find_page: page = find_get_page(mapping, index); if (!page) { page_cache_sync_readahead(mapping, ra, filp, index, last_index - index); page = find_get_page(mapping, index); if (unlikely(page == NULL)) goto no_cached_page; } （以下省略）
ありました。for文の中でfind_get_page()を呼び出していて、pageがNULLならページキャッシュにミスヒットしたというロジックになっています。
find_get_page()もやはりmm/filemap.cにあります。
struct page *find_get_page(struct address_space *mapping, pgoff_t offset) { void **pagep; struct page *page; rcu_read_lock(); repeat: page = NULL; pagep = radix_tree_lookup_slot(&mapping->page_tree, offset); if (pagep) { page = radix_tree_deref_slot(pagep); if (unlikely(!page)) goto out; if (radix_tree_deref_retry(page)) goto repeat; if (!page_cache_get_speculative(page)) goto repeat; /* * Has the page moved? * This is part of the lockless pagecache protocol. See * include/linux/pagemap.h for details. */ if (unlikely(page != *pagep)) { page_cache_release(page); goto repeat; } } out: rcu_read_unlock(); return page; }
基数ツリーのライブラリ関数を呼び出して該当のファイルのデータがキャッシュにあるか検索しています。ちなみに基数ツリーを扱うライブラリはlib/radix-tree.cにありました。
address_space構造体のpage_treeに基数ツリーの構造が格納されているようです。address_space構造体の定義を見てみます。
include/linux/fs.h
struct address_space { struct inode *host; /* owner: inode, block_device */ struct radix_tree_root page_tree; /* radix tree of all pages */ spinlock_t tree_lock; /* and lock protecting it */ unsigned int i_mmap_writable;/* count VM_SHARED mappings */ struct prio_tree_root i_mmap; /* tree of private and shared mappings */ struct list_head i_mmap_nonlinear;/*list VM_NONLINEAR mappings */ struct mutex i_mmap_mutex; /* protect tree, count, list */ /* Protected by tree_lock together with the radix tree */ unsigned long nrpages; /* number of total pages */ pgoff_t writeback_index;/* writeback starts here */ const struct address_space_operations *a_ops; /* methods */ unsigned long flags; /* error bits/gfp mask */ struct backing_dev_info *backing_dev_info; /* device readahead, etc */ spinlock_t private_lock; /* for use by the address_space */ struct list_head private_list; /* ditto */ struct address_space *assoc_mapping; /* ditto */ } __attribute__((aligned(sizeof(long))));
inode構造体のポインタが格納されています。ページキャッシュはブロックデバイスにおけるinodeごとに存在するということですね。
※まとめ
- ページキャッシュはページ単位でファイルの内容が基数ツリーで管理されている
- ブロックデバイスのinode1つに対して基数ツリーが1つ存在する
- ページキャッシュミスはdo_generic_file_read()で起きている
- ブロックデバイスを扱うファイルシステムは多くの場合（少なくともread(2)時に）ページキャッシュを走査する実装になっている（これが「透過的に働く」の意味）
しかし、このdo_generic_file_read()はPageReadAheadやPageUptoDateなど気になるワードが満載で、もっと読みこんでいきたいところです。
