drd/drd_bitmap.h

   1 /*
   2   This file is part of drd, a thread error detector.
   3
   4   Copyright (C) 2006-2011 Bart Van Assche <bvanassche@acm.org>.
   5
   6   This program is free software; you can redistribute it and/or
   7   modify it under the terms of the GNU General Public License as
   8   published by the Free Software Foundation; either version 2 of the
   9   License, or (at your option) any later version.
  10
  11   This program is distributed in the hope that it will be useful, but
  12   WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14   General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with this program; if not, write to the Free Software
  18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19   02111-1307, USA.
  20
  21   The GNU General Public License is contained in the file COPYING.
  22 */
  23
  24
  25 #ifndef __DRD_BITMAP_H
  26 #define __DRD_BITMAP_H
  27
  28
  29 #include "pub_drd_bitmap.h"
  30 #include "pub_tool_basics.h"
  31 #include "pub_tool_oset.h"
  32 #include "pub_tool_libcbase.h"
  33 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
  34 #include "pub_tool_libcassert.h"
  35 #endif
  36
  37
  38 /* Bitmap representation. A bitmap is a data structure in which two bits are
  39  * reserved per 32 bit address: one bit that indicates that the data at the
  40  * specified address has been read, and one bit that indicates that the data
  41  * has been written to.
  42  */
  43
  44 /* Client addresses are split into bitfields as follows:
  45  * ------------------------------------------------------
  46  * | Address MSB |      Address LSB      | Ignored bits |
  47  * ------------------------------------------------------
  48  * | Address MSB | UWord MSB | UWord LSB | Ignored bits |
  49  * ------------------------------------------------------
  50  */
  51
  52
  53
  54 /* Address MSB / LSB split. */
  55
  56
  57 /** Number of least significant address bits that are ignored. */
  58 #define ADDR_IGNORED_BITS 0
  59 #define ADDR_IGNORED_MASK ((1U << ADDR_IGNORED_BITS) - 1U)
  60 #define ADDR_GRANULARITY  (1U << ADDR_IGNORED_BITS)
  61
  62 /**
  63  * Round argument a up to a multiple of (1 << ADDR_GRANULARITY), and next
  64  * shift it right ADDR_GRANULARITY bits. The expression below is optimized
  65  * for the case where a is a constant.
  66  */
  67 #define SCALED_SIZE(a)                                                  \
  68    (((((a) - 1U) | ADDR_IGNORED_MASK) + 1U) >> ADDR_IGNORED_BITS)
  69
  70 /**
  71  * Number of bits assigned to the least significant component of an address.
  72  */
  73 #define ADDR_LSB_BITS 12
  74
  75 /**
  76  * Mask that has to be applied to an address of type Addr in order to
  77  * compute the least significant part of an address split, after having
  78  * shifted the address bits ADDR_GRANULARITY to the right.
  79  */
  80 #define ADDR_LSB_MASK (((UWord)1 << ADDR_LSB_BITS) - 1U)
  81
  82 /** Compute least significant bits of an address of type Addr. */
  83 static __inline__
  84 UWord address_lsb(const Addr a)
  85 { return (a >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK; }
  86
  87 /**
  88  * Compute the first address for which address_lsb() is equal to
  89  * address_lsb(a).
  90  */
  91 static __inline__
  92 Addr first_address_with_same_lsb(const Addr a)
  93 {
  94    return ((a | ADDR_IGNORED_MASK) ^ ADDR_IGNORED_MASK);
  95 }
  96
  97 /**
  98  * Compute the first address for which address_lsb() is greater than
  99  * address_lsb(a).
 100  */
 101 static __inline__
 102 Addr first_address_with_higher_lsb(const Addr a)
 103 {
 104    return ((a | ADDR_IGNORED_MASK) + 1U);
 105 }
 106
 107 /** Compute most significant bits of an address of type Addr. */
 108 static __inline__
 109 UWord address_msb(const Addr a)
 110 { return a >> (ADDR_LSB_BITS + ADDR_IGNORED_BITS); }
 111
 112 static __inline__
 113 Addr first_address_with_higher_msb(const Addr a)
 114 {
 115    return ((a | ((ADDR_LSB_MASK << ADDR_IGNORED_BITS) | ADDR_IGNORED_MASK))
 116            + 1U);
 117 }
 118
 119 /**
 120  * Convert LSB and MSB back into an address.
 121  *
 122  * @note It is assumed that sizeof(Addr) == sizeof(UWord).
 123  */
 124 static __inline__
 125 Addr make_address(const UWord a1, const UWord a0)
 126 {
 127    return ((a1 << (ADDR_LSB_BITS + ADDR_IGNORED_BITS))
 128            | (a0 << ADDR_IGNORED_BITS));
 129 }
 130
 131
 132
 133
 134
 135 /** Number of bits that fit in a variable of type UWord. */
 136 #define BITS_PER_UWORD (8U * sizeof(UWord))
 137
 138 /** Log2 of BITS_PER_UWORD. */
 139 #if defined(VGA_x86) || defined(VGA_ppc32) || defined(VGA_arm)
 140 #define BITS_PER_BITS_PER_UWORD 5
 141 #elif defined(VGA_amd64) || defined(VGA_ppc64) || defined(VGA_s390x)
 142 #define BITS_PER_BITS_PER_UWORD 6
 143 #else
 144 #error Unknown platform.
 145 #endif
 146
 147 /** Number of UWord's needed to store one bit per address LSB. */
 148 #define BITMAP1_UWORD_COUNT (1U << (ADDR_LSB_BITS - BITS_PER_BITS_PER_UWORD))
 149
 150 /**
 151  * Mask that has to be applied to an (Addr >> ADDR_IGNORED_BITS) expression
 152  * in order to compute the least significant part of an UWord.
 153  */
 154 #define UWORD_LSB_MASK (((UWord)1 << BITS_PER_BITS_PER_UWORD) - 1)
 155
 156 /**
 157  * Compute index into bm0[] array.
 158  *
 159  * @param a Address shifted right ADDR_IGNORED_BITS bits.
 160  */
 161 static __inline__
 162 UWord uword_msb(const UWord a)
 163 {
 164 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 165    tl_assert(a < (1U << ADDR_LSB_BITS));
 166 #endif
 167    return a >> BITS_PER_BITS_PER_UWORD;
 168 }
 169
 170 /**
 171  * Return the least significant bits.
 172  *
 173  * @param a Address shifted right ADDR_IGNORED_BITS bits.
 174  */
 175 static __inline__
 176 UWord uword_lsb(const UWord a)
 177 {
 178 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 179    tl_assert(a < (1U << ADDR_LSB_BITS));
 180 #endif
 181    return a & UWORD_LSB_MASK;
 182 }
 183
 184 /**
 185  * Compute the highest address lower than a for which
 186  * uword_lsb(address_lsb(a)) == 0.
 187  *
 188  * @param a Address.
 189  */
 190 static __inline__
 191 Addr first_address_with_same_uword_lsb(const Addr a)
 192 {
 193    return (a & (~UWORD_LSB_MASK << ADDR_IGNORED_BITS));
 194 }
 195
 196 /**
 197  * First address that will go in the UWord past the one 'a' goes in.
 198  *
 199  *  @param a Address.
 200  */
 201 static __inline__
 202 Addr first_address_with_higher_uword_msb(const Addr a)
 203 {
 204    return ((a | ((UWORD_LSB_MASK << ADDR_IGNORED_BITS) | ADDR_IGNORED_MASK))
 205            + 1);
 206 }
 207
 208
 209
 210 /* Local variables. */
 211
 212 static ULong s_bitmap2_creation_count;
 213
 214
 215
 216 /*********************************************************************/
 217 /*           Functions for manipulating a struct bitmap1.            */
 218 /*********************************************************************/
 219
 220
 221 /* Lowest level, corresponding to the lowest ADDR_LSB_BITS of an address. */
 222 struct bitmap1
 223 {
 224    UWord bm0_r[BITMAP1_UWORD_COUNT];
 225    UWord bm0_w[BITMAP1_UWORD_COUNT];
 226 };
 227
 228 static __inline__ UWord bm0_mask(const UWord a)
 229 {
 230 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 231    tl_assert(address_msb(make_address(0, a)) == 0);
 232 #endif
 233    return ((UWord)1 << uword_lsb(a));
 234 }
 235
 236 /** Set the bit corresponding to address a in bitmap bm0. */
 237 static __inline__ void bm0_set(UWord* bm0, const UWord a)
 238 {
 239 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 240    tl_assert(address_msb(make_address(0, a)) == 0);
 241 #endif
 242    bm0[uword_msb(a)] |= (UWord)1 << uword_lsb(a);
 243 }
 244
 245 /**
 246  * Set the bits corresponding to all of the addresses in range
 247  * [ a << ADDR_IGNORED_BITS .. (a + size) << ADDR_IGNORED_BITS [
 248  * in bitmap bm0.
 249  */
 250 static __inline__ void bm0_set_range(UWord* bm0,
 251                                      const UWord a, const SizeT size)
 252 {
 253 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 254    tl_assert(size > 0);
 255    tl_assert(address_msb(make_address(0, a)) == 0);
 256    tl_assert(address_msb(make_address(0, a + size - 1)) == 0);
 257    tl_assert(uword_msb(a) == uword_msb(a + size - 1));
 258 #endif
 259    bm0[uword_msb(a)]
 260       |= (((UWord)1 << size) - 1) << uword_lsb(a);
 261 }
 262
 263 /** Clear the bit corresponding to address a in bitmap bm0. */
 264 static __inline__ void bm0_clear(UWord* bm0, const UWord a)
 265 {
 266 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 267    tl_assert(address_msb(make_address(0, a)) == 0);
 268 #endif
 269    bm0[uword_msb(a)] &= ~((UWord)1 << uword_lsb(a));
 270 }
 271
 272 /**
 273  * Clear all of the addresses in range
 274  * [ a << ADDR_IGNORED_BITS .. (a + size) << ADDR_IGNORED_BITS [
 275  * in bitmap bm0.
 276  */
 277 static __inline__ void bm0_clear_range(UWord* bm0,
 278                                        const UWord a, const SizeT size)
 279 {
 280 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 281    tl_assert(address_msb(make_address(0, a)) == 0);
 282    tl_assert(size == 0 || address_msb(make_address(0, a + size - 1)) == 0);
 283    tl_assert(size == 0 || uword_msb(a) == uword_msb(a + size - 1));
 284 #endif
 285    /*
 286     * Note: although the expression below yields a correct result even if
 287     * size == 0, do not touch bm0[] if size == 0 because this might otherwise
 288     * cause an access of memory just past the end of the bm0[] array.
 289     */
 290    if (size > 0)
 291    {
 292       bm0[uword_msb(a)]
 293          &= ~((((UWord)1 << size) - 1) << uword_lsb(a));
 294    }
 295 }
 296
 297 /** Test whether the bit corresponding to address a is set in bitmap bm0. */
 298 static __inline__ UWord bm0_is_set(const UWord* bm0, const UWord a)
 299 {
 300 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 301    tl_assert(address_msb(make_address(0, a)) == 0);
 302 #endif
 303    return (bm0[uword_msb(a)] & ((UWord)1 << uword_lsb(a)));
 304 }
 305
 306 /**
 307  * Return true if a bit corresponding to any of the addresses in range
 308  * [ a << ADDR_IGNORED_BITS .. (a + size) << ADDR_IGNORED_BITS [
 309  * is set in bm0.
 310  */
 311 static __inline__ UWord bm0_is_any_set(const UWord* bm0,
 312                                        const Addr a, const SizeT size)
 313 {
 314 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 315    tl_assert(size > 0);
 316    tl_assert(address_msb(make_address(0, a)) == 0);
 317    tl_assert(address_msb(make_address(0, a + size - 1)) == 0);
 318    tl_assert(uword_msb(a) == uword_msb(a + size - 1));
 319 #endif
 320    return (bm0[uword_msb(a)] & ((((UWord)1 << size) - 1) << uword_lsb(a)));
 321 }
 322
 323
 324
 325 /*********************************************************************/
 326 /*           Functions for manipulating a struct bitmap.             */
 327 /*********************************************************************/
 328
 329
 330 /* Second level bitmap. */
 331 struct bitmap2
 332 {
 333    Addr           addr;   ///< address_msb(...)
 334    Bool           recalc;
 335    struct bitmap1 bm1;
 336 };
 337
 338
 339 static void bm2_clear(struct bitmap2* const bm2);
 340 static __inline__
 341 struct bitmap2* bm2_insert(struct bitmap* const bm, const UWord a1);
 342
 343
 344
 345 /**
 346  * Rotate elements cache[0..n-1] such that the element at position n-1 is
 347  * moved to position 0. This allows to speed up future cache lookups.
 348  */
 349 static __inline__
 350 void bm_cache_rotate(struct bm_cache_elem cache[], const int n)
 351 {
 352 #if 0
 353    struct bm_cache_elem t;
 354
 355    tl_assert(2 <= n && n <= 8);
 356
 357    t = cache[0];
 358    if (n > 1)
 359       cache[0] = cache[1];
 360    if (n > 2)
 361       cache[1] = cache[2];
 362    if (n > 3)
 363       cache[2] = cache[3];
 364    if (n > 4)
 365       cache[3] = cache[4];
 366    if (n > 5)
 367       cache[4] = cache[5];
 368    if (n > 6)
 369       cache[5] = cache[6];
 370    if (n > 7)
 371       cache[6] = cache[7];
 372    cache[n - 1] = t;
 373 #endif
 374 }
 375
 376 static __inline__
 377 Bool bm_cache_lookup(struct bitmap* const bm, const UWord a1,
 378                      struct bitmap2** bm2)
 379 {
 380 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 381    tl_assert(bm);
 382    tl_assert(bm2);
 383 #endif
 384
 385 #if DRD_BITMAP_N_CACHE_ELEM > 8
 386 #error Please update the code below.
 387 #endif
 388 #if DRD_BITMAP_N_CACHE_ELEM >= 1
 389    if (a1 == bm->cache[0].a1)
 390    {
 391       *bm2 = bm->cache[0].bm2;
 392       return True;
 393    }
 394 #endif
 395 #if DRD_BITMAP_N_CACHE_ELEM >= 2
 396    if (a1 == bm->cache[1].a1)
 397    {
 398       *bm2 = bm->cache[1].bm2;
 399       return True;
 400    }
 401 #endif
 402 #if DRD_BITMAP_N_CACHE_ELEM >= 3
 403    if (a1 == bm->cache[2].a1)
 404    {
 405       *bm2 = bm->cache[2].bm2;
 406       bm_cache_rotate(bm->cache, 3);
 407       return True;
 408    }
 409 #endif
 410 #if DRD_BITMAP_N_CACHE_ELEM >= 4
 411    if (a1 == bm->cache[3].a1)
 412    {
 413       *bm2 = bm->cache[3].bm2;
 414       bm_cache_rotate(bm->cache, 4);
 415       return True;
 416    }
 417 #endif
 418 #if DRD_BITMAP_N_CACHE_ELEM >= 5
 419    if (a1 == bm->cache[4].a1)
 420    {
 421       *bm2 = bm->cache[4].bm2;
 422       bm_cache_rotate(bm->cache, 5);
 423       return True;
 424    }
 425 #endif
 426 #if DRD_BITMAP_N_CACHE_ELEM >= 6
 427    if (a1 == bm->cache[5].a1)
 428    {
 429       *bm2 = bm->cache[5].bm2;
 430       bm_cache_rotate(bm->cache, 6);
 431       return True;
 432    }
 433 #endif
 434 #if DRD_BITMAP_N_CACHE_ELEM >= 7
 435    if (a1 == bm->cache[6].a1)
 436    {
 437       *bm2 = bm->cache[6].bm2;
 438       bm_cache_rotate(bm->cache, 7);
 439       return True;
 440    }
 441 #endif
 442 #if DRD_BITMAP_N_CACHE_ELEM >= 8
 443    if (a1 == bm->cache[7].a1)
 444    {
 445       *bm2 = bm->cache[7].bm2;
 446       bm_cache_rotate(bm->cache, 8);
 447       return True;
 448    }
 449 #endif
 450    *bm2 = 0;
 451    return False;
 452 }
 453
 454 static __inline__
 455 void bm_update_cache(struct bitmap* const bm,
 456                      const UWord a1,
 457                      struct bitmap2* const bm2)
 458 {
 459 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 460    tl_assert(bm);
 461 #endif
 462
 463 #if DRD_BITMAP_N_CACHE_ELEM > 8
 464 #error Please update the code below.
 465 #endif
 466 #if DRD_BITMAP_N_CACHE_ELEM >= 8
 467    bm->cache[7] = bm->cache[6];
 468 #endif
 469 #if DRD_BITMAP_N_CACHE_ELEM >= 7
 470    bm->cache[6] = bm->cache[5];
 471 #endif
 472 #if DRD_BITMAP_N_CACHE_ELEM >= 6
 473    bm->cache[5] = bm->cache[4];
 474 #endif
 475 #if DRD_BITMAP_N_CACHE_ELEM >= 5
 476    bm->cache[4] = bm->cache[3];
 477 #endif
 478 #if DRD_BITMAP_N_CACHE_ELEM >= 4
 479    bm->cache[3] = bm->cache[2];
 480 #endif
 481 #if DRD_BITMAP_N_CACHE_ELEM >= 3
 482    bm->cache[2] = bm->cache[1];
 483 #endif
 484 #if DRD_BITMAP_N_CACHE_ELEM >= 2
 485    bm->cache[1] = bm->cache[0];
 486 #endif
 487    bm->cache[0].a1  = a1;
 488    bm->cache[0].bm2 = bm2;
 489 }
 490
 491 /**
 492  * Look up the address a1 in bitmap bm and return a pointer to a potentially
 493  * shared second level bitmap. The bitmap where the returned pointer points
 494  * at may not be modified by the caller.
 495  *
 496  * @param a1 client address shifted right by ADDR_LSB_BITS.
 497  * @param bm bitmap pointer.
 498  */
 499 static __inline__
 500 const struct bitmap2* bm2_lookup(struct bitmap* const bm, const UWord a1)
 501 {
 502    struct bitmap2* bm2;
 503
 504 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 505    tl_assert(bm);
 506 #endif
 507
 508    if (! bm_cache_lookup(bm, a1, &bm2))
 509    {
 510       bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
 511       bm_update_cache(bm, a1, bm2);
 512    }
 513    return bm2;
 514 }
 515
 516 /**
 517  * Look up the address a1 in bitmap bm and return a pointer to a second
 518  * level bitmap that is not shared and hence may be modified.
 519  *
 520  * @param a1 client address shifted right by ADDR_LSB_BITS.
 521  * @param bm bitmap pointer.
 522  */
 523 static __inline__
 524 struct bitmap2*
 525 bm2_lookup_exclusive(struct bitmap* const bm, const UWord a1)
 526 {
 527    struct bitmap2* bm2;
 528
 529 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 530    tl_assert(bm);
 531 #endif
 532
 533    if (! bm_cache_lookup(bm, a1, &bm2))
 534    {
 535       bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
 536    }
 537
 538    return bm2;
 539 }
 540
 541 /** Clear the content of the second-level bitmap. */
 542 static __inline__
 543 void bm2_clear(struct bitmap2* const bm2)
 544 {
 545 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 546    tl_assert(bm2);
 547 #endif
 548    VG_(memset)(&bm2->bm1, 0, sizeof(bm2->bm1));
 549 }
 550
 551 /**
 552  * Insert an uninitialized second level bitmap for the address a1.
 553  *
 554  * @param bm bitmap pointer.
 555  * @param a1 client address shifted right by ADDR_LSB_BITS.
 556  *
 557  * @note bitmap2::recalc isn't initialized here on purpose.
 558  */
 559 static __inline__
 560 struct bitmap2* bm2_insert(struct bitmap* const bm, const UWord a1)
 561 {
 562    struct bitmap2* bm2;
 563
 564 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 565    tl_assert(bm);
 566 #endif
 567
 568    s_bitmap2_creation_count++;
 569
 570    bm2 = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*bm2));
 571    bm2->addr = a1;
 572    VG_(OSetGen_Insert)(bm->oset, bm2);
 573
 574    bm_update_cache(bm, a1, bm2);
 575
 576    return bm2;
 577 }
 578
 579 static __inline__
 580 struct bitmap2* bm2_insert_copy(struct bitmap* const bm,
 581                                 struct bitmap2* const bm2)
 582 {
 583    struct bitmap2* bm2_copy;
 584
 585    bm2_copy = bm2_insert(bm, bm2->addr);
 586    VG_(memcpy)(&bm2_copy->bm1, &bm2->bm1, sizeof(bm2->bm1));
 587    return bm2_copy;
 588 }
 589
 590 /**
 591  * Look up the address a1 in bitmap bm, and insert it if not found.
 592  * The returned second level bitmap may not be modified.
 593  *
 594  * @param bm bitmap pointer.
 595  * @param a1 client address shifted right by ADDR_LSB_BITS.
 596  */
 597 static __inline__
 598 struct bitmap2* bm2_lookup_or_insert(struct bitmap* const bm, const UWord a1)
 599 {
 600    struct bitmap2* bm2;
 601
 602 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 603    tl_assert(bm);
 604 #endif
 605
 606    if (bm_cache_lookup(bm, a1, &bm2))
 607    {
 608       if (bm2 == 0)
 609       {
 610          bm2 = bm2_insert(bm, a1);
 611          bm2_clear(bm2);
 612       }
 613    }
 614    else
 615    {
 616       bm2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
 617       if (! bm2)
 618       {
 619          bm2 = bm2_insert(bm, a1);
 620          bm2_clear(bm2);
 621       }
 622       bm_update_cache(bm, a1, bm2);
 623    }
 624    return bm2;
 625 }
 626
 627 /**
 628  * Look up the address a1 in bitmap bm, and insert it if not found.
 629  * The returned second level bitmap may be modified.
 630  *
 631  * @param a1 client address shifted right by ADDR_LSB_BITS.
 632  * @param bm bitmap pointer.
 633  */
 634 static __inline__
 635 struct bitmap2* bm2_lookup_or_insert_exclusive(struct bitmap* const bm,
 636                                                const UWord a1)
 637 {
 638    return bm2_lookup_or_insert(bm, a1);
 639 }
 640
 641 static __inline__
 642 void bm2_remove(struct bitmap* const bm, const UWord a1)
 643 {
 644    struct bitmap2* bm2;
 645
 646 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 647    tl_assert(bm);
 648 #endif
 649
 650    bm2 = VG_(OSetGen_Remove)(bm->oset, &a1);
 651    VG_(OSetGen_FreeNode)(bm->oset, bm2);
 652
 653    bm_update_cache(bm, a1, NULL);
 654 }
 655
 656 static __inline__
 657 void bm_access_aligned_load(struct bitmap* const bm,
 658                             const Addr a1, const SizeT size)
 659 {
 660    struct bitmap2* bm2;
 661
 662 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 663    tl_assert(bm);
 664 #endif
 665
 666    bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(a1));
 667    bm0_set_range(bm2->bm1.bm0_r,
 668                  (a1 >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK,
 669                  SCALED_SIZE(size));
 670 }
 671
 672 static __inline__
 673 void bm_access_aligned_store(struct bitmap* const bm,
 674                              const Addr a1, const SizeT size)
 675 {
 676    struct bitmap2* bm2;
 677
 678 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 679    tl_assert(bm);
 680 #endif
 681
 682    bm2 = bm2_lookup_or_insert_exclusive(bm, address_msb(a1));
 683    bm0_set_range(bm2->bm1.bm0_w,
 684                  (a1 >> ADDR_IGNORED_BITS) & ADDR_LSB_MASK,
 685                  SCALED_SIZE(size));
 686 }
 687
 688 static __inline__
 689 Bool bm_aligned_load_has_conflict_with(struct bitmap* const bm,
 690                                        const Addr a, const SizeT size)
 691 {
 692    const struct bitmap2* bm2;
 693
 694 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 695    tl_assert(bm);
 696 #endif
 697
 698    bm2 = bm2_lookup(bm, address_msb(a));
 699    return (bm2
 700            && bm0_is_any_set(bm2->bm1.bm0_w,
 701                              address_lsb(a),
 702                              SCALED_SIZE(size)));
 703 }
 704
 705 static __inline__
 706 Bool bm_aligned_store_has_conflict_with(struct bitmap* const bm,
 707                                         const Addr a, const SizeT size)
 708 {
 709    const struct bitmap2* bm2;
 710
 711 #ifdef ENABLE_DRD_CONSISTENCY_CHECKS
 712    tl_assert(bm);
 713 #endif
 714
 715    bm2 = bm2_lookup(bm, address_msb(a));
 716    if (bm2)
 717    {
 718       if (bm0_is_any_set(bm2->bm1.bm0_r, address_lsb(a), SCALED_SIZE(size))
 719           | bm0_is_any_set(bm2->bm1.bm0_w, address_lsb(a), SCALED_SIZE(size)))
 720       {
 721          return True;
 722       }
 723    }
 724    return False;
 725 }
 726
 727 #endif /* __DRD_BITMAP_H */