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-exception 6 // 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 "local_cache.h" 18 #include "mem_map.h" 19 #include "memtag.h" 20 #include "options.h" 21 #include "release.h" 22 #include "stats.h" 23 #include "string_utils.h" 24 #include "thread_annotations.h" 25 26 namespace scudo { 27 28 // SizeClassAllocator64 is an allocator tuned for 64-bit address space. 29 // 30 // It starts by reserving NumClasses * 2^RegionSizeLog bytes, equally divided in 31 // Regions, specific to each size class. Note that the base of that mapping is 32 // random (based to the platform specific map() capabilities). If 33 // PrimaryEnableRandomOffset is set, each Region actually starts at a random 34 // offset from its base. 35 // 36 // Regions are mapped incrementally on demand to fulfill allocation requests, 37 // those mappings being split into equally sized Blocks based on the size class 38 // they belong to. The Blocks created are shuffled to prevent predictable 39 // address patterns (the predictability increases with the size of the Blocks). 40 // 41 // The 1st Region (for size class 0) holds the TransferBatches. This is a 42 // structure used to transfer arrays of available pointers from the class size 43 // freelist to the thread specific freelist, and back. 44 // 45 // The memory used by this allocator is never unmapped, but can be partially 46 // released if the platform allows for it. 47 48 template <typename Config> class SizeClassAllocator64 { 49 public: 50 typedef typename Config::CompactPtrT CompactPtrT; 51 typedef typename Config::SizeClassMap SizeClassMap; 52 typedef typename Config::ConditionVariableT ConditionVariableT; 53 static const uptr CompactPtrScale = Config::getCompactPtrScale(); 54 static const uptr RegionSizeLog = Config::getRegionSizeLog(); 55 static const uptr GroupSizeLog = Config::getGroupSizeLog(); 56 static_assert(RegionSizeLog >= GroupSizeLog, 57 "Group size shouldn't be greater than the region size"); 58 static const uptr GroupScale = GroupSizeLog - CompactPtrScale; 59 typedef SizeClassAllocator64<Config> ThisT; 60 typedef SizeClassAllocatorLocalCache<ThisT> CacheT; 61 typedef TransferBatch<ThisT> TransferBatchT; 62 typedef BatchGroup<ThisT> BatchGroupT; 63 64 static_assert(sizeof(BatchGroupT) <= sizeof(TransferBatchT), 65 "BatchGroupT uses the same class size as TransferBatchT"); 66 getSizeByClassId(uptr ClassId)67 static uptr getSizeByClassId(uptr ClassId) { 68 return (ClassId == SizeClassMap::BatchClassId) 69 ? roundUp(sizeof(TransferBatchT), 1U << CompactPtrScale) 70 : SizeClassMap::getSizeByClassId(ClassId); 71 } 72 canAllocate(uptr Size)73 static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; } 74 conditionVariableEnabled()75 static bool conditionVariableEnabled() { 76 return Config::hasConditionVariableT(); 77 } 78 init(s32 ReleaseToOsInterval)79 void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS { 80 DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT))); 81 82 const uptr PageSize = getPageSizeCached(); 83 const uptr GroupSize = (1UL << GroupSizeLog); 84 const uptr PagesInGroup = GroupSize / PageSize; 85 const uptr MinSizeClass = getSizeByClassId(1); 86 // When trying to release pages back to memory, visiting smaller size 87 // classes is expensive. Therefore, we only try to release smaller size 88 // classes when the amount of free blocks goes over a certain threshold (See 89 // the comment in releaseToOSMaybe() for more details). For example, for 90 // size class 32, we only do the release when the size of free blocks is 91 // greater than 97% of pages in a group. However, this may introduce another 92 // issue that if the number of free blocks is bouncing between 97% ~ 100%. 93 // Which means we may try many page releases but only release very few of 94 // them (less than 3% in a group). Even though we have 95 // `&ReleaseToOsIntervalMs` which slightly reduce the frequency of these 96 // calls but it will be better to have another guard to mitigate this issue. 97 // 98 // Here we add another constraint on the minimum size requirement. The 99 // constraint is determined by the size of in-use blocks in the minimal size 100 // class. Take size class 32 as an example, 101 // 102 // +- one memory group -+ 103 // +----------------------+------+ 104 // | 97% of free blocks | | 105 // +----------------------+------+ 106 // \ / 107 // 3% in-use blocks 108 // 109 // * The release size threshold is 97%. 110 // 111 // The 3% size in a group is about 7 pages. For two consecutive 112 // releaseToOSMaybe(), we require the difference between `PushedBlocks` 113 // should be greater than 7 pages. This mitigates the page releasing 114 // thrashing which is caused by memory usage bouncing around the threshold. 115 // The smallest size class takes longest time to do the page release so we 116 // use its size of in-use blocks as a heuristic. 117 SmallerBlockReleasePageDelta = 118 PagesInGroup * (1 + MinSizeClass / 16U) / 100; 119 120 u32 Seed; 121 const u64 Time = getMonotonicTimeFast(); 122 if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))) 123 Seed = static_cast<u32>(Time ^ (reinterpret_cast<uptr>(&Seed) >> 12)); 124 125 for (uptr I = 0; I < NumClasses; I++) 126 getRegionInfo(I)->RandState = getRandomU32(&Seed); 127 128 if (Config::getEnableContiguousRegions()) { 129 ReservedMemoryT ReservedMemory = {}; 130 // Reserve the space required for the Primary. 131 CHECK(ReservedMemory.create(/*Addr=*/0U, RegionSize * NumClasses, 132 "scudo:primary_reserve")); 133 const uptr PrimaryBase = ReservedMemory.getBase(); 134 135 for (uptr I = 0; I < NumClasses; I++) { 136 MemMapT RegionMemMap = ReservedMemory.dispatch( 137 PrimaryBase + (I << RegionSizeLog), RegionSize); 138 RegionInfo *Region = getRegionInfo(I); 139 140 initRegion(Region, I, RegionMemMap, Config::getEnableRandomOffset()); 141 } 142 shuffle(RegionInfoArray, NumClasses, &Seed); 143 } 144 145 // The binding should be done after region shuffling so that it won't bind 146 // the FLLock from the wrong region. 147 for (uptr I = 0; I < NumClasses; I++) 148 getRegionInfo(I)->FLLockCV.bindTestOnly(getRegionInfo(I)->FLLock); 149 150 // The default value in the primary config has the higher priority. 151 if (Config::getDefaultReleaseToOsIntervalMs() != INT32_MIN) 152 ReleaseToOsInterval = Config::getDefaultReleaseToOsIntervalMs(); 153 setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval)); 154 } 155 unmapTestOnly()156 void unmapTestOnly() { 157 for (uptr I = 0; I < NumClasses; I++) { 158 RegionInfo *Region = getRegionInfo(I); 159 { 160 ScopedLock ML(Region->MMLock); 161 MemMapT MemMap = Region->MemMapInfo.MemMap; 162 if (MemMap.isAllocated()) 163 MemMap.unmap(MemMap.getBase(), MemMap.getCapacity()); 164 } 165 *Region = {}; 166 } 167 } 168 169 // When all blocks are freed, it has to be the same size as `AllocatedUser`. verifyAllBlocksAreReleasedTestOnly()170 void verifyAllBlocksAreReleasedTestOnly() { 171 // `BatchGroup` and `TransferBatch` also use the blocks from BatchClass. 172 uptr BatchClassUsedInFreeLists = 0; 173 for (uptr I = 0; I < NumClasses; I++) { 174 // We have to count BatchClassUsedInFreeLists in other regions first. 175 if (I == SizeClassMap::BatchClassId) 176 continue; 177 RegionInfo *Region = getRegionInfo(I); 178 ScopedLock ML(Region->MMLock); 179 ScopedLock FL(Region->FLLock); 180 const uptr BlockSize = getSizeByClassId(I); 181 uptr TotalBlocks = 0; 182 for (BatchGroupT &BG : Region->FreeListInfo.BlockList) { 183 // `BG::Batches` are `TransferBatches`. +1 for `BatchGroup`. 184 BatchClassUsedInFreeLists += BG.Batches.size() + 1; 185 for (const auto &It : BG.Batches) 186 TotalBlocks += It.getCount(); 187 } 188 189 DCHECK_EQ(TotalBlocks, Region->MemMapInfo.AllocatedUser / BlockSize); 190 DCHECK_EQ(Region->FreeListInfo.PushedBlocks, 191 Region->FreeListInfo.PoppedBlocks); 192 } 193 194 RegionInfo *Region = getRegionInfo(SizeClassMap::BatchClassId); 195 ScopedLock ML(Region->MMLock); 196 ScopedLock FL(Region->FLLock); 197 const uptr BlockSize = getSizeByClassId(SizeClassMap::BatchClassId); 198 uptr TotalBlocks = 0; 199 for (BatchGroupT &BG : Region->FreeListInfo.BlockList) { 200 if (LIKELY(!BG.Batches.empty())) { 201 for (const auto &It : BG.Batches) 202 TotalBlocks += It.getCount(); 203 } else { 204 // `BatchGroup` with empty freelist doesn't have `TransferBatch` record 205 // itself. 206 ++TotalBlocks; 207 } 208 } 209 DCHECK_EQ(TotalBlocks + BatchClassUsedInFreeLists, 210 Region->MemMapInfo.AllocatedUser / BlockSize); 211 DCHECK_GE(Region->FreeListInfo.PoppedBlocks, 212 Region->FreeListInfo.PushedBlocks); 213 const uptr BlocksInUse = 214 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks; 215 DCHECK_EQ(BlocksInUse, BatchClassUsedInFreeLists); 216 } 217 popBlocks(CacheT * C,uptr ClassId,CompactPtrT * ToArray,const u16 MaxBlockCount)218 u16 popBlocks(CacheT *C, uptr ClassId, CompactPtrT *ToArray, 219 const u16 MaxBlockCount) { 220 DCHECK_LT(ClassId, NumClasses); 221 RegionInfo *Region = getRegionInfo(ClassId); 222 u16 PopCount = 0; 223 224 { 225 ScopedLock L(Region->FLLock); 226 PopCount = popBlocksImpl(C, ClassId, Region, ToArray, MaxBlockCount); 227 if (PopCount != 0U) 228 return PopCount; 229 } 230 231 bool ReportRegionExhausted = false; 232 233 if (conditionVariableEnabled()) { 234 PopCount = popBlocksWithCV(C, ClassId, Region, ToArray, MaxBlockCount, 235 ReportRegionExhausted); 236 } else { 237 while (true) { 238 // When two threads compete for `Region->MMLock`, we only want one of 239 // them to call populateFreeListAndPopBatch(). To avoid both of them 240 // doing that, always check the freelist before mapping new pages. 241 ScopedLock ML(Region->MMLock); 242 { 243 ScopedLock FL(Region->FLLock); 244 PopCount = popBlocksImpl(C, ClassId, Region, ToArray, MaxBlockCount); 245 if (PopCount != 0U) 246 return PopCount; 247 } 248 249 const bool RegionIsExhausted = Region->Exhausted; 250 if (!RegionIsExhausted) { 251 PopCount = populateFreeListAndPopBlocks(C, ClassId, Region, ToArray, 252 MaxBlockCount); 253 } 254 ReportRegionExhausted = !RegionIsExhausted && Region->Exhausted; 255 break; 256 } 257 } 258 259 if (UNLIKELY(ReportRegionExhausted)) { 260 Printf("Can't populate more pages for size class %zu.\n", 261 getSizeByClassId(ClassId)); 262 263 // Theoretically, BatchClass shouldn't be used up. Abort immediately when 264 // it happens. 265 if (ClassId == SizeClassMap::BatchClassId) 266 reportOutOfBatchClass(); 267 } 268 269 return PopCount; 270 } 271 272 // Push the array of free blocks to the designated batch group. pushBlocks(CacheT * C,uptr ClassId,CompactPtrT * Array,u32 Size)273 void pushBlocks(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size) { 274 DCHECK_LT(ClassId, NumClasses); 275 DCHECK_GT(Size, 0); 276 277 RegionInfo *Region = getRegionInfo(ClassId); 278 if (ClassId == SizeClassMap::BatchClassId) { 279 ScopedLock L(Region->FLLock); 280 pushBatchClassBlocks(Region, Array, Size); 281 if (conditionVariableEnabled()) 282 Region->FLLockCV.notifyAll(Region->FLLock); 283 return; 284 } 285 286 // TODO(chiahungduan): Consider not doing grouping if the group size is not 287 // greater than the block size with a certain scale. 288 289 bool SameGroup = true; 290 if (GroupSizeLog < RegionSizeLog) { 291 // Sort the blocks so that blocks belonging to the same group can be 292 // pushed together. 293 for (u32 I = 1; I < Size; ++I) { 294 if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I])) 295 SameGroup = false; 296 CompactPtrT Cur = Array[I]; 297 u32 J = I; 298 while (J > 0 && compactPtrGroup(Cur) < compactPtrGroup(Array[J - 1])) { 299 Array[J] = Array[J - 1]; 300 --J; 301 } 302 Array[J] = Cur; 303 } 304 } 305 306 { 307 ScopedLock L(Region->FLLock); 308 pushBlocksImpl(C, ClassId, Region, Array, Size, SameGroup); 309 if (conditionVariableEnabled()) 310 Region->FLLockCV.notifyAll(Region->FLLock); 311 } 312 } 313 disable()314 void disable() NO_THREAD_SAFETY_ANALYSIS { 315 // The BatchClassId must be locked last since other classes can use it. 316 for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) { 317 if (static_cast<uptr>(I) == SizeClassMap::BatchClassId) 318 continue; 319 getRegionInfo(static_cast<uptr>(I))->MMLock.lock(); 320 getRegionInfo(static_cast<uptr>(I))->FLLock.lock(); 321 } 322 getRegionInfo(SizeClassMap::BatchClassId)->MMLock.lock(); 323 getRegionInfo(SizeClassMap::BatchClassId)->FLLock.lock(); 324 } 325 enable()326 void enable() NO_THREAD_SAFETY_ANALYSIS { 327 getRegionInfo(SizeClassMap::BatchClassId)->FLLock.unlock(); 328 getRegionInfo(SizeClassMap::BatchClassId)->MMLock.unlock(); 329 for (uptr I = 0; I < NumClasses; I++) { 330 if (I == SizeClassMap::BatchClassId) 331 continue; 332 getRegionInfo(I)->FLLock.unlock(); 333 getRegionInfo(I)->MMLock.unlock(); 334 } 335 } 336 iterateOverBlocks(F Callback)337 template <typename F> void iterateOverBlocks(F Callback) { 338 for (uptr I = 0; I < NumClasses; I++) { 339 if (I == SizeClassMap::BatchClassId) 340 continue; 341 RegionInfo *Region = getRegionInfo(I); 342 // TODO: The call of `iterateOverBlocks` requires disabling 343 // SizeClassAllocator64. We may consider locking each region on demand 344 // only. 345 Region->FLLock.assertHeld(); 346 Region->MMLock.assertHeld(); 347 const uptr BlockSize = getSizeByClassId(I); 348 const uptr From = Region->RegionBeg; 349 const uptr To = From + Region->MemMapInfo.AllocatedUser; 350 for (uptr Block = From; Block < To; Block += BlockSize) 351 Callback(Block); 352 } 353 } 354 getStats(ScopedString * Str)355 void getStats(ScopedString *Str) { 356 // TODO(kostyak): get the RSS per region. 357 uptr TotalMapped = 0; 358 uptr PoppedBlocks = 0; 359 uptr PushedBlocks = 0; 360 for (uptr I = 0; I < NumClasses; I++) { 361 RegionInfo *Region = getRegionInfo(I); 362 { 363 ScopedLock L(Region->MMLock); 364 TotalMapped += Region->MemMapInfo.MappedUser; 365 } 366 { 367 ScopedLock L(Region->FLLock); 368 PoppedBlocks += Region->FreeListInfo.PoppedBlocks; 369 PushedBlocks += Region->FreeListInfo.PushedBlocks; 370 } 371 } 372 const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs); 373 Str->append("Stats: SizeClassAllocator64: %zuM mapped (%uM rss) in %zu " 374 "allocations; remains %zu; ReleaseToOsIntervalMs = %d\n", 375 TotalMapped >> 20, 0U, PoppedBlocks, 376 PoppedBlocks - PushedBlocks, IntervalMs >= 0 ? IntervalMs : -1); 377 378 for (uptr I = 0; I < NumClasses; I++) { 379 RegionInfo *Region = getRegionInfo(I); 380 ScopedLock L1(Region->MMLock); 381 ScopedLock L2(Region->FLLock); 382 getStats(Str, I, Region); 383 } 384 } 385 getFragmentationInfo(ScopedString * Str)386 void getFragmentationInfo(ScopedString *Str) { 387 Str->append( 388 "Fragmentation Stats: SizeClassAllocator64: page size = %zu bytes\n", 389 getPageSizeCached()); 390 391 for (uptr I = 1; I < NumClasses; I++) { 392 RegionInfo *Region = getRegionInfo(I); 393 ScopedLock L(Region->MMLock); 394 getRegionFragmentationInfo(Region, I, Str); 395 } 396 } 397 setOption(Option O,sptr Value)398 bool setOption(Option O, sptr Value) { 399 if (O == Option::ReleaseInterval) { 400 const s32 Interval = Max( 401 Min(static_cast<s32>(Value), Config::getMaxReleaseToOsIntervalMs()), 402 Config::getMinReleaseToOsIntervalMs()); 403 atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval); 404 return true; 405 } 406 // Not supported by the Primary, but not an error either. 407 return true; 408 } 409 tryReleaseToOS(uptr ClassId,ReleaseToOS ReleaseType)410 uptr tryReleaseToOS(uptr ClassId, ReleaseToOS ReleaseType) { 411 RegionInfo *Region = getRegionInfo(ClassId); 412 // Note that the tryLock() may fail spuriously, given that it should rarely 413 // happen and page releasing is fine to skip, we don't take certain 414 // approaches to ensure one page release is done. 415 if (Region->MMLock.tryLock()) { 416 uptr BytesReleased = releaseToOSMaybe(Region, ClassId, ReleaseType); 417 Region->MMLock.unlock(); 418 return BytesReleased; 419 } 420 return 0; 421 } 422 releaseToOS(ReleaseToOS ReleaseType)423 uptr releaseToOS(ReleaseToOS ReleaseType) { 424 uptr TotalReleasedBytes = 0; 425 for (uptr I = 0; I < NumClasses; I++) { 426 if (I == SizeClassMap::BatchClassId) 427 continue; 428 RegionInfo *Region = getRegionInfo(I); 429 ScopedLock L(Region->MMLock); 430 TotalReleasedBytes += releaseToOSMaybe(Region, I, ReleaseType); 431 } 432 return TotalReleasedBytes; 433 } 434 getRegionInfoArrayAddress()435 const char *getRegionInfoArrayAddress() const { 436 return reinterpret_cast<const char *>(RegionInfoArray); 437 } 438 getRegionInfoArraySize()439 static uptr getRegionInfoArraySize() { return sizeof(RegionInfoArray); } 440 getCompactPtrBaseByClassId(uptr ClassId)441 uptr getCompactPtrBaseByClassId(uptr ClassId) { 442 return getRegionInfo(ClassId)->RegionBeg; 443 } 444 compactPtr(uptr ClassId,uptr Ptr)445 CompactPtrT compactPtr(uptr ClassId, uptr Ptr) { 446 DCHECK_LE(ClassId, SizeClassMap::LargestClassId); 447 return compactPtrInternal(getCompactPtrBaseByClassId(ClassId), Ptr); 448 } 449 decompactPtr(uptr ClassId,CompactPtrT CompactPtr)450 void *decompactPtr(uptr ClassId, CompactPtrT CompactPtr) { 451 DCHECK_LE(ClassId, SizeClassMap::LargestClassId); 452 return reinterpret_cast<void *>( 453 decompactPtrInternal(getCompactPtrBaseByClassId(ClassId), CompactPtr)); 454 } 455 findNearestBlock(const char * RegionInfoData,uptr Ptr)456 static BlockInfo findNearestBlock(const char *RegionInfoData, 457 uptr Ptr) NO_THREAD_SAFETY_ANALYSIS { 458 const RegionInfo *RegionInfoArray = 459 reinterpret_cast<const RegionInfo *>(RegionInfoData); 460 461 uptr ClassId; 462 uptr MinDistance = -1UL; 463 for (uptr I = 0; I != NumClasses; ++I) { 464 if (I == SizeClassMap::BatchClassId) 465 continue; 466 uptr Begin = RegionInfoArray[I].RegionBeg; 467 // TODO(chiahungduan): In fact, We need to lock the RegionInfo::MMLock. 468 // However, the RegionInfoData is passed with const qualifier and lock the 469 // mutex requires modifying RegionInfoData, which means we need to remove 470 // the const qualifier. This may lead to another undefined behavior (The 471 // first one is accessing `AllocatedUser` without locking. It's better to 472 // pass `RegionInfoData` as `void *` then we can lock the mutex properly. 473 uptr End = Begin + RegionInfoArray[I].MemMapInfo.AllocatedUser; 474 if (Begin > End || End - Begin < SizeClassMap::getSizeByClassId(I)) 475 continue; 476 uptr RegionDistance; 477 if (Begin <= Ptr) { 478 if (Ptr < End) 479 RegionDistance = 0; 480 else 481 RegionDistance = Ptr - End; 482 } else { 483 RegionDistance = Begin - Ptr; 484 } 485 486 if (RegionDistance < MinDistance) { 487 MinDistance = RegionDistance; 488 ClassId = I; 489 } 490 } 491 492 BlockInfo B = {}; 493 if (MinDistance <= 8192) { 494 B.RegionBegin = RegionInfoArray[ClassId].RegionBeg; 495 B.RegionEnd = 496 B.RegionBegin + RegionInfoArray[ClassId].MemMapInfo.AllocatedUser; 497 B.BlockSize = SizeClassMap::getSizeByClassId(ClassId); 498 B.BlockBegin = 499 B.RegionBegin + uptr(sptr(Ptr - B.RegionBegin) / sptr(B.BlockSize) * 500 sptr(B.BlockSize)); 501 while (B.BlockBegin < B.RegionBegin) 502 B.BlockBegin += B.BlockSize; 503 while (B.RegionEnd < B.BlockBegin + B.BlockSize) 504 B.BlockBegin -= B.BlockSize; 505 } 506 return B; 507 } 508 509 AtomicOptions Options; 510 511 private: 512 static const uptr RegionSize = 1UL << RegionSizeLog; 513 static const uptr NumClasses = SizeClassMap::NumClasses; 514 515 static const uptr MapSizeIncrement = Config::getMapSizeIncrement(); 516 // Fill at most this number of batches from the newly map'd memory. 517 static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U; 518 519 struct ReleaseToOsInfo { 520 uptr BytesInFreeListAtLastCheckpoint; 521 uptr RangesReleased; 522 uptr LastReleasedBytes; 523 u64 LastReleaseAtNs; 524 }; 525 526 struct BlocksInfo { 527 SinglyLinkedList<BatchGroupT> BlockList = {}; 528 uptr PoppedBlocks = 0; 529 uptr PushedBlocks = 0; 530 }; 531 532 struct PagesInfo { 533 MemMapT MemMap = {}; 534 // Bytes mapped for user memory. 535 uptr MappedUser = 0; 536 // Bytes allocated for user memory. 537 uptr AllocatedUser = 0; 538 }; 539 540 struct UnpaddedRegionInfo { 541 // Mutex for operations on freelist 542 HybridMutex FLLock; 543 ConditionVariableT FLLockCV GUARDED_BY(FLLock); 544 // Mutex for memmap operations 545 HybridMutex MMLock ACQUIRED_BEFORE(FLLock); 546 // `RegionBeg` is initialized before thread creation and won't be changed. 547 uptr RegionBeg = 0; 548 u32 RandState GUARDED_BY(MMLock) = 0; 549 BlocksInfo FreeListInfo GUARDED_BY(FLLock); 550 PagesInfo MemMapInfo GUARDED_BY(MMLock); 551 // The minimum size of pushed blocks to trigger page release. 552 uptr TryReleaseThreshold GUARDED_BY(MMLock) = 0; 553 ReleaseToOsInfo ReleaseInfo GUARDED_BY(MMLock) = {}; 554 bool Exhausted GUARDED_BY(MMLock) = false; 555 bool isPopulatingFreeList GUARDED_BY(FLLock) = false; 556 }; 557 struct RegionInfo : UnpaddedRegionInfo { 558 char Padding[SCUDO_CACHE_LINE_SIZE - 559 (sizeof(UnpaddedRegionInfo) % SCUDO_CACHE_LINE_SIZE)] = {}; 560 }; 561 static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, ""); 562 getRegionInfo(uptr ClassId)563 RegionInfo *getRegionInfo(uptr ClassId) { 564 DCHECK_LT(ClassId, NumClasses); 565 return &RegionInfoArray[ClassId]; 566 } 567 getRegionBaseByClassId(uptr ClassId)568 uptr getRegionBaseByClassId(uptr ClassId) { 569 RegionInfo *Region = getRegionInfo(ClassId); 570 Region->MMLock.assertHeld(); 571 572 if (!Config::getEnableContiguousRegions() && 573 !Region->MemMapInfo.MemMap.isAllocated()) { 574 return 0U; 575 } 576 return Region->MemMapInfo.MemMap.getBase(); 577 } 578 compactPtrInternal(uptr Base,uptr Ptr)579 static CompactPtrT compactPtrInternal(uptr Base, uptr Ptr) { 580 return static_cast<CompactPtrT>((Ptr - Base) >> CompactPtrScale); 581 } 582 decompactPtrInternal(uptr Base,CompactPtrT CompactPtr)583 static uptr decompactPtrInternal(uptr Base, CompactPtrT CompactPtr) { 584 return Base + (static_cast<uptr>(CompactPtr) << CompactPtrScale); 585 } 586 compactPtrGroup(CompactPtrT CompactPtr)587 static uptr compactPtrGroup(CompactPtrT CompactPtr) { 588 const uptr Mask = (static_cast<uptr>(1) << GroupScale) - 1; 589 return static_cast<uptr>(CompactPtr) & ~Mask; 590 } decompactGroupBase(uptr Base,uptr CompactPtrGroupBase)591 static uptr decompactGroupBase(uptr Base, uptr CompactPtrGroupBase) { 592 DCHECK_EQ(CompactPtrGroupBase % (static_cast<uptr>(1) << (GroupScale)), 0U); 593 return Base + (CompactPtrGroupBase << CompactPtrScale); 594 } 595 isSmallBlock(uptr BlockSize)596 ALWAYS_INLINE static bool isSmallBlock(uptr BlockSize) { 597 const uptr PageSize = getPageSizeCached(); 598 return BlockSize < PageSize / 16U; 599 } 600 isLargeBlock(uptr BlockSize)601 ALWAYS_INLINE static bool isLargeBlock(uptr BlockSize) { 602 const uptr PageSize = getPageSizeCached(); 603 return BlockSize > PageSize; 604 } 605 initRegion(RegionInfo * Region,uptr ClassId,MemMapT MemMap,bool EnableRandomOffset)606 ALWAYS_INLINE void initRegion(RegionInfo *Region, uptr ClassId, 607 MemMapT MemMap, bool EnableRandomOffset) 608 REQUIRES(Region->MMLock) { 609 DCHECK(!Region->MemMapInfo.MemMap.isAllocated()); 610 DCHECK(MemMap.isAllocated()); 611 612 const uptr PageSize = getPageSizeCached(); 613 614 Region->MemMapInfo.MemMap = MemMap; 615 616 Region->RegionBeg = MemMap.getBase(); 617 if (EnableRandomOffset) { 618 Region->RegionBeg += 619 (getRandomModN(&Region->RandState, 16) + 1) * PageSize; 620 } 621 622 // Releasing small blocks is expensive, set a higher threshold to avoid 623 // frequent page releases. 624 if (isSmallBlock(getSizeByClassId(ClassId))) 625 Region->TryReleaseThreshold = PageSize * SmallerBlockReleasePageDelta; 626 else 627 Region->TryReleaseThreshold = PageSize; 628 } 629 pushBatchClassBlocks(RegionInfo * Region,CompactPtrT * Array,u32 Size)630 void pushBatchClassBlocks(RegionInfo *Region, CompactPtrT *Array, u32 Size) 631 REQUIRES(Region->FLLock) { 632 DCHECK_EQ(Region, getRegionInfo(SizeClassMap::BatchClassId)); 633 634 // Free blocks are recorded by TransferBatch in freelist for all 635 // size-classes. In addition, TransferBatch is allocated from BatchClassId. 636 // In order not to use additional block to record the free blocks in 637 // BatchClassId, they are self-contained. I.e., A TransferBatch records the 638 // block address of itself. See the figure below: 639 // 640 // TransferBatch at 0xABCD 641 // +----------------------------+ 642 // | Free blocks' addr | 643 // | +------+------+------+ | 644 // | |0xABCD|... |... | | 645 // | +------+------+------+ | 646 // +----------------------------+ 647 // 648 // When we allocate all the free blocks in the TransferBatch, the block used 649 // by TransferBatch is also free for use. We don't need to recycle the 650 // TransferBatch. Note that the correctness is maintained by the invariant, 651 // 652 // Each popBlocks() request returns the entire TransferBatch. Returning 653 // part of the blocks in a TransferBatch is invalid. 654 // 655 // This ensures that TransferBatch won't leak the address itself while it's 656 // still holding other valid data. 657 // 658 // Besides, BatchGroup is also allocated from BatchClassId and has its 659 // address recorded in the TransferBatch too. To maintain the correctness, 660 // 661 // The address of BatchGroup is always recorded in the last TransferBatch 662 // in the freelist (also imply that the freelist should only be 663 // updated with push_front). Once the last TransferBatch is popped, 664 // the block used by BatchGroup is also free for use. 665 // 666 // With this approach, the blocks used by BatchGroup and TransferBatch are 667 // reusable and don't need additional space for them. 668 669 Region->FreeListInfo.PushedBlocks += Size; 670 BatchGroupT *BG = Region->FreeListInfo.BlockList.front(); 671 672 if (BG == nullptr) { 673 // Construct `BatchGroup` on the last element. 674 BG = reinterpret_cast<BatchGroupT *>( 675 decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1])); 676 --Size; 677 BG->Batches.clear(); 678 // BatchClass hasn't enabled memory group. Use `0` to indicate there's no 679 // memory group here. 680 BG->CompactPtrGroupBase = 0; 681 // `BG` is also the block of BatchClassId. Note that this is different 682 // from `CreateGroup` in `pushBlocksImpl` 683 BG->PushedBlocks = 1; 684 BG->BytesInBGAtLastCheckpoint = 0; 685 BG->MaxCachedPerBatch = 686 CacheT::getMaxCached(getSizeByClassId(SizeClassMap::BatchClassId)); 687 688 Region->FreeListInfo.BlockList.push_front(BG); 689 } 690 691 if (UNLIKELY(Size == 0)) 692 return; 693 694 // This happens under 2 cases. 695 // 1. just allocated a new `BatchGroup`. 696 // 2. Only 1 block is pushed when the freelist is empty. 697 if (BG->Batches.empty()) { 698 // Construct the `TransferBatch` on the last element. 699 TransferBatchT *TB = reinterpret_cast<TransferBatchT *>( 700 decompactPtr(SizeClassMap::BatchClassId, Array[Size - 1])); 701 TB->clear(); 702 // As mentioned above, addresses of `TransferBatch` and `BatchGroup` are 703 // recorded in the TransferBatch. 704 TB->add(Array[Size - 1]); 705 TB->add( 706 compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(BG))); 707 --Size; 708 DCHECK_EQ(BG->PushedBlocks, 1U); 709 // `TB` is also the block of BatchClassId. 710 BG->PushedBlocks += 1; 711 BG->Batches.push_front(TB); 712 } 713 714 TransferBatchT *CurBatch = BG->Batches.front(); 715 DCHECK_NE(CurBatch, nullptr); 716 717 for (u32 I = 0; I < Size;) { 718 u16 UnusedSlots = 719 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount()); 720 if (UnusedSlots == 0) { 721 CurBatch = reinterpret_cast<TransferBatchT *>( 722 decompactPtr(SizeClassMap::BatchClassId, Array[I])); 723 CurBatch->clear(); 724 // Self-contained 725 CurBatch->add(Array[I]); 726 ++I; 727 // TODO(chiahungduan): Avoid the use of push_back() in `Batches` of 728 // BatchClassId. 729 BG->Batches.push_front(CurBatch); 730 UnusedSlots = static_cast<u16>(BG->MaxCachedPerBatch - 1); 731 } 732 // `UnusedSlots` is u16 so the result will be also fit in u16. 733 const u16 AppendSize = static_cast<u16>(Min<u32>(UnusedSlots, Size - I)); 734 CurBatch->appendFromArray(&Array[I], AppendSize); 735 I += AppendSize; 736 } 737 738 BG->PushedBlocks += Size; 739 } 740 741 // Push the blocks to their batch group. The layout will be like, 742 // 743 // FreeListInfo.BlockList - > BG -> BG -> BG 744 // | | | 745 // v v v 746 // TB TB TB 747 // | 748 // v 749 // TB 750 // 751 // Each BlockGroup(BG) will associate with unique group id and the free blocks 752 // are managed by a list of TransferBatch(TB). To reduce the time of inserting 753 // blocks, BGs are sorted and the input `Array` are supposed to be sorted so 754 // that we can get better performance of maintaining sorted property. 755 // Use `SameGroup=true` to indicate that all blocks in the array are from the 756 // same group then we will skip checking the group id of each block. 757 void pushBlocksImpl(CacheT *C, uptr ClassId, RegionInfo *Region, 758 CompactPtrT *Array, u32 Size, bool SameGroup = false) 759 REQUIRES(Region->FLLock) { 760 DCHECK_NE(ClassId, SizeClassMap::BatchClassId); 761 DCHECK_GT(Size, 0U); 762 763 auto CreateGroup = [&](uptr CompactPtrGroupBase) { 764 BatchGroupT *BG = 765 reinterpret_cast<BatchGroupT *>(C->getBatchClassBlock()); 766 BG->Batches.clear(); 767 TransferBatchT *TB = 768 reinterpret_cast<TransferBatchT *>(C->getBatchClassBlock()); 769 TB->clear(); 770 771 BG->CompactPtrGroupBase = CompactPtrGroupBase; 772 BG->Batches.push_front(TB); 773 BG->PushedBlocks = 0; 774 BG->BytesInBGAtLastCheckpoint = 0; 775 BG->MaxCachedPerBatch = TransferBatchT::MaxNumCached; 776 777 return BG; 778 }; 779 780 auto InsertBlocks = [&](BatchGroupT *BG, CompactPtrT *Array, u32 Size) { 781 SinglyLinkedList<TransferBatchT> &Batches = BG->Batches; 782 TransferBatchT *CurBatch = Batches.front(); 783 DCHECK_NE(CurBatch, nullptr); 784 785 for (u32 I = 0; I < Size;) { 786 DCHECK_GE(BG->MaxCachedPerBatch, CurBatch->getCount()); 787 u16 UnusedSlots = 788 static_cast<u16>(BG->MaxCachedPerBatch - CurBatch->getCount()); 789 if (UnusedSlots == 0) { 790 CurBatch = 791 reinterpret_cast<TransferBatchT *>(C->getBatchClassBlock()); 792 CurBatch->clear(); 793 Batches.push_front(CurBatch); 794 UnusedSlots = BG->MaxCachedPerBatch; 795 } 796 // `UnusedSlots` is u16 so the result will be also fit in u16. 797 u16 AppendSize = static_cast<u16>(Min<u32>(UnusedSlots, Size - I)); 798 CurBatch->appendFromArray(&Array[I], AppendSize); 799 I += AppendSize; 800 } 801 802 BG->PushedBlocks += Size; 803 }; 804 805 Region->FreeListInfo.PushedBlocks += Size; 806 BatchGroupT *Cur = Region->FreeListInfo.BlockList.front(); 807 808 // In the following, `Cur` always points to the BatchGroup for blocks that 809 // will be pushed next. `Prev` is the element right before `Cur`. 810 BatchGroupT *Prev = nullptr; 811 812 while (Cur != nullptr && 813 compactPtrGroup(Array[0]) > Cur->CompactPtrGroupBase) { 814 Prev = Cur; 815 Cur = Cur->Next; 816 } 817 818 if (Cur == nullptr || 819 compactPtrGroup(Array[0]) != Cur->CompactPtrGroupBase) { 820 Cur = CreateGroup(compactPtrGroup(Array[0])); 821 if (Prev == nullptr) 822 Region->FreeListInfo.BlockList.push_front(Cur); 823 else 824 Region->FreeListInfo.BlockList.insert(Prev, Cur); 825 } 826 827 // All the blocks are from the same group, just push without checking group 828 // id. 829 if (SameGroup) { 830 for (u32 I = 0; I < Size; ++I) 831 DCHECK_EQ(compactPtrGroup(Array[I]), Cur->CompactPtrGroupBase); 832 833 InsertBlocks(Cur, Array, Size); 834 return; 835 } 836 837 // The blocks are sorted by group id. Determine the segment of group and 838 // push them to their group together. 839 u32 Count = 1; 840 for (u32 I = 1; I < Size; ++I) { 841 if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I])) { 842 DCHECK_EQ(compactPtrGroup(Array[I - 1]), Cur->CompactPtrGroupBase); 843 InsertBlocks(Cur, Array + I - Count, Count); 844 845 while (Cur != nullptr && 846 compactPtrGroup(Array[I]) > Cur->CompactPtrGroupBase) { 847 Prev = Cur; 848 Cur = Cur->Next; 849 } 850 851 if (Cur == nullptr || 852 compactPtrGroup(Array[I]) != Cur->CompactPtrGroupBase) { 853 Cur = CreateGroup(compactPtrGroup(Array[I])); 854 DCHECK_NE(Prev, nullptr); 855 Region->FreeListInfo.BlockList.insert(Prev, Cur); 856 } 857 858 Count = 1; 859 } else { 860 ++Count; 861 } 862 } 863 864 InsertBlocks(Cur, Array + Size - Count, Count); 865 } 866 popBlocksWithCV(CacheT * C,uptr ClassId,RegionInfo * Region,CompactPtrT * ToArray,const u16 MaxBlockCount,bool & ReportRegionExhausted)867 u16 popBlocksWithCV(CacheT *C, uptr ClassId, RegionInfo *Region, 868 CompactPtrT *ToArray, const u16 MaxBlockCount, 869 bool &ReportRegionExhausted) { 870 u16 PopCount = 0; 871 872 while (true) { 873 // We only expect one thread doing the freelist refillment and other 874 // threads will be waiting for either the completion of the 875 // `populateFreeListAndPopBatch()` or `pushBlocks()` called by other 876 // threads. 877 bool PopulateFreeList = false; 878 { 879 ScopedLock FL(Region->FLLock); 880 if (!Region->isPopulatingFreeList) { 881 Region->isPopulatingFreeList = true; 882 PopulateFreeList = true; 883 } 884 } 885 886 if (PopulateFreeList) { 887 ScopedLock ML(Region->MMLock); 888 889 const bool RegionIsExhausted = Region->Exhausted; 890 if (!RegionIsExhausted) { 891 PopCount = populateFreeListAndPopBlocks(C, ClassId, Region, ToArray, 892 MaxBlockCount); 893 } 894 ReportRegionExhausted = !RegionIsExhausted && Region->Exhausted; 895 896 { 897 // Before reacquiring the `FLLock`, the freelist may be used up again 898 // and some threads are waiting for the freelist refillment by the 899 // current thread. It's important to set 900 // `Region->isPopulatingFreeList` to false so the threads about to 901 // sleep will notice the status change. 902 ScopedLock FL(Region->FLLock); 903 Region->isPopulatingFreeList = false; 904 Region->FLLockCV.notifyAll(Region->FLLock); 905 } 906 907 break; 908 } 909 910 // At here, there are two preconditions to be met before waiting, 911 // 1. The freelist is empty. 912 // 2. Region->isPopulatingFreeList == true, i.e, someone is still doing 913 // `populateFreeListAndPopBatch()`. 914 // 915 // Note that it has the chance that freelist is empty but 916 // Region->isPopulatingFreeList == false because all the new populated 917 // blocks were used up right after the refillment. Therefore, we have to 918 // check if someone is still populating the freelist. 919 ScopedLock FL(Region->FLLock); 920 PopCount = popBlocksImpl(C, ClassId, Region, ToArray, MaxBlockCount); 921 if (PopCount != 0U) 922 break; 923 924 if (!Region->isPopulatingFreeList) 925 continue; 926 927 // Now the freelist is empty and someone's doing the refillment. We will 928 // wait until anyone refills the freelist or someone finishes doing 929 // `populateFreeListAndPopBatch()`. The refillment can be done by 930 // `populateFreeListAndPopBatch()`, `pushBlocks()`, 931 // `pushBatchClassBlocks()` and `mergeGroupsToReleaseBack()`. 932 Region->FLLockCV.wait(Region->FLLock); 933 934 PopCount = popBlocksImpl(C, ClassId, Region, ToArray, MaxBlockCount); 935 if (PopCount != 0U) 936 break; 937 } 938 939 return PopCount; 940 } 941 popBlocksImpl(CacheT * C,uptr ClassId,RegionInfo * Region,CompactPtrT * ToArray,const u16 MaxBlockCount)942 u16 popBlocksImpl(CacheT *C, uptr ClassId, RegionInfo *Region, 943 CompactPtrT *ToArray, const u16 MaxBlockCount) 944 REQUIRES(Region->FLLock) { 945 if (Region->FreeListInfo.BlockList.empty()) 946 return 0U; 947 948 SinglyLinkedList<TransferBatchT> &Batches = 949 Region->FreeListInfo.BlockList.front()->Batches; 950 951 if (Batches.empty()) { 952 DCHECK_EQ(ClassId, SizeClassMap::BatchClassId); 953 BatchGroupT *BG = Region->FreeListInfo.BlockList.front(); 954 Region->FreeListInfo.BlockList.pop_front(); 955 956 // Block used by `BatchGroup` is from BatchClassId. Turn the block into 957 // `TransferBatch` with single block. 958 TransferBatchT *TB = reinterpret_cast<TransferBatchT *>(BG); 959 ToArray[0] = 960 compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(TB)); 961 Region->FreeListInfo.PoppedBlocks += 1; 962 return 1U; 963 } 964 965 // So far, instead of always filling blocks to `MaxBlockCount`, we only 966 // examine single `TransferBatch` to minimize the time spent in the primary 967 // allocator. Besides, the sizes of `TransferBatch` and 968 // `CacheT::getMaxCached()` may also impact the time spent on accessing the 969 // primary allocator. 970 // TODO(chiahungduan): Evaluate if we want to always prepare `MaxBlockCount` 971 // blocks and/or adjust the size of `TransferBatch` according to 972 // `CacheT::getMaxCached()`. 973 TransferBatchT *B = Batches.front(); 974 DCHECK_NE(B, nullptr); 975 DCHECK_GT(B->getCount(), 0U); 976 977 // BachClassId should always take all blocks in the TransferBatch. Read the 978 // comment in `pushBatchClassBlocks()` for more details. 979 const u16 PopCount = ClassId == SizeClassMap::BatchClassId 980 ? B->getCount() 981 : Min(MaxBlockCount, B->getCount()); 982 B->moveNToArray(ToArray, PopCount); 983 984 // TODO(chiahungduan): The deallocation of unused BatchClassId blocks can be 985 // done without holding `FLLock`. 986 if (B->empty()) { 987 Batches.pop_front(); 988 // `TransferBatch` of BatchClassId is self-contained, no need to 989 // deallocate. Read the comment in `pushBatchClassBlocks()` for more 990 // details. 991 if (ClassId != SizeClassMap::BatchClassId) 992 C->deallocate(SizeClassMap::BatchClassId, B); 993 994 if (Batches.empty()) { 995 BatchGroupT *BG = Region->FreeListInfo.BlockList.front(); 996 Region->FreeListInfo.BlockList.pop_front(); 997 998 // We don't keep BatchGroup with zero blocks to avoid empty-checking 999 // while allocating. Note that block used for constructing BatchGroup is 1000 // recorded as free blocks in the last element of BatchGroup::Batches. 1001 // Which means, once we pop the last TransferBatch, the block is 1002 // implicitly deallocated. 1003 if (ClassId != SizeClassMap::BatchClassId) 1004 C->deallocate(SizeClassMap::BatchClassId, BG); 1005 } 1006 } 1007 1008 Region->FreeListInfo.PoppedBlocks += PopCount; 1009 1010 return PopCount; 1011 } 1012 populateFreeListAndPopBlocks(CacheT * C,uptr ClassId,RegionInfo * Region,CompactPtrT * ToArray,const u16 MaxBlockCount)1013 NOINLINE u16 populateFreeListAndPopBlocks(CacheT *C, uptr ClassId, 1014 RegionInfo *Region, 1015 CompactPtrT *ToArray, 1016 const u16 MaxBlockCount) 1017 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) { 1018 if (!Config::getEnableContiguousRegions() && 1019 !Region->MemMapInfo.MemMap.isAllocated()) { 1020 ReservedMemoryT ReservedMemory; 1021 if (UNLIKELY(!ReservedMemory.create(/*Addr=*/0U, RegionSize, 1022 "scudo:primary_reserve", 1023 MAP_ALLOWNOMEM))) { 1024 Printf("Can't reserve pages for size class %zu.\n", 1025 getSizeByClassId(ClassId)); 1026 return 0U; 1027 } 1028 initRegion(Region, ClassId, 1029 ReservedMemory.dispatch(ReservedMemory.getBase(), 1030 ReservedMemory.getCapacity()), 1031 /*EnableRandomOffset=*/false); 1032 } 1033 1034 DCHECK(Region->MemMapInfo.MemMap.isAllocated()); 1035 const uptr Size = getSizeByClassId(ClassId); 1036 const u16 MaxCount = CacheT::getMaxCached(Size); 1037 const uptr RegionBeg = Region->RegionBeg; 1038 const uptr MappedUser = Region->MemMapInfo.MappedUser; 1039 const uptr TotalUserBytes = 1040 Region->MemMapInfo.AllocatedUser + MaxCount * Size; 1041 // Map more space for blocks, if necessary. 1042 if (TotalUserBytes > MappedUser) { 1043 // Do the mmap for the user memory. 1044 const uptr MapSize = 1045 roundUp(TotalUserBytes - MappedUser, MapSizeIncrement); 1046 const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId); 1047 if (UNLIKELY(RegionBase + MappedUser + MapSize > RegionSize)) { 1048 Region->Exhausted = true; 1049 return 0U; 1050 } 1051 1052 if (UNLIKELY(!Region->MemMapInfo.MemMap.remap( 1053 RegionBeg + MappedUser, MapSize, "scudo:primary", 1054 MAP_ALLOWNOMEM | MAP_RESIZABLE | 1055 (useMemoryTagging<Config>(Options.load()) ? MAP_MEMTAG 1056 : 0)))) { 1057 return 0U; 1058 } 1059 Region->MemMapInfo.MappedUser += MapSize; 1060 C->getStats().add(StatMapped, MapSize); 1061 } 1062 1063 const u32 NumberOfBlocks = 1064 Min(MaxNumBatches * MaxCount, 1065 static_cast<u32>((Region->MemMapInfo.MappedUser - 1066 Region->MemMapInfo.AllocatedUser) / 1067 Size)); 1068 DCHECK_GT(NumberOfBlocks, 0); 1069 1070 constexpr u32 ShuffleArraySize = 1071 MaxNumBatches * TransferBatchT::MaxNumCached; 1072 CompactPtrT ShuffleArray[ShuffleArraySize]; 1073 DCHECK_LE(NumberOfBlocks, ShuffleArraySize); 1074 1075 const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId); 1076 uptr P = RegionBeg + Region->MemMapInfo.AllocatedUser; 1077 for (u32 I = 0; I < NumberOfBlocks; I++, P += Size) 1078 ShuffleArray[I] = compactPtrInternal(CompactPtrBase, P); 1079 1080 ScopedLock L(Region->FLLock); 1081 1082 if (ClassId != SizeClassMap::BatchClassId) { 1083 u32 N = 1; 1084 uptr CurGroup = compactPtrGroup(ShuffleArray[0]); 1085 for (u32 I = 1; I < NumberOfBlocks; I++) { 1086 if (UNLIKELY(compactPtrGroup(ShuffleArray[I]) != CurGroup)) { 1087 shuffle(ShuffleArray + I - N, N, &Region->RandState); 1088 pushBlocksImpl(C, ClassId, Region, ShuffleArray + I - N, N, 1089 /*SameGroup=*/true); 1090 N = 1; 1091 CurGroup = compactPtrGroup(ShuffleArray[I]); 1092 } else { 1093 ++N; 1094 } 1095 } 1096 1097 shuffle(ShuffleArray + NumberOfBlocks - N, N, &Region->RandState); 1098 pushBlocksImpl(C, ClassId, Region, &ShuffleArray[NumberOfBlocks - N], N, 1099 /*SameGroup=*/true); 1100 } else { 1101 pushBatchClassBlocks(Region, ShuffleArray, NumberOfBlocks); 1102 } 1103 1104 const u16 PopCount = 1105 popBlocksImpl(C, ClassId, Region, ToArray, MaxBlockCount); 1106 DCHECK_NE(PopCount, 0U); 1107 1108 // Note that `PushedBlocks` and `PoppedBlocks` are supposed to only record 1109 // the requests from `PushBlocks` and `PopBatch` which are external 1110 // interfaces. `populateFreeListAndPopBatch` is the internal interface so we 1111 // should set the values back to avoid incorrectly setting the stats. 1112 Region->FreeListInfo.PushedBlocks -= NumberOfBlocks; 1113 1114 const uptr AllocatedUser = Size * NumberOfBlocks; 1115 C->getStats().add(StatFree, AllocatedUser); 1116 Region->MemMapInfo.AllocatedUser += AllocatedUser; 1117 1118 return PopCount; 1119 } 1120 getStats(ScopedString * Str,uptr ClassId,RegionInfo * Region)1121 void getStats(ScopedString *Str, uptr ClassId, RegionInfo *Region) 1122 REQUIRES(Region->MMLock, Region->FLLock) { 1123 if (Region->MemMapInfo.MappedUser == 0) 1124 return; 1125 const uptr BlockSize = getSizeByClassId(ClassId); 1126 const uptr InUseBlocks = 1127 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks; 1128 const uptr BytesInFreeList = 1129 Region->MemMapInfo.AllocatedUser - InUseBlocks * BlockSize; 1130 uptr RegionPushedBytesDelta = 0; 1131 if (BytesInFreeList >= 1132 Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) { 1133 RegionPushedBytesDelta = 1134 BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint; 1135 } 1136 const uptr TotalChunks = Region->MemMapInfo.AllocatedUser / BlockSize; 1137 Str->append( 1138 "%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu " 1139 "inuse: %6zu total: %6zu releases: %6zu last " 1140 "released: %6zuK latest pushed bytes: %6zuK region: 0x%zx (0x%zx)\n", 1141 Region->Exhausted ? "E" : " ", ClassId, getSizeByClassId(ClassId), 1142 Region->MemMapInfo.MappedUser >> 10, Region->FreeListInfo.PoppedBlocks, 1143 Region->FreeListInfo.PushedBlocks, InUseBlocks, TotalChunks, 1144 Region->ReleaseInfo.RangesReleased, 1145 Region->ReleaseInfo.LastReleasedBytes >> 10, 1146 RegionPushedBytesDelta >> 10, Region->RegionBeg, 1147 getRegionBaseByClassId(ClassId)); 1148 } 1149 getRegionFragmentationInfo(RegionInfo * Region,uptr ClassId,ScopedString * Str)1150 void getRegionFragmentationInfo(RegionInfo *Region, uptr ClassId, 1151 ScopedString *Str) REQUIRES(Region->MMLock) { 1152 const uptr BlockSize = getSizeByClassId(ClassId); 1153 const uptr AllocatedUserEnd = 1154 Region->MemMapInfo.AllocatedUser + Region->RegionBeg; 1155 1156 SinglyLinkedList<BatchGroupT> GroupsToRelease; 1157 { 1158 ScopedLock L(Region->FLLock); 1159 GroupsToRelease = Region->FreeListInfo.BlockList; 1160 Region->FreeListInfo.BlockList.clear(); 1161 } 1162 1163 FragmentationRecorder Recorder; 1164 if (!GroupsToRelease.empty()) { 1165 PageReleaseContext Context = 1166 markFreeBlocks(Region, BlockSize, AllocatedUserEnd, 1167 getCompactPtrBaseByClassId(ClassId), GroupsToRelease); 1168 auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; }; 1169 releaseFreeMemoryToOS(Context, Recorder, SkipRegion); 1170 1171 mergeGroupsToReleaseBack(Region, GroupsToRelease); 1172 } 1173 1174 ScopedLock L(Region->FLLock); 1175 const uptr PageSize = getPageSizeCached(); 1176 const uptr TotalBlocks = Region->MemMapInfo.AllocatedUser / BlockSize; 1177 const uptr InUseBlocks = 1178 Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks; 1179 const uptr AllocatedPagesCount = 1180 roundUp(Region->MemMapInfo.AllocatedUser, PageSize) / PageSize; 1181 DCHECK_GE(AllocatedPagesCount, Recorder.getReleasedPagesCount()); 1182 const uptr InUsePages = 1183 AllocatedPagesCount - Recorder.getReleasedPagesCount(); 1184 const uptr InUseBytes = InUsePages * PageSize; 1185 1186 uptr Integral; 1187 uptr Fractional; 1188 computePercentage(BlockSize * InUseBlocks, InUsePages * PageSize, &Integral, 1189 &Fractional); 1190 Str->append(" %02zu (%6zu): inuse/total blocks: %6zu/%6zu inuse/total " 1191 "pages: %6zu/%6zu inuse bytes: %6zuK util: %3zu.%02zu%%\n", 1192 ClassId, BlockSize, InUseBlocks, TotalBlocks, InUsePages, 1193 AllocatedPagesCount, InUseBytes >> 10, Integral, Fractional); 1194 } 1195 1196 NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId, 1197 ReleaseToOS ReleaseType = ReleaseToOS::Normal) 1198 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) { 1199 const uptr BlockSize = getSizeByClassId(ClassId); 1200 uptr BytesInFreeList; 1201 const uptr AllocatedUserEnd = 1202 Region->MemMapInfo.AllocatedUser + Region->RegionBeg; 1203 SinglyLinkedList<BatchGroupT> GroupsToRelease; 1204 1205 { 1206 ScopedLock L(Region->FLLock); 1207 1208 BytesInFreeList = Region->MemMapInfo.AllocatedUser - 1209 (Region->FreeListInfo.PoppedBlocks - 1210 Region->FreeListInfo.PushedBlocks) * 1211 BlockSize; 1212 if (UNLIKELY(BytesInFreeList == 0)) 1213 return false; 1214 1215 // ==================================================================== // 1216 // 1. Check if we have enough free blocks and if it's worth doing a page 1217 // release. 1218 // ==================================================================== // 1219 if (ReleaseType != ReleaseToOS::ForceAll && 1220 !hasChanceToReleasePages(Region, BlockSize, BytesInFreeList, 1221 ReleaseType)) { 1222 return 0; 1223 } 1224 1225 // ==================================================================== // 1226 // 2. Determine which groups can release the pages. Use a heuristic to 1227 // gather groups that are candidates for doing a release. 1228 // ==================================================================== // 1229 if (ReleaseType == ReleaseToOS::ForceAll) { 1230 GroupsToRelease = Region->FreeListInfo.BlockList; 1231 Region->FreeListInfo.BlockList.clear(); 1232 } else { 1233 GroupsToRelease = 1234 collectGroupsToRelease(Region, BlockSize, AllocatedUserEnd, 1235 getCompactPtrBaseByClassId(ClassId)); 1236 } 1237 if (GroupsToRelease.empty()) 1238 return 0; 1239 } 1240 1241 // Note that we have extracted the `GroupsToRelease` from region freelist. 1242 // It's safe to let pushBlocks()/popBlocks() access the remaining region 1243 // freelist. In the steps 3 and 4, we will temporarily release the FLLock 1244 // and lock it again before step 5. 1245 1246 // ==================================================================== // 1247 // 3. Mark the free blocks in `GroupsToRelease` in the `PageReleaseContext`. 1248 // Then we can tell which pages are in-use by querying 1249 // `PageReleaseContext`. 1250 // ==================================================================== // 1251 PageReleaseContext Context = 1252 markFreeBlocks(Region, BlockSize, AllocatedUserEnd, 1253 getCompactPtrBaseByClassId(ClassId), GroupsToRelease); 1254 if (UNLIKELY(!Context.hasBlockMarked())) { 1255 mergeGroupsToReleaseBack(Region, GroupsToRelease); 1256 return 0; 1257 } 1258 1259 // ==================================================================== // 1260 // 4. Release the unused physical pages back to the OS. 1261 // ==================================================================== // 1262 RegionReleaseRecorder<MemMapT> Recorder(&Region->MemMapInfo.MemMap, 1263 Region->RegionBeg, 1264 Context.getReleaseOffset()); 1265 auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; }; 1266 releaseFreeMemoryToOS(Context, Recorder, SkipRegion); 1267 if (Recorder.getReleasedRangesCount() > 0) { 1268 Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList; 1269 Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount(); 1270 Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes(); 1271 } 1272 Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast(); 1273 1274 // ====================================================================== // 1275 // 5. Merge the `GroupsToRelease` back to the freelist. 1276 // ====================================================================== // 1277 mergeGroupsToReleaseBack(Region, GroupsToRelease); 1278 1279 return Recorder.getReleasedBytes(); 1280 } 1281 hasChanceToReleasePages(RegionInfo * Region,uptr BlockSize,uptr BytesInFreeList,ReleaseToOS ReleaseType)1282 bool hasChanceToReleasePages(RegionInfo *Region, uptr BlockSize, 1283 uptr BytesInFreeList, ReleaseToOS ReleaseType) 1284 REQUIRES(Region->MMLock, Region->FLLock) { 1285 DCHECK_GE(Region->FreeListInfo.PoppedBlocks, 1286 Region->FreeListInfo.PushedBlocks); 1287 const uptr PageSize = getPageSizeCached(); 1288 1289 // Always update `BytesInFreeListAtLastCheckpoint` with the smallest value 1290 // so that we won't underestimate the releasable pages. For example, the 1291 // following is the region usage, 1292 // 1293 // BytesInFreeListAtLastCheckpoint AllocatedUser 1294 // v v 1295 // |---------------------------------------> 1296 // ^ ^ 1297 // BytesInFreeList ReleaseThreshold 1298 // 1299 // In general, if we have collected enough bytes and the amount of free 1300 // bytes meets the ReleaseThreshold, we will try to do page release. If we 1301 // don't update `BytesInFreeListAtLastCheckpoint` when the current 1302 // `BytesInFreeList` is smaller, we may take longer time to wait for enough 1303 // freed blocks because we miss the bytes between 1304 // (BytesInFreeListAtLastCheckpoint - BytesInFreeList). 1305 if (BytesInFreeList <= 1306 Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint) { 1307 Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList; 1308 } 1309 1310 const uptr RegionPushedBytesDelta = 1311 BytesInFreeList - Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint; 1312 if (RegionPushedBytesDelta < PageSize) 1313 return false; 1314 1315 // Releasing smaller blocks is expensive, so we want to make sure that a 1316 // significant amount of bytes are free, and that there has been a good 1317 // amount of batches pushed to the freelist before attempting to release. 1318 if (isSmallBlock(BlockSize) && ReleaseType == ReleaseToOS::Normal) 1319 if (RegionPushedBytesDelta < Region->TryReleaseThreshold) 1320 return false; 1321 1322 if (ReleaseType == ReleaseToOS::Normal) { 1323 const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs); 1324 if (IntervalMs < 0) 1325 return false; 1326 1327 // The constant 8 here is selected from profiling some apps and the number 1328 // of unreleased pages in the large size classes is around 16 pages or 1329 // more. Choose half of it as a heuristic and which also avoids page 1330 // release every time for every pushBlocks() attempt by large blocks. 1331 const bool ByPassReleaseInterval = 1332 isLargeBlock(BlockSize) && RegionPushedBytesDelta > 8 * PageSize; 1333 if (!ByPassReleaseInterval) { 1334 if (Region->ReleaseInfo.LastReleaseAtNs + 1335 static_cast<u64>(IntervalMs) * 1000000 > 1336 getMonotonicTimeFast()) { 1337 // Memory was returned recently. 1338 return false; 1339 } 1340 } 1341 } // if (ReleaseType == ReleaseToOS::Normal) 1342 1343 return true; 1344 } 1345 1346 SinglyLinkedList<BatchGroupT> collectGroupsToRelease(RegionInfo * Region,const uptr BlockSize,const uptr AllocatedUserEnd,const uptr CompactPtrBase)1347 collectGroupsToRelease(RegionInfo *Region, const uptr BlockSize, 1348 const uptr AllocatedUserEnd, const uptr CompactPtrBase) 1349 REQUIRES(Region->MMLock, Region->FLLock) { 1350 const uptr GroupSize = (1UL << GroupSizeLog); 1351 const uptr PageSize = getPageSizeCached(); 1352 SinglyLinkedList<BatchGroupT> GroupsToRelease; 1353 1354 // We are examining each group and will take the minimum distance to the 1355 // release threshold as the next Region::TryReleaseThreshold(). Note that if 1356 // the size of free blocks has reached the release threshold, the distance 1357 // to the next release will be PageSize * SmallerBlockReleasePageDelta. See 1358 // the comment on `SmallerBlockReleasePageDelta` for more details. 1359 uptr MinDistToThreshold = GroupSize; 1360 1361 for (BatchGroupT *BG = Region->FreeListInfo.BlockList.front(), 1362 *Prev = nullptr; 1363 BG != nullptr;) { 1364 // Group boundary is always GroupSize-aligned from CompactPtr base. The 1365 // layout of memory groups is like, 1366 // 1367 // (CompactPtrBase) 1368 // #1 CompactPtrGroupBase #2 CompactPtrGroupBase ... 1369 // | | | 1370 // v v v 1371 // +-----------------------+-----------------------+ 1372 // \ / \ / 1373 // --- GroupSize --- --- GroupSize --- 1374 // 1375 // After decompacting the CompactPtrGroupBase, we expect the alignment 1376 // property is held as well. 1377 const uptr BatchGroupBase = 1378 decompactGroupBase(CompactPtrBase, BG->CompactPtrGroupBase); 1379 DCHECK_LE(Region->RegionBeg, BatchGroupBase); 1380 DCHECK_GE(AllocatedUserEnd, BatchGroupBase); 1381 DCHECK_EQ((Region->RegionBeg - BatchGroupBase) % GroupSize, 0U); 1382 // TransferBatches are pushed in front of BG.Batches. The first one may 1383 // not have all caches used. 1384 const uptr NumBlocks = (BG->Batches.size() - 1) * BG->MaxCachedPerBatch + 1385 BG->Batches.front()->getCount(); 1386 const uptr BytesInBG = NumBlocks * BlockSize; 1387 1388 if (BytesInBG <= BG->BytesInBGAtLastCheckpoint) { 1389 BG->BytesInBGAtLastCheckpoint = BytesInBG; 1390 Prev = BG; 1391 BG = BG->Next; 1392 continue; 1393 } 1394 1395 const uptr PushedBytesDelta = BytesInBG - BG->BytesInBGAtLastCheckpoint; 1396 1397 // Given the randomness property, we try to release the pages only if the 1398 // bytes used by free blocks exceed certain proportion of group size. Note 1399 // that this heuristic only applies when all the spaces in a BatchGroup 1400 // are allocated. 1401 if (isSmallBlock(BlockSize)) { 1402 const uptr BatchGroupEnd = BatchGroupBase + GroupSize; 1403 const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd 1404 ? GroupSize 1405 : AllocatedUserEnd - BatchGroupBase; 1406 const uptr ReleaseThreshold = 1407 (AllocatedGroupSize * (100 - 1U - BlockSize / 16U)) / 100U; 1408 const bool HighDensity = BytesInBG >= ReleaseThreshold; 1409 const bool MayHaveReleasedAll = NumBlocks >= (GroupSize / BlockSize); 1410 // If all blocks in the group are released, we will do range marking 1411 // which is fast. Otherwise, we will wait until we have accumulated 1412 // a certain amount of free memory. 1413 const bool ReachReleaseDelta = 1414 MayHaveReleasedAll 1415 ? true 1416 : PushedBytesDelta >= PageSize * SmallerBlockReleasePageDelta; 1417 1418 if (!HighDensity) { 1419 DCHECK_LE(BytesInBG, ReleaseThreshold); 1420 // The following is the usage of a memroy group, 1421 // 1422 // BytesInBG ReleaseThreshold 1423 // / \ v 1424 // +---+---------------------------+-----+ 1425 // | | | | | 1426 // +---+---------------------------+-----+ 1427 // \ / ^ 1428 // PushedBytesDelta GroupEnd 1429 MinDistToThreshold = 1430 Min(MinDistToThreshold, 1431 ReleaseThreshold - BytesInBG + PushedBytesDelta); 1432 } else { 1433 // If it reaches high density at this round, the next time we will try 1434 // to release is based on SmallerBlockReleasePageDelta 1435 MinDistToThreshold = 1436 Min(MinDistToThreshold, PageSize * SmallerBlockReleasePageDelta); 1437 } 1438 1439 if (!HighDensity || !ReachReleaseDelta) { 1440 Prev = BG; 1441 BG = BG->Next; 1442 continue; 1443 } 1444 } 1445 1446 // If `BG` is the first BatchGroupT in the list, we only need to advance 1447 // `BG` and call FreeListInfo.BlockList::pop_front(). No update is needed 1448 // for `Prev`. 1449 // 1450 // (BG) (BG->Next) 1451 // Prev Cur BG 1452 // | | | 1453 // v v v 1454 // nil +--+ +--+ 1455 // |X | -> | | -> ... 1456 // +--+ +--+ 1457 // 1458 // Otherwise, `Prev` will be used to extract the `Cur` from the 1459 // `FreeListInfo.BlockList`. 1460 // 1461 // (BG) (BG->Next) 1462 // Prev Cur BG 1463 // | | | 1464 // v v v 1465 // +--+ +--+ +--+ 1466 // | | -> |X | -> | | -> ... 1467 // +--+ +--+ +--+ 1468 // 1469 // After FreeListInfo.BlockList::extract(), 1470 // 1471 // Prev Cur BG 1472 // | | | 1473 // v v v 1474 // +--+ +--+ +--+ 1475 // | |-+ |X | +->| | -> ... 1476 // +--+ | +--+ | +--+ 1477 // +--------+ 1478 // 1479 // Note that we need to advance before pushing this BatchGroup to 1480 // GroupsToRelease because it's a destructive operation. 1481 1482 BatchGroupT *Cur = BG; 1483 BG = BG->Next; 1484 1485 // Ideally, we may want to update this only after successful release. 1486 // However, for smaller blocks, each block marking is a costly operation. 1487 // Therefore, we update it earlier. 1488 // TODO: Consider updating this after releasing pages if `ReleaseRecorder` 1489 // can tell the released bytes in each group. 1490 Cur->BytesInBGAtLastCheckpoint = BytesInBG; 1491 1492 if (Prev != nullptr) 1493 Region->FreeListInfo.BlockList.extract(Prev, Cur); 1494 else 1495 Region->FreeListInfo.BlockList.pop_front(); 1496 GroupsToRelease.push_back(Cur); 1497 } 1498 1499 // Only small blocks have the adaptive `TryReleaseThreshold`. 1500 if (isSmallBlock(BlockSize)) { 1501 // If the MinDistToThreshold is not updated, that means each memory group 1502 // may have only pushed less than a page size. In that case, just set it 1503 // back to normal. 1504 if (MinDistToThreshold == GroupSize) 1505 MinDistToThreshold = PageSize * SmallerBlockReleasePageDelta; 1506 Region->TryReleaseThreshold = MinDistToThreshold; 1507 } 1508 1509 return GroupsToRelease; 1510 } 1511 1512 PageReleaseContext markFreeBlocks(RegionInfo * Region,const uptr BlockSize,const uptr AllocatedUserEnd,const uptr CompactPtrBase,SinglyLinkedList<BatchGroupT> & GroupsToRelease)1513 markFreeBlocks(RegionInfo *Region, const uptr BlockSize, 1514 const uptr AllocatedUserEnd, const uptr CompactPtrBase, 1515 SinglyLinkedList<BatchGroupT> &GroupsToRelease) 1516 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) { 1517 const uptr GroupSize = (1UL << GroupSizeLog); 1518 auto DecompactPtr = [CompactPtrBase](CompactPtrT CompactPtr) { 1519 return decompactPtrInternal(CompactPtrBase, CompactPtr); 1520 }; 1521 1522 const uptr ReleaseBase = decompactGroupBase( 1523 CompactPtrBase, GroupsToRelease.front()->CompactPtrGroupBase); 1524 const uptr LastGroupEnd = 1525 Min(decompactGroupBase(CompactPtrBase, 1526 GroupsToRelease.back()->CompactPtrGroupBase) + 1527 GroupSize, 1528 AllocatedUserEnd); 1529 // The last block may straddle the group boundary. Rounding up to BlockSize 1530 // to get the exact range. 1531 const uptr ReleaseEnd = 1532 roundUpSlow(LastGroupEnd - Region->RegionBeg, BlockSize) + 1533 Region->RegionBeg; 1534 const uptr ReleaseRangeSize = ReleaseEnd - ReleaseBase; 1535 const uptr ReleaseOffset = ReleaseBase - Region->RegionBeg; 1536 1537 PageReleaseContext Context(BlockSize, /*NumberOfRegions=*/1U, 1538 ReleaseRangeSize, ReleaseOffset); 1539 // We may not be able to do the page release in a rare case that we may 1540 // fail on PageMap allocation. 1541 if (UNLIKELY(!Context.ensurePageMapAllocated())) 1542 return Context; 1543 1544 for (BatchGroupT &BG : GroupsToRelease) { 1545 const uptr BatchGroupBase = 1546 decompactGroupBase(CompactPtrBase, BG.CompactPtrGroupBase); 1547 const uptr BatchGroupEnd = BatchGroupBase + GroupSize; 1548 const uptr AllocatedGroupSize = AllocatedUserEnd >= BatchGroupEnd 1549 ? GroupSize 1550 : AllocatedUserEnd - BatchGroupBase; 1551 const uptr BatchGroupUsedEnd = BatchGroupBase + AllocatedGroupSize; 1552 const bool MayContainLastBlockInRegion = 1553 BatchGroupUsedEnd == AllocatedUserEnd; 1554 const bool BlockAlignedWithUsedEnd = 1555 (BatchGroupUsedEnd - Region->RegionBeg) % BlockSize == 0; 1556 1557 uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize; 1558 if (!BlockAlignedWithUsedEnd) 1559 ++MaxContainedBlocks; 1560 1561 const uptr NumBlocks = (BG.Batches.size() - 1) * BG.MaxCachedPerBatch + 1562 BG.Batches.front()->getCount(); 1563 1564 if (NumBlocks == MaxContainedBlocks) { 1565 for (const auto &It : BG.Batches) { 1566 if (&It != BG.Batches.front()) 1567 DCHECK_EQ(It.getCount(), BG.MaxCachedPerBatch); 1568 for (u16 I = 0; I < It.getCount(); ++I) 1569 DCHECK_EQ(compactPtrGroup(It.get(I)), BG.CompactPtrGroupBase); 1570 } 1571 1572 Context.markRangeAsAllCounted(BatchGroupBase, BatchGroupUsedEnd, 1573 Region->RegionBeg, /*RegionIndex=*/0, 1574 Region->MemMapInfo.AllocatedUser); 1575 } else { 1576 DCHECK_LT(NumBlocks, MaxContainedBlocks); 1577 // Note that we don't always visit blocks in each BatchGroup so that we 1578 // may miss the chance of releasing certain pages that cross 1579 // BatchGroups. 1580 Context.markFreeBlocksInRegion( 1581 BG.Batches, DecompactPtr, Region->RegionBeg, /*RegionIndex=*/0, 1582 Region->MemMapInfo.AllocatedUser, MayContainLastBlockInRegion); 1583 } 1584 } 1585 1586 DCHECK(Context.hasBlockMarked()); 1587 1588 return Context; 1589 } 1590 mergeGroupsToReleaseBack(RegionInfo * Region,SinglyLinkedList<BatchGroupT> & GroupsToRelease)1591 void mergeGroupsToReleaseBack(RegionInfo *Region, 1592 SinglyLinkedList<BatchGroupT> &GroupsToRelease) 1593 REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) { 1594 ScopedLock L(Region->FLLock); 1595 1596 // After merging two freelists, we may have redundant `BatchGroup`s that 1597 // need to be recycled. The number of unused `BatchGroup`s is expected to be 1598 // small. Pick a constant which is inferred from real programs. 1599 constexpr uptr MaxUnusedSize = 8; 1600 CompactPtrT Blocks[MaxUnusedSize]; 1601 u32 Idx = 0; 1602 RegionInfo *BatchClassRegion = getRegionInfo(SizeClassMap::BatchClassId); 1603 // We can't call pushBatchClassBlocks() to recycle the unused `BatchGroup`s 1604 // when we are manipulating the freelist of `BatchClassRegion`. Instead, we 1605 // should just push it back to the freelist when we merge two `BatchGroup`s. 1606 // This logic hasn't been implemented because we haven't supported releasing 1607 // pages in `BatchClassRegion`. 1608 DCHECK_NE(BatchClassRegion, Region); 1609 1610 // Merge GroupsToRelease back to the Region::FreeListInfo.BlockList. Note 1611 // that both `Region->FreeListInfo.BlockList` and `GroupsToRelease` are 1612 // sorted. 1613 for (BatchGroupT *BG = Region->FreeListInfo.BlockList.front(), 1614 *Prev = nullptr; 1615 ;) { 1616 if (BG == nullptr || GroupsToRelease.empty()) { 1617 if (!GroupsToRelease.empty()) 1618 Region->FreeListInfo.BlockList.append_back(&GroupsToRelease); 1619 break; 1620 } 1621 1622 DCHECK(!BG->Batches.empty()); 1623 1624 if (BG->CompactPtrGroupBase < 1625 GroupsToRelease.front()->CompactPtrGroupBase) { 1626 Prev = BG; 1627 BG = BG->Next; 1628 continue; 1629 } 1630 1631 BatchGroupT *Cur = GroupsToRelease.front(); 1632 TransferBatchT *UnusedTransferBatch = nullptr; 1633 GroupsToRelease.pop_front(); 1634 1635 if (BG->CompactPtrGroupBase == Cur->CompactPtrGroupBase) { 1636 BG->PushedBlocks += Cur->PushedBlocks; 1637 // We have updated `BatchGroup::BytesInBGAtLastCheckpoint` while 1638 // collecting the `GroupsToRelease`. 1639 BG->BytesInBGAtLastCheckpoint = Cur->BytesInBGAtLastCheckpoint; 1640 const uptr MaxCachedPerBatch = BG->MaxCachedPerBatch; 1641 1642 // Note that the first TransferBatches in both `Batches` may not be 1643 // full and only the first TransferBatch can have non-full blocks. Thus 1644 // we have to merge them before appending one to another. 1645 if (Cur->Batches.front()->getCount() == MaxCachedPerBatch) { 1646 BG->Batches.append_back(&Cur->Batches); 1647 } else { 1648 TransferBatchT *NonFullBatch = Cur->Batches.front(); 1649 Cur->Batches.pop_front(); 1650 const u16 NonFullBatchCount = NonFullBatch->getCount(); 1651 // The remaining Batches in `Cur` are full. 1652 BG->Batches.append_back(&Cur->Batches); 1653 1654 if (BG->Batches.front()->getCount() == MaxCachedPerBatch) { 1655 // Only 1 non-full TransferBatch, push it to the front. 1656 BG->Batches.push_front(NonFullBatch); 1657 } else { 1658 const u16 NumBlocksToMove = static_cast<u16>( 1659 Min(static_cast<u16>(MaxCachedPerBatch - 1660 BG->Batches.front()->getCount()), 1661 NonFullBatchCount)); 1662 BG->Batches.front()->appendFromTransferBatch(NonFullBatch, 1663 NumBlocksToMove); 1664 if (NonFullBatch->isEmpty()) 1665 UnusedTransferBatch = NonFullBatch; 1666 else 1667 BG->Batches.push_front(NonFullBatch); 1668 } 1669 } 1670 1671 const u32 NeededSlots = UnusedTransferBatch == nullptr ? 1U : 2U; 1672 if (UNLIKELY(Idx + NeededSlots > MaxUnusedSize)) { 1673 ScopedLock L(BatchClassRegion->FLLock); 1674 pushBatchClassBlocks(BatchClassRegion, Blocks, Idx); 1675 if (conditionVariableEnabled()) 1676 BatchClassRegion->FLLockCV.notifyAll(BatchClassRegion->FLLock); 1677 Idx = 0; 1678 } 1679 Blocks[Idx++] = 1680 compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(Cur)); 1681 if (UnusedTransferBatch) { 1682 Blocks[Idx++] = 1683 compactPtr(SizeClassMap::BatchClassId, 1684 reinterpret_cast<uptr>(UnusedTransferBatch)); 1685 } 1686 Prev = BG; 1687 BG = BG->Next; 1688 continue; 1689 } 1690 1691 // At here, the `BG` is the first BatchGroup with CompactPtrGroupBase 1692 // larger than the first element in `GroupsToRelease`. We need to insert 1693 // `GroupsToRelease::front()` (which is `Cur` below) before `BG`. 1694 // 1695 // 1. If `Prev` is nullptr, we simply push `Cur` to the front of 1696 // FreeListInfo.BlockList. 1697 // 2. Otherwise, use `insert()` which inserts an element next to `Prev`. 1698 // 1699 // Afterwards, we don't need to advance `BG` because the order between 1700 // `BG` and the new `GroupsToRelease::front()` hasn't been checked. 1701 if (Prev == nullptr) 1702 Region->FreeListInfo.BlockList.push_front(Cur); 1703 else 1704 Region->FreeListInfo.BlockList.insert(Prev, Cur); 1705 DCHECK_EQ(Cur->Next, BG); 1706 Prev = Cur; 1707 } 1708 1709 if (Idx != 0) { 1710 ScopedLock L(BatchClassRegion->FLLock); 1711 pushBatchClassBlocks(BatchClassRegion, Blocks, Idx); 1712 if (conditionVariableEnabled()) 1713 BatchClassRegion->FLLockCV.notifyAll(BatchClassRegion->FLLock); 1714 } 1715 1716 if (SCUDO_DEBUG) { 1717 BatchGroupT *Prev = Region->FreeListInfo.BlockList.front(); 1718 for (BatchGroupT *Cur = Prev->Next; Cur != nullptr; 1719 Prev = Cur, Cur = Cur->Next) { 1720 CHECK_LT(Prev->CompactPtrGroupBase, Cur->CompactPtrGroupBase); 1721 } 1722 } 1723 1724 if (conditionVariableEnabled()) 1725 Region->FLLockCV.notifyAll(Region->FLLock); 1726 } 1727 1728 // The minimum size of pushed blocks that we will try to release the pages in 1729 // that size class. 1730 uptr SmallerBlockReleasePageDelta = 0; 1731 atomic_s32 ReleaseToOsIntervalMs = {}; 1732 alignas(SCUDO_CACHE_LINE_SIZE) RegionInfo RegionInfoArray[NumClasses]; 1733 }; 1734 1735 } // namespace scudo 1736 1737 #endif // SCUDO_PRIMARY64_H_ 1738