[scudo] Change aligned alloc functions to be more compliant & perf changes

[cryptoad]

Summary

We were not following the man documented behaviors for invalid arguments to
memalign and associated functions. Using CHECK for those was a bit extreme,
so we relax the behavior to return null pointers as expected when this happens.
Adapt the associated test.

I am using this change also to change a few more minor performance improvements:

• mark as UNLIKELY a bunch of unlikely conditions;
• the current CHECK in __sanitizer::RoundUpTo is redundant for us in *all* calls. So I am introducing our own version without said CHECK.
• change our combined allocator GetActuallyAllocatedSize. We already know if the pointer is from the Primary or Secondary, so the PointerIsMine check is redundant as well, and costly for the 32-bit Primary. So we get the size by directly using the available Primary functions.

Finally, change a int to uptr to avoid a warning/error when compiling on
Android.

[cryptoad]

Removing the CHECK line in the test that is no longer needed.

[alekseyshl]

lib/scudo/scudo_allocator.cpp

346

Why this one is likely? My guess would be that most pointers we get to check are valid. Is it not so?

583–584

Others use CallocShouldReturnNullDueToOverflow, maybe you can use it too?

666

Why nullptr, why not return FailureHandler::OnBadRequest()?

672

Same here

683

And here

lib/scudo/scudo_allocator.h

119

Please add a comment why you have your own RoundUpTo, otherwise someone later will "improve" the code back.

[cryptoad]

lib/scudo/scudo_allocator.cpp

346

So on this, I went back and forth. Basically this is a helper function that is only used for __sanitizer_get_ownership.
I assume that anything can be fed to this function, as opposed to only heap pointers.
The reasoning was that nullptr was less likely overall, but then I have no guarantee on alignments.

583–584

Good point. Will do.

666

Here and for the following comments, I guess my answer (which is debatable) is that it's not technically a bad request.
The man page for memalign, posix_memalign, and aligned_alloc says that hey return null for those specific cases.
Which, in my opinion, is different that trying to exceed a maximum alignment or size, or triggering an overflow in calloc.
As such I would lean towards this behavior as opposed to a failure or null based on an allocator setting.
Let me know if that makes sense.
If you judge that OnBadRequest is the way to go, I'll go that way, I am not strongly attached to the way I did it.

lib/scudo/scudo_allocator.h

119

Will do.

[alekseyshl]

lib/scudo/scudo_allocator.cpp

346

Makes sense.

583–584

D34799 renames it to CheckForCallocOverflow. Whoever is late to commit, gets to merge, I guess :)

666

My take on it is that we have a flag allocator_may_return_null and when it is == 0, our allocator should do just that, never return null. If the client desires the up to the spec behavior of those memory functions, they should specify allocator_may_return_null=1.

That way our behavior is consistent.

I'm open to debate too, there's always some space for improvements!

675–677

To follow the spec, we should check the result too:

if (!*MemPtr)

return errno_ENOMEM;

[cryptoad]

lib/scudo/scudo_allocator.cpp

666

I'll revisit that portion tomorrow and see how it checks out.

675–677

Yeah I wanted to talk to you about that.
Following what's in https://linux.die.net/man/3/malloc (look for ENOMEM) , we should probably set the errno in ReturnNullOrDieOnFailure::OnOOM (or whichever works better).

[cryptoad]

lib/scudo/scudo_allocator.cpp

675–677

I just realized there is no errno_ENOMEM. Do you know the reasoning behind having errno_E* as opposed to using the E* value itself?

[alekseyshl]

lib/scudo/scudo_allocator.cpp

675–677

Nope, I do not know the reason, and yes, you're right, we must set errno to ENOMEM in case of OOM (Windows expects the same, actually).

[cryptoad]

Addressing the review comments.
I will wait for D34799 to land anyway due to the switch to CheckForCallocOverflow.

[alekseyshl]

Or just go ahead and submit it, I'll merge with your changes.

lib/scudo/scudo_allocator.h

struct AP32 {
   typedef __scudo::ByteMap ByteMap;
   typedef NoOpMapUnmapCallback MapUnmapCallback;
   static const uptr kFlags =
       SizeClassAllocator32FlagMasks::kRandomShuffleChunks;
 };
 typedef SizeClassAllocator32<AP32> PrimaryAllocator;
 #endif  // SANITIZER_CAN_USE_ALLOCATOR64
 
