Add support for ZSTD-compressed kernel
Subsystems (5)
Nick Terrell
maintainercover 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.
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.
Thanks,
Nick Terrell
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 +- scripts/Makefile.lib | 15 ++ usr/Kconfig | 22 +++ 17 files changed, 465 insertions(+), 25 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 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.
--- 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 +- scripts/Makefile.lib | 15 ++ usr/Kconfig | 22 +++ 11 files changed, 442 insertions(+), 18 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 ****************************************************************/
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 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
[email protected]
reviewerQuoted 43 lines · Nick Terrell
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.
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.Thanks,
Nick TerrellNick Terrell (2):
lib: Add support for ZSTD-compressed kernel
x86: Add support for ZSTD-compressed kernelDocumentation/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 +- scripts/Makefile.lib | 15 ++ usr/Kconfig | 22 +++ 17 files changed, 465 insertions(+), 25 deletions(-)
Quoted 2 lines
create mode 100644
include/linux/decompress/unzstd.hcreate mode 100644lib/decompress_unzstd.c
And, pray tell, what are the actual results? What is the trade-off of kernel size versus decompression performance versus the other algorithms that we already support? Adding algorithms for their own sake is a bad thing not a good thing.
Signature · 1 line
Sent from my Android device with K-9 Mail. Please excuse my brevity.
Nick Terrell
maintainerQuoted 47 lines · On 10/10/17, 2:56 PM, "[email protected]" <[email protected]> wrote:
Quoted 43 lines · Nick Terrell
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.
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.Thanks,
Nick TerrellNick Terrell (2):
lib: Add support for ZSTD-compressed kernel
x86: Add support for ZSTD-compressed kernelDocumentation/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 +- scripts/Makefile.lib | 15 ++ usr/Kconfig | 22 +++ 17 files changed, 465 insertions(+), 25 deletions(-)Quoted 2 lines
create mode 100644
include/linux/decompress/unzstd.hcreate mode 100644lib/decompress_unzstd.c
Quoted 1 line
And, pray tell, what are the actual results? What is the trade-off of kernel size versus decompression performance versus the other algorithms that we already support? Adding algorithms for their own sake is a bad thing not a good thing.
Sorry I neglected to include the benchmarks I've run so far. I've included them below, and will add them to the next version's cover letter.
Comparing the command line tools on a kernel image that is 68970616 B large:
| Algorithm | Compression Ratio | Decompression MB/s | |-----------|-------------------|--------------------| | zstd | 4.42 | 436.5 | | gzip | 3.72 | 134.1 | | xz | 4.83 | 53.1 | | lz4 | 3.18 | 1682.2 | | lzo | 3.36 | 389.6 | | bzip2 | 4.03 | 33.3 |
This isn't actually benchmarks of the kernel decompression, but I expect the relative results to be the same. It compresses the second best and decompresses the second fastest.
I know that this isn't a real benchmark of the kernel decompression. I still need to figure out how to time the kernel decompression. If you have any suggestions let me know. Otherwise, I'll get back to you when I've figured out how to run the benchmark.
Best,
Nick Terrell
Quoted 27 lines · Nick Terrell
Quoted 16 lines · On 10/10/17, 2:56 PM, "[email protected]" <[email protected]> wrote:
Quoted 8 lines · Nick Terrell
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.
Quoted 6 lines
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.Quoted 4 lines
And, pray tell, what are the actual results? What is the trade-off of kernel size versus decompression performance versus the other algorithms that we already support? Adding algorithms for their own sake is a bad thing not a good thing.
Sorry I neglected to include the benchmarks I've run so far. I've included them below, and will add them to the next version's cover letter.
Comparing the command line tools on a kernel image that is 68970616 B large:
Quoted 8 lines
| Algorithm | Compression Ratio | Decompression MB/s | |-----------|-------------------|--------------------| | zstd | 4.42 | 436.5 | | gzip | 3.72 | 134.1 | | xz | 4.83 | 53.1 | | lz4 | 3.18 | 1682.2 | | lzo | 3.36 | 389.6 | | bzip2 | 4.03 | 33.3 |
Perhaps it'd be a good idea to cull some of bad algorithms? I don't know the memory used by those, but envelope of the table you just shown suggests using bzip2 and lzo is pointless. So is gzip, but it's widespread as the default for initramfs producers, thus it'd be unsafe to kill it.
Meow!
Signature · 4 lines
⢀⣴⠾⠻⢶⣦⠀ We domesticated dogs 36000 years ago; together we chased ⣾⠁⢰⠒⠀⣿⡁ animals, hung out and licked or scratched our private parts. ⢿⡄⠘⠷⠚⠋⠀ Cats domesticated us 9500 years ago, and immediately we got ⠈⠳⣄⠀⠀⠀⠀ agriculture, towns then cities. -- whitroth on /.
Nick Terrell
maintainerQuoted 37 lines · Adam Borowski
Quoted 27 lines · Nick Terrell
Quoted 16 lines · On 10/10/17, 2:56 PM, "[email protected]" <[email protected]> wrote:
Quoted 8 lines · Nick Terrell
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.
Quoted 6 lines
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.Quoted 4 lines
And, pray tell, what are the actual results? What is the trade-off of kernel size versus decompression performance versus the other algorithms that we already support? Adding algorithms for their own sake is a bad thing not a good thing.
Sorry I neglected to include the benchmarks I've run so far. I've included them below, and will add them to the next version's cover letter.
Comparing the command line tools on a kernel image that is 68970616 B large:
Quoted 8 lines
| Algorithm | Compression Ratio | Decompression MB/s | |-----------|-------------------|--------------------| | zstd | 4.42 | 436.5 | | gzip | 3.72 | 134.1 | | xz | 4.83 | 53.1 | | lz4 | 3.18 | 1682.2 | | lzo | 3.36 | 389.6 | | bzip2 | 4.03 | 33.3 |
Quoted 4 lines
Perhaps it'd be a good idea to cull some of bad algorithms? I don't know the memory used by those, but envelope of the table you just shown suggests using bzip2 and lzo is pointless. So is gzip, but it's widespread as the default for initramfs producers, thus it'd be unsafe to kill it.
I'm not sure there is a great use case for bzip2. It requires more memory than xz, compresses worse, and decompresses slower. lzo in the kernel might decompress a bit faster than zstd (looking back at the BtrFS benchmarks, it did). More importantly, it uses less memory than zstd. When decompressing the kernel zstd only needs 192 KB, but for initramfs, it will need more. Still, unless you really need 5% more compression, lz4 is probably a better option than lzo for speed.
Quoted 4 lines
Quoted 4 lines
I know that this isn't a real benchmark of the kernel decompression. I still need to figure out how to time the kernel decompression. If you have any suggestions let me know. Otherwise, I'll get back to you when I've figured out how to run the benchmark.
I've found a way to benchmark the kernel decompression time during boot with QEMU. I add timestamps to every line of the output. I also had to print 100 lines before the decompression starts to get consistent results.
I've found that zstd is decompressing 2x slower than it should. I narrowed down the problem to ZSTD_wildcopy() and ZSTD_copy8() in lib/zstd/zstd_internal.h. ZSTD_wildcopy() calls memcpy(src, dst, 8) in a loop and doesn't handle the freestanding memcpy() well. Replacing it with __builtin_mcmpy(src, dst, 8) doubles the speed.
I'm not an expert in freestanding gcc compilation, but I believe it is okay to call __builtin_memcpy() in freestanding mode, and gcc will either inline it, or add the right function call. The difference being that gcc will be able to apply its memcpy() analysis. I also see that arch/x86/boot/string.h defines memcpy() to __builtin_memcpy. Is it safe to directly use __builtin_memcpy() in lib/zstd/zstd_internal.h?
If so, I'll submit a separate patch, and make sure to benchmark the existing use cases (BtrFS and SquashFS).
Quoted 24 lines · Nick Terrell
Quoted 18 lines · Adam Borowski
Quoted 8 lines · Nick Terrell
Quoted 4 lines · On 10/10/17, 2:56 PM, "[email protected]" <[email protected]> wrote:
Quoted 3 lines · Nick Terrell
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.
Comparing the command line tools on a kernel image that is 68970616 B large:
Quoted 8 lines
| Algorithm | Compression Ratio | Decompression MB/s | |-----------|-------------------|--------------------| | zstd | 4.42 | 436.5 | | gzip | 3.72 | 134.1 | | xz | 4.83 | 53.1 | | lz4 | 3.18 | 1682.2 | | lzo | 3.36 | 389.6 | | bzip2 | 4.03 | 33.3 |Quoted 4 lines
Perhaps it'd be a good idea to cull some of bad algorithms? I don't know the memory used by those, but envelope of the table you just shown suggests using bzip2 and lzo is pointless. So is gzip, but it's widespread as the default for initramfs producers, thus it'd be unsafe to kill it.
Quoted 7 lines
I'm not sure there is a great use case for bzip2. It requires more memory than xz, compresses worse, and decompresses slower. lzo in the kernel might decompress a bit faster than zstd (looking back at the BtrFS benchmarks, it did). More importantly, it uses less memory than zstd. When decompressing the kernel zstd only needs 192 KB, but for initramfs, it will need more. Still, unless you really need 5% more compression, lz4 is probably a better option than lzo for speed.
The main reason I'm raising this question is, bzip2 has no other users in the kernel, thus removing support for it would allow us to delete its code.
As for lzo, even if there are cases when it's a bit faster (overcoming the 9% lead zstd has in your userspace benchmark), it wouldn't be faster by much -- certainly nowhere to make anyone want the massive compression loss.
Thus, let's enumerate use cases:
* a fast modern machine: zstd boots a second faster at the cost of 1.3MB image size; doesn't matter much either way. No one wants weaker options.
* a weaker machine: zstd rapidly gains as boot times rise.
* a very slow machine with fast I/O that boots often: lz4.
* disk space at extreme premium: xz.
In no case I can think of other algorithms are the rational choice. There's little gain in removing the rest, though: the code is used for other purposes in the kernel, and doesn't get compiled in unless manually selected.
Zstd looks like a good default, but it's nowhere near mature enough: this patch is x86-only, tools which people may use to analyze compressed kernels don't know about zstd yet, etc.
Thus, I'd propose the following plan:
* add zstd
* remove bzip2
* update recommendations (Kconfig text)
* in a year or two, consider making zstd the default
Quoted 9 lines
Quoted 4 lines
Quoted 4 lines
I know that this isn't a real benchmark of the kernel decompression. I still need to figure out how to time the kernel decompression. If you have any suggestions let me know. Otherwise, I'll get back to you when I've figured out how to run the benchmark.
I've found a way to benchmark the kernel decompression time during boot with QEMU. I add timestamps to every line of the output. I also had to print 100 lines before the decompression starts to get consistent results.
Quoted 5 lines
I've found that zstd is decompressing 2x slower than it should. I narrowed down the problem to
ZSTD_wildcopy()andZSTD_copy8()inlib/zstd/zstd_internal.h.ZSTD_wildcopy()callsmemcpy(src, dst, 8)in a loop and doesn't handle the freestandingmemcpy()well. Replacing it with__builtin_mcmpy(src, dst, 8)doubles the speed.
... and by maturing I meant issues like this.
Quoted 6 lines
I'm not an expert in freestanding gcc compilation, but I believe it is okay to call
__builtin_memcpy()in freestanding mode, and gcc will either inline it, or add the right function call. The difference being that gcc will be able to apply itsmemcpy()analysis. I also see thatarch/x86/boot/string.hdefinesmemcpy()to__builtin_memcpy. Is it safe to directly use__builtin_memcpy()inlib/zstd/zstd_internal.h?
Try it, and see if it builds and fails to crash. :)
Meow!
Signature · 4 lines
⢀⣴⠾⠻⢶⣦⠀ We domesticated dogs 36000 years ago; together we chased ⣾⠁⢰⠒⠀⣿⡁ animals, hung out and licked or scratched our private parts. ⢿⡄⠘⠷⠚⠋⠀ Cats domesticated us 9500 years ago, and immediately we got ⠈⠳⣄⠀⠀⠀⠀ agriculture, towns then cities. -- whitroth on /.