Re: [Qemu-devel] [PATCH v5 01/11] qcow2: Calculate refcount block entry count

[Max Reitz <mreitz@redhat.com>]

On 30.08.2014 01:03, Eric Blake wrote:
> On 08/29/2014 03:40 PM, Max Reitz wrote:
>> The size of a refblock entry is (in theory) variable; calculate
>> therefore the number of entries per refblock and the according bit shift
>> (1 << x == entry count) when opening an image.
>>
>> Signed-off-by: Max Reitz <mreitz@redhat.com>
>> ---
>>   block/qcow2.c | 2 ++
>>   block/qcow2.h | 2 ++
>>   2 files changed, 4 insertions(+)
> What is the maximum refcount_order?  The specs don't mention; the file
> format is wide open to overflows.  Even something as benign-sounding as
> refcount_order=6 (64 bits) means that each cluster can be referenced
> 2**64 times, which is far longer than our lifetimes to build it up that
> high incrementally, and represents far greater than the amount of
> storage in existence being deduplicated!  Shockingly easy to start
> getting into undefined territory, so maybe we ought to explicitly cap
> refcount_order to 6.

Well, the most obvious issue to me is that qcow2 only supports 64 bit 
offsets and sizes etc., so it shouldn't have refcounts wider than 64 bits.

On the other hand, it is probably possible to generate a valid image 
with a cluster having a refcount which exceeds 2^{64} - 1: Set the 
virtual size to (2^{64} - cluster_size), use a single data cluster for 
all virtual clusters which makes its refcount (2^{64} - cluster_size) / 
cluster_size (which would be 2^{55} - 1 in the most extreme case). Then 
you create cluster_size snapshots and the refcount of that cluster is 
now at (2^{55} - 1) * (1 + 512) = 2^{64} + 2^{55} - 512 - 1 >= 2^{64}.

But that would be crazy, so I think it very reasonable to forbid 
refcount_order > 6, too.

>> diff --git a/block/qcow2.c b/block/qcow2.c
>> index f9e045f..172ad00 100644
>> --- a/block/qcow2.c
>> +++ b/block/qcow2.c
>> @@ -689,6 +689,8 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
>>   
>>       s->l2_bits = s->cluster_bits - 3; /* L2 is always one cluster */
>>       s->l2_size = 1 << s->l2_bits;
>> +    s->refcount_block_bits = s->cluster_bits - (s->refcount_order - 3);
> Hmm; we document that qemu requires cluster_bits to be between 9 and 21
> inclusive.  So, if cluster_bits is 9 (512-byte clusters), and
> refcount_order is 6, then we can pack in 9 - (6 - 3) or 2**6 (that is,
> 64) refcounts per cluster.
>
> On the other extreme, the minimum refcount_order of 0 (each cluster
> occupies refcount bits, and so is either allocated or not, but no
> sharing), starts having the math looks ugly, because you are mixing:
>
> (int) = (uint32_t) - ( (uint32_t) - (int) )
>
> so at one point, you are doing s->cluster_bits - (4294967293U), but that
> wraps around (thankfully, wraparound is well-defined on unsigned types)
> for a net answer of cluster_bits + 3.  But in the worst case, that means
> an image with 2M clusters will be packing 21 - (0 - 3) or 2**24 (that
> is, 16M) refcounts in one cluster.  Still fits in an int, so it looks
> like you are safe...
>
>> +    s->refcount_block_size = 1 << s->refcount_block_bits;
> ...that this particular shift will not cause undefined behavior, for
> reasonable refcount_order in the range [0,6].

Well, for now refcount_order is asserted to be 4, anyway. ;-)

> Reviewed-by: Eric Blake <eblake@redhat.com>
>
> [We really ought to tighten the qcow2 spec - but that's a separate patch]

Yep, I'll include it in v2 of the follow-up series.

Max