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
measureWastage(const std::vector<Alloc> & allocs,const std::vector<size_t> & classes,size_t pageSize,size_t headerSize)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
readAllocs(std::vector<Alloc> & allocs,const char * path)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
log2Floor(size_t x)63 size_t log2Floor(size_t x) { return sizeof(long) * 8 - 1 - __builtin_clzl(x); }
64
usage()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
main(int argc,char ** argv)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 }
163