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