Skip to contentSkip to conversation

fcache: a remapping boot cache

PATCH In review Jens Axboe 4 participants 10 messages May 15, 2006 – Jun 26, 2006 1 message not in the archive Block layer

lore
Share & tools
lore

Jens Axboe

author
#0 lore raw

PATCH 1/1 fcache: a remapping boot cache

Hi,

Inspired by recent postings on various ways to speedup booting, I wrote a little module as a weekend project to actually test some of this. The goal was to make the boot process be completely linear on disk, without having to modify the file system. The results is 'fcache', a remapping cache that sits between the file system and block device.

fcache has two run modes - a priming mode and a normal mode. When run in priming mode, it mirrors every read to the target partition as a write operation on a cache partition resulting in data being laid out linearly on the cache device as a function of time. When running in the normal mode, it acts as a lookup cache and serves data from the cache partition if it can. So if the workload is mostly repeatable, fcache will provide perfect access to the data. So the idea is that you boot with priming enabled once and the subsequent boots with priming off will be faster than normal.

Some facts about fcache and how it works:

o fcache is a "perfect" solution to the problem because it will catch everything, data as well as file system meta data.

o fcache is detachable from the file system at any time. IOW, the file system remains completely valid at all times.

o fcache is file system independent. The patch only includes a half assed modification to ext3 to support it, other file systems are trivially supportable.

o fcache isn't implemented as a dm target, as I wanted to be able to easily attach fcache to any already installed system and easily boot older kernels on it as well.

o fcache requires a separate partition to be used as a cache device, similar to how people normally setup swap. In fact for easy testing if you don't have an extra partition available, just disable swap and use the swap device as the cache device.

Some facts about the current implementation:

o It only supports a single device currently. Can trivially be extended to more.

o As mentioned above, only ext3 is modified to support fcache open/close.

o Trying it on my notebook brought the time from the kernel starts loading to kde has fully auto-logged in down from 50 seconds to 38 seconds. The primed boot took 61 seconds. The notebook is about 4 months old and the file system is very fresh, so better results should be seen on more fragmented installs.

How to use it:

Two new mount options are added to allow specifying the cache device and cache mode, fcache_dev and fcache_prime. fcache_dev takes a string describing the major and minor number of the cache device, and fcache_prime takes a simple integer 0/1 describing whether this is a primed mount or not. IOW:

mount /dev/sda1 /foo -o fcache_dev=8/6,fcache_prime=1

will mount /dev/sda1 on /foo with /dev/sda6 as the cache device and in priming mode. The easiest way to try it out as a boot optimizer is to modify the boot script that remounts the file system rw and attach fcache there. On suse, that's /etc/init.d/boot.rootfsck - just grep for "remount,rw" in /etc/init.d should help you find the location. Add the fcache arguments there, eg for the first boot you would have:

	mount -n -o remount,rw,fcache_dev=8/6,fcache_prime=1 /

and for subsequent boots:

	mount -n -o remount,rw,fcache_dev=8/6,fcache_prime=0 /

After the first boot with priming has been completed, you should remount the fs with priming disabled to end the priming period. When you choose to do that depends on how much you want to prime - perhaps you would do it right after log in, or perhaps you want to start firefox first to get that added as well. Either way, you would issue a normal remount operation with fcache_prime=0 to do that:

# mount / -o remount,fcache_dev=8/6,fcache_prime=0o

fcache will then tell you how much it logged:

# dmesg
[...]
fcache: reads 8787, hits 0, nothing 0
fcache: wrote 8787 extents, holding 281724KiB of data
fcache: wrote header (extents=8787,serial=323)
fcache: open 800006, prime=0, serial=323
fcache: header looks valid (extents=8787 extents, serial=323)
fcache: loaded 8787 extents
fcache: sda6 opened successfully

You probably also want to do that after the first non-primed boot just to check that your hit rate is in the range expected (eg hits == reads, or at least very close):

# dmesg
[...]
fcache: reads 8293, hits 8273, nothing 16
fcache: wrote header (extents=8525,serial=325)
fcache: open 800006, prime=0, serial=325
fcache: header looks valid (extents=8525 extents, serial=325)
fcache: loaded 8525 extents
fcache: sda6 opened successfully

