fastboot: unpacking initramfs faster

fastboot: unpacking initramfs faster

[Andreas Robinson]

Hi,

here's a quick update on what can be done to make initramfs unpacking
faster that I suggested a few weeks ago. There results are mixed.


The bad:

I tried running the initramfs unpacking asynchronously (and earlier) but
ran into a curious problem: The parent thread stalled until
decompression was done. I don't know why - I made sure that the two
threads ran on different cores. Perhaps the parent was cache starved.

I then looked at multithreaded decompression and found that neither gzip
files nor deflate streams provide enough information (eg block lengths)
to let you share the decompression among threads.

It can be done of course, but obviously not without modifying file
formats and userspace tools. 

(Thoughts of snowballs and hell presented themselves at this point.)


The good:

LZO compression is roughly twice as fast as gunzip while files are only
about 7% bigger. The file format is multiprocessing friendly and the
decompressor is already in the mainline kernel.

I estimate that single-threaded LZO would cut the unpacking time almost
in half even on a low-end PC with a slow drive, like the Eee 901.

Finally, someone already wrote support for bzip2 and lzma compressed
initramfs. It's in the -tip tree. Adding LZO to that list should be
straightforward so that's where I'm going next.

Cheers,
Andreas

Re: fastboot: unpacking initramfs faster

[Bodo Eggert]

Andreas Robinson <andr345@gmail.com> wrote:

> I tried running the initramfs unpacking asynchronously (and earlier) but
> ran into a curious problem: The parent thread stalled until
> decompression was done. I don't know why - I made sure that the two
> threads ran on different cores. Perhaps the parent was cache starved.

I could not stall my system by gzip</dev/urandom>/dev/null.
Maybe you accidentally used vfork?

> I then looked at multithreaded decompression and found that neither gzip
> files nor deflate streams provide enough information (eg block lengths)
> to let you share the decompression among threads.
> 
> It can be done of course, but obviously not without modifying file
> formats and userspace tools.
> 
> (Thoughts of snowballs and hell presented themselves at this point.)

Why not make a new set? http://7eggert.dyndns.org:8080/l/bgz.tar.gz

Re: fastboot: unpacking initramfs faster

[Andreas Robinson]

On Tue, 2009-03-24 at 23:11 +0100, Bodo Eggert wrote:
> Andreas Robinson <andr345@gmail.com> wrote:
> 
> > I tried running the initramfs unpacking asynchronously (and earlier) but
> > ran into a curious problem: The parent thread stalled until
> > decompression was done. I don't know why - I made sure that the two
> > threads ran on different cores. Perhaps the parent was cache starved.
> 
> I could not stall my system by gzip</dev/urandom>/dev/null.
> Maybe you accidentally used vfork?

No, this was an in-kernel test. I used the Arjan's new async facility
which calls kthread_create().

> > I then looked at multithreaded decompression and found that neither gzip
> > files nor deflate streams provide enough information (eg block lengths)
> > to let you share the decompression among threads.
> > 
> > It can be done of course, but obviously not without modifying file
> > formats and userspace tools.
> > 
> > (Thoughts of snowballs and hell presented themselves at this point.)
> 
> Why not make a new set? http://7eggert.dyndns.org:8080/l/bgz.tar.gz

Hmm, well if you think there is a chance of it being accepted, then
sure! I'll cook something up, but will be looking to use LZO first since
it's a bit faster to begin with.

Re: fastboot: unpacking initramfs faster

[Bodo Eggert]

On Thu, 26 Mar 2009, Andreas Robinson wrote:
> On Tue, 2009-03-24 at 23:11 +0100, Bodo Eggert wrote:
> > Andreas Robinson <andr345@gmail.com> wrote:

> > > I then looked at multithreaded decompression and found that neither gzip
> > > files nor deflate streams provide enough information (eg block lengths)
> > > to let you share the decompression among threads.
> > > 
> > > It can be done of course, but obviously not without modifying file
> > > formats and userspace tools.
> > > 
> > > (Thoughts of snowballs and hell presented themselves at this point.)
> > 
> > Why not make a new set? http://7eggert.dyndns.org:8080/l/bgz.tar.gz
> 
> Hmm, well if you think there is a chance of it being accepted, then
> sure! I'll cook something up, but will be looking to use LZO first since
> it's a bit faster to begin with.

It's small enough, and now I've updated it to support lzo and put a
license into the files.

Thinking about it: It's now very kernel-specific, other users might like a
block signature to make it robust against errors - e.g. in the middle of a
.tar.bgz file. I think I'll change that soon and put 0x55aa in front of
each block.
-- 
Borges sumus. Resistere inutile est.

