![[logo]](/images/suz.gif)
いまどきのファイルシステムに求められるもの いまどきのファイルシステムに求められるものいまよく使われている ファイルシステムの多くは古い歴史をもっている。 bsd 系の ffs なんかは どれぐらい古いか よくわからないが 20 年ぐらいは 前に設計されたものじゃないかと思う。
linux でよくつかわれている ext2fs は出来てから 10年弱だけれども 設計自体が新しいわけではないはずだし、 今の Disk の 性能バランスにあっているかどうか というと 疑問がある。
Disk の spec を考えると、10年ちょっと前 -- 100MB - 300MB ぐらいのレンジの ものを使っていた ころから 3桁ぐらい容量が上がっている。
Disk の 性能はというと... I/O の スループットは、せいぜい 1MB/sec 程度だった のが 30 倍ぐらい あがって 30MB/sec ぐらいにはなっていると思う。 データは 2次元に配置されるから、sqrt(1000) の 30 倍ぐらいというのは、 妥当だと思う。
ただし、アクセスタイムは 回転数に依存するから、2倍程度しか性能は上がって いない。7200 rpm の Disk でランダムアクセスすると 8ms ぐらい。 大昔でも 3600 rpm ぐらいだったから、たぶん 2 倍。
要するに 同じ容量に対する データアクセスのスループットは、1/30 ぐらい にまで落ちていて、アクセスタイムでは 1/500 ぐらい落ちているわけだ。
実際 FSCK の時間が、がまんできないぐらい遅くなっている。 メタデータの安全性というメインの機能よりも、FSCK いらず という面の 方が 重要だと思える。
容量に対する 性能バランスが大幅に変わってきたから、 こういう機能が必要になってきたわけだが... それ以外の点で 古い設計の ファイルシステムに破綻は生じていないんだろうか？ というのが 本題。
昔と同じ使い方で、容量に比例した規模 というのを想定すれば 破綻しているの は明らかだから、 どのように 使うから どういう性質が必要か という話をしていかないと いけない。
私は、ビデオのキャプチャーをしないけども、 他の人と話していると、こういうことが当り前にできないと いけなさそうだ。
ビデオの スループットは、8MB/sec 程度だと考えると、スループット的には 足りていて、たとえば、キャプチャーしながら 他のものを見て さらに 他のアプリケーションを開くなんてことは可能だと思える。
アクセスタイムは どうなんだろうか？
それは当然としても
簡単な例をあげると...
ビデオのキャプチャー
========= ==========
他のビデオの 再生
--------- ----------
2 つのデータを アクセスしているとする。たぶん 交互にアクセスすることに なるから、その間でシークが発生する。秒間 100 回のシークしか許容できない とすれば、最低でも
の I/O サイズである必要がある。
こんなに単純な使いかたではなく、他でやっていることは、一般に データサイズが 小さく アクセス頻度が 非常に高いと仮定すれば、動画の I/O に許される I/O 頻度をもっと小さくしなければならない。 秒間 4回ぐらいに押えるとすれば...
この値がなにを意味するか...
上位層のアプリケーションでは
たぶん もっと大きなバッファを用意するし、メモリ管理でも 十分な量の
バッファを確保できているのは当然として、
さらに 連続した領域を順に書き出すというのも当然としよう。
それだけではダメで、分断することなく2MB 程度まで一気に書ききる 。
そういう仕組みが必要になる ということ。
1 ページ 4K とすれば、最低でも 512 個のページを まとめて I/O できるように なっていないといけない ということだから、なかなか難しいのではないか...
1 つのデータを書こうとするときに、連続した データも 強制的に書き出す... そういう 仕組みが メモリ管理のところに 必要だと思う。
ちなみに どれぐらいの メモリが必要か ... 30 秒間の間に データを 書き出すとすれば、8MB/sec で データ が作られるから、240MB のメモリが あれば良い。このこと自体は、昨今のメモリの値段を考えると問題ではないと 思う。
問題は、240MB も溜ってしまうような ことが 起きる原因。 他のことの、アクセス頻度 が Disk の 能力より高く、 Disk に書き出せない --- そういう状況がもっとも 有り得そうである。
そういう状況になると システムが 遅くなって、結局 は、メモリ と Disk の性能 がバランスするようになるはずだが ... キャプチャーのアプリケーションが 止まるのは困る。
これを防ぐような仕組みを考えると .... ある状況 Disk の I/O 頻度が 飽和しそうになったら、意図的に I/O の 性能を遅くして、 アプリケーションを止めておく そういう コードが必要だと思える。 システムが飽和してしまえば、同じことになるから、こういうコードを いれても いままでより遅くなるわけではない。
read/write システムコールを使っているアプリケーションなら、 なんとか これをやる方法はあるんじゃないかと思う。
小さな沢山のファイルを 全部アクセスする --- そういうことは時々やる。 キャッシュに載ってしまえば 普通は とても速く、キャッシュに載っていない ときは とても遅い。
ちょっと実験。linux で ファイルシステムは、ext2fs というシステムで、 linux カーネルを 2 つのディレクトリに展開する。 その二つのディレクトリに対して diff -ruN をやってみる。
展開したばかりだと 1.445 秒で終った。ところが 一旦 umount して から計ると 107.961 秒もかかった。
2 ケタも違うわけである。/proc/stat で、disk I/O を見てみると 271716 Kバイトを 読み込むのに 33325 回の I/O をしていた。 平均 I/O サイズは、8.15 K バイト。1 回の I/O に 3.239 ms かかっていて、 I/O 性能は、2.516 MB/sec 。
この disk に対して
time dd if=/dev/sdxx of=/dev/null bs=1k count=271716
なんてやると 5.953 秒で終り、45.643 MB/sec も出ている。
I/O 頻度が ボトルネックになって、DISK の スループットの 5.59 % しか 利用できていない。
上の使いかたは、本当にはランダムアクセスではないはず。 うまく I/O を制御できれば、20 倍は無理としても 10倍速くできる可能性が ある。
はじめの方で 昔とは データの量に対して、アクセス性能が 1/500、 スループットが 1/30 だと書いた。このバランスなら、スループットに 対する アクセス性能が16.6 倍 になるわけだから、 スループットと I/O 回数の性能比がバランスしているわけだ。 ファイルシステムの設計が古いと思ったのは、このことが理由。
どうしたら良いのか ...例えば linux では、disk に対して pre-read をかけている。この量は、IDE なら 4K SCSI なら 60K になっている。
すべてのファイルを 順にアクセスするといった ことをすれば、これは 十分 有効で、grep なら すべてをアクセスしても 16.137 秒で read できる 当然 キャッシュにのっていれば すごく速く 1.876 秒。
ところが、上記のように 2 つの 物理的に連続した ファイル群を 交互にアクセスするといったことをやると 107 秒になってしまうわけだ。
DISK ドライバレベルでなんとかするのではなく、VM か ファイル システムレベルで、物理的に近いもの を 先読みする といった 改良を行えば 107 秒が 16秒 ぐらいにはなりそうで、うまくやることができれば 7秒ぐらい までにできそうだ。
ただし、なんでもかんでも pre-read を大きくすれば良いというものではない。 本当に不連続な アクセスパターンの場合は、キャッシュの 効率が 十数分の1に落ちてしまう。
さて、有野さんの日記に
コードの読み方 で、
・ 本当に深く干渉している、 ・ より複雑な、 ・ 設計で回避可能でない、 ・ 関係が多対多である ・ 手続き的でない
ようなコードをどう読むか という話題があったので、
というテーマで どのように読んだかを例題にして説明してみる。
ある程度 上記にマッチしているような気がするけども、 これを例題に選んだのは、私が はっきりしたテーマがなければ コードを積極的に 読む気がしないから。
読もうとするテーマを 詳しく書くと、
こういうところが linux ではどう実装されているかということ。
この作業 は、メモを取りながら 読んだので、1 時間ぐらいかかった。 普段はメモを取らないので、20 分ぐらいでできると思う。 集中力があがってきたら 10 分程度かも知れない。
とりあえず、メモリ管理の部分の mm から write を grep してみる。
たくさん出て来るが、write_lock とかが目立つので それを抜いてみる。
grep write *.c | grep -v lock |less
これで 100行ぐらいにまで減るので、ながめてみると
int (*writepage)(struct page *) = mapping->a_ops->writepage;
というのが見付かる。page を管理する構造体には、それをどうやって書くか についての メソッドがくっついているようだ。
writepage というのがキーワードらしいので、それと readpage を grep してみる。
みつかるのは、filemap.c と vmscan.c だけ。これらを読めばよそさそうだ。
とりあえず、readpage はおいておいて... writepage だけ追っかけると writepage を 使っている関数をみてみる。
filemap.c: filemap_fdatasync()
filemap.c: generic_file_mmap()
vmscan.c: shrink_cache()
このなかで、shrink_cache() のみが関係ありそう。
この関数は、170 行ぐらいだが
while (max_scan && (entry = inactive_list.prev) != &inactive_list) {
page = list_entry(entry, struct page, lru);
if ((PageDirty(page) || DelallocPage(page)) && ... ) {
(page->mapping->a_ops->writepage)(page);
}
という構造が読み取れる。
1 ページ 1 ページ書いているとしか思えないが...
ここまで読んで、fs のところが flush する コードのメインだと気が付いた。
fs に移動して、writepage を grep してみる。 お、あった
buffer.c: ret = page->mapping->a_ops->writepage(page);
さて writepage を読んでいる関数構造をみていくと
_write_buffer(struct buffer_head *bh, int wait) {
if (buffer_delay(bh)) {
ret = page->mapping->a_ops->writepage(page);
}
}
write_buffer(struct buffer_head *bh, int wait)
{
if (!buffer_delay(bh)) {
ll_rw_block(WRITE, 1, &bh);
return 1;
} else
return _write_buffer(bh, wait);
}
_write_buffer もしくは write_buffer を 呼んでいるところを見てみる。
write_some_buffers fsync_inode_buffers sync_page_buffers
の 3つが見付かる。
とりあえず、簡単そうなものから みてみると
next = lru_list[BUF_DIRTY];
while (next && --nr >= 0) {
if (atomic_set_buffer_clean(bh)) {
write_locked_buffers(array, count);
}
}
という構造で、dirty 専用の LRU リストをなめ diry なページを書き出す。
さて、write_some_buffers が求めるもの みたいであるが ... 書き出す関数は、write_locked_buffers() であって、write_buffer では なかった。
ここで、下位構造である write_locked_buffers() と 上位構造がどうなっているかも見てみることにする。
write_locked_buffers(...)
{
do {
struct buffer_head * bh = *array++;
bh->b_end_io = end_buffer_io_sync;
submit_bh(WRITE, bh);
} while (--count);
}
ここで、buffer_head の配列を 全部 submit_bh で書き出すようだということが わかった。
submit_bh と make_generic_request という関数が、ブロックデバイスに 対して I/O 要求を出す手続きだという予備知識があったので、これ以下は 読む必要はなかった。
さて上位構造
下から 追っていくと 2つの流れがみつかる。
ひとつは、
static void write_unlocked_buffers(kdev_t dev)
{
do {
spin_lock(&lru_list_lock);
} while (write_some_buffers(dev));
run_task_queue(&tq_disk);
}
void balance_dirty(void)
{
spin_lock(&lru_list_lock);
write_some_buffers(NODEV);
}
static void free_more_memory(void)
{
balance_dirty();
wakeup_bdflush();
current->policy |= SCHED_YIELD;
__set_current_state(TASK_RUNNING);
schedule();
}
一応 理解を書くと、 メモリが足りなくなったら、dirty な キャッシュをバランスを取って書き出そう とする という感じか。
もうひとつは、
sync_old_buffers()
{
for (;;) {
struct buffer_head *bh;
spin_lock(&lru_list_lock);
bh = lru_list[BUF_DIRTY];
if (!bh || time_before(jiffies, bh->b_flushtime))
break;
if (write_some_buffers(NODEV))
continue;
return 0;
}
}
kupdate() {
for (;;) {
schedule_timeout(interval);
:
sync_old_buffers
}
}
という流れ、
kupdated という名前の デーモン(kernel_thread) があって、 定期的 (デフォルト 5秒) に 1 回 sync_old_buffers を呼び その中で write_some_buffers を呼び出す。
これで、上のテーマ どこでどういう風にということは終り。
Q1. struct buffer_head に相当する構造体は? (25点)
Q2. atomic_set_buffer_clean(bh) に相当する処理は? (25点)
Q3. lru_list[BUF_DIRTY] に相当するデータ構造は？ (25点)
Q4. write_some_buffers() に相当する関数は？ (25点)
制限時間 30分 -- 理解の程度は どうすれば分かるか確信を持てるまでで良い。
こんなところでどうだろう。
さて、write に関してやりたいことは、何かというと write_some_buffers の中で、書くことが決まったページ が出たら、 LRU にかかわらず disk の 物理的位置が連続している ダーティなページを 書き出すということである。ただし無限に やると 時間が かかりすぎるので、 あるゾーンの中でという条件を付け加える。ゾーンは disk の offset を 2MB 毎に 区切ったもの ということで良いと思う。
ゾーンを見つけ出すためには、通常 ハッシュを持つことになると思う。 その なかに入るのは、buffer_head ということになりそうだ。
buffer_head は、include/linux/fs.h に定義がある。
既にそういうロジックがあるかどうかだが、buffer_head には、 どこに書き出すかについての 情報が含まれている。だから buffer_head の ハッシュを作るのは、適切なはず。
struct buffer_head {
/* First cache line: */
struct buffer_head *b_next; /* Hash queue list */
unsigned long b_blocknr; /* block number */
kdev_t b_dev; /* device (B_FREE = free) */
struct buffer_head *b_next_free;/* lru/free list linkage */
struct buffer_head *b_reqnext; /* request queue */
char * b_data; /* pointer to data block */
struct page *b_page; /* the page this bh is mapped to */
:
全部じゃないけどまあ、こんなかんじ。
Disk の 物理的な位置でハッシュするなんてことは、やっていないようだ。 だから コードをいれる必要がある。
まあ、そんなに難しいということはないんじゃないか なんて思っている。
結局 、ダーティブロック専用の ハッシュを作り、 write_some_buffers() で、1 つのページを write 対象にしたときは、 それが含まれる 2MB のゾーンのうち、連続して汚れている分を 一気に書き出す。 という仕組みを作った。本来 write_some_buffers は、1 回で 128KB 書き出す ような 設計になっていたが、今回は、I/O 1 回 相当にした。(一気に書き出すから スループットはかえって高い)
評価は、linux カーネルを 1 台のDisk の別々のディレクトリに 5 多重で展開して、
カーネルは、2.4.10 を使った。
オリジナル 今回の改造の結果 時間 129.6 sec 32.4 sec Write量 464.016 MB 684.296 MB 転送速度 3.57 MB/sec 21.08 MB/sec Write頻度 119.2 times/sec 194.25 times/sec 平均I/O サイズ 30.01 KB 108.53 KB 1 回に書き出した量の平均 -- 603.78 KB
うーん。なかなかではないか。
おやくそく パッチ
2.4.10 からかなり変わっているからそのままは 当たらない。
( 2.4.15 をみたらかなり変わっているけど、今回変更したところは、
それほどは影響ないみたい。)
テストなんで きれいなコードではない。そこんところよろしく。
さらに おやくそく。このコードは動作を保証するものではない。
特にファイル系をいじっているので、ファイルが壊れるかも...
練習問題)
NetBSD で 同じことをやってみましょう。
( やる必要があるかどうかわからないけど )
制限時間 50時間
問題 その1) 上記の改造をすると、確かに メモリがある間は 速くなった。 ところが、大量の ファイルを展開すると、システムが止まったりして、 ひどいことになる。
なぜそうなるのか...調べていくと ... ファイルを沢山つくると、管理情報で ある inode と ファイルの実態である buffer_cache がともに 急速に増える わけだが、メモリが足りなくなったら、buffer_cache を シュリンクしにいく。
inode の方は、ほとんど (というよりまったく) シュリンクされないような 動きになって、必要のない inode を大量に溜め込み、buffer_cache がほとんど ない状態になる。
もともと、disk のスループットを上げるために、buffer_cache が かなり あるのが前提なわけで、メモリが足りなくなったからといって buffer_cache が ないような状態にまで行ってしまうと、スループットは 極端に落ちる。
さらに調べていくと ... どうも 一回使った inode は、ほとんど free されない。 umount したときに はじめて inode が free される といっても過言では ないぐらい。
具体的にかくと...__alloc_pages というページをアロケートする関数が メモリ不足を認識すると、
balance_classzone
try_to_free_pages
shrink_caches
1) shrink_cache
try_to_free_buffers
2) shrink_icache_memory
という関係で shrink のルーチンが動く。しかし ... shrink_icache_memory で ほとんど free しない。結果 buffer_cache ばかり free される。
うーん。どうしたものか。
頭を冷やしてコードを見れば... inode というものは、リファレンスがなくなれば
速やかに free される構造をしている。... ということは誰がリファレンスを
握っているのか ...
それは、dentry といわれるもの。ファイル名から inode を検索するための
キャッシュと考えて良い。
で、例えば linux カーネルを 5 つ展開すると inode の数と dentry の数は
次のように変わる。
nr_dentry (nr_unused) nr_inodes (nr_unused) 展開前 3133 2841 2232 0 展開後 51729 48976 50816 0
nr_dentry の nr_unused にカウントされているものは、現時点では 使われていないが、キャッシュされているもの。 いつだって free できる状態だが、free しない。キャッシュだから当然だ。
で、nr_unused な dentry を free するのは、メモリが枯渇して、alloc_pages (ページ単位のアロケート)が できない となった状態。これでは 先に buffer_cache がなくなってしまうから、遅すぎる というのがたぶん問題。 こういうことであれば -- dentry の数 に制限を設けるようなコードを いれるのが、たぶん最も簡単な解決策だろう。
どこにいれるべきか... たぶん dentry を allocate しようと思ったときに 数をチェックして、制限を越えていたら、nr_unused の 何割かを free してしまう。 その関数には、prune_dcache() が使えるはず。多分うまくいくだろう。
結局、これについては、こんなコードにした。
fs/dache.c:d_alloc() -- dentry を allocate する関数 --- の先頭で、
dentry の数 dentry_stat.nr_dentry が ある数を越えて、かつ
dentry_stat.nr_unused がある一定するあるケース(普通はある)
では、
prune_dcache(2000);
prune_icache(2000);
という風に cache を free するようにした。(2000 は適当)
このコードは 一見うまくいく。dentry および inode の数を一定に押えることが 出来て、メモリを圧迫しない。これによって より多くの ファイルを展開する ことが出来るようにはなった。ただし、ずっと ファイルを展開しているような 定常状態には耐えられない。
上記の
1) shrink_cache
try_to_free_buffers
このパスで呼ばれる、try_to_free_buffers が致命的に遅く システムが止まる。 メモリを圧迫する要素は、buffer_cache と inode dentry のみであることは、 /proc/slabinfo を見れば分かる。try_to_free_buffers が呼ばれるような 状況がたぶんとてもまずい。flush する効率を上げているわけだから、 clean な buffer が増える速度も速い。だから、区別なく free するのではなく、 まずは、clean な buffer を free してくれないと困る。
さて、try_to_free_buffers では具体的にどんなことをしているか。今見ている VM と 最新の VM では違うそうだから、処理が同じかどうか ... このあたり を調べてみることにする。
try_to_free_buffers を見ると、パラメータで指定された page および buffer_head を free する というもので、 page がダーティなら、sync_page_buffers() で 書き出してから、free する。
もうすこし上位レベルから見てみる。
vmscan.c:shrink_cache() というのが、page を scan して free していく コード。当然 page の lru の順に free していく。
でも、選んだ ページを free する構造はこういう風になっている。
if (PageDirty(page) && is_page_cache_freeable(page)) {
page->mapping->a_ops->writepage(page);
}
if (page->buffers) {
try_to_free_buffers(page, gfp_mask);
}
2.4.17 では、try_to_free_buffers のかわりに try_to_release_page という関数 が使われているが、構造は同じ。
shrink_cache() を 2 パスにして、最初のパスでは、書き出さなければ いけない page を skip するようにしたらよさそうに思える。 この方針で考えてみることにする。
なんとなく、わかってきた。
__alloc_pages でメモリが足りないと判断すると try_to_free_pages を呼び それが shrink_caches を呼ぶ。
もともとは、shrink_caches は、buffer_cache を 減らせるだけ減らして、 それでも ダメなら、dentry ひいては inode を free し出す。
これが第一の問題で、これは、dentry の数を制限することで解決する。 これをクリアすると次の問題が見えてくる。buffer_cache を減らすルーチン は、shrink_cache だが、LRU の順番だけで free していくので、 上の改造の 利点が 生かせない。
これが第2の問題。これは、clean なページのみを free するものを作って 最初に それを動かせば良い。これはなんとか作ることが出来た。
さて、これをどうやっていれるか ... 実は これが大問題であった。
かなりごまかしているが、こんな感じにしてみたらうまくいっている模様。
shrink_caches に来る条件は、たぶん classzone->free_pages < classzone->pages_high ということらしいので、これに 引っかかりそうになる前に clean なページを大量に free してみる。 で、もう一回 classzone->free_pages > classzone->pages_high のチェックして、OK なら戻る。 次に dentry と icache を free してみるが、 dentry が多すぎるときのみ にする。 次に shrink_cache を呼んで buffer を free してみる。 これで、ダメなら、思い切って dentry を free する。
なんだか 意味不明な文章になってしまった。後でもういちど整理することにしよう。
2.4.10 で 計ったら 改造前後で、それほど 性能が違わなかった。 どうも 上でオリジナルと書いたのは、2.4.10 以前のものらしい。 そして、20 MB/sec が上限になってしまうのは、Disk の性能がネック ではないかも知れない。
1) Disk に書いたり ページの 開放をしない ようなケースの最短を計る。
測定の都合で、2.4.10 の改造版では、1 つ展開するのに 最短 1.640 秒 で終ったりする 。この時間は、user + sys の時間にかなり近い。5 つなら 8.200 秒。
2) 何回も違うディレクトリに展開して 定常状態にした上で 性能を測定。
こうすると、どれぐらいの性能になるんだろうか .... 5 つ分を並列に展開するのを なんかいかやって 性能を測定する。
5 台の Disk をストライピングして、100MB/sec で書けるはずの環境では、
32.755 秒ぐらいかかった。
そして 実際に Disk に書けた 性能は、19.61 MB/sec 平均 Write サイズは、63.26 KB
( ストライピングしているんで、128 K 近い I/O は、だいたい 2 つに分割される
そうすると、したのDisk レベルで見える I/O 長は 半分の 64K になってしまう)
いつも使っている Disk だと ばらつきは大きいもののこれより速い。
26.873 秒 - 27.865 秒 - 37.856 秒 - 26.673 秒 - 34.936 秒
でも Disk の Write 性能は、20.01 MB/sec 平均 Write サイズは、108.90 KB
では、2.4.10 そのものはどうだろう。
おなじ Disk だと
38.177 秒 - 47.604 秒 - 48.811 秒 - 48.352 秒 - 47.655 秒
となった。確かに速くなっている。ただ、オリジナルも すごく遅いわけではない。
今の疑問は、いったい なにがボトルネックなのかということ。
これは原因がわかった、テストプログラムを動かしているときに、KDB で止めて スタックをトレースしてみれば良いわけだ。
そうして、どこで止まっているかを見たら ...
ext2_new_block の延長で read_block_bitmap で read しているか、 ext2_new_inode の延長で、read_inode_bitmap で read しているか の どちらか で止まっている tar のプロセスがいて、他の プロセスも 結局おなじ ことがしたいわけで、read しているプロセスの処理が終るのを 待っていたりする。
結局、bitmap を pre_read するような改造を ext2fs でしなければ、これ以上の write 性能の改善は無理なのだろう。
write を先にやったのは、いろいろ理由があるんだけども、 write の方が 簡単だから という理由も大きい。
read の方は、共通部ではどうにもならず、 ファイルシステムをいじらないといけない 予感がするしぃ。
いったいどっから手を付ければよいか... それもイメージが湧いていない。 基本的には、ある Disk のデータを読むということを決めたら、そのまわりの データも一気に読み込めば良いわけだ。read の場合は、ゾーンは、128K ぐらい で良いと思う。( write は 既に汚れたデータを書くから それほど 無駄にはならないが、read は無駄になる可能性が ある。)
ただ、無駄になったとしても、メモリが無駄というだけで、Disk 性能としては あまり 無駄になっていない。なぜなら、1 回の I/O で 10ms かかるとして、 余分に 100KB 程読んでも (30-50MB/sec で転送できるとすれば)時間は、 2-3ms しか余分にかからない。
50 % しか有効でないとしても 10KB 程度の I/O とくらべて 5倍のスループットで 有効なデータをロードできる。3割増しの時間がかかるとしても、3.5 倍ぐらい 性能があがるわけだ。100% なら 7 倍。数字は適当だが、無駄でも沢山読んだ ほうがお得なのは理解してもらえるだろう。
評価の基準は、
という感じでいいかな。オリジナルは、107.961 秒ですごく遅い。 20秒ぐらいまで速くなるといいなと思っている。
さて、上位レベルで、pre read を行うには、どうしたら良いか ... その前に block を read する 手続きを調べてみることにする。
同期して read するコードは次のようになっている。
struct buffer_head * bread(kdev_t dev, int block, int size)
{
struct buffer_head * bh;
bh = getblk(dev, block, size); /* buffer cache を取って来る */
if (buffer_uptodate(bh)) /* 既に read 済なら 戻る */
return bh;
ll_rw_block(READ, 1, &bh); /* read 要求を出す */
wait_on_buffer(bh); /* read 完了を待つ */
if (buffer_uptodate(bh)) /* 中身がはいっていたら 戻る */
return bh;
brelse(bh); /* エラーのときは buffer cache を開放
( リファレンスを減らす)
*/
return NULL;
}
pre_read を行うには、
get_blk して buffer cache を取る。 もし buffer_uptodate(bh) なら、既に read 済だから なにもしない。 ll_rw_block(READ, 1, &bh); して、read 要求を出しておく。
というようなコードを動かせば、 cache に fill はしてくれる。 問題は後始末。brelse(bh) 動かせば良いだけだけども だれがいつやるのか.. かなぁ。
先に API を考えてみる。上位層は、ここの block を非同期で fill してね みたいな API が便利かも。
void pre_bread(kdev_t dev, int block, int size, int num)
こんなかんじで、dev,block,size から num 個分 を fill するような関数仕様 が使いやすそう。 で、その結果なんて知ったことではないから、戻り値はなしで、 後始末が必要なら下位層でやる。
たぶん bread() するところで、次読んどくところが予想できる 場合があれば、pre_bread を突っ込むだけで良い。
で、後始末はどうすべきか ... buffer head に フラグを1つ持たせて、 read が完了したときに、リファレンスを減らすとかすれば良いのかなぁ。
ll_rw_block では、
bh->b_end_io = end_buffer_io_sync;
とやっているから、たぶん end_buffer_io_sync で Preread なら 後始末をすれば良いのだろう。
この線で検討してみることにする。
bread というのは、同期の read で、ext2fs では inode , inode_bitmap, block_bitmap の read に使うことは、わかった。
そして inode_bitmap や block_bitmap を read するタイミングで、 将来必要になりそうなところを非同期で read しておくのが良いのではないか という気がする。
また、通常のデータは、block_read_full_page とかが 使われるようだ。 この場合は、非同期で read を行う。こっちのケースでは、 将来必要になりそうなところはわからない。局所性があるに違いないということで 読みたいページの周囲を 非同期で read しておく というので良いのだろう という気はする。
ただ、どうやって というのが よくわからない。うーん。どうしたものか。
第一の問題は、必要なときに読む方法と ずいぶん違う読み方になるので、
読んだデータが 本来の read のパスで ちゃんと 再利用されるのかどうか。
第二の問題は、必要なときまで、pre-read したものを保持できているかどうか。
それ以外にもまだ問題はありそう。