alloc-pool.c revision 169689
167754Smsmith/* Functions to support a pool of allocatable objects. 267754Smsmith Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, 2006 367754Smsmith Free Software Foundation, Inc. 4102550Siwasaki Contributed by Daniel Berlin <dan@cgsoftware.com> 567754Smsmith 667754SmsmithThis file is part of GCC. 767754Smsmith 867754SmsmithGCC is free software; you can redistribute it and/or modify it under 967754Smsmiththe terms of the GNU General Public License as published by the Free 1067754SmsmithSoftware Foundation; either version 2, or (at your option) any later 1167754Smsmithversion. 1291116Smsmith 1370243SmsmithGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1467754SmsmithWARRANTY; without even the implied warranty of MERCHANTABILITY or 1567754SmsmithFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1667754Smsmithfor more details. 1767754Smsmith 1867754SmsmithYou should have received a copy of the GNU General Public License 1967754Smsmithalong with GCC; see the file COPYING. If not, write to the Free 2067754SmsmithSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2167754Smsmith02110-1301, USA. */ 2267754Smsmith 2367754Smsmith#include "config.h" 2467754Smsmith#include "system.h" 2567754Smsmith#include "alloc-pool.h" 2667754Smsmith#include "hashtab.h" 2767754Smsmith 2867754Smsmith#define align_eight(x) (((x+7) >> 3) << 3) 2967754Smsmith 3067754Smsmith/* The internal allocation object. */ 3167754Smsmithtypedef struct allocation_object_def 3267754Smsmith{ 3367754Smsmith#ifdef ENABLE_CHECKING 3467754Smsmith /* The ID of alloc pool which the object was allocated from. */ 3567754Smsmith ALLOC_POOL_ID_TYPE id; 3667754Smsmith#endif 3767754Smsmith 3867754Smsmith union 3967754Smsmith { 4067754Smsmith /* The data of the object. */ 4167754Smsmith char data[1]; 4267754Smsmith 4367754Smsmith /* Because we want any type of data to be well aligned after the ID, 4467754Smsmith the following elements are here. They are never accessed so 4567754Smsmith the allocated object may be even smaller than this structure. */ 4667754Smsmith char *align_p; 4767754Smsmith HOST_WIDEST_INT align_i; 4867754Smsmith long double align_ld; 4967754Smsmith } u; 5067754Smsmith} allocation_object; 5167754Smsmith 5267754Smsmith/* Convert a pointer to allocation_object from a pointer to user data. */ 5367754Smsmith#define ALLOCATION_OBJECT_PTR_FROM_USER_PTR(X) \ 5467754Smsmith ((allocation_object *) (((char *) (X)) \ 5567754Smsmith - offsetof (allocation_object, u.data))) 5667754Smsmith 5767754Smsmith/* Convert a pointer to user data from a pointer to allocation_object. */ 5867754Smsmith#define USER_PTR_FROM_ALLOCATION_OBJECT_PTR(X) \ 5967754Smsmith ((void *) (((allocation_object *) (X))->u.data)) 6067754Smsmith 6167754Smsmith#ifdef ENABLE_CHECKING 6267754Smsmith/* Last used ID. */ 6367754Smsmithstatic ALLOC_POOL_ID_TYPE last_id; 6467754Smsmith#endif 6567754Smsmith 6667754Smsmith#ifdef GATHER_STATISTICS 6767754Smsmith 6867754Smsmith/* Store information about each particular alloc_pool. */ 6967754Smsmithstruct alloc_pool_descriptor 7067754Smsmith{ 7167754Smsmith const char *name; 7267754Smsmith int allocated; 7367754Smsmith int created; 7467754Smsmith int peak; 7567754Smsmith int current; 7667754Smsmith}; 7767754Smsmith 7867754Smsmith/* Hashtable mapping alloc_pool names to descriptors. */ 7967754Smsmithstatic htab_t alloc_pool_hash; 8067754Smsmith 8167754Smsmith/* Hashtable helpers. */ 8267754Smsmithstatic hashval_t 8367754Smsmithhash_descriptor (const void *p) 8467754Smsmith{ 8567754Smsmith const struct alloc_pool_descriptor *d = p; 8667754Smsmith return htab_hash_pointer (d->name); 8767754Smsmith} 8867754Smsmithstatic int 8967754Smsmitheq_descriptor (const void *p1, const void *p2) 9067754Smsmith{ 9167754Smsmith const struct alloc_pool_descriptor *d = p1; 9267754Smsmith return d->name == p2; 9367754Smsmith} 9467754Smsmith 9567754Smsmith/* For given name, return descriptor, create new if needed. */ 9667754Smsmithstatic struct alloc_pool_descriptor * 9767754Smsmithalloc_pool_descriptor (const char *name) 9867754Smsmith{ 9967754Smsmith struct alloc_pool_descriptor **slot; 10067754Smsmith 10167754Smsmith if (!alloc_pool_hash) 10267754Smsmith alloc_pool_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL); 10367754Smsmith 10467754Smsmith slot = (struct alloc_pool_descriptor **) 10567754Smsmith htab_find_slot_with_hash (alloc_pool_hash, name, 10667754Smsmith htab_hash_pointer (name), 10767754Smsmith 1); 10867754Smsmith if (*slot) 10967754Smsmith return *slot; 11067754Smsmith *slot = xcalloc (sizeof (**slot), 1); 11167754Smsmith (*slot)->name = name; 11267754Smsmith return *slot; 11367754Smsmith} 11467754Smsmith#endif 11567754Smsmith 11667754Smsmith/* Create a pool of things of size SIZE, with NUM in each block we 11767754Smsmith allocate. */ 11867754Smsmith 11967754Smsmithalloc_pool 12067754Smsmithcreate_alloc_pool (const char *name, size_t size, size_t num) 12167754Smsmith{ 12267754Smsmith alloc_pool pool; 12367754Smsmith size_t pool_size, header_size; 12467754Smsmith#ifdef GATHER_STATISTICS 12567754Smsmith struct alloc_pool_descriptor *desc; 12667754Smsmith#endif 12767754Smsmith 12867754Smsmith gcc_assert (name); 12967754Smsmith 13067754Smsmith /* Make size large enough to store the list header. */ 13167754Smsmith if (size < sizeof (alloc_pool_list)) 13267754Smsmith size = sizeof (alloc_pool_list); 13367754Smsmith 13467754Smsmith /* Now align the size to a multiple of 4. */ 13567754Smsmith size = align_eight (size); 13667754Smsmith 13767754Smsmith#ifdef ENABLE_CHECKING 13867754Smsmith /* Add the aligned size of ID. */ 13967754Smsmith size += offsetof (allocation_object, u.data); 14067754Smsmith#endif 14167754Smsmith 14267754Smsmith /* Um, we can't really allocate 0 elements per block. */ 14367754Smsmith gcc_assert (num); 14467754Smsmith 14567754Smsmith /* Find the size of the pool structure, and the name. */ 14667754Smsmith pool_size = sizeof (struct alloc_pool_def); 14767754Smsmith 14867754Smsmith /* and allocate that much memory. */ 14967754Smsmith pool = xmalloc (pool_size); 15091116Smsmith 15167754Smsmith /* Now init the various pieces of our pool structure. */ 15267754Smsmith pool->name = /*xstrdup (name)*/name; 15367754Smsmith#ifdef GATHER_STATISTICS 15477424Smsmith desc = alloc_pool_descriptor (name); 15591116Smsmith desc->created++; 15667754Smsmith#endif 15767754Smsmith pool->elt_size = size; 15867754Smsmith pool->elts_per_block = num; 15991116Smsmith 16091116Smsmith /* List header size should be a multiple of 8. */ 16167754Smsmith header_size = align_eight (sizeof (struct alloc_pool_list_def)); 16267754Smsmith 16367754Smsmith pool->block_size = (size * num) + header_size; 16499679Siwasaki pool->free_list = NULL; 16567754Smsmith pool->elts_allocated = 0; 16699679Siwasaki pool->elts_free = 0; 16799679Siwasaki pool->blocks_allocated = 0; 16899679Siwasaki pool->block_list = NULL; 16967754Smsmith 17067754Smsmith#ifdef ENABLE_CHECKING 17199679Siwasaki /* Increase the last used ID and use it for this pool. 17299679Siwasaki ID == 0 is used for free elements of pool so skip it. */ 17399679Siwasaki last_id++; 17499679Siwasaki if (last_id == 0) 17599679Siwasaki last_id++; 17699679Siwasaki 177102550Siwasaki pool->id = last_id; 17899679Siwasaki#endif 17999679Siwasaki 18099679Siwasaki return (pool); 181102550Siwasaki} 18299679Siwasaki 18399679Siwasaki/* Free all memory allocated for the given memory pool. */ 18499679Siwasakivoid 18599679Siwasakifree_alloc_pool (alloc_pool pool) 18699679Siwasaki{ 18799679Siwasaki alloc_pool_list block, next_block; 18899679Siwasaki#ifdef GATHER_STATISTICS 189102550Siwasaki struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name); 19099679Siwasaki#endif 19199679Siwasaki 19299679Siwasaki gcc_assert (pool); 19399679Siwasaki 19499679Siwasaki /* Free each block allocated to the pool. */ 19599679Siwasaki for (block = pool->block_list; block != NULL; block = next_block) 19699679Siwasaki { 19799679Siwasaki next_block = block->next; 19899679Siwasaki free (block); 19999679Siwasaki#ifdef GATHER_STATISTICS 20099679Siwasaki desc->current -= pool->block_size; 20199679Siwasaki#endif 20299679Siwasaki } 20399679Siwasaki#ifdef ENABLE_CHECKING 20499679Siwasaki memset (pool, 0xaf, sizeof (*pool)); 20599679Siwasaki#endif 20699679Siwasaki /* Lastly, free the pool. */ 20799679Siwasaki free (pool); 20899679Siwasaki} 20999679Siwasaki 21099679Siwasaki/* Frees the alloc_pool, if it is empty and zero *POOL in this case. */ 21199679Siwasakivoid 21299679Siwasakifree_alloc_pool_if_empty (alloc_pool *pool) 21399679Siwasaki{ 21499679Siwasaki if ((*pool)->elts_free == (*pool)->elts_allocated) 21599679Siwasaki { 21699679Siwasaki free_alloc_pool (*pool); 21799679Siwasaki *pool = NULL; 21899679Siwasaki } 21967754Smsmith} 22077424Smsmith 22167754Smsmith/* Allocates one element from the pool specified. */ 22267754Smsmithvoid * 22367754Smsmithpool_alloc (alloc_pool pool) 22467754Smsmith{ 22567754Smsmith alloc_pool_list header; 22667754Smsmith char *block; 22767754Smsmith#ifdef GATHER_STATISTICS 22867754Smsmith struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name); 22967754Smsmith 23067754Smsmith desc->allocated+=pool->elt_size; 23167754Smsmith#endif 23267754Smsmith 23399679Siwasaki gcc_assert (pool); 23467754Smsmith 23567754Smsmith /* If there are no more free elements, make some more!. */ 23691116Smsmith if (!pool->free_list) 23767754Smsmith { 23867754Smsmith size_t i; 23999679Siwasaki alloc_pool_list block_header; 24077424Smsmith 24191116Smsmith /* Make the block. */ 24267754Smsmith block = XNEWVEC (char, pool->block_size); 24367754Smsmith block_header = (alloc_pool_list) block; 24499679Siwasaki block += align_eight (sizeof (struct alloc_pool_list_def)); 24567754Smsmith#ifdef GATHER_STATISTICS 24691116Smsmith desc->current += pool->block_size; 24767754Smsmith if (desc->peak < desc->current) 24867754Smsmith desc->peak = desc->current; 24967754Smsmith#endif 25067754Smsmith 25167754Smsmith /* Throw it on the block list. */ 25291116Smsmith block_header->next = pool->block_list; 25367754Smsmith pool->block_list = block_header; 25467754Smsmith 25567754Smsmith /* Now put the actual block pieces onto the free list. */ 25677424Smsmith for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size) 25799679Siwasaki { 25891116Smsmith#ifdef ENABLE_CHECKING 25967754Smsmith /* Mark the element to be free. */ 26067754Smsmith ((allocation_object *) block)->id = 0; 26167754Smsmith#endif 26267754Smsmith header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block); 26391116Smsmith header->next = pool->free_list; 26467754Smsmith pool->free_list = header; 26591116Smsmith } 26667754Smsmith /* Also update the number of elements we have free/allocated, and 26767754Smsmith increment the allocated block count. */ 26867754Smsmith pool->elts_allocated += pool->elts_per_block; 26967754Smsmith pool->elts_free += pool->elts_per_block; 27091116Smsmith pool->blocks_allocated += 1; 27167754Smsmith } 27291116Smsmith 27367754Smsmith /* Pull the first free element from the free list, and return it. */ 27467754Smsmith header = pool->free_list; 27567754Smsmith pool->free_list = header->next; 27677424Smsmith pool->elts_free--; 27767754Smsmith 27891116Smsmith#ifdef ENABLE_CHECKING 27967754Smsmith /* Set the ID for element. */ 28067754Smsmith ALLOCATION_OBJECT_PTR_FROM_USER_PTR (header)->id = pool->id; 28167754Smsmith#endif 28277424Smsmith 28367754Smsmith return ((void *) header); 28491116Smsmith} 28567754Smsmith 28667754Smsmith/* Puts PTR back on POOL's free list. */ 28767754Smsmithvoid 28867754Smsmithpool_free (alloc_pool pool, void *ptr) 28991116Smsmith{ 29067754Smsmith alloc_pool_list header; 29191116Smsmith 29267754Smsmith gcc_assert (ptr); 29367754Smsmith 29467754Smsmith#ifdef ENABLE_CHECKING 29577424Smsmith memset (ptr, 0xaf, pool->elt_size - offsetof (allocation_object, u.data)); 29667754Smsmith 29791116Smsmith /* Check whether the PTR was allocated from POOL. */ 29867754Smsmith gcc_assert (pool->id == ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id); 29967754Smsmith 30067754Smsmith /* Mark the element to be free. */ 30167754Smsmith ALLOCATION_OBJECT_PTR_FROM_USER_PTR (ptr)->id = 0; 30291116Smsmith#else 30367754Smsmith /* Check if we free more than we allocated, which is Bad (TM). */ 30491116Smsmith gcc_assert (pool->elts_free < pool->elts_allocated); 30567754Smsmith#endif 30667754Smsmith 30767754Smsmith header = (alloc_pool_list) ptr; 30877424Smsmith header->next = pool->free_list; 30967754Smsmith pool->free_list = header; 31091116Smsmith pool->elts_free++; 31167754Smsmith} 31267754Smsmith/* Output per-alloc_pool statistics. */ 31367754Smsmith#ifdef GATHER_STATISTICS 31467754Smsmith 31591116Smsmith/* Used to accumulate statistics about alloc_pool sizes. */ 31667754Smsmithstruct output_info 31791116Smsmith{ 31867754Smsmith int count; 31967754Smsmith int size; 32067754Smsmith}; 32177424Smsmith 32267754Smsmith/* Called via htab_traverse. Output alloc_pool descriptor pointed out by SLOT 32391116Smsmith and update statistics. */ 32467754Smsmithstatic int 32567754Smsmithprint_statistics (void **slot, void *b) 32667754Smsmith{ 32767754Smsmith struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot; 32891116Smsmith struct output_info *i = (struct output_info *) b; 32967754Smsmith 33091116Smsmith if (d->allocated) 33167754Smsmith { 33267754Smsmith fprintf (stderr, "%-21s %6d %10d %10d %10d\n", d->name, 33367754Smsmith d->created, d->allocated, d->peak, d->current); 33477424Smsmith i->size += d->allocated; 33567754Smsmith i->count += d->created; 33691116Smsmith } 33767754Smsmith return 1; 33867754Smsmith} 33977424Smsmith#endif 34077424Smsmith 34191116Smsmith/* Output per-alloc_pool memory usage statistics. */ 34277424Smsmithvoid 34391116Smsmithdump_alloc_pool_statistics (void) 34477424Smsmith{ 34577424Smsmith#ifdef GATHER_STATISTICS 34677424Smsmith struct output_info info; 34777424Smsmith 34877424Smsmith if (!alloc_pool_hash) 34991116Smsmith return; 35077424Smsmith 35177424Smsmith fprintf (stderr, "\nAlloc-pool Kind Pools Allocated Peak Leak\n"); 35291116Smsmith fprintf (stderr, "-------------------------------------------------------------\n"); 35367754Smsmith info.count = 0; 35491116Smsmith info.size = 0; 35567754Smsmith htab_traverse (alloc_pool_hash, print_statistics, &info); 35691116Smsmith fprintf (stderr, "-------------------------------------------------------------\n"); 35767754Smsmith fprintf (stderr, "%-20s %7d %10d\n", 35867754Smsmith "Total", info.count, info.size); 35991116Smsmith fprintf (stderr, "-------------------------------------------------------------\n"); 36067754Smsmith#endif 36191116Smsmith} 36267754Smsmith