714 lines · c
1//===-- release.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_RELEASE_H_10#define SCUDO_RELEASE_H_11 12#include "common.h"13#include "list.h"14#include "mem_map.h"15#include "mutex.h"16#include "thread_annotations.h"17 18namespace scudo {19 20template <typename MemMapT> class RegionReleaseRecorder {21public:22 RegionReleaseRecorder(MemMapT *RegionMemMap, uptr Base, uptr Offset = 0)23 : RegionMemMap(RegionMemMap), Base(Base), Offset(Offset) {}24 25 uptr getReleasedBytes() const { return ReleasedBytes; }26 27 uptr getBase() const { return Base; }28 29 // Releases [From, To) range of pages back to OS. Note that `From` and `To`30 // are offseted from `Base` + Offset.31 void releasePageRangeToOS(uptr From, uptr To) {32 const uptr Size = To - From;33 RegionMemMap->releasePagesToOS(getBase() + Offset + From, Size);34 ReleasedBytes += Size;35 }36 37private:38 uptr ReleasedBytes = 0;39 MemMapT *RegionMemMap = nullptr;40 uptr Base = 0;41 // The release offset from Base. This is used when we know a given range after42 // Base will not be released.43 uptr Offset = 0;44};45 46class ReleaseRecorder {47public:48 ReleaseRecorder(uptr Base, uptr Offset = 0, MapPlatformData *Data = nullptr)49 : Base(Base), Offset(Offset), Data(Data) {}50 51 uptr getReleasedBytes() const { return ReleasedBytes; }52 53 uptr getBase() const { return Base; }54 55 // Releases [From, To) range of pages back to OS.56 void releasePageRangeToOS(uptr From, uptr To) {57 const uptr Size = To - From;58 releasePagesToOS(Base, From + Offset, Size, Data);59 ReleasedBytes += Size;60 }61 62private:63 uptr ReleasedBytes = 0;64 // The starting address to release. Note that we may want to combine (Base +65 // Offset) as a new Base. However, the Base is retrieved from66 // `MapPlatformData` on Fuchsia, which means the offset won't be aware.67 // Therefore, store them separately to make it work on all the platforms.68 uptr Base = 0;69 // The release offset from Base. This is used when we know a given range after70 // Base will not be released.71 uptr Offset = 0;72 MapPlatformData *Data = nullptr;73};74 75class FragmentationRecorder {76public:77 FragmentationRecorder() = default;78 79 uptr getReleasedPagesCount() const { return ReleasedPagesCount; }80 81 void releasePageRangeToOS(uptr From, uptr To) {82 DCHECK_EQ((To - From) % getPageSizeCached(), 0U);83 ReleasedPagesCount += (To - From) >> getPageSizeLogCached();84 }85 86private:87 uptr ReleasedPagesCount = 0;88};89 90template <uptr GroupSize, uptr NumGroups>91class MemoryGroupFragmentationRecorder {92public:93 const uptr NumPagesInOneGroup = GroupSize / getPageSizeCached();94 95 void releasePageRangeToOS(uptr From, uptr To) {96 for (uptr I = From / getPageSizeCached(); I < To / getPageSizeCached(); ++I)97 ++FreePagesCount[I / NumPagesInOneGroup];98 }99 100 uptr getNumFreePages(uptr GroupId) { return FreePagesCount[GroupId]; }101 102private:103 uptr FreePagesCount[NumGroups] = {};104};105 106// A buffer pool which holds a fixed number of static buffers of `uptr` elements107// for fast buffer allocation. If the request size is greater than108// `StaticBufferNumElements` or if all the static buffers are in use, it'll109// delegate the allocation to map().110template <uptr StaticBufferCount, uptr StaticBufferNumElements>111class BufferPool {112public:113 // Preserve 1 bit in the `Mask` so that we don't need to do zero-check while114 // extracting the least significant bit from the `Mask`.115 static_assert(StaticBufferCount < SCUDO_WORDSIZE, "");116 static_assert(isAligned(StaticBufferNumElements * sizeof(uptr),117 SCUDO_CACHE_LINE_SIZE),118 "");119 120 struct Buffer {121 // Pointer to the buffer's memory, or nullptr if no buffer was allocated.122 uptr *Data = nullptr;123 124 // The index of the underlying static buffer, or StaticBufferCount if this125 // buffer was dynamically allocated. This value is initially set to a poison126 // value to aid debugging.127 uptr BufferIndex = ~static_cast<uptr>(0);128 129 // Only valid if BufferIndex == StaticBufferCount.130 MemMapT MemMap = {};131 };132 133 // Return a zero-initialized buffer which can contain at least the given134 // number of elements, or nullptr on failure.135 Buffer getBuffer(const uptr NumElements) {136 if (UNLIKELY(NumElements > StaticBufferNumElements))137 return getDynamicBuffer(NumElements);138 139 uptr index;140 {141 // TODO: In general, we expect this operation should be fast so the142 // waiting thread won't be put into sleep. The HybridMutex does implement143 // the busy-waiting but we may want to review the performance and see if144 // we need an explict spin lock here.145 ScopedLock L(Mutex);146 index = getLeastSignificantSetBitIndex(Mask);147 if (index < StaticBufferCount)148 Mask ^= static_cast<uptr>(1) << index;149 }150 151 if (index >= StaticBufferCount)152 return getDynamicBuffer(NumElements);153 154 Buffer Buf;155 Buf.Data = &RawBuffer[index * StaticBufferNumElements];156 Buf.BufferIndex = index;157 memset(Buf.Data, 0, StaticBufferNumElements * sizeof(uptr));158 return Buf;159 }160 161 void releaseBuffer(Buffer Buf) {162 DCHECK_NE(Buf.Data, nullptr);163 DCHECK_LE(Buf.BufferIndex, StaticBufferCount);164 if (Buf.BufferIndex != StaticBufferCount) {165 ScopedLock L(Mutex);166 DCHECK_EQ((Mask & (static_cast<uptr>(1) << Buf.BufferIndex)), 0U);167 Mask |= static_cast<uptr>(1) << Buf.BufferIndex;168 } else {169 Buf.MemMap.unmap();170 }171 }172 173 bool isStaticBufferTestOnly(const Buffer &Buf) {174 DCHECK_NE(Buf.Data, nullptr);175 DCHECK_LE(Buf.BufferIndex, StaticBufferCount);176 return Buf.BufferIndex != StaticBufferCount;177 }178 179private:180 Buffer getDynamicBuffer(const uptr NumElements) {181 // When using a heap-based buffer, precommit the pages backing the182 // Vmar by passing |MAP_PRECOMMIT| flag. This allows an optimization183 // where page fault exceptions are skipped as the allocated memory184 // is accessed. So far, this is only enabled on Fuchsia. It hasn't proven a185 // performance benefit on other platforms.186 const uptr MmapFlags = MAP_ALLOWNOMEM | (SCUDO_FUCHSIA ? MAP_PRECOMMIT : 0);187 const uptr MappedSize =188 roundUp(NumElements * sizeof(uptr), getPageSizeCached());189 Buffer Buf;190 if (Buf.MemMap.map(/*Addr=*/0, MappedSize, "scudo:counters", MmapFlags)) {191 Buf.Data = reinterpret_cast<uptr *>(Buf.MemMap.getBase());192 Buf.BufferIndex = StaticBufferCount;193 }194 return Buf;195 }196 197 HybridMutex Mutex;198 // '1' means that buffer index is not used. '0' means the buffer is in use.199 uptr Mask GUARDED_BY(Mutex) = ~static_cast<uptr>(0);200 uptr RawBuffer[StaticBufferCount * StaticBufferNumElements] GUARDED_BY(Mutex);201};202 203// A Region page map is used to record the usage of pages in the regions. It204// implements a packed array of Counters. Each counter occupies 2^N bits, enough205// to store counter's MaxValue. Ctor will try to use a static buffer first, and206// if that fails (the buffer is too small or already locked), will allocate the207// required Buffer via map(). The caller is expected to check whether the208// initialization was successful by checking isAllocated() result. For209// performance sake, none of the accessors check the validity of the arguments,210// It is assumed that Index is always in [0, N) range and the value is not211// incremented past MaxValue.212class RegionPageMap {213public:214 RegionPageMap()215 : Regions(0), NumCounters(0), CounterSizeBitsLog(0), CounterMask(0),216 PackingRatioLog(0), BitOffsetMask(0), SizePerRegion(0),217 BufferNumElements(0) {}218 RegionPageMap(uptr NumberOfRegions, uptr CountersPerRegion, uptr MaxValue) {219 reset(NumberOfRegions, CountersPerRegion, MaxValue);220 }221 ~RegionPageMap() {222 if (!isAllocated())223 return;224 Buffers.releaseBuffer(Buffer);225 Buffer = {};226 }227 228 // Lock of `StaticBuffer` is acquired conditionally and there's no easy way to229 // specify the thread-safety attribute properly in current code structure.230 // Besides, it's the only place we may want to check thread safety. Therefore,231 // it's fine to bypass the thread-safety analysis now.232 void reset(uptr NumberOfRegion, uptr CountersPerRegion, uptr MaxValue) {233 DCHECK_GT(NumberOfRegion, 0);234 DCHECK_GT(CountersPerRegion, 0);235 DCHECK_GT(MaxValue, 0);236 237 Regions = NumberOfRegion;238 NumCounters = CountersPerRegion;239 240 constexpr uptr MaxCounterBits = sizeof(*Buffer.Data) * 8UL;241 // Rounding counter storage size up to the power of two allows for using242 // bit shifts calculating particular counter's Index and offset.243 const uptr CounterSizeBits =244 roundUpPowerOfTwo(getMostSignificantSetBitIndex(MaxValue) + 1);245 DCHECK_LE(CounterSizeBits, MaxCounterBits);246 CounterSizeBitsLog = getLog2(CounterSizeBits);247 CounterMask = ~(static_cast<uptr>(0)) >> (MaxCounterBits - CounterSizeBits);248 249 const uptr PackingRatio = MaxCounterBits >> CounterSizeBitsLog;250 DCHECK_GT(PackingRatio, 0);251 PackingRatioLog = getLog2(PackingRatio);252 BitOffsetMask = PackingRatio - 1;253 254 SizePerRegion =255 roundUp(NumCounters, static_cast<uptr>(1U) << PackingRatioLog) >>256 PackingRatioLog;257 BufferNumElements = SizePerRegion * Regions;258 Buffer = Buffers.getBuffer(BufferNumElements);259 }260 261 bool isAllocated() const { return Buffer.Data != nullptr; }262 263 uptr getCount() const { return NumCounters; }264 265 uptr get(uptr Region, uptr I) const {266 DCHECK_LT(Region, Regions);267 DCHECK_LT(I, NumCounters);268 const uptr Index = I >> PackingRatioLog;269 const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;270 return (Buffer.Data[Region * SizePerRegion + Index] >> BitOffset) &271 CounterMask;272 }273 274 void inc(uptr Region, uptr I) const {275 DCHECK_LT(get(Region, I), CounterMask);276 const uptr Index = I >> PackingRatioLog;277 const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;278 DCHECK_LT(BitOffset, SCUDO_WORDSIZE);279 DCHECK_EQ(isAllCounted(Region, I), false);280 Buffer.Data[Region * SizePerRegion + Index] += static_cast<uptr>(1U)281 << BitOffset;282 }283 284 void incN(uptr Region, uptr I, uptr N) const {285 DCHECK_GT(N, 0U);286 DCHECK_LE(N, CounterMask);287 DCHECK_LE(get(Region, I), CounterMask - N);288 const uptr Index = I >> PackingRatioLog;289 const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;290 DCHECK_LT(BitOffset, SCUDO_WORDSIZE);291 DCHECK_EQ(isAllCounted(Region, I), false);292 Buffer.Data[Region * SizePerRegion + Index] += N << BitOffset;293 }294 295 void incRange(uptr Region, uptr From, uptr To) const {296 DCHECK_LE(From, To);297 const uptr Top = Min(To + 1, NumCounters);298 for (uptr I = From; I < Top; I++)299 inc(Region, I);300 }301 302 // Set the counter to the max value. Note that the max number of blocks in a303 // page may vary. To provide an easier way to tell if all the blocks are304 // counted for different pages, set to the same max value to denote the305 // all-counted status.306 void setAsAllCounted(uptr Region, uptr I) const {307 DCHECK_LE(get(Region, I), CounterMask);308 const uptr Index = I >> PackingRatioLog;309 const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;310 DCHECK_LT(BitOffset, SCUDO_WORDSIZE);311 Buffer.Data[Region * SizePerRegion + Index] |= CounterMask << BitOffset;312 }313 void setAsAllCountedRange(uptr Region, uptr From, uptr To) const {314 DCHECK_LE(From, To);315 const uptr Top = Min(To + 1, NumCounters);316 for (uptr I = From; I < Top; I++)317 setAsAllCounted(Region, I);318 }319 320 bool updateAsAllCountedIf(uptr Region, uptr I, uptr MaxCount) {321 const uptr Count = get(Region, I);322 if (Count == CounterMask)323 return true;324 if (Count == MaxCount) {325 setAsAllCounted(Region, I);326 return true;327 }328 return false;329 }330 bool isAllCounted(uptr Region, uptr I) const {331 return get(Region, I) == CounterMask;332 }333 334 uptr getBufferNumElements() const { return BufferNumElements; }335 336private:337 // We may consider making this configurable if there are cases which may338 // benefit from this.339 static const uptr StaticBufferCount = 2U;340 static const uptr StaticBufferNumElements = 512U;341 using BufferPoolT = BufferPool<StaticBufferCount, StaticBufferNumElements>;342 static BufferPoolT Buffers;343 344 uptr Regions;345 uptr NumCounters;346 uptr CounterSizeBitsLog;347 uptr CounterMask;348 uptr PackingRatioLog;349 uptr BitOffsetMask;350 351 uptr SizePerRegion;352 uptr BufferNumElements;353 BufferPoolT::Buffer Buffer;354};355 356template <class ReleaseRecorderT> class FreePagesRangeTracker {357public:358 explicit FreePagesRangeTracker(ReleaseRecorderT &Recorder)359 : Recorder(Recorder) {}360 361 void processNextPage(bool Released) {362 if (Released) {363 if (!InRange) {364 CurrentRangeStatePage = CurrentPage;365 InRange = true;366 }367 } else {368 closeOpenedRange();369 }370 CurrentPage++;371 }372 373 void skipPages(uptr N) {374 closeOpenedRange();375 CurrentPage += N;376 }377 378 void finish() { closeOpenedRange(); }379 380private:381 void closeOpenedRange() {382 if (InRange) {383 const uptr PageSizeLog = getPageSizeLogCached();384 Recorder.releasePageRangeToOS((CurrentRangeStatePage << PageSizeLog),385 (CurrentPage << PageSizeLog));386 InRange = false;387 }388 }389 390 ReleaseRecorderT &Recorder;391 bool InRange = false;392 uptr CurrentPage = 0;393 uptr CurrentRangeStatePage = 0;394};395 396struct PageReleaseContext {397 PageReleaseContext(uptr BlockSize, uptr NumberOfRegions, uptr ReleaseSize,398 uptr ReleaseOffset = 0)399 : BlockSize(BlockSize), NumberOfRegions(NumberOfRegions) {400 const uptr PageSize = getPageSizeCached();401 if (BlockSize <= PageSize) {402 if (PageSize % BlockSize == 0) {403 // Same number of chunks per page, no cross overs.404 FullPagesBlockCountMax = PageSize / BlockSize;405 SameBlockCountPerPage = true;406 } else if (BlockSize % (PageSize % BlockSize) == 0) {407 // Some chunks are crossing page boundaries, which means that the page408 // contains one or two partial chunks, but all pages contain the same409 // number of chunks.410 FullPagesBlockCountMax = PageSize / BlockSize + 1;411 SameBlockCountPerPage = true;412 } else {413 // Some chunks are crossing page boundaries, which means that the page414 // contains one or two partial chunks.415 FullPagesBlockCountMax = PageSize / BlockSize + 2;416 SameBlockCountPerPage = false;417 }418 } else {419 if ((BlockSize & (PageSize - 1)) == 0) {420 // One chunk covers multiple pages, no cross overs.421 FullPagesBlockCountMax = 1;422 SameBlockCountPerPage = true;423 } else {424 // One chunk covers multiple pages, Some chunks are crossing page425 // boundaries. Some pages contain one chunk, some contain two.426 FullPagesBlockCountMax = 2;427 SameBlockCountPerPage = false;428 }429 }430 431 // TODO: For multiple regions, it's more complicated to support partial432 // region marking (which includes the complexity of how to handle the last433 // block in a region). We may consider this after markFreeBlocks() accepts434 // only free blocks from the same region.435 if (NumberOfRegions != 1)436 DCHECK_EQ(ReleaseOffset, 0U);437 438 const uptr PageSizeLog = getPageSizeLogCached();439 PagesCount = roundUp(ReleaseSize, PageSize) >> PageSizeLog;440 ReleasePageOffset = ReleaseOffset >> PageSizeLog;441 }442 443 // PageMap is lazily allocated when markFreeBlocks() is invoked.444 bool hasBlockMarked() const {445 return PageMap.isAllocated();446 }447 448 bool ensurePageMapAllocated() {449 if (PageMap.isAllocated())450 return true;451 PageMap.reset(NumberOfRegions, PagesCount, FullPagesBlockCountMax);452 // TODO: Log some message when we fail on PageMap allocation.453 return PageMap.isAllocated();454 }455 456 // Mark all the blocks in the given range [From, to). Instead of visiting all457 // the blocks, we will just mark the page as all counted. Note the `From` and458 // `To` has to be page aligned but with one exception, if `To` is equal to the459 // RegionSize, it's not necessary to be aligned with page size.460 bool markRangeAsAllCounted(uptr From, uptr To, uptr Base,461 const uptr RegionIndex, const uptr RegionSize) {462 const uptr PageSize = getPageSizeCached();463 DCHECK_LT(From, To);464 DCHECK_LE(To, Base + RegionSize);465 DCHECK_EQ(From % PageSize, 0U);466 DCHECK_LE(To - From, RegionSize);467 468 if (!ensurePageMapAllocated())469 return false;470 471 uptr FromInRegion = From - Base;472 uptr ToInRegion = To - Base;473 uptr FirstBlockInRange = roundUpSlow(FromInRegion, BlockSize);474 475 // The straddling block sits across entire range.476 if (FirstBlockInRange >= ToInRegion)477 return true;478 479 // First block may not sit at the first pape in the range, move480 // `FromInRegion` to the first block page.481 FromInRegion = roundDown(FirstBlockInRange, PageSize);482 483 // When The first block is not aligned to the range boundary, which means484 // there is a block sitting acorss `From`, that looks like,485 //486 // From To487 // V V488 // +-----------------------------------------------+489 // +-----+-----+-----+-----+490 // | | | | | ...491 // +-----+-----+-----+-----+492 // |- first page -||- second page -||- ...493 //494 // Therefore, we can't just mark the first page as all counted. Instead, we495 // increment the number of blocks in the first page in the page map and496 // then round up the `From` to the next page.497 if (FirstBlockInRange != FromInRegion) {498 DCHECK_GT(FromInRegion + PageSize, FirstBlockInRange);499 uptr NumBlocksInFirstPage =500 (FromInRegion + PageSize - FirstBlockInRange + BlockSize - 1) /501 BlockSize;502 PageMap.incN(RegionIndex, getPageIndex(FromInRegion),503 NumBlocksInFirstPage);504 FromInRegion = roundUp(FromInRegion + 1, PageSize);505 }506 507 uptr LastBlockInRange = roundDownSlow(ToInRegion - 1, BlockSize);508 509 // Note that LastBlockInRange may be smaller than `FromInRegion` at this510 // point because it may contain only one block in the range.511 512 // When the last block sits across `To`, we can't just mark the pages513 // occupied by the last block as all counted. Instead, we increment the514 // counters of those pages by 1. The exception is that if it's the last515 // block in the region, it's fine to mark those pages as all counted.516 if (LastBlockInRange + BlockSize != RegionSize) {517 DCHECK_EQ(ToInRegion % PageSize, 0U);518 // The case below is like,519 //520 // From To521 // V V522 // +----------------------------------------+523 // +-----+-----+-----+-----+524 // | | | | | ...525 // +-----+-----+-----+-----+526 // ... -||- last page -||- next page -|527 //528 // The last block is not aligned to `To`, we need to increment the529 // counter of `next page` by 1.530 if (LastBlockInRange + BlockSize != ToInRegion) {531 PageMap.incRange(RegionIndex, getPageIndex(ToInRegion),532 getPageIndex(LastBlockInRange + BlockSize - 1));533 }534 } else {535 ToInRegion = RegionSize;536 }537 538 // After handling the first page and the last block, it's safe to mark any539 // page in between the range [From, To).540 if (FromInRegion < ToInRegion) {541 PageMap.setAsAllCountedRange(RegionIndex, getPageIndex(FromInRegion),542 getPageIndex(ToInRegion - 1));543 }544 545 return true;546 }547 548 template <class TransferBatchT, typename DecompactPtrT>549 bool markFreeBlocksInRegion(const IntrusiveList<TransferBatchT> &FreeList,550 DecompactPtrT DecompactPtr, const uptr Base,551 const uptr RegionIndex, const uptr RegionSize,552 bool MayContainLastBlockInRegion) {553 if (!ensurePageMapAllocated())554 return false;555 556 const uptr PageSize = getPageSizeCached();557 if (MayContainLastBlockInRegion) {558 const uptr LastBlockInRegion =559 ((RegionSize / BlockSize) - 1U) * BlockSize;560 // The last block in a region may not use the entire page, we mark the561 // following "pretend" memory block(s) as free in advance.562 //563 // Region Boundary564 // v565 // -----+-----------------------+566 // | Last Page | <- Rounded Region Boundary567 // -----+-----------------------+568 // |-----||- trailing blocks -|569 // ^570 // last block571 const uptr RoundedRegionSize = roundUp(RegionSize, PageSize);572 const uptr TrailingBlockBase = LastBlockInRegion + BlockSize;573 // If the difference between `RoundedRegionSize` and574 // `TrailingBlockBase` is larger than a page, that implies the reported575 // `RegionSize` may not be accurate.576 DCHECK_LT(RoundedRegionSize - TrailingBlockBase, PageSize);577 578 // Only the last page touched by the last block needs to mark the trailing579 // blocks. Note that if the last "pretend" block straddles the boundary,580 // we still have to count it in so that the logic of counting the number581 // of blocks on a page is consistent.582 uptr NumTrailingBlocks =583 (roundUpSlow(RoundedRegionSize - TrailingBlockBase, BlockSize) +584 BlockSize - 1) /585 BlockSize;586 if (NumTrailingBlocks > 0) {587 PageMap.incN(RegionIndex, getPageIndex(TrailingBlockBase),588 NumTrailingBlocks);589 }590 }591 592 // Iterate over free chunks and count how many free chunks affect each593 // allocated page.594 if (BlockSize <= PageSize && PageSize % BlockSize == 0) {595 // Each chunk affects one page only.596 for (const auto &It : FreeList) {597 for (u16 I = 0; I < It.getCount(); I++) {598 const uptr PInRegion = DecompactPtr(It.get(I)) - Base;599 DCHECK_LT(PInRegion, RegionSize);600 PageMap.inc(RegionIndex, getPageIndex(PInRegion));601 }602 }603 } else {604 // In all other cases chunks might affect more than one page.605 DCHECK_GE(RegionSize, BlockSize);606 for (const auto &It : FreeList) {607 for (u16 I = 0; I < It.getCount(); I++) {608 const uptr PInRegion = DecompactPtr(It.get(I)) - Base;609 PageMap.incRange(RegionIndex, getPageIndex(PInRegion),610 getPageIndex(PInRegion + BlockSize - 1));611 }612 }613 }614 615 return true;616 }617 618 uptr getPageIndex(uptr P) {619 return (P >> getPageSizeLogCached()) - ReleasePageOffset;620 }621 uptr getReleaseOffset() {622 return ReleasePageOffset << getPageSizeLogCached();623 }624 625 uptr BlockSize;626 uptr NumberOfRegions;627 // For partial region marking, some pages in front are not needed to be628 // counted.629 uptr ReleasePageOffset;630 uptr PagesCount;631 uptr FullPagesBlockCountMax;632 bool SameBlockCountPerPage;633 RegionPageMap PageMap;634};635 636// Try to release the page which doesn't have any in-used block, i.e., they are637// all free blocks. The `PageMap` will record the number of free blocks in each638// page.639template <class ReleaseRecorderT, typename SkipRegionT>640NOINLINE void641releaseFreeMemoryToOS(PageReleaseContext &Context,642 ReleaseRecorderT &Recorder, SkipRegionT SkipRegion) {643 const uptr PageSize = getPageSizeCached();644 const uptr BlockSize = Context.BlockSize;645 const uptr PagesCount = Context.PagesCount;646 const uptr NumberOfRegions = Context.NumberOfRegions;647 const uptr ReleasePageOffset = Context.ReleasePageOffset;648 const uptr FullPagesBlockCountMax = Context.FullPagesBlockCountMax;649 const bool SameBlockCountPerPage = Context.SameBlockCountPerPage;650 RegionPageMap &PageMap = Context.PageMap;651 652 // Iterate over pages detecting ranges of pages with chunk Counters equal653 // to the expected number of chunks for the particular page.654 FreePagesRangeTracker<ReleaseRecorderT> RangeTracker(Recorder);655 if (SameBlockCountPerPage) {656 // Fast path, every page has the same number of chunks affecting it.657 for (uptr I = 0; I < NumberOfRegions; I++) {658 if (SkipRegion(I)) {659 RangeTracker.skipPages(PagesCount);660 continue;661 }662 for (uptr J = 0; J < PagesCount; J++) {663 const bool CanRelease =664 PageMap.updateAsAllCountedIf(I, J, FullPagesBlockCountMax);665 RangeTracker.processNextPage(CanRelease);666 }667 }668 } else {669 // Slow path, go through the pages keeping count how many chunks affect670 // each page.671 const uptr Pn = BlockSize < PageSize ? PageSize / BlockSize : 1;672 const uptr Pnc = Pn * BlockSize;673 // The idea is to increment the current page pointer by the first chunk674 // size, middle portion size (the portion of the page covered by chunks675 // except the first and the last one) and then the last chunk size, adding676 // up the number of chunks on the current page and checking on every step677 // whether the page boundary was crossed.678 for (uptr I = 0; I < NumberOfRegions; I++) {679 if (SkipRegion(I)) {680 RangeTracker.skipPages(PagesCount);681 continue;682 }683 uptr PrevPageBoundary = 0;684 uptr CurrentBoundary = 0;685 if (ReleasePageOffset > 0) {686 PrevPageBoundary = ReleasePageOffset << getPageSizeLogCached();687 CurrentBoundary = roundUpSlow(PrevPageBoundary, BlockSize);688 }689 for (uptr J = 0; J < PagesCount; J++) {690 const uptr PageBoundary = PrevPageBoundary + PageSize;691 uptr BlocksPerPage = Pn;692 if (CurrentBoundary < PageBoundary) {693 if (CurrentBoundary > PrevPageBoundary)694 BlocksPerPage++;695 CurrentBoundary += Pnc;696 if (CurrentBoundary < PageBoundary) {697 BlocksPerPage++;698 CurrentBoundary += BlockSize;699 }700 }701 PrevPageBoundary = PageBoundary;702 const bool CanRelease =703 PageMap.updateAsAllCountedIf(I, J, BlocksPerPage);704 RangeTracker.processNextPage(CanRelease);705 }706 }707 }708 RangeTracker.finish();709}710 711} // namespace scudo712 713#endif // SCUDO_RELEASE_H_714