|
From: <sv...@va...> - 2008-03-24 06:41:24
|
Author: bart
Date: 2008-03-24 06:41:30 +0000 (Mon, 24 Mar 2008)
New Revision: 7768
Log:
Extended bitmap lookup cache from one to four elements.
Modified:
trunk/exp-drd/drd_bitmap.c
trunk/exp-drd/drd_bitmap.h
trunk/exp-drd/pub_drd_bitmap.h
Modified: trunk/exp-drd/drd_bitmap.c
===================================================================
--- trunk/exp-drd/drd_bitmap.c 2008-03-24 06:38:39 UTC (rev 7767)
+++ trunk/exp-drd/drd_bitmap.c 2008-03-24 06:41:30 UTC (rev 7768)
@@ -51,6 +51,7 @@
struct bitmap* bm_new()
{
+ unsigned i;
struct bitmap* bm;
// If this assert fails, fix the definition of BITS_PER_BITS_PER_UWORD
@@ -59,8 +60,11 @@
bm = VG_(malloc)(sizeof(*bm));
tl_assert(bm);
- bm->last_lookup_a1 = 0;
- bm->last_lookup_result = 0;
+ 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, VG_(malloc), VG_(free));
s_bitmap_creation_count++;
@@ -743,6 +747,8 @@
{
unsigned k;
+ tl_assert(bm2l);
+ tl_assert(bm2r);
tl_assert(bm2l->addr == bm2r->addr);
for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
@@ -764,7 +770,7 @@
{ 0 + ADDR0_COUNT, 1, eLoad },
{ 666 + ADDR0_COUNT, 4, eLoad },
{ 667 + ADDR0_COUNT, 2, eStore },
- { -1 + 2*ADDR0_COUNT, 1, eStore },
+ { -2 + 2*ADDR0_COUNT, 1, eStore },
{ 0x0001ffffUL, 1, eLoad },
{ 0x0002ffffUL, 1, eLoad },
{ 0x00ffffffUL, 1, eLoad },
Modified: trunk/exp-drd/drd_bitmap.h
===================================================================
--- trunk/exp-drd/drd_bitmap.h 2008-03-24 06:38:39 UTC (rev 7767)
+++ trunk/exp-drd/drd_bitmap.h 2008-03-24 06:41:30 UTC (rev 7768)
@@ -23,8 +23,8 @@
*/
-#ifndef __DRD_BITMAP3_H
-#define __DRD_BITMAP3_H
+#ifndef __DRD_BITMAP_H
+#define __DRD_BITMAP_H
#include "pub_tool_oset.h"
@@ -75,7 +75,7 @@
#define UWORD_HIGHEST_ADDRESS(a) ((a) | (BITS_PER_UWORD - 1))
-/* Local constants. */
+/* Local variables. */
static ULong s_bitmap2_creation_count;
@@ -151,20 +151,107 @@
/*********************************************************************/
+/* Second level bitmap. */
struct bitmap2
{
- Addr addr; ///< address >> ADDR0_BITS
+ Addr addr; ///< address >> ADDR0_BITS
struct bitmap1 bm1;
};
+struct bm_cache_elem
+{
+ Addr a1;
+ struct bitmap2* bm2;
+};
+
+#define N_CACHE_ELEM 4
+
/* Complete bitmap. */
struct bitmap
{
- Addr last_lookup_a1;
- struct bitmap2* last_lookup_result;
- OSet* oset;
+ struct bm_cache_elem cache[N_CACHE_ELEM];
+ OSet* oset;
};
+
+static __inline__
+struct bitmap2* bm_cache_lookup(const struct bitmap* const bm, const UWord a1)
+{
+ tl_assert(bm);
+
+#if N_CACHE_ELEM > 8
+#error Please update the code below.
+#endif
+#if N_CACHE_ELEM >= 1
+ if (a1 == bm->cache[0].a1)
+ return bm->cache[0].bm2;
+#endif
+#if N_CACHE_ELEM >= 2
+ if (a1 == bm->cache[1].a1)
+ return bm->cache[1].bm2;
+#endif
+#if N_CACHE_ELEM >= 3
+ if (a1 == bm->cache[2].a1)
+ return bm->cache[2].bm2;
+#endif
+#if N_CACHE_ELEM >= 4
+ if (a1 == bm->cache[3].a1)
+ return bm->cache[3].bm2;
+#endif
+#if N_CACHE_ELEM >= 5
+ if (a1 == bm->cache[4].a1)
+ return bm->cache[4].bm2;
+#endif
+#if N_CACHE_ELEM >= 6
+ if (a1 == bm->cache[5].a1)
+ return bm->cache[5].bm2;
+#endif
+#if N_CACHE_ELEM >= 7
+ if (a1 == bm->cache[6].a1)
+ return bm->cache[6].bm2;
+#endif
+#if N_CACHE_ELEM >= 8
+ if (a1 == bm->cache[7].a1)
+ return bm->cache[7].bm2;
+#endif
+ return 0;
+}
+
+static __inline__
+void bm_update_cache(struct bitmap* const bm,
+ const UWord a1,
+ struct bitmap2* const bm2)
+{
+ tl_assert(bm);
+
+#if N_CACHE_ELEM > 8
+#error Please update the code below.
+#endif
+#if N_CACHE_ELEM >= 8
+ bm->cache[7] = bm->cache[6];
+#endif
+#if N_CACHE_ELEM >= 7
+ bm->cache[6] = bm->cache[5];
+#endif
+#if N_CACHE_ELEM >= 6
+ bm->cache[5] = bm->cache[4];
+#endif
+#if N_CACHE_ELEM >= 5
+ bm->cache[4] = bm->cache[3];
+#endif
+#if N_CACHE_ELEM >= 4
+ bm->cache[3] = bm->cache[2];
+#endif
+#if N_CACHE_ELEM >= 3
+ bm->cache[2] = bm->cache[1];
+#endif
+#if N_CACHE_ELEM >= 2
+ bm->cache[1] = bm->cache[0];
+#endif
+ bm->cache[0].a1 = a1;
+ bm->cache[0].bm2 = bm2;
+}
+
/** Look up the address a1 in bitmap bm.
* @param a1 client address shifted right by ADDR0_BITS.
* @param bm bitmap pointer.
@@ -172,30 +259,30 @@
static __inline__
struct bitmap2* bm2_lookup(const struct bitmap* const bm, const UWord a1)
{
- struct bitmap2* result;
- if (a1 == bm->last_lookup_a1)
+ struct bitmap2* bm2;
+ bm2 = bm_cache_lookup(bm, a1);
+ if (bm2 == 0)
{
- return bm->last_lookup_result;
+ bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ if (bm2)
+ {
+ bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
+ }
}
- result = VG_(OSetGen_Lookup)(bm->oset, &a1);
- if (result)
- {
- ((struct bitmap*)bm)->last_lookup_a1 = a1;
- ((struct bitmap*)bm)->last_lookup_result = result;
- }
- return result;
+ return bm2;
}
static __inline__
struct bitmap2* bm2_insert(const struct bitmap* const bm, const UWord a1)
{
- struct bitmap2* const bm2 = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2));
+ struct bitmap2* bm2;
+
+ bm2 = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2));
bm2->addr = a1;
VG_(memset)(&bm2->bm1, 0, sizeof(bm2->bm1));
VG_(OSetGen_Insert)(bm->oset, bm2);
- ((struct bitmap*)bm)->last_lookup_a1 = a1;
- ((struct bitmap*)bm)->last_lookup_result = bm2;
+ bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
s_bitmap2_creation_count++;
@@ -213,20 +300,18 @@
{
struct bitmap2* bm2;
- if (a1 == bm->last_lookup_a1)
- {
- return bm->last_lookup_result;
- }
-
- bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ bm2 = bm_cache_lookup(bm, a1);
if (bm2 == 0)
{
- bm2 = bm2_insert(bm, a1);
+ bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ if (bm2 == 0)
+ {
+ bm2 = bm2_insert(bm, a1);
+ }
+ bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
}
- ((struct bitmap*)bm)->last_lookup_a1 = a1;
- ((struct bitmap*)bm)->last_lookup_result = bm2;
return bm2;
}
-#endif /* __DRD_BITMAP3_H */
+#endif /* __DRD_BITMAP_H */
Modified: trunk/exp-drd/pub_drd_bitmap.h
===================================================================
--- trunk/exp-drd/pub_drd_bitmap.h 2008-03-24 06:38:39 UTC (rev 7767)
+++ trunk/exp-drd/pub_drd_bitmap.h 2008-03-24 06:41:30 UTC (rev 7768)
@@ -28,8 +28,8 @@
// segment.
-#ifndef __DRD_BITMAP_H
-#define __DRD_BITMAP_H
+#ifndef __PUB_DRD_BITMAP_H
+#define __PUB_DRD_BITMAP_H
#include "pub_tool_basics.h" /* Addr, SizeT */
@@ -107,6 +107,7 @@
void bm_print(const struct bitmap* bm);
ULong bm_get_bitmap_creation_count(void);
ULong bm_get_bitmap2_creation_count(void);
+void bm_test(void);
-#endif /* __DRD_BITMAP_H */
+#endif /* __PUB_DRD_BITMAP_H */
|