Branch data Line data Source code
1 : : /* Functions to support a pool of allocatable objects
2 : : Copyright (C) 1997-2025 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
8 : : it under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful,
13 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : GNU General Public License 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 : : #ifndef ALLOC_POOL_H
21 : : #define ALLOC_POOL_H
22 : :
23 : : #include "memory-block.h"
24 : : #include "options.h" // for flag_checking
25 : :
26 : : extern void dump_alloc_pool_statistics (void);
27 : :
28 : : /* Flag indicates whether memory statistics are gathered any longer. */
29 : : extern bool after_memory_report;
30 : :
31 : : typedef unsigned long ALLOC_POOL_ID_TYPE;
32 : :
33 : : /* Last used ID. */
34 : : extern ALLOC_POOL_ID_TYPE last_id;
35 : :
36 : : /* Pool allocator memory usage. */
37 : : class pool_usage: public mem_usage
38 : : {
39 : : public:
40 : : /* Default contructor. */
41 : : pool_usage (): m_element_size (0), m_pool_name ("") {}
42 : : /* Constructor. */
43 : : pool_usage (size_t allocated, size_t times, size_t peak,
44 : : size_t instances, size_t element_size,
45 : : const char *pool_name)
46 : : : mem_usage (allocated, times, peak, instances),
47 : : m_element_size (element_size),
48 : : m_pool_name (pool_name) {}
49 : :
50 : : /* Sum the usage with SECOND usage. */
51 : : pool_usage
52 : : operator+ (const pool_usage &second)
53 : : {
54 : : return pool_usage (m_allocated + second.m_allocated,
55 : : m_times + second.m_times,
56 : : m_peak + second.m_peak,
57 : : m_instances + second.m_instances,
58 : : m_element_size, m_pool_name);
59 : : }
60 : :
61 : : /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
62 : : inline void
63 : : dump (mem_location *loc, const mem_usage &total) const
64 : : {
65 : : char *location_string = loc->to_string ();
66 : :
67 : : fprintf (stderr, "%-32s%-48s " PRsa(5) PRsa(9) ":%5.1f%%"
68 : : PRsa(9) PRsa(9) ":%5.1f%%%12" PRIu64 "\n",
69 : : m_pool_name, location_string,
70 : : SIZE_AMOUNT (m_instances),
71 : : SIZE_AMOUNT (m_allocated),
72 : : get_percent (m_allocated, total.m_allocated),
73 : : SIZE_AMOUNT (m_peak),
74 : : SIZE_AMOUNT (m_times),
75 : : get_percent (m_times, total.m_times),
76 : : (uint64_t)m_element_size);
77 : :
78 : : free (location_string);
79 : : }
80 : :
81 : : /* Dump header with NAME. */
82 : : static inline void
83 : : dump_header (const char *name)
84 : : {
85 : : fprintf (stderr, "%-32s%-48s %6s%11s%16s%17s%12s\n", "Pool name", name,
86 : : "Pools", "Leak", "Peak", "Times", "Elt size");
87 : : }
88 : :
89 : : /* Dump footer. */
90 : : inline void
91 : : dump_footer ()
92 : : {
93 : : fprintf (stderr, "%s" PRsa(82) PRsa(10) "\n", "Total",
94 : : SIZE_AMOUNT (m_instances), SIZE_AMOUNT (m_allocated));
95 : : }
96 : :
97 : : /* Element size. */
98 : : size_t m_element_size;
99 : : /* Pool name. */
100 : : const char *m_pool_name;
101 : : };
102 : :
103 : : extern mem_alloc_description<pool_usage> pool_allocator_usage;
104 : :
105 : : #if 0
106 : : /* If a pool with custom block size is needed, one might use the following
107 : : template. An instance of this template can be used as a parameter for
108 : : instantiating base_pool_allocator template:
109 : :
110 : : typedef custom_block_allocator <128*1024> huge_block_allocator;
111 : : ...
112 : : static base_pool_allocator <huge_block_allocator>
113 : : value_pool ("value", 16384);
114 : :
115 : : Right now it's not used anywhere in the code, and is given here as an
116 : : example). */
117 : :
118 : : template <size_t BlockSize>
119 : : class custom_block_allocator
120 : : {
121 : : public:
122 : : static const size_t block_size = BlockSize;
123 : :
124 : : static inline void *
125 : : allocate () ATTRIBUTE_MALLOC
126 : : {
127 : : return XNEWVEC (char, BlockSize);
128 : : }
129 : :
130 : : static inline void
131 : : release (void *block)
132 : : {
133 : : XDELETEVEC (block);
134 : : }
135 : : };
136 : : #endif
137 : :
138 : : /* Generic pool allocator. */
139 : :
140 : : template <typename TBlockAllocator>
141 : : class base_pool_allocator
142 : : {
143 : : public:
144 : : /* Default constructor for pool allocator called NAME. */
145 : : base_pool_allocator (const char *name, size_t size CXX_MEM_STAT_INFO);
146 : : ~base_pool_allocator ();
147 : : void release ();
148 : : void release_if_empty ();
149 : : void *allocate () ATTRIBUTE_MALLOC;
150 : : void remove (void *object);
151 : : size_t num_elts_current ();
152 : :
153 : : private:
154 : : struct allocation_pool_list
155 : : {
156 : : allocation_pool_list *next;
157 : : };
158 : :
159 : : /* Initialize a pool allocator. */
160 : : void initialize ();
161 : :
162 : : struct allocation_object
163 : : {
164 : : #if CHECKING_P
165 : : /* The ID of alloc pool which the object was allocated from. */
166 : : ALLOC_POOL_ID_TYPE id;
167 : : #endif
168 : :
169 : : union
170 : : {
171 : : /* The data of the object. */
172 : : char data[1];
173 : :
174 : : /* Because we want any type of data to be well aligned after the ID,
175 : : the following elements are here. They are never accessed so
176 : : the allocated object may be even smaller than this structure.
177 : : We do not care about alignment for floating-point types. */
178 : : char *align_p;
179 : : int64_t align_i;
180 : : } u;
181 : :
182 : : #if CHECKING_P
183 : : static inline allocation_object*
184 : : get_instance (void *data_ptr)
185 : : {
186 : : return (allocation_object *)(((char *)(data_ptr))
187 : : - offsetof (allocation_object,
188 : : u.data));
189 : : }
190 : : #endif
191 : :
192 : : static inline void*
193 : 14248507011 : get_data (void *instance_ptr)
194 : : {
195 : 14248507011 : return (void*)(((allocation_object *) instance_ptr)->u.data);
196 : : }
197 : : };
198 : :
199 : : /* Align X to 8. */
200 : : static inline size_t
201 : 31445070 : align_eight (size_t x)
202 : : {
203 : 31445070 : return (((x+7) >> 3) << 3);
204 : : }
205 : :
206 : : const char *m_name;
207 : : ALLOC_POOL_ID_TYPE m_id;
208 : : size_t m_elts_per_block;
209 : :
210 : : /* These are the elements that have been allocated at least once
211 : : and freed. */
212 : : allocation_pool_list *m_returned_free_list;
213 : :
214 : : /* These are the elements that have not yet been allocated out of
215 : : the last block obtained from XNEWVEC. */
216 : : char* m_virgin_free_list;
217 : :
218 : : /* The number of elements in the virgin_free_list that can be
219 : : allocated before needing another block. */
220 : : size_t m_virgin_elts_remaining;
221 : : /* The number of elements that are allocated. */
222 : : size_t m_elts_allocated;
223 : : /* The number of elements that are released. */
224 : : size_t m_elts_free;
225 : : /* The number of allocated blocks. */
226 : : size_t m_blocks_allocated;
227 : : /* List of blocks that are used to allocate new objects. */
228 : : allocation_pool_list *m_block_list;
229 : : /* Size of a pool elements in bytes. */
230 : : size_t m_elt_size;
231 : : /* Size in bytes that should be allocated for each element. */
232 : : size_t m_size;
233 : : /* Flag if a pool allocator is initialized. */
234 : : bool m_initialized;
235 : : /* Memory allocation location. */
236 : : mem_location m_location;
237 : : };
238 : :
239 : : template <typename TBlockAllocator>
240 : : inline
241 : 78091427 : base_pool_allocator <TBlockAllocator>::base_pool_allocator (
242 : : const char *name, size_t size MEM_STAT_DECL):
243 : 78091427 : m_name (name), m_id (0), m_elts_per_block (0), m_returned_free_list (NULL),
244 : 78091427 : m_virgin_free_list (NULL), m_virgin_elts_remaining (0), m_elts_allocated (0),
245 : 78091427 : m_elts_free (0), m_blocks_allocated (0), m_block_list (NULL), m_elt_size (0),
246 : 78091427 : m_size (size), m_initialized (false),
247 : 78091427 : m_location (ALLOC_POOL_ORIGIN, false PASS_MEM_STAT) {}
248 : :
249 : : /* Initialize a pool allocator. */
250 : :
251 : : template <typename TBlockAllocator>
252 : : inline void
253 : 31445070 : base_pool_allocator <TBlockAllocator>::initialize ()
254 : : {
255 : 31445070 : gcc_checking_assert (!m_initialized);
256 : 31445070 : m_initialized = true;
257 : :
258 : 31445070 : size_t size = m_size;
259 : :
260 : 31445070 : gcc_checking_assert (m_name);
261 : 31445070 : gcc_checking_assert (m_size);
262 : :
263 : : /* Make size large enough to store the list header. */
264 : 31445070 : if (size < sizeof (allocation_pool_list*))
265 : : size = sizeof (allocation_pool_list*);
266 : :
267 : : /* Now align the size to a multiple of 8. */
268 : 31445070 : size = align_eight (size);
269 : :
270 : : /* Add the aligned size of ID. */
271 : 31445070 : size += offsetof (allocation_object, u.data);
272 : :
273 : 31445070 : m_elt_size = size;
274 : :
275 : : if (GATHER_STATISTICS)
276 : : {
277 : : pool_usage *u = pool_allocator_usage.register_descriptor
278 : : (this, new mem_location (m_location));
279 : :
280 : : u->m_element_size = m_elt_size;
281 : : u->m_pool_name = m_name;
282 : : }
283 : :
284 : : /* List header size should be a multiple of 8. */
285 : 31445070 : size_t header_size = align_eight (sizeof (allocation_pool_list));
286 : :
287 : 31445070 : m_elts_per_block = (TBlockAllocator::block_size - header_size) / size;
288 : 31445070 : gcc_checking_assert (m_elts_per_block != 0);
289 : :
290 : : /* Increase the last used ID and use it for this pool.
291 : : ID == 0 is used for free elements of pool so skip it. */
292 : 31445070 : last_id++;
293 : 31445070 : if (last_id == 0)
294 : 0 : last_id++;
295 : :
296 : 31445070 : m_id = last_id;
297 : 31445070 : }
298 : :
299 : : /* Free all memory allocated for the given memory pool. */
300 : : template <typename TBlockAllocator>
301 : : inline void
302 : 631048657 : base_pool_allocator <TBlockAllocator>::release ()
303 : : {
304 : 631048657 : if (!m_initialized)
305 : : return;
306 : :
307 : : allocation_pool_list *block, *next_block;
308 : :
309 : : /* Free each block allocated to the pool. */
310 : 1060071884 : for (block = m_block_list; block != NULL; block = next_block)
311 : : {
312 : 515904615 : next_block = block->next;
313 : 515904615 : TBlockAllocator::release (block);
314 : : }
315 : :
316 : : if (GATHER_STATISTICS && !after_memory_report)
317 : : {
318 : : pool_allocator_usage.release_instance_overhead
319 : : (this, (m_elts_allocated - m_elts_free) * m_elt_size);
320 : : }
321 : :
322 : 544167269 : m_returned_free_list = NULL;
323 : 544167269 : m_virgin_free_list = NULL;
324 : 544167269 : m_virgin_elts_remaining = 0;
325 : 544167269 : m_elts_allocated = 0;
326 : 544167269 : m_elts_free = 0;
327 : 544167269 : m_blocks_allocated = 0;
328 : 544167269 : m_block_list = NULL;
329 : : }
330 : :
331 : : template <typename TBlockAllocator>
332 : : inline void
333 : 457553466 : base_pool_allocator <TBlockAllocator>::release_if_empty ()
334 : : {
335 : 457553466 : if (m_elts_free == m_elts_allocated)
336 : 414177292 : release ();
337 : : }
338 : :
339 : : template <typename TBlockAllocator>
340 : 78785999 : inline base_pool_allocator <TBlockAllocator>::~base_pool_allocator ()
341 : : {
342 : 78785999 : release ();
343 : 40985088 : }
344 : :
345 : : /* Allocates one element from the pool specified. */
346 : : template <typename TBlockAllocator>
347 : : inline void*
348 : 22525385308 : base_pool_allocator <TBlockAllocator>::allocate ()
349 : : {
350 : 22525385308 : if (!m_initialized)
351 : 31445070 : initialize ();
352 : :
353 : : allocation_pool_list *header;
354 : : #ifdef ENABLE_VALGRIND_ANNOTATIONS
355 : : int size;
356 : : #endif
357 : :
358 : : if (GATHER_STATISTICS)
359 : : {
360 : : pool_allocator_usage.register_instance_overhead (m_elt_size, this);
361 : : }
362 : :
363 : : #ifdef ENABLE_VALGRIND_ANNOTATIONS
364 : : size = m_elt_size - offsetof (allocation_object, u.data);
365 : : #endif
366 : :
367 : : /* If there are no more free elements, make some more!. */
368 : 22525385308 : if (!m_returned_free_list)
369 : : {
370 : : char *block;
371 : 14248507011 : if (!m_virgin_elts_remaining)
372 : : {
373 : : allocation_pool_list *block_header;
374 : :
375 : : /* Make the block. */
376 : 515926477 : block = reinterpret_cast<char *> (TBlockAllocator::allocate ());
377 : 515926477 : block_header = new (block) allocation_pool_list;
378 : 515926477 : block += align_eight (sizeof (allocation_pool_list));
379 : :
380 : : /* Throw it on the block list. */
381 : 515926477 : block_header->next = m_block_list;
382 : 515926477 : m_block_list = block_header;
383 : :
384 : : /* Make the block available for allocation. */
385 : 515926477 : m_virgin_free_list = block;
386 : 515926477 : m_virgin_elts_remaining = m_elts_per_block;
387 : :
388 : : /* Also update the number of elements we have free/allocated, and
389 : : increment the allocated block count. */
390 : 515926477 : m_elts_allocated += m_elts_per_block;
391 : 515926477 : m_elts_free += m_elts_per_block;
392 : 515926477 : m_blocks_allocated += 1;
393 : : }
394 : :
395 : : /* We now know that we can take the first elt off the virgin list and
396 : : put it on the returned list. */
397 : 14248507011 : block = m_virgin_free_list;
398 : 14248507011 : header = (allocation_pool_list*) allocation_object::get_data (block);
399 : 14248507011 : header->next = NULL;
400 : :
401 : : /* Mark the element to be free. */
402 : : #if CHECKING_P
403 : 14248507011 : ((allocation_object*) block)->id = 0;
404 : : #endif
405 : : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size));
406 : 14248507011 : m_returned_free_list = header;
407 : 14248507011 : m_virgin_free_list += m_elt_size;
408 : 14248507011 : m_virgin_elts_remaining--;
409 : :
410 : : }
411 : :
412 : : /* Pull the first free element from the free list, and return it. */
413 : 22525385308 : header = m_returned_free_list;
414 : : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof (*header)));
415 : 22525385308 : m_returned_free_list = header->next;
416 : 22525385308 : m_elts_free--;
417 : :
418 : : /* Set the ID for element. */
419 : : #if CHECKING_P
420 : 22525385308 : allocation_object::get_instance (header)->id = m_id;
421 : : #endif
422 : : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size));
423 : :
424 : 22525385308 : return (void *)(header);
425 : : }
426 : :
427 : : /* Puts PTR back on POOL's free list. */
428 : : template <typename TBlockAllocator>
429 : : inline void
430 : 15567522321 : base_pool_allocator <TBlockAllocator>::remove (void *object)
431 : : {
432 : 15567522321 : int size = m_elt_size - offsetof (allocation_object, u.data);
433 : :
434 : 15567522321 : if (flag_checking)
435 : : {
436 : 15567481521 : gcc_assert (m_initialized);
437 : 15567481521 : gcc_assert (object
438 : : /* Check if we free more than we allocated. */
439 : : && m_elts_free < m_elts_allocated);
440 : : #if CHECKING_P
441 : : /* Check whether the PTR was allocated from POOL. */
442 : 15567481521 : gcc_assert (m_id == allocation_object::get_instance (object)->id);
443 : : #endif
444 : :
445 : 15567481521 : memset (object, 0xaf, size);
446 : : }
447 : :
448 : : #if CHECKING_P
449 : : /* Mark the element to be free. */
450 : 15567522321 : allocation_object::get_instance (object)->id = 0;
451 : : #endif
452 : :
453 : 15567522321 : allocation_pool_list *header = new (object) allocation_pool_list;
454 : 15567522321 : header->next = m_returned_free_list;
455 : 15567522321 : m_returned_free_list = header;
456 : : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (object, size));
457 : 15567522321 : m_elts_free++;
458 : :
459 : : if (GATHER_STATISTICS)
460 : : {
461 : : pool_allocator_usage.release_instance_overhead (this, m_elt_size);
462 : : }
463 : 15567522321 : }
464 : :
465 : : /* Number of elements currently active (not returned to pool). Used for cheap
466 : : consistency checks. */
467 : : template <typename TBlockAllocator>
468 : : inline size_t
469 : : base_pool_allocator <TBlockAllocator>::num_elts_current ()
470 : : {
471 : : return m_elts_allocated - m_elts_free;
472 : : }
473 : :
474 : : /* Specialization of base_pool_allocator which should be used in most cases.
475 : : Another specialization may be needed, if object size is greater than
476 : : memory_block_pool::block_size (64 KB). */
477 : : typedef base_pool_allocator <memory_block_pool> pool_allocator;
478 : :
479 : : /* Type based memory pool allocator. */
480 : : template <typename T>
481 : 37800903 : class object_allocator
482 : : {
483 : : public:
484 : : /* Default constructor for pool allocator called NAME. */
485 : 37943911 : object_allocator (const char *name CXX_MEM_STAT_INFO):
486 : 22163227 : m_allocator (name, sizeof (T) PASS_MEM_STAT) {}
487 : :
488 : : inline void
489 : 115030749 : release ()
490 : : {
491 : 67728983 : m_allocator.release ();
492 : 20598610 : }
493 : :
494 : 228776733 : inline void release_if_empty ()
495 : : {
496 : 435865379 : m_allocator.release_if_empty ();
497 : : }
498 : :
499 : :
500 : : /* Allocate memory for instance of type T and call a default constructor. */
501 : :
502 : : inline T *
503 : 21809469323 : allocate () ATTRIBUTE_MALLOC
504 : : {
505 : 20957640217 : return ::new (m_allocator.allocate ()) T;
506 : : }
507 : :
508 : : /* Allocate memory for instance of type T and return void * that
509 : : could be used in situations where a default constructor is not provided
510 : : by the class T. */
511 : :
512 : : inline void *
513 : 9323160 : allocate_raw () ATTRIBUTE_MALLOC
514 : : {
515 : 9323160 : return m_allocator.allocate ();
516 : : }
517 : :
518 : : inline void
519 : 15243404168 : remove (T *object)
520 : : {
521 : : /* Call destructor. */
522 : 15189511985 : object->~T ();
523 : :
524 : 15169698193 : m_allocator.remove (object);
525 : 8930298406 : }
526 : :
527 : : inline void
528 : 7341880 : remove_raw (void *object)
529 : : {
530 : 7341880 : m_allocator.remove (object);
531 : : }
532 : :
533 : : inline size_t
534 : : num_elts_current ()
535 : : {
536 : : return m_allocator.num_elts_current ();
537 : : }
538 : :
539 : : private:
540 : : pool_allocator m_allocator;
541 : : };
542 : :
543 : : /* Store information about each particular alloc_pool. Note that this
544 : : will underestimate the amount the amount of storage used by a small amount:
545 : : 1) The overhead in a pool is not accounted for.
546 : : 2) The unallocated elements in a block are not accounted for. Note
547 : : that this can at worst case be one element smaller that the block
548 : : size for that pool. */
549 : : struct alloc_pool_descriptor
550 : : {
551 : : /* Number of pools allocated. */
552 : : unsigned long created;
553 : : /* Gross allocated storage. */
554 : : unsigned long allocated;
555 : : /* Amount of currently active storage. */
556 : : unsigned long current;
557 : : /* Peak amount of storage used. */
558 : : unsigned long peak;
559 : : /* Size of element in the pool. */
560 : : int elt_size;
561 : : };
562 : :
563 : : /* Helper for classes that do not provide default ctor. */
564 : :
565 : : template <typename T>
566 : : inline void *
567 : 1981280 : operator new (size_t, object_allocator<T> &a)
568 : : {
569 : 1981280 : return a.allocate_raw ();
570 : : }
571 : :
572 : : /* Hashtable mapping alloc_pool names to descriptors. */
573 : : extern hash_map<const char *, alloc_pool_descriptor> *alloc_pool_hash;
574 : :
575 : :
576 : : #endif
|
