1 // Copyright 2016 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // +build ignore 6 7 // Generate tables for small malloc size classes. 8 // 9 // See malloc.go for overview. 10 // 11 // The size classes are chosen so that rounding an allocation 12 // request up to the next size class wastes at most 12.5% (1.125x). 13 // 14 // Each size class has its own page count that gets allocated 15 // and chopped up when new objects of the size class are needed. 16 // That page count is chosen so that chopping up the run of 17 // pages into objects of the given size wastes at most 12.5% (1.125x) 18 // of the memory. It is not necessary that the cutoff here be 19 // the same as above. 20 // 21 // The two sources of waste multiply, so the worst possible case 22 // for the above constraints would be that allocations of some 23 // size might have a 26.6% (1.266x) overhead. 24 // In practice, only one of the wastes comes into play for a 25 // given size (sizes < 512 waste mainly on the round-up, 26 // sizes > 512 waste mainly on the page chopping). 27 // 28 // TODO(rsc): Compute max waste for any given size. 29 30 package main 31 32 import ( 33 "bytes" 34 "flag" 35 "fmt" 36 "go/format" 37 "io" 38 "io/ioutil" 39 "log" 40 "os" 41 ) 42 43 // Generate msize.go 44 45 var stdout = flag.Bool("stdout", false, "write to stdout instead of sizeclasses.go") 46 47 func main() { 48 flag.Parse() 49 50 var b bytes.Buffer 51 fmt.Fprintln(&b, "// AUTO-GENERATED by mksizeclasses.go; DO NOT EDIT") 52 fmt.Fprintln(&b, "//go:generate go run mksizeclasses.go") 53 fmt.Fprintln(&b) 54 fmt.Fprintln(&b, "package runtime") 55 classes := makeClasses() 56 57 printComment(&b, classes) 58 59 printClasses(&b, classes) 60 61 out, err := format.Source(b.Bytes()) 62 if err != nil { 63 log.Fatal(err) 64 } 65 if *stdout { 66 _, err = os.Stdout.Write(out) 67 } else { 68 err = ioutil.WriteFile("sizeclasses.go", out, 0666) 69 } 70 if err != nil { 71 log.Fatal(err) 72 } 73 } 74 75 const ( 76 // Constants that we use and will transfer to the runtime. 77 maxSmallSize = 32 << 10 78 smallSizeDiv = 8 79 smallSizeMax = 1024 80 largeSizeDiv = 128 81 pageShift = 13 82 83 // Derived constants. 84 pageSize = 1 << pageShift 85 ) 86 87 type class struct { 88 size int // max size 89 npages int // number of pages 90 91 mul int 92 shift uint 93 shift2 uint 94 mask int 95 } 96 97 func powerOfTwo(x int) bool { 98 return x != 0 && x&(x-1) == 0 99 } 100 101 func makeClasses() []class { 102 var classes []class 103 104 classes = append(classes, class{}) // class #0 is a dummy entry 105 106 align := 8 107 for size := align; size <= maxSmallSize; size += align { 108 if powerOfTwo(size) { // bump alignment once in a while 109 if size >= 2048 { 110 align = 256 111 } else if size >= 128 { 112 align = size / 8 113 } else if size >= 16 { 114 align = 16 // required for x86 SSE instructions, if we want to use them 115 } 116 } 117 if !powerOfTwo(align) { 118 panic("incorrect alignment") 119 } 120 121 // Make the allocnpages big enough that 122 // the leftover is less than 1/8 of the total, 123 // so wasted space is at most 12.5%. 124 allocsize := pageSize 125 for allocsize%size > allocsize/8 { 126 allocsize += pageSize 127 } 128 npages := allocsize / pageSize 129 130 // If the previous sizeclass chose the same 131 // allocation size and fit the same number of 132 // objects into the page, we might as well 133 // use just this size instead of having two 134 // different sizes. 135 if len(classes) > 1 && npages == classes[len(classes)-1].npages && allocsize/size == allocsize/classes[len(classes)-1].size { 136 classes[len(classes)-1].size = size 137 continue 138 } 139 classes = append(classes, class{size: size, npages: npages}) 140 } 141 142 // Increase object sizes if we can fit the same number of larger objects 143 // into the same number of pages. For example, we choose size 8448 above 144 // with 6 objects in 7 pages. But we can well use object size 9472, 145 // which is also 6 objects in 7 pages but +1024 bytes (+12.12%). 146 // We need to preserve at least largeSizeDiv alignment otherwise 147 // sizeToClass won't work. 148 for i := range classes { 149 if i == 0 { 150 continue 151 } 152 c := &classes[i] 153 psize := c.npages * pageSize 154 new_size := (psize / (psize / c.size)) &^ (largeSizeDiv - 1) 155 if new_size > c.size { 156 c.size = new_size 157 } 158 } 159 160 if len(classes) != 67 { 161 panic("number of size classes has changed") 162 } 163 164 for i := range classes { 165 computeDivMagic(&classes[i]) 166 } 167 168 return classes 169 } 170 171 // computeDivMagic computes some magic constants to implement 172 // the division required to compute object number from span offset. 173 // n / c.size is implemented as n >> c.shift * c.mul >> c.shift2 174 // for all 0 <= n < c.npages * pageSize 175 func computeDivMagic(c *class) { 176 // divisor 177 d := c.size 178 if d == 0 { 179 return 180 } 181 182 // maximum input value for which the formula needs to work. 183 max := c.npages*pageSize - 1 184 185 if powerOfTwo(d) { 186 // If the size is a power of two, heapBitsForObject can divide even faster by masking. 187 // Compute this mask. 188 if max >= 1<<16 { 189 panic("max too big for power of two size") 190 } 191 c.mask = 1<<16 - d 192 } 193 194 // Compute pre-shift by factoring power of 2 out of d. 195 for d%2 == 0 { 196 c.shift++ 197 d >>= 1 198 max >>= 1 199 } 200 201 // Find the smallest k that works. 202 // A small k allows us to fit the math required into 32 bits 203 // so we can use 32-bit multiplies and shifts on 32-bit platforms. 204 nextk: 205 for k := uint(0); ; k++ { 206 mul := (int(1)<<k + d - 1) / d // 2^k / d 207 208 // Test to see if mul works. 209 for n := 0; n <= max; n++ { 210 if n*mul>>k != n/d { 211 continue nextk 212 } 213 } 214 if mul >= 1<<16 { 215 panic("mul too big") 216 } 217 if uint64(mul)*uint64(max) >= 1<<32 { 218 panic("mul*max too big") 219 } 220 c.mul = mul 221 c.shift2 = k 222 break 223 } 224 225 // double-check. 226 for n := 0; n <= max; n++ { 227 if n*c.mul>>c.shift2 != n/d { 228 fmt.Printf("d=%d max=%d mul=%d shift2=%d n=%d\n", d, max, c.mul, c.shift2, n) 229 panic("bad multiply magic") 230 } 231 // Also check the exact computations that will be done by the runtime, 232 // for both 32 and 64 bit operations. 233 if uint32(n)*uint32(c.mul)>>uint8(c.shift2) != uint32(n/d) { 234 fmt.Printf("d=%d max=%d mul=%d shift2=%d n=%d\n", d, max, c.mul, c.shift2, n) 235 panic("bad 32-bit multiply magic") 236 } 237 if uint64(n)*uint64(c.mul)>>uint8(c.shift2) != uint64(n/d) { 238 fmt.Printf("d=%d max=%d mul=%d shift2=%d n=%d\n", d, max, c.mul, c.shift2, n) 239 panic("bad 64-bit multiply magic") 240 } 241 } 242 } 243 244 func printComment(w io.Writer, classes []class) { 245 fmt.Fprintf(w, "// %-5s %-9s %-10s %-7s %-11s\n", "class", "bytes/obj", "bytes/span", "objects", "waste bytes") 246 for i, c := range classes { 247 if i == 0 { 248 continue 249 } 250 spanSize := c.npages * pageSize 251 objects := spanSize / c.size 252 waste := spanSize - c.size*(spanSize/c.size) 253 fmt.Fprintf(w, "// %5d %9d %10d %7d %11d\n", i, c.size, spanSize, objects, waste) 254 } 255 fmt.Fprintf(w, "\n") 256 } 257 258 func printClasses(w io.Writer, classes []class) { 259 fmt.Fprintln(w, "const (") 260 fmt.Fprintf(w, "_MaxSmallSize = %d\n", maxSmallSize) 261 fmt.Fprintf(w, "smallSizeDiv = %d\n", smallSizeDiv) 262 fmt.Fprintf(w, "smallSizeMax = %d\n", smallSizeMax) 263 fmt.Fprintf(w, "largeSizeDiv = %d\n", largeSizeDiv) 264 fmt.Fprintf(w, "_NumSizeClasses = %d\n", len(classes)) 265 fmt.Fprintf(w, "_PageShift = %d\n", pageShift) 266 fmt.Fprintln(w, ")") 267 268 fmt.Fprint(w, "var class_to_size = [_NumSizeClasses]uint16 {") 269 for _, c := range classes { 270 fmt.Fprintf(w, "%d,", c.size) 271 } 272 fmt.Fprintln(w, "}") 273 274 fmt.Fprint(w, "var class_to_allocnpages = [_NumSizeClasses]uint8 {") 275 for _, c := range classes { 276 fmt.Fprintf(w, "%d,", c.npages) 277 } 278 fmt.Fprintln(w, "}") 279 280 fmt.Fprintln(w, "type divMagic struct {") 281 fmt.Fprintln(w, " shift uint8") 282 fmt.Fprintln(w, " shift2 uint8") 283 fmt.Fprintln(w, " mul uint16") 284 fmt.Fprintln(w, " baseMask uint16") 285 fmt.Fprintln(w, "}") 286 fmt.Fprint(w, "var class_to_divmagic = [_NumSizeClasses]divMagic {") 287 for _, c := range classes { 288 fmt.Fprintf(w, "{%d,%d,%d,%d},", c.shift, c.shift2, c.mul, c.mask) 289 } 290 fmt.Fprintln(w, "}") 291 292 // map from size to size class, for small sizes. 293 sc := make([]int, smallSizeMax/smallSizeDiv+1) 294 for i := range sc { 295 size := i * smallSizeDiv 296 for j, c := range classes { 297 if c.size >= size { 298 sc[i] = j 299 break 300 } 301 } 302 } 303 fmt.Fprint(w, "var size_to_class8 = [smallSizeMax/smallSizeDiv+1]uint8 {") 304 for _, v := range sc { 305 fmt.Fprintf(w, "%d,", v) 306 } 307 fmt.Fprintln(w, "}") 308 309 // map from size to size class, for large sizes. 310 sc = make([]int, (maxSmallSize-smallSizeMax)/largeSizeDiv+1) 311 for i := range sc { 312 size := smallSizeMax + i*largeSizeDiv 313 for j, c := range classes { 314 if c.size >= size { 315 sc[i] = j 316 break 317 } 318 } 319 } 320 fmt.Fprint(w, "var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv+1]uint8 {") 321 for _, v := range sc { 322 fmt.Fprintf(w, "%d,", v) 323 } 324 fmt.Fprintln(w, "}") 325 } 326