pintos-os.org Git - pspp/blob - 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 /* Help identify source of bugs for Checker users. */
 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 within POOL and returns a pointer to the
 248    duplicate. */
 249 char *
 250 pool_strdup (struct pool *pool, const char *string)
 251 {
 252   size_t amt;
 253   void *p;
 254
 255   assert (pool && string);
 256   amt = strlen (string) + 1;
 257
 258   /* Note that strings need not be aligned on any boundary. */
 259   {
 260 #if !DISCRETE_BLOCKS
 261     struct pool_block *const b = pool->blocks;
 262
 263     if (b->ofs + amt <= BLOCK_SIZE)
 264       {
 265         p = ((char *) b) + b->ofs;
 266         b->ofs += amt;
 267       }
 268     else
 269 #endif
 270       p = pool_alloc (pool, amt);
 271   }
 272
 273   memcpy (p, string, amt);
 274   return p;
 275 }
 276 \f
 277 /* Standard allocation routines. */
 278
 279 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
 280    returns a pointer to the beginning of the block.
 281    If POOL is a null pointer, then allocates a normal memory block
 282    with malloc().  */
 283 void *
 284 pool_malloc (struct pool *pool, size_t amt)
 285 {
 286   if (pool != NULL)
 287     {
 288       if (amt != 0)
 289         {
 290           struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
 291           g->type = POOL_GIZMO_MALLOC;
 292           add_gizmo (pool, g);
 293
 294           return ((char *) g) + POOL_GIZMO_SIZE;
 295         }
 296       else
 297         return NULL;
 298     }
 299   else
 300     return xmalloc (amt);
 301 }
 302
 303 /* Changes the allocation size of the specified memory block P managed
 304    by POOL to AMT bytes and returns a pointer to the beginning of the
 305    block.
 306    If POOL is a null pointer, then the block is reallocated in the
 307    usual way with realloc(). */
 308 void *
 309 pool_realloc (struct pool *pool, void *p, size_t amt)
 310 {
 311   if (pool != NULL)
 312     {
 313       if (p != NULL)
 314         {
 315           if (amt != 0)
 316             {
 317               struct pool_gizmo *g;
 318
 319               g = xrealloc (((char *) p) - POOL_GIZMO_SIZE,
 320                             amt + POOL_GIZMO_SIZE);
 321               if (g->next)
 322                 g->next->prev = g;
 323               if (g->prev)
 324                 g->prev->next = g;
 325               else
 326                 pool->gizmos = g;
 327
 328               return ((char *) g) + POOL_GIZMO_SIZE;
 329             }
 330           else
 331             {
 332               pool_free (pool, p);
 333               return NULL;
 334             }
 335         }
 336       else
 337         return pool_malloc (pool, amt);
 338     }
 339   else
 340     return xrealloc (p, amt);
 341 }
 342
 343 /* Frees block P managed by POOL.
 344    If POOL is a null pointer, then the block is freed as usual with
 345    free(). */
 346 void
 347 pool_free (struct pool *pool, void *p)
 348 {
 349   if (pool != NULL && p != NULL)
 350     {
 351       struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
 352       delete_gizmo (pool, g);
 353       free (g);
 354     }
 355   else
 356     free (p);
 357 }
 358 \f
 359 /* Gizmo allocations. */
 360
 361 /* Creates and returns a pool as a subpool of POOL.
 362    The subpool will be destroyed automatically when POOL is destroyed.
 363    It may also be destroyed explicitly in advance. */
 364 struct pool *
 365 pool_create_subpool (struct pool *pool)
 366 {
 367   struct pool *subpool;
 368   struct pool_gizmo *g;
 369
 370   assert (pool != NULL);
 371   subpool = pool_create ();
 372   subpool->parent = pool;
 373
 374   g = (void *) (((char *) subpool) + subpool->blocks->ofs);
 375   subpool->blocks->ofs += POOL_GIZMO_SIZE;
 376
 377   g->type = POOL_GIZMO_SUBPOOL;
 378   g->p.subpool = subpool;
 379
 380   add_gizmo (pool, g);
 381
 382   return subpool;
 383 }
 384
 385 /* Opens file FILENAME with mode MODE and returns a handle to it
 386    if successful or a null pointer if not.
 387    The file will be closed automatically when POOL is destroyed, or it
 388    may be closed explicitly in advance using pool_fclose. */
 389 FILE *
 390 pool_fopen (struct pool *pool, const char *filename, const char *mode)
 391 {
 392   FILE *f;
 393
 394   assert (pool && filename && mode);
 395   f = fopen (filename, mode);
 396   if (f == NULL)
 397     return NULL;
 398
 399   {
 400     struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
 401     g->type = POOL_GIZMO_FILE;
 402     g->p.file = f;
 403     add_gizmo (pool, g);
 404   }
 405
 406   return f;
 407 }
 408
 409 /* Closes file FILE managed by POOL. */
 410 int
 411 pool_fclose (struct pool *pool, FILE *file)
 412 {
 413   assert (pool && file);
 414   if (fclose (file) == EOF)
 415     return EOF;
 416
 417   {
 418     struct pool_gizmo *g;
 419
 420     for (g = pool->gizmos; g; g = g->next)
 421       if (g->type == POOL_GIZMO_FILE && g->p.file == file)
 422         {
 423           delete_gizmo (pool, g);
 424           break;
 425         }
 426   }
 427
 428   return 0;
 429 }
 430 \f
 431 /* Registers FREE to be called with argument P.
 432    P should be unique among those registered in POOL so that it can be
 433    uniquely identified by pool_unregister().
 434    If not unregistered, FREE will be called with argument P when POOL
 435    is destroyed. */
 436 void
 437 pool_register (struct pool *pool, void (*free) (void *), void *p)
 438 {
 439   assert (pool && free && p);
 440
 441   {
 442     struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
 443     g->type = POOL_GIZMO_REGISTERED;
 444     g->p.registered.free = free;
 445     g->p.registered.p = p;
 446     add_gizmo (pool, g);
 447   }
 448 }
 449
 450 /* Unregisters previously registered P from POOL.
 451    Returns nonzero only if P was found to be registered in POOL. */
 452 int
 453 pool_unregister (struct pool *pool, void *p)
 454 {
 455   assert (pool && p);
 456
 457   {
 458     struct pool_gizmo *g;
 459
 460     for (g = pool->gizmos; g; g = g->next)
 461       if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
 462         {
 463           delete_gizmo (pool, g);
 464           return 1;
 465         }
 466   }
 467
 468   return 0;
 469 }
 470 \f
 471 /* Partial freeing. */
 472
 473 /* Notes the state of POOL into MARK so that it may be restored
 474    by a call to pool_release(). */
 475 void
 476 pool_mark (struct pool *pool, struct pool_mark *mark)
 477 {
 478   assert (pool && mark);
 479
 480   mark->block = pool->blocks;
 481   mark->ofs = pool->blocks->ofs;
 482
 483   mark->serial = serial;
 484 }
 485
 486 /* Restores to POOL the state recorded in MARK. */
 487 void
 488 pool_release (struct pool *pool, const struct pool_mark *mark)
 489 {
 490   assert (pool && mark);
 491
 492   {
 493     struct pool_gizmo *cur, *next;
 494
 495     for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
 496       {
 497         next = cur->next;
 498         free_gizmo (cur);
 499       }
 500
 501     if (cur != NULL)
 502       {
 503         cur->prev = NULL;
 504         pool->gizmos = cur;
 505       }
 506     else
 507       pool->gizmos = NULL;
 508   }
 509
 510   {
 511     struct pool_block *cur, *next, *last;
 512
 513     last = pool->blocks->prev;
 514     for (cur = pool->blocks; cur != mark->block; cur = next)
 515       {
 516         next = cur->next;
 517         assert (next != cur);
 518
 519         free (cur);
 520       }
 521
 522     cur->prev = last;
 523     last->next = pool->blocks = cur;
 524
 525     cur->ofs = mark->ofs;
 526   }
 527 }
 528 \f
 529 /* Private functions. */
 530
 531 /* Adds GIZMO at the beginning of POOL's gizmo list. */
 532 static void
 533 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
 534 {
 535   assert (pool && gizmo);
 536
 537   gizmo->next = pool->gizmos;
 538   gizmo->prev = NULL;
 539   if (pool->gizmos)
 540     pool->gizmos->prev = gizmo;
 541   pool->gizmos = gizmo;
 542
 543   gizmo->serial = serial++;
 544 }
 545
 546 /* Removes GIZMO from POOL's gizmo list. */
 547 static void
 548 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
 549 {
 550   assert (pool && gizmo);
 551
 552   if (gizmo->prev)
 553     gizmo->prev->next = gizmo->next;
 554   else
 555     pool->gizmos = gizmo->next;
 556   if (gizmo->next)
 557     gizmo->next->prev = gizmo->prev;
 558 }
 559
 560 /* Frees any of GIZMO's internal state.
 561    GIZMO's data must not be referenced after calling this function. */
 562 static void
 563 free_gizmo (struct pool_gizmo *gizmo)
 564 {
 565   assert (gizmo != NULL);
 566
 567   switch (gizmo->type)
 568     {
 569     case POOL_GIZMO_MALLOC:
 570       free (gizmo);
 571       break;
 572     case POOL_GIZMO_FILE:
 573       fclose (gizmo->p.file);   /* Ignore errors. */
 574       break;
 575     case POOL_GIZMO_SUBPOOL:
 576       gizmo->p.subpool->parent = NULL;
 577       pool_destroy (gizmo->p.subpool);
 578       break;
 579     case POOL_GIZMO_REGISTERED:
 580       gizmo->p.registered.free (gizmo->p.registered.p);
 581       break;
 582     default:
 583       assert (0);
 584     }
 585 }
 586 \f
 587 /* Memory allocation. */
 588
 589 #if !PSPP
 590 /* Allocates SIZE bytes of space using malloc().  Aborts if out of
 591    memory. */
 592 static void *
 593 xmalloc (size_t size)
 594 {
 595   void *vp;
 596   if (size == 0)
 597     return NULL;
 598   vp = malloc (size);
 599   assert (vp != NULL);
 600   if (vp == NULL)
 601     abort ();
 602   return vp;
 603 }
 604
 605 /* Reallocates P to be SIZE bytes long using realloc().  Aborts if out
 606    of memory. */
 607 static void *
 608 xrealloc (void *p, size_t size)
 609 {
 610   if (p == NULL)
 611     return xmalloc (size);
 612   if (size == 0)
 613     {
 614       free (p);
 615       return NULL;
 616     }
 617   p = realloc (p, size);
 618   if (p == NULL)
 619     abort ();
 620   return p;
 621 }
 622 #endif /* !PSPP */
 623 \f
 624 /* Self-test routine. */
 625
 626 #if SELF_TEST
 627 #include <errno.h>
 628 #include <stdio.h>
 629 #include <stdlib.h>
 630 #include <string.h>
 631 #include <time.h>
 632
 633 #define N_ITERATIONS 8192
 634 #define N_FILES 16
 635
 636 /* Self-test routine.
 637    This is not exhaustive, but it can be useful. */
 638 int
 639 main (int argc, char **argv)
 640 {
 641   int seed;
 642
 643   if (argc == 2)
 644     seed = atoi (argv[1]);
 645   else
 646     seed = time (0) * 257 % 32768;
 647
 648   for (;;)
 649     {
 650       struct pool *pool;
 651       struct pool_mark m1, m2;
 652       FILE *files[N_FILES];
 653       int cur_file;
 654       long i;
 655
 656       printf ("Random number seed: %d\n", seed);
 657       srand (seed++);
 658
 659       printf ("Creating pool...\n");
 660       pool = pool_create ();
 661
 662       printf ("Marking pool state...\n");
 663       pool_mark (pool, &m1);
 664
 665       printf ("    Populating pool with random-sized small objects...\n");
 666       for (i = 0; i < N_ITERATIONS; i++)
 667         {
 668           size_t size = rand () % MAX_SUBALLOC;
 669           void *p = pool_alloc (pool, size);
 670           memset (p, 0, size);
 671         }
 672
 673       printf ("    Marking pool state...\n");
 674       pool_mark (pool, &m2);
 675
 676       printf ("       Populating pool with random-sized small "
 677               "and large objects...\n");
 678       for (i = 0; i < N_ITERATIONS; i++)
 679         {
 680           size_t size = rand () % (2 * MAX_SUBALLOC);
 681           void *p = pool_alloc (pool, size);
 682           memset (p, 0, size);
 683         }
 684
 685       printf ("    Releasing pool state...\n");
 686       pool_release (pool, &m2);
 687
 688       printf ("    Populating pool with random objects and gizmos...\n");
 689       for (i = 0; i < N_FILES; i++)
 690         files[i] = NULL;
 691       cur_file = 0;
 692       for (i = 0; i < N_ITERATIONS; i++)
 693         {
 694           int type = rand () % 32;
 695
 696           if (type == 0)
 697             {
 698               if (files[cur_file] != NULL
 699                   && EOF == pool_fclose (pool, files[cur_file]))
 700                 printf ("error on fclose: %s\n", strerror (errno));
 701
 702               files[cur_file] = pool_fopen (pool, "/dev/null", "r");
 703
 704               if (++cur_file >= N_FILES)
 705                 cur_file = 0;
 706             }
 707           else if (type == 1)
 708             pool_create_subpool (pool);
 709           else
 710             {
 711               size_t size = rand () % (2 * MAX_SUBALLOC);
 712               void *p = pool_alloc (pool, size);
 713               memset (p, 0, size);
 714             }
 715         }
 716
 717       printf ("Releasing pool state...\n");
 718       pool_release (pool, &m1);
 719
 720       printf ("Destroying pool...\n");
 721       pool_destroy (pool);
 722
 723       putchar ('\n');
 724     }
 725 }
 726
 727 #endif /* SELF_TEST */
 728
 729 /*
 730    Local variables:
 731    compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o pool_test pool.c"
 732    End:
 733 */