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