[08/13] block: Support meta dirty bitmap

The added group of operations enables tracking of the changed bits in
the dirty bitmap.

Signed-off-by: Fam Zheng <famz@redhat.com>
---
 block/dirty-bitmap.c         | 51 ++++++++++++++++++++++++++++++++++++++++++++
 include/block/dirty-bitmap.h |  9 ++++++++
 2 files changed, 60 insertions(+)

On 01/04/2016 05:27 AM, Fam Zheng wrote:
> The added group of operations enables tracking of the changed bits in
> the dirty bitmap.
> 
> Signed-off-by: Fam Zheng <famz@redhat.com>
> ---
>  block/dirty-bitmap.c         | 51 ++++++++++++++++++++++++++++++++++++++++++++
>  include/block/dirty-bitmap.h |  9 ++++++++
>  2 files changed, 60 insertions(+)
> 
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 53cf88d..4314659 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -37,6 +37,7 @@
>   */
>  struct BdrvDirtyBitmap {
>      HBitmap *bitmap;            /* Dirty sector bitmap implementation */
> +    HBitmap *meta;              /* Meta dirty bitmap */

IMO, this gets a little strange -- if I understand correctly, you're
using this meta pointer as a cache for the meta bitmap contained within
"bitmap," and not actually creating a new "standalone" HBitmap.

Since it has the same type as the prior "bitmap" member, though, it
makes it look like they're both the same kind of object ... when in
fact, one is the child of the other.

It's probably fine, but I was momentarily confused. I don't have a
better suggestion.

>      BdrvDirtyBitmap *successor; /* Anonymous child; implies frozen status */
>      char *name;                 /* Optional non-empty unique ID */
>      int64_t size;               /* Size of the bitmap (Number of sectors) */
> @@ -102,6 +103,56 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
>      return bitmap;
>  }
>  
> +/* bdrv_create_meta_dirty_bitmap
> + *
> + * Create a meta dirty bitmap that tracks the changes of bits in @bitmap. I.e.
> + * when a dirty status bit in @bitmap is changed (either from reset to set or
> + * the other way around), its respective meta dirty bitmap bit will be marked
> + * dirty as well.
> + *
> + * @bitmap: the block dirty bitmap for which to create a meta dirty bitmap.
> + * @granularity: how many bytes of bitmap data does each bit in the meta bitmap
> + * track.
> + */
> +void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> +                                   int granularity)
> +{
> +    assert(!bitmap->meta);
> +    bitmap->meta = hbitmap_create_meta(bitmap->bitmap,
> +                                       BDRV_SECTOR_SIZE * BITS_PER_BYTE);
> +}
> +
> +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
> +{
> +    assert(bitmap->meta);
> +    hbitmap_free(bitmap->meta);

This leaves a dangling pointer inside the Hbitmap, no?

> +    bitmap->meta = NULL;
> +}
> +
> +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
> +                               BdrvDirtyBitmap *bitmap, int64_t sector,
> +                               int nb_sectors)
> +{
> +    uint64_t i;
> +    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
> +
> +    /* To optimize: we can make hbitmap to internally check the range in a
> +     * coarse level, or at least do it word by word. */
> +    for (i = sector; i < sector + nb_sectors; i += gran) {
> +        if (hbitmap_get(bitmap->meta, i)) {
> +            return true;
> +        }
> +    }
> +    return false;
> +}
> +

In essence get_meta() is a greedy algorithm that simply returns true if
anything is set between [sector, sector + nb_sectors], yes?

Is this more useful than just using an iterator directly on the
meta-bitmap?

I haven't finished reading but, I imagine that:

- If we need to check to see what is dirty specifically, we can just use
the iterator. If the iterator doesn't return anything, we know it's
empty. If it does return, we know exactly what's dirty.
- If we need to explicitly check for emptiness in general, we can use
the internal popcount.


I'm not sure when a 'dirty range bool' will be explicitly useful all by
itself, but maybe that becomes obvious later.

> +void bdrv_dirty_bitmap_reset_meta(BlockDriverState *bs,
> +                                  BdrvDirtyBitmap *bitmap, int64_t sector,
> +                                  int nb_sectors)
> +{
> +    hbitmap_reset(bitmap->meta, sector, nb_sectors);
> +}
> +
>  bool bdrv_dirty_bitmap_frozen(BdrvDirtyBitmap *bitmap)
>  {
>      return bitmap->successor;
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 16bb15a..0715220 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -8,6 +8,9 @@ BdrvDirtyBitmap *bdrv_create_dirty_bitmap(BlockDriverState *bs,
>                                            uint32_t granularity,
>                                            const char *name,
>                                            Error **errp);
> +void bdrv_create_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap,
> +                                   int granularity);
> +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap);
>  int bdrv_dirty_bitmap_create_successor(BlockDriverState *bs,
>                                         BdrvDirtyBitmap *bitmap,
>                                         Error **errp);
> @@ -34,6 +37,12 @@ void bdrv_set_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>                             int64_t cur_sector, int nr_sectors);
>  void bdrv_reset_dirty_bitmap(BdrvDirtyBitmap *bitmap,
>                               int64_t cur_sector, int nr_sectors);
> +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
> +                               BdrvDirtyBitmap *bitmap, int64_t sector,
> +                               int nb_sectors);
> +void bdrv_dirty_bitmap_reset_meta(BlockDriverState *bs,
> +                                  BdrvDirtyBitmap *bitmap, int64_t sector,
> +                                  int nb_sectors);
>  BdrvDirtyBitmapIter *bdrv_dirty_iter_new(BdrvDirtyBitmap *bitmap,
>                                           uint64_t first_sector);
>  void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter);
>

