> On Oct 6, 2021, at 2:39 PM, Sedat Dilek <sedat.dilek@xxxxxxxxx> wrote: > > On Wed, Oct 6, 2021 at 9:21 PM Nick Terrell <nickrterrell@xxxxxxxxx> wrote: >> >> From: Nick Terrell <terrelln@xxxxxx> >> >> The following changes since commit 9e1ff307c779ce1f0f810c7ecce3d95bbae40896: >> >> Linux 5.15-rc4 (2021-10-03 14:08:47 -0700) >> >> are available in the Git repository at: >> >> https://github.com/terrelln/linux.git zstd-1.4.10 >> >> for you to fetch changes up to a0ccd980d5048053578f3b524e3cd3f5d980a9c5: >> >> MAINTAINERS: Add maintainer entry for zstd (2021-10-04 20:04:32 -0700) >> >> I would like to merge this pull request into linux-next to bake, and then submit >> the PR to Linux in the 5.16 merge window. If you have been a part of the >> discussion, are a maintainer of a caller of zstd, tested this code, or otherwise >> been involved, thank you! And could you please respond below with an appropiate >> tag, so I can collect support for the PR >> >> Best, >> Nick Terrell >> >> ---------------------------------------------------------------- >> Update to zstd-1.4.10 >> >> - The first commit 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.10 maintains the same >> API and preserves the semantics, so that none of the callers need to be >> updated. All callers are updated in the commit, because there are zero >> functional changes. >> - The second commit adds an indirection for `lib/decompress_unzstd.c` so it >> doesn't depend on the layout of `lib/zstd/` to include every source file. >> This allows the next patch to be automatically generated. >> - The third commit is automatically generated, and imports the zstd-1.4.10 source >> code. This commit is completely generated by automation. >> - The fourth commit adds me (terrelln@xxxxxx) as the maintainer of `lib/zstd`. >> >> The discussion around this patchset has been pretty long, so I've included a >> FAQ-style summary of the history of the patchset, and why we are taking this >> approach. >> >> Why do we need to update? >> ------------------------- >> >> The zstd version in the kernel is based off of zstd-1.3.1, which is was released >> August 20, 2017. Since then zstd has seen many bug fixes and performance >> improvements. And, importantly, upstream zstd is continuously fuzzed by OSS-Fuzz, >> and bug fixes aren't backported to older versions. So the only way to sanely get >> these fixes is to keep up to date with upstream zstd. There are no known security >> issues that affect the kernel, but we need to be able to update in case there >> are. And while there are no known security issues, there are relevant 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. >> >> Additionally the performance improvements for kernel use cases are significant. >> Measured for x86_64 on my Intel i9-9900k @ 3.6 GHz: >> >> - 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 >> >> On top of this, there are significant performance improvements coming down the >> line in the next zstd release, and the new automated update patch generation >> will allow us to pull them easily. >> >> How is the update patch generated? >> ---------------------------------- >> >> The first two patches are preparation for updating the zstd version. Then the >> 3rd patch in the series imports upstream zstd into the kernel. This patch is >> automatically generated from upstream. A script makes the necessary changes and >> imports it into the kernel. The changes are: >> >> - Replace all libc dependencies with kernel replacements and rewrite includes. >> - Remove unncessary portability macros like: #if defined(_MSC_VER). >> - 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. >> >> The automated process makes it easy to keep the kernel version of zstd up to >> date. The current zstd in the kernel shares the guts of the code, but has a lot >> of API and minor changes to work in the kernel. This is because at the time >> upstream zstd was not ready to be used in the kernel envrionment as-is. But, >> since then upstream zstd has evolved to support being used in the kernel as-is. >> >> Why are we updating in one big patch? >> ------------------------------------- >> >> The 3rd patch in the series is very large. This is because it is restructuring >> the code, so it both deletes the existing zstd, and re-adds the new structure. >> Future updates will be directly proportional to the changes in upstream zstd >> since the last import. They will admittidly be large, as zstd is an actively >> developed project, and has hundreds of commits between every release. However, >> there is no other great alternative. >> >> One option ruled out is to replay every upstream zstd commit. This is not feasible >> for several reasons: >> - There are over 3500 upstream commits since the zstd version in the kernel. >> - The automation to automatically generate the kernel update was only added recently, >> so older commits cannot easily be imported. >> - Not every upstream zstd commit builds. >> - Only zstd releases are "supported", and individual commits may have bugs that were >> fixed before a release. >> >> Another option to reduce the patch size would be to first reorganize to the new >> file structure, and then apply the patch. However, the current kernel zstd is formatted >> with clang-format to be more "kernel-like". But, the new method imports zstd as-is, >> without additional formatting, to allow for closer correlation with upstream, and >> easier debugging. So the patch wouldn't be any smaller. >> >> It also doesn't make sense to import upstream zstd commit by commit going >> forward. Upstream zstd doesn't support production use cases running of the >> development branch. We have a lot of post-commit fuzzing that catches many bugs, >> so indiviudal commits may be buggy, but fixed before a release. So going forward, >> I intend to import every (important) zstd release into the Kernel. >> >> So, while it isn't ideal, updating in one big patch is the only patch I see forward. >> >> Who is responsible for this code? >> --------------------------------- >> >> I am. This patchset adds me as the maintainer for zstd. Previously, there was no tree >> for zstd patches. Because of that, there were several patches that either got ignored, >> or took a long time to merge, since it wasn't clear which tree should pick them up. >> I'm officially stepping up as maintainer, and setting up my tree as the path through >> which zstd patches get merged. I'll make sure that patches to the kernel zstd get >> ported upstream, so they aren't erased when the next version update happens. >> >> How is this code tested? >> ------------------------ >> >> I tested every caller of zstd on x86_64 (BtrFS, ZRAM, SquashFS, F2FS, Kernel, >> InitRAMFS). I also tested Kernel & InitRAMFS on i386 and aarch64. I checked both >> performance and correctness. >> >> Also, thanks to many people in the community who have tested these patches locally. >> If you have tested the patches, please reply with a Tested-By so I can collect them >> for the PR I will send to Linus. >> >> Lastly, this code will bake in linux-next before being merged into v5.16. >> >> Why update to zstd-1.4.10 when zstd-1.5.0 has been released? >> ------------------------------------------------------------ >> >> This patchset has been outstanding since 2020, and zstd-1.4.10 was the latest >> release when it was created. Since the update patch is automatically generated >> from upstream, I could generate it from zstd-1.5.0. However, there were some >> large stack usage regressions in zstd-1.5.0, and are only fixed in the latest >> development branch. And the latest development branch contains some new code that >> needs to bake in the fuzzer before I would feel comfortable releasing to the >> kernel. >> >> Once this patchset has been merged, and we've released zstd-1.5.1, we can update >> the kernel to zstd-1.5.1, and exercise the update process. >> >> You may notice that zstd-1.4.10 doesn't exist upstream. This release is an >> artifical release based off of zstd-1.4.9, with some fixes for the kernel >> backported from the development branch. I will tag the zstd-1.4.10 release after >> this patchset is merged, so the Linux Kernel is running a known version of zstd >> that can be debugged upstream. >> >> Why was a wrapper API added? >> ---------------------------- >> >> The first versions of this patchset migrated the kernel to the upstream zstd >> API. It first added a shim API that supported the new upstream API with the old >> code, then updated callers to use the new shim API, then transitioned to the >> new code and deleted the shim API. However, Cristoph Hellwig suggested that we >> transition to a kernel style API, and hide zstd's upstream API behind that. >> This is because zstd's upstream API is supports many other use cases, and does >> not follow the kernel style guide, while the kernel API is focused on the >> kernel's use cases, and follows the kernel style guide. >> >> Changelog >> --------- >> >> 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! >> >> v9 -> v10: >> * Add a 4th patch in the series which adds an entry for zstd to MAINTAINERS. >> >> v10 -> v11: >> * Rebase cleanly onto v5.12-rc8 >> * (3/4) Replace invalid kernel style comments in zstd with regular comments. >> Thanks to Randy Dunlap for the suggestion. >> >> v11 -> v12: >> * Re-write the cover letter & send as a PR only. >> * Rebase cleanly onto 5.15-rc4. >> * (3/4) Clean up licensing to reflect that we're GPL-2.0+ OR BSD-3-Clause. >> * (3/4) Reduce compression stack usage by 80 bytes. >> * (3/4) Make upstream zstd `-Wfall-through` compliant and use the FALLTHROUGH >> macro in the Linux Kernel. >> >> Signed-off-by: Nick Terrell <terrelln@xxxxxx> >> Tested By: Paul Jones <paul@xxxxxxxxxxxxxxx> >> Tested-by: Oleksandr Natalenko <oleksandr@xxxxxxxxxxxxxx> >> > > Hi Nick, > > can you please CC me on further patchsets? Yeah of course! Your name must’ve accidentally been removed from my CC list. > Thanks for taking responsibility as linux-zstd maintainer. > > I am currently testing this on top of Linux v5.15-rc4 building with > LLVM/Clang v13. > > Do I also need ZSTD version 1.4.10 in user-space? > Debian/unstable AMD64 ships here version 1.4.8. Nope, you can use any zstd version >= 1.0.0 in userspace. It is forward and backward compatible. Best, Nick > Thanks. > > Regards, > - Sedat - > >> ---------------------------------------------------------------- >> Nick Terrell (4): >> 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 >> MAINTAINERS: Add maintainer entry for zstd >> >> MAINTAINERS | 12 + >> 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 | 46 +- >> lib/zstd/bitstream.h | 380 -- >> lib/zstd/common/bitstream.h | 437 ++ >> lib/zstd/common/compiler.h | 170 + >> 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 | 905 +++++ >> lib/zstd/compress/zstd_compress.c | 5109 ++++++++++++++++++++++++ >> 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 | 519 +++ >> 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 | 2082 ++++++++++ >> lib/zstd/decompress/zstd_decompress_block.c | 1540 +++++++ >> lib/zstd/decompress/zstd_decompress_block.h | 62 + >> lib/zstd/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 | 160 + >> lib/zstd/zstd_decompress_module.c | 105 + >> lib/zstd/zstd_internal.h | 273 -- >> lib/zstd/zstd_opt.h | 1014 ----- >> 76 files changed, 27367 insertions(+), 12941 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
