alloc-pool.c revision 132718 
1/* Functions to support a pool of allocatable objects.
2   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004
3   Free Software Foundation, Inc.
4   Contributed by Daniel Berlin <dan@cgsoftware.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 2, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING.  If not, write to the Free
20Software Foundation, 59 Temple Place - Suite 330, Boston, MA
2102111-1307, USA.  */
22
23#include "config.h"
24#include "system.h"
25#include "alloc-pool.h"
26#include "hashtab.h"
27
28/* Redefine abort to report an internal error w/o coredump, and
29   reporting the location of the error in the source file.  This logic
30   is duplicated in rtl.h and tree.h because every file that needs the
31   special abort includes one or both.  toplev.h gets too few files,
32   system.h gets too many.  */
33
34extern void fancy_abort (const char *, int, const char *)
35    ATTRIBUTE_NORETURN;
36#define abort() fancy_abort (__FILE__, __LINE__, __FUNCTION__)
37
38#define align_eight(x) (((x+7) >> 3) << 3)
39
40/* The internal allocation object.  */
41typedef struct allocation_object_def
42{
43#ifdef ENABLE_CHECKING
44  /* The ID of alloc pool which the object was allocated from.  */
45  ALLOC_POOL_ID_TYPE id;
46#endif
47
48  union
49    {
50      /* The data of the object.  */
51      char data[1];
52
53      /* Because we want any type of data to be well aligned after the ID,
54	 the following elements are here.  They are never accessed so
55	 the allocated object may be even smaller than this structure.  */
56      char *align_p;
57      HOST_WIDEST_INT align_i;
58      long double align_ld;
59    } u;
60} allocation_object;
61
62/* Convert a pointer to allocation_object from a pointer to user data.  */
63#define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X)				\
64   ((allocation_object *) (((char *) (X))				\
65			   - offsetof (allocation_object, u.data)))
66
67/* Convert a pointer to user data from a pointer to allocation_object.  */
68#define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X)				\
69   ((void *) (((allocation_object *) (X))->u.data))
70
71#ifdef ENABLE_CHECKING
72/* Last used ID.  */
73static ALLOC_POOL_ID_TYPE last_id;
74#endif
75
76#ifdef GATHER_STATISTICS
77
78/* Store infromation about each particular alloc_pool.  */
79struct alloc_pool_descriptor
80{
81  const char *name;
82  int allocated;
83  int created;
84  int peak;
85  int current;
86};
87
88/* Hashtable mapping alloc_pool names to descriptors.  */
89static htab_t alloc_pool_hash;
90
91/* Hashtable helpers.  */
92static hashval_t
93hash_descriptor (const void *p)
94{
95  const struct alloc_pool_descriptor *d = p;
96  return htab_hash_pointer (d->name);
97}
98static int
99eq_descriptor (const void *p1, const void *p2)
100{
101  const struct alloc_pool_descriptor *d = p1;
102  return d->name == p2;
103}
104
105/* For given name, return descriptor, create new if needed.  */
106static struct alloc_pool_descriptor *
107alloc_pool_descriptor (const char *name)
108{
109  struct alloc_pool_descriptor **slot;
110
111  if (!alloc_pool_hash)
112    alloc_pool_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
113
114  slot = (struct alloc_pool_descriptor **)
115    htab_find_slot_with_hash (alloc_pool_hash, name,
116		    	      htab_hash_pointer (name),
117			      1);
118  if (*slot)
119    return *slot;
120  *slot = xcalloc (sizeof (**slot), 1);
121  (*slot)->name = name;
122  return *slot;
123}
124#endif
125
126/* Create a pool of things of size SIZE, with NUM in each block we
127   allocate.  */
128
129alloc_pool
130create_alloc_pool (const char *name, size_t size, size_t num)
131{
132  alloc_pool pool;
133  size_t pool_size, header_size;
134#ifdef GATHER_STATISTICS
135  struct alloc_pool_descriptor *desc;
136#endif
137
138  if (!name)
139    abort ();
140
141  /* Make size large enough to store the list header.  */
142  if (size < sizeof (alloc_pool_list))
143    size = sizeof (alloc_pool_list);
144
145  /* Now align the size to a multiple of 4.  */
146  size = align_eight (size);
147
148#ifdef ENABLE_CHECKING
149  /* Add the aligned size of ID.  */
150  size += offsetof (allocation_object, u.data);
151#endif
152
153  /* Um, we can't really allocate 0 elements per block.  */
154  if (num == 0)
155    abort ();
156
157  /* Find the size of the pool structure, and the name.  */
158  pool_size = sizeof (struct alloc_pool_def);
159
160  /* and allocate that much memory.  */
161  pool = xmalloc (pool_size);
162
163  /* Now init the various pieces of our pool structure.  */
164  pool->name = /*xstrdup (name)*/name;
165#ifdef GATHER_STATISTICS
166  desc = alloc_pool_descriptor (name);
167  desc->created++;
168#endif
169  pool->elt_size = size;
170  pool->elts_per_block = num;
171
172  /* List header size should be a multiple of 8.  */
173  header_size = align_eight (sizeof (struct alloc_pool_list_def));
174
175  pool->block_size = (size * num) + header_size;
176  pool->free_list = NULL;
177  pool->elts_allocated = 0;
178  pool->elts_free = 0;
179  pool->blocks_allocated = 0;
180  pool->block_list = NULL;
181
182#ifdef ENABLE_CHECKING
183  /* Increase the last used ID and use it for this pool.
184     ID == 0 is used for free elements of pool so skip it.  */
185  last_id++;
186  if (last_id == 0)
187    last_id++;
188
189  pool->id = last_id;
190#endif
191
192  return (pool);
193}
194
195/* Free all memory allocated for the given memory pool.  */
196void
197free_alloc_pool (alloc_pool pool)
198{
199  alloc_pool_list block, next_block;
200#ifdef GATHER_STATISTICS
201  struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
202#endif
203
204#ifdef ENABLE_CHECKING
205  if (!pool)
206    abort ();
207#endif
208
209  /* Free each block allocated to the pool.  */
210  for (block = pool->block_list; block != NULL; block = next_block)
211    {
212      next_block = block->next;
213      free (block);
214#ifdef GATHER_STATISTICS
215      desc->current -= pool->block_size;
216#endif
217    }
218  /* Lastly, free the pool.  */
219#ifdef ENABLE_CHECKING
220  memset (pool, 0xaf, sizeof (*pool));
221#endif
222  free (pool);
223}
224
225/* Allocates one element from the pool specified.  */
226void *
227pool_alloc (alloc_pool pool)
228{
229  alloc_pool_list header;
230  char *block;
231#ifdef GATHER_STATISTICS
232  struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
233
234  desc->allocated+=pool->elt_size;
235#endif
236
237#ifdef ENABLE_CHECKING
238  if (!pool)
239    abort ();
240#endif
241
242  /* If there are no more free elements, make some more!.  */
243  if (!pool->free_list)
244    {
245      size_t i;
246      alloc_pool_list block_header;
247
248      /* Make the block.  */
249      block = xmalloc (pool->block_size);
250      block_header = (alloc_pool_list) block;
251      block += align_eight (sizeof (struct alloc_pool_list_def));
252#ifdef GATHER_STATISTICS
253      desc->current += pool->block_size;
254      if (desc->peak < desc->current)
255	desc->peak = desc->current;
256#endif
257
258      /* Throw it on the block list.  */
259      block_header->next = pool->block_list;
260      pool->block_list = block_header;
261
262      /* Now put the actual block pieces onto the free list.  */
263      for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
264      {
265#ifdef ENABLE_CHECKING
266	/* Mark the element to be free.  */
267	((allocation_object *) block)->id = 0;
268#endif
269        header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
270        header->next = pool->free_list;
271        pool->free_list = header;
272      }
273      /* Also update the number of elements we have free/allocated, and
274         increment the allocated block count.  */
275      pool->elts_allocated += pool->elts_per_block;
276      pool->elts_free += pool->elts_per_block;
277      pool->blocks_allocated += 1;
278    }
279
280  /* Pull the first free element from the free list, and return it.  */
281  header = pool->free_list;
282  pool->free_list = header->next;
283  pool->elts_free--;
284
285#ifdef ENABLE_CHECKING
286  /* Set the ID for element.  */
287  ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id;
288#endif
289
290  return ((void *) header);
291}
292
293/* Puts PTR back on POOL's free list.  */
294void
295pool_free (alloc_pool pool, void *ptr)
296{
297  alloc_pool_list header;
298
299#ifdef ENABLE_CHECKING
300  if (!ptr)
301    abort ();
302
303  memset (ptr, 0xaf, pool->elt_size - offsetof (allocation_object, u.data));
304
305  /* Check whether the PTR was allocated from POOL.  */
306  if (pool->id != ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id)
307    abort ();
308
309  /* Mark the element to be free.  */
310  ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0;
311#else
312  /* Check if we free more than we allocated, which is Bad (TM).  */
313  if (pool->elts_free + 1 > pool->elts_allocated)
314    abort ();
315#endif
316
317  header = (alloc_pool_list) ptr;
318  header->next = pool->free_list;
319  pool->free_list = header;
320  pool->elts_free++;
321}
322/* Output per-alloc_pool statistics.  */
323#ifdef GATHER_STATISTICS
324
325/* Used to accumulate statistics about alloc_pool sizes.  */
326struct output_info
327{
328  int count;
329  int size;
330};
331
332/* Called via htab_traverse.  Output alloc_pool descriptor pointed out by SLOT
333   and update statistics.  */
334static int
335print_statistics (void **slot, void *b)
336{
337  struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot;
338  struct output_info *i = (struct output_info *) b;
339
340  if (d->allocated)
341    {
342      fprintf (stderr, "%-21s %6d %10d %10d %10d\n", d->name,
343	       d->created, d->allocated, d->peak, d->current);
344      i->size += d->allocated;
345      i->count += d->created;
346    }
347  return 1;
348}
349#endif
350
351/* Output per-alloc_pool memory usage statistics.  */
352void dump_alloc_pool_statistics (void)
353{
354#ifdef GATHER_STATISTICS
355  struct output_info info;
356
357  fprintf (stderr, "\nAlloc-pool Kind        Pools  Allocated      Peak        Leak\n");
358  fprintf (stderr, "-------------------------------------------------------------\n");
359  info.count = 0;
360  info.size = 0;
361  htab_traverse (alloc_pool_hash, print_statistics, &info);
362  fprintf (stderr, "-------------------------------------------------------------\n");
363  fprintf (stderr, "%-20s %7d %10d\n",
364	   "Total", info.count, info.size);
365  fprintf (stderr, "-------------------------------------------------------------\n");
366#endif
367}
368