+// __sanitizer::RoundUp has a CHECK that is extraneous for us. Use our own.
+INLINE uptr RoundUpTo(uptr Size, uptr Boundary) {
+  return (Size + Boundary - 1) & ~(Boundary - 1);
+}
+
 #include "scudo_allocator_secondary.h"
 #include "scudo_allocator_combined.h"
 
 typedef SizeClassAllocatorLocalCache<PrimaryAllocator> AllocatorCache;
 typedef ScudoLargeMmapAllocator SecondaryAllocator;
 typedef ScudoCombinedAllocator<PrimaryAllocator, AllocatorCache,
     SecondaryAllocator> ScudoBackendAllocator;
 

lib/scudo/scudo_allocator.cpp

 #include "scudo_allocator.h"
 #include "scudo_crc32.h"
 #include "scudo_tls.h"
 #include "scudo_utils.h"
 
 #include "sanitizer_common/sanitizer_allocator_interface.h"
 #include "sanitizer_common/sanitizer_quarantine.h"
 
-#include <limits.h>
-#include <pthread.h>
+#include <errno.h>
 #include <string.h>
 
 namespace __scudo {
 
 // Global static cookie, initialized at start-up.
 static uptr Cookie;
 
 // We default to software CRC32 if the alternatives are not supported, either
void init(const AllocatorOptions &Options) {
     BackendAllocator.InitCache(&FallbackAllocatorCache);
     FallbackPrng.initFromURandom();
     Cookie = FallbackPrng.getNext();
   }
 
   // Helper function that checks for a valid Scudo chunk. nullptr isn't.
   bool isValidPointer(const void *UserPtr) {
     initThreadMaybe();
-    if (!UserPtr)
+    if (UNLIKELY(!UserPtr))
       return false;
     uptr UserBeg = reinterpret_cast<uptr>(UserPtr);
     if (!IsAligned(UserBeg, MinAlignment))
       return false;
     return getScudoChunk(UserBeg)->isValid();
   }
 
   // Allocates a chunk.
   void *allocate(uptr Size, uptr Alignment, AllocType Type,
                  bool ForceZeroContents = false) {
     initThreadMaybe();
-    if (UNLIKELY(!IsPowerOfTwo(Alignment))) {
-      dieWithMessage("ERROR: alignment is not a power of 2\n");
-    }
-    if (Alignment > MaxAlignment)
+    if (UNLIKELY(Alignment > MaxAlignment))
       return FailureHandler::OnBadRequest();
-    if (Alignment < MinAlignment)
+    if (UNLIKELY(Alignment < MinAlignment))
       Alignment = MinAlignment;
-    if (Size >= MaxAllowedMallocSize)
+    if (UNLIKELY(Size >= MaxAllowedMallocSize))
       return FailureHandler::OnBadRequest();
-    if (Size == 0)
+    if (UNLIKELY(Size == 0))
       Size = 1;
 
     uptr NeededSize = RoundUpTo(Size, MinAlignment) + AlignedChunkHeaderSize;
     uptr AlignedSize = (Alignment > MinAlignment) ?
         NeededSize + (Alignment - AlignedChunkHeaderSize) : NeededSize;
-    if (AlignedSize >= MaxAllowedMallocSize)
+    if (UNLIKELY(AlignedSize >= MaxAllowedMallocSize))
       return FailureHandler::OnBadRequest();
 
     // 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;
     uptr Salt;
     uptr AllocationSize = FromPrimary ? AlignedSize : NeededSize;
     uptr AllocationAlignment = FromPrimary ? MinAlignment : Alignment;
     ScudoThreadContext *ThreadContext = getThreadContextAndLock();
     if (LIKELY(ThreadContext)) {
       Salt = getPrng(ThreadContext)->getNext();
       Ptr = BackendAllocator.Allocate(getAllocatorCache(ThreadContext),
                                       AllocationSize, AllocationAlignment,
                                       FromPrimary);
       ThreadContext->unlock();
     } else {
       SpinMutexLock l(&FallbackMutex);
       Salt = FallbackPrng.getNext();
       Ptr = BackendAllocator.Allocate(&FallbackAllocatorCache, AllocationSize,
                                       AllocationAlignment, FromPrimary);
     }
-    if (!Ptr)
+    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));
 
     UnpackedHeader Header = {};
     uptr AllocBeg = reinterpret_cast<uptr>(Ptr);
     uptr UserBeg = AllocBeg + AlignedChunkHeaderSize;
-    if (!IsAligned(UserBeg, Alignment)) {
+    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;
     }
