drd/drd_bitmap.h

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