Re: [Qemu-devel] QCow2 compression

Re: [Qemu-devel] QCow2 compression

[mgreger]

---- Eric Blake <eblake@redhat.com> wrote: 
> [any way you could convince your mailer to not break threading?]
> 
> On 03/03/2016 09:24 PM, mgreger@cinci.rr.com wrote:
> >>
> >> The zeros are not part of the compressed data, though, that's why the 
> >> Compressed Cluster Descriptor indicates a shorter size. Had another 
> >> compressed cluster been written to the same image, it might have ended 
> >> up where you are seeing the zero padding now. (The trick with 
> >> compression is that multiple guest clusters can end up in a single host 
> >> cluster.) 
> >>
> >  
> > Thanks, but the given length of 0x5600 is still short by 160(decimal) bytes 
> > compared to the 
> > non-zero data (which occupies an additional 133 bytes beyond the expected end at 
> > 0x3DED50) and zero 
> > padding (an additional 27 bytes beyond that). Could there be an off-by-one error 
> > somewhere? 
> > The file doesn't even end on a sector boundary let alone a cluster boundary. 
> 
> Based on an IRC conversation I had when you first asked the question, I
> think the spec is indeed weak, and that we DO have some fishy code.
> 
> Look at what the code does:
> 
> uint64_t qcow2_alloc_compressed_cluster_offset(BlockDriverState *bs,
>                                                uint64_t offset,
>                                                int compressed_size)
> ...
>     nb_csectors = ((cluster_offset + compressed_size - 1) >> 9) -
>                   (cluster_offset >> 9);
> 
>     cluster_offset |= QCOW_OFLAG_COMPRESSED |
>                       ((uint64_t)nb_csectors << s->csize_shift);
> 
> That sure does sound like an off-by-one.  cluster_offset does indeed
> look like a byte offset (from qcow2_alloc_bytes); so let's consider what
> happens if we've already allocated one compressed cluster in the past,
> going from 65536 to 66999.  So on this call, cluster_offset would be
> 67000, and if compressed size is 1025 (just round numbers to make
> discussion easy; no idea if gzip would really do this on any particular
> data), we are computing ((67000+1025-1)>>9) - (67000>>9) == 2, but 1025
> bytes occupies 3 sectors, not 2.
> 
> But we offset it by another off-by-one:
> 
> int qcow2_decompress_cluster(BlockDriverState *bs, uint64_t cluster_offset)
> {
> ...
>         nb_csectors = ((cluster_offset >> s->csize_shift) &
> s->csize_mask) + 1;
> 
> Yuck.  That is horribly ugly.
> 
> We need to fix the documentation to make it obvious that the sector
> count is a _LOWER BOUND_ on the number of sectors occupied, and that you
> need to read at least one more cluster's worth of data before decompressing.
> 
> It would also be nice to fix qcow2 code to not have quite so many
> off-by-one computations, but be more precise about what data is going where.
> 
> -- 
> Eric Blake   eblake redhat com    +1-919-301-3266
> Libvirt virtualization library http://libvirt.org
> 

Thanks for verifying the behavior for me. This will
allow me to add compression support to the code I've
already written.

I've implemented QCow2 support for a fork of the popular
DOSBox emulator.

The project (not mine), is called DOSBox-X, and is geared
towards emulating Windows9x era hardware with a specific
focus on games: http://dosbox-x.com/

If you'd like to give me any feedback on the QCow2 code I've written
please feel free to e-mail me directly. The relevant files are
qcow2_disk.cpp and qcow_disk.h. If you do, please be kind as
my C++ skills are very rusty. Overall I think it is pretty readable.
It took me about 2 and a half weeks working in my spare time to go
from reading the spec to the final code integrated into DOSBox-X.

Thanks,
Michael Greger

Re: [Qemu-devel] QCow2 compression

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2777 bytes --]

[any way you could convince your mailer to not break threading?]

