[Qemu-devel] [PATCH] qcow2: fix range check

[Qemu-devel] [PATCH] qcow2: fix range check

[Frediano Ziglio]

QCowL2Meta::offset is not cluster aligned but only sector aligned
however nb_clusters count cluster from cluster start.
This fix range check. Note that old code have no corruption issues
related to this check cause it only cause intersection to occur
when shouldn't.

Signed-off-by: Frediano Ziglio <freddy77@gmail.com>
---
 block/qcow2-cluster.c |   14 +++++++-------
 1 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/block/qcow2-cluster.c b/block/qcow2-cluster.c
index 428b5ad..2f76311 100644
--- a/block/qcow2-cluster.c
+++ b/block/qcow2-cluster.c
@@ -776,17 +776,17 @@ again:
      */
     QLIST_FOREACH(old_alloc, &s->cluster_allocs, next_in_flight) {
 
-        uint64_t end_offset = offset + nb_clusters * s->cluster_size;
-        uint64_t old_offset = old_alloc->offset;
-        uint64_t old_end_offset = old_alloc->offset +
-            old_alloc->nb_clusters * s->cluster_size;
+        uint64_t start = offset >> s->cluster_bits;
+        uint64_t end = start + nb_clusters;
+        uint64_t old_start = old_alloc->offset >> s->cluster_bits;
+        uint64_t old_end = old_start + old_alloc->nb_clusters;
 
-        if (end_offset < old_offset || offset > old_end_offset) {
+        if (end < old_start || start > old_end) {
             /* No intersection */
         } else {
-            if (offset < old_offset) {
+            if (start < old_start) {
                 /* Stop at the start of a running allocation */
-                nb_clusters = (old_offset - offset) >> s->cluster_bits;
+                nb_clusters = old_start - start;
             } else {
                 nb_clusters = 0;
             }
-- 
1.7.1

Re: [Qemu-devel] [PATCH] qcow2: fix range check

[Kevin Wolf]

Am 10.09.2011 10:23, schrieb Frediano Ziglio:
> QCowL2Meta::offset is not cluster aligned but only sector aligned
> however nb_clusters count cluster from cluster start.
> This fix range check. Note that old code have no corruption issues
> related to this check cause it only cause intersection to occur
> when shouldn't.

Are you sure? See below. (I think it doesn't corrupt the image, but for
a different reason)

> 
> Signed-off-by: Frediano Ziglio <freddy77@gmail.com>
> ---
>  block/qcow2-cluster.c |   14 +++++++-------
>  1 files changed, 7 insertions(+), 7 deletions(-)
> 
> diff --git a/block/qcow2-cluster.c b/block/qcow2-cluster.c
> index 428b5ad..2f76311 100644
> --- a/block/qcow2-cluster.c
> +++ b/block/qcow2-cluster.c
> @@ -776,17 +776,17 @@ again:
>       */
>      QLIST_FOREACH(old_alloc, &s->cluster_allocs, next_in_flight) {
>  
> -        uint64_t end_offset = offset + nb_clusters * s->cluster_size;
> -        uint64_t old_offset = old_alloc->offset;
> -        uint64_t old_end_offset = old_alloc->offset +
> -            old_alloc->nb_clusters * s->cluster_size;
> +        uint64_t start = offset >> s->cluster_bits;
> +        uint64_t end = start + nb_clusters;
> +        uint64_t old_start = old_alloc->offset >> s->cluster_bits;
> +        uint64_t old_end = old_start + old_alloc->nb_clusters;
>  
> -        if (end_offset < old_offset || offset > old_end_offset) {
> +        if (end < old_start || start > old_end) {
>              /* No intersection */

Consider request A from 0x0 + 0x1000 bytes and request B from 0x2000 +
0x1000 bytes. Both touch the same cluster and therefore should be
serialised, but 0x2000 > 0x1000, so we decided here that there is no
intersection and we don't have to care.

Note that this doesn't corrupt the image, qcow2 can handle parallel
requests allocating the same cluster. In qcow2_alloc_cluster_link_l2()
we get an additional COW operation, so performance will be hurt, but
correctness is maintained.

>          } else {
> -            if (offset < old_offset) {
> +            if (start < old_start) {
>                  /* Stop at the start of a running allocation */
> -                nb_clusters = (old_offset - offset) >> s->cluster_bits;
> +                nb_clusters = old_start - start;
>              } else {
>                  nb_clusters = 0;
>              }

Anyway, the patch looks good. Applied to the block branch.

Kevin

Re: [Qemu-devel] [PATCH] qcow2: fix range check

[Frediano Ziglio]

2011/9/12 Kevin Wolf <kwolf@redhat.com>:
> Am 10.09.2011 10:23, schrieb Frediano Ziglio:
>> QCowL2Meta::offset is not cluster aligned but only sector aligned
>> however nb_clusters count cluster from cluster start.
>> This fix range check. Note that old code have no corruption issues
>> related to this check cause it only cause intersection to occur
>> when shouldn't.
>
> Are you sure? See below. (I think it doesn't corrupt the image, but for
> a different reason)
>
>>
>> Signed-off-by: Frediano Ziglio <freddy77@gmail.com>
>> ---
>>  block/qcow2-cluster.c |   14 +++++++-------
>>  1 files changed, 7 insertions(+), 7 deletions(-)
>>
>> diff --git a/block/qcow2-cluster.c b/block/qcow2-cluster.c
>> index 428b5ad..2f76311 100644
>> --- a/block/qcow2-cluster.c
>> +++ b/block/qcow2-cluster.c
>> @@ -776,17 +776,17 @@ again:
>>       */
>>      QLIST_FOREACH(old_alloc, &s->cluster_allocs, next_in_flight) {
>>
>> -        uint64_t end_offset = offset + nb_clusters * s->cluster_size;
>> -        uint64_t old_offset = old_alloc->offset;
>> -        uint64_t old_end_offset = old_alloc->offset +
>> -            old_alloc->nb_clusters * s->cluster_size;
>> +        uint64_t start = offset >> s->cluster_bits;
>> +        uint64_t end = start + nb_clusters;
>> +        uint64_t old_start = old_alloc->offset >> s->cluster_bits;
>> +        uint64_t old_end = old_start + old_alloc->nb_clusters;
>>
>> -        if (end_offset < old_offset || offset > old_end_offset) {
>> +        if (end < old_start || start > old_end) {
>>              /* No intersection */
>
> Consider request A from 0x0 + 0x1000 bytes and request B from 0x2000 +
> 0x1000 bytes. Both touch the same cluster and therefore should be
> serialised, but 0x2000 > 0x1000, so we decided here that there is no
> intersection and we don't have to care.
>
> Note that this doesn't corrupt the image, qcow2 can handle parallel
> requests allocating the same cluster. In qcow2_alloc_cluster_link_l2()
> we get an additional COW operation, so performance will be hurt, but
> correctness is maintained.
>

I tested this adding some printf and also with strace and I can
confirm that current code serialize allocation.
Using ranges A (0-0x1000) and B (0x2000-0x3000) and assuming 0x10000
(64k) as cluster size you get
A:
   offset 0
   nb_clusters 1
B:
  offset 0x2000
  nb_clusters 1

So without the patch you get two ranges
A: 0-0x10000
B: 0x2000-0x12000
which intersects.

>>          } else {
>> -            if (offset < old_offset) {
>> +            if (start < old_start) {
>>                  /* Stop at the start of a running allocation */
>> -                nb_clusters = (old_offset - offset) >> s->cluster_bits;
>> +                nb_clusters = old_start - start;
>>              } else {
>>                  nb_clusters = 0;
>>              }
>
> Anyway, the patch looks good. Applied to the block branch.
>
> Kevin
>

Oh... I realize that ranges are [start, end) (end not inclusive) so
intersection test should be

   if (end <= old_start || start >= old_end) {

intead of

    if (end < old_start || start > old_end) {

However I don't understand why I got some small speed penalty with
this change (only done some small tests).

Frediano

Re: [Qemu-devel] [PATCH] qcow2: fix range check

[Kevin Wolf]

Am 13.09.2011 10:10, schrieb Frediano Ziglio:
> 2011/9/12 Kevin Wolf <kwolf@redhat.com>:
>> Am 10.09.2011 10:23, schrieb Frediano Ziglio:
>>> QCowL2Meta::offset is not cluster aligned but only sector aligned
>>> however nb_clusters count cluster from cluster start.
>>> This fix range check. Note that old code have no corruption issues
>>> related to this check cause it only cause intersection to occur
>>> when shouldn't.
>>
>> Are you sure? See below. (I think it doesn't corrupt the image, but for
>> a different reason)
>>
>>>
>>> Signed-off-by: Frediano Ziglio <freddy77@gmail.com>
>>> ---
>>>  block/qcow2-cluster.c |   14 +++++++-------
>>>  1 files changed, 7 insertions(+), 7 deletions(-)
>>>
>>> diff --git a/block/qcow2-cluster.c b/block/qcow2-cluster.c
>>> index 428b5ad..2f76311 100644
>>> --- a/block/qcow2-cluster.c
>>> +++ b/block/qcow2-cluster.c
>>> @@ -776,17 +776,17 @@ again:
>>>       */
>>>      QLIST_FOREACH(old_alloc, &s->cluster_allocs, next_in_flight) {
>>>
>>> -        uint64_t end_offset = offset + nb_clusters * s->cluster_size;
>>> -        uint64_t old_offset = old_alloc->offset;
>>> -        uint64_t old_end_offset = old_alloc->offset +
>>> -            old_alloc->nb_clusters * s->cluster_size;
>>> +        uint64_t start = offset >> s->cluster_bits;
>>> +        uint64_t end = start + nb_clusters;
>>> +        uint64_t old_start = old_alloc->offset >> s->cluster_bits;
>>> +        uint64_t old_end = old_start + old_alloc->nb_clusters;
>>>
>>> -        if (end_offset < old_offset || offset > old_end_offset) {
>>> +        if (end < old_start || start > old_end) {
>>>              /* No intersection */
>>
>> Consider request A from 0x0 + 0x1000 bytes and request B from 0x2000 +
>> 0x1000 bytes. Both touch the same cluster and therefore should be
>> serialised, but 0x2000 > 0x1000, so we decided here that there is no
>> intersection and we don't have to care.
>>
>> Note that this doesn't corrupt the image, qcow2 can handle parallel
>> requests allocating the same cluster. In qcow2_alloc_cluster_link_l2()
>> we get an additional COW operation, so performance will be hurt, but
>> correctness is maintained.
>>
> 
> I tested this adding some printf and also with strace and I can
> confirm that current code serialize allocation.
> Using ranges A (0-0x1000) and B (0x2000-0x3000) and assuming 0x10000
> (64k) as cluster size you get
> A:
>    offset 0
>    nb_clusters 1
> B:
>   offset 0x2000
>   nb_clusters 1
> 
> So without the patch you get two ranges
> A: 0-0x10000
> B: 0x2000-0x12000
> which intersects.
> 
>>>          } else {
>>> -            if (offset < old_offset) {
>>> +            if (start < old_start) {
>>>                  /* Stop at the start of a running allocation */
>>> -                nb_clusters = (old_offset - offset) >> s->cluster_bits;
>>> +                nb_clusters = old_start - start;
>>>              } else {
>>>                  nb_clusters = 0;
>>>              }
>>
>> Anyway, the patch looks good. Applied to the block branch.
>>
>> Kevin
>>
> 
> Oh... I realize that ranges are [start, end) (end not inclusive) so
> intersection test should be
> 
>    if (end <= old_start || start >= old_end) {
> 
> intead of
> 
>     if (end < old_start || start > old_end) {
> 
> However I don't understand why I got some small speed penalty with
> this change (only done some small tests).

Hm, I think you are right. How do you measure performance?

Kevin