[scudo] Finer lock granularity in Region of SizeClassAllocator64

[Chia-hungDuan]

Summary

[scudo] Finer lock granularity in Region of SizeClassAllocator64

In this CL, we introduce two new locks, MMLock for MemMap operations and
FLLock for freelist operations.

MMLock will be used when we want to manipulate pages. For example,
mapping more pages through populateFreeList() and releaseToOSMaybe().

FLLock will be used when we want to access the freelist. For example,
pushBlocks() and popBatch().

With the new locks, they increase the parallelism of the operations
mentioned above. For example, populateFreeList() won't block the
pushBlocks() when it's still doing the system call for more pages.

We also enforce lock hierarchy to avoid deadlock, MMLock is required to
be held before FLLock if you have to lock both of them. We don't store
the lock owner, therefore, we rely static thread-safey annotation to
detect any violation.

[Chia-hungDuan]

Fix the logic of pushing block of BatchClass

[Chia-hungDuan]

Add more comments

[Chia-hungDuan]

Acquire FLLock before entering releaseToOSMaybe()

[Chia-hungDuan]

Fix the use of tryLock() in popBatch()

[Chia-hungDuan]

Minor refactor in populateFreeList. Which is mainly for the dependent CLs

[cryptoad]

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

190

nit: const

499–501

Isn't RandState getting changed with every shuffle?

[Chia-hungDuan]

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

499–501

You're right. I forgot it's passed by reference in shuffle(). Will fix it in later CL

[Chia-hungDuan]

Mark RandState as guarded by MMLock and other review comment

[cferris]

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

168

to call

171

Use a condition

185

gets

189

Since the same locks aren't being held, I'm guessing you still want to do the stats printing after the loop to avoid holding MMLock. If so, you should probably put a comment here about that.

223

using a condition

228

Is there a reason you are using a variable here? It looks like the if statement below is the only time NeedToRefill is used.

[Chia-hungDuan]

Address review comment

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

228

I hope this variable will give the idea of why we check Size == 1U and that is a little bit unclear at the first glance. In the future change D152419, we add one more condition here so I think it may be better not to squeeze them in the predicate.

[cferris]

LGTM.

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