On 03/03/2016 09:24 PM, mgreger@cinci.rr.com wrote:
>>
>> The zeros are not part of the compressed data, though, that's why the 
>> Compressed Cluster Descriptor indicates a shorter size. Had another 
>> compressed cluster been written to the same image, it might have ended 
>> up where you are seeing the zero padding now. (The trick with 
>> compression is that multiple guest clusters can end up in a single host 
>> cluster.) 
>>
>  
> Thanks, but the given length of 0x5600 is still short by 160(decimal) bytes 
> compared to the 
> non-zero data (which occupies an additional 133 bytes beyond the expected end at 
> 0x3DED50) and zero 
> padding (an additional 27 bytes beyond that). Could there be an off-by-one error 
> somewhere? 
> The file doesn't even end on a sector boundary let alone a cluster boundary. 

Based on an IRC conversation I had when you first asked the question, I
think the spec is indeed weak, and that we DO have some fishy code.

Look at what the code does:

uint64_t qcow2_alloc_compressed_cluster_offset(BlockDriverState *bs,
                                               uint64_t offset,
                                               int compressed_size)
...
    nb_csectors = ((cluster_offset + compressed_size - 1) >> 9) -
                  (cluster_offset >> 9);

    cluster_offset |= QCOW_OFLAG_COMPRESSED |
                      ((uint64_t)nb_csectors << s->csize_shift);

That sure does sound like an off-by-one.  cluster_offset does indeed
look like a byte offset (from qcow2_alloc_bytes); so let's consider what
happens if we've already allocated one compressed cluster in the past,
going from 65536 to 66999.  So on this call, cluster_offset would be
67000, and if compressed size is 1025 (just round numbers to make
discussion easy; no idea if gzip would really do this on any particular
data), we are computing ((67000+1025-1)>>9) - (67000>>9) == 2, but 1025
bytes occupies 3 sectors, not 2.

But we offset it by another off-by-one:

int qcow2_decompress_cluster(BlockDriverState *bs, uint64_t cluster_offset)
{
...
        nb_csectors = ((cluster_offset >> s->csize_shift) &
s->csize_mask) + 1;

Yuck.  That is horribly ugly.

We need to fix the documentation to make it obvious that the sector
count is a _LOWER BOUND_ on the number of sectors occupied, and that you
need to read at least one more cluster's worth of data before decompressing.

It would also be nice to fix qcow2 code to not have quite so many
off-by-one computations, but be more precise about what data is going where.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] QCow2 compression

[mgreger]

> > I have for example a compressed cluster with an L2 entry value of 4A 
> > C0 00 00 00 3D 97 50. This would lead me to believe the cluster starts 
> > at offset 0x3D9750 and has a length of 0x2B 512-byte sectors (or 0x2B 
> > times 0x200 = 0x5600). Added to the offset this would give an end for 
> > the cluster at offset 0x3DED50. However, it is clear from looking at 
> > the image that the compressed cluster extends further, the data ending 
> > at 0x3DEDD5 and being followed by some zero padding until 0x3DEDF0 
> > where the file ends. How can I know the data extends beyond the length 
> > I calculated? Did I misunderstand the documentation somewhere? Why 
> > does the file end here versus a cluster aligned offset? 
> 
> This zero padding happens in the very last cluster in the image in order 
> to ensure that the image file is aligned to a multiple of the cluster 
> size (qcow2 images are defined to consist of "units of constant size", 
> i.e. only full clusters). 
> 
> The zeros are not part of the compressed data, though, that's why the 
> Compressed Cluster Descriptor indicates a shorter size. Had another 
> compressed cluster been written to the same image, it might have ended 
> up where you are seeing the zero padding now. (The trick with 
> compression is that multiple guest clusters can end up in a single host 
> cluster.) 
> 
 
Thanks, but the given length of 0x5600 is still short by 160(decimal) bytes 
compared to the 
non-zero data (which occupies an additional 133 bytes beyond the expected end at 
0x3DED50) and zero 
padding (an additional 27 bytes beyond that). Could there be an off-by-one error 
somewhere? 
The file doesn't even end on a sector boundary let alone a cluster boundary. 
 
