Skip to contentSkip to conversation

erofs-utils: add DEFLATE compression support

PATCH Superseded Gao Xiang 2 participants 12 messages Jul 9, 2023 – Jul 10, 2023 Library code

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Gao Xiang

author
#0 lore raw

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.

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

Gao Xiang (4):
erofs-utils: switch to effective unaligned access
erofs-utils: add a built-in DEFLATE compressor
erofs-utils: fuse: add DEFLATE algorithm support
erofs-utils: mkfs: add DEFLATE algorithm support

 configure.ac             |   45 ++
 dump/Makefile.am         |    3 +-
 fsck/Makefile.am         |    6 +-
 fuse/Makefile.am         |    2 +-
 include/erofs/defs.h     |   24 +-
 include/erofs/internal.h |    2 -
 include/erofs_fs.h       |    7 +
 lib/Makefile.am          |    2 +
 lib/compress.c           |   24 +
 lib/compressor.c         |    1 +
 lib/compressor.h         |    1 +
 lib/compressor_deflate.c |   77 +++
 lib/decompress.c         |  147 +++++
 lib/dedupe.c             |   23 +-
 lib/kite_deflate.c       | 1267 ++++++++++++++++++++++++++++++++++++++
 15 files changed, 1618 insertions(+), 13 deletions(-)
 create mode 100644 lib/compressor_deflate.c
 create mode 100644 lib/kite_deflate.c
Signature · 1 line
2.24.4
author
#1 lore raw

PATCH 1/4 erofs-utils: switch to effective unaligned access

In order to prepare for LZ77 matchfinder. Note that erofs_memcmp2() is still not quite effective.

---
 include/erofs/defs.h     | 24 ++++++++++++++++++++++--
 include/erofs/internal.h |  2 --
 lib/dedupe.c             | 23 ++++++++++++++++++-----
 3 files changed, 40 insertions(+), 9 deletions(-)
include/erofs/defs.h +22 -2
index e5aa23c..44af557 100644
@@ -179,9 +179,29 @@ typedef int64_t         s64;
 #define __maybe_unused      __attribute__((__unused__))
 #endif
 
-static inline u32 get_unaligned_le32(const u8 *p)
+#define __packed __attribute__((__packed__))
+
+#define __get_unaligned_t(type, ptr) ({						\
+	const struct { type x; } __packed *__pptr = (typeof(__pptr))(ptr);	\
+	__pptr->x;								\
+})
+
+#define __put_unaligned_t(type, val, ptr) do {					\
+	struct { type x; } __packed *__pptr = (typeof(__pptr))(ptr);		\
+	__pptr->x = (val);							\
+} while (0)
+
+#define get_unaligned(ptr)	__get_unaligned_t(typeof(*(ptr)), (ptr))
+#define put_unaligned(val, ptr) __put_unaligned_t(typeof(*(ptr)), (val), (ptr))
+
+static inline u32 get_unaligned_le32(const void *p)
+{
+	return le32_to_cpu(__get_unaligned_t(__le32, p));
+}
+
+static inline void put_unaligned_le32(u32 val, void *p)
 {
-	return p[0] | p[1] << 8 | p[2] << 16 | p[3] << 24;
+	__put_unaligned_t(__le32, cpu_to_le32(val), p);
 }
 
 /**
include/erofs/internal.h +0 -2
index ab964d4..aad2115 100644
@@ -17,8 +17,6 @@ extern "C"
 
 typedef unsigned short umode_t;
 
-#define __packed __attribute__((__packed__))
-
 #include "erofs_fs.h"
 #include <fcntl.h>
 #include <sys/types.h> /* for off_t definition */
