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 /* Destroy the specified pool, including all subpools. */
172 pool_destroy (struct pool *pool)
177 /* Remove this pool from its parent's list of gizmos. */
179 delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
181 free_all_gizmos (pool);
183 /* Free all the memory. */
185 struct pool_block *cur, *next;
187 pool->blocks->prev->next = NULL;
188 for (cur = pool->blocks; cur; cur = next)
196 /* Release all the memory and gizmos in POOL.
197 Blocks are not given back with free() but kept for later
198 allocations. To give back memory, use a subpool instead. */
200 pool_clear (struct pool *pool)
202 free_all_gizmos (pool);
204 /* Zero out block sizes. */
206 struct pool_block *cur;
211 cur->ofs = POOL_BLOCK_SIZE;
212 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
214 cur->ofs += POOL_SIZE;
215 if (pool->parent != NULL)
216 cur->ofs += POOL_GIZMO_SIZE;
220 while (cur != pool->blocks);
224 /* Suballocation routines. */
226 /* Allocates a memory region AMT bytes in size from POOL and returns a
227 pointer to the region's start. */
229 pool_alloc (struct pool *pool, size_t amt)
231 assert (pool != NULL);
233 #ifndef DISCRETE_BLOCKS
234 if (amt <= MAX_SUBALLOC)
236 /* If there is space in this block, take it. */
237 struct pool_block *b = pool->blocks;
238 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
239 if (b->ofs + amt <= BLOCK_SIZE)
241 void *const p = ((char *) b) + b->ofs;
246 /* No space in this block, so we must make other
248 if (b->next->ofs == 0)
250 /* The next block is empty. Use it. */
252 b->ofs = POOL_BLOCK_SIZE;
253 if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
258 /* Create a new block at the start of the list. */
259 b = xmalloc (BLOCK_SIZE);
260 b->next = pool->blocks;
261 b->prev = pool->blocks->prev;
262 b->ofs = POOL_BLOCK_SIZE;
263 pool->blocks->prev->next = b;
264 pool->blocks->prev = b;
268 /* Allocate space from B. */
270 return ((char *) b) + b->ofs - amt;
274 return pool_malloc (pool, amt);
277 /* Allocates a memory region N * S bytes in size from POOL and
278 returns a pointer to the region's start.
279 N must be nonnegative, S must be positive.
280 Terminates the program if the memory cannot be obtained,
281 including the case where N * S overflows the range of size_t. */
283 pool_nalloc (struct pool *pool, size_t n, size_t s)
285 if (xalloc_oversized (n, s))
287 return pool_alloc (pool, n * s);
290 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
291 returns the new copy. */
293 pool_clone (struct pool *pool, const void *buffer, size_t size)
295 void *block = pool_alloc (pool, size);
296 memcpy (block, buffer, size);
300 /* Duplicates STRING, which has LENGTH characters, within POOL,
301 and returns a pointer to the duplicate. LENGTH should not
302 include the null terminator, which is always added to the
303 duplicate. For use only with strings, because the returned
304 pointere may not be aligned properly for other types. */
306 pool_strndup (struct pool *pool, const char *string, size_t length)
311 assert (pool && string);
314 /* Note that strings need not be aligned on any boundary. */
315 #ifndef DISCRETE_BLOCKS
317 struct pool_block *const b = pool->blocks;
319 if (b->ofs + size <= BLOCK_SIZE)
321 copy = ((char *) b) + b->ofs;
325 copy = pool_alloc (pool, size);
328 copy = pool_alloc (pool, size);
331 memcpy (copy, string, length);
336 /* Duplicates null-terminated STRING, within POOL, and returns a
337 pointer to the duplicate. For use only with strings, because
338 the returned pointere may not be aligned properly for other
341 pool_strdup (struct pool *pool, const char *string)
343 return pool_strndup (pool, string, strlen (string));
346 /* Standard allocation routines. */
348 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
349 returns a pointer to the beginning of the block.
350 If POOL is a null pointer, then allocates a normal memory block
353 pool_malloc (struct pool *pool, size_t amt)
359 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
360 g->type = POOL_GIZMO_MALLOC;
363 return ((char *) g) + POOL_GIZMO_SIZE;
369 return xmalloc (amt);
372 /* Allocates and returns N elements of S bytes each, to be
374 If POOL is a null pointer, then allocates a normal memory block
376 N must be nonnegative, S must be positive.
377 Terminates the program if the memory cannot be obtained,
378 including the case where N * S overflows the range of size_t. */
380 pool_nmalloc (struct pool *pool, size_t n, size_t s)
382 if (xalloc_oversized (n, s))
384 return pool_malloc (pool, n * s);
387 /* Changes the allocation size of the specified memory block P managed
388 by POOL to AMT bytes and returns a pointer to the beginning of the
390 If POOL is a null pointer, then the block is reallocated in the
391 usual way with realloc(). */
393 pool_realloc (struct pool *pool, void *p, size_t amt)
401 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
402 check_gizmo (pool, g);
404 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
411 check_gizmo (pool, g);
413 return ((char *) g) + POOL_GIZMO_SIZE;
422 return pool_malloc (pool, amt);
425 return xrealloc (p, amt);
428 /* Changes the allocation size of the specified memory block P
429 managed by POOL to N * S bytes and returns a pointer to the
430 beginning of the block.
431 N must be nonnegative, S must be positive.
432 If POOL is a null pointer, then the block is reallocated in
433 the usual way with xrealloc().
434 Terminates the program if the memory cannot be obtained,
435 including the case where N * S overflows the range of size_t. */
437 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
439 if (xalloc_oversized (n, s))
441 return pool_realloc (pool, p, n * s);
444 /* If P is null, allocate a block of at least *PN such objects;
445 otherwise, reallocate P so that it contains more than *PN
446 objects each of S bytes. *PN must be nonzero unless P is
447 null, and S must be nonzero. Set *PN to the new number of
448 objects, and return the pointer to the new block. *PN is
449 never set to zero, and the returned pointer is never null.
451 The block returned is managed by POOL. If POOL is a null
452 pointer, then the block is reallocated in the usual way with
455 Terminates the program if the memory cannot be obtained,
456 including the case where the memory required overflows the
459 Repeated reallocations are guaranteed to make progress, either by
460 allocating an initial block with a nonzero size, or by allocating a
463 In the following implementation, nonzero sizes are doubled so that
464 repeated reallocations have O(N log N) overall cost rather than
465 O(N**2) cost, but the specification for this function does not
466 guarantee that sizes are doubled.
468 Here is an example of use:
473 size_t allocated = 0;
476 append_int (int value)
478 if (used == allocated)
479 p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
483 This causes x2nrealloc to allocate a block of some nonzero size the
484 first time it is called.
486 To have finer-grained control over the initial size, set *PN to a
487 nonzero value before calling this function with P == NULL. For
493 size_t allocated = 0;
494 size_t allocated1 = 1000;
497 append_int (int value)
499 if (used == allocated)
501 p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
502 allocated = allocated1;
507 This function implementation is from gnulib. */
509 pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
517 /* The approximate size to use for initial small allocation
518 requests, when the invoking code specifies an old size of
519 zero. 64 bytes is the largest "small" request for the
520 GNU C library malloc. */
521 enum { DEFAULT_MXFAST = 64 };
523 n = DEFAULT_MXFAST / s;
529 if (SIZE_MAX / 2 / s < n)
535 return pool_realloc (pool, p, n * s);
538 /* Frees block P managed by POOL.
539 If POOL is a null pointer, then the block is freed as usual with
542 pool_free (struct pool *pool, void *p)
544 if (pool != NULL && p != NULL)
546 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
547 check_gizmo (pool, g);
548 delete_gizmo (pool, g);
555 /* Gizmo allocations. */
557 /* Creates and returns a pool as a subpool of POOL.
558 The subpool will be destroyed automatically when POOL is destroyed.
559 It may also be destroyed explicitly in advance. */
561 pool_create_subpool (struct pool *pool)
563 struct pool *subpool;
564 struct pool_gizmo *g;
566 assert (pool != NULL);
567 subpool = pool_create ();
568 subpool->parent = pool;
570 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
571 subpool->blocks->ofs += POOL_GIZMO_SIZE;
573 g->type = POOL_GIZMO_SUBPOOL;
574 g->p.subpool = subpool;
581 /* Opens file FILENAME with mode MODE and returns a handle to it
582 if successful or a null pointer if not.
583 The file will be closed automatically when POOL is destroyed, or it
584 may be closed explicitly in advance using pool_fclose. */
586 pool_fopen (struct pool *pool, const char *filename, const char *mode)
590 assert (pool && filename && mode);
591 f = fopen (filename, mode);
596 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
597 g->type = POOL_GIZMO_FILE;
605 /* Closes file FILE managed by POOL. */
607 pool_fclose (struct pool *pool, FILE *file)
609 assert (pool && file);
610 if (fclose (file) == EOF)
614 struct pool_gizmo *g;
616 for (g = pool->gizmos; g; g = g->next)
617 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
619 delete_gizmo (pool, g);
627 /* Registers FREE to be called with argument P.
628 P should be unique among those registered in POOL so that it can be
629 uniquely identified by pool_unregister().
630 If not unregistered, FREE will be called with argument P when POOL
633 pool_register (struct pool *pool, void (*free) (void *), void *p)
635 assert (pool && free && p);
638 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
639 g->type = POOL_GIZMO_REGISTERED;
640 g->p.registered.free = free;
641 g->p.registered.p = p;
646 /* Unregisters previously registered P from POOL.
647 Returns nonzero only if P was found to be registered in POOL. */
649 pool_unregister (struct pool *pool, void *p)
654 struct pool_gizmo *g;
656 for (g = pool->gizmos; g; g = g->next)
657 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
659 delete_gizmo (pool, g);
667 /* Partial freeing. */
669 /* Notes the state of POOL into MARK so that it may be restored
670 by a call to pool_release(). */
672 pool_mark (struct pool *pool, struct pool_mark *mark)
674 assert (pool && mark);
676 mark->block = pool->blocks;
677 mark->ofs = pool->blocks->ofs;
679 mark->serial = serial;
682 /* Restores to POOL the state recorded in MARK.
683 Emptied blocks are not given back with free() but kept for
684 later allocations. To get that behavior, use a subpool
687 pool_release (struct pool *pool, const struct pool_mark *mark)
689 assert (pool && mark);
692 struct pool_gizmo *cur, *next;
694 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
710 struct pool_block *cur;
712 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
714 cur->ofs = POOL_BLOCK_SIZE;
715 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
717 cur->ofs += POOL_SIZE;
718 if (pool->parent != NULL)
719 cur->ofs += POOL_GIZMO_SIZE;
722 pool->blocks = mark->block;
723 pool->blocks->ofs = mark->ofs;
727 /* Private functions. */
729 /* Adds GIZMO at the beginning of POOL's gizmo list. */
731 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
733 assert (pool && gizmo);
736 gizmo->next = pool->gizmos;
739 pool->gizmos->prev = gizmo;
740 pool->gizmos = gizmo;
742 gizmo->serial = serial++;
744 check_gizmo (pool, gizmo);
747 /* Removes GIZMO from POOL's gizmo list. */
749 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
751 assert (pool && gizmo);
753 check_gizmo (pool, gizmo);
756 gizmo->prev->next = gizmo->next;
758 pool->gizmos = gizmo->next;
760 gizmo->next->prev = gizmo->prev;
763 /* Frees any of GIZMO's internal state.
764 GIZMO's data must not be referenced after calling this function. */
766 free_gizmo (struct pool_gizmo *gizmo)
768 assert (gizmo != NULL);
772 case POOL_GIZMO_MALLOC:
775 case POOL_GIZMO_FILE:
776 fclose (gizmo->p.file); /* Ignore errors. */
778 case POOL_GIZMO_SUBPOOL:
779 gizmo->p.subpool->parent = NULL;
780 pool_destroy (gizmo->p.subpool);
782 case POOL_GIZMO_REGISTERED:
783 gizmo->p.registered.free (gizmo->p.registered.p);
790 /* Free all the gizmos in POOL. */
792 free_all_gizmos (struct pool *pool)
794 struct pool_gizmo *cur, *next;
796 for (cur = pool->gizmos; cur; cur = next)
805 check_gizmo (struct pool *p, struct pool_gizmo *g)
807 assert (g->pool == p);
808 assert (g->next == NULL || g->next->prev == g);
809 assert ((g->prev != NULL && g->prev->next == g)
810 || (g->prev == NULL && p->gizmos == g));
814 /* Self-test routine. */
822 #define N_ITERATIONS 8192
825 /* Self-test routine.
826 This is not exhaustive, but it can be useful. */
828 cmd_debug_pool (void)
830 int seed = time (0) * 257 % 32768;
835 struct pool_mark m1, m2;
836 FILE *files[N_FILES];
840 printf ("Random number seed: %d\n", seed);
843 printf ("Creating pool...\n");
844 pool = pool_create ();
846 printf ("Marking pool state...\n");
847 pool_mark (pool, &m1);
849 printf (" Populating pool with random-sized small objects...\n");
850 for (i = 0; i < N_ITERATIONS; i++)
852 size_t size = rand () % MAX_SUBALLOC;
853 void *p = pool_alloc (pool, size);
857 printf (" Marking pool state...\n");
858 pool_mark (pool, &m2);
860 printf (" Populating pool with random-sized small "
861 "and large objects...\n");
862 for (i = 0; i < N_ITERATIONS; i++)
864 size_t size = rand () % (2 * MAX_SUBALLOC);
865 void *p = pool_alloc (pool, size);
869 printf (" Releasing pool state...\n");
870 pool_release (pool, &m2);
872 printf (" Populating pool with random objects and gizmos...\n");
873 for (i = 0; i < N_FILES; i++)
876 for (i = 0; i < N_ITERATIONS; i++)
878 int type = rand () % 32;
882 if (files[cur_file] != NULL
883 && EOF == pool_fclose (pool, files[cur_file]))
884 printf ("error on fclose: %s\n", strerror (errno));
886 files[cur_file] = pool_fopen (pool, "/dev/null", "r");
888 if (++cur_file >= N_FILES)
892 pool_create_subpool (pool);
895 size_t size = rand () % (2 * MAX_SUBALLOC);
896 void *p = pool_alloc (pool, size);
901 printf ("Releasing pool state...\n");
902 pool_release (pool, &m1);
904 printf ("Destroying pool...\n");