[libvirt] [PATCH v2 2/9] New functions for virBitmap

[Hu Tao]

On Thu, Sep 06, 2012 at 11:17:58PM -0600, Eric Blake wrote:
> On 09/06/2012 04:13 AM, Hu Tao wrote:
> > In many places we store bitmap info in a chunk of data
> > (pointed to by a char *), and have redundant codes to
> > set/unset bits. This patch extends virBitmap, and convert
> > those codes to use virBitmap in subsequent patches.
> > ---
> 
> >  
> >  struct _virBitmap {
> > -    size_t size;
> > -    unsigned long *map;
> > +    size_t size;        /* size in bits */
> > +    size_t size2;       /* size in LONGs */
> 
> The name 'size2' isn't very descriptive.  Maybe we should rename to
> s/size/max_bit/ and s/size2/map_len/ for easier reading?

Thanks for suggestion.

> 
> > +    unsigned long *map; /* bits are stored in little-endian format */
> 
> This comment...
> 
> > +/* Helper function. caller must ensure b < bitmap->size */
> > +static bool virBitmapIsSet(virBitmapPtr bitmap, size_t b)
> > +{
> > +    return !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b));
> 
> ...and this code disagree.  This code is reading in machine-native
> format, not little-endian.  And I much prefer operating in
> machine-native format.  Which means when converting from char* to long,
> you'll have to properly pass things through endian conversion, rather
> than requiring the longs to be little-endian.

OK.

> 
> > +char *virBitmapFormat(virBitmapPtr bitmap)
> > +{
> > +    virBuffer buf = VIR_BUFFER_INITIALIZER;
> > +    int first = -1;
> > +    int start, cur;
> > +    int ret;
> > +    bool isset;
> > +
> > +    if (!bitmap)
> > +        return NULL;
> > +
> > +    cur = 0;
> > +    start = -1;
> > +    while (cur < bitmap->size) {
> > +        ret = virBitmapGetBit(bitmap, cur, &isset);
> 
> I'm wondering if we should optimize this by using things like ffsl() and
> iterating a long at a time for longs that are 0 or -1, rather than
> blindly processing one bit at a time.  Or even make this use the new
> virBitmapNextSetBit, and have that function be optimized a bit more.

Will improve it.

> 
> > +        if (ret != 0)
> > +            goto error;
> > +        else if (isset) {
> 
> Style.  Since the else branch used {}, the if branch must also use {}.

OK.

> 
> > +            if (start == -1)
> > +                start = cur;
> > +        } else if (start != -1) {
> > +            if (!first)
> > +                virBufferAddLit(&buf, ",");
> > +            else
> > +                first = 0;
> > +            if (cur == start + 1)
> > +                virBufferAsprintf(&buf, "%d", start);
> > +            else
> > +                virBufferAsprintf(&buf, "%d-%d", start, cur - 1);
> > +            start = -1;
> > +        }
> > +        cur++;
> > +    }
> > +
> > +    if (start != -1) {
> > +        if (!first)
> > +            virBufferAddLit(&buf, ",");
> > +        if (cur == start + 1)
> > +            virBufferAsprintf(&buf, "%d", start);
> > +        else
> > +            virBufferAsprintf(&buf, "%d-%d", start, cur - 1);
> > +    }
> > +
> > +    if (virBufferError(&buf)) {
> > +error:
> > +        virBufferFreeAndReset(&buf);
> > +        return NULL;
> > +    }
> > +
> > +    return virBufferContentAndReset(&buf);
> 
> Ouch.  If the bitset is completely unset, then this returns NULL for
> both errors and success.  You need to special-case a map that is
> completely unset to return strdup("") instead.

OK.

> 
> > +
> > +#ifdef __BIG_ENDIAN__
> > +static unsigned long
> > +virSwapEndian(unsigned long l)
> 
> Yuck.  __BIG_ENDIAN__ vs. __LITTLE_ENDIAN__ is not guaranteed to exist.
>  And even if you can rely on it, there's bound to be better ways to
> implement this instead of open-coding it ourselves (not to mention that
> by avoiding the #ifdefs, we avoid introducing bugs in the big-endian
> code that cannot be detected on little-endian machines).  (Hmm, too bad
> gnulib doesn't guarantee be32toh and be64toh).
> 
> > +/**
> > + * virBitmapAllocFromData:
> > + * @data: the data
> > + * @len: length of @data in bytes
> > + *
> > + * Allocate a bitmap from a chunk of data containing bits
> > + * information
> > + *
> > + * Returns a pointer to the allocated bitmap or NULL if
> > + * memory cannot be allocated.
> > + */
> > +virBitmapPtr virBitmapAllocFromData(void *data, int len)
> > +{
> > +    virBitmapPtr bitmap;
> > +#ifdef __BIG_ENDIAN__
> > +    int i;
> > +#endif
> > +
> > +    bitmap = virBitmapAlloc(len * CHAR_BIT);
> > +    if (!bitmap)
> > +        return NULL;
> > +
> > +    memcpy(bitmap->map, data, len);
> 
> Instead of trying to memcpy() and then conditionally virSwapEndian(), I
> would just do it the manual way of reading one byte at a time for both
> endian types.  Fewer #ifdefs, less ugly code.

OK.

> 
> > +int virBitmapToData(virBitmapPtr bitmap, char **data, int *dataLen)
> > +{
> > +    int len;
> > +#ifdef __BIG_ENDIAN__
> > +    unsigned long *l;
> > +#endif
> > +
> > +    len = bitmap->size2 * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT);
> > +
> > +    if (VIR_ALLOC_N(*data, len) < 0)
> > +        return -1;
> > +
> > +    memcpy(*data, bitmap->map, len);
> > +    *dataLen = len;
> > +
> > +#ifdef __BIG_ENDIAN__
> > +    l = (unsigned long *)*data;
> > +    for (i = 0; i < bitmap->size2; i++, l++)
> > +        *l = virSwapEndian(*l);
> > +#endif
> 
> Again, I'm not a fan of these #ifdefs.
> 
> > +int virBitmapNextSetBit(virBitmapPtr bitmap, int pos)
> > +{
> > +    int nl;
> > +    int nb;
> > +    unsigned long bits;
> > +
> > +    if (pos < 0)
> > +        pos = -1;
> > +
> > +    pos++;
> > +
> > +    if (pos >= bitmap->size)
> > +        return -1;
> > +
> > +    nl = pos / VIR_BITMAP_BITS_PER_UNIT;
> > +    nb = pos % VIR_BITMAP_BITS_PER_UNIT;
> > +
> > +    bits = bitmap->map[nl] & ~((1UL << nb) - 1);
> > +
> > +    while (bits == 0 && ++nl < bitmap->size2) {
> > +        bits = bitmap->map[nl];
> > +    }
> 
> Use ffsl() instead of iterating one bit at a time.
> 
> > +
> > +    if (bits == 0)
> > +        return -1;
> > +
> > +    return __builtin_ctzl(bits) + nl * VIR_BITMAP_BITS_PER_UNIT;
> 
> __builtin_ctzl() is not guaranteed to exist.  ffsl() should already give
> you what you need.
> 
> 
> > +++ b/tests/virbitmaptest.c
> > @@ -0,0 +1,233 @@
> 
> > +#include <config.h>
> > +
> > +#include <time.h>
> > +#include <sched.h>
> 
> What are you using <time.h> and <sched.h> for?

Oops. This is a copy&paste.

> 
> It's late for me, so I didn't closely read the entire patch, so much as
> identified things that jumped out on first glance.

Have a good night:)

-- 
Thanks,
Hu Tao