1 /*
2 This file is part of drd, a thread error detector.
3
4 Copyright (C) 2006-2013 Bart Van Assche <bvanassche@acm.org>.
5
6 This program is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as
8 published by the Free Software Foundation; either version 2 of the
9 License, or (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19 02111-1307, USA.
20
21 The GNU General Public License is contained in the file COPYING.
22 */
23
24
25 #include "drd_error.h"
26 #include "drd_barrier.h"
27 #include "drd_clientobj.h"
28 #include "drd_cond.h"
29 #include "drd_mutex.h"
30 #include "drd_segment.h"
31 #include "drd_semaphore.h"
32 #include "drd_suppression.h"
33 #include "drd_thread.h"
34 #include "pub_tool_vki.h"
35 #include "pub_tool_basics.h" // Addr, SizeT
36 #include "pub_tool_libcassert.h" // tl_assert()
37 #include "pub_tool_libcbase.h" // VG_(strlen)()
38 #include "pub_tool_libcprint.h" // VG_(printf)()
39 #include "pub_tool_machine.h"
40 #include "pub_tool_mallocfree.h" // VG_(malloc)(), VG_(free)()
41 #include "pub_tool_options.h" // VG_(clo_backtrace_size)
42 #include "pub_tool_threadstate.h" // VG_(get_pthread_id)()
43
44
45
46 /* Local functions. */
47
48 static void thread_append_segment(const DrdThreadId tid, Segment* const sg);
49 static void thread_discard_segment(const DrdThreadId tid, Segment* const sg);
50 static void thread_compute_conflict_set(struct bitmap** conflict_set,
51 const DrdThreadId tid);
52 static Bool thread_conflict_set_up_to_date(const DrdThreadId tid);
53
54
55 /* Local variables. */
56
57 static ULong s_context_switch_count;
58 static ULong s_discard_ordered_segments_count;
59 static ULong s_compute_conflict_set_count;
60 static ULong s_update_conflict_set_count;
61 static ULong s_update_conflict_set_new_sg_count;
62 static ULong s_update_conflict_set_sync_count;
63 static ULong s_update_conflict_set_join_count;
64 static ULong s_conflict_set_bitmap_creation_count;
65 static ULong s_conflict_set_bitmap2_creation_count;
66 static ThreadId s_vg_running_tid = VG_INVALID_THREADID;
67 DrdThreadId DRD_(g_drd_running_tid) = DRD_INVALID_THREADID;
68 ThreadInfo* DRD_(g_threadinfo);
69 struct bitmap* DRD_(g_conflict_set);
70 Bool DRD_(verify_conflict_set);
71 static Bool s_trace_context_switches = False;
72 static Bool s_trace_conflict_set = False;
73 static Bool s_trace_conflict_set_bm = False;
74 static Bool s_trace_fork_join = False;
75 static Bool s_segment_merging = True;
76 static Bool s_new_segments_since_last_merge;
77 static int s_segment_merge_interval = 10;
78 static unsigned s_join_list_vol = 10;
79 static unsigned s_deletion_head;
80 static unsigned s_deletion_tail;
81
82
83 /* Function definitions. */
84
85 /** Enables/disables context switch tracing. */
DRD_(thread_trace_context_switches)86 void DRD_(thread_trace_context_switches)(const Bool t)
87 {
88 tl_assert(t == False || t == True);
89 s_trace_context_switches = t;
90 }
91
92 /** Enables/disables conflict set tracing. */
DRD_(thread_trace_conflict_set)93 void DRD_(thread_trace_conflict_set)(const Bool t)
94 {
95 tl_assert(t == False || t == True);
96 s_trace_conflict_set = t;
97 }
98
99 /** Enables/disables conflict set bitmap tracing. */
DRD_(thread_trace_conflict_set_bm)100 void DRD_(thread_trace_conflict_set_bm)(const Bool t)
101 {
102 tl_assert(t == False || t == True);
103 s_trace_conflict_set_bm = t;
104 }
105
106 /** Report whether fork/join tracing is enabled. */
DRD_(thread_get_trace_fork_join)107 Bool DRD_(thread_get_trace_fork_join)(void)
108 {
109 return s_trace_fork_join;
110 }
111
112 /** Enables/disables fork/join tracing. */
DRD_(thread_set_trace_fork_join)113 void DRD_(thread_set_trace_fork_join)(const Bool t)
114 {
115 tl_assert(t == False || t == True);
116 s_trace_fork_join = t;
117 }
118
119 /** Enables/disables segment merging. */
DRD_(thread_set_segment_merging)120 void DRD_(thread_set_segment_merging)(const Bool m)
121 {
122 tl_assert(m == False || m == True);
123 s_segment_merging = m;
124 }
125
126 /** Get the segment merging interval. */
DRD_(thread_get_segment_merge_interval)127 int DRD_(thread_get_segment_merge_interval)(void)
128 {
129 return s_segment_merge_interval;
130 }
131
132 /** Set the segment merging interval. */
DRD_(thread_set_segment_merge_interval)133 void DRD_(thread_set_segment_merge_interval)(const int i)
134 {
135 s_segment_merge_interval = i;
136 }
137
DRD_(thread_set_join_list_vol)138 void DRD_(thread_set_join_list_vol)(const int jlv)
139 {
140 s_join_list_vol = jlv;
141 }
142
DRD_(thread_init)143 void DRD_(thread_init)(void)
144 {
145 DRD_(g_threadinfo) = VG_(malloc)("drd.main.ti.1",
146 DRD_N_THREADS * sizeof DRD_(g_threadinfo)[0]);
147 for (UInt i = 0; i < DRD_N_THREADS; ++i) {
148 static ThreadInfo initval;
149 DRD_(g_threadinfo)[i] = initval;
150 }
151 }
152
153 /**
154 * Convert Valgrind's ThreadId into a DrdThreadId.
155 *
156 * @return DRD thread ID upon success and DRD_INVALID_THREADID if the passed
157 * Valgrind ThreadId does not yet exist.
158 */
DRD_(VgThreadIdToDrdThreadId)159 DrdThreadId DRD_(VgThreadIdToDrdThreadId)(const ThreadId tid)
160 {
161 UInt i;
162
163 if (tid == VG_INVALID_THREADID)
164 return DRD_INVALID_THREADID;
165
166 for (i = 1; i < DRD_N_THREADS; i++)
167 {
168 if (DRD_(g_threadinfo)[i].vg_thread_exists == True
169 && DRD_(g_threadinfo)[i].vg_threadid == tid)
170 {
171 return i;
172 }
173 }
174
175 return DRD_INVALID_THREADID;
176 }
177
178 /** Allocate a new DRD thread ID for the specified Valgrind thread ID. */
DRD_(VgThreadIdToNewDrdThreadId)179 static DrdThreadId DRD_(VgThreadIdToNewDrdThreadId)(const ThreadId tid)
180 {
181 UInt i;
182
183 tl_assert(DRD_(VgThreadIdToDrdThreadId)(tid) == DRD_INVALID_THREADID);
184
185 for (i = 1; i < DRD_N_THREADS; i++)
186 {
187 if (!DRD_(g_threadinfo)[i].valid)
188 {
189 tl_assert(! DRD_(IsValidDrdThreadId)(i));
190
191 DRD_(g_threadinfo)[i].valid = True;
192 DRD_(g_threadinfo)[i].vg_thread_exists = True;
193 DRD_(g_threadinfo)[i].vg_threadid = tid;
194 DRD_(g_threadinfo)[i].pt_threadid = INVALID_POSIX_THREADID;
195 DRD_(g_threadinfo)[i].stack_min = 0;
196 DRD_(g_threadinfo)[i].stack_min_min = 0;
197 DRD_(g_threadinfo)[i].stack_startup = 0;
198 DRD_(g_threadinfo)[i].stack_max = 0;
199 DRD_(thread_set_name)(i, "");
200 DRD_(g_threadinfo)[i].on_alt_stack = False;
201 DRD_(g_threadinfo)[i].is_recording_loads = True;
202 DRD_(g_threadinfo)[i].is_recording_stores = True;
203 DRD_(g_threadinfo)[i].pthread_create_nesting_level = 0;
204 DRD_(g_threadinfo)[i].synchr_nesting = 0;
205 DRD_(g_threadinfo)[i].deletion_seq = s_deletion_tail - 1;
206 tl_assert(DRD_(g_threadinfo)[i].sg_first == NULL);
207 tl_assert(DRD_(g_threadinfo)[i].sg_last == NULL);
208
209 tl_assert(DRD_(IsValidDrdThreadId)(i));
210
211 return i;
212 }
213 }
214
215 VG_(printf)(
216 "\nSorry, but the maximum number of threads supported by DRD has been exceeded."
217 "Aborting.\n");
218
219 tl_assert(False);
220
221 return DRD_INVALID_THREADID;
222 }
223
224 /** Convert a POSIX thread ID into a DRD thread ID. */
DRD_(PtThreadIdToDrdThreadId)225 DrdThreadId DRD_(PtThreadIdToDrdThreadId)(const PThreadId tid)
226 {
227 UInt i;
228
229 if (tid != INVALID_POSIX_THREADID)
230 {
231 for (i = 1; i < DRD_N_THREADS; i++)
232 {
233 if (DRD_(g_threadinfo)[i].posix_thread_exists
234 && DRD_(g_threadinfo)[i].pt_threadid == tid)
235 {
236 return i;
237 }
238 }
239 }
240 return DRD_INVALID_THREADID;
241 }
242
243 /** Convert a DRD thread ID into a Valgrind thread ID. */
DRD_(DrdThreadIdToVgThreadId)244 ThreadId DRD_(DrdThreadIdToVgThreadId)(const DrdThreadId tid)
245 {
246 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
247 && tid != DRD_INVALID_THREADID);
248
249 return (DRD_(g_threadinfo)[tid].vg_thread_exists
250 ? DRD_(g_threadinfo)[tid].vg_threadid
251 : VG_INVALID_THREADID);
252 }
253
254 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
255 /**
256 * Sanity check of the doubly linked list of segments referenced by a
257 * ThreadInfo struct.
258 * @return True if sane, False if not.
259 */
DRD_(sane_ThreadInfo)260 static Bool DRD_(sane_ThreadInfo)(const ThreadInfo* const ti)
261 {
262 Segment* p;
263
264 for (p = ti->sg_first; p; p = p->thr_next) {
265 if (p->thr_next && p->thr_next->thr_prev != p)
266 return False;
267 if (p->thr_next == 0 && p != ti->sg_last)
268 return False;
269 }
270 for (p = ti->sg_last; p; p = p->thr_prev) {
271 if (p->thr_prev && p->thr_prev->thr_next != p)
272 return False;
273 if (p->thr_prev == 0 && p != ti->sg_first)
274 return False;
275 }
276 return True;
277 }
278 #endif
279
280 /**
281 * Create the first segment for a newly started thread.
282 *
283 * This function is called from the handler installed via
284 * VG_(track_pre_thread_ll_create)(). The Valgrind core invokes this handler
285 * from the context of the creator thread, before the new thread has been
286 * created.
287 *
288 * @param[in] creator DRD thread ID of the creator thread.
289 * @param[in] vg_created Valgrind thread ID of the created thread.
290 *
291 * @return DRD thread ID of the created thread.
292 */
DRD_(thread_pre_create)293 DrdThreadId DRD_(thread_pre_create)(const DrdThreadId creator,
294 const ThreadId vg_created)
295 {
296 DrdThreadId created;
297
298 tl_assert(DRD_(VgThreadIdToDrdThreadId)(vg_created) == DRD_INVALID_THREADID);
299 created = DRD_(VgThreadIdToNewDrdThreadId)(vg_created);
300 tl_assert(0 <= (int)created && created < DRD_N_THREADS
301 && created != DRD_INVALID_THREADID);
302
303 tl_assert(DRD_(g_threadinfo)[created].sg_first == NULL);
304 tl_assert(DRD_(g_threadinfo)[created].sg_last == NULL);
305 /* Create an initial segment for the newly created thread. */
306 thread_append_segment(created, DRD_(sg_new)(creator, created));
307
308 return created;
309 }
310
311 /**
312 * Initialize DRD_(g_threadinfo)[] for a newly created thread. Must be called
313 * after the thread has been created and before any client instructions are run
314 * on the newly created thread, e.g. from the handler installed via
315 * VG_(track_pre_thread_first_insn)().
316 *
317 * @param[in] vg_created Valgrind thread ID of the newly created thread.
318 *
319 * @return DRD thread ID for the new thread.
320 */
DRD_(thread_post_create)321 DrdThreadId DRD_(thread_post_create)(const ThreadId vg_created)
322 {
323 const DrdThreadId created = DRD_(VgThreadIdToDrdThreadId)(vg_created);
324
325 tl_assert(0 <= (int)created && created < DRD_N_THREADS
326 && created != DRD_INVALID_THREADID);
327
328 DRD_(g_threadinfo)[created].stack_max
329 = VG_(thread_get_stack_max)(vg_created);
330 DRD_(g_threadinfo)[created].stack_startup
331 = DRD_(g_threadinfo)[created].stack_max;
332 DRD_(g_threadinfo)[created].stack_min
333 = DRD_(g_threadinfo)[created].stack_max;
334 DRD_(g_threadinfo)[created].stack_min_min
335 = DRD_(g_threadinfo)[created].stack_max;
336 DRD_(g_threadinfo)[created].stack_size
337 = VG_(thread_get_stack_size)(vg_created);
338 tl_assert(DRD_(g_threadinfo)[created].stack_max != 0);
339
340 return created;
341 }
342
DRD_(thread_delayed_delete)343 static void DRD_(thread_delayed_delete)(const DrdThreadId tid)
344 {
345 UInt j;
346
347 DRD_(g_threadinfo)[tid].vg_thread_exists = False;
348 DRD_(g_threadinfo)[tid].posix_thread_exists = False;
349 DRD_(g_threadinfo)[tid].deletion_seq = s_deletion_head++;
350 #if 0
351 VG_(message)(Vg_DebugMsg, "Adding thread %d to the deletion list\n", tid);
352 #endif
353 if (s_deletion_head - s_deletion_tail >= s_join_list_vol) {
354 for (j = 0; j < DRD_N_THREADS; ++j) {
355 if (DRD_(IsValidDrdThreadId)(j)
356 && DRD_(g_threadinfo)[j].deletion_seq == s_deletion_tail)
357 {
358 s_deletion_tail++;
359 #if 0
360 VG_(message)(Vg_DebugMsg, "Delayed delete of thread %d\n", j);
361 #endif
362 DRD_(thread_delete)(j, False);
363 break;
364 }
365 }
366 }
367 }
368
369 /**
370 * Process VG_USERREQ__POST_THREAD_JOIN. This client request is invoked just
371 * after thread drd_joiner joined thread drd_joinee.
372 */
DRD_(thread_post_join)373 void DRD_(thread_post_join)(DrdThreadId drd_joiner, DrdThreadId drd_joinee)
374 {
375 tl_assert(DRD_(IsValidDrdThreadId)(drd_joiner));
376 tl_assert(DRD_(IsValidDrdThreadId)(drd_joinee));
377
378 DRD_(thread_new_segment)(drd_joiner);
379 DRD_(thread_combine_vc_join)(drd_joiner, drd_joinee);
380 DRD_(thread_new_segment)(drd_joinee);
381
382 if (s_trace_fork_join)
383 {
384 const ThreadId joiner = DRD_(DrdThreadIdToVgThreadId)(drd_joiner);
385 const unsigned msg_size = 256;
386 HChar* msg;
387
388 msg = VG_(malloc)("drd.main.dptj.1", msg_size);
389
390 VG_(snprintf)(msg, msg_size,
391 "drd_post_thread_join joiner = %d, joinee = %d",
392 drd_joiner, drd_joinee);
393 if (joiner)
394 {
395 HChar* vc;
396
397 vc = DRD_(vc_aprint)(DRD_(thread_get_vc)(drd_joiner));
398 VG_(snprintf)(msg + VG_(strlen)(msg), msg_size - VG_(strlen)(msg),
399 ", new vc: %s", vc);
400 VG_(free)(vc);
401 }
402 DRD_(trace_msg)("%pS", msg);
403 VG_(free)(msg);
404 }
405
406 if (! DRD_(get_check_stack_accesses)())
407 {
408 DRD_(finish_suppression)(DRD_(thread_get_stack_max)(drd_joinee)
409 - DRD_(thread_get_stack_size)(drd_joinee),
410 DRD_(thread_get_stack_max)(drd_joinee));
411 }
412 DRD_(clientobj_delete_thread)(drd_joinee);
413 DRD_(thread_delayed_delete)(drd_joinee);
414 }
415
416 /**
417 * NPTL hack: NPTL allocates the 'struct pthread' on top of the stack,
418 * and accesses this data structure from multiple threads without locking.
419 * Any conflicting accesses in the range stack_startup..stack_max will be
420 * ignored.
421 */
DRD_(thread_set_stack_startup)422 void DRD_(thread_set_stack_startup)(const DrdThreadId tid,
423 const Addr stack_startup)
424 {
425 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
426 && tid != DRD_INVALID_THREADID);
427 tl_assert(DRD_(g_threadinfo)[tid].stack_min <= stack_startup);
428 tl_assert(stack_startup <= DRD_(g_threadinfo)[tid].stack_max);
429 DRD_(g_threadinfo)[tid].stack_startup = stack_startup;
430 }
431
432 /** Return the stack pointer for the specified thread. */
DRD_(thread_get_stack_min)433 Addr DRD_(thread_get_stack_min)(const DrdThreadId tid)
434 {
435 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
436 && tid != DRD_INVALID_THREADID);
437 return DRD_(g_threadinfo)[tid].stack_min;
438 }
439
440 /**
441 * Return the lowest value that was ever assigned to the stack pointer
442 * for the specified thread.
443 */
DRD_(thread_get_stack_min_min)444 Addr DRD_(thread_get_stack_min_min)(const DrdThreadId tid)
445 {
446 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
447 && tid != DRD_INVALID_THREADID);
448 return DRD_(g_threadinfo)[tid].stack_min_min;
449 }
450
451 /** Return the top address for the stack of the specified thread. */
DRD_(thread_get_stack_max)452 Addr DRD_(thread_get_stack_max)(const DrdThreadId tid)
453 {
454 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
455 && tid != DRD_INVALID_THREADID);
456 return DRD_(g_threadinfo)[tid].stack_max;
457 }
458
459 /** Return the maximum stack size for the specified thread. */
DRD_(thread_get_stack_size)460 SizeT DRD_(thread_get_stack_size)(const DrdThreadId tid)
461 {
462 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
463 && tid != DRD_INVALID_THREADID);
464 return DRD_(g_threadinfo)[tid].stack_size;
465 }
466
DRD_(thread_get_on_alt_stack)467 Bool DRD_(thread_get_on_alt_stack)(const DrdThreadId tid)
468 {
469 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
470 && tid != DRD_INVALID_THREADID);
471 return DRD_(g_threadinfo)[tid].on_alt_stack;
472 }
473
DRD_(thread_set_on_alt_stack)474 void DRD_(thread_set_on_alt_stack)(const DrdThreadId tid,
475 const Bool on_alt_stack)
476 {
477 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
478 && tid != DRD_INVALID_THREADID);
479 tl_assert(on_alt_stack == !!on_alt_stack);
480 DRD_(g_threadinfo)[tid].on_alt_stack = on_alt_stack;
481 }
482
DRD_(thread_get_threads_on_alt_stack)483 Int DRD_(thread_get_threads_on_alt_stack)(void)
484 {
485 int n = 0;
486
487 for (UInt i = 1; i < DRD_N_THREADS; i++)
488 n += DRD_(g_threadinfo)[i].on_alt_stack;
489 return n;
490 }
491
492 /**
493 * Clean up thread-specific data structures.
494 */
DRD_(thread_delete)495 void DRD_(thread_delete)(const DrdThreadId tid, const Bool detached)
496 {
497 Segment* sg;
498 Segment* sg_prev;
499
500 tl_assert(DRD_(IsValidDrdThreadId)(tid));
501
502 tl_assert(DRD_(g_threadinfo)[tid].synchr_nesting >= 0);
503 for (sg = DRD_(g_threadinfo)[tid].sg_last; sg; sg = sg_prev) {
504 sg_prev = sg->thr_prev;
505 sg->thr_next = NULL;
506 sg->thr_prev = NULL;
507 DRD_(sg_put)(sg);
508 }
509 DRD_(g_threadinfo)[tid].valid = False;
510 DRD_(g_threadinfo)[tid].vg_thread_exists = False;
511 DRD_(g_threadinfo)[tid].posix_thread_exists = False;
512 if (detached)
513 DRD_(g_threadinfo)[tid].detached_posix_thread = False;
514 else
515 tl_assert(!DRD_(g_threadinfo)[tid].detached_posix_thread);
516 DRD_(g_threadinfo)[tid].sg_first = NULL;
517 DRD_(g_threadinfo)[tid].sg_last = NULL;
518
519 tl_assert(!DRD_(IsValidDrdThreadId)(tid));
520 }
521
522 /**
523 * Called after a thread performed its last memory access and before
524 * thread_delete() is called. Note: thread_delete() is only called for
525 * joinable threads, not for detached threads.
526 */
DRD_(thread_finished)527 void DRD_(thread_finished)(const DrdThreadId tid)
528 {
529 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
530 && tid != DRD_INVALID_THREADID);
531
532 DRD_(g_threadinfo)[tid].vg_thread_exists = False;
533
534 if (DRD_(g_threadinfo)[tid].detached_posix_thread)
535 {
536 /*
537 * Once a detached thread has finished, its stack is deallocated and
538 * should no longer be taken into account when computing the conflict set.
539 */
540 DRD_(g_threadinfo)[tid].stack_min = DRD_(g_threadinfo)[tid].stack_max;
541
542 /*
543 * For a detached thread, calling pthread_exit() invalidates the
544 * POSIX thread ID associated with the detached thread. For joinable
545 * POSIX threads however, the POSIX thread ID remains live after the
546 * pthread_exit() call until pthread_join() is called.
547 */
548 DRD_(g_threadinfo)[tid].posix_thread_exists = False;
549 }
550 }
551
552 /** Called just after fork() in the child process. */
DRD_(drd_thread_atfork_child)553 void DRD_(drd_thread_atfork_child)(const DrdThreadId tid)
554 {
555 unsigned i;
556
557 for (i = 1; i < DRD_N_THREADS; i++)
558 {
559 if (i == tid)
560 continue;
561 if (DRD_(IsValidDrdThreadId(i)))
562 DRD_(thread_delete)(i, True);
563 tl_assert(!DRD_(IsValidDrdThreadId(i)));
564 }
565
566 DRD_(bm_cleanup)(DRD_(g_conflict_set));
567 DRD_(bm_init)(DRD_(g_conflict_set));
568 }
569
570 /** Called just before pthread_cancel(). */
DRD_(thread_pre_cancel)571 void DRD_(thread_pre_cancel)(const DrdThreadId tid)
572 {
573 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
574 && tid != DRD_INVALID_THREADID);
575 tl_assert(DRD_(g_threadinfo)[tid].pt_threadid != INVALID_POSIX_THREADID);
576
577 if (DRD_(thread_get_trace_fork_join)())
578 DRD_(trace_msg)("[%d] drd_thread_pre_cancel %d",
579 DRD_(g_drd_running_tid), tid);
580 }
581
582 /**
583 * Store the POSIX thread ID for the specified thread.
584 *
585 * @note This function can be called two times for the same thread -- see also
586 * the comment block preceding the pthread_create() wrapper in
587 * drd_pthread_intercepts.c.
588 */
DRD_(thread_set_pthreadid)589 void DRD_(thread_set_pthreadid)(const DrdThreadId tid, const PThreadId ptid)
590 {
591 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
592 && tid != DRD_INVALID_THREADID);
593 tl_assert(DRD_(g_threadinfo)[tid].pt_threadid == INVALID_POSIX_THREADID
594 || DRD_(g_threadinfo)[tid].pt_threadid == ptid);
595 tl_assert(ptid != INVALID_POSIX_THREADID);
596 DRD_(g_threadinfo)[tid].posix_thread_exists = True;
597 DRD_(g_threadinfo)[tid].pt_threadid = ptid;
598 }
599
600 /** Returns true for joinable threads and false for detached threads. */
DRD_(thread_get_joinable)601 Bool DRD_(thread_get_joinable)(const DrdThreadId tid)
602 {
603 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
604 && tid != DRD_INVALID_THREADID);
605 return ! DRD_(g_threadinfo)[tid].detached_posix_thread;
606 }
607
608 /** Store the thread mode: joinable or detached. */
609 #if defined(VGP_mips32_linux) || defined(VGP_mips64_linux)
610 /* There is a cse related issue in gcc for MIPS. Optimization level
611 has to be lowered, so cse related optimizations are not
612 included.*/
613 __attribute__((optimize("O1")))
614 #endif
DRD_(thread_set_joinable)615 void DRD_(thread_set_joinable)(const DrdThreadId tid, const Bool joinable)
616 {
617 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
618 && tid != DRD_INVALID_THREADID);
619 tl_assert((!! joinable) == joinable);
620 tl_assert(DRD_(g_threadinfo)[tid].pt_threadid != INVALID_POSIX_THREADID);
621
622 DRD_(g_threadinfo)[tid].detached_posix_thread = ! joinable;
623 }
624
625 /** Tells DRD that the calling thread is about to enter pthread_create(). */
DRD_(thread_entering_pthread_create)626 void DRD_(thread_entering_pthread_create)(const DrdThreadId tid)
627 {
628 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
629 && tid != DRD_INVALID_THREADID);
630 tl_assert(DRD_(g_threadinfo)[tid].pt_threadid != INVALID_POSIX_THREADID);
631 tl_assert(DRD_(g_threadinfo)[tid].pthread_create_nesting_level >= 0);
632
633 DRD_(g_threadinfo)[tid].pthread_create_nesting_level++;
634 }
635
636 /** Tells DRD that the calling thread has left pthread_create(). */
DRD_(thread_left_pthread_create)637 void DRD_(thread_left_pthread_create)(const DrdThreadId tid)
638 {
639 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
640 && tid != DRD_INVALID_THREADID);
641 tl_assert(DRD_(g_threadinfo)[tid].pt_threadid != INVALID_POSIX_THREADID);
642 tl_assert(DRD_(g_threadinfo)[tid].pthread_create_nesting_level > 0);
643
644 DRD_(g_threadinfo)[tid].pthread_create_nesting_level--;
645 }
646
647 /** Obtain the thread number and the user-assigned thread name. */
DRD_(thread_get_name)648 const HChar* DRD_(thread_get_name)(const DrdThreadId tid)
649 {
650 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
651 && tid != DRD_INVALID_THREADID);
652
653 return DRD_(g_threadinfo)[tid].name;
654 }
655
656 /** Set the name of the specified thread. */
DRD_(thread_set_name)657 void DRD_(thread_set_name)(const DrdThreadId tid, const HChar* const name)
658 {
659 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
660 && tid != DRD_INVALID_THREADID);
661
662 if (name == NULL || name[0] == 0)
663 VG_(snprintf)(DRD_(g_threadinfo)[tid].name,
664 sizeof(DRD_(g_threadinfo)[tid].name),
665 "Thread %d",
666 tid);
667 else
668 VG_(snprintf)(DRD_(g_threadinfo)[tid].name,
669 sizeof(DRD_(g_threadinfo)[tid].name),
670 "Thread %d (%s)",
671 tid, name);
672 DRD_(g_threadinfo)[tid].name[sizeof(DRD_(g_threadinfo)[tid].name) - 1] = 0;
673 }
674
675 /**
676 * Update s_vg_running_tid, DRD_(g_drd_running_tid) and recalculate the
677 * conflict set.
678 */
DRD_(thread_set_vg_running_tid)679 void DRD_(thread_set_vg_running_tid)(const ThreadId vg_tid)
680 {
681 tl_assert(vg_tid != VG_INVALID_THREADID);
682
683 if (vg_tid != s_vg_running_tid)
684 {
685 DRD_(thread_set_running_tid)(vg_tid,
686 DRD_(VgThreadIdToDrdThreadId)(vg_tid));
687 }
688
689 tl_assert(s_vg_running_tid != VG_INVALID_THREADID);
690 tl_assert(DRD_(g_drd_running_tid) != DRD_INVALID_THREADID);
691 }
692
693 /**
694 * Update s_vg_running_tid, DRD_(g_drd_running_tid) and recalculate the
695 * conflict set.
696 */
DRD_(thread_set_running_tid)697 void DRD_(thread_set_running_tid)(const ThreadId vg_tid,
698 const DrdThreadId drd_tid)
699 {
700 tl_assert(vg_tid != VG_INVALID_THREADID);
701 tl_assert(drd_tid != DRD_INVALID_THREADID);
702
703 if (vg_tid != s_vg_running_tid)
704 {
705 if (s_trace_context_switches
706 && DRD_(g_drd_running_tid) != DRD_INVALID_THREADID)
707 {
708 VG_(message)(Vg_DebugMsg,
709 "Context switch from thread %d to thread %d;"
710 " segments: %llu\n",
711 DRD_(g_drd_running_tid), drd_tid,
712 DRD_(sg_get_segments_alive_count)());
713 }
714 s_vg_running_tid = vg_tid;
715 DRD_(g_drd_running_tid) = drd_tid;
716 thread_compute_conflict_set(&DRD_(g_conflict_set), drd_tid);
717 s_context_switch_count++;
718 }
719
720 tl_assert(s_vg_running_tid != VG_INVALID_THREADID);
721 tl_assert(DRD_(g_drd_running_tid) != DRD_INVALID_THREADID);
722 }
723
724 /**
725 * Increase the synchronization nesting counter. Must be called before the
726 * client calls a synchronization function.
727 */
DRD_(thread_enter_synchr)728 int DRD_(thread_enter_synchr)(const DrdThreadId tid)
729 {
730 tl_assert(DRD_(IsValidDrdThreadId)(tid));
731 return DRD_(g_threadinfo)[tid].synchr_nesting++;
732 }
733
734 /**
735 * Decrease the synchronization nesting counter. Must be called after the
736 * client left a synchronization function.
737 */
DRD_(thread_leave_synchr)738 int DRD_(thread_leave_synchr)(const DrdThreadId tid)
739 {
740 tl_assert(DRD_(IsValidDrdThreadId)(tid));
741 tl_assert(DRD_(g_threadinfo)[tid].synchr_nesting >= 1);
742 return --DRD_(g_threadinfo)[tid].synchr_nesting;
743 }
744
745 /** Returns the synchronization nesting counter. */
DRD_(thread_get_synchr_nesting_count)746 int DRD_(thread_get_synchr_nesting_count)(const DrdThreadId tid)
747 {
748 tl_assert(DRD_(IsValidDrdThreadId)(tid));
749 return DRD_(g_threadinfo)[tid].synchr_nesting;
750 }
751
752 /** Append a new segment at the end of the segment list. */
753 static
thread_append_segment(const DrdThreadId tid,Segment * const sg)754 void thread_append_segment(const DrdThreadId tid, Segment* const sg)
755 {
756 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
757 && tid != DRD_INVALID_THREADID);
758
759 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
760 tl_assert(DRD_(sane_ThreadInfo)(&DRD_(g_threadinfo)[tid]));
761 #endif
762
763 // add at tail
764 sg->thr_prev = DRD_(g_threadinfo)[tid].sg_last;
765 sg->thr_next = NULL;
766 if (DRD_(g_threadinfo)[tid].sg_last)
767 DRD_(g_threadinfo)[tid].sg_last->thr_next = sg;
768 DRD_(g_threadinfo)[tid].sg_last = sg;
769 if (DRD_(g_threadinfo)[tid].sg_first == NULL)
770 DRD_(g_threadinfo)[tid].sg_first = sg;
771
772 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
773 tl_assert(DRD_(sane_ThreadInfo)(&DRD_(g_threadinfo)[tid]));
774 #endif
775 }
776
777 /**
778 * Remove a segment from the segment list of thread threadid, and free the
779 * associated memory.
780 */
781 static
thread_discard_segment(const DrdThreadId tid,Segment * const sg)782 void thread_discard_segment(const DrdThreadId tid, Segment* const sg)
783 {
784 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
785 && tid != DRD_INVALID_THREADID);
786
787 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
788 tl_assert(DRD_(sane_ThreadInfo)(&DRD_(g_threadinfo)[tid]));
789 #endif
790
791 if (sg->thr_prev)
792 sg->thr_prev->thr_next = sg->thr_next;
793 if (sg->thr_next)
794 sg->thr_next->thr_prev = sg->thr_prev;
795 if (sg == DRD_(g_threadinfo)[tid].sg_first)
796 DRD_(g_threadinfo)[tid].sg_first = sg->thr_next;
797 if (sg == DRD_(g_threadinfo)[tid].sg_last)
798 DRD_(g_threadinfo)[tid].sg_last = sg->thr_prev;
799 DRD_(sg_put)(sg);
800
801 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
802 tl_assert(DRD_(sane_ThreadInfo)(&DRD_(g_threadinfo)[tid]));
803 #endif
804 }
805
806 /**
807 * Returns a pointer to the vector clock of the most recent segment associated
808 * with thread 'tid'.
809 */
DRD_(thread_get_vc)810 VectorClock* DRD_(thread_get_vc)(const DrdThreadId tid)
811 {
812 Segment* latest_sg;
813
814 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
815 && tid != DRD_INVALID_THREADID);
816 latest_sg = DRD_(g_threadinfo)[tid].sg_last;
817 tl_assert(latest_sg);
818 return &latest_sg->vc;
819 }
820
821 /**
822 * Return the latest segment of thread 'tid' and increment its reference count.
823 */
DRD_(thread_get_latest_segment)824 void DRD_(thread_get_latest_segment)(Segment** sg, const DrdThreadId tid)
825 {
826 Segment* latest_sg;
827
828 tl_assert(sg);
829 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
830 && tid != DRD_INVALID_THREADID);
831 latest_sg = DRD_(g_threadinfo)[tid].sg_last;
832 tl_assert(latest_sg);
833
834 DRD_(sg_put)(*sg);
835 *sg = DRD_(sg_get)(latest_sg);
836 }
837
838 /**
839 * Compute the minimum of all latest vector clocks of all threads
840 * (Michiel Ronsse calls this "clock snooping" in his papers about DIOTA).
841 *
842 * @param vc pointer to a vectorclock, holds result upon return.
843 */
DRD_(thread_compute_minimum_vc)844 static void DRD_(thread_compute_minimum_vc)(VectorClock* vc)
845 {
846 unsigned i;
847 Bool first;
848 Segment* latest_sg;
849
850 first = True;
851 for (i = 0; i < DRD_N_THREADS; i++)
852 {
853 latest_sg = DRD_(g_threadinfo)[i].sg_last;
854 if (latest_sg) {
855 if (first)
856 DRD_(vc_assign)(vc, &latest_sg->vc);
857 else
858 DRD_(vc_min)(vc, &latest_sg->vc);
859 first = False;
860 }
861 }
862 }
863
864 /**
865 * Compute the maximum of all latest vector clocks of all threads.
866 *
867 * @param vc pointer to a vectorclock, holds result upon return.
868 */
DRD_(thread_compute_maximum_vc)869 static void DRD_(thread_compute_maximum_vc)(VectorClock* vc)
870 {
871 unsigned i;
872 Bool first;
873 Segment* latest_sg;
874
875 first = True;
876 for (i = 0; i < DRD_N_THREADS; i++)
877 {
878 latest_sg = DRD_(g_threadinfo)[i].sg_last;
879 if (latest_sg) {
880 if (first)
881 DRD_(vc_assign)(vc, &latest_sg->vc);
882 else
883 DRD_(vc_combine)(vc, &latest_sg->vc);
884 first = False;
885 }
886 }
887 }
888
889 /**
890 * Discard all segments that have a defined order against the latest vector
891 * clock of all threads -- these segments can no longer be involved in a
892 * data race.
893 */
thread_discard_ordered_segments(void)894 static void thread_discard_ordered_segments(void)
895 {
896 unsigned i;
897 VectorClock thread_vc_min;
898
899 s_discard_ordered_segments_count++;
900
901 DRD_(vc_init)(&thread_vc_min, 0, 0);
902 DRD_(thread_compute_minimum_vc)(&thread_vc_min);
903 if (DRD_(sg_get_trace)())
904 {
905 HChar *vc_min, *vc_max;
906 VectorClock thread_vc_max;
907
908 DRD_(vc_init)(&thread_vc_max, 0, 0);
909 DRD_(thread_compute_maximum_vc)(&thread_vc_max);
910 vc_min = DRD_(vc_aprint)(&thread_vc_min);
911 vc_max = DRD_(vc_aprint)(&thread_vc_max);
912 VG_(message)(Vg_DebugMsg,
913 "Discarding ordered segments -- min vc is %s, max vc is %s\n",
914 vc_min, vc_max);
915 VG_(free)(vc_min);
916 VG_(free)(vc_max);
917 DRD_(vc_cleanup)(&thread_vc_max);
918 }
919
920 for (i = 0; i < DRD_N_THREADS; i++) {
921 Segment* sg;
922 Segment* sg_next;
923
924 for (sg = DRD_(g_threadinfo)[i].sg_first;
925 sg && (sg_next = sg->thr_next)
926 && DRD_(vc_lte)(&sg->vc, &thread_vc_min);
927 sg = sg_next)
928 {
929 thread_discard_segment(i, sg);
930 }
931 }
932 DRD_(vc_cleanup)(&thread_vc_min);
933 }
934
935 /**
936 * An implementation of the property 'equiv(sg1, sg2)' as defined in the paper
937 * by Mark Christiaens e.a. The property equiv(sg1, sg2) holds if and only if
938 * all segments in the set CS are ordered consistently against both sg1 and
939 * sg2. The set CS is defined as the set of segments that can immediately
940 * precede future segments via inter-thread synchronization operations. In
941 * DRD the set CS consists of the latest segment of each thread combined with
942 * all segments for which the reference count is strictly greater than one.
943 * The code below is an optimized version of the following:
944 *
945 * for (i = 0; i < DRD_N_THREADS; i++)
946 * {
947 * Segment* sg;
948 *
949 * for (sg = DRD_(g_threadinfo)[i].first; sg; sg = sg->next)
950 * {
951 * if (sg == DRD_(g_threadinfo)[i].last || DRD_(sg_get_refcnt)(sg) > 1)
952 * {
953 * if ( DRD_(vc_lte)(&sg1->vc, &sg->vc)
954 * != DRD_(vc_lte)(&sg2->vc, &sg->vc)
955 * || DRD_(vc_lte)(&sg->vc, &sg1->vc)
956 * != DRD_(vc_lte)(&sg->vc, &sg2->vc))
957 * {
958 * return False;
959 * }
960 * }
961 * }
962 * }
963 */
thread_consistent_segment_ordering(const DrdThreadId tid,Segment * const sg1,Segment * const sg2)964 static Bool thread_consistent_segment_ordering(const DrdThreadId tid,
965 Segment* const sg1,
966 Segment* const sg2)
967 {
968 unsigned i;
969
970 tl_assert(sg1->thr_next);
971 tl_assert(sg2->thr_next);
972 tl_assert(sg1->thr_next == sg2);
973 tl_assert(DRD_(vc_lte)(&sg1->vc, &sg2->vc));
974
975 for (i = 0; i < DRD_N_THREADS; i++)
976 {
977 Segment* sg;
978
979 for (sg = DRD_(g_threadinfo)[i].sg_first; sg; sg = sg->thr_next) {
980 if (!sg->thr_next || DRD_(sg_get_refcnt)(sg) > 1) {
981 if (DRD_(vc_lte)(&sg2->vc, &sg->vc))
982 break;
983 if (DRD_(vc_lte)(&sg1->vc, &sg->vc))
984 return False;
985 }
986 }
987 for (sg = DRD_(g_threadinfo)[i].sg_last; sg; sg = sg->thr_prev) {
988 if (!sg->thr_next || DRD_(sg_get_refcnt)(sg) > 1) {
989 if (DRD_(vc_lte)(&sg->vc, &sg1->vc))
990 break;
991 if (DRD_(vc_lte)(&sg->vc, &sg2->vc))
992 return False;
993 }
994 }
995 }
996 return True;
997 }
998
999 /**
1000 * Merge all segments that may be merged without triggering false positives
1001 * or discarding real data races. For the theoretical background of segment
1002 * merging, see also the following paper: Mark Christiaens, Michiel Ronsse
1003 * and Koen De Bosschere. Bounding the number of segment histories during
1004 * data race detection. Parallel Computing archive, Volume 28, Issue 9,
1005 * pp 1221-1238, September 2002. This paper contains a proof that merging
1006 * consecutive segments for which the property equiv(s1,s2) holds can be
1007 * merged without reducing the accuracy of datarace detection. Furthermore
1008 * it is also proven that the total number of all segments will never grow
1009 * unbounded if all segments s1, s2 for which equiv(s1, s2) holds are merged
1010 * every time a new segment is created. The property equiv(s1, s2) is defined
1011 * as follows: equiv(s1, s2) <=> for all segments in the set CS, the vector
1012 * clocks of segments s and s1 are ordered in the same way as those of segments
1013 * s and s2. The set CS is defined as the set of existing segments s that have
1014 * the potential to conflict with not yet created segments, either because the
1015 * segment s is the latest segment of a thread or because it can become the
1016 * immediate predecessor of a new segment due to a synchronization operation.
1017 */
thread_merge_segments(void)1018 static void thread_merge_segments(void)
1019 {
1020 unsigned i;
1021
1022 s_new_segments_since_last_merge = 0;
1023
1024 for (i = 0; i < DRD_N_THREADS; i++)
1025 {
1026 Segment* sg;
1027
1028 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
1029 tl_assert(DRD_(sane_ThreadInfo)(&DRD_(g_threadinfo)[i]));
1030 #endif
1031
1032 for (sg = DRD_(g_threadinfo)[i].sg_first; sg; sg = sg->thr_next) {
1033 if (DRD_(sg_get_refcnt)(sg) == 1 && sg->thr_next) {
1034 Segment* const sg_next = sg->thr_next;
1035 if (DRD_(sg_get_refcnt)(sg_next) == 1
1036 && sg_next->thr_next
1037 && thread_consistent_segment_ordering(i, sg, sg_next))
1038 {
1039 /* Merge sg and sg_next into sg. */
1040 DRD_(sg_merge)(sg, sg_next);
1041 thread_discard_segment(i, sg_next);
1042 }
1043 }
1044 }
1045
1046 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
1047 tl_assert(DRD_(sane_ThreadInfo)(&DRD_(g_threadinfo)[i]));
1048 #endif
1049 }
1050 }
1051
1052 /**
1053 * Create a new segment for the specified thread, and discard any segments
1054 * that cannot cause races anymore.
1055 */
DRD_(thread_new_segment)1056 void DRD_(thread_new_segment)(const DrdThreadId tid)
1057 {
1058 Segment* last_sg;
1059 Segment* new_sg;
1060
1061 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1062 && tid != DRD_INVALID_THREADID);
1063 tl_assert(thread_conflict_set_up_to_date(DRD_(g_drd_running_tid)));
1064
1065 last_sg = DRD_(g_threadinfo)[tid].sg_last;
1066 new_sg = DRD_(sg_new)(tid, tid);
1067 thread_append_segment(tid, new_sg);
1068 if (tid == DRD_(g_drd_running_tid) && last_sg)
1069 {
1070 DRD_(thread_update_conflict_set)(tid, &last_sg->vc);
1071 s_update_conflict_set_new_sg_count++;
1072 }
1073
1074 tl_assert(thread_conflict_set_up_to_date(DRD_(g_drd_running_tid)));
1075
1076 if (s_segment_merging
1077 && ++s_new_segments_since_last_merge >= s_segment_merge_interval)
1078 {
1079 thread_discard_ordered_segments();
1080 thread_merge_segments();
1081 }
1082 }
1083
1084 /** Call this function after thread 'joiner' joined thread 'joinee'. */
DRD_(thread_combine_vc_join)1085 void DRD_(thread_combine_vc_join)(DrdThreadId joiner, DrdThreadId joinee)
1086 {
1087 tl_assert(joiner != joinee);
1088 tl_assert(0 <= (int)joiner && joiner < DRD_N_THREADS
1089 && joiner != DRD_INVALID_THREADID);
1090 tl_assert(0 <= (int)joinee && joinee < DRD_N_THREADS
1091 && joinee != DRD_INVALID_THREADID);
1092 tl_assert(DRD_(g_threadinfo)[joiner].sg_first);
1093 tl_assert(DRD_(g_threadinfo)[joiner].sg_last);
1094 tl_assert(DRD_(g_threadinfo)[joinee].sg_first);
1095 tl_assert(DRD_(g_threadinfo)[joinee].sg_last);
1096
1097 if (DRD_(sg_get_trace)())
1098 {
1099 HChar *str1, *str2;
1100 str1 = DRD_(vc_aprint)(DRD_(thread_get_vc)(joiner));
1101 str2 = DRD_(vc_aprint)(DRD_(thread_get_vc)(joinee));
1102 VG_(message)(Vg_DebugMsg, "Before join: joiner %s, joinee %s\n",
1103 str1, str2);
1104 VG_(free)(str1);
1105 VG_(free)(str2);
1106 }
1107 if (joiner == DRD_(g_drd_running_tid)) {
1108 VectorClock old_vc;
1109
1110 DRD_(vc_copy)(&old_vc, DRD_(thread_get_vc)(joiner));
1111 DRD_(vc_combine)(DRD_(thread_get_vc)(joiner),
1112 DRD_(thread_get_vc)(joinee));
1113 DRD_(thread_update_conflict_set)(joiner, &old_vc);
1114 s_update_conflict_set_join_count++;
1115 DRD_(vc_cleanup)(&old_vc);
1116 } else {
1117 DRD_(vc_combine)(DRD_(thread_get_vc)(joiner),
1118 DRD_(thread_get_vc)(joinee));
1119 }
1120
1121 thread_discard_ordered_segments();
1122
1123 if (DRD_(sg_get_trace)()) {
1124 HChar* str;
1125
1126 str = DRD_(vc_aprint)(DRD_(thread_get_vc)(joiner));
1127 VG_(message)(Vg_DebugMsg, "After join: %s\n", str);
1128 VG_(free)(str);
1129 }
1130 }
1131
1132 /**
1133 * Update the vector clock of the last segment of thread tid with the
1134 * the vector clock of segment sg.
1135 */
thread_combine_vc_sync(DrdThreadId tid,const Segment * sg)1136 static void thread_combine_vc_sync(DrdThreadId tid, const Segment* sg)
1137 {
1138 const VectorClock* const vc = &sg->vc;
1139
1140 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1141 && tid != DRD_INVALID_THREADID);
1142 tl_assert(DRD_(g_threadinfo)[tid].sg_first);
1143 tl_assert(DRD_(g_threadinfo)[tid].sg_last);
1144 tl_assert(sg);
1145 tl_assert(vc);
1146
1147 if (tid != sg->tid) {
1148 VectorClock old_vc;
1149
1150 DRD_(vc_copy)(&old_vc, DRD_(thread_get_vc)(tid));
1151 DRD_(vc_combine)(DRD_(thread_get_vc)(tid), vc);
1152 if (DRD_(sg_get_trace)()) {
1153 HChar *str1, *str2;
1154 str1 = DRD_(vc_aprint)(&old_vc);
1155 str2 = DRD_(vc_aprint)(DRD_(thread_get_vc)(tid));
1156 VG_(message)(Vg_DebugMsg, "thread %d: vc %s -> %s\n", tid, str1, str2);
1157 VG_(free)(str1);
1158 VG_(free)(str2);
1159 }
1160
1161 thread_discard_ordered_segments();
1162
1163 DRD_(thread_update_conflict_set)(tid, &old_vc);
1164 s_update_conflict_set_sync_count++;
1165
1166 DRD_(vc_cleanup)(&old_vc);
1167 } else {
1168 tl_assert(DRD_(vc_lte)(vc, DRD_(thread_get_vc)(tid)));
1169 }
1170 }
1171
1172 /**
1173 * Create a new segment for thread tid and update the vector clock of the last
1174 * segment of this thread with the the vector clock of segment sg. Call this
1175 * function after thread tid had to wait because of thread synchronization
1176 * until the memory accesses in the segment sg finished.
1177 */
DRD_(thread_new_segment_and_combine_vc)1178 void DRD_(thread_new_segment_and_combine_vc)(DrdThreadId tid, const Segment* sg)
1179 {
1180 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1181 && tid != DRD_INVALID_THREADID);
1182 tl_assert(thread_conflict_set_up_to_date(DRD_(g_drd_running_tid)));
1183 tl_assert(sg);
1184
1185 thread_append_segment(tid, DRD_(sg_new)(tid, tid));
1186
1187 thread_combine_vc_sync(tid, sg);
1188
1189 if (s_segment_merging
1190 && ++s_new_segments_since_last_merge >= s_segment_merge_interval)
1191 {
1192 thread_discard_ordered_segments();
1193 thread_merge_segments();
1194 }
1195 }
1196
1197 /**
1198 * Call this function whenever a thread is no longer using the memory
1199 * [ a1, a2 [, e.g. because of a call to free() or a stack pointer
1200 * increase.
1201 */
DRD_(thread_stop_using_mem)1202 void DRD_(thread_stop_using_mem)(const Addr a1, const Addr a2)
1203 {
1204 Segment* p;
1205
1206 for (p = DRD_(g_sg_list); p; p = p->g_next)
1207 DRD_(bm_clear)(DRD_(sg_bm)(p), a1, a2);
1208
1209 DRD_(bm_clear)(DRD_(g_conflict_set), a1, a2);
1210 }
1211
1212 /** Specify whether memory loads should be recorded. */
DRD_(thread_set_record_loads)1213 void DRD_(thread_set_record_loads)(const DrdThreadId tid, const Bool enabled)
1214 {
1215 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1216 && tid != DRD_INVALID_THREADID);
1217 tl_assert(enabled == !! enabled);
1218
1219 DRD_(g_threadinfo)[tid].is_recording_loads = enabled;
1220 }
1221
1222 /** Specify whether memory stores should be recorded. */
DRD_(thread_set_record_stores)1223 void DRD_(thread_set_record_stores)(const DrdThreadId tid, const Bool enabled)
1224 {
1225 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1226 && tid != DRD_INVALID_THREADID);
1227 tl_assert(enabled == !! enabled);
1228
1229 DRD_(g_threadinfo)[tid].is_recording_stores = enabled;
1230 }
1231
1232 /**
1233 * Print the segment information for all threads.
1234 *
1235 * This function is only used for debugging purposes.
1236 */
DRD_(thread_print_all)1237 void DRD_(thread_print_all)(void)
1238 {
1239 unsigned i;
1240 Segment* p;
1241
1242 for (i = 0; i < DRD_N_THREADS; i++)
1243 {
1244 p = DRD_(g_threadinfo)[i].sg_first;
1245 if (p) {
1246 VG_(printf)("**************\n"
1247 "* thread %3d (%d/%d/%d/%d/0x%lx/%d) *\n"
1248 "**************\n",
1249 i,
1250 DRD_(g_threadinfo)[i].valid,
1251 DRD_(g_threadinfo)[i].vg_thread_exists,
1252 DRD_(g_threadinfo)[i].vg_threadid,
1253 DRD_(g_threadinfo)[i].posix_thread_exists,
1254 DRD_(g_threadinfo)[i].pt_threadid,
1255 DRD_(g_threadinfo)[i].detached_posix_thread);
1256 for ( ; p; p = p->thr_next)
1257 DRD_(sg_print)(p);
1258 }
1259 }
1260 }
1261
1262 /** Show a call stack involved in a data race. */
show_call_stack(const DrdThreadId tid,ExeContext * const callstack)1263 static void show_call_stack(const DrdThreadId tid, ExeContext* const callstack)
1264 {
1265 const ThreadId vg_tid = DRD_(DrdThreadIdToVgThreadId)(tid);
1266
1267 if (vg_tid != VG_INVALID_THREADID) {
1268 if (callstack)
1269 VG_(pp_ExeContext)(callstack);
1270 else
1271 VG_(get_and_pp_StackTrace)(vg_tid, VG_(clo_backtrace_size));
1272 } else {
1273 if (!VG_(clo_xml))
1274 VG_(message)(Vg_UserMsg,
1275 " (thread finished, call stack no longer available)\n");
1276 }
1277 }
1278
1279 /** Print information about the segments involved in a data race. */
1280 static void
thread_report_conflicting_segments_segment(const DrdThreadId tid,const Addr addr,const SizeT size,const BmAccessTypeT access_type,const Segment * const p)1281 thread_report_conflicting_segments_segment(const DrdThreadId tid,
1282 const Addr addr,
1283 const SizeT size,
1284 const BmAccessTypeT access_type,
1285 const Segment* const p)
1286 {
1287 unsigned i;
1288
1289 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1290 && tid != DRD_INVALID_THREADID);
1291 tl_assert(p);
1292
1293 for (i = 0; i < DRD_N_THREADS; i++) {
1294 if (i != tid) {
1295 Segment* q;
1296
1297 for (q = DRD_(g_threadinfo)[i].sg_last; q; q = q->thr_prev) {
1298 /*
1299 * Since q iterates over the segments of thread i in order of
1300 * decreasing vector clocks, if q->vc <= p->vc, then
1301 * q->next->vc <= p->vc will also hold. Hence, break out of the
1302 * loop once this condition is met.
1303 */
1304 if (DRD_(vc_lte)(&q->vc, &p->vc))
1305 break;
1306 if (!DRD_(vc_lte)(&p->vc, &q->vc)) {
1307 if (DRD_(bm_has_conflict_with)(DRD_(sg_bm)(q), addr, addr + size,
1308 access_type)) {
1309 Segment* q_next;
1310
1311 tl_assert(q->stacktrace);
1312 if (VG_(clo_xml))
1313 VG_(printf_xml)(" <other_segment_start>\n");
1314 else
1315 VG_(message)(Vg_UserMsg,
1316 "Other segment start (thread %d)\n", i);
1317 show_call_stack(i, q->stacktrace);
1318 if (VG_(clo_xml))
1319 VG_(printf_xml)(" </other_segment_start>\n"
1320 " <other_segment_end>\n");
1321 else
1322 VG_(message)(Vg_UserMsg,
1323 "Other segment end (thread %d)\n", i);
1324 q_next = q->thr_next;
1325 show_call_stack(i, q_next ? q_next->stacktrace : 0);
1326 if (VG_(clo_xml))
1327 VG_(printf_xml)(" </other_segment_end>\n");
1328 }
1329 }
1330 }
1331 }
1332 }
1333 }
1334
1335 /** Print information about all segments involved in a data race. */
DRD_(thread_report_conflicting_segments)1336 void DRD_(thread_report_conflicting_segments)(const DrdThreadId tid,
1337 const Addr addr,
1338 const SizeT size,
1339 const BmAccessTypeT access_type)
1340 {
1341 Segment* p;
1342
1343 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1344 && tid != DRD_INVALID_THREADID);
1345
1346 for (p = DRD_(g_threadinfo)[tid].sg_first; p; p = p->thr_next) {
1347 if (DRD_(bm_has)(DRD_(sg_bm)(p), addr, addr + size, access_type))
1348 thread_report_conflicting_segments_segment(tid, addr, size,
1349 access_type, p);
1350 }
1351 }
1352
1353 /**
1354 * Verify whether the conflict set for thread tid is up to date. Only perform
1355 * the check if the environment variable DRD_VERIFY_CONFLICT_SET has been set.
1356 */
thread_conflict_set_up_to_date(const DrdThreadId tid)1357 static Bool thread_conflict_set_up_to_date(const DrdThreadId tid)
1358 {
1359 Bool result;
1360 struct bitmap* computed_conflict_set = 0;
1361
1362 if (!DRD_(verify_conflict_set))
1363 return True;
1364
1365 thread_compute_conflict_set(&computed_conflict_set, tid);
1366 result = DRD_(bm_equal)(DRD_(g_conflict_set), computed_conflict_set);
1367 if (! result)
1368 {
1369 VG_(printf)("actual conflict set:\n");
1370 DRD_(bm_print)(DRD_(g_conflict_set));
1371 VG_(printf)("\n");
1372 VG_(printf)("computed conflict set:\n");
1373 DRD_(bm_print)(computed_conflict_set);
1374 VG_(printf)("\n");
1375 }
1376 DRD_(bm_delete)(computed_conflict_set);
1377 return result;
1378 }
1379
1380 /**
1381 * Compute the conflict set: a bitmap that represents the union of all memory
1382 * accesses of all segments that are unordered to the current segment of the
1383 * thread tid.
1384 */
thread_compute_conflict_set(struct bitmap ** conflict_set,const DrdThreadId tid)1385 static void thread_compute_conflict_set(struct bitmap** conflict_set,
1386 const DrdThreadId tid)
1387 {
1388 Segment* p;
1389
1390 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1391 && tid != DRD_INVALID_THREADID);
1392 tl_assert(tid == DRD_(g_drd_running_tid));
1393
1394 s_compute_conflict_set_count++;
1395 s_conflict_set_bitmap_creation_count
1396 -= DRD_(bm_get_bitmap_creation_count)();
1397 s_conflict_set_bitmap2_creation_count
1398 -= DRD_(bm_get_bitmap2_creation_count)();
1399
1400 if (*conflict_set) {
1401 DRD_(bm_cleanup)(*conflict_set);
1402 DRD_(bm_init)(*conflict_set);
1403 } else {
1404 *conflict_set = DRD_(bm_new)();
1405 }
1406
1407 if (s_trace_conflict_set) {
1408 HChar* str;
1409
1410 str = DRD_(vc_aprint)(DRD_(thread_get_vc)(tid));
1411 VG_(message)(Vg_DebugMsg,
1412 "computing conflict set for thread %d with vc %s\n",
1413 tid, str);
1414 VG_(free)(str);
1415 }
1416
1417 p = DRD_(g_threadinfo)[tid].sg_last;
1418 {
1419 unsigned j;
1420
1421 if (s_trace_conflict_set) {
1422 HChar* vc;
1423
1424 vc = DRD_(vc_aprint)(&p->vc);
1425 VG_(message)(Vg_DebugMsg, "conflict set: thread [%d] at vc %s\n",
1426 tid, vc);
1427 VG_(free)(vc);
1428 }
1429
1430 for (j = 0; j < DRD_N_THREADS; j++) {
1431 if (j != tid && DRD_(IsValidDrdThreadId)(j)) {
1432 Segment* q;
1433
1434 for (q = DRD_(g_threadinfo)[j].sg_last; q; q = q->thr_prev) {
1435 if (!DRD_(vc_lte)(&q->vc, &p->vc)
1436 && !DRD_(vc_lte)(&p->vc, &q->vc)) {
1437 if (s_trace_conflict_set) {
1438 HChar* str;
1439
1440 str = DRD_(vc_aprint)(&q->vc);
1441 VG_(message)(Vg_DebugMsg,
1442 "conflict set: [%d] merging segment %s\n",
1443 j, str);
1444 VG_(free)(str);
1445 }
1446 DRD_(bm_merge2)(*conflict_set, DRD_(sg_bm)(q));
1447 } else {
1448 if (s_trace_conflict_set) {
1449 HChar* str;
1450
1451 str = DRD_(vc_aprint)(&q->vc);
1452 VG_(message)(Vg_DebugMsg,
1453 "conflict set: [%d] ignoring segment %s\n",
1454 j, str);
1455 VG_(free)(str);
1456 }
1457 }
1458 }
1459 }
1460 }
1461 }
1462
1463 s_conflict_set_bitmap_creation_count
1464 += DRD_(bm_get_bitmap_creation_count)();
1465 s_conflict_set_bitmap2_creation_count
1466 += DRD_(bm_get_bitmap2_creation_count)();
1467
1468 if (s_trace_conflict_set_bm) {
1469 VG_(message)(Vg_DebugMsg, "[%d] new conflict set:\n", tid);
1470 DRD_(bm_print)(*conflict_set);
1471 VG_(message)(Vg_DebugMsg, "[%d] end of new conflict set.\n", tid);
1472 }
1473 }
1474
1475 /**
1476 * Update the conflict set after the vector clock of thread tid has been
1477 * updated from old_vc to its current value, either because a new segment has
1478 * been created or because of a synchronization operation.
1479 */
DRD_(thread_update_conflict_set)1480 void DRD_(thread_update_conflict_set)(const DrdThreadId tid,
1481 const VectorClock* const old_vc)
1482 {
1483 const VectorClock* new_vc;
1484 Segment* p;
1485 unsigned j;
1486
1487 tl_assert(0 <= (int)tid && tid < DRD_N_THREADS
1488 && tid != DRD_INVALID_THREADID);
1489 tl_assert(old_vc);
1490 tl_assert(tid == DRD_(g_drd_running_tid));
1491 tl_assert(DRD_(g_conflict_set));
1492
1493 if (s_trace_conflict_set) {
1494 HChar* str;
1495
1496 str = DRD_(vc_aprint)(DRD_(thread_get_vc)(tid));
1497 VG_(message)(Vg_DebugMsg,
1498 "updating conflict set for thread %d with vc %s\n",
1499 tid, str);
1500 VG_(free)(str);
1501 }
1502
1503 new_vc = DRD_(thread_get_vc)(tid);
1504 tl_assert(DRD_(vc_lte)(old_vc, new_vc));
1505
1506 DRD_(bm_unmark)(DRD_(g_conflict_set));
1507
1508 for (j = 0; j < DRD_N_THREADS; j++)
1509 {
1510 Segment* q;
1511
1512 if (j == tid || ! DRD_(IsValidDrdThreadId)(j))
1513 continue;
1514
1515 for (q = DRD_(g_threadinfo)[j].sg_last;
1516 q && !DRD_(vc_lte)(&q->vc, new_vc);
1517 q = q->thr_prev) {
1518 const Bool included_in_old_conflict_set
1519 = !DRD_(vc_lte)(old_vc, &q->vc);
1520 const Bool included_in_new_conflict_set
1521 = !DRD_(vc_lte)(new_vc, &q->vc);
1522
1523 if (UNLIKELY(s_trace_conflict_set)) {
1524 HChar* str;
1525
1526 str = DRD_(vc_aprint)(&q->vc);
1527 VG_(message)(Vg_DebugMsg,
1528 "conflict set: [%d] %s segment %s\n", j,
1529 included_in_old_conflict_set
1530 != included_in_new_conflict_set
1531 ? "merging" : "ignoring", str);
1532 VG_(free)(str);
1533 }
1534 if (included_in_old_conflict_set != included_in_new_conflict_set)
1535 DRD_(bm_mark)(DRD_(g_conflict_set), DRD_(sg_bm)(q));
1536 }
1537
1538 for ( ; q && !DRD_(vc_lte)(&q->vc, old_vc); q = q->thr_prev) {
1539 const Bool included_in_old_conflict_set
1540 = !DRD_(vc_lte)(old_vc, &q->vc);
1541 const Bool included_in_new_conflict_set
1542 = !DRD_(vc_lte)(&q->vc, new_vc)
1543 && !DRD_(vc_lte)(new_vc, &q->vc);
1544
1545 if (UNLIKELY(s_trace_conflict_set)) {
1546 HChar* str;
1547
1548 str = DRD_(vc_aprint)(&q->vc);
1549 VG_(message)(Vg_DebugMsg,
1550 "conflict set: [%d] %s segment %s\n", j,
1551 included_in_old_conflict_set
1552 != included_in_new_conflict_set
1553 ? "merging" : "ignoring", str);
1554 VG_(free)(str);
1555 }
1556 if (included_in_old_conflict_set != included_in_new_conflict_set)
1557 DRD_(bm_mark)(DRD_(g_conflict_set), DRD_(sg_bm)(q));
1558 }
1559 }
1560
1561 DRD_(bm_clear_marked)(DRD_(g_conflict_set));
1562
1563 p = DRD_(g_threadinfo)[tid].sg_last;
1564 for (j = 0; j < DRD_N_THREADS; j++) {
1565 if (j != tid && DRD_(IsValidDrdThreadId)(j)) {
1566 Segment* q;
1567 for (q = DRD_(g_threadinfo)[j].sg_last;
1568 q && !DRD_(vc_lte)(&q->vc, &p->vc);
1569 q = q->thr_prev) {
1570 if (!DRD_(vc_lte)(&p->vc, &q->vc))
1571 DRD_(bm_merge2_marked)(DRD_(g_conflict_set), DRD_(sg_bm)(q));
1572 }
1573 }
1574 }
1575
1576 DRD_(bm_remove_cleared_marked)(DRD_(g_conflict_set));
1577
1578 s_update_conflict_set_count++;
1579
1580 if (s_trace_conflict_set_bm)
1581 {
1582 VG_(message)(Vg_DebugMsg, "[%d] updated conflict set:\n", tid);
1583 DRD_(bm_print)(DRD_(g_conflict_set));
1584 VG_(message)(Vg_DebugMsg, "[%d] end of updated conflict set.\n", tid);
1585 }
1586
1587 tl_assert(thread_conflict_set_up_to_date(DRD_(g_drd_running_tid)));
1588 }
1589
1590 /** Report the number of context switches performed. */
DRD_(thread_get_context_switch_count)1591 ULong DRD_(thread_get_context_switch_count)(void)
1592 {
1593 return s_context_switch_count;
1594 }
1595
1596 /** Report the number of ordered segments that have been discarded. */
DRD_(thread_get_discard_ordered_segments_count)1597 ULong DRD_(thread_get_discard_ordered_segments_count)(void)
1598 {
1599 return s_discard_ordered_segments_count;
1600 }
1601
1602 /** Return how many times the conflict set has been updated entirely. */
DRD_(thread_get_compute_conflict_set_count)1603 ULong DRD_(thread_get_compute_conflict_set_count)()
1604 {
1605 return s_compute_conflict_set_count;
1606 }
1607
1608 /** Return how many times the conflict set has been updated partially. */
DRD_(thread_get_update_conflict_set_count)1609 ULong DRD_(thread_get_update_conflict_set_count)(void)
1610 {
1611 return s_update_conflict_set_count;
1612 }
1613
1614 /**
1615 * Return how many times the conflict set has been updated partially
1616 * because a new segment has been created.
1617 */
DRD_(thread_get_update_conflict_set_new_sg_count)1618 ULong DRD_(thread_get_update_conflict_set_new_sg_count)(void)
1619 {
1620 return s_update_conflict_set_new_sg_count;
1621 }
1622
1623 /**
1624 * Return how many times the conflict set has been updated partially
1625 * because of combining vector clocks due to synchronization operations
1626 * other than reader/writer lock or barrier operations.
1627 */
DRD_(thread_get_update_conflict_set_sync_count)1628 ULong DRD_(thread_get_update_conflict_set_sync_count)(void)
1629 {
1630 return s_update_conflict_set_sync_count;
1631 }
1632
1633 /**
1634 * Return how many times the conflict set has been updated partially
1635 * because of thread joins.
1636 */
DRD_(thread_get_update_conflict_set_join_count)1637 ULong DRD_(thread_get_update_conflict_set_join_count)(void)
1638 {
1639 return s_update_conflict_set_join_count;
1640 }
1641
1642 /**
1643 * Return the number of first-level bitmaps that have been created during
1644 * conflict set updates.
1645 */
DRD_(thread_get_conflict_set_bitmap_creation_count)1646 ULong DRD_(thread_get_conflict_set_bitmap_creation_count)(void)
1647 {
1648 return s_conflict_set_bitmap_creation_count;
1649 }
1650
1651 /**
1652 * Return the number of second-level bitmaps that have been created during
1653 * conflict set updates.
1654 */
DRD_(thread_get_conflict_set_bitmap2_creation_count)1655 ULong DRD_(thread_get_conflict_set_bitmap2_creation_count)(void)
1656 {
1657 return s_conflict_set_bitmap2_creation_count;
1658 }
1659