Random notes if this is interesting enough to be taken further:

o Wants to be completely integrated with the distro, of course. It should handle the prime/non-prime mounts automatically by for instance doing a primed boot after the first install and/or whenever the hit rate drops too much due to file system layout changes. You also would want to prevent preload from stepping on your toes during boot. The root remount script should also check for fcache presence so you don't get failed boots due to unknown mount options on older kernels or kernels without fcache loaded.

o Fixup the ext3 integration and add support for other file systems. In theory this could be done generically, perhaps?

Patch is against recent Linus tree, should apply easily to most newer kernels.

block/ll_rw_blk.c +5 -6
index e5041a0..3a50e3f 100644
@@ -2804,12 +2804,10 @@ static void init_request_from_bio(struct
 	 */
 	if (bio_rw_ahead(bio) || bio_failfast(bio))
 		req->flags |= REQ_FAILFAST;
-
-	/*
-	 * REQ_BARRIER implies no merging, but lets make it explicit
-	 */
 	if (unlikely(bio_barrier(bio)))
-		req->flags |= (REQ_HARDBARRIER | REQ_NOMERGE);
+		req->flags |= REQ_HARDBARRIER;
+	if (!bio_mergeable(bio))
+		req->flags |= REQ_NOMERGE;
 
 	req->errors = 0;
 	req->hard_sector = req->sector = bio->bi_sector;
@@ -2857,7 +2855,7 @@ static int __make_request(request_queue_
 
 	spin_lock_irq(q->queue_lock);
 
-	if (unlikely(barrier) || elv_queue_empty(q))
+	if (!bio_mergeable(bio) || elv_queue_empty(q))
 		goto get_rq;
 
 	el_ret = elv_merge(q, &req, bio);
@@ -3096,6 +3094,7 @@ void submit_bio(int rw, struct bio *bio)
 
 	BIO_BUG_ON(!bio->bi_size);
 	BIO_BUG_ON(!bio->bi_io_vec);
+	WARN_ON(bio->bi_next);
 	bio->bi_rw |= rw;
 	if (rw & WRITE)
 		mod_page_state(pgpgout, count);
drivers/block/Kconfig +6 -0
index ae0949b..b53ecec 100644
@@ -456,4 +456,10 @@ config ATA_OVER_ETH
 	This driver provides Support for ATA over Ethernet block
 	devices like the Coraid EtherDrive (R) Storage Blade.
 
+config BLK_FCACHE
+	bool "Boot frontend cache driver"
+	help
+	This driver puts the data needed for a boot sequentially in a
+	defined place, taking all seeks out of the boot process.
+
 endmenu
drivers/block/Makefile +1 -0
index 410f259..279988d 100644
@@ -30,3 +30,4 @@ obj-$(CONFIG_VIODASD)		+= viodasd.o
 obj-$(CONFIG_BLK_DEV_SX8)	+= sx8.o
 obj-$(CONFIG_BLK_DEV_UB)	+= ub.o
 
+obj-$(CONFIG_BLK_FCACHE)	+= fcache.o
drivers/block/fcache.c new file +1204 -0

1,204 lines not on this page · raw message

fs/ext3/super.c +77 -4

169 lines not on this page · raw message

include/linux/bio.h +9 -0
index b60ffe3..db43b56 100644
@@ -124,6 +124,7 @@ #define BIO_CLONED	4	/* doesn't own data
 #define BIO_BOUNCED	5	/* bio is a bounce bio */
 #define BIO_USER_MAPPED 6	/* contains user pages */
 #define BIO_EOPNOTSUPP	7	/* not supported */
+#define BIO_FCACHE	8	/* foo */
 #define bio_flagged(bio, flag)	((bio)->bi_flags & (1 << (flag)))
 
 /*
@@ -179,6 +180,14 @@ #define bio_sync(bio)		((bio)->bi_rw & (
 #define bio_failfast(bio)	((bio)->bi_rw & (1 << BIO_RW_FAILFAST))
 #define bio_rw_ahead(bio)	((bio)->bi_rw & (1 << BIO_RW_AHEAD))
 
+static inline int bio_mergeable(struct bio *bio)
+{
+	if (!bio_barrier(bio) && !bio->bi_idx)
+		return 1;
+
+	return 0;
+}
+
 /*
  * will die
  */
include/linux/ext3_fs.h +2 -0
index 3ade6a4..47ed5a9 100644
@@ -376,6 +376,8 @@ #define EXT3_MOUNT_NOBH			0x40000 /* No 
 #define EXT3_MOUNT_QUOTA		0x80000 /* Some quota option set */
 #define EXT3_MOUNT_USRQUOTA		0x100000 /* "old" user quota */
 #define EXT3_MOUNT_GRPQUOTA		0x200000 /* "old" group quota */
+#define EXT3_MOUNT_FCACHE		0x400000 /* using fcache */
+#define EXT3_MOUNT_FCACHEPRIME		0x800000 /* priming fcache */
 
 /* Compatibility, for having both ext2_fs.h and ext3_fs.h included at once */
 #ifndef _LINUX_EXT2_FS_H
Signature · 1 line
Jens Axboe
author
#1 lore raw
Quoted 5 lines · Jens Axboe

o Trying it on my notebook brought the time from the kernel starts loading to kde has fully auto-logged in down from 50 seconds to 38 seconds. The primed boot took 61 seconds. The notebook is about 4 months old and the file system is very fresh, so better results should be seen on more fragmented installs.

Update - the above numbers were with an older version and with the cache partition located at the very end of the drive (hence being a lot slower than the root partition at the front). The fcache boot takes 33 seconds now, from the kernel starts loading to the kde login has finished. Probably 5 seconds of that time is device probe and network setup (dunno why the latter is still sleeping so much, I disabled dhcp for this test to avoid waits (for both fcache and normal boot, of course)).

Signature · 1 line
Jens Axboe
author
#2 lore raw
Quoted 7 lines · Jens Axboe
Quoted 5 lines · Jens Axboe

o Trying it on my notebook brought the time from the kernel starts loading to kde has fully auto-logged in down from 50 seconds to 38 seconds. The primed boot took 61 seconds. The notebook is about 4 months old and the file system is very fresh, so better results should be seen on more fragmented installs.

Quoted 7 lines

Update - the above numbers were with an older version and with the cache partition located at the very end of the drive (hence being a lot slower than the root partition at the front). The fcache boot takes 33 seconds now, from the kernel starts loading to the kde login has finished. Probably 5 seconds of that time is device probe and network setup (dunno why the latter is still sleeping so much, I disabled dhcp for this test to avoid waits (for both fcache and normal boot, of course)).

Updated patch available in the fcache branch of the block repo. Various cleanups and fixes (nothing critical), and gets rid of the BIO_FCACHE hack.

git://brick.kernel.dk/data/git/linux-2.6-block.git fcache

Signature · 1 line
Jens Axboe
#3 lore raw
Quoted 8 lines · Jens Axboe
Quoted 7 lines · Jens Axboe
Quoted 5 lines · Jens Axboe

o Trying it on my notebook brought the time from the kernel starts loading to kde has fully auto-logged in down from 50 seconds to 38 seconds. The primed boot took 61 seconds. The notebook is about 4 months old and the file system is very fresh, so better results should be seen on more fragmented installs.

[...]

Quoted 1 line

git://brick.kernel.dk/data/git/linux-2.6-block.git fcache

Just cloned.

Any progress on this project Jens?

I'll try to apply the patch to mainline and post here some numbers.

Ciao,

Signature · 2 lines
Paolo
http://paolociarrocchi.googlepages.com
author
#4 lore raw
Quoted 10 lines · Paolo Ciarrocchi
Quoted 9 lines · Jens Axboe
Quoted 5 lines · Jens Axboe
Quoted 4 lines · Jens Axboe

o Trying it on my notebook brought the time from the kernel starts loading to kde has fully auto-logged in down from 50 seconds to 38 seconds. The primed boot took 61 seconds. The notebook is about 4 months old and the file system is very fresh, so better results

should

Quoted 2 lines
Quoted 1 line

be seen on more fragmented installs.

Quoted 8 lines

[...]

Quoted 1 line

git://brick.kernel.dk/data/git/linux-2.6-block.git fcache

Just cloned.

Any progress on this project Jens?

I'll try to apply the patch to mainline and post here some numbers.

Well it's a git repo, get it and see :-)
But yes, it's had various fixes and optimizations, it should apply to latest Linus kernel. There's also a consistency checker here:

git://brick.kernel.dk/data/git/fcache.git

that can check both fcache data and metadata.

Signature · 1 line
Jens Axboe
#5 lore raw

Set this up on my laptop yesterday with some awesome results. I'm using 2.6.17-ck1 which has v2.1.

Heres some bootcharts, before, after, and a prime run.

http://archlinux.org/~james/normal.png
http://archlinux.org/~james/fs-fcache.png
http://archlinux.org/~james/fs-fcache-prime.png

Repeated boots show about the same 6 second improvement, 32 down to 26 seconds. Looking at the slowdowns in the fs-fcache run, most are due to cpu load, waiting on network or, modprobe, and not disk access. X now starts nearly instantaneously.

As an experiment, I primed my cache right through to logging into my desktop environment. It was so effective, that now when I login, the GNOME splash screen only flickers onto the screen briefly, and the panels appear almost instantly. This is a big improvment over without fcache, where you'd see each component of GNOME being loaded on the splash screen, nautilus, metacity, and the panels would take quite a bit of time to render and load all their applets.

Impressive work, I hope to see it broadened to other filesystems, improved and merged to vanilla soon because it has clear improvements.

James

Signature · 2 lines
iphitus - Beyond Maintainer, Arch Trusted User, Arch Developer.
Home:iphitus.loudas.com
author
#6 lore raw
Quoted 22 lines · James

Set this up on my laptop yesterday with some awesome results. I'm using 2.6.17-ck1 which has v2.1.

Heres some bootcharts, before, after, and a prime run.

http://archlinux.org/~james/normal.png
http://archlinux.org/~james/fs-fcache.png
http://archlinux.org/~james/fs-fcache-prime.png

Repeated boots show about the same 6 second improvement, 32 down to 26 seconds. Looking at the slowdowns in the fs-fcache run, most are due to cpu load, waiting on network or, modprobe, and not disk access. X now starts nearly instantaneously.

As an experiment, I primed my cache right through to logging into my desktop environment. It was so effective, that now when I login, the GNOME splash screen only flickers onto the screen briefly, and the panels appear almost instantly. This is a big improvment over without fcache, where you'd see each component of GNOME being loaded on the splash screen, nautilus, metacity, and the panels would take quite a bit of time to render and load all their applets.

Quoted 2 lines

Impressive work, I hope to see it broadened to other filesystems, improved and merged to vanilla soon because it has clear improvements.

Thanks for giving it a spin! I have plans to implement some improvements on monday that will speed it up even more, I hope I can talk you into retesting it then. Basically it make sure we always get full speed out of the drive by extending the 4kb reads with a sliding window cache. That will help both drive efficiency, and also speed up the cases where sub sequent boots differ just a little bit from the primed boot (often the case with parallel init scripts). It should win you a few seconds more in total, would be my guess.

I hope to be able to extend it to xfs and reiser in the very near future as well, should not be hard to do.

Signature · 1 line
Jens Axboe
#7 lore raw
Quoted 35 lines · Jens Axboe
Quoted 22 lines · James

Set this up on my laptop yesterday with some awesome results. I'm using 2.6.17-ck1 which has v2.1.

Heres some bootcharts, before, after, and a prime run.

http://archlinux.org/~james/normal.png
http://archlinux.org/~james/fs-fcache.png
http://archlinux.org/~james/fs-fcache-prime.png

Repeated boots show about the same 6 second improvement, 32 down to 26 seconds. Looking at the slowdowns in the fs-fcache run, most are due to cpu load, waiting on network or, modprobe, and not disk access. X now starts nearly instantaneously.

As an experiment, I primed my cache right through to logging into my desktop environment. It was so effective, that now when I login, the GNOME splash screen only flickers onto the screen briefly, and the panels appear almost instantly. This is a big improvment over without fcache, where you'd see each component of GNOME being loaded on the splash screen, nautilus, metacity, and the panels would take quite a bit of time to render and load all their applets.

Quoted 2 lines

Impressive work, I hope to see it broadened to other filesystems, improved and merged to vanilla soon because it has clear improvements.

Thanks for giving it a spin! I have plans to implement some improvements on monday that will speed it up even more, I hope I can talk you into retesting it then. Basically it make sure we always get full speed out of the drive by extending the 4kb reads with a sliding window cache. That will help both drive efficiency, and also speed up the cases where sub sequent boots differ just a little bit from the primed boot (often the case with parallel init scripts). It should win you a few seconds more in total, would be my guess.

Quoted 2 lines

I hope to be able to extend it to xfs and reiser in the very near future as well, should not be hard to do.

Impressive good work, Jens!

Do you have any distribution in contact with you already?

Thank you so much, I look forward to test it on xfs.

Best regards,

Signature · 2 lines
[]s,
André Goddard
author
#8 lore raw
Quoted 36 lines · André Goddard Rosa
Quoted 35 lines · Jens Axboe
Quoted 22 lines · James

Set this up on my laptop yesterday with some awesome results. I'm using 2.6.17-ck1 which has v2.1.

Heres some bootcharts, before, after, and a prime run.

http://archlinux.org/~james/normal.png
http://archlinux.org/~james/fs-fcache.png
http://archlinux.org/~james/fs-fcache-prime.png

Repeated boots show about the same 6 second improvement, 32 down to 26 seconds. Looking at the slowdowns in the fs-fcache run, most are due to cpu load, waiting on network or, modprobe, and not disk access. X now starts nearly instantaneously.

As an experiment, I primed my cache right through to logging into my desktop environment. It was so effective, that now when I login, the GNOME splash screen only flickers onto the screen briefly, and the panels appear almost instantly. This is a big improvment over without fcache, where you'd see each component of GNOME being loaded on the splash screen, nautilus, metacity, and the panels would take quite a bit of time to render and load all their applets.

Quoted 2 lines

Impressive work, I hope to see it broadened to other filesystems, improved and merged to vanilla soon because it has clear improvements.

Thanks for giving it a spin! I have plans to implement some improvements on monday that will speed it up even more, I hope I can talk you into retesting it then. Basically it make sure we always get full speed out of the drive by extending the 4kb reads with a sliding window cache. That will help both drive efficiency, and also speed up the cases where sub sequent boots differ just a little bit from the primed boot (often the case with parallel init scripts). It should win you a few seconds more in total, would be my guess.

Quoted 4 lines
Quoted 2 lines

I hope to be able to extend it to xfs and reiser in the very near future as well, should not be hard to do.

Impressive good work, Jens!

Thanks

Quoted 1 line

Do you have any distribution in contact with you already?

Not sure what you mean... My original intention with fcache was to use it as a research project into what perfect block layout would do to the boot process, since that seems to be a hot topic for some people. Personally, the machines I do boot frequently are often bigger beasts for testing purposes and they spend minutes getting to grub anyways. I mostly use suspend/resume to keep my on times fast.

But it is interesting, and perhaps some parts of fcache will find its way into distrobutions sometime (either directly, or parts of fcache being reused for a slightly different approach).

Signature · 1 line
Jens Axboe
author
#10 lore raw
In reply to a message not in the archive
Quoted 10 lines · gary sheppard

The thing is there are a lot of Desktop users out there who for various reasons will shut down their systems either every night, or every few days. Where I live now is notorious for brown outs and black outs. Now in a server room you *WILL* have battery backup and of course will simply laugh at such an event. In the home very few people I know who have computers have a battery backup system. For those types of people anything to help boot time is nice to have. It may be totally bogus to equate boot time with system performance but many folks do in fact equate boot time/ system responsiveness to performance. I very much believe that your work with Fcache is and will be very much appreciated. Another project

Yes, I realize that and I look forward to posting some numbers on the newer fcache later today. It should be even faster than before. I just stated my personal usage pattern, I know it might not be the average.

Quoted 2 lines

http://www.initng.org/ is actively working on reducing boot time. I
actually downloaded their live CD and have to admit it is pretty good!

Fixing init scripts is of course a priority, but it needs to happen with improve disk layout as well to get the huge speed increase.

There are also things like kernel device detection. SATA is pretty quick, but the old IDE is dog slow and you easily waste many seconds there.

Signature · 1 line
Jens Axboe