[PATCH v3 0/2] btrfs: Add zstd support to grub btrfs

[PATCH v3 0/2] btrfs: Add zstd support to grub btrfs

[Nick Terrell]

Hi all,

This patch set imports the upstream zstd library, adds zstd support to the
btrfs module, and adds a test case. I've also tested the patch set by storing
my boot partition in btrfs with and without zstd compression and rebooting.

The fist patch imports the files needed to support zstd decompression from
zstd-1.3.6 as-is. It is a very large patch. In case it doesn't make it,
I've included the commit hash and the script I used to download the files.

Upstream zstd commit hash: 4fa456d7f12f8b27bd3b2f5dfd4f46898cb31c24
Upstream zstd commit name: Merge pull request #1354 from facebook/dev

---
#!/bin/sh -e

curl -L -O https://github.com/facebook/zstd/releases/download/v1.3.6/zstd-1.3.6.tar.gz
curl -L -O https://github.com/facebook/zstd/releases/download/v1.3.6/zstd-1.3.6.tar.gz.sha256
sha256sum --check zstd-1.3.6.tar.gz.sha256
tar xzf zstd-1.3.6.tar.gz

SRC_LIB="zstd-1.3.6/lib"
DST_LIB="grub-core/lib/zstd"
rm -rf $DST_LIB
mkdir -p $DST_LIB
cp $SRC_LIB/zstd.h $DST_LIB/
cp $SRC_LIB/common/*.[hc] $DST_LIB/
cp $SRC_LIB/decompress/*.[hc] $DST_LIB/
rm $DST_LIB/{pool.[hc],threading.[hc]}
rm -rf zstd-1.3.6*
echo SUCCESS!
---

Best,
Nick Terrell

Changelog:

v1 -> v2:
- Switch to upstream zstd-1.3.6 and drop all the local patches.
- Fix comments from Daniel Kiper.

v2 -> v3:
- Remove an extra file accidentally included in the first patch.
- Use grub_error() to set grub_errno in grub_btrfs_zstd_decompress().
- Fix style and formatting comments.

Nick Terrell (2):
  Import upstream zstd-1.3.6
  btrfs: Add zstd support to grub btrfs

 Makefile.util.def                    |   10 +-
 grub-core/Makefile.core.def          |   10 +-
 grub-core/fs/btrfs.c                 |  112 +-
 grub-core/lib/zstd/bitstream.h       |  458 ++++
 grub-core/lib/zstd/compiler.h        |  133 ++
 grub-core/lib/zstd/cpu.h             |  215 ++
 grub-core/lib/zstd/debug.c           |   44 +
 grub-core/lib/zstd/debug.h           |  123 +
 grub-core/lib/zstd/entropy_common.c  |  236 ++
 grub-core/lib/zstd/error_private.c   |   48 +
 grub-core/lib/zstd/error_private.h   |   76 +
 grub-core/lib/zstd/fse.h             |  708 ++++++
 grub-core/lib/zstd/fse_decompress.c  |  309 +++
 grub-core/lib/zstd/huf.h             |  334 +++
 grub-core/lib/zstd/huf_decompress.c  | 1096 +++++++++
 grub-core/lib/zstd/mem.h             |  374 ++++
 grub-core/lib/zstd/xxhash.c          |  876 ++++++++
 grub-core/lib/zstd/xxhash.h          |  305 +++
 grub-core/lib/zstd/zstd.h            | 1516 +++++++++++++
 grub-core/lib/zstd/zstd_common.c     |   81 +
 grub-core/lib/zstd/zstd_decompress.c | 3108 ++++++++++++++++++++++++++
 grub-core/lib/zstd/zstd_errors.h     |   92 +
 grub-core/lib/zstd/zstd_internal.h   |  257 +++
 tests/btrfs_test.in                  |    1 +
 tests/util/grub-fs-tester.in         |    2 +-
 25 files changed, 10520 insertions(+), 4 deletions(-)
 create mode 100644 grub-core/lib/zstd/bitstream.h
 create mode 100644 grub-core/lib/zstd/compiler.h
 create mode 100644 grub-core/lib/zstd/cpu.h
 create mode 100644 grub-core/lib/zstd/debug.c
 create mode 100644 grub-core/lib/zstd/debug.h
 create mode 100644 grub-core/lib/zstd/entropy_common.c
 create mode 100644 grub-core/lib/zstd/error_private.c
 create mode 100644 grub-core/lib/zstd/error_private.h
 create mode 100644 grub-core/lib/zstd/fse.h
 create mode 100644 grub-core/lib/zstd/fse_decompress.c
 create mode 100644 grub-core/lib/zstd/huf.h
 create mode 100644 grub-core/lib/zstd/huf_decompress.c
 create mode 100644 grub-core/lib/zstd/mem.h
 create mode 100644 grub-core/lib/zstd/xxhash.c
 create mode 100644 grub-core/lib/zstd/xxhash.h
 create mode 100644 grub-core/lib/zstd/zstd.h
 create mode 100644 grub-core/lib/zstd/zstd_common.c
 create mode 100644 grub-core/lib/zstd/zstd_decompress.c
 create mode 100644 grub-core/lib/zstd/zstd_errors.h
 create mode 100644 grub-core/lib/zstd/zstd_internal.h

--
2.17.1

[PATCH v3 2/2] btrfs: Add zstd support to grub btrfs

[Nick Terrell]

Adds zstd support to the btrfs module.

Tested on Ubuntu-18.04 with a btrfs /boot partition with and without zstd
compression. A test case was also added to the test suite that fails before
the patch, and passes after.

Signed-off-by: Nick Terrell <terrelln@fb.com>
---
v1 -> v2:
- Fix comments from Daniel Kiper.

v2 -> v3:
- Use grub_error() to set grub_errno in grub_btrfs_zstd_decompress().
- Fix style and formatting comments.

 Makefile.util.def            |  10 +++-
 grub-core/Makefile.core.def  |  10 +++-
 grub-core/fs/btrfs.c         | 112 ++++++++++++++++++++++++++++++++++-
 tests/btrfs_test.in          |   1 +
 tests/util/grub-fs-tester.in |   2 +-
 5 files changed, 131 insertions(+), 4 deletions(-)

diff --git a/Makefile.util.def b/Makefile.util.def
index f9caccb97..27c5e9903 100644
--- a/Makefile.util.def
+++ b/Makefile.util.def
@@ -54,7 +54,7 @@ library = {
 library = {
   name = libgrubmods.a;
   cflags = '-fno-builtin -Wno-undef';
-  cppflags = '-I$(top_srcdir)/grub-core/lib/minilzo -I$(srcdir)/grub-core/lib/xzembed -DMINILZO_HAVE_CONFIG_H';
+  cppflags = '-I$(srcdir)/grub-core/lib/minilzo -I$(srcdir)/grub-core/lib/xzembed -I$(srcdir)/grub-core/lib/zstd -DMINILZO_HAVE_CONFIG_H';

   common_nodist = grub_script.tab.c;
   common_nodist = grub_script.yy.c;
@@ -164,6 +164,14 @@ library = {
   common = grub-core/lib/xzembed/xz_dec_bcj.c;
   common = grub-core/lib/xzembed/xz_dec_lzma2.c;
   common = grub-core/lib/xzembed/xz_dec_stream.c;
+  common = grub-core/lib/zstd/debug.c;
+  common = grub-core/lib/zstd/entropy_common.c;
+  common = grub-core/lib/zstd/error_private.c;
+  common = grub-core/lib/zstd/fse_decompress.c;
+  common = grub-core/lib/zstd/huf_decompress.c;
+  common = grub-core/lib/zstd/xxhash.c;
+  common = grub-core/lib/zstd/zstd_common.c;
+  common = grub-core/lib/zstd/zstd_decompress.c;
 };

 program = {
diff --git a/grub-core/Makefile.core.def b/grub-core/Makefile.core.def
index 2c1d62cee..f818f58bc 100644
--- a/grub-core/Makefile.core.def
+++ b/grub-core/Makefile.core.def
@@ -1265,8 +1265,16 @@ module = {
   name = btrfs;
   common = fs/btrfs.c;
   common = lib/crc.c;
+  common = lib/zstd/debug.c;
+  common = lib/zstd/entropy_common.c;
+  common = lib/zstd/error_private.c;
+  common = lib/zstd/fse_decompress.c;
+  common = lib/zstd/huf_decompress.c;
+  common = lib/zstd/xxhash.c;
+  common = lib/zstd/zstd_common.c;
+  common = lib/zstd/zstd_decompress.c;
   cflags = '$(CFLAGS_POSIX) -Wno-undef';
-  cppflags = '-I$(srcdir)/lib/posix_wrap -I$(srcdir)/lib/minilzo -DMINILZO_HAVE_CONFIG_H';
+  cppflags = '-I$(srcdir)/lib/posix_wrap -I$(srcdir)/lib/minilzo -I$(srcdir)/lib/zstd -DMINILZO_HAVE_CONFIG_H';
 };

 module = {
diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
index 4849c1ceb..c44fe8029 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -17,6 +17,8 @@
  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  */

