[scudo][standalone] Minor optimization & improvements

[cryptoad]

Summary

A few small improvements and optimizations:

• when refilling the free list, push back the last batch and return the front one: this allows to keep the allocations towards the front of the region;
• instead of using 48 entries in the shuffle array, use a multiple of MaxNumCached;
• make the maximum number of batches to create on refil a constant; ultimately it should be configurable, but that's for later;
• initCache doesn't need to zero out the cache, it's already done.
• it turns out that when using || or &&, the compiler is adamant on adding a short circuit for every part of the expression. Which ends up making somewhat annoying asm with lots of test and conditional jump. I am changing that to bitwise | or & in two place so that the generated code looks better. Added comments since it might feel weird to people.

This yields to some small performance gains overall, nothing drastic
though.

[cryptoad]

And I forgot in the message the part about only checking Size and not NeededSize, adding compiler check to make sure we do not overflow a uptr.
This allows us to skip a check, and doesn't impact our security.

[hctim]

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

167

!!?

[hctim]

Other than that, LGTM

[cryptoad]

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

167

Options.ZeroContents is technically not a boolean, and I really want to have a boolean when using a bitwise or (since the logical or adds a long condition jump).
Hence the double logical not.

[hctim]

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

167

Maybe static_cast<bool>(Options.ZeroContents)? Looks more clear to me IMO, and compiles down to the same thing: https://godbolt.org/z/SrbU2p

[cryptoad]

Replacing the !! construct with a static_cast<bool>.

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

public:
 
   void unmapTestOnly() {
     TSDRegistry.unmapTestOnly();
     Primary.unmapTestOnly();
   }
 
   TSDRegistryT *getTSDRegistry() { return &TSDRegistry; }
 
