New subject: [libvirt] [PATCH v1 2/8] use virBitmap to store cpupin info

30 Aug 2012

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.
---
 .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
 /tests/virbuftest
 /tests/virdrivermoduletest
diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
index 27eb43e..9c27218 100644
--- a/src/libvirt_private.syms
+++ b/src/libvirt_private.syms
@@ -7,11 +7,21 @@
 
 # bitmap.h
 virBitmapAlloc;
+virBitmapAllocFromData;
+virBitmapClearAll;
 virBitmapClearBit;
+virBitmapCmp;
+virBitmapCopy;
+virBitmapFormat;
 virBitmapFree;
 virBitmapGetBit;
+virBitmapIsAllSet;
+virBitmapParse;
+virBitmapSetAll;
 virBitmapSetBit;
+virBitmapSize;
 virBitmapString;
+virBitmapToData;
 
 
 # buf.h
diff --git a/src/util/bitmap.c b/src/util/bitmap.c
index 53a8a38..2e668c6 100644
--- a/src/util/bitmap.c
+++ 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;
 };
 
 
-#define VIR_BITMAP_BITS_PER_UNIT  ((int) sizeof(unsigned long) * CHAR_BIT)
+#define VIR_BITMAP_BITS_PER_UNIT  ((int) sizeof(unsigned char) * CHAR_BIT)
 #define VIR_BITMAP_UNIT_OFFSET(b) ((b) / VIR_BITMAP_BITS_PER_UNIT)
 #define VIR_BITMAP_BIT_OFFSET(b)  ((b) % VIR_BITMAP_BITS_PER_UNIT)
 #define VIR_BITMAP_BIT(b)         (1UL << VIR_BITMAP_BIT_OFFSET(b))
@@ -129,6 +131,12 @@ int virBitmapClearBit(virBitmapPtr bitmap, size_t b)
     return 0;
 }
 
