[lkml]   [2006]   [May]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    Patch in this message
    Subject[RFC] kernel facilities for cache prefetching
    Pre-caching reloaded ;)

    I have been exploring cache prefetching on desktop systems for quite
    some time, and recently found ways that have _proven_ effects.

    The basic ideas are described in the following google soc proposal,
    with the proof-of-concept patch to support I/O priority attached.

    I'd like to know whether the two proposed kernel components would be
    acceptable for the mainline kernel, and any recommends to improve them.



    Rapid linux desktop startup through pre-caching


    KDE, Gnome, OpenOffice, and Firefox all take too long to start up.
    Boot time pre-caching seems to be the single most straightforward and
    effective way to improve it and make linux desktop experience more
    comfortable. It is a great pleasure for me to take up the work.


    I have been working on linux kernel readahead for over a year, and
    developed an adaptive readahead patch(
    to bring a bunch of new capabilities to linux. During the time I
    gained knowledge about the VM/IO subsystems of linux kernel, and get
    acquainted with the slow startup problem, the existing solutions, why
    they do no work as one would expect and how to get the job better done.


    There has been some similar efforts, i.e.
    - Linux: Boot Time Speedups Through Precaching
    - Andrew Morton's kernel module solution
    - preload - adaptive readahead daemon
    The formers are mainly kernel staffs, while the latter is a pure
    user-land solution. But none seems to do the trick for system startup
    time. Andrew saw ~10% speedup, while preload actually saw slow down.

    IMHO, Andrew's kernel module to dump the contents of pagecache and to
    restore it at boot time is one step towards the final solution.
    However, it takes one more step to actually win the time: to optimize
    the I/O on restoring time.


    How come the prefetcher gains little or even negative time?

    After some huntings in the source tree and some experiments,
    I came to the conclusions that

    1. the prefetcher has to readahead one file _after_ another, thus loses
    the opportunity to reorder the blocks and reduce seeking time.
    == reasoning ==
    It tends to be blocked on calling open(), where the kernel has to do
    some dir/inode/bmap lookups and do tiny I/Os _synchronously_ and with
    _locks_ held.

    2. the readahead I/O stands in the way of normal I/O, thus the prefetcher
    blocks normal apps and loses the opportunity to overlap CPU/IO time.
    == reasoning ==
    Support of I/O priority is still incomplete for linux. Of the three
    I/O elevators, anticipatory & deadline simply overlooks priority;
    CFQ is built for fair I/O priorities, though is still not enough for
    the case of readahead. Imagine that the prefetcher first issues an
    I/O request for page A with low priority, then comes the real app
    that needs page A, and simply waits on the page to be available,
    which will take rather long time because the elevator still thinks
    the page as a low priority one.

    So we get the amazing fact that prefetching actually slows things down!


    1) kernel facility to provide necessary I/O priority support
    - add basic I/O priority support to AS/deadline elevators:
    never have readahead I/O stand in the way of normal I/O
    - enable AS/CFQ/deadline to react on I/O priority changes:
    reschedule a previous readahead I/O that is now actually
    demanded by a legacy program

    2) kernel module to query the file cache
    - on loading: create /proc/filecache
    - setting up: echo "param value" > /proc/filecache
    - info query: cat /proc/filecache
    - sample sessions:

    # modprobe filecache
    $ cat /proc/filecache
    # file ALL
    # mask 0
    # ino size cached status refcnt name
    0 2929846 3181 D 1 /dev/hda1
    81455 9 9 _ 1 /sbin/init

    $ echo "file /dev/hda1" > /proc/filecache
    $ cat /proc/filecache
    # file /dev/hda1
    # mask 0
    # idx len
    0 24
    48 2
    53 5

    3) user-land tools to dump the current content of file cache,
    and to restore it on boot time
    - store as plain text files to be script/user friendly
    - be able to run on the very beginning of boot process
    - be able to trim down the cache records (for small systems)
    - optional poor man's defrag ;)
    - record and replay I/O for any task by taking two cache
    snapshots and do a set-substract

    A proof of concept implementation has been developed and ran on my
    desktop. According to the experimental results, the expected effect
    of the final work would be:
    - the power-on to login time remains roughly the same
    - most gui files are ready on login time
    - login to usable desktop time comes close to a warm startup


    I am currently pursuing PhD. degree in University of Science and
    Technology of China. I enjoy computing and GNU/Linux.

    - programming since 1993
    - using linux since 1998
    - playing PXE since 2000
    - developing OSS since 2004
    - developing adaptive readahead for linux since 2005

    block/deadline-iosched.c | 35 +++++++++++++++++++++++++++++++++++
    block/ll_rw_blk.c | 8 ++++++++
    fs/buffer.c | 5 +++--
    include/linux/elevator.h | 2 ++
    4 files changed, 48 insertions(+), 2 deletions(-)

    --- linux.orig/block/deadline-iosched.c
    +++ linux/block/deadline-iosched.c
    @@ -310,6 +310,40 @@ deadline_add_request(struct request_queu

    + * kick a page for io
    + */
    +static int
    +deadline_kick_page(struct request_queue *q, struct page *page)
    + struct deadline_data *dd = q->elevator->elevator_data;
    + struct deadline_rq *drq;
    + struct request *rq;
    + struct list_head *pos;
    + struct bio_vec *bvec;
    + struct bio *bio;
    + int i;
    + list_for_each(pos, &dd->fifo_list[READ]) {
    + drq = list_entry_fifo(pos);
    + rq = drq->request;
    + rq_for_each_bio(bio, rq) {
    + bio_for_each_segment(bvec, bio, i) {
    + if (page == bvec->bv_page)
    + goto found;
    + }
    + }
    + }
    + return -1;
    + rq->ioprio = 1;
    + list_del(&drq->fifo);
    + deadline_add_drq_fifo(dd, rq);
    + return 0;
    * remove rq from rbtree, fifo, and hash
    static void deadline_remove_request(request_queue_t *q, struct request *rq)
    @@ -784,6 +818,7 @@ static struct elevator_type iosched_dead
    .elevator_merge_req_fn = deadline_merged_requests,
    .elevator_dispatch_fn = deadline_dispatch_requests,
    .elevator_add_req_fn = deadline_add_request,
    + .elevator_kick_page_fn = deadline_kick_page,
    .elevator_queue_empty_fn = deadline_queue_empty,
    .elevator_former_req_fn = deadline_former_request,
    .elevator_latter_req_fn = deadline_latter_request,
    --- linux.orig/block/ll_rw_blk.c
    +++ linux/block/ll_rw_blk.c
    @@ -1620,6 +1620,14 @@ static void blk_backing_dev_unplug(struc
    request_queue_t *q = bdi->unplug_io_data;

    + if (page &&
    + IOPRIO_PRIO_CLASS(current->ioprio) != IOPRIO_CLASS_IDLE &&
    + q->elevator && q->elevator->ops->elevator_kick_page_fn) {
    + spin_lock_irq(q->queue_lock);
    + q->elevator->ops->elevator_kick_page_fn(q, page);
    + spin_unlock_irq(q->queue_lock);
    + }
    * devices don't necessarily have an ->unplug_fn defined
    --- linux.orig/fs/buffer.c
    +++ linux/fs/buffer.c
    @@ -63,8 +63,9 @@ static int sync_buffer(void *word)

    bd = bh->b_bdev;
    - if (bd)
    - blk_run_address_space(bd->bd_inode->i_mapping);
    + if (bd && bd->bd_inode && bd->bd_inode->i_mapping)
    + blk_run_backing_dev(bd->bd_inode->i_mapping->backing_dev_info,
    + bh->b_page);
    return 0;
    --- linux.orig/include/linux/elevator.h
    +++ linux/include/linux/elevator.h
    @@ -20,6 +20,7 @@ typedef int (elevator_set_req_fn) (reque
    typedef void (elevator_put_req_fn) (request_queue_t *, struct request *);
    typedef void (elevator_activate_req_fn) (request_queue_t *, struct request *);
    typedef void (elevator_deactivate_req_fn) (request_queue_t *, struct request *);
    +typedef int (elevator_kick_page_fn) (request_queue_t *, struct page *);

    typedef int (elevator_init_fn) (request_queue_t *, elevator_t *);
    typedef void (elevator_exit_fn) (elevator_t *);
    @@ -34,6 +35,7 @@ struct elevator_ops
    elevator_add_req_fn *elevator_add_req_fn;
    elevator_activate_req_fn *elevator_activate_req_fn;
    elevator_deactivate_req_fn *elevator_deactivate_req_fn;
    + elevator_kick_page_fn *elevator_kick_page_fn;

    elevator_queue_empty_fn *elevator_queue_empty_fn;
    elevator_completed_req_fn *elevator_completed_req_fn;
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at
     \ /
      Last update: 2006-05-02 09:53    [W:0.033 / U:10.576 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site