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 a memory region N * S bytes in size from POOL and
277 returns a pointer to the region's start.
278 N must be nonnegative, S must be positive.
279 Terminates the program if the memory cannot be obtained,
280 including the case where N * S overflows the range of size_t. */
282 pool_nalloc (struct pool *pool, size_t n, size_t s)
284 if (xalloc_oversized (n, s))
286 return pool_alloc (pool, n * s);
289 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
290 returns the new copy. */
292 pool_clone (struct pool *pool, const void *buffer, size_t size)
294 void *block = pool_alloc (pool, size);
295 memcpy (block, buffer, size);
299 /* Duplicates STRING, which has LENGTH characters, within POOL,
300 and returns a pointer to the duplicate. LENGTH should not
301 include the null terminator, which is always added to the
302 duplicate. For use only with strings, because the returned
303 pointere may not be aligned properly for other types. */
305 pool_strndup (struct pool *pool, const char *string, size_t length)
310 assert (pool && string);
313 /* Note that strings need not be aligned on any boundary. */
314 #ifndef DISCRETE_BLOCKS
316 struct pool_block *const b = pool->blocks;
318 if (b->ofs + size <= BLOCK_SIZE)
320 copy = ((char *) b) + b->ofs;
324 copy = pool_alloc (pool, size);
327 copy = pool_alloc (pool, size);
330 memcpy (copy, string, length);
335 /* Duplicates null-terminated STRING, within POOL, and returns a
336 pointer to the duplicate. For use only with strings, because
337 the returned pointere may not be aligned properly for other
340 pool_strdup (struct pool *pool, const char *string)
342 return pool_strndup (pool, string, strlen (string));
345 /* Standard allocation routines. */
347 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
348 returns a pointer to the beginning of the block.
349 If POOL is a null pointer, then allocates a normal memory block
352 pool_malloc (struct pool *pool, size_t amt)
358 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
359 g->type = POOL_GIZMO_MALLOC;
362 return ((char *) g) + POOL_GIZMO_SIZE;
368 return xmalloc (amt);
371 /* Allocates and returns N elements of S bytes each, to be
373 If POOL is a null pointer, then allocates a normal memory block
375 N must be nonnegative, S must be positive.
376 Terminates the program if the memory cannot be obtained,
377 including the case where N * S overflows the range of size_t. */
379 pool_nmalloc (struct pool *pool, size_t n, size_t s)
381 if (xalloc_oversized (n, s))
383 return pool_malloc (pool, n * s);
386 /* Changes the allocation size of the specified memory block P managed
387 by POOL to AMT bytes and returns a pointer to the beginning of the
389 If POOL is a null pointer, then the block is reallocated in the
390 usual way with realloc(). */
392 pool_realloc (struct pool *pool, void *p, size_t amt)
400 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
401 check_gizmo (pool, g);
403 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
410 check_gizmo (pool, g);
412 return ((char *) g) + POOL_GIZMO_SIZE;
421 return pool_malloc (pool, amt);
424 return xrealloc (p, amt);
427 /* Changes the allocation size of the specified memory block P
428 managed by POOL to N * S bytes and returns a pointer to the
429 beginning of the block.
430 N must be nonnegative, S must be positive.
431 If POOL is a null pointer, then the block is reallocated in
432 the usual way with xrealloc().
433 Terminates the program if the memory cannot be obtained,
434 including the case where N * S overflows the range of size_t. */
436 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
438 if (xalloc_oversized (n, s))
440 return pool_realloc (pool, p, n * s);
443 /* Frees block P managed by POOL.
444 If POOL is a null pointer, then the block is freed as usual with
447 pool_free (struct pool *pool, void *p)
449 if (pool != NULL && p != NULL)
451 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
452 check_gizmo (pool, g);
453 delete_gizmo (pool, g);
460 /* Gizmo allocations. */
462 /* Creates and returns a pool as a subpool of POOL.
463 The subpool will be destroyed automatically when POOL is destroyed.
464 It may also be destroyed explicitly in advance. */
466 pool_create_subpool (struct pool *pool)
468 struct pool *subpool;
469 struct pool_gizmo *g;
471 assert (pool != NULL);
472 subpool = pool_create ();
473 subpool->parent = pool;
475 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
476 subpool->blocks->ofs += POOL_GIZMO_SIZE;
478 g->type = POOL_GIZMO_SUBPOOL;
479 g->p.subpool = subpool;
486 /* Opens file FILENAME with mode MODE and returns a handle to it
487 if successful or a null pointer if not.
488 The file will be closed automatically when POOL is destroyed, or it
489 may be closed explicitly in advance using pool_fclose. */
491 pool_fopen (struct pool *pool, const char *filename, const char *mode)
495 assert (pool && filename && mode);
496 f = fopen (filename, mode);
501 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
502 g->type = POOL_GIZMO_FILE;
510 /* Closes file FILE managed by POOL. */
512 pool_fclose (struct pool *pool, FILE *file)
514 assert (pool && file);
515 if (fclose (file) == EOF)
519 struct pool_gizmo *g;
521 for (g = pool->gizmos; g; g = g->next)
522 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
524 delete_gizmo (pool, g);
532 /* Registers FREE to be called with argument P.
533 P should be unique among those registered in POOL so that it can be
534 uniquely identified by pool_unregister().
535 If not unregistered, FREE will be called with argument P when POOL
538 pool_register (struct pool *pool, void (*free) (void *), void *p)
540 assert (pool && free && p);
543 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
544 g->type = POOL_GIZMO_REGISTERED;
545 g->p.registered.free = free;
546 g->p.registered.p = p;
551 /* Unregisters previously registered P from POOL.
552 Returns nonzero only if P was found to be registered in POOL. */
554 pool_unregister (struct pool *pool, void *p)
559 struct pool_gizmo *g;
561 for (g = pool->gizmos; g; g = g->next)
562 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
564 delete_gizmo (pool, g);
572 /* Partial freeing. */
574 /* Notes the state of POOL into MARK so that it may be restored
575 by a call to pool_release(). */
577 pool_mark (struct pool *pool, struct pool_mark *mark)
579 assert (pool && mark);
581 mark->block = pool->blocks;
582 mark->ofs = pool->blocks->ofs;
584 mark->serial = serial;
587 /* Restores to POOL the state recorded in MARK.
588 Emptied blocks are not given back with free() but kept for
589 later allocations. To get that behavior, use a subpool
592 pool_release (struct pool *pool, const struct pool_mark *mark)
594 assert (pool && mark);
597 struct pool_gizmo *cur, *next;
599 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
615 struct pool_block *cur;
617 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
619 cur->ofs = POOL_BLOCK_SIZE;
620 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
622 cur->ofs += POOL_SIZE;
623 if (pool->parent != NULL)
624 cur->ofs += POOL_GIZMO_SIZE;
627 pool->blocks = mark->block;
628 pool->blocks->ofs = mark->ofs;
632 /* Private functions. */
634 /* Adds GIZMO at the beginning of POOL's gizmo list. */
636 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
638 assert (pool && gizmo);
641 gizmo->next = pool->gizmos;
644 pool->gizmos->prev = gizmo;
645 pool->gizmos = gizmo;
647 gizmo->serial = serial++;
649 check_gizmo (pool, gizmo);
652 /* Removes GIZMO from POOL's gizmo list. */
654 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
656 assert (pool && gizmo);
658 check_gizmo (pool, gizmo);
661 gizmo->prev->next = gizmo->next;
663 pool->gizmos = gizmo->next;
665 gizmo->next->prev = gizmo->prev;
668 /* Frees any of GIZMO's internal state.
669 GIZMO's data must not be referenced after calling this function. */
671 free_gizmo (struct pool_gizmo *gizmo)
673 assert (gizmo != NULL);
677 case POOL_GIZMO_MALLOC:
680 case POOL_GIZMO_FILE:
681 fclose (gizmo->p.file); /* Ignore errors. */
683 case POOL_GIZMO_SUBPOOL:
684 gizmo->p.subpool->parent = NULL;
685 pool_destroy (gizmo->p.subpool);
687 case POOL_GIZMO_REGISTERED:
688 gizmo->p.registered.free (gizmo->p.registered.p);
695 /* Free all the gizmos in POOL. */
697 free_all_gizmos (struct pool *pool)
699 struct pool_gizmo *cur, *next;
701 for (cur = pool->gizmos; cur; cur = next)
710 check_gizmo (struct pool *p, struct pool_gizmo *g)
712 assert (g->pool == p);
713 assert (g->next == NULL || g->next->prev == g);
714 assert ((g->prev != NULL && g->prev->next == g)
715 || (g->prev == NULL && p->gizmos == g));
719 /* Self-test routine. */
727 #define N_ITERATIONS 8192
730 /* Self-test routine.
731 This is not exhaustive, but it can be useful. */
733 cmd_debug_pool (void)
735 int seed = time (0) * 257 % 32768;
740 struct pool_mark m1, m2;
741 FILE *files[N_FILES];
745 printf ("Random number seed: %d\n", seed);
748 printf ("Creating pool...\n");
749 pool = pool_create ();
751 printf ("Marking pool state...\n");
752 pool_mark (pool, &m1);
754 printf (" Populating pool with random-sized small objects...\n");
755 for (i = 0; i < N_ITERATIONS; i++)
757 size_t size = rand () % MAX_SUBALLOC;
758 void *p = pool_alloc (pool, size);
762 printf (" Marking pool state...\n");
763 pool_mark (pool, &m2);
765 printf (" Populating pool with random-sized small "
766 "and large objects...\n");
767 for (i = 0; i < N_ITERATIONS; i++)
769 size_t size = rand () % (2 * MAX_SUBALLOC);
770 void *p = pool_alloc (pool, size);
774 printf (" Releasing pool state...\n");
775 pool_release (pool, &m2);
777 printf (" Populating pool with random objects and gizmos...\n");
778 for (i = 0; i < N_FILES; i++)
781 for (i = 0; i < N_ITERATIONS; i++)
783 int type = rand () % 32;
787 if (files[cur_file] != NULL
788 && EOF == pool_fclose (pool, files[cur_file]))
789 printf ("error on fclose: %s\n", strerror (errno));
791 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
793 if (++cur_file >= N_FILES)
797 pool_create_subpool (pool);
800 size_t size = rand () % (2 * MAX_SUBALLOC);
801 void *p = pool_alloc (pool, size);
806 printf ("Releasing pool state...\n");
807 pool_release (pool, &m1);
809 printf ("Destroying pool...\n");