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