scudo: Interleave odd and even tags for adjacent blocks.

[pcc]

Summary

This guarantees that we will detect a buffer overflow or underflow
that overwrites an adjacent block. This spatial guarantee is similar
to the temporal guarantee that we provide for immediate use-after-free.

Enabling odd/even tags involves a tradeoff between use-after-free
detection and buffer overflow detection. Odd/even tags make it more
likely for buffer overflows to be detected by increasing the size of
the guaranteed "red zone" around the allocation, but on the other
hand use-after-free is less likely to be detected because the tag
space for any particular chunk is cut in half. Therefore we introduce
a tuning setting to control whether odd/even tags are enabled.

[pcc]

Add a tuning setting

[vitalybuka]

compiler-rt/lib/scudo/standalone/tests/combined_test.cpp

474

in a separate patch, could you fix this?
somewhere in the begining

template  <class Base>
class TestAllocator : public Base {
  TestAllocator() {
    reset();
    // maybe releaseToOS();
  }
  ~TestAllocator() {
      unmapTestOnly();
  }
};

and then replace everywhere with

`
  TestAllocator<scudo::Allocator<scudo::AndroidConfig>> Allocator;
  ....
  useAllocator(Allocator);

[pcc]

Rebase

[pcc]

compiler-rt/lib/scudo/standalone/tests/combined_test.cpp

474

Seems mostly reasonable to me, see D84454. The allocator objects are too large to go on the stack, so I kept them on the heap.

[eugenis]

LGTM

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

 // This function is not part of the NDK so it does not appear in any public
 // header files. We only declare/use it when targeting the platform.
 extern "C" size_t android_unsafe_frame_pointer_chase(scudo::uptr *buf,
                                                      size_t num_entries);
 #endif
 
 namespace scudo {
 
-enum class Option { ReleaseInterval };
+enum class Option { ReleaseInterval, MemtagTuning };
 
 template <class Params, void (*PostInitCallback)(void) = EmptyCallback>
 class Allocator {
 public:
   using PrimaryT = typename Params::Primary;
   using CacheT = typename PrimaryT::CacheT;
   typedef Allocator<Params, PostInitCallback> ThisT;
   typedef typename Params::template TSDRegistryT<ThisT> TSDRegistryT;
void initLinkerInitialized() {
     Options.MayReturnNull = getFlags()->may_return_null;
     Options.FillContents =
         getFlags()->zero_contents
             ? ZeroFill
             : (getFlags()->pattern_fill_contents ? PatternOrZeroFill : NoFill);
     Options.DeallocTypeMismatch = getFlags()->dealloc_type_mismatch;
     Options.DeleteSizeMismatch = getFlags()->delete_size_mismatch;
     Options.TrackAllocationStacks = false;
+    Options.UseOddEvenTags = true;
     Options.QuarantineMaxChunkSize =
         static_cast<u32>(getFlags()->quarantine_max_chunk_size);
 
     Stats.initLinkerInitialized();
     const s32 ReleaseToOsIntervalMs = getFlags()->release_to_os_interval_ms;
     Primary.initLinkerInitialized(ReleaseToOsIntervalMs);
     Secondary.initLinkerInitialized(&Stats, ReleaseToOsIntervalMs);
 
uptr Size =
         android_unsafe_frame_pointer_chase(Stack, MaxTraceSize + DiscardFrames);
     Size = Min<uptr>(Size, MaxTraceSize + DiscardFrames);
     return Depot.insert(Stack + Min<uptr>(DiscardFrames, Size), Stack + Size);
 #else
     return 0;
 #endif
   }
 
+  uptr computeOddEvenMaskForPointerMaybe(uptr Ptr, uptr Size) {
+    if (!Options.UseOddEvenTags)
+      return 0;
+
+    // If a chunk's tag is odd, we want the tags of the surrounding blocks to be
+    // even, and vice versa. Blocks are laid out Size bytes apart, and adding
+    // Size to Ptr will flip the least significant set bit of Size in Ptr, so
+    // that bit will have the pattern 010101... for consecutive blocks, which we
+    // can use to determine which tag mask to use.
+    return (Ptr & (1ULL << getLeastSignificantSetBitIndex(Size))) ? 0xaaaa
+                                                                  : 0x5555;
+  }
+
   NOINLINE void *allocate(uptr Size, Chunk::Origin Origin,
                           uptr Alignment = MinAlignment,
                           bool ZeroContents = false) {
     initThreadMaybe();
 
 #ifdef GWP_ASAN_HOOKS
     if (UNLIKELY(GuardedAlloc.shouldSample())) {
       if (void *Ptr = GuardedAlloc.allocate(roundUpTo(Size, Alignment)))
if (ClassId) {
       // FIXME: When the kernel provides a way to set the background tag of a
       // mapping, we should be able to tag secondary allocations as well.
       //
       // When memory tagging is enabled, zeroing the contents is done as part of
       // setting the tag.
       if (UNLIKELY(useMemoryTagging())) {
         uptr PrevUserPtr;
         Chunk::UnpackedHeader Header;
-        const uptr BlockEnd = BlockUptr + PrimaryT::getSizeByClassId(ClassId);
+        const uptr BlockSize = PrimaryT::getSizeByClassId(ClassId);
+        const uptr BlockEnd = BlockUptr + BlockSize;
         // If possible, try to reuse the UAF tag that was set by deallocate().
         // For simplicity, only reuse tags if we have the same start address as
         // the previous allocation. This handles the majority of cases since
         // most allocations will not be more aligned than the minimum alignment.
         //
         // We need to handle situations involving reclaimed chunks, and retag
         // the reclaimed portions if necessary. In the case where the chunk is
         // fully reclaimed, the chunk's header will be zero, which will trigger
if (ClassId) {
           TaggedPtr = reinterpret_cast<void *>(TaggedUserPtr);
           resizeTaggedChunk(PrevEnd, TaggedUserPtr + Size, BlockEnd);
           if (Size) {
             // Clear any stack metadata that may have previously been stored in
             // the chunk data.
             memset(TaggedPtr, 0, archMemoryTagGranuleSize());
           }
         } else {
-          TaggedPtr = prepareTaggedChunk(Ptr, Size, BlockEnd);
+          const uptr OddEvenMask =
+              computeOddEvenMaskForPointerMaybe(BlockUptr, BlockSize);
+          TaggedPtr = prepareTaggedChunk(Ptr, Size, OddEvenMask, BlockEnd);
         }
         storeAllocationStackMaybe(Ptr);
       } else if (UNLIKELY(FillContents != NoFill)) {
         // This condition is not necessarily unlikely, but since memset is
         // costly, we might as well mark it as such.
         memset(Block, FillContents == ZeroFill ? 0 : PatternFillByte,
                PrimaryT::getSizeByClassId(ClassId));
       }
#endif
   }
 
   bool setOption(Option O, sptr Value) {
     if (O == Option::ReleaseInterval) {
       Primary.setReleaseToOsIntervalMs(static_cast<s32>(Value));
       Secondary.setReleaseToOsIntervalMs(static_cast<s32>(Value));
       return true;
     }
+    if (O == Option::MemtagTuning) {
+      // Enabling odd/even tags involves a tradeoff between use-after-free
+      // detection and buffer overflow detection. Odd/even tags make it more
+      // likely for buffer overflows to be detected by increasing the size of
+      // the guaranteed "red zone" around the allocation, but on the other hand
+      // use-after-free is less likely to be detected because the tag space for
+      // any particular chunk is cut in half. Therefore we use this tuning
+      // setting to control whether odd/even tags are enabled.
+      if (Value == M_MEMTAG_TUNING_BUFFER_OVERFLOW) {
+        Options.UseOddEvenTags = true;
+        return true;
+      }
+      if (Value == M_MEMTAG_TUNING_UAF) {
+        Options.UseOddEvenTags = false;
+        return true;
+      }
+    }
     return false;
   }
 
   // Return the usable size for a given chunk. Technically we lie, as we just
   // report the actual size of a chunk. This is done to counteract code actively
   // writing past the end of a chunk (like sqlite3) when the usable size allows
   // for it, which then forces realloc to copy the usable size of a chunk as
   // opposed to its actual size.
private:
   u32 Cookie;
 
   struct {
     u8 MayReturnNull : 1;       // may_return_null
     FillContentsMode FillContents : 2; // zero_contents, pattern_fill_contents
     u8 DeallocTypeMismatch : 1; // dealloc_type_mismatch
     u8 DeleteSizeMismatch : 1;  // delete_size_mismatch
     u8 TrackAllocationStacks : 1;
+    u8 UseOddEvenTags : 1;
     u32 QuarantineMaxChunkSize; // quarantine_max_chunk_size
   } Options;
 
 #ifdef GWP_ASAN_HOOKS
   gwp_asan::GuardedPoolAllocator GuardedAlloc;
 #endif // GWP_ASAN_HOOKS
 
   StackDepot Depot;
#endif // GWP_ASAN_HOOKS
   }
 
   void quarantineOrDeallocateChunk(void *Ptr, Chunk::UnpackedHeader *Header,
                                    uptr Size) {
     Chunk::UnpackedHeader NewHeader = *Header;
     if (UNLIKELY(NewHeader.ClassId && useMemoryTagging())) {
       u8 PrevTag = extractTag(loadTag(reinterpret_cast<uptr>(Ptr)));
       uptr TaggedBegin, TaggedEnd;
+      const uptr OddEvenMask = computeOddEvenMaskForPointerMaybe(
+          reinterpret_cast<uptr>(getBlockBegin(Ptr, &NewHeader)),
+          SizeClassMap::getSizeByClassId(NewHeader.ClassId));
       // Exclude the previous tag so that immediate use after free is detected
       // 100% of the time.
-      setRandomTag(Ptr, Size, 1UL << PrevTag, &TaggedBegin, &TaggedEnd);
+      setRandomTag(Ptr, Size, OddEvenMask | (1UL << PrevTag), &TaggedBegin,
+                   &TaggedEnd);
       storeDeallocationStackMaybe(Ptr, PrevTag);
     }
     // 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.
     // 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);

compiler-rt/lib/scudo/standalone/include/scudo/interface.h

 //===-- scudo/interface.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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SCUDO_INTERFACE_H_
 #define SCUDO_INTERFACE_H_
 
 #include <stddef.h>
+#include <stdint.h>
 
 extern "C" {
 
 __attribute__((weak)) const char *__scudo_default_options();
 
 // Post-allocation & pre-deallocation hooks.
 // They must be thread-safe and not use heap related functions.
 __attribute__((weak)) void __scudo_allocate_hook(void *ptr, size_t size);

 };
 
 const char *__scudo_get_stack_depot_addr();
 size_t __scudo_get_stack_depot_size();
 
 const char *__scudo_get_region_info_addr();
 size_t __scudo_get_region_info_size();
 
+#ifndef M_DECAY_TIME
+#define M_DECAY_TIME -100
+#endif
+
+#ifndef M_PURGE
+#define M_PURGE -101
+#endif
+
+// Tune the allocator's choice of memory tags to make it more likely that
+// a certain class of memory errors will be detected. The value argument should
+// be one of the enumerators of the scudo_memtag_tuning enum below.
+#ifndef M_MEMTAG_TUNING
+#define M_MEMTAG_TUNING -102
+#endif
+
+enum scudo_memtag_tuning {
+  // Tune for buffer overflows.
+  M_MEMTAG_TUNING_BUFFER_OVERFLOW,
+
+  // Tune for use-after-free.
+  M_MEMTAG_TUNING_UAF,
+};
+
 } // extern "C"
 
 #endif // SCUDO_INTERFACE_H_

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

inline void setRandomTag(void *Ptr, uptr Size, uptr ExcludeMask,
   2:
   )"
       :
       [TaggedPtr] "=&r"(*TaggedBegin), [Cur] "=&r"(*TaggedEnd), [End] "=&r"(End)
       : [Ptr] "r"(Ptr), [Size] "r"(Size), [ExcludeMask] "r"(ExcludeMask)
       : "memory");
 }
 
-inline void *prepareTaggedChunk(void *Ptr, uptr Size, uptr BlockEnd) {
+inline void *prepareTaggedChunk(void *Ptr, uptr Size, uptr ExcludeMask,
+                                uptr BlockEnd) {
   // Prepare the granule before the chunk to store the chunk header by setting
   // its tag to 0. Normally its tag will already be 0, but in the case where a
   // chunk holding a low alignment allocation is reused for a higher alignment
   // allocation, the chunk may already have a non-zero tag from the previous
   // allocation.
   __asm__ __volatile__(".arch_extension mte; stg %0, [%0, #-16]"
                        :
                        : "r"(Ptr)
                        : "memory");
 
   uptr TaggedBegin, TaggedEnd;
-  setRandomTag(Ptr, Size, 0, &TaggedBegin, &TaggedEnd);
+  setRandomTag(Ptr, Size, ExcludeMask, &TaggedBegin, &TaggedEnd);
 
   // Finally, set the tag of the granule past the end of the allocation to 0,
   // to catch linear overflows even if a previous larger allocation used the
   // same block and tag. Only do this if the granule past the end is in our
   // block, because this would otherwise lead to a SEGV if the allocation
   // covers the entire block and our block is at the end of a mapping. The tag
   // of the next block's header granule will be set to 0, so it will serve the
   // purpose of catching linear overflows in this case.
inline void setRandomTag(void *Ptr, uptr Size, uptr ExcludeMask,
   (void)Ptr;
   (void)Size;
   (void)ExcludeMask;
   (void)TaggedBegin;
   (void)TaggedEnd;
   UNREACHABLE("memory tagging not supported");
 }
 
-inline void *prepareTaggedChunk(void *Ptr, uptr Size, uptr BlockEnd) {
+inline void *prepareTaggedChunk(void *Ptr, uptr Size, uptr ExcludeMask,
+                                uptr BlockEnd) {
   (void)Ptr;
   (void)Size;
+  (void)ExcludeMask;
   (void)BlockEnd;
   UNREACHABLE("memory tagging not supported");
 }
 
 inline void resizeTaggedChunk(uptr OldPtr, uptr NewPtr, uptr BlockEnd) {
   (void)OldPtr;
   (void)NewPtr;
   (void)BlockEnd;

compiler-rt/lib/scudo/standalone/tests/combined_test.cpp

for (scudo::uptr ClassId = 1U;
     }
     while (!V.empty()) {
       Allocator->deallocate(V.back(), Origin);
       V.pop_back();
     }
   }
   EXPECT_EQ(FailedAllocationsCount, 0U);
 }
+
+TEST(ScudoCombinedTest, OddEven) {
+  using AllocatorT = TestAllocator<scudo::AndroidConfig>;
+  using SizeClassMap = AllocatorT::PrimaryT::SizeClassMap;
+  auto Allocator = std::make_unique<AllocatorT>();
+
+  if (!Allocator->useMemoryTagging())
+    return;
+
+  auto CheckOddEven = [](scudo::uptr P1, scudo::uptr P2) {
+    scudo::uptr Tag1 = scudo::extractTag(scudo::loadTag(P1));
+    scudo::uptr Tag2 = scudo::extractTag(scudo::loadTag(P2));
+    EXPECT_NE(Tag1 % 2, Tag2 % 2);
+  };
+
+  for (scudo::uptr ClassId = 1U; ClassId <= SizeClassMap::LargestClassId;
+       ClassId++) {
+    const scudo::uptr Size = SizeClassMap::getSizeByClassId(ClassId);
+
+    std::set<scudo::uptr> Ptrs;
+    bool Found = false;
+    for (unsigned I = 0; I != 65536; ++I) {
+      scudo::uptr P = scudo::untagPointer(reinterpret_cast<scudo::uptr>(
+          Allocator->allocate(Size - scudo::Chunk::getHeaderSize(), Origin)));
+      if (Ptrs.count(P - Size)) {
+        Found = true;
+        CheckOddEven(P, P - Size);
+        break;
+      }
+      if (Ptrs.count(P + Size)) {
+        Found = true;
+        CheckOddEven(P, P + Size);
+        break;
+      }
+      Ptrs.insert(P);
+    }
+    EXPECT_TRUE(Found);
+  }
+}

compiler-rt/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 "scudo/interface.h"
 #include "tests/scudo_unit_test.h"
 
 #include <errno.h>
 #include <limits.h>
 #include <malloc.h>
 #include <stdlib.h>
 #include <unistd.h>
 
if (SCUDO_ANDROID) {
     EXPECT_NE(P, nullptr);
     EXPECT_LE(Size * 2U, malloc_usable_size(P));
     for (size_t I = 0; I < Size; I++)
       EXPECT_EQ(0x42, (reinterpret_cast<uint8_t *>(P))[I]);
     free(P);
   }
 }
 
-#ifndef M_DECAY_TIME
-#define M_DECAY_TIME -100
-#endif
-
-#ifndef M_PURGE
-#define M_PURGE -101
-#endif
-
 #if !SCUDO_FUCHSIA
 TEST(ScudoWrappersCTest, MallOpt) {
   errno = 0;
   EXPECT_EQ(mallopt(-1000, 1), 0);
   // mallopt doesn't set errno.
   EXPECT_EQ(errno, 0);
 
   EXPECT_EQ(mallopt(M_PURGE, 0), 1);

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

 // conflicting return types for mallinfo() if we use our own structure. So if
 // struct mallinfo is declared (#define courtesy of malloc.h), use it directly.
 #if STRUCT_MALLINFO_DECLARED
 #define SCUDO_MALLINFO mallinfo
 #else
 #define SCUDO_MALLINFO __scudo_mallinfo
 #endif
 
-#ifndef M_DECAY_TIME
-#define M_DECAY_TIME -100
-#endif
-
-#ifndef M_PURGE
-#define M_PURGE -101
-#endif
-
 #endif // SCUDO_WRAPPERS_C_H_

compiler-rt/lib/scudo/standalone/wrappers_c.inc

if (param == M_DECAY_TIME) {
     }
 
     SCUDO_ALLOCATOR.setOption(scudo::Option::ReleaseInterval,
                               static_cast<scudo::sptr>(value));
     return 1;
   } else if (param == M_PURGE) {
     SCUDO_ALLOCATOR.releaseToOS();
     return 1;
+  } else if (param == M_MEMTAG_TUNING) {
+    return SCUDO_ALLOCATOR.setOption(scudo::Option::MemtagTuning,
+                                     static_cast<scudo::sptr>(value));
   }
   return 0;
 }
 
 INTERFACE WEAK void *SCUDO_PREFIX(aligned_alloc)(size_t alignment,
                                                  size_t size) {
   if (UNLIKELY(scudo::checkAlignedAllocAlignmentAndSize(alignment, size))) {
     if (SCUDO_ALLOCATOR.canReturnNull()) {