drd/drd_bitmap.c

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