Skip to contentSkip to conversation

Add support for ZSTD-compressed kernel and initramfs

PATCH Superseded Nick Terrell 5 participants 17 messages Apr 1, 2020 – Apr 6, 2020

Subsystems (5)

v4 of 10 Superseded Latest is v10 →

lore
Share & tools
lore
#0 lore raw

v4 cover Add support for ZSTD-compressed kernel and initramfs

From: Nick Terrell <[email protected]>

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.

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
Signature · 1 line
2.26.0
#1 lore raw

PATCH v4 1/8 lib: prepare zstd for preboot environment

From: Nick Terrell <[email protected]>

* Don't export symbols if ZSTD_PREBOOT is defined.
* Remove a double definition of the CHECK_F macro when the zstd library is amalgamated.
* Switch ZSTD_copy8() to __builtin_memcpy(), because in the preboot environment on x86 gcc can't inline memcpy() otherwise.
* Limit the gcc hack in ZSTD_wildcopy() to the broken gcc version. See
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388.

These changes are necessary to get the build to work in the preboot environment, and to get reasonable performance. ZSTD_copy8() and ZSTD_wildcopy() are in the core of the zstd hot loop. So outlining these calls to memcpy(), and having an extra branch are very detrimental to performance.

---
 lib/zstd/decompress.c     |  2 ++
 lib/zstd/fse_decompress.c |  9 +--------
 lib/zstd/zstd_internal.h  | 14 ++++++++++++--
 3 files changed, 15 insertions(+), 10 deletions(-)
lib/zstd/decompress.c +2 -0
index 269ee9a796c1..73ded63278cf 100644
@@ -2490,6 +2490,7 @@ size_t ZSTD_decompressStream(ZSTD_DStream *zds, ZSTD_outBuffer *output, ZSTD_inB
 	}
 }
 
+#ifndef ZSTD_PREBOOT
 EXPORT_SYMBOL(ZSTD_DCtxWorkspaceBound);
 EXPORT_SYMBOL(ZSTD_initDCtx);
 EXPORT_SYMBOL(ZSTD_decompressDCtx);
@@ -2529,3 +2530,4 @@ EXPORT_SYMBOL(ZSTD_insertBlock);
 
 MODULE_LICENSE("Dual BSD/GPL");
 MODULE_DESCRIPTION("Zstd Decompressor");
+#endif
lib/zstd/fse_decompress.c +1 -8
index a84300e5a013..0b353530fb3f 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
 ****************************************************************/
lib/zstd/zstd_internal.h +12 -2
index 1a79fab9e13a..dac753397f86 100644
@@ -127,7 +127,14 @@ 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,13 +144,16 @@ 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;
-	/* Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388.
+#if defined(GCC_VERSION) && 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
 	 * doesn't involve pointer/integer overflow.
 	 */
 	if (length <= 8)
 		return ZSTD_copy8(dst, src);
+#endif
 	do {
 		ZSTD_copy8(op, ip);
 		op += 8;
Signature · 1 line
2.26.0
#2 lore raw

PATCH v4 2/8 lib: prepare xxhash for preboot environment

In reply to Nick Terrell

From: Nick Terrell <[email protected]>

Don't export symbols if XXH_PREBOOT is defined.

This change is necessary to get xxhash to work in a preboot environment, which is needed to support zstd-compressed kernels.

---
 lib/xxhash.c | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)
lib/xxhash.c +12 -9
index aa61e2a3802f..b4364e011392 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 XXH_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
Signature · 1 line
2.26.0
#3 lore raw

PATCH v4 3/8 lib: add zstd support to decompress

In reply to Nick Terrell

From: Nick Terrell <[email protected]>

* Add unzstd() and the zstd decompress interface.
* Add zstd support to decompress_method().

The decompress_method() and unzstd() functions are used to decompress the initramfs and the initrd. The __decompress() function is used in the preboot environment to decompress a zstd compressed kernel.

The zstd decompression function allows the input and output buffers to overlap because that is used by x86 kernel decompression.

---
 include/linux/decompress/unzstd.h |  11 +
 lib/Kconfig                       |   4 +
 lib/Makefile                      |   1 +
 lib/decompress.c                  |   5 +
 lib/decompress_unzstd.c           | 342 ++++++++++++++++++++++++++++++
 5 files changed, 363 insertions(+)
 create mode 100644 include/linux/decompress/unzstd.h
 create mode 100644 lib/decompress_unzstd.c
