11:01 a.m.
Add a growable bitmap implementation building on top of the 'regular'
bitmap implementation. (no doubt, this could also be done differently...)
This patch also adds a test virgbitmaptest.c that is largely a copy of
virbitmaptest.c with some minor modifications to test for growth of the
bitmap.
Signed-off-by: Stefan Berger <stefanb(a)linux.vnet.ibm.com>
---
PS: This patch builds on top of a patch with a virBitmapNextClearBit
implementation.
---
src/Makefile.am | 1
src/libvirt_private.syms | 22 ++
src/util/virbitmap.c | 17 +
src/util/virbitmap.h | 6
src/util/virgbitmap.c | 348 ++++++++++++++++++++++++++++++++
src/util/virgbitmap.h | 95 ++++++++
tests/Makefile.am | 5
tests/virgbitmaptest.c | 499
+++++++++++++++++++++++++++++++++++++++++++++++
8 files changed, 993 insertions(+)
Index: libvirt/src/Makefile.am
===================================================================
--- libvirt.orig/src/Makefile.am
+++ libvirt/src/Makefile.am
@@ -71,6 +71,7 @@ UTIL_SOURCES = \
util/virevent.c util/virevent.h \
util/vireventpoll.c util/vireventpoll.h \
util/virfile.c util/virfile.h \
+ util/virgbitmap.c util/virgbitmap.h \
util/virhash.c util/virhash.h \
util/virhashcode.c util/virhashcode.h \
util/virhook.c util/virhook.h \
Index: libvirt/src/util/virbitmap.c
===================================================================
--- libvirt.orig/src/util/virbitmap.c
+++ libvirt/src/util/virbitmap.c
@@ -111,6 +111,23 @@ int virBitmapCopy(virBitmapPtr dst, virB
return 0;
}
+/*
+ * virBitmapCopyResize:
+ * @dst: Destination bitmap
+ * @src: Source bitmap
+ *
+ * Copy bits from source bitmap @src into destination bitmap @dst
+ * where the source and destination bitmaps may be of different size.
+ * Any bits not found in the source bitmap will remain untouched
+ * in the destination bitmap.
+ */
+void virBitmapCopyResize(virBitmapPtr dst, virBitmapPtr src)
+{
+ size_t tocopy = MIN(src->map_len, dst->map_len);
+
+ memcpy(dst->map, src->map,
+ tocopy * sizeof(src->map[0]));
+}
/**
* virBitmapSetBit:
Index: libvirt/src/util/virbitmap.h
===================================================================
--- libvirt.orig/src/util/virbitmap.h
+++ libvirt/src/util/virbitmap.h
@@ -49,6 +49,12 @@ void virBitmapFree(virBitmapPtr bitmap);
int virBitmapCopy(virBitmapPtr dst, virBitmapPtr src);
/*
+ * Copy bits from @src to @dst. The bitmap sizes
+ * need not be the same
+ */
+void virBitmapCopyResize(virBitmapPtr dst, virBitmapPtr src);
+
+/*
* Set bit position @b in @bitmap
*/
int virBitmapSetBit(virBitmapPtr bitmap, size_t b)
Index: libvirt/src/util/virgbitmap.c
===================================================================
--- /dev/null
+++ libvirt/src/util/virgbitmap.c
@@ -0,0 +1,348 @@
+/*
+ * virgbitmap.c: Growable bitmap operations
+ *
+ * Copyright (C) 2013 IBM Corporation
+ *
+ * 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/>;.
+ *
+ * Author: Stefan Berger <stefanb(a)linux.vnet.ibm.com>
+ */
+
+#include <config.h>
+
+#include "virgbitmap.h"
+#include "viralloc.h"
+
+struct _virGBitmap {
+ virBitmapPtr bitmap;
+};
+
+/**
+ * virGBitmapNew:
+ * @size: number of bits
+ *
+ * Allocate a growable bitmap capable of initially containing @size bits.
+ *
+ * Returns a pointer to the allocated bitmap or NULL if
+ * memory cannot be allocated.
+ */
+virGBitmapPtr virGBitmapNew(size_t size)
+{
+ virGBitmapPtr bitmap;
+
+ if (VIR_ALLOC(bitmap) < 0)
+ return NULL;
+
+ bitmap->bitmap = virBitmapNew(size);
+
+ if (!bitmap->bitmap) {
+ virGBitmapFree(bitmap);
+ return NULL;
+ }
+
+ return bitmap;
+}
+
+/**
+ * virGBitmapFree:
+ * @bitmap: previously allocated bitmap
+ *
+ * Free @bitmap previously allocated by virBitmapNew.
+ */
+void virGBitmapFree(virGBitmapPtr bitmap)
+{
+ if (bitmap) {
+ virBitmapFree(bitmap->bitmap);
+ VIR_FREE(bitmap);
+ }
+}
+
+/**
+ * virGBitmapResize:
+ * @bitmap: previously allocated bitmap
+ * @new_size: new size of the bitmap
+ *
+ * Resize the @bitmap to the given @new_size. Old bits are copied
+ * into the new
+ */
+static int virGBitmapResize(virGBitmapPtr bitmap, size_t new_size)
+{
+ virBitmapPtr bm;
+
+ if (!(bm = virBitmapNew(new_size)))
+ return -1;
+
+ virBitmapCopyResize(bm, bitmap->bitmap);
+
+ virBitmapFree(bitmap->bitmap);
+ bitmap->bitmap = bm;
+
+ return 0;
+}
+
+/**
+ * virGBitmapSetBit:
+ * @bitmap: Pointer to growable bitmap
+ * @b: bit position to set
+ *
+ * Set bit position @b in @bitmap. Grow the @bitmap if necessary
+ * filling newly allocated bits with zeros.
+ *
+ * Returns 0 on if bit is successfully set, -1 on error.
+ */
+int virGBitmapSetBit(virGBitmapPtr bitmap, ssize_t b)
+{
+ if (virBitmapSize(bitmap->bitmap) <= b &&
+ virGBitmapResize(bitmap,
+ ((unsigned long long)b * 120) / 100) < 0)
+ return -1;
+
+ return virBitmapSetBit(bitmap->bitmap, b);
+}
+
+/**
+ * virBitmapGetBit:
+ * @bitmap: Pointer to bitmap
+ * @b: bit position to get
+ * @result: bool pointer to receive bit setting
+ *
+ * Get setting of bit position @b in @bitmap and store in @result.
+ * Note: If the bitmap is not currently large enough, it will grow
+ * to at least the size of the bit position @b.
+ *
+ * On success, @result will contain the setting of @b and 0 is
+ * returned. On failure, -1 is returned and @result is unchanged.
+ */
+int virGBitmapGetBit(virGBitmapPtr bitmap, size_t b, bool *result)
+{
+ if (virBitmapSize(bitmap->bitmap) <= b) {
+ if (virGBitmapResize(bitmap,
+ ((unsigned long long)b * 120) / 100) < 0)
+ return -1;
+ *result = 0;
+ return 0;
+ }
+
+ return virBitmapGetBit(bitmap->bitmap, b, result);
+}
+
+/**
+ * virGBitmapFormat:
+ * @bitmap: the bitmap
+ *
+ * This function is the counterpart of virGBitmapParse. This function
creates
+ * a human-readable string representing the bits in bitmap.
+ *
+ * See virGBitmapParse for the format of @str.
+ *
+ * Returns the string on success or NULL otherwise. Caller should call
+ * VIR_FREE to free the string.
+ */
+char *virGBitmapFormat(virGBitmapPtr bitmap)
+{
+ return virBitmapFormat(bitmap->bitmap);
+}
+
+size_t virGBitmapSize(virGBitmapPtr bitmap)
+{
+ return virBitmapSize(bitmap->bitmap);
+}
+
+/**
+ * virGBitmapSetAll:
+ * @bitmap: the bitmap
+ *
+ * set all bits in @bitmap.
+ */
+void virGBitmapSetAll(virGBitmapPtr bitmap)
+{
+ virBitmapSetAll(bitmap->bitmap);
+}
+
+/**
+ * virGBitmapClearAll:
+ * @bitmap: the bitmap
+ *
+ * clear all bits in @bitmap.
+ */
+void virGBitmapClearAll(virGBitmapPtr bitmap)
+{
+ virBitmapClearAll(bitmap->bitmap);
+}
+
+/**
+ * virGBitmapIsAllSet:
+ * @bitmap: the bitmap to check
+ *
+ * check if all bits in @bitmap are set.
+ */
+bool virGBitmapIsAllSet(virGBitmapPtr bitmap)
+{
+ return virBitmapIsAllSet(bitmap->bitmap);
+}
+
+/**
+ * virGBitmapParse:
+ * @str: points to a string representing a human-readable bitmap
+ * @terminator: character separating the bitmap to parse
+ * @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.
+ *
+ * To allow parsing of bitmaps within larger strings it is possible to set
+ * a termination character in the argument @terminator. When the character
+ * in @terminator is encountered in @str, the parsing of the bitmap stops.
+ * Pass 0 as @terminator if it is not needed. Whitespace characters may not
+ * be used as terminators.
+ *
+ * Returns the number of bits set in @bitmap, or -1 in case of error.
+ */
+int
+virGBitmapParse(const char *str,
+ char terminator,
+ virGBitmapPtr *bitmap,
+ size_t bitmapSize)
+{
+ virGBitmapPtr res;
+
+ if (VIR_ALLOC(res) < 0)
+ return -1;
+
+ if (virBitmapParse(str, terminator, &res->bitmap, bitmapSize) < 0) {
+ VIR_FREE(res);
+ return -1;
+ }
+
+ *bitmap = res;
+
+ return 0;
+}
+
+
+/**
+ * virGBitmapNewData:
+ * @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.
+ */
+virGBitmapPtr virGBitmapNewData(void *data, int len)
+{
+ virGBitmapPtr res;
+
+ if (VIR_ALLOC(res) < 0)
+ return NULL;
+
+ res->bitmap = virBitmapNewData(data, len);
+ if (!res->bitmap) {
+ VIR_FREE(res);
+ return NULL;
+ }
+
+ return res;
+}
+
+/**
+ * virGBitmapToData:
+ * @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 virGBitmapToData(virGBitmapPtr bitmap, unsigned char **data, int
*dataLen)
+{
+ return virBitmapToData(bitmap->bitmap, data, dataLen);
+}
+
+
+/**
+ * virGBitmapNextSetBit:
+ * @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. This function will never grow the bitmap.
+ *
+ * returns the position of the found bit, or -1 if no bit found.
+ */
+ssize_t virGBitmapNextSetBit(virGBitmapPtr bitmap, ssize_t pos)
+{
+ /* never grow since we won't find set bits there */
+ return virBitmapNextSetBit(bitmap->bitmap, pos);
+}
+
+/**
+ * virGBitmapNextClearBit:
+ * @bitmap: the bitmap
+ * @pos: the position after which to search for a set bit
+ *
+ * Search the first clear bit after position @pos in bitmap @bitmap.
+ * @pos can be -1 to search for the first set bit. Position starts
+ * at 0. This function will grow the bitmap if the currently allocated
+ * bitmap has all bits set.
+ *
+ * returns the position of the found bit, or -1 if no bit found.
+ */
+ssize_t virGBitmapNextClearBit(virGBitmapPtr bitmap, ssize_t pos)
+{
+ size_t lastpos, newsize, max_bit;
+ ssize_t res;
+
+ if (pos < 0)
+ pos = -1;
+
+ if (pos < (ssize_t)virBitmapSize(bitmap->bitmap)) {
+ res = virBitmapNextClearBit(bitmap->bitmap, pos);
+
+ if (res >= 0)
+ return res;
+ }
+
+ max_bit = virBitmapSize(bitmap->bitmap);
+
+ lastpos = max_bit - 1;
+ if (pos > lastpos)
+ lastpos = pos;
+
+ newsize = (max_bit > 80)
+ ? ((unsigned long long)max_bit * 120) / 100 /* 20 % growth */
+ : max_bit + 24;
+ if (virGBitmapResize(bitmap, newsize) < 0)
+ return -1;
+
+ return virBitmapNextClearBit(bitmap->bitmap, lastpos);
+}
+
+/* Return the number of bits currently set in the map. */
+size_t
+virGBitmapCountBits(virGBitmapPtr bitmap)
+{
+ return virBitmapCountBits(bitmap->bitmap);
+}
Index: libvirt/src/util/virgbitmap.h
===================================================================
--- /dev/null
+++ libvirt/src/util/virgbitmap.h
@@ -0,0 +1,95 @@
+/*
+ * virgbitmap.h: Growable bitmap operations
+ *
+ * Copyright (C) 2013 IBM Corporation
+ *
+ * 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/>;.
+ *
+ * Derived from virbitmap.h.
+ *
+ * Author: Stefan Berger <stefanb(a)linux.vnet.ibm.com>
+ */
+
+#ifndef __GBITMAP_H__
+# define __GBITMAP_H__
+
+# include "internal.h"
+
+# include <sys/types.h>
+
+# include "virbitmap.h"
+
+typedef struct _virGBitmap virGBitmap;
+typedef virGBitmap *virGBitmapPtr;
+
+/*
+ * Allocate a bitmap capable of initially containing @size bits.
+ */
+virGBitmapPtr virGBitmapNew(size_t size) ATTRIBUTE_RETURN_CHECK;
+
+/*
+ * Free previously allocated bitmap
+ */
+void virGBitmapFree(virGBitmapPtr bitmap);
+
+/*
+ * Set bit position @b in @bitmap
+ */
+int virGBitmapSetBit(virGBitmapPtr bitmap, ssize_t pos)
+ ATTRIBUTE_NONNULL(1);
+
+/*
+ * Get setting of bit position @b in @bitmap and store in @result
+ */
+int virGBitmapGetBit(virGBitmapPtr bitmap, size_t b, bool *result)
+ ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3) ATTRIBUTE_RETURN_CHECK;
+
+char *virGBitmapFormat(virGBitmapPtr bitmap)
+ ATTRIBUTE_NONNULL(1);
+
+int virGBitmapParse(const char *str,
+ char sep,
+ virGBitmapPtr *bitmap,
+ size_t bitmapSize);
+
+virGBitmapPtr virGBitmapNewData(void *data, int len) ATTRIBUTE_NONNULL(1);
+
+int virGBitmapToData(virGBitmapPtr bitmap, unsigned char **data, int
*dataLen)
+ ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(2);
+
+size_t virGBitmapSize(virGBitmapPtr bitmap)
+ ATTRIBUTE_NONNULL(1);
+
+void virGBitmapSetAll(virGBitmapPtr bitmap)
+ ATTRIBUTE_NONNULL(1);
+
+void virGBitmapClearAll(virGBitmapPtr bitmap)
+ ATTRIBUTE_NONNULL(1);
+
+bool virGBitmapIsAllSet(virGBitmapPtr bitmap)
+ ATTRIBUTE_NONNULL(1);
+
+ ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3);
+
+ssize_t virGBitmapNextSetBit(virGBitmapPtr bitmap, ssize_t pos)
+ ATTRIBUTE_NONNULL(1);
+
+ssize_t virGBitmapNextClearBit(virGBitmapPtr bitmap, ssize_t pos)
+ ATTRIBUTE_NONNULL(1);
+
+size_t virGBitmapCountBits(virGBitmapPtr bitmap)
+ ATTRIBUTE_NONNULL(1);
+
+#endif
Index: libvirt/tests/Makefile.am
===================================================================
--- libvirt.orig/tests/Makefile.am
+++ libvirt/tests/Makefile.am
@@ -96,6 +96,7 @@ test_programs = virshtest sockettest \
virtimetest viruritest virkeyfiletest \
virauthconfigtest \
virbitmaptest \
+ virgbitmaptest \
virlockspacetest \
virstringtest \
virportallocatortest \
@@ -649,6 +650,10 @@ virbitmaptest_SOURCES = \
virbitmaptest.c testutils.h testutils.c
virbitmaptest_LDADD = $(LDADDS)
+virgbitmaptest_SOURCES = \
+ virgbitmaptest.c testutils.h testutils.c
+virgbitmaptest_LDADD = $(LDADDS)
+
jsontest_SOURCES = \
jsontest.c testutils.h testutils.c
jsontest_LDADD = $(LDADDS)
Index: libvirt/tests/virgbitmaptest.c
===================================================================
--- /dev/null
+++ libvirt/tests/virgbitmaptest.c
@@ -0,0 +1,499 @@
+/*
+ * 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 "virgbitmap.h"
+
+static int test1(const void *data ATTRIBUTE_UNUSED)
+{
+ virGBitmapPtr bitmap;
+ int size;
+ int bit;
+ bool result;
+ int ret = -1;
+
+ size = 1024;
+ bit = 100;
+ if (!(bitmap = virGBitmapNew(size)))
+ goto error;
+
+ if (virGBitmapSetBit(bitmap, bit) < 0)
+ goto error;
+
+ if (virGBitmapGetBit(bitmap, bit, &result) < 0)
+ goto error;
+
+ if (!result)
+ goto error;
+
+ if (virGBitmapGetBit(bitmap, bit + 1, &result) < 0)
+ goto error;
+
+ if (result)
+ goto error;
+
+ ret = 0;
+
+error:
+ virGBitmapFree(bitmap);
+ return ret;
+}
+
+static int
+testBit(virGBitmapPtr bitmap,
+ unsigned int start,
+ unsigned int end,
+ bool expected)
+{
+ int i;
+ bool result;
+
+ for (i = start; i <= end; i++) {
+ if (virGBitmapGetBit(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";
+ const char *bitsStringAfter = "1-32,50,88-99,1021-1023,1111";
+ char *bitsString2 = NULL, *bitsString3 = NULL;
+ virGBitmapPtr bitmap = NULL;
+ int ret = -1;
+ int size = 1025;
+
+ if (virGBitmapParse(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;
+
+ if (virGBitmapCountBits(bitmap) != 48)
+ goto error;
+
+ if (!(bitsString2 = virGBitmapFormat(bitmap)))
+ goto error;
+ if (strcmp(bitsString1, bitsString2))
+ goto error;
+
+ if (virGBitmapSetBit(bitmap, 1111) < 0)
+ goto error;
+
+ if (!(bitsString3 = virGBitmapFormat(bitmap)))
+ goto error;
+ if (strcmp(bitsStringAfter, bitsString3))
+ goto error;
+
+ size = 1111;
+ virGBitmapSetAll(bitmap);
+ if (testBit(bitmap, 0, size - 1, true) < 0)
+ goto error;
+ if (virGBitmapCountBits(bitmap) < size)
+ goto error;
+
+ if (!virGBitmapIsAllSet(bitmap))
+ goto error;
+
+ virGBitmapClearAll(bitmap);
+ if (testBit(bitmap, 0, size - 1, false) < 0)
+ goto error;
+ if (virGBitmapCountBits(bitmap) != 0)
+ goto error;
+
+ ret = 0;
+
+error:
+ virGBitmapFree(bitmap);
+ VIR_FREE(bitsString2);
+ VIR_FREE(bitsString3);
+ return ret;
+}
+
+static int test3(const void *data ATTRIBUTE_UNUSED)
+{
+ virGBitmapPtr bitmap = NULL;
+ int ret = -1;
+ int size = 5;
+ int i;
+
+ if ((bitmap = virGBitmapNew(size)) == NULL)
+ goto error;
+
+ for (i = 0; i < size * 2; i++)
+ ignore_value(virGBitmapSetBit(bitmap, i));
+
+ if (virGBitmapSize(bitmap) < (2 * size))
+ goto error;
+
+ if (!virGBitmapIsAllSet(bitmap))
+ goto error;
+
+ ret = 0;
+
+error:
+ virGBitmapFree(bitmap);
+ return ret;
+}
+
+/* test for virGBitmapNextSetBit */
+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;
+ virGBitmapPtr bitmap = NULL;
+ int i, j;
+
+ /* 1. zero set */
+
+ bitmap = virGBitmapNew(size);
+ if (!bitmap)
+ goto error;
+
+ if (virGBitmapNextSetBit(bitmap, -1) >= 0)
+ goto error;
+
+ virGBitmapFree(bitmap);
+ bitmap = NULL;
+
+ /* 2. partial set */
+
+ if (virGBitmapParse(bitsString, 0, &bitmap, size) < 0)
+ goto error;
+ if (!bitmap)
+ goto error;
+
+ j = 0;
+ i = -1;
+
+ while (j < npos) {
+ i = virGBitmapNextSetBit(bitmap, i);
+ if (i != bitsPos[j++])
+ goto error;
+ }
+
+ if (virGBitmapNextSetBit(bitmap, i) > 0)
+ goto error;
+
+ /* 3. full set */
+
+ i = -1;
+ virGBitmapSetAll(bitmap);
+
+ for (j = 0; j < size; j++) {
+ i = virGBitmapNextSetBit(bitmap, i);
+ if (i != j)
+ goto error;
+ }
+
+ if (virGBitmapNextSetBit(bitmap, i) > 0)
+ goto error;
+
+ virGBitmapFree(bitmap);
+ return 0;
+
+error:
+ virGBitmapFree(bitmap);
+ return -1;
+}
+
+/* test for virGBitmapNewData/ToData */
+static int test5(const void *v ATTRIBUTE_UNUSED)
+{
+ char data[] = {0x01, 0x02, 0x00, 0x00, 0x04};
+ unsigned char *data2 = NULL;
+ int len2;
+ int bits[] = {0, 9, 34};
+ virGBitmapPtr bitmap;
+ int i, j;
+ int ret = -1;
+
+ bitmap = virGBitmapNewData(data, sizeof(data));
+ if (!bitmap)
+ goto error;
+
+ i = 0;
+ j = -1;
+ while (i < sizeof(bits)/sizeof(int) &&
+ (j = virGBitmapNextSetBit(bitmap, j)) >= 0) {
+ if (j != bits[i++])
+ goto error;
+ }
+ if (virGBitmapNextSetBit(bitmap, j) > 0)
+ goto error;
+
+ ignore_value(virGBitmapSetBit(bitmap, 2));
+ ignore_value(virGBitmapSetBit(bitmap, 15));
+
+ if (virGBitmapToData(bitmap, &data2, &len2) < 0)
+ goto error;
+
+ if (len2 != sizeof(data) ||
+ data2[0] != 0x05 ||
+ data2[1] != 0x82 ||
+ data2[2] != 0x00 ||
+ data2[3] != 0x00 ||
+ data2[4] != 0x04)
+ goto error;
+
+ ret = 0;
+error:
+ virGBitmapFree(bitmap);
+ VIR_FREE(data2);
+ return ret;
+}
+
+/* test for virGBitmapFormat */
+static int test6(const void *v ATTRIBUTE_UNUSED)
+{
+ virGBitmapPtr bitmap = NULL;
+ char *str = NULL;
+ int size = 64;
+ int ret = -1;
+
+ bitmap = virGBitmapNew(size);
+ if (!bitmap)
+ goto error;
+
+ str = virGBitmapFormat(bitmap);
+ if (!str)
+ goto error;
+
+ if (!STREQ(str, ""))
+ goto error;
+
+ VIR_FREE(str);
+
+ ignore_value(virGBitmapSetBit(bitmap, 0));
+ str = virGBitmapFormat(bitmap);
+ if (!str)
+ goto error;
+
+ if (!STREQ(str, "0"))
+ goto error;
+
+ VIR_FREE(str);
+
+ ignore_value(virGBitmapSetBit(bitmap, 4));
+ ignore_value(virGBitmapSetBit(bitmap, 5));
+ str = virGBitmapFormat(bitmap);
+ if (!str)
+ goto error;
+
+ if (!STREQ(str, "0,4-5"))
+ goto error;
+
+ VIR_FREE(str);
+
+ ignore_value(virGBitmapSetBit(bitmap, 6));
+ str = virGBitmapFormat(bitmap);
+ if (!str)
+ goto error;
+
+ if (!STREQ(str, "0,4-6"))
+ goto error;
+
+ VIR_FREE(str);
+
+ ignore_value(virGBitmapSetBit(bitmap, 13));
+ ignore_value(virGBitmapSetBit(bitmap, 14));
+ ignore_value(virGBitmapSetBit(bitmap, 15));
+ ignore_value(virGBitmapSetBit(bitmap, 16));
+ str = virGBitmapFormat(bitmap);
+ if (!str)
+ goto error;
+
+ if (!STREQ(str, "0,4-6,13-16"))
+ goto error;
+
+ VIR_FREE(str);
+
+ ignore_value(virGBitmapSetBit(bitmap, 62));
+ ignore_value(virGBitmapSetBit(bitmap, 63));
+ str = virGBitmapFormat(bitmap);
+ if (!str)
+ goto error;
+
+ if (!STREQ(str, "0,4-6,13-16,62-63"))
+ goto error;
+
+
+ ret = 0;
+error:
+ virGBitmapFree(bitmap);
+ VIR_FREE(str);
+ return ret;
+}
+
+static int test7(const void *v ATTRIBUTE_UNUSED)
+{
+ virGBitmapPtr bitmap;
+ size_t i;
+ size_t maxBit[] = {
+ 1, 8, 31, 32, 63, 64, 95, 96, 127, 128, 159, 160
+ };
+ size_t nmaxBit = 12;
+
+ for (i = 0; i < nmaxBit; i++) {
+ bitmap = virGBitmapNew(maxBit[i]);
+ if (!bitmap)
+ goto error;
+
+ if (virGBitmapIsAllSet(bitmap))
+ goto error;
+
+ ignore_value(virGBitmapSetBit(bitmap, 1));
+ if (virGBitmapIsAllSet(bitmap))
+ goto error;
+
+ virGBitmapSetAll(bitmap);
+ if (!virGBitmapIsAllSet(bitmap))
+ goto error;
+
+ virGBitmapFree(bitmap);
+ }
+
+ return 0;
+
+error:
+ virGBitmapFree(bitmap);
+ return -1;
+}
+
+/* test for virGBitmapNextClearBit */
+static int test8(const void *data ATTRIBUTE_UNUSED)
+{
+ const char *bitsString = "0, 2-4, 6-10, 12, 14-18, 20, 22, 25,
28-33, 35, "
+ "41-42, 45-46";
+ int size = 48;
+ int noBitsPos[] = {
+ 1, 5, 11, 13, 19, 21, 23, 24,
+ 26, 27, 34, 36, 37, 38, 39, 40,
+ 43, 44, 47
+ };
+ int npos = 19;
+ virGBitmapPtr bitmap = NULL;
+ int i, j;
+
+ /* 1. zero set */
+
+ bitmap = virGBitmapNew(size);
+ if (!bitmap)
+ goto error;
+
+ if (virGBitmapNextClearBit(bitmap, -1) != 0)
+ goto error;
+
+ virGBitmapFree(bitmap);
+ bitmap = NULL;
+
+ /* 2. partial set */
+
+ if (virGBitmapParse(bitsString, 0, &bitmap, size) < 0)
+ goto error;
+ if (!bitmap)
+ goto error;
+
+ j = 0;
+ i = -1;
+
+ while (j < npos) {
+ i = virGBitmapNextClearBit(bitmap, i);
+ if (i != noBitsPos[j++])
+ goto error;
+ }
+
+ if (virGBitmapNextSetBit(bitmap, i) > 0)
+ goto error;
+
+ /* 3. full set */
+
+ i = -1;
+ virGBitmapSetAll(bitmap);
+
+ for (j = 0; j < size; j++) {
+ i = virGBitmapNextSetBit(bitmap, i);
+ if (i != j)
+ goto error;
+ }
+
+ if (virGBitmapNextClearBit(bitmap, i) != i + 1)
+ goto error;
+
+ virGBitmapFree(bitmap);
+ return 0;
+
+error:
+ virGBitmapFree(bitmap);
+ return -1;
+}
+
+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;
+ if (virtTestRun("test7", 1, test7, NULL) < 0)
+ ret = -1;
+ if (virtTestRun("test8", 1, test8, NULL) < 0)
+ ret = -1;
+
+ return ret;
+}
+
+VIRT_TEST_MAIN(mymain)
Index: libvirt/src/libvirt_private.syms
===================================================================
--- libvirt.orig/src/libvirt_private.syms
+++ libvirt/src/libvirt_private.syms
@@ -9,6 +9,7 @@
virBitmapClearAll;
virBitmapClearBit;
virBitmapCopy;
+virBitmapCopyResize;
virBitmapCountBits;
virBitmapEqual;
virBitmapFormat;
@@ -1390,6 +1391,27 @@ virFileWrapperFdFree;
virFileWrapperFdNew;
+# virbitmap.h
+virGBitmapClearAll;
+virGBitmapClearBit;
+virGBitmapCopy;
+virGBitmapCountBits;
+virGBitmapFormat;
+virGBitmapFree;
+virGBitmapGetBit;
+virGBitmapIsAllSet;
+virGBitmapNew;
+virGBitmapNewData;
+virGBitmapNextClearBit;
+virGBitmapNextSetBit;
+virGBitmapParse;
+virGBitmapSetAll;
+virGBitmapSetBit;
+virGBitmapSize;
+virGBitmapString;
+virGBitmapToData;
+
+
# virinitctl.h
virInitctlSetRunLevel;
12:05 p.m.
On Mon, Feb 04, 2013 at 12:01:16PM -0500, Stefan Berger wrote:
Add a growable bitmap implementation building on top of the
'regular'
bitmap implementation. (no doubt, this could also be done differently...)
Indeed, I don't think this approach is desirable. Either add a
'bool growable' parameter to virBitmapNew(), or define a new
constructor virBitmapNewGrowable() and implement it directly
in the existing codebase.
Daniel
--
|: http://berrange.com -o- http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org -o- http://virt-manager.org :|
|: http://autobuild.org -o- http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org -o- http://live.gnome.org/gtk-vnc :|
12:24 p.m.
On 02/04/2013 10:01 AM, Stefan Berger wrote:
Add a growable bitmap implementation building on top of the
'regular'
bitmap implementation. (no doubt, this could also be done differently...)
This patch also adds a test virgbitmaptest.c that is largely a copy of
virbitmaptest.c with some minor modifications to test for growth of the
bitmap.
Signed-off-by: Stefan Berger <stefanb(a)linux.vnet.ibm.com>
---
PS: This patch builds on top of a patch with a virBitmapNextClearBit
implementation.
In addition to Dan's comments...
virBitmapNextClearBit makes sense to add in isolation (our code should
provide symmetric handling of a bitmap; and the fact that we can iterate
over set bits but not clear bits is a wart worth fixing). However, in
the context of fd passing, I'm not so sure we need a bitmap at all,
growable or otherwise. It should be sufficient just to have a per-vm
single integer set to the highest fdset number allocated so far; any
time a new fdset is needed, we increment the per-vm integer (even if
that leaves gaps in lower-valued fdsets), and on libvirtd reload, the
post-processing pass would merely set the integer to one more than the
maximum fdset seen among all the devices. Thus, I'm a bit worried that
this code is a tangent that will end up not being needed in the fdset case.
--
Eric Blake eblake redhat com +1-919-301-3266
Libvirt virtualization library http://libvirt.org
4309
days inactive
4309
days old
2 comments
3 participants
participants (3)
-
Daniel P. Berrange -
Eric Blake -
Stefan Berger