1 /*--------------------------------------------------------------------*/
2 /*--- A pool (memory) allocator that avoids duplicated copies. ---*/
3 /*--- m_deduppoolalloc.c ---*/
4 /*--------------------------------------------------------------------*/
5 /*
6 This file is part of Valgrind, a dynamic binary instrumentation
7 framework.
8
9 Copyright (C) 2014-2015 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_libcprint.h"
32 #include "pub_core_libcassert.h"
33 #include "pub_core_xarray.h"
34 #include "pub_core_deduppoolalloc.h" /* self */
35 #include "pub_core_hashtable.h"
36 #include "pub_core_poolalloc.h"
37 #include "pub_core_options.h"
38 #include "pub_core_mallocfree.h"
39 #include "pub_core_debuglog.h"
40
41 struct _DedupPoolAlloc {
42 SizeT poolSzB; /* Minimum size of a pool. */
43 SizeT fixedSzb; /* If using VG_(allocFixedEltDedupPA), size of elements */
44 SizeT eltAlign;
45 void* (*alloc_fn)(const HChar*, SizeT); /* pool allocator */
46 const HChar* cc; /* pool allocator's cost centre */
47 void (*free_fn)(void*); /* pool allocator's deallocation function */
48 /* XArray of void* (pointers to pools). The pools themselves.
49 Each element is a pointer to a block of size at least PoolSzB bytes.
50 The last block might be smaller due to a call to shrink_block. */
51 XArray *pools;
52
53 /* hash table of pool elements, used to dedup.
54 If NULL, it means the DedupPoolAlloc is frozen. */
55 VgHashTable *ht_elements;
56
57 /* Hash table nodes of pool_elements are allocated with a pool, to
58 decrease memory overhead during insertion in the DedupPoolAlloc. */
59 PoolAlloc *ht_node_pa;
60
61 UChar *curpool; /* last allocated pool. */
62 UChar *curpool_free; /* Pos in current pool to allocate next elt.
63 always aligned on eltAlign. */
64 UChar *curpool_limit; /* Last pos in current pool. */
65 /* Note that for a fixed size pool, we only have a single pool to allow
66 simple/fast indexing. This single pool is grown, which might change
67 the address of the already allocated elements. */
68
69 /* Total nr of alloc calls, resulting in (we hope) a lot less
70 real (dedup) elements. */
71 ULong nr_alloc_calls;
72 };
73
74 typedef
75 struct _ht_node {
76 struct _ht_node *next; // Read/Write by hashtable (pub_tool_hashtable.h)
77 UWord key; // Read by hashtable (pub_tool_hashtable.h)
78 SizeT eltSzB;
79 const void *elt;
80 }
81 ht_node;
82
VG_(newDedupPA)83 DedupPoolAlloc* VG_(newDedupPA) ( SizeT poolSzB,
84 SizeT eltAlign,
85 void* (*alloc_fn)(const HChar*, SizeT),
86 const HChar* cc,
87 void (*free_fn)(void*) )
88 {
89 DedupPoolAlloc* ddpa;
90 vg_assert(poolSzB >= eltAlign);
91 vg_assert(poolSzB >= 100); /* let's say */
92 vg_assert(poolSzB >= 10*eltAlign); /* let's say */
93 vg_assert(alloc_fn);
94 vg_assert(cc);
95 vg_assert(free_fn);
96 ddpa = alloc_fn(cc, sizeof(*ddpa));
97 VG_(memset)(ddpa, 0, sizeof(*ddpa));
98 ddpa->poolSzB = poolSzB;
99 ddpa->fixedSzb = 0;
100 ddpa->eltAlign = eltAlign;
101 ddpa->alloc_fn = alloc_fn;
102 ddpa->cc = cc;
103 ddpa->free_fn = free_fn;
104 ddpa->pools = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(void*) );
105
106 ddpa->ht_elements = VG_(HT_construct) (cc);
107 ddpa->ht_node_pa = VG_(newPA) ( sizeof(ht_node),
108 1000,
109 alloc_fn,
110 cc,
111 free_fn);
112 ddpa->curpool = NULL;
113 ddpa->curpool_limit = NULL;
114 ddpa->curpool_free = NULL;
115
116 return ddpa;
117 }
118
VG_(deleteDedupPA)119 void VG_(deleteDedupPA) ( DedupPoolAlloc* ddpa)
120 {
121 Word i;
122 if (ddpa->ht_elements)
123 // Free data structures used for insertion.
124 VG_(freezeDedupPA) (ddpa, NULL);
125 for (i = 0; i < VG_(sizeXA) (ddpa->pools); i++)
126 ddpa->free_fn (*(UWord **)VG_(indexXA) ( ddpa->pools, i ));
127 VG_(deleteXA) (ddpa->pools);
128 ddpa->free_fn (ddpa);
129 }
130
131 static __inline__
ddpa_align(DedupPoolAlloc * ddpa,UChar * c)132 UChar* ddpa_align ( DedupPoolAlloc* ddpa, UChar *c )
133 {
134 return (UChar*)VG_ROUNDUP(c, ddpa->eltAlign);
135 }
136
137 /* Allocate a new pool or grow the (only) pool for a fixed size ddpa. */
138 __attribute__((noinline))
ddpa_add_new_pool_or_grow(DedupPoolAlloc * ddpa)139 static void ddpa_add_new_pool_or_grow ( DedupPoolAlloc* ddpa )
140 {
141 vg_assert(ddpa);
142
143 if (ddpa->fixedSzb > 0 && ddpa->curpool != NULL) {
144 // Grow (* 2) the current (fixed elt) pool
145 UChar *curpool_align = ddpa_align(ddpa, ddpa->curpool);
146 SizeT curpool_used = ddpa->curpool_free - curpool_align;
147 SizeT curpool_size = ddpa->curpool_limit - ddpa->curpool + 1;
148 UChar *newpool = ddpa->alloc_fn (ddpa->cc, 2 * curpool_size);
149 UChar *newpool_free = ddpa_align (ddpa, newpool);
150 UChar *newpool_limit = newpool + 2 * curpool_size - 1;
151 Word reloc_offset = (Addr)newpool_free - (Addr)curpool_align;
152 ht_node *n;
153
154 VG_(memcpy) (newpool_free, curpool_align, curpool_used);
155 /* We have reallocated the (only) pool. We need to relocate the pointers
156 in the hash table nodes. */
157 VG_(HT_ResetIter) (ddpa->ht_elements);
158 while ((n = VG_(HT_Next) (ddpa->ht_elements))) {
159 n->elt = (void*)((Addr)n->elt + reloc_offset);
160 }
161 newpool_free += curpool_used;
162
163 VG_(dropHeadXA) (ddpa->pools, 1);
164 ddpa->free_fn (ddpa->curpool);
165 ddpa->curpool = newpool;
166 ddpa->curpool_free = newpool_free;
167 ddpa->curpool_limit = newpool_limit;
168 VG_(addToXA)( ddpa->pools, &ddpa->curpool);
169 } else {
170 /* Allocate a new pool, or allocate the first/only pool for a
171 fixed size ddpa. */
172 ddpa->curpool = ddpa->alloc_fn( ddpa->cc, ddpa->poolSzB);
173 ddpa->curpool_limit = ddpa->curpool + ddpa->poolSzB - 1;
174 ddpa->curpool_free = ddpa_align (ddpa, ddpa->curpool);
175 /* add to our collection of pools */
176 VG_(addToXA)( ddpa->pools, &ddpa->curpool );
177 }
178 }
179
180 /* Compare function for 'gen' hash table. No need to compare the key
181 in this function, as the hash table already does it for us,
182 and that in any case, if the data is equal, the keys must also be
183 equal. */
cmp_pool_elt(const void * node1,const void * node2)184 static Word cmp_pool_elt (const void* node1, const void* node2 )
185 {
186 const ht_node* hnode1 = node1;
187 const ht_node* hnode2 = node2;
188
189 /* As this function is called by hashtable, that has already checked
190 for key equality, it is likely that it is the 'good' element.
191 So, we handle the equal case first. */
192 if (hnode1->eltSzB == hnode2->eltSzB)
193 return VG_(memcmp) (hnode1->elt, hnode2->elt, hnode1->eltSzB);
194 else if (hnode1->eltSzB < hnode2->eltSzB)
195 return -1;
196 else
197 return 1;
198 }
199
200 /* Print some stats. */
print_stats(DedupPoolAlloc * ddpa)201 static void print_stats (DedupPoolAlloc *ddpa)
202 {
203 VG_(message)(Vg_DebugMsg,
204 "dedupPA:%s %ld allocs (%u uniq)"
205 " %ld pools (%ld bytes free in last pool)\n",
206 ddpa->cc,
207 (long int) ddpa->nr_alloc_calls,
208 VG_(HT_count_nodes)(ddpa->ht_elements),
209 VG_(sizeXA)(ddpa->pools),
210 ddpa->curpool ?
211 (long int) (ddpa->curpool_limit - ddpa->curpool_free + 1) : 0);
212 VG_(HT_print_stats) (ddpa->ht_elements, cmp_pool_elt);
213 }
214
215 /* Dummy free, as the ht elements are allocated in a pool, and
216 we will destroy the pool in one single operation. */
htelem_dummyfree(void * ht_elem)217 static void htelem_dummyfree(void* ht_elem)
218 {
219 }
220
VG_(freezeDedupPA)221 void VG_(freezeDedupPA) (DedupPoolAlloc *ddpa,
222 void (*shrink_block)(void*, SizeT))
223 {
224 if (VG_(clo_stats)
225 && (VG_(clo_verbosity) > 2 || VG_(debugLog_getLevel) () >= 2)) {
226 print_stats(ddpa);
227 }
228 vg_assert (!ddpa->fixedSzb || VG_(sizeXA) (ddpa->pools) == 1);
229 if (shrink_block && ddpa->curpool_limit > ddpa->curpool_free)
230 (*shrink_block)(ddpa->curpool, ddpa->curpool_free - ddpa->curpool);
231 VG_(HT_destruct) ( ddpa->ht_elements, htelem_dummyfree);
232 ddpa->ht_elements = NULL;
233 VG_(deletePA) (ddpa->ht_node_pa);
234 ddpa->ht_node_pa = NULL;
235 }
236
237
238 // hash function used by gawk and SDBM.
sdbm_hash(const UChar * buf,UInt len)239 static UInt sdbm_hash (const UChar* buf, UInt len )
240 {
241 UInt h;
242 UInt i;
243
244 h = 0;
245 for (i = 0; i < len; i++)
246 h = *buf++ + (h<<6) + (h<<16) - h;
247 return h;
248 }
249
VG_(allocEltDedupPA)250 const void* VG_(allocEltDedupPA) (DedupPoolAlloc *ddpa, SizeT eltSzB,
251 const void *elt)
252 {
253 ht_node ht_elt;
254 void* elt_ins;
255 ht_node *ht_ins;
256 vg_assert(ddpa);
257 vg_assert(ddpa->ht_elements);
258 vg_assert (eltSzB <= ddpa->poolSzB);
259
260 ddpa->nr_alloc_calls++;
261
262 ht_elt.key = sdbm_hash (elt, eltSzB);
263
264 ht_elt.eltSzB = eltSzB;
265 ht_elt.elt = elt;
266
267 ht_ins = VG_(HT_gen_lookup) (ddpa->ht_elements, &ht_elt, cmp_pool_elt);
268 if (ht_ins)
269 return ht_ins->elt;
270
271 /* Not found -> we need to allocate a new element from the pool
272 and insert it in the hash table of inserted elements. */
273
274 // Add a new pool or grow pool if not enough space in the current pool
275 if (UNLIKELY(ddpa->curpool_free == NULL
276 || ddpa->curpool_free + eltSzB - 1 > ddpa->curpool_limit)) {
277 ddpa_add_new_pool_or_grow (ddpa);
278 }
279
280 elt_ins = ddpa->curpool_free;
281 VG_(memcpy)(elt_ins, elt, eltSzB);
282 ddpa->curpool_free = ddpa_align(ddpa, ddpa->curpool_free + eltSzB);
283
284 ht_ins = VG_(allocEltPA) (ddpa->ht_node_pa);
285 ht_ins->key = ht_elt.key;
286 ht_ins->eltSzB = eltSzB;
287 ht_ins->elt = elt_ins;
288 VG_(HT_add_node)(ddpa->ht_elements, ht_ins);
289 return elt_ins;
290 }
291
292 static __inline__
elt2nr(DedupPoolAlloc * ddpa,const void * dedup_elt)293 UInt elt2nr (DedupPoolAlloc *ddpa, const void *dedup_elt)
294 {
295 vg_assert (dedup_elt >= (const void *)ddpa->curpool
296 && dedup_elt < (const void *)ddpa->curpool_free);
297 return 1 + ((const UChar*)dedup_elt - (const UChar *)ddpa->curpool)
298 / VG_ROUNDUP(ddpa->fixedSzb, ddpa->eltAlign);
299 }
300
VG_(allocFixedEltDedupPA)301 UInt VG_(allocFixedEltDedupPA) (DedupPoolAlloc *ddpa,
302 SizeT eltSzB, const void *elt)
303 {
304 if (ddpa->fixedSzb == 0) {
305 // First insertion in this ddpa
306 vg_assert (ddpa->nr_alloc_calls == 0);
307 vg_assert (eltSzB > 0);
308 ddpa->fixedSzb = eltSzB;
309 }
310 vg_assert (ddpa->fixedSzb == eltSzB);
311 const void *dedup_elt = VG_(allocEltDedupPA) (ddpa, eltSzB, elt);
312 return elt2nr (ddpa, dedup_elt);
313 }
314
VG_(indexEltNumber)315 void* VG_(indexEltNumber) (DedupPoolAlloc *ddpa,
316 UInt eltNr)
317 {
318 void *dedup_elt;
319
320 dedup_elt = ddpa->curpool
321 + (eltNr - 1) * VG_ROUNDUP(ddpa->fixedSzb, ddpa->eltAlign);
322
323 vg_assert ((UChar*)dedup_elt >= ddpa->curpool
324 && (UChar*)dedup_elt < ddpa->curpool_free);
325
326 return dedup_elt;
327 }
328
VG_(sizeDedupPA)329 UInt VG_(sizeDedupPA) (DedupPoolAlloc *ddpa)
330 {
331 if (ddpa->curpool == NULL)
332 return 0;
333
334 vg_assert (ddpa->fixedSzb);
335 return (ddpa->curpool_free - ddpa_align(ddpa, ddpa->curpool))
336 / VG_ROUNDUP(ddpa->fixedSzb, ddpa->eltAlign);
337 }
338