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