1 /* Functions to support a pool of allocatable objects
2 Copyright (C) 1997-2021 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. */
pool_usage()41 pool_usage (): m_element_size (0), m_pool_name ("") {}
42 /* Constructor. */
pool_usage(size_t allocated,size_t times,size_t peak,size_t instances,size_t element_size,const char * pool_name)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
dump(mem_location * loc,const mem_usage & total)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
dump_header(const char * name)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
dump_footer()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*
get_instanceallocation_object184 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*
get_dataallocation_object193 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
align_eight(size_t x)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
base_pool_allocator(const char * name,size_t size MEM_STAT_DECL)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
initialize()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 (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. */
300 template <typename TBlockAllocator>
301 inline void
release()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 (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
331 template <typename TBlockAllocator>
332 inline void
release_if_empty()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>
~base_pool_allocator()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*
allocate()348 base_pool_allocator <TBlockAllocator>::allocate ()
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. */
428 template <typename TBlockAllocator>
429 inline void
remove(void * object)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 (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. */
467 template <typename TBlockAllocator>
468 inline size_t
num_elts_current()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. */
object_allocator(const char * name CXX_MEM_STAT_INFO)485 object_allocator (const char *name CXX_MEM_STAT_INFO):
486 m_allocator (name, sizeof (T) PASS_MEM_STAT) {}
487
488 inline void
release()489 release ()
490 {
491 m_allocator.release ();
492 }
493
release_if_empty()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 *
allocate()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 *
allocate_raw()513 allocate_raw () ATTRIBUTE_MALLOC
514 {
515 return m_allocator.allocate ();
516 }
517
518 inline void
remove(T * object)519 remove (T *object)
520 {
521 /* Call destructor. */
522 object->~T ();
523
524 m_allocator.remove (object);
525 }
526
527 inline void
remove_raw(void * object)528 remove_raw (void *object)
529 {
530 m_allocator.remove (object);
531 }
532
533 inline size_t
num_elts_current()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 *
new(size_t,object_allocator<T> & a)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