Home | History | Annotate | Download | only in coregrind
      1 /*------------------------------------------------------------------------*/
      2 /*--- A simple pool (memory) allocator implementation. m_poolalloc.c ---  */
      3 /*------------------------------------------------------------------------*/
      4 /*
      5    This file is part of Valgrind, a dynamic binary instrumentation
      6    framework.
      7 
      8    Copyright (C) 2011-2013 OpenWorks LLP info (at) open-works.co.uk,
      9                            Philippe Waroquiers philippe.waroquiers (at) skynet.be
     10 
     11    This program is free software; you can redistribute it and/or
     12    modify it under the terms of the GNU General Public License as
     13    published by the Free Software Foundation; either version 2 of the
     14    License, or (at your option) any later version.
     15 
     16    This program is distributed in the hope that it will be useful, but
     17    WITHOUT ANY WARRANTY; without even the implied warranty of
     18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     19    General Public License for more details.
     20 
     21    You should have received a copy of the GNU General Public License
     22    along with this program; if not, write to the Free Software
     23    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
     24    02111-1307, USA.
     25 
     26    The GNU General Public License is contained in the file COPYING.
     27 */
     28 
     29 #include "pub_core_basics.h"
     30 #include "pub_core_libcbase.h"
     31 #include "pub_core_libcassert.h"
     32 #include "pub_core_xarray.h"
     33 #include "pub_core_poolalloc.h" /* self */
     34 
     35 struct _PoolAlloc {
     36    UWord   nrRef;         /* nr reference to this pool allocator */
     37    UWord   elemSzB;       /* element size */
     38    UWord   nPerPool;      /* # elems per pool */
     39    void*   (*alloc)(const HChar*, SizeT); /* pool allocator */
     40    const HChar*  cc; /* pool allocator's cc */
     41    void    (*free)(void*); /* pool allocator's free-er */
     42    /* XArray of void* (pointers to pools).  The pools themselves.
     43       Each element is a pointer to a block of size (elemSzB *
     44       nPerPool) bytes. */
     45    XArray* pools;
     46    /* next free element.  Is a pointer to an element in one of the
     47       pools pointed to by .pools */
     48    void* nextFree;
     49 };
     50 
     51 PoolAlloc* VG_(newPA) ( UWord  elemSzB,
     52                         UWord  nPerPool,
     53                         void*  (*alloc)(const HChar*, SizeT),
     54                         const  HChar* cc,
     55                         void   (*free_fn)(void*) )
     56 {
     57    PoolAlloc* pa;
     58    vg_assert(0 == (elemSzB % sizeof(UWord)));
     59    vg_assert(elemSzB >= sizeof(UWord));
     60    vg_assert(nPerPool >= 100); /* let's say */
     61    vg_assert(alloc);
     62    vg_assert(cc);
     63    vg_assert(free_fn);
     64    pa = alloc(cc, sizeof(*pa));
     65    vg_assert(pa);
     66    VG_(memset)(pa, 0, sizeof(*pa));
     67    pa->nrRef    = 0;
     68    pa->elemSzB  = elemSzB;
     69    pa->nPerPool = nPerPool;
     70    pa->pools    = NULL;
     71    pa->alloc    = alloc;
     72    pa->cc       = cc;
     73    pa->free     = free_fn;
     74    pa->pools    = VG_(newXA)( alloc, cc, free_fn, sizeof(void*) );
     75    pa->nextFree = NULL;
     76    vg_assert(pa->pools);
     77    return pa;
     78 }
     79 
     80 void VG_(deletePA) ( PoolAlloc* pa)
     81 {
     82    Word i;
     83    vg_assert(pa->nrRef == 0);
     84    for (i = 0; i < VG_(sizeXA) (pa->pools); i++)
     85       pa->free (*(UWord **)VG_(indexXA) ( pa->pools, i ));
     86    VG_(deleteXA) (pa->pools);
     87    pa->free (pa);
     88 }
     89 
     90 /* The freelist is empty.  Allocate a new pool and put all the new
     91    elements in it onto the freelist. */
     92 __attribute__((noinline))
     93 static void pal_add_new_pool ( PoolAlloc* pa )
     94 {
     95    Word   i;
     96    UWord* pool;
     97    vg_assert(pa);
     98    vg_assert(pa->nextFree == NULL);
     99    pool = pa->alloc( pa->cc, pa->elemSzB * pa->nPerPool );
    100    vg_assert(pool);
    101    /* extend the freelist through the new pool.  Place the freelist
    102       pointer in the first word of each element.  That's why the
    103       element size must be at least one word. */
    104    for (i = pa->nPerPool-1; i >= 0; i--) {
    105       UChar* elemC = ((UChar*)pool) + i * pa->elemSzB;
    106       UWord* elem  = (UWord*)elemC;
    107       vg_assert(0 == (((UWord)elem) % sizeof(UWord)));
    108       *elem = (UWord)pa->nextFree;
    109       pa->nextFree = elem;
    110    }
    111    /* and add to our collection of pools */
    112    VG_(addToXA)( pa->pools, &pool );
    113 }
    114 
    115 void* VG_(allocEltPA) ( PoolAlloc* pa)
    116 {
    117    UWord* elem;
    118    if (UNLIKELY(pa->nextFree == NULL)) {
    119       pal_add_new_pool(pa);
    120    }
    121    elem = pa->nextFree;
    122    pa->nextFree = (void*)*elem;
    123    *elem = 0; /* unnecessary, but just to be on the safe side */
    124    return elem;
    125 }
    126 
    127 void VG_(freeEltPA) ( PoolAlloc* pa, void* p)
    128 {
    129    UWord* elem = (UWord*)p;
    130    *elem = (UWord)pa->nextFree;
    131    pa->nextFree = elem;
    132 }
    133 
    134 
    135 void VG_(addRefPA) ( PoolAlloc* pa)
    136 {
    137    pa->nrRef++;
    138 }
    139 
    140 UWord VG_(releasePA)(PoolAlloc* pa)
    141 {
    142    UWord nrRef;
    143 
    144    vg_assert(pa->nrRef > 0);
    145    nrRef = --pa->nrRef;
    146    if (nrRef == 0)
    147       VG_(deletePA)(pa);
    148    return nrRef;
    149 }
    150