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