Skip to contentSkip to conversation

Add support for ZSTD-compressed kernel

PATCH Superseded Nick Terrell 3 participants 8 messages Oct 10, 2017 – Oct 11, 2017

Subsystems (5)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Nick Terrell

author maintainer
#0 lore raw

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.

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
author maintainer
#1 lore raw

PATCH 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
new file mode 100644
index 0000000..6f3022c
@@ -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
index 78cb246..3caa314 100644
@@ -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
index b1445b2..4d32bec 100644
@@ -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
index dafa796..8afcdc3 100644
@@ -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
index 62696df..b17bb07 100644
@@ -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
index aa61e2a..7f1d3cb 100644
@@ -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
index b178467..b7b6599 100644
@@ -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
index a84300e..0b35353 100644
@@ -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
index 5e975fe..807c1fa 100644
@@ -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
index d53112fd..b63d8ee 100644
@@ -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
author maintainer
#2 lore raw

PATCH 2/2 x86: Add support for ZSTD-compressed kernel

In reply to Nick Terrell

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.

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
index 5e9b826..7f5d1f9 100644
@@ -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
index 971feac..e34e3e5 100644
@@ -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
index 8a95827..118a423 100644
@@ -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
index c14217c..8140895 100644
@@ -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
index 1bb08ec..11b70e1 100644
@@ -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
index abd06b1..dcfdd4e 100644
@@ -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
#3 lore raw
In reply to Nick Terrell
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 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(-)
Quoted 2 lines

create mode 100644 include/linux/decompress/unzstd.h create mode 100644 lib/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.
author maintainer
#4 lore raw
Quoted 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 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(-)
Quoted 2 lines

create mode 100644 include/linux/decompress/unzstd.h create mode 100644 lib/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

#5 lore raw
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 /.
author maintainer
#6 lore raw
Quoted 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).

#7 lore raw
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() 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.

... 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 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?

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 /.