Skip to contentSkip to conversation

erofs-utils: add DEFLATE compression support

PATCH Superseded Gao Xiang 1 participant 7 messages Jul 10, 2023 – Jul 14, 2023 Library code

lore
Share & tools
lore

Gao Xiang

author
#0 lore raw

v3 cover erofs-utils: add DEFLATE compression support

Hi folks,

This is the EROFS DEFLATE support which I've been working on these months, mainly implementing DEFLATE fixed-sized output approach. Note that it's still some room to improve but I introduce it just to avoid external outdated zlib dependencies and the basic zlib encoder.

DEFLATE is a popular generic-purpose compression algorithm for a quite long time (many advanced formats like zlib, gzip, zip, png are all based on that), which is made of LZ77 as wells as Huffman code, fully documented as RFC1951 and quite easy to understand. DEFLATE encoder and decoder are also easy to be implemented and they generally have fairly small code size and runtime memory consumption.

In addition, there are several hardware on-market DEFLATE accelerators as well, such as (s390) DFLTCC, (Intel) IAA/QAT, (HiSilicon) ZIP accelerator, etc. Therefore, it's useful to support DEFLATE in order to use these for async I/Os and get benefits from these later.

As usual, some numbers of enwik8 and silesia.tar are available below:

Commandline option: -zdeflate,9 (to match mksquashfs default level) Sliding window size: 32768

enwik8:
____________________________

|  file system  |    size    |
|_______________|____________|
|___ enwik8 ____|_100000000__|
|_ squashfs_4k _|__46325760__|
|_ squashfs_8k _|__43618304__|
|__ erofs_4k ___|__43073536__| (erofs default)
| squashfs_16k _|__41406464__|
|__ erofs_8k ___|__40873984__|
|__ erofs_16k __|__38998016__|
| squashfs_64k _|__38109184__|
| squashfs_128k |__37306368__| (squashfs default)
|__ erofs_64k __|__37142528__|

silesia.tar (much similar to enwik8 so I omit some):
____________________________

|  file system  |    size    |
|_______________|____________|
|_ silesia.tar _|_211957760__|
|_ squashfs_4k _|__86884352__|
|_ squashfs_8k _|__81125376__|
|__ erofs_4k ___|__78970880__| (erofs default)
|__ erofs_8k ___|__74768384__|
| squashfs_64k _|__70447104__|
| squashfs_128k |__69079040__| (squashfs default)
|__ erofs_64k __|__68640768__|

Thanks,
Gao Xiang

changes since v2:
- add libdeflate compressor support by using the currect APIs.

Gao Xiang (4):
erofs-utils: add a built-in DEFLATE compressor
erofs-utils: fuse,fsck: add DEFLATE algorithm support
erofs-utils: mkfs: add DEFLATE algorithm support
erofs-utils: mkfs: add libdeflate compressor support

 configure.ac                |   46 ++
 dump/Makefile.am            |    2 +-
 fsck/Makefile.am            |    4 +-
 fuse/Makefile.am            |    2 +-
 include/erofs_fs.h          |    7 +
 lib/Makefile.am             |    5 +
 lib/compress.c              |   24 +
 lib/compressor.c            |    4 +
 lib/compressor.h            |    2 +
 lib/compressor_deflate.c    |   78 +++
 lib/compressor_libdeflate.c |  114 ++++
 lib/decompress.c            |  147 ++++
 lib/kite_deflate.c          | 1270 +++++++++++++++++++++++++++++++++++
 mkfs/Makefile.am            |    2 +-
 14 files changed, 1702 insertions(+), 5 deletions(-)
 create mode 100644 lib/compressor_deflate.c
 create mode 100644 lib/compressor_libdeflate.c
 create mode 100644 lib/kite_deflate.c
Signature · 1 line
2.24.4
author
#1 lore raw

PATCH v3 1/4 erofs-utils: add a built-in DEFLATE compressor

