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