Re: [Qemu-block] [PATCH v4 15/20] block: Resize bitmaps on bdrv_truncate
On Tue, Apr 07, 2015 at 12:45:30PM -0400, John Snow wrote:
>
>
> On 04/07/2015 08:57 AM, Stefan Hajnoczi wrote:
> >On Thu, Apr 02, 2015 at 11:57:59AM -0400, John Snow wrote:
> >>
> >>
> >>On 04/02/2015 09:37 AM, Stefan Hajnoczi wrote:
> >>>On Fri, Mar 20, 2015 at 03:16:58PM -0400, John Snow wrote:
> +void hbitmap_truncate(HBitmap *hb, uint64_t size)
> +{
> +bool shrink;
> +unsigned i;
> +uint64_t num_elements = size;
> +uint64_t old;
> +
> +/* Size comes in as logical elements, adjust for granularity. */
> +size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
> +assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
> +shrink = size < hb->size;
> +
> +/* bit sizes are identical; nothing to do. */
> +if (size == hb->size) {
> +return;
> +}
> +
> +/* If we're losing bits, let's clear those bits before we invalidate
> all of
> + * our invariants. This helps keep the bitcount consistent, and will
> prevent
> + * us from carrying around garbage bits beyond the end of the map.
> + *
> + * Because clearing bits past the end of map might reset bits we
> care about
> + * within the array, record the current value of the last bit we're
> keeping.
> + */
> +if (shrink) {
> +bool set = hbitmap_get(hb, num_elements - 1);
> +uint64_t fix_count = (hb->size << hb->granularity) -
> num_elements;
> +
> +assert(fix_count);
> +hbitmap_reset(hb, num_elements, fix_count);
> +if (set) {
> +hbitmap_set(hb, num_elements - 1, 1);
> +}
> >>>
> >>>Why is it necessary to set the last bit (if it was set)? The comment
> >>>isn't clear to me.
> >>>
> >>
> >>Sure. The granularity of the bitmap provides us with virtual bit groups. for
> >>a granularity of say g=2, we have 2^2 virtual bits per every real bit:
> >>
> >>101 in memory is treated, virtually, as .
> >>
> >>The get/set calls operate on virtual bits, not concrete ones, so if we were
> >>to reset virtual bits 2-11:
> >>11|11
> >>
> >>We'd set the real bits to '000', because we clear or set the entire virtual
> >>group.
> >>
> >>This is probably not what we really want, so as a shortcut I just read and
> >>then re-set the final bit.
> >>
> >>It is programmatically avoidable (Are we truncating into a granularity
> >>group?) but in the case that we are, I'd need to read/reset the bit anyway,
> >>so it seemed fine to just unconditionally apply the fix.
> >
> >I see. This is equivalent to:
> >
> >uint64_t start = QEMU_ALIGN_UP(num_elements, hb->granularity);
>
> Probably you mean QEMU_ALIGN_UP(num_elements, 1 << hb->granularity)
Yes, you are right.
Stefan
pgptlQ6l2wKXg.pgp
Description: PGP signature
Re: [Qemu-block] [PATCH v4 15/20] block: Resize bitmaps on bdrv_truncate
On 04/07/2015 08:57 AM, Stefan Hajnoczi wrote:
On Thu, Apr 02, 2015 at 11:57:59AM -0400, John Snow wrote:
On 04/02/2015 09:37 AM, Stefan Hajnoczi wrote:
On Fri, Mar 20, 2015 at 03:16:58PM -0400, John Snow wrote:
+void hbitmap_truncate(HBitmap *hb, uint64_t size)
+{
+bool shrink;
+unsigned i;
+uint64_t num_elements = size;
+uint64_t old;
+
+/* Size comes in as logical elements, adjust for granularity. */
+size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
+assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
+shrink = size < hb->size;
+
+/* bit sizes are identical; nothing to do. */
+if (size == hb->size) {
+return;
+}
+
+/* If we're losing bits, let's clear those bits before we invalidate all of
+ * our invariants. This helps keep the bitcount consistent, and will
prevent
+ * us from carrying around garbage bits beyond the end of the map.
+ *
+ * Because clearing bits past the end of map might reset bits we care about
+ * within the array, record the current value of the last bit we're
keeping.
+ */
+if (shrink) {
+bool set = hbitmap_get(hb, num_elements - 1);
+uint64_t fix_count = (hb->size << hb->granularity) - num_elements;
+
+assert(fix_count);
+hbitmap_reset(hb, num_elements, fix_count);
+if (set) {
+hbitmap_set(hb, num_elements - 1, 1);
+}
Why is it necessary to set the last bit (if it was set)? The comment
isn't clear to me.
Sure. The granularity of the bitmap provides us with virtual bit groups. for
a granularity of say g=2, we have 2^2 virtual bits per every real bit:
101 in memory is treated, virtually, as .
The get/set calls operate on virtual bits, not concrete ones, so if we were
to reset virtual bits 2-11:
11|11
We'd set the real bits to '000', because we clear or set the entire virtual
group.
This is probably not what we really want, so as a shortcut I just read and
then re-set the final bit.
It is programmatically avoidable (Are we truncating into a granularity
group?) but in the case that we are, I'd need to read/reset the bit anyway,
so it seemed fine to just unconditionally apply the fix.
I see. This is equivalent to:
uint64_t start = QEMU_ALIGN_UP(num_elements, hb->granularity);
Probably you mean QEMU_ALIGN_UP(num_elements, 1 << hb->granularity)
uint64_t fix_count = (hb->size << hb->granularity) - start;
hbitmap_reset(hb, start, fix_count);
The explicit QEMU_ALIGN_UP(num_elements, hb->granularity) calculation
shows that we're working around the granularity. I find this easier to
understand.
If you keep the get/set version, please extend the comment to explain
that clearing the first bit could destroy up to granularity - 1 bits
that must be preserved.
Your solution will read more nicely, so I'll just adopt that, thanks.
Stefan
Re: [Qemu-block] [PATCH v4 15/20] block: Resize bitmaps on bdrv_truncate
On Thu, Apr 02, 2015 at 11:57:59AM -0400, John Snow wrote:
>
>
> On 04/02/2015 09:37 AM, Stefan Hajnoczi wrote:
> >On Fri, Mar 20, 2015 at 03:16:58PM -0400, John Snow wrote:
> >>+void hbitmap_truncate(HBitmap *hb, uint64_t size)
> >>+{
> >>+bool shrink;
> >>+unsigned i;
> >>+uint64_t num_elements = size;
> >>+uint64_t old;
> >>+
> >>+/* Size comes in as logical elements, adjust for granularity. */
> >>+size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
> >>+assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
> >>+shrink = size < hb->size;
> >>+
> >>+/* bit sizes are identical; nothing to do. */
> >>+if (size == hb->size) {
> >>+return;
> >>+}
> >>+
> >>+/* If we're losing bits, let's clear those bits before we invalidate
> >>all of
> >>+ * our invariants. This helps keep the bitcount consistent, and will
> >>prevent
> >>+ * us from carrying around garbage bits beyond the end of the map.
> >>+ *
> >>+ * Because clearing bits past the end of map might reset bits we care
> >>about
> >>+ * within the array, record the current value of the last bit we're
> >>keeping.
> >>+ */
> >>+if (shrink) {
> >>+bool set = hbitmap_get(hb, num_elements - 1);
> >>+uint64_t fix_count = (hb->size << hb->granularity) - num_elements;
> >>+
> >>+assert(fix_count);
> >>+hbitmap_reset(hb, num_elements, fix_count);
> >>+if (set) {
> >>+hbitmap_set(hb, num_elements - 1, 1);
> >>+}
> >
> >Why is it necessary to set the last bit (if it was set)? The comment
> >isn't clear to me.
> >
>
> Sure. The granularity of the bitmap provides us with virtual bit groups. for
> a granularity of say g=2, we have 2^2 virtual bits per every real bit:
>
> 101 in memory is treated, virtually, as .
>
> The get/set calls operate on virtual bits, not concrete ones, so if we were
> to reset virtual bits 2-11:
> 11|11
>
> We'd set the real bits to '000', because we clear or set the entire virtual
> group.
>
> This is probably not what we really want, so as a shortcut I just read and
> then re-set the final bit.
>
> It is programmatically avoidable (Are we truncating into a granularity
> group?) but in the case that we are, I'd need to read/reset the bit anyway,
> so it seemed fine to just unconditionally apply the fix.
I see. This is equivalent to:
uint64_t start = QEMU_ALIGN_UP(num_elements, hb->granularity);
uint64_t fix_count = (hb->size << hb->granularity) - start;
hbitmap_reset(hb, start, fix_count);
The explicit QEMU_ALIGN_UP(num_elements, hb->granularity) calculation
shows that we're working around the granularity. I find this easier to
understand.
If you keep the get/set version, please extend the comment to explain
that clearing the first bit could destroy up to granularity - 1 bits
that must be preserved.
Stefan
pgp0NDiaAHG10.pgp
Description: PGP signature
Re: [Qemu-block] [PATCH v4 15/20] block: Resize bitmaps on bdrv_truncate
On 04/02/2015 09:37 AM, Stefan Hajnoczi wrote:
On Fri, Mar 20, 2015 at 03:16:58PM -0400, John Snow wrote:
+void hbitmap_truncate(HBitmap *hb, uint64_t size)
+{
+bool shrink;
+unsigned i;
+uint64_t num_elements = size;
+uint64_t old;
+
+/* Size comes in as logical elements, adjust for granularity. */
+size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
+assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
+shrink = size < hb->size;
+
+/* bit sizes are identical; nothing to do. */
+if (size == hb->size) {
+return;
+}
+
+/* If we're losing bits, let's clear those bits before we invalidate all of
+ * our invariants. This helps keep the bitcount consistent, and will
prevent
+ * us from carrying around garbage bits beyond the end of the map.
+ *
+ * Because clearing bits past the end of map might reset bits we care about
+ * within the array, record the current value of the last bit we're
keeping.
+ */
+if (shrink) {
+bool set = hbitmap_get(hb, num_elements - 1);
+uint64_t fix_count = (hb->size << hb->granularity) - num_elements;
+
+assert(fix_count);
+hbitmap_reset(hb, num_elements, fix_count);
+if (set) {
+hbitmap_set(hb, num_elements - 1, 1);
+}
Why is it necessary to set the last bit (if it was set)? The comment
isn't clear to me.
Sure. The granularity of the bitmap provides us with virtual bit groups.
for a granularity of say g=2, we have 2^2 virtual bits per every real bit:
101 in memory is treated, virtually, as .
The get/set calls operate on virtual bits, not concrete ones, so if we
were to reset virtual bits 2-11:
11|11
We'd set the real bits to '000', because we clear or set the entire
virtual group.
This is probably not what we really want, so as a shortcut I just read
and then re-set the final bit.
It is programmatically avoidable (Are we truncating into a granularity
group?) but in the case that we are, I'd need to read/reset the bit
anyway, so it seemed fine to just unconditionally apply the fix.
Re: [Qemu-block] [PATCH v4 15/20] block: Resize bitmaps on bdrv_truncate
On Fri, Mar 20, 2015 at 03:16:58PM -0400, John Snow wrote:
> +void hbitmap_truncate(HBitmap *hb, uint64_t size)
> +{
> +bool shrink;
> +unsigned i;
> +uint64_t num_elements = size;
> +uint64_t old;
> +
> +/* Size comes in as logical elements, adjust for granularity. */
> +size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
> +assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
> +shrink = size < hb->size;
> +
> +/* bit sizes are identical; nothing to do. */
> +if (size == hb->size) {
> +return;
> +}
> +
> +/* If we're losing bits, let's clear those bits before we invalidate all
> of
> + * our invariants. This helps keep the bitcount consistent, and will
> prevent
> + * us from carrying around garbage bits beyond the end of the map.
> + *
> + * Because clearing bits past the end of map might reset bits we care
> about
> + * within the array, record the current value of the last bit we're
> keeping.
> + */
> +if (shrink) {
> +bool set = hbitmap_get(hb, num_elements - 1);
> +uint64_t fix_count = (hb->size << hb->granularity) - num_elements;
> +
> +assert(fix_count);
> +hbitmap_reset(hb, num_elements, fix_count);
> +if (set) {
> +hbitmap_set(hb, num_elements - 1, 1);
> +}
Why is it necessary to set the last bit (if it was set)? The comment
isn't clear to me.
pgpHrb2qK9blZ.pgp
Description: PGP signature
[Qemu-block] [PATCH v4 15/20] block: Resize bitmaps on bdrv_truncate
Signed-off-by: John Snow
Reviewed-by: Max Reitz
---
block.c| 18 +
include/qemu/hbitmap.h | 10 ++
util/hbitmap.c | 52 ++
3 files changed, 80 insertions(+)
diff --git a/block.c b/block.c
index 81d176a..9a8f2da 100644
--- a/block.c
+++ b/block.c
@@ -113,6 +113,7 @@ static void bdrv_set_dirty(BlockDriverState *bs, int64_t
cur_sector,
int nr_sectors);
static void bdrv_reset_dirty(BlockDriverState *bs, int64_t cur_sector,
int nr_sectors);
+static void bdrv_dirty_bitmap_truncate(BlockDriverState *bs);
/* If non-zero, use only whitelisted block drivers */
static int use_bdrv_whitelist;
@@ -3550,6 +3551,7 @@ int bdrv_truncate(BlockDriverState *bs, int64_t offset)
ret = drv->bdrv_truncate(bs, offset);
if (ret == 0) {
ret = refresh_total_sectors(bs, offset >> BDRV_SECTOR_BITS);
+bdrv_dirty_bitmap_truncate(bs);
if (bs->blk) {
blk_dev_resize_cb(bs->blk);
}
@@ -5560,6 +5562,22 @@ BdrvDirtyBitmap
*bdrv_reclaim_dirty_bitmap(BlockDriverState *bs,
return parent;
}
+/**
+ * Truncates _all_ bitmaps attached to a BDS.
+ */
+static void bdrv_dirty_bitmap_truncate(BlockDriverState *bs)
+{
+BdrvDirtyBitmap *bitmap;
+uint64_t size = bdrv_nb_sectors(bs);
+
+QLIST_FOREACH(bitmap, &bs->dirty_bitmaps, list) {
+if (bdrv_dirty_bitmap_frozen(bitmap)) {
+continue;
+}
+hbitmap_truncate(bitmap->bitmap, size);
+}
+}
+
void bdrv_release_dirty_bitmap(BlockDriverState *bs, BdrvDirtyBitmap *bitmap)
{
BdrvDirtyBitmap *bm, *next;
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index c19c1cb..a75157e 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -65,6 +65,16 @@ struct HBitmapIter {
HBitmap *hbitmap_alloc(uint64_t size, int granularity);
/**
+ * hbitmap_truncate:
+ * @hb: The bitmap to change the size of.
+ * @size: The number of elements to change the bitmap to accommodate.
+ *
+ * truncate or grow an existing bitmap to accommodate a new number of elements.
+ * This may invalidate existing HBitmapIterators.
+ */
+void hbitmap_truncate(HBitmap *hb, uint64_t size);
+
+/**
* hbitmap_merge:
* @a: The bitmap to store the result in.
* @b: The bitmap to merge into @a.
diff --git a/util/hbitmap.c b/util/hbitmap.c
index ba11fd3..4505ef7 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -400,6 +400,58 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
return hb;
}
+void hbitmap_truncate(HBitmap *hb, uint64_t size)
+{
+bool shrink;
+unsigned i;
+uint64_t num_elements = size;
+uint64_t old;
+
+/* Size comes in as logical elements, adjust for granularity. */
+size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
+assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
+shrink = size < hb->size;
+
+/* bit sizes are identical; nothing to do. */
+if (size == hb->size) {
+return;
+}
+
+/* If we're losing bits, let's clear those bits before we invalidate all of
+ * our invariants. This helps keep the bitcount consistent, and will
prevent
+ * us from carrying around garbage bits beyond the end of the map.
+ *
+ * Because clearing bits past the end of map might reset bits we care about
+ * within the array, record the current value of the last bit we're
keeping.
+ */
+if (shrink) {
+bool set = hbitmap_get(hb, num_elements - 1);
+uint64_t fix_count = (hb->size << hb->granularity) - num_elements;
+
+assert(fix_count);
+hbitmap_reset(hb, num_elements, fix_count);
+if (set) {
+hbitmap_set(hb, num_elements - 1, 1);
+}
+}
+
+hb->size = size;
+for (i = HBITMAP_LEVELS; i-- > 0; ) {
+size = MAX(BITS_TO_LONGS(size), 1);
+if (hb->sizes[i] == size) {
+break;
+}
+old = hb->sizes[i];
+hb->sizes[i] = size;
+hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
+if (!shrink) {
+memset(&hb->levels[i][old], 0x00,
+ (size - old) * sizeof(*hb->levels[i]));
+}
+}
+}
+
+
/**
* Given HBitmaps A and B, let A := A (BITOR) B.
* Bitmap B will not be modified.
--
2.1.0
