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