X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fpool.c;h=b8ca4ad1205afbe6d069d308c0030f64eeb91502;hb=b9799cdd10b30ea96d9178b7a0d48504d052228c;hp=e7396574b38a6fac8b34072568c9020b573094f9;hpb=b18e1b9c95a478d434e9fcef9d8579d0b96b9a8d;p=pspp-builds.git diff --git a/src/pool.c b/src/pool.c index e7396574..b8ca4ad1 100644 --- a/src/pool.c +++ b/src/pool.c @@ -14,16 +14,16 @@ You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA - 02111-1307, USA. */ + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ -#if HAVE_CONFIG_H #include -#endif -#include +#include "pool.h" #include #include "alloc.h" -#include "pool.h" +#include "command.h" +#include "error.h" +#include "size_max.h" #include "str.h" /* Fast, low-overhead memory block suballocator. */ @@ -56,6 +56,7 @@ enum This structure is used to keep track of them. */ struct pool_gizmo { + struct pool *pool; struct pool_gizmo *prev; struct pool_gizmo *next; @@ -96,11 +97,7 @@ union align /* This should be the alignment size used by malloc(). The size of the union above is correct, if not optimal, in all known cases. */ -#if defined (i386) || defined (__i386__) -#define ALIGN_SIZE 4 /* Save some extra memory. */ -#else #define ALIGN_SIZE sizeof (union align) -#endif /* DISCRETE_BLOCKS may be declared as nonzero to prevent suballocation of blocks. This is useful under memory @@ -112,12 +109,6 @@ union align simplified functionality. */ /*#define DISCRETE_BLOCKS 1*/ -/* Enable debug code if appropriate. */ -#undef DEBUGGING -#if SELF_TEST -#define DEBUGGING 1 -#endif - /* Size of each block allocated in the pool, in bytes. Should be at least 1k. */ #ifndef BLOCK_SIZE @@ -142,12 +133,9 @@ static long serial = 0; /* Prototypes. */ static void add_gizmo (struct pool *, struct pool_gizmo *); static void free_gizmo (struct pool_gizmo *); +static void free_all_gizmos (struct pool *pool); static void delete_gizmo (struct pool *, struct pool_gizmo *); - -#if !PSPP -static void *xmalloc (size_t); -static void *xrealloc (void *, size_t); -#endif +static void check_gizmo (struct pool *, struct pool_gizmo *); /* General routines. */ @@ -175,6 +163,27 @@ pool_create (void) return pool; } +/* Creates a pool, allocates a block STRUCT_SIZE bytes in + length from it, stores the pool's address at offset + POOL_MEMBER_OFFSET within the block, and returns the allocated + block. + + Meant for use indirectly via pool_create_container(). */ +void * +pool_create_at_offset (size_t struct_size, size_t pool_member_offset) +{ + struct pool *pool; + char *struct_; + + assert (struct_size >= sizeof pool); + assert (pool_member_offset <= struct_size - sizeof pool); + + pool = pool_create (); + struct_ = pool_alloc (pool, struct_size); + *(struct pool **) (struct_ + pool_member_offset) = pool; + return struct_; +} + /* Destroy the specified pool, including all subpools. */ void pool_destroy (struct pool *pool) @@ -182,20 +191,13 @@ pool_destroy (struct pool *pool) if (pool == NULL) return; + /* Remove this pool from its parent's list of gizmos. */ if (pool->parent) - delete_gizmo (pool, - (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE)); - - { - struct pool_gizmo *cur, *next; - - for (cur = pool->gizmos; cur; cur = next) - { - next = cur->next; - free_gizmo (cur); - } - } + delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE)); + free_all_gizmos (pool); + + /* Free all the memory. */ { struct pool_block *cur, *next; @@ -207,19 +209,52 @@ pool_destroy (struct pool *pool) } } } + +/* Release all the memory and gizmos in POOL. + Blocks are not given back with free() but kept for later + allocations. To give back memory, use a subpool instead. */ +void +pool_clear (struct pool *pool) +{ + free_all_gizmos (pool); + + /* Zero out block sizes. */ + { + struct pool_block *cur; + + cur = pool->blocks; + do + { + cur->ofs = POOL_BLOCK_SIZE; + if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) + { + cur->ofs += POOL_SIZE; + if (pool->parent != NULL) + cur->ofs += POOL_GIZMO_SIZE; + } + cur = cur->next; + } + while (cur != pool->blocks); + } +} /* Suballocation routines. */ /* Allocates a memory region AMT bytes in size from POOL and returns a - pointer to the region's start. */ + pointer to the region's start. + The region is properly aligned for storing any object. */ void * pool_alloc (struct pool *pool, size_t amt) { assert (pool != NULL); + + if (amt == 0) + return NULL; -#if !DISCRETE_BLOCKS +#ifndef DISCRETE_BLOCKS if (amt <= MAX_SUBALLOC) { + /* If there is space in this block, take it. */ struct pool_block *b = pool->blocks; b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE); if (b->ofs + amt <= BLOCK_SIZE) @@ -229,53 +264,102 @@ pool_alloc (struct pool *pool, size_t amt) return p; } - b = xmalloc (BLOCK_SIZE); - b->next = pool->blocks; - b->prev = pool->blocks->prev; - b->ofs = POOL_BLOCK_SIZE + amt; - - pool->blocks->prev->next = b; - pool->blocks = pool->blocks->prev = b; - - return ((char *) b) + POOL_BLOCK_SIZE; + /* No space in this block, so we must make other + arrangements. */ + if (b->next->ofs == 0) + { + /* The next block is empty. Use it. */ + b = b->next; + b->ofs = POOL_BLOCK_SIZE; + if ((char *) b + POOL_BLOCK_SIZE == (char *) pool) + b->ofs += POOL_SIZE; + } + else + { + /* Create a new block at the start of the list. */ + b = xmalloc (BLOCK_SIZE); + b->next = pool->blocks; + b->prev = pool->blocks->prev; + b->ofs = POOL_BLOCK_SIZE; + pool->blocks->prev->next = b; + pool->blocks->prev = b; + } + pool->blocks = b; + + /* Allocate space from B. */ + b->ofs += amt; + return ((char *) b) + b->ofs - amt; } else -#endif /* !DISCRETE_BLOCKS */ +#endif return pool_malloc (pool, amt); } -/* Duplicates STRING, which has LENGTH characters, within POOL, - and returns a pointer to the duplicate. LENGTH should not - include the null terminator, which is always added to the - duplicate. For use only with strings, because the returned - pointere may not be aligned properly for other types. */ -char * -pool_strndup (struct pool *pool, const char *string, size_t length) +/* Allocates a memory region AMT bytes in size from POOL and + returns a pointer to the region's start. The region is not + necessarily aligned, so it is most suitable for storing + strings. */ +void * +pool_alloc_unaligned (struct pool *pool, size_t amt) { - size_t size; - char *copy; + assert (pool != NULL); - assert (pool && string); - size = length + 1; +#ifndef DISCRETE_BLOCKS + /* Strings need not be aligned on any boundary, but some + operations may be more efficient when they are. However, + that's only going to help with reasonably long strings. */ + if (amt < ALIGN_SIZE) + { + if (amt == 0) + return NULL; + else + { + struct pool_block *const b = pool->blocks; + + if (b->ofs + amt <= BLOCK_SIZE) + { + void *p = ((char *) b) + b->ofs; + b->ofs += amt; + return p; + } + } + } +#endif - /* Note that strings need not be aligned on any boundary. */ - { -#if !DISCRETE_BLOCKS - struct pool_block *const b = pool->blocks; + return pool_alloc (pool, amt); +} - if (b->ofs + size <= BLOCK_SIZE) - { - copy = ((char *) b) + b->ofs; - b->ofs += size; - } - else -#endif - copy = pool_alloc (pool, size); - } +/* Allocates a memory region N * S bytes in size from POOL and + returns a pointer to the region's start. + N must be nonnegative, S must be positive. + Terminates the program if the memory cannot be obtained, + including the case where N * S overflows the range of size_t. */ +void * +pool_nalloc (struct pool *pool, size_t n, size_t s) +{ + if (xalloc_oversized (n, s)) + xalloc_die (); + return pool_alloc (pool, n * s); +} - memcpy (copy, string, length); - copy[length] = '\0'; - return copy; +/* Allocates SIZE bytes in POOL, copies BUFFER into it, and + returns the new copy. */ +void * +pool_clone (struct pool *pool, const void *buffer, size_t size) +{ + void *block = pool_alloc (pool, size); + memcpy (block, buffer, size); + return block; +} + +/* Allocates SIZE bytes of unaligned data in POOL, copies BUFFER + into it, and returns the new copy. */ +void * +pool_clone_unaligned (struct pool *pool, const void *buffer, size_t size) +{ + void *block = pool_alloc_unaligned (pool, size); + memcpy (block, buffer, size); + return block; } /* Duplicates null-terminated STRING, within POOL, and returns a @@ -285,7 +369,7 @@ pool_strndup (struct pool *pool, const char *string, size_t length) char * pool_strdup (struct pool *pool, const char *string) { - return pool_strndup (pool, string, strlen (string)); + return pool_clone_unaligned (pool, string, strlen (string) + 1); } /* Standard allocation routines. */ @@ -293,7 +377,7 @@ pool_strdup (struct pool *pool, const char *string) /* Allocates AMT bytes using malloc(), to be managed by POOL, and returns a pointer to the beginning of the block. If POOL is a null pointer, then allocates a normal memory block - with malloc(). */ + with xmalloc(). */ void * pool_malloc (struct pool *pool, size_t amt) { @@ -314,6 +398,21 @@ pool_malloc (struct pool *pool, size_t amt) return xmalloc (amt); } +/* Allocates and returns N elements of S bytes each, to be + managed by POOL. + If POOL is a null pointer, then allocates a normal memory block + with malloc(). + N must be nonnegative, S must be positive. + Terminates the program if the memory cannot be obtained, + including the case where N * S overflows the range of size_t. */ +void * +pool_nmalloc (struct pool *pool, size_t n, size_t s) +{ + if (xalloc_oversized (n, s)) + xalloc_die (); + return pool_malloc (pool, n * s); +} + /* Changes the allocation size of the specified memory block P managed by POOL to AMT bytes and returns a pointer to the beginning of the block. @@ -328,16 +427,17 @@ pool_realloc (struct pool *pool, void *p, size_t amt) { if (amt != 0) { - struct pool_gizmo *g; + struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE); + check_gizmo (pool, g); - g = xrealloc (((char *) p) - POOL_GIZMO_SIZE, - amt + POOL_GIZMO_SIZE); + g = xrealloc (g, amt + POOL_GIZMO_SIZE); if (g->next) g->next->prev = g; if (g->prev) g->prev->next = g; else pool->gizmos = g; + check_gizmo (pool, g); return ((char *) g) + POOL_GIZMO_SIZE; } @@ -354,6 +454,116 @@ pool_realloc (struct pool *pool, void *p, size_t amt) return xrealloc (p, amt); } +/* Changes the allocation size of the specified memory block P + managed by POOL to N * S bytes and returns a pointer to the + beginning of the block. + N must be nonnegative, S must be positive. + If POOL is a null pointer, then the block is reallocated in + the usual way with xrealloc(). + Terminates the program if the memory cannot be obtained, + including the case where N * S overflows the range of size_t. */ +void * +pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s) +{ + if (xalloc_oversized (n, s)) + xalloc_die (); + return pool_realloc (pool, p, n * s); +} + +/* If P is null, allocate a block of at least *PN such objects; + otherwise, reallocate P so that it contains more than *PN + objects each of S bytes. *PN must be nonzero unless P is + null, and S must be nonzero. Set *PN to the new number of + objects, and return the pointer to the new block. *PN is + never set to zero, and the returned pointer is never null. + + The block returned is managed by POOL. If POOL is a null + pointer, then the block is reallocated in the usual way with + x2nrealloc(). + + Terminates the program if the memory cannot be obtained, + including the case where the memory required overflows the + range of size_t. + + Repeated reallocations are guaranteed to make progress, either by + allocating an initial block with a nonzero size, or by allocating a + larger block. + + In the following implementation, nonzero sizes are doubled so that + repeated reallocations have O(N log N) overall cost rather than + O(N**2) cost, but the specification for this function does not + guarantee that sizes are doubled. + + Here is an example of use: + + int *p = NULL; + struct pool *pool; + size_t used = 0; + size_t allocated = 0; + + void + append_int (int value) + { + if (used == allocated) + p = pool_2nrealloc (pool, p, &allocated, sizeof *p); + p[used++] = value; + } + + This causes x2nrealloc to allocate a block of some nonzero size the + first time it is called. + + To have finer-grained control over the initial size, set *PN to a + nonzero value before calling this function with P == NULL. For + example: + + int *p = NULL; + struct pool *pool; + size_t used = 0; + size_t allocated = 0; + size_t allocated1 = 1000; + + void + append_int (int value) + { + if (used == allocated) + { + p = pool_2nrealloc (pool, p, &allocated1, sizeof *p); + allocated = allocated1; + } + p[used++] = value; + } + + This function implementation is from gnulib. */ +void * +pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s) +{ + size_t n = *pn; + + if (p == NULL) + { + if (n == 0) + { + /* The approximate size to use for initial small allocation + requests, when the invoking code specifies an old size of + zero. 64 bytes is the largest "small" request for the + GNU C library malloc. */ + enum { DEFAULT_MXFAST = 64 }; + + n = DEFAULT_MXFAST / s; + n += !n; + } + } + else + { + if (SIZE_MAX / 2 / s < n) + xalloc_die (); + n *= 2; + } + + *pn = n; + return pool_realloc (pool, p, n * s); +} + /* Frees block P managed by POOL. If POOL is a null pointer, then the block is freed as usual with free(). */ @@ -363,6 +573,7 @@ pool_free (struct pool *pool, void *p) if (pool != NULL && p != NULL) { struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE); + check_gizmo (pool, g); delete_gizmo (pool, g); free (g); } @@ -385,7 +596,7 @@ pool_create_subpool (struct pool *pool) subpool = pool_create (); subpool->parent = pool; - g = (void *) (((char *) subpool) + subpool->blocks->ofs); + g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs); subpool->blocks->ofs += POOL_GIZMO_SIZE; g->type = POOL_GIZMO_SUBPOOL; @@ -396,6 +607,27 @@ pool_create_subpool (struct pool *pool) return subpool; } +/* Makes SUBPOOL a subpool of POOL. + SUBPOOL must not already have a parent pool. + The subpool will be destroyed automatically when POOL is destroyed. + It may also be destroyed explicitly in advance. */ +void +pool_add_subpool (struct pool *pool, struct pool *subpool) +{ + struct pool_gizmo *g; + + assert (pool != NULL); + assert (subpool != NULL); + assert (subpool->parent == NULL); + + g = pool_alloc (subpool, sizeof *g); + g->type = POOL_GIZMO_SUBPOOL; + g->p.subpool = subpool; + add_gizmo (pool, g); + + subpool->parent = pool; +} + /* Opens file FILENAME with mode MODE and returns a handle to it if successful or a null pointer if not. The file will be closed automatically when POOL is destroyed, or it @@ -497,7 +729,10 @@ pool_mark (struct pool *pool, struct pool_mark *mark) mark->serial = serial; } -/* Restores to POOL the state recorded in MARK. */ +/* Restores to POOL the state recorded in MARK. + Emptied blocks are not given back with free() but kept for + later allocations. To get that behavior, use a subpool + instead. */ void pool_release (struct pool *pool, const struct pool_mark *mark) { @@ -522,21 +757,20 @@ pool_release (struct pool *pool, const struct pool_mark *mark) } { - struct pool_block *cur, *next, *last; + struct pool_block *cur; - last = pool->blocks->prev; - for (cur = pool->blocks; cur != mark->block; cur = next) + for (cur = pool->blocks; cur != mark->block; cur = cur->next) { - next = cur->next; - assert (next != cur); - - free (cur); + cur->ofs = POOL_BLOCK_SIZE; + if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) + { + cur->ofs += POOL_SIZE; + if (pool->parent != NULL) + cur->ofs += POOL_GIZMO_SIZE; + } } - - cur->prev = last; - last->next = pool->blocks = cur; - - cur->ofs = mark->ofs; + pool->blocks = mark->block; + pool->blocks->ofs = mark->ofs; } } @@ -547,7 +781,8 @@ static void add_gizmo (struct pool *pool, struct pool_gizmo *gizmo) { assert (pool && gizmo); - + + gizmo->pool = pool; gizmo->next = pool->gizmos; gizmo->prev = NULL; if (pool->gizmos) @@ -555,6 +790,8 @@ add_gizmo (struct pool *pool, struct pool_gizmo *gizmo) pool->gizmos = gizmo; gizmo->serial = serial++; + + check_gizmo (pool, gizmo); } /* Removes GIZMO from POOL's gizmo list. */ @@ -562,7 +799,9 @@ static void delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo) { assert (pool && gizmo); - + + check_gizmo (pool, gizmo); + if (gizmo->prev) gizmo->prev->next = gizmo->next; else @@ -577,7 +816,7 @@ static void free_gizmo (struct pool_gizmo *gizmo) { assert (gizmo != NULL); - + switch (gizmo->type) { case POOL_GIZMO_MALLOC: @@ -597,47 +836,33 @@ free_gizmo (struct pool_gizmo *gizmo) assert (0); } } - -/* Memory allocation. */ -#if !PSPP -/* Allocates SIZE bytes of space using malloc(). Aborts if out of - memory. */ -static void * -xmalloc (size_t size) +/* Free all the gizmos in POOL. */ +static void +free_all_gizmos (struct pool *pool) { - void *vp; - if (size == 0) - return NULL; - vp = malloc (size); - assert (vp != NULL); - if (vp == NULL) - abort (); - return vp; -} + struct pool_gizmo *cur, *next; -/* Reallocates P to be SIZE bytes long using realloc(). Aborts if out - of memory. */ -static void * -xrealloc (void *p, size_t size) -{ - if (p == NULL) - return xmalloc (size); - if (size == 0) + for (cur = pool->gizmos; cur; cur = next) { - free (p); - return NULL; + next = cur->next; + free_gizmo (cur); } - p = realloc (p, size); - if (p == NULL) - abort (); - return p; + pool->gizmos = NULL; +} + +static void +check_gizmo (struct pool *p, struct pool_gizmo *g) +{ + assert (g->pool == p); + assert (g->next == NULL || g->next->prev == g); + assert ((g->prev != NULL && g->prev->next == g) + || (g->prev == NULL && p->gizmos == g)); + } -#endif /* !PSPP */ /* Self-test routine. */ -#if SELF_TEST #include #include #include @@ -650,14 +875,9 @@ xrealloc (void *p, size_t size) /* Self-test routine. This is not exhaustive, but it can be useful. */ int -main (int argc, char **argv) +cmd_debug_pool (void) { - int seed; - - if (argc == 2) - seed = atoi (argv[1]); - else - seed = time (0) * 257 % 32768; + int seed = time (0) * 257 % 32768; for (;;) { @@ -736,12 +956,7 @@ main (int argc, char **argv) putchar ('\n'); } -} -#endif /* SELF_TEST */ + return CMD_SUCCESS; +} -/* - Local variables: - compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c" - End: -*/