l4/pkg/valgrind/src/valgrind-3.6.0-svn/drd/drd_bitmap.c

   1 /* -*- mode: C; c-basic-offset: 3; indent-tabs-mode: nil; -*- */
   2 /*
   3   This file is part of drd, a thread error detector.
   4
   5   Copyright (C) 2006-2011 Bart Van Assche <bvanassche@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 }