summaryrefslogtreecommitdiffstats
path: root/lib/zstd
AgeCommit message (Collapse)AuthorFilesLines
2022-10-03zstd: Fixing mixed module-builtin objectsAlexey Kardashevskiy3-10/+21
With CONFIG_ZSTD_COMPRESS=m and CONFIG_ZSTD_DECOMPRESS=y we end up in a situation when files from lib/zstd/common/ are compiled once to be linked later for ZSTD_DECOMPRESS (build-in) and ZSTD_COMPRESS (module) even though CFLAGS are different for builtins and modules. So far somehow this was not a problem but enabling LLVM LTO exposes the problem as: ld.lld: error: linking module flags 'Code Model': IDs have conflicting values in 'lib/built-in.a(zstd_common.o at 5868)' and 'ld-temp.o' This particular conflict is caused by KBUILD_CFLAGS=-mcmodel=medium vs. KBUILD_CFLAGS_MODULE=-mcmodel=large , modules use the large model on POWERPC as explained at https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/powerpc/Makefile?h=v5.18-rc4#n127 but the current use of common files is wrong anyway. This works around the issue by introducing a zstd_common module with shared code. Signed-off-by: Alexey Kardashevskiy <aik@ozlabs.ru> Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
2021-11-18lib: zstd: Don't add -O3 to cflagsNick Terrell1-2/+0
After the update to zstd-1.4.10 passing -O3 is no longer necessary to get good performance from zstd. Using the default optimization level -O2 is sufficient to get good performance. I've measured no significant change to compression speed, and a ~1% decompression speed loss, which is acceptable. This fixes the reported parisc -Wframe-larger-than=1536 errors [0]. The gcc-8-hppa-linux-gnu compiler performed very poorly with -O3, generating stacks that are ~3KB. With -O2 these same functions generate stacks in the < 100B, completely fixing the problem. Function size deltas are listed below: ZSTD_compressBlock_fast_extDict_generic: 3800 -> 68 ZSTD_compressBlock_fast: 2216 -> 40 ZSTD_compressBlock_fast_dictMatchState: 1848 -> 64 ZSTD_compressBlock_doubleFast_extDict_generic: 3744 -> 76 ZSTD_fillDoubleHashTable: 3252 -> 0 ZSTD_compressBlock_doubleFast: 5856 -> 36 ZSTD_compressBlock_doubleFast_dictMatchState: 5380 -> 84 ZSTD_copmressBlock_lazy2: 2420 -> 72 Additionally, this improves the reported code bloat [1]. With gcc-11 bloat-o-meter shows an 80KB code size improvement: ``` > ../scripts/bloat-o-meter vmlinux.old vmlinux add/remove: 31/8 grow/shrink: 24/155 up/down: 25734/-107924 (-82190) Total: Before=6418562, After=6336372, chg -1.28% ``` Compared to before the zstd-1.4.10 update we see a total code size regression of 105KB, down from 374KB at v5.16-rc1: ``` > ../scripts/bloat-o-meter vmlinux.old vmlinux add/remove: 292/62 grow/shrink: 56/88 up/down: 235009/-127487 (107522) Total: Before=6228850, After=6336372, chg +1.73% ``` [0] https://lkml.org/lkml/2021/11/15/710 [1] https://lkml.org/lkml/2021/11/14/189 Link: https://lore.kernel.org/r/20211117014949.1169186-4-nickrterrell@gmail.com/ Link: https://lore.kernel.org/r/20211117201459.1194876-4-nickrterrell@gmail.com/ Reported-by: Geert Uytterhoeven <geert@linux-m68k.org> Tested-by: Geert Uytterhoeven <geert@linux-m68k.org> Reviewed-by: Geert Uytterhoeven <geert@linux-m68k.org> Signed-off-by: Nick Terrell <terrelln@fb.com>
2021-11-18lib: zstd: Don't inline functions in zstd_opt.cNick Terrell2-0/+19
`zstd_opt.c` contains the match finder for the highest compression levels. These levels are already very slow, and are unlikely to be used in the kernel. If they are used, they shouldn't be used in latency sensitive workloads, so slowing them down shouldn't be a big deal. This saves 188 KB of the 288 KB regression reported by Geert Uytterhoeven [0]. I've also opened an issue upstream [1] so that we can properly tackle the code size issue in `zstd_opt.c` for all users, and can hopefully remove this hack in the next zstd version we import. Bloat-o-meter output on x86-64: ``` > ../scripts/bloat-o-meter vmlinux.old vmlinux add/remove: 6/5 grow/shrink: 1/9 up/down: 16673/-209939 (-193266) Function old new delta ZSTD_compressBlock_opt_generic.constprop - 7559 +7559 ZSTD_insertBtAndGetAllMatches - 6304 +6304 ZSTD_insertBt1 - 1731 +1731 ZSTD_storeSeq - 693 +693 ZSTD_BtGetAllMatches - 255 +255 ZSTD_updateRep - 128 +128 ZSTD_updateTree 96 99 +3 ZSTD_insertAndFindFirstIndexHash3 81 - -81 ZSTD_setBasePrices.constprop 98 - -98 ZSTD_litLengthPrice.constprop 138 - -138 ZSTD_count 362 181 -181 ZSTD_count_2segments 1407 938 -469 ZSTD_insertBt1.constprop 2689 - -2689 ZSTD_compressBlock_btultra2 19990 423 -19567 ZSTD_compressBlock_btultra 19633 15 -19618 ZSTD_initStats_ultra 19825 - -19825 ZSTD_compressBlock_btopt 20374 12 -20362 ZSTD_compressBlock_btopt_extDict 29984 12 -29972 ZSTD_compressBlock_btultra_extDict 30718 15 -30703 ZSTD_compressBlock_btopt_dictMatchState 32689 12 -32677 ZSTD_compressBlock_btultra_dictMatchState 33574 15 -33559 Total: Before=6611828, After=6418562, chg -2.92% ``` [0] https://lkml.org/lkml/2021/11/14/189 [1] https://github.com/facebook/zstd/issues/2862 Link: https://lore.kernel.org/r/20211117014949.1169186-3-nickrterrell@gmail.com/ Link: https://lore.kernel.org/r/20211117201459.1194876-3-nickrterrell@gmail.com/ Reported-by: Geert Uytterhoeven <geert@linux-m68k.org> Tested-by: Geert Uytterhoeven <geert@linux-m68k.org> Reviewed-by: Geert Uytterhoeven <geert@linux-m68k.org> Signed-off-by: Nick Terrell <terrelln@fb.com>
2021-11-18lib: zstd: Fix unused variable warningNick Terrell1-0/+2
The variable `litLengthSum` is only used by an `assert()`, so when asserts are disabled the compiler doesn't see any usage and warns. This issue is already fixed upstream by PR #2838 [0]. It was reported by the Kernel test robot in [1]. Another approach would be to change zstd's disabled `assert()` definition to use the argument in a disabled branch, instead of ignoring the argument. I've avoided this approach because there are some small changes necessary to get zstd to build, and I would want to thoroughly re-test for performance, since that is slightly changing the code in every function in zstd. It seems like a trivial change, but some functions are pretty sensitive to small changes. However, I think it is a valid approach that I would like to see upstream take, so I've opened Issue #2868 to attempt this upstream. Lastly, I've chosen not to use __maybe_unused because all code in lib/zstd/ must eventually be upstreamed. Upstream zstd can't use __maybe_unused because it isn't portable across all compilers. [0] https://github.com/facebook/zstd/pull/2838 [1] https://lore.kernel.org/linux-mm/202111120312.833wII4i-lkp@intel.com/T/ [2] https://github.com/facebook/zstd/issues/2868 Link: https://lore.kernel.org/r/20211117014949.1169186-2-nickrterrell@gmail.com/ Link: https://lore.kernel.org/r/20211117201459.1194876-2-nickrterrell@gmail.com/ Reported-by: kernel test robot <lkp@intel.com> Signed-off-by: Nick Terrell <terrelln@fb.com>
2021-11-08lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logicalNathan Chancellor1-1/+1
A new warning in clang warns that there is an instance where boolean expressions are being used with bitwise operators instead of logical ones: lib/zstd/decompress/huf_decompress.c:890:25: warning: use of bitwise '&' with boolean operands [-Wbitwise-instead-of-logical] (BIT_reloadDStreamFast(&bitD1) == BIT_DStream_unfinished) ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ zstd does this frequently to help with performance, as logical operators have branches whereas bitwise ones do not. To fix this warning in other cases, the expressions were placed on separate lines with the '&=' operator; however, this particular instance was moved away from that so that it could be surrounded by LIKELY, which is a macro for __builtin_expect(), to help with a performance regression, according to upstream zstd pull #1973. Aside from switching to logical operators, which is likely undesirable in this instance, or disabling the warning outright, the solution is casting one of the expressions to an integer type to make it clear to clang that the author knows what they are doing. Add a cast to U32 to silence the warning. The first U32 cast is to silence an instance of -Wshorten-64-to-32 because __builtin_expect() returns long so it cannot be moved. Link: https://github.com/ClangBuiltLinux/linux/issues/1486 Link: https://github.com/facebook/zstd/pull/1973 Reported-by: Nick Desaulniers <ndesaulniers@google.com> Signed-off-by: Nathan Chancellor <nathan@kernel.org> Signed-off-by: Nick Terrell <terrelln@fb.com>
2021-11-08lib: zstd: Upgrade to latest upstream zstd version 1.4.10Nick Terrell65-11944/+24453
Upgrade to the latest upstream zstd version 1.4.10. This patch is 100% generated from upstream zstd commit 20821a46f412 [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, replace `/**` comments with `/*` comments, 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 20821a46f412 [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/20821a46f4122f9abd7c7b245d28162dde8129c9 [1] https://github.com/terrelln/linux/commit/e0fa481d0e3df26918da0a13749740a1f6777574 Signed-off-by: Nick Terrell <terrelln@fb.com> Tested By: Paul Jones <paul@pauljones.id.au> Tested-by: Oleksandr Natalenko <oleksandr@natalenko.name> Tested-by: Sedat Dilek <sedat.dilek@gmail.com> # LLVM/Clang v13.0.0 on x86-64 Tested-by: Jean-Denis Girard <jd.girard@sysnux.pf>
2021-11-08lib: zstd: Add decompress_sources.h for decompress_unzstdNick Terrell1-0/+23
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. Signed-off-by: Nick Terrell <terrelln@fb.com> Tested By: Paul Jones <paul@pauljones.id.au> Tested-by: Oleksandr Natalenko <oleksandr@natalenko.name> Tested-by: Sedat Dilek <sedat.dilek@gmail.com> # LLVM/Clang v13.0.0 on x86-64 Tested-by: Jean-Denis Girard <jd.girard@sysnux.pf>
2021-11-08lib: zstd: Add kernel-specific APINick Terrell2-73/+162
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. Signed-off-by: Nick Terrell <terrelln@fb.com> Tested By: Paul Jones <paul@pauljones.id.au> Tested-by: Oleksandr Natalenko <oleksandr@natalenko.name> Tested-by: Sedat Dilek <sedat.dilek@gmail.com> # LLVM/Clang v13.0.0 on x86-64 Tested-by: Jean-Denis Girard <jd.girard@sysnux.pf>
2021-07-01lib/decompressors: fix spelling mistakesZhen Lei1-1/+1
Fix some spelling mistakes in comments: sentinal ==> sentinel compresed ==> compressed dependeny ==> dependency immediatelly ==> immediately dervied ==> derived splitted ==> split nore ==> not independed ==> independent asumed ==> assumed Link: https://lkml.kernel.org/r/20210604085656.12257-1-thunder.leizhen@huawei.com Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com> Cc: Jiri Kosina <jkosina@suse.cz> Cc: Thomas Bogendoerfer <tsbogend@alpha.franken.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-11-19lib: Fix fall-through warnings for ClangGustavo A. R. Silva2-0/+2
In preparation to enable -Wimplicit-fallthrough for Clang, fix multiple warnings by explicitly adding multiple break statements instead of letting the code fall through to the next case, and by replacing a number of /* fall through */ comments with the new pseudo-keyword macro fallthrough. Notice that Clang doesn't recognize /* Fall through */ comments as implicit fall-through markings. Link: https://github.com/KSPP/linux/issues/115 Signed-off-by: Gustavo A. R. Silva <gustavoars@kernel.org>
2020-11-18Revert "lib: Revert use of fallthrough pseudo-keyword in lib/"Nick Desaulniers4-14/+14
This reverts commit 6a9dc5fd6170 ("lib: Revert use of fallthrough pseudo-keyword in lib/") Now that we can build arch/powerpc/boot/ free of -Wimplicit-fallthrough, re-enable these fixes for lib/. Signed-off-by: Nick Desaulniers <ndesaulniers@google.com> Tested-by: Nathan Chancellor <natechancellor@gmail.com> Reviewed-by: Nathan Chancellor <natechancellor@gmail.com> Reviewed-by: Gustavo A. R. Silva <gustavoars@kernel.org> Reviewed-by: Miguel Ojeda <ojeda@kernel.org> Link: https://github.com/ClangBuiltLinux/linux/issues/236 Signed-off-by: Gustavo A. R. Silva <gustavoars@kernel.org>
2020-08-24lib: Revert use of fallthrough pseudo-keyword in lib/Gustavo A. R. Silva4-14/+14
The following build error for powerpc64 was reported by Nathan Chancellor: "$ scripts/config --file arch/powerpc/configs/powernv_defconfig -e KERNEL_XZ $ make -skj"$(nproc)" ARCH=powerpc CROSS_COMPILE=powerpc64le-linux- distclean powernv_defconfig zImage ... In file included from arch/powerpc/boot/../../../lib/decompress_unxz.c:234, from arch/powerpc/boot/decompress.c:38: arch/powerpc/boot/../../../lib/xz/xz_dec_stream.c: In function 'dec_main': arch/powerpc/boot/../../../lib/xz/xz_dec_stream.c:586:4: error: 'fallthrough' undeclared (first use in this function) 586 | fallthrough; | ^~~~~~~~~~~ This will end up affecting distribution configurations such as Debian and OpenSUSE according to my testing. I am not sure what the solution is, the PowerPC wrapper does not set -D__KERNEL__ so I am not sure that compiler_attributes.h can be safely included." In order to avoid these sort of problems, it seems that the best solution is to use /* fall through */ comments instead of the fallthrough pseudo-keyword macro in lib/, for now. Reported-by: Nathan Chancellor <natechancellor@gmail.com> Fixes: df561f6688fe ("treewide: Use fallthrough pseudo-keyword") Signed-off-by: Gustavo A. R. Silva <gustavoars@kernel.org> Reviewed-and-tested-by: Nathan Chancellor <natechancellor@gmail.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-08-23treewide: Use fallthrough pseudo-keywordGustavo A. R. Silva4-14/+14
Replace the existing /* fall through */ comments and its variants with the new pseudo-keyword macro fallthrough[1]. Also, remove unnecessary fall-through markings when it is the case. [1] https://www.kernel.org/doc/html/v5.7/process/deprecated.html?highlight=fallthrough#implicit-switch-case-fall-through Signed-off-by: Gustavo A. R. Silva <gustavoars@kernel.org>
2020-07-31lib: Prepare zstd for preboot environment, improve performanceNick Terrell2-10/+13
These changes are necessary to get the build to work in the preboot environment, and to get reasonable performance: - Remove a double definition of the CHECK_F macro when the zstd library is amalgamated. - Switch ZSTD_copy8() to __builtin_memcpy(), because in the preboot environment on x86 gcc can't inline `memcpy()` otherwise. - Limit the gcc hack in ZSTD_wildcopy() to the broken gcc version. See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388. ZSTD_copy8() and ZSTD_wildcopy() are in the core of the zstd hot loop. So outlining these calls to memcpy(), and having an extra branch are very detrimental to performance. Signed-off-by: Nick Terrell <terrelln@fb.com> Signed-off-by: Ingo Molnar <mingo@kernel.org> Tested-by: Sedat Dilek <sedat.dilek@gmail.com> Reviewed-by: Kees Cook <keescook@chromium.org> Link: https://lore.kernel.org/r/20200730190841.2071656-2-nickrterrell@gmail.com
2019-09-15lib/zstd/mem.h: replace __inline by inlineRasmus Villemoes1-1/+1
Currently, compiler_types.h #defines __inline as inline (and further #defines inline to automatically attach some attributes), so this does not change functionality. It serves as preparation for removing the #define of __inline. While at it, also remove the __attribute__((unused)) - it's already included in the definition of the inline macro, and "open-coded" __attribute__(()) should be avoided. Since commit a95b37e20db9 (kbuild: get <linux/compiler_types.h> out of <linux/kconfig.h>), compiler_types.h is automatically included by all kernel C code - i.e., the definition of inline including the unused attribute is guaranteed to be in effect whenever ZSTD_STATIC is expanded. Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Miguel Ojeda <miguel.ojeda.sandonis@gmail.com>
2019-05-21treewide: Add SPDX license identifier - Makefile/KconfigThomas Gleixner1-0/+1
Add SPDX license identifiers to all Make/Kconfig files which: - Have no license information of any form These files fall under the project license, GPL v2 only. The resulting SPDX license identifier is: GPL-2.0-only Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2019-04-08lib: zstd: Mark expected switch fall-throughsGustavo A. R. Silva4-1/+12
In preparation to enabling -Wimplicit-fallthrough, mark switch cases where we are expecting to fall through. This patch fixes the following warnings: lib/zstd/bitstream.h:261:30: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/bitstream.h:262:30: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/bitstream.h:263:30: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/bitstream.h:264:30: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/bitstream.h:265:30: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/compress.c:3183:16: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/decompress.c:1770:18: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/decompress.c:2376:15: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/decompress.c:2404:15: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/decompress.c:2435:16: warning: this statement may fall through [-Wimplicit-fallthrough=] lib/zstd/huf_compress.c: In function ‘HUF_compress1X_usingCTable’: lib/zstd/huf_compress.c:535:5: warning: this statement may fall through [-Wimplicit-fallthrough=] if (sizeof((stream)->bitContainer) * 8 < HUF_TABLELOG_MAX * 4 + 7) \ ^ lib/zstd/huf_compress.c:558:54: note: in expansion of macro ‘HUF_FLUSHBITS_2’ case 3: HUF_encodeSymbol(&bitC, ip[n + 2], CTable); HUF_FLUSHBITS_2(&bitC); ^~~~~~~~~~~~~~~ lib/zstd/huf_compress.c:559:2: note: here case 2: HUF_encodeSymbol(&bitC, ip[n + 1], CTable); HUF_FLUSHBITS_1(&bitC); ^~~~ lib/zstd/huf_compress.c:531:5: warning: this statement may fall through [-Wimplicit-fallthrough=] if (sizeof((stream)->bitContainer) * 8 < HUF_TABLELOG_MAX * 2 + 7) \ ^ lib/zstd/huf_compress.c:559:54: note: in expansion of macro ‘HUF_FLUSHBITS_1’ case 2: HUF_encodeSymbol(&bitC, ip[n + 1], CTable); HUF_FLUSHBITS_1(&bitC); ^~~~~~~~~~~~~~~ lib/zstd/huf_compress.c:560:2: note: here case 1: HUF_encodeSymbol(&bitC, ip[n + 0], CTable); HUF_FLUSHBITS(&bitC); ^~~~ AR lib/zstd//built-in.a Warning level 3 was used: -Wimplicit-fallthrough=3 This patch is part of the ongoing efforts to enabling -Wimplicit-fallthrough. Reviewed-by: Kees Cook <keescook@chromium.org> Signed-off-by: Gustavo A. R. Silva <gustavo@embeddedor.com>
2018-03-26lib: zstd: clean up Makefile for simpler composite object handlingMasahiro Yamada1-13/+4
Now, Kbuild nicely handles composite objects to avoid multiple definition. Makefiles can simply add the same objects multiple times across composite objects. Signed-off-by: Masahiro Yamada <yamada.masahiro@socionext.com>
2017-08-15lib: Add zstd modulesNick Terrell16-0/+11847
Add zstd compression and decompression kernel modules. zstd offers a wide varity of compression speed and quality trade-offs. It can compress at speeds approaching lz4, and quality approaching lzma. zstd decompressions at speeds more than twice as fast as zlib, and decompression speed remains roughly the same across all compression levels. The code was ported from the upstream zstd source repository. The `linux/zstd.h` header was modified to match linux kernel style. The cross-platform and allocation code was stripped out. Instead zstd requires the caller to pass a preallocated workspace. The source files were clang-formatted [1] to match the Linux Kernel style as much as possible. Otherwise, the code was unmodified. We would like to avoid as much further manual modification to the source code as possible, so it will be easier to keep the kernel zstd up to date. I benchmarked zstd compression as a special character device. I ran zstd and zlib compression at several levels, as well as performing no compression, which measure the time spent copying the data to kernel space. Data is passed to the compresser 4096 B at a time. The benchmark file is located in the upstream zstd source repository under `contrib/linux-kernel/zstd_compress_test.c` [2]. I ran the benchmarks on a Ubuntu 14.04 VM with 2 cores and 4 GiB of RAM. The VM is running on a MacBook Pro with a 3.1 GHz Intel Core i7 processor, 16 GB of RAM, and a SSD. I benchmarked using `silesia.tar` [3], which is 211,988,480 B large. Run the following commands for the benchmark: sudo modprobe zstd_compress_test sudo mknod zstd_compress_test c 245 0 sudo cp silesia.tar zstd_compress_test The time is reported by the time of the userland `cp`. The MB/s is computed with 1,536,217,008 B / time(buffer size, hash) which includes the time to copy from userland. The Adjusted MB/s is computed with 1,536,217,088 B / (time(buffer size, hash) - time(buffer size, none)). The memory reported is the amount of memory the compressor requests. | Method | Size (B) | Time (s) | Ratio | MB/s | Adj MB/s | Mem (MB) | |----------|----------|----------|-------|---------|----------|----------| | none | 11988480 | 0.100 | 1 | 2119.88 | - | - | | zstd -1 | 73645762 | 1.044 | 2.878 | 203.05 | 224.56 | 1.23 | | zstd -3 | 66988878 | 1.761 | 3.165 | 120.38 | 127.63 | 2.47 | | zstd -5 | 65001259 | 2.563 | 3.261 | 82.71 | 86.07 | 2.86 | | zstd -10 | 60165346 | 13.242 | 3.523 | 16.01 | 16.13 | 13.22 | | zstd -15 | 58009756 | 47.601 | 3.654 | 4.45 | 4.46 | 21.61 | | zstd -19 | 54014593 | 102.835 | 3.925 | 2.06 | 2.06 | 60.15 | | zlib -1 | 77260026 | 2.895 | 2.744 | 73.23 | 75.85 | 0.27 | | zlib -3 | 72972206 | 4.116 | 2.905 | 51.50 | 52.79 | 0.27 | | zlib -6 | 68190360 | 9.633 | 3.109 | 22.01 | 22.24 | 0.27 | | zlib -9 | 67613382 | 22.554 | 3.135 | 9.40 | 9.44 | 0.27 | I benchmarked zstd decompression using the same method on the same machine. The benchmark file is located in the upstream zstd repo under `contrib/linux-kernel/zstd_decompress_test.c` [4]. The memory reported is the amount of memory required to decompress data compressed with the given compression level. If you know the maximum size of your input, you can reduce the memory usage of decompression irrespective of the compression level. | Method | Time (s) | MB/s | Adjusted MB/s | Memory (MB) | |----------|----------|---------|---------------|-------------| | none | 0.025 | 8479.54 | - | - | | zstd -1 | 0.358 | 592.15 | 636.60 | 0.84 | | zstd -3 | 0.396 | 535.32 | 571.40 | 1.46 | | zstd -5 | 0.396 | 535.32 | 571.40 | 1.46 | | zstd -10 | 0.374 | 566.81 | 607.42 | 2.51 | | zstd -15 | 0.379 | 559.34 | 598.84 | 4.61 | | zstd -19 | 0.412 | 514.54 | 547.77 | 8.80 | | zlib -1 | 0.940 | 225.52 | 231.68 | 0.04 | | zlib -3 | 0.883 | 240.08 | 247.07 | 0.04 | | zlib -6 | 0.844 | 251.17 | 258.84 | 0.04 | | zlib -9 | 0.837 | 253.27 | 287.64 | 0.04 | Tested in userland using the test-suite in the zstd repo under `contrib/linux-kernel/test/UserlandTest.cpp` [5] by mocking the kernel functions. Fuzz tested using libfuzzer [6] with the fuzz harnesses under `contrib/linux-kernel/test/{RoundTripCrash.c,DecompressCrash.c}` [7] [8] with ASAN, UBSAN, and MSAN. Additionaly, it was tested while testing the BtrFS and SquashFS patches coming next. [1] https://clang.llvm.org/docs/ClangFormat.html [2] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/zstd_compress_test.c [3] http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia [4] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/zstd_decompress_test.c [5] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/UserlandTest.cpp [6] http://llvm.org/docs/LibFuzzer.html [7] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/RoundTripCrash.c [8] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/DecompressCrash.c zstd source repository: https://github.com/facebook/zstd Signed-off-by: Nick Terrell <terrelln@fb.com> Signed-off-by: Chris Mason <clm@fb.com>
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 12:47:49 +0000