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 1111 0000 1111.
The get/set calls operate on virtual bits, not concrete ones, so if we were
to reset virtual bits 2-11:
11|11 0000 1111
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.