+#define ZSTD_STATIC_LINKING_ONLY
+
 #include <grub/err.h>
 #include <grub/file.h>
 #include <grub/mm.h>
@@ -27,6 +29,7 @@
 #include <grub/lib/crc.h>
 #include <grub/deflate.h>
 #include <minilzo.h>
+#include <zstd.h>
 #include <grub/i18n.h>
 #include <grub/btrfs.h>

@@ -45,6 +48,9 @@ GRUB_MOD_LICENSE ("GPLv3+");
 #define GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE (GRUB_BTRFS_LZO_BLOCK_SIZE + \
 				     (GRUB_BTRFS_LZO_BLOCK_SIZE / 16) + 64 + 3)

+#define ZSTD_BTRFS_MAX_WINDOWLOG 17
+#define ZSTD_BTRFS_MAX_INPUT     (1 << ZSTD_BTRFS_MAX_WINDOWLOG)
+
 typedef grub_uint8_t grub_btrfs_checksum_t[0x20];
 typedef grub_uint16_t grub_btrfs_uuid_t[8];

@@ -212,6 +218,7 @@ struct grub_btrfs_extent_data
 #define GRUB_BTRFS_COMPRESSION_NONE 0
 #define GRUB_BTRFS_COMPRESSION_ZLIB 1
 #define GRUB_BTRFS_COMPRESSION_LZO  2
+#define GRUB_BTRFS_COMPRESSION_ZSTD 3

 #define GRUB_BTRFS_OBJECT_ID_CHUNK 0x100

