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
28 /* Fast, low-overhead memory block suballocator. */
31 struct pool *parent; /* Pool of which this pool is a subpool. */
32 struct pool_block *blocks; /* Blocks owned by the pool. */
33 struct pool_gizmo *gizmos; /* Other stuff owned by the pool. */
39 struct pool_block *prev;
40 struct pool_block *next;
50 POOL_GIZMO_REGISTERED,
53 /* Pool routines can maintain objects (`gizmos') as well as doing
55 This structure is used to keep track of them. */
58 struct pool_gizmo *prev;
59 struct pool_gizmo *next;
61 long serial; /* Serial number. */
62 int type; /* Type of this gizmo. */
64 /* Type-dependent info. */
67 FILE *file; /* POOL_GIZMO_FILE. */
68 struct pool *subpool; /* POOL_GIZMO_SUBPOOL. */
70 /* POOL_GIZMO_REGISTERED. */
73 void (*free) (void *p);
81 /* Rounds X up to the next multiple of Y. */
83 #define ROUND_UP(X, Y) \
84 (((X) + ((Y) - 1)) / (Y) * (Y))
87 /* Types that provide typically useful alignment sizes. */
96 /* This should be the alignment size used by malloc(). The size of
97 the union above is correct, if not optimal, in all known cases. */
98 #if defined (i386) || defined (__i386__)
99 #define ALIGN_SIZE 4 /* Save some extra memory. */
101 #define ALIGN_SIZE sizeof (union align)
104 /* DISCRETE_BLOCKS may be declared as nonzero to prevent suballocation
105 of blocks. This is useful under memory debuggers like Checker
106 because it allows the source location of bugs to be more accurately
109 On the other hand, if we're testing the library, then we want to
110 test the library's real functionality, not its crippled, slow,
111 simplified functionality. */
112 #if __CHECKER__ && !SELF_TEST
113 #define DISCRETE_BLOCKS 1
116 /* Enable debug code if appropriate. */
122 /* Size of each block allocated in the pool, in bytes.
123 Should be at least 1k. */
125 #define BLOCK_SIZE 1024
128 /* Maximum size of a suballocated block. Larger blocks are allocated
129 directly with malloc() to avoid memory wastage at the end of a
130 suballocation block. */
132 #define MAX_SUBALLOC 64
135 /* Sizes of some structures with alignment padding included. */
136 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
137 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
138 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
140 /* Serial number used to keep track of gizmos for mark/release. */
141 static long serial = 0;
144 static void add_gizmo (struct pool *, struct pool_gizmo *);
145 static void free_gizmo (struct pool_gizmo *);
146 static void delete_gizmo (struct pool *, struct pool_gizmo *);
149 static void *xmalloc (size_t);
150 static void *xrealloc (void *, size_t);
153 /* General routines. */
155 /* Creates and returns a new memory pool, which allows malloc()'d
156 blocks to be suballocated in a time- and space-efficient manner.
157 The entire contents of the memory pool are freed at once.
159 In addition, other objects can be associated with a memory pool.
160 These are released when the pool is destroyed. */
164 struct pool_block *block;
167 block = xmalloc (BLOCK_SIZE);
168 block->prev = block->next = block;
169 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
171 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
173 pool->blocks = block;
179 /* Destroy the specified pool, including all subpools. */
181 pool_destroy (struct pool *pool)
188 (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
191 struct pool_gizmo *cur, *next;
193 for (cur = pool->gizmos; cur; cur = next)
201 struct pool_block *cur, *next;
203 pool->blocks->prev->next = NULL;
204 for (cur = pool->blocks; cur; cur = next)
212 /* Suballocation routines. */
214 /* Allocates a memory region AMT bytes in size from POOL and returns a
215 pointer to the region's start. */
217 pool_alloc (struct pool *pool, size_t amt)
219 assert (pool != NULL);
221 #if !DISCRETE_BLOCKS /* Help identify source of bugs for Checker users. */
222 if (amt <= MAX_SUBALLOC)
224 struct pool_block *b = pool->blocks;
225 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
226 if (b->ofs + amt <= BLOCK_SIZE)
228 void *const p = ((char *) b) + b->ofs;
233 b = xmalloc (BLOCK_SIZE);
234 b->next = pool->blocks;
235 b->prev = pool->blocks->prev;
236 b->ofs = POOL_BLOCK_SIZE + amt;
238 pool->blocks->prev->next = b;
239 pool->blocks = pool->blocks->prev = b;
241 return ((char *) b) + POOL_BLOCK_SIZE;
244 #endif /* !DISCRETE_BLOCKS */
245 return pool_malloc (pool, amt);
248 /* Duplicates STRING within POOL and returns a pointer to the
251 pool_strdup (struct pool *pool, const char *string)
256 assert (pool && string);
257 amt = strlen (string) + 1;
259 /* Note that strings need not be aligned on any boundary. */
262 struct pool_block *const b = pool->blocks;
264 if (b->ofs + amt <= BLOCK_SIZE)
266 p = ((char *) b) + b->ofs;
271 p = pool_alloc (pool, amt);
274 memcpy (p, string, amt);
278 /* Standard allocation routines. */
280 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
281 returns a pointer to the beginning of the block.
282 If POOL is a null pointer, then allocates a normal memory block
285 pool_malloc (struct pool *pool, size_t amt)
291 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
292 g->type = POOL_GIZMO_MALLOC;
295 return ((char *) g) + POOL_GIZMO_SIZE;
301 return xmalloc (amt);
304 /* Changes the allocation size of the specified memory block P managed
305 by POOL to AMT bytes and returns a pointer to the beginning of the
307 If POOL is a null pointer, then the block is reallocated in the
308 usual way with realloc(). */
310 pool_realloc (struct pool *pool, void *p, size_t amt)
318 struct pool_gizmo *g;
320 g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
321 amt + POOL_GIZMO_SIZE);
329 return ((char *) g) + POOL_GIZMO_SIZE;
338 return pool_malloc (pool, amt);
341 return xrealloc (p, amt);
344 /* Frees block P managed by POOL.
345 If POOL is a null pointer, then the block is freed as usual with
348 pool_free (struct pool *pool, void *p)
350 if (pool != NULL && p != NULL)
352 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
353 delete_gizmo (pool, g);
360 /* Gizmo allocations. */
362 /* Creates and returns a pool as a subpool of POOL.
363 The subpool will be destroyed automatically when POOL is destroyed.
364 It may also be destroyed explicitly in advance. */
366 pool_create_subpool (struct pool *pool)
368 struct pool *subpool;
369 struct pool_gizmo *g;
371 assert (pool != NULL);
372 subpool = pool_create ();
373 subpool->parent = pool;
375 g = (void *) (((char *) subpool) + subpool->blocks->ofs);
376 subpool->blocks->ofs += POOL_GIZMO_SIZE;
378 g->type = POOL_GIZMO_SUBPOOL;
379 g->p.subpool = subpool;
386 /* Opens file FILENAME with mode MODE and returns a handle to it
387 if successful or a null pointer if not.
388 The file will be closed automatically when POOL is destroyed, or it
389 may be closed explicitly in advance using pool_fclose. */
391 pool_fopen (struct pool *pool, const char *filename, const char *mode)
395 assert (pool && filename && mode);
396 f = fopen (filename, mode);
401 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
402 g->type = POOL_GIZMO_FILE;
410 /* Closes file FILE managed by POOL. */
412 pool_fclose (struct pool *pool, FILE *file)
414 assert (pool && file);
415 if (fclose (file) == EOF)
419 struct pool_gizmo *g;
421 for (g = pool->gizmos; g; g = g->next)
422 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
424 delete_gizmo (pool, g);
432 /* Registers FREE to be called with argument P.
433 P should be unique among those registered in POOL so that it can be
434 uniquely identified by pool_unregister().
435 If not unregistered, FREE will be called with argument P when POOL
438 pool_register (struct pool *pool, void (*free) (void *), void *p)
440 assert (pool && free && p);
443 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
444 g->type = POOL_GIZMO_REGISTERED;
445 g->p.registered.free = free;
446 g->p.registered.p = p;
451 /* Unregisters previously registered P from POOL.
452 Returns nonzero only if P was found to be registered in POOL. */
454 pool_unregister (struct pool *pool, void *p)
459 struct pool_gizmo *g;
461 for (g = pool->gizmos; g; g = g->next)
462 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
464 delete_gizmo (pool, g);
472 /* Partial freeing. */
474 /* Notes the state of POOL into MARK so that it may be restored
475 by a call to pool_release(). */
477 pool_mark (struct pool *pool, struct pool_mark *mark)
479 assert (pool && mark);
481 mark->block = pool->blocks;
482 mark->ofs = pool->blocks->ofs;
484 mark->serial = serial;
487 /* Restores to POOL the state recorded in MARK. */
489 pool_release (struct pool *pool, const struct pool_mark *mark)
491 assert (pool && mark);
494 struct pool_gizmo *cur, *next;
496 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
512 struct pool_block *cur, *next, *last;
514 last = pool->blocks->prev;
515 for (cur = pool->blocks; cur != mark->block; cur = next)
518 assert (next != cur);
524 last->next = pool->blocks = cur;
526 cur->ofs = mark->ofs;
530 /* Private functions. */
532 /* Adds GIZMO at the beginning of POOL's gizmo list. */
534 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
536 assert (pool && gizmo);
538 gizmo->next = pool->gizmos;
541 pool->gizmos->prev = gizmo;
542 pool->gizmos = gizmo;
544 gizmo->serial = serial++;
547 /* Removes GIZMO from POOL's gizmo list. */
549 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
551 assert (pool && gizmo);
554 gizmo->prev->next = gizmo->next;
556 pool->gizmos = gizmo->next;
558 gizmo->next->prev = gizmo->prev;
561 /* Frees any of GIZMO's internal state.
562 GIZMO's data must not be referenced after calling this function. */
564 free_gizmo (struct pool_gizmo *gizmo)
566 assert (gizmo != NULL);
570 case POOL_GIZMO_MALLOC:
573 case POOL_GIZMO_FILE:
574 fclose (gizmo->p.file); /* Ignore errors. */
576 case POOL_GIZMO_SUBPOOL:
577 gizmo->p.subpool->parent = NULL;
578 pool_destroy (gizmo->p.subpool);
580 case POOL_GIZMO_REGISTERED:
581 gizmo->p.registered.free (gizmo->p.registered.p);
588 /* Memory allocation. */
591 /* Allocates SIZE bytes of space using malloc(). Aborts if out of
594 xmalloc (size_t size)
606 /* Reallocates P to be SIZE bytes long using realloc(). Aborts if out
609 xrealloc (void *p, size_t size)
612 return xmalloc (size);
618 p = realloc (p, size);
625 /* Self-test routine. */
634 #define N_ITERATIONS 8192
637 /* Self-test routine.
638 This is not exhaustive, but it can be useful. */
640 main (int argc, char **argv)
645 seed = atoi (argv[1]);
647 seed = time (0) * 257 % 32768;
652 struct pool_mark m1, m2;
653 FILE *files[N_FILES];
657 printf ("Random number seed: %d\n", seed);
660 printf ("Creating pool...\n");
661 pool = pool_create ();
663 printf ("Marking pool state...\n");
664 pool_mark (pool, &m1);
666 printf (" Populating pool with random-sized small objects...\n");
667 for (i = 0; i < N_ITERATIONS; i++)
669 size_t size = rand () % MAX_SUBALLOC;
670 void *p = pool_alloc (pool, size);
674 printf (" Marking pool state...\n");
675 pool_mark (pool, &m2);
677 printf (" Populating pool with random-sized small "
678 "and large objects...\n");
679 for (i = 0; i < N_ITERATIONS; i++)
681 size_t size = rand () % (2 * MAX_SUBALLOC);
682 void *p = pool_alloc (pool, size);
686 printf (" Releasing pool state...\n");
687 pool_release (pool, &m2);
689 printf (" Populating pool with random objects and gizmos...\n");
690 for (i = 0; i < N_FILES; i++)
693 for (i = 0; i < N_ITERATIONS; i++)
695 int type = rand () % 32;
699 if (files[cur_file] != NULL
700 && EOF == pool_fclose (pool, files[cur_file]))
701 printf ("error on fclose: %s\n", strerror (errno));
703 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
705 if (++cur_file >= N_FILES)
709 pool_create_subpool (pool);
712 size_t size = rand () % (2 * MAX_SUBALLOC);
713 void *p = pool_alloc (pool, size);
718 printf ("Releasing pool state...\n");
719 pool_release (pool, &m1);
721 printf ("Destroying pool...\n");
728 #endif /* SELF_TEST */
732 compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"