]>
Commit | Line | Data |
---|---|---|
263e39ce | 1 | /* Functions to support a pool of allocatable objects. |
3aea1f79 | 2 | Copyright (C) 1987-2014 Free Software Foundation, Inc. |
263e39ce | 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 | |
8c4c00c1 | 9 | Software Foundation; either version 3, or (at your option) any later |
263e39ce | 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 | |
8c4c00c1 | 18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
263e39ce | 20 | |
263e39ce | 21 | #include "config.h" |
22 | #include "system.h" | |
23 | #include "alloc-pool.h" | |
c580da87 | 24 | #include "hash-table.h" |
263e39ce | 25 | |
263e39ce | 26 | #define align_eight(x) (((x+7) >> 3) << 3) |
27 | ||
a5f52a45 | 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 | |
3089b75c | 43 | the allocated object may be even smaller than this structure. |
44 | We do not care about alignment for floating-point types. */ | |
a5f52a45 | 45 | char *align_p; |
a5f52a45 | 46 | HOST_WIDEST_INT align_i; |
a5f52a45 | 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 | ||
3573ec04 | 59 | #ifdef ENABLE_CHECKING |
a5f52a45 | 60 | /* Last used ID. */ |
61 | static ALLOC_POOL_ID_TYPE last_id; | |
3573ec04 | 62 | #endif |
a5f52a45 | 63 | |
918c094d | 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. */ | |
7fec61de | 70 | struct alloc_pool_descriptor |
71 | { | |
72 | const char *name; | |
918c094d | 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; | |
7fec61de | 83 | }; |
84 | ||
d9dd21a8 | 85 | /* Hashtable helpers. */ |
c580da87 | 86 | struct alloc_pool_hasher : typed_noop_remove <alloc_pool_descriptor> |
87 | { | |
88 | typedef alloc_pool_descriptor value_type; | |
89 | typedef char compare_type; | |
90 | static inline hashval_t hash (const alloc_pool_descriptor *); | |
91 | static inline bool equal (const value_type *, const compare_type *); | |
92 | }; | |
93 | ||
c580da87 | 94 | inline hashval_t |
95 | alloc_pool_hasher::hash (const value_type *d) | |
7fec61de | 96 | { |
7fec61de | 97 | return htab_hash_pointer (d->name); |
98 | } | |
c580da87 | 99 | |
100 | inline bool | |
101 | alloc_pool_hasher::equal (const value_type *d, | |
102 | const compare_type *p2) | |
7fec61de | 103 | { |
7fec61de | 104 | return d->name == p2; |
105 | } | |
106 | ||
d9dd21a8 | 107 | /* Hashtable mapping alloc_pool names to descriptors. */ |
108 | static hash_table <alloc_pool_hasher> alloc_pool_hash; | |
109 | ||
7fec61de | 110 | /* For given name, return descriptor, create new if needed. */ |
111 | static struct alloc_pool_descriptor * | |
c580da87 | 112 | allocate_pool_descriptor (const char *name) |
7fec61de | 113 | { |
114 | struct alloc_pool_descriptor **slot; | |
115 | ||
c580da87 | 116 | if (!alloc_pool_hash.is_created ()) |
117 | alloc_pool_hash.create (10); | |
7fec61de | 118 | |
c580da87 | 119 | slot = alloc_pool_hash.find_slot_with_hash (name, |
120 | htab_hash_pointer (name), INSERT); | |
7fec61de | 121 | if (*slot) |
122 | return *slot; | |
b8ede6a9 | 123 | *slot = XCNEW (struct alloc_pool_descriptor); |
7fec61de | 124 | (*slot)->name = name; |
125 | return *slot; | |
126 | } | |
7fec61de | 127 | |
263e39ce | 128 | /* Create a pool of things of size SIZE, with NUM in each block we |
129 | allocate. */ | |
130 | ||
131 | alloc_pool | |
aecda0d6 | 132 | create_alloc_pool (const char *name, size_t size, size_t num) |
263e39ce | 133 | { |
134 | alloc_pool pool; | |
c768b48b | 135 | size_t header_size; |
263e39ce | 136 | |
0ea2d350 | 137 | gcc_checking_assert (name); |
263e39ce | 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. */ | |
992f5b1b | 144 | size = align_eight (size); |
263e39ce | 145 | |
bdc1331d | 146 | #ifdef ENABLE_CHECKING |
147 | /* Add the aligned size of ID. */ | |
148 | size += offsetof (allocation_object, u.data); | |
149 | #endif | |
a5f52a45 | 150 | |
263e39ce | 151 | /* Um, we can't really allocate 0 elements per block. */ |
0ea2d350 | 152 | gcc_checking_assert (num); |
263e39ce | 153 | |
c768b48b | 154 | /* Allocate memory for the pool structure. */ |
155 | pool = XNEW (struct alloc_pool_def); | |
263e39ce | 156 | |
157 | /* Now init the various pieces of our pool structure. */ | |
7fec61de | 158 | pool->name = /*xstrdup (name)*/name; |
263e39ce | 159 | pool->elt_size = size; |
160 | pool->elts_per_block = num; | |
161 | ||
ecd52ea9 | 162 | if (GATHER_STATISTICS) |
163 | { | |
c580da87 | 164 | struct alloc_pool_descriptor *desc = allocate_pool_descriptor (name); |
ecd52ea9 | 165 | desc->elt_size = size; |
166 | desc->created++; | |
167 | } | |
168 | ||
8b332087 | 169 | /* List header size should be a multiple of 8. */ |
263e39ce | 170 | header_size = align_eight (sizeof (struct alloc_pool_list_def)); |
171 | ||
172 | pool->block_size = (size * num) + header_size; | |
3072d30e | 173 | pool->returned_free_list = NULL; |
174 | pool->virgin_free_list = NULL; | |
175 | pool->virgin_elts_remaining = 0; | |
263e39ce | 176 | pool->elts_allocated = 0; |
177 | pool->elts_free = 0; | |
178 | pool->blocks_allocated = 0; | |
179 | pool->block_list = NULL; | |
180 | ||
a5f52a45 | 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 | ||
263e39ce | 191 | return (pool); |
192 | } | |
193 | ||
194 | /* Free all memory allocated for the given memory pool. */ | |
195 | void | |
48694fc0 | 196 | empty_alloc_pool (alloc_pool pool) |
263e39ce | 197 | { |
198 | alloc_pool_list block, next_block; | |
199 | ||
0ea2d350 | 200 | gcc_checking_assert (pool); |
263e39ce | 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 | } | |
48694fc0 | 208 | |
ecd52ea9 | 209 | if (GATHER_STATISTICS) |
210 | { | |
c580da87 | 211 | struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name); |
ecd52ea9 | 212 | desc->current -= (pool->elts_allocated - pool->elts_free) * pool->elt_size; |
213 | } | |
214 | ||
48694fc0 | 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); | |
992f5b1b | 230 | #ifdef ENABLE_CHECKING |
231 | memset (pool, 0xaf, sizeof (*pool)); | |
232 | #endif | |
7fec61de | 233 | /* Lastly, free the pool. */ |
263e39ce | 234 | free (pool); |
235 | } | |
236 | ||
0a06d4f0 | 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 | ||
263e39ce | 248 | /* Allocates one element from the pool specified. */ |
249 | void * | |
aecda0d6 | 250 | pool_alloc (alloc_pool pool) |
263e39ce | 251 | { |
252 | alloc_pool_list header; | |
4d039f23 | 253 | #ifdef ENABLE_VALGRIND_CHECKING |
254 | int size; | |
255 | #endif | |
7fec61de | 256 | |
ecd52ea9 | 257 | if (GATHER_STATISTICS) |
258 | { | |
c580da87 | 259 | struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name); |
ecd52ea9 | 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 | } | |
263e39ce | 266 | |
0ea2d350 | 267 | gcc_checking_assert (pool); |
4d039f23 | 268 | #ifdef ENABLE_VALGRIND_CHECKING |
269 | size = pool->elt_size - offsetof (allocation_object, u.data); | |
270 | #endif | |
263e39ce | 271 | |
272 | /* If there are no more free elements, make some more!. */ | |
3072d30e | 273 | if (!pool->returned_free_list) |
263e39ce | 274 | { |
3072d30e | 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)); | |
48e1416a | 284 | |
3072d30e | 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 | ||
48e1416a | 300 | |
3072d30e | 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; | |
a5f52a45 | 306 | #ifdef ENABLE_CHECKING |
3072d30e | 307 | /* Mark the element to be free. */ |
308 | ((allocation_object *) block)->id = 0; | |
a5f52a45 | 309 | #endif |
d01dddf9 | 310 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size)); |
3072d30e | 311 | pool->returned_free_list = header; |
312 | pool->virgin_free_list += pool->elt_size; | |
313 | pool->virgin_elts_remaining--; | |
314 | ||
263e39ce | 315 | } |
316 | ||
317 | /* Pull the first free element from the free list, and return it. */ | |
3072d30e | 318 | header = pool->returned_free_list; |
9af5ce0c | 319 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof (*header))); |
3072d30e | 320 | pool->returned_free_list = header->next; |
263e39ce | 321 | pool->elts_free--; |
a5f52a45 | 322 | |
323 | #ifdef ENABLE_CHECKING | |
324 | /* Set the ID for element. */ | |
325 | ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id; | |
326 | #endif | |
d01dddf9 | 327 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size)); |
a5f52a45 | 328 | |
263e39ce | 329 | return ((void *) header); |
330 | } | |
331 | ||
332 | /* Puts PTR back on POOL's free list. */ | |
333 | void | |
aecda0d6 | 334 | pool_free (alloc_pool pool, void *ptr) |
263e39ce | 335 | { |
336 | alloc_pool_list header; | |
d01dddf9 | 337 | #if defined(ENABLE_VALGRIND_CHECKING) || defined(ENABLE_CHECKING) |
338 | int size; | |
339 | size = pool->elt_size - offsetof (allocation_object, u.data); | |
340 | #endif | |
263e39ce | 341 | |
64db345d | 342 | #ifdef ENABLE_CHECKING |
0ea2d350 | 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); | |
a5f52a45 | 348 | |
d01dddf9 | 349 | memset (ptr, 0xaf, size); |
3471582e | 350 | |
a5f52a45 | 351 | /* Mark the element to be free. */ |
352 | ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0; | |
a5f52a45 | 353 | #endif |
354 | ||
263e39ce | 355 | header = (alloc_pool_list) ptr; |
3072d30e | 356 | header->next = pool->returned_free_list; |
357 | pool->returned_free_list = header; | |
d01dddf9 | 358 | VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (ptr, size)); |
263e39ce | 359 | pool->elts_free++; |
918c094d | 360 | |
ecd52ea9 | 361 | if (GATHER_STATISTICS) |
362 | { | |
c580da87 | 363 | struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name); |
ecd52ea9 | 364 | desc->current -= pool->elt_size; |
365 | } | |
263e39ce | 366 | } |
ecd52ea9 | 367 | |
7fec61de | 368 | /* Output per-alloc_pool statistics. */ |
7fec61de | 369 | |
370 | /* Used to accumulate statistics about alloc_pool sizes. */ | |
371 | struct output_info | |
372 | { | |
918c094d | 373 | unsigned long total_created; |
374 | unsigned long total_allocated; | |
7fec61de | 375 | }; |
376 | ||
c580da87 | 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) | |
7fec61de | 382 | { |
c580da87 | 383 | struct alloc_pool_descriptor *d = *slot; |
7fec61de | 384 | |
385 | if (d->allocated) | |
386 | { | |
c580da87 | 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, | |
918c094d | 391 | d->current, d->current / d->elt_size); |
392 | i->total_allocated += d->allocated; | |
393 | i->total_created += d->created; | |
7fec61de | 394 | } |
395 | return 1; | |
396 | } | |
7fec61de | 397 | |
398 | /* Output per-alloc_pool memory usage statistics. */ | |
2e2fd8fe | 399 | void |
400 | dump_alloc_pool_statistics (void) | |
7fec61de | 401 | { |
7fec61de | 402 | struct output_info info; |
403 | ||
ecd52ea9 | 404 | if (! GATHER_STATISTICS) |
405 | return; | |
406 | ||
c580da87 | 407 | if (!alloc_pool_hash.is_created ()) |
1bb42c87 | 408 | return; |
409 | ||
918c094d | 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; | |
c580da87 | 414 | alloc_pool_hash.traverse <struct output_info *, |
415 | print_alloc_pool_statistics> (&info); | |
918c094d | 416 | fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n"); |
417 | fprintf (stderr, "%-22s %7lu %10lu\n", | |
418 | "Total", info.total_created, info.total_allocated); | |
419 | fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n"); | |
7fec61de | 420 | } |