8:23 p.m.
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
8:23 p.m.
New subject: [libvirt] [PATCH 1/4] memory: make it safer to expand arrays
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
8:20 p.m.
New subject: [libvirt] [PATCH 1/4] memory: make it safer to expand arrays
On Sat, Aug 14, 2010 at 10:23:53AM -0600, Eric Blake wrote:
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 :|
8:27 p.m.
New subject: [libvirt] [PATCH 1/4] memory: make it safer to expand arrays
On 08/16/2010 10:20 AM, Daniel P. Berrange wrote:
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
8:23 p.m.
New subject: [libvirt] [PATCH 2/4] daemon: use safer memory growth macros
* 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(a)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
8:21 p.m.
New subject: [libvirt] [PATCH 2/4] daemon: use safer memory growth macros
On Sat, Aug 14, 2010 at 10:23:54AM -0600, Eric Blake wrote:
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 :|
8:23 p.m.
New subject: [libvirt] [PATCH 3/4] memory: make it easier to avoid quadratic scaling of arrays
* 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
8:23 p.m.
New subject: [libvirt] [PATCH 4/4] daemon: use more efficient memory growth macros
* 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
11:08 p.m.
On 08/14/2010 10:23 AM, Eric Blake wrote:
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
12:05 a.m.
On Sat, Aug 14, 2010 at 01:08:33PM -0600, Eric Blake wrote:
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 :|
7:21 p.m.
On 08/14/2010 02:05 PM, Daniel P. Berrange wrote:
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
5326
days inactive
5328
days old
10 comments
2 participants
participants (2)
-
Daniel P. Berrange -
Eric Blake