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 suballocation
106 of blocks. This is useful under memory debuggers like Checker
107 because it allows the source location of bugs to be more accurately
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 #if __CHECKER__ && !SELF_TEST
114 #define DISCRETE_BLOCKS 1
117 /* Enable debug code if appropriate. */
123 /* Size of each block allocated in the pool, in bytes.
124 Should be at least 1k. */
126 #define BLOCK_SIZE 1024
129 /* Maximum size of a suballocated block. Larger blocks are allocated
130 directly with malloc() to avoid memory wastage at the end of a
131 suballocation block. */
133 #define MAX_SUBALLOC 64
136 /* Sizes of some structures with alignment padding included. */
137 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
138 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
139 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
141 /* Serial number used to keep track of gizmos for mark/release. */
142 static long serial = 0;
145 static void add_gizmo (struct pool *, struct pool_gizmo *);
146 static void free_gizmo (struct pool_gizmo *);
147 static void delete_gizmo (struct pool *, struct pool_gizmo *);
150 static void *xmalloc (size_t);
151 static void *xrealloc (void *, size_t);
154 /* General routines. */
156 /* Creates and returns a new memory pool, which allows malloc()'d
157 blocks to be suballocated in a time- and space-efficient manner.
158 The entire contents of the memory pool are freed at once.
160 In addition, other objects can be associated with a memory pool.
161 These are released when the pool is destroyed. */
165 struct pool_block *block;
168 block = xmalloc (BLOCK_SIZE);
169 block->prev = block->next = block;
170 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
172 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
174 pool->blocks = block;
180 /* Destroy the specified pool, including all subpools. */
182 pool_destroy (struct pool *pool)
189 (void *) (((char *) pool) + POOL_SIZE + POOL_BLOCK_SIZE));
192 struct pool_gizmo *cur, *next;
194 for (cur = pool->gizmos; cur; cur = next)
202 struct pool_block *cur, *next;
204 pool->blocks->prev->next = NULL;
205 for (cur = pool->blocks; cur; cur = next)
213 /* Suballocation routines. */
215 /* Allocates a memory region AMT bytes in size from POOL and returns a
216 pointer to the region's start. */
218 pool_alloc (struct pool *pool, size_t amt)
220 assert (pool != NULL);
222 #if !DISCRETE_BLOCKS /* Help identify source of bugs for Checker users. */
223 if (amt <= MAX_SUBALLOC)
225 struct pool_block *b = pool->blocks;
226 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
227 if (b->ofs + amt <= BLOCK_SIZE)
229 void *const p = ((char *) b) + b->ofs;
234 b = xmalloc (BLOCK_SIZE);
235 b->next = pool->blocks;
236 b->prev = pool->blocks->prev;
237 b->ofs = POOL_BLOCK_SIZE + amt;
239 pool->blocks->prev->next = b;
240 pool->blocks = pool->blocks->prev = b;
242 return ((char *) b) + POOL_BLOCK_SIZE;
245 #endif /* !DISCRETE_BLOCKS */
246 return pool_malloc (pool, amt);
249 /* Duplicates STRING within POOL and returns a pointer to the
252 pool_strdup (struct pool *pool, const char *string)
257 assert (pool && string);
258 amt = strlen (string) + 1;
260 /* Note that strings need not be aligned on any boundary. */
263 struct pool_block *const b = pool->blocks;
265 if (b->ofs + amt <= BLOCK_SIZE)
267 p = ((char *) b) + b->ofs;
272 p = pool_alloc (pool, amt);
275 memcpy (p, string, amt);
279 /* Standard allocation routines. */
281 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
282 returns a pointer to the beginning of the block.
283 If POOL is a null pointer, then allocates a normal memory block
286 pool_malloc (struct pool *pool, size_t amt)
292 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
293 g->type = POOL_GIZMO_MALLOC;
296 return ((char *) g) + POOL_GIZMO_SIZE;
302 return xmalloc (amt);
305 /* Changes the allocation size of the specified memory block P managed
306 by POOL to AMT bytes and returns a pointer to the beginning of the
308 If POOL is a null pointer, then the block is reallocated in the
309 usual way with realloc(). */
311 pool_realloc (struct pool *pool, void *p, size_t amt)
319 struct pool_gizmo *g;
321 g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
322 amt + POOL_GIZMO_SIZE);
330 return ((char *) g) + POOL_GIZMO_SIZE;
339 return pool_malloc (pool, amt);
342 return xrealloc (p, amt);
345 /* Frees block P managed by POOL.
346 If POOL is a null pointer, then the block is freed as usual with
349 pool_free (struct pool *pool, void *p)
351 if (pool != NULL && p != NULL)
353 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
354 delete_gizmo (pool, g);
361 /* Gizmo allocations. */
363 /* Creates and returns a pool as a subpool of POOL.
364 The subpool will be destroyed automatically when POOL is destroyed.
365 It may also be destroyed explicitly in advance. */
367 pool_create_subpool (struct pool *pool)
369 struct pool *subpool;
370 struct pool_gizmo *g;
372 assert (pool != NULL);
373 subpool = pool_create ();
374 subpool->parent = pool;
376 g = (void *) (((char *) subpool) + subpool->blocks->ofs);
377 subpool->blocks->ofs += POOL_GIZMO_SIZE;
379 g->type = POOL_GIZMO_SUBPOOL;
380 g->p.subpool = subpool;
387 /* Opens file FILENAME with mode MODE and returns a handle to it
388 if successful or a null pointer if not.
389 The file will be closed automatically when POOL is destroyed, or it
390 may be closed explicitly in advance using pool_fclose. */
392 pool_fopen (struct pool *pool, const char *filename, const char *mode)
396 assert (pool && filename && mode);
397 f = fopen (filename, mode);
402 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
403 g->type = POOL_GIZMO_FILE;
411 /* Closes file FILE managed by POOL. */
413 pool_fclose (struct pool *pool, FILE *file)
415 assert (pool && file);
416 if (fclose (file) == EOF)
420 struct pool_gizmo *g;
422 for (g = pool->gizmos; g; g = g->next)
423 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
425 delete_gizmo (pool, g);
433 /* Registers FREE to be called with argument P.
434 P should be unique among those registered in POOL so that it can be
435 uniquely identified by pool_unregister().
436 If not unregistered, FREE will be called with argument P when POOL
439 pool_register (struct pool *pool, void (*free) (void *), void *p)
441 assert (pool && free && p);
444 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
445 g->type = POOL_GIZMO_REGISTERED;
446 g->p.registered.free = free;
447 g->p.registered.p = p;
452 /* Unregisters previously registered P from POOL.
453 Returns nonzero only if P was found to be registered in POOL. */
455 pool_unregister (struct pool *pool, void *p)
460 struct pool_gizmo *g;
462 for (g = pool->gizmos; g; g = g->next)
463 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
465 delete_gizmo (pool, g);
473 /* Partial freeing. */
475 /* Notes the state of POOL into MARK so that it may be restored
476 by a call to pool_release(). */
478 pool_mark (struct pool *pool, struct pool_mark *mark)
480 assert (pool && mark);
482 mark->block = pool->blocks;
483 mark->ofs = pool->blocks->ofs;
485 mark->serial = serial;
488 /* Restores to POOL the state recorded in MARK. */
490 pool_release (struct pool *pool, const struct pool_mark *mark)
492 assert (pool && mark);
495 struct pool_gizmo *cur, *next;
497 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
513 struct pool_block *cur, *next, *last;
515 last = pool->blocks->prev;
516 for (cur = pool->blocks; cur != mark->block; cur = next)
519 assert (next != cur);
525 last->next = pool->blocks = cur;
527 cur->ofs = mark->ofs;
531 /* Private functions. */
533 /* Adds GIZMO at the beginning of POOL's gizmo list. */
535 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
537 assert (pool && gizmo);
539 gizmo->next = pool->gizmos;
542 pool->gizmos->prev = gizmo;
543 pool->gizmos = gizmo;
545 gizmo->serial = serial++;
548 /* Removes GIZMO from POOL's gizmo list. */
550 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
552 assert (pool && gizmo);
555 gizmo->prev->next = gizmo->next;
557 pool->gizmos = gizmo->next;
559 gizmo->next->prev = gizmo->prev;
562 /* Frees any of GIZMO's internal state.
563 GIZMO's data must not be referenced after calling this function. */
565 free_gizmo (struct pool_gizmo *gizmo)
567 assert (gizmo != NULL);
571 case POOL_GIZMO_MALLOC:
574 case POOL_GIZMO_FILE:
575 fclose (gizmo->p.file); /* Ignore errors. */
577 case POOL_GIZMO_SUBPOOL:
578 gizmo->p.subpool->parent = NULL;
579 pool_destroy (gizmo->p.subpool);
581 case POOL_GIZMO_REGISTERED:
582 gizmo->p.registered.free (gizmo->p.registered.p);
589 /* Memory allocation. */
592 /* Allocates SIZE bytes of space using malloc(). Aborts if out of
595 xmalloc (size_t size)
607 /* Reallocates P to be SIZE bytes long using realloc(). Aborts if out
610 xrealloc (void *p, size_t size)
613 return xmalloc (size);
619 p = realloc (p, size);
626 /* Self-test routine. */
635 #define N_ITERATIONS 8192
638 /* Self-test routine.
639 This is not exhaustive, but it can be useful. */
641 main (int argc, char **argv)
646 seed = atoi (argv[1]);
648 seed = time (0) * 257 % 32768;
653 struct pool_mark m1, m2;
654 FILE *files[N_FILES];
658 printf ("Random number seed: %d\n", seed);
661 printf ("Creating pool...\n");
662 pool = pool_create ();
664 printf ("Marking pool state...\n");
665 pool_mark (pool, &m1);
667 printf (" Populating pool with random-sized small objects...\n");
668 for (i = 0; i < N_ITERATIONS; i++)
670 size_t size = rand () % MAX_SUBALLOC;
671 void *p = pool_alloc (pool, size);
675 printf (" Marking pool state...\n");
676 pool_mark (pool, &m2);
678 printf (" Populating pool with random-sized small "
679 "and large objects...\n");
680 for (i = 0; i < N_ITERATIONS; i++)
682 size_t size = rand () % (2 * MAX_SUBALLOC);
683 void *p = pool_alloc (pool, size);
687 printf (" Releasing pool state...\n");
688 pool_release (pool, &m2);
690 printf (" Populating pool with random objects and gizmos...\n");
691 for (i = 0; i < N_FILES; i++)
694 for (i = 0; i < N_ITERATIONS; i++)
696 int type = rand () % 32;
700 if (files[cur_file] != NULL
701 && EOF == pool_fclose (pool, files[cur_file]))
702 printf ("error on fclose: %s\n", strerror (errno));
704 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
706 if (++cur_file >= N_FILES)
710 pool_create_subpool (pool);
713 size_t size = rand () % (2 * MAX_SUBALLOC);
714 void *p = pool_alloc (pool, size);
719 printf ("Releasing pool state...\n");
720 pool_release (pool, &m1);
722 printf ("Destroying pool...\n");
729 #endif /* SELF_TEST */
733 compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"