linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs
@ 2020-07-30 19:08 Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 1/8] lib: prepare zstd for preboot environment Nick Terrell
                   ` (10 more replies)
  0 siblings, 11 replies; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Nick Terrell <terrelln@fb.com>

Please pull from

  git@github.com:terrelln/linux.git tags/v10-zstd

to get these changes. Alternatively the patchset is included.

Hi all,

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

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

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

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

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

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

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

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

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

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

Alex Xu ran benchmarks in https://lkml.org/lkml/2020/7/1/722.

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

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

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

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

v5 -> v6:
- Rebase onto v5.8-rc4

v6 -> v7:
- (1/7) Don't define or use 'ZSTD_PREBOOT' to hide exports
- (2/8) Drop 'lib: prepare xxhash for preboot environment'
- (2/7) Use '__DISABLE_EXPORTS' in unzstd to hide exports
- (3/7) Update zstd compression cmd to follow other compressors
- (3/7) Add zstd22 cmd
- (6/7) Use zstd -22 --ultra (zstd22) for x86 kernel compression

v7 -> v8:
- (2/7) Don't define '__DISABLE_EXPORTS'
- (6/7) Define '__DISABLE_EXPORTS' in misc.c

v8 -> v9:
- Rebase onto v5.8-rc7
- (2/7) Fix nits about comment style & typos
- (3/7) Fix typo in init/Kconfig description
- (6/7) Explain BOOT_HEAP_SIZE increase and define __DISABLE_EXPORTS in
        Makefile KBUILD_CFLAGS and remove definitions from kaslr.c and misc.c

v9 -> v10:
- (6/8) Fix commit message regarding __DISABLE_EXPORTS
- (8/8) Add .zst files to Documentation/dontdiff

Best,
Nick Terrell

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

Nick Terrell (7):
  lib: prepare zstd 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
  Documentation: dontdiff: Add zstd compressed files

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

-- 
2.27.0


^ permalink raw reply	[flat|nested] 17+ messages in thread

* [PATCH v10 1/8] lib: prepare zstd for preboot environment
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
@ 2020-07-30 19:08 ` Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 2/8] lib: add zstd support to decompress Nick Terrell
                   ` (9 subsequent siblings)
  10 siblings, 0 replies; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Nick Terrell <terrelln@fb.com>

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

Reviewed-by: Kees Cook <keescook@chromium.org>
Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
Signed-off-by: Nick Terrell <terrelln@fb.com>
---
 lib/zstd/fse_decompress.c |  9 +--------
 lib/zstd/zstd_internal.h  | 14 ++++++++++++--
 2 files changed, 13 insertions(+), 10 deletions(-)

diff --git a/lib/zstd/fse_decompress.c b/lib/zstd/fse_decompress.c
index a84300e5a013..0b353530fb3f 100644
--- a/lib/zstd/fse_decompress.c
+++ b/lib/zstd/fse_decompress.c
@@ -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
 ****************************************************************/
diff --git a/lib/zstd/zstd_internal.h b/lib/zstd/zstd_internal.h
index 1a79fab9e13a..dac753397f86 100644
--- a/lib/zstd/zstd_internal.h
+++ b/lib/zstd/zstd_internal.h
@@ -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;
-- 
2.27.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH v10 2/8] lib: add zstd support to decompress
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 1/8] lib: prepare zstd for preboot environment Nick Terrell
@ 2020-07-30 19:08 ` Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 3/8] init: add support for zstd compressed kernel Nick Terrell
                   ` (8 subsequent siblings)
  10 siblings, 0 replies; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Nick Terrell <terrelln@fb.com>

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

Reviewed-by: Kees Cook <keescook@chromium.org>
Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
Signed-off-by: Nick Terrell <terrelln@fb.com>
---
 include/linux/decompress/unzstd.h |  11 +
 lib/Kconfig                       |   4 +
 lib/Makefile                      |   1 +
 lib/decompress.c                  |   5 +
 lib/decompress_unzstd.c           | 345 ++++++++++++++++++++++++++++++
 5 files changed, 366 insertions(+)
 create mode 100644 include/linux/decompress/unzstd.h
 create mode 100644 lib/decompress_unzstd.c

diff --git a/include/linux/decompress/unzstd.h b/include/linux/decompress/unzstd.h
new file mode 100644
index 000000000000..56d539ae880f
--- /dev/null
+++ b/include/linux/decompress/unzstd.h
@@ -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
diff --git a/lib/Kconfig b/lib/Kconfig
index df3f3da95990..a5d6f23c4cab 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -342,6 +342,10 @@ config DECOMPRESS_LZ4
 	select LZ4_DECOMPRESS
 	tristate
 
+config DECOMPRESS_ZSTD
+	select ZSTD_DECOMPRESS
+	tristate
+
 #
 # Generic allocator support is selected if needed
 #
diff --git a/lib/Makefile b/lib/Makefile
index b1c42c10073b..2ba9642a3a87 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -170,6 +170,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
diff --git a/lib/decompress.c b/lib/decompress.c
index 857ab1af1ef3..ab3fc90ffc64 100644
--- a/lib/decompress.c
+++ b/lib/decompress.c
@@ -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 }
 };
 
diff --git a/lib/decompress_unzstd.c b/lib/decompress_unzstd.c
new file mode 100644
index 000000000000..0ad2c15479ed
--- /dev/null
+++ b/lib/decompress_unzstd.c
@@ -0,0 +1,345 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * Important notes about in-place decompression
+ *
+ * At least on x86, the kernel is decompressed in place: the compressed data
+ * is placed to the end of the output buffer, and the decompressor overwrites
+ * most of the compressed data. There must be enough safety margin to
+ * guarantee that the write position is always behind the read position.
+ *
+ * The safety margin for ZSTD with a 128 KB block size is calculated below.
+ * Note that the margin with ZSTD is bigger than with GZIP or XZ!
+ *
+ * The worst case for in-place decompression is that the beginning of
+ * the file is compressed extremely well, and the rest of the file is
+ * uncompressible. Thus, we must look for worst-case expansion when the
+ * compressor is encoding uncompressible data.
+ *
+ * The structure of the .zst file in case of a compresed kernel is as follows.
+ * Maximum sizes (as bytes) of the fields are in parenthesis.
+ *
+ *    Frame Header: (18)
+ *    Blocks: (N)
+ *    Checksum: (4)
+ *
+ * The frame header and checksum overhead is at most 22 bytes.
+ *
+ * ZSTD stores the data in blocks. Each block has a header whose size is
+ * a 3 bytes. After the block header, there is up to 128 KB of payload.
+ * The maximum uncompressed size of the payload is 128 KB. The minimum
+ * uncompressed size of the payload is never less than the payload size
+ * (excluding the block header).
+ *
+ * The assumption, that the uncompressed size of the payload is never
+ * smaller than the payload itself, is valid only when talking about
+ * the payload as a whole. It is possible that the payload has parts where
+ * the decompressor consumes more input than it produces output. Calculating
+ * the worst case for this would be tricky. Instead of trying to do that,
+ * let's simply make sure that the decompressor never overwrites any bytes
+ * of the payload which it is currently reading.
+ *
+ * Now we have enough information to calculate the safety margin. We need
+ *   - 22 bytes for the .zst file format headers;
+ *   - 3 bytes per every 128 KiB of uncompressed size (one block header per
+ *     block); and
+ *   - 128 KiB (biggest possible zstd block size) to make sure that the
+ *     decompressor never overwrites anything from the block it is currently
+ *     reading.
+ *
+ * We get the following formula:
+ *
+ *    safety_margin = 22 + uncompressed_size * 3 / 131072 + 131072
+ *                 <= 22 + (uncompressed_size >> 15) + 131072
+ */
+
+/*
+ * Preboot environments #include "path/to/decompress_unzstd.c".
+ * All of the source files we depend on must be #included.
+ * zstd's only source dependeny is xxhash, which has no source
+ * dependencies.
+ *
+ * When UNZSTD_PREBOOT is defined we declare __decompress(), which is
+ * used for kernel decompression, instead of unzstd().
+ *
+ * Define __DISABLE_EXPORTS in preboot environments to prevent symbols
+ * from xxhash and zstd from being exported by the EXPORT_SYMBOL macro.
+ */
+#ifdef STATIC
+# define UNZSTD_PREBOOT
+# include "xxhash.c"
+# include "zstd/entropy_common.c"
+# include "zstd/fse_decompress.c"
+# include "zstd/huf_decompress.c"
+# include "zstd/zstd_common.c"
+# include "zstd/decompress.c"
+#endif
+
+#include <linux/decompress/mm.h>
+#include <linux/kernel.h>
+#include <linux/zstd.h>
+
+/* 128MB is the maximum window size supported by zstd. */
+#define ZSTD_WINDOWSIZE_MAX	(1 << ZSTD_WINDOWLOG_MAX)
+/*
+ * Size of the input and output buffers in multi-call mode.
+ * Pick a larger size because it isn't used during kernel decompression,
+ * since that is single pass, and we have to allocate a large buffer for
+ * zstd's window anyway. The larger size speeds up initramfs decompression.
+ */
+#define ZSTD_IOBUF_SIZE		(1 << 17)
+
+static int INIT handle_zstd_error(size_t ret, void (*error)(char *x))
+{
+	const int err = ZSTD_getErrorCode(ret);
+
+	if (!ZSTD_isError(ret))
+		return 0;
+
+	switch (err) {
+	case ZSTD_error_memory_allocation:
+		error("ZSTD decompressor ran out of memory");
+		break;
+	case ZSTD_error_prefix_unknown:
+		error("Input is not in the ZSTD format (wrong magic bytes)");
+		break;
+	case ZSTD_error_dstSize_tooSmall:
+	case ZSTD_error_corruption_detected:
+	case ZSTD_error_checksum_wrong:
+		error("ZSTD-compressed data is corrupt");
+		break;
+	default:
+		error("ZSTD-compressed data is probably corrupt");
+		break;
+	}
+	return -1;
+}
+
+/*
+ * Handle the case where we have the entire input and output in one segment.
+ * We can allocate less memory (no circular buffer for the sliding window),
+ * and avoid some memcpy() calls.
+ */
+static int INIT decompress_single(const u8 *in_buf, long in_len, u8 *out_buf,
+				  long out_len, long *in_pos,
+				  void (*error)(char *x))
+{
+	const size_t wksp_size = ZSTD_DCtxWorkspaceBound();
+	void *wksp = large_malloc(wksp_size);
+	ZSTD_DCtx *dctx = ZSTD_initDCtx(wksp, wksp_size);
+	int err;
+	size_t ret;
+
+	if (dctx == NULL) {
+		error("Out of memory while allocating ZSTD_DCtx");
+		err = -1;
+		goto out;
+	}
+	/*
+	 * Find out how large the frame actually is, there may be junk at
+	 * the end of the frame that ZSTD_decompressDCtx() can't handle.
+	 */
+	ret = ZSTD_findFrameCompressedSize(in_buf, in_len);
+	err = handle_zstd_error(ret, error);
+	if (err)
+		goto out;
+	in_len = (long)ret;
+
+	ret = ZSTD_decompressDCtx(dctx, out_buf, out_len, in_buf, in_len);
+	err = handle_zstd_error(ret, error);
+	if (err)
+		goto out;
+
+	if (in_pos != NULL)
+		*in_pos = in_len;
+
+	err = 0;
+out:
+	if (wksp != NULL)
+		large_free(wksp);
+	return err;
+}
+
+static int INIT __unzstd(unsigned char *in_buf, long in_len,
+			 long (*fill)(void*, unsigned long),
+			 long (*flush)(void*, unsigned long),
+			 unsigned char *out_buf, long out_len,
+			 long *in_pos,
+			 void (*error)(char *x))
+{
+	ZSTD_inBuffer in;
+	ZSTD_outBuffer out;
+	ZSTD_frameParams params;
+	void *in_allocated = NULL;
+	void *out_allocated = NULL;
+	void *wksp = NULL;
+	size_t wksp_size;
+	ZSTD_DStream *dstream;
+	int err;
+	size_t ret;
+
+	if (out_len == 0)
+		out_len = LONG_MAX; /* no limit */
+
+	if (fill == NULL && flush == NULL)
+		/*
+		 * We can decompress faster and with less memory when we have a
+		 * single chunk.
+		 */
+		return decompress_single(in_buf, in_len, out_buf, out_len,
+					 in_pos, error);
+
+	/*
+	 * If in_buf is not provided, we must be using fill(), so allocate
+	 * a large enough buffer. If it is provided, it must be at least
+	 * ZSTD_IOBUF_SIZE large.
+	 */
+	if (in_buf == NULL) {
+		in_allocated = large_malloc(ZSTD_IOBUF_SIZE);
+		if (in_allocated == NULL) {
+			error("Out of memory while allocating input buffer");
+			err = -1;
+			goto out;
+		}
+		in_buf = in_allocated;
+		in_len = 0;
+	}
+	/* Read the first chunk, since we need to decode the frame header. */
+	if (fill != NULL)
+		in_len = fill(in_buf, ZSTD_IOBUF_SIZE);
+	if (in_len < 0) {
+		error("ZSTD-compressed data is truncated");
+		err = -1;
+		goto out;
+	}
+	/* Set the first non-empty input buffer. */
+	in.src = in_buf;
+	in.pos = 0;
+	in.size = in_len;
+	/* Allocate the output buffer if we are using flush(). */
+	if (flush != NULL) {
+		out_allocated = large_malloc(ZSTD_IOBUF_SIZE);
+		if (out_allocated == NULL) {
+			error("Out of memory while allocating output buffer");
+			err = -1;
+			goto out;
+		}
+		out_buf = out_allocated;
+		out_len = ZSTD_IOBUF_SIZE;
+	}
+	/* Set the output buffer. */
+	out.dst = out_buf;
+	out.pos = 0;
+	out.size = out_len;
+
+	/*
+	 * We need to know the window size to allocate the ZSTD_DStream.
+	 * Since we are streaming, we need to allocate a buffer for the sliding
+	 * window. The window size varies from 1 KB to ZSTD_WINDOWSIZE_MAX
+	 * (8 MB), so it is important to use the actual value so as not to
+	 * waste memory when it is smaller.
+	 */
+	ret = ZSTD_getFrameParams(&params, in.src, in.size);
+	err = handle_zstd_error(ret, error);
+	if (err)
+		goto out;
+	if (ret != 0) {
+		error("ZSTD-compressed data has an incomplete frame header");
+		err = -1;
+		goto out;
+	}
+	if (params.windowSize > ZSTD_WINDOWSIZE_MAX) {
+		error("ZSTD-compressed data has too large a window size");
+		err = -1;
+		goto out;
+	}
+
+	/*
+	 * Allocate the ZSTD_DStream now that we know how much memory is
+	 * required.
+	 */
+	wksp_size = ZSTD_DStreamWorkspaceBound(params.windowSize);
+	wksp = large_malloc(wksp_size);
+	dstream = ZSTD_initDStream(params.windowSize, wksp, wksp_size);
+	if (dstream == NULL) {
+		error("Out of memory while allocating ZSTD_DStream");
+		err = -1;
+		goto out;
+	}
+
+	/*
+	 * Decompression loop:
+	 * Read more data if necessary (error if no more data can be read).
+	 * Call the decompression function, which returns 0 when finished.
+	 * Flush any data produced if using flush().
+	 */
+	if (in_pos != NULL)
+		*in_pos = 0;
+	do {
+		/*
+		 * If we need to reload data, either we have fill() and can
+		 * try to get more data, or we don't and the input is truncated.
+		 */
+		if (in.pos == in.size) {
+			if (in_pos != NULL)
+				*in_pos += in.pos;
+			in_len = fill ? fill(in_buf, ZSTD_IOBUF_SIZE) : -1;
+			if (in_len < 0) {
+				error("ZSTD-compressed data is truncated");
+				err = -1;
+				goto out;
+			}
+			in.pos = 0;
+			in.size = in_len;
+		}
+		/* Returns zero when the frame is complete. */
+		ret = ZSTD_decompressStream(dstream, &out, &in);
+		err = handle_zstd_error(ret, error);
+		if (err)
+			goto out;
+		/* Flush all of the data produced if using flush(). */
+		if (flush != NULL && out.pos > 0) {
+			if (out.pos != flush(out.dst, out.pos)) {
+				error("Failed to flush()");
+				err = -1;
+				goto out;
+			}
+			out.pos = 0;
+		}
+	} while (ret != 0);
+
+	if (in_pos != NULL)
+		*in_pos += in.pos;
+
+	err = 0;
+out:
+	if (in_allocated != NULL)
+		large_free(in_allocated);
+	if (out_allocated != NULL)
+		large_free(out_allocated);
+	if (wksp != NULL)
+		large_free(wksp);
+	return err;
+}
+
+#ifndef UNZSTD_PREBOOT
+STATIC int INIT unzstd(unsigned char *buf, long len,
+		       long (*fill)(void*, unsigned long),
+		       long (*flush)(void*, unsigned long),
+		       unsigned char *out_buf,
+		       long *pos,
+		       void (*error)(char *x))
+{
+	return __unzstd(buf, len, fill, flush, out_buf, 0, pos, error);
+}
+#else
+STATIC int INIT __decompress(unsigned char *buf, long len,
+			     long (*fill)(void*, unsigned long),
+			     long (*flush)(void*, unsigned long),
+			     unsigned char *out_buf, long out_len,
+			     long *pos,
+			     void (*error)(char *x))
+{
+	return __unzstd(buf, len, fill, flush, out_buf, out_len, pos, error);
+}
+#endif
-- 
2.27.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH v10 3/8] init: add support for zstd compressed kernel
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 1/8] lib: prepare zstd for preboot environment Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 2/8] lib: add zstd support to decompress Nick Terrell
@ 2020-07-30 19:08 ` Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 4/8] usr: add support for zstd compressed initramfs Nick Terrell
                   ` (7 subsequent siblings)
  10 siblings, 0 replies; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Nick Terrell <terrelln@fb.com>

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

Architecture specific support is still needed for decompression.

Reviewed-by: Kees Cook <keescook@chromium.org>
Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
Signed-off-by: Nick Terrell <terrelln@fb.com>
---
 Makefile             |  3 ++-
 init/Kconfig         | 15 ++++++++++++++-
 scripts/Makefile.lib | 22 ++++++++++++++++++++++
 3 files changed, 38 insertions(+), 2 deletions(-)

diff --git a/Makefile b/Makefile
index 229e67f2ff75..565084f347bd 100644
--- a/Makefile
+++ b/Makefile
@@ -464,6 +464,7 @@ KLZOP		= lzop
 LZMA		= lzma
 LZ4		= lz4c
 XZ		= xz
+ZSTD		= zstd
 
 CHECKFLAGS     := -D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ \
 		  -Wbitwise -Wno-return-void -Wno-unknown-attribute $(CF)
@@ -512,7 +513,7 @@ CLANG_FLAGS :=
 export ARCH SRCARCH CONFIG_SHELL BASH HOSTCC KBUILD_HOSTCFLAGS CROSS_COMPILE LD CC
 export CPP AR NM STRIP OBJCOPY OBJDUMP OBJSIZE READELF PAHOLE LEX YACC AWK INSTALLKERNEL
 export PERL PYTHON PYTHON3 CHECK CHECKFLAGS MAKE UTS_MACHINE HOSTCXX
-export KGZIP KBZIP2 KLZOP LZMA LZ4 XZ
+export KGZIP KBZIP2 KLZOP LZMA LZ4 XZ ZSTD
 export KBUILD_HOSTCXXFLAGS KBUILD_HOSTLDFLAGS KBUILD_HOSTLDLIBS LDFLAGS_MODULE
 
 export KBUILD_CPPFLAGS NOSTDINC_FLAGS LINUXINCLUDE OBJCOPYFLAGS KBUILD_LDFLAGS
diff --git a/init/Kconfig b/init/Kconfig
index 0498af567f70..2b6409fec53f 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -191,13 +191,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
@@ -276,6 +279,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 tool is required for compression.
+
 config KERNEL_UNCOMPRESSED
 	bool "None"
 	depends on HAVE_KERNEL_UNCOMPRESSED
diff --git a/scripts/Makefile.lib b/scripts/Makefile.lib
index 916b2f7f7098..54f7b7eb580b 100644
--- a/scripts/Makefile.lib
+++ b/scripts/Makefile.lib
@@ -413,6 +413,28 @@ 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.
+#
+# zstd uses a maximum window size of 8 MB. zstd22 uses a maximum window size of
+# 128 MB. zstd22 is used for kernel compression because it is decompressed in a
+# single pass, so zstd doesn't need to allocate a window buffer. When streaming
+# decompression is used, like initramfs decompression, zstd22 should likely not
+# be used because it would require zstd to allocate a 128 MB buffer.
+
+quiet_cmd_zstd = ZSTD    $@
+      cmd_zstd = { cat $(real-prereqs) | $(ZSTD) -19; $(size_append); } > $@
+
+quiet_cmd_zstd22 = ZSTD22  $@
+      cmd_zstd22 = { cat $(real-prereqs) | $(ZSTD) -22 --ultra; $(size_append); } > $@
+
 # ASM offsets
 # ---------------------------------------------------------------------------
 
-- 
2.27.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH v10 4/8] usr: add support for zstd compressed initramfs
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
                   ` (2 preceding siblings ...)
  2020-07-30 19:08 ` [PATCH v10 3/8] init: add support for zstd compressed kernel Nick Terrell
@ 2020-07-30 19:08 ` Nick Terrell
  2020-08-04  6:52   ` Geert Uytterhoeven
  2020-07-30 19:08 ` [PATCH v10 5/8] x86: bump ZO_z_extra_bytes margin for zstd Nick Terrell
                   ` (6 subsequent siblings)
  10 siblings, 1 reply; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Nick Terrell <terrelln@fb.com>

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

Reviewed-by: Kees Cook <keescook@chromium.org>
Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
Signed-off-by: Nick Terrell <terrelln@fb.com>
---
 usr/Kconfig  | 20 ++++++++++++++++++++
 usr/Makefile |  1 +
 2 files changed, 21 insertions(+)

diff --git a/usr/Kconfig b/usr/Kconfig
index 96afb03b65f9..2599bc21c1b2 100644
--- a/usr/Kconfig
+++ b/usr/Kconfig
@@ -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 != ""
@@ -196,6 +205,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.
+
 config INITRAMFS_COMPRESSION_NONE
 	bool "None"
 	help
diff --git a/usr/Makefile b/usr/Makefile
index c12e6b15ce72..b1a81a40eab1 100644
--- a/usr/Makefile
+++ b/usr/Makefile
@@ -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
 
-- 
2.27.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH v10 5/8] x86: bump ZO_z_extra_bytes margin for zstd
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
                   ` (3 preceding siblings ...)
  2020-07-30 19:08 ` [PATCH v10 4/8] usr: add support for zstd compressed initramfs Nick Terrell
@ 2020-07-30 19:08 ` Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 6/8] x86: Add support for ZSTD compressed kernel Nick Terrell
                   ` (5 subsequent siblings)
  10 siblings, 0 replies; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Nick Terrell <terrelln@fb.com>

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.

The existing code is 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. The comments just above this diff
state that:

Reviewed-by: Kees Cook <keescook@chromium.org>
Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
Signed-off-by: Nick Terrell <terrelln@fb.com>
---
 arch/x86/boot/header.S | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/arch/x86/boot/header.S b/arch/x86/boot/header.S
index 735ad7f21ab0..6dbd7e9f74c9 100644
--- a/arch/x86/boot/header.S
+++ b/arch/x86/boot/header.S
@@ -539,8 +539,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)
-- 
2.27.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH v10 6/8] x86: Add support for ZSTD compressed kernel
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
                   ` (4 preceding siblings ...)
  2020-07-30 19:08 ` [PATCH v10 5/8] x86: bump ZO_z_extra_bytes margin for zstd Nick Terrell
@ 2020-07-30 19:08 ` Nick Terrell
  2020-07-30 19:08 ` [PATCH v10 7/8] .gitignore: add ZSTD-compressed files Nick Terrell
                   ` (4 subsequent siblings)
  10 siblings, 0 replies; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Nick Terrell <terrelln@fb.com>