-  void initCache(CacheT *Cache) { Cache->init(&Stats, &Primary); }
+  // The Cache must be provided zero-initialized.
+  void initCache(CacheT *Cache) {
+    Cache->initLinkerInitialized(&Stats, &Primary);
+  }
 
   // Release the resources used by a TSD, which involves:
   // - draining the local quarantine cache to the global quarantine;
   // - releasing the cached pointers back to the Primary;
   // - unlinking the local stats from the global ones (destroying the cache does
   //   the last two items).
   void commitBack(TSD<ThisT> *TSD) {
     Quarantine.drain(&TSD->QuarantineCache,
                      QuarantineCallback(*this, TSD->Cache));
     TSD->Cache.destroy(&Stats);
   }
 
   NOINLINE void *allocate(uptr Size, Chunk::Origin Origin,
                           uptr Alignment = MinAlignment,
                           bool ZeroContents = false) {
     initThreadMaybe();
-    ZeroContents = ZeroContents || Options.ZeroContents;
+    ZeroContents |= static_cast<bool>(Options.ZeroContents);
 
     if (UNLIKELY(Alignment > MaxAlignment)) {
       if (Options.MayReturnNull)
         return nullptr;
       reportAlignmentTooBig(Alignment, MaxAlignment);
     }
     if (Alignment < MinAlignment)
       Alignment = MinAlignment;
 
     // If the requested size happens to be 0 (more common than you might think),
     // allocate MinAlignment bytes on top of the header. Then add the extra
     // bytes required to fulfill the alignment requirements: we allocate enough
     // to be sure that there will be an address in the block that will satisfy
     // the alignment.
     const uptr NeededSize =
         roundUpTo(Size, MinAlignment) +
         ((Alignment > MinAlignment) ? Alignment : Chunk::getHeaderSize());
 
     // Takes care of extravagantly large sizes as well as integer overflows.
-    if (UNLIKELY(Size >= MaxAllowedMallocSize ||
-                 NeededSize >= MaxAllowedMallocSize)) {
+    COMPILER_CHECK(MaxAllowedMallocSize < UINTPTR_MAX - MaxAlignment);
+    if (UNLIKELY(Size >= MaxAllowedMallocSize)) {
       if (Options.MayReturnNull)
         return nullptr;
       reportAllocationSizeTooBig(Size, NeededSize, MaxAllowedMallocSize);
     }
+    DCHECK_LE(Size, NeededSize);
 
     void *Block;
     uptr ClassId;
     uptr BlockEnd;
     if (LIKELY(PrimaryT::canAllocate(NeededSize))) {
       ClassId = SizeClassMap::getClassIdBySize(NeededSize);
       DCHECK_NE(ClassId, 0U);
       bool UnlockRequired;
ALWAYS_INLINE void initThreadMaybe(bool MinimalInit = false) {
     TSDRegistry.initThreadMaybe(this, MinimalInit);
   }
 
   void quarantineOrDeallocateChunk(void *Ptr, Chunk::UnpackedHeader *Header,
                                    uptr Size) {
     Chunk::UnpackedHeader NewHeader = *Header;
     // If the quarantine is disabled, the actual size of a chunk is 0 or larger
     // than the maximum allowed, we return a chunk directly to the backend.
-    const bool BypassQuarantine = !Quarantine.getCacheSize() || !Size ||
+    // Logical Or can be short-circuited, which introduces unnecessary
+    // conditional jumps, so use bitwise Or and let the compiler be clever.
+    const bool BypassQuarantine = !Quarantine.getCacheSize() | !Size |
                                   (Size > Options.QuarantineMaxChunkSize);
     if (BypassQuarantine) {
       NewHeader.State = Chunk::State::Available;
       Chunk::compareExchangeHeader(Cookie, Ptr, &NewHeader, Header);
       void *BlockBegin = getBlockBegin(Ptr, &NewHeader);
       const uptr ClassId = NewHeader.ClassId;
       if (LIKELY(ClassId)) {
         bool UnlockRequired;

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

if (UNLIKELY(!Region))
       return nullptr;
     C->getStats().add(StatMapped, RegionSize);
     const uptr Size = getSizeByClassId(ClassId);
     const u32 MaxCount = TransferBatch::getMaxCached(Size);
     DCHECK_GT(MaxCount, 0);
     const uptr NumberOfBlocks = RegionSize / Size;
     DCHECK_GT(NumberOfBlocks, 0);
     TransferBatch *B = nullptr;
-    constexpr uptr ShuffleArraySize = 48;
+    constexpr u32 ShuffleArraySize = 8U * TransferBatch::MaxNumCached;
     void *ShuffleArray[ShuffleArraySize];
     u32 Count = 0;
-    const uptr AllocatedUser = NumberOfBlocks * Size;
+    const uptr AllocatedUser = Size * NumberOfBlocks;
     for (uptr I = Region; I < Region + AllocatedUser; I += Size) {
       ShuffleArray[Count++] = reinterpret_cast<void *>(I);
       if (Count == ShuffleArraySize) {
         if (UNLIKELY(!populateBatches(C, Sci, ClassId, &B, MaxCount,
                                       ShuffleArray, Count)))
           return nullptr;
         Count = 0;
       }
     }
     if (Count) {
       if (UNLIKELY(!populateBatches(C, Sci, ClassId, &B, MaxCount, ShuffleArray,
                                     Count)))
         return nullptr;
     }
     DCHECK(B);
+    if (!Sci->FreeList.empty()) {
+      Sci->FreeList.push_back(B);
+      B = Sci->FreeList.front();
+      Sci->FreeList.pop_front();
+    }
     DCHECK_GT(B->getCount(), 0);
 
     C->getStats().add(StatFree, AllocatedUser);
     Sci->AllocatedUser += AllocatedUser;
     if (Sci->CanRelease)
       Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
     return B;
   }

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

 
 private:
   static const uptr RegionSize = 1UL << RegionSizeLog;
   static const uptr NumClasses = SizeClassMap::NumClasses;
   static const uptr PrimarySize = RegionSize * NumClasses;
 
   // Call map for user memory with at least this size.
   static const uptr MapSizeIncrement = 1UL << 17;
+  // Fill at most this number of batches from the newly map'd memory.
+  static const u32 MaxNumBatches = 8U;
 
   struct RegionStats {
     uptr PoppedBlocks;
     uptr PushedBlocks;
   };
 
   struct ReleaseToOsInfo {
     uptr PushedBlocksAtLastRelease;
if (TotalUserBytes > MappedUser) {
       if (UNLIKELY(!map(reinterpret_cast<void *>(RegionBeg + MappedUser),
                         UserMapSize, "scudo:primary",
                         MAP_ALLOWNOMEM | MAP_RESIZABLE, &Region->Data)))
         return nullptr;
       Region->MappedUser += UserMapSize;
       C->getStats().add(StatMapped, UserMapSize);
     }
 
-    const uptr NumberOfBlocks = Min(
-        8UL * MaxCount, (Region->MappedUser - Region->AllocatedUser) / Size);
+    const u32 NumberOfBlocks = Min(
+        MaxNumBatches * MaxCount,
+        static_cast<u32>((Region->MappedUser - Region->AllocatedUser) / Size));
     DCHECK_GT(NumberOfBlocks, 0);
 
     TransferBatch *B = nullptr;
-    constexpr uptr ShuffleArraySize = 48;
+    constexpr u32 ShuffleArraySize =
+        MaxNumBatches * TransferBatch::MaxNumCached;
     void *ShuffleArray[ShuffleArraySize];
     u32 Count = 0;
     const uptr P = RegionBeg + Region->AllocatedUser;
-    const uptr AllocatedUser = NumberOfBlocks * Size;
+    const uptr AllocatedUser = Size * NumberOfBlocks;
     for (uptr I = P; I < P + AllocatedUser; I += Size) {
       ShuffleArray[Count++] = reinterpret_cast<void *>(I);
       if (Count == ShuffleArraySize) {
         if (UNLIKELY(!populateBatches(C, Region, ClassId, &B, MaxCount,
                                       ShuffleArray, Count)))
           return nullptr;
         Count = 0;
       }
     }
     if (Count) {
       if (UNLIKELY(!populateBatches(C, Region, ClassId, &B, MaxCount,
                                     ShuffleArray, Count)))
         return nullptr;
     }
     DCHECK(B);
+    if (!Region->FreeList.empty()) {
+      Region->FreeList.push_back(B);
+      B = Region->FreeList.front();
+      Region->FreeList.pop_front();
+    }
     DCHECK_GT(B->getCount(), 0);
 
     C->getStats().add(StatFree, AllocatedUser);
     Region->AllocatedUser += AllocatedUser;
     Region->Exhausted = false;
     if (Region->CanRelease)
       Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();