l4/pkg/valgrind/src/valgrind-3.6.0-svn/drd/tests/unit_bitmap.c

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