[scudo][standalone] Correct min/max region indices

[cryptoad]

Summary

The original code to keep track of the minimum and maximum indices
of allocated 32-bit primary regions was sketchy at best.

MinRegionIndex & MaxRegionIndex were shared between all size
classes, and could (theoretically) have been updated concurrently. This
didn't materialize anywhere I could see, but still it's not proper.

This changes those min/max indices by making them class specific rather
than global: classes are locked when growing, so there is no
concurrency there. This also allows to simplify some of the 32-bit
release code, that now doesn't have to go through all the regions to
get the proper min/max. Iterate and unmap will no longer have access to
the global min/max, but they aren't used as much so this is fine.

[cryptoad]

Further simplify the release function.

[cryptoad]

Ping please!

[hctim]

LGTM w/ nits

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

169

If it's substantially cheaper to walk each class and get the region bounds, can you do the same thing for unmapTestOnly? If it's not a whole bunch cheaper, can you change this to just walk all the regions?

307

Instead of rematerializing, can you pass the size class info as a parameter from populateFreeList.

321

Probably didn't help because of the rematerialization, but can you add a comment here that Sci->Mutex is already locked by the caller?

[cferris]

Before submitting, this seems to have some performance issues. I see some cases where it's much better, but I see a lot of cases where it's much slower.

I'll put the list of the worst offenders and I need to dig to see if the data is good.

[cferris]

Okay, every calloc/malloc seems to be much slower. I'm going to rerun because it doesn't seem like this change should be causing this kind of problem.

[cryptoad]

Addressing review comments.

[cferris]

Ignore the performance drop, it looks like something else introduced a regression that I need to track down. This change doesn't change performance in any measurable way.

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

