2020-04-08 22:02:15

by Nick Terrell

[permalink] [raw]
Subject: [GIT PULL][PATCH v5 0/8] Add support for ZSTD-compressed kernel and initramfs

From: Nick Terrell <[email protected]>

Please pull from

[email protected]:terrelln/linux.git tags/v5-zstd

to get these changes. Alternatively the patchset is included.

Hi all,

This patch set adds support for a ZSTD-compressed kernel, ramdisk, and
initramfs in the kernel boot process. ZSTD-compressed ramdisk and initramfs
are supported on all architectures. The ZSTD-compressed kernel is only
hooked up to x86 in this patch set.

Zstandard requires slightly more memory during the kernel decompression
on x86 (192 KB vs 64 KB), and the memory usage is independent of the
window size.

Zstandard requires memory proprortional to the window size used during
compression for decompressing the ramdisk image, since streaming mode is
used. Newer versions of zstd (1.3.2+) list the window size of a file
with `zstd -lv <file>'. The absolute maximum amount of memory required
is just over 8 MB, but it can be controlled at compression time.

This patch set has been boot tested with buildroot and QEMU based off
of linux-5.6-rc6.

On i386 and x86_64 I have tested the following configurations:
* zstd compressed kernel and a separate zstd compressed initramfs
* zstd compressed kernel and a built-in zstd compressed initramfs
* gzip compressed kernel and a separate gzip compressed initramfs
* gzip compressed kernel and a built-in gzip compressed initramfs

On arm and aarch64 I tested the same configurations, except that the kernel is
always gzip compressed.

Facebook has been using v1 of these patches on x86_64 devices for more than 6
months. When we switched from a xz compressed initramfs to a zstd compressed
initramfs decompression time shrunk from 12 seconds to 3 seconds. When we
switched from a xz compressed kernel to a zstd compressed kernel we saved 2
seconds of boot time.

Facebook has been using v2 of these patches on aarch64 devices for a few weeks.
When we switched from an lzma compressed initramfs to a zstd compressed initramfs
decompression time shrunk from 27 seconds to 8 seconds.

The zstd compressed kernel is smaller than the gzip compressed kernel but larger
than the xz or lzma compressed kernels, and it decompresses faster than
everything except lz4. See the table below for the measurement of an x86_64
kernel ordered by compressed size:

algo size
xz 6,509,792
lzma 6,856,576
zstd 7,399,157
gzip 8,522,527
bzip 8,629,603
lzo 9,808,035
lz4 10,705,570
none 32,565,672

v1 -> v2:
- Rebase
- usr/Makefile and init/Kconfig were changed so the patches were updated
- No functional changes except to rebase
- Split the patches up into smaller chunks

v2 -> v3:
- Add *.zst to the .gitignore in patch 8
- Style nits in patch 3
- Rename the PREBOOT macro to ZSTD_PREBOOT and XXH_PREBOOT in patches
1 through 3

v3 -> v4:
- Increase the ZSTD_IOBUF_SIZE from 4KB to 128KB to improve performance.
With this change I switch from malloc() to large_malloc() for the
buffers.
- Increase the maximum allowed window size from 8 MB to 128 MB, which is
the max that zstd in the kernel supports.

v4 -> v5:
- Update commit message for patch 6 in response to comments
- Rebase onto next-20200408

Best,
Nick Terrell

Adam Borowski (1):
.gitignore: add ZSTD-compressed files

Nick Terrell (7):
lib: prepare zstd for preboot environment
lib: prepare xxhash for preboot environment
lib: add zstd support to decompress
init: add support for zstd compressed kernel
usr: add support for zstd compressed initramfs
x86: bump ZO_z_extra_bytes margin for zstd
x86: Add support for ZSTD compressed kernel

.gitignore | 1 +
Documentation/x86/boot.rst | 6 +-
arch/x86/Kconfig | 1 +
arch/x86/boot/compressed/Makefile | 5 +-
arch/x86/boot/compressed/misc.c | 4 +
arch/x86/boot/header.S | 8 +-
arch/x86/include/asm/boot.h | 6 +-
include/linux/decompress/unzstd.h | 11 +
init/Kconfig | 15 +-
lib/Kconfig | 4 +
lib/Makefile | 1 +
lib/decompress.c | 5 +
lib/decompress_unzstd.c | 342 ++++++++++++++++++++++++++++++
lib/xxhash.c | 21 +-
lib/zstd/decompress.c | 2 +
lib/zstd/fse_decompress.c | 9 +-
lib/zstd/zstd_internal.h | 14 +-
scripts/Makefile.lib | 15 ++
usr/Kconfig | 20 ++
usr/Makefile | 1 +
20 files changed, 464 insertions(+), 27 deletions(-)
create mode 100644 include/linux/decompress/unzstd.h
create mode 100644 lib/decompress_unzstd.c

--
2.26.0


2020-04-08 22:02:17

by Nick Terrell

[permalink] [raw]
Subject: [PATCH v5 7/8] x86: Add support for ZSTD compressed kernel

From: Nick Terrell <[email protected]>

* Add support for zstd compressed kernel
* Bump the heap size for zstd.
* Update the documentation.

Integrates the ZSTD decompression code to the x86 pre-boot code.

Zstandard requires slightly more memory during the kernel decompression
on x86 (192 KB vs 64 KB), and the memory usage is independent of the
window size.

This patch has been boot tested with both a zstd and gzip compressed
kernel on i386 and x86_64 using buildroot and QEMU.

Additionally, this has been tested in production on x86_64 devices.
We saw a 2 second boot time reduction by switching kernel compression
from xz to zstd.

Reviewed-by: Kees Cook <[email protected]>
Tested-by: Sedat Dilek <[email protected]>
Signed-off-by: Nick Terrell <[email protected]>
---
Documentation/x86/boot.rst | 6 +++---
arch/x86/Kconfig | 1 +
arch/x86/boot/compressed/Makefile | 5 ++++-
arch/x86/boot/compressed/misc.c | 4 ++++
arch/x86/include/asm/boot.h | 6 ++++--
5 files changed, 16 insertions(+), 6 deletions(-)

diff --git a/Documentation/x86/boot.rst b/Documentation/x86/boot.rst
index fa7ddc0428c8..0404e99dc1d4 100644
--- a/Documentation/x86/boot.rst
+++ b/Documentation/x86/boot.rst
@@ -782,9 +782,9 @@ Protocol: 2.08+
uncompressed data should be determined using the standard magic
numbers. The currently supported compression formats are gzip
(magic numbers 1F 8B or 1F 9E), bzip2 (magic number 42 5A), LZMA
- (magic number 5D 00), XZ (magic number FD 37), and LZ4 (magic number
- 02 21). The uncompressed payload is currently always ELF (magic
- number 7F 45 4C 46).
+ (magic number 5D 00), XZ (magic number FD 37), LZ4 (magic number
+ 02 21) and ZSTD (magic number 28 B5). The uncompressed payload is
+ currently always ELF (magic number 7F 45 4C 46).

============ ==============
Field name: payload_length
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 886fa8368256..912f783bc01a 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -185,6 +185,7 @@ config X86
select HAVE_KERNEL_LZMA
select HAVE_KERNEL_LZO
select HAVE_KERNEL_XZ
+ select HAVE_KERNEL_ZSTD
select HAVE_KPROBES
select HAVE_KPROBES_ON_FTRACE
select HAVE_FUNCTION_ERROR_INJECTION
diff --git a/arch/x86/boot/compressed/Makefile b/arch/x86/boot/compressed/Makefile
index 7619742f91c9..471e61400a2e 100644
--- a/arch/x86/boot/compressed/Makefile
+++ b/arch/x86/boot/compressed/Makefile
@@ -26,7 +26,7 @@ OBJECT_FILES_NON_STANDARD := y
KCOV_INSTRUMENT := n

targets := vmlinux vmlinux.bin vmlinux.bin.gz vmlinux.bin.bz2 vmlinux.bin.lzma \
- vmlinux.bin.xz vmlinux.bin.lzo vmlinux.bin.lz4
+ vmlinux.bin.xz vmlinux.bin.lzo vmlinux.bin.lz4 vmlinux.bin.zst

KBUILD_CFLAGS := -m$(BITS) -O2
KBUILD_CFLAGS += -fno-strict-aliasing $(call cc-option, -fPIE, -fPIC)
@@ -145,6 +145,8 @@ $(obj)/vmlinux.bin.lzo: $(vmlinux.bin.all-y) FORCE
$(call if_changed,lzo)
$(obj)/vmlinux.bin.lz4: $(vmlinux.bin.all-y) FORCE
$(call if_changed,lz4)
+$(obj)/vmlinux.bin.zst: $(vmlinux.bin.all-y) FORCE
+ $(call if_changed,zstd)

suffix-$(CONFIG_KERNEL_GZIP) := gz
suffix-$(CONFIG_KERNEL_BZIP2) := bz2
@@ -152,6 +154,7 @@ suffix-$(CONFIG_KERNEL_LZMA) := lzma
suffix-$(CONFIG_KERNEL_XZ) := xz
suffix-$(CONFIG_KERNEL_LZO) := lzo
suffix-$(CONFIG_KERNEL_LZ4) := lz4
+suffix-$(CONFIG_KERNEL_ZSTD) := zst

quiet_cmd_mkpiggy = MKPIGGY [email protected]
cmd_mkpiggy = $(obj)/mkpiggy $< > [email protected]
diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index 9652d5c2afda..39e592d0e0b4 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -77,6 +77,10 @@ static int lines, cols;
#ifdef CONFIG_KERNEL_LZ4
#include "../../../../lib/decompress_unlz4.c"
#endif
+
+#ifdef CONFIG_KERNEL_ZSTD
+#include "../../../../lib/decompress_unzstd.c"
+#endif
/*
* NOTE: When adding a new decompressor, please update the analysis in
* ../header.S.
diff --git a/arch/x86/include/asm/boot.h b/arch/x86/include/asm/boot.h
index 680c320363db..d6dd43d25d9f 100644
--- a/arch/x86/include/asm/boot.h
+++ b/arch/x86/include/asm/boot.h
@@ -24,9 +24,11 @@
# error "Invalid value for CONFIG_PHYSICAL_ALIGN"
#endif

-#ifdef CONFIG_KERNEL_BZIP2
+#if defined(CONFIG_KERNEL_BZIP2)
# define BOOT_HEAP_SIZE 0x400000
-#else /* !CONFIG_KERNEL_BZIP2 */
+#elif defined(CONFIG_KERNEL_ZSTD)
+# define BOOT_HEAP_SIZE 0x30000
+#else
# define BOOT_HEAP_SIZE 0x10000
#endif

--
2.26.0

2020-06-01 22:03:17

by Norbert Lange

[permalink] [raw]
Subject: Re: [GIT PULL][PATCH v5 0/8] Add support for ZSTD-compressed kernel and initramfs

The series seems to be stuck in limbo, and I got the hint to bring
this to Andrew's attention [1].
Hope this will finally end in upstream, been using these patches for ~2 years.

Regards, Norbert

[1] - https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=955469

2020-06-01 22:04:29

by Sedat Dilek

[permalink] [raw]
Subject: Re: [GIT PULL][PATCH v5 0/8] Add support for ZSTD-compressed kernel and initramfs

On Mon, Jun 1, 2020 at 11:59 PM Norbert Lange <[email protected]> wrote:
>
> The series seems to be stuck in limbo, and I got the hint to bring
> this to Andrew's attention [1].
> Hope this will finally end in upstream, been using these patches for ~2 years.
>
> Regards, Norbert
>
> [1] - https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=955469

Hi Norbert,

I am using v5 since Linux v5.7-rc+ with modification to Debian's
initramfs-tools.

Thanks for bringing this up!

Regards,
- Sedat -

2020-06-01 22:06:02

by Nick Terrell

[permalink] [raw]
Subject: Re: [GIT PULL][PATCH v5 0/8] Add support for ZSTD-compressed kernel and initramfs

> On Jun 1, 2020, at 2:58 PM, Norbert Lange <[email protected]> wrote:
>
> The series seems to be stuck in limbo, and I got the hint to bring
> this to Andrew's attention [1].
> Hope this will finally end in upstream, been using these patches for ~2 years.

Thanks for the CC!

Subject: Re: [GIT PULL][PATCH v5 0/8] Add support for ZSTD-compressed kernel and initramfs

On Mon, Jun 1, 2020 at 2:59 PM Norbert Lange <[email protected]> wrote:
>
> The series seems to be stuck in limbo, and I got the hint to bring
> this to Andrew's attention [1].
> Hope this will finally end in upstream, been using these patches for ~2 years.
>
> Regards, Norbert
>
> [1] - https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=955469

Began using your patch for Debian Buster backport of 0.136 initramfs-tools, and Nick Terrel's kernel patch for 5.6 -- but modified for 5.5.17-19 in my reiser4 builds -- and set both defaults to zstd.

Thus far, as long as there exists 'a priori' the Zstd package, the combination works in both local and my custom Google cloud instances installations.

Best Professional Regards.


--
Jose R R
http://metztli.it
---------------------------------------------------------------------------------------------
Download Metztli Reiser4: Debian Buster w/ Linux 5.5.19 AMD64
---------------------------------------------------------------------------------------------
feats ZSTD compression https://sf.net/projects/metztli-reiser4/
-------------------------------------------------------------------------------------------
Official current Reiser4 resources: https://reiser4.wiki.kernel.org/

2020-06-16 16:30:00

by Sedat Dilek

[permalink] [raw]
Subject: Re: [GIT PULL][PATCH v5 0/8] Add support for ZSTD-compressed kernel and initramfs

On Tue, Jun 2, 2020 at 12:01 AM Nick Terrell <[email protected]> wrote:
>
> > On Jun 1, 2020, at 2:58 PM, Norbert Lange <[email protected]> wrote:
> >
> > The series seems to be stuck in limbo, and I got the hint to bring
> > this to Andrew's attention [1].
> > Hope this will finally end in upstream, been using these patches for ~2 years.
>
> Thanks for the CC!

Nick can you offer latest zstd (v5) on top of Linux v5.8-rc1, please?

- Sedat -