[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-block] [Qemu-devel] [PATCH v2 06/13] HBitmap: Introduce "meta"
From: |
John Snow |
Subject: |
Re: [Qemu-block] [Qemu-devel] [PATCH v2 06/13] HBitmap: Introduce "meta" bitmap to track bit changes |
Date: |
Mon, 25 Jan 2016 17:02:42 -0500 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 |
On 01/20/2016 01:11 AM, Fam Zheng wrote:
> Upon each bit toggle, the corresponding bit in the meta bitmap will be
> set.
>
> Signed-off-by: Fam Zheng <address@hidden>
Reviewed-by: John Snow <address@hidden>
> ---
> include/qemu/hbitmap.h | 17 +++++++++++++
> util/hbitmap.c | 66
> ++++++++++++++++++++++++++++++++++++++------------
> 2 files changed, 68 insertions(+), 15 deletions(-)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index bb94a00..595ad65 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -181,6 +181,23 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap
> *hb, uint64_t first);
> */
> unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>
> +/* hbitmap_create_meta:
> + * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
> + * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
> + * free it.
> + *
> + * @hb: The HBitmap to operate on.
> + * @chunk_size: How many bits in @hb does one bit in the meta track.
> + */
> +HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size);
> +
> +/* hbitmap_free_meta:
> + * Free the meta bitmap of @hb.
> + *
> + * @hb: The HBitmap whose meta bitmap should be freed.
> + */
> +void hbitmap_free_meta(HBitmap *hb);
> +
> /**
> * hbitmap_iter_next:
> * @hbi: HBitmapIter to operate on.
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 50b888f..79f6236 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -81,6 +81,9 @@ struct HBitmap {
> */
> int granularity;
>
> + /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */
> + HBitmap *meta;
> +
> /* A number of progressively less coarse bitmaps (i.e. level 0 is the
> * coarsest). Each bit in level N represents a word in level N+1 that
> * has a set bit, except the last level where each bit represents the
> @@ -212,25 +215,27 @@ static uint64_t hb_count_between(HBitmap *hb, uint64_t
> start, uint64_t last)
> }
>
> /* Setting starts at the last layer and propagates up if an element
> - * changes from zero to non-zero.
> + * changes.
> */
> static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t
> last)
> {
> unsigned long mask;
> - bool changed;
> + unsigned long old;
>
> assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
> assert(start <= last);
>
> mask = 2UL << (last & (BITS_PER_LONG - 1));
> mask -= 1UL << (start & (BITS_PER_LONG - 1));
> - changed = (*elem == 0);
> + old = *elem;
> *elem |= mask;
> - return changed;
> + return old != *elem;
> }
>
> -/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
> -static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t
> last)
> +/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
> + * Returns true if at least one bit is changed. */
> +static bool hb_set_between(HBitmap *hb, int level, uint64_t start,
> + uint64_t last)
> {
> size_t pos = start >> BITS_PER_LEVEL;
> size_t lastpos = last >> BITS_PER_LEVEL;
> @@ -259,22 +264,27 @@ static void hb_set_between(HBitmap *hb, int level,
> uint64_t start, uint64_t last
> if (level > 0 && changed) {
> hb_set_between(hb, level - 1, pos, lastpos);
> }
> + return changed;
> }
>
> void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
> {
> /* Compute range in the last layer. */
> + uint64_t first, n;
> uint64_t last = start + count - 1;
>
> trace_hbitmap_set(hb, start, count,
> start >> hb->granularity, last >> hb->granularity);
>
> - start >>= hb->granularity;
> + first = start >> hb->granularity;
> last >>= hb->granularity;
> - count = last - start + 1;
> + n = last - first + 1;
>
> - hb->count += count - hb_count_between(hb, start, last);
> - hb_set_between(hb, HBITMAP_LEVELS - 1, start, last);
> + hb->count += n - hb_count_between(hb, first, last);
> + if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&
> + hb->meta) {
> + hbitmap_set(hb->meta, start, count);
> + }
> }
>
> /* Resetting works the other way round: propagate up if the new
> @@ -295,8 +305,10 @@ static inline bool hb_reset_elem(unsigned long *elem,
> uint64_t start, uint64_t l
> return blanked;
> }
>
> -/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
> -static void hb_reset_between(HBitmap *hb, int level, uint64_t start,
> uint64_t last)
> +/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
> + * Returns true if at least one bit is changed. */
> +static bool hb_reset_between(HBitmap *hb, int level, uint64_t start,
> + uint64_t last)
> {
> size_t pos = start >> BITS_PER_LEVEL;
> size_t lastpos = last >> BITS_PER_LEVEL;
> @@ -339,21 +351,28 @@ static void hb_reset_between(HBitmap *hb, int level,
> uint64_t start, uint64_t la
> if (level > 0 && changed) {
> hb_reset_between(hb, level - 1, pos, lastpos);
> }
> +
> + return changed;
> +
> }
>
> void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
> {
> /* Compute range in the last layer. */
> + uint64_t first;
> uint64_t last = start + count - 1;
>
> trace_hbitmap_reset(hb, start, count,
> start >> hb->granularity, last >> hb->granularity);
>
> - start >>= hb->granularity;
> + first = start >> hb->granularity;
> last >>= hb->granularity;
>
> - hb->count -= hb_count_between(hb, start, last);
> - hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
> + hb->count -= hb_count_between(hb, first, last);
> + if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
> + hb->meta) {
> + hbitmap_set(hb->meta, start, count);
> + }
> }
>
> void hbitmap_reset_all(HBitmap *hb)
> @@ -381,6 +400,7 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
> void hbitmap_free(HBitmap *hb)
> {
> unsigned i;
> + assert(!hb->meta);
> for (i = HBITMAP_LEVELS; i-- > 0; ) {
> g_free(hb->levels[i]);
> }
> @@ -493,3 +513,19 @@ bool hbitmap_merge(HBitmap *a, const HBitmap *b)
>
> return true;
> }
> +
> +HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size)
> +{
> + assert(!(chunk_size & (chunk_size - 1)));
> + assert(!hb->meta);
> + hb->meta = hbitmap_alloc(hb->size << hb->granularity,
> + hb->granularity + ctz32(chunk_size));
> + return hb->meta;
> +}
> +
> +void hbitmap_free_meta(HBitmap *hb)
> +{
> + assert(hb->meta);
> + hbitmap_free(hb->meta);
> + hb->meta = NULL;
> +}
>
- [Qemu-block] [PATCH v2 01/13] backup: Use Bitmap to replace "s->bitmap", (continued)
- [Qemu-block] [PATCH v2 01/13] backup: Use Bitmap to replace "s->bitmap", Fam Zheng, 2016/01/20
- [Qemu-block] [PATCH v2 02/13] typedefs: Add BdrvDirtyBitmap, Fam Zheng, 2016/01/20
- [Qemu-block] [PATCH v2 03/13] block: Move block dirty bitmap code to separate files, Fam Zheng, 2016/01/20
- [Qemu-block] [PATCH v2 04/13] block: Remove unused typedef of BlockDriverDirtyHandler, Fam Zheng, 2016/01/20
- [Qemu-block] [PATCH v2 05/13] block: Hide HBitmap in block dirty bitmap interface, Fam Zheng, 2016/01/20
- [Qemu-block] [PATCH v2 06/13] HBitmap: Introduce "meta" bitmap to track bit changes, Fam Zheng, 2016/01/20
- Re: [Qemu-block] [Qemu-devel] [PATCH v2 06/13] HBitmap: Introduce "meta" bitmap to track bit changes,
John Snow <=
- [Qemu-block] [PATCH v2 07/13] tests: Add test code for meta bitmap, Fam Zheng, 2016/01/20
- [Qemu-block] [PATCH v2 08/13] block: Support meta dirty bitmap, Fam Zheng, 2016/01/20
Re: [Qemu-block] [Qemu-devel] [PATCH v2 08/13] block: Support meta dirty bitmap, John Snow, 2016/01/25