diff --git a/compiler-rt/lib/scudo/standalone/primary32.h b/compiler-rt/lib/scudo/standalone/primary32.h --- a/compiler-rt/lib/scudo/standalone/primary32.h +++ b/compiler-rt/lib/scudo/standalone/primary32.h @@ -118,6 +118,8 @@ return CompactPtr >> GroupSizeLog; } + uptr batchGroupBase(uptr GroupId) { return GroupId << GroupSizeLog; } + TransferBatch *popBatch(CacheT *C, uptr ClassId) { DCHECK_LT(ClassId, NumClasses); SizeClassInfo *Sci = getSizeClassInfo(ClassId); @@ -778,9 +780,36 @@ } BG.PushedBlocksAtLastCheckpoint = BG.PushedBlocks; - // Note that we don't always visit blocks in each BatchGroup so that we - // may miss the chance of releasing certain pages that cross BatchGroups. - Context.markFreeBlocks(BG.Batches, DecompactPtr, Base); + + const uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize; + // The first condition to do range marking is that all the blocks in the + // range need to be from same region. In SizeClassAllocator32, this is + // true when GroupSize and RegionSize are the same. Another tirck case is, + // while doing range marking, the last block in a region needs the logic + // to mark the last page. However, in SizeClassAllocator32, the RegionSize + // recorded in PageReleaseContext may be different from + // `CurrentRegionAllocated` of the current region. This exception excludes + // the chance of doing range marking for the current region. + const bool CanDoRangeMark = + GroupSize == RegionSize && BG.GroupId != CurRegionGroupId; + + if (!CanDoRangeMark || NumBlocks != MaxContainedBlocks) { + if (CanDoRangeMark) + DCHECK_LT(NumBlocks, MaxContainedBlocks); + + // Note that we don't always visit blocks in each BatchGroup so that we + // may miss the chance of releasing certain pages that cross + // BatchGroups. + Context.markFreeBlocks(BG.Batches, DecompactPtr, Base); + } else { + for (const auto &It : BG.Batches) + for (u16 I = 0; I < It.getCount(); ++I) + DCHECK_EQ(compactPtrGroup(It.get(I)), BG.GroupId); + + const uptr From = batchGroupBase(BG.GroupId); + const uptr To = batchGroupBase(BG.GroupId) + AllocatedGroupSize; + Context.markRangeAsAllCounted(From, To, Base); + } } if (!Context.hasBlockMarked()) diff --git a/compiler-rt/lib/scudo/standalone/primary64.h b/compiler-rt/lib/scudo/standalone/primary64.h --- a/compiler-rt/lib/scudo/standalone/primary64.h +++ b/compiler-rt/lib/scudo/standalone/primary64.h @@ -862,9 +862,29 @@ } BG.PushedBlocksAtLastCheckpoint = BG.PushedBlocks; - // Note that we don't always visit blocks in each BatchGroup so that we - // may miss the chance of releasing certain pages that cross BatchGroups. - Context.markFreeBlocks(BG.Batches, DecompactPtr, Region->RegionBeg); + + const uptr BatchGroupUsedEnd = BatchGroupBeg + AllocatedGroupSize; + const bool BlockAlignedWithUsedEnd = + (BatchGroupUsedEnd - Region->RegionBeg) % BlockSize == 0; + + uptr MaxContainedBlocks = AllocatedGroupSize / BlockSize; + if (!BlockAlignedWithUsedEnd) + ++MaxContainedBlocks; + + if (NumBlocks != MaxContainedBlocks) { + DCHECK_LT(NumBlocks, MaxContainedBlocks); + // Note that we don't always visit blocks in each BatchGroup so that we + // may miss the chance of releasing certain pages that cross + // BatchGroups. + Context.markFreeBlocks(BG.Batches, DecompactPtr, Region->RegionBeg); + } else { + for (const auto &It : BG.Batches) + for (u16 I = 0; I < It.getCount(); ++I) + DCHECK_EQ(compactPtrGroup(It.get(I)), BG.GroupId); + + Context.markRangeAsAllCounted(BatchGroupBeg, BatchGroupUsedEnd, + Region->RegionBeg); + } } if (!Context.hasBlockMarked()) diff --git a/compiler-rt/lib/scudo/standalone/release.h b/compiler-rt/lib/scudo/standalone/release.h --- a/compiler-rt/lib/scudo/standalone/release.h +++ b/compiler-rt/lib/scudo/standalone/release.h @@ -147,6 +147,17 @@ << BitOffset; } + void incN(uptr Region, uptr I, uptr N) const { + DCHECK_GT(N, 0U); + DCHECK_LE(N, CounterMask); + DCHECK_LE(get(Region, I), CounterMask - N); + const uptr Index = I >> PackingRatioLog; + const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog; + DCHECK_LT(BitOffset, SCUDO_WORDSIZE); + DCHECK_EQ(isAllCounted(Region, I), false); + Buffer[Region * SizePerRegion + Index] += N << BitOffset; + } + void incRange(uptr Region, uptr From, uptr To) const { DCHECK_LE(From, To); const uptr Top = Min(To + 1, NumCounters); @@ -165,6 +176,23 @@ DCHECK_LT(BitOffset, SCUDO_WORDSIZE); Buffer[Region * SizePerRegion + Index] |= CounterMask << BitOffset; } + void setAsAllCountedRange(uptr Region, uptr From, uptr To) const { + DCHECK_LE(From, To); + const uptr Top = Min(To + 1, NumCounters); + for (uptr I = From; I < Top; I++) + setAsAllCounted(Region, I); + } + + bool updateAsAllCountedIf(uptr Region, uptr I, uptr MaxCount) { + const uptr Count = get(Region, I); + if (Count == CounterMask) + return true; + if (Count == MaxCount) { + setAsAllCounted(Region, I); + return true; + } + return false; + } bool isAllCounted(uptr Region, uptr I) const { return get(Region, I) == CounterMask; } @@ -284,6 +312,101 @@ DCHECK(PageMap.isAllocated()); } + // Mark all the blocks in the given range [From, to). Instead of visiting all + // the blocks, we will just mark the page as all counted. Note the `From` and + // `To` has to be page aligned but with one exception, if `To` is equal to the + // RegionSize, it's not necessary to be aligned with page size. + void markRangeAsAllCounted(uptr From, uptr To, uptr Base) { + DCHECK_LT(From, To); + DCHECK_EQ(From % PageSize, 0U); + + ensurePageMapAllocated(); + + const uptr FromOffset = From - Base; + const uptr ToOffset = To - Base; + + const uptr RegionIndex = + NumberOfRegions == 1U ? 0 : FromOffset / RegionSize; + if (SCUDO_DEBUG) { + const uptr ToRegionIndex = + NumberOfRegions == 1U ? 0 : (ToOffset - 1) / RegionSize; + CHECK_EQ(RegionIndex, ToRegionIndex); + } + + uptr FromInRegion = FromOffset - RegionIndex * RegionSize; + uptr ToInRegion = ToOffset - RegionIndex * RegionSize; + uptr FirstBlockInRange = roundUpSlow(FromInRegion, BlockSize); + + // The straddling block sits across entire range. + if (FirstBlockInRange >= ToInRegion) + return; + + // First block may not sit at the first pape in the range, move + // `FromInRegion` to the first block page. + FromInRegion = roundDown(FirstBlockInRange, PageSize); + + // When The first block is not aligned the range boundary, which means there + // is a block sits acorss `From`, which looks like, + // + // From To + // V V + // +-----------------------------------------------+ + // +-----+-----+-----+-----+ + // | | | | | ... + // +-----+-----+-----+-----+ + // |- first page -||- second page -||- ... + // + // Therefore, we can't just mark the first page as all counted. Instead, we + // increment the number of blocks in the first page in the page map and + // then round up the `From` to the next page. + if (FirstBlockInRange != FromInRegion) { + DCHECK_GT(FromInRegion + PageSize, FirstBlockInRange); + uptr NumBlocksInFirstPage = + (FromInRegion + PageSize - FirstBlockInRange + BlockSize - 1) / + BlockSize; + PageMap.incN(RegionIndex, FromInRegion >> PageSizeLog, + NumBlocksInFirstPage); + FromInRegion = roundUp(FromInRegion + 1, PageSize); + } + + uptr LastBlockInRange = roundDownSlow(ToInRegion - 1, BlockSize); + if (LastBlockInRange < FromInRegion) + return; + + // When the last block sits across `To`, we can't just mark the pages + // occupied by the last block as all counted. Instead, we increment the + // counters of those pages by 1. The exception is that if it's the last + // block in the region, it's fine to mark those pages as all counted. + if (LastBlockInRange + BlockSize != RegionSize) { + DCHECK_EQ(ToInRegion % PageSize, 0U); + // The case below is like, + // + // From To + // V V + // +----------------------------------------+ + // +-----+-----+-----+-----+ + // | | | | | ... + // +-----+-----+-----+-----+ + // ... -||- last page -||- next page -| + // + // The last block is not aligned to `To`, we need to increment the + // counter of `next page` by 1. + if (LastBlockInRange + BlockSize != ToInRegion) { + PageMap.incRange(RegionIndex, ToInRegion >> PageSizeLog, + (LastBlockInRange + BlockSize - 1) >> PageSizeLog); + } + } else { + ToInRegion = RegionSize; + } + + // After handling the first page and the last block, it's safe to mark any + // page in between the range [From, To). + if (FromInRegion < ToInRegion) { + PageMap.setAsAllCountedRange(RegionIndex, FromInRegion >> PageSizeLog, + (ToInRegion - 1) >> PageSizeLog); + } + } + template void markFreeBlocks(const IntrusiveList &FreeList, DecompactPtrT DecompactPtr, uptr Base) { @@ -371,9 +494,8 @@ continue; } for (uptr J = 0; J < PagesCount; J++) { - const bool CanRelease = PageMap.get(I, J) == FullPagesBlockCountMax; - if (CanRelease) - PageMap.setAsAllCounted(I, J); + const bool CanRelease = + PageMap.updateAsAllCountedIf(I, J, FullPagesBlockCountMax); RangeTracker.processNextPage(CanRelease); } } @@ -407,9 +529,8 @@ } } PrevPageBoundary = PageBoundary; - const bool CanRelease = PageMap.get(I, J) == BlocksPerPage; - if (CanRelease) - PageMap.setAsAllCounted(I, J); + const bool CanRelease = + PageMap.updateAsAllCountedIf(I, J, BlocksPerPage); RangeTracker.processNextPage(CanRelease); } } diff --git a/compiler-rt/lib/scudo/standalone/tests/release_test.cpp b/compiler-rt/lib/scudo/standalone/tests/release_test.cpp --- a/compiler-rt/lib/scudo/standalone/tests/release_test.cpp +++ b/compiler-rt/lib/scudo/standalone/tests/release_test.cpp @@ -54,6 +54,27 @@ EXPECT_EQ(2UL, PageMap.get(0U, C)); } } + + // Similar to the above except that we are using incN(). + for (scudo::uptr I = 0; (SCUDO_WORDSIZE >> I) != 0; I++) { + // Make sure counters request one memory page for the buffer. + const scudo::uptr NumCounters = + (scudo::getPageSizeCached() / 8) * (SCUDO_WORDSIZE >> I); + scudo::uptr MaxValue = 1UL << ((1UL << I) - 1); + if (MaxValue <= 1U) + continue; + + scudo::RegionPageMap PageMap(1U, NumCounters, MaxValue); + + scudo::uptr N = MaxValue / 2; + PageMap.incN(0U, 0, N); + for (scudo::uptr C = 1; C < NumCounters; C++) { + EXPECT_EQ(0UL, PageMap.get(0U, C)); + PageMap.incN(0U, C, N); + EXPECT_EQ(N, PageMap.get(0U, C - 1)); + } + EXPECT_EQ(N, PageMap.get(0U, NumCounters - 1)); + } } class StringRangeRecorder { @@ -277,6 +298,109 @@ } } +template void testPageMapMarkRange() { + const scudo::uptr PageSize = scudo::getPageSizeCached(); + + for (scudo::uptr I = 1; I <= SizeClassMap::LargestClassId; I++) { + const scudo::uptr BlockSize = SizeClassMap::getSizeByClassId(I); + + const scudo::uptr GroupNum = 2; + const scudo::uptr GroupSize = scudo::roundUp(BlockSize, PageSize) * 2; + const scudo::uptr RegionSize = + scudo::roundUpSlow(GroupSize * GroupNum, BlockSize); + const scudo::uptr RoundedRegionSize = scudo::roundUp(RegionSize, PageSize); + + std::vector Pages(RoundedRegionSize / PageSize, 0); + for (scudo::uptr Block = 0; Block + BlockSize <= RoundedRegionSize; + Block += BlockSize) { + for (scudo::uptr page = Block / PageSize; + page <= (Block + BlockSize - 1) / PageSize; ++page) { + ASSERT_LT(page, Pages.size()); + ++Pages[page]; + } + } + + for (scudo::uptr GroupId = 0; GroupId < GroupNum; ++GroupId) { + const scudo::uptr GroupBeg = GroupId * GroupSize; + const scudo::uptr GroupEnd = GroupBeg + GroupSize; + + scudo::PageReleaseContext Context(BlockSize, RegionSize, + /*NumberOfRegions=*/1U); + Context.markRangeAsAllCounted(GroupBeg, GroupEnd, /*Base=*/0); + + scudo::uptr FirstBlock = + ((GroupBeg + BlockSize - 1) / BlockSize) * BlockSize; + + // All the pages before first block page are supposed not to be marked. + if (FirstBlock / PageSize > 0) { + for (scudo::uptr Page = 0; Page <= FirstBlock / PageSize - 1; ++Page) + EXPECT_EQ(Context.PageMap.get(/*Region=*/0, Page), 0U); + } + + // Verify the pages used by the blocks in the group except that if the + // end of the last block is not aligned with `GroupEnd`, it'll be verified + // later. + scudo::uptr Block; + for (Block = FirstBlock; Block + BlockSize <= GroupEnd; + Block += BlockSize) { + for (scudo::uptr Page = Block / PageSize; + Page <= (Block + BlockSize - 1) / PageSize; ++Page) { + // First used page in the group has two cases, which are w/ and w/o + // block sits across the boundary. + if (Page == FirstBlock / PageSize) { + if (FirstBlock % PageSize == 0) { + EXPECT_TRUE(Context.PageMap.isAllCounted(/*Region=*/0U, Page)); + } else { + // There's a block straddles `GroupBeg`, it's supposed to only + // increment the counter and we expect it should be 1 less + // (exclude the straddling one) than the total blocks on the page. + EXPECT_EQ(Context.PageMap.get(/*Region=*/0U, Page), + Pages[Page] - 1); + } + } else { + EXPECT_TRUE(Context.PageMap.isAllCounted(/*Region=*/0, Page)); + } + } + } + + if (Block == GroupEnd) + continue; + + // Examine the last block which sits across the group boundary. + if (Block + BlockSize == RegionSize) { + // This is the last block in the region, it's supposed to mark all the + // pages as all counted. + for (scudo::uptr Page = Block / PageSize; + Page <= (Block + BlockSize - 1) / PageSize; ++Page) { + EXPECT_TRUE(Context.PageMap.isAllCounted(/*Region=*/0, Page)); + } + } else { + for (scudo::uptr Page = Block / PageSize; + Page <= (Block + BlockSize - 1) / PageSize; ++Page) { + if (Page <= (GroupEnd - 1) / PageSize) + EXPECT_TRUE(Context.PageMap.isAllCounted(/*Region=*/0, Page)); + else + EXPECT_EQ(Context.PageMap.get(/*Region=*/0U, Page), 1U); + } + } + + const scudo::uptr FirstUncountedPage = + scudo::roundUp(Block + BlockSize, PageSize); + for (scudo::uptr Page = FirstUncountedPage; + Page <= RoundedRegionSize / PageSize; ++Page) { + EXPECT_EQ(Context.PageMap.get(/*Region=*/0U, Page), 0U); + } + } // Iterate each Group + + // Release the entire region. This is to ensure the last page is counted. + scudo::PageReleaseContext Context(BlockSize, RegionSize, + /*NumberOfRegions=*/1U); + Context.markRangeAsAllCounted(/*From=*/0U, /*To=*/RegionSize, /*Base=*/0); + for (scudo::uptr Page = 0; Page < RoundedRegionSize / PageSize; ++Page) + EXPECT_TRUE(Context.PageMap.isAllCounted(/*Region=*/0, Page)); + } // Iterate each size class +} + TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSDefault) { testReleaseFreeMemoryToOS(); } @@ -288,3 +412,10 @@ TEST(ScudoReleaseTest, ReleaseFreeMemoryToOSSvelte) { testReleaseFreeMemoryToOS(); } + +TEST(ScudoReleaseTest, PageMapMarkRange) { + testPageMapMarkRange(); + testPageMapMarkRange(); + testPageMapMarkRange(); + testPageMapMarkRange(); +}