[Qemu-devel] [PATCH 0/3] COW: Speed up writes

[Qemu-devel] [PATCH 0/3] COW: Speed up writes

[Charlie Shepherd]

Following on from Paolo's commits 26ae980 and 276cbc7, this patchset
implements some changes he recommended earlier which I didn't previously have
time to do while on GSoC.

Patch 2 was written initially I was intending to use cow_co_is_allocated in
Patch 3 and needed it to consider all sectors but in the end cow_find_streak
was sufficient, so it may not strictly be necessary.

Charlie Shepherd (3):
  COW: Speed up writes
  COW: Extend checking allocated bits to beyond one sector
  COW: Skip setting already set bits

 block/cow.c | 122 ++++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 74 insertions(+), 48 deletions(-)

-- 
1.8.4.rc3

[Qemu-devel] [PATCH 1/3] COW: Speed up writes

[Charlie Shepherd]

Process a whole sector's worth of COW bits by reading a sector, setting the bits, then writing it
out again. Make sure we only flush once, before writing metadata.

Signed-off-by: Charlie Shepherd <charlie@ctshepherd.com>
---
 block/cow.c | 79 ++++++++++++++++++++++++++++++++-----------------------------
 1 file changed, 41 insertions(+), 38 deletions(-)

diff --git a/block/cow.c b/block/cow.c
index 909c3e7..66f1478 100644
--- a/block/cow.c
+++ b/block/cow.c
@@ -103,40 +103,18 @@ static int cow_open(BlockDriverState *bs, QDict *options, int flags,
     return ret;
 }
 
