[GWP-ASan] Update alignment on Android.

[hctim]

Summary

Android has different alignment requirements. You can read more about
them here
(https://cs.android.com/android/platform/superproject/+/master:bionic/tests/malloc_test.cpp;l=808),
but the general gist is that for malloc(x <= 8), we do malloc(8), and
for everything else, we do 16-byte alignment.

[eugenis]

LGTM

compiler-rt/lib/gwp_asan/platform_specific/utilities_posix.cpp

17

missing __ at the end

57

static constexpr

62

rename to "rightAlignedAllocationSize"? Otherwise it's not clear what the allocation size has to do with alignment.

compiler-rt/lib/gwp_asan/utilities.h

19

alignment is usually the actual number in bytes.
Call this AlignmentPolicy or something.

[morehouse]

Does Bionic's malloc have the required alignment information available at the call to gwp_asan::allocate? If so, we could get tighter right alignment by adding an alignment parameter (instead of conservative 16-byte rounding). This is the approach used in both Chrome and TCMalloc.

e.g., one of the most common malloc sizes is 24 (nodes in tree structures), which won't get perfectly right-aligned with the current approach, though it should be safe to do so.

[hctim]

In D74364#1868418, @morehouse wrote:

Does Bionic's malloc have the required alignment information available at the call to gwp_asan::allocate? If so, we could get tighter right alignment by adding an alignment parameter (instead of conservative 16-byte rounding). This is the approach used in both Chrome and TCMalloc.

e.g., one of the most common malloc sizes is 24 (nodes in tree structures), which won't get perfectly right-aligned with the current approach, though it should be safe to do so.

Unfortunately not, we're called directly from the malloc() family. Doesn't matter though, because...

As @pcc pointed out, the Android policy isn't eight-then-sixteen, it's actually "always align to 16 bytes if asked for an allocation with alignment 16-bytes, otherwise align 8-bytes", e.g.

malloc(5) => malloc(8)
malloc(9) => malloc(16)
malloc(17) => malloc(24)
malloc(16) => malloc(16), or if you're the backing allocator and there are no 16-byte buckets, you *must* use malloc(32), not malloc(24).

For our purposes, we can *always* ensure that a 16-byte allocation gets 16-bytes, and we only need to round to 8-bytes. Let me update the patchset.

[hctim]

• Update with eugenis@ comments and 8-byte alignment.

[hctim]

Just wanted to check, still LGTY @morehouse @eugenis?

[morehouse]

compiler-rt/lib/gwp_asan/options.inc

20–23

I'm not positive if its safe to go down to 8 bytes here. Until recently, there was an ambiguity in the standard that meant most mallocs used 16-byte alignment. It's gone now, but there may still be Android use cases that expect malloc(16+) to have the higher alignment (pretty sure this exists in Google3).

In TCMalloc, all operator news get 8-byte alignment by default while malloc and friends follow the memalign(16, size) path. But I don't know how Bionic does this...

22

Add space after .

compiler-rt/lib/gwp_asan/platform_specific/utilities_posix.cpp

14

Is this Bionic-specific, or Android generally?

40

static

46

static

54

Should this be the same for Android generally?

56

I think we should have a comment here explaining why rounding to 8 is sufficient for Android.

compiler-rt/lib/gwp_asan/tests/alignment.cpp

28

The test is called AlignToEight, but we expect alignments of 16, 24, etc.... Maybe call it AndroidAlignment and just use 8 or 16, since that's what we need.

And maybe add a comment explaining Android's alignment scheme.

[morehouse]

compiler-rt/lib/gwp_asan/options.inc

20–23

Regardless, I think we'll need 16-byte alignment for malloc() with size>=16. Unless malloc() doesn't follow the path with GWP-ASan sampling.

[hctim]

compiler-rt/lib/gwp_asan/options.inc

20–23

The "source of truth" for bionic is documented here: https://cs.android.com/android/platform/superproject/+/master:bionic/tests/malloc_test.cpp;l=808

So, in general, we currently are weak-aligned (with the current power-of-two alignment) for all platforms.

Android requires semi-strong alignment, where:

malloc(0 < x <= 8) => malloc(8)/malloc(16)/malloc(24)...

malloc(8 < x <= 16) => malloc(16)/malloc(32)/malloc(48)...

malloc(16 < x <= 24) => malloc(16)/malloc(24)/malloc(32)...

malloc(24 < x <= 32) => malloc(32)/malloc(48)/malloc(64)...

This guarantee is enforced by the aforementioned malloc.align_check test.

For GWP-ASan on Android, this mish-mash can be greatly simplified. As malloc(X) can *always* get exactly an X-sized allocation, we don't need to worry about the malloc(24 < x <= 32) case. This simplifies down to us only requiring 8-byte alignment.

I definitely agree we should consider enforcing strong alignment for general platforms. I'd like to (in future) change this option to use either perfect, strong, weak (current), or android alignment. I'll follow up with that later, but for now, I've just changed some wording to basically add an Android-specific strategy. The default (weak alignment) on all other platforms hasn't changed.

compiler-rt/lib/gwp_asan/platform_specific/utilities_posix.cpp

14

bionic-specific

54

No, we're specifically targeting Android Bionic here (and their guarantees). Android libc (for host) is a whole different kettle of fish.

56

Done above alignBionic.

[hctim]

• Fixed Matt's comments, and added some documentation.

[morehouse]

compiler-rt/lib/gwp_asan/tests/alignment.cpp

28

Nit: we technically don't care about alignments >16, so why test for them? (same for PowerOfTwo test)

[hctim]

compiler-rt/lib/gwp_asan/tests/alignment.cpp

28

We're not testing the alignment here, it's actually the mapping between asked size => real (aligned) size. Let me update the variable names to make this more clear.

[hctim]

• /s/AllocSizeToAlignment/AskedSizeToAlignedSize

[cryptoad]

compiler-rt/lib/gwp_asan/platform_specific/utilities_posix.cpp

87

I am getting a gcc error here:
control reaches end of non-void function [-Werror=return-type]

[hctim]

compiler-rt/lib/gwp_asan/platform_specific/utilities_posix.cpp

87

gcc's warning is wrong here (all paths lead to return), but i can fix it anyway.

compiler-rt/lib/gwp_asan/guarded_pool_allocator.h

private:
 
   // Reserve a slot for a new guarded allocation. Returns kInvalidSlotID if no
   // slot is available to be reserved.
   size_t reserveSlot();
 
   // Unreserve the guarded slot.
   void freeSlot(size_t SlotIndex);
 
-  // Returns the offset (in bytes) between the start of a guarded slot and where
-  // the start of the allocation should take place. Determined using the size of
-  // the allocation and the options provided at init-time.
-  uintptr_t allocationSlotOffset(size_t AllocationSize) const;
-
   // Raise a SEGV and set the corresponding fields in the Allocator's State in
   // order to tell the crash handler what happened. Used when errors are
   // detected internally (Double Free, Invalid Free).
   void trapOnAddress(uintptr_t Address, Error E);
 
   static GuardedPoolAllocator *getSingleton();
 
   // Install a pthread_atfork handler.

compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp

 //===-- guarded_pool_allocator.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 "gwp_asan/guarded_pool_allocator.h"
 
+#include "gwp_asan/optional/segv_handler.h"
 #include "gwp_asan/options.h"
+#include "gwp_asan/random.h"
 #include "gwp_asan/utilities.h"
-#include "optional/segv_handler.h"
 
 // RHEL creates the PRIu64 format macro (for printing uint64_t's) only when this
 // macro is defined before including <inttypes.h>.
 #ifndef __STDC_FORMAT_MACROS
 #define __STDC_FORMAT_MACROS 1
 #endif
 
 #include <assert.h>
size_t Index;
     ScopedLock L(PoolMutex);
     Index = reserveSlot();
   }
 
   if (Index == kInvalidSlotID)
     return nullptr;
 
   uintptr_t Ptr = State.slotToAddr(Index);
