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 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.
> >
> >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