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. */
121 /* Size of each block allocated in the pool, in bytes.
122 Should be at least 1k. */
124 #define BLOCK_SIZE 1024
127 /* Maximum size of a suballocated block. Larger blocks are allocated
128 directly with malloc() to avoid memory wastage at the end of a
129 suballocation block. */
131 #define MAX_SUBALLOC 64
134 /* Sizes of some structures with alignment padding included. */
135 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
136 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
137 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
139 /* Serial number used to keep track of gizmos for mark/release. */
140 static long serial = 0;
143 static void add_gizmo (struct pool *, struct pool_gizmo *);
144 static void free_gizmo (struct pool_gizmo *);
145 static void delete_gizmo (struct pool *, struct pool_gizmo *);
148 static void *xmalloc (size_t);
149 static void *xrealloc (void *, size_t);
152 /* General routines. */
154 /* Creates and returns a new memory pool, which allows malloc()'d
155 blocks to be suballocated in a time- and space-efficient manner.
156 The entire contents of the memory pool are freed at once.
158 In addition, other objects can be associated with a memory pool.
159 These are released when the pool is destroyed. */
163 struct pool_block *block;
166 block = xmalloc (BLOCK_SIZE);
167 block->prev = block->next = block;
168 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
170 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
172 pool->blocks = block;
178 /* Destroy the specified pool, including all subpools. */
180 pool_destroy (struct pool *pool)
187 (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
190 struct pool_gizmo *cur, *next;
192 for (cur = pool->gizmos; cur; cur = next)
200 struct pool_block *cur, *next;
202 pool->blocks->prev->next = NULL;
203 for (cur = pool->blocks; cur; cur = next)
211 /* Suballocation routines. */
213 /* Allocates a memory region AMT bytes in size from POOL and returns a
214 pointer to the region's start. */
216 pool_alloc (struct pool *pool, size_t amt)
218 assert (pool != NULL);
220 #if !DISCRETE_BLOCKS /* Help identify source of bugs for Checker users. */
221 if (amt <= MAX_SUBALLOC)
223 struct pool_block *b = pool->blocks;
224 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
225 if (b->ofs + amt <= BLOCK_SIZE)
227 void *const p = ((char *) b) + b->ofs;
232 b = xmalloc (BLOCK_SIZE);
233 b->next = pool->blocks;
234 b->prev = pool->blocks->prev;
235 b->ofs = POOL_BLOCK_SIZE + amt;
237 pool->blocks->prev->next = b;
238 pool->blocks = pool->blocks->prev = b;
240 return ((char *) b) + POOL_BLOCK_SIZE;
243 #endif /* !DISCRETE_BLOCKS */
244 return pool_malloc (pool, amt);
247 /* Duplicates STRING within POOL and returns a pointer to the
250 pool_strdup (struct pool *pool, const char *string)
255 assert (pool && string);
256 amt = strlen (string) + 1;
258 /* Note that strings need not be aligned on any boundary. */
261 struct pool_block *const b = pool->blocks;
263 if (b->ofs + amt <= BLOCK_SIZE)
265 p = ((char *) b) + b->ofs;
270 p = pool_alloc (pool, amt);
273 memcpy (p, string, amt);
277 /* Standard allocation routines. */
279 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
280 returns a pointer to the beginning of the block.
281 If POOL is a null pointer, then allocates a normal memory block
284 pool_malloc (struct pool *pool, size_t amt)
290 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
291 g->type = POOL_GIZMO_MALLOC;
294 return ((char *) g) + POOL_GIZMO_SIZE;
300 return xmalloc (amt);
303 /* Changes the allocation size of the specified memory block P managed
304 by POOL to AMT bytes and returns a pointer to the beginning of the
306 If POOL is a null pointer, then the block is reallocated in the
307 usual way with realloc(). */
309 pool_realloc (struct pool *pool, void *p, size_t amt)
317 struct pool_gizmo *g;
319 g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
320 amt + POOL_GIZMO_SIZE);
328 return ((char *) g) + POOL_GIZMO_SIZE;
337 return pool_malloc (pool, amt);
340 return xrealloc (p, amt);
343 /* Frees block P managed by POOL.
344 If POOL is a null pointer, then the block is freed as usual with
347 pool_free (struct pool *pool, void *p)
349 if (pool != NULL && p != NULL)
351 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
352 delete_gizmo (pool, g);
359 /* Gizmo allocations. */
361 /* Creates and returns a pool as a subpool of POOL.
362 The subpool will be destroyed automatically when POOL is destroyed.
363 It may also be destroyed explicitly in advance. */
365 pool_create_subpool (struct pool *pool)
367 struct pool *subpool;
368 struct pool_gizmo *g;
370 assert (pool != NULL);
371 subpool = pool_create ();
372 subpool->parent = pool;
374 g = (void *) (((char *) subpool) + subpool->blocks->ofs);
375 subpool->blocks->ofs += POOL_GIZMO_SIZE;
377 g->type = POOL_GIZMO_SUBPOOL;
378 g->p.subpool = subpool;
385 /* Opens file FILENAME with mode MODE and returns a handle to it
386 if successful or a null pointer if not.
387 The file will be closed automatically when POOL is destroyed, or it
388 may be closed explicitly in advance using pool_fclose. */
390 pool_fopen (struct pool *pool, const char *filename, const char *mode)
394 assert (pool && filename && mode);
395 f = fopen (filename, mode);
400 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
401 g->type = POOL_GIZMO_FILE;
409 /* Closes file FILE managed by POOL. */
411 pool_fclose (struct pool *pool, FILE *file)
413 assert (pool && file);
414 if (fclose (file) == EOF)
418 struct pool_gizmo *g;
420 for (g = pool->gizmos; g; g = g->next)
421 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
423 delete_gizmo (pool, g);
431 /* Registers FREE to be called with argument P.
432 P should be unique among those registered in POOL so that it can be
433 uniquely identified by pool_unregister().
434 If not unregistered, FREE will be called with argument P when POOL
437 pool_register (struct pool *pool, void (*free) (void *), void *p)
439 assert (pool && free && p);
442 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
443 g->type = POOL_GIZMO_REGISTERED;
444 g->p.registered.free = free;
445 g->p.registered.p = p;
450 /* Unregisters previously registered P from POOL.
451 Returns nonzero only if P was found to be registered in POOL. */
453 pool_unregister (struct pool *pool, void *p)
458 struct pool_gizmo *g;
460 for (g = pool->gizmos; g; g = g->next)
461 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
463 delete_gizmo (pool, g);
471 /* Partial freeing. */
473 /* Notes the state of POOL into MARK so that it may be restored
474 by a call to pool_release(). */
476 pool_mark (struct pool *pool, struct pool_mark *mark)
478 assert (pool && mark);
480 mark->block = pool->blocks;
481 mark->ofs = pool->blocks->ofs;
483 mark->serial = serial;
486 /* Restores to POOL the state recorded in MARK. */
488 pool_release (struct pool *pool, const struct pool_mark *mark)
490 assert (pool && mark);
493 struct pool_gizmo *cur, *next;
495 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
511 struct pool_block *cur, *next, *last;
513 last = pool->blocks->prev;
514 for (cur = pool->blocks; cur != mark->block; cur = next)
517 assert (next != cur);
523 last->next = pool->blocks = cur;
525 cur->ofs = mark->ofs;
529 /* Private functions. */
531 /* Adds GIZMO at the beginning of POOL's gizmo list. */
533 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
535 assert (pool && gizmo);
537 gizmo->next = pool->gizmos;
540 pool->gizmos->prev = gizmo;
541 pool->gizmos = gizmo;
543 gizmo->serial = serial++;
546 /* Removes GIZMO from POOL's gizmo list. */
548 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
550 assert (pool && gizmo);
553 gizmo->prev->next = gizmo->next;
555 pool->gizmos = gizmo->next;
557 gizmo->next->prev = gizmo->prev;
560 /* Frees any of GIZMO's internal state.
561 GIZMO's data must not be referenced after calling this function. */
563 free_gizmo (struct pool_gizmo *gizmo)
565 assert (gizmo != NULL);
569 case POOL_GIZMO_MALLOC:
572 case POOL_GIZMO_FILE:
573 fclose (gizmo->p.file); /* Ignore errors. */
575 case POOL_GIZMO_SUBPOOL:
576 gizmo->p.subpool->parent = NULL;
577 pool_destroy (gizmo->p.subpool);
579 case POOL_GIZMO_REGISTERED:
580 gizmo->p.registered.free (gizmo->p.registered.p);
587 /* Memory allocation. */
590 /* Allocates SIZE bytes of space using malloc(). Aborts if out of
593 xmalloc (size_t size)
605 /* Reallocates P to be SIZE bytes long using realloc(). Aborts if out
608 xrealloc (void *p, size_t size)
611 return xmalloc (size);
617 p = realloc (p, size);
624 /* Self-test routine. */
633 #define N_ITERATIONS 8192
636 /* Self-test routine.
637 This is not exhaustive, but it can be useful. */
639 main (int argc, char **argv)
644 seed = atoi (argv[1]);
646 seed = time (0) * 257 % 32768;
651 struct pool_mark m1, m2;
652 FILE *files[N_FILES];
656 printf ("Random number seed: %d\n", seed);
659 printf ("Creating pool...\n");
660 pool = pool_create ();
662 printf ("Marking pool state...\n");
663 pool_mark (pool, &m1);
665 printf (" Populating pool with random-sized small objects...\n");
666 for (i = 0; i < N_ITERATIONS; i++)
668 size_t size = rand () % MAX_SUBALLOC;
669 void *p = pool_alloc (pool, size);
673 printf (" Marking pool state...\n");
674 pool_mark (pool, &m2);
676 printf (" Populating pool with random-sized small "
677 "and large objects...\n");
678 for (i = 0; i < N_ITERATIONS; i++)
680 size_t size = rand () % (2 * MAX_SUBALLOC);
681 void *p = pool_alloc (pool, size);
685 printf (" Releasing pool state...\n");
686 pool_release (pool, &m2);
688 printf (" Populating pool with random objects and gizmos...\n");
689 for (i = 0; i < N_FILES; i++)
692 for (i = 0; i < N_ITERATIONS; i++)
694 int type = rand () % 32;
698 if (files[cur_file] != NULL
699 && EOF == pool_fclose (pool, files[cur_file]))
700 printf ("error on fclose: %s\n", strerror (errno));
702 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
704 if (++cur_file >= N_FILES)
708 pool_create_subpool (pool);
711 size_t size = rand () % (2 * MAX_SUBALLOC);
712 void *p = pool_alloc (pool, size);
717 printf ("Releasing pool state...\n");
718 pool_release (pool, &m1);
720 printf ("Destroying pool...\n");
727 #endif /* SELF_TEST */
731 compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"