void quarantineOrDeallocateChunk(ScudoChunk *Chunk, UnpackedHeader *Header,
     }
   }
 
   // Deallocates a Chunk, which means adding it to the delayed free list (or
   // Quarantine).
   void deallocate(void *UserPtr, uptr DeleteSize, AllocType Type) {
     initThreadMaybe();
     // if (&__sanitizer_free_hook) __sanitizer_free_hook(UserPtr);
-    if (!UserPtr)
+    if (UNLIKELY(!UserPtr))
       return;
     uptr UserBeg = reinterpret_cast<uptr>(UserPtr);
     if (UNLIKELY(!IsAligned(UserBeg, MinAlignment))) {
       dieWithMessage("ERROR: attempted to deallocate a chunk not properly "
                      "aligned at address %p\n", UserPtr);
     }
     ScudoChunk *Chunk = getScudoChunk(UserBeg);
     UnpackedHeader OldHeader;
if (NewPtr) {
       quarantineOrDeallocateChunk(Chunk, &OldHeader, UsableSize);
     }
     return NewPtr;
   }
 
   // Helper function that returns the actual usable size of a chunk.
   uptr getUsableSize(const void *Ptr) {
     initThreadMaybe();
-    if (!Ptr)
+    if (UNLIKELY(!Ptr))
       return 0;
     uptr UserBeg = reinterpret_cast<uptr>(Ptr);
     ScudoChunk *Chunk = getScudoChunk(UserBeg);
     UnpackedHeader Header;
     Chunk->loadHeader(&Header);
     // Getting the usable size of a chunk only makes sense if it's allocated.
     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();
-    uptr Total = NMemB * Size;
-    if (Size != 0 && Total / Size != NMemB)  // Overflow check
+    // TODO(kostyak): switch to CheckForCallocOverflow once D34799 lands.
+    if (CallocShouldReturnNullDueToOverflow(NMemB, Size))
       return FailureHandler::OnBadRequest();
-    return allocate(Total, MinAlignment, FromMalloc, true);
+    return allocate(NMemB * Size, MinAlignment, FromMalloc, true);
   }
 
   void commitBack(ScudoThreadContext *ThreadContext) {
     AllocatorCache *Cache = getAllocatorCache(ThreadContext);
     AllocatorQuarantine.Drain(getQuarantineCache(ThreadContext),
                               QuarantineCallback(Cache));
     BackendAllocator.DestroyCache(Cache);
   }

 void *scudoCalloc(uptr NMemB, uptr Size) {
   return Instance.calloc(NMemB, Size);
 }
 
 void *scudoValloc(uptr Size) {
   return Instance.allocate(Size, GetPageSizeCached(), FromMemalign);
 }
 
-void *scudoMemalign(uptr Alignment, uptr Size) {
-  return Instance.allocate(Size, Alignment, FromMemalign);
-}
-
 void *scudoPvalloc(uptr Size) {
   uptr PageSize = GetPageSizeCached();
   Size = RoundUpTo(Size, PageSize);
   if (Size == 0) {
     // pvalloc(0) should allocate one page.
     Size = PageSize;
   }
   return Instance.allocate(Size, PageSize, FromMemalign);
 }
 
+void *scudoMemalign(uptr Alignment, uptr Size) {
+  if (UNLIKELY(!IsPowerOfTwo(Alignment)))
+    return ScudoAllocator::FailureHandler::OnBadRequest();
+  return Instance.allocate(Size, Alignment, FromMemalign);
+}
+
 int scudoPosixMemalign(void **MemPtr, uptr Alignment, uptr Size) {
+  if (UNLIKELY(!IsPowerOfTwo(Alignment) || (Alignment % sizeof(void *)) != 0)) {
+    *MemPtr = ScudoAllocator::FailureHandler::OnBadRequest();
+    return EINVAL;
+  }
   *MemPtr = Instance.allocate(Size, Alignment, FromMemalign);
+  if (!*MemPtr)
+    return ENOMEM;
   return 0;
 }
 
 void *scudoAlignedAlloc(uptr Alignment, uptr Size) {
-  // size must be a multiple of the alignment. To avoid a division, we first
-  // make sure that alignment is a power of 2.
-  CHECK(IsPowerOfTwo(Alignment));
-  CHECK_EQ((Size & (Alignment - 1)), 0);
+  // Alignment must be a power of 2, Size must be a multiple of Alignment.
+  if (UNLIKELY(!IsPowerOfTwo(Alignment) || (Size & (Alignment - 1)) != 0))
+    return ScudoAllocator::FailureHandler::OnBadRequest();
   return Instance.allocate(Size, Alignment, FromMalloc);
 }
 
 uptr scudoMallocUsableSize(void *Ptr) {
   return Instance.getUsableSize(Ptr);
 }
 
 }  // namespace __scudo