include/linux/decompress/unzstd.h new file +11 -0
new file mode 100644
index 000000000000..56d539ae880f
@@ -0,0 +1,11 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#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
lib/Kconfig +4 -0
index bc7e56370129..11de5fa09a52 100644
@@ -336,6 +336,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 611872c06926..09ad45ba6883 100644
@@ -160,6 +160,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 857ab1af1ef3..ab3fc90ffc64 100644
@@ -13,6 +13,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>
@@ -37,6 +38,9 @@
 #ifndef CONFIG_DECOMPRESS_LZ4
 # define unlz4 NULL
 #endif
+#ifndef CONFIG_DECOMPRESS_ZSTD
+# define unzstd NULL
+#endif
 
 struct compress_format {
 	unsigned char magic[2];
@@ -52,6 +56,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 +342 -0

342 lines not on this page · raw message

Signature · 1 line
2.26.0
#4 lore raw

PATCH v4 4/8 init: add support for zstd compressed kernel

In reply to Nick Terrell

From: Nick Terrell <[email protected]>

* Adds the zstd cmd to scripts/Makefile.lib
* Adds the HAVE_KERNEL_ZSTD and KERNEL_ZSTD options

Architecture specific support is still needed for decompression.

---
 init/Kconfig         | 15 ++++++++++++++-
 scripts/Makefile.lib | 15 +++++++++++++++
 2 files changed, 29 insertions(+), 1 deletion(-)
init/Kconfig +14 -1
index 20a6ac33761c..9b646a25918e 100644
@@ -173,13 +173,16 @@ config HAVE_KERNEL_LZO
 config HAVE_KERNEL_LZ4
 	bool
 
+config HAVE_KERNEL_ZSTD
+	bool
+
 config HAVE_KERNEL_UNCOMPRESSED
 	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 || HAVE_KERNEL_UNCOMPRESSED
+	depends on HAVE_KERNEL_GZIP || HAVE_KERNEL_BZIP2 || HAVE_KERNEL_LZMA || HAVE_KERNEL_XZ || HAVE_KERNEL_LZO || HAVE_KERNEL_LZ4 || HAVE_KERNEL_ZSTD || HAVE_KERNEL_UNCOMPRESSED
 	help
 	  The linux kernel is a kind of self-extracting executable.
 	  Several compression algorithms are available, which differ
@@ -258,6 +261,16 @@ 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. The zstd command
+	  line tools is required for compression.
+
 config KERNEL_UNCOMPRESSED
 	bool "None"
 	depends on HAVE_KERNEL_UNCOMPRESSED
scripts/Makefile.lib +15 -0
index 752ff0a225a9..4b99893efa3d 100644
@@ -394,6 +394,21 @@ quiet_cmd_xzkern = XZKERN  $@
 quiet_cmd_xzmisc = XZMISC  $@
       cmd_xzmisc = cat $(real-prereqs) | xz --check=crc32 --lzma2=dict=1MiB > $@
 
+# 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
 # ---------------------------------------------------------------------------
 
Signature · 1 line
2.26.0
#5 lore raw

PATCH v4 5/8 usr: add support for zstd compressed initramfs

In reply to Nick Terrell

From: Nick Terrell <[email protected]>

* Add support for a zstd compressed initramfs.
* Add compression for compressing built-in initramfs with zstd.

I have tested this patch by boot testing with buildroot and QEMU. Specifically, I booted the kernel with both a zstd and gzip compressed initramfs, both built into the kernel and separate. I ensured that the correct compression algorithm was used. I tested on arm, aarch64, i386, and x86_64.

This patch has been tested in production on aarch64 and x86_64 devices.

Additionally, I have performance measurements from internal use in production. On an aarch64 device we saw 19 second boot time improvement from switching from lzma to zstd (27 seconds to 8 seconds). On an x86_64 device we saw a 9 second boot time reduction from switching from xz to zstd.

---
 usr/Kconfig  | 20 ++++++++++++++++++++
 usr/Makefile |  1 +
 2 files changed, 21 insertions(+)
usr/Kconfig +20 -0
index bdf5bbd40727..43aca37d09b5 100644
@@ -100,6 +100,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 != ""
@@ -207,4 +216,15 @@ 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
usr/Makefile +1 -0
index c12e6b15ce72..b1a81a40eab1 100644
@@ -15,6 +15,7 @@ compress-$(CONFIG_INITRAMFS_COMPRESSION_LZMA)	:= lzma
 compress-$(CONFIG_INITRAMFS_COMPRESSION_XZ)	:= xzmisc
 compress-$(CONFIG_INITRAMFS_COMPRESSION_LZO)	:= lzo
 compress-$(CONFIG_INITRAMFS_COMPRESSION_LZ4)	:= lz4
+compress-$(CONFIG_INITRAMFS_COMPRESSION_ZSTD)	:= zstd
 
 obj-$(CONFIG_BLK_DEV_INITRD) := initramfs_data.o
 
Signature · 1 line
2.26.0
#6 lore raw

PATCH v4 6/8 x86: bump ZO_z_extra_bytes margin for zstd

In reply to Nick Terrell

From: Nick Terrell <[email protected]>

Bump the ZO_z_extra_bytes margin for zstd.

Zstd needs 3 bytes per 128 KB, and has a 22 byte fixed overhead. Zstd needs to maintain 128 KB of space at all times, since that is the maximum block size. See the comments regarding in-place decompression added in lib/decompress_unzstd.c for details.

---
 arch/x86/boot/header.S | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)
