coregrind/m_poolalloc.c

   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-2017 OpenWorks LLP info@open-works.co.uk,
   9                            Philippe Waroquiers philippe.waroquiers@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, see <http://www.gnu.org/licenses/>.
  23
  24    The GNU General Public License is contained in the file COPYING.
  25 */
  26
  27 #include "pub_core_basics.h"
  28 #include "pub_core_libcbase.h"
  29 #include "pub_core_libcassert.h"
  30 #include "pub_core_xarray.h"
  31 #include "pub_core_poolalloc.h" /* self */
  32
  33 struct _PoolAlloc {
  34    UWord   nrRef;         /* nr reference to this pool allocator */
  35    UWord   elemSzB;       /* element size */
  36    UWord   nPerPool;      /* # elems per pool */
  37    Alloc_Fn_t alloc_fn;   /* pool allocator */
  38    const HChar*  cc;      /* pool allocator's cost centre */
  39    Free_Fn_t free_fn;     /* pool allocator's free-er */
  40    /* XArray of void* (pointers to pools).  The pools themselves.
  41       Each element is a pointer to a block of size (elemSzB *
  42       nPerPool) bytes. */
  43    XArray* pools;
  44    /* next free element.  Is a pointer to an element in one of the
  45       pools pointed to by .pools */
  46    void* nextFree;
  47 };
  48
  49 PoolAlloc* VG_(newPA) ( UWord  elemSzB,
  50                         UWord  nPerPool,
  51                         Alloc_Fn_t alloc_fn,
  52                         const  HChar* cc,
  53                         Free_Fn_t free_fn )
  54 {
  55    PoolAlloc* pa;
  56    vg_assert(0 == (elemSzB % sizeof(UWord)));
  57    vg_assert(elemSzB >= sizeof(UWord));
  58    vg_assert(nPerPool >= 100); /* let's say */
  59    vg_assert(alloc_fn);
  60    vg_assert(cc);
  61    vg_assert(free_fn);
  62    pa = alloc_fn(cc, sizeof(*pa));
  63    VG_(memset)(pa, 0, sizeof(*pa));
  64    pa->nrRef    = 0;
  65    pa->elemSzB  = elemSzB;
  66    pa->nPerPool = nPerPool;
  67    pa->pools    = NULL;
  68    pa->alloc_fn = alloc_fn;
  69    pa->cc       = cc;
  70    pa->free_fn  = free_fn;
  71    pa->pools    = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(void*) );
  72    pa->nextFree = NULL;
  73
  74    return pa;
  75 }
  76
  77 void VG_(deletePA) ( PoolAlloc* pa)
  78 {
  79    Word i;
  80    vg_assert(pa->nrRef == 0);
  81    for (i = 0; i < VG_(sizeXA) (pa->pools); i++)
  82       pa->free_fn (*(UWord **)VG_(indexXA) ( pa->pools, i ));
  83    VG_(deleteXA) (pa->pools);
  84    pa->free_fn (pa);
  85 }
  86
  87 /* The freelist is empty.  Allocate a new pool and put all the new
  88    elements in it onto the freelist. */
  89 __attribute__((noinline))
  90 static void pal_add_new_pool ( PoolAlloc* pa )
  91 {
  92    Word   i;
  93    UWord* pool;
  94    vg_assert(pa);
  95    vg_assert(pa->nextFree == NULL);
  96    pool = pa->alloc_fn( pa->cc, pa->elemSzB * pa->nPerPool );
  97    /* extend the freelist through the new pool.  Place the freelist
  98       pointer in the first word of each element.  That's why the
  99       element size must be at least one word. */
 100    for (i = pa->nPerPool-1; i >= 0; i--) {
 101       UChar* elemC = ((UChar*)pool) + i * pa->elemSzB;
 102       UWord* elem  = (UWord*)elemC;
 103       vg_assert(0 == (((UWord)elem) % sizeof(UWord)));
 104       *elem = (UWord)pa->nextFree;
 105       pa->nextFree = elem;
 106    }
 107    /* and add to our collection of pools */
 108    VG_(addToXA)( pa->pools, &pool );
 109 }
 110
 111 UWord VG_(sizePA) ( PoolAlloc* pa)
 112 {
 113    vg_assert(pa);
 114    return pa->nPerPool * VG_(sizeXA) (pa->pools);
 115 }
 116
 117 void* VG_(allocEltPA) ( PoolAlloc* pa)
 118 {
 119    UWord* elem;
 120    if (UNLIKELY(pa->nextFree == NULL)) {
 121       pal_add_new_pool(pa);
 122    }
 123    elem = pa->nextFree;
 124    pa->nextFree = (void*)*elem;
 125    *elem = 0; /* unnecessary, but just to be on the safe side */
 126    return elem;
 127 }
 128
 129 void VG_(freeEltPA) ( PoolAlloc* pa, void* p)
 130 {
 131    UWord* elem = (UWord*)p;
 132    *elem = (UWord)pa->nextFree;
 133    pa->nextFree = elem;
 134 }
 135
 136
 137 void VG_(addRefPA) ( PoolAlloc* pa)
 138 {
 139    pa->nrRef++;
 140 }
 141
 142 UWord VG_(releasePA)(PoolAlloc* pa)
 143 {
 144    UWord nrRef;
 145
 146    vg_assert(pa->nrRef > 0);
 147    nrRef = --pa->nrRef;
 148    if (nrRef == 0)
 149       VG_(deletePA)(pa);
 150    return nrRef;
 151 }