Implemented segment merging.
git-svn-id: svn://svn.valgrind.org/valgrind/trunk@7750 a5019735-40e9-0310-863c-91ae7b9d1cf9
diff --git a/exp-drd/drd_main.c b/exp-drd/drd_main.c
index 758edc4..32f85bd 100644
--- a/exp-drd/drd_main.c
+++ b/exp-drd/drd_main.c
@@ -71,20 +71,22 @@
static Bool drd_process_cmd_line_option(Char* arg)
{
- Bool show_confl_seg = True;
- Bool trace_barrier = False;
- Bool trace_clientobj = False;
- Bool trace_cond = False;
- Bool trace_csw = False;
- Bool trace_danger_set = False;
- Bool trace_mutex = False;
- Bool trace_rwlock = False;
- Bool trace_segment = False;
- Bool trace_semaphore = False;
- Bool trace_suppression = False;
- Char* trace_address = 0;
+ int segment_merging = -1;
+ int show_confl_seg = -1;
+ int trace_barrier = -1;
+ int trace_clientobj = -1;
+ int trace_cond = -1;
+ int trace_csw = -1;
+ int trace_danger_set = -1;
+ int trace_mutex = -1;
+ int trace_rwlock = -1;
+ int trace_segment = -1;
+ int trace_semaphore = -1;
+ int trace_suppression = -1;
+ Char* trace_address = 0;
VG_BOOL_CLO (arg, "--drd-stats", drd_print_stats)
+ else VG_BOOL_CLO(arg, "--segment-merging", segment_merging)
else VG_BOOL_CLO(arg, "--show-confl-seg", show_confl_seg)
else VG_BOOL_CLO(arg, "--trace-barrier", trace_barrier)
else VG_BOOL_CLO(arg, "--trace-clientobj", trace_clientobj)
@@ -102,31 +104,33 @@
else
return False;
- if (! show_confl_seg)
+ if (segment_merging != -1)
+ thread_set_segment_merging(segment_merging);
+ if (show_confl_seg != -1)
set_show_conflicting_segments(show_confl_seg);
if (trace_address)
{
drd_trace_address = VG_(strtoll16)(trace_address, 0);
}
- if (trace_barrier)
+ if (trace_barrier != -1)
barrier_set_trace(trace_barrier);
- if (trace_clientobj)
+ if (trace_clientobj != -1)
clientobj_set_trace(trace_clientobj);
- if (trace_cond)
+ if (trace_cond != -1)
cond_set_trace(trace_cond);
- if (trace_csw)
+ if (trace_csw != -1)
thread_trace_context_switches(trace_csw);
- if (trace_danger_set)
+ if (trace_danger_set != -1)
thread_trace_danger_set(trace_danger_set);
- if (trace_mutex)
+ if (trace_mutex != -1)
mutex_set_trace(trace_mutex);
- if (trace_rwlock)
+ if (trace_rwlock != -1)
rwlock_set_trace(trace_rwlock);
- if (trace_segment)
+ if (trace_segment != -1)
sg_set_trace(trace_segment);
- if (trace_semaphore)
+ if (trace_semaphore != -1)
semaphore_set_trace(trace_semaphore);
- if (trace_suppression)
+ if (trace_suppression != -1)
suppression_set_trace(trace_suppression);
return True;
diff --git a/exp-drd/drd_segment.c b/exp-drd/drd_segment.c
index 1bb186e..3fbed86 100644
--- a/exp-drd/drd_segment.c
+++ b/exp-drd/drd_segment.c
@@ -188,6 +188,32 @@
}
}
+/** Merge sg1 and sg2 into sg1. */
+void sg_merge(const Segment* const sg1, Segment* const sg2)
+{
+ tl_assert(sg1);
+ tl_assert(sg2);
+
+ if (drd_trace_segment)
+ {
+ char msg[256];
+
+ VG_(snprintf)(msg, sizeof(msg), "Merging segments with vector clocks ");
+ vc_snprint(msg + VG_(strlen)(msg), sizeof(msg) - VG_(strlen)(msg),
+ &sg1->vc);
+ VG_(snprintf)(msg + VG_(strlen)(msg), sizeof(msg) - VG_(strlen)(msg),
+ " and ");
+ vc_snprint(msg + VG_(strlen)(msg), sizeof(msg) - VG_(strlen)(msg),
+ &sg2->vc);
+ VG_(message)(Vg_UserMsg, "%s", msg);
+ }
+
+ // Keep sg1->stacktrace.
+ // Keep sg1->vc.
+ // Merge sg2->bm into sg1->bm.
+ bm_merge2(sg1->bm, sg2->bm);
+}
+
void sg_print(const Segment* const sg)
{
tl_assert(sg);
diff --git a/exp-drd/drd_segment.h b/exp-drd/drd_segment.h
index e7eeeeb..487dc22 100644
--- a/exp-drd/drd_segment.h
+++ b/exp-drd/drd_segment.h
@@ -53,6 +53,7 @@
int sg_get_refcnt(const Segment* const sg);
Segment* sg_get(Segment* const sg);
void sg_put(Segment* const sg);
+void sg_merge(const Segment* const sg1, Segment* const sg2);
void sg_print(const Segment* const sg);
Bool sg_get_trace(void);
void sg_set_trace(const Bool trace_segment);
diff --git a/exp-drd/drd_thread.c b/exp-drd/drd_thread.c
index fe68c45..62eb0f3 100644
--- a/exp-drd/drd_thread.c
+++ b/exp-drd/drd_thread.c
@@ -59,6 +59,7 @@
struct bitmap* s_danger_set;
static Bool s_trace_context_switches = False;
static Bool s_trace_danger_set = False;
+static Bool s_segment_merging = True;
// Function definitions.
@@ -73,6 +74,11 @@
s_trace_danger_set = t;
}
+void thread_set_segment_merging(const Bool m)
+{
+ s_segment_merging = m;
+}
+
__inline__ Bool IsValidDrdThreadId(const DrdThreadId tid)
{
return (0 <= tid && tid < DRD_N_THREADS && tid != DRD_INVALID_THREADID
@@ -538,6 +544,41 @@
vc_cleanup(&thread_vc_min);
}
+/** Merge all segments that may be merged without triggering false positives
+ * or discarding real data races. For the theoretical background of segment
+ * merging, see also the following paper:
+ * Mark Christiaens, Michiel Ronsse and Koen De Bosschere.
+ * Bounding the number of segment histories during data race detection.
+ * Parallel Computing archive, Volume 28, Issue 9, pp 1221-1238,
+ * September 2002.
+ */
+static void thread_merge_segments(void)
+{
+ unsigned i;
+
+ for (i = 0; i < sizeof(s_threadinfo) / sizeof(s_threadinfo[0]); i++)
+ {
+ Segment* sg;
+
+ tl_assert(sane_ThreadInfo(&s_threadinfo[i]));
+
+ for (sg = s_threadinfo[i].first; sg; sg = sg->next)
+ {
+ if (sg_get_refcnt(sg) == 1
+ && sg->next
+ && sg_get_refcnt(sg->next) == 1
+ && sg->next->next)
+ {
+ /* Merge sg and sg->next into sg. */
+ sg_merge(sg, sg->next);
+ thread_discard_segment(i, sg->next);
+ }
+ }
+
+ tl_assert(sane_ThreadInfo(&s_threadinfo[i]));
+ }
+}
+
/** Create a new segment for the specified thread, and discard any segments
* that cannot cause races anymore.
*/
@@ -549,6 +590,9 @@
thread_discard_ordered_segments();
+ if (s_segment_merging)
+ thread_merge_segments();
+
if (tid == s_drd_running_tid)
{
/* Every change in the vector clock of the current thread may cause */
diff --git a/exp-drd/drd_thread.h b/exp-drd/drd_thread.h
index 66aa637..bbfbbd8 100644
--- a/exp-drd/drd_thread.h
+++ b/exp-drd/drd_thread.h
@@ -89,6 +89,7 @@
void thread_trace_context_switches(const Bool t);
void thread_trace_danger_set(const Bool t);
+void thread_set_segment_merging(const Bool m);
Bool IsValidDrdThreadId(const DrdThreadId tid);
DrdThreadId VgThreadIdToDrdThreadId(const ThreadId tid);