Line data Source code
1 : /* Functions to support a pool of allocatable objects
2 : Copyright (C) 1997-2026 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 constructor. */
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 : inline auto &
104 : pool_allocator_usage ()
105 : {
106 : return mem_alloc_description<pool_usage>::instance<ALLOC_POOL_ORIGIN> ();
107 : }
108 :
109 : #if 0
110 : /* If a pool with custom block size is needed, one might use the following
111 : template. An instance of this template can be used as a parameter for
112 : instantiating base_pool_allocator template:
113 :
114 : typedef custom_block_allocator <128*1024> huge_block_allocator;
115 : ...
116 : static base_pool_allocator <huge_block_allocator>
117 : value_pool ("value", 16384);
118 :
119 : Right now it's not used anywhere in the code, and is given here as an
120 : example). */
121 :
122 : template <size_t BlockSize>
123 : class custom_block_allocator
124 : {
125 : public:
126 : static const size_t block_size = BlockSize;
127 :
128 : static inline void *
129 : allocate () ATTRIBUTE_MALLOC
130 : {
131 : return XNEWVEC (char, BlockSize);
132 : }
133 :
134 : static inline void
135 : release (void *block)
136 : {
137 : XDELETEVEC (block);
138 : }
139 : };
140 : #endif
141 :
142 : /* Generic pool allocator. */
143 :
144 : template <typename TBlockAllocator>
145 : class base_pool_allocator
146 : {
147 : public:
148 : /* Default constructor for pool allocator called NAME. */
149 : base_pool_allocator (const char *name, size_t size CXX_MEM_STAT_INFO);
150 : ~base_pool_allocator ();
151 : void release ();
152 : void release_if_empty ();
153 : void *allocate () ATTRIBUTE_MALLOC;
154 : void remove (void *object);
155 : size_t num_elts_current ();
156 :
157 : private:
158 : struct allocation_pool_list
159 : {
160 : allocation_pool_list *next;
161 : };
162 :
163 : /* Initialize a pool allocator. */
164 : void initialize ();
165 :
166 : struct allocation_object
167 : {
168 : #if CHECKING_P
169 : /* The ID of alloc pool which the object was allocated from. */
170 : ALLOC_POOL_ID_TYPE id;
171 : #endif
172 :
173 : union
174 : {
175 : /* The data of the object. */
176 : char data[1];
177 :
178 : /* Because we want any type of data to be well aligned after the ID,
179 : the following elements are here. They are never accessed so
180 : the allocated object may be even smaller than this structure.
181 : We do not care about alignment for floating-point types. */
182 : char *align_p;
183 : int64_t align_i;
184 : } u;
185 :
186 : #if CHECKING_P
187 : static inline allocation_object*
188 : get_instance (void *data_ptr)
189 : {
190 : return (allocation_object *)(((char *)(data_ptr))
191 : - offsetof (allocation_object,
192 : u.data));
193 : }
194 : #endif
195 :
196 : static inline void*
197 15479179674 : get_data (void *instance_ptr)
198 : {
199 15479179674 : return (void*)(((allocation_object *) instance_ptr)->u.data);
200 : }
201 : };
202 :
203 : /* Align X to 8. */
204 : static inline size_t
205 32134889 : align_eight (size_t x)
206 : {
207 32134889 : return (((x+7) >> 3) << 3);
208 : }
209 :
210 : const char *m_name;
211 : ALLOC_POOL_ID_TYPE m_id;
212 : size_t m_elts_per_block;
213 :
214 : /* These are the elements that have been allocated at least once
215 : and freed. */
216 : allocation_pool_list *m_returned_free_list;
217 :
218 : /* These are the elements that have not yet been allocated out of
219 : the last block obtained from XNEWVEC. */
220 : char* m_virgin_free_list;
221 :
222 : /* The number of elements in the virgin_free_list that can be
223 : allocated before needing another block. */
224 : size_t m_virgin_elts_remaining;
225 : /* The number of elements that are allocated. */
226 : size_t m_elts_allocated;
227 : /* The number of elements that are released. */
228 : size_t m_elts_free;
229 : /* The number of allocated blocks. */
230 : size_t m_blocks_allocated;
231 : /* List of blocks that are used to allocate new objects. */
232 : allocation_pool_list *m_block_list;
233 : /* Size of a pool elements in bytes. */
234 : size_t m_elt_size;
235 : /* Size in bytes that should be allocated for each element. */
236 : size_t m_size;
237 : /* Flag if a pool allocator is initialized. */
238 : bool m_initialized;
239 : /* Memory allocation location. */
240 : mem_location m_location;
241 : };
242 :
243 : template <typename TBlockAllocator>
244 : inline
245 81806775 : base_pool_allocator <TBlockAllocator>::base_pool_allocator (
246 : const char *name, size_t size MEM_STAT_DECL):
247 81806775 : m_name (name), m_id (0), m_elts_per_block (0), m_returned_free_list (NULL),
248 81806775 : m_virgin_free_list (NULL), m_virgin_elts_remaining (0), m_elts_allocated (0),
249 81806775 : m_elts_free (0), m_blocks_allocated (0), m_block_list (NULL), m_elt_size (0),
250 81806775 : m_size (size), m_initialized (false),
251 81806775 : m_location (ALLOC_POOL_ORIGIN, false PASS_MEM_STAT) {}
252 :
253 : /* Initialize a pool allocator. */
254 :
255 : template <typename TBlockAllocator>
256 : inline void
257 32134889 : base_pool_allocator <TBlockAllocator>::initialize ()
258 : {
259 32134889 : gcc_checking_assert (!m_initialized);
260 32134889 : m_initialized = true;
261 :
262 32134889 : size_t size = m_size;
263 :
264 32134889 : gcc_checking_assert (m_name);
265 32134889 : gcc_checking_assert (m_size);
266 :
267 : /* Make size large enough to store the list header. */
268 32134889 : if (size < sizeof (allocation_pool_list*))
269 : size = sizeof (allocation_pool_list*);
270 :
271 : /* Now align the size to a multiple of 8. */
272 32134889 : size = align_eight (size);
273 :
274 : /* Add the aligned size of ID. */
275 32134889 : size += offsetof (allocation_object, u.data);
276 :
277 32134889 : m_elt_size = size;
278 :
279 : if (GATHER_STATISTICS)
280 : {
281 : pool_usage *u = pool_allocator_usage ().register_descriptor
282 : (this, new mem_location (m_location));
283 :
284 : u->m_element_size = m_elt_size;
285 : u->m_pool_name = m_name;
286 : }
287 :
288 : /* List header size should be a multiple of 8. */
289 32134889 : size_t header_size = align_eight (sizeof (allocation_pool_list));
290 :
291 32134889 : m_elts_per_block = (TBlockAllocator::block_size - header_size) / size;
292 32134889 : gcc_checking_assert (m_elts_per_block != 0);
293 :
294 : /* Increase the last used ID and use it for this pool.
295 : ID == 0 is used for free elements of pool so skip it. */
296 32134889 : last_id++;
297 32134889 : if (last_id == 0)
298 0 : last_id++;
299 :
300 32134889 : m_id = last_id;
301 32134889 : }
302 :
303 : /* Free all memory allocated for the given memory pool. */
304 : template <typename TBlockAllocator>
305 : inline void
306 695168325 : base_pool_allocator <TBlockAllocator>::release ()
307 : {
308 695168325 : if (!m_initialized)
309 : return;
310 :
311 : allocation_pool_list *block, *next_block;
312 :
313 : /* Free each block allocated to the pool. */
314 1175534291 : for (block = m_block_list; block != NULL; block = next_block)
315 : {
316 572600692 : next_block = block->next;
317 572600692 : TBlockAllocator::release (block);
318 : }
319 :
320 : if (GATHER_STATISTICS && !after_memory_report)
321 : {
322 : pool_allocator_usage ().release_instance_overhead
323 : (this, (m_elts_allocated - m_elts_free) * m_elt_size);
324 : }
325 :
326 602933599 : m_returned_free_list = NULL;
327 602933599 : m_virgin_free_list = NULL;
328 602933599 : m_virgin_elts_remaining = 0;
329 602933599 : m_elts_allocated = 0;
330 602933599 : m_elts_free = 0;
331 602933599 : m_blocks_allocated = 0;
332 602933599 : m_block_list = NULL;
333 : }
334 :
335 : template <typename TBlockAllocator>
336 : inline void
337 513191566 : base_pool_allocator <TBlockAllocator>::release_if_empty ()
338 : {
339 513191566 : if (m_elts_free == m_elts_allocated)
340 464828512 : release ();
341 : }
342 :
343 : template <typename TBlockAllocator>
344 82519983 : inline base_pool_allocator <TBlockAllocator>::~base_pool_allocator ()
345 : {
346 82519983 : release ();
347 43192860 : }
348 :
349 : /* Allocates one element from the pool specified. */
350 : template <typename TBlockAllocator>
351 : inline void*
352 24973234601 : base_pool_allocator <TBlockAllocator>::allocate ()
353 : {
354 24973234601 : if (!m_initialized)
355 32134889 : initialize ();
356 :
357 : allocation_pool_list *header;
358 : #ifdef ENABLE_VALGRIND_ANNOTATIONS
359 : int size;
360 : #endif
361 :
362 : if (GATHER_STATISTICS)
363 : {
364 : pool_allocator_usage ().register_instance_overhead (m_elt_size, this);
365 : }
366 :
367 : #ifdef ENABLE_VALGRIND_ANNOTATIONS
368 : size = m_elt_size - offsetof (allocation_object, u.data);
369 : #endif
370 :
371 : /* If there are no more free elements, make some more!. */
372 24973234601 : if (!m_returned_free_list)
373 : {
374 : char *block;
375 15479179674 : if (!m_virgin_elts_remaining)
376 : {
377 : allocation_pool_list *block_header;
378 :
379 : /* Make the block. */
380 572622681 : block = reinterpret_cast<char *> (TBlockAllocator::allocate ());
381 572622681 : block_header = new (block) allocation_pool_list;
382 572622681 : block += align_eight (sizeof (allocation_pool_list));
383 :
384 : /* Throw it on the block list. */
385 572622681 : block_header->next = m_block_list;
386 572622681 : m_block_list = block_header;
387 :
388 : /* Make the block available for allocation. */
389 572622681 : m_virgin_free_list = block;
390 572622681 : m_virgin_elts_remaining = m_elts_per_block;
391 :
392 : /* Also update the number of elements we have free/allocated, and
393 : increment the allocated block count. */
394 572622681 : m_elts_allocated += m_elts_per_block;
395 572622681 : m_elts_free += m_elts_per_block;
396 572622681 : m_blocks_allocated += 1;
397 : }
398 :
399 : /* We now know that we can take the first elt off the virgin list and
400 : put it on the returned list. */
401 15479179674 : block = m_virgin_free_list;
402 15479179674 : header = (allocation_pool_list*) allocation_object::get_data (block);
403 15479179674 : header->next = NULL;
404 :
405 : /* Mark the element to be free. */
406 : #if CHECKING_P
407 15479179674 : ((allocation_object*) block)->id = 0;
408 : #endif
409 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size));
410 15479179674 : m_returned_free_list = header;
411 15479179674 : m_virgin_free_list += m_elt_size;
412 15479179674 : m_virgin_elts_remaining--;
413 :
414 : }
415 :
416 : /* Pull the first free element from the free list, and return it. */
417 24973234601 : header = m_returned_free_list;
418 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof (*header)));
419 24973234601 : m_returned_free_list = header->next;
420 24973234601 : m_elts_free--;
421 :
422 : /* Set the ID for element. */
423 : #if CHECKING_P
424 24973234601 : allocation_object::get_instance (header)->id = m_id;
425 : #endif
426 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size));
427 :
428 24973234601 : return (void *)(header);
429 : }
430 :
431 : /* Puts PTR back on POOL's free list. */
432 : template <typename TBlockAllocator>
433 : inline void
434 17682307435 : base_pool_allocator <TBlockAllocator>::remove (void *object)
435 : {
436 17682307435 : int size = m_elt_size - offsetof (allocation_object, u.data);
437 :
438 17682307435 : if (flag_checking)
439 : {
440 17682260213 : gcc_assert (m_initialized);
441 17682260213 : gcc_assert (object
442 : /* Check if we free more than we allocated. */
443 : && m_elts_free < m_elts_allocated);
444 : #if CHECKING_P
445 : /* Check whether the PTR was allocated from POOL. */
446 17682260213 : gcc_assert (m_id == allocation_object::get_instance (object)->id);
447 : #endif
448 :
449 17682260213 : memset (object, 0xaf, size);
450 : }
451 :
452 : #if CHECKING_P
453 : /* Mark the element to be free. */
454 17682307435 : allocation_object::get_instance (object)->id = 0;
455 : #endif
456 :
457 17682307435 : allocation_pool_list *header = new (object) allocation_pool_list;
458 17682307435 : header->next = m_returned_free_list;
459 17682307435 : m_returned_free_list = header;
460 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (object, size));
461 17682307435 : m_elts_free++;
462 :
463 : if (GATHER_STATISTICS)
464 : {
465 : pool_allocator_usage ().release_instance_overhead (this, m_elt_size);
466 : }
467 17682307435 : }
468 :
469 : /* Number of elements currently active (not returned to pool). Used for cheap
470 : consistency checks. */
471 : template <typename TBlockAllocator>
472 : inline size_t
473 : base_pool_allocator <TBlockAllocator>::num_elts_current ()
474 : {
475 : return m_elts_allocated - m_elts_free;
476 : }
477 :
478 : /* Specialization of base_pool_allocator which should be used in most cases.
479 : Another specialization may be needed, if object size is greater than
480 : memory_block_pool::block_size (64 KB). */
481 : typedef base_pool_allocator <memory_block_pool> pool_allocator;
482 :
483 : /* Type based memory pool allocator. */
484 : template <typename T>
485 39327115 : class object_allocator
486 : {
487 : public:
488 : /* Default constructor for pool allocator called NAME. */
489 39483747 : object_allocator (const char *name CXX_MEM_STAT_INFO):
490 22844698 : m_allocator (name, sizeof (T) PASS_MEM_STAT) {}
491 :
492 : inline void
493 123187747 : release ()
494 : {
495 77264219 : m_allocator.release ();
496 : }
497 :
498 256595783 : inline void release_if_empty ()
499 : {
500 489010039 : m_allocator.release_if_empty ();
501 : }
502 :
503 :
504 : /* Allocate memory for instance of type T and call a default constructor. */
505 :
506 : template<typename... Ts>
507 : inline ATTRIBUTE_MALLOC T *
508 22848056020 : allocate (Ts... args)
509 : {
510 23137634611 : return ::new (m_allocator.allocate ()) T (std::forward<Ts> (args)...);
511 : }
512 :
513 : /* Allocate memory for instance of type T and return void * that
514 : could be used in situations where a default constructor is not provided
515 : by the class T. */
516 :
517 : inline void *
518 10438717 : allocate_raw () ATTRIBUTE_MALLOC
519 : {
520 10438717 : return m_allocator.allocate ();
521 : }
522 :
523 : inline void
524 17310621691 : remove (T *object)
525 : {
526 : /* Call destructor. */
527 17252247469 : object->~T ();
528 :
529 15239309404 : m_allocator.remove (object);
530 1280185 : }
531 :
532 : inline void
533 8274227 : remove_raw (void *object)
534 : {
535 8274227 : m_allocator.remove (object);
536 : }
537 :
538 : inline size_t
539 : num_elts_current ()
540 : {
541 : return m_allocator.num_elts_current ();
542 : }
543 :
544 : private:
545 : pool_allocator m_allocator;
546 : };
547 :
548 : /* Store information about each particular alloc_pool. Note that this
549 : will underestimate the amount the amount of storage used by a small amount:
550 : 1) The overhead in a pool is not accounted for.
551 : 2) The unallocated elements in a block are not accounted for. Note
552 : that this can at worst case be one element smaller that the block
553 : size for that pool. */
554 : struct alloc_pool_descriptor
555 : {
556 : /* Number of pools allocated. */
557 : unsigned long created;
558 : /* Gross allocated storage. */
559 : unsigned long allocated;
560 : /* Amount of currently active storage. */
561 : unsigned long current;
562 : /* Peak amount of storage used. */
563 : unsigned long peak;
564 : /* Size of element in the pool. */
565 : int elt_size;
566 : };
567 :
568 : /* Helper for classes that do not provide default ctor. */
569 :
570 : template <typename T>
571 : inline void *
572 2164490 : operator new (size_t, object_allocator<T> &a)
573 : {
574 2164490 : return a.allocate_raw ();
575 : }
576 :
577 : /* Hashtable mapping alloc_pool names to descriptors. */
578 : extern hash_map<const char *, alloc_pool_descriptor> *alloc_pool_hash;
579 :
580 :
581 : #endif
|
