gcc/alloc-pool.c

   1 /* Functions to support a pool of allocatable objects.
   2    Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004
   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 2, 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 COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "alloc-pool.h"
  26 #include "hashtab.h"
  27
  28 /* Redefine abort to report an internal error w/o coredump, and
  29    reporting the location of the error in the source file.  This logic
  30    is duplicated in rtl.h and tree.h because every file that needs the
  31    special abort includes one or both.  toplev.h gets too few files,
  32    system.h gets too many.  */
  33
  34 extern void fancy_abort (const char *, int, const char *)
  35     ATTRIBUTE_NORETURN;
  36 #define abort() fancy_abort (__FILE__, __LINE__, __FUNCTION__)
  37
  38 #define align_eight(x) (((x+7) >> 3) << 3)
  39
  40 /* The internal allocation object.  */
  41 typedef struct allocation_object_def
  42 {
  43 #ifdef ENABLE_CHECKING
  44   /* The ID of alloc pool which the object was allocated from.  */
  45   ALLOC_POOL_ID_TYPE id;
  46 #endif
  47
  48   union
  49     {
  50       /* The data of the object.  */
  51       char data[1];
  52
  53       /* Because we want any type of data to be well aligned after the ID,
  54          the following elements are here.  They are never accessed so
  55          the allocated object may be even smaller than this structure.  */
  56       char *align_p;
  57       HOST_WIDEST_INT align_i;
  58       long double align_ld;
  59     } u;
  60 } allocation_object;
  61
  62 /* Convert a pointer to allocation_object from a pointer to user data.  */
  63 #define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X)                          \
  64    ((allocation_object *) (((char *) (X))                               \
  65                            - offsetof (allocation_object, u.data)))
  66
  67 /* Convert a pointer to user data from a pointer to allocation_object.  */
  68 #define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X)                          \
  69    ((void *) (((allocation_object *) (X))->u.data))
  70
  71 #ifdef ENABLE_CHECKING
  72 /* Last used ID.  */
  73 static ALLOC_POOL_ID_TYPE last_id;
  74 #endif
  75
  76 #ifdef GATHER_STATISTICS
  77
  78 /* Store information about each particular alloc_pool.  */
  79 struct alloc_pool_descriptor
  80 {
  81   const char *name;
  82   int allocated;
  83   int created;
  84   int peak;
  85   int current;
  86 };
  87
  88 /* Hashtable mapping alloc_pool names to descriptors.  */
  89 static htab_t alloc_pool_hash;
  90
  91 /* Hashtable helpers.  */
  92 static hashval_t
  93 hash_descriptor (const void *p)
  94 {
  95   const struct alloc_pool_descriptor *d = p;
  96   return htab_hash_pointer (d->name);
  97 }
  98 static int
  99 eq_descriptor (const void *p1, const void *p2)
 100 {
 101   const struct alloc_pool_descriptor *d = 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                               1);
 118   if (*slot)
 119     return *slot;
 120   *slot = xcalloc (sizeof (**slot), 1);
 121   (*slot)->name = name;
 122   return *slot;
 123 }
 124 #endif
 125
 126 /* Create a pool of things of size SIZE, with NUM in each block we
 127    allocate.  */
 128
 129 alloc_pool
 130 create_alloc_pool (const char *name, size_t size, size_t num)
 131 {
 132   alloc_pool pool;
 133   size_t pool_size, header_size;
 134 #ifdef GATHER_STATISTICS
 135   struct alloc_pool_descriptor *desc;
 136 #endif
 137
 138   if (!name)
 139     abort ();
 140
 141   /* Make size large enough to store the list header.  */
 142   if (size < sizeof (alloc_pool_list))
 143     size = sizeof (alloc_pool_list);
 144
 145   /* Now align the size to a multiple of 4.  */
 146   size = align_eight (size);
 147
 148 #ifdef ENABLE_CHECKING
 149   /* Add the aligned size of ID.  */
 150   size += offsetof (allocation_object, u.data);
 151 #endif
 152
 153   /* Um, we can't really allocate 0 elements per block.  */
 154   if (num == 0)
 155     abort ();
 156
 157   /* Find the size of the pool structure, and the name.  */
 158   pool_size = sizeof (struct alloc_pool_def);
 159
 160   /* and allocate that much memory.  */
 161   pool = xmalloc (pool_size);
 162
 163   /* Now init the various pieces of our pool structure.  */
 164   pool->name = /*xstrdup (name)*/name;
 165 #ifdef GATHER_STATISTICS
 166   desc = alloc_pool_descriptor (name);
 167   desc->created++;
 168 #endif
 169   pool->elt_size = size;
 170   pool->elts_per_block = num;
 171
 172   /* List header size should be a multiple of 8.  */
 173   header_size = align_eight (sizeof (struct alloc_pool_list_def));
 174
 175   pool->block_size = (size * num) + header_size;
 176   pool->free_list = NULL;
 177   pool->elts_allocated = 0;
 178   pool->elts_free = 0;
 179   pool->blocks_allocated = 0;
 180   pool->block_list = NULL;
 181
 182 #ifdef ENABLE_CHECKING
 183   /* Increase the last used ID and use it for this pool.
 184      ID == 0 is used for free elements of pool so skip it.  */
 185   last_id++;
 186   if (last_id == 0)
 187     last_id++;
 188
 189   pool->id = last_id;
 190 #endif
 191
 192   return (pool);
 193 }
 194
 195 /* Free all memory allocated for the given memory pool.  */
 196 void
 197 free_alloc_pool (alloc_pool pool)
 198 {
 199   alloc_pool_list block, next_block;
 200 #ifdef GATHER_STATISTICS
 201   struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 202 #endif
 203
 204 #ifdef ENABLE_CHECKING
 205   if (!pool)
 206     abort ();
 207 #endif
 208
 209   /* Free each block allocated to the pool.  */
 210   for (block = pool->block_list; block != NULL; block = next_block)
 211     {
 212       next_block = block->next;
 213       free (block);
 214 #ifdef GATHER_STATISTICS
 215       desc->current -= pool->block_size;
 216 #endif
 217     }
 218 #ifdef ENABLE_CHECKING
 219   memset (pool, 0xaf, sizeof (*pool));
 220 #endif
 221   /* Lastly, free the pool.  */
 222   free (pool);
 223 }
 224
 225 /* Allocates one element from the pool specified.  */
 226 void *
 227 pool_alloc (alloc_pool pool)
 228 {
 229   alloc_pool_list header;
 230   char *block;
 231 #ifdef GATHER_STATISTICS
 232   struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
 233
 234   desc->allocated+=pool->elt_size;
 235 #endif
 236
 237 #ifdef ENABLE_CHECKING
 238   if (!pool)
 239     abort ();
 240 #endif
 241
 242   /* If there are no more free elements, make some more!.  */
 243   if (!pool->free_list)
 244     {
 245       size_t i;
 246       alloc_pool_list block_header;
 247
 248       /* Make the block.  */
 249       block = xmalloc (pool->block_size);
 250       block_header = (alloc_pool_list) block;
 251       block += align_eight (sizeof (struct alloc_pool_list_def));
 252 #ifdef GATHER_STATISTICS
 253       desc->current += pool->block_size;
 254       if (desc->peak < desc->current)
 255         desc->peak = desc->current;
 256 #endif
 257
 258       /* Throw it on the block list.  */
 259       block_header->next = pool->block_list;
 260       pool->block_list = block_header;
 261
 262       /* Now put the actual block pieces onto the free list.  */
 263       for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
 264       {
 265 #ifdef ENABLE_CHECKING
 266         /* Mark the element to be free.  */
 267         ((allocation_object *) block)->id = 0;
 268 #endif
 269         header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
 270         header->next = pool->free_list;
 271         pool->free_list = header;
 272       }
 273       /* Also update the number of elements we have free/allocated, and
 274          increment the allocated block count.  */
 275       pool->elts_allocated += pool->elts_per_block;
 276       pool->elts_free += pool->elts_per_block;
 277       pool->blocks_allocated += 1;
 278     }
 279
 280   /* Pull the first free element from the free list, and return it.  */
 281   header = pool->free_list;
 282   pool->free_list = header->next;
 283   pool->elts_free--;
 284
 285 #ifdef ENABLE_CHECKING
 286   /* Set the ID for element.  */
 287   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
 288 #endif
 289
 290   return ((void *) header);
 291 }
 292
 293 /* Puts PTR back on POOL's free list.  */
 294 void
 295 pool_free (alloc_pool pool, void *ptr)
 296 {
 297   alloc_pool_list header;
 298
 299 #ifdef ENABLE_CHECKING
 300   if (!ptr)
 301     abort ();
 302
 303   memset (ptr, 0xaf, pool->elt_size - offsetof (allocation_object, u.data));
 304
 305   /* Check whether the PTR was allocated from POOL.  */
 306   if (pool->id != ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id)
 307     abort ();
 308
 309   /* Mark the element to be free.  */
 310   ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
 311 #else
 312   /* Check if we free more than we allocated, which is Bad (TM).  */
 313   if (pool->elts_free + 1 > pool->elts_allocated)
 314     abort ();
 315 #endif
 316
 317   header = (alloc_pool_list) ptr;
 318   header->next = pool->free_list;
 319   pool->free_list = header;
 320   pool->elts_free++;
 321 }
 322 /* Output per-alloc_pool statistics.  */
 323 #ifdef GATHER_STATISTICS
 324
 325 /* Used to accumulate statistics about alloc_pool sizes.  */
 326 struct output_info
 327 {
 328   int count;
 329   int size;
 330 };
 331
 332 /* Called via htab_traverse.  Output alloc_pool descriptor pointed out by SLOT
 333    and update statistics.  */
 334 static int
 335 print_statistics (void **slot, void *b)
 336 {
 337   struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot;
 338   struct output_info *i = (struct output_info *) b;
 339
 340   if (d->allocated)
 341     {
 342       fprintf (stderr, "%-21s %6d %10d %10d %10d\n", d->name,
 343                d->created, d->allocated, d->peak, d->current);
 344       i->size += d->allocated;
 345       i->count += d->created;
 346     }
 347   return 1;
 348 }
 349 #endif
 350
 351 /* Output per-alloc_pool memory usage statistics.  */
 352 void dump_alloc_pool_statistics (void)
 353 {
 354 #ifdef GATHER_STATISTICS
 355   struct output_info info;
 356
 357   fprintf (stderr, "\nAlloc-pool Kind        Pools  Allocated      Peak        Leak\n");
 358   fprintf (stderr, "-------------------------------------------------------------\n");
 359   info.count = 0;
 360   info.size = 0;
 361   htab_traverse (alloc_pool_hash, print_statistics, &info);
 362   fprintf (stderr, "-------------------------------------------------------------\n");
 363   fprintf (stderr, "%-20s %7d %10d\n",
 364            "Total", info.count, info.size);
 365   fprintf (stderr, "-------------------------------------------------------------\n");
 366 #endif
 367 }