-  Ptr += allocationSlotOffset(Size);
+  // Should we right-align this allocation?
+  if (getRandomUnsigned32() % 2 == 0) {
+    AlignmentStrategy Align = AlignmentStrategy::DEFAULT;
+    if (PerfectlyRightAlign)
+      Align = AlignmentStrategy::PERFECT;
+    Ptr +=
+        State.maximumAllocationSize() - rightAlignedAllocationSize(Size, Align);
+  }
   AllocationMetadata *Meta = addrToMetadata(Ptr);
 
   // If a slot is multiple pages in size, and the allocation takes up a single
   // page, we can improve overflow detection by leaving the unused pages as
   // unmapped.
   markReadWrite(reinterpret_cast<void *>(getPageAddr(Ptr, State.PageSize)),
                 Size, kGwpAsanAliveSlotName);
 
size_t GuardedPoolAllocator::reserveSlot() {
   return SlotIndex;
 }
 
 void GuardedPoolAllocator::freeSlot(size_t SlotIndex) {
   assert(FreeSlotsLength < State.MaxSimultaneousAllocations);
   FreeSlots[FreeSlotsLength++] = SlotIndex;
 }
 
-uintptr_t GuardedPoolAllocator::allocationSlotOffset(size_t Size) const {
-  assert(Size > 0);
-
-  bool ShouldRightAlign = getRandomUnsigned32() % 2 == 0;
-  if (!ShouldRightAlign)
-    return 0;
-
-  uintptr_t Offset = State.maximumAllocationSize();
-  if (!PerfectlyRightAlign) {
-    if (Size == 3)
-      Size = 4;
-    else if (Size > 4 && Size <= 8)
-      Size = 8;
-    else if (Size > 8 && (Size % 16) != 0)
-      Size += 16 - (Size % 16);
-  }
-  Offset -= Size;
-  return Offset;
-}
-
 GWP_ASAN_TLS_INITIAL_EXEC
 GuardedPoolAllocator::ThreadLocalPackedVariables
     GuardedPoolAllocator::ThreadLocals;
 } // namespace gwp_asan

