[libvirt] [PATCH 0/3] Decrease execution complexity of formating iothread scheduler info
While refactoring the old way to store iothread scheduler info I've added an algorithm that isn't entirely optimal but allows to store the scheduler info in a sane way. Unfortunately when you specify an insane number of iothreads the code takes ages to execute. To avoid this series being completely useless except for the one corner case I've opted to finally add support for self expanding bitmaps, which might become useful in the future. The self-expanding bitmap is then used instead of one of the loops that was necessary to determine the maximum iothread ID. Peter Krempa (3): util: bitmap: Intoduce self-expanding bitmap APIs conf: decrease iterations complexity when formatting iothreads conf: Remove now unused virDomainIOThreadIDMap src/conf/domain_conf.c | 51 ++++++++++---------------- src/conf/domain_conf.h | 3 -- src/libvirt_private.syms | 4 ++- src/util/virbitmap.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++ src/util/virbitmap.h | 8 +++++ tests/virbitmaptest.c | 51 ++++++++++++++++++++++++++ 6 files changed, 173 insertions(+), 37 deletions(-) -- 2.7.3
In some cases it's impractical to use the regular APIs as the bitmap size needs to be pre-declared. These new APIs allow to use bitmaps that self expand. The new code adds a property to the bitmap to track the alocation of memory so that VIR_RESIZE_N can be used. --- src/libvirt_private.syms | 3 ++ src/util/virbitmap.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++ src/util/virbitmap.h | 8 +++++ tests/virbitmaptest.c | 51 ++++++++++++++++++++++++++ 4 files changed, 155 insertions(+) diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms index af133c5..311858f 100644 --- a/src/libvirt_private.syms +++ b/src/libvirt_private.syms @@ -1134,6 +1134,7 @@ virAuthConfigNewData; # util/virbitmap.h virBitmapClearAll; virBitmapClearBit; +virBitmapClearBitExpand; virBitmapCopy; virBitmapCountBits; virBitmapDataToString; @@ -1148,6 +1149,7 @@ virBitmapLastSetBit; virBitmapNew; virBitmapNewCopy; virBitmapNewData; +virBitmapNewEmpty; virBitmapNewQuiet; virBitmapNextClearBit; virBitmapNextSetBit; @@ -1155,6 +1157,7 @@ virBitmapOverlaps; virBitmapParse; virBitmapSetAll; virBitmapSetBit; +virBitmapSetBitExpand; virBitmapSize; virBitmapString; virBitmapSubtract; diff --git a/src/util/virbitmap.c b/src/util/virbitmap.c index f116607..cce91f2 100644 --- a/src/util/virbitmap.c +++ b/src/util/virbitmap.c @@ -43,6 +43,7 @@ struct _virBitmap { size_t max_bit; size_t map_len; + size_t map_alloc; unsigned long *map; }; @@ -83,6 +84,7 @@ virBitmapNewQuiet(size_t size) bitmap->max_bit = size; bitmap->map_len = sz; + bitmap->map_alloc = sz; return bitmap; } @@ -109,6 +111,25 @@ virBitmapNew(size_t size) /** + * virBitmapNewEmpty + * + * Allocate an empty bitmap. It can be used with self-expanding APIs. + * + * Returns a pointer to the allocated bitmap or NULL if memory cannot be + * allocated. Reports libvirt errors. + */ +virBitmapPtr +virBitmapNewEmpty(void) +{ + virBitmapPtr ret; + + ignore_value(VIR_ALLOC(ret)); + + return ret; +} + + +/** * virBitmapFree: * @bitmap: previously allocated bitmap * @@ -155,6 +176,54 @@ int virBitmapSetBit(virBitmapPtr bitmap, size_t b) } /** + * virBitmapExpand: + * @map: Pointer to bitmap + * @b: bit position to include in bitmap + * + * Resizes the bitmap so that bit @b will fit into it. This shall be called only + * if @b would not fit into the map. + * + * Returns 0 on success, -1 on error. + */ +static int virBitmapExpand(virBitmapPtr map, size_t b) +{ + size_t new_len = VIR_DIV_UP(b, VIR_BITMAP_BITS_PER_UNIT); + + /* resize the memory if necessary */ + if (map->map_len < new_len) { + if (VIR_RESIZE_N(map->map, map->map_alloc, map->map_len, + new_len - map->map_len) < 0) + return -1; + } + + map->max_bit = b + 1; + map->map_len = new_len; + + return 0; +} + + +/** + * virBitmapSetBitExpand: + * @bitmap: Pointer to bitmap + * @b: bit position to set + * + * Set bit position @b in @bitmap. Expands the bitmap as necessary so that @b is + * included in the map. + * + * Returns 0 on if bit is successfully set, -1 on error. + */ +int virBitmapSetBitExpand(virBitmapPtr bitmap, size_t b) +{ + if (bitmap->max_bit <= b && virBitmapExpand(bitmap, b) < 0) + return -1; + + bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] |= VIR_BITMAP_BIT(b); + return 0; +} + + +/** * virBitmapClearBit: * @bitmap: Pointer to bitmap * @b: bit position to clear @@ -172,6 +241,30 @@ int virBitmapClearBit(virBitmapPtr bitmap, size_t b) return 0; } + +/** + * virBitmapClearBitExpand: + * @bitmap: Pointer to bitmap + * @b: bit position to set + * + * Clear bit position @b in @bitmap. Expands the bitmap as necessary so that + * @b is included in the map. + * + * Returns 0 on if bit is successfully cleared, -1 on error. + */ +int virBitmapClearBitExpand(virBitmapPtr bitmap, size_t b) +{ + if (bitmap->max_bit <= b) { + if (virBitmapExpand(bitmap, b) < 0) + return -1; + } else { + bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] &= ~VIR_BITMAP_BIT(b); + } + + return 0; +} + + /* Helper function. caller must ensure b < bitmap->max_bit */ static bool virBitmapIsSet(virBitmapPtr bitmap, size_t b) { diff --git a/src/util/virbitmap.h b/src/util/virbitmap.h index 846aca3..79f53dd 100644 --- a/src/util/virbitmap.h +++ b/src/util/virbitmap.h @@ -37,6 +37,7 @@ typedef virBitmap *virBitmapPtr; */ virBitmapPtr virBitmapNewQuiet(size_t size) ATTRIBUTE_RETURN_CHECK; virBitmapPtr virBitmapNew(size_t size) ATTRIBUTE_RETURN_CHECK; +virBitmapPtr virBitmapNewEmpty(void) ATTRIBUTE_RETURN_CHECK; /* * Free previously allocated bitmap @@ -55,12 +56,19 @@ int virBitmapCopy(virBitmapPtr dst, virBitmapPtr src); int virBitmapSetBit(virBitmapPtr bitmap, size_t b) ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK; +int virBitmapSetBitExpand(virBitmapPtr bitmap, size_t b) + ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK; + + /* * Clear bit position @b in @bitmap */ int virBitmapClearBit(virBitmapPtr bitmap, size_t b) ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK; +int virBitmapClearBitExpand(virBitmapPtr bitmap, size_t b) + ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK; + /* * Get bit @b in @bitmap. Returns false if b is out of range. */ diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c index 967a5c8..92f1e6e 100644 --- a/tests/virbitmaptest.c +++ b/tests/virbitmaptest.c @@ -590,6 +590,54 @@ test11(const void *opaque) return ret; } +#define TEST_MAP(sz, expect) \ + do { \ + char *actual = virBitmapFormat(map); \ + if (virBitmapSize(map) != sz) { \ + fprintf(stderr, "\n expected bitmap size: '%d' actual size: " \ + "'%zu'\n", sz, virBitmapSize(map)); \ + goto cleanup; \ + } \ + if (STRNEQ_NULLABLE(expect, actual)) { \ + fprintf(stderr, "\n expected bitmap contents '%s' actual contents "\ + "'%s'\n", NULLSTR(expect), NULLSTR(actual)); \ + VIR_FREE(actual); \ + goto cleanup; \ + } \ + VIR_FREE(actual); \ + } while (0) + +/* test self-expanding bitmap APIs */ +static int +test12(const void *opaque ATTRIBUTE_UNUSED) +{ + virBitmapPtr map = NULL; + int ret = -1; + + if (!(map = virBitmapNewEmpty())) + return -1; + + TEST_MAP(0, ""); + + if (virBitmapSetBitExpand(map, 100) < 0) + goto cleanup; + + TEST_MAP(101, "100"); + + if (virBitmapClearBitExpand(map, 150) < 0) + goto cleanup; + + TEST_MAP(151, "100"); + + ret = 0; + + cleanup: + virBitmapFree(map); + return ret; +} +#undef TEST_MAP + + #define TESTBINARYOP(A, B, RES, FUNC) \ testBinaryOpData.a = A; \ testBinaryOpData.b = B; \ @@ -633,6 +681,9 @@ mymain(void) TESTBINARYOP("0-3", "0,^0", "0-3", test11); TESTBINARYOP("0,2", "1,3", "0,2", test11); + if (virtTestRun("test12", test12, NULL) < 0) + ret = -1; + return ret; } -- 2.7.3
Doh - I was looking at these while I see Michal posted an ACK series... so hopefully before you push... $SUBJ Introduce On 03/22/2016 10:00 AM, Peter Krempa wrote:
In some cases it's impractical to use the regular APIs as the bitmap size needs to be pre-declared. These new APIs allow to use bitmaps that self expand.
The new code adds a property to the bitmap to track the alocation of
allocation
memory so that VIR_RESIZE_N can be used. --- src/libvirt_private.syms | 3 ++ src/util/virbitmap.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++ src/util/virbitmap.h | 8 +++++ tests/virbitmaptest.c | 51 ++++++++++++++++++++++++++ 4 files changed, 155 insertions(+)
[...]
diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c index 967a5c8..92f1e6e 100644 --- a/tests/virbitmaptest.c +++ b/tests/virbitmaptest.c @@ -590,6 +590,54 @@ test11(const void *opaque) return ret; }
+#define TEST_MAP(sz, expect) \ + do { \ + char *actual = virBitmapFormat(map); \ + if (virBitmapSize(map) != sz) { \ + fprintf(stderr, "\n expected bitmap size: '%d' actual size: " \ + "'%zu'\n", sz, virBitmapSize(map)); \
According to Coverity, actual can be leaked here...
+ goto cleanup; \ + } \ + if (STRNEQ_NULLABLE(expect, actual)) { \ + fprintf(stderr, "\n expected bitmap contents '%s' actual contents "\ + "'%s'\n", NULLSTR(expect), NULLSTR(actual)); \ + VIR_FREE(actual); \ + goto cleanup; \ + } \ + VIR_FREE(actual); \ + } while (0) + +/* test self-expanding bitmap APIs */ +static int +test12(const void *opaque ATTRIBUTE_UNUSED) +{ + virBitmapPtr map = NULL; + int ret = -1; + + if (!(map = virBitmapNewEmpty())) + return -1; + + TEST_MAP(0, ""); + + if (virBitmapSetBitExpand(map, 100) < 0) + goto cleanup; + + TEST_MAP(101, "100"); + + if (virBitmapClearBitExpand(map, 150) < 0) + goto cleanup; + + TEST_MAP(151, "100"); + + ret = 0; + + cleanup: + virBitmapFree(map); + return ret; +} +#undef TEST_MAP + +
John
On Tue, Mar 29, 2016 at 11:12:38 -0400, John Ferlan wrote:
Doh - I was looking at these while I see Michal posted an ACK series... so hopefully before you push...
I've fixed the things you've pointed out and pushed this. Thanks. Peter
Create a bitmap of iothreads that have scheduler info set so that the transformation algorithm does not have to iterate the empty bitmap many times. By reusing self-expanding bitmaps the bitmap size does not need to be pre-calculated. Resolves: https://bugzilla.redhat.com/show_bug.cgi?id=1264008 --- src/conf/domain_conf.c | 23 ++++++++++++++++++----- 1 file changed, 18 insertions(+), 5 deletions(-) diff --git a/src/conf/domain_conf.c b/src/conf/domain_conf.c index d5d9ff7..d7f0291 100644 --- a/src/conf/domain_conf.c +++ b/src/conf/domain_conf.c @@ -21808,19 +21808,32 @@ static int virDomainFormatIOThreadSchedDef(virDomainDefPtr def, virBufferPtr buf) { - virBitmapPtr allthreadmap; - int ret; + virBitmapPtr threadmap; + size_t i; + int ret = -1; if (def->niothreadids == 0) return 0; - if (!(allthreadmap = virDomainIOThreadIDMap(def))) + if (!(threadmap = virBitmapNewEmpty())) return -1; + for (i = 0; i < def->niothreadids; i++) { + if (def->iothreadids[i]->sched.policy != VIR_PROC_POLICY_NONE && + virBitmapSetBitExpand(threadmap, def->iothreadids[i]->iothread_id) < 0) + goto cleanup; + } + + if (virBitmapIsAllClear(threadmap)) { + ret = 0; + goto cleanup; + } + ret = virDomainFormatSchedDef(def, buf, "iothreads", - virDomainDefGetIOThreadSched, allthreadmap); + virDomainDefGetIOThreadSched, threadmap); - virBitmapFree(allthreadmap); + cleanup: + virBitmapFree(threadmap); return ret; } -- 2.7.3
--- src/conf/domain_conf.c | 28 ---------------------------- src/conf/domain_conf.h | 3 --- src/libvirt_private.syms | 1 - 3 files changed, 32 deletions(-) diff --git a/src/conf/domain_conf.c b/src/conf/domain_conf.c index d7f0291..d11ccfa 100644 --- a/src/conf/domain_conf.c +++ b/src/conf/domain_conf.c @@ -18522,34 +18522,6 @@ virDomainIOThreadIDAdd(virDomainDefPtr def, } -/* - * virDomainIOThreadIDMap: - * @def: domain definition - * - * Returns a map of active iothreads for @def. - */ -virBitmapPtr -virDomainIOThreadIDMap(virDomainDefPtr def) -{ - unsigned int max = 0; - size_t i; - virBitmapPtr ret = NULL; - - for (i = 0; i < def->niothreadids; i++) { - if (def->iothreadids[i]->iothread_id > max) - max = def->iothreadids[i]->iothread_id; - } - - if (!(ret = virBitmapNew(max))) - return NULL; - - for (i = 0; i < def->niothreadids; i++) - ignore_value(virBitmapSetBit(ret, def->iothreadids[i]->iothread_id)); - - return ret; -} - - void virDomainIOThreadIDDel(virDomainDefPtr def, unsigned int iothread_id) diff --git a/src/conf/domain_conf.h b/src/conf/domain_conf.h index 83bdd67..8fa6533 100644 --- a/src/conf/domain_conf.h +++ b/src/conf/domain_conf.h @@ -2709,9 +2709,6 @@ virDomainIOThreadIDDefPtr virDomainIOThreadIDFind(const virDomainDef *def, unsigned int iothread_id); virDomainIOThreadIDDefPtr virDomainIOThreadIDAdd(virDomainDefPtr def, unsigned int iothread_id); - -virBitmapPtr virDomainIOThreadIDMap(virDomainDefPtr def) - ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK; void virDomainIOThreadIDDel(virDomainDefPtr def, unsigned int iothread_id); unsigned int virDomainDefFormatConvertXMLFlags(unsigned int flags); diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms index 311858f..ede9b59 100644 --- a/src/libvirt_private.syms +++ b/src/libvirt_private.syms @@ -344,7 +344,6 @@ virDomainIOThreadIDAdd; virDomainIOThreadIDDefFree; virDomainIOThreadIDDel; virDomainIOThreadIDFind; -virDomainIOThreadIDMap; virDomainKeyWrapCipherNameTypeFromString; virDomainKeyWrapCipherNameTypeToString; virDomainLeaseDefFree; -- 2.7.3
On 22.03.2016 15:00, Peter Krempa wrote:
While refactoring the old way to store iothread scheduler info I've added an algorithm that isn't entirely optimal but allows to store the scheduler info in a sane way. Unfortunately when you specify an insane number of iothreads the code takes ages to execute.
To avoid this series being completely useless except for the one corner case I've opted to finally add support for self expanding bitmaps, which might become useful in the future. The self-expanding bitmap is then used instead of one of the loops that was necessary to determine the maximum iothread ID.
Peter Krempa (3): util: bitmap: Intoduce self-expanding bitmap APIs conf: decrease iterations complexity when formatting iothreads conf: Remove now unused virDomainIOThreadIDMap
src/conf/domain_conf.c | 51 ++++++++++---------------- src/conf/domain_conf.h | 3 -- src/libvirt_private.syms | 4 ++- src/util/virbitmap.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++ src/util/virbitmap.h | 8 +++++ tests/virbitmaptest.c | 51 ++++++++++++++++++++++++++ 6 files changed, 173 insertions(+), 37 deletions(-)
ACK series. Michal
participants (3)
-
John Ferlan -
Michal Privoznik -
Peter Krempa