1 | /* Functions to support a pool of allocatable objects |
2 | Copyright (C) 1997-2023 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, format: "%-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 (nominator: m_allocated, denominator: total.m_allocated), |
73 | SIZE_AMOUNT (m_peak), |
74 | SIZE_AMOUNT (m_times), |
75 | get_percent (nominator: m_times, denominator: total.m_times), |
76 | (uint64_t)m_element_size); |
77 | |
78 | free (ptr: location_string); |
79 | } |
80 | |
81 | /* Dump header with NAME. */ |
82 | static inline void |
83 | (const char *name) |
84 | { |
85 | fprintf (stderr, format: "%-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 | () |
92 | { |
93 | fprintf (stderr, format: "%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 | 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; |
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 | base_pool_allocator <TBlockAllocator>::base_pool_allocator ( |
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 | |
251 | template <typename TBlockAllocator> |
252 | inline void |
253 | base_pool_allocator <TBlockAllocator>::initialize () |
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 (x: 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 = align_eight (x: 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. */ |
300 | template <typename TBlockAllocator> |
301 | inline void |
302 | base_pool_allocator <TBlockAllocator>::release () |
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 | (ptr: this, size: (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 | |
331 | template <typename TBlockAllocator> |
332 | inline void |
333 | base_pool_allocator <TBlockAllocator>::release_if_empty () |
334 | { |
335 | if (m_elts_free == m_elts_allocated) |
336 | release (); |
337 | } |
338 | |
339 | template <typename TBlockAllocator> |
340 | inline base_pool_allocator <TBlockAllocator>::~base_pool_allocator () |
341 | { |
342 | release (); |
343 | } |
344 | |
345 | /* Allocates one element from the pool specified. */ |
346 | template <typename TBlockAllocator> |
347 | inline void* |
348 | base_pool_allocator <TBlockAllocator>::allocate () |
349 | { |
350 | if (!m_initialized) |
351 | initialize (); |
352 | |
353 | allocation_pool_list *; |
354 | #ifdef ENABLE_VALGRIND_ANNOTATIONS |
355 | int size; |
356 | #endif |
357 | |
358 | if (GATHER_STATISTICS) |
359 | { |
360 | pool_allocator_usage.register_instance_overhead (size: m_elt_size, ptr: 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 *; |
374 | |
375 | /* Make the block. */ |
376 | block = reinterpret_cast<char *> (TBlockAllocator::allocate ()); |
377 | block_header = new (block) allocation_pool_list; |
378 | block += align_eight (x: 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. */ |
428 | template <typename TBlockAllocator> |
429 | inline void |
430 | base_pool_allocator <TBlockAllocator>::remove (void *object) |
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 (s: object, c: 0xaf, n: 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 * = 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 (ptr: this, size: m_elt_size); |
462 | } |
463 | } |
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 | class object_allocator |
482 | { |
483 | public: |
484 | /* Default constructor for pool allocator called NAME. */ |
485 | object_allocator (const char *name CXX_MEM_STAT_INFO): |
486 | m_allocator (name, sizeof (T) PASS_MEM_STAT) {} |
487 | |
488 | inline void |
489 | release () |
490 | { |
491 | m_allocator.release (); |
492 | } |
493 | |
494 | inline void release_if_empty () |
495 | { |
496 | 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 | 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 |
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 | operator new (size_t, object_allocator<T> &a) |
568 | { |
569 | 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 |
577 | |