1 // Copyright 2009 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 // Malloc small size classes.
6 //
7 // See malloc.h for overview.
8 //
9 // The size classes are chosen so that rounding an allocation
10 // request up to the next size class wastes at most 12.5% (1.125x).
11 //
12 // Each size class has its own page count that gets allocated
13 // and chopped up when new objects of the size class are needed.
14 // That page count is chosen so that chopping up the run of
15 // pages into objects of the given size wastes at most 12.5% (1.125x)
16 // of the memory. It is not necessary that the cutoff here be
17 // the same as above.
18 //
19 // The two sources of waste multiply, so the worst possible case
20 // for the above constraints would be that allocations of some
21 // size might have a 26.6% (1.266x) overhead.
22 // In practice, only one of the wastes comes into play for a
23 // given size (sizes < 512 waste mainly on the round-up,
24 // sizes > 512 waste mainly on the page chopping).
25 //
26 // TODO(rsc): Compute max waste for any given size.
27
28 #include "runtime.h"
29 #include "arch.h"
30 #include "malloc.h"
31
32 int32 runtime_class_to_size[NumSizeClasses];
33 int32 runtime_class_to_allocnpages[NumSizeClasses];
34
35 // The SizeToClass lookup is implemented using two arrays,
36 // one mapping sizes <= 1024 to their class and one mapping
37 // sizes >= 1024 and <= MaxSmallSize to their class.
38 // All objects are 8-aligned, so the first array is indexed by
39 // the size divided by 8 (rounded up). Objects >= 1024 bytes
40 // are 128-aligned, so the second array is indexed by the
41 // size divided by 128 (rounded up). The arrays are filled in
42 // by InitSizes.
43
44 int8 runtime_size_to_class8[1024/8 + 1];
45 int8 runtime_size_to_class128[(MaxSmallSize-1024)/128 + 1];
46
47 int32
runtime_SizeToClass(int32 size)48 runtime_SizeToClass(int32 size)
49 {
50 if(size > MaxSmallSize)
51 runtime_throw("SizeToClass - invalid size");
52 if(size > 1024-8)
53 return runtime_size_to_class128[(size-1024+127) >> 7];
54 return runtime_size_to_class8[(size+7)>>3];
55 }
56
57 void
runtime_InitSizes(void)58 runtime_InitSizes(void)
59 {
60 int32 align, sizeclass, size, nextsize, n;
61 uint32 i;
62 uintptr allocsize, npages;
63
64 // Initialize the runtime_class_to_size table (and choose class sizes in the process).
65 runtime_class_to_size[0] = 0;
66 sizeclass = 1; // 0 means no class
67 align = 8;
68 for(size = align; size <= MaxSmallSize; size += align) {
69 if((size&(size-1)) == 0) { // bump alignment once in a while
70 if(size >= 2048)
71 align = 256;
72 else if(size >= 128)
73 align = size / 8;
74 else if(size >= 16)
75 align = 16; // required for x86 SSE instructions, if we want to use them
76 }
77 if((align&(align-1)) != 0)
78 runtime_throw("InitSizes - bug");
79
80 // Make the allocnpages big enough that
81 // the leftover is less than 1/8 of the total,
82 // so wasted space is at most 12.5%.
83 allocsize = PageSize;
84 while(allocsize%size > allocsize/8)
85 allocsize += PageSize;
86 npages = allocsize >> PageShift;
87
88 // If the previous sizeclass chose the same
89 // allocation size and fit the same number of
90 // objects into the page, we might as well
91 // use just this size instead of having two
92 // different sizes.
93 if(sizeclass > 1 &&
94 (int32)npages == runtime_class_to_allocnpages[sizeclass-1] &&
95 allocsize/size == allocsize/runtime_class_to_size[sizeclass-1]) {
96 runtime_class_to_size[sizeclass-1] = size;
97 continue;
98 }
99
100 runtime_class_to_allocnpages[sizeclass] = npages;
101 runtime_class_to_size[sizeclass] = size;
102 sizeclass++;
103 }
104 if(sizeclass != NumSizeClasses) {
105 runtime_printf("sizeclass=%d NumSizeClasses=%d\n", sizeclass, NumSizeClasses);
106 runtime_throw("InitSizes - bad NumSizeClasses");
107 }
108
109 // Initialize the size_to_class tables.
110 nextsize = 0;
111 for (sizeclass = 1; sizeclass < NumSizeClasses; sizeclass++) {
112 for(; nextsize < 1024 && nextsize <= runtime_class_to_size[sizeclass]; nextsize+=8)
113 runtime_size_to_class8[nextsize/8] = sizeclass;
114 if(nextsize >= 1024)
115 for(; nextsize <= runtime_class_to_size[sizeclass]; nextsize += 128)
116 runtime_size_to_class128[(nextsize-1024)/128] = sizeclass;
117 }
118
119 // Double-check SizeToClass.
120 if(0) {
121 for(n=0; n < MaxSmallSize; n++) {
122 sizeclass = runtime_SizeToClass(n);
123 if(sizeclass < 1 || sizeclass >= NumSizeClasses || runtime_class_to_size[sizeclass] < n) {
124 runtime_printf("size=%d sizeclass=%d runtime_class_to_size=%d\n", n, sizeclass, runtime_class_to_size[sizeclass]);
125 runtime_printf("incorrect SizeToClass");
126 goto dump;
127 }
128 if(sizeclass > 1 && runtime_class_to_size[sizeclass-1] >= n) {
129 runtime_printf("size=%d sizeclass=%d runtime_class_to_size=%d\n", n, sizeclass, runtime_class_to_size[sizeclass]);
130 runtime_printf("SizeToClass too big");
131 goto dump;
132 }
133 }
134 }
135
136 // Copy out for statistics table.
137 for(i=0; i<nelem(runtime_class_to_size); i++)
138 mstats.by_size[i].size = runtime_class_to_size[i];
139 return;
140
141 dump:
142 if(1){
143 runtime_printf("NumSizeClasses=%d\n", NumSizeClasses);
144 runtime_printf("runtime_class_to_size:");
145 for(sizeclass=0; sizeclass<NumSizeClasses; sizeclass++)
146 runtime_printf(" %d", runtime_class_to_size[sizeclass]);
147 runtime_printf("\n\n");
148 runtime_printf("size_to_class8:");
149 for(i=0; i<nelem(runtime_size_to_class8); i++)
150 runtime_printf(" %d=>%d(%d)\n", i*8, runtime_size_to_class8[i],
151 runtime_class_to_size[runtime_size_to_class8[i]]);
152 runtime_printf("\n");
153 runtime_printf("size_to_class128:");
154 for(i=0; i<nelem(runtime_size_to_class128); i++)
155 runtime_printf(" %d=>%d(%d)\n", i*128, runtime_size_to_class128[i],
156 runtime_class_to_size[runtime_size_to_class128[i]]);
157 runtime_printf("\n");
158 }
159 runtime_throw("InitSizes failed");
160 }
161
162 // Returns size of the memory block that mallocgc will allocate if you ask for the size.
163 uintptr
runtime_roundupsize(uintptr size)164 runtime_roundupsize(uintptr size)
165 {
166 if(size < MaxSmallSize) {
167 if(size <= 1024-8)
168 return runtime_class_to_size[runtime_size_to_class8[(size+7)>>3]];
169 else
170 return runtime_class_to_size[runtime_size_to_class128[(size-1024+127) >> 7]];
171 }
172 if(size + PageSize < size)
173 return size;
174 return ROUND(size, PageSize);
175 }
176