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 (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_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 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 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__ 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)) 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. */ 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. */ 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. */ 217 static void htelem_dummyfree(void* ht_elem) 218 { 219 } 220 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. 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 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__ 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 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 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 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
