[Qemu-devel] [PATCH] Make cow_co_is_allocated and cow_update_bitmap more efficient

[Qemu-devel] [PATCH] Make cow_co_is_allocated and cow_update_bitmap more efficient

[Charlie Shepherd]

cow_co_is_allocated and cow_update_bitmap set bits by reading the relevant
word, setting the specific bit in it and writing it back. These functions set
a number of contiguous bits however, so this is an extremely inefficient way
of doing this. This patch converts them to read the whole bitmap they need in
one go, update it and then write it out, which should be much more more
efficient.

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

diff --git a/block/cow.c b/block/cow.c
index 1cc2e89..87ebef6 100644
--- a/block/cow.c
+++ b/block/cow.c
@@ -102,84 +102,92 @@ 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)
-{
-    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;
-    }
-
-    bitmap |= (1 << (bitnum % 8));
-
-    ret = bdrv_pwrite_sync(bs->file, offset, &bitmap, sizeof(bitmap));
-    if (ret < 0) {
-       return ret;
-    }
-    return 0;
-}
-
-static inline int is_bit_set(BlockDriverState *bs, int64_t bitnum)
-{
-    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;
-    }
-
-    return !!(bitmap & (1 << (bitnum % 8)));
-}
-
 /* Return true if first block has been changed (ie. current version is
  * in COW file).  Set the number of continuous blocks for which that
  * is true. */
 static int coroutine_fn cow_co_is_allocated(BlockDriverState *bs,
         int64_t sector_num, int nb_sectors, int *num_same)
 {
-    int changed;
+    int ret, changed;
+    uint64_t offset = sizeof(struct cow_header_v2) + sector_num / 8;
+
+    int init_bits = (sector_num % 8) ? (8 - (sector_num % 8)) : 0;
+    int remaining = sector_num - init_bits;
+    int full_bytes = remaining / 8;
+    int trail = remaining % 8;
+
+    int len = !!init_bits + full_bytes + !!trail;
+    uint8_t buf[len];
 
     if (nb_sectors == 0) {
-	*num_same = nb_sectors;
-	return 0;
+        *num_same = nb_sectors;
+        return 0;
     }
 
-    changed = is_bit_set(bs, sector_num);
-    if (changed < 0) {
-        return 0; /* XXX: how to return I/O errors? */
+    ret = bdrv_pread(bs->file, offset, buf, len);
+    if (ret < 0) {
+        return ret;
     }
 
+#define is_bit_set(b) (!!(buf[(b)/8] & (1 << ((b) % 8))))
+
+    changed = is_bit_set(sector_num);
     for (*num_same = 1; *num_same < nb_sectors; (*num_same)++) {
-	if (is_bit_set(bs, sector_num + *num_same) != changed)
-	    break;
+        if (is_bit_set(sector_num + *num_same) != changed) {
+            break;
+        }
     }
 
+#undef is_bit_set
+
     return changed;
 }
 
+/* Set the bits from sector_num to sector_num + nb_sectors in the bitmap of
+ * bs->file. */
 static int cow_update_bitmap(BlockDriverState *bs, int64_t sector_num,
         int nb_sectors)
 {
-    int error = 0;
-    int i;
+    int ret;
+    uint64_t offset = sizeof(struct cow_header_v2) + sector_num / 8;
 
-    for (i = 0; i < nb_sectors; i++) {
-        error = cow_set_bit(bs, sector_num + i);
-        if (error) {
-            break;
-        }
+    int init_bits = (sector_num % 8) ? (8 - (sector_num % 8)) : 0;
+    int remaining = sector_num - init_bits;
+    int full_bytes = remaining / 8;
+    int trail = remaining % 8;
+
+    int len = !!init_bits + full_bytes + !!trail;
+    uint8_t buf[len];
+
+    ret = bdrv_pread(bs->file, offset, buf, len);
+    if (ret < 0) {
+        return ret;
+    }
+
+    /* Do sector_num -> nearest byte boundary */
+    if (init_bits) {
+        /* This sets the highest init_bits bits in the byte */
+        uint8_t bits = ((1 << init_bits) - 1) << (8 - init_bits);
+        buf[0] |= bits;
+    }
+
+    if (full_bytes) {
+        memset(&buf[!!init_bits], ~0, full_bytes);
+    }
+
+    /* Set the trailing bits in the final byte */
+    if (trail) {
+        /* This sets the lowest trail bits in the byte */
+        uint8_t bits = (1 << trail) - 1;
+        buf[len - 1] |= bits;
+    }
+
+    ret = bdrv_pwrite_sync(bs->file, offset, buf, len);
+    if (ret < 0) {
+        return ret;
     }
 
-    return error;
+    return 0;
 }
 
 static int coroutine_fn cow_read(BlockDriverState *bs, int64_t sector_num,
-- 
1.8.3.2

Re: [Qemu-devel] [PATCH] Make cow_co_is_allocated and cow_update_bitmap more efficient

[Paolo Bonzini]

Il 20/08/2013 15:42, Charlie Shepherd ha scritto:
> cow_co_is_allocated and cow_update_bitmap set bits by reading the relevant
> word, setting the specific bit in it and writing it back. These functions set
> a number of contiguous bits however, so this is an extremely inefficient way
> of doing this. This patch converts them to read the whole bitmap they need in
> one go, update it and then write it out, which should be much more more
> efficient.
> 
> Signed-off-by: Charlie Shepherd <charlie@ctshepherd.com>
> ---
>  block/cow.c | 116 ++++++++++++++++++++++++++++++++----------------------------
>  1 file changed, 62 insertions(+), 54 deletions(-)
> 
> diff --git a/block/cow.c b/block/cow.c
> index 1cc2e89..87ebef6 100644
> --- a/block/cow.c
> +++ b/block/cow.c
> @@ -102,84 +102,92 @@ 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)
> -{
> -    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;
> -    }
> -
> -    bitmap |= (1 << (bitnum % 8));
> -
> -    ret = bdrv_pwrite_sync(bs->file, offset, &bitmap, sizeof(bitmap));
> -    if (ret < 0) {
> -       return ret;
> -    }
> -    return 0;
> -}
> -
> -static inline int is_bit_set(BlockDriverState *bs, int64_t bitnum)
> -{
> -    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;
> -    }
> -
> -    return !!(bitmap & (1 << (bitnum % 8)));
> -}
> -
>  /* Return true if first block has been changed (ie. current version is
>   * in COW file).  Set the number of continuous blocks for which that
>   * is true. */
>  static int coroutine_fn cow_co_is_allocated(BlockDriverState *bs,
>          int64_t sector_num, int nb_sectors, int *num_same)
>  {
> -    int changed;
> +    int ret, changed;
> +    uint64_t offset = sizeof(struct cow_header_v2) + sector_num / 8;
> +
> +    int init_bits = (sector_num % 8) ? (8 - (sector_num % 8)) : 0;
> +    int remaining = sector_num - init_bits;
> +    int full_bytes = remaining / 8;
> +    int trail = remaining % 8;
> +
> +    int len = !!init_bits + full_bytes + !!trail;
> +    uint8_t buf[len];
>  
>      if (nb_sectors == 0) {
> -	*num_same = nb_sectors;
> -	return 0;
> +        *num_same = nb_sectors;
> +        return 0;
>      }
>  
> -    changed = is_bit_set(bs, sector_num);
> -    if (changed < 0) {
> -        return 0; /* XXX: how to return I/O errors? */
> +    ret = bdrv_pread(bs->file, offset, buf, len);
> +    if (ret < 0) {
> +        return ret;
>      }
>  
> +#define is_bit_set(b) (!!(buf[(b)/8] & (1 << ((b) % 8))))
> +
> +    changed = is_bit_set(sector_num);
>      for (*num_same = 1; *num_same < nb_sectors; (*num_same)++) {
> -	if (is_bit_set(bs, sector_num + *num_same) != changed)
> -	    break;
> +        if (is_bit_set(sector_num + *num_same) != changed) {
> +            break;
> +        }
>      }
>  
> +#undef is_bit_set
> +
>      return changed;
>  }
>  
> +/* Set the bits from sector_num to sector_num + nb_sectors in the bitmap of
> + * bs->file. */
>  static int cow_update_bitmap(BlockDriverState *bs, int64_t sector_num,
>          int nb_sectors)
>  {
> -    int error = 0;
> -    int i;
> +    int ret;
> +    uint64_t offset = sizeof(struct cow_header_v2) + sector_num / 8;
>  
> -    for (i = 0; i < nb_sectors; i++) {
> -        error = cow_set_bit(bs, sector_num + i);
> -        if (error) {
> -            break;
> -        }
> +    int init_bits = (sector_num % 8) ? (8 - (sector_num % 8)) : 0;
> +    int remaining = sector_num - init_bits;
> +    int full_bytes = remaining / 8;
> +    int trail = remaining % 8;
> +
> +    int len = !!init_bits + full_bytes + !!trail;
> +    uint8_t buf[len];
> +
> +    ret = bdrv_pread(bs->file, offset, buf, len);
> +    if (ret < 0) {
> +        return ret;
> +    }
> +
> +    /* Do sector_num -> nearest byte boundary */
> +    if (init_bits) {
> +        /* This sets the highest init_bits bits in the byte */
> +        uint8_t bits = ((1 << init_bits) - 1) << (8 - init_bits);
> +        buf[0] |= bits;
> +    }
> +
> +    if (full_bytes) {
> +        memset(&buf[!!init_bits], ~0, full_bytes);
> +    }
> +
> +    /* Set the trailing bits in the final byte */
> +    if (trail) {
> +        /* This sets the lowest trail bits in the byte */
> +        uint8_t bits = (1 << trail) - 1;
> +        buf[len - 1] |= bits;
> +    }
> +
> +    ret = bdrv_pwrite_sync(bs->file, offset, buf, len);
> +    if (ret < 0) {
> +        return ret;
>      }
>  
> -    return error;
> +    return 0;
>  }
>  
>  static int coroutine_fn cow_read(BlockDriverState *bs, int64_t sector_num,
> 

I had very similar patches in my series to add get_block_status...

Paolo

Re: [Qemu-devel] [PATCH] Make cow_co_is_allocated and cow_update_bitmap more efficient

[Charlie Shepherd]

On 20/08/2013 14:45, Paolo Bonzini wrote:
> I had very similar patches in my series to add get_block_status...

Ah, sorry if I've duplicated something you've already done. Stefan 
encouraged me to contribute to an area of QEMU I found interesting and 
seeing the XXX I thought I'd take a shot at improving the code. Where 
should I look in the future for patches like this?


Charlie

Re: [Qemu-devel] [PATCH] Make cow_co_is_allocated and cow_update_bitmap more efficient

[Paolo Bonzini]

Il 20/08/2013 15:50, Charlie Shepherd ha scritto:
> On 20/08/2013 14:45, Paolo Bonzini wrote:
>> I had very similar patches in my series to add get_block_status...
> 
> Ah, sorry if I've duplicated something you've already done. Stefan
> encouraged me to contribute to an area of QEMU I found interesting and
> seeing the XXX I thought I'd take a shot at improving the code. Where
> should I look in the future for patches like this?

There is still room for improvement in this area.  You can compare my
patches and yours, they follow very different ideas.

I could pick up your patch in my series too, actually, if they're
reviewed fast enough (I'm not sure I'll have the cycles to do that,
unfortunately).

Paolo