|
From: <sv...@va...> - 2008-03-23 17:13:25
|
Author: bart
Date: 2008-03-23 17:13:30 +0000 (Sun, 23 Mar 2008)
New Revision: 7764
Log:
Extended bitmap lookup cache from one to two elements.
Modified:
branches/DRDDEV/exp-drd/drd_bitmap.c
branches/DRDDEV/exp-drd/drd_bitmap.h
Modified: branches/DRDDEV/exp-drd/drd_bitmap.c
===================================================================
--- branches/DRDDEV/exp-drd/drd_bitmap.c 2008-03-23 16:15:43 UTC (rev 7763)
+++ branches/DRDDEV/exp-drd/drd_bitmap.c 2008-03-23 17:13:30 UTC (rev 7764)
@@ -58,6 +58,7 @@
struct bitmap* bm_new()
{
+ unsigned i;
struct bitmap* bm;
// If this assert fails, fix the definition of BITS_PER_BITS_PER_UWORD
@@ -66,10 +67,12 @@
bm = VG_(malloc)(sizeof(*bm));
tl_assert(bm);
- bm->last_lookup_a1 = 0;
- bm->last_lookup_bm2ref = 0;
- bm->last_lookup_bm2 = 0;
- bm->oset = VG_(OSetGen_Create)(0, 0, bm2ref_new, bm2ref_del);
+ for (i = 0; i < N_CACHE_ELEM; i++)
+ {
+ bm->cache[i].a1 = 0;
+ bm->cache[i].bm2 = 0;
+ }
+ bm->oset = VG_(OSetGen_Create)(0, 0, bm2ref_new, bm2ref_del);
s_bitmap_creation_count++;
@@ -427,6 +430,9 @@
if (p2)
{
Addr c = b;
+ /* If the first address in the bitmap that must be cleared does not */
+ /* start on an UWord boundary, start clearing the first addresses */
+ /* by calling bm1_clear(). */
if (UWORD_LSB(c))
{
Addr c_next = UWORD_MSB(c) + BITS_PER_UWORD;
@@ -435,6 +441,7 @@
bm1_clear(&p2->bm1, c, c_next);
c = c_next;
}
+ /* If some UWords have to be cleared entirely, do this now. */
if (UWORD_LSB(c) == 0)
{
const Addr c_next = UWORD_MSB(b_next);
@@ -450,6 +457,9 @@
c = c_next;
}
}
+ /* If the last address in the bitmap that must be cleared does not */
+ /* fall on an UWord boundary, clear the last addresses by calling */
+ /* bm1_clear(). */
if (c != b_next)
{
bm1_clear(&p2->bm1, c, b_next);
@@ -833,9 +843,7 @@
VG_(memcpy)(&bm2_copy->bm1, &bm2->bm1, sizeof(bm2->bm1));
bm2ref->bm2 = bm2_copy;
- bm->last_lookup_a1 = a1;
- bm->last_lookup_bm2ref = bm2ref;
- bm->last_lookup_bm2 = bm2_copy;
+ bm_update_cache(bm, a1, bm2_copy);
return bm2_copy;
}
Modified: branches/DRDDEV/exp-drd/drd_bitmap.h
===================================================================
--- branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 16:15:43 UTC (rev 7763)
+++ branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 17:13:30 UTC (rev 7764)
@@ -166,13 +166,19 @@
struct bitmap2* bm2;
};
+struct bm_cache_elem
+{
+ Addr a1;
+ struct bitmap2* bm2;
+};
+
+#define N_CACHE_ELEM 2
+
/* Complete bitmap. */
struct bitmap
{
- Addr last_lookup_a1;
- struct bitmap2ref* last_lookup_bm2ref;
- struct bitmap2* last_lookup_bm2;
- OSet* oset;
+ struct bm_cache_elem cache[N_CACHE_ELEM];
+ OSet* oset;
};
@@ -189,18 +195,32 @@
static __inline__
int bm_check(const struct bitmap* const bm)
{
+ struct bitmap2_ref* bm2ref;
+
tl_assert(bm);
- return (bm->last_lookup_a1 == 0
- || (VG_(OSetGen_Lookup)(bm->oset, &bm->last_lookup_a1)
- == bm->last_lookup_bm2ref
- && bm->last_lookup_bm2ref->bm2
- && bm->last_lookup_a1 == bm->last_lookup_bm2ref->bm2->addr
- && bm->last_lookup_bm2ref->bm2->refcnt >= 1)
+ return (bm->cache[0].a1 == 0
+ && bm->cache[1].a1 == 0
+ || ((bm2ref = VG_(OSetGen_Lookup)(bm->oset, &bm->last_lookup_a1))
+ && bm2ref->bm2
+ && bm->last_lookup_a1 == bm2ref->bm2->addr
+ && bm2ref->bm2->refcnt >= 1)
);
}
#endif
+static __inline__
+void bm_update_cache(struct bitmap* const bm,
+ const UWord a1,
+ struct bitmap2* const bm2)
+{
+ tl_assert(bm);
+
+ bm->cache[1] = bm->cache[0];
+ bm->cache[0].a1 = a1;
+ bm->cache[0].bm2 = bm2;
+}
+
/** Look up the address a1 in bitmap bm and return a pointer to a potentially
* shared second level bitmap. The bitmap where the returned pointer points
* at may not be modified by the caller.
@@ -214,17 +234,19 @@
struct bitmap2ref* bm2ref;
tl_assert(bm);
- if (a1 == bm->last_lookup_a1)
+ if (a1 == bm->cache[0].a1)
{
- return bm->last_lookup_bm2;
+ return bm->cache[0].bm2;
}
+ if (a1 == bm->cache[1].a1)
+ {
+ return bm->cache[1].bm2;
+ }
bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
if (bm2ref)
{
struct bitmap2* const bm2 = bm2ref->bm2;
- ((struct bitmap*)bm)->last_lookup_a1 = a1;
- ((struct bitmap*)bm)->last_lookup_bm2ref = bm2ref;
- ((struct bitmap*)bm)->last_lookup_bm2 = bm2;
+ bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
return bm2;
}
return 0;
@@ -243,16 +265,21 @@
struct bitmap2ref* bm2ref;
struct bitmap2* bm2;
- if (bm->last_lookup_a1 == a1)
+ bm2ref = 0;
+ if (bm->cache[0].a1 == a1)
{
- if (bm->last_lookup_bm2->refcnt == 1)
+ bm2 = bm->cache[0].bm2;
+ if (bm2->refcnt > 1)
{
- return bm->last_lookup_bm2;
+ bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
}
- else
+ }
+ else if (bm->cache[1].a1 == a1)
+ {
+ bm2 = bm->cache[1].bm2;
+ if (bm2->refcnt > 1)
{
- bm2 = bm2_make_exclusive((struct bitmap*)bm, bm->last_lookup_bm2ref);
- return bm2;
+ bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
}
}
else
@@ -261,14 +288,22 @@
if (bm2ref)
{
bm2 = bm2ref->bm2;
- if (bm2->refcnt > 1)
- {
- bm2 = bm2_make_exclusive((struct bitmap*)bm, bm2ref);
- }
- return bm2;
}
+ else
+ {
+ return 0;
+ }
}
- return 0;
+
+ tl_assert(bm2);
+
+ if (bm2->refcnt > 1)
+ {
+ tl_assert(bm2ref);
+ bm2 = bm2_make_exclusive(*(struct bitmap**)&bm, bm2ref);
+ }
+
+ return bm2;
}
/** Look up the address a1 in bitmap bm. The returned second level bitmap has
@@ -290,9 +325,7 @@
VG_(memset)(&bm2->bm1, 0, sizeof(bm2->bm1));
VG_(OSetGen_Insert)(bm->oset, bm2ref);
- ((struct bitmap*)bm)->last_lookup_a1 = a1;
- ((struct bitmap*)bm)->last_lookup_bm2ref = bm2ref;
- ((struct bitmap*)bm)->last_lookup_bm2 = bm2;
+ bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
return bm2;
}
@@ -307,16 +340,14 @@
struct bitmap2ref* bm2ref;
tl_assert(bm);
- tl_assert(VG_(OSetGen_Lookup)(bm->oset, &bm2->addr) == 0);
+ //tl_assert(VG_(OSetGen_Lookup)(bm->oset, &bm2->addr) == 0);
bm2ref = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2ref));
bm2ref->addr = bm2->addr;
bm2ref->bm2 = bm2;
bm2->refcnt++;
VG_(OSetGen_Insert)(bm->oset, bm2ref);
- ((struct bitmap*)bm)->last_lookup_a1 = bm2->addr;
- ((struct bitmap*)bm)->last_lookup_bm2ref = bm2ref;
- ((struct bitmap*)bm)->last_lookup_bm2 = bm2;
+ bm_update_cache(*(struct bitmap**)&bm, bm2->addr, bm2);
return bm2;
}
@@ -336,22 +367,26 @@
tl_assert(bm);
tl_assert(a1);
- if (a1 == bm->last_lookup_a1)
+ if (a1 == bm->cache[0].a1)
{
- return bm->last_lookup_bm2;
+ bm2 = bm->cache[0].bm2;
}
-
- bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
- if (bm2ref == 0)
+ else if (a1 == bm->cache[1].a1)
{
- bm2 = bm2_insert(bm, a1);
+ bm2 = bm->cache[1].bm2;
}
else
{
- bm2 = bm2ref->bm2;
- ((struct bitmap*)bm)->last_lookup_a1 = a1;
- ((struct bitmap*)bm)->last_lookup_bm2ref = bm2ref;
- ((struct bitmap*)bm)->last_lookup_bm2 = bm2;
+ bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ if (bm2ref)
+ {
+ bm2 = bm2ref->bm2;
+ }
+ else
+ {
+ bm2 = bm2_insert(bm, a1);
+ }
+ bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
}
return bm2;
}
|