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
27void* VG_(malloc)(const HChar* cc, SizeT nbytes)
28{ return malloc(nbytes); }
29void  VG_(free)(void* p)
30{ return free(p); }
31void  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
47void* VG_(memset)(void *s, Int c, SizeT sz)
48{ return memset(s, c, sz); }
49void* VG_(memcpy)(void *d, const void *s, SizeT sz)
50{ return memcpy(d, s, sz); }
51void* VG_(memmove)(void *d, const void *s, SizeT sz)
52{ return memmove(d, s, sz); }
53Int VG_(memcmp)(const void* s1, const void* s2, SizeT n)
54{ return memcmp(s1, s2, n); }
55UInt VG_(printf)(const HChar *format, ...)
56{ UInt ret; va_list vargs; va_start(vargs, format); ret = vprintf(format, vargs); va_end(vargs); return ret; }
57UInt 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; }
59Bool DRD_(is_suppressed)(const Addr a1, const Addr a2)
60{ assert(0); }
61void VG_(vcbprintf)(void(*char_sink)(HChar, void* opaque),
62                    void* opaque,
63                    const HChar* format, va_list vargs)
64{ assert(0); }
65void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
66                 Int (*compar)(const void*, const void*) )
67{ assert(0); }
68
69/* Actual unit test */
70
71static int s_verbose = 1;
72
73static
74struct { 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 */
99int 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
129void 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. */
171void 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. */
193void 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
319int 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