[Qemu-devel] [PATCH 0/2] qcow2: Drop REFCOUNT_SHIFT

[Qemu-devel] [PATCH 0/2] qcow2: Drop REFCOUNT_SHIFT

[Max Reitz]

In preparation for qemu maybe actually supporting variable refcount
widths in the far future, drop the hardcoded REFCOUNT_SHIFT and instead
use the value as given by the image.

Also, the qcow2 documentation gave the width of a refcount block entry
as sizeof(uint16_t), which is wrong for any refcount order other than 4.
Fix that.

This is a follow-up to my "[PATCH v5 00/11] qcow2: Fix image repairing"
series and therefore depends on it.


Max Reitz (2):
  qcow2: Drop REFCOUNT_SHIFT
  docs/qcow2: Correct refcount_block_entries

 block/qcow2-refcount.c | 32 ++++++++++++++------------------
 block/qcow2.c          |  2 +-
 block/qcow2.h          |  2 --
 docs/specs/qcow2.txt   |  2 +-
 4 files changed, 16 insertions(+), 22 deletions(-)

-- 
2.1.0

[Qemu-devel] [PATCH 1/2] qcow2: Drop REFCOUNT_SHIFT

[Max Reitz]

With BDRVQcowState.refcount_block_bits, we don't need REFCOUNT_SHIFT
anymore.

Signed-off-by: Max Reitz <mreitz@redhat.com>
---
 block/qcow2-refcount.c | 32 ++++++++++++++------------------
 block/qcow2.c          |  2 +-
 block/qcow2.h          |  2 --
 3 files changed, 15 insertions(+), 21 deletions(-)

diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index 29136ee..cd6f5a0 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -102,7 +102,7 @@ static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
     uint16_t *refcount_block;
     uint16_t refcount;
 
-    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
+    refcount_table_index = cluster_index >> s->refcount_block_bits;
     if (refcount_table_index >= s->refcount_table_size)
         return 0;
     refcount_block_offset =
@@ -116,8 +116,7 @@ static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
         return ret;
     }
 
