[v5,2/3] qcow2: add update refcount table realization for update_refcount

When every item of refcount block is NULL, free refcount block and reset the
corresponding item of refcount table with NULL. At the same time, put this
cluster to s->free_cluster_index.

Signed-off-by: Jun Li <junmuzi@gmail.com>
---
v5:
  Just instead write_reftable_entry with bdrv_pwrite_sync. As write_reftable_entry has deleted from the source code.

v4:
  Do not change anything for this commit id.

v3:
  Add handle self-describing refcount blocks.
---
 block/qcow2-refcount.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 48 insertions(+), 1 deletion(-)

On 2014-10-26 at 16:20, Jun Li wrote:
> When every item of refcount block is NULL, free refcount block and reset the
> corresponding item of refcount table with NULL. At the same time, put this
> cluster to s->free_cluster_index.
>
> Signed-off-by: Jun Li <junmuzi@gmail.com>
> ---
> v5:
>    Just instead write_reftable_entry with bdrv_pwrite_sync. As write_reftable_entry has deleted from the source code.
>
> v4:
>    Do not change anything for this commit id.
>
> v3:
>    Add handle self-describing refcount blocks.
> ---
>   block/qcow2-refcount.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++++-
>   1 file changed, 48 insertions(+), 1 deletion(-)

Well, this patch will conflict with my "qcow2: Support refcount orders 
!= 4" series, but that's how it is.

> diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
> index 1477031..abb4f6d 100644
> --- a/block/qcow2-refcount.c
> +++ b/block/qcow2-refcount.c
> @@ -596,6 +596,53 @@ static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
>           if (refcount == 0 && s->discard_passthrough[type]) {
>               update_refcount_discard(bs, cluster_offset, s->cluster_size);
>           }

We can skip the whole following block if refcount > 0, so we should do that.

> +
> +        unsigned int refcount_table_index;

Declarations only at the start of the block, please. Furthermore, this 
is the same as table_index.

> +        refcount_table_index = cluster_index >> s->refcount_block_bits;
> +
> +        uint64_t refcount_block_offset =
> +            s->refcount_table[refcount_table_index] & REFT_OFFSET_MASK;
> +
> +        int64_t self_block_index = refcount_block_offset >> s->cluster_bits;
> +        int self_block_index2 = (refcount_block_offset >> s->cluster_bits) &
> +            ((1 << s->refcount_block_bits) - 1);

You are assuming here that every refblock is described by itself. While 
that may be true for QEMU's current qcow2 driver, it's by no means 
defined that way.