void unmapTestOnly() NO_THREAD_SAFETY_ANALYSIS {
     if (PrimaryBase)
       ReservedMemory.release();
     PrimaryBase = 0U;
   }
 
   TransferBatch *popBatch(CacheT *C, uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     RegionInfo *Region = getRegionInfo(ClassId);
-    bool PrintStats = false;
+
     {
-      ScopedLock L(Region->Mutex);
+      ScopedLock L(Region->FLLock);
       TransferBatch *B = popBatchImpl(C, ClassId, Region);
       if (LIKELY(B)) {
         Region->FreeListInfo.PoppedBlocks += B->getCount();
         return B;
       }
+    }
 
-      const bool RegionIsExhausted = Region->Exhausted;
-      if (UNLIKELY(RegionIsExhausted ||
-                   !populateFreeList(C, ClassId, Region))) {
-        PrintStats = !RegionIsExhausted && Region->Exhausted;
-      } else {
-        B = popBatchImpl(C, ClassId, Region);
-        // if `populateFreeList` succeeded, we are supposed to get free blocks.
-        DCHECK_NE(B, nullptr);
+    bool PrintStats = false;
+
+    while (true) {
+      // When two threads compete for `Region->MMLock`, we only want one of them
+      // to call populateFreeList(). To avoid both of them doing that, always
+      // check the freelist before mapping new pages.
+      //
+      // TODO(chiahungduan): Use a condition variable so that we don't need to
+      // hold `Region->MMLock` here.
+      ScopedLock ML(Region->MMLock);
+      {
+        ScopedLock FL(Region->FLLock);
+        TransferBatch *B = popBatchImpl(C, ClassId, Region);
+        if (LIKELY(B)) {
           Region->FreeListInfo.PoppedBlocks += B->getCount();
           return B;
         }
       }
 
+      const bool RegionIsExhausted = Region->Exhausted;
+      if (!RegionIsExhausted) {
+        // TODO: Make sure the one who does populateFreeList() gets one Batch
+        // here.
+        populateFreeList(C, ClassId, Region);
+      }
+      PrintStats = !RegionIsExhausted && Region->Exhausted;
+      if (Region->Exhausted)
+        break;
+    }
+
     // Note that `getStats()` requires locking each region so we can't call it
     // while locking the Region->Mutex in the above.
     if (UNLIKELY(PrintStats)) {
       ScopedString Str;
       getStats(&Str);
       Str.append(
           "Scudo OOM: The process has exhausted %zuM for size class %zu.\n",
           RegionSize >> 20, getSizeByClassId(ClassId));
       Str.output();
     }
+
     return nullptr;
   }
 
   // Push the array of free blocks to the designated batch group.
   void pushBlocks(CacheT *C, uptr ClassId, CompactPtrT *Array, u32 Size) {
     DCHECK_LT(ClassId, NumClasses);
     DCHECK_GT(Size, 0);
 
     RegionInfo *Region = getRegionInfo(ClassId);
     if (ClassId == SizeClassMap::BatchClassId) {
-      bool PrintStats = false;
-      {
-        ScopedLock L(Region->Mutex);
-        // Constructing a batch group in the free list will use two blocks in
-        // BatchClassId. If we are pushing BatchClassId blocks, we will use the
-        // blocks in the array directly (can't delegate local cache which will
-        // cause a recursive allocation). However, The number of free blocks may
-        // be less than two. Therefore, populate the free list before inserting
-        // the blocks.
+      // be less than two. Therefore, populate the freelist before inserting the
+      // blocks.
+      while (true) {
+        // TODO(chiahungduan): Move the lock right before the call of
+        // populateFreeList() by using a condition variable. See more details in
+        // the comment of popBatch().
+        ScopedLock L(Region->MMLock);
+        {
+          ScopedLock L(Region->FLLock);
           const bool NeedToRefill =
               Size == 1U && Region->FreeListInfo.BlockList.empty();
-        // If BatchClass has been exhausted, the program should have been
-        // aborted.
-        DCHECK(!Region->Exhausted);
-
-        if (UNLIKELY(
-                NeedToRefill &&
-                !populateFreeList(C, SizeClassMap::BatchClassId, Region))) {
-          PrintStats = true;
-        } else {
+          if (!NeedToRefill) {
             pushBlocksImpl(C, SizeClassMap::BatchClassId, Region, Array, Size);
             Region->FreeListInfo.PushedBlocks += Size;
+            return;
           }
         }
 
-      // Note that `getStats()` requires the lock of each region so we can't
-      // call it while locking the Region->Mutex in the above.
-      if (UNLIKELY(PrintStats)) {
-        ScopedString Str;
-        getStats(&Str);
-        Str.append(
-            "Scudo OOM: The process has exhausted %zuM for size class %zu.\n",
-            RegionSize >> 20, getSizeByClassId(ClassId));
-        Str.output();
-        // Theoretically, BatchClass shouldn't be used up. Abort immediately
-        // when it happens.
-        reportOutOfBatchClass();
-      }
+        if (UNLIKELY(!populateFreeList(C, SizeClassMap::BatchClassId, Region)))
+          break;
+      }
+
+      // At here, it hints that the BatchClass region has been used up. Dump the
+      // region stats before the program shutdown.
 
       return;
     }
 
     // TODO(chiahungduan): Consider not doing grouping if the group size is not
     // greater than the block size with a certain scale.
 
     // Sort the blocks so that blocks belonging to the same group can be pushed
     // together.
     bool SameGroup = true;
     for (u32 I = 1; I < Size; ++I) {
       if (compactPtrGroup(Array[I - 1]) != compactPtrGroup(Array[I]))
         SameGroup = false;
       CompactPtrT Cur = Array[I];
       u32 J = I;
       while (J > 0 && compactPtrGroup(Cur) < compactPtrGroup(Array[J - 1])) {
         Array[J] = Array[J - 1];
         --J;
       }
       Array[J] = Cur;
     }
 
-    ScopedLock L(Region->Mutex);
+    {
+      ScopedLock L(Region->FLLock);
       pushBlocksImpl(C, ClassId, Region, Array, Size, SameGroup);
-
       Region->FreeListInfo.PushedBlocks += Size;
-    if (ClassId != SizeClassMap::BatchClassId)
+    }
+
+    // Only non-BatchClass will be here, try to release the pages in the region.
+
+    // Note that the tryLock() may fail spuriously, given that it should rarely
+    // happen and page releasing is fine to skip, we don't take certain
+    // approaches to ensure one page release is done.
+    if (Region->MMLock.tryLock()) {
       releaseToOSMaybe(Region, ClassId);
+      Region->MMLock.unlock();
+    }
   }
 
   void disable() NO_THREAD_SAFETY_ANALYSIS {
     // The BatchClassId must be locked last since other classes can use it.
     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
       if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
         continue;
-      getRegionInfo(static_cast<uptr>(I))->Mutex.lock();
+      getRegionInfo(static_cast<uptr>(I))->MMLock.lock();
+      getRegionInfo(static_cast<uptr>(I))->FLLock.lock();
     }
-    getRegionInfo(SizeClassMap::BatchClassId)->Mutex.lock();
+    getRegionInfo(SizeClassMap::BatchClassId)->MMLock.lock();
+    getRegionInfo(SizeClassMap::BatchClassId)->FLLock.lock();
   }
 
   void enable() NO_THREAD_SAFETY_ANALYSIS {
-    getRegionInfo(SizeClassMap::BatchClassId)->Mutex.unlock();
+    getRegionInfo(SizeClassMap::BatchClassId)->FLLock.unlock();
+    getRegionInfo(SizeClassMap::BatchClassId)->MMLock.unlock();
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
-      getRegionInfo(I)->Mutex.unlock();
+      getRegionInfo(I)->FLLock.unlock();
+      getRegionInfo(I)->MMLock.unlock();
     }
   }
 
   template <typename F> void iterateOverBlocks(F Callback) {
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       RegionInfo *Region = getRegionInfo(I);
       // TODO: The call of `iterateOverBlocks` requires disabling
       // SizeClassAllocator64. We may consider locking each region on demand
       // only.
-      Region->Mutex.assertHeld();
+      Region->FLLock.assertHeld();
+      Region->MMLock.assertHeld();
       const uptr BlockSize = getSizeByClassId(I);
       const uptr From = Region->RegionBeg;
       const uptr To = From + Region->MemMapInfo.AllocatedUser;
       for (uptr Block = From; Block < To; Block += BlockSize)
         Callback(Block);
     }
   }
 
   void getStats(ScopedString *Str) {
     // TODO(kostyak): get the RSS per region.
     uptr TotalMapped = 0;
     uptr PoppedBlocks = 0;
     uptr PushedBlocks = 0;
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
-      ScopedLock L(Region->Mutex);
-      if (Region->MemMapInfo.MappedUser)
+      {
+        ScopedLock L(Region->MMLock);
         TotalMapped += Region->MemMapInfo.MappedUser;
+      }
+      {
+        ScopedLock L(Region->FLLock);
         PoppedBlocks += Region->FreeListInfo.PoppedBlocks;
         PushedBlocks += Region->FreeListInfo.PushedBlocks;
       }
+    }
     Str->append("Stats: SizeClassAllocator64: %zuM mapped (%uM rss) in %zu "
                 "allocations; remains %zu\n",
                 TotalMapped >> 20, 0U, PoppedBlocks,
                 PoppedBlocks - PushedBlocks);
 
     for (uptr I = 0; I < NumClasses; I++) {
       RegionInfo *Region = getRegionInfo(I);
-      ScopedLock L(Region->Mutex);
+      ScopedLock L1(Region->MMLock);
+      ScopedLock L2(Region->FLLock);
       getStats(Str, I, Region, 0);
     }
   }
 
   bool setOption(Option O, sptr Value) {
     if (O == Option::ReleaseInterval) {
       const s32 Interval = Max(Min(static_cast<s32>(Value),
                                    Config::Primary::MaxReleaseToOsIntervalMs),
                                Config::Primary::MinReleaseToOsIntervalMs);
       atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval);
       return true;
     }
     // Not supported by the Primary, but not an error either.
     return true;
   }
 
   uptr releaseToOS(ReleaseToOS ReleaseType) {
     uptr TotalReleasedBytes = 0;
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       RegionInfo *Region = getRegionInfo(I);
-      ScopedLock L(Region->Mutex);
+      ScopedLock L(Region->MMLock);
       TotalReleasedBytes += releaseToOSMaybe(Region, I, ReleaseType);
     }
     return TotalReleasedBytes;
   }
 
   const char *getRegionInfoArrayAddress() const {
     return reinterpret_cast<const char *>(RegionInfoArray);
   }
