Author: njn
Date: 2009-05-10 23:40:50 +0100 (Sun, 10 May 2009)
New Revision: 9830
Log:
Merge from the trunk r9813, r9814, r9816, r9817, r9819, r9822, r9823 (DRD
tweaks and ignore file updates) done by Bart.
Modified:
branches/DARWIN/configure.in
branches/DARWIN/drd/drd_bitmap.c
branches/DARWIN/drd/drd_bitmap.h
branches/DARWIN/drd/pub_drd_bitmap.h
branches/DARWIN/drd/scripts/run-splash2
branches/DARWIN/drd/tests/drd_bitmap_test.c
branches/DARWIN/massif/tests/
branches/DARWIN/memcheck/perf/
branches/DARWIN/memcheck/tests/
branches/DARWIN/nightly/
branches/DARWIN/none/tests/linux/
branches/DARWIN/none/tests/x86-linux/
branches/DARWIN/tests/
Modified: branches/DARWIN/configure.in
===================================================================
--- branches/DARWIN/configure.in 2009-05-10 22:23:48 UTC (rev 9829)
+++ branches/DARWIN/configure.in 2009-05-10 22:40:50 UTC (rev 9830)
@@ -983,7 +983,15 @@
void *(*)(void*), void*);
__asm__(".symver pthread_create_glibc_2_0, pthread_create@GLIBC_2.0");
], [
+#ifdef __powerpc__
+/*
+ * Apparently on PowerPC linking this program succeeds and generates an
+ * executable with the undefined symbol pthread_create@GLIBC_2.0.
+ */
+#error This test does not work properly on PowerPC.
+#else
pthread_create_glibc_2_0(0, 0, 0, 0);
+#endif
return 0;
],
[
Modified: branches/DARWIN/drd/drd_bitmap.c
===================================================================
--- branches/DARWIN/drd/drd_bitmap.c 2009-05-10 22:23:48 UTC (rev 9829)
+++ branches/DARWIN/drd/drd_bitmap.c 2009-05-10 22:40:50 UTC (rev 9830)
@@ -37,20 +37,18 @@
#include "pub_tool_mallocfree.h" /* VG_(malloc), VG_(free) */
-/* Forward declarations. */
-
-struct bitmap2;
-
-
/* Local function declarations. */
static void bm2_merge(struct bitmap2* const bm2l,
const struct bitmap2* const bm2r);
+static void bm2_print(const struct bitmap2* const bm2);
/* Local variables. */
static ULong s_bitmap_creation_count;
+static ULong s_bitmap_merge_count;
+static ULong s_bitmap2_merge_count;
/* Function definitions. */
@@ -66,9 +64,10 @@
bm = VG_(malloc)("drd.bitmap.bn.1", sizeof(*bm));
tl_assert(bm);
- /* Cache initialization. a1 is initialized with a value that never can */
- /* match any valid address: the upper ADDR0_BITS bits of a1 are always */
- /* zero for a valid cache entry. */
+ /* Cache initialization. a1 is initialized with a value that never can
+ * 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++)
{
bm->cache[i].a1 = ~(UWord)1;
@@ -84,22 +83,8 @@
void DRD_(bm_delete)(struct bitmap* const bm)
{
- struct bitmap2* bm2;
- struct bitmap2ref* bm2ref;
-
tl_assert(bm);
- VG_(OSetGen_ResetIter)(bm->oset);
- for ( ; (bm2ref = VG_(OSetGen_Next)(bm->oset)) != 0; )
- {
- bm2 = bm2ref->bm2;
- tl_assert(bm2->refcnt >= 1);
- if (--bm2->refcnt == 0)
- {
- VG_(free)(bm2);
- }
- }
-
VG_(OSetGen_Destroy)(bm->oset);
VG_(free)(bm);
}
@@ -107,6 +92,11 @@
/**
* Record an access of type access_type at addresses a .. a + size - 1 in
* bitmap bm.
+ *
+ * @note The current implementation of bm_access_range does not work for the
+ * highest addresses in the address range. At least on Linux this is
+ * not a problem since the upper part of the address space is reserved
+ * for the kernel.
*/
void DRD_(bm_access_range)(struct bitmap* const bm,
const Addr a1, const Addr a2,
@@ -120,52 +110,50 @@
return DRD_(bm_access_range_store)(bm, a1, a2);
}
-void DRD_(bm_access_range_load)(struct bitmap* const bm,
- const Addr a1, const Addr a2)
+void DRD_(bm_access_range_load)(struct bitmap* const bm, Addr a1, Addr a2)
{
Addr b, b_next;
tl_assert(bm);
tl_assert(a1 < a2);
- /* The current implementation of bm_access_range does not work for the */
- /* ADDR0_COUNT highest addresses in the address range. At least on Linux */
- /* this is not a problem since the upper part of the address space is */
- /* reserved for the kernel. */
- tl_assert(a2 + ADDR0_COUNT > a2);
+ tl_assert(a2 < first_address_with_higher_msb(a2));
+ tl_assert(a1 == first_address_with_same_lsb(a1));
+ tl_assert(a2 == first_address_with_same_lsb(a2));
for (b = a1; b < a2; b = b_next)
{
Addr b_start;
Addr b_end;
struct bitmap2* bm2;
- SPLIT_ADDRESS(b);
+ UWord b0;
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
}
- bm2 = bm2_lookup_or_insert_exclusive(bm, b1);
+ bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b));
tl_assert(bm2);
- if ((bm2->addr << ADDR0_BITS) < a1)
+ if (make_address(bm2->addr, 0) < a1)
b_start = a1;
else
- if ((bm2->addr << ADDR0_BITS) < a2)
- b_start = (bm2->addr << ADDR0_BITS);
+ if (make_address(bm2->addr, 0) < a2)
+ b_start = make_address(bm2->addr, 0);
else
break;
- if ((bm2->addr << ADDR0_BITS) + ADDR0_COUNT < a2)
- b_end = (bm2->addr << ADDR0_BITS) + ADDR0_COUNT;
+ if (make_address(bm2->addr + 1, 0) < a2)
+ b_end = make_address(bm2->addr + 1, 0);
else
b_end = a2;
tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2);
- tl_assert((b_start & ADDR0_MASK) <= ((b_end - 1) & ADDR0_MASK));
+ tl_assert(address_msb(b_start) == address_msb(b_end - 1));
+ tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
- if (b_end - b_start == ADDR0_COUNT)
+ if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0)
{
unsigned k;
@@ -176,7 +164,7 @@
}
else
{
- for (b0 = b_start & ADDR0_MASK; b0 <= ((b_end - 1) & ADDR0_MASK); b0++)
+ for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
{
bm0_set(bm2->bm1.bm0_r, b0);
}
@@ -225,45 +213,44 @@
tl_assert(bm);
tl_assert(a1 < a2);
- /* The current implementation of bm_access_range does not work for the */
- /* ADDR0_COUNT highest addresses in the address range. At least on Linux */
- /* this is not a problem since the upper part of the address space is */
- /* reserved for the kernel. */
- tl_assert(a2 + ADDR0_COUNT > a2);
+ tl_assert(a2 < first_address_with_higher_msb(a2));
+ tl_assert(a1 == first_address_with_same_lsb(a1));
+ tl_assert(a2 == first_address_with_same_lsb(a2));
for (b = a1; b < a2; b = b_next)
{
Addr b_start;
Addr b_end;
struct bitmap2* bm2;
- SPLIT_ADDRESS(b);
+ UWord b0;
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
}
- bm2 = bm2_lookup_or_insert_exclusive(bm, b1);
+ bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b));
tl_assert(bm2);
- if ((bm2->addr << ADDR0_BITS) < a1)
+ if (make_address(bm2->addr, 0) < a1)
b_start = a1;
else
- if ((bm2->addr << ADDR0_BITS) < a2)
- b_start = (bm2->addr << ADDR0_BITS);
+ if (make_address(bm2->addr, 0) < a2)
+ b_start = make_address(bm2->addr, 0);
else
break;
- if ((bm2->addr << ADDR0_BITS) + ADDR0_COUNT < a2)
- b_end = (bm2->addr << ADDR0_BITS) + ADDR0_COUNT;
+ if (make_address(bm2->addr + 1, 0) < a2)
+ b_end = make_address(bm2->addr + 1, 0);
else
b_end = a2;
tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2);
- tl_assert((b_start & ADDR0_MASK) <= ((b_end - 1) & ADDR0_MASK));
+ tl_assert(address_msb(b_start) == address_msb(b_end - 1));
+ tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
- if (b_end - b_start == ADDR0_COUNT)
+ if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0)
{
unsigned k;
@@ -274,7 +261,7 @@
}
else
{
- for (b0 = b_start & ADDR0_MASK; b0 <= ((b_end - 1) & ADDR0_MASK); b0++)
+ for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
{
bm0_set(bm2->bm1.bm0_w, b0);
}
@@ -336,9 +323,9 @@
for (b = a1; b < a2; b = b_next)
{
- const struct bitmap2* bm2 = bm2_lookup(bm, b >> ADDR0_BITS);
+ const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b));
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
@@ -351,24 +338,24 @@
UWord b0;
const struct bitmap1* const p1 = &bm2->bm1;
- if ((bm2->addr << ADDR0_BITS) < a1)
+ if (make_address(bm2->addr, 0) < a1)
b_start = a1;
else
- if ((bm2->addr << ADDR0_BITS) < a2)
- b_start = (bm2->addr << ADDR0_BITS);
+ if (make_address(bm2->addr, 0) < a2)
+ b_start = make_address(bm2->addr, 0);
else
break;
tl_assert(a1 <= b_start && b_start <= a2);
- if ((bm2->addr << ADDR0_BITS) + ADDR0_COUNT < a2)
- b_end = (bm2->addr << ADDR0_BITS) + ADDR0_COUNT;
+ if (make_address(bm2->addr + 1, 0) < a2)
+ b_end = make_address(bm2->addr + 1, 0);
else
b_end = a2;
tl_assert(a1 <= b_end && b_end <= a2);
tl_assert(b_start < b_end);
- tl_assert((b_start & ADDR0_MASK) <= ((b_end - 1) & ADDR0_MASK));
+ tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
- for (b0 = b_start & ADDR0_MASK; b0 <= ((b_end-1) & ADDR0_MASK); b0++)
+ for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
{
if (bm0_is_set(p1->bm0_r, b0))
{
@@ -389,9 +376,9 @@
for (b = a1; b < a2; b = b_next)
{
- const struct bitmap2* bm2 = bm2_lookup(bm, b >> ADDR0_BITS);
+ const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b));
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
@@ -404,24 +391,24 @@
UWord b0;
const struct bitmap1* const p1 = &bm2->bm1;
- if ((bm2->addr << ADDR0_BITS) < a1)
+ if (make_address(bm2->addr, 0) < a1)
b_start = a1;
else
- if ((bm2->addr << ADDR0_BITS) < a2)
- b_start = (bm2->addr << ADDR0_BITS);
+ if (make_address(bm2->addr, 0) < a2)
+ b_start = make_address(bm2->addr, 0);
else
break;
tl_assert(a1 <= b_start && b_start <= a2);
- if ((bm2->addr << ADDR0_BITS) + ADDR0_COUNT < a2)
- b_end = (bm2->addr << ADDR0_BITS) + ADDR0_COUNT;
+ if (make_address(bm2->addr + 1, 0) < a2)
+ b_end = make_address(bm2->addr + 1, 0);
else
b_end = a2;
tl_assert(a1 <= b_end && b_end <= a2);
tl_assert(b_start < b_end);
- tl_assert((b_start & ADDR0_MASK) <= ((b_end - 1) & ADDR0_MASK));
+ tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
- for (b0 = b_start & ADDR0_MASK; b0 <= ((b_end-1) & ADDR0_MASK); b0++)
+ for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
{
if (bm0_is_set(p1->bm0_w, b0))
{
@@ -444,9 +431,9 @@
for (b = a1; b < a2; b = b_next)
{
- const struct bitmap2* bm2 = bm2_lookup(bm, b >> ADDR0_BITS);
+ const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b));
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
@@ -459,24 +446,24 @@
UWord b0;
const struct bitmap1* const p1 = &bm2->bm1;
- if ((bm2->addr << ADDR0_BITS) < a1)
+ if (make_address(bm2->addr, 0) < a1)
b_start = a1;
else
- if ((bm2->addr << ADDR0_BITS) < a2)
- b_start = (bm2->addr << ADDR0_BITS);
+ if (make_address(bm2->addr, 0) < a2)
+ b_start = make_address(bm2->addr, 0);
else
break;
tl_assert(a1 <= b_start && b_start <= a2);
- if ((bm2->addr << ADDR0_BITS) + ADDR0_COUNT < a2)
- b_end = (bm2->addr << ADDR0_BITS) + ADDR0_COUNT;
+ if (make_address(bm2->addr + 1, 0) < a2)
+ b_end = make_address(bm2->addr + 1, 0);
else
b_end = a2;
tl_assert(a1 <= b_end && b_end <= a2);
tl_assert(b_start < b_end);
- tl_assert((b_start & ADDR0_MASK) <= ((b_end - 1) & ADDR0_MASK));
+ tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
- for (b0 = b_start & ADDR0_MASK; b0 <= ((b_end-1) & ADDR0_MASK); b0++)
+ for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
{
if (bm0_is_set(p1->bm0_r, b0) | bm0_is_set(p1->bm0_w, b0))
{
@@ -498,11 +485,11 @@
const struct bitmap2* p2;
const struct bitmap1* p1;
const UWord* p0;
- const UWord a0 = a & ADDR0_MASK;
+ const UWord a0 = address_lsb(a);
tl_assert(bm);
- p2 = bm2_lookup(bm, a >> ADDR0_BITS);
+ p2 = bm2_lookup(bm, address_msb(a));
if (p2)
{
p1 = &p2->bm1;
@@ -512,20 +499,16 @@
return False;
}
-void DRD_(bm_clear)(struct bitmap* const bm, const Addr a1, const Addr a2)
+void DRD_(bm_clear)(struct bitmap* const bm, Addr a1, Addr a2)
{
Addr b, b_next;
tl_assert(bm);
tl_assert(a1);
tl_assert(a1 <= a2);
+ tl_assert(a1 == first_address_with_same_lsb(a1));
+ tl_assert(a2 == first_address_with_same_lsb(a2));
-#if 0
- if (a2 - a1 >= ADDR0_COUNT)
- VG_(message)(Vg_DebugMsg, "bm_clear(bm = %p, a1 = 0x%lx, a2 = 0x%lx,"
- " delta = 0x%lx", bm, a1, a2, a2 - a1);
-#endif
-
for (b = a1; b < a2; b = b_next)
{
struct bitmap2* p2;
@@ -535,9 +518,9 @@
tl_assert(a1 <= b && b < a2);
#endif
- p2 = bm2_lookup_exclusive(bm, b >> ADDR0_BITS);
+ p2 = bm2_lookup_exclusive(bm, address_msb(b));
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
@@ -549,34 +532,33 @@
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. */
- if (UWORD_LSB(c))
+ if (uword_lsb(address_lsb(c)))
{
- Addr c_next = UWORD_MSB(c) + BITS_PER_UWORD;
+ Addr c_next = first_address_with_higher_uword_msb(c);
if (c_next > b_next)
c_next = b_next;
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next
&& b_next <= a2);
#endif
- bm0_clear_range(p2->bm1.bm0_r, c & ADDR0_MASK, c_next - c);
- bm0_clear_range(p2->bm1.bm0_w, c & ADDR0_MASK, c_next - c);
+ bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(c_next - c));
+ bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(c_next - c));
c = c_next;
}
/* If some UWords have to be cleared entirely, do this now. */
- if (UWORD_LSB(c) == 0)
+ if (uword_lsb(address_lsb(c)) == 0)
{
- const Addr c_next = UWORD_MSB(b_next);
+ Addr c_next = first_address_with_same_uword_lsb(b_next);
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(UWORD_LSB(c) == 0);
- tl_assert(UWORD_LSB(c_next) == 0);
+ tl_assert(uword_lsb(address_lsb(c)) == 0);
+ tl_assert(uword_lsb(address_lsb(c_next)) == 0);
tl_assert(c_next <= b_next);
- tl_assert(c <= c_next);
#endif
if (c_next > c)
{
- UWord idx = (c & ADDR0_MASK) >> BITS_PER_BITS_PER_UWORD;
- VG_(memset)(&p2->bm1.bm0_r[idx], 0, (c_next - c) / 8);
- VG_(memset)(&p2->bm1.bm0_w[idx], 0, (c_next - c) / 8);
+ UWord idx = uword_msb(address_lsb(c));
+ VG_(memset)(&p2->bm1.bm0_r[idx], 0, SCALED_SIZE((c_next - c) / 8));
+ VG_(memset)(&p2->bm1.bm0_w[idx], 0, SCALED_SIZE((c_next - c) / 8));
c = c_next;
}
}
@@ -585,8 +567,8 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
#endif
- bm0_clear_range(p2->bm1.bm0_r, c & ADDR0_MASK, b_next - c);
- bm0_clear_range(p2->bm1.bm0_w, c & ADDR0_MASK, b_next - c);
+ bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(b_next - c));
+ bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(b_next - c));
}
}
@@ -594,20 +576,16 @@
* Clear all references to loads in bitmap bm starting at address a1 and
* up to but not including address a2.
*/
-void DRD_(bm_clear_load)(struct bitmap* const bm, const Addr a1, const Addr a2)
+void DRD_(bm_clear_load)(struct bitmap* const bm, Addr a1, Addr a2)
{
Addr b, b_next;
tl_assert(bm);
tl_assert(a1);
tl_assert(a1 <= a2);
+ tl_assert(a1 == first_address_with_same_lsb(a1));
+ tl_assert(a2 == first_address_with_same_lsb(a2));
-#if 0
- if (a2 - a1 >= ADDR0_COUNT)
- VG_(message)(Vg_DebugMsg, "bm_clear_load(bm = %p, a1 = 0x%lx, a2 = 0x%lx,"
- " delta = 0x%lx", bm, a1, a2, a2 - a1);
-#endif
-
for (b = a1; b < a2; b = b_next)
{
struct bitmap2* p2;
@@ -617,9 +595,9 @@
tl_assert(a1 <= b && b < a2);
#endif
- p2 = bm2_lookup_exclusive(bm, b >> ADDR0_BITS);
+ p2 = bm2_lookup_exclusive(bm, address_msb(b));
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
@@ -634,35 +612,35 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c < b_next && b_next <= a2);
#endif
- if (UWORD_LSB(c))
+ if (uword_lsb(address_lsb(c)))
{
- Addr c_next = UWORD_MSB(c) + BITS_PER_UWORD;
+ Addr c_next = first_address_with_higher_uword_msb(c);
if (c_next > b_next)
c_next = b_next;
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c < c_next && c_next <= b_next
&& b_next <= a2);
#endif
- bm0_clear_range(p2->bm1.bm0_r, c & ADDR0_MASK, c_next - c);
+ bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(c_next - c));
c = c_next;
}
/* If some UWords have to be cleared entirely, do this now. */
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
#endif
- if (UWORD_LSB(c) == 0)
+ if (uword_lsb(address_lsb(c)) == 0)
{
- const Addr c_next = UWORD_MSB(b_next);
+ Addr c_next = first_address_with_same_uword_lsb(b_next);
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(UWORD_LSB(c) == 0);
- tl_assert(UWORD_LSB(c_next) == 0);
+ tl_assert(uword_lsb(address_lsb(c)) == 0);
+ tl_assert(uword_lsb(address_lsb(c_next)) == 0);
tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next
&& b_next <= a2);
#endif
if (c_next > c)
{
- UWord idx = (c & ADDR0_MASK) >> BITS_PER_BITS_PER_UWORD;
- VG_(memset)(&p2->bm1.bm0_r[idx], 0, (c_next - c) / 8);
+ UWord idx = uword_msb(address_lsb(c));
+ VG_(memset)(&p2->bm1.bm0_r[idx], 0, SCALED_SIZE((c_next - c) / 8));
c = c_next;
}
}
@@ -671,7 +649,7 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
#endif
- bm0_clear_range(p2->bm1.bm0_r, c & ADDR0_MASK, b_next - c);
+ bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(b_next - c));
}
}
@@ -687,13 +665,9 @@
tl_assert(bm);
tl_assert(a1);
tl_assert(a1 <= a2);
+ tl_assert(a1 == first_address_with_same_lsb(a1));
+ tl_assert(a2 == first_address_with_same_lsb(a2));
-#if 0
- if (a2 - a1 >= ADDR0_COUNT)
- VG_(message)(Vg_DebugMsg, "bm_clear_store(bm = %p, a1 = 0x%lx, a2 = 0x%lx,"
- " delta = 0x%lx", bm, a1, a2, a2 - a1);
-#endif
-
for (b = a1; b < a2; b = b_next)
{
struct bitmap2* p2;
@@ -703,9 +677,9 @@
tl_assert(a1 <= b && b < a2);
#endif
- p2 = bm2_lookup_exclusive(bm, b >> ADDR0_BITS);
+ p2 = bm2_lookup_exclusive(bm, address_msb(b));
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
@@ -720,35 +694,35 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c < b_next && b_next <= a2);
#endif
- if (UWORD_LSB(c))
+ if (uword_lsb(address_lsb(c)))
{
- Addr c_next = UWORD_MSB(c) + BITS_PER_UWORD;
+ Addr c_next = first_address_with_higher_uword_msb(c);
if (c_next > b_next)
c_next = b_next;
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c < c_next && c_next <= b_next
&& b_next <= a2);
#endif
- bm0_clear_range(p2->bm1.bm0_w, c & ADDR0_MASK, c_next - c);
+ bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(c_next - c));
c = c_next;
}
/* If some UWords have to be cleared entirely, do this now. */
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
#endif
- if (UWORD_LSB(c) == 0)
+ if (uword_lsb(address_lsb(c)) == 0)
{
- const Addr c_next = UWORD_MSB(b_next);
+ Addr c_next = first_address_with_same_uword_lsb(b_next);
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(UWORD_LSB(c) == 0);
- tl_assert(UWORD_LSB(c_next) == 0);
+ tl_assert(uword_lsb(address_lsb(c)) == 0);
+ tl_assert(uword_lsb(address_lsb(c_next)) == 0);
tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next
&& b_next <= a2);
#endif
if (c_next > c)
{
- UWord idx = (c & ADDR0_MASK) >> BITS_PER_BITS_PER_UWORD;
- VG_(memset)(&p2->bm1.bm0_w[idx], 0, (c_next - c) / 8);
+ UWord idx = uword_msb(address_lsb(c));
+ VG_(memset)(&p2->bm1.bm0_w[idx], 0, SCALED_SIZE((c_next - c) / 8));
c = c_next;
}
}
@@ -757,7 +731,7 @@
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2);
#endif
- bm0_clear_range(p2->bm1.bm0_w, c & ADDR0_MASK, b_next - c);
+ bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(b_next - c));
}
}
@@ -786,9 +760,9 @@
for (b = a1; b < a2; b = b_next)
{
- const struct bitmap2* bm2 = bm2_lookup(bm, b >> ADDR0_BITS);
+ const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b));
- b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
+ b_next = first_address_with_higher_msb(b);
if (b_next > a2)
{
b_next = a2;
@@ -801,24 +775,24 @@
UWord b0;
const struct bitmap1* const p1 = &bm2->bm1;
- if ((bm2->addr << ADDR0_BITS) < a1)
+ if (make_address(bm2->addr, 0) < a1)
b_start = a1;
else
- if ((bm2->addr << ADDR0_BITS) < a2)
- b_start = (bm2->addr << ADDR0_BITS);
+ if (make_address(bm2->addr, 0) < a2)
+ b_start = make_address(bm2->addr, 0);
else
break;
tl_assert(a1 <= b_start && b_start <= a2);
- if ((bm2->addr << ADDR0_BITS) + ADDR0_COUNT < a2)
- b_end = (bm2->addr << ADDR0_BITS) + ADDR0_COUNT;
+ if (make_address(bm2->addr + 1, 0) < a2)
+ b_end = make_address(bm2->addr + 1, 0);
else
b_end = a2;
tl_assert(a1 <= b_end && b_end <= a2);
tl_assert(b_start < b_end);
- tl_assert((b_start & ADDR0_MASK) <= ((b_end - 1) & ADDR0_MASK));
+ tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1));
- for (b0 = b_start & ADDR0_MASK; b0 <= ((b_end-1) & ADDR0_MASK); b0++)
+ for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++)
{
if (access_type == eLoad)
{
@@ -919,9 +893,7 @@
Bool DRD_(bm_equal)(struct bitmap* const lhs, struct bitmap* const rhs)
{
struct bitmap2* bm2l;
- struct bitmap2ref* bm2l_ref;
struct bitmap2* bm2r;
- const struct bitmap2ref* bm2r_ref;
/* It's not possible to have two independent iterators over the same OSet, */
/* so complain if lhs == rhs. */
@@ -930,54 +902,38 @@
VG_(OSetGen_ResetIter)(lhs->oset);
VG_(OSetGen_ResetIter)(rhs->oset);
- for ( ; (bm2l_ref = VG_(OSetGen_Next)(lhs->oset)) != 0; )
+ for ( ; (bm2l = VG_(OSetGen_Next)(lhs->oset)) != 0; )
{
- while (bm2l_ref
- && (bm2l = bm2l_ref->bm2)
- && bm2l
+ while (bm2l
&& ! DRD_(bm_has_any_access)(lhs,
- bm2l->addr << ADDR0_BITS,
- (bm2l->addr + 1) << ADDR0_BITS))
+ make_address(bm2l->addr, 0),
+ make_address(bm2l->addr + 1, 0)))
{
- bm2l_ref = VG_(OSetGen_Next)(lhs->oset);
+ bm2l = VG_(OSetGen_Next)(lhs->oset);
}
- if (bm2l_ref == 0)
+ if (bm2l == 0)
break;
tl_assert(bm2l);
-#if 0
- VG_(message)(Vg_DebugMsg, "bm_equal: at 0x%lx", bm2l->addr << ADDR0_BITS);
-#endif
do
{
- bm2r_ref = VG_(OSetGen_Next)(rhs->oset);
- if (bm2r_ref == 0)
- {
-#if 0
- VG_(message)(Vg_DebugMsg, "bm_equal: no match found");
-#endif
+ bm2r = VG_(OSetGen_Next)(rhs->oset);
+ if (bm2r == 0)
return False;
- }
- bm2r = bm2r_ref->bm2;
- tl_assert(bm2r);
}
while (! DRD_(bm_has_any_access)(rhs,
- bm2r->addr << ADDR0_BITS,
- (bm2r->addr + 1) << ADDR0_BITS));
+ make_address(bm2r->addr, 0),
+ make_address(bm2r->addr + 1, 0)));
tl_assert(bm2r);
tl_assert(DRD_(bm_has_any_access)(rhs,
- bm2r->addr << ADDR0_BITS,
- (bm2r->addr + 1) << ADDR0_BITS));
+ make_address(bm2r->addr, 0),
+ make_address(bm2r->addr + 1, 0)));
if (bm2l != bm2r
&& (bm2l->addr != bm2r->addr
|| VG_(memcmp)(&bm2l->bm1, &bm2r->bm1, sizeof(bm2l->bm1)) != 0))
{
-#if 0
- VG_(message)(Vg_DebugMsg, "bm_equal: rhs 0x%lx -- returning false",
- bm2r->addr << ADDR0_BITS);
-#endif
return False;
}
}
@@ -986,18 +942,13 @@
{
bm2r = VG_(OSetGen_Next)(rhs->oset);
} while (bm2r && ! DRD_(bm_has_any_access)(rhs,
- bm2r->addr << ADDR0_BITS,
- (bm2r->addr + 1) << ADDR0_BITS));
+ make_address(bm2r->addr, 0),
+ make_address(bm2r->addr + 1, 0)));
if (bm2r)
{
tl_assert(DRD_(bm_has_any_access)(rhs,
- bm2r->addr << ADDR0_BITS,
- (bm2r->addr + 1) << ADDR0_BITS));
-#if 0
- VG_(message)(Vg_DebugMsg,
- "bm_equal: remaining rhs 0x%lx -- returning false",
- bm2r->addr << ADDR0_BITS);
-#endif
+ make_address(bm2r->addr, 0),
+ make_address(bm2r->addr + 1, 0)));
return False;
}
return True;
@@ -1015,29 +966,27 @@
struct bitmap* const rhs)
{
struct bitmap2* bm2l;
- struct bitmap2ref* bm2l_ref;
struct bitmap2* bm2r;
- const struct bitmap2ref* bm2r_ref;
+ /* It's not possible to have two independent iterators over the same OSet, */
+ /* so complain if lhs == rhs. */
+ tl_assert(lhs != rhs);
+
+ s_bitmap_merge_count++;
+
VG_(OSetGen_ResetIter)(rhs->oset);
- for ( ; (bm2r_ref = VG_(OSetGen_Next)(rhs->oset)) != 0; )
+ for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; )
{
- bm2r = bm2r_ref->bm2;
- bm2l_ref = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr);
- if (bm2l_ref)
+ bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr);
+ if (bm2l)
{
- bm2l = bm2l_ref->bm2;
- if (bm2l != bm2r)
- {
- if (bm2l->refcnt > 1)
- bm2l = bm2_make_exclusive(lhs, bm2l_ref);
- bm2_merge(bm2l, bm2r);
- }
+ tl_assert(bm2l != bm2r);
+ bm2_merge(bm2l, bm2r);
}
else
{
- bm2_insert_addref(lhs, bm2r);
+ bm2_insert_copy(lhs, bm2r);
}
}
}
@@ -1055,24 +1004,20 @@
for (;;)
{
- const struct bitmap2ref* bm2l_ref;
- const struct bitmap2ref* bm2r_ref;
const struct bitmap2* bm2l;
const struct bitmap2* bm2r;
const struct bitmap1* bm1l;
const struct bitmap1* bm1r;
unsigned k;
- bm2l_ref = VG_(OSetGen_Next)(lhs->oset);
- bm2l = bm2l_ref->bm2;
- bm2r_ref = VG_(OSetGen_Next)(rhs->oset);
- bm2r = bm2r_ref->bm2;
+ 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 = (bm2l_ref = VG_(OSetGen_Next)(lhs->oset))->bm2;
+ bm2l = VG_(OSetGen_Next)(lhs->oset);
else
- bm2r = (bm2r_ref = VG_(OSetGen_Next)(rhs->oset))->bm2;
+ bm2r = VG_(OSetGen_Next)(rhs->oset);
}
if (bm2l == 0 || bm2r == 0)
break;
@@ -1090,7 +1035,7 @@
| ((bm1l->bm0_w[k] & bm0_mask(b)) ? LHS_W : 0)
| ((bm1r->bm0_r[k] & bm0_mask(b)) ? RHS_R : 0)
| ((bm1r->bm0_w[k] & bm0_mask(b)) ? RHS_W : 0);
- Addr const a = MAKE_ADDRESS(bm2l->addr, k * BITS_PER_UWORD | b);
+ Addr const a = make_address(bm2l->addr, k * BITS_PER_UWORD | b);
if (HAS_RACE(access_mask) && ! DRD_(is_suppressed)(a, a + 1))
{
return 1;
@@ -1104,29 +1049,35 @@
void DRD_(bm_print)(struct bitmap* const bm)
{
struct bitmap2* bm2;
- struct bitmap2ref* bm2ref;
- VG_(OSetGen_ResetIter)(bm->oset);
-
- for ( ; (bm2ref = VG_(OSetGen_Next)(bm->oset)) != 0; )
+ for (VG_(OSetGen_ResetIter)(bm->oset);
+ (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0;
+ )
{
- const struct bitmap1* bm1;
- unsigned b;
+ bm2_print(bm2);
+ }
+}
- bm2 = bm2ref->bm2;
- bm1 = &bm2->bm1;
- for (b = 0; b < ADDR0_COUNT; b++)
+static void bm2_print(const struct bitmap2* const bm2)
+{
+ const struct bitmap1* bm1;
+ Addr a;
+
+ tl_assert(bm2);
+
+ bm1 = &bm2->bm1;
+ for (a = make_address(bm2->addr, 0);
+ a <= make_address(bm2->addr + 1, 0) - 1;
+ a++)
+ {
+ const Bool r = bm0_is_set(bm1->bm0_r, address_lsb(a)) != 0;
+ const Bool w = bm0_is_set(bm1->bm0_w, address_lsb(a)) != 0;
+ if (r || w)
{
- const Addr a = (bm2->addr << ADDR0_BITS) | b;
- const Bool r = bm0_is_set(bm1->bm0_r, b) != 0;
- const Bool w = bm0_is_set(bm1->bm0_w, b) != 0;
- if (r || w)
- {
- VG_(printf)("0x%08lx %c %c\n",
- a,
- w ? 'W' : ' ',
- r ? 'R' : ' ');
- }
+ VG_(printf)("0x%08lx %c %c\n",
+ a,
+ w ? 'W' : ' ',
+ r ? 'R' : ' ');
}
}
}
@@ -1146,63 +1097,30 @@
return s_bitmap2_creation_count;
}
-/** Allocate and initialize a second level bitmap. */
-static struct bitmap2* bm2_new(const UWord a1)
+ULong DRD_(bm_get_bitmap2_merge_count)(void)
{
- struct bitmap2* bm2;
-
- bm2 = VG_(malloc)("drd.bitmap.bm2n.1", sizeof(*bm2));
- bm2->addr = a1;
- bm2->refcnt = 1;
-
- s_bitmap2_creation_count++;
-
- return bm2;
+ return s_bitmap2_merge_count;
}
-/** Make a copy of a shared second level bitmap such that the copy can be
- * modified.
- *
- * @param a1 client address shifted right by ADDR0_BITS.
- * @param bm bitmap pointer.
- */
-static struct bitmap2* bm2_make_exclusive(struct bitmap* const bm,
- struct bitmap2ref* const bm2ref)
+/** Clear the bitmap contents. */
+static void bm2_clear(struct bitmap2* const bm2)
{
- UWord a1;
- struct bitmap2* bm2;
- struct bitmap2* bm2_copy;
-
- tl_assert(bm);
- tl_assert(bm2ref);
- bm2 = bm2ref->bm2;
tl_assert(bm2);
- tl_assert(bm2->refcnt > 1);
- bm2->refcnt--;
- tl_assert(bm2->refcnt >= 1);
- a1 = bm2->addr;
- bm2_copy = bm2_new(a1);
- tl_assert(bm2_copy);
- tl_assert(bm2_copy->addr == a1);
- tl_assert(bm2_copy->refcnt == 1);
- VG_(memcpy)(&bm2_copy->bm1, &bm2->bm1, sizeof(bm2->bm1));
- bm2ref->bm2 = bm2_copy;
-
- bm_update_cache(bm, a1, bm2_copy);
-
- return bm2_copy;
+ VG_(memset)(&bm2->bm1, 0, sizeof(bm2->bm1));
}
-static void bm2_merge(struct bitmap2* const bm2l,
- const struct bitmap2* const bm2r)
+/** Compute *bm2l |= *bm2r. */
+static
+void bm2_merge(struct bitmap2* const bm2l, const struct bitmap2* const bm2r)
{
unsigned k;
tl_assert(bm2l);
tl_assert(bm2r);
tl_assert(bm2l->addr == bm2r->addr);
- tl_assert(bm2l->refcnt == 1);
+ s_bitmap2_merge_count++;
+
for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
{
bm2l->bm1.bm0_r[k] |= bm2r->bm1.bm0_r[k];
Modified: branches/DARWIN/drd/drd_bitmap.h
===================================================================
--- branches/DARWIN/drd/drd_bitmap.h 2009-05-10 22:23:48 UTC (rev 9829)
+++ branches/DARWIN/drd/drd_bitmap.h 2009-05-10 22:40:50 UTC (rev 9830)
@@ -27,36 +27,109 @@
#define __DRD_BITMAP_H
+#include "pub_drd_bitmap.h"
#include "pub_tool_basics.h"
#include "pub_tool_oset.h"
#include "pub_tool_libcbase.h"
-/*
- Bitmap representation. A bitmap is a data structure in which two bits are
- reserved per 32 bit address: one bit that indicates that the data at the
- specified address has been read, and one bit that indicates that the data has
- been written to.
-*/
+/* Bitmap representation. A bitmap is a data structure in which two bits are
+ * reserved per 32 bit address: one bit that indicates that the data at the
+ * specified address has been read, and one bit that indicates that the data
+ * has been written to.
+ */
+/* Client addresses are split into bitfields as follows:
+ * ------------------------------------------------------
+ * | Address MSB | Address LSB | Ignored bits |
+ * ------------------------------------------------------
+ * | Address MSB | UWord MSB | UWord LSB | Ignored bits |
+ * ------------------------------------------------------
+ */
-/* Macro definitions. */
-#define ADDR0_BITS 14
-#define ADDR0_COUNT ((UWord)1 << ADDR0_BITS)
+/* Address MSB / LSB split. */
-#define ADDR0_MASK (ADDR0_COUNT - 1)
-#define SPLIT_ADDRESS(a) \
- UWord a##0 = ((a) & ADDR0_MASK); \
- UWord a##1 = ((a) >> ADDR0_BITS);
+/** Number of least significant address bits that are ignored. */
+#define ADDR_IGNORED_BITS 0
+#define ADDR_IGNORED_MASK ((1U << ADDR_IGNORED_BITS) - 1U)
+#define ADDR_GRANULARITY (1U << ADDR_IGNORED_BITS)
-// Assumption: sizeof(Addr) == sizeof(UWord).
-#define MAKE_ADDRESS(a1, a0) \
- (Addr)(((UWord)(a1) << (ADDR0_BITS)) | ((UWord)(a0)))
+/** Round argument a up to a multiple of (1 << ADDR_GRANULARITY), and next
+ * shift it right ADDR_GRANULARITY bits. The expression below is optimized
+ * for the case where a is a constant.
+ */
+#define SCALED_SIZE(a) \
+ (((((a) - 1U) | ADDR_IGNORED_MASK) + 1U) >> ADDR_IGNORED_BITS)
-#define BITS_PER_UWORD (8UL*sizeof(UWord))
+/** Number of bits assigned to the least significant component of an address.
+ */
+#define ADDR_LSB_BITS 12
+
+/** Mask that has to be applied to an address of type Addr in order to
+ * compute the least significant part of an address split, after having
+ * shifted the address bits ADDR_GRANULARITY to the right.
+ */
+#define ADDR_LSB_MASK (((UWord)1 << ADDR_LSB_BITS) - 1U)
+
+/** Compute least significant bits of an address of type Addr. */
+static __inline__
+UWord address_lsb(const Addr a)
+{ return (a >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK; }
+
+/**
+ * Compute the first address for which address_lsb() is equal to
+ * address_lsb(a).
+ */
+static __inline__
+Addr first_address_with_same_lsb(const Addr a)
+{
+ return ((a | ADDR_IGNORED_MASK) ^ ADDR_IGNORED_MASK);
+}
+
+/**
+ * Compute the first address for which address_lsb() is greater than
+ * address_lsb(a).
+ */
+static __inline__
+Addr first_address_with_higher_lsb(const Addr a)
+{
+ return ((a | ADDR_IGNORED_MASK) + 1U);
+}
+
+/** Compute most significant bits of an address of type Addr. */
+static __inline__
+UWord address_msb(const Addr a)
+{ return a >> (ADDR_LSB_BITS + ADDR_IGNORED_BITS); }
+
+static __inline__
+Addr first_address_with_higher_msb(const Addr a)
+{
+ return ((a | ((ADDR_LSB_MASK << ADDR_IGNORED_BITS) | ADDR_IGNORED_MASK))
+ + 1U);
+}
+
+/** Convert LSB and MSB back into an address.
+ *
+ * @note It is assumed that sizeof(Addr) == sizeof(UWord).
+ */
+static __inline__
+Addr make_address(const UWord a1, const UWord a0)
+{
+ return ((a1 << (ADDR_LSB_BITS + ADDR_IGNORED_BITS))
+ | (a0 << ADDR_IGNORED_BITS));
+}
+
+
+
+
+
+/* Number of bits that fit in a variable of type UWord. */
+#define BITS_PER_UWORD (8U * sizeof(UWord))
+
+/* Log2 of BITS_PER_UWORD. */
#if defined(VGA_x86) || defined(VGA_ppc32)
#define BITS_PER_BITS_PER_UWORD 5
#elif defined(VGA_amd64) || defined(VGA_ppc64)
@@ -65,18 +138,66 @@
#error Unknown platform.
#endif
-#define BITMAP1_UWORD_COUNT (ADDR0_COUNT >> BITS_PER_BITS_PER_UWORD)
+/** Number of UWord's needed to store one bit per address LSB.
+ */
+#define BITMAP1_UWORD_COUNT (1U << (ADDR_LSB_BITS - BITS_PER_BITS_PER_UWORD))
-/* Highest bits of an address that fit into the same UWord of bm0[]. */
-#define UWORD_MSB(a) ((a) & ~(BITS_PER_UWORD - 1))
+/** Mask that has to be applied to an (Addr >> ADDR_IGNORED_BITS) expression
+ * in order to compute the least significant part of an UWord.
+ */
+#define UWORD_LSB_MASK (((UWord)1 << BITS_PER_BITS_PER_UWORD) - 1)
-/* Lowest bits of an address that fit into the same UWord of bm0[]. */
-#define UWORD_LSB(a) ((a) & (BITS_PER_UWORD - 1))
+/** Compute index into bm0[] array.
+ *
+ * @param a Address shifted right ADDR_IGNORED_BITS bits.
+ */
+static __inline__
+UWord uword_msb(const UWord a)
+{
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(a < (1U << ADDR_LSB_BITS));
+#endif
+ return a >> BITS_PER_BITS_PER_UWORD;
+}
-/* Highest address that fits in the same UWord as a. */
-#define UWORD_HIGHEST_ADDRESS(a) ((a) | (BITS_PER_UWORD - 1))
+/** Return the least significant bits.
+ *
+ * @param a Address shifted right ADDR_IGNORED_BITS bits.
+ */
+static __inline__
+UWord uword_lsb(const UWord a)
+{
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(a < (1U << ADDR_LSB_BITS));
+#endif
+ return a & UWORD_LSB_MASK;
+}
+/** Compute the highest address lower than a for which
+ * uword_lsb(address_lsb(a)) == 0.
+ *
+ * @param a Address.
+ */
+static __inline__
+Addr first_address_with_same_uword_lsb(const Addr a)
+{
+ return (a & (~UWORD_LSB_MASK << ADDR_IGNORED_BITS));
+}
+/**
+ * First address that will go in the UWord past the one 'a' goes in.
+ *
+ * @param a Address.
+ */
+static __inline__
+Addr first_address_with_higher_uword_msb(const Addr a)
+{
+ return ((a | ((UWORD_LSB_MASK << ADDR_IGNORED_BITS) | ADDR_IGNORED_MASK))
+ + 1);
+}
+
+
+
/* Local variables. */
static ULong s_bitmap2_creation_count;
@@ -89,56 +210,69 @@
/*********************************************************************/
-/* Lowest level, corresponding to the lowest ADDR0_BITS of an address. */
+/* Lowest level, corresponding to the lowest ADDR_LSB_BITS of an address. */
struct bitmap1
{
UWord bm0_r[BITMAP1_UWORD_COUNT];
UWord bm0_w[BITMAP1_UWORD_COUNT];
};
-static __inline__ UWord bm0_mask(const Addr a)
+static __inline__ UWord bm0_mask(const UWord a)
{
- return ((UWord)1 << UWORD_LSB(a));
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(address_msb(make_address(0, a)) == 0);
+#endif
+ return ((UWord)1 << uword_lsb(a));
}
-static __inline__ void bm0_set(UWord* bm0, const Addr a)
+/** Set the bit corresponding to address a in bitmap bm0. */
+static __inline__ void bm0_set(UWord* bm0, const UWord a)
{
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(a < ADDR0_COUNT);
+ tl_assert(address_msb(make_address(0, a)) == 0);
#endif
- bm0[a >> BITS_PER_BITS_PER_UWORD] |= (UWord)1 << UWORD_LSB(a);
+ bm0[uword_msb(a)] |= (UWord)1 << uword_lsb(a);
}
-/** Set all of the addresses in range [ a1 .. a1 + size [ in bitmap bm0. */
+/**
+ * Set the bits corresponding to all of the addresses in range
+ * [ a << ADDR_IGNORED_BITS .. (a + size) << ADDR_IGNORED_BITS [
+ * in bitmap bm0.
+ */
static __inline__ void bm0_set_range(UWord* bm0,
- const Addr a1, const SizeT size)
+ const UWord a, const SizeT size)
{
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(a1 < ADDR0_COUNT);
tl_assert(size > 0);
- tl_assert(a1 + size <= ADDR0_COUNT);
- tl_assert(UWORD_MSB(a1) == UWORD_MSB(a1 + size - 1));
+ tl_assert(address_msb(make_address(0, a)) == 0);
+ tl_assert(address_msb(make_address(0, a + size - 1)) == 0);
+ tl_assert(uword_msb(a) == uword_msb(a + size - 1));
#endif
- bm0[a1 >> BITS_PER_BITS_PER_UWORD]
- |= (((UWord)1 << size) - 1) << UWORD_LSB(a1);
+ bm0[uword_msb(a)]
+ |= (((UWord)1 << size) - 1) << uword_lsb(a);
}
-static __inline__ void bm0_clear(UWord* bm0, const Addr a)
+/** Clear the bit corresponding to address a in bitmap bm0. */
+static __inline__ void bm0_clear(UWord* bm0, const UWord a)
{
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(a < ADDR0_COUNT);
+ tl_assert(address_msb(make_address(0, a)) == 0);
#endif
- bm0[a >> BITS_PER_BITS_PER_UWORD] &= ~((UWord)1 << UWORD_LSB(a));
+ bm0[uword_msb(a)] &= ~((UWord)1 << uword_lsb(a));
}
-/** Clear all of the addresses in range [ a1 .. a1 + size [ in bitmap bm0. */
+/**
+ * Clear all of the addresses in range
+ * [ a << ADDR_IGNORED_BITS .. (a + size) << ADDR_IGNORED_BITS [
+ * in bitmap bm0.
+ */
static __inline__ void bm0_clear_range(UWord* bm0,
- const Addr a1, const SizeT size)
+ const UWord a, const SizeT size)
{
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(a1 <= ADDR0_COUNT);
- tl_assert(a1 + size <= ADDR0_COUNT);
- tl_assert(size == 0 || UWORD_MSB(a1) == UWORD_MSB(a1 + size - 1));
+ tl_assert(address_msb(make_address(0, a)) == 0);
+ tl_assert(size == 0 || address_msb(make_address(0, a + size - 1)) == 0);
+ tl_assert(size == 0 || uword_msb(a) == uword_msb(a + size - 1));
#endif
/*
* Note: although the expression below yields a correct result even if
@@ -147,31 +281,35 @@
*/
if (size > 0)
{
- bm0[a1 >> BITS_PER_BITS_PER_UWORD]
- &= ~((((UWord)1 << size) - 1) << UWORD_LSB(a1));
+ bm0[uword_msb(a)]
+ &= ~((((UWord)1 << size) - 1) << uword_lsb(a));
}
}
-static __inline__ UWord bm0_is_set(const UWord* bm0, const Addr a)
+/** Test whether the bit corresponding to address a is set in bitmap bm0. */
+static __inline__ UWord bm0_is_set(const UWord* bm0, const UWord a)
{
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(a < ADDR0_COUNT);
+ tl_assert(address_msb(make_address(0, a)) == 0);
#endif
- return (bm0[a >> BITS_PER_BITS_PER_UWORD] & ((UWord)1 << UWORD_LSB(a)));
+ return (bm0[uword_msb(a)] & ((UWord)1 << uword_lsb(a)));
}
-/** Return true if any of the bits [ a1 .. a1+size [ are set in bm0. */
+/**
+ * Return true if a bit corresponding to any of the addresses in range
+ * [ a << ADDR_IGNORED_BITS .. (a + size) << ADDR_IGNORED_BITS [
+ * is set in bm0.
+ */
static __inline__ UWord bm0_is_any_set(const UWord* bm0,
- const Addr a1, const SizeT size)
+ const Addr a, const SizeT size)
{
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(a1 < ADDR0_COUNT);
tl_assert(size > 0);
- tl_assert(a1 + size <= ADDR0_COUNT);
- tl_assert(UWORD_MSB(a1) == UWORD_MSB(a1 + size - 1));
+ tl_assert(address_msb(make_address(0, a)) == 0);
+ tl_assert(address_msb(make_address(0, a + size - 1)) == 0);
+ tl_assert(uword_msb(a) == uword_msb(a + size - 1));
#endif
- return (bm0[a1 >> BITS_PER_BITS_PER_UWORD]
- & ((((UWord)1 << size) - 1) << UWORD_LSB(a1)));
+ return (bm0[uword_msb(a)] & ((((UWord)1 << size) - 1) << uword_lsb(a)));
}
@@ -184,18 +322,10 @@
/* Second level bitmap. */
struct bitmap2
{
- Addr addr; ///< address >> ADDR0_BITS
- int refcnt;
+ Addr addr; ///< address_msb(...)
struct bitmap1 bm1;
};
-/* One node of bitmap::oset. */
-struct bitmap2ref
-{
- Addr addr; ///< address >> ADDR0_BITS
- struct bitmap2* bm2;
-};
-
struct bm_cache_elem
{
Addr a1;
@@ -212,10 +342,12 @@
};
-static struct bitmap2* bm2_new(const UWord a1);
-static struct bitmap2* bm2_make_exclusive(struct bitmap* const bm,
- struct bitmap2ref* const bm2ref);
+static void bm2_clear(struct bitmap2* const bm2);
+static __inline__
+struct bitmap2* bm2_insert(struct bitmap* const bm, const UWord a1);
+
+
/** 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.
*/
@@ -365,26 +497,22 @@
* shared second level bitmap. The bitmap where the returned pointer points
* at may not be modified by the caller.
*
- * @param a1 client address shifted right by ADDR0_BITS.
+ * @param a1 client address shifted right by ADDR_LSB_BITS.
* @param bm bitmap pointer.
*/
static __inline__
const struct bitmap2* bm2_lookup(struct bitmap* const bm, const UWord a1)
{
- struct bitmap2* bm2;
- struct bitmap2ref* bm2ref;
+ struct bitmap2* bm2;
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(bm);
#endif
+
if (! bm_cache_lookup(bm, a1, &bm2))
{
- bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
- if (bm2ref)
- {
- bm2 = bm2ref->bm2;
- }
- bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
+ bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ bm_update_cache(bm, a1, bm2);
}
return bm2;
}
@@ -392,134 +520,95 @@
/** Look up the address a1 in bitmap bm and return a pointer to a second
* level bitmap that is not shared and hence may be modified.
*
- * @param a1 client address shifted right by ADDR0_BITS.
+ * @param a1 client address shifted right by ADDR_LSB_BITS.
* @param bm bitmap pointer.
*/
static __inline__
struct bitmap2*
bm2_lookup_exclusive(struct bitmap* const bm, const UWord a1)
{
- struct bitmap2ref* bm2ref;
struct bitmap2* bm2;
- bm2ref = 0;
- if (bm_cache_lookup(bm, a1, &bm2))
- {
- if (bm2 == 0)
- return 0;
- if (bm2->refcnt > 1)
- {
- bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
- }
- }
- else
- {
- bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
- if (bm2ref == 0)
- return 0;
- bm2 = bm2ref->bm2;
- }
-
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(bm2);
+ tl_assert(bm);
#endif
- if (bm2->refcnt > 1)
+ if (! bm_cache_lookup(bm, a1, &bm2))
{
-#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(bm2ref);
-#endif
- bm2 = bm2_make_exclusive(*(struct bitmap**)&bm, bm2ref);
+ bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
}
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 an uninitialized second level bitmap for the address a1.
*
- * @param a1 client address shifted right by ADDR0_BITS.
* @param bm bitmap pointer.
+ * @param a1 client address shifted right by ADDR_LSB_BITS.
*/
static __inline__
struct bitmap2* bm2_insert(struct bitmap* const bm, const UWord a1)
{
- struct bitmap2ref* bm2ref;
struct bitmap2* bm2;
- s_bitmap2_node_creation_count++;
- bm2ref = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2ref));
- bm2ref->addr = a1;
- bm2 = bm2_new(a1);
- bm2ref->bm2 = bm2;
- VG_(memset)(&bm2->bm1, 0, sizeof(bm2->bm1));
- VG_(OSetGen_Insert)(bm->oset, bm2ref);
-
- bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+#endif
+ s_bitmap2_creation_count++;
+
+ bm2 = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2));
+ bm2->addr = a1;
+ VG_(OSetGen_Insert)(bm->oset, 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.
- */
static __inline__
-struct bitmap2* bm2_insert_addref(struct bitmap* const bm,
- struct bitmap2* const bm2)
+struct bitmap2* bm2_insert_copy(struct bitmap* const bm,
+ struct bitmap2* const bm2)
{
- struct bitmap2ref* bm2ref;
+ struct bitmap2* bm2_copy;
-#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(bm);
- tl_assert(VG_(OSetGen_Lookup)(bm->oset, &bm2->addr) == 0);
-#endif
-
- s_bitmap2_node_creation_count++;
- bm2ref = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2ref));
- bm2ref->addr = bm2->addr;
- bm2ref->bm2 = bm2;
- bm2->refcnt++;
- VG_(OSetGen_Insert)(bm->oset, bm2ref);
-
- bm_update_cache(*(struct bitmap**)&bm, bm2->addr, bm2);
-
- return bm2;
+ bm2_copy = bm2_insert(bm, bm2->addr);
+ VG_(memcpy)(&bm2_copy->bm1, &bm2->bm1, sizeof(bm2->bm1));
+ return bm2_copy;
}
/** Look up the address a1 in bitmap bm, and insert it if not found.
* The returned second level bitmap may not be modified.
*
- * @param a1 client address shifted right by ADDR0_BITS.
+ * @param a1 client address shifted right by ADDR_LSB_BITS.
* @param bm bitmap pointer.
*/
static __inline__
struct bitmap2* bm2_lookup_or_insert(struct bitmap* const bm, const UWord a1)
{
- struct bitmap2ref* bm2ref;
struct bitmap2* bm2;
#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
tl_assert(bm);
#endif
+
if (bm_cache_lookup(bm, a1, &bm2))
{
if (bm2 == 0)
{
bm2 = bm2_insert(bm, a1);
+ bm2_clear(bm2);
}
}
else
{
- bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
- if (bm2ref)
+ bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ if (! bm2)
{
- bm2 = bm2ref->bm2;
- }
- else
- {
bm2 = bm2_insert(bm, a1);
+ bm2_clear(bm2);
}
- bm_update_cache(*(struct bitmap**)&bm, a1, bm2);
+ bm_update_cache(bm, a1, bm2);
}
return bm2;
}
@@ -527,29 +616,14 @@
/** Look up the address a1 in bitmap bm, and insert it if not found.
* The returned second level bitmap may be modified.
*
- * @param a1 client address shifted right by ADDR0_BITS.
+ * @param a1 client address shifted right by ADDR_LSB_BITS.
* @param bm bitmap pointer.
*/
static __inline__
struct bitmap2* bm2_lookup_or_insert_exclusive(struct bitmap* const bm,
const UWord a1)
{
- struct bitmap2* bm2;
-
-#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(bm);
-#endif
- bm2 = (struct bitmap2*)bm2_lookup_or_insert(bm, a1);
-#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
- tl_assert(bm2);
-#endif
- if (bm2->refcnt > 1)
- {
- struct bitmap2ref* bm2ref;
- bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
- bm2 = bm2_make_exclusive(bm, bm2ref);
- }
- return bm2;
+ return bm2_lookup_or_insert(bm, a1);
}
static __inline__
@@ -558,8 +632,14 @@
{
struct bitmap2* bm2;
- bm2 = bm2_lookup_or_insert_exclusive(bm, a1 >> ADDR0_BITS);
- bm0_set_range(bm2->bm1.bm0_r, a1 & ADDR0_MASK, size);
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+#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,
+ SCALED_SIZE(size));
}
static __inline__
@@ -568,33 +648,48 @@
{
struct bitmap2* bm2;
- bm2 = bm2_lookup_or_insert_exclusive(bm, a1 >> ADDR0_BITS);
- bm0_set_range(bm2->bm1.bm0_w, a1 & ADDR0_MASK, size);
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+#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,
+ SCALED_SIZE(size));
}
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, a1 >> ADDR0_BITS);
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+ tl_assert(bm);
+#endif
- return (bm2 && bm0_is_any_set(bm2->bm1.bm0_w, a1 & ADDR0_MASK, size));
+ bm2 = bm2_lookup(bm, address_msb(a));
+ return (bm2
+ && bm0_is_any_set(bm2->bm1.bm0_w,
+ 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, a1 >> ADDR0_BITS);
+#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 & ADDR0_MASK, size)
- | bm0_is_any_set(bm2->bm1.bm0_w, a1 & ADDR0_MASK, 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/DARWIN/drd/pub_drd_bitmap.h
===================================================================
--- branches/DARWIN/drd/pub_drd_bitmap.h 2009-05-10 22:23:48 UTC (rev 9829)
+++ branches/DARWIN/drd/pub_drd_bitmap.h 2009-05-10 22:40:50 UTC (rev 9830)
@@ -34,6 +34,7 @@
#define __PUB_DRD_BITMAP_H
+#include "drd_basics.h" /* DRD_() */
#include "pub_tool_basics.h" /* Addr, SizeT */
@@ -123,8 +124,6 @@
ULong DRD_(bm_get_bitmap_creation_count)(void);
ULong DRD_(bm_get_bitmap2_node_creation_count)(void);
ULong DRD_(bm_get_bitmap2_creation_count)(void);
+ULong DRD_(bm_get_bitmap2_merge_count)(void);
-void DRD_(bm_test)(void);
-
-
#endif /* __PUB_DRD_BITMAP_H */
Modified: branches/DARWIN/drd/scripts/run-splash2
===================================================================
--- branches/DARWIN/drd/scripts/run-splash2 2009-05-10 22:23:48 UTC (rev 9829)
+++ branches/DARWIN/drd/scripts/run-splash2 2009-05-10 22:40:50 UTC (rev 9830)
@@ -59,12 +59,14 @@
p=4
test_output="${1}-drd-with-stack-var-4.out" \
print_runtime_ratio "${avg4}" "${stddev4}" "${vsz4}" "${vszdev4}" \
- "$VG" --tool=drd --check-stack-var=yes "$@" -p${psep}${p} "${test_args}"
+ "$VG" --tool=drd --first-race-only=yes --check-stack-var=yes \
+ "$@" -p${psep}${p} "${test_args}"
p=4
test_output="${1}-drd-without-stack-var-4.out" \
print_runtime_ratio "${avg4}" "${stddev4}" "${vsz4}" "${vszdev4}" \
- "$VG" --tool=drd --check-stack-var=no "$@" -p${psep}${p} "${test_args}"
+ "$VG" --tool=drd --first-race-only=yes --check-stack-var=no \
+ "$@" -p${psep}${p} "${test_args}"
p=4
test_output="${1}-helgrind-4.out" \
@@ -129,25 +131,25 @@
# granularity does ITC use ? And which m4 macro's have been used by ITC as
# implementation of the synchronization primitives ?
#
-# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
-###########################################################################################################################
-# Results: native native native none none DRD DRD HG ITC ITC
-# -p1 -p2 -p4 -p1 -p4 -p4 -p4+f -p4 -p4 -p4+f
-# .........................................................................................................................
-# Cholesky 0.09 11880 0.07 21888 0.65 41883 13.2 4.86 2.5 2.08 19 2.34 13 2.53 29 6.04 239 82
-# FFT 0.03 6560 0.02 15101 0.02 32176 21.0 7.92 20.5 2.41 118 2.81 53 3.06 120 5.42 90 41
-# LU, contiguous 0.07 3968 0.05 12176 0.06 28584 14.8 12.29 21.0 2.62 124 2.87 74 3.16 157 5.53 428 128
-# Ocean, contiguous 0.19 23208 0.18 31744 0.13 48888 6.7 3.75 10.6 2.09 69 2.52 43 2.71 264 5.95 90 28
-# Radix 0.20 15008 0.11 23200 0.11 39592 13.1 4.06 22.6 2.17 56 2.61 41 2.82 111 6.11 222 56
-# Raytrace 0.66 206976 0.47 215168 0.47 232235 8.4 1.22 10.8 1.20 272 1.53 88 1.56 211 3.79 172 53
-# Water-n2 0.19 10560 0.09 26944 0.10 59704 12.9 5.40 24.0 1.79 3793 2.92 621 2.95 109 3.54 189 39
-# Water-sp 0.21 4312 0.10 13400 0.10 29496 10.2 11.41 22.0 2.52 279 3.03 55 5.55 97 4.76 183 34
-# .........................................................................................................................
-# geometric mean 0.14 13360 0.09 26319 0.12 48476 11.9 5.21 14.0 2.06 154 2.53 64 2.88 117 5.05 180 51
-# .........................................................................................................................
+# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
+############################################################################################################################
+# Results: native native native none none DRD DRD HG ITC ITC
+# -p1 -p2 -p4 -p1 -p4 -p4 -p4+f -p4 -p4 -p4+f
+# ..........................................................................................................................
+# Cholesky 0.13 12016 0.06 22016 0.59 41669 11.3 4.46 2.4 2.11 24 2.37 16 2.57 28 6.10 239 82
+# FFT 0.03 6692 0.02 15571 0.02 31962 12.0 7.92 20.0 2.43 121 2.84 54 3.09 117 5.48 90 41
+# LU, contiguous 0.08 ...
[truncated message content] |