philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 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 |
philippe | 1554fa5 | 2014-06-30 20:58:32 +0000 | [diff] [blame] | 38 | // elements. In other words, this can be considered a "dictionary" of elements. |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 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. |
philippe | 1554fa5 | 2014-06-30 20:58:32 +0000 | [diff] [blame] | 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. |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 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). |
philippe | 1554fa5 | 2014-06-30 20:58:32 +0000 | [diff] [blame] | 76 | // The only way to free the elements is to delete the dedup pool allocator. |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 77 | //-------------------------------------------------------------------- |
| 78 | |
| 79 | |
| 80 | typedef struct _DedupPoolAlloc DedupPoolAlloc; |
| 81 | |
| 82 | /* Create new DedupPoolAlloc, using given allocation and free function. |
florian | 5e1e923 | 2014-09-15 07:21:36 +0000 | [diff] [blame] | 83 | alloc_fn must not return NULL (that is, if it returns it must have |
| 84 | succeeded.) |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 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 |
florian | 5e1e923 | 2014-09-15 07:21:36 +0000 | [diff] [blame] | 88 | from the DedupPoolAlloc. |
| 89 | This function never returns NULL. */ |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 90 | extern DedupPoolAlloc* VG_(newDedupPA) ( SizeT poolSzB, |
philippe | 0b9d064 | 2014-06-30 19:47:24 +0000 | [diff] [blame] | 91 | SizeT eltAlign, |
| 92 | void* (*alloc)(const HChar*, SizeT), |
| 93 | const HChar* cc, |
| 94 | void (*free_fn)(void*) ); |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 95 | |
florian | 5e1e923 | 2014-09-15 07:21:36 +0000 | [diff] [blame] | 96 | /* Allocates a new element from ddpa with eltSzB bytes to store elt. |
| 97 | This function never returns NULL. */ |
florian | 1ef70c6 | 2014-10-22 17:42:37 +0000 | [diff] [blame^] | 98 | extern const void* VG_(allocEltDedupPA) (DedupPoolAlloc *ddpa, |
| 99 | SizeT eltSzB, const void *elt); |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 100 | |
philippe | 1554fa5 | 2014-06-30 20:58:32 +0000 | [diff] [blame] | 101 | /* Allocates a new (fixed size) element from ddpa. Returns the |
florian | 5e1e923 | 2014-09-15 07:21:36 +0000 | [diff] [blame] | 102 | unique number identifying this element. This function never returns NULL. */ |
philippe | 1554fa5 | 2014-06-30 20:58:32 +0000 | [diff] [blame] | 103 | extern UInt VG_(allocFixedEltDedupPA) (DedupPoolAlloc *ddpa, |
| 104 | SizeT eltSzB, const void *elt); |
| 105 | |
| 106 | /* Translate an element number to its address. Note that the address |
| 107 | corresponding to eltNr can change if new elements are inserted |
| 108 | in the pool. */ |
| 109 | extern void* VG_(indexEltNumber) (DedupPoolAlloc *ddpa, |
| 110 | UInt eltNr); |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 111 | |
| 112 | /* The Dedup Pool Allocator must maintain a data structure to avoid |
| 113 | duplicates as long as new elements can be allocated from the pool. |
| 114 | Once no new elements will be allocated, this dedup data structure |
| 115 | can be released using VG_(freezeDedupPA). Once ddpa has been frozen, |
philippe | 1554fa5 | 2014-06-30 20:58:32 +0000 | [diff] [blame] | 116 | it is an error to call VG_(allocEltDedupPA) or VG_(allocFixedEltDedupPA). |
philippe | 0b9d064 | 2014-06-30 19:47:24 +0000 | [diff] [blame] | 117 | If shrink_block is not NULL, the last pool will be shrunk using |
| 118 | shrink_block. */ |
| 119 | extern void VG_(freezeDedupPA) (DedupPoolAlloc *ddpa, |
| 120 | void (*shrink_block)(void*, SizeT)); |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 121 | |
philippe | 1554fa5 | 2014-06-30 20:58:32 +0000 | [diff] [blame] | 122 | /* How many (unique) elements are there in this ddpa now? */ |
| 123 | extern UInt VG_(sizeDedupPA) (DedupPoolAlloc *ddpa); |
| 124 | |
philippe | 7293d25 | 2014-06-14 16:30:09 +0000 | [diff] [blame] | 125 | /* Free all memory associated with a DedupPoolAlloc. */ |
| 126 | extern void VG_(deleteDedupPA) ( DedupPoolAlloc *ddpa); |
| 127 | |
| 128 | #endif // __PUB_TOOL_DEDUPPOOLALLOC_ |
| 129 | |
| 130 | /*--------------------------------------------------------------------*/ |
| 131 | /*--- end pub_tool_deduppoolalloc.h ---*/ |
| 132 | /*--------------------------------------------------------------------*/ |