Daily bump.
[official-gcc.git] / gcc / alloc-pool.h
blob1cdcc7fc3ba7c10a77ea61975300c7102c29f717
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>
5 This file is part of GCC.
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.
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.
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
23 #include "memory-block.h"
24 #include "options.h" // for flag_checking
26 extern void dump_alloc_pool_statistics (void);
28 /* Flag indicates whether memory statistics are gathered any longer. */
29 extern bool after_memory_report;
31 typedef unsigned long ALLOC_POOL_ID_TYPE;
33 /* Last used ID. */
34 extern ALLOC_POOL_ID_TYPE last_id;
36 /* Pool allocator memory usage. */
37 class pool_usage: public mem_usage
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) {}
50 /* Sum the usage with SECOND usage. */
51 pool_usage
52 operator+ (const pool_usage &second)
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);
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
65 char *location_string = loc->to_string ();
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);
78 free (location_string);
81 /* Dump header with NAME. */
82 static inline void
83 dump_header (const char *name)
85 fprintf (stderr, "%-32s%-48s %6s%11s%16s%17s%12s\n", "Pool name", name,
86 "Pools", "Leak", "Peak", "Times", "Elt size");
89 /* Dump footer. */
90 inline void
91 dump_footer ()
93 fprintf (stderr, "%s" PRsa(82) PRsa(10) "\n", "Total",
94 SIZE_AMOUNT (m_instances), SIZE_AMOUNT (m_allocated));
97 /* Element size. */
98 size_t m_element_size;
99 /* Pool name. */
100 const char *m_pool_name;
103 extern mem_alloc_description<pool_usage> pool_allocator_usage;
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:
110 typedef custom_block_allocator <128*1024> huge_block_allocator;
112 static base_pool_allocator <huge_block_allocator>
113 value_pool ("value", 16384);
115 Right now it's not used anywhere in the code, and is given here as an
116 example). */
118 template <size_t BlockSize>
119 class custom_block_allocator
121 public:
122 static const size_t block_size = BlockSize;
124 static inline void *
125 allocate () ATTRIBUTE_MALLOC
127 return XNEWVEC (char, BlockSize);
130 static inline void
131 release (void *block)
133 XDELETEVEC (block);
136 #endif
138 /* Generic pool allocator. */
140 template <typename TBlockAllocator>
141 class base_pool_allocator
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 ();
153 private:
154 struct allocation_pool_list
156 allocation_pool_list *next;
159 /* Initialize a pool allocator. */
160 void initialize ();
162 struct allocation_object
164 #if CHECKING_P
165 /* The ID of alloc pool which the object was allocated from. */
166 ALLOC_POOL_ID_TYPE id;
167 #endif
169 union
171 /* The data of the object. */
172 char data[1];
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;
182 #if CHECKING_P
183 static inline allocation_object*
184 get_instance (void *data_ptr)
186 return (allocation_object *)(((char *)(data_ptr))
187 - offsetof (allocation_object,
188 u.data));
190 #endif
192 static inline void*
193 get_data (void *instance_ptr)
195 return (void*)(((allocation_object *) instance_ptr)->u.data);
199 /* Align X to 8. */
200 static inline size_t
201 align_eight (size_t x)
203 return (((x+7) >> 3) << 3);
206 const char *m_name;
207 ALLOC_POOL_ID_TYPE m_id;
208 size_t m_elts_per_block;
210 /* These are the elements that have been allocated at least once
211 and freed. */
212 allocation_pool_list *m_returned_free_list;
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;
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;
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) {}
249 /* Initialize a pool allocator. */
251 template <typename TBlockAllocator>
252 inline void
253 base_pool_allocator <TBlockAllocator>::initialize ()
255 gcc_checking_assert (!m_initialized);
256 m_initialized = true;
258 size_t size = m_size;
260 gcc_checking_assert (m_name);
261 gcc_checking_assert (m_size);
263 /* Make size large enough to store the list header. */
264 if (size < sizeof (allocation_pool_list*))
265 size = sizeof (allocation_pool_list*);
267 /* Now align the size to a multiple of 8. */
268 size = align_eight (size);
270 /* Add the aligned size of ID. */
271 size += offsetof (allocation_object, u.data);
273 m_elt_size = size;
275 if (GATHER_STATISTICS)
277 pool_usage *u = pool_allocator_usage.register_descriptor
278 (this, new mem_location (m_location));
280 u->m_element_size = m_elt_size;
281 u->m_pool_name = m_name;
284 /* List header size should be a multiple of 8. */
285 size_t header_size = align_eight (sizeof (allocation_pool_list));
287 m_elts_per_block = (TBlockAllocator::block_size - header_size) / size;
288 gcc_checking_assert (m_elts_per_block != 0);
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++;
296 m_id = last_id;
299 /* Free all memory allocated for the given memory pool. */
300 template <typename TBlockAllocator>
301 inline void
302 base_pool_allocator <TBlockAllocator>::release ()
304 if (!m_initialized)
305 return;
307 allocation_pool_list *block, *next_block;
309 /* Free each block allocated to the pool. */
310 for (block = m_block_list; block != NULL; block = next_block)
312 next_block = block->next;
313 TBlockAllocator::release (block);
316 if (GATHER_STATISTICS && !after_memory_report)
318 pool_allocator_usage.release_instance_overhead
319 (this, (m_elts_allocated - m_elts_free) * m_elt_size);
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;
331 template <typename TBlockAllocator>
332 inline void
333 base_pool_allocator <TBlockAllocator>::release_if_empty ()
335 if (m_elts_free == m_elts_allocated)
336 release ();
339 template <typename TBlockAllocator>
340 inline base_pool_allocator <TBlockAllocator>::~base_pool_allocator ()
342 release ();
345 /* Allocates one element from the pool specified. */
346 template <typename TBlockAllocator>
347 inline void*
348 base_pool_allocator <TBlockAllocator>::allocate ()
350 if (!m_initialized)
351 initialize ();
353 allocation_pool_list *header;
354 #ifdef ENABLE_VALGRIND_ANNOTATIONS
355 int size;
356 #endif
358 if (GATHER_STATISTICS)
360 pool_allocator_usage.register_instance_overhead (m_elt_size, this);
363 #ifdef ENABLE_VALGRIND_ANNOTATIONS
364 size = m_elt_size - offsetof (allocation_object, u.data);
365 #endif
367 /* If there are no more free elements, make some more!. */
368 if (!m_returned_free_list)
370 char *block;
371 if (!m_virgin_elts_remaining)
373 allocation_pool_list *block_header;
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));
380 /* Throw it on the block list. */
381 block_header->next = m_block_list;
382 m_block_list = block_header;
384 /* Make the block available for allocation. */
385 m_virgin_free_list = block;
386 m_virgin_elts_remaining = m_elts_per_block;
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;
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;
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--;
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--;
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));
424 return (void *)(header);
427 /* Puts PTR back on POOL's free list. */
428 template <typename TBlockAllocator>
429 inline void
430 base_pool_allocator <TBlockAllocator>::remove (void *object)
432 int size = m_elt_size - offsetof (allocation_object, u.data);
434 if (flag_checking)
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
445 memset (object, 0xaf, size);
448 #if CHECKING_P
449 /* Mark the element to be free. */
450 allocation_object::get_instance (object)->id = 0;
451 #endif
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++;
459 if (GATHER_STATISTICS)
461 pool_allocator_usage.release_instance_overhead (this, m_elt_size);
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 ()
471 return m_elts_allocated - m_elts_free;
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;
479 /* Type based memory pool allocator. */
480 template <typename T>
481 class object_allocator
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) {}
488 inline void
489 release ()
491 m_allocator.release ();
494 inline void release_if_empty ()
496 m_allocator.release_if_empty ();
500 /* Allocate memory for instance of type T and call a default constructor. */
502 inline T *
503 allocate () ATTRIBUTE_MALLOC
505 return ::new (m_allocator.allocate ()) T;
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. */
512 inline void *
513 allocate_raw () ATTRIBUTE_MALLOC
515 return m_allocator.allocate ();
518 inline void
519 remove (T *object)
521 /* Call destructor. */
522 object->~T ();
524 m_allocator.remove (object);
527 inline void
528 remove_raw (void *object)
530 m_allocator.remove (object);
533 inline size_t
534 num_elts_current ()
536 return m_allocator.num_elts_current ();
539 private:
540 pool_allocator m_allocator;
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
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;
563 /* Helper for classes that do not provide default ctor. */
565 template <typename T>
566 inline void *
567 operator new (size_t, object_allocator<T> &a)
569 return a.allocate_raw ();
572 /* Hashtable mapping alloc_pool names to descriptors. */
573 extern hash_map<const char *, alloc_pool_descriptor> *alloc_pool_hash;
576 #endif