const RegionInfo *RegionInfoArray =
         reinterpret_cast<const RegionInfo *>(RegionInfoData);
 
     uptr ClassId;
     uptr MinDistance = -1UL;
     for (uptr I = 0; I != NumClasses; ++I) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       uptr Begin = RegionInfoArray[I].RegionBeg;
-      // TODO(chiahungduan): In fact, We need to lock the RegionInfo::Mutex.
+      // TODO(chiahungduan): In fact, We need to lock the RegionInfo::MMLock.
       // However, the RegionInfoData is passed with const qualifier and lock the
       // mutex requires modifying RegionInfoData, which means we need to remove
       // the const qualifier. This may lead to another undefined behavior (The
       // first one is accessing `AllocatedUser` without locking. It's better to
       // pass `RegionInfoData` as `void *` then we can lock the mutex properly.
       uptr End = Begin + RegionInfoArray[I].MemMapInfo.AllocatedUser;
       if (Begin > End || End - Begin < SizeClassMap::getSizeByClassId(I))
         continue;
struct PagesInfo {
     MemMapT MemMap = {};
     // Bytes mapped for user memory.
     uptr MappedUser = 0;
     // Bytes allocated for user memory.
     uptr AllocatedUser = 0;
   };
 
   struct UnpaddedRegionInfo {
-    HybridMutex Mutex;
-    // This is initialized before thread creation.
+    // Mutex for operations on freelist
+    HybridMutex FLLock;
+    // Mutex for memmap operations
+    HybridMutex MMLock ACQUIRED_BEFORE(FLLock);
+    // `RegionBeg` is initialized before thread creation and won't be changed.
     uptr RegionBeg = 0;
-    u32 RandState GUARDED_BY(Mutex) = 0;
-    BlocksInfo FreeListInfo GUARDED_BY(Mutex);
-    PagesInfo MemMapInfo GUARDED_BY(Mutex);
+    u32 RandState GUARDED_BY(MMLock) = 0;
+    BlocksInfo FreeListInfo GUARDED_BY(FLLock);
+    PagesInfo MemMapInfo GUARDED_BY(MMLock);
     // The minimum size of pushed blocks to trigger page release.
-    uptr TryReleaseThreshold GUARDED_BY(Mutex) = 0;
-    ReleaseToOsInfo ReleaseInfo GUARDED_BY(Mutex) = {};
-    bool Exhausted GUARDED_BY(Mutex) = false;
+    uptr TryReleaseThreshold GUARDED_BY(MMLock) = 0;
+    ReleaseToOsInfo ReleaseInfo GUARDED_BY(MMLock) = {};
+    bool Exhausted GUARDED_BY(MMLock) = false;
   };
   struct RegionInfo : UnpaddedRegionInfo {
     char Padding[SCUDO_CACHE_LINE_SIZE -
                  (sizeof(UnpaddedRegionInfo) % SCUDO_CACHE_LINE_SIZE)] = {};
   };
   static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
 
   // TODO: `PrimaryBase` can be obtained from ReservedMemory. This needs to be
