[scudo] Support partial concurrent page release in SizeClassAllocator64

[Chia-hungDuan]

Summary

After extracting memory groups, it's safe to do

1. markFreeBlocks
2. releaseFreeMemoryToOS concurrently with pushBlocks() and

popBatches(). This will improve the throughput of Scudo.

[Chia-hungDuan]

Add more comment on the special ScopedUnlock

[cferris]

compiler-rt/lib/scudo/standalone/primary64.h

1018–1034

a

1042

steps

1395

that need to be recycled.

1396

BatchGroups

1397

real

1402–1404

I'm not sure what this is describing. It's not clear what's not implemented. Do you mean the algorithm to release a BatchGroup with the same CompactPtrGroupBase is not done yet?

[Chia-hungDuan]

Address review comment

[Chia-hungDuan]

compiler-rt/lib/scudo/standalone/primary64.h

1402–1404

When there are two BatchGroups with same CompactPtrGroupBase,

For non-BatchClass,

1. we merge the freelists and release one of the BatchGroups.
2. call pushBatchClassBlocks to recycle the redundant BatchGroup.

For BatchClass,

1. we merge the freelists and release one of the BatchGroups. (same as above)
2. Push the BlockGroup into the merged freelist directly

It can't use pushBatchClassBlocks because we are manipulating the freelist of BatchClass.

I paraphrased it a little bit.

[cferris]

LGTM.

[Chia-hungDuan]

compiler-rt/lib/scudo/standalone/primary64.h

1440–1441

This has to be done because when we determine if we can do range marking, it supposes only the first TransferBatch may not be full. Now this breaks the invariant.

Will revert this change first

compiler-rt/lib/scudo/standalone/primary64.h

Str->append("%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
                 Rss >> 10, Region->ReleaseInfo.RangesReleased,
                 Region->ReleaseInfo.LastReleasedBytes >> 10, Region->RegionBeg,
                 getRegionBaseByClassId(ClassId));
   }
 
   NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
                                  ReleaseToOS ReleaseType = ReleaseToOS::Normal)
       REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
-    // TODO(chiahungduan): Release `FLLock` in step 3 & 4 described in the
-    // comment below.
     ScopedLock L(Region->FLLock);
 
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr BytesInFreeList =
         Region->MemMapInfo.AllocatedUser - (Region->FreeListInfo.PoppedBlocks -
                                             Region->FreeListInfo.PushedBlocks) *
                                                BlockSize;
     if (UNLIKELY(BytesInFreeList == 0))
       return false;
 
     const uptr AllocatedUserEnd =
         Region->MemMapInfo.AllocatedUser + Region->RegionBeg;
     const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);
 
     // ====================================================================== //
     // 1. Check if we have enough free blocks and if it's worth doing a page
     //    release.
     // ====================================================================== //
     if (ReleaseType != ReleaseToOS::ForceAll &&
         !hasChanceToReleasePages(Region, BlockSize, BytesInFreeList,
                                  ReleaseType)) {
       return 0;
     }
 
-    // This is only used for debugging to ensure the consistency of the number
-    // of groups.
-    uptr NumberOfBatchGroups = Region->FreeListInfo.BlockList.size();
-
     // ====================================================================== //
     // 2. Determine which groups can release the pages. Use a heuristic to
     //    gather groups that are candidates for doing a release.
     // ====================================================================== //
     SinglyLinkedList<BatchGroup> GroupsToRelease;
     if (ReleaseType == ReleaseToOS::ForceAll) {
       GroupsToRelease = Region->FreeListInfo.BlockList;
       Region->FreeListInfo.BlockList.clear();
     } else {
       GroupsToRelease = collectGroupsToRelease(
           Region, BlockSize, AllocatedUserEnd, CompactPtrBase);
     }
     if (GroupsToRelease.empty())
       return 0;
 