-    block_index = cluster_index &
-        ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
+    block_index = cluster_index & (s->refcount_block_size - 1);
     refcount = be16_to_cpu(refcount_block[block_index]);
 
     ret = qcow2_cache_put(bs, s->refcount_block_cache,
@@ -152,8 +151,8 @@ static unsigned int next_refcount_table_size(BDRVQcowState *s,
 static int in_same_refcount_block(BDRVQcowState *s, uint64_t offset_a,
     uint64_t offset_b)
 {
-    uint64_t block_a = offset_a >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
-    uint64_t block_b = offset_b >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
+    uint64_t block_a = offset_a >> (s->cluster_bits + s->refcount_block_bits);
+    uint64_t block_b = offset_b >> (s->cluster_bits + s->refcount_block_bits);
 
     return (block_a == block_b);
 }
@@ -174,7 +173,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
     BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC);
 
     /* Find the refcount block for the given cluster */
-    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
+    refcount_table_index = cluster_index >> s->refcount_block_bits;
 
     if (refcount_table_index < s->refcount_table_size) {
 
@@ -243,7 +242,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
 
         /* The block describes itself, need to update the cache */
         int block_index = (new_block >> s->cluster_bits) &
-            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
+            (s->refcount_block_size - 1);
         (*refcount_block)[block_index] = cpu_to_be16(1);
     } else {
         /* Described somewhere else. This can recurse at most twice before we
@@ -315,8 +314,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
     BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_GROW);
 
     /* Calculate the number of refcount blocks needed so far */
-    uint64_t refcount_block_clusters = 1 << (s->cluster_bits - REFCOUNT_SHIFT);
-    uint64_t blocks_used = DIV_ROUND_UP(cluster_index, refcount_block_clusters);
+    uint64_t blocks_used = DIV_ROUND_UP(cluster_index, s->refcount_block_size);
 
     if (blocks_used > QCOW_MAX_REFTABLE_SIZE / sizeof(uint64_t)) {
         return -EFBIG;
@@ -330,14 +328,14 @@ static int alloc_refcount_block(BlockDriverState *bs,
         uint64_t table_clusters =
             size_to_clusters(s, table_size * sizeof(uint64_t));
         blocks_clusters = 1 +
-            ((table_clusters + refcount_block_clusters - 1)
-            / refcount_block_clusters);
+            ((table_clusters + s->refcount_block_size - 1)
+            / s->refcount_block_size);
         uint64_t meta_clusters = table_clusters + blocks_clusters;
 
         last_table_size = table_size;
         table_size = next_refcount_table_size(s, blocks_used +
-            ((meta_clusters + refcount_block_clusters - 1)
-            / refcount_block_clusters));
+            ((meta_clusters + s->refcount_block_size - 1)
+            / s->refcount_block_size));
 
     } while (last_table_size != table_size);
 
@@ -347,7 +345,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
 #endif
 
     /* Create the new refcount table and blocks */
-    uint64_t meta_offset = (blocks_used * refcount_block_clusters) *
+    uint64_t meta_offset = (blocks_used * s->refcount_block_size) *
         s->cluster_size;
     uint64_t table_offset = meta_offset + blocks_clusters * s->cluster_size;
     uint64_t *new_table = g_try_new0(uint64_t, table_size);
@@ -546,8 +544,7 @@ static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
     {
         int block_index, refcount;
         int64_t cluster_index = cluster_offset >> s->cluster_bits;
-        int64_t table_index =
-            cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
+        int64_t table_index = cluster_index >> s->refcount_block_bits;
 
         /* Load the refcount block and allocate it if needed */
         if (table_index != old_table_index) {
@@ -569,8 +566,7 @@ static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
         qcow2_cache_entry_mark_dirty(s->refcount_block_cache, refcount_block);
 
         /* we can update the count and save it */
-        block_index = cluster_index &
-            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
+        block_index = cluster_index & (s->refcount_block_size - 1);
 
         refcount = be16_to_cpu(refcount_block[block_index]);
         refcount += addend;
diff --git a/block/qcow2.c b/block/qcow2.c
index 82bca88..cdbcb81 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -1799,7 +1799,7 @@ static int qcow2_create2(const char *filename, int64_t total_size,
         .l1_size                    = cpu_to_be32(0),
         .refcount_table_offset      = cpu_to_be64(cluster_size),
         .refcount_table_clusters    = cpu_to_be32(1),
-        .refcount_order             = cpu_to_be32(3 + REFCOUNT_SHIFT),
+        .refcount_order             = cpu_to_be32(4),
         .header_length              = cpu_to_be32(sizeof(*header)),
     };
 
diff --git a/block/qcow2.h b/block/qcow2.h
index 7c01fb7..5b099cb 100644
--- a/block/qcow2.h
+++ b/block/qcow2.h
@@ -59,8 +59,6 @@
 /* The cluster reads as all zeros */
 #define QCOW_OFLAG_ZERO (1ULL << 0)
 
-#define REFCOUNT_SHIFT 1 /* refcount size is 2 bytes */
-
 #define MIN_CLUSTER_BITS 9
 #define MAX_CLUSTER_BITS 21
 
-- 
2.1.0

[Qemu-devel] [PATCH 2/2] docs/qcow2: Correct refcount_block_entries

[Max Reitz]

A refblock entry may have a different size than 16 bits, it may even be
smaller than a byte. Correct the refcount_block_entries calculation
accordingly.

Signed-off-by: Max Reitz <mreitz@redhat.com>
---
 docs/specs/qcow2.txt | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/docs/specs/qcow2.txt b/docs/specs/qcow2.txt
index cfbc8b0..531c478 100644
--- a/docs/specs/qcow2.txt
+++ b/docs/specs/qcow2.txt
@@ -183,7 +183,7 @@ blocks and are exactly one cluster in size.
 Given a offset into the image file, the refcount of its cluster can be obtained
 as follows:
 
-    refcount_block_entries = (cluster_size / sizeof(uint16_t))
+    refcount_block_entries = (cluster_size / (refcount_bits / 8))
 
     refcount_block_index = (offset / cluster_size) % refcount_block_entries
     refcount_table_index = (offset / cluster_size) / refcount_block_entries
-- 
2.1.0

Re: [Qemu-devel] [PATCH 2/2] docs/qcow2: Correct refcount_block_entries

[Eric Blake]

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

On 08/29/2014 03:45 PM, Max Reitz wrote:
> A refblock entry may have a different size than 16 bits, it may even be
> smaller than a byte. Correct the refcount_block_entries calculation
> accordingly.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  docs/specs/qcow2.txt | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/docs/specs/qcow2.txt b/docs/specs/qcow2.txt
> index cfbc8b0..531c478 100644
> --- a/docs/specs/qcow2.txt
> +++ b/docs/specs/qcow2.txt
> @@ -183,7 +183,7 @@ blocks and are exactly one cluster in size.
>  Given a offset into the image file, the refcount of its cluster can be obtained
>  as follows:
>  
> -    refcount_block_entries = (cluster_size / sizeof(uint16_t))
> +    refcount_block_entries = (cluster_size / (refcount_bits / 8))
>  


Consider refcount_order == 0 (that is, no shared blocks, ALL blocks have
at most refcount 1).  Then, refcount_bits is (1 << 0) == 1.  But 1/8 in
integer math truncates to 0 (oops, division by zero is undefined); when
in reality, the expression you want here is (cluster_size * 8 /
refcount_bits).

-- 
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: 539 bytes --]

Re: [Qemu-devel] [PATCH 1/2] qcow2: Drop REFCOUNT_SHIFT

[Eric Blake]

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

On 08/29/2014 03:45 PM, Max Reitz wrote:
> With BDRVQcowState.refcount_block_bits, we don't need REFCOUNT_SHIFT
> anymore.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  block/qcow2-refcount.c | 32 ++++++++++++++------------------
>  block/qcow2.c          |  2 +-
>  block/qcow2.h          |  2 --
>  3 files changed, 15 insertions(+), 21 deletions(-)

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
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: 539 bytes --]

Re: [Qemu-devel] [PATCH 2/2] docs/qcow2: Correct refcount_block_entries

[Benoît Canet]

The Friday 29 Aug 2014 à 23:45:27 (+0200), Max Reitz wrote :
> A refblock entry may have a different size than 16 bits, it may even be
> smaller than a byte. Correct the refcount_block_entries calculation

Now if the refblock entry size is smaller than a byte

> accordingly.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  docs/specs/qcow2.txt | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/docs/specs/qcow2.txt b/docs/specs/qcow2.txt
> index cfbc8b0..531c478 100644
> --- a/docs/specs/qcow2.txt
> +++ b/docs/specs/qcow2.txt
> @@ -183,7 +183,7 @@ blocks and are exactly one cluster in size.
>  Given a offset into the image file, the refcount of its cluster can be obtained
>  as follows:
>  
> -    refcount_block_entries = (cluster_size / sizeof(uint16_t))
> +    refcount_block_entries = (cluster_size / (refcount_bits / 8))

This give a divide by zero error.                   ^

>  
>      refcount_block_index = (offset / cluster_size) % refcount_block_entries
>      refcount_table_index = (offset / cluster_size) / refcount_block_entries
> -- 
> 2.1.0
> 
> 

Re: [Qemu-devel] [PATCH 1/2] qcow2: Drop REFCOUNT_SHIFT

[Benoît Canet]

The Friday 29 Aug 2014 à 23:45:26 (+0200), Max Reitz wrote :
> With BDRVQcowState.refcount_block_bits, we don't need REFCOUNT_SHIFT
> anymore.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  block/qcow2-refcount.c | 32 ++++++++++++++------------------
>  block/qcow2.c          |  2 +-
>  block/qcow2.h          |  2 --
>  3 files changed, 15 insertions(+), 21 deletions(-)
> 
> diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
> index 29136ee..cd6f5a0 100644
> --- a/block/qcow2-refcount.c
> +++ b/block/qcow2-refcount.c
> @@ -102,7 +102,7 @@ static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
>      uint16_t *refcount_block;
>      uint16_t refcount;
>  
> -    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
> +    refcount_table_index = cluster_index >> s->refcount_block_bits;
>      if (refcount_table_index >= s->refcount_table_size)
>          return 0;
>      refcount_block_offset =
> @@ -116,8 +116,7 @@ static int get_refcount(BlockDriverState *bs, int64_t cluster_index)
>          return ret;
>      }
>  
> -    block_index = cluster_index &
> -        ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
> +    block_index = cluster_index & (s->refcount_block_size - 1);
>      refcount = be16_to_cpu(refcount_block[block_index]);
>  
>      ret = qcow2_cache_put(bs, s->refcount_block_cache,
> @@ -152,8 +151,8 @@ static unsigned int next_refcount_table_size(BDRVQcowState *s,
>  static int in_same_refcount_block(BDRVQcowState *s, uint64_t offset_a,
>      uint64_t offset_b)
>  {
> -    uint64_t block_a = offset_a >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
> -    uint64_t block_b = offset_b >> (2 * s->cluster_bits - REFCOUNT_SHIFT);
> +    uint64_t block_a = offset_a >> (s->cluster_bits + s->refcount_block_bits);
> +    uint64_t block_b = offset_b >> (s->cluster_bits + s->refcount_block_bits);
>  
>      return (block_a == block_b);
>  }
> @@ -174,7 +173,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
>      BLKDBG_EVENT(bs->file, BLKDBG_REFBLOCK_ALLOC);
>  
>      /* Find the refcount block for the given cluster */
> -    refcount_table_index = cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
> +    refcount_table_index = cluster_index >> s->refcount_block_bits;
>  
>      if (refcount_table_index < s->refcount_table_size) {
>  
> @@ -243,7 +242,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
>  
>          /* The block describes itself, need to update the cache */
>          int block_index = (new_block >> s->cluster_bits) &
> -            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
> +            (s->refcount_block_size - 1);
>          (*refcount_block)[block_index] = cpu_to_be16(1);
>      } else {
>          /* Described somewhere else. This can recurse at most twice before we
> @@ -315,8 +314,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
>      BLKDBG_EVENT(bs->file, BLKDBG_REFTABLE_GROW);
>  
>      /* Calculate the number of refcount blocks needed so far */
> -    uint64_t refcount_block_clusters = 1 << (s->cluster_bits - REFCOUNT_SHIFT);
> -    uint64_t blocks_used = DIV_ROUND_UP(cluster_index, refcount_block_clusters);
> +    uint64_t blocks_used = DIV_ROUND_UP(cluster_index, s->refcount_block_size);
>  
>      if (blocks_used > QCOW_MAX_REFTABLE_SIZE / sizeof(uint64_t)) {
>          return -EFBIG;
> @@ -330,14 +328,14 @@ static int alloc_refcount_block(BlockDriverState *bs,
>          uint64_t table_clusters =
>              size_to_clusters(s, table_size * sizeof(uint64_t));
>          blocks_clusters = 1 +
> -            ((table_clusters + refcount_block_clusters - 1)
> -            / refcount_block_clusters);
> +            ((table_clusters + s->refcount_block_size - 1)
> +            / s->refcount_block_size);
>          uint64_t meta_clusters = table_clusters + blocks_clusters;
>  
>          last_table_size = table_size;
>          table_size = next_refcount_table_size(s, blocks_used +
> -            ((meta_clusters + refcount_block_clusters - 1)
> -            / refcount_block_clusters));
> +            ((meta_clusters + s->refcount_block_size - 1)
> +            / s->refcount_block_size));
>  
>      } while (last_table_size != table_size);
>  
> @@ -347,7 +345,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
>  #endif
>  
>      /* Create the new refcount table and blocks */
> -    uint64_t meta_offset = (blocks_used * refcount_block_clusters) *
> +    uint64_t meta_offset = (blocks_used * s->refcount_block_size) *
>          s->cluster_size;
>      uint64_t table_offset = meta_offset + blocks_clusters * s->cluster_size;
>      uint64_t *new_table = g_try_new0(uint64_t, table_size);
> @@ -546,8 +544,7 @@ static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
>      {
>          int block_index, refcount;
>          int64_t cluster_index = cluster_offset >> s->cluster_bits;
> -        int64_t table_index =
> -            cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
> +        int64_t table_index = cluster_index >> s->refcount_block_bits;
>  
>          /* Load the refcount block and allocate it if needed */
>          if (table_index != old_table_index) {
> @@ -569,8 +566,7 @@ static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,
>          qcow2_cache_entry_mark_dirty(s->refcount_block_cache, refcount_block);
>  
>          /* we can update the count and save it */
> -        block_index = cluster_index &
> -            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
> +        block_index = cluster_index & (s->refcount_block_size - 1);
>  
>          refcount = be16_to_cpu(refcount_block[block_index]);
>          refcount += addend;
> diff --git a/block/qcow2.c b/block/qcow2.c
> index 82bca88..cdbcb81 100644
> --- a/block/qcow2.c
> +++ b/block/qcow2.c
> @@ -1799,7 +1799,7 @@ static int qcow2_create2(const char *filename, int64_t total_size,
>          .l1_size                    = cpu_to_be32(0),
>          .refcount_table_offset      = cpu_to_be64(cluster_size),
>          .refcount_table_clusters    = cpu_to_be32(1),
> -        .refcount_order             = cpu_to_be32(3 + REFCOUNT_SHIFT),
> +        .refcount_order             = cpu_to_be32(4),
>          .header_length              = cpu_to_be32(sizeof(*header)),
>      };
>  
> diff --git a/block/qcow2.h b/block/qcow2.h
> index 7c01fb7..5b099cb 100644
> --- a/block/qcow2.h
> +++ b/block/qcow2.h
> @@ -59,8 +59,6 @@
>  /* The cluster reads as all zeros */
>  #define QCOW_OFLAG_ZERO (1ULL << 0)
>  
> -#define REFCOUNT_SHIFT 1 /* refcount size is 2 bytes */
> -
>  #define MIN_CLUSTER_BITS 9
>  #define MAX_CLUSTER_BITS 21
>  
> -- 
> 2.1.0
> 
> 

Putting Jun Li in copy because he just wrote a patch using it.

Re: [Qemu-devel] [PATCH 2/2] docs/qcow2: Correct refcount_block_entries

[Max Reitz]

On 30.08.2014 00:37, Eric Blake wrote:
> On 08/29/2014 03:45 PM, Max Reitz wrote:
>> A refblock entry may have a different size than 16 bits, it may even be
>> smaller than a byte. Correct the refcount_block_entries calculation
>> accordingly.
>>
>> Signed-off-by: Max Reitz <mreitz@redhat.com>
>> ---
>>   docs/specs/qcow2.txt | 2 +-
>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/docs/specs/qcow2.txt b/docs/specs/qcow2.txt
>> index cfbc8b0..531c478 100644
>> --- a/docs/specs/qcow2.txt
>> +++ b/docs/specs/qcow2.txt
>> @@ -183,7 +183,7 @@ blocks and are exactly one cluster in size.
>>   Given a offset into the image file, the refcount of its cluster can be obtained
>>   as follows:
>>   
>> -    refcount_block_entries = (cluster_size / sizeof(uint16_t))
>> +    refcount_block_entries = (cluster_size / (refcount_bits / 8))
>>   
>
> Consider refcount_order == 0 (that is, no shared blocks, ALL blocks have
> at most refcount 1).  Then, refcount_bits is (1 << 0) == 1.  But 1/8 in
> integer math truncates to 0 (oops, division by zero is undefined); when
> in reality, the expression you want here is (cluster_size * 8 /
> refcount_bits).

If it is integer division, that is. ;-)

I'm counting on you accepting "cluster_size * 8 / refcount_bits" and not 
rejecting it because of a possible integer overflow. *g*

Max

Re: [Qemu-devel] [PATCH 2/2] docs/qcow2: Correct refcount_block_entries

[Eric Blake]

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

On 09/02/2014 12:59 PM, Max Reitz wrote:

>> Consider refcount_order == 0 (that is, no shared blocks, ALL blocks have
>> at most refcount 1).  Then, refcount_bits is (1 << 0) == 1.  But 1/8 in
>> integer math truncates to 0 (oops, division by zero is undefined); when
>> in reality, the expression you want here is (cluster_size * 8 /
>> refcount_bits).
> 
> If it is integer division, that is. ;-)
> 
> I'm counting on you accepting "cluster_size * 8 / refcount_bits" and not
> rejecting it because of a possible integer overflow. *g*

We already document that qemu's maximum cluster size is 2M; and 2M*8 is
less than 32 bits :)

Maybe the qcow2 spec allows the theoretical file with a cluster size of
512M, where overflow then matters.  But you are correct that I won't
reject your patch, given that qemu doesn't parse all possible
theoretical qcow2 files :)

-- 
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: 539 bytes --]