[scudo] Do not grab a cache for secondary allocation & per related changes

[cryptoad]

Summary

Secondary backed allocations do not require a cache. While it's not necessary
an issue when each thread has its cache, it becomes one with a shared pool of
caches (Android), as a Secondary backed allocation or deallocation holds a
cache that could be useful to another thread doing a Primary backed allocation.

We introduce an additional PRNG and its mutex (to avoid contention with the
Fallback one for Primary allocations) that will provide the Salt needed for
Secondary backed allocations.

I changed some of the code in a way that feels more readable to me (eg: using
some values directly rather than going through ternary assigned variables,
using directly true/false rather than FromPrimary). I will let reviewers
decide if it actually is.

An additional change is to mark CheckForCallocOverflow as UNLIKELY.

[alekseyshl]

lib/scudo/scudo_allocator.cpp

388

Now it feels like your combined allocator API should be AllocatePrimary/AllocateSecondary and the same for Deallocate/etc to do not pass useless params and branch on those.

389

Yep, it is more compact now, but I'd still add /*parameter name*/ comments next to those literals. They do help readability.

393

I believe you want to {} two lines above too.

428

Nit: I get why you did this, but now there's a logical disconnect between the size passed to the allocator and this statement.

[cryptoad]

lib/scudo/scudo_allocator.cpp

388

Sounds good.

389

Ok.

393

I am not sure I understand what you mean here.
The FallbackMutex encompasses both the Prng and the Cache, so I am using it for the whole else statement.

428

So bringing back AllocationSize here?

[alekseyshl]

lib/scudo/scudo_allocator.cpp

393

Ah, right, got carried away. Please ignore it.

428

If it does not affect performance (why should it, though?), yes, please bring it back.

[cryptoad]

Addressing Aleksey's comments:

• introduce allocate{Primary,Secondary} and their deallocation counterparts in the combined allocator. As explained in the comments, the Secondary functions do not require a Cache parameter, and the Primary allocation function doesn't require an Alignment parameter. That simplifies the prototypes;
• bring back AllocSize, add /*xxx=*/ for "inlined" parameters (which now is really only one instance of getActuallyAllocatedSize);

One additional change:

• the Combined functions were not compliant with the LLVM coding style, make them start with a lower case character. They were already "verb actions".

lib/scudo/scudo_allocator.cpp

