|
From: <sv...@va...> - 2008-07-13 07:52:05
|
Author: bart
Date: 2008-07-13 08:52:10 +0100 (Sun, 13 Jul 2008)
New Revision: 8428
Log:
Added support for computed bitmaps.
Modified:
branches/DRDDEV/drd/drd_bitmap.c
branches/DRDDEV/drd/drd_bitmap.h
branches/DRDDEV/drd/drd_thread.c
branches/DRDDEV/drd/pub_drd_bitmap.h
Modified: branches/DRDDEV/drd/drd_bitmap.c
===================================================================
--- branches/DRDDEV/drd/drd_bitmap.c 2008-07-13 07:51:30 UTC (rev 8427)
+++ branches/DRDDEV/drd/drd_bitmap.c 2008-07-13 07:52:10 UTC (rev 8428)
@@ -54,8 +54,19 @@
/* Function definitions. */
-struct bitmap* bm_new()
+/** Allocate and initialize a new bitmap structure. */
+struct bitmap* bm_new(void)
{
+ return bm_new_cb(0);
+}
+
+/** Allocate and initialize a new bitmap structure.
+ *
+ * @param compute_bitmap2 Callback function for computing the actual bitmap
+ * data.
+ */
+struct bitmap* bm_new_cb(struct bitmap2* (*compute_bitmap2)(UWord))
+{
unsigned i;
struct bitmap* bm;
@@ -74,6 +85,7 @@
bm->cache[i].bm2 = 0;
}
bm->oset = VG_(OSetGen_Create)(0, 0, VG_(malloc), VG_(free));
+ bm->compute_bitmap2 = compute_bitmap2;
s_bitmap_creation_count++;
@@ -91,10 +103,13 @@
for ( ; (bm2ref = VG_(OSetGen_Next)(bm->oset)) != 0; )
{
bm2 = bm2ref->bm2;
- tl_assert(bm2->refcnt >= 1);
- if (--bm2->refcnt == 0)
+ if (bm2)
{
- VG_(free)(bm2);
+ tl_assert(bm2->refcnt >= 1);
+ if (--bm2->refcnt == 0)
+ {
+ VG_(free)(bm2);
+ }
}
}
Modified: branches/DRDDEV/drd/drd_bitmap.h
===================================================================
--- branches/DRDDEV/drd/drd_bitmap.h 2008-07-13 07:51:30 UTC (rev 8427)
+++ branches/DRDDEV/drd/drd_bitmap.h 2008-07-13 07:52:10 UTC (rev 8428)
@@ -305,13 +305,20 @@
{
struct bm_cache_elem cache[N_CACHE_ELEM];
OSet* oset;
+ struct bitmap2* (*compute_bitmap2)(const UWord a1);
};
static struct bitmap2* bm2_new(const UWord a1);
static struct bitmap2* bm2_make_exclusive(struct bitmap* const bm,
struct bitmap2ref* const bm2ref);
+static __inline__
+void bm2_insert_empty(struct bitmap* const bm, const UWord a1);
+static __inline__
+struct bitmap2* bm2_insert_addref(struct bitmap* const bm,
+ struct bitmap2* const bm2);
+
/** Rotate elements cache[0..n-1] such that the element at position n-1 is
* moved to position 0. This allows to speed up future cache lookups.
*/
@@ -473,6 +480,7 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(bm);
#endif
+
if (! bm_cache_lookup(bm, a1, &bm2))
{
bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
@@ -480,7 +488,22 @@
{
bm2 = bm2ref->bm2;
}
- bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
+ else if (bm->compute_bitmap2)
+ {
+ /* Compute the second-level bitmap, and insert the pointer to the
+ * computed bitmap. Note: this pointer may be NULL. */
+ bm2 = (*bm->compute_bitmap2)(a1);
+ if (bm2)
+ {
+ return bm2_insert_addref(bm, bm2);
+ }
+ else
+ {
+ bm2_insert_empty(bm, a1);
+ return NULL;
+ }
+ }
+ bm_update_cache(bm, a1, bm2);
}
return bm2;
}
@@ -498,6 +521,11 @@
struct bitmap2ref* bm2ref;
struct bitmap2* bm2;
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+ tl_assert(bm->compute_bitmap2 == 0);
+#endif
+
bm2ref = 0;
if (bm_cache_lookup(bm, a1, &bm2))
{
@@ -525,17 +553,17 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(bm2ref);
#endif
- bm2 = bm2_make_exclusive(*(struct bitmap**)&bm, bm2ref);
+ bm2 = bm2_make_exclusive(bm, bm2ref);
}
return bm2;
}
-/** Look up the address a1 in bitmap bm. The returned second level bitmap has
- * reference count one and hence may be modified.
+/** Insert a new node in bitmap bm for the address a1. The returned second
+ * level bitmap has reference count one and hence may be modified.
*
+ * @param bm bitmap pointer.
* @param a1 client address shifted right by ADDR_LSB_BITS.
- * @param bm bitmap pointer.
*/
static __inline__
struct bitmap2* bm2_insert(struct bitmap* const bm, const UWord a1)
@@ -543,6 +571,10 @@
struct bitmap2ref* bm2ref;
struct bitmap2* bm2;
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+#endif
+
s_bitmap2_node_creation_count++;
bm2ref = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2ref));
bm2ref->addr = a1;
@@ -551,13 +583,16 @@
VG_(memset)(&bm2->bm1, 0, sizeof(bm2->bm1));
VG_(OSetGen_Insert)(bm->oset, bm2ref);
- bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
+ bm_update_cache(bm, a1, bm2);
return bm2;
}
/** Insert a new node in bitmap bm that points to the second level bitmap
* *bm2. This means that *bm2 becomes shared over two or more bitmaps.
+ *
+ * @param bm bitmap pointer.
+ * @param bm2 Second-level bitmap pointer. May be NULL.
*/
static __inline__
struct bitmap2* bm2_insert_addref(struct bitmap* const bm,
@@ -567,6 +602,7 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(bm);
+ tl_assert(bm2);
tl_assert(VG_(OSetGen_Lookup)(bm->oset, &bm2->addr) == 0);
#endif
@@ -577,11 +613,35 @@
bm2->refcnt++;
VG_(OSetGen_Insert)(bm->oset, bm2ref);
- bm_update_cache(*(struct bitmap**)&bm, bm2->addr, bm2);
+ bm_update_cache(bm, bm2->addr, bm2);
return bm2;
}
+/** Insert an empty node in bitmap bm.
+ *
+ * @param bm bitmap pointer.
+ * @param a1 client address shifted right by ADDR_LSB_BITS.
+ */
+static __inline__
+void bm2_insert_empty(struct bitmap* const bm, const UWord a1)
+{
+ struct bitmap2ref* bm2ref;
+
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+ tl_assert(VG_(OSetGen_Lookup)(bm->oset, &a1) == 0);
+#endif
+
+ s_bitmap2_node_creation_count++;
+ bm2ref = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2ref));
+ bm2ref->addr = a1;
+ bm2ref->bm2 = NULL;
+ VG_(OSetGen_Insert)(bm->oset, bm2ref);
+
+ bm_update_cache(bm, a1, NULL);
+}
+
/** Look up the address a1 in bitmap bm, and insert it if not found.
* The returned second level bitmap may not be modified.
*
@@ -596,7 +656,9 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(bm);
+ tl_assert(bm->compute_bitmap2 == 0);
#endif
+
if (bm_cache_lookup(bm, a1, &bm2))
{
if (bm2 == 0)
@@ -615,7 +677,7 @@
{
bm2 = bm2_insert(bm, a1);
}
- bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
+ bm_update_cache(bm, a1, bm2);
}
return bm2;
}
@@ -634,7 +696,9 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(bm);
+ tl_assert(bm->compute_bitmap2 == 0);
#endif
+
bm2 = (struct bitmap2*)bm2_lookup_or_insert(bm, a1);
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(bm2);
@@ -654,6 +718,11 @@
{
struct bitmap2* bm2;
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+ tl_assert(bm->compute_bitmap2 == 0);
+#endif
+
bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(a1));
bm0_set_range(bm2->bm1.bm0_r,
(a1 >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK,
@@ -666,6 +735,11 @@
{
struct bitmap2* bm2;
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+ tl_assert(bm->compute_bitmap2 == 0);
+#endif
+
bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(a1));
bm0_set_range(bm2->bm1.bm0_w,
(a1 >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK,
@@ -674,34 +748,36 @@
static __inline__
Bool bm_aligned_load_has_conflict_with(struct bitmap* const bm,
- const Addr a1, const SizeT size)
+ const Addr a, const SizeT size)
{
const struct bitmap2* bm2;
- bm2 = bm2_lookup(bm, address_msb(a1));
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+#endif
+ bm2 = bm2_lookup(bm, address_msb(a));
return (bm2
&& bm0_is_any_set(bm2->bm1.bm0_w,
- (a1 >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK,
+ address_lsb(a),
SCALED_SIZE(size)));
}
static __inline__
Bool bm_aligned_store_has_conflict_with(struct bitmap* const bm,
- const Addr a1, const SizeT size)
+ const Addr a, const SizeT size)
{
const struct bitmap2* bm2;
- bm2 = bm2_lookup(bm, address_msb(a1));
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+#endif
+ bm2 = bm2_lookup(bm, address_msb(a));
if (bm2)
{
- if (bm0_is_any_set(bm2->bm1.bm0_r,
- (a1 >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK,
- SCALED_SIZE(size))
- | bm0_is_any_set(bm2->bm1.bm0_w,
- (a1 >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK,
- SCALED_SIZE(size)))
+ if (bm0_is_any_set(bm2->bm1.bm0_r, address_lsb(a), SCALED_SIZE(size))
+ | bm0_is_any_set(bm2->bm1.bm0_w, address_lsb(a), SCALED_SIZE(size)))
{
return True;
}
Modified: branches/DRDDEV/drd/drd_thread.c
===================================================================
--- branches/DRDDEV/drd/drd_thread.c 2008-07-13 07:51:30 UTC (rev 8427)
+++ branches/DRDDEV/drd/drd_thread.c 2008-07-13 07:52:10 UTC (rev 8428)
@@ -895,6 +895,17 @@
}
}
+static struct bitmap2* thread_compute_conflict_set_bitmap2(const UWord a1)
+{
+ if (s_trace_conflict_set)
+ {
+ VG_(message)(Vg_UserMsg,
+ "thread_compute_conflict_set_bitmap2(a1 = %#lx)",
+ a1);
+ }
+ return 0;
+}
+
/** Compute a bitmap that represents the union of all memory accesses of all
* segments that are unordered to the current segment of the thread tid.
*/
@@ -915,7 +926,7 @@
{
bm_delete(*conflict_set);
}
- *conflict_set = bm_new();
+ *conflict_set = bm_new_cb(thread_compute_conflict_set_bitmap2);
if (s_trace_conflict_set)
{
Modified: branches/DRDDEV/drd/pub_drd_bitmap.h
===================================================================
--- branches/DRDDEV/drd/pub_drd_bitmap.h 2008-07-13 07:51:30 UTC (rev 8427)
+++ branches/DRDDEV/drd/pub_drd_bitmap.h 2008-07-13 07:52:10 UTC (rev 8428)
@@ -47,6 +47,7 @@
// Forward declarations.
struct bitmap;
+struct bitmap2;
// Datatype definitions.
@@ -55,6 +56,7 @@
// Function declarations.
struct bitmap* bm_new(void);
+struct bitmap* bm_new_cb(struct bitmap2* (*compute_bitmap2)(UWord));
void bm_delete(struct bitmap* const bm);
void bm_access_range(struct bitmap* const bm,
const Addr a1, const Addr a2,
|