[scudo][standalone] Android related improvements

[cryptoad]

Summary

This changes a few things to improve memory footprint and performances
on Android, and fixes a test compilation error:

• add stdlib.h to wrappers_c_test.cc to address https://bugs.llvm.org/show_bug.cgi?id=42810
• change Android size class maps, based on benchmarks, to improve performances and lower the Svelte memory footprint. Also change the 32-bit region size for said configuration
• change the reallocate logic to reallocate in place for sizes larger than the original chunk size, when they still fit in the same block. This addresses patterns from memory_replay dumps like the following:

202: realloc 0xb48fd000 0xb4930650 12352
202: realloc 0xb48fd000 0xb48fd000 12420
202: realloc 0xb48fd000 0xb48fd000 12492
202: realloc 0xb48fd000 0xb48fd000 12564
202: realloc 0xb48fd000 0xb48fd000 12636
202: realloc 0xb48fd000 0xb48fd000 12708
202: realloc 0xb48fd000 0xb48fd000 12780
202: realloc 0xb48fd000 0xb48fd000 12852
202: realloc 0xb48fd000 0xb48fd000 12924
202: realloc 0xb48fd000 0xb48fd000 12996
202: realloc 0xb48fd000 0xb48fd000 13068
202: realloc 0xb48fd000 0xb48fd000 13140
202: realloc 0xb48fd000 0xb48fd000 13212
202: realloc 0xb48fd000 0xb48fd000 13284
202: realloc 0xb48fd000 0xb48fd000 13356
202: realloc 0xb48fd000 0xb48fd000 13428
202: realloc 0xb48fd000 0xb48fd000 13500
202: realloc 0xb48fd000 0xb48fd000 13572
202: realloc 0xb48fd000 0xb48fd000 13644
202: realloc 0xb48fd000 0xb48fd000 13716
202: realloc 0xb48fd000 0xb48fd000 13788
...

In this situation we were deallocating the old chunk, and
allocating a new one for every single one of those, but now we can
keep the same chunk (we just updated the header), which saves some
heap operations.

[cryptoad]

Add a LIKELY to be compliant with our stance that Primary based
allocations are likelier.

[cryptoad]

SCM update.

[morehouse]

LGTM

lib/scudo/standalone/allocator_config.h

 };
 
 struct AndroidSvelteConfig {
   using SizeClassMap = SvelteSizeClassMap;
 #if SCUDO_CAN_USE_PRIMARY64
   // 512MB regions
   typedef SizeClassAllocator64<SizeClassMap, 29U> Primary;
 #else
-  // 256KB regions
-  typedef SizeClassAllocator32<SizeClassMap, 18U> Primary;
+  // 64KB regions
+  typedef SizeClassAllocator32<SizeClassMap, 16U> Primary;
 #endif
   template <class A>
   using TSDRegistryT = TSDRegistrySharedT<A, 1U>; // Shared, only 1 TSD.
 };
 
 struct FuchsiaConfig {
   // 1GB Regions
   typedef SizeClassAllocator64<DefaultSizeClassMap, 30U> Primary;

lib/scudo/standalone/combined.h

void *reallocate(void *OldPtr, uptr NewSize, uptr Alignment = MinAlignment) {
     // applications think that it is OK to realloc a memalign'ed pointer, which
     // will trigger this check. It really isn't.
     if (Options.DeallocTypeMismatch) {
       if (UNLIKELY(OldHeader.Origin != Chunk::Origin::Malloc))
         reportDeallocTypeMismatch(AllocatorAction::Reallocating, OldPtr,
                                   OldHeader.Origin, Chunk::Origin::Malloc);
     }
 
-    const uptr OldSize = getSize(OldPtr, &OldHeader);
-    // If the new size is identical to the old one, or lower but within an
-    // acceptable range, we just keep the old chunk, and update its header.
-    if (UNLIKELY(NewSize == OldSize))
-      return OldPtr;
-    if (NewSize < OldSize) {
-      const uptr Delta = OldSize - NewSize;
-      if (Delta < (SizeClassMap::MaxSize / 2)) {
+    void *BlockBegin = getBlockBegin(OldPtr, &OldHeader);
+    uptr BlockEnd;
+    uptr OldSize;
+    const uptr ClassId = OldHeader.ClassId;
+    if (LIKELY(ClassId)) {
+      BlockEnd = reinterpret_cast<uptr>(BlockBegin) +
+                 SizeClassMap::getSizeByClassId(ClassId);
+      OldSize = OldHeader.SizeOrUnusedBytes;
+    } else {
+      BlockEnd = SecondaryT::getBlockEnd(BlockBegin);
+      OldSize = BlockEnd -
+                (reinterpret_cast<uptr>(OldPtr) + OldHeader.SizeOrUnusedBytes);
+    }
+    // If the new chunk still fits in the previously allocated block (with a
+    // reasonable delta), we just keep the old block, and update the chunk
+    // header to reflect the size change.
+    if (reinterpret_cast<uptr>(OldPtr) + NewSize <= BlockEnd) {
+      const uptr Delta =
+          OldSize < NewSize ? NewSize - OldSize : OldSize - NewSize;
+      if (Delta <= SizeClassMap::MaxSize / 2) {
         Chunk::UnpackedHeader NewHeader = OldHeader;
         NewHeader.SizeOrUnusedBytes =
-            (OldHeader.ClassId ? NewHeader.SizeOrUnusedBytes - Delta
-                               : NewHeader.SizeOrUnusedBytes + Delta) &
+            (ClassId ? NewSize
+                     : BlockEnd - (reinterpret_cast<uptr>(OldPtr) + NewSize)) &
             Chunk::SizeOrUnusedBytesMask;
         Chunk::compareExchangeHeader(Cookie, OldPtr, &NewHeader, &OldHeader);
         return OldPtr;
       }
     }
 
     // Otherwise we allocate a new one, and deallocate the old one. Some
     // allocators will allocate an even larger chunk (by a fixed factor) to
     // allow for potential further in-place realloc. The gains of such a trick
     // are currently unclear.
     void *NewPtr = allocate(NewSize, Chunk::Origin::Malloc, Alignment);
     if (NewPtr) {
+      const uptr OldSize = getSize(OldPtr, &OldHeader);
       memcpy(NewPtr, OldPtr, Min(NewSize, OldSize));
       quarantineOrDeallocateChunk(OldPtr, &OldHeader, OldSize);
     }
     return NewPtr;
   }
 
   // TODO(kostyak): while this locks the Primary & Secondary, it still allows
   //                pointers to be fetched from the TSD. We ultimately want to

lib/scudo/standalone/size_class_map.h

static void validate() {
     }
   }
 };
 
 typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap;
 
 // TODO(kostyak): further tune class maps for Android & Fuchsia.
 #if SCUDO_WORDSIZE == 64U
-typedef SizeClassMap<3, 5, 8, 15, 8, 10> SvelteSizeClassMap;
+typedef SizeClassMap<4, 4, 8, 14, 4, 8> SvelteSizeClassMap;
 typedef SizeClassMap<3, 5, 8, 17, 14, 14> AndroidSizeClassMap;
 #else
-typedef SizeClassMap<3, 4, 7, 15, 8, 10> SvelteSizeClassMap;
-typedef SizeClassMap<3, 4, 7, 17, 14, 14> AndroidSizeClassMap;
+typedef SizeClassMap<4, 4, 8, 14, 4, 8> SvelteSizeClassMap;
+typedef SizeClassMap<3, 5, 8, 17, 14, 14> AndroidSizeClassMap;
 #endif
 
 } // namespace scudo
 
 #endif // SCUDO_SIZE_CLASS_MAP_H_

