先読み処理


先読みとは、page単位の実際の読込みサイズを拡大して読込む事で、ブロックデバイス登録でblk_alloc_queue_node()がコールされる際、BIOリストが作成されるrequest_queueq->backing_dev_info.ra_pagesに先読みサイズ最大値が設定されます。先読みサイズ最大値ra_pagesは、実読込みサイズ+先読みサイズで、実サイズを読み込んで、先読みサイズ分を読み込むのでなく、読み込み際は、実サイズ/読み込みサイズ関係なく、両者を合わせたサイズ値で読み込みます。

最大サイズのデフォルトはVM_MAX_READAHEAD=128で、page数(VM_MAX_READAHEAD * 1024) / PAGE_CACHE_SIZE=32 pageとなります。ブロックデバイススペシャルファイルのioctl()のBLKRASETで設定できます。この先読みサイズ情報が、ファイルを作成毎にstruct fileのf_ra.ra_pagesに設定されます。
#define VM_MAX_READAHEAD        128     /* kbytes */

struct file {
 :
       fmode_t                 f_mode;
       loff_t                  f_pos;
       struct fown_struct      f_owner;
       const struct cred       *f_cred;
       struct file_ra_state    f_ra;

       u64                     f_version;
 :
};

struct file_ra_state {
       pgoff_t start;                  /* where readahead started */
       unsigned int size;              /* # of readahead pages */
       unsigned int async_size;        /* do asynchronous readahead when
                                          there are only # of pages ahead */

       unsigned int ra_pages;          /* Maximum readahead window */
       unsigned int mmap_miss;         /* Cache miss stat for mmap accesses */
       loff_t prev_pos;                /* Cache last read() position */
};

struct request_queue *blk_alloc_queue_node(gfp_t gfp_mask, int node_id)
{
       struct request_queue *q;
       int err;

       q = kmem_cache_alloc_node(blk_requestq_cachep,
                               gfp_mask | __GFP_ZERO, node_id);
       if (!q)
               return NULL;

       q->id = ida_simple_get(&blk_queue_ida, 0, 0, GFP_KERNEL);
       if (q->id < 0)
               goto fail_q;

       q->backing_dev_info.ra_pages =
                       (VM_MAX_READAHEAD * 1024) / PAGE_CACHE_SIZE;
       q->backing_dev_info.state = 0;
       q->backing_dev_info.capabilities = BDI_CAP_MAP_COPY;
       q->backing_dev_info.name = "block";
       q->node = node_id;

       err = bdi_init(&q->backing_dev_info);
 :
       q->queue_lock = &q->__queue_lock;

       return q;

fail_id:
       ida_simple_remove(&blk_queue_ida, q->id);
fail_q:
       kmem_cache_free(blk_requestq_cachep, q);
       return NULL;
}

int blkdev_ioctl(struct block_device *bdev, fmode_t mode, unsigned cmd,
                       unsigned long arg)
{
       struct gendisk *disk = bdev->bd_disk;
       struct backing_dev_info *bdi;
       loff_t size;
       int ret, n;

       switch(cmd) {
       case BLKRAGET:
       case BLKFRAGET:
               if (!arg)
                       return -EINVAL;
               bdi = blk_get_backing_dev_info(bdev);
               if (bdi == NULL)
                       return -ENOTTY;
               return put_long(arg, (bdi->ra_pages * PAGE_CACHE_SIZE) / 512);
 :
       case BLKRASET:
       case BLKFRASET:
               if(!capable(CAP_SYS_ADMIN))
                       return -EACCES;
               bdi = blk_get_backing_dev_info(bdev);
               if (bdi == NULL)
                       return -ENOTTY;
               bdi->ra_pages = (arg * 512) / PAGE_CACHE_SIZE;
               return 0;
 :
       default:
               ret = __blkdev_driver_ioctl(bdev, mode, cmd, arg);
       }
       return ret;
}
ファイルの読込みはファイルオペレーションコールバックからdo_generic_file_read()がコールされ、mapping->page_treeのページキャッシュから読み込み済みのpageを取得し、pageが取得できない時page_cache_sync_readahead()を、先読みpageとして取得できた時でも、先読みのためpage_cache_async_readahead()がコールされます。
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;
               }
 :
               if (PageReadahead(page)) {
                       page_cache_async_readahead(mapping,
                                       ra, filp, page,
                                       index, last_index - index);
               }
 :
}
pageを取得できなかったケースで、実読込みサイズ+先読みサイズでの読み込みとなります。なお、ra->ra_pagesで先読みサイズが0なら先読みせずreturnとなり、復帰先でアドレススペースコールバックのis_partially_uptodateがコールされ、掛かるpageのみの読み込みとなります。