I can replicate this easily and produce files which demonstrate what I am seeing 
here. 
I will try to replicate using a newer version of the qemu-img. The version in 
Debian stable is quite old apparently. 

Re: [Qemu-devel] QCow2 compression

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1834 bytes --]

On 02/29/2016 07:01 AM, Kevin Wolf wrote:
>> I have for example a compressed cluster with an L2 entry value of 4A
>> C0 00 00 00 3D 97 50. This would lead me to believe the cluster starts
>> at offset 0x3D9750 and has a length of 0x2B 512-byte sectors (or 0x2B
>> times 0x200 = 0x5600). Added to the offset this would give an end for
>> the cluster at offset 0x3DED50. However, it is clear from looking at
>> the image that the compressed cluster extends further, the data ending
>> at 0x3DEDD5 and being followed by some zero padding until 0x3DEDF0
>> where the file ends. How can I know the data extends beyond the length
>> I calculated? Did I misunderstand the documentation somewhere? Why
>> does the file end here versus a cluster aligned offset?
> 
> This zero padding happens in the very last cluster in the image in order
> to ensure that the image file is aligned to a multiple of the cluster
> size (qcow2 images are defined to consist of "units of constant size",
> i.e. only full clusters).

The qcow2 spec is just fine with a host file that is not a multiple of a
cluster size (the bytes not present must behave as if they read as 0).
Whether we write explicit padding bytes or just truncate the file, on
the last cluster, shouldn't matter.  Although if we are only padding
part of the way, that's a bit odd.

> qemu-devel is alright for this kind of questions. I'm also copying
> qemu-block now, which makes the email thread more visible for the
> relevant people (as qemu-devel is relatively high traffic these days),
> but qemu-devel should always be included anyway.

Good idea, and sorry I wrote my first reply before seeing your message,
where I didn't include qemu-block.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] QCow2 compression

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 994 bytes --]

On 02/29/2016 07:59 AM, Eric Blake wrote:

>> an L2 entry value of 4A C0 00 00 00 3D 97 50.
> 
> So with default 64k clusters, x = 62 - (16 - 8) = 54.  Bits 0-54 are the
> host cluster offset, or 0x003d9750, but that is in terms of host
> sectors.  The comment in block/qcow2.c is telling, and perhaps we should
> improve the qcow2 spec to make it obvious:
> 
>   - Size of compressed clusters is stored in sectors to reduce bit usage
>     in the cluster offsets.
> 
> Thus, in your image, the guest compressed data starts at sector
> 0x003d9750, or host file offset 0x7b2ea000.  This value is NOT aligned
> to a cluster, but IS aligned to a sector (since a sector is the smallest
> unit we write to), and makes more sense than something ending in 0x50
> (which is not sector aligned).

Disclaimer - I did not test things, so I may be misreading the spec myself.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] QCow2 compression

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 3883 bytes --]

On 02/26/2016 10:00 PM, mgreger@cinci.rr.com wrote:
> Hello, I am hoping someone here can help me. I am implementing QCow2 support for a PC emulator project and have a couple questions regarding compression I haven't been able to figure out on my own.

[Can you convince your mailer to wrap long lines? It makes replying to
your mail easier]

> 
> First some background:
> I am using the information I found at https://people.gnome.org/~markmc/qcow-image-format.html

That page is outdated.  Better is the current spec, maintained directly
in qemu.git:

http://git.qemu.org/?p=qemu.git;a=blob;f=docs/specs/qcow2.txt

> and I have implemented working support for QCow2 images as described there except for snapshots, encryption, and compression. Of these, only compression is of immediate use to me.

Do NOT implement encryption, at least not in the form documented in
anything you've read so far.  We have a pending patch to implement LUKS
encryption, to replace the insecure existing encryption, although Dan's
latest email says it might not land until qemu 2.7:

https://lists.gnu.org/archive/html/qemu-devel/2016-02/msg06552.html


> 
> I have some QCow2 images all using 16-bit clusters created using qemu-img 2.1.2