On Thu, 01/07 14:30, John Snow wrote:
> > +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
> > +{
> > +    assert(bitmap->meta);
> > +    hbitmap_free(bitmap->meta);
> 
> This leaves a dangling pointer inside the Hbitmap, no?

Yes, will fix.

> 
> > +    bitmap->meta = NULL;
> > +}
> > +
> > +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
> > +                               BdrvDirtyBitmap *bitmap, int64_t sector,
> > +                               int nb_sectors)
> > +{
> > +    uint64_t i;
> > +    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
> > +
> > +    /* To optimize: we can make hbitmap to internally check the range in a
> > +     * coarse level, or at least do it word by word. */
> > +    for (i = sector; i < sector + nb_sectors; i += gran) {
> > +        if (hbitmap_get(bitmap->meta, i)) {
> > +            return true;
> > +        }
> > +    }
> > +    return false;
> > +}
> > +
> 
> In essence get_meta() is a greedy algorithm that simply returns true if
> anything is set between [sector, sector + nb_sectors], yes?
> 
> Is this more useful than just using an iterator directly on the
> meta-bitmap?
> 
> I haven't finished reading but, I imagine that:
> 
> - If we need to check to see what is dirty specifically, we can just use
> the iterator. If the iterator doesn't return anything, we know it's
> empty. If it does return, we know exactly what's dirty.
> - If we need to explicitly check for emptiness in general, we can use
> the internal popcount.
> 
> 
> I'm not sure when a 'dirty range bool' will be explicitly useful all by
> itself, but maybe that becomes obvious later.

It's for the meta bitmap user to decide. In the case of persistent dirty bitmap
driver, I simply check whether the range of write request is meta-dirty, and
write the corresponding dirty bitmap range accordingly, rather than splitting
one write req into potentially multiple bit ranges that are meta-dirty. I think
this is reasonable, hence the interface.

On 01/20/2016 01:07 AM, Fam Zheng wrote:
> On Thu, 01/07 14:30, John Snow wrote:
>>> +void bdrv_release_meta_dirty_bitmap(BdrvDirtyBitmap *bitmap)
>>> +{
>>> +    assert(bitmap->meta);
>>> +    hbitmap_free(bitmap->meta);
>>
>> This leaves a dangling pointer inside the Hbitmap, no?
> 
> Yes, will fix.
> 
>>
>>> +    bitmap->meta = NULL;
>>> +}
>>> +
>>> +int bdrv_dirty_bitmap_get_meta(BlockDriverState *bs,
>>> +                               BdrvDirtyBitmap *bitmap, int64_t sector,
>>> +                               int nb_sectors)
>>> +{
>>> +    uint64_t i;
>>> +    int gran = bdrv_dirty_bitmap_granularity(bitmap) >> BDRV_SECTOR_BITS;
>>> +
>>> +    /* To optimize: we can make hbitmap to internally check the range in a
>>> +     * coarse level, or at least do it word by word. */
>>> +    for (i = sector; i < sector + nb_sectors; i += gran) {
>>> +        if (hbitmap_get(bitmap->meta, i)) {
>>> +            return true;
>>> +        }
>>> +    }
>>> +    return false;
>>> +}
>>> +
>>
>> In essence get_meta() is a greedy algorithm that simply returns true if
>> anything is set between [sector, sector + nb_sectors], yes?
>>
>> Is this more useful than just using an iterator directly on the
>> meta-bitmap?
>>
>> I haven't finished reading but, I imagine that:
>>
>> - If we need to check to see what is dirty specifically, we can just use
>> the iterator. If the iterator doesn't return anything, we know it's
>> empty. If it does return, we know exactly what's dirty.
>> - If we need to explicitly check for emptiness in general, we can use
>> the internal popcount.
>>
>>
>> I'm not sure when a 'dirty range bool' will be explicitly useful all by
>> itself, but maybe that becomes obvious later.
> 
> It's for the meta bitmap user to decide. In the case of persistent dirty bitmap
> driver, I simply check whether the range of write request is meta-dirty, and
> write the corresponding dirty bitmap range accordingly, rather than splitting
> one write req into potentially multiple bit ranges that are meta-dirty. I think
> this is reasonable, hence the interface.
> 

OK, I think I see what the use case is, thanks.