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., 51 Franklin Street, Fifth Floor, 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. */
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 /* Size of each block allocated in the pool, in bytes.
116 Should be at least 1k. */
118 #define BLOCK_SIZE 1024
121 /* Maximum size of a suballocated block. Larger blocks are allocated
122 directly with malloc() to avoid memory wastage at the end of a
123 suballocation block. */
125 #define MAX_SUBALLOC 64
128 /* Sizes of some structures with alignment padding included. */
129 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
130 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
131 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
133 /* Serial number used to keep track of gizmos for mark/release. */
134 static long serial = 0;
137 static void add_gizmo (struct pool *, struct pool_gizmo *);
138 static void free_gizmo (struct pool_gizmo *);
139 static void free_all_gizmos (struct pool *pool);
140 static void delete_gizmo (struct pool *, struct pool_gizmo *);
141 static void check_gizmo (struct pool *, struct pool_gizmo *);
143 /* General routines. */
145 /* Creates and returns a new memory pool, which allows malloc()'d
146 blocks to be suballocated in a time- and space-efficient manner.
147 The entire contents of the memory pool are freed at once.
149 In addition, other objects can be associated with a memory pool.
150 These are released when the pool is destroyed. */
154 struct pool_block *block;
157 block = xmalloc (BLOCK_SIZE);
158 block->prev = block->next = block;
159 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
161 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
163 pool->blocks = block;
169 /* Destroy the specified pool, including all subpools. */
171 pool_destroy (struct pool *pool)
176 /* Remove this pool from its parent's list of gizmos. */
178 delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
180 free_all_gizmos (pool);
182 /* Free all the memory. */
184 struct pool_block *cur, *next;
186 pool->blocks->prev->next = NULL;
187 for (cur = pool->blocks; cur; cur = next)
195 /* Release all the memory and gizmos in POOL.
196 Blocks are not given back with free() but kept for later
197 allocations. To give back memory, use a subpool instead. */
199 pool_clear (struct pool *pool)
201 free_all_gizmos (pool);
203 /* Zero out block sizes. */
205 struct pool_block *cur;
210 cur->ofs = POOL_BLOCK_SIZE;
211 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
213 cur->ofs += POOL_SIZE;
214 if (pool->parent != NULL)
215 cur->ofs += POOL_GIZMO_SIZE;
219 while (cur != pool->blocks);
223 /* Suballocation routines. */
225 /* Allocates a memory region AMT bytes in size from POOL and returns a
226 pointer to the region's start. */
228 pool_alloc (struct pool *pool, size_t amt)
230 assert (pool != NULL);
232 #ifndef DISCRETE_BLOCKS
233 if (amt <= MAX_SUBALLOC)
235 /* If there is space in this block, take it. */
236 struct pool_block *b = pool->blocks;
237 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
238 if (b->ofs + amt <= BLOCK_SIZE)
240 void *const p = ((char *) b) + b->ofs;
245 /* No space in this block, so we must make other
247 if (b->next->ofs == 0)
249 /* The next block is empty. Use it. */
251 b->ofs = POOL_BLOCK_SIZE;
252 if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
257 /* Create a new block at the start of the list. */
258 b = xmalloc (BLOCK_SIZE);
259 b->next = pool->blocks;
260 b->prev = pool->blocks->prev;
261 b->ofs = POOL_BLOCK_SIZE;
262 pool->blocks->prev->next = b;
263 pool->blocks->prev = b;
267 /* Allocate space from B. */
269 return ((char *) b) + b->ofs - amt;
273 return pool_malloc (pool, amt);
276 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
277 returns the new copy. */
279 pool_clone (struct pool *pool, const void *buffer, size_t size)
281 void *block = pool_alloc (pool, size);
282 memcpy (block, buffer, size);
286 /* Duplicates STRING, which has LENGTH characters, within POOL,
287 and returns a pointer to the duplicate. LENGTH should not
288 include the null terminator, which is always added to the
289 duplicate. For use only with strings, because the returned
290 pointere may not be aligned properly for other types. */
292 pool_strndup (struct pool *pool, const char *string, size_t length)
297 assert (pool && string);
300 /* Note that strings need not be aligned on any boundary. */
301 #ifndef DISCRETE_BLOCKS
303 struct pool_block *const b = pool->blocks;
305 if (b->ofs + size <= BLOCK_SIZE)
307 copy = ((char *) b) + b->ofs;
311 copy = pool_alloc (pool, size);
314 copy = pool_alloc (pool, size);
317 memcpy (copy, string, length);
322 /* Duplicates null-terminated STRING, within POOL, and returns a
323 pointer to the duplicate. For use only with strings, because
324 the returned pointere may not be aligned properly for other
327 pool_strdup (struct pool *pool, const char *string)
329 return pool_strndup (pool, string, strlen (string));
332 /* Standard allocation routines. */
334 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
335 returns a pointer to the beginning of the block.
336 If POOL is a null pointer, then allocates a normal memory block
339 pool_malloc (struct pool *pool, size_t amt)
345 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
346 g->type = POOL_GIZMO_MALLOC;
349 return ((char *) g) + POOL_GIZMO_SIZE;
355 return xmalloc (amt);
358 /* Changes the allocation size of the specified memory block P managed
359 by POOL to AMT bytes and returns a pointer to the beginning of the
361 If POOL is a null pointer, then the block is reallocated in the
362 usual way with realloc(). */
364 pool_realloc (struct pool *pool, void *p, size_t amt)
372 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
373 check_gizmo (pool, g);
375 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
382 check_gizmo (pool, g);
384 return ((char *) g) + POOL_GIZMO_SIZE;
393 return pool_malloc (pool, amt);
396 return xrealloc (p, amt);
399 /* Frees block P managed by POOL.
400 If POOL is a null pointer, then the block is freed as usual with
403 pool_free (struct pool *pool, void *p)
405 if (pool != NULL && p != NULL)
407 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
408 check_gizmo (pool, g);
409 delete_gizmo (pool, g);
416 /* Gizmo allocations. */
418 /* Creates and returns a pool as a subpool of POOL.
419 The subpool will be destroyed automatically when POOL is destroyed.
420 It may also be destroyed explicitly in advance. */
422 pool_create_subpool (struct pool *pool)
424 struct pool *subpool;
425 struct pool_gizmo *g;
427 assert (pool != NULL);
428 subpool = pool_create ();
429 subpool->parent = pool;
431 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
432 subpool->blocks->ofs += POOL_GIZMO_SIZE;
434 g->type = POOL_GIZMO_SUBPOOL;
435 g->p.subpool = subpool;
442 /* Opens file FILENAME with mode MODE and returns a handle to it
443 if successful or a null pointer if not.
444 The file will be closed automatically when POOL is destroyed, or it
445 may be closed explicitly in advance using pool_fclose. */
447 pool_fopen (struct pool *pool, const char *filename, const char *mode)
451 assert (pool && filename && mode);
452 f = fopen (filename, mode);
457 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
458 g->type = POOL_GIZMO_FILE;
466 /* Closes file FILE managed by POOL. */
468 pool_fclose (struct pool *pool, FILE *file)
470 assert (pool && file);
471 if (fclose (file) == EOF)
475 struct pool_gizmo *g;
477 for (g = pool->gizmos; g; g = g->next)
478 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
480 delete_gizmo (pool, g);
488 /* Registers FREE to be called with argument P.
489 P should be unique among those registered in POOL so that it can be
490 uniquely identified by pool_unregister().
491 If not unregistered, FREE will be called with argument P when POOL
494 pool_register (struct pool *pool, void (*free) (void *), void *p)
496 assert (pool && free && p);
499 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
500 g->type = POOL_GIZMO_REGISTERED;
501 g->p.registered.free = free;
502 g->p.registered.p = p;
507 /* Unregisters previously registered P from POOL.
508 Returns nonzero only if P was found to be registered in POOL. */
510 pool_unregister (struct pool *pool, void *p)
515 struct pool_gizmo *g;
517 for (g = pool->gizmos; g; g = g->next)
518 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
520 delete_gizmo (pool, g);
528 /* Partial freeing. */
530 /* Notes the state of POOL into MARK so that it may be restored
531 by a call to pool_release(). */
533 pool_mark (struct pool *pool, struct pool_mark *mark)
535 assert (pool && mark);
537 mark->block = pool->blocks;
538 mark->ofs = pool->blocks->ofs;
540 mark->serial = serial;
543 /* Restores to POOL the state recorded in MARK.
544 Emptied blocks are not given back with free() but kept for
545 later allocations. To get that behavior, use a subpool
548 pool_release (struct pool *pool, const struct pool_mark *mark)
550 assert (pool && mark);
553 struct pool_gizmo *cur, *next;
555 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
571 struct pool_block *cur;
573 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
575 cur->ofs = POOL_BLOCK_SIZE;
576 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
578 cur->ofs += POOL_SIZE;
579 if (pool->parent != NULL)
580 cur->ofs += POOL_GIZMO_SIZE;
583 pool->blocks = mark->block;
584 pool->blocks->ofs = mark->ofs;
588 /* Private functions. */
590 /* Adds GIZMO at the beginning of POOL's gizmo list. */
592 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
594 assert (pool && gizmo);
597 gizmo->next = pool->gizmos;
600 pool->gizmos->prev = gizmo;
601 pool->gizmos = gizmo;
603 gizmo->serial = serial++;
605 check_gizmo (pool, gizmo);
608 /* Removes GIZMO from POOL's gizmo list. */
610 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
612 assert (pool && gizmo);
614 check_gizmo (pool, gizmo);
617 gizmo->prev->next = gizmo->next;
619 pool->gizmos = gizmo->next;
621 gizmo->next->prev = gizmo->prev;
624 /* Frees any of GIZMO's internal state.
625 GIZMO's data must not be referenced after calling this function. */
627 free_gizmo (struct pool_gizmo *gizmo)
629 assert (gizmo != NULL);
633 case POOL_GIZMO_MALLOC:
636 case POOL_GIZMO_FILE:
637 fclose (gizmo->p.file); /* Ignore errors. */
639 case POOL_GIZMO_SUBPOOL:
640 gizmo->p.subpool->parent = NULL;
641 pool_destroy (gizmo->p.subpool);
643 case POOL_GIZMO_REGISTERED:
644 gizmo->p.registered.free (gizmo->p.registered.p);
651 /* Free all the gizmos in POOL. */
653 free_all_gizmos (struct pool *pool)
655 struct pool_gizmo *cur, *next;
657 for (cur = pool->gizmos; cur; cur = next)
666 check_gizmo (struct pool *p, struct pool_gizmo *g)
668 assert (g->pool == p);
669 assert (g->next == NULL || g->next->prev == g);
670 assert ((g->prev != NULL && g->prev->next == g)
671 || (g->prev == NULL && p->gizmos == g));
675 /* Self-test routine. */
683 #define N_ITERATIONS 8192
686 /* Self-test routine.
687 This is not exhaustive, but it can be useful. */
689 cmd_debug_pool (void)
691 int seed = time (0) * 257 % 32768;
696 struct pool_mark m1, m2;
697 FILE *files[N_FILES];
701 printf ("Random number seed: %d\n", seed);
704 printf ("Creating pool...\n");
705 pool = pool_create ();
707 printf ("Marking pool state...\n");
708 pool_mark (pool, &m1);
710 printf (" Populating pool with random-sized small objects...\n");
711 for (i = 0; i < N_ITERATIONS; i++)
713 size_t size = rand () % MAX_SUBALLOC;
714 void *p = pool_alloc (pool, size);
718 printf (" Marking pool state...\n");
719 pool_mark (pool, &m2);
721 printf (" Populating pool with random-sized small "
722 "and large objects...\n");
723 for (i = 0; i < N_ITERATIONS; i++)
725 size_t size = rand () % (2 * MAX_SUBALLOC);
726 void *p = pool_alloc (pool, size);
730 printf (" Releasing pool state...\n");
731 pool_release (pool, &m2);
733 printf (" Populating pool with random objects and gizmos...\n");
734 for (i = 0; i < N_FILES; i++)
737 for (i = 0; i < N_ITERATIONS; i++)
739 int type = rand () % 32;
743 if (files[cur_file] != NULL
744 && EOF == pool_fclose (pool, files[cur_file]))
745 printf ("error on fclose: %s\n", strerror (errno));
747 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
749 if (++cur_file >= N_FILES)
753 pool_create_subpool (pool);
756 size_t size = rand () % (2 * MAX_SUBALLOC);
757 void *p = pool_alloc (pool, size);
762 printf ("Releasing pool state...\n");
763 pool_release (pool, &m1);
765 printf ("Destroying pool...\n");