#はじめに
Linuxでファイルのreadaheadがどのように動いているのかを読み解くという趣旨の雑記です。kernelへの理解の助けにはなると思いますが、何かしらの結論めいた記事というには程遠いです。
なお、Linux-4.16くらいを見ています。
#readaheadの役割
例えば、とあるファイルを先頭から4KB分readしようとしたとする。要求に応じ、Linux kernelは該当ファイルのinodeの中身の位置を特定し、少なくとも中身の先頭から4KB分をreadして返さないといけない。
ただ、先頭から4KBをreadするようなユースケースの場合、続けて次の4KBもreadするような処理へ続く可能性が一般的に高い。このため、先に4KBをreadするときに、kernelが勝手に4KBではなくて8KBやら16KBやらreadしてページキャッシュに載せておくと、続きの要求を出すときにすでにreadが完了していることになる。このように、「次にこのへんへのread要求が来るに違いない」と先を見据えて勝手にreadしておく仕組みのことをreadaheadという。
ディスクのI/OはCPUやRAMに比べて桁違いに遅い。ただし、シーケンシャルには少し強い。このため、先を見据えて一度にたくさん目にreadしておくと、読みが当たった時の効果が大きくなる。
え？最近はNVMeなSSDで、ランダムに強いし、待ちもそれほど長くはないって？確かにそういう話もあるから、この記事の内容はすぐに陳腐化するかもしれない。下記は、現状のLinuxの実装を追っていて、またそれは従来型のHDDなディスクを前提にしているかもしれない。
#readaheadの処理の流れ
概ね、下記の番号順に処理が流れて、readaheadの実処理へとつながる。
- ブロックデバイスのドライバによるra_pagesの初期値
- ブロックデバイスのインスタンス毎のsysfsのread_ahead_kb設定
- Filesystem固有のra_pages
- File Descripter毎のra_pagesとファイルアクセスモード
- read要求の起こり方によるreadaheadアルゴリズム
特に5番目は、mmapした領域でのpage faultを起こしたときと、普通に**read(2)**したときとで少し系が異なる。下記で軽く触れていくが、概ね似たような系に行き着く。
#実験
readaheadの動きは、普段はほとんど意識しないため、実際に動かして確認しながらのほうが理解しやすい。
linux-ftoolsを使った実験
Linuxでページキャッシュを確認・解放してみた - Qiitaを参考に、fincoreとfadviseを用意する。
次に、テストに用いる適当なファイルを用意する。
[rarul@tina ~]$ mkdir test
[rarul@tina ~]$ cd test
[rarul@tina test]$ dd if=/dev/urandom of=hoge.dat bs=4k count=1024
で、おもむろに下記のようなテスト用サンプルプログラムを書き、
#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#include <fcntl.h>
#include <unistd.h>
static void do_main(char *filename, int advise_val, unsigned int start_pos, unsigned int end_pos) {
int fd;
unsigned i;
off_t lseek_ret;
char buf[4096];
if (start_pos >= end_pos) {
errx(1, "pos err: start_pos %d end_pos %d\n", start_pos, end_pos);
}
fd = open (filename, O_RDONLY);
if (fd < 0){
err(1, "%s not found\n", filename);
}
if (advise_val >= 0) {
printf("fadvise %d\n", advise_val);
int retval = posix_fadvise (fd, 0, 0, advise_val);
if (retval) {
printf("posix_fadvise(%s, %d) ret %d\n", filename, advise_val, retval);
}
} else {
printf("skipping posix_fadvise\n");
}
lseek_ret = lseek (fd, start_pos * sizeof(buf), SEEK_SET);
if (lseek_ret != start_pos * sizeof(buf)) {
printf("lseek() fail...\n");
}
for( i=start_pos; i<end_pos; i++) {
ssize_t read_ret;
printf("reading pos %d(*4KB)\n", i);
read_ret = read (fd, buf, sizeof(buf));
if (read_ret != sizeof(buf)) {
printf("read() fail... expected %ld, readed %ld\n", sizeof(buf), read_ret);
}
}
close(fd);
}
int main (int argc, char *argv[]) {
if (argc < 2) {
errx(1,"filename required\n");
}
if (argc < 3) {
errx(1,"fadvise num required\n");
}
if (argc < 4) {
errx(1,"start_pos (*4KB) required\n");
}
if (argc < 5) {
errx(1,"end_pos (*4KB) required\n");
}
do_main (argv[1], atoi(argv[2]), atoi(argv[3]), atoi(argv[4]));
return 0;
}
実験してみる
[rarul@tina test]$ gcc -Wall -O2 -g -c -o main.o main.c
[rarul@tina test]$ fincore hoge.dat
filename size total pages cached pages cached size cached percentage
hoge.dat 4194304 1024 0 0 0.000000
[rarul@tina test]$ ./main hoge.dat 0 0 1
skipping posix_fadvise
reading pos 0(*4KB)
[rarul@tina test]$ fincore hoge.dat
filename size total pages cached pages cached size cached percentage
0 1 2 3
hoge.dat 4194304 1024 4 16384 0.390625
4KBしかreadしていないのに、readaheadにより16KBキャッシュにのってる様子がわかる。また下記のように事前にposix_fadvise()でPOSIX_FADV_RANDOMを設定しておくと、4KBのreadで4KBしかキャッシュにのらない様子もわかる。
[rarul@tina test]$ fincore hoge.dat
filename size total pages cached pages cached size cached percentage
hoge.dat 4194304 1024 0 0 0.000000
[rarul@tina test]$ ./main hoge.dat 1 0 1
fadvise 1
reading pos 0(*4KB)
[rarul@tina test]$ fincore hoge.dat
filename size total pages cached pages cached size cached percentage
0
hoge.dat 4194304 1024 1 4096 0.097656
また実験を行うときは、fadviseコマンドを使い事前にキャッシュから追い出しておくことを忘れずに。
[rarul@tina test]$ fadvise hoge.dat POSIX_FADV_DONTNEED
Going to fadvise hoge.dat
offset: 0
length: 4194304
mode: POSIX_FADV_DONTNEED
WIN
drop_cachesの方法でもいいけど、こちらだと、特定のファイルや領域ではなくてすべてのキャッシュを対象になってしまうのでご注意を。
/dev/ram0を使ってblktrace
linux-ftoolsを使った実験のほうがわかりやすいものの「それ本当にreadaheadの動きなの？」と疑い深い人は、blktraceを使って実験すると良いと思う。この場合、実験の対象のブロックデバイスをそれ用に用意したほうがわかりやすい。brd: メモリ上に作成するブロックデバイス - Qiitaを参考に、/dev/ram0を用意してテストする。
root@tina:/home/rarul/test/bdev# mkfs.ext4 /dev/ram0
mke2fs 1.42.13 (17-May-2015)
Discarding device blocks: done
Creating filesystem with 65536 1k blocks and 16384 inodes
Filesystem UUID: 5d025508-82d7-4a8b-832f-4c56a3e4d029
Superblock backups stored on blocks:
8193, 24577, 40961, 57345
Allocating group tables: done
Writing inode tables: done
Creating journal (4096 blocks): done
Writing superblocks and filesystem accounting information: done
root@tina:/home/rarul# mkdir mnt
root@tina:/home/rarul# mount -t ext4 /dev/ram0 mnt
root@tina:/home/rarul# cd mnt
root@tina:/home/rarul/mnt# dd if=/dev/urandom of=hoge.dat bs=4k count=1024
別端末を開いてそこでblktraceを使いリアルタイム監視しながら、
root@tina:/home/rarul/mnt# blktrace -d /dev/ram0 -o - |blkparse -i -
先と同じように、fincore, fadvise, main(テストプログラム)で4KBをreadしてみると、blktraceに下記のようなログが流れて、16KB(==32*512)のreadが行われたことがわかる。
1,0 1 8 33.140543276 25621 Q R 20482 + 32 [main]
#ブロックデバイスのドライバによるra_pagesの初期値
ここからは具体的にコードを追っておく。まずはブロックデバイスのドライバによるra_pagesの初期値から。kernel/block/blk-core.cの**blk_alloc_queue_node()**より、
q->backing_dev_info->ra_pages =
(VM_MAX_READAHEAD * 1024) / PAGE_SIZE;
VM_MAX_READAHEADは、kernel/include/linux/mm.hより、
/* readahead.c */
#define VM_MAX_READAHEAD 128 /* kbytes */
#define VM_MIN_READAHEAD 16 /* kbytes (includes current page) */
で、128KB(をページ数にしたもの)が入る。ただこの値はドライバにより上書きされる。例えばkernel/drivers/md/raid0.cの**raid0_run()**より、
if (mddev->queue) {
/* calculate the max read-ahead size.
* For read-ahead of large files to be effective, we need to
* readahead at least twice a whole stripe. i.e. number of devices
* multiplied by chunk size times 2.
* If an individual device has an ra_pages greater than the
* chunk size, then we will not drive that device as hard as it
* wants. We consider this a configuration error: a larger
* chunksize should be used in that case.
*/
int stripe = mddev->raid_disks *
(mddev->chunk_sectors << 9) / PAGE_SIZE;
if (mddev->queue->backing_dev_info->ra_pages < 2* stripe)
mddev->queue->backing_dev_info->ra_pages = 2* stripe;
}
と、RAIDの場合はストライピングサイズを気にして大きめのほうが良いという判断のようだ。逆に言えば、それだけキャッシュに乗せても大丈夫なくらいRAMが潤沢にある、もしくはこのボリュームでは小さいファイルをたくさん作るような用途を想定していない、などの前提が置かれていることになる。
ブロックデバイスのドライバごとにこういう処理をやっていることがあるので、詳しくはソースコードをra_pagesで確認してみると良い。ちなみに、いちばん身近だと思われるSCSIディスク(/dev/sda)では特に個別処理はやっていないようだ。
#ブロックデバイスのインスタンス毎のsysfsのread_ahead_kb設定
ブロックデバイスごとに初期値が入ったra_pagesは、sysfsやioctlにより、インスタンスごとに設定値を変更できる。kernel/block/blk-sysfs.cより、
static ssize_t queue_ra_show(struct request_queue *q, char *page)
{
unsigned long ra_kb = q->backing_dev_info->ra_pages <<
(PAGE_SHIFT - 10);
return queue_var_show(ra_kb, (page));
}
static ssize_t
queue_ra_store(struct request_queue *q, const char *page, size_t count)
{
unsigned long ra_kb;
ssize_t ret = queue_var_store(&ra_kb, page, count);
if (ret < 0)
return ret;
q->backing_dev_info->ra_pages = ra_kb >> (PAGE_SHIFT - 10);
return ret;
}
static struct queue_sysfs_entry queue_ra_entry = {
.attr = {.name = "read_ahead_kb", .mode = S_IRUGO | S_IWUSR },
.show = queue_ra_show,
.store = queue_ra_store,
};
という感じになっていて、/sys/block/sda/queue/read_ahead_kbから設定値を確認・変更できる。
[rarul@tina ~]$ cat /sys/block/sda/queue/read_ahead_kb
128
確かに128(KB)になっていた。このあたりはDocumentationにも書いてある。kernel/Documentation/block/queue-sysfs.txtより、
read_ahead_kb (RW)
------------------
Maximum number of kilobytes to read-ahead for filesystems on this block
device.
また、ioctl()のBLKFRAGET, BLKFRASETででも設定・変更できる。kernel/block/ioctl.cより、
case BLKRAGET:
case BLKFRAGET:
if (!arg)
return -EINVAL;
return put_long(arg, (bdev->bd_bdi->ra_pages*PAGE_SIZE) / 512);
case BLKRASET:
case BLKFRASET:
if(!capable(CAP_SYS_ADMIN))
return -EACCES;
bdev->bd_bdi->ra_pages = (arg * 512) / PAGE_SIZE;
return 0;
#Filesystem固有のra_pages
このようにブロックデバイス毎(正確にはbacking_dev_info毎)に用意されたra_pagesではあるが、Filesystemによっては、mountするときにこれがことごとく無視される。例えばbtrfsの場合、kernel/fs/btrfs/disk-io.cの**open_ctree()**より、
sb->s_bdi->ra_pages = VM_MAX_READAHEAD * SZ_1K / PAGE_SIZE;
sb->s_bdi->ra_pages *= btrfs_super_num_devices(disk_super);
sb->s_bdi->ra_pages = max(sb->s_bdi->ra_pages, SZ_4M / PAGE_SIZE);
となっていて、せっかくのbdi(backing_dev_info)のもとの値を全く使っていない。そのBDIも、こういう具合に個別化するケースを考慮していて、kernel/fs/super.cより、
/*
* Setup private BDI for given superblock. It gets automatically cleaned up
* in generic_shutdown_super().
*/
int super_setup_bdi_name(struct super_block *sb, char *fmt, ...)
{
struct backing_dev_info *bdi;
int err;
va_list args;
bdi = bdi_alloc(GFP_KERNEL);
if (!bdi)
return -ENOMEM;
bdi->name = sb->s_type->name;
va_start(args, fmt);
err = bdi_register_va(bdi, fmt, args);
va_end(args);
if (err) {
bdi_put(bdi);
return err;
}
WARN_ON(sb->s_bdi != &noop_backing_dev_info);
sb->s_bdi = bdi;
return 0;
}
EXPORT_SYMBOL(super_setup_bdi_name);
/*
* Setup private BDI for given superblock. I gets automatically cleaned up
* in generic_shutdown_super().
*/
int super_setup_bdi(struct super_block *sb)
{
static atomic_long_t bdi_seq = ATOMIC_LONG_INIT(0);
return super_setup_bdi_name(sb, "%.28s-%ld", sb->s_type->name,
atomic_long_inc_return(&bdi_seq));
}
EXPORT_SYMBOL(super_setup_bdi);
と、**super_setup_bdi()やsuper_setup_bdi_name()を呼べば良いという構造になっている。現にbtrfsもそうしていて、kernel/fs/btrfs/super.cのbtrfs_fill_super()**より、
err = super_setup_bdi(sb);
if (err) {
btrfs_err(fs_info, "super_setup_bdi failed");
return err;
}
ちなみに、bdi(backing_dev_info)とは、こういう具合に同じブロックデバイス(のインスタンス)であったとしても、使われ方により先読みや(dirtyなinodeの)writebackの処理に差を設けたい(namespace(==dockerなどのパーティショニング)場合のために設けられた機構の模様。
#File Descripter毎のra_pagesとファイルアクセスモード
このようにmount(superblock)毎に用意されたra_pagesは、ファイルをopenしたときのfile descriptorに結び付けられる。kernel/mm/readahead.cより、
/*
* Initialise a struct file's readahead state. Assumes that the caller has
* memset *ra to zero.
*/
void
file_ra_state_init(struct file_ra_state *ra, struct address_space *mapping)
{
ra->ra_pages = inode_to_bdi(mapping->host)->ra_pages;
ra->prev_pos = -1;
}
EXPORT_SYMBOL_GPL(file_ra_state_init);
kernel/fs/open.cの**do_dentry_open()**より、
file_ra_state_init(&f->f_ra, f->f_mapping->host->i_mapping);
となっていて、open()するときにbdiのra_pagesからfdのra_pagesへ初期値が渡る。
なお、posix_fadvise()ではPOSIX_FADV_NORMAL, POSIX_FADV_SEQUENTIAL, POSIX_FADV_RANDOMのいずれかの状態を指定することができる(初期はPOSIX_FADV_NORMAL)が、この状態もFile Descriptorごとに記憶されることになるため、使用する際には注意が必要となる。kernel/mm/fadvise.cより、
switch (advice) {
case POSIX_FADV_NORMAL:
f.file->f_ra.ra_pages = bdi->ra_pages;
spin_lock(&f.file->f_lock);
f.file->f_mode &= ~FMODE_RANDOM;
spin_unlock(&f.file->f_lock);
break;
case POSIX_FADV_RANDOM:
spin_lock(&f.file->f_lock);
f.file->f_mode |= FMODE_RANDOM;
spin_unlock(&f.file->f_lock);
break;
case POSIX_FADV_SEQUENTIAL:
f.file->f_ra.ra_pages = bdi->ra_pages * 2;
spin_lock(&f.file->f_lock);
f.file->f_mode &= ~FMODE_RANDOM;
spin_unlock(&f.file->f_lock);
break;
f.fileに覚えているためFile Descriptor毎となる。なお、他にPOSIX_FADV_WILLNEED, POSIX_FADV_NOREUSE, POSIX_FADV_DONTNEEDがあるが、これらは先読みの動きに関する状態は特に覚えたり忘れたりはしない。
似たsyscallsとして**madvise()**があるが、こちらはvmaに状態を覚えている。kernel/mm/madvise.cより、
/*
* We can potentially split a vm area into separate
* areas, each area with its own behavior.
*/
static long madvise_behavior(struct vm_area_struct *vma,
struct vm_area_struct **prev,
unsigned long start, unsigned long end, int behavior)
{
struct mm_struct *mm = vma->vm_mm;
int error = 0;
pgoff_t pgoff;
unsigned long new_flags = vma->vm_flags;
switch (behavior) {
case MADV_NORMAL:
new_flags = new_flags & ~VM_RAND_READ & ~VM_SEQ_READ;
break;
case MADV_SEQUENTIAL:
new_flags = (new_flags & ~VM_RAND_READ) | VM_SEQ_READ;
break;
case MADV_RANDOM:
new_flags = (new_flags & ~VM_SEQ_READ) | VM_RAND_READ;
break;
(-----snip-----)
success:
/*
* vm_flags is protected by the mmap_sem held in write mode.
*/
vma->vm_flags = new_flags;
vmaごとなので、1つのmmap()に閉じた設定となり、通常はプロセスをまたぐことはないと思われる(ちょっと自信ない)
#read要求の起こり方によるreadaheadアルゴリズム
ようやく、fdやvmaごとの値に基づいたreadaheadのアルゴリズムに入れる。ただ、実コードはヒューリスティックな処理ばかりなので、ぱっと見では何をどうしたいのか理解しづらい。このため、先に見るべき箇所をピックアップしておく。
##ASCIIアート入りコメント
kernel/mm/readahead.cのcount_history_pages()の手前に説明がある。
/*
* On-demand readahead design.
*
* The fields in struct file_ra_state represent the most-recently-executed
* readahead attempt:
*
* |<----- async_size ---------|
* |------------------- size -------------------->|
* |==================#===========================|
* ^start ^page marked with PG_readahead
*
* To overlap application thinking time and disk I/O time, we do
* `readahead pipelining': Do not wait until the application consumed all
* readahead pages and stalled on the missing page at readahead_index;
* Instead, submit an asynchronous readahead I/O as soon as there are
* only async_size pages left in the readahead window. Normally async_size
* will be equal to size, for maximum pipelining.
*
* In interleaved sequential reads, concurrent streams on the same fd can
* be invalidating each other's readahead state. So we flag the new readahead
* page at (start+size-async_size) with PG_readahead, and use it as readahead
* indicator. The flag won't be set on already cached pages, to avoid the
* readahead-for-nothing fuss, saving pointless page cache lookups.
*
* prev_pos tracks the last visited byte in the _previous_ read request.
* It should be maintained by the caller, and will be used for detecting
* small random reads. Note that the readahead algorithm checks loosely
* for sequential patterns. Hence interleaved reads might be served as
* sequential ones.
*
* There is a special-case: if the first page which the application tries to
* read happens to be the first page of the file, it is assumed that a linear
* read is about to happen and the window is immediately set to the initial size
* based on I/O request size and the max_readahead.
*
* The code ramps up the readahead size aggressively at first, but slow down as
* it approaches max_readhead.
*/
##readaheadが走る系
mm以下で似たような名前の関数を呼び分けているので、いくつか典型的なcall traceを書き出してみて、どういうときにどこの関数がreadaheadするかを整理してみる。
###filemap_fault()
mmap()した領域へのアクセスでpage faultを起こしたときに呼ばれる関数である。ただいくつかのFilesystemでは、直接.faultでfilemap_fault()をしていするのではなくて、独自にヘルパー関数を用意しているようだ(今回はここは詳細を追わないことにする)
filemap_fault()では、faultを起こしたpageがすでにキャッシュにあった(==find_get_page())ら**do_async_mmap_readahead()を呼び、なかったらdo_sync_mmap_readahead()**を呼ぶ、という動きをする。また、うまくreadできなかったら、**shrink_readahead_size_eio()**を呼び、ra_pagesを4分の1にする。kernel/mm/filemap.cより、
/*
* CD/DVDs are error prone. When a medium error occurs, the driver may fail
* a _large_ part of the i/o request. Imagine the worst scenario:
*
* ---R__________________________________________B__________
* ^ reading here ^ bad block(assume 4k)
*
* read(R) => miss => readahead(R...B) => media error => frustrating retries
* => failing the whole request => read(R) => read(R+1) =>
* readahead(R+1...B+1) => bang => read(R+2) => read(R+3) =>
* readahead(R+3...B+2) => bang => read(R+3) => read(R+4) =>
* readahead(R+4...B+3) => bang => read(R+4) => read(R+5) => ......
*
* It is going insane. Fix it by quickly scaling down the readahead size.
*/
static void shrink_readahead_size_eio(struct file *filp,
struct file_ra_state *ra)
{
ra->ra_pages /= 4;
}
**do_async_mmap_readahead()**は、VM_RAND_READでなかったら(==madvise()をMADV_RANDOMで呼んでなかったら)、**page_cache_async_readahead()**を呼ぶ。
**do_sync_mmap_readahead()**は、VM_RAND_READだったら(==madvise()をMADV_RANDOMで呼んでいたら)なにもせず、そうでない場合に、VM_SEQ_READだったら(==madvise()をMADV_SEQUENTIALで呼んでいたら)**page_cache_sync_readahead()**を呼び、そうでなかったら先読みを含むreadをする(後述する)
###generic_file_read_iter()
read()を呼んだときに来る。ここも先と同様、Filesystemによっては、直接.read_iterでgeneric_file_read_iter()をしていするのではなくて、独自にヘルパー関数を用意している(同様に詳細は追わない)
generic_file_read_iter()は、O_DIRECTじゃない場合は特に何もせずにgeneric_file_buffered_read()を呼ぶ。generic_file_buffered_read()は、読みたいところがまだキャッシュに乗ってなかったらpage_cache_sync_readahead()を呼び、そうでないならpage_cache_async_readahead()を呼ぶ。
call traceまとめ
ざっくりとしすぎているが、まとめるとこうなる。madvise()やposix_fadvise()はあまり使わないので、太字で強調したところがよく来る箇所になるかと思う。
- fault起こした箇所がキャッシュに乗っていなかった場合
-
madvise()をMADV_RANDOMで呼んでいなくて、madvise()をMADV_SEQUENTIALで呼んでいなかった場合
- filemap_fault()->do_sync_mmap_readahead()->ra_submit()
- do_sync_mmap_readahead()の中で先読みサイズをヒューリスティックに決める。
- madvise()をMADV_RANDOMで呼んでいなくて、madvise()をMADV_SEQUENTIALで呼んでいて、posix_fadvise()をPOSIX_FADV_RANDOMで呼んでいなかった場合
- filemap_fault()->do_sync_mmap_readahead()->page_cache_sync_readahead()->ondemand_readahead()
- ondemand_readahead()でヒューリスティックなアルゴリズムを実行する
- madvise()をMADV_RANDOMで呼んでいなくて、madvise()をMADV_SEQUENTIALで呼んでいて、posix_fadvise()をPOSIX_FADV_RANDOMで呼んでいた場合
- filemap_fault()->do_sync_mmap_readahead()->page_cache_sync_readahead()->force_page_cache_readahead()
- force_page_cache_readahead()にて、ra_pages分だけ先読みをする。
- madvise()をMADV_RANDOMで呼んでいた場合、
- filemap_fault()->do_sync_mmap_readahead()までくるが、先読みをしない
- fault起こした箇所がキャッシュに乗っていた場合
-
madvise()でMADV_SEQUENTIALしていなかった場合
- filemap_fault()->do_async_mmap_readahead()->page_cache_async_readahead()->ondemand_readahead()
- ondemand_readahead()でヒューリスティックなアルゴリズムを実行する
- madvise()でMADV_SEQUENTIALしていた場合
- filemap_fault()->do_async_mmap_readahead()までくるが、先読みをしない
- O_DIRECTでないファイルをreadした場合
-
readする箇所がキャッシュに乗っていなくて、posix_fadvise()をPOSIX_FADV_RANDOMで呼んでいなかった場合
- generic_file_buffered_read()->page_cache_sync_readahead()->ondemand_readahead()
- ondemand_readahead()でヒューリスティックなアルゴリズムを実行する
- readする箇所がキャッシュに乗っていなくて、posix_fadvise()をPOSIX_FADV_RANDOMで呼んでいた場合
- generic_file_buffered_read()->page_cache_sync_readahead()->force_page_cache_readahead()
- force_page_cache_readahead()は、先読みというよりも、本当に必要な分だけ読むという感じ。
-
readする箇所がキャッシュに乗っていた場合
- generic_file_buffered_read()->page_cache_async_readahead()->ondemand_readahead()
- ondemand_readahead()でヒューリスティックなアルゴリズムを実行する
- O_DIRECTなファイルをreadした場合
- 先読みは行わない。それ以外の詳細は今回は省略。興味ある人は直接はgeneric_file_read_iter()以下を見て。
force_page_cache_readahead()は、引数の分だけ必ず先読みを行う関数。posix_fadvise()をPOSIX_FADV_WILLNEEDで呼んだ場合、madvise()をMADV_WILLNEEDで呼んだ場合、**readahead()**システムコールを呼んだ場合、にも来る系となっている。
##readaheadのアルゴリズム
**force_page_cache_readahead()**は引数で指定された分だけ先読みをする関数なので、アルゴリズムっぽいものは2箇所だけとなる。
###do_sync_mmap_readahead()の後半の箇所
kernel/mm/filemap.cより、
/*
* Synchronous readahead happens when we don't even find
* a page in the page cache at all.
*/
static void do_sync_mmap_readahead(struct vm_area_struct *vma,
struct file_ra_state *ra,
struct file *file,
pgoff_t offset)
{
struct address_space *mapping = file->f_mapping;
/* If we don't want any read-ahead, don't bother */
if (vma->vm_flags & VM_RAND_READ)
return;
if (!ra->ra_pages)
return;
if (vma->vm_flags & VM_SEQ_READ) {
page_cache_sync_readahead(mapping, ra, file, offset,
ra->ra_pages);
return;
}
/* Avoid banging the cache line if not needed */
if (ra->mmap_miss < MMAP_LOTSAMISS * 10)
ra->mmap_miss++;
/*
* Do we miss much more than hit in this file? If so,
* stop bothering with read-ahead. It will only hurt.
*/
if (ra->mmap_miss > MMAP_LOTSAMISS)
return;
/*
* mmap read-around
*/
ra->start = max_t(long, 0, offset - ra->ra_pages / 2);
ra->size = ra->ra_pages;
ra->async_size = ra->ra_pages / 4;
ra_submit(ra, mapping, file);
}
VM_RAND_READやVM_SEQ_READをを確認しているのは先の系で書いたとおり。
ra_pagesがゼロになるのは、意図的にsysfsなどで設定した場合、shrink_readahead_size_eio()が繰り返し呼ばれた場合(なぜかreadに失敗する、readしたのになぜかすぐupdateでなくなってしまう)
mmap_missのチェックは、端的には、この関数do_sync_mmap_readahead()が過剰に呼ばれているに先読みを拒否するコード。アルゴリズムが理想的に動いているならば、do_async_mmap_readahead()を呼ぶことが増えるはずだが、そうなっていない場合のフェールセーフかと思われる。
チェックが終わったあと、実際に読むサイズを決める。faultを起こした箇所の前後ra_pages/2分ずつを先読みする分としつつ、faultを起こした箇所からra_pages/4分を本当に欲しい箇所としている。
###ondemand_readahead()
長めなので、複数回に分けて記載する。kernel/mm/readahead.cより、
/*
* A minimal readahead algorithm for trivial sequential/random reads.
*/
static unsigned long
ondemand_readahead(struct address_space *mapping,
struct file_ra_state *ra, struct file *filp,
bool hit_readahead_marker, pgoff_t offset,
unsigned long req_size)
{
struct backing_dev_info *bdi = inode_to_bdi(mapping->host);
unsigned long max_pages = ra->ra_pages;
pgoff_t prev_offset;
/*
* If the request exceeds the readahead window, allow the read to
* be up to the optimal hardware IO size
*/
if (req_size > max_pages && bdi->io_pages > max_pages)
max_pages = min(req_size, bdi->io_pages);
ra_pages(==max_pages)が思ったより小さかったら行けそうなところまで広げている。これが先読みするときのサイズの上限となる。
/*
* start of file
*/
if (!offset)
goto initial_readahead;
ファイルの先頭だったら、アルゴリズムを継続するのではなくて、一度get_init_ra_size()を呼びパラメータをリセットしている。
/*
* It's the expected callback offset, assume sequential access.
* Ramp up sizes, and push forward the readahead window.
*/
if ((offset == (ra->start + ra->size - ra->async_size) ||
offset == (ra->start + ra->size))) {
ra->start += ra->size;
ra->size = get_next_ra_size(ra, max_pages);
ra->async_size = ra->size;
goto readit;
}
今の要求がピッタリだったら、つまり直前の先読みがまさにうまく行っていたら、シーケンシャルアクセスだと断定する。つまり積極的な先読みをすべくget_next_ra_size()を呼ぶ。get_next_ra_sizeは、kernel/mm/readahead.cより、
/*
* Get the previous window size, ramp it up, and
* return it as the new window size.
*/
static unsigned long get_next_ra_size(struct file_ra_state *ra,
unsigned long max)
{
unsigned long cur = ra->size;
unsigned long newsize;
if (cur < max / 16)
newsize = 4 * cur;
else
newsize = 2 * cur;
return min(newsize, max);
}
先読みサイズを4倍もしくは2倍に大きくしようとする。もとのondemand_readahead()への続きへと戻り、
/*
* Hit a marked page without valid readahead state.
* E.g. interleaved reads.
* Query the pagecache for async_size, which normally equals to
* readahead size. Ramp it up and use it as the new readahead size.
*/
if (hit_readahead_marker) {
pgoff_t start;
rcu_read_lock();
start = page_cache_next_hole(mapping, offset + 1, max_pages);
rcu_read_unlock();
if (!start || start - offset > max_pages)
return 0;
ra->start = start;
ra->size = start - offset; /* old async_size */
ra->size += req_size;
ra->size = get_next_ra_size(ra, max_pages);
ra->async_size = ra->size;
goto readit;
}
page_cache_async_readahead()から呼ばれていた場合(==hit_readahead_markerがtrue)なら、holeが見つかる位置までは積極的に先読みをしようとしている。「interleaved reads」とは、https://github.com/torvalds/linux/commit/6b10c6c9fbfe754e8482efb8c8b84f8e40c0f2ebによると、同じfdを複数のスレッドが使うようなケースの模様。
/*
* oversize read
*/
if (req_size > max_pages)
goto initial_readahead;
/*
* sequential cache miss
* trivial case: (offset - prev_offset) == 1
* unaligned reads: (offset - prev_offset) == 0
*/
prev_offset = (unsigned long long)ra->prev_pos >> PAGE_SHIFT;
if (offset - prev_offset <= 1UL)
goto initial_readahead;
max_pagesが小さかった場合(途中でra_pagesをsysfsなどで小さくした？)、きれいなシーケンシャルreadが崩れた場合、にget_init_ra_size()を呼び、アルゴリズムのパラメータをリセットする。
/*
* Query the page cache and look for the traces(cached history pages)
* that a sequential stream would leave behind.
*/
if (try_context_readahead(mapping, ra, offset, req_size, max_pages))
goto readit;
try_context_readahead()は、kernel/mm/readahead.cより、
/*
* Count contiguously cached pages from @offset-1 to @offset-@max,
* this count is a conservative estimation of
* - length of the sequential read sequence, or
* - thrashing threshold in memory tight systems
*/
static pgoff_t count_history_pages(struct address_space *mapping,
pgoff_t offset, unsigned long max)
{
pgoff_t head;
rcu_read_lock();
head = page_cache_prev_hole(mapping, offset - 1, max);
rcu_read_unlock();
return offset - 1 - head;
}
/*
* page cache context based read-ahead
*/
static int try_context_readahead(struct address_space *mapping,
struct file_ra_state *ra,
pgoff_t offset,
unsigned long req_size,
unsigned long max)
{
pgoff_t size;
size = count_history_pages(mapping, offset, max);
/*
* not enough history pages:
* it could be a random read
*/
if (size <= req_size)
return 0;
/*
* starts from beginning of file:
* it is a strong indication of long-run stream (or whole-file-read)
*/
if (size >= offset)
size *= 2;
ra->start = offset;
ra->size = min(size + req_size, max);
ra->async_size = 1;
return 1;
}
現在の位置が十分な大きさのoffsetになっている(おおむね大きなファイルを読み込み中という意味になる？)なら、最大サイズまで先読みしようとする。async_size に1を入れているが、あとで計算し直すので、影響はない。下の箇所の続きへと戻り、
/*
* standalone, small random read
* Read as is, and do not pollute the readahead state.
*/
return __do_page_cache_readahead(mapping, filp, offset, req_size, 0);
これまでの条件に合致しなかったら、先読み不要となり、必要な箇所のみ読む。これで関数終わりではなく、積極的な先読みをする場合のgotoの飛び先ラベルが続き、
initial_readahead:
ra->start = offset;
ra->size = get_init_ra_size(req_size, max_pages);
ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;
get_init_ra_size()は、kernrl/mm/readahead.cより、
/*
* Set the initial window size, round to next power of 2 and square
* for small size, x 4 for medium, and x 2 for large
* for 128k (32 page) max ra
* 1-8 page = 32k initial, > 8 page = 128k initial
*/
static unsigned long get_init_ra_size(unsigned long size, unsigned long max)
{
unsigned long newsize = roundup_pow_of_two(size);
if (newsize <= max / 32)
newsize = newsize * 4;
else if (newsize <= max / 4)
newsize = newsize * 2;
else
newsize = max;
return newsize;
}
initialという名前に反し、先読みサイズを狭めるという内容の模様。元の関数に戻り、もう1つのラベルについて、
readit:
/*
* Will this read hit the readahead marker made by itself?
* If so, trigger the readahead marker hit now, and merge
* the resulted next readahead window into the current one.
*/
if (offset == ra->start && ra->size == ra->async_size) {
ra->async_size = get_next_ra_size(ra, max_pages);
ra->size += ra->async_size;
}
return ra_submit(ra, mapping, filp);
get_next_ra_size()は、先に見たとおり、先読みサイズを広げる。ここで作った要求をra_submit()にて実際に処理する。
#その他
###fuseの先読み
先で見たとおり、Filesystemで独自のbacking_dev_infoを載せたりできる仕組みがあるが、これを最大限使っていて、fuseのユーザランドに広く委ねるような実装のように見える。逆に言えば、readaheadを意識したコードにしておかないとパフォーマンスが出にくいという問題にハマりそう。
え？今どきはRAMも多いからファイルはすべてキャッシュに乗せてから運用スタートだって？いやいや組み込みの世界は日々coldbootの起動時間の理想と実測の狭間に苦しみながら汗とか涙とかストレスとか睡眠不足とか血とか上司への悪口とか(ry
###noop_backing_dev_info
noop_backing_dev_infoという名前のインスタンスがある。処理途中でブロックデバイスが消えてしまった場合などのnullオブジェクトパターンとして使われる。
###DAX
DAX(direct access mode)という機能が入りつつある。これは主にNVDIMMなどを想定して、ページキャッシュをバイパスするための機構の模様。あまり詳しくないので、このへんでも見てください。
- Linuxの不揮発メモリ対応について - Qiita
-
Linuxの不揮発メモリの使い方について - Qiitta
###swapinのreadahead
swapinの処理の中にもreadaheadというキーワードが見えた。確かにディスクから読む処理なのでreadaheadのような考え方も必要なのかもしれない。今回はほとんど目を通していないので、興味ある方、読み解いて報告くれると嬉しいです。
#おわりに
ざっくりとreadaheadの仕組みを見てきた。実際の動きは確認せずにコード上で追ってきたので、読み間違えている箇所があるかもしれない。その時はごめんなさい。
Linuxのreadaheadのこのへんは、ここ10年ほどはあまり大きな変更はないようだ。今のアルゴリズムがそれなりに上手く働いているということの裏返しかもしれない。
その一方で、SSDやらNVDIMやら、慌ただしい周辺業界の変化はある。とはいえ、昔ほどRAMは切迫してなくて一度ディスクから読めばあとはページキャッシュに乗りっぱなしというのが実情だったりするのかもしれない。
ディスクの性能・特性やらrequest_queueのマージやらI/Oスケジューラやらファイルシステムのレイアウトやらに左右されるので、readaheadは何をするとよくなり何をすると悪くなるかが見えにくい。
#参考サイト