unit_bitmap.c revision e739ac0589b4fb43561f801c4faba8c1b89f8680 
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
25void* VG_(malloc)(HChar* cc, SizeT nbytes)
26{ return malloc(nbytes); }
27void  VG_(free)(void* p)
28{ return free(p); }
29void  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
45void* VG_(memset)(void *s, Int c, SizeT sz)
46{ return memset(s, c, sz); }
47void* VG_(memcpy)(void *d, const void *s, SizeT sz)
48{ return memcpy(d, s, sz); }
49Int VG_(memcmp)(const void* s1, const void* s2, SizeT n)
50{ return memcmp(s1, s2, n); }
51UInt VG_(printf)(const HChar *format, ...)
52{ UInt ret; va_list vargs; va_start(vargs, format); ret = vprintf(format, vargs); va_end(vargs); return ret; }
53UInt 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; }
55Bool DRD_(is_suppressed)(const Addr a1, const Addr a2)
56{ assert(0); }
57
58
59/* Actual unit test */
60
61static int s_verbose = 1;
62
63static
64struct { 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) || defined(VGP_ppc64_aix5)
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 */
89int 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
119void 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. */
161void 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. */
183void 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
309int 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