X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fpool.c;h=0f6b11e05caa7c3a090660cbddb86a6ed5161bec;hb=d7b5d9144738a5a8989d45a01f4e458a78b68c0b;hp=336671e2bcd6b84c868f380e95608dbc76ad47b8;hpb=7b98b3a4f58f6dc5a8e9cbc188b627966d5e652d;p=pspp diff --git a/src/pool.c b/src/pool.c index 336671e2bc..0f6b11e05c 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 "pool.h" -#include #include #include "alloc.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; @@ -112,10 +113,6 @@ union align simplified functionality. */ /*#define DISCRETE_BLOCKS 1*/ -/* Enable debug code if appropriate. */ -#if SELF_TEST -#endif - /* Size of each block allocated in the pool, in bytes. Should be at least 1k. */ #ifndef BLOCK_SIZE @@ -142,11 +139,7 @@ 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. */ @@ -183,9 +176,8 @@ pool_destroy (struct pool *pool) /* Remove this pool from its parent's list of gizmos. */ if (pool->parent) - delete_gizmo (pool->parent, - (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE)); - + delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE)); + free_all_gizmos (pool); /* Free all the memory. */ @@ -217,8 +209,12 @@ pool_clear (struct pool *pool) do { cur->ofs = POOL_BLOCK_SIZE; - if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) - cur->ofs += POOL_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); @@ -278,6 +274,29 @@ pool_alloc (struct pool *pool, size_t amt) return pool_malloc (pool, amt); } +/* 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); +} + +/* 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; +} + /* 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 @@ -302,6 +321,8 @@ pool_strndup (struct pool *pool, const char *string, size_t length) copy = ((char *) b) + b->ofs; b->ofs += size; } + else + copy = pool_alloc (pool, size); } #else copy = pool_alloc (pool, size); @@ -327,7 +348,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) { @@ -348,6 +369,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. @@ -362,16 +398,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; } @@ -388,6 +425,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(). */ @@ -397,6 +544,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); } @@ -419,7 +567,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; @@ -564,8 +712,12 @@ pool_release (struct pool *pool, const struct pool_mark *mark) for (cur = pool->blocks; cur != mark->block; cur = cur->next) { cur->ofs = POOL_BLOCK_SIZE; - if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) - cur->ofs += POOL_SIZE; + if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) + { + cur->ofs += POOL_SIZE; + if (pool->parent != NULL) + cur->ofs += POOL_GIZMO_SIZE; + } } pool->blocks = mark->block; pool->blocks->ofs = mark->ofs; @@ -579,7 +731,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) @@ -587,6 +740,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. */ @@ -594,7 +749,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 @@ -609,7 +766,7 @@ static void free_gizmo (struct pool_gizmo *gizmo) { assert (gizmo != NULL); - + switch (gizmo->type) { case POOL_GIZMO_MALLOC: @@ -641,48 +798,21 @@ free_all_gizmos (struct pool *pool) next = cur->next; free_gizmo (cur); } + pool->gizmos = NULL; } - -/* Memory allocation. */ -#if !PSPP -/* Allocates SIZE bytes of space using malloc(). Aborts if out of - memory. */ -static void * -xmalloc (size_t size) +static void +check_gizmo (struct pool *p, struct pool_gizmo *g) { - void *vp; - if (size == 0) - return NULL; - vp = malloc (size); - assert (vp != NULL); - if (vp == NULL) - abort (); - return vp; -} + 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)); -/* 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) - { - free (p); - return NULL; - } - p = realloc (p, size); - if (p == NULL) - abort (); - return p; } -#endif /* !PSPP */ /* Self-test routine. */ -#if SELF_TEST #include #include #include @@ -695,14 +825,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 (;;) { @@ -781,12 +906,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: -*/