-    // ====================================================================== //
-    // 3. Mark the free blocks in `GroupsToRelease` in the `PageReleaseContext`.
-    //    Then we can tell which pages are in-use by querying
-    //    `PageReleaseContext`.
-    // ====================================================================== //
+    // Ideally, we should use a class like `ScopedUnlock`. However, this form of
+    // unlocking is not supported by the thread-safety analysis. See
+    // https://clang.llvm.org/docs/ThreadSafetyAnalysis.html#no-alias-analysis
+    // for more details.
+    // Put it as local class so that we can mark the ctor/dtor with proper
+    // annotations associated to the target lock. Note that accessing the
+    // function variable in local class only works in thread-safety annotations.
+    // TODO: Implement general `ScopedUnlock` when it's supported.
+    class FLLockScopedUnlock {
+    public:
+      FLLockScopedUnlock(RegionInfo *Region) RELEASE(Region->FLLock)
+          : R(Region) {
+        R->FLLock.assertHeld();
+        R->FLLock.unlock();
+      }
+      ~FLLockScopedUnlock() ACQUIRE(Region->FLLock) { R->FLLock.lock(); }
+
+    private:
+      RegionInfo *R;
+    };
+
+    // Note that we have extracted the `GroupsToRelease` from region freelist.
+    // It's safe to let pushBlocks()/popBatches() access the remaining region
+    // freelist. In the steps 3 and 4, we will temporarily release the FLLock
+    // and lock it again before step 5.
+
+    uptr ReleasedBytes = 0;
+    {
+      FLLockScopedUnlock UL(Region);
+      // ==================================================================== //
+      // 3. Mark the free blocks in `GroupsToRelease` in the
+      //    `PageReleaseContext`. Then we can tell which pages are in-use by
+      //    querying `PageReleaseContext`.
+      // ==================================================================== //
       PageReleaseContext Context = markFreeBlocks(
           Region, BlockSize, AllocatedUserEnd, CompactPtrBase, GroupsToRelease);
       if (UNLIKELY(!Context.hasBlockMarked())) {
-      mergeGroupsToReleaseBack(Region, GroupsToRelease, NumberOfBatchGroups);
+        ScopedLock L(Region->FLLock);
+        mergeGroupsToReleaseBack(Region, GroupsToRelease);
         return 0;
       }
 
-    // ====================================================================== //
+      // ==================================================================== //
       // 4. Release the unused physical pages back to the OS.
-    // ====================================================================== //
+      // ==================================================================== //
       RegionReleaseRecorder<MemMapT> Recorder(&Region->MemMapInfo.MemMap,
                                               Region->RegionBeg,
                                               Context.getReleaseOffset());
       auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
       releaseFreeMemoryToOS(Context, Recorder, SkipRegion);
       if (Recorder.getReleasedRangesCount() > 0) {
         Region->ReleaseInfo.BytesInFreeListAtLastCheckpoint = BytesInFreeList;
         Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
         Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
       }
       Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTimeFast();
+      ReleasedBytes = Recorder.getReleasedBytes();
+    }
 
     // ====================================================================== //
     // 5. Merge the `GroupsToRelease` back to the freelist.
     // ====================================================================== //
-    mergeGroupsToReleaseBack(Region, GroupsToRelease, NumberOfBatchGroups);
+    mergeGroupsToReleaseBack(Region, GroupsToRelease);
 
