sewardj | af44c82 | 2007-11-25 14:01:38 +0000 | [diff] [blame] | 1 | /* |
| 2 | This file is part of drd, a data race detector. |
| 3 | |
sewardj | 8564292 | 2008-01-14 11:54:56 +0000 | [diff] [blame] | 4 | Copyright (C) 2006-2008 Bart Van Assche |
sewardj | af44c82 | 2007-11-25 14:01:38 +0000 | [diff] [blame] | 5 | bart.vanassche@gmail.com |
| 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 | #ifndef __DRD_BITMAP3_H |
| 27 | #define __DRD_BITMAP3_H |
| 28 | |
| 29 | |
| 30 | #include "pub_tool_oset.h" |
| 31 | |
| 32 | |
| 33 | /* |
| 34 | Bitmap representation. A bitmap is a data structure in which two bits are |
| 35 | reserved per 32 bit address: one bit that indicates that the data at the |
| 36 | specified address has been read, and one bit that indicates that the data has |
| 37 | been written to. |
| 38 | */ |
| 39 | |
| 40 | |
| 41 | /* Macro definitions. */ |
| 42 | |
| 43 | #define ADDR0_BITS 12 |
| 44 | |
| 45 | #define ADDR0_COUNT (1UL << ADDR0_BITS) |
| 46 | |
| 47 | #define ADDR0_MASK (ADDR0_COUNT - 1) |
| 48 | |
bart | 0268dfa | 2008-03-11 20:10:21 +0000 | [diff] [blame^] | 49 | #define SPLIT_ADDRESS(a) \ |
| 50 | UWord a##0 = ((a) & ADDR0_MASK); \ |
sewardj | af44c82 | 2007-11-25 14:01:38 +0000 | [diff] [blame] | 51 | UWord a##1 = ((a) >> ADDR0_BITS); |
| 52 | |
| 53 | // Assumption: sizeof(Addr) == sizeof(UWord). |
bart | 0268dfa | 2008-03-11 20:10:21 +0000 | [diff] [blame^] | 54 | #define MAKE_ADDRESS(a1, a0) \ |
sewardj | af44c82 | 2007-11-25 14:01:38 +0000 | [diff] [blame] | 55 | (Addr)(((UWord)(a1) << (ADDR0_BITS)) | ((UWord)(a0))) |
| 56 | |
| 57 | #define BITS_PER_UWORD (8UL*sizeof(UWord)) |
| 58 | #if defined(VGA_x86) || defined(VGA_ppc32) |
| 59 | #define BITS_PER_BITS_PER_UWORD 5 |
| 60 | #elif defined(VGA_amd64) || defined(VGA_ppc64) |
| 61 | #define BITS_PER_BITS_PER_UWORD 6 |
| 62 | #else |
| 63 | #error Unknown platform. |
| 64 | #endif |
| 65 | |
| 66 | #define BITMAP1_UWORD_COUNT (ADDR0_COUNT >> BITS_PER_BITS_PER_UWORD) |
| 67 | |
| 68 | /* Highest bits of an address that fit into the same UWord of bm0[]. */ |
| 69 | #define UWORD_MSB(a) ((a) & ~(BITS_PER_UWORD - 1)) |
| 70 | |
| 71 | /* Lowest bits of an address that fit into the same UWord of bm0[]. */ |
| 72 | #define UWORD_LSB(a) ((a) & (BITS_PER_UWORD - 1)) |
| 73 | |
| 74 | /* Highest address that fits in the same UWord as a. */ |
| 75 | #define UWORD_HIGHEST_ADDRESS(a) ((a) | (BITS_PER_UWORD - 1)) |
| 76 | |
| 77 | |
sewardj | af44c82 | 2007-11-25 14:01:38 +0000 | [diff] [blame] | 78 | // Local constants. |
| 79 | |
| 80 | static ULong s_bitmap2_creation_count; |
| 81 | |
| 82 | |
| 83 | /* Lowest level, corresponding to the lowest ADDR0_BITS of an address. */ |
| 84 | struct bitmap1 |
| 85 | { |
| 86 | UWord bm0_r[BITMAP1_UWORD_COUNT]; |
| 87 | UWord bm0_w[BITMAP1_UWORD_COUNT]; |
| 88 | }; |
| 89 | |
| 90 | static __inline__ UWord bm0_mask(const Addr a) |
| 91 | { |
| 92 | return (1UL << UWORD_LSB(a)); |
| 93 | } |
| 94 | |
| 95 | static __inline__ void bm0_set(UWord* bm0, const Addr a) |
| 96 | { |
| 97 | //tl_assert(a < ADDR0_COUNT); |
| 98 | bm0[a >> BITS_PER_BITS_PER_UWORD] |= 1UL << UWORD_LSB(a); |
| 99 | } |
| 100 | |
| 101 | static __inline__ void bm0_clear(UWord* bm0, const Addr a) |
| 102 | { |
| 103 | //tl_assert(a < ADDR0_COUNT); |
| 104 | bm0[a >> BITS_PER_BITS_PER_UWORD] &= ~(1UL << UWORD_LSB(a)); |
| 105 | } |
| 106 | |
| 107 | static __inline__ UWord bm0_is_set(const UWord* bm0, const Addr a) |
| 108 | { |
| 109 | //tl_assert(a < ADDR0_COUNT); |
| 110 | return (bm0[a >> BITS_PER_BITS_PER_UWORD] & (1UL << UWORD_LSB(a))); |
| 111 | } |
| 112 | |
| 113 | |
| 114 | struct bitmap2 |
| 115 | { |
| 116 | Addr addr; ///< address >> ADDR0_BITS |
| 117 | struct bitmap1 bm1; |
| 118 | }; |
| 119 | |
| 120 | /* Complete bitmap. */ |
| 121 | struct bitmap |
| 122 | { |
| 123 | OSet* oset; |
| 124 | }; |
| 125 | |
| 126 | static __inline__ |
| 127 | struct bitmap2* bm_lookup(const struct bitmap* const bm, const Addr a) |
| 128 | { |
| 129 | const UWord a1 = a >> ADDR0_BITS; |
sewardj | 8564292 | 2008-01-14 11:54:56 +0000 | [diff] [blame] | 130 | return VG_(OSetGen_Lookup)(bm->oset, &a1); |
sewardj | af44c82 | 2007-11-25 14:01:38 +0000 | [diff] [blame] | 131 | } |
| 132 | |
| 133 | static __inline__ |
| 134 | struct bitmap2* bm2_insert(const struct bitmap* const bm, |
| 135 | const UWord a1) |
| 136 | { |
| 137 | struct bitmap2* const node = VG_(OSetGen_AllocNode)(bm->oset, sizeof(*node)); |
| 138 | node->addr = a1; |
| 139 | VG_(memset)(&node->bm1, 0, sizeof(node->bm1)); |
| 140 | VG_(OSetGen_Insert)(bm->oset, node); |
| 141 | |
| 142 | s_bitmap2_creation_count++; |
| 143 | |
| 144 | return node; |
| 145 | } |
| 146 | |
| 147 | static __inline__ |
| 148 | struct bitmap2* bm2_lookup_or_insert(const struct bitmap* const bm, |
| 149 | const UWord a1) |
| 150 | { |
sewardj | 8564292 | 2008-01-14 11:54:56 +0000 | [diff] [blame] | 151 | struct bitmap2* p2 = VG_(OSetGen_Lookup)(bm->oset, &a1); |
sewardj | af44c82 | 2007-11-25 14:01:38 +0000 | [diff] [blame] | 152 | if (p2 == 0) |
| 153 | { |
| 154 | p2 = bm2_insert(bm, a1); |
| 155 | } |
| 156 | return p2; |
| 157 | } |
| 158 | |
| 159 | |
| 160 | #endif /* __DRD_BITMAP3_H */ |