private:
   // blocks, BGs are sorted and the input `Array` are supposed to be sorted so
   // that we can get better performance of maintaining sorted property.
   // Use `SameGroup=true` to indicate that all blocks in the array are from the
   // same group then we will skip checking the group id of each block.
   //
   // The region mutex needs to be held while calling this method.
   void pushBlocksImpl(CacheT *C, uptr ClassId, RegionInfo *Region,
                       CompactPtrT *Array, u32 Size, bool SameGroup = false)
-      REQUIRES(Region->Mutex) {
+      REQUIRES(Region->FLLock) {
     DCHECK_GT(Size, 0U);
 
     auto CreateGroup = [&](uptr CompactPtrGroupBase) {
       BatchGroup *BG = nullptr;
       TransferBatch *TB = nullptr;
       if (ClassId == SizeClassMap::BatchClassId) {
         DCHECK_GE(Size, 2U);
 
void pushBlocksImpl(CacheT *C, uptr ClassId, RegionInfo *Region,
     InsertBlocks(Cur, Array + Size - Count, Count);
   }
 
   // Pop one TransferBatch from a BatchGroup. The BatchGroup with the smallest
   // group id will be considered first.
   //
   // The region mutex needs to be held while calling this method.
   TransferBatch *popBatchImpl(CacheT *C, uptr ClassId, RegionInfo *Region)
-      REQUIRES(Region->Mutex) {
+      REQUIRES(Region->FLLock) {
     if (Region->FreeListInfo.BlockList.empty())
       return nullptr;
 
     SinglyLinkedList<TransferBatch> &Batches =
         Region->FreeListInfo.BlockList.front()->Batches;
     DCHECK(!Batches.empty());
 
     TransferBatch *B = Batches.front();
if (Batches.empty()) {
       if (ClassId != SizeClassMap::BatchClassId)
         C->deallocate(SizeClassMap::BatchClassId, BG);
     }
 
     return B;
   }
 
   NOINLINE bool populateFreeList(CacheT *C, uptr ClassId, RegionInfo *Region)
-      REQUIRES(Region->Mutex) {
+      REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
     const uptr Size = getSizeByClassId(ClassId);
     const u16 MaxCount = TransferBatch::getMaxCached(Size);
 
     const uptr RegionBeg = Region->RegionBeg;
     const uptr MappedUser = Region->MemMapInfo.MappedUser;
     const uptr TotalUserBytes =
         Region->MemMapInfo.AllocatedUser + MaxCount * Size;
     // Map more space for blocks, if necessary.
NOINLINE bool populateFreeList(CacheT *C, uptr ClassId, RegionInfo *Region)
     CompactPtrT ShuffleArray[ShuffleArraySize];
     DCHECK_LE(NumberOfBlocks, ShuffleArraySize);
 
     const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);
     uptr P = RegionBeg + Region->MemMapInfo.AllocatedUser;
     for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)
       ShuffleArray[I] = compactPtrInternal(CompactPtrBase, P);
 
+    ScopedLock L(Region->FLLock);
+
     if (ClassId != SizeClassMap::BatchClassId) {
       u32 N = 1;
       uptr CurGroup = compactPtrGroup(ShuffleArray[0]);
       for (u32 I = 1; I < NumberOfBlocks; I++) {
         if (UNLIKELY(compactPtrGroup(ShuffleArray[I]) != CurGroup)) {
           shuffle(ShuffleArray + I - N, N, &Region->RandState);
           pushBlocksImpl(C, ClassId, Region, ShuffleArray + I - N, N,
                          /*SameGroup=*/true);
NOINLINE bool populateFreeList(CacheT *C, uptr ClassId, RegionInfo *Region)
     const uptr AllocatedUser = Size * NumberOfBlocks;
     C->getStats().add(StatFree, AllocatedUser);
     Region->MemMapInfo.AllocatedUser += AllocatedUser;
 
     return true;
   }
 
   void getStats(ScopedString *Str, uptr ClassId, RegionInfo *Region, uptr Rss)
-      REQUIRES(Region->Mutex) {
+      REQUIRES(Region->MMLock, Region->FLLock) {
     if (Region->MemMapInfo.MappedUser == 0)
       return;
     const uptr InUse =
         Region->FreeListInfo.PoppedBlocks - Region->FreeListInfo.PushedBlocks;
     const uptr TotalChunks =
         Region->MemMapInfo.AllocatedUser / getSizeByClassId(ClassId);
     Str->append("%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
                 "inuse: %6zu total: %6zu rss: %6zuK releases: %6zu last "
                 "released: %6zuK region: 0x%zx (0x%zx)\n",
                 Region->Exhausted ? "F" : " ", ClassId,
                 getSizeByClassId(ClassId), Region->MemMapInfo.MappedUser >> 10,
                 Region->FreeListInfo.PoppedBlocks,
                 Region->FreeListInfo.PushedBlocks, InUse, TotalChunks,
                 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->Mutex) {
+      REQUIRES(Region->MMLock) EXCLUDES(Region->FLLock) {
+    // TODO(chiahungduan): Release `FLLock` when doing releaseFreeMemoryToOS().
+    ScopedLock L(Region->FLLock);
+
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();
 
     DCHECK_GE(Region->FreeListInfo.PoppedBlocks,
               Region->FreeListInfo.PushedBlocks);
     const uptr BytesInFreeList =
         Region->MemMapInfo.AllocatedUser - (Region->FreeListInfo.PoppedBlocks -
                                             Region->FreeListInfo.PushedBlocks) *