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,
   3    2007, 2008, 2010  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          We do not care about alignment for floating-point types.  */
  46       char *align_p;
  47       HOST_WIDEST_INT align_i;
  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 /* Store information about each particular alloc_pool.  Note that this
  66    will underestimate the amount the amount of storage used by a small amount:
  67    1) The overhead in a pool is not accounted for.
  68    2) The unallocated elements in a block are not accounted for.  Note
  69    that this can at worst case be one element smaller that the block
  70    size for that pool.  */
  71 struct alloc_pool_descriptor
  72 {
  73   const char *name;
  74   /* Number of pools allocated.  */
  75   unsigned long created;
  76   /* Gross allocated storage.  */
  77   unsigned long allocated;
  78   /* Amount of currently active storage. */
  79   unsigned long current;
  80   /* Peak amount of storage used.  */
  81   unsigned long peak;
  82   /* Size of element in the pool.  */
  83   int elt_size;
  84 };
  85
  86 /* Hashtable mapping alloc_pool names to descriptors.  */
  87 static htab_t alloc_pool_hash;
  88
  89 /* Hashtable helpers.  */
  90 static hashval_t
  91 hash_descriptor (const void *p)
  92 {
  93   const struct alloc_pool_descriptor *const d =
  94     (const struct alloc_pool_descriptor * )p;
  95   return htab_hash_pointer (d->name);
  96 }
  97 static int
  98 eq_descriptor (const void *p1, const void *p2)
  99 {
 100   const struct alloc_pool_descriptor *const d =
 101     (const struct alloc_pool_descriptor *) p1;
 102   return d->name == p2;
 103 }
 104
 105 /* For given name, return descriptor, create new if needed.  */
 106 static struct alloc_pool_descriptor *
 107 alloc_pool_descriptor (const char *name)
 108 {
 109   struct alloc_pool_descriptor **slot;
 110
 111   if (!alloc_pool_hash)
 112     alloc_pool_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
 113
 114   slot = (struct alloc_pool_descriptor **)
 115     htab_find_slot_with_hash (alloc_pool_hash, name,
 116                               htab_hash_pointer (name),
 117                               INSERT);
 118   if (*slot)
 119     return *slot;
 120   *slot = XCNEW (struct alloc_pool_descriptor);
 121   (*slot)->name = name;
 122   return *slot;
 123 }
 124
 125 /* Create a pool of things of size SIZE, with NUM in each block we
 126    allocate.  */
 127
 128 alloc_pool
 129 create_alloc_pool (const char *name, size_t size, size_t num)
 130 {
 131   alloc_pool pool;
 132   size_t header_size;
 133
 134   gcc_checking_assert (name);
 135
 136   /* Make size large enough to store the list header.  */
 137   if (size < sizeof (alloc_pool_list))
 138     size = sizeof (alloc_pool_list);
 139
 140   /* Now align the size to a multiple of 4.  */
 141   size = align_eight (size);
 142
 143   if (ENABLE_CHECKING)
 144     {
 145       /* Add the aligned size of ID.  */
 146       size += offsetof (allocation_object, u.data);
 147     }
 148
 149   /* Um, we can't really allocate 0 elements per block.  */
 150   gcc_checking_assert (num);
 151
 152   /* Allocate memory for the pool structure.  */
 153   pool = XNEW (struct alloc_pool_def);
 154
 155   /* Now init the various pieces of our pool structure.  */
 156   pool->name = /*xstrdup (name)*/name;
 157   pool->elt_size = size;
 158   pool->elts_per_block = num;
 159
 160   if (GATHER_STATISTICS)
 161     {
 162       struct alloc_pool_descriptor *desc = alloc_pool_descriptor (name);
 163       desc->elt_size = size;
 164       desc->created++;
 165     }
 166
 167   /* List header size should be a multiple of 8.  */
 168   header_size = align_eight (sizeof (struct alloc_pool_list_def));
 169
 170   pool->block_size = (size * num) + header_size;
 171   pool->returned_free_list = NULL;
 172   pool->virgin_free_list = NULL;
 173   pool->virgin_elts_remaining = 0;
 174   pool->elts_allocated = 0;
 175   pool->elts_free = 0;
 176   pool->blocks_allocated = 0;
 177   pool->block_list = NULL;
 178
 179 #ifdef ENABLE_CHECKING
 180   /* Increase the last used ID and use it for this pool.
 181      ID == 0 is used for free elements of pool so skip it.  */
 182   last_id++;
 183   if (last_id == 0)
 184     last_id++;
 185
 186   pool->id = last_id;
 187 #endif
 188
 189   return (pool);
 190 }
 191
 192 /* Free all memory allocated for the given memory pool.  */
 193 void
 194 empty_alloc_pool (alloc_pool pool)
 195 {
 196   alloc_pool_list block, next_block;
 197
 198   gcc_checking_assert (pool);
 199
 200   /* Free each block allocated to the pool.  */
 201   for (block = pool->block_list; block != NULL; block = next_block)
 202     {
 203       next_block = block->next;
 204       free (block);
 205     }
 206
 207   if (GATHER_STATISTICS)
 208     {
 209       struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 210       desc->current -= (pool->elts_allocated - pool->elts_free) * pool->elt_size;
 211     }
 212
 213   pool->returned_free_list = NULL;
 214   pool->virgin_free_list = NULL;
 215   pool->virgin_elts_remaining = 0;
 216   pool->elts_allocated = 0;
 217   pool->elts_free = 0;
 218   pool->blocks_allocated = 0;
 219   pool->block_list = NULL;
 220 }
 221
 222 /* Free all memory allocated for the given memory pool and the pool itself.  */
 223 void
 224 free_alloc_pool (alloc_pool pool)
 225 {
 226   /* First empty the pool.  */
 227   empty_alloc_pool (pool);
 228 #ifdef ENABLE_CHECKING
 229   memset (pool, 0xaf, sizeof (*pool));
 230 #endif
 231   /* Lastly, free the pool.  */
 232   free (pool);
 233 }
 234
 235 /* Frees the alloc_pool, if it is empty and zero *POOL in this case.  */
 236 void
 237 free_alloc_pool_if_empty (alloc_pool *pool)
 238 {
 239   if ((*pool)->elts_free == (*pool)->elts_allocated)
 240     {
 241       free_alloc_pool (*pool);
 242       *pool = NULL;
 243     }
 244 }
 245
 246 /* Allocates one element from the pool specified.  */
 247 void *
 248 pool_alloc (alloc_pool pool)
 249 {
 250   alloc_pool_list header;
 251
 252   if (GATHER_STATISTICS)
 253     {
 254       struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 255
 256       desc->allocated += pool->elt_size;
 257       desc->current += pool->elt_size;
 258       if (desc->peak < desc->current)
 259         desc->peak = desc->current;
 260     }
 261
 262   gcc_checking_assert (pool);
 263
 264   /* If there are no more free elements, make some more!.  */
 265   if (!pool->returned_free_list)
 266     {
 267       char *block;
 268       if (!pool->virgin_elts_remaining)
 269         {
 270           alloc_pool_list block_header;
 271
 272           /* Make the block.  */
 273           block = XNEWVEC (char, pool->block_size);
 274           block_header = (alloc_pool_list) block;
 275           block += align_eight (sizeof (struct alloc_pool_list_def));
 276
 277           /* Throw it on the block list.  */
 278           block_header->next = pool->block_list;
 279           pool->block_list = block_header;
 280
 281           /* Make the block available for allocation.  */
 282           pool->virgin_free_list = block;
 283           pool->virgin_elts_remaining = pool->elts_per_block;
 284
 285           /* Also update the number of elements we have free/allocated, and
 286              increment the allocated block count.  */
 287           pool->elts_allocated += pool->elts_per_block;
 288           pool->elts_free += pool->elts_per_block;
 289           pool->blocks_allocated += 1;
 290         }
 291
 292
 293       /* We now know that we can take the first elt off the virgin list and
 294          put it on the returned list. */
 295       block = pool->virgin_free_list;
 296       header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
 297       header->next = NULL;
 298 #ifdef ENABLE_CHECKING
 299       /* Mark the element to be free.  */
 300       ((allocation_object *) block)->id = 0;
 301 #endif
 302       pool->returned_free_list = header;
 303       pool->virgin_free_list += pool->elt_size;
 304       pool->virgin_elts_remaining--;
 305
 306     }
 307
 308   /* Pull the first free element from the free list, and return it.  */
 309   header = pool->returned_free_list;
 310   pool->returned_free_list = header->next;
 311   pool->elts_free--;
 312
 313 #ifdef ENABLE_CHECKING
 314   /* Set the ID for element.  */
 315   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
 316 #endif
 317
 318   return ((void *) header);
 319 }
 320
 321 /* Puts PTR back on POOL's free list.  */
 322 void
 323 pool_free (alloc_pool pool, void *ptr)
 324 {
 325   alloc_pool_list header;
 326
 327 #ifdef ENABLE_CHECKING
 328   gcc_assert (ptr
 329               /* Check if we free more than we allocated, which is Bad (TM).  */
 330               && pool->elts_free < pool->elts_allocated
 331               /* Check whether the PTR was allocated from POOL.  */
 332               && pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id);
 333
 334   memset (ptr, 0xaf, pool->elt_size - offsetof (allocation_object, u.data));
 335
 336   /* Mark the element to be free.  */
 337   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
 338 #endif
 339
 340   header = (alloc_pool_list) ptr;
 341   header->next = pool->returned_free_list;
 342   pool->returned_free_list = header;
 343   pool->elts_free++;
 344
 345   if (GATHER_STATISTICS)
 346     {
 347       struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 348       desc->current -= pool->elt_size;
 349     }
 350 }
 351
 352 /* Output per-alloc_pool statistics.  */
 353
 354 /* Used to accumulate statistics about alloc_pool sizes.  */
 355 struct output_info
 356 {
 357   unsigned long total_created;
 358   unsigned long total_allocated;
 359 };
 360
 361 /* Called via htab_traverse.  Output alloc_pool descriptor pointed out by SLOT
 362    and update statistics.  */
 363 static int
 364 print_statistics (void **slot, void *b)
 365 {
 366   struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot;
 367   struct output_info *i = (struct output_info *) b;
 368
 369   if (d->allocated)
 370     {
 371       fprintf (stderr, "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n", d->name,
 372                d->elt_size, d->created, d->allocated, d->allocated / d->elt_size,
 373                d->peak, d->peak / d->elt_size,
 374                d->current, d->current / d->elt_size);
 375       i->total_allocated += d->allocated;
 376       i->total_created += d->created;
 377     }
 378   return 1;
 379 }
 380
 381 /* Output per-alloc_pool memory usage statistics.  */
 382 void
 383 dump_alloc_pool_statistics (void)
 384 {
 385   struct output_info info;
 386
 387   if (! GATHER_STATISTICS)
 388     return;
 389
 390   if (!alloc_pool_hash)
 391     return;
 392
 393   fprintf (stderr, "\nAlloc-pool Kind         Elt size  Pools  Allocated (elts)            Peak (elts)            Leak (elts)\n");
 394   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 395   info.total_created = 0;
 396   info.total_allocated = 0;
 397   htab_traverse (alloc_pool_hash, print_statistics, &info);
 398   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 399   fprintf (stderr, "%-22s           %7lu %10lu\n",
 400            "Total", info.total_created, info.total_allocated);
 401   fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
 402 }