GCC Middle and Back End API Reference
alloc-pool.h
Go to the documentation of this file.
1/* Functions to support a pool of allocatable objects
2 Copyright (C) 1997-2024 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@cgsoftware.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
26extern void dump_alloc_pool_statistics (void);
27
28/* Flag indicates whether memory statistics are gathered any longer. */
29extern bool after_memory_report;
30
31typedef unsigned long ALLOC_POOL_ID_TYPE;
32
33/* Last used ID. */
35
36/* Pool allocator memory usage. */
37class pool_usage: public mem_usage
38{
39public:
40 /* Default contructor. */
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. */
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,
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,
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
92 {
93 fprintf (stderr, "%s" PRsa(82) PRsa(10) "\n", "Total",
95 }
96
97 /* Element size. */
99 /* Pool name. */
100 const char *m_pool_name;
101};
102
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
118template <size_t BlockSize>
119class custom_block_allocator
120{
121public:
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
140template <typename TBlockAllocator>
142{
143public:
144 /* Default constructor for pool allocator called NAME. */
145 base_pool_allocator (const char *name, size_t size CXX_MEM_STAT_INFO);
147 void release ();
149 void *allocate () ATTRIBUTE_MALLOC;
150 void remove (void *object);
152
153private:
158
159 /* Initialize a pool allocator. */
160 void initialize ();
161
163 {
164#if CHECKING_P
165 /* The ID of alloc pool which the object was allocated from. */
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))
188 u.data));
189 }
190#endif
191
192 static inline void*
193 get_data (void *instance_ptr)
194 {
195 return (void*)(((allocation_object *) instance_ptr)->u.data);
196 }
197 };
198
199 /* Align X to 8. */
200 static inline size_t
201 align_eight (size_t x)
202 {
203 return (((x+7) >> 3) << 3);
204 }
205
206 const char *m_name;
209
210 /* These are the elements that have been allocated at least once
211 and freed. */
213
214 /* These are the elements that have not yet been allocated out of
215 the last block obtained from XNEWVEC. */
217
218 /* The number of elements in the virgin_free_list that can be
219 allocated before needing another block. */
221 /* The number of elements that are allocated. */
223 /* The number of elements that are released. */
225 /* The number of allocated blocks. */
227 /* List of blocks that are used to allocate new objects. */
229 /* Size of a pool elements in bytes. */
231 /* Size in bytes that should be allocated for each element. */
232 size_t m_size;
233 /* Flag if a pool allocator is initialized. */
235 /* Memory allocation location. */
237};
238
239template <typename TBlockAllocator>
240inline
242 const char *name, size_t size MEM_STAT_DECL):
243 m_name (name), m_id (0), m_elts_per_block (0), m_returned_free_list (NULL),
244 m_virgin_free_list (NULL), m_virgin_elts_remaining (0), m_elts_allocated (0),
245 m_elts_free (0), m_blocks_allocated (0), m_block_list (NULL), m_elt_size (0),
246 m_size (size), m_initialized (false),
247 m_location (ALLOC_POOL_ORIGIN, false PASS_MEM_STAT) {}
248
249/* Initialize a pool allocator. */
250
251template <typename TBlockAllocator>
252inline void
254{
255 gcc_checking_assert (!m_initialized);
256 m_initialized = true;
257
258 size_t size = m_size;
259
260 gcc_checking_assert (m_name);
261 gcc_checking_assert (m_size);
262
263 /* Make size large enough to store the list header. */
264 if (size < sizeof (allocation_pool_list*))
265 size = sizeof (allocation_pool_list*);
266
267 /* Now align the size to a multiple of 8. */
268 size = align_eight (size);
269
270 /* Add the aligned size of ID. */
271 size += offsetof (allocation_object, u.data);
272
273 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 size_t header_size = align_eight (sizeof (allocation_pool_list));
286
287 m_elts_per_block = (TBlockAllocator::block_size - header_size) / size;
288 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 last_id++;
293 if (last_id == 0)
294 last_id++;
295
296 m_id = last_id;
297}
298
299/* Free all memory allocated for the given memory pool. */
300template <typename TBlockAllocator>
301inline void
303{
304 if (!m_initialized)
305 return;
306
307 allocation_pool_list *block, *next_block;
308
309 /* Free each block allocated to the pool. */
310 for (block = m_block_list; block != NULL; block = next_block)
311 {
312 next_block = block->next;
313 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 m_returned_free_list = NULL;
323 m_virgin_free_list = NULL;
324 m_virgin_elts_remaining = 0;
325 m_elts_allocated = 0;
326 m_elts_free = 0;
327 m_blocks_allocated = 0;
328 m_block_list = NULL;
329}
330
331template <typename TBlockAllocator>
332inline void
334{
335 if (m_elts_free == m_elts_allocated)
336 release ();
337}
338
339template <typename TBlockAllocator>
340inline base_pool_allocator <TBlockAllocator>::~base_pool_allocator ()
341{
342 release ();
343}
344
345/* Allocates one element from the pool specified. */
346template <typename TBlockAllocator>
347inline void*
349{
350 if (!m_initialized)
351 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 if (!m_returned_free_list)
369 {
370 char *block;
371 if (!m_virgin_elts_remaining)
372 {
373 allocation_pool_list *block_header;
374
375 /* Make the block. */
376 block = reinterpret_cast<char *> (TBlockAllocator::allocate ());
377 block_header = new (block) allocation_pool_list;
378 block += align_eight (sizeof (allocation_pool_list));
379
380 /* Throw it on the block list. */
381 block_header->next = m_block_list;
382 m_block_list = block_header;
383
384 /* Make the block available for allocation. */
385 m_virgin_free_list = block;
386 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 m_elts_allocated += m_elts_per_block;
391 m_elts_free += m_elts_per_block;
392 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 block = m_virgin_free_list;
398 header = (allocation_pool_list*) allocation_object::get_data (block);
399 header->next = NULL;
400
401 /* Mark the element to be free. */
402#if CHECKING_P
403 ((allocation_object*) block)->id = 0;
404#endif
405 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size));
406 m_returned_free_list = header;
407 m_virgin_free_list += m_elt_size;
408 m_virgin_elts_remaining--;
409
410 }
411
412 /* Pull the first free element from the free list, and return it. */
413 header = m_returned_free_list;
414 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof (*header)));
415 m_returned_free_list = header->next;
416 m_elts_free--;
417
418 /* Set the ID for element. */
419#if CHECKING_P
420 allocation_object::get_instance (header)->id = m_id;
421#endif
422 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size));
423
424 return (void *)(header);
425}
426
427/* Puts PTR back on POOL's free list. */
428template <typename TBlockAllocator>
429inline void
431{
432 int size = m_elt_size - offsetof (allocation_object, u.data);
433
434 if (flag_checking)
435 {
436 gcc_assert (m_initialized);
437 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 gcc_assert (m_id == allocation_object::get_instance (object)->id);
443#endif
444
445 memset (object, 0xaf, size);
446 }
447
448#if CHECKING_P
449 /* Mark the element to be free. */
450 allocation_object::get_instance (object)->id = 0;
451#endif
452
453 allocation_pool_list *header = new (object) allocation_pool_list;
454 header->next = m_returned_free_list;
455 m_returned_free_list = header;
456 VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (object, size));
457 m_elts_free++;
458
459 if (GATHER_STATISTICS)
460 {
461 pool_allocator_usage.release_instance_overhead (this, m_elt_size);
462 }
463}
464
465/* Number of elements currently active (not returned to pool). Used for cheap
466 consistency checks. */
467template <typename TBlockAllocator>
468inline size_t
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). */
477typedef base_pool_allocator <memory_block_pool> pool_allocator;
478
479/* Type based memory pool allocator. */
480template <typename T>
482{
483public:
484 /* Default constructor for pool allocator called NAME. */
486 m_allocator (name, sizeof (T) PASS_MEM_STAT) {}
487
488 inline void
490 {
492 }
493
494 inline void release_if_empty ()
495 {
497 }
498
499
500 /* Allocate memory for instance of type T and call a default constructor. */
501
502 inline T *
503 allocate () ATTRIBUTE_MALLOC
504 {
505 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 allocate_raw () ATTRIBUTE_MALLOC
514 {
515 return m_allocator.allocate ();
516 }
517
518 inline void
519 remove (T *object)
520 {
521 /* Call destructor. */
522 object->~T ();
523
524 m_allocator.remove (object);
525 }
526
527 inline void
528 remove_raw (void *object)
529 {
530 m_allocator.remove (object);
531 }
532
533 inline size_t
535 {
537 }
538
539private:
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. */
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. */
561};
562
563/* Helper for classes that do not provide default ctor. */
564
565template <typename T>
566inline void *
567operator new (size_t, object_allocator<T> &a)
568{
569 return a.allocate_raw ();
570}
571
572/* Hashtable mapping alloc_pool names to descriptors. */
574
575
576#endif
mem_alloc_description< pool_usage > pool_allocator_usage
Definition alloc-pool.cc:27
ALLOC_POOL_ID_TYPE last_id
Definition alloc-pool.cc:26
base_pool_allocator< memory_block_pool > pool_allocator
Definition alloc-pool.h:477
hash_map< const char *, alloc_pool_descriptor > * alloc_pool_hash
void dump_alloc_pool_statistics(void)
Definition alloc-pool.cc:32
bool after_memory_report
Definition alloc-pool.cc:28
unsigned long ALLOC_POOL_ID_TYPE
Definition alloc-pool.h:31
Definition alloc-pool.h:142
size_t m_elts_free
Definition alloc-pool.h:224
const char * m_name
Definition alloc-pool.h:206
~base_pool_allocator()
Definition alloc-pool.h:340
char * m_virgin_free_list
Definition alloc-pool.h:216
void release_if_empty()
Definition alloc-pool.h:333
size_t m_virgin_elts_remaining
Definition alloc-pool.h:220
ALLOC_POOL_ID_TYPE m_id
Definition alloc-pool.h:207
allocation_pool_list * m_block_list
Definition alloc-pool.h:228
allocation_pool_list * m_returned_free_list
Definition alloc-pool.h:212
void initialize()
Definition alloc-pool.h:253
size_t m_size
Definition alloc-pool.h:232
base_pool_allocator(const char *name, size_t size CXX_MEM_STAT_INFO)
Definition alloc-pool.h:241
size_t m_elts_per_block
Definition alloc-pool.h:208
size_t num_elts_current()
Definition alloc-pool.h:469
size_t m_blocks_allocated
Definition alloc-pool.h:226
void remove(void *object)
Definition alloc-pool.h:430
static size_t align_eight(size_t x)
Definition alloc-pool.h:201
size_t m_elt_size
Definition alloc-pool.h:230
size_t m_elts_allocated
Definition alloc-pool.h:222
void release()
Definition alloc-pool.h:302
mem_location m_location
Definition alloc-pool.h:236
void * allocate() ATTRIBUTE_MALLOC
Definition alloc-pool.h:348
bool m_initialized
Definition alloc-pool.h:234
Definition genoutput.cc:147
Definition hash-map.h:40
Definition mem-stats.h:278
Definition mem-stats.h:35
char * to_string()
Definition mem-stats.h:93
Definition mem-stats.h:128
size_t m_allocated
Definition mem-stats.h:253
size_t m_peak
Definition mem-stats.h:257
size_t m_instances
Definition mem-stats.h:259
size_t m_times
Definition mem-stats.h:255
static float get_percent(size_t nominator, size_t denominator)
Definition mem-stats.h:230
Definition alloc-pool.h:482
pool_allocator m_allocator
Definition alloc-pool.h:540
void * allocate_raw() ATTRIBUTE_MALLOC
Definition alloc-pool.h:513
void remove_raw(void *object)
Definition alloc-pool.h:528
void remove(T *object)
Definition alloc-pool.h:519
object_allocator(const char *name CXX_MEM_STAT_INFO)
Definition alloc-pool.h:485
void release()
Definition alloc-pool.h:489
void release_if_empty()
Definition alloc-pool.h:494
size_t num_elts_current()
Definition alloc-pool.h:534
T * allocate() ATTRIBUTE_MALLOC
Definition alloc-pool.h:503
Definition alloc-pool.h:38
const char * m_pool_name
Definition alloc-pool.h:100
pool_usage()
Definition alloc-pool.h:41
pool_usage operator+(const pool_usage &second)
Definition alloc-pool.h:52
void dump(mem_location *loc, const mem_usage &total) const
Definition alloc-pool.h:63
pool_usage(size_t allocated, size_t times, size_t peak, size_t instances, size_t element_size, const char *pool_name)
Definition alloc-pool.h:43
size_t m_element_size
Definition alloc-pool.h:98
static void dump_header(const char *name)
Definition alloc-pool.h:83
void dump_footer()
Definition alloc-pool.h:91
static struct token T
Definition gengtype-parse.cc:45
free(str)
#define PRIu64
Definition hwint.h:93
@ ALLOC_POOL_ORIGIN
Definition mem-stats-traits.h:33
Ca & a
Definition poly-int.h:766
#define PASS_MEM_STAT
Definition statistics.h:54
#define MEM_STAT_DECL
Definition statistics.h:52
#define CXX_MEM_STAT_INFO
Definition statistics.h:58
Definition alloc-pool.h:550
unsigned long current
Definition alloc-pool.h:556
unsigned long allocated
Definition alloc-pool.h:554
int elt_size
Definition alloc-pool.h:560
unsigned long created
Definition alloc-pool.h:552
unsigned long peak
Definition alloc-pool.h:558
Definition alloc-pool.h:163
static void * get_data(void *instance_ptr)
Definition alloc-pool.h:193
union base_pool_allocator::allocation_object::@1 u
int64_t align_i
Definition alloc-pool.h:179
char data[1]
Definition alloc-pool.h:172
char * align_p
Definition alloc-pool.h:178
allocation_pool_list * next
Definition alloc-pool.h:156
Definition collect2.cc:168
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:821
#define offsetof(TYPE, MEMBER)
Definition system.h:741
#define false
Definition system.h:895
#define VALGRIND_DISCARD(x)
Definition system.h:1222
#define SIZE_AMOUNT(size)
Definition system.h:1290
#define PRsa(n)
Definition system.h:1294
#define gcc_checking_assert(EXPR)
Definition system.h:828