937 lines · c
1//===-- secondary.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_SECONDARY_H_10#define SCUDO_SECONDARY_H_11 12#include "chunk.h"13#include "common.h"14#include "list.h"15#include "mem_map.h"16#include "memtag.h"17#include "mutex.h"18#include "options.h"19#include "stats.h"20#include "string_utils.h"21#include "thread_annotations.h"22#include "tracing.h"23#include "vector.h"24 25namespace scudo {26 27// This allocator wraps the platform allocation primitives, and as such is on28// the slower side and should preferably be used for larger sized allocations.29// Blocks allocated will be preceded and followed by a guard page, and hold30// their own header that is not checksummed: the guard pages and the Combined31// header should be enough for our purpose.32 33namespace LargeBlock {34 35struct alignas(Max<uptr>(archSupportsMemoryTagging()36 ? archMemoryTagGranuleSize()37 : 1,38 1U << SCUDO_MIN_ALIGNMENT_LOG)) Header {39 LargeBlock::Header *Prev;40 LargeBlock::Header *Next;41 uptr CommitBase;42 uptr CommitSize;43 MemMapT MemMap;44};45 46static_assert(sizeof(Header) % (1U << SCUDO_MIN_ALIGNMENT_LOG) == 0, "");47static_assert(!archSupportsMemoryTagging() ||48 sizeof(Header) % archMemoryTagGranuleSize() == 0,49 "");50 51constexpr uptr getHeaderSize() { return sizeof(Header); }52 53template <typename Config> static uptr addHeaderTag(uptr Ptr) {54 if (allocatorSupportsMemoryTagging<Config>())55 return addFixedTag(Ptr, 1);56 return Ptr;57}58 59template <typename Config> static Header *getHeader(uptr Ptr) {60 return reinterpret_cast<Header *>(addHeaderTag<Config>(Ptr)) - 1;61}62 63template <typename Config> static Header *getHeader(const void *Ptr) {64 return getHeader<Config>(reinterpret_cast<uptr>(Ptr));65}66 67} // namespace LargeBlock68 69static inline void unmap(MemMapT &MemMap) { MemMap.unmap(); }70 71namespace {72 73struct CachedBlock {74 static constexpr u16 CacheIndexMax = UINT16_MAX;75 static constexpr u16 EndOfListVal = CacheIndexMax;76 77 // We allow a certain amount of fragmentation and part of the fragmented bytes78 // will be released by `releaseAndZeroPagesToOS()`. This increases the chance79 // of cache hit rate and reduces the overhead to the RSS at the same time. See80 // more details in the `MapAllocatorCache::retrieve()` section.81 //82 // We arrived at this default value after noticing that mapping in larger83 // memory regions performs better than releasing memory and forcing a cache84 // hit. According to the data, it suggests that beyond 4 pages, the release85 // execution time is longer than the map execution time. In this way,86 // the default is dependent on the platform.87 static constexpr uptr MaxReleasedCachePages = 4U;88 89 uptr CommitBase = 0;90 uptr CommitSize = 0;91 uptr BlockBegin = 0;92 MemMapT MemMap = {};93 u64 Time = 0;94 u16 Next = 0;95 u16 Prev = 0;96 97 bool isValid() { return CommitBase != 0; }98 99 void invalidate() { CommitBase = 0; }100};101} // namespace102 103template <typename Config> class MapAllocatorNoCache {104public:105 void init(UNUSED s32 ReleaseToOsInterval) {}106 CachedBlock retrieve(UNUSED uptr MaxAllowedFragmentedBytes, UNUSED uptr Size,107 UNUSED uptr Alignment, UNUSED uptr HeadersSize,108 UNUSED uptr &EntryHeaderPos) {109 return {};110 }111 void store(UNUSED Options Options, UNUSED uptr CommitBase,112 UNUSED uptr CommitSize, UNUSED uptr BlockBegin,113 UNUSED MemMapT MemMap) {114 // This should never be called since canCache always returns false.115 UNREACHABLE(116 "It is not valid to call store on MapAllocatorNoCache objects.");117 }118 119 bool canCache(UNUSED uptr Size) { return false; }120 void disable() {}121 void enable() {}122 void releaseToOS(ReleaseToOS) {}123 void disableMemoryTagging() {}124 void unmapTestOnly() {}125 bool setOption(Option O, UNUSED sptr Value) {126 if (O == Option::ReleaseInterval || O == Option::MaxCacheEntriesCount ||127 O == Option::MaxCacheEntrySize)128 return false;129 // Not supported by the Secondary Cache, but not an error either.130 return true;131 }132 133 void getStats(UNUSED ScopedString *Str) {134 Str->append("Secondary Cache Disabled\n");135 }136};137 138static const uptr MaxUnreleasedCachePages = 4U;139 140template <typename Config>141bool mapSecondary(const Options &Options, uptr CommitBase, uptr CommitSize,142 uptr AllocPos, uptr Flags, MemMapT &MemMap) {143 Flags |= MAP_RESIZABLE;144 Flags |= MAP_ALLOWNOMEM;145 146 const uptr PageSize = getPageSizeCached();147 if (SCUDO_TRUSTY) {148 /*149 * On Trusty we need AllocPos to be usable for shared memory, which cannot150 * cross multiple mappings. This means we need to split around AllocPos151 * and not over it. We can only do this if the address is page-aligned.152 */153 const uptr TaggedSize = AllocPos - CommitBase;154 if (useMemoryTagging<Config>(Options) && isAligned(TaggedSize, PageSize)) {155 DCHECK_GT(TaggedSize, 0);156 return MemMap.remap(CommitBase, TaggedSize, "scudo:secondary",157 MAP_MEMTAG | Flags) &&158 MemMap.remap(AllocPos, CommitSize - TaggedSize, "scudo:secondary",159 Flags);160 } else {161 const uptr RemapFlags =162 (useMemoryTagging<Config>(Options) ? MAP_MEMTAG : 0) | Flags;163 return MemMap.remap(CommitBase, CommitSize, "scudo:secondary",164 RemapFlags);165 }166 }167 168 const uptr MaxUnreleasedCacheBytes = MaxUnreleasedCachePages * PageSize;169 if (useMemoryTagging<Config>(Options) &&170 CommitSize > MaxUnreleasedCacheBytes) {171 const uptr UntaggedPos =172 Max(AllocPos, CommitBase + MaxUnreleasedCacheBytes);173 return MemMap.remap(CommitBase, UntaggedPos - CommitBase, "scudo:secondary",174 MAP_MEMTAG | Flags) &&175 MemMap.remap(UntaggedPos, CommitBase + CommitSize - UntaggedPos,176 "scudo:secondary", Flags);177 } else {178 const uptr RemapFlags =179 (useMemoryTagging<Config>(Options) ? MAP_MEMTAG : 0) | Flags;180 return MemMap.remap(CommitBase, CommitSize, "scudo:secondary", RemapFlags);181 }182}183 184// Template specialization to avoid producing zero-length array185template <typename T, size_t Size> class NonZeroLengthArray {186public:187 T &operator[](uptr Idx) { return values[Idx]; }188 189private:190 T values[Size];191};192template <typename T> class NonZeroLengthArray<T, 0> {193public:194 T &operator[](uptr UNUSED Idx) { UNREACHABLE("Unsupported!"); }195};196 197// The default unmap callback is simply scudo::unmap.198// In testing, a different unmap callback is used to199// record information about unmaps in the cache200template <typename Config, void (*unmapCallBack)(MemMapT &) = unmap>201class MapAllocatorCache {202public:203 void getStats(ScopedString *Str) {204 ScopedLock L(Mutex);205 uptr Integral;206 uptr Fractional;207 computePercentage(SuccessfulRetrieves, CallsToRetrieve, &Integral,208 &Fractional);209 const s32 Interval = atomic_load_relaxed(&ReleaseToOsIntervalMs);210 Str->append("Stats: MapAllocatorCache: EntriesCount: %zu, "211 "MaxEntriesCount: %u, MaxEntrySize: %zu, ReleaseToOsSkips: "212 "%zu, ReleaseToOsIntervalMs = %d\n",213 LRUEntries.size(), atomic_load_relaxed(&MaxEntriesCount),214 atomic_load_relaxed(&MaxEntrySize),215 atomic_load_relaxed(&ReleaseToOsSkips),216 Interval >= 0 ? Interval : -1);217 Str->append("Stats: CacheRetrievalStats: SuccessRate: %u/%u "218 "(%zu.%02zu%%)\n",219 SuccessfulRetrieves, CallsToRetrieve, Integral, Fractional);220 Str->append("Cache Entry Info (Most Recent -> Least Recent):\n");221 222 for (CachedBlock &Entry : LRUEntries) {223 Str->append(" StartBlockAddress: 0x%zx, EndBlockAddress: 0x%zx, "224 "BlockSize: %zu %s\n",225 Entry.CommitBase, Entry.CommitBase + Entry.CommitSize,226 Entry.CommitSize, Entry.Time == 0 ? "[R]" : "");227 }228 }229 230 // Ensure the default maximum specified fits the array.231 static_assert(Config::getDefaultMaxEntriesCount() <=232 Config::getEntriesArraySize(),233 "");234 // Ensure the cache entry array size fits in the LRU list Next and Prev235 // index fields236 static_assert(Config::getEntriesArraySize() <= CachedBlock::CacheIndexMax,237 "Cache entry array is too large to be indexed.");238 239 void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS {240 DCHECK_EQ(LRUEntries.size(), 0U);241 setOption(Option::MaxCacheEntriesCount,242 static_cast<sptr>(Config::getDefaultMaxEntriesCount()));243 setOption(Option::MaxCacheEntrySize,244 static_cast<sptr>(Config::getDefaultMaxEntrySize()));245 // The default value in the cache config has the higher priority.246 if (Config::getDefaultReleaseToOsIntervalMs() != INT32_MIN)247 ReleaseToOsInterval = Config::getDefaultReleaseToOsIntervalMs();248 setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval));249 250 LRUEntries.clear();251 LRUEntries.init(Entries, sizeof(Entries));252 OldestPresentEntry = nullptr;253 254 AvailEntries.clear();255 AvailEntries.init(Entries, sizeof(Entries));256 for (u32 I = 0; I < Config::getEntriesArraySize(); I++)257 AvailEntries.push_back(&Entries[I]);258 }259 260 void store(const Options &Options, uptr CommitBase, uptr CommitSize,261 uptr BlockBegin, MemMapT MemMap) EXCLUDES(Mutex) {262 DCHECK(canCache(CommitSize));263 264 const s32 Interval = atomic_load_relaxed(&ReleaseToOsIntervalMs);265 u64 Time;266 CachedBlock Entry;267 268 Entry.CommitBase = CommitBase;269 Entry.CommitSize = CommitSize;270 Entry.BlockBegin = BlockBegin;271 Entry.MemMap = MemMap;272 Entry.Time = UINT64_MAX;273 274 bool MemoryTaggingEnabled = useMemoryTagging<Config>(Options);275 if (MemoryTaggingEnabled) {276 if (Interval == 0 && !SCUDO_FUCHSIA) {277 // Release the memory and make it inaccessible at the same time by278 // creating a new MAP_NOACCESS mapping on top of the existing mapping.279 // Fuchsia does not support replacing mappings by creating a new mapping280 // on top so we just do the two syscalls there.281 Entry.Time = 0;282 mapSecondary<Config>(Options, Entry.CommitBase, Entry.CommitSize,283 Entry.CommitBase, MAP_NOACCESS, Entry.MemMap);284 } else {285 Entry.MemMap.setMemoryPermission(Entry.CommitBase, Entry.CommitSize,286 MAP_NOACCESS);287 }288 }289 290 // Usually only one entry will be evicted from the cache.291 // Only in the rare event that the cache shrinks in real-time292 // due to a decrease in the configurable value MaxEntriesCount293 // will more than one cache entry be evicted.294 // The vector is used to save the MemMaps of evicted entries so295 // that the unmap call can be performed outside the lock296 Vector<MemMapT, 1U> EvictionMemMaps;297 298 do {299 ScopedLock L(Mutex);300 301 // Time must be computed under the lock to ensure302 // that the LRU cache remains sorted with respect to303 // time in a multithreaded environment304 Time = getMonotonicTimeFast();305 if (Entry.Time != 0)306 Entry.Time = Time;307 308 if (MemoryTaggingEnabled && !useMemoryTagging<Config>(Options)) {309 // If we get here then memory tagging was disabled in between when we310 // read Options and when we locked Mutex. We can't insert our entry into311 // the quarantine or the cache because the permissions would be wrong so312 // just unmap it.313 unmapCallBack(Entry.MemMap);314 break;315 }316 317 if (!Config::getQuarantineDisabled() && Config::getQuarantineSize()) {318 QuarantinePos =319 (QuarantinePos + 1) % Max(Config::getQuarantineSize(), 1u);320 if (!Quarantine[QuarantinePos].isValid()) {321 Quarantine[QuarantinePos] = Entry;322 return;323 }324 CachedBlock PrevEntry = Quarantine[QuarantinePos];325 Quarantine[QuarantinePos] = Entry;326 Entry = PrevEntry;327 }328 329 // All excess entries are evicted from the cache. Note that when330 // `MaxEntriesCount` is zero, cache storing shouldn't happen and it's331 // guarded by the `DCHECK(canCache(CommitSize))` above. As a result, we332 // won't try to pop `LRUEntries` when it's empty.333 while (LRUEntries.size() >= atomic_load_relaxed(&MaxEntriesCount)) {334 // Save MemMaps of evicted entries to perform unmap outside of lock335 CachedBlock *Entry = LRUEntries.back();336 EvictionMemMaps.push_back(Entry->MemMap);337 remove(Entry);338 }339 340 insert(Entry);341 } while (0);342 343 for (MemMapT &EvictMemMap : EvictionMemMaps)344 unmapCallBack(EvictMemMap);345 346 if (Interval >= 0) {347 // It is very likely that multiple threads trying to do a release at the348 // same time will not actually release any extra elements. Therefore,349 // let any other thread continue, skipping the release.350 if (Mutex.tryLock()) {351 SCUDO_SCOPED_TRACE(352 GetSecondaryReleaseToOSTraceName(ReleaseToOS::Normal));353 354 releaseOlderThan(Time - static_cast<u64>(Interval) * 1000000);355 Mutex.unlock();356 } else357 atomic_fetch_add(&ReleaseToOsSkips, 1U, memory_order_relaxed);358 }359 }360 361 CachedBlock retrieve(uptr MaxAllowedFragmentedPages, uptr Size,362 uptr Alignment, uptr HeadersSize, uptr &EntryHeaderPos)363 EXCLUDES(Mutex) {364 const uptr PageSize = getPageSizeCached();365 // 10% of the requested size proved to be the optimal choice for366 // retrieving cached blocks after testing several options.367 constexpr u32 FragmentedBytesDivisor = 10;368 CachedBlock Entry;369 EntryHeaderPos = 0;370 {371 ScopedLock L(Mutex);372 CallsToRetrieve++;373 if (LRUEntries.size() == 0)374 return {};375 CachedBlock *RetrievedEntry = nullptr;376 uptr MinDiff = UINTPTR_MAX;377 378 // Since allocation sizes don't always match cached memory chunk sizes379 // we allow some memory to be unused (called fragmented bytes). The380 // amount of unused bytes is exactly EntryHeaderPos - CommitBase.381 //382 // CommitBase CommitBase + CommitSize383 // V V384 // +---+------------+-----------------+---+385 // | | | | |386 // +---+------------+-----------------+---+387 // ^ ^ ^388 // Guard EntryHeaderPos Guard-page-end389 // page-begin390 //391 // [EntryHeaderPos, CommitBase + CommitSize) contains the user data as392 // well as the header metadata. If EntryHeaderPos - CommitBase exceeds393 // MaxAllowedFragmentedPages * PageSize, the cached memory chunk is394 // not considered valid for retrieval.395 for (CachedBlock &Entry : LRUEntries) {396 const uptr CommitBase = Entry.CommitBase;397 const uptr CommitSize = Entry.CommitSize;398 const uptr AllocPos =399 roundDown(CommitBase + CommitSize - Size, Alignment);400 const uptr HeaderPos = AllocPos - HeadersSize;401 const uptr MaxAllowedFragmentedBytes =402 MaxAllowedFragmentedPages * PageSize;403 if (HeaderPos > CommitBase + CommitSize)404 continue;405 // TODO: Remove AllocPos > CommitBase + MaxAllowedFragmentedBytes406 // and replace with Diff > MaxAllowedFragmentedBytes407 if (HeaderPos < CommitBase ||408 AllocPos > CommitBase + MaxAllowedFragmentedBytes) {409 continue;410 }411 412 const uptr Diff = roundDown(HeaderPos, PageSize) - CommitBase;413 414 // Keep track of the smallest cached block415 // that is greater than (AllocSize + HeaderSize)416 if (Diff >= MinDiff)417 continue;418 419 MinDiff = Diff;420 RetrievedEntry = &Entry;421 EntryHeaderPos = HeaderPos;422 423 // Immediately use a cached block if its size is close enough to the424 // requested size425 const uptr OptimalFitThesholdBytes =426 (CommitBase + CommitSize - HeaderPos) / FragmentedBytesDivisor;427 if (Diff <= OptimalFitThesholdBytes)428 break;429 }430 431 if (RetrievedEntry != nullptr) {432 Entry = *RetrievedEntry;433 remove(RetrievedEntry);434 SuccessfulRetrieves++;435 }436 }437 438 // The difference between the retrieved memory chunk and the request439 // size is at most MaxAllowedFragmentedPages440 //441 // +- MaxAllowedFragmentedPages * PageSize -+442 // +--------------------------+-------------+443 // | | |444 // +--------------------------+-------------+445 // \ Bytes to be released / ^446 // |447 // (may or may not be committed)448 //449 // The maximum number of bytes released to the OS is capped by450 // MaxReleasedCachePages451 //452 // TODO : Consider making MaxReleasedCachePages configurable since453 // the release to OS API can vary across systems.454 if (Entry.Time != 0) {455 const uptr FragmentedBytes =456 roundDown(EntryHeaderPos, PageSize) - Entry.CommitBase;457 const uptr MaxUnreleasedCacheBytes = MaxUnreleasedCachePages * PageSize;458 if (FragmentedBytes > MaxUnreleasedCacheBytes) {459 const uptr MaxReleasedCacheBytes =460 CachedBlock::MaxReleasedCachePages * PageSize;461 uptr BytesToRelease =462 roundUp(Min<uptr>(MaxReleasedCacheBytes,463 FragmentedBytes - MaxUnreleasedCacheBytes),464 PageSize);465 Entry.MemMap.releaseAndZeroPagesToOS(Entry.CommitBase, BytesToRelease);466 }467 }468 469 return Entry;470 }471 472 bool canCache(uptr Size) {473 return atomic_load_relaxed(&MaxEntriesCount) != 0U &&474 Size <= atomic_load_relaxed(&MaxEntrySize);475 }476 477 bool setOption(Option O, sptr Value) {478 if (O == Option::ReleaseInterval) {479 const s32 Interval = Max(480 Min(static_cast<s32>(Value), Config::getMaxReleaseToOsIntervalMs()),481 Config::getMinReleaseToOsIntervalMs());482 atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval);483 return true;484 }485 if (O == Option::MaxCacheEntriesCount) {486 if (Value < 0)487 return false;488 atomic_store_relaxed(489 &MaxEntriesCount,490 Min<u32>(static_cast<u32>(Value), Config::getEntriesArraySize()));491 return true;492 }493 if (O == Option::MaxCacheEntrySize) {494 atomic_store_relaxed(&MaxEntrySize, static_cast<uptr>(Value));495 return true;496 }497 // Not supported by the Secondary Cache, but not an error either.498 return true;499 }500 501 void releaseToOS([[maybe_unused]] ReleaseToOS ReleaseType) EXCLUDES(Mutex) {502 SCUDO_SCOPED_TRACE(GetSecondaryReleaseToOSTraceName(ReleaseType));503 504 // Since this is a request to release everything, always wait for the505 // lock so that we guarantee all entries are released after this call.506 ScopedLock L(Mutex);507 releaseOlderThan(UINT64_MAX);508 }509 510 void disableMemoryTagging() EXCLUDES(Mutex) {511 ScopedLock L(Mutex);512 if (!Config::getQuarantineDisabled()) {513 for (u32 I = 0; I != Config::getQuarantineSize(); ++I) {514 if (Quarantine[I].isValid()) {515 MemMapT &MemMap = Quarantine[I].MemMap;516 unmapCallBack(MemMap);517 Quarantine[I].invalidate();518 }519 }520 QuarantinePos = -1U;521 }522 523 for (CachedBlock &Entry : LRUEntries)524 Entry.MemMap.setMemoryPermission(Entry.CommitBase, Entry.CommitSize, 0);525 }526 527 void disable() NO_THREAD_SAFETY_ANALYSIS { Mutex.lock(); }528 529 void enable() NO_THREAD_SAFETY_ANALYSIS { Mutex.unlock(); }530 531 void unmapTestOnly() { empty(); }532 533 void releaseOlderThanTestOnly(u64 ReleaseTime) {534 ScopedLock L(Mutex);535 releaseOlderThan(ReleaseTime);536 }537 538private:539 void insert(const CachedBlock &Entry) REQUIRES(Mutex) {540 CachedBlock *AvailEntry = AvailEntries.front();541 AvailEntries.pop_front();542 543 *AvailEntry = Entry;544 LRUEntries.push_front(AvailEntry);545 if (OldestPresentEntry == nullptr && AvailEntry->Time != 0)546 OldestPresentEntry = AvailEntry;547 }548 549 void remove(CachedBlock *Entry) REQUIRES(Mutex) {550 DCHECK(Entry->isValid());551 if (OldestPresentEntry == Entry) {552 OldestPresentEntry = LRUEntries.getPrev(Entry);553 DCHECK(OldestPresentEntry == nullptr || OldestPresentEntry->Time != 0);554 }555 LRUEntries.remove(Entry);556 Entry->invalidate();557 AvailEntries.push_front(Entry);558 }559 560 void empty() {561 MemMapT MapInfo[Config::getEntriesArraySize()];562 uptr N = 0;563 {564 ScopedLock L(Mutex);565 566 for (CachedBlock &Entry : LRUEntries)567 MapInfo[N++] = Entry.MemMap;568 LRUEntries.clear();569 OldestPresentEntry = nullptr;570 }571 for (uptr I = 0; I < N; I++) {572 MemMapT &MemMap = MapInfo[I];573 unmapCallBack(MemMap);574 }575 }576 577 void releaseOlderThan(u64 ReleaseTime) REQUIRES(Mutex) {578 SCUDO_SCOPED_TRACE(GetSecondaryReleaseOlderThanTraceName());579 580 if (!Config::getQuarantineDisabled()) {581 for (uptr I = 0; I < Config::getQuarantineSize(); I++) {582 auto &Entry = Quarantine[I];583 if (!Entry.isValid() || Entry.Time == 0 || Entry.Time > ReleaseTime)584 continue;585 Entry.MemMap.releaseAndZeroPagesToOS(Entry.CommitBase,586 Entry.CommitSize);587 Entry.Time = 0;588 }589 }590 591 for (CachedBlock *Entry = OldestPresentEntry; Entry != nullptr;592 Entry = LRUEntries.getPrev(Entry)) {593 DCHECK(Entry->isValid());594 DCHECK(Entry->Time != 0);595 596 if (Entry->Time > ReleaseTime) {597 // All entries are newer than this, so no need to keep scanning.598 OldestPresentEntry = Entry;599 return;600 }601 602 Entry->MemMap.releaseAndZeroPagesToOS(Entry->CommitBase,603 Entry->CommitSize);604 Entry->Time = 0;605 }606 OldestPresentEntry = nullptr;607 }608 609 HybridMutex Mutex;610 u32 QuarantinePos GUARDED_BY(Mutex) = 0;611 atomic_u32 MaxEntriesCount = {};612 atomic_uptr MaxEntrySize = {};613 atomic_s32 ReleaseToOsIntervalMs = {};614 u32 CallsToRetrieve GUARDED_BY(Mutex) = 0;615 u32 SuccessfulRetrieves GUARDED_BY(Mutex) = 0;616 atomic_uptr ReleaseToOsSkips = {};617 618 CachedBlock Entries[Config::getEntriesArraySize()] GUARDED_BY(Mutex) = {};619 NonZeroLengthArray<CachedBlock, Config::getQuarantineSize()>620 Quarantine GUARDED_BY(Mutex) = {};621 622 // The oldest entry in the LRUEntries that has Time non-zero.623 CachedBlock *OldestPresentEntry GUARDED_BY(Mutex) = nullptr;624 // Cached blocks stored in LRU order625 DoublyLinkedList<CachedBlock> LRUEntries GUARDED_BY(Mutex);626 // The unused Entries627 SinglyLinkedList<CachedBlock> AvailEntries GUARDED_BY(Mutex);628};629 630template <typename Config> class MapAllocator {631public:632 void init(GlobalStats *S,633 s32 ReleaseToOsInterval = -1) NO_THREAD_SAFETY_ANALYSIS {634 DCHECK_EQ(AllocatedBytes, 0U);635 DCHECK_EQ(FreedBytes, 0U);636 Cache.init(ReleaseToOsInterval);637 Stats.init();638 if (LIKELY(S))639 S->link(&Stats);640 }641 642 void *allocate(const Options &Options, uptr Size, uptr AlignmentHint = 0,643 uptr *BlockEnd = nullptr,644 FillContentsMode FillContents = NoFill);645 646 void deallocate(const Options &Options, void *Ptr);647 648 void *tryAllocateFromCache(const Options &Options, uptr Size, uptr Alignment,649 uptr *BlockEndPtr, FillContentsMode FillContents);650 651 static uptr getBlockEnd(void *Ptr) {652 auto *B = LargeBlock::getHeader<Config>(Ptr);653 return B->CommitBase + B->CommitSize;654 }655 656 static uptr getBlockSize(void *Ptr) {657 return getBlockEnd(Ptr) - reinterpret_cast<uptr>(Ptr);658 }659 660 static uptr getGuardPageSize() {661 if (Config::getEnableGuardPages())662 return getPageSizeCached();663 return 0U;664 }665 666 static constexpr uptr getHeadersSize() {667 return Chunk::getHeaderSize() + LargeBlock::getHeaderSize();668 }669 670 void disable() NO_THREAD_SAFETY_ANALYSIS {671 Mutex.lock();672 Cache.disable();673 }674 675 void enable() NO_THREAD_SAFETY_ANALYSIS {676 Cache.enable();677 Mutex.unlock();678 }679 680 template <typename F> void iterateOverBlocks(F Callback) const {681 Mutex.assertHeld();682 683 for (const auto &H : InUseBlocks) {684 uptr Ptr = reinterpret_cast<uptr>(&H) + LargeBlock::getHeaderSize();685 if (allocatorSupportsMemoryTagging<Config>())686 Ptr = untagPointer(Ptr);687 Callback(Ptr);688 }689 }690 691 bool canCache(uptr Size) { return Cache.canCache(Size); }692 693 bool setOption(Option O, sptr Value) { return Cache.setOption(O, Value); }694 695 void releaseToOS(ReleaseToOS ReleaseType) { Cache.releaseToOS(ReleaseType); }696 697 void disableMemoryTagging() { Cache.disableMemoryTagging(); }698 699 void unmapTestOnly() { Cache.unmapTestOnly(); }700 701 void getStats(ScopedString *Str);702 703private:704 typename Config::template CacheT<typename Config::CacheConfig> Cache;705 706 mutable HybridMutex Mutex;707 DoublyLinkedList<LargeBlock::Header> InUseBlocks GUARDED_BY(Mutex);708 uptr AllocatedBytes GUARDED_BY(Mutex) = 0;709 uptr FreedBytes GUARDED_BY(Mutex) = 0;710 uptr FragmentedBytes GUARDED_BY(Mutex) = 0;711 uptr LargestSize GUARDED_BY(Mutex) = 0;712 u32 NumberOfAllocs GUARDED_BY(Mutex) = 0;713 u32 NumberOfFrees GUARDED_BY(Mutex) = 0;714 LocalStats Stats GUARDED_BY(Mutex);715};716 717template <typename Config>718void *719MapAllocator<Config>::tryAllocateFromCache(const Options &Options, uptr Size,720 uptr Alignment, uptr *BlockEndPtr,721 FillContentsMode FillContents) {722 CachedBlock Entry;723 uptr EntryHeaderPos;724 uptr MaxAllowedFragmentedPages = MaxUnreleasedCachePages;725 726 if (LIKELY(!useMemoryTagging<Config>(Options))) {727 MaxAllowedFragmentedPages += CachedBlock::MaxReleasedCachePages;728 } else {729 // TODO: Enable MaxReleasedCachePages may result in pages for an entry being730 // partially released and it erases the tag of those pages as well. To731 // support this feature for MTE, we need to tag those pages again.732 DCHECK_EQ(MaxAllowedFragmentedPages, MaxUnreleasedCachePages);733 }734 735 Entry = Cache.retrieve(MaxAllowedFragmentedPages, Size, Alignment,736 getHeadersSize(), EntryHeaderPos);737 if (!Entry.isValid())738 return nullptr;739 740 LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>(741 LargeBlock::addHeaderTag<Config>(EntryHeaderPos));742 bool Zeroed = Entry.Time == 0;743 if (useMemoryTagging<Config>(Options)) {744 uptr NewBlockBegin = reinterpret_cast<uptr>(H + 1);745 Entry.MemMap.setMemoryPermission(Entry.CommitBase, Entry.CommitSize, 0);746 if (Zeroed) {747 storeTags(LargeBlock::addHeaderTag<Config>(Entry.CommitBase),748 NewBlockBegin);749 } else if (Entry.BlockBegin < NewBlockBegin) {750 storeTags(Entry.BlockBegin, NewBlockBegin);751 } else {752 storeTags(untagPointer(NewBlockBegin), untagPointer(Entry.BlockBegin));753 }754 }755 756 H->CommitBase = Entry.CommitBase;757 H->CommitSize = Entry.CommitSize;758 H->MemMap = Entry.MemMap;759 760 const uptr BlockEnd = H->CommitBase + H->CommitSize;761 if (BlockEndPtr)762 *BlockEndPtr = BlockEnd;763 uptr HInt = reinterpret_cast<uptr>(H);764 if (allocatorSupportsMemoryTagging<Config>())765 HInt = untagPointer(HInt);766 const uptr PtrInt = HInt + LargeBlock::getHeaderSize();767 void *Ptr = reinterpret_cast<void *>(PtrInt);768 if (FillContents && !Zeroed)769 memset(Ptr, FillContents == ZeroFill ? 0 : PatternFillByte,770 BlockEnd - PtrInt);771 {772 ScopedLock L(Mutex);773 InUseBlocks.push_back(H);774 AllocatedBytes += H->CommitSize;775 FragmentedBytes += H->MemMap.getCapacity() - H->CommitSize;776 NumberOfAllocs++;777 Stats.add(StatAllocated, H->CommitSize);778 Stats.add(StatMapped, H->MemMap.getCapacity());779 }780 return Ptr;781}782// As with the Primary, the size passed to this function includes any desired783// alignment, so that the frontend can align the user allocation. The hint784// parameter allows us to unmap spurious memory when dealing with larger785// (greater than a page) alignments on 32-bit platforms.786// Due to the sparsity of address space available on those platforms, requesting787// an allocation from the Secondary with a large alignment would end up wasting788// VA space (even though we are not committing the whole thing), hence the need789// to trim off some of the reserved space.790// For allocations requested with an alignment greater than or equal to a page,791// the committed memory will amount to something close to Size - AlignmentHint792// (pending rounding and headers).793template <typename Config>794void *MapAllocator<Config>::allocate(const Options &Options, uptr Size,795 uptr Alignment, uptr *BlockEndPtr,796 FillContentsMode FillContents) {797 if (Options.get(OptionBit::AddLargeAllocationSlack))798 Size += 1UL << SCUDO_MIN_ALIGNMENT_LOG;799 Alignment = Max(Alignment, uptr(1U) << SCUDO_MIN_ALIGNMENT_LOG);800 const uptr PageSize = getPageSizeCached();801 802 // Note that cached blocks may have aligned address already. Thus we simply803 // pass the required size (`Size` + `getHeadersSize()`) to do cache look up.804 const uptr MinNeededSizeForCache = roundUp(Size + getHeadersSize(), PageSize);805 806 if (Alignment < PageSize && Cache.canCache(MinNeededSizeForCache)) {807 void *Ptr = tryAllocateFromCache(Options, Size, Alignment, BlockEndPtr,808 FillContents);809 if (Ptr != nullptr)810 return Ptr;811 }812 813 uptr RoundedSize =814 roundUp(roundUp(Size, Alignment) + getHeadersSize(), PageSize);815 if (UNLIKELY(Alignment > PageSize))816 RoundedSize += Alignment - PageSize;817 818 ReservedMemoryT ReservedMemory;819 const uptr MapSize = RoundedSize + 2 * getGuardPageSize();820 if (UNLIKELY(!ReservedMemory.create(/*Addr=*/0U, MapSize, nullptr,821 MAP_ALLOWNOMEM))) {822 return nullptr;823 }824 825 // Take the entire ownership of reserved region.826 MemMapT MemMap = ReservedMemory.dispatch(ReservedMemory.getBase(),827 ReservedMemory.getCapacity());828 uptr MapBase = MemMap.getBase();829 uptr CommitBase = MapBase + getGuardPageSize();830 uptr MapEnd = MapBase + MapSize;831 832 // In the unlikely event of alignments larger than a page, adjust the amount833 // of memory we want to commit, and trim the extra memory.834 if (UNLIKELY(Alignment >= PageSize)) {835 // For alignments greater than or equal to a page, the user pointer (eg:836 // the pointer that is returned by the C or C++ allocation APIs) ends up837 // on a page boundary , and our headers will live in the preceding page.838 CommitBase =839 roundUp(MapBase + getGuardPageSize() + 1, Alignment) - PageSize;840 // We only trim the extra memory on 32-bit platforms: 64-bit platforms841 // are less constrained memory wise, and that saves us two syscalls.842 if (SCUDO_WORDSIZE == 32U) {843 const uptr NewMapBase = CommitBase - getGuardPageSize();844 DCHECK_GE(NewMapBase, MapBase);845 if (NewMapBase != MapBase) {846 MemMap.unmap(MapBase, NewMapBase - MapBase);847 MapBase = NewMapBase;848 }849 // CommitBase is past the first guard page, but this computation needs850 // to include a page where the header lives.851 const uptr NewMapEnd =852 CommitBase + PageSize + roundUp(Size, PageSize) + getGuardPageSize();853 DCHECK_LE(NewMapEnd, MapEnd);854 if (NewMapEnd != MapEnd) {855 MemMap.unmap(NewMapEnd, MapEnd - NewMapEnd);856 MapEnd = NewMapEnd;857 }858 }859 }860 861 const uptr CommitSize = MapEnd - getGuardPageSize() - CommitBase;862 const uptr AllocPos = roundDown(CommitBase + CommitSize - Size, Alignment);863 if (!mapSecondary<Config>(Options, CommitBase, CommitSize, AllocPos, 0,864 MemMap)) {865 unmap(MemMap);866 return nullptr;867 }868 const uptr HeaderPos = AllocPos - getHeadersSize();869 // Make sure that the header is not in the guard page or before the base.870 DCHECK_GE(HeaderPos, MapBase + getGuardPageSize());871 LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>(872 LargeBlock::addHeaderTag<Config>(HeaderPos));873 if (useMemoryTagging<Config>(Options))874 storeTags(LargeBlock::addHeaderTag<Config>(CommitBase),875 reinterpret_cast<uptr>(H + 1));876 H->CommitBase = CommitBase;877 H->CommitSize = CommitSize;878 H->MemMap = MemMap;879 if (BlockEndPtr)880 *BlockEndPtr = CommitBase + CommitSize;881 {882 ScopedLock L(Mutex);883 InUseBlocks.push_back(H);884 AllocatedBytes += CommitSize;885 FragmentedBytes += H->MemMap.getCapacity() - CommitSize;886 if (LargestSize < CommitSize)887 LargestSize = CommitSize;888 NumberOfAllocs++;889 Stats.add(StatAllocated, CommitSize);890 Stats.add(StatMapped, H->MemMap.getCapacity());891 }892 return reinterpret_cast<void *>(HeaderPos + LargeBlock::getHeaderSize());893}894 895template <typename Config>896void MapAllocator<Config>::deallocate(const Options &Options, void *Ptr)897 EXCLUDES(Mutex) {898 LargeBlock::Header *H = LargeBlock::getHeader<Config>(Ptr);899 const uptr CommitSize = H->CommitSize;900 {901 ScopedLock L(Mutex);902 InUseBlocks.remove(H);903 FreedBytes += CommitSize;904 FragmentedBytes -= H->MemMap.getCapacity() - CommitSize;905 NumberOfFrees++;906 Stats.sub(StatAllocated, CommitSize);907 Stats.sub(StatMapped, H->MemMap.getCapacity());908 }909 910 if (Cache.canCache(H->CommitSize)) {911 Cache.store(Options, H->CommitBase, H->CommitSize,912 reinterpret_cast<uptr>(H + 1), H->MemMap);913 } else {914 // Note that the `H->MemMap` is stored on the pages managed by itself. Take915 // over the ownership before unmap() so that any operation along with916 // unmap() won't touch inaccessible pages.917 MemMapT MemMap = H->MemMap;918 unmap(MemMap);919 }920}921 922template <typename Config>923void MapAllocator<Config>::getStats(ScopedString *Str) EXCLUDES(Mutex) {924 ScopedLock L(Mutex);925 Str->append("Stats: MapAllocator: allocated %u times (%zuK), freed %u times "926 "(%zuK), remains %u (%zuK) max %zuM, Fragmented %zuK\n",927 NumberOfAllocs, AllocatedBytes >> 10, NumberOfFrees,928 FreedBytes >> 10, NumberOfAllocs - NumberOfFrees,929 (AllocatedBytes - FreedBytes) >> 10, LargestSize >> 20,930 FragmentedBytes >> 10);931 Cache.getStats(Str);932}933 934} // namespace scudo935 936#endif // SCUDO_SECONDARY_H_937