text: //===-- size_class_map.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_SIZE_CLASS_MAP_H_
  #define SCUDO_SIZE_CLASS_MAP_H_
  
  #include "common.h"
  #include "string_utils.h"
  
  namespace scudo {
  
  // SizeClassMap maps allocation sizes into size classes and back, in an
  // efficient table-free manner.
  //
  // Class 0 is a special class that doesn't abide by the same rules as other
  // classes. The allocator uses it to hold batches.
  //
  // The other sizes are controlled by the template parameters:
  // - MinSizeLog: defines the first class as 2^MinSizeLog bytes.
  // - MaxSizeLog: defines the last class as 2^MaxSizeLog bytes.
  // - MidSizeLog: classes increase with step 2^MinSizeLog from 2^MinSizeLog to
  //               2^MidSizeLog bytes.
  // - NumBits: the number of non-zero bits in sizes after 2^MidSizeLog.
  //            eg. with NumBits==3 all size classes after 2^MidSizeLog look like
  //            0b1xx0..0 (where x is either 0 or 1).
  //
  // This class also gives a hint to a thread-caching allocator about the amount
  // of chunks that can be cached per-thread:
  // - MaxNumCachedHint is a hint for the max number of chunks cached per class.
  // - 2^MaxBytesCachedLog is the max number of bytes cached per class.
  
  template <u8 NumBits, u8 MinSizeLog, u8 MidSizeLog, u8 MaxSizeLog,
            u32 MaxNumCachedHintT, u8 MaxBytesCachedLog>
  class SizeClassMap {
    static const uptr MinSize = 1UL << MinSizeLog;
    static const uptr MidSize = 1UL << MidSizeLog;
    static const uptr MidClass = MidSize / MinSize;
    static const u8 S = NumBits - 1;
    static const uptr M = (1UL << S) - 1;
  
  public:
    static const u32 MaxNumCachedHint = MaxNumCachedHintT;
  
    static const uptr MaxSize = 1UL << MaxSizeLog;
    static const uptr NumClasses =
        MidClass + ((MaxSizeLog - MidSizeLog) << S) + 1;
    COMPILER_CHECK(NumClasses <= 256);
    static const uptr LargestClassId = NumClasses - 1;
    static const uptr BatchClassId = 0;
  
    static uptr getSizeByClassId(uptr ClassId) {
      DCHECK_NE(ClassId, BatchClassId);
      if (ClassId <= MidClass)
        return ClassId << MinSizeLog;
      ClassId -= MidClass;
      const uptr T = MidSize << (ClassId >> S);
      return T + (T >> S) * (ClassId & M);
    }
  
    static uptr getClassIdBySize(uptr Size) {
      DCHECK_LE(Size, MaxSize);
      if (Size <= MidSize)
        return (Size + MinSize - 1) >> MinSizeLog;
      const uptr L = getMostSignificantSetBitIndex(Size);
      const uptr HBits = (Size >> (L - S)) & M;
      const uptr LBits = Size & ((1UL << (L - S)) - 1);
      const uptr L1 = L - MidSizeLog;
      return MidClass + (L1 << S) + HBits + (LBits > 0);
    }
  
    static u32 getMaxCachedHint(uptr Size) {
      DCHECK_LE(Size, MaxSize);
      DCHECK_NE(Size, 0);
      u32 N;
      // Force a 32-bit division if the template parameters allow for it.
      if (MaxBytesCachedLog > 31 || MaxSizeLog > 31)
        N = static_cast<u32>((1UL << MaxBytesCachedLog) / Size);
      else
        N = (1U << MaxBytesCachedLog) / static_cast<u32>(Size);
      return Max(1U, Min(MaxNumCachedHint, N));
    }
  
    static void print() {
      uptr PrevS = 0;
      uptr TotalCached = 0;
      for (uptr I = 0; I < NumClasses; I++) {
        if (I == BatchClassId)
          continue;
        const uptr S = getSizeByClassId(I);
        if (S >= MidSize / 2 && (S & (S - 1)) == 0)
          Printf("\n");
        const uptr D = S - PrevS;
        const uptr P = PrevS ? (D * 100 / PrevS) : 0;
        const uptr L = S ? getMostSignificantSetBitIndex(S) : 0;
        const uptr Cached = getMaxCachedHint(S) * S;
        Printf(
            "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n",
            I, getSizeByClassId(I), D, P, L, getMaxCachedHint(S), Cached,
            getClassIdBySize(S));
        TotalCached += Cached;
        PrevS = S;
      }
      Printf("Total Cached: %zu\n", TotalCached);
    }
  
    static void validate() {
      for (uptr C = 0; C < NumClasses; C++) {
        if (C == BatchClassId)
          continue;
        const uptr S = getSizeByClassId(C);
        CHECK_NE(S, 0U);
        CHECK_EQ(getClassIdBySize(S), C);
        if (C < LargestClassId)
          CHECK_EQ(getClassIdBySize(S + 1), C + 1);
        CHECK_EQ(getClassIdBySize(S - 1), C);
        CHECK_GT(getSizeByClassId(C), getSizeByClassId(C - 1));
      }
      // Do not perform the loop if the maximum size is too large.
      if (MaxSizeLog > 19)
        return;
      for (uptr S = 1; S <= MaxSize; S++) {
        const uptr C = getClassIdBySize(S);
        CHECK_LT(C, NumClasses);
        CHECK_GE(getSizeByClassId(C), S);
        if (C > 0)
          CHECK_LT(getSizeByClassId(C - 1), S);
      }
    }
  };
  
  typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap;
  
  // TODO(kostyak): further tune class maps for Android & Fuchsia.
  #if SCUDO_WORDSIZE == 64U
  typedef SizeClassMap<3, 5, 8, 15, 8, 10> SvelteSizeClassMap;
  typedef SizeClassMap<3, 5, 8, 16, 14, 12> AndroidSizeClassMap;
  #else
  typedef SizeClassMap<3, 4, 7, 15, 8, 10> SvelteSizeClassMap;
  typedef SizeClassMap<3, 4, 7, 16, 14, 12> AndroidSizeClassMap;
  #endif
  
  } // namespace scudo
  
  #endif // SCUDO_SIZE_CLASS_MAP_H_
  