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-2014 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 // or using VG_(allocFixedEltDedupPA).
  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 // In the same pool, you can only use one of the allocate element functions.
  69 //
  70 // A dedup pool allocator has significantly less memory overhead than
  71 // calling directly pub_tool_mallocfree.h if the deduplication factor
  72 // is big. However, allocating an element incurs a cost for searching
  73 // if an identical element is already in the pool.
  74 //
  75 // Note: the elements of the pool cannot be freed (at least currently).
  76 // The only way to free the elements is to delete the dedup pool allocator.
  77 //--------------------------------------------------------------------
  78
  79
  80 typedef  struct _DedupPoolAlloc  DedupPoolAlloc;
  81
  82 /* Create new DedupPoolAlloc, using given allocation and free function.
  83    alloc_fn must not return NULL (that is, if it returns it must have
  84    succeeded.)
  85    poolSzB is the (minimum) size in bytes of the pool of elements allocated
  86    with alloc.
  87    eltAlign is the minimum required alignement for the elements allocated
  88    from the DedupPoolAlloc.
  89    This function never returns NULL. */
  90 extern DedupPoolAlloc* VG_(newDedupPA) ( SizeT  poolSzB,
  91                                          SizeT  eltAlign,
  92                                          void*  (*alloc)(const HChar*, SizeT),
  93                                          const  HChar* cc,
  94                                          void   (*free_fn)(void*) );
  95
  96 /* Allocates a new element from ddpa with eltSzB bytes to store elt.
  97    This function never returns NULL.
  98    If ddpa already contains an element equal to elt, then the address of
  99    the already existing element is returned.
 100    Equality between elements is done by comparing all bytes.
 101    So, if void *elt points to a struct, be sure to initialise all components
 102    and the holes between components. */
 103 extern const void* VG_(allocEltDedupPA) (DedupPoolAlloc *ddpa,
 104                                          SizeT eltSzB, const void *elt);
 105
 106 /* Allocates a new (fixed size) element from ddpa. Returns the
 107    unique number identifying this element. This function never returns NULL.
 108    Similarly to VG_(allocEltDedupPA), this will return the unique number
 109    of an already existing identical element to elt. */
 110 extern UInt VG_(allocFixedEltDedupPA) (DedupPoolAlloc *ddpa,
 111                                        SizeT eltSzB, const void *elt);
 112
 113 /* Translate an element number to its address. Note that the address
 114    corresponding to eltNr can change if new elements are inserted
 115    in the pool. */
 116 extern void* VG_(indexEltNumber) (DedupPoolAlloc *ddpa,
 117                                   UInt eltNr);
 118
 119 /* The Dedup Pool Allocator must maintain a data structure to avoid
 120    duplicates as long as new elements can be allocated from the pool.
 121    Once no new elements will be allocated, this dedup data structure
 122    can be released using VG_(freezeDedupPA). Once ddpa has been frozen,
 123    it is an error to call VG_(allocEltDedupPA) or VG_(allocFixedEltDedupPA).
 124    If shrink_block is not NULL, the last pool will be shrunk using
 125    shrink_block. */
 126 extern void VG_(freezeDedupPA) (DedupPoolAlloc *ddpa,
 127                                 void (*shrink_block)(void*, SizeT));
 128
 129 /* How many (unique) elements are there in this ddpa now? */
 130 extern UInt VG_(sizeDedupPA) (DedupPoolAlloc *ddpa);
 131
 132 /* Free all memory associated with a DedupPoolAlloc. */
 133 extern void VG_(deleteDedupPA) ( DedupPoolAlloc *ddpa);
 134
 135 #endif   // __PUB_TOOL_DEDUPPOOLALLOC_
 136
 137 /*--------------------------------------------------------------------*/
 138 /*--- end                               pub_tool_deduppoolalloc.h  ---*/
 139 /*--------------------------------------------------------------------*/