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

[PATCH v7 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.

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.

v3 -> v4:
- Put zstd in its own module.
- Update commit messages.
- Use attribute unused.
- Rebase on top of RAID patchset.

v4 -> v5:
- Add change lists to the top of the commit messages.
- Add a header to zstd's moudle.c file.
- Clarify where zstd's dependencies are coming from.
- Add module.c to Makefile.util.def.
- Clarify some error logging.
- Explain why I changed lzo's include.

v5 -> v6:
- Formatting changes

v6 -> v7:
- 2 spaces for first indent, not 4.

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

 Makefile.util.def                    |   11 +-
 grub-core/Makefile.core.def          |   17 +-
 grub-core/fs/btrfs.c                 |  119 +-
 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/module.c          |   21 +
 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 +-
 26 files changed, 10556 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/module.c
 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 v7 2/2] btrfs: Add zstd support to grub btrfs

[Nick Terrell]

- Adds zstd support to the btrfs module.
- Adds a test case for btrfs zstd support.
- Changes top_srcdir to srcdir in the btrfs module's lzo include
  following comments from Daniel Kiper about the zstd include.

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>
Reviewed-by: Daniel Kiper <daniel.kiper@oracle.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.

v3 -> v4:
- Use attribute unused.

v4 -> v5:
- Add zstd's module.c to Makefile.util.def.
- Clarify some error logging.
- Explain why I changed lzo's include.

v5 -> v6:
- Formatting changes (no functional changes).

v6 -> v7:
- 2 spaces as first indent, not 4.

 Makefile.util.def            |  11 +++-
 grub-core/Makefile.core.def  |   2 +-
 grub-core/fs/btrfs.c         | 119 ++++++++++++++++++++++++++++++++++-
 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 9ae45f351..a0495a87f 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;
@@ -165,6 +165,15 @@ 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/module.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 829e7bb57..2d75c4daf 100644
--- a/grub-core/Makefile.core.def
+++ b/grub-core/Makefile.core.def
@@ -1291,7 +1291,7 @@ module = {
   common = fs/btrfs.c;
   common = lib/crc.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 cac9ef588..3d6d11ec5 100644
--- a/grub-core/fs/btrfs.c
+++ b/grub-core/fs/btrfs.c
@@ -17,6 +17,14 @@
  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  */

+/*
+ * Tell zstd to expose functions that aren't part of the stable API, which
+ * aren't safe to use when linking against a dynamic library. We vendor in a
+ * specific zstd version, so we know what we're getting. We need these unstable
+ * functions to provide our own allocator, which uses grub_malloc(), to zstd.
+ */
+#define ZSTD_STATIC_LINKING_ONLY
+
 #include <grub/err.h>
 #include <grub/file.h>
 #include <grub/mm.h>
@@ -27,6 +35,7 @@
 #include <grub/lib/crc.h>
 #include <grub/deflate.h>
 #include <minilzo.h>
+#include <zstd.h>
 #include <grub/i18n.h>
 #include <grub/btrfs.h>
 #include <grub/crypto.h>
@@ -47,6 +56,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];

@@ -217,6 +229,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

@@ -1216,6 +1229,96 @@ 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 __attribute__((unused)), size_t size)
+{
+  return grub_malloc (size);
+}
+
+static void grub_zstd_free (void *state __attribute__((unused)), void *address)
+{
+  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)
+	{
+	  grub_error (GRUB_ERR_OUT_OF_MEMORY, "failed allocate a zstd buffer");
+	  goto err;
+	}
+      otmpbuf = (char *) allocated;
+      otmpsize = ZSTD_BTRFS_MAX_INPUT;
+    }
+
+  /* Create the ZSTD_DCtx. */
+  dctx = ZSTD_createDCtx_advanced (grub_zstd_allocator ());
+  if (!dctx)
+    {
+      /* ZSTD_createDCtx_advanced() only fails if it is out of memory. */
+      grub_error (GRUB_ERR_OUT_OF_MEMORY, "failed to create a zstd context");
+      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)
@@ -1391,7 +1494,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",
@@ -1431,6 +1535,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;
@@ -1468,6 +1581,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 ef65fbc93..bc14a05ca 100644
--- a/tests/util/grub-fs-tester.in
+++ b/tests/util/grub-fs-tester.in
@@ -629,7 +629,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 v7 0/2] btrfs: Add zstd support to grub btrfs

[Daniel Kiper]

On Mon, Nov 19, 2018 at 11:20:06AM -0800, 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.

LGTM. I will apply both patches in a week or so.

Thank you for doing the work.

Daniel

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

[Nick Terrell]

> On Nov 19, 2018, at 12:34 PM, Daniel Kiper <dkiper@net-space.pl> wrote:
> 
> On Mon, Nov 19, 2018 at 11:20:06AM -0800, 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.
> 
> LGTM. I will apply both patches in a week or so.
> 
> Thank you for doing the work.
> 
> Daniel


Thanks for taking the time to review and merge the patches, and for
maintaining GRUB!

Nick

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

[Daniel Kiper]

On Tue, Nov 27, 2018 at 02:55:33AM +0000, Nick Terrell wrote:
> > On Nov 19, 2018, at 12:34 PM, Daniel Kiper <dkiper@net-space.pl> wrote:
> > On Mon, Nov 19, 2018 at 11:20:06AM -0800, 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.
> >
> > LGTM. I will apply both patches in a week or so.
> >
> > Thank you for doing the work.
> >
> > Daniel
>
>
> Thanks for taking the time to review and merge the patches, and for
> maintaining GRUB!

You are welcome!

Daniel