Source file
src/runtime/mksizeclasses.go
Documentation: runtime
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 package main
32
33 import (
34 "bytes"
35 "flag"
36 "fmt"
37 "go/format"
38 "io"
39 "log"
40 "math"
41 "math/bits"
42 "os"
43 )
44
45
46
47 var stdout = flag.Bool("stdout", false, "write to stdout instead of sizeclasses.go")
48
49 func main() {
50 flag.Parse()
51
52 var b bytes.Buffer
53 fmt.Fprintln(&b, "// Code generated by mksizeclasses.go; DO NOT EDIT.")
54 fmt.Fprintln(&b, "//go:generate go run mksizeclasses.go")
55 fmt.Fprintln(&b)
56 fmt.Fprintln(&b, "package runtime")
57 classes := makeClasses()
58
59 printComment(&b, classes)
60
61 printClasses(&b, classes)
62
63 out, err := format.Source(b.Bytes())
64 if err != nil {
65 log.Fatal(err)
66 }
67 if *stdout {
68 _, err = os.Stdout.Write(out)
69 } else {
70 err = os.WriteFile("sizeclasses.go", out, 0666)
71 }
72 if err != nil {
73 log.Fatal(err)
74 }
75 }
76
77 const (
78
79 maxSmallSize = 32 << 10
80 smallSizeDiv = 8
81 smallSizeMax = 1024
82 largeSizeDiv = 128
83 pageShift = 13
84
85
86 pageSize = 1 << pageShift
87 )
88
89 type class struct {
90 size int
91 npages int
92 }
93
94 func powerOfTwo(x int) bool {
95 return x != 0 && x&(x-1) == 0
96 }
97
98 func makeClasses() []class {
99 var classes []class
100
101 classes = append(classes, class{})
102
103 align := 8
104 for size := align; size <= maxSmallSize; size += align {
105 if powerOfTwo(size) {
106 if size >= 2048 {
107 align = 256
108 } else if size >= 128 {
109 align = size / 8
110 } else if size >= 32 {
111 align = 16
112 }
113 }
114 if !powerOfTwo(align) {
115 panic("incorrect alignment")
116 }
117
118
119
120
121 allocsize := pageSize
122 for allocsize%size > allocsize/8 {
123 allocsize += pageSize
124 }
125 npages := allocsize / pageSize
126
127
128
129
130
131
132 if len(classes) > 1 && npages == classes[len(classes)-1].npages && allocsize/size == allocsize/classes[len(classes)-1].size {
133 classes[len(classes)-1].size = size
134 continue
135 }
136 classes = append(classes, class{size: size, npages: npages})
137 }
138
139
140
141
142
143
144
145 for i := range classes {
146 if i == 0 {
147 continue
148 }
149 c := &classes[i]
150 psize := c.npages * pageSize
151 new_size := (psize / (psize / c.size)) &^ (largeSizeDiv - 1)
152 if new_size > c.size {
153 c.size = new_size
154 }
155 }
156
157 if len(classes) != 68 {
158 panic("number of size classes has changed")
159 }
160
161 for i := range classes {
162 computeDivMagic(&classes[i])
163 }
164
165 return classes
166 }
167
168
169
170
171
172 func computeDivMagic(c *class) {
173
174 d := c.size
175 if d == 0 {
176 return
177 }
178
179
180 max := c.npages * pageSize
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204 N := bits.Len(uint(max))
205 var F int
206 if powerOfTwo(d) {
207 F = int(math.Log2(float64(d)))
208 if d != 1<<F {
209 panic("imprecise log2")
210 }
211 } else {
212 for L := 0; ; L++ {
213 if d <= ((1<<(N+L))%d)+(1<<L) {
214 F = N + L
215 break
216 }
217 }
218 }
219
220
221
222
223 if F > 32 {
224 fmt.Printf("d=%d max=%d N=%d F=%d\n", c.size, max, N, F)
225 panic("size class requires more than 32 bits of precision")
226 }
227
228
229
230 m := ^uint32(0)/uint32(c.size) + 1
231 for n := 0; n <= max; n++ {
232 if uint32((uint64(n)*uint64(m))>>32) != uint32(n/c.size) {
233 fmt.Printf("d=%d max=%d m=%d n=%d\n", d, max, m, n)
234 panic("bad 32-bit multiply magic")
235 }
236 }
237 }
238
239 func printComment(w io.Writer, classes []class) {
240 fmt.Fprintf(w, "// %-5s %-9s %-10s %-7s %-10s %-9s %-9s\n", "class", "bytes/obj", "bytes/span", "objects", "tail waste", "max waste", "min align")
241 prevSize := 0
242 var minAligns [pageShift + 1]int
243 for i, c := range classes {
244 if i == 0 {
245 continue
246 }
247 spanSize := c.npages * pageSize
248 objects := spanSize / c.size
249 tailWaste := spanSize - c.size*(spanSize/c.size)
250 maxWaste := float64((c.size-prevSize-1)*objects+tailWaste) / float64(spanSize)
251 alignBits := bits.TrailingZeros(uint(c.size))
252 if alignBits > pageShift {
253
254 alignBits = pageShift
255 }
256 for i := range minAligns {
257 if i > alignBits {
258 minAligns[i] = 0
259 } else if minAligns[i] == 0 {
260 minAligns[i] = c.size
261 }
262 }
263 prevSize = c.size
264 fmt.Fprintf(w, "// %5d %9d %10d %7d %10d %8.2f%% %9d\n", i, c.size, spanSize, objects, tailWaste, 100*maxWaste, 1<<alignBits)
265 }
266 fmt.Fprintf(w, "\n")
267
268 fmt.Fprintf(w, "// %-9s %-4s %-12s\n", "alignment", "bits", "min obj size")
269 for bits, size := range minAligns {
270 if size == 0 {
271 break
272 }
273 if bits+1 < len(minAligns) && size == minAligns[bits+1] {
274 continue
275 }
276 fmt.Fprintf(w, "// %9d %4d %12d\n", 1<<bits, bits, size)
277 }
278 fmt.Fprintf(w, "\n")
279 }
280
281 func printClasses(w io.Writer, classes []class) {
282 fmt.Fprintln(w, "const (")
283 fmt.Fprintf(w, "_MaxSmallSize = %d\n", maxSmallSize)
284 fmt.Fprintf(w, "smallSizeDiv = %d\n", smallSizeDiv)
285 fmt.Fprintf(w, "smallSizeMax = %d\n", smallSizeMax)
286 fmt.Fprintf(w, "largeSizeDiv = %d\n", largeSizeDiv)
287 fmt.Fprintf(w, "_NumSizeClasses = %d\n", len(classes))
288 fmt.Fprintf(w, "_PageShift = %d\n", pageShift)
289 fmt.Fprintln(w, ")")
290
291 fmt.Fprint(w, "var class_to_size = [_NumSizeClasses]uint16 {")
292 for _, c := range classes {
293 fmt.Fprintf(w, "%d,", c.size)
294 }
295 fmt.Fprintln(w, "}")
296
297 fmt.Fprint(w, "var class_to_allocnpages = [_NumSizeClasses]uint8 {")
298 for _, c := range classes {
299 fmt.Fprintf(w, "%d,", c.npages)
300 }
301 fmt.Fprintln(w, "}")
302
303 fmt.Fprint(w, "var class_to_divmagic = [_NumSizeClasses]uint32 {")
304 for _, c := range classes {
305 if c.size == 0 {
306 fmt.Fprintf(w, "0,")
307 continue
308 }
309 fmt.Fprintf(w, "^uint32(0)/%d+1,", c.size)
310 }
311 fmt.Fprintln(w, "}")
312
313
314 sc := make([]int, smallSizeMax/smallSizeDiv+1)
315 for i := range sc {
316 size := i * smallSizeDiv
317 for j, c := range classes {
318 if c.size >= size {
319 sc[i] = j
320 break
321 }
322 }
323 }
324 fmt.Fprint(w, "var size_to_class8 = [smallSizeMax/smallSizeDiv+1]uint8 {")
325 for _, v := range sc {
326 fmt.Fprintf(w, "%d,", v)
327 }
328 fmt.Fprintln(w, "}")
329
330
331 sc = make([]int, (maxSmallSize-smallSizeMax)/largeSizeDiv+1)
332 for i := range sc {
333 size := smallSizeMax + i*largeSizeDiv
334 for j, c := range classes {
335 if c.size >= size {
336 sc[i] = j
337 break
338 }
339 }
340 }
341 fmt.Fprint(w, "var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv+1]uint8 {")
342 for _, v := range sc {
343 fmt.Fprintf(w, "%d,", v)
344 }
345 fmt.Fprintln(w, "}")
346 }
347
View as plain text