blob: 7212ccfdac395b1c25d770a2fa9055a3be26b231 [file] [log] [blame]
sewardjaf44c822007-11-25 14:01:38 +00001/*
2 This file is part of drd, a data race detector.
3
sewardj85642922008-01-14 11:54:56 +00004 Copyright (C) 2006-2008 Bart Van Assche
sewardjaf44c822007-11-25 14:01:38 +00005 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
bart0268dfa2008-03-11 20:10:21 +000049#define SPLIT_ADDRESS(a) \
50 UWord a##0 = ((a) & ADDR0_MASK); \
sewardjaf44c822007-11-25 14:01:38 +000051 UWord a##1 = ((a) >> ADDR0_BITS);
52
53// Assumption: sizeof(Addr) == sizeof(UWord).
bart0268dfa2008-03-11 20:10:21 +000054#define MAKE_ADDRESS(a1, a0) \
sewardjaf44c822007-11-25 14:01:38 +000055 (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
sewardjaf44c822007-11-25 14:01:38 +000078// Local constants.
79
80static ULong s_bitmap2_creation_count;
81
82
83/* Lowest level, corresponding to the lowest ADDR0_BITS of an address. */
84struct bitmap1
85{
86 UWord bm0_r[BITMAP1_UWORD_COUNT];
87 UWord bm0_w[BITMAP1_UWORD_COUNT];
88};
89
90static __inline__ UWord bm0_mask(const Addr a)
91{
92 return (1UL << UWORD_LSB(a));
93}
94
95static __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
101static __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
107static __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
114struct bitmap2
115{
116 Addr addr; ///< address >> ADDR0_BITS
117 struct bitmap1 bm1;
118};
119
120/* Complete bitmap. */
121struct bitmap
122{
123 OSet* oset;
124};
125
126static __inline__
127struct bitmap2* bm_lookup(const struct bitmap* const bm, const Addr a)
128{
129 const UWord a1 = a >> ADDR0_BITS;
sewardj85642922008-01-14 11:54:56 +0000130 return VG_(OSetGen_Lookup)(bm->oset, &a1);
sewardjaf44c822007-11-25 14:01:38 +0000131}
132
133static __inline__
134struct 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
147static __inline__
148struct bitmap2* bm2_lookup_or_insert(const struct bitmap* const bm,
149 const UWord a1)
150{
sewardj85642922008-01-14 11:54:56 +0000151 struct bitmap2* p2 = VG_(OSetGen_Lookup)(bm->oset, &a1);
sewardjaf44c822007-11-25 14:01:38 +0000152 if (p2 == 0)
153 {
154 p2 = bm2_insert(bm, a1);
155 }
156 return p2;
157}
158
159
160#endif /* __DRD_BITMAP3_H */