scudo: Make prepareTaggedChunk() and resizeTaggedChunk() generic.

[pcc]

Summary

Now that we have a more efficient implementation of storeTags(),
we should start using it from resizeTaggedChunk(). With that, plus
a new storeTag() function, resizeTaggedChunk() can be made generic,
and so can prepareTaggedChunk(). Make it so.

Now that the functions are generic, move them to combined.h so that
memtag.h no longer needs to know about chunks.

Depends on D100910

[vitalybuka]

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

1146

Why we don't tag entire unused tail? It may detect UseAfterFree.

[pcc]

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

1146

We detect UAF by retagging on free. So from that perspective there's no advantage to retagging the tail here.

[vitalybuka]

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

1146

then why do we need to remove a tag on a single granule here?
To distinguish UAF and out of bounds?

[eugenis]

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

1146

For guaranteed linear overflow detection.

In fact, by not retagging the tail, we have guaranteed false negative for overflow by 16 bytes, right? Should we change this? It should be pretty cheap in the primary allocator.

[pcc]

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

1146

Hmm, I would expect the cost increase to correspond to the average ratio between size classes (i.e. around sqrt(2)).

Let's investigate doing that as part of a separate change. It should be easier to implement once we have the generic resizeTaggedChunk() implementation in.

[vitalybuka]

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

1146

So UAF is not guaranteed, but we want linear overflow guaranteed and without spending cycles to retag entire [RoundNewPtr, BlockEnd)?

[vitalybuka]

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

1146

Hmm, I would expect the cost increase to correspond to the average ratio between size classes (i.e. around sqrt(2)).

Let's investigate doing that as part of a separate change. It should be easier to implement once we have the generic resizeTaggedChunk() implementation in.

Agree, this is unchanged in the patch and better addressed (if needed) separately.

[pcc]

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

1146

Immediate UAF is guaranteed due to retag on free -- that retags the entire previous allocation (of course, we don't know how large the next allocation to use that chunk will be).

Yes, the reason why we didn't retag that entire region with 0 was to save cycles.

[eugenis]

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

1146

well probably half of that, on average.
SGTM, let's not worry about that for now.

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

#endif
 
   static uptr getChunkOffsetFromBlock(const char *Block) {
     u32 Offset = 0;
     if (reinterpret_cast<const u32 *>(Block)[0] == BlockMarker)
       Offset = reinterpret_cast<const u32 *>(Block)[1];
     return Offset + Chunk::getHeaderSize();
   }
 
+  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.
+    storeTag(reinterpret_cast<uptr>(Ptr) - archMemoryTagGranuleSize());
+
+    uptr 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.
+    uptr UntaggedEnd = untagPointer(TaggedEnd);
+    if (UntaggedEnd != BlockEnd)
+      storeTag(UntaggedEnd);
+    return reinterpret_cast<void *>(TaggedBegin);
+  }
+
+  void resizeTaggedChunk(uptr OldPtr, uptr NewPtr, uptr BlockEnd) {
+    uptr RoundOldPtr = roundUpTo(OldPtr, archMemoryTagGranuleSize());
+    uptr RoundNewPtr;
+    if (RoundOldPtr >= NewPtr) {
+      // If the allocation is shrinking we just need to set the tag past the end
+      // of the allocation to 0. See explanation in prepareTaggedChunk above.
+      RoundNewPtr = roundUpTo(NewPtr, archMemoryTagGranuleSize());
+    } else {
+      // Set the memory tag of the region
+      // [RoundOldPtr, roundUpTo(NewPtr, archMemoryTagGranuleSize()))
+      // to the pointer tag stored in OldPtr.
+      RoundNewPtr = storeTags(RoundOldPtr, NewPtr);
+    }
+
+    uptr UntaggedNewPtr = untagPointer(RoundNewPtr);
+    if (UntaggedNewPtr != BlockEnd)
+      storeTag(UntaggedNewPtr);
+  }
+
   void storePrimaryAllocationStackMaybe(Options Options, void *Ptr) {
     if (!UNLIKELY(Options.get(OptionBit::TrackAllocationStacks)))
       return;
     auto *Ptr32 = reinterpret_cast<u32 *>(Ptr);
     Ptr32[MemTagAllocationTraceIndex] = collectStackTrace();
     Ptr32[MemTagAllocationTidIndex] = getThreadID();
   }
 

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

 
 #if SCUDO_LINUX
 #include <sys/auxv.h>
 #include <sys/prctl.h>
 #endif
 
 namespace scudo {
 
-void setRandomTag(void *Ptr, uptr Size, uptr ExcludeMask, uptr *TaggedBegin,
-                  uptr *TaggedEnd);
-
 #if defined(__aarch64__) || defined(SCUDO_FUZZ)
 
 // We assume that Top-Byte Ignore is enabled if the architecture supports memory
 // tagging. Not all operating systems enable TBI, so we only claim architectural
 // support for memory tagging if the operating system enables TBI.
 #if SCUDO_LINUX && !defined(SCUDO_DISABLE_TBI)
 inline constexpr bool archSupportsMemoryTagging() { return true; }
 #else
inline uptr storeTags(uptr Begin, uptr End) {
   )"
       : [Cur] "+&r"(Begin), [LineSize] "=&r"(LineSize), [Next] "=&r"(Next),
         [Tmp] "=&r"(Tmp)
       : [End] "r"(End)
       : "memory");
   return Begin;
 }
 
