[scudo][standalone] Allow Primary allocations to fail up multiple times.

[cferris]

Summary

When enabling some malloc debug features on Android, multiple 32 bit
regions become exhausted, and the allocations fail. Allow allocations
to keep trying each bigger class in the Primary until it finds a fit.
In addition, some Android tests running on 32 bit fail sometimes due
to a running out of space in two regions, and then fail the allocation.

[cryptoad]

One of the things with this behavior is that it could have security repercussions, in the sense that we can lose the property of the separation per class size.
eg: by filling in all the previous class sizes, one could end up in another, allowing to properly exploit a UAF or overflow.
This is probably more theoretical than practical, but something to keep in mind for the future.

[MaskRay]

@cferris

Hi, you can drop Reviewers: Subscribers: Tags: and the text Summary: from the git commit with the following script:

arcfilter () {
        arc amend
        git log -1 --pretty=%B | awk '/Reviewers:|Subscribers:/{p=1} /Reviewed By:|Differential Revision:/{p=0} !p && !/^Summary:$/ {sub(/^Summary: /,"");print}' | git commit --amend --date=now -F -
}

Reviewed By: is considered important by some people. Please keep the tag. (I have updated my script to use --date=now (setting author date to committer date))

https://reviews.llvm.org/D80978 contains a git pre-push hook to automate this.

[cryptoad]

I did the commit and followed the instructions @ https://llvm.org/docs/Phabricator.html#committing-someone-s-change-from-phabricator.
Let me know if they are no longer relevant.

In D82070#2102280, @MaskRay wrote:

@cferris

Hi, you can drop Reviewers: Subscribers: Tags: and the text Summary: from the git commit with the following script:

arcfilter () {
        arc amend
        git log -1 --pretty=%B | awk '/Reviewers:|Subscribers:/{p=1} /Reviewed By:|Differential Revision:/{p=0} !p && !/^Summary:$/ {sub(/^Summary: /,"");print}' | git commit --amend --date=now -F -
}

Reviewed By: is considered important by some people. Please keep the tag. (I have updated my script to use --date=now (setting author date to committer date))

https://reviews.llvm.org/D80978 contains a git pre-push hook to automate this.

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

#endif // GWP_ASAN_HOOKS
     uptr ClassId = 0;
     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 dealing with the largest class, fallback to the Secondary.
+      // If the allocation failed, the most likely reason with a 32-bit primary
+      // is the region being full. In that event, retry in each successively
+      // larger class until it fits. If it fails to fit in the largest class,
+      // fallback to the Secondary.
       if (UNLIKELY(!Block)) {
-        if (ClassId < SizeClassMap::LargestClassId)
+        while (ClassId < SizeClassMap::LargestClassId) {
           Block = TSD->Cache.allocate(++ClassId);
-        else
+          if (LIKELY(Block)) {
+            break;
+          }
+        }
+        if (UNLIKELY(!Block)) {
           ClassId = 0;
         }
+      }
       if (UnlockRequired)
         TSD->unlock();
     }
     if (UNLIKELY(ClassId == 0))
       Block = Secondary.allocate(NeededSize, Alignment, &SecondaryBlockEnd,
                                  FillContents);
 
     if (UNLIKELY(!Block)) {

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

#else
   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 = 11;
+  static const scudo::uptr MaxSizeLog = 13;
   static const scudo::u32 MaxNumCachedHint = 4;
   static const scudo::uptr MaxBytesCachedLog = 12;
 };
 
 static const scudo::uptr DeathRegionSizeLog = 20U;
 struct DeathConfig {
-  // Tiny allocator, its Primary only serves chunks of two sizes.
+  // Tiny allocator, its Primary only serves chunks of four sizes.
   using DeathSizeClassMap = scudo::FixedSizeClassMap<DeathSizeClassConfig>;
   typedef scudo::SizeClassAllocator64<DeathSizeClassMap, DeathRegionSizeLog>
       Primary;
   typedef scudo::MapAllocator<scudo::MapAllocatorNoCache> Secondary;
   template <class A> using TSDRegistryT = scudo::TSDRegistrySharedT<A, 1U>;
 };
 
 TEST(ScudoCombinedTest, DeathCombined) {
TEST(ScudoCombinedTest, FullRegion) {
   Allocator->reset();
 
   std::vector<void *> V;
   scudo::uptr FailedAllocationsCount = 0;
   for (scudo::uptr ClassId = 1U;
        ClassId <= DeathConfig::DeathSizeClassMap::LargestClassId; ClassId++) {
     const scudo::uptr Size =
         DeathConfig::DeathSizeClassMap::getSizeByClassId(ClassId);
-    const scudo::uptr MaxNumberOfChunks = (1U << DeathRegionSizeLog) / Size;
+    // Allocate enough to fill all of the regions above this one.
+    const scudo::uptr MaxNumberOfChunks =
+        ((1U << DeathRegionSizeLog) / Size) *
+        (DeathConfig::DeathSizeClassMap::LargestClassId - ClassId + 1);
     void *P;
     for (scudo::uptr I = 0; I <= MaxNumberOfChunks; I++) {
       P = Allocator->allocate(Size - 64U, Origin);
       if (!P)
         FailedAllocationsCount++;
       else
         V.push_back(P);
     }
-  }
     while (!V.empty()) {
       Allocator->deallocate(V.back(), Origin);
       V.pop_back();
     }
+  }
   EXPECT_EQ(FailedAllocationsCount, 0U);
 }