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. --- .gitignore | 1 + src/libvirt_private.syms | 11 ++ src/util/bitmap.c | 405 +++++++++++++++++++++++++++++++++++++++++++++- src/util/bitmap.h | 34 ++++ tests/Makefile.am | 7 +- tests/virbitmaptest.c | 362 +++++++++++++++++++++++++++++++++++++++++ 6 files changed, 818 insertions(+), 2 deletions(-) create mode 100644 tests/virbitmaptest.c diff --git a/.gitignore b/.gitignore index d998f0e..1ca537e 100644 --- a/.gitignore +++ b/.gitignore @@ -157,6 +157,7 @@ /tests/utiltest /tests/viratomictest /tests/virauthconfigtest +/tests/virbitmaptest /tests/virbuftest /tests/virdrivermoduletest /tests/virhashtest diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms index 557fa0e..da0e647 100644 --- a/src/libvirt_private.syms +++ b/src/libvirt_private.syms @@ -6,13 +6,24 @@ # # bitmap.h +virBitmapClearAll; virBitmapClearBit; virBitmapCopy; +virBitmapEqual; +virBitmapFormat; virBitmapFree; virBitmapGetBit; +virBitmapIsAllSet; virBitmapNew; +virBitmapNewCopy; +virBitmapNewData; +virBitmapNextSetBit; +virBitmapParse; +virBitmapSetAll; virBitmapSetBit; +virBitmapSize; virBitmapString; +virBitmapToData; # buf.h diff --git a/src/util/bitmap.c b/src/util/bitmap.c index dc9c28a..51e567a 100644 --- a/src/util/bitmap.c +++ b/src/util/bitmap.c @@ -33,6 +33,8 @@ #include "bitmap.h" #include "memory.h" #include "buf.h" +#include "util.h" +#include "c-ctype.h" struct _virBitmap { @@ -145,6 +147,12 @@ int virBitmapClearBit(virBitmapPtr bitmap, size_t b) return 0; } +/* Helper function. caller must ensure b < bitmap->max_bit */ +static bool virBitmapIsSet(virBitmapPtr bitmap, size_t b) +{ + return !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b)); +} + /** * virBitmapGetBit: * @bitmap: Pointer to bitmap @@ -161,7 +169,7 @@ int virBitmapGetBit(virBitmapPtr bitmap, size_t b, bool *result) if (bitmap->max_bit <= b) return -1; - *result = !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b)); + *result = virBitmapIsSet(bitmap, b); return 0; } @@ -195,3 +203,398 @@ char *virBitmapString(virBitmapPtr bitmap) return virBufferContentAndReset(&buf); } + +/** + * 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; + bool first = true; + int start, cur, prev; + + if (!bitmap) + return NULL; + + cur = virBitmapNextSetBit(bitmap, -1); + if (cur < 0) + return strdup(""); + + start = prev = cur; + while (prev >= 0) { + cur = virBitmapNextSetBit(bitmap, prev); + + if (cur == prev + 1) { + prev = cur; + continue; + } + + /* cur < 0 or cur > prev + 1 */ + + if (!first) + virBufferAddLit(&buf, ","); + else + first = false; + + if (prev == start) + virBufferAsprintf(&buf, "%d", start); + else + virBufferAsprintf(&buf, "%d-%d", start, prev); + + start = prev = cur; + } + + if (virBufferError(&buf)) { + virBufferFreeAndReset(&buf); + return NULL; + } + + return virBufferContentAndReset(&buf); +} + +/** + * 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; + bool neg = false; + const char *cur; + char *tmp; + int i, start, last; + + if (!str) + return -1; + + cur = str; + virSkipSpaces(&cur); + + if (*cur == 0) + return -1; + + *bitmap = virBitmapNew(bitmapSize); + if (!*bitmap) + return -1; + + while (*cur != 0 && *cur != sep) { + /* + * 3 constructs are allowed: + * - N : a single CPU number + * - N-M : a range of CPU numbers with N < M + * - ^N : remove a single CPU number from the current set + */ + if (*cur == '^') { + cur++; + neg = true; + } + + if (!c_isdigit(*cur)) + goto parse_error; + + if (virStrToLong_i(cur, &tmp, 10, &start) < 0) + goto parse_error; + if (start < 0) + goto parse_error; + + cur = tmp; + + virSkipSpaces(&cur); + + if (*cur == ',' || *cur == 0 || *cur == sep) { + if (neg) { + if (virBitmapIsSet(*bitmap, start)) { + ignore_value(virBitmapClearBit(*bitmap, start)); + ret--; + } + } else { + if (!virBitmapIsSet(*bitmap, start)) { + ignore_value(virBitmapSetBit(*bitmap, start)); + ret++; + } + } + } else if (*cur == '-') { + if (neg) + goto parse_error; + + cur++; + virSkipSpaces(&cur); + + if (virStrToLong_i(cur, &tmp, 10, &last) < 0) + goto parse_error; + if (last < start) + goto parse_error; + + cur = tmp; + + for (i = start; i <= last; i++) { + if (!virBitmapIsSet(*bitmap, i)) { + ignore_value(virBitmapSetBit(*bitmap, i)); + ret++; + } + } + + virSkipSpaces(&cur); + } + + if (*cur == ',') { + cur++; + virSkipSpaces(&cur); + neg = false; + } else if(*cur == 0 || *cur == sep) { + break; + } else { + goto parse_error; + } + } + + return ret; + +parse_error: + virBitmapFree(*bitmap); + *bitmap = NULL; + return -1; +} + +/** + * virBitmapNewCopy: + * @src: the source bitmap. + * + * Makes a copy of bitmap @src. + * + * returns the copied bitmap on success, or NULL otherwise. Caller + * should call virBitmapFree to free the returned bitmap. + */ +virBitmapPtr virBitmapNewCopy(virBitmapPtr src) +{ + virBitmapPtr dst; + + if ((dst = virBitmapNew(src->max_bit)) == NULL) + return NULL; + + if (virBitmapCopy(dst, src) != 0) { + virBitmapFree(dst); + return NULL; + } + + return dst; +} + +/** + * virBitmapNewData: + * @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 virBitmapNewData(void *data, int len) +{ + virBitmapPtr bitmap; + int i; + + bitmap = virBitmapNew(len * CHAR_BIT); + if (!bitmap) + return NULL; + + memcpy(bitmap->map, data, len); + for (i = 0; i < bitmap->map_len; i++) + bitmap->map[i] = le64toh(bitmap->map[i]); + + return bitmap; +} + +/** + * 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, unsigned char **data, int *dataLen) +{ + int len; + unsigned long *l; + int i; + + len = bitmap->map_len * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT); + + if (VIR_ALLOC_N(*data, len) < 0) + return -1; + + memcpy(*data, bitmap->map, len); + *dataLen = len; + + l = (unsigned long *)*data; + for (i = 0; i < bitmap->map_len; i++, l++) + *l = htole64(*l); + + return 0; +} + +/** + * virBitmapEqual: + * @b1: bitmap 1 + * @b2: bitmap 2 + * + * Compares two bitmaps, whose lengths can be different from each other. + * + * Returns true if two bitmaps have exactly the same set of bits set, + * otherwise false. + */ +bool virBitmapEqual(virBitmapPtr b1, virBitmapPtr b2) +{ + virBitmapPtr tmp; + int i; + + if (b1->max_bit > b2->max_bit) { + tmp = b1; + b1 = b2; + b2 = tmp; + } + + /* Now b1 is the smaller one, if not equal */ + + for (i = 0; i < b1->map_len; i++) { + if (b1->map[i] != b2->map[i]) + return false; + } + + for (; i < b2->map_len; i++) { + if (b2->map[i]) + return false; + } + + return true; +} + +size_t virBitmapSize(virBitmapPtr bitmap) +{ + return bitmap->max_bit; +} + +/** + * virBitmapSetAll: + * @bitmap: the bitmap + * + * set all bits in @bitmap. + */ +void virBitmapSetAll(virBitmapPtr bitmap) +{ + memset(bitmap->map, 0xff, + bitmap->map_len * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT)); +} + +/** + * virBitmapClearAll: + * @bitmap: the bitmap + * + * clear all bits in @bitmap. + */ +void virBitmapClearAll(virBitmapPtr bitmap) +{ + memset(bitmap->map, 0, + bitmap->map_len * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT)); +} + +/** + * 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; + + unusedBits = bitmap->map_len * VIR_BITMAP_BITS_PER_UNIT - bitmap->max_bit; + + sz = bitmap->map_len; + if (unusedBits > 0) + sz--; + + for (i = 0; i < sz; i++) + if (bitmap->map[i] != -1) + return false; + + if (unusedBits > 0) { + if ((bitmap->map[sz] & ((1U << (VIR_BITMAP_BITS_PER_UNIT - unusedBits)) - 1)) + != ((1U << (VIR_BITMAP_BITS_PER_UNIT - unusedBits)) - 1)) + return false; + } + + return true; +} + +/** + * virBitmapNextSetBit: + * @bitmap: the bitmap + * @pos: the position after which to search for a set bit + * + * search the first set bit after position @pos in bitmap @bitmap. + * @pos can be -1 to search for the first set bit. Position starts + * at 0. + * + * returns the position of the found bit, or -1 if no bit found. + */ +int virBitmapNextSetBit(virBitmapPtr bitmap, int pos) +{ + int nl; + int nb; + unsigned long bits; + + if (pos < 0) + pos = -1; + + pos++; + + if (pos >= bitmap->max_bit) + 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->map_len) { + bits = bitmap->map[nl]; + } + + if (bits == 0) + return -1; + + return ffsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT; +} diff --git a/src/util/bitmap.h b/src/util/bitmap.h index 2609509..06c577f 100644 --- a/src/util/bitmap.h +++ b/src/util/bitmap.h @@ -68,4 +68,38 @@ int virBitmapGetBit(virBitmapPtr bitmap, size_t b, bool *result) char *virBitmapString(virBitmapPtr bitmap) ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK; +char *virBitmapFormat(virBitmapPtr bitmap) + ATTRIBUTE_NONNULL(1); + +int virBitmapParse(const char *str, + char sep, + virBitmapPtr *bitmap, + size_t bitmapSize) + ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3); + +virBitmapPtr virBitmapNewCopy(virBitmapPtr src) ATTRIBUTE_NONNULL(1); + +virBitmapPtr virBitmapNewData(void *data, int len) ATTRIBUTE_NONNULL(1); + +int virBitmapToData(virBitmapPtr bitmap, unsigned char **data, int *dataLen) + ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(2); + +bool virBitmapEqual(virBitmapPtr b1, virBitmapPtr b2) + ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(2); + +size_t virBitmapSize(virBitmapPtr bitmap) + ATTRIBUTE_NONNULL(1); + +void virBitmapSetAll(virBitmapPtr bitmap) + ATTRIBUTE_NONNULL(1); + +void virBitmapClearAll(virBitmapPtr bitmap) + ATTRIBUTE_NONNULL(1); + +bool virBitmapIsAllSet(virBitmapPtr bitmap) + ATTRIBUTE_NONNULL(1); + +int virBitmapNextSetBit(virBitmapPtr bitmap, int pos) + ATTRIBUTE_NONNULL(1); + #endif diff --git a/tests/Makefile.am b/tests/Makefile.am index c5cecaa..8dbad97 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -92,7 +92,8 @@ test_programs = virshtest sockettest \ viratomictest \ utiltest virnettlscontexttest shunloadtest \ virtimetest viruritest virkeyfiletest \ - virauthconfigtest + virauthconfigtest \ + virbitmaptest if WITH_SECDRIVER_SELINUX test_programs += securityselinuxtest @@ -589,6 +590,10 @@ viratomictest_SOURCES = \ viratomictest.c testutils.h testutils.c viratomictest_LDADD = $(LDADDS) +virbitmaptest_SOURCES = \ + virbitmaptest.c testutils.h testutils.c +virbitmaptest_LDADD = $(LDADDS) + jsontest_SOURCES = \ jsontest.c testutils.h testutils.c jsontest_LDADD = $(LDADDS) diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c new file mode 100644 index 0000000..0975996 --- /dev/null +++ b/tests/virbitmaptest.c @@ -0,0 +1,362 @@ +/* + * Copyright (C) 2012 Fujitsu. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; If not, see + * <http://www.gnu.org/licenses/>;. + * + */ + +#include <config.h> + +#include "testutils.h" + +#include "bitmap.h" + +static int test1(const void *data ATTRIBUTE_UNUSED) +{ + virBitmapPtr bitmap; + int size; + int bit; + bool result; + + size = 1024; + bit = 100; + bitmap = virBitmapNew(size); + if (virBitmapSetBit(bitmap, bit) < 0) + return -1; + + if (virBitmapGetBit(bitmap, bit, &result) < 0) + return -1; + + if (!result) + return -1; + + if (virBitmapGetBit(bitmap, bit + 1, &result) < 0) + return -1; + + if (result) + return -1; + + return 0; +} + +int testBit(virBitmapPtr bitmap, + unsigned int start, + unsigned int end, + bool expected) +{ + int i; + bool result; + + for (i = start; i <= end; i++) { + if (virBitmapGetBit(bitmap, i, &result) < 0) + return -1; + if (result == expected) + return 0; + } + + return -1; +} + +static int test2(const void *data ATTRIBUTE_UNUSED) +{ + const char *bitsString1 = "1-32,50,88-99,1021-1023"; + char *bitsString2 = NULL; + virBitmapPtr bitmap = NULL; + int ret = -1; + int size = 1025; + + if (virBitmapParse(bitsString1, 0, &bitmap, size) < 0) + goto error; + + if (testBit(bitmap, 1, 32, true) < 0) + goto error; + if (testBit(bitmap, 50, 50, true) < 0) + goto error; + if (testBit(bitmap, 88, 99, true) < 0) + goto error; + if (testBit(bitmap, 1021, 1023, true) < 0) + goto error; + + if (testBit(bitmap, 0, 0, false) < 0) + goto error; + if (testBit(bitmap, 33, 49, false) < 0) + goto error; + if (testBit(bitmap, 51, 87, false) < 0) + goto error; + if (testBit(bitmap, 100, 1020, false) < 0) + goto error; + + bitsString2 = virBitmapFormat(bitmap); + if (strcmp(bitsString1, bitsString2)) + goto error; + + virBitmapSetAll(bitmap); + if (testBit(bitmap, 0, size - 1, true) < 0) + goto error; + + if (!virBitmapIsAllSet(bitmap)) + goto error; + + virBitmapClearAll(bitmap); + if (testBit(bitmap, 0, size - 1, false) < 0) + goto error; + + ret = 0; + +error: + virBitmapFree(bitmap); + VIR_FREE(bitsString2); + return ret; +} + +static int test3(const void *data ATTRIBUTE_UNUSED) +{ + virBitmapPtr bitmap = NULL; + int ret = -1; + int size = 5; + int i; + + if ((bitmap = virBitmapNew(size)) == NULL) + goto error; + + for (i = 0; i < size; i++) + ignore_value(virBitmapSetBit(bitmap, i)); + + if (!virBitmapIsAllSet(bitmap)) + goto error; + + ret = 0; + +error: + virBitmapFree(bitmap); + return ret; +} + +/* test for virBitmapNextSetBit */ +static int test4(const void *data ATTRIBUTE_UNUSED) +{ + const char *bitsString = "0, 2-4, 6-10, 12, 14-18, 20, 22, 25"; + int size = 40; + int bitsPos[] = { + 0, 2, 3, 4, 6, 7, 8, 9, 10, 12, + 14, 15, 16, 17, 18, 20, 22, 25 + }; + int npos = 18; + virBitmapPtr bitmap = NULL; + int i, j; + + /* 1. zero set */ + + bitmap = virBitmapNew(size); + if (!bitmap) + goto error; + + if (virBitmapNextSetBit(bitmap, -1) >= 0) + goto error; + + virBitmapFree(bitmap); + bitmap = NULL; + + /* 2. partial set */ + + if (virBitmapParse(bitsString, 0, &bitmap, size) < 0) + goto error; + if (!bitmap) + goto error; + + j = 0; + i = -1; + + while (j < npos) { + i = virBitmapNextSetBit(bitmap, i); + if (i != bitsPos[j++]) + goto error; + } + + if (virBitmapNextSetBit(bitmap, i) > 0) + goto error; + + /* 3. full set */ + + i = -1; + virBitmapSetAll(bitmap); + + for (j = 0; j < size; j++) { + i = virBitmapNextSetBit(bitmap, i); + if (i != j) + goto error; + } + + if (virBitmapNextSetBit(bitmap, i) > 0) + goto error; + + virBitmapFree(bitmap); + return 0; + +error: + virBitmapFree(bitmap); + return -1; +} + +/* test for virBitmapNewData/ToData */ +static int test5(const void *v ATTRIBUTE_UNUSED) +{ + char data[] = {0x01, 0x02, 0x00, 0x00}; + unsigned char *data2 = NULL; + int len2; + int bits[] = {0, 9}; + virBitmapPtr bitmap; + int i, j; + int ret = -1; + + bitmap = virBitmapNewData(data, 4); + if (!bitmap) + goto error; + + i = 0; + j = -1; + while (i < sizeof(bits)/sizeof(int) && + (j = virBitmapNextSetBit(bitmap, j)) >= 0) { + if (j != bits[i++]) + goto error; + } + if (virBitmapNextSetBit(bitmap, j) > 0) + goto error; + + ignore_value(virBitmapSetBit(bitmap, 2)); + ignore_value(virBitmapSetBit(bitmap, 15)); + + if (virBitmapToData(bitmap, &data2, &len2) < 0) + goto error; + + if (data2[0] != 0x05 || + data2[1] != 0x82 || + data2[2] != 0x00 || + data2[3] != 0x00) + goto error; + + ret = 0; +error: + virBitmapFree(bitmap); + VIR_FREE(data2); + return ret; +} + + +/* test for virBitmapFormat */ +static int test6(const void *v ATTRIBUTE_UNUSED) +{ + virBitmapPtr bitmap = NULL; + char *str = NULL; + int size = 64; + int ret = -1; + + bitmap = virBitmapNew(size); + if (!bitmap) + goto error; + + str = virBitmapFormat(bitmap); + if (!str) + goto error; + + if (!STREQ(str, "")) + goto error; + + VIR_FREE(str); + + ignore_value(virBitmapSetBit(bitmap, 0)); + str = virBitmapFormat(bitmap); + if (!str) + goto error; + + if (!STREQ(str, "0")) + goto error; + + VIR_FREE(str); + + ignore_value(virBitmapSetBit(bitmap, 4)); + ignore_value(virBitmapSetBit(bitmap, 5)); + str = virBitmapFormat(bitmap); + if (!str) + goto error; + + if (!STREQ(str, "0,4-5")) + goto error; + + VIR_FREE(str); + + ignore_value(virBitmapSetBit(bitmap, 6)); + str = virBitmapFormat(bitmap); + if (!str) + goto error; + + if (!STREQ(str, "0,4-6")) + goto error; + + VIR_FREE(str); + + ignore_value(virBitmapSetBit(bitmap, 13)); + ignore_value(virBitmapSetBit(bitmap, 14)); + ignore_value(virBitmapSetBit(bitmap, 15)); + ignore_value(virBitmapSetBit(bitmap, 16)); + str = virBitmapFormat(bitmap); + if (!str) + goto error; + + if (!STREQ(str, "0,4-6,13-16")) + goto error; + + VIR_FREE(str); + + ignore_value(virBitmapSetBit(bitmap, 62)); + ignore_value(virBitmapSetBit(bitmap, 63)); + str = virBitmapFormat(bitmap); + if (!str) + goto error; + + if (!STREQ(str, "0,4-6,13-16,62-63")) + goto error; + + + ret = 0; +error: + virBitmapFree(bitmap); + VIR_FREE(str); + return ret; +} + +static int +mymain(void) +{ + int ret = 0; + + if (virtTestRun("test1", 1, test1, NULL) < 0) + ret = -1; + if (virtTestRun("test2", 1, test2, NULL) < 0) + ret = -1; + if (virtTestRun("test3", 1, test3, NULL) < 0) + ret = -1; + if (virtTestRun("test4", 1, test4, NULL) < 0) + ret = -1; + if (virtTestRun("test5", 1, test5, NULL) < 0) + ret = -1; + if (virtTestRun("test6", 1, test6, NULL) < 0) + ret = -1; + + + return ret; +} + +VIRT_TEST_MAIN(mymain)