1439 lines · cpp
1//===-- sanitizer_allocator_test.cpp --------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of ThreadSanitizer/AddressSanitizer runtime.10// Tests for sanitizer_allocator.h.11//12//===----------------------------------------------------------------------===//13#include "sanitizer_common/sanitizer_allocator.h"14 15#include <stdio.h>16#include <stdlib.h>17 18#include <algorithm>19#include <random>20#include <set>21#include <vector>22 23#include "gtest/gtest.h"24#include "sanitizer_common/sanitizer_allocator_internal.h"25#include "sanitizer_common/sanitizer_common.h"26#include "sanitizer_pthread_wrappers.h"27#include "sanitizer_test_utils.h"28 29using namespace __sanitizer;30 31#if defined(__sparcv9)32// FIXME: These tests probably fail because Solaris/sparcv9 uses the full33// 64-bit address space. Same on Linux/sparc64, so probably a general SPARC34// issue. Needs more investigation35# define SKIP_ON_SPARCV9(x) DISABLED_##x36#else37# define SKIP_ON_SPARCV9(x) x38#endif39 40// On 64-bit systems with small virtual address spaces (e.g. 39-bit) we can't41// use size class maps with a large number of classes, as that will make the42// SizeClassAllocator64 region size too small (< 2^32).43#if SANITIZER_ANDROID && defined(__aarch64__)44#define ALLOCATOR64_SMALL_SIZE 145#elif SANITIZER_RISCV6446#define ALLOCATOR64_SMALL_SIZE 147#else48#define ALLOCATOR64_SMALL_SIZE 049#endif50 51// Too slow for debug build52#if !SANITIZER_DEBUG53 54#if SANITIZER_CAN_USE_ALLOCATOR6455#if SANITIZER_WINDOWS56// On Windows 64-bit there is no easy way to find a large enough fixed address57// space that is always available. Thus, a dynamically allocated address space58// is used instead (i.e. ~(uptr)0).59static const uptr kAllocatorSpace = ~(uptr)0;60static const uptr kAllocatorSize = 0x8000000000ULL; // 500G61static const u64 kAddressSpaceSize = 1ULL << 47;62typedef DefaultSizeClassMap SizeClassMap;63#elif SANITIZER_ANDROID && defined(__aarch64__)64static const uptr kAllocatorSpace = 0x3000000000ULL;65static const uptr kAllocatorSize = 0x2000000000ULL;66static const u64 kAddressSpaceSize = 1ULL << 39;67typedef VeryCompactSizeClassMap SizeClassMap;68#elif SANITIZER_RISCV6469const uptr kAllocatorSpace = ~(uptr)0;70const uptr kAllocatorSize = 0x2000000000ULL; // 128G.71static const u64 kAddressSpaceSize = 1ULL << 38;72typedef VeryDenseSizeClassMap SizeClassMap;73# elif SANITIZER_APPLE74static const uptr kAllocatorSpace = 0x700000000000ULL;75static const uptr kAllocatorSize = 0x010000000000ULL; // 1T.76static const u64 kAddressSpaceSize = 1ULL << 47;77typedef DefaultSizeClassMap SizeClassMap;78# else79static const uptr kAllocatorSpace = 0x500000000000ULL;80static const uptr kAllocatorSize = 0x010000000000ULL; // 1T.81static const u64 kAddressSpaceSize = 1ULL << 47;82typedef DefaultSizeClassMap SizeClassMap;83# endif84 85template <typename AddressSpaceViewTy>86struct AP64 { // Allocator Params. Short name for shorter demangled names..87 static const uptr kSpaceBeg = kAllocatorSpace;88 static const uptr kSpaceSize = kAllocatorSize;89 static const uptr kMetadataSize = 16;90 typedef ::SizeClassMap SizeClassMap;91 typedef NoOpMapUnmapCallback MapUnmapCallback;92 static const uptr kFlags = 0;93 using AddressSpaceView = AddressSpaceViewTy;94};95 96template <typename AddressSpaceViewTy>97struct AP64Dyn {98 static const uptr kSpaceBeg = ~(uptr)0;99 static const uptr kSpaceSize = kAllocatorSize;100 static const uptr kMetadataSize = 16;101 typedef ::SizeClassMap SizeClassMap;102 typedef NoOpMapUnmapCallback MapUnmapCallback;103 static const uptr kFlags = 0;104 using AddressSpaceView = AddressSpaceViewTy;105};106 107template <typename AddressSpaceViewTy>108struct AP64Compact {109 static const uptr kSpaceBeg = ~(uptr)0;110 static const uptr kSpaceSize = kAllocatorSize;111 static const uptr kMetadataSize = 16;112 typedef CompactSizeClassMap SizeClassMap;113 typedef NoOpMapUnmapCallback MapUnmapCallback;114 static const uptr kFlags = 0;115 using AddressSpaceView = AddressSpaceViewTy;116};117 118template <typename AddressSpaceViewTy>119struct AP64VeryCompact {120 static const uptr kSpaceBeg = ~(uptr)0;121 static const uptr kSpaceSize = 1ULL << 37;122 static const uptr kMetadataSize = 16;123 typedef VeryCompactSizeClassMap SizeClassMap;124 typedef NoOpMapUnmapCallback MapUnmapCallback;125 static const uptr kFlags = 0;126 using AddressSpaceView = AddressSpaceViewTy;127};128 129template <typename AddressSpaceViewTy>130struct AP64Dense {131 static const uptr kSpaceBeg = kAllocatorSpace;132 static const uptr kSpaceSize = kAllocatorSize;133 static const uptr kMetadataSize = 16;134 typedef DenseSizeClassMap SizeClassMap;135 typedef NoOpMapUnmapCallback MapUnmapCallback;136 static const uptr kFlags = 0;137 using AddressSpaceView = AddressSpaceViewTy;138};139 140template <typename AddressSpaceView>141using Allocator64ASVT = SizeClassAllocator64<AP64<AddressSpaceView>>;142using Allocator64 = Allocator64ASVT<LocalAddressSpaceView>;143 144template <typename AddressSpaceView>145using Allocator64DynamicASVT = SizeClassAllocator64<AP64Dyn<AddressSpaceView>>;146using Allocator64Dynamic = Allocator64DynamicASVT<LocalAddressSpaceView>;147 148template <typename AddressSpaceView>149using Allocator64CompactASVT =150 SizeClassAllocator64<AP64Compact<AddressSpaceView>>;151using Allocator64Compact = Allocator64CompactASVT<LocalAddressSpaceView>;152 153template <typename AddressSpaceView>154using Allocator64VeryCompactASVT =155 SizeClassAllocator64<AP64VeryCompact<AddressSpaceView>>;156using Allocator64VeryCompact =157 Allocator64VeryCompactASVT<LocalAddressSpaceView>;158 159template <typename AddressSpaceView>160using Allocator64DenseASVT = SizeClassAllocator64<AP64Dense<AddressSpaceView>>;161using Allocator64Dense = Allocator64DenseASVT<LocalAddressSpaceView>;162 163#elif defined(__mips64)164static const u64 kAddressSpaceSize = 1ULL << 40;165#elif defined(__aarch64__)166static const u64 kAddressSpaceSize = 1ULL << 39;167#elif defined(__s390x__)168static const u64 kAddressSpaceSize = 1ULL << 53;169#elif defined(__s390__)170static const u64 kAddressSpaceSize = 1ULL << 31;171#else172static const u64 kAddressSpaceSize = 1ULL << 32;173#endif174 175static const uptr kRegionSizeLog = FIRST_32_SECOND_64(20, 24);176 177template <typename AddressSpaceViewTy>178struct AP32Compact {179 static const uptr kSpaceBeg = 0;180 static const u64 kSpaceSize = kAddressSpaceSize;181 static const uptr kMetadataSize = 16;182 typedef CompactSizeClassMap SizeClassMap;183 static const uptr kRegionSizeLog = ::kRegionSizeLog;184 using AddressSpaceView = AddressSpaceViewTy;185 typedef NoOpMapUnmapCallback MapUnmapCallback;186 static const uptr kFlags = 0;187};188template <typename AddressSpaceView>189using Allocator32CompactASVT =190 SizeClassAllocator32<AP32Compact<AddressSpaceView>>;191using Allocator32Compact = Allocator32CompactASVT<LocalAddressSpaceView>;192 193template <class SizeClassMap>194void TestSizeClassMap() {195 typedef SizeClassMap SCMap;196 SCMap::Print();197 SCMap::Validate();198}199 200TEST(SanitizerCommon, DefaultSizeClassMap) {201 TestSizeClassMap<DefaultSizeClassMap>();202}203 204TEST(SanitizerCommon, CompactSizeClassMap) {205 TestSizeClassMap<CompactSizeClassMap>();206}207 208TEST(SanitizerCommon, VeryCompactSizeClassMap) {209 TestSizeClassMap<VeryCompactSizeClassMap>();210}211 212TEST(SanitizerCommon, InternalSizeClassMap) {213 TestSizeClassMap<InternalSizeClassMap>();214}215 216TEST(SanitizerCommon, DenseSizeClassMap) {217 TestSizeClassMap<VeryCompactSizeClassMap>();218}219 220template <class Allocator>221void TestSizeClassAllocator(uptr premapped_heap = 0) {222 Allocator *a = new Allocator;223 a->Init(kReleaseToOSIntervalNever, premapped_heap);224 typename Allocator::AllocatorCache cache;225 memset(&cache, 0, sizeof(cache));226 cache.Init(0);227 228 static const uptr sizes[] = {229 1, 16, 30, 40, 100, 1000, 10000,230 50000, 60000, 100000, 120000, 300000, 500000, 1000000, 2000000231 };232 233 std::vector<void *> allocated;234 235 uptr last_total_allocated = 0;236 for (int i = 0; i < 3; i++) {237 // Allocate a bunch of chunks.238 for (uptr s = 0; s < ARRAY_SIZE(sizes); s++) {239 uptr size = sizes[s];240 if (!a->CanAllocate(size, 1)) continue;241 // printf("s = %ld\n", size);242 uptr n_iter = std::max((uptr)6, 4000000 / size);243 // fprintf(stderr, "size: %ld iter: %ld\n", size, n_iter);244 for (uptr i = 0; i < n_iter; i++) {245 uptr class_id0 = Allocator::SizeClassMapT::ClassID(size);246 char *x = (char*)cache.Allocate(a, class_id0);247 x[0] = 0;248 x[size - 1] = 0;249 x[size / 2] = 0;250 allocated.push_back(x);251 CHECK_EQ(x, a->GetBlockBegin(x));252 CHECK_EQ(x, a->GetBlockBegin(x + size - 1));253 CHECK(a->PointerIsMine(x));254 CHECK(a->PointerIsMine(x + size - 1));255 CHECK(a->PointerIsMine(x + size / 2));256 CHECK_GE(a->GetActuallyAllocatedSize(x), size);257 uptr class_id = a->GetSizeClass(x);258 CHECK_EQ(class_id, Allocator::SizeClassMapT::ClassID(size));259 uptr *metadata = reinterpret_cast<uptr*>(a->GetMetaData(x));260 metadata[0] = reinterpret_cast<uptr>(x) + 1;261 metadata[1] = 0xABCD;262 }263 }264 // Deallocate all.265 for (uptr i = 0; i < allocated.size(); i++) {266 void *x = allocated[i];267 uptr *metadata = reinterpret_cast<uptr*>(a->GetMetaData(x));268 CHECK_EQ(metadata[0], reinterpret_cast<uptr>(x) + 1);269 CHECK_EQ(metadata[1], 0xABCD);270 cache.Deallocate(a, a->GetSizeClass(x), x);271 }272 allocated.clear();273 uptr total_allocated = a->TotalMemoryUsed();274 if (last_total_allocated == 0)275 last_total_allocated = total_allocated;276 CHECK_EQ(last_total_allocated, total_allocated);277 }278 279 // Check that GetBlockBegin never crashes.280 for (uptr x = 0, step = kAddressSpaceSize / 100000;281 x < kAddressSpaceSize - step; x += step)282 if (a->PointerIsMine(reinterpret_cast<void *>(x)))283 Ident(a->GetBlockBegin(reinterpret_cast<void *>(x)));284 285 a->TestOnlyUnmap();286 delete a;287}288 289#if SANITIZER_CAN_USE_ALLOCATOR64290 291// Allocates kAllocatorSize aligned bytes on construction and frees it on292// destruction.293class ScopedPremappedHeap {294 public:295 ScopedPremappedHeap() {296 BasePtr = MmapNoReserveOrDie(2 * kAllocatorSize, "preallocated heap");297 AlignedAddr = RoundUpTo(reinterpret_cast<uptr>(BasePtr), kAllocatorSize);298 }299 300 ~ScopedPremappedHeap() { UnmapOrDie(BasePtr, kAllocatorSize); }301 302 uptr Addr() { return AlignedAddr; }303 304 private:305 void *BasePtr;306 uptr AlignedAddr;307};308 309// These tests can fail on Windows if memory is somewhat full and lit happens310// to run them all at the same time. FIXME: Make them not flaky and reenable.311#if !SANITIZER_WINDOWS312TEST(SanitizerCommon, SizeClassAllocator64) {313 TestSizeClassAllocator<Allocator64>();314}315 316TEST(SanitizerCommon, SizeClassAllocator64Dynamic) {317 TestSizeClassAllocator<Allocator64Dynamic>();318}319 320#if !ALLOCATOR64_SMALL_SIZE321// Android only has 39-bit address space, so mapping 2 * kAllocatorSize322// sometimes fails.323TEST(SanitizerCommon, SizeClassAllocator64DynamicPremapped) {324 ScopedPremappedHeap h;325 TestSizeClassAllocator<Allocator64Dynamic>(h.Addr());326}327 328TEST(SanitizerCommon, SizeClassAllocator64Compact) {329 TestSizeClassAllocator<Allocator64Compact>();330}331 332TEST(SanitizerCommon, SizeClassAllocator64Dense) {333 TestSizeClassAllocator<Allocator64Dense>();334}335#endif336 337TEST(SanitizerCommon, SizeClassAllocator64VeryCompact) {338 TestSizeClassAllocator<Allocator64VeryCompact>();339}340#endif341#endif342 343TEST(SanitizerCommon, SizeClassAllocator32Compact) {344 TestSizeClassAllocator<Allocator32Compact>();345}346 347template <typename AddressSpaceViewTy>348struct AP32SeparateBatches {349 static const uptr kSpaceBeg = 0;350 static const u64 kSpaceSize = kAddressSpaceSize;351 static const uptr kMetadataSize = 16;352 typedef DefaultSizeClassMap SizeClassMap;353 static const uptr kRegionSizeLog = ::kRegionSizeLog;354 using AddressSpaceView = AddressSpaceViewTy;355 typedef NoOpMapUnmapCallback MapUnmapCallback;356 static const uptr kFlags =357 SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch;358};359template <typename AddressSpaceView>360using Allocator32SeparateBatchesASVT =361 SizeClassAllocator32<AP32SeparateBatches<AddressSpaceView>>;362using Allocator32SeparateBatches =363 Allocator32SeparateBatchesASVT<LocalAddressSpaceView>;364 365TEST(SanitizerCommon, SizeClassAllocator32SeparateBatches) {366 TestSizeClassAllocator<Allocator32SeparateBatches>();367}368 369template <class Allocator>370void SizeClassAllocatorMetadataStress(uptr premapped_heap = 0) {371 Allocator *a = new Allocator;372 a->Init(kReleaseToOSIntervalNever, premapped_heap);373 typename Allocator::AllocatorCache cache;374 memset(&cache, 0, sizeof(cache));375 cache.Init(0);376 377 const uptr kNumAllocs = 1 << 13;378 void *allocated[kNumAllocs];379 void *meta[kNumAllocs];380 for (uptr i = 0; i < kNumAllocs; i++) {381 void *x = cache.Allocate(a, 1 + i % (Allocator::kNumClasses - 1));382 allocated[i] = x;383 meta[i] = a->GetMetaData(x);384 }385 // Get Metadata kNumAllocs^2 times.386 for (uptr i = 0; i < kNumAllocs * kNumAllocs; i++) {387 uptr idx = i % kNumAllocs;388 void *m = a->GetMetaData(allocated[idx]);389 EXPECT_EQ(m, meta[idx]);390 }391 for (uptr i = 0; i < kNumAllocs; i++) {392 cache.Deallocate(a, 1 + i % (Allocator::kNumClasses - 1), allocated[i]);393 }394 395 a->TestOnlyUnmap();396 delete a;397}398 399#if SANITIZER_CAN_USE_ALLOCATOR64400// These tests can fail on Windows if memory is somewhat full and lit happens401// to run them all at the same time. FIXME: Make them not flaky and reenable.402#if !SANITIZER_WINDOWS403TEST(SanitizerCommon, SizeClassAllocator64MetadataStress) {404 SizeClassAllocatorMetadataStress<Allocator64>();405}406 407TEST(SanitizerCommon, SizeClassAllocator64DynamicMetadataStress) {408 SizeClassAllocatorMetadataStress<Allocator64Dynamic>();409}410 411#if !ALLOCATOR64_SMALL_SIZE412TEST(SanitizerCommon, SizeClassAllocator64DynamicPremappedMetadataStress) {413 ScopedPremappedHeap h;414 SizeClassAllocatorMetadataStress<Allocator64Dynamic>(h.Addr());415}416 417TEST(SanitizerCommon, SizeClassAllocator64CompactMetadataStress) {418 SizeClassAllocatorMetadataStress<Allocator64Compact>();419}420#endif421 422#endif423#endif // SANITIZER_CAN_USE_ALLOCATOR64424TEST(SanitizerCommon, SizeClassAllocator32CompactMetadataStress) {425 SizeClassAllocatorMetadataStress<Allocator32Compact>();426}427 428template <class Allocator>429void SizeClassAllocatorGetBlockBeginStress(u64 TotalSize,430 uptr premapped_heap = 0) {431 Allocator *a = new Allocator;432 a->Init(kReleaseToOSIntervalNever, premapped_heap);433 typename Allocator::AllocatorCache cache;434 memset(&cache, 0, sizeof(cache));435 cache.Init(0);436 437 uptr max_size_class = Allocator::SizeClassMapT::kLargestClassID;438 uptr size = Allocator::SizeClassMapT::Size(max_size_class);439 // Make sure we correctly compute GetBlockBegin() w/o overflow.440 for (size_t i = 0; i <= TotalSize / size; i++) {441 void *x = cache.Allocate(a, max_size_class);442 void *beg = a->GetBlockBegin(x);443 // if ((i & (i - 1)) == 0)444 // fprintf(stderr, "[%zd] %p %p\n", i, x, beg);445 EXPECT_EQ(x, beg);446 }447 448 a->TestOnlyUnmap();449 delete a;450}451 452#if SANITIZER_CAN_USE_ALLOCATOR64453// These tests can fail on Windows if memory is somewhat full and lit happens454// to run them all at the same time. FIXME: Make them not flaky and reenable.455#if !SANITIZER_WINDOWS456TEST(SanitizerCommon, SizeClassAllocator64GetBlockBegin) {457 SizeClassAllocatorGetBlockBeginStress<Allocator64>(458 1ULL << (SANITIZER_ANDROID ? 31 : 33));459}460TEST(SanitizerCommon, SizeClassAllocator64DynamicGetBlockBegin) {461 SizeClassAllocatorGetBlockBeginStress<Allocator64Dynamic>(462 1ULL << (SANITIZER_ANDROID ? 31 : 33));463}464#if !ALLOCATOR64_SMALL_SIZE465TEST(SanitizerCommon, SizeClassAllocator64DynamicPremappedGetBlockBegin) {466 ScopedPremappedHeap h;467 SizeClassAllocatorGetBlockBeginStress<Allocator64Dynamic>(468 1ULL << (SANITIZER_ANDROID ? 31 : 33), h.Addr());469}470TEST(SanitizerCommon, SizeClassAllocator64CompactGetBlockBegin) {471 SizeClassAllocatorGetBlockBeginStress<Allocator64Compact>(1ULL << 33);472}473#endif474TEST(SanitizerCommon, SizeClassAllocator64VeryCompactGetBlockBegin) {475 // Does not have > 4Gb for each class.476 SizeClassAllocatorGetBlockBeginStress<Allocator64VeryCompact>(1ULL << 31);477}478TEST(SanitizerCommon, SizeClassAllocator32CompactGetBlockBegin) {479 SizeClassAllocatorGetBlockBeginStress<Allocator32Compact>(1ULL << 33);480}481#endif482#endif // SANITIZER_CAN_USE_ALLOCATOR64483 484struct TestMapUnmapCallback {485 static int map_count, map_secondary_count, unmap_count;486 void OnMap(uptr p, uptr size) const { map_count++; }487 void OnMapSecondary(uptr p, uptr size, uptr user_begin,488 uptr user_size) const {489 map_secondary_count++;490 }491 void OnUnmap(uptr p, uptr size) const { unmap_count++; }492 493 static void Reset() { map_count = map_secondary_count = unmap_count = 0; }494};495int TestMapUnmapCallback::map_count;496int TestMapUnmapCallback::map_secondary_count;497int TestMapUnmapCallback::unmap_count;498 499#if SANITIZER_CAN_USE_ALLOCATOR64500// These tests can fail on Windows if memory is somewhat full and lit happens501// to run them all at the same time. FIXME: Make them not flaky and reenable.502#if !SANITIZER_WINDOWS503 504template <typename AddressSpaceViewTy = LocalAddressSpaceView>505struct AP64WithCallback {506 static const uptr kSpaceBeg = kAllocatorSpace;507 static const uptr kSpaceSize = kAllocatorSize;508 static const uptr kMetadataSize = 16;509 typedef ::SizeClassMap SizeClassMap;510 typedef TestMapUnmapCallback MapUnmapCallback;511 static const uptr kFlags = 0;512 using AddressSpaceView = AddressSpaceViewTy;513};514 515TEST(SanitizerCommon, SizeClassAllocator64MapUnmapCallback) {516 TestMapUnmapCallback::Reset();517 typedef SizeClassAllocator64<AP64WithCallback<>> Allocator64WithCallBack;518 Allocator64WithCallBack *a = new Allocator64WithCallBack;519 a->Init(kReleaseToOSIntervalNever);520 EXPECT_EQ(TestMapUnmapCallback::map_count, 1); // Allocator state.521 EXPECT_EQ(TestMapUnmapCallback::map_secondary_count, 0);522 typename Allocator64WithCallBack::AllocatorCache cache;523 memset(&cache, 0, sizeof(cache));524 cache.Init(0);525 AllocatorStats stats;526 stats.Init();527 const size_t kNumChunks = 128;528 uint32_t chunks[kNumChunks];529 a->GetFromAllocator(&stats, 30, chunks, kNumChunks);530 // State + alloc + metadata + freearray.531 EXPECT_EQ(TestMapUnmapCallback::map_count, 4);532 EXPECT_EQ(TestMapUnmapCallback::map_secondary_count, 0);533 a->TestOnlyUnmap();534 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1); // The whole thing.535 delete a;536}537#endif538#endif539 540template <typename AddressSpaceViewTy = LocalAddressSpaceView>541struct AP32WithCallback {542 static const uptr kSpaceBeg = 0;543 static const u64 kSpaceSize = kAddressSpaceSize;544 static const uptr kMetadataSize = 16;545 typedef CompactSizeClassMap SizeClassMap;546 static const uptr kRegionSizeLog = ::kRegionSizeLog;547 using AddressSpaceView = AddressSpaceViewTy;548 typedef TestMapUnmapCallback MapUnmapCallback;549 static const uptr kFlags = 0;550};551 552TEST(SanitizerCommon, SizeClassAllocator32MapUnmapCallback) {553 TestMapUnmapCallback::Reset();554 typedef SizeClassAllocator32<AP32WithCallback<>> Allocator32WithCallBack;555 Allocator32WithCallBack *a = new Allocator32WithCallBack;556 a->Init(kReleaseToOSIntervalNever);557 EXPECT_EQ(TestMapUnmapCallback::map_count, 0);558 EXPECT_EQ(TestMapUnmapCallback::map_secondary_count, 0);559 Allocator32WithCallBack::AllocatorCache cache;560 memset(&cache, 0, sizeof(cache));561 cache.Init(0);562 AllocatorStats stats;563 stats.Init();564 a->AllocateBatch(&stats, &cache, 32);565 EXPECT_EQ(TestMapUnmapCallback::map_count, 1);566 EXPECT_EQ(TestMapUnmapCallback::map_secondary_count, 0);567 a->TestOnlyUnmap();568 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1);569 delete a;570}571 572TEST(SanitizerCommon, LargeMmapAllocatorMapUnmapCallback) {573 TestMapUnmapCallback::Reset();574 LargeMmapAllocator<TestMapUnmapCallback> a;575 a.Init();576 AllocatorStats stats;577 stats.Init();578 void *x = a.Allocate(&stats, 1 << 20, 1);579 EXPECT_EQ(TestMapUnmapCallback::map_count, 0);580 EXPECT_EQ(TestMapUnmapCallback::map_secondary_count, 1);581 a.Deallocate(&stats, x);582 EXPECT_EQ(TestMapUnmapCallback::unmap_count, 1);583}584 585// Don't test OOM conditions on Win64 because it causes other tests on the same586// machine to OOM.587#if SANITIZER_CAN_USE_ALLOCATOR64 && !SANITIZER_WINDOWS64588TEST(SanitizerCommon, SizeClassAllocator64Overflow) {589 Allocator64 a;590 a.Init(kReleaseToOSIntervalNever);591 Allocator64::AllocatorCache cache;592 memset(&cache, 0, sizeof(cache));593 cache.Init(0);594 AllocatorStats stats;595 stats.Init();596 597 const size_t kNumChunks = 128;598 uint32_t chunks[kNumChunks];599 bool allocation_failed = false;600 for (int i = 0; i < 1000000; i++) {601 uptr class_id = a.kNumClasses - 1;602 if (!a.GetFromAllocator(&stats, class_id, chunks, kNumChunks)) {603 allocation_failed = true;604 break;605 }606 }607 EXPECT_EQ(allocation_failed, true);608 609 a.TestOnlyUnmap();610}611#endif612 613TEST(SanitizerCommon, LargeMmapAllocator) {614 LargeMmapAllocator<NoOpMapUnmapCallback> a;615 a.Init();616 AllocatorStats stats;617 stats.Init();618 619 static const int kNumAllocs = 1000;620 char *allocated[kNumAllocs];621 static const uptr size = 4000;622 // Allocate some.623 for (int i = 0; i < kNumAllocs; i++) {624 allocated[i] = (char *)a.Allocate(&stats, size, 1);625 CHECK(a.PointerIsMine(allocated[i]));626 }627 // Deallocate all.628 CHECK_GT(a.TotalMemoryUsed(), size * kNumAllocs);629 for (int i = 0; i < kNumAllocs; i++) {630 char *p = allocated[i];631 CHECK(a.PointerIsMine(p));632 a.Deallocate(&stats, p);633 }634 // Check that non left.635 CHECK_EQ(a.TotalMemoryUsed(), 0);636 637 // Allocate some more, also add metadata.638 for (int i = 0; i < kNumAllocs; i++) {639 char *x = (char *)a.Allocate(&stats, size, 1);640 CHECK_GE(a.GetActuallyAllocatedSize(x), size);641 uptr *meta = reinterpret_cast<uptr*>(a.GetMetaData(x));642 *meta = i;643 allocated[i] = x;644 }645 for (int i = 0; i < kNumAllocs * kNumAllocs; i++) {646 char *p = allocated[i % kNumAllocs];647 CHECK(a.PointerIsMine(p));648 CHECK(a.PointerIsMine(p + 2000));649 }650 CHECK_GT(a.TotalMemoryUsed(), size * kNumAllocs);651 // Deallocate all in reverse order.652 for (int i = 0; i < kNumAllocs; i++) {653 int idx = kNumAllocs - i - 1;654 char *p = allocated[idx];655 uptr *meta = reinterpret_cast<uptr*>(a.GetMetaData(p));656 CHECK_EQ(*meta, idx);657 CHECK(a.PointerIsMine(p));658 a.Deallocate(&stats, p);659 }660 CHECK_EQ(a.TotalMemoryUsed(), 0);661 662 // Test alignments. Test with 512MB alignment on x64 non-Windows machines.663 // Windows doesn't overcommit, and many machines do not have 51.2GB of swap.664 uptr max_alignment =665 (SANITIZER_WORDSIZE == 64 && !SANITIZER_WINDOWS) ? (1 << 28) : (1 << 24);666 for (uptr alignment = 8; alignment <= max_alignment; alignment *= 2) {667 const uptr kNumAlignedAllocs = 100;668 for (uptr i = 0; i < kNumAlignedAllocs; i++) {669 uptr size = ((i % 10) + 1) * 4096;670 char *p = allocated[i] = (char *)a.Allocate(&stats, size, alignment);671 CHECK_EQ(p, a.GetBlockBegin(p));672 CHECK_EQ(p, a.GetBlockBegin(p + size - 1));673 CHECK_EQ(p, a.GetBlockBegin(p + size / 2));674 CHECK_EQ(0, (uptr)allocated[i] % alignment);675 p[0] = p[size - 1] = 0;676 }677 for (uptr i = 0; i < kNumAlignedAllocs; i++) {678 a.Deallocate(&stats, allocated[i]);679 }680 }681 682 // Regression test for boundary condition in GetBlockBegin().683 uptr page_size = GetPageSizeCached();684 char *p = (char *)a.Allocate(&stats, page_size, 1);685 CHECK_EQ(p, a.GetBlockBegin(p));686 CHECK_EQ(p, (char *)a.GetBlockBegin(p + page_size - 1));687 CHECK_NE(p, (char *)a.GetBlockBegin(p + page_size));688 a.Deallocate(&stats, p);689}690 691template <class PrimaryAllocator>692void TestCombinedAllocator(uptr premapped_heap = 0) {693 typedef CombinedAllocator<PrimaryAllocator> Allocator;694 Allocator *a = new Allocator;695 a->Init(kReleaseToOSIntervalNever, premapped_heap);696 std::mt19937 r;697 698 typename Allocator::AllocatorCache cache;699 memset(&cache, 0, sizeof(cache));700 a->InitCache(&cache);701 702 EXPECT_EQ(a->Allocate(&cache, -1, 1), (void*)0);703 EXPECT_EQ(a->Allocate(&cache, -1, 1024), (void*)0);704 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1024, 1), (void*)0);705 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1024, 1024), (void*)0);706 EXPECT_EQ(a->Allocate(&cache, (uptr)-1 - 1023, 1024), (void*)0);707 EXPECT_EQ(a->Allocate(&cache, -1, 1), (void*)0);708 709 const uptr kNumAllocs = 100000;710 const uptr kNumIter = 10;711 for (uptr iter = 0; iter < kNumIter; iter++) {712 std::vector<void*> allocated;713 for (uptr i = 0; i < kNumAllocs; i++) {714 uptr size = (i % (1 << 14)) + 1;715 if ((i % 1024) == 0)716 size = 1 << (10 + (i % 14));717 void *x = a->Allocate(&cache, size, 1);718 uptr *meta = reinterpret_cast<uptr*>(a->GetMetaData(x));719 CHECK_EQ(*meta, 0);720 *meta = size;721 allocated.push_back(x);722 }723 724 std::shuffle(allocated.begin(), allocated.end(), r);725 726 // Test ForEachChunk(...)727 {728 std::set<void *> reported_chunks;729 auto cb = [](uptr chunk, void *arg) {730 auto reported_chunks_ptr = reinterpret_cast<std::set<void *> *>(arg);731 auto pair =732 reported_chunks_ptr->insert(reinterpret_cast<void *>(chunk));733 // Check chunk is never reported more than once.734 ASSERT_TRUE(pair.second);735 };736 a->ForEachChunk(cb, reinterpret_cast<void *>(&reported_chunks));737 for (const auto &allocated_ptr : allocated) {738 ASSERT_NE(reported_chunks.find(allocated_ptr), reported_chunks.end());739 }740 }741 742 for (uptr i = 0; i < kNumAllocs; i++) {743 void *x = allocated[i];744 uptr *meta = reinterpret_cast<uptr*>(a->GetMetaData(x));745 CHECK_NE(*meta, 0);746 CHECK(a->PointerIsMine(x));747 *meta = 0;748 a->Deallocate(&cache, x);749 }750 allocated.clear();751 a->SwallowCache(&cache);752 }753 a->DestroyCache(&cache);754 a->TestOnlyUnmap();755}756 757#if SANITIZER_CAN_USE_ALLOCATOR64758TEST(SanitizerCommon, CombinedAllocator64) {759 TestCombinedAllocator<Allocator64>();760}761 762TEST(SanitizerCommon, CombinedAllocator64Dynamic) {763 TestCombinedAllocator<Allocator64Dynamic>();764}765 766#if !ALLOCATOR64_SMALL_SIZE767#if !SANITIZER_WINDOWS768// Windows fails to map 1TB, so disable this test.769TEST(SanitizerCommon, CombinedAllocator64DynamicPremapped) {770 ScopedPremappedHeap h;771 TestCombinedAllocator<Allocator64Dynamic>(h.Addr());772}773#endif774 775TEST(SanitizerCommon, CombinedAllocator64Compact) {776 TestCombinedAllocator<Allocator64Compact>();777}778#endif779 780TEST(SanitizerCommon, CombinedAllocator64VeryCompact) {781 TestCombinedAllocator<Allocator64VeryCompact>();782}783#endif784 785TEST(SanitizerCommon, SKIP_ON_SPARCV9(CombinedAllocator32Compact)) {786 TestCombinedAllocator<Allocator32Compact>();787}788 789template <class Allocator>790void TestSizeClassAllocatorLocalCache(uptr premapped_heap = 0) {791 using AllocatorCache = typename Allocator::AllocatorCache;792 AllocatorCache cache;793 Allocator *a = new Allocator();794 795 a->Init(kReleaseToOSIntervalNever, premapped_heap);796 memset(&cache, 0, sizeof(cache));797 cache.Init(0);798 799 const uptr kNumAllocs = 10000;800 const int kNumIter = 100;801 uptr saved_total = 0;802 for (int class_id = 1; class_id <= 5; class_id++) {803 for (int it = 0; it < kNumIter; it++) {804 void *allocated[kNumAllocs];805 for (uptr i = 0; i < kNumAllocs; i++) {806 allocated[i] = cache.Allocate(a, class_id);807 }808 for (uptr i = 0; i < kNumAllocs; i++) {809 cache.Deallocate(a, class_id, allocated[i]);810 }811 cache.Drain(a);812 uptr total_allocated = a->TotalMemoryUsed();813 if (it)814 CHECK_EQ(saved_total, total_allocated);815 saved_total = total_allocated;816 }817 }818 819 a->TestOnlyUnmap();820 delete a;821}822 823#if SANITIZER_CAN_USE_ALLOCATOR64824// These tests can fail on Windows if memory is somewhat full and lit happens825// to run them all at the same time. FIXME: Make them not flaky and reenable.826#if !SANITIZER_WINDOWS827TEST(SanitizerCommon, SizeClassAllocator64LocalCache) {828 TestSizeClassAllocatorLocalCache<Allocator64>();829}830 831TEST(SanitizerCommon, SizeClassAllocator64DynamicLocalCache) {832 TestSizeClassAllocatorLocalCache<Allocator64Dynamic>();833}834 835#if !ALLOCATOR64_SMALL_SIZE836TEST(SanitizerCommon, SizeClassAllocator64DynamicPremappedLocalCache) {837 ScopedPremappedHeap h;838 TestSizeClassAllocatorLocalCache<Allocator64Dynamic>(h.Addr());839}840 841TEST(SanitizerCommon, SizeClassAllocator64CompactLocalCache) {842 TestSizeClassAllocatorLocalCache<Allocator64Compact>();843}844#endif845TEST(SanitizerCommon, SizeClassAllocator64VeryCompactLocalCache) {846 TestSizeClassAllocatorLocalCache<Allocator64VeryCompact>();847}848#endif849#endif850 851TEST(SanitizerCommon, SizeClassAllocator32CompactLocalCache) {852 TestSizeClassAllocatorLocalCache<Allocator32Compact>();853}854 855#if SANITIZER_CAN_USE_ALLOCATOR64856typedef Allocator64::AllocatorCache AllocatorCache;857static AllocatorCache static_allocator_cache;858 859void *AllocatorLeakTestWorker(void *arg) {860 typedef AllocatorCache::Allocator Allocator;861 Allocator *a = (Allocator*)(arg);862 static_allocator_cache.Allocate(a, 10);863 static_allocator_cache.Drain(a);864 return 0;865}866 867TEST(SanitizerCommon, AllocatorLeakTest) {868 typedef AllocatorCache::Allocator Allocator;869 Allocator a;870 a.Init(kReleaseToOSIntervalNever);871 uptr total_used_memory = 0;872 for (int i = 0; i < 100; i++) {873 pthread_t t;874 PTHREAD_CREATE(&t, 0, AllocatorLeakTestWorker, &a);875 PTHREAD_JOIN(t, 0);876 if (i == 0)877 total_used_memory = a.TotalMemoryUsed();878 EXPECT_EQ(a.TotalMemoryUsed(), total_used_memory);879 }880 881 a.TestOnlyUnmap();882}883 884// Struct which is allocated to pass info to new threads. The new thread frees885// it.886struct NewThreadParams {887 AllocatorCache *thread_cache;888 AllocatorCache::Allocator *allocator;889 uptr class_id;890};891 892// Called in a new thread. Just frees its argument.893static void *DeallocNewThreadWorker(void *arg) {894 NewThreadParams *params = reinterpret_cast<NewThreadParams*>(arg);895 params->thread_cache->Deallocate(params->allocator, params->class_id, params);896 return NULL;897}898 899// The allocator cache is supposed to be POD and zero initialized. We should be900// able to call Deallocate on a zeroed cache, and it will self-initialize.901TEST(Allocator, AllocatorCacheDeallocNewThread) {902 AllocatorCache::Allocator allocator;903 allocator.Init(kReleaseToOSIntervalNever);904 AllocatorCache main_cache;905 AllocatorCache child_cache;906 memset(&main_cache, 0, sizeof(main_cache));907 memset(&child_cache, 0, sizeof(child_cache));908 909 uptr class_id = DefaultSizeClassMap::ClassID(sizeof(NewThreadParams));910 NewThreadParams *params = reinterpret_cast<NewThreadParams*>(911 main_cache.Allocate(&allocator, class_id));912 params->thread_cache = &child_cache;913 params->allocator = &allocator;914 params->class_id = class_id;915 pthread_t t;916 PTHREAD_CREATE(&t, 0, DeallocNewThreadWorker, params);917 PTHREAD_JOIN(t, 0);918 919 allocator.TestOnlyUnmap();920}921#endif922 923TEST(Allocator, Basic) {924 char *p = (char*)InternalAlloc(10);925 EXPECT_NE(p, (char*)0);926 char *p2 = (char*)InternalAlloc(20);927 EXPECT_NE(p2, (char*)0);928 EXPECT_NE(p2, p);929 InternalFree(p);930 InternalFree(p2);931}932 933TEST(Allocator, Stress) {934 const int kCount = 1000;935 char *ptrs[kCount];936 unsigned rnd = 42;937 for (int i = 0; i < kCount; i++) {938 uptr sz = my_rand_r(&rnd) % 1000;939 char *p = (char*)InternalAlloc(sz);940 EXPECT_NE(p, (char*)0);941 ptrs[i] = p;942 }943 for (int i = 0; i < kCount; i++) {944 InternalFree(ptrs[i]);945 }946}947 948TEST(Allocator, LargeAlloc) {949 void *p = InternalAlloc(10 << 20);950 InternalFree(p);951}952 953TEST(Allocator, ScopedBuffer) {954 const int kSize = 512;955 {956 InternalMmapVector<int> int_buf(kSize);957 EXPECT_EQ((uptr)kSize, int_buf.size());958 }959 InternalMmapVector<char> char_buf(kSize);960 EXPECT_EQ((uptr)kSize, char_buf.size());961 internal_memset(char_buf.data(), 'c', kSize);962 for (int i = 0; i < kSize; i++) {963 EXPECT_EQ('c', char_buf[i]);964 }965}966 967void IterationTestCallback(uptr chunk, void *arg) {968 reinterpret_cast<std::set<uptr> *>(arg)->insert(chunk);969}970 971template <class Allocator>972void TestSizeClassAllocatorIteration(uptr premapped_heap = 0) {973 Allocator *a = new Allocator;974 a->Init(kReleaseToOSIntervalNever, premapped_heap);975 typename Allocator::AllocatorCache cache;976 memset(&cache, 0, sizeof(cache));977 cache.Init(0);978 979 static const uptr sizes[] = {1, 16, 30, 40, 100, 1000, 10000,980 50000, 60000, 100000, 120000, 300000, 500000, 1000000, 2000000};981 982 std::vector<void *> allocated;983 984 // Allocate a bunch of chunks.985 for (uptr s = 0; s < ARRAY_SIZE(sizes); s++) {986 uptr size = sizes[s];987 if (!a->CanAllocate(size, 1)) continue;988 // printf("s = %ld\n", size);989 uptr n_iter = std::max((uptr)6, 80000 / size);990 // fprintf(stderr, "size: %ld iter: %ld\n", size, n_iter);991 for (uptr j = 0; j < n_iter; j++) {992 uptr class_id0 = Allocator::SizeClassMapT::ClassID(size);993 void *x = cache.Allocate(a, class_id0);994 allocated.push_back(x);995 }996 }997 998 std::set<uptr> reported_chunks;999 a->ForceLock();1000 a->ForEachChunk(IterationTestCallback, &reported_chunks);1001 a->ForceUnlock();1002 1003 for (uptr i = 0; i < allocated.size(); i++) {1004 // Don't use EXPECT_NE. Reporting the first mismatch is enough.1005 ASSERT_NE(reported_chunks.find(reinterpret_cast<uptr>(allocated[i])),1006 reported_chunks.end());1007 }1008 1009 a->TestOnlyUnmap();1010 delete a;1011}1012 1013#if SANITIZER_CAN_USE_ALLOCATOR641014// These tests can fail on Windows if memory is somewhat full and lit happens1015// to run them all at the same time. FIXME: Make them not flaky and reenable.1016#if !SANITIZER_WINDOWS1017TEST(SanitizerCommon, SizeClassAllocator64Iteration) {1018 TestSizeClassAllocatorIteration<Allocator64>();1019}1020TEST(SanitizerCommon, SizeClassAllocator64DynamicIteration) {1021 TestSizeClassAllocatorIteration<Allocator64Dynamic>();1022}1023#if !ALLOCATOR64_SMALL_SIZE1024TEST(SanitizerCommon, SizeClassAllocator64DynamicPremappedIteration) {1025 ScopedPremappedHeap h;1026 TestSizeClassAllocatorIteration<Allocator64Dynamic>(h.Addr());1027}1028#endif1029#endif1030#endif1031 1032TEST(SanitizerCommon, SKIP_ON_SPARCV9(SizeClassAllocator32Iteration)) {1033 TestSizeClassAllocatorIteration<Allocator32Compact>();1034}1035 1036TEST(SanitizerCommon, LargeMmapAllocatorIteration) {1037 LargeMmapAllocator<NoOpMapUnmapCallback> a;1038 a.Init();1039 AllocatorStats stats;1040 stats.Init();1041 1042 static const uptr kNumAllocs = 1000;1043 char *allocated[kNumAllocs];1044 static const uptr size = 40;1045 // Allocate some.1046 for (uptr i = 0; i < kNumAllocs; i++)1047 allocated[i] = (char *)a.Allocate(&stats, size, 1);1048 1049 std::set<uptr> reported_chunks;1050 a.ForceLock();1051 a.ForEachChunk(IterationTestCallback, &reported_chunks);1052 a.ForceUnlock();1053 1054 for (uptr i = 0; i < kNumAllocs; i++) {1055 // Don't use EXPECT_NE. Reporting the first mismatch is enough.1056 ASSERT_NE(reported_chunks.find(reinterpret_cast<uptr>(allocated[i])),1057 reported_chunks.end());1058 }1059 for (uptr i = 0; i < kNumAllocs; i++)1060 a.Deallocate(&stats, allocated[i]);1061}1062 1063TEST(SanitizerCommon, LargeMmapAllocatorBlockBegin) {1064 LargeMmapAllocator<NoOpMapUnmapCallback> a;1065 a.Init();1066 AllocatorStats stats;1067 stats.Init();1068 1069 static const uptr kNumAllocs = 1024;1070 static const uptr kNumExpectedFalseLookups = 10000000;1071 char *allocated[kNumAllocs];1072 static const uptr size = 4096;1073 // Allocate some.1074 for (uptr i = 0; i < kNumAllocs; i++) {1075 allocated[i] = (char *)a.Allocate(&stats, size, 1);1076 }1077 1078 a.ForceLock();1079 for (uptr i = 0; i < kNumAllocs * kNumAllocs; i++) {1080 // if ((i & (i - 1)) == 0) fprintf(stderr, "[%zd]\n", i);1081 char *p1 = allocated[i % kNumAllocs];1082 EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1));1083 EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 + size / 2));1084 EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 + size - 1));1085 EXPECT_EQ(p1, a.GetBlockBeginFastLocked(p1 - 100));1086 }1087 1088 for (uptr i = 0; i < kNumExpectedFalseLookups; i++) {1089 void *p = reinterpret_cast<void *>(i % 1024);1090 EXPECT_EQ((void *)0, a.GetBlockBeginFastLocked(p));1091 p = reinterpret_cast<void *>(~0L - (i % 1024));1092 EXPECT_EQ((void *)0, a.GetBlockBeginFastLocked(p));1093 }1094 a.ForceUnlock();1095 1096 for (uptr i = 0; i < kNumAllocs; i++)1097 a.Deallocate(&stats, allocated[i]);1098}1099 1100 1101// Don't test OOM conditions on Win64 because it causes other tests on the same1102// machine to OOM.1103#if SANITIZER_CAN_USE_ALLOCATOR64 && !SANITIZER_WINDOWS64 && !ALLOCATOR64_SMALL_SIZE1104typedef __sanitizer::SizeClassMap<2, 22, 22, 34, 128, 16> SpecialSizeClassMap;1105template <typename AddressSpaceViewTy = LocalAddressSpaceView>1106struct AP64_SpecialSizeClassMap {1107 static const uptr kSpaceBeg = kAllocatorSpace;1108 static const uptr kSpaceSize = kAllocatorSize;1109 static const uptr kMetadataSize = 0;1110 typedef SpecialSizeClassMap SizeClassMap;1111 typedef NoOpMapUnmapCallback MapUnmapCallback;1112 static const uptr kFlags = 0;1113 using AddressSpaceView = AddressSpaceViewTy;1114};1115 1116// Regression test for out-of-memory condition in PopulateFreeList().1117TEST(SanitizerCommon, SizeClassAllocator64PopulateFreeListOOM) {1118 // In a world where regions are small and chunks are huge...1119 typedef SizeClassAllocator64<AP64_SpecialSizeClassMap<>> SpecialAllocator64;1120 const uptr kRegionSize =1121 kAllocatorSize / SpecialSizeClassMap::kNumClassesRounded;1122 SpecialAllocator64 *a = new SpecialAllocator64;1123 a->Init(kReleaseToOSIntervalNever);1124 SpecialAllocator64::AllocatorCache cache;1125 memset(&cache, 0, sizeof(cache));1126 cache.Init(0);1127 1128 // ...one man is on a mission to overflow a region with a series of1129 // successive allocations.1130 1131 const uptr kClassID = 24;1132 const uptr kAllocationSize = SpecialSizeClassMap::Size(kClassID);1133 ASSERT_LT(2 * kAllocationSize, kRegionSize);1134 ASSERT_GT(3 * kAllocationSize, kRegionSize);1135 EXPECT_NE(cache.Allocate(a, kClassID), nullptr);1136 EXPECT_NE(cache.Allocate(a, kClassID), nullptr);1137 EXPECT_EQ(cache.Allocate(a, kClassID), nullptr);1138 1139 const uptr Class2 = 21;1140 const uptr Size2 = SpecialSizeClassMap::Size(Class2);1141 ASSERT_EQ(Size2 * 8, kRegionSize);1142 char *p[7];1143 for (int i = 0; i < 7; i++) {1144 p[i] = (char*)cache.Allocate(a, Class2);1145 EXPECT_NE(p[i], nullptr);1146 fprintf(stderr, "p[%d] %p s = %lx\n", i, (void*)p[i], Size2);1147 p[i][Size2 - 1] = 42;1148 if (i) ASSERT_LT(p[i - 1], p[i]);1149 }1150 EXPECT_EQ(cache.Allocate(a, Class2), nullptr);1151 cache.Deallocate(a, Class2, p[0]);1152 cache.Drain(a);1153 ASSERT_EQ(p[6][Size2 - 1], 42);1154 a->TestOnlyUnmap();1155 delete a;1156}1157 1158#endif1159 1160#if SANITIZER_CAN_USE_ALLOCATOR641161 1162class NoMemoryMapper {1163 public:1164 uptr last_request_buffer_size = 0;1165 1166 u64 *MapPackedCounterArrayBuffer(uptr buffer_size) {1167 last_request_buffer_size = buffer_size * sizeof(u64);1168 return nullptr;1169 }1170};1171 1172class RedZoneMemoryMapper {1173 public:1174 RedZoneMemoryMapper() {1175 const auto page_size = GetPageSize();1176 buffer = MmapOrDie(3ULL * page_size, "");1177 MprotectNoAccess(reinterpret_cast<uptr>(buffer), page_size);1178 MprotectNoAccess(reinterpret_cast<uptr>(buffer) + page_size * 2, page_size);1179 }1180 ~RedZoneMemoryMapper() { UnmapOrDie(buffer, 3 * GetPageSize()); }1181 1182 u64 *MapPackedCounterArrayBuffer(uptr buffer_size) {1183 buffer_size *= sizeof(u64);1184 const auto page_size = GetPageSize();1185 CHECK_EQ(buffer_size, page_size);1186 u64 *p =1187 reinterpret_cast<u64 *>(reinterpret_cast<uptr>(buffer) + page_size);1188 memset(p, 0, page_size);1189 return p;1190 }1191 1192 private:1193 void *buffer;1194};1195 1196TEST(SanitizerCommon, SizeClassAllocator64PackedCounterArray) {1197 NoMemoryMapper no_memory_mapper;1198 for (int i = 0; i < 64; i++) {1199 // Various valid counter's max values packed into one word.1200 Allocator64::PackedCounterArray counters_2n(1, 1ULL << i,1201 &no_memory_mapper);1202 EXPECT_EQ(8ULL, no_memory_mapper.last_request_buffer_size);1203 1204 // Check the "all bit set" values too.1205 Allocator64::PackedCounterArray counters_2n1_1(1, ~0ULL >> i,1206 &no_memory_mapper);1207 EXPECT_EQ(8ULL, no_memory_mapper.last_request_buffer_size);1208 1209 // Verify the packing ratio, the counter is expected to be packed into the1210 // closest power of 2 bits.1211 Allocator64::PackedCounterArray counters(64, 1ULL << i, &no_memory_mapper);1212 EXPECT_EQ(8ULL * RoundUpToPowerOfTwo(i + 1),1213 no_memory_mapper.last_request_buffer_size);1214 }1215 1216 RedZoneMemoryMapper memory_mapper;1217 // Go through 1, 2, 4, 8, .. 64 bits per counter.1218 for (int i = 0; i < 7; i++) {1219 // Make sure counters request one memory page for the buffer.1220 const u64 kNumCounters = (GetPageSize() / 8) * (64 >> i);1221 Allocator64::PackedCounterArray counters(1222 kNumCounters, 1ULL << ((1 << i) - 1), &memory_mapper);1223 counters.Inc(0);1224 for (u64 c = 1; c < kNumCounters - 1; c++) {1225 ASSERT_EQ(0ULL, counters.Get(c));1226 counters.Inc(c);1227 ASSERT_EQ(1ULL, counters.Get(c - 1));1228 }1229 ASSERT_EQ(0ULL, counters.Get(kNumCounters - 1));1230 counters.Inc(kNumCounters - 1);1231 1232 if (i > 0) {1233 counters.IncRange(0, kNumCounters - 1);1234 for (u64 c = 0; c < kNumCounters; c++)1235 ASSERT_EQ(2ULL, counters.Get(c));1236 }1237 }1238}1239 1240class RangeRecorder {1241 public:1242 std::string reported_pages;1243 1244 RangeRecorder()1245 : page_size_scaled_log(1246 Log2(GetPageSizeCached() >> Allocator64::kCompactPtrScale)),1247 last_page_reported(0) {}1248 1249 void ReleasePageRangeToOS(u32 class_id, u32 from, u32 to) {1250 from >>= page_size_scaled_log;1251 to >>= page_size_scaled_log;1252 ASSERT_LT(from, to);1253 if (!reported_pages.empty())1254 ASSERT_LT(last_page_reported, from);1255 reported_pages.append(from - last_page_reported, '.');1256 reported_pages.append(to - from, 'x');1257 last_page_reported = to;1258 }1259 1260 private:1261 const uptr page_size_scaled_log;1262 u32 last_page_reported;1263};1264 1265TEST(SanitizerCommon, SizeClassAllocator64FreePagesRangeTracker) {1266 typedef Allocator64::FreePagesRangeTracker<RangeRecorder> RangeTracker;1267 1268 // 'x' denotes a page to be released, '.' denotes a page to be kept around.1269 const char* test_cases[] = {1270 "",1271 ".",1272 "x",1273 "........",1274 "xxxxxxxxxxx",1275 "..............xxxxx",1276 "xxxxxxxxxxxxxxxxxx.....",1277 "......xxxxxxxx........",1278 "xxx..........xxxxxxxxxxxxxxx",1279 "......xxxx....xxxx........",1280 "xxx..........xxxxxxxx....xxxxxxx",1281 "x.x.x.x.x.x.x.x.x.x.x.x.",1282 ".x.x.x.x.x.x.x.x.x.x.x.x",1283 ".x.x.x.x.x.x.x.x.x.x.x.x.",1284 "x.x.x.x.x.x.x.x.x.x.x.x.x",1285 };1286 1287 for (auto test_case : test_cases) {1288 RangeRecorder range_recorder;1289 RangeTracker tracker(&range_recorder, 1);1290 for (int i = 0; test_case[i] != 0; i++)1291 tracker.NextPage(test_case[i] == 'x');1292 tracker.Done();1293 // Strip trailing '.'-pages before comparing the results as they are not1294 // going to be reported to range_recorder anyway.1295 const char* last_x = strrchr(test_case, 'x');1296 std::string expected(1297 test_case,1298 last_x == nullptr ? 0 : (last_x - test_case + 1));1299 EXPECT_STREQ(expected.c_str(), range_recorder.reported_pages.c_str());1300 }1301}1302 1303class ReleasedPagesTrackingMemoryMapper {1304 public:1305 std::set<u32> reported_pages;1306 std::vector<u64> buffer;1307 1308 u64 *MapPackedCounterArrayBuffer(uptr buffer_size) {1309 reported_pages.clear();1310 buffer.assign(buffer_size, 0);1311 return buffer.data();1312 }1313 void ReleasePageRangeToOS(u32 class_id, u32 from, u32 to) {1314 uptr page_size_scaled =1315 GetPageSizeCached() >> Allocator64::kCompactPtrScale;1316 for (u32 i = from; i < to; i += page_size_scaled)1317 reported_pages.insert(i);1318 }1319};1320 1321template <class Allocator>1322void TestReleaseFreeMemoryToOS() {1323 ReleasedPagesTrackingMemoryMapper memory_mapper;1324 const uptr kAllocatedPagesCount = 1024;1325 const uptr page_size = GetPageSizeCached();1326 const uptr page_size_scaled = page_size >> Allocator::kCompactPtrScale;1327 std::mt19937 r;1328 uint32_t rnd_state = 42;1329 1330 for (uptr class_id = 1; class_id <= Allocator::SizeClassMapT::kLargestClassID;1331 class_id++) {1332 const uptr chunk_size = Allocator::SizeClassMapT::Size(class_id);1333 const uptr chunk_size_scaled = chunk_size >> Allocator::kCompactPtrScale;1334 const uptr max_chunks =1335 kAllocatedPagesCount * GetPageSizeCached() / chunk_size;1336 1337 // Generate the random free list.1338 std::vector<u32> free_array;1339 bool in_free_range = false;1340 uptr current_range_end = 0;1341 for (uptr i = 0; i < max_chunks; i++) {1342 if (i == current_range_end) {1343 in_free_range = (my_rand_r(&rnd_state) & 1U) == 1;1344 current_range_end += my_rand_r(&rnd_state) % 100 + 1;1345 }1346 if (in_free_range)1347 free_array.push_back(i * chunk_size_scaled);1348 }1349 if (free_array.empty())1350 continue;1351 // Shuffle free_list to verify that ReleaseFreeMemoryToOS does not depend on1352 // the list ordering.1353 std::shuffle(free_array.begin(), free_array.end(), r);1354 1355 Allocator::ReleaseFreeMemoryToOS(&free_array[0], free_array.size(),1356 chunk_size, kAllocatedPagesCount,1357 &memory_mapper, class_id);1358 1359 // Verify that there are no released pages touched by used chunks and all1360 // ranges of free chunks big enough to contain the entire memory pages had1361 // these pages released.1362 uptr verified_released_pages = 0;1363 std::set<u32> free_chunks(free_array.begin(), free_array.end());1364 1365 u32 current_chunk = 0;1366 in_free_range = false;1367 u32 current_free_range_start = 0;1368 for (uptr i = 0; i <= max_chunks; i++) {1369 bool is_free_chunk = free_chunks.find(current_chunk) != free_chunks.end();1370 1371 if (is_free_chunk) {1372 if (!in_free_range) {1373 in_free_range = true;1374 current_free_range_start = current_chunk;1375 }1376 } else {1377 // Verify that this used chunk does not touch any released page.1378 for (uptr i_page = current_chunk / page_size_scaled;1379 i_page <= (current_chunk + chunk_size_scaled - 1) /1380 page_size_scaled;1381 i_page++) {1382 bool page_released =1383 memory_mapper.reported_pages.find(i_page * page_size_scaled) !=1384 memory_mapper.reported_pages.end();1385 ASSERT_EQ(false, page_released);1386 }1387 1388 if (in_free_range) {1389 in_free_range = false;1390 // Verify that all entire memory pages covered by this range of free1391 // chunks were released.1392 u32 page = RoundUpTo(current_free_range_start, page_size_scaled);1393 while (page + page_size_scaled <= current_chunk) {1394 bool page_released =1395 memory_mapper.reported_pages.find(page) !=1396 memory_mapper.reported_pages.end();1397 ASSERT_EQ(true, page_released);1398 verified_released_pages++;1399 page += page_size_scaled;1400 }1401 }1402 }1403 1404 current_chunk += chunk_size_scaled;1405 }1406 1407 ASSERT_EQ(memory_mapper.reported_pages.size(), verified_released_pages);1408 }1409}1410 1411TEST(SanitizerCommon, SizeClassAllocator64ReleaseFreeMemoryToOS) {1412 TestReleaseFreeMemoryToOS<Allocator64>();1413}1414 1415#if !ALLOCATOR64_SMALL_SIZE1416TEST(SanitizerCommon, SizeClassAllocator64CompactReleaseFreeMemoryToOS) {1417 TestReleaseFreeMemoryToOS<Allocator64Compact>();1418}1419 1420TEST(SanitizerCommon, SizeClassAllocator64VeryCompactReleaseFreeMemoryToOS) {1421 TestReleaseFreeMemoryToOS<Allocator64VeryCompact>();1422}1423#endif // !ALLOCATOR64_SMALL_SIZE1424 1425#endif // SANITIZER_CAN_USE_ALLOCATOR641426 1427TEST(SanitizerCommon, LowLevelAllocatorShouldRoundUpSizeOnAlloc) {1428 // When allocating a memory block slightly bigger than a memory page and1429 // LowLevelAllocator calls MmapOrDie for the internal buffer, it should round1430 // the size up to the page size, so that subsequent calls to the allocator1431 // can use the remaining space in the last allocated page.1432 static LowLevelAllocator allocator;1433 char *ptr1 = (char *)allocator.Allocate(GetPageSizeCached() + 16);1434 char *ptr2 = (char *)allocator.Allocate(16);1435 EXPECT_EQ(ptr2, ptr1 + GetPageSizeCached() + 16);1436}1437 1438#endif // #if !SANITIZER_DEBUG1439