As Apple documentation written "If you require interoperability with non-Apple devices, use COMPRESSION_ZLIB. [1]", DEFLATE is a popular generic-purpose compression algorithm for a quite long time (many advanced formats like zlib, gzip, zip, png are all based on that), which is made of LZ77 as wells as Huffman code, fully documented as RFC1951 [2] and quite easy to understand, implement.

There are several hardware on-market DEFLATE accelerators as well, such as (s390) DFLTCC, (Intel) IAA/QAT, (HiSilicon) ZIP accelerator, etc. Therefore, it's useful to support DEFLATE compression in order to use these for async I/Os and get benefits from these.

Since there is _no fixed-sized output DEFLATE compression appoach_ available in public (fitblk is somewhat ineffective) and the original zlib is quite slowly developping, let's work out one for our use cases. Fortunately, it's only less than 1.5kLOC with lazy matching to just match the full zlib abilities. Besides, near-optimal block splitting (based on price function) doesn't support since it's no rush to us.

In the future, there might be more built-in optimizers landed to fulfill our needs even further (especially for other popular algorithms without native fixed-sized output support). In addition, I'd be quite happy to see more popular encoders to support native fixed-sized output compression too.

[1] https://developer.apple.com/documentation/compression/compression_algorithm
[2] https://datatracker.ietf.org/doc/html/rfc1951

---
 lib/Makefile.am    |    2 +
 lib/kite_deflate.c | 1270 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 1272 insertions(+)
 create mode 100644 lib/kite_deflate.c
lib/Makefile.am +2 -0
index e243c1c..b729098 100644
@@ -43,3 +43,5 @@ if ENABLE_LIBLZMA
 liberofs_la_CFLAGS += ${liblzma_CFLAGS}
 liberofs_la_SOURCES += compressor_liblzma.c
 endif
+
+liberofs_la_SOURCES += kite_deflate.c
lib/kite_deflate.c new file +1270 -0

1,270 lines not on this page · raw message

Signature · 1 line
2.24.4
author
#2 lore raw

PATCH v3 2/4 erofs-utils: fuse,fsck: add DEFLATE algorithm support

In reply to Gao Xiang

This patch adds DEFLATE compression algorithm support to erofsfuse by using zlib (by default) and libdeflate. libdeflate will be used instead of zlib if libdeflate is enabled.

---
 configure.ac       |  45 ++++++++++++++
 dump/Makefile.am   |   2 +-
 fsck/Makefile.am   |   4 +-
 fuse/Makefile.am   |   2 +-
 include/erofs_fs.h |   7 +++
 lib/decompress.c   | 147 +++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 203 insertions(+), 4 deletions(-)
configure.ac +45 -0
index 54608fb..d6dc7af 100644
@@ -122,6 +122,15 @@ AC_ARG_ENABLE(lzma,
    [AS_HELP_STRING([--enable-lzma], [enable LZMA compression support @<:@default=no@:>@])],
    [enable_lzma="$enableval"], [enable_lzma="no"])
 
+AC_ARG_WITH(zlib,
+   [AS_HELP_STRING([--without-zlib],
+      [Ignore presence of zlib inflate support @<:@default=enabled@:>@])])
+
+AC_ARG_WITH(libdeflate,
+   [AS_HELP_STRING([--with-libdeflate],
+      [Enable and build with libdeflate inflate support @<:@default=disabled@:>@])], [],
+      [with_libdeflate="no"])
+
 AC_ARG_ENABLE(fuse,
    [AS_HELP_STRING([--enable-fuse], [enable erofsfuse @<:@default=no@:>@])],
    [enable_fuse="$enableval"], [enable_fuse="no"])
@@ -395,6 +404,34 @@ if test "x$enable_lzma" = "xyes"; then
   CPPFLAGS="${saved_CPPFLAGS}"
 fi
 
