[GIT,PULL] zstd changes for v5.16

Message ID	20211109013058.22224-1-nickrterrell@gmail.com (mailing list archive)
State	New, archived
Headers	show Return-Path: <linux-btrfs-owner@kernel.org> From: Nick Terrell <nickrterrell@gmail.com> To: Linus Torvalds <torvalds@linux-foundation.org> Cc: Stephen Rothwell <sfr@canb.auug.org.au>, linux-crypto@vger.kernel.org, linux-btrfs@vger.kernel.org, squashfs-devel@lists.sourceforge.net, linux-f2fs-devel@lists.sourceforge.net, linux-kernel@vger.kernel.org, Kernel Team <Kernel-team@fb.com>, Nick Terrell <nickrterrell@gmail.com>, Nick Terrell <terrelln@fb.com>, Chris Mason <clm@fb.com>, Petr Malat <oss@malat.biz>, Yann Collet <cyan@fb.com>, Christoph Hellwig <hch@infradead.org>, =?utf-8?b?TWljaGHFgiBNaXJvc8WCYXc=?= <mirq-linux@rere.qmqm.pl>, David Sterba <dsterba@suse.cz>, Oleksandr Natalenko <oleksandr@natalenko.name>, Felix Handte <felixh@fb.com>, Eric Biggers <ebiggers@kernel.org>, Randy Dunlap <rdunlap@infradead.org>, Paul Jones <paul@pauljones.id.au>, Tom Seewald <tseewald@gmail.com>, Sedat Dilek <sedat.dilek@gmail.com>, Jean-Denis Girard <jd.girard@sysnux.pf> Subject: [GIT PULL] zstd changes for v5.16 Date: Mon, 8 Nov 2021 17:30:58 -0800 Message-Id: <20211109013058.22224-1-nickrterrell@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Precedence: bulk
Series	[GIT,PULL] zstd changes for v5.16 \| expand [GIT,PULL] zstd changes for v5.16

Nick Terrell Nov. 9, 2021, 1:30 a.m. UTC

From: Nick Terrell <terrelln@fb.com>

Hi Linus,

I am sending you a pull request to add myself as the maintainer of zstd and
update the zstd version in the kernel, which is now 4 years out of date,
to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
and performance improvements. And generates the kernel zstd automatically
from upstream zstd, so it is easier to keep the zstd verison up to date, and we
don't fall so far out of date again.

Thanks,
Nick Terrell

The following changes since commit d2f38a3c6507b2520101f9a3807ed98f1bdc545a:

  Merge tag 'backlight-next-5.16' of git://git.kernel.org/pub/scm/linux/kernel/git/lee/backlight (2021-11-08 12:21:28 -0800)

are available in the Git repository at:

  git@github.com:terrelln/linux.git tags/zstd-for-linus-v5.16

for you to fetch changes up to 0a8ea235837cc39f27c45689930aa97ae91d5953:

  lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical (2021-11-08 16:55:38 -0800)

----------------------------------------------------------------
Update to zstd-1.4.10

This PR includes 5 commits that update the zstd library version:

1. 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.
2. 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.
3. Imports the zstd-1.4.10 source code. This commit is automatically generated
   from upstream zstd (https://github.com/facebook/zstd).
4. Adds me (terrelln@fb.com) as the maintainer of `lib/zstd`.
5. Fixes a newly added build warning for clang.

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.

Where is the previous discussion?
---------------------------------

Links for the discussions of the previous versions of the patch set.
The largest changes in the design of the patchset are driven by the discussions
in V11, V5, and V1. Sorry for the mix of links, I couldn't find most of the the
threads on lkml.org.

V12: https://www.spinics.net/lists/linux-crypto/msg58189.html
V11: https://lore.kernel.org/linux-btrfs/20210430013157.747152-1-nickrterrell@gmail.com/
V10: https://lore.kernel.org/lkml/20210426234621.870684-2-nickrterrell@gmail.com/
V9: https://lore.kernel.org/linux-btrfs/20210330225112.496213-1-nickrterrell@gmail.com/
V8: https://lore.kernel.org/linux-f2fs-devel/20210326191859.1542272-1-nickrterrell@gmail.com/
V7: https://lkml.org/lkml/2020/12/3/1195
V6: https://lkml.org/lkml/2020/12/2/1245
V5: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
V4: https://www.spinics.net/lists/linux-btrfs/msg105783.html
V3: https://lkml.org/lkml/2020/9/23/1074
V2: https://www.spinics.net/lists/linux-btrfs/msg105505.html
V1: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/

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>

----------------------------------------------------------------
Nathan Chancellor (1):
      lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical

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                  | 1414 +++++++
 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                   | 1346 +++++++
 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          | 2085 ++++++++++
 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, 27373 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

Nick Terrell Nov. 10, 2021, 6:46 p.m. UTC | #1

> On Nov 8, 2021, at 5:30 PM, Nick Terrell <nickrterrell@gmail.com> wrote:
> 
> From: Nick Terrell <terrelln@fb.com>
> 
> Hi Linus,
> 
> I am sending you a pull request to add myself as the maintainer of zstd and
> update the zstd version in the kernel, which is now 4 years out of date,
> to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
> and performance improvements. And generates the kernel zstd automatically
> from upstream zstd, so it is easier to keep the zstd verison up to date, and we
> don't fall so far out of date again.
> 
> Thanks,
> Nick Terrell

Hi Linus,

I just wanted to make sure that you’ve received my pull request. I’m a newbie
here, so I want to make sure I’m not making a stupid mistake that means you’ve
missed my message. I’d hate for this PR to not even be considered for merging
in this window because of some mistake I’ve made.

Thanks,
Nick Terrell


> The following changes since commit d2f38a3c6507b2520101f9a3807ed98f1bdc545a:
> 
>  Merge tag 'backlight-next-5.16' of git://git.kernel.org/pub/scm/linux/kernel/git/lee/backlight (2021-11-08 12:21:28 -0800)
> 
> are available in the Git repository at:
> 
>  git@github.com:terrelln/linux.git tags/zstd-for-linus-v5.16
> 
> for you to fetch changes up to 0a8ea235837cc39f27c45689930aa97ae91d5953:
> 
>  lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical (2021-11-08 16:55:38 -0800)
> 
> ----------------------------------------------------------------
> Update to zstd-1.4.10
> 
> This PR includes 5 commits that update the zstd library version:
> 
> 1. 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.
> 2. 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.
> 3. Imports the zstd-1.4.10 source code. This commit is automatically generated
>   from upstream zstd (https://github.com/facebook/zstd).
> 4. Adds me (terrelln@fb.com) as the maintainer of `lib/zstd`.
> 5. Fixes a newly added build warning for clang.
> 
> 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.
> 
> Where is the previous discussion?
> ---------------------------------
> 
> Links for the discussions of the previous versions of the patch set.
> The largest changes in the design of the patchset are driven by the discussions
> in V11, V5, and V1. Sorry for the mix of links, I couldn't find most of the the
> threads on lkml.org.
> 
> V12: https://www.spinics.net/lists/linux-crypto/msg58189.html 
> V11: https://lore.kernel.org/linux-btrfs/20210430013157.747152-1-nickrterrell@gmail.com/
> V10: https://lore.kernel.org/lkml/20210426234621.870684-2-nickrterrell@gmail.com/
> V9: https://lore.kernel.org/linux-btrfs/20210330225112.496213-1-nickrterrell@gmail.com/
> V8: https://lore.kernel.org/linux-f2fs-devel/20210326191859.1542272-1-nickrterrell@gmail.com/
> V7: https://lkml.org/lkml/2020/12/3/1195
> V6: https://lkml.org/lkml/2020/12/2/1245
> V5: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
> V4: https://www.spinics.net/lists/linux-btrfs/msg105783.html 
> V3: https://lkml.org/lkml/2020/9/23/1074
> V2: https://www.spinics.net/lists/linux-btrfs/msg105505.html 
> V1: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
> 
> 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>
> 
> ----------------------------------------------------------------
> Nathan Chancellor (1):
>      lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical
> 
> 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                  | 1414 +++++++
> 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                   | 1346 +++++++
> 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          | 2085 ++++++++++
> 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, 27373 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

Nick Terrell Nov. 11, 2021, 8:11 p.m. UTC | #2

> On Nov 8, 2021, at 5:30 PM, Nick Terrell <nickrterrell@gmail.com> wrote:
> 
> From: Nick Terrell <terrelln@fb.com>
> 
> Hi Linus,
> 
> I am sending you a pull request to add myself as the maintainer of zstd and
> update the zstd version in the kernel, which is now 4 years out of date,
> to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
> and performance improvements. And generates the kernel zstd automatically
> from upstream zstd, so it is easier to keep the zstd verison up to date, and we
> don't fall so far out of date again.
> 
> Thanks,
> Nick Terrell
> 
> The following changes since commit d2f38a3c6507b2520101f9a3807ed98f1bdc545a:
> 
>  Merge tag 'backlight-next-5.16' of git://git.kernel.org/pub/scm/linux/kernel/git/lee/backlight (2021-11-08 12:21:28 -0800)
> 
> are available in the Git repository at:
> 
>  git@github.com:terrelln/linux.git tags/zstd-for-linus-v5.16

I’ve mistakenly sent you an authenticated git repo URL. Please use this address
instead. Alternatively, I can re-send the pull request with the fixed URL if you
please.

  git://github.com/terrelln/linux tags/zstd-for-linus-v5.16

Additionally, after some off-list feedback I am:

1. Working on getting my GPG key signed by two members of the Kernel
    developer PGP keyring. I hope to have at least one signature today.
2. Reaching out to Herbert Xu—because the first zstd version went through the
    crypto tree—and other relevant maintainers who have been
    involved, and trying to get a word of support for adding me as the maintainer
    of lib/zstd in this thread.

Best,
Nick Terrell

> 
> for you to fetch changes up to 0a8ea235837cc39f27c45689930aa97ae91d5953:
> 
>  lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical (2021-11-08 16:55:38 -0800)
> 
> ----------------------------------------------------------------
> Update to zstd-1.4.10
> 
> This PR includes 5 commits that update the zstd library version:
> 
> 1. 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.
> 2. 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.
> 3. Imports the zstd-1.4.10 source code. This commit is automatically generated
>   from upstream zstd (https://github.com/facebook/zstd).
> 4. Adds me (terrelln@fb.com) as the maintainer of `lib/zstd`.
> 5. Fixes a newly added build warning for clang.
> 
> 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.
> 
> Where is the previous discussion?
> ---------------------------------
> 
> Links for the discussions of the previous versions of the patch set.
> The largest changes in the design of the patchset are driven by the discussions
> in V11, V5, and V1. Sorry for the mix of links, I couldn't find most of the the
> threads on lkml.org.
> 
> V12: https://www.spinics.net/lists/linux-crypto/msg58189.html 
> V11: https://lore.kernel.org/linux-btrfs/20210430013157.747152-1-nickrterrell@gmail.com/
> V10: https://lore.kernel.org/lkml/20210426234621.870684-2-nickrterrell@gmail.com/
> V9: https://lore.kernel.org/linux-btrfs/20210330225112.496213-1-nickrterrell@gmail.com/
> V8: https://lore.kernel.org/linux-f2fs-devel/20210326191859.1542272-1-nickrterrell@gmail.com/
> V7: https://lkml.org/lkml/2020/12/3/1195
> V6: https://lkml.org/lkml/2020/12/2/1245
> V5: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
> V4: https://www.spinics.net/lists/linux-btrfs/msg105783.html 
> V3: https://lkml.org/lkml/2020/9/23/1074
> V2: https://www.spinics.net/lists/linux-btrfs/msg105505.html 
> V1: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
> 
> 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>
> 
> ----------------------------------------------------------------
> Nathan Chancellor (1):
>      lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical
> 
> 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                  | 1414 +++++++
> 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                   | 1346 +++++++
> 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          | 2085 ++++++++++
> 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, 27373 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

Linus Torvalds Nov. 11, 2021, 10:59 p.m. UTC | #3

On Wed, Nov 10, 2021 at 10:47 AM Nick Terrell <terrelln@fb.com> wrote:
>
> I just wanted to make sure that you’ve received my pull request. I’m a newbie
> here, so I want to make sure I’m not making a stupid mistake that means you’ve
> missed my message. I’d hate for this PR to not even be considered for merging
> in this window because of some mistake I’ve made.

Oh, it's in my queue, but it's basically at the end of my queue
because I will need to take a much deeper look into what's going on.

It's not just that you're a new source of pulls, it's also that this
is a big change and completely changes the organization of the zlib
stuff. So every time I look at my list of pending pulls, this always
ends up being "I'll do all the normal ones first".

So it's not lost, but this is the kind of pull that I tend to do when
my queues have emptied. Which they haven't done yet..

               Linus

Nick Terrell Nov. 12, 2021, 12:08 a.m. UTC | #4

> On Nov 11, 2021, at 2:59 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> 
> On Wed, Nov 10, 2021 at 10:47 AM Nick Terrell <terrelln@fb.com> wrote:
>> 
>> I just wanted to make sure that you’ve received my pull request. I’m a newbie
>> here, so I want to make sure I’m not making a stupid mistake that means you’ve
>> missed my message. I’d hate for this PR to not even be considered for merging
>> in this window because of some mistake I’ve made.
> 
> Oh, it's in my queue, but it's basically at the end of my queue
> because I will need to take a much deeper look into what's going on.
>
> It's not just that you're a new source of pulls, it's also that this
> is a big change and completely changes the organization of the zlib
> stuff. So every time I look at my list of pending pulls, this always
> ends up being "I'll do all the normal ones first".
> 
> So it's not lost, but this is the kind of pull that I tend to do when
> my queues have emptied. Which they haven't done yet..

Thanks for the ack, I really appreciate it! I figured that was the case.

When you do get a chance to take a look, please let me know if there
is anything more I can do to make it easier for you. In the meantime,
I’ll focus on getting my key better signed.

Best,
Nick

>               Linus

Herbert Xu Nov. 13, 2021, 5:41 a.m. UTC | #5

Nick Terrell <terrelln@fb.com> wrote:
>
> 2. Reaching out to Herbert Xu—because the first zstd version went through the
>    crypto tree—and other relevant maintainers who have been
>    involved, and trying to get a word of support for adding me as the maintainer
>    of lib/zstd in this thread.

Actually I don't think I ever merged lib/zstd.  I did take
crypto/zstd though which is the Crypto API wrapper around the
lib/zstd code.

Since the current contention is with lib/zstd I think it probably
makes sense for Linus to take it directly.

I think you should certainly be the maintainer of lib/zstd since
it was added by you and mostly used by you too :)

Thanks,

Sedat Dilek Nov. 13, 2021, 9:07 p.m. UTC | #6

On Tue, Nov 9, 2021 at 2:24 AM Nick Terrell <nickrterrell@gmail.com> wrote:
>
> From: Nick Terrell <terrelln@fb.com>
>
> Hi Linus,
>
> I am sending you a pull request to add myself as the maintainer of zstd and
> update the zstd version in the kernel, which is now 4 years out of date,
> to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
> and performance improvements. And generates the kernel zstd automatically
> from upstream zstd, so it is easier to keep the zstd verison up to date, and we
> don't fall so far out of date again.
>

Hi Nick,

is it possible to have an adapted version of your work for Linux
v5.15.y which is a new kernel with LongTerm Support (see [1])?

Thanks.

Regards,
- Sedat -

[1] https://www.kernel.org/category/releases.html

> Thanks,
> Nick Terrell
>
> The following changes since commit d2f38a3c6507b2520101f9a3807ed98f1bdc545a:
>
>   Merge tag 'backlight-next-5.16' of git://git.kernel.org/pub/scm/linux/kernel/git/lee/backlight (2021-11-08 12:21:28 -0800)
>
> are available in the Git repository at:
>
>   git@github.com:terrelln/linux.git tags/zstd-for-linus-v5.16
>
> for you to fetch changes up to 0a8ea235837cc39f27c45689930aa97ae91d5953:
>
>   lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical (2021-11-08 16:55:38 -0800)
>
> ----------------------------------------------------------------
> Update to zstd-1.4.10
>
> This PR includes 5 commits that update the zstd library version:
>
> 1. 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.
> 2. 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.
> 3. Imports the zstd-1.4.10 source code. This commit is automatically generated
>    from upstream zstd (https://github.com/facebook/zstd).
> 4. Adds me (terrelln@fb.com) as the maintainer of `lib/zstd`.
> 5. Fixes a newly added build warning for clang.
>
> 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.
>
> Where is the previous discussion?
> ---------------------------------
>
> Links for the discussions of the previous versions of the patch set.
> The largest changes in the design of the patchset are driven by the discussions
> in V11, V5, and V1. Sorry for the mix of links, I couldn't find most of the the
> threads on lkml.org.
>
> V12: https://www.spinics.net/lists/linux-crypto/msg58189.html
> V11: https://lore.kernel.org/linux-btrfs/20210430013157.747152-1-nickrterrell@gmail.com/
> V10: https://lore.kernel.org/lkml/20210426234621.870684-2-nickrterrell@gmail.com/
> V9: https://lore.kernel.org/linux-btrfs/20210330225112.496213-1-nickrterrell@gmail.com/
> V8: https://lore.kernel.org/linux-f2fs-devel/20210326191859.1542272-1-nickrterrell@gmail.com/
> V7: https://lkml.org/lkml/2020/12/3/1195
> V6: https://lkml.org/lkml/2020/12/2/1245
> V5: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
> V4: https://www.spinics.net/lists/linux-btrfs/msg105783.html
> V3: https://lkml.org/lkml/2020/9/23/1074
> V2: https://www.spinics.net/lists/linux-btrfs/msg105505.html
> V1: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
>
> 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>
>
> ----------------------------------------------------------------
> Nathan Chancellor (1):
>       lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical
>
> 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                  | 1414 +++++++
>  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                   | 1346 +++++++
>  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          | 2085 ++++++++++
>  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, 27373 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

pr-tracker-bot@kernel.org Nov. 14, 2021, 12:43 a.m. UTC | #7

The pull request you sent on Mon,  8 Nov 2021 17:30:58 -0800:

> git@github.com:terrelln/linux.git tags/zstd-for-linus-v5.16

has been merged into torvalds/linux.git:
https://git.kernel.org/torvalds/c/c8c109546a19613d323a319d0c921cb1f317e629

Thank you!

Geert Uytterhoeven Nov. 14, 2021, 7:11 p.m. UTC | #8

On Sat, Nov 13, 2021 at 10:12 PM Sedat Dilek <sedat.dilek@gmail.com> wrote:
> On Tue, Nov 9, 2021 at 2:24 AM Nick Terrell <nickrterrell@gmail.com> wrote:
> > I am sending you a pull request to add myself as the maintainer of zstd and
> > update the zstd version in the kernel, which is now 4 years out of date,
> > to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
> > and performance improvements. And generates the kernel zstd automatically
> > from upstream zstd, so it is easier to keep the zstd verison up to date, and we
> > don't fall so far out of date again.

> is it possible to have an adapted version of your work for Linux
> v5.15.y which is a new kernel with LongTerm Support (see [1])?

Let's wait a bit before porting this to stable...

bloat-o-meter output for an atari_defconfig build with the old/new zstd
code (i.e. before/after commit e0c1b49f5b674cca ("lib: zstd: Upgrade to
latest upstream zstd version 1.4.10"):

vmlinux:

    add/remove: 96/28 grow/shrink: 28/29 up/down: 51766/-38162 (13604)
    CONFIG_ZSTD_DECOMPRESS=y due to CONFIG_RD_ZSTD=y (which is the default)

    Not a small increase, but acceptable, I guess?

lib/zstd/zstd_compress.ko:

    CONFIG_ZSTD_COMPRESS=m

    add/remove: 183/38 grow/shrink: 58/37 up/down: 346620/-51074 (295546)
    Function                                     old     new   delta
    ZSTD_compressBlock_btultra_dictMatchState       -   27802  +27802
    ZSTD_compressBlock_btopt_dictMatchState        -   27614  +27614
    ZSTD_compressBlock_doubleFast_dictMatchState       -   24420  +24420
    ZSTD_compressBlock_btultra_extDict             -   24376  +24376
    ZSTD_compressBlock_fast_dictMatchState         -   16712  +16712
    ZSTD_compressBlock_btultra2                    -   15432  +15432
    ZSTD_compressBlock_btopt_extDict            9052   24096  +15044
    ZSTD_initStats_ultra                           -   15040  +15040
    ZSTD_compressBlock_btultra                     -   14802  +14802
    ZSTD_compressBlock_doubleFast_extDict_generic    2432   12216   +9784
    ZSTD_compressBlock_doubleFast               8846   16342   +7496
    ZSTD_compressBlock_fast_extDict_generic     1254    8556   +7302
    ZSTD_compressBlock_btopt                    8826   15184   +6358
    ZSTD_compressBlock_fast                     3896    9532   +5636
    ZSTD_compressBlock_lazy2_extDict            6940   11578   +4638
    ZSTD_compressSuperBlock                        -    4440   +4440
    ZSTD_resetCCtx_internal                        -    3736   +3736
    ZSTD_HcFindBestMatch_dedicatedDictSearch_selectMLS.constprop
-    3706   +3706
    ...

    An increase of 288 KiB?
    My first thought was bloat-a-meter doesn't handle modules correctly.
    So I enabled CONFIG_CRYPTO_ZSTD=y, which made CONFIG_ZSTD_COMPRESS=y,
    and the impact on vmlinux is:

        add/remove: 288/0 grow/shrink: 5/0 up/down: 432712/0 (432712)

    Whoops...

    All of the top functions above just call ZSTD_compressBlock_opt_generic()
    with different parameters. Looks like the forced inlining

        FORCE_INLINE_TEMPLATE size_t
        ZSTD_compressBlock_opt_generic(ZSTD_matchState_t* ms,
                                       seqStore_t* seqStore,
                                       U32 rep[ZSTD_REP_NUM],
                                 const void* src, size_t srcSize,
                                 const int optLevel,
                                 const ZSTD_dictMode_e dictMode)

    is not that suitable for the kernel...

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Nick Terrell Nov. 14, 2021, 8:33 p.m. UTC | #9

On Sun, Nov 14, 2021 at 11:11 AM Geert Uytterhoeven
<geert@linux-m68k.org> wrote:
>
> On Sat, Nov 13, 2021 at 10:12 PM Sedat Dilek <sedat.dilek@gmail.com> wrote:
> > On Tue, Nov 9, 2021 at 2:24 AM Nick Terrell <nickrterrell@gmail.com> wrote:
> > > I am sending you a pull request to add myself as the maintainer of zstd and
> > > update the zstd version in the kernel, which is now 4 years out of date,
> > > to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
> > > and performance improvements. And generates the kernel zstd automatically
> > > from upstream zstd, so it is easier to keep the zstd verison up to date, and we
> > > don't fall so far out of date again.
>
> > is it possible to have an adapted version of your work for Linux
> > v5.15.y which is a new kernel with LongTerm Support (see [1])?
>
> Let's wait a bit before porting this to stable...
>
> bloat-o-meter output for an atari_defconfig build with the old/new zstd
> code (i.e. before/after commit e0c1b49f5b674cca ("lib: zstd: Upgrade to
> latest upstream zstd version 1.4.10"):
>
> vmlinux:
>
>     add/remove: 96/28 grow/shrink: 28/29 up/down: 51766/-38162 (13604)
>     CONFIG_ZSTD_DECOMPRESS=y due to CONFIG_RD_ZSTD=y (which is the default)
>
>     Not a small increase, but acceptable, I guess?
>
> lib/zstd/zstd_compress.ko:
>
>     CONFIG_ZSTD_COMPRESS=m
>
>     add/remove: 183/38 grow/shrink: 58/37 up/down: 346620/-51074 (295546)
>     Function                                     old     new   delta
>     ZSTD_compressBlock_btultra_dictMatchState       -   27802  +27802
>     ZSTD_compressBlock_btopt_dictMatchState        -   27614  +27614
>     ZSTD_compressBlock_doubleFast_dictMatchState       -   24420  +24420
>     ZSTD_compressBlock_btultra_extDict             -   24376  +24376
>     ZSTD_compressBlock_fast_dictMatchState         -   16712  +16712
>     ZSTD_compressBlock_btultra2                    -   15432  +15432
>     ZSTD_compressBlock_btopt_extDict            9052   24096  +15044
>     ZSTD_initStats_ultra                           -   15040  +15040
>     ZSTD_compressBlock_btultra                     -   14802  +14802
>     ZSTD_compressBlock_doubleFast_extDict_generic    2432   12216   +9784
>     ZSTD_compressBlock_doubleFast               8846   16342   +7496
>     ZSTD_compressBlock_fast_extDict_generic     1254    8556   +7302
>     ZSTD_compressBlock_btopt                    8826   15184   +6358
>     ZSTD_compressBlock_fast                     3896    9532   +5636
>     ZSTD_compressBlock_lazy2_extDict            6940   11578   +4638
>     ZSTD_compressSuperBlock                        -    4440   +4440
>     ZSTD_resetCCtx_internal                        -    3736   +3736
>     ZSTD_HcFindBestMatch_dedicatedDictSearch_selectMLS.constprop
> -    3706   +3706
>     ...
>
>     An increase of 288 KiB?
>     My first thought was bloat-a-meter doesn't handle modules correctly.
>     So I enabled CONFIG_CRYPTO_ZSTD=y, which made CONFIG_ZSTD_COMPRESS=y,
>     and the impact on vmlinux is:
>
>         add/remove: 288/0 grow/shrink: 5/0 up/down: 432712/0 (432712)
>
>     Whoops...
>
>     All of the top functions above just call ZSTD_compressBlock_opt_generic()
>     with different parameters. Looks like the forced inlining
>
>         FORCE_INLINE_TEMPLATE size_t
>         ZSTD_compressBlock_opt_generic(ZSTD_matchState_t* ms,
>                                        seqStore_t* seqStore,
>                                        U32 rep[ZSTD_REP_NUM],
>                                  const void* src, size_t srcSize,
>                                  const int optLevel,
>                                  const ZSTD_dictMode_e dictMode)
>
>     is not that suitable for the kernel...

Thanks for pointing that out! Code size wasn't something I was measuring in my
tests. I'll put up a patch to fix it.

That function is used by the highest compression level, so there
should be little
usage in the kernel. And what usage there is shouldn't be very speed sensitive.
So we should just be able to disable inlining for that file.

Longer term, we have noticed upstream that we had some code size bloat in
the compressor. We aggressively inlined to get better speed, but that tradeoff
went too far in some cases. So we're working on reducing the code size of
our largest translation units for the next release. All that to say
that we can land
a shorter term fix of disabling inlining for
lib/zstd/compress/zstd_opt.c for the
v5.16 kernel, and handle the problem thoroughly upstream in our next release.

Best,
Nick Terrell

> Gr{oetje,eeting}s,
>
>                         Geert
>
> --
> Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org
>
> In personal conversations with technical people, I call myself a hacker. But
> when I'm talking to journalists I just say "programmer" or something like that.
>                                 -- Linus Torvalds

Sedat Dilek Feb. 20, 2022, 9:45 a.m. UTC | #10

On Tue, Nov 9, 2021 at 2:24 AM Nick Terrell <nickrterrell@gmail.com> wrote:
>
> From: Nick Terrell <terrelln@fb.com>
>
> Hi Linus,
>
> I am sending you a pull request to add myself as the maintainer of zstd and
> update the zstd version in the kernel, which is now 4 years out of date,
> to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
> and performance improvements. And generates the kernel zstd automatically
> from upstream zstd, so it is easier to keep the zstd verison up to date, and we
> don't fall so far out of date again.
>
> Thanks,
> Nick Terrell
>
> The following changes since commit d2f38a3c6507b2520101f9a3807ed98f1bdc545a:
>
>   Merge tag 'backlight-next-5.16' of git://git.kernel.org/pub/scm/linux/kernel/git/lee/backlight (2021-11-08 12:21:28 -0800)
>
> are available in the Git repository at:
>
>   git@github.com:terrelln/linux.git tags/zstd-for-linus-v5.16
>
> for you to fetch changes up to 0a8ea235837cc39f27c45689930aa97ae91d5953:
>
>   lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical (2021-11-08 16:55:38 -0800)
>
> ----------------------------------------------------------------
> Update to zstd-1.4.10
>

Hi Nick,

where is the official ZSTD version 1.4.10 (see below links)?
Can you clarify on this, please?

v1.4.19 seems to be faster than v1.4.18 in some benchmarks.
The background of question is I wanted to request a new zstd version
for Debian (currently v1.4.18).

My second question:
As your changes where accepted for upcoming Linux v5.17...
Do you plan Git branches for...
Linux v5.16 (is [6] up2date with changes in v5.17?)...
...or even Linux v5.15 LTS?

Thanks.

Regards,
- Sedat -

[1] https://github.com/facebook/zstd/releases
[2] https://github.com/facebook/zstd/tags
[3] https://github.com/facebook/zstd/releases/tag/v1.4.9
[4] https://packages.debian.org/zstd
[5] https://github.com/terrelln/linux/branches
[6] https://github.com/terrelln/linux/commits/zstd-1.4.10

> This PR includes 5 commits that update the zstd library version:
>
> 1. 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.
> 2. 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.
> 3. Imports the zstd-1.4.10 source code. This commit is automatically generated
>    from upstream zstd (https://github.com/facebook/zstd).
> 4. Adds me (terrelln@fb.com) as the maintainer of `lib/zstd`.
> 5. Fixes a newly added build warning for clang.
>
> 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.
>
> Where is the previous discussion?
> ---------------------------------
>
> Links for the discussions of the previous versions of the patch set.
> The largest changes in the design of the patchset are driven by the discussions
> in V11, V5, and V1. Sorry for the mix of links, I couldn't find most of the the
> threads on lkml.org.
>
> V12: https://www.spinics.net/lists/linux-crypto/msg58189.html
> V11: https://lore.kernel.org/linux-btrfs/20210430013157.747152-1-nickrterrell@gmail.com/
> V10: https://lore.kernel.org/lkml/20210426234621.870684-2-nickrterrell@gmail.com/
> V9: https://lore.kernel.org/linux-btrfs/20210330225112.496213-1-nickrterrell@gmail.com/
> V8: https://lore.kernel.org/linux-f2fs-devel/20210326191859.1542272-1-nickrterrell@gmail.com/
> V7: https://lkml.org/lkml/2020/12/3/1195
> V6: https://lkml.org/lkml/2020/12/2/1245
> V5: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
> V4: https://www.spinics.net/lists/linux-btrfs/msg105783.html
> V3: https://lkml.org/lkml/2020/9/23/1074
> V2: https://www.spinics.net/lists/linux-btrfs/msg105505.html
> V1: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
>
> 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>
>
> ----------------------------------------------------------------
> Nathan Chancellor (1):
>       lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical
>
> 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                  | 1414 +++++++
>  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                   | 1346 +++++++
>  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          | 2085 ++++++++++
>  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, 27373 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

Nick Terrell March 1, 2022, 7:09 p.m. UTC | #11

> On Feb 20, 2022, at 1:45 AM, Sedat Dilek <sedat.dilek@gmail.com> wrote:
> 
> On Tue, Nov 9, 2021 at 2:24 AM Nick Terrell <nickrterrell@gmail.com> wrote:
>> 
>> From: Nick Terrell <terrelln@fb.com>
>> 
>> Hi Linus,
>> 
>> I am sending you a pull request to add myself as the maintainer of zstd and
>> update the zstd version in the kernel, which is now 4 years out of date,
>> to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
>> and performance improvements. And generates the kernel zstd automatically
>> from upstream zstd, so it is easier to keep the zstd verison up to date, and we
>> don't fall so far out of date again.
>> 
>> Thanks,
>> Nick Terrell
>> 
>> The following changes since commit d2f38a3c6507b2520101f9a3807ed98f1bdc545a:
>> 
>>  Merge tag 'backlight-next-5.16' of git://git.kernel.org/pub/scm/linux/kernel/git/lee/backlight (2021-11-08 12:21:28 -0800)
>> 
>> are available in the Git repository at:
>> 
>>  git@github.com:terrelln/linux.git tags/zstd-for-linus-v5.16
>> 
>> for you to fetch changes up to 0a8ea235837cc39f27c45689930aa97ae91d5953:
>> 
>>  lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical (2021-11-08 16:55:38 -0800)
>> 
>> ----------------------------------------------------------------
>> Update to zstd-1.4.10
>> 
> 
> Hi Nick,
> 
> where is the official ZSTD version 1.4.10 (see below links)?
> Can you clarify on this, please?

The upstream tag v1.4.10 [0] is what is imported into the kernel.

> v1.4.19 seems to be faster than v1.4.18 in some benchmarks.
> The background of question is I wanted to request a new zstd version
> for Debian (currently v1.4.18).

There is no v1.4.18 or v1.4.19, I believe you meant v1.4.8 and v1.4.9.

The latest zstd versions is v1.5.2. We do expect speed improvements
in v1.5.2. However, we don't manage the zstd package in any package
manager, Debian included. So we don't have control over the version
of zstd in Debian.

> My second question:
> As your changes where accepted for upcoming Linux v5.17...
> Do you plan Git branches for...
> Linux v5.16 (is [6] up2date with changes in v5.17?)...
> ...or even Linux v5.15 LTS?

These changes landed in v5.16. I'm not planning on backporting
these changes to any older kernel version myself.

But, I am hoping to update to the latest zstd in either v5.18 or
v5.19. I'm a bit busy currently, but I just got a tentative volunteer
to update the kernel to v1.5.2, and more importantly test the
update.

Best,
Nick Terrell

[0] https://github.com/facebook/zstd/tree/v1.4.10

> Thanks.
> 
> Regards,
> - Sedat -
> 
> [1] https://github.com/facebook/zstd/releases
> [2] https://github.com/facebook/zstd/tags
> [3] https://github.com/facebook/zstd/releases/tag/v1.4.9
> [4] https://packages.debian.org/zstd 
> [5] https://github.com/terrelln/linux/branches
> [6] https://github.com/terrelln/linux/commits/zstd-1.4.10
> 
>> This PR includes 5 commits that update the zstd library version:
>> 
>> 1. 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.
>> 2. 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.
>> 3. Imports the zstd-1.4.10 source code. This commit is automatically generated
>>   from upstream zstd (https://github.com/facebook/zstd).
>> 4. Adds me (terrelln@fb.com) as the maintainer of `lib/zstd`.
>> 5. Fixes a newly added build warning for clang.
>> 
>> 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.
>> 
>> Where is the previous discussion?
>> ---------------------------------
>> 
>> Links for the discussions of the previous versions of the patch set.
>> The largest changes in the design of the patchset are driven by the discussions
>> in V11, V5, and V1. Sorry for the mix of links, I couldn't find most of the the
>> threads on lkml.org.
>> 
>> V12: https://www.spinics.net/lists/linux-crypto/msg58189.html 
>> V11: https://lore.kernel.org/linux-btrfs/20210430013157.747152-1-nickrterrell@gmail.com/
>> V10: https://lore.kernel.org/lkml/20210426234621.870684-2-nickrterrell@gmail.com/
>> V9: https://lore.kernel.org/linux-btrfs/20210330225112.496213-1-nickrterrell@gmail.com/
>> V8: https://lore.kernel.org/linux-f2fs-devel/20210326191859.1542272-1-nickrterrell@gmail.com/
>> V7: https://lkml.org/lkml/2020/12/3/1195
>> V6: https://lkml.org/lkml/2020/12/2/1245
>> V5: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
>> V4: https://www.spinics.net/lists/linux-btrfs/msg105783.html 
>> V3: https://lkml.org/lkml/2020/9/23/1074
>> V2: https://www.spinics.net/lists/linux-btrfs/msg105505.html 
>> V1: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
>> 
>> 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>
>> 
>> ----------------------------------------------------------------
>> Nathan Chancellor (1):
>>      lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical
>> 
>> 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                  | 1414 +++++++
>> 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                   | 1346 +++++++
>> 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          | 2085 ++++++++++
>> 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, 27373 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

Sedat Dilek March 2, 2022, 10:31 p.m. UTC | #12

On Tue, Mar 1, 2022 at 8:10 PM Nick Terrell <terrelln@fb.com> wrote:
>
>
>
> > On Feb 20, 2022, at 1:45 AM, Sedat Dilek <sedat.dilek@gmail.com> wrote:
> >
> > On Tue, Nov 9, 2021 at 2:24 AM Nick Terrell <nickrterrell@gmail.com> wrote:
> >>
> >> From: Nick Terrell <terrelln@fb.com>
> >>
> >> Hi Linus,
> >>
> >> I am sending you a pull request to add myself as the maintainer of zstd and
> >> update the zstd version in the kernel, which is now 4 years out of date,
> >> to the latest zstd release. This includes bug fixes, much more extensive fuzzing,
> >> and performance improvements. And generates the kernel zstd automatically
> >> from upstream zstd, so it is easier to keep the zstd verison up to date, and we
> >> don't fall so far out of date again.
> >>
> >> Thanks,
> >> Nick Terrell
> >>
> >> The following changes since commit d2f38a3c6507b2520101f9a3807ed98f1bdc545a:
> >>
> >>  Merge tag 'backlight-next-5.16' of git://git.kernel.org/pub/scm/linux/kernel/git/lee/backlight (2021-11-08 12:21:28 -0800)
> >>
> >> are available in the Git repository at:
> >>
> >>  git@github.com:terrelln/linux.git tags/zstd-for-linus-v5.16
> >>
> >> for you to fetch changes up to 0a8ea235837cc39f27c45689930aa97ae91d5953:
> >>
> >>  lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical (2021-11-08 16:55:38 -0800)
> >>
> >> ----------------------------------------------------------------
> >> Update to zstd-1.4.10
> >>
> >
> > Hi Nick,
> >
> > where is the official ZSTD version 1.4.10 (see below links)?
> > Can you clarify on this, please?
>
> The upstream tag v1.4.10 [0] is what is imported into the kernel.
>
> > v1.4.19 seems to be faster than v1.4.18 in some benchmarks.
> > The background of question is I wanted to request a new zstd version
> > for Debian (currently v1.4.18).
>
> There is no v1.4.18 or v1.4.19, I believe you meant v1.4.8 and v1.4.9.
>

Hehe, yes.
Mixed that up with kernel release versions, maybe.

> The latest zstd versions is v1.5.2. We do expect speed improvements
> in v1.5.2. However, we don't manage the zstd package in any package
> manager, Debian included. So we don't have control over the version
> of zstd in Debian.
>

Just read about the speed improvements (even post v1.4.8).

I wanted to request a version bump to 1.4.10 via Debian's reportbug tool.
There is nothing you shall do for me.
Bumping from existing 1.4.8+dfsg-3 to the lasted v1.4x like 1.4.10
might be reasonable and easier to request.
But I can ask for zstd v1.5.2 in another release branach like
Debian/experimental.

About DFSG see:

https://wiki.debian.org/DFSGLicenses

> > My second question:
> > As your changes where accepted for upcoming Linux v5.17...
> > Do you plan Git branches for...
> > Linux v5.16 (is [6] up2date with changes in v5.17?)...
> > ...or even Linux v5.15 LTS?
>
> These changes landed in v5.16. I'm not planning on backporting
> these changes to any older kernel version myself.
>

Right - backporting to v5.15 was my real question as this is LTS.

> But, I am hoping to update to the latest zstd in either v5.18 or
> v5.19. I'm a bit busy currently, but I just got a tentative volunteer
> to update the kernel to v1.5.2, and more importantly test the
> update.
>

Nice plans.
Keep me in CC.

Just for the records: v1.4.10 was tagged 8 days ago.

- Sedat -

[1] https://github.com/facebook/zstd/tags
[2] https://github.com/facebook/zstd/releases/tag/v1.4.10

> Best,
> Nick Terrell
>
> [0] https://github.com/facebook/zstd/tree/v1.4.10
>
> > Thanks.
> >
> > Regards,
> > - Sedat -
> >
> > [1] https://github.com/facebook/zstd/releases
> > [2] https://github.com/facebook/zstd/tags
> > [3] https://github.com/facebook/zstd/releases/tag/v1.4.9
> > [4] https://packages.debian.org/zstd
> > [5] https://github.com/terrelln/linux/branches
> > [6] https://github.com/terrelln/linux/commits/zstd-1.4.10
> >
> >> This PR includes 5 commits that update the zstd library version:
> >>
> >> 1. 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.
> >> 2. 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.
> >> 3. Imports the zstd-1.4.10 source code. This commit is automatically generated
> >>   from upstream zstd (https://github.com/facebook/zstd).
> >> 4. Adds me (terrelln@fb.com) as the maintainer of `lib/zstd`.
> >> 5. Fixes a newly added build warning for clang.
> >>
> >> 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.
> >>
> >> Where is the previous discussion?
> >> ---------------------------------
> >>
> >> Links for the discussions of the previous versions of the patch set.
> >> The largest changes in the design of the patchset are driven by the discussions
> >> in V11, V5, and V1. Sorry for the mix of links, I couldn't find most of the the
> >> threads on lkml.org.
> >>
> >> V12: https://www.spinics.net/lists/linux-crypto/msg58189.html
> >> V11: https://lore.kernel.org/linux-btrfs/20210430013157.747152-1-nickrterrell@gmail.com/
> >> V10: https://lore.kernel.org/lkml/20210426234621.870684-2-nickrterrell@gmail.com/
> >> V9: https://lore.kernel.org/linux-btrfs/20210330225112.496213-1-nickrterrell@gmail.com/
> >> V8: https://lore.kernel.org/linux-f2fs-devel/20210326191859.1542272-1-nickrterrell@gmail.com/
> >> V7: https://lkml.org/lkml/2020/12/3/1195
> >> V6: https://lkml.org/lkml/2020/12/2/1245
> >> V5: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
> >> V4: https://www.spinics.net/lists/linux-btrfs/msg105783.html
> >> V3: https://lkml.org/lkml/2020/9/23/1074
> >> V2: https://www.spinics.net/lists/linux-btrfs/msg105505.html
> >> V1: https://lore.kernel.org/linux-btrfs/20200916034307.2092020-1-nickrterrell@gmail.com/
> >>
> >> 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>
> >>
> >> ----------------------------------------------------------------
> >> Nathan Chancellor (1):
> >>      lib: zstd: Add cast to silence clang's -Wbitwise-instead-of-logical
> >>
> >> 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                  | 1414 +++++++
> >> 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                   | 1346 +++++++
> >> 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          | 2085 ++++++++++
> >> 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, 27373 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
>

Sedat Dilek April 3, 2022, 11:13 a.m. UTC | #13

On Wed, Mar 2, 2022 at 11:31 PM Sedat Dilek <sedat.dilek@gmail.com> wrote:

[ CC Peter Pentchev (Debian libzstd maintainer) ]

[...]

> I wanted to request a version bump to 1.4.10 via Debian's reportbug tool.

Debian now ships ZSTD (libzstd) v1.4.10 in their unstable repository.

- Sedat -

[1] https://metadata.ftp-master.debian.org/changelogs//main/libz/libzstd/libzstd_1.4.10+dfsg-1_changelog

[GIT,PULL] zstd changes for v5.16

Pull-request

Message

Comments