1281 lines · c
1//===-- primary32.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_PRIMARY32_H_10#define SCUDO_PRIMARY32_H_11 12#include "allocator_common.h"13#include "bytemap.h"14#include "common.h"15#include "list.h"16#include "options.h"17#include "release.h"18#include "report.h"19#include "size_class_allocator.h"20#include "stats.h"21#include "string_utils.h"22#include "thread_annotations.h"23#include "tracing.h"24 25namespace scudo {26 27// SizeClassAllocator32 is an allocator for 32 or 64-bit address space.28//29// It maps Regions of 2^RegionSizeLog bytes aligned on a 2^RegionSizeLog bytes30// boundary, and keeps a bytemap of the mappable address space to track the size31// class they are associated with.32//33// Mapped regions are split into equally sized Blocks according to the size34// class they belong to, and the associated pointers are shuffled to prevent any35// predictable address pattern (the predictability increases with the block36// size).37//38// Regions for size class 0 are special and used to hold Batches, which39// allow to transfer arrays of pointers from the global size class freelist to40// the thread specific freelist for said class, and back.41//42// Memory used by this allocator is never unmapped but can be partially43// reclaimed if the platform allows for it.44 45template <typename Config> class SizeClassAllocator32 {46public:47 typedef typename Config::CompactPtrT CompactPtrT;48 typedef typename Config::SizeClassMap SizeClassMap;49 static const uptr GroupSizeLog = Config::getGroupSizeLog();50 // The bytemap can only track UINT8_MAX - 1 classes.51 static_assert(SizeClassMap::LargestClassId <= (UINT8_MAX - 1), "");52 // Regions should be large enough to hold the largest Block.53 static_assert((1UL << Config::getRegionSizeLog()) >= SizeClassMap::MaxSize,54 "");55 typedef SizeClassAllocator32<Config> ThisT;56 using SizeClassAllocatorT =57 typename Conditional<Config::getEnableBlockCache(),58 SizeClassAllocatorLocalCache<ThisT>,59 SizeClassAllocatorNoCache<ThisT>>::type;60 typedef Batch<ThisT> BatchT;61 typedef BatchGroup<ThisT> BatchGroupT;62 static const u16 MaxNumBlocksInBatch = SizeClassMap::MaxNumCachedHint;63 64 static constexpr uptr getSizeOfBatchClass() {65 const uptr HeaderSize = sizeof(BatchT);66 return HeaderSize + sizeof(CompactPtrT) * MaxNumBlocksInBatch;67 }68 69 static_assert(sizeof(BatchGroupT) <= getSizeOfBatchClass(),70 "BatchGroupT also uses BatchClass");71 72 static uptr getSizeByClassId(uptr ClassId) {73 return (ClassId == SizeClassMap::BatchClassId)74 ? getSizeOfBatchClass()75 : SizeClassMap::getSizeByClassId(ClassId);76 }77 78 static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }79 80 void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS;81 82 void unmapTestOnly();83 84 // When all blocks are freed, it has to be the same size as `AllocatedUser`.85 void verifyAllBlocksAreReleasedTestOnly();86 87 CompactPtrT compactPtr(UNUSED uptr ClassId, uptr Ptr) const {88 return static_cast<CompactPtrT>(Ptr);89 }90 void *decompactPtr(UNUSED uptr ClassId, CompactPtrT CompactPtr) const {91 return reinterpret_cast<void *>(static_cast<uptr>(CompactPtr));92 }93 uptr compactPtrGroupBase(CompactPtrT CompactPtr) {94 const uptr Mask = (static_cast<uptr>(1) << GroupSizeLog) - 1;95 return CompactPtr & ~Mask;96 }97 uptr decompactGroupBase(uptr CompactPtrGroupBase) {98 return CompactPtrGroupBase;99 }100 ALWAYS_INLINE bool isSmallBlock(uptr BlockSize) {101 const uptr PageSize = getPageSizeCached();102 return BlockSize < PageSize / 16U;103 }104 ALWAYS_INLINE bool isLargeBlock(uptr BlockSize) {105 const uptr PageSize = getPageSizeCached();106 return BlockSize > PageSize;107 }108 109 u16 popBlocks(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,110 CompactPtrT *ToArray, const u16 MaxBlockCount);111 112 // Push the array of free blocks to the designated batch group.113 void pushBlocks(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,114 CompactPtrT *Array, u32 Size);115 116 void disable() NO_THREAD_SAFETY_ANALYSIS;117 void enable() NO_THREAD_SAFETY_ANALYSIS;118 119 template <typename F> void iterateOverBlocks(F Callback);120 121 void getStats(ScopedString *Str);122 void getFragmentationInfo(ScopedString *Str);123 void getMemoryGroupFragmentationInfo(ScopedString *Str) {124 // Each region is also a memory group because region size is the same as125 // group size.126 getFragmentationInfo(Str);127 }128 129 bool setOption(Option O, sptr Value);130 131 uptr tryReleaseToOS(uptr ClassId, ReleaseToOS ReleaseType);132 uptr releaseToOS(ReleaseToOS ReleaseType);133 134 const char *getRegionInfoArrayAddress() const { return nullptr; }135 static uptr getRegionInfoArraySize() { return 0; }136 137 // Not supported in SizeClassAllocator32.138 static BlockInfo findNearestBlock(UNUSED const char *RegionInfoData,139 UNUSED uptr Ptr) {140 return {};141 }142 143 AtomicOptions Options;144 145private:146 static const uptr NumClasses = SizeClassMap::NumClasses;147 static const uptr RegionSize = 1UL << Config::getRegionSizeLog();148 static const uptr NumRegions = SCUDO_MMAP_RANGE_SIZE >>149 Config::getRegionSizeLog();150 static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U;151 typedef FlatByteMap<NumRegions> ByteMap;152 153 struct ReleaseToOsInfo {154 uptr BytesInFreeListAtLastCheckpoint;155 uptr NumReleasesAttempted;156 uptr LastReleasedBytes;157 u64 LastReleaseAtNs;158 };159 160 struct BlocksInfo {161 SinglyLinkedList<BatchGroupT> BlockList = {};162 uptr PoppedBlocks = 0;163 uptr PushedBlocks = 0;164 };165 166 struct alignas(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {167 HybridMutex Mutex;168 BlocksInfo FreeListInfo GUARDED_BY(Mutex);169 uptr CurrentRegion GUARDED_BY(Mutex);170 uptr CurrentRegionAllocated GUARDED_BY(Mutex);171 u32 RandState;172 uptr AllocatedUser GUARDED_BY(Mutex);173 // Lowest & highest region index allocated for this size class, to avoid174 // looping through the whole NumRegions.175 uptr MinRegionIndex GUARDED_BY(Mutex);176 uptr MaxRegionIndex GUARDED_BY(Mutex);177 ReleaseToOsInfo ReleaseInfo GUARDED_BY(Mutex);178 };179 static_assert(sizeof(SizeClassInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");180 181 uptr computeRegionId(uptr Mem) {182 const uptr Id = Mem >> Config::getRegionSizeLog();183 CHECK_LT(Id, NumRegions);184 return Id;185 }186 187 uptr allocateRegion(SizeClassInfo *Sci, uptr ClassId) REQUIRES(Sci->Mutex);188 uptr allocateRegionSlow();189 190 SizeClassInfo *getSizeClassInfo(uptr ClassId) {191 DCHECK_LT(ClassId, NumClasses);192 return &SizeClassInfoArray[ClassId];193 }194 195 void pushBatchClassBlocks(SizeClassInfo *Sci, CompactPtrT *Array, u32 Size)196 REQUIRES(Sci->Mutex);197 198 void pushBlocksImpl(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,199 SizeClassInfo *Sci, CompactPtrT *Array, u32 Size,200 bool SameGroup = false) REQUIRES(Sci->Mutex);201 u16 popBlocksImpl(SizeClassAllocatorT *SizeClassAllocator, uptr ClassId,202 SizeClassInfo *Sci, CompactPtrT *ToArray,203 const u16 MaxBlockCount) REQUIRES(Sci->Mutex);204 NOINLINE bool populateFreeList(SizeClassAllocatorT *SizeClassAllocator,205 uptr ClassId, SizeClassInfo *Sci)206 REQUIRES(Sci->Mutex);207 208 void getStats(ScopedString *Str, uptr ClassId, SizeClassInfo *Sci)209 REQUIRES(Sci->Mutex);210 void getSizeClassFragmentationInfo(SizeClassInfo *Sci, uptr ClassId,211 ScopedString *Str) REQUIRES(Sci->Mutex);212 213 NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,214 ReleaseToOS ReleaseType = ReleaseToOS::Normal)215 REQUIRES(Sci->Mutex);216 bool hasChanceToReleasePages(SizeClassInfo *Sci, uptr BlockSize,217 uptr BytesInFreeList, ReleaseToOS ReleaseType)218 REQUIRES(Sci->Mutex);219 PageReleaseContext markFreeBlocks(SizeClassInfo *Sci, const uptr ClassId,220 const uptr BlockSize, const uptr Base,221 const uptr NumberOfRegions,222 ReleaseToOS ReleaseType)223 REQUIRES(Sci->Mutex);224 225 SizeClassInfo SizeClassInfoArray[NumClasses] = {};226 HybridMutex ByteMapMutex;227 // Track the regions in use, 0 is unused, otherwise store ClassId + 1.228 ByteMap PossibleRegions GUARDED_BY(ByteMapMutex) = {};229 atomic_s32 ReleaseToOsIntervalMs = {};230 // Unless several threads request regions simultaneously from different size231 // classes, the stash rarely contains more than 1 entry.232 static constexpr uptr MaxStashedRegions = 4;233 HybridMutex RegionsStashMutex;234 uptr NumberOfStashedRegions GUARDED_BY(RegionsStashMutex) = 0;235 uptr RegionsStash[MaxStashedRegions] GUARDED_BY(RegionsStashMutex) = {};236};237 238template <typename Config>239void SizeClassAllocator32<Config>::init(s32 ReleaseToOsInterval)240 NO_THREAD_SAFETY_ANALYSIS {241 if (SCUDO_FUCHSIA)242 reportError("SizeClassAllocator32 is not supported on Fuchsia");243 244 if (SCUDO_TRUSTY)245 reportError("SizeClassAllocator32 is not supported on Trusty");246 247 DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));248 PossibleRegions.init();249 u32 Seed;250 const u64 Time = getMonotonicTimeFast();251 if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed)))252 Seed = static_cast<u32>(Time ^253 (reinterpret_cast<uptr>(SizeClassInfoArray) >> 6));254 for (uptr I = 0; I < NumClasses; I++) {255 SizeClassInfo *Sci = getSizeClassInfo(I);256 Sci->RandState = getRandomU32(&Seed);257 // Sci->MaxRegionIndex is already initialized to 0.258 Sci->MinRegionIndex = NumRegions;259 Sci->ReleaseInfo.LastReleaseAtNs = Time;260 }261 262 // The default value in the primary config has the higher priority.263 if (Config::getDefaultReleaseToOsIntervalMs() != INT32_MIN)264 ReleaseToOsInterval = Config::getDefaultReleaseToOsIntervalMs();265 setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval));266}267 268template <typename Config> void SizeClassAllocator32<Config>::unmapTestOnly() {269 {270 ScopedLock L(RegionsStashMutex);271 while (NumberOfStashedRegions > 0) {272 unmap(reinterpret_cast<void *>(RegionsStash[--NumberOfStashedRegions]),273 RegionSize);274 }275 }276 277 uptr MinRegionIndex = NumRegions, MaxRegionIndex = 0;278 for (uptr I = 0; I < NumClasses; I++) {279 SizeClassInfo *Sci = getSizeClassInfo(I);280 ScopedLock L(Sci->Mutex);281 if (Sci->MinRegionIndex < MinRegionIndex)282 MinRegionIndex = Sci->MinRegionIndex;283 if (Sci->MaxRegionIndex > MaxRegionIndex)284 MaxRegionIndex = Sci->MaxRegionIndex;285 *Sci = {};286 }287 288 ScopedLock L(ByteMapMutex);289 for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++)290 if (PossibleRegions[I])291 unmap(reinterpret_cast<void *>(I * RegionSize), RegionSize);292 PossibleRegions.unmapTestOnly();293}294 295template <typename Config>296void SizeClassAllocator32<Config>::verifyAllBlocksAreReleasedTestOnly() {297 // `BatchGroup` and `Batch` also use the blocks from BatchClass.298 uptr BatchClassUsedInFreeLists = 0;299 for (uptr I = 0; I < NumClasses; I++) {300 // We have to count BatchClassUsedInFreeLists in other regions first.301 if (I == SizeClassMap::BatchClassId)302 continue;303 SizeClassInfo *Sci = getSizeClassInfo(I);304 ScopedLock L1(Sci->Mutex);305 uptr TotalBlocks = 0;306 for (BatchGroupT &BG : Sci->FreeListInfo.BlockList) {307 // `BG::Batches` are `Batches`. +1 for `BatchGroup`.308 BatchClassUsedInFreeLists += BG.Batches.size() + 1;309 for (const auto &It : BG.Batches)310 TotalBlocks += It.getCount();311 }312 313 const uptr BlockSize = getSizeByClassId(I);314 DCHECK_EQ(TotalBlocks, Sci->AllocatedUser / BlockSize);315 DCHECK_EQ(Sci->FreeListInfo.PushedBlocks, Sci->FreeListInfo.PoppedBlocks);316 }317 318 SizeClassInfo *Sci = getSizeClassInfo(SizeClassMap::BatchClassId);319 ScopedLock L1(Sci->Mutex);320 uptr TotalBlocks = 0;321 for (BatchGroupT &BG : Sci->FreeListInfo.BlockList) {322 if (LIKELY(!BG.Batches.empty())) {323 for (const auto &It : BG.Batches)324 TotalBlocks += It.getCount();325 } else {326 // `BatchGroup` with empty freelist doesn't have `Batch` record327 // itself.328 ++TotalBlocks;329 }330 }331 332 const uptr BlockSize = getSizeByClassId(SizeClassMap::BatchClassId);333 DCHECK_EQ(TotalBlocks + BatchClassUsedInFreeLists,334 Sci->AllocatedUser / BlockSize);335 const uptr BlocksInUse =336 Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks;337 DCHECK_EQ(BlocksInUse, BatchClassUsedInFreeLists);338}339 340template <typename Config>341u16 SizeClassAllocator32<Config>::popBlocks(342 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, CompactPtrT *ToArray,343 const u16 MaxBlockCount) {344 DCHECK_LT(ClassId, NumClasses);345 SizeClassInfo *Sci = getSizeClassInfo(ClassId);346 ScopedLock L(Sci->Mutex);347 348 u16 PopCount =349 popBlocksImpl(SizeClassAllocator, ClassId, Sci, ToArray, MaxBlockCount);350 if (UNLIKELY(PopCount == 0)) {351 if (UNLIKELY(!populateFreeList(SizeClassAllocator, ClassId, Sci)))352 return 0U;353 PopCount =354 popBlocksImpl(SizeClassAllocator, ClassId, Sci, ToArray, MaxBlockCount);355 DCHECK_NE(PopCount, 0U);356 }357 358 return PopCount;359}360 361template <typename Config>362void SizeClassAllocator32<Config>::pushBlocks(363 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, CompactPtrT *Array,364 u32 Size) {365 DCHECK_LT(ClassId, NumClasses);366 DCHECK_GT(Size, 0);367 368 SizeClassInfo *Sci = getSizeClassInfo(ClassId);369 if (ClassId == SizeClassMap::BatchClassId) {370 ScopedLock L(Sci->Mutex);371 pushBatchClassBlocks(Sci, Array, Size);372 return;373 }374 375 // TODO(chiahungduan): Consider not doing grouping if the group size is not376 // greater than the block size with a certain scale.377 378 // Sort the blocks so that blocks belonging to the same group can be pushed379 // together.380 bool SameGroup = true;381 for (u32 I = 1; I < Size; ++I) {382 if (compactPtrGroupBase(Array[I - 1]) != compactPtrGroupBase(Array[I]))383 SameGroup = false;384 CompactPtrT Cur = Array[I];385 u32 J = I;386 while (J > 0 &&387 compactPtrGroupBase(Cur) < compactPtrGroupBase(Array[J - 1])) {388 Array[J] = Array[J - 1];389 --J;390 }391 Array[J] = Cur;392 }393 394 ScopedLock L(Sci->Mutex);395 pushBlocksImpl(SizeClassAllocator, ClassId, Sci, Array, Size, SameGroup);396}397 398template <typename Config>399void SizeClassAllocator32<Config>::disable() NO_THREAD_SAFETY_ANALYSIS {400 // The BatchClassId must be locked last since other classes can use it.401 for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {402 if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)403 continue;404 getSizeClassInfo(static_cast<uptr>(I))->Mutex.lock();405 }406 getSizeClassInfo(SizeClassMap::BatchClassId)->Mutex.lock();407 RegionsStashMutex.lock();408 ByteMapMutex.lock();409}410 411template <typename Config>412void SizeClassAllocator32<Config>::enable() NO_THREAD_SAFETY_ANALYSIS {413 ByteMapMutex.unlock();414 RegionsStashMutex.unlock();415 getSizeClassInfo(SizeClassMap::BatchClassId)->Mutex.unlock();416 for (uptr I = 0; I < NumClasses; I++) {417 if (I == SizeClassMap::BatchClassId)418 continue;419 getSizeClassInfo(I)->Mutex.unlock();420 }421}422 423template <typename Config>424template <typename F>425void SizeClassAllocator32<Config>::iterateOverBlocks(F Callback) {426 uptr MinRegionIndex = NumRegions, MaxRegionIndex = 0;427 for (uptr I = 0; I < NumClasses; I++) {428 SizeClassInfo *Sci = getSizeClassInfo(I);429 // TODO: The call of `iterateOverBlocks` requires disabling430 // SizeClassAllocator32. We may consider locking each region on demand431 // only.432 Sci->Mutex.assertHeld();433 if (Sci->MinRegionIndex < MinRegionIndex)434 MinRegionIndex = Sci->MinRegionIndex;435 if (Sci->MaxRegionIndex > MaxRegionIndex)436 MaxRegionIndex = Sci->MaxRegionIndex;437 }438 439 // SizeClassAllocator32 is disabled, i.e., ByteMapMutex is held.440 ByteMapMutex.assertHeld();441 442 for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {443 if (PossibleRegions[I] &&444 (PossibleRegions[I] - 1U) != SizeClassMap::BatchClassId) {445 const uptr BlockSize = getSizeByClassId(PossibleRegions[I] - 1U);446 const uptr From = I * RegionSize;447 const uptr To = From + (RegionSize / BlockSize) * BlockSize;448 for (uptr Block = From; Block < To; Block += BlockSize)449 Callback(Block);450 }451 }452}453 454template <typename Config>455void SizeClassAllocator32<Config>::getStats(ScopedString *Str) {456 // TODO(kostyak): get the RSS per region.457 uptr TotalMapped = 0;458 uptr PoppedBlocks = 0;459 uptr PushedBlocks = 0;460 for (uptr I = 0; I < NumClasses; I++) {461 SizeClassInfo *Sci = getSizeClassInfo(I);462 ScopedLock L(Sci->Mutex);463 TotalMapped += Sci->AllocatedUser;464 PoppedBlocks += Sci->FreeListInfo.PoppedBlocks;465 PushedBlocks += Sci->FreeListInfo.PushedBlocks;466 }467 Str->append("Stats: SizeClassAllocator32: %zuM mapped in %zu allocations; "468 "remains %zu\n",469 TotalMapped >> 20, PoppedBlocks, PoppedBlocks - PushedBlocks);470 for (uptr I = 0; I < NumClasses; I++) {471 SizeClassInfo *Sci = getSizeClassInfo(I);472 ScopedLock L(Sci->Mutex);473 getStats(Str, I, Sci);474 }475}476 477template <typename Config>478void SizeClassAllocator32<Config>::getFragmentationInfo(ScopedString *Str) {479 Str->append(480 "Fragmentation Stats: SizeClassAllocator32: page size = %zu bytes\n",481 getPageSizeCached());482 483 for (uptr I = 1; I < NumClasses; I++) {484 SizeClassInfo *Sci = getSizeClassInfo(I);485 ScopedLock L(Sci->Mutex);486 getSizeClassFragmentationInfo(Sci, I, Str);487 }488}489 490template <typename Config>491bool SizeClassAllocator32<Config>::setOption(Option O, sptr Value) {492 if (O == Option::ReleaseInterval) {493 const s32 Interval =494 Max(Min(static_cast<s32>(Value), Config::getMaxReleaseToOsIntervalMs()),495 Config::getMinReleaseToOsIntervalMs());496 atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval);497 return true;498 }499 // Not supported by the Primary, but not an error either.500 return true;501}502 503template <typename Config>504uptr SizeClassAllocator32<Config>::tryReleaseToOS(uptr ClassId,505 ReleaseToOS ReleaseType) {506 SizeClassInfo *Sci = getSizeClassInfo(ClassId);507 // TODO: Once we have separate locks like primary64, we may consider using508 // tryLock() as well.509 ScopedLock L(Sci->Mutex);510 return releaseToOSMaybe(Sci, ClassId, ReleaseType);511}512 513template <typename Config>514uptr SizeClassAllocator32<Config>::releaseToOS(ReleaseToOS ReleaseType) {515 SCUDO_SCOPED_TRACE(GetPrimaryReleaseToOSTraceName(ReleaseType));516 517 uptr TotalReleasedBytes = 0;518 for (uptr I = 0; I < NumClasses; I++) {519 if (I == SizeClassMap::BatchClassId)520 continue;521 SizeClassInfo *Sci = getSizeClassInfo(I);522 ScopedLock L(Sci->Mutex);523 TotalReleasedBytes += releaseToOSMaybe(Sci, I, ReleaseType);524 }525 return TotalReleasedBytes;526}527 528template <typename Config>529uptr SizeClassAllocator32<Config>::allocateRegion(SizeClassInfo *Sci,530 uptr ClassId)531 REQUIRES(Sci->Mutex) {532 DCHECK_LT(ClassId, NumClasses);533 uptr Region = 0;534 {535 ScopedLock L(RegionsStashMutex);536 if (NumberOfStashedRegions > 0)537 Region = RegionsStash[--NumberOfStashedRegions];538 }539 if (!Region)540 Region = allocateRegionSlow();541 if (LIKELY(Region)) {542 // Sci->Mutex is held by the caller, updating the Min/Max is safe.543 const uptr RegionIndex = computeRegionId(Region);544 if (RegionIndex < Sci->MinRegionIndex)545 Sci->MinRegionIndex = RegionIndex;546 if (RegionIndex > Sci->MaxRegionIndex)547 Sci->MaxRegionIndex = RegionIndex;548 ScopedLock L(ByteMapMutex);549 PossibleRegions.set(RegionIndex, static_cast<u8>(ClassId + 1U));550 }551 return Region;552}553 554template <typename Config>555uptr SizeClassAllocator32<Config>::allocateRegionSlow() {556 uptr MapSize = 2 * RegionSize;557 const uptr MapBase = reinterpret_cast<uptr>(558 map(nullptr, MapSize, "scudo:primary", MAP_ALLOWNOMEM));559 if (!MapBase)560 return 0;561 const uptr MapEnd = MapBase + MapSize;562 uptr Region = MapBase;563 if (isAligned(Region, RegionSize)) {564 ScopedLock L(RegionsStashMutex);565 if (NumberOfStashedRegions < MaxStashedRegions)566 RegionsStash[NumberOfStashedRegions++] = MapBase + RegionSize;567 else568 MapSize = RegionSize;569 } else {570 Region = roundUp(MapBase, RegionSize);571 unmap(reinterpret_cast<void *>(MapBase), Region - MapBase);572 MapSize = RegionSize;573 }574 const uptr End = Region + MapSize;575 if (End != MapEnd)576 unmap(reinterpret_cast<void *>(End), MapEnd - End);577 578 DCHECK_EQ(Region % RegionSize, 0U);579 static_assert(Config::getRegionSizeLog() == GroupSizeLog,580 "Memory group should be the same size as Region");581 582 return Region;583}584 585template <typename Config>586void SizeClassAllocator32<Config>::pushBatchClassBlocks(SizeClassInfo *Sci,587 CompactPtrT *Array,588 u32 Size)589 REQUIRES(Sci->Mutex) {590 DCHECK_EQ(Sci, getSizeClassInfo(SizeClassMap::BatchClassId));591 592 // Free blocks are recorded by Batch in freelist for all593 // size-classes. In addition, Batch is allocated from BatchClassId.594 // In order not to use additional block to record the free blocks in595 // BatchClassId, they are self-contained. I.e., A Batch records the596 // block address of itself. See the figure below:597 //598 // Batch at 0xABCD599 // +----------------------------+600 // | Free blocks' addr |601 // | +------+------+------+ |602 // | |0xABCD|... |... | |603 // | +------+------+------+ |604 // +----------------------------+605 //606 // When we allocate all the free blocks in the Batch, the block used607 // by Batch is also free for use. We don't need to recycle the608 // Batch. Note that the correctness is maintained by the invariant,609 //610 // Each popBlocks() request returns the entire Batch. Returning611 // part of the blocks in a Batch is invalid.612 //613 // This ensures that Batch won't leak the address itself while it's614 // still holding other valid data.615 //616 // Besides, BatchGroup is also allocated from BatchClassId and has its617 // address recorded in the Batch too. To maintain the correctness,618 //619 // The address of BatchGroup is always recorded in the last Batch620 // in the freelist (also imply that the freelist should only be621 // updated with push_front). Once the last Batch is popped,622 // the block used by BatchGroup is also free for use.623 //624 // With this approach, the blocks used by BatchGroup and Batch are625 // reusable and don't need additional space for them.626 627 Sci->FreeListInfo.PushedBlocks += Size;628 BatchGroupT *BG = Sci->FreeListInfo.BlockList.front();629 630 if (BG == nullptr) {631 // Construct `BatchGroup` on the last element.632 BG = reinterpret_cast<BatchGroupT *>(633 decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1]));634 --Size;635 BG->Batches.clear();636 // BatchClass hasn't enabled memory group. Use `0` to indicate there's no637 // memory group here.638 BG->CompactPtrGroupBase = 0;639 BG->BytesInBGAtLastCheckpoint = 0;640 BG->MaxCachedPerBatch = SizeClassAllocatorT::getMaxCached(641 getSizeByClassId(SizeClassMap::BatchClassId));642 643 Sci->FreeListInfo.BlockList.push_front(BG);644 }645 646 if (UNLIKELY(Size == 0))647 return;648 649 // This happens under 2 cases.650 // 1. just allocated a new `BatchGroup`.651 // 2. Only 1 block is pushed when the freelist is empty.652 if (BG->Batches.empty()) {653 // Construct the `Batch` on the last element.654 BatchT *TB = reinterpret_cast<BatchT *>(655 decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1]));656 TB->clear();657 // As mentioned above, addresses of `Batch` and `BatchGroup` are658 // recorded in the Batch.659 TB->add(Array[Size - 1]);660 TB->add(compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(BG)));661 --Size;662 BG->Batches.push_front(TB);663 }664 665 BatchT *CurBatch = BG->Batches.front();666 DCHECK_NE(CurBatch, nullptr);667 668 for (u32 I = 0; I < Size;) {669 u16 UnusedSlots =670 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount());671 if (UnusedSlots == 0) {672 CurBatch = reinterpret_cast<BatchT *>(673 decompactPtr(SizeClassMap::BatchClassId, Array[I]));674 CurBatch->clear();675 // Self-contained676 CurBatch->add(Array[I]);677 ++I;678 // TODO(chiahungduan): Avoid the use of push_back() in `Batches` of679 // BatchClassId.680 BG->Batches.push_front(CurBatch);681 UnusedSlots = static_cast<u16>(BG->MaxCachedPerBatch - 1);682 }683 // `UnusedSlots` is u16 so the result will be also fit in u16.684 const u16 AppendSize = static_cast<u16>(Min<u32>(UnusedSlots, Size - I));685 CurBatch->appendFromArray(&Array[I], AppendSize);686 I += AppendSize;687 }688}689 690// Push the blocks to their batch group. The layout will be like,691//692// FreeListInfo.BlockList - > BG -> BG -> BG693// | | |694// v v v695// TB TB TB696// |697// v698// TB699//700// Each BlockGroup(BG) will associate with unique group id and the free blocks701// are managed by a list of Batch(TB). To reduce the time of inserting blocks,702// BGs are sorted and the input `Array` are supposed to be sorted so that we can703// get better performance of maintaining sorted property. Use `SameGroup=true`704// to indicate that all blocks in the array are from the same group then we will705// skip checking the group id of each block.706//707// The region mutex needs to be held while calling this method.708template <typename Config>709void SizeClassAllocator32<Config>::pushBlocksImpl(710 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, SizeClassInfo *Sci,711 CompactPtrT *Array, u32 Size, bool SameGroup) REQUIRES(Sci->Mutex) {712 DCHECK_NE(ClassId, SizeClassMap::BatchClassId);713 DCHECK_GT(Size, 0U);714 715 auto CreateGroup = [&](uptr CompactPtrGroupBase) {716 BatchGroupT *BG = reinterpret_cast<BatchGroupT *>(717 SizeClassAllocator->getBatchClassBlock());718 BG->Batches.clear();719 BatchT *TB =720 reinterpret_cast<BatchT *>(SizeClassAllocator->getBatchClassBlock());721 TB->clear();722 723 BG->CompactPtrGroupBase = CompactPtrGroupBase;724 BG->Batches.push_front(TB);725 BG->BytesInBGAtLastCheckpoint = 0;726 BG->MaxCachedPerBatch = MaxNumBlocksInBatch;727 728 return BG;729 };730 731 auto InsertBlocks = [&](BatchGroupT *BG, CompactPtrT *Array, u32 Size) {732 SinglyLinkedList<BatchT> &Batches = BG->Batches;733 BatchT *CurBatch = Batches.front();734 DCHECK_NE(CurBatch, nullptr);735 736 for (u32 I = 0; I < Size;) {737 DCHECK_GE(BG->MaxCachedPerBatch, CurBatch->getCount());738 u16 UnusedSlots =739 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount());740 if (UnusedSlots == 0) {741 CurBatch = reinterpret_cast<BatchT *>(742 SizeClassAllocator->getBatchClassBlock());743 CurBatch->clear();744 Batches.push_front(CurBatch);745 UnusedSlots = BG->MaxCachedPerBatch;746 }747 // `UnusedSlots` is u16 so the result will be also fit in u16.748 u16 AppendSize = static_cast<u16>(Min<u32>(UnusedSlots, Size - I));749 CurBatch->appendFromArray(&Array[I], AppendSize);750 I += AppendSize;751 }752 };753 754 Sci->FreeListInfo.PushedBlocks += Size;755 BatchGroupT *Cur = Sci->FreeListInfo.BlockList.front();756 757 // In the following, `Cur` always points to the BatchGroup for blocks that758 // will be pushed next. `Prev` is the element right before `Cur`.759 BatchGroupT *Prev = nullptr;760 761 while (Cur != nullptr &&762 compactPtrGroupBase(Array[0]) > Cur->CompactPtrGroupBase) {763 Prev = Cur;764 Cur = Cur->Next;765 }766 767 if (Cur == nullptr ||768 compactPtrGroupBase(Array[0]) != Cur->CompactPtrGroupBase) {769 Cur = CreateGroup(compactPtrGroupBase(Array[0]));770 if (Prev == nullptr)771 Sci->FreeListInfo.BlockList.push_front(Cur);772 else773 Sci->FreeListInfo.BlockList.insert(Prev, Cur);774 }775 776 // All the blocks are from the same group, just push without checking group777 // id.778 if (SameGroup) {779 for (u32 I = 0; I < Size; ++I)780 DCHECK_EQ(compactPtrGroupBase(Array[I]), Cur->CompactPtrGroupBase);781 782 InsertBlocks(Cur, Array, Size);783 return;784 }785 786 // The blocks are sorted by group id. Determine the segment of group and787 // push them to their group together.788 u32 Count = 1;789 for (u32 I = 1; I < Size; ++I) {790 if (compactPtrGroupBase(Array[I - 1]) != compactPtrGroupBase(Array[I])) {791 DCHECK_EQ(compactPtrGroupBase(Array[I - 1]), Cur->CompactPtrGroupBase);792 InsertBlocks(Cur, Array + I - Count, Count);793 794 while (Cur != nullptr &&795 compactPtrGroupBase(Array[I]) > Cur->CompactPtrGroupBase) {796 Prev = Cur;797 Cur = Cur->Next;798 }799 800 if (Cur == nullptr ||801 compactPtrGroupBase(Array[I]) != Cur->CompactPtrGroupBase) {802 Cur = CreateGroup(compactPtrGroupBase(Array[I]));803 DCHECK_NE(Prev, nullptr);804 Sci->FreeListInfo.BlockList.insert(Prev, Cur);805 }806 807 Count = 1;808 } else {809 ++Count;810 }811 }812 813 InsertBlocks(Cur, Array + Size - Count, Count);814}815 816template <typename Config>817u16 SizeClassAllocator32<Config>::popBlocksImpl(818 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, SizeClassInfo *Sci,819 CompactPtrT *ToArray, const u16 MaxBlockCount) REQUIRES(Sci->Mutex) {820 if (Sci->FreeListInfo.BlockList.empty())821 return 0U;822 823 SinglyLinkedList<BatchT> &Batches =824 Sci->FreeListInfo.BlockList.front()->Batches;825 826 if (Batches.empty()) {827 DCHECK_EQ(ClassId, SizeClassMap::BatchClassId);828 BatchGroupT *BG = Sci->FreeListInfo.BlockList.front();829 Sci->FreeListInfo.BlockList.pop_front();830 831 // Block used by `BatchGroup` is from BatchClassId. Turn the block into832 // `Batch` with single block.833 BatchT *TB = reinterpret_cast<BatchT *>(BG);834 ToArray[0] =835 compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(TB));836 Sci->FreeListInfo.PoppedBlocks += 1;837 return 1U;838 }839 840 // So far, instead of always filling the blocks to `MaxBlockCount`, we only841 // examine single `Batch` to minimize the time spent on the primary842 // allocator. Besides, the sizes of `Batch` and843 // `SizeClassAllocatorT::getMaxCached()` may also impact the time spent on844 // accessing the primary allocator.845 // TODO(chiahungduan): Evaluate if we want to always prepare `MaxBlockCount`846 // blocks and/or adjust the size of `Batch` according to847 // `SizeClassAllocatorT::getMaxCached()`.848 BatchT *B = Batches.front();849 DCHECK_NE(B, nullptr);850 DCHECK_GT(B->getCount(), 0U);851 852 // BachClassId should always take all blocks in the Batch. Read the853 // comment in `pushBatchClassBlocks()` for more details.854 const u16 PopCount = ClassId == SizeClassMap::BatchClassId855 ? B->getCount()856 : Min(MaxBlockCount, B->getCount());857 B->moveNToArray(ToArray, PopCount);858 859 // TODO(chiahungduan): The deallocation of unused BatchClassId blocks can be860 // done without holding `Mutex`.861 if (B->empty()) {862 Batches.pop_front();863 // `Batch` of BatchClassId is self-contained, no need to864 // deallocate. Read the comment in `pushBatchClassBlocks()` for more865 // details.866 if (ClassId != SizeClassMap::BatchClassId)867 SizeClassAllocator->deallocate(SizeClassMap::BatchClassId, B);868 869 if (Batches.empty()) {870 BatchGroupT *BG = Sci->FreeListInfo.BlockList.front();871 Sci->FreeListInfo.BlockList.pop_front();872 873 // We don't keep BatchGroup with zero blocks to avoid empty-checking874 // while allocating. Note that block used for constructing BatchGroup is875 // recorded as free blocks in the last element of BatchGroup::Batches.876 // Which means, once we pop the last Batch, the block is877 // implicitly deallocated.878 if (ClassId != SizeClassMap::BatchClassId)879 SizeClassAllocator->deallocate(SizeClassMap::BatchClassId, BG);880 }881 }882 883 Sci->FreeListInfo.PoppedBlocks += PopCount;884 return PopCount;885}886 887template <typename Config>888bool SizeClassAllocator32<Config>::populateFreeList(889 SizeClassAllocatorT *SizeClassAllocator, uptr ClassId, SizeClassInfo *Sci)890 REQUIRES(Sci->Mutex) {891 uptr Region;892 uptr Offset;893 // If the size-class currently has a region associated to it, use it. The894 // newly created blocks will be located after the currently allocated memory895 // for that region (up to RegionSize). Otherwise, create a new region, where896 // the new blocks will be carved from the beginning.897 if (Sci->CurrentRegion) {898 Region = Sci->CurrentRegion;899 DCHECK_GT(Sci->CurrentRegionAllocated, 0U);900 Offset = Sci->CurrentRegionAllocated;901 } else {902 DCHECK_EQ(Sci->CurrentRegionAllocated, 0U);903 Region = allocateRegion(Sci, ClassId);904 if (UNLIKELY(!Region))905 return false;906 SizeClassAllocator->getStats().add(StatMapped, RegionSize);907 Sci->CurrentRegion = Region;908 Offset = 0;909 }910 911 const uptr Size = getSizeByClassId(ClassId);912 const u16 MaxCount = SizeClassAllocatorT::getMaxCached(Size);913 DCHECK_GT(MaxCount, 0U);914 // The maximum number of blocks we should carve in the region is dictated915 // by the maximum number of batches we want to fill, and the amount of916 // memory left in the current region (we use the lowest of the two). This917 // will not be 0 as we ensure that a region can at least hold one block (via918 // static_assert and at the end of this function).919 const u32 NumberOfBlocks = Min(920 MaxNumBatches * MaxCount, static_cast<u32>((RegionSize - Offset) / Size));921 DCHECK_GT(NumberOfBlocks, 0U);922 923 constexpr u32 ShuffleArraySize = MaxNumBatches * MaxNumBlocksInBatch;924 // Fill the transfer batches and put them in the size-class freelist. We925 // need to randomize the blocks for security purposes, so we first fill a926 // local array that we then shuffle before populating the batches.927 CompactPtrT ShuffleArray[ShuffleArraySize];928 DCHECK_LE(NumberOfBlocks, ShuffleArraySize);929 930 uptr P = Region + Offset;931 for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)932 ShuffleArray[I] = reinterpret_cast<CompactPtrT>(P);933 934 if (ClassId != SizeClassMap::BatchClassId) {935 u32 N = 1;936 uptr CurGroup = compactPtrGroupBase(ShuffleArray[0]);937 for (u32 I = 1; I < NumberOfBlocks; I++) {938 if (UNLIKELY(compactPtrGroupBase(ShuffleArray[I]) != CurGroup)) {939 shuffle(ShuffleArray + I - N, N, &Sci->RandState);940 pushBlocksImpl(SizeClassAllocator, ClassId, Sci, ShuffleArray + I - N,941 N,942 /*SameGroup=*/true);943 N = 1;944 CurGroup = compactPtrGroupBase(ShuffleArray[I]);945 } else {946 ++N;947 }948 }949 950 shuffle(ShuffleArray + NumberOfBlocks - N, N, &Sci->RandState);951 pushBlocksImpl(SizeClassAllocator, ClassId, Sci,952 &ShuffleArray[NumberOfBlocks - N], N,953 /*SameGroup=*/true);954 } else {955 pushBatchClassBlocks(Sci, ShuffleArray, NumberOfBlocks);956 }957 958 // Note that `pushedBlocks` and `poppedBlocks` are supposed to only record959 // the requests from `pushBlocks` and `PopBatch` which are external960 // interfaces. `populateFreeList` is the internal interface so we should set961 // the values back to avoid incorrectly setting the stats.962 Sci->FreeListInfo.PushedBlocks -= NumberOfBlocks;963 964 const uptr AllocatedUser = Size * NumberOfBlocks;965 SizeClassAllocator->getStats().add(StatFree, AllocatedUser);966 DCHECK_LE(Sci->CurrentRegionAllocated + AllocatedUser, RegionSize);967 // If there is not enough room in the region currently associated to fit968 // more blocks, we deassociate the region by resetting CurrentRegion and969 // CurrentRegionAllocated. Otherwise, update the allocated amount.970 if (RegionSize - (Sci->CurrentRegionAllocated + AllocatedUser) < Size) {971 Sci->CurrentRegion = 0;972 Sci->CurrentRegionAllocated = 0;973 } else {974 Sci->CurrentRegionAllocated += AllocatedUser;975 }976 Sci->AllocatedUser += AllocatedUser;977 978 return true;979}980 981template <typename Config>982void SizeClassAllocator32<Config>::getStats(ScopedString *Str, uptr ClassId,983 SizeClassInfo *Sci)984 REQUIRES(Sci->Mutex) {985 if (Sci->AllocatedUser == 0)986 return;987 const uptr BlockSize = getSizeByClassId(ClassId);988 const uptr InUse =989 Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks;990 const uptr BytesInFreeList = Sci->AllocatedUser - InUse * BlockSize;991 uptr PushedBytesDelta = 0;992 if (BytesInFreeList >= Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint) {993 PushedBytesDelta =994 BytesInFreeList - Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint;995 }996 const uptr AvailableChunks = Sci->AllocatedUser / BlockSize;997 Str->append(998 " %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "999 "inuse: %6zu avail: %6zu releases attempted: %6zu last released: %6zuK "1000 "latest pushed bytes: %6zuK\n",1001 ClassId, getSizeByClassId(ClassId), Sci->AllocatedUser >> 10,1002 Sci->FreeListInfo.PoppedBlocks, Sci->FreeListInfo.PushedBlocks, InUse,1003 AvailableChunks, Sci->ReleaseInfo.NumReleasesAttempted,1004 Sci->ReleaseInfo.LastReleasedBytes >> 10, PushedBytesDelta >> 10);1005}1006 1007template <typename Config>1008void SizeClassAllocator32<Config>::getSizeClassFragmentationInfo(1009 SizeClassInfo *Sci, uptr ClassId, ScopedString *Str) REQUIRES(Sci->Mutex) {1010 const uptr BlockSize = getSizeByClassId(ClassId);1011 const uptr First = Sci->MinRegionIndex;1012 const uptr Last = Sci->MaxRegionIndex;1013 const uptr Base = First * RegionSize;1014 const uptr NumberOfRegions = Last - First + 1U;1015 auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {1016 ScopedLock L(ByteMapMutex);1017 return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;1018 };1019 1020 FragmentationRecorder Recorder;1021 if (!Sci->FreeListInfo.BlockList.empty()) {1022 PageReleaseContext Context = markFreeBlocks(1023 Sci, ClassId, BlockSize, Base, NumberOfRegions, ReleaseToOS::ForceAll);1024 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);1025 }1026 1027 const uptr PageSize = getPageSizeCached();1028 const uptr TotalBlocks = Sci->AllocatedUser / BlockSize;1029 const uptr InUseBlocks =1030 Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks;1031 uptr AllocatedPagesCount = 0;1032 if (TotalBlocks != 0U) {1033 for (uptr I = 0; I < NumberOfRegions; ++I) {1034 if (SkipRegion(I))1035 continue;1036 AllocatedPagesCount += RegionSize / PageSize;1037 }1038 1039 DCHECK_NE(AllocatedPagesCount, 0U);1040 }1041 1042 DCHECK_GE(AllocatedPagesCount, Recorder.getReleasedPagesCount());1043 const uptr InUsePages =1044 AllocatedPagesCount - Recorder.getReleasedPagesCount();1045 const uptr InUseBytes = InUsePages * PageSize;1046 1047 uptr Integral;1048 uptr Fractional;1049 computePercentage(BlockSize * InUseBlocks, InUseBytes, &Integral,1050 &Fractional);1051 Str->append(" %02zu (%6zu): inuse/total blocks: %6zu/%6zu inuse/total "1052 "pages: %6zu/%6zu inuse bytes: %6zuK util: %3zu.%02zu%%\n",1053 ClassId, BlockSize, InUseBlocks, TotalBlocks, InUsePages,1054 AllocatedPagesCount, InUseBytes >> 10, Integral, Fractional);1055}1056 1057template <typename Config>1058uptr SizeClassAllocator32<Config>::releaseToOSMaybe(SizeClassInfo *Sci,1059 uptr ClassId,1060 ReleaseToOS ReleaseType)1061 REQUIRES(Sci->Mutex) {1062 const uptr BlockSize = getSizeByClassId(ClassId);1063 1064 DCHECK_GE(Sci->FreeListInfo.PoppedBlocks, Sci->FreeListInfo.PushedBlocks);1065 const uptr BytesInFreeList =1066 Sci->AllocatedUser -1067 (Sci->FreeListInfo.PoppedBlocks - Sci->FreeListInfo.PushedBlocks) *1068 BlockSize;1069 1070 if (UNLIKELY(BytesInFreeList == 0))1071 return 0;1072 1073 // ====================================================================== //1074 // 1. Check if we have enough free blocks and if it's worth doing a page1075 // release.1076 // ====================================================================== //1077 if (ReleaseType != ReleaseToOS::ForceAll &&1078 !hasChanceToReleasePages(Sci, BlockSize, BytesInFreeList, ReleaseType)) {1079 return 0;1080 }1081 1082 const uptr First = Sci->MinRegionIndex;1083 const uptr Last = Sci->MaxRegionIndex;1084 DCHECK_NE(Last, 0U);1085 DCHECK_LE(First, Last);1086 uptr TotalReleasedBytes = 0;1087 const uptr Base = First * RegionSize;1088 const uptr NumberOfRegions = Last - First + 1U;1089 1090 // The following steps contribute to the majority time spent in page1091 // releasing thus we increment the counter here.1092 ++Sci->ReleaseInfo.NumReleasesAttempted;1093 1094 // ==================================================================== //1095 // 2. Mark the free blocks and we can tell which pages are in-use by1096 // querying `PageReleaseContext`.1097 // ==================================================================== //1098 1099 // Only add trace point after the quick returns have occurred to avoid1100 // incurring performance penalties. Most of the time in this function1101 // will be the mark free blocks call and the actual release to OS call.1102 SCUDO_SCOPED_TRACE(GetPrimaryReleaseToOSMaybeTraceName(ReleaseType));1103 1104 PageReleaseContext Context = markFreeBlocks(Sci, ClassId, BlockSize, Base,1105 NumberOfRegions, ReleaseType);1106 if (!Context.hasBlockMarked())1107 return 0;1108 1109 // ==================================================================== //1110 // 3. Release the unused physical pages back to the OS.1111 // ==================================================================== //1112 ReleaseRecorder Recorder(Base);1113 auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {1114 ScopedLock L(ByteMapMutex);1115 return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;1116 };1117 releaseFreeMemoryToOS(Context, Recorder, SkipRegion);1118 1119 if (Recorder.getReleasedBytes() > 0) {1120 Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;1121 Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();1122 TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;1123 }1124 Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast();1125 1126 return TotalReleasedBytes;1127}1128 1129template <typename Config>1130bool SizeClassAllocator32<Config>::hasChanceToReleasePages(1131 SizeClassInfo *Sci, uptr BlockSize, uptr BytesInFreeList,1132 ReleaseToOS ReleaseType) REQUIRES(Sci->Mutex) {1133 DCHECK_GE(Sci->FreeListInfo.PoppedBlocks, Sci->FreeListInfo.PushedBlocks);1134 const uptr PageSize = getPageSizeCached();1135 1136 if (BytesInFreeList <= Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint)1137 Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;1138 1139 // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value1140 // so that we won't underestimate the releasable pages. For example, the1141 // following is the region usage,1142 //1143 // BytesInFreeListAtLastCheckpoint AllocatedUser1144 // v v1145 // |--------------------------------------->1146 // ^ ^1147 // BytesInFreeList ReleaseThreshold1148 //1149 // In general, if we have collected enough bytes and the amount of free1150 // bytes meets the ReleaseThreshold, we will try to do page release. If we1151 // don't update `BytesInFreeListAtLastCheckpoint` when the current1152 // `BytesInFreeList` is smaller, we may take longer time to wait for enough1153 // freed blocks because we miss the bytes between1154 // (BytesInFreeListAtLastCheckpoint - BytesInFreeList).1155 const uptr PushedBytesDelta =1156 BytesInFreeList - Sci->ReleaseInfo.BytesInFreeListAtLastCheckpoint;1157 if (PushedBytesDelta < PageSize)1158 return false;1159 1160 // Releasing smaller blocks is expensive, so we want to make sure that a1161 // significant amount of bytes are free, and that there has been a good1162 // amount of batches pushed to the freelist before attempting to release.1163 if (isSmallBlock(BlockSize) && ReleaseType == ReleaseToOS::Normal)1164 if (PushedBytesDelta < Sci->AllocatedUser / 16U)1165 return false;1166 1167 if (ReleaseType == ReleaseToOS::Normal) {1168 const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs);1169 if (IntervalMs < 0)1170 return false;1171 1172 // The constant 8 here is selected from profiling some apps and the number1173 // of unreleased pages in the large size classes is around 16 pages or1174 // more. Choose half of it as a heuristic and which also avoids page1175 // release every time for every pushBlocks() attempt by large blocks.1176 const bool ByPassReleaseInterval =1177 isLargeBlock(BlockSize) && PushedBytesDelta > 8 * PageSize;1178 if (!ByPassReleaseInterval) {1179 if (Sci->ReleaseInfo.LastReleaseAtNs +1180 static_cast<u64>(IntervalMs) * 1000000 >1181 getMonotonicTimeFast()) {1182 // Memory was returned recently.1183 return false;1184 }1185 }1186 } // if (ReleaseType == ReleaseToOS::Normal)1187 1188 return true;1189}1190 1191template <typename Config>1192PageReleaseContext SizeClassAllocator32<Config>::markFreeBlocks(1193 SizeClassInfo *Sci, const uptr ClassId, const uptr BlockSize,1194 const uptr Base, const uptr NumberOfRegions, ReleaseToOS ReleaseType)1195 REQUIRES(Sci->Mutex) {1196 const uptr PageSize = getPageSizeCached();1197 const uptr GroupSize = (1UL << GroupSizeLog);1198 const uptr CurGroupBase =1199 compactPtrGroupBase(compactPtr(ClassId, Sci->CurrentRegion));1200 1201 PageReleaseContext Context(BlockSize, NumberOfRegions,1202 /*ReleaseSize=*/RegionSize);1203 1204 auto DecompactPtr = [](CompactPtrT CompactPtr) {1205 return reinterpret_cast<uptr>(CompactPtr);1206 };1207 for (BatchGroupT &BG : Sci->FreeListInfo.BlockList) {1208 const uptr GroupBase = decompactGroupBase(BG.CompactPtrGroupBase);1209 // The `GroupSize` may not be divided by `BlockSize`, which means there is1210 // an unused space at the end of Region. Exclude that space to avoid1211 // unused page map entry.1212 uptr AllocatedGroupSize = GroupBase == CurGroupBase1213 ? Sci->CurrentRegionAllocated1214 : roundDownSlow(GroupSize, BlockSize);1215 if (AllocatedGroupSize == 0)1216 continue;1217 1218 // Batches are pushed in front of BG.Batches. The first one may1219 // not have all caches used.1220 const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch +1221 BG.Batches.front()->getCount();1222 const uptr BytesInBG = NumBlocks * BlockSize;1223 1224 if (ReleaseType != ReleaseToOS::ForceAll) {1225 if (BytesInBG <= BG.BytesInBGAtLastCheckpoint) {1226 BG.BytesInBGAtLastCheckpoint = BytesInBG;1227 continue;1228 }1229 1230 const uptr PushedBytesDelta = BytesInBG - BG.BytesInBGAtLastCheckpoint;1231 if (PushedBytesDelta < PageSize)1232 continue;1233 1234 // Given the randomness property, we try to release the pages only if1235 // the bytes used by free blocks exceed certain proportion of allocated1236 // spaces.1237 if (isSmallBlock(BlockSize) && (BytesInBG * 100U) / AllocatedGroupSize <1238 (100U - 1U - BlockSize / 16U)) {1239 continue;1240 }1241 }1242 1243 // TODO: Consider updating this after page release if `ReleaseRecorder`1244 // can tell the released bytes in each group.1245 BG.BytesInBGAtLastCheckpoint = BytesInBG;1246 1247 const uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize;1248 const uptr RegionIndex = (GroupBase - Base) / RegionSize;1249 1250 if (NumBlocks == MaxContainedBlocks) {1251 for (const auto &It : BG.Batches)1252 for (u16 I = 0; I < It.getCount(); ++I)1253 DCHECK_EQ(compactPtrGroupBase(It.get(I)), BG.CompactPtrGroupBase);1254 1255 const uptr To = GroupBase + AllocatedGroupSize;1256 Context.markRangeAsAllCounted(GroupBase, To, GroupBase, RegionIndex,1257 AllocatedGroupSize);1258 } else {1259 DCHECK_LT(NumBlocks, MaxContainedBlocks);1260 1261 // Note that we don't always visit blocks in each BatchGroup so that we1262 // may miss the chance of releasing certain pages that cross1263 // BatchGroups.1264 Context.markFreeBlocksInRegion(BG.Batches, DecompactPtr, GroupBase,1265 RegionIndex, AllocatedGroupSize,1266 /*MayContainLastBlockInRegion=*/true);1267 }1268 1269 // We may not be able to do the page release In a rare case that we may1270 // fail on PageMap allocation.1271 if (UNLIKELY(!Context.hasBlockMarked()))1272 break;1273 }1274 1275 return Context;1276}1277 1278} // namespace scudo1279 1280#endif // SCUDO_PRIMARY32_H_1281