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