gcc/alloc-pool.h

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