1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2000, 2010, 2011, 2012 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19 #include "libpspp/pool.h"
24 #include "libpspp/assertion.h"
25 #include "libpspp/message.h"
26 #include "libpspp/temp-file.h"
27 #include "libpspp/str.h"
29 #include "gl/xalloc-oversized.h"
30 #include "gl/xalloc.h"
32 /* Fast, low-overhead memory block suballocator. */
35 struct pool *parent; /* Pool of which this pool is a subpool. */
36 struct pool_block *blocks; /* Blocks owned by the pool. */
37 struct pool_gizmo *gizmos; /* Other stuff owned by the pool. */
43 struct pool_block *prev;
44 struct pool_block *next;
55 POOL_GIZMO_REGISTERED,
58 /* Pool routines can maintain objects (`gizmos') as well as doing
60 This structure is used to keep track of them. */
64 struct pool_gizmo *prev;
65 struct pool_gizmo *next;
67 long serial; /* Serial number. */
68 int type; /* Type of this gizmo. */
70 /* Type-dependent info. */
73 FILE *file; /* POOL_GIZMO_FILE, POOL_GIZMO_TEMP_FILE. */
74 struct pool *subpool; /* POOL_GIZMO_SUBPOOL. */
76 /* POOL_GIZMO_REGISTERED. */
79 void (*free) (void *p);
87 /* Rounds X up to the next multiple of Y. */
89 #define ROUND_UP(X, Y) \
90 (((X) + ((Y) - 1)) / (Y) * (Y))
93 /* Types that provide typically useful alignment sizes. */
101 /* glibc jmp_buf on ia64 requires 16-byte alignment. This ensures it. */
105 /* This should be the alignment size used by malloc(). The size of
106 the union above is correct, if not optimal, in all known cases.
108 This is normally 8 bytes for 32-bit architectures and 16 bytes for 64-bit
110 #define ALIGN_SIZE sizeof (union align)
112 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
113 suballocation of blocks. This is useful under memory
114 debuggers like valgrind because it allows the source location
115 of bugs to be more accurately pinpointed.
117 On the other hand, if we're testing the library, then we want to
118 test the library's real functionality, not its crippled, slow,
119 simplified functionality. */
120 /*#define DISCRETE_BLOCKS 1*/
122 /* Size of each block allocated in the pool, in bytes.
123 Should be at least 1k. */
125 #define BLOCK_SIZE 1024
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.
249 The region is properly aligned for storing any object. */
251 pool_alloc (struct pool *pool, size_t amt)
253 assert (pool != NULL);
258 #ifndef DISCRETE_BLOCKS
259 if (amt <= MAX_SUBALLOC)
261 /* If there is space in this block, take it. */
262 struct pool_block *b = pool->blocks;
263 b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
264 if (b->ofs + amt <= BLOCK_SIZE)
266 void *const p = ((char *) b) + b->ofs;
271 /* No space in this block, so we must make other
273 if (b->next->ofs == 0)
275 /* The next block is empty. Use it. */
277 b->ofs = POOL_BLOCK_SIZE;
278 if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
283 /* Create a new block at the start of the list. */
284 b = xmalloc (BLOCK_SIZE);
285 b->next = pool->blocks;
286 b->prev = pool->blocks->prev;
287 b->ofs = POOL_BLOCK_SIZE;
288 pool->blocks->prev->next = b;
289 pool->blocks->prev = b;
293 /* Allocate space from B. */
295 return ((char *) b) + b->ofs - amt;
299 return pool_malloc (pool, amt);
302 /* Allocates a memory region AMT bytes in size from POOL and
303 returns a pointer to the region's start. The region is not
304 necessarily aligned, so it is most suitable for storing
307 pool_alloc_unaligned (struct pool *pool, size_t amt)
310 return xmalloc (amt);
312 #ifndef DISCRETE_BLOCKS
313 /* Strings need not be aligned on any boundary, but some
314 operations may be more efficient when they are. However,
315 that's only going to help with reasonably long strings. */
316 if (amt < ALIGN_SIZE)
322 struct pool_block *const b = pool->blocks;
324 if (b->ofs + amt <= BLOCK_SIZE)
326 void *p = ((char *) b) + b->ofs;
334 return pool_alloc (pool, amt);
337 /* Allocates a memory region N * S bytes in size from POOL and
338 returns a pointer to the region's start.
339 N must be nonnegative, S must be positive.
340 Terminates the program if the memory cannot be obtained,
341 including the case where N * S overflows the range of size_t. */
343 pool_nalloc (struct pool *pool, size_t n, size_t s)
345 if (xalloc_oversized (n, s))
347 return pool_alloc (pool, n * s);
350 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
351 returns the new copy. */
353 pool_clone (struct pool *pool, const void *buffer, size_t size)
355 void *block = pool_alloc (pool, size);
356 memcpy (block, buffer, size);
360 /* Allocates SIZE bytes of unaligned data in POOL, copies BUFFER
361 into it, and returns the new copy. */
363 pool_clone_unaligned (struct pool *pool, const void *buffer, size_t size)
365 void *block = pool_alloc_unaligned (pool, size);
366 memcpy (block, buffer, size);
370 /* Duplicates null-terminated STRING, within POOL, and returns a
371 pointer to the duplicate. For use only with strings, because
372 the returned pointere may not be aligned properly for other
375 pool_strdup (struct pool *pool, const char *string)
377 return pool_clone_unaligned (pool, string, strlen (string) + 1);
380 /* Duplicates the SIZE bytes of STRING, plus a trailing 0 byte,
381 and returns a pointer to the duplicate. For use only with
382 strings, because the returned pointere may not be aligned
383 properly for other types. */
385 pool_memdup0 (struct pool *pool, const char *string, size_t size)
387 char *new_string = pool_alloc_unaligned (pool, size + 1);
388 memcpy (new_string, string, size);
389 new_string[size] = '\0';
393 /* Formats FORMAT with the given ARGS in memory allocated from
394 POOL and returns the formatted string. */
396 pool_vasprintf (struct pool *pool, const char *format, va_list args_)
399 return xvasprintf (format, args_);
401 struct pool_block *b;
406 va_copy (args, args_);
408 avail = BLOCK_SIZE - b->ofs;
409 s = ((char *) b) + b->ofs;
410 needed = vsnprintf (s, avail, format, args);
417 /* Success. Reserve the space that was actually used. */
418 b->ofs += needed + 1;
422 /* Failure, but now we know how much space is needed.
423 Allocate that much and reformat. */
424 s = pool_alloc (pool, needed + 1);
426 va_copy (args, args_);
427 vsprintf (s, format, args);
433 /* Some old libc's returned -1 when the destination string
434 was too short. This should be uncommon these days and
435 it's a rare case anyhow. Use the easiest solution: punt
436 to dynamic allocation. */
437 va_copy (args, args_);
438 s = xvasprintf (format, args);
441 pool_register (pool, free, s);
447 /* Formats FORMAT in memory allocated from POOL
448 and returns the formatted string. */
450 pool_asprintf (struct pool *pool, const char *format, ...)
455 va_start (args, format);
456 string = pool_vasprintf (pool, format, args);
462 /* Standard allocation routines. */
464 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
465 returns a pointer to the beginning of the block.
466 If POOL is a null pointer, then allocates a normal memory block
469 pool_malloc (struct pool *pool, size_t amt)
475 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
476 g->type = POOL_GIZMO_MALLOC;
479 return ((char *) g) + POOL_GIZMO_SIZE;
485 return xmalloc (amt);
488 /* Allocates and returns N elements of S bytes each, to be
490 If POOL is a null pointer, then allocates a normal memory block
492 N must be nonnegative, S must be positive.
493 Terminates the program if the memory cannot be obtained,
494 including the case where N * S overflows the range of size_t. */
496 pool_nmalloc (struct pool *pool, size_t n, size_t s)
498 if (xalloc_oversized (n, s))
500 return pool_malloc (pool, n * s);
503 /* Allocates AMT bytes using malloc(), to be managed by POOL,
504 zeros the block, and returns a pointer to the beginning of the
506 If POOL is a null pointer, then allocates a normal memory block
509 pool_zalloc (struct pool *pool, size_t amt)
511 void *p = pool_malloc (pool, amt);
516 /* Allocates and returns N elements of S bytes each, to be
517 managed by POOL, and zeros the block.
518 If POOL is a null pointer, then allocates a normal memory block
520 N must be nonnegative, S must be positive.
521 Terminates the program if the memory cannot be obtained,
522 including the case where N * S overflows the range of size_t. */
524 pool_calloc (struct pool *pool, size_t n, size_t s)
526 void *p = pool_nmalloc (pool, n, s);
527 memset (p, 0, n * s);
531 /* Changes the allocation size of the specified memory block P managed
532 by POOL to AMT bytes and returns a pointer to the beginning of the
534 If POOL is a null pointer, then the block is reallocated in the
535 usual way with realloc(). */
537 pool_realloc (struct pool *pool, void *p, size_t amt)
545 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
546 check_gizmo (pool, g);
548 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
555 check_gizmo (pool, g);
557 return ((char *) g) + POOL_GIZMO_SIZE;
566 return pool_malloc (pool, amt);
569 return xrealloc (p, amt);
572 /* Changes the allocation size of the specified memory block P
573 managed by POOL to N * S bytes and returns a pointer to the
574 beginning of the block.
575 N must be nonnegative, S must be positive.
576 If POOL is a null pointer, then the block is reallocated in
577 the usual way with xrealloc().
578 Terminates the program if the memory cannot be obtained,
579 including the case where N * S overflows the range of size_t. */
581 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
583 if (xalloc_oversized (n, s))
585 return pool_realloc (pool, p, n * s);
588 /* If P is null, allocate a block of at least *PN such objects;
589 otherwise, reallocate P so that it contains more than *PN
590 objects each of S bytes. *PN must be nonzero unless P is
591 null, and S must be nonzero. Set *PN to the new number of
592 objects, and return the pointer to the new block. *PN is
593 never set to zero, and the returned pointer is never null.
595 The block returned is managed by POOL. If POOL is a null
596 pointer, then the block is reallocated in the usual way with
599 Terminates the program if the memory cannot be obtained,
600 including the case where the memory required overflows the
603 Repeated reallocations are guaranteed to make progress, either by
604 allocating an initial block with a nonzero size, or by allocating a
607 In the following implementation, nonzero sizes are doubled so that
608 repeated reallocations have O(N log N) overall cost rather than
609 O(N**2) cost, but the specification for this function does not
610 guarantee that sizes are doubled.
612 Here is an example of use:
617 size_t allocated = 0;
620 append_int (int value)
622 if (used == allocated)
623 p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
627 This causes x2nrealloc to allocate a block of some nonzero size the
628 first time it is called.
630 To have finer-grained control over the initial size, set *PN to a
631 nonzero value before calling this function with P == NULL. For
637 size_t allocated = 0;
638 size_t allocated1 = 1000;
641 append_int (int value)
643 if (used == allocated)
645 p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
646 allocated = allocated1;
651 This function implementation is from gnulib. */
653 pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
661 /* The approximate size to use for initial small allocation
662 requests, when the invoking code specifies an old size of
663 zero. 64 bytes is the largest "small" request for the
664 GNU C library malloc. */
665 enum { DEFAULT_MXFAST = 64 };
667 n = DEFAULT_MXFAST / s;
673 if (SIZE_MAX / 2 / s < n)
679 return pool_realloc (pool, p, n * s);
682 /* Frees block P managed by POOL.
683 If POOL is a null pointer, then the block is freed as usual with
686 pool_free (struct pool *pool, void *p)
688 if (pool != NULL && p != NULL)
690 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
691 check_gizmo (pool, g);
692 delete_gizmo (pool, g);
699 /* Gizmo allocations. */
701 /* Creates and returns a pool as a subpool of POOL.
702 The subpool will be destroyed automatically when POOL is destroyed.
703 It may also be destroyed explicitly in advance. */
705 pool_create_subpool (struct pool *pool)
707 struct pool *subpool;
708 struct pool_gizmo *g;
710 assert (pool != NULL);
711 subpool = pool_create ();
712 subpool->parent = pool;
714 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
715 subpool->blocks->ofs += POOL_GIZMO_SIZE;
717 g->type = POOL_GIZMO_SUBPOOL;
718 g->p.subpool = subpool;
725 /* Makes SUBPOOL a subpool of POOL.
726 SUBPOOL must not already have a parent pool.
727 The subpool will be destroyed automatically when POOL is destroyed.
728 It may also be destroyed explicitly in advance. */
730 pool_add_subpool (struct pool *pool, struct pool *subpool)
732 struct pool_gizmo *g;
734 assert (pool != NULL);
735 assert (subpool != NULL);
736 assert (subpool->parent == NULL);
738 g = pool_alloc (subpool, sizeof *g);
739 g->type = POOL_GIZMO_SUBPOOL;
740 g->p.subpool = subpool;
743 subpool->parent = pool;
746 /* Opens file FILE_NAME with mode MODE and returns a handle to it
747 if successful or a null pointer if not.
748 The file will be closed automatically when POOL is destroyed, or it
749 may be closed explicitly in advance using pool_fclose(), or
750 detached from the pool with pool_detach_file(). */
752 pool_fopen (struct pool *pool, const char *file_name, const char *mode)
756 assert (pool && file_name && mode);
757 f = fopen (file_name, mode);
759 pool_attach_file (pool, f);
764 /* Closes file FILE managed by POOL.
765 Returns 0 if successful, EOF if an I/O error occurred. */
767 pool_fclose (struct pool *pool, FILE *file)
769 assert (pool && file);
770 pool_detach_file (pool, file);
771 return fclose (file);
774 /* Attaches FILE to POOL.
775 The file will be closed automatically when POOL is destroyed, or it
776 may be closed explicitly in advance using pool_fclose(), or
777 detached from the pool with pool_detach_file(). */
779 pool_attach_file (struct pool *pool, FILE *file)
781 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
782 g->type = POOL_GIZMO_FILE;
787 /* Detaches FILE from POOL. */
789 pool_detach_file (struct pool *pool, FILE *file)
791 struct pool_gizmo *g;
793 for (g = pool->gizmos; g; g = g->next)
794 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
796 delete_gizmo (pool, g);
801 /* Creates a temporary file with create_temp_file() and returns a handle to it
802 if successful or a null pointer if not.
803 The file will be closed automatically when POOL is destroyed, or it
804 may be closed explicitly in advance using pool_fclose_temp_file(), or
805 detached from the pool with pool_detach_temp_file(). */
807 pool_create_temp_file (struct pool *pool)
809 FILE *file = create_temp_file ();
811 pool_attach_temp_file (pool, file);
815 /* Closes file FILE managed by POOL.
816 FILE must have been opened with create_temp_file(). */
818 pool_fclose_temp_file (struct pool *pool, FILE *file)
820 assert (pool && file);
821 pool_detach_temp_file (pool, file);
822 close_temp_file (file);
825 /* Attaches FILE, which must have been opened with create_temp_file(), to POOL.
826 The file will be closed automatically when POOL is destroyed, or it
827 may be closed explicitly in advance using pool_fclose_temp_file(), or
828 detached from the pool with pool_detach_temp_file(). */
830 pool_attach_temp_file (struct pool *pool, FILE *file)
832 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
833 g->type = POOL_GIZMO_TEMP_FILE;
838 /* Detaches FILE that was opened with create_temp_file() from POOL. */
840 pool_detach_temp_file (struct pool *pool, FILE *file)
842 struct pool_gizmo *g;
844 for (g = pool->gizmos; g; g = g->next)
845 if (g->type == POOL_GIZMO_TEMP_FILE && g->p.file == file)
847 delete_gizmo (pool, g);
852 /* Registers FREE to be called with argument P.
853 P should be unique among those registered in POOL so that it can be
854 uniquely identified by pool_unregister().
855 If not unregistered, FREE will be called with argument P when POOL
858 pool_register (struct pool *pool, void (*free) (void *), void *p)
860 assert (pool && free && p);
863 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
864 g->type = POOL_GIZMO_REGISTERED;
865 g->p.registered.free = free;
866 g->p.registered.p = p;
871 /* Unregisters previously registered P from POOL.
872 Returns true only if P was found to be registered in POOL. */
874 pool_unregister (struct pool *pool, void *p)
879 struct pool_gizmo *g;
881 for (g = pool->gizmos; g; g = g->next)
882 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
884 delete_gizmo (pool, g);
892 /* Partial freeing. */
894 /* Notes the state of POOL into MARK so that it may be restored
895 by a call to pool_release(). */
897 pool_mark (struct pool *pool, struct pool_mark *mark)
899 assert (pool && mark);
901 mark->block = pool->blocks;
902 mark->ofs = pool->blocks->ofs;
904 mark->serial = serial;
907 /* Restores to POOL the state recorded in MARK.
908 Emptied blocks are not given back with free() but kept for
909 later allocations. To get that behavior, use a subpool
912 pool_release (struct pool *pool, const struct pool_mark *mark)
914 assert (pool && mark);
917 struct pool_gizmo *cur, *next;
919 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
935 struct pool_block *cur;
937 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
939 cur->ofs = POOL_BLOCK_SIZE;
940 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
942 cur->ofs += POOL_SIZE;
943 if (pool->parent != NULL)
944 cur->ofs += POOL_GIZMO_SIZE;
947 pool->blocks = mark->block;
948 pool->blocks->ofs = mark->ofs;
952 /* Private functions. */
954 /* Adds GIZMO at the beginning of POOL's gizmo list. */
956 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
958 assert (pool && gizmo);
961 gizmo->next = pool->gizmos;
964 pool->gizmos->prev = gizmo;
965 pool->gizmos = gizmo;
967 gizmo->serial = serial++;
969 check_gizmo (pool, gizmo);
972 /* Removes GIZMO from POOL's gizmo list. */
974 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
976 assert (pool && gizmo);
978 check_gizmo (pool, gizmo);
981 gizmo->prev->next = gizmo->next;
983 pool->gizmos = gizmo->next;
985 gizmo->next->prev = gizmo->prev;
988 /* Frees any of GIZMO's internal state.
989 GIZMO's data must not be referenced after calling this function. */
991 free_gizmo (struct pool_gizmo *gizmo)
993 assert (gizmo != NULL);
997 case POOL_GIZMO_MALLOC:
1000 case POOL_GIZMO_FILE:
1001 fclose (gizmo->p.file); /* Ignore errors. */
1003 case POOL_GIZMO_TEMP_FILE:
1004 close_temp_file (gizmo->p.file); /* Ignore errors. */
1006 case POOL_GIZMO_SUBPOOL:
1007 gizmo->p.subpool->parent = NULL;
1008 pool_destroy (gizmo->p.subpool);
1010 case POOL_GIZMO_REGISTERED:
1011 gizmo->p.registered.free (gizmo->p.registered.p);
1018 /* Free all the gizmos in POOL. */
1020 free_all_gizmos (struct pool *pool)
1022 struct pool_gizmo *cur, *next;
1024 for (cur = pool->gizmos; cur; cur = next)
1029 pool->gizmos = NULL;
1033 check_gizmo (struct pool *p, struct pool_gizmo *g)
1035 assert (g->pool == p);
1036 assert (g->next == NULL || g->next->prev == g);
1037 assert ((g->prev != NULL && g->prev->next == g)
1038 || (g->prev == NULL && p->gizmos == g));