drd/drd_bitmap.c

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