Re: fastboot: unpacking initramfs faster

[Andreas Robinson]

On Thu, 2009-03-26 at 12:26 +0100, Bodo Eggert wrote:
> On Thu, 26 Mar 2009, Andreas Robinson wrote:
> > On Tue, 2009-03-24 at 23:11 +0100, Bodo Eggert wrote:
[snip]
> > > Why not make a new set? http://7eggert.dyndns.org:8080/l/bgz.tar.gz
> > 
> > Hmm, well if you think there is a chance of it being accepted, then
> > sure! I'll cook something up, but will be looking to use LZO first since
> > it's a bit faster to begin with.
> 
> It's small enough, and now I've updated it to support lzo and put a
> license into the files.

The file permissions are wrong, I'm not allowed to download it.

> Thinking about it: It's now very kernel-specific, other users might like a
> block signature to make it robust against errors - e.g. in the middle of a
> .tar.bgz file. I think I'll change that soon and put 0x55aa in front of
> each block.

I think we'll want an optional checksum of the compressed data.
Suppose bit 32 in the compressed block size field is set, the next field
is the block's Adler32 checksum.
(the adler32 source is in include/linux/zutil.h)

Re: fastboot: unpacking initramfs faster

[Bodo Eggert]

On Thu, 26 Mar 2009, Andreas Robinson wrote:
> On Thu, 2009-03-26 at 12:26 +0100, Bodo Eggert wrote:
> > On Thu, 26 Mar 2009, Andreas Robinson wrote:
> > > On Tue, 2009-03-24 at 23:11 +0100, Bodo Eggert wrote:
> [snip]

> > > > Why not make a new set? http://7eggert.dyndns.org:8080/l/bgz.tar.gz

> The file permissions are wrong, I'm not allowed to download it.

fixed

> > Thinking about it: It's now very kernel-specific, other users might like a
> > block signature to make it robust against errors - e.g. in the middle of a
> > .tar.bgz file. I think I'll change that soon and put 0x55aa in front of
> > each block.
> 
> I think we'll want an optional checksum of the compressed data.
> Suppose bit 32 in the compressed block size field is set, the next field
> is the block's Adler32 checksum.
> (the adler32 source is in include/linux/zutil.h)

I will think about it.
-- 
Funny quotes:
5. 99 percent of lawyers give the rest a bad name.

Re: fastboot: unpacking initramfs faster

[Andreas Robinson]

Here is a quick and dirty patch that works for me. Applies to current
git.kernel.org/pub/scm/linux/kernel/git/mingo/linux-2.6-x86.git

Work on monolithic-kernel decompression and multithreading is next.

>From 27d64e5fca08d695282da219eb71e5fca978a9d2 Mon Sep 17 00:00:00 2001
From: Andreas Robinson <andr345@gmail.com>
Date: Thu, 26 Mar 2009 16:44:14 +0100
Subject: [PATCH] lib: support lzo-compressed initramfs images

Impact: Allows faster unpacking of the initial ramdisk.

LZO files are marginally larger than gzip, about 7% for the
best compression method lzo1x_999, but decompress about 30%
faster on x86 hardware.

This patch supports a new stream format generated by a
userspace tool named blzo.

Patch content:
* necessary additions to Kconfig and makefiles
* a simple initramfs decompressor
---
 include/linux/decompress/ublzo.h |   12 ++++++
 lib/Kconfig                      |    4 ++
 lib/Makefile                     |    1 +
 lib/decompress.c                 |    5 +++
 lib/decompress_ublzo.c           |   75 ++++++++++++++++++++++++++++++++++++++
 usr/Kconfig                      |    9 +++++
 6 files changed, 106 insertions(+), 0 deletions(-)
 create mode 100644 include/linux/decompress/ublzo.h
 create mode 100644 lib/decompress_ublzo.c

diff --git a/include/linux/decompress/ublzo.h b/include/linux/decompress/ublzo.h
new file mode 100644
index 0000000..e453d07
--- /dev/null
+++ b/include/linux/decompress/ublzo.h
@@ -0,0 +1,12 @@
+#ifndef DECOMPRESS_UBLZO_H
+#define DECOMPRESS_UBLZO_H
+
+int ublzo(unsigned char *, int,
+	  int(*fill)(void*, unsigned int),
+	  int(*flush)(void*, unsigned int),
+	  unsigned char *output,
+	  int *posp,
+	  void(*error)(char *x)
+	);
+
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index e3b7d7a..9e5c7f1 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -104,6 +104,10 @@ config LZO_DECOMPRESS
 # These all provide a common interface (hence the apparent duplication with
 # ZLIB_INFLATE; DECOMPRESS_GZIP is just a wrapper.)
 #
