Skip to contentSkip to conversation

kernel facilities for cache prefetching

RFC Arjan van de Ven 9 participants 18 messages May 2, 2006 – May 6, 2006 3 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#2 lore raw
Quoted 12 lines · Arjan van de Ven
Quoted 11 lines

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

Quoted 1 line

you missed the solution Fedora deploys since over a year using readahead

Thanks, and sorry for more previous works that I failed to mention here :)

Wu

A message that is not in the archive (sent off-list or not yet received): [email protected]

#4 lore raw
Quoted 13 lines · Wu Fengguang
Quoted 12 lines · Arjan van de Ven
Quoted 11 lines

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

Quoted 3 lines
Quoted 1 line

you missed the solution Fedora deploys since over a year using readahead

Thanks, and sorry for more previous works that I failed to mention here :)

one interesting thing that came out of the fedora readahead work is that most of the bootup isn't actually IO bound. My test machine for example can load all the data into ram in about 10 seconds, so that the rest of the boot is basically IO-less. But that still takes 2 minutes.... So I'm not entirely sure how much you can win by just attacking this.

Another interesting approach would be to actually put all the data you want to use in a non-fragmented, sequential area on disk somehow (there is an OLS paper submitted about that by Ben) so that at least the disk side is seekless...

#5 lore raw
Quoted 5 lines · Arjan van de Ven

one interesting thing that came out of the fedora readahead work is that most of the bootup isn't actually IO bound. My test machine for example can load all the data into ram in about 10 seconds, so that the rest of the boot is basically IO-less. But that still takes 2 minutes.... So I'm not entirely sure how much you can win by just attacking this.

Yes, I find it hard to improve the boot time of the init.d stage. However, it is perfectly ok to preload all GUI staffs during that timespan, by overlapping CPU/IO activities.

Quoted 4 lines

Another interesting approach would be to actually put all the data you want to use in a non-fragmented, sequential area on disk somehow (there is an OLS paper submitted about that by Ben) so that at least the disk side is seekless...

You are right, reducing seeking distances helps not much. My fluxbox desktop requires near 3k seeks, which can be loaded in the 20s init.d booting time. But for KDE/GNOME desktops, some defragging would be necessary to fit them into the 20s time span.

I found ext3 to be rather good filesystem to support poor man's defrag described by Chris Mason:
http://www.gelato.unsw.edu.au/archives/git/0504/1690.html
This certainly can help. Based on some ideas from andrea I made a poor man's defrag script last year that was similar. It worked by copying files into a flat dir in the order you expected to read them in, deleting the original, then hard linking them into their original name.

Make the 'flat dir' as an top level dir would do the trick for ext3. We have good chance to merge 10k seeks into 3k seeks by this trick :)

Wu

#6 lore raw
Quoted 8 lines · Wu Fengguang
Quoted 5 lines · Arjan van de Ven

one interesting thing that came out of the fedora readahead work is that most of the bootup isn't actually IO bound. My test machine for example can load all the data into ram in about 10 seconds, so that the rest of the boot is basically IO-less. But that still takes 2 minutes.... So I'm not entirely sure how much you can win by just attacking this.

Yes, I find it hard to improve the boot time of the init.d stage.

Then _get rid of your init.d_.

SysV init sequence is insane.

I use daemontools-based setup and it starts up to login prompt in 5-10 secs (counting from the root fs mount).

In my setup, after a few simple startup scripts a svscan process is called, which starts all services in parallel. Gettys are services, and start right away.
--
vda

A message that is not in the archive (sent off-list or not yet received): [email protected]

#8 lore raw
Quoted 10 lines · Wu Fengguang
Quoted 5 lines · Arjan van de Ven

one interesting thing that came out of the fedora readahead work is that most of the bootup isn't actually IO bound. My test machine for example can load all the data into ram in about 10 seconds, so that the rest of the boot is basically IO-less. But that still takes 2 minutes.... So I'm not entirely sure how much you can win by just attacking this.

Yes, I find it hard to improve the boot time of the init.d stage. However, it is perfectly ok to preload all GUI staffs during that timespan, by overlapping CPU/IO activities.

fwiw fedora even loads a bunch of GUI apps into memory already

Quoted 10 lines
Quoted 5 lines

Another interesting approach would be to actually put all the data you want to use in a non-fragmented, sequential area on disk somehow (there is an OLS paper submitted about that by Ben) so that at least the disk side is seekless...

