• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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