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
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. */
60 struct pool_gizmo *prev;
61 struct pool_gizmo *next;
63 long serial; /* Serial number. */
64 int type; /* Type of this gizmo. */
66 /* Type-dependent info. */
69 FILE *file; /* POOL_GIZMO_FILE. */
70 struct pool *subpool; /* POOL_GIZMO_SUBPOOL. */
72 /* POOL_GIZMO_REGISTERED. */
75 void (*free) (void *p);
83 /* Rounds X up to the next multiple of Y. */
85 #define ROUND_UP(X, Y) \
86 (((X) + ((Y) - 1)) / (Y) * (Y))
89 /* Types that provide typically useful alignment sizes. */
98 /* This should be the alignment size used by malloc(). The size of
99 the union above is correct, if not optimal, in all known cases. */
100 #define ALIGN_SIZE sizeof (union align)
102 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
103 suballocation of blocks. This is useful under memory
104 debuggers like Checker or valgrind because it allows the
105 source location of bugs to be more accurately pinpointed.
107 On the other hand, if we're testing the library, then we want to
108 test the library's real functionality, not its crippled, slow,
109 simplified functionality. */
110 /*#define DISCRETE_BLOCKS 1*/
112 /* Size of each block allocated in the pool, in bytes.
113 Should be at least 1k. */
115 #define BLOCK_SIZE 1024
118 /* Maximum size of a suballocated block. Larger blocks are allocated
119 directly with malloc() to avoid memory wastage at the end of a
120 suballocation block. */
122 #define MAX_SUBALLOC 64
125 /* Sizes of some structures with alignment padding included. */
126 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
127 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
128 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
130 /* Serial number used to keep track of gizmos for mark/release. */
131 static long serial = 0;
134 static void add_gizmo (struct pool *, struct pool_gizmo *);
135 static void free_gizmo (struct pool_gizmo *);
136 static void free_all_gizmos (struct pool *pool);
137 static void delete_gizmo (struct pool *, struct pool_gizmo *);
138 static void check_gizmo (struct pool *, struct pool_gizmo *);
140 /* General routines. */
142 /* Creates and returns a new memory pool, which allows malloc()'d
143 blocks to be suballocated in a time- and space-efficient manner.
144 The entire contents of the memory pool are freed at once.
146 In addition, other objects can be associated with a memory pool.
147 These are released when the pool is destroyed. */
151 struct pool_block *block;
154 block = xmalloc (BLOCK_SIZE);
155 block->prev = block->next = block;
156 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
158 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
160 pool->blocks = block;
166 /* Creates a pool, allocates a block STRUCT_SIZE bytes in
167 length from it, stores the pool's address at offset
168 POOL_MEMBER_OFFSET within the block, and returns the allocated
171 Meant for use indirectly via pool_create_container(). */
173 pool_create_at_offset (size_t struct_size, size_t pool_member_offset)
178 assert (struct_size >= sizeof pool);
179 assert (pool_member_offset <= struct_size - sizeof pool);
181 pool = pool_create ();
182 struct_ = pool_alloc (pool, struct_size);
183 *(struct pool **) (struct_ + pool_member_offset) = pool;
187 /* Destroy the specified pool, including all subpools. */
189 pool_destroy (struct pool *pool)
194 /* Remove this pool from its parent's list of gizmos. */
196 delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
198 free_all_gizmos (pool);
200 /* Free all the memory. */
202 struct pool_block *cur, *next;
204 pool->blocks->prev->next = NULL;
205 for (cur = pool->blocks; cur; cur = next)
213 /* Release all the memory and gizmos in POOL.
214 Blocks are not given back with free() but kept for later
215 allocations. To give back memory, use a subpool instead. */
217 pool_clear (struct pool *pool)
219 free_all_gizmos (pool);
221 /* Zero out block sizes. */
223 struct pool_block *cur;
228 cur->ofs = POOL_BLOCK_SIZE;
229 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
231 cur->ofs += POOL_SIZE;
232 if (pool->parent != NULL)
233 cur->ofs += POOL_GIZMO_SIZE;
237 while (cur != pool->blocks);
241 /* Suballocation routines. */
243 /* Allocates a memory region AMT bytes in size from POOL and returns a
244 pointer to the region's start.
245 The region is properly aligned for storing any object. */
247 pool_alloc (struct pool *pool, size_t amt)
249 assert (pool != NULL);
254 #ifndef DISCRETE_BLOCKS
255 if (amt <= MAX_SUBALLOC)
257 /* If there is space in this block, take it. */
258 struct pool_block *b = pool->blocks;
259 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
260 if (b->ofs + amt <= BLOCK_SIZE)
262 void *const p = ((char *) b) + b->ofs;
267 /* No space in this block, so we must make other
269 if (b->next->ofs == 0)
271 /* The next block is empty. Use it. */
273 b->ofs = POOL_BLOCK_SIZE;
274 if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
279 /* Create a new block at the start of the list. */
280 b = xmalloc (BLOCK_SIZE);
281 b->next = pool->blocks;
282 b->prev = pool->blocks->prev;
283 b->ofs = POOL_BLOCK_SIZE;
284 pool->blocks->prev->next = b;
285 pool->blocks->prev = b;
289 /* Allocate space from B. */
291 return ((char *) b) + b->ofs - amt;
295 return pool_malloc (pool, amt);
298 /* Allocates a memory region AMT bytes in size from POOL and
299 returns a pointer to the region's start. The region is not
300 necessarily aligned, so it is most suitable for storing
303 pool_alloc_unaligned (struct pool *pool, size_t amt)
305 assert (pool != NULL);
307 #ifndef DISCRETE_BLOCKS
308 /* Strings need not be aligned on any boundary, but some
309 operations may be more efficient when they are. However,
310 that's only going to help with reasonably long strings. */
311 if (amt < ALIGN_SIZE)
317 struct pool_block *const b = pool->blocks;
319 if (b->ofs + amt <= BLOCK_SIZE)
321 void *p = ((char *) b) + b->ofs;
329 return pool_alloc (pool, amt);
332 /* Allocates a memory region N * S bytes in size from POOL and
333 returns a pointer to the region's start.
334 N must be nonnegative, S must be positive.
335 Terminates the program if the memory cannot be obtained,
336 including the case where N * S overflows the range of size_t. */
338 pool_nalloc (struct pool *pool, size_t n, size_t s)
340 if (xalloc_oversized (n, s))
342 return pool_alloc (pool, n * s);
345 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
346 returns the new copy. */
348 pool_clone (struct pool *pool, const void *buffer, size_t size)
350 void *block = pool_alloc (pool, size);
351 memcpy (block, buffer, size);
355 /* Allocates SIZE bytes of unaligned data in POOL, copies BUFFER
356 into it, and returns the new copy. */
358 pool_clone_unaligned (struct pool *pool, const void *buffer, size_t size)
360 void *block = pool_alloc_unaligned (pool, size);
361 memcpy (block, buffer, size);
365 /* Duplicates null-terminated STRING, within POOL, and returns a
366 pointer to the duplicate. For use only with strings, because
367 the returned pointere may not be aligned properly for other
370 pool_strdup (struct pool *pool, const char *string)
372 return pool_clone_unaligned (pool, string, strlen (string) + 1);
375 /* Standard allocation routines. */
377 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
378 returns a pointer to the beginning of the block.
379 If POOL is a null pointer, then allocates a normal memory block
382 pool_malloc (struct pool *pool, size_t amt)
388 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
389 g->type = POOL_GIZMO_MALLOC;
392 return ((char *) g) + POOL_GIZMO_SIZE;
398 return xmalloc (amt);
401 /* Allocates and returns N elements of S bytes each, to be
403 If POOL is a null pointer, then allocates a normal memory block
405 N must be nonnegative, S must be positive.
406 Terminates the program if the memory cannot be obtained,
407 including the case where N * S overflows the range of size_t. */
409 pool_nmalloc (struct pool *pool, size_t n, size_t s)
411 if (xalloc_oversized (n, s))
413 return pool_malloc (pool, n * s);
416 /* Changes the allocation size of the specified memory block P managed
417 by POOL to AMT bytes and returns a pointer to the beginning of the
419 If POOL is a null pointer, then the block is reallocated in the
420 usual way with realloc(). */
422 pool_realloc (struct pool *pool, void *p, size_t amt)
430 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
431 check_gizmo (pool, g);
433 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
440 check_gizmo (pool, g);
442 return ((char *) g) + POOL_GIZMO_SIZE;
451 return pool_malloc (pool, amt);
454 return xrealloc (p, amt);
457 /* Changes the allocation size of the specified memory block P
458 managed by POOL to N * S bytes and returns a pointer to the
459 beginning of the block.
460 N must be nonnegative, S must be positive.
461 If POOL is a null pointer, then the block is reallocated in
462 the usual way with xrealloc().
463 Terminates the program if the memory cannot be obtained,
464 including the case where N * S overflows the range of size_t. */
466 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
468 if (xalloc_oversized (n, s))
470 return pool_realloc (pool, p, n * s);
473 /* If P is null, allocate a block of at least *PN such objects;
474 otherwise, reallocate P so that it contains more than *PN
475 objects each of S bytes. *PN must be nonzero unless P is
476 null, and S must be nonzero. Set *PN to the new number of
477 objects, and return the pointer to the new block. *PN is
478 never set to zero, and the returned pointer is never null.
480 The block returned is managed by POOL. If POOL is a null
481 pointer, then the block is reallocated in the usual way with
484 Terminates the program if the memory cannot be obtained,
485 including the case where the memory required overflows the
488 Repeated reallocations are guaranteed to make progress, either by
489 allocating an initial block with a nonzero size, or by allocating a
492 In the following implementation, nonzero sizes are doubled so that
493 repeated reallocations have O(N log N) overall cost rather than
494 O(N**2) cost, but the specification for this function does not
495 guarantee that sizes are doubled.
497 Here is an example of use:
502 size_t allocated = 0;
505 append_int (int value)
507 if (used == allocated)
508 p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
512 This causes x2nrealloc to allocate a block of some nonzero size the
513 first time it is called.
515 To have finer-grained control over the initial size, set *PN to a
516 nonzero value before calling this function with P == NULL. For
522 size_t allocated = 0;
523 size_t allocated1 = 1000;
526 append_int (int value)
528 if (used == allocated)
530 p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
531 allocated = allocated1;
536 This function implementation is from gnulib. */
538 pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
546 /* The approximate size to use for initial small allocation
547 requests, when the invoking code specifies an old size of
548 zero. 64 bytes is the largest "small" request for the
549 GNU C library malloc. */
550 enum { DEFAULT_MXFAST = 64 };
552 n = DEFAULT_MXFAST / s;
558 if (SIZE_MAX / 2 / s < n)
564 return pool_realloc (pool, p, n * s);
567 /* Frees block P managed by POOL.
568 If POOL is a null pointer, then the block is freed as usual with
571 pool_free (struct pool *pool, void *p)
573 if (pool != NULL && p != NULL)
575 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
576 check_gizmo (pool, g);
577 delete_gizmo (pool, g);
584 /* Gizmo allocations. */
586 /* Creates and returns a pool as a subpool of POOL.
587 The subpool will be destroyed automatically when POOL is destroyed.
588 It may also be destroyed explicitly in advance. */
590 pool_create_subpool (struct pool *pool)
592 struct pool *subpool;
593 struct pool_gizmo *g;
595 assert (pool != NULL);
596 subpool = pool_create ();
597 subpool->parent = pool;
599 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
600 subpool->blocks->ofs += POOL_GIZMO_SIZE;
602 g->type = POOL_GIZMO_SUBPOOL;
603 g->p.subpool = subpool;
610 /* Makes SUBPOOL a subpool of POOL.
611 SUBPOOL must not already have a parent pool.
612 The subpool will be destroyed automatically when POOL is destroyed.
613 It may also be destroyed explicitly in advance. */
615 pool_add_subpool (struct pool *pool, struct pool *subpool)
617 struct pool_gizmo *g;
619 assert (pool != NULL);
620 assert (subpool != NULL);
621 assert (subpool->parent == NULL);
623 g = pool_alloc (subpool, sizeof *g);
624 g->type = POOL_GIZMO_SUBPOOL;
625 g->p.subpool = subpool;
628 subpool->parent = pool;
631 /* Opens file FILENAME with mode MODE and returns a handle to it
632 if successful or a null pointer if not.
633 The file will be closed automatically when POOL is destroyed, or it
634 may be closed explicitly in advance using pool_fclose. */
636 pool_fopen (struct pool *pool, const char *filename, const char *mode)
640 assert (pool && filename && mode);
641 f = fopen (filename, mode);
646 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
647 g->type = POOL_GIZMO_FILE;
655 /* Closes file FILE managed by POOL. */
657 pool_fclose (struct pool *pool, FILE *file)
659 assert (pool && file);
660 if (fclose (file) == EOF)
664 struct pool_gizmo *g;
666 for (g = pool->gizmos; g; g = g->next)
667 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
669 delete_gizmo (pool, g);
677 /* Registers FREE to be called with argument P.
678 P should be unique among those registered in POOL so that it can be
679 uniquely identified by pool_unregister().
680 If not unregistered, FREE will be called with argument P when POOL
683 pool_register (struct pool *pool, void (*free) (void *), void *p)
685 assert (pool && free && p);
688 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
689 g->type = POOL_GIZMO_REGISTERED;
690 g->p.registered.free = free;
691 g->p.registered.p = p;
696 /* Unregisters previously registered P from POOL.
697 Returns nonzero only if P was found to be registered in POOL. */
699 pool_unregister (struct pool *pool, void *p)
704 struct pool_gizmo *g;
706 for (g = pool->gizmos; g; g = g->next)
707 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
709 delete_gizmo (pool, g);
717 /* Partial freeing. */
719 /* Notes the state of POOL into MARK so that it may be restored
720 by a call to pool_release(). */
722 pool_mark (struct pool *pool, struct pool_mark *mark)
724 assert (pool && mark);
726 mark->block = pool->blocks;
727 mark->ofs = pool->blocks->ofs;
729 mark->serial = serial;
732 /* Restores to POOL the state recorded in MARK.
733 Emptied blocks are not given back with free() but kept for
734 later allocations. To get that behavior, use a subpool
737 pool_release (struct pool *pool, const struct pool_mark *mark)
739 assert (pool && mark);
742 struct pool_gizmo *cur, *next;
744 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
760 struct pool_block *cur;
762 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
764 cur->ofs = POOL_BLOCK_SIZE;
765 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
767 cur->ofs += POOL_SIZE;
768 if (pool->parent != NULL)
769 cur->ofs += POOL_GIZMO_SIZE;
772 pool->blocks = mark->block;
773 pool->blocks->ofs = mark->ofs;
777 /* Private functions. */
779 /* Adds GIZMO at the beginning of POOL's gizmo list. */
781 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
783 assert (pool && gizmo);
786 gizmo->next = pool->gizmos;
789 pool->gizmos->prev = gizmo;
790 pool->gizmos = gizmo;
792 gizmo->serial = serial++;
794 check_gizmo (pool, gizmo);
797 /* Removes GIZMO from POOL's gizmo list. */
799 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
801 assert (pool && gizmo);
803 check_gizmo (pool, gizmo);
806 gizmo->prev->next = gizmo->next;
808 pool->gizmos = gizmo->next;
810 gizmo->next->prev = gizmo->prev;
813 /* Frees any of GIZMO's internal state.
814 GIZMO's data must not be referenced after calling this function. */
816 free_gizmo (struct pool_gizmo *gizmo)
818 assert (gizmo != NULL);
822 case POOL_GIZMO_MALLOC:
825 case POOL_GIZMO_FILE:
826 fclose (gizmo->p.file); /* Ignore errors. */
828 case POOL_GIZMO_SUBPOOL:
829 gizmo->p.subpool->parent = NULL;
830 pool_destroy (gizmo->p.subpool);
832 case POOL_GIZMO_REGISTERED:
833 gizmo->p.registered.free (gizmo->p.registered.p);
840 /* Free all the gizmos in POOL. */
842 free_all_gizmos (struct pool *pool)
844 struct pool_gizmo *cur, *next;
846 for (cur = pool->gizmos; cur; cur = next)
855 check_gizmo (struct pool *p, struct pool_gizmo *g)
857 assert (g->pool == p);
858 assert (g->next == NULL || g->next->prev == g);
859 assert ((g->prev != NULL && g->prev->next == g)
860 || (g->prev == NULL && p->gizmos == g));
864 /* Self-test routine. */
872 #define N_ITERATIONS 8192
875 /* Self-test routine.
876 This is not exhaustive, but it can be useful. */
878 cmd_debug_pool (void)
880 int seed = time (0) * 257 % 32768;
885 struct pool_mark m1, m2;
886 FILE *files[N_FILES];
890 printf ("Random number seed: %d\n", seed);
893 printf ("Creating pool...\n");
894 pool = pool_create ();
896 printf ("Marking pool state...\n");
897 pool_mark (pool, &m1);
899 printf (" Populating pool with random-sized small objects...\n");
900 for (i = 0; i < N_ITERATIONS; i++)
902 size_t size = rand () % MAX_SUBALLOC;
903 void *p = pool_alloc (pool, size);
907 printf (" Marking pool state...\n");
908 pool_mark (pool, &m2);
910 printf (" Populating pool with random-sized small "
911 "and large objects...\n");
912 for (i = 0; i < N_ITERATIONS; i++)
914 size_t size = rand () % (2 * MAX_SUBALLOC);
915 void *p = pool_alloc (pool, size);
919 printf (" Releasing pool state...\n");
920 pool_release (pool, &m2);
922 printf (" Populating pool with random objects and gizmos...\n");
923 for (i = 0; i < N_FILES; i++)
926 for (i = 0; i < N_ITERATIONS; i++)
928 int type = rand () % 32;
932 if (files[cur_file] != NULL
933 && EOF == pool_fclose (pool, files[cur_file]))
934 printf ("error on fclose: %s\n", strerror (errno));
936 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
938 if (++cur_file >= N_FILES)
942 pool_create_subpool (pool);
945 size_t size = rand () % (2 * MAX_SUBALLOC);
946 void *p = pool_alloc (pool, size);
951 printf ("Releasing pool state...\n");
952 pool_release (pool, &m1);
954 printf ("Destroying pool...\n");