Add 'numbering identification' to the dedup pool.
The dedup pool can now be used to allocate elements and identify
them with a number rather than an address.
This new feature is not used (yet) but is intended to be used to
decrease the memory needed to store the CFSI information.
git-svn-id: svn://svn.valgrind.org/valgrind/trunk@14123 a5019735-40e9-0310-863c-91ae7b9d1cf9
diff --git a/coregrind/m_deduppoolalloc.c b/coregrind/m_deduppoolalloc.c
index bb77fa8..1d37924 100644
--- a/coregrind/m_deduppoolalloc.c
+++ b/coregrind/m_deduppoolalloc.c
@@ -40,12 +40,14 @@
struct _DedupPoolAlloc {
SizeT poolSzB; /* Minimum size of a pool. */
+ SizeT fixedSzb; /* If using VG_(allocFixedEltDedupPA), size of elements */
SizeT eltAlign;
void* (*alloc)(const HChar*, SizeT); /* pool allocator */
const HChar* cc; /* pool allocator's cc */
void (*free)(void*); /* pool allocator's free-er */
/* XArray of void* (pointers to pools). The pools themselves.
- Each element is a pointer to a block of size at least PoolSzB bytes. */
+ Each element is a pointer to a block of size at least PoolSzB bytes.
+ The last block might be smaller due to a call to shrink_block. */
XArray *pools;
/* hash table of pool elements, used to dedup.
@@ -56,12 +58,17 @@
decrease memory overhead during insertion in the DedupPoolAlloc. */
PoolAlloc *ht_node_pa;
- UChar *curpool_free; /* Pos in current pool to allocate next elt. */
+ UChar *curpool; /* last allocated pool. */
+ UChar *curpool_free; /* Pos in current pool to allocate next elt.
+ always aligned on eltAlign. */
UChar *curpool_limit; /* Last pos in current pool. */
+ /* Note that for a fixed size pool, we only have a single pool to allow
+ simple/fast indexing. This single pool is grown, which might change
+ the address of the already allocated elements. */
/* Total nr of alloc calls, resulting in (we hope) a lot less
real (dedup) elements. */
- ULong nr_alloc_calls;
+ ULong nr_alloc_calls;
};
typedef
@@ -90,6 +97,7 @@
vg_assert(ddpa);
VG_(memset)(ddpa, 0, sizeof(*ddpa));
ddpa->poolSzB = poolSzB;
+ ddpa->fixedSzb = 0;
ddpa->eltAlign = eltAlign;
ddpa->alloc = alloc;
ddpa->cc = cc;
@@ -102,7 +110,7 @@
alloc,
cc,
free_fn);
-
+ ddpa->curpool = NULL;
ddpa->curpool_limit = NULL;
ddpa->curpool_free = ddpa->curpool_limit + 1;
vg_assert(ddpa->pools);
@@ -113,7 +121,8 @@
{
Word i;
if (ddpa->ht_elements)
- VG_(freezeDedupPA) (ddpa, NULL); // Free data structures used for insertion.
+ // Free data structures used for insertion.
+ VG_(freezeDedupPA) (ddpa, NULL);
for (i = 0; i < VG_(sizeXA) (ddpa->pools); i++)
ddpa->free (*(UWord **)VG_(indexXA) ( ddpa->pools, i ));
VG_(deleteXA) (ddpa->pools);
@@ -121,22 +130,46 @@
}
static __inline__
-void ddpa_align_curpool_free ( DedupPoolAlloc* ddpa )
+UChar* ddpa_align ( DedupPoolAlloc* ddpa, UChar *c )
{
- ddpa->curpool_free = (UChar*)VG_ROUNDUP(ddpa->curpool_free, ddpa->eltAlign);
+ return (UChar*)VG_ROUNDUP(c, ddpa->eltAlign);
}
-/* No space. Allocate a new pool. */
+/* Allocate a new pool or grow the (only) pool for a fixed size ddpa. */
__attribute__((noinline))
-static void ddpa_add_new_pool ( DedupPoolAlloc* ddpa )
+static void ddpa_add_new_pool_or_grow ( DedupPoolAlloc* ddpa )
{
vg_assert(ddpa);
- ddpa->curpool_free = ddpa->alloc( ddpa->cc, ddpa->poolSzB);
- vg_assert(ddpa->curpool_free);
- ddpa->curpool_limit = ddpa->curpool_free + ddpa->poolSzB - 1;
- /* add to our collection of pools */
- VG_(addToXA)( ddpa->pools, &ddpa->curpool_free );
- ddpa_align_curpool_free (ddpa);
+
+ if (ddpa->fixedSzb > 0 && ddpa->curpool != NULL) {
+ // Grow (* 2) the current (fixed elt) pool
+ UChar *curpool_align = ddpa_align(ddpa, ddpa->curpool);
+ SizeT curpool_used = ddpa->curpool_free - curpool_align;
+ SizeT curpool_size = ddpa->curpool_limit - ddpa->curpool + 1;
+ UChar *newpool = ddpa->alloc (ddpa->cc, 2 * curpool_size);
+ UChar *newpool_free = ddpa_align (ddpa, newpool);
+ UChar *newpool_limit = newpool + 2 * curpool_size - 1;
+
+ vg_assert (newpool);
+ VG_(memcpy) (newpool_free, curpool_align, curpool_used);
+ newpool_free += curpool_used;
+
+ VG_(dropHeadXA) (ddpa->pools, 1);
+ ddpa->free (ddpa->curpool);
+ ddpa->curpool = newpool;
+ ddpa->curpool_free = newpool_free;
+ ddpa->curpool_limit = newpool_limit;
+ VG_(addToXA)( ddpa->pools, &ddpa->curpool);
+ } else {
+ /* Allocate a new pool, or allocate the first/only pool for a
+ fixed size ddpa. */
+ ddpa->curpool = ddpa->alloc( ddpa->cc, ddpa->poolSzB);
+ vg_assert(ddpa->curpool);
+ ddpa->curpool_limit = ddpa->curpool + ddpa->poolSzB - 1;
+ ddpa->curpool_free = ddpa_align (ddpa, ddpa->curpool);
+ /* add to our collection of pools */
+ VG_(addToXA)( ddpa->pools, &ddpa->curpool );
+ }
}
static Word cmp_pool_elt (const void* node1, const void* node2 )
@@ -183,12 +216,9 @@
&& (VG_(clo_verbosity) > 2 || VG_(debugLog_getLevel) () >= 2)) {
print_stats(ddpa);
}
- if (shrink_block && ddpa->curpool_limit > ddpa->curpool_free) {
- UChar *last_added_pool =
- (*(UChar **)VG_(indexXA) ( ddpa->pools,
- VG_(sizeXA)(ddpa->pools) - 1));
- (*shrink_block)(last_added_pool, ddpa->curpool_free - last_added_pool);
- }
+ vg_assert (!ddpa->fixedSzb || VG_(sizeXA) (ddpa->pools) == 1);
+ if (shrink_block && ddpa->curpool_limit > ddpa->curpool_free)
+ (*shrink_block)(ddpa->curpool, ddpa->curpool_free - ddpa->curpool);
VG_(HT_destruct) ( ddpa->ht_elements, htelem_dummyfree);
ddpa->ht_elements = NULL;
VG_(deletePA) (ddpa->ht_node_pa);
@@ -225,15 +255,14 @@
/* Not found -> we need to allocate a new element from the pool
and insert it in the hash table of inserted elements. */
- // Add a new pool if not enough space in the current pool
+ // Add a new pool or grow pool if not enough space in the current pool
if (UNLIKELY(ddpa->curpool_free + eltSzB - 1 > ddpa->curpool_limit)) {
- ddpa_add_new_pool(ddpa);
+ ddpa_add_new_pool_or_grow (ddpa);
}
elt_ins = ddpa->curpool_free;
VG_(memcpy)(elt_ins, elt, eltSzB);
- ddpa->curpool_free = ddpa->curpool_free + eltSzB;
- ddpa_align_curpool_free (ddpa);
+ ddpa->curpool_free = ddpa_align(ddpa, ddpa->curpool_free + eltSzB);
ht_ins = VG_(allocEltPA) (ddpa->ht_node_pa);
ht_ins->key = ht_elt.key;
@@ -242,3 +271,50 @@
VG_(HT_add_node)(ddpa->ht_elements, ht_ins);
return elt_ins;
}
+
+static __inline__
+UInt elt2nr (DedupPoolAlloc *ddpa, const void *dedup_elt)
+{
+ vg_assert ((UChar*)dedup_elt >= ddpa->curpool
+ && (UChar*)dedup_elt < ddpa->curpool_free);
+ return 1 + ((UChar*)dedup_elt - ddpa->curpool)
+ / VG_ROUNDUP(ddpa->fixedSzb, ddpa->eltAlign);
+}
+
+UInt VG_(allocFixedEltDedupPA) (DedupPoolAlloc *ddpa,
+ SizeT eltSzB, const void *elt)
+{
+ if (ddpa->fixedSzb == 0) {
+ // First insertion in this ddpa
+ vg_assert (ddpa->nr_alloc_calls == 0);
+ vg_assert (eltSzB > 0);
+ ddpa->fixedSzb = eltSzB;
+ }
+ vg_assert (ddpa->fixedSzb == eltSzB);
+ void *dedup_elt = VG_(allocEltDedupPA) (ddpa, eltSzB, elt);
+ return elt2nr (ddpa, dedup_elt);
+}
+
+void* VG_(indexEltNumber) (DedupPoolAlloc *ddpa,
+ UInt eltNr)
+{
+ void *dedup_elt;
+
+ dedup_elt = ddpa->curpool
+ + (eltNr - 1) * VG_ROUNDUP(ddpa->fixedSzb, ddpa->eltAlign);
+
+ vg_assert ((UChar*)dedup_elt >= ddpa->curpool
+ && (UChar*)dedup_elt < ddpa->curpool_free);
+
+ return dedup_elt;
+}
+
+UInt VG_(sizeDedupPA) (DedupPoolAlloc *ddpa)
+{
+ if (ddpa->curpool == NULL)
+ return 0;
+
+ vg_assert (ddpa->fixedSzb);
+ return (ddpa->curpool_free - ddpa_align(ddpa, ddpa->curpool))
+ / VG_ROUNDUP(ddpa->fixedSzb, ddpa->eltAlign);
+}
diff --git a/include/pub_tool_deduppoolalloc.h b/include/pub_tool_deduppoolalloc.h
index ac3a577..c048b77 100644
--- a/include/pub_tool_deduppoolalloc.h
+++ b/include/pub_tool_deduppoolalloc.h
@@ -35,7 +35,7 @@
//-----------------------------------------------------------------------------
// PURPOSE: Provides a pool allocator for elements, storing only once identical
-// elements. In other words, this can be considered a "dictionary" of elements.
+// elements. In other words, this can be considered a "dictionary" of elements.
//
// This pool allocator manages elements allocation by allocating "pools" of
// many elements from a lower level allocator (typically pub_tool_mallocfree.h).
@@ -43,6 +43,29 @@
// Currently, elements can only be allocated, elements cannot be freed
// individually.
// Once allocated, an element must not be modified anymore.
+//
+// Elements can be inserted in the pool using VG_(allocEltDedupPA)
+// or using VG_(allocFixedEltDedupPA).
+//
+// Use VG_(allocFixedEltDedupPA) to allocate elements that are all of
+// the same size and that you want to identify with a (small) number:
+// VG_(allocFixedEltDedupPA) will assign a sequence number to each
+// unique allocated element. This unique number can be translated to
+// an address when the element data must be used.
+// The idea is that such small numbers can be used as reference instead
+// of the element address, to spare memory.
+// Elements are numbered starting from 1. The nr 0 can thus be used
+// as 'null element'. The address identified by a nr can change
+// if new elements are inserted in the pool. Once the pool is frozen,
+// an element address does not change.
+//
+// Use VG_(allocEltDedupPA) for variable size elements or when the
+// memory needed to store the element reference is not critical or
+// when performance to access elements is critical.
+// The address of an element allocated with VG_(allocEltDedupPA) does
+// not change, even if new elements are inserted in the pool.
+//
+// In the same pool, you can only use one of the allocate element functions.
//
// A dedup pool allocator has significantly less memory overhead than
// calling directly pub_tool_mallocfree.h if the deduplication factor
@@ -50,7 +73,7 @@
// if an identical element is already in the pool.
//
// Note: the elements of the pool cannot be freed (at least currently).
-// The only way to free the elements is to delete the pool allocator.
+// The only way to free the elements is to delete the dedup pool allocator.
//--------------------------------------------------------------------
@@ -72,17 +95,30 @@
extern void* VG_(allocEltDedupPA) (DedupPoolAlloc *ddpa,
SizeT eltSzB, const void *elt);
+/* Allocates a new (fixed size) element from ddpa. Returns the
+ unique number identifying this element. */
+extern UInt VG_(allocFixedEltDedupPA) (DedupPoolAlloc *ddpa,
+ SizeT eltSzB, const void *elt);
+
+/* Translate an element number to its address. Note that the address
+ corresponding to eltNr can change if new elements are inserted
+ in the pool. */
+extern void* VG_(indexEltNumber) (DedupPoolAlloc *ddpa,
+ UInt eltNr);
/* The Dedup Pool Allocator must maintain a data structure to avoid
duplicates as long as new elements can be allocated from the pool.
Once no new elements will be allocated, this dedup data structure
can be released using VG_(freezeDedupPA). Once ddpa has been frozen,
- it is an error to call VG_(allocEltDedupPA).
+ it is an error to call VG_(allocEltDedupPA) or VG_(allocFixedEltDedupPA).
If shrink_block is not NULL, the last pool will be shrunk using
shrink_block. */
extern void VG_(freezeDedupPA) (DedupPoolAlloc *ddpa,
void (*shrink_block)(void*, SizeT));
+/* How many (unique) elements are there in this ddpa now? */
+extern UInt VG_(sizeDedupPA) (DedupPoolAlloc *ddpa);
+
/* Free all memory associated with a DedupPoolAlloc. */
extern void VG_(deleteDedupPA) ( DedupPoolAlloc *ddpa);