@@ -912,6 +919,95 @@ grub_btrfs_read_inode (struct grub_btrfs_data *data,
   return grub_btrfs_read_logical (data, elemaddr, inode, sizeof (*inode), 0);
 }

+static void* grub_zstd_malloc (void* state, size_t size)
+{
+	(void)state;
+
+	return grub_malloc (size);
+}
+
+static void grub_zstd_free (void* state, void* address)
+{
+	(void)state;
+
+	return grub_free (address);
+}
+
+static ZSTD_customMem grub_zstd_allocator (void)
+{
+	ZSTD_customMem allocator;
+
+	allocator.customAlloc = &grub_zstd_malloc;
+	allocator.customFree = &grub_zstd_free;
+	allocator.opaque = NULL;
+
+	return allocator;
+}
+
+static grub_ssize_t
+grub_btrfs_zstd_decompress (char *ibuf, grub_size_t isize, grub_off_t off,
+			    char *obuf, grub_size_t osize)
+{
+	void *allocated = NULL;
+	char *otmpbuf = obuf;
+	grub_size_t otmpsize = osize;
+	ZSTD_DCtx *dctx = NULL;
+	grub_size_t zstd_ret;
+	grub_ssize_t ret = -1;
+
+	/*
+	 * Zstd will fail if it can't fit the entire output in the destination
+	 * buffer, so if osize isn't large enough, allocate a temporary buffer.
+	 */
+	if (otmpsize < ZSTD_BTRFS_MAX_INPUT) {
+		allocated = grub_malloc (ZSTD_BTRFS_MAX_INPUT);
+		if (!allocated) {
+			goto err;
+		}
+		otmpbuf = (char*)allocated;
+		otmpsize = ZSTD_BTRFS_MAX_INPUT;
+	}
+
+	/* Create the ZSTD_DCtx. */
+	dctx = ZSTD_createDCtx_advanced (grub_zstd_allocator ());
+	if (!dctx) {
+		grub_error (GRUB_ERR_OUT_OF_MEMORY, "zstd out of memory");
+		goto err;
+	}
+
+	/*
+	 * Get the real input size, there may be junk at the
+	 * end of the frame.
+	 */
+	isize = ZSTD_findFrameCompressedSize (ibuf, isize);
+	if (ZSTD_isError (isize)) {
+		grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
+			    "zstd data corrupted");
+		goto err;
+	}
+
+	/* Decompress and check for errors. */
+	zstd_ret = ZSTD_decompressDCtx (dctx, otmpbuf, otmpsize, ibuf, isize);
+	if (ZSTD_isError (zstd_ret)) {
+		grub_error (GRUB_ERR_BAD_COMPRESSED_DATA,
+			    "zstd data corrupted");
+		goto err;
+	}
+
+	/*
+	 * Move the requested data into the obuf. obuf may be equal
+	 * to otmpbuf, which is why grub_memmove() is required.
+	 */
+	grub_memmove (obuf, otmpbuf + off, osize);
+	ret = osize;
+
+err:
+	grub_free (allocated);
+	ZSTD_freeDCtx (dctx);
+
+	return ret;
+}
+
 static grub_ssize_t
 grub_btrfs_lzo_decompress(char *ibuf, grub_size_t isize, grub_off_t off,
 			  char *obuf, grub_size_t osize)
@@ -1087,7 +1183,8 @@ grub_btrfs_extent_read (struct grub_btrfs_data *data,

       if (data->extent->compression != GRUB_BTRFS_COMPRESSION_NONE
 	  && data->extent->compression != GRUB_BTRFS_COMPRESSION_ZLIB
-	  && data->extent->compression != GRUB_BTRFS_COMPRESSION_LZO)
+	  && data->extent->compression != GRUB_BTRFS_COMPRESSION_LZO
+	  && data->extent->compression != GRUB_BTRFS_COMPRESSION_ZSTD)
 	{
 	  grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
 		      "compression type 0x%x not supported",
@@ -1127,6 +1224,15 @@ grub_btrfs_extent_read (struct grub_btrfs_data *data,
 		  != (grub_ssize_t) csize)
 		return -1;
 	    }
+	  else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZSTD)
+	    {
+	      if (grub_btrfs_zstd_decompress(data->extent->inl, data->extsize -
+					     ((grub_uint8_t *) data->extent->inl
+					      - (grub_uint8_t *) data->extent),
+					     extoff, buf, csize)
+		  != (grub_ssize_t) csize)
+		return -1;
+	    }
 	  else
 	    grub_memcpy (buf, data->extent->inl + extoff, csize);
 	  break;
@@ -1164,6 +1270,10 @@ grub_btrfs_extent_read (struct grub_btrfs_data *data,
 		ret = grub_btrfs_lzo_decompress (tmp, zsize, extoff
 				    + grub_le_to_cpu64 (data->extent->offset),
 				    buf, csize);
+	      else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZSTD)
+		ret = grub_btrfs_zstd_decompress (tmp, zsize, extoff
+				    + grub_le_to_cpu64 (data->extent->offset),
+				    buf, csize);
 	      else
 		ret = -1;

