[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH v6 3/4] qcow2: add zstd cluster compression

From: Denis Plotnikov
Subject: Re: [PATCH v6 3/4] qcow2: add zstd cluster compression
Date: Mon, 16 Mar 2020 18:57:08 +0300
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1

On 16.03.2020 17:01, Eric Blake wrote:
On 3/12/20 4:22 AM, Denis Plotnikov wrote:
zstd significantly reduces cluster compression time.
It provides better compression performance maintaining
the same level of the compression ratio in comparison with
zlib, which, at the moment, is the only compression
method available.

+++ b/docs/interop/qcow2.txt
@@ -208,6 +208,7 @@ version 2.
                        Available compression type values:
                          0: zlib <https://www.zlib.net/>
+                        1: zstd <http://github.com/facebook/zstd>
      === Header padding ===
@@ -575,11 +576,30 @@ Compressed Clusters Descriptor (x = 62 - (cluster_bits - 8)):                       Another compressed cluster may map to the tail of the final
                      sector used by this compressed cluster.
  +                    The layout of the compressed data depends on the compression +                    type used for the image (see compressed cluster layout).
  If a cluster is unallocated, read requests shall read the data from the backing   file (except if bit 0 in the Standard Cluster Descriptor is set). If there is   no backing file or the backing file is smaller than the image, they shall read
  zeros for all parts that are not covered by the backing file.
  +=== Compressed Cluster Layout ===
+The compressed cluster data has a layout depending on the compression
+type used for the image, as follows:
+Compressed data layout for the available compression types:
+data_space_lenght - data chunk length available to store a compressed cluster.


+(for more details see "Compressed Clusters Descriptor")
+x = data_space_length - 1

If I understand correctly, data_space_length is really an upper bounds on the length available, because it is computed by rounding UP to the next 512-byte boundary (that is, the L2 descriptor lists the number of additional sectors used in storing the compressed data).  Which really means that we have the following, where + is cluster boundaries, S and E are the start and end of the compressed data, and D is the offset determined by data_space_length:


+    0:  (default)  zlib <http://zlib.net/>:
+            Byte  0 -  x:     the compressed data content
+                              all the space provided used for compressed data

For zlib, we have byte 0-E are compressed data, and bytes (E+1)-D (if any) are ignored.  There is no way to tell how many bytes between E and D exist, because zlib doesn't care (the compression stream itself ensures that decompression stops when input reaches E because the output reached a cluster boundary at that point).

+    1:  zstd <http://github.com/facebook/zstd>:
+            Byte  0 -  3:     the length of compressed data in bytes
+                  4 -  x:     the compressed data content

Whereas for zstd, the decompression MUST know the actual location of E, rather than passing in the slop between E and D; bytes 0-3 give us that information.

But your description is not very accurate:  if 'x' is point E, then it is NOT data_space_length - 1, but rather data_space_length - slop, where slop can be up to 511 bytes (the number of bytes from (E+1) to D).  And if 'x' is point E, then the real layout for zlib is:

byte 0 - E: the compressed data content
byte E+1 - x: ignored slop (E is implied solely by the compressed data)

and for zstd is:

byte 0 - 3: the length of the compressed data
byte 4 - E: the compressed data (E computed from byte 0-3)
byte E+1 - x: ignored

I'm not sure what the best way is to document this.

+++ b/block/qcow2-threads.c

+static ssize_t qcow2_zstd_compress(void *dest, size_t dest_size,
+                                   const void *src, size_t src_size)
+    size_t ret;
+    /*
+     * steal ZSTD_LEN_BUF bytes in the very beginning of the buffer
+     * to store compressed chunk size
+     */
+    char *d_buf = ((char *) dest) + ZSTD_LEN_BUF;
+    /*
+     * sanity check that we can store the compressed data length,
+     * and there is some space left for the compressor buffer
+     */
+    if (dest_size <= ZSTD_LEN_BUF) {
+        return -ENOMEM;
+    }
+    dest_size -= ZSTD_LEN_BUF;
+    ret = ZSTD_compress(d_buf, dest_size, src, src_size, 5);

Where does the magic number 5 come from?
I did some tests to get the same compression ratio as zlib but do it faster than zlib. ZLIB also used hardcoded "compression ratio". Changing of the compression ratios in both compression types is something that can be changed with later patches.

+    if (ZSTD_isError(ret)) {
+        if (ZSTD_getErrorCode(ret) == ZSTD_error_dstSize_tooSmall) {
+            return -ENOMEM;
+        } else {
+            return -EIO;
+        }
+    }
+    /*
+     * paranoid sanity check that we can store
+     * the compressed size in the first 4 bytes
+     */
+    if (ret > UINT32_MAX) {
+        return -ENOMEM;
+    }

The if is awkward.  I'd prefer to change this to:

     * Our largest cluster is 2M, and we insist that compression
     * actually compressed things.
    assert(ret < UINT32_MAX);

or even tighten to assert(ret <= dest_size)

+    /* store the compressed chunk size in the very beginning of the buffer */
+    stl_be_p(dest, ret);
+    return ret + ZSTD_LEN_BUF;
+ * qcow2_zstd_decompress()
+ *
+ * Decompress some data (not more than @src_size bytes) to produce exactly
+ * @dest_size bytes using zstd compression method
+ *
+ * @dest - destination buffer, @dest_size bytes
+ * @src - source buffer, @src_size bytes
+ *
+ * Returns: 0 on success
+ *          -EIO on any error
+ */
+static ssize_t qcow2_zstd_decompress(void *dest, size_t dest_size,
+                                     const void *src, size_t src_size)
+    /*
+     * zstd decompress wants to know the exact length of the data.
+     * For that purpose, on compression, the length is stored in
+     * the very beginning of the compressed buffer
+     */
+    size_t s_size;
+    const char *s_buf = ((const char *) src) + ZSTD_LEN_BUF;
+    /*
+     * sanity check that we can read 4 byte the content length and
+     * and there is some content to decompress
+     */
+    if (src_size <= ZSTD_LEN_BUF) {
+        return -EIO;
+    }
+    s_size = ldl_be_p(src);
+    /* sanity check that the buffer is big enough to read the content from */
+    if (src_size - ZSTD_LEN_BUF < s_size) {
+        return -EIO;
+    }
+    if (ZSTD_isError(
+            ZSTD_decompress(dest, dest_size, s_buf, s_size))) {

You are correct that ZSTD_decompress() is picky that it must be given the exact size of the compressed buffer it is decompressing.  But the ZSTD manual mentions that if an exact size is not known in advance, that the streaming API can be used instead:

To be honest, I didn't find where they mentioned that explicitly. Could you please point where exactly?

But I found the following:

  Calling ZSTD_compressStream2() with ZSTD_e_end instructs to finish a frame.
  It will perform a flush and write frame epilogue.
  The epilogue is required for decoders to consider a frame completed.
  flush operation is the same, and follows same rules as calling 
ZSTD_compressStream2() with ZSTD_e_flush.
  You must continue calling ZSTD_compressStream2() with ZSTD_e_end until it 
returns 0, at which point you are free to
  start a new frame

I think in the epilogue they store the same information that I did and 
potentially (I didn't check) some more to finish the frame.
So we didn't win any space. Additionally, using streaming API will make the 
code more complex.

So I decided to stick with more simple version.

In other words, would it be possible to NOT have to prepend four bytes of exact size information, by instead setting up decompression via the streaming API where the input is (usually) oversized, but the output buffer limited to exactly one cluster is sufficient to consume the exact compressed data and ignore the slop, just as we do in zlib?

The rest of this patch looks okay.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]