+# Configure zlib
+AS_IF([test "x$with_zlib" != "xno"], [
+  PKG_CHECK_MODULES([zlib], [zlib])
+  # Paranoia: don't trust the result reported by pkgconfig before trying out
+  saved_LIBS="$LIBS"
+  saved_CPPFLAGS=${CPPFLAGS}
+  CPPFLAGS="${zlib_CFLAGS} ${CPPFLAGS}"
+  LIBS="${zlib_LIBS} $LIBS"
+  AC_CHECK_LIB(z, inflate, [
+    have_zlib="yes" ], [
+    AC_MSG_ERROR([zlib doesn't work properly])])
+  LIBS="${saved_LIBS}"
+  CPPFLAGS="${saved_CPPFLAGS}"], [have_zlib="no"])
+
+# Configure libdeflate
+AS_IF([test "x$with_libdeflate" != "xno"], [
+  PKG_CHECK_MODULES([libdeflate], [libdeflate])
+  # Paranoia: don't trust the result reported by pkgconfig before trying out
+  saved_LIBS="$LIBS"
+  saved_CPPFLAGS=${CPPFLAGS}
+  CPPFLAGS="${libdeflate_CFLAGS} ${CPPFLAGS}"
+  LIBS="${libdeflate_LIBS} $LIBS"
+  AC_CHECK_LIB(deflate, libdeflate_deflate_decompress, [
+    have_libdeflate="yes" ], [
+    AC_MSG_ERROR([libdeflate doesn't work properly])])
+  LIBS="${saved_LIBS}"
+  CPPFLAGS="${saved_CPPFLAGS}"], [have_libdeflate="no"])
+
 # Enable 64-bit off_t
 CFLAGS+=" -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64"
 
@@ -450,6 +487,14 @@ if test "x${have_liblzma}" = "xyes"; then
   AC_SUBST([liblzma_CFLAGS])
 fi
 
+if test "x$have_zlib" = "xyes"; then
+  AC_DEFINE([HAVE_ZLIB], 1, [Define to 1 if zlib is found])
+fi
+
+if test "x$have_libdeflate" = "xyes"; then
+  AC_DEFINE([HAVE_LIBDEFLATE], 1, [Define to 1 if libdeflate is found])
+fi
+
 # Dump maximum block size
 AS_IF([test "x$erofs_cv_max_block_size" = "x"],
       [$erofs_cv_max_block_size = 4096], [])
dump/Makefile.am +1 -1
index 90227a5..aed20c2 100644
@@ -7,4 +7,4 @@ AM_CPPFLAGS = ${libuuid_CFLAGS}
 dump_erofs_SOURCES = main.c
 dump_erofs_CFLAGS = -Wall -I$(top_srcdir)/include
 dump_erofs_LDADD = $(top_builddir)/lib/liberofs.la ${libselinux_LIBS} \
-	${liblz4_LIBS} ${liblzma_LIBS}
+	${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} ${libdeflate_LIBS}
fsck/Makefile.am +2 -2
index 369cb2f..d024405 100644
@@ -7,7 +7,7 @@ AM_CPPFLAGS = ${libuuid_CFLAGS}
 fsck_erofs_SOURCES = main.c
 fsck_erofs_CFLAGS = -Wall -I$(top_srcdir)/include
 fsck_erofs_LDADD = $(top_builddir)/lib/liberofs.la ${libselinux_LIBS} \
-	${liblz4_LIBS} ${liblzma_LIBS}
+	${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} ${libdeflate_LIBS}
 
 if ENABLE_FUZZING
 noinst_PROGRAMS   = fuzz_erofsfsck
@@ -15,5 +15,5 @@ fuzz_erofsfsck_SOURCES = main.c
 fuzz_erofsfsck_CFLAGS = -Wall -I$(top_srcdir)/include -DFUZZING
 fuzz_erofsfsck_LDFLAGS = -fsanitize=address,fuzzer
 fuzz_erofsfsck_LDADD = $(top_builddir)/lib/liberofs.la ${libselinux_LIBS} \
-	${liblz4_LIBS} ${liblzma_LIBS}
+	${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} ${libdeflate_LIBS}
 endif
fuse/Makefile.am +1 -1
index 3179a2b..50be783 100644
@@ -7,4 +7,4 @@ erofsfuse_SOURCES = main.c
 erofsfuse_CFLAGS = -Wall -I$(top_srcdir)/include
 erofsfuse_CFLAGS += -DFUSE_USE_VERSION=26 ${libfuse_CFLAGS} ${libselinux_CFLAGS}
 erofsfuse_LDADD = $(top_builddir)/lib/liberofs.la ${libfuse_LIBS} ${liblz4_LIBS} \
-	${libselinux_LIBS} ${liblzma_LIBS}
+	${libselinux_LIBS} ${liblzma_LIBS} ${zlib_LIBS} ${libdeflate_LIBS}
include/erofs_fs.h +7 -0
index 3697882..6b7b34f 100644
@@ -297,6 +297,7 @@ enum {
 enum {
 	Z_EROFS_COMPRESSION_LZ4		= 0,
 	Z_EROFS_COMPRESSION_LZMA	= 1,
+	Z_EROFS_COMPRESSION_DEFLATE	= 1,
 	Z_EROFS_COMPRESSION_MAX
 };
 #define Z_EROFS_ALL_COMPR_ALGS		((1 << Z_EROFS_COMPRESSION_MAX) - 1)
@@ -317,6 +318,12 @@ struct z_erofs_lzma_cfgs {
 
 #define Z_EROFS_LZMA_MAX_DICT_SIZE	(8 * Z_EROFS_PCLUSTER_MAX_SIZE)
 
+/* 6 bytes (+ length field = 8 bytes) */
+struct z_erofs_deflate_cfgs {
+	u8 windowbits;			/* 8..15 for DEFLATE */
+	u8 reserved[5];
+} __packed;
+
 /*
  * bit 0 : COMPACTED_2B indexes (0 - off; 1 - on)
  *  e.g. for 4k logical cluster size,      4B        if compacted 2B is off;
lib/decompress.c +147 -0

159 lines not on this page · raw message

Signature · 1 line
2.24.4
author
#3 lore raw

PATCH v4 2/4 erofs-utils: fuse,fsck: add DEFLATE algorithm support

This patch adds DEFLATE compression algorithm support to erofsfuse by using zlib (by default) and libdeflate. libdeflate will be used instead of zlib if libdeflate is enabled.

---
change since v3:
- fix improper Z_EROFS_COMPRESSION_DEFLATE number.

 configure.ac       |  45 ++++++++++++++
 dump/Makefile.am   |   2 +-
 fsck/Makefile.am   |   4 +-
 fuse/Makefile.am   |   2 +-
 include/erofs_fs.h |   7 +++
 lib/decompress.c   | 147 +++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 203 insertions(+), 4 deletions(-)
configure.ac +45 -0
index 54608fb..d6dc7af 100644
@@ -122,6 +122,15 @@ AC_ARG_ENABLE(lzma,
    [AS_HELP_STRING([--enable-lzma], [enable LZMA compression support @<:@default=no@:>@])],
    [enable_lzma="$enableval"], [enable_lzma="no"])
 
+AC_ARG_WITH(zlib,
+   [AS_HELP_STRING([--without-zlib],
+      [Ignore presence of zlib inflate support @<:@default=enabled@:>@])])
+
+AC_ARG_WITH(libdeflate,
+   [AS_HELP_STRING([--with-libdeflate],
+      [Enable and build with libdeflate inflate support @<:@default=disabled@:>@])], [],
+      [with_libdeflate="no"])
+
 AC_ARG_ENABLE(fuse,
    [AS_HELP_STRING([--enable-fuse], [enable erofsfuse @<:@default=no@:>@])],
    [enable_fuse="$enableval"], [enable_fuse="no"])
@@ -395,6 +404,34 @@ if test "x$enable_lzma" = "xyes"; then
   CPPFLAGS="${saved_CPPFLAGS}"
 fi
 
+# Configure zlib
+AS_IF([test "x$with_zlib" != "xno"], [
+  PKG_CHECK_MODULES([zlib], [zlib])
+  # Paranoia: don't trust the result reported by pkgconfig before trying out
+  saved_LIBS="$LIBS"
+  saved_CPPFLAGS=${CPPFLAGS}
+  CPPFLAGS="${zlib_CFLAGS} ${CPPFLAGS}"
+  LIBS="${zlib_LIBS} $LIBS"
+  AC_CHECK_LIB(z, inflate, [
+    have_zlib="yes" ], [
+    AC_MSG_ERROR([zlib doesn't work properly])])
+  LIBS="${saved_LIBS}"
+  CPPFLAGS="${saved_CPPFLAGS}"], [have_zlib="no"])
+
+# Configure libdeflate
+AS_IF([test "x$with_libdeflate" != "xno"], [
+  PKG_CHECK_MODULES([libdeflate], [libdeflate])
+  # Paranoia: don't trust the result reported by pkgconfig before trying out
+  saved_LIBS="$LIBS"
+  saved_CPPFLAGS=${CPPFLAGS}
+  CPPFLAGS="${libdeflate_CFLAGS} ${CPPFLAGS}"
+  LIBS="${libdeflate_LIBS} $LIBS"
+  AC_CHECK_LIB(deflate, libdeflate_deflate_decompress, [
+    have_libdeflate="yes" ], [
+    AC_MSG_ERROR([libdeflate doesn't work properly])])
+  LIBS="${saved_LIBS}"
+  CPPFLAGS="${saved_CPPFLAGS}"], [have_libdeflate="no"])
+
 # Enable 64-bit off_t
 CFLAGS+=" -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64"
 
@@ -450,6 +487,14 @@ if test "x${have_liblzma}" = "xyes"; then
   AC_SUBST([liblzma_CFLAGS])
 fi
 
+if test "x$have_zlib" = "xyes"; then
+  AC_DEFINE([HAVE_ZLIB], 1, [Define to 1 if zlib is found])
+fi
+
+if test "x$have_libdeflate" = "xyes"; then
+  AC_DEFINE([HAVE_LIBDEFLATE], 1, [Define to 1 if libdeflate is found])
+fi
+
 # Dump maximum block size
 AS_IF([test "x$erofs_cv_max_block_size" = "x"],
       [$erofs_cv_max_block_size = 4096], [])
dump/Makefile.am +1 -1
index 90227a5..aed20c2 100644
@@ -7,4 +7,4 @@ AM_CPPFLAGS = ${libuuid_CFLAGS}
 dump_erofs_SOURCES = main.c
 dump_erofs_CFLAGS = -Wall -I$(top_srcdir)/include
 dump_erofs_LDADD = $(top_builddir)/lib/liberofs.la ${libselinux_LIBS} \
-	${liblz4_LIBS} ${liblzma_LIBS}
+	${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} ${libdeflate_LIBS}
fsck/Makefile.am +2 -2
index 369cb2f..d024405 100644
@@ -7,7 +7,7 @@ AM_CPPFLAGS = ${libuuid_CFLAGS}
 fsck_erofs_SOURCES = main.c
 fsck_erofs_CFLAGS = -Wall -I$(top_srcdir)/include
 fsck_erofs_LDADD = $(top_builddir)/lib/liberofs.la ${libselinux_LIBS} \
-	${liblz4_LIBS} ${liblzma_LIBS}
+	${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} ${libdeflate_LIBS}
 
 if ENABLE_FUZZING
 noinst_PROGRAMS   = fuzz_erofsfsck
@@ -15,5 +15,5 @@ fuzz_erofsfsck_SOURCES = main.c
 fuzz_erofsfsck_CFLAGS = -Wall -I$(top_srcdir)/include -DFUZZING
 fuzz_erofsfsck_LDFLAGS = -fsanitize=address,fuzzer
 fuzz_erofsfsck_LDADD = $(top_builddir)/lib/liberofs.la ${libselinux_LIBS} \
-	${liblz4_LIBS} ${liblzma_LIBS}
+	${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} ${libdeflate_LIBS}
 endif
fuse/Makefile.am +1 -1
index 3179a2b..50be783 100644
@@ -7,4 +7,4 @@ erofsfuse_SOURCES = main.c
 erofsfuse_CFLAGS = -Wall -I$(top_srcdir)/include
 erofsfuse_CFLAGS += -DFUSE_USE_VERSION=26 ${libfuse_CFLAGS} ${libselinux_CFLAGS}
 erofsfuse_LDADD = $(top_builddir)/lib/liberofs.la ${libfuse_LIBS} ${liblz4_LIBS} \
-	${libselinux_LIBS} ${liblzma_LIBS}
+	${libselinux_LIBS} ${liblzma_LIBS} ${zlib_LIBS} ${libdeflate_LIBS}
include/erofs_fs.h +7 -0
index 3697882..850438a 100644
@@ -297,6 +297,7 @@ enum {
 enum {
 	Z_EROFS_COMPRESSION_LZ4		= 0,
 	Z_EROFS_COMPRESSION_LZMA	= 1,
+	Z_EROFS_COMPRESSION_DEFLATE	= 2,
 	Z_EROFS_COMPRESSION_MAX
 };
 #define Z_EROFS_ALL_COMPR_ALGS		((1 << Z_EROFS_COMPRESSION_MAX) - 1)
@@ -317,6 +318,12 @@ struct z_erofs_lzma_cfgs {
 
 #define Z_EROFS_LZMA_MAX_DICT_SIZE	(8 * Z_EROFS_PCLUSTER_MAX_SIZE)
 
+/* 6 bytes (+ length field = 8 bytes) */
+struct z_erofs_deflate_cfgs {
+	u8 windowbits;			/* 8..15 for DEFLATE */
+	u8 reserved[5];
+} __packed;
+
 /*
  * bit 0 : COMPACTED_2B indexes (0 - off; 1 - on)
  *  e.g. for 4k logical cluster size,      4B        if compacted 2B is off;
lib/decompress.c +147 -0

159 lines not on this page · raw message

Signature · 1 line
2.24.4
author
#4 lore raw

PATCH v3 3/4 erofs-utils: mkfs: add DEFLATE algorithm support

In reply to Gao Xiang

This patch adds DEFLATE compression algorithm support to erofs-utils compression framework.

Note that windowbits (which indicates dictionary size) is recorded in the on-disk compression configuration. Since some accelerators (e.g. Intel IAA) don't have enough on-chip memory, compressed data generated with large windowbits (e.g. > 12 for the IAA accelerator) doesn't seem to be worked properly on those.

---
 lib/Makefile.am          |  2 +-
 lib/compress.c           | 24 +++++++++++++
 lib/compressor.c         |  1 +
 lib/compressor.h         |  1 +
 lib/compressor_deflate.c | 78 ++++++++++++++++++++++++++++++++++++++++
 5 files changed, 105 insertions(+), 1 deletion(-)
 create mode 100644 lib/compressor_deflate.c
lib/Makefile.am +1 -1
index b729098..ae19b74 100644
@@ -44,4 +44,4 @@ liberofs_la_CFLAGS += ${liblzma_CFLAGS}
 liberofs_la_SOURCES += compressor_liblzma.c
 endif
 
-liberofs_la_SOURCES += kite_deflate.c
+liberofs_la_SOURCES += kite_deflate.c compressor_deflate.c
lib/compress.c +24 -0
index 14d228f..318b8de 100644
@@ -1026,6 +1026,8 @@ static int erofs_get_compress_algorithm_id(const char *name)
 		return Z_EROFS_COMPRESSION_LZ4;
 	if (!strcmp(name, "lzma"))
 		return Z_EROFS_COMPRESSION_LZMA;
+	if (!strcmp(name, "deflate"))
+		return Z_EROFS_COMPRESSION_DEFLATE;
 	return -ENOTSUP;
 }
 
@@ -1080,6 +1082,28 @@ int z_erofs_build_compr_cfgs(struct erofs_buffer_head *sb_bh)
 		bh->op = &erofs_drop_directly_bhops;
 	}
 #endif
+	if (sbi.available_compr_algs & (1 << Z_EROFS_COMPRESSION_DEFLATE)) {
+		struct {
+			__le16 size;
+			struct z_erofs_deflate_cfgs z;
+		} __packed zalg = {
+			.size = cpu_to_le16(sizeof(struct z_erofs_deflate_cfgs)),
+			.z = {
+				.windowbits =
+					cpu_to_le32(ilog2(cfg.c_dict_size)),
+			}
+		};
+
+		bh = erofs_battach(bh, META, sizeof(zalg));
+		if (IS_ERR(bh)) {
+			DBG_BUGON(1);
+			return PTR_ERR(bh);
+		}
+		erofs_mapbh(bh->block);
+		ret = dev_write(&zalg, erofs_btell(bh, false),
+				sizeof(zalg));
+		bh->op = &erofs_drop_directly_bhops;
+	}
 	return ret;
 }
 
lib/compressor.c +1 -0
index 52eb761..ca4d364 100644
@@ -20,6 +20,7 @@ static const struct erofs_compressor *compressors[] = {
 #if HAVE_LIBLZMA
 		&erofs_compressor_lzma,
 #endif
+		&erofs_compressor_deflate,
 };
 
 int erofs_compress_destsize(const struct erofs_compress *c,
lib/compressor.h +1 -0
index cf063f1..c1eee20 100644
@@ -44,6 +44,7 @@ struct erofs_compress {
 extern const struct erofs_compressor erofs_compressor_lz4;
 extern const struct erofs_compressor erofs_compressor_lz4hc;
 extern const struct erofs_compressor erofs_compressor_lzma;
+extern const struct erofs_compressor erofs_compressor_deflate;
 
 int erofs_compress_destsize(const struct erofs_compress *c,
 			    const void *src, unsigned int *srcsize,
lib/compressor_deflate.c new file +78 -0

78 lines not on this page · raw message

Signature · 1 line
2.24.4
author
#5 lore raw

PATCH v3 4/4 erofs-utils: mkfs: add libdeflate compressor support

In reply to Gao Xiang

Eric suggests a "binary search + heuristics" way by using the current libdeflate APIs to generate fixed-sized output DEFLATE streams.

Compared to the previous built-in one, it will generate smaller images (which is expected since the built-in one is roughly just the original zlib replacement), yet the total compression time might be amplified a lot especially if some larger pclusters are used by users compared to the built-in one.

For example:

$ time mkfs.erofs -zdeflate,9 -C65536 enwik8.z enwik8
real    0m9.559s
user    0m9.453s
sys     0m0.069s
$ time mkfs.erofs -zlibdeflate,9 -C65536 enwik8.libdeflate.9.z enwik8
real    0m50.184s
user    0m50.082s
sys     0m0.074s
$ mkfs/mkfs.erofs -zlibdeflate,6 -C65536 enwik8.libdeflate.6.z enwik8
real    0m23.428s
user    0m23.329s
sys     0m0.067s

37175296 enwik8.libdeflate.6.z
37142528 enwik8.z
36835328 enwik8.libdeflate.9.z

Anyway, let's use the current APIs for users who needs smaller image sizes for now. Besides, EROFS also supports multiple per-file algorithms in one image, so it can be used for specific files as well.

---
 configure.ac                |   1 +
 lib/Makefile.am             |   3 +
 lib/compress.c              |   2 +-
 lib/compressor.c            |   3 +
 lib/compressor.h            |   1 +
 lib/compressor_libdeflate.c | 114 ++++++++++++++++++++++++++++++++++++
 mkfs/Makefile.am            |   2 +-
 7 files changed, 124 insertions(+), 2 deletions(-)
 create mode 100644 lib/compressor_libdeflate.c
configure.ac +1 -0
index d6dc7af..ac0b0ed 100644
@@ -450,6 +450,7 @@ AM_CONDITIONAL([ENABLE_LZ4], [test "x${have_lz4}" = "xyes"])
 AM_CONDITIONAL([ENABLE_LZ4HC], [test "x${have_lz4hc}" = "xyes"])
 AM_CONDITIONAL([ENABLE_FUSE], [test "x${have_fuse}" = "xyes"])
 AM_CONDITIONAL([ENABLE_LIBLZMA], [test "x${have_liblzma}" = "xyes"])
+AM_CONDITIONAL([ENABLE_LIBDEFLATE], [test "x${have_libdeflate}" = "xyes"])
 
 if test "x$have_uuid" = "xyes"; then
   AC_DEFINE([HAVE_LIBUUID], 1, [Define to 1 if libuuid is found])
lib/Makefile.am +3 -0
index ae19b74..694888e 100644
@@ -45,3 +45,6 @@ liberofs_la_SOURCES += compressor_liblzma.c
 endif
 
 liberofs_la_SOURCES += kite_deflate.c compressor_deflate.c
+if ENABLE_LIBDEFLATE
+liberofs_la_SOURCES += compressor_libdeflate.c
+endif
lib/compress.c +1 -1
index 318b8de..6fb63cb 100644
@@ -1026,7 +1026,7 @@ static int erofs_get_compress_algorithm_id(const char *name)
 		return Z_EROFS_COMPRESSION_LZ4;
 	if (!strcmp(name, "lzma"))
 		return Z_EROFS_COMPRESSION_LZMA;
-	if (!strcmp(name, "deflate"))
+	if (!strcmp(name, "deflate") || !strcmp(name, "libdeflate"))
 		return Z_EROFS_COMPRESSION_DEFLATE;
 	return -ENOTSUP;
 }
lib/compressor.c +3 -0
index ca4d364..f81db5b 100644
@@ -21,6 +21,9 @@ static const struct erofs_compressor *compressors[] = {
 		&erofs_compressor_lzma,
 #endif
 		&erofs_compressor_deflate,
+#if HAVE_LIBDEFLATE
+		&erofs_compressor_libdeflate,
+#endif
 };
 
 int erofs_compress_destsize(const struct erofs_compress *c,
lib/compressor.h +1 -0
index c1eee20..f699fe7 100644
@@ -45,6 +45,7 @@ extern const struct erofs_compressor erofs_compressor_lz4;
 extern const struct erofs_compressor erofs_compressor_lz4hc;
 extern const struct erofs_compressor erofs_compressor_lzma;
 extern const struct erofs_compressor erofs_compressor_deflate;
+extern const struct erofs_compressor erofs_compressor_libdeflate;
 
 int erofs_compress_destsize(const struct erofs_compress *c,
 			    const void *src, unsigned int *srcsize,
lib/compressor_libdeflate.c new file +114 -0

114 lines not on this page · raw message

mkfs/Makefile.am +1 -1
index a08dc53..603c2f3 100644
@@ -6,4 +6,4 @@ AM_CPPFLAGS = ${libselinux_CFLAGS}
 mkfs_erofs_SOURCES = main.c
 mkfs_erofs_CFLAGS = -Wall -I$(top_srcdir)/include
 mkfs_erofs_LDADD = $(top_builddir)/lib/liberofs.la ${libselinux_LIBS} \
-	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS}
+	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS} ${libdeflate_LIBS}
Signature · 1 line
2.24.4
author
#6 lore raw
In reply to Gao Xiang
Quoted 14 lines · Gao Xiang

Hi folks,

This is the EROFS DEFLATE support which I've been working on these months, mainly implementing DEFLATE fixed-sized output approach. Note that it's still some room to improve but I introduce it just to avoid external outdated zlib dependencies and the basic zlib encoder.

DEFLATE is a popular generic-purpose compression algorithm for a quite long time (many advanced formats like zlib, gzip, zip, png are all based on that), which is made of LZ77 as wells as Huffman code, fully documented as RFC1951 and quite easy to understand. DEFLATE encoder and decoder are also easy to be implemented and they generally have fairly small code size and runtime memory consumption.

Quoted 5 lines

In addition, there are several hardware on-market DEFLATE accelerators as well, such as (s390) DFLTCC, (Intel) IAA/QAT, (HiSilicon) ZIP accelerator, etc. Therefore, it's useful to support DEFLATE in order to use these for async I/Os and get benefits from these later.

I will apply this patchset since these patches work fine on my side and do incremental development if there are some further improvements.

Thanks,
Gao Xiang