On 08/30/2012 02:55 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 subsquent patches.
s/subsquent/subsequent/ The overall series sounds nice. There was no cover letter (0/8) to the series, so it's a bit harder to track the overall diffstat, although it looks like you have a net reduction of lines based on previewing individual patches later in the series - always a nice result. And having nice interfaces here means that later patches should still apply even if I make you change the internals of this patch. Overall, I think we can get this series into shape for 0.10.2.
--- .gitignore | 1 + src/libvirt_private.syms | 10 ++ src/util/bitmap.c | 391 +++++++++++++++++++++++++++++++++++++++++++++- src/util/bitmap.h | 23 +++ tests/Makefile.am | 8 +- tests/virbitmaptest.c | 134 ++++++++++++++++ 6 files changed, 562 insertions(+), 5 deletions(-) create mode 100644 tests/virbitmaptest.c
diff --git a/.gitignore b/.gitignore index 5041ddf..9aaa1f5 100644 --- a/.gitignore +++ b/.gitignore @@ -155,6 +155,7 @@ /tests/storagebackendsheepdogtest /tests/utiltest /tests/viratomictest +/tests/virbitmaptest /tests/virauthconfigtest
Needs to be sorted, otherwise the next person running ./autogen.sh on a fresh checkout will have a spurious difference.
+++ b/src/util/bitmap.c @@ -33,15 +33,17 @@ #include "bitmap.h" #include "memory.h" #include "buf.h" +#include "util.h" +#include "c-ctype.h"
struct _virBitmap { size_t size; - unsigned long *map; + unsigned char *map;
NACK to this hunk; iterating over longs is more efficient than iterating over char. It means the conversion from a char* data will have to be a bit more involved, but that's life.
};
-#define VIR_BITMAP_BITS_PER_UNIT ((int) sizeof(unsigned long) * CHAR_BIT) +#define VIR_BITMAP_BITS_PER_UNIT ((int) sizeof(unsigned char) * CHAR_BIT)
sizeof(unsigned char) == 1, by definition; I always question use of code like this (and if you follow my earlier comment of keeping things with long* rather than char*, then my objection on this hunk becomes irrelevant).
+/* Helper function. caller must ensure b < bitmap->size */ +static bool bitmapIsset(virBitmapPtr bitmap, size_t b)
s/bitmapIsset/virBitmapIsSet/ - we want to use consistent naming, even for static functions.
@@ -168,7 +176,7 @@ char *virBitmapString(virBitmapPtr bitmap) VIR_BITMAP_BITS_PER_UNIT;
while (sz--) { - virBufferAsprintf(&buf, "%0*lx", + virBufferAsprintf(&buf, "%0*hx",
char* would be hhx, not hx (but again, I want to keep this at lx).
+/** + * virBitmapFormat: + * @bitmap: the bitmap + * + * This function is the counterpart of virBitmapParse. This function creates + * a human-readable string representing the bits in bitmap. + * + * See virBitmapParse for the format of @str. + * + * Returns the string on success or NULL otherwise. Caller should call + * VIR_FREE to free the string. + */ +char *virBitmapFormat(virBitmapPtr bitmap) +{ + virBuffer buf =VIR_BUFFER_INITIALIZER;
space after =
+/** + * virBitmapParse: + * @str: points to a string representing a human-readable bitmap + * @bitmap: a bitmap created from @str + * @bitmapSize: the upper limit of num of bits in created bitmap + * + * This function is the counterpart of virBitmapFormat. This function creates + * a bitmap, in which bits are set according to the content of @str. + * + * @str is a comma separated string of fields N, which means a number of bit + * to set, and ^N, which means to unset the bit, and N-M for ranges of bits + * to set. + * + * Returns the number of bits set in @bitmap, or -1 in case of error. + */ + +int virBitmapParse(const char *str, + char sep, + virBitmapPtr *bitmap, + size_t bitmapSize) +{ + int ret = 0; + int neg = 0;
s/int/bool/; s/0/false/ for all uses of neg in this function
+/** + * virBitmapAllocFromData: + * @data: the data + * @len: len of @data in byte
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; + + bitmap = virBitmapAlloc(len * CHAR_BIT); + if (!bitmap) + return NULL; + + memcpy(bitmap->map, data, len);
Here's where you need to do some work to keep virBitmap using longs.
+/** + * virBitmapToData: + * @data: the data + * @len: len of @data in byte + * + * Convert a bitmap to a chunk of data containing bits information. + * Data consists of sequential bytes, with lower bytes containing + * lower bits. + * + * Returns 0 on success, -1 otherwise. + */ +int virBitmapToData(virBitmapPtr bitmap, char **data, int *dataLen) +{ + size_t sz; + + sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) / + VIR_BITMAP_BITS_PER_UNIT;
Hmm; we seem to be recomputing this in a lot of code; maybe it's better to compute it once at virBitmap creation and make the struct one member larger.
+ + if (VIR_ALLOC_N(*data, sz) < 0) + return -1; + + memcpy(*data, bitmap->map, sz);
And another conversion needed, this time from long to char.
+/** + * virBitmapCmp: + * @b1: bitmap 1 + * @b2: bitmap 2 + * + * Compares two bitmaps. Returns true if two bitmaps have exactly + * the same set of bits set, otherwise false.
Mention specifically that this works even for maps of different lengths, if the longer map has a 0 tail.
+ */ +bool virBitmapCmp(virBitmapPtr b1, virBitmapPtr b2) +{ + virBitmapPtr b; + size_t sz1, sz2, sz; + int i; + + sz1 = (b1->size + VIR_BITMAP_BITS_PER_UNIT - 1) / + VIR_BITMAP_BITS_PER_UNIT; + sz2 = (b2->size + VIR_BITMAP_BITS_PER_UNIT - 1) / + VIR_BITMAP_BITS_PER_UNIT; + + sz = sz1 < sz2 ? sz1 : sz2; + + for (i = 0; i < sz; i++) { + if (b1->map[i] != b2->map[i]) + return false; + } + + b = sz1 > sz ? b1 : b2; + sz = sz1 > sz ? sz1 : sz2;
Rather than computing 'sz1 > sz ?:' three times, why not: if (b1->size > b2->size) { virBitmapPtr tmp = b1; b1 = b2; b2 = b1; } up front, prior to computing sz1 and sz2, at which point you know that sz1 <= sz2 for the rest of the function.
+/** + * virBitmapSetAll: + * @bitmap: the bitmap + * + * set all bits in @bitmap. + */ +void virBitmapSetAll(virBitmapPtr bitmap) +{
Do we _also_ want virBitmapSetRange(virBitmapPtr bitmap, size_t start, size_t len), for setting a portion of the map?
+ for (i = 0; i < sz; i++) + bitmap->map[i] = -1;
Why not memset()?
+/** + * virBitmapClearAll: + * @bitmap: the bitmap + * + * clear all bits in @bitmap.
Similarly for virBitmapClearRange(virBitmapPtr bitmap, size_t start, size_t len).
+ */ +void virBitmapClearAll(virBitmapPtr bitmap) +{ + int i; + size_t sz; + + sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) / + VIR_BITMAP_BITS_PER_UNIT; + + for (i = 0; i < sz; i++) + bitmap->map[i] = 0;
Again, memset().
+ * virBitmapIsAllSet: + * @bitmap: the bitmap to check + * + * check if all bits in @bitmap are set. + */ +bool virBitmapIsAllSet(virBitmapPtr bitmap) +{ + int i; + int unusedBits; + size_t sz, tmp; + + sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) / + VIR_BITMAP_BITS_PER_UNIT; + unusedBits = sz * VIR_BITMAP_BITS_PER_UNIT - bitmap->size; + + tmp = sz; + if (unusedBits > 0) + tmp = sz - 1; + + for (i = 0; i < tmp; i++) + if (bitmap->map[i] != (unsigned char)-1)
Unnecessary cast (especially if you keep the code with long).
+ return false; + + if (unusedBits > 0) { + if ((bitmap->map[sz - 1] & ((1 << (VIR_BITMAP_BITS_PER_UNIT - unusedBits + 1)) - 1))
s/1 <</1U <</ - need to use unsigned math to guarantee defined results.
+++ b/src/util/bitmap.h @@ -62,4 +62,27 @@ int virBitmapGetBit(virBitmapPtr bitmap, size_t b, bool *result) char *virBitmapString(virBitmapPtr bitmap) ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK;
+char *virBitmapFormat(virBitmapPtr bitmap);
Quite a few of these need ATTRIBUTE_NONNULL() markings.
+++ b/tests/Makefile.am @@ -92,7 +92,8 @@ test_programs = virshtest sockettest \ viratomictest \ utiltest virnettlscontexttest shunloadtest \ virtimetest viruritest virkeyfiletest \ - virauthconfigtest + virauthconfigtest \ + virbitmaptest
Spacing is off; Makefiles use TAB.
@@ -592,6 +597,7 @@ shunloadtest_SOURCES = \ shunloadtest_LDADD = $(LIB_PTHREAD) shunloadtest_DEPENDENCIES = libshunload.la
+ if WITH_CIL
Spurious whitespace change.
+++ b/tests/virbitmaptest.c
+bool testBit(virBitmapPtr bitmap, unsigned int start, unsigned int end)
Too weak - you are using this to check that all bits in a range have a given value, but for that to work, you need to know what the desired value is as a fourth parameter.
+ if (!testBit(bitmap, 1021, 1023)) + goto error; + + if (testBit(bitmap, 0, 0)) + goto error; + if (testBit(bitmap, 33,49)) + goto error;
That is, in these uses, you really want: if (testBits(bitmap, 1021, 1023, true) < 0 || testBits(bitmap, 33, 49, false) < 0) goto error; -- Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org