scudo: Optimize getSizeLSBByClassId() by compressing the table into an integer if possible. NFCI.

[pcc]

Summary

With AndroidSizeClassMap all of the LSBs are in the range 4-6 so we
only need 2 bits of information per size class. Furthermore we have
32 size classes, which conveniently lets us fit all of the information
into a 64-bit integer. Do so if possible so that we can avoid a table
lookup entirely.

[eugenis]

Nice.
If this is a significant optimization, we might want to request it through the allocator config and fail if it is impossible - in case we change the size class map in the future and break this by accident.

[pcc]

In D101105#2710053, @eugenis wrote:

Nice.
If this is a significant optimization, we might want to request it through the allocator config and fail if it is impossible - in case we change the size class map in the future and break this by accident.

Sure, it makes sense to have a check for the Android size class map. It seems like the most straightforward way to do it would be to expose the bool and check it via a static_assert, which I've done.

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

static uptr getSizeByClassId(uptr ClassId) {
     const uptr T = MidSize << (ClassId >> S);
     return T + (T >> S) * (ClassId & M) + SizeDelta;
   }
 
   static u8 getSizeLSBByClassId(uptr ClassId) {
     return u8(getLeastSignificantSetBitIndex(getSizeByClassId(ClassId)));
   }
 
+  static constexpr bool usesCompressedLSBFormat() {
+    return false;
+  }
+
   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 {
 
     u8 Tab[getTableSize()] = {};
   };
 
   static constexpr SizeTable SzTable = {};
 
   struct LSBTable {
     constexpr LSBTable() {
+      u8 Min = 255, Max = 0;
       for (uptr I = 0; I != ClassesSize; ++I) {
         for (u8 Bit = 0; Bit != 64; ++Bit) {
           if (Config::Classes[I] & (1 << Bit)) {
             Tab[I] = Bit;
+            if (Bit < Min)
+              Min = Bit;
+            if (Bit > Max)
+              Max = Bit;
             break;
           }
         }
       }
+
+      if (Max - Min > 3 || ClassesSize > 32)
+        return;
+
+      UseCompressedFormat = true;
+      CompressedMin = Min;
+      for (uptr I = 0; I != ClassesSize; ++I)
+        CompressedValue |= u64(Tab[I] - Min) << (I * 2);
     }
 
     u8 Tab[ClassesSize] = {};
+
+    bool UseCompressedFormat = false;
+    u8 CompressedMin = 0;
+    u64 CompressedValue = 0;
   };
 
   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) {
+    if (LTable.UseCompressedFormat)
+      return ((LTable.CompressedValue >> ((ClassId - 1) * 2)) & 3) +
+             LTable.CompressedMin;
+    else
       return LTable.Tab[ClassId - 1];
   }
 
+  static constexpr bool usesCompressedLSBFormat() {
+    return LTable.UseCompressedFormat;
+  }
+
   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 SzTable.Tab[scaledLog2(Size - 1, Config::MidSizeLog, S)];
static constexpr u32 Classes[] = {
       0x04510, 0x04810, 0x05c10, 0x06f10, 0x07310, 0x08010, 0x0c010, 0x10010,
   };
   static const uptr SizeDelta = 16;
 #endif
 };
 
 typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap;
 
+#if SCUDO_WORDSIZE == 64U
+static_assert(AndroidSizeClassMap::usesCompressedLSBFormat(), "");
+#endif
+
 struct SvelteSizeClassConfig {
 #if SCUDO_WORDSIZE == 64U
   static const uptr NumBits = 4;
   static const uptr MinSizeLog = 4;
   static const uptr MidSizeLog = 8;
   static const uptr MaxSizeLog = 14;
   static const u32 MaxNumCachedHint = 13;
   static const uptr MaxBytesCachedLog = 10;