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