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 } 361
