[PATCH 0/7] erofs: add LZMA compression support

[Gao Xiang]

Hi folks,

Here is the EROFS LZMA support which I've been working on and off for
more than half a year together with the XZ author Lasse Collin (many
thanks again!).

In order to better support the LZMA fixed-sized output compression,
especially for 4KiB pcluster size (which has lowest memory pressure
thus useful for memory-sensitive scenarios). Lasse introduced a new
LZMA header/container format called MicroLZMA [1] to minimize the
original LZMA1 header (for example, we don't need to waste 4-byte
dictionary size and another 8-byte uncompressed size, which can be
calculated by fs directly, for each pcluster.) and enable EROFS
fixed-sized output compression. Also note that MicroLZMA can be used
by other things in addition to EROFS too where wasting minimal amount
of space for headers is important, which can be compiled by enabling
XZ_DEC_MICROLZMA.

Similar to LZ4, EROFS LZMA decompression runtime also utilizes inplace
I/O and overlapped decompression to reuse the file page for compressed
data temporarily with proper strategies, which is useful to ensure
guaranteed performance under extremely memory pressure without extra
cost.

Due to the EROFS on-disk design, LZMA algorithm can be used in the
per-file basis independently and as a secondary compression algorithm
besides the primary algorithm given in one file as a complement for
specific access/data patterns.

The latest version can also be fetched from:
git://git.kernel.org/pub/scm/linux/kernel/git/xiang/linux.git -b erofs/lzma

The latest mkfs can be fetched from:
git://git.kernel.org/pub/scm/linux/kernel/git/xiang/erofs-utils.git -b experimental-lzma

[ The latest liblzma should be used in order to support MicroLZMA:
  https://git.tukaani.org/?p=xz.git ]

Finally, there are few in-kernel fses with LZMA support but as always
I might need to show some real numbers here anyway.. There are still
some ongoing EROFS runtime strategies to optimize such CPU bound
decompression algorithms even further. But let's do step by step:

Kernel: Linux 5.15.0-rc2
Testdata: enwik8 (100000000 bytes)
Compression level: LZMA_PRESET_DEFAULT (6)

Processor: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
SSD: INTEL SSDPEKKF360G7H (360 GB)
DDR: Samsung M471A1K43CB1-CRC (8 GB)
OS Distribution: Debian 10
Test environment:
Turbo Boost disabled
scaling_governor = userspace, scaling_{min,max}_freq = 1801000
 __________________________________________________
|  file system  |   size    | seq read | rand read |
|_______________|___________|_ MiB/s __|__ MiB/s __|
|___erofs_4k____|__41664512_|_ 59.92 __|__ 16.88 __|
|___erofs_8k____|__38555648_|_ 63.86 __|__ 22.18 __|
|___erofs_16k___|__36179968_|_ 63.14 __|__ 28.98 __|
|___erofs_32k___|__34299904_|_ 59.14 __|__ 35.38 __|
|___erofs_64k___|__32792576_|_ 57.56 __|__ 41.24 __|
|__squashfs_8k__|__43274240_|_ 21.48 __|__ 15.42 __|
|__squashfs_16k_|__39866368_|_ 25.10 __|__ 20.80 __|
|__squashfs_64k_|__35241984_|_ 31.02 __|__ 31.36 __|
|_squashfs_128k_|__33632256_|_ 36.62 __|__ 36.92 __|

Some numbers of silesia.tar:
 ___________________________
|  file system  |   size    |
|_______________|___________|
|__silesia.tar__|_211957760_|
|__squashfs_8k__|__75964416_|
|___erofs_4k____|__70987776_|
|__squashfs_16k_|__69337088_|
|___erofs_8k____|__65617920_|
|___erofs_16k___|__61333504_|
|__squashfs_64k_|__60669952_|
|___erofs_32k___|__58331136_|
|_squashfs_128k_|__58036224_|
|___erofs_64k___|__56123392_|

Revised EROFS roadmap:
https://lore.kernel.org/r/20211009061150.GA7479@hsiangkao-HP-ZHAN-66-Pro-G1


[1] where the first byte of a raw LZMA stream has been replaced with a
    bitwise-negation of the lc/lp/pb properties byte and it has no EOPM marker
    since the exact compressed size is known and provided explicitly.


Hi Andrew,

Some XZ embedded (lib/xz) patches by Lasse are sent out together in this series
although they're irrelevant to MicroLZMA but quite coupled. Can I send a pull
request together with EROFS LZMA support for 5.16 then? Many thanks in advance!

Thanks,
Gao Xiang


Gao Xiang (2):
  erofs: rename some generic methods in decompressor
  erofs: lzma compression support

Lasse Collin (5):
  lib/xz: Avoid overlapping memcpy() with invalid input with in-place
    decompression
  lib/xz: Validate the value before assigning it to an enum variable
  lib/xz: Move s->lzma.len = 0 initialization to lzma_reset()
  lib/xz: Add MicroLZMA decoder
  lib/xz, lib/decompress_unxz.c: Fix spelling in comments

 fs/erofs/Kconfig             |  16 ++
 fs/erofs/Makefile            |   1 +
 fs/erofs/compress.h          |  16 ++
 fs/erofs/decompressor.c      |  73 +++++----
 fs/erofs/decompressor_lzma.c | 290 +++++++++++++++++++++++++++++++++++
 fs/erofs/erofs_fs.h          |  14 +-
 fs/erofs/internal.h          |  22 +++
 fs/erofs/super.c             |  17 +-
 fs/erofs/zdata.c             |   4 +-
 fs/erofs/zdata.h             |   7 -
 fs/erofs/zmap.c              |   5 +-
 include/linux/xz.h           | 106 +++++++++++++
 lib/decompress_unxz.c        |  10 +-
 lib/xz/Kconfig               |  13 ++
 lib/xz/xz_dec_lzma2.c        | 182 +++++++++++++++++++++-
 lib/xz/xz_dec_stream.c       |   6 +-
 lib/xz/xz_dec_syms.c         |   9 +-
 lib/xz/xz_private.h          |   3 +
 18 files changed, 725 insertions(+), 69 deletions(-)
 create mode 100644 fs/erofs/decompressor_lzma.c

-- 
2.20.1