[libvirt] [RFC: PATCH 0/4] Update array allocation macros
I'm posing this series as an RFC for the moment. The basic premise is that I got bit trying to use VIR_REALLOC_N when working on the virCommand API, assuming that it zeroed out new memory because the documentation said so, only to hit a core dump. On looking closer, it became obvious to me that the VIR_REALLOC_N API is deficient - there's no way to know how much memory, if any, to zeroize without knowing the original size, so the new memory has to be uninitialized (explaining my crash), and the documentation is wrong. So, after some IRC discussions, two ideas emerged in addition to the obvious documentation update. One is the simpler VIR_EXPAND_N, where the array size always matches the array allocation, along with a VIR_SHRINK_N counterpart which can trim an array back down (and failure to trim need not be fatal). But this can scale quadratically if you end up with a large array, as the existing contents must be copied on every realloc. See patches 1 and 2 for an implementation and use. The other idea is VIR_RESIZE_N, which tracks allocation separately from usage, and has better scaling by doing geometric growth only when needed rather than on every array usage increase. But it takes more parameters (making it slightly harder to remember how to use correctly), along with possible modifications of the struct tracking an array (so it might not be possible to modify all uses of VIR_REALLOC_N to use this, if it would end up altering a public struct layout). See patches 3 and 4 for an implementation and use. Note that event.c is an example of code that already tracked allocation separately from usage, so the new VIR_RESIZE_N was very easy to use. On the other hand, libvirtd.c is an example of code where I had to add allocation tracking; notice the difference between patches 2/4 and 4/4 of the logic differences needed when using VIR_EXPAND_N vs. VIR_RESIZE_N. And notice that both patch 2 and patch 4 provide a net reduction in lines outside of memory.[ch]. Either way, I'm willing to audit all remaining uses of VIR_REALLOC_N (in fact, libvirtd.c has another use of VIR_REALLOC_N to allocate a buffer for getgrnam_r, where the uninitialized memory aspect was just fine and not worth converting). The only reason I'm posting this series as an RFC is to get a feel for which of the two styles I should prefer when doing my audit on the rest of the code base (rather than doing style A now only to find that style B would be preferred). Also, as written, the implementation forces all array count variables to be size_t if using VIR_EXPAND_N or VIR_RESIZE_N; I may come across a public API where I can't change the array count type, in which case I will have to rewrite the macros to be type-agnostic. Well, more like making the macro choose between a 4-byte or 8-byte implementation, based on sizeof(count), and adding a compiler verify() that count must be one of those two sizes, whether on 32-bit or 64-bit machines. Eric Blake (4): memory: make it safer to expand arrays daemon: use safer memory growth macros memory: make it easier to avoid quadratic scaling of arrays daemon: use more efficient memory growth macros daemon/event.c | 44 ++++++++++------------- daemon/libvirtd.c | 8 ++--- daemon/libvirtd.h | 11 +++--- docs/hacking.html.in | 61 ++++++++++++++++++++++++++------ src/util/memory.c | 94 +++++++++++++++++++++++++++++++++++++++++++++++++- src/util/memory.h | 77 +++++++++++++++++++++++++++++++++++++--- 6 files changed, 242 insertions(+), 53 deletions(-) -- 1.7.2.1
Note - I did _not_ update HACKING. Do we have a makefile rule for doing an auto-xsl translation from hacking.html.in yet, or is something I'll have to do manually before pushing this? * src/util/memory.h (VIR_REALLOC_N): Update docs. (VIR_EXPAND_N, VIR_SHRINK_N): New macros. (virAlloc, virAllocN, virReallocN, virAllocVar, virFree): Add some gcc attributes. * src/util/memory.c (virExpandN, virShrinkN): New functions. (virReallocN): Update docs. * docs/hacking.html.in: Prefer newer interfaces over VIR_REALLOC_N, since uninitialized memory can bite us. --- docs/hacking.html.in | 24 +++++++++++-------- src/util/memory.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++- src/util/memory.h | 51 ++++++++++++++++++++++++++++++++++++++----- 3 files changed, 117 insertions(+), 17 deletions(-) diff --git a/docs/hacking.html.in b/docs/hacking.html.in index deab530..4cc92f4 100644 --- a/docs/hacking.html.in +++ b/docs/hacking.html.in @@ -332,11 +332,11 @@ Use of the malloc/free/realloc/calloc APIs is deprecated in the libvirt codebase, because they encourage a number of serious coding bugs and do not enable compile time verification of checks for NULL. Instead of these - routines, use the macros from memory.h + routines, use the macros from memory.h. </p> <ul> - <li><p>eg to allocate a single object:</p> + <li><p>To allocate a single object:</p> <pre> virDomainPtr domain; @@ -347,11 +347,11 @@ } </pre></li> - <li><p>eg to allocate an array of objects</p> + <li><p>To allocate an array of objects</p> <pre> virDomainPtr domains; - int ndomains = 10; + size_t ndomains = 10; if (VIR_ALLOC_N(domains, ndomains) < 0) { virReportOOMError(); @@ -359,7 +359,7 @@ } </pre></li> - <li><p>eg to allocate an array of object pointers</p> + <li><p>To allocate an array of object pointers</p> <pre> virDomainPtr *domains; @@ -371,18 +371,22 @@ } </pre></li> - <li><p>eg to re-allocate the array of domains to be longer</p> + <li><p>To re-allocate the array of domains to be 10 elements longer</p> <pre> - ndomains = 20 - - if (VIR_REALLOC_N(domains, ndomains) < 0) { + if (VIR_EXPAND_N(domains, ndomains, 10) < 0) { virReportOOMError(); return NULL; } </pre></li> - <li><p>eg to free the domain</p> + <li><p>To trim an array of domains to have one less element</p> + +<pre> + VIR_SHRINK_N(domains, ndomains, 1); +</pre></li> + + <li><p>To free the domain</p> <pre> VIR_FREE(domain); diff --git a/src/util/memory.c b/src/util/memory.c index dd1216b..e95aa47 100644 --- a/src/util/memory.c +++ b/src/util/memory.c @@ -1,6 +1,7 @@ /* * memory.c: safer memory allocation * + * Copyright (C) 2010 Red Hat, Inc. * Copyright (C) 2008 Daniel P. Berrange * * This library is free software; you can redistribute it and/or @@ -24,6 +25,7 @@ #include <stddef.h> #include "memory.h" +#include "ignore-value.h" #if TEST_OOM @@ -141,7 +143,7 @@ int virAllocN(void *ptrptr, size_t size, size_t count) * 'count' elements, each 'size' bytes in length. Update 'ptrptr' * with the address of the newly allocated memory. On failure, * 'ptrptr' is not changed and still points to the original memory - * block. The newly allocated memory is filled with zeros. + * block. Any newly allocated memory in 'ptrptr' is uninitialized. * * Returns -1 on failure to allocate, zero on success */ @@ -165,6 +167,61 @@ int virReallocN(void *ptrptr, size_t size, size_t count) } /** + * virExpandN: + * @ptrptr: pointer to pointer for address of allocated memory + * @size: number of bytes per element + * @countptr: pointer to number of elements in array + * @add: number of elements to add + * + * Resize the block of memory in 'ptrptr' to be an array of + * '*countptr' + 'add' elements, each 'size' bytes in length. + * Update 'ptrptr' and 'countptr' with the details of the newly + * allocated memory. On failure, 'ptrptr' and 'countptr' are not + * changed. Any newly allocated memory in 'ptrptr' is zero-filled. + * + * Returns -1 on failure to allocate, zero on success + */ +int virExpandN(void *ptrptr, size_t size, size_t *countptr, size_t add) +{ + int res; + + if (*countptr + add < *countptr) { + errno = ENOMEM; + return -1; + } + res = virReallocN(ptrptr, size, *countptr + add); + if (res == 0) { + memset(*(char **)ptrptr + (size * *countptr), 0, size * add); + *countptr += add; + } + return res; +} + +/** + * virShrinkN: + * @ptrptr: pointer to pointer for address of allocated memory + * @size: number of bytes per element + * @countptr: pointer to number of elements in array + * @remove: number of elements to remove + * + * Resize the block of memory in 'ptrptr' to be an array of + * '*countptr' - 'remove' elements, each 'size' bytes in length. + * Update 'ptrptr' and 'countptr' with the details of the newly + * allocated memory. If 'remove' is larger than 'countptr', free + * the entire array. + */ +void virShrinkN(void *ptrptr, size_t size, size_t *countptr, size_t remove) +{ + if (remove < *countptr) + ignore_value(virReallocN(ptrptr, size, *countptr -= remove)); + else { + virFree(ptrptr); + *countptr = 0; + } +} + + +/** * Vir_Alloc_Var: * @ptrptr: pointer to hold address of allocated memory * @struct_size: size of initial struct diff --git a/src/util/memory.h b/src/util/memory.h index 60e2be6..98ac2b3 100644 --- a/src/util/memory.h +++ b/src/util/memory.h @@ -46,14 +46,21 @@ /* Don't call these directly - use the macros below */ -int virAlloc(void *ptrptr, size_t size) ATTRIBUTE_RETURN_CHECK; -int virAllocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK; -int virReallocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK; +int virAlloc(void *ptrptr, size_t size) ATTRIBUTE_RETURN_CHECK + ATTRIBUTE_NONNULL(1); +int virAllocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK + ATTRIBUTE_NONNULL(1); +int virReallocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK + ATTRIBUTE_NONNULL(1); +int virExpandN(void *ptrptr, size_t size, size_t *count, size_t add) + ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3); +void virShrinkN(void *ptrptr, size_t size, size_t *count, size_t remove) + ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3); int virAllocVar(void *ptrptr, size_t struct_size, size_t element_size, - size_t count) ATTRIBUTE_RETURN_CHECK; -void virFree(void *ptrptr); + size_t count) ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1); +void virFree(void *ptrptr) ATTRIBUTE_NONNULL(1); /** * VIR_ALLOC: @@ -87,12 +94,44 @@ void virFree(void *ptrptr); * * Re-allocate an array of 'count' elements, each sizeof(*ptr) * bytes long and store the address of allocated memory in - * 'ptr'. Fill the newly allocated memory with zeros + * 'ptr'. If 'ptr' grew, the added memory is uninitialized. * * Returns -1 on failure, 0 on success */ # define VIR_REALLOC_N(ptr, count) virReallocN(&(ptr), sizeof(*(ptr)), (count)) +/** + * VIR_EXPAND_N: + * @ptr: pointer to hold address of allocated memory + * @count: variable tracking number of elements currently allocated + * @add: number of elements to add + * + * Re-allocate an array of 'count' elements, each sizeof(*ptr) + * bytes long, to be 'count' + 'add' elements long, then store the + * address of allocated memory in 'ptr' and the new size in 'count'. + * The new elements are filled with zero. + * + * Returns -1 on failure, 0 on success + */ +# define VIR_EXPAND_N(ptr, count, add) \ + virExpandN(&(ptr), sizeof(*(ptr)), &(count), add) + +/** + * VIR_SHRINK_N: + * @ptr: pointer to hold address of allocated memory + * @count: variable tracking number of elements currently allocated + * @remove: number of elements to remove + * + * Re-allocate an array of 'count' elements, each sizeof(*ptr) + * bytes long, to be 'count' - 'remove' elements long, then store the + * address of allocated memory in 'ptr' and the new size in 'count'. + * If 'count' <= 'remove', the entire array is freed. + * + * No return value. + */ +# define VIR_SHRINK_N(ptr, count, remove) \ + virShrinkN(&(ptr), sizeof(*(ptr)), &(count), remove) + /* * VIR_ALLOC_VAR_OVERSIZED: * @M: size of base structure -- 1.7.2.1
On Sat, Aug 14, 2010 at 10:23:53AM -0600, Eric Blake wrote:
Note - I did _not_ update HACKING. Do we have a makefile rule for doing an auto-xsl translation from hacking.html.in yet, or is something I'll have to do manually before pushing this?
* src/util/memory.h (VIR_REALLOC_N): Update docs. (VIR_EXPAND_N, VIR_SHRINK_N): New macros. (virAlloc, virAllocN, virReallocN, virAllocVar, virFree): Add some gcc attributes. * src/util/memory.c (virExpandN, virShrinkN): New functions. (virReallocN): Update docs. * docs/hacking.html.in: Prefer newer interfaces over VIR_REALLOC_N, since uninitialized memory can bite us. --- docs/hacking.html.in | 24 +++++++++++-------- src/util/memory.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++- src/util/memory.h | 51 ++++++++++++++++++++++++++++++++++++++----- 3 files changed, 117 insertions(+), 17 deletions(-)
diff --git a/docs/hacking.html.in b/docs/hacking.html.in index deab530..4cc92f4 100644 --- a/docs/hacking.html.in +++ b/docs/hacking.html.in @@ -332,11 +332,11 @@ Use of the malloc/free/realloc/calloc APIs is deprecated in the libvirt codebase, because they encourage a number of serious coding bugs and do not enable compile time verification of checks for NULL. Instead of these - routines, use the macros from memory.h + routines, use the macros from memory.h. </p>
<ul> - <li><p>eg to allocate a single object:</p> + <li><p>To allocate a single object:</p>
<pre> virDomainPtr domain; @@ -347,11 +347,11 @@ } </pre></li>
- <li><p>eg to allocate an array of objects</p> + <li><p>To allocate an array of objects</p>
<pre> virDomainPtr domains; - int ndomains = 10; + size_t ndomains = 10;
if (VIR_ALLOC_N(domains, ndomains) < 0) { virReportOOMError(); @@ -359,7 +359,7 @@ } </pre></li>
- <li><p>eg to allocate an array of object pointers</p> + <li><p>To allocate an array of object pointers</p>
<pre> virDomainPtr *domains; @@ -371,18 +371,22 @@ } </pre></li>
- <li><p>eg to re-allocate the array of domains to be longer</p> + <li><p>To re-allocate the array of domains to be 10 elements longer</p>
<pre> - ndomains = 20 - - if (VIR_REALLOC_N(domains, ndomains) < 0) { + if (VIR_EXPAND_N(domains, ndomains, 10) < 0) { virReportOOMError(); return NULL; } </pre></li>
- <li><p>eg to free the domain</p> + <li><p>To trim an array of domains to have one less element</p> + +<pre> + VIR_SHRINK_N(domains, ndomains, 1); +</pre></li> + + <li><p>To free the domain</p>
<pre> VIR_FREE(domain); diff --git a/src/util/memory.c b/src/util/memory.c index dd1216b..e95aa47 100644 --- a/src/util/memory.c +++ b/src/util/memory.c @@ -1,6 +1,7 @@ /* * memory.c: safer memory allocation * + * Copyright (C) 2010 Red Hat, Inc. * Copyright (C) 2008 Daniel P. Berrange * * This library is free software; you can redistribute it and/or @@ -24,6 +25,7 @@ #include <stddef.h>
#include "memory.h" +#include "ignore-value.h"
#if TEST_OOM @@ -141,7 +143,7 @@ int virAllocN(void *ptrptr, size_t size, size_t count) * 'count' elements, each 'size' bytes in length. Update 'ptrptr' * with the address of the newly allocated memory. On failure, * 'ptrptr' is not changed and still points to the original memory - * block. The newly allocated memory is filled with zeros. + * block. Any newly allocated memory in 'ptrptr' is uninitialized. * * Returns -1 on failure to allocate, zero on success */ @@ -165,6 +167,61 @@ int virReallocN(void *ptrptr, size_t size, size_t count) }
/** + * virExpandN: + * @ptrptr: pointer to pointer for address of allocated memory + * @size: number of bytes per element + * @countptr: pointer to number of elements in array + * @add: number of elements to add + * + * Resize the block of memory in 'ptrptr' to be an array of + * '*countptr' + 'add' elements, each 'size' bytes in length. + * Update 'ptrptr' and 'countptr' with the details of the newly + * allocated memory. On failure, 'ptrptr' and 'countptr' are not + * changed. Any newly allocated memory in 'ptrptr' is zero-filled. + * + * Returns -1 on failure to allocate, zero on success + */ +int virExpandN(void *ptrptr, size_t size, size_t *countptr, size_t add) +{ + int res; + + if (*countptr + add < *countptr) { + errno = ENOMEM; + return -1; + } + res = virReallocN(ptrptr, size, *countptr + add); + if (res == 0) { + memset(*(char **)ptrptr + (size * *countptr), 0, size * add); + *countptr += add; + } + return res; +} + +/** + * virShrinkN: + * @ptrptr: pointer to pointer for address of allocated memory + * @size: number of bytes per element + * @countptr: pointer to number of elements in array + * @remove: number of elements to remove + * + * Resize the block of memory in 'ptrptr' to be an array of + * '*countptr' - 'remove' elements, each 'size' bytes in length. + * Update 'ptrptr' and 'countptr' with the details of the newly + * allocated memory. If 'remove' is larger than 'countptr', free + * the entire array. + */ +void virShrinkN(void *ptrptr, size_t size, size_t *countptr, size_t remove) +{ + if (remove < *countptr) + ignore_value(virReallocN(ptrptr, size, *countptr -= remove)); + else { + virFree(ptrptr); + *countptr = 0; + } +} + + +/** * Vir_Alloc_Var: * @ptrptr: pointer to hold address of allocated memory * @struct_size: size of initial struct diff --git a/src/util/memory.h b/src/util/memory.h index 60e2be6..98ac2b3 100644 --- a/src/util/memory.h +++ b/src/util/memory.h @@ -46,14 +46,21 @@
/* Don't call these directly - use the macros below */ -int virAlloc(void *ptrptr, size_t size) ATTRIBUTE_RETURN_CHECK; -int virAllocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK; -int virReallocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK; +int virAlloc(void *ptrptr, size_t size) ATTRIBUTE_RETURN_CHECK + ATTRIBUTE_NONNULL(1); +int virAllocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK + ATTRIBUTE_NONNULL(1); +int virReallocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK + ATTRIBUTE_NONNULL(1); +int virExpandN(void *ptrptr, size_t size, size_t *count, size_t add) + ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3); +void virShrinkN(void *ptrptr, size_t size, size_t *count, size_t remove) + ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3); int virAllocVar(void *ptrptr, size_t struct_size, size_t element_size, - size_t count) ATTRIBUTE_RETURN_CHECK; -void virFree(void *ptrptr); + size_t count) ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1); +void virFree(void *ptrptr) ATTRIBUTE_NONNULL(1);
/** * VIR_ALLOC: @@ -87,12 +94,44 @@ void virFree(void *ptrptr); * * Re-allocate an array of 'count' elements, each sizeof(*ptr) * bytes long and store the address of allocated memory in - * 'ptr'. Fill the newly allocated memory with zeros + * 'ptr'. If 'ptr' grew, the added memory is uninitialized. * * Returns -1 on failure, 0 on success */ # define VIR_REALLOC_N(ptr, count) virReallocN(&(ptr), sizeof(*(ptr)), (count))
+/** + * VIR_EXPAND_N: + * @ptr: pointer to hold address of allocated memory + * @count: variable tracking number of elements currently allocated + * @add: number of elements to add + * + * Re-allocate an array of 'count' elements, each sizeof(*ptr) + * bytes long, to be 'count' + 'add' elements long, then store the + * address of allocated memory in 'ptr' and the new size in 'count'. + * The new elements are filled with zero. + * + * Returns -1 on failure, 0 on success + */ +# define VIR_EXPAND_N(ptr, count, add) \ + virExpandN(&(ptr), sizeof(*(ptr)), &(count), add) + +/** + * VIR_SHRINK_N: + * @ptr: pointer to hold address of allocated memory + * @count: variable tracking number of elements currently allocated + * @remove: number of elements to remove + * + * Re-allocate an array of 'count' elements, each sizeof(*ptr) + * bytes long, to be 'count' - 'remove' elements long, then store the + * address of allocated memory in 'ptr' and the new size in 'count'. + * If 'count' <= 'remove', the entire array is freed. + * + * No return value. + */ +# define VIR_SHRINK_N(ptr, count, remove) \ + virShrinkN(&(ptr), sizeof(*(ptr)), &(count), remove) + /* * VIR_ALLOC_VAR_OVERSIZED: * @M: size of base structure
ACK, I've wanted to add this for a long time now Daniel -- |: Red Hat, Engineering, London -o- http://people.redhat.com/berrange/ :| |: http://libvirt.org -o- http://virt-manager.org -o- http://deltacloud.org :| |: http://autobuild.org -o- http://search.cpan.org/~danberr/ :| |: GnuPG: 7D3B9505 -o- F3C9 553F A1DA 4AC2 5648 23C1 B3DF F742 7D3B 9505 :|
On 08/16/2010 10:20 AM, Daniel P. Berrange wrote:
On Sat, Aug 14, 2010 at 10:23:53AM -0600, Eric Blake wrote:
Note - I did _not_ update HACKING. Do we have a makefile rule for doing an auto-xsl translation from hacking.html.in yet, or is something I'll have to do manually before pushing this?
Any thoughts on this question?
ACK, I've wanted to add this for a long time now
Good, I suspected that this patch was uncontroversial; it was more the rest of the series (and the remaining auditing work to go through more than 100 more VIR_REALLOC_N usages) that I posed this as an RFC; so I will hold of pushing this patch until the reworked series is complete. -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
* daemon/libvirtd.h (qemud_server): Change types of members tracking array sizes. * daemon/event.c (virEventLoop): Likewise. (virEventAddHandleImpl, virEventAddTimeoutImpl) (virEventCleanupTimeouts, virEventCleanupHandles): Use VIR_EXPAND_N and VIR_SHRINK_N instead of VIR_REALLOC_N. Tweak debug messages to match type changes. * daemon/libvirtd.c (qemudDispatchServer, qemudRunLoop): Use VIR_EXPAND_N and VIR_SHRINK_N. Signed-off-by: Eric Blake <eblake@redhat.com> --- daemon/event.c | 44 +++++++++++++++++++------------------------- daemon/libvirtd.c | 10 ++++------ daemon/libvirtd.h | 10 +++++----- 3 files changed, 28 insertions(+), 36 deletions(-) diff --git a/daemon/event.c b/daemon/event.c index 6971409..77498e8 100644 --- a/daemon/event.c +++ b/daemon/event.c @@ -73,11 +73,11 @@ struct virEventLoop { int running; pthread_t leader; int wakeupfd[2]; - int handlesCount; - int handlesAlloc; + size_t handlesCount; + size_t handlesAlloc; struct virEventHandle *handles; - int timeoutsCount; - int timeoutsAlloc; + size_t timeoutsCount; + size_t timeoutsAlloc; struct virEventTimeout *timeouts; }; @@ -113,14 +113,13 @@ int virEventAddHandleImpl(int fd, int events, EVENT_DEBUG("Add handle fd=%d events=%d cb=%p opaque=%p", fd, events, cb, opaque); virEventLock(); if (eventLoop.handlesCount == eventLoop.handlesAlloc) { - EVENT_DEBUG("Used %d handle slots, adding %d more", + EVENT_DEBUG("Used %zu handle slots, adding %d more", eventLoop.handlesAlloc, EVENT_ALLOC_EXTENT); - if (VIR_REALLOC_N(eventLoop.handles, - (eventLoop.handlesAlloc + EVENT_ALLOC_EXTENT)) < 0) { + if (VIR_EXPAND_N(eventLoop.handles, eventLoop.handlesAlloc, + EVENT_ALLOC_EXTENT) < 0) { virEventUnlock(); return -1; } - eventLoop.handlesAlloc += EVENT_ALLOC_EXTENT; } watch = nextWatch++; @@ -214,14 +213,13 @@ int virEventAddTimeoutImpl(int frequency, virEventLock(); if (eventLoop.timeoutsCount == eventLoop.timeoutsAlloc) { - EVENT_DEBUG("Used %d timeout slots, adding %d more", + EVENT_DEBUG("Used %zu timeout slots, adding %d more", eventLoop.timeoutsAlloc, EVENT_ALLOC_EXTENT); - if (VIR_REALLOC_N(eventLoop.timeouts, - (eventLoop.timeoutsAlloc + EVENT_ALLOC_EXTENT)) < 0) { + if (VIR_EXPAND_N(eventLoop.timeouts, eventLoop.timeoutsAlloc, + EVENT_ALLOC_EXTENT) < 0) { virEventUnlock(); return -1; } - eventLoop.timeoutsAlloc += EVENT_ALLOC_EXTENT; } eventLoop.timeouts[eventLoop.timeoutsCount].timer = nextTimer++; @@ -311,7 +309,7 @@ int virEventRemoveTimeoutImpl(int timer) { static int virEventCalculateTimeout(int *timeout) { unsigned long long then = 0; int i; - EVENT_DEBUG("Calculate expiry of %d timers", eventLoop.timeoutsCount); + EVENT_DEBUG("Calculate expiry of %zu timers", eventLoop.timeoutsCount); /* Figure out if we need a timeout */ for (i = 0 ; i < eventLoop.timeoutsCount ; i++) { if (eventLoop.timeouts[i].frequency < 0) @@ -492,7 +490,7 @@ static int virEventDispatchHandles(int nfds, struct pollfd *fds) { */ static int virEventCleanupTimeouts(void) { int i; - DEBUG("Cleanup %d", eventLoop.timeoutsCount); + DEBUG("Cleanup %zu", eventLoop.timeoutsCount); /* Remove deleted entries, shuffling down remaining * entries as needed to form contiguous series @@ -517,12 +515,10 @@ static int virEventCleanupTimeouts(void) { /* Release some memory if we've got a big chunk free */ if ((eventLoop.timeoutsAlloc - EVENT_ALLOC_EXTENT) > eventLoop.timeoutsCount) { - EVENT_DEBUG("Releasing %d out of %d timeout slots used, releasing %d", + EVENT_DEBUG("Releasing %zu out of %zu timeout slots used, releasing %d", eventLoop.timeoutsCount, eventLoop.timeoutsAlloc, EVENT_ALLOC_EXTENT); - if (VIR_REALLOC_N(eventLoop.timeouts, - (eventLoop.timeoutsAlloc - EVENT_ALLOC_EXTENT)) < 0) - return -1; - eventLoop.timeoutsAlloc -= EVENT_ALLOC_EXTENT; + VIR_SHRINK_N(eventLoop.timeouts, eventLoop.timeoutsAlloc, + EVENT_ALLOC_EXTENT); } return 0; } @@ -533,7 +529,7 @@ static int virEventCleanupTimeouts(void) { */ static int virEventCleanupHandles(void) { int i; - DEBUG("Cleanupo %d", eventLoop.handlesCount); + DEBUG("Cleanup %zu", eventLoop.handlesCount); /* Remove deleted entries, shuffling down remaining * entries as needed to form contiguous series @@ -557,12 +553,10 @@ static int virEventCleanupHandles(void) { /* Release some memory if we've got a big chunk free */ if ((eventLoop.handlesAlloc - EVENT_ALLOC_EXTENT) > eventLoop.handlesCount) { - EVENT_DEBUG("Releasing %d out of %d handles slots used, releasing %d", + EVENT_DEBUG("Releasing %zu out of %zu handles slots used, releasing %d", eventLoop.handlesCount, eventLoop.handlesAlloc, EVENT_ALLOC_EXTENT); - if (VIR_REALLOC_N(eventLoop.handles, - (eventLoop.handlesAlloc - EVENT_ALLOC_EXTENT)) < 0) - return -1; - eventLoop.handlesAlloc -= EVENT_ALLOC_EXTENT; + VIR_SHRINK_N(eventLoop.handles, eventLoop.handlesAlloc, + EVENT_ALLOC_EXTENT); } return 0; } diff --git a/daemon/libvirtd.c b/daemon/libvirtd.c index 711360b..f0681a7 100644 --- a/daemon/libvirtd.c +++ b/daemon/libvirtd.c @@ -1320,7 +1320,7 @@ static int qemudDispatchServer(struct qemud_server *server, struct qemud_socket return -1; } - if (VIR_REALLOC_N(server->clients, server->nclients+1) < 0) { + if (VIR_EXPAND_N(server->clients, server->nclients, 1) < 0) { VIR_ERROR0(_("Out of memory allocating clients")); close(fd); return -1; @@ -1444,7 +1444,7 @@ static int qemudDispatchServer(struct qemud_server *server, struct qemud_socket } } - server->clients[server->nclients++] = client; + server->clients[server->nclients - 1] = client; if (server->nclients > server->nactiveworkers && server->nactiveworkers < server->nworkers) { @@ -1468,6 +1468,7 @@ static int qemudDispatchServer(struct qemud_server *server, struct qemud_socket if (client) VIR_FREE(client->rx); VIR_FREE(client); + VIR_SHRINK_N(server->clients, server->nclients, 1); return -1; } @@ -2343,10 +2344,7 @@ static void *qemudRunLoop(void *opaque) { server->clients + i + 1, sizeof (*server->clients) * (server->nclients - i)); - if (VIR_REALLOC_N(server->clients, - server->nclients) < 0) { - ; /* ignore */ - } + VIR_SHRINK_N(server->clients, server->nclients, 0); goto reprocess; } } diff --git a/daemon/libvirtd.h b/daemon/libvirtd.h index 3f13fb1..8d7720d 100644 --- a/daemon/libvirtd.h +++ b/daemon/libvirtd.h @@ -1,7 +1,7 @@ /* * libvirtd.h: daemon data structure definitions * - * Copyright (C) 2006-2009 Red Hat, Inc. + * Copyright (C) 2006-2010 Red Hat, Inc. * Copyright (C) 2006 Daniel P. Berrange * * This library is free software; you can redistribute it and/or @@ -261,12 +261,12 @@ struct qemud_server { int privileged; - int nworkers; - int nactiveworkers; + size_t nworkers; + size_t nactiveworkers; struct qemud_worker *workers; - int nsockets; + size_t nsockets; struct qemud_socket *sockets; - int nclients; + size_t nclients; struct qemud_client **clients; int sigread; -- 1.7.2.1
On Sat, Aug 14, 2010 at 10:23:54AM -0600, Eric Blake wrote:
* daemon/libvirtd.h (qemud_server): Change types of members tracking array sizes. * daemon/event.c (virEventLoop): Likewise. (virEventAddHandleImpl, virEventAddTimeoutImpl) (virEventCleanupTimeouts, virEventCleanupHandles): Use VIR_EXPAND_N and VIR_SHRINK_N instead of VIR_REALLOC_N. Tweak debug messages to match type changes. * daemon/libvirtd.c (qemudDispatchServer, qemudRunLoop): Use VIR_EXPAND_N and VIR_SHRINK_N.
Signed-off-by: Eric Blake <eblake@redhat.com> --- daemon/event.c | 44 +++++++++++++++++++------------------------- daemon/libvirtd.c | 10 ++++------ daemon/libvirtd.h | 10 +++++----- 3 files changed, 28 insertions(+), 36 deletions(-)
ACK, looks nicer. Daniel -- |: Red Hat, Engineering, London -o- http://people.redhat.com/berrange/ :| |: http://libvirt.org -o- http://virt-manager.org -o- http://deltacloud.org :| |: http://autobuild.org -o- http://search.cpan.org/~danberr/ :| |: GnuPG: 7D3B9505 -o- F3C9 553F A1DA 4AC2 5648 23C1 B3DF F742 7D3B 9505 :|
* src/util/memory.h (VIR_RESIZE_N): New macro. * src/util/memory.c (virResizeN): New function. * docs/hacking.html.in: Document it. --- docs/hacking.html.in | 51 ++++++++++++++++++++++++++++++++++++++++++------- src/util/memory.c | 35 ++++++++++++++++++++++++++++++++++ src/util/memory.h | 26 +++++++++++++++++++++++++ 3 files changed, 104 insertions(+), 8 deletions(-) diff --git a/docs/hacking.html.in b/docs/hacking.html.in index 4cc92f4..4967184 100644 --- a/docs/hacking.html.in +++ b/docs/hacking.html.in @@ -347,7 +347,7 @@ } </pre></li> - <li><p>To allocate an array of objects</p> + <li><p>To allocate an array of objects:</p> <pre> virDomainPtr domains; @@ -359,11 +359,11 @@ } </pre></li> - <li><p>To allocate an array of object pointers</p> + <li><p>To allocate an array of object pointers:</p> <pre> virDomainPtr *domains; - int ndomains = 10; + size_t ndomains = 10; if (VIR_ALLOC_N(domains, ndomains) < 0) { virReportOOMError(); @@ -371,25 +371,60 @@ } </pre></li> - <li><p>To re-allocate the array of domains to be 10 elements longer</p> + <li><p>To re-allocate the array of domains to be 1 element + longer (however, note that repeatedly expanding an array by 1 + scales quadratically, so this is recommended only for smaller + arrays):</p> <pre> - if (VIR_EXPAND_N(domains, ndomains, 10) < 0) { + virDomainPtr domains; + size_t ndomains = 0; + + if (VIR_EXPAND_N(domains, ndomains, 1) < 0) { virReportOOMError(); return NULL; } + domains[ndomains - 1] = domain; </pre></li> - <li><p>To trim an array of domains to have one less element</p> + <li><p>To ensure an array has room to hold at least one more + element (this approach scales better, but requires tracking + allocation separately from usage)</p> <pre> + virDomainPtr domains; + size_t ndomains = 0; + size_t ndomains_max = 0; + + if (VIR_RESIZE_N(domains, ndomains_max, ndomains, 1) < 0) { + virReportOOMError(); + return NULL; + } + domains[ndomains++] = domain; +</pre></li> + + <li><p>To trim an array of domains to have one less element:</p> + +<pre> + virDomainPtr domains; + size_t ndomains = 0; + size_t ndomains_max = 0; + VIR_SHRINK_N(domains, ndomains, 1); </pre></li> - <li><p>To free the domain</p> + <li><p>To free an array of domains:</p> <pre> - VIR_FREE(domain); + virDomainPtr domains; + size_t ndomains = x; + size_t ndomains_max = y; + size_t i; + + for (i = 0; i < ndomains; i++) + VIR_FREE(domains[i]); + VIR_FREE(domains) + ndomains_max = ndomains = 0; </pre></li> </ul> diff --git a/src/util/memory.c b/src/util/memory.c index e95aa47..7485bcb 100644 --- a/src/util/memory.c +++ b/src/util/memory.c @@ -198,6 +198,41 @@ int virExpandN(void *ptrptr, size_t size, size_t *countptr, size_t add) } /** + * virResizeN: + * @ptrptr: pointer to pointer for address of allocated memory + * @size: number of bytes per element + * @allocptr: pointer to number of elements allocated in array + * @count: number of elements currently used in array + * @add: minimum number of additional elements to support in array + * + * If 'count' + 'add' is larger than '*allocptr', then Resize the + * block of memory in 'ptrptr' to be an array of at least 'count' + + * 'add' elements, each 'size' bytes in length. Update 'ptrptr' and + * 'allocptr' with the details of the newly allocated memory. On + * failure, 'ptrptr' and 'allocptr' are not changed. Any newly + * allocated memory in 'ptrptr' is zero-filled. + * + * Returns -1 on failure to allocate, zero on success + */ +int virResizeN(void *ptrptr, size_t size, size_t *allocptr, size_t count, + size_t add) +{ + size_t delta; + + if (count + add < count) { + errno = ENOMEM; + return -1; + } + if (count + add <= *allocptr) + return 0; + + delta = count + add - *allocptr; + if (delta < *allocptr / 2) + delta = *allocptr / 2; + return virExpandN(ptrptr, size, allocptr, delta); +} + +/** * virShrinkN: * @ptrptr: pointer to pointer for address of allocated memory * @size: number of bytes per element diff --git a/src/util/memory.h b/src/util/memory.h index 98ac2b3..2b39393 100644 --- a/src/util/memory.h +++ b/src/util/memory.h @@ -54,6 +54,9 @@ int virReallocN(void *ptrptr, size_t size, size_t count) ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1); int virExpandN(void *ptrptr, size_t size, size_t *count, size_t add) ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3); +int virResizeN(void *ptrptr, size_t size, size_t *alloc, size_t count, + size_t desired) + ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3); void virShrinkN(void *ptrptr, size_t size, size_t *count, size_t remove) ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3); int virAllocVar(void *ptrptr, @@ -117,6 +120,29 @@ void virFree(void *ptrptr) ATTRIBUTE_NONNULL(1); virExpandN(&(ptr), sizeof(*(ptr)), &(count), add) /** + * VIR_RESIZE_N: + * @ptr: pointer to hold address of allocated memory + * @alloc: variable tracking number of elements currently allocated + * @count: number of elements currently in use + * @add: minimum number of elements to additionally support + * + * Blindly using VIR_EXPAND_N(array, alloc, 1) in a loop scales + * quadratically, because every iteration must copy contents from + * all prior iterations. But amortized linear scaling can be achieved + * by tracking allocation size separately from the number of used + * elements, and growing geometrically only as needed. + * + * If 'count' + 'add' is larger than 'count', then geometrically reallocate + * the array of 'alloc' elements, each sizeof(*ptr) bytes long, and store + * the address of allocated memory in 'ptr' and the new size in 'alloc'. + * The new elements are filled with zero. + * + * Returns -1 on failure, 0 on success + */ +# define VIR_RESIZE_N(ptr, alloc, count, add) \ + virResizeN(&(ptr), sizeof(*(ptr)), &(alloc), count, add) + +/** * VIR_SHRINK_N: * @ptr: pointer to hold address of allocated memory * @count: variable tracking number of elements currently allocated -- 1.7.2.1
* daemon/event.c (virEventAddHandleImpl, virEventAddTimeoutImpl): Change VIR_EXPAND_N to VIR_RESIZE_N. * daemon/libvirtd.c (qemudDispatchServer): Likewise. * daemon/libvirtd.h (qemud_server): Add allocation trackers. --- daemon/event.c | 12 ++++++------ daemon/libvirtd.c | 6 +++--- daemon/libvirtd.h | 1 + 3 files changed, 10 insertions(+), 9 deletions(-) diff --git a/daemon/event.c b/daemon/event.c index 77498e8..9ff0b6b 100644 --- a/daemon/event.c +++ b/daemon/event.c @@ -113,10 +113,10 @@ int virEventAddHandleImpl(int fd, int events, EVENT_DEBUG("Add handle fd=%d events=%d cb=%p opaque=%p", fd, events, cb, opaque); virEventLock(); if (eventLoop.handlesCount == eventLoop.handlesAlloc) { - EVENT_DEBUG("Used %zu handle slots, adding %d more", + EVENT_DEBUG("Used %zu handle slots, adding at least %d more", eventLoop.handlesAlloc, EVENT_ALLOC_EXTENT); - if (VIR_EXPAND_N(eventLoop.handles, eventLoop.handlesAlloc, - EVENT_ALLOC_EXTENT) < 0) { + if (VIR_RESIZE_N(eventLoop.handles, eventLoop.handlesAlloc, + eventLoop.handlesCount, EVENT_ALLOC_EXTENT) < 0) { virEventUnlock(); return -1; } @@ -213,10 +213,10 @@ int virEventAddTimeoutImpl(int frequency, virEventLock(); if (eventLoop.timeoutsCount == eventLoop.timeoutsAlloc) { - EVENT_DEBUG("Used %zu timeout slots, adding %d more", + EVENT_DEBUG("Used %zu timeout slots, adding at least %d more", eventLoop.timeoutsAlloc, EVENT_ALLOC_EXTENT); - if (VIR_EXPAND_N(eventLoop.timeouts, eventLoop.timeoutsAlloc, - EVENT_ALLOC_EXTENT) < 0) { + if (VIR_RESIZE_N(eventLoop.timeouts, eventLoop.timeoutsAlloc, + eventLoop.timeoutsCount, EVENT_ALLOC_EXTENT) < 0) { virEventUnlock(); return -1; } diff --git a/daemon/libvirtd.c b/daemon/libvirtd.c index f0681a7..150bacf 100644 --- a/daemon/libvirtd.c +++ b/daemon/libvirtd.c @@ -1320,7 +1320,8 @@ static int qemudDispatchServer(struct qemud_server *server, struct qemud_socket return -1; } - if (VIR_EXPAND_N(server->clients, server->nclients, 1) < 0) { + if (VIR_RESIZE_N(server->clients, server->nclients_max, + server->nclients, 1) < 0) { VIR_ERROR0(_("Out of memory allocating clients")); close(fd); return -1; @@ -1444,7 +1445,7 @@ static int qemudDispatchServer(struct qemud_server *server, struct qemud_socket } } - server->clients[server->nclients - 1] = client; + server->clients[server->nclients++] = client; if (server->nclients > server->nactiveworkers && server->nactiveworkers < server->nworkers) { @@ -1468,7 +1469,6 @@ static int qemudDispatchServer(struct qemud_server *server, struct qemud_socket if (client) VIR_FREE(client->rx); VIR_FREE(client); - VIR_SHRINK_N(server->clients, server->nclients, 1); return -1; } diff --git a/daemon/libvirtd.h b/daemon/libvirtd.h index 8d7720d..b45a0e1 100644 --- a/daemon/libvirtd.h +++ b/daemon/libvirtd.h @@ -267,6 +267,7 @@ struct qemud_server { size_t nsockets; struct qemud_socket *sockets; size_t nclients; + size_t nclients_max; struct qemud_client **clients; int sigread; -- 1.7.2.1
On 08/14/2010 10:23 AM, Eric Blake wrote:
So, after some IRC discussions, two ideas emerged in addition to the obvious documentation update. One is the simpler VIR_EXPAND_N, where the array size always matches the array allocation, along with a VIR_SHRINK_N counterpart which can trim an array back down (and failure to trim need not be fatal). But this can scale quadratically if you end up with a large array, as the existing contents must be copied on every realloc. See patches 1 and 2 for an implementation and use.
The other idea is VIR_RESIZE_N, which tracks allocation separately from usage, and has better scaling by doing geometric growth only when needed rather than on every array usage increase. But it takes more parameters (making it slightly harder to remember how to use correctly), along with possible modifications of the struct tracking an array (so it might not be possible to modify all uses of VIR_REALLOC_N to use this, if it would end up altering a public struct layout). See patches 3 and 4 for an implementation and use.
Again on IRC, Matthias had yet another idea, by borrowing after c++'s new[] and delete[] operators. Basically, VIR_ALLOC_N overallocates, reserves the first 8 bytes for itself (or, more likely, __alignof__(union{size_t;long double;}) bytes, to be precise to platform alignment needs), and stores the length of the array in that chunk while returning an offset pointer to the user. That way, the user does not have to track allocations; all other VIR_*_N macros would be able to look before the user's pointer to find that hidden length field. On the other hand, it means we would need a VIR_FREE_N for arrays, since the user's pointer is not the same as the pointer returned by malloc; and mixing VIR_ALLOC/VIR_FREE_N or VIR_ALLOC_N/VIR_FREE is a disaster waiting to happen. It sounds like it might have some appeal for reducing some of the user's book-keeping, but would require a careful audit of code to safely match VIR_ALLOC_N exactly with VIR_FREE_N. Thoughts on this approach? -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
On Sat, Aug 14, 2010 at 01:08:33PM -0600, Eric Blake wrote:
On 08/14/2010 10:23 AM, Eric Blake wrote:
So, after some IRC discussions, two ideas emerged in addition to the obvious documentation update. One is the simpler VIR_EXPAND_N, where the array size always matches the array allocation, along with a VIR_SHRINK_N counterpart which can trim an array back down (and failure to trim need not be fatal). But this can scale quadratically if you end up with a large array, as the existing contents must be copied on every realloc. See patches 1 and 2 for an implementation and use.
The other idea is VIR_RESIZE_N, which tracks allocation separately from usage, and has better scaling by doing geometric growth only when needed rather than on every array usage increase. But it takes more parameters (making it slightly harder to remember how to use correctly), along with possible modifications of the struct tracking an array (so it might not be possible to modify all uses of VIR_REALLOC_N to use this, if it would end up altering a public struct layout). See patches 3 and 4 for an implementation and use.
Again on IRC, Matthias had yet another idea, by borrowing after c++'s new[] and delete[] operators. Basically, VIR_ALLOC_N overallocates, reserves the first 8 bytes for itself (or, more likely, __alignof__(union{size_t;long double;}) bytes, to be precise to platform alignment needs), and stores the length of the array in that chunk while returning an offset pointer to the user. That way, the user does not have to track allocations; all other VIR_*_N macros would be able to look before the user's pointer to find that hidden length field. On the other hand, it means we would need a VIR_FREE_N for arrays, since the user's pointer is not the same as the pointer returned by malloc; and mixing VIR_ALLOC/VIR_FREE_N or VIR_ALLOC_N/VIR_FREE is a disaster waiting to happen.
It sounds like it might have some appeal for reducing some of the user's book-keeping, but would require a careful audit of code to safely match VIR_ALLOC_N exactly with VIR_FREE_N. Thoughts on this approach?
The #1 goal of the memory allocation APIs is to make it hard to make programming mistakes. Having a VIR_FREE and VIR_FREE_N somewhat compromises that goal, for only a small convenience, so I don't think we need to go down that route. Regards, Daniel -- |: Red Hat, Engineering, London -o- http://people.redhat.com/berrange/ :| |: http://libvirt.org -o- http://virt-manager.org -o- http://deltacloud.org :| |: http://autobuild.org -o- http://search.cpan.org/~danberr/ :| |: GnuPG: 7D3B9505 -o- F3C9 553F A1DA 4AC2 5648 23C1 B3DF F742 7D3B 9505 :|
On 08/14/2010 02:05 PM, Daniel P. Berrange wrote:
It sounds like it might have some appeal for reducing some of the user's book-keeping, but would require a careful audit of code to safely match VIR_ALLOC_N exactly with VIR_FREE_N. Thoughts on this approach?
The #1 goal of the memory allocation APIs is to make it hard to make programming mistakes. Having a VIR_FREE and VIR_FREE_N somewhat compromises that goal, for only a small convenience, so I don't think we need to go down that route.
Thanks for the feedback. I agree with ditching the idea of VIR_FREE_N and any notion of storing the allocation size as part of the array - too much complexity to make it easier to write safe programs. Now back to the question in my original cover letter: does VIR_RESIZE_N look worthwhile, or should I confine my rework of VIR_REALLOC_N to just use VIR_EXPAND_N? -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
participants (2)
-
Daniel P. Berrange -
Eric Blake