From 676e604135b05af05b52111d76d05ee391dea5eb Mon Sep 17 00:00:00 2001 From: Wayne Davison Date: Tue, 29 May 2007 04:19:41 +0000 Subject: [PATCH] Added pool_free_old() and pool_boundary() functions to add a way to free all wholly affected extents older than a particular point in time. --- lib/pool_alloc.3 | 52 ++++++++++++++-- lib/pool_alloc.c | 156 +++++++++++++++++++++++++++++++---------------- lib/pool_alloc.h | 9 +-- 3 files changed, 155 insertions(+), 62 deletions(-) diff --git a/lib/pool_alloc.3 b/lib/pool_alloc.3 index 0fc7a551..2cecc6cf 100644 --- a/lib/pool_alloc.3 +++ b/lib/pool_alloc.3 @@ -28,7 +28,7 @@ See \fB\\$1\fP in \fB\\$2\fP for details. .. .TH POOL_ALLOC 3 .SH NAME -pool_alloc, pool_free, pool_talloc, pool_tfree, pool_create, pool_destroy +pool_alloc, pool_free, pool_free_old, pool_talloc, pool_tfree, pool_create, pool_destroy, pool_boundary \- Allocate and free memory in managed allocation pools. .SH SYNOPSIS .B #include "pool_alloc.h" @@ -41,9 +41,13 @@ pool_alloc, pool_free, pool_talloc, pool_tfree, pool_create, pool_destroy \fBvoid pool_free(struct alloc_pool *\fIpool\fB, size_t \fIsize\fB, void *\fIaddr\fB); +\fBvoid pool_free_old(struct alloc_pool *\fIpool\fB, void *\fIaddr\fB); + \fBvoid *pool_talloc(struct alloc_pool *\fIpool\fB, \fItype\fB), int \fIcount\fB, char *\fImsg\fB); \fBvoid pool_tfree(struct alloc_pool *\fIpool\fB, \fItype\fB, int \fIcount\fB, void *\fIaddr\fB); + +\fBvoid pool_boundary(struct alloc_pool *\fIpool\fB, sise_t \fIsize\fB); .SH DESCRIPTION .P The pool allocation routines use @@ -58,16 +62,17 @@ Instead, each extent tracks the total free memory within the extent. Each extent can either be used to allocate memory or to manage the freeing of memory within that extent. When an extent has less free memory than a given -allocation request (or at the request of the user), -memory within that extent ceases to be used for allocation, -and a new extent is added to the pool. +allocation request, the current extent ceases to be used +for allocation. See also the +.B pool_boundary() +function. .P This form of memory management is suited to large numbers of small related allocations that are held for a while and then freed as a group. Because the underlying allocations are done in large contiguous extents, -when an extent is freed, it releases a large enough +when an extent is freed, it can release a large enough contiguous block of memory to allow the memory to be returned to the OS for use by whatever program needs it. You can allocate from one or more memory pools and/or @@ -168,6 +173,38 @@ is no memory will be freed, but subsequent allocations will come from a new extent. .P +.B pool_free_old() +takes a boundary +.I addr +value that was returned by +.B pool_boundary() +and frees up any extents in the +.I pool +that have data allocated from that point backward in time. +NOTE: you must NOT mix calls to both +.B pool_free +and +.B pool_free_old +on the same pool! +.P +.B pool_boundary() +asks for a boundary value that can be sent to +.B pool_free_old() +at a later time to free up all memory allocated prior to a particular +moment in time. +If the extent that holds the boundary point has allocations from after the +boundary point, it will not be freed until a future +.B pool_free_old() +call encompasses the entirety of the extent's data. +If +.I len +is non-zero, the call will also check if the active extent has at least +that much free memory available in it, and if not, it will mark the +extent as inactive, forcing a new extent to be used for future allocations. +(You can specify -1 for +.I len +if you want to force a new extent to start.) +.P .B pool_talloc() is a macro that takes a .I type @@ -199,7 +236,12 @@ will normally require casting to the desired type but will returns a pointer of the requested .IR type . .P +.B pool_boundary() +returns a pointer that should only be used in a call to +.BR pool_free_old() . +.P .BR pool_free() , +.BR pool_free_old() , .B pool_tfree() and .B pool_destroy() diff --git a/lib/pool_alloc.c b/lib/pool_alloc.c index bc33003c..7d95f197 100644 --- a/lib/pool_alloc.c +++ b/lib/pool_alloc.c @@ -6,9 +6,7 @@ struct alloc_pool { size_t size; /* extent size */ size_t quantum; /* allocation quantum */ - struct pool_extent *live; /* current extent for - * allocations */ - struct pool_extent *free; /* unfreed extent list */ + struct pool_extent *extents; /* top extent is "live" */ void (*bomb)(); /* function to call if * malloc fails */ int flags; @@ -74,13 +72,7 @@ pool_destroy(alloc_pool_t p) if (!pool) return; - if (pool->live) { - cur = pool->live; - free(cur->start); - if (!(pool->flags & POOL_APPEND)) - free(cur); - } - for (cur = pool->free; cur; cur = next) { + for (cur = pool->extents; cur; cur = next) { next = cur->next; free(cur->start); if (!(pool->flags & POOL_APPEND)) @@ -104,7 +96,7 @@ pool_alloc(alloc_pool_t p, size_t len, const char *bomb_msg) if (len > pool->size) goto bomb_out; - if (!pool->live || len > pool->live->free) { + if (!pool->extents || len > pool->extents->free) { void *start; size_t free; size_t bound; @@ -112,11 +104,6 @@ pool_alloc(alloc_pool_t p, size_t len, const char *bomb_msg) size_t asize; struct pool_extent *ext; - if (pool->live) { - pool->live->next = pool->free; - pool->free = pool->live; - } - free = pool->size; bound = 0; @@ -142,8 +129,8 @@ pool_alloc(alloc_pool_t p, size_t len, const char *bomb_msg) ext->start = start; ext->free = free; ext->bound = bound; - ext->next = NULL; - pool->live = ext; + ext->next = pool->extents; + pool->extents = ext; pool->e_created++; } @@ -151,9 +138,9 @@ pool_alloc(alloc_pool_t p, size_t len, const char *bomb_msg) pool->n_allocated++; pool->b_allocated += len; - pool->live->free -= len; + pool->extents->free -= len; - return PTR_ADD(pool->live->start, pool->live->free); + return PTR_ADD(pool->extents->start, pool->extents->free); bomb_out: if (pool->bomb) @@ -178,25 +165,20 @@ pool_free(alloc_pool_t p, size_t len, void *addr) else if (pool->quantum > 1 && len % pool->quantum) len += pool->quantum - len % pool->quantum; - if (!addr && pool->live) { - pool->live->next = pool->free; - pool->free = pool->live; - pool->live = NULL; - return; - } pool->n_freed++; pool->b_freed += len; - cur = pool->live; - if (cur && addr >= cur->start - && addr < PTR_ADD(cur->start, pool->size)) { - if (addr == PTR_ADD(cur->start, cur->free)) { - if (pool->flags & POOL_CLEAR) - memset(addr, 0, len); - cur->free += len; - } else - cur->bound += len; - if (cur->free + cur->bound >= pool->size) { + for (prev = NULL, cur = pool->extents; cur; prev = cur, cur = cur->next) { + if (addr >= cur->start + && addr < PTR_ADD(cur->start, pool->size)) + break; + } + if (!cur) + return; + + if (!prev) { + /* The "live" extent is kept ready for more allocations. */ + if (cur->free + cur->bound + len >= pool->size) { size_t skew; if (pool->flags & POOL_CLEAR) { @@ -210,10 +192,44 @@ pool_free(alloc_pool_t p, size_t len, void *addr) cur->bound += skew; cur->free -= skew; } + } else if (addr == PTR_ADD(cur->start, cur->free)) { + if (pool->flags & POOL_CLEAR) + memset(addr, 0, len); + cur->free += len; + } else + cur->bound += len; + } else { + cur->bound += len; + + if (cur->free + cur->bound >= pool->size) { + prev->next = cur->next; + free(cur->start); + if (!(pool->flags & POOL_APPEND)) + free(cur); + pool->e_freed++; + } else if (prev != pool->extents) { + /* Move the extent to be the first non-live extent. */ + prev->next = cur->next; + cur->next = pool->extents->next; + pool->extents->next = cur; } - return; } - for (prev = NULL, cur = pool->free; cur; prev = cur, cur = cur->next) { +} + +/* This allows you to declare that the given address marks the edge of some + * pool memory that is no longer needed. Any extents that hold only data + * older than the boundary address are freed. NOTE: You MUST NOT USE BOTH + * pool_free() and pool_free_old() on the same pool!! */ +void +pool_free_old(alloc_pool_t p, void *addr) +{ + struct alloc_pool *pool = (struct alloc_pool *)p; + struct pool_extent *cur, *prev, *next; + + if (!pool || !addr) + return; + + for (prev = NULL, cur = pool->extents; cur; prev = cur, cur = cur->next) { if (addr >= cur->start && addr < PTR_ADD(cur->start, pool->size)) break; @@ -221,16 +237,32 @@ pool_free(alloc_pool_t p, size_t len, void *addr) if (!cur) return; - if (prev) { - prev->next = cur->next; - cur->next = pool->free; - pool->free = cur; - } - cur->bound += len; + if (addr == PTR_ADD(cur->start, cur->free)) { + if (prev) { + prev->next = NULL; + next = cur; + } else { + size_t skew; - if (cur->free + cur->bound >= pool->size) { - pool->free = cur->next; + /* The most recent live extent can just be reset. */ + if (pool->flags & POOL_CLEAR) + memset(addr, 0, pool->size - cur->free); + cur->free = pool->size; + cur->bound = 0; + if (pool->flags & POOL_QALIGN && pool->quantum > 1 + && (skew = (size_t)PTR_ADD(cur->start, cur->free) % pool->quantum)) { + cur->bound += skew; + cur->free -= skew; + } + next = cur->next; + } + } else { + next = cur->next; + cur->next = NULL; + } + while ((cur = next) != NULL) { + next = cur->next; free(cur->start); if (!(pool->flags & POOL_APPEND)) free(cur); @@ -238,6 +270,29 @@ pool_free(alloc_pool_t p, size_t len, void *addr) } } +/* If the current extent doesn't have "len" free space in it, mark it as full + * so that the next alloc will start a new extent. If len is (size_t)-1, this + * bump will always occur. The function returns a boundary address that can + * be used with pool_free_old(), or a NULL if no memory is allocated. */ +void * +pool_boundary(alloc_pool_t p, size_t len) +{ + struct alloc_pool *pool = (struct alloc_pool *)p; + struct pool_extent *cur; + + if (!pool || !pool->extents) + return NULL; + + cur = pool->extents; + + if (cur->free < len) { + cur->bound += cur->free; + cur->free = 0; + } + + return PTR_ADD(cur->start, cur->free); +} + #define FDPRINT(label, value) \ snprintf(buf, sizeof buf, label, value), \ write(fd, buf, strlen(buf)) @@ -270,16 +325,11 @@ pool_stats(alloc_pool_t p, int fd, int summarize) if (summarize) return; - if (!pool->live && !pool->free) + if (!pool->extents) return; write(fd, "\n", 1); - if (pool->live) - FDEXTSTAT(pool->live); - strlcpy(buf, " FREE BOUND\n", sizeof buf); - write(fd, buf, strlen(buf)); - - for (cur = pool->free; cur; cur = cur->next) + for (cur = pool->extents; cur; cur = cur->next) FDEXTSTAT(cur); } diff --git a/lib/pool_alloc.h b/lib/pool_alloc.h index 3d095634..e9a5da4f 100644 --- a/lib/pool_alloc.h +++ b/lib/pool_alloc.h @@ -9,12 +9,13 @@ typedef void *alloc_pool_t; alloc_pool_t pool_create(size_t size, size_t quantum, void (*bomb)(const char *), int flags); void pool_destroy(alloc_pool_t pool); -void *pool_alloc(alloc_pool_t pool, size_t size, const char *bomb); +void *pool_alloc(alloc_pool_t pool, size_t size, const char *bomb_msg); void pool_free(alloc_pool_t pool, size_t size, void *addr); +void pool_free_old(alloc_pool_t pool, void *addr); +void *pool_boundary(alloc_pool_t pool, size_t size); -#define pool_talloc(pool, type, count, bomb) \ - ((type *)pool_alloc(pool, sizeof(type) * count, bomb)) +#define pool_talloc(pool, type, count, bomb_msg) \ + ((type *)pool_alloc(pool, sizeof(type) * count, bomb_msg)) #define pool_tfree(pool, type, count, addr) \ (pool_free(pool, sizeof(type) * count, addr)) - -- 2.34.1