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