-/*
- * XXX(hch): right now these functions are extremely inefficient.
- * We should just read the whole bitmap we'll need in one go instead.
- */
-static inline int cow_set_bit(BlockDriverState *bs, int64_t bitnum, bool *first)
+static inline void cow_set_bits(uint8_t *bitmap, int start, int64_t nb_sectors)
 {
-    uint64_t offset = sizeof(struct cow_header_v2) + bitnum / 8;
-    uint8_t bitmap;
-    int ret;
-
-    ret = bdrv_pread(bs->file, offset, &bitmap, sizeof(bitmap));
-    if (ret < 0) {
-       return ret;
-    }
-
-    if (bitmap & (1 << (bitnum % 8))) {
-        return 0;
-    }
-
-    if (*first) {
-        ret = bdrv_flush(bs->file);
-        if (ret < 0) {
-            return ret;
+    int64_t bitnum = start, last = start + nb_sectors;
+    while (bitnum < last) {
+        if ((bitnum & 7) == 0) {
+            bitmap[bitnum / 8] = 0xFF;
+            bitnum += 8;
+            continue;
         }
-        *first = false;
-    }
-
-    bitmap |= (1 << (bitnum % 8));
-
-    ret = bdrv_pwrite(bs->file, offset, &bitmap, sizeof(bitmap));
-    if (ret < 0) {
-       return ret;
+        bitmap[bitnum/8] |= (1 << (bitnum % 8));
+        bitnum++;
     }
-    return 0;
 }
 
 #define BITS_PER_BITMAP_SECTOR (512 * 8)
@@ -204,18 +182,43 @@ static int64_t coroutine_fn cow_co_get_block_status(BlockDriverState *bs,
 static int cow_update_bitmap(BlockDriverState *bs, int64_t sector_num,
         int nb_sectors)
 {
-    int error = 0;
-    int i;
+    int64_t bitnum = sector_num + sizeof(struct cow_header_v2) * 8;
+    uint64_t offset = (bitnum / 8) & -BDRV_SECTOR_SIZE;
     bool first = true;
 
-    for (i = 0; i < nb_sectors; i++) {
-        error = cow_set_bit(bs, sector_num + i, &first);
-        if (error) {
-            break;
+    while (nb_sectors) {
+        int ret;
+        uint8_t bitmap[BDRV_SECTOR_SIZE];
+
+        bitnum &= BITS_PER_BITMAP_SECTOR - 1;
+        int sector_bits = MIN(nb_sectors, BITS_PER_BITMAP_SECTOR - bitnum);
+
+        ret = bdrv_pread(bs->file, offset, &bitmap, sizeof(bitmap));
+        if (ret < 0) {
+            return ret;
         }
+
+        if (first) {
+            ret = bdrv_flush(bs->file);
+            if (ret < 0) {
+                return ret;
+            }
+            first = false;
+        }
+
+        cow_set_bits(bitmap, bitnum, sector_bits);
+
+        ret = bdrv_pwrite(bs->file, offset, &bitmap, sizeof(bitmap));
+        if (ret < 0) {
+            return ret;
+        }
+
+        bitnum += sector_bits;
+        nb_sectors -= sector_bits;
+        offset += BDRV_SECTOR_SIZE;
     }
 
-    return error;
+    return 0;
 }
 
 static int coroutine_fn cow_read(BlockDriverState *bs, int64_t sector_num,
-- 
1.8.4.rc3

[Qemu-devel] [PATCH 2/3] COW: Extend checking allocated bits to beyond one sector

[Charlie Shepherd]

cow_co_is_allocated() only checks one sector's worth of allocated bits before returning. This is
allowed but (slightly) inefficient, so extend it to check all of the file's metadata sectors.

Signed-off-by: Charlie Shepherd <charlie@ctshepherd.com>
---
 block/cow.c | 36 ++++++++++++++++++++++++++----------
 1 file changed, 26 insertions(+), 10 deletions(-)

diff --git a/block/cow.c b/block/cow.c
index 66f1478..4a081cb 100644
--- a/block/cow.c
+++ b/block/cow.c
@@ -152,18 +152,34 @@ static int coroutine_fn cow_co_is_allocated(BlockDriverState *bs,
 {
     int64_t bitnum = sector_num + sizeof(struct cow_header_v2) * 8;
     uint64_t offset = (bitnum / 8) & -BDRV_SECTOR_SIZE;
-    uint8_t bitmap[BDRV_SECTOR_SIZE];
-    int ret;
-    int changed;
+    bool first = true;
+    int changed, same = 0;
 
-    ret = bdrv_pread(bs->file, offset, &bitmap, sizeof(bitmap));
-    if (ret < 0) {
-        return ret;
-    }
+    do {
+        int ret;
+        uint8_t bitmap[BDRV_SECTOR_SIZE];
+
+        bitnum &= BITS_PER_BITMAP_SECTOR - 1;
+        int sector_bits = MIN(nb_sectors, BITS_PER_BITMAP_SECTOR - bitnum);
+
+        ret = bdrv_pread(bs->file, offset, &bitmap, sizeof(bitmap));
+        if (ret < 0) {
+            return ret;
+        }
+
+        if (first) {
+            changed = cow_test_bit(bitnum, bitmap);
+            first = false;
+        }
+
+        same += cow_find_streak(bitmap, changed, bitnum, nb_sectors);
+
+        bitnum += sector_bits;
+        nb_sectors -= sector_bits;
+        offset += BDRV_SECTOR_SIZE;
+    } while (nb_sectors);
 
-    bitnum &= BITS_PER_BITMAP_SECTOR - 1;
-    changed = cow_test_bit(bitnum, bitmap);
-    *num_same = cow_find_streak(bitmap, changed, bitnum, nb_sectors);
+    *num_same = same;
     return changed;
 }
 
-- 
1.8.4.rc3

[Qemu-devel] [PATCH 3/3] COW: Skip setting already set bits

[Charlie Shepherd]

Rather than unnecessarily setting bits that are already set, re-use cow_find_streak to find how
many bits are already set for this sector, and only set unset bits. Do this before the flush to
avoid it if no bits need to be set at all.

Signed-off-by: Charlie Shepherd <charlie@ctshepherd.com>
---
 block/cow.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/block/cow.c b/block/cow.c
index 4a081cb..d7d992b 100644
--- a/block/cow.c
+++ b/block/cow.c
@@ -203,7 +203,7 @@ static int cow_update_bitmap(BlockDriverState *bs, int64_t sector_num,
     bool first = true;
 
     while (nb_sectors) {
-        int ret;
+        int ret, set;
         uint8_t bitmap[BDRV_SECTOR_SIZE];
 
         bitnum &= BITS_PER_BITMAP_SECTOR - 1;
@@ -214,6 +214,13 @@ static int cow_update_bitmap(BlockDriverState *bs, int64_t sector_num,
             return ret;
         }
 
+        /* Skip over any already set bits */
+        set = cow_find_streak(bitmap, 1, bitnum, sector_bits);
+        if (set == sector_bits) {
+            continue;
+        }
+        bitnum += set;
+
         if (first) {
             ret = bdrv_flush(bs->file);
             if (ret < 0) {
-- 
1.8.4.rc3

Re: [Qemu-devel] [PATCH 1/3] COW: Speed up writes

[Paolo Bonzini]

Il 06/11/2013 13:23, Charlie Shepherd ha scritto:
> Process a whole sector's worth of COW bits by reading a sector, setting the bits, then writing it
> out again. Make sure we only flush once, before writing metadata.
> 
> Signed-off-by: Charlie Shepherd <charlie@ctshepherd.com>
> ---
>  block/cow.c | 79 ++++++++++++++++++++++++++++++++-----------------------------
>  1 file changed, 41 insertions(+), 38 deletions(-)
> 
> diff --git a/block/cow.c b/block/cow.c
> index 909c3e7..66f1478 100644
> --- a/block/cow.c
> +++ b/block/cow.c
> @@ -103,40 +103,18 @@ static int cow_open(BlockDriverState *bs, QDict *options, int flags,
>      return ret;
>  }
>  
> -/*
> - * XXX(hch): right now these functions are extremely inefficient.
> - * We should just read the whole bitmap we'll need in one go instead.
> - */
> -static inline int cow_set_bit(BlockDriverState *bs, int64_t bitnum, bool *first)
> +static inline void cow_set_bits(uint8_t *bitmap, int start, int64_t nb_sectors)
>  {
> -    uint64_t offset = sizeof(struct cow_header_v2) + bitnum / 8;
> -    uint8_t bitmap;
> -    int ret;
> -
> -    ret = bdrv_pread(bs->file, offset, &bitmap, sizeof(bitmap));
> -    if (ret < 0) {
> -       return ret;
> -    }
> -
> -    if (bitmap & (1 << (bitnum % 8))) {
> -        return 0;
> -    }
> -
> -    if (*first) {
> -        ret = bdrv_flush(bs->file);
> -        if (ret < 0) {
> -            return ret;
> +    int64_t bitnum = start, last = start + nb_sectors;
> +    while (bitnum < last) {
> +        if ((bitnum & 7) == 0) {

I think this is missing " && bitnum + 8 <= last" in the condition.

Otherwise looks good.

Paolo

> +            bitmap[bitnum / 8] = 0xFF;
> +            bitnum += 8;
> +            continue;
>          }
> -        *first = false;
> -    }
> -
> -    bitmap |= (1 << (bitnum % 8));
> -
> -    ret = bdrv_pwrite(bs->file, offset, &bitmap, sizeof(bitmap));
> -    if (ret < 0) {
> -       return ret;
> +        bitmap[bitnum/8] |= (1 << (bitnum % 8));
> +        bitnum++;
>      }
> -    return 0;
>  }
>  
>  #define BITS_PER_BITMAP_SECTOR (512 * 8)
> @@ -204,18 +182,43 @@ static int64_t coroutine_fn cow_co_get_block_status(BlockDriverState *bs,
>  static int cow_update_bitmap(BlockDriverState *bs, int64_t sector_num,
>          int nb_sectors)
>  {
> -    int error = 0;
> -    int i;
> +    int64_t bitnum = sector_num + sizeof(struct cow_header_v2) * 8;
> +    uint64_t offset = (bitnum / 8) & -BDRV_SECTOR_SIZE;
>      bool first = true;
>  
> -    for (i = 0; i < nb_sectors; i++) {
> -        error = cow_set_bit(bs, sector_num + i, &first);
> -        if (error) {
> -            break;
> +    while (nb_sectors) {
> +        int ret;
> +        uint8_t bitmap[BDRV_SECTOR_SIZE];
> +
> +        bitnum &= BITS_PER_BITMAP_SECTOR - 1;
> +        int sector_bits = MIN(nb_sectors, BITS_PER_BITMAP_SECTOR - bitnum);
> +
> +        ret = bdrv_pread(bs->file, offset, &bitmap, sizeof(bitmap));
> +        if (ret < 0) {
> +            return ret;
>          }
> +
> +        if (first) {
> +            ret = bdrv_flush(bs->file);
> +            if (ret < 0) {
> +                return ret;
> +            }
> +            first = false;
> +        }
> +
> +        cow_set_bits(bitmap, bitnum, sector_bits);
> +
> +        ret = bdrv_pwrite(bs->file, offset, &bitmap, sizeof(bitmap));
> +        if (ret < 0) {
> +            return ret;
> +        }
> +
> +        bitnum += sector_bits;
> +        nb_sectors -= sector_bits;
> +        offset += BDRV_SECTOR_SIZE;
>      }
>  
> -    return error;
> +    return 0;
>  }
>  
>  static int coroutine_fn cow_read(BlockDriverState *bs, int64_t sector_num,
> 

Re: [Qemu-devel] [PATCH 3/3] COW: Skip setting already set bits

[Paolo Bonzini]

Il 06/11/2013 13:23, Charlie Shepherd ha scritto:
> +        set = cow_find_streak(bitmap, 1, bitnum, sector_bits);
> +        if (set == sector_bits) {
> +            continue;

I think this shouldn't be a continue; these lines should be executed:

        bitnum += sector_bits;
        nb_sectors -= sector_bits;
        offset += BDRV_SECTOR_SIZE;

> +        }
> +        bitnum += set;

Here you're adjusting bitnum but not nb_sectors and sector_bits.

Paolo

Re: [Qemu-devel] [PATCH 2/3] COW: Extend checking allocated bits to beyond one sector

[Paolo Bonzini]

Il 06/11/2013 13:23, Charlie Shepherd ha scritto:
> cow_co_is_allocated() only checks one sector's worth of allocated bits before returning. This is
> allowed but (slightly) inefficient, so extend it to check all of the file's metadata sectors.
> 
> Signed-off-by: Charlie Shepherd <charlie@ctshepherd.com>
> ---
>  block/cow.c | 36 ++++++++++++++++++++++++++----------
>  1 file changed, 26 insertions(+), 10 deletions(-)
> 
> diff --git a/block/cow.c b/block/cow.c
> index 66f1478..4a081cb 100644
> --- a/block/cow.c
> +++ b/block/cow.c
> @@ -152,18 +152,34 @@ static int coroutine_fn cow_co_is_allocated(BlockDriverState *bs,
>  {
>      int64_t bitnum = sector_num + sizeof(struct cow_header_v2) * 8;
>      uint64_t offset = (bitnum / 8) & -BDRV_SECTOR_SIZE;
> -    uint8_t bitmap[BDRV_SECTOR_SIZE];
> -    int ret;
> -    int changed;
> +    bool first = true;
> +    int changed, same = 0;
>  
> -    ret = bdrv_pread(bs->file, offset, &bitmap, sizeof(bitmap));
> -    if (ret < 0) {
> -        return ret;
> -    }
> +    do {
> +        int ret;
> +        uint8_t bitmap[BDRV_SECTOR_SIZE];
> +
> +        bitnum &= BITS_PER_BITMAP_SECTOR - 1;
> +        int sector_bits = MIN(nb_sectors, BITS_PER_BITMAP_SECTOR - bitnum);
> +
> +        ret = bdrv_pread(bs->file, offset, &bitmap, sizeof(bitmap));
> +        if (ret < 0) {
> +            return ret;
> +        }
> +
> +        if (first) {
> +            changed = cow_test_bit(bitnum, bitmap);
> +            first = false;
> +        }
> +
> +        same += cow_find_streak(bitmap, changed, bitnum, nb_sectors);
> +
> +        bitnum += sector_bits;
> +        nb_sectors -= sector_bits;
> +        offset += BDRV_SECTOR_SIZE;
> +    } while (nb_sectors);
>  
> -    bitnum &= BITS_PER_BITMAP_SECTOR - 1;
> -    changed = cow_test_bit(bitnum, bitmap);
> -    *num_same = cow_find_streak(bitmap, changed, bitnum, nb_sectors);
> +    *num_same = same;
>      return changed;
>  }
>  
> 

This one is good.

Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>

Re: [Qemu-devel] [PATCH 3/3] COW: Skip setting already set bits

[Charlie Shepherd]

On 06/11/2013 12:29, Paolo Bonzini wrote:
> Il 06/11/2013 13:23, Charlie Shepherd ha scritto:
>> +        set = cow_find_streak(bitmap, 1, bitnum, sector_bits);
>> +        if (set == sector_bits) {
>> +            continue;
> I think this shouldn't be a continue; these lines should be executed:
>
>          bitnum += sector_bits;
>          nb_sectors -= sector_bits;
>          offset += BDRV_SECTOR_SIZE;

Good point, this is basically a poor man's for-loop. I'll turn it into a 
for loop then continue will make sense here.

>> +        }
>> +        bitnum += set;
> Here you're adjusting bitnum but not nb_sectors and sector_bits.

Good catch.

Charlie

Re: [Qemu-devel] [PATCH 0/3] COW: Speed up writes

[Paolo Bonzini]

Il 06/11/2013 13:23, Charlie Shepherd ha scritto:
> Patch 2 was written initially I was intending to use cow_co_is_allocated in
> Patch 3 and needed it to consider all sectors but in the end cow_find_streak
> was sufficient, so it may not strictly be necessary.

Patch 2 can still speed up reads that cross a sector boundary from 4 I/O
operations (2 for the bitmap, 2 for the data) to 3 (only 1 for the data).

Paolo