+config DECOMPRESS_BLZO
+	select LZO_DECOMPRESS
+	tristate
+
 config DECOMPRESS_GZIP
 	select ZLIB_INFLATE
 	tristate
diff --git a/lib/Makefile b/lib/Makefile
index b24222c..9ee48e8 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -65,6 +65,7 @@ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
 obj-$(CONFIG_LZO_COMPRESS) += lzo/
 obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
 
+lib-$(CONFIG_DECOMPRESS_BLZO) += decompress_ublzo.o
 lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o
 lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o
 lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o
diff --git a/lib/decompress.c b/lib/decompress.c
index d2842f5..8c189a0 100644
--- a/lib/decompress.c
+++ b/lib/decompress.c
@@ -9,10 +9,14 @@
 #include <linux/decompress/bunzip2.h>
 #include <linux/decompress/unlzma.h>
 #include <linux/decompress/inflate.h>
+#include <linux/decompress/ublzo.h>
 
 #include <linux/types.h>
 #include <linux/string.h>
 
+#ifndef CONFIG_DECOMPRESS_BLZO
+# define ublzo NULL
+#endif
 #ifndef CONFIG_DECOMPRESS_GZIP
 # define gunzip NULL
 #endif
@@ -28,6 +32,7 @@ static const struct compress_format {
 	const char *name;
 	decompress_fn decompressor;
 } compressed_formats[] = {
+	{ {'B', 'L'}, "blzo", ublzo },
 	{ {037, 0213}, "gzip", gunzip },
 	{ {037, 0236}, "gzip", gunzip },
 	{ {0x42, 0x5a}, "bzip2", bunzip2 },
diff --git a/lib/decompress_ublzo.c b/lib/decompress_ublzo.c
new file mode 100644
index 0000000..136f57f
--- /dev/null
+++ b/lib/decompress_ublzo.c
@@ -0,0 +1,75 @@
+/* Simple LZO file format decompressor.
+ *
+ *     Copyright (C) 2009 Andreas Robinson <andr345@gmail.com>
+ *
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ */
+
+#include <linux/types.h>
+#include <linux/lzo.h>
+
+#ifndef STATIC
+#include <linux/decompress/ublzo.h>
+#endif /* STATIC */
+#include <linux/decompress/mm.h>
+
+#define BLZO_BLOCK_SIZE 65536
+
+int INIT ublzo(unsigned char *inbuf, int len,
+		int(*fill)(void*, unsigned int),
+		int(*flush)(void*, unsigned int),
+		unsigned char *output,
+		int *posp,
+		void(*error)(char *x))
+{
+	int ret = LZO_E_OK;
+	size_t start_len, in_len, out_len;
+	void *out;
+
+	start_len = len;
+
+	if (fill) {
+		error("the decompress 'fill' feature is not yet implemented");
+		return LZO_E_ERROR;
+	} else {
+		out = malloc(BLZO_BLOCK_SIZE);
+		if (!out)
+			panic("Cannot allocate decompression buffers!");
+
+		if (memcmp("BLZO", inbuf, 4) != 0)
+			return LZO_E_ERROR;
+
+		inbuf += 4;
+		len -= 4;
+
+		while (len > 0) {
+			in_len = (inbuf[0] << 8) + inbuf[1];
+			inbuf += 2;
+			len -= 2;
+			if (in_len == 0)
+				goto done;
+
+			out_len = BLZO_BLOCK_SIZE;
+			ret = lzo1x_decompress_safe(inbuf, in_len, out, &out_len);
+			if (ret != LZO_E_OK) {
+				error("error in LZO archive");
+				goto done;
+			}
+
+			inbuf += in_len;
+			len -= in_len;
+			flush(out, out_len);
+		}
+	}
+
+done:
+	free(out);
+	*posp = start_len - len;
+	return ret;
+}
+
+#define decompress ublzo
diff --git a/usr/Kconfig b/usr/Kconfig
index 43a3a0f..ff2b15c 100644
--- a/usr/Kconfig
+++ b/usr/Kconfig
@@ -45,6 +45,15 @@ config INITRAMFS_ROOT_GID
 
 	  If you are not sure, leave it set to "0".
 
+config RD_BLZO
+	bool "Initial ramdisk compressed using blzo"
+	default y
+	depends on BLK_DEV_INITRD=y
+	select DECOMPRESS_BLZO
+	help
+	  Support loading of a blzo encoded initial ramdisk or cpio buffer.
+	  If unsure, say Y.
+
 config RD_GZIP
 	bool "Initial ramdisk compressed using gzip"
 	default y
-- 
1.5.6.3