FMODE_RANDOMを設定されているとforce_page_cache_readahead()が、そうでないと第4引数をfalseでondemand_readahead()がコールされ、通常はondemand_readahead()の第4引数をfalseでコールされます。FMODE_RANDOMはブロックデバイスのioctr()で設定します。
void page_cache_sync_readahead(struct address_space *mapping,
                              struct file_ra_state *ra, struct file *filp,
                              pgoff_t offset, unsigned long req_size)
{
       /* no read-ahead */
       if (!ra->ra_pages)
               return;

       if (filp && (filp->f_mode & FMODE_RANDOM)) {
               force_page_cache_readahead(mapping, filp, offset, req_size);
               return;
       }

       ondemand_readahead(mapping, ra, filp, false, offset, req_size);
}
先読みpageからpageを取得したケースで、先読みサイズだけの読み込みとなります。この時、読み込めたpageがWriteback中なら、ioの競合を避けるため先読みしません。ondemand_readahead()の第4引数をtrueでコールされます。
void
page_cache_async_readahead(struct address_space *mapping,
                          struct file_ra_state *ra, struct file *filp,
                          struct page *page, pgoff_t offset,
                          unsigned long req_size)
{
       if (!ra->ra_pages)
               return;

       if (PageWriteback(page))
               return;

       ClearPageReadahead(page);

       if (bdi_read_congested(mapping->backing_dev_info))
               return;

       ondemand_readahead(mapping, ra, filp, true, offset, req_size);
}
ondemand_readahead()で実サイズ+先読みサイズを読み込みます。この時ファイル操作に依存した最適な読み込みサイズに更新します。

!offsetなら新規読み込みで、initial_readaheadでstruct file_ra_stateを初期化しての読み込みです。

offsetが実読み込みの終端(ra->start + ra->size - ra->async_size)/先読みの終端(ra->start + ra->size)なら、読み込み位置を終端(ra->start + ra->size)とし、サイズをget_next_ra_size(ra, max)、先読みだけの読み込み(ra->async_size = ra->size)となります。

上記の終端でない途中から取得した場合で、それが先読みpageだったらhit_readahead_marker=trueで、先読みだけの読み込み(ra->async_size = ra->size)となります。開始位置は読み込めた位置の次の空きのpage位置(まだ読み込んでいないpage)をradix_tree_next_hole()で取得し、ra->size = start - offsetは今回の処理でまだreadしていない先読みpage数です。それにdo_generic_file_readの読み込みpage数を加算し、get_next_ra_size()でra->sizeとします。そしてそのすべてをra->async_sizeとすることで、全領域を先読み領域とします。ここでの処理は読み込みpageは先読みpageだったため、より多くの先読みpageを読み込むようにすることです。

以降の処理は、pageが取得できなかったpage_cache_sync_readahead()でのコールに適用されます。読み込みpage数がra->ra_pagesより大きいとき/読み込み位置が前回読み込んだ位置より小さい場合(シーケンス的な読み込みでない)initial_readaheadで、struct file_ra_stateを初期化しなおしての読み込みです。

initial_readahead:はreq_sizeのサイズに依存し、ra->sizeはreq_size*2:req_size*4:ra->ra_pagesのどれかで、先読みサイズをra->async_size = ra->size - req_sizeとするstruct file_ra_stateとして初期化します。

if (offset == ra->start && ra->size == ra->async_size)は、ページキャッシュ内は全て先読みpageで、このpageを実pageとし、そのpageの2倍/4倍を先読みpageとします。これは読み込み位置が、実/先読みpageの境界、取得pageが先読みpageだった場合のケースです。
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)
{
       unsigned long max = max_sane_readahead(ra->ra_pages);

       if (!offset)
               goto initial_readahead;

       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);
               ra->async_size = ra->size;
               goto readit;
       }

       if (hit_readahead_marker) {
               pgoff_t start;

               rcu_read_lock();
               start = radix_tree_next_hole(&mapping->page_tree, offset+1,max);
               rcu_read_unlock();

               if (!start || start - offset > max)
                       return 0;

               ra->start = start;
               ra->size = start - offset;      /* old async_size */
               ra->size += req_size;
               ra->size = get_next_ra_size(ra, max);
               ra->async_size = ra->size;
               goto readit;
       }

       if (req_size > max)
               goto initial_readahead;

       if (offset - (ra->prev_pos >> PAGE_CACHE_SHIFT) <= 1UL)
               goto initial_readahead;

       if (try_context_readahead(mapping, ra, offset, req_size, max))
               goto readit;


       return __do_page_cache_readahead(mapping, filp, offset, req_size, 0);

initial_readahead:
       ra->start = offset;
       ra->size = get_init_ra_size(req_size, max);
       ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;

