Add support for ZSTD-compressed kernel
Subsystems (5)
Nick Terrell
maintainerv2 cover Add support for ZSTD-compressed kernel
Hi,
This patch set adds support for a ZSTD-compressed kernel and ramdisk images in the kernel boot process. It only integrates the support with x86, though the first patch is generic to all architectures.
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. In my tests it compresses the second best (behind LZMA/XZ) and decompresses the third fastest (behind LZO and LZ4).
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.
I benchmarked kernel decompression by adding a log line before and after decompression, appending a timestamp to each line of QEMU's stdout, and measuring the time between the two lines. I had to spin before decompression for some time to normalize the measurements. The benchmarks are run in QEMU a 2.2GHz x86 CPU, using a kernel config pulled from my machine.
Original kernel size: 21756168 B (21.7 MB)
| Algorithm | Ratio | Decompress MB/s | |-----------|-------|-----------------| | GZIP | 3.11 | 229.1 | | BZIP2 | 3.23 | 30.0 | | LZMA | 3.81 | 36.6 | | XZ | 4.06 | 42.2 | | LZO | 2.81 | 582.9 | | LZ4 | 2.18 | 1447.5 | | ZSTD | 3.55 | 364.6 |
BZIP2 and LZMA aren't interesting, since XZ is better than both in all respects. GZIP remains useful because of its wide adoption. LZO is squeezed tightly between LZ4 and ZSTD, though maintains an edge on ratio or decompression speed respectively.
Thanks,
Nick Terrell
Changelog:
v1 -> v2:
- Fix performance bug in zstd decompression
- Gate gcc bug workaround to buggy versions
- Benchmark kernel compression
Nick Terrell (2):
lib: Add support for ZSTD-compressed kernel
x86: Add support for ZSTD-compressed kernel
Documentation/x86/boot.txt | 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 | 26 +++ init/Kconfig | 14 +- lib/Kconfig | 4 + lib/Makefile | 1 + lib/decompress.c | 5 + lib/decompress_unzstd.c | 341 ++++++++++++++++++++++++++++++++++++++ lib/xxhash.c | 21 ++- lib/zstd/decompress.c | 2 + lib/zstd/fse_decompress.c | 9 +- lib/zstd/zstd_internal.h | 10 +- scripts/Makefile.lib | 15 ++ usr/Kconfig | 22 +++ 18 files changed, 474 insertions(+), 26 deletions(-) create mode 100644 include/linux/decompress/unzstd.h create mode 100644 lib/decompress_unzstd.c
Signature · 1 line
2.9.5
Nick Terrell
maintainerPATCH v2 1/2 lib: Add support for ZSTD-compressed kernel
Add support for extracting ZSTD-compressed kernel images, as well as ZSTD-compressed ramdisk images in the kernel boot process.
When neither fill' nor flush' are used, the decompression function requires a constant amount of memory (192 KB is sufficient). When either is used the decompression function requires memory proportional to the window size used during compression, which is limited to 8 MB. The maximum memory usage is just over 8 MB.
Fix up lib/zstd and lib/xxhash.c for the preboot environment. They avoid declaring themselves as modules. A memcpy() call needs to be a __builtin_memcpy() for performance. The gcc-7.1 bug in ZSTD_wildcopy() was fixed in gcc-7.2, so it can be gated, since it hurts performance.
---
v1 -> v2:
- Fix performance bug in zstd decompression
- Gate gcc bug workaround to buggy versions
include/linux/decompress/unzstd.h | 26 +++ init/Kconfig | 14 +- lib/Kconfig | 4 + lib/Makefile | 1 + lib/decompress.c | 5 + lib/decompress_unzstd.c | 341 ++++++++++++++++++++++++++++++++++++++ lib/xxhash.c | 21 ++- lib/zstd/decompress.c | 2 + lib/zstd/fse_decompress.c | 9 +- lib/zstd/zstd_internal.h | 10 +- scripts/Makefile.lib | 15 ++ usr/Kconfig | 22 +++ 12 files changed, 451 insertions(+), 19 deletions(-) create mode 100644 include/linux/decompress/unzstd.h create mode 100644 lib/decompress_unzstd.c
include/linux/decompress/unzstd.h new file +26 -0
@@ -0,0 +1,26 @@ +/* +* Copyright (C) 2017 Facebook +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public +* License v2 as published by the Free Software Foundation. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +* General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program. If not, see <https://www.gnu.org/licenses/>. +*/ + +#ifndef LINUX_DECOMPRESS_UNZSTD_H +#define LINUX_DECOMPRESS_UNZSTD_H + +int unzstd (unsigned char *inbuf,long len, +long (*fill)(void *,unsigned long ), +long (*flush)(void *,unsigned long ), +unsigned char *output, +long *pos, +void (*error_fn)(char *x)); +#endif
init/Kconfig +13 -1
@@ -127,10 +127,13 @@ config HAVE_KERNEL_LZO config HAVE_KERNEL_LZ4 bool +config HAVE_KERNEL_ZSTD + bool + choice prompt "Kernel compression mode" default KERNEL_GZIP - depends on HAVE_KERNEL_GZIP || HAVE_KERNEL_BZIP2 || HAVE_KERNEL_LZMA || HAVE_KERNEL_XZ || HAVE_KERNEL_LZO || HAVE_KERNEL_LZ4 + depends on HAVE_KERNEL_GZIP || HAVE_KERNEL_BZIP2 || HAVE_KERNEL_LZMA || HAVE_KERNEL_XZ || HAVE_KERNEL_LZO || HAVE_KERNEL_LZ4 || HAVE_KERNEL_ZSTD help The linux kernel is a kind of self-extracting executable. Several compression algorithms are available, which differ
@@ -209,6 +212,15 @@ config KERNEL_LZ4 is about 8% bigger than LZO. But the decompression speed is faster than LZO. +config KERNEL_ZSTD + bool "ZSTD" + depends on HAVE_KERNEL_ZSTD + help + ZSTD is a compression algorithm targeting intermediate compression + with fast decompression speed. It will compress better than GZIP and + decompress around the same speed as LZO, but slower than LZ4. You + will need at least 192 KB RAM or more for booting. + endchoice config DEFAULT_HOSTNAME
lib/Kconfig +4 -0
@@ -285,6 +285,10 @@ config DECOMPRESS_LZ4 select LZ4_DECOMPRESS tristate +config DECOMPRESS_ZSTD + select ZSTD_DECOMPRESS + tristate + # # Generic allocator support is selected if needed #
lib/Makefile +1 -0
@@ -128,6 +128,7 @@ lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o lib-$(CONFIG_DECOMPRESS_XZ) += decompress_unxz.o lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o lib-$(CONFIG_DECOMPRESS_LZ4) += decompress_unlz4.o +lib-$(CONFIG_DECOMPRESS_ZSTD) += decompress_unzstd.o obj-$(CONFIG_TEXTSEARCH) += textsearch.o obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
lib/decompress.c +5 -0
@@ -12,6 +12,7 @@#include <linux/decompress/inflate.h> #include <linux/decompress/unlzo.h> #include <linux/decompress/unlz4.h> +#include <linux/decompress/unzstd.h> #include <linux/types.h> #include <linux/string.h>
@@ -36,6 +37,9 @@#ifndef CONFIG_DECOMPRESS_LZ4 # define unlz4 NULL#endif +#ifndef CONFIG_DECOMPRESS_ZSTD +# define unzstd NULL +#endif struct compress_format {unsigned char magic[2 ];
@@ -51,6 +55,7 @@ static const struct compress_format compressed_formats[] __initconst = { { {0xfd, 0x37}, "xz", unxz }, { {0x89, 0x4c}, "lzo", unlzo }, { {0x02, 0x21}, "lz4", unlz4 }, + { {0x28, 0xb5}, "zstd", unzstd }, { {0, 0}, NULL, NULL } };
lib/decompress_unzstd.c new file +341 -0
341 lines not on this page · raw message
lib/xxhash.c +12 -9
@@ -80,13 +80,11 @@ void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src) {memcpy (dst, src,sizeof (*dst)); } -EXPORT_SYMBOL (xxh32_copy_state);void xxh64_copy_state (struct xxh64_state *dst,const struct xxh64_state *src) {memcpy (dst, src,sizeof (*dst)); } -EXPORT_SYMBOL (xxh64_copy_state);/*-*************************** * Simple Hash Functions
@@ -151,7 +149,6 @@ uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)return h32; } -EXPORT_SYMBOL (xxh32);static uint64_t xxh64_round (uint64_t acc,const uint64_t input) {
@@ -234,7 +231,6 @@ uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)return h64; } -EXPORT_SYMBOL (xxh64);/*-************************************************** * Advanced Hash Functions
@@ -251,7 +247,6 @@ void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed) state.v4 = seed -PRIME32_1 ;memcpy (statePtr, &state,sizeof (state)); } -EXPORT_SYMBOL (xxh32_reset);void xxh64_reset (struct xxh64_state *statePtr,const uint64_t seed) {
@@ -265,7 +260,6 @@ void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed) state.v4 = seed -PRIME64_1 ;memcpy (statePtr, &state,sizeof (state)); } -EXPORT_SYMBOL (xxh64_reset);int xxh32_update (struct xxh32_state *state,const void *input,const size_t len) {
@@ -334,7 +328,6 @@ int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)return 0 ; } -EXPORT_SYMBOL (xxh32_update);uint32_t xxh32_digest (const struct xxh32_state *state) {
@@ -372,7 +365,6 @@ uint32_t xxh32_digest(const struct xxh32_state *state)return h32; } -EXPORT_SYMBOL (xxh32_digest);int xxh64_update (struct xxh64_state *state,const void *input,const size_t len) {
@@ -439,7 +431,6 @@ int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)return 0 ; } -EXPORT_SYMBOL (xxh64_update);uint64_t xxh64_digest (const struct xxh64_state *state) {
@@ -494,7 +485,19 @@ uint64_t xxh64_digest(const struct xxh64_state *state)return h64; } + +#ifndef PREBOOT +EXPORT_SYMBOL (xxh32_copy_state); +EXPORT_SYMBOL (xxh64_copy_state); +EXPORT_SYMBOL (xxh32); +EXPORT_SYMBOL (xxh64); +EXPORT_SYMBOL (xxh32_reset); +EXPORT_SYMBOL (xxh64_reset); +EXPORT_SYMBOL (xxh32_update); +EXPORT_SYMBOL (xxh32_digest); +EXPORT_SYMBOL (xxh64_update);EXPORT_SYMBOL (xxh64_digest);MODULE_LICENSE ("Dual BSD/GPL" );MODULE_DESCRIPTION ("xxHash" ); +#endif
lib/zstd/decompress.c +2 -0
@@ -2487,6 +2487,7 @@ size_t ZSTD_decompressStream(ZSTD_DStream *zds, ZSTD_outBuffer *output, ZSTD_inB } } +#ifndef PREBOOT EXPORT_SYMBOL (ZSTD_DCtxWorkspaceBound);EXPORT_SYMBOL (ZSTD_initDCtx);EXPORT_SYMBOL (ZSTD_decompressDCtx);
@@ -2526,3 +2527,4 @@ EXPORT_SYMBOL(ZSTD_insertBlock);MODULE_LICENSE ("Dual BSD/GPL" );MODULE_DESCRIPTION ("Zstd Decompressor" ); +#endif
lib/zstd/fse_decompress.c +1 -8
@@ -47,6 +47,7 @@****************************************************************/ #include "bitstream.h" #include "fse.h" +#include "zstd_internal.h" #include <linux/compiler.h> #include <linux/kernel.h> #include <linux/string.h> /* memcpy, memset */
@@ -60,14 +61,6 @@enum { FSE_static_assert =1 / (int )(!!(c)) }; \ }/* use only *after* variable declarations */ -/* check and forward error code */ -#define CHECK_F (f) \ - { \ - size_t const e = f; \ - if (FSE_isError(e)) \ - return e; \ - } -/* ************************************************************** * Templates ****************************************************************/
lib/zstd/zstd_internal.h +9 -1
@@ -127,7 +127,13 @@ static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;* Shared functions to include for inlining *********************************************/ ZSTD_STATIC void ZSTD_copy8(void *dst, const void *src) { -memcpy (dst, src,8 ); +/* zstd relies heavily on gcc being able to analyze and inline this +* memcpy() call, since it is called in a tight loop. Preboot mode +* is compiled in freestanding mode, which stops gcc from analyzing +* memcpy(). Use __builtin_memcpy() to tell gcc to analyze this as a +* regular memcpy(). +*/ +__builtin_memcpy (dst, src,8 ); }/*! ZSTD_wildcopy() : * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
@@ -137,6 +143,7 @@ ZSTD_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)const BYTE * ip = (const BYTE *)src;BYTE * op = (BYTE *)dst;BYTE *const oend = op + length; +#if GCC_VERSION >=70000 &&GCC_VERSION <70200 /* Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388. * Avoid the bad case where the loop only runs once by handling the * special case separately. This doesn't trigger the bug because it
@@ -144,6 +151,7 @@ ZSTD_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)*/ if (length <=8 )return ZSTD_copy8 (dst, src); +#endif do { ZSTD_copy8(op, ip); op += 8;
scripts/Makefile.lib +15 -0
@@ -412,6 +412,21 @@ cmd_xzmisc = (cat $(filter-out FORCE,$^) | \ xz --check=crc32 --lzma2=dict=1MiB) > $@ || \ (rm -f $@ ; false) +# ZSTD +# --------------------------------------------------------------------------- +# Appends the uncompressed size of the data using size_append. The .zst +# format has the size information available at the beginning of the file too, +# but it's in a more complex format and it's good to avoid changing the part +# of the boot code that reads the uncompressed size. +# Note that the bytes added by size_append will make the zstd tool think that +# the file is corrupt. This is expected. + +quiet_cmd_zstd = ZSTD $@ +cmd_zstd = (cat $(filter-out FORCE,$^) | \ + zstd -19 && \ + $(call size_append, $(filter-out FORCE,$^))) > $@ || \ + (rm -f $@ ; false) + # ASM offsets # ---------------------------------------------------------------------------
usr/Kconfig +22 -0
@@ -105,6 +105,15 @@ config RD_LZ4 Support loading of a LZ4 encoded initial ramdisk or cpio buffer If unsure, say N. +config RD_ZSTD + bool "Support initial ramdisk/ramfs compressed using ZSTD" + default y + depends on BLK_DEV_INITRD + select DECOMPRESS_ZSTD + help + Support loading of a ZSTD encoded initial ramdisk or cpio buffer. + If unsure, say N. + choice prompt "Built-in initramfs compression mode" depends on INITRAMFS_SOURCE!=""
@@ -213,6 +222,17 @@ config INITRAMFS_COMPRESSION_LZ4 If you choose this, keep in mind that most distros don't provide lz4 by default which could cause a build failure. +config INITRAMFS_COMPRESSION_ZSTD + bool "ZSTD" + depends on RD_ZSTD + help + ZSTD is a compression algorithm targeting intermediate compression + with fast decompression speed. It will compress better than GZIP and + decompress around the same speed as LZO, but slower than LZ4. + + If you choose this, keep in mind that you may need to install the zstd + tool to be able to compress the initram. + endchoice config INITRAMFS_COMPRESSION
@@ -225,10 +245,12 @@ config INITRAMFS_COMPRESSION default ".xz" if INITRAMFS_COMPRESSION_XZ default ".lzo" if INITRAMFS_COMPRESSION_LZO default ".lz4" if INITRAMFS_COMPRESSION_LZ4 + default ".zst" if INITRAMFS_COMPRESSION_ZSTD default ".gz" if RD_GZIP default ".lz4" if RD_LZ4 default ".lzo" if RD_LZO default ".xz" if RD_XZ default ".lzma" if RD_LZMA default ".bz2" if RD_BZIP2 + default ".zst" if RD_ZSTD default ""
Signature · 1 line
2.9.5
Nick Terrell
maintainerPATCH v2 2/2 x86: Add support for ZSTD-compressed kernel
In reply to Nick TerrellIntegrates 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.
Zstandard requires memory proportional 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.
--- Documentation/x86/boot.txt | 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 ++++-- 6 files changed, 23 insertions(+), 7 deletions(-)
Documentation/x86/boot.txt +3 -3
@@ -666,9 +666,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 Type: read
arch/x86/Kconfig +1 -0
@@ -150,6 +150,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_KRETPROBES
arch/x86/boot/compressed/Makefile +4 -1
@@ -23,7 +23,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) -D__KERNEL__ -O2 KBUILD_CFLAGS += -fno-strict-aliasing $(call cc-option, -fPIE, -fPIC)
@@ -133,6 +133,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
@@ -140,6 +142,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 $@ cmd_mkpiggy = $(obj)/mkpiggy $< > $@ || ( rm -f $@ ; false )
arch/x86/boot/compressed/misc.c +4 -0
@@ -74,6 +74,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.
arch/x86/boot/header.S +7 -1
@@ -526,8 +526,14 @@ pref_address: .quad LOAD_PHYSICAL_ADDR # preferred load addr # the size-dependent part now grows so fast. # # extra_bytes = (uncompressed_size >> 8) + 65536 +# +# ZSTD compressed data grows by at most 3 bytes per 128K, and only has a 22 +# byte fixed overhead but has a maximum block size of 128K, so it needs a +# larger margin. +# +# extra_bytes = (uncompressed_size >> 8) + 131072 -#define ZO_z_extra_bytes ((ZO_z_output_len >> 8) + 65536) +#define ZO_z_extra_bytes ((ZO_z_output_len >> 8) + 131072) #if ZO_z_output_len > ZO_z_input_len # define ZO_z_extract_offset (ZO_z_output_len + ZO_z_extra_bytes - \ ZO_z_input_len)
arch/x86/include/asm/boot.h +4 -2
@@ -23,9 +23,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
Signature · 1 line
2.9.5
Re: [PATCH v2 2/2] x86: Add support for ZSTD-compressed kernel
arch/x86/boot/compressed/Makefile $(obj)/vmlinux.bin.lzo: $(vmlinux.bin.all-y) FORCE · line 137
Quoted 6 lines · Nick Terrell
arch/x86/boot/compressed/Makefile +2
-0@@ -133,6 +133,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)
In my experience the biggest problem with these options is that the special command line tools needed for the build are often not installed on the build systems.
So we turn it off and go back to GZIP to make the kernel build again. Or we settle on some other option, but then when a better compressor like ZSTD comes up it's too much trouble to change all the .configs.
There were recently some patches to add a stackprotector automatic selection that probes if gcc supports stack overflow support, and if not falls back automatically.
A similar thing for good compression options would seem better:
have a AUTO config option that uses ZSTD and fall back to GZIP if it's not available. Then put it into defconfig.
I suspect that would increase your user base quite a bit.
-Andi