On 06/15/2012 09:05 AM, Paolo Bonzini wrote:
> HBitmaps provides an array of bits.  The bits are stored as usual in an
> array of unsigned longs, but HBitmap is also optimized to provide fast
> iteration over set bits; going from one bit to the next is O(log log n)
> worst case, which is low enough that the number of levels is in fact fixed.
> 

> 
> Setting or clearing a range of m bits on all levels, the work to perform
> is O(m + m/W + m/W^2 + ...), which in O(m) like on a regular bitmap.

s/in/is/ (in commit message and code comment)

I made the mistake of starting on the .c before the .h, and my first
comments were:

> +struct HBitmap {
> +    uint64_t size;

Number of total bits in the bottom level?

> +    uint64_t count;

Number of set bits in the bottom level?

> +    int granularity;

A scaling factor, so that you can iterate over addresses of a sector
(512 bytes at a time) instead of having to scale the bit result?  [Hint
- these names are not self-obvious, so a short comment might help the
reader]

> +    unsigned long *levels[HBITMAP_LEVELS];

and at this point, I decided reading the .h first makes more sense.
Also, this is a high-level first-impressions review, not a line-by-line
algorithmic accuracy review.  Did you invent this yourself, or copy from
the ideas from a published work?

> +};
> +
> +static int64_t hbi_next_internal(HBitmapIter *hbi)
> +{

> +
> +        /* Check for end of iteration.  We only use up to
> +         * BITS_PER_LEVEL bits (actually less) in the level 0 bitmap,
> +         * and a sentinel is placed in hbitmap_alloc that ends the
> +         * above loop.

Level 0 being the coursest (top, each bit represents that at least one
page of level 1 has a set bit), and level n being the finest (each bit
representing the actual bitmap?

> +         */
> +
> +        if (i == 0 && (cur & (BITS_PER_LONG - 1)) == 0) {
> +            return -1;
> +        }
> +        for (; i < HBITMAP_LEVELS - 1; i++) {
> +            /* Find least significant set bit in the word, use them
> +             * to add back shifted out bits to pos.
> +             */
> +            pos = (pos << BITS_PER_LEVEL) + ffsl(cur) - 1;

ffsl() is a glibc extension.  Do we have a fallback for other platforms?
 (Only ffs() is POSIX).

> +
> +/* The recursive workhorse... */
> +static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t end)

And the recursion is bounded by HBITMAP_LEVELS, which is relatively
small, right?


> +
> +HBitmap *hbitmap_alloc(uint64_t size, int granularity)
> +{
> +    HBitmap *hb = g_malloc0(sizeof (struct HBitmap));
> +    int i;
> +
> +    size = (size + (1 << granularity) - 1) >> granularity;

Doesn't this mean that granularity > 31 or < 0 gives undefined behavior?
 Should you be validating it for being in range?


> +
> +/* For 32-bit, the largest that fits in a 4 GiB address space.
> + * For 64-bit, the number of sectors in 1 PiB.  Good luck, in
> + * either case... :)
> + */
> +#define HBITMAP_LOG_MAX_SIZE   (BITS_PER_LONG == 32 ? 34 : 41)

Indeed :)

-- 
Eric Blake   eblake@redhat.com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org