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