1/* 2 This file is part of drd, a thread error detector. 3 4 Copyright (C) 2006-2015 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_basics.h" /* DRD_() */ 26#include "drd_bitmap.h" 27#include "drd_error.h" 28#include "drd_suppression.h" 29#include "pub_drd_bitmap.h" 30#include "pub_tool_basics.h" /* Addr, SizeT */ 31#include "pub_tool_libcassert.h" /* tl_assert() */ 32#include "pub_tool_libcbase.h" /* VG_(memset) */ 33#include "pub_tool_libcprint.h" /* VG_(printf) */ 34#include "pub_tool_mallocfree.h" /* VG_(malloc), VG_(free) */ 35 36 37/* Local function declarations. */ 38 39static void bm2_merge(struct bitmap2* const bm2l, 40 const struct bitmap2* const bm2r); 41static void bm2_print(const struct bitmap2* const bm2); 42 43 44/* Local variables. */ 45 46static OSet* s_bm2_set_template; 47static ULong s_bitmap_creation_count; 48static ULong s_bitmap_merge_count; 49static ULong s_bitmap2_merge_count; 50 51 52/* Function definitions. */ 53 54void DRD_(bm_module_init)(void) 55{ 56 tl_assert(!s_bm2_set_template); 57 s_bm2_set_template 58 = VG_(OSetGen_Create_With_Pool)(0, 0, VG_(malloc), "drd.bitmap.bn.2", 59 VG_(free), 512, sizeof(struct bitmap2)); 60} 61 62void DRD_(bm_module_cleanup)(void) 63{ 64 tl_assert(s_bm2_set_template); 65 VG_(OSetGen_Destroy)(s_bm2_set_template); 66 s_bm2_set_template = NULL; 67} 68 69struct bitmap* DRD_(bm_new)() 70{ 71 struct bitmap* bm; 72 73 /* If this assert fails, fix the definition of BITS_PER_BITS_PER_UWORD */ 74 /* in drd_bitmap.h. */ 75 tl_assert((1 << BITS_PER_BITS_PER_UWORD) == BITS_PER_UWORD); 76 77 bm = VG_(malloc)("drd.bitmap.bn.1", sizeof(*bm)); 78 DRD_(bm_init)(bm); 79 80 return bm; 81} 82 83void DRD_(bm_delete)(struct bitmap* const bm) 84{ 85 tl_assert(bm); 86 87 DRD_(bm_cleanup)(bm); 88 VG_(free)(bm); 89} 90 91/** Initialize *bm. */ 92void DRD_(bm_init)(struct bitmap* const bm) 93{ 94 unsigned i; 95 96 tl_assert(bm); 97 /* 98 * Cache initialization. a1 is initialized with a value that never can 99 * match any valid address: the upper (ADDR_LSB_BITS + ADDR_IGNORED_BITS) 100 * bits of a1 are always zero for a valid cache entry. 101 */ 102 for (i = 0; i < DRD_BITMAP_N_CACHE_ELEM; i++) 103 { 104 bm->cache[i].a1 = ~(UWord)1; 105 bm->cache[i].bm2 = 0; 106 } 107 bm->oset = VG_(OSetGen_EmptyClone)(s_bm2_set_template); 108 109 s_bitmap_creation_count++; 110} 111 112/** Free the memory allocated by DRD_(bm_init)(). */ 113void DRD_(bm_cleanup)(struct bitmap* const bm) 114{ 115 VG_(OSetGen_Destroy)(bm->oset); 116} 117 118/** 119 * Record an access of type access_type at addresses a .. a + size - 1 in 120 * bitmap bm. 121 * 122 * @note The current implementation of bm_access_range does not work for the 123 * highest addresses in the address range. At least on Linux this is 124 * not a problem since the upper part of the address space is reserved 125 * for the kernel. 126 */ 127void DRD_(bm_access_range)(struct bitmap* const bm, 128 const Addr a1, const Addr a2, 129 const BmAccessTypeT access_type) 130{ 131 tl_assert(access_type == eLoad || access_type == eStore); 132 133 if (access_type == eLoad) 134 return DRD_(bm_access_range_load)(bm, a1, a2); 135 else 136 return DRD_(bm_access_range_store)(bm, a1, a2); 137} 138 139void DRD_(bm_access_range_load)(struct bitmap* const bm, Addr a1, Addr a2) 140{ 141 Addr b, b_next; 142 143 tl_assert(bm); 144 tl_assert(a1 <= a2); 145 tl_assert(a2 < first_address_with_higher_msb(a2)); 146 tl_assert(a1 == first_address_with_same_lsb(a1)); 147 tl_assert(a2 == first_address_with_same_lsb(a2)); 148 149 for (b = a1; b < a2; b = b_next) 150 { 151 Addr b_start; 152 Addr b_end; 153 struct bitmap2* bm2; 154 UWord b0; 155 156 b_next = first_address_with_higher_msb(b); 157 if (b_next > a2) 158 { 159 b_next = a2; 160 } 161 162 bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b)); 163 tl_assert(bm2); 164 165 if (make_address(bm2->addr, 0) < a1) 166 b_start = a1; 167 else 168 if (make_address(bm2->addr, 0) < a2) 169 b_start = make_address(bm2->addr, 0); 170 else 171 break; 172 173 if (make_address(bm2->addr + 1, 0) < a2) 174 b_end = make_address(bm2->addr + 1, 0); 175 else 176 b_end = a2; 177 178 tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2); 179 tl_assert(address_msb(b_start) == address_msb(b_end - 1)); 180 tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 181 182 if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0) 183 { 184 unsigned k; 185 186 for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 187 { 188 bm2->bm1.bm0_r[k] = ~(UWord)0; 189 } 190 } 191 else 192 { 193 for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 194 { 195 bm0_set(bm2->bm1.bm0_r, b0); 196 } 197 } 198 } 199} 200 201void DRD_(bm_access_load_1)(struct bitmap* const bm, const Addr a1) 202{ 203 bm_access_aligned_load(bm, a1, 1); 204} 205 206void DRD_(bm_access_load_2)(struct bitmap* const bm, const Addr a1) 207{ 208 if ((a1 & 1) == 0) 209 bm_access_aligned_load(bm, a1, 2); 210 else 211 DRD_(bm_access_range)(bm, a1, a1 + 2, eLoad); 212} 213 214void DRD_(bm_access_load_4)(struct bitmap* const bm, const Addr a1) 215{ 216 if ((a1 & 3) == 0) 217 bm_access_aligned_load(bm, a1, 4); 218 else 219 DRD_(bm_access_range)(bm, a1, a1 + 4, eLoad); 220} 221 222void DRD_(bm_access_load_8)(struct bitmap* const bm, const Addr a1) 223{ 224 if ((a1 & 7) == 0) 225 bm_access_aligned_load(bm, a1, 8); 226 else if ((a1 & 3) == 0) 227 { 228 bm_access_aligned_load(bm, a1 + 0, 4); 229 bm_access_aligned_load(bm, a1 + 4, 4); 230 } 231 else 232 DRD_(bm_access_range)(bm, a1, a1 + 8, eLoad); 233} 234 235void DRD_(bm_access_range_store)(struct bitmap* const bm, 236 const Addr a1, const Addr a2) 237{ 238 Addr b, b_next; 239 240 tl_assert(bm); 241 tl_assert(a1 <= a2); 242 tl_assert(a2 < first_address_with_higher_msb(a2)); 243 tl_assert(a1 == first_address_with_same_lsb(a1)); 244 tl_assert(a2 == first_address_with_same_lsb(a2)); 245 246 for (b = a1; b < a2; b = b_next) 247 { 248 Addr b_start; 249 Addr b_end; 250 struct bitmap2* bm2; 251 UWord b0; 252 253 b_next = first_address_with_higher_msb(b); 254 if (b_next > a2) 255 { 256 b_next = a2; 257 } 258 259 bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(b)); 260 tl_assert(bm2); 261 262 if (make_address(bm2->addr, 0) < a1) 263 b_start = a1; 264 else 265 if (make_address(bm2->addr, 0) < a2) 266 b_start = make_address(bm2->addr, 0); 267 else 268 break; 269 270 if (make_address(bm2->addr + 1, 0) < a2) 271 b_end = make_address(bm2->addr + 1, 0); 272 else 273 b_end = a2; 274 275 tl_assert(a1 <= b_start && b_start < b_end && b_end && b_end <= a2); 276 tl_assert(address_msb(b_start) == address_msb(b_end - 1)); 277 tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 278 279 if (address_lsb(b_start) == 0 && address_lsb(b_end) == 0) 280 { 281 unsigned k; 282 283 for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 284 { 285 bm2->bm1.bm0_w[k] = ~(UWord)0; 286 } 287 } 288 else 289 { 290 for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 291 { 292 bm0_set(bm2->bm1.bm0_w, b0); 293 } 294 } 295 } 296} 297 298void DRD_(bm_access_store_1)(struct bitmap* const bm, const Addr a1) 299{ 300 bm_access_aligned_store(bm, a1, 1); 301} 302 303void DRD_(bm_access_store_2)(struct bitmap* const bm, const Addr a1) 304{ 305 if ((a1 & 1) == 0) 306 bm_access_aligned_store(bm, a1, 2); 307 else 308 DRD_(bm_access_range)(bm, a1, a1 + 2, eStore); 309} 310 311void DRD_(bm_access_store_4)(struct bitmap* const bm, const Addr a1) 312{ 313 if ((a1 & 3) == 0) 314 bm_access_aligned_store(bm, a1, 4); 315 else 316 DRD_(bm_access_range)(bm, a1, a1 + 4, eStore); 317} 318 319void DRD_(bm_access_store_8)(struct bitmap* const bm, const Addr a1) 320{ 321 if ((a1 & 7) == 0) 322 bm_access_aligned_store(bm, a1, 8); 323 else if ((a1 & 3) == 0) 324 { 325 bm_access_aligned_store(bm, a1 + 0, 4); 326 bm_access_aligned_store(bm, a1 + 4, 4); 327 } 328 else 329 DRD_(bm_access_range)(bm, a1, a1 + 8, eStore); 330} 331 332Bool DRD_(bm_has)(struct bitmap* const bm, const Addr a1, const Addr a2, 333 const BmAccessTypeT access_type) 334{ 335 tl_assert(access_type == eLoad || access_type == eStore); 336 337 if (access_type == eLoad) 338 return DRD_(bm_has_any_load)(bm, a1, a2); 339 else 340 return DRD_(bm_has_any_store)(bm, a1, a2); 341} 342 343Bool DRD_(bm_has_any_load_g)(struct bitmap* const bm) 344{ 345 struct bitmap2* bm2; 346 347 tl_assert(bm); 348 349 VG_(OSetGen_ResetIter)(bm->oset); 350 for ( ; (bm2 = VG_(OSetGen_Next)(bm->oset)) != NULL; ) { 351 Addr b_start; 352 Addr b_end; 353 UWord b0; 354 const struct bitmap1* const p1 = &bm2->bm1; 355 356 b_start = make_address(bm2->addr, 0); 357 b_end = make_address(bm2->addr + 1, 0); 358 359 for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 360 if (bm0_is_set(p1->bm0_r, b0)) 361 return True; 362 } 363 return False; 364} 365 366Bool 367DRD_(bm_has_any_load)(struct bitmap* const bm, const Addr a1, const Addr a2) 368{ 369 Addr b, b_next; 370 371 tl_assert(bm); 372 373 for (b = a1; b < a2; b = b_next) 374 { 375 const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b)); 376 377 b_next = first_address_with_higher_msb(b); 378 if (b_next > a2) 379 { 380 b_next = a2; 381 } 382 383 if (bm2) 384 { 385 Addr b_start; 386 Addr b_end; 387 UWord b0; 388 const struct bitmap1* const p1 = &bm2->bm1; 389 390 if (make_address(bm2->addr, 0) < a1) 391 b_start = a1; 392 else 393 if (make_address(bm2->addr, 0) < a2) 394 b_start = make_address(bm2->addr, 0); 395 else 396 break; 397 tl_assert(a1 <= b_start && b_start <= a2); 398 399 if (make_address(bm2->addr + 1, 0) < a2) 400 b_end = make_address(bm2->addr + 1, 0); 401 else 402 b_end = a2; 403 tl_assert(a1 <= b_end && b_end <= a2); 404 tl_assert(b_start < b_end); 405 tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 406 407 for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 408 { 409 if (bm0_is_set(p1->bm0_r, b0)) 410 { 411 return True; 412 } 413 } 414 } 415 } 416 return 0; 417} 418 419Bool DRD_(bm_has_any_store)(struct bitmap* const bm, 420 const Addr a1, const Addr a2) 421{ 422 Addr b, b_next; 423 424 tl_assert(bm); 425 426 for (b = a1; b < a2; b = b_next) 427 { 428 const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b)); 429 430 b_next = first_address_with_higher_msb(b); 431 if (b_next > a2) 432 { 433 b_next = a2; 434 } 435 436 if (bm2) 437 { 438 Addr b_start; 439 Addr b_end; 440 UWord b0; 441 const struct bitmap1* const p1 = &bm2->bm1; 442 443 if (make_address(bm2->addr, 0) < a1) 444 b_start = a1; 445 else 446 if (make_address(bm2->addr, 0) < a2) 447 b_start = make_address(bm2->addr, 0); 448 else 449 break; 450 tl_assert(a1 <= b_start && b_start <= a2); 451 452 if (make_address(bm2->addr + 1, 0) < a2) 453 b_end = make_address(bm2->addr + 1, 0); 454 else 455 b_end = a2; 456 tl_assert(a1 <= b_end && b_end <= a2); 457 tl_assert(b_start < b_end); 458 tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 459 460 for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 461 { 462 if (bm0_is_set(p1->bm0_w, b0)) 463 { 464 return True; 465 } 466 } 467 } 468 } 469 return 0; 470} 471 472/* Return True if there is a read access, write access or both */ 473/* to any of the addresses in the range [ a1, a2 [ in bitmap bm. */ 474Bool DRD_(bm_has_any_access)(struct bitmap* const bm, 475 const Addr a1, const Addr a2) 476{ 477 Addr b, b_next; 478 479 tl_assert(bm); 480 481 for (b = a1; b < a2; b = b_next) 482 { 483 const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b)); 484 485 b_next = first_address_with_higher_msb(b); 486 if (b_next > a2) 487 { 488 b_next = a2; 489 } 490 491 if (bm2) 492 { 493 Addr b_start; 494 Addr b_end; 495 UWord b0; 496 const struct bitmap1* const p1 = &bm2->bm1; 497 498 if (make_address(bm2->addr, 0) < a1) 499 b_start = a1; 500 else 501 if (make_address(bm2->addr, 0) < a2) 502 b_start = make_address(bm2->addr, 0); 503 else 504 break; 505 tl_assert(a1 <= b_start && b_start <= a2); 506 507 if (make_address(bm2->addr + 1, 0) < a2) 508 b_end = make_address(bm2->addr + 1, 0); 509 else 510 b_end = a2; 511 tl_assert(a1 <= b_end && b_end <= a2); 512 tl_assert(b_start < b_end); 513 tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 514 515 for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 516 { 517 /* 518 * Note: the statement below uses a binary or instead of a logical 519 * or on purpose. 520 */ 521 if (bm0_is_set(p1->bm0_r, b0) | bm0_is_set(p1->bm0_w, b0)) 522 { 523 return True; 524 } 525 } 526 } 527 } 528 return False; 529} 530 531/** 532 * Report whether an access of type access_type at address a is recorded in 533 * bitmap bm. 534 */ 535Bool DRD_(bm_has_1)(struct bitmap* const bm, 536 const Addr a, const BmAccessTypeT access_type) 537{ 538 const struct bitmap2* p2; 539 const struct bitmap1* p1; 540 const UWord* p0; 541 const UWord a0 = address_lsb(a); 542 543 tl_assert(bm); 544 545 p2 = bm2_lookup(bm, address_msb(a)); 546 if (p2) 547 { 548 p1 = &p2->bm1; 549 p0 = (access_type == eLoad) ? p1->bm0_r : p1->bm0_w; 550 return bm0_is_set(p0, a0) ? True : False; 551 } 552 return False; 553} 554 555void DRD_(bm_clear)(struct bitmap* const bm, Addr a1, Addr a2) 556{ 557 Addr b, b_next; 558 559 tl_assert(bm); 560 tl_assert(a1); 561 tl_assert(a1 <= a2); 562 tl_assert(a1 == first_address_with_same_lsb(a1)); 563 tl_assert(a2 == first_address_with_same_lsb(a2)); 564 565 for (b = a1; b < a2; b = b_next) 566 { 567 struct bitmap2* p2; 568 Addr c; 569 570#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 571 tl_assert(a1 <= b && b < a2); 572#endif 573 574 p2 = bm2_lookup_exclusive(bm, address_msb(b)); 575 576 b_next = first_address_with_higher_msb(b); 577 if (b_next > a2) 578 { 579 b_next = a2; 580 } 581 582 if (p2 == 0) 583 continue; 584 585 c = b; 586 /* If the first address in the bitmap that must be cleared does not */ 587 /* start on an UWord boundary, start clearing the first addresses. */ 588 if (uword_lsb(address_lsb(c))) 589 { 590 Addr c_next = first_address_with_higher_uword_msb(c); 591 if (c_next > b_next) 592 c_next = b_next; 593#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 594 tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next 595 && b_next <= a2); 596#endif 597 bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(c_next - c)); 598 bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(c_next - c)); 599 c = c_next; 600 } 601 /* If some UWords have to be cleared entirely, do this now. */ 602 if (uword_lsb(address_lsb(c)) == 0) 603 { 604 Addr c_next = first_address_with_same_uword_lsb(b_next); 605#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 606 tl_assert(uword_lsb(address_lsb(c)) == 0); 607 tl_assert(uword_lsb(address_lsb(c_next)) == 0); 608 tl_assert(c_next <= b_next); 609#endif 610 if (c_next > c) 611 { 612 UWord idx = uword_msb(address_lsb(c)); 613 VG_(memset)(&p2->bm1.bm0_r[idx], 0, SCALED_SIZE((c_next - c) / 8)); 614 VG_(memset)(&p2->bm1.bm0_w[idx], 0, SCALED_SIZE((c_next - c) / 8)); 615 c = c_next; 616 } 617 } 618 /* If the last address in the bitmap that must be cleared does not */ 619 /* fall on an UWord boundary, clear the last addresses. */ 620#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 621 tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 622#endif 623 bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(b_next - c)); 624 bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(b_next - c)); 625 } 626} 627 628/** 629 * Clear all references to loads in bitmap bm starting at address a1 and 630 * up to but not including address a2. 631 */ 632void DRD_(bm_clear_load)(struct bitmap* const bm, Addr a1, Addr a2) 633{ 634 Addr b, b_next; 635 636 tl_assert(bm); 637 tl_assert(a1); 638 tl_assert(a1 <= a2); 639 tl_assert(a1 == first_address_with_same_lsb(a1)); 640 tl_assert(a2 == first_address_with_same_lsb(a2)); 641 642 for (b = a1; b < a2; b = b_next) 643 { 644 struct bitmap2* p2; 645 Addr c; 646 647#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 648 tl_assert(a1 <= b && b < a2); 649#endif 650 651 p2 = bm2_lookup_exclusive(bm, address_msb(b)); 652 653 b_next = first_address_with_higher_msb(b); 654 if (b_next > a2) 655 { 656 b_next = a2; 657 } 658 659 if (p2 == 0) 660 continue; 661 662 c = b; 663 /* If the first address in the bitmap that must be cleared does not */ 664 /* start on an UWord boundary, start clearing the first addresses. */ 665#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 666 tl_assert(a1 <= b && b <= c && c < b_next && b_next <= a2); 667#endif 668 if (uword_lsb(address_lsb(c))) 669 { 670 Addr c_next = first_address_with_higher_uword_msb(c); 671 if (c_next > b_next) 672 c_next = b_next; 673#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 674 tl_assert(a1 <= b && b <= c && c < c_next && c_next <= b_next 675 && b_next <= a2); 676#endif 677 bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(c_next - c)); 678 c = c_next; 679 } 680 /* If some UWords have to be cleared entirely, do this now. */ 681#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 682 tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 683#endif 684 if (uword_lsb(address_lsb(c)) == 0) 685 { 686 Addr c_next = first_address_with_same_uword_lsb(b_next); 687#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 688 tl_assert(uword_lsb(address_lsb(c)) == 0); 689 tl_assert(uword_lsb(address_lsb(c_next)) == 0); 690 tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next 691 && b_next <= a2); 692#endif 693 if (c_next > c) 694 { 695 UWord idx = uword_msb(address_lsb(c)); 696 VG_(memset)(&p2->bm1.bm0_r[idx], 0, SCALED_SIZE((c_next - c) / 8)); 697 c = c_next; 698 } 699 } 700 /* If the last address in the bitmap that must be cleared does not */ 701 /* fall on an UWord boundary, clear the last addresses. */ 702#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 703 tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 704#endif 705 bm0_clear_range(p2->bm1.bm0_r, address_lsb(c), SCALED_SIZE(b_next - c)); 706 } 707} 708 709/** 710 * Clear all references to stores in bitmap bm starting at address a1 and 711 * up to but not including address a2. 712 */ 713void DRD_(bm_clear_store)(struct bitmap* const bm, 714 const Addr a1, const Addr a2) 715{ 716 Addr b, b_next; 717 718 tl_assert(bm); 719 tl_assert(a1); 720 tl_assert(a1 <= a2); 721 tl_assert(a1 == first_address_with_same_lsb(a1)); 722 tl_assert(a2 == first_address_with_same_lsb(a2)); 723 724 for (b = a1; b < a2; b = b_next) 725 { 726 struct bitmap2* p2; 727 Addr c; 728 729#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 730 tl_assert(a1 <= b && b < a2); 731#endif 732 733 p2 = bm2_lookup_exclusive(bm, address_msb(b)); 734 735 b_next = first_address_with_higher_msb(b); 736 if (b_next > a2) 737 { 738 b_next = a2; 739 } 740 741 if (p2 == 0) 742 continue; 743 744 c = b; 745 /* If the first address in the bitmap that must be cleared does not */ 746 /* start on an UWord boundary, start clearing the first addresses. */ 747#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 748 tl_assert(a1 <= b && b <= c && c < b_next && b_next <= a2); 749#endif 750 if (uword_lsb(address_lsb(c))) 751 { 752 Addr c_next = first_address_with_higher_uword_msb(c); 753 if (c_next > b_next) 754 c_next = b_next; 755#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 756 tl_assert(a1 <= b && b <= c && c < c_next && c_next <= b_next 757 && b_next <= a2); 758#endif 759 bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(c_next - c)); 760 c = c_next; 761 } 762 /* If some UWords have to be cleared entirely, do this now. */ 763#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 764 tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 765#endif 766 if (uword_lsb(address_lsb(c)) == 0) 767 { 768 Addr c_next = first_address_with_same_uword_lsb(b_next); 769#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 770 tl_assert(uword_lsb(address_lsb(c)) == 0); 771 tl_assert(uword_lsb(address_lsb(c_next)) == 0); 772 tl_assert(a1 <= b && b <= c && c <= c_next && c_next <= b_next 773 && b_next <= a2); 774#endif 775 if (c_next > c) 776 { 777 UWord idx = uword_msb(address_lsb(c)); 778 VG_(memset)(&p2->bm1.bm0_w[idx], 0, SCALED_SIZE((c_next - c) / 8)); 779 c = c_next; 780 } 781 } 782 /* If the last address in the bitmap that must be cleared does not */ 783 /* fall on an UWord boundary, clear the last addresses. */ 784#ifdef ENABLE_DRD_CONSISTENCY_CHECKS 785 tl_assert(a1 <= b && b <= c && c <= b_next && b_next <= a2); 786#endif 787 bm0_clear_range(p2->bm1.bm0_w, address_lsb(c), SCALED_SIZE(b_next - c)); 788 } 789} 790 791/** 792 * Clear bitmap bm starting at address a1 and up to but not including address 793 * a2. Return True if and only if any of the addresses was set before 794 * clearing. 795 */ 796Bool DRD_(bm_test_and_clear)(struct bitmap* const bm, 797 const Addr a1, const Addr a2) 798{ 799 Bool result; 800 801 result = DRD_(bm_has_any_access)(bm, a1, a2) != 0; 802 DRD_(bm_clear)(bm, a1, a2); 803 return result; 804} 805 806Bool DRD_(bm_has_conflict_with)(struct bitmap* const bm, 807 const Addr a1, const Addr a2, 808 const BmAccessTypeT access_type) 809{ 810 Addr b, b_next; 811 812 tl_assert(bm); 813 814 for (b = a1; b < a2; b = b_next) 815 { 816 const struct bitmap2* bm2 = bm2_lookup(bm, address_msb(b)); 817 818 b_next = first_address_with_higher_msb(b); 819 if (b_next > a2) 820 { 821 b_next = a2; 822 } 823 824 if (bm2) 825 { 826 Addr b_start; 827 Addr b_end; 828 UWord b0; 829 const struct bitmap1* const p1 = &bm2->bm1; 830 831 if (make_address(bm2->addr, 0) < a1) 832 b_start = a1; 833 else 834 if (make_address(bm2->addr, 0) < a2) 835 b_start = make_address(bm2->addr, 0); 836 else 837 break; 838 tl_assert(a1 <= b_start && b_start <= a2); 839 840 if (make_address(bm2->addr + 1, 0) < a2) 841 b_end = make_address(bm2->addr + 1, 0); 842 else 843 b_end = a2; 844 tl_assert(a1 <= b_end && b_end <= a2); 845 tl_assert(b_start < b_end); 846 tl_assert(address_lsb(b_start) <= address_lsb(b_end - 1)); 847 848 for (b0 = address_lsb(b_start); b0 <= address_lsb(b_end - 1); b0++) 849 { 850 if (access_type == eLoad) 851 { 852 if (bm0_is_set(p1->bm0_w, b0)) 853 { 854 return True; 855 } 856 } 857 else 858 { 859 tl_assert(access_type == eStore); 860 if (bm0_is_set(p1->bm0_r, b0) 861 | bm0_is_set(p1->bm0_w, b0)) 862 { 863 return True; 864 } 865 } 866 } 867 } 868 } 869 return False; 870} 871 872Bool DRD_(bm_load_has_conflict_with)(struct bitmap* const bm, 873 const Addr a1, const Addr a2) 874{ 875 return DRD_(bm_has_conflict_with)(bm, a1, a2, eLoad); 876} 877 878Bool DRD_(bm_load_1_has_conflict_with)(struct bitmap* const bm, const Addr a1) 879{ 880 return bm_aligned_load_has_conflict_with(bm, a1, 1); 881} 882 883Bool DRD_(bm_load_2_has_conflict_with)(struct bitmap* const bm, const Addr a1) 884{ 885 if ((a1 & 1) == 0) 886 return bm_aligned_load_has_conflict_with(bm, a1, 2); 887 else 888 return DRD_(bm_has_conflict_with)(bm, a1, a1 + 2, eLoad); 889} 890 891Bool DRD_(bm_load_4_has_conflict_with)(struct bitmap* const bm, const Addr a1) 892{ 893 if ((a1 & 3) == 0) 894 return bm_aligned_load_has_conflict_with(bm, a1, 4); 895 else 896 return DRD_(bm_has_conflict_with)(bm, a1, a1 + 4, eLoad); 897} 898 899Bool DRD_(bm_load_8_has_conflict_with)(struct bitmap* const bm, const Addr a1) 900{ 901 if ((a1 & 7) == 0) 902 return bm_aligned_load_has_conflict_with(bm, a1, 8); 903 else 904 return DRD_(bm_has_conflict_with)(bm, a1, a1 + 8, eLoad); 905} 906 907Bool DRD_(bm_store_1_has_conflict_with)(struct bitmap* const bm, const Addr a1) 908{ 909 return bm_aligned_store_has_conflict_with(bm, a1, 1); 910} 911 912Bool DRD_(bm_store_2_has_conflict_with)(struct bitmap* const bm, const Addr a1) 913{ 914 if ((a1 & 1) == 0) 915 return bm_aligned_store_has_conflict_with(bm, a1, 2); 916 else 917 return DRD_(bm_has_conflict_with)(bm, a1, a1 + 2, eStore); 918} 919 920Bool DRD_(bm_store_4_has_conflict_with)(struct bitmap* const bm, const Addr a1) 921{ 922 if ((a1 & 3) == 0) 923 return bm_aligned_store_has_conflict_with(bm, a1, 4); 924 else 925 return DRD_(bm_has_conflict_with)(bm, a1, a1 + 4, eStore); 926} 927 928Bool DRD_(bm_store_8_has_conflict_with)(struct bitmap* const bm, const Addr a1) 929{ 930 if ((a1 & 7) == 0) 931 return bm_aligned_store_has_conflict_with(bm, a1, 8); 932 else 933 return DRD_(bm_has_conflict_with)(bm, a1, a1 + 8, eStore); 934} 935 936Bool DRD_(bm_store_has_conflict_with)(struct bitmap* const bm, 937 const Addr a1, const Addr a2) 938{ 939 return DRD_(bm_has_conflict_with)(bm, a1, a2, eStore); 940} 941 942/** 943 * Return True if the two bitmaps *lhs and *rhs are identical, and false 944 * if not. 945 */ 946Bool DRD_(bm_equal)(struct bitmap* const lhs, struct bitmap* const rhs) 947{ 948 struct bitmap2* bm2l; 949 struct bitmap2* bm2r; 950 951 /* It's not possible to have two independent iterators over the same OSet, */ 952 /* so complain if lhs == rhs. */ 953 tl_assert(lhs != rhs); 954 955 VG_(OSetGen_ResetIter)(lhs->oset); 956 VG_(OSetGen_ResetIter)(rhs->oset); 957 958 for ( ; (bm2l = VG_(OSetGen_Next)(lhs->oset)) != 0; ) 959 { 960 while (bm2l 961 && ! DRD_(bm_has_any_access)(lhs, 962 make_address(bm2l->addr, 0), 963 make_address(bm2l->addr + 1, 0))) 964 { 965 bm2l = VG_(OSetGen_Next)(lhs->oset); 966 } 967 if (bm2l == 0) 968 break; 969 tl_assert(bm2l); 970 971 do 972 { 973 bm2r = VG_(OSetGen_Next)(rhs->oset); 974 if (bm2r == 0) 975 return False; 976 } 977 while (! DRD_(bm_has_any_access)(rhs, 978 make_address(bm2r->addr, 0), 979 make_address(bm2r->addr + 1, 0))); 980 981 tl_assert(bm2r); 982 tl_assert(DRD_(bm_has_any_access)(rhs, 983 make_address(bm2r->addr, 0), 984 make_address(bm2r->addr + 1, 0))); 985 986 if (bm2l != bm2r 987 && (bm2l->addr != bm2r->addr 988 || VG_(memcmp)(&bm2l->bm1, &bm2r->bm1, sizeof(bm2l->bm1)) != 0)) 989 { 990 return False; 991 } 992 } 993 994 do 995 { 996 bm2r = VG_(OSetGen_Next)(rhs->oset); 997 } while (bm2r && ! DRD_(bm_has_any_access)(rhs, 998 make_address(bm2r->addr, 0), 999 make_address(bm2r->addr + 1, 0))); 1000 if (bm2r) 1001 { 1002 tl_assert(DRD_(bm_has_any_access)(rhs, 1003 make_address(bm2r->addr, 0), 1004 make_address(bm2r->addr + 1, 0))); 1005 return False; 1006 } 1007 return True; 1008} 1009 1010void DRD_(bm_swap)(struct bitmap* const bm1, struct bitmap* const bm2) 1011{ 1012 OSet* const tmp = bm1->oset; 1013 bm1->oset = bm2->oset; 1014 bm2->oset = tmp; 1015} 1016 1017/** Merge bitmaps *lhs and *rhs into *lhs. */ 1018void DRD_(bm_merge2)(struct bitmap* const lhs, struct bitmap* const rhs) 1019{ 1020 struct bitmap2* bm2l; 1021 struct bitmap2* bm2r; 1022 1023 /* 1024 * It's not possible to have two independent iterators over the same OSet, 1025 * so complain if lhs == rhs. 1026 */ 1027 tl_assert(lhs != rhs); 1028 1029 s_bitmap_merge_count++; 1030 1031 VG_(OSetGen_ResetIter)(rhs->oset); 1032 1033 for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; ) 1034 { 1035 bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr); 1036 if (bm2l) 1037 { 1038 tl_assert(bm2l != bm2r); 1039 bm2_merge(bm2l, bm2r); 1040 } 1041 else 1042 { 1043 bm2_insert_copy(lhs, bm2r); 1044 } 1045 } 1046} 1047 1048/** Clear bitmap2::recalc. */ 1049void DRD_(bm_unmark)(struct bitmap* bm) 1050{ 1051 struct bitmap2* bm2; 1052 1053 for (VG_(OSetGen_ResetIter)(bm->oset); 1054 (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; 1055 ) 1056 { 1057 bm2->recalc = False; 1058 } 1059} 1060 1061/** 1062 * Report whether bitmap2::recalc has been set for the second level bitmap 1063 * corresponding to address a. 1064 */ 1065Bool DRD_(bm_is_marked)(struct bitmap* bm, const Addr a) 1066{ 1067 const struct bitmap2* bm2; 1068 1069 bm2 = bm2_lookup(bm, a); 1070 return bm2 && bm2->recalc; 1071} 1072 1073/** 1074 * Set bitmap2::recalc in bml for each second level bitmap in bmr that contains 1075 * at least one access. 1076 * 1077 * @note Any new second-level bitmaps inserted in bml by this function are 1078 * uninitialized. 1079 */ 1080void DRD_(bm_mark)(struct bitmap* bml, struct bitmap* bmr) 1081{ 1082 struct bitmap2* bm2l; 1083 struct bitmap2* bm2r; 1084 1085 for (VG_(OSetGen_ResetIter)(bmr->oset); 1086 (bm2r = VG_(OSetGen_Next)(bmr->oset)) != 0; 1087 ) 1088 { 1089 bm2l = bm2_lookup_or_insert(bml, bm2r->addr); 1090 bm2l->recalc = True; 1091 } 1092} 1093 1094/** Clear all second-level bitmaps for which bitmap2::recalc == True. */ 1095void DRD_(bm_clear_marked)(struct bitmap* bm) 1096{ 1097 struct bitmap2* bm2; 1098 1099 for (VG_(OSetGen_ResetIter)(bm->oset); 1100 (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; 1101 ) 1102 { 1103 if (bm2->recalc) 1104 bm2_clear(bm2); 1105 } 1106} 1107 1108/** Merge the second level bitmaps from *rhs into *lhs for which recalc == True. */ 1109void DRD_(bm_merge2_marked)(struct bitmap* const lhs, struct bitmap* const rhs) 1110{ 1111 struct bitmap2* bm2l; 1112 struct bitmap2* bm2r; 1113 1114 /* 1115 * It's not possible to have two independent iterators over the same OSet, 1116 * so complain if lhs == rhs. 1117 */ 1118 tl_assert(lhs != rhs); 1119 1120 s_bitmap_merge_count++; 1121 1122 VG_(OSetGen_ResetIter)(rhs->oset); 1123 1124 for ( ; (bm2r = VG_(OSetGen_Next)(rhs->oset)) != 0; ) 1125 { 1126 bm2l = VG_(OSetGen_Lookup)(lhs->oset, &bm2r->addr); 1127 if (bm2l && bm2l->recalc) 1128 { 1129 tl_assert(bm2l != bm2r); 1130 bm2_merge(bm2l, bm2r); 1131 } 1132 } 1133} 1134 1135/** Remove all marked second-level bitmaps that do not contain any access. */ 1136void DRD_(bm_remove_cleared_marked)(struct bitmap* bm) 1137{ 1138 struct bitmap2* bm2; 1139 1140 VG_(OSetGen_ResetIter)(bm->oset); 1141 for ( ; (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; ) 1142 { 1143 const UWord a1 = bm2->addr; 1144 if (bm2->recalc 1145 && ! DRD_(bm_has_any_access(bm, make_address(a1, 0), 1146 make_address(a1 + 1, 0)))) 1147 { 1148 bm2_remove(bm, a1); 1149 VG_(OSetGen_ResetIterAt)(bm->oset, &a1); 1150 } 1151 } 1152} 1153 1154/** 1155 * Report whether there are any RW / WR / WW patterns in lhs and rhs. 1156 * @param lhs First bitmap. 1157 * @param rhs Bitmap to be compared with lhs. 1158 * @return !=0 if there are data races, == 0 if there are none. 1159 */ 1160int DRD_(bm_has_races)(struct bitmap* const lhs, struct bitmap* const rhs) 1161{ 1162 VG_(OSetGen_ResetIter)(lhs->oset); 1163 VG_(OSetGen_ResetIter)(rhs->oset); 1164 1165 for (;;) 1166 { 1167 const struct bitmap2* bm2l; 1168 const struct bitmap2* bm2r; 1169 const struct bitmap1* bm1l; 1170 const struct bitmap1* bm1r; 1171 unsigned k; 1172 1173 bm2l = VG_(OSetGen_Next)(lhs->oset); 1174 bm2r = VG_(OSetGen_Next)(rhs->oset); 1175 while (bm2l && bm2r && bm2l->addr != bm2r->addr) 1176 { 1177 if (bm2l->addr < bm2r->addr) 1178 bm2l = VG_(OSetGen_Next)(lhs->oset); 1179 else 1180 bm2r = VG_(OSetGen_Next)(rhs->oset); 1181 } 1182 if (bm2l == 0 || bm2r == 0) 1183 break; 1184 1185 bm1l = &bm2l->bm1; 1186 bm1r = &bm2r->bm1; 1187 1188 for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 1189 { 1190 unsigned b; 1191 for (b = 0; b < BITS_PER_UWORD; b++) 1192 { 1193 UWord const access_mask 1194 = ((bm1l->bm0_r[k] & bm0_mask(b)) ? LHS_R : 0) 1195 | ((bm1l->bm0_w[k] & bm0_mask(b)) ? LHS_W : 0) 1196 | ((bm1r->bm0_r[k] & bm0_mask(b)) ? RHS_R : 0) 1197 | ((bm1r->bm0_w[k] & bm0_mask(b)) ? RHS_W : 0); 1198 Addr const a = make_address(bm2l->addr, k * BITS_PER_UWORD | b); 1199 if (HAS_RACE(access_mask) && ! DRD_(is_suppressed)(a, a + 1)) 1200 { 1201 return 1; 1202 } 1203 } 1204 } 1205 } 1206 return 0; 1207} 1208 1209void DRD_(bm_print)(struct bitmap* const bm) 1210{ 1211 struct bitmap2* bm2; 1212 1213 for (VG_(OSetGen_ResetIter)(bm->oset); 1214 (bm2 = VG_(OSetGen_Next)(bm->oset)) != 0; 1215 ) 1216 { 1217 bm2_print(bm2); 1218 } 1219} 1220 1221static void bm2_print(const struct bitmap2* const bm2) 1222{ 1223 const struct bitmap1* bm1; 1224 Addr a; 1225 1226 tl_assert(bm2); 1227 1228 bm1 = &bm2->bm1; 1229 for (a = make_address(bm2->addr, 0); 1230 a <= make_address(bm2->addr + 1, 0) - 1; 1231 a++) 1232 { 1233 const Bool r = bm0_is_set(bm1->bm0_r, address_lsb(a)) != 0; 1234 const Bool w = bm0_is_set(bm1->bm0_w, address_lsb(a)) != 0; 1235 if (r || w) 1236 { 1237 VG_(printf)("0x%08lx %c %c\n", 1238 a, 1239 w ? 'W' : ' ', 1240 r ? 'R' : ' '); 1241 } 1242 } 1243} 1244 1245ULong DRD_(bm_get_bitmap_creation_count)(void) 1246{ 1247 return s_bitmap_creation_count; 1248} 1249 1250ULong DRD_(bm_get_bitmap2_creation_count)(void) 1251{ 1252 return s_bitmap2_creation_count; 1253} 1254 1255ULong DRD_(bm_get_bitmap2_merge_count)(void) 1256{ 1257 return s_bitmap2_merge_count; 1258} 1259 1260/** Compute *bm2l |= *bm2r. */ 1261static 1262void bm2_merge(struct bitmap2* const bm2l, const struct bitmap2* const bm2r) 1263{ 1264 unsigned k; 1265 1266 tl_assert(bm2l); 1267 tl_assert(bm2r); 1268 tl_assert(bm2l->addr == bm2r->addr); 1269 1270 s_bitmap2_merge_count++; 1271 1272 for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 1273 { 1274 bm2l->bm1.bm0_r[k] |= bm2r->bm1.bm0_r[k]; 1275 } 1276 for (k = 0; k < BITMAP1_UWORD_COUNT; k++) 1277 { 1278 bm2l->bm1.bm0_w[k] |= bm2r->bm1.bm0_w[k]; 1279 } 1280} 1281