public:
 
   static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
 
   void initLinkerInitialized(s32 ReleaseToOsInterval) {
     if (SCUDO_FUCHSIA)
       reportError("SizeClassAllocator32 is not supported on Fuchsia");
 
     PossibleRegions.initLinkerInitialized();
-    MinRegionIndex = NumRegions; // MaxRegionIndex is already initialized to 0.
 
     u32 Seed;
     const u64 Time = getMonotonicTime();
     if (UNLIKELY(!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))))
       Seed = static_cast<u32>(
           Time ^ (reinterpret_cast<uptr>(SizeClassInfoArray) >> 6));
     const uptr PageSize = getPageSizeCached();
     for (uptr I = 0; I < NumClasses; I++) {
       SizeClassInfo *Sci = getSizeClassInfo(I);
       Sci->RandState = getRandomU32(&Seed);
+      // Sci->MaxRegionIndex is already initialized to 0.
+      Sci->MinRegionIndex = NumRegions;
       // See comment in the 64-bit primary about releasing smaller size classes.
       Sci->CanRelease = (I != SizeClassMap::BatchClassId) &&
                         (getSizeByClassId(I) >= (PageSize / 32));
       if (Sci->CanRelease)
         Sci->ReleaseInfo.LastReleaseAtNs = Time;
     }
     setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval));
   }
   void init(s32 ReleaseToOsInterval) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(ReleaseToOsInterval);
   }
 
   void unmapTestOnly() {
     while (NumberOfStashedRegions > 0)
       unmap(reinterpret_cast<void *>(RegionsStash[--NumberOfStashedRegions]),
             RegionSize);
-    for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++)
+    uptr MinRegionIndex = NumRegions, MaxRegionIndex = 0;
+    for (uptr I = 0; I < NumClasses; I++) {
+      SizeClassInfo *Sci = getSizeClassInfo(I);
+      if (Sci->MinRegionIndex < MinRegionIndex)
+        MinRegionIndex = Sci->MinRegionIndex;
+      if (Sci->MaxRegionIndex > MaxRegionIndex)
+        MaxRegionIndex = Sci->MaxRegionIndex;
+    }
+    for (uptr I = MinRegionIndex; I < MaxRegionIndex; I++)
       if (PossibleRegions[I])
         unmap(reinterpret_cast<void *>(I * RegionSize), RegionSize);
     PossibleRegions.unmapTestOnly();
   }
 
   TransferBatch *popBatch(CacheT *C, uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
void enable() {
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       getSizeClassInfo(I)->Mutex.unlock();
     }
   }
 
   template <typename F> void iterateOverBlocks(F Callback) {
+    uptr MinRegionIndex = NumRegions, MaxRegionIndex = 0;
+    for (uptr I = 0; I < NumClasses; I++) {
+      SizeClassInfo *Sci = getSizeClassInfo(I);
+      if (Sci->MinRegionIndex < MinRegionIndex)
+        MinRegionIndex = Sci->MinRegionIndex;
+      if (Sci->MaxRegionIndex > MaxRegionIndex)
+        MaxRegionIndex = Sci->MaxRegionIndex;
+    }
     for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++)
       if (PossibleRegions[I] &&
           (PossibleRegions[I] - 1U) != SizeClassMap::BatchClassId) {
         const uptr BlockSize = getSizeByClassId(PossibleRegions[I] - 1U);
         const uptr From = I * RegionSize;
         const uptr To = From + (RegionSize / BlockSize) * BlockSize;
         for (uptr Block = From; Block < To; Block += BlockSize)
           Callback(Block);
uptr releaseToOS() {
     for (uptr I = 0; I < NumClasses; I++) {
       SizeClassInfo *Sci = getSizeClassInfo(I);
       ScopedLock L(Sci->Mutex);
       TotalReleasedBytes += releaseToOSMaybe(Sci, I, /*Force=*/true);
     }
     return TotalReleasedBytes;
   }
 
-  static bool useMemoryTagging(Options Options) {
-    (void)Options;
-    return false;
-  }
+  static bool useMemoryTagging(UNUSED Options Options) { return false; }
   void disableMemoryTagging() {}
 
   const char *getRegionInfoArrayAddress() const { return nullptr; }
   static uptr getRegionInfoArraySize() { return 0; }
 
-  static BlockInfo findNearestBlock(const char *RegionInfoData, uptr Ptr) {
-    (void)RegionInfoData;
-    (void)Ptr;
+  static BlockInfo findNearestBlock(UNUSED const char *RegionInfoData,
+                                    UNUSED uptr Ptr) {
     return {};
   }
 
   AtomicOptions Options;
 
 private:
   static const uptr NumClasses = SizeClassMap::NumClasses;
   static const uptr RegionSize = 1UL << RegionSizeLog;
struct alignas(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {
     HybridMutex Mutex;
     SinglyLinkedList<TransferBatch> FreeList;
     uptr CurrentRegion;
     uptr CurrentRegionAllocated;
     SizeClassStats Stats;
     bool CanRelease;
     u32 RandState;
     uptr AllocatedUser;
+    // Lowest & highest region index allocated for this size class, to avoid
+    // looping through the whole NumRegions.
+    uptr MinRegionIndex;
+    uptr MaxRegionIndex;
     ReleaseToOsInfo ReleaseInfo;
   };
   static_assert(sizeof(SizeClassInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
 
   uptr computeRegionId(uptr Mem) {
     const uptr Id = Mem >> RegionSizeLog;
     CHECK_LT(Id, NumRegions);
     return Id;
if (isAligned(Region, RegionSize)) {
       MapSize = RegionSize;
     }
     const uptr End = Region + MapSize;
     if (End != MapEnd)
       unmap(reinterpret_cast<void *>(End), MapEnd - End);
     return Region;
   }
 
-  uptr allocateRegion(uptr ClassId) {
+  uptr allocateRegion(SizeClassInfo *Sci, uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     uptr Region = 0;
     {
       ScopedLock L(RegionsStashMutex);
       if (NumberOfStashedRegions > 0)
         Region = RegionsStash[--NumberOfStashedRegions];
     }
     if (!Region)
       Region = allocateRegionSlow();
     if (LIKELY(Region)) {
+      // Sci->Mutex is held by the caller, updating the Min/Max is safe.
       const uptr RegionIndex = computeRegionId(Region);
-      if (RegionIndex < MinRegionIndex)
-        MinRegionIndex = RegionIndex;
-      if (RegionIndex > MaxRegionIndex)
-        MaxRegionIndex = RegionIndex;
+      if (RegionIndex < Sci->MinRegionIndex)
+        Sci->MinRegionIndex = RegionIndex;
+      if (RegionIndex > Sci->MaxRegionIndex)
+        Sci->MaxRegionIndex = RegionIndex;
       PossibleRegions.set(RegionIndex, static_cast<u8>(ClassId + 1U));
     }
     return Region;
   }
 
   SizeClassInfo *getSizeClassInfo(uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     return &SizeClassInfoArray[ClassId];
   }
 
   NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
                                            SizeClassInfo *Sci) {
     uptr Region;
     uptr Offset;
     // If the size-class currently has a region associated to it, use it. The
     // newly created blocks will be located after the currently allocated memory
     // for that region (up to RegionSize). Otherwise, create a new region, where
     // the new blocks will be carved from the beginning.
     if (Sci->CurrentRegion) {
       Region = Sci->CurrentRegion;
       DCHECK_GT(Sci->CurrentRegionAllocated, 0U);
       Offset = Sci->CurrentRegionAllocated;
     } else {
       DCHECK_EQ(Sci->CurrentRegionAllocated, 0U);
-      Region = allocateRegion(ClassId);
+      Region = allocateRegion(Sci, ClassId);
       if (UNLIKELY(!Region))
         return nullptr;
       C->getStats().add(StatMapped, RegionSize);
       Sci->CurrentRegion = Region;
       Offset = 0;
     }
 
     const uptr Size = getSizeByClassId(ClassId);
Str->append("  %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
                 AvailableChunks, Rss >> 10, Sci->ReleaseInfo.RangesReleased);
   }
 
   NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
                                  bool Force = false) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();
 
-    CHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks);
+    DCHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks);
     const uptr BytesInFreeList =
         Sci->AllocatedUser -
         (Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks) * BlockSize;
     if (BytesInFreeList < PageSize)
       return 0; // No chance to release anything.
     const uptr BytesPushed =
         (Sci->Stats.PushedBlocks - Sci->ReleaseInfo.PushedBlocksAtLastRelease) *
         BlockSize;
if (!Force) {
         return 0;
       if (Sci->ReleaseInfo.LastReleaseAtNs +
               static_cast<u64>(IntervalMs) * 1000000 >
           getMonotonicTime()) {
         return 0; // Memory was returned recently.
       }
     }
 
-    DCHECK_GT(MinRegionIndex, 0U);
-    uptr First = 0;
-    for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {
-      if (PossibleRegions[I] - 1U == ClassId) {
-        First = I;
-        break;
-      }
-    }
-    uptr Last = 0;
-    for (uptr I = MaxRegionIndex; I >= MinRegionIndex; I--) {
-      if (PossibleRegions[I] - 1U == ClassId) {
-        Last = I;
-        break;
-      }
-    }
+    const uptr First = Sci->MinRegionIndex;
+    const uptr Last = Sci->MaxRegionIndex;
+    DCHECK_NE(Last, 0U);
+    DCHECK_LE(First, Last);
     uptr TotalReleasedBytes = 0;
-    auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {
-      return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;
-    };
-    if (First && Last) {
-      const uptr Base = First * RegionSize;
-      const uptr NumberOfRegions = Last - First + 1U;
-      ReleaseRecorder Recorder(Base);
-      releaseFreeMemoryToOS(Sci->FreeList, Base, RegionSize, NumberOfRegions,
-                            BlockSize, &Recorder, SkipRegion);
-      if (Recorder.getReleasedRangesCount() > 0) {
-        Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks;
-        Sci->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
-        Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
-        TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;
-      }
-    }
+    auto SkipRegion = [this, First, ClassId](uptr RegionIndex) {
+      return (PossibleRegions[First + RegionIndex] - 1U) != ClassId;
+    };
     Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
+
     return TotalReleasedBytes;
   }
 
   SizeClassInfo SizeClassInfoArray[NumClasses];
 
   // Track the regions in use, 0 is unused, otherwise store ClassId + 1.
   ByteMap PossibleRegions;
-  // Keep track of the lowest & highest regions allocated to avoid looping
-  // through the whole NumRegions.
-  uptr MinRegionIndex;
-  uptr MaxRegionIndex;
   atomic_s32 ReleaseToOsIntervalMs;
   // Unless several threads request regions simultaneously from different size
   // classes, the stash rarely contains more than 1 entry.
   static constexpr uptr MaxStashedRegions = 4;
   HybridMutex RegionsStashMutex;
   uptr NumberOfStashedRegions;
   uptr RegionsStash[MaxStashedRegions];
 };
 
 } // namespace scudo
 
 #endif // SCUDO_PRIMARY32_H_