1132718Skan/* Functions to support a pool of allocatable objects. 2169689Skan Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, 2006 3132718Skan Free Software Foundation, Inc. 4132718Skan Contributed by Daniel Berlin <dan@cgsoftware.com> 5132718Skan 6132718SkanThis file is part of GCC. 7132718Skan 8132718SkanGCC is free software; you can redistribute it and/or modify it under 9132718Skanthe terms of the GNU General Public License as published by the Free 10132718SkanSoftware Foundation; either version 2, or (at your option) any later 11132718Skanversion. 12132718Skan 13132718SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 14132718SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 15132718SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16132718Skanfor more details. 17132718Skan 18132718SkanYou should have received a copy of the GNU General Public License 19132718Skanalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 22132718Skan 23132718Skan#include "config.h" 24132718Skan#include "system.h" 25132718Skan#include "alloc-pool.h" 26132718Skan#include "hashtab.h" 27132718Skan 28132718Skan#define align_eight(x) (((x+7) >> 3) << 3) 29132718Skan 30132718Skan/* The internal allocation object. */ 31132718Skantypedef struct allocation_object_def 32132718Skan{ 33132718Skan#ifdef ENABLE_CHECKING 34132718Skan /* The ID of alloc pool which the object was allocated from. */ 35132718Skan ALLOC_POOL_ID_TYPE id; 36132718Skan#endif 37132718Skan 38132718Skan union 39132718Skan { 40132718Skan /* The data of the object. */ 41132718Skan char data[1]; 42132718Skan 43132718Skan /* Because we want any type of data to be well aligned after the ID, 44132718Skan the following elements are here. They are never accessed so 45132718Skan the allocated object may be even smaller than this structure. */ 46132718Skan char *align_p; 47132718Skan HOST_WIDEST_INT align_i; 48132718Skan long double align_ld; 49132718Skan } u; 50132718Skan} allocation_object; 51132718Skan 52132718Skan/* Convert a pointer to allocation_object from a pointer to user data. */ 53132718Skan#define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X) \ 54132718Skan ((allocation_object *) (((char *) (X)) \ 55132718Skan - offsetof (allocation_object, u.data))) 56132718Skan 57132718Skan/* Convert a pointer to user data from a pointer to allocation_object. */ 58132718Skan#define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X) \ 59132718Skan ((void *) (((allocation_object *) (X))->u.data)) 60132718Skan 61132718Skan#ifdef ENABLE_CHECKING 62132718Skan/* Last used ID. */ 63132718Skanstatic ALLOC_POOL_ID_TYPE last_id; 64132718Skan#endif 65132718Skan 66132718Skan#ifdef GATHER_STATISTICS 67132718Skan 68169689Skan/* Store information about each particular alloc_pool. */ 69132718Skanstruct alloc_pool_descriptor 70132718Skan{ 71132718Skan const char *name; 72132718Skan int allocated; 73132718Skan int created; 74132718Skan int peak; 75132718Skan int current; 76132718Skan}; 77132718Skan 78132718Skan/* Hashtable mapping alloc_pool names to descriptors. */ 79132718Skanstatic htab_t alloc_pool_hash; 80132718Skan 81132718Skan/* Hashtable helpers. */ 82132718Skanstatic hashval_t 83132718Skanhash_descriptor (const void *p) 84132718Skan{ 85132718Skan const struct alloc_pool_descriptor *d = p; 86132718Skan return htab_hash_pointer (d->name); 87132718Skan} 88132718Skanstatic int 89132718Skaneq_descriptor (const void *p1, const void *p2) 90132718Skan{ 91132718Skan const struct alloc_pool_descriptor *d = p1; 92132718Skan return d->name == p2; 93132718Skan} 94132718Skan 95132718Skan/* For given name, return descriptor, create new if needed. */ 96132718Skanstatic struct alloc_pool_descriptor * 97132718Skanalloc_pool_descriptor (const char *name) 98132718Skan{ 99132718Skan struct alloc_pool_descriptor **slot; 100132718Skan 101132718Skan if (!alloc_pool_hash) 102132718Skan alloc_pool_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL); 103132718Skan 104132718Skan slot = (struct alloc_pool_descriptor **) 105132718Skan htab_find_slot_with_hash (alloc_pool_hash, name, 106169689Skan htab_hash_pointer (name), 107132718Skan 1); 108132718Skan if (*slot) 109132718Skan return *slot; 110132718Skan *slot = xcalloc (sizeof (**slot), 1); 111132718Skan (*slot)->name = name; 112132718Skan return *slot; 113132718Skan} 114132718Skan#endif 115132718Skan 116132718Skan/* Create a pool of things of size SIZE, with NUM in each block we 117132718Skan allocate. */ 118132718Skan 119132718Skanalloc_pool 120132718Skancreate_alloc_pool (const char *name, size_t size, size_t num) 121132718Skan{ 122132718Skan alloc_pool pool; 123132718Skan size_t pool_size, header_size; 124132718Skan#ifdef GATHER_STATISTICS 125132718Skan struct alloc_pool_descriptor *desc; 126132718Skan#endif 127132718Skan 128169689Skan gcc_assert (name); 129132718Skan 130132718Skan /* Make size large enough to store the list header. */ 131132718Skan if (size < sizeof (alloc_pool_list)) 132132718Skan size = sizeof (alloc_pool_list); 133132718Skan 134132718Skan /* Now align the size to a multiple of 4. */ 135132718Skan size = align_eight (size); 136132718Skan 137132718Skan#ifdef ENABLE_CHECKING 138132718Skan /* Add the aligned size of ID. */ 139132718Skan size += offsetof (allocation_object, u.data); 140132718Skan#endif 141132718Skan 142132718Skan /* Um, we can't really allocate 0 elements per block. */ 143169689Skan gcc_assert (num); 144132718Skan 145132718Skan /* Find the size of the pool structure, and the name. */ 146132718Skan pool_size = sizeof (struct alloc_pool_def); 147132718Skan 148132718Skan /* and allocate that much memory. */ 149132718Skan pool = xmalloc (pool_size); 150132718Skan 151132718Skan /* Now init the various pieces of our pool structure. */ 152132718Skan pool->name = /*xstrdup (name)*/name; 153132718Skan#ifdef GATHER_STATISTICS 154132718Skan desc = alloc_pool_descriptor (name); 155132718Skan desc->created++; 156132718Skan#endif 157132718Skan pool->elt_size = size; 158132718Skan pool->elts_per_block = num; 159132718Skan 160132718Skan /* List header size should be a multiple of 8. */ 161132718Skan header_size = align_eight (sizeof (struct alloc_pool_list_def)); 162132718Skan 163132718Skan pool->block_size = (size * num) + header_size; 164132718Skan pool->free_list = NULL; 165132718Skan pool->elts_allocated = 0; 166132718Skan pool->elts_free = 0; 167132718Skan pool->blocks_allocated = 0; 168132718Skan pool->block_list = NULL; 169132718Skan 170132718Skan#ifdef ENABLE_CHECKING 171132718Skan /* Increase the last used ID and use it for this pool. 172132718Skan ID == 0 is used for free elements of pool so skip it. */ 173132718Skan last_id++; 174132718Skan if (last_id == 0) 175132718Skan last_id++; 176132718Skan 177132718Skan pool->id = last_id; 178132718Skan#endif 179132718Skan 180132718Skan return (pool); 181132718Skan} 182132718Skan 183132718Skan/* Free all memory allocated for the given memory pool. */ 184132718Skanvoid 185132718Skanfree_alloc_pool (alloc_pool pool) 186132718Skan{ 187132718Skan alloc_pool_list block, next_block; 188132718Skan#ifdef GATHER_STATISTICS 189132718Skan struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name); 190132718Skan#endif 191132718Skan 192169689Skan gcc_assert (pool); 193132718Skan 194132718Skan /* Free each block allocated to the pool. */ 195132718Skan for (block = pool->block_list; block != NULL; block = next_block) 196132718Skan { 197132718Skan next_block = block->next; 198132718Skan free (block); 199132718Skan#ifdef GATHER_STATISTICS 200132718Skan desc->current -= pool->block_size; 201132718Skan#endif 202132718Skan } 203132718Skan#ifdef ENABLE_CHECKING 204132718Skan memset (pool, 0xaf, sizeof (*pool)); 205132718Skan#endif 206169689Skan /* Lastly, free the pool. */ 207132718Skan free (pool); 208132718Skan} 209132718Skan 210169689Skan/* Frees the alloc_pool, if it is empty and zero *POOL in this case. */ 211169689Skanvoid 212169689Skanfree_alloc_pool_if_empty (alloc_pool *pool) 213169689Skan{ 214169689Skan if ((*pool)->elts_free == (*pool)->elts_allocated) 215169689Skan { 216169689Skan free_alloc_pool (*pool); 217169689Skan *pool = NULL; 218169689Skan } 219169689Skan} 220169689Skan 221132718Skan/* Allocates one element from the pool specified. */ 222132718Skanvoid * 223132718Skanpool_alloc (alloc_pool pool) 224132718Skan{ 225132718Skan alloc_pool_list header; 226132718Skan char *block; 227132718Skan#ifdef GATHER_STATISTICS 228132718Skan struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name); 229132718Skan 230132718Skan desc->allocated+=pool->elt_size; 231132718Skan#endif 232132718Skan 233169689Skan gcc_assert (pool); 234132718Skan 235132718Skan /* If there are no more free elements, make some more!. */ 236132718Skan if (!pool->free_list) 237132718Skan { 238132718Skan size_t i; 239132718Skan alloc_pool_list block_header; 240132718Skan 241132718Skan /* Make the block. */ 242169689Skan block = XNEWVEC (char, pool->block_size); 243132718Skan block_header = (alloc_pool_list) block; 244132718Skan block += align_eight (sizeof (struct alloc_pool_list_def)); 245132718Skan#ifdef GATHER_STATISTICS 246132718Skan desc->current += pool->block_size; 247132718Skan if (desc->peak < desc->current) 248132718Skan desc->peak = desc->current; 249132718Skan#endif 250132718Skan 251132718Skan /* Throw it on the block list. */ 252132718Skan block_header->next = pool->block_list; 253132718Skan pool->block_list = block_header; 254132718Skan 255132718Skan /* Now put the actual block pieces onto the free list. */ 256132718Skan for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size) 257132718Skan { 258132718Skan#ifdef ENABLE_CHECKING 259132718Skan /* Mark the element to be free. */ 260132718Skan ((allocation_object *) block)->id = 0; 261132718Skan#endif 262169689Skan header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block); 263169689Skan header->next = pool->free_list; 264169689Skan pool->free_list = header; 265132718Skan } 266132718Skan /* Also update the number of elements we have free/allocated, and 267169689Skan increment the allocated block count. */ 268132718Skan pool->elts_allocated += pool->elts_per_block; 269132718Skan pool->elts_free += pool->elts_per_block; 270132718Skan pool->blocks_allocated += 1; 271132718Skan } 272132718Skan 273132718Skan /* Pull the first free element from the free list, and return it. */ 274132718Skan header = pool->free_list; 275132718Skan pool->free_list = header->next; 276132718Skan pool->elts_free--; 277132718Skan 278132718Skan#ifdef ENABLE_CHECKING 279132718Skan /* Set the ID for element. */ 280132718Skan ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id; 281132718Skan#endif 282132718Skan 283132718Skan return ((void *) header); 284132718Skan} 285132718Skan 286132718Skan/* Puts PTR back on POOL's free list. */ 287132718Skanvoid 288132718Skanpool_free (alloc_pool pool, void *ptr) 289132718Skan{ 290132718Skan alloc_pool_list header; 291132718Skan 292169689Skan gcc_assert (ptr); 293169689Skan 294132718Skan#ifdef ENABLE_CHECKING 295132718Skan memset (ptr, 0xaf, pool->elt_size - offsetof (allocation_object, u.data)); 296132718Skan 297132718Skan /* Check whether the PTR was allocated from POOL. */ 298169689Skan gcc_assert (pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id); 299132718Skan 300132718Skan /* Mark the element to be free. */ 301132718Skan ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0; 302132718Skan#else 303132718Skan /* Check if we free more than we allocated, which is Bad (TM). */ 304169689Skan gcc_assert (pool->elts_free < pool->elts_allocated); 305132718Skan#endif 306132718Skan 307132718Skan header = (alloc_pool_list) ptr; 308132718Skan header->next = pool->free_list; 309132718Skan pool->free_list = header; 310132718Skan pool->elts_free++; 311132718Skan} 312132718Skan/* Output per-alloc_pool statistics. */ 313132718Skan#ifdef GATHER_STATISTICS 314132718Skan 315132718Skan/* Used to accumulate statistics about alloc_pool sizes. */ 316132718Skanstruct output_info 317132718Skan{ 318132718Skan int count; 319132718Skan int size; 320132718Skan}; 321132718Skan 322132718Skan/* Called via htab_traverse. Output alloc_pool descriptor pointed out by SLOT 323132718Skan and update statistics. */ 324132718Skanstatic int 325132718Skanprint_statistics (void **slot, void *b) 326132718Skan{ 327132718Skan struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot; 328132718Skan struct output_info *i = (struct output_info *) b; 329132718Skan 330132718Skan if (d->allocated) 331132718Skan { 332132718Skan fprintf (stderr, "%-21s %6d %10d %10d %10d\n", d->name, 333132718Skan d->created, d->allocated, d->peak, d->current); 334132718Skan i->size += d->allocated; 335132718Skan i->count += d->created; 336132718Skan } 337132718Skan return 1; 338132718Skan} 339132718Skan#endif 340132718Skan 341132718Skan/* Output per-alloc_pool memory usage statistics. */ 342169689Skanvoid 343169689Skandump_alloc_pool_statistics (void) 344132718Skan{ 345132718Skan#ifdef GATHER_STATISTICS 346132718Skan struct output_info info; 347132718Skan 348169689Skan if (!alloc_pool_hash) 349169689Skan return; 350169689Skan 351132718Skan fprintf (stderr, "\nAlloc-pool Kind Pools Allocated Peak Leak\n"); 352132718Skan fprintf (stderr, "-------------------------------------------------------------\n"); 353132718Skan info.count = 0; 354132718Skan info.size = 0; 355132718Skan htab_traverse (alloc_pool_hash, print_statistics, &info); 356132718Skan fprintf (stderr, "-------------------------------------------------------------\n"); 357132718Skan fprintf (stderr, "%-20s %7d %10d\n", 358132718Skan "Total", info.count, info.size); 359132718Skan fprintf (stderr, "-------------------------------------------------------------\n"); 360132718Skan#endif 361132718Skan} 362