readit:
       if (offset == ra->start && ra->size == ra->async_size) {
               ra->async_size = get_next_ra_size(ra, max);
               ra->size += ra->async_size;
       }

       return ra_submit(ra, mapping, filp);
}

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)
{
       unsigned long max = max_sane_readahead(ra->ra_pages);

       if (!offset)
               goto initial_readahead;

       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);
               ra->async_size = ra->size;
               goto readit;
       }

       if (hit_readahead_marker) {
               pgoff_t start;

               rcu_read_lock();
               start = radix_tree_next_hole(&mapping->page_tree, offset+1,max);
               rcu_read_unlock();

               if (!start || start - offset > max)
                       return 0;

               ra->start = start;
               ra->size = start - offset;      /* old async_size */
               ra->size += req_size;
               ra->size = get_next_ra_size(ra, max);
               ra->async_size = ra->size;
               goto readit;
       }

       if (req_size > max)
               goto initial_readahead;

       if (offset - (ra->prev_pos >> PAGE_CACHE_SHIFT) <= 1UL)
               goto initial_readahead;

       if (try_context_readahead(mapping, ra, offset, req_size, max))
               goto readit;

       return __do_page_cache_readahead(mapping, filp, offset, req_size, 0);

initial_readahead:
       ra->start = offset;
       ra->size = get_init_ra_size(req_size, max);
       ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;

readit:
       if (offset == ra->start && ra->size == ra->async_size) {
               ra->async_size = get_next_ra_size(ra, max);
               ra->size += ra->async_size;
       }

       return ra_submit(ra, mapping, filp);
}

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;
}

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);
}
count_history_pages()はoffset前の空いているpageとoffset間のサイズを返します。!sizeと言うのは、直前のpageが空いている事で、このファイルはランダムファイルの可能性があります。

size >= offsetはスタートの0位置まで空きがなく、オーバアランドしてoffset以降で取得できた結果で、先頭から連続してoffsetまで読み込まれているということで、シーケンシャルファイルの可能性があります。この場合先読みサイズを拡大します。
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, ra, offset, max);

       if (!size)
               return 0;

       if (size >= offset)
               size *= 2;

       ra->start = offset;
       ra->size = get_init_ra_size(size + req_size, max);
       ra->async_size = ra->size;

       return 1;
}
radix_tree_prev_hole()でoffset - 1から前に向かってmax分、空きpageを検索します。検索する位置が先頭に達すると、radix-treeの終端からの検索となります。
static pgoff_t count_history_pages(struct address_space *mapping,
                                  struct file_ra_state *ra,
                                  pgoff_t offset, unsigned long max)
{
       pgoff_t head;

       rcu_read_lock();
       head = radix_tree_prev_hole(&mapping->page_tree, offset - 1, max);
       rcu_read_unlock();

       return offset - 1 - head;
}
__do_page_cache_readahead()は、ra->startからra->size分page数を読み込みます。この時ra->size - ra->async_size分のpageには、page->flagsにPG_readaheadが設定されます。
unsigned long ra_submit(struct file_ra_state *ra,
                      struct address_space *mapping, struct file *filp)
{
       int actual;

       actual = __do_page_cache_readahead(mapping, filp,
                                       ra->start, ra->size, ra->async_size);

       return actual;
}

補足

先読み処理は、実読み込みと先読み込み、漠然とそれぞれ独立した実装かと思っていましたが、IO読込みとしては、実読み込み/先読み込み関係なく、ra->sizeサイズ分読み込めばいいだけで、ra->sizeサイズをどれくらい拡大するか。という故だけの込み入った処理に過ぎません。要は以下のパターン等で如何にサイズ計算するかということです。

・ページキャッシュから取得できなかった。
・取得できたページキャッシュが先読みpageだった。
・読み込んだpageが実読み込み/先読みの最終位置だった。
・先頭位置の読み込みだった。
・読み込みサイズが先読み最大サイズより大きかった。
・読み込み位置が、前回読み込んだ位置より前だった。
・シーケンシャル読み込みだった。
・ランダム読み込みだった。

ramfs/sysfs等は、先読みする意味がないので(むしろマイナス効果)、q->backing_dev_info.ra_pages=0となります。
static struct backing_dev_info ramfs_backing_dev_info = {
       .name           = "ramfs",
       .ra_pages       = 0,    /* No readahead */
       .capabilities   = BDI_CAP_NO_ACCT_AND_WRITEBACK |
                         BDI_CAP_MAP_DIRECT | BDI_CAP_MAP_COPY |
                         BDI_CAP_READ_MAP | BDI_CAP_WRITE_MAP | BDI_CAP_EXEC_MAP,
};

static struct backing_dev_info sysfs_backing_dev_info = {
       .name           = "sysfs",
       .ra_pages       = 0,    /* No readahead */
       .capabilities   = BDI_CAP_NO_ACCT_AND_WRITEBACK,
};

最終更新 2014/12/28 23:54:22 - north
(2014/12/28 22:20:42 作成)


検索

アクセス数
3576132
最近のコメント
コアダンプファイル - sakaia
list_head構造体 - yocto_no_yomikata
勧告ロックと強制ロック - wataash
LKMからのファイル出力 - 重松 宏昌
kprobe - ななし
ksetの実装 - スーパーコピー
カーネルスレッドとは - ノース
カーネルスレッドとは - nbyst
asmlinkageってなに? - ノース
asmlinkageってなに? - よろしく
Adsense
広告情報が設定されていません。