|
From: <sv...@va...> - 2009-06-03 12:00:44
|
Author: bart
Date: 2009-06-03 13:00:30 +0100 (Wed, 03 Jun 2009)
New Revision: 10227
Log:
Reduced the number of memory allocations needed when DRD creates a new segment.
Modified:
branches/DRDDEV/coregrind/m_oset.c
branches/DRDDEV/drd/drd_bitmap.c
branches/DRDDEV/drd/drd_bitmap.h
branches/DRDDEV/drd/pub_drd_bitmap.h
branches/DRDDEV/include/pub_tool_oset.h
Modified: branches/DRDDEV/coregrind/m_oset.c
===================================================================
--- branches/DRDDEV/coregrind/m_oset.c 2009-06-03 10:22:11 UTC (rev 10226)
+++ branches/DRDDEV/coregrind/m_oset.c 2009-06-03 12:00:30 UTC (rev 10227)
@@ -103,26 +103,8 @@
Short magic;
};
-#define STACK_MAX 32 // At most 2**32 entries can be iterated over
#define OSET_MAGIC 0x5b1f
-// An OSet (AVL tree). If cmp is NULL, the key must be a UWord, and must
-// be the first word in the element. If cmp is set, arbitrary keys in
-// arbitrary positions can be used.
-struct _OSet {
- SizeT keyOff; // key offset
- OSetCmp_t cmp; // compare a key and an element, or NULL
- OSetAlloc_t alloc; // allocator
- HChar* cc; // cc for allocator
- OSetFree_t free; // deallocator
- Word nElems; // number of elements in the tree
- AvlNode* root; // root node
-
- AvlNode* nodeStack[STACK_MAX]; // Iterator node stack
- Int numStack[STACK_MAX]; // Iterator num stack
- Int stackTop; // Iterator stack pointer, one past end
-};
-
/*--------------------------------------------------------------------*/
/*--- Helper operations ---*/
/*--------------------------------------------------------------------*/
@@ -243,7 +225,7 @@
{
Int i;
vg_assert(t);
- for (i = 0; i < STACK_MAX; i++) {
+ for (i = 0; i < OSET_STACK_MAX; i++) {
t->nodeStack[i] = NULL;
t->numStack[i] = 0;
}
@@ -253,7 +235,7 @@
// Push onto the iterator stack.
static inline void stackPush(AvlTree* t, AvlNode* n, Int i)
{
- vg_assert(t->stackTop < STACK_MAX);
+ vg_assert(t->stackTop < OSET_STACK_MAX);
vg_assert(1 <= i && i <= 3);
t->nodeStack[t->stackTop] = n;
t-> numStack[t->stackTop] = i;
@@ -263,7 +245,7 @@
// Pop from the iterator stack.
static inline Bool stackPop(AvlTree* t, AvlNode** n, Int* i)
{
- vg_assert(t->stackTop <= STACK_MAX);
+ vg_assert(t->stackTop <= OSET_STACK_MAX);
if (t->stackTop > 0) {
t->stackTop--;
@@ -297,7 +279,14 @@
vg_assert(_free);
if (!_cmp) vg_assert(0 == _keyOff); // If no cmp, offset must be zero
- t = VG_(malloc)("oset", sizeof(AvlTree));
+ t = _alloc(_cc, sizeof(AvlTree));
+ return VG_(OSetGen_Initialize)(t, _keyOff, _cmp, _alloc, _cc, _free);
+}
+
+OSet* VG_(OSetGen_Initialize)(AvlTree* t, PtrdiffT _keyOff, OSetCmp_t _cmp,
+ OSetAlloc_t _alloc, HChar* _cc,
+ OSetFree_t _free)
+ {
t->keyOff = _keyOff;
t->cmp = _cmp;
t->alloc = _alloc;
@@ -316,8 +305,7 @@
return VG_(OSetGen_Create)(/*keyOff*/0, /*cmp*/NULL, _alloc, _cc, _free);
}
-// Destructor, frees up all memory held by remaining nodes.
-void VG_(OSetGen_Destroy)(AvlTree* t)
+void VG_(OSetGen_Cleanup)(AvlTree* t)
{
AvlNode* n = NULL;
Int i = 0;
@@ -347,9 +335,15 @@
}
}
vg_assert(sz == t->nElems);
+}
+// Destructor, frees up all memory held by remaining nodes.
+void VG_(OSetGen_Destroy)(AvlTree* t)
+{
+ VG_(OSetGen_Cleanup)(t);
+
/* Free the AvlTree itself. */
- VG_(free)(t);
+ t->free(t);
}
void VG_(OSetWord_Destroy)(AvlTree* t)
Modified: branches/DRDDEV/drd/drd_bitmap.c
===================================================================
--- branches/DRDDEV/drd/drd_bitmap.c 2009-06-03 10:22:11 UTC (rev 10226)
+++ branches/DRDDEV/drd/drd_bitmap.c 2009-06-03 12:00:30 UTC (rev 10227)
@@ -87,19 +87,19 @@
* match any valid address: the upper (ADDR_LSB_BITS + ADDR_IGNORED_BITS)
* bits of a1 are always zero for a valid cache entry.
*/
- for (i = 0; i < N_CACHE_ELEM; i++)
+ for (i = 0; i < DRD_BITMAP_N_CACHE_ELEM; i++)
{
bm->cache[i].a1 = ~(UWord)1;
bm->cache[i].bm2 = 0;
}
- bm->oset = VG_(OSetGen_Create)(0, 0, DRD_(bm2_alloc_node),
- "drd.bitmap.bn.2", DRD_(bm2_free_node));
+ VG_(OSetGen_Initialize)(&bm->oset, 0, 0, DRD_(bm2_alloc_node),
+ "drd.bitmap.bn.2", DRD_(bm2_free_node));
}
/** Free the memory allocated by DRD_(bm_init)(). */
void DRD_(bm_cleanup)(struct bitmap* const bm)
{
- VG_(OSetGen_Destroy)(bm->oset);
+ VG_(OSetGen_Cleanup)(&bm->oset);
}
/**
@@ -916,17 +916,17 @@
/* so complain if lhs == rhs. */
tl_assert(lhs != rhs);
- VG_(OSetGen_ResetIter)(lhs->oset);
- VG_(OSetGen_ResetIter)(rhs->oset);
+ VG_(OSetGen_ResetIter)(&lhs->oset);
+ VG_(OSetGen_ResetIter)(&rhs->oset);
- for ( ; (bm2l = VG_(OSetGen_Next)(lhs->oset)) != 0; )
+ for ( ; (bm2l = VG_(OSetGen_Next)(&lhs->oset)) != 0; )
{
while (bm2l
&& ! DRD_(bm_has_any_access)(lhs,
make_address(bm2l->addr, 0),
make_address(bm2l->addr + 1, 0)))
{
- bm2l = VG_(OSetGen_Next)(lhs->oset);
+ bm2l = VG_(OSetGen_Next)(&lhs->oset);
}
if (bm2l == 0)
break;
@@ -934,7 +934,7 @@
do
{
- bm2r = VG_(OSetGen_Next)(rhs->oset);
+ bm2r = VG_(OSetGen_Next)(&rhs->oset);
if (bm2r == 0)
return False;
}
@@ -957,7 +957,7 @@
do
{
- bm2r = VG_(OSetGen_Next)(rhs->oset);
+ bm2r = VG_(OSetGen_Next)(&rhs->oset);
} while (bm2r && ! DRD_(bm_has_any_access)(rhs,
make_address(bm2r->addr, 0),
make_address(bm2r->addr + 1, 0)));
@@ -973,7 +973,7 @@
void DRD_(bm_swap)(struct bitmap* const bm1, struct bitmap* const bm2)
{
- OSet* const tmp = bm1->oset;
+ OSet const tmp = bm1->oset;
bm1->oset = bm2->oset;
bm2->oset = tmp;
}
@@ -992,11 +992,11 @@
s_bitmap_merge_count++;
- VG_(OSetGen_ResetIter)(rhs->oset);
+ VG_(OSetGen_ResetIter)(&rhs->oset);
- for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; )
+ for ( ; (bm2r = VG_(OSetGen_Next)(&rhs->oset)) != 0; )
{
- bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr);
+ bm2l = VG_(OSetGen_Lookup)(&lhs->oset, &bm2r->addr);
if (bm2l)
{
tl_assert(bm2l != bm2r);
@@ -1014,8 +1014,8 @@
{
struct bitmap2* bm2;
- for (VG_(OSetGen_ResetIter)(bm->oset);
- (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0;
+ for (VG_(OSetGen_ResetIter)(&bm->oset);
+ (bm2 = VG_(OSetGen_Next)(&bm->oset)) != 0;
)
{
bm2->recalc = False;
@@ -1046,8 +1046,8 @@
struct bitmap2* bm2l;
struct bitmap2* bm2r;
- for (VG_(OSetGen_ResetIter)(bmr->oset);
- (bm2r = VG_(OSetGen_Next)(bmr->oset)) != 0;
+ for (VG_(OSetGen_ResetIter)(&bmr->oset);
+ (bm2r = VG_(OSetGen_Next)(&bmr->oset)) != 0;
)
{
/*if (DRD_(bm_has_any_access(bmr, make_address(bm2r->addr, 0),
@@ -1064,8 +1064,8 @@
{
struct bitmap2* bm2;
- for (VG_(OSetGen_ResetIter)(bm->oset);
- (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0;
+ for (VG_(OSetGen_ResetIter)(&bm->oset);
+ (bm2 = VG_(OSetGen_Next)(&bm->oset)) != 0;
)
{
if (bm2->recalc)
@@ -1089,11 +1089,11 @@
s_bitmap_merge_count++;
- VG_(OSetGen_ResetIter)(rhs->oset);
+ VG_(OSetGen_ResetIter)(&rhs->oset);
- for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; )
+ for ( ; (bm2r = VG_(OSetGen_Next)(&rhs->oset)) != 0; )
{
- bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr);
+ bm2l = VG_(OSetGen_Lookup)(&lhs->oset, &bm2r->addr);
if (bm2l && bm2l->recalc)
{
tl_assert(bm2l != bm2r);
@@ -1110,8 +1110,8 @@
*/
int DRD_(bm_has_races)(struct bitmap* const lhs, struct bitmap* const rhs)
{
- VG_(OSetGen_ResetIter)(lhs->oset);
- VG_(OSetGen_ResetIter)(rhs->oset);
+ VG_(OSetGen_ResetIter)(&lhs->oset);
+ VG_(OSetGen_ResetIter)(&rhs->oset);
for (;;)
{
@@ -1121,14 +1121,14 @@
const struct bitmap1* bm1r;
unsigned k;
- bm2l = VG_(OSetGen_Next)(lhs->oset);
- bm2r = VG_(OSetGen_Next)(rhs->oset);
+ bm2l = VG_(OSetGen_Next)(&lhs->oset);
+ bm2r = VG_(OSetGen_Next)(&rhs->oset);
while (bm2l && bm2r && bm2l->addr != bm2r->addr)
{
if (bm2l->addr < bm2r->addr)
- bm2l = VG_(OSetGen_Next)(lhs->oset);
+ bm2l = VG_(OSetGen_Next)(&lhs->oset);
else
- bm2r = VG_(OSetGen_Next)(rhs->oset);
+ bm2r = VG_(OSetGen_Next)(&rhs->oset);
}
if (bm2l == 0 || bm2r == 0)
break;
@@ -1161,8 +1161,8 @@
{
struct bitmap2* bm2;
- for (VG_(OSetGen_ResetIter)(bm->oset);
- (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0;
+ for (VG_(OSetGen_ResetIter)(&bm->oset);
+ (bm2 = VG_(OSetGen_Next)(&bm->oset)) != 0;
)
{
bm2_print(bm2);
Modified: branches/DRDDEV/drd/drd_bitmap.h
===================================================================
--- branches/DRDDEV/drd/drd_bitmap.h 2009-06-03 10:22:11 UTC (rev 10226)
+++ branches/DRDDEV/drd/drd_bitmap.h 2009-06-03 12:00:30 UTC (rev 10227)
@@ -380,24 +380,24 @@
tl_assert(bm2);
#endif
-#if N_CACHE_ELEM > 8
+#if DRD_BITMAP_N_CACHE_ELEM > 8
#error Please update the code below.
#endif
-#if N_CACHE_ELEM >= 1
+#if DRD_BITMAP_N_CACHE_ELEM >= 1
if (a1 == bm->cache[0].a1)
{
*bm2 = bm->cache[0].bm2;
return True;
}
#endif
-#if N_CACHE_ELEM >= 2
+#if DRD_BITMAP_N_CACHE_ELEM >= 2
if (a1 == bm->cache[1].a1)
{
*bm2 = bm->cache[1].bm2;
return True;
}
#endif
-#if N_CACHE_ELEM >= 3
+#if DRD_BITMAP_N_CACHE_ELEM >= 3
if (a1 == bm->cache[2].a1)
{
*bm2 = bm->cache[2].bm2;
@@ -405,7 +405,7 @@
return True;
}
#endif
-#if N_CACHE_ELEM >= 4
+#if DRD_BITMAP_N_CACHE_ELEM >= 4
if (a1 == bm->cache[3].a1)
{
*bm2 = bm->cache[3].bm2;
@@ -413,7 +413,7 @@
return True;
}
#endif
-#if N_CACHE_ELEM >= 5
+#if DRD_BITMAP_N_CACHE_ELEM >= 5
if (a1 == bm->cache[4].a1)
{
*bm2 = bm->cache[4].bm2;
@@ -421,7 +421,7 @@
return True;
}
#endif
-#if N_CACHE_ELEM >= 6
+#if DRD_BITMAP_N_CACHE_ELEM >= 6
if (a1 == bm->cache[5].a1)
{
*bm2 = bm->cache[5].bm2;
@@ -429,7 +429,7 @@
return True;
}
#endif
-#if N_CACHE_ELEM >= 7
+#if DRD_BITMAP_N_CACHE_ELEM >= 7
if (a1 == bm->cache[6].a1)
{
*bm2 = bm->cache[6].bm2;
@@ -437,7 +437,7 @@
return True;
}
#endif
-#if N_CACHE_ELEM >= 8
+#if DRD_BITMAP_N_CACHE_ELEM >= 8
if (a1 == bm->cache[7].a1)
{
*bm2 = bm->cache[7].bm2;
@@ -458,28 +458,28 @@
tl_assert(bm);
#endif
-#if N_CACHE_ELEM > 8
+#if DRD_BITMAP_N_CACHE_ELEM > 8
#error Please update the code below.
#endif
-#if N_CACHE_ELEM >= 8
+#if DRD_BITMAP_N_CACHE_ELEM >= 8
bm->cache[7] = bm->cache[6];
#endif
-#if N_CACHE_ELEM >= 7
+#if DRD_BITMAP_N_CACHE_ELEM >= 7
bm->cache[6] = bm->cache[5];
#endif
-#if N_CACHE_ELEM >= 6
+#if DRD_BITMAP_N_CACHE_ELEM >= 6
bm->cache[5] = bm->cache[4];
#endif
-#if N_CACHE_ELEM >= 5
+#if DRD_BITMAP_N_CACHE_ELEM >= 5
bm->cache[4] = bm->cache[3];
#endif
-#if N_CACHE_ELEM >= 4
+#if DRD_BITMAP_N_CACHE_ELEM >= 4
bm->cache[3] = bm->cache[2];
#endif
-#if N_CACHE_ELEM >= 3
+#if DRD_BITMAP_N_CACHE_ELEM >= 3
bm->cache[2] = bm->cache[1];
#endif
-#if N_CACHE_ELEM >= 2
+#if DRD_BITMAP_N_CACHE_ELEM >= 2
bm->cache[1] = bm->cache[0];
#endif
bm->cache[0].a1 = a1;
@@ -505,7 +505,7 @@
if (! bm_cache_lookup(bm, a1, &bm2))
{
- bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ bm2 = VG_(OSetGen_Lookup)(&bm->oset, &a1);
bm_update_cache(bm, a1, bm2);
}
return bm2;
@@ -530,7 +530,7 @@
if (! bm_cache_lookup(bm, a1, &bm2))
{
- bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ bm2 = VG_(OSetGen_Lookup)(&bm->oset, &a1);
}
return bm2;
@@ -555,9 +555,9 @@
s_bitmap2_creation_count++;
- bm2 = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2));
+ bm2 = VG_(OSetGen_AllocNode)(&bm->oset, sizeof(*bm2));
bm2->addr = a1;
- VG_(OSetGen_Insert)(bm->oset, bm2);
+ VG_(OSetGen_Insert)(&bm->oset, bm2);
bm_update_cache(bm, a1, bm2);
@@ -601,7 +601,7 @@
}
else
{
- bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ bm2 = VG_(OSetGen_Lookup)(&bm->oset, &a1);
if (! bm2)
{
bm2 = bm2_insert(bm, a1);
Modified: branches/DRDDEV/drd/pub_drd_bitmap.h
===================================================================
--- branches/DRDDEV/drd/pub_drd_bitmap.h 2009-06-03 10:22:11 UTC (rev 10226)
+++ branches/DRDDEV/drd/pub_drd_bitmap.h 2009-06-03 12:00:30 UTC (rev 10227)
@@ -34,8 +34,9 @@
#define __PUB_DRD_BITMAP_H
-#include "drd_basics.h" /* DRD_() */
+#include "drd_basics.h" /* DRD_() */
#include "pub_tool_basics.h" /* Addr, SizeT */
+#include "pub_tool_oset.h" /* struct _OSet */
/* Defines. */
@@ -63,13 +64,13 @@
struct bitmap2* bm2;
};
-#define N_CACHE_ELEM 4
+#define DRD_BITMAP_N_CACHE_ELEM 4
/* Complete bitmap. */
struct bitmap
{
- struct bm_cache_elem cache[N_CACHE_ELEM];
- struct _OSet* oset;
+ struct bm_cache_elem cache[DRD_BITMAP_N_CACHE_ELEM];
+ struct _OSet oset;
};
Modified: branches/DRDDEV/include/pub_tool_oset.h
===================================================================
--- branches/DRDDEV/include/pub_tool_oset.h 2009-06-03 10:22:11 UTC (rev 10226)
+++ branches/DRDDEV/include/pub_tool_oset.h 2009-06-03 12:00:30 UTC (rev 10227)
@@ -70,6 +70,8 @@
/*--- Types ---*/
/*--------------------------------------------------------------------*/
+#define OSET_STACK_MAX 32 // At most 2**32 entries can be iterated over
+
typedef struct _OSet OSet;
// - Cmp: returns -1, 0 or 1 if key is <, == or > elem.
@@ -80,6 +82,24 @@
typedef void* (*OSetAlloc_t) ( HChar* ec, SizeT szB );
typedef void (*OSetFree_t) ( void* p );
+// An OSet (AVL tree). If cmp is NULL, the key must be a UWord, and must
+// be the first word in the element. If cmp is set, arbitrary keys in
+// arbitrary positions can be used. Do not access the members of this
+// structure directly -- use the VG_(OSetGen_*)() functions instead.
+struct _OSet {
+ SizeT keyOff; // key offset
+ OSetCmp_t cmp; // compare a key and an element, or NULL
+ OSetAlloc_t alloc; // allocator
+ HChar* cc; // cc for allocator
+ OSetFree_t free; // deallocator
+ Word nElems; // number of elements in the tree
+ struct _OSetNode* root; // root node
+
+ struct _OSetNode* nodeStack[OSET_STACK_MAX]; // Iterator node stack
+ Int numStack[OSET_STACK_MAX]; // Iterator num stack
+ Int stackTop; // Iterator stack pointer, one past end
+};
+
/*--------------------------------------------------------------------*/
/*--- Creating and destroying OSets (UWord) ---*/
/*--------------------------------------------------------------------*/
@@ -171,6 +191,11 @@
// to allow the destruction of any attached resources; if NULL it is not
// called.
//
+// * Initialize: initialize allocated memory as an OSet.
+//
+// * Cleanup: frees all nodes in the table but not the memory used by the
+// table itself.
+//
// * AllocNode: Allocate and zero memory for a node to go into the OSet.
// Uses the alloc function given to VG_(OSetGen_Create)() to allocated a
// node which is big enough for both an element and the OSet metadata.
@@ -187,6 +212,10 @@
OSetAlloc_t alloc, HChar* ec,
OSetFree_t _free );
extern void VG_(OSetGen_Destroy) ( OSet* os );
+extern OSet* VG_(OSetGen_Initialize)( OSet* os, PtrdiffT keyOff, OSetCmp_t cmp,
+ OSetAlloc_t alloc, HChar* ec,
+ OSetFree_t _free );
+extern void VG_(OSetGen_Cleanup) ( OSet* os );
extern void* VG_(OSetGen_AllocNode) ( OSet* os, SizeT elemSize );
extern void VG_(OSetGen_FreeNode) ( OSet* os, void* elem );
|