gcc/alloc-pool.h

   1 /* Functions to support a pool of allocatable objects
   2    Copyright (C) 1997-2018 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 struct pool_usage: public mem_usage
  38 {
  39   /* Default contructor.  */
  40   pool_usage (): m_element_size (0), m_pool_name ("") {}
  41   /* Constructor.  */
  42   pool_usage (size_t allocated, size_t times, size_t peak,
  43               size_t instances, size_t element_size,
  44               const char *pool_name)
  45     : mem_usage (allocated, times, peak, instances),
  46       m_element_size (element_size),
  47       m_pool_name (pool_name) {}
  48
  49   /* Sum the usage with SECOND usage.  */
  50   pool_usage
  51   operator+ (const pool_usage &second)
  52   {
  53     return pool_usage (m_allocated + second.m_allocated,
  54                              m_times + second.m_times,
  55                              m_peak + second.m_peak,
  56                              m_instances + second.m_instances,
  57                              m_element_size, m_pool_name);
  58   }
  59
  60   /* Dump usage coupled to LOC location, where TOTAL is sum of all rows.  */
  61   inline void
  62   dump (mem_location *loc, mem_usage &total) const
  63   {
  64     char *location_string = loc->to_string ();
  65
  66     fprintf (stderr, "%-32s%-48s " PRsa(5) PRsa(9) ":%5.1f%%"
  67              PRsa(9) PRsa(9) ":%5.1f%%%12" PRIu64 "\n",
  68              m_pool_name, location_string,
  69              SIZE_AMOUNT (m_instances),
  70              SIZE_AMOUNT (m_allocated),
  71              get_percent (m_allocated, total.m_allocated),
  72              SIZE_AMOUNT (m_peak),
  73              SIZE_AMOUNT (m_times),
  74              get_percent (m_times, total.m_times),
  75              (uint64_t)m_element_size);
  76
  77     free (location_string);
  78   }
  79
  80   /* Dump header with NAME.  */
  81   static inline void
  82   dump_header (const char *name)
  83   {
  84     fprintf (stderr, "%-32s%-48s %6s%11s%16s%17s%12s\n", "Pool name", name,
  85              "Pools", "Leak", "Peak", "Times", "Elt size");
  86     print_dash_line ();
  87   }
  88
  89   /* Dump footer.  */
  90   inline void
  91   dump_footer ()
  92   {
  93     print_dash_line ();
  94     fprintf (stderr, "%s" PRsa(82) PRsa(10) "\n", "Total",
  95              SIZE_AMOUNT (m_instances), SIZE_AMOUNT (m_allocated));
  96     print_dash_line ();
  97   }
  98
  99   /* Element size.  */
 100   size_t m_element_size;
 101   /* Pool name.  */
 102   const char *m_pool_name;
 103 };
 104
 105 extern mem_alloc_description<pool_usage> pool_allocator_usage;
 106
 107 #if 0
 108 /* If a pool with custom block size is needed, one might use the following
 109    template.  An instance of this template can be used as a parameter for
 110    instantiating base_pool_allocator template:
 111
 112         typedef custom_block_allocator <128*1024> huge_block_allocator;
 113         ...
 114         static base_pool_allocator <huge_block_allocator>
 115                                                 value_pool ("value", 16384);
 116
 117    Right now it's not used anywhere in the code, and is given here as an
 118    example).  */
 119
 120 template <size_t BlockSize>
 121 class custom_block_allocator
 122 {
 123 public:
 124   static const size_t block_size = BlockSize;
 125
 126   static inline void *
 127   allocate () ATTRIBUTE_MALLOC
 128   {
 129     return XNEWVEC (char, BlockSize);
 130   }
 131
 132   static inline void
 133   release (void *block)
 134   {
 135     XDELETEVEC (block);
 136   }
 137 };
 138 #endif
 139
 140 /* Generic pool allocator.  */
 141
 142 template <typename TBlockAllocator>
 143 class base_pool_allocator
 144 {
 145 public:
 146   /* Default constructor for pool allocator called NAME.  */
 147   base_pool_allocator (const char *name, size_t size CXX_MEM_STAT_INFO);
 148   ~base_pool_allocator ();
 149   void release ();
 150   void release_if_empty ();
 151   void *allocate () ATTRIBUTE_MALLOC;
 152   void remove (void *object);
 153   size_t num_elts_current ();
 154
 155 private:
 156   struct allocation_pool_list
 157   {
 158     allocation_pool_list *next;
 159   };
 160
 161   /* Initialize a pool allocator.  */
 162   void initialize ();
 163
 164   struct allocation_object
 165   {
 166 #if CHECKING_P
 167     /* The ID of alloc pool which the object was allocated from.  */
 168     ALLOC_POOL_ID_TYPE id;
 169 #endif
 170
 171     union
 172       {
 173         /* The data of the object.  */
 174         char data[1];
 175
 176         /* Because we want any type of data to be well aligned after the ID,
 177            the following elements are here.  They are never accessed so
 178            the allocated object may be even smaller than this structure.
 179            We do not care about alignment for floating-point types.  */
 180         char *align_p;
 181         int64_t align_i;
 182       } u;
 183
 184 #if CHECKING_P
 185     static inline allocation_object*
 186     get_instance (void *data_ptr)
 187     {
 188       return (allocation_object *)(((char *)(data_ptr))
 189                                       - offsetof (allocation_object,
 190                                                   u.data));
 191     }
 192 #endif
 193
 194     static inline void*
 195     get_data (void *instance_ptr)
 196     {
 197       return (void*)(((allocation_object *) instance_ptr)->u.data);
 198     }
 199   };
 200
 201   /* Align X to 8.  */
 202   static inline size_t
 203   align_eight (size_t x)
 204   {
 205     return (((x+7) >> 3) << 3);
 206   }
 207
 208   const char *m_name;
 209   ALLOC_POOL_ID_TYPE m_id;
 210   size_t m_elts_per_block;
 211
 212   /* These are the elements that have been allocated at least once
 213      and freed.  */
 214   allocation_pool_list *m_returned_free_list;
 215
 216   /* These are the elements that have not yet been allocated out of
 217      the last block obtained from XNEWVEC.  */
 218   char* m_virgin_free_list;
 219
 220   /* The number of elements in the virgin_free_list that can be
 221      allocated before needing another block.  */
 222   size_t m_virgin_elts_remaining;
 223   /* The number of elements that are allocated.  */
 224   size_t m_elts_allocated;
 225   /* The number of elements that are released.  */
 226   size_t m_elts_free;
 227   /* The number of allocated blocks.  */
 228   size_t m_blocks_allocated;
 229   /* List of blocks that are used to allocate new objects.  */
 230   allocation_pool_list *m_block_list;
 231   /* Size of a pool elements in bytes.  */
 232   size_t m_elt_size;
 233   /* Size in bytes that should be allocated for each element.  */
 234   size_t m_size;
 235   /* Flag if a pool allocator is initialized.  */
 236   bool m_initialized;
 237   /* Memory allocation location.  */
 238   mem_location m_location;
 239 };
 240
 241 template <typename TBlockAllocator>
 242 inline
 243 base_pool_allocator <TBlockAllocator>::base_pool_allocator (
 244                                 const char *name, size_t size MEM_STAT_DECL):
 245   m_name (name), m_id (0), m_elts_per_block (0), m_returned_free_list (NULL),
 246   m_virgin_free_list (NULL), m_virgin_elts_remaining (0), m_elts_allocated (0),
 247   m_elts_free (0), m_blocks_allocated (0), m_block_list (NULL), m_elt_size (0),
 248   m_size (size), m_initialized (false),
 249   m_location (ALLOC_POOL_ORIGIN, false PASS_MEM_STAT) {}
 250
 251 /* Initialize a pool allocator.  */
 252
 253 template <typename TBlockAllocator>
 254 inline void
 255 base_pool_allocator <TBlockAllocator>::initialize ()
 256 {
 257   gcc_checking_assert (!m_initialized);
 258   m_initialized = true;
 259
 260   size_t size = m_size;
 261
 262   gcc_checking_assert (m_name);
 263   gcc_checking_assert (m_size);
 264
 265   /* Make size large enough to store the list header.  */
 266   if (size < sizeof (allocation_pool_list*))
 267     size = sizeof (allocation_pool_list*);
 268
 269   /* Now align the size to a multiple of 8.  */
 270   size = align_eight (size);
 271
 272   /* Add the aligned size of ID.  */
 273   size += offsetof (allocation_object, u.data);
 274
 275   m_elt_size = size;
 276
 277   if (GATHER_STATISTICS)
 278     {
 279       pool_usage *u = pool_allocator_usage.register_descriptor
 280         (this, new mem_location (m_location));
 281
 282       u->m_element_size = m_elt_size;
 283       u->m_pool_name = m_name;
 284     }
 285
 286   /* List header size should be a multiple of 8.  */
 287   size_t header_size = align_eight (sizeof (allocation_pool_list));
 288
 289   m_elts_per_block = (TBlockAllocator::block_size - header_size) / size;
 290   gcc_checking_assert (m_elts_per_block != 0);
 291
 292   /* Increase the last used ID and use it for this pool.
 293      ID == 0 is used for free elements of pool so skip it.  */
 294   last_id++;
 295   if (last_id == 0)
 296     last_id++;
 297
 298   m_id = last_id;
 299 }
 300
 301 /* Free all memory allocated for the given memory pool.  */
 302 template <typename TBlockAllocator>
 303 inline void
 304 base_pool_allocator <TBlockAllocator>::release ()
 305 {
 306   if (!m_initialized)
 307     return;
 308
 309   allocation_pool_list *block, *next_block;
 310
 311   /* Free each block allocated to the pool.  */
 312   for (block = m_block_list; block != NULL; block = next_block)
 313     {
 314       next_block = block->next;
 315       TBlockAllocator::release (block);
 316     }
 317
 318   if (GATHER_STATISTICS && !after_memory_report)
 319     {
 320       pool_allocator_usage.release_instance_overhead
 321         (this, (m_elts_allocated - m_elts_free) * m_elt_size);
 322     }
 323
 324   m_returned_free_list = NULL;
 325   m_virgin_free_list = NULL;
 326   m_virgin_elts_remaining = 0;
 327   m_elts_allocated = 0;
 328   m_elts_free = 0;
 329   m_blocks_allocated = 0;
 330   m_block_list = NULL;
 331 }
 332
 333 template <typename TBlockAllocator>
 334 inline void
 335 base_pool_allocator <TBlockAllocator>::release_if_empty ()
 336 {
 337   if (m_elts_free == m_elts_allocated)
 338     release ();
 339 }
 340
 341 template <typename TBlockAllocator>
 342 inline base_pool_allocator <TBlockAllocator>::~base_pool_allocator ()
 343 {
 344   release ();
 345 }
 346
 347 /* Allocates one element from the pool specified.  */
 348 template <typename TBlockAllocator>
 349 inline void*
 350 base_pool_allocator <TBlockAllocator>::allocate ()
 351 {
 352   if (!m_initialized)
 353     initialize ();
 354
 355   allocation_pool_list *header;
 356 #ifdef ENABLE_VALGRIND_ANNOTATIONS
 357   int size;
 358 #endif
 359
 360   if (GATHER_STATISTICS)
 361     {
 362       pool_allocator_usage.register_instance_overhead (m_elt_size, this);
 363     }
 364
 365 #ifdef ENABLE_VALGRIND_ANNOTATIONS
 366   size = m_elt_size - offsetof (allocation_object, u.data);
 367 #endif
 368
 369   /* If there are no more free elements, make some more!.  */
 370   if (!m_returned_free_list)
 371     {
 372       char *block;
 373       if (!m_virgin_elts_remaining)
 374         {
 375           allocation_pool_list *block_header;
 376
 377           /* Make the block.  */
 378           block = reinterpret_cast<char *> (TBlockAllocator::allocate ());
 379           block_header = new (block) allocation_pool_list;
 380           block += align_eight (sizeof (allocation_pool_list));
 381
 382           /* Throw it on the block list.  */
 383           block_header->next = m_block_list;
 384           m_block_list = block_header;
 385
 386           /* Make the block available for allocation.  */
 387           m_virgin_free_list = block;
 388           m_virgin_elts_remaining = m_elts_per_block;
 389
 390           /* Also update the number of elements we have free/allocated, and
 391              increment the allocated block count.  */
 392           m_elts_allocated += m_elts_per_block;
 393           m_elts_free += m_elts_per_block;
 394           m_blocks_allocated += 1;
 395         }
 396
 397       /* We now know that we can take the first elt off the virgin list and
 398          put it on the returned list.  */
 399       block = m_virgin_free_list;
 400       header = (allocation_pool_list*) allocation_object::get_data (block);
 401       header->next = NULL;
 402
 403       /* Mark the element to be free.  */
 404 #if CHECKING_P
 405       ((allocation_object*) block)->id = 0;
 406 #endif
 407       VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size));
 408       m_returned_free_list = header;
 409       m_virgin_free_list += m_elt_size;
 410       m_virgin_elts_remaining--;
 411
 412     }
 413
 414   /* Pull the first free element from the free list, and return it.  */
 415   header = m_returned_free_list;
 416   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof (*header)));
 417   m_returned_free_list = header->next;
 418   m_elts_free--;
 419
 420   /* Set the ID for element.  */
 421 #if CHECKING_P
 422   allocation_object::get_instance (header)->id = m_id;
 423 #endif
 424   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size));
 425
 426   return (void *)(header);
 427 }
 428
 429 /* Puts PTR back on POOL's free list.  */
 430 template <typename TBlockAllocator>
 431 inline void
 432 base_pool_allocator <TBlockAllocator>::remove (void *object)
 433 {
 434   int size = m_elt_size - offsetof (allocation_object, u.data);
 435
 436   if (flag_checking)
 437     {
 438       gcc_assert (m_initialized);
 439       gcc_assert (object
 440                   /* Check if we free more than we allocated.  */
 441                   && m_elts_free < m_elts_allocated);
 442 #if CHECKING_P
 443       /* Check whether the PTR was allocated from POOL.  */
 444       gcc_assert (m_id == allocation_object::get_instance (object)->id);
 445 #endif
 446
 447       memset (object, 0xaf, size);
 448     }
 449
 450 #if CHECKING_P
 451   /* Mark the element to be free.  */
 452   allocation_object::get_instance (object)->id = 0;
 453 #endif
 454
 455   allocation_pool_list *header = new (object) allocation_pool_list;
 456   header->next = m_returned_free_list;
 457   m_returned_free_list = header;
 458   VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (object, size));
 459   m_elts_free++;
 460
 461   if (GATHER_STATISTICS)
 462     {
 463       pool_allocator_usage.release_instance_overhead (this, m_elt_size);
 464     }
 465 }
 466
 467 /* Number of elements currently active (not returned to pool).  Used for cheap
 468    consistency checks.  */
 469 template <typename TBlockAllocator>
 470 inline size_t
 471 base_pool_allocator <TBlockAllocator>::num_elts_current ()
 472 {
 473   return m_elts_allocated - m_elts_free;
 474 }
 475
 476 /* Specialization of base_pool_allocator which should be used in most cases.
 477    Another specialization may be needed, if object size is greater than
 478    memory_block_pool::block_size (64 KB).  */
 479 typedef base_pool_allocator <memory_block_pool> pool_allocator;
 480
 481 /* Type based memory pool allocator.  */
 482 template <typename T>
 483 class object_allocator
 484 {
 485 public:
 486   /* Default constructor for pool allocator called NAME.  */
 487   object_allocator (const char *name CXX_MEM_STAT_INFO):
 488     m_allocator (name, sizeof (T) PASS_MEM_STAT) {}
 489
 490   inline void
 491   release ()
 492   {
 493     m_allocator.release ();
 494   }
 495
 496   inline void release_if_empty ()
 497   {
 498     m_allocator.release_if_empty ();
 499   }
 500
 501
 502   /* Allocate memory for instance of type T and call a default constructor.  */
 503
 504   inline T *
 505   allocate () ATTRIBUTE_MALLOC
 506   {
 507     return ::new (m_allocator.allocate ()) T;
 508   }
 509
 510   /* Allocate memory for instance of type T and return void * that
 511      could be used in situations where a default constructor is not provided
 512      by the class T.  */
 513
 514   inline void *
 515   allocate_raw () ATTRIBUTE_MALLOC
 516   {
 517     return m_allocator.allocate ();
 518   }
 519
 520   inline void
 521   remove (T *object)
 522   {
 523     /* Call destructor.  */
 524     object->~T ();
 525
 526     m_allocator.remove (object);
 527   }
 528
 529   inline size_t
 530   num_elts_current ()
 531   {
 532     return m_allocator.num_elts_current ();
 533   }
 534
 535 private:
 536   pool_allocator m_allocator;
 537 };
 538
 539 /* Store information about each particular alloc_pool.  Note that this
 540    will underestimate the amount the amount of storage used by a small amount:
 541    1) The overhead in a pool is not accounted for.
 542    2) The unallocated elements in a block are not accounted for.  Note
 543    that this can at worst case be one element smaller that the block
 544    size for that pool.  */
 545 struct alloc_pool_descriptor
 546 {
 547   /* Number of pools allocated.  */
 548   unsigned long created;
 549   /* Gross allocated storage.  */
 550   unsigned long allocated;
 551   /* Amount of currently active storage.  */
 552   unsigned long current;
 553   /* Peak amount of storage used.  */
 554   unsigned long peak;
 555   /* Size of element in the pool.  */
 556   int elt_size;
 557 };
 558
 559 /* Helper for classes that do not provide default ctor.  */
 560
 561 template <typename T>
 562 inline void *
 563 operator new (size_t, object_allocator<T> &a)
 564 {
 565   return a.allocate_raw ();
 566 }
 567
 568 /* Hashtable mapping alloc_pool names to descriptors.  */
 569 extern hash_map<const char *, alloc_pool_descriptor> *alloc_pool_hash;
 570
 571
 572 #endif