Update to zstd-1.4.10
Subsystems (7)
From: Nick Terrell <[email protected]>
Please pull from
[email protected]:terrelln/linux.git tags/v9-zstd-1.4.10
to get these changes. Alternatively the patchset is included.
This patchset upgrades the zstd library to the latest upstream release. The current zstd version in the kernel is a modified version of upstream zstd-1.3.1. At the time it was integrated, zstd wasn't ready to be used in the kernel as-is. But, it is now possible to use upstream zstd directly in the kernel.
I have not yet released zstd-1.4.10 upstream. I want the zstd version in the kernel to match up with a known upstream release, so we know exactly what code is running. Whenever this patchset is ready for merge, I will cut a release at the upstream commit that gets merged. This should not be necessary for future releases.
The kernel zstd library is automatically generated from upstream zstd. A script makes the necessary changes and imports it into the kernel. The changes are:
1. Replace all libc dependencies with kernel replacements and rewrite includes.
2. Remove unncessary portability macros like: #if defined(_MSC_VER).
3. Use the kernel xxhash instead of bundling it.
This automation gets tested every commit by upstream's continuous integration. When we cut a new zstd release, we will submit a patch to the kernel to update the zstd version in the kernel.
I've updated zstd to upstream with one big patch because every commit must build, so that precludes partial updates. Since the commit is 100% generated, I hope the review burden is lightened. I considered replaying upstream commits, but that is not possible because there have been ~3500 upstream commits since the last zstd import, and the commits don't all build individually. The bulk update preserves bisectablity because bugs can be bisected to the zstd version update. At that point the update can be reverted, and we can work with upstream to find and fix the bug. After this big switch in how the kernel consumes zstd, future patches will be smaller, because they will only have one upstream release worth of changes each.
This patchset adds a new kernel-style wrapper around zstd. This wrapper API is functionally equivalent to the subset of the current zstd API that is currently used. The wrapper API changes to be kernel style so that the symbols don't collide with zstd's symbols. The update to zstd-1.4.6 maintains the same API and preserves the semantics, so that none of the callers need to be updated.
This patchset comes in 2 parts:
1. The first 2 patches prepare for the zstd upgrade. The first patch adds the new kernel style API so zstd can be upgraded without modifying any callers. The second patch adds an indirection for the lib/decompress_unzstd.c including of all decompression source files.
2. Import zstd-1.4.10. This patch is completely generated from upstream using automated tooling.
I tested every caller of zstd on x86_64. I tested both after the 1.4.10 upgrade using the compatibility wrapper, and after the final patch in this series.
I tested kernel and initramfs decompression in i386 and arm.
I ran benchmarks to compare the current zstd in the kernel with zstd-1.4.6. I benchmarked on x86_64 using QEMU with KVM enabled on an Intel i9-9900k. I found:
* BtrFS zstd compression at levels 1 and 3 is 5% faster
* BtrFS zstd decompression+read is 15% faster
* SquashFS zstd decompression+read is 15% faster
* F2FS zstd compression+write at level 3 is 8% faster
* F2FS zstd decompression+read is 20% faster
* ZRAM decompression+read is 30% faster
* Kernel zstd decompression is 35% faster
* Initramfs zstd decompression+build is 5% faster
The latest zstd also offers bug fixes. For example the problem with large kernel decompression has been fixed upstream for over 2 years
https://lkml.org/lkml/2020/9/29/27.
Please let me know if there is anything that I can do to ease the way for these patches. I think it is important because it gets large performance improvements, contains bug fixes, and is switching to a more maintainable model of consuming upstream zstd directly, making it easy to keep up to date.
Best,
Nick Terrell
v1 -> v2:
* Successfully tested F2FS with help from Chao Yu to fix my test.
* (1/9) Fix ZSTD_initCStream() wrapper to handle pledged_src_size=0 means unknown. This fixes F2FS with the zstd-1.4.6 compatibility wrapper, exposed by the test.
v2 -> v3:
* (3/9) Silence warnings by Kernel Test Robot:
https://github.com/facebook/zstd/pull/2324
Stack size warnings remain, but these aren't new, and the functions it warns on are either unused or not in the maximum stack path. This patchset reduces zstd compression stack usage by 1 KB overall. I've gotten the low hanging fruit, and more stack reduction would require significant changes that have the potential to introduce new bugs. However, I do hope to continue to reduce zstd stack usage in future versions.
v3 -> v4:
* (3/9) Fix errors and warnings reported by Kernel Test Robot:
https://github.com/facebook/zstd/pull/2326
- Replace mem.h with a custom kernel implementation that matches the current lib/zstd/mem.h in the kernel. This avoids calls to __builtin_bswap*() which don't work on certain architectures, as exposed by the Kernel Test Robot.
- Remove ASAN/MSAN (un)poisoning code which doesn't work in the kernel, as exposed by the Kernel Test Robot.
- I've fixed all of the valid cppcheck warnings reported, but there were many false positives, where cppcheck was incorrectly analyzing the situation, which I did not fix. I don't believe it is reasonable to expect that upstream zstd silences all the static analyzer false positives. Upstream zstd uses clang scan-build for its static analysis. We find that supporting multiple static analysis tools multiplies the burden of silencing false positives, without providing enough marginal value over running a single static analysis tool.
v4 -> v5:
* Rebase onto v5.10-rc2
* (6/9) Merge with other F2FS changes (no functional change in patch).
v5 -> v6:
* Rebase onto v5.10-rc6.
* Switch to using a kernel style wrapper API as suggested by Cristoph.
v6 -> v7:
* Expose the upstream library header as include/linux/zstd_lib.h. Instead of creating new structs mirroring the upstream zstd structs use upstream's structs directly with a typedef to get a kernel style name. This removes the memcpy cruft.
* (1/3) Undo ZSTD_WINDOWLOG_MAX and handle_zstd_error changes.
* (3/3) Expose zstd_errors.h as include/linux/zstd_errors.h because it is needed by the kernel wrapper API.
v7 -> v8:
* (1/3) Fix typo in EXPORT_SYMBOL().
* (1/3) Fix typo in zstd.h comments.
* (3/3) Update to latest zstd release: 1.4.6 -> 1.4.10 This includes ~1KB of stack space reductions.
v8 -> v9:
* (1/3) Rebase onto v5.12-rc5
* (1/3) Add zstd_min_clevel() & zstd_max_clevel() and use in f2fs. Thanks to Oleksandr Natalenko for spotting it!
* (1/3) Move lib/decompress_unzstd.c usage of ZSTD_getErrorCode() to zstd_get_error_code().
* (1/3) Update modified zstd headers to yearless copyright.
* (2/3) Add copyright/license header to decompress_sources.h for consistency.
* (3/3) Update to yearless copyright for all zstd files. Thanks to Mike Dolan for spotting it!
Nick Terrell (3):
lib: zstd: Add kernel-specific API
lib: zstd: Add decompress_sources.h for decompress_unzstd
lib: zstd: Upgrade to latest upstream zstd version 1.4.10
crypto/zstd.c | 28 +- fs/btrfs/zstd.c | 68 +- fs/f2fs/compress.c | 56 +- fs/f2fs/super.c | 2 +- fs/pstore/platform.c | 2 +- fs/squashfs/zstd_wrapper.c | 16 +- include/linux/zstd.h | 1252 +--- include/linux/zstd_errors.h | 77 + include/linux/zstd_lib.h | 2432 ++++++++ lib/decompress_unzstd.c | 48 +- lib/zstd/Makefile | 44 +- lib/zstd/bitstream.h | 380 -- lib/zstd/common/bitstream.h | 437 ++ lib/zstd/common/compiler.h | 151 + lib/zstd/common/cpu.h | 194 + lib/zstd/common/debug.c | 24 + lib/zstd/common/debug.h | 101 + lib/zstd/common/entropy_common.c | 357 ++ lib/zstd/common/error_private.c | 56 + lib/zstd/common/error_private.h | 66 + lib/zstd/common/fse.h | 710 +++ lib/zstd/common/fse_decompress.c | 390 ++ lib/zstd/common/huf.h | 356 ++ lib/zstd/common/mem.h | 259 + lib/zstd/common/zstd_common.c | 83 + lib/zstd/common/zstd_deps.h | 125 + lib/zstd/common/zstd_internal.h | 450 ++ lib/zstd/compress.c | 3485 ----------- lib/zstd/compress/fse_compress.c | 625 ++ lib/zstd/compress/hist.c | 165 + lib/zstd/compress/hist.h | 75 + lib/zstd/compress/huf_compress.c | 902 +++ lib/zstd/compress/zstd_compress.c | 5105 +++++++++++++++++ lib/zstd/compress/zstd_compress_internal.h | 1188 ++++ lib/zstd/compress/zstd_compress_literals.c | 158 + lib/zstd/compress/zstd_compress_literals.h | 29 + lib/zstd/compress/zstd_compress_sequences.c | 439 ++ lib/zstd/compress/zstd_compress_sequences.h | 54 + lib/zstd/compress/zstd_compress_superblock.c | 850 +++ lib/zstd/compress/zstd_compress_superblock.h | 32 + lib/zstd/compress/zstd_cwksp.h | 482 ++ lib/zstd/compress/zstd_double_fast.c | 521 ++ lib/zstd/compress/zstd_double_fast.h | 32 + lib/zstd/compress/zstd_fast.c | 496 ++ lib/zstd/compress/zstd_fast.h | 31 + lib/zstd/compress/zstd_lazy.c | 1412 +++++ lib/zstd/compress/zstd_lazy.h | 81 + lib/zstd/compress/zstd_ldm.c | 686 +++ lib/zstd/compress/zstd_ldm.h | 110 + lib/zstd/compress/zstd_ldm_geartab.h | 103 + lib/zstd/compress/zstd_opt.c | 1345 +++++ lib/zstd/compress/zstd_opt.h | 50 + lib/zstd/decompress.c | 2531 -------- lib/zstd/decompress/huf_decompress.c | 1206 ++++ lib/zstd/decompress/zstd_ddict.c | 241 + lib/zstd/decompress/zstd_ddict.h | 44 + lib/zstd/decompress/zstd_decompress.c | 2075 +++++++ lib/zstd/decompress/zstd_decompress_block.c | 1540 +++++ lib/zstd/decompress/zstd_decompress_block.h | 62 + .../decompress/zstd_decompress_internal.h | 202 + lib/zstd/decompress_sources.h | 28 + lib/zstd/entropy_common.c | 243 - lib/zstd/error_private.h | 53 - lib/zstd/fse.h | 575 -- lib/zstd/fse_compress.c | 795 --- lib/zstd/fse_decompress.c | 325 -- lib/zstd/huf.h | 212 - lib/zstd/huf_compress.c | 773 --- lib/zstd/huf_decompress.c | 960 ---- lib/zstd/mem.h | 151 - lib/zstd/zstd_common.c | 75 - lib/zstd/zstd_compress_module.c | 124 + lib/zstd/zstd_decompress_module.c | 105 + lib/zstd/zstd_internal.h | 273 - lib/zstd/zstd_opt.h | 1014 ---- 75 files changed, 27287 insertions(+), 12940 deletions(-) create mode 100644 include/linux/zstd_errors.h create mode 100644 include/linux/zstd_lib.h delete mode 100644 lib/zstd/bitstream.h create mode 100644 lib/zstd/common/bitstream.h create mode 100644 lib/zstd/common/compiler.h create mode 100644 lib/zstd/common/cpu.h create mode 100644 lib/zstd/common/debug.c create mode 100644 lib/zstd/common/debug.h create mode 100644 lib/zstd/common/entropy_common.c create mode 100644 lib/zstd/common/error_private.c create mode 100644 lib/zstd/common/error_private.h create mode 100644 lib/zstd/common/fse.h create mode 100644 lib/zstd/common/fse_decompress.c create mode 100644 lib/zstd/common/huf.h create mode 100644 lib/zstd/common/mem.h create mode 100644 lib/zstd/common/zstd_common.c create mode 100644 lib/zstd/common/zstd_deps.h create mode 100644 lib/zstd/common/zstd_internal.h delete mode 100644 lib/zstd/compress.c create mode 100644 lib/zstd/compress/fse_compress.c create mode 100644 lib/zstd/compress/hist.c create mode 100644 lib/zstd/compress/hist.h create mode 100644 lib/zstd/compress/huf_compress.c create mode 100644 lib/zstd/compress/zstd_compress.c create mode 100644 lib/zstd/compress/zstd_compress_internal.h create mode 100644 lib/zstd/compress/zstd_compress_literals.c create mode 100644 lib/zstd/compress/zstd_compress_literals.h create mode 100644 lib/zstd/compress/zstd_compress_sequences.c create mode 100644 lib/zstd/compress/zstd_compress_sequences.h create mode 100644 lib/zstd/compress/zstd_compress_superblock.c create mode 100644 lib/zstd/compress/zstd_compress_superblock.h create mode 100644 lib/zstd/compress/zstd_cwksp.h create mode 100644 lib/zstd/compress/zstd_double_fast.c create mode 100644 lib/zstd/compress/zstd_double_fast.h create mode 100644 lib/zstd/compress/zstd_fast.c create mode 100644 lib/zstd/compress/zstd_fast.h create mode 100644 lib/zstd/compress/zstd_lazy.c create mode 100644 lib/zstd/compress/zstd_lazy.h create mode 100644 lib/zstd/compress/zstd_ldm.c create mode 100644 lib/zstd/compress/zstd_ldm.h create mode 100644 lib/zstd/compress/zstd_ldm_geartab.h create mode 100644 lib/zstd/compress/zstd_opt.c create mode 100644 lib/zstd/compress/zstd_opt.h delete mode 100644 lib/zstd/decompress.c create mode 100644 lib/zstd/decompress/huf_decompress.c create mode 100644 lib/zstd/decompress/zstd_ddict.c create mode 100644 lib/zstd/decompress/zstd_ddict.h create mode 100644 lib/zstd/decompress/zstd_decompress.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.h create mode 100644 lib/zstd/decompress/zstd_decompress_internal.h create mode 100644 lib/zstd/decompress_sources.h delete mode 100644 lib/zstd/entropy_common.c delete mode 100644 lib/zstd/error_private.h delete mode 100644 lib/zstd/fse.h delete mode 100644 lib/zstd/fse_compress.c delete mode 100644 lib/zstd/fse_decompress.c delete mode 100644 lib/zstd/huf.h delete mode 100644 lib/zstd/huf_compress.c delete mode 100644 lib/zstd/huf_decompress.c delete mode 100644 lib/zstd/mem.h delete mode 100644 lib/zstd/zstd_common.c create mode 100644 lib/zstd/zstd_compress_module.c create mode 100644 lib/zstd/zstd_decompress_module.c delete mode 100644 lib/zstd/zstd_internal.h delete mode 100644 lib/zstd/zstd_opt.h
--
2.31.0
_______________________________________________
Linux-f2fs-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
PATCH v9 1/3 lib: zstd: Add kernel-specific API
From: Nick Terrell <[email protected]>
This patch:
- Moves include/linux/zstd.h -> include/linux/zstd_lib.h
- Updates modified zstd headers to yearless copyright
- Adds a new API in include/linux/zstd.h that is functionally equivalent to the in-use subset of the current API. Functions are renamed to avoid symbol collisions with zstd, to make it clear it is not the upstream zstd API, and to follow the kernel style guide.
- Updates all callers to use the new API.
There are no functional changes in this patch. Since there are no functional change, I felt it was okay to update all the callers in a single patch. Once the API is approved, the callers are mechanically changed.
This patch is preparing for the 3rd patch in this series, which updates zstd to version 1.4.10. Since the upstream zstd API is no longer exposed to callers, the update can happen transparently.
--- crypto/zstd.c | 28 +- fs/btrfs/zstd.c | 68 +- fs/f2fs/compress.c | 56 +- fs/f2fs/super.c | 2 +- fs/pstore/platform.c | 2 +- fs/squashfs/zstd_wrapper.c | 16 +- include/linux/zstd.h | 1243 ++++++++---------------------------- include/linux/zstd_lib.h | 1157 +++++++++++++++++++++++++++++++++ lib/decompress_unzstd.c | 42 +- lib/zstd/compress.c | 123 ++-- lib/zstd/decompress.c | 112 ++-- 11 files changed, 1691 insertions(+), 1158 deletions(-) create mode 100644 include/linux/zstd_lib.h
crypto/zstd.c +14 -14
@@ -18,22 +18,22 @@#define ZSTD_DEF_LEVEL 3struct zstd_ctx { -ZSTD_CCtx *cctx; -ZSTD_DCtx *dctx; +zstd_cctx *cctx; +zstd_dctx *dctx;void *cwksp;void *dwksp; }; -static ZSTD_parameters zstd_params (void ) +static zstd_parameters zstd_params (void ) { -return ZSTD_getParams (ZSTD_DEF_LEVEL ,0 ,0 ); +return zstd_get_params (ZSTD_DEF_LEVEL ,0 ); }static int zstd_comp_init (struct zstd_ctx *ctx) {int ret =0 ; -const ZSTD_parameters params =zstd_params (); -const size_t wksp_size =ZSTD_CCtxWorkspaceBound (params.cParams); +const zstd_parameters params =zstd_params (); +const size_t wksp_size =zstd_cctx_workspace_bound (¶ms.cParams); ctx->cwksp =vzalloc (wksp_size);if (!ctx->cwksp) {
@@ -41,7 +41,7 @@ static int zstd_comp_init(struct zstd_ctx *ctx) goto out; } - ctx->cctx =ZSTD_initCCtx (ctx->cwksp, wksp_size); + ctx->cctx =zstd_init_cctx (ctx->cwksp, wksp_size);if (!ctx->cctx) { ret = -EINVAL ; goto out_free;
@@ -56,7 +56,7 @@ static int zstd_comp_init(struct zstd_ctx *ctx)static int zstd_decomp_init (struct zstd_ctx *ctx) {int ret =0 ; -const size_t wksp_size =ZSTD_DCtxWorkspaceBound (); +const size_t wksp_size =zstd_dctx_workspace_bound (); ctx->dwksp =vzalloc (wksp_size);if (!ctx->dwksp) {
@@ -64,7 +64,7 @@ static int zstd_decomp_init(struct zstd_ctx *ctx) goto out; } - ctx->dctx =ZSTD_initDCtx (ctx->dwksp, wksp_size); + ctx->dctx =zstd_init_dctx (ctx->dwksp, wksp_size);if (!ctx->dctx) { ret = -EINVAL ; goto out_free;
@@ -152,10 +152,10 @@ static int __zstd_compress(const u8 *src, unsigned int slen, {size_t out_len;struct zstd_ctx *zctx = ctx; -const ZSTD_parameters params =zstd_params (); +const zstd_parameters params =zstd_params (); - out_len =ZSTD_compressCCtx (zctx->cctx, dst, *dlen, src, slen, params); -if (ZSTD_isError (out_len)) + out_len =zstd_compress_cctx (zctx->cctx, dst, *dlen, src, slen, ¶ms); +if (zstd_is_error (out_len))return -EINVAL ; *dlen = out_len;return 0 ;
@@ -182,8 +182,8 @@ static int __zstd_decompress(const u8 *src, unsigned int slen,size_t out_len;struct zstd_ctx *zctx = ctx; - out_len =ZSTD_decompressDCtx (zctx->dctx, dst, *dlen, src, slen); -if (ZSTD_isError (out_len)) + out_len =zstd_decompress_dctx (zctx->dctx, dst, *dlen, src, slen); +if (zstd_is_error (out_len))return -EINVAL ; *dlen = out_len;return 0 ;
fs/btrfs/zstd.c +34 -34
169 lines not on this page · raw message
fs/f2fs/compress.c +28 -28
123 lines not on this page · raw message
fs/f2fs/super.c +1 -1
@@ -525,7 +525,7 @@ static int f2fs_set_zstd_level(struct f2fs_sb_info *sbi, const char *str)if (kstrtouint (str +1 ,10 , &level))return -EINVAL ; -if (!level || level >ZSTD_maxCLevel ()) { +if (!level || level >zstd_max_clevel ()) {f2fs_info (sbi,"invalid zstd compress level: %d" , level);return -EINVAL ; }
fs/pstore/platform.c +1 -1
@@ -218,7 +218,7 @@ static int zbufsize_842(size_t size)#if IS_ENABLED (CONFIG_PSTORE_ZSTD_COMPRESS )static int zbufsize_zstd (size_t size) { -return ZSTD_compressBound (size); +return zstd_compress_bound (size); }#endif
fs/squashfs/zstd_wrapper.c +8 -8
@@ -34,7 +34,7 @@ static void *zstd_init(struct squashfs_sb_info *msblk, void *buff) goto failed; wksp->window_size =max_t (size_t, msblk->block_size,SQUASHFS_METADATA_SIZE ); - wksp->mem_size =ZSTD_DStreamWorkspaceBound (wksp->window_size); + wksp->mem_size =zstd_dstream_workspace_bound (wksp->window_size); wksp->mem =vmalloc (wksp->mem_size);if (wksp->mem ==NULL ) goto failed;
@@ -63,15 +63,15 @@ static int zstd_uncompress(struct squashfs_sb_info *msblk, void *strm, struct squashfs_page_actor *output) {struct workspace *wksp = strm; -ZSTD_DStream *stream; +zstd_dstream *stream;size_t total_out =0 ;int error =0 ; -ZSTD_inBuffer in_buf = {NULL ,0 ,0 }; -ZSTD_outBuffer out_buf = {NULL ,0 ,0 }; +zstd_in_buffer in_buf = {NULL ,0 ,0 }; +zstd_out_buffer out_buf = {NULL ,0 ,0 };struct bvec_iter_all iter_all = {};struct bio_vec *bvec =bvec_init_iter_all (&iter_all); - stream =ZSTD_initDStream (wksp->window_size, wksp->mem, wksp->mem_size); + stream =zstd_init_dstream (wksp->window_size, wksp->mem, wksp->mem_size);if (!stream) {ERROR ("Failed to initialize zstd decompressor\n" );
@@ -116,14 +116,14 @@ static int zstd_uncompress(struct squashfs_sb_info *msblk, void *strm, } total_out -= out_buf.pos; - zstd_err =ZSTD_decompressStream (stream, &out_buf, &in_buf); + zstd_err =zstd_decompress_stream (stream, &out_buf, &in_buf); total_out += out_buf.pos;/* add the additional data produced */ if (zstd_err ==0 )break ; -if (ZSTD_isError (zstd_err)) { +if (zstd_is_error (zstd_err)) {ERROR ("zstd decompression error: %d\n" , - (int )ZSTD_getErrorCode (zstd_err)); + (int )zstd_get_error_code (zstd_err)); error = -EIO ;break ; }
include/linux/zstd.h +263 -980
1,418 lines not on this page · raw message
include/linux/zstd_lib.h new file +1157 -0
1,155 lines not on this page · raw message
lib/decompress_unzstd.c +23 -19
42 lines not on this page · raw message
lib/zstd/compress.c +86 -37
123 lines not on this page · raw message
lib/zstd/decompress.c +76 -36
112 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 8 lines
2.31.0 _______________________________________________ Linux-f2fs-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
Part of the diff is not shown here. View the raw message.
PATCH v9 2/3 lib: zstd: Add decompress_sources.h for decompress_unzstd
In reply to Nick TerrellFrom: Nick Terrell <[email protected]>
Adds decompress_sources.h which includes every .c file necessary for zstd decompression. This is used in decompress_unzstd.c so the internal structure of the library isn't exposed.
This allows us to upgrade the zstd library version without modifying any callers. Instead we just need to update decompress_sources.h.
--- lib/decompress_unzstd.c | 6 +----- lib/zstd/decompress_sources.h | 23 +++++++++++++++++++++++ 2 files changed, 24 insertions(+), 5 deletions(-) create mode 100644 lib/zstd/decompress_sources.h
lib/decompress_unzstd.c +1 -5
@@ -68,11 +68,7 @@#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" +# include "zstd/decompress_sources.h" #endif #include <linux/decompress/mm.h>
lib/zstd/decompress_sources.h new file +23 -0
@@ -0,0 +1,23 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* +* Copyright (c) Facebook, Inc. +* All rights reserved. +* +* This source code is licensed under both the BSD-style license (found in the +* LICENSE file in the root directory of this source tree) and the GPLv2 (found +* in the COPYING file in the root directory of this source tree). +* You may select, at your option, one of the above-listed licenses. +*/ + +/* +* This file includes every .c file needed for decompression. +* It is used by lib/decompress_unzstd.c to include the decompression +* source into the translation-unit, so it can be used for kernel +* decompression. +*/ + +#include "entropy_common.c" +#include "fse_decompress.c" +#include "huf_decompress.c" +#include "zstd_common.c" +#include "decompress.c"
Signature · 8 lines
2.31.0 _______________________________________________ Linux-f2fs-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
PATCH v9 3/3 lib: zstd: Upgrade to latest upstream zstd version 1.4.10
In reply to Nick TerrellFrom: Nick Terrell <[email protected]>
Upgrade to the latest upstream zstd version 1.4.10.
This patch is 100% generated from upstream zstd commit 4432dac93bea [0].
This patch is very large because it is transitioning from the custom kernel zstd to using upstream directly. The new zstd follows upstreams file structure which is different. Future update patches will be much smaller because they will only contain the changes from one upstream zstd release.
As an aid for review I've created a commit [1] that shows the diff between upstream zstd as-is (which doesn't compile), and the zstd code imported in this patch. The verion of zstd in this patch is generated from upstream with changes applied by automation to replace upstreams libc dependencies, remove unnecessary portability macros, and use the kernel's xxhash instead of bundling it.
The benefits of this patch are as follows:
1. Using upstream directly with automated script to generate kernel code. This allows us to update the kernel every upstream release, so the kernel gets the latest bug fixes and performance improvements, and doesn't get 3 years out of date again. The automation and the translated code are tested every upstream commit to ensure it continues to work.
2. Upgrades from a custom zstd based on 1.3.1 to 1.4.10, getting 3 years of performance improvements and bug fixes. On x86_64 I've measured 15% faster BtrFS and SquashFS decompression+read speeds, 35% faster kernel decompression, and 30% faster ZRAM decompression+read speeds.
3. Zstd-1.4.10 supports negative compression levels, which allow zstd to match or subsume lzo's performance.
4. Maintains the same kernel-specific wrapper API, so no callers have to be modified with zstd version updates.
One concern that was brought up was stack usage. Upstream zstd had already removed most of its heavy stack usage functions, but I just removed the last functions that allocate arrays on the stack. I've measured the high water mark for both compression and decompression before and after this patch. Decompression is approximately neutral, using about 1.2KB of stack space. Compression levels up to 3 regressed from 1.4KB -> 1.6KB, and higher compression levels regressed from 1.5KB -> 2KB. We've added unit tests upstream to prevent further regression. I believe that this is a reasonable increase, and if it does end up causing problems, this commit can be cleanly reverted, because it only touches zstd.
I chose the bulk update instead of replaying upstream commits because there have been ~3500 upstream commits since the 1.3.1 release, zstd wasn't ready to be used in the kernel as-is before a month ago, and not all upstream zstd commits build. The bulk update preserves bisectablity because bugs can be bisected to the zstd version update. At that point the update can be reverted, and we can work with upstream to find and fix the bug.
Note that upstream zstd release 1.4.10 doesn't exist yet. I have cut a staging branch at 4432dac93bea [0] and will apply any changes requested to the staging branch. Once we're ready to merge this update I will cut a zstd release at the commit we merge, so we have a known zstd release in the kernel.
The implementation of the kernel API is contained in zstd_compress_module.c and zstd_decompress_module.c.
[0] https://github.com/facebook/zstd/commit/4432dac93bea0ae7cb48c7f010caee7a103382d3
[1] https://github.com/terrelln/linux/commit/292e2183aeab24b016c8f66ec6ded6006e4298f1
--- include/linux/zstd.h | 11 +- include/linux/zstd_errors.h | 77 + include/linux/zstd_lib.h | 3325 +++++++---- lib/zstd/Makefile | 44 +- lib/zstd/bitstream.h | 380 -- lib/zstd/common/bitstream.h | 437 ++ lib/zstd/common/compiler.h | 151 + lib/zstd/common/cpu.h | 194 + lib/zstd/common/debug.c | 24 + lib/zstd/common/debug.h | 101 + lib/zstd/common/entropy_common.c | 357 ++ lib/zstd/common/error_private.c | 56 + lib/zstd/common/error_private.h | 66 + lib/zstd/common/fse.h | 710 +++ lib/zstd/common/fse_decompress.c | 390 ++ lib/zstd/common/huf.h | 356 ++ lib/zstd/common/mem.h | 259 + lib/zstd/common/zstd_common.c | 83 + lib/zstd/common/zstd_deps.h | 125 + lib/zstd/common/zstd_internal.h | 450 ++ lib/zstd/compress.c | 3534 ------------ lib/zstd/compress/fse_compress.c | 625 ++ lib/zstd/compress/hist.c | 165 + lib/zstd/compress/hist.h | 75 + lib/zstd/compress/huf_compress.c | 902 +++ lib/zstd/compress/zstd_compress.c | 5105 +++++++++++++++++ lib/zstd/compress/zstd_compress_internal.h | 1188 ++++ lib/zstd/compress/zstd_compress_literals.c | 158 + lib/zstd/compress/zstd_compress_literals.h | 29 + lib/zstd/compress/zstd_compress_sequences.c | 439 ++ lib/zstd/compress/zstd_compress_sequences.h | 54 + lib/zstd/compress/zstd_compress_superblock.c | 850 +++ lib/zstd/compress/zstd_compress_superblock.h | 32 + lib/zstd/compress/zstd_cwksp.h | 482 ++ lib/zstd/compress/zstd_double_fast.c | 521 ++ lib/zstd/compress/zstd_double_fast.h | 32 + lib/zstd/compress/zstd_fast.c | 496 ++ lib/zstd/compress/zstd_fast.h | 31 + lib/zstd/compress/zstd_lazy.c | 1412 +++++ lib/zstd/compress/zstd_lazy.h | 81 + lib/zstd/compress/zstd_ldm.c | 686 +++ lib/zstd/compress/zstd_ldm.h | 110 + lib/zstd/compress/zstd_ldm_geartab.h | 103 + lib/zstd/compress/zstd_opt.c | 1345 +++++ lib/zstd/compress/zstd_opt.h | 50 + lib/zstd/decompress.c | 2571 --------- lib/zstd/decompress/huf_decompress.c | 1206 ++++ lib/zstd/decompress/zstd_ddict.c | 241 + lib/zstd/decompress/zstd_ddict.h | 44 + lib/zstd/decompress/zstd_decompress.c | 2075 +++++++ lib/zstd/decompress/zstd_decompress_block.c | 1540 +++++ lib/zstd/decompress/zstd_decompress_block.h | 62 + .../decompress/zstd_decompress_internal.h | 202 + lib/zstd/decompress_sources.h | 15 +- lib/zstd/entropy_common.c | 243 - lib/zstd/error_private.h | 53 - lib/zstd/fse.h | 575 -- lib/zstd/fse_compress.c | 795 --- lib/zstd/fse_decompress.c | 325 -- lib/zstd/huf.h | 212 - lib/zstd/huf_compress.c | 773 --- lib/zstd/huf_decompress.c | 960 ---- lib/zstd/mem.h | 151 - lib/zstd/zstd_common.c | 75 - lib/zstd/zstd_compress_module.c | 124 + lib/zstd/zstd_decompress_module.c | 105 + lib/zstd/zstd_internal.h | 273 - lib/zstd/zstd_opt.h | 1014 ---- 68 files changed, 26765 insertions(+), 12970 deletions(-) create mode 100644 include/linux/zstd_errors.h delete mode 100644 lib/zstd/bitstream.h create mode 100644 lib/zstd/common/bitstream.h create mode 100644 lib/zstd/common/compiler.h create mode 100644 lib/zstd/common/cpu.h create mode 100644 lib/zstd/common/debug.c create mode 100644 lib/zstd/common/debug.h create mode 100644 lib/zstd/common/entropy_common.c create mode 100644 lib/zstd/common/error_private.c create mode 100644 lib/zstd/common/error_private.h create mode 100644 lib/zstd/common/fse.h create mode 100644 lib/zstd/common/fse_decompress.c create mode 100644 lib/zstd/common/huf.h create mode 100644 lib/zstd/common/mem.h create mode 100644 lib/zstd/common/zstd_common.c create mode 100644 lib/zstd/common/zstd_deps.h create mode 100644 lib/zstd/common/zstd_internal.h delete mode 100644 lib/zstd/compress.c create mode 100644 lib/zstd/compress/fse_compress.c create mode 100644 lib/zstd/compress/hist.c create mode 100644 lib/zstd/compress/hist.h create mode 100644 lib/zstd/compress/huf_compress.c create mode 100644 lib/zstd/compress/zstd_compress.c create mode 100644 lib/zstd/compress/zstd_compress_internal.h create mode 100644 lib/zstd/compress/zstd_compress_literals.c create mode 100644 lib/zstd/compress/zstd_compress_literals.h create mode 100644 lib/zstd/compress/zstd_compress_sequences.c create mode 100644 lib/zstd/compress/zstd_compress_sequences.h create mode 100644 lib/zstd/compress/zstd_compress_superblock.c create mode 100644 lib/zstd/compress/zstd_compress_superblock.h create mode 100644 lib/zstd/compress/zstd_cwksp.h create mode 100644 lib/zstd/compress/zstd_double_fast.c create mode 100644 lib/zstd/compress/zstd_double_fast.h create mode 100644 lib/zstd/compress/zstd_fast.c create mode 100644 lib/zstd/compress/zstd_fast.h create mode 100644 lib/zstd/compress/zstd_lazy.c create mode 100644 lib/zstd/compress/zstd_lazy.h create mode 100644 lib/zstd/compress/zstd_ldm.c create mode 100644 lib/zstd/compress/zstd_ldm.h create mode 100644 lib/zstd/compress/zstd_ldm_geartab.h create mode 100644 lib/zstd/compress/zstd_opt.c create mode 100644 lib/zstd/compress/zstd_opt.h delete mode 100644 lib/zstd/decompress.c create mode 100644 lib/zstd/decompress/huf_decompress.c create mode 100644 lib/zstd/decompress/zstd_ddict.c create mode 100644 lib/zstd/decompress/zstd_ddict.h create mode 100644 lib/zstd/decompress/zstd_decompress.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.h create mode 100644 lib/zstd/decompress/zstd_decompress_internal.h delete mode 100644 lib/zstd/entropy_common.c delete mode 100644 lib/zstd/error_private.h delete mode 100644 lib/zstd/fse.h delete mode 100644 lib/zstd/fse_compress.c delete mode 100644 lib/zstd/fse_decompress.c delete mode 100644 lib/zstd/huf.h delete mode 100644 lib/zstd/huf_compress.c delete mode 100644 lib/zstd/huf_decompress.c delete mode 100644 lib/zstd/mem.h delete mode 100644 lib/zstd/zstd_common.c create mode 100644 lib/zstd/zstd_compress_module.c create mode 100644 lib/zstd/zstd_decompress_module.c delete mode 100644 lib/zstd/zstd_internal.h delete mode 100644 lib/zstd/zstd_opt.h
include/linux/zstd.h +9 -2
@@ -22,6 +22,7 @@/* ====== Dependency ====== */ #include <linux/types.h> +#include <linux/zstd_errors.h> #include <linux/zstd_lib.h> /* ====== Helper Functions ====== */
@@ -417,12 +418,18 @@ size_t zstd_find_frame_compressed_size(const void *src, size_t src_size);/** * struct zstd_frame_params - zstd frame parameters stored in the frame header -* @frameContentSize: The frame content size, or 0 if not present. +* @frameContentSize: The frame content size, or ZSTD_CONTENTSIZE_UNKNOWN if not +* present. * @windowSize: The window size, or 0 if the frame is a skippable frame. +* @blockSizeMax: The maximum block size. +* @frameType: The frame type (zstd or skippable) +* @headerSize: The size of the frame header. * @dictID: The dictionary id, or 0 if not present. * @checksumFlag: Whether a checksum was used. +* +* See zstd_lib.h. */ -typedef ZSTD_frameParams zstd_frame_header ; +typedef ZSTD_frameHeader zstd_frame_header ;/** * zstd_get_frame_header() - extracts parameters from a zstd or skippable frame
include/linux/zstd_errors.h new file +77 -0
77 lines not on this page · raw message
include/linux/zstd_lib.h +2300 -1025
2,896 lines not on this page · raw message
lib/zstd/Makefile +40 -4
44 lines not on this page · raw message
lib/zstd/bitstream.h deleted +0 -380
380 lines not on this page · raw message
lib/zstd/common/bitstream.h new file +437 -0
437 lines not on this page · raw message
lib/zstd/common/compiler.h new file +151 -0
151 lines not on this page · raw message
lib/zstd/common/cpu.h new file +194 -0
194 lines not on this page · raw message
lib/zstd/common/debug.h new file +101 -0
101 lines not on this page · raw message
lib/zstd/common/entropy_common.c new file +357 -0
357 lines not on this page · raw message
lib/zstd/common/error_private.c new file +56 -0
56 lines not on this page · raw message
lib/zstd/common/error_private.h new file +66 -0
66 lines not on this page · raw message
lib/zstd/common/fse.h new file +710 -0
710 lines not on this page · raw message
lib/zstd/common/fse_decompress.c new file +390 -0
390 lines not on this page · raw message
lib/zstd/common/huf.h new file +356 -0
356 lines not on this page · raw message
lib/zstd/common/mem.h new file +259 -0
259 lines not on this page · raw message
lib/zstd/common/zstd_common.c new file +83 -0
83 lines not on this page · raw message
lib/zstd/common/zstd_deps.h new file +125 -0
125 lines not on this page · raw message
lib/zstd/common/zstd_internal.h new file +450 -0
450 lines not on this page · raw message
lib/zstd/compress.c deleted +0 -3534
3,534 lines not on this page · raw message
lib/zstd/compress/fse_compress.c new file +625 -0
625 lines not on this page · raw message
lib/zstd/compress/hist.c new file +165 -0
165 lines not on this page · raw message
lib/zstd/compress/hist.h new file +75 -0
75 lines not on this page · raw message
lib/zstd/compress/huf_compress.c new file +902 -0
902 lines not on this page · raw message
lib/zstd/compress/zstd_compress.c new file +5105 -0
5,105 lines not on this page · raw message
lib/zstd/compress/zstd_compress_internal.h new file +1188 -0
1,188 lines not on this page · raw message
lib/zstd/compress/zstd_compress_literals.c new file +158 -0
158 lines not on this page · raw message
lib/zstd/compress/zstd_compress_literals.h new file +29 -0
Lines of this file are not shown. View the raw message.
lib/zstd/compress/zstd_compress_sequences.c new file +439 -0
439 lines not on this page · raw message
lib/zstd/compress/zstd_compress_sequences.h new file +54 -0
54 lines not on this page · raw message
lib/zstd/compress/zstd_compress_superblock.c new file +850 -0
850 lines not on this page · raw message
lib/zstd/compress/zstd_compress_superblock.h new file +32 -0
Lines of this file are not shown. View the raw message.
lib/zstd/compress/zstd_cwksp.h new file +482 -0
482 lines not on this page · raw message
lib/zstd/compress/zstd_double_fast.c new file +521 -0
521 lines not on this page · raw message
lib/zstd/compress/zstd_double_fast.h new file +32 -0
Lines of this file are not shown. View the raw message.
lib/zstd/compress/zstd_fast.c new file +496 -0
496 lines not on this page · raw message
lib/zstd/compress/zstd_fast.h new file +31 -0
Lines of this file are not shown. View the raw message.
lib/zstd/compress/zstd_lazy.c new file +1412 -0
1,412 lines not on this page · raw message
lib/zstd/compress/zstd_lazy.h new file +81 -0
81 lines not on this page · raw message
lib/zstd/compress/zstd_ldm.c new file +686 -0
686 lines not on this page · raw message
lib/zstd/compress/zstd_ldm.h new file +110 -0
110 lines not on this page · raw message
lib/zstd/compress/zstd_ldm_geartab.h new file +103 -0
103 lines not on this page · raw message
lib/zstd/compress/zstd_opt.c new file +1345 -0
1,345 lines not on this page · raw message
lib/zstd/compress/zstd_opt.h new file +50 -0
50 lines not on this page · raw message
lib/zstd/decompress.c deleted +0 -2571
2,571 lines not on this page · raw message
lib/zstd/decompress/huf_decompress.c new file +1206 -0
1,206 lines not on this page · raw message
lib/zstd/decompress/zstd_ddict.c new file +241 -0
241 lines not on this page · raw message
lib/zstd/decompress/zstd_ddict.h new file +44 -0
44 lines not on this page · raw message
lib/zstd/decompress/zstd_decompress.c new file +2075 -0
2,075 lines not on this page · raw message
lib/zstd/decompress/zstd_decompress_block.c new file +1540 -0
1,540 lines not on this page · raw message
lib/zstd/decompress/zstd_decompress_block.h new file +62 -0
62 lines not on this page · raw message
lib/zstd/decompress/zstd_decompress_internal.h new file +202 -0
202 lines not on this page · raw message
lib/zstd/entropy_common.c deleted +0 -243
243 lines not on this page · raw message
lib/zstd/error_private.h deleted +0 -53
53 lines not on this page · raw message
lib/zstd/fse.h deleted +0 -575
575 lines not on this page · raw message
lib/zstd/fse_compress.c deleted +0 -795
795 lines not on this page · raw message
lib/zstd/fse_decompress.c deleted +0 -325
325 lines not on this page · raw message
lib/zstd/huf.h deleted +0 -212
212 lines not on this page · raw message
lib/zstd/huf_compress.c deleted +0 -773
773 lines not on this page · raw message
lib/zstd/huf_decompress.c deleted +0 -960
960 lines not on this page · raw message
lib/zstd/mem.h deleted +0 -151
151 lines not on this page · raw message
lib/zstd/zstd_common.c deleted +0 -75
75 lines not on this page · raw message
lib/zstd/zstd_compress_module.c new file +124 -0
124 lines not on this page · raw message
lib/zstd/zstd_decompress_module.c new file +105 -0
105 lines not on this page · raw message
lib/zstd/zstd_internal.h deleted +0 -273
273 lines not on this page · raw message
lib/zstd/zstd_opt.h deleted +0 -1014
1,014 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 8 lines
2.31.0 _______________________________________________ Linux-f2fs-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
Part of the diff is not shown here. View the raw message.
Oleksandr Natalenko
Tested-byHello.
Quoted 298 lines · Nick Terrell
From: Nick Terrell <[email protected]>
Please pull from
[email protected]:terrelln/linux.git tags/v9-zstd-1.4.10
to get these changes. Alternatively the patchset is included.
This patchset upgrades the zstd library to the latest upstream release. The current zstd version in the kernel is a modified version of upstream zstd-1.3.1. At the time it was integrated, zstd wasn't ready to be used in the kernel as-is. But, it is now possible to use upstream zstd directly in the kernel.
I have not yet released zstd-1.4.10 upstream. I want the zstd version in the kernel to match up with a known upstream release, so we know exactly what code is running. Whenever this patchset is ready for merge, I will cut a release at the upstream commit that gets merged. This should not be necessary for future releases.
The kernel zstd library is automatically generated from upstream zstd. A script makes the necessary changes and imports it into the kernel. The changes are:
1. Replace all libc dependencies with kernel replacements and rewrite includes.
2. Remove unncessary portability macros like: #ifdefined(_MSC_VER).
3. Use the kernel xxhash instead of bundling it.This automation gets tested every commit by upstream's continuous integration. When we cut a new zstd release, we will submit a patch to the kernel to update the zstd version in the kernel.
I've updated zstd to upstream with one big patch because every commit must build, so that precludes partial updates. Since the commit is 100% generated, I hope the review burden is lightened. I considered replaying upstream commits, but that is not possible because there have been ~3500 upstream commits since the last zstd import, and the commits don't all build individually. The bulk update preserves bisectablity because bugs can be bisected to the zstd version update. At that point the update can be reverted, and we can work with upstream to find and fix the bug. After this big switch in how the kernel consumes zstd, future patches will be smaller, because they will only have one upstream release worth of changes each.
This patchset adds a new kernel-style wrapper around zstd. This wrapper API is functionally equivalent to the subset of the current zstd API that is currently used. The wrapper API changes to be kernel style so that the symbols don't collide with zstd's symbols. The update to zstd-1.4.6 maintains the same API and preserves the semantics, so that none of the callers need to be updated.
This patchset comes in 2 parts:
1. The first 2 patches prepare for the zstd upgrade. The first patch adds the new kernel style API so zstd can be upgraded without modifying any callers. The second patch adds an indirection for thelib/decompress_unzstd.cincluding of all decompression source files.
2. Import zstd-1.4.10. This patch is completely generated from upstream using automated tooling.I tested every caller of zstd on
x86_64. I tested both after the 1.4.10 upgrade using the compatibility wrapper, and after the final patch in this series.I tested kernel and initramfs decompression in i386 and arm.
I ran benchmarks to compare the current zstd in the kernel with zstd-1.4.6. I benchmarked on
x86_64using QEMU with KVM enabled on an Intel i9-9900k. I found:
* BtrFS zstd compression at levels 1 and 3 is 5% faster
* BtrFS zstd decompression+read is 15% faster
* SquashFS zstd decompression+read is 15% faster
* F2FS zstd compression+write at level 3 is 8% faster
* F2FS zstd decompression+read is 20% faster
* ZRAM decompression+read is 30% faster
* Kernel zstd decompression is 35% faster
* Initramfs zstd decompression+build is 5% fasterThe latest zstd also offers bug fixes. For example the problem with large kernel decompression has been fixed upstream for over 2 years
https://lkml.org/lkml/2020/9/29/27.Please let me know if there is anything that I can do to ease the way for these patches. I think it is important because it gets large performance improvements, contains bug fixes, and is switching to a more maintainable model of consuming upstream zstd directly, making it easy to keep up to date.
Best,
Nick Terrellv1 -> v2:
* Successfully tested F2FS with help from Chao Yu to fix my test.
* (1/9) FixZSTD_initCStream()wrapper to handle pledged_src_size=0 means unknown. This fixes F2FS with the zstd-1.4.6 compatibility wrapper, exposed by the test.v2 -> v3:
* (3/9) Silence warnings by Kernel Test Robot:
https://github.com/facebook/zstd/pull/2324
Stack size warnings remain, but these aren't new, and the functions it warns on are either unused or not in the maximum stack path. This patchset reduces zstd compression stack usage by 1 KB overall. I've gotten the low hanging fruit, and more stack reduction would require significant changes that have the potential to introduce new bugs. However, I do hope to continue to reduce zstd stack usage in future versions.v3 -> v4:
* (3/9) Fix errors and warnings reported by Kernel Test Robot:
https://github.com/facebook/zstd/pull/2326
- Replacemem.hwith a custom kernel implementation that matches the currentlib/zstd/mem.hin the kernel. This avoids calls to __builtin_bswap*() which don't work on certain architectures, as exposed by the Kernel Test Robot.
- Remove ASAN/MSAN (un)poisoning code which doesn't work in the kernel, as exposed by the Kernel Test Robot.
- I've fixed all of the valid cppcheck warnings reported, but there were many false positives, where cppcheck was incorrectly analyzing the situation, which I did not fix. I don't believe it is reasonable to expect that upstream zstd silences all the static analyzer false positives. Upstream zstd uses clang scan-build for its static analysis. We find that supporting multiple static analysis tools multiplies the burden of silencing false positives, without providing enough marginal value over running a single static analysis tool.v4 -> v5:
* Rebase onto v5.10-rc2
* (6/9) Merge with other F2FS changes (no functional change in patch).v5 -> v6:
* Rebase onto v5.10-rc6.
* Switch to using a kernel style wrapper API as suggested by Cristoph.v6 -> v7:
* Expose the upstream library header asinclude/linux/zstd_lib.h. Instead of creating new structs mirroring the upstream zstd structs use upstream's structs directly with a typedef to get a kernel style name. This removes the memcpy cruft.
* (1/3) UndoZSTD_WINDOWLOG_MAXandhandle_zstd_errorchanges.
* (3/3) Exposezstd_errors.hasinclude/linux/zstd_errors.hbecause it is needed by the kernel wrapper API.v7 -> v8:
* (1/3) Fix typo inEXPORT_SYMBOL().
* (1/3) Fix typo inzstd.hcomments.
* (3/3) Update to latest zstd release: 1.4.6 -> 1.4.10 This includes ~1KB of stack space reductions.v8 -> v9:
* (1/3) Rebase onto v5.12-rc5
* (1/3) Addzstd_min_clevel()&zstd_max_clevel()and use in f2fs. Thanks to Oleksandr Natalenko for spotting it!
* (1/3) Movelib/decompress_unzstd.cusage ofZSTD_getErrorCode()tozstd_get_error_code().
* (1/3) Update modified zstd headers to yearless copyright.
* (2/3) Add copyright/license header todecompress_sources.hfor consistency.
* (3/3) Update to yearless copyright for all zstd files. Thanks to Mike Dolan for spotting it!Nick Terrell (3):
lib: zstd: Add kernel-specific API
lib: zstd: Adddecompress_sources.hfordecompress_unzstd
lib: zstd: Upgrade to latest upstream zstd version 1.4.10crypto/zstd.c | 28 +- fs/btrfs/zstd.c | 68 +- fs/f2fs/compress.c | 56 +- fs/f2fs/super.c | 2 +- fs/pstore/platform.c | 2 +- fs/squashfs/zstd_wrapper.c | 16 +- include/linux/zstd.h | 1252 +--- include/linux/zstd_errors.h | 77 + include/linux/zstd_lib.h | 2432 ++++++++ lib/decompress_unzstd.c | 48 +- lib/zstd/Makefile | 44 +- lib/zstd/bitstream.h | 380 -- lib/zstd/common/bitstream.h | 437 ++ lib/zstd/common/compiler.h | 151 + lib/zstd/common/cpu.h | 194 + lib/zstd/common/debug.c | 24 + lib/zstd/common/debug.h | 101 + lib/zstd/common/entropy_common.c | 357 ++ lib/zstd/common/error_private.c | 56 + lib/zstd/common/error_private.h | 66 + lib/zstd/common/fse.h | 710 +++ lib/zstd/common/fse_decompress.c | 390 ++ lib/zstd/common/huf.h | 356 ++ lib/zstd/common/mem.h | 259 + lib/zstd/common/zstd_common.c | 83 + lib/zstd/common/zstd_deps.h | 125 + lib/zstd/common/zstd_internal.h | 450 ++ lib/zstd/compress.c | 3485 ----------- lib/zstd/compress/fse_compress.c | 625 ++ lib/zstd/compress/hist.c | 165 + lib/zstd/compress/hist.h | 75 + lib/zstd/compress/huf_compress.c | 902 +++ lib/zstd/compress/zstd_compress.c | 5105 +++++++++++++++++ lib/zstd/compress/zstd_compress_internal.h | 1188 ++++ lib/zstd/compress/zstd_compress_literals.c | 158 + lib/zstd/compress/zstd_compress_literals.h | 29 + lib/zstd/compress/zstd_compress_sequences.c | 439 ++ lib/zstd/compress/zstd_compress_sequences.h | 54 + lib/zstd/compress/zstd_compress_superblock.c | 850 +++ lib/zstd/compress/zstd_compress_superblock.h | 32 + lib/zstd/compress/zstd_cwksp.h | 482 ++ lib/zstd/compress/zstd_double_fast.c | 521 ++ lib/zstd/compress/zstd_double_fast.h | 32 + lib/zstd/compress/zstd_fast.c | 496 ++ lib/zstd/compress/zstd_fast.h | 31 + lib/zstd/compress/zstd_lazy.c | 1412 +++++ lib/zstd/compress/zstd_lazy.h | 81 + lib/zstd/compress/zstd_ldm.c | 686 +++ lib/zstd/compress/zstd_ldm.h | 110 + lib/zstd/compress/zstd_ldm_geartab.h | 103 + lib/zstd/compress/zstd_opt.c | 1345 +++++ lib/zstd/compress/zstd_opt.h | 50 + lib/zstd/decompress.c | 2531 -------- lib/zstd/decompress/huf_decompress.c | 1206 ++++ lib/zstd/decompress/zstd_ddict.c | 241 + lib/zstd/decompress/zstd_ddict.h | 44 + lib/zstd/decompress/zstd_decompress.c | 2075 +++++++ lib/zstd/decompress/zstd_decompress_block.c | 1540 +++++ lib/zstd/decompress/zstd_decompress_block.h | 62 + .../decompress/zstd_decompress_internal.h | 202 + lib/zstd/decompress_sources.h | 28 + lib/zstd/entropy_common.c | 243 - lib/zstd/error_private.h | 53 - lib/zstd/fse.h | 575 -- lib/zstd/fse_compress.c | 795 --- lib/zstd/fse_decompress.c | 325 -- lib/zstd/huf.h | 212 - lib/zstd/huf_compress.c | 773 --- lib/zstd/huf_decompress.c | 960 ---- lib/zstd/mem.h | 151 - lib/zstd/zstd_common.c | 75 - lib/zstd/zstd_compress_module.c | 124 + lib/zstd/zstd_decompress_module.c | 105 + lib/zstd/zstd_internal.h | 273 - lib/zstd/zstd_opt.h | 1014 ---- 75 files changed, 27287 insertions(+), 12940 deletions(-) create mode 100644 include/linux/zstd_errors.h create mode 100644 include/linux/zstd_lib.h delete mode 100644 lib/zstd/bitstream.h create mode 100644 lib/zstd/common/bitstream.h create mode 100644 lib/zstd/common/compiler.h create mode 100644 lib/zstd/common/cpu.h create mode 100644 lib/zstd/common/debug.c create mode 100644 lib/zstd/common/debug.h create mode 100644 lib/zstd/common/entropy_common.c create mode 100644 lib/zstd/common/error_private.c create mode 100644 lib/zstd/common/error_private.h create mode 100644 lib/zstd/common/fse.h create mode 100644 lib/zstd/common/fse_decompress.c create mode 100644 lib/zstd/common/huf.h create mode 100644 lib/zstd/common/mem.h create mode 100644 lib/zstd/common/zstd_common.c create mode 100644 lib/zstd/common/zstd_deps.h create mode 100644 lib/zstd/common/zstd_internal.h delete mode 100644 lib/zstd/compress.c create mode 100644 lib/zstd/compress/fse_compress.c create mode 100644 lib/zstd/compress/hist.c create mode 100644 lib/zstd/compress/hist.h create mode 100644 lib/zstd/compress/huf_compress.c create mode 100644 lib/zstd/compress/zstd_compress.c create mode 100644 lib/zstd/compress/zstd_compress_internal.h create mode 100644 lib/zstd/compress/zstd_compress_literals.c create mode 100644 lib/zstd/compress/zstd_compress_literals.h create mode 100644 lib/zstd/compress/zstd_compress_sequences.c create mode 100644 lib/zstd/compress/zstd_compress_sequences.h create mode 100644 lib/zstd/compress/zstd_compress_superblock.c create mode 100644 lib/zstd/compress/zstd_compress_superblock.h create mode 100644 lib/zstd/compress/zstd_cwksp.h create mode 100644 lib/zstd/compress/zstd_double_fast.c create mode 100644 lib/zstd/compress/zstd_double_fast.h create mode 100644 lib/zstd/compress/zstd_fast.c create mode 100644 lib/zstd/compress/zstd_fast.h create mode 100644 lib/zstd/compress/zstd_lazy.c create mode 100644 lib/zstd/compress/zstd_lazy.h create mode 100644 lib/zstd/compress/zstd_ldm.c create mode 100644 lib/zstd/compress/zstd_ldm.h create mode 100644 lib/zstd/compress/zstd_ldm_geartab.h create mode 100644 lib/zstd/compress/zstd_opt.c create mode 100644 lib/zstd/compress/zstd_opt.h delete mode 100644 lib/zstd/decompress.c create mode 100644 lib/zstd/decompress/huf_decompress.c create mode 100644 lib/zstd/decompress/zstd_ddict.c create mode 100644 lib/zstd/decompress/zstd_ddict.h create mode 100644 lib/zstd/decompress/zstd_decompress.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.h create mode 100644 lib/zstd/decompress/zstd_decompress_internal.h create mode 100644 lib/zstd/decompress_sources.h delete mode 100644 lib/zstd/entropy_common.c delete mode 100644 lib/zstd/error_private.h delete mode 100644 lib/zstd/fse.h delete mode 100644 lib/zstd/fse_compress.c delete mode 100644 lib/zstd/fse_decompress.c delete mode 100644 lib/zstd/huf.h delete mode 100644 lib/zstd/huf_compress.c delete mode 100644 lib/zstd/huf_decompress.c delete mode 100644 lib/zstd/mem.h delete mode 100644 lib/zstd/zstd_common.c create mode 100644 lib/zstd/zstd_compress_module.c create mode 100644 lib/zstd/zstd_decompress_module.c delete mode 100644 lib/zstd/zstd_internal.h delete mode 100644 lib/zstd/zstd_opt.h
Quoted 3 lines
--
2.31.0
Running this series for quite some time already (v9 as well as previous submissions) on different machines without any issues.
Hence, for the series:
Thanks!
Signature · 1 line
Oleksandr Natalenko (post-factum)
What can I do to help get this merged?
Cristoph, is this new patch series with the kernel wrapper API satisfactory?
Best,
Nick
Quoted 302 lines · Nick Terrell
From: Nick Terrell <[email protected]>
Please pull from
[email protected]:terrelln/linux.git tags/v9-zstd-1.4.10
to get these changes. Alternatively the patchset is included.
This patchset upgrades the zstd library to the latest upstream release. The current zstd version in the kernel is a modified version of upstream zstd-1.3.1. At the time it was integrated, zstd wasn't ready to be used in the kernel as-is. But, it is now possible to use upstream zstd directly in the kernel.
I have not yet released zstd-1.4.10 upstream. I want the zstd version in the kernel to match up with a known upstream release, so we know exactly what code is running. Whenever this patchset is ready for merge, I will cut a release at the upstream commit that gets merged. This should not be necessary for future releases.
The kernel zstd library is automatically generated from upstream zstd. A script makes the necessary changes and imports it into the kernel. The changes are:
1. Replace all libc dependencies with kernel replacements and rewrite includes.
2. Remove unncessary portability macros like: #ifdefined(_MSC_VER).
3. Use the kernel xxhash instead of bundling it.This automation gets tested every commit by upstream's continuous integration. When we cut a new zstd release, we will submit a patch to the kernel to update the zstd version in the kernel.
I've updated zstd to upstream with one big patch because every commit must build, so that precludes partial updates. Since the commit is 100% generated, I hope the review burden is lightened. I considered replaying upstream commits, but that is not possible because there have been ~3500 upstream commits since the last zstd import, and the commits don't all build individually. The bulk update preserves bisectablity because bugs can be bisected to the zstd version update. At that point the update can be reverted, and we can work with upstream to find and fix the bug. After this big switch in how the kernel consumes zstd, future patches will be smaller, because they will only have one upstream release worth of changes each.
This patchset adds a new kernel-style wrapper around zstd. This wrapper API is functionally equivalent to the subset of the current zstd API that is currently used. The wrapper API changes to be kernel style so that the symbols don't collide with zstd's symbols. The update to zstd-1.4.6 maintains the same API and preserves the semantics, so that none of the callers need to be updated.
This patchset comes in 2 parts:
1. The first 2 patches prepare for the zstd upgrade. The first patch adds the new kernel style API so zstd can be upgraded without modifying any callers. The second patch adds an indirection for thelib/decompress_unzstd.cincluding of all decompression source files.
2. Import zstd-1.4.10. This patch is completely generated from upstream using automated tooling.I tested every caller of zstd on
x86_64. I tested both after the 1.4.10 upgrade using the compatibility wrapper, and after the final patch in this series.I tested kernel and initramfs decompression in i386 and arm.
I ran benchmarks to compare the current zstd in the kernel with zstd-1.4.6. I benchmarked on
x86_64using QEMU with KVM enabled on an Intel i9-9900k. I found:
* BtrFS zstd compression at levels 1 and 3 is 5% faster
* BtrFS zstd decompression+read is 15% faster
* SquashFS zstd decompression+read is 15% faster
* F2FS zstd compression+write at level 3 is 8% faster
* F2FS zstd decompression+read is 20% faster
* ZRAM decompression+read is 30% faster
* Kernel zstd decompression is 35% faster
* Initramfs zstd decompression+build is 5% fasterThe latest zstd also offers bug fixes. For example the problem with large kernel decompression has been fixed upstream for over 2 years
https://lkml.org/lkml/2020/9/29/27.Please let me know if there is anything that I can do to ease the way for these patches. I think it is important because it gets large performance improvements, contains bug fixes, and is switching to a more maintainable model of consuming upstream zstd directly, making it easy to keep up to date.
Best,
Nick Terrellv1 -> v2:
* Successfully tested F2FS with help from Chao Yu to fix my test.
* (1/9) FixZSTD_initCStream()wrapper to handle pledged_src_size=0 means unknown. This fixes F2FS with the zstd-1.4.6 compatibility wrapper, exposed by the test.v2 -> v3:
* (3/9) Silence warnings by Kernel Test Robot:
https://github.com/facebook/zstd/pull/2324
Stack size warnings remain, but these aren't new, and the functions it warns on are either unused or not in the maximum stack path. This patchset reduces zstd compression stack usage by 1 KB overall. I've gotten the low hanging fruit, and more stack reduction would require significant changes that have the potential to introduce new bugs. However, I do hope to continue to reduce zstd stack usage in future versions.v3 -> v4:
* (3/9) Fix errors and warnings reported by Kernel Test Robot:
https://github.com/facebook/zstd/pull/2326
- Replacemem.hwith a custom kernel implementation that matches the currentlib/zstd/mem.hin the kernel. This avoids calls to __builtin_bswap*() which don't work on certain architectures, as exposed by the Kernel Test Robot.
- Remove ASAN/MSAN (un)poisoning code which doesn't work in the kernel, as exposed by the Kernel Test Robot.
- I've fixed all of the valid cppcheck warnings reported, but there were many false positives, where cppcheck was incorrectly analyzing the situation, which I did not fix. I don't believe it is reasonable to expect that upstream zstd silences all the static analyzer false positives. Upstream zstd uses clang scan-build for its static analysis. We find that supporting multiple static analysis tools multiplies the burden of silencing false positives, without providing enough marginal value over running a single static analysis tool.v4 -> v5:
* Rebase onto v5.10-rc2
* (6/9) Merge with other F2FS changes (no functional change in patch).v5 -> v6:
* Rebase onto v5.10-rc6.
* Switch to using a kernel style wrapper API as suggested by Cristoph.v6 -> v7:
* Expose the upstream library header asinclude/linux/zstd_lib.h. Instead of creating new structs mirroring the upstream zstd structs use upstream's structs directly with a typedef to get a kernel style name. This removes the memcpy cruft.
* (1/3) UndoZSTD_WINDOWLOG_MAXandhandle_zstd_errorchanges.
* (3/3) Exposezstd_errors.hasinclude/linux/zstd_errors.hbecause it is needed by the kernel wrapper API.v7 -> v8:
* (1/3) Fix typo inEXPORT_SYMBOL().
* (1/3) Fix typo inzstd.hcomments.
* (3/3) Update to latest zstd release: 1.4.6 -> 1.4.10 This includes ~1KB of stack space reductions.v8 -> v9:
* (1/3) Rebase onto v5.12-rc5
* (1/3) Addzstd_min_clevel()&zstd_max_clevel()and use in f2fs. Thanks to Oleksandr Natalenko for spotting it!
* (1/3) Movelib/decompress_unzstd.cusage ofZSTD_getErrorCode()tozstd_get_error_code().
* (1/3) Update modified zstd headers to yearless copyright.
* (2/3) Add copyright/license header todecompress_sources.hfor consistency.
* (3/3) Update to yearless copyright for all zstd files. Thanks to Mike Dolan for spotting it!Nick Terrell (3):
lib: zstd: Add kernel-specific API
lib: zstd: Adddecompress_sources.hfordecompress_unzstd
lib: zstd: Upgrade to latest upstream zstd version 1.4.10crypto/zstd.c | 28 +- fs/btrfs/zstd.c | 68 +- fs/f2fs/compress.c | 56 +- fs/f2fs/super.c | 2 +- fs/pstore/platform.c | 2 +- fs/squashfs/zstd_wrapper.c | 16 +- include/linux/zstd.h | 1252 +--- include/linux/zstd_errors.h | 77 + include/linux/zstd_lib.h | 2432 ++++++++ lib/decompress_unzstd.c | 48 +- lib/zstd/Makefile | 44 +- lib/zstd/bitstream.h | 380 -- lib/zstd/common/bitstream.h | 437 ++ lib/zstd/common/compiler.h | 151 + lib/zstd/common/cpu.h | 194 + lib/zstd/common/debug.c | 24 + lib/zstd/common/debug.h | 101 + lib/zstd/common/entropy_common.c | 357 ++ lib/zstd/common/error_private.c | 56 + lib/zstd/common/error_private.h | 66 + lib/zstd/common/fse.h | 710 +++ lib/zstd/common/fse_decompress.c | 390 ++ lib/zstd/common/huf.h | 356 ++ lib/zstd/common/mem.h | 259 + lib/zstd/common/zstd_common.c | 83 + lib/zstd/common/zstd_deps.h | 125 + lib/zstd/common/zstd_internal.h | 450 ++ lib/zstd/compress.c | 3485 ----------- lib/zstd/compress/fse_compress.c | 625 ++ lib/zstd/compress/hist.c | 165 + lib/zstd/compress/hist.h | 75 + lib/zstd/compress/huf_compress.c | 902 +++ lib/zstd/compress/zstd_compress.c | 5105 +++++++++++++++++ lib/zstd/compress/zstd_compress_internal.h | 1188 ++++ lib/zstd/compress/zstd_compress_literals.c | 158 + lib/zstd/compress/zstd_compress_literals.h | 29 + lib/zstd/compress/zstd_compress_sequences.c | 439 ++ lib/zstd/compress/zstd_compress_sequences.h | 54 + lib/zstd/compress/zstd_compress_superblock.c | 850 +++ lib/zstd/compress/zstd_compress_superblock.h | 32 + lib/zstd/compress/zstd_cwksp.h | 482 ++ lib/zstd/compress/zstd_double_fast.c | 521 ++ lib/zstd/compress/zstd_double_fast.h | 32 + lib/zstd/compress/zstd_fast.c | 496 ++ lib/zstd/compress/zstd_fast.h | 31 + lib/zstd/compress/zstd_lazy.c | 1412 +++++ lib/zstd/compress/zstd_lazy.h | 81 + lib/zstd/compress/zstd_ldm.c | 686 +++ lib/zstd/compress/zstd_ldm.h | 110 + lib/zstd/compress/zstd_ldm_geartab.h | 103 + lib/zstd/compress/zstd_opt.c | 1345 +++++ lib/zstd/compress/zstd_opt.h | 50 + lib/zstd/decompress.c | 2531 -------- lib/zstd/decompress/huf_decompress.c | 1206 ++++ lib/zstd/decompress/zstd_ddict.c | 241 + lib/zstd/decompress/zstd_ddict.h | 44 + lib/zstd/decompress/zstd_decompress.c | 2075 +++++++ lib/zstd/decompress/zstd_decompress_block.c | 1540 +++++ lib/zstd/decompress/zstd_decompress_block.h | 62 + .../decompress/zstd_decompress_internal.h | 202 + lib/zstd/decompress_sources.h | 28 + lib/zstd/entropy_common.c | 243 - lib/zstd/error_private.h | 53 - lib/zstd/fse.h | 575 -- lib/zstd/fse_compress.c | 795 --- lib/zstd/fse_decompress.c | 325 -- lib/zstd/huf.h | 212 - lib/zstd/huf_compress.c | 773 --- lib/zstd/huf_decompress.c | 960 ---- lib/zstd/mem.h | 151 - lib/zstd/zstd_common.c | 75 - lib/zstd/zstd_compress_module.c | 124 + lib/zstd/zstd_decompress_module.c | 105 + lib/zstd/zstd_internal.h | 273 - lib/zstd/zstd_opt.h | 1014 ---- 75 files changed, 27287 insertions(+), 12940 deletions(-) create mode 100644 include/linux/zstd_errors.h create mode 100644 include/linux/zstd_lib.h delete mode 100644 lib/zstd/bitstream.h create mode 100644 lib/zstd/common/bitstream.h create mode 100644 lib/zstd/common/compiler.h create mode 100644 lib/zstd/common/cpu.h create mode 100644 lib/zstd/common/debug.c create mode 100644 lib/zstd/common/debug.h create mode 100644 lib/zstd/common/entropy_common.c create mode 100644 lib/zstd/common/error_private.c create mode 100644 lib/zstd/common/error_private.h create mode 100644 lib/zstd/common/fse.h create mode 100644 lib/zstd/common/fse_decompress.c create mode 100644 lib/zstd/common/huf.h create mode 100644 lib/zstd/common/mem.h create mode 100644 lib/zstd/common/zstd_common.c create mode 100644 lib/zstd/common/zstd_deps.h create mode 100644 lib/zstd/common/zstd_internal.h delete mode 100644 lib/zstd/compress.c create mode 100644 lib/zstd/compress/fse_compress.c create mode 100644 lib/zstd/compress/hist.c create mode 100644 lib/zstd/compress/hist.h create mode 100644 lib/zstd/compress/huf_compress.c create mode 100644 lib/zstd/compress/zstd_compress.c create mode 100644 lib/zstd/compress/zstd_compress_internal.h create mode 100644 lib/zstd/compress/zstd_compress_literals.c create mode 100644 lib/zstd/compress/zstd_compress_literals.h create mode 100644 lib/zstd/compress/zstd_compress_sequences.c create mode 100644 lib/zstd/compress/zstd_compress_sequences.h create mode 100644 lib/zstd/compress/zstd_compress_superblock.c create mode 100644 lib/zstd/compress/zstd_compress_superblock.h create mode 100644 lib/zstd/compress/zstd_cwksp.h create mode 100644 lib/zstd/compress/zstd_double_fast.c create mode 100644 lib/zstd/compress/zstd_double_fast.h create mode 100644 lib/zstd/compress/zstd_fast.c create mode 100644 lib/zstd/compress/zstd_fast.h create mode 100644 lib/zstd/compress/zstd_lazy.c create mode 100644 lib/zstd/compress/zstd_lazy.h create mode 100644 lib/zstd/compress/zstd_ldm.c create mode 100644 lib/zstd/compress/zstd_ldm.h create mode 100644 lib/zstd/compress/zstd_ldm_geartab.h create mode 100644 lib/zstd/compress/zstd_opt.c create mode 100644 lib/zstd/compress/zstd_opt.h delete mode 100644 lib/zstd/decompress.c create mode 100644 lib/zstd/decompress/huf_decompress.c create mode 100644 lib/zstd/decompress/zstd_ddict.c create mode 100644 lib/zstd/decompress/zstd_ddict.h create mode 100644 lib/zstd/decompress/zstd_decompress.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.h create mode 100644 lib/zstd/decompress/zstd_decompress_internal.h create mode 100644 lib/zstd/decompress_sources.h delete mode 100644 lib/zstd/entropy_common.c delete mode 100644 lib/zstd/error_private.h delete mode 100644 lib/zstd/fse.h delete mode 100644 lib/zstd/fse_compress.c delete mode 100644 lib/zstd/fse_decompress.c delete mode 100644 lib/zstd/huf.h delete mode 100644 lib/zstd/huf_compress.c delete mode 100644 lib/zstd/huf_decompress.c delete mode 100644 lib/zstd/mem.h delete mode 100644 lib/zstd/zstd_common.c create mode 100644 lib/zstd/zstd_compress_module.c create mode 100644 lib/zstd/zstd_decompress_module.c delete mode 100644 lib/zstd/zstd_internal.h delete mode 100644 lib/zstd/zstd_opt.h--
2.31.0
Hi all,
I would really like to make some progress on this and get it merged. This patchset offsers:
* 15-30% better decompression speed
* 3 years of zstd bug fixes and code improvements
* Allows us to import zstd directly from upstream so we don't fall 3 years out of date again
Thanks,
Nick
Quoted 311 lines · Nick Terrell
What can I do to help get this merged?
Cristoph, is this new patch series with the kernel wrapper API satisfactory?
Best,
NickQuoted 302 lines · Nick Terrell
From: Nick Terrell <[email protected]>
Please pull from
[email protected]:terrelln/linux.git tags/v9-zstd-1.4.10
to get these changes. Alternatively the patchset is included.
This patchset upgrades the zstd library to the latest upstream release. The current zstd version in the kernel is a modified version of upstream zstd-1.3.1. At the time it was integrated, zstd wasn't ready to be used in the kernel as-is. But, it is now possible to use upstream zstd directly in the kernel.
I have not yet released zstd-1.4.10 upstream. I want the zstd version in the kernel to match up with a known upstream release, so we know exactly what code is running. Whenever this patchset is ready for merge, I will cut a release at the upstream commit that gets merged. This should not be necessary for future releases.
The kernel zstd library is automatically generated from upstream zstd. A script makes the necessary changes and imports it into the kernel. The changes are:
1. Replace all libc dependencies with kernel replacements and rewrite includes.
2. Remove unncessary portability macros like: #ifdefined(_MSC_VER).
3. Use the kernel xxhash instead of bundling it.This automation gets tested every commit by upstream's continuous integration. When we cut a new zstd release, we will submit a patch to the kernel to update the zstd version in the kernel.
I've updated zstd to upstream with one big patch because every commit must build, so that precludes partial updates. Since the commit is 100% generated, I hope the review burden is lightened. I considered replaying upstream commits, but that is not possible because there have been ~3500 upstream commits since the last zstd import, and the commits don't all build individually. The bulk update preserves bisectablity because bugs can be bisected to the zstd version update. At that point the update can be reverted, and we can work with upstream to find and fix the bug. After this big switch in how the kernel consumes zstd, future patches will be smaller, because they will only have one upstream release worth of changes each.
This patchset adds a new kernel-style wrapper around zstd. This wrapper API is functionally equivalent to the subset of the current zstd API that is currently used. The wrapper API changes to be kernel style so that the symbols don't collide with zstd's symbols. The update to zstd-1.4.6 maintains the same API and preserves the semantics, so that none of the callers need to be updated.
This patchset comes in 2 parts:
1. The first 2 patches prepare for the zstd upgrade. The first patch adds the new kernel style API so zstd can be upgraded without modifying any callers. The second patch adds an indirection for thelib/decompress_unzstd.cincluding of all decompression source files.
2. Import zstd-1.4.10. This patch is completely generated from upstream using automated tooling.I tested every caller of zstd on
x86_64. I tested both after the 1.4.10 upgrade using the compatibility wrapper, and after the final patch in this series.I tested kernel and initramfs decompression in i386 and arm.
I ran benchmarks to compare the current zstd in the kernel with zstd-1.4.6. I benchmarked on
x86_64using QEMU with KVM enabled on an Intel i9-9900k. I found:
* BtrFS zstd compression at levels 1 and 3 is 5% faster
* BtrFS zstd decompression+read is 15% faster
* SquashFS zstd decompression+read is 15% faster
* F2FS zstd compression+write at level 3 is 8% faster
* F2FS zstd decompression+read is 20% faster
* ZRAM decompression+read is 30% faster
* Kernel zstd decompression is 35% faster
* Initramfs zstd decompression+build is 5% fasterThe latest zstd also offers bug fixes. For example the problem with large kernel decompression has been fixed upstream for over 2 years
https://lkml.org/lkml/2020/9/29/27.Please let me know if there is anything that I can do to ease the way for these patches. I think it is important because it gets large performance improvements, contains bug fixes, and is switching to a more maintainable model of consuming upstream zstd directly, making it easy to keep up to date.
Best,
Nick Terrellv1 -> v2:
* Successfully tested F2FS with help from Chao Yu to fix my test.
* (1/9) FixZSTD_initCStream()wrapper to handle pledged_src_size=0 means unknown. This fixes F2FS with the zstd-1.4.6 compatibility wrapper, exposed by the test.v2 -> v3:
* (3/9) Silence warnings by Kernel Test Robot:
https://github.com/facebook/zstd/pull/2324
Stack size warnings remain, but these aren't new, and the functions it warns on are either unused or not in the maximum stack path. This patchset reduces zstd compression stack usage by 1 KB overall. I've gotten the low hanging fruit, and more stack reduction would require significant changes that have the potential to introduce new bugs. However, I do hope to continue to reduce zstd stack usage in future versions.v3 -> v4:
* (3/9) Fix errors and warnings reported by Kernel Test Robot:
https://github.com/facebook/zstd/pull/2326
- Replacemem.hwith a custom kernel implementation that matches the currentlib/zstd/mem.hin the kernel. This avoids calls to __builtin_bswap*() which don't work on certain architectures, as exposed by the Kernel Test Robot.
- Remove ASAN/MSAN (un)poisoning code which doesn't work in the kernel, as exposed by the Kernel Test Robot.
- I've fixed all of the valid cppcheck warnings reported, but there were many false positives, where cppcheck was incorrectly analyzing the situation, which I did not fix. I don't believe it is reasonable to expect that upstream zstd silences all the static analyzer false positives. Upstream zstd uses clang scan-build for its static analysis. We find that supporting multiple static analysis tools multiplies the burden of silencing false positives, without providing enough marginal value over running a single static analysis tool.v4 -> v5:
* Rebase onto v5.10-rc2
* (6/9) Merge with other F2FS changes (no functional change in patch).v5 -> v6:
* Rebase onto v5.10-rc6.
* Switch to using a kernel style wrapper API as suggested by Cristoph.v6 -> v7:
* Expose the upstream library header asinclude/linux/zstd_lib.h. Instead of creating new structs mirroring the upstream zstd structs use upstream's structs directly with a typedef to get a kernel style name. This removes the memcpy cruft.
* (1/3) UndoZSTD_WINDOWLOG_MAXandhandle_zstd_errorchanges.
* (3/3) Exposezstd_errors.hasinclude/linux/zstd_errors.hbecause it is needed by the kernel wrapper API.v7 -> v8:
* (1/3) Fix typo inEXPORT_SYMBOL().
* (1/3) Fix typo inzstd.hcomments.
* (3/3) Update to latest zstd release: 1.4.6 -> 1.4.10 This includes ~1KB of stack space reductions.v8 -> v9:
* (1/3) Rebase onto v5.12-rc5
* (1/3) Addzstd_min_clevel()&zstd_max_clevel()and use in f2fs. Thanks to Oleksandr Natalenko for spotting it!
* (1/3) Movelib/decompress_unzstd.cusage ofZSTD_getErrorCode()tozstd_get_error_code().
* (1/3) Update modified zstd headers to yearless copyright.
* (2/3) Add copyright/license header todecompress_sources.hfor consistency.
* (3/3) Update to yearless copyright for all zstd files. Thanks to Mike Dolan for spotting it!Nick Terrell (3):
lib: zstd: Add kernel-specific API
lib: zstd: Adddecompress_sources.hfordecompress_unzstd
lib: zstd: Upgrade to latest upstream zstd version 1.4.10crypto/zstd.c | 28 +- fs/btrfs/zstd.c | 68 +- fs/f2fs/compress.c | 56 +- fs/f2fs/super.c | 2 +- fs/pstore/platform.c | 2 +- fs/squashfs/zstd_wrapper.c | 16 +- include/linux/zstd.h | 1252 +--- include/linux/zstd_errors.h | 77 + include/linux/zstd_lib.h | 2432 ++++++++ lib/decompress_unzstd.c | 48 +- lib/zstd/Makefile | 44 +- lib/zstd/bitstream.h | 380 -- lib/zstd/common/bitstream.h | 437 ++ lib/zstd/common/compiler.h | 151 + lib/zstd/common/cpu.h | 194 + lib/zstd/common/debug.c | 24 + lib/zstd/common/debug.h | 101 + lib/zstd/common/entropy_common.c | 357 ++ lib/zstd/common/error_private.c | 56 + lib/zstd/common/error_private.h | 66 + lib/zstd/common/fse.h | 710 +++ lib/zstd/common/fse_decompress.c | 390 ++ lib/zstd/common/huf.h | 356 ++ lib/zstd/common/mem.h | 259 + lib/zstd/common/zstd_common.c | 83 + lib/zstd/common/zstd_deps.h | 125 + lib/zstd/common/zstd_internal.h | 450 ++ lib/zstd/compress.c | 3485 ----------- lib/zstd/compress/fse_compress.c | 625 ++ lib/zstd/compress/hist.c | 165 + lib/zstd/compress/hist.h | 75 + lib/zstd/compress/huf_compress.c | 902 +++ lib/zstd/compress/zstd_compress.c | 5105 +++++++++++++++++ lib/zstd/compress/zstd_compress_internal.h | 1188 ++++ lib/zstd/compress/zstd_compress_literals.c | 158 + lib/zstd/compress/zstd_compress_literals.h | 29 + lib/zstd/compress/zstd_compress_sequences.c | 439 ++ lib/zstd/compress/zstd_compress_sequences.h | 54 + lib/zstd/compress/zstd_compress_superblock.c | 850 +++ lib/zstd/compress/zstd_compress_superblock.h | 32 + lib/zstd/compress/zstd_cwksp.h | 482 ++ lib/zstd/compress/zstd_double_fast.c | 521 ++ lib/zstd/compress/zstd_double_fast.h | 32 + lib/zstd/compress/zstd_fast.c | 496 ++ lib/zstd/compress/zstd_fast.h | 31 + lib/zstd/compress/zstd_lazy.c | 1412 +++++ lib/zstd/compress/zstd_lazy.h | 81 + lib/zstd/compress/zstd_ldm.c | 686 +++ lib/zstd/compress/zstd_ldm.h | 110 + lib/zstd/compress/zstd_ldm_geartab.h | 103 + lib/zstd/compress/zstd_opt.c | 1345 +++++ lib/zstd/compress/zstd_opt.h | 50 + lib/zstd/decompress.c | 2531 -------- lib/zstd/decompress/huf_decompress.c | 1206 ++++ lib/zstd/decompress/zstd_ddict.c | 241 + lib/zstd/decompress/zstd_ddict.h | 44 + lib/zstd/decompress/zstd_decompress.c | 2075 +++++++ lib/zstd/decompress/zstd_decompress_block.c | 1540 +++++ lib/zstd/decompress/zstd_decompress_block.h | 62 + .../decompress/zstd_decompress_internal.h | 202 + lib/zstd/decompress_sources.h | 28 + lib/zstd/entropy_common.c | 243 - lib/zstd/error_private.h | 53 - lib/zstd/fse.h | 575 -- lib/zstd/fse_compress.c | 795 --- lib/zstd/fse_decompress.c | 325 -- lib/zstd/huf.h | 212 - lib/zstd/huf_compress.c | 773 --- lib/zstd/huf_decompress.c | 960 ---- lib/zstd/mem.h | 151 - lib/zstd/zstd_common.c | 75 - lib/zstd/zstd_compress_module.c | 124 + lib/zstd/zstd_decompress_module.c | 105 + lib/zstd/zstd_internal.h | 273 - lib/zstd/zstd_opt.h | 1014 ---- 75 files changed, 27287 insertions(+), 12940 deletions(-) create mode 100644 include/linux/zstd_errors.h create mode 100644 include/linux/zstd_lib.h delete mode 100644 lib/zstd/bitstream.h create mode 100644 lib/zstd/common/bitstream.h create mode 100644 lib/zstd/common/compiler.h create mode 100644 lib/zstd/common/cpu.h create mode 100644 lib/zstd/common/debug.c create mode 100644 lib/zstd/common/debug.h create mode 100644 lib/zstd/common/entropy_common.c create mode 100644 lib/zstd/common/error_private.c create mode 100644 lib/zstd/common/error_private.h create mode 100644 lib/zstd/common/fse.h create mode 100644 lib/zstd/common/fse_decompress.c create mode 100644 lib/zstd/common/huf.h create mode 100644 lib/zstd/common/mem.h create mode 100644 lib/zstd/common/zstd_common.c create mode 100644 lib/zstd/common/zstd_deps.h create mode 100644 lib/zstd/common/zstd_internal.h delete mode 100644 lib/zstd/compress.c create mode 100644 lib/zstd/compress/fse_compress.c create mode 100644 lib/zstd/compress/hist.c create mode 100644 lib/zstd/compress/hist.h create mode 100644 lib/zstd/compress/huf_compress.c create mode 100644 lib/zstd/compress/zstd_compress.c create mode 100644 lib/zstd/compress/zstd_compress_internal.h create mode 100644 lib/zstd/compress/zstd_compress_literals.c create mode 100644 lib/zstd/compress/zstd_compress_literals.h create mode 100644 lib/zstd/compress/zstd_compress_sequences.c create mode 100644 lib/zstd/compress/zstd_compress_sequences.h create mode 100644 lib/zstd/compress/zstd_compress_superblock.c create mode 100644 lib/zstd/compress/zstd_compress_superblock.h create mode 100644 lib/zstd/compress/zstd_cwksp.h create mode 100644 lib/zstd/compress/zstd_double_fast.c create mode 100644 lib/zstd/compress/zstd_double_fast.h create mode 100644 lib/zstd/compress/zstd_fast.c create mode 100644 lib/zstd/compress/zstd_fast.h create mode 100644 lib/zstd/compress/zstd_lazy.c create mode 100644 lib/zstd/compress/zstd_lazy.h create mode 100644 lib/zstd/compress/zstd_ldm.c create mode 100644 lib/zstd/compress/zstd_ldm.h create mode 100644 lib/zstd/compress/zstd_ldm_geartab.h create mode 100644 lib/zstd/compress/zstd_opt.c create mode 100644 lib/zstd/compress/zstd_opt.h delete mode 100644 lib/zstd/decompress.c create mode 100644 lib/zstd/decompress/huf_decompress.c create mode 100644 lib/zstd/decompress/zstd_ddict.c create mode 100644 lib/zstd/decompress/zstd_ddict.h create mode 100644 lib/zstd/decompress/zstd_decompress.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.c create mode 100644 lib/zstd/decompress/zstd_decompress_block.h create mode 100644 lib/zstd/decompress/zstd_decompress_internal.h create mode 100644 lib/zstd/decompress_sources.h delete mode 100644 lib/zstd/entropy_common.c delete mode 100644 lib/zstd/error_private.h delete mode 100644 lib/zstd/fse.h delete mode 100644 lib/zstd/fse_compress.c delete mode 100644 lib/zstd/fse_decompress.c delete mode 100644 lib/zstd/huf.h delete mode 100644 lib/zstd/huf_compress.c delete mode 100644 lib/zstd/huf_decompress.c delete mode 100644 lib/zstd/mem.h delete mode 100644 lib/zstd/zstd_common.c create mode 100644 lib/zstd/zstd_compress_module.c create mode 100644 lib/zstd/zstd_decompress_module.c delete mode 100644 lib/zstd/zstd_internal.h delete mode 100644 lib/zstd/zstd_opt.h--
2.31.0
Quoted 9 lines · Nick Terrell
Hi all,
I would really like to make some progress on this and get it merged. This patchset offsers:
* 15-30% better decompression speed
* 3 years of zstd bug fixes and code improvements
* Allows us to import zstd directly from upstream so we don't fall 3 years out of date again
Quoted 3 lines
Thanks,
Nick
I think it would help get it merged if someone actually volunteered to maintain it. As-is there is no entry in MAINTAINERS for this code.
- Eric
Quoted 11 lines · Eric Biggers
Quoted 9 lines · Nick Terrell
Hi all,
I would really like to make some progress on this and get it merged. This patchset offsers:
* 15-30% better decompression speed
* 3 years of zstd bug fixes and code improvements
* Allows us to import zstd directly from upstream so we don't fall 3 years out of date again
Quoted 6 lines
Quoted 3 lines
Thanks,
NickI think it would help get it merged if someone actually volunteered to maintain it. As-is there is no entry in
MAINTAINERSfor this code.
I was discussing with Chris Mason about volunteering to maintain the code myself.
We wanted to wait until this series got merged before going that route, because there
was already a lot of comments about it, and I didn't want to appear to be trying to bypass
any review or criticisms. But, please let me know what you think.
Best,
Nick
Quoted 1 line
- Eric
Quoted 19 lines · Nick Terrell
Quoted 11 lines · Eric Biggers
Quoted 9 lines · Nick Terrell
Hi all,
I would really like to make some progress on this and get it merged. This patchset offsers:
* 15-30% better decompression speed
* 3 years of zstd bug fixes and code improvements
* Allows us to import zstd directly from upstream so we don't fall 3 years out of date againQuoted 6 lines
Quoted 3 lines
Thanks,
NickI think it would help get it merged if someone actually volunteered to maintain it. As-is there is no entry in
MAINTAINERSfor this code.
Quoted 8 lines
I was discussing with Chris Mason about volunteering to maintain the code myself.
We wanted to wait until this series got merged before going that route, because there
was already a lot of comments about it, and I didn't want to appear to be trying to bypass
any review or criticisms. But, please let me know what you think.
I expect that most people would like to see a commitment to maintain this code before merging. The usual way to do that is to add a MAINTAINERS entry.
Otherwise it is 27000 lines of code dumped on other people to maintain.
- Eric
_______________________________________________
Linux-f2fs-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
Quoted 30 lines · Eric Biggers
Quoted 19 lines · Nick Terrell
Quoted 11 lines · Eric Biggers
Quoted 9 lines · Nick Terrell
Hi all,
I would really like to make some progress on this and get it merged. This patchset offsers:
* 15-30% better decompression speed
* 3 years of zstd bug fixes and code improvements
* Allows us to import zstd directly from upstream so we don't fall 3 years out of date againQuoted 6 lines
Quoted 3 lines
Thanks,
NickI think it would help get it merged if someone actually volunteered to maintain it. As-is there is no entry in
MAINTAINERSfor this code.Quoted 8 lines
I was discussing with Chris Mason about volunteering to maintain the code myself.
We wanted to wait until this series got merged before going that route, because there
was already a lot of comments about it, and I didn't want to appear to be trying to bypass
any review or criticisms. But, please let me know what you think.
Quoted 4 lines
I expect that most people would like to see a commitment to maintain this code before merging. The usual way to do that is to add a
MAINTAINERSentry.Otherwise it is 27000 lines of code dumped on other people to maintain.
I will add a 4th patch in the series to update the MAINTAINERS.
Quoted 1 line
- Eric