sanitizer_allocator_test.cc revision bdd844cb41718c27ef727a99a236191bc29a3df8
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_common.h" 16 17#include "sanitizer_test_utils.h" 18 19#include "gtest/gtest.h" 20 21#include <stdlib.h> 22#include <pthread.h> 23#include <algorithm> 24#include <vector> 25 26// Too slow for debug build 27#if TSAN_DEBUG == 0 28 29#if SANITIZER_WORDSIZE == 64 30static const uptr kAllocatorSpace = 0x700000000000ULL; 31static const uptr kAllocatorSize = 0x010000000000ULL; // 1T. 32static const u64 kAddressSpaceSize = 1ULL << 47; 33 34typedef SizeClassAllocator64< 35 kAllocatorSpace, kAllocatorSize, 16, DefaultSizeClassMap> Allocator64; 36 37typedef SizeClassAllocator64< 38 kAllocatorSpace, kAllocatorSize, 16, CompactSizeClassMap> Allocator64Compact; 39#else 40static const u64 kAddressSpaceSize = 1ULL << 32; 41#endif 42 43typedef SizeClassAllocator32< 44 0, kAddressSpaceSize, 16, CompactSizeClassMap> Allocator32Compact; 45 46template <class SizeClassMap> 47void TestSizeClassMap() { 48 typedef SizeClassMap SCMap; 49 // SCMap::Print(); 50 SCMap::Validate(); 51} 52 53TEST(SanitizerCommon, DefaultSizeClassMap) { 54 TestSizeClassMap<DefaultSizeClassMap>(); 55} 56 57TEST(SanitizerCommon, CompactSizeClassMap) { 58 TestSizeClassMap<CompactSizeClassMap>(); 59} 60 61template <class Allocator> 62void TestSizeClassAllocator() { 63 Allocator *a = new Allocator; 64 a->Init(); 65 SizeClassAllocatorLocalCache<Allocator> cache; 66 memset(&cache, 0, sizeof(cache)); 67 cache.Init(0); 68 69 static const uptr sizes[] = {1, 16, 30, 40, 100, 1000, 10000, 70 50000, 60000, 100000, 120000, 300000, 500000, 1000000, 2000000}; 71 72 std::vector<void *> allocated; 73 74 uptr last_total_allocated = 0; 75 for (int i = 0; i < 3; i++) { 76 // Allocate a bunch of chunks. 77 for (uptr s = 0; s < ARRAY_SIZE(sizes); s++) { 78 uptr size = sizes[s]; 79 if (!a->CanAllocate(size, 1)) continue; 80 // printf("s = %ld\n", size); 81 uptr n_iter = std::max((uptr)6, 10000000 / size); 82 // fprintf(stderr, "size: %ld iter: %ld\n", size, n_iter); 83 for (uptr i = 0; i < n_iter; i++) { 84 uptr class_id0 = Allocator::SizeClassMapT::ClassID(size); 85 char *x = (char*)cache.Allocate(a, class_id0); 86 x[0] = 0; 87 x[size - 1] = 0; 88 x[size / 2] = 0; 89 allocated.push_back(x); 90 CHECK_EQ(x, a->GetBlockBegin(x)); 91 CHECK_EQ(x, a->GetBlockBegin(x + size - 1)); 92 CHECK(a->PointerIsMine(x)); 93 CHECK(a->PointerIsMine(x + size - 1)); 94 CHECK(a->PointerIsMine(x + size / 2)); 95 CHECK_GE(a->GetActuallyAllocatedSize(x), size); 96 uptr class_id = a->GetSizeClass(x); 97 CHECK_EQ(class_id, Allocator::SizeClassMapT::ClassID(size)); 98 uptr *metadata = reinterpret_cast<uptr*>(a->GetMetaData(x)); 99 metadata[0] = reinterpret_cast<uptr>(x) + 1; 100 metadata[1] = 0xABCD; 101 } 102 } 103 // Deallocate all. 104 for (uptr i = 0; i < allocated.size(); i++) { 105 void *x = allocated[i]; 106 uptr *metadata = reinterpret_cast<uptr*>(a->GetMetaData(x)); 107 CHECK_EQ(metadata[0], reinterpret_cast<uptr>(x) + 1); 108 CHECK_EQ(metadata[1], 0xABCD); 109 cache.Deallocate(a, a->GetSizeClass(x), x); 110 } 111 allocated.clear(); 112 uptr total_allocated = a->TotalMemoryUsed(); 113 if (last_total_allocated == 0) 114 last_total_allocated = total_allocated; 115 CHECK_EQ(last_total_allocated, total_allocated); 116 } 117 118 a->TestOnlyUnmap(); 119 delete a; 120} 121 122#if SANITIZER_WORDSIZE == 64 123TEST(SanitizerCommon, SizeClassAllocator64) { 124 TestSizeClassAllocator<Allocator64>(); 125} 126 127TEST(SanitizerCommon, SizeClassAllocator64Compact) { 128 TestSizeClassAllocator<Allocator64Compact>(); 129} 130#endif 131 132TEST(SanitizerCommon, SizeClassAllocator32Compact) { 133 TestSizeClassAllocator<Allocator32Compact>(); 134} 135 136template <class Allocator> 137void SizeClassAllocatorMetadataStress() { 138 Allocator *a = new Allocator; 139 a->Init(); 140 SizeClassAllocatorLocalCache<Allocator> cache; 141 memset(&cache, 0, sizeof(cache)); 142 cache.Init(0); 143 static volatile void *sink; 144 145 const uptr kNumAllocs = 10000; 146 void *allocated[kNumAllocs]; 147 for (uptr i = 0; i < kNumAllocs; i++) { 148 void *x = cache.Allocate(a, 1 + i % 50); 149 allocated[i] = x; 150 } 151 // Get Metadata kNumAllocs^2 times. 152 for (uptr i = 0; i < kNumAllocs * kNumAllocs; i++) { 153 sink = a->GetMetaData(allocated[i % kNumAllocs]); 154 } 155 for (uptr i = 0; i < kNumAllocs; i++) { 156 cache.Deallocate(a, 1 + i % 50, allocated[i]); 157 } 158 159 a->TestOnlyUnmap(); 160 (void)sink; 161 delete a; 162} 163 164#if SANITIZER_WORDSIZE == 64 165TEST(SanitizerCommon, SizeClassAllocator64MetadataStress) { 166 SizeClassAllocatorMetadataStress<Allocator64>(); 167} 168 169TEST(SanitizerCommon, SizeClassAllocator64CompactMetadataStress) { 170 SizeClassAllocatorMetadataStress<Allocator64Compact>(); 171} 172#endif 173TEST(SanitizerCommon, SizeClassAllocator32CompactMetadataStress) { 174 SizeClassAllocatorMetadataStress<Allocator32Compact>(); 175} 176 177struct TestMapUnmapCallback { 178 static int map_count, unmap_count; 179 void OnMap(uptr p, uptr size) const { map_count++; } 180 void OnUnmap(uptr p, uptr size) const { unmap_count++; } 181}; 182int TestMapUnmapCallback::map_count; 183int TestMapUnmapCallback::unmap_count; 184 185#if SANITIZER_WORDSIZE == 64 186TEST(SanitizerCommon, SizeClassAllocator64MapUnmapCallback) { 187 TestMapUnmapCallback::map_count = 0; 188 TestMapUnmapCallback::unmap_count = 0; 189 typedef SizeClassAllocator64< 190 kAllocatorSpace, kAllocatorSize, 16, DefaultSizeClassMap, 191 TestMapUnmapCallback> Allocator64WithCallBack; 192 Allocator64WithCallBack *a = new Allocator64WithCallBack; 193 a->Init(); 194 EXPECT_EQ(TestMapUnmapCallback::map_count, 1); // Allocator state. 195 SizeClassAllocatorLocalCache<Allocator64WithCallBack> cache; 196 memset(&cache, 0, sizeof(cache)); 197 cache.Init(0); 198 AllocatorStats stats; 199 stats.Init(); 200 a->AllocateBatch(&stats, &cache, 64); 201 EXPECT_EQ(TestMapUnmapCallback::map_count, 3); // State + alloc + metadata. 202 a->TestOnlyUnmap(); 203 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1); // The whole thing. 204 delete a; 205} 206#endif 207 208TEST(SanitizerCommon, SizeClassAllocator32MapUnmapCallback) { 209 TestMapUnmapCallback::map_count = 0; 210 TestMapUnmapCallback::unmap_count = 0; 211 typedef SizeClassAllocator32< 212 0, kAddressSpaceSize, 16, CompactSizeClassMap, 213 TestMapUnmapCallback> Allocator32WithCallBack; 214 Allocator32WithCallBack *a = new Allocator32WithCallBack; 215 a->Init(); 216 EXPECT_EQ(TestMapUnmapCallback::map_count, 1); // Allocator state. 217 SizeClassAllocatorLocalCache<Allocator32WithCallBack> cache; 218 memset(&cache, 0, sizeof(cache)); 219 cache.Init(0); 220 AllocatorStats stats; 221 stats.Init(); 222 a->AllocateBatch(&stats, &cache, 64); 223 EXPECT_EQ(TestMapUnmapCallback::map_count, 2); // alloc. 224 a->TestOnlyUnmap(); 225 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 2); // The whole thing + alloc. 226 delete a; 227 // fprintf(stderr, "Map: %d Unmap: %d\n", 228 // TestMapUnmapCallback::map_count, 229 // TestMapUnmapCallback::unmap_count); 230} 231 232TEST(SanitizerCommon, LargeMmapAllocatorMapUnmapCallback) { 233 TestMapUnmapCallback::map_count = 0; 234 TestMapUnmapCallback::unmap_count = 0; 235 LargeMmapAllocator<TestMapUnmapCallback> a; 236 a.Init(); 237 AllocatorStats stats; 238 stats.Init(); 239 void *x = a.Allocate(&stats, 1 << 20, 1); 240 EXPECT_EQ(TestMapUnmapCallback::map_count, 1); 241 a.Deallocate(&stats, x); 242 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1); 243} 244 245template<class Allocator> 246void FailInAssertionOnOOM() { 247 Allocator a; 248 a.Init(); 249 SizeClassAllocatorLocalCache<Allocator> cache; 250 memset(&cache, 0, sizeof(cache)); 251 cache.Init(0); 252 AllocatorStats stats; 253 stats.Init(); 254 for (int i = 0; i < 1000000; i++) { 255 a.AllocateBatch(&stats, &cache, 64); 256 } 257 258 a.TestOnlyUnmap(); 259} 260 261#if SANITIZER_WORDSIZE == 64 262TEST(SanitizerCommon, SizeClassAllocator64Overflow) { 263 EXPECT_DEATH(FailInAssertionOnOOM<Allocator64>(), "Out of memory"); 264} 265#endif 266 267TEST(SanitizerCommon, LargeMmapAllocator) { 268 LargeMmapAllocator<> a; 269 a.Init(); 270 AllocatorStats stats; 271 stats.Init(); 272 273 static const int kNumAllocs = 1000; 274 char *allocated[kNumAllocs]; 275 static const uptr size = 4000; 276 // Allocate some. 277 for (int i = 0; i < kNumAllocs; i++) { 278 allocated[i] = (char *)a.Allocate(&stats, size, 1); 279 CHECK(a.PointerIsMine(allocated[i])); 280 } 281 // Deallocate all. 282 CHECK_GT(a.TotalMemoryUsed(), size * kNumAllocs); 283 for (int i = 0; i < kNumAllocs; i++) { 284 char *p = allocated[i]; 285 CHECK(a.PointerIsMine(p)); 286 a.Deallocate(&stats, p); 287 } 288 // Check that non left. 289 CHECK_EQ(a.TotalMemoryUsed(), 0); 290 291 // Allocate some more, also add metadata. 292 for (int i = 0; i < kNumAllocs; i++) { 293 char *x = (char *)a.Allocate(&stats, size, 1); 294 CHECK_GE(a.GetActuallyAllocatedSize(x), size); 295 uptr *meta = reinterpret_cast<uptr*>(a.GetMetaData(x)); 296 *meta = i; 297 allocated[i] = x; 298 } 299 for (int i = 0; i < kNumAllocs * kNumAllocs; i++) { 300 char *p = allocated[i % kNumAllocs]; 301 CHECK(a.PointerIsMine(p)); 302 CHECK(a.PointerIsMine(p + 2000)); 303 } 304 CHECK_GT(a.TotalMemoryUsed(), size * kNumAllocs); 305 // Deallocate all in reverse order. 306 for (int i = 0; i < kNumAllocs; i++) { 307 int idx = kNumAllocs - i - 1; 308 char *p = allocated[idx]; 309 uptr *meta = reinterpret_cast<uptr*>(a.GetMetaData(p)); 310 CHECK_EQ(*meta, idx); 311 CHECK(a.PointerIsMine(p)); 312 a.Deallocate(&stats, p); 313 } 314 CHECK_EQ(a.TotalMemoryUsed(), 0); 315 316 // Test alignments. 317 uptr max_alignment = SANITIZER_WORDSIZE == 64 ? (1 << 28) : (1 << 24); 318 for (uptr alignment = 8; alignment <= max_alignment; alignment *= 2) { 319 const uptr kNumAlignedAllocs = 100; 320 for (uptr i = 0; i < kNumAlignedAllocs; i++) { 321 uptr size = ((i % 10) + 1) * 4096; 322 char *p = allocated[i] = (char *)a.Allocate(&stats, size, alignment); 323 CHECK_EQ(p, a.GetBlockBegin(p)); 324 CHECK_EQ(p, a.GetBlockBegin(p + size - 1)); 325 CHECK_EQ(p, a.GetBlockBegin(p + size / 2)); 326 CHECK_EQ(0, (uptr)allocated[i] % alignment); 327 p[0] = p[size - 1] = 0; 328 } 329 for (uptr i = 0; i < kNumAlignedAllocs; i++) { 330 a.Deallocate(&stats, allocated[i]); 331 } 332 } 333} 334 335template 336<class PrimaryAllocator, class SecondaryAllocator, class AllocatorCache> 337void TestCombinedAllocator() { 338 typedef 339 CombinedAllocator<PrimaryAllocator, AllocatorCache, SecondaryAllocator> 340 Allocator; 341 Allocator *a = new Allocator; 342 a->Init(); 343 344 AllocatorCache cache; 345 memset(&cache, 0, sizeof(cache)); 346 a->InitCache(&cache); 347 348 EXPECT_EQ(a->Allocate(&cache, -1, 1), (void*)0); 349 EXPECT_EQ(a->Allocate(&cache, -1, 1024), (void*)0); 350 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1024, 1), (void*)0); 351 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1024, 1024), (void*)0); 352 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1023, 1024), (void*)0); 353 354 const uptr kNumAllocs = 100000; 355 const uptr kNumIter = 10; 356 for (uptr iter = 0; iter < kNumIter; iter++) { 357 std::vector<void*> allocated; 358 for (uptr i = 0; i < kNumAllocs; i++) { 359 uptr size = (i % (1 << 14)) + 1; 360 if ((i % 1024) == 0) 361 size = 1 << (10 + (i % 14)); 362 void *x = a->Allocate(&cache, size, 1); 363 uptr *meta = reinterpret_cast<uptr*>(a->GetMetaData(x)); 364 CHECK_EQ(*meta, 0); 365 *meta = size; 366 allocated.push_back(x); 367 } 368 369 random_shuffle(allocated.begin(), allocated.end()); 370 371 for (uptr i = 0; i < kNumAllocs; i++) { 372 void *x = allocated[i]; 373 uptr *meta = reinterpret_cast<uptr*>(a->GetMetaData(x)); 374 CHECK_NE(*meta, 0); 375 CHECK(a->PointerIsMine(x)); 376 *meta = 0; 377 a->Deallocate(&cache, x); 378 } 379 allocated.clear(); 380 a->SwallowCache(&cache); 381 } 382 a->DestroyCache(&cache); 383 a->TestOnlyUnmap(); 384} 385 386#if SANITIZER_WORDSIZE == 64 387TEST(SanitizerCommon, CombinedAllocator64) { 388 TestCombinedAllocator<Allocator64, 389 LargeMmapAllocator<>, 390 SizeClassAllocatorLocalCache<Allocator64> > (); 391} 392 393TEST(SanitizerCommon, CombinedAllocator64Compact) { 394 TestCombinedAllocator<Allocator64Compact, 395 LargeMmapAllocator<>, 396 SizeClassAllocatorLocalCache<Allocator64Compact> > (); 397} 398#endif 399 400TEST(SanitizerCommon, CombinedAllocator32Compact) { 401 TestCombinedAllocator<Allocator32Compact, 402 LargeMmapAllocator<>, 403 SizeClassAllocatorLocalCache<Allocator32Compact> > (); 404} 405 406template <class AllocatorCache> 407void TestSizeClassAllocatorLocalCache() { 408 AllocatorCache cache; 409 typedef typename AllocatorCache::Allocator Allocator; 410 Allocator *a = new Allocator(); 411 412 a->Init(); 413 memset(&cache, 0, sizeof(cache)); 414 cache.Init(0); 415 416 const uptr kNumAllocs = 10000; 417 const int kNumIter = 100; 418 uptr saved_total = 0; 419 for (int class_id = 1; class_id <= 5; class_id++) { 420 for (int it = 0; it < kNumIter; it++) { 421 void *allocated[kNumAllocs]; 422 for (uptr i = 0; i < kNumAllocs; i++) { 423 allocated[i] = cache.Allocate(a, class_id); 424 } 425 for (uptr i = 0; i < kNumAllocs; i++) { 426 cache.Deallocate(a, class_id, allocated[i]); 427 } 428 cache.Drain(a); 429 uptr total_allocated = a->TotalMemoryUsed(); 430 if (it) 431 CHECK_EQ(saved_total, total_allocated); 432 saved_total = total_allocated; 433 } 434 } 435 436 a->TestOnlyUnmap(); 437 delete a; 438} 439 440#if SANITIZER_WORDSIZE == 64 441TEST(SanitizerCommon, SizeClassAllocator64LocalCache) { 442 TestSizeClassAllocatorLocalCache< 443 SizeClassAllocatorLocalCache<Allocator64> >(); 444} 445 446TEST(SanitizerCommon, SizeClassAllocator64CompactLocalCache) { 447 TestSizeClassAllocatorLocalCache< 448 SizeClassAllocatorLocalCache<Allocator64Compact> >(); 449} 450#endif 451 452TEST(SanitizerCommon, SizeClassAllocator32CompactLocalCache) { 453 TestSizeClassAllocatorLocalCache< 454 SizeClassAllocatorLocalCache<Allocator32Compact> >(); 455} 456 457#if SANITIZER_WORDSIZE == 64 458typedef SizeClassAllocatorLocalCache<Allocator64> AllocatorCache; 459static AllocatorCache static_allocator_cache; 460 461void *AllocatorLeakTestWorker(void *arg) { 462 typedef AllocatorCache::Allocator Allocator; 463 Allocator *a = (Allocator*)(arg); 464 static_allocator_cache.Allocate(a, 10); 465 static_allocator_cache.Drain(a); 466 return 0; 467} 468 469TEST(SanitizerCommon, AllocatorLeakTest) { 470 typedef AllocatorCache::Allocator Allocator; 471 Allocator a; 472 a.Init(); 473 uptr total_used_memory = 0; 474 for (int i = 0; i < 100; i++) { 475 pthread_t t; 476 EXPECT_EQ(0, pthread_create(&t, 0, AllocatorLeakTestWorker, &a)); 477 EXPECT_EQ(0, pthread_join(t, 0)); 478 if (i == 0) 479 total_used_memory = a.TotalMemoryUsed(); 480 EXPECT_EQ(a.TotalMemoryUsed(), total_used_memory); 481 } 482 483 a.TestOnlyUnmap(); 484} 485#endif 486 487TEST(Allocator, Basic) { 488 char *p = (char*)InternalAlloc(10); 489 EXPECT_NE(p, (char*)0); 490 char *p2 = (char*)InternalAlloc(20); 491 EXPECT_NE(p2, (char*)0); 492 EXPECT_NE(p2, p); 493 InternalFree(p); 494 InternalFree(p2); 495} 496 497TEST(Allocator, Stress) { 498 const int kCount = 1000; 499 char *ptrs[kCount]; 500 unsigned rnd = 42; 501 for (int i = 0; i < kCount; i++) { 502 uptr sz = my_rand_r(&rnd) % 1000; 503 char *p = (char*)InternalAlloc(sz); 504 EXPECT_NE(p, (char*)0); 505 ptrs[i] = p; 506 } 507 for (int i = 0; i < kCount; i++) { 508 InternalFree(ptrs[i]); 509 } 510} 511 512TEST(Allocator, ScopedBuffer) { 513 const int kSize = 512; 514 { 515 InternalScopedBuffer<int> int_buf(kSize); 516 EXPECT_EQ(sizeof(int) * kSize, int_buf.size()); // NOLINT 517 } 518 InternalScopedBuffer<char> char_buf(kSize); 519 EXPECT_EQ(sizeof(char) * kSize, char_buf.size()); // NOLINT 520 internal_memset(char_buf.data(), 'c', kSize); 521 for (int i = 0; i < kSize; i++) { 522 EXPECT_EQ('c', char_buf[i]); 523 } 524} 525 526#endif // #if TSAN_DEBUG==0 527