lib/dedupe.c +18 -5
index 0a69b8f..17da452 100644
@@ -11,12 +11,14 @@
 unsigned long erofs_memcmp2(const u8 *s1, const u8 *s2,
 			    unsigned long sz)
 {
+	const unsigned long *a1, *a2;
 	unsigned long n = sz;
 
-	if (sz >= sizeof(long) && ((long)s1 & (sizeof(long) - 1)) ==
-			((long)s2 & (sizeof(long) - 1))) {
-		const unsigned long *a1, *a2;
+	if (sz < sizeof(long))
+		goto out_bytes;
 
+	if (((long)s1 & (sizeof(long) - 1)) ==
+			((long)s2 & (sizeof(long) - 1))) {
 		while ((long)s1 & (sizeof(long) - 1)) {
 			if (*s1 != *s2)
 				break;
@@ -34,9 +36,20 @@ unsigned long erofs_memcmp2(const u8 *s1, const u8 *s2,
 			++a2;
 			sz -= sizeof(long);
 		}
-		s1 = (const u8 *)a1;
-		s2 = (const u8 *)a2;
+	} else {
+		a1 = (const unsigned long *)s1;
+		a2 = (const unsigned long *)s2;
+		do {
+			if (get_unaligned(a1) != get_unaligned(a2))
+				break;
+			++a1;
+			++a2;
+			sz -= sizeof(long);
+		} while (sz >= sizeof(long));
 	}
+	s1 = (const u8 *)a1;
+	s2 = (const u8 *)a2;
+out_bytes:
 	while (sz) {
 		if (*s1 != *s2)
 			break;
Signature · 1 line
2.24.4
author
#2 lore raw

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

In reply to Gao Xiang

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 match the basic zlib ability. Besides, near-optimal block splitting (based on price function) doesn't support for now since it's not rush for us.

In the future, there may be more built-in optimizers landed to fulfill our needs even further. In addition, I'd be quite happy to see more popular encoders to support 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 | 1267 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 1269 insertions(+)
 create mode 100644 lib/kite_deflate.c
lib/Makefile.am +2 -0
index faa7311..fa3b804 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 +1267 -0

1,267 lines not on this page · raw message

Signature · 1 line
2.24.4
#3 lore raw

Re: [PATCH 2/4] erofs-utils: add a built-in DEFLATE compressor

Hi Gao,

Quoted 12 lines · Gao Xiang

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 match the basic zlib ability. Besides, near-optimal block splitting (based on price function) doesn't support for now since it's not rush for us.

In the future, there may be more built-in optimizers landed to fulfill our needs even further. In addition, I'd be quite happy to see more popular encoders to support fixed-sized output compression too.

Quoted 8 lines

[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 | 1267 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 1269 insertions(+)
 create mode 100644 lib/kite_deflate.c

Have you considered simply running any standard compressor multiple times to find the maximum input size that compresses to less than or equal to the desired output size? It may sound too slow, but it can be made to do the search in a smart way (binary search + heuristics). Also, it would easily work with every compressor, and it would always produce the optimal input size.

I wrote a proof-of-concept patch that implements this idea in the benchmark program in libdeflate. It finds the optimal input size in about 8 attempts on average for a target output size of 4096, or about 13 for a target output size of 65536. Note, if an optimal solution is not needed, it could be sped up slightly by stopping when the output size is at, or just under (if desired), the target output size. Also keep in mind that any compression level can be used.

The full code I tested is currently at
https://github.com/ebiggers/libdeflate/tree/fixed-output-size, but below is the actual algorithm:

/*
* Compresses the largest prefix of 'in', with maximum size 'in_nbytes', whose
* compressed output is at most 'target_output_size' bytes. The compressed size
* is returned as the return value, and the uncompressed size is returned in
* *actual_in_nbytes_ret. The output buffer 'out' has size 'out_nbytes_avail',
* which should be at least 'target_output_size + 9'. 'tmpbuf' must be a buffer
* the same size as 'out'.
*/
static size_t
do_compress_withfixedoutputsize(struct compressor *c,
const u8 *in, size_t in_nbytes,
u8 *out, size_t out_nbytes_avail, size_t target_output_size,
size_t last_uncompressed_size,
u8 *tmpbuf,
size_t *actual_in_nbytes_ret)

{
	size_t l = 0; /* largest input that fits so far */
	size_t l_csize = 0;
	size_t r = in_nbytes + 1; /* smallest input that doesn't fit so far */
	size_t m;

	if (last_uncompressed_size)
		m = last_uncompressed_size * 15 / 16;
	else
		m = target_output_size * 4;
	for (;;) {
		size_t csize;

		m = MAX(m, l + 1);
		m = MIN(m, r - 1);

		csize = do_compress(c, in, m, tmpbuf, out_nbytes_avail);
		if (csize > 0 && csize <= target_output_size) {
			/* Fits */
			memcpy(out, tmpbuf, csize);
			l = m;
			l_csize = csize;
			if (r <= l + 1)
				break;
			/*
			 * Estimate needed input prefix size based on current
			 * compression ratio.
			 */
			m = (target_output_size * m) / csize;
		} else {
			/* Doesn't fit */
			r = m;
			if (r <= l + 1)
				break;
			m = (l + r) / 2;
		}
	}
	*actual_in_nbytes_ret = l;
	return l_csize;
}

What do you think?

- Eric

author
#4 lore raw

Re: [PATCH 2/4] erofs-utils: add a built-in DEFLATE compressor

Hi Eric,

Quoted 24 lines · Eric Biggers

Hi Gao,

Quoted 12 lines · Gao Xiang

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 match the basic zlib ability. Besides, near-optimal block splitting (based on price function) doesn't support for now since it's not rush for us.

In the future, there may be more built-in optimizers landed to fulfill our needs even further. In addition, I'd be quite happy to see more popular encoders to support fixed-sized output compression too.

Quoted 8 lines

[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 | 1267 ++++++++++++++++++++++++++++++++++++++++++++
  2 files changed, 1269 insertions(+)

create mode 100644 lib/kite_deflate.c

Quoted 3 lines

Have you considered simply running any standard compressor multiple times to find the maximum input size that compresses to less than or equal to the desired output size? It may sound too slow, but it can be made to do the search in a

Thanks for your interest and reply!

Actually I've tried several ways before (just like fitblk.c or binary search), but the compression ratios is sliently impacted and compression speed is really impacted (maybe we need to develop segment-splitted multi-threadded compression as well, and it's developping by a college student now but I'm not sure the progress.)

I think we could use this way first for the new Zstd support (if they don't have bandwidth to add a offical fixed-sized output approach), but considering deflate algorithm is quite easy for me to understand so at least I could have a simple built-in one to avoid external dependency (mainly considering zlib since it's quite outdated). Since EROFS is actually offline compression so the compressed data correctness can always be checked in advance before image release.

Also I have more ideas to optimize the last symbol from matchfinders (even lazy matching) for fixed-sized output approaches to get even better compression ratios (especially for smaller filesystem cluster like 4kb.)

Quoted 10 lines

smart way (binary search + heuristics). Also, it would easily work with every compressor, and it would always produce the optimal input size.

I wrote a proof-of-concept patch that implements this idea in the benchmark program in libdeflate. It finds the optimal input size in about 8 attempts on average for a target output size of 4096, or about 13 for a target output size of 65536. Note, if an optimal solution is not needed, it could be sped up slightly by stopping when the output size is at, or just under (if desired), the target output size. Also keep in mind that any compression level can be used.

Quoted 3 lines

The full code I tested is currently at
https://github.com/ebiggers/libdeflate/tree/fixed-output-size, but below is the actual algorithm:

If libdeflate officically supports this mode, I'm very happy to integrate libdeflate in this way as an alternative encoder (if you could merge this), and if the compression speed is improved, I could switch it to the default encoder then. In the other words, I really hope there could be an official deflate encoder to support this mode as well. Also I think the in-kernel zlib decompression is somewhat slow just due to some non-technical reasons, I might need to improve this eveutually but it's no rush for us compared to support DEFLATE format first as well.

Quoted 58 lines

/*
* Compresses the largest prefix of 'in', with maximum size 'in_nbytes', whose
* compressed output is at most 'target_output_size' bytes. The compressed size
* is returned as the return value, and the uncompressed size is returned in
* *actual_in_nbytes_ret. The output buffer 'out' has size 'out_nbytes_avail',
* which should be at least 'target_output_size + 9'. 'tmpbuf' must be a buffer
* the same size as 'out'.
*/
static size_t
do_compress_withfixedoutputsize(struct compressor *c,
const u8 *in, size_t in_nbytes,
u8 *out, size_t out_nbytes_avail, size_t target_output_size,
size_t last_uncompressed_size,
u8 *tmpbuf,
size_t *actual_in_nbytes_ret)

{
	size_t l = 0; /* largest input that fits so far */
	size_t l_csize = 0;
	size_t r = in_nbytes + 1; /* smallest input that doesn't fit so far */
	size_t m;

	if (last_uncompressed_size)
		m = last_uncompressed_size * 15 / 16;
	else
		m = target_output_size * 4;
	for (;;) {
		size_t csize;

		m = MAX(m, l + 1);
		m = MIN(m, r - 1);

		csize = do_compress(c, in, m, tmpbuf, out_nbytes_avail);
		if (csize > 0 && csize <= target_output_size) {
			/* Fits */
			memcpy(out, tmpbuf, csize);
			l = m;
			l_csize = csize;
			if (r <= l + 1)
				break;
			/*
			 * Estimate needed input prefix size based on current
			 * compression ratio.
			 */
			m = (target_output_size * m) / csize;
		} else {
			/* Doesn't fit */
			r = m;
			if (r <= l + 1)
				break;
			m = (l + r) / 2;
		}
	}
	*actual_in_nbytes_ret = l;
	return l_csize;
}
Quoted 1 line

What do you think?

Thank you for the time and your efforts, I much appreciate if it could be supported so I could add a alternative encoder for this.

Thanks,
Gao Xiang

Quoted 2 lines

- Eric

#5 lore raw

Re: [PATCH 2/4] erofs-utils: add a built-in DEFLATE compressor

Quoted 27 lines · Gao Xiang

Hi Eric,

Quoted 24 lines · Eric Biggers

Hi Gao,

Quoted 20 lines · Gao Xiang

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 match the basic zlib ability. Besides, near-optimal block splitting (based on price function) doesn't support for now since it's not rush for us.

In the future, there may be more built-in optimizers landed to fulfill our needs even further. In addition, I'd be quite happy to see more popular encoders to support 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 | 1267 ++++++++++++++++++++++++++++++++++++++++++++
  2 files changed, 1269 insertions(+)

create mode 100644 lib/kite_deflate.c

Quoted 8 lines
Quoted 3 lines

Have you considered simply running any standard compressor multiple times to find the maximum input size that compresses to less than or equal to the desired output size? It may sound too slow, but it can be made to do the search in a

Thanks for your interest and reply!

Actually I've tried several ways before (just like fitblk.c or binary search), but the compression ratios is sliently impacted

That's strange, since the method I suggested should improve the compression ratio.

Quoted 4 lines

and compression speed is really
impacted (maybe we need to develop segment-splitted multi-threadded compression as well, and it's developping by a college student now but I'm not sure the progress.)

I'm surprised that multi-threaded compression isn't something you have already!

Quoted 7 lines

I think we could use this way first for the new Zstd support (if they don't have bandwidth to add a offical fixed-sized output approach), but considering deflate algorithm is quite easy for me to understand so at least I could have a simple built-in one to avoid external dependency (mainly considering zlib since it's quite outdated). Since EROFS is actually offline compression so the compressed data correctness can always be checked in advance before image release.

Writing an optimized compressor, especially one that implements high compression levels, is very hard. Are you sure it's something you want to implement and maintain in erofs-utils?

Quoted 3 lines

Also I have more ideas to optimize the last symbol from matchfinders (even lazy matching) for fixed-sized output approaches to get even better compression ratios (especially for smaller filesystem cluster like 4kb.)

Yes, there are some tricks that compressors that natively support fixed-size-output mode could use in order to avoid redundant work.

Quoted 81 lines
Quoted 10 lines

smart way (binary search + heuristics). Also, it would easily work with every compressor, and it would always produce the optimal input size.

I wrote a proof-of-concept patch that implements this idea in the benchmark program in libdeflate. It finds the optimal input size in about 8 attempts on average for a target output size of 4096, or about 13 for a target output size of 65536. Note, if an optimal solution is not needed, it could be sped up slightly by stopping when the output size is at, or just under (if desired), the target output size. Also keep in mind that any compression level can be used.

Quoted 3 lines

The full code I tested is currently at
https://github.com/ebiggers/libdeflate/tree/fixed-output-size, but below is the actual algorithm:

If libdeflate officically supports this mode, I'm very happy to integrate libdeflate in this way as an alternative encoder (if you could merge this), and if the compression speed is improved, I could switch it to the default encoder then. In the other words, I really hope there could be an official deflate encoder to support this mode as well. Also I think the in-kernel zlib decompression is somewhat slow just due to some non-technical reasons, I might need to improve this eveutually but it's no rush for us compared to support DEFLATE format first as well.

Quoted 58 lines

/*
* Compresses the largest prefix of 'in', with maximum size 'in_nbytes', whose
* compressed output is at most 'target_output_size' bytes. The compressed size
* is returned as the return value, and the uncompressed size is returned in
* *actual_in_nbytes_ret. The output buffer 'out' has size 'out_nbytes_avail',
* which should be at least 'target_output_size + 9'. 'tmpbuf' must be a buffer
* the same size as 'out'.
*/
static size_t
do_compress_withfixedoutputsize(struct compressor *c,
const u8 *in, size_t in_nbytes,
u8 *out, size_t out_nbytes_avail, size_t target_output_size,
size_t last_uncompressed_size,
u8 *tmpbuf,
size_t *actual_in_nbytes_ret)

{
	size_t l = 0; /* largest input that fits so far */
	size_t l_csize = 0;
	size_t r = in_nbytes + 1; /* smallest input that doesn't fit so far */
	size_t m;

	if (last_uncompressed_size)
		m = last_uncompressed_size * 15 / 16;
	else
		m = target_output_size * 4;
	for (;;) {
		size_t csize;

		m = MAX(m, l + 1);
		m = MIN(m, r - 1);

		csize = do_compress(c, in, m, tmpbuf, out_nbytes_avail);
		if (csize > 0 && csize <= target_output_size) {
			/* Fits */
			memcpy(out, tmpbuf, csize);
			l = m;
			l_csize = csize;
			if (r <= l + 1)
				break;
			/*
			 * Estimate needed input prefix size based on current
			 * compression ratio.
			 */
			m = (target_output_size * m) / csize;
		} else {
			/* Doesn't fit */
			r = m;
			if (r <= l + 1)
				break;
			m = (l + r) / 2;
		}
	}
	*actual_in_nbytes_ret = l;
	return l_csize;
}
Quoted 5 lines
Quoted 1 line

What do you think?

Thank you for the time and your efforts, I much appreciate if it could be supported so I could add a alternative encoder for this.

Native fixed-size-output size support in libdeflate is something I'll think about. However, the point I'm making is that it's unclear how valuable native fixed-size-output size support in compressors is, given that the search algorithm I described above actually seems to work fairly well, and it can produce the optimal solution.

Here's a quick proof of concept patch for mkfs.erofs:

lib/Makefile.am +1 -0
index 553b387..f58a684 100644
@@ -45,3 +45,4 @@ liberofs_la_SOURCES += compressor_liblzma.c
 endif
 
 liberofs_la_SOURCES += kite_deflate.c compressor_deflate.c
+liberofs_la_LDFLAGS = -ldeflate
lib/compressor_deflate.c +66 -2

121 lines not on this page · raw message

Here are some quick benchmarks I did of mkfs.erofs showing the size of the resulting filesystem and the time it took for mkfs.erofs to run:

-zdeflate,1

    kite_deflate: 10772480 bytes in 0.474s
    libdeflate: 10366976 bytes in 0.468s
-zdeflate,3
    kite_deflate: 10203136 bytes in 0.511s
    libdeflate: 10092544 bytes in 0.702s
-zdeflate,5
    kite_deflate: 10080256 bytes in 0.596s
    libdeflate: 9973760 bytes in 0.896s
-zdeflate,6
    kite_deflate: 9977856 bytes in 0.650s
    libdeflate: 9936896 bytes in 0.981s
-zdeflate,7
    kite_deflate: 9969664 bytes in 0.690s
    libdeflate: 9920512 bytes in 1.187s
-zdeflate,9
    kite_deflate: 9945088 bytes in 0.986s
    libdeflate: 9871360 bytes in 2.041s
-zdeflate,12
    kite_deflate: N/A
    libdeflate: 9740288 bytes in 28.080s

So it seems my "naive" search algorithm, when combined with libdeflate, actually does about as well as kite_deflate... Plus it automatically brings in support for higher compression levels.

- Eric

author
#6 lore raw

Re: [PATCH 2/4] erofs-utils: add a built-in DEFLATE compressor

Quoted 32 lines · Eric Biggers
Quoted 31 lines · Gao Xiang

Hi Eric,

Quoted 27 lines · Eric Biggers

Hi Gao,

Quoted 12 lines · Gao Xiang

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 match the basic zlib ability. Besides, near-optimal block splitting (based on price function) doesn't support for now since it's not rush for us.

In the future, there may be more built-in optimizers landed to fulfill our needs even further. In addition, I'd be quite happy to see more popular encoders to support fixed-sized output compression too.

Quoted 8 lines

[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 | 1267 ++++++++++++++++++++++++++++++++++++++++++++
   2 files changed, 1269 insertions(+)

create mode 100644 lib/kite_deflate.c

Have you considered simply running any standard compressor multiple times to find the maximum input size that compresses to less than or equal to the desired output size? It may sound too slow, but it can be made to do the search in a

Quoted 7 lines
Quoted 4 lines

Thanks for your interest and reply!

Actually I've tried several ways before (just like fitblk.c or binary search), but the compression ratios is sliently impacted

That's strange, since the method I suggested should improve the compression ratio.

It depends, the current kite_deflate approach is already better than zlib (no matter fitblk.c or binary search.) Compared to libdeflate, yes, it doesn't support optimal deflate block splitting and some advanced matchfinder other than hash chains so I'm afraid not.

This encoder is only used to replace zlib and I think we could integrate libdeflate like what you suggested first.

Quoted 7 lines
Quoted 5 lines

and compression speed is really
impacted (maybe we need to develop segment-splitted multi-threadded compression as well, and it's developping by a college student now but I'm not sure the progress.)

I'm surprised that multi-threaded compression isn't something you have already!

Because my own time is limited and no more volunteer for this, rolling-hash compressed data deduplication is more useful and natual to EROFS since EROFS has byte-granularity uncompressed offset/length indexes (kernel improvements always have higher priority than userspace stuffs since userspace stuffs can easily be bumpped with new released versions.)

Quoted 281 lines
Quoted 8 lines

I think we could use this way first for the new Zstd support (if they don't have bandwidth to add a offical fixed-sized output approach), but considering deflate algorithm is quite easy for me to understand so at least I could have a simple built-in one to avoid external dependency (mainly considering zlib since it's quite outdated). Since EROFS is actually offline compression so the compressed data correctness can always be checked in advance before image release.

Writing an optimized compressor, especially one that implements high compression levels, is very hard. Are you sure it's something you want to implement and maintain in erofs-utils?

Quoted 3 lines

Also I have more ideas to optimize the last symbol from matchfinders (even lazy matching) for fixed-sized output approaches to get even better compression ratios (especially for smaller filesystem cluster like 4kb.)

Yes, there are some tricks that compressors that natively support fixed-size-output mode could use in order to avoid redundant work.

Quoted 81 lines
Quoted 10 lines

smart way (binary search + heuristics). Also, it would easily work with every compressor, and it would always produce the optimal input size.

I wrote a proof-of-concept patch that implements this idea in the benchmark program in libdeflate. It finds the optimal input size in about 8 attempts on average for a target output size of 4096, or about 13 for a target output size of 65536. Note, if an optimal solution is not needed, it could be sped up slightly by stopping when the output size is at, or just under (if desired), the target output size. Also keep in mind that any compression level can be used.

Quoted 3 lines

The full code I tested is currently at
https://github.com/ebiggers/libdeflate/tree/fixed-output-size, but below is the actual algorithm:

If libdeflate officically supports this mode, I'm very happy to integrate libdeflate in this way as an alternative encoder (if you could merge this), and if the compression speed is improved, I could switch it to the default encoder then. In the other words, I really hope there could be an official deflate encoder to support this mode as well. Also I think the in-kernel zlib decompression is somewhat slow just due to some non-technical reasons, I might need to improve this eveutually but it's no rush for us compared to support DEFLATE format first as well.

Quoted 58 lines

/*
* Compresses the largest prefix of 'in', with maximum size 'in_nbytes', whose
* compressed output is at most 'target_output_size' bytes. The compressed size
* is returned as the return value, and the uncompressed size is returned in
* *actual_in_nbytes_ret. The output buffer 'out' has size 'out_nbytes_avail',
* which should be at least 'target_output_size + 9'. 'tmpbuf' must be a buffer
* the same size as 'out'.
*/
static size_t
do_compress_withfixedoutputsize(struct compressor *c,
const u8 *in, size_t in_nbytes,
u8 *out, size_t out_nbytes_avail, size_t target_output_size,
size_t last_uncompressed_size,
u8 *tmpbuf,
size_t *actual_in_nbytes_ret)

{
	size_t l = 0; /* largest input that fits so far */
	size_t l_csize = 0;
	size_t r = in_nbytes + 1; /* smallest input that doesn't fit so far */
	size_t m;

	if (last_uncompressed_size)
		m = last_uncompressed_size * 15 / 16;
	else
		m = target_output_size * 4;
	for (;;) {
		size_t csize;

		m = MAX(m, l + 1);
		m = MIN(m, r - 1);

		csize = do_compress(c, in, m, tmpbuf, out_nbytes_avail);
		if (csize > 0 && csize <= target_output_size) {
			/* Fits */
			memcpy(out, tmpbuf, csize);
			l = m;
			l_csize = csize;
			if (r <= l + 1)
				break;
			/*
			 * Estimate needed input prefix size based on current
			 * compression ratio.
			 */
			m = (target_output_size * m) / csize;
		} else {
			/* Doesn't fit */
			r = m;
			if (r <= l + 1)
				break;
			m = (l + r) / 2;
		}
	}
	*actual_in_nbytes_ret = l;
	return l_csize;
}
Quoted 5 lines
Quoted 1 line

What do you think?

Thank you for the time and your efforts, I much appreciate if it could be supported so I could add a alternative encoder for this.

Native fixed-size-output size support in libdeflate is something I'll think about. However, the point I'm making is that it's unclear how valuable native fixed-size-output size support in compressors is, given that the search algorithm I described above actually seems to work fairly well, and it can produce the optimal solution.

Here's a quick proof of concept patch for mkfs.erofs:

lib/Makefile.am +1 -0
index 553b387..f58a684 100644
@@ -45,3 +45,4 @@ liberofs_la_SOURCES += compressor_liblzma.c
  endif
 
  liberofs_la_SOURCES += kite_deflate.c compressor_deflate.c
+liberofs_la_LDFLAGS = -ldeflate
lib/compressor_deflate.c +66 -2
index ad76b7c..d7a5e90 100644
@@ -6,6 +6,7 @@
  #include "erofs/internal.h"
  #include "erofs/print.h"
  #include "erofs/config.h"
+#include "libdeflate.h"
  #include "compressor.h"
 
  void *kite_deflate_init(int level, unsigned int dict_size);
@@ -13,16 +14,64 @@ void kite_deflate_end(void *s);
  int kite_deflate_destsize(void *s, const u8 *in, u8 *out,
  			  unsigned int *srcsize, unsigned int target_dstsize);
 
+#define USE_LIBDEFLATE
+
  static int deflate_compress_destsize(const struct erofs_compress *c,
  				     const void *src, unsigned int *srcsize,
  				     void *dst, unsigned int dstsize)
  {
+#ifdef USE_LIBDEFLATE
+	static size_t last_uncompressed_size = 0;
+	size_t l = 0; /* largest input that fits so far */
+	size_t l_csize = 0;
+	size_t r = *srcsize + 1; /* smallest input that doesn't fit so far */
+	size_t m;
+	u8 tmpbuf[dstsize + 9];
+
+	if (last_uncompressed_size)
+		m = last_uncompressed_size * 15 / 16;
+	else
+		m = dstsize * 4;
+	for (;;) {
+		size_t csize;
+
+		m = max(m, l + 1);
+		m = min(m, r - 1);
+
+		csize = libdeflate_deflate_compress(c->private_data, src, m, tmpbuf, dstsize + 9);
+		/*printf("Tried %zu => %zu\n", m, csize);*/
+		if (csize > 0 && csize <= dstsize) {
+			/* Fits */
+			memcpy(dst, tmpbuf, csize);
+			l = m;
+			l_csize = csize;
+			if (r <= l + 1 || csize + (22 - 2*(int)c->compression_level) >= dstsize)
+				break;
+			/*
+			 * Estimate needed input prefix size based on current
+			 * compression ratio.
+			 */
+			m = (dstsize * m) / csize;
+		} else {
+			/* Doesn't fit */
+			r = m;
+			if (r <= l + 1)
+				break;
+			m = (l + r) / 2;
+		}
+	}
+	/*printf("Choosing %zu => %zu\n", l, l_csize);*/
+	*srcsize = l;
+	last_uncompressed_size = l;
+	return l_csize;
+#else
  	int rc = kite_deflate_destsize(c->private_data, src, dst,
  				       srcsize, dstsize);
 
  	if (rc <= 0)
  		return -EFAULT;
  	return rc;
+#endif
  }
 
  static int compressor_deflate_exit(struct erofs_compress *c)
@@ -30,7 +79,11 @@ static int compressor_deflate_exit(struct erofs_compress *c)
  	if (!c->private_data)
  		return -EINVAL;
 
+#ifdef USE_LIBDEFLATE
+	libdeflate_free_compressor(c->private_data);
+#else
  	kite_deflate_end(c->private_data);
+#endif
  	return 0;
  }
 
@@ -47,8 +100,13 @@ static int compressor_deflate_init(struct erofs_compress *c)
  static int erofs_compressor_deflate_setlevel(struct erofs_compress *c,
  					     int compression_level)
  {
-	void *s;
+	if (compression_level < 0)
+		compression_level = erofs_compressor_deflate.default_level;
 
+#ifdef USE_LIBDEFLATE
+	libdeflate_free_compressor(c->private_data);
+	c->private_data = libdeflate_alloc_compressor(compression_level);
+#else
  	if (c->private_data) {
  		kite_deflate_end(c->private_data);
  		c->private_data = NULL;
@@ -57,11 +115,13 @@ static int erofs_compressor_deflate_setlevel(struct erofs_compress *c,
  	if (compression_level < 0)
  		compression_level = erofs_compressor_deflate.default_level;
 
-	s = kite_deflate_init(compression_level, cfg.c_dict_size);
+	void *s = kite_deflate_init(compression_level, cfg.c_dict_size);
  	if (IS_ERR(s))
  		return PTR_ERR(s);
 
  	c->private_data = s;
+#endif
+
  	c->compression_level = compression_level;
  	return 0;
  }
@@ -69,7 +129,11 @@ static int erofs_compressor_deflate_setlevel(struct erofs_compress *c,
  const struct erofs_compressor erofs_compressor_deflate = {
  	.name = "deflate",
  	.default_level = 1,
+#ifdef USE_LIBDEFLATE
+	.best_level = 12,
+#else
  	.best_level = 9,
+#endif
  	.init = compressor_deflate_init,
  	.exit = compressor_deflate_exit,
  	.setlevel = erofs_compressor_deflate_setlevel,

Here are some quick benchmarks I did of mkfs.erofs showing the size of the resulting filesystem and the time it took for mkfs.erofs to run:

lib/compressor_deflate.c +0 -7
-zdeflate,1
     kite_deflate: 10772480 bytes in 0.474s
     libdeflate: 10366976 bytes in 0.468s
-zdeflate,3
     kite_deflate: 10203136 bytes in 0.511s
     libdeflate: 10092544 bytes in 0.702s
-zdeflate,5
     kite_deflate: 10080256 bytes in 0.596s
     libdeflate: 9973760 bytes in 0.896s
-zdeflate,6
     kite_deflate: 9977856 bytes in 0.650s
     libdeflate: 9936896 bytes in 0.981s
-zdeflate,7
     kite_deflate: 9969664 bytes in 0.690s
     libdeflate: 9920512 bytes in 1.187s
-zdeflate,9
     kite_deflate: 9945088 bytes in 0.986s
     libdeflate: 9871360 bytes in 2.041s
-zdeflate,12
     kite_deflate: N/A
     libdeflate: 9740288 bytes in 28.080s
Quoted 3 lines

So it seems my "naive" search algorithm, when combined with libdeflate, actually does about as well as kite_deflate... Plus it automatically brings in support for higher compression levels.

kite_deflate still has some room to improve since I just make it work to replace the original zlib, just TBH.

Yeah, I could integrate libdeflate like this first, thanks Eric!

Thanks,
Gao Xiang

author
#7 lore raw

Re: [PATCH 2/4] erofs-utils: add a built-in DEFLATE compressor

(forgot to respond something...)

Quoted 2 lines · Gao Xiang

...

Quoted 9 lines
Quoted 9 lines
Quoted 8 lines

I think we could use this way first for the new Zstd support (if they don't have bandwidth to add a offical fixed-sized output approach), but considering deflate algorithm is quite easy for me to understand so at least I could have a simple built-in one to avoid external dependency (mainly considering zlib since it's quite outdated).  Since EROFS is actually offline compression so the compressed data correctness can always be checked in advance before image release.

Quoted 3 lines
Quoted 3 lines

Writing an optimized compressor, especially one that implements high compression levels, is very hard.  Are you sure it's something you want to implement and maintain in erofs-utils?

Nope, as I said earlier, I'd like to write a simple one to replace zlib functionality (kite_deflate already does), and I hope more popular encoders could have offical modes for EROFS in the long term. That is something that I wish to the opensource communities...

Thanks,
Gao Xiang

author
#8 lore raw

PATCH 3/4 erofs-utils: fuse: 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   |   3 +-
 fsck/Makefile.am   |   6 +-
 fuse/Makefile.am   |   2 +-
 include/erofs_fs.h |   7 +++
 lib/decompress.c   | 145 +++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 204 insertions(+), 4 deletions(-)
configure.ac +45 -0
index cd6be4a..d41f4a3 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"])
@@ -394,6 +403,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"
 
@@ -449,6 +486,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 +2 -1
index c2bef6d..63f301e 100644
@@ -7,4 +7,5 @@ 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} \
-	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS}
+	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} \
+	${libdeflate_LIBS}
fsck/Makefile.am +4 -2
index 9366a9d..ffdd0be 100644
@@ -7,7 +7,8 @@ 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} \
-	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS}
+	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} \
+	${libdeflate_LIBS}
 
 if ENABLE_FUZZING
 noinst_PROGRAMS   = fuzz_erofsfsck
@@ -15,5 +16,6 @@ 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} \
-	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS}
+	${libuuid_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 +145 -0

157 lines not on this page · raw message

Signature · 1 line
2.24.4
author
#9 lore raw

PATCH 4/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 | 77 ++++++++++++++++++++++++++++++++++++++++
 lib/decompress.c         |  8 +++--
 6 files changed, 109 insertions(+), 4 deletions(-)
 create mode 100644 lib/compressor_deflate.c
lib/Makefile.am +1 -1
index fa3b804..553b387 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 +77 -0

77 lines not on this page · raw message

lib/decompress.c +5 -3
index 5bc55c5..a3e8ed7 100644
@@ -133,9 +133,11 @@ static int z_erofs_decompress_deflate(struct z_erofs_decompress_req *rq)
 	strm.avail_out = rq->decodedlength;
 
 	ret = inflate(&strm, rq->partial_decoding ? Z_SYNC_FLUSH : Z_FINISH);
-	if (ret != Z_STREAM_END) {
-		ret = zerr(ret);
-		goto out_inflate_end;
+	if (ret != Z_STREAM_END || strm.total_out != rq->decodedlength) {
+		if (rq->partial_decoding && ret != Z_OK) {
+			ret = zerr(ret);
+			goto out_inflate_end;
+		}
 	}
 
 	if (rq->decodedskip)
Signature · 1 line
2.24.4
author
#10 lore raw

PATCH v2 3/4 erofs-utils: fuse: 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.

---
v2:
move a misplaced logic from [4/4] to [3/4].

 configure.ac       |  45 ++++++++++++++
 dump/Makefile.am   |   3 +-
 fsck/Makefile.am   |   6 +-
 fuse/Makefile.am   |   2 +-
 include/erofs_fs.h |   7 +++
 lib/decompress.c   | 147 +++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 206 insertions(+), 4 deletions(-)
configure.ac +45 -0
index cd6be4a..b393064 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"])
@@ -394,6 +403,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"
 
@@ -449,6 +486,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 +2 -1
index c2bef6d..63f301e 100644
@@ -7,4 +7,5 @@ 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} \
-	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS}
+	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} \
+	${libdeflate_LIBS}
fsck/Makefile.am +4 -2
index 9366a9d..ffdd0be 100644
@@ -7,7 +7,8 @@ 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} \
-	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS}
+	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS} ${zlib_LIBS} \
+	${libdeflate_LIBS}
 
 if ENABLE_FUZZING
 noinst_PROGRAMS   = fuzz_erofsfsck
@@ -15,5 +16,6 @@ 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} \
-	${libuuid_LIBS} ${liblz4_LIBS} ${liblzma_LIBS}
+	${libuuid_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
#11 lore raw

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

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.

---
v2:
improve print message.

 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 fa3b804..553b387 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