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 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 15252850618 : get_data (void *instance_ptr)
194 : {
195 15252850618 : return (void*)(((allocation_object *) instance_ptr)->u.data);
196 : }
197 : };
198 :
199 : /* Align X to 8. */
200 : static inline size_t
201 32316707 : align_eight (size_t x)
202 : {
203 32316707 : 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 80238384 : base_pool_allocator <TBlockAllocator>::base_pool_allocator (
242 : const char *name, size_t size MEM_STAT_DECL):
243 80238384 : m_name (name), m_id (0), m_elts_per_block (0), m_returned_free_list (NULL),
244 80238384 : m_virgin_free_list (NULL), m_virgin_elts_remaining (0), m_elts_allocated (0),
245 80238384 : m_elts_free (0), m_blocks_allocated (0), m_block_list (NULL), m_elt_size (0),
246 80238384 : m_size (size), m_initialized (false),
247 80238384 : m_location (ALLOC_POOL_ORIGIN, false PASS_MEM_STAT) {}
248 :
249 : /* Initialize a pool allocator. */
250 :
251 : template <typename TBlockAllocator>
252 : inline void
253 32316707 : base_pool_allocator <TBlockAllocator>::initialize ()
254 : {
255 32316707 : gcc_checking_assert (!m_initialized);
256 32316707 : m_initialized = true;
257 :
258 32316707 : size_t size = m_size;
259 :
260 32316707 : gcc_checking_assert (m_name);
261 32316707 : gcc_checking_assert (m_size);
262 :
263 : /* Make size large enough to store the list header. */
264 32316707 : if (size < sizeof (allocation_pool_list*))
265 : size = sizeof (allocation_pool_list*);
266 :
267 : /* Now align the size to a multiple of 8. */
268 32316707 : size = align_eight (size);
269 :
270 : /* Add the aligned size of ID. */
271 32316707 : size += offsetof (allocation_object, u.data);
272 :
273 32316707 : 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 32316707 : size_t header_size = align_eight (sizeof (allocation_pool_list));
286 :
287 32316707 : m_elts_per_block = (TBlockAllocator::block_size - header_size) / size;
288 32316707 : 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 32316707 : last_id++;
293 32316707 : if (last_id == 0)
294 0 : last_id++;
295 :
296 32316707 : m_id = last_id;
297 32316707 : }
298 :
299 : /* Free all memory allocated for the given memory pool. */
300 : template <typename TBlockAllocator>
301 : inline void
302 672211271 : base_pool_allocator <TBlockAllocator>::release ()
303 : {
304 672211271 : if (!m_initialized)
305 : return;
306 :
307 : allocation_pool_list *block, *next_block;
308 :
309 : /* Free each block allocated to the pool. */
310 1135490009 : for (block = m_block_list; block != NULL; block = next_block)
311 : {
312 553045704 : next_block = block->next;
313 553045704 : 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 582444305 : m_returned_free_list = NULL;
323 582444305 : m_virgin_free_list = NULL;
324 582444305 : m_virgin_elts_remaining = 0;
325 582444305 : m_elts_allocated = 0;
326 582444305 : m_elts_free = 0;
327 582444305 : m_blocks_allocated = 0;
328 582444305 : m_block_list = NULL;
329 : }
330 :
331 : template <typename TBlockAllocator>
332 : inline void
333 492969916 : base_pool_allocator <TBlockAllocator>::release_if_empty ()
334 : {
335 492969916 : if (m_elts_free == m_elts_allocated)
336 446446894 : release ();
337 : }
338 :
339 : template <typename TBlockAllocator>
340 80929377 : inline base_pool_allocator <TBlockAllocator>::~base_pool_allocator ()
341 : {
342 80929377 : release ();
343 42002989 : }
344 :
345 : /* Allocates one element from the pool specified. */
346 : template <typename TBlockAllocator>
347 : inline void*
348 24438923735 : base_pool_allocator <TBlockAllocator>::allocate ()
349 : {
350 24438923735 : if (!m_initialized)
351 32316707 : 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 24438923735 : if (!m_returned_free_list)
369 : {
370 : char *block;
371 15252850618 : if (!m_virgin_elts_remaining)
372 : {
373 : allocation_pool_list *block_header;
374 :
375 : /* Make the block. */
376 553067296 : block = reinterpret_cast<char *> (TBlockAllocator::allocate ());
377 553067296 : block_header = new (block) allocation_pool_list;
378 553067296 : block += align_eight (sizeof (allocation_pool_list));
379 :
380 : /* Throw it on the block list. */
381 553067296 : block_header->next = m_block_list;
382 553067296 : m_block_list = block_header;
383 :
384 : /* Make the block available for allocation. */
385 553067296 : m_virgin_free_list = block;
386 553067296 : 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 553067296 : m_elts_allocated += m_elts_per_block;
391 553067296 : m_elts_free += m_elts_per_block;
392 553067296 : 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 15252850618 : block = m_virgin_free_list;
398 15252850618 : header = (allocation_pool_list*) allocation_object::get_data (block);
399 15252850618 : header->next = NULL;
400 :
401 : /* Mark the element to be free. */
402 : #if CHECKING_P
403 15252850618 : ((allocation_object*) block)->id = 0;
404 : #endif
405 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size));
406 15252850618 : m_returned_free_list = header;
407 15252850618 : m_virgin_free_list += m_elt_size;
408 15252850618 : m_virgin_elts_remaining--;
409 :
410 : }
411 :
412 : /* Pull the first free element from the free list, and return it. */
413 24438923735 : header = m_returned_free_list;
414 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof (*header)));
415 24438923735 : m_returned_free_list = header->next;
416 24438923735 : m_elts_free--;
417 :
418 : /* Set the ID for element. */
419 : #if CHECKING_P
420 24438923735 : allocation_object::get_instance (header)->id = m_id;
421 : #endif
422 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size));
423 :
424 24438923735 : return (void *)(header);
425 : }
426 :
427 : /* Puts PTR back on POOL's free list. */
428 : template <typename TBlockAllocator>
429 : inline void
430 17107312522 : base_pool_allocator <TBlockAllocator>::remove (void *object)
431 : {
432 17107312522 : int size = m_elt_size - offsetof (allocation_object, u.data);
433 :
434 17107312522 : if (flag_checking)
435 : {
436 17107264881 : gcc_assert (m_initialized);
437 17107264881 : 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 17107264881 : gcc_assert (m_id == allocation_object::get_instance (object)->id);
443 : #endif
444 :
445 17107264881 : memset (object, 0xaf, size);
446 : }
447 :
448 : #if CHECKING_P
449 : /* Mark the element to be free. */
450 17107312522 : allocation_object::get_instance (object)->id = 0;
451 : #endif
452 :
453 17107312522 : allocation_pool_list *header = new (object) allocation_pool_list;
454 17107312522 : header->next = m_returned_free_list;
455 17107312522 : m_returned_free_list = header;
456 : VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (object, size));
457 17107312522 : m_elts_free++;
458 :
459 : if (GATHER_STATISTICS)
460 : {
461 : pool_allocator_usage.release_instance_overhead (this, m_elt_size);
462 : }
463 17107312522 : }
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 38926380 : class object_allocator
482 : {
483 : public:
484 : /* Default constructor for pool allocator called NAME. */
485 39080127 : object_allocator (const char *name CXX_MEM_STAT_INFO):
486 22907067 : m_allocator (name, sizeof (T) PASS_MEM_STAT) {}
487 :
488 : inline void
489 120706845 : release ()
490 : {
491 75633498 : m_allocator.release ();
492 21949609 : }
493 :
494 246484958 : inline void release_if_empty ()
495 : {
496 469708405 : 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 23669289575 : allocate () ATTRIBUTE_MALLOC
504 : {
505 22791970689 : 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 9221000 : allocate_raw () ATTRIBUTE_MALLOC
514 : {
515 9221000 : return m_allocator.allocate ();
516 : }
517 :
518 : inline void
519 16753045256 : remove (T *object)
520 : {
521 : /* Call destructor. */
522 16696745844 : object->~T ();
523 :
524 16674026644 : m_allocator.remove (object);
525 9906599272 : }
526 :
527 : inline void
528 7100833 : remove_raw (void *object)
529 : {
530 7100833 : 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 2120167 : operator new (size_t, object_allocator<T> &a)
568 : {
569 2120167 : 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
|