You are right, reducing seeking distances helps not much. My fluxbox desktop requires near 3k seeks, which can be loaded in the 20s init.d booting time. But for KDE/GNOME desktops, some defragging would be necessary to fit them into the 20s time span.

or just move the blocks (or copy them) to a reserved area...

#9 lore raw
Quoted 11 lines
Quoted 9 lines
Quoted 4 lines

Another interesting approach would be to actually put all the data you want to use in a non-fragmented, sequential area on disk somehow (there is an OLS paper submitted about that by Ben) so that at least the disk side is seekless...

You are right, reducing seeking distances helps not much. My fluxbox desktop requires near 3k seeks, which can be loaded in the 20s init.d booting time. But for KDE/GNOME desktops, some defragging would be necessary to fit them into the 20s time span.

or just move the blocks (or copy them) to a reserved area...

Or even put it into a ramdisk, and then fix userspace. When Gnome loads more than 10000 files [http://kerneltrap.org/node/2157], it sounds like a design problem.

Jan Engelhardt

#10 lore raw
In reply to Arjan van de Ven
Quoted 5 lines · Arjan van de Ven
Quoted 3 lines

Yes, I find it hard to improve the boot time of the init.d stage. However, it is perfectly ok to preload all GUI staffs during that timespan, by overlapping CPU/IO activities.

fwiw fedora even loads a bunch of GUI apps into memory already

Hopefully the warm cache time has been improving.
I have very good performance with fluxbox. Lubos Lunak said
(http://wiki.kde.org/tiki-index.php?page=KDE%20Google%20SoC%202006%20ideas#id106304)
that "KDE startup with cold caches is several times slower than with warm caches." The latest GNOME release also saw good speedup.

Quoted 11 lines
Quoted 9 lines
Quoted 4 lines

Another interesting approach would be to actually put all the data you want to use in a non-fragmented, sequential area on disk somehow (there is an OLS paper submitted about that by Ben) so that at least the disk side is seekless...

You are right, reducing seeking distances helps not much. My fluxbox desktop requires near 3k seeks, which can be loaded in the 20s init.d booting time. But for KDE/GNOME desktops, some defragging would be necessary to fit them into the 20s time span.

or just move the blocks (or copy them) to a reserved area...

Ah, we can save discontinuous pages into the journal file on umounting and restore them on mounting. But let's do the simple way first :)

Wu

#11 lore raw
In reply to Arjan van de Ven
Quoted 2 lines · Arjan van de Ven

one interesting thing that came out of the fedora readahead work is that most of the bootup isn't actually IO bound.

Here's another interesting datapoint.
A huge proportion of I/O done during bootup is _completely_ unnecessary.

Profiling just a few of the places that seemed to stall yielded some lovely things, like cupsd reading in and parsing descriptions for every printer ever known to man, even if there's no printer connected. Or my favorite.. hald reloading and reparsing the same XML hardware description files.. ~50 times, _each_.

Utterly insane.

(And these aren't Fedora specific problems btw, every distro shipping those
bits will have the same dumb behaviour [modulo versions])

Dave

Signature · 1 line
http://www.codemonkey.org.uk
#12 lore raw
In reply to a message not in the archive
Quoted 2 lines · Wu Fengguang

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

I tried something very similar to this years ago, except I made it explicit instead of hiding it in the blk_run_backing_dev() which we didn't have at that time. My initial results showed that you would get a load of requests for different pages so would end up doing io randomly instead again.

Your patch isn't exactly pretty, but that is fixable. I'm more interested in how you'd control that sanely.

Signature · 1 line
Jens Axboe
#13 lore raw
Quoted 5 lines · Jens Axboe

I tried something very similar to this years ago, except I made it explicit instead of hiding it in the blk_run_backing_dev() which we didn't have at that time. My initial results showed that you would get a load of requests for different pages so would end up doing io randomly instead again.

Yes, the hard one would be _not_ to impact normal I/Os in any way. A simple solution for the case of deadline scheduler would be:

- static const int read_expire = HZ / 2; /* max time before a read is submitted. */
+ static const int read_expire = HZ / 2; /* max time before a impending read is submitted. */
+ static const int reada_expire = HZ * 30; /* max time before a read-ahead is submitted. */

Wu

#14 lore raw
In reply to Jens Axboe
Quoted 2 lines · Jens Axboe

Your patch isn't exactly pretty, but that is fixable. I'm more interested in how you'd control that sanely.

I have a quick and dirty hack called BootCache (only afterwards did I notice that Apple used the same name) that snoops all the read requests during startup and uses that to populate a file which gets read in to populate the cache on subsequent boots. The results are impressive: eliminating the seeks (since the file is contiguous) results in 15s (out of the 45s from init starting to the login prompt) reduction in boot time on ext3.

Prefetch without reordering isn't particularly effective, as the cost of the seeks to read in the inodes and file data tend to block critical path io in the startup scripts.

I hope to release the code sometime soon and rework it to be a better fit for merging with the kernel -- it should be possible to use the block io tracing facility to log the blocks required and then feed that back into the filesystem to reallocate blocks in the filesystem. That would eliminate the messy part of bootcache that has to snoop block writes to maintain the cache. This is all part of what I'm aiming to present at OLS.

-ben

Signature · 2 lines
"Time is of no importance, Mr. President, only life is important."
Don't Email: <[email protected]>.
#15 lore raw
In reply to a message not in the archive

Hi!

Quoted 3 lines

SOC PROPOSAL

Rapid linux desktop startup through pre-caching

Looks nice me...

Quoted 17 lines

SCHEME/GOAL
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
......

Quoted 10 lines

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

Could we use this instead of blockdev freezing/big suspend image support? It should permit us to resume quickly (with small image), and then do readahead. ... that will give us usable machine quickly, still very responsive desktop after resume?

Pavel

Signature · 1 line
Thanks for all the (sleeping) penguins.
#16 lore raw

Hi.

Quoted 4 lines · Pavel Machek

Could we use this instead of blockdev freezing/big suspend image support? It should permit us to resume quickly (with small image), and then do readahead. ... that will give us usable machine quickly, still very responsive desktop after resume?

Unrelated to bdev freezing, and will involve far more seeking than reading a contiguous image (as they normally are).

Regards,

Nigel

Signature · 2 lines
See our web page for Howtos, FAQs, the Wiki and mailing list info.
http://www.suspend2.net                IRC: #suspend2 on Freenode
#17 lore raw
Quoted 7 lines · Nigel Cunningham
Quoted 4 lines

Could we use this instead of blockdev freezing/big suspend image support? It should permit us to resume quickly (with small image), and then do readahead. ... that will give us usable machine quickly, still very responsive desktop after resume?

Unrelated to bdev freezing, and will involve far more seeking than reading a contiguous image (as they normally are).

Yes, needs more pondering on this issue...

#18 lore raw
In reply to Pavel Machek

Hi Pavel,

Quoted 5 lines · Pavel Machek
Quoted 3 lines

SOC PROPOSAL

Rapid linux desktop startup through pre-caching

Looks nice me...

Thanks.

Quoted 28 lines
Quoted 17 lines

SCHEME/GOAL
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
......

Quoted 10 lines

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

Quoted 4 lines

Could we use this instead of blockdev freezing/big suspend image support? It should permit us to resume quickly (with small image), and then do readahead. ... that will give us usable machine quickly, still very responsive desktop after resume?

Sure. Indeed I have considered about the possibility to integrate my work with the foresighted userland-swsusp idea. The added value of this approach is that user-land tools can do all kinds of smart processing of the contents, and present users with different policies.

Another imagined user of /proc/filecache is system adms :)

Wu

#19 lore raw
In reply to Pavel Machek
Quoted 4 lines · Pavel Machek

Could we use this instead of blockdev freezing/big suspend image support? It should permit us to resume quickly (with small image), and then do readahead. ... that will give us usable machine quickly, still very responsive desktop after resume?

Seems that it can help in reducing the image size:
write only small ranges of file pages to the suspend image(maybe 80MB = 10k ranges * 8k avgsize), and let the prefetcher restore other large chunks of code/data, depending on user specified policies.

Wu

#20 lore raw
In reply to Pavel Machek
Quoted 11 lines · Pavel Machek
Quoted 10 lines
		$ echo "file /dev/hda1" > /proc/filecache
		$ cat /proc/filecache
		# file /dev/hda1
		# mask 0
		#
		# idx	len
		0	24
		48	2
		53	5
		......
Quoted 4 lines

Could we use this instead of blockdev freezing/big suspend image support? It should permit us to resume quickly (with small image), and then do readahead. ... that will give us usable machine quickly, still very responsive desktop after resume?

Badari's usage case inspired me that on suspension we can
- first invoke a user-land tool to do all the cache status-logging/analyzing/selective-dropping jobs
- then let the kernel write all the remaining caches(made up of many small chunks) to the suspend image

And do the reverse things on restoring. With that we moved all the strategies to userspace.

Wu