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 */