* Add support for zstd compressed kernel
* Define __DISABLE_EXPORTS in Makefile
* Remove __DISABLE_EXPORTS definition from kaslr.c
* 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.

__DISABLE_EXPORTS is now defined in the Makefile, which covers both
the existing use in kaslr.c, and the use needed by the zstd decompressor
in misc.c.

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

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

Reviewed-by: Kees Cook <keescook@chromium.org>
Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
Signed-off-by: Nick Terrell <terrelln@fb.com>
---
 Documentation/x86/boot.rst        |  6 +++---
 arch/x86/Kconfig                  |  1 +
 arch/x86/boot/compressed/Makefile |  6 +++++-
 arch/x86/boot/compressed/kaslr.c  |  7 -------
 arch/x86/boot/compressed/misc.c   |  4 ++++
 arch/x86/include/asm/boot.h       | 11 +++++++++--
 6 files changed, 22 insertions(+), 13 deletions(-)

diff --git a/Documentation/x86/boot.rst b/Documentation/x86/boot.rst
index 5325c71ca877..7fafc7ac00d7 100644
--- a/Documentation/x86/boot.rst
+++ b/Documentation/x86/boot.rst
@@ -782,9 +782,9 @@ Protocol:	2.08+
   uncompressed data should be determined using the standard magic
   numbers.  The currently supported compression formats are gzip
   (magic numbers 1F 8B or 1F 9E), bzip2 (magic number 42 5A), LZMA
