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@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, 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_fn)(const HChar*, SizeT); /* pool allocator */
40 const HChar* cc; /* pool allocator's cost centre */
41 void (*free_fn)(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
VG_(newPA)51 PoolAlloc* VG_(newPA) ( UWord elemSzB,
52 UWord nPerPool,
53 void* (*alloc_fn)(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_fn);
62 vg_assert(cc);
63 vg_assert(free_fn);
64 pa = alloc_fn(cc, sizeof(*pa));
65 VG_(memset)(pa, 0, sizeof(*pa));
66 pa->nrRef = 0;
67 pa->elemSzB = elemSzB;
68 pa->nPerPool = nPerPool;
69 pa->pools = NULL;
70 pa->alloc_fn = alloc_fn;
71 pa->cc = cc;
72 pa->free_fn = free_fn;
73 pa->pools = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(void*) );
74 pa->nextFree = NULL;
75
76 return pa;
77 }
78
VG_(deletePA)79 void VG_(deletePA) ( PoolAlloc* pa)
80 {
81 Word i;
82 vg_assert(pa->nrRef == 0);
83 for (i = 0; i < VG_(sizeXA) (pa->pools); i++)
84 pa->free_fn (*(UWord **)VG_(indexXA) ( pa->pools, i ));
85 VG_(deleteXA) (pa->pools);
86 pa->free_fn (pa);
87 }
88
89 /* The freelist is empty. Allocate a new pool and put all the new
90 elements in it onto the freelist. */
91 __attribute__((noinline))
pal_add_new_pool(PoolAlloc * pa)92 static void pal_add_new_pool ( PoolAlloc* pa )
93 {
94 Word i;
95 UWord* pool;
96 vg_assert(pa);
97 vg_assert(pa->nextFree == NULL);
98 pool = pa->alloc_fn( pa->cc, pa->elemSzB * pa->nPerPool );
99 /* extend the freelist through the new pool. Place the freelist
100 pointer in the first word of each element. That's why the
101 element size must be at least one word. */
102 for (i = pa->nPerPool-1; i >= 0; i--) {
103 UChar* elemC = ((UChar*)pool) + i * pa->elemSzB;
104 UWord* elem = (UWord*)elemC;
105 vg_assert(0 == (((UWord)elem) % sizeof(UWord)));
106 *elem = (UWord)pa->nextFree;
107 pa->nextFree = elem;
108 }
109 /* and add to our collection of pools */
110 VG_(addToXA)( pa->pools, &pool );
111 }
112
VG_(sizePA)113 UWord VG_(sizePA) ( PoolAlloc* pa)
114 {
115 vg_assert(pa);
116 return pa->nPerPool * VG_(sizeXA) (pa->pools);
117 }
118
VG_(allocEltPA)119 void* VG_(allocEltPA) ( PoolAlloc* pa)
120 {
121 UWord* elem;
122 if (UNLIKELY(pa->nextFree == NULL)) {
123 pal_add_new_pool(pa);
124 }
125 elem = pa->nextFree;
126 pa->nextFree = (void*)*elem;
127 *elem = 0; /* unnecessary, but just to be on the safe side */
128 return elem;
129 }
130
VG_(freeEltPA)131 void VG_(freeEltPA) ( PoolAlloc* pa, void* p)
132 {
133 UWord* elem = (UWord*)p;
134 *elem = (UWord)pa->nextFree;
135 pa->nextFree = elem;
136 }
137
138
VG_(addRefPA)139 void VG_(addRefPA) ( PoolAlloc* pa)
140 {
141 pa->nrRef++;
142 }
143
VG_(releasePA)144 UWord VG_(releasePA)(PoolAlloc* pa)
145 {
146 UWord nrRef;
147
148 vg_assert(pa->nrRef > 0);
149 nrRef = --pa->nrRef;
150 if (nrRef == 0)
151 VG_(deletePA)(pa);
152 return nrRef;
153 }
154