include/pub_tool_deduppoolalloc.h

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- A pool (memory) allocator that avoids duplicated copies.     ---*/
   4 /*---                                    pub_tool_deduppoolalloc.h ---*/
   5 /*--------------------------------------------------------------------*/
   6
   7 /*
   8    This file is part of Valgrind, a dynamic binary instrumentation
   9    framework.
  10
  11    Copyright (C) 2014-2017 Philippe Waroquiers philippe.waroquiers@skynet.be
  12
  13    This program is free software; you can redistribute it and/or
  14    modify it under the terms of the GNU General Public License as
  15    published by the Free Software Foundation; either version 2 of the
  16    License, or (at your option) any later version.
  17
  18    This program is distributed in the hope that it will be useful, but
  19    WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21    General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, see <http://www.gnu.org/licenses/>.
  25
  26    The GNU General Public License is contained in the file COPYING.
  27 */
  28
  29 #ifndef __PUB_TOOL_DEDUPPOOLALLOC_H
  30 #define __PUB_TOOL_DEDUPPOOLALLOC_H
  31
  32 #include "pub_tool_basics.h"   // UWord
  33
  34 //-----------------------------------------------------------------------------
  35 // PURPOSE: Provides a pool allocator for elements, storing only once identical
  36 // elements. In other words, this can be considered a "dictionary" of elements.
  37 //
  38 // This pool allocator manages elements allocation by allocating "pools" of
  39 // many elements from a lower level allocator (typically pub_tool_mallocfree.h).
  40 // Single elements are allocated from these pools.
  41 // Currently, elements can only be allocated, elements cannot be freed
  42 // individually.
  43 // Once allocated, an element must not be modified anymore.
  44 //
  45 // Elements can be inserted in the pool using VG_(allocEltDedupPA),
  46 // VG_(allocFixedEltDedupPA) or VG_(allocStrDedupPA).
  47 //
  48 // Use VG_(allocFixedEltDedupPA) to allocate elements that are all of
  49 // the same size and that you want to identify with a (small) number:
  50 // VG_(allocFixedEltDedupPA) will assign a sequence number to each
  51 // unique allocated element. This unique number can be translated to
  52 // an address when the element data must be used.
  53 // The idea is that such small numbers can be used as reference instead
  54 // of the element address, to spare memory.
  55 // Elements are numbered starting from 1. The nr 0 can thus be used
  56 // as 'null element'. The address identified by a nr can change
  57 // if new elements are inserted in the pool. Once the pool is frozen,
  58 // an element address does not change.
  59 //
  60 // Use VG_(allocEltDedupPA) for variable size elements or when the
  61 // memory needed to store the element reference is not critical or
  62 // when performance to access elements is critical.
  63 // The address of an element allocated with VG_(allocEltDedupPA) does
  64 // not change, even if new elements are inserted in the pool.
  65 //
  66 // Use VG_(allocStrDedupPA) to create a pool of strings (in other words, a
  67 //  dictionnary of strings). Similarly to VG_(allocFixedEltDedupPA), strings
  68 // inserted in a dedup pool can be identified by an element number.
  69 //
  70 // In the same pool, you can only use one of the allocate element functions.
  71 //
  72 // A dedup pool allocator has significantly less memory overhead than
  73 // calling directly pub_tool_mallocfree.h if the deduplication factor
  74 // is big. However, allocating an element incurs a cost for searching
  75 // if an identical element is already in the pool.
  76 //
  77 // Note: the elements of the pool cannot be freed (at least currently).
  78 // The only way to free the elements is to delete the dedup pool allocator.
  79 //--------------------------------------------------------------------
  80
  81
  82 typedef  struct _DedupPoolAlloc  DedupPoolAlloc;
  83
  84 /* Create new DedupPoolAlloc, using given allocation and free function.
  85    alloc_fn must not return NULL (that is, if it returns it must have
  86    succeeded.)
  87    poolSzB is the (minimum) size in bytes of the pool of elements allocated
  88    with alloc.
  89    eltAlign is the minimum required alignement for the elements allocated
  90    from the DedupPoolAlloc.
  91    This function never returns NULL. */
  92 extern DedupPoolAlloc* VG_(newDedupPA) ( SizeT  poolSzB,
  93                                          SizeT  eltAlign,
  94                                          Alloc_Fn_t alloc_fn,
  95                                          const  HChar* cc,
  96                                          Free_Fn_t free_fn );
  97
  98 /* Allocates or retrieve element from ddpa with eltSzB bytes to store elt.
  99    This function never returns NULL.
 100    If ddpa already contains an element equal to elt, then the address of
 101    the already existing element is returned.
 102    Equality between elements is done by comparing all bytes.
 103    So, if void *elt points to a struct, be sure to initialise all components
 104    and the holes between components. */
 105 extern const void* VG_(allocEltDedupPA) (DedupPoolAlloc* ddpa,
 106                                          SizeT eltSzB, const void* elt);
 107
 108 /* Allocates or retrieve a (fixed size) element from ddpa. Returns the
 109    unique number identifying this element.
 110    Similarly to VG_(allocEltDedupPA), this will return the unique number
 111    of an already existing identical element to elt. */
 112 extern UInt VG_(allocFixedEltDedupPA) (DedupPoolAlloc* ddpa,
 113                                        SizeT eltSzB, const void* elt);
 114
 115 /* Translate an element number to its address. Note that the address
 116    corresponding to eltNr can change if new elements are inserted
 117    in the pool. */
 118 extern void* VG_(indexEltNumber) (DedupPoolAlloc* ddpa,
 119                                   UInt eltNr);
 120
 121 /* Allocates or retrieve a string element from ddpa. Returns the
 122    unique number identifying this string.
 123    newStr is set to True if the str is a newly inserted string, False
 124    if the str was already present in the pool.
 125    Similarly to VG_(allocEltDedupPA), this will return the unique number
 126    of an already existing identical string. */
 127 extern UInt VG_(allocStrDedupPA) (DedupPoolAlloc *ddpa,
 128                                   const HChar* str,
 129                                   Bool* newStr);
 130 /* Note: Implementing a function to return the string value from its strNr
 131    implies some overhead, so will be done only if/when needed. */
 132
 133
 134 /* The Dedup Pool Allocator must maintain a data structure to avoid
 135    duplicates as long as new elements can be allocated from the pool.
 136    Once no new elements will be allocated, this dedup data structure
 137    can be released using VG_(freezeDedupPA). Once ddpa has been frozen,
 138    it is an error to call VG_(allocEltDedupPA) or VG_(allocFixedEltDedupPA).
 139    If shrink_block is not NULL, the last pool will be shrunk using
 140    shrink_block. */
 141 extern void VG_(freezeDedupPA) (DedupPoolAlloc* ddpa,
 142                                 void (*shrink_block)(void*, SizeT));
 143
 144 /* How many (unique) elements are there in this ddpa now? */
 145 extern UInt VG_(sizeDedupPA) (DedupPoolAlloc* ddpa);
 146
 147 /* Free all memory associated with a DedupPoolAlloc. */
 148 extern void VG_(deleteDedupPA) ( DedupPoolAlloc* ddpa);
 149
 150 #endif   // __PUB_TOOL_DEDUPPOOLALLOC_
 151
 152 /*--------------------------------------------------------------------*/
 153 /*--- end                               pub_tool_deduppoolalloc.h  ---*/
 154 /*--------------------------------------------------------------------*/