-    return Recorder.getReleasedBytes();
+    return ReleasedBytes;
   }
 
   bool hasChanceToReleasePages(RegionInfo *Region, uptr BlockSize,
                                uptr BytesInFreeList, ReleaseToOS ReleaseType)
       REQUIRES(Region->MMLock, Region->FLLock) {
     DCHECK_GE(Region->FreeListInfo.PoppedBlocks,
               Region->FreeListInfo.PushedBlocks);
     const uptr PageSize = getPageSizeCached();
collectGroupsToRelease(RegionInfo *Region, const uptr BlockSize,
 
     return GroupsToRelease;
   }
 
   PageReleaseContext
   markFreeBlocks(RegionInfo *Region, const uptr BlockSize,
                  const uptr AllocatedUserEnd, const uptr CompactPtrBase,
                  SinglyLinkedList<BatchGroup> &GroupsToRelease)
-      REQUIRES(Region->MMLock, Region->FLLock) {
+      REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
     const uptr GroupSize = (1U << GroupSizeLog);
     auto DecompactPtr = [CompactPtrBase](CompactPtrT CompactPtr) {
       return decompactPtrInternal(CompactPtrBase, CompactPtr);
     };
 
     const uptr ReleaseBase = decompactGroupBase(
         CompactPtrBase, GroupsToRelease.front()->CompactPtrGroupBase);
     const uptr LastGroupEnd =
markFreeBlocks(RegionInfo *Region, const uptr BlockSize,
     }
 
     DCHECK(Context.hasBlockMarked());
 
     return Context;
   }
 
   void mergeGroupsToReleaseBack(RegionInfo *Region,
-                                SinglyLinkedList<BatchGroup> &GroupsToRelease,
-                                const uptr NumberOfBatchGroups)
+                                SinglyLinkedList<BatchGroup> &GroupsToRelease)
       REQUIRES(Region->MMLock, Region->FLLock) {
+    // After merging two freelists, we may have redundant `BatchGroup`s that
+    // need to be recycled. The number of unused `BatchGroup`s is expected to be
+    // small. Pick a constant which is inferred from real programs.
+    constexpr uptr MaxUnusedSize = 8;
+    CompactPtrT Blocks[MaxUnusedSize];
+    u32 Idx = 0;
+    RegionInfo *BatchClassRegion = getRegionInfo(SizeClassMap::BatchClassId);
+    // We can't call pushBatchClassBlocks() to recycle the unused `BatchGroup`s
+    // when we are manipulating the freelist of `BatchClassRegion`. Instead, we
+    // should just push it back to the freelist when we merge two `BatchGroup`s.
+    // This logic hasn't been implemented because we haven't supported releasing
+    // pages in `BatchClassRegion`.
+    DCHECK_NE(BatchClassRegion, Region);
+
     // Merge GroupsToRelease back to the Region::FreeListInfo.BlockList. Note
     // that both `Region->FreeListInfo.BlockList` and `GroupsToRelease` are
     // sorted.
     for (BatchGroup *BG = Region->FreeListInfo.BlockList.front(),
                     *Prev = nullptr;
          ;) {
       if (BG == nullptr || GroupsToRelease.empty()) {
         if (!GroupsToRelease.empty())
           Region->FreeListInfo.BlockList.append_back(&GroupsToRelease);
         break;
       }
 
-      DCHECK_NE(BG->CompactPtrGroupBase,
-                GroupsToRelease.front()->CompactPtrGroupBase);
+      DCHECK(!BG->Batches.empty());
 
       if (BG->CompactPtrGroupBase <
           GroupsToRelease.front()->CompactPtrGroupBase) {
         Prev = BG;
         BG = BG->Next;
         continue;
       }
 
+      BatchGroup *Cur = GroupsToRelease.front();
+      GroupsToRelease.pop_front();
+
+      if (BG->CompactPtrGroupBase == Cur->CompactPtrGroupBase) {
+        BG->PushedBlocks += Cur->PushedBlocks;
+        // We have updated `BatchGroup::BytesInBGAtLastCheckpoint` while
+        // collecting the `GroupsToRelease`.
+        BG->BytesInBGAtLastCheckpoint = Cur->BytesInBGAtLastCheckpoint;
+        // Note that the first TransferBatches in both `Batches` may not be
+        // full.
+        // TODO: We may want to merge them if they can fit into one
+        // `TransferBatch`.
+        BG->Batches.append_back(&Cur->Batches);
+
+        if (Idx == MaxUnusedSize) {
+          ScopedLock L(BatchClassRegion->FLLock);
+          pushBatchClassBlocks(BatchClassRegion, Blocks, Idx);
+          Idx = 0;
+        }
+        Blocks[Idx++] =
+            compactPtr(SizeClassMap::BatchClassId, reinterpret_cast<uptr>(Cur));
+        Prev = BG;
+        BG = BG->Next;
+        continue;
+      }
+
       // At here, the `BG` is the first BatchGroup with CompactPtrGroupBase
       // larger than the first element in `GroupsToRelease`. We need to insert
       // `GroupsToRelease::front()` (which is `Cur` below)  before `BG`.
       //
       //   1. If `Prev` is nullptr, we simply push `Cur` to the front of
       //      FreeListInfo.BlockList.
       //   2. Otherwise, use `insert()` which inserts an element next to `Prev`.
       //
       // Afterwards, we don't need to advance `BG` because the order between
       // `BG` and the new `GroupsToRelease::front()` hasn't been checked.
-      BatchGroup *Cur = GroupsToRelease.front();
-      GroupsToRelease.pop_front();
       if (Prev == nullptr)
         Region->FreeListInfo.BlockList.push_front(Cur);
       else
         Region->FreeListInfo.BlockList.insert(Prev, Cur);
       DCHECK_EQ(Cur->Next, BG);
       Prev = Cur;
     }
 
-    DCHECK_EQ(Region->FreeListInfo.BlockList.size(), NumberOfBatchGroups);
-    (void)NumberOfBatchGroups;
+    if (Idx != 0) {
+      ScopedLock L(BatchClassRegion->FLLock);
+      pushBatchClassBlocks(BatchClassRegion, Blocks, Idx);
+    }
 
     if (SCUDO_DEBUG) {
       BatchGroup *Prev = Region->FreeListInfo.BlockList.front();
       for (BatchGroup *Cur = Prev->Next; Cur != nullptr;
            Prev = Cur, Cur = Cur->Next) {
         CHECK_LT(Prev->CompactPtrGroupBase, Cur->CompactPtrGroupBase);
       }
     }