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 /*--------------------------------------------------------------------*/ 140