-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__(
-      R"(
-      .arch_extension memtag
-      stg %0, [%0, #-16]
-      )"
-      :
-      : "r"(Ptr)
-      : "memory");
-
-  uptr 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.
-  uptr UntaggedEnd = untagPointer(TaggedEnd);
-  if (UntaggedEnd != BlockEnd)
-    __asm__ __volatile__(
-        R"(
-        .arch_extension memtag
-        stg %0, [%0]
-        )"
-        :
-        : "r"(UntaggedEnd)
-        : "memory");
-  return reinterpret_cast<void *>(TaggedBegin);
-}
-
-inline void resizeTaggedChunk(uptr OldPtr, uptr NewPtr, uptr BlockEnd) {
-  uptr RoundOldPtr = roundUpTo(OldPtr, 16);
-  if (RoundOldPtr >= NewPtr) {
-    // If the allocation is shrinking we just need to set the tag past the end
-    // of the allocation to 0. See explanation in prepareTaggedChunk above.
-    uptr RoundNewPtr = untagPointer(roundUpTo(NewPtr, 16));
-    if (RoundNewPtr != BlockEnd)
-      __asm__ __volatile__(
-          R"(
-          .arch_extension memtag
-          stg %0, [%0]
-          )"
+inline void storeTag(uptr Ptr) {
+  __asm__ __volatile__(R"(
                        :
-          : "r"(RoundNewPtr)
-          : "memory");
-    return;
-  }
-
-  __asm__ __volatile__(R"(
-    .arch_extension memtag
-
-    // Set the memory tag of the region
-    // [roundUpTo(OldPtr, 16), roundUpTo(NewPtr, 16))
-    // to the pointer tag stored in OldPtr.
-  1:
-    stzg %[Cur], [%[Cur]], #16
-    cmp %[Cur], %[End]
-    b.lt 1b
-
-    // Finally, set the tag of the granule past the end of the allocation to 0.
-    and %[Cur], %[Cur], #(1 << 56) - 1
-    cmp %[Cur], %[BlockEnd]
-    b.eq 2f
-    stg %[Cur], [%[Cur]]
-
-  2:
-  )"
-                       : [Cur] "+&r"(RoundOldPtr), [End] "+&r"(NewPtr)
-                       : [BlockEnd] "r"(BlockEnd)
+                       : "r"(Ptr)
                        : "memory");
 }
 
 inline uptr loadTag(uptr Ptr) {
   uptr TaggedPtr = Ptr;
   __asm__ __volatile__(
       R"(
       .arch_extension memtag

 }
 
 inline uptr storeTags(uptr Begin, uptr End) {
   (void)Begin;
   (void)End;
   UNREACHABLE("memory tagging not supported");
 }
 
-inline void *prepareTaggedChunk(void *Ptr, uptr Size, uptr ExcludeMask,
-                                uptr BlockEnd) {
+inline void storeTag(uptr Ptr) {
   (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;
   UNREACHABLE("memory tagging not supported");
 }
 
 inline uptr loadTag(uptr Ptr) {
   (void)Ptr;
   UNREACHABLE("memory tagging not supported");
 }