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