You can subscribe to this list here.
| 2002 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
(1) |
Oct
(122) |
Nov
(152) |
Dec
(69) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2003 |
Jan
(6) |
Feb
(25) |
Mar
(73) |
Apr
(82) |
May
(24) |
Jun
(25) |
Jul
(10) |
Aug
(11) |
Sep
(10) |
Oct
(54) |
Nov
(203) |
Dec
(182) |
| 2004 |
Jan
(307) |
Feb
(305) |
Mar
(430) |
Apr
(312) |
May
(187) |
Jun
(342) |
Jul
(487) |
Aug
(637) |
Sep
(336) |
Oct
(373) |
Nov
(441) |
Dec
(210) |
| 2005 |
Jan
(385) |
Feb
(480) |
Mar
(636) |
Apr
(544) |
May
(679) |
Jun
(625) |
Jul
(810) |
Aug
(838) |
Sep
(634) |
Oct
(521) |
Nov
(965) |
Dec
(543) |
| 2006 |
Jan
(494) |
Feb
(431) |
Mar
(546) |
Apr
(411) |
May
(406) |
Jun
(322) |
Jul
(256) |
Aug
(401) |
Sep
(345) |
Oct
(542) |
Nov
(308) |
Dec
(481) |
| 2007 |
Jan
(427) |
Feb
(326) |
Mar
(367) |
Apr
(255) |
May
(244) |
Jun
(204) |
Jul
(223) |
Aug
(231) |
Sep
(354) |
Oct
(374) |
Nov
(497) |
Dec
(362) |
| 2008 |
Jan
(322) |
Feb
(482) |
Mar
(658) |
Apr
(422) |
May
(476) |
Jun
(396) |
Jul
(455) |
Aug
(267) |
Sep
(280) |
Oct
(253) |
Nov
(232) |
Dec
(304) |
| 2009 |
Jan
(486) |
Feb
(470) |
Mar
(458) |
Apr
(423) |
May
(696) |
Jun
(461) |
Jul
(551) |
Aug
(575) |
Sep
(134) |
Oct
(110) |
Nov
(157) |
Dec
(102) |
| 2010 |
Jan
(226) |
Feb
(86) |
Mar
(147) |
Apr
(117) |
May
(107) |
Jun
(203) |
Jul
(193) |
Aug
(238) |
Sep
(300) |
Oct
(246) |
Nov
(23) |
Dec
(75) |
| 2011 |
Jan
(133) |
Feb
(195) |
Mar
(315) |
Apr
(200) |
May
(267) |
Jun
(293) |
Jul
(353) |
Aug
(237) |
Sep
(278) |
Oct
(611) |
Nov
(274) |
Dec
(260) |
| 2012 |
Jan
(303) |
Feb
(391) |
Mar
(417) |
Apr
(441) |
May
(488) |
Jun
(655) |
Jul
(590) |
Aug
(610) |
Sep
(526) |
Oct
(478) |
Nov
(359) |
Dec
(372) |
| 2013 |
Jan
(467) |
Feb
(226) |
Mar
(391) |
Apr
(281) |
May
(299) |
Jun
(252) |
Jul
(311) |
Aug
(352) |
Sep
(481) |
Oct
(571) |
Nov
(222) |
Dec
(231) |
| 2014 |
Jan
(185) |
Feb
(329) |
Mar
(245) |
Apr
(238) |
May
(281) |
Jun
(399) |
Jul
(382) |
Aug
(500) |
Sep
(579) |
Oct
(435) |
Nov
(487) |
Dec
(256) |
| 2015 |
Jan
(338) |
Feb
(357) |
Mar
(330) |
Apr
(294) |
May
(191) |
Jun
(108) |
Jul
(142) |
Aug
(261) |
Sep
(190) |
Oct
(54) |
Nov
(83) |
Dec
(22) |
| 2016 |
Jan
(49) |
Feb
(89) |
Mar
(33) |
Apr
(50) |
May
(27) |
Jun
(34) |
Jul
(53) |
Aug
(53) |
Sep
(98) |
Oct
(206) |
Nov
(93) |
Dec
(53) |
| 2017 |
Jan
(65) |
Feb
(82) |
Mar
(102) |
Apr
(86) |
May
(187) |
Jun
(67) |
Jul
(23) |
Aug
(93) |
Sep
(65) |
Oct
(45) |
Nov
(35) |
Dec
(17) |
| 2018 |
Jan
(26) |
Feb
(35) |
Mar
(38) |
Apr
(32) |
May
(8) |
Jun
(43) |
Jul
(27) |
Aug
(30) |
Sep
(43) |
Oct
(42) |
Nov
(38) |
Dec
(67) |
| 2019 |
Jan
(32) |
Feb
(37) |
Mar
(53) |
Apr
(64) |
May
(49) |
Jun
(18) |
Jul
(14) |
Aug
(53) |
Sep
(25) |
Oct
(30) |
Nov
(49) |
Dec
(31) |
| 2020 |
Jan
(87) |
Feb
(45) |
Mar
(37) |
Apr
(51) |
May
(99) |
Jun
(36) |
Jul
(11) |
Aug
(14) |
Sep
(20) |
Oct
(24) |
Nov
(40) |
Dec
(23) |
| 2021 |
Jan
(14) |
Feb
(53) |
Mar
(85) |
Apr
(15) |
May
(19) |
Jun
(3) |
Jul
(14) |
Aug
(1) |
Sep
(57) |
Oct
(73) |
Nov
(56) |
Dec
(22) |
| 2022 |
Jan
(3) |
Feb
(22) |
Mar
(6) |
Apr
(55) |
May
(46) |
Jun
(39) |
Jul
(15) |
Aug
(9) |
Sep
(11) |
Oct
(34) |
Nov
(20) |
Dec
(36) |
| 2023 |
Jan
(79) |
Feb
(41) |
Mar
(99) |
Apr
(169) |
May
(48) |
Jun
(16) |
Jul
(16) |
Aug
(57) |
Sep
(19) |
Oct
|
Nov
|
Dec
|
| S | M | T | W | T | F | S |
|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
1
(21) |
|
2
(19) |
3
(33) |
4
(24) |
5
(18) |
6
(13) |
7
(22) |
8
(21) |
|
9
(38) |
10
(25) |
11
(20) |
12
(27) |
13
(43) |
14
(9) |
15
(19) |
|
16
(37) |
17
(19) |
18
(13) |
19
(11) |
20
(8) |
21
(11) |
22
(25) |
|
23
(21) |
24
(30) |
25
(18) |
26
(11) |
27
(10) |
28
(14) |
29
(40) |
|
30
(24) |
31
(14) |
|
|
|
|
|
|
From: Nicholas N. <nj...@cs...> - 2008-03-23 22:47:04
|
On Sun, 23 Mar 2008, Nuno Lopes wrote: >>> > Allow me just a last question: is it safe to replace the 't30 = >>> > LDle:I32(t26)' statement with 't30 = 0x4:I32'? Well in general I would >>> > say it is safe, but I dunno about memory-mapped I/O nor if/how valgrind >>> > handles it. Maybe this can be done in only certain architectures? >> >> Difficult question! I would comment first that it might be worth looking >> at the original code to figure out why the compiler put a store and then >> a load from the same location in the next insn. It might be that the >> second instruction (0x80483DC) is a branch target, maybe the top of a >> loop. > > I see that this doesn't work.. If the ptr point to some allocated memory, > other thread may free() it, the ptr will start pointing to freed memory and > thus following read/writes need to be marked as an error. A lesson in binary translation/instrumentation/optimisation: handling correct programs is much easier than handling bogus programs, for exactly this kind of reason! Nick |
|
From: <sv...@va...> - 2008-03-23 18:50:30
|
Author: bart
Date: 2008-03-23 18:50:32 +0000 (Sun, 23 Mar 2008)
New Revision: 7766
Log:
Bitmap lookup cache is now really four elements in size.
Modified:
branches/DRDDEV/exp-drd/drd_bitmap.h
Modified: branches/DRDDEV/exp-drd/drd_bitmap.h
===================================================================
--- branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 18:12:24 UTC (rev 7765)
+++ branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 18:50:32 UTC (rev 7766)
@@ -210,6 +210,49 @@
#endif
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)
@@ -220,25 +263,25 @@
#error Please update the code below.
#endif
#if N_CACHE_ELEM >= 8
- bm->cache[7] = bm->cache[6];
+ bm->cache[7] = bm->cache[6];
#endif
#if N_CACHE_ELEM >= 7
- bm->cache[6] = bm->cache[5];
+ bm->cache[6] = bm->cache[5];
#endif
#if N_CACHE_ELEM >= 6
- bm->cache[5] = bm->cache[4];
+ bm->cache[5] = bm->cache[4];
#endif
#if N_CACHE_ELEM >= 5
- bm->cache[4] = bm->cache[3];
+ bm->cache[4] = bm->cache[3];
#endif
#if N_CACHE_ELEM >= 4
- bm->cache[3] = bm->cache[2];
+ bm->cache[3] = bm->cache[2];
#endif
#if N_CACHE_ELEM >= 3
- bm->cache[2] = bm->cache[1];
+ bm->cache[2] = bm->cache[1];
#endif
#if N_CACHE_ELEM >= 2
- bm->cache[1] = bm->cache[0];
+ bm->cache[1] = bm->cache[0];
#endif
bm->cache[0].a1 = a1;
bm->cache[0].bm2 = bm2;
@@ -289,22 +332,14 @@
struct bitmap2* bm2;
bm2ref = 0;
- if (bm->cache[0].a1 == a1)
+ bm2 = bm_cache_lookup(bm, a1);
+ if (bm2)
{
- bm2 = bm->cache[0].bm2;
if (bm2->refcnt > 1)
{
bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
}
}
- else if (bm->cache[1].a1 == a1)
- {
- bm2 = bm->cache[1].bm2;
- if (bm2->refcnt > 1)
- {
- bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
- }
- }
else
{
bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
@@ -390,16 +425,9 @@
tl_assert(bm);
tl_assert(a1);
- if (a1 == bm->cache[0].a1)
+ bm2 = bm_cache_lookup(bm, a1);
+ if (bm2 == 0)
{
- bm2 = bm->cache[0].bm2;
- }
- else if (a1 == bm->cache[1].a1)
- {
- bm2 = bm->cache[1].bm2;
- }
- else
- {
bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
if (bm2ref)
{
|
|
From: <sv...@va...> - 2008-03-23 18:12:23
|
Author: bart
Date: 2008-03-23 18:12:24 +0000 (Sun, 23 Mar 2008)
New Revision: 7765
Log:
Changed number of cached lookups from two to four.
Modified:
branches/DRDDEV/exp-drd/drd_bitmap.h
Modified: branches/DRDDEV/exp-drd/drd_bitmap.h
===================================================================
--- branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 17:13:30 UTC (rev 7764)
+++ branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 18:12:24 UTC (rev 7765)
@@ -172,7 +172,7 @@
struct bitmap2* bm2;
};
-#define N_CACHE_ELEM 2
+#define N_CACHE_ELEM 4
/* Complete bitmap. */
struct bitmap
@@ -216,7 +216,30 @@
{
tl_assert(bm);
- bm->cache[1] = bm->cache[0];
+#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;
}
|
|
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;
}
|
|
From: <sv...@va...> - 2008-03-23 16:30:51
|
Author: bart
Date: 2008-03-23 15:47:03 +0000 (Sun, 23 Mar 2008)
New Revision: 7762
Log:
Implemented reference counting on DRD's second level bitmap.
Modified:
branches/DRDDEV/coregrind/m_oset.c
branches/DRDDEV/exp-drd/drd_bitmap.c
branches/DRDDEV/exp-drd/drd_bitmap.h
branches/DRDDEV/exp-drd/pub_drd_bitmap.h
branches/DRDDEV/include/pub_tool_oset.h
branches/DRDDEV/memcheck/tests/oset_test.c
Modified: branches/DRDDEV/coregrind/m_oset.c
===================================================================
--- branches/DRDDEV/coregrind/m_oset.c 2008-03-23 14:32:21 UTC (rev 7761)
+++ branches/DRDDEV/coregrind/m_oset.c 2008-03-23 15:47:03 UTC (rev 7762)
@@ -76,9 +76,10 @@
// concurrent uses would screw things up.
#include "pub_core_basics.h"
+#include "pub_core_libcassert.h"
#include "pub_core_libcbase.h"
-#include "pub_core_libcassert.h"
#include "pub_core_libcprint.h"
+#include "pub_core_mallocfree.h"
#include "pub_core_oset.h"
/*--------------------------------------------------------------------*/
@@ -294,7 +295,7 @@
vg_assert(_free);
if (!_cmp) vg_assert(0 == _keyOff); // If no cmp, offset must be zero
- t = _alloc(sizeof(AvlTree));
+ t = VG_(malloc)(sizeof(AvlTree));
t->keyOff = _keyOff;
t->cmp = _cmp;
t->alloc = _alloc;
@@ -344,7 +345,7 @@
vg_assert(sz == t->nElems);
/* Free the AvlTree itself. */
- t->free(t);
+ VG_(free)(t);
}
void VG_(OSetWord_Destroy)(AvlTree* t)
@@ -368,6 +369,11 @@
t->free( node_of_elem(e) );
}
+void* VG_(OSetGen_NodeToElem)(void* node)
+{
+ return elem_of_node(node);
+}
+
/*--------------------------------------------------------------------*/
/*--- Insertion ---*/
/*--------------------------------------------------------------------*/
Modified: branches/DRDDEV/exp-drd/drd_bitmap.c
===================================================================
--- branches/DRDDEV/exp-drd/drd_bitmap.c 2008-03-23 14:32:21 UTC (rev 7761)
+++ branches/DRDDEV/exp-drd/drd_bitmap.c 2008-03-23 15:47:03 UTC (rev 7762)
@@ -36,19 +36,26 @@
#include "drd_suppression.h"
-// Local constants.
+/* Forward declarations. */
-static ULong s_bitmap_creation_count;
+struct bitmap2;
-// Local function declarations.
+/* Local function declarations. */
+static void* bm2ref_new(const SizeT size);
+static void bm2ref_del(void* node);
static void bm2_merge(struct bitmap2* const bm2l,
const struct bitmap2* const bm2r);
-// Function definitions.
+/* Local constants. */
+static ULong s_bitmap_creation_count;
+
+
+/* Function definitions. */
+
struct bitmap* bm_new()
{
struct bitmap* bm;
@@ -60,8 +67,9 @@
bm = VG_(malloc)(sizeof(*bm));
tl_assert(bm);
bm->last_lookup_a1 = 0;
- bm->last_lookup_result = 0;
- bm->oset = VG_(OSetGen_Create)(0, 0, VG_(malloc), VG_(free));
+ bm->last_lookup_bm2ref = 0;
+ bm->last_lookup_bm2 = 0;
+ bm->oset = VG_(OSetGen_Create)(0, 0, bm2ref_new, bm2ref_del);
s_bitmap_creation_count++;
@@ -102,7 +110,7 @@
b_next = a2;
}
- bm2 = bm2_lookup_or_insert(bm, b1);
+ bm2 = bm2_lookup_or_insert_exclusive(bm, b1);
tl_assert(bm2);
if ((bm2->addr << ADDR0_BITS) < a1)
@@ -145,7 +153,7 @@
{
struct bitmap2* bm2;
- bm2 = bm2_lookup_or_insert(bm, a1 >> ADDR0_BITS);
+ bm2 = bm2_lookup_or_insert_exclusive(bm, a1 >> ADDR0_BITS);
bm0_set_range(bm2->bm1.bm0_r, a1 & ADDR0_MASK, size);
}
@@ -155,7 +163,7 @@
{
struct bitmap2* bm2;
- bm2 = bm2_lookup_or_insert(bm, a1 >> ADDR0_BITS);
+ bm2 = bm2_lookup_or_insert_exclusive(bm, a1 >> ADDR0_BITS);
bm0_set_range(bm2->bm1.bm0_w, a1 & ADDR0_MASK, size);
}
@@ -283,7 +291,7 @@
for (b = a1; b < a2; b = b_next)
{
- struct bitmap2* bm2 = bm2_lookup(bm, b >> ADDR0_BITS);
+ const struct bitmap2* bm2 = bm2_lookup(bm, b >> ADDR0_BITS);
b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
if (b_next > a2)
@@ -338,9 +346,9 @@
const Addr a,
const BmAccessTypeT access_type)
{
- struct bitmap2* p2;
- struct bitmap1* p1;
- UWord* p0;
+ const struct bitmap2* p2;
+ const struct bitmap1* p1;
+ const UWord* p0;
const UWord a0 = a & ADDR0_MASK;
tl_assert(bm);
@@ -380,12 +388,16 @@
void bm_clear_all(const struct bitmap* const bm)
{
struct bitmap2* bm2;
+ struct bitmap2ref* bm2ref;
VG_(OSetGen_ResetIter)(bm->oset);
- for ( ; (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; )
+ for ( ; (bm2ref = VG_(OSetGen_Next)(bm->oset)) != 0; )
{
- struct bitmap1* const bm1 = &bm2->bm1;
+ struct bitmap1* bm1;
+
+ bm2 = bm2ref->bm2;
+ bm1 = &bm2->bm1;
tl_assert(bm1);
VG_(memset)(&bm1->bm0_r[0], 0, sizeof(bm1->bm0_r));
VG_(memset)(&bm1->bm0_w[0], 0, sizeof(bm1->bm0_w));
@@ -404,7 +416,7 @@
for (b = a1; b < a2; b = b_next)
{
- struct bitmap2* const p2 = bm2_lookup(bm, b >> ADDR0_BITS);
+ struct bitmap2* const p2 = bm2_lookup_exclusive(bm, b >> ADDR0_BITS);
b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
if (b_next > a2)
@@ -456,7 +468,7 @@
for (b = a1; b < a2; b = b_next)
{
- struct bitmap2* bm2 = bm2_lookup(bm, b >> ADDR0_BITS);
+ const struct bitmap2* bm2 = bm2_lookup(bm, b >> ADDR0_BITS);
b_next = (b & ~ADDR0_MASK) + ADDR0_COUNT;
if (b_next > a2)
@@ -516,7 +528,7 @@
Bool bm_aligned_load_has_conflict_with(const struct bitmap* const bm,
const Addr a1, const SizeT size)
{
- struct bitmap2* bm2;
+ const struct bitmap2* bm2;
bm2 = bm2_lookup(bm, a1 >> ADDR0_BITS);
@@ -527,7 +539,7 @@
Bool bm_aligned_store_has_conflict_with(const struct bitmap* const bm,
const Addr a1, const SizeT size)
{
- struct bitmap2* bm2;
+ const struct bitmap2* bm2;
bm2 = bm2_lookup(bm, a1 >> ADDR0_BITS);
@@ -623,23 +635,28 @@
const struct bitmap* const rhs)
{
struct bitmap2* bm2l;
+ const struct bitmap2ref* bm2l_ref;
const struct bitmap2* bm2r;
+ const struct bitmap2ref* bm2r_ref;
// First step: allocate any missing bitmaps in *lhs.
VG_(OSetGen_ResetIter)(rhs->oset);
- for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; )
+ for ( ; (bm2r_ref = VG_(OSetGen_Next)(rhs->oset)) != 0; )
{
+ bm2r = bm2r_ref->bm2;
bm2_lookup_or_insert(lhs, bm2r->addr);
}
VG_(OSetGen_ResetIter)(lhs->oset);
VG_(OSetGen_ResetIter)(rhs->oset);
- for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; )
+ for ( ; (bm2r_ref = VG_(OSetGen_Next)(rhs->oset)) != 0; )
{
+ bm2r = bm2r_ref->bm2;
do
{
- bm2l = VG_(OSetGen_Next)(lhs->oset);
+ bm2l_ref = VG_(OSetGen_Next)(lhs->oset);
+ bm2l = bm2l_ref->bm2;
} while (bm2l->addr < bm2r->addr);
tl_assert(bm2l->addr == bm2r->addr);
@@ -662,18 +679,24 @@
for (;;)
{
- const struct bitmap2* bm2l = VG_(OSetGen_Next)(lhs->oset);
- const struct bitmap2* bm2r = VG_(OSetGen_Next)(rhs->oset);
+ 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;
while (bm2l && bm2r && bm2l->addr != bm2r->addr)
{
if (bm2l->addr < bm2r->addr)
- bm2l = VG_(OSetGen_Next)(lhs->oset);
+ bm2l = (bm2l_ref = VG_(OSetGen_Next)(lhs->oset))->bm2;
else
- bm2r = VG_(OSetGen_Next)(rhs->oset);
+ bm2r = (bm2r_ref = VG_(OSetGen_Next)(rhs->oset))->bm2;
}
if (bm2l == 0 || bm2r == 0)
break;
@@ -705,13 +728,17 @@
void bm_print(const struct bitmap* const bm)
{
struct bitmap2* bm2;
+ struct bitmap2ref* bm2ref;
VG_(OSetGen_ResetIter)(bm->oset);
- for ( ; (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; )
+ for ( ; (bm2ref = VG_(OSetGen_Next)(bm->oset)) != 0; )
{
- const struct bitmap1* const bm1 = &bm2->bm1;
+ const struct bitmap1* bm1;
unsigned b;
+
+ bm2 = bm2ref->bm2;
+ bm1 = &bm2->bm1;
for (b = 0; b < ADDR0_COUNT; b++)
{
const Addr a = (bm2->addr << ADDR0_BITS) | b;
@@ -738,6 +765,83 @@
return s_bitmap2_creation_count;
}
+/** Allocate memory for a tree node, without initializing the tree node. */
+static void* bm2ref_new(const SizeT size)
+{
+ void* node = VG_(malloc)(size);
+ return node;
+}
+
+/** Deallocate the tree node, decrement the reference count of the second
+ * level bitmap and deallocate the second level bitmap memory if the reference
+ * count reached zero.
+ */
+static void bm2ref_del(void* node)
+{
+ struct bitmap2* bm2;
+ struct bitmap2ref* bm2ref;
+
+ bm2ref = VG_(OSetGen_NodeToElem)(node);
+ tl_assert(bm2ref);
+ bm2 = bm2ref->bm2;
+ tl_assert(bm2->refcnt >= 1);
+ if (--bm2->refcnt == 0)
+ {
+ VG_(free)(bm2);
+ }
+ VG_(free)(node);
+}
+
+/** Allocate and initialize a second level bitmap. */
+static struct bitmap2* bm2_new(const UWord a1)
+{
+ struct bitmap2* bm2;
+
+ bm2 = VG_(malloc)(sizeof(*bm2));
+ bm2->addr = a1;
+ bm2->refcnt = 1;
+
+ s_bitmap2_creation_count++;
+
+ return bm2;
+}
+
+/** 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)
+{
+ 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->last_lookup_a1 = a1;
+ bm->last_lookup_bm2ref = bm2ref;
+ bm->last_lookup_bm2 = bm2_copy;
+
+ return bm2_copy;
+}
+
static void bm2_merge(struct bitmap2* const bm2l,
const struct bitmap2* const bm2r)
{
@@ -764,7 +868,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: branches/DRDDEV/exp-drd/drd_bitmap.h
===================================================================
--- branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 14:32:21 UTC (rev 7761)
+++ branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 15:47:03 UTC (rev 7762)
@@ -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,58 +151,154 @@
/*********************************************************************/
+/* Second level bitmap. */
struct bitmap2
{
- Addr addr; ///< address >> ADDR0_BITS
+ Addr addr; ///< address >> ADDR0_BITS
+ int refcnt;
struct bitmap1 bm1;
};
+/* One node of bitmap::oset. */
+struct bitmap2ref
+{
+ Addr addr; ///< address >> ADDR0_BITS
+ struct bitmap2* bm2;
+};
+
/* Complete bitmap. */
struct bitmap
{
- Addr last_lookup_a1;
- struct bitmap2* last_lookup_result;
- OSet* oset;
+ Addr last_lookup_a1;
+ struct bitmap2ref* last_lookup_bm2ref;
+ struct bitmap2* last_lookup_bm2;
+ OSet* oset;
};
-/** Look up the address a1 in bitmap bm.
+
+static struct bitmap2* bm2_new(const UWord a1);
+static struct bitmap2* bm2_make_exclusive(struct bitmap* const bm,
+ struct bitmap2ref* const bm2ref);
+
+
+#if 0
+/** Bitmap invariant check.
+ *
+ * @return 1 if the invariant is satisfied, 0 if not.
+ */
+static __inline__
+int bm_check(const struct bitmap* const bm)
+{
+ 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)
+ );
+}
+#endif
+
+/** 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.
+ *
* @param a1 client address shifted right by ADDR0_BITS.
* @param bm bitmap pointer.
*/
static __inline__
-struct bitmap2* bm2_lookup(const struct bitmap* const bm, const UWord a1)
+const struct bitmap2* bm2_lookup(const struct bitmap* const bm, const UWord a1)
{
- struct bitmap2* result;
+ struct bitmap2ref* bm2ref;
+
+ tl_assert(bm);
if (a1 == bm->last_lookup_a1)
{
- return bm->last_lookup_result;
+ return bm->last_lookup_bm2;
}
- result = VG_(OSetGen_Lookup)(bm->oset, &a1);
- if (result)
+ 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_result = result;
+ ((struct bitmap*)bm)->last_lookup_bm2ref = bm2ref;
+ ((struct bitmap*)bm)->last_lookup_bm2 = bm2;
+ return bm2;
}
- return result;
+ return 0;
}
+/** 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 bm bitmap pointer.
+ */
static __inline__
+struct bitmap2*
+bm2_lookup_exclusive(const struct bitmap* const bm, const UWord a1)
+{
+ struct bitmap2ref* bm2ref;
+ struct bitmap2* bm2;
+
+ if (bm->last_lookup_a1 == a1)
+ {
+ if (bm->last_lookup_bm2->refcnt == 1)
+ {
+ return bm->last_lookup_bm2;
+ }
+ else
+ {
+ bm2 = bm2_make_exclusive((struct bitmap*)bm, bm->last_lookup_bm2ref);
+ return bm2;
+ }
+ }
+ else
+ {
+ bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ if (bm2ref)
+ {
+ bm2 = bm2ref->bm2;
+ if (bm2->refcnt > 1)
+ {
+ bm2 = bm2_make_exclusive((struct bitmap*)bm, bm2ref);
+ }
+ return bm2;
+ }
+ }
+ return 0;
+}
+
+/** Look up the address a1 in bitmap bm. The returned second level bitmap has
+ * reference count one and hence may be modified.
+ *
+ * @param a1 client address shifted right by ADDR0_BITS.
+ * @param bm bitmap pointer.
+ */
+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));
- bm2->addr = a1;
+ struct bitmap2ref* bm2ref;
+ struct bitmap2* bm2;
+
+ 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, bm2);
+ VG_(OSetGen_Insert)(bm->oset, bm2ref);
((struct bitmap*)bm)->last_lookup_a1 = a1;
- ((struct bitmap*)bm)->last_lookup_result = bm2;
-
- s_bitmap2_creation_count++;
-
+ ((struct bitmap*)bm)->last_lookup_bm2ref = bm2ref;
+ ((struct bitmap*)bm)->last_lookup_bm2 = bm2;
+
return bm2;
}
/** 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 bm bitmap pointer.
@@ -211,22 +307,54 @@
struct bitmap2* bm2_lookup_or_insert(const struct bitmap* const bm,
const UWord a1)
{
+ struct bitmap2ref* bm2ref;
struct bitmap2* bm2;
+ tl_assert(bm);
+ tl_assert(a1);
if (a1 == bm->last_lookup_a1)
{
- return bm->last_lookup_result;
+ return bm->last_lookup_bm2;
}
- bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
- if (bm2 == 0)
+ bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ if (bm2ref == 0)
{
bm2 = bm2_insert(bm, a1);
}
- ((struct bitmap*)bm)->last_lookup_a1 = a1;
- ((struct bitmap*)bm)->last_lookup_result = 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;
+ }
return bm2;
}
+/** 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 bm bitmap pointer.
+ */
+static __inline__
+struct bitmap2* bm2_lookup_or_insert_exclusive(struct bitmap* const bm,
+ const UWord a1)
+{
+ struct bitmap2* bm2;
-#endif /* __DRD_BITMAP3_H */
+ tl_assert(bm);
+ bm2 = (struct bitmap2*)bm2_lookup_or_insert(bm, a1);
+ tl_assert(bm2);
+ if (bm2->refcnt > 1)
+ {
+ struct bitmap2ref* bm2ref;
+ bm2ref = VG_(OSetGen_Lookup)(bm->oset, &a1);
+ bm2 = bm2_make_exclusive(bm, bm2ref);
+ }
+ return bm2;
+}
+
+
+#endif /* __DRD_BITMAP_H */
Modified: branches/DRDDEV/exp-drd/pub_drd_bitmap.h
===================================================================
--- branches/DRDDEV/exp-drd/pub_drd_bitmap.h 2008-03-23 14:32:21 UTC (rev 7761)
+++ branches/DRDDEV/exp-drd/pub_drd_bitmap.h 2008-03-23 15:47:03 UTC (rev 7762)
@@ -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 */
Modified: branches/DRDDEV/include/pub_tool_oset.h
===================================================================
--- branches/DRDDEV/include/pub_tool_oset.h 2008-03-23 14:32:21 UTC (rev 7761)
+++ branches/DRDDEV/include/pub_tool_oset.h 2008-03-23 15:47:03 UTC (rev 7762)
@@ -187,6 +187,7 @@
extern void VG_(OSetGen_Destroy) ( OSet* os );
extern void* VG_(OSetGen_AllocNode) ( OSet* os, SizeT elemSize );
extern void VG_(OSetGen_FreeNode) ( OSet* os, void* elem );
+extern void* VG_(OSetGen_NodeToElem)( void* node );
/*--------------------------------------------------------------------*/
/*--- Operations on OSets (Gen) ---*/
Modified: branches/DRDDEV/memcheck/tests/oset_test.c
===================================================================
--- branches/DRDDEV/memcheck/tests/oset_test.c 2008-03-23 14:32:21 UTC (rev 7761)
+++ branches/DRDDEV/memcheck/tests/oset_test.c 2008-03-23 15:47:03 UTC (rev 7762)
@@ -28,6 +28,9 @@
#define vgPlain_memset memset
#define vgPlain_memcpy memcpy
+static void* VG_(malloc)( SizeT nbytes ) { return malloc(nbytes); }
+static void VG_(free) ( void* p ) { return free(p); }
+
#include "coregrind/m_oset.c"
#define NN 1000 // Size of OSets being created
|
|
From: <sv...@va...> - 2008-03-23 16:18:26
|
Author: bart
Date: 2008-03-23 16:15:43 +0000 (Sun, 23 Mar 2008)
New Revision: 7763
Log:
bm_merge2() now shares unmodified second level bitmaps instead of copying these.
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 15:47:03 UTC (rev 7762)
+++ branches/DRDDEV/exp-drd/drd_bitmap.c 2008-03-23 16:15:43 UTC (rev 7763)
@@ -631,37 +631,35 @@
bm2->oset = tmp;
}
+/** Merge bitmaps *lhs and *rhs into *lhs. */
void bm_merge2(struct bitmap* const lhs,
const struct bitmap* const rhs)
{
struct bitmap2* bm2l;
- const struct bitmap2ref* bm2l_ref;
- const struct bitmap2* bm2r;
+ struct bitmap2ref* bm2l_ref;
+ struct bitmap2* bm2r;
const struct bitmap2ref* bm2r_ref;
- // First step: allocate any missing bitmaps in *lhs.
VG_(OSetGen_ResetIter)(rhs->oset);
- for ( ; (bm2r_ref = VG_(OSetGen_Next)(rhs->oset)) != 0; )
- {
- bm2r = bm2r_ref->bm2;
- bm2_lookup_or_insert(lhs, bm2r->addr);
- }
- VG_(OSetGen_ResetIter)(lhs->oset);
- VG_(OSetGen_ResetIter)(rhs->oset);
-
for ( ; (bm2r_ref = VG_(OSetGen_Next)(rhs->oset)) != 0; )
{
bm2r = bm2r_ref->bm2;
- do
+ bm2l_ref = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr);
+ if (bm2l_ref)
{
- bm2l_ref = VG_(OSetGen_Next)(lhs->oset);
bm2l = bm2l_ref->bm2;
- } while (bm2l->addr < bm2r->addr);
-
- tl_assert(bm2l->addr == bm2r->addr);
-
- bm2_merge(bm2l, bm2r);
+ if (bm2l != bm2r)
+ {
+ if (bm2l->refcnt > 1)
+ bm2l = bm2_make_exclusive(lhs, bm2l_ref);
+ bm2_merge(bm2l, bm2r);
+ }
+ }
+ else
+ {
+ bm2_insert_addref(lhs, bm2r);
+ }
}
}
@@ -847,7 +845,10 @@
{
unsigned k;
+ tl_assert(bm2l);
+ tl_assert(bm2r);
tl_assert(bm2l->addr == bm2r->addr);
+ tl_assert(bm2l->refcnt == 1);
for (k = 0; k < BITMAP1_UWORD_COUNT; k++)
{
Modified: branches/DRDDEV/exp-drd/drd_bitmap.h
===================================================================
--- branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 15:47:03 UTC (rev 7762)
+++ branches/DRDDEV/exp-drd/drd_bitmap.h 2008-03-23 16:15:43 UTC (rev 7763)
@@ -297,6 +297,30 @@
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(const struct bitmap* const bm,
+ struct bitmap2* const bm2)
+{
+ struct bitmap2ref* bm2ref;
+
+ tl_assert(bm);
+ 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;
+
+ return bm2;
+}
+
/** Look up the address a1 in bitmap bm, and insert it if not found.
* The returned second level bitmap may not be modified.
*
|
|
From: Nuno L. <nun...@sa...> - 2008-03-23 15:32:03
|
Thank you both for your comprehensive answers. Some comments inline:
>> > ------ IMark(0x80483D5, 7) ------
>> > PUT(60) = 0x80483D5:I32
>> > t137 = Left32(t130)
>> > t26 = Add32(t25,0xFFFFFFF8:I32)
>> > t139 = CmpNEZ32(t137)
>> > DIRTY t139 RdFX-gst(16,4) RdFX-gst(60,4) :::
>> > MC_(helperc_value_check4_fail){0x38006920}() DIRTY 1:I1 RdFX-gst(16,4)
>> > RdFX-gst(60,4) :::
>> > MC_(helperc_STOREV32le)[rp=2]{0x38006d40}(t26,0x0:I32)
>> > STle(t26) = 0x4:I32
>
>> > At first glance I would say that the first PUT(60) could be removed,
>> > right? It is basically a dead store (assuming it can only be read/write
>> > with GET/PUT). I didn't check further why the redudant removal
>> > optimization doesn't pick this, so I'm checking here first if this is
>> > sane.
>>
>> It's not removed because there's another statement (the STle) between it
>> and the subsequent PUT(60) that could cause a memory exception. A signal
>> handler for such an exception might inspect the %eip value, so it has to
>> be
>> up-to-date. Annoying, because it's so unlikely, but necessary.
>
> Yes. But not only for the STle, also for the call to
> MC_(helperc_value_check4_fail).
>
> If you look at struct VexGuestX86State in libvex_guest_x86.h, you can
> see that offset 60 is guest_EIP (the program counter). So the PUT is
> updating the simulated program counter, so it is up to date should the
> store generate an exception, but also (importantly) so that if
> MC_(helperc_value_check4_fail) needs to make a stack backtrace, it will
> start from the right point.
That makes sense. So there's nothing to do here :S
>> > Second question is: can the last memcheck check be removed? i.e. the
>> > last
>> > call to helperc_LOADV32le() is redudant, since it has already done a
>> > store to that location and thus it knows that the operation is safe.
>> > Can
>> > this call be removed? And what value do I assign to t144 then?
>> > VA_BITS32_DEFINED? (I'm just considering the simpler case where the
>> > #store bits >= #load bits).
>>
>> I think it is redundant. Since 0x0 (which is VA_BITS32_DEFINED) was the
>> shadow store value, you'd assign 0x0 to t144. And you're right that you
>> could do likewise if t144 was smaller than 32 bits.
>>
>> > Allow me just a last question: is it safe to replace the 't30 =
>> > LDle:I32(t26)' statement with 't30 = 0x4:I32'? Well in general I would
>> > say it is safe, but I dunno about memory-mapped I/O nor if/how valgrind
>> > handles it. Maybe this can be done in only certain architectures?
>>
>> If we're optimising away the shadow load, maybe it's reasonable to
>> optimise
>> away the real load, but I'm really not sure about that one. Julian might
>> have more to add.
>
> Difficult question! I would comment first that it might be worth looking
> at the original code to figure out why the compiler put a store and then
> a load from the same location in the next insn. It might be that the
> second instruction (0x80483DC) is a branch target, maybe the top of a
> loop.
>
> So is it safe to remove the real and shadow load and forward values
> directly to it from the real and shadow store? Well, that would probably
> work _most_ of the time, but sounds dangerous if multiple threads are
> doing spinlocks or something like that - then it might be that changing
> the number of memory references might have some bad effect.
I see that this doesn't work.. If the ptr point to some allocated memory,
other thread may free() it, the ptr will start pointing to freed memory and
thus following read/writes need to be marked as an error.
So, no luck this time. I'll keep searching :)
Thanks,
Nuno
|
|
From: <sv...@va...> - 2008-03-23 14:32:24
|
Author: bart Date: 2008-03-23 14:32:21 +0000 (Sun, 23 Mar 2008) New Revision: 7761 Log: Updated documentation. Modified: trunk/exp-drd/TODO.txt trunk/exp-drd/docs/README.txt Modified: trunk/exp-drd/TODO.txt =================================================================== --- trunk/exp-drd/TODO.txt 2008-03-23 13:17:52 UTC (rev 7760) +++ trunk/exp-drd/TODO.txt 2008-03-23 14:32:21 UTC (rev 7761) @@ -4,26 +4,15 @@ Data-race detection algorithm ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -- Implement segment merging, such that the number of segments per thread - remains limited even when there is no synchronization between threads. -- Add locking order checking. -- Discuss on the Valgrind mailing list how to make it possible to call - POSIX thread synchronization primitives from client code (drd_intercepts.c) - without triggering Valgrind's redirection mechanism. - Make sure -v works again with exp-drd. +- Add locking order checking. - Continue the discussion on the Valgrind mailing list about docbook and 'make dist'. -- Continue the discussion on the Valgrind mailing list about -Wformat. -- Enable format string checking for DRD during compilation. -- Propose to modify tl_assert() / vg_assert() such that it uses - __builtin_expect. - Explain on the Valgrind mailing list the difference between a bus lock and acquire / release labels. - Add configure tests for the name of the 'kind' member in pthread_mutex_t. - Find out why a race is reported on std::string::string(std::string const&) (stc test case 16). -- Find out why no races are reported on matinv_openmp.c when "private(k)" is - removed. - Add support for objects that are shared over threads and that use reference counting, e.g. std::string -- no races should be reported on the reference count. @@ -35,18 +24,14 @@ - Find out why no line number or variable name information is printed for races detected in parallel sections of OpenMP programs. An example: ./vg-in-place --tool=exp-drd exp-drd/tests/omp_prime 4 -t 2 -- Find a way for suppressing races reported on _IO_2_1_stdout. This race is - triggered by calling printf() from more than one thread. Examples (AMD64): - ./vg-in-place --tool=exp-drd exp-drd/tests/tc21_pthonce - Find out why 'matinv 400' runs faster in 32-bit mode than in 64-bit mode on the same CPU. - testing on PPC and AIX (current implementation is only tested on X86 and AMD64). - Convert the array in drd_thread.c with thread information into an OSet. -- Performance testing and tuning. -- Optimize run time of the following test case: - ./vg-in-place --tool=exp-drd exp-drd/tests/matinv 100 +- Performance testing and tuning, a.o. for kate / knode / open office / matinv. + Testing ~~~~~~~ - testing with more complex multithreaded test programs. @@ -68,13 +53,3 @@ ~~~~~~~~~~~ - Does not work with a glibc library compiled with linuxthreads -- NPTL is required for proper operation. - - -Known bugs -~~~~~~~~~~ -- Gets killed by the OOM handler for realistically sized applications, - e.g. knode and OpenOffice. -- [x86_64] Reports "Allocation context: unknown" for BSS symbols on AMD64 - (works fine on i386). This is a bug in Valgrind's debug info reader - -- VG_(find_seginfo)() returns NULL for BSS symbols on x86_64. Not yet in - the KDE bug tracking system. Modified: trunk/exp-drd/docs/README.txt =================================================================== --- trunk/exp-drd/docs/README.txt 2008-03-23 13:17:52 UTC (rev 7760) +++ trunk/exp-drd/docs/README.txt 2008-03-23 14:32:21 UTC (rev 7761) @@ -301,10 +301,7 @@ Future DRD Versions ------------------- The following may be expected in future versions of DRD: -* Drastically reduced memory consumption, such that realistic applications can - be analyzed with DRD. * A lock dependency analyzer, as a help in deadlock prevention. -* Faster operation. * More extensive documentation. * Support for PowerPC CPU's. |
|
From: Bart V. A. <bar...@gm...> - 2008-03-23 14:21:20
|
Hello Julian,
Can you please have a look at the following:
$ ls -l /var/run/nscd/passwd
-rw------- 1 root root 217016 2008-03-23 15:11 /var/run/nscd/passwd
$ ./vg-in-place --tool=none knode
...
--4396-- WARNING: Serious error when reading debug info
--4396-- When reading debug info from /var/run/nscd/passwd:
--4396-- can't open file to inspect ELF header
...
>From the output of strace -f knode:
...
[pid 4457] socket(PF_FILE, SOCK_STREAM, 0) = 10
[pid 4457] fcntl(10, F_SETFL, O_RDWR|O_NONBLOCK) = 0
[pid 4457] connect(10, {sa_family=AF_FILE,
path="/var/run/nscd/socket"}, 110) = 0
...
Thanks,
Bart.
|
|
From: <sv...@va...> - 2008-03-23 13:18:13
|
Author: sewardj
Date: 2008-03-23 13:17:52 +0000 (Sun, 23 Mar 2008)
New Revision: 7760
Log:
Specialise implementation of the type "WordBag" so that no dynamic
memory allocation is required in the common case where there is only
one unique value in the bag. Unfortunately this has the side effect
of making the type non-abstract.
Modified:
branches/HGDEV/helgrind/hg_main.c
branches/HGDEV/helgrind/hg_wordfm.c
branches/HGDEV/helgrind/hg_wordfm.h
Modified: branches/HGDEV/helgrind/hg_main.c
===================================================================
--- branches/HGDEV/helgrind/hg_main.c 2008-03-23 08:03:27 UTC (rev 7759)
+++ branches/HGDEV/helgrind/hg_main.c 2008-03-23 13:17:52 UTC (rev 7760)
@@ -58,9 +58,6 @@
- Fix command line ordering assumptions for --ignore-i= vs --ignore-n=
- - Specialise the heldBy field in Locks for the case where the lock
- is only held by one thread.
-
STUFF I DON'T UNDERSTAND:
Make sense of ignore-n/ignore-i. What exactly does this do?
@@ -462,20 +459,22 @@
ExeContext* appeared_at;
/* If the lock is held, place where the lock most recently made
an unlocked->locked transition. Must be sync'd with .heldBy:
- either both NULL or both non-NULL. */
+ if acquired_at is NULL then .heldBy must be empty, and vice
+ versa. */
ExeContext* acquired_at;
/* USEFUL-STATIC */
Addr guestaddr; /* Guest address of lock */
LockKind kind; /* what kind of lock this is */
/* USEFUL-DYNAMIC */
- Bool heldW;
- WordBag* heldBy; /* bag of threads that hold this lock */
- /* .heldBy is NULL: lock is unheld, and .heldW is meaningless
- but arbitrarily set to False
- .heldBy is non-NULL:
- .heldW is True: lock is w-held by threads in heldBy
- .heldW is False: lock is r-held by threads in heldBy
- Either way, heldBy may not validly be an empty Bag.
+ Bool heldW;
+ WordBag heldBy; /* bag of threads that hold this lock */
+ /* HG_(isEmptyBag)(.heldBy) == True
+ means: lock is unheld, and heldW is meaningless
+ but arbitrarily set to False
+ HG_(isEmptyBag)(.heldBy) == False
+ means:
+ lock is w-held by threads in .heldBy if .heldW is True
+ lock is r-held by threads in .heldBy if .heldW is False
for LK_nonRec, r-holdings are not allowed, and w-holdings may
only have sizeTotal(heldBy) == 1
@@ -483,7 +482,8 @@
for LK_mbRec, r-holdings are not allowed, and w-holdings may
only have sizeUnique(heldBy) == 1
- for LK_rdwr, w-holdings may only have sizeTotal(heldBy) == 1 */
+ for LK_rdwr, w-holdings may only have sizeTotal(.heldBy) == 1
+ */
}
Lock;
@@ -847,7 +847,7 @@
lock->guestaddr = guestaddr;
lock->kind = kind;
lock->heldW = False;
- lock->heldBy = NULL;
+ HG_(initBag)(&lock->heldBy, hg_zalloc, hg_free);
tl_assert(is_sane_LockN(lock));
admin_locks = lock;
return lock;
@@ -894,7 +894,7 @@
case LK_mbRec: case LK_nonRec: case LK_rdwr: break;
default: return False;
}
- if (lock->heldBy == NULL) {
+ if (HG_(isEmptyBag)(&lock->heldBy)) {
if (lock->acquired_at != NULL) return False;
/* Unheld. We arbitrarily require heldW to be False. */
return !lock->heldW;
@@ -902,18 +902,13 @@
if (lock->acquired_at == NULL) return False;
}
- /* If heldBy is non-NULL, we require it to contain at least one
- thread. */
- if (HG_(isEmptyBag)(lock->heldBy))
- return False;
-
/* Lock is either r- or w-held. */
- if (!is_sane_Bag_of_Threads(lock->heldBy))
+ if (!is_sane_Bag_of_Threads(&lock->heldBy))
return False;
if (lock->heldW) {
/* Held in write-mode */
if ((lock->kind == LK_nonRec || lock->kind == LK_rdwr)
- && !HG_(isSingletonTotalBag)(lock->heldBy))
+ && !HG_(isSingletonTotalBag)(&lock->heldBy))
return False;
} else {
/* Held in read-mode */
@@ -937,14 +932,13 @@
/* Release storage for a Lock. Also release storage in .heldBy, if
any. */
-static void del_LockN ( Lock* lk )
-{
- tl_assert(is_sane_LockN(lk));
- if (lk->heldBy)
- HG_(deleteBag)( lk->heldBy );
- VG_(memset)(lk, 0xAA, sizeof(*lk));
- hg_free(lk);
-}
+//static void del_LockN ( Lock* lk )
+//{
+// tl_assert(is_sane_LockN(lk));
+// HG_(finiBag)( &lk->heldBy );
+// VG_(memset)(lk, 0xAA, sizeof(*lk));
+// hg_free(lk);
+//}
/* Update 'lk' to reflect that 'thr' now has a write-acquisition of
it. This is done strictly: only combinations resulting from
@@ -961,38 +955,39 @@
acquired, so as to produce better lock-order error messages. */
if (lk->acquired_at == NULL) {
ThreadId tid;
- tl_assert(lk->heldBy == NULL);
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy));
tid = map_threads_maybe_reverse_lookup_SLOW(thr);
lk->acquired_at
= VG_(record_ExeContext(tid, 0/*first_ip_delta*/));
} else {
- tl_assert(lk->heldBy != NULL);
+ tl_assert(!HG_(isEmptyBag)(&lk->heldBy));
}
/* end EXPOSITION only */
switch (lk->kind) {
case LK_nonRec:
case_LK_nonRec:
- tl_assert(lk->heldBy == NULL); /* can't w-lock recursively */
+ /* can't w-lock recursively */
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy));
tl_assert(!lk->heldW);
- lk->heldW = True;
- lk->heldBy = HG_(newBag)( hg_zalloc, hg_free );
- HG_(addToBag)( lk->heldBy, (Word)thr );
+ lk->heldW = True;
+ HG_(addToBag)( &lk->heldBy, (Word)thr );
break;
case LK_mbRec:
- if (lk->heldBy == NULL)
+ if (HG_(isEmptyBag)(&lk->heldBy))
goto case_LK_nonRec;
/* 2nd and subsequent locking of a lock by its owner */
tl_assert(lk->heldW);
/* assert: lk is only held by one thread .. */
- tl_assert(HG_(sizeUniqueBag(lk->heldBy)) == 1);
+ tl_assert(HG_(sizeUniqueBag(&lk->heldBy)) == 1);
/* assert: .. and that thread is 'thr'. */
- tl_assert(HG_(elemBag)(lk->heldBy, (Word)thr)
- == HG_(sizeTotalBag)(lk->heldBy));
- HG_(addToBag)(lk->heldBy, (Word)thr);
+ tl_assert(HG_(elemBag)(&lk->heldBy, (Word)thr)
+ == HG_(sizeTotalBag)(&lk->heldBy));
+ HG_(addToBag)(&lk->heldBy, (Word)thr);
break;
case LK_rdwr:
- tl_assert(lk->heldBy == NULL && !lk->heldW); /* must be unheld */
+ /* must be unheld */
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy) && !lk->heldW);
goto case_LK_nonRec;
default:
tl_assert(0);
@@ -1007,8 +1002,8 @@
/* can only add reader to a reader-writer lock. */
tl_assert(lk->kind == LK_rdwr);
/* lk must be free or already r-held. */
- tl_assert(lk->heldBy == NULL
- || (lk->heldBy != NULL && !lk->heldW));
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy)
+ || (!HG_(isEmptyBag)(&lk->heldBy) && !lk->heldW));
stats__lockN_acquires++;
@@ -1017,21 +1012,20 @@
acquired, so as to produce better lock-order error messages. */
if (lk->acquired_at == NULL) {
ThreadId tid;
- tl_assert(lk->heldBy == NULL);
+ tl_assert(HG_(isEmptyBag)(&lk->heldBy));
tid = map_threads_maybe_reverse_lookup_SLOW(thr);
lk->acquired_at
= VG_(record_ExeContext(tid, 0/*first_ip_delta*/));
} else {
- tl_assert(lk->heldBy != NULL);
+ tl_assert(!HG_(isEmptyBag)(&lk->heldBy));
}
/* end EXPOSITION only */
- if (lk->heldBy) {
- HG_(addToBag)(lk->heldBy, (Word)thr);
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
+ HG_(addToBag)(&lk->heldBy, (Word)thr);
} else {
- lk->heldW = False;
- lk->heldBy = HG_(newBag)( hg_zalloc, hg_free );
- HG_(addToBag)( lk->heldBy, (Word)thr );
+ lk->heldW = False;
+ HG_(addToBag)( &lk->heldBy, (Word)thr );
}
tl_assert(!lk->heldW);
tl_assert(is_sane_LockN(lk));
@@ -1047,17 +1041,15 @@
tl_assert(is_sane_LockN(lk));
tl_assert(is_sane_Thread(thr));
/* lock must be held by someone */
- tl_assert(lk->heldBy);
+ tl_assert(!HG_(isEmptyBag)(&lk->heldBy));
stats__lockN_releases++;
/* Remove it from the holder set */
- b = HG_(delFromBag)(lk->heldBy, (Word)thr);
+ b = HG_(delFromBag)(&lk->heldBy, (Word)thr);
/* thr must actually have been a holder of lk */
tl_assert(b);
/* normalise */
tl_assert(lk->acquired_at);
- if (HG_(isEmptyBag)(lk->heldBy)) {
- HG_(deleteBag)(lk->heldBy);
- lk->heldBy = NULL;
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
lk->heldW = False;
lk->acquired_at = NULL;
}
@@ -1067,13 +1059,13 @@
static void remove_Lock_from_locksets_of_all_owning_Threads( Lock* lk )
{
Thread* thr;
- if (!lk->heldBy) {
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
tl_assert(!lk->heldW);
return;
}
/* for each thread that holds this lock do ... */
- HG_(initIterBag)( lk->heldBy );
- while (HG_(nextIterBag)( lk->heldBy, (Word*)&thr, NULL )) {
+ HG_(initIterBag)( &lk->heldBy );
+ while (HG_(nextIterBag)( &lk->heldBy, (Word*)&thr, NULL )) {
tl_assert(is_sane_Thread(thr));
tl_assert(HG_(elemWS)( univ_lsets,
thr->locksetA, (Word)lk ));
@@ -1087,7 +1079,7 @@
= HG_(delFromWS)( univ_lsets, thr->locksetW, (Word)lk );
}
}
- HG_(doneIterBag)( lk->heldBy );
+ HG_(doneIterBag)( &lk->heldBy );
}
/* --------- xxxID functions --------- */
@@ -1358,15 +1350,15 @@
space(d+3); VG_(printf)("unique %llu\n", lk->unique);
space(d+3); VG_(printf)("kind %s\n", show_LockKind(lk->kind));
space(d+3); VG_(printf)("heldW %s\n", lk->heldW ? "yes" : "no");
- space(d+3); VG_(printf)("heldBy %p", lk->heldBy);
- if (lk->heldBy) {
+ //space(d+3); VG_(printf)("heldBy %p", lk->heldBy);
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
Thread* thr;
Word count;
VG_(printf)(" { ");
- HG_(initIterBag)( lk->heldBy );
- while (HG_(nextIterBag)( lk->heldBy, (Word*)&thr, &count ))
+ HG_(initIterBag)( &lk->heldBy );
+ while (HG_(nextIterBag)( &lk->heldBy, (Word*)&thr, &count ))
VG_(printf)("%lu:%p ", count, thr);
- HG_(doneIterBag)( lk->heldBy );
+ HG_(doneIterBag)( &lk->heldBy );
VG_(printf)("}");
}
VG_(printf)("\n");
@@ -2925,10 +2917,7 @@
/* Return True iff 'thr' holds 'lk' in some mode. */
static Bool thread_is_a_holder_of_Lock ( Thread* thr, Lock* lk )
{
- if (lk->heldBy)
- return HG_(elemBag)( lk->heldBy, (Word)thr ) > 0;
- else
- return False;
+ return HG_(elemBag)( &lk->heldBy, (Word)thr ) > 0;
}
/* Sanity check Threads, as far as possible */
@@ -3008,11 +2997,11 @@
//if (is_SHVAL_NoAccess(shadow_mem_get8(lk->guestaddr))) BAD("5");
// look at all threads mentioned as holders of this lock. Ensure
// this lock is mentioned in their locksets.
- if (lk->heldBy) {
+ if (!HG_(isEmptyBag)( &lk->heldBy )) {
Thread* thr;
Word count;
- HG_(initIterBag)( lk->heldBy );
- while (HG_(nextIterBag)( lk->heldBy,
+ HG_(initIterBag)( &lk->heldBy );
+ while (HG_(nextIterBag)( &lk->heldBy,
(Word*)&thr, &count )) {
// is_sane_LockN above ensures these
tl_assert(count >= 1);
@@ -3027,7 +3016,7 @@
&& HG_(elemWS)(univ_lsets, thr->locksetW, (Word)lk))
BAD("8");
}
- HG_(doneIterBag)( lk->heldBy );
+ HG_(doneIterBag)( &lk->heldBy );
} else {
/* lock not held by anybody */
if (lk->heldW) BAD("9"); /* should be False if !heldBy */
@@ -3585,7 +3574,7 @@
VG_(printf)("\n");
}
- if (__bus_lock_Lock->heldBy) {
+ if (!HG_(isEmptyBag)(&__bus_lock_Lock->heldBy)) {
VG_(printf)("BHL is held\n");
}
@@ -3637,8 +3626,8 @@
goto done;
}
- if (UNLIKELY(__bus_lock_Lock->heldBy)
- && (is_SHVAL_New(sv_old) || is_SHVAL_R(sv_old))) {
+ if (UNLIKELY(!HG_(isEmptyBag_UNCHECKED)(&__bus_lock_Lock->heldBy)
+ && (is_SHVAL_New(sv_old) || is_SHVAL_R(sv_old)))) {
stats__msm_BHL_hack++;
// BHL is held and we are in 'Read' or 'New' state.
// User is doing something very smart with LOCK prefix.
@@ -3772,8 +3761,8 @@
goto done;
}
- if (UNLIKELY(__bus_lock_Lock->heldBy)
- && (is_SHVAL_New(sv_old) || is_SHVAL_R(sv_old))) {
+ if (UNLIKELY(!HG_(isEmptyBag_UNCHECKED)(&__bus_lock_Lock->heldBy))
+ && (is_SHVAL_New(sv_old) || is_SHVAL_R(sv_old))) {
stats__msm_BHL_hack++;
// BHL is held and we are in 'Read' or 'New' state.
// User is doing something very smart with LOCK prefix.
@@ -5694,13 +5683,13 @@
one of the threads that holds it; really we should mention
them all, but that's too much hassle. So choose one
arbitrarily. */
- if (lk->heldBy) {
- tl_assert(!HG_(isEmptyBag)(lk->heldBy));
- record_error_FreeMemLock( (Thread*)HG_(anyElementOfBag)(lk->heldBy),
- lk );
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
+ record_error_FreeMemLock(
+ (Thread*)HG_(anyElementOfBag)(&lk->heldBy),
+ lk
+ );
/* remove lock from locksets of all owning threads */
remove_Lock_from_locksets_of_all_owning_Threads( lk );
- /* Leave lk->heldBy in place; del_Lock below will free it up. */
}
}
HG_(doneIterFM)( map_locks );
@@ -5832,7 +5821,7 @@
tl_assert( is_sane_LockN(lk) );
shmem__set_mbHasLocks( lock_ga, True );
- if (lk->heldBy == NULL) {
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
/* the lock isn't held. Simple. */
tl_assert(!lk->heldW);
lockN_acquire_writer( lk, thr );
@@ -5841,7 +5830,6 @@
/* So the lock is already held. If held as a r-lock then
libpthread must be buggy. */
- tl_assert(lk->heldBy);
if (!lk->heldW) {
record_error_Misc( thr, "Bug in libpthread: write lock "
"granted on rwlock which is currently rd-held");
@@ -5850,9 +5838,9 @@
/* So the lock is held in w-mode. If it's held by some other
thread, then libpthread must be buggy. */
- tl_assert(HG_(sizeUniqueBag)(lk->heldBy) == 1); /* from precondition */
+ tl_assert(HG_(sizeUniqueBag)(&lk->heldBy) == 1); /* from precondition */
- if (thr != (Thread*)HG_(anyElementOfBag)(lk->heldBy)) {
+ if (thr != (Thread*)HG_(anyElementOfBag)(&lk->heldBy)) {
record_error_Misc( thr, "Bug in libpthread: write lock "
"granted on mutex/rwlock which is currently "
"wr-held by a different thread");
@@ -5929,7 +5917,7 @@
tl_assert( is_sane_LockN(lk) );
shmem__set_mbHasLocks( lock_ga, True );
- if (lk->heldBy == NULL) {
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
/* the lock isn't held. Simple. */
tl_assert(!lk->heldW);
lockN_acquire_reader( lk, thr );
@@ -5938,7 +5926,6 @@
/* So the lock is already held. If held as a w-lock then
libpthread must be buggy. */
- tl_assert(lk->heldBy);
if (lk->heldW) {
record_error_Misc( thr, "Bug in libpthread: read lock "
"granted on rwlock which is "
@@ -6017,7 +6004,7 @@
"pthread_rwlock_t* argument " );
}
- if (!lock->heldBy) {
+ if (HG_(isEmptyBag)(&lock->heldBy)) {
/* The lock is not held. This indicates a serious bug in the
client. */
tl_assert(!lock->heldW);
@@ -6029,14 +6016,14 @@
/* The lock is held. Is this thread one of the holders? If not,
report a bug in the client. */
- n = HG_(elemBag)( lock->heldBy, (Word)thr );
+ n = HG_(elemBag)( &lock->heldBy, (Word)thr );
tl_assert(n >= 0);
if (n == 0) {
/* We are not a current holder of the lock. This is a bug in
the guest, and (per POSIX pthread rules) the unlock
attempt will fail. So just complain and do nothing
else. */
- Thread* realOwner = (Thread*)HG_(anyElementOfBag)( lock->heldBy );
+ Thread* realOwner = (Thread*)HG_(anyElementOfBag)( &lock->heldBy );
tl_assert(is_sane_Thread(realOwner));
tl_assert(realOwner != thr);
tl_assert(!HG_(elemWS)( univ_lsets, thr->locksetA, (Word)lock ));
@@ -6054,8 +6041,8 @@
tl_assert(n >= 0);
if (n > 0) {
- tl_assert(lock->heldBy);
- tl_assert(n == HG_(elemBag)( lock->heldBy, (Word)thr ));
+ tl_assert(!HG_(isEmptyBag)(&lock->heldBy));
+ tl_assert(n == HG_(elemBag)( &lock->heldBy, (Word)thr ));
/* We still hold the lock. So either it's a recursive lock
or a rwlock which is currently r-held. */
tl_assert(lock->kind == LK_mbRec
@@ -6067,9 +6054,8 @@
tl_assert(!HG_(elemWS)( univ_lsets, thr->locksetW, (Word)lock ));
} else {
/* We no longer hold the lock. */
- if (lock->heldBy) {
- tl_assert(0 == HG_(elemBag)( lock->heldBy, (Word)thr ));
- }
+ tl_assert(HG_(isEmptyBag)(&lock->heldBy));
+ tl_assert(0 == HG_(elemBag)( &lock->heldBy, (Word)thr ));
/* update this thread's lockset accordingly. */
thr->locksetA
= HG_(delFromWS)( univ_lsets, thr->locksetA, (Word)lock );
@@ -6591,17 +6577,16 @@
if (lk) {
tl_assert( is_sane_LockN(lk) );
tl_assert( lk->guestaddr == (Addr)mutex );
- if (lk->heldBy) {
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
/* Basically act like we unlocked the lock */
record_error_Misc( thr, "pthread_mutex_destroy of a locked mutex" );
/* remove lock from locksets of all owning threads */
remove_Lock_from_locksets_of_all_owning_Threads( lk );
- HG_(deleteBag)( lk->heldBy );
- lk->heldBy = NULL;
+ HG_(emptyOutBag)( &lk->heldBy );
lk->heldW = False;
lk->acquired_at = NULL;
}
- tl_assert( !lk->heldBy );
+ tl_assert( HG_(isEmptyBag)(&lk->heldBy) );
tl_assert( is_sane_LockN(lk) );
}
@@ -6634,9 +6619,9 @@
if ( lk
&& isTryLock == 0
&& (lk->kind == LK_nonRec || lk->kind == LK_rdwr)
- && lk->heldBy
+ && !HG_(isEmptyBag)(&lk->heldBy)
&& lk->heldW
- && HG_(elemBag)( lk->heldBy, (Word)thr ) > 0 ) {
+ && HG_(elemBag)( &lk->heldBy, (Word)thr ) > 0 ) {
/* uh, it's a non-recursive lock and we already w-hold it, and
this is a real lock operation (not a speculative "tryLock"
kind of thing). Duh. Deadlock coming up; but at least
@@ -6891,13 +6876,13 @@
thr, "pthread_cond_{timed}wait called with mutex "
"of type pthread_rwlock_t*" );
} else
- if (lk->heldBy == NULL) {
+ if (HG_(isEmptyBag)(&lk->heldBy)) {
lk_valid = False;
record_error_Misc(
thr, "pthread_cond_{timed}wait called with un-held mutex");
} else
- if (lk->heldBy != NULL
- && HG_(elemBag)( lk->heldBy, (Word)thr ) == 0) {
+ if (!HG_(isEmptyBag)(&lk->heldBy)
+ && HG_(elemBag)( &lk->heldBy, (Word)thr ) == 0) {
lk_valid = False;
record_error_Misc(
thr, "pthread_cond_{timed}wait called with mutex "
@@ -6972,17 +6957,16 @@
if (lk) {
tl_assert( is_sane_LockN(lk) );
tl_assert( lk->guestaddr == (Addr)rwl );
- if (lk->heldBy) {
+ if (!HG_(isEmptyBag)(&lk->heldBy)) {
/* Basically act like we unlocked the lock */
record_error_Misc( thr, "pthread_rwlock_destroy of a locked mutex" );
/* remove lock from locksets of all owning threads */
remove_Lock_from_locksets_of_all_owning_Threads( lk );
- HG_(deleteBag)( lk->heldBy );
- lk->heldBy = NULL;
+ HG_(emptyOutBag)( &lk->heldBy );
lk->heldW = False;
lk->acquired_at = NULL;
}
- tl_assert( !lk->heldBy );
+ tl_assert( HG_(isEmptyBag)(&lk->heldBy) );
tl_assert( is_sane_LockN(lk) );
}
@@ -8630,10 +8614,10 @@
lkp->admin = NULL;
lkp->magic = LockP_MAGIC;
/* Forget about the bag of lock holders - don't copy that.
- Also, acquired_at should be NULL whenever heldBy is, and vice
- versa. */
+ Also, acquired_at should be NULL whenever heldBy is empty,
+ and vice versa. */
lkp->heldW = False;
- lkp->heldBy = NULL;
+ VG_(memset)( &lkp->heldBy, 0, sizeof(lkp->heldBy) );
lkp->acquired_at = NULL;
HG_(addToFM)( yaWFM, (Word)lkp, (Word)lkp );
}
Modified: branches/HGDEV/helgrind/hg_wordfm.c
===================================================================
--- branches/HGDEV/helgrind/hg_wordfm.c 2008-03-23 08:03:27 UTC (rev 7759)
+++ branches/HGDEV/helgrind/hg_wordfm.c 2008-03-23 13:17:52 UTC (rev 7760)
@@ -531,7 +531,7 @@
void (*dealloc)(void*),
Word (*kCmp)(UWord,UWord) )
{
- fm->root = 0;
+ fm->root = NULL;
fm->kCmp = kCmp;
fm->alloc_nofail = alloc_nofail;
fm->dealloc = dealloc;
@@ -644,6 +644,23 @@
return fm->root ? size_avl_nonNull( fm->root ) : 0;
}
+Bool HG_(isEmptyFM)( WordFM* fm )
+{
+ return fm->root == NULL;
+}
+
+Bool HG_(anyElementOfFM) ( WordFM* fm,
+ /*OUT*/UWord* keyP, /*OUT*/UWord* valP )
+{
+ if (!fm->root)
+ return False;
+ if (keyP)
+ *keyP = fm->root->key;
+ if (valP)
+ *valP = fm->root->val;
+ return True;
+}
+
// set up FM for iteration
void HG_(initIterFM) ( WordFM* fm )
{
@@ -783,47 +800,139 @@
//--- Implementation ---//
//------------------------------------------------------------------//
-/* A WordBag is just a WordFM, but we typedef-void it for the
- interface, to make it opaque. */
+//struct _WordBag {
+// void* (*alloc_nofail)( SizeT );
+// void (*dealloc)(void*);
+// UWord firstWord;
+// UWord firstCount;
+// WordFM* rest;
+// /* When zero, the next call to HG_(nextIterBag) gives
+// (.firstWord, .firstCount). When nonzero, such calls traverse
+// .rest. */
+// UWord iterCount;
+//};
-WordBag* HG_(newBag) ( void* (*alloc_nofail)( SizeT ),
- void (*dealloc)(void*) )
+/* Representational invariants. Either:
+
+ * bag is empty
+ firstWord == firstCount == 0
+ rest == NULL
+
+ * bag contains just one unique element
+ firstCount > 0
+ rest == NULL
+
+ * bag contains more than one unique element
+ firstCount > 0
+ rest != NULL
+
+ If rest != NULL, then
+ (1) firstWord != any .key in rest, and
+ (2) all .val in rest > 0
+*/
+
+static inline Bool is_plausible_WordBag ( WordBag* bag ) {
+ if (bag->firstWord == 0 && bag->firstCount == 0 && bag->rest == NULL)
+ return True;
+ if (bag->firstCount > 0 && bag->rest == NULL)
+ return True;
+ if (bag->firstCount > 0 && bag->rest != NULL)
+ /* really should check (1) and (2) now, but that's
+ v. expensive */
+ return True;
+ return False;
+}
+
+void HG_(initBag) ( WordBag* bag,
+ void* (*alloc_nofail)( SizeT ),
+ void (*dealloc)(void*) )
{
- return HG_(newFM)( alloc_nofail, dealloc, NULL );
+ bag->alloc_nofail = alloc_nofail;
+ bag->dealloc = dealloc;
+ bag->firstWord = 0;
+ bag->firstCount = 0;
+ bag->rest = NULL;
+ bag->iterCount = 0;
}
-void HG_(deleteBag) ( WordBag* bag )
+void HG_(emptyOutBag) ( WordBag* bag )
{
- HG_(deleteFM)( bag, NULL, NULL );
+ if (bag->rest)
+ HG_(deleteFM)( bag->rest, NULL, NULL );
+ /* Don't zero out the alloc and dealloc function pointers, since we
+ want to be able to keep on using this bag later, without having
+ to call HG_(initBag) again. */
+ bag->firstWord = 0;
+ bag->firstCount = 0;
+ bag->rest = NULL;
+ bag->iterCount = 0;
}
void HG_(addToBag)( WordBag* bag, UWord w )
{
- UWord key, count;
- if (HG_(lookupFM)(bag, &key, &count, w)) {
- tl_assert(key == w);
- tl_assert(count >= 1);
- HG_(addToFM)(bag, w, count+1);
- } else {
- HG_(addToFM)(bag, w, 1);
+ tl_assert(is_plausible_WordBag(bag));
+ /* case where the bag is completely empty */
+ if (bag->firstCount == 0) {
+ tl_assert(bag->firstWord == 0 && bag->rest == NULL);
+ bag->firstWord = w;
+ bag->firstCount = 1;
+ return;
}
+ /* there must be at least one element in it */
+ tl_assert(bag->firstCount > 0);
+ if (bag->firstWord == w) {
+ bag->firstCount++;
+ return;
+ }
+ /* it's not the Distinguished Element. Try the rest */
+ { UWord key, count;
+ if (bag->rest == NULL) {
+ bag->rest = HG_(newFM)( bag->alloc_nofail, bag->dealloc,
+ NULL/*unboxed uword cmp*/ );
+ }
+ tl_assert(bag->rest);
+ if (HG_(lookupFM)(bag->rest, &key, &count, w)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ HG_(addToFM)(bag->rest, w, count+1);
+ } else {
+ HG_(addToFM)(bag->rest, w, 1);
+ }
+ }
}
UWord HG_(elemBag) ( WordBag* bag, UWord w )
{
- UWord key, count;
- if (HG_(lookupFM)( bag, &key, &count, w)) {
- tl_assert(key == w);
- tl_assert(count >= 1);
- return count;
- } else {
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount == 0) {
return 0;
}
+ if (w == bag->firstWord) {
+ return bag->firstCount;
+ }
+ if (!bag->rest) {
+ return 0;
+ }
+ { UWord key, count;
+ if (HG_(lookupFM)( bag->rest, &key, &count, w)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ return count;
+ } else {
+ return 0;
+ }
+ }
}
UWord HG_(sizeUniqueBag) ( WordBag* bag )
{
- return HG_(sizeFM)( bag );
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount == 0) {
+ tl_assert(bag->firstWord == 0);
+ tl_assert(bag->rest == NULL);
+ return 0;
+ }
+ return 1 + (bag->rest ? HG_(sizeFM)( bag->rest ) : 0);
}
static UWord sizeTotalBag_wrk ( AvlNode* nd )
@@ -839,72 +948,166 @@
}
UWord HG_(sizeTotalBag)( WordBag* bag )
{
- if (((WordFM*)bag)->root)
- return sizeTotalBag_wrk(((WordFM*)bag)->root);
- else
+ UWord res;
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount == 0) {
+ tl_assert(bag->firstWord == 0);
+ tl_assert(bag->rest == NULL);
return 0;
+ }
+ res = bag->firstCount;
+ if (bag->rest && bag->rest->root)
+ res += sizeTotalBag_wrk( bag->rest->root );
+ return res;
}
Bool HG_(delFromBag)( WordBag* bag, UWord w )
{
- UWord key, count;
- if (HG_(lookupFM)(bag, &key, &count, w)) {
- tl_assert(key == w);
- tl_assert(count >= 1);
- if (count > 1) {
- HG_(addToFM)(bag, w, count-1);
+ tl_assert(is_plausible_WordBag(bag));
+
+ /* Case: bag is empty */
+ if (bag->firstCount == 0) {
+ /* empty */
+ tl_assert(bag->firstWord == 0 && bag->rest == NULL);
+ return False;
+ }
+ tl_assert(bag->firstCount > 0);
+
+ /* Case: deleting from the distinguished (word,count) */
+ if (w == bag->firstWord) {
+ Bool b;
+ UWord tmpWord, tmpCount;
+ if (bag->firstCount > 1) {
+ /* Easy. */
+ bag->firstCount--;
+ return True;
+ }
+ tl_assert(bag->firstCount == 1);
+ /* Now it gets complex. Since the distinguished (word,count)
+ pair is about to disappear, we have to get a new one from
+ 'rest'. */
+ if (bag->rest == NULL) {
+ /* Resulting bag really is completely empty. */
+ bag->firstWord = 0;
+ bag->firstCount = 0;
+ return True;
+ }
+ /* Get a new distinguished element from 'rest'. This must be
+ possible if 'rest' is non-NULL. */
+ b = HG_(anyElementOfFM)( bag->rest, &bag->firstWord, &bag->firstCount );
+ tl_assert(b);
+ tl_assert(bag->firstCount > 0);
+ b = HG_(delFromFM)( bag->rest, &tmpWord, &tmpCount, bag->firstWord );
+ tl_assert(b);
+ tl_assert(tmpWord == bag->firstWord);
+ tl_assert(tmpCount == bag->firstCount);
+ if (HG_(isEmptyFM)( bag->rest )) {
+ HG_(deleteFM)( bag->rest, NULL, NULL );
+ bag->rest = NULL;
+ }
+ return True;
+ }
+
+ /* Case: deleting from 'rest' */
+ tl_assert(bag->firstCount > 0);
+ tl_assert(bag->firstWord != w);
+ if (bag->rest) {
+ UWord key, count;
+ if (HG_(lookupFM)(bag->rest, &key, &count, w)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ if (count > 1) {
+ HG_(addToFM)(bag->rest, w, count-1);
+ } else {
+ tl_assert(count == 1);
+ HG_(delFromFM)(bag->rest, NULL, NULL, w);
+ if (HG_(isEmptyFM)( bag->rest )) {
+ HG_(deleteFM)( bag->rest, NULL, NULL );
+ bag->rest = NULL;
+ }
+ }
+ return True;
} else {
- tl_assert(count == 1);
- HG_(delFromFM)(bag, NULL, NULL, w);
+ return False;
}
- return True;
} else {
return False;
}
+ /*NOTREACHED*/
+ tl_assert(0);
}
Bool HG_(isEmptyBag)( WordBag* bag )
{
- return HG_(sizeFM)(bag) == 0;
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount == 0) {
+ tl_assert(bag->firstWord == 0);
+ tl_assert(bag->rest == NULL);
+ return True;
+ } else {
+ return False;
+ }
}
Bool HG_(isSingletonTotalBag)( WordBag* bag )
{
- AvlNode* nd;
- if (HG_(sizeFM)(bag) != 1)
- return False;
- nd = ((WordFM*)bag)->root;
- tl_assert(nd);
- tl_assert(!nd->child[0]);
- tl_assert(!nd->child[1]);
- return nd->val == 1;
+ tl_assert(is_plausible_WordBag(bag));
+ return bag->firstCount > 0 && bag->rest == NULL;
}
UWord HG_(anyElementOfBag)( WordBag* bag )
{
- /* Return an arbitrarily chosen element in the bag. We might as
- well return the one at the root of the underlying AVL tree. */
- AvlNode* nd = ((WordFM*)bag)->root;
- tl_assert(nd); /* if this fails, 'bag' is empty - caller is in error. */
- tl_assert(nd->val >= 1);
- return nd->key;
+ tl_assert(is_plausible_WordBag(bag));
+ if (bag->firstCount > 0) {
+ return bag->firstWord;
+ }
+ /* The bag is empty, so the caller is in error, and we should
+ assert. */
+ tl_assert(0);
}
void HG_(initIterBag)( WordBag* bag )
{
- HG_(initIterFM)(bag);
+ tl_assert(is_plausible_WordBag(bag));
+ bag->iterCount = 0;
}
Bool HG_(nextIterBag)( WordBag* bag, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount )
{
- return HG_(nextIterFM)( bag, pVal, pCount );
+ Bool b;
+ if (bag->iterCount == 0) {
+ /* Emitting (.firstWord, .firstCount) if we have it. */
+ if (bag->firstCount == 0) {
+ /* empty */
+ return False;
+ }
+ if (pVal) *pVal = bag->firstWord;
+ if (pCount) *pCount = bag->firstCount;
+ bag->iterCount = 1;
+ return True;
+ }
+
+ /* else emitting from .rest, if present */
+ if (!bag->rest)
+ return False;
+
+ if (bag->iterCount == 1)
+ HG_(initIterFM)( bag->rest );
+
+ b = HG_(nextIterFM)( bag->rest, pVal, pCount );
+ bag->iterCount++;
+
+ return b;
}
void HG_(doneIterBag)( WordBag* bag )
{
- HG_(doneIterFM)( bag );
+ bag->iterCount = 0;
+ if (bag->rest)
+ HG_(doneIterFM)( bag->rest );
}
+
//------------------------------------------------------------------//
//--- end WordBag (unboxed words only) ---//
//--- Implementation ---//
@@ -954,6 +1157,18 @@
return n_found;
}
+void showBag ( WordBag* bag )
+{
+ UWord val, count;
+ printf("Bag{");
+ HG_(initIterBag)( bag );
+ while (HG_(nextIterBag)( bag, &val, &count )) {
+ printf(" %lux%lu ", count, val );
+ }
+ HG_(doneIterBag)( bag );
+ printf("}"); fflush(stdout);
+}
+
int main(void)
{
long i, n = 10;
@@ -1018,6 +1233,82 @@
printf("Delete the map\n");
HG_(deleteFM)(map, NULL, NULL);
printf("Ok!\n");
+
+ printf("\nBEGIN testing WordBag\n");
+ WordBag bag;
+ Bool b;
+
+ HG_(initBag)( &bag, malloc, free );
+
+ printf("operations on an empty bag\n");
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ assert( HG_(isEmptyBag)( &bag ));
+ printf("\noperations on bag { 41 }\n");
+ HG_(addToBag)( &bag, 41 );
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ b = HG_(delFromBag)( &bag, 41 ); assert(b);
+
+ printf("\noperations on bag { 41,41 }\n");
+ HG_(addToBag)( &bag, 41 );
+ HG_(addToBag)( &bag, 41 );
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ printf("\noperations on bag { 41,41, 42, 43,43 }\n");
+ HG_(addToBag)( &bag, 42 );
+ HG_(addToBag)( &bag, 43 );
+ HG_(addToBag)( &bag, 43 );
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ b = HG_(delFromBag)( &bag, 41 ); assert(b);
+ printf(" after del of 41: " ); showBag( &bag ); printf("\n");
+ b = HG_(delFromBag)( &bag, 41 ); assert(b);
+ printf(" after del of 41: " ); showBag( &bag ); printf("\n");
+ b = HG_(delFromBag)( &bag, 43 ); assert(b);
+ printf(" after del of 43: " ); showBag( &bag ); printf("\n");
+ b = HG_(delFromBag)( &bag, 42 ); assert(!b); // already gone
+ printf(" after del of 42: " ); showBag( &bag ); printf("\n");
+ b = HG_(delFromBag)( &bag, 43 ); assert(b);
+ printf(" after del of 43: " ); showBag( &bag ); printf("\n");
+
+ HG_(emptyOutBag)( &bag );
+
+ printf("\noperations on now empty bag\n");
+ printf(" show: " ); showBag( &bag ); printf("\n");
+ printf(" elem: %lu\n", HG_(elemBag)( &bag, 42 ));
+ printf(" isEmpty: %lu\n", (UWord) HG_(isEmptyBag)( &bag ));
+ printf(" iSTB: %lu\n", (UWord) HG_(isSingletonTotalBag)( &bag ));
+ printf(" sizeUnique: %lu\n", HG_(sizeUniqueBag)( &bag ));
+ printf(" sizeTotal: %lu\n", HG_(sizeTotalBag)( &bag ));
+ printf(" delFrom: %lu\n", (UWord)HG_(delFromBag)( &bag, 42 ));
+
+ printf("\nEND testing WordBag\n");
+
return 0;
}
Modified: branches/HGDEV/helgrind/hg_wordfm.h
===================================================================
--- branches/HGDEV/helgrind/hg_wordfm.h 2008-03-23 08:03:27 UTC (rev 7759)
+++ branches/HGDEV/helgrind/hg_wordfm.h 2008-03-23 13:17:52 UTC (rev 7760)
@@ -97,9 +97,17 @@
Bool HG_(lookupFM) ( WordFM* fm,
/*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key );
-// How many elements are there in fm?
+// How many elements are there in fm? Note; slow; O(# elems in the fm)
UWord HG_(sizeFM) ( WordFM* fm );
+// Is the fm empty? Fast (constant-time)
+Bool HG_(isEmptyFM)( WordFM* fm );
+
+// If fm is non-empty, return an arbitrarily chosen key/value pair
+// through *keyP/*valP, and return True. If empty return False.
+Bool HG_(anyElementOfFM) ( WordFM* fm,
+ /*OUT*/UWord* keyP, /*OUT*/UWord* valP );
+
// set up FM for iteration
void HG_(initIterFM) ( WordFM* fm );
@@ -136,15 +144,35 @@
//--- Public interface ---//
//------------------------------------------------------------------//
-typedef void WordBag; /* opaque */
+//typedef struct _WordBag WordBag; /* opaque */
-/* Allocate and initialise a WordBag */
-WordBag* HG_(newBag) ( void* (*alloc_nofail)( SizeT ),
- void (*dealloc)(void*) );
+// FIXME! find some way to turn this back into an abstract type.
+typedef
+ struct {
+ void* (*alloc_nofail)( SizeT );
+ void (*dealloc)(void*);
+ UWord firstWord;
+ UWord firstCount;
+ WordFM* rest;
+ /* When zero, the next call to HG_(nextIterBag) gives
+ (.firstWord, .firstCount). When nonzero, such calls traverse
+ .rest. */
+ UWord iterCount;
+ }
+ WordBag;
-/* Free up the Bag. */
-void HG_(deleteBag) ( WordBag* );
+/* Initialise a WordBag and make it empty. Only do this once for each
+ bag, at the start of its lifetime. */
+void HG_(initBag) ( WordBag* bag,
+ void* (*alloc_nofail)( SizeT ),
+ void (*dealloc)(void*) );
+
+/* Remove all elements from a bag, thereby making it empty, and free
+ all associated memory. This can be done as many times as required,
+ but only after the initial HG_(initBag) call. */
+void HG_(emptyOutBag) ( WordBag* bag );
+
/* Add a word. */
void HG_(addToBag)( WordBag*, UWord );
@@ -157,6 +185,11 @@
/* Is the bag empty? */
Bool HG_(isEmptyBag)( WordBag* );
+/* Is the bag empty, skipping all sanity checks? */
+static inline Bool HG_(isEmptyBag_UNCHECKED)( WordBag* bag ) {
+ return bag->firstCount == 0;
+}
+
/* Does the bag have exactly one element? */
Bool HG_(isSingletonTotalBag)( WordBag* );
@@ -164,8 +197,8 @@
UWord HG_(anyElementOfBag)( WordBag* );
/* How many different / total elements are in the bag? */
-UWord HG_(sizeUniqueBag)( WordBag* ); /* fast */
-UWord HG_(sizeTotalBag)( WordBag* ); /* warning: slow */
+UWord HG_(sizeUniqueBag)( WordBag* ); /* warning: slow */
+UWord HG_(sizeTotalBag)( WordBag* ); /* warning: very slow */
/* Iterating over the elements of a bag. */
void HG_(initIterBag)( WordBag* );
|
|
From: <sv...@va...> - 2008-03-23 08:03:22
|
Author: bart Date: 2008-03-23 08:03:27 +0000 (Sun, 23 Mar 2008) New Revision: 7759 Log: Created a copy of trunk r7758 in order to experiment with reference counting on bitmaps. Added: branches/DRDDEV/ Copied: branches/DRDDEV (from rev 7758, trunk) |
|
From: <sv...@va...> - 2008-03-23 07:53:59
|
Author: bart
Date: 2008-03-23 07:54:02 +0000 (Sun, 23 Mar 2008)
New Revision: 7758
Log:
Reorganized error printing code slightly.
Modified:
trunk/exp-drd/drd_error.c
trunk/exp-drd/drd_error.h
Modified: trunk/exp-drd/drd_error.c
===================================================================
--- trunk/exp-drd/drd_error.c 2008-03-22 17:36:23 UTC (rev 7757)
+++ trunk/exp-drd/drd_error.c 2008-03-23 07:54:02 UTC (rev 7758)
@@ -39,13 +39,6 @@
#include "pub_tool_tooliface.h" // VG_(needs_tool_errors)()
-/* Local type definitions. */
-
-typedef enum {
- ConflictingAccessSupp
-} DRD_SuppKind;
-
-
/* Local variables. */
static Bool s_drd_show_conflicting_segments = True;
@@ -253,12 +246,26 @@
static Bool drd_tool_error_recog(Char* const name, Supp* const supp)
{
- SuppKind skind;
+ SuppKind skind = 0;
- if (VG_(strcmp)(name, "ConflictingAccess") == 0)
- skind = ConflictingAccessSupp;
- else if (VG_(strcmp)(name, "CondErr") == 0)
- skind = CondErr;
+ if (VG_(strcmp)(name, STR_DataRaceErr) == 0)
+ ;
+ else if (VG_(strcmp)(name, STR_MutexErr) == 0)
+ ;
+ else if (VG_(strcmp)(name, STR_CondErr) == 0)
+ ;
+ else if (VG_(strcmp)(name, STR_CondRaceErr) == 0)
+ ;
+ else if (VG_(strcmp)(name, STR_CondDestrErr) == 0)
+ ;
+ else if (VG_(strcmp)(name, STR_SemaphoreErr) == 0)
+ ;
+ else if (VG_(strcmp)(name, STR_BarrierErr) == 0)
+ ;
+ else if (VG_(strcmp)(name, STR_RwlockErr) == 0)
+ ;
+ else if (VG_(strcmp)(name, STR_GenericErr) == 0)
+ ;
else
return False;
@@ -283,15 +290,15 @@
{
switch (VG_(get_error_kind)(e))
{
- case DataRaceErr: return "ConflictingAccess";
- case MutexErr: return "MutexErr";
- case CondErr: return "CondErr";
- case CondRaceErr: return "CondRaceErr";
- case CondDestrErr: return "CondDestrErr";
- case SemaphoreErr: return "SemaphoreErr";
- case BarrierErr: return "BarrierErr";
- case RwlockErr: return "RwlockErr";
- case GenericErr: return "GenericErr";
+ case DataRaceErr: return VGAPPEND(STR_, DataRaceErr);
+ case MutexErr: return VGAPPEND(STR_, MutexErr);
+ case CondErr: return VGAPPEND(STR_, CondErr);
+ case CondRaceErr: return VGAPPEND(STR_, CondRaceErr);
+ case CondDestrErr: return VGAPPEND(STR_, CondDestrErr);
+ case SemaphoreErr: return VGAPPEND(STR_, SemaphoreErr);
+ case BarrierErr: return VGAPPEND(STR_, BarrierErr);
+ case RwlockErr: return VGAPPEND(STR_, RwlockErr);
+ case GenericErr: return VGAPPEND(STR_, GenericErr);
default:
tl_assert(0);
}
Modified: trunk/exp-drd/drd_error.h
===================================================================
--- trunk/exp-drd/drd_error.h 2008-03-22 17:36:23 UTC (rev 7757)
+++ trunk/exp-drd/drd_error.h 2008-03-23 07:54:02 UTC (rev 7758)
@@ -37,14 +37,23 @@
/* DRD error types. */
typedef enum {
+#define STR_DataRaceErr "ConflictingAccess"
DataRaceErr = 1,
+#define STR_MutexErr "MutexErr"
MutexErr = 2,
+#define STR_CondErr "CondErr"
CondErr = 3,
+#define STR_CondRaceErr "CondRaceErr"
CondRaceErr = 4,
+#define STR_CondDestrErr "CondDestrErr"
CondDestrErr = 5,
+#define STR_SemaphoreErr "SemaphoreErr"
SemaphoreErr = 6,
+#define STR_BarrierErr "BarrierErr"
BarrierErr = 7,
+#define STR_RwlockErr "RwlockErr"
RwlockErr = 8,
+#define STR_GenericErr "GenericErr"
GenericErr = 9,
} DrdErrorKind;
|
|
From: Tom H. <th...@cy...> - 2008-03-23 05:14:38
|
Nightly build on alvis ( i686, Red Hat 7.3 ) started at 2008-03-23 03:15:04 GMT Results unchanged from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 330 tests, 76 stderr failures, 1 stdout failure, 29 post failures == memcheck/tests/addressable (stderr) memcheck/tests/badjump (stderr) memcheck/tests/describe-block (stderr) memcheck/tests/erringfds (stderr) memcheck/tests/leak-0 (stderr) memcheck/tests/leak-cycle (stderr) memcheck/tests/leak-pool-0 (stderr) memcheck/tests/leak-pool-1 (stderr) memcheck/tests/leak-pool-2 (stderr) memcheck/tests/leak-pool-3 (stderr) memcheck/tests/leak-pool-4 (stderr) memcheck/tests/leak-pool-5 (stderr) memcheck/tests/leak-regroot (stderr) memcheck/tests/leak-tree (stderr) memcheck/tests/long_namespace_xml (stderr) memcheck/tests/lsframe1 (stderr) memcheck/tests/lsframe2 (stderr) memcheck/tests/malloc_free_fill (stderr) memcheck/tests/match-overrun (stderr) memcheck/tests/noisy_child (stderr) memcheck/tests/partial_load_dflt (stderr) memcheck/tests/partial_load_ok (stderr) memcheck/tests/partiallydefinedeq (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/sigkill (stderr) memcheck/tests/stack_changes (stderr) memcheck/tests/varinfo1 (stderr) memcheck/tests/varinfo2 (stderr) memcheck/tests/varinfo3 (stderr) memcheck/tests/varinfo4 (stderr) memcheck/tests/varinfo5 (stderr) memcheck/tests/varinfo6 (stderr) memcheck/tests/x86/bug152022 (stderr) memcheck/tests/x86/scalar (stderr) memcheck/tests/x86/scalar_supp (stderr) memcheck/tests/x86/xor-undef-x86 (stderr) memcheck/tests/xml1 (stderr) massif/tests/alloc-fns-A (post) massif/tests/alloc-fns-B (post) massif/tests/basic (post) massif/tests/basic2 (post) massif/tests/big-alloc (post) massif/tests/culling1 (stderr) massif/tests/culling2 (stderr) massif/tests/custom_alloc (post) massif/tests/deep-A (post) massif/tests/deep-B (stderr) massif/tests/deep-B (post) massif/tests/deep-C (stderr) massif/tests/deep-C (post) massif/tests/deep-D (post) massif/tests/ignoring (post) massif/tests/insig (post) massif/tests/long-names (post) massif/tests/long-time (post) massif/tests/new-cpp (post) massif/tests/null (post) massif/tests/one (post) massif/tests/overloaded-new (post) massif/tests/peak (post) massif/tests/peak2 (stderr) massif/tests/peak2 (post) massif/tests/realloc (stderr) massif/tests/realloc (post) massif/tests/thresholds_0_0 (post) massif/tests/thresholds_0_10 (post) massif/tests/thresholds_10_0 (post) massif/tests/thresholds_10_10 (post) massif/tests/thresholds_5_0 (post) massif/tests/thresholds_5_10 (post) massif/tests/zero1 (post) massif/tests/zero2 (post) none/tests/blockfault (stderr) none/tests/faultstatus (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) none/tests/shell (stderr) none/tests/shell_valid1 (stderr) none/tests/shell_valid2 (stderr) none/tests/shell_valid3 (stderr) helgrind/tests/hg01_all_ok (stderr) helgrind/tests/hg02_deadlock (stderr) helgrind/tests/hg03_inherit (stderr) helgrind/tests/hg04_race (stderr) helgrind/tests/hg05_race2 (stderr) helgrind/tests/hg06_readshared (stderr) helgrind/tests/tc01_simple_race (stderr) helgrind/tests/tc02_simple_tls (stderr) helgrind/tests/tc03_re_excl (stderr) helgrind/tests/tc05_simple_race (stderr) helgrind/tests/tc06_two_races (stderr) helgrind/tests/tc07_hbl1 (stderr) helgrind/tests/tc08_hbl2 (stderr) helgrind/tests/tc09_bad_unlock (stderr) helgrind/tests/tc11_XCHG (stderr) helgrind/tests/tc12_rwl_trivial (stderr) helgrind/tests/tc14_laog_dinphils (stderr) helgrind/tests/tc16_byterace (stderr) helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc18_semabuse (stderr) helgrind/tests/tc19_shadowmem (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) helgrind/tests/tc23_bogus_condwait (stderr) helgrind/tests/tc24_nonzero_sem (stderr) |
|
From: Tom H. <th...@cy...> - 2008-03-23 04:24:09
|
Nightly build on lloyd ( x86_64, Fedora 7 ) started at 2008-03-23 03:05:04 GMT Results differ from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 413 tests, 6 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/scalar (stderr) none/tests/faultstatus (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Results from 24 hours ago == ================================================= Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 413 tests, 7 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/scalar (stderr) none/tests/faultstatus (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Difference between 24 hours ago and now == ================================================= *** old.short Sun Mar 23 03:42:18 2008 --- new.short Sun Mar 23 04:24:10 2008 *************** *** 8,10 **** ! == 413 tests, 7 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) --- 8,10 ---- ! == 413 tests, 6 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) *************** *** 16,18 **** helgrind/tests/tc20_verifywrap (stderr) - helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) --- 16,17 ---- |
|
From: Tom H. <th...@cy...> - 2008-03-23 03:52:31
|
Nightly build on aston ( x86_64, Fedora Core 5 ) started at 2008-03-23 03:20:07 GMT Results unchanged from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 419 tests, 9 stderr failures, 1 stdout failure, 0 post failures == memcheck/tests/malloc_free_fill (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/x86/scalar (stderr) none/tests/blockfault (stderr) none/tests/faultstatus (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) |
|
From: Tom H. <th...@cy...> - 2008-03-23 03:40:14
|
Nightly build on trojan ( x86_64, Fedora Core 6 ) started at 2008-03-23 03:25:05 GMT Results differ from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 417 tests, 9 stderr failures, 5 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/bug133694 (stdout) memcheck/tests/x86/bug133694 (stderr) memcheck/tests/x86/scalar (stderr) none/tests/cmdline1 (stdout) none/tests/cmdline2 (stdout) none/tests/faultstatus (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Results from 24 hours ago == ================================================= Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 417 tests, 8 stderr failures, 5 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/bug133694 (stdout) memcheck/tests/x86/bug133694 (stderr) memcheck/tests/x86/scalar (stderr) none/tests/cmdline1 (stdout) none/tests/cmdline2 (stdout) none/tests/faultstatus (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Difference between 24 hours ago and now == ================================================= *** old.short Sun Mar 23 03:32:48 2008 --- new.short Sun Mar 23 03:40:20 2008 *************** *** 8,10 **** ! == 417 tests, 8 stderr failures, 5 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) --- 8,10 ---- ! == 417 tests, 9 stderr failures, 5 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) *************** *** 19,20 **** --- 19,21 ---- none/tests/mremap2 (stdout) + helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc20_verifywrap (stderr) |
|
From: Tom H. <th...@cy...> - 2008-03-23 03:33:50
|
Nightly build on dellow ( x86_64, Fedora 8 ) started at 2008-03-23 03:10:03 GMT Results differ from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 413 tests, 8 stderr failures, 3 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/scalar (stderr) none/tests/faultstatus (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) none/tests/pth_cvsimple (stdout) helgrind/tests/tc18_semabuse (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Results from 24 hours ago == ================================================= Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 413 tests, 8 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/scalar (stderr) none/tests/faultstatus (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc18_semabuse (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Difference between 24 hours ago and now == ================================================= *** old.short Sun Mar 23 03:21:59 2008 --- new.short Sun Mar 23 03:33:53 2008 *************** *** 8,10 **** ! == 413 tests, 8 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) --- 8,10 ---- ! == 413 tests, 8 stderr failures, 3 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) *************** *** 15,16 **** --- 15,17 ---- none/tests/mremap2 (stdout) + none/tests/pth_cvsimple (stdout) helgrind/tests/tc18_semabuse (stderr) |
|
From: Tom H. <th...@cy...> - 2008-03-23 03:18:06
|
Nightly build on gill ( x86_64, Fedora Core 2 ) started at 2008-03-23 03:00:02 GMT Results differ from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 419 tests, 31 stderr failures, 3 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/stack_switch (stderr) memcheck/tests/varinfo6 (stderr) memcheck/tests/x86/scalar (stderr) memcheck/tests/x86/scalar_supp (stderr) none/tests/amd64/insn_ssse3 (stdout) none/tests/amd64/insn_ssse3 (stderr) none/tests/amd64/ssse3_misaligned (stderr) none/tests/blockfault (stderr) none/tests/faultstatus (stderr) none/tests/fdleak_fcntl (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) none/tests/x86/insn_ssse3 (stdout) none/tests/x86/insn_ssse3 (stderr) none/tests/x86/ssse3_misaligned (stderr) helgrind/tests/hg01_all_ok (stderr) helgrind/tests/hg02_deadlock (stderr) helgrind/tests/hg03_inherit (stderr) helgrind/tests/hg04_race (stderr) helgrind/tests/hg05_race2 (stderr) helgrind/tests/tc01_simple_race (stderr) helgrind/tests/tc05_simple_race (stderr) helgrind/tests/tc06_two_races (stderr) helgrind/tests/tc09_bad_unlock (stderr) helgrind/tests/tc14_laog_dinphils (stderr) helgrind/tests/tc16_byterace (stderr) helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc19_shadowmem (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) helgrind/tests/tc23_bogus_condwait (stderr) ================================================= == Results from 24 hours ago == ================================================= Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 419 tests, 32 stderr failures, 3 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/stack_switch (stderr) memcheck/tests/varinfo6 (stderr) memcheck/tests/x86/scalar (stderr) memcheck/tests/x86/scalar_supp (stderr) none/tests/amd64/insn_ssse3 (stdout) none/tests/amd64/insn_ssse3 (stderr) none/tests/amd64/ssse3_misaligned (stderr) none/tests/blockfault (stderr) none/tests/faultstatus (stderr) none/tests/fdleak_fcntl (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) none/tests/x86/insn_ssse3 (stdout) none/tests/x86/insn_ssse3 (stderr) none/tests/x86/ssse3_misaligned (stderr) helgrind/tests/hg01_all_ok (stderr) helgrind/tests/hg02_deadlock (stderr) helgrind/tests/hg03_inherit (stderr) helgrind/tests/hg04_race (stderr) helgrind/tests/hg05_race2 (stderr) helgrind/tests/tc01_simple_race (stderr) helgrind/tests/tc05_simple_race (stderr) helgrind/tests/tc06_two_races (stderr) helgrind/tests/tc09_bad_unlock (stderr) helgrind/tests/tc14_laog_dinphils (stderr) helgrind/tests/tc16_byterace (stderr) helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc19_shadowmem (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) helgrind/tests/tc23_bogus_condwait (stderr) exp-drd/tests/pth_create_chain (stderr) ================================================= == Difference between 24 hours ago and now == ================================================= *** old.short Sun Mar 23 03:09:17 2008 --- new.short Sun Mar 23 03:18:10 2008 *************** *** 8,10 **** ! == 419 tests, 32 stderr failures, 3 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) --- 8,10 ---- ! == 419 tests, 31 stderr failures, 3 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) *************** *** 43,45 **** helgrind/tests/tc23_bogus_condwait (stderr) - exp-drd/tests/pth_create_chain (stderr) --- 43,44 ---- |
|
From: Julian S. <js...@ac...> - 2008-03-23 03:04:57
|
On Sunday 23 March 2008 02:01, Nicholas Nethercote wrote:
> > ------ IMark(0x80483D5, 7) ------
> > PUT(60) = 0x80483D5:I32
> > t137 = Left32(t130)
> > t26 = Add32(t25,0xFFFFFFF8:I32)
> > t139 = CmpNEZ32(t137)
> > DIRTY t139 RdFX-gst(16,4) RdFX-gst(60,4) :::
> > MC_(helperc_value_check4_fail){0x38006920}() DIRTY 1:I1 RdFX-gst(16,4)
> > RdFX-gst(60,4) ::: MC_(helperc_STOREV32le)[rp=2]{0x38006d40}(t26,0x0:I32)
> > STle(t26) = 0x4:I32
> > At first glance I would say that the first PUT(60) could be removed,
> > right? It is basically a dead store (assuming it can only be read/write
> > with GET/PUT). I didn't check further why the redudant removal
> > optimization doesn't pick this, so I'm checking here first if this is
> > sane.
>
> It's not removed because there's another statement (the STle) between it
> and the subsequent PUT(60) that could cause a memory exception. A signal
> handler for such an exception might inspect the %eip value, so it has to be
> up-to-date. Annoying, because it's so unlikely, but necessary.
Yes. But not only for the STle, also for the call to
MC_(helperc_value_check4_fail).
If you look at struct VexGuestX86State in libvex_guest_x86.h, you can
see that offset 60 is guest_EIP (the program counter). So the PUT is
updating the simulated program counter, so it is up to date should the
store generate an exception, but also (importantly) so that if
MC_(helperc_value_check4_fail) needs to make a stack backtrace, it will
start from the right point.
MC_(helperc_value_check4_fail) is the function that will, or at least
may, eventually lead to memcheck giving an error "Use of uninitialised
value of size 4".
If you look at priv/guest-x86/ghelpers.c, function
guest_x86_state_requires_precise_mem_exns tells the ir optimiser
(iropt.c) which parts of the guest state must be kept up to date at
all times, basically so that helper functions can get correct
stack backtraces. So it forces EBP, ESP and EIP to always be up
to date; all other guest registers can get completely out of date
and are only sync'd with reality at superblock transitions.
> > Second question is: can the last memcheck check be removed? i.e. the last
> > call to helperc_LOADV32le() is redudant, since it has already done a
> > store to that location and thus it knows that the operation is safe. Can
> > this call be removed? And what value do I assign to t144 then?
> > VA_BITS32_DEFINED? (I'm just considering the simpler case where the
> > #store bits >= #load bits).
>
> I think it is redundant. Since 0x0 (which is VA_BITS32_DEFINED) was the
> shadow store value, you'd assign 0x0 to t144. And you're right that you
> could do likewise if t144 was smaller than 32 bits.
>
> > Allow me just a last question: is it safe to replace the 't30 =
> > LDle:I32(t26)' statement with 't30 = 0x4:I32'? Well in general I would
> > say it is safe, but I dunno about memory-mapped I/O nor if/how valgrind
> > handles it. Maybe this can be done in only certain architectures?
>
> If we're optimising away the shadow load, maybe it's reasonable to optimise
> away the real load, but I'm really not sure about that one. Julian might
> have more to add.
Difficult question! I would comment first that it might be worth looking
at the original code to figure out why the compiler put a store and then
a load from the same location in the next insn. It might be that the
second instruction (0x80483DC) is a branch target, maybe the top of a
loop.
So is it safe to remove the real and shadow load and forward values
directly to it from the real and shadow store? Well, that would probably
work _most_ of the time, but sounds dangerous if multiple threads are
doing spinlocks or something like that - then it might be that changing
the number of memory references might have some bad effect.
J
|
|
From: Nicholas N. <nj...@cs...> - 2008-03-23 01:01:17
|
On Sun, 23 Mar 2008, Nuno Lopes wrote:
> ------ IMark(0x80483CE, 7) ------
> t130 = GET:I32(340)
> t25 = GET:I32(20)
> t132 = Left32(t130)
> t24 = Add32(t25,0xFFFFFFF4:I32)
> t134 = CmpNEZ32(t132)
> DIRTY t134 RdFX-gst(16,4) RdFX-gst(60,4) ::: MC_(helperc_value_check4_fail){0x38006920}()
> DIRTY 1:I1 RdFX-gst(16,4) RdFX-gst(60,4) ::: MC_(helperc_STOREV32le)[rp=2]{0x38006d40}(t24,0x0:I32)
> STle(t24) = 0x2:I32
> ------ IMark(0x80483D5, 7) ------
> PUT(60) = 0x80483D5:I32
> t137 = Left32(t130)
> t26 = Add32(t25,0xFFFFFFF8:I32)
> t139 = CmpNEZ32(t137)
> DIRTY t139 RdFX-gst(16,4) RdFX-gst(60,4) ::: MC_(helperc_value_check4_fail){0x38006920}()
> DIRTY 1:I1 RdFX-gst(16,4) RdFX-gst(60,4) ::: MC_(helperc_STOREV32le)[rp=2]{0x38006d40}(t26,0x0:I32)
> STle(t26) = 0x4:I32
> ------ IMark(0x80483DC, 3) ------
> PUT(60) = 0x80483DC:I32
> IR-NoOp
> t144 = DIRTY 1:I1 RdFX-gst(16,4) RdFX-gst(60,4) ::: MC_(helperc_LOADV32le)[rp=1]{0x380070e0}(t26)
> t30 = LDle:I32(t26)
>
>
> At first glance I would say that the first PUT(60) could be removed, right?
> It is basically a dead store (assuming it can only be read/write with
> GET/PUT). I didn't check further why the redudant removal optimization
> doesn't pick this, so I'm checking here first if this is sane.
It's not removed because there's another statement (the STle) between it and
the subsequent PUT(60) that could cause a memory exception. A signal
handler for such an exception might inspect the %eip value, so it has to be
up-to-date. Annoying, because it's so unlikely, but necessary.
> Second question is: can the last memcheck check be removed? i.e. the last
> call to helperc_LOADV32le() is redudant, since it has already done a store to
> that location and thus it knows that the operation is safe. Can this call be
> removed? And what value do I assign to t144 then? VA_BITS32_DEFINED? (I'm
> just considering the simpler case where the #store bits >= #load bits).
I think it is redundant. Since 0x0 (which is VA_BITS32_DEFINED) was the
shadow store value, you'd assign 0x0 to t144. And you're right that you
could do likewise if t144 was smaller than 32 bits.
> Allow me just a last question: is it safe to replace the 't30 =
> LDle:I32(t26)' statement with 't30 = 0x4:I32'? Well in general I would say it
> is safe, but I dunno about memory-mapped I/O nor if/how valgrind handles it.
> Maybe this can be done in only certain architectures?
If we're optimising away the shadow load, maybe it's reasonable to optimise
away the real load, but I'm really not sure about that one. Julian might
have more to add.
Nick
|
|
From: Nuno L. <nun...@sa...> - 2008-03-23 00:12:27
|
Hi,
So today I was looking a bit to the superblocks with and without
instrumentation and I got the following:
------ IMark(0x80483CE, 7) ------
t130 = GET:I32(340)
t25 = GET:I32(20)
t132 = Left32(t130)
t24 = Add32(t25,0xFFFFFFF4:I32)
t134 = CmpNEZ32(t132)
DIRTY t134 RdFX-gst(16,4) RdFX-gst(60,4) :::
MC_(helperc_value_check4_fail){0x38006920}()
DIRTY 1:I1 RdFX-gst(16,4) RdFX-gst(60,4) :::
MC_(helperc_STOREV32le)[rp=2]{0x38006d40}(t24,0x0:I32)
STle(t24) = 0x2:I32
------ IMark(0x80483D5, 7) ------
PUT(60) = 0x80483D5:I32
t137 = Left32(t130)
t26 = Add32(t25,0xFFFFFFF8:I32)
t139 = CmpNEZ32(t137)
DIRTY t139 RdFX-gst(16,4) RdFX-gst(60,4) :::
MC_(helperc_value_check4_fail){0x38006920}()
DIRTY 1:I1 RdFX-gst(16,4) RdFX-gst(60,4) :::
MC_(helperc_STOREV32le)[rp=2]{0x38006d40}(t26,0x0:I32)
STle(t26) = 0x4:I32
------ IMark(0x80483DC, 3) ------
PUT(60) = 0x80483DC:I32
IR-NoOp
t144 = DIRTY 1:I1 RdFX-gst(16,4) RdFX-gst(60,4) :::
MC_(helperc_LOADV32le)[rp=1]{0x380070e0}(t26)
t30 = LDle:I32(t26)
At first glance I would say that the first PUT(60) could be removed, right?
It is basically a dead store (assuming it can only be read/write with
GET/PUT). I didn't check further why the redudant removal optimization
doesn't pick this, so I'm checking here first if this is sane.
Second question is: can the last memcheck check be removed? i.e. the last
call to helperc_LOADV32le() is redudant, since it has already done a store
to that location and thus it knows that the operation is safe. Can this call
be removed? And what value do I assign to t144 then? VA_BITS32_DEFINED? (I'm
just considering the simpler case where the #store bits >= #load bits).
Allow me just a last question: is it safe to replace the 't30 =
LDle:I32(t26)' statement with 't30 = 0x4:I32'? Well in general I would say
it is safe, but I dunno about memory-mapped I/O nor if/how valgrind handles
it. Maybe this can be done in only certain architectures?
Thanks in advance,
Nuno
|