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