-  (magic number 5D 00), XZ (magic number FD 37), and LZ4 (magic number
-  02 21).  The uncompressed payload is currently always ELF (magic
-  number 7F 45 4C 46).
+  (magic number 5D 00), XZ (magic number FD 37), LZ4 (magic number
+  02 21) and ZSTD (magic number 28 B5). The uncompressed payload is
+  currently always ELF (magic number 7F 45 4C 46).
 
 ============	==============
 Field name:	payload_length
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 883da0abf779..4a64395bc35d 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -188,6 +188,7 @@ config X86
 	select HAVE_KERNEL_LZMA
 	select HAVE_KERNEL_LZO
 	select HAVE_KERNEL_XZ
+	select HAVE_KERNEL_ZSTD
 	select HAVE_KPROBES
 	select HAVE_KPROBES_ON_FTRACE
 	select HAVE_FUNCTION_ERROR_INJECTION
diff --git a/arch/x86/boot/compressed/Makefile b/arch/x86/boot/compressed/Makefile
index 5a828fde7a42..c08714ae76ec 100644
--- a/arch/x86/boot/compressed/Makefile
+++ b/arch/x86/boot/compressed/Makefile
@@ -26,7 +26,7 @@ OBJECT_FILES_NON_STANDARD	:= y
 KCOV_INSTRUMENT		:= n
 
 targets := vmlinux vmlinux.bin vmlinux.bin.gz vmlinux.bin.bz2 vmlinux.bin.lzma \