compiler-rt/lib/gwp_asan/options.inc

 
 GWP_ASAN_OPTION(bool, Enabled, true, "Is GWP-ASan enabled? Defaults to true.")
 
 GWP_ASAN_OPTION(
     bool, PerfectlyRightAlign, false,
     "When allocations are right-aligned, should we perfectly align them up to "
     "the page boundary? By default (false), we round up allocation size to the "
     "nearest power of two (1, 2, 4, 8, 16) up to a maximum of 16-byte "
-    "alignment for performance reasons. Setting this to true can find single "
-    "byte buffer-overflows for multibyte allocations at the cost of "
-    "performance, and may be incompatible with some architectures.")
+    "alignment for performance reasons. For Bionic, we use 8-byte alignment by "
+    "default. Setting this to true can find single byte buffer-overflows for "
+    "multibyte allocations at the cost of performance, and may be incompatible "
+    "with some architectures.")
 
 GWP_ASAN_OPTION(int, MaxSimultaneousAllocations, 16,
                 "Number of simultaneously-guarded allocations available in the "
                 "pool. Defaults to 16.")
 
 GWP_ASAN_OPTION(int, SampleRate, 5000,
                 "The probability (1 / SampleRate) that an allocation is "
                 "selected for GWP-ASan sampling. Default is 5000. Sample rates "

compiler-rt/lib/gwp_asan/platform_specific/utilities_posix.cpp

 //===-- utilities_posix.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 "gwp_asan/definitions.h"
 #include "gwp_asan/utilities.h"
 
-#ifdef ANDROID
+#include <assert.h>
+
+#ifdef __BIONIC__
 #include <stdlib.h>
 extern "C" GWP_ASAN_WEAK void android_set_abort_message(const char *);
-#else // ANDROID
+#else // __BIONIC__
 #include <stdio.h>
 #endif
 
 namespace gwp_asan {
 
-#ifdef ANDROID
+#ifdef __BIONIC__
 void Check(bool Condition, const char *Message) {
   if (Condition)
     return;
   if (&android_set_abort_message != nullptr)
     android_set_abort_message(Message);
   abort();
 }
-#else  // ANDROID
+#else  // __BIONIC__
 void Check(bool Condition, const char *Message) {
   if (Condition)
     return;
   fprintf(stderr, "%s", Message);
   __builtin_trap();
 }
-#endif // ANDROID
+#endif // __BIONIC__
+
+// See `bionic/tests/malloc_test.cpp` in the Android source for documentation
+// regarding their alignment guarantees. We always round up to the closest
+// 8-byte window. As GWP-ASan's malloc(X) can always get exactly an X-sized
+// allocation, an allocation that rounds up to 16-bytes will always be given a
+// 16-byte aligned allocation.
+static size_t alignBionic(size_t RealAllocationSize) {
+  if (RealAllocationSize % 8 == 0)
+    return RealAllocationSize;
+  return RealAllocationSize + 8 - (RealAllocationSize % 8);
+}
+
+static size_t alignPowerOfTwo(size_t RealAllocationSize) {
+  if (RealAllocationSize <= 2)
+    return RealAllocationSize;
+  if (RealAllocationSize <= 4)
+    return 4;
+  if (RealAllocationSize <= 8)
+    return 8;
+  if (RealAllocationSize % 16 == 0)
+    return RealAllocationSize;
+  return RealAllocationSize + 16 - (RealAllocationSize % 16);
+}
+
+#ifdef __BIONIC__
+static constexpr AlignmentStrategy PlatformDefaultAlignment =
+    AlignmentStrategy::ANDROID;
+#else  // __BIONIC__
+static constexpr AlignmentStrategy PlatformDefaultAlignment =
+    AlignmentStrategy::POWER_OF_TWO;
+#endif // __BIONIC__
+
+size_t rightAlignedAllocationSize(size_t RealAllocationSize,
+                                  AlignmentStrategy Align) {
+  assert(RealAllocationSize > 0);
+  if (Align == AlignmentStrategy::DEFAULT)
+    Align = PlatformDefaultAlignment;
+
+  switch (Align) {
+  case AlignmentStrategy::BIONIC:
+    return alignBionic(RealAllocationSize);
+  case AlignmentStrategy::POWER_OF_TWO:
+    return alignPowerOfTwo(RealAllocationSize);
+  case AlignmentStrategy::PERFECT:
+    return RealAllocationSize;
+  case AlignmentStrategy::DEFAULT:
+    __builtin_unreachable();
+  }
+}
 
 } // namespace gwp_asan

compiler-rt/lib/gwp_asan/tests/alignment.cpp

 //===-- alignment.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 "gwp_asan/tests/harness.h"
+#include "gwp_asan/utilities.h"
 
-TEST_F(DefaultGuardedPoolAllocator, BasicAllocation) {
-  std::vector<std::pair<int, int>> AllocSizeToAlignment = {
+TEST(AlignmentTest, PowerOfTwo) {
+  std::vector<std::pair<size_t, size_t>> AskedSizeToAlignedSize = {
       {1, 1},   {2, 2},   {3, 4},       {4, 4},       {5, 8},   {7, 8},
-      {8, 8},   {9, 16},  {15, 16},     {16, 16},     {17, 16}, {31, 16},
-      {32, 16}, {33, 16}, {4095, 4096}, {4096, 4096},
+      {8, 8},   {9, 16},  {15, 16},     {16, 16},     {17, 32}, {31, 32},
+      {32, 32}, {33, 48}, {4095, 4096}, {4096, 4096},
   };
 
-  for (const auto &KV : AllocSizeToAlignment) {
-    void *Ptr = GPA.allocate(KV.first);
-    EXPECT_NE(nullptr, Ptr);
+  for (const auto &KV : AskedSizeToAlignedSize) {
+    EXPECT_EQ(KV.second,
+              gwp_asan::rightAlignedAllocationSize(
+                  KV.first, gwp_asan::AlignmentStrategy::POWER_OF_TWO));
+  }
+}
+
+TEST(AlignmentTest, AlignBionic) {
+  std::vector<std::pair<size_t, size_t>> AskedSizeToAlignedSize = {
+      {1, 8},   {2, 8},   {3, 8},       {4, 8},       {5, 8},   {7, 8},
+      {8, 8},   {9, 16},  {15, 16},     {16, 16},     {17, 24}, {31, 32},
+      {32, 32}, {33, 40}, {4095, 4096}, {4096, 4096},
+  };
 
-    // Check the alignment of the pointer is as expected.
-    EXPECT_EQ(0u, reinterpret_cast<uintptr_t>(Ptr) % KV.second);
+  for (const auto &KV : AskedSizeToAlignedSize) {
+    EXPECT_EQ(KV.second, gwp_asan::rightAlignedAllocationSize(
+                             KV.first, gwp_asan::AlignmentStrategy::BIONIC));
+  }
+}
 
-    GPA.deallocate(Ptr);
+TEST(AlignmentTest, PerfectAlignment) {
+  for (size_t i = 1; i <= 4096; ++i) {
+    EXPECT_EQ(i, gwp_asan::rightAlignedAllocationSize(
+                     i, gwp_asan::AlignmentStrategy::PERFECT));
   }
 }

compiler-rt/lib/gwp_asan/utilities.h

 //===-- utilities.h ---------------------------------------------*- 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 "gwp_asan/definitions.h"
 
+#include <stddef.h>
+#include <stdint.h>
+
 namespace gwp_asan {
 // Checks that `Condition` is true, otherwise fails in a platform-specific way
 // with `Message`.
 void Check(bool Condition, const char *Message);
+
+enum class AlignmentStrategy {
+  // Default => POWER_OF_TWO on most platforms, BIONIC for Android Bionic.
+  DEFAULT,
+  POWER_OF_TWO,
+  BIONIC,
+  PERFECT,
+};
+
+// Returns the real size of a right-aligned allocation.
+size_t rightAlignedAllocationSize(
+    size_t RealAllocationSize,
+    AlignmentStrategy Align = AlignmentStrategy::DEFAULT);
 } // namespace gwp_asan