void *getAllocBeg(UnpackedHeader *Header) {
     return reinterpret_cast<void *>(
         reinterpret_cast<uptr>(this) - (Header->Offset << MinAlignmentLog));
   }
 
   // Returns the usable size for a chunk, meaning the amount of bytes from the
   // beginning of the user data to the end of the backend allocated chunk.
   uptr getUsableSize(UnpackedHeader *Header) {
     uptr Size =
-        getBackendAllocator().GetActuallyAllocatedSize(getAllocBeg(Header),
+        getBackendAllocator().getActuallyAllocatedSize(getAllocBeg(Header),
                                                        Header->FromPrimary);
     if (Size == 0)
       return 0;
     return Size - AlignedChunkHeaderSize - (Header->Offset << MinAlignmentLog);
   }
 
   // Compute the checksum of the Chunk pointer and its ChunkHeader.
   u16 computeChecksum(UnpackedHeader *Header) const {
void Recycle(ScudoChunk *Chunk) {
     UnpackedHeader Header;
     Chunk->loadHeader(&Header);
     if (UNLIKELY(Header.State != ChunkQuarantine)) {
       dieWithMessage("ERROR: invalid chunk state when recycling address %p\n",
                      Chunk);
     }
     Chunk->eraseHeader();
     void *Ptr = Chunk->getAllocBeg(&Header);
-    getBackendAllocator().Deallocate(Cache_, Ptr, Header.FromPrimary);
+    if (Header.FromPrimary)
+      getBackendAllocator().deallocatePrimary(Cache_, Ptr);
+    else
+      getBackendAllocator().deallocateSecondary(Ptr);
   }
 
   // Internal quarantine allocation and deallocation functions. We first check
   // that the batches are indeed serviced by the Primary.
   // TODO(kostyak): figure out the best way to protect the batches.
   COMPILER_CHECK(sizeof(QuarantineBatch) < SizeClassMap::kMaxSize);
   void *Allocate(uptr Size) {
-    return getBackendAllocator().Allocate(Cache_, Size, MinAlignment, true);
+    return getBackendAllocator().allocatePrimary(Cache_, Size);
   }
 
   void Deallocate(void *Ptr) {
-    getBackendAllocator().Deallocate(Cache_, Ptr, true);
+    getBackendAllocator().deallocatePrimary(Cache_, Ptr);
   }
 
   AllocatorCache *Cache_;
 };
 
 typedef Quarantine<QuarantineCallback, ScudoChunk> ScudoQuarantine;
 typedef ScudoQuarantine::Cache ScudoQuarantineCache;
 COMPILER_CHECK(sizeof(ScudoQuarantineCache) <=
struct ScudoAllocator {
   static const uptr MaxAllowedMallocSize =
       FIRST_32_SECOND_64(2UL << 30, 1ULL << 40);
 
   typedef ReturnNullOrDieOnFailure FailureHandler;
 
   ScudoBackendAllocator BackendAllocator;
   ScudoQuarantine AllocatorQuarantine;
 
+  StaticSpinMutex GlobalPrngMutex;
+  ScudoPrng GlobalPrng;
+
   // The fallback caches are used when the thread local caches have been
   // 'detroyed' on thread tear-down. They are protected by a Mutex as they can
   // be accessed by different threads.
   StaticSpinMutex FallbackMutex;
   AllocatorCache FallbackAllocatorCache;
   ScudoQuarantineCache FallbackQuarantineCache;
   ScudoPrng FallbackPrng;
 
void init(const AllocatorOptions &Options) {
     // case of the Secondary allocator, it takes care of alignment and the
     // offset will always be 0. In the case of the Primary, the worst case
     // scenario happens in the last size class, when the backend allocation
     // would already be aligned on the requested alignment, which would happen
     // to be the maximum alignment that would fit in that size class. As a
     // result, the maximum offset will be at most the maximum alignment for the
     // last size class minus the header size, in multiples of MinAlignment.
     UnpackedHeader Header = {};
-    uptr MaxPrimaryAlignment = 1 << MostSignificantSetBitIndex(
-        SizeClassMap::kMaxSize - MinAlignment);
-    uptr MaxOffset = (MaxPrimaryAlignment - AlignedChunkHeaderSize) >>
-        MinAlignmentLog;
+    uptr MaxPrimaryAlignment =
+        1 << MostSignificantSetBitIndex(SizeClassMap::kMaxSize - MinAlignment);
+    uptr MaxOffset =
+        (MaxPrimaryAlignment - AlignedChunkHeaderSize) >> MinAlignmentLog;
     Header.Offset = MaxOffset;
     if (Header.Offset != MaxOffset) {
       dieWithMessage("ERROR: the maximum possible offset doesn't fit in the "
                      "header\n");
     }
     // Verify that we can fit the maximum size or amount of unused bytes in the
     // header. Given that the Secondary fits the allocation to a page, the worst
     // case scenario happens in the Primary. It will depend on the second to
     // last and last class sizes, as well as the dynamic base for the Primary.
     // The following is an over-approximation that works for our needs.
     uptr MaxSizeOrUnusedBytes = SizeClassMap::kMaxSize - 1;
     Header.SizeOrUnusedBytes = MaxSizeOrUnusedBytes;
     if (Header.SizeOrUnusedBytes != MaxSizeOrUnusedBytes) {
       dieWithMessage("ERROR: the maximum possible unused bytes doesn't fit in "
                      "the header\n");
     }
 
     DeallocationTypeMismatch = Options.DeallocationTypeMismatch;
     DeleteSizeMismatch = Options.DeleteSizeMismatch;
     ZeroContents = Options.ZeroContents;
     SetAllocatorMayReturnNull(Options.MayReturnNull);
-    BackendAllocator.Init(Options.ReleaseToOSIntervalMs);
+    BackendAllocator.init(Options.ReleaseToOSIntervalMs);
     AllocatorQuarantine.Init(
         static_cast<uptr>(Options.QuarantineSizeMb) << 20,
         static_cast<uptr>(Options.ThreadLocalQuarantineSizeKb) << 10);
-    BackendAllocator.InitCache(&FallbackAllocatorCache);
+    GlobalPrng.init();
+    Cookie = GlobalPrng.getU64();
+    BackendAllocator.initCache(&FallbackAllocatorCache);
     FallbackPrng.init();
-    Cookie = FallbackPrng.getU64();
   }
 
   // Helper function that checks for a valid Scudo chunk. nullptr isn't.
   bool isValidPointer(const void *UserPtr) {
     initThreadMaybe();
     if (UNLIKELY(!UserPtr))
       return false;
     uptr UserBeg = reinterpret_cast<uptr>(UserPtr);
void *allocate(uptr Size, uptr Alignment, AllocType Type,
 
     // Primary and Secondary backed allocations have a different treatment. We
     // deal with alignment requirements of Primary serviced allocations here,
     // but the Secondary will take care of its own alignment needs.
     bool FromPrimary = PrimaryAllocator::CanAllocate(AlignedSize, MinAlignment);
 
     void *Ptr;
     u8 Salt;
-    uptr AllocationSize = FromPrimary ? AlignedSize : NeededSize;
-    uptr AllocationAlignment = FromPrimary ? MinAlignment : Alignment;
+    uptr AllocSize;
+    if (FromPrimary) {
+      AllocSize = AlignedSize;
       ScudoThreadContext *ThreadContext = getThreadContextAndLock();
       if (LIKELY(ThreadContext)) {
         Salt = getPrng(ThreadContext)->getU8();
-      Ptr = BackendAllocator.Allocate(getAllocatorCache(ThreadContext),
-                                      AllocationSize, AllocationAlignment,
-                                      FromPrimary);
+        Ptr = BackendAllocator.allocatePrimary(getAllocatorCache(ThreadContext),
+                                               AllocSize);
         ThreadContext->unlock();
       } else {
         SpinMutexLock l(&FallbackMutex);
         Salt = FallbackPrng.getU8();
-      Ptr = BackendAllocator.Allocate(&FallbackAllocatorCache, AllocationSize,
-                                      AllocationAlignment, FromPrimary);
+        Ptr = BackendAllocator.allocatePrimary(&FallbackAllocatorCache,
+                                               AllocSize);
+      }
+    } else {
+      {
+        SpinMutexLock l(&GlobalPrngMutex);
+        Salt = GlobalPrng.getU8();
+      }
+      AllocSize = NeededSize;
+      Ptr = BackendAllocator.allocateSecondary(AllocSize, Alignment);
     }
     if (UNLIKELY(!Ptr))
       return FailureHandler::OnOOM();
 
     // If requested, we will zero out the entire contents of the returned chunk.
     if ((ForceZeroContents || ZeroContents) && FromPrimary)
-       memset(Ptr, 0,
-              BackendAllocator.GetActuallyAllocatedSize(Ptr, FromPrimary));
+      memset(Ptr, 0, BackendAllocator.getActuallyAllocatedSize(
+          Ptr, /*FromPrimary=*/true));
 
     UnpackedHeader Header = {};
     uptr AllocBeg = reinterpret_cast<uptr>(Ptr);
     uptr UserBeg = AllocBeg + AlignedChunkHeaderSize;
     if (UNLIKELY(!IsAligned(UserBeg, Alignment))) {
       // Since the Secondary takes care of alignment, a non-aligned pointer
       // means it is from the Primary. It is also the only case where the offset
       // field of the header would be non-zero.
       CHECK(FromPrimary);
       UserBeg = RoundUpTo(UserBeg, Alignment);
       uptr Offset = UserBeg - AlignedChunkHeaderSize - AllocBeg;
       Header.Offset = Offset >> MinAlignmentLog;
     }
-    CHECK_LE(UserBeg + Size, AllocBeg + AllocationSize);
+    CHECK_LE(UserBeg + Size, AllocBeg + AllocSize);
     Header.State = ChunkAllocated;
     Header.AllocType = Type;
     if (FromPrimary) {
-      Header.FromPrimary = FromPrimary;
+      Header.FromPrimary = 1;
       Header.SizeOrUnusedBytes = Size;
     } else {
       // The secondary fits the allocations to a page, so the amount of unused
       // bytes is the difference between the end of the user allocation and the
       // next page boundary.
       uptr PageSize = GetPageSizeCached();
       uptr TrailingBytes = (UserBeg + Size) & (PageSize - 1);
       if (TrailingBytes)
         Header.SizeOrUnusedBytes = PageSize - TrailingBytes;
     }
-    Header.Salt = static_cast<u8>(Salt);
+    Header.Salt = Salt;
     getScudoChunk(UserBeg)->storeHeader(&Header);
     void *UserPtr = reinterpret_cast<void *>(UserBeg);
     // if (&__sanitizer_malloc_hook) __sanitizer_malloc_hook(UserPtr, Size);
     return UserPtr;
   }
 
   // Place a chunk in the quarantine. In the event of a zero-sized quarantine,
   // we directly deallocate the chunk, otherwise the flow would lead to the
   // chunk being loaded (and checked) twice, and stored (and checksummed) once,
   // with no additional security value.
   void quarantineOrDeallocateChunk(ScudoChunk *Chunk, UnpackedHeader *Header,
                                    uptr Size) {
     bool FromPrimary = Header->FromPrimary;
     bool BypassQuarantine = (AllocatorQuarantine.GetCacheSize() == 0);
     if (BypassQuarantine) {
       Chunk->eraseHeader();
       void *Ptr = Chunk->getAllocBeg(Header);
+      if (FromPrimary) {
         ScudoThreadContext *ThreadContext = getThreadContextAndLock();
         if (LIKELY(ThreadContext)) {
-        getBackendAllocator().Deallocate(getAllocatorCache(ThreadContext), Ptr,
-                                         FromPrimary);
+          getBackendAllocator().deallocatePrimary(
+              getAllocatorCache(ThreadContext), Ptr);
           ThreadContext->unlock();
         } else {
           SpinMutexLock Lock(&FallbackMutex);
-        getBackendAllocator().Deallocate(&FallbackAllocatorCache, Ptr,
-                                         FromPrimary);
+          getBackendAllocator().deallocatePrimary(&FallbackAllocatorCache, Ptr);
+        }
+      } else {
+        getBackendAllocator().deallocateSecondary(Ptr);
       }
     } else {
       UnpackedHeader NewHeader = *Header;
       NewHeader.State = ChunkQuarantine;
       Chunk->compareExchangeHeader(&NewHeader, Header);
       ScudoThreadContext *ThreadContext = getThreadContextAndLock();
       if (LIKELY(ThreadContext)) {
         AllocatorQuarantine.Put(getQuarantineCache(ThreadContext),
if (UNLIKELY(Header.State != ChunkAllocated)) {
       dieWithMessage("ERROR: invalid chunk state when sizing address %p\n",
                      Ptr);
     }
     return Chunk->getUsableSize(&Header);
   }
 
   void *calloc(uptr NMemB, uptr Size) {
     initThreadMaybe();
-    if (CheckForCallocOverflow(NMemB, Size))
+    if (UNLIKELY(CheckForCallocOverflow(NMemB, Size)))
       return FailureHandler::OnBadRequest();
     return allocate(NMemB * Size, MinAlignment, FromMalloc, true);
   }
 
   void commitBack(ScudoThreadContext *ThreadContext) {
     AllocatorCache *Cache = getAllocatorCache(ThreadContext);
     AllocatorQuarantine.Drain(getQuarantineCache(ThreadContext),
                               QuarantineCallback(Cache));
-    BackendAllocator.DestroyCache(Cache);
+    BackendAllocator.destroyCache(Cache);
   }
 
   uptr getStats(AllocatorStat StatType) {
     initThreadMaybe();
     uptr stats[AllocatorStatCount];
-    BackendAllocator.GetStats(stats);
+    BackendAllocator.getStats(stats);
     return stats[StatType];
   }
 };
 
 static ScudoAllocator Instance(LINKER_INITIALIZED);
 
 static ScudoBackendAllocator &getBackendAllocator() {
   return Instance.BackendAllocator;
 }
 
 static void initScudoInternal(const AllocatorOptions &Options) {
   Instance.init(Options);
 }
 
 void ScudoThreadContext::init() {
-  getBackendAllocator().InitCache(&Cache);
+  getBackendAllocator().initCache(&Cache);
   Prng.init();
   memset(QuarantineCachePlaceHolder, 0, sizeof(QuarantineCachePlaceHolder));
 }
 
 void ScudoThreadContext::commitBack() {
   Instance.commitBack(this);
 }
 

lib/scudo/scudo_allocator_combined.h

 #ifndef SCUDO_ALLOCATOR_H_
 #error "This file must be included inside scudo_allocator.h."
 #endif
 
 template <class PrimaryAllocator, class AllocatorCache,
     class SecondaryAllocator>
 class ScudoCombinedAllocator {
  public:
-  void Init(s32 ReleaseToOSIntervalMs) {
+  void init(s32 ReleaseToOSIntervalMs) {
     Primary.Init(ReleaseToOSIntervalMs);
     Secondary.Init();
     Stats.Init();
   }
 
-  void *Allocate(AllocatorCache *Cache, uptr Size, uptr Alignment,
-                 bool FromPrimary) {
-    if (FromPrimary)
-      return Cache->Allocate(&Primary, Primary.ClassID(Size));
+  // Primary allocations are always MinAlignment aligned, and as such do not
+  // require an Alignment parameter.
+  void *allocatePrimary(AllocatorCache *Cache, uptr Size) {
+  }
+
+  // Secondary allocations do not require a Cache, but do require an Alignment
+  // parameter.
+  void *allocateSecondary(uptr Size, uptr Alignment) {
     return Secondary.Allocate(&Stats, Size, Alignment);
   }
 
-  void Deallocate(AllocatorCache *Cache, void *Ptr, bool FromPrimary) {
-    if (FromPrimary)
-      Cache->Deallocate(&Primary, Primary.GetSizeClass(Ptr), Ptr);
-    else
-      Secondary.Deallocate(&Stats, Ptr);
+  void deallocatePrimary(AllocatorCache *Cache, void *Ptr) {
+  }
+
+  void deallocateSecondary(void *Ptr) {
   }
 
-  uptr GetActuallyAllocatedSize(void *Ptr, bool FromPrimary) {
+  uptr getActuallyAllocatedSize(void *Ptr, bool FromPrimary) {
     if (FromPrimary)
       return PrimaryAllocator::ClassIdToSize(Primary.GetSizeClass(Ptr));
     return Secondary.GetActuallyAllocatedSize(Ptr);
   }
 
-  void InitCache(AllocatorCache *Cache) {
+  void initCache(AllocatorCache *Cache) {
     Cache->Init(&Stats);
   }
 
-  void DestroyCache(AllocatorCache *Cache) {
+  void destroyCache(AllocatorCache *Cache) {
     Cache->Destroy(&Primary, &Stats);
   }
 
-  void GetStats(AllocatorStatCounters StatType) const {
+  void getStats(AllocatorStatCounters StatType) const {
     Stats.Get(StatType);
   }
 
  private:
   PrimaryAllocator Primary;
   SecondaryAllocator Secondary;
   AllocatorGlobalStats Stats;
 };
 
 #endif  // SCUDO_ALLOCATOR_COMBINED_H_