[scudo][standalone] Workaround for full regions on Android

[cryptoad]

Summary

Due to Unity, we had to reduce our region sizes, but in some rare
situations, some programs (mostly tests AFAICT) manage to fill up
a region for a given size class.

So this adds a workaround for that attempts to allocate the block
from the immediately larger size class, wasting some memory but
allowing the application to keep going.

[pcc]

LGTM

Does it make sense to write a test for this?

[hctim]

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

275

Why not do this for all platforms?

[cryptoad]

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

275

We had to reduce the region sizes on Android to 256MB, other platforms usually have 1GB or more, which makes them less likely to run out of space in the primary.
Since it only surfaced on Android, I figured I would spare the other platforms the additional code.

[cryptoad]

In D74567#1874708, @pcc wrote:

Does it make sense to write a test for this?

Yes I am working on one. The idea is to add another class to the DeathConfig, fill the 1024 one and make sure it keeps on going with the 2048 one.

[hctim]

LGTM w/ one suggestion

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

275

i'm not sure you're saving either runtime or code size here - i'd say just make the branch

if (UNLIKELY(!Block) && SCUDO_CAN_USE_PRIMARY64) {

Up to you though.

[cryptoad]

Adding the test here rather than later.
This made me realize that since the SizeClassAllocator64 is used on 32-bit
(region size permitting), the SCUDO_CAN_USE_PRIMARY64 check can't be applied.

[cryptoad]

The previous one didn't have the changes to the DeathConfig SCM.

[pcc]

LGTM

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

#endif // GWP_ASAN_HOOKS
     uptr ClassId;
     uptr SecondaryBlockEnd;
     if (LIKELY(PrimaryT::canAllocate(NeededSize))) {
       ClassId = SizeClassMap::getClassIdBySize(NeededSize);
       DCHECK_NE(ClassId, 0U);
       bool UnlockRequired;
       auto *TSD = TSDRegistry.getTSDAndLock(&UnlockRequired);
       Block = TSD->Cache.allocate(ClassId);
+      // If the allocation failed, the most likely reason with a 64-bit primary
+      // is the region being full. In that event, retry once using the
+      // immediately larger class (except if the failing class was already the
+      // largest). This will waste some memory but will allow the application to
+      // not fail.
+      if (SCUDO_ANDROID) {
+        if (UNLIKELY(!Block)) {
+          if (ClassId < SizeClassMap::LargestClassId)
+            Block = TSD->Cache.allocate(++ClassId);
+        }
+      }
       if (UnlockRequired)
         TSD->unlock();
     } else {
       ClassId = 0;
       Block = Secondary.allocate(NeededSize, Alignment, &SecondaryBlockEnd,
                                  ZeroContents);
     }
 

compiler-rt/lib/scudo/standalone/tests/combined_test.cpp

#if SCUDO_FUCHSIA
   testAllocatorThreaded<scudo::FuchsiaConfig>();
 #else
   testAllocatorThreaded<scudo::DefaultConfig>();
   UseQuarantine = true;
   testAllocatorThreaded<scudo::AndroidConfig>();
 #endif
 }
 
-
 struct DeathSizeClassConfig {
   static const scudo::uptr NumBits = 1;
   static const scudo::uptr MinSizeLog = 10;
   static const scudo::uptr MidSizeLog = 10;
   static const scudo::uptr MaxSizeLog = 10;
   static const scudo::u32 MaxNumCachedHint = 1;
   static const scudo::uptr MaxBytesCachedLog = 10;
 };
 
+static const scudo::uptr DeathRegionSizeLog = 20U;
 struct DeathConfig {
-  // Tiny allocator, its Primary only serves chunks of 1024 bytes.
+  // Tiny allocator, its Primary only serves chunks of two sizes.
   using DeathSizeClassMap = scudo::FixedSizeClassMap<DeathSizeClassConfig>;
-  typedef scudo::SizeClassAllocator64<DeathSizeClassMap, 20U> Primary;
+  typedef scudo::SizeClassAllocator64<DeathSizeClassMap, DeathRegionSizeLog>
+      Primary;
   typedef scudo::MapAllocator<scudo::MapAllocatorNoCache> Secondary;
   template <class A> using TSDRegistryT = scudo::TSDRegistrySharedT<A, 1U>;
 };
 
 TEST(ScudoCombinedTest, DeathCombined) {
   using AllocatorT = scudo::Allocator<DeathConfig>;
   auto Deleter = [](AllocatorT *A) {
     A->unmapTestOnly();
auto Deleter = [](AllocatorT *A) {
     delete A;
   };
   std::unique_ptr<AllocatorT, decltype(Deleter)> Allocator(new AllocatorT,
                                                            Deleter);
   Allocator->reset();
 
   Allocator->releaseToOS();
 }
+
+// Verify that when a region gets full, Android will still manage to
+// fulfill the allocation through a larger size class.
+TEST(ScudoCombinedTest, FullRegion) {
+  using AllocatorT = scudo::Allocator<DeathConfig>;
+  auto Deleter = [](AllocatorT *A) {
+    A->unmapTestOnly();
+    delete A;
+  };
+  std::unique_ptr<AllocatorT, decltype(Deleter)> Allocator(new AllocatorT,
+                                                           Deleter);
+  Allocator->reset();
+
+  const scudo::uptr Size = 1000U;
+  const scudo::uptr MaxNumberOfChunks =
+      (1U << DeathRegionSizeLog) /
+      DeathConfig::DeathSizeClassMap::getSizeByClassId(1U);
+  void *P;
+  std::vector<void *> V;
+  scudo::uptr FailedAllocationsCount = 0;
+  for (scudo::uptr I = 0; I <= MaxNumberOfChunks; I++) {
+    P = Allocator->allocate(Size, Origin);
+    if (!P)
+      FailedAllocationsCount++;
+    else
+      V.push_back(P);
+  }
+  while (!V.empty()) {
+    Allocator->deallocate(V.back(), Origin);
+    V.pop_back();
+  }
+  if (SCUDO_ANDROID)
+    EXPECT_EQ(FailedAllocationsCount, 0U);
+  else
+    EXPECT_GT(FailedAllocationsCount, 0U);
+}