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