[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

1015–1027

a

1035

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

1438–1439

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.
     ScopedLock L(Region->FLLock);
 
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr BytesInFreeList =
         Region->MemMapInfo.AllocatedUser - (Region->FreeListInfo.PoppedBlocks -
                                             Region->FreeListInfo.PushedBlocks) *
                                                BlockSize;
     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 of doing page
     //    release.
     // ====================================================================== //
     if (ReleaseType != ReleaseToOS::Force &&
         !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 to release the pages. Given that not all groups
     //    are available for releasing unused pages, we use some heuristic to
     //    select candidate groups.
     // ====================================================================== //
     SinglyLinkedList<BatchGroup> GroupsToRelease;
     if (ReleaseType == ReleaseToOS::Force) {
       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 certain class like `ScopedUnlock`. However, this
+    // form of locking is not supported by the thread-safety analysis. See
+    // https://clang.llvm.org/docs/ThreadSafetyAnalysis.html#no-alias-analysis
+    // for more details.
+    // TODO: Implement `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 step 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 (!Context.hasBlockMarked())
         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 need to
+    // recycle. The number of unused `BatchGroup` is expected to be small. Pick
+    // a constant which is inferred from some real programs.
+    constexpr uptr MaxUnusedSize = 8;
+    CompactPtrT Blocks[MaxUnusedSize];
+    u32 Idx = 0;
+    RegionInfo *BatchClassRegion = getRegionInfo(SizeClassMap::BatchClassId);
+    // To support releasing pages used by BatchClass, it has different logic in
+    // processing BatchGroups with same CompactPtrGroupBase and which is not
+    // implemented yet.
+    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);
       }
     }