You may want to use current qemu.git, which will soon be 2.5, although
compression hasn't really changed since then.

> According to the documentation I linked,

Better, according to the current documentation:

> Compressed Clusters Descriptor (x = 62 - (cluster_bits - 8)):
>
>   Bit 0 - x: Host cluster offset. This is usually _not_ aligned to a
>              cluster boundary!
>
>    x+1 - 61: Compressed size of the images in sectors of 512 bytes

> an L2 entry value of 4A C0 00 00 00 3D 97 50.

So with default 64k clusters, x = 62 - (16 - 8) = 54.  Bits 0-54 are the
host cluster offset, or 0x003d9750, but that is in terms of host
sectors.  The comment in block/qcow2.c is telling, and perhaps we should
improve the qcow2 spec to make it obvious:

  - Size of compressed clusters is stored in sectors to reduce bit usage
    in the cluster offsets.

Thus, in your image, the guest compressed data starts at sector
0x003d9750, or host file offset 0x7b2ea000.  This value is NOT aligned
to a cluster, but IS aligned to a sector (since a sector is the smallest
unit we write to), and makes more sense than something ending in 0x50
(which is not sector aligned).

> This would lead me to believe the cluster starts at offset 0x3D9750
and has a length of 0x2B 512-byte sectors (or 0x2B times 0x200 = 0x5600).

You are correct about the 64k of guest data being compressed into 0x5600
bytes in the host file, but incorrect at where to read those bytes.

> 
> A final question: I noticed that compressed clusters typically have a reference count higher than one, yet there are no snapshots present in the image. I suspect the count is incremented for each compressed cluster that exists even partially within a normal sized cluster region of the file, but I can find no documentation to this effect and am merely speculating. Am I correct?

Yes, you are correct, and yes, the spec I pointed to documents that.
Since the L2 entry in your example occupies only 43/128 sectors, any
other adjacent clusters from the guest point of view can be compressed
into the remaining sectors of the host cluster, and the refcount must be
equal to the number of all compressed guest clusters that occupy at
least one sector of the host cluster.

> 
> If it is the wrong place to ask these questions, I would appreciate it if anyone could direct me to a more appropriate venue. Thank you for taking the time to read this and tanks in advance for any assistance.

This is the right list.


-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] QCow2 compression

[Kevin Wolf]

[ Cc: qemu-block ]

Am 27.02.2016 um 06:00 hat mgreger@cinci.rr.com geschrieben:
> Hello, I am hoping someone here can help me. I am implementing QCow2
> support for a PC emulator project and have a couple questions
> regarding compression I haven't been able to figure out on my own.
> 
> First some background: I am using the information I found at
> https://people.gnome.org/~markmc/qcow-image-format.html and I have
> implemented working support for QCow2 images as described there except
> for snapshots, encryption, and compression. Of these, only compression
> is of immediate use to me.

First of all, the preferable source is the qcow2 specification from the
QEMU git repository:

http://git.qemu.org/?p=qemu.git;a=blob;f=docs/specs/qcow2.txt

The description you were using is good, but rather old. Not a problem
for the basics of compression because these things haven't ever changed,
but if you want to make sense of everything in a current image, you'll
need something more recent.

> I have some QCow2 images all using 16-bit clusters created using
> qemu-img 2.1.2 (the version bundled with Debian stable). According to
> the documentation I linked, 8 bits of an L2 table entry following the
> copy flag should say how many 512 byte sectors a compressed cluster
> takes up and the remaining bits are the actual offset of the cluster
> within the file.

The spec says this (which is essentially the same):

L2 table entry:

    Bit  0 -  61:   Cluster descriptor

              62:   0 for standard clusters
                    1 for compressed clusters

              63:   0 for a cluster that is unused or requires COW, 1 if its
                    refcount is exactly one. This information is only accurate
                    in L2 tables that are reachable from the active L1
                    table.

Compressed Clusters Descriptor (x = 62 - (cluster_bits - 8)):

    Bit  0 -  x:    Host cluster offset. This is usually _not_ aligned to a
                    cluster boundary!

       x+1 - 61:    Compressed size of the images in sectors of 512 bytes

