1 /** @brief Unit-test for DRD's bitmap implementation. */
2
3
4 #include <assert.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <unistd.h>
9 #include "coregrind/m_oset.c"
10 #include "drd/drd_bitmap.c"
11 #include "drd/drd_bitmap2_node.c"
12 #include "drd/pub_drd_bitmap.h"
13
14
15 #ifndef MIN
16 #define MIN(x, y) ((x) < (y) ? (x) : (y))
17 #endif
18 #ifndef MAX
19 #define MAX(x, y) ((x) > (y) ? (x) : (y))
20 #endif
21
22
23 /* Replacements for Valgrind core functionality. */
24
VG_(malloc)25 void* VG_(malloc)(HChar* cc, SizeT nbytes)
26 { return malloc(nbytes); }
VG_(free)27 void VG_(free)(void* p)
28 { return free(p); }
VG_(assert_fail)29 void VG_(assert_fail)(Bool isCore, const Char* assertion, const Char* file,
30 Int line, const Char* function, const HChar* format,
31 ...)
32 {
33 fprintf(stderr,
34 "%s:%u: %s%sAssertion `%s' failed.\n",
35 file,
36 line,
37 function ? (char*)function : "",
38 function ? ": " : "",
39 assertion);
40 fflush(stdout);
41 fflush(stderr);
42 abort();
43 }
44
VG_(memset)45 void* VG_(memset)(void *s, Int c, SizeT sz)
46 { return memset(s, c, sz); }
VG_(memcpy)47 void* VG_(memcpy)(void *d, const void *s, SizeT sz)
48 { return memcpy(d, s, sz); }
VG_(memcmp)49 Int VG_(memcmp)(const void* s1, const void* s2, SizeT n)
50 { return memcmp(s1, s2, n); }
VG_(printf)51 UInt VG_(printf)(const HChar *format, ...)
52 { UInt ret; va_list vargs; va_start(vargs, format); ret = vprintf(format, vargs); va_end(vargs); return ret; }
VG_(message)53 UInt VG_(message)(VgMsgKind kind, const HChar* format, ...)
54 { UInt ret; va_list vargs; va_start(vargs, format); ret = vprintf(format, vargs); va_end(vargs); printf("\n"); return ret; }
DRD_(is_suppressed)55 Bool DRD_(is_suppressed)(const Addr a1, const Addr a2)
56 { assert(0); }
57
58
59 /* Actual unit test */
60
61 static int s_verbose = 1;
62
63 static
64 struct { Addr address; SizeT size; BmAccessTypeT access_type; }
65 s_test1_args[] = {
66 { 0, 0, eLoad },
67 { 0, 1, eLoad },
68 { 666, 4, eLoad },
69 { 667, 2, eStore },
70 { 1024, 1, eStore },
71 { 0xffffULL, 1, eStore },
72 { 0x0001ffffULL, 1, eLoad },
73 { 0x00ffffffULL, 1, eLoad },
74 { 0xffffffffULL - (((1 << ADDR_LSB_BITS) + 1) << ADDR_IGNORED_BITS),
75 1, eStore },
76 #if defined(VGP_amd64_linux) || defined(VGP_ppc64_linux)
77 { 0xffffffffULL - (1 << ADDR_LSB_BITS << ADDR_IGNORED_BITS),
78 1, eStore },
79 { 0xffffffffULL, 1, eStore },
80 { 0x100000000ULL, 1, eStore },
81 { -2ULL - (1 << ADDR_LSB_BITS << ADDR_IGNORED_BITS),
82 1, eStore },
83 #endif
84 };
85
86 /**
87 * Compare two bitmaps and if different, print the differences.
88 */
bm_equal_print_diffs(struct bitmap * bm1,struct bitmap * bm2)89 int bm_equal_print_diffs(struct bitmap* bm1, struct bitmap* bm2)
90 {
91 int equal;
92
93 equal = DRD_(bm_equal)(bm1, bm2);
94 if (s_verbose && ! equal)
95 {
96 unsigned i;
97
98 VG_(printf)("Bitmaps are different.\n");
99 for (i = 0; i < 0x10000; i++)
100 {
101 if (DRD_(bm_has_1)(bm1, i, eLoad) != DRD_(bm_has_1)(bm2, i, eLoad)
102 || DRD_(bm_has_1)(bm1, i, eStore) != DRD_(bm_has_1)(bm2, i, eStore))
103 {
104 printf("0x%x %c %c %c %c\n",
105 i,
106 DRD_(bm_has_1)(bm1, i, eLoad) ? 'R' : ' ',
107 DRD_(bm_has_1)(bm1, i, eStore) ? 'W' : ' ',
108 DRD_(bm_has_1)(bm2, i, eLoad) ? 'R' : ' ',
109 DRD_(bm_has_1)(bm2, i, eStore) ? 'W' : ' '
110 );
111 }
112 }
113 fflush(stdout);
114 }
115
116 return equal;
117 }
118
bm_test1(void)119 void bm_test1(void)
120 {
121 struct bitmap* bm;
122 struct bitmap* bm2;
123 unsigned i, j;
124
125 bm = DRD_(bm_new)();
126
127 for (i = 0; i < sizeof(s_test1_args)/sizeof(s_test1_args[0]); i++)
128 {
129 DRD_(bm_access_range)(bm,
130 s_test1_args[i].address,
131 s_test1_args[i].address + s_test1_args[i].size,
132 s_test1_args[i].access_type);
133 }
134
135 for (i = 0; i < sizeof(s_test1_args)/sizeof(s_test1_args[0]); i++)
136 {
137 for (j = 0;
138 first_address_with_higher_lsb(j) <= s_test1_args[i].size;
139 j = first_address_with_higher_lsb(j))
140 {
141 tl_assert(DRD_(bm_has_1)(bm,
142 s_test1_args[i].address + j,
143 s_test1_args[i].access_type));
144 }
145 }
146
147 bm2 = DRD_(bm_new)();
148 DRD_(bm_merge2)(bm2, bm);
149 DRD_(bm_merge2)(bm2, bm);
150 assert(bm_equal_print_diffs(bm2, bm));
151
152 if (s_verbose)
153 VG_(printf)("Deleting bitmap bm\n");
154 DRD_(bm_delete)(bm);
155 if (s_verbose)
156 VG_(printf)("Deleting bitmap bm2\n");
157 DRD_(bm_delete)(bm2);
158 }
159
160 /** Test whether bm_equal() works correctly. */
bm_test2()161 void bm_test2()
162 {
163 struct bitmap* bm1;
164 struct bitmap* bm2;
165
166 bm1 = DRD_(bm_new)();
167 bm2 = DRD_(bm_new)();
168 DRD_(bm_access_load_1)(bm1, 7);
169 DRD_(bm_access_load_1)(bm2, make_address(1, 0) + 7);
170 assert(! DRD_(bm_equal)(bm1, bm2));
171 assert(! DRD_(bm_equal)(bm2, bm1));
172 DRD_(bm_access_load_1)(bm2, 7);
173 assert(! DRD_(bm_equal)(bm1, bm2));
174 assert(! DRD_(bm_equal)(bm2, bm1));
175 DRD_(bm_access_store_1)(bm1, make_address(1, 0) + 7);
176 assert(! DRD_(bm_equal)(bm1, bm2));
177 assert(! DRD_(bm_equal)(bm2, bm1));
178 DRD_(bm_delete)(bm2);
179 DRD_(bm_delete)(bm1);
180 }
181
182 /** Torture test of the functions that set or clear a range of bits. */
bm_test3(const int outer_loop_step,const int inner_loop_step)183 void bm_test3(const int outer_loop_step, const int inner_loop_step)
184 {
185 unsigned i, j;
186 struct bitmap* bm1;
187 struct bitmap* bm2;
188
189 const Addr lb = make_address(2, 0) - 2 * BITS_PER_UWORD;
190 const Addr ub = make_address(2, 0) + 2 * BITS_PER_UWORD;
191
192 assert(outer_loop_step >= 1);
193 assert((outer_loop_step % ADDR_GRANULARITY) == 0);
194 assert(inner_loop_step >= 1);
195 assert((inner_loop_step % ADDR_GRANULARITY) == 0);
196
197 bm1 = DRD_(bm_new)();
198 bm2 = DRD_(bm_new)();
199 for (i = lb; i < ub; i += outer_loop_step)
200 {
201 for (j = i + ADDR_GRANULARITY; j < ub; j += inner_loop_step)
202 {
203 DRD_(bm_access_range_load)(bm1, i, j);
204 DRD_(bm_clear_load)(bm1, i, j);
205 assert(bm_equal_print_diffs(bm1, bm2));
206 DRD_(bm_access_load_1)(bm1, i);
207 DRD_(bm_clear_load)(bm1, i, i + MAX(1, ADDR_GRANULARITY));
208 assert(bm_equal_print_diffs(bm1, bm2));
209 DRD_(bm_access_load_2)(bm1, i);
210 DRD_(bm_clear_load)(bm1, i, i + MAX(2, ADDR_GRANULARITY));
211 assert(bm_equal_print_diffs(bm1, bm2));
212 DRD_(bm_access_load_4)(bm1, i);
213 DRD_(bm_clear_load)(bm1, i, i + MAX(4, ADDR_GRANULARITY));
214 assert(bm_equal_print_diffs(bm1, bm2));
215 DRD_(bm_access_load_8)(bm1, i);
216 DRD_(bm_clear_load)(bm1, i, i + MAX(8, ADDR_GRANULARITY));
217 assert(bm_equal_print_diffs(bm1, bm2));
218
219 DRD_(bm_access_range_store)(bm1, i, j);
220 DRD_(bm_clear_store)(bm1, i, j);
221 assert(bm_equal_print_diffs(bm1, bm2));
222 DRD_(bm_access_store_1)(bm1, i);
223 DRD_(bm_clear_store)(bm1, i, i + MAX(1, ADDR_GRANULARITY));
224 assert(bm_equal_print_diffs(bm1, bm2));
225 DRD_(bm_access_store_2)(bm1, i);
226 DRD_(bm_clear_store)(bm1, i, i + MAX(2, ADDR_GRANULARITY));
227 assert(bm_equal_print_diffs(bm1, bm2));
228 DRD_(bm_access_store_4)(bm1, i);
229 DRD_(bm_clear_store)(bm1, i, i + MAX(4, ADDR_GRANULARITY));
230 assert(bm_equal_print_diffs(bm1, bm2));
231 DRD_(bm_access_store_8)(bm1, i);
232 DRD_(bm_clear_store)(bm1, i, i + MAX(8, ADDR_GRANULARITY));
233 assert(bm_equal_print_diffs(bm1, bm2));
234
235 DRD_(bm_access_range_load)(bm1, i, j);
236 DRD_(bm_access_range_store)(bm1, i, j);
237 DRD_(bm_clear)(bm1, i, j);
238 assert(bm_equal_print_diffs(bm1, bm2));
239 DRD_(bm_access_load_1)(bm1, i);
240 DRD_(bm_access_store_1)(bm1, i);
241 DRD_(bm_clear)(bm1, i, i + MAX(1, ADDR_GRANULARITY));
242 assert(bm_equal_print_diffs(bm1, bm2));
243 DRD_(bm_access_load_2)(bm1, i);
244 DRD_(bm_access_store_2)(bm1, i);
245 DRD_(bm_clear)(bm1, i, i + MAX(2, ADDR_GRANULARITY));
246 assert(bm_equal_print_diffs(bm1, bm2));
247 DRD_(bm_access_load_4)(bm1, i);
248 DRD_(bm_access_store_4)(bm1, i);
249 DRD_(bm_clear)(bm1, i, i + MAX(4, ADDR_GRANULARITY));
250 assert(bm_equal_print_diffs(bm1, bm2));
251 DRD_(bm_access_load_8)(bm1, i);
252 DRD_(bm_access_store_8)(bm1, i);
253 DRD_(bm_clear)(bm1, i, i + MAX(8, ADDR_GRANULARITY));
254 assert(bm_equal_print_diffs(bm1, bm2));
255 }
256 }
257 DRD_(bm_access_range_load)(bm1, 0, make_address(2, 0) + 2 * BITS_PER_UWORD);
258 DRD_(bm_access_range_store)(bm1, 0, make_address(2, 0) + 2 * BITS_PER_UWORD);
259 DRD_(bm_access_range_load)(bm2, 0, make_address(2, 0) + 2 * BITS_PER_UWORD);
260 DRD_(bm_access_range_store)(bm2, 0, make_address(2, 0) + 2 * BITS_PER_UWORD);
261 for (i = make_address(1, 0) - 2 * BITS_PER_UWORD;
262 i < make_address(1, 0) + 2 * BITS_PER_UWORD;
263 i += outer_loop_step)
264 {
265 for (j = i + 1; j < ub; j += inner_loop_step)
266 {
267 DRD_(bm_clear_load)(bm1, i, j);
268 DRD_(bm_access_range_load)(bm1, i, j);
269 assert(bm_equal_print_diffs(bm1, bm2));
270 DRD_(bm_clear_load)(bm1, i, i+1);
271 DRD_(bm_access_load_1)(bm1, i);
272 assert(bm_equal_print_diffs(bm1, bm2));
273 DRD_(bm_clear_load)(bm1, i, i+2);
274 DRD_(bm_access_load_2)(bm1, i);
275 assert(bm_equal_print_diffs(bm1, bm2));
276 DRD_(bm_clear_load)(bm1, i, i+4);
277 DRD_(bm_access_load_4)(bm1, i);
278 assert(bm_equal_print_diffs(bm1, bm2));
279 DRD_(bm_clear_load)(bm1, i, i+8);
280 DRD_(bm_access_load_8)(bm1, i);
281 assert(bm_equal_print_diffs(bm1, bm2));
282
283 DRD_(bm_clear_store)(bm1, i, j);
284 DRD_(bm_access_range_store)(bm1, i, j);
285 assert(bm_equal_print_diffs(bm1, bm2));
286 DRD_(bm_clear_store)(bm1, i, i+1);
287 DRD_(bm_access_store_1)(bm1, i);
288 assert(bm_equal_print_diffs(bm1, bm2));
289 DRD_(bm_clear_store)(bm1, i, i+2);
290 DRD_(bm_access_store_2)(bm1, i);
291 assert(bm_equal_print_diffs(bm1, bm2));
292 DRD_(bm_clear_store)(bm1, i, i+4);
293 DRD_(bm_access_store_4)(bm1, i);
294 assert(bm_equal_print_diffs(bm1, bm2));
295 DRD_(bm_clear_store)(bm1, i, i+8);
296 DRD_(bm_access_store_8)(bm1, i);
297 assert(bm_equal_print_diffs(bm1, bm2));
298
299 DRD_(bm_clear)(bm1, i, j);
300 DRD_(bm_access_range_load)(bm1, i, j);
301 DRD_(bm_access_range_store)(bm1, i, j);
302 assert(bm_equal_print_diffs(bm1, bm2));
303 }
304 }
305 DRD_(bm_delete)(bm2);
306 DRD_(bm_delete)(bm1);
307 }
308
main(int argc,char ** argv)309 int main(int argc, char** argv)
310 {
311 int outer_loop_step = ADDR_GRANULARITY;
312 int inner_loop_step = ADDR_GRANULARITY;
313 int optchar;
314
315 while ((optchar = getopt(argc, argv, "s:t:q")) != EOF)
316 {
317 switch (optchar)
318 {
319 case 's':
320 outer_loop_step = atoi(optarg);
321 break;
322 case 't':
323 inner_loop_step = atoi(optarg);
324 break;
325 case 'q':
326 s_verbose = 0;
327 break;
328 default:
329 fprintf(stderr,
330 "Usage: %s [-s<outer_loop_step>] [-t<inner_loop_step>] [-q].\n",
331 argv[0]);
332 break;
333 }
334 }
335
336 fprintf(stderr, "Start of DRD BM unit test.\n");
337
338 bm_test1();
339 bm_test2();
340 bm_test3(outer_loop_step, inner_loop_step);
341
342 fprintf(stderr, "End of DRD BM unit test.\n");
343
344 return 0;
345 }
346