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?
+ 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.
+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.
+ if (ret != 0) + goto error; + else if (isset) {
Style. Since the else branch used {}, the if branch must also use {}.
+ 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.
+ +#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.
+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? 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. -- Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org