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 #if defined (i386) || defined (__i386__)
101 #define ALIGN_SIZE 4 /* Save some extra memory. */
103 #define ALIGN_SIZE sizeof (union align)
106 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
107 suballocation of blocks. This is useful under memory
108 debuggers like Checker or valgrind because it allows the
109 source location of bugs to be more accurately pinpointed.
111 On the other hand, if we're testing the library, then we want to
112 test the library's real functionality, not its crippled, slow,
113 simplified functionality. */
114 /*#define DISCRETE_BLOCKS 1*/
116 /* Size of each block allocated in the pool, in bytes.
117 Should be at least 1k. */
119 #define BLOCK_SIZE 1024
122 /* Maximum size of a suballocated block. Larger blocks are allocated
123 directly with malloc() to avoid memory wastage at the end of a
124 suballocation block. */
126 #define MAX_SUBALLOC 64
129 /* Sizes of some structures with alignment padding included. */
130 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
131 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
132 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
134 /* Serial number used to keep track of gizmos for mark/release. */
135 static long serial = 0;
138 static void add_gizmo (struct pool *, struct pool_gizmo *);
139 static void free_gizmo (struct pool_gizmo *);
140 static void free_all_gizmos (struct pool *pool);
141 static void delete_gizmo (struct pool *, struct pool_gizmo *);
142 static void check_gizmo (struct pool *, struct pool_gizmo *);
144 /* General routines. */
146 /* Creates and returns a new memory pool, which allows malloc()'d
147 blocks to be suballocated in a time- and space-efficient manner.
148 The entire contents of the memory pool are freed at once.
150 In addition, other objects can be associated with a memory pool.
151 These are released when the pool is destroyed. */
155 struct pool_block *block;
158 block = xmalloc (BLOCK_SIZE);
159 block->prev = block->next = block;
160 block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
162 pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
164 pool->blocks = block;
170 /* Creates a pool, allocates a block STRUCT_SIZE bytes in
171 length from it, stores the pool's address at offset
172 POOL_MEMBER_OFFSET within the block, and returns the allocated
175 Meant for use indirectly via pool_create_container(). */
177 pool_create_at_offset (size_t struct_size, size_t pool_member_offset)
182 assert (struct_size >= sizeof pool);
183 assert (pool_member_offset <= struct_size - sizeof pool);
185 pool = pool_create ();
186 struct_ = pool_alloc (pool, struct_size);
187 *(struct pool **) (struct_ + pool_member_offset) = pool;
191 /* Destroy the specified pool, including all subpools. */
193 pool_destroy (struct pool *pool)
198 /* Remove this pool from its parent's list of gizmos. */
200 delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
202 free_all_gizmos (pool);
204 /* Free all the memory. */
206 struct pool_block *cur, *next;
208 pool->blocks->prev->next = NULL;
209 for (cur = pool->blocks; cur; cur = next)
217 /* Release all the memory and gizmos in POOL.
218 Blocks are not given back with free() but kept for later
219 allocations. To give back memory, use a subpool instead. */
221 pool_clear (struct pool *pool)
223 free_all_gizmos (pool);
225 /* Zero out block sizes. */
227 struct pool_block *cur;
232 cur->ofs = POOL_BLOCK_SIZE;
233 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
235 cur->ofs += POOL_SIZE;
236 if (pool->parent != NULL)
237 cur->ofs += POOL_GIZMO_SIZE;
241 while (cur != pool->blocks);
245 /* Suballocation routines. */
247 /* Allocates a memory region AMT bytes in size from POOL and returns a
248 pointer to the region's start. */
250 pool_alloc (struct pool *pool, size_t amt)
252 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 N * S bytes in size from POOL and
299 returns a pointer to the region's start.
300 N must be nonnegative, S must be positive.
301 Terminates the program if the memory cannot be obtained,
302 including the case where N * S overflows the range of size_t. */
304 pool_nalloc (struct pool *pool, size_t n, size_t s)
306 if (xalloc_oversized (n, s))
308 return pool_alloc (pool, n * s);
311 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
312 returns the new copy. */
314 pool_clone (struct pool *pool, const void *buffer, size_t size)
316 void *block = pool_alloc (pool, size);
317 memcpy (block, buffer, size);
321 /* Duplicates STRING, which has LENGTH characters, within POOL,
322 and returns a pointer to the duplicate. LENGTH should not
323 include the null terminator, which is always added to the
324 duplicate. For use only with strings, because the returned
325 pointere may not be aligned properly for other types. */
327 pool_strndup (struct pool *pool, const char *string, size_t length)
332 assert (pool && string);
335 /* Note that strings need not be aligned on any boundary. */
336 #ifndef DISCRETE_BLOCKS
338 struct pool_block *const b = pool->blocks;
340 if (b->ofs + size <= BLOCK_SIZE)
342 copy = ((char *) b) + b->ofs;
346 copy = pool_alloc (pool, size);
349 copy = pool_alloc (pool, size);
352 memcpy (copy, string, length);
357 /* Duplicates null-terminated STRING, within POOL, and returns a
358 pointer to the duplicate. For use only with strings, because
359 the returned pointere may not be aligned properly for other
362 pool_strdup (struct pool *pool, const char *string)
364 return pool_strndup (pool, string, strlen (string));
367 /* Standard allocation routines. */
369 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
370 returns a pointer to the beginning of the block.
371 If POOL is a null pointer, then allocates a normal memory block
374 pool_malloc (struct pool *pool, size_t amt)
380 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
381 g->type = POOL_GIZMO_MALLOC;
384 return ((char *) g) + POOL_GIZMO_SIZE;
390 return xmalloc (amt);
393 /* Allocates and returns N elements of S bytes each, to be
395 If POOL is a null pointer, then allocates a normal memory block
397 N must be nonnegative, S must be positive.
398 Terminates the program if the memory cannot be obtained,
399 including the case where N * S overflows the range of size_t. */
401 pool_nmalloc (struct pool *pool, size_t n, size_t s)
403 if (xalloc_oversized (n, s))
405 return pool_malloc (pool, n * s);
408 /* Changes the allocation size of the specified memory block P managed
409 by POOL to AMT bytes and returns a pointer to the beginning of the
411 If POOL is a null pointer, then the block is reallocated in the
412 usual way with realloc(). */
414 pool_realloc (struct pool *pool, void *p, size_t amt)
422 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
423 check_gizmo (pool, g);
425 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
432 check_gizmo (pool, g);
434 return ((char *) g) + POOL_GIZMO_SIZE;
443 return pool_malloc (pool, amt);
446 return xrealloc (p, amt);
449 /* Changes the allocation size of the specified memory block P
450 managed by POOL to N * S bytes and returns a pointer to the
451 beginning of the block.
452 N must be nonnegative, S must be positive.
453 If POOL is a null pointer, then the block is reallocated in
454 the usual way with xrealloc().
455 Terminates the program if the memory cannot be obtained,
456 including the case where N * S overflows the range of size_t. */
458 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
460 if (xalloc_oversized (n, s))
462 return pool_realloc (pool, p, n * s);
465 /* If P is null, allocate a block of at least *PN such objects;
466 otherwise, reallocate P so that it contains more than *PN
467 objects each of S bytes. *PN must be nonzero unless P is
468 null, and S must be nonzero. Set *PN to the new number of
469 objects, and return the pointer to the new block. *PN is
470 never set to zero, and the returned pointer is never null.
472 The block returned is managed by POOL. If POOL is a null
473 pointer, then the block is reallocated in the usual way with
476 Terminates the program if the memory cannot be obtained,
477 including the case where the memory required overflows the
480 Repeated reallocations are guaranteed to make progress, either by
481 allocating an initial block with a nonzero size, or by allocating a
484 In the following implementation, nonzero sizes are doubled so that
485 repeated reallocations have O(N log N) overall cost rather than
486 O(N**2) cost, but the specification for this function does not
487 guarantee that sizes are doubled.
489 Here is an example of use:
494 size_t allocated = 0;
497 append_int (int value)
499 if (used == allocated)
500 p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
504 This causes x2nrealloc to allocate a block of some nonzero size the
505 first time it is called.
507 To have finer-grained control over the initial size, set *PN to a
508 nonzero value before calling this function with P == NULL. For
514 size_t allocated = 0;
515 size_t allocated1 = 1000;
518 append_int (int value)
520 if (used == allocated)
522 p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
523 allocated = allocated1;
528 This function implementation is from gnulib. */
530 pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
538 /* The approximate size to use for initial small allocation
539 requests, when the invoking code specifies an old size of
540 zero. 64 bytes is the largest "small" request for the
541 GNU C library malloc. */
542 enum { DEFAULT_MXFAST = 64 };
544 n = DEFAULT_MXFAST / s;
550 if (SIZE_MAX / 2 / s < n)
556 return pool_realloc (pool, p, n * s);
559 /* Frees block P managed by POOL.
560 If POOL is a null pointer, then the block is freed as usual with
563 pool_free (struct pool *pool, void *p)
565 if (pool != NULL && p != NULL)
567 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
568 check_gizmo (pool, g);
569 delete_gizmo (pool, g);
576 /* Gizmo allocations. */
578 /* Creates and returns a pool as a subpool of POOL.
579 The subpool will be destroyed automatically when POOL is destroyed.
580 It may also be destroyed explicitly in advance. */
582 pool_create_subpool (struct pool *pool)
584 struct pool *subpool;
585 struct pool_gizmo *g;
587 assert (pool != NULL);
588 subpool = pool_create ();
589 subpool->parent = pool;
591 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
592 subpool->blocks->ofs += POOL_GIZMO_SIZE;
594 g->type = POOL_GIZMO_SUBPOOL;
595 g->p.subpool = subpool;
602 /* Makes SUBPOOL a subpool of POOL.
603 SUBPOOL must not already have a parent pool.
604 The subpool will be destroyed automatically when POOL is destroyed.
605 It may also be destroyed explicitly in advance. */
607 pool_add_subpool (struct pool *pool, struct pool *subpool)
609 struct pool_gizmo *g;
611 assert (pool != NULL);
612 assert (subpool != NULL);
613 assert (subpool->parent == NULL);
615 g = pool_alloc (subpool, sizeof *g);
616 g->type = POOL_GIZMO_SUBPOOL;
617 g->p.subpool = subpool;
620 subpool->parent = pool;
623 /* Opens file FILENAME with mode MODE and returns a handle to it
624 if successful or a null pointer if not.
625 The file will be closed automatically when POOL is destroyed, or it
626 may be closed explicitly in advance using pool_fclose. */
628 pool_fopen (struct pool *pool, const char *filename, const char *mode)
632 assert (pool && filename && mode);
633 f = fopen (filename, mode);
638 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
639 g->type = POOL_GIZMO_FILE;
647 /* Closes file FILE managed by POOL. */
649 pool_fclose (struct pool *pool, FILE *file)
651 assert (pool && file);
652 if (fclose (file) == EOF)
656 struct pool_gizmo *g;
658 for (g = pool->gizmos; g; g = g->next)
659 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
661 delete_gizmo (pool, g);
669 /* Registers FREE to be called with argument P.
670 P should be unique among those registered in POOL so that it can be
671 uniquely identified by pool_unregister().
672 If not unregistered, FREE will be called with argument P when POOL
675 pool_register (struct pool *pool, void (*free) (void *), void *p)
677 assert (pool && free && p);
680 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
681 g->type = POOL_GIZMO_REGISTERED;
682 g->p.registered.free = free;
683 g->p.registered.p = p;
688 /* Unregisters previously registered P from POOL.
689 Returns nonzero only if P was found to be registered in POOL. */
691 pool_unregister (struct pool *pool, void *p)
696 struct pool_gizmo *g;
698 for (g = pool->gizmos; g; g = g->next)
699 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
701 delete_gizmo (pool, g);
709 /* Partial freeing. */
711 /* Notes the state of POOL into MARK so that it may be restored
712 by a call to pool_release(). */
714 pool_mark (struct pool *pool, struct pool_mark *mark)
716 assert (pool && mark);
718 mark->block = pool->blocks;
719 mark->ofs = pool->blocks->ofs;
721 mark->serial = serial;
724 /* Restores to POOL the state recorded in MARK.
725 Emptied blocks are not given back with free() but kept for
726 later allocations. To get that behavior, use a subpool
729 pool_release (struct pool *pool, const struct pool_mark *mark)
731 assert (pool && mark);
734 struct pool_gizmo *cur, *next;
736 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
752 struct pool_block *cur;
754 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
756 cur->ofs = POOL_BLOCK_SIZE;
757 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
759 cur->ofs += POOL_SIZE;
760 if (pool->parent != NULL)
761 cur->ofs += POOL_GIZMO_SIZE;
764 pool->blocks = mark->block;
765 pool->blocks->ofs = mark->ofs;
769 /* Private functions. */
771 /* Adds GIZMO at the beginning of POOL's gizmo list. */
773 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
775 assert (pool && gizmo);
778 gizmo->next = pool->gizmos;
781 pool->gizmos->prev = gizmo;
782 pool->gizmos = gizmo;
784 gizmo->serial = serial++;
786 check_gizmo (pool, gizmo);
789 /* Removes GIZMO from POOL's gizmo list. */
791 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
793 assert (pool && gizmo);
795 check_gizmo (pool, gizmo);
798 gizmo->prev->next = gizmo->next;
800 pool->gizmos = gizmo->next;
802 gizmo->next->prev = gizmo->prev;
805 /* Frees any of GIZMO's internal state.
806 GIZMO's data must not be referenced after calling this function. */
808 free_gizmo (struct pool_gizmo *gizmo)
810 assert (gizmo != NULL);
814 case POOL_GIZMO_MALLOC:
817 case POOL_GIZMO_FILE:
818 fclose (gizmo->p.file); /* Ignore errors. */
820 case POOL_GIZMO_SUBPOOL:
821 gizmo->p.subpool->parent = NULL;
822 pool_destroy (gizmo->p.subpool);
824 case POOL_GIZMO_REGISTERED:
825 gizmo->p.registered.free (gizmo->p.registered.p);
832 /* Free all the gizmos in POOL. */
834 free_all_gizmos (struct pool *pool)
836 struct pool_gizmo *cur, *next;
838 for (cur = pool->gizmos; cur; cur = next)
847 check_gizmo (struct pool *p, struct pool_gizmo *g)
849 assert (g->pool == p);
850 assert (g->next == NULL || g->next->prev == g);
851 assert ((g->prev != NULL && g->prev->next == g)
852 || (g->prev == NULL && p->gizmos == g));
856 /* Self-test routine. */
864 #define N_ITERATIONS 8192
867 /* Self-test routine.
868 This is not exhaustive, but it can be useful. */
870 cmd_debug_pool (void)
872 int seed = time (0) * 257 % 32768;
877 struct pool_mark m1, m2;
878 FILE *files[N_FILES];
882 printf ("Random number seed: %d\n", seed);
885 printf ("Creating pool...\n");
886 pool = pool_create ();
888 printf ("Marking pool state...\n");
889 pool_mark (pool, &m1);
891 printf (" Populating pool with random-sized small objects...\n");
892 for (i = 0; i < N_ITERATIONS; i++)
894 size_t size = rand () % MAX_SUBALLOC;
895 void *p = pool_alloc (pool, size);
899 printf (" Marking pool state...\n");
900 pool_mark (pool, &m2);
902 printf (" Populating pool with random-sized small "
903 "and large objects...\n");
904 for (i = 0; i < N_ITERATIONS; i++)
906 size_t size = rand () % (2 * MAX_SUBALLOC);
907 void *p = pool_alloc (pool, size);
911 printf (" Releasing pool state...\n");
912 pool_release (pool, &m2);
914 printf (" Populating pool with random objects and gizmos...\n");
915 for (i = 0; i < N_FILES; i++)
918 for (i = 0; i < N_ITERATIONS; i++)
920 int type = rand () % 32;
924 if (files[cur_file] != NULL
925 && EOF == pool_fclose (pool, files[cur_file]))
926 printf ("error on fclose: %s\n", strerror (errno));
928 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
930 if (++cur_file >= N_FILES)
934 pool_create_subpool (pool);
937 size_t size = rand () % (2 * MAX_SUBALLOC);
938 void *p = pool_alloc (pool, size);
943 printf ("Releasing pool state...\n");
944 pool_release (pool, &m1);
946 printf ("Destroying pool...\n");