arch/x86/boot/header.S +7 -1
index 97d9b6d6c1af..b820875c5c95 100644
@@ -536,8 +536,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)
Signature · 1 line
2.26.0
maintainer
#7 lore raw

Re: [PATCH v4 6/8] x86: bump ZO_z_extra_bytes margin for zstd

Quoted 27 lines · Nick Terrell

From: Nick Terrell <[email protected]>

Bump the ZO_z_extra_bytes margin for zstd.

Zstd needs 3 bytes per 128 KB, and has a 22 byte fixed overhead. Zstd needs to maintain 128 KB of space at all times, since that is the maximum block size. See the comments regarding in-place decompression added in lib/decompress_unzstd.c for details.

---
 arch/x86/boot/header.S | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)
arch/x86/boot/header.S +2 -0
index 97d9b6d6c1af..b820875c5c95 100644
@@ -536,8 +536,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

arch/x86/boot/header.S pref_address: .quad LOAD_PHYSICAL_ADDR # preferred load addr · line 549

Quoted 10 lines
arch/x86/boot/header.S +5 -1
+# 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)

So why is this change unconditional if only this compression alg. needs it?

Signature · 4 lines
Regards/Gruss,
    Boris.

https://people.kernel.org/tglx/notes-about-netiquette
maintainer
#8 lore raw

Re: [PATCH v4 6/8] x86: bump ZO_z_extra_bytes margin for zstd

Quoted 36 lines · Borislav Petkov
Quoted 31 lines · Nick Terrell

From: Nick Terrell <[email protected]>

Bump the ZO_z_extra_bytes margin for zstd.

Zstd needs 3 bytes per 128 KB, and has a 22 byte fixed overhead. Zstd needs to maintain 128 KB of space at all times, since that is the maximum block size. See the comments regarding in-place decompression added in lib/decompress_unzstd.c for details.

---
arch/x86/boot/header.S | 8 +++++++-

1 file changed, 7 insertions(+), 1 deletion(-)
arch/x86/boot/header.S +6 -0
index 97d9b6d6c1af..b820875c5c95 100644
@@ -536,8 +536,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
 
Quoted 9 lines

arch/x86/boot/header.S pref_address: .quad LOAD_PHYSICAL_ADDR # preferred load addr · line 549

Quoted 6 lines
arch/x86/boot/header.S +1 -1
-#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)

So why is this change unconditional if only this compression alg. needs it?

The code is currently written so that all the compression algorithms use the same ZO_z_extra_bytes. It is taken to be the maximum of the growth rate plus the maximum fixed overhead. Just a few lines above is the comment:

# … Hence safety

# margin should be updated to cover all decompressors so that we don't
# need to deal with each of them separately. Please check
# the description in lib/decompressor_xxx.c for specific information.