-	vmlinux.bin.xz vmlinux.bin.lzo vmlinux.bin.lz4
+	vmlinux.bin.xz vmlinux.bin.lzo vmlinux.bin.lz4 vmlinux.bin.zst
 
 KBUILD_CFLAGS := -m$(BITS) -O2
 KBUILD_CFLAGS += -fno-strict-aliasing $(call cc-option, -fPIE, -fPIC)
@@ -42,6 +42,7 @@ KBUILD_CFLAGS += $(call cc-disable-warning, gnu)
 KBUILD_CFLAGS += -Wno-pointer-sign
 KBUILD_CFLAGS += $(call cc-option,-fmacro-prefix-map=$(srctree)/=)
 KBUILD_CFLAGS += -fno-asynchronous-unwind-tables
+KBUILD_CFLAGS += -D__DISABLE_EXPORTS
 
 KBUILD_AFLAGS  := $(KBUILD_CFLAGS) -D__ASSEMBLY__
 GCOV_PROFILE := n
@@ -145,6 +146,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,zstd22)
 
 suffix-$(CONFIG_KERNEL_GZIP)	:= gz
 suffix-$(CONFIG_KERNEL_BZIP2)	:= bz2
@@ -152,6 +155,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 $< > $@
diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index d7408af55738..0048269180d5 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -19,13 +19,6 @@
  */
 #define BOOT_CTYPE_H
 
-/*
- * _ctype[] in lib/ctype.c is needed by isspace() of linux/ctype.h.
- * While both lib/ctype.c and lib/cmdline.c will bring EXPORT_SYMBOL
- * which is meaningless and will cause compiling error in some cases.
- */
-#define __DISABLE_EXPORTS
-
 #include "misc.h"
 #include "error.h"
 #include "../string.h"
diff --git a/arch/x86/boot/compressed/misc.c b/arch/x86/boot/compressed/misc.c
index 9652d5c2afda..39e592d0e0b4 100644
--- a/arch/x86/boot/compressed/misc.c
+++ b/arch/x86/boot/compressed/misc.c
@@ -77,6 +77,10 @@ static int lines, cols;
 #ifdef CONFIG_KERNEL_LZ4
 #include "../../../../lib/decompress_unlz4.c"
 #endif
+
+#ifdef CONFIG_KERNEL_ZSTD
+#include "../../../../lib/decompress_unzstd.c"
+#endif
 /*
  * NOTE: When adding a new decompressor, please update the analysis in
  * ../header.S.
diff --git a/arch/x86/include/asm/boot.h b/arch/x86/include/asm/boot.h
index 680c320363db..9191280d9ea3 100644
--- a/arch/x86/include/asm/boot.h
+++ b/arch/x86/include/asm/boot.h
@@ -24,9 +24,16 @@
 # 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)
+/*
+ * Zstd needs to allocate the ZSTD_DCtx in order to decompress the kernel.
+ * The ZSTD_DCtx is ~160KB, so set the heap size to 192KB because it is a
+ * round number and to allow some slack.
+ */
+# define BOOT_HEAP_SIZE		 0x30000
+#else
 # define BOOT_HEAP_SIZE		 0x10000
 #endif
 
-- 
2.27.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH v10 7/8] .gitignore: add ZSTD-compressed files
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
                   ` (5 preceding siblings ...)
  2020-07-30 19:08 ` [PATCH v10 6/8] x86: Add support for ZSTD compressed kernel Nick Terrell
@ 2020-07-30 19:08 ` Nick Terrell
  2020-07-31  9:50   ` Ingo Molnar
  2020-07-30 19:08 ` [PATCH v10 8/8] Documentation: dontdiff: Add zstd compressed files Nick Terrell
                   ` (3 subsequent siblings)
  10 siblings, 1 reply; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Adam Borowski <kilobyte@angband.pl>

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.

Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
Reviewed-by: Kees Cook <keescook@chromium.org>
Signed-off-by: Nick Terrell <terrelln@fb.com>
Signed-off-by: Adam Borowski <kilobyte@angband.pl>
---
 .gitignore | 1 +
 1 file changed, 1 insertion(+)

diff --git a/.gitignore b/.gitignore
index d5f4804ed07c..162bd2b67bdf 100644
--- a/.gitignore
+++ b/.gitignore
@@ -44,6 +44,7 @@
 *.tab.[ch]
 *.tar
 *.xz
+*.zst
 Module.symvers
 modules.builtin
 modules.order
-- 
2.27.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH v10 8/8] Documentation: dontdiff: Add zstd compressed files
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
                   ` (6 preceding siblings ...)
  2020-07-30 19:08 ` [PATCH v10 7/8] .gitignore: add ZSTD-compressed files Nick Terrell
