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_ppc64be_linux) \
87 || defined(VGP_ppc64le_linux)
88 { 0xffffffffULL - (1 << ADDR_LSB_BITS << ADDR_IGNORED_BITS),
89 1, eStore },
90 { 0xffffffffULL, 1, eStore },
91 { 0x100000000ULL, 1, eStore },
92 { -2ULL - (1 << ADDR_LSB_BITS << ADDR_IGNORED_BITS),
93 1, eStore },
94 #endif
95 };
96
97 /**
98 * Compare two bitmaps and if different, print the differences.
99 */
bm_equal_print_diffs(struct bitmap * bm1,struct bitmap * bm2)100 int bm_equal_print_diffs(struct bitmap* bm1, struct bitmap* bm2)
101 {
102 int equal;
103
104 equal = DRD_(bm_equal)(bm1, bm2);
105 if (s_verbose && ! equal)
106 {
107 unsigned i;
108
109 VG_(printf)("Bitmaps are different.\n");
110 for (i = 0; i < 0x10000; i++)
111 {
112 if (DRD_(bm_has_1)(bm1, i, eLoad) != DRD_(bm_has_1)(bm2, i, eLoad)
113 || DRD_(bm_has_1)(bm1, i, eStore) != DRD_(bm_has_1)(bm2, i, eStore))
114 {
115 printf("0x%x %c %c %c %c\n",
116 i,
117 DRD_(bm_has_1)(bm1, i, eLoad) ? 'R' : ' ',
118 DRD_(bm_has_1)(bm1, i, eStore) ? 'W' : ' ',
119 DRD_(bm_has_1)(bm2, i, eLoad) ? 'R' : ' ',
120 DRD_(bm_has_1)(bm2, i, eStore) ? 'W' : ' '
121 );
122 }
123 }
124 fflush(stdout);
125 }
126
127 return equal;
128 }
129
bm_test1(void)130 void bm_test1(void)
131 {
132 struct bitmap* bm;
133 struct bitmap* bm2;
134 unsigned i, j;
135
136 bm = DRD_(bm_new)();
137
138 for (i = 0; i < sizeof(s_test1_args)/sizeof(s_test1_args[0]); i++)
139 {
140 DRD_(bm_access_range)(bm,
141 s_test1_args[i].address,
142 s_test1_args[i].address + s_test1_args[i].size,
143 s_test1_args[i].access_type);
144 }
145
146 for (i = 0; i < sizeof(s_test1_args)/sizeof(s_test1_args[0]); i++)
147 {
148 for (j = 0;
149 first_address_with_higher_lsb(j) <= s_test1_args[i].size;
150 j = first_address_with_higher_lsb(j))
151 {
152 tl_assert(DRD_(bm_has_1)(bm,
153 s_test1_args[i].address + j,
154 s_test1_args[i].access_type));
155 }
156 }
157
158 bm2 = DRD_(bm_new)();
159 DRD_(bm_merge2)(bm2, bm);
160 DRD_(bm_merge2)(bm2, bm);
161 assert(bm_equal_print_diffs(bm2, bm));
162
163 if (s_verbose)
164 VG_(printf)("Deleting bitmap bm\n");
165 DRD_(bm_delete)(bm);
166 if (s_verbose)
167 VG_(printf)("Deleting bitmap bm2\n");
168 DRD_(bm_delete)(bm2);
169 }
170
171 /** Test whether bm_equal() works correctly. */
bm_test2()172 void bm_test2()
173 {
174 struct bitmap* bm1;
175 struct bitmap* bm2;
176
177 bm1 = DRD_(bm_new)();
178 bm2 = DRD_(bm_new)();
179 DRD_(bm_access_load_1)(bm1, 7);
180 DRD_(bm_access_load_1)(bm2, make_address(1, 0) + 7);
181 assert(! DRD_(bm_equal)(bm1, bm2));
182 assert(! DRD_(bm_equal)(bm2, bm1));
183 DRD_(bm_access_load_1)(bm2, 7);
184 assert(! DRD_(bm_equal)(bm1, bm2));
185 assert(! DRD_(bm_equal)(bm2, bm1));
186 DRD_(bm_access_store_1)(bm1, make_address(1, 0) + 7);
187 assert(! DRD_(bm_equal)(bm1, bm2));
188 assert(! DRD_(bm_equal)(bm2, bm1));
189 DRD_(bm_delete)(bm2);
190 DRD_(bm_delete)(bm1);
191 }
192
193 /** 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)194 void bm_test3(const int outer_loop_step, const int inner_loop_step)
195 {
196 unsigned i, j;
197 struct bitmap* bm1;
198 struct bitmap* bm2;
199
200 const Addr lb = make_address(2, 0) - 2 * BITS_PER_UWORD;
201 const Addr ub = make_address(2, 0) + 2 * BITS_PER_UWORD;
202
203 assert(outer_loop_step >= 1);
204 assert((outer_loop_step % ADDR_GRANULARITY) == 0);
205 assert(inner_loop_step >= 1);
206 assert((inner_loop_step % ADDR_GRANULARITY) == 0);
207
208 bm1 = DRD_(bm_new)();
209 bm2 = DRD_(bm_new)();
210 for (i = lb; i < ub; i += outer_loop_step)
211 {
212 for (j = i + ADDR_GRANULARITY; j < ub; j += inner_loop_step)
213 {
214 DRD_(bm_access_range_load)(bm1, i, j);
215 DRD_(bm_clear_load)(bm1, i, j);
216 assert(bm_equal_print_diffs(bm1, bm2));
217 DRD_(bm_access_load_1)(bm1, i);
218 DRD_(bm_clear_load)(bm1, i, i + MAX(1, ADDR_GRANULARITY));
219 assert(bm_equal_print_diffs(bm1, bm2));
220 DRD_(bm_access_load_2)(bm1, i);
221 DRD_(bm_clear_load)(bm1, i, i + MAX(2, ADDR_GRANULARITY));
222 assert(bm_equal_print_diffs(bm1, bm2));
223 DRD_(bm_access_load_4)(bm1, i);
224 DRD_(bm_clear_load)(bm1, i, i + MAX(4, ADDR_GRANULARITY));
225 assert(bm_equal_print_diffs(bm1, bm2));
226 DRD_(bm_access_load_8)(bm1, i);
227 DRD_(bm_clear_load)(bm1, i, i + MAX(8, ADDR_GRANULARITY));
228 assert(bm_equal_print_diffs(bm1, bm2));
229
230 DRD_(bm_access_range_store)(bm1, i, j);
231 DRD_(bm_clear_store)(bm1, i, j);
232 assert(bm_equal_print_diffs(bm1, bm2));
233 DRD_(bm_access_store_1)(bm1, i);
234 DRD_(bm_clear_store)(bm1, i, i + MAX(1, ADDR_GRANULARITY));
235 assert(bm_equal_print_diffs(bm1, bm2));
236 DRD_(bm_access_store_2)(bm1, i);
237 DRD_(bm_clear_store)(bm1, i, i + MAX(2, ADDR_GRANULARITY));
238 assert(bm_equal_print_diffs(bm1, bm2));
239 DRD_(bm_access_store_4)(bm1, i);
240 DRD_(bm_clear_store)(bm1, i, i + MAX(4, ADDR_GRANULARITY));
241 assert(bm_equal_print_diffs(bm1, bm2));
242 DRD_(bm_access_store_8)(bm1, i);
243 DRD_(bm_clear_store)(bm1, i, i + MAX(8, ADDR_GRANULARITY));
244 assert(bm_equal_print_diffs(bm1, bm2));
245
246 DRD_(bm_access_range_load)(bm1, i, j);
247 DRD_(bm_access_range_store)(bm1, i, j);
248 DRD_(bm_clear)(bm1, i, j);
249 assert(bm_equal_print_diffs(bm1, bm2));
250 DRD_(bm_access_load_1)(bm1, i);
251 DRD_(bm_access_store_1)(bm1, i);
252 DRD_(bm_clear)(bm1, i, i + MAX(1, ADDR_GRANULARITY));
253 assert(bm_equal_print_diffs(bm1, bm2));
254 DRD_(bm_access_load_2)(bm1, i);
255 DRD_(bm_access_store_2)(bm1, i);
256 DRD_(bm_clear)(bm1, i, i + MAX(2, ADDR_GRANULARITY));
257 assert(bm_equal_print_diffs(bm1, bm2));
258 DRD_(bm_access_load_4)(bm1, i);
259 DRD_(bm_access_store_4)(bm1, i);
260 DRD_(bm_clear)(bm1, i, i + MAX(4, ADDR_GRANULARITY));
261 assert(bm_equal_print_diffs(bm1, bm2));
262 DRD_(bm_access_load_8)(bm1, i);
263 DRD_(bm_access_store_8)(bm1, i);
264 DRD_(bm_clear)(bm1, i, i + MAX(8, ADDR_GRANULARITY));
265 assert(bm_equal_print_diffs(bm1, bm2));
266 }
267 }
268 DRD_(bm_access_range_load)(bm1, 0, make_address(2, 0) + 2 * BITS_PER_UWORD);
269 DRD_(bm_access_range_store)(bm1, 0, make_address(2, 0) + 2 * BITS_PER_UWORD);
270 DRD_(bm_access_range_load)(bm2, 0, make_address(2, 0) + 2 * BITS_PER_UWORD);
271 DRD_(bm_access_range_store)(bm2, 0, make_address(2, 0) + 2 * BITS_PER_UWORD);
272 for (i = make_address(1, 0) - 2 * BITS_PER_UWORD;
273 i < make_address(1, 0) + 2 * BITS_PER_UWORD;
274 i += outer_loop_step)
275 {
276 for (j = i + 1; j < ub; j += inner_loop_step)
277 {
278 DRD_(bm_clear_load)(bm1, i, j);
279 DRD_(bm_access_range_load)(bm1, i, j);
280 assert(bm_equal_print_diffs(bm1, bm2));
281 DRD_(bm_clear_load)(bm1, i, i+1);
282 DRD_(bm_access_load_1)(bm1, i);
283 assert(bm_equal_print_diffs(bm1, bm2));
284 DRD_(bm_clear_load)(bm1, i, i+2);
285 DRD_(bm_access_load_2)(bm1, i);
286 assert(bm_equal_print_diffs(bm1, bm2));
287 DRD_(bm_clear_load)(bm1, i, i+4);
288 DRD_(bm_access_load_4)(bm1, i);
289 assert(bm_equal_print_diffs(bm1, bm2));
290 DRD_(bm_clear_load)(bm1, i, i+8);
291 DRD_(bm_access_load_8)(bm1, i);
292 assert(bm_equal_print_diffs(bm1, bm2));
293
294 DRD_(bm_clear_store)(bm1, i, j);
295 DRD_(bm_access_range_store)(bm1, i, j);
296 assert(bm_equal_print_diffs(bm1, bm2));
297 DRD_(bm_clear_store)(bm1, i, i+1);
298 DRD_(bm_access_store_1)(bm1, i);
299 assert(bm_equal_print_diffs(bm1, bm2));
300 DRD_(bm_clear_store)(bm1, i, i+2);
301 DRD_(bm_access_store_2)(bm1, i);
302 assert(bm_equal_print_diffs(bm1, bm2));
303 DRD_(bm_clear_store)(bm1, i, i+4);
304 DRD_(bm_access_store_4)(bm1, i);
305 assert(bm_equal_print_diffs(bm1, bm2));
306 DRD_(bm_clear_store)(bm1, i, i+8);
307 DRD_(bm_access_store_8)(bm1, i);
308 assert(bm_equal_print_diffs(bm1, bm2));
309
310 DRD_(bm_clear)(bm1, i, j);
311 DRD_(bm_access_range_load)(bm1, i, j);
312 DRD_(bm_access_range_store)(bm1, i, j);
313 assert(bm_equal_print_diffs(bm1, bm2));
314 }
315 }
316 DRD_(bm_delete)(bm2);
317 DRD_(bm_delete)(bm1);
318 }
319
main(int argc,char ** argv)320 int main(int argc, char** argv)
321 {
322 int outer_loop_step = ADDR_GRANULARITY;
323 int inner_loop_step = ADDR_GRANULARITY;
324 int optchar;
325
326 while ((optchar = getopt(argc, argv, "s:t:q")) != EOF)
327 {
328 switch (optchar)
329 {
330 case 's':
331 outer_loop_step = atoi(optarg);
332 break;
333 case 't':
334 inner_loop_step = atoi(optarg);
335 break;
336 case 'q':
337 s_verbose = 0;
338 break;
339 default:
340 fprintf(stderr,
341 "Usage: %s [-s<outer_loop_step>] [-t<inner_loop_step>] [-q].\n",
342 argv[0]);
343 break;
344 }
345 }
346
347 fprintf(stderr, "Start of DRD BM unit test.\n");
348
349 DRD_(bm_module_init)();
350 bm_test1();
351 bm_test2();
352 bm_test3(outer_loop_step, inner_loop_step);
353 DRD_(bm_module_cleanup)();
354
355 fprintf(stderr, "End of DRD BM unit test.\n");
356
357 return 0;
358 }
359