1/* Functions to support a pool of allocatable objects.
2   Copyright (C) 1987-2015 Free Software Foundation, Inc.
3   Contributed by Daniel Berlin <dan@cgsoftware.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "alloc-pool.h"
25#include "hash-table.h"
26#include "hash-map.h"
27
28#define align_eight(x) (((x+7) >> 3) << 3)
29
30/* The internal allocation object.  */
31typedef struct allocation_object_def
32{
33#ifdef ENABLE_CHECKING
34  /* The ID of alloc pool which the object was allocated from.  */
35  ALLOC_POOL_ID_TYPE id;
36#endif
37
38  union
39    {
40      /* The data of the object.  */
41      char data[1];
42
43      /* Because we want any type of data to be well aligned after the ID,
44	 the following elements are here.  They are never accessed so
45	 the allocated object may be even smaller than this structure.
46	 We do not care about alignment for floating-point types.  */
47      char *align_p;
48      int64_t align_i;
49    } u;
50} allocation_object;
51
52/* Convert a pointer to allocation_object from a pointer to user data.  */
53#define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X)				\
54   ((allocation_object *) (((char *) (X))				\
55			   - offsetof (allocation_object, u.data)))
56
57/* Convert a pointer to user data from a pointer to allocation_object.  */
58#define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X)				\
59   ((void *) (((allocation_object *) (X))->u.data))
60
61#ifdef ENABLE_CHECKING
62/* Last used ID.  */
63static ALLOC_POOL_ID_TYPE last_id;
64#endif
65
66/* Store information about each particular alloc_pool.  Note that this
67   will underestimate the amount the amount of storage used by a small amount:
68   1) The overhead in a pool is not accounted for.
69   2) The unallocated elements in a block are not accounted for.  Note
70   that this can at worst case be one element smaller that the block
71   size for that pool.  */
72struct alloc_pool_descriptor
73{
74  /* Number of pools allocated.  */
75  unsigned long created;
76  /* Gross allocated storage.  */
77  unsigned long allocated;
78  /* Amount of currently active storage. */
79  unsigned long current;
80  /* Peak amount of storage used.  */
81  unsigned long peak;
82  /* Size of element in the pool.  */
83  int elt_size;
84};
85
86/* Hashtable mapping alloc_pool names to descriptors.  */
87static hash_map<const char *, alloc_pool_descriptor> *alloc_pool_hash;
88
89/* For given name, return descriptor, create new if needed.  */
90static struct alloc_pool_descriptor *
91allocate_pool_descriptor (const char *name)
92{
93  if (!alloc_pool_hash)
94    alloc_pool_hash = new hash_map<const char *, alloc_pool_descriptor> (10);
95
96  return &alloc_pool_hash->get_or_insert (name);
97}
98
99/* Create a pool of things of size SIZE, with NUM in each block we
100   allocate.  */
101
102alloc_pool
103create_alloc_pool (const char *name, size_t size, size_t num)
104{
105  alloc_pool pool;
106  size_t header_size;
107
108  gcc_checking_assert (name);
109
110  /* Make size large enough to store the list header.  */
111  if (size < sizeof (alloc_pool_list))
112    size = sizeof (alloc_pool_list);
113
114  /* Now align the size to a multiple of 4.  */
115  size = align_eight (size);
116
117#ifdef ENABLE_CHECKING
118  /* Add the aligned size of ID.  */
119  size += offsetof (allocation_object, u.data);
120#endif
121
122  /* Um, we can't really allocate 0 elements per block.  */
123  gcc_checking_assert (num);
124
125  /* Allocate memory for the pool structure.  */
126  pool = XNEW (struct alloc_pool_def);
127
128  /* Now init the various pieces of our pool structure.  */
129  pool->name = /*xstrdup (name)*/name;
130  pool->elt_size = size;
131  pool->elts_per_block = num;
132
133  if (GATHER_STATISTICS)
134    {
135      struct alloc_pool_descriptor *desc = allocate_pool_descriptor (name);
136      desc->elt_size = size;
137      desc->created++;
138    }
139
140  /* List header size should be a multiple of 8.  */
141  header_size = align_eight (sizeof (struct alloc_pool_list_def));
142
143  pool->block_size = (size * num) + header_size;
144  pool->returned_free_list = NULL;
145  pool->virgin_free_list = NULL;
146  pool->virgin_elts_remaining = 0;
147  pool->elts_allocated = 0;
148  pool->elts_free = 0;
149  pool->blocks_allocated = 0;
150  pool->block_list = NULL;
151
152#ifdef ENABLE_CHECKING
153  /* Increase the last used ID and use it for this pool.
154     ID == 0 is used for free elements of pool so skip it.  */
155  last_id++;
156  if (last_id == 0)
157    last_id++;
158
159  pool->id = last_id;
160#endif
161
162  return (pool);
163}
164
165/* Free all memory allocated for the given memory pool.  */
166void
167empty_alloc_pool (alloc_pool pool)
168{
169  alloc_pool_list block, next_block;
170
171  gcc_checking_assert (pool);
172
173  /* Free each block allocated to the pool.  */
174  for (block = pool->block_list; block != NULL; block = next_block)
175    {
176      next_block = block->next;
177      free (block);
178    }
179
180  if (GATHER_STATISTICS)
181    {
182      struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
183      desc->current -= (pool->elts_allocated - pool->elts_free) * pool->elt_size;
184    }
185
186  pool->returned_free_list = NULL;
187  pool->virgin_free_list = NULL;
188  pool->virgin_elts_remaining = 0;
189  pool->elts_allocated = 0;
190  pool->elts_free = 0;
191  pool->blocks_allocated = 0;
192  pool->block_list = NULL;
193}
194
195/* Free all memory allocated for the given memory pool and the pool itself.  */
196void
197free_alloc_pool (alloc_pool pool)
198{
199  /* First empty the pool.  */
200  empty_alloc_pool (pool);
201#ifdef ENABLE_CHECKING
202  memset (pool, 0xaf, sizeof (*pool));
203#endif
204  /* Lastly, free the pool.  */
205  free (pool);
206}
207
208/* Frees the alloc_pool, if it is empty and zero *POOL in this case.  */
209void
210free_alloc_pool_if_empty (alloc_pool *pool)
211{
212  if ((*pool)->elts_free == (*pool)->elts_allocated)
213    {
214      free_alloc_pool (*pool);
215      *pool = NULL;
216    }
217}
218
219/* Allocates one element from the pool specified.  */
220void *
221pool_alloc (alloc_pool pool)
222{
223  alloc_pool_list header;
224#ifdef ENABLE_VALGRIND_ANNOTATIONS
225  int size;
226#endif
227
228  if (GATHER_STATISTICS)
229    {
230      struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
231
232      desc->allocated += pool->elt_size;
233      desc->current += pool->elt_size;
234      if (desc->peak < desc->current)
235	desc->peak = desc->current;
236    }
237
238  gcc_checking_assert (pool);
239#ifdef ENABLE_VALGRIND_ANNOTATIONS
240  size = pool->elt_size - offsetof (allocation_object, u.data);
241#endif
242
243  /* If there are no more free elements, make some more!.  */
244  if (!pool->returned_free_list)
245    {
246      char *block;
247      if (!pool->virgin_elts_remaining)
248	{
249	  alloc_pool_list block_header;
250
251	  /* Make the block.  */
252	  block = XNEWVEC (char, pool->block_size);
253	  block_header = (alloc_pool_list) block;
254	  block += align_eight (sizeof (struct alloc_pool_list_def));
255
256	  /* Throw it on the block list.  */
257	  block_header->next = pool->block_list;
258	  pool->block_list = block_header;
259
260	  /* Make the block available for allocation.  */
261	  pool->virgin_free_list = block;
262	  pool->virgin_elts_remaining = pool->elts_per_block;
263
264	  /* Also update the number of elements we have free/allocated, and
265	     increment the allocated block count.  */
266	  pool->elts_allocated += pool->elts_per_block;
267	  pool->elts_free += pool->elts_per_block;
268	  pool->blocks_allocated += 1;
269	}
270
271
272      /* We now know that we can take the first elt off the virgin list and
273	 put it on the returned list. */
274      block = pool->virgin_free_list;
275      header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
276      header->next = NULL;
277#ifdef ENABLE_CHECKING
278      /* Mark the element to be free.  */
279      ((allocation_object *) block)->id = 0;
280#endif
281      VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (header,size));
282      pool->returned_free_list = header;
283      pool->virgin_free_list += pool->elt_size;
284      pool->virgin_elts_remaining--;
285
286    }
287
288  /* Pull the first free element from the free list, and return it.  */
289  header = pool->returned_free_list;
290  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_DEFINED (header, sizeof (*header)));
291  pool->returned_free_list = header->next;
292  pool->elts_free--;
293
294#ifdef ENABLE_CHECKING
295  /* Set the ID for element.  */
296  ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
297#endif
298  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_UNDEFINED (header, size));
299
300  return ((void *) header);
301}
302
303/* Puts PTR back on POOL's free list.  */
304void
305pool_free (alloc_pool pool, void *ptr)
306{
307  alloc_pool_list header;
308#if defined(ENABLE_VALGRIND_ANNOTATIONS) || defined(ENABLE_CHECKING)
309  int size;
310  size = pool->elt_size - offsetof (allocation_object, u.data);
311#endif
312
313#ifdef ENABLE_CHECKING
314  gcc_assert (ptr
315	      /* Check if we free more than we allocated, which is Bad (TM).  */
316	      && pool->elts_free < pool->elts_allocated
317	      /* Check whether the PTR was allocated from POOL.  */
318	      && pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id);
319
320  memset (ptr, 0xaf, size);
321
322  /* Mark the element to be free.  */
323  ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
324#endif
325
326  header = (alloc_pool_list) ptr;
327  header->next = pool->returned_free_list;
328  pool->returned_free_list = header;
329  VALGRIND_DISCARD (VALGRIND_MAKE_MEM_NOACCESS (ptr, size));
330  pool->elts_free++;
331
332  if (GATHER_STATISTICS)
333    {
334      struct alloc_pool_descriptor *desc = allocate_pool_descriptor (pool->name);
335      desc->current -= pool->elt_size;
336    }
337}
338
339/* Output per-alloc_pool statistics.  */
340
341/* Used to accumulate statistics about alloc_pool sizes.  */
342struct pool_output_info
343{
344  unsigned long total_created;
345  unsigned long total_allocated;
346};
347
348/* Called via hash_map.traverse.  Output alloc_pool descriptor pointed out by
349   SLOT and update statistics.  */
350bool
351print_alloc_pool_statistics (const char *const &name,
352			     const alloc_pool_descriptor &d,
353			     struct pool_output_info *i)
354{
355  if (d.allocated)
356    {
357      fprintf (stderr,
358	       "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n",
359	       name, d.elt_size, d.created, d.allocated,
360	       d.allocated / d.elt_size, d.peak, d.peak / d.elt_size,
361	       d.current, d.current / d.elt_size);
362      i->total_allocated += d.allocated;
363      i->total_created += d.created;
364    }
365  return 1;
366}
367
368/* Output per-alloc_pool memory usage statistics.  */
369void
370dump_alloc_pool_statistics (void)
371{
372  struct pool_output_info info;
373
374  if (! GATHER_STATISTICS)
375    return;
376
377  if (!alloc_pool_hash)
378    return;
379
380  fprintf (stderr, "\nAlloc-pool Kind         Elt size  Pools  Allocated (elts)            Peak (elts)            Leak (elts)\n");
381  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
382  info.total_created = 0;
383  info.total_allocated = 0;
384  alloc_pool_hash->traverse <struct pool_output_info *,
385			     print_alloc_pool_statistics> (&info);
386  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
387  fprintf (stderr, "%-22s           %7lu %10lu\n",
388	   "Total", info.total_created, info.total_allocated);
389  fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n");
390}
391