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 291 // A global test counter for number of times the NewHandler is called. 292 static int news_handled = 0; 293 static void TestNewHandler() { 294 ++news_handled; 295 throw std::bad_alloc(); 296 } 297 298 // Because we compile without exceptions, we expect these will not throw. 299 static void TestOneNewWithoutExceptions(void* (*func)(size_t), 300 bool should_throw) { 301 // success test 302 try { 303 void* ptr = (*func)(kNotTooBig); 304 EXPECT_NE(reinterpret_cast<void*>(NULL), ptr) << 305 "allocation should not have failed."; 306 } catch(...) { 307 EXPECT_EQ(0, 1) << "allocation threw unexpected exception."; 308 } 309 310 // failure test 311 try { 312 void* rv = (*func)(kTooBig); 313 EXPECT_EQ(NULL, rv); 314 EXPECT_FALSE(should_throw) << "allocation should have thrown."; 315 } catch(...) { 316 EXPECT_TRUE(should_throw) << "allocation threw unexpected exception."; 317 } 318 } 319 320 static void TestNothrowNew(void* (*func)(size_t)) { 321 news_handled = 0; 322 323 // test without new_handler: 324 std::new_handler saved_handler = std::set_new_handler(0); 325 TestOneNewWithoutExceptions(func, false); 326 327 // test with new_handler: 328 std::set_new_handler(TestNewHandler); 329 TestOneNewWithoutExceptions(func, true); 330 EXPECT_EQ(news_handled, 1) << "nothrow new_handler was not called."; 331 std::set_new_handler(saved_handler); 332 } 333 334 } // namespace 335 336 //----------------------------------------------------------------------------- 337 338 TEST(Atomics, AtomicIncrementWord) { 339 TestAtomicIncrement<AtomicWord>(); 340 } 341 342 TEST(Atomics, AtomicIncrement32) { 343 TestAtomicIncrement<Atomic32>(); 344 } 345 346 TEST(Atomics, AtomicOpsWord) { 347 TestAtomicIncrement<AtomicWord>(); 348 } 349 350 TEST(Atomics, AtomicOps32) { 351 TestAtomicIncrement<Atomic32>(); 352 } 353 354 TEST(Allocators, Malloc) { 355 // Try allocating data with a bunch of alignments and sizes 356 for (int size = 1; size < 1048576; size *= 2) { 357 unsigned char* ptr = reinterpret_cast<unsigned char*>(malloc(size)); 358 CheckAlignment(ptr, 2); // Should be 2 byte aligned 359 Fill(ptr, size); 360 EXPECT_TRUE(Valid(ptr, size)); 361 free(ptr); 362 } 363 } 364 365 TEST(Allocators, Calloc) { 366 TestCalloc(0, 0, true); 367 TestCalloc(0, 1, true); 368 TestCalloc(1, 1, true); 369 TestCalloc(1<<10, 0, true); 370 TestCalloc(1<<20, 0, true); 371 TestCalloc(0, 1<<10, true); 372 TestCalloc(0, 1<<20, true); 373 TestCalloc(1<<20, 2, true); 374 TestCalloc(2, 1<<20, true); 375 TestCalloc(1000, 1000, true); 376 377 TestCalloc(kMaxSize, 2, false); 378 TestCalloc(2, kMaxSize, false); 379 TestCalloc(kMaxSize, kMaxSize, false); 380 381 TestCalloc(kMaxSignedSize, 3, false); 382 TestCalloc(3, kMaxSignedSize, false); 383 TestCalloc(kMaxSignedSize, kMaxSignedSize, false); 384 } 385 386 TEST(Allocators, New) { 387 TestNothrowNew(&::operator new); 388 TestNothrowNew(&::operator new[]); 389 } 390 391 // This makes sure that reallocing a small number of bytes in either 392 // direction doesn't cause us to allocate new memory. 393 TEST(Allocators, Realloc1) { 394 int start_sizes[] = { 100, 1000, 10000, 100000 }; 395 int deltas[] = { 1, -2, 4, -8, 16, -32, 64, -128 }; 396 397 for (int s = 0; s < sizeof(start_sizes)/sizeof(*start_sizes); ++s) { 398 void* p = malloc(start_sizes[s]); 399 ASSERT_TRUE(p); 400 // The larger the start-size, the larger the non-reallocing delta. 401 for (int d = 0; d < s*2; ++d) { 402 void* new_p = realloc(p, start_sizes[s] + deltas[d]); 403 ASSERT_EQ(p, new_p); // realloc should not allocate new memory 404 } 405 // Test again, but this time reallocing smaller first. 406 for (int d = 0; d < s*2; ++d) { 407 void* new_p = realloc(p, start_sizes[s] - deltas[d]); 408 ASSERT_EQ(p, new_p); // realloc should not allocate new memory 409 } 410 free(p); 411 } 412 } 413 414 TEST(Allocators, Realloc2) { 415 for (int src_size = 0; src_size >= 0; src_size = NextSize(src_size)) { 416 for (int dst_size = 0; dst_size >= 0; dst_size = NextSize(dst_size)) { 417 unsigned char* src = reinterpret_cast<unsigned char*>(malloc(src_size)); 418 Fill(src, src_size); 419 unsigned char* dst = 420 reinterpret_cast<unsigned char*>(realloc(src, dst_size)); 421 EXPECT_TRUE(Valid(dst, min(src_size, dst_size))); 422 Fill(dst, dst_size); 423 EXPECT_TRUE(Valid(dst, dst_size)); 424 if (dst != NULL) free(dst); 425 } 426 } 427 428 // Now make sure realloc works correctly even when we overflow the 429 // packed cache, so some entries are evicted from the cache. 430 // The cache has 2^12 entries, keyed by page number. 431 const int kNumEntries = 1 << 14; 432 int** p = reinterpret_cast<int**>(malloc(sizeof(*p) * kNumEntries)); 433 int sum = 0; 434 for (int i = 0; i < kNumEntries; i++) { 435 // no page size is likely to be bigger than 8192? 436 p[i] = reinterpret_cast<int*>(malloc(8192)); 437 p[i][1000] = i; // use memory deep in the heart of p 438 } 439 for (int i = 0; i < kNumEntries; i++) { 440 p[i] = reinterpret_cast<int*>(realloc(p[i], 9000)); 441 } 442 for (int i = 0; i < kNumEntries; i++) { 443 sum += p[i][1000]; 444 free(p[i]); 445 } 446 EXPECT_EQ(kNumEntries/2 * (kNumEntries - 1), sum); // assume kNE is even 447 free(p); 448 } 449 450 TEST(Allocators, ReallocZero) { 451 // Test that realloc to zero does not return NULL. 452 for (int size = 0; size >= 0; size = NextSize(size)) { 453 char* ptr = reinterpret_cast<char*>(malloc(size)); 454 EXPECT_NE(static_cast<char*>(NULL), ptr); 455 ptr = reinterpret_cast<char*>(realloc(ptr, 0)); 456 EXPECT_NE(static_cast<char*>(NULL), ptr); 457 if (ptr) 458 free(ptr); 459 } 460 } 461 462 #ifdef WIN32 463 // Test recalloc 464 TEST(Allocators, Recalloc) { 465 for (int src_size = 0; src_size >= 0; src_size = NextSize(src_size)) { 466 for (int dst_size = 0; dst_size >= 0; dst_size = NextSize(dst_size)) { 467 unsigned char* src = 468 reinterpret_cast<unsigned char*>(_recalloc(NULL, 1, src_size)); 469 EXPECT_TRUE(IsZeroed(src, src_size)); 470 Fill(src, src_size); 471 unsigned char* dst = 472 reinterpret_cast<unsigned char*>(_recalloc(src, 1, dst_size)); 473 EXPECT_TRUE(Valid(dst, min(src_size, dst_size))); 474 Fill(dst, dst_size); 475 EXPECT_TRUE(Valid(dst, dst_size)); 476 if (dst != NULL) 477 free(dst); 478 } 479 } 480 } 481 482 // Test windows specific _aligned_malloc() and _aligned_free() methods. 483 TEST(Allocators, AlignedMalloc) { 484 // Try allocating data with a bunch of alignments and sizes 485 static const int kTestAlignments[] = {8, 16, 256, 4096, 8192, 16384}; 486 for (int size = 1; size > 0; size = NextSize(size)) { 487 for (int i = 0; i < ARRAYSIZE(kTestAlignments); ++i) { 488 unsigned char* ptr = static_cast<unsigned char*>( 489 _aligned_malloc(size, kTestAlignments[i])); 490 CheckAlignment(ptr, kTestAlignments[i]); 491 Fill(ptr, size); 492 EXPECT_TRUE(Valid(ptr, size)); 493 494 // Make a second allocation of the same size and alignment to prevent 495 // allocators from passing this test by accident. Per jar, tcmalloc 496 // provides allocations for new (never before seen) sizes out of a thread 497 // local heap of a given "size class." Each time the test requests a new 498 // size, it will usually get the first element of a span, which is a 499 // 4K aligned allocation. 500 unsigned char* ptr2 = static_cast<unsigned char*>( 501 _aligned_malloc(size, kTestAlignments[i])); 502 CheckAlignment(ptr2, kTestAlignments[i]); 503 Fill(ptr2, size); 504 EXPECT_TRUE(Valid(ptr2, size)); 505 506 // Should never happen, but sanity check just in case. 507 ASSERT_NE(ptr, ptr2); 508 _aligned_free(ptr); 509 _aligned_free(ptr2); 510 } 511 } 512 } 513 514 #endif 515 516 517 int main(int argc, char** argv) { 518 testing::InitGoogleTest(&argc, argv); 519 return RUN_ALL_TESTS(); 520 } 521