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