kernel facilities for cache prefetching
Subsystems (2)
RFC 1/1 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.
Thanks,
Wu
------------------------------------------------------------------------
SOC PROPOSAL
Rapid linux desktop startup through pre-caching
MOTIVATION
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.
QUALIFICATION
I have been working on linux kernel readahead for over a year, and developed an adaptive readahead patch(http://lwn.net/Articles/155510/) 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.
PREVIOUS WORKS
There has been some similar efforts, i.e.
- Linux: Boot Time Speedups Through Precaching
http://kerneltrap.org/node/2157
- Andrew Morton's kernel module solution
http://www.zip.com.au/~akpm/linux/fboot.tar.gz
- preload - adaptive readahead daemon
http://sourceforge.net/projects/preload
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.
I/O ANALYSE
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!
SCHEME/GOAL
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
BIO
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(-)
block/deadline-iosched.c +35 -0
@@ -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 ; + +found: + 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,
block/ll_rw_blk.c +8 -0
@@ -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 */
fs/buffer.c +3 -2
@@ -63,8 +63,9 @@ static int sync_buffer(void *word)smp_mb (); 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);io_schedule ();return 0 ; }
include/linux/elevator.h +2 -0
@@ -20,6 +20,7 @@ typedef int (elevator_set_req_fn) (requetypedef 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_opselevator_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;
Quoted 1 line · Wu Fengguang
2) kernel module to query the file cache
Can't mincore() + /proc/$PID/* stuff be used to replace that ? Improving boot time is nice and querying the file cache would work for that, but improving the boot time of some programs once the system is running (ie: running openoffice 6 hours after booting) is something that other preloaders do in other OSes aswell, querying the full file cache wouldn't be that useful for such cases.
The main reason why I believe that the pure userspace (preload.sf.net) solution slows down in some cases is becauses it uses bayesian heuristics (!) as a magic ball to guess the future, which is a flawed idea IMHO. I started (but didn't finish) a preloader which uses the process event connector to get notifications of what processes are being launched, then it profiles it (using mincore(), /proc/$PID/* stuff, etc) and preloads things optimally the next time it gets a notification of the same app.
Mac OS X has a program that implements your idea, available (the sources) at http://darwinsource.opendarwin.org/projects/apsl/BootCache-25/
Also, mac os x uses launchd, as init/init.d replacement
(http://darwinsource.opendarwin.org/projects/apsl/launchd-106/)
If (as Arjan noticed) the bootup is not really IO-bound, launchd could help to reduce the amount of CPU time wasted if the CPU time being wasted is in shell interpreters (a more unixy port has been done by the freebsd people - http://wikitest.freebsd.org/moin.cgi/launchd)
Diego,
Quoted 6 lines · Diego Calleja
Quoted 1 line · Wu Fengguang
2) kernel module to query the file cache
Can't
mincore()+/proc/$PID/*stuff be used to replace that ?
Nope. mincore() only provides info about files that are currently opened, by the process itself. The majority in the file cache are closed files.
Quoted 5 lines
Improving boot time is nice and querying the file cache would work for that, but improving the boot time of some programs once the system is running (ie: running openoffice 6 hours after booting) is something that other preloaders do in other OSes aswell, querying the full file cache wouldn't be that useful for such cases.
Yes, it can still be useful after booting :) One can get the cache footprint of any task started at any time by taking snapshots of the cache before and after the task, and do a set-subtract on them.
Quoted 8 lines
The main reason why I believe that the pure userspace (preload.sf.net) solution slows down in some cases is becauses it uses bayesian heuristics (!) as a magic ball to guess the future, which is a flawed idea IMHO. I started (but didn't finish) a preloader which uses the process event connector to get notifications of what processes are being launched, then it profiles it (using
mincore(),/proc/$PID/*stuff, etc) and preloads things optimally the next time it gets a notification of the same app.
My thought is that any prefetcher that ignores the thousands of small data files is incomplete. Only kernel can provide that info.
Quoted 2 lines
Mac OS X has a program that implements your idea, available (the sources) at http://darwinsource.opendarwin.org/projects/apsl/BootCache-25/
Ah, thanks for mentioning it.
It seems to do the job mostly in kernel, comprising of 2400+ LOC. Whereas my plan is to write a module of ~300 LOC to _only_ provide the necessary info, and leave other jobs to smart user-land tools.
Wu
Quoted 3 lines · Wu Fengguang
Nope.
mincore()only provides info about files that are currently opened, by the process itself. The majority in the file cache are closed files.
Yes; what I meant was:
- start listening the process event connector as firsk task on startup
- get a list of what files are being used (every second or something) by looking at /proc/$PID/* stuff
- mincore() all those files at the end of the bootup
Quoted 3 lines
Yes, it can still be useful after booting :) One can get the cache footprint of any task started at any time by taking snapshots of the cache before and after the task, and do a set-subtract on them.
Although this certainly looks simpler for userspace (and complete, if you want to get absolutely all the info about files that get opened and closed faster than the profile interval of a prefetcher)
(another useful tool would be a dtrace-like thing)
Quoted 10 lines · Diego Calleja
Quoted 3 lines
Nope.
mincore()only provides info about files that are currently opened, by the process itself. The majority in the file cache are closed files.Yes; what I meant was:
- start listening the process event connector as firsk task on startup
- get a list of what files are being used (every second or something) by looking at/proc/$PID/*stuff
-mincore()all those files at the end of the bootup
Quoted 7 lines
Quoted 3 lines
Yes, it can still be useful after booting :) One can get the cache footprint of any task started at any time by taking snapshots of the cache before and after the task, and do a set-subtract on them.
Although this certainly looks simpler for userspace (and complete, if you want to get absolutely all the info about files that get opened and closed faster than the profile interval of a prefetcher)
Thanks, so it's a question of simplicity/completeness :)
Quoted 1 line
(another useful tool would be a dtrace-like thing)
Lubos Lunak also reminds me of SUSE's preload
(http://en.opensuse.org/index.php?title=SUPER_preloading_internals)
which is a user-land solution using strace to collect the info.
And there's Andrea Arcangeli's "bootcache userspace logging" kernel patch(http://lkml.org/lkml/2004/8/6/216).
Wu
Quoted 6 lines · Wu Fengguang
Lubos Lunak also reminds me of SUSE's preload
(http://en.opensuse.org/index.php?title=SUPER_preloading_internals)
which is a user-land solution using strace to collect the info.And there's Andrea Arcangeli's "bootcache userspace logging" kernel patch(http://lkml.org/lkml/2004/8/6/216).
Just for completeness, windows vista will include a enhanced prefetcher called (sic) SuperFetch. The idea behind it seems to be to analyze I/O patterns and then "mirror" the most frequently used disk blocks into the USB flash drive; so if when the usb flash drive is plugged in the system will read those blocks from it as it was the hard drive the next time you run the app
(http://www.windowsitpro.com/Windows/Article/ArticleID/48085/48085.html)
Quoted 7 lines · Diego Calleja
Just for completeness, windows vista will include a enhanced prefetcher called (sic) SuperFetch. The idea behind it seems to be to analyze I/O patterns and then "mirror" the most frequently used disk blocks into the USB flash drive; so if when the usb flash drive is plugged in the system will read those blocks from it as it was the hard drive the next time you run the app
(http://www.windowsitpro.com/Windows/Article/ArticleID/48085/48085.html)
Linux should be able to do something like this using unionfs. It could be worthwhile to try it with one of the very fastest flash cards or USB drives.
With slower cards and USB keys its more of a loss unless the faster seek speed can make up for it, because sequential hard drive access is faster.
For comparison, a OCZ USB 2.0 Flash Drive with dual channel works at about 30 MB/s. One of my 7,200 RPM SATA desktop drives does 45 MB/s. A 15k SCSI drive can do over 60 MB/s.
It'd be great for laptops though. My slug of a laptop drive does 20 MB/s on a good day.
Signature · 1 line
Zan Lynx <[email protected]>
Quoted 3 lines · Zan Lynx
Linux should be able to do something like this using unionfs. It could be worthwhile to try it with one of the very fastest flash cards or USB drives.
BTW; I forgot that the next intel laptops (and apparently, mactel laptops) will have a small flash memory built in for this very purpose. According to an article at extremetech.com, the flash memory requires an "I/O controller"; IOW, it is not transparent and seems to need support from the OS (although I guess that vista's "superprefetch" was designed precisely for this hardware). Apparently, the main purpose here is to improve the battery life (disks seeking for too many seconds can eat lot of power, I guess). "Prefetchers" are becoming trendy, it seems
(page 14) http://www.intel.com/pressroom/kits/events/idfspr_2006/20060307_MaloneyTranscript.pdf
Quoted 3 lines
With slower cards and USB keys its more of a loss unless the faster seek speed can make up for it, because sequential hard drive access is faster.
That's where the gain is; if the hard drive access was sequential people wouldn't be talking about prefetchers. My SATA desktop drive also does ~45 MB/s, but it doesn't goes beyond 2 when seeking
Quoted 6 lines · Wu Fengguang
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(-)
Now, regardless of the other issues people have brought up, I'd like to say that I think this is broken.
Doing prefetching on a physical block basis is simply not a valid approach, for several reasons:
- it misses several important cases (you can surely prefetch over NFS too)
- it gives you only a very limited view into what is actually going on.
- it doesn't much allow you to _fix_ any problems, it just allows you to try to paper them over.
- it's useless anyway, since pretty all kernel caching is based on virtual caches, so if you "pre-read" the physical buffers, it won't
help: you'll just waste time reading the data into a buffer that will never be used, and when the real request comes in, the read will be done _again_.
So I would _seriously_ claim that the place to do all the statistics allocation is in anything that ends up having to call "->readpage()", and do it all on a virtual mapping level.
Yes, it isn't perfect either (I'll mention some problems), but it's a _lot_ better. It means that when you gather the statistics, you can see the actual _files_ and offsets being touched. You can even get the filenames by following the address space -> inode -> i_dentry list.
This is important for several reasons:
(a) it makes it a hell of a lot more readable, and the user gets a lot more information that may make him see the higher-level issues involved.
(b) it's in the form that we cache things, so if you read-ahead in that form, you'll actually get real information.
(c) it's in a form where you can actually _do_ something about things like fragmentation etc ("Oh, I could move these files all to a separate area")
Now, admittedly it has a few downsides:
- right now "readpage()" is called in several places, and you'd have to create some kind of nice wrapper for the most common "mapping->a_ops->readpage()" thing and hook into there to avoid duplicating the effort.
Alternatively, you could decide that you only want to do this at the filesystem level, which actually simplifies some things. If you instrument "mpage_readpage[2]()", you'll already get several of the ones you care about, and you could do the others individually.
[ As a third alternative, you might decide that the only thing you actually care about is when you have to wait on a locked page, and instrument the page wait-queues instead. ]
- it will miss any situation where a filesystem does a read some other way. Notably, in many loads, the _directory_ accesses are the important ones, and if you want statistics for those you'd often have to do that separately (not always - some of the filesystems just use the same page reading stuff).
The downsides basically boil down to the fact that it's not as clearly just one single point. You can't just look at the request queue and see what physical requests go out.
NOTE! You can obviously do both, and try to correlate one against the other, and you'd get the best possible information ("is this seek because we started reading another file, or is it because the file itself is fragmented" kind of stuff). So physical statistics aren't meaningless. They're just _less_ important than the virtual ones, and you should do them only if you already do virtual stats.
Linus
Quoted 4 lines · Linus Torvalds
The downsides basically boil down to the fact that it's not as clearly just one single point. You can't just look at the request queue and see what physical requests go out.
The other problem is that readpages has no idea about the layout of the disk so just doing it dumbly might end up with a lot of seeking.
I suppose you would at least need some tweaks to the scheduler to make sure it doesn't give these reads any priority and keeps them in the queue long enough to get real good sorting and large requests.
Problem is that this would likely need to be asynchronous to be any useful unless you were willing to block a thread for a potentially long time for each file to be prefetched.
-Andi
Quoted 2 lines · Linus Torvalds
Doing prefetching on a physical block basis is simply not a valid approach, for several reasons:
Sorry!
I made a misleading introduction. I'll try to explain it in more detail.
DATA ACQUISITION
/proc/filecache provides an interface to query the cached pages of any file. This information is expressed in tuples of <idx, len>, which more specifically means <mapping-offset, pages>.
Normally one should use 'echo' to setup two parameters before doing 'cat':
@file
the filename;
use 'ALL' to get a list all files cached
@mask
only show the pages with non-zero (page-flags & @mask); for simplicity, use '0' to show all present pages(take 0 as ~0)
Normally, one should first get the file list using param 'file ALL', and then iterate through all the files and pages of interested with params 'file filename' and 'mask pagemask'.
The param 'mask' acts as a filter for different users: it allows sysadms to know where his memory goes, and the prefetcher to ignore pages from false readahead.
One can use 'mask hex(PG_active|PG_referenced|PG_mapped)' in its hex form to show only accessed pages(here PG_mapped is a faked flag), and use 'mask hex(PG_dirty)' to show only dirtied pages.
One can use
$ echo "file /sbin/init" > /proc/filecache
$ echo "mask 0" > /proc/filecache
$ cat /proc/filecache
to get an idea which pages of /sbin/init are currently cached.In the proposal, I used the following example, which is proved to be rather misleading:
$ echo "file /dev/hda1" > /proc/filecache
$ cat /proc/filecache
The intention of that example was to show that filesystem dir/inode
buffer status -- which is the key data for user-land pre-caching --
can also be retrieved through this interface.So the proposed solution is to
- prefetch normal files on the virtual mapping level
- prefetch fs dir/inode buffers on a physical block basis
I/O SUBMISSION
How can we avoid unnecessary seeks when prefetching on virtual mapping level? The answer is to leave this job to i/o elevators. What we should do is to present elevators with most readahead requests before too many requests being submitted to disk drivers.
The proposed scheme is to:
1) (first things first)
issue all readahead requests for filesystem buffers
2) (in background, often blocked)
issue all readahead requests for normal files
-) make sure the above requests are of really _low_ priority
3) regular system boot continues
4) promote the priority of any request that is now demanded by legacy programs
In the scheme, most work is done by user-land tools. The required kernel support is minimal and general-purpose:
- an /proc/filecache interface
- the ability to promote I/O priority on demanded pages
By this approach, we avoided the complicated OSX bootcache solution, which is a physical-blocks-based, special-handlings-in-kernel solution that is exactly what Linus is against.
Thanks,
Wu
Quoted 9 lines · Linus Torvalds
So I would _seriously_ claim that the place to do all the statistics allocation is in anything that ends up having to call "->readpage()", and do it all on a virtual mapping level.
Yes, it isn't perfect either (I'll mention some problems), but it's a _lot_ better. It means that when you gather the statistics, you can see the actual _files_ and offsets being touched. You can even get the filenames by following the address space -> inode ->
i_dentrylist.
Quoted 9 lines
This is important for several reasons:
(a) it makes it a hell of a lot more readable, and the user gets a lot more information that may make him see the higher-level issues involved.
(b) it's in the form that we cache things, so if you read-ahead in that form, you'll actually get real information.
(c) it's in a form where you can actually _do_ something about things like fragmentation etc ("Oh, I could move these files all to a separate area")
There have been two alternatives for me:
1) static/passive interface i.e. the /proc/filecache querier
- user-land tools request to dump the cache contents on demand
2) dynamic/active interface i.e. the readpage() logger
- user-land daemon accepts live page access/io activities
Quoted 22 lines
Now, admittedly it has a few downsides:
- right now "
readpage()" is called in several places, and you'd have to create some kind of nice wrapper for the most common "mapping->a_ops->readpage()" thing and hook into there to avoid duplicating the effort.Alternatively, you could decide that you only want to do this at the filesystem level, which actually simplifies some things. If you instrument "mpage_readpage[2]()", you'll already get several of the ones you care about, and you could do the others individually.
[ As a third alternative, you might decide that the only thing you actually care about is when you have to wait on a locked page, and instrument the page wait-queues instead. ]
- it will miss any situation where a filesystem does a read some other way. Notably, in many loads, the _directory_ accesses are the important ones, and if you want statistics for those you'd often have to do that separately (not always - some of the filesystems just use the same page reading stuff).
Quoted 3 lines
The downsides basically boil down to the fact that it's not as clearly just one single point. You can't just look at the request queue and see what physical requests go out.
Good insights.
The readpage() activities logging idea has been appealing for me. We might even go further to log mark_page_accessed() calls for more information.
This approach is more precise, and provides process/page correlations and time info that the /proc/filecache interface cannot provide. Though it involves more complexity and overhead(for me they mean the possibility of being rejected:).
Wu
Quoted 1 line · Linus Torvalds
[...]
Quoted 17 lines
Now, admittedly it has a few downsides:
- right now "
readpage()" is called in several places, and you'd have to create some kind of nice wrapper for the most common "mapping->a_ops->readpage()" thing and hook into there to avoid duplicating the effort.Alternatively, you could decide that you only want to do this at the filesystem level, which actually simplifies some things. If you instrument "mpage_readpage[2]()", you'll already get several of the ones you care about, and you could do the others individually.
[ As a third alternative, you might decide that the only thing you actually care about is when you have to wait on a locked page, and instrument the page wait-queues instead. ]
Quoted 5 lines
- it will miss any situation where a filesystem does a read some other way. Notably, in many loads, the _directory_ accesses are the important ones, and if you want statistics for those you'd often have to do that separately (not always - some of the filesystems just use the same page reading stuff).
Another disadvantage is that ->readpage() can only do read-ahead within single file, which is not helpful for the case of reading a lot of small files (and this is what happens during startup).
And to implement reasonable multi-file read-ahead at the file system layer one needs asynchronous inode loading interface implemented for every file system.
Nikita.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 67 lines · Wu Fengguang
Quoted 2 lines · Linus Torvalds
Doing prefetching on a physical block basis is simply not a valid approach, for several reasons:
Sorry!
I made a misleading introduction. I'll try to explain it in more detail.DATA ACQUISITION
/proc/filecacheprovides an interface to query the cached pages of any file. This information is expressed in tuples of <idx, len>, which more specifically means <mapping-offset, pages>.Normally one should use 'echo' to setup two parameters before doing 'cat':
@file
the filename;
use 'ALL' to get a list all files cached
@mask
only show the pages with non-zero (page-flags & @mask); for simplicity, use '0' to show all present pages(take 0 as ~0)Normally, one should first get the file list using param 'file ALL', and then iterate through all the files and pages of interested with params 'file filename' and 'mask pagemask'.
The param 'mask' acts as a filter for different users: it allows sysadms to know where his memory goes, and the prefetcher to ignore pages from false readahead.
One can use 'mask
hex(PG_active|PG_referenced|PG_mapped)' in its hex form to show only accessedpages(here PG_mapped is a faked flag), and use 'maskhex(PG_dirty)' to show only dirtied pages.One can use
$ echo "file /sbin/init" > /proc/filecache $ echo "mask 0" > /proc/filecache $ cat /proc/filecache to get an idea which pages of /sbin/init are currently cached.In the proposal, I used the following example, which is proved to be rather misleading:
$ echo "file /dev/hda1" > /proc/filecache $ cat /proc/filecache The intention of that example was to show that filesystem dir/inode buffer status -- which is the key data for user-land pre-caching -- can also be retrieved through this interface.So the proposed solution is to
- prefetch normal files on the virtual mapping level
- prefetch fs dir/inode buffers on a physical block basisI/O SUBMISSION
How can we avoid unnecessary seeks when prefetching on virtual mapping level? The answer is to leave this job to i/o elevators. What we should do is to present elevators with most readahead requests before too many requests being submitted to disk drivers.
The proposed scheme is to:
1) (first things first)
issue all readahead requests for filesystem buffers
2) (in background, often blocked)
issue all readahead requests for normal files
-) make sure the above requests are of really _low_ priority
3) regular system boot continues
4) promote the priority of any request that is now demanded by legacy programs
Quoted 8 lines
In the scheme, most work is done by user-land tools. The required kernel support is minimal and general-purpose:
- an/proc/filecacheinterface
- the ability to promote I/O priority on demanded pagesBy this approach, we avoided the complicated OSX bootcache solution, which is a physical-blocks-based, special-handlings-in-kernel solution that is exactly what Linus is against.
Wu,
While ago, I hacked up similar /proc interface
echo "<filesystem-name>" > /proc/pagecache-usage
Which showed pagecache usage of every file in that filesystem (filename, #num pages). My main objective was to shoot down pagecache for all the files in a given filesystem. I ended up using it to do posix_fadivse(POSIX_FADV_DONTNEED) on those files. (Initially, tried to do this without this, by doing fadvise() on all files in the filesystem - but ended up bloating up inode and dcache).
Yeah. having this kind of information would be useful. But I am not sure how much of this can benefit regular workloads - unless one is willing to tweak things heavily. Bottom line is, need to have a better strategy on how you would use information ..
Thanks,
Badari
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 12 lines · Wu Fengguang
Quoted 9 lines · Badari Pulavarty
While ago, I hacked up similar /proc interface
echo "<filesystem-name>" >/proc/pagecache-usageWhich showed pagecache usage of every file in that filesystem (filename, #num pages). My main objective was to shoot down pagecache for all the files in a given filesystem. I ended up using it to do
posix_fadivse(POSIX_FADV_DONTNEED)on those files. (Initially, tried to do this without this, by doingfadvise()on all files in the filesystem - but ended up bloating up inode and dcache).
Quoted 2 lines
Ah, I have not thought of the possibility of querying the page cache just to drop some caches -- a subset of
sysctl_drop_cachesfunctions.
Actually, I did something even simpler for a totally one-off thing: you don't actually even need to drop caches or track pretty much anything, it's sufficient for most analysis to just have a timestamp on each page cache, and then have some way to read out the current cached contents.
You can then use the timestamps to get a pretty good idea of what order things happened in.
You'll lose the temporary file information (files that are created and deleted), because deleting a file will also flush the page cache for it, but temporary files tend to not be hugely interesting.
The really nice thing was that you don't even have to set the timestamp in any complex place: you do it at page _allocation_ time. That automatically gets the right answer for any page cache page, and you can do it in a single place.
Linus
Quoted 25 lines · Linus Torvalds
Quoted 12 lines · Wu Fengguang
Quoted 9 lines · Badari Pulavarty
While ago, I hacked up similar /proc interface
echo "<filesystem-name>" >/proc/pagecache-usageWhich showed pagecache usage of every file in that filesystem (filename, #num pages). My main objective was to shoot down pagecache for all the files in a given filesystem. I ended up using it to do
posix_fadivse(POSIX_FADV_DONTNEED)on those files. (Initially, tried to do this without this, by doingfadvise()on all files in the filesystem - but ended up bloating up inode and dcache).Quoted 2 lines
Ah, I have not thought of the possibility of querying the page cache just to drop some caches -- a subset of
sysctl_drop_cachesfunctions.Actually, I did something even simpler for a totally one-off thing: you don't actually even need to drop caches or track pretty much anything, it's sufficient for most analysis to just have a timestamp on each page cache, and then have some way to read out the current cached contents.
You can then use the timestamps to get a pretty good idea of what order things happened in.
Quoted 8 lines
You'll lose the temporary file information (files that are created and deleted), because deleting a file will also flush the page cache for it, but temporary files tend to not be hugely interesting.
The really nice thing was that you don't even have to set the timestamp in any complex place: you do it at page _allocation_ time. That automatically gets the right answer for any page cache page, and you can do it in a single place.
Sounds like an interesting idea.
The problem, I was trying to address was that - one of our large database customer was complaining about the variation (degradation) in database performance when other applications like backup, ftp, scp, tar happening on other filesystems on the system. VM end up swapping out some of database process data to make room for these read/writes.
They wanted a way to completely flush out pagecache data for a given filesystem to see if it improves their situation. (although "swapiness" should in *theory* do the same thing). In fact, they want a way to control the amount of pagecache filesystems populate through /proc :(
My patch was an initial attempt to unwind mysteries of VM behaviour :) (VM may doing the right thing from kernel perspective - but customer was complaining that its thrashing their workload).
Thanks,
Badari
Quoted 5 lines · Linus Torvalds
Actually, I did something even simpler for a totally one-off thing: you don't actually even need to drop caches or track pretty much anything, it's sufficient for most analysis to just have a timestamp on each page cache, and then have some way to read out the current cached contents.
Quoted 7 lines
You can then use the timestamps to get a pretty good idea of what order things happened in.
The really nice thing was that you don't even have to set the timestamp in any complex place: you do it at page _allocation_ time. That automatically gets the right answer for any page cache page, and you can do it in a single place.
Looks nice. A detailed scheme might be:
1) ctime/atime for each radixtree node(or, cluser of pages) It seems to be a good accuracy/overhead compromise. And is perfect for the most common case of sequential accesses.
struct radix_tree_node {
+ unsigned long ctime, atime;
}
radix_tree_node_alloc()
{
+ node->ctime = some_virtual_time();
}
radix_tree_lookup_slot()
{
+ node->atime = some_virtual_time();
}
2) eviction-time for each recently evicted page
Store eviction-time _in place_ in the slot that used to store the page's address, with minimal space/time impact.
+#define SLOT_IS_EVICTION_TIME 1radix_tree_delete()
{
- pathp->node->slots[pathp->offset] = NULL;
+ pathp->node->slots[pathp->offset] =
+ some_virtual_time() | SLOT_IS_EVICTION_TIME;
}
Regards,
Wu
Quoted 8 lines · Linus Torvalds
Now, regardless of the other issues people have brought up, I'd like to say that I think this is broken.
Doing prefetching on a physical block basis is simply not a valid approach, for several reasons:
- it misses several important cases (you can surely prefetch over NFS too)
---
I don't think fetching over a network is a case that needs
to be "optimized". I don't think any there would be sufficient gain in "pre-fetching" over a network (even if it was one long network read) to outweigh network latencies. I would strongly suggest this be ignored.
Quoted 1 line
- it gives you only a very limited view into what is actually going on.
---
??? In what way? I don't think we need a *complex* view of what
is going on. If anything, complexity can be a performance drag (though in some cases, an excellent algorithm can outweigh the extra computational complexitiy.
Quoted 2 lines
- it doesn't much allow you to _fix_ any problems, it just allows you to try to paper them over.
----
It isn't designed to be the one "true" fix for every problem known.
It's meant to provide speedups for a common subset of io-requests.
If one comes up with the one-uber algorithm in three years, then
replace this one, meanwhile...
Quoted 5 lines
- it's useless anyway, since pretty all kernel caching is based on virtual caches, so if you "pre-read" the physical buffers, it won't
help: you'll just waste time reading the data into a buffer that will never be used, and when the real request comes in, the read will be done _again_.
----
This is the big drawback/problem. But this leads me to an obvious
question. If I read a file into memory, it is cached, _seemingly_, relative to the filename. If I read the the same physical block into memory using _block_-i/o, relative to the device, the claim is that two separate reads are done into the block cache? Can't this result in inconsistent results between the two copies? If I change the file relative block, how is this coordinated with the device-relative block? Surely there is some block coelescing done at some point to ensure the two different views of the block are consistent?
If not, I'd tend to view this as a "bug".
But presuming this is "dealt with" at some layer, can't the
same information used to merge the two blocks be used to identify that the same block is already in memory?
If file-blockno, addresses can't be converted to device-blockno's,
how can the blocks be written to disk?
If the file-blockno's are convertable, can't this be used to
compare which physical blocks are already in the cache? Certainly this would be faster than the milliseconds it could take to do another physial read, no?
Quoted 3 lines
(a) it makes it a hell of a lot more readable, and the user gets a lot more information that may make him see the higher-level issues involved.
---
I'm not sure this is a benefit that outweight the elimination of
having to go through the file system (following directory chains, indirect blocks, extents, etc).
Quoted 2 lines
(b) it's in the form that we cache things, so if you read-ahead in that form, you'll actually get real information.
----
This may not be a great reason. Using the fact that "this is the
way things are already done", may not allow optimal implementation of faster algorithms.
Quoted 3 lines
(c) it's in a form where you can actually _do_ something about things like fragmentation etc ("Oh, I could move these files all to a separate area")
----
This could theoretically be done solely on a block basis. While
file pointers would have to be updated to point to "out-of-sequence" blocks, it might be more optimal to store _some_ files discontiguously in order to pack the desired blocks into a (relatively) "small" area that can be read into memory in some minimal number of physical i/o requests.
Quoted 5 lines
- it will miss any situation where a filesystem does a read some other way. Notably, in many loads, the _directory_ accesses are the important ones, and if you want statistics for those you'd often have to do that separately (not always - some of the filesystems just use the same page reading stuff).
---
Recording physical block reads could automatically include this
situation.
Quoted 4 lines
The downsides basically boil down to the fact that it's not as clearly just one single point. You can't just look at the request queue and see what physical requests go out.
---
You also have the downside of having to go through the file-system
and following each path and file-chain in order to read a potentially discontiguous section of a file. It also, _seemingly_, has the downside of reading in "entire files" when only subsections of files may be needed on startup.
Quoted 7 lines
NOTE! You can obviously do both, and try to correlate one against the other, and you'd get the best possible information ("is this seek because we started reading another file, or is it because the file itself is fragmented" kind of stuff). So physical statistics aren't meaningless. They're just _less_ important than the virtual ones, and you should do them only if you already do virtual stats.
---
Sounds like you might need to have 2 sets of "addresses" / block:
file relative block addresses, and device relative block addresses.
-l
Quoted 5 lines · Linda Walsh
Quoted 2 lines
- it gives you only a very limited view into what is actually going on.
??? In what way? I don't think we need a *complex* view of what
is going on.
The block-based view is a very simple one, but it's _too_ simple. It doesn't actually tell the user what is happening. It doesn't tell you why the request happened in the first place, so it leaves you no way to really do anything sane about it.
You can't prefetch (because the indexing is wrong), and you can't actually even analyze it (because you don't know any background to what you're seeing). In short, you can't _do_ anything with it.
Linus
Quoted 7 lines · Linus Torvalds
Quoted 5 lines · Linda Walsh
Quoted 2 lines
- it gives you only a very limited view into what is actually going
on.??? In what way? I don't think we need a *complex* view of what
is going on.
Quoted 8 lines
The block-based view is a very simple one, but it's _too_ simple. It doesn't actually tell the user what is happening. It doesn't tell you why the request happened in the first place, so it leaves you no way to really do anything sane about it.
You can't prefetch (because the indexing is wrong), and you can't actually even analyze it (because you don't know any background to what you're seeing). In short, you can't _do_ anything with it.
Please forgive me if I'm dumb, but what about the following reasoning:
The user as such (the person just *using* the computer) won't do anything with "program xyz uses block a, b, and c.".
But it wouldn't help much if he was told "program xyz uses files a, b, and d." That's a task for package maintainers and distributions to optimize the *number* of accesses.
So the simple information which block numbers we need would not benefit the users (or the distribution developers), but it's enough for caching things:
Ascending block numbers on disk can be read very fast, as the disk needs no or less seeking. That's even true for stripes and mirrors. (I grant you that there are complicated setups out there, but these could be handled similar.)
If we know which blocks are read (directories, inodes, data), an early userspace application (possibly even from initrd) could
- read these blocks into a ramdisk device (linearly),
- define a device mapper as a mirror of
- the original root partition,
- and a sparse device composed from parts of the ramdisk, interleaved by non-existing (error-producing) ranges, and
- setup the device mapper as a root device.
- In a specified point at startup the mapping device gets set to just a linear interpretation of the root partition, and the ramdisk gets discarded.
Example:
--------
N specifies a needed block, the numbers other blocks.
Harddisk: 1 2 3 N N N 7 8 N 10 N 12 13 14 N 16 N ... RAM-Disk contains 4 5 6 9 11 15 17
The mirror set would look like this,
with E representing an error-returning block:
Harddisk: 1 2 3 N N N 7 8 N 10 N 12 13 14 N 16 N ...
mapped from RAM-Disk: E E E 4 5 6 E E 9 E 11 E E E 15 E 17 ...
Advantages:
- As long as there's a good chance that the needed blocks are read from the ramdisk (which was filled linearly, with 20-60MB/sec as reported by others), *all* disk-access times (inodes, directories, data) should be nearly zero. Of course, there will be blocks which have now to be read which weren't needed the last boot, which will have to be taken from the harddisk, but the majority should be taken from the ramdisk.
Problems:
- We'd need to define a priority in the mirror set, so that *everything* possible is taken from the ramdisk
- There has to be a way to *not* disable the ram-disk when an error-block is read.
That's completely doable in userspace (except for knowing which blocks have to be read), and doesn't sound like much overhead to me.
Suggestions, ideas?
Does that work? Does it not?
Regards,
Phil
Quoted 6 lines
Ascending block numbers on disk can be read very fast, as the disk needs no or less seeking. That's even true for stripes and mirrors. (I grant you that there are complicated setups out there, but these could be handled similar.)
btw this all really spells out that you may want to do this as a device mapper thing; eg have a device mapper module that can do "lookaside" to a different order/mirror block whatever. The filesystem just doesn't want to know; do it at the DM level ;) That also solves the entire caching layering problem etc ;)
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 9 lines · Wu Fengguang
Quoted 8 lines · Arjan van de Ven
Quoted 6 lines
Ascending block numbers on disk can be read very fast, as the disk needs no or less seeking. That's even true for stripes and mirrors. (I grant you that there are complicated setups out there, but these could be handled similar.)
Quoted 8 lines
Quoted 5 lines
btw this all really spells out that you may want to do this as a device mapper thing; eg have a device mapper module that can do "lookaside" to a different order/mirror block whatever. The filesystem just doesn't want to know; do it at the DM level ;) That also solves the entire caching layering problem etc ;)
I guess some big corps might want to install such a layer into their storage products ;)
maybe, could be.
Doing it at this level also has the advantage that fs metadata becomes seek free as well; since that is mostly fixed-location inside the fs, reordering that on an fs-level is really hard.. on a dm level.. easy.
Quoted 8 lines · Arjan van de Ven
Quoted 6 lines
Ascending block numbers on disk can be read very fast, as the disk needs no or less seeking. That's even true for stripes and mirrors. (I grant you that there are complicated setups out there, but these could be handled similar.)
Quoted 5 lines
btw this all really spells out that you may want to do this as a device mapper thing; eg have a device mapper module that can do "lookaside" to a different order/mirror block whatever. The filesystem just doesn't want to know; do it at the DM level ;) That also solves the entire caching layering problem etc ;)
I guess some big corps might want to install such a layer into their storage products ;)
Quoted 7 lines · Linus Torvalds
Quoted 2 lines · Wu Fengguang
4 files changed, 48 insertions(+), 2 deletions(-)So I would _seriously_ claim that the place to do all the statistics allocation is in anything that ends up having to call "->readpage()", and do it all on a virtual mapping level.
Why not simply read everything in a whole file at a time at boot time, while we still have enough free memory ?
We can have a small modification to the readahead code to read in the whole file on the first read or fault, or maybe even on open.
Once the system is done booting, it can switch this bootup readahead mode off through a tunable in /proc. If the system is booting on a system with not enough memory to load everything file-at-a-time, the bootup scripts can switch this off earlier (or not switch it on).
The kernel modifications needed to make this work are minimal. It might need some tweaking so we don't try to read in truly enormous files, but that is easy.
Does this sound reasonable ?
Signature · 1 line
All Rights Reversed
Quoted 2 lines · Rik van Riel
Why not simply read everything in a whole file at a time at boot time, while we still have enough free memory ?
Sure it helps, though may be unnecessary once we can rely on userspace pre-caching tools to do it in a more accurate and efficient way.
The main concern would be inter-file/inter-buffer readahead. I have some data to support it:
% wc -l hda* startup.files
1743 hda2_buffers <== my /
335 hda3_buffers <== my /home
1130 startup.files
3208 total
The above cache sizes sum up to ~110MB, so it's about 36KB per seek.
Thanks,
Wu
Quoted 4 lines · Wu Fengguang
Pre-caching reloaded ;)
I/O ANALYSE...
SCHEME/GOAL(s)...
Some good analysis and ideas. I don't know if it is wanted, but I'd
like to add a 'few cents' referring to the pre-fetch mechanism in XP, which addresses both boot and application prefetch and has the benefit of showing measurable performance improvements (compare the boot time of an NT4 system to XP; maybe a 5-8x performance boost?).
1. As you mention; reading files "sequentially" through the file
system is "bad" for several reasons. Areas of interest:
a) don't go through the file system. Don't waste time doing
directory lookups and following file-allocation maps; Instead, use raw-disk i/o and read sectors in using device & block number.
b) Be "dynamic"; "Trace" (record (dev&blockno/range) blocks
starting ASAP after system boot and continuing for some "configurable" number of seconds past reaching the desired "run-level" (coinciding with initial disk quiescence). Save as "configurable" (~6-8?) number of traces to allow finding the common initial subset of blocks needed.
c) Allow specification of max# of blocks and max number of "sections"
(discontiguous areas on disk);
d) "Ideally", would have a way to "defrag" the common set of blocks.
I.e. -- moving the needed blocks from potentially disparate areas of files into 1 or 2 contiguous areas, hopefully near the beginning of the disk (or partition(s)).
That's the area of "boot" pre-caching.
Next is doing something similar for "application" starts. Start tracing when an application is loaded & observe what blocks are requested for that app for the first 20 ("configurable") seconds of execution. Store traces on a per-application basis. Again, it would be ideal if the different files (blocks, really), needed by an application could be grouped so that sequentially needed disk-blocks are stored sequentially on disk (this _could_ imply the containing files are not contiguous).
Essentially, one wants to do for applications, the same thing one does for booting. On small applications, the benefit would likely be negligible, but on loading a large app like a windowing system, IDE, or database app, multiple configuration files could be read into the cache in one large read.
That's "application" pre-caching.
A third area -- that can't be easily done in the kernel, but would
require a higher skill level on the part of application and library
developers, is to move towards using "delay-loaded" libraries. In
Windows, it seems common among system libraries to use this feature. An obvious benefit -- if certain features of a program are not used, the associated libraries are never loaded. Not loading unneeded parts
of a program should speed up initial application load time, significantly.
I don't know where the "cross-over" point is, but moving to demand
loaded "so's" can cause extreme benefits for interactive usage. In addition to load-time benefits, additional benefits are gained by not wasting memory on unused libraries and program features.
In looking at the distro I use, many unused libraries are linked in
with commonly used programs. For a small office or home setup, I rarely have a need for LDAP, internationalized libraries, & application support for virtually any hardware & software configuration.
This isn't a kernel problem -- the kernel has dynamically loadable
modules to allow loading only of hardware & software drivers that are needed in a particular kernel. User applications that I have been exposed to in Linux usually don't have this adaptability -- virtually everything is loaded at execution time -- not as needed during program execution.
I've seen this feature used on Unix systems to dynamically present
feature interfaces depending on the user's software configuration. On linux, I more often see a "everything, including the kitchen sink" approach, where every possible software configuration is supported via "static", shared libraries that must be present and loaded into memory before the program begins execution.
This has the potential to have a greater benefit as the application
environment becomes more complex if you think about how the number of statically loaded, sharable libraries have increased (have seen addition of ldap, pam, and most recently, selinux libraries that are required for loading before application execution).
Good luck in speeding these things up. It might require some
level of cooperation in different areas (kernel, fs utils, distro-configuration, application design and build...etc).
-linda
Quoted 5 lines · Linda Walsh
1. As you mention; reading files "sequentially" through the file
system is "bad" for several reasons. Areas of interest:
a) don't go through the file system. Don't waste time doing
directory lookups and following file-allocation maps; Instead, use raw-disk i/o and read sectors in using device & block number.
Sorry, it does not fit in the linux's cache model.
Quoted 5 lines
b) Be "dynamic"; "Trace" (record (dev&blockno/range) blocks
starting ASAP after system boot and continuing for some "configurable" number of seconds past reaching the desired "run-level" (coinciding with initial disk quiescence). Save as "configurable" (~6-8?) number of traces to allow finding the common initial subset of blocks needed.
It is a alternative way of doing the same job: more precise, with more complexity and more overhead. However the 'blockno' way is not so tasteful.
Quoted 2 lines
c) Allow specification of max# of blocks and max number of "sections"
(discontiguous areas on disk);
Good point, will do it in my work.
Quoted 5 lines
d) "Ideally", would have a way to "defrag" the common set of blocks.
I.e. -- moving the needed blocks from potentially disparate areas of files into 1 or 2 contiguous areas, hopefully near the beginning of the disk (or partition(s)).
That's the area of "boot" pre-caching.
I guess poor man's defrag would be good enough for the seeking storm.
Quoted 8 lines
Next is doing something similar for "application" starts. Start tracing when an application is loaded & observe what blocks are requested for that app for the first 20 ("configurable") seconds of execution. Store traces on a per-application basis. Again, it would be ideal if the different files (blocks, really), needed by an application could be grouped so that sequentially needed disk-blocks are stored sequentially on disk (this _could_ imply the containing files are not contiguous).
Quoted 7 lines
Essentially, one wants to do for applications, the same thing one does for booting. On small applications, the benefit would likely be negligible, but on loading a large app like a windowing system, IDE, or database app, multiple configuration files could be read into the cache in one large read.
That's "application" pre-caching.
Yes, it is a planned feature, will do it.
Quoted 7 lines
A third area -- that can't be easily done in the kernel, but would
require a higher skill level on the part of application and library developers, is to move towards using "delay-loaded" libraries. In Windows, it seems common among system libraries to use this feature. An obvious benefit -- if certain features of a program are not used, the associated libraries are never loaded. Not loading unneeded parts of a program should speed up initial application load time, significantly.
Linux already does lazy loading for linked libs. The only one pitfall is that /lib/ld-linux.so.2 seems to touch the first 512B data of every libs before doing mmap():
% strace dateexecve("/bin/date", ["date"], [/* 41 vars */]) = 0
uname({sys="Linux", node="lark", ...}) = 0
brk(0) = 0x8053000
access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)mmap2(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xb7f0e000access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)mmap2(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xb7f0d000open("/etc/ld.so.cache", O_RDONLY) = 3fstat64(3, {st_mode=S_IFREG|0644, st_size=77643, ...}) = 0mmap2(NULL, 77643, PROT_READ, MAP_PRIVATE, 3, 0) = 0xb7efa000
close(3) = 0access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
open("/lib/tls/librt.so.1", O_RDONLY) = 3
read(3, "\177ELF\1\1\1\0\0\0\0\0\0\0\0\0\3\0\3\0\1\0\0\0`\35\0\000"..., 512) = 512 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~HERE~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ fstat64(3, {st_mode=S_IFREG|0644, st_size=30612, ...}) = 0mmap2(NULL, 29264, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0xb7ef2000 mmap2(0xb7ef8000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x6) = 0xb7ef8000
close(3) = 0access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
open("/lib/tls/libc.so.6", O_RDONLY) = 3read(3, "\177ELF\1\1\1\0\0\0\0\0\0\0\0\0\3\0\3\0\1\0\0\0\260O\1"..., 512) = 512 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~HERE~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ fstat64(3, {st_mode=S_IFREG|0755, st_size=1270928, ...}) = 0mmap2(NULL, 1276892, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0xb7dba000 mmap2(0xb7ee8000, 32768, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x12e) = 0xb7ee8000 mmap2(0xb7ef0000, 7132, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xb7ef0000
close(3) = 0access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
open("/lib/tls/libpthread.so.0", O_RDONLY) = 3read(3, "\177ELF\1\1\1\0\0\0\0\0\0\0\0\0\3\0\3\0\1\0\0\0\340G\0"..., 512) = 512 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~HERE~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ fstat64(3, {st_mode=S_IFREG|0755, st_size=85770, ...}) = 0mmap2(NULL, 70104, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0xb7da8000
mmap2(0xb7db6000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0xd) = 0xb7db6000 mmap2(0xb7db8000, 4568, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xb7db8000
close(3) = 0
They can lead to more seeks, and also disturb the readahead logic much.
Wu
Quoted 11 lines · Wu Fengguang
Quoted 6 lines · Linda Walsh
1. As you mention; reading files "sequentially" through the file
system is "bad" for several reasons. Areas of interest:
a) don't go through the file system. Don't waste time doing
directory lookups and following file-allocation maps; Instead, use raw-disk i/o and read sectors in using device & block number.Sorry, it does not fit in the linux's cache model.
---
Maybe linux's cache model needs to be _improved_ to better
allow for hardware acceleration?^** It is the job of the OS to provide sufficiently low level facilities to allow optimal use of the system hardware, while at the same time providing enough high level facilities to support applications that don't require such tuning.
Quoted 11 lines
Quoted 6 lines
b) Be "dynamic"; "Trace" (record (dev&blockno/range) blocks
starting ASAP after system boot and continuing for some "configurable" number of seconds past reaching the desired "run-level" (coinciding with initial disk quiescence). Save as "configurable" (~6-8?) number of traces to allow finding the common initial subset of blocks needed.It is a alternative way of doing the same job: more precise, with more complexity and more overhead. However the 'blockno' way is not so tasteful.
----
Maybe not so tasteful to you, but it is an alternate path that circumvents unnecessary i/o redirections. An additional optimization is to have a "cache" of frequently used "system applications" that have their pathnames registered, so no run-time seaching of the user PATH is necessary.
Quoted 15 lines
Quoted 3 lines
c) Allow specification of max# of blocks and max number of "sections"
(discontiguous areas on disk);Good point, will do it in my work.
Quoted 6 lines
d) "Ideally", would have a way to "defrag" the common set of blocks.
I.e. -- moving the needed blocks from potentially disparate areas of files into 1 or 2 contiguous areas, hopefully near the beginning of the disk (or partition(s)).
That's the area of "boot" pre-caching.
Quoted 2 lines
I guess poor man's defrag would be good enough for the seeking storm.
---
I disagree. The "poor man's defrag, as you call it, puts entire files
into contiguous sections -- each of which will have to be referenced by following a PATH and directory chain. The optimization I'm talking about would only store the referenced data-blocks actually used in the files. This would allow a directy read into memory of a *bunch* of needed sectors while not including sectors from the same files that are not actually read from during the boot *or* app. initialization process.
Quoted 4 lines
Quoted 2 lines
That's "application" pre-caching.
Yes, it is a planned feature, will do it.
Trés cool.
Quoted 11 lines
Quoted 7 lines
A third area -- that can't be easily done in the kernel, but would
require a higher skill level on the part of application and library
developers, is to move towards using "delay-loaded" libraries. In
Windows, it seems common among system libraries to use this feature. An obvious benefit -- if certain features of a program are not used, the associated libraries are never loaded. Not loading unneeded parts
of a program should speed up initial application load time, significantly.Linux already does lazy loading for linked libs. The only one pitfall is that
/lib/ld-linux.so.2seems to touch the first 512B data of every libs before doingmmap():
----
Yes -- and this is the "killer". If my app may "potentially" use
50 run-time libs, but in any single invocation, only uses 20 of those libs, the page tables and fixups for the unused 30 libraries don't need to be done. In fact, in some configurations, those 30 libs may not even need to be present on disk!
Typical example - "Active Directory"; I don't use it. I don't
need the libraries on my system or need them "resolved" at runtime. It would be far preferable if programs would only load those libraries actually used at run-time -- and load them *dynamically*,
as needed (for libraries that may not actually be called or
used). This way, the initial time to start the program is
significantly reduced to the "core" set of libraries needed to
run the program. Optional features are loaded as those features
are called for off disk. Delays of loading optional libraries
one-two at a time, interactively, are not likely to be noticed,
but if you load all of those "optional" libraries prior to execution,
the sum-total will be noticed in an interactive environment.
^** -- "somewhere", it _seems_, the physical, device relative sector must be resolved. If it is not, how is i/o-block buffer consistency maintained when the user references "device "hda", sector "1000", then the same sector as "hda1", sector 500, and also as file "/etc/passwd", sector 0? _If_ cache consistency is maintained (and I _assume_^**2 it is), they all need to be mapped to a physical sector at some point.
^**2 - Use of assumption noted; feel free to correct me and tell me this isn't the case if linux doesn't maintain disk-block cache consistency.
-linda
Quoted 8 lines · Linda Walsh
Quoted 7 lines · Wu Fengguang
Quoted 6 lines
b) Be "dynamic"; "Trace" (record (dev&blockno/range) blocks
starting ASAP after system boot and continuing for some "configurable" number of seconds past reaching the desired "run-level" (coinciding with initial disk quiescence). Save as "configurable" (~6-8?) number of traces to allow finding the common initial subset of blocks needed.
Quoted 7 lines
Quoted 4 lines
It is a alternative way of doing the same job: more precise, with more complexity and more overhead. However the 'blockno' way is not so tasteful.
----
Maybe not so tasteful to you, but it is an alternate path that circumvents unnecessary i/o redirections. An additional optimization
Yes, it's about the choice of the overhead/generalization that indirections bring about.
Quoted 3 lines
is to have a "cache" of frequently used "system applications" that have their pathnames registered, so no run-time seaching of the user PATH is necessary.
The facility is already there: it is called dcache.
Quoted 13 lines
Quoted 2 lines
I guess poor man's defrag would be good enough for the seeking storm.
---
I disagree. The "poor man's defrag, as you call it, puts entire files
into contiguous sections -- each of which will have to be referenced by following
a PATH and directory chain. The optimization I'm talking about would only store
the referenced data-blocks actually used in the files. This would allow a directy read into memory of a *bunch* of needed sectors while not including sectors from the same files that are not actually read from during the boot *or*
app. initialization process.
The seek storm is mostly caused by small files(that are read in wholes), and the corresponding scattered dir/inode buffers. By moving these files to one single directory, both the file data/inode buffers are kept continuous enough.
Quoted 10 lines
^** -- "somewhere", it _seems_, the physical, device relative sector must be resolved. If it is not, how is i/o-block buffer consistency maintained when the user references "device "hda", sector "1000", then the same sector as "hda1", sector 500, and also as file "
/etc/passwd", sector 0? _If_ cache consistency is maintained (and I _assume_^**2 it is), they all need to be mapped to a physical sector at some point.^**2 - Use of assumption noted; feel free to correct me and tell me this isn't the case if linux doesn't maintain disk-block cache consistency.
The linux cache model is something like:
physical drive file /dev/hda1
| <-----------------> |
file /bin/ls | |
|<---------------------> | |
|<---------------------> | |
| <-----------------> |
| |
| |
file /boot/vmlinuz | |
|<---------------------> | |
| | |
| | |
|<---------------------> | |
| <-----------------> |
| |
| |
| | As opposed to this one:
file /dev/hda1 physical drive
| <-----------------> |
file /bin/ls | |
|<---------------------> | |
|<---------------------> | |
| <-----------------> |
| |
| |
file /boot/vmlinuz | |
|<---------------------> | |
| | |
| | |
|<---------------------> | |
| <-----------------> |
| |
| |
| | Wu
Quoted 11 lines · Wu Fengguang
Rapid linux desktop startup through pre-caching
MOTIVATION
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.
Actually, the best way is to not run so much software. An yes, that is an option. I won't say no to an improved kernel too though. :-)
The apps mentioned are popular, but few needs *all* of them. One can do without KDE and gnome, run a nice lightweight window manager instead. Take the kde/gnome performance hit only when you actually need some kde/gnome app. Not every day. A nice windowmanager like icewm of fluxbox brings the login delay down to 3s or so for me.
Openoffice has lightweight alternatives for every task. (abiword,lyx,gnumeric, . . . ) Strange that this bloated sw is as popular as it is, given the many alternatives. Not something I use every month, and I use linux exclusively for my office tasks.
Another alternative is to profile the slow apps and improve them. Fix algorithms, optimize stuff.
The slow boot is fixable by:
1) run boot scripts in parallell instead of sequentially - somewhat experimental but helps. Especially if you can bring up X before slowest stuff
completes.
2) Don't run what you don't use/need! Don't install everything and the kitchen sink just because it is free software. I am guilty of installing
too much myself,
so I suffer 40-second bootup time. But I don't reboot my office pc
every
week, normally I only have that 3s login delay.
Helge Hafting