coregrind/m_deduppoolalloc.c

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