gcc/alloc-pool.c

   1 /* Functions to support a pool of allocatable objects.
   2    Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007
   3    Free Software Foundation, Inc.
   4    Contributed by Daniel Berlin <dan@cgsoftware.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "alloc-pool.h"
  25 #include "hashtab.h"
  26
  27 #define align_eight(x) (((x+7) >> 3) << 3)
  28
  29 /* The internal allocation object.  */
  30 typedef struct allocation_object_def
  31 {
  32 #ifdef ENABLE_CHECKING
  33   /* The ID of alloc pool which the object was allocated from.  */
  34   ALLOC_POOL_ID_TYPE id;
  35 #endif
  36
  37   union
  38     {
  39       /* The data of the object.  */
  40       char data[1];
  41
  42       /* Because we want any type of data to be well aligned after the ID,
  43          the following elements are here.  They are never accessed so
  44          the allocated object may be even smaller than this structure.  */
  45       char *align_p;
  46       HOST_WIDEST_INT align_i;
  47       long double align_ld;
  48     } u;
  49 } allocation_object;
  50
  51 /* Convert a pointer to allocation_object from a pointer to user data.  */
  52 #define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X)                          \
  53    ((allocation_object *) (((char *) (X))                               \
  54                            - offsetof (allocation_object, u.data)))
  55
  56 /* Convert a pointer to user data from a pointer to allocation_object.  */
  57 #define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X)                          \
  58    ((void *) (((allocation_object *) (X))->u.data))
  59
  60 #ifdef ENABLE_CHECKING
  61 /* Last used ID.  */
  62 static ALLOC_POOL_ID_TYPE last_id;
  63 #endif
  64
  65 #ifdef GATHER_STATISTICS
  66
  67 /* Store information about each particular alloc_pool.  */
  68 struct alloc_pool_descriptor
  69 {
  70   const char *name;
  71   int allocated;
  72   int created;
  73   int peak;
  74   int current;
  75 };
  76
  77 /* Hashtable mapping alloc_pool names to descriptors.  */
  78 static htab_t alloc_pool_hash;
  79
  80 /* Hashtable helpers.  */
  81 static hashval_t
  82 hash_descriptor (const void *p)
  83 {
  84   const struct alloc_pool_descriptor *const d =
  85     (const struct alloc_pool_descriptor * )p;
  86   return htab_hash_pointer (d->name);
  87 }
  88 static int
  89 eq_descriptor (const void *p1, const void *p2)
  90 {
  91   const struct alloc_pool_descriptor *const d =
  92     (const struct alloc_pool_descriptor *) p1;
  93   return d->name == p2;
  94 }
  95
  96 /* For given name, return descriptor, create new if needed.  */
  97 static struct alloc_pool_descriptor *
  98 alloc_pool_descriptor (const char *name)
  99 {
 100   struct alloc_pool_descriptor **slot;
 101
 102   if (!alloc_pool_hash)
 103     alloc_pool_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
 104
 105   slot = (struct alloc_pool_descriptor **)
 106     htab_find_slot_with_hash (alloc_pool_hash, name,
 107                               htab_hash_pointer (name),
 108                               1);
 109   if (*slot)
 110     return *slot;
 111   *slot = XCNEW (struct alloc_pool_descriptor);
 112   (*slot)->name = name;
 113   return *slot;
 114 }
 115 #endif
 116
 117 /* Create a pool of things of size SIZE, with NUM in each block we
 118    allocate.  */
 119
 120 alloc_pool
 121 create_alloc_pool (const char *name, size_t size, size_t num)
 122 {
 123   alloc_pool pool;
 124   size_t header_size;
 125 #ifdef GATHER_STATISTICS
 126   struct alloc_pool_descriptor *desc;
 127 #endif
 128
 129   gcc_assert (name);
 130
 131   /* Make size large enough to store the list header.  */
 132   if (size < sizeof (alloc_pool_list))
 133     size = sizeof (alloc_pool_list);
 134
 135   /* Now align the size to a multiple of 4.  */
 136   size = align_eight (size);
 137
 138 #ifdef ENABLE_CHECKING
 139   /* Add the aligned size of ID.  */
 140   size += offsetof (allocation_object, u.data);
 141 #endif
 142
 143   /* Um, we can't really allocate 0 elements per block.  */
 144   gcc_assert (num);
 145
 146   /* Allocate memory for the pool structure.  */
 147   pool = XNEW (struct alloc_pool_def);
 148
 149   /* Now init the various pieces of our pool structure.  */
 150   pool->name = /*xstrdup (name)*/name;
 151 #ifdef GATHER_STATISTICS
 152   desc = alloc_pool_descriptor (name);
 153   desc->created++;
 154 #endif
 155   pool->elt_size = size;
 156   pool->elts_per_block = num;
 157
 158   /* List header size should be a multiple of 8.  */
 159   header_size = align_eight (sizeof (struct alloc_pool_list_def));
 160
 161   pool->block_size = (size * num) + header_size;
 162   pool->returned_free_list = NULL;
 163   pool->virgin_free_list = NULL;
 164   pool->virgin_elts_remaining = 0;
 165   pool->elts_allocated = 0;
 166   pool->elts_free = 0;
 167   pool->blocks_allocated = 0;
 168   pool->block_list = NULL;
 169
 170 #ifdef ENABLE_CHECKING
 171   /* Increase the last used ID and use it for this pool.
 172      ID == 0 is used for free elements of pool so skip it.  */
 173   last_id++;
 174   if (last_id == 0)
 175     last_id++;
 176
 177   pool->id = last_id;
 178 #endif
 179
 180   return (pool);
 181 }
 182
 183 /* Free all memory allocated for the given memory pool.  */
 184 void
 185 empty_alloc_pool (alloc_pool pool)
 186 {
 187   alloc_pool_list block, next_block;
 188 #ifdef GATHER_STATISTICS
 189   struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 190 #endif
 191
 192   gcc_assert (pool);
 193
 194   /* Free each block allocated to the pool.  */
 195   for (block = pool->block_list; block != NULL; block = next_block)
 196     {
 197       next_block = block->next;
 198       free (block);
 199 #ifdef GATHER_STATISTICS
 200       desc->current -= pool->block_size;
 201 #endif
 202     }
 203
 204   pool->returned_free_list = NULL;
 205   pool->virgin_free_list = NULL;
 206   pool->virgin_elts_remaining = 0;
 207   pool->elts_allocated = 0;
 208   pool->elts_free = 0;
 209   pool->blocks_allocated = 0;
 210   pool->block_list = NULL;
 211 }
 212
 213 /* Free all memory allocated for the given memory pool and the pool itself.  */
 214 void
 215 free_alloc_pool (alloc_pool pool)
 216 {
 217   /* First empty the pool.  */
 218   empty_alloc_pool (pool);
 219 #ifdef ENABLE_CHECKING
 220   memset (pool, 0xaf, sizeof (*pool));
 221 #endif
 222   /* Lastly, free the pool.  */
 223   free (pool);
 224 }
 225
 226 /* Frees the alloc_pool, if it is empty and zero *POOL in this case.  */
 227 void
 228 free_alloc_pool_if_empty (alloc_pool *pool)
 229 {
 230   if ((*pool)->elts_free == (*pool)->elts_allocated)
 231     {
 232       free_alloc_pool (*pool);
 233       *pool = NULL;
 234     }
 235 }
 236
 237 /* Allocates one element from the pool specified.  */
 238 void *
 239 pool_alloc (alloc_pool pool)
 240 {
 241   alloc_pool_list header;
 242 #ifdef GATHER_STATISTICS
 243   struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 244
 245   desc->allocated+=pool->elt_size;
 246 #endif
 247
 248   gcc_assert (pool);
 249
 250   /* If there are no more free elements, make some more!.  */
 251   if (!pool->returned_free_list)
 252     {
 253       char *block;
 254       if (!pool->virgin_elts_remaining)
 255         {
 256           alloc_pool_list block_header;
 257
 258           /* Make the block.  */
 259           block = XNEWVEC (char, pool->block_size);
 260           block_header = (alloc_pool_list) block;
 261           block += align_eight (sizeof (struct alloc_pool_list_def));
 262 #ifdef GATHER_STATISTICS
 263           desc->current += pool->block_size;
 264           if (desc->peak < desc->current)
 265             desc->peak = desc->current;
 266 #endif
 267
 268           /* Throw it on the block list.  */
 269           block_header->next = pool->block_list;
 270           pool->block_list = block_header;
 271
 272           /* Make the block available for allocation.  */
 273           pool->virgin_free_list = block;
 274           pool->virgin_elts_remaining = pool->elts_per_block;
 275
 276           /* Also update the number of elements we have free/allocated, and
 277              increment the allocated block count.  */
 278           pool->elts_allocated += pool->elts_per_block;
 279           pool->elts_free += pool->elts_per_block;
 280           pool->blocks_allocated += 1;
 281         }
 282
 283
 284       /* We now know that we can take the first elt off the virgin list and
 285          put it on the returned list. */
 286       block = pool->virgin_free_list;
 287       header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
 288       header->next = NULL;
 289 #ifdef ENABLE_CHECKING
 290       /* Mark the element to be free.  */
 291       ((allocation_object *) block)->id = 0;
 292 #endif
 293       pool->returned_free_list = header;
 294       pool->virgin_free_list += pool->elt_size;
 295       pool->virgin_elts_remaining--;
 296
 297     }
 298
 299   /* Pull the first free element from the free list, and return it.  */
 300   header = pool->returned_free_list;
 301   pool->returned_free_list = header->next;
 302   pool->elts_free--;
 303
 304 #ifdef ENABLE_CHECKING
 305   /* Set the ID for element.  */
 306   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
 307 #endif
 308
 309   return ((void *) header);
 310 }
 311
 312 /* Puts PTR back on POOL's free list.  */
 313 void
 314 pool_free (alloc_pool pool, void *ptr)
 315 {
 316   alloc_pool_list header;
 317
 318   gcc_assert (ptr);
 319
 320 #ifdef ENABLE_CHECKING
 321   /* Check whether the PTR was allocated from POOL.  */
 322   gcc_assert (pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id);
 323
 324   memset (ptr, 0xaf, pool->elt_size - offsetof (allocation_object, u.data));
 325
 326   /* Mark the element to be free.  */
 327   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
 328 #else
 329   /* Check if we free more than we allocated, which is Bad (TM).  */
 330   gcc_assert (pool->elts_free < pool->elts_allocated);
 331 #endif
 332
 333   header = (alloc_pool_list) ptr;
 334   header->next = pool->returned_free_list;
 335   pool->returned_free_list = header;
 336   pool->elts_free++;
 337 }
 338 /* Output per-alloc_pool statistics.  */
 339 #ifdef GATHER_STATISTICS
 340
 341 /* Used to accumulate statistics about alloc_pool sizes.  */
 342 struct output_info
 343 {
 344   int count;
 345   int size;
 346 };
 347
 348 /* Called via htab_traverse.  Output alloc_pool descriptor pointed out by SLOT
 349    and update statistics.  */
 350 static int
 351 print_statistics (void **slot, void *b)
 352 {
 353   struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot;
 354   struct output_info *i = (struct output_info *) b;
 355
 356   if (d->allocated)
 357     {
 358       fprintf (stderr, "%-21s %6d %10d %10d %10d\n", d->name,
 359                d->created, d->allocated, d->peak, d->current);
 360       i->size += d->allocated;
 361       i->count += d->created;
 362     }
 363   return 1;
 364 }
 365 #endif
 366
 367 /* Output per-alloc_pool memory usage statistics.  */
 368 void
 369 dump_alloc_pool_statistics (void)
 370 {
 371 #ifdef GATHER_STATISTICS
 372   struct output_info info;
 373
 374   if (!alloc_pool_hash)
 375     return;
 376
 377   fprintf (stderr, "\nAlloc-pool Kind        Pools  Allocated      Peak        Leak\n");
 378   fprintf (stderr, "-------------------------------------------------------------\n");
 379   info.count = 0;
 380   info.size = 0;
 381   htab_traverse (alloc_pool_hash, print_statistics, &info);
 382   fprintf (stderr, "-------------------------------------------------------------\n");
 383   fprintf (stderr, "%-20s %7d %10d\n",
 384            "Total", info.count, info.size);
 385   fprintf (stderr, "-------------------------------------------------------------\n");
 386 #endif
 387 }