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_)
398 struct pool_block *b;
403 va_copy (args, args_);
405 avail = BLOCK_SIZE - b->ofs;
406 s = ((char *) b) + b->ofs;
407 needed = vsnprintf (s, avail, format, args);
414 /* Success. Reserve the space that was actually used. */
415 b->ofs += needed + 1;
419 /* Failure, but now we know how much space is needed.
420 Allocate that much and reformat. */
421 s = pool_alloc (pool, needed + 1);
423 va_copy (args, args_);
424 vsprintf (s, format, args);
430 /* Some old libc's returned -1 when the destination string
431 was too short. This should be uncommon these days and
432 it's a rare case anyhow. Use the easiest solution: punt
433 to dynamic allocation. */
434 va_copy (args, args_);
435 s = xvasprintf (format, args);
438 pool_register (pool, free, s);
444 /* Formats FORMAT in memory allocated from POOL
445 and returns the formatted string. */
447 pool_asprintf (struct pool *pool, const char *format, ...)
452 va_start (args, format);
453 string = pool_vasprintf (pool, format, args);
459 /* Standard allocation routines. */
461 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
462 returns a pointer to the beginning of the block.
463 If POOL is a null pointer, then allocates a normal memory block
466 pool_malloc (struct pool *pool, size_t amt)
472 struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
473 g->type = POOL_GIZMO_MALLOC;
476 return ((char *) g) + POOL_GIZMO_SIZE;
482 return xmalloc (amt);
485 /* Allocates and returns N elements of S bytes each, to be
487 If POOL is a null pointer, then allocates a normal memory block
489 N must be nonnegative, S must be positive.
490 Terminates the program if the memory cannot be obtained,
491 including the case where N * S overflows the range of size_t. */
493 pool_nmalloc (struct pool *pool, size_t n, size_t s)
495 if (xalloc_oversized (n, s))
497 return pool_malloc (pool, n * s);
500 /* Allocates AMT bytes using malloc(), to be managed by POOL,
501 zeros the block, and returns a pointer to the beginning of the
503 If POOL is a null pointer, then allocates a normal memory block
506 pool_zalloc (struct pool *pool, size_t amt)
508 void *p = pool_malloc (pool, amt);
513 /* Allocates and returns N elements of S bytes each, to be
514 managed by POOL, and zeros the block.
515 If POOL is a null pointer, then allocates a normal memory block
517 N must be nonnegative, S must be positive.
518 Terminates the program if the memory cannot be obtained,
519 including the case where N * S overflows the range of size_t. */
521 pool_calloc (struct pool *pool, size_t n, size_t s)
523 void *p = pool_nmalloc (pool, n, s);
524 memset (p, 0, n * s);
528 /* Changes the allocation size of the specified memory block P managed
529 by POOL to AMT bytes and returns a pointer to the beginning of the
531 If POOL is a null pointer, then the block is reallocated in the
532 usual way with realloc(). */
534 pool_realloc (struct pool *pool, void *p, size_t amt)
542 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
543 check_gizmo (pool, g);
545 g = xrealloc (g, amt + POOL_GIZMO_SIZE);
552 check_gizmo (pool, g);
554 return ((char *) g) + POOL_GIZMO_SIZE;
563 return pool_malloc (pool, amt);
566 return xrealloc (p, amt);
569 /* Changes the allocation size of the specified memory block P
570 managed by POOL to N * S bytes and returns a pointer to the
571 beginning of the block.
572 N must be nonnegative, S must be positive.
573 If POOL is a null pointer, then the block is reallocated in
574 the usual way with xrealloc().
575 Terminates the program if the memory cannot be obtained,
576 including the case where N * S overflows the range of size_t. */
578 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
580 if (xalloc_oversized (n, s))
582 return pool_realloc (pool, p, n * s);
585 /* If P is null, allocate a block of at least *PN such objects;
586 otherwise, reallocate P so that it contains more than *PN
587 objects each of S bytes. *PN must be nonzero unless P is
588 null, and S must be nonzero. Set *PN to the new number of
589 objects, and return the pointer to the new block. *PN is
590 never set to zero, and the returned pointer is never null.
592 The block returned is managed by POOL. If POOL is a null
593 pointer, then the block is reallocated in the usual way with
596 Terminates the program if the memory cannot be obtained,
597 including the case where the memory required overflows the
600 Repeated reallocations are guaranteed to make progress, either by
601 allocating an initial block with a nonzero size, or by allocating a
604 In the following implementation, nonzero sizes are doubled so that
605 repeated reallocations have O(N log N) overall cost rather than
606 O(N**2) cost, but the specification for this function does not
607 guarantee that sizes are doubled.
609 Here is an example of use:
614 size_t allocated = 0;
617 append_int (int value)
619 if (used == allocated)
620 p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
624 This causes x2nrealloc to allocate a block of some nonzero size the
625 first time it is called.
627 To have finer-grained control over the initial size, set *PN to a
628 nonzero value before calling this function with P == NULL. For
634 size_t allocated = 0;
635 size_t allocated1 = 1000;
638 append_int (int value)
640 if (used == allocated)
642 p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
643 allocated = allocated1;
648 This function implementation is from gnulib. */
650 pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
658 /* The approximate size to use for initial small allocation
659 requests, when the invoking code specifies an old size of
660 zero. 64 bytes is the largest "small" request for the
661 GNU C library malloc. */
662 enum { DEFAULT_MXFAST = 64 };
664 n = DEFAULT_MXFAST / s;
670 if (SIZE_MAX / 2 / s < n)
676 return pool_realloc (pool, p, n * s);
679 /* Frees block P managed by POOL.
680 If POOL is a null pointer, then the block is freed as usual with
683 pool_free (struct pool *pool, void *p)
685 if (pool != NULL && p != NULL)
687 struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
688 check_gizmo (pool, g);
689 delete_gizmo (pool, g);
696 /* Gizmo allocations. */
698 /* Creates and returns a pool as a subpool of POOL.
699 The subpool will be destroyed automatically when POOL is destroyed.
700 It may also be destroyed explicitly in advance. */
702 pool_create_subpool (struct pool *pool)
704 struct pool *subpool;
705 struct pool_gizmo *g;
707 assert (pool != NULL);
708 subpool = pool_create ();
709 subpool->parent = pool;
711 g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
712 subpool->blocks->ofs += POOL_GIZMO_SIZE;
714 g->type = POOL_GIZMO_SUBPOOL;
715 g->p.subpool = subpool;
722 /* Makes SUBPOOL a subpool of POOL.
723 SUBPOOL must not already have a parent pool.
724 The subpool will be destroyed automatically when POOL is destroyed.
725 It may also be destroyed explicitly in advance. */
727 pool_add_subpool (struct pool *pool, struct pool *subpool)
729 struct pool_gizmo *g;
731 assert (pool != NULL);
732 assert (subpool != NULL);
733 assert (subpool->parent == NULL);
735 g = pool_alloc (subpool, sizeof *g);
736 g->type = POOL_GIZMO_SUBPOOL;
737 g->p.subpool = subpool;
740 subpool->parent = pool;
743 /* Opens file FILE_NAME with mode MODE and returns a handle to it
744 if successful or a null pointer if not.
745 The file will be closed automatically when POOL is destroyed, or it
746 may be closed explicitly in advance using pool_fclose(), or
747 detached from the pool with pool_detach_file(). */
749 pool_fopen (struct pool *pool, const char *file_name, const char *mode)
753 assert (pool && file_name && mode);
754 f = fopen (file_name, mode);
756 pool_attach_file (pool, f);
761 /* Closes file FILE managed by POOL.
762 Returns 0 if successful, EOF if an I/O error occurred. */
764 pool_fclose (struct pool *pool, FILE *file)
766 assert (pool && file);
767 pool_detach_file (pool, file);
768 return fclose (file);
771 /* Attaches FILE to POOL.
772 The file will be closed automatically when POOL is destroyed, or it
773 may be closed explicitly in advance using pool_fclose(), or
774 detached from the pool with pool_detach_file(). */
776 pool_attach_file (struct pool *pool, FILE *file)
778 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
779 g->type = POOL_GIZMO_FILE;
784 /* Detaches FILE from POOL. */
786 pool_detach_file (struct pool *pool, FILE *file)
788 struct pool_gizmo *g;
790 for (g = pool->gizmos; g; g = g->next)
791 if (g->type == POOL_GIZMO_FILE && g->p.file == file)
793 delete_gizmo (pool, g);
798 /* Creates a temporary file with create_temp_file() and returns a handle to it
799 if successful or a null pointer if not.
800 The file will be closed automatically when POOL is destroyed, or it
801 may be closed explicitly in advance using pool_fclose_temp_file(), or
802 detached from the pool with pool_detach_temp_file(). */
804 pool_create_temp_file (struct pool *pool)
806 FILE *file = create_temp_file ();
808 pool_attach_temp_file (pool, file);
812 /* Closes file FILE managed by POOL.
813 FILE must have been opened with create_temp_file(). */
815 pool_fclose_temp_file (struct pool *pool, FILE *file)
817 assert (pool && file);
818 pool_detach_temp_file (pool, file);
819 close_temp_file (file);
822 /* Attaches FILE, which must have been opened with create_temp_file(), to POOL.
823 The file will be closed automatically when POOL is destroyed, or it
824 may be closed explicitly in advance using pool_fclose_temp_file(), or
825 detached from the pool with pool_detach_temp_file(). */
827 pool_attach_temp_file (struct pool *pool, FILE *file)
829 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
830 g->type = POOL_GIZMO_TEMP_FILE;
835 /* Detaches FILE that was opened with create_temp_file() from POOL. */
837 pool_detach_temp_file (struct pool *pool, FILE *file)
839 struct pool_gizmo *g;
841 for (g = pool->gizmos; g; g = g->next)
842 if (g->type == POOL_GIZMO_TEMP_FILE && g->p.file == file)
844 delete_gizmo (pool, g);
849 /* Registers FREE to be called with argument P.
850 P should be unique among those registered in POOL so that it can be
851 uniquely identified by pool_unregister().
852 If not unregistered, FREE will be called with argument P when POOL
855 pool_register (struct pool *pool, void (*free) (void *), void *p)
857 assert (pool && free && p);
860 struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
861 g->type = POOL_GIZMO_REGISTERED;
862 g->p.registered.free = free;
863 g->p.registered.p = p;
868 /* Unregisters previously registered P from POOL.
869 Returns true only if P was found to be registered in POOL. */
871 pool_unregister (struct pool *pool, void *p)
876 struct pool_gizmo *g;
878 for (g = pool->gizmos; g; g = g->next)
879 if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
881 delete_gizmo (pool, g);
889 /* Partial freeing. */
891 /* Notes the state of POOL into MARK so that it may be restored
892 by a call to pool_release(). */
894 pool_mark (struct pool *pool, struct pool_mark *mark)
896 assert (pool && mark);
898 mark->block = pool->blocks;
899 mark->ofs = pool->blocks->ofs;
901 mark->serial = serial;
904 /* Restores to POOL the state recorded in MARK.
905 Emptied blocks are not given back with free() but kept for
906 later allocations. To get that behavior, use a subpool
909 pool_release (struct pool *pool, const struct pool_mark *mark)
911 assert (pool && mark);
914 struct pool_gizmo *cur, *next;
916 for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
932 struct pool_block *cur;
934 for (cur = pool->blocks; cur != mark->block; cur = cur->next)
936 cur->ofs = POOL_BLOCK_SIZE;
937 if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
939 cur->ofs += POOL_SIZE;
940 if (pool->parent != NULL)
941 cur->ofs += POOL_GIZMO_SIZE;
944 pool->blocks = mark->block;
945 pool->blocks->ofs = mark->ofs;
949 /* Private functions. */
951 /* Adds GIZMO at the beginning of POOL's gizmo list. */
953 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
955 assert (pool && gizmo);
958 gizmo->next = pool->gizmos;
961 pool->gizmos->prev = gizmo;
962 pool->gizmos = gizmo;
964 gizmo->serial = serial++;
966 check_gizmo (pool, gizmo);
969 /* Removes GIZMO from POOL's gizmo list. */
971 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
973 assert (pool && gizmo);
975 check_gizmo (pool, gizmo);
978 gizmo->prev->next = gizmo->next;
980 pool->gizmos = gizmo->next;
982 gizmo->next->prev = gizmo->prev;
985 /* Frees any of GIZMO's internal state.
986 GIZMO's data must not be referenced after calling this function. */
988 free_gizmo (struct pool_gizmo *gizmo)
990 assert (gizmo != NULL);
994 case POOL_GIZMO_MALLOC:
997 case POOL_GIZMO_FILE:
998 fclose (gizmo->p.file); /* Ignore errors. */
1000 case POOL_GIZMO_TEMP_FILE:
1001 close_temp_file (gizmo->p.file); /* Ignore errors. */
1003 case POOL_GIZMO_SUBPOOL:
1004 gizmo->p.subpool->parent = NULL;
1005 pool_destroy (gizmo->p.subpool);
1007 case POOL_GIZMO_REGISTERED:
1008 gizmo->p.registered.free (gizmo->p.registered.p);
1015 /* Free all the gizmos in POOL. */
1017 free_all_gizmos (struct pool *pool)
1019 struct pool_gizmo *cur, *next;
1021 for (cur = pool->gizmos; cur; cur = next)
1026 pool->gizmos = NULL;
1030 check_gizmo (struct pool *p, struct pool_gizmo *g)
1032 assert (g->pool == p);
1033 assert (g->next == NULL || g->next->prev == g);
1034 assert ((g->prev != NULL && g->prev->next == g)
1035 || (g->prev == NULL && p->gizmos == g));