> I have for example a compressed cluster with an L2 entry value of 4A
> C0 00 00 00 3D 97 50. This would lead me to believe the cluster starts
> at offset 0x3D9750 and has a length of 0x2B 512-byte sectors (or 0x2B
> times 0x200 = 0x5600). Added to the offset this would give an end for
> the cluster at offset 0x3DED50. However, it is clear from looking at
> the image that the compressed cluster extends further, the data ending
> at 0x3DEDD5 and being followed by some zero padding until 0x3DEDF0
> where the file ends. How can I know the data extends beyond the length
> I calculated? Did I misunderstand the documentation somewhere? Why
> does the file end here versus a cluster aligned offset?

This zero padding happens in the very last cluster in the image in order
to ensure that the image file is aligned to a multiple of the cluster
size (qcow2 images are defined to consist of "units of constant size",
i.e. only full clusters).

The zeros are not part of the compressed data, though, that's why the
Compressed Cluster Descriptor indicates a shorter size. Had another
compressed cluster been written to the same image, it might have ended
up where you are seeing the zero padding now. (The trick with
compression is that multiple guest clusters can end up in a single host
cluster.)

> A final question: I noticed that compressed clusters typically have a
> reference count higher than one, yet there are no snapshots present in
> the image. I suspect the count is incremented for each compressed
> cluster that exists even partially within a normal sized cluster
> region of the file, but I can find no documentation to this effect and
> am merely speculating. Am I correct?

Yes. You have multiple L2 entries referring to the same cluster, so it
needs to have a refcount that represents this.

Once you overwrite a compressed cluster, a copy-on-write operation is
performed and the refcount is decreased. You want to free the (host)
cluster holding the compressed data only after the last L2 entry using
it has gone.

> If it is the wrong place to ask these questions, I would appreciate it
> if anyone could direct me to a more appropriate venue. Thank you for
> taking the time to read this and tanks in advance for any assistance.

qemu-devel is alright for this kind of questions. I'm also copying
qemu-block now, which makes the email thread more visible for the
relevant people (as qemu-devel is relatively high traffic these days),
but qemu-devel should always be included anyway.

Kevin

[Qemu-devel] QCow2 compression

[mgreger]

Hello, I am hoping someone here can help me. I am implementing QCow2 support for a PC emulator project and have a couple questions regarding compression I haven't been able to figure out on my own.

First some background:
I am using the information I found at https://people.gnome.org/~markmc/qcow-image-format.html and I have implemented working support for QCow2 images as described there except for snapshots, encryption, and compression. Of these, only compression is of immediate use to me.

I have some QCow2 images all using 16-bit clusters created using qemu-img 2.1.2 (the version bundled with Debian stable). According to the documentation I linked, 8 bits of an L2 table entry following the copy flag should say how many 512 byte sectors a compressed cluster takes up and the remaining bits are the actual offset of the cluster within the file. I have for example a compressed cluster with an L2 entry value of 4A C0 00 00 00 3D 97 50. This would lead me to believe the cluster starts at offset 0x3D9750 and has a length of 0x2B 512-byte sectors (or 0x2B times 0x200 = 0x5600). Added to the offset this would give an end for the cluster at offset 0x3DED50. However, it is clear from looking at the image that the compressed cluster extends further, the data ending at 0x3DEDD5 and being followed by some zero padding until 0x3DEDF0 where the file ends. How can I know the data extends beyond the length I calculated? Did I misunderstand the documentation somewhere? Why does the file end here versus a cluster aligned offset?

A final question: I noticed that compressed clusters typically have a reference count higher than one, yet there are no snapshots present in the image. I suspect the count is incremented for each compressed cluster that exists even partially within a normal sized cluster region of the file, but I can find no documentation to this effect and am merely speculating. Am I correct?

If it is the wrong place to ask these questions, I would appreciate it if anyone could direct me to a more appropriate venue. Thank you for taking the time to read this and tanks in advance for any assistance.