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