[PATCH v2 0/2] Add support for ZSTD-compressed kernel

[Nick Terrell <terrelln@fb.com>]

Hi,

This patch set adds support for a ZSTD-compressed kernel and ramdisk
images in the kernel boot process. It only integrates the support with
x86, though the first patch is generic to all architectures.

Zstandard requires slightly more memory during the kernel decompression
on x86 (192 KB vs 64 KB), and the memory usage is independent of the
window size. In my tests it compresses the second best (behind LZMA/XZ)
and decompresses the third fastest (behind LZO and LZ4).

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

I benchmarked kernel decompression by adding a log line before and after
decompression, appending a timestamp to each line of QEMU's stdout, and
measuring the time between the two lines. I had to spin before
decompression for some time to normalize the measurements. The benchmarks
are run in QEMU a 2.2GHz x86 CPU, using a kernel config pulled from my
machine.

Original kernel size: 21756168 B (21.7 MB)

| Algorithm | Ratio | Decompress MB/s |
|-----------|-------|-----------------|
| GZIP      |  3.11 |           229.1 |
| BZIP2     |  3.23 |            30.0 |
| LZMA      |  3.81 |            36.6 |
| XZ        |  4.06 |            42.2 |
| LZO       |  2.81 |           582.9 |
| LZ4       |  2.18 |          1447.5 |
| ZSTD      |  3.55 |           364.6 |

BZIP2 and LZMA aren't interesting, since XZ is better than both in all
respects. GZIP remains useful because of its wide adoption. LZO is
squeezed tightly between LZ4 and ZSTD, though maintains an edge on ratio or
decompression speed respectively.

Thanks,
Nick Terrell

Changelog:

v1 -> v2:
- Fix performance bug in zstd decompression
- Gate gcc bug workaround to buggy versions
- Benchmark kernel compression

Nick Terrell (2):
  lib: Add support for ZSTD-compressed kernel
  x86: Add support for ZSTD-compressed kernel

 Documentation/x86/boot.txt        |   6 +-
 arch/x86/Kconfig                  |   1 +
 arch/x86/boot/compressed/Makefile |   5 +-
 arch/x86/boot/compressed/misc.c   |   4 +
 arch/x86/boot/header.S            |   8 +-
 arch/x86/include/asm/boot.h       |   6 +-
 include/linux/decompress/unzstd.h |  26 +++
 init/Kconfig                      |  14 +-
 lib/Kconfig                       |   4 +
 lib/Makefile                      |   1 +
 lib/decompress.c                  |   5 +
 lib/decompress_unzstd.c           | 341 ++++++++++++++++++++++++++++++++++++++
 lib/xxhash.c                      |  21 ++-
 lib/zstd/decompress.c             |   2 +
 lib/zstd/fse_decompress.c         |   9 +-
 lib/zstd/zstd_internal.h          |  10 +-
 scripts/Makefile.lib              |  15 ++
 usr/Kconfig                       |  22 +++
 18 files changed, 474 insertions(+), 26 deletions(-)
 create mode 100644 include/linux/decompress/unzstd.h
 create mode 100644 lib/decompress_unzstd.c

-- 
2.9.5