diff --git a/tests/btrfs_test.in b/tests/btrfs_test.in
index 2b37ddd33..0c9bf3a68 100644
--- a/tests/btrfs_test.in
+++ b/tests/btrfs_test.in
@@ -18,6 +18,7 @@ fi
 "@builddir@/grub-fs-tester" btrfs
 "@builddir@/grub-fs-tester" btrfs_zlib
 "@builddir@/grub-fs-tester" btrfs_lzo
+"@builddir@/grub-fs-tester" btrfs_zstd
 "@builddir@/grub-fs-tester" btrfs_raid0
 "@builddir@/grub-fs-tester" btrfs_raid1
 "@builddir@/grub-fs-tester" btrfs_single
diff --git a/tests/util/grub-fs-tester.in b/tests/util/grub-fs-tester.in
index 15969d796..3470c89e3 100644
--- a/tests/util/grub-fs-tester.in
+++ b/tests/util/grub-fs-tester.in
@@ -626,7 +626,7 @@ for LOGSECSIZE in $(range "$MINLOGSECSIZE" "$MAXLOGSECSIZE" 1); do
 		    ;;
 		x"btrfs")
 		    "mkfs.btrfs" -s $SECSIZE -L "$FSLABEL" "${MOUNTDEVICE}" ;;
-		x"btrfs_zlib" | x"btrfs_lzo")
+		x"btrfs_zlib" | x"btrfs_lzo" | x"btrfs_zstd")
 		    "mkfs.btrfs" -s $SECSIZE -L "$FSLABEL" "${MOUNTDEVICE}"
 		    MOUNTOPTS="compress=${fs/btrfs_/},"
 		    MOUNTFS="btrfs"
--
2.17.1

Re: [PATCH v3 0/2] btrfs: Add zstd support to grub btrfs

[Paul Menzel]

Dear Nick,


Thank you very much for your patches.


Am 10.10.2018 um 01:21 schrieb Nick Terrell:

> This patch set imports the upstream zstd library, adds zstd support to the
> btrfs module, and adds a test case. I've also tested the patch set by storing
> my boot partition in btrfs with and without zstd compression and rebooting.
> 
> The fist patch imports the files needed to support zstd decompression from
> zstd-1.3.6 as-is. It is a very large patch. In case it doesn't make it,
> I've included the commit hash and the script I used to download the files.
> 
> Upstream zstd commit hash: 4fa456d7f12f8b27bd3b2f5dfd4f46898cb31c24
> Upstream zstd commit name: Merge pull request #1354 from facebook/dev
> 
> ---
> #!/bin/sh -e
> 
> curl -L -O https://github.com/facebook/zstd/releases/download/v1.3.6/zstd-1.3.6.tar.gz
> curl -L -O https://github.com/facebook/zstd/releases/download/v1.3.6/zstd-1.3.6.tar.gz.sha256
> sha256sum --check zstd-1.3.6.tar.gz.sha256
> tar xzf zstd-1.3.6.tar.gz
> 
> SRC_LIB="zstd-1.3.6/lib"
> DST_LIB="grub-core/lib/zstd"
> rm -rf $DST_LIB
> mkdir -p $DST_LIB
> cp $SRC_LIB/zstd.h $DST_LIB/
> cp $SRC_LIB/common/*.[hc] $DST_LIB/
> cp $SRC_LIB/decompress/*.[hc] $DST_LIB/
> rm $DST_LIB/{pool.[hc],threading.[hc]}
> rm -rf zstd-1.3.6*
> echo SUCCESS!
> ---

Sorry for being ignorant, but you explain, why the library needs to be 
imported and it is not enough to use that library as an external dependency?

Importing the library means, it has to be maintained in the GRUB 
repository, which will result in some maintenance burden.


Kind regards,

Paul

Re: [PATCH v3 0/2] btrfs: Add zstd support to grub btrfs

[Nick Terrell]

> On Oct 10, 2018, at 12:34 AM, Paul Menzel <pmenzel@molgen.mpg.de> wrote:
> 
> Sorry for being ignorant, but you explain, why the library needs to be imported and it is not enough to use that library as an external dependency?
> 
> Importing the library means, it has to be maintained in the GRUB repository, which will result in some maintenance burden.

I've imported zstd because thats the way the rest of the decompressors are imported.

We could potentially use libzstd as an external dependency, since its only dependency is libc
and GRUB provides the definitions of the libc functions that zstd needs to decompress
(memcpy, and memmove). Theres some other stuff in the library that requires libc functionality
that GRUB doesn't provide, but that isn't used during decompression. We strip those files
out in the import.

Let me know if you want me to switch to an external dependency.

Best,
Nick

Re: [PATCH v3 0/2] btrfs: Add zstd support to grub btrfs

[Paul Menzel]

Dear Nick,


Am 10.10.2018 um 22:28 schrieb Nick Terrell:

>> On Oct 10, 2018, at 12:34 AM, Paul Menzel wrote:
>> 
>> Sorry for being ignorant, but you explain, why the library needs to
>> be imported and it is not enough to use that library as an external
>> dependency?
>> 
>> Importing the library means, it has to be maintained in the GRUB
>> repository, which will result in some maintenance burden.
> 
> I've imported zstd because thats the way the rest of the
> decompressors are imported.
> 
> We could potentially use libzstd as an external dependency, since its
> only dependency is libc and GRUB provides the definitions of the libc
> functions that zstd needs to decompress (memcpy, and memmove). Theres
> some other stuff in the library that requires libc functionality that
> GRUB doesn't provide, but that isn't used during decompression. We
> strip those files out in the import.

Thank you for the explanation.

> Let me know if you want me to switch to an external dependency.

I cannot make that decision. The main developers and the distribution
folks should comment on that.


Kind regards,

Paul

Re: [PATCH v3 0/2] btrfs: Add zstd support to grub btrfs

[Daniel Kiper]

On Wed, Oct 10, 2018 at 08:28:27PM +0000, Nick Terrell wrote:
> > On Oct 10, 2018, at 12:34 AM, Paul Menzel <pmenzel@molgen.mpg.de> wrote:
> >
> > Sorry for being ignorant, but you explain, why the library needs to be imported and it is not enough to use that library as an external dependency?
> >
> > Importing the library means, it has to be maintained in the GRUB repository, which will result in some maintenance burden.
>
> I've imported zstd because thats the way the rest of the decompressors are imported.
>
> We could potentially use libzstd as an external dependency, since its only dependency is libc
> and GRUB provides the definitions of the libc functions that zstd needs to decompress
> (memcpy, and memmove). Theres some other stuff in the library that requires libc functionality
> that GRUB doesn't provide, but that isn't used during decompression. We strip those files
> out in the import.
>
> Let me know if you want me to switch to an external dependency.

I do not think it is possible. Or it can be at least difficult. Even if
it is possible it would require a major rework of GRUB build machine.
So, even if current solution is not perfect I would like to stick to it.
And zstd library integration is not very difficult. So, I do not think
it will add a lot of burden in the future.

Daniel

Re: [PATCH v3 1/2] Import upstream zstd-1.3.6

[Daniel Kiper]

On Tue, Oct 09, 2018 at 04:21:36PM -0700, Nick Terrell wrote:
> Import zstd-1.3.6 from upstream [1]. Only the files need for decompression
> are imported.
>
> I used the latest zstd release, which includes patches [2] to build cleanly
> in GRUB.
>
> Upstream zstd commit hash: 4fa456d7f12f8b27bd3b2f5dfd4f46898cb31c24
> Upstream zstd commit name: Merge pull request #1354 from facebook/dev
>
> I've included the script used to import zstd-1.3.6 below.
>
> [1] https://github.com/facebook/zstd/releases/tag/v1.3.6
> [2] https://github.com/facebook/zstd/pull/1344
>
> ---

I think that you should replace the dashes with something different
here. Otherwise "git am" may tear off the rest of commit message
starting from here.

> #!/bin/sh -e
>
> curl -L -O https://github.com/facebook/zstd/releases/download/v1.3.6/zstd-1.3.6.tar.gz
> curl -L -O https://github.com/facebook/zstd/releases/download/v1.3.6/zstd-1.3.6.tar.gz.sha256
> sha256sum --check zstd-1.3.6.tar.gz.sha256
> tar xzf zstd-1.3.6.tar.gz
>
> SRC_LIB="zstd-1.3.6/lib"
> DST_LIB="grub-core/lib/zstd"
> rm -rf $DST_LIB
> mkdir -p $DST_LIB
> cp $SRC_LIB/zstd.h $DST_LIB/
> cp $SRC_LIB/common/*.[hc] $DST_LIB/
> cp $SRC_LIB/decompress/*.[hc] $DST_LIB/
> rm $DST_LIB/{pool.[hc],threading.[hc]}
> rm -rf zstd-1.3.6*
> echo SUCCESS!
> ---

Ditto.

> Signed-off-by: Nick Terrell <terrelln@fb.com>

If you fix things above you can add
  Reviewed-by: Daniel Kiper <daniel.kiper@oracle.com>

Daniel

Re: [PATCH v3 2/2] btrfs: Add zstd support to grub btrfs

[Daniel Kiper]

On Tue, Oct 09, 2018 at 04:21:37PM -0700, Nick Terrell wrote:
> Adds zstd support to the btrfs module.
>
> Tested on Ubuntu-18.04 with a btrfs /boot partition with and without zstd
> compression. A test case was also added to the test suite that fails before
> the patch, and passes after.
>
> Signed-off-by: Nick Terrell <terrelln@fb.com>
> ---
> v1 -> v2:
> - Fix comments from Daniel Kiper.
>
> v2 -> v3:
> - Use grub_error() to set grub_errno in grub_btrfs_zstd_decompress().
> - Fix style and formatting comments.
>
>  Makefile.util.def            |  10 +++-
>  grub-core/Makefile.core.def  |  10 +++-
>  grub-core/fs/btrfs.c         | 112 ++++++++++++++++++++++++++++++++++-
>  tests/btrfs_test.in          |   1 +
>  tests/util/grub-fs-tester.in |   2 +-
>  5 files changed, 131 insertions(+), 4 deletions(-)
>
> diff --git a/Makefile.util.def b/Makefile.util.def
> index f9caccb97..27c5e9903 100644
> --- a/Makefile.util.def
> +++ b/Makefile.util.def
> @@ -54,7 +54,7 @@ library = {
>  library = {
>    name = libgrubmods.a;
>    cflags = '-fno-builtin -Wno-undef';
> -  cppflags = '-I$(top_srcdir)/grub-core/lib/minilzo -I$(srcdir)/grub-core/lib/xzembed -DMINILZO_HAVE_CONFIG_H';
> +  cppflags = '-I$(srcdir)/grub-core/lib/minilzo -I$(srcdir)/grub-core/lib/xzembed -I$(srcdir)/grub-core/lib/zstd -DMINILZO_HAVE_CONFIG_H';
>
>    common_nodist = grub_script.tab.c;
>    common_nodist = grub_script.yy.c;
> @@ -164,6 +164,14 @@ library = {
>    common = grub-core/lib/xzembed/xz_dec_bcj.c;
>    common = grub-core/lib/xzembed/xz_dec_lzma2.c;
>    common = grub-core/lib/xzembed/xz_dec_stream.c;
> +  common = grub-core/lib/zstd/debug.c;
> +  common = grub-core/lib/zstd/entropy_common.c;
> +  common = grub-core/lib/zstd/error_private.c;
> +  common = grub-core/lib/zstd/fse_decompress.c;
> +  common = grub-core/lib/zstd/huf_decompress.c;
> +  common = grub-core/lib/zstd/xxhash.c;
> +  common = grub-core/lib/zstd/zstd_common.c;
> +  common = grub-core/lib/zstd/zstd_decompress.c;
>  };
>
>  program = {
> diff --git a/grub-core/Makefile.core.def b/grub-core/Makefile.core.def
> index 2c1d62cee..f818f58bc 100644
> --- a/grub-core/Makefile.core.def
> +++ b/grub-core/Makefile.core.def
> @@ -1265,8 +1265,16 @@ module = {
>    name = btrfs;
>    common = fs/btrfs.c;
>    common = lib/crc.c;
> +  common = lib/zstd/debug.c;
> +  common = lib/zstd/entropy_common.c;
> +  common = lib/zstd/error_private.c;
> +  common = lib/zstd/fse_decompress.c;
> +  common = lib/zstd/huf_decompress.c;
> +  common = lib/zstd/xxhash.c;
> +  common = lib/zstd/zstd_common.c;
> +  common = lib/zstd/zstd_decompress.c;
>    cflags = '$(CFLAGS_POSIX) -Wno-undef';
> -  cppflags = '-I$(srcdir)/lib/posix_wrap -I$(srcdir)/lib/minilzo -DMINILZO_HAVE_CONFIG_H';
> +  cppflags = '-I$(srcdir)/lib/posix_wrap -I$(srcdir)/lib/minilzo -I$(srcdir)/lib/zstd -DMINILZO_HAVE_CONFIG_H';
>  };

Please do not embed zstd lib into btrfs module here.
I would like to see zstd lib as separate module if possible.

>  module = {
> diff --git a/grub-core/fs/btrfs.c b/grub-core/fs/btrfs.c
> index 4849c1ceb..c44fe8029 100644
> --- a/grub-core/fs/btrfs.c
> +++ b/grub-core/fs/btrfs.c
> @@ -17,6 +17,8 @@
>   *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
>   */
>
> +#define ZSTD_STATIC_LINKING_ONLY
> +
>  #include <grub/err.h>
>  #include <grub/file.h>
>  #include <grub/mm.h>
> @@ -27,6 +29,7 @@
>  #include <grub/lib/crc.h>
>  #include <grub/deflate.h>
>  #include <minilzo.h>
> +#include <zstd.h>
>  #include <grub/i18n.h>
>  #include <grub/btrfs.h>
>
> @@ -45,6 +48,9 @@ GRUB_MOD_LICENSE ("GPLv3+");
>  #define GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE (GRUB_BTRFS_LZO_BLOCK_SIZE + \
>  				     (GRUB_BTRFS_LZO_BLOCK_SIZE / 16) + 64 + 3)
>
> +#define ZSTD_BTRFS_MAX_WINDOWLOG 17
> +#define ZSTD_BTRFS_MAX_INPUT     (1 << ZSTD_BTRFS_MAX_WINDOWLOG)
> +
>  typedef grub_uint8_t grub_btrfs_checksum_t[0x20];
>  typedef grub_uint16_t grub_btrfs_uuid_t[8];
>
> @@ -212,6 +218,7 @@ struct grub_btrfs_extent_data
>  #define GRUB_BTRFS_COMPRESSION_NONE 0
>  #define GRUB_BTRFS_COMPRESSION_ZLIB 1
>  #define GRUB_BTRFS_COMPRESSION_LZO  2
> +#define GRUB_BTRFS_COMPRESSION_ZSTD 3
>
>  #define GRUB_BTRFS_OBJECT_ID_CHUNK 0x100
>
> @@ -912,6 +919,95 @@ grub_btrfs_read_inode (struct grub_btrfs_data *data,
>    return grub_btrfs_read_logical (data, elemaddr, inode, sizeof (*inode), 0);
>  }
>
> +static void* grub_zstd_malloc (void* state, size_t size)
> +{
> +	(void)state;

Please drop this and use "__attribute__ ((unused))" in function prototype.

> +	return grub_malloc (size);
> +}
> +
> +static void grub_zstd_free (void* state, void* address)
> +{
> +	(void)state;

Ditto.

> +	return grub_free (address);
> +}
> +
> +static ZSTD_customMem grub_zstd_allocator (void)
> +{
> +	ZSTD_customMem allocator;
> +
> +	allocator.customAlloc = &grub_zstd_malloc;
> +	allocator.customFree = &grub_zstd_free;
> +	allocator.opaque = NULL;
> +
> +	return allocator;
> +}
> +
> +static grub_ssize_t
> +grub_btrfs_zstd_decompress (char *ibuf, grub_size_t isize, grub_off_t off,
> +			    char *obuf, grub_size_t osize)
> +{
> +	void *allocated = NULL;
> +	char *otmpbuf = obuf;
> +	grub_size_t otmpsize = osize;
> +	ZSTD_DCtx *dctx = NULL;
> +	grub_size_t zstd_ret;
> +	grub_ssize_t ret = -1;
> +
> +	/*
> +	 * Zstd will fail if it can't fit the entire output in the destination
> +	 * buffer, so if osize isn't large enough, allocate a temporary buffer.
> +	 */
> +	if (otmpsize < ZSTD_BTRFS_MAX_INPUT) {
> +		allocated = grub_malloc (ZSTD_BTRFS_MAX_INPUT);
> +		if (!allocated) {

Hmmm... Should not we say something here? Like grub_error() call below?
It seems to me that failing silently is bad idea here.

> +			goto err;
> +		}
> +		otmpbuf = (char*)allocated;
> +		otmpsize = ZSTD_BTRFS_MAX_INPUT;
> +	}
> +
> +	/* Create the ZSTD_DCtx. */
> +	dctx = ZSTD_createDCtx_advanced (grub_zstd_allocator ());
> +	if (!dctx) {
> +		grub_error (GRUB_ERR_OUT_OF_MEMORY, "zstd out of memory");
> +		goto err;
> +	}

Daniel

Re: [PATCH v3 2/2] btrfs: Add zstd support to grub btrfs

[Nick Terrell]

> On Oct 11, 2018, at 10:55 AM, Daniel Kiper <dkiper@net-space.pl> wrote:
> 
> On Tue, Oct 09, 2018 at 04:21:37PM -0700, Nick Terrell wrote:
>> Adds zstd support to the btrfs module.
>> 
>> Tested on Ubuntu-18.04 with a btrfs /boot partition with and without zstd
>> compression. A test case was also added to the test suite that fails before
>> the patch, and passes after.
>> 
>> Signed-off-by: Nick Terrell <terrelln@fb.com>
>> ---
>> v1 -> v2:
>> - Fix comments from Daniel Kiper.
>> 
>> v2 -> v3:
>> - Use grub_error() to set grub_errno in grub_btrfs_zstd_decompress().
>> - Fix style and formatting comments.
>> 
>> Makefile.util.def            |  10 +++-
>> grub-core/Makefile.core.def  |  10 +++-
>> grub-core/fs/btrfs.c         | 112 ++++++++++++++++++++++++++++++++++-
>> tests/btrfs_test.in          |   1 +
>> tests/util/grub-fs-tester.in |   2 +-
>> 5 files changed, 131 insertions(+), 4 deletions(-)
>> 
>> diff --git a/Makefile.util.def b/Makefile.util.def
>> index f9caccb97..27c5e9903 100644
>> --- a/Makefile.util.def
>> +++ b/Makefile.util.def
>> @@ -54,7 +54,7 @@ library = {
>> library = {
>>   name = libgrubmods.a;
>>   cflags = '-fno-builtin -Wno-undef';
>> -  cppflags = '-I$(top_srcdir)/grub-core/lib/minilzo -I$(srcdir)/grub-core/lib/xzembed -DMINILZO_HAVE_CONFIG_H';
>> +  cppflags = '-I$(srcdir)/grub-core/lib/minilzo -I$(srcdir)/grub-core/lib/xzembed -I$(srcdir)/grub-core/lib/zstd -DMINILZO_HAVE_CONFIG_H';
>> 
>>   common_nodist = grub_script.tab.c;
>>   common_nodist = grub_script.yy.c;
>> @@ -164,6 +164,14 @@ library = {
>>   common = grub-core/lib/xzembed/xz_dec_bcj.c;
>>   common = grub-core/lib/xzembed/xz_dec_lzma2.c;
>>   common = grub-core/lib/xzembed/xz_dec_stream.c;
>> +  common = grub-core/lib/zstd/debug.c;
>> +  common = grub-core/lib/zstd/entropy_common.c;
>> +  common = grub-core/lib/zstd/error_private.c;
>> +  common = grub-core/lib/zstd/fse_decompress.c;
>> +  common = grub-core/lib/zstd/huf_decompress.c;
>> +  common = grub-core/lib/zstd/xxhash.c;
>> +  common = grub-core/lib/zstd/zstd_common.c;
>> +  common = grub-core/lib/zstd/zstd_decompress.c;
>> };
>> 
>> program = {
>> diff --git a/grub-core/Makefile.core.def b/grub-core/Makefile.core.def
>> index 2c1d62cee..f818f58bc 100644
>> --- a/grub-core/Makefile.core.def
>> +++ b/grub-core/Makefile.core.def
>> @@ -1265,8 +1265,16 @@ module = {
>>   name = btrfs;
>>   common = fs/btrfs.c;
>>   common = lib/crc.c;
>> +  common = lib/zstd/debug.c;
>> +  common = lib/zstd/entropy_common.c;
>> +  common = lib/zstd/error_private.c;
>> +  common = lib/zstd/fse_decompress.c;
>> +  common = lib/zstd/huf_decompress.c;
>> +  common = lib/zstd/xxhash.c;
>> +  common = lib/zstd/zstd_common.c;
>> +  common = lib/zstd/zstd_decompress.c;
>>   cflags = '$(CFLAGS_POSIX) -Wno-undef';
>> -  cppflags = '-I$(srcdir)/lib/posix_wrap -I$(srcdir)/lib/minilzo -DMINILZO_HAVE_CONFIG_H';
>> +  cppflags = '-I$(srcdir)/lib/posix_wrap -I$(srcdir)/lib/minilzo -I$(srcdir)/lib/zstd -DMINILZO_HAVE_CONFIG_H';
>> };
> 
> Please do not embed zstd lib into btrfs module here.
> I would like to see zstd lib as separate module if possible.

Sure, I'm not exactly sure how the build system works. I haven't been able to
find any documentation, if there is some can you point me to it? I think the zstd
module should look like:

module = {
  name = zstd;
  common = lib/zstd/debug.c;
  common = lib/zstd/entropy_common.c;
  common = lib/zstd/error_private.c;
  common = lib/zstd/fse_decompress.c;
  common = lib/zstd/huf_decompress.c;
  common = lib/zstd/xxhash.c;
  common = lib/zstd/zstd_common.c;
  common = lib/zstd/zstd_decompress.c;
  cflags = '$(CFLAGS_POSIX) -Wno-undef';
  cppflags = '-I$(srcdir)/lib/posix_wrap -I$(srcdir)/lib/zstd';
};

Then how do I add a dependency on it in btrfs?


>> +static grub_ssize_t
>> +grub_btrfs_zstd_decompress (char *ibuf, grub_size_t isize, grub_off_t off,
>> +			    char *obuf, grub_size_t osize)
>> +{
>> +	void *allocated = NULL;
>> +	char *otmpbuf = obuf;
>> +	grub_size_t otmpsize = osize;
>> +	ZSTD_DCtx *dctx = NULL;
>> +	grub_size_t zstd_ret;
>> +	grub_ssize_t ret = -1;
>> +
>> +	/*
>> +	 * Zstd will fail if it can't fit the entire output in the destination
>> +	 * buffer, so if osize isn't large enough, allocate a temporary buffer.
>> +	 */
>> +	if (otmpsize < ZSTD_BTRFS_MAX_INPUT) {
>> +		allocated = grub_malloc (ZSTD_BTRFS_MAX_INPUT);
>> +		if (!allocated) {
> 
> Hmmm... Should not we say something here? Like grub_error() call below?
> It seems to me that failing silently is bad idea here.

grub_malloc() already calls grub_error with the message "Out of memory".

Thanks,
Nick

Re: [PATCH v3 0/2] btrfs: Add zstd support to grub btrfs

[Daniel Kiper]

Hi Nick,

CC-ing Goffredo.

On Tue, Oct 09, 2018 at 04:21:35PM -0700, Nick Terrell wrote:
> Hi all,
>
> This patch set imports the upstream zstd library, adds zstd support to the
> btrfs module, and adds a test case. I've also tested the patch set by storing
> my boot partition in btrfs with and without zstd compression and rebooting.
>
> The fist patch imports the files needed to support zstd decompression from
> zstd-1.3.6 as-is. It is a very large patch. In case it doesn't make it,
> I've included the commit hash and the script I used to download the files.
>
> Upstream zstd commit hash: 4fa456d7f12f8b27bd3b2f5dfd4f46898cb31c24
> Upstream zstd commit name: Merge pull request #1354 from facebook/dev

In general I am happy with the patches. If everything is done what
I have asked for then I will get them. However, there is one problem.
Another big btrfs (RAID) patchset is lurking around for months. It is
almost ready. Goffredo, I am looking at you... So, I would like to take
RAID patchset first. If it is in the tree then I will ask you to rebase
zstd patchset on top of RAID patchset and I will take it. Nick, are you
OK with that?

Daniel

Re: [PATCH v3 0/2] btrfs: Add zstd support to grub btrfs

[Nick Terrell]

> On Oct 11, 2018, at 11:15 AM, Daniel Kiper <dkiper@net-space.pl> wrote:
> 
> Hi Nick,
> 
> CC-ing Goffredo.
> 
> On Tue, Oct 09, 2018 at 04:21:35PM -0700, Nick Terrell wrote:
>> Hi all,
>> 
>> This patch set imports the upstream zstd library, adds zstd support to the
>> btrfs module, and adds a test case. I've also tested the patch set by storing
>> my boot partition in btrfs with and without zstd compression and rebooting.
>> 
>> The fist patch imports the files needed to support zstd decompression from
>> zstd-1.3.6 as-is. It is a very large patch. In case it doesn't make it,
>> I've included the commit hash and the script I used to download the files.
>> 
>> Upstream zstd commit hash: 4fa456d7f12f8b27bd3b2f5dfd4f46898cb31c24
>> Upstream zstd commit name: Merge pull request #1354 from facebook/dev
> 
> In general I am happy with the patches. If everything is done what
> I have asked for then I will get them. However, there is one problem.
> Another big btrfs (RAID) patchset is lurking around for months. It is
> almost ready. Goffredo, I am looking at you... So, I would like to take
> RAID patchset first. If it is in the tree then I will ask you to rebase
> zstd patchset on top of RAID patchset and I will take it. Nick, are you
> OK with that?

That works for me, thanks!

> Daniel