drd/drd_bitmap.c

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