drd/drd_bitmap.h

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