compiler-rt/lib/scudo/standalone/tools/compute_size_class_config.cpp

   1 //===-- compute_size_class_config.cpp -------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include <errno.h>
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include <string.h>
  13
  14 #include <algorithm>
  15 #include <vector>
  16
  17 struct Alloc {
  18   size_t size, count;
  19 };
  20
  21 size_t measureWastage(const std::vector<Alloc> &allocs,
  22                       const std::vector<size_t> &classes, size_t pageSize,
  23                       size_t headerSize) {
  24   size_t totalWastage = 0;
  25   for (auto &a : allocs) {
  26     size_t sizePlusHeader = a.size + headerSize;
  27     size_t wastage = -1ull;
  28     for (auto c : classes)
  29       if (c >= sizePlusHeader && c - sizePlusHeader < wastage)
  30         wastage = c - sizePlusHeader;
  31     if (wastage == -1ull)
  32       continue;
  33     if (wastage > 2 * pageSize)
  34       wastage = 2 * pageSize;
  35     totalWastage += wastage * a.count;
  36   }
  37   return totalWastage;
  38 }
  39
  40 void readAllocs(std::vector<Alloc> &allocs, const char *path) {
  41   FILE *f = fopen(path, "r");
  42   if (!f) {
  43     fprintf(stderr, "compute_size_class_config: could not open %s: %s\n", path,
  44             strerror(errno));
  45     exit(1);
  46   }
  47
  48   const char header[] = "<malloc version=\"scudo-1\">\n";
  49   char buf[sizeof(header) - 1];
  50   if (fread(buf, 1, sizeof(header) - 1, f) != sizeof(header) - 1 ||
  51       memcmp(buf, header, sizeof(header) - 1) != 0) {
  52     fprintf(stderr, "compute_size_class_config: invalid input format\n");
  53     exit(1);
  54   }
  55
  56   Alloc a;
  57   while (fscanf(f, "<alloc size=\"%zu\" count=\"%zu\"/>\n", &a.size,
  58                 &a.count) == 2)
  59     allocs.push_back(a);
  60   fclose(f);
  61 }
  62
  63 size_t log2Floor(size_t x) { return sizeof(long) * 8 - 1 - __builtin_clzl(x); }
  64
  65 void usage() {
  66   fprintf(stderr,
  67           "usage: compute_size_class_config [-p pageSize] [-c largestClass] "
  68           "[-h headerSize] [-n numClasses] [-b numBits] profile...\n");
  69   exit(1);
  70 }
  71
  72 int main(int argc, char **argv) {
  73   size_t pageSize = 4096;
  74   size_t largestClass = 65552;
  75   size_t headerSize = 16;
  76   size_t numClasses = 32;
  77   size_t numBits = 5;
  78
  79   std::vector<Alloc> allocs;
  80   for (size_t i = 1; i != argc;) {
  81     auto matchArg = [&](size_t &arg, const char *name) {
  82       if (strcmp(argv[i], name) == 0) {
  83         if (i + 1 != argc) {
  84           arg = atoi(argv[i + 1]);
  85           i += 2;
  86         } else {
  87           usage();
  88         }
  89         return true;
  90       }
  91       return false;
  92     };
  93     if (matchArg(pageSize, "-p") || matchArg(largestClass, "-c") ||
  94         matchArg(headerSize, "-h") || matchArg(numClasses, "-n") ||
  95         matchArg(numBits, "-b"))
  96       continue;
  97     readAllocs(allocs, argv[i]);
  98     ++i;
  99   }
 100
 101   if (allocs.empty())
 102     usage();
 103
 104   std::vector<size_t> classes;
 105   classes.push_back(largestClass);
 106   for (size_t i = 1; i != numClasses; ++i) {
 107     size_t minWastage = -1ull;
 108     size_t minWastageClass;
 109     for (size_t newClass = 16; newClass != largestClass; newClass += 16) {
 110       // Skip classes with more than numBits bits, ignoring leading or trailing
 111       // zero bits.
 112       if (__builtin_ctzl(newClass - headerSize) +
 113               __builtin_clzl(newClass - headerSize) <
 114           sizeof(long) * 8 - numBits)
 115         continue;
 116
 117       classes.push_back(newClass);
 118       size_t newWastage = measureWastage(allocs, classes, pageSize, headerSize);
 119       classes.pop_back();
 120       if (newWastage < minWastage) {
 121         minWastage = newWastage;
 122         minWastageClass = newClass;
 123       }
 124     }
 125     classes.push_back(minWastageClass);
 126   }
 127
 128   std::sort(classes.begin(), classes.end());
 129   size_t minSizeLog = log2Floor(headerSize);
 130   size_t midSizeIndex = 0;
 131   while (classes[midSizeIndex + 1] - classes[midSizeIndex] == (1 << minSizeLog))
 132     midSizeIndex++;
 133   size_t midSizeLog = log2Floor(classes[midSizeIndex] - headerSize);
 134   size_t maxSizeLog = log2Floor(classes.back() - headerSize - 1) + 1;
 135
 136   printf(R"(// wastage = %zu
 137
 138 struct MySizeClassConfig {
 139   static const uptr NumBits = %zu;
 140   static const uptr MinSizeLog = %zu;
 141   static const uptr MidSizeLog = %zu;
 142   static const uptr MaxSizeLog = %zu;
 143   static const u16 MaxNumCachedHint = 14;
 144   static const uptr MaxBytesCachedLog = 14;
 145
 146   static constexpr u32 Classes[] = {)",
 147          measureWastage(allocs, classes, pageSize, headerSize), numBits,
 148          minSizeLog, midSizeLog, maxSizeLog);
 149   for (size_t i = 0; i != classes.size(); ++i) {
 150     if ((i % 8) == 0)
 151       printf("\n      ");
 152     else
 153       printf(" ");
 154     printf("0x%05zx,", classes[i]);
 155   }
 156   printf(R"(
 157   };
 158   static const uptr SizeDelta = %zu;
 159 };
 160 )",
 161          headerSize);
 162 }