+/* Helper function. caller must ensure b < bitmap->size */
+static bool bitmapIsset(virBitmapPtr bitmap, size_t b)
+{
+    return !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b));
+}
+
 /**
  * virBitmapGetBit:
  * @bitmap: Pointer to bitmap
@@ -145,7 +153,7 @@ int virBitmapGetBit(virBitmapPtr bitmap, size_t b, bool *result)
     if (bitmap->size <= b)
         return -1;
 
-    *result = !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b));
+    *result = bitmapIsset(bitmap, b);
     return 0;
 }
 
@@ -168,7 +176,7 @@ char *virBitmapString(virBitmapPtr bitmap)
           VIR_BITMAP_BITS_PER_UNIT;
 
     while (sz--) {
-        virBufferAsprintf(&buf, "%0*lx",
+        virBufferAsprintf(&buf, "%0*hx",
                           VIR_BITMAP_BITS_PER_UNIT / 4,
                           bitmap->map[sz]);
     }
@@ -180,3 +188,378 @@ 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;
+    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);
+        if (ret != 0)
+            goto error;
+        else if (isset) {
+            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);
+}
+
+/**
+ * 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;
+    const char *cur;
+    char *tmp;
+    int i, start, last;
+
+    if (!str)
+        return -1;
+
+    cur = str;
+    virSkipSpaces(&cur);
+
+    if (*cur == 0)
+        return -1;
+
+    *bitmap = virBitmapAlloc(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 = 1;
+        }
+
+        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 (bitmapIsset(*bitmap, start)) {
+                    ignore_value(virBitmapClearBit(*bitmap, start));
+                    ret--;
+                }
+            } else {
+                if (!bitmapIsset(*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 (!bitmapIsset(*bitmap, i)) {
+                    ignore_value(virBitmapSetBit(*bitmap, i));
+                    ret++;
+                }
+            }
+
+            virSkipSpaces(&cur);
+        }
+
+        if (*cur == ',') {
+            cur++;
+            virSkipSpaces(&cur);
+            neg = 0;
+        } else if(*cur == 0 || *cur == sep) {
+            break;
+        } else {
+            goto parse_error;
+        }
+    }
+
+    return ret;
+
+parse_error:
+    virBitmapFree(*bitmap);
+    *bitmap = NULL;
+    return -1;
+}
+
+/**
+ * virBitmapCopy:
+ * @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 virBitmapCopy(virBitmapPtr src)
+{
+    virBitmapPtr dst;
+    size_t sz;
+
+    sz = (src->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+
+    if (VIR_ALLOC(dst) < 0)
+        return NULL;
+
+    if (VIR_ALLOC_N(dst->map, sz) < 0) {
+        VIR_FREE(dst);
+        return NULL;
+    }
+
+    memcpy(dst->map, src->map, sz);
+    dst->size = src->size;
+
+    return dst;
+}
+
+/**
+ * virBitmapAllocFromData:
+ * @data: the data
+ * @len: len of @data in byte
+ *
+ * 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);
+
+    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, char **data, int *dataLen)
+{
+    size_t sz;
+
+    sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+
+    if (VIR_ALLOC_N(*data, sz) < 0)
+        return -1;
+
+    memcpy(*data, bitmap->map, sz);
+    *dataLen = sz;
+
+    return 0;
+}
+
+/**
+ * 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.
+ */
+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;
+    for (; i < sz; i++) {
+        if (b->map[i])
+            return false;
+    }
+
+    return true;
+}
+
+size_t virBitmapSize(virBitmapPtr bitmap)
+{
+    return bitmap->size;
+}
+
+/**
+ * virBitmapSetAll:
+ * @bitmap: the bitmap
+ *
+ * set all bits in @bitmap.
+ */
+void virBitmapSetAll(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] = -1;
+}
+
+/**
+ * virBitmapClearAll:
+ * @bitmap: the bitmap
+ *
+ * clear all bits in @bitmap.
+ */
+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;
+}
+
+/**
+ * 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)
+            return false;
+
+    if (unusedBits > 0) {
+        if ((bitmap->map[sz - 1] & ((1 << (VIR_BITMAP_BITS_PER_UNIT - unusedBits + 1)) - 1))
+            != ((1 << (VIR_BITMAP_BITS_PER_UNIT - unusedBits + 1)) - 1))
+            return false;
+    }
+
+    return true;
+}
diff --git a/src/util/bitmap.h b/src/util/bitmap.h
index c3e6222..4823604 100644
--- a/src/util/bitmap.h
+++ 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);
+
+int virBitmapParse(const char *str,
+                   char sep,
+                   virBitmapPtr *bitmap,
+                   size_t bitmapSize);
+
+virBitmapPtr virBitmapCopy(virBitmapPtr src);
+
+virBitmapPtr virBitmapAllocFromData(void *data, int len);
+
+int virBitmapToData(virBitmapPtr bitmap, char **data, int *dataLen);
+
+bool virBitmapCmp(virBitmapPtr b1, virBitmapPtr b2);
+
+size_t virBitmapSize(virBitmapPtr bitmap);
+
+void virBitmapSetAll(virBitmapPtr bitmap);
+
+void virBitmapClearAll(virBitmapPtr bitmap);
+
+bool virBitmapIsAllSet(virBitmapPtr bitmap);
+
 #endif
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 8cf8015..ec436df 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
@@ -562,6 +563,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)
@@ -592,6 +597,7 @@ shunloadtest_SOURCES = \
 shunloadtest_LDADD = $(LIB_PTHREAD)
 shunloadtest_DEPENDENCIES = libshunload.la
 
+
 if WITH_CIL
 CILOPTFLAGS =
 CILOPTINCS =
diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c
new file mode 100644
index 0000000..c688618
--- /dev/null
+++ b/tests/virbitmaptest.c
@@ -0,0 +1,134 @@
+/*
+ * 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 <time.h>
+#include <sched.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 = virBitmapAlloc(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;
+}
+
+bool testBit(virBitmapPtr bitmap, unsigned int start, unsigned int end)
+{
+    int i;
+    bool result;
+
+    for (i = start; i <= end; i++) {
+        if (virBitmapGetBit(bitmap, i, &result) < 0)
+            return 0;
+        if (!result)
+            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 = 1024;
+
+    if (virBitmapParse(bitsString1, 0, &bitmap, size) < 0)
+        goto error;
+
+    if (!testBit(bitmap, 1, 32))
+        goto error;
+    if (!testBit(bitmap, 50, 50))
+        goto error;
+    if (!testBit(bitmap, 88, 99))
+        goto error;
+    if (!testBit(bitmap, 1021, 1023))
+        goto error;
+
+    if (testBit(bitmap, 0, 0))
+        goto error;
+    if (testBit(bitmap, 33,49))
+        goto error;
+    if (testBit(bitmap, 51,87))
+        goto error;
+    if (testBit(bitmap, 100,1020))
+        goto error;
+
+    bitsString2 = virBitmapFormat(bitmap);
+    if (strcmp(bitsString1, bitsString2))
+        goto error;
+
+    virBitmapSetAll(bitmap);
+    if (!testBit(bitmap, 0, size - 1))
+        goto error;
+
+    virBitmapClearAll(bitmap);
+    if (testBit(bitmap, 0, size - 1))
+        goto error;
+
+    ret = 0;
+
+error:
+    virBitmapFree(bitmap);
+    VIR_FREE(bitsString2);
+    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;
+
+    return ret;
+}
+
+VIRT_TEST_MAIN(mymain)
-- 
1.7.10.2

    

[libvirt] [PATCH v1 1/8] New functions for virBitmap

Hu Tao

Hu Tao

Eric Blake

Hu Tao

Eric Blake

Hu Tao

Eric Blake

Hu Tao

Eric Blake

Hu Tao

Hu Tao

Eric Blake

Hu Tao

Eric Blake

tags

participants (2)