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-2012 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_tool_xarray.h" 33 #include "pub_tool_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)(HChar*, SizeT); /* pool allocator */ 40 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)(HChar*, SizeT), 54 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
