Adopt use of gnulib for portability.
[pspp] / src / pool.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 2000 Free Software Foundation, Inc.
3    Written by Ben Pfaff <blp@gnu.org>.
4
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.
9
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.
14
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
18    02110-1301, USA. */
19
20 #include <config.h>
21 #include "pool.h"
22 #include "command.h"
23 #include "error.h"
24 #include <stdlib.h>
25 #include "alloc.h"
26 #include "str.h"
27
28 /* Fast, low-overhead memory block suballocator. */
29 struct pool
30   {
31     struct pool *parent;        /* Pool of which this pool is a subpool. */
32     struct pool_block *blocks;  /* Blocks owned by the pool. */
33     struct pool_gizmo *gizmos;  /* Other stuff owned by the pool. */
34   };
35
36 /* Pool block. */
37 struct pool_block 
38   {
39     struct pool_block *prev;
40     struct pool_block *next;
41     size_t ofs;
42   };
43
44 /* Gizmo types. */
45 enum
46   {
47     POOL_GIZMO_MALLOC,
48     POOL_GIZMO_FILE,
49     POOL_GIZMO_SUBPOOL,
50     POOL_GIZMO_REGISTERED,
51   };
52
53 /* Pool routines can maintain objects (`gizmos') as well as doing
54    suballocation.  
55    This structure is used to keep track of them. */
56 struct pool_gizmo
57   {
58     struct pool *pool;
59     struct pool_gizmo *prev;
60     struct pool_gizmo *next;
61
62     long serial;                /* Serial number. */
63     int type;                   /* Type of this gizmo. */
64
65     /* Type-dependent info. */
66     union
67       {
68         FILE *file;             /* POOL_GIZMO_FILE. */
69         struct pool *subpool;   /* POOL_GIZMO_SUBPOOL. */
70
71         /* POOL_GIZMO_REGISTERED. */
72         struct
73           {
74             void (*free) (void *p);
75             void *p;
76           }
77         registered;
78       }
79     p;
80   };
81
82 /* Rounds X up to the next multiple of Y. */
83 #ifndef ROUND_UP
84 #define ROUND_UP(X, Y)                          \
85         (((X) + ((Y) - 1)) / (Y) * (Y))
86 #endif
87
88 /* Types that provide typically useful alignment sizes. */
89 union align
90   {
91     void *op;
92     void (*fp) (void);
93     long l;
94     double d;
95   };
96
97 /* This should be the alignment size used by malloc().  The size of
98    the union above is correct, if not optimal, in all known cases. */
99 #if defined (i386) || defined (__i386__)
100 #define ALIGN_SIZE 4            /* Save some extra memory. */
101 #else
102 #define ALIGN_SIZE sizeof (union align)
103 #endif
104
105 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
106    suballocation of blocks.  This is useful under memory
107    debuggers like Checker or valgrind because it allows the
108    source location of bugs to be more accurately pinpointed.
109
110    On the other hand, if we're testing the library, then we want to
111    test the library's real functionality, not its crippled, slow,
112    simplified functionality. */
113 /*#define DISCRETE_BLOCKS 1*/
114
115 /* Size of each block allocated in the pool, in bytes.
116    Should be at least 1k. */
117 #ifndef BLOCK_SIZE
118 #define BLOCK_SIZE 1024
119 #endif
120
121 /* Maximum size of a suballocated block.  Larger blocks are allocated
122    directly with malloc() to avoid memory wastage at the end of a
123    suballocation block. */
124 #ifndef MAX_SUBALLOC
125 #define MAX_SUBALLOC 64
126 #endif
127
128 /* Sizes of some structures with alignment padding included. */
129 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
130 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
131 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
132
133 /* Serial number used to keep track of gizmos for mark/release. */
134 static long serial = 0;
135
136 /* Prototypes. */
137 static void add_gizmo (struct pool *, struct pool_gizmo *);
138 static void free_gizmo (struct pool_gizmo *);
139 static void free_all_gizmos (struct pool *pool);
140 static void delete_gizmo (struct pool *, struct pool_gizmo *);
141 static void check_gizmo (struct pool *, struct pool_gizmo *);
142 \f
143 /* General routines. */
144
145 /* Creates and returns a new memory pool, which allows malloc()'d
146    blocks to be suballocated in a time- and space-efficient manner.
147    The entire contents of the memory pool are freed at once.
148
149    In addition, other objects can be associated with a memory pool.
150    These are released when the pool is destroyed. */
151 struct pool *
152 pool_create (void)
153 {
154   struct pool_block *block;
155   struct pool *pool;
156
157   block = xmalloc (BLOCK_SIZE);
158   block->prev = block->next = block;
159   block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
160   
161   pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
162   pool->parent = NULL;
163   pool->blocks = block;
164   pool->gizmos = NULL;
165
166   return pool;
167 }
168
169 /* Destroy the specified pool, including all subpools. */
170 void
171 pool_destroy (struct pool *pool)
172 {
173   if (pool == NULL)
174     return;
175
176   /* Remove this pool from its parent's list of gizmos. */
177   if (pool->parent) 
178     delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
179   
180   free_all_gizmos (pool);
181
182   /* Free all the memory. */
183   {
184     struct pool_block *cur, *next;
185
186     pool->blocks->prev->next = NULL;
187     for (cur = pool->blocks; cur; cur = next)
188       {
189         next = cur->next;
190         free (cur);
191       }
192   }
193 }
194
195 /* Release all the memory and gizmos in POOL.
196    Blocks are not given back with free() but kept for later
197    allocations.  To give back memory, use a subpool instead. */ 
198 void
199 pool_clear (struct pool *pool) 
200 {
201   free_all_gizmos (pool);
202
203   /* Zero out block sizes. */
204   {
205     struct pool_block *cur;
206     
207     cur = pool->blocks;
208     do
209       {
210         cur->ofs = POOL_BLOCK_SIZE;
211         if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) 
212           {
213             cur->ofs += POOL_SIZE;
214             if (pool->parent != NULL)
215               cur->ofs += POOL_GIZMO_SIZE; 
216           }
217         cur = cur->next;
218       }
219     while (cur != pool->blocks);
220   }
221 }
222 \f
223 /* Suballocation routines. */
224
225 /* Allocates a memory region AMT bytes in size from POOL and returns a
226    pointer to the region's start. */
227 void *
228 pool_alloc (struct pool *pool, size_t amt)
229 {
230   assert (pool != NULL);
231   
232 #ifndef DISCRETE_BLOCKS
233   if (amt <= MAX_SUBALLOC)
234     {
235       /* If there is space in this block, take it. */
236       struct pool_block *b = pool->blocks;
237       b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
238       if (b->ofs + amt <= BLOCK_SIZE)
239         {
240           void *const p = ((char *) b) + b->ofs;
241           b->ofs += amt;
242           return p;
243         }
244
245       /* No space in this block, so we must make other
246          arrangements. */
247       if (b->next->ofs == 0) 
248         {
249           /* The next block is empty.  Use it. */
250           b = b->next;
251           b->ofs = POOL_BLOCK_SIZE;
252           if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
253             b->ofs += POOL_SIZE;
254         }
255       else 
256         {
257           /* Create a new block at the start of the list. */
258           b = xmalloc (BLOCK_SIZE);
259           b->next = pool->blocks;
260           b->prev = pool->blocks->prev;
261           b->ofs = POOL_BLOCK_SIZE;
262           pool->blocks->prev->next = b;
263           pool->blocks->prev = b;
264         }
265       pool->blocks = b;
266
267       /* Allocate space from B. */
268       b->ofs += amt;
269       return ((char *) b) + b->ofs - amt;
270     }
271   else
272 #endif
273     return pool_malloc (pool, amt);
274 }
275
276 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
277    returns the new copy. */
278 void *
279 pool_clone (struct pool *pool, const void *buffer, size_t size)
280 {
281   void *block = pool_alloc (pool, size);
282   memcpy (block, buffer, size);
283   return block;
284 }
285
286 /* Duplicates STRING, which has LENGTH characters, within POOL,
287    and returns a pointer to the duplicate.  LENGTH should not
288    include the null terminator, which is always added to the
289    duplicate.  For use only with strings, because the returned
290    pointere may not be aligned properly for other types. */
291 char *
292 pool_strndup (struct pool *pool, const char *string, size_t length)
293 {
294   size_t size;
295   char *copy;
296
297   assert (pool && string);
298   size = length + 1;
299
300   /* Note that strings need not be aligned on any boundary. */
301 #ifndef DISCRETE_BLOCKS
302   {
303     struct pool_block *const b = pool->blocks;
304
305     if (b->ofs + size <= BLOCK_SIZE)
306       {
307         copy = ((char *) b) + b->ofs;
308         b->ofs += size;
309       }
310     else
311       copy = pool_alloc (pool, size);
312   }
313 #else
314   copy = pool_alloc (pool, size);
315 #endif
316
317   memcpy (copy, string, length);
318   copy[length] = '\0';
319   return copy;
320 }
321
322 /* Duplicates null-terminated STRING, within POOL, and returns a
323    pointer to the duplicate.  For use only with strings, because
324    the returned pointere may not be aligned properly for other
325    types. */
326 char *
327 pool_strdup (struct pool *pool, const char *string) 
328 {
329   return pool_strndup (pool, string, strlen (string));
330 }
331 \f
332 /* Standard allocation routines. */
333
334 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
335    returns a pointer to the beginning of the block.
336    If POOL is a null pointer, then allocates a normal memory block
337    with malloc().  */
338 void *
339 pool_malloc (struct pool *pool, size_t amt)
340 {
341   if (pool != NULL)
342     {
343       if (amt != 0)
344         {
345           struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
346           g->type = POOL_GIZMO_MALLOC;
347           add_gizmo (pool, g);
348
349           return ((char *) g) + POOL_GIZMO_SIZE;
350         }
351       else
352         return NULL;
353     }
354   else
355     return xmalloc (amt);
356 }
357
358 /* Changes the allocation size of the specified memory block P managed
359    by POOL to AMT bytes and returns a pointer to the beginning of the
360    block.
361    If POOL is a null pointer, then the block is reallocated in the
362    usual way with realloc(). */
363 void *
364 pool_realloc (struct pool *pool, void *p, size_t amt)
365 {
366   if (pool != NULL)
367     {
368       if (p != NULL)
369         {
370           if (amt != 0)
371             {
372               struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
373               check_gizmo (pool, g);
374
375               g = xrealloc (g, amt + POOL_GIZMO_SIZE);
376               if (g->next)
377                 g->next->prev = g;
378               if (g->prev)
379                 g->prev->next = g;
380               else
381                 pool->gizmos = g;
382               check_gizmo (pool, g);
383
384               return ((char *) g) + POOL_GIZMO_SIZE;
385             }
386           else
387             {
388               pool_free (pool, p);
389               return NULL;
390             }
391         }
392       else
393         return pool_malloc (pool, amt);
394     }
395   else
396     return xrealloc (p, amt);
397 }
398
399 /* Frees block P managed by POOL.
400    If POOL is a null pointer, then the block is freed as usual with
401    free(). */
402 void
403 pool_free (struct pool *pool, void *p)
404 {
405   if (pool != NULL && p != NULL)
406     {
407       struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
408       check_gizmo (pool, g);
409       delete_gizmo (pool, g);
410       free (g);
411     }
412   else
413     free (p);
414 }
415 \f
416 /* Gizmo allocations. */
417
418 /* Creates and returns a pool as a subpool of POOL.
419    The subpool will be destroyed automatically when POOL is destroyed.
420    It may also be destroyed explicitly in advance. */
421 struct pool *
422 pool_create_subpool (struct pool *pool)
423 {
424   struct pool *subpool;
425   struct pool_gizmo *g;
426
427   assert (pool != NULL);
428   subpool = pool_create ();
429   subpool->parent = pool;
430
431   g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
432   subpool->blocks->ofs += POOL_GIZMO_SIZE;
433   
434   g->type = POOL_GIZMO_SUBPOOL;
435   g->p.subpool = subpool;
436
437   add_gizmo (pool, g);
438
439   return subpool;
440 }
441
442 /* Opens file FILENAME with mode MODE and returns a handle to it
443    if successful or a null pointer if not.
444    The file will be closed automatically when POOL is destroyed, or it
445    may be closed explicitly in advance using pool_fclose. */
446 FILE *
447 pool_fopen (struct pool *pool, const char *filename, const char *mode)
448 {
449   FILE *f;
450
451   assert (pool && filename && mode);
452   f = fopen (filename, mode);
453   if (f == NULL)
454     return NULL;
455
456   {
457     struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
458     g->type = POOL_GIZMO_FILE;
459     g->p.file = f;
460     add_gizmo (pool, g);
461   }
462
463   return f;
464 }
465
466 /* Closes file FILE managed by POOL. */
467 int
468 pool_fclose (struct pool *pool, FILE *file)
469 {
470   assert (pool && file);
471   if (fclose (file) == EOF)
472     return EOF;
473   
474   {
475     struct pool_gizmo *g;
476
477     for (g = pool->gizmos; g; g = g->next)
478       if (g->type == POOL_GIZMO_FILE && g->p.file == file)
479         {
480           delete_gizmo (pool, g);
481           break;
482         }
483   }
484   
485   return 0;
486 }
487 \f
488 /* Registers FREE to be called with argument P.
489    P should be unique among those registered in POOL so that it can be
490    uniquely identified by pool_unregister().
491    If not unregistered, FREE will be called with argument P when POOL
492    is destroyed. */
493 void
494 pool_register (struct pool *pool, void (*free) (void *), void *p)
495 {
496   assert (pool && free && p);
497
498   {
499     struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
500     g->type = POOL_GIZMO_REGISTERED;
501     g->p.registered.free = free;
502     g->p.registered.p = p;
503     add_gizmo (pool, g);
504   }
505 }
506
507 /* Unregisters previously registered P from POOL.
508    Returns nonzero only if P was found to be registered in POOL. */
509 int
510 pool_unregister (struct pool *pool, void *p)
511 {
512   assert (pool && p);
513   
514   {
515     struct pool_gizmo *g;
516
517     for (g = pool->gizmos; g; g = g->next)
518       if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
519         {
520           delete_gizmo (pool, g);
521           return 1;
522         }
523   }
524   
525   return 0;
526 }
527 \f
528 /* Partial freeing. */
529
530 /* Notes the state of POOL into MARK so that it may be restored
531    by a call to pool_release(). */
532 void
533 pool_mark (struct pool *pool, struct pool_mark *mark)
534 {
535   assert (pool && mark);
536
537   mark->block = pool->blocks;
538   mark->ofs = pool->blocks->ofs;
539
540   mark->serial = serial;
541 }
542
543 /* Restores to POOL the state recorded in MARK.
544    Emptied blocks are not given back with free() but kept for
545    later allocations.  To get that behavior, use a subpool
546    instead. */ 
547 void
548 pool_release (struct pool *pool, const struct pool_mark *mark)
549 {
550   assert (pool && mark);
551   
552   {
553     struct pool_gizmo *cur, *next;
554
555     for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
556       {
557         next = cur->next;
558         free_gizmo (cur);
559       }
560
561     if (cur != NULL)
562       {
563         cur->prev = NULL;
564         pool->gizmos = cur;
565       }
566     else
567       pool->gizmos = NULL;
568   }
569   
570   {
571     struct pool_block *cur;
572
573     for (cur = pool->blocks; cur != mark->block; cur = cur->next) 
574       {
575         cur->ofs = POOL_BLOCK_SIZE;
576         if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool) 
577           {
578             cur->ofs += POOL_SIZE;
579             if (pool->parent != NULL)
580               cur->ofs += POOL_GIZMO_SIZE; 
581           }
582       }
583     pool->blocks = mark->block;
584     pool->blocks->ofs = mark->ofs;
585   }
586 }
587 \f
588 /* Private functions. */
589
590 /* Adds GIZMO at the beginning of POOL's gizmo list. */
591 static void
592 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
593 {
594   assert (pool && gizmo);
595
596   gizmo->pool = pool;
597   gizmo->next = pool->gizmos;
598   gizmo->prev = NULL;
599   if (pool->gizmos)
600     pool->gizmos->prev = gizmo;
601   pool->gizmos = gizmo;
602
603   gizmo->serial = serial++;
604
605   check_gizmo (pool, gizmo);
606 }
607  
608 /* Removes GIZMO from POOL's gizmo list. */
609 static void
610 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
611 {
612   assert (pool && gizmo);
613
614   check_gizmo (pool, gizmo);
615
616   if (gizmo->prev)
617     gizmo->prev->next = gizmo->next;
618   else
619     pool->gizmos = gizmo->next;
620   if (gizmo->next)
621     gizmo->next->prev = gizmo->prev;
622 }
623
624 /* Frees any of GIZMO's internal state.
625    GIZMO's data must not be referenced after calling this function. */
626 static void
627 free_gizmo (struct pool_gizmo *gizmo)
628 {
629   assert (gizmo != NULL);
630
631   switch (gizmo->type)
632     {
633     case POOL_GIZMO_MALLOC:
634       free (gizmo);
635       break;
636     case POOL_GIZMO_FILE:
637       fclose (gizmo->p.file);   /* Ignore errors. */
638       break;
639     case POOL_GIZMO_SUBPOOL:
640       gizmo->p.subpool->parent = NULL;
641       pool_destroy (gizmo->p.subpool);
642       break;
643     case POOL_GIZMO_REGISTERED:
644       gizmo->p.registered.free (gizmo->p.registered.p);
645       break;
646     default:
647       assert (0);
648     }
649 }
650
651 /* Free all the gizmos in POOL. */
652 static void
653 free_all_gizmos (struct pool *pool) 
654 {
655   struct pool_gizmo *cur, *next;
656
657   for (cur = pool->gizmos; cur; cur = next)
658     {
659       next = cur->next;
660       free_gizmo (cur);
661     }
662   pool->gizmos = NULL;
663 }
664
665 static void
666 check_gizmo (struct pool *p, struct pool_gizmo *g) 
667 {
668   assert (g->pool == p);
669   assert (g->next == NULL || g->next->prev == g);
670   assert ((g->prev != NULL && g->prev->next == g)
671           || (g->prev == NULL && p->gizmos == g));
672
673 }
674 \f
675 /* Self-test routine. */
676
677 #include <errno.h>
678 #include <stdio.h>
679 #include <stdlib.h>
680 #include <string.h>
681 #include <time.h>
682
683 #define N_ITERATIONS 8192
684 #define N_FILES 16
685
686 /* Self-test routine.
687    This is not exhaustive, but it can be useful. */
688 int
689 cmd_debug_pool (void)
690 {
691   int seed = time (0) * 257 % 32768;
692
693   for (;;)
694     {
695       struct pool *pool;
696       struct pool_mark m1, m2;
697       FILE *files[N_FILES];
698       int cur_file;
699       long i;
700
701       printf ("Random number seed: %d\n", seed);
702       srand (seed++);
703
704       printf ("Creating pool...\n");
705       pool = pool_create ();
706
707       printf ("Marking pool state...\n");
708       pool_mark (pool, &m1);
709
710       printf ("    Populating pool with random-sized small objects...\n");
711       for (i = 0; i < N_ITERATIONS; i++)
712         {
713           size_t size = rand () % MAX_SUBALLOC;
714           void *p = pool_alloc (pool, size);
715           memset (p, 0, size);
716         }
717
718       printf ("    Marking pool state...\n");
719       pool_mark (pool, &m2);
720       
721       printf ("       Populating pool with random-sized small "
722               "and large objects...\n");
723       for (i = 0; i < N_ITERATIONS; i++)
724         {
725           size_t size = rand () % (2 * MAX_SUBALLOC);
726           void *p = pool_alloc (pool, size);
727           memset (p, 0, size);
728         }
729
730       printf ("    Releasing pool state...\n");
731       pool_release (pool, &m2);
732
733       printf ("    Populating pool with random objects and gizmos...\n");
734       for (i = 0; i < N_FILES; i++)
735         files[i] = NULL;
736       cur_file = 0;
737       for (i = 0; i < N_ITERATIONS; i++)
738         {
739           int type = rand () % 32;
740
741           if (type == 0)
742             {
743               if (files[cur_file] != NULL
744                   && EOF == pool_fclose (pool, files[cur_file]))
745                 printf ("error on fclose: %s\n", strerror (errno));
746
747               files[cur_file] = pool_fopen (pool, "/dev/null", "r");
748
749               if (++cur_file >= N_FILES)
750                 cur_file = 0;
751             }
752           else if (type == 1)
753             pool_create_subpool (pool);
754           else 
755             {
756               size_t size = rand () % (2 * MAX_SUBALLOC);
757               void *p = pool_alloc (pool, size);
758               memset (p, 0, size);
759             }
760         }
761       
762       printf ("Releasing pool state...\n");
763       pool_release (pool, &m1);
764
765       printf ("Destroying pool...\n");
766       pool_destroy (pool);
767
768       putchar ('\n');
769     }
770
771   return CMD_SUCCESS;
772 }
773