Home | History | Annotate | Download | only in drd
      1 /*
      2   This file is part of drd, a thread error detector.
      3 
      4   Copyright (C) 2006-2015 Bart Van Assche <bvanassche (at) 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 }
   1281