commit 7112166df1ad68376618f9b7397a9003c6e560ec
author Peter Collingbourne <peter@pcc.me.uk> Thu Apr 22 12:59:57 2021 -0700
committer Copybara-Service <copybara-worker@google.com> Sun May 09 19:09:10 2021 -0700
tree 94b14eeacec319fba2d2469792d8691984e727ea
parent fb0a4a8ed3eaf6f702297d378d0b7ff4858ba89a

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

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.

Differential Revision: https://reviews.llvm.org/D101105

GitOrigin-RevId: a6500b013a257c969e19ce0d8414ff43fe9bd4fa

size_class_map.h

diff --git a/size_class_map.h b/size_class_map.h
index bb06902..37a3efd 100644
--- a/size_class_map.h
+++ b/size_class_map.h
@@ -89,6 +89,10 @@
     return u8(getLeastSignificantSetBitIndex(getSizeByClassId(ClassId)));
   }
 
+  static constexpr bool usesCompressedLSBFormat() {
+    return false;
+  }
+
   static uptr getClassIdBySize(uptr Size) {
     if (Size <= SizeDelta + (1 << Config::MinSizeLog))
       return 1;
@@ -145,17 +149,34 @@
 
   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 = {};
@@ -174,7 +195,15 @@
   }
 
   static u8 getSizeLSBByClassId(uptr ClassId) {
-    return LTable.Tab[ClassId - 1];
+    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) {
@@ -244,6 +273,10 @@
 
 typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap;
 
+#if SCUDO_WORDSIZE == 64U
+static_assert(AndroidSizeClassMap::usesCompressedLSBFormat(), "");
+#endif
+
 struct SvelteSizeClassConfig {
 #if SCUDO_WORDSIZE == 64U
   static const uptr NumBits = 4;