1981 lines · c
1//===-- primary64.h ---------------------------------------------*- C++ -*-===//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#ifndef SCUDO_PRIMARY64_H_10#define SCUDO_PRIMARY64_H_11 12#include "allocator_common.h"13#include "bytemap.h"14#include "common.h"15#include "condition_variable.h"16#include "list.h"17#include "mem_map.h"18#include "memtag.h"19#include "options.h"20#include "release.h"21#include "size_class_allocator.h"22#include "stats.h"23#include "string_utils.h"24#include "thread_annotations.h"25#include "tracing.h"26 27namespace scudo {28 29// SizeClassAllocator64 is an allocator tuned for 64-bit address space.30//31// It starts by reserving NumClasses * 2^RegionSizeLog bytes, equally divided in32// Regions, specific to each size class. Note that the base of that mapping is33// random (based to the platform specific map() capabilities). If34// PrimaryEnableRandomOffset is set, each Region actually starts at a random35// offset from its base.36//37// Regions are mapped incrementally on demand to fulfill allocation requests,38// those mappings being split into equally sized Blocks based on the size class39// they belong to. The Blocks created are shuffled to prevent predictable40// address patterns (the predictability increases with the size of the Blocks).41//42// The 1st Region (for size class 0) holds the Batches. This is a43// structure used to transfer arrays of available pointers from the class size44// freelist to the thread specific freelist, and back.45//46// The memory used by this allocator is never unmapped, but can be partially47// released if the platform allows for it.48 49template <typename Config> class SizeClassAllocator64 {50public:51 typedef typename Config::CompactPtrT CompactPtrT;52 typedef typename Config::SizeClassMap SizeClassMap;53 typedef typename Config::ConditionVariableT ConditionVariableT;54 static const uptr CompactPtrScale = Config::getCompactPtrScale();55 static const uptr RegionSizeLog = Config::getRegionSizeLog();56 static const uptr GroupSizeLog = Config::getGroupSizeLog();57 static_assert(RegionSizeLog >= GroupSizeLog,58 "Group size shouldn't be greater than the region size");59 static const uptr GroupScale = GroupSizeLog - CompactPtrScale;60 typedef SizeClassAllocator64<Config> ThisT;61 typedef Batch<ThisT> BatchT;62 typedef BatchGroup<ThisT> BatchGroupT;63 using SizeClassAllocatorT =64 typename Conditional<Config::getEnableBlockCache(),65 SizeClassAllocatorLocalCache<ThisT>,66 SizeClassAllocatorNoCache<ThisT>>::type;67 static const u16 MaxNumBlocksInBatch = SizeClassMap::MaxNumCachedHint;68 69 static constexpr uptr getSizeOfBatchClass() {70 const uptr HeaderSize = sizeof(BatchT);71 return roundUp(HeaderSize + sizeof(CompactPtrT) * MaxNumBlocksInBatch,72 1 << CompactPtrScale);73 }74 75 static_assert(sizeof(BatchGroupT) <= getSizeOfBatchClass(),76 "BatchGroupT also uses BatchClass");77 78 // BachClass is used to store internal metadata so it needs to be at least as79 // large as the largest data structure.80 static uptr getSizeByClassId(uptr ClassId) {81 return (ClassId == SizeClassMap::BatchClassId)82 ? getSizeOfBatchClass()83 : SizeClassMap::getSizeByClassId(ClassId);84 }85 86 static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }87 static bool conditionVariableEnabled() {88 return Config::hasConditionVariableT();89 }90 static uptr getRegionInfoArraySize() { return sizeof(RegionInfoArray); }91 static BlockInfo findNearestBlock(const char *RegionInfoData,92 uptr Ptr) NO_THREAD_SAFETY_ANALYSIS;93 94 void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS;95 96 void unmapTestOnly();97 98 // When all blocks are freed, it has to be the same size as `AllocatedUser`.99 void verifyAllBlocksAreReleasedTestOnly();100 101 u16 popBlocks(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,102 CompactPtrT *ToArray, const u16 MaxBlockCount);103 104 // Push the array of free blocks to the designated batch group.105 void pushBlocks(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,106 CompactPtrT *Array, u32 Size);107 108 void disable() NO_THREAD_SAFETY_ANALYSIS;109 void enable() NO_THREAD_SAFETY_ANALYSIS;110 111 template <typename F> void iterateOverBlocks(F Callback);112 113 void getStats(ScopedString *Str);114 void getFragmentationInfo(ScopedString *Str);115 void getMemoryGroupFragmentationInfo(ScopedString *Str);116 117 bool setOption(Option O, sptr Value);118 119 // These are used for returning unused pages. Note that it doesn't unmap the120 // pages, it only suggests that the physical pages can be released.121 uptr tryReleaseToOS(uptr ClassId, ReleaseToOS ReleaseType);122 uptr releaseToOS(ReleaseToOS ReleaseType);123 124 const char *getRegionInfoArrayAddress() const {125 return reinterpret_cast<const char *>(RegionInfoArray);126 }127 128 uptr getCompactPtrBaseByClassId(uptr ClassId) {129 return getRegionInfo(ClassId)->RegionBeg;130 }131 CompactPtrT compactPtr(uptr ClassId, uptr Ptr) {132 DCHECK_LE(ClassId, SizeClassMap::LargestClassId);133 return compactPtrInternal(getCompactPtrBaseByClassId(ClassId), Ptr);134 }135 void *decompactPtr(uptr ClassId, CompactPtrT CompactPtr) {136 DCHECK_LE(ClassId, SizeClassMap::LargestClassId);137 return reinterpret_cast<void *>(138 decompactPtrInternal(getCompactPtrBaseByClassId(ClassId), CompactPtr));139 }140 141 AtomicOptions Options;142 143private:144 static const uptr RegionSize = 1UL << RegionSizeLog;145 static const uptr NumClasses = SizeClassMap::NumClasses;146 static const uptr MapSizeIncrement = Config::getMapSizeIncrement();147 // Fill at most this number of batches from the newly map'd memory.148 static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U;149 150 struct ReleaseToOsInfo {151 uptr BytesInFreeListAtLastCheckpoint;152 uptr NumReleasesAttempted;153 uptr LastReleasedBytes;154 // The minimum size of pushed blocks to trigger page release.155 uptr TryReleaseThreshold;156 // The number of bytes not triggering `releaseToOSMaybe()` because of157 // the length of release interval.158 uptr PendingPushedBytesDelta;159 u64 LastReleaseAtNs;160 };161 162 struct BlocksInfo {163 SinglyLinkedList<BatchGroupT> BlockList = {};164 uptr PoppedBlocks = 0;165 uptr PushedBlocks = 0;166 };167 168 struct PagesInfo {169 MemMapT MemMap = {};170 // Bytes mapped for user memory.171 uptr MappedUser = 0;172 // Bytes allocated for user memory.173 uptr AllocatedUser = 0;174 };175 176 struct UnpaddedRegionInfo {177 // Mutex for operations on freelist178 HybridMutex FLLock;179 ConditionVariableT FLLockCV GUARDED_BY(FLLock);180 // Mutex for memmap operations181 HybridMutex MMLock ACQUIRED_BEFORE(FLLock);182 // `RegionBeg` is initialized before thread creation and won't be changed.183 uptr RegionBeg = 0;184 u32 RandState GUARDED_BY(MMLock) = 0;185 BlocksInfo FreeListInfo GUARDED_BY(FLLock);186 PagesInfo MemMapInfo GUARDED_BY(MMLock);187 ReleaseToOsInfo ReleaseInfo GUARDED_BY(MMLock) = {};188 bool Exhausted GUARDED_BY(MMLock) = false;189 bool isPopulatingFreeList GUARDED_BY(FLLock) = false;190 };191 struct RegionInfo : UnpaddedRegionInfo {192 char Padding[SCUDO_CACHE_LINE_SIZE -193 (sizeof(UnpaddedRegionInfo) % SCUDO_CACHE_LINE_SIZE)] = {};194 };195 static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");196 197 RegionInfo *getRegionInfo(uptr ClassId) {198 DCHECK_LT(ClassId, NumClasses);199 return &RegionInfoArray[ClassId];200 }201 202 uptr getRegionBaseByClassId(uptr ClassId) {203 RegionInfo *Region = getRegionInfo(ClassId);204 Region->MMLock.assertHeld();205 206 if (!Config::getEnableContiguousRegions() &&207 !Region->MemMapInfo.MemMap.isAllocated()) {208 return 0U;209 }210 return Region->MemMapInfo.MemMap.getBase();211 }212 213 CompactPtrT compactPtrInternal(uptr Base, uptr Ptr) const {214 return static_cast<CompactPtrT>((Ptr - Base) >> CompactPtrScale);215 }216 uptr decompactPtrInternal(uptr Base, CompactPtrT CompactPtr) const {217 return Base + (static_cast<uptr>(CompactPtr) << CompactPtrScale);218 }219 uptr compactPtrGroup(CompactPtrT CompactPtr) const {220 const uptr Mask = (static_cast<uptr>(1) << GroupScale) - 1;221 return static_cast<uptr>(CompactPtr) & ~Mask;222 }223 uptr decompactGroupBase(uptr Base, uptr CompactPtrGroupBase) const {224 DCHECK_EQ(CompactPtrGroupBase % (static_cast<uptr>(1) << (GroupScale)), 0U);225 return Base + (CompactPtrGroupBase << CompactPtrScale);226 }227 ALWAYS_INLINE bool isSmallBlock(uptr BlockSize) const {228 const uptr PageSize = getPageSizeCached();229 return BlockSize < PageSize / 16U;230 }231 ALWAYS_INLINE uptr getMinReleaseAttemptSize(uptr BlockSize) {232 return roundUp(BlockSize, getPageSizeCached());233 }234 235 ALWAYS_INLINE void initRegion(RegionInfo *Region, uptr ClassId,236 MemMapT MemMap, bool EnableRandomOffset)237 REQUIRES(Region->MMLock);238 239 void pushBlocksImpl(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,240 RegionInfo *Region, CompactPtrT *Array, u32 Size,241 bool SameGroup = false) REQUIRES(Region->FLLock);242 243 // Similar to `pushBlocksImpl` but has some logics specific to BatchClass.244 void pushBatchClassBlocks(RegionInfo *Region, CompactPtrT *Array, u32 Size)245 REQUIRES(Region->FLLock);246 247 // Pop at most `MaxBlockCount` from the freelist of the given region.248 u16 popBlocksImpl(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,249 RegionInfo *Region, CompactPtrT *ToArray,250 const u16 MaxBlockCount) REQUIRES(Region->FLLock);251 // Same as `popBlocksImpl` but is used when conditional variable is enabled.252 u16 popBlocksWithCV(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,253 RegionInfo *Region, CompactPtrT *ToArray,254 const u16 MaxBlockCount, bool &ReportRegionExhausted);255 256 // When there's no blocks available in the freelist, it tries to prepare more257 // blocks by mapping more pages.258 NOINLINE u16 populateFreeListAndPopBlocks(259 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,260 CompactPtrT *ToArray, const u16 MaxBlockCount) REQUIRES(Region->MMLock)261 EXCLUDES(Region->FLLock);262 263 void getStats(ScopedString *Str, uptr ClassId, RegionInfo *Region)264 REQUIRES(Region->MMLock, Region->FLLock);265 void getRegionFragmentationInfo(RegionInfo *Region, uptr ClassId,266 ScopedString *Str) REQUIRES(Region->MMLock);267 void getMemoryGroupFragmentationInfoInRegion(RegionInfo *Region, uptr ClassId,268 ScopedString *Str)269 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock);270 271 NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,272 ReleaseToOS ReleaseType = ReleaseToOS::Normal)273 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock);274 bool hasChanceToReleasePages(RegionInfo *Region, uptr BlockSize,275 uptr BytesInFreeList, ReleaseToOS ReleaseType)276 REQUIRES(Region->MMLock, Region->FLLock);277 SinglyLinkedList<BatchGroupT>278 collectGroupsToRelease(RegionInfo *Region, const uptr BlockSize,279 const uptr AllocatedUserEnd, const uptr CompactPtrBase)280 REQUIRES(Region->MMLock, Region->FLLock);281 PageReleaseContext282 markFreeBlocks(RegionInfo *Region, const uptr BlockSize,283 const uptr AllocatedUserEnd, const uptr CompactPtrBase,284 SinglyLinkedList<BatchGroupT> &GroupsToRelease)285 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock);286 287 void mergeGroupsToReleaseBack(RegionInfo *Region,288 SinglyLinkedList<BatchGroupT> &GroupsToRelease)289 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock);290 291 // The minimum size of pushed blocks that we will try to release the pages in292 // that size class.293 uptr SmallerBlockReleasePageDelta = 0;294 atomic_s32 ReleaseToOsIntervalMs = {};295 alignas(SCUDO_CACHE_LINE_SIZE) RegionInfo RegionInfoArray[NumClasses];296};297 298template <typename Config>299void SizeClassAllocator64<Config>::init(s32 ReleaseToOsInterval)300 NO_THREAD_SAFETY_ANALYSIS {301 DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));302 303 const uptr PageSize = getPageSizeCached();304 const uptr GroupSize = (1UL << GroupSizeLog);305 const uptr PagesInGroup = GroupSize / PageSize;306 const uptr MinSizeClass = getSizeByClassId(1);307 // When trying to release pages back to memory, visiting smaller size308 // classes is expensive. Therefore, we only try to release smaller size309 // classes when the amount of free blocks goes over a certain threshold (See310 // the comment in releaseToOSMaybe() for more details). For example, for311 // size class 32, we only do the release when the size of free blocks is312 // greater than 97% of pages in a group. However, this may introduce another313 // issue that if the number of free blocks is bouncing between 97% ~ 100%.314 // Which means we may try many page releases but only release very few of315 // them (less than 3% in a group). Even though we have316 // `&ReleaseToOsIntervalMs` which slightly reduce the frequency of these317 // calls but it will be better to have another guard to mitigate this issue.318 //319 // Here we add another constraint on the minimum size requirement. The320 // constraint is determined by the size of in-use blocks in the minimal size321 // class. Take size class 32 as an example,322 //323 // +- one memory group -+324 // +----------------------+------+325 // | 97% of free blocks | |326 // +----------------------+------+327 // \ /328 // 3% in-use blocks329 //330 // * The release size threshold is 97%.331 //332 // The 3% size in a group is about 7 pages. For two consecutive333 // releaseToOSMaybe(), we require the difference between `PushedBlocks`334 // should be greater than 7 pages. This mitigates the page releasing335 // thrashing which is caused by memory usage bouncing around the threshold.336 // The smallest size class takes longest time to do the page release so we337 // use its size of in-use blocks as a heuristic.338 SmallerBlockReleasePageDelta = PagesInGroup * (1 + MinSizeClass / 16U) / 100;339 340 u32 Seed;341 const u64 Time = getMonotonicTimeFast();342 if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed)))343 Seed = static_cast<u32>(Time ^ (reinterpret_cast<uptr>(&Seed) >> 12));344 345 for (uptr I = 0; I < NumClasses; I++)346 getRegionInfo(I)->RandState = getRandomU32(&Seed);347 348 if (Config::getEnableContiguousRegions()) {349 ReservedMemoryT ReservedMemory = {};350 // Reserve the space required for the Primary.351 CHECK(ReservedMemory.create(/*Addr=*/0U, RegionSize * NumClasses,352 "scudo:primary_reserve"));353 const uptr PrimaryBase = ReservedMemory.getBase();354 355 for (uptr I = 0; I < NumClasses; I++) {356 MemMapT RegionMemMap = ReservedMemory.dispatch(357 PrimaryBase + (I << RegionSizeLog), RegionSize);358 RegionInfo *Region = getRegionInfo(I);359 360 initRegion(Region, I, RegionMemMap, Config::getEnableRandomOffset());361 }362 shuffle(RegionInfoArray, NumClasses, &Seed);363 }364 365 // The binding should be done after region shuffling so that it won't bind366 // the FLLock from the wrong region.367 for (uptr I = 0; I < NumClasses; I++)368 getRegionInfo(I)->FLLockCV.bindTestOnly(getRegionInfo(I)->FLLock);369 370 // The default value in the primary config has the higher priority.371 if (Config::getDefaultReleaseToOsIntervalMs() != INT32_MIN)372 ReleaseToOsInterval = Config::getDefaultReleaseToOsIntervalMs();373 setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval));374}375 376template <typename Config>377void SizeClassAllocator64<Config>::initRegion(RegionInfo *Region, uptr ClassId,378 MemMapT MemMap,379 bool EnableRandomOffset)380 REQUIRES(Region->MMLock) {381 DCHECK(!Region->MemMapInfo.MemMap.isAllocated());382 DCHECK(MemMap.isAllocated());383 384 const uptr PageSize = getPageSizeCached();385 386 Region->MemMapInfo.MemMap = MemMap;387 388 Region->RegionBeg = MemMap.getBase();389 if (EnableRandomOffset) {390 Region->RegionBeg += (getRandomModN(&Region->RandState, 16) + 1) * PageSize;391 }392 393 const uptr BlockSize = getSizeByClassId(ClassId);394 // Releasing small blocks is expensive, set a higher threshold to avoid395 // frequent page releases.396 if (isSmallBlock(BlockSize)) {397 Region->ReleaseInfo.TryReleaseThreshold =398 PageSize * SmallerBlockReleasePageDelta;399 } else {400 Region->ReleaseInfo.TryReleaseThreshold =401 getMinReleaseAttemptSize(BlockSize);402 }403}404 405template <typename Config> void SizeClassAllocator64<Config>::unmapTestOnly() {406 for (uptr I = 0; I < NumClasses; I++) {407 RegionInfo *Region = getRegionInfo(I);408 {409 ScopedLock ML(Region->MMLock);410 MemMapT MemMap = Region->MemMapInfo.MemMap;411 if (MemMap.isAllocated())412 MemMap.unmap();413 }414 *Region = {};415 }416}417 418template <typename Config>419void SizeClassAllocator64<Config>::verifyAllBlocksAreReleasedTestOnly() {420 // `BatchGroup` and `Batch` also use the blocks from BatchClass.421 uptr BatchClassUsedInFreeLists = 0;422 for (uptr I = 0; I < NumClasses; I++) {423 // We have to count BatchClassUsedInFreeLists in other regions first.424 if (I == SizeClassMap::BatchClassId)425 continue;426 RegionInfo *Region = getRegionInfo(I);427 ScopedLock ML(Region->MMLock);428 ScopedLock FL(Region->FLLock);429 const uptr BlockSize = getSizeByClassId(I);430 uptr TotalBlocks = 0;431 for (BatchGroupT &BG : Region->FreeListInfo.BlockList) {432 // `BG::Batches` are `Batches`. +1 for `BatchGroup`.433 BatchClassUsedInFreeLists += BG.Batches.size() + 1;434 for (const auto &It : BG.Batches)435 TotalBlocks += It.getCount();436 }437 438 DCHECK_EQ(TotalBlocks, Region->MemMapInfo.AllocatedUser / BlockSize);439 DCHECK_EQ(Region->FreeListInfo.PushedBlocks,440 Region->FreeListInfo.PoppedBlocks);441 }442 443 RegionInfo *Region = getRegionInfo(SizeClassMap::BatchClassId);444 ScopedLock ML(Region->MMLock);445 ScopedLock FL(Region->FLLock);446 const uptr BlockSize = getSizeByClassId(SizeClassMap::BatchClassId);447 uptr TotalBlocks = 0;448 for (BatchGroupT &BG : Region->FreeListInfo.BlockList) {449 if (LIKELY(!BG.Batches.empty())) {450 for (const auto &It : BG.Batches)451 TotalBlocks += It.getCount();452 } else {453 // `BatchGroup` with empty freelist doesn't have `Batch` record454 // itself.455 ++TotalBlocks;456 }457 }458 DCHECK_EQ(TotalBlocks + BatchClassUsedInFreeLists,459 Region->MemMapInfo.AllocatedUser / BlockSize);460 DCHECK_GE(Region->FreeListInfo.PoppedBlocks,461 Region->FreeListInfo.PushedBlocks);462 const uptr BlocksInUse =463 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;464 DCHECK_EQ(BlocksInUse, BatchClassUsedInFreeLists);465}466 467template <typename Config>468u16 SizeClassAllocator64<Config>::popBlocks(469 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, CompactPtrT *ToArray,470 const u16 MaxBlockCount) {471 DCHECK_LT(ClassId, NumClasses);472 RegionInfo *Region = getRegionInfo(ClassId);473 u16 PopCount = 0;474 475 {476 ScopedLock L(Region->FLLock);477 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region, ToArray,478 MaxBlockCount);479 if (PopCount != 0U)480 return PopCount;481 }482 483 bool ReportRegionExhausted = false;484 485 if (conditionVariableEnabled()) {486 PopCount = popBlocksWithCV(SizeClassAllocator, ClassId, Region, ToArray,487 MaxBlockCount, ReportRegionExhausted);488 } else {489 while (true) {490 // When two threads compete for `Region->MMLock`, we only want one of491 // them to call populateFreeListAndPopBlocks(). To avoid both of them492 // doing that, always check the freelist before mapping new pages.493 ScopedLock ML(Region->MMLock);494 {495 ScopedLock FL(Region->FLLock);496 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region, ToArray,497 MaxBlockCount);498 if (PopCount != 0U)499 return PopCount;500 }501 502 const bool RegionIsExhausted = Region->Exhausted;503 if (!RegionIsExhausted) {504 PopCount = populateFreeListAndPopBlocks(SizeClassAllocator, ClassId,505 Region, ToArray, MaxBlockCount);506 }507 ReportRegionExhausted = !RegionIsExhausted && Region->Exhausted;508 break;509 }510 }511 512 if (UNLIKELY(ReportRegionExhausted)) {513 Printf("Can't populate more pages for size class %zu.\n",514 getSizeByClassId(ClassId));515 516 // Theoretically, BatchClass shouldn't be used up. Abort immediately when517 // it happens.518 if (ClassId == SizeClassMap::BatchClassId)519 reportOutOfBatchClass();520 }521 522 return PopCount;523}524 525template <typename Config>526u16 SizeClassAllocator64<Config>::popBlocksWithCV(527 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,528 CompactPtrT *ToArray, const u16 MaxBlockCount,529 bool &ReportRegionExhausted) {530 u16 PopCount = 0;531 532 while (true) {533 // We only expect one thread doing the freelist refillment and other534 // threads will be waiting for either the completion of the535 // `populateFreeListAndPopBlocks()` or `pushBlocks()` called by other536 // threads.537 bool PopulateFreeList = false;538 {539 ScopedLock FL(Region->FLLock);540 if (!Region->isPopulatingFreeList) {541 Region->isPopulatingFreeList = true;542 PopulateFreeList = true;543 }544 }545 546 if (PopulateFreeList) {547 ScopedLock ML(Region->MMLock);548 549 const bool RegionIsExhausted = Region->Exhausted;550 if (!RegionIsExhausted) {551 PopCount = populateFreeListAndPopBlocks(SizeClassAllocator, ClassId,552 Region, ToArray, MaxBlockCount);553 }554 ReportRegionExhausted = !RegionIsExhausted && Region->Exhausted;555 556 {557 // Before reacquiring the `FLLock`, the freelist may be used up again558 // and some threads are waiting for the freelist refillment by the559 // current thread. It's important to set560 // `Region->isPopulatingFreeList` to false so the threads about to561 // sleep will notice the status change.562 ScopedLock FL(Region->FLLock);563 Region->isPopulatingFreeList = false;564 Region->FLLockCV.notifyAll(Region->FLLock);565 }566 567 break;568 }569 570 // At here, there are two preconditions to be met before waiting,571 // 1. The freelist is empty.572 // 2. Region->isPopulatingFreeList == true, i.e, someone is still doing573 // `populateFreeListAndPopBlocks()`.574 //575 // Note that it has the chance that freelist is empty but576 // Region->isPopulatingFreeList == false because all the new populated577 // blocks were used up right after the refillment. Therefore, we have to578 // check if someone is still populating the freelist.579 ScopedLock FL(Region->FLLock);580 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region, ToArray,581 MaxBlockCount);582 if (PopCount != 0U)583 break;584 585 if (!Region->isPopulatingFreeList)586 continue;587 588 // Now the freelist is empty and someone's doing the refillment. We will589 // wait until anyone refills the freelist or someone finishes doing590 // `populateFreeListAndPopBlocks()`. The refillment can be done by591 // `populateFreeListAndPopBlocks()`, `pushBlocks()`,592 // `pushBatchClassBlocks()` and `mergeGroupsToReleaseBack()`.593 Region->FLLockCV.wait(Region->FLLock);594 595 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region, ToArray,596 MaxBlockCount);597 if (PopCount != 0U)598 break;599 }600 601 return PopCount;602}603 604template <typename Config>605u16 SizeClassAllocator64<Config>::popBlocksImpl(606 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,607 CompactPtrT *ToArray, const u16 MaxBlockCount) REQUIRES(Region->FLLock) {608 if (Region->FreeListInfo.BlockList.empty())609 return 0U;610 611 SinglyLinkedList<BatchT> &Batches =612 Region->FreeListInfo.BlockList.front()->Batches;613 614 if (Batches.empty()) {615 DCHECK_EQ(ClassId, SizeClassMap::BatchClassId);616 BatchGroupT *BG = Region->FreeListInfo.BlockList.front();617 Region->FreeListInfo.BlockList.pop_front();618 619 // Block used by `BatchGroup` is from BatchClassId. Turn the block into620 // `Batch` with single block.621 BatchT *TB = reinterpret_cast<BatchT *>(BG);622 ToArray[0] =623 compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(TB));624 Region->FreeListInfo.PoppedBlocks += 1;625 return 1U;626 }627 628 // So far, instead of always filling blocks to `MaxBlockCount`, we only629 // examine single `Batch` to minimize the time spent in the primary630 // allocator. Besides, the sizes of `Batch` and631 // `SizeClassAllocatorT::getMaxCached()` may also impact the time spent on632 // accessing the primary allocator.633 // TODO(chiahungduan): Evaluate if we want to always prepare `MaxBlockCount`634 // blocks and/or adjust the size of `Batch` according to635 // `SizeClassAllocatorT::getMaxCached()`.636 BatchT *B = Batches.front();637 DCHECK_NE(B, nullptr);638 DCHECK_GT(B->getCount(), 0U);639 640 // BachClassId should always take all blocks in the Batch. Read the641 // comment in `pushBatchClassBlocks()` for more details.642 const u16 PopCount = ClassId == SizeClassMap::BatchClassId643 ? B->getCount()644 : Min(MaxBlockCount, B->getCount());645 B->moveNToArray(ToArray, PopCount);646 647 // TODO(chiahungduan): The deallocation of unused BatchClassId blocks can be648 // done without holding `FLLock`.649 if (B->empty()) {650 Batches.pop_front();651 // `Batch` of BatchClassId is self-contained, no need to652 // deallocate. Read the comment in `pushBatchClassBlocks()` for more653 // details.654 if (ClassId != SizeClassMap::BatchClassId)655 SizeClassAllocator->deallocate(SizeClassMap::BatchClassId, B);656 657 if (Batches.empty()) {658 BatchGroupT *BG = Region->FreeListInfo.BlockList.front();659 Region->FreeListInfo.BlockList.pop_front();660 661 // We don't keep BatchGroup with zero blocks to avoid empty-checking662 // while allocating. Note that block used for constructing BatchGroup is663 // recorded as free blocks in the last element of BatchGroup::Batches.664 // Which means, once we pop the last Batch, the block is665 // implicitly deallocated.666 if (ClassId != SizeClassMap::BatchClassId)667 SizeClassAllocator->deallocate(SizeClassMap::BatchClassId, BG);668 }669 }670 671 Region->FreeListInfo.PoppedBlocks += PopCount;672 673 return PopCount;674}675 676template <typename Config>677u16 SizeClassAllocator64<Config>::populateFreeListAndPopBlocks(678 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,679 CompactPtrT *ToArray, const u16 MaxBlockCount) REQUIRES(Region->MMLock)680 EXCLUDES(Region->FLLock) {681 if (!Config::getEnableContiguousRegions() &&682 !Region->MemMapInfo.MemMap.isAllocated()) {683 ReservedMemoryT ReservedMemory;684 if (UNLIKELY(!ReservedMemory.create(/*Addr=*/0U, RegionSize,685 "scudo:primary_reserve",686 MAP_ALLOWNOMEM))) {687 Printf("Can't reserve pages for size class %zu.\n",688 getSizeByClassId(ClassId));689 return 0U;690 }691 initRegion(Region, ClassId,692 ReservedMemory.dispatch(ReservedMemory.getBase(),693 ReservedMemory.getCapacity()),694 /*EnableRandomOffset=*/false);695 }696 697 DCHECK(Region->MemMapInfo.MemMap.isAllocated());698 const uptr Size = getSizeByClassId(ClassId);699 const u16 MaxCount = SizeClassAllocatorT::getMaxCached(Size);700 const uptr RegionBeg = Region->RegionBeg;701 const uptr MappedUser = Region->MemMapInfo.MappedUser;702 const uptr TotalUserBytes =703 Region->MemMapInfo.AllocatedUser + MaxCount * Size;704 // Map more space for blocks, if necessary.705 if (TotalUserBytes > MappedUser) {706 // Do the mmap for the user memory.707 const uptr MapSize = roundUp(TotalUserBytes - MappedUser, MapSizeIncrement);708 const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId);709 if (UNLIKELY(RegionBase + MappedUser + MapSize > RegionSize)) {710 Region->Exhausted = true;711 return 0U;712 }713 714 if (UNLIKELY(!Region->MemMapInfo.MemMap.remap(715 RegionBeg + MappedUser, MapSize, "scudo:primary",716 MAP_ALLOWNOMEM | MAP_RESIZABLE |717 (useMemoryTagging<Config>(Options.load()) ? MAP_MEMTAG : 0)))) {718 return 0U;719 }720 Region->MemMapInfo.MappedUser += MapSize;721 SizeClassAllocator->getStats().add(StatMapped, MapSize);722 }723 724 const u32 NumberOfBlocks =725 Min(MaxNumBatches * MaxCount,726 static_cast<u32>((Region->MemMapInfo.MappedUser -727 Region->MemMapInfo.AllocatedUser) /728 Size));729 DCHECK_GT(NumberOfBlocks, 0);730 731 constexpr u32 ShuffleArraySize = MaxNumBatches * MaxNumBlocksInBatch;732 CompactPtrT ShuffleArray[ShuffleArraySize];733 DCHECK_LE(NumberOfBlocks, ShuffleArraySize);734 735 const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);736 uptr P = RegionBeg + Region->MemMapInfo.AllocatedUser;737 for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)738 ShuffleArray[I] = compactPtrInternal(CompactPtrBase, P);739 740 ScopedLock L(Region->FLLock);741 742 if (ClassId != SizeClassMap::BatchClassId) {743 u32 N = 1;744 uptr CurGroup = compactPtrGroup(ShuffleArray[0]);745 for (u32 I = 1; I < NumberOfBlocks; I++) {746 if (UNLIKELY(compactPtrGroup(ShuffleArray[I]) != CurGroup)) {747 shuffle(ShuffleArray + I - N, N, &Region->RandState);748 pushBlocksImpl(SizeClassAllocator, ClassId, Region,749 ShuffleArray + I - N, N,750 /*SameGroup=*/true);751 N = 1;752 CurGroup = compactPtrGroup(ShuffleArray[I]);753 } else {754 ++N;755 }756 }757 758 shuffle(ShuffleArray + NumberOfBlocks - N, N, &Region->RandState);759 pushBlocksImpl(SizeClassAllocator, ClassId, Region,760 &ShuffleArray[NumberOfBlocks - N], N,761 /*SameGroup=*/true);762 } else {763 pushBatchClassBlocks(Region, ShuffleArray, NumberOfBlocks);764 }765 766 const u16 PopCount = popBlocksImpl(SizeClassAllocator, ClassId, Region,767 ToArray, MaxBlockCount);768 DCHECK_NE(PopCount, 0U);769 770 // Note that `PushedBlocks` and `PoppedBlocks` are supposed to only record771 // the requests from `PushBlocks` and `PopBatch` which are external772 // interfaces. `populateFreeListAndPopBlocks` is the internal interface so773 // we should set the values back to avoid incorrectly setting the stats.774 Region->FreeListInfo.PushedBlocks -= NumberOfBlocks;775 776 const uptr AllocatedUser = Size * NumberOfBlocks;777 SizeClassAllocator->getStats().add(StatFree, AllocatedUser);778 Region->MemMapInfo.AllocatedUser += AllocatedUser;779 780 return PopCount;781}782 783template <typename Config>784void SizeClassAllocator64<Config>::pushBlocks(785 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, CompactPtrT *Array,786 u32 Size) {787 DCHECK_LT(ClassId, NumClasses);788 DCHECK_GT(Size, 0);789 790 RegionInfo *Region = getRegionInfo(ClassId);791 if (ClassId == SizeClassMap::BatchClassId) {792 ScopedLock L(Region->FLLock);793 pushBatchClassBlocks(Region, Array, Size);794 if (conditionVariableEnabled())795 Region->FLLockCV.notifyAll(Region->FLLock);796 return;797 }798 799 // TODO(chiahungduan): Consider not doing grouping if the group size is not800 // greater than the block size with a certain scale.801 802 bool SameGroup = true;803 if (GroupSizeLog < RegionSizeLog) {804 // Sort the blocks so that blocks belonging to the same group can be805 // pushed together.806 for (u32 I = 1; I < Size; ++I) {807 if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I]))808 SameGroup = false;809 CompactPtrT Cur = Array[I];810 u32 J = I;811 while (J > 0 && compactPtrGroup(Cur) < compactPtrGroup(Array[J - 1])) {812 Array[J] = Array[J - 1];813 --J;814 }815 Array[J] = Cur;816 }817 }818 819 {820 ScopedLock L(Region->FLLock);821 pushBlocksImpl(SizeClassAllocator, ClassId, Region, Array, Size, SameGroup);822 if (conditionVariableEnabled())823 Region->FLLockCV.notifyAll(Region->FLLock);824 }825}826 827// Push the blocks to their batch group. The layout will be like,828//829// FreeListInfo.BlockList - > BG -> BG -> BG830// | | |831// v v v832// TB TB TB833// |834// v835// TB836//837// Each BlockGroup(BG) will associate with unique group id and the free blocks838// are managed by a list of Batch(TB). To reduce the time of inserting blocks,839// BGs are sorted and the input `Array` are supposed to be sorted so that we can840// get better performance of maintaining sorted property. Use `SameGroup=true`841// to indicate that all blocks in the array are from the same group then we will842// skip checking the group id of each block.843template <typename Config>844void SizeClassAllocator64<Config>::pushBlocksImpl(845 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, RegionInfo *Region,846 CompactPtrT *Array, u32 Size, bool SameGroup) REQUIRES(Region->FLLock) {847 DCHECK_NE(ClassId, SizeClassMap::BatchClassId);848 DCHECK_GT(Size, 0U);849 850 auto CreateGroup = [&](uptr CompactPtrGroupBase) {851 BatchGroupT *BG = reinterpret_cast<BatchGroupT *>(852 SizeClassAllocator->getBatchClassBlock());853 BG->Batches.clear();854 BatchT *TB =855 reinterpret_cast<BatchT *>(SizeClassAllocator->getBatchClassBlock());856 TB->clear();857 858 BG->CompactPtrGroupBase = CompactPtrGroupBase;859 BG->Batches.push_front(TB);860 BG->BytesInBGAtLastCheckpoint = 0;861 BG->MaxCachedPerBatch = MaxNumBlocksInBatch;862 863 return BG;864 };865 866 auto InsertBlocks = [&](BatchGroupT *BG, CompactPtrT *Array, u32 Size) {867 SinglyLinkedList<BatchT> &Batches = BG->Batches;868 BatchT *CurBatch = Batches.front();869 DCHECK_NE(CurBatch, nullptr);870 871 for (u32 I = 0; I < Size;) {872 DCHECK_GE(BG->MaxCachedPerBatch, CurBatch->getCount());873 u16 UnusedSlots =874 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount());875 if (UnusedSlots == 0) {876 CurBatch = reinterpret_cast<BatchT *>(877 SizeClassAllocator->getBatchClassBlock());878 CurBatch->clear();879 Batches.push_front(CurBatch);880 UnusedSlots = BG->MaxCachedPerBatch;881 }882 // `UnusedSlots` is u16 so the result will be also fit in u16.883 u16 AppendSize = static_cast<u16>(Min<u32>(UnusedSlots, Size - I));884 CurBatch->appendFromArray(&Array[I], AppendSize);885 I += AppendSize;886 }887 };888 889 Region->FreeListInfo.PushedBlocks += Size;890 BatchGroupT *Cur = Region->FreeListInfo.BlockList.front();891 892 // In the following, `Cur` always points to the BatchGroup for blocks that893 // will be pushed next. `Prev` is the element right before `Cur`.894 BatchGroupT *Prev = nullptr;895 896 while (Cur != nullptr &&897 compactPtrGroup(Array[0]) > Cur->CompactPtrGroupBase) {898 Prev = Cur;899 Cur = Cur->Next;900 }901 902 if (Cur == nullptr || compactPtrGroup(Array[0]) != Cur->CompactPtrGroupBase) {903 Cur = CreateGroup(compactPtrGroup(Array[0]));904 if (Prev == nullptr)905 Region->FreeListInfo.BlockList.push_front(Cur);906 else907 Region->FreeListInfo.BlockList.insert(Prev, Cur);908 }909 910 // All the blocks are from the same group, just push without checking group911 // id.912 if (SameGroup) {913 for (u32 I = 0; I < Size; ++I)914 DCHECK_EQ(compactPtrGroup(Array[I]), Cur->CompactPtrGroupBase);915 916 InsertBlocks(Cur, Array, Size);917 return;918 }919 920 // The blocks are sorted by group id. Determine the segment of group and921 // push them to their group together.922 u32 Count = 1;923 for (u32 I = 1; I < Size; ++I) {924 if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I])) {925 DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->CompactPtrGroupBase);926 InsertBlocks(Cur, Array + I - Count, Count);927 928 while (Cur != nullptr &&929 compactPtrGroup(Array[I]) > Cur->CompactPtrGroupBase) {930 Prev = Cur;931 Cur = Cur->Next;932 }933 934 if (Cur == nullptr ||935 compactPtrGroup(Array[I]) != Cur->CompactPtrGroupBase) {936 Cur = CreateGroup(compactPtrGroup(Array[I]));937 DCHECK_NE(Prev, nullptr);938 Region->FreeListInfo.BlockList.insert(Prev, Cur);939 }940 941 Count = 1;942 } else {943 ++Count;944 }945 }946 947 InsertBlocks(Cur, Array + Size - Count, Count);948}949 950template <typename Config>951void SizeClassAllocator64<Config>::pushBatchClassBlocks(RegionInfo *Region,952 CompactPtrT *Array,953 u32 Size)954 REQUIRES(Region->FLLock) {955 DCHECK_EQ(Region, getRegionInfo(SizeClassMap::BatchClassId));956 957 // Free blocks are recorded by Batch in freelist for all958 // size-classes. In addition, Batch is allocated from BatchClassId.959 // In order not to use additional block to record the free blocks in960 // BatchClassId, they are self-contained. I.e., A Batch records the961 // block address of itself. See the figure below:962 //963 // Batch at 0xABCD964 // +----------------------------+965 // | Free blocks' addr |966 // | +------+------+------+ |967 // | |0xABCD|... |... | |968 // | +------+------+------+ |969 // +----------------------------+970 //971 // When we allocate all the free blocks in the Batch, the block used972 // by Batch is also free for use. We don't need to recycle the973 // Batch. Note that the correctness is maintained by the invariant,974 //975 // Each popBlocks() request returns the entire Batch. Returning976 // part of the blocks in a Batch is invalid.977 //978 // This ensures that Batch won't leak the address itself while it's979 // still holding other valid data.980 //981 // Besides, BatchGroup is also allocated from BatchClassId and has its982 // address recorded in the Batch too. To maintain the correctness,983 //984 // The address of BatchGroup is always recorded in the last Batch985 // in the freelist (also imply that the freelist should only be986 // updated with push_front). Once the last Batch is popped,987 // the block used by BatchGroup is also free for use.988 //989 // With this approach, the blocks used by BatchGroup and Batch are990 // reusable and don't need additional space for them.991 992 Region->FreeListInfo.PushedBlocks += Size;993 BatchGroupT *BG = Region->FreeListInfo.BlockList.front();994 995 if (BG == nullptr) {996 // Construct `BatchGroup` on the last element.997 BG = reinterpret_cast<BatchGroupT *>(998 decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1]));999 --Size;1000 BG->Batches.clear();1001 // BatchClass hasn't enabled memory group. Use `0` to indicate there's no1002 // memory group here.1003 BG->CompactPtrGroupBase = 0;1004 BG->BytesInBGAtLastCheckpoint = 0;1005 BG->MaxCachedPerBatch = SizeClassAllocatorT::getMaxCached(1006 getSizeByClassId(SizeClassMap::BatchClassId));1007 1008 Region->FreeListInfo.BlockList.push_front(BG);1009 }1010 1011 if (UNLIKELY(Size == 0))1012 return;1013 1014 // This happens under 2 cases.1015 // 1. just allocated a new `BatchGroup`.1016 // 2. Only 1 block is pushed when the freelist is empty.1017 if (BG->Batches.empty()) {1018 // Construct the `Batch` on the last element.1019 BatchT *TB = reinterpret_cast<BatchT *>(1020 decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1]));1021 TB->clear();1022 // As mentioned above, addresses of `Batch` and `BatchGroup` are1023 // recorded in the Batch.1024 TB->add(Array[Size - 1]);1025 TB->add(compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(BG)));1026 --Size;1027 BG->Batches.push_front(TB);1028 }1029 1030 BatchT *CurBatch = BG->Batches.front();1031 DCHECK_NE(CurBatch, nullptr);1032 1033 for (u32 I = 0; I < Size;) {1034 u16 UnusedSlots =1035 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount());1036 if (UnusedSlots == 0) {1037 CurBatch = reinterpret_cast<BatchT *>(1038 decompactPtr(SizeClassMap::BatchClassId, Array[I]));1039 CurBatch->clear();1040 // Self-contained1041 CurBatch->add(Array[I]);1042 ++I;1043 // TODO(chiahungduan): Avoid the use of push_back() in `Batches` of1044 // BatchClassId.1045 BG->Batches.push_front(CurBatch);1046 UnusedSlots = static_cast<u16>(BG->MaxCachedPerBatch - 1);1047 }1048 // `UnusedSlots` is u16 so the result will be also fit in u16.1049 const u16 AppendSize = static_cast<u16>(Min<u32>(UnusedSlots, Size - I));1050 CurBatch->appendFromArray(&Array[I], AppendSize);1051 I += AppendSize;1052 }1053}1054 1055template <typename Config>1056void SizeClassAllocator64<Config>::disable() NO_THREAD_SAFETY_ANALYSIS {1057 // The BatchClassId must be locked last since other classes can use it.1058 for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {1059 if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)1060 continue;1061 getRegionInfo(static_cast<uptr>(I))->MMLock.lock();1062 getRegionInfo(static_cast<uptr>(I))->FLLock.lock();1063 }1064 getRegionInfo(SizeClassMap::BatchClassId)->MMLock.lock();1065 getRegionInfo(SizeClassMap::BatchClassId)->FLLock.lock();1066}1067 1068template <typename Config>1069void SizeClassAllocator64<Config>::enable() NO_THREAD_SAFETY_ANALYSIS {1070 getRegionInfo(SizeClassMap::BatchClassId)->FLLock.unlock();1071 getRegionInfo(SizeClassMap::BatchClassId)->MMLock.unlock();1072 for (uptr I = 0; I < NumClasses; I++) {1073 if (I == SizeClassMap::BatchClassId)1074 continue;1075 getRegionInfo(I)->FLLock.unlock();1076 getRegionInfo(I)->MMLock.unlock();1077 }1078}1079 1080template <typename Config>1081template <typename F>1082void SizeClassAllocator64<Config>::iterateOverBlocks(F Callback) {1083 for (uptr I = 0; I < NumClasses; I++) {1084 if (I == SizeClassMap::BatchClassId)1085 continue;1086 RegionInfo *Region = getRegionInfo(I);1087 // TODO: The call of `iterateOverBlocks` requires disabling1088 // SizeClassAllocator64. We may consider locking each region on demand1089 // only.1090 Region->FLLock.assertHeld();1091 Region->MMLock.assertHeld();1092 const uptr BlockSize = getSizeByClassId(I);1093 const uptr From = Region->RegionBeg;1094 const uptr To = From + Region->MemMapInfo.AllocatedUser;1095 for (uptr Block = From; Block < To; Block += BlockSize)1096 Callback(Block);1097 }1098}1099 1100template <typename Config>1101void SizeClassAllocator64<Config>::getStats(ScopedString *Str) {1102 // TODO(kostyak): get the RSS per region.1103 uptr TotalMapped = 0;1104 uptr PoppedBlocks = 0;1105 uptr PushedBlocks = 0;1106 for (uptr I = 0; I < NumClasses; I++) {1107 RegionInfo *Region = getRegionInfo(I);1108 {1109 ScopedLock L(Region->MMLock);1110 TotalMapped += Region->MemMapInfo.MappedUser;1111 }1112 {1113 ScopedLock L(Region->FLLock);1114 PoppedBlocks += Region->FreeListInfo.PoppedBlocks;1115 PushedBlocks += Region->FreeListInfo.PushedBlocks;1116 }1117 }1118 const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs);1119 Str->append("Stats: SizeClassAllocator64: %zuM mapped (%uM rss) in %zu "1120 "allocations; remains %zu; ReleaseToOsIntervalMs = %d\n",1121 TotalMapped >> 20, 0U, PoppedBlocks, PoppedBlocks - PushedBlocks,1122 IntervalMs >= 0 ? IntervalMs : -1);1123 1124 for (uptr I = 0; I < NumClasses; I++) {1125 RegionInfo *Region = getRegionInfo(I);1126 ScopedLock L1(Region->MMLock);1127 ScopedLock L2(Region->FLLock);1128 getStats(Str, I, Region);1129 }1130}1131 1132template <typename Config>1133void SizeClassAllocator64<Config>::getStats(ScopedString *Str, uptr ClassId,1134 RegionInfo *Region)1135 REQUIRES(Region->MMLock, Region->FLLock) {1136 if (Region->MemMapInfo.MappedUser == 0)1137 return;1138 const uptr BlockSize = getSizeByClassId(ClassId);1139 const uptr InUseBlocks =1140 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;1141 const uptr BytesInFreeList =1142 Region->MemMapInfo.AllocatedUser - InUseBlocks * BlockSize;1143 uptr RegionPushedBytesDelta = 0;1144 if (BytesInFreeList >= Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {1145 RegionPushedBytesDelta =1146 BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint;1147 }1148 const uptr TotalChunks = Region->MemMapInfo.AllocatedUser / BlockSize;1149 Str->append(1150 "%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "1151 "inuse: %6zu total: %6zu releases attempted: %6zu last "1152 "released: %6zuK latest pushed bytes: %6zuK region: 0x%zx "1153 "(0x%zx)\n",1154 Region->Exhausted ? "E" : " ", ClassId, getSizeByClassId(ClassId),1155 Region->MemMapInfo.MappedUser >> 10, Region->FreeListInfo.PoppedBlocks,1156 Region->FreeListInfo.PushedBlocks, InUseBlocks, TotalChunks,1157 Region->ReleaseInfo.NumReleasesAttempted,1158 Region->ReleaseInfo.LastReleasedBytes >> 10, RegionPushedBytesDelta >> 10,1159 Region->RegionBeg, getRegionBaseByClassId(ClassId));1160}1161 1162template <typename Config>1163void SizeClassAllocator64<Config>::getFragmentationInfo(ScopedString *Str) {1164 Str->append(1165 "Fragmentation Stats: SizeClassAllocator64: page size = %zu bytes\n",1166 getPageSizeCached());1167 1168 for (uptr I = 1; I < NumClasses; I++) {1169 RegionInfo *Region = getRegionInfo(I);1170 ScopedLock L(Region->MMLock);1171 getRegionFragmentationInfo(Region, I, Str);1172 }1173}1174 1175template <typename Config>1176void SizeClassAllocator64<Config>::getRegionFragmentationInfo(1177 RegionInfo *Region, uptr ClassId, ScopedString *Str)1178 REQUIRES(Region->MMLock) {1179 const uptr BlockSize = getSizeByClassId(ClassId);1180 const uptr AllocatedUserEnd =1181 Region->MemMapInfo.AllocatedUser + Region->RegionBeg;1182 1183 SinglyLinkedList<BatchGroupT> GroupsToRelease;1184 {1185 ScopedLock L(Region->FLLock);1186 GroupsToRelease = Region->FreeListInfo.BlockList;1187 Region->FreeListInfo.BlockList.clear();1188 }1189 1190 FragmentationRecorder Recorder;1191 if (!GroupsToRelease.empty()) {1192 PageReleaseContext Context =1193 markFreeBlocks(Region, BlockSize, AllocatedUserEnd,1194 getCompactPtrBaseByClassId(ClassId), GroupsToRelease);1195 auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };1196 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);1197 1198 mergeGroupsToReleaseBack(Region, GroupsToRelease);1199 }1200 1201 ScopedLock L(Region->FLLock);1202 const uptr PageSize = getPageSizeCached();1203 const uptr TotalBlocks = Region->MemMapInfo.AllocatedUser / BlockSize;1204 const uptr InUseBlocks =1205 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;1206 const uptr AllocatedPagesCount =1207 roundUp(Region->MemMapInfo.AllocatedUser, PageSize) / PageSize;1208 DCHECK_GE(AllocatedPagesCount, Recorder.getReleasedPagesCount());1209 const uptr InUsePages =1210 AllocatedPagesCount - Recorder.getReleasedPagesCount();1211 const uptr InUseBytes = InUsePages * PageSize;1212 1213 uptr Integral;1214 uptr Fractional;1215 computePercentage(BlockSize * InUseBlocks, InUseBytes, &Integral,1216 &Fractional);1217 Str->append(" %02zu (%6zu): inuse/total blocks: %6zu/%6zu inuse/total "1218 "pages: %6zu/%6zu inuse bytes: %6zuK util: %3zu.%02zu%%\n",1219 ClassId, BlockSize, InUseBlocks, TotalBlocks, InUsePages,1220 AllocatedPagesCount, InUseBytes >> 10, Integral, Fractional);1221}1222 1223template <typename Config>1224void SizeClassAllocator64<Config>::getMemoryGroupFragmentationInfoInRegion(1225 RegionInfo *Region, uptr ClassId, ScopedString *Str)1226 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {1227 const uptr BlockSize = getSizeByClassId(ClassId);1228 const uptr AllocatedUserEnd =1229 Region->MemMapInfo.AllocatedUser + Region->RegionBeg;1230 1231 SinglyLinkedList<BatchGroupT> GroupsToRelease;1232 {1233 ScopedLock L(Region->FLLock);1234 GroupsToRelease = Region->FreeListInfo.BlockList;1235 Region->FreeListInfo.BlockList.clear();1236 }1237 1238 constexpr uptr GroupSize = (1UL << GroupSizeLog);1239 constexpr uptr MaxNumGroups = RegionSize / GroupSize;1240 1241 MemoryGroupFragmentationRecorder<GroupSize, MaxNumGroups> Recorder;1242 if (!GroupsToRelease.empty()) {1243 PageReleaseContext Context =1244 markFreeBlocks(Region, BlockSize, AllocatedUserEnd,1245 getCompactPtrBaseByClassId(ClassId), GroupsToRelease);1246 auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };1247 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);1248 1249 mergeGroupsToReleaseBack(Region, GroupsToRelease);1250 }1251 1252 Str->append("MemoryGroupFragmentationInfo in Region %zu (%zu)\n", ClassId,1253 BlockSize);1254 1255 const uptr MaxNumGroupsInUse =1256 roundUp(Region->MemMapInfo.AllocatedUser, GroupSize) / GroupSize;1257 for (uptr I = 0; I < MaxNumGroupsInUse; ++I) {1258 uptr Integral;1259 uptr Fractional;1260 computePercentage(Recorder.NumPagesInOneGroup - Recorder.getNumFreePages(I),1261 Recorder.NumPagesInOneGroup, &Integral, &Fractional);1262 Str->append("MemoryGroup #%zu (0x%zx): util: %3zu.%02zu%%\n", I,1263 Region->RegionBeg + I * GroupSize, Integral, Fractional);1264 }1265}1266 1267template <typename Config>1268void SizeClassAllocator64<Config>::getMemoryGroupFragmentationInfo(1269 ScopedString *Str) {1270 Str->append(1271 "Fragmentation Stats: SizeClassAllocator64: page size = %zu bytes\n",1272 getPageSizeCached());1273 1274 for (uptr I = 1; I < NumClasses; I++) {1275 RegionInfo *Region = getRegionInfo(I);1276 ScopedLock L(Region->MMLock);1277 getMemoryGroupFragmentationInfoInRegion(Region, I, Str);1278 }1279}1280 1281template <typename Config>1282bool SizeClassAllocator64<Config>::setOption(Option O, sptr Value) {1283 if (O == Option::ReleaseInterval) {1284 const s32 Interval =1285 Max(Min(static_cast<s32>(Value), Config::getMaxReleaseToOsIntervalMs()),1286 Config::getMinReleaseToOsIntervalMs());1287 atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval);1288 return true;1289 }1290 // Not supported by the Primary, but not an error either.1291 return true;1292}1293 1294template <typename Config>1295uptr SizeClassAllocator64<Config>::tryReleaseToOS(uptr ClassId,1296 ReleaseToOS ReleaseType) {1297 RegionInfo *Region = getRegionInfo(ClassId);1298 // Note that the tryLock() may fail spuriously, given that it should rarely1299 // happen and page releasing is fine to skip, we don't take certain1300 // approaches to ensure one page release is done.1301 if (Region->MMLock.tryLock()) {1302 uptr BytesReleased = releaseToOSMaybe(Region, ClassId, ReleaseType);1303 Region->MMLock.unlock();1304 return BytesReleased;1305 }1306 return 0;1307}1308 1309template <typename Config>1310uptr SizeClassAllocator64<Config>::releaseToOS(ReleaseToOS ReleaseType) {1311 SCUDO_SCOPED_TRACE(GetPrimaryReleaseToOSTraceName(ReleaseType));1312 1313 uptr TotalReleasedBytes = 0;1314 for (uptr I = 0; I < NumClasses; I++) {1315 if (I == SizeClassMap::BatchClassId)1316 continue;1317 RegionInfo *Region = getRegionInfo(I);1318 ScopedLock L(Region->MMLock);1319 TotalReleasedBytes += releaseToOSMaybe(Region, I, ReleaseType);1320 }1321 return TotalReleasedBytes;1322}1323 1324template <typename Config>1325/* static */ BlockInfo SizeClassAllocator64<Config>::findNearestBlock(1326 const char *RegionInfoData, uptr Ptr) NO_THREAD_SAFETY_ANALYSIS {1327 const RegionInfo *RegionInfoArray =1328 reinterpret_cast<const RegionInfo *>(RegionInfoData);1329 1330 uptr ClassId;1331 uptr MinDistance = -1UL;1332 for (uptr I = 0; I != NumClasses; ++I) {1333 if (I == SizeClassMap::BatchClassId)1334 continue;1335 uptr Begin = RegionInfoArray[I].RegionBeg;1336 // TODO(chiahungduan): In fact, We need to lock the RegionInfo::MMLock.1337 // However, the RegionInfoData is passed with const qualifier and lock the1338 // mutex requires modifying RegionInfoData, which means we need to remove1339 // the const qualifier. This may lead to another undefined behavior (The1340 // first one is accessing `AllocatedUser` without locking. It's better to1341 // pass `RegionInfoData` as `void *` then we can lock the mutex properly.1342 uptr End = Begin + RegionInfoArray[I].MemMapInfo.AllocatedUser;1343 if (Begin > End || End - Begin < SizeClassMap::getSizeByClassId(I))1344 continue;1345 uptr RegionDistance;1346 if (Begin <= Ptr) {1347 if (Ptr < End)1348 RegionDistance = 0;1349 else1350 RegionDistance = Ptr - End;1351 } else {1352 RegionDistance = Begin - Ptr;1353 }1354 1355 if (RegionDistance < MinDistance) {1356 MinDistance = RegionDistance;1357 ClassId = I;1358 }1359 }1360 1361 BlockInfo B = {};1362 if (MinDistance <= 8192) {1363 B.RegionBegin = RegionInfoArray[ClassId].RegionBeg;1364 B.RegionEnd =1365 B.RegionBegin + RegionInfoArray[ClassId].MemMapInfo.AllocatedUser;1366 B.BlockSize = SizeClassMap::getSizeByClassId(ClassId);1367 B.BlockBegin = B.RegionBegin + uptr(sptr(Ptr - B.RegionBegin) /1368 sptr(B.BlockSize) * sptr(B.BlockSize));1369 while (B.BlockBegin < B.RegionBegin)1370 B.BlockBegin += B.BlockSize;1371 while (B.RegionEnd < B.BlockBegin + B.BlockSize)1372 B.BlockBegin -= B.BlockSize;1373 }1374 return B;1375}1376 1377template <typename Config>1378uptr SizeClassAllocator64<Config>::releaseToOSMaybe(RegionInfo *Region,1379 uptr ClassId,1380 ReleaseToOS ReleaseType)1381 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {1382 const uptr BlockSize = getSizeByClassId(ClassId);1383 uptr BytesInFreeList;1384 const uptr AllocatedUserEnd =1385 Region->MemMapInfo.AllocatedUser + Region->RegionBeg;1386 uptr RegionPushedBytesDelta = 0;1387 SinglyLinkedList<BatchGroupT> GroupsToRelease;1388 1389 {1390 ScopedLock L(Region->FLLock);1391 1392 BytesInFreeList =1393 Region->MemMapInfo.AllocatedUser - (Region->FreeListInfo.PoppedBlocks -1394 Region->FreeListInfo.PushedBlocks) *1395 BlockSize;1396 if (UNLIKELY(BytesInFreeList == 0))1397 return 0;1398 1399 // ==================================================================== //1400 // 1. Check if we have enough free blocks and if it's worth doing a page1401 // release.1402 // ==================================================================== //1403 if (ReleaseType != ReleaseToOS::ForceAll &&1404 !hasChanceToReleasePages(Region, BlockSize, BytesInFreeList,1405 ReleaseType)) {1406 return 0;1407 }1408 1409 // Given that we will unlock the freelist for block operations, cache the1410 // value here so that when we are adapting the `TryReleaseThreshold`1411 // later, we are using the right metric.1412 RegionPushedBytesDelta =1413 BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint;1414 1415 // ==================================================================== //1416 // 2. Determine which groups can release the pages. Use a heuristic to1417 // gather groups that are candidates for doing a release.1418 // ==================================================================== //1419 if (ReleaseType == ReleaseToOS::ForceAll) {1420 GroupsToRelease = Region->FreeListInfo.BlockList;1421 Region->FreeListInfo.BlockList.clear();1422 } else {1423 GroupsToRelease =1424 collectGroupsToRelease(Region, BlockSize, AllocatedUserEnd,1425 getCompactPtrBaseByClassId(ClassId));1426 }1427 if (GroupsToRelease.empty())1428 return 0;1429 }1430 1431 // The following steps contribute to the majority time spent in page1432 // releasing thus we increment the counter here.1433 ++Region->ReleaseInfo.NumReleasesAttempted;1434 1435 // Note that we have extracted the `GroupsToRelease` from region freelist.1436 // It's safe to let pushBlocks()/popBlocks() access the remaining region1437 // freelist. In the steps 3 and 4, we will temporarily release the FLLock1438 // and lock it again before step 5.1439 1440 // ==================================================================== //1441 // 3. Mark the free blocks in `GroupsToRelease` in the `PageReleaseContext`.1442 // Then we can tell which pages are in-use by querying1443 // `PageReleaseContext`.1444 // ==================================================================== //1445 1446 // Only add trace point after the quick returns have occurred to avoid1447 // incurring performance penalties. Most of the time in this function1448 // will be the mark free blocks call and the actual release to OS call.1449 SCUDO_SCOPED_TRACE(GetPrimaryReleaseToOSMaybeTraceName(ReleaseType));1450 1451 PageReleaseContext Context =1452 markFreeBlocks(Region, BlockSize, AllocatedUserEnd,1453 getCompactPtrBaseByClassId(ClassId), GroupsToRelease);1454 if (UNLIKELY(!Context.hasBlockMarked())) {1455 mergeGroupsToReleaseBack(Region, GroupsToRelease);1456 return 0;1457 }1458 1459 // ==================================================================== //1460 // 4. Release the unused physical pages back to the OS.1461 // ==================================================================== //1462 RegionReleaseRecorder<MemMapT> Recorder(&Region->MemMapInfo.MemMap,1463 Region->RegionBeg,1464 Context.getReleaseOffset());1465 auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };1466 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);1467 if (Recorder.getReleasedBytes() > 0) {1468 // This is the case that we didn't hit the release threshold but it has1469 // been past a certain period of time. Thus we try to release some pages1470 // and if it does release some additional pages, it's hint that we are1471 // able to lower the threshold. Currently, this case happens when the1472 // `RegionPushedBytesDelta` is over half of the `TryReleaseThreshold`. As1473 // a result, we shrink the threshold to half accordingly.1474 // TODO(chiahungduan): Apply the same adjustment strategy to small blocks.1475 if (!isSmallBlock(BlockSize)) {1476 if (RegionPushedBytesDelta < Region->ReleaseInfo.TryReleaseThreshold &&1477 Recorder.getReleasedBytes() >1478 Region->ReleaseInfo.LastReleasedBytes +1479 getMinReleaseAttemptSize(BlockSize)) {1480 Region->ReleaseInfo.TryReleaseThreshold =1481 Max(Region->ReleaseInfo.TryReleaseThreshold / 2,1482 getMinReleaseAttemptSize(BlockSize));1483 }1484 }1485 1486 Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;1487 Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();1488 }1489 Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast();1490 1491 if (Region->ReleaseInfo.PendingPushedBytesDelta > 0) {1492 // Instead of increasing the threshold by the amount of1493 // `PendingPushedBytesDelta`, we only increase half of the amount so that1494 // it won't be a leap (which may lead to higher memory pressure) because1495 // of certain memory usage bursts which don't happen frequently.1496 Region->ReleaseInfo.TryReleaseThreshold +=1497 Region->ReleaseInfo.PendingPushedBytesDelta / 2;1498 // This is another guard of avoiding the growth of threshold indefinitely.1499 // Note that we may consider to make this configurable if we have a better1500 // way to model this.1501 Region->ReleaseInfo.TryReleaseThreshold = Min<uptr>(1502 Region->ReleaseInfo.TryReleaseThreshold, (1UL << GroupSizeLog) / 2);1503 Region->ReleaseInfo.PendingPushedBytesDelta = 0;1504 }1505 1506 // ====================================================================== //1507 // 5. Merge the `GroupsToRelease` back to the freelist.1508 // ====================================================================== //1509 mergeGroupsToReleaseBack(Region, GroupsToRelease);1510 1511 return Recorder.getReleasedBytes();1512}1513 1514template <typename Config>1515bool SizeClassAllocator64<Config>::hasChanceToReleasePages(1516 RegionInfo *Region, uptr BlockSize, uptr BytesInFreeList,1517 ReleaseToOS ReleaseType) REQUIRES(Region->MMLock, Region->FLLock) {1518 DCHECK_GE(Region->FreeListInfo.PoppedBlocks,1519 Region->FreeListInfo.PushedBlocks);1520 // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value1521 // so that we won't underestimate the releasable pages. For example, the1522 // following is the region usage,1523 //1524 // BytesInFreeListAtLastCheckpoint AllocatedUser1525 // v v1526 // |--------------------------------------->1527 // ^ ^1528 // BytesInFreeList ReleaseThreshold1529 //1530 // In general, if we have collected enough bytes and the amount of free1531 // bytes meets the ReleaseThreshold, we will try to do page release. If we1532 // don't update `BytesInFreeListAtLastCheckpoint` when the current1533 // `BytesInFreeList` is smaller, we may take longer time to wait for enough1534 // freed blocks because we miss the bytes between1535 // (BytesInFreeListAtLastCheckpoint - BytesInFreeList).1536 if (BytesInFreeList <= Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {1537 Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;1538 }1539 1540 const uptr RegionPushedBytesDelta =1541 BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint;1542 1543 if (ReleaseType == ReleaseToOS::Normal) {1544 if (RegionPushedBytesDelta < Region->ReleaseInfo.TryReleaseThreshold / 2)1545 return false;1546 1547 const s64 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs);1548 if (IntervalMs < 0)1549 return false;1550 1551 const u64 IntervalNs = static_cast<u64>(IntervalMs) * 1000000;1552 const u64 CurTimeNs = getMonotonicTimeFast();1553 const u64 DiffSinceLastReleaseNs =1554 CurTimeNs - Region->ReleaseInfo.LastReleaseAtNs;1555 1556 // At here, `RegionPushedBytesDelta` is more than half of1557 // `TryReleaseThreshold`. If the last release happened 2 release interval1558 // before, we will still try to see if there's any chance to release some1559 // memory even it doesn't exceed the threshold.1560 if (RegionPushedBytesDelta < Region->ReleaseInfo.TryReleaseThreshold) {1561 // We want the threshold to have a shorter response time to the variant1562 // memory usage patterns. According to data collected during experiments1563 // (which were done with 1, 2, 4, 8 intervals), `2` strikes the better1564 // balance between the memory usage and number of page release attempts.1565 if (DiffSinceLastReleaseNs < 2 * IntervalNs)1566 return false;1567 } else if (DiffSinceLastReleaseNs < IntervalNs) {1568 // `TryReleaseThreshold` is capped by (1UL << GroupSizeLog) / 2). If1569 // RegionPushedBytesDelta grows to twice the threshold, it implies some1570 // huge deallocations have happened so we better try to release some1571 // pages. Note this tends to happen for larger block sizes.1572 if (RegionPushedBytesDelta > (1ULL << GroupSizeLog))1573 return true;1574 1575 // In this case, we are over the threshold but we just did some page1576 // release in the same release interval. This is a hint that we may want1577 // a higher threshold so that we can release more memory at once.1578 // `TryReleaseThreshold` will be adjusted according to how many bytes1579 // are not released, i.e., the `PendingPushedBytesdelta` here.1580 // TODO(chiahungduan): Apply the same adjustment strategy to small1581 // blocks.1582 if (!isSmallBlock(BlockSize))1583 Region->ReleaseInfo.PendingPushedBytesDelta = RegionPushedBytesDelta;1584 1585 // Memory was returned recently.1586 return false;1587 }1588 } // if (ReleaseType == ReleaseToOS::Normal)1589 1590 return true;1591}1592 1593template <typename Config>1594SinglyLinkedList<typename SizeClassAllocator64<Config>::BatchGroupT>1595SizeClassAllocator64<Config>::collectGroupsToRelease(1596 RegionInfo *Region, const uptr BlockSize, const uptr AllocatedUserEnd,1597 const uptr CompactPtrBase) REQUIRES(Region->MMLock, Region->FLLock) {1598 const uptr GroupSize = (1UL << GroupSizeLog);1599 const uptr PageSize = getPageSizeCached();1600 SinglyLinkedList<BatchGroupT> GroupsToRelease;1601 1602 // We are examining each group and will take the minimum distance to the1603 // release threshold as the next `TryReleaseThreshold`. Note that if the1604 // size of free blocks has reached the release threshold, the distance to1605 // the next release will be PageSize * SmallerBlockReleasePageDelta. See the1606 // comment on `SmallerBlockReleasePageDelta` for more details.1607 uptr MinDistToThreshold = GroupSize;1608 1609 for (BatchGroupT *BG = Region->FreeListInfo.BlockList.front(),1610 *Prev = nullptr;1611 BG != nullptr;) {1612 // Group boundary is always GroupSize-aligned from CompactPtr base. The1613 // layout of memory groups is like,1614 //1615 // (CompactPtrBase)1616 // #1 CompactPtrGroupBase #2 CompactPtrGroupBase ...1617 // | | |1618 // v v v1619 // +-----------------------+-----------------------+1620 // \ / \ /1621 // --- GroupSize --- --- GroupSize ---1622 //1623 // After decompacting the CompactPtrGroupBase, we expect the alignment1624 // property is held as well.1625 const uptr BatchGroupBase =1626 decompactGroupBase(CompactPtrBase, BG->CompactPtrGroupBase);1627 DCHECK_LE(Region->RegionBeg, BatchGroupBase);1628 DCHECK_GE(AllocatedUserEnd, BatchGroupBase);1629 DCHECK_EQ((Region->RegionBeg - BatchGroupBase) % GroupSize, 0U);1630 // Batches are pushed in front of BG.Batches. The first one may1631 // not have all caches used.1632 const uptr NumBlocks = (BG->Batches.size() - 1) * BG->MaxCachedPerBatch +1633 BG->Batches.front()->getCount();1634 const uptr BytesInBG = NumBlocks * BlockSize;1635 1636 if (BytesInBG <= BG->BytesInBGAtLastCheckpoint) {1637 BG->BytesInBGAtLastCheckpoint = BytesInBG;1638 Prev = BG;1639 BG = BG->Next;1640 continue;1641 }1642 1643 const uptr PushedBytesDelta = BytesInBG - BG->BytesInBGAtLastCheckpoint;1644 if (PushedBytesDelta < getMinReleaseAttemptSize(BlockSize)) {1645 Prev = BG;1646 BG = BG->Next;1647 continue;1648 }1649 1650 // Given the randomness property, we try to release the pages only if the1651 // bytes used by free blocks exceed certain proportion of group size. Note1652 // that this heuristic only applies when all the spaces in a BatchGroup1653 // are allocated.1654 if (isSmallBlock(BlockSize)) {1655 const uptr BatchGroupEnd = BatchGroupBase + GroupSize;1656 const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd1657 ? GroupSize1658 : AllocatedUserEnd - BatchGroupBase;1659 const uptr ReleaseThreshold =1660 (AllocatedGroupSize * (100 - 1U - BlockSize / 16U)) / 100U;1661 const bool HighDensity = BytesInBG >= ReleaseThreshold;1662 const bool MayHaveReleasedAll = NumBlocks >= (GroupSize / BlockSize);1663 // If all blocks in the group are released, we will do range marking1664 // which is fast. Otherwise, we will wait until we have accumulated1665 // a certain amount of free memory.1666 const bool ReachReleaseDelta =1667 MayHaveReleasedAll1668 ? true1669 : PushedBytesDelta >= PageSize * SmallerBlockReleasePageDelta;1670 1671 if (!HighDensity) {1672 DCHECK_LE(BytesInBG, ReleaseThreshold);1673 // The following is the usage of a memroy group,1674 //1675 // BytesInBG ReleaseThreshold1676 // / \ v1677 // +---+---------------------------+-----+1678 // | | | | |1679 // +---+---------------------------+-----+1680 // \ / ^1681 // PushedBytesDelta GroupEnd1682 MinDistToThreshold =1683 Min(MinDistToThreshold,1684 ReleaseThreshold - BytesInBG + PushedBytesDelta);1685 } else {1686 // If it reaches high density at this round, the next time we will try1687 // to release is based on SmallerBlockReleasePageDelta1688 MinDistToThreshold =1689 Min(MinDistToThreshold, PageSize * SmallerBlockReleasePageDelta);1690 }1691 1692 if (!HighDensity || !ReachReleaseDelta) {1693 Prev = BG;1694 BG = BG->Next;1695 continue;1696 }1697 }1698 1699 // If `BG` is the first BatchGroupT in the list, we only need to advance1700 // `BG` and call FreeListInfo.BlockList::pop_front(). No update is needed1701 // for `Prev`.1702 //1703 // (BG) (BG->Next)1704 // Prev Cur BG1705 // | | |1706 // v v v1707 // nil +--+ +--+1708 // |X | -> | | -> ...1709 // +--+ +--+1710 //1711 // Otherwise, `Prev` will be used to extract the `Cur` from the1712 // `FreeListInfo.BlockList`.1713 //1714 // (BG) (BG->Next)1715 // Prev Cur BG1716 // | | |1717 // v v v1718 // +--+ +--+ +--+1719 // | | -> |X | -> | | -> ...1720 // +--+ +--+ +--+1721 //1722 // After FreeListInfo.BlockList::extract(),1723 //1724 // Prev Cur BG1725 // | | |1726 // v v v1727 // +--+ +--+ +--+1728 // | |-+ |X | +->| | -> ...1729 // +--+ | +--+ | +--+1730 // +--------+1731 //1732 // Note that we need to advance before pushing this BatchGroup to1733 // GroupsToRelease because it's a destructive operation.1734 1735 BatchGroupT *Cur = BG;1736 BG = BG->Next;1737 1738 // Ideally, we may want to update this only after successful release.1739 // However, for smaller blocks, each block marking is a costly operation.1740 // Therefore, we update it earlier.1741 // TODO: Consider updating this after releasing pages if `ReleaseRecorder`1742 // can tell the released bytes in each group.1743 Cur->BytesInBGAtLastCheckpoint = BytesInBG;1744 1745 if (Prev != nullptr)1746 Region->FreeListInfo.BlockList.extract(Prev, Cur);1747 else1748 Region->FreeListInfo.BlockList.pop_front();1749 GroupsToRelease.push_back(Cur);1750 }1751 1752 // Only small blocks have the adaptive `TryReleaseThreshold`.1753 if (isSmallBlock(BlockSize)) {1754 // If the MinDistToThreshold is not updated, that means each memory group1755 // may have only pushed less than a page size. In that case, just set it1756 // back to normal.1757 if (MinDistToThreshold == GroupSize)1758 MinDistToThreshold = PageSize * SmallerBlockReleasePageDelta;1759 Region->ReleaseInfo.TryReleaseThreshold = MinDistToThreshold;1760 }1761 1762 return GroupsToRelease;1763}1764 1765template <typename Config>1766PageReleaseContext SizeClassAllocator64<Config>::markFreeBlocks(1767 RegionInfo *Region, const uptr BlockSize, const uptr AllocatedUserEnd,1768 const uptr CompactPtrBase, SinglyLinkedList<BatchGroupT> &GroupsToRelease)1769 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {1770 const uptr GroupSize = (1UL << GroupSizeLog);1771 auto DecompactPtr = [CompactPtrBase, this](CompactPtrT CompactPtr) {1772 return decompactPtrInternal(CompactPtrBase, CompactPtr);1773 };1774 1775 const uptr ReleaseBase = decompactGroupBase(1776 CompactPtrBase, GroupsToRelease.front()->CompactPtrGroupBase);1777 const uptr LastGroupEnd =1778 Min(decompactGroupBase(CompactPtrBase,1779 GroupsToRelease.back()->CompactPtrGroupBase) +1780 GroupSize,1781 AllocatedUserEnd);1782 // The last block may straddle the group boundary. Rounding up to BlockSize1783 // to get the exact range.1784 const uptr ReleaseEnd =1785 roundUpSlow(LastGroupEnd - Region->RegionBeg, BlockSize) +1786 Region->RegionBeg;1787 const uptr ReleaseRangeSize = ReleaseEnd - ReleaseBase;1788 const uptr ReleaseOffset = ReleaseBase - Region->RegionBeg;1789 1790 PageReleaseContext Context(BlockSize, /*NumberOfRegions=*/1U,1791 ReleaseRangeSize, ReleaseOffset);1792 // We may not be able to do the page release in a rare case that we may1793 // fail on PageMap allocation.1794 if (UNLIKELY(!Context.ensurePageMapAllocated()))1795 return Context;1796 1797 for (BatchGroupT &BG : GroupsToRelease) {1798 const uptr BatchGroupBase =1799 decompactGroupBase(CompactPtrBase, BG.CompactPtrGroupBase);1800 const uptr BatchGroupEnd = BatchGroupBase + GroupSize;1801 const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd1802 ? GroupSize1803 : AllocatedUserEnd - BatchGroupBase;1804 const uptr BatchGroupUsedEnd = BatchGroupBase + AllocatedGroupSize;1805 const bool MayContainLastBlockInRegion =1806 BatchGroupUsedEnd == AllocatedUserEnd;1807 const bool BlockAlignedWithUsedEnd =1808 (BatchGroupUsedEnd - Region->RegionBeg) % BlockSize == 0;1809 1810 uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize;1811 if (!BlockAlignedWithUsedEnd)1812 ++MaxContainedBlocks;1813 1814 const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch +1815 BG.Batches.front()->getCount();1816 1817 if (NumBlocks == MaxContainedBlocks) {1818 for (const auto &It : BG.Batches) {1819 if (&It != BG.Batches.front())1820 DCHECK_EQ(It.getCount(), BG.MaxCachedPerBatch);1821 for (u16 I = 0; I < It.getCount(); ++I)1822 DCHECK_EQ(compactPtrGroup(It.get(I)), BG.CompactPtrGroupBase);1823 }1824 1825 Context.markRangeAsAllCounted(BatchGroupBase, BatchGroupUsedEnd,1826 Region->RegionBeg, /*RegionIndex=*/0,1827 Region->MemMapInfo.AllocatedUser);1828 } else {1829 DCHECK_LT(NumBlocks, MaxContainedBlocks);1830 // Note that we don't always visit blocks in each BatchGroup so that we1831 // may miss the chance of releasing certain pages that cross1832 // BatchGroups.1833 Context.markFreeBlocksInRegion(1834 BG.Batches, DecompactPtr, Region->RegionBeg, /*RegionIndex=*/0,1835 Region->MemMapInfo.AllocatedUser, MayContainLastBlockInRegion);1836 }1837 }1838 1839 DCHECK(Context.hasBlockMarked());1840 1841 return Context;1842}1843 1844template <typename Config>1845void SizeClassAllocator64<Config>::mergeGroupsToReleaseBack(1846 RegionInfo *Region, SinglyLinkedList<BatchGroupT> &GroupsToRelease)1847 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {1848 ScopedLock L(Region->FLLock);1849 1850 // After merging two freelists, we may have redundant `BatchGroup`s that1851 // need to be recycled. The number of unused `BatchGroup`s is expected to be1852 // small. Pick a constant which is inferred from real programs.1853 constexpr uptr MaxUnusedSize = 8;1854 CompactPtrT Blocks[MaxUnusedSize];1855 u32 Idx = 0;1856 RegionInfo *BatchClassRegion = getRegionInfo(SizeClassMap::BatchClassId);1857 // We can't call pushBatchClassBlocks() to recycle the unused `BatchGroup`s1858 // when we are manipulating the freelist of `BatchClassRegion`. Instead, we1859 // should just push it back to the freelist when we merge two `BatchGroup`s.1860 // This logic hasn't been implemented because we haven't supported releasing1861 // pages in `BatchClassRegion`.1862 DCHECK_NE(BatchClassRegion, Region);1863 1864 // Merge GroupsToRelease back to the Region::FreeListInfo.BlockList. Note1865 // that both `Region->FreeListInfo.BlockList` and `GroupsToRelease` are1866 // sorted.1867 for (BatchGroupT *BG = Region->FreeListInfo.BlockList.front(),1868 *Prev = nullptr;1869 ;) {1870 if (BG == nullptr || GroupsToRelease.empty()) {1871 if (!GroupsToRelease.empty())1872 Region->FreeListInfo.BlockList.append_back(&GroupsToRelease);1873 break;1874 }1875 1876 DCHECK(!BG->Batches.empty());1877 1878 if (BG->CompactPtrGroupBase <1879 GroupsToRelease.front()->CompactPtrGroupBase) {1880 Prev = BG;1881 BG = BG->Next;1882 continue;1883 }1884 1885 BatchGroupT *Cur = GroupsToRelease.front();1886 BatchT *UnusedBatch = nullptr;1887 GroupsToRelease.pop_front();1888 1889 if (BG->CompactPtrGroupBase == Cur->CompactPtrGroupBase) {1890 // We have updated `BatchGroup::BytesInBGAtLastCheckpoint` while1891 // collecting the `GroupsToRelease`.1892 BG->BytesInBGAtLastCheckpoint = Cur->BytesInBGAtLastCheckpoint;1893 const uptr MaxCachedPerBatch = BG->MaxCachedPerBatch;1894 1895 // Note that the first Batches in both `Batches` may not be1896 // full and only the first Batch can have non-full blocks. Thus1897 // we have to merge them before appending one to another.1898 if (Cur->Batches.front()->getCount() == MaxCachedPerBatch) {1899 BG->Batches.append_back(&Cur->Batches);1900 } else {1901 BatchT *NonFullBatch = Cur->Batches.front();1902 Cur->Batches.pop_front();1903 const u16 NonFullBatchCount = NonFullBatch->getCount();1904 // The remaining Batches in `Cur` are full.1905 BG->Batches.append_back(&Cur->Batches);1906 1907 if (BG->Batches.front()->getCount() == MaxCachedPerBatch) {1908 // Only 1 non-full Batch, push it to the front.1909 BG->Batches.push_front(NonFullBatch);1910 } else {1911 const u16 NumBlocksToMove = static_cast<u16>(1912 Min(static_cast<u16>(MaxCachedPerBatch -1913 BG->Batches.front()->getCount()),1914 NonFullBatchCount));1915 BG->Batches.front()->appendFromBatch(NonFullBatch, NumBlocksToMove);1916 if (NonFullBatch->isEmpty())1917 UnusedBatch = NonFullBatch;1918 else1919 BG->Batches.push_front(NonFullBatch);1920 }1921 }1922 1923 const u32 NeededSlots = UnusedBatch == nullptr ? 1U : 2U;1924 if (UNLIKELY(Idx + NeededSlots > MaxUnusedSize)) {1925 ScopedLock L(BatchClassRegion->FLLock);1926 pushBatchClassBlocks(BatchClassRegion, Blocks, Idx);1927 if (conditionVariableEnabled())1928 BatchClassRegion->FLLockCV.notifyAll(BatchClassRegion->FLLock);1929 Idx = 0;1930 }1931 Blocks[Idx++] =1932 compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(Cur));1933 if (UnusedBatch) {1934 Blocks[Idx++] = compactPtr(SizeClassMap::BatchClassId,1935 reinterpret_cast<uptr>(UnusedBatch));1936 }1937 Prev = BG;1938 BG = BG->Next;1939 continue;1940 }1941 1942 // At here, the `BG` is the first BatchGroup with CompactPtrGroupBase1943 // larger than the first element in `GroupsToRelease`. We need to insert1944 // `GroupsToRelease::front()` (which is `Cur` below) before `BG`.1945 //1946 // 1. If `Prev` is nullptr, we simply push `Cur` to the front of1947 // FreeListInfo.BlockList.1948 // 2. Otherwise, use `insert()` which inserts an element next to `Prev`.1949 //1950 // Afterwards, we don't need to advance `BG` because the order between1951 // `BG` and the new `GroupsToRelease::front()` hasn't been checked.1952 if (Prev == nullptr)1953 Region->FreeListInfo.BlockList.push_front(Cur);1954 else1955 Region->FreeListInfo.BlockList.insert(Prev, Cur);1956 DCHECK_EQ(Cur->Next, BG);1957 Prev = Cur;1958 }1959 1960 if (Idx != 0) {1961 ScopedLock L(BatchClassRegion->FLLock);1962 pushBatchClassBlocks(BatchClassRegion, Blocks, Idx);1963 if (conditionVariableEnabled())1964 BatchClassRegion->FLLockCV.notifyAll(BatchClassRegion->FLLock);1965 }1966 1967 if (SCUDO_DEBUG) {1968 BatchGroupT *Prev = Region->FreeListInfo.BlockList.front();1969 for (BatchGroupT *Cur = Prev->Next; Cur != nullptr;1970 Prev = Cur, Cur = Cur->Next) {1971 CHECK_LT(Prev->CompactPtrGroupBase, Cur->CompactPtrGroupBase);1972 }1973 }1974 1975 if (conditionVariableEnabled())1976 Region->FLLockCV.notifyAll(Region->FLLock);1977}1978} // namespace scudo1979 1980#endif // SCUDO_PRIMARY64_H_1981