lib/scudo/standalone/tests/combined_test.cpp

while (Size > 1U) {
     void *NewP = Allocator->reallocate(P, Size);
     EXPECT_NE(NewP, nullptr);
     for (scudo::uptr J = 0; J < scudo::Min(Size, DataSize); J++)
       EXPECT_EQ((reinterpret_cast<char *>(NewP))[J], Marker);
     P = NewP;
   }
   Allocator->deallocate(P, Origin);
 
+  // Check that reallocating a chunk to a slightly smaller or larger size
+  // returns the same chunk. This requires that all the sizes we iterate on use
+  // the same block size, but that should be the case for 2048 with our default
+  // class size maps.
+  P  = Allocator->allocate(DataSize, Origin);
+  memset(P, Marker, DataSize);
+  for (scudo::sptr Delta = -32; Delta < 32; Delta += 8) {
+    const scudo::uptr NewSize = DataSize + Delta;
+    void *NewP = Allocator->reallocate(P, NewSize);
+    EXPECT_EQ(NewP, P);
+    for (scudo::uptr I = 0; I < scudo::Min(DataSize, NewSize); I++)
+      EXPECT_EQ((reinterpret_cast<char *>(NewP))[I], Marker);
+  }
+  Allocator->deallocate(P, Origin);
+
   // Allocates a bunch of chunks, then iterate over all the chunks, ensuring
   // they are the ones we allocated. This requires the allocator to not have any
   // other allocated chunk at this point (eg: won't work with the Quarantine).
   if (!UseQuarantine) {
     std::vector<void *> V;
     for (scudo::uptr I = 0; I < 64U; I++)
       V.push_back(Allocator->allocate(rand() % (MaxSize / 2U), Origin));
     Allocator->disable();

lib/scudo/standalone/tests/wrappers_c_test.cpp

 //===-- wrappers_c_test.cpp -------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "platform.h"
 
 #include "gtest/gtest.h"
 
 #include <limits.h>
 #include <malloc.h>
+#include <stdlib.h>
 #include <unistd.h>
 
 extern "C" {
 void malloc_enable(void);
 void malloc_disable(void);
 int malloc_iterate(uintptr_t base, size_t size,
                    void (*callback)(uintptr_t base, size_t size, void *arg),
                    void *arg);