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