12:17 a.m.
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(a)redhat.com +1-919-301-3266
Libvirt virtualization library http://libvirt.org