1 /* PSPP - computes sample statistics.
2 Copyright (C) 2000 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>.
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 License, or (at your option) any later version.
10 This program is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
29 /* Fast, low-overhead memory block suballocator. */
32 struct pool *parent; /* Pool of which this pool is a subpool. */
33 struct pool_block *blocks; /* Blocks owned by the pool. */
34 struct pool_gizmo *gizmos; /* Other stuff owned by the pool. */
40 struct pool_block *prev;
41 struct pool_block *next;
51 POOL_GIZMO_REGISTERED,
54 /* Pool routines can maintain objects (`gizmos') as well as doing
56 This structure is used to keep track of them. */
59 struct pool_gizmo *prev;
60 struct pool_gizmo *next;
62 long serial; /* Serial number. */
63 int type; /* Type of this gizmo. */
65 /* Type-dependent info. */
68 FILE *file; /* POOL_GIZMO_FILE. */
69 struct pool *subpool; /* POOL_GIZMO_SUBPOOL. */
71 /* POOL_GIZMO_REGISTERED. */
74 void (*free) (void *p);
82 /* Rounds X up to the next multiple of Y. */
84 #define ROUND_UP(X, Y) \
85 (((X) + ((Y) - 1)) / (Y) * (Y))
88 /* Types that provide typically useful alignment sizes. */
97 /* This should be the alignment size used by malloc(). The size of
98 the union above is correct, if not optimal, in all known cases. */
99 #if defined (i386) || defined (__i386__)
100 #define ALIGN_SIZE 4 /* Save some extra memory. */
102 #define ALIGN_SIZE sizeof (union align)
105 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
106 suballocation of blocks. This is useful under memory
107 debuggers like Checker or valgrind because it allows the
108 source location of bugs to be more accurately pinpointed.
110 On the other hand, if we're testing the library, then we want to
111 test the library's real functionality, not its crippled, slow,
112 simplified functionality. */
113 /*#define DISCRETE_BLOCKS 1*/
115 /* Enable debug code if appropriate. */
119 /* Size of each block allocated in the pool, in bytes.
120 Should be at least 1k. */
122 #define BLOCK_SIZE 1024
125 /* Maximum size of a suballocated block. Larger blocks are allocated
126 directly with malloc() to avoid memory wastage at the end of a
127 suballocation block. */
129 #define MAX_SUBALLOC 64
132 /* Sizes of some structures with alignment padding included. */
133 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
134 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
135 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
137 /* Serial number used to keep track of gizmos for mark/release. */
138 static long serial = 0;
141 static void add_gizmo (struct pool *, struct pool_gizmo *);
142 static void free_gizmo (struct pool_gizmo *);
143 static void free_all_gizmos (struct pool *pool);
144 static void delete_gizmo (struct pool *, struct pool_gizmo *);
147 static void *xmalloc (size_t);
148 static void *xrealloc (void *, size_t);
151 /* General routines. */
153 /* Creates and returns a new memory pool, which allows malloc()'d
154 blocks to be suballocated in a time- and space-efficient manner.
155 The entire contents of the memory pool are freed at once.
157 In addition, other objects can be associated with a memory pool.
158 These are released when the pool is destroyed. */
162 struct pool_block *block;
165 block = xmalloc (BLOCK_SIZE);
166 block->prev = block->next = block;
167 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
169 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
171 pool->blocks = block;
177 /* Destroy the specified pool, including all subpools. */
179 pool_destroy (struct pool *pool)
184 /* Remove this pool from its parent's list of gizmos. */
186 delete_gizmo (pool->parent,
187 (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
189 free_all_gizmos (pool);
191 /* Free all the memory. */
193 struct pool_block *cur, *next;
195 pool->blocks->prev->next = NULL;
196 for (cur = pool->blocks; cur; cur = next)
204 /* Release all the memory and gizmos in POOL.
205 Blocks are not given back with free() but kept for later
206 allocations. To give back memory, use a subpool instead. */
208 pool_clear (struct pool *pool)
210 free_all_gizmos (pool);
212 /* Zero out block sizes. */
214 struct pool_block *cur;
219 cur->ofs = POOL_BLOCK_SIZE;
220 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
221 cur->ofs += POOL_SIZE;
224 while (cur != pool->blocks);
228 /* Suballocation routines. */
230 /* Allocates a memory region AMT bytes in size from POOL and returns a
231 pointer to the region's start. */
233 pool_alloc (struct pool *pool, size_t amt)
235 assert (pool != NULL);
237 #ifndef DISCRETE_BLOCKS
238 if (amt <= MAX_SUBALLOC)
240 /* If there is space in this block, take it. */
241 struct pool_block *b = pool->blocks;
242 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
243 if (b->ofs + amt <= BLOCK_SIZE)
245 void *const p = ((char *) b) + b->ofs;
250 /* No space in this block, so we must make other
252 if (b->next->ofs == 0)
254 /* The next block is empty. Use it. */
256 b->ofs = POOL_BLOCK_SIZE;
257 if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
262 /* Create a new block at the start of the list. */
263 b = xmalloc (BLOCK_SIZE);
264 b->next = pool->blocks;
265 b->prev = pool->blocks->prev;
266 b->ofs = POOL_BLOCK_SIZE;
267 pool->blocks->prev->next = b;
268 pool->blocks->prev = b;
272 /* Allocate space from B. */
274 return ((char *) b) + b->ofs - amt;
278 return pool_malloc (pool, amt);
281 /* Duplicates STRING, which has LENGTH characters, within POOL,
282 and returns a pointer to the duplicate. LENGTH should not
283 include the null terminator, which is always added to the
284 duplicate. For use only with strings, because the returned
285 pointere may not be aligned properly for other types. */
287 pool_strndup (struct pool *pool, const char *string, size_t length)
292 assert (pool && string);
295 /* Note that strings need not be aligned on any boundary. */
296 #ifndef DISCRETE_BLOCKS
298 struct pool_block *const b = pool->blocks;
300 if (b->ofs + size <= BLOCK_SIZE)
302 copy = ((char *) b) + b->ofs;
307 copy = pool_alloc (pool, size);
310 memcpy (copy, string, length);
315 /* Duplicates null-terminated STRING, within POOL, and returns a
316 pointer to the duplicate. For use only with strings, because
317 the returned pointere may not be aligned properly for other
320 pool_strdup (struct pool *pool, const char *string)
322 return pool_strndup (pool, string, strlen (string));
325 /* Standard allocation routines. */
327 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
328 returns a pointer to the beginning of the block.
329 If POOL is a null pointer, then allocates a normal memory block
332 pool_malloc (struct pool *pool, size_t amt)
338 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
339 g->type = POOL_GIZMO_MALLOC;
342 return ((char *) g) + POOL_GIZMO_SIZE;
348 return xmalloc (amt);
351 /* Changes the allocation size of the specified memory block P managed
352 by POOL to AMT bytes and returns a pointer to the beginning of the
354 If POOL is a null pointer, then the block is reallocated in the
355 usual way with realloc(). */
357 pool_realloc (struct pool *pool, void *p, size_t amt)
365 struct pool_gizmo *g;
367 g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
368 amt + POOL_GIZMO_SIZE);
376 return ((char *) g) + POOL_GIZMO_SIZE;
385 return pool_malloc (pool, amt);
388 return xrealloc (p, amt);
391 /* Frees block P managed by POOL.
392 If POOL is a null pointer, then the block is freed as usual with
395 pool_free (struct pool *pool, void *p)
397 if (pool != NULL && p != NULL)
399 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
400 delete_gizmo (pool, g);
407 /* Gizmo allocations. */
409 /* Creates and returns a pool as a subpool of POOL.
410 The subpool will be destroyed automatically when POOL is destroyed.
411 It may also be destroyed explicitly in advance. */
413 pool_create_subpool (struct pool *pool)
415 struct pool *subpool;
416 struct pool_gizmo *g;
418 assert (pool != NULL);
419 subpool = pool_create ();
420 subpool->parent = pool;
422 g = (void *) (((char *) subpool) + subpool->blocks->ofs);
423 subpool->blocks->ofs += POOL_GIZMO_SIZE;
425 g->type = POOL_GIZMO_SUBPOOL;
426 g->p.subpool = subpool;
433 /* Opens file FILENAME with mode MODE and returns a handle to it
434 if successful or a null pointer if not.
435 The file will be closed automatically when POOL is destroyed, or it
436 may be closed explicitly in advance using pool_fclose. */
438 pool_fopen (struct pool *pool, const char *filename, const char *mode)
442 assert (pool && filename && mode);
443 f = fopen (filename, mode);
448 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
449 g->type = POOL_GIZMO_FILE;
457 /* Closes file FILE managed by POOL. */
459 pool_fclose (struct pool *pool, FILE *file)
461 assert (pool && file);
462 if (fclose (file) == EOF)
466 struct pool_gizmo *g;
468 for (g = pool->gizmos; g; g = g->next)
469 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
471 delete_gizmo (pool, g);
479 /* Registers FREE to be called with argument P.
480 P should be unique among those registered in POOL so that it can be
481 uniquely identified by pool_unregister().
482 If not unregistered, FREE will be called with argument P when POOL
485 pool_register (struct pool *pool, void (*free) (void *), void *p)
487 assert (pool && free && p);
490 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
491 g->type = POOL_GIZMO_REGISTERED;
492 g->p.registered.free = free;
493 g->p.registered.p = p;
498 /* Unregisters previously registered P from POOL.
499 Returns nonzero only if P was found to be registered in POOL. */
501 pool_unregister (struct pool *pool, void *p)
506 struct pool_gizmo *g;
508 for (g = pool->gizmos; g; g = g->next)
509 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
511 delete_gizmo (pool, g);
519 /* Partial freeing. */
521 /* Notes the state of POOL into MARK so that it may be restored
522 by a call to pool_release(). */
524 pool_mark (struct pool *pool, struct pool_mark *mark)
526 assert (pool && mark);
528 mark->block = pool->blocks;
529 mark->ofs = pool->blocks->ofs;
531 mark->serial = serial;
534 /* Restores to POOL the state recorded in MARK.
535 Emptied blocks are not given back with free() but kept for
536 later allocations. To get that behavior, use a subpool
539 pool_release (struct pool *pool, const struct pool_mark *mark)
541 assert (pool && mark);
544 struct pool_gizmo *cur, *next;
546 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
562 struct pool_block *cur;
564 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
566 cur->ofs = POOL_BLOCK_SIZE;
567 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
568 cur->ofs += POOL_SIZE;
570 pool->blocks = mark->block;
571 pool->blocks->ofs = mark->ofs;
575 /* Private functions. */
577 /* Adds GIZMO at the beginning of POOL's gizmo list. */
579 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
581 assert (pool && gizmo);
583 gizmo->next = pool->gizmos;
586 pool->gizmos->prev = gizmo;
587 pool->gizmos = gizmo;
589 gizmo->serial = serial++;
592 /* Removes GIZMO from POOL's gizmo list. */
594 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
596 assert (pool && gizmo);
599 gizmo->prev->next = gizmo->next;
601 pool->gizmos = gizmo->next;
603 gizmo->next->prev = gizmo->prev;
606 /* Frees any of GIZMO's internal state.
607 GIZMO's data must not be referenced after calling this function. */
609 free_gizmo (struct pool_gizmo *gizmo)
611 assert (gizmo != NULL);
615 case POOL_GIZMO_MALLOC:
618 case POOL_GIZMO_FILE:
619 fclose (gizmo->p.file); /* Ignore errors. */
621 case POOL_GIZMO_SUBPOOL:
622 gizmo->p.subpool->parent = NULL;
623 pool_destroy (gizmo->p.subpool);
625 case POOL_GIZMO_REGISTERED:
626 gizmo->p.registered.free (gizmo->p.registered.p);
633 /* Free all the gizmos in POOL. */
635 free_all_gizmos (struct pool *pool)
637 struct pool_gizmo *cur, *next;
639 for (cur = pool->gizmos; cur; cur = next)
646 /* Memory allocation. */
649 /* Allocates SIZE bytes of space using malloc(). Aborts if out of
652 xmalloc (size_t size)
664 /* Reallocates P to be SIZE bytes long using realloc(). Aborts if out
667 xrealloc (void *p, size_t size)
670 return xmalloc (size);
676 p = realloc (p, size);
683 /* Self-test routine. */
692 #define N_ITERATIONS 8192
695 /* Self-test routine.
696 This is not exhaustive, but it can be useful. */
698 main (int argc, char **argv)
703 seed = atoi (argv[1]);
705 seed = time (0) * 257 % 32768;
710 struct pool_mark m1, m2;
711 FILE *files[N_FILES];
715 printf ("Random number seed: %d\n", seed);
718 printf ("Creating pool...\n");
719 pool = pool_create ();
721 printf ("Marking pool state...\n");
722 pool_mark (pool, &m1);
724 printf (" Populating pool with random-sized small objects...\n");
725 for (i = 0; i < N_ITERATIONS; i++)
727 size_t size = rand () % MAX_SUBALLOC;
728 void *p = pool_alloc (pool, size);
732 printf (" Marking pool state...\n");
733 pool_mark (pool, &m2);
735 printf (" Populating pool with random-sized small "
736 "and large objects...\n");
737 for (i = 0; i < N_ITERATIONS; i++)
739 size_t size = rand () % (2 * MAX_SUBALLOC);
740 void *p = pool_alloc (pool, size);
744 printf (" Releasing pool state...\n");
745 pool_release (pool, &m2);
747 printf (" Populating pool with random objects and gizmos...\n");
748 for (i = 0; i < N_FILES; i++)
751 for (i = 0; i < N_ITERATIONS; i++)
753 int type = rand () % 32;
757 if (files[cur_file] != NULL
758 && EOF == pool_fclose (pool, files[cur_file]))
759 printf ("error on fclose: %s\n", strerror (errno));
761 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
763 if (++cur_file >= N_FILES)
767 pool_create_subpool (pool);
770 size_t size = rand () % (2 * MAX_SUBALLOC);
771 void *p = pool_alloc (pool, size);
776 printf ("Releasing pool state...\n");
777 pool_release (pool, &m1);
779 printf ("Destroying pool...\n");
786 #endif /* SELF_TEST */
790 compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"