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