So I was been following the guidance in the comments. If we want to refactor it to handle each compressor individually we could make ZO_z_extra_bytes smaller for most algorithms.

Does it matter? I’m not an expert here, but it seems to me that requiring an extra 64 KB of RAM for kernel decompression isn’t such an onerous addition.

Best,
Nick

maintainer
#9 lore raw

Re: [PATCH v4 6/8] x86: bump ZO_z_extra_bytes margin for zstd

Quoted 10 lines · Nick Terrell

The code is currently written so that all the compression algorithms use the same ZO_z_extra_bytes. It is taken to be the maximum of the growth rate plus the maximum fixed overhead. Just a few lines above is the comment:

# … Hence safety

# margin should be updated to cover all decompressors so that we don't
# need to deal with each of them separately. Please check
# the description in lib/decompressor_xxx.c for specific information.

So I was been following the guidance in the comments.

Please state that in the commit message when you send your next revision.

Quoted 1 line

Does it matter? I’m not an expert here,

Huh, you're only sending the code then? Or what do you mean with not being an expert?

Thx.

Signature · 4 lines
Regards/Gruss,
    Boris.

https://people.kernel.org/tglx/notes-about-netiquette
maintainer
#10 lore raw

Re: [PATCH v4 6/8] x86: bump ZO_z_extra_bytes margin for zstd

Quoted 14 lines · Borislav Petkov
Quoted 9 lines · Nick Terrell

The code is currently written so that all the compression algorithms use the same ZO_z_extra_bytes. It is taken to be the maximum of the growth rate plus the maximum fixed overhead. Just a few lines above is the comment:

# … Hence safety

# margin should be updated to cover all decompressors so that we don't
# need to deal with each of them separately. Please check
# the description in lib/decompressor_xxx.c for specific information.
Quoted 4 lines
Quoted 1 line

So I was been following the guidance in the comments.

Please state that in the commit message when you send your next revision.

Will do.

Quoted 4 lines
Quoted 1 line

Does it matter? I’m not an expert here,

Huh, you're only sending the code then? Or what do you mean with not being an expert?

I mean that while I’ve read and understood this piece of the code, have tested the patches, have followed the template of other compression methods added, and am confident in the correctness of the code, I’m not a regular contributor to the pre-boot x86 kernel code. So it is possible that there is a use case for kernel compression that I’m not aware of where RAM is extremely tight and within 64 KB of the current limits.

It seems to me that adding 64KB to the memory requirement for kernel decompression is not going to break anyone. If it did the kernel image is taking up nearly all available RAM, which doesn’t seem likely. But, I don’t know all use cases. If it does break someone, we can put up a separate patch that switches all the compression methods over a per-method ZO_z_extra_bytes.

Best,
Nick

maintainer
#11 lore raw

Re: [PATCH v4 6/8] x86: bump ZO_z_extra_bytes margin for zstd

Quoted 3 lines · Nick Terrell

So it is possible that there is a use case for kernel compression that I’m not aware of where RAM is extremely tight and within 64 KB of the current limits.

That's exactly my concern, albeit a very minor one.

Quoted 6 lines

It seems to me that adding 64KB to the memory requirement for kernel decompression is not going to break anyone. If it did the kernel image is taking up nearly all available RAM, which doesn’t seem likely. But, I don’t know all use cases. If it does break someone, we can put up a separate patch that switches all the compression methods over a per-method ZO_z_extra_bytes.

Ok.

Thx.

Signature · 4 lines
Regards/Gruss,
    Boris.

https://people.kernel.org/tglx/notes-about-netiquette
#12 lore raw

Re: [PATCH v4 6/8] x86: bump ZO_z_extra_bytes margin for zstd

In reply to Nick Terrell
Quoted 34 lines · Nick Terrell
Quoted 15 lines · Borislav Petkov
Quoted 9 lines · Nick Terrell

The code is currently written so that all the compression algorithms use the same ZO_z_extra_bytes. It is taken to be the maximum of the growth rate plus the maximum fixed overhead. Just a few lines above is the comment:

# … Hence safety

# margin should be updated to cover all decompressors so that we don't
# need to deal with each of them separately. Please check
# the description in lib/decompressor_xxx.c for specific information.
Quoted 4 lines
Quoted 1 line

