1 //===-- sanitizer_allocator_test.cc ---------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file is a part of ThreadSanitizer/AddressSanitizer runtime. 11 // Tests for sanitizer_allocator.h. 12 // 13 //===----------------------------------------------------------------------===// 14 #include "sanitizer_common/sanitizer_allocator.h" 15 #include "sanitizer_common/sanitizer_allocator_internal.h" 16 #include "sanitizer_common/sanitizer_common.h" 17 18 #include "sanitizer_test_utils.h" 19 #include "sanitizer_pthread_wrappers.h" 20 21 #include "gtest/gtest.h" 22 23 #include <stdlib.h> 24 #include <algorithm> 25 #include <vector> 26 #include <set> 27 28 // Too slow for debug build 29 #if !SANITIZER_DEBUG 30 31 #if SANITIZER_CAN_USE_ALLOCATOR64 32 static const uptr kAllocatorSpace = 0x700000000000ULL; 33 static const uptr kAllocatorSize = 0x010000000000ULL; // 1T. 34 static const u64 kAddressSpaceSize = 1ULL << 47; 35 36 typedef SizeClassAllocator64< 37 kAllocatorSpace, kAllocatorSize, 16, DefaultSizeClassMap> Allocator64; 38 39 typedef SizeClassAllocator64< 40 kAllocatorSpace, kAllocatorSize, 16, CompactSizeClassMap> Allocator64Compact; 41 #elif defined(__mips64) 42 static const u64 kAddressSpaceSize = 1ULL << 40; 43 #elif defined(__aarch64__) 44 static const u64 kAddressSpaceSize = 1ULL << 39; 45 #else 46 static const u64 kAddressSpaceSize = 1ULL << 32; 47 #endif 48 49 static const uptr kRegionSizeLog = FIRST_32_SECOND_64(20, 24); 50 static const uptr kFlatByteMapSize = kAddressSpaceSize >> kRegionSizeLog; 51 52 typedef SizeClassAllocator32< 53 0, kAddressSpaceSize, 54 /*kMetadataSize*/16, 55 CompactSizeClassMap, 56 kRegionSizeLog, 57 FlatByteMap<kFlatByteMapSize> > 58 Allocator32Compact; 59 60 template <class SizeClassMap> 61 void TestSizeClassMap() { 62 typedef SizeClassMap SCMap; 63 // SCMap::Print(); 64 SCMap::Validate(); 65 } 66 67 TEST(SanitizerCommon, DefaultSizeClassMap) { 68 TestSizeClassMap<DefaultSizeClassMap>(); 69 } 70 71 TEST(SanitizerCommon, CompactSizeClassMap) { 72 TestSizeClassMap<CompactSizeClassMap>(); 73 } 74 75 TEST(SanitizerCommon, InternalSizeClassMap) { 76 TestSizeClassMap<InternalSizeClassMap>(); 77 } 78 79 template <class Allocator> 80 void TestSizeClassAllocator() { 81 Allocator *a = new Allocator; 82 a->Init(); 83 SizeClassAllocatorLocalCache<Allocator> cache; 84 memset(&cache, 0, sizeof(cache)); 85 cache.Init(0); 86 87 static const uptr sizes[] = {1, 16, 30, 40, 100, 1000, 10000, 88 50000, 60000, 100000, 120000, 300000, 500000, 1000000, 2000000}; 89 90 std::vector<void *> allocated; 91 92 uptr last_total_allocated = 0; 93 for (int i = 0; i < 3; i++) { 94 // Allocate a bunch of chunks. 95 for (uptr s = 0; s < ARRAY_SIZE(sizes); s++) { 96 uptr size = sizes[s]; 97 if (!a->CanAllocate(size, 1)) continue; 98 // printf("s = %ld\n", size); 99 uptr n_iter = std::max((uptr)6, 4000000 / size); 100 // fprintf(stderr, "size: %ld iter: %ld\n", size, n_iter); 101 for (uptr i = 0; i < n_iter; i++) { 102 uptr class_id0 = Allocator::SizeClassMapT::ClassID(size); 103 char *x = (char*)cache.Allocate(a, class_id0); 104 x[0] = 0; 105 x[size - 1] = 0; 106 x[size / 2] = 0; 107 allocated.push_back(x); 108 CHECK_EQ(x, a->GetBlockBegin(x)); 109 CHECK_EQ(x, a->GetBlockBegin(x + size - 1)); 110 CHECK(a->PointerIsMine(x)); 111 CHECK(a->PointerIsMine(x + size - 1)); 112 CHECK(a->PointerIsMine(x + size / 2)); 113 CHECK_GE(a->GetActuallyAllocatedSize(x), size); 114 uptr class_id = a->GetSizeClass(x); 115 CHECK_EQ(class_id, Allocator::SizeClassMapT::ClassID(size)); 116 uptr *metadata = reinterpret_cast<uptr*>(a->GetMetaData(x)); 117 metadata[0] = reinterpret_cast<uptr>(x) + 1; 118 metadata[1] = 0xABCD; 119 } 120 } 121 // Deallocate all. 122 for (uptr i = 0; i < allocated.size(); i++) { 123 void *x = allocated[i]; 124 uptr *metadata = reinterpret_cast<uptr*>(a->GetMetaData(x)); 125 CHECK_EQ(metadata[0], reinterpret_cast<uptr>(x) + 1); 126 CHECK_EQ(metadata[1], 0xABCD); 127 cache.Deallocate(a, a->GetSizeClass(x), x); 128 } 129 allocated.clear(); 130 uptr total_allocated = a->TotalMemoryUsed(); 131 if (last_total_allocated == 0) 132 last_total_allocated = total_allocated; 133 CHECK_EQ(last_total_allocated, total_allocated); 134 } 135 136 // Check that GetBlockBegin never crashes. 137 for (uptr x = 0, step = kAddressSpaceSize / 100000; 138 x < kAddressSpaceSize - step; x += step) 139 if (a->PointerIsMine(reinterpret_cast<void *>(x))) 140 Ident(a->GetBlockBegin(reinterpret_cast<void *>(x))); 141 142 a->TestOnlyUnmap(); 143 delete a; 144 } 145 146 #if SANITIZER_CAN_USE_ALLOCATOR64 147 TEST(SanitizerCommon, SizeClassAllocator64) { 148 TestSizeClassAllocator<Allocator64>(); 149 } 150 151 TEST(SanitizerCommon, SizeClassAllocator64Compact) { 152 TestSizeClassAllocator<Allocator64Compact>(); 153 } 154 #endif 155 156 TEST(SanitizerCommon, SizeClassAllocator32Compact) { 157 TestSizeClassAllocator<Allocator32Compact>(); 158 } 159 160 template <class Allocator> 161 void SizeClassAllocatorMetadataStress() { 162 Allocator *a = new Allocator; 163 a->Init(); 164 SizeClassAllocatorLocalCache<Allocator> cache; 165 memset(&cache, 0, sizeof(cache)); 166 cache.Init(0); 167 168 const uptr kNumAllocs = 1 << 13; 169 void *allocated[kNumAllocs]; 170 void *meta[kNumAllocs]; 171 for (uptr i = 0; i < kNumAllocs; i++) { 172 void *x = cache.Allocate(a, 1 + i % 50); 173 allocated[i] = x; 174 meta[i] = a->GetMetaData(x); 175 } 176 // Get Metadata kNumAllocs^2 times. 177 for (uptr i = 0; i < kNumAllocs * kNumAllocs; i++) { 178 uptr idx = i % kNumAllocs; 179 void *m = a->GetMetaData(allocated[idx]); 180 EXPECT_EQ(m, meta[idx]); 181 } 182 for (uptr i = 0; i < kNumAllocs; i++) { 183 cache.Deallocate(a, 1 + i % 50, allocated[i]); 184 } 185 186 a->TestOnlyUnmap(); 187 delete a; 188 } 189 190 #if SANITIZER_CAN_USE_ALLOCATOR64 191 TEST(SanitizerCommon, SizeClassAllocator64MetadataStress) { 192 SizeClassAllocatorMetadataStress<Allocator64>(); 193 } 194 195 TEST(SanitizerCommon, SizeClassAllocator64CompactMetadataStress) { 196 SizeClassAllocatorMetadataStress<Allocator64Compact>(); 197 } 198 #endif // SANITIZER_CAN_USE_ALLOCATOR64 199 TEST(SanitizerCommon, SizeClassAllocator32CompactMetadataStress) { 200 SizeClassAllocatorMetadataStress<Allocator32Compact>(); 201 } 202 203 template <class Allocator> 204 void SizeClassAllocatorGetBlockBeginStress() { 205 Allocator *a = new Allocator; 206 a->Init(); 207 SizeClassAllocatorLocalCache<Allocator> cache; 208 memset(&cache, 0, sizeof(cache)); 209 cache.Init(0); 210 211 uptr max_size_class = Allocator::kNumClasses - 1; 212 uptr size = Allocator::SizeClassMapT::Size(max_size_class); 213 u64 G8 = 1ULL << 33; 214 // Make sure we correctly compute GetBlockBegin() w/o overflow. 215 for (size_t i = 0; i <= G8 / size; i++) { 216 void *x = cache.Allocate(a, max_size_class); 217 void *beg = a->GetBlockBegin(x); 218 // if ((i & (i - 1)) == 0) 219 // fprintf(stderr, "[%zd] %p %p\n", i, x, beg); 220 EXPECT_EQ(x, beg); 221 } 222 223 a->TestOnlyUnmap(); 224 delete a; 225 } 226 227 #if SANITIZER_CAN_USE_ALLOCATOR64 228 TEST(SanitizerCommon, SizeClassAllocator64GetBlockBegin) { 229 SizeClassAllocatorGetBlockBeginStress<Allocator64>(); 230 } 231 TEST(SanitizerCommon, SizeClassAllocator64CompactGetBlockBegin) { 232 SizeClassAllocatorGetBlockBeginStress<Allocator64Compact>(); 233 } 234 TEST(SanitizerCommon, SizeClassAllocator32CompactGetBlockBegin) { 235 SizeClassAllocatorGetBlockBeginStress<Allocator32Compact>(); 236 } 237 #endif // SANITIZER_CAN_USE_ALLOCATOR64 238 239 struct TestMapUnmapCallback { 240 static int map_count, unmap_count; 241 void OnMap(uptr p, uptr size) const { map_count++; } 242 void OnUnmap(uptr p, uptr size) const { unmap_count++; } 243 }; 244 int TestMapUnmapCallback::map_count; 245 int TestMapUnmapCallback::unmap_count; 246 247 #if SANITIZER_CAN_USE_ALLOCATOR64 248 TEST(SanitizerCommon, SizeClassAllocator64MapUnmapCallback) { 249 TestMapUnmapCallback::map_count = 0; 250 TestMapUnmapCallback::unmap_count = 0; 251 typedef SizeClassAllocator64< 252 kAllocatorSpace, kAllocatorSize, 16, DefaultSizeClassMap, 253 TestMapUnmapCallback> Allocator64WithCallBack; 254 Allocator64WithCallBack *a = new Allocator64WithCallBack; 255 a->Init(); 256 EXPECT_EQ(TestMapUnmapCallback::map_count, 1); // Allocator state. 257 SizeClassAllocatorLocalCache<Allocator64WithCallBack> cache; 258 memset(&cache, 0, sizeof(cache)); 259 cache.Init(0); 260 AllocatorStats stats; 261 stats.Init(); 262 a->AllocateBatch(&stats, &cache, 32); 263 EXPECT_EQ(TestMapUnmapCallback::map_count, 3); // State + alloc + metadata. 264 a->TestOnlyUnmap(); 265 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1); // The whole thing. 266 delete a; 267 } 268 #endif 269 270 TEST(SanitizerCommon, SizeClassAllocator32MapUnmapCallback) { 271 TestMapUnmapCallback::map_count = 0; 272 TestMapUnmapCallback::unmap_count = 0; 273 typedef SizeClassAllocator32< 274 0, kAddressSpaceSize, 275 /*kMetadataSize*/16, 276 CompactSizeClassMap, 277 kRegionSizeLog, 278 FlatByteMap<kFlatByteMapSize>, 279 TestMapUnmapCallback> 280 Allocator32WithCallBack; 281 Allocator32WithCallBack *a = new Allocator32WithCallBack; 282 a->Init(); 283 EXPECT_EQ(TestMapUnmapCallback::map_count, 0); 284 SizeClassAllocatorLocalCache<Allocator32WithCallBack> cache; 285 memset(&cache, 0, sizeof(cache)); 286 cache.Init(0); 287 AllocatorStats stats; 288 stats.Init(); 289 a->AllocateBatch(&stats, &cache, 32); 290 EXPECT_EQ(TestMapUnmapCallback::map_count, 1); 291 a->TestOnlyUnmap(); 292 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1); 293 delete a; 294 // fprintf(stderr, "Map: %d Unmap: %d\n", 295 // TestMapUnmapCallback::map_count, 296 // TestMapUnmapCallback::unmap_count); 297 } 298 299 TEST(SanitizerCommon, LargeMmapAllocatorMapUnmapCallback) { 300 TestMapUnmapCallback::map_count = 0; 301 TestMapUnmapCallback::unmap_count = 0; 302 LargeMmapAllocator<TestMapUnmapCallback> a; 303 a.Init(/* may_return_null */ false); 304 AllocatorStats stats; 305 stats.Init(); 306 void *x = a.Allocate(&stats, 1 << 20, 1); 307 EXPECT_EQ(TestMapUnmapCallback::map_count, 1); 308 a.Deallocate(&stats, x); 309 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1); 310 } 311 312 template<class Allocator> 313 void FailInAssertionOnOOM() { 314 Allocator a; 315 a.Init(); 316 SizeClassAllocatorLocalCache<Allocator> cache; 317 memset(&cache, 0, sizeof(cache)); 318 cache.Init(0); 319 AllocatorStats stats; 320 stats.Init(); 321 for (int i = 0; i < 1000000; i++) { 322 a.AllocateBatch(&stats, &cache, 52); 323 } 324 325 a.TestOnlyUnmap(); 326 } 327 328 #if SANITIZER_CAN_USE_ALLOCATOR64 329 TEST(SanitizerCommon, SizeClassAllocator64Overflow) { 330 EXPECT_DEATH(FailInAssertionOnOOM<Allocator64>(), "Out of memory"); 331 } 332 #endif 333 334 #if !defined(_WIN32) // FIXME: This currently fails on Windows. 335 TEST(SanitizerCommon, LargeMmapAllocator) { 336 LargeMmapAllocator<> a; 337 a.Init(/* may_return_null */ false); 338 AllocatorStats stats; 339 stats.Init(); 340 341 static const int kNumAllocs = 1000; 342 char *allocated[kNumAllocs]; 343 static const uptr size = 4000; 344 // Allocate some. 345 for (int i = 0; i < kNumAllocs; i++) { 346 allocated[i] = (char *)a.Allocate(&stats, size, 1); 347 CHECK(a.PointerIsMine(allocated[i])); 348 } 349 // Deallocate all. 350 CHECK_GT(a.TotalMemoryUsed(), size * kNumAllocs); 351 for (int i = 0; i < kNumAllocs; i++) { 352 char *p = allocated[i]; 353 CHECK(a.PointerIsMine(p)); 354 a.Deallocate(&stats, p); 355 } 356 // Check that non left. 357 CHECK_EQ(a.TotalMemoryUsed(), 0); 358 359 // Allocate some more, also add metadata. 360 for (int i = 0; i < kNumAllocs; i++) { 361 char *x = (char *)a.Allocate(&stats, size, 1); 362 CHECK_GE(a.GetActuallyAllocatedSize(x), size); 363 uptr *meta = reinterpret_cast<uptr*>(a.GetMetaData(x)); 364 *meta = i; 365 allocated[i] = x; 366 } 367 for (int i = 0; i < kNumAllocs * kNumAllocs; i++) { 368 char *p = allocated[i % kNumAllocs]; 369 CHECK(a.PointerIsMine(p)); 370 CHECK(a.PointerIsMine(p + 2000)); 371 } 372 CHECK_GT(a.TotalMemoryUsed(), size * kNumAllocs); 373 // Deallocate all in reverse order. 374 for (int i = 0; i < kNumAllocs; i++) { 375 int idx = kNumAllocs - i - 1; 376 char *p = allocated[idx]; 377 uptr *meta = reinterpret_cast<uptr*>(a.GetMetaData(p)); 378 CHECK_EQ(*meta, idx); 379 CHECK(a.PointerIsMine(p)); 380 a.Deallocate(&stats, p); 381 } 382 CHECK_EQ(a.TotalMemoryUsed(), 0); 383 384 // Test alignments. 385 uptr max_alignment = SANITIZER_WORDSIZE == 64 ? (1 << 28) : (1 << 24); 386 for (uptr alignment = 8; alignment <= max_alignment; alignment *= 2) { 387 const uptr kNumAlignedAllocs = 100; 388 for (uptr i = 0; i < kNumAlignedAllocs; i++) { 389 uptr size = ((i % 10) + 1) * 4096; 390 char *p = allocated[i] = (char *)a.Allocate(&stats, size, alignment); 391 CHECK_EQ(p, a.GetBlockBegin(p)); 392 CHECK_EQ(p, a.GetBlockBegin(p + size - 1)); 393 CHECK_EQ(p, a.GetBlockBegin(p + size / 2)); 394 CHECK_EQ(0, (uptr)allocated[i] % alignment); 395 p[0] = p[size - 1] = 0; 396 } 397 for (uptr i = 0; i < kNumAlignedAllocs; i++) { 398 a.Deallocate(&stats, allocated[i]); 399 } 400 } 401 402 // Regression test for boundary condition in GetBlockBegin(). 403 uptr page_size = GetPageSizeCached(); 404 char *p = (char *)a.Allocate(&stats, page_size, 1); 405 CHECK_EQ(p, a.GetBlockBegin(p)); 406 CHECK_EQ(p, (char *)a.GetBlockBegin(p + page_size - 1)); 407 CHECK_NE(p, (char *)a.GetBlockBegin(p + page_size)); 408 a.Deallocate(&stats, p); 409 } 410 #endif 411 412 template 413 <class PrimaryAllocator, class SecondaryAllocator, class AllocatorCache> 414 void TestCombinedAllocator() { 415 typedef 416 CombinedAllocator<PrimaryAllocator, AllocatorCache, SecondaryAllocator> 417 Allocator; 418 Allocator *a = new Allocator; 419 a->Init(/* may_return_null */ true); 420 421 AllocatorCache cache; 422 memset(&cache, 0, sizeof(cache)); 423 a->InitCache(&cache); 424 425 EXPECT_EQ(a->Allocate(&cache, -1, 1), (void*)0); 426 EXPECT_EQ(a->Allocate(&cache, -1, 1024), (void*)0); 427 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1024, 1), (void*)0); 428 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1024, 1024), (void*)0); 429 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1023, 1024), (void*)0); 430 431 // Set to false 432 a->SetMayReturnNull(false); 433 EXPECT_DEATH(a->Allocate(&cache, -1, 1), 434 "allocator is terminating the process"); 435 436 const uptr kNumAllocs = 100000; 437 const uptr kNumIter = 10; 438 for (uptr iter = 0; iter < kNumIter; iter++) { 439 std::vector<void*> allocated; 440 for (uptr i = 0; i < kNumAllocs; i++) { 441 uptr size = (i % (1 << 14)) + 1; 442 if ((i % 1024) == 0) 443 size = 1 << (10 + (i % 14)); 444 void *x = a->Allocate(&cache, size, 1); 445 uptr *meta = reinterpret_cast<uptr*>(a->GetMetaData(x)); 446 CHECK_EQ(*meta, 0); 447 *meta = size; 448 allocated.push_back(x); 449 } 450 451 random_shuffle(allocated.begin(), allocated.end()); 452 453 for (uptr i = 0; i < kNumAllocs; i++) { 454 void *x = allocated[i]; 455 uptr *meta = reinterpret_cast<uptr*>(a->GetMetaData(x)); 456 CHECK_NE(*meta, 0); 457 CHECK(a->PointerIsMine(x)); 458 *meta = 0; 459 a->Deallocate(&cache, x); 460 } 461 allocated.clear(); 462 a->SwallowCache(&cache); 463 } 464 a->DestroyCache(&cache); 465 a->TestOnlyUnmap(); 466 } 467 468 #if SANITIZER_CAN_USE_ALLOCATOR64 469 TEST(SanitizerCommon, CombinedAllocator64) { 470 TestCombinedAllocator<Allocator64, 471 LargeMmapAllocator<>, 472 SizeClassAllocatorLocalCache<Allocator64> > (); 473 } 474 475 TEST(SanitizerCommon, CombinedAllocator64Compact) { 476 TestCombinedAllocator<Allocator64Compact, 477 LargeMmapAllocator<>, 478 SizeClassAllocatorLocalCache<Allocator64Compact> > (); 479 } 480 #endif 481 482 #if !defined(_WIN32) // FIXME: This currently fails on Windows. 483 TEST(SanitizerCommon, CombinedAllocator32Compact) { 484 TestCombinedAllocator<Allocator32Compact, 485 LargeMmapAllocator<>, 486 SizeClassAllocatorLocalCache<Allocator32Compact> > (); 487 } 488 #endif 489 490 template <class AllocatorCache> 491 void TestSizeClassAllocatorLocalCache() { 492 AllocatorCache cache; 493 typedef typename AllocatorCache::Allocator Allocator; 494 Allocator *a = new Allocator(); 495 496 a->Init(); 497 memset(&cache, 0, sizeof(cache)); 498 cache.Init(0); 499 500 const uptr kNumAllocs = 10000; 501 const int kNumIter = 100; 502 uptr saved_total = 0; 503 for (int class_id = 1; class_id <= 5; class_id++) { 504 for (int it = 0; it < kNumIter; it++) { 505 void *allocated[kNumAllocs]; 506 for (uptr i = 0; i < kNumAllocs; i++) { 507 allocated[i] = cache.Allocate(a, class_id); 508 } 509 for (uptr i = 0; i < kNumAllocs; i++) { 510 cache.Deallocate(a, class_id, allocated[i]); 511 } 512 cache.Drain(a); 513 uptr total_allocated = a->TotalMemoryUsed(); 514 if (it) 515 CHECK_EQ(saved_total, total_allocated); 516 saved_total = total_allocated; 517 } 518 } 519 520 a->TestOnlyUnmap(); 521 delete a; 522 } 523 524 #if SANITIZER_CAN_USE_ALLOCATOR64 525 TEST(SanitizerCommon, SizeClassAllocator64LocalCache) { 526 TestSizeClassAllocatorLocalCache< 527 SizeClassAllocatorLocalCache<Allocator64> >(); 528 } 529 530 TEST(SanitizerCommon, SizeClassAllocator64CompactLocalCache) { 531 TestSizeClassAllocatorLocalCache< 532 SizeClassAllocatorLocalCache<Allocator64Compact> >(); 533 } 534 #endif 535 536 TEST(SanitizerCommon, SizeClassAllocator32CompactLocalCache) { 537 TestSizeClassAllocatorLocalCache< 538 SizeClassAllocatorLocalCache<Allocator32Compact> >(); 539 } 540 541 #if SANITIZER_CAN_USE_ALLOCATOR64 542 typedef SizeClassAllocatorLocalCache<Allocator64> AllocatorCache; 543 static AllocatorCache static_allocator_cache; 544 545 void *AllocatorLeakTestWorker(void *arg) { 546 typedef AllocatorCache::Allocator Allocator; 547 Allocator *a = (Allocator*)(arg); 548 static_allocator_cache.Allocate(a, 10); 549 static_allocator_cache.Drain(a); 550 return 0; 551 } 552 553 TEST(SanitizerCommon, AllocatorLeakTest) { 554 typedef AllocatorCache::Allocator Allocator; 555 Allocator a; 556 a.Init(); 557 uptr total_used_memory = 0; 558 for (int i = 0; i < 100; i++) { 559 pthread_t t; 560 PTHREAD_CREATE(&t, 0, AllocatorLeakTestWorker, &a); 561 PTHREAD_JOIN(t, 0); 562 if (i == 0) 563 total_used_memory = a.TotalMemoryUsed(); 564 EXPECT_EQ(a.TotalMemoryUsed(), total_used_memory); 565 } 566 567 a.TestOnlyUnmap(); 568 } 569 570 // Struct which is allocated to pass info to new threads. The new thread frees 571 // it. 572 struct NewThreadParams { 573 AllocatorCache *thread_cache; 574 AllocatorCache::Allocator *allocator; 575 uptr class_id; 576 }; 577 578 // Called in a new thread. Just frees its argument. 579 static void *DeallocNewThreadWorker(void *arg) { 580 NewThreadParams *params = reinterpret_cast<NewThreadParams*>(arg); 581 params->thread_cache->Deallocate(params->allocator, params->class_id, params); 582 return NULL; 583 } 584 585 // The allocator cache is supposed to be POD and zero initialized. We should be 586 // able to call Deallocate on a zeroed cache, and it will self-initialize. 587 TEST(Allocator, AllocatorCacheDeallocNewThread) { 588 AllocatorCache::Allocator allocator; 589 allocator.Init(); 590 AllocatorCache main_cache; 591 AllocatorCache child_cache; 592 memset(&main_cache, 0, sizeof(main_cache)); 593 memset(&child_cache, 0, sizeof(child_cache)); 594 595 uptr class_id = DefaultSizeClassMap::ClassID(sizeof(NewThreadParams)); 596 NewThreadParams *params = reinterpret_cast<NewThreadParams*>( 597 main_cache.Allocate(&allocator, class_id)); 598 params->thread_cache = &child_cache; 599 params->allocator = &allocator; 600 params->class_id = class_id; 601 pthread_t t; 602 PTHREAD_CREATE(&t, 0, DeallocNewThreadWorker, params); 603 PTHREAD_JOIN(t, 0); 604 } 605 #endif 606 607 TEST(Allocator, Basic) { 608 char *p = (char*)InternalAlloc(10); 609 EXPECT_NE(p, (char*)0); 610 char *p2 = (char*)InternalAlloc(20); 611 EXPECT_NE(p2, (char*)0); 612 EXPECT_NE(p2, p); 613 InternalFree(p); 614 InternalFree(p2); 615 } 616 617 TEST(Allocator, Stress) { 618 const int kCount = 1000; 619 char *ptrs[kCount]; 620 unsigned rnd = 42; 621 for (int i = 0; i < kCount; i++) { 622 uptr sz = my_rand_r(&rnd) % 1000; 623 char *p = (char*)InternalAlloc(sz); 624 EXPECT_NE(p, (char*)0); 625 ptrs[i] = p; 626 } 627 for (int i = 0; i < kCount; i++) { 628 InternalFree(ptrs[i]); 629 } 630 } 631 632 TEST(Allocator, LargeAlloc) { 633 void *p = InternalAlloc(10 << 20); 634 InternalFree(p); 635 } 636 637 TEST(Allocator, ScopedBuffer) { 638 const int kSize = 512; 639 { 640 InternalScopedBuffer<int> int_buf(kSize); 641 EXPECT_EQ(sizeof(int) * kSize, int_buf.size()); // NOLINT 642 } 643 InternalScopedBuffer<char> char_buf(kSize); 644 EXPECT_EQ(sizeof(char) * kSize, char_buf.size()); // NOLINT 645 internal_memset(char_buf.data(), 'c', kSize); 646 for (int i = 0; i < kSize; i++) { 647 EXPECT_EQ('c', char_buf[i]); 648 } 649 } 650 651 void IterationTestCallback(uptr chunk, void *arg) { 652 reinterpret_cast<std::set<uptr> *>(arg)->insert(chunk); 653 } 654 655 template <class Allocator> 656 void TestSizeClassAllocatorIteration() { 657 Allocator *a = new Allocator; 658 a->Init(); 659 SizeClassAllocatorLocalCache<Allocator> cache; 660 memset(&cache, 0, sizeof(cache)); 661 cache.Init(0); 662 663 static const uptr sizes[] = {1, 16, 30, 40, 100, 1000, 10000, 664 50000, 60000, 100000, 120000, 300000, 500000, 1000000, 2000000}; 665 666 std::vector<void *> allocated; 667 668 // Allocate a bunch of chunks. 669 for (uptr s = 0; s < ARRAY_SIZE(sizes); s++) { 670 uptr size = sizes[s]; 671 if (!a->CanAllocate(size, 1)) continue; 672 // printf("s = %ld\n", size); 673 uptr n_iter = std::max((uptr)6, 80000 / size); 674 // fprintf(stderr, "size: %ld iter: %ld\n", size, n_iter); 675 for (uptr j = 0; j < n_iter; j++) { 676 uptr class_id0 = Allocator::SizeClassMapT::ClassID(size); 677 void *x = cache.Allocate(a, class_id0); 678 allocated.push_back(x); 679 } 680 } 681 682 std::set<uptr> reported_chunks; 683 a->ForceLock(); 684 a->ForEachChunk(IterationTestCallback, &reported_chunks); 685 a->ForceUnlock(); 686 687 for (uptr i = 0; i < allocated.size(); i++) { 688 // Don't use EXPECT_NE. Reporting the first mismatch is enough. 689 ASSERT_NE(reported_chunks.find(reinterpret_cast<uptr>(allocated[i])), 690 reported_chunks.end()); 691 } 692 693 a->TestOnlyUnmap(); 694 delete a; 695 } 696 697 #if SANITIZER_CAN_USE_ALLOCATOR64 698 TEST(SanitizerCommon, SizeClassAllocator64Iteration) { 699 TestSizeClassAllocatorIteration<Allocator64>(); 700 } 701 #endif 702 703 TEST(SanitizerCommon, SizeClassAllocator32Iteration) { 704 TestSizeClassAllocatorIteration<Allocator32Compact>(); 705 } 706 707 TEST(SanitizerCommon, LargeMmapAllocatorIteration) { 708 LargeMmapAllocator<> a; 709 a.Init(/* may_return_null */ false); 710 AllocatorStats stats; 711 stats.Init(); 712 713 static const uptr kNumAllocs = 1000; 714 char *allocated[kNumAllocs]; 715 static const uptr size = 40; 716 // Allocate some. 717 for (uptr i = 0; i < kNumAllocs; i++) 718 allocated[i] = (char *)a.Allocate(&stats, size, 1); 719 720 std::set<uptr> reported_chunks; 721 a.ForceLock(); 722 a.ForEachChunk(IterationTestCallback, &reported_chunks); 723 a.ForceUnlock(); 724 725 for (uptr i = 0; i < kNumAllocs; i++) { 726 // Don't use EXPECT_NE. Reporting the first mismatch is enough. 727 ASSERT_NE(reported_chunks.find(reinterpret_cast<uptr>(allocated[i])), 728 reported_chunks.end()); 729 } 730 for (uptr i = 0; i < kNumAllocs; i++) 731 a.Deallocate(&stats, allocated[i]); 732 } 733 734 TEST(SanitizerCommon, LargeMmapAllocatorBlockBegin) { 735 LargeMmapAllocator<> a; 736 a.Init(/* may_return_null */ false); 737 AllocatorStats stats; 738 stats.Init(); 739 740 static const uptr kNumAllocs = 1024; 741 static const uptr kNumExpectedFalseLookups = 10000000; 742 char *allocated[kNumAllocs]; 743 static const uptr size = 4096; 744 // Allocate some. 745 for (uptr i = 0; i < kNumAllocs; i++) { 746 allocated[i] = (char *)a.Allocate(&stats, size, 1); 747 } 748 749 a.ForceLock(); 750 for (uptr i = 0; i < kNumAllocs * kNumAllocs; i++) { 751 // if ((i & (i - 1)) == 0) fprintf(stderr, "[%zd]\n", i); 752 char *p1 = allocated[i % kNumAllocs]; 753 EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1)); 754 EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 + size / 2)); 755 EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 + size - 1)); 756 EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 - 100)); 757 } 758 759 for (uptr i = 0; i < kNumExpectedFalseLookups; i++) { 760 void *p = reinterpret_cast<void *>(i % 1024); 761 EXPECT_EQ((void *)0, a.GetBlockBeginFastLocked(p)); 762 p = reinterpret_cast<void *>(~0L - (i % 1024)); 763 EXPECT_EQ((void *)0, a.GetBlockBeginFastLocked(p)); 764 } 765 a.ForceUnlock(); 766 767 for (uptr i = 0; i < kNumAllocs; i++) 768 a.Deallocate(&stats, allocated[i]); 769 } 770 771 772 #if SANITIZER_CAN_USE_ALLOCATOR64 773 // Regression test for out-of-memory condition in PopulateFreeList(). 774 TEST(SanitizerCommon, SizeClassAllocator64PopulateFreeListOOM) { 775 // In a world where regions are small and chunks are huge... 776 typedef SizeClassMap<63, 128, 16> SpecialSizeClassMap; 777 typedef SizeClassAllocator64<kAllocatorSpace, kAllocatorSize, 0, 778 SpecialSizeClassMap> SpecialAllocator64; 779 const uptr kRegionSize = 780 kAllocatorSize / SpecialSizeClassMap::kNumClassesRounded; 781 SpecialAllocator64 *a = new SpecialAllocator64; 782 a->Init(); 783 SizeClassAllocatorLocalCache<SpecialAllocator64> cache; 784 memset(&cache, 0, sizeof(cache)); 785 cache.Init(0); 786 787 // ...one man is on a mission to overflow a region with a series of 788 // successive allocations. 789 const uptr kClassID = 107; 790 const uptr kAllocationSize = DefaultSizeClassMap::Size(kClassID); 791 ASSERT_LT(2 * kAllocationSize, kRegionSize); 792 ASSERT_GT(3 * kAllocationSize, kRegionSize); 793 cache.Allocate(a, kClassID); 794 EXPECT_DEATH(cache.Allocate(a, kClassID) && cache.Allocate(a, kClassID), 795 "The process has exhausted"); 796 a->TestOnlyUnmap(); 797 delete a; 798 } 799 #endif 800 801 TEST(SanitizerCommon, TwoLevelByteMap) { 802 const u64 kSize1 = 1 << 6, kSize2 = 1 << 12; 803 const u64 n = kSize1 * kSize2; 804 TwoLevelByteMap<kSize1, kSize2> m; 805 m.TestOnlyInit(); 806 for (u64 i = 0; i < n; i += 7) { 807 m.set(i, (i % 100) + 1); 808 } 809 for (u64 j = 0; j < n; j++) { 810 if (j % 7) 811 EXPECT_EQ(m[j], 0); 812 else 813 EXPECT_EQ(m[j], (j % 100) + 1); 814 } 815 816 m.TestOnlyUnmap(); 817 } 818 819 820 typedef TwoLevelByteMap<1 << 12, 1 << 13, TestMapUnmapCallback> TestByteMap; 821 822 struct TestByteMapParam { 823 TestByteMap *m; 824 size_t shard; 825 size_t num_shards; 826 }; 827 828 void *TwoLevelByteMapUserThread(void *param) { 829 TestByteMapParam *p = (TestByteMapParam*)param; 830 for (size_t i = p->shard; i < p->m->size(); i += p->num_shards) { 831 size_t val = (i % 100) + 1; 832 p->m->set(i, val); 833 EXPECT_EQ((*p->m)[i], val); 834 } 835 return 0; 836 } 837 838 TEST(SanitizerCommon, ThreadedTwoLevelByteMap) { 839 TestByteMap m; 840 m.TestOnlyInit(); 841 TestMapUnmapCallback::map_count = 0; 842 TestMapUnmapCallback::unmap_count = 0; 843 static const int kNumThreads = 4; 844 pthread_t t[kNumThreads]; 845 TestByteMapParam p[kNumThreads]; 846 for (int i = 0; i < kNumThreads; i++) { 847 p[i].m = &m; 848 p[i].shard = i; 849 p[i].num_shards = kNumThreads; 850 PTHREAD_CREATE(&t[i], 0, TwoLevelByteMapUserThread, &p[i]); 851 } 852 for (int i = 0; i < kNumThreads; i++) { 853 PTHREAD_JOIN(t[i], 0); 854 } 855 EXPECT_EQ((uptr)TestMapUnmapCallback::map_count, m.size1()); 856 EXPECT_EQ((uptr)TestMapUnmapCallback::unmap_count, 0UL); 857 m.TestOnlyUnmap(); 858 EXPECT_EQ((uptr)TestMapUnmapCallback::map_count, m.size1()); 859 EXPECT_EQ((uptr)TestMapUnmapCallback::unmap_count, m.size1()); 860 } 861 862 #endif // #if !SANITIZER_DEBUG 863