lib/scudo/scudo_allocator_combined.h

void Deallocate(AllocatorCache *Cache, void *Ptr, bool FromPrimary) {
     if (FromPrimary)
       Cache->Deallocate(&Primary, Primary.GetSizeClass(Ptr), Ptr);
     else
       Secondary.Deallocate(&Stats, Ptr);
   }
 
   uptr GetActuallyAllocatedSize(void *Ptr, bool FromPrimary) {
     if (FromPrimary)
-      return Primary.GetActuallyAllocatedSize(Ptr);
+      return PrimaryAllocator::ClassIdToSize(Primary.GetSizeClass(Ptr));
     return Secondary.GetActuallyAllocatedSize(Ptr);
   }
 
   void InitCache(AllocatorCache *Cache) {
     Cache->Init(&Stats);
   }
 
   void DestroyCache(AllocatorCache *Cache) {

lib/scudo/scudo_tls_android.cpp

static void initOnce() {
   // testing, we create an unused key. Since the key_data array follows the tls
   // array, it basically gives us the extra entry we need.
   // TODO(kostyak): remove and restrict to N and above.
   CHECK_EQ(pthread_key_create(&PThreadKey, NULL), 0);
   initScudo();
   NumberOfContexts = getNumberOfCPUs();
   ThreadContexts = reinterpret_cast<ScudoThreadContext *>(
       MmapOrDie(sizeof(ScudoThreadContext) * NumberOfContexts, __func__));
-  for (int i = 0; i < NumberOfContexts; i++)
+  for (uptr i = 0; i < NumberOfContexts; i++)
     ThreadContexts[i].init();
 }
 
 void initThread() {
   pthread_once(&GlobalInitialized, initOnce);
   // Initial context assignment is done in a plain round-robin fashion.
   u32 Index = atomic_fetch_add(&ThreadContextCurrentIndex, 1,
                                memory_order_relaxed);

test/scudo/memalign.cpp

 // RUN: %clang_scudo %s -o %t
-// RUN:     %run %t valid   2>&1
-// RUN: not %run %t invalid 2>&1 | FileCheck %s
+// RUN: %run %t valid   2>&1
+// RUN: %run %t invalid 2>&1
 
 // Tests that the various aligned allocation functions work as intended. Also
 // tests for the condition where the alignment is not a power of 2.
 
 #include <assert.h>
+#include <errno.h>
 #include <malloc.h>
 #include <stdlib.h>
 #include <string.h>
 
 // Reduce the size of the quarantine, or the test can run out of aligned memory
 // on 32-bit for the larger alignments.
 extern "C" const char *__scudo_default_options() {
   return "QuarantineSizeMb=1";
 }
 
 // Sometimes the headers may not have this...
 extern "C" void *aligned_alloc (size_t alignment, size_t size);
 
 int main(int argc, char **argv)
 {
   void *p = nullptr;
   size_t alignment = 1U << 12;
   size_t size = 1U << 12;
+  int err;
 
   assert(argc == 2);
 
   if (!strcmp(argv[1], "valid")) {
     posix_memalign(&p, alignment, size);
     assert(p);
     free(p);
     p = aligned_alloc(alignment, size);
for (int i = 19; i <= 24; i++) {
       for (int k = 0; k < 3; k++) {
         p = memalign(alignment, 0x1000 - (2 * sizeof(void *) * k));
         assert(p);
         free(p);
       }
     }
   }
   if (!strcmp(argv[1], "invalid")) {
+    // Alignment is not a power of 2.
     p = memalign(alignment - 1, size);
-    free(p);
+    assert(!p);
+    // Size is not a multiple of alignment.
+    p = aligned_alloc(alignment, size >> 1);
+    assert(!p);
+    p = (void *)0x42UL;
+    // Alignment is not a power of 2.
+    err = posix_memalign(&p, 3, size);
+    assert(!p);
+    assert(err == EINVAL);
+    p = (void *)0x42UL;
+    // Alignment is a power of 2, but not a multiple of size(void *).
+    err = posix_memalign(&p, 2, size);
+    assert(!p);
+    assert(err == EINVAL);
   }
   return 0;
 }
-
-// CHECK: ERROR: alignment is not a power of 2