Merge pull request #786 from terrelln/squashfs-tools
[linux-kernel] Update patches for v4 and v5
diff --git a/contrib/linux-kernel/0000-cover-letter.patch b/contrib/linux-kernel/0000-cover-letter.patch
index 33a5189..d57ef27 100644
--- a/contrib/linux-kernel/0000-cover-letter.patch
+++ b/contrib/linux-kernel/0000-cover-letter.patch
@@ -1,7 +1,7 @@
-From 0cd63464d182bb9708f8b25f7da3dc8e5ec6b4fa Mon Sep 17 00:00:00 2001
+From 308795a7713ca6fcd468b60fba9a2fca99cee6a0 Mon Sep 17 00:00:00 2001
From: Nick Terrell <terrelln@fb.com>
-Date: Thu, 20 Jul 2017 13:18:30 -0700
-Subject: [PATCH v3 0/4] Add xxhash and zstd modules
+Date: Tue, 8 Aug 2017 19:20:25 -0700
+Subject: [PATCH v5 0/5] Add xxhash and zstd modules
Hi all,
@@ -16,27 +16,45 @@
Changelog:
v1 -> v2:
-- Make pointer in lib/xxhash.c:394 non-const (1/4)
-- Use div_u64() for division of u64s (2/4)
+- Make pointer in lib/xxhash.c:394 non-const (1/5)
+- Use div_u64() for division of u64s (2/5)
- Reduce stack usage of ZSTD_compressSequences(), ZSTD_buildSeqTable(),
ZSTD_decompressSequencesLong(), FSE_buildDTable(), FSE_decompress_wksp(),
HUF_writeCTable(), HUF_readStats(), HUF_readCTable(),
- HUF_compressWeights(), HUF_readDTableX2(), and HUF_readDTableX4() (2/4)
-- No zstd function uses more than 400 B of stack space (2/4)
+ HUF_compressWeights(), HUF_readDTableX2(), and HUF_readDTableX4() (2/5)
+- No zstd function uses more than 400 B of stack space (2/5)
v2 -> v3:
- Work around gcc-7 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388
- (2/4)
-- Fix bug in dictionary compression from upstream commit cc1522351f (2/4)
-- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff (3/4)
-- Change default compression level for BtrFS to 3 (3/4)
+ (2/5)
+- Fix bug in dictionary compression from upstream commit cc1522351f (2/5)
+- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff (3/5)
+- Change default compression level for BtrFS to 3 (3/5)
-Nick Terrell (4):
+v3 -> v4:
+- Fix compiler warnings (2/5)
+- Add missing includes (3/5)
+- Fix minor linter warnings (3/5, 4/5)
+- Add crypto patch (5/5)
+
+v4 -> v5:
+- Fix rare compression bug from upstream commit 308047eb5d (2/5)
+- Fix bug introduced in v3 when working around the gcc-7 bug (2/5)
+- Fix ZSTD_DStream initialization code in squashfs (4/5)
+- Fix patch documentation for patches written by Sean Purcell (4/5)
+
+Nick Terrell (5):
lib: Add xxhash module
lib: Add zstd modules
btrfs: Add zstd support
squashfs: Add zstd support
+ crypto: Add zstd support
+ crypto/Kconfig | 9 +
+ crypto/Makefile | 1 +
+ crypto/testmgr.c | 10 +
+ crypto/testmgr.h | 71 +
+ crypto/zstd.c | 265 ++++
fs/btrfs/Kconfig | 2 +
fs/btrfs/Makefile | 2 +-
fs/btrfs/compression.c | 1 +
@@ -47,13 +65,13 @@
fs/btrfs/props.c | 6 +
fs/btrfs/super.c | 12 +-
fs/btrfs/sysfs.c | 2 +
- fs/btrfs/zstd.c | 435 ++++++
+ fs/btrfs/zstd.c | 432 ++++++
fs/squashfs/Kconfig | 14 +
fs/squashfs/Makefile | 1 +
fs/squashfs/decompressor.c | 7 +
fs/squashfs/decompressor.h | 4 +
fs/squashfs/squashfs_fs.h | 1 +
- fs/squashfs/zstd_wrapper.c | 150 ++
+ fs/squashfs/zstd_wrapper.c | 151 ++
include/linux/xxhash.h | 236 +++
include/linux/zstd.h | 1157 +++++++++++++++
include/uapi/linux/btrfs.h | 8 +-
@@ -62,9 +80,9 @@
lib/xxhash.c | 500 +++++++
lib/zstd/Makefile | 18 +
lib/zstd/bitstream.h | 374 +++++
- lib/zstd/compress.c | 3479 ++++++++++++++++++++++++++++++++++++++++++++
- lib/zstd/decompress.c | 2526 ++++++++++++++++++++++++++++++++
- lib/zstd/entropy_common.c | 243 ++++
+ lib/zstd/compress.c | 3484 ++++++++++++++++++++++++++++++++++++++++++++
+ lib/zstd/decompress.c | 2528 ++++++++++++++++++++++++++++++++
+ lib/zstd/entropy_common.c | 243 +++
lib/zstd/error_private.h | 53 +
lib/zstd/fse.h | 575 ++++++++
lib/zstd/fse_compress.c | 795 ++++++++++
@@ -74,9 +92,10 @@
lib/zstd/huf_decompress.c | 960 ++++++++++++
lib/zstd/mem.h | 151 ++
lib/zstd/zstd_common.c | 75 +
- lib/zstd/zstd_internal.h | 250 ++++
+ lib/zstd/zstd_internal.h | 263 ++++
lib/zstd/zstd_opt.h | 1014 +++++++++++++
- 39 files changed, 14382 insertions(+), 12 deletions(-)
+ 44 files changed, 14756 insertions(+), 12 deletions(-)
+ create mode 100644 crypto/zstd.c
create mode 100644 fs/btrfs/zstd.c
create mode 100644 fs/squashfs/zstd_wrapper.c
create mode 100644 include/linux/xxhash.h
diff --git a/contrib/linux-kernel/0001-lib-Add-xxhash-module.patch b/contrib/linux-kernel/0001-lib-Add-xxhash-module.patch
index f86731c..83f0992 100644
--- a/contrib/linux-kernel/0001-lib-Add-xxhash-module.patch
+++ b/contrib/linux-kernel/0001-lib-Add-xxhash-module.patch
@@ -1,7 +1,7 @@
-From fc7f26acbabda35f1c61dfc357dbb207dc8ed23d Mon Sep 17 00:00:00 2001
+From a4b1ffb6e89bbccd519f9afa0910635668436105 Mon Sep 17 00:00:00 2001
From: Nick Terrell <terrelln@fb.com>
Date: Mon, 17 Jul 2017 17:07:18 -0700
-Subject: [PATCH v3 1/4] lib: Add xxhash module
+Subject: [PATCH v5 1/5] lib: Add xxhash module
Adds xxhash kernel module with xxh32 and xxh64 hashes. xxhash is an
extremely fast non-cryptographic hash algorithm for checksumming.
diff --git a/contrib/linux-kernel/0002-lib-Add-zstd-modules.patch b/contrib/linux-kernel/0002-lib-Add-zstd-modules.patch
index 268307c..eb8b8b2 100644
--- a/contrib/linux-kernel/0002-lib-Add-zstd-modules.patch
+++ b/contrib/linux-kernel/0002-lib-Add-zstd-modules.patch
@@ -1,7 +1,7 @@
-From 686a6149b98250d66b5951e3ae05e79063e9de98 Mon Sep 17 00:00:00 2001
+From b7f044163968d724be55bf4841fd80babe036dc2 Mon Sep 17 00:00:00 2001
From: Nick Terrell <terrelln@fb.com>
Date: Mon, 17 Jul 2017 17:08:19 -0700
-Subject: [PATCH v3 2/4] lib: Add zstd modules
+Subject: [PATCH v5 2/5] lib: Add zstd modules
Add zstd compression and decompression kernel modules.
zstd offers a wide varity of compression speed and quality trade-offs.
@@ -114,13 +114,20 @@
- Work around gcc-7 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388
- Fix bug in dictionary compression from upstream commit cc1522351f
+v3 -> v4:
+- Fix minor compiler warnings
+
+v4 -> v5:
+- Fix rare compression bug from upstream commit 308047eb5d
+- Fix bug introduced in v3 when working around the gcc-7 bug
+
include/linux/zstd.h | 1157 +++++++++++++++
lib/Kconfig | 8 +
lib/Makefile | 2 +
lib/zstd/Makefile | 18 +
lib/zstd/bitstream.h | 374 +++++
- lib/zstd/compress.c | 3479 +++++++++++++++++++++++++++++++++++++++++++++
- lib/zstd/decompress.c | 2526 ++++++++++++++++++++++++++++++++
+ lib/zstd/compress.c | 3484 +++++++++++++++++++++++++++++++++++++++++++++
+ lib/zstd/decompress.c | 2528 ++++++++++++++++++++++++++++++++
lib/zstd/entropy_common.c | 243 ++++
lib/zstd/error_private.h | 53 +
lib/zstd/fse.h | 575 ++++++++
@@ -131,9 +138,9 @@
lib/zstd/huf_decompress.c | 960 +++++++++++++
lib/zstd/mem.h | 151 ++
lib/zstd/zstd_common.c | 75 +
- lib/zstd/zstd_internal.h | 250 ++++
+ lib/zstd/zstd_internal.h | 263 ++++
lib/zstd/zstd_opt.h | 1014 +++++++++++++
- 19 files changed, 12994 insertions(+)
+ 19 files changed, 13014 insertions(+)
create mode 100644 include/linux/zstd.h
create mode 100644 lib/zstd/Makefile
create mode 100644 lib/zstd/bitstream.h
@@ -1753,10 +1760,10 @@
+#endif /* BITSTREAM_H_MODULE */
diff --git a/lib/zstd/compress.c b/lib/zstd/compress.c
new file mode 100644
-index 0000000..d60ab7d
+index 0000000..f9166cf
--- /dev/null
+++ b/lib/zstd/compress.c
-@@ -0,0 +1,3479 @@
+@@ -0,0 +1,3484 @@
+/**
+ * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
+ * All rights reserved.
@@ -2342,7 +2349,7 @@
+ mlCodeTable[seqStorePtr->longLengthPos] = MaxML;
+}
+
-+ZSTD_STATIC size_t ZSTD_compressSequences(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, size_t srcSize)
++ZSTD_STATIC size_t ZSTD_compressSequences_internal(ZSTD_CCtx *zc, void *dst, size_t dstCapacity)
+{
+ const int longOffsets = zc->params.cParams.windowLog > STREAM_ACCUMULATOR_MIN;
+ const seqStore_t *seqStorePtr = &(zc->seqStore);
@@ -2395,7 +2402,7 @@
+ else
+ op[0] = 0xFF, ZSTD_writeLE16(op + 1, (U16)(nbSeq - LONGNBSEQ)), op += 3;
+ if (nbSeq == 0)
-+ goto _check_compressibility;
++ return op - ostart;
+
+ /* seqHead : flags for FSE encoding type */
+ seqHead = op++;
@@ -2585,28 +2592,33 @@
+ op += streamSize;
+ }
+ }
-+
-+/* check compressibility */
-+_check_compressibility:
-+ {
-+ size_t const minGain = ZSTD_minGain(srcSize);
-+ size_t const maxCSize = srcSize - minGain;
-+ if ((size_t)(op - ostart) >= maxCSize) {
-+ zc->flagStaticHufTable = HUF_repeat_none;
-+ return 0;
-+ }
-+ }
-+
-+ /* confirm repcodes */
-+ {
-+ int i;
-+ for (i = 0; i < ZSTD_REP_NUM; i++)
-+ zc->rep[i] = zc->repToConfirm[i];
-+ }
-+
+ return op - ostart;
+}
+
++ZSTD_STATIC size_t ZSTD_compressSequences(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, size_t srcSize)
++{
++ size_t const cSize = ZSTD_compressSequences_internal(zc, dst, dstCapacity);
++ size_t const minGain = ZSTD_minGain(srcSize);
++ size_t const maxCSize = srcSize - minGain;
++ /* If the srcSize <= dstCapacity, then there is enough space to write a
++ * raw uncompressed block. Since we ran out of space, the block must not
++ * be compressible, so fall back to a raw uncompressed block.
++ */
++ int const uncompressibleError = cSize == ERROR(dstSize_tooSmall) && srcSize <= dstCapacity;
++ int i;
++
++ if (ZSTD_isError(cSize) && !uncompressibleError)
++ return cSize;
++ if (cSize >= maxCSize || uncompressibleError) {
++ zc->flagStaticHufTable = HUF_repeat_none;
++ return 0;
++ }
++ /* confirm repcodes */
++ for (i = 0; i < ZSTD_REP_NUM; i++)
++ zc->rep[i] = zc->repToConfirm[i];
++ return cSize;
++}
++
+/*! ZSTD_storeSeq() :
+ Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
+ `offsetCode` : distance to match, or 0 == repCode.
@@ -5238,10 +5250,10 @@
+MODULE_DESCRIPTION("Zstd Compressor");
diff --git a/lib/zstd/decompress.c b/lib/zstd/decompress.c
new file mode 100644
-index 0000000..62449ae
+index 0000000..b178467
--- /dev/null
+++ b/lib/zstd/decompress.c
-@@ -0,0 +1,2526 @@
+@@ -0,0 +1,2528 @@
+/**
+ * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
+ * All rights reserved.
@@ -6242,6 +6254,8 @@
+ BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
+ FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
+
++ seq.match = NULL;
++
+ return seq;
+}
+
@@ -11996,10 +12010,10 @@
+}
diff --git a/lib/zstd/zstd_internal.h b/lib/zstd/zstd_internal.h
new file mode 100644
-index 0000000..f0ba474
+index 0000000..1a79fab
--- /dev/null
+++ b/lib/zstd/zstd_internal.h
-@@ -0,0 +1,250 @@
+@@ -0,0 +1,263 @@
+/**
+ * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
+ * All rights reserved.
@@ -12128,7 +12142,7 @@
+/*-*******************************************
+* Shared functions to include for inlining
+*********************************************/
-+static void ZSTD_copy8(void *dst, const void *src) {
++ZSTD_STATIC void ZSTD_copy8(void *dst, const void *src) {
+ memcpy(dst, src, 8);
+}
+/*! ZSTD_wildcopy() :
@@ -12136,8 +12150,21 @@
+#define WILDCOPY_OVERLENGTH 8
+ZSTD_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)
+{
-+ if (length > 0)
-+ memcpy(dst, src, length);
++ const BYTE* ip = (const BYTE*)src;
++ BYTE* op = (BYTE*)dst;
++ BYTE* const oend = op + length;
++ /* Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388.
++ * Avoid the bad case where the loop only runs once by handling the
++ * special case separately. This doesn't trigger the bug because it
++ * doesn't involve pointer/integer overflow.
++ */
++ if (length <= 8)
++ return ZSTD_copy8(dst, src);
++ do {
++ ZSTD_copy8(op, ip);
++ op += 8;
++ ip += 8;
++ } while (op < oend);
+}
+
+/*-*******************************************
diff --git a/contrib/linux-kernel/0003-btrfs-Add-zstd-support.patch b/contrib/linux-kernel/0003-btrfs-Add-zstd-support.patch
index 5578fa3..edc7839 100644
--- a/contrib/linux-kernel/0003-btrfs-Add-zstd-support.patch
+++ b/contrib/linux-kernel/0003-btrfs-Add-zstd-support.patch
@@ -1,7 +1,7 @@
-From b0ef8fc63c9ca251ceca632f53aa1de8f1f17772 Mon Sep 17 00:00:00 2001
+From 8a9dddfbf6551afea73911e367dd4be64d62b9fd Mon Sep 17 00:00:00 2001
From: Nick Terrell <terrelln@fb.com>
Date: Mon, 17 Jul 2017 17:08:39 -0700
-Subject: [PATCH v3 3/4] btrfs: Add zstd support
+Subject: [PATCH v5 3/5] btrfs: Add zstd support
Add zstd compression and decompression support to BtrFS. zstd at its
fastest level compresses almost as well as zlib, while offering much
@@ -67,6 +67,10 @@
- Port upstream BtrFS commits e1ddce71d6, 389a6cfc2a, and 6acafd1eff
- Change default compression level for BtrFS to 3
+v3 -> v4:
+- Add missing includes, which fixes the aarch64 build
+- Fix minor linter warnings
+
fs/btrfs/Kconfig | 2 +
fs/btrfs/Makefile | 2 +-
fs/btrfs/compression.c | 1 +
@@ -77,9 +81,9 @@
fs/btrfs/props.c | 6 +
fs/btrfs/super.c | 12 +-
fs/btrfs/sysfs.c | 2 +
- fs/btrfs/zstd.c | 435 +++++++++++++++++++++++++++++++++++++++++++++
+ fs/btrfs/zstd.c | 432 +++++++++++++++++++++++++++++++++++++++++++++
include/uapi/linux/btrfs.h | 8 +-
- 12 files changed, 471 insertions(+), 12 deletions(-)
+ 12 files changed, 468 insertions(+), 12 deletions(-)
create mode 100644 fs/btrfs/zstd.c
diff --git a/fs/btrfs/Kconfig b/fs/btrfs/Kconfig
@@ -277,10 +281,10 @@
BTRFS_FEAT_ATTR_PTR(raid56),
diff --git a/fs/btrfs/zstd.c b/fs/btrfs/zstd.c
new file mode 100644
-index 0000000..1822068
+index 0000000..607ce47
--- /dev/null
+++ b/fs/btrfs/zstd.c
-@@ -0,0 +1,435 @@
+@@ -0,0 +1,432 @@
+/*
+ * Copyright (c) 2016-present, Facebook, Inc.
+ * All rights reserved.
@@ -293,20 +297,16 @@
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
-+ *
-+ * You should have received a copy of the GNU General Public
-+ * License along with this program; if not, write to the
-+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-+ * Boston, MA 021110-1307, USA.
+ */
-+#include <linux/kernel.h>
-+#include <linux/slab.h>
-+#include <linux/vmalloc.h>
-+#include <linux/init.h>
-+#include <linux/err.h>
-+#include <linux/sched.h>
-+#include <linux/pagemap.h>
+#include <linux/bio.h>
++#include <linux/err.h>
++#include <linux/init.h>
++#include <linux/kernel.h>
++#include <linux/mm.h>
++#include <linux/pagemap.h>
++#include <linux/refcount.h>
++#include <linux/sched.h>
++#include <linux/slab.h>
+#include <linux/zstd.h>
+#include "compression.h"
+
@@ -316,7 +316,8 @@
+
+static ZSTD_parameters zstd_get_btrfs_parameters(size_t src_len)
+{
-+ ZSTD_parameters params = ZSTD_getParams(ZSTD_BTRFS_DEFAULT_LEVEL, src_len, 0);
++ ZSTD_parameters params = ZSTD_getParams(ZSTD_BTRFS_DEFAULT_LEVEL,
++ src_len, 0);
+
+ if (params.cParams.windowLog > ZSTD_BTRFS_MAX_WINDOWLOG)
+ params.cParams.windowLog = ZSTD_BTRFS_MAX_WINDOWLOG;
diff --git a/contrib/linux-kernel/0004-squashfs-Add-zstd-support.patch b/contrib/linux-kernel/0004-squashfs-Add-zstd-support.patch
index 02bd107..36cdf71 100644
--- a/contrib/linux-kernel/0004-squashfs-Add-zstd-support.patch
+++ b/contrib/linux-kernel/0004-squashfs-Add-zstd-support.patch
@@ -1,7 +1,7 @@
-From 0cd63464d182bb9708f8b25f7da3dc8e5ec6b4fa Mon Sep 17 00:00:00 2001
-From: Nick Terrell <terrelln@fb.com>
+From 46bf8f6d30d6ddf2446c110f122482b5e5e16933 Mon Sep 17 00:00:00 2001
+From: Sean Purcell <me@seanp.xyz>
Date: Mon, 17 Jul 2017 17:08:59 -0700
-Subject: [PATCH v3 4/4] squashfs: Add zstd support
+Subject: [PATCH v5 4/5] squashfs: Add zstd support
Add zstd compression and decompression support to SquashFS. zstd is a
great fit for SquashFS because it can compress at ratios approaching xz,
@@ -42,16 +42,23 @@
zstd source repository: https://github.com/facebook/zstd
-Cc: Sean Purcell <me@seanp.xyz>
+Signed-off-by: Sean Purcell <me@seanp.xyz>
Signed-off-by: Nick Terrell <terrelln@fb.com>
---
+v3 -> v4:
+- Fix minor linter warnings
+
+v4 -> v5:
+- Fix ZSTD_DStream initialization code in squashfs
+- Fix patch documentation to reflect that Sean Purcell is the author
+
fs/squashfs/Kconfig | 14 +++++
fs/squashfs/Makefile | 1 +
fs/squashfs/decompressor.c | 7 +++
fs/squashfs/decompressor.h | 4 ++
fs/squashfs/squashfs_fs.h | 1 +
- fs/squashfs/zstd_wrapper.c | 150 +++++++++++++++++++++++++++++++++++++++++++++
- 6 files changed, 177 insertions(+)
+ fs/squashfs/zstd_wrapper.c | 151 +++++++++++++++++++++++++++++++++++++++++++++
+ 6 files changed, 178 insertions(+)
create mode 100644 fs/squashfs/zstd_wrapper.c
diff --git a/fs/squashfs/Kconfig b/fs/squashfs/Kconfig
@@ -140,10 +147,10 @@
__le32 s_magic;
diff --git a/fs/squashfs/zstd_wrapper.c b/fs/squashfs/zstd_wrapper.c
new file mode 100644
-index 0000000..8cb7c76
+index 0000000..eeaabf8
--- /dev/null
+++ b/fs/squashfs/zstd_wrapper.c
-@@ -0,0 +1,150 @@
+@@ -0,0 +1,151 @@
+/*
+ * Squashfs - a compressed read only filesystem for Linux
+ *
@@ -160,10 +167,6 @@
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
-+ * You should have received a copy of the GNU General Public License
-+ * along with this program; if not, write to the Free Software
-+ * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
-+ *
+ * zstd_wrapper.c
+ */
+
@@ -182,15 +185,18 @@
+struct workspace {
+ void *mem;
+ size_t mem_size;
++ size_t window_size;
+};
+
+static void *zstd_init(struct squashfs_sb_info *msblk, void *buff)
+{
+ struct workspace *wksp = kmalloc(sizeof(*wksp), GFP_KERNEL);
++
+ if (wksp == NULL)
+ goto failed;
-+ wksp->mem_size = ZSTD_DStreamWorkspaceBound(max_t(size_t,
-+ msblk->block_size, SQUASHFS_METADATA_SIZE));
++ wksp->window_size = max_t(size_t,
++ msblk->block_size, SQUASHFS_METADATA_SIZE);
++ wksp->mem_size = ZSTD_DStreamWorkspaceBound(wksp->window_size);
+ wksp->mem = vmalloc(wksp->mem_size);
+ if (wksp->mem == NULL)
+ goto failed;
@@ -226,7 +232,7 @@
+ ZSTD_inBuffer in_buf = { NULL, 0, 0 };
+ ZSTD_outBuffer out_buf = { NULL, 0, 0 };
+
-+ stream = ZSTD_initDStream(wksp->mem_size, wksp->mem, wksp->mem_size);
++ stream = ZSTD_initDStream(wksp->window_size, wksp->mem, wksp->mem_size);
+
+ if (!stream) {
+ ERROR("Failed to initialize zstd decompressor\n");
@@ -239,6 +245,7 @@
+ do {
+ if (in_buf.pos == in_buf.size && k < b) {
+ int avail = min(length, msblk->devblksize - offset);
++
+ length -= avail;
+ in_buf.src = bh[k]->b_data + offset;
+ in_buf.size = avail;
@@ -249,8 +256,9 @@
+ if (out_buf.pos == out_buf.size) {
+ out_buf.dst = squashfs_next_page(output);
+ if (out_buf.dst == NULL) {
-+ /* shouldn't run out of pages before stream is
-+ * done */
++ /* Shouldn't run out of pages
++ * before stream is done.
++ */
+ squashfs_finish_page(output);
+ goto out;
+ }
diff --git a/contrib/linux-kernel/0005-crypto-Add-zstd-support.patch b/contrib/linux-kernel/0005-crypto-Add-zstd-support.patch
new file mode 100644
index 0000000..971b063
--- /dev/null
+++ b/contrib/linux-kernel/0005-crypto-Add-zstd-support.patch
@@ -0,0 +1,424 @@
+From 308795a7713ca6fcd468b60fba9a2fca99cee6a0 Mon Sep 17 00:00:00 2001
+From: Nick Terrell <terrelln@fb.com>
+Date: Wed, 2 Aug 2017 18:02:13 -0700
+Subject: [PATCH v5 5/5] crypto: Add zstd support
+
+Adds zstd support to crypto and scompress. Only supports the default
+level.
+
+Signed-off-by: Nick Terrell <terrelln@fb.com>
+---
+ crypto/Kconfig | 9 ++
+ crypto/Makefile | 1 +
+ crypto/testmgr.c | 10 +++
+ crypto/testmgr.h | 71 +++++++++++++++
+ crypto/zstd.c | 265 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ 5 files changed, 356 insertions(+)
+ create mode 100644 crypto/zstd.c
+
+diff --git a/crypto/Kconfig b/crypto/Kconfig
+index caa770e..4fc3936 100644
+--- a/crypto/Kconfig
++++ b/crypto/Kconfig
+@@ -1662,6 +1662,15 @@ config CRYPTO_LZ4HC
+ help
+ This is the LZ4 high compression mode algorithm.
+
++config CRYPTO_ZSTD
++ tristate "Zstd compression algorithm"
++ select CRYPTO_ALGAPI
++ select CRYPTO_ACOMP2
++ select ZSTD_COMPRESS
++ select ZSTD_DECOMPRESS
++ help
++ This is the zstd algorithm.
++
+ comment "Random Number Generation"
+
+ config CRYPTO_ANSI_CPRNG
+diff --git a/crypto/Makefile b/crypto/Makefile
+index d41f033..b22e1e8 100644
+--- a/crypto/Makefile
++++ b/crypto/Makefile
+@@ -133,6 +133,7 @@ obj-$(CONFIG_CRYPTO_USER_API_HASH) += algif_hash.o
+ obj-$(CONFIG_CRYPTO_USER_API_SKCIPHER) += algif_skcipher.o
+ obj-$(CONFIG_CRYPTO_USER_API_RNG) += algif_rng.o
+ obj-$(CONFIG_CRYPTO_USER_API_AEAD) += algif_aead.o
++obj-$(CONFIG_CRYPTO_ZSTD) += zstd.o
+
+ ecdh_generic-y := ecc.o
+ ecdh_generic-y += ecdh.o
+diff --git a/crypto/testmgr.c b/crypto/testmgr.c
+index 7125ba3..8a124d3 100644
+--- a/crypto/testmgr.c
++++ b/crypto/testmgr.c
+@@ -3603,6 +3603,16 @@ static const struct alg_test_desc alg_test_descs[] = {
+ .decomp = __VECS(zlib_deflate_decomp_tv_template)
+ }
+ }
++ }, {
++ .alg = "zstd",
++ .test = alg_test_comp,
++ .fips_allowed = 1,
++ .suite = {
++ .comp = {
++ .comp = __VECS(zstd_comp_tv_template),
++ .decomp = __VECS(zstd_decomp_tv_template)
++ }
++ }
+ }
+ };
+
+diff --git a/crypto/testmgr.h b/crypto/testmgr.h
+index 6ceb0e2..e6b5920 100644
+--- a/crypto/testmgr.h
++++ b/crypto/testmgr.h
+@@ -34631,4 +34631,75 @@ static const struct comp_testvec lz4hc_decomp_tv_template[] = {
+ },
+ };
+
++static const struct comp_testvec zstd_comp_tv_template[] = {
++ {
++ .inlen = 68,
++ .outlen = 39,
++ .input = "The algorithm is zstd. "
++ "The algorithm is zstd. "
++ "The algorithm is zstd.",
++ .output = "\x28\xb5\x2f\xfd\x00\x50\xf5\x00\x00\xb8\x54\x68\x65"
++ "\x20\x61\x6c\x67\x6f\x72\x69\x74\x68\x6d\x20\x69\x73"
++ "\x20\x7a\x73\x74\x64\x2e\x20\x01\x00\x55\x73\x36\x01"
++ ,
++ },
++ {
++ .inlen = 244,
++ .outlen = 151,
++ .input = "zstd, short for Zstandard, is a fast lossless "
++ "compression algorithm, targeting real-time "
++ "compression scenarios at zlib-level and better "
++ "compression ratios. The zstd compression library "
++ "provides in-memory compression and decompression "
++ "functions.",
++ .output = "\x28\xb5\x2f\xfd\x00\x50\x75\x04\x00\x42\x4b\x1e\x17"
++ "\x90\x81\x31\x00\xf2\x2f\xe4\x36\xc9\xef\x92\x88\x32"
++ "\xc9\xf2\x24\x94\xd8\x68\x9a\x0f\x00\x0c\xc4\x31\x6f"
++ "\x0d\x0c\x38\xac\x5c\x48\x03\xcd\x63\x67\xc0\xf3\xad"
++ "\x4e\x90\xaa\x78\xa0\xa4\xc5\x99\xda\x2f\xb6\x24\x60"
++ "\xe2\x79\x4b\xaa\xb6\x6b\x85\x0b\xc9\xc6\x04\x66\x86"
++ "\xe2\xcc\xe2\x25\x3f\x4f\x09\xcd\xb8\x9d\xdb\xc1\x90"
++ "\xa9\x11\xbc\x35\x44\x69\x2d\x9c\x64\x4f\x13\x31\x64"
++ "\xcc\xfb\x4d\x95\x93\x86\x7f\x33\x7f\x1a\xef\xe9\x30"
++ "\xf9\x67\xa1\x94\x0a\x69\x0f\x60\xcd\xc3\xab\x99\xdc"
++ "\x42\xed\x97\x05\x00\x33\xc3\x15\x95\x3a\x06\xa0\x0e"
++ "\x20\xa9\x0e\x82\xb9\x43\x45\x01",
++ },
++};
++
++static const struct comp_testvec zstd_decomp_tv_template[] = {
++ {
++ .inlen = 43,
++ .outlen = 68,
++ .input = "\x28\xb5\x2f\xfd\x04\x50\xf5\x00\x00\xb8\x54\x68\x65"
++ "\x20\x61\x6c\x67\x6f\x72\x69\x74\x68\x6d\x20\x69\x73"
++ "\x20\x7a\x73\x74\x64\x2e\x20\x01\x00\x55\x73\x36\x01"
++ "\x6b\xf4\x13\x35",
++ .output = "The algorithm is zstd. "
++ "The algorithm is zstd. "
++ "The algorithm is zstd.",
++ },
++ {
++ .inlen = 155,
++ .outlen = 244,
++ .input = "\x28\xb5\x2f\xfd\x04\x50\x75\x04\x00\x42\x4b\x1e\x17"
++ "\x90\x81\x31\x00\xf2\x2f\xe4\x36\xc9\xef\x92\x88\x32"
++ "\xc9\xf2\x24\x94\xd8\x68\x9a\x0f\x00\x0c\xc4\x31\x6f"
++ "\x0d\x0c\x38\xac\x5c\x48\x03\xcd\x63\x67\xc0\xf3\xad"
++ "\x4e\x90\xaa\x78\xa0\xa4\xc5\x99\xda\x2f\xb6\x24\x60"
++ "\xe2\x79\x4b\xaa\xb6\x6b\x85\x0b\xc9\xc6\x04\x66\x86"
++ "\xe2\xcc\xe2\x25\x3f\x4f\x09\xcd\xb8\x9d\xdb\xc1\x90"
++ "\xa9\x11\xbc\x35\x44\x69\x2d\x9c\x64\x4f\x13\x31\x64"
++ "\xcc\xfb\x4d\x95\x93\x86\x7f\x33\x7f\x1a\xef\xe9\x30"
++ "\xf9\x67\xa1\x94\x0a\x69\x0f\x60\xcd\xc3\xab\x99\xdc"
++ "\x42\xed\x97\x05\x00\x33\xc3\x15\x95\x3a\x06\xa0\x0e"
++ "\x20\xa9\x0e\x82\xb9\x43\x45\x01\xaa\x6d\xda\x0d",
++ .output = "zstd, short for Zstandard, is a fast lossless "
++ "compression algorithm, targeting real-time "
++ "compression scenarios at zlib-level and better "
++ "compression ratios. The zstd compression library "
++ "provides in-memory compression and decompression "
++ "functions.",
++ },
++};
+ #endif /* _CRYPTO_TESTMGR_H */
+diff --git a/crypto/zstd.c b/crypto/zstd.c
+new file mode 100644
+index 0000000..9a76b3e
+--- /dev/null
++++ b/crypto/zstd.c
+@@ -0,0 +1,265 @@
++/*
++ * Cryptographic API.
++ *
++ * Copyright (c) 2017-present, Facebook, Inc.
++ *
++ * This program is free software; you can redistribute it and/or modify it
++ * under the terms of the GNU General Public License version 2 as published by
++ * the Free Software Foundation.
++ *
++ * This program is distributed in the hope that it will be useful, but WITHOUT
++ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
++ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
++ * more details.
++ */
++#include <linux/crypto.h>
++#include <linux/init.h>
++#include <linux/interrupt.h>
++#include <linux/mm.h>
++#include <linux/module.h>
++#include <linux/net.h>
++#include <linux/vmalloc.h>
++#include <linux/zstd.h>
++#include <crypto/internal/scompress.h>
++
++
++#define ZSTD_DEF_LEVEL 3
++
++struct zstd_ctx {
++ ZSTD_CCtx *cctx;
++ ZSTD_DCtx *dctx;
++ void *cwksp;
++ void *dwksp;
++};
++
++static ZSTD_parameters zstd_params(void)
++{
++ return ZSTD_getParams(ZSTD_DEF_LEVEL, 0, 0);
++}
++
++static int zstd_comp_init(struct zstd_ctx *ctx)
++{
++ int ret = 0;
++ const ZSTD_parameters params = zstd_params();
++ const size_t wksp_size = ZSTD_CCtxWorkspaceBound(params.cParams);
++
++ ctx->cwksp = vzalloc(wksp_size);
++ if (!ctx->cwksp) {
++ ret = -ENOMEM;
++ goto out;
++ }
++
++ ctx->cctx = ZSTD_initCCtx(ctx->cwksp, wksp_size);
++ if (!ctx->cctx) {
++ ret = -EINVAL;
++ goto out_free;
++ }
++out:
++ return ret;
++out_free:
++ vfree(ctx->cwksp);
++ goto out;
++}
++
++static int zstd_decomp_init(struct zstd_ctx *ctx)
++{
++ int ret = 0;
++ const size_t wksp_size = ZSTD_DCtxWorkspaceBound();
++
++ ctx->dwksp = vzalloc(wksp_size);
++ if (!ctx->dwksp) {
++ ret = -ENOMEM;
++ goto out;
++ }
++
++ ctx->dctx = ZSTD_initDCtx(ctx->dwksp, wksp_size);
++ if (!ctx->dctx) {
++ ret = -EINVAL;
++ goto out_free;
++ }
++out:
++ return ret;
++out_free:
++ vfree(ctx->dwksp);
++ goto out;
++}
++
++static void zstd_comp_exit(struct zstd_ctx *ctx)
++{
++ vfree(ctx->cwksp);
++ ctx->cwksp = NULL;
++ ctx->cctx = NULL;
++}
++
++static void zstd_decomp_exit(struct zstd_ctx *ctx)
++{
++ vfree(ctx->dwksp);
++ ctx->dwksp = NULL;
++ ctx->dctx = NULL;
++}
++
++static int __zstd_init(void *ctx)
++{
++ int ret;
++
++ ret = zstd_comp_init(ctx);
++ if (ret)
++ return ret;
++ ret = zstd_decomp_init(ctx);
++ if (ret)
++ zstd_comp_exit(ctx);
++ return ret;
++}
++
++static void *zstd_alloc_ctx(struct crypto_scomp *tfm)
++{
++ int ret;
++ struct zstd_ctx *ctx;
++
++ ctx = kzalloc(sizeof(*ctx), GFP_KERNEL);
++ if (!ctx)
++ return ERR_PTR(-ENOMEM);
++
++ ret = __zstd_init(ctx);
++ if (ret) {
++ kfree(ctx);
++ return ERR_PTR(ret);
++ }
++
++ return ctx;
++}
++
++static int zstd_init(struct crypto_tfm *tfm)
++{
++ struct zstd_ctx *ctx = crypto_tfm_ctx(tfm);
++
++ return __zstd_init(ctx);
++}
++
++static void __zstd_exit(void *ctx)
++{
++ zstd_comp_exit(ctx);
++ zstd_decomp_exit(ctx);
++}
++
++static void zstd_free_ctx(struct crypto_scomp *tfm, void *ctx)
++{
++ __zstd_exit(ctx);
++ kzfree(ctx);
++}
++
++static void zstd_exit(struct crypto_tfm *tfm)
++{
++ struct zstd_ctx *ctx = crypto_tfm_ctx(tfm);
++
++ __zstd_exit(ctx);
++}
++
++static int __zstd_compress(const u8 *src, unsigned int slen,
++ u8 *dst, unsigned int *dlen, void *ctx)
++{
++ size_t out_len;
++ struct zstd_ctx *zctx = ctx;
++ const ZSTD_parameters params = zstd_params();
++
++ out_len = ZSTD_compressCCtx(zctx->cctx, dst, *dlen, src, slen, params);
++ if (ZSTD_isError(out_len))
++ return -EINVAL;
++ *dlen = out_len;
++ return 0;
++}
++
++static int zstd_compress(struct crypto_tfm *tfm, const u8 *src,
++ unsigned int slen, u8 *dst, unsigned int *dlen)
++{
++ struct zstd_ctx *ctx = crypto_tfm_ctx(tfm);
++
++ return __zstd_compress(src, slen, dst, dlen, ctx);
++}
++
++static int zstd_scompress(struct crypto_scomp *tfm, const u8 *src,
++ unsigned int slen, u8 *dst, unsigned int *dlen,
++ void *ctx)
++{
++ return __zstd_compress(src, slen, dst, dlen, ctx);
++}
++
++static int __zstd_decompress(const u8 *src, unsigned int slen,
++ u8 *dst, unsigned int *dlen, void *ctx)
++{
++ size_t out_len;
++ struct zstd_ctx *zctx = ctx;
++
++ out_len = ZSTD_decompressDCtx(zctx->dctx, dst, *dlen, src, slen);
++ if (ZSTD_isError(out_len))
++ return -EINVAL;
++ *dlen = out_len;
++ return 0;
++}
++
++static int zstd_decompress(struct crypto_tfm *tfm, const u8 *src,
++ unsigned int slen, u8 *dst, unsigned int *dlen)
++{
++ struct zstd_ctx *ctx = crypto_tfm_ctx(tfm);
++
++ return __zstd_decompress(src, slen, dst, dlen, ctx);
++}
++
++static int zstd_sdecompress(struct crypto_scomp *tfm, const u8 *src,
++ unsigned int slen, u8 *dst, unsigned int *dlen,
++ void *ctx)
++{
++ return __zstd_decompress(src, slen, dst, dlen, ctx);
++}
++
++static struct crypto_alg alg = {
++ .cra_name = "zstd",
++ .cra_flags = CRYPTO_ALG_TYPE_COMPRESS,
++ .cra_ctxsize = sizeof(struct zstd_ctx),
++ .cra_module = THIS_MODULE,
++ .cra_init = zstd_init,
++ .cra_exit = zstd_exit,
++ .cra_u = { .compress = {
++ .coa_compress = zstd_compress,
++ .coa_decompress = zstd_decompress } }
++};
++
++static struct scomp_alg scomp = {
++ .alloc_ctx = zstd_alloc_ctx,
++ .free_ctx = zstd_free_ctx,
++ .compress = zstd_scompress,
++ .decompress = zstd_sdecompress,
++ .base = {
++ .cra_name = "zstd",
++ .cra_driver_name = "zstd-scomp",
++ .cra_module = THIS_MODULE,
++ }
++};
++
++static int __init zstd_mod_init(void)
++{
++ int ret;
++
++ ret = crypto_register_alg(&alg);
++ if (ret)
++ return ret;
++
++ ret = crypto_register_scomp(&scomp);
++ if (ret)
++ crypto_unregister_alg(&alg);
++
++ return ret;
++}
++
++static void __exit zstd_mod_fini(void)
++{
++ crypto_unregister_alg(&alg);
++ crypto_unregister_scomp(&scomp);
++}
++
++module_init(zstd_mod_init);
++module_exit(zstd_mod_fini);
++
++MODULE_LICENSE("GPL");
++MODULE_DESCRIPTION("Zstd Compression Algorithm");
++MODULE_ALIAS_CRYPTO("zstd");
+--
+2.9.3
diff --git a/contrib/linux-kernel/0006-squashfs-tools-Add-zstd-support.patch b/contrib/linux-kernel/0006-squashfs-tools-Add-zstd-support.patch
new file mode 100644
index 0000000..b38930f
--- /dev/null
+++ b/contrib/linux-kernel/0006-squashfs-tools-Add-zstd-support.patch
@@ -0,0 +1,418 @@
+From cc08b43a31fed1289c2027d5090999da569457f1 Mon Sep 17 00:00:00 2001
+From: Sean Purcell <me@seanp.xyz>
+Date: Thu, 3 Aug 2017 17:47:03 -0700
+Subject: [PATCH v5] squashfs-tools: Add zstd support
+
+This patch adds zstd support to squashfs-tools. It works with zstd
+versions >= 1.0.0. It was originally written by Sean Purcell.
+
+Signed-off-by: Sean Purcell <me@seanp.xyz>
+Signed-off-by: Nick Terrell <terrelln@fb.com>
+---
+v4 -> v5:
+- Fix patch documentation to reflect that Sean Purcell is the author
+- Don't strip trailing whitespace of unreleated code
+- Make zstd_display_options() static
+
+ squashfs-tools/Makefile | 21 ++++
+ squashfs-tools/compressor.c | 8 ++
+ squashfs-tools/squashfs_fs.h | 1 +
+ squashfs-tools/zstd_wrapper.c | 254 ++++++++++++++++++++++++++++++++++++++++++
+ squashfs-tools/zstd_wrapper.h | 48 ++++++++
+ 5 files changed, 332 insertions(+)
+ create mode 100644 squashfs-tools/zstd_wrapper.c
+ create mode 100644 squashfs-tools/zstd_wrapper.h
+
+diff --git a/squashfs-tools/Makefile b/squashfs-tools/Makefile
+index 52d2582..8e82e09 100644
+--- a/squashfs-tools/Makefile
++++ b/squashfs-tools/Makefile
+@@ -75,6 +75,19 @@ GZIP_SUPPORT = 1
+ #LZMA_SUPPORT = 1
+ #LZMA_DIR = ../../../../LZMA/lzma465
+
++
++########### Building ZSTD support ############
++#
++# The ZSTD library is supported
++# ZSTD homepage: http://zstd.net
++# ZSTD source repository: https://github.com/facebook/zstd
++#
++# To build configure the tools using cmake to build shared libraries,
++# install and uncomment
++# the ZSTD_SUPPORT line below.
++#
++#ZSTD_SUPPORT = 1
++
+ ######## Specifying default compression ########
+ #
+ # The next line specifies which compression algorithm is used by default
+@@ -177,6 +190,14 @@ LIBS += -llz4
+ COMPRESSORS += lz4
+ endif
+
++ifeq ($(ZSTD_SUPPORT),1)
++CFLAGS += -DZSTD_SUPPORT
++MKSQUASHFS_OBJS += zstd_wrapper.o
++UNSQUASHFS_OBJS += zstd_wrapper.o
++LIBS += -lzstd
++COMPRESSORS += zstd
++endif
++
+ ifeq ($(XATTR_SUPPORT),1)
+ ifeq ($(XATTR_DEFAULT),1)
+ CFLAGS += -DXATTR_SUPPORT -DXATTR_DEFAULT
+diff --git a/squashfs-tools/compressor.c b/squashfs-tools/compressor.c
+index 525e316..02b5e90 100644
+--- a/squashfs-tools/compressor.c
++++ b/squashfs-tools/compressor.c
+@@ -65,6 +65,13 @@ static struct compressor xz_comp_ops = {
+ extern struct compressor xz_comp_ops;
+ #endif
+
++#ifndef ZSTD_SUPPORT
++static struct compressor zstd_comp_ops = {
++ ZSTD_COMPRESSION, "zstd"
++};
++#else
++extern struct compressor zstd_comp_ops;
++#endif
+
+ static struct compressor unknown_comp_ops = {
+ 0, "unknown"
+@@ -77,6 +84,7 @@ struct compressor *compressor[] = {
+ &lzo_comp_ops,
+ &lz4_comp_ops,
+ &xz_comp_ops,
++ &zstd_comp_ops,
+ &unknown_comp_ops
+ };
+
+diff --git a/squashfs-tools/squashfs_fs.h b/squashfs-tools/squashfs_fs.h
+index 791fe12..afca918 100644
+--- a/squashfs-tools/squashfs_fs.h
++++ b/squashfs-tools/squashfs_fs.h
+@@ -277,6 +277,7 @@ typedef long long squashfs_inode;
+ #define LZO_COMPRESSION 3
+ #define XZ_COMPRESSION 4
+ #define LZ4_COMPRESSION 5
++#define ZSTD_COMPRESSION 6
+
+ struct squashfs_super_block {
+ unsigned int s_magic;
+diff --git a/squashfs-tools/zstd_wrapper.c b/squashfs-tools/zstd_wrapper.c
+new file mode 100644
+index 0000000..dcab75a
+--- /dev/null
++++ b/squashfs-tools/zstd_wrapper.c
+@@ -0,0 +1,254 @@
++/*
++ * Copyright (c) 2017
++ * Phillip Lougher <phillip@squashfs.org.uk>
++ *
++ * This program is free software; you can redistribute it and/or
++ * modify it under the terms of the GNU General Public License
++ * as published by the Free Software Foundation; either version 2,
++ * or (at your option) any later version.
++ *
++ * This program is distributed in the hope that it will be useful,
++ * but WITHOUT ANY WARRANTY; without even the implied warranty of
++ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
++ * GNU General Public License for more details.
++ *
++ * zstd_wrapper.c
++ *
++ * Support for ZSTD compression http://zstd.net
++ */
++
++#include <stdio.h>
++#include <string.h>
++#include <stdlib.h>
++#include <zstd.h>
++#include <zstd_errors.h>
++
++#include "squashfs_fs.h"
++#include "zstd_wrapper.h"
++#include "compressor.h"
++
++static int compression_level = ZSTD_DEFAULT_COMPRESSION_LEVEL;
++
++/*
++ * This function is called by the options parsing code in mksquashfs.c
++ * to parse any -X compressor option.
++ *
++ * This function returns:
++ * >=0 (number of additional args parsed) on success
++ * -1 if the option was unrecognised, or
++ * -2 if the option was recognised, but otherwise bad in
++ * some way (e.g. invalid parameter)
++ *
++ * Note: this function sets internal compressor state, but does not
++ * pass back the results of the parsing other than success/failure.
++ * The zstd_dump_options() function is called later to get the options in
++ * a format suitable for writing to the filesystem.
++ */
++static int zstd_options(char *argv[], int argc)
++{
++ if (strcmp(argv[0], "-Xcompression-level") == 0) {
++ if (argc < 2) {
++ fprintf(stderr, "zstd: -Xcompression-level missing "
++ "compression level\n");
++ fprintf(stderr, "zstd: -Xcompression-level it should "
++ "be 1 <= n <= %d\n", ZSTD_maxCLevel());
++ goto failed;
++ }
++
++ compression_level = atoi(argv[1]);
++ if (compression_level < 1 ||
++ compression_level > ZSTD_maxCLevel()) {
++ fprintf(stderr, "zstd: -Xcompression-level invalid, it "
++ "should be 1 <= n <= %d\n", ZSTD_maxCLevel());
++ goto failed;
++ }
++
++ return 1;
++ }
++
++ return -1;
++failed:
++ return -2;
++}
++
++/*
++ * This function is called by mksquashfs to dump the parsed
++ * compressor options in a format suitable for writing to the
++ * compressor options field in the filesystem (stored immediately
++ * after the superblock).
++ *
++ * This function returns a pointer to the compression options structure
++ * to be stored (and the size), or NULL if there are no compression
++ * options.
++ */
++static void *zstd_dump_options(int block_size, int *size)
++{
++ static struct zstd_comp_opts comp_opts;
++
++ /* don't return anything if the options are all default */
++ if (compression_level == ZSTD_DEFAULT_COMPRESSION_LEVEL)
++ return NULL;
++
++ comp_opts.compression_level = compression_level;
++
++ SQUASHFS_INSWAP_COMP_OPTS(&comp_opts);
++
++ *size = sizeof(comp_opts);
++ return &comp_opts;
++}
++
++/*
++ * This function is a helper specifically for the append mode of
++ * mksquashfs. Its purpose is to set the internal compressor state
++ * to the stored compressor options in the passed compressor options
++ * structure.
++ *
++ * In effect this function sets up the compressor options
++ * to the same state they were when the filesystem was originally
++ * generated, this is to ensure on appending, the compressor uses
++ * the same compression options that were used to generate the
++ * original filesystem.
++ *
++ * Note, even if there are no compressor options, this function is still
++ * called with an empty compressor structure (size == 0), to explicitly
++ * set the default options, this is to ensure any user supplied
++ * -X options on the appending mksquashfs command line are over-ridden.
++ *
++ * This function returns 0 on sucessful extraction of options, and -1 on error.
++ */
++static int zstd_extract_options(int block_size, void *buffer, int size)
++{
++ struct zstd_comp_opts *comp_opts = buffer;
++
++ if (size == 0) {
++ /* Set default values */
++ compression_level = ZSTD_DEFAULT_COMPRESSION_LEVEL;
++ return 0;
++ }
++
++ /* we expect a comp_opts structure of sufficient size to be present */
++ if (size < sizeof(*comp_opts))
++ goto failed;
++
++ SQUASHFS_INSWAP_COMP_OPTS(comp_opts);
++
++ if (comp_opts->compression_level < 1 ||
++ comp_opts->compression_level > ZSTD_maxCLevel()) {
++ fprintf(stderr, "zstd: bad compression level in compression "
++ "options structure\n");
++ goto failed;
++ }
++
++ compression_level = comp_opts->compression_level;
++
++ return 0;
++
++failed:
++ fprintf(stderr, "zstd: error reading stored compressor options from "
++ "filesystem!\n");
++
++ return -1;
++}
++
++static void zstd_display_options(void *buffer, int size)
++{
++ struct zstd_comp_opts *comp_opts = buffer;
++
++ /* we expect a comp_opts structure of sufficient size to be present */
++ if (size < sizeof(*comp_opts))
++ goto failed;
++
++ SQUASHFS_INSWAP_COMP_OPTS(comp_opts);
++
++ if (comp_opts->compression_level < 1 ||
++ comp_opts->compression_level > ZSTD_maxCLevel()) {
++ fprintf(stderr, "zstd: bad compression level in compression "
++ "options structure\n");
++ goto failed;
++ }
++
++ printf("\tcompression-level %d\n", comp_opts->compression_level);
++
++ return;
++
++failed:
++ fprintf(stderr, "zstd: error reading stored compressor options from "
++ "filesystem!\n");
++}
++
++/*
++ * This function is called by mksquashfs to initialise the
++ * compressor, before compress() is called.
++ *
++ * This function returns 0 on success, and -1 on error.
++ */
++static int zstd_init(void **strm, int block_size, int datablock)
++{
++ ZSTD_CCtx *cctx = ZSTD_createCCtx();
++
++ if (!cctx) {
++ fprintf(stderr, "zstd: failed to allocate compression "
++ "context!\n");
++ return -1;
++ }
++
++ *strm = cctx;
++ return 0;
++}
++
++static int zstd_compress(void *strm, void *dest, void *src, int size,
++ int block_size, int *error)
++{
++ const size_t res = ZSTD_compressCCtx((ZSTD_CCtx*)strm, dest, block_size,
++ src, size, compression_level);
++
++ if (ZSTD_isError(res)) {
++ /* FIXME:
++ * zstd does not expose stable error codes. The error enum may
++ * change between versions. Until upstream zstd stablizes the
++ * error codes, we have no way of knowing why the error occurs.
++ * zstd shouldn't fail to compress any input unless there isn't
++ * enough output space. We assume that is the cause and return
++ * the special error code for not enough output space.
++ */
++ return 0;
++ }
++
++ return (int)res;
++}
++
++static int zstd_uncompress(void *dest, void *src, int size, int outsize,
++ int *error)
++{
++ const size_t res = ZSTD_decompress(dest, outsize, src, size);
++
++ if (ZSTD_isError(res)) {
++ fprintf(stderr, "\t%d %d\n", outsize, size);
++
++ *error = (int)ZSTD_getErrorCode(res);
++ return -1;
++ }
++
++ return (int)res;
++}
++
++static void zstd_usage(void)
++{
++ fprintf(stderr, "\t -Xcompression-level <compression-level>\n");
++ fprintf(stderr, "\t\t<compression-level> should be 1 .. %d (default "
++ "%d)\n", ZSTD_maxCLevel(), ZSTD_DEFAULT_COMPRESSION_LEVEL);
++}
++
++struct compressor zstd_comp_ops = {
++ .init = zstd_init,
++ .compress = zstd_compress,
++ .uncompress = zstd_uncompress,
++ .options = zstd_options,
++ .dump_options = zstd_dump_options,
++ .extract_options = zstd_extract_options,
++ .display_options = zstd_display_options,
++ .usage = zstd_usage,
++ .id = ZSTD_COMPRESSION,
++ .name = "zstd",
++ .supported = 1
++};
+diff --git a/squashfs-tools/zstd_wrapper.h b/squashfs-tools/zstd_wrapper.h
+new file mode 100644
+index 0000000..4fbef0a
+--- /dev/null
++++ b/squashfs-tools/zstd_wrapper.h
+@@ -0,0 +1,48 @@
++#ifndef ZSTD_WRAPPER_H
++#define ZSTD_WRAPPER_H
++/*
++ * Squashfs
++ *
++ * Copyright (c) 2017
++ * Phillip Lougher <phillip@squashfs.org.uk>
++ *
++ * This program is free software; you can redistribute it and/or
++ * modify it under the terms of the GNU General Public License
++ * as published by the Free Software Foundation; either version 2,
++ * or (at your option) any later version.
++ *
++ * This program is distributed in the hope that it will be useful,
++ * but WITHOUT ANY WARRANTY; without even the implied warranty of
++ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
++ * GNU General Public License for more details.
++ *
++ * zstd_wrapper.h
++ *
++ */
++
++#ifndef linux
++#define __BYTE_ORDER BYTE_ORDER
++#define __BIG_ENDIAN BIG_ENDIAN
++#define __LITTLE_ENDIAN LITTLE_ENDIAN
++#else
++#include <endian.h>
++#endif
++
++#if __BYTE_ORDER == __BIG_ENDIAN
++extern unsigned int inswap_le16(unsigned short);
++extern unsigned int inswap_le32(unsigned int);
++
++#define SQUASHFS_INSWAP_COMP_OPTS(s) { \
++ (s)->compression_level = inswap_le32((s)->compression_level); \
++}
++#else
++#define SQUASHFS_INSWAP_COMP_OPTS(s)
++#endif
++
++/* Default compression */
++#define ZSTD_DEFAULT_COMPRESSION_LEVEL 15
++
++struct zstd_comp_opts {
++ int compression_level;
++};
++#endif
+--
+2.9.3
diff --git a/contrib/linux-kernel/README.md b/contrib/linux-kernel/README.md
index 1b58304..86552b8 100644
--- a/contrib/linux-kernel/README.md
+++ b/contrib/linux-kernel/README.md
@@ -1,7 +1,7 @@
# Linux Kernel Patch
There are four pieces, the `xxhash` kernel module, the `zstd_compress` and `zstd_decompress` kernel modules, the BtrFS patch, and the SquashFS patch.
-The patches are based off of the linux kernel master branch (version 4.10).
+The patches are based off of the linux kernel master branch.
## xxHash kernel module
@@ -42,7 +42,7 @@
Benchmarks run on a Ubuntu 14.04 with 2 cores and 4 GiB of RAM.
The VM is running on a Macbook Pro with a 3.1 GHz Intel Core i7 processor,
16 GB of ram, and a SSD.
-The kernel running was built from the master branch with the patch (version 4.10).
+The kernel running was built from the master branch with the patch.
The compression benchmark is copying 10 copies of the
unzipped [silesia corpus](http://mattmahoney.net/dc/silesia.html) into a BtrFS
@@ -69,14 +69,14 @@
* The patch is located in `squashfs.diff`
* Additionally `fs/squashfs/zstd_wrapper.c` is provided as a source for convenience.
-* The patch has been tested on a 4.10 kernel.
+* The patch has been tested on the master branch of the kernel.
### Benchmarks
Benchmarks run on a Ubuntu 14.04 with 2 cores and 4 GiB of RAM.
The VM is running on a Macbook Pro with a 3.1 GHz Intel Core i7 processor,
16 GB of ram, and a SSD.
-The kernel running was built from the master branch with the patch (version 4.10).
+The kernel running was built from the master branch with the patch.
The compression benchmark is the file tree from the SquashFS archive found in the
Ubuntu 16.10 desktop image (ubuntu-16.10-desktop-amd64.iso).
diff --git a/contrib/linux-kernel/fs/btrfs/zstd.c b/contrib/linux-kernel/fs/btrfs/zstd.c
index 1822068..607ce47 100644
--- a/contrib/linux-kernel/fs/btrfs/zstd.c
+++ b/contrib/linux-kernel/fs/btrfs/zstd.c
@@ -10,20 +10,16 @@
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
- *
- * You should have received a copy of the GNU General Public
- * License along with this program; if not, write to the
- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 021110-1307, USA.
*/
-#include <linux/kernel.h>
-#include <linux/slab.h>
-#include <linux/vmalloc.h>
-#include <linux/init.h>
-#include <linux/err.h>
-#include <linux/sched.h>
-#include <linux/pagemap.h>
#include <linux/bio.h>
+#include <linux/err.h>
+#include <linux/init.h>
+#include <linux/kernel.h>
+#include <linux/mm.h>
+#include <linux/pagemap.h>
+#include <linux/refcount.h>
+#include <linux/sched.h>
+#include <linux/slab.h>
#include <linux/zstd.h>
#include "compression.h"
@@ -33,7 +29,8 @@
static ZSTD_parameters zstd_get_btrfs_parameters(size_t src_len)
{
- ZSTD_parameters params = ZSTD_getParams(ZSTD_BTRFS_DEFAULT_LEVEL, src_len, 0);
+ ZSTD_parameters params = ZSTD_getParams(ZSTD_BTRFS_DEFAULT_LEVEL,
+ src_len, 0);
if (params.cParams.windowLog > ZSTD_BTRFS_MAX_WINDOWLOG)
params.cParams.windowLog = ZSTD_BTRFS_MAX_WINDOWLOG;
diff --git a/contrib/linux-kernel/fs/squashfs/zstd_wrapper.c b/contrib/linux-kernel/fs/squashfs/zstd_wrapper.c
index 8cb7c76..eeaabf8 100644
--- a/contrib/linux-kernel/fs/squashfs/zstd_wrapper.c
+++ b/contrib/linux-kernel/fs/squashfs/zstd_wrapper.c
@@ -14,10 +14,6 @@
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
* zstd_wrapper.c
*/
@@ -36,15 +32,18 @@
struct workspace {
void *mem;
size_t mem_size;
+ size_t window_size;
};
static void *zstd_init(struct squashfs_sb_info *msblk, void *buff)
{
struct workspace *wksp = kmalloc(sizeof(*wksp), GFP_KERNEL);
+
if (wksp == NULL)
goto failed;
- wksp->mem_size = ZSTD_DStreamWorkspaceBound(max_t(size_t,
- msblk->block_size, SQUASHFS_METADATA_SIZE));
+ wksp->window_size = max_t(size_t,
+ msblk->block_size, SQUASHFS_METADATA_SIZE);
+ wksp->mem_size = ZSTD_DStreamWorkspaceBound(wksp->window_size);
wksp->mem = vmalloc(wksp->mem_size);
if (wksp->mem == NULL)
goto failed;
@@ -80,7 +79,7 @@
ZSTD_inBuffer in_buf = { NULL, 0, 0 };
ZSTD_outBuffer out_buf = { NULL, 0, 0 };
- stream = ZSTD_initDStream(wksp->mem_size, wksp->mem, wksp->mem_size);
+ stream = ZSTD_initDStream(wksp->window_size, wksp->mem, wksp->mem_size);
if (!stream) {
ERROR("Failed to initialize zstd decompressor\n");
@@ -93,6 +92,7 @@
do {
if (in_buf.pos == in_buf.size && k < b) {
int avail = min(length, msblk->devblksize - offset);
+
length -= avail;
in_buf.src = bh[k]->b_data + offset;
in_buf.size = avail;
@@ -103,8 +103,9 @@
if (out_buf.pos == out_buf.size) {
out_buf.dst = squashfs_next_page(output);
if (out_buf.dst == NULL) {
- /* shouldn't run out of pages before stream is
- * done */
+ /* Shouldn't run out of pages
+ * before stream is done.
+ */
squashfs_finish_page(output);
goto out;
}
diff --git a/contrib/linux-kernel/lib/zstd/compress.c b/contrib/linux-kernel/lib/zstd/compress.c
index d60ab7d..f9166cf 100644
--- a/contrib/linux-kernel/lib/zstd/compress.c
+++ b/contrib/linux-kernel/lib/zstd/compress.c
@@ -583,7 +583,7 @@
mlCodeTable[seqStorePtr->longLengthPos] = MaxML;
}
-ZSTD_STATIC size_t ZSTD_compressSequences(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, size_t srcSize)
+ZSTD_STATIC size_t ZSTD_compressSequences_internal(ZSTD_CCtx *zc, void *dst, size_t dstCapacity)
{
const int longOffsets = zc->params.cParams.windowLog > STREAM_ACCUMULATOR_MIN;
const seqStore_t *seqStorePtr = &(zc->seqStore);
@@ -636,7 +636,7 @@
else
op[0] = 0xFF, ZSTD_writeLE16(op + 1, (U16)(nbSeq - LONGNBSEQ)), op += 3;
if (nbSeq == 0)
- goto _check_compressibility;
+ return op - ostart;
/* seqHead : flags for FSE encoding type */
seqHead = op++;
@@ -826,28 +826,33 @@
op += streamSize;
}
}
-
-/* check compressibility */
-_check_compressibility:
- {
- size_t const minGain = ZSTD_minGain(srcSize);
- size_t const maxCSize = srcSize - minGain;
- if ((size_t)(op - ostart) >= maxCSize) {
- zc->flagStaticHufTable = HUF_repeat_none;
- return 0;
- }
- }
-
- /* confirm repcodes */
- {
- int i;
- for (i = 0; i < ZSTD_REP_NUM; i++)
- zc->rep[i] = zc->repToConfirm[i];
- }
-
return op - ostart;
}
+ZSTD_STATIC size_t ZSTD_compressSequences(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, size_t srcSize)
+{
+ size_t const cSize = ZSTD_compressSequences_internal(zc, dst, dstCapacity);
+ size_t const minGain = ZSTD_minGain(srcSize);
+ size_t const maxCSize = srcSize - minGain;
+ /* If the srcSize <= dstCapacity, then there is enough space to write a
+ * raw uncompressed block. Since we ran out of space, the block must not
+ * be compressible, so fall back to a raw uncompressed block.
+ */
+ int const uncompressibleError = cSize == ERROR(dstSize_tooSmall) && srcSize <= dstCapacity;
+ int i;
+
+ if (ZSTD_isError(cSize) && !uncompressibleError)
+ return cSize;
+ if (cSize >= maxCSize || uncompressibleError) {
+ zc->flagStaticHufTable = HUF_repeat_none;
+ return 0;
+ }
+ /* confirm repcodes */
+ for (i = 0; i < ZSTD_REP_NUM; i++)
+ zc->rep[i] = zc->repToConfirm[i];
+ return cSize;
+}
+
/*! ZSTD_storeSeq() :
Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
`offsetCode` : distance to match, or 0 == repCode.
diff --git a/contrib/linux-kernel/lib/zstd/decompress.c b/contrib/linux-kernel/lib/zstd/decompress.c
index 62449ae..b178467 100644
--- a/contrib/linux-kernel/lib/zstd/decompress.c
+++ b/contrib/linux-kernel/lib/zstd/decompress.c
@@ -998,6 +998,8 @@
BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
+ seq.match = NULL;
+
return seq;
}
diff --git a/contrib/linux-kernel/lib/zstd/zstd_internal.h b/contrib/linux-kernel/lib/zstd/zstd_internal.h
index f0ba474..1a79fab 100644
--- a/contrib/linux-kernel/lib/zstd/zstd_internal.h
+++ b/contrib/linux-kernel/lib/zstd/zstd_internal.h
@@ -126,7 +126,7 @@
/*-*******************************************
* Shared functions to include for inlining
*********************************************/
-static void ZSTD_copy8(void *dst, const void *src) {
+ZSTD_STATIC void ZSTD_copy8(void *dst, const void *src) {
memcpy(dst, src, 8);
}
/*! ZSTD_wildcopy() :
@@ -134,8 +134,21 @@
#define WILDCOPY_OVERLENGTH 8
ZSTD_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)
{
- if (length > 0)
- memcpy(dst, src, length);
+ const BYTE* ip = (const BYTE*)src;
+ BYTE* op = (BYTE*)dst;
+ BYTE* const oend = op + length;
+ /* Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388.
+ * Avoid the bad case where the loop only runs once by handling the
+ * special case separately. This doesn't trigger the bug because it
+ * doesn't involve pointer/integer overflow.
+ */
+ if (length <= 8)
+ return ZSTD_copy8(dst, src);
+ do {
+ ZSTD_copy8(op, ip);
+ op += 8;
+ ip += 8;
+ } while (op < oend);
}
/*-*******************************************