main.cpp revision f0b2c68c83e6ced8f988f014bc235393ca231958
1/* 2** Copyright 2013 The Android Open Source Project 3** 4** Licensed under the Apache License, Version 2.0 (the "License"); 5** you may not use this file except in compliance with the License. 6** You may obtain a copy of the License at 7** 8** http://www.apache.org/licenses/LICENSE-2.0 9** 10** Unless required by applicable law or agreed to in writing, software 11** distributed under the License is distributed on an "AS IS" BASIS, 12** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13** See the License for the specific language governing permissions and 14** limitations under the License. 15*/ 16 17#include <stdio.h> 18#include <stdlib.h> 19#include <unistd.h> 20#include <sys/mman.h> 21 22// Put any local test functions into the extern below. 23extern "C" { 24} 25 26#define FENCEPOST_LENGTH 8 27 28#define MAX_MEMCPY_TEST_SIZE 2048 29#define MAX_MEMCPY_BUFFER_SIZE (3 * MAX_MEMCPY_TEST_SIZE) 30 31#define MAX_MEMSET_TEST_SIZE 2048 32#define MAX_MEMSET_BUFFER_SIZE (3 * MAX_MEMSET_TEST_SIZE) 33 34#define MAX_STRCMP_TEST_SIZE 1024 35#define MAX_STRCMP_BUFFER_SIZE (3 * MAX_STRCMP_TEST_SIZE) 36 37// Return a pointer into the current string with the specified alignment. 38void *getAlignedPtr(void *orig_ptr, int alignment, int or_mask) { 39 uint64_t ptr = reinterpret_cast<uint64_t>(orig_ptr); 40 if (alignment > 0) { 41 // When setting the alignment, set it to exactly the alignment chosen. 42 // The pointer returned will be guaranteed not to be aligned to anything 43 // more than that. 44 ptr += alignment - (ptr & (alignment - 1)); 45 ptr |= alignment | or_mask; 46 } 47 48 return reinterpret_cast<void*>(ptr); 49} 50 51void setFencepost(uint8_t *buffer) { 52 for (int i = 0; i < FENCEPOST_LENGTH; i += 2) { 53 buffer[i] = 0xde; 54 buffer[i+1] = 0xad; 55 } 56} 57 58bool verifyFencepost(uint8_t *buffer) { 59 for (int i = 0; i < FENCEPOST_LENGTH; i += 2) { 60 if (buffer[i] != 0xde || buffer[i+1] != 0xad) { 61 uint8_t expected_value; 62 if (buffer[i] == 0xde) { 63 i++; 64 expected_value = 0xad; 65 } else { 66 expected_value = 0xde; 67 } 68 printf(" mismatch at fencepost[%d], expected %d found %d\n", 69 i, expected_value, buffer[i]); 70 return false; 71 } 72 } 73 return true; 74} 75 76bool doStrcmpExpectEqual(char *string1, char *string2, int align[4], 77 int (*test_strcmp)(const char *s1, const char *s2), 78 bool verbose) { 79 char *align_str1 = (char*)getAlignedPtr(string1, align[0], align[1]); 80 char *align_str2 = (char*)getAlignedPtr(string2, align[2], align[3]); 81 82 for (size_t i = 0; i < MAX_STRCMP_TEST_SIZE; i++) { 83 for (size_t j = 0; j < i; j++) { 84 align_str1[j] = (char)(32 + (j % 96)); 85 align_str2[j] = align_str1[j]; 86 } 87 align_str1[i] = '\0'; 88 align_str2[i] = '\0'; 89 90 // Set the characters after the string terminates to different values 91 // to verify that the strcmp is not over checking. 92 for (size_t j = i+1; j < i+64; j++) { 93 align_str1[j] = (char)(32 + j); 94 align_str2[j] = (char)(40 + j); 95 } 96 97 if (verbose) { 98 printf("Testing size %d, align_str1=%p[%d,%d], align_str2=%p[%d,%d]\n", 99 i, align_str1, align[0], align[1], align_str2, align[2], align[3]); 100 } 101 102 if (test_strcmp(align_str1, align_str2) != 0) { 103 printf(" Failed at size %d, src1 %p, src2 %p\n", 104 i, align_str1, align_str2); 105 return false; 106 } 107 } 108 109 return true; 110} 111 112bool doStrcmpExpectDiff(char *string1, char *string2, int diff_align[2], 113 int align[4], char diff_char, 114 int (*test_strcmp)(const char *s1, const char *s2), 115 bool verbose) { 116 char *align_str1 = (char*)getAlignedPtr(string1, align[0], align[1]); 117 char *align_str2 = (char*)getAlignedPtr(string2, align[2], align[3]); 118 119 for (int i = 0; i < MAX_STRCMP_TEST_SIZE; i++) { 120 // Use valid ascii characters, no unprintables characters. 121 align_str1[i] = (char)(32 + (i % 96)); 122 if (align_str1[i] == diff_char) { 123 // Assumes that one less than the diff character is still a valid 124 // character. 125 align_str1[i] = diff_char-1; 126 } 127 align_str2[i] = align_str1[i]; 128 } 129 align_str1[MAX_STRCMP_TEST_SIZE] = '\0'; 130 align_str2[MAX_STRCMP_TEST_SIZE] = '\0'; 131 132 // Quick check to make sure that the strcmp knows that everything is 133 // equal. If it's so broken that it already thinks the strings are 134 // different, then there is no point running any of the other tests. 135 if (test_strcmp(align_str1, align_str2) != 0) { 136 printf(" strcmp is too broken to do difference testing.\n"); 137 return false; 138 } 139 140 // Get a pointer into the string at the specified alignment. 141 char *bad = (char*)getAlignedPtr(align_str1+MAX_STRCMP_TEST_SIZE/2, 142 diff_align[0], diff_align[1]); 143 144 char saved_char = bad[0]; 145 bad[0] = diff_char; 146 147 if (verbose) { 148 printf("Testing difference, align_str1=%p[%d,%d], align_str2=%p[%d,%d]\n", 149 align_str1, align[0], align[1], align_str2, align[2], align[3]); 150 } 151 if (test_strcmp(align_str1, align_str2) == 0) { 152 printf(" Did not miscompare at size %d, src1 %p, src2 %p, diff %p\n", 153 MAX_STRCMP_TEST_SIZE, align_str1, align_str2, bad); 154 return false; 155 } 156 bad[0] = saved_char; 157 158 // Re-verify that something hasn't gone horribly wrong. 159 if (test_strcmp(align_str1, align_str2) != 0) { 160 printf(" strcmp is too broken to do difference testing.\n"); 161 return false; 162 } 163 164 bad = (char*)getAlignedPtr(align_str2+MAX_STRCMP_TEST_SIZE/2, diff_align[0], 165 diff_align[1]); 166 bad[0] = diff_char; 167 168 if (verbose) { 169 printf("Testing reverse difference, align_str1=%p[%d,%d], align_str2=%p[%d,%d]\n", 170 align_str1, align[0], align[1], align_str2, align[2], align[3]); 171 } 172 if (test_strcmp(align_str1, align_str2) == 0) { 173 printf(" Did not miscompare at size %d, src1 %p, src2 %p, diff %p\n", 174 MAX_STRCMP_TEST_SIZE, align_str1, align_str2, bad); 175 return false; 176 } 177 178 return true; 179} 180 181bool doStrcmpCheckRead(int (*test_strcmp)(const char *s1, const char *s2), 182 bool verbose) { 183 // In order to verify that the strcmp is not reading past the end of the 184 // string, create some strings that end near unreadable memory. 185 long pagesize = sysconf(_SC_PAGE_SIZE); 186 char *memory = (char*)memalign(pagesize, 2 * pagesize); 187 if (memory == NULL) { 188 perror("Unable to allocate memory.\n"); 189 return false; 190 } 191 192 // Make the second page unreadable and unwritable. 193 if (mprotect(&memory[pagesize], pagesize, PROT_NONE) != 0) { 194 perror("Unable to set protection of page.\n"); 195 return false; 196 } 197 198 size_t max_size = pagesize < MAX_STRCMP_TEST_SIZE ? pagesize-1 : MAX_STRCMP_TEST_SIZE; 199 // Allocate an extra byte beyond the string terminator to allow us to 200 // extend the string to be larger than our protected string. 201 char *other_string = (char *)malloc(max_size+2); 202 if (other_string == NULL) { 203 perror("Unable to allocate memory.\n"); 204 return false; 205 } 206 char *string; 207 for (size_t i = 0; i <= max_size; i++) { 208 string = &memory[pagesize-i-1]; 209 for (size_t j = 0; j < i; j++) { 210 other_string[j] = (char)(32 + (j % 96)); 211 string[j] = other_string[j]; 212 } 213 other_string[i] = '\0'; 214 string[i] = '\0'; 215 216 if (verbose) { 217 printf("Testing size %d, strings equal.\n", i); 218 } 219 if (test_strcmp(other_string, string) != 0) { 220 printf(" Failed at size %d, src1 %p, src2 %p\n", i, other_string, string); 221 return false; 222 } 223 224 if (verbose) { 225 printf("Testing size %d, strings equal reverse strings.\n", i); 226 } 227 if (test_strcmp(string, other_string) != 0) { 228 printf(" Failed at size %d, src1 %p, src2 %p\n", i, string, other_string); 229 return false; 230 } 231 232 // Now make other_string longer than our protected string. 233 other_string[i] = '1'; 234 other_string[i+1] = '\0'; 235 236 if (verbose) { 237 printf("Testing size %d, strings not equal.\n", i); 238 } 239 if (test_strcmp(other_string, string) == 0) { 240 printf(" Failed at size %d, src1 %p, src2 %p\n", i, other_string, string); 241 return false; 242 } 243 244 if (verbose) { 245 printf("Testing size %d, strings not equal reverse the strings.\n", i); 246 } 247 if (test_strcmp(string, other_string) == 0) { 248 printf(" Failed at size %d, src1 %p, src2 %p\n", i, string, other_string); 249 return false; 250 } 251 } 252 return true; 253} 254 255bool runStrcmpTest(int (*test_strcmp)(const char *s1, const char *s2), 256 bool verbose) { 257 // Allocate two large buffers to hold the two strings. 258 char *string1 = reinterpret_cast<char*>(malloc(MAX_STRCMP_BUFFER_SIZE+1)); 259 char *string2 = reinterpret_cast<char*>(malloc(MAX_STRCMP_BUFFER_SIZE+1)); 260 if (string1 == NULL || string2 == NULL) { 261 perror("Unable to allocate memory.\n"); 262 return false; 263 } 264 265 // Initialize the strings to be exactly the same. 266 for (int i = 0; i < MAX_STRCMP_BUFFER_SIZE; i++) { 267 string1[i] = (char)(32 + (i % 96)); 268 string2[i] = string1[i]; 269 } 270 string1[MAX_STRCMP_BUFFER_SIZE] = '\0'; 271 string2[MAX_STRCMP_BUFFER_SIZE] = '\0'; 272 273 // Check different string alignments. All zeroes indicates that the 274 // unmodified malloc values should be used. 275 int string_aligns[][4] = { 276 // All zeroes to use the values returned from malloc. 277 { 0, 0, 0, 0 }, 278 279 { 1, 0, 1, 0 }, 280 { 2, 0, 2, 0 }, 281 { 4, 0, 4, 0 }, 282 { 8, 0, 8, 0 }, 283 284 { 8, 0, 4, 0 }, 285 { 4, 0, 8, 0 }, 286 287 { 8, 0, 8, 1 }, 288 { 8, 0, 8, 2 }, 289 { 8, 0, 8, 3 }, 290 { 8, 1, 8, 0 }, 291 { 8, 2, 8, 0 }, 292 { 8, 3, 8, 0 }, 293 294 { 4, 0, 4, 1 }, 295 { 4, 0, 4, 2 }, 296 { 4, 0, 4, 3 }, 297 { 4, 1, 4, 0 }, 298 { 4, 2, 4, 0 }, 299 { 4, 3, 4, 0 }, 300 }; 301 302 printf(" Verifying equal sized strings at different alignments.\n"); 303 for (size_t i = 0; i < sizeof(string_aligns)/sizeof(int[4]); i++) { 304 if (!doStrcmpExpectEqual(string1, string2, string_aligns[i], test_strcmp, 305 verbose)) { 306 return false; 307 } 308 } 309 310 // Test the function finds strings with differences at specific locations. 311 int diff_aligns[][2] = { 312 { 4, 0 }, 313 { 4, 1 }, 314 { 4, 2 }, 315 { 4, 3 }, 316 { 8, 0 }, 317 { 8, 1 }, 318 { 8, 2 }, 319 { 8, 3 }, 320 }; 321 printf(" Verifying different strings at different alignments.\n"); 322 for (size_t i = 0; i < sizeof(diff_aligns)/sizeof(int[2]); i++) { 323 // First loop put the string terminator at the chosen alignment. 324 for (size_t j = 0; j < sizeof(string_aligns)/sizeof(int[4]); j++) { 325 if (!doStrcmpExpectDiff(string1, string2, diff_aligns[i], 326 string_aligns[j], '\0', test_strcmp, verbose)) { 327 return false; 328 } 329 } 330 // Second loop put a different character at the chosen alignment. 331 // This character is guaranteed not to be in the original string. 332 for (size_t j = 0; j < sizeof(string_aligns)/sizeof(int[4]); j++) { 333 if (!doStrcmpExpectDiff(string1, string2, diff_aligns[i], 334 string_aligns[j], '\0', test_strcmp, verbose)) { 335 return false; 336 } 337 } 338 } 339 340 printf(" Verifying strcmp does not read too many bytes.\n"); 341 if (!doStrcmpCheckRead(test_strcmp, verbose)) { 342 return false; 343 } 344 345 printf(" All tests pass.\n"); 346 347 return true; 348} 349 350bool runMemcpyTest(void* (*test_memcpy)(void *dst, const void *src, size_t n), 351 bool verbose) { 352 // Allocate two large buffers to hold the dst and src. 353 uint8_t *dst = reinterpret_cast<uint8_t*>(malloc(MAX_MEMCPY_BUFFER_SIZE)); 354 uint8_t *src = reinterpret_cast<uint8_t*>(malloc(MAX_MEMCPY_BUFFER_SIZE)); 355 if (dst == NULL || src == NULL) { 356 perror("Unable to allocate memory.\n"); 357 return false; 358 } 359 360 // Set the source to a known pattern once. The assumption is that the 361 // memcpy is not so broken that it will write in to the source buffer. 362 // However, do not write zeroes into the source so a very quick can be 363 // made to verify the source has not been modified. 364 for (int i = 0; i < MAX_MEMCPY_BUFFER_SIZE; i++) { 365 src[i] = i % 256; 366 if (src[i] == 0) { 367 src[i] = 0xaa; 368 } 369 } 370 371 int aligns[][4] = { 372 // Src and dst use pointers returned by malloc. 373 { 0, 0, 0, 0 }, 374 375 // Src and dst at same alignment. 376 { 1, 0, 1, 0 }, 377 { 2, 0, 2, 0 }, 378 { 4, 0, 4, 0 }, 379 { 8, 0, 8, 0 }, 380 { 16, 0, 16, 0 }, 381 { 32, 0, 32, 0 }, 382 { 64, 0, 64, 0 }, 383 { 128, 0, 128, 0 }, 384 385 // Different alignments between src and dst. 386 { 8, 0, 4, 0 }, 387 { 4, 0, 8, 0 }, 388 { 16, 0, 4, 0 }, 389 { 4, 0, 16, 0 }, 390 391 // General unaligned cases. 392 { 4, 0, 4, 1 }, 393 { 4, 0, 4, 2 }, 394 { 4, 0, 4, 3 }, 395 { 4, 1, 4, 0 }, 396 { 4, 2, 4, 0 }, 397 { 4, 3, 4, 0 }, 398 399 // All non-word aligned cases. 400 { 4, 1, 4, 0 }, 401 { 4, 1, 4, 1 }, 402 { 4, 1, 4, 2 }, 403 { 4, 1, 4, 3 }, 404 405 { 4, 2, 4, 0 }, 406 { 4, 2, 4, 1 }, 407 { 4, 2, 4, 2 }, 408 { 4, 2, 4, 3 }, 409 410 { 4, 3, 4, 0 }, 411 { 4, 3, 4, 1 }, 412 { 4, 3, 4, 2 }, 413 { 4, 3, 4, 3 }, 414 415 { 2, 0, 4, 0 }, 416 { 4, 0, 2, 0 }, 417 { 2, 0, 2, 0 }, 418 419 // Invoke the unaligned case where the code needs to align dst to 0x10. 420 { 128, 1, 128, 4 }, 421 { 128, 1, 128, 8 }, 422 { 128, 1, 128, 12 }, 423 { 128, 1, 128, 16 }, 424 }; 425 426 printf(" Verifying variable sized copies at different alignments.\n"); 427 uint8_t *src_align, *dst_align; 428 for (size_t i = 0; i < sizeof(aligns)/sizeof(int[4]); i++) { 429 for (size_t len = 0; len <= MAX_MEMCPY_TEST_SIZE; len++) { 430 if (aligns[i][0]) { 431 src_align = (uint8_t*)getAlignedPtr(src+FENCEPOST_LENGTH, aligns[i][0], 432 aligns[i][1]); 433 dst_align = (uint8_t*)getAlignedPtr(dst+FENCEPOST_LENGTH, aligns[i][2], 434 aligns[i][3]); 435 } else { 436 src_align = src; 437 dst_align = dst; 438 } 439 440 if (verbose) { 441 printf("Testing size %d, src_align=%p[%d,%d], dst_align=%p[%d,%d]\n", 442 len, src_align, aligns[i][0], aligns[i][1], 443 dst_align, aligns[i][2], aligns[i][3]); 444 } 445 446 memset(dst_align, 0, len); 447 448 // Don't add a pre fencepost if we are using the value from the malloc. 449 if (dst_align != dst) { 450 setFencepost(&dst_align[-FENCEPOST_LENGTH]); 451 } 452 setFencepost(&dst_align[len]); 453 454 test_memcpy(dst_align, src_align, len); 455 456 for (size_t j = 0; j < len; j++) { 457 if (dst_align[j] != src_align[j] || !src_align[j]) { 458 if (!src_align[j]) { 459 printf(" src_align[%d] is 0, memcpy wrote into the source.\n", j); 460 } else { 461 printf(" mismatch at %d, expected %d found %d\n", j, 462 src_align[j], dst_align[j]); 463 } 464 printf(" Failed at size %d, src_align=%p[%d,%d], dst_align=%p[%d,%d]\n", 465 len, src_align, aligns[i][0], aligns[i][1], 466 dst_align, aligns[i][2], aligns[i][3]); 467 return false; 468 } 469 } 470 if (dst_align != dst && !verifyFencepost(&dst_align[-8])) { 471 printf(" wrote before the array.\n"); 472 printf(" Failed at size %d, src_align=%p[%d,%d], dst_align=%p[%d,%d]\n", 473 len, src_align, aligns[i][0], aligns[i][1], 474 dst_align, aligns[i][2], aligns[i][3]); 475 return false; 476 } 477 if (!verifyFencepost(&dst_align[len])) { 478 printf(" wrote past the end of the array.\n"); 479 printf(" Failed at size %d, src_align=%p[%d,%d], dst_align=%p[%d,%d]\n", 480 len, src_align, aligns[i][0], aligns[i][1], 481 dst_align, aligns[i][2], aligns[i][3]); 482 return false; 483 } 484 } 485 } 486 487 printf(" All tests pass.\n"); 488 489 return true; 490} 491 492bool runMemsetTest(void* (*test_memset)(void *s, int c, size_t n), 493 bool verbose) { 494 // Allocate one large buffer to hold the dst. 495 uint8_t *buf = reinterpret_cast<uint8_t*>(malloc(MAX_MEMSET_BUFFER_SIZE)); 496 if (buf == NULL) { 497 perror("Unable to allocate memory.\n"); 498 return false; 499 } 500 501 int aligns[][2] = { 502 // Use malloc return values unaltered. 503 { 0, 0 }, 504 505 // Different alignments. 506 { 1, 0 }, 507 { 2, 0 }, 508 { 4, 0 }, 509 { 8, 0 }, 510 { 16, 0 }, 511 { 32, 0 }, 512 { 64, 0 }, 513 514 // Different alignments between src and dst. 515 { 8, 1 }, 516 { 8, 2 }, 517 { 8, 3 }, 518 { 8, 4 }, 519 { 8, 5 }, 520 { 8, 6 }, 521 { 8, 7 }, 522 }; 523 524 printf(" Verifying variable sized memsets at different alignments.\n"); 525 uint8_t *buf_align; 526 for (size_t i = 0; i < sizeof(aligns)/sizeof(int[2]); i++) { 527 for (size_t len = 0; len <= MAX_MEMSET_TEST_SIZE; len++) { 528 if (aligns[i]) { 529 buf_align = (uint8_t*)getAlignedPtr(buf+FENCEPOST_LENGTH, aligns[i][0], 530 aligns[i][1]); 531 } else { 532 buf_align = buf; 533 } 534 535 if (verbose) { 536 printf("Testing size %d, buf_align=%p[%d,%d]\n", 537 len, buf_align, aligns[i][0], aligns[i][1]); 538 } 539 540 // Set the buffer to all zero without memset since it might be the 541 // function we are testing. 542 for (size_t j = 0; j < len; j++) { 543 buf_align[j] = 0; 544 } 545 546 // Don't add a pre fencepost if we are using the value from the malloc. 547 if (buf_align != buf) { 548 setFencepost(&buf_align[-FENCEPOST_LENGTH]); 549 } 550 setFencepost(&buf_align[len]); 551 552 int value = (len % 255) + 1; 553 test_memset(buf_align, value, len); 554 555 for (size_t j = 0; j < len; j++) { 556 if (buf_align[j] != value) { 557 printf(" Failed at size %d[%d,%d!=%d], buf_align=%p[%d,%d]\n", 558 len, j, buf_align[j], value, buf_align, aligns[i][0], 559 aligns[i][1]); 560 return false; 561 } 562 } 563 if (buf_align != buf && !verifyFencepost(&buf_align[-8])) { 564 printf(" wrote before the beginning of the array.\n"); 565 printf(" Failed at size %d, buf_align=%p[%d,%d]\n", 566 len, buf_align, aligns[i][0], aligns[i][1]); 567 return false; 568 } 569 if (!verifyFencepost(&buf_align[len])) { 570 printf(" wrote after the end of the array.\n"); 571 printf(" Failed at size %d, buf_align=%p[%d,%d]\n", 572 len, buf_align, aligns[i][0], aligns[i][1]); 573 return false; 574 } 575 } 576 } 577 578 printf(" All tests pass.\n"); 579 580 return true; 581} 582 583int main(int argc, char **argv) { 584 bool verbose = false; 585 if (argc == 2 && strcmp(argv[1], "-v") == 0) { 586 verbose = true; 587 } 588 589 bool tests_passing = true; 590 printf("Testing strcmp...\n"); 591 tests_passing = runStrcmpTest(strcmp, verbose) && tests_passing; 592 593 printf("Testing memcpy...\n"); 594 tests_passing = runMemcpyTest(memcpy, verbose) && tests_passing; 595 596 printf("Testing memset...\n"); 597 tests_passing = runMemsetTest(memset, verbose) && tests_passing; 598 599 return (tests_passing ? 0 : 1); 600} 601