@ 2020-07-30 19:08 ` Nick Terrell
  2020-07-31  9:47 ` [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Sedat Dilek
                   ` (2 subsequent siblings)
  10 siblings, 0 replies; 17+ messages in thread
From: Nick Terrell @ 2020-07-30 19:08 UTC (permalink / raw)
  To: Borislav Petkov, Thomas Gleixner
  Cc: linux-kernel, Chris Mason, linux-kbuild, x86, gregkh, Petr Malat,
	Kees Cook, Kernel Team, Nick Terrell, Adam Borowski,
	Patrick Williams, rmikey, mingo, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

From: Nick Terrell <terrelln@fb.com>

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.

Signed-off-by: Nick Terrell <terrelln@fb.com>
---
 Documentation/dontdiff | 1 +
 1 file changed, 1 insertion(+)

diff --git a/Documentation/dontdiff b/Documentation/dontdiff
index ef9519c32c55..e361fc95ca29 100644
--- a/Documentation/dontdiff
+++ b/Documentation/dontdiff
@@ -55,6 +55,7 @@
 *.ver
 *.xml
 *.xz
+*.zst
 *_MODULES
 *_vga16.c
 *~
-- 
2.27.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* Re: [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
                   ` (7 preceding siblings ...)
  2020-07-30 19:08 ` [PATCH v10 8/8] Documentation: dontdiff: Add zstd compressed files Nick Terrell
@ 2020-07-31  9:47 ` Sedat Dilek
  2020-07-31 14:36 ` Sedat Dilek
  2020-08-04  6:47 ` Sedat Dilek
  10 siblings, 0 replies; 17+ messages in thread
From: Sedat Dilek @ 2020-07-31  9:47 UTC (permalink / raw)
  To: Nick Terrell
  Cc: Borislav Petkov, Thomas Gleixner, linux-kernel, Chris Mason,
	linux-kbuild, x86, gregkh, Petr Malat, Kees Cook, Kernel Team,
	Adam Borowski, Patrick Williams, rmikey, mingo, Patrick Williams,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

On Thu, Jul 30, 2020 at 9:11 PM Nick Terrell <nickrterrell@gmail.com> wrote:
>
> From: Nick Terrell <terrelln@fb.com>
>
> Please pull from
>
>   git@github.com:terrelln/linux.git tags/v10-zstd
>
> to get these changes. Alternatively the patchset is included.
>
> Hi all,
>
> This patch set adds support for a ZSTD-compressed kernel, ramdisk, and
> initramfs in the kernel boot process. ZSTD-compressed ramdisk and initramfs
> are supported on all architectures. The ZSTD-compressed kernel is only
> hooked up to x86 in this patch set.
>
> Zstandard requires slightly more memory during the kernel decompression
> on x86 (192 KB vs 64 KB), and the memory usage is independent of the
> window size.
>
> Zstandard requires memory proprortional to the window size used during
> compression for decompressing the ramdisk image, since streaming mode is
> used. Newer versions of zstd (1.3.2+) list the window size of a file
> with `zstd -lv <file>'. The absolute maximum amount of memory required
> is just over 8 MB, but it can be controlled at compression time.
>
> This patch set has been boot tested with buildroot and QEMU based off
> of linux-5.6-rc6.
>
> On i386 and x86_64 I have tested the following configurations:
> * zstd compressed kernel and a separate zstd compressed initramfs
> * zstd compressed kernel and a built-in zstd compressed initramfs
> * gzip compressed kernel and a separate gzip compressed initramfs
> * gzip compressed kernel and a built-in gzip compressed initramfs
>
> On arm and aarch64 I tested the same configurations, except that the kernel is
> always gzip compressed.
>
> Facebook has been using v1 of these patches on x86_64 devices for more than 6
> months. When we switched from a xz compressed initramfs to a zstd compressed
> initramfs decompression time shrunk from 12 seconds to 3 seconds. When we
> switched from a xz compressed kernel to a zstd compressed kernel we saved 2
> seconds of boot time.
>
> Facebook has been using v2 of these patches on aarch64 devices for a few weeks.
> When we switched from an lzma compressed initramfs to a zstd compressed initramfs
> decompression time shrunk from 27 seconds to 8 seconds.
>
> The zstd compressed kernel is smaller than the gzip compressed kernel but larger
> than the xz or lzma compressed kernels, and it decompresses faster than
> everything except lz4. See the table below for the measurement of an x86_64
> kernel ordered by compressed size:
>
> algo    size
> xz       6,509,792
> lzma     6,856,576
> zstd     7,399,157
> gzip     8,522,527
> bzip     8,629,603
> lzo      9,808,035
> lz4     10,705,570
> none    32,565,672
>
> Alex Xu ran benchmarks in https://lkml.org/lkml/2020/7/1/722.
>
> v1 -> v2:
> - Rebase
>   - usr/Makefile and init/Kconfig were changed so the patches were updated
> - No functional changes except to rebase
> - Split the patches up into smaller chunks
>
> v2 -> v3:
> - Add *.zst to the .gitignore in patch 8
> - Style nits in patch 3
> - Rename the PREBOOT macro to ZSTD_PREBOOT and XXH_PREBOOT in patches
>   1 through 3
>
> v3 -> v4:
> - Increase the ZSTD_IOBUF_SIZE from 4KB to 128KB to improve performance.
>   With this change I switch from malloc() to large_malloc() for the
>   buffers.
> - Increase the maximum allowed window size from 8 MB to 128 MB, which is
>   the max that zstd in the kernel supports.
>
> v4 -> v5:
> - Update commit message for patch 6 in response to comments
> - Rebase onto next-20200408
>
> v5 -> v6:
> - Rebase onto v5.8-rc4
>
> v6 -> v7:
> - (1/7) Don't define or use 'ZSTD_PREBOOT' to hide exports
> - (2/8) Drop 'lib: prepare xxhash for preboot environment'
> - (2/7) Use '__DISABLE_EXPORTS' in unzstd to hide exports
> - (3/7) Update zstd compression cmd to follow other compressors
> - (3/7) Add zstd22 cmd
> - (6/7) Use zstd -22 --ultra (zstd22) for x86 kernel compression
>
> v7 -> v8:
> - (2/7) Don't define '__DISABLE_EXPORTS'
> - (6/7) Define '__DISABLE_EXPORTS' in misc.c
>
> v8 -> v9:
> - Rebase onto v5.8-rc7
> - (2/7) Fix nits about comment style & typos
> - (3/7) Fix typo in init/Kconfig description
> - (6/7) Explain BOOT_HEAP_SIZE increase and define __DISABLE_EXPORTS in
>         Makefile KBUILD_CFLAGS and remove definitions from kaslr.c and misc.c
>
> v9 -> v10:
> - (6/8) Fix commit message regarding __DISABLE_EXPORTS
> - (8/8) Add .zst files to Documentation/dontdiff
>

Hi Nick,

Hope with version 10 of your patchset the review process has an end
and it will picked up into tip Git.

Again: Tested-by: Sedat Dilek <sedat.dilek@gmail.com>

Build-environments (more details see [1]):
#0: Debian/unstable AMD64
#1: LLVM v11.0.0-rc1 (clang-11, ld.lld-11 and LLVM "bin"utils)
#2: GCC v10.2 and GNU/ld.bfd v2.35 and GNU/binutils

With the best wishes,
- Sedat -

[1] https://github.com/ClangBuiltLinux/linux/issues/1086#issuecomment-667036028


> Best,
> Nick Terrell
>
> Adam Borowski (1):
>   .gitignore: add ZSTD-compressed files
>
> Nick Terrell (7):
>   lib: prepare zstd 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
>   Documentation: dontdiff: Add zstd compressed files
>
>  .gitignore                        |   1 +
>  Documentation/dontdiff            |   1 +
>  Documentation/x86/boot.rst        |   6 +-
>  Makefile                          |   3 +-
>  arch/x86/Kconfig                  |   1 +
>  arch/x86/boot/compressed/Makefile |   6 +-
>  arch/x86/boot/compressed/kaslr.c  |   7 -
>  arch/x86/boot/compressed/misc.c   |   4 +
>  arch/x86/boot/header.S            |   8 +-
>  arch/x86/include/asm/boot.h       |  11 +-
>  include/linux/decompress/unzstd.h |  11 +
>  init/Kconfig                      |  15 +-
>  lib/Kconfig                       |   4 +
>  lib/Makefile                      |   1 +
>  lib/decompress.c                  |   5 +
>  lib/decompress_unzstd.c           | 345 ++++++++++++++++++++++++++++++
>  lib/zstd/fse_decompress.c         |   9 +-
>  lib/zstd/zstd_internal.h          |  14 +-
>  scripts/Makefile.lib              |  22 ++
>  usr/Kconfig                       |  20 ++
>  usr/Makefile                      |   1 +
>  21 files changed, 469 insertions(+), 26 deletions(-)
>  create mode 100644 include/linux/decompress/unzstd.h
>  create mode 100644 lib/decompress_unzstd.c
>
> --
> 2.27.0
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v10 7/8] .gitignore: add ZSTD-compressed files
  2020-07-30 19:08 ` [PATCH v10 7/8] .gitignore: add ZSTD-compressed files Nick Terrell
@ 2020-07-31  9:50   ` Ingo Molnar
  2020-07-31 17:17     ` Nick Terrell
  0 siblings, 1 reply; 17+ messages in thread
From: Ingo Molnar @ 2020-07-31  9:50 UTC (permalink / raw)
  To: Nick Terrell, Adam Borowski
  Cc: Borislav Petkov, Thomas Gleixner, linux-kernel, Chris Mason,
	linux-kbuild, x86, gregkh, Petr Malat, Kees Cook, Kernel Team,
	Adam Borowski, Patrick Williams, rmikey, Patrick Williams,
	Sedat Dilek, Norbert Lange, Andrew Morton, Alex Xu,
	Masahiro Yamada, Nick Terrell


* Nick Terrell <nickrterrell@gmail.com> wrote:

> From: Adam Borowski <kilobyte@angband.pl>
> 
> 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.
> 
> Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
> Reviewed-by: Kees Cook <keescook@chromium.org>
> Signed-off-by: Nick Terrell <terrelln@fb.com>
> Signed-off-by: Adam Borowski <kilobyte@angband.pl>

I presume Adam Borowski's Signed-off-by was intended to be added as 
the first entry of the SOB chain?

I've added it, please let me know if that's not OK.

Thanks,

	Ingo

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
                   ` (8 preceding siblings ...)
  2020-07-31  9:47 ` [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Sedat Dilek
@ 2020-07-31 14:36 ` Sedat Dilek
  2020-08-04  6:47 ` Sedat Dilek
  10 siblings, 0 replies; 17+ messages in thread
From: Sedat Dilek @ 2020-07-31 14:36 UTC (permalink / raw)
  To: Nick Terrell
  Cc: Borislav Petkov, Thomas Gleixner, linux-kernel, Chris Mason,
	linux-kbuild, x86, gregkh, Petr Malat, Kees Cook, Kernel Team,
	Adam Borowski, Patrick Williams, rmikey, mingo, Patrick Williams,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

On Thu, Jul 30, 2020 at 9:11 PM Nick Terrell <nickrterrell@gmail.com> wrote:
>
> From: Nick Terrell <terrelln@fb.com>
>
> Please pull from
>
>   git@github.com:terrelln/linux.git tags/v10-zstd
>
> to get these changes. Alternatively the patchset is included.
>
> Hi all,
>
> This patch set adds support for a ZSTD-compressed kernel, ramdisk, and
> initramfs in the kernel boot process. ZSTD-compressed ramdisk and initramfs
> are supported on all architectures. The ZSTD-compressed kernel is only
> hooked up to x86 in this patch set.
>
> Zstandard requires slightly more memory during the kernel decompression
> on x86 (192 KB vs 64 KB), and the memory usage is independent of the
> window size.
>
> Zstandard requires memory proprortional to the window size used during
> compression for decompressing the ramdisk image, since streaming mode is
> used. Newer versions of zstd (1.3.2+) list the window size of a file
> with `zstd -lv <file>'. The absolute maximum amount of memory required
> is just over 8 MB, but it can be controlled at compression time.
>
> This patch set has been boot tested with buildroot and QEMU based off
> of linux-5.6-rc6.
>
> On i386 and x86_64 I have tested the following configurations:
> * zstd compressed kernel and a separate zstd compressed initramfs
> * zstd compressed kernel and a built-in zstd compressed initramfs
> * gzip compressed kernel and a separate gzip compressed initramfs
> * gzip compressed kernel and a built-in gzip compressed initramfs
>
> On arm and aarch64 I tested the same configurations, except that the kernel is
> always gzip compressed.
>
> Facebook has been using v1 of these patches on x86_64 devices for more than 6
> months. When we switched from a xz compressed initramfs to a zstd compressed
> initramfs decompression time shrunk from 12 seconds to 3 seconds. When we
> switched from a xz compressed kernel to a zstd compressed kernel we saved 2
> seconds of boot time.
>
> Facebook has been using v2 of these patches on aarch64 devices for a few weeks.
> When we switched from an lzma compressed initramfs to a zstd compressed initramfs
> decompression time shrunk from 27 seconds to 8 seconds.
>
> The zstd compressed kernel is smaller than the gzip compressed kernel but larger
> than the xz or lzma compressed kernels, and it decompresses faster than
> everything except lz4. See the table below for the measurement of an x86_64
> kernel ordered by compressed size:
>
> algo    size
> xz       6,509,792
> lzma     6,856,576
> zstd     7,399,157
> gzip     8,522,527
> bzip     8,629,603
> lzo      9,808,035
> lz4     10,705,570
> none    32,565,672
>
> Alex Xu ran benchmarks in https://lkml.org/lkml/2020/7/1/722.
>
> v1 -> v2:
> - Rebase
>   - usr/Makefile and init/Kconfig were changed so the patches were updated
> - No functional changes except to rebase
> - Split the patches up into smaller chunks
>
> v2 -> v3:
> - Add *.zst to the .gitignore in patch 8
> - Style nits in patch 3
> - Rename the PREBOOT macro to ZSTD_PREBOOT and XXH_PREBOOT in patches
>   1 through 3
>
> v3 -> v4:
> - Increase the ZSTD_IOBUF_SIZE from 4KB to 128KB to improve performance.
>   With this change I switch from malloc() to large_malloc() for the
>   buffers.
> - Increase the maximum allowed window size from 8 MB to 128 MB, which is
>   the max that zstd in the kernel supports.
>
> v4 -> v5:
> - Update commit message for patch 6 in response to comments
> - Rebase onto next-20200408
>
> v5 -> v6:
> - Rebase onto v5.8-rc4
>
> v6 -> v7:
> - (1/7) Don't define or use 'ZSTD_PREBOOT' to hide exports
> - (2/8) Drop 'lib: prepare xxhash for preboot environment'
> - (2/7) Use '__DISABLE_EXPORTS' in unzstd to hide exports
> - (3/7) Update zstd compression cmd to follow other compressors
> - (3/7) Add zstd22 cmd
> - (6/7) Use zstd -22 --ultra (zstd22) for x86 kernel compression
>
> v7 -> v8:
> - (2/7) Don't define '__DISABLE_EXPORTS'
> - (6/7) Define '__DISABLE_EXPORTS' in misc.c
>
> v8 -> v9:
> - Rebase onto v5.8-rc7
> - (2/7) Fix nits about comment style & typos
> - (3/7) Fix typo in init/Kconfig description
> - (6/7) Explain BOOT_HEAP_SIZE increase and define __DISABLE_EXPORTS in
>         Makefile KBUILD_CFLAGS and remove definitions from kaslr.c and misc.c
>
> v9 -> v10:
> - (6/8) Fix commit message regarding __DISABLE_EXPORTS
> - (8/8) Add .zst files to Documentation/dontdiff
>

Looks like v10 was pushed to <tip.git#x86/boot>.

Thanks to all involved people!

- Sedat -

[1] https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git/log/?h=x86/boot

> Best,
> Nick Terrell
>
> Adam Borowski (1):
>   .gitignore: add ZSTD-compressed files
>
> Nick Terrell (7):
>   lib: prepare zstd 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
>   Documentation: dontdiff: Add zstd compressed files
>
>  .gitignore                        |   1 +
>  Documentation/dontdiff            |   1 +
>  Documentation/x86/boot.rst        |   6 +-
>  Makefile                          |   3 +-
>  arch/x86/Kconfig                  |   1 +
>  arch/x86/boot/compressed/Makefile |   6 +-
>  arch/x86/boot/compressed/kaslr.c  |   7 -
>  arch/x86/boot/compressed/misc.c   |   4 +
>  arch/x86/boot/header.S            |   8 +-
>  arch/x86/include/asm/boot.h       |  11 +-
>  include/linux/decompress/unzstd.h |  11 +
>  init/Kconfig                      |  15 +-
>  lib/Kconfig                       |   4 +
>  lib/Makefile                      |   1 +
>  lib/decompress.c                  |   5 +
>  lib/decompress_unzstd.c           | 345 ++++++++++++++++++++++++++++++
>  lib/zstd/fse_decompress.c         |   9 +-
>  lib/zstd/zstd_internal.h          |  14 +-
>  scripts/Makefile.lib              |  22 ++
>  usr/Kconfig                       |  20 ++
>  usr/Makefile                      |   1 +
>  21 files changed, 469 insertions(+), 26 deletions(-)
>  create mode 100644 include/linux/decompress/unzstd.h
>  create mode 100644 lib/decompress_unzstd.c
>
> --
> 2.27.0
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v10 7/8] .gitignore: add ZSTD-compressed files
  2020-07-31  9:50   ` Ingo Molnar
@ 2020-07-31 17:17     ` Nick Terrell
  0 siblings, 0 replies; 17+ messages in thread
From: Nick Terrell @ 2020-07-31 17:17 UTC (permalink / raw)
  To: Ingo Molnar
  Cc: Nick Terrell, Adam Borowski, Borislav Petkov, Thomas Gleixner,
	Linux Kernel Mailing List, Chris Mason, linux-kbuild, x86,
	gregkh, Petr Malat, Kees Cook, Kernel Team, Patrick Williams,
	Michael van der Westhuizen, Patrick Williams, Sedat Dilek,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada



> On Jul 31, 2020, at 2:50 AM, Ingo Molnar <mingo@kernel.org> wrote:
> 
> 
> * Nick Terrell <nickrterrell@gmail.com> wrote:
> 
>> From: Adam Borowski <kilobyte@angband.pl>
>> 
>> 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.
>> 
>> Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
>> Reviewed-by: Kees Cook <keescook@chromium.org>
>> Signed-off-by: Nick Terrell <terrelln@fb.com>
>> Signed-off-by: Adam Borowski <kilobyte@angband.pl>
> 
> I presume Adam Borowski's Signed-off-by was intended to be added as 
> the first entry of the SOB chain?
> 
> I've added it, please let me know if that's not OK.

Yeah, it was. If a new version is needed I will update it.


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs
  2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
                   ` (9 preceding siblings ...)
  2020-07-31 14:36 ` Sedat Dilek
@ 2020-08-04  6:47 ` Sedat Dilek
  10 siblings, 0 replies; 17+ messages in thread
From: Sedat Dilek @ 2020-08-04  6:47 UTC (permalink / raw)
  To: Nick Terrell
  Cc: Borislav Petkov, Thomas Gleixner, linux-kernel, Chris Mason,
	linux-kbuild, x86, gregkh, Petr Malat, Kees Cook, Kernel Team,
	Adam Borowski, Patrick Williams, rmikey, mingo, Patrick Williams,
	Norbert Lange, Andrew Morton, Alex Xu, Masahiro Yamada,
	Nick Terrell

On Thu, Jul 30, 2020 at 9:11 PM Nick Terrell <nickrterrell@gmail.com> wrote:
>
> From: Nick Terrell <terrelln@fb.com>
>
> Please pull from
>
>   git@github.com:terrelln/linux.git tags/v10-zstd
>
> to get these changes. Alternatively the patchset is included.
>
> Hi all,
>
> This patch set adds support for a ZSTD-compressed kernel, ramdisk, and
> initramfs in the kernel boot process. ZSTD-compressed ramdisk and initramfs
> are supported on all architectures. The ZSTD-compressed kernel is only
> hooked up to x86 in this patch set.
>
> Zstandard requires slightly more memory during the kernel decompression
> on x86 (192 KB vs 64 KB), and the memory usage is independent of the
> window size.
>
> Zstandard requires memory proprortional to the window size used during
> compression for decompressing the ramdisk image, since streaming mode is
> used. Newer versions of zstd (1.3.2+) list the window size of a file
> with `zstd -lv <file>'. The absolute maximum amount of memory required
> is just over 8 MB, but it can be controlled at compression time.
>
> This patch set has been boot tested with buildroot and QEMU based off
> of linux-5.6-rc6.
>
> On i386 and x86_64 I have tested the following configurations:
> * zstd compressed kernel and a separate zstd compressed initramfs
> * zstd compressed kernel and a built-in zstd compressed initramfs
> * gzip compressed kernel and a separate gzip compressed initramfs
> * gzip compressed kernel and a built-in gzip compressed initramfs
>
> On arm and aarch64 I tested the same configurations, except that the kernel is
> always gzip compressed.
>
> Facebook has been using v1 of these patches on x86_64 devices for more than 6
> months. When we switched from a xz compressed initramfs to a zstd compressed
> initramfs decompression time shrunk from 12 seconds to 3 seconds. When we
> switched from a xz compressed kernel to a zstd compressed kernel we saved 2
> seconds of boot time.
>
> Facebook has been using v2 of these patches on aarch64 devices for a few weeks.
> When we switched from an lzma compressed initramfs to a zstd compressed initramfs
> decompression time shrunk from 27 seconds to 8 seconds.
>
> The zstd compressed kernel is smaller than the gzip compressed kernel but larger
> than the xz or lzma compressed kernels, and it decompresses faster than
> everything except lz4. See the table below for the measurement of an x86_64
> kernel ordered by compressed size:
>
> algo    size
> xz       6,509,792
> lzma     6,856,576
> zstd     7,399,157
> gzip     8,522,527
> bzip     8,629,603
> lzo      9,808,035
> lz4     10,705,570
> none    32,565,672
>
> Alex Xu ran benchmarks in https://lkml.org/lkml/2020/7/1/722.
>
> v1 -> v2:
> - Rebase
>   - usr/Makefile and init/Kconfig were changed so the patches were updated
> - No functional changes except to rebase
> - Split the patches up into smaller chunks
>
> v2 -> v3:
> - Add *.zst to the .gitignore in patch 8
> - Style nits in patch 3
> - Rename the PREBOOT macro to ZSTD_PREBOOT and XXH_PREBOOT in patches
>   1 through 3
>
> v3 -> v4:
> - Increase the ZSTD_IOBUF_SIZE from 4KB to 128KB to improve performance.
>   With this change I switch from malloc() to large_malloc() for the
>   buffers.
> - Increase the maximum allowed window size from 8 MB to 128 MB, which is
>   the max that zstd in the kernel supports.
>
> v4 -> v5:
> - Update commit message for patch 6 in response to comments
> - Rebase onto next-20200408
>
> v5 -> v6:
> - Rebase onto v5.8-rc4
>
> v6 -> v7:
> - (1/7) Don't define or use 'ZSTD_PREBOOT' to hide exports
> - (2/8) Drop 'lib: prepare xxhash for preboot environment'
> - (2/7) Use '__DISABLE_EXPORTS' in unzstd to hide exports
> - (3/7) Update zstd compression cmd to follow other compressors
> - (3/7) Add zstd22 cmd
> - (6/7) Use zstd -22 --ultra (zstd22) for x86 kernel compression
>
> v7 -> v8:
> - (2/7) Don't define '__DISABLE_EXPORTS'
> - (6/7) Define '__DISABLE_EXPORTS' in misc.c
>
> v8 -> v9:
> - Rebase onto v5.8-rc7
> - (2/7) Fix nits about comment style & typos
> - (3/7) Fix typo in init/Kconfig description
> - (6/7) Explain BOOT_HEAP_SIZE increase and define __DISABLE_EXPORTS in
>         Makefile KBUILD_CFLAGS and remove definitions from kaslr.c and misc.c
>
> v9 -> v10:
> - (6/8) Fix commit message regarding __DISABLE_EXPORTS
> - (8/8) Add .zst files to Documentation/dontdiff
>

Now in Linus Git tree.

- Sedat -

[1] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=c0dfadfed87489fa6126ece161a14c2d15dbdc79

> Best,
> Nick Terrell
>
> Adam Borowski (1):
>   .gitignore: add ZSTD-compressed files
>
> Nick Terrell (7):
>   lib: prepare zstd 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
>   Documentation: dontdiff: Add zstd compressed files
>
>  .gitignore                        |   1 +
>  Documentation/dontdiff            |   1 +
>  Documentation/x86/boot.rst        |   6 +-
>  Makefile                          |   3 +-
>  arch/x86/Kconfig                  |   1 +
>  arch/x86/boot/compressed/Makefile |   6 +-
>  arch/x86/boot/compressed/kaslr.c  |   7 -
>  arch/x86/boot/compressed/misc.c   |   4 +
>  arch/x86/boot/header.S            |   8 +-
>  arch/x86/include/asm/boot.h       |  11 +-
>  include/linux/decompress/unzstd.h |  11 +
>  init/Kconfig                      |  15 +-
>  lib/Kconfig                       |   4 +
>  lib/Makefile                      |   1 +
>  lib/decompress.c                  |   5 +
>  lib/decompress_unzstd.c           | 345 ++++++++++++++++++++++++++++++
>  lib/zstd/fse_decompress.c         |   9 +-
>  lib/zstd/zstd_internal.h          |  14 +-
>  scripts/Makefile.lib              |  22 ++
>  usr/Kconfig                       |  20 ++
>  usr/Makefile                      |   1 +
>  21 files changed, 469 insertions(+), 26 deletions(-)
>  create mode 100644 include/linux/decompress/unzstd.h
>  create mode 100644 lib/decompress_unzstd.c
>
> --
> 2.27.0
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v10 4/8] usr: add support for zstd compressed initramfs
  2020-07-30 19:08 ` [PATCH v10 4/8] usr: add support for zstd compressed initramfs Nick Terrell
@ 2020-08-04  6:52   ` Geert Uytterhoeven
  2020-08-04  7:25     ` Sedat Dilek
  0 siblings, 1 reply; 17+ messages in thread
From: Geert Uytterhoeven @ 2020-08-04  6:52 UTC (permalink / raw)
  To: Nick Terrell
  Cc: Borislav Petkov, Thomas Gleixner, Linux Kernel Mailing List,
	Chris Mason, linux-kbuild, the arch/x86 maintainers, Greg KH,
	Petr Malat, Kees Cook, Kernel Team, Adam Borowski,
	Patrick Williams, rmikey, Ingo Molnar, Patrick Williams,
	Sedat Dilek, Norbert Lange, Andrew Morton, Alex Xu,
	Masahiro Yamada, Nick Terrell

Hi Nick,

On Thu, Jul 30, 2020 at 9:13 PM Nick Terrell <nickrterrell@gmail.com> wrote:
> From: Nick Terrell <terrelln@fb.com>
>
> * 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.
>
> Reviewed-by: Kees Cook <keescook@chromium.org>
> Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
> Signed-off-by: Nick Terrell <terrelln@fb.com>

Thanks for your patch, which is now commit a30d8a39f0571425 ("usr: Add
support for zstd compressed initramfs").

> --- a/usr/Kconfig
> +++ b/usr/Kconfig
> @@ -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.

I'm aware you copied this from the other entries, but IMHO "default y",
and "If unsure, say N" are not a good combination.

Gr{oetje,eeting}s,

                        Geert

-- 
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v10 4/8] usr: add support for zstd compressed initramfs
  2020-08-04  6:52   ` Geert Uytterhoeven
@ 2020-08-04  7:25     ` Sedat Dilek
  2020-08-04  9:19       ` Adam Borowski
  0 siblings, 1 reply; 17+ messages in thread
From: Sedat Dilek @ 2020-08-04  7:25 UTC (permalink / raw)
  To: Geert Uytterhoeven
  Cc: Nick Terrell, Borislav Petkov, Thomas Gleixner,
	Linux Kernel Mailing List, Chris Mason, linux-kbuild,
	the arch/x86 maintainers, Greg KH, Petr Malat, Kees Cook,
	Kernel Team, Adam Borowski, Patrick Williams, rmikey,
	Ingo Molnar, Patrick Williams, Norbert Lange, Andrew Morton,
	Alex Xu, Masahiro Yamada, Nick Terrell

On Tue, Aug 4, 2020 at 8:52 AM Geert Uytterhoeven <geert@linux-m68k.org> wrote:
>
> Hi Nick,
>
> On Thu, Jul 30, 2020 at 9:13 PM Nick Terrell <nickrterrell@gmail.com> wrote:
> > From: Nick Terrell <terrelln@fb.com>
> >
> > * 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.
> >
> > Reviewed-by: Kees Cook <keescook@chromium.org>
> > Tested-by: Sedat Dilek <sedat.dilek@gmail.com>
> > Signed-off-by: Nick Terrell <terrelln@fb.com>
>
> Thanks for your patch, which is now commit a30d8a39f0571425 ("usr: Add
> support for zstd compressed initramfs").
>
> > --- a/usr/Kconfig
> > +++ b/usr/Kconfig
> > @@ -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.
>
> I'm aware you copied this from the other entries, but IMHO "default y",
> and "If unsure, say N" are not a good combination.
>

Hi Geert,

you are right - for new stuff it should be "default n".

What I am missing - still - is a note - that your user-space should
have the correct bits to support zstd-initramfs.
Unsure where to place such an information.

If you send a patch for above feel free to add my:

Reviewed-by: Sedat Dilek <sedat.dilek@gmail.com>

Thanks.

Regards,
- Sedat -

[1] https://bugs.debian.org/955469

> Gr{oetje,eeting}s,
>
>                         Geert
>
> --
> Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org
>
> In personal conversations with technical people, I call myself a hacker. But
> when I'm talking to journalists I just say "programmer" or something like that.
>                                 -- Linus Torvalds

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH v10 4/8] usr: add support for zstd compressed initramfs
  2020-08-04  7:25     ` Sedat Dilek
@ 2020-08-04  9:19       ` Adam Borowski
  0 siblings, 0 replies; 17+ messages in thread
From: Adam Borowski @ 2020-08-04  9:19 UTC (permalink / raw)
  To: Sedat Dilek
  Cc: Geert Uytterhoeven, Nick Terrell, Borislav Petkov,
	Thomas Gleixner, Linux Kernel Mailing List, Chris Mason,
	linux-kbuild, the arch/x86 maintainers, Greg KH, Petr Malat,
	Kees Cook, Kernel Team, Patrick Williams, rmikey, Ingo Molnar,
	Patrick Williams, Norbert Lange, Andrew Morton, Alex Xu,
	Masahiro Yamada, Nick Terrell

On Tue, Aug 04, 2020 at 09:25:23AM +0200, Sedat Dilek wrote:
> On Tue, Aug 4, 2020 at 8:52 AM Geert Uytterhoeven <geert@linux-m68k.org> wrote:
> > On Thu, Jul 30, 2020 at 9:13 PM Nick Terrell <nickrterrell@gmail.com> wrote:
> > > From: Nick Terrell <terrelln@fb.com>
> > > * Add support for a zstd compressed initramfs.
> > > * Add compression for compressing built-in initramfs with zstd.

> > > --- a/usr/Kconfig
> > > +++ b/usr/Kconfig
> > > @@ -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.
> >
> > I'm aware you copied this from the other entries, but IMHO "default y",
> > and "If unsure, say N" are not a good combination.

> you are right - for new stuff it should be "default n".

It got already applied to Linus' tree with "y", and I think it'd be nice
to have it as a default.  Let's disable other compressors instead.

On the other hand, having an unsupported rd compressor results in a boot
failure that's not immediately obvious, so that's a reason for keeping
the setting as "y".

On the third hand, distributions default to either gz or xz, thus I'd say:
* let's have gz xz zstd default to y, all others to n
* drop bzip2 lzma1 completely
* distros can't switch the mkinitramfs default yet, but if RD_ZSTD=y now,
  they'll be able to once they drop support for old kernels in a few years

> What I am missing - still - is a note - that your user-space should
> have the correct bits to support zstd-initramfs.
> Unsure where to place such an information.

Looks like INITRAMFS_COMPRESSION_* have lengthy prose but are not shown in
menuconfig, while RD_*, with no such prose, are shown.

The prose itself is grossly obsolete, too.  I have some updates in:
    https://github.com/kilobyte/linux/commits/nobz2-v3
but that patchset needs rebasing and refreshing.


Meow!
-- 
⢀⣴⠾⠻⢶⣦⠀
⣾⠁⢠⠒⠀⣿⡁
⢿⡄⠘⠷⠚⠋⠀ It's time to migrate your Imaginary Protocol from version 4i to 6i.
⠈⠳⣄⠀⠀⠀⠀

^ permalink raw reply	[flat|nested] 17+ messages in thread

end of thread, other threads:[~2020-08-04  9:20 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-07-30 19:08 [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Nick Terrell
2020-07-30 19:08 ` [PATCH v10 1/8] lib: prepare zstd for preboot environment Nick Terrell
2020-07-30 19:08 ` [PATCH v10 2/8] lib: add zstd support to decompress Nick Terrell
2020-07-30 19:08 ` [PATCH v10 3/8] init: add support for zstd compressed kernel Nick Terrell
2020-07-30 19:08 ` [PATCH v10 4/8] usr: add support for zstd compressed initramfs Nick Terrell
2020-08-04  6:52   ` Geert Uytterhoeven
2020-08-04  7:25     ` Sedat Dilek
2020-08-04  9:19       ` Adam Borowski
2020-07-30 19:08 ` [PATCH v10 5/8] x86: bump ZO_z_extra_bytes margin for zstd Nick Terrell
2020-07-30 19:08 ` [PATCH v10 6/8] x86: Add support for ZSTD compressed kernel Nick Terrell
2020-07-30 19:08 ` [PATCH v10 7/8] .gitignore: add ZSTD-compressed files Nick Terrell
2020-07-31  9:50   ` Ingo Molnar
2020-07-31 17:17     ` Nick Terrell
2020-07-30 19:08 ` [PATCH v10 8/8] Documentation: dontdiff: Add zstd compressed files Nick Terrell
2020-07-31  9:47 ` [GIT PULL][PATCH v10 0/8] Add support for ZSTD-compressed kernel and initramfs Sedat Dilek
2020-07-31 14:36 ` Sedat Dilek
2020-08-04  6:47 ` Sedat Dilek

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).