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