scudo: Use a table to look up the LSB for computing the odd/even mask. NFCI.

[pcc]

Summary

In the most common case we call computeOddEvenMaskForPointerMaybe()
from quarantineOrDeallocateChunk(), in which case we need to look up
the class size from the SizeClassMap in order to compute the LSB. Since
we need to do a lookup anyway, we may as well look up the LSB itself
and avoid computing it every time.

While here, switch to a slightly more efficient way of computing the
odd/even mask.

[pcc]

Fix build

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

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(Options Options, uptr Ptr, uptr Size) {
+  uptr computeOddEvenMaskForPointerMaybe(Options Options, uptr Ptr,
+                                         uptr ClassId) {
     if (!Options.get(OptionBit::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;
+    return 0x5555U << ((Ptr >> SizeClassMap::getSizeLSBByClassId(ClassId)) & 1);
   }
 
   NOINLINE void *allocate(uptr Size, Chunk::Origin Origin,
                           uptr Alignment = MinAlignment,
                           bool ZeroContents = false) {
     initThreadMaybe();
 
 #ifdef GWP_ASAN_HOOKS
if (LIKELY(ClassId)) {
                                        archMemoryTagGranuleSize())));
           } else if (Size) {
             // Clear any stack metadata that may have previously been stored in
             // the chunk data.
             memset(TaggedPtr, 0, archMemoryTagGranuleSize());
           }
         } else {
           const uptr OddEvenMask =
-              computeOddEvenMaskForPointerMaybe(Options, BlockUptr, BlockSize);
+              computeOddEvenMaskForPointerMaybe(Options, BlockUptr, ClassId);
           TaggedPtr = prepareTaggedChunk(Ptr, Size, OddEvenMask, BlockEnd);
         }
         storePrimaryAllocationStackMaybe(Options, Ptr);
       } else {
         Block = addHeaderTag(Block);
         Ptr = addHeaderTag(Ptr);
         if (UNLIKELY(FillContents != NoFill)) {
           // This condition is not necessarily unlikely, but since memset is
void quarantineOrDeallocateChunk(Options Options, void *TaggedPtr,
     Chunk::UnpackedHeader NewHeader = *Header;
     if (UNLIKELY(useMemoryTagging<Params>(Options))) {
       u8 PrevTag = extractTag(reinterpret_cast<uptr>(TaggedPtr));
       if (NewHeader.ClassId) {
         if (!TSDRegistry.getDisableMemInit()) {
           uptr TaggedBegin, TaggedEnd;
           const uptr OddEvenMask = computeOddEvenMaskForPointerMaybe(
               Options, reinterpret_cast<uptr>(getBlockBegin(Ptr, &NewHeader)),
-              SizeClassMap::getSizeByClassId(NewHeader.ClassId));
+              NewHeader.ClassId);
           // Exclude the previous tag so that immediate use after free is
           // detected 100% of the time.
           setRandomTag(Ptr, Size, OddEvenMask | (1UL << PrevTag), &TaggedBegin,
                        &TaggedEnd);
         }
         NewHeader.OriginOrWasZeroed = !TSDRegistry.getDisableMemInit();
       }
       storeDeallocationStackMaybe(Options, Ptr, PrevTag, Size);

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

static uptr getSizeByClassId(uptr ClassId) {
     DCHECK_NE(ClassId, BatchClassId);
     if (ClassId <= MidClass)
       return (ClassId << Config::MinSizeLog) + SizeDelta;
     ClassId -= MidClass;
     const uptr T = MidSize << (ClassId >> S);
     return T + (T >> S) * (ClassId & M) + SizeDelta;
   }
 
+  static u8 getSizeLSBByClassId(uptr ClassId) {
+    return u8(getLeastSignificantSetBitIndex(getSizeByClassId(ClassId)));
+  }
+
   static uptr getClassIdBySize(uptr Size) {
     if (Size <= SizeDelta + (1 << Config::MinSizeLog))
       return 1;
     Size -= SizeDelta;
     DCHECK_LE(Size, MaxSize);
     if (Size <= MidSize)
       return (Size + MinSize - 1) >> Config::MinSizeLog;
     return MidClass + 1 + scaledLog2(Size - 1, Config::MidSizeLog, S);
struct SizeTable {
 
     constexpr static uptr getTableSize() {
       return (Config::MaxSizeLog - Config::MidSizeLog) << S;
     }
 
     u8 Tab[getTableSize()] = {};
   };
 
-  static constexpr SizeTable Table = {};
+  static constexpr SizeTable SzTable = {};
+
+  struct LSBTable {
+    constexpr LSBTable() {
+      for (uptr I = 0; I != ClassesSize; ++I) {
+        for (u8 Bit = 0; Bit != 64; ++Bit) {
+          if (Config::Classes[I] & (1 << Bit)) {
+            Tab[I] = Bit;
+            break;
+          }
+        }
+      }
+    }
+
+    u8 Tab[ClassesSize] = {};
+  };
+
+  static constexpr LSBTable LTable = {};
 
 public:
   static const u32 MaxNumCachedHint = Config::MaxNumCachedHint;
 
   static const uptr NumClasses = ClassesSize + 1;
   static_assert(NumClasses < 256, "");
   static const uptr LargestClassId = NumClasses - 1;
   static const uptr BatchClassId = 0;
   static const uptr MaxSize = Config::Classes[LargestClassId - 1];
 
   static uptr getSizeByClassId(uptr ClassId) {
     return Config::Classes[ClassId - 1];
   }
 
+  static u8 getSizeLSBByClassId(uptr ClassId) {
+    return LTable.Tab[ClassId - 1];
+  }
+
   static uptr getClassIdBySize(uptr Size) {
     if (Size <= Config::Classes[0])
       return 1;
     Size -= Config::SizeDelta;
     DCHECK_LE(Size, MaxSize);
     if (Size <= (1 << Config::MidSizeLog))
       return ((Size - 1) >> Config::MinSizeLog) + 1;
-    return Table.Tab[scaledLog2(Size - 1, Config::MidSizeLog, S)];
+    return SzTable.Tab[scaledLog2(Size - 1, Config::MidSizeLog, S)];
   }
 
   static u32 getMaxCachedHint(uptr Size) {
     DCHECK_LE(Size, MaxSize);
     return Base::getMaxCachedHint(Size);
   }
 };