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