1 // Copyright 2014 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <algorithm> // for min() 8 9 #include "base/atomicops.h" 10 #include "testing/gtest/include/gtest/gtest.h" 11 12 // Number of bits in a size_t. 13 static const int kSizeBits = 8 * sizeof(size_t); 14 // The maximum size of a size_t. 15 static const size_t kMaxSize = ~static_cast<size_t>(0); 16 // Maximum positive size of a size_t if it were signed. 17 static const size_t kMaxSignedSize = ((size_t(1) << (kSizeBits-1)) - 1); 18 // An allocation size which is not too big to be reasonable. 19 static const size_t kNotTooBig = 100000; 20 // An allocation size which is just too big. 21 static const size_t kTooBig = ~static_cast<size_t>(0); 22 23 namespace { 24 25 using std::min; 26 27 // Fill a buffer of the specified size with a predetermined pattern 28 static void Fill(unsigned char* buffer, int n) { 29 for (int i = 0; i < n; i++) { 30 buffer[i] = (i & 0xff); 31 } 32 } 33 34 // Check that the specified buffer has the predetermined pattern 35 // generated by Fill() 36 static bool Valid(unsigned char* buffer, int n) { 37 for (int i = 0; i < n; i++) { 38 if (buffer[i] != (i & 0xff)) { 39 return false; 40 } 41 } 42 return true; 43 } 44 45 // Check that a buffer is completely zeroed. 46 static bool IsZeroed(unsigned char* buffer, int n) { 47 for (int i = 0; i < n; i++) { 48 if (buffer[i] != 0) { 49 return false; 50 } 51 } 52 return true; 53 } 54 55 // Check alignment 56 static void CheckAlignment(void* p, int align) { 57 EXPECT_EQ(0, reinterpret_cast<uintptr_t>(p) & (align-1)); 58 } 59 60 // Return the next interesting size/delta to check. Returns -1 if no more. 61 static int NextSize(int size) { 62 if (size < 100) 63 return size+1; 64 65 if (size < 100000) { 66 // Find next power of two 67 int power = 1; 68 while (power < size) 69 power <<= 1; 70 71 // Yield (power-1, power, power+1) 72 if (size < power-1) 73 return power-1; 74 75 if (size == power-1) 76 return power; 77 78 assert(size == power); 79 return power+1; 80 } else { 81 return -1; 82 } 83 } 84 85 template <class AtomicType> 86 static void TestAtomicIncrement() { 87 // For now, we just test single threaded execution 88 89 // use a guard value to make sure the NoBarrier_AtomicIncrement doesn't go 90 // outside the expected address bounds. This is in particular to 91 // test that some future change to the asm code doesn't cause the 92 // 32-bit NoBarrier_AtomicIncrement to do the wrong thing on 64-bit machines. 93 struct { 94 AtomicType prev_word; 95 AtomicType count; 96 AtomicType next_word; 97 } s; 98 99 AtomicType prev_word_value, next_word_value; 100 memset(&prev_word_value, 0xFF, sizeof(AtomicType)); 101 memset(&next_word_value, 0xEE, sizeof(AtomicType)); 102 103 s.prev_word = prev_word_value; 104 s.count = 0; 105 s.next_word = next_word_value; 106 107 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, 1), 1); 108 EXPECT_EQ(s.count, 1); 109 EXPECT_EQ(s.prev_word, prev_word_value); 110 EXPECT_EQ(s.next_word, next_word_value); 111 112 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, 2), 3); 113 EXPECT_EQ(s.count, 3); 114 EXPECT_EQ(s.prev_word, prev_word_value); 115 EXPECT_EQ(s.next_word, next_word_value); 116 117 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, 3), 6); 118 EXPECT_EQ(s.count, 6); 119 EXPECT_EQ(s.prev_word, prev_word_value); 120 EXPECT_EQ(s.next_word, next_word_value); 121 122 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, -3), 3); 123 EXPECT_EQ(s.count, 3); 124 EXPECT_EQ(s.prev_word, prev_word_value); 125 EXPECT_EQ(s.next_word, next_word_value); 126 127 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, -2), 1); 128 EXPECT_EQ(s.count, 1); 129 EXPECT_EQ(s.prev_word, prev_word_value); 130 EXPECT_EQ(s.next_word, next_word_value); 131 132 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, -1), 0); 133 EXPECT_EQ(s.count, 0); 134 EXPECT_EQ(s.prev_word, prev_word_value); 135 EXPECT_EQ(s.next_word, next_word_value); 136 137 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, -1), -1); 138 EXPECT_EQ(s.count, -1); 139 EXPECT_EQ(s.prev_word, prev_word_value); 140 EXPECT_EQ(s.next_word, next_word_value); 141 142 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, -4), -5); 143 EXPECT_EQ(s.count, -5); 144 EXPECT_EQ(s.prev_word, prev_word_value); 145 EXPECT_EQ(s.next_word, next_word_value); 146 147 EXPECT_EQ(base::subtle::NoBarrier_AtomicIncrement(&s.count, 5), 0); 148 EXPECT_EQ(s.count, 0); 149 EXPECT_EQ(s.prev_word, prev_word_value); 150 EXPECT_EQ(s.next_word, next_word_value); 151 } 152 153 154 #define NUM_BITS(T) (sizeof(T) * 8) 155 156 157 template <class AtomicType> 158 static void TestCompareAndSwap() { 159 AtomicType value = 0; 160 AtomicType prev = base::subtle::NoBarrier_CompareAndSwap(&value, 0, 1); 161 EXPECT_EQ(1, value); 162 EXPECT_EQ(0, prev); 163 164 // Use test value that has non-zero bits in both halves, more for testing 165 // 64-bit implementation on 32-bit platforms. 166 const AtomicType k_test_val = (static_cast<uint64_t>(1) << 167 (NUM_BITS(AtomicType) - 2)) + 11; 168 value = k_test_val; 169 prev = base::subtle::NoBarrier_CompareAndSwap(&value, 0, 5); 170 EXPECT_EQ(k_test_val, value); 171 EXPECT_EQ(k_test_val, prev); 172 173 value = k_test_val; 174 prev = base::subtle::NoBarrier_CompareAndSwap(&value, k_test_val, 5); 175 EXPECT_EQ(5, value); 176 EXPECT_EQ(k_test_val, prev); 177 } 178 179 180 template <class AtomicType> 181 static void TestAtomicExchange() { 182 AtomicType value = 0; 183 AtomicType new_value = base::subtle::NoBarrier_AtomicExchange(&value, 1); 184 EXPECT_EQ(1, value); 185 EXPECT_EQ(0, new_value); 186 187 // Use test value that has non-zero bits in both halves, more for testing 188 // 64-bit implementation on 32-bit platforms. 189 const AtomicType k_test_val = (static_cast<uint64_t>(1) << 190 (NUM_BITS(AtomicType) - 2)) + 11; 191 value = k_test_val; 192 new_value = base::subtle::NoBarrier_AtomicExchange(&value, k_test_val); 193 EXPECT_EQ(k_test_val, value); 194 EXPECT_EQ(k_test_val, new_value); 195 196 value = k_test_val; 197 new_value = base::subtle::NoBarrier_AtomicExchange(&value, 5); 198 EXPECT_EQ(5, value); 199 EXPECT_EQ(k_test_val, new_value); 200 } 201 202 203 template <class AtomicType> 204 static void TestAtomicIncrementBounds() { 205 // Test increment at the half-width boundary of the atomic type. 206 // It is primarily for testing at the 32-bit boundary for 64-bit atomic type. 207 AtomicType test_val = static_cast<uint64_t>(1) << (NUM_BITS(AtomicType) / 2); 208 AtomicType value = test_val - 1; 209 AtomicType new_value = base::subtle::NoBarrier_AtomicIncrement(&value, 1); 210 EXPECT_EQ(test_val, value); 211 EXPECT_EQ(value, new_value); 212 213 base::subtle::NoBarrier_AtomicIncrement(&value, -1); 214 EXPECT_EQ(test_val - 1, value); 215 } 216 217 // This is a simple sanity check that values are correct. Not testing 218 // atomicity 219 template <class AtomicType> 220 static void TestStore() { 221 const AtomicType kVal1 = static_cast<AtomicType>(0xa5a5a5a5a5a5a5a5LL); 222 const AtomicType kVal2 = static_cast<AtomicType>(-1); 223 224 AtomicType value; 225 226 base::subtle::NoBarrier_Store(&value, kVal1); 227 EXPECT_EQ(kVal1, value); 228 base::subtle::NoBarrier_Store(&value, kVal2); 229 EXPECT_EQ(kVal2, value); 230 231 base::subtle::Acquire_Store(&value, kVal1); 232 EXPECT_EQ(kVal1, value); 233 base::subtle::Acquire_Store(&value, kVal2); 234 EXPECT_EQ(kVal2, value); 235 236 base::subtle::Release_Store(&value, kVal1); 237 EXPECT_EQ(kVal1, value); 238 base::subtle::Release_Store(&value, kVal2); 239 EXPECT_EQ(kVal2, value); 240 } 241 242 // This is a simple sanity check that values are correct. Not testing 243 // atomicity 244 template <class AtomicType> 245 static void TestLoad() { 246 const AtomicType kVal1 = static_cast<AtomicType>(0xa5a5a5a5a5a5a5a5LL); 247 const AtomicType kVal2 = static_cast<AtomicType>(-1); 248 249 AtomicType value; 250 251 value = kVal1; 252 EXPECT_EQ(kVal1, base::subtle::NoBarrier_Load(&value)); 253 value = kVal2; 254 EXPECT_EQ(kVal2, base::subtle::NoBarrier_Load(&value)); 255 256 value = kVal1; 257 EXPECT_EQ(kVal1, base::subtle::Acquire_Load(&value)); 258 value = kVal2; 259 EXPECT_EQ(kVal2, base::subtle::Acquire_Load(&value)); 260 261 value = kVal1; 262 EXPECT_EQ(kVal1, base::subtle::Release_Load(&value)); 263 value = kVal2; 264 EXPECT_EQ(kVal2, base::subtle::Release_Load(&value)); 265 } 266 267 template <class AtomicType> 268 static void TestAtomicOps() { 269 TestCompareAndSwap<AtomicType>(); 270 TestAtomicExchange<AtomicType>(); 271 TestAtomicIncrementBounds<AtomicType>(); 272 TestStore<AtomicType>(); 273 TestLoad<AtomicType>(); 274 } 275 276 static void TestCalloc(size_t n, size_t s, bool ok) { 277 char* p = reinterpret_cast<char*>(calloc(n, s)); 278 if (!ok) { 279 EXPECT_EQ(NULL, p) << "calloc(n, s) should not succeed"; 280 } else { 281 EXPECT_NE(reinterpret_cast<void*>(NULL), p) << 282 "calloc(n, s) should succeed"; 283 for (int i = 0; i < n*s; i++) { 284 EXPECT_EQ('\0', p[i]); 285 } 286 free(p); 287 } 288 } 289 290 // MSVC C4530 complains about exception handler usage when exceptions are 291 // disabled. Temporarily disable that warning so we can test that they are, in 292 // fact, disabled. 293 #if defined(OS_WIN) 294 #pragma warning(push) 295 #pragma warning(disable: 4530) 296 #endif 297 298 // A global test counter for number of times the NewHandler is called. 299 static int news_handled = 0; 300 static void TestNewHandler() { 301 ++news_handled; 302 throw std::bad_alloc(); 303 } 304 305 // Because we compile without exceptions, we expect these will not throw. 306 static void TestOneNewWithoutExceptions(void* (*func)(size_t), 307 bool should_throw) { 308 // success test 309 try { 310 void* ptr = (*func)(kNotTooBig); 311 EXPECT_NE(reinterpret_cast<void*>(NULL), ptr) << 312 "allocation should not have failed."; 313 } catch(...) { 314 EXPECT_EQ(0, 1) << "allocation threw unexpected exception."; 315 } 316 317 // failure test 318 try { 319 void* rv = (*func)(kTooBig); 320 EXPECT_EQ(NULL, rv); 321 EXPECT_FALSE(should_throw) << "allocation should have thrown."; 322 } catch(...) { 323 EXPECT_TRUE(should_throw) << "allocation threw unexpected exception."; 324 } 325 } 326 327 static void TestNothrowNew(void* (*func)(size_t)) { 328 news_handled = 0; 329 330 // test without new_handler: 331 std::new_handler saved_handler = std::set_new_handler(0); 332 TestOneNewWithoutExceptions(func, false); 333 334 // test with new_handler: 335 std::set_new_handler(TestNewHandler); 336 TestOneNewWithoutExceptions(func, true); 337 EXPECT_EQ(news_handled, 1) << "nothrow new_handler was not called."; 338 std::set_new_handler(saved_handler); 339 } 340 341 #if defined(OS_WIN) 342 #pragma warning(pop) 343 #endif 344 345 } // namespace 346 347 //----------------------------------------------------------------------------- 348 349 TEST(Atomics, AtomicIncrementWord) { 350 TestAtomicIncrement<AtomicWord>(); 351 } 352 353 TEST(Atomics, AtomicIncrement32) { 354 TestAtomicIncrement<Atomic32>(); 355 } 356 357 TEST(Atomics, AtomicOpsWord) { 358 TestAtomicIncrement<AtomicWord>(); 359 } 360 361 TEST(Atomics, AtomicOps32) { 362 TestAtomicIncrement<Atomic32>(); 363 } 364 365 TEST(Allocators, Malloc) { 366 // Try allocating data with a bunch of alignments and sizes 367 for (int size = 1; size < 1048576; size *= 2) { 368 unsigned char* ptr = reinterpret_cast<unsigned char*>(malloc(size)); 369 CheckAlignment(ptr, 2); // Should be 2 byte aligned 370 Fill(ptr, size); 371 EXPECT_TRUE(Valid(ptr, size)); 372 free(ptr); 373 } 374 } 375 376 TEST(Allocators, Calloc) { 377 TestCalloc(0, 0, true); 378 TestCalloc(0, 1, true); 379 TestCalloc(1, 1, true); 380 TestCalloc(1<<10, 0, true); 381 TestCalloc(1<<20, 0, true); 382 TestCalloc(0, 1<<10, true); 383 TestCalloc(0, 1<<20, true); 384 TestCalloc(1<<20, 2, true); 385 TestCalloc(2, 1<<20, true); 386 TestCalloc(1000, 1000, true); 387 388 TestCalloc(kMaxSize, 2, false); 389 TestCalloc(2, kMaxSize, false); 390 TestCalloc(kMaxSize, kMaxSize, false); 391 392 TestCalloc(kMaxSignedSize, 3, false); 393 TestCalloc(3, kMaxSignedSize, false); 394 TestCalloc(kMaxSignedSize, kMaxSignedSize, false); 395 } 396 397 TEST(Allocators, New) { 398 TestNothrowNew(&::operator new); 399 TestNothrowNew(&::operator new[]); 400 } 401 402 // This makes sure that reallocing a small number of bytes in either 403 // direction doesn't cause us to allocate new memory. 404 TEST(Allocators, Realloc1) { 405 int start_sizes[] = { 100, 1000, 10000, 100000 }; 406 int deltas[] = { 1, -2, 4, -8, 16, -32, 64, -128 }; 407 408 for (int s = 0; s < sizeof(start_sizes)/sizeof(*start_sizes); ++s) { 409 void* p = malloc(start_sizes[s]); 410 ASSERT_TRUE(p); 411 // The larger the start-size, the larger the non-reallocing delta. 412 for (int d = 0; d < s*2; ++d) { 413 void* new_p = realloc(p, start_sizes[s] + deltas[d]); 414 ASSERT_EQ(p, new_p); // realloc should not allocate new memory 415 } 416 // Test again, but this time reallocing smaller first. 417 for (int d = 0; d < s*2; ++d) { 418 void* new_p = realloc(p, start_sizes[s] - deltas[d]); 419 ASSERT_EQ(p, new_p); // realloc should not allocate new memory 420 } 421 free(p); 422 } 423 } 424 425 TEST(Allocators, Realloc2) { 426 for (int src_size = 0; src_size >= 0; src_size = NextSize(src_size)) { 427 for (int dst_size = 0; dst_size >= 0; dst_size = NextSize(dst_size)) { 428 unsigned char* src = reinterpret_cast<unsigned char*>(malloc(src_size)); 429 Fill(src, src_size); 430 unsigned char* dst = 431 reinterpret_cast<unsigned char*>(realloc(src, dst_size)); 432 EXPECT_TRUE(Valid(dst, min(src_size, dst_size))); 433 Fill(dst, dst_size); 434 EXPECT_TRUE(Valid(dst, dst_size)); 435 if (dst != NULL) free(dst); 436 } 437 } 438 439 // Now make sure realloc works correctly even when we overflow the 440 // packed cache, so some entries are evicted from the cache. 441 // The cache has 2^12 entries, keyed by page number. 442 const int kNumEntries = 1 << 14; 443 int** p = reinterpret_cast<int**>(malloc(sizeof(*p) * kNumEntries)); 444 int sum = 0; 445 for (int i = 0; i < kNumEntries; i++) { 446 // no page size is likely to be bigger than 8192? 447 p[i] = reinterpret_cast<int*>(malloc(8192)); 448 p[i][1000] = i; // use memory deep in the heart of p 449 } 450 for (int i = 0; i < kNumEntries; i++) { 451 p[i] = reinterpret_cast<int*>(realloc(p[i], 9000)); 452 } 453 for (int i = 0; i < kNumEntries; i++) { 454 sum += p[i][1000]; 455 free(p[i]); 456 } 457 EXPECT_EQ(kNumEntries/2 * (kNumEntries - 1), sum); // assume kNE is even 458 free(p); 459 } 460 461 TEST(Allocators, ReallocZero) { 462 // Test that realloc to zero does not return NULL. 463 for (int size = 0; size >= 0; size = NextSize(size)) { 464 char* ptr = reinterpret_cast<char*>(malloc(size)); 465 EXPECT_NE(static_cast<char*>(NULL), ptr); 466 ptr = reinterpret_cast<char*>(realloc(ptr, 0)); 467 EXPECT_NE(static_cast<char*>(NULL), ptr); 468 if (ptr) 469 free(ptr); 470 } 471 } 472 473 #ifdef WIN32 474 // Test recalloc 475 TEST(Allocators, Recalloc) { 476 for (int src_size = 0; src_size >= 0; src_size = NextSize(src_size)) { 477 for (int dst_size = 0; dst_size >= 0; dst_size = NextSize(dst_size)) { 478 unsigned char* src = 479 reinterpret_cast<unsigned char*>(_recalloc(NULL, 1, src_size)); 480 EXPECT_TRUE(IsZeroed(src, src_size)); 481 Fill(src, src_size); 482 unsigned char* dst = 483 reinterpret_cast<unsigned char*>(_recalloc(src, 1, dst_size)); 484 EXPECT_TRUE(Valid(dst, min(src_size, dst_size))); 485 Fill(dst, dst_size); 486 EXPECT_TRUE(Valid(dst, dst_size)); 487 if (dst != NULL) 488 free(dst); 489 } 490 } 491 } 492 493 // Test windows specific _aligned_malloc() and _aligned_free() methods. 494 TEST(Allocators, AlignedMalloc) { 495 // Try allocating data with a bunch of alignments and sizes 496 static const int kTestAlignments[] = {8, 16, 256, 4096, 8192, 16384}; 497 for (int size = 1; size > 0; size = NextSize(size)) { 498 for (int i = 0; i < ARRAYSIZE(kTestAlignments); ++i) { 499 unsigned char* ptr = static_cast<unsigned char*>( 500 _aligned_malloc(size, kTestAlignments[i])); 501 CheckAlignment(ptr, kTestAlignments[i]); 502 Fill(ptr, size); 503 EXPECT_TRUE(Valid(ptr, size)); 504 505 // Make a second allocation of the same size and alignment to prevent 506 // allocators from passing this test by accident. Per jar, tcmalloc 507 // provides allocations for new (never before seen) sizes out of a thread 508 // local heap of a given "size class." Each time the test requests a new 509 // size, it will usually get the first element of a span, which is a 510 // 4K aligned allocation. 511 unsigned char* ptr2 = static_cast<unsigned char*>( 512 _aligned_malloc(size, kTestAlignments[i])); 513 CheckAlignment(ptr2, kTestAlignments[i]); 514 Fill(ptr2, size); 515 EXPECT_TRUE(Valid(ptr2, size)); 516 517 // Should never happen, but sanity check just in case. 518 ASSERT_NE(ptr, ptr2); 519 _aligned_free(ptr); 520 _aligned_free(ptr2); 521 } 522 } 523 } 524 525 #endif 526 527 528 int main(int argc, char** argv) { 529 testing::InitGoogleTest(&argc, argv); 530 return RUN_ALL_TESTS(); 531 } 532