|
0
|
1 /* Functions to support a pool of allocatable objects.
|
|
|
2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, 2006,
|
|
|
3 2007, 2008 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 3, 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 COPYING3. If not see
|
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
|
21
|
|
|
22 #include "config.h"
|
|
|
23 #include "system.h"
|
|
|
24 #include "alloc-pool.h"
|
|
|
25 #include "hashtab.h"
|
|
|
26
|
|
|
27 #define align_eight(x) (((x+7) >> 3) << 3)
|
|
|
28
|
|
|
29 /* The internal allocation object. */
|
|
|
30 typedef struct allocation_object_def
|
|
|
31 {
|
|
|
32 #ifdef ENABLE_CHECKING
|
|
|
33 /* The ID of alloc pool which the object was allocated from. */
|
|
|
34 ALLOC_POOL_ID_TYPE id;
|
|
|
35 #endif
|
|
|
36
|
|
|
37 union
|
|
|
38 {
|
|
|
39 /* The data of the object. */
|
|
|
40 char data[1];
|
|
|
41
|
|
|
42 /* Because we want any type of data to be well aligned after the ID,
|
|
|
43 the following elements are here. They are never accessed so
|
|
|
44 the allocated object may be even smaller than this structure. */
|
|
|
45 char *align_p;
|
|
|
46 HOST_WIDEST_INT align_i;
|
|
|
47 long double align_ld;
|
|
|
48 } u;
|
|
|
49 } allocation_object;
|
|
|
50
|
|
|
51 /* Convert a pointer to allocation_object from a pointer to user data. */
|
|
|
52 #define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X) \
|
|
|
53 ((allocation_object *) (((char *) (X)) \
|
|
|
54 - offsetof (allocation_object, u.data)))
|
|
|
55
|
|
|
56 /* Convert a pointer to user data from a pointer to allocation_object. */
|
|
|
57 #define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X) \
|
|
|
58 ((void *) (((allocation_object *) (X))->u.data))
|
|
|
59
|
|
|
60 #ifdef ENABLE_CHECKING
|
|
|
61 /* Last used ID. */
|
|
|
62 static ALLOC_POOL_ID_TYPE last_id;
|
|
|
63 #endif
|
|
|
64
|
|
|
65 #ifdef GATHER_STATISTICS
|
|
|
66
|
|
|
67 /* Store information about each particular alloc_pool. Note that this
|
|
|
68 will underestimate the amount the amount of storage used by a small amount:
|
|
|
69 1) The overhead in a pool is not accounted for.
|
|
|
70 2) The unallocated elements in a block are not accounted for. Note
|
|
|
71 that this can at worst case be one element smaller that the block
|
|
|
72 size for that pool. */
|
|
|
73 struct alloc_pool_descriptor
|
|
|
74 {
|
|
|
75 const char *name;
|
|
|
76 /* Number of pools allocated. */
|
|
|
77 unsigned long created;
|
|
|
78 /* Gross allocated storage. */
|
|
|
79 unsigned long allocated;
|
|
|
80 /* Amount of currently active storage. */
|
|
|
81 unsigned long current;
|
|
|
82 /* Peak amount of storage used. */
|
|
|
83 unsigned long peak;
|
|
|
84 /* Size of element in the pool. */
|
|
|
85 int elt_size;
|
|
|
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 *const d =
|
|
|
96 (const struct alloc_pool_descriptor * )p;
|
|
|
97 return htab_hash_pointer (d->name);
|
|
|
98 }
|
|
|
99 static int
|
|
|
100 eq_descriptor (const void *p1, const void *p2)
|
|
|
101 {
|
|
|
102 const struct alloc_pool_descriptor *const d =
|
|
|
103 (const struct alloc_pool_descriptor *) p1;
|
|
|
104 return d->name == p2;
|
|
|
105 }
|
|
|
106
|
|
|
107 /* For given name, return descriptor, create new if needed. */
|
|
|
108 static struct alloc_pool_descriptor *
|
|
|
109 alloc_pool_descriptor (const char *name)
|
|
|
110 {
|
|
|
111 struct alloc_pool_descriptor **slot;
|
|
|
112
|
|
|
113 if (!alloc_pool_hash)
|
|
|
114 alloc_pool_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
|
|
|
115
|
|
|
116 slot = (struct alloc_pool_descriptor **)
|
|
|
117 htab_find_slot_with_hash (alloc_pool_hash, name,
|
|
|
118 htab_hash_pointer (name),
|
|
|
119 1);
|
|
|
120 if (*slot)
|
|
|
121 return *slot;
|
|
|
122 *slot = XCNEW (struct alloc_pool_descriptor);
|
|
|
123 (*slot)->name = name;
|
|
|
124 return *slot;
|
|
|
125 }
|
|
|
126 #endif
|
|
|
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 #ifdef GATHER_STATISTICS
|
|
|
137 struct alloc_pool_descriptor *desc;
|
|
|
138 #endif
|
|
|
139
|
|
|
140 gcc_assert (name);
|
|
|
141
|
|
|
142 /* Make size large enough to store the list header. */
|
|
|
143 if (size < sizeof (alloc_pool_list))
|
|
|
144 size = sizeof (alloc_pool_list);
|
|
|
145
|
|
|
146 /* Now align the size to a multiple of 4. */
|
|
|
147 size = align_eight (size);
|
|
|
148
|
|
|
149 #ifdef ENABLE_CHECKING
|
|
|
150 /* Add the aligned size of ID. */
|
|
|
151 size += offsetof (allocation_object, u.data);
|
|
|
152 #endif
|
|
|
153
|
|
|
154 /* Um, we can't really allocate 0 elements per block. */
|
|
|
155 gcc_assert (num);
|
|
|
156
|
|
|
157 /* Allocate memory for the pool structure. */
|
|
|
158 pool = XNEW (struct alloc_pool_def);
|
|
|
159
|
|
|
160 /* Now init the various pieces of our pool structure. */
|
|
|
161 pool->name = /*xstrdup (name)*/name;
|
|
|
162 #ifdef GATHER_STATISTICS
|
|
|
163 desc = alloc_pool_descriptor (name);
|
|
|
164 desc->elt_size = size;
|
|
|
165 desc->created++;
|
|
|
166 #endif
|
|
|
167 pool->elt_size = size;
|
|
|
168 pool->elts_per_block = num;
|
|
|
169
|
|
|
170 /* List header size should be a multiple of 8. */
|
|
|
171 header_size = align_eight (sizeof (struct alloc_pool_list_def));
|
|
|
172
|
|
|
173 pool->block_size = (size * num) + header_size;
|
|
|
174 pool->returned_free_list = NULL;
|
|
|
175 pool->virgin_free_list = NULL;
|
|
|
176 pool->virgin_elts_remaining = 0;
|
|
|
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 empty_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 gcc_assert (pool);
|
|
|
205
|
|
|
206 /* Free each block allocated to the pool. */
|
|
|
207 for (block = pool->block_list; block != NULL; block = next_block)
|
|
|
208 {
|
|
|
209 next_block = block->next;
|
|
|
210 free (block);
|
|
|
211 }
|
|
|
212
|
|
|
213 #ifdef GATHER_STATISTICS
|
|
|
214 desc->current -= (pool->elts_allocated - pool->elts_free) * pool->elt_size;
|
|
|
215 #endif
|
|
|
216 pool->returned_free_list = NULL;
|
|
|
217 pool->virgin_free_list = NULL;
|
|
|
218 pool->virgin_elts_remaining = 0;
|
|
|
219 pool->elts_allocated = 0;
|
|
|
220 pool->elts_free = 0;
|
|
|
221 pool->blocks_allocated = 0;
|
|
|
222 pool->block_list = NULL;
|
|
|
223 }
|
|
|
224
|
|
|
225 /* Free all memory allocated for the given memory pool and the pool itself. */
|
|
|
226 void
|
|
|
227 free_alloc_pool (alloc_pool pool)
|
|
|
228 {
|
|
|
229 /* First empty the pool. */
|
|
|
230 empty_alloc_pool (pool);
|
|
|
231 #ifdef ENABLE_CHECKING
|
|
|
232 memset (pool, 0xaf, sizeof (*pool));
|
|
|
233 #endif
|
|
|
234 /* Lastly, free the pool. */
|
|
|
235 free (pool);
|
|
|
236 }
|
|
|
237
|
|
|
238 /* Frees the alloc_pool, if it is empty and zero *POOL in this case. */
|
|
|
239 void
|
|
|
240 free_alloc_pool_if_empty (alloc_pool *pool)
|
|
|
241 {
|
|
|
242 if ((*pool)->elts_free == (*pool)->elts_allocated)
|
|
|
243 {
|
|
|
244 free_alloc_pool (*pool);
|
|
|
245 *pool = NULL;
|
|
|
246 }
|
|
|
247 }
|
|
|
248
|
|
|
249 /* Allocates one element from the pool specified. */
|
|
|
250 void *
|
|
|
251 pool_alloc (alloc_pool pool)
|
|
|
252 {
|
|
|
253 alloc_pool_list header;
|
|
|
254 #ifdef GATHER_STATISTICS
|
|
|
255 struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
|
|
|
256
|
|
|
257 desc->allocated += pool->elt_size;
|
|
|
258 desc->current += pool->elt_size;
|
|
|
259 if (desc->peak < desc->current)
|
|
|
260 desc->peak = desc->current;
|
|
|
261 #endif
|
|
|
262
|
|
|
263 gcc_assert (pool);
|
|
|
264
|
|
|
265 /* If there are no more free elements, make some more!. */
|
|
|
266 if (!pool->returned_free_list)
|
|
|
267 {
|
|
|
268 char *block;
|
|
|
269 if (!pool->virgin_elts_remaining)
|
|
|
270 {
|
|
|
271 alloc_pool_list block_header;
|
|
|
272
|
|
|
273 /* Make the block. */
|
|
|
274 block = XNEWVEC (char, pool->block_size);
|
|
|
275 block_header = (alloc_pool_list) block;
|
|
|
276 block += align_eight (sizeof (struct alloc_pool_list_def));
|
|
|
277
|
|
|
278 /* Throw it on the block list. */
|
|
|
279 block_header->next = pool->block_list;
|
|
|
280 pool->block_list = block_header;
|
|
|
281
|
|
|
282 /* Make the block available for allocation. */
|
|
|
283 pool->virgin_free_list = block;
|
|
|
284 pool->virgin_elts_remaining = pool->elts_per_block;
|
|
|
285
|
|
|
286 /* Also update the number of elements we have free/allocated, and
|
|
|
287 increment the allocated block count. */
|
|
|
288 pool->elts_allocated += pool->elts_per_block;
|
|
|
289 pool->elts_free += pool->elts_per_block;
|
|
|
290 pool->blocks_allocated += 1;
|
|
|
291 }
|
|
|
292
|
|
|
293
|
|
|
294 /* We now know that we can take the first elt off the virgin list and
|
|
|
295 put it on the returned list. */
|
|
|
296 block = pool->virgin_free_list;
|
|
|
297 header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
|
|
|
298 header->next = NULL;
|
|
|
299 #ifdef ENABLE_CHECKING
|
|
|
300 /* Mark the element to be free. */
|
|
|
301 ((allocation_object *) block)->id = 0;
|
|
|
302 #endif
|
|
|
303 pool->returned_free_list = header;
|
|
|
304 pool->virgin_free_list += pool->elt_size;
|
|
|
305 pool->virgin_elts_remaining--;
|
|
|
306
|
|
|
307 }
|
|
|
308
|
|
|
309 /* Pull the first free element from the free list, and return it. */
|
|
|
310 header = pool->returned_free_list;
|
|
|
311 pool->returned_free_list = header->next;
|
|
|
312 pool->elts_free--;
|
|
|
313
|
|
|
314 #ifdef ENABLE_CHECKING
|
|
|
315 /* Set the ID for element. */
|
|
|
316 ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
|
|
|
317 #endif
|
|
|
318
|
|
|
319 return ((void *) header);
|
|
|
320 }
|
|
|
321
|
|
|
322 /* Puts PTR back on POOL's free list. */
|
|
|
323 void
|
|
|
324 pool_free (alloc_pool pool, void *ptr)
|
|
|
325 {
|
|
|
326 alloc_pool_list header;
|
|
|
327 #ifdef GATHER_STATISTICS
|
|
|
328 struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
|
|
|
329 #endif
|
|
|
330
|
|
|
331 gcc_assert (ptr);
|
|
|
332
|
|
|
333 #ifdef ENABLE_CHECKING
|
|
|
334 /* Check whether the PTR was allocated from POOL. */
|
|
|
335 gcc_assert (pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id);
|
|
|
336
|
|
|
337 memset (ptr, 0xaf, pool->elt_size - offsetof (allocation_object, u.data));
|
|
|
338
|
|
|
339 /* Mark the element to be free. */
|
|
|
340 ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
|
|
|
341 #else
|
|
|
342 /* Check if we free more than we allocated, which is Bad (TM). */
|
|
|
343 gcc_assert (pool->elts_free < pool->elts_allocated);
|
|
|
344 #endif
|
|
|
345
|
|
|
346 header = (alloc_pool_list) ptr;
|
|
|
347 header->next = pool->returned_free_list;
|
|
|
348 pool->returned_free_list = header;
|
|
|
349 pool->elts_free++;
|
|
|
350
|
|
|
351 #ifdef GATHER_STATISTICS
|
|
|
352 desc->current -= pool->elt_size;
|
|
|
353 #endif
|
|
|
354
|
|
|
355 }
|
|
|
356 /* Output per-alloc_pool statistics. */
|
|
|
357 #ifdef GATHER_STATISTICS
|
|
|
358
|
|
|
359 /* Used to accumulate statistics about alloc_pool sizes. */
|
|
|
360 struct output_info
|
|
|
361 {
|
|
|
362 unsigned long total_created;
|
|
|
363 unsigned long total_allocated;
|
|
|
364 };
|
|
|
365
|
|
|
366 /* Called via htab_traverse. Output alloc_pool descriptor pointed out by SLOT
|
|
|
367 and update statistics. */
|
|
|
368 static int
|
|
|
369 print_statistics (void **slot, void *b)
|
|
|
370 {
|
|
|
371 struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot;
|
|
|
372 struct output_info *i = (struct output_info *) b;
|
|
|
373
|
|
|
374 if (d->allocated)
|
|
|
375 {
|
|
|
376 fprintf (stderr, "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n", d->name,
|
|
|
377 d->elt_size, d->created, d->allocated, d->allocated / d->elt_size,
|
|
|
378 d->peak, d->peak / d->elt_size,
|
|
|
379 d->current, d->current / d->elt_size);
|
|
|
380 i->total_allocated += d->allocated;
|
|
|
381 i->total_created += d->created;
|
|
|
382 }
|
|
|
383 return 1;
|
|
|
384 }
|
|
|
385 #endif
|
|
|
386
|
|
|
387 /* Output per-alloc_pool memory usage statistics. */
|
|
|
388 void
|
|
|
389 dump_alloc_pool_statistics (void)
|
|
|
390 {
|
|
|
391 #ifdef GATHER_STATISTICS
|
|
|
392 struct output_info info;
|
|
|
393
|
|
|
394 if (!alloc_pool_hash)
|
|
|
395 return;
|
|
|
396
|
|
|
397 fprintf (stderr, "\nAlloc-pool Kind Elt size Pools Allocated (elts) Peak (elts) Leak (elts)\n");
|
|
|
398 fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
|
|
|
399 info.total_created = 0;
|
|
|
400 info.total_allocated = 0;
|
|
|
401 htab_traverse (alloc_pool_hash, print_statistics, &info);
|
|
|
402 fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
|
|
|
403 fprintf (stderr, "%-22s %7lu %10lu\n",
|
|
|
404 "Total", info.total_created, info.total_allocated);
|
|
|
405 fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
|
|
|
406 #endif
|
|
|
407 }
|
