gcc/alloc-pool.h

   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.  */
  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     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 (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
 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
 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 *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
 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
 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