> +
> +        /* When refcount block is NULL, update refcount table */
> +        if (!be16_to_cpu(refcount_block[0]) || self_block_index2 == 0) {

Is this check really necessary? I think we can just go into the for () 
loop. If the first entry is not 0, it will be exited immediately anyway.

> +            int k;
> +            int refcount_block_entries = s->cluster_size /
> +                                         sizeof(refcount_block[0]);

s->refcount_block_size is what you want (but we probably didn't have it 
in October yet).

> +            for (k = 0; k < refcount_block_entries; k++) {
> +                if (k == self_block_index2) {
> +                    k++;

This should be replaced by a "continue", otherwise the following array 
access will overflow if self_block_index2 == refcount_block_entries - 1;

> +                }
> +
> +                if (be16_to_cpu(refcount_block[k])) {
> +                    break;
> +                }
> +            }
> +
> +            if (k == refcount_block_entries) {
> +                if (self_block_index < s->free_cluster_index) {
> +                    s->free_cluster_index = self_block_index;
> +                }

You should probably flush the refblock cache here. When the cluster 
which was occupied by the refblock is marked free, it may be used for 
different data, while the refblock remains cached. When the cache entry 
is removed later on, it will be written to disk and overwrite that cluster.

Also, you're again assuming that every refblock handles its own 
refcount, which is not necessarily true. The refcount may be handled by 
a different refblock in which case you have to decrement its refcount there.

> +
> +                /* update refcount table */
> +                s->refcount_table[refcount_table_index] = 0;
> +                uint64_t data64 = cpu_to_be64(0);
> +                ret = bdrv_pwrite_sync(bs->file,
> +                                       s->refcount_table_offset +
> +                                       refcount_table_index *
> +                                       sizeof(uint64_t),
> +                                       &data64, sizeof(data64));
> +                if (ret < 0) {
> +                    fprintf(stderr, "Could not update refcount table: %s\n",
> +                            strerror(-ret));
> +                    goto fail;
> +                }
> +

There's an empty line here which is probably unneeded. Also, you may 
want to do an overlap check before updating the reftable.

> +            }
> +        }
>       }
>   
>       ret = 0;
> @@ -1204,7 +1251,7 @@ static int check_refcounts_l2(BlockDriverState *bs, BdrvCheckResult *res,
>   
>           case QCOW2_CLUSTER_NORMAL:
>           {
> -            uint64_t offset = l2_entry & L2E_OFFSET_MASK;
> +            uint64_t offset = (uint64_t)(l2_entry & L2E_OFFSET_MASK);

Is that supposed to be in this patch? Also, what does it do? l2_entry is 
uint64_t anyway, so the result of l2_entry & L2E_OFFSET_MASK should 
already be of type uint64_t.

>               if (flags & CHECK_FRAG_INFO) {
>                   res->bfi.allocated_clusters++;

So, about this whole patch: I'm not sure whether we need it in this 
series but I remember you saying that it's actually worth it, so I'm 
trusting you.

Second, I somehow don't like iterating over the whole refblock for each 
refcount updated or at least for each refcount set to 0. There are 32768 
entries per refblock with 16 bit refcounts and 64 kB clusters. 
Therefore, when freeing all clusters referenced by a refblock (and if 
that refblock doesn't have any free entries yet), we will loop over 
16384 entries (in average) before noticing there are still entries with 
a non-zero refcount, and that we will do 32768 times (okay, 32767, 
because you're assuming a refblock always contains its own refcount). I 
think that a bit much. But I don't have any idea to fix this other than 
keeping the number of entries per refblock with refcount != 0 in a table 
in memory (which is probably not too bad, but not too nice either).

Max

On 11/21/2014 05:41 AM, Max Reitz wrote:
> On 2014-10-26 at 16:20, Jun Li wrote:
>> When every item of refcount block is NULL, free refcount block and
>> reset the
>> corresponding item of refcount table with NULL. At the same time, put
>> this
>> cluster to s->free_cluster_index.
>>
>> Signed-off-by: Jun Li <junmuzi@gmail.com>
>> ---

>> +        refcount_table_index = cluster_index >> s->refcount_block_bits;
>> +
>> +        uint64_t refcount_block_offset =
>> +            s->refcount_table[refcount_table_index] & REFT_OFFSET_MASK;
>> +
>> +        int64_t self_block_index = refcount_block_offset >>
>> s->cluster_bits;
>> +        int self_block_index2 = (refcount_block_offset >>
>> s->cluster_bits) &
>> +            ((1 << s->refcount_block_bits) - 1);
> 
> You are assuming here that every refblock is described by itself. While
> that may be true for QEMU's current qcow2 driver, it's by no means
> defined that way.

In fact, it is NOT true for qemu's qcow2 driver.  Remember, the reftable
MUST be contiguous clusters.  I can create an image with enough data
such that the reftable itself will occupy more clusters than what a
single refblock will describe.  Worst case, with 512-byte clusters, and
after the series allowing for refcount_order != 4, the smallest such
image is a 64-bit refcount-width, where each cluster of the reftable
describes 64 refblocks, and where each refblock describes 64 clusters.
An image that is large enough to need 127 or more clusters in the
reftable (merely 127*64*64*512 == 266,338,304 host bytes) means that at
least 64 consecutive clusters are all tied up by the reftable and
therefore those clusters cannot contain a self-referential refblock.

The sizes get (much) bigger for the defaults of 64k clusters and 16-bit
refcounts (each cluster of the reftable covers 8192 refblocks, each
refblock covers 32768 clusters, so you need 65535 consecutive clusters
in the reftable before guaranteeing a refblock is not self-referential;
but this works out to an image of 65535*8192*32768*65536 ==
1,152,903,912,420,802,560 bytes; and I'm not going to try to create an
exabyte image any time soon).  But even if I can't guarantee such an
image in a reasonable size does not mean that such an image won't be
created at smaller sizes due to other allocation patterns.

You DO need to be able to recognize self-referential refblocks, in order
clean them up if the only refcount remaining in the refblock is
self-referential, but you must ALSO recognize that not all refblocks are
self-referential.

> So, about this whole patch: I'm not sure whether we need it in this
> series but I remember you saying that it's actually worth it, so I'm
> trusting you.
> 
> Second, I somehow don't like iterating over the whole refblock for each
> refcount updated or at least for each refcount set to 0. There are 32768
> entries per refblock with 16 bit refcounts and 64 kB clusters.
> Therefore, when freeing all clusters referenced by a refblock (and if
> that refblock doesn't have any free entries yet), we will loop over
> 16384 entries (in average) before noticing there are still entries with
> a non-zero refcount, and that we will do 32768 times (okay, 32767,
> because you're assuming a refblock always contains its own refcount). I
> think that a bit much. But I don't have any idea to fix this other than
> keeping the number of entries per refblock with refcount != 0 in a table
> in memory (which is probably not too bad, but not too nice either).

On the other hand, since we have a proposal on the floor to track an
in-memory representation of used clusters to (tremendously) speed up
cluster overlap checking, THAT would be a perfect place to add in-memory
tracking of each refblock's current count of used refcounts, and could
therefore make it much faster to tell when a refblock is
self-referential, as well as its current count of occupied refcounts, so
that we don't have to scan the entire cluster on every operation.  It
does mean more bookkeeping when allocating or freeing clusters, but the
benefits may be worth it.