So I was been following the guidance in the comments.

Please state that in the commit message when you send your next revision.

Will do.

Quoted 4 lines
Quoted 1 line

Does it matter? I’m not an expert here,

Huh, you're only sending the code then? Or what do you mean with not being an expert?

I mean that while I’ve read and understood this piece of the code, have tested the patches, have followed the template of other compression methods added, and am confident in the correctness of the code, I’m not a regular contributor to the pre-boot x86 kernel code. So it is possible that there is a use case for kernel compression that I’m not aware of where RAM is extremely tight and within 64 KB of the current limits.

Quoted 6 lines

It seems to me that adding 64KB to the memory requirement for kernel decompression is not going to break anyone. If it did the kernel image is taking up nearly all available RAM, which doesn’t seem likely. But, I don’t know all use cases. If it does break someone, we can put up a separate patch that switches all the compression methods over a per-method ZO_z_extra_bytes.

Hi Nick,

are you planning a zstd-v5?
If yes, please CC me, thanks.

Regards,
- Sedat -

#13 lore raw

PATCH v4 7/8 x86: Add support for ZSTD compressed kernel

In reply to Nick Terrell

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.

---
 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(-)
Documentation/x86/boot.rst +3 -3
index c9c201596c3e..cedcf4d49bf0 100644
@@ -786,9 +786,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
arch/x86/Kconfig +1 -0
index beea77046f9b..12d88997a3a6 100644
@@ -183,6 +183,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
arch/x86/boot/compressed/Makefile +4 -1
index 26050ae0b27e..8233f598f15b 100644
@@ -24,7 +24,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 $@
       cmd_mkpiggy = $(obj)/mkpiggy $< > $@
arch/x86/boot/compressed/misc.c +4 -0
index 9652d5c2afda..39e592d0e0b4 100644
@@ -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.
arch/x86/include/asm/boot.h +4 -2
index 680c320363db..d6dd43d25d9f 100644
@@ -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
 
Signature · 1 line
2.26.0
#14 lore raw

PATCH v4 8/8 .gitignore: add ZSTD-compressed files

In reply to Nick Terrell

From: Adam Borowski <[email protected]>

For now, that's arch/x86/boot/compressed/vmlinux.bin.zst but probably more will come, thus let's be consistent with all other compressors.

---
 .gitignore | 1 +
 1 file changed, 1 insertion(+)
.gitignore +1 -0
index 72ef86a5570d..edb0191c294f 100644
@@ -43,6 +43,7 @@
 *.tab.[ch]
 *.tar
 *.xz
+*.zst
 Module.symvers
 modules.builtin
 modules.order
Signature · 1 line
2.26.0
Tested-by Gabriel Craciunescu on the v4 series
#15 lore raw
In reply to Nick Terrell
Quoted 3 lines · Nick Terrell

From: Nick Terrell <[email protected]>

Hi all,

Hi Nick,

Quoted 15 lines

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.

Quoted 8 lines

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

I tested this and already v2 and v3 on some boxes without a problem.

Also I've tested :

XZ compressed kernel ZSTD compressed initramfs ( XZ compressed modules )

XZ compressed kernel ZSTD compressed initramfs ( ZSTD compressed modules , that need an kmod patch )

ZSTD compressed kernel ZSTD compressed initramfs ( ZSTD compressed modules, that need an kmod patch )

ZSTD compressed kernel XZ compressed initramfs ( ZSTD/XZ compressed modules )

Quoted 8 lines

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.

I can confirm that on my server I tested the patches decompression went down

6 secs and 3.1 seconds faster boot time with zstd compressed kernel.

Also I see around 2++seconds faster boot across all testing boxes.

Quoted 31 lines

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

Quoted 6 lines

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.

Quoted 39 lines

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

#16 lore raw
In reply to Nick Terrell
Quoted 69 lines · Nick Terrell

From: Nick Terrell <[email protected]>

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

Quoted 7 lines

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.

Hi Nick,

thanks for version 4.

I have re-tested against Linux v5.6 final and it boots fine with a ZSTD-compressed initramfs on Debian/testing AMD64.

Regards,
- Sedat -

Quoted 42 lines

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