diff options
Diffstat (limited to 'src/runtime/msize.c')
| -rw-r--r-- | src/runtime/msize.c | 184 |
1 files changed, 184 insertions, 0 deletions
diff --git a/src/runtime/msize.c b/src/runtime/msize.c new file mode 100644 index 000000000..7cb65dad0 --- /dev/null +++ b/src/runtime/msize.c @@ -0,0 +1,184 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Malloc small size classes. +// +// See malloc.h for overview. +// +// The size classes are chosen so that rounding an allocation +// request up to the next size class wastes at most 12.5% (1.125x). +// +// Each size class has its own page count that gets allocated +// and chopped up when new objects of the size class are needed. +// That page count is chosen so that chopping up the run of +// pages into objects of the given size wastes at most 12.5% (1.125x) +// of the memory. It is not necessary that the cutoff here be +// the same as above. +// +// The two sources of waste multiply, so the worst possible case +// for the above constraints would be that allocations of some +// size might have a 26.6% (1.266x) overhead. +// In practice, only one of the wastes comes into play for a +// given size (sizes < 512 waste mainly on the round-up, +// sizes > 512 waste mainly on the page chopping). +// +// TODO(rsc): Compute max waste for any given size. + +#include "runtime.h" +#include "arch_GOARCH.h" +#include "malloc.h" +#include "textflag.h" + +#pragma dataflag NOPTR +int32 runtime·class_to_size[NumSizeClasses]; +#pragma dataflag NOPTR +int32 runtime·class_to_allocnpages[NumSizeClasses]; + +// The SizeToClass lookup is implemented using two arrays, +// one mapping sizes <= 1024 to their class and one mapping +// sizes >= 1024 and <= MaxSmallSize to their class. +// All objects are 8-aligned, so the first array is indexed by +// the size divided by 8 (rounded up). Objects >= 1024 bytes +// are 128-aligned, so the second array is indexed by the +// size divided by 128 (rounded up). The arrays are filled in +// by InitSizes. + +#pragma dataflag NOPTR +int8 runtime·size_to_class8[1024/8 + 1]; +#pragma dataflag NOPTR +int8 runtime·size_to_class128[(MaxSmallSize-1024)/128 + 1]; + +void runtime·testdefersizes(void); + +int32 +runtime·SizeToClass(int32 size) +{ + if(size > MaxSmallSize) + runtime·throw("SizeToClass - invalid size"); + if(size > 1024-8) + return runtime·size_to_class128[(size-1024+127) >> 7]; + return runtime·size_to_class8[(size+7)>>3]; +} + +void +runtime·InitSizes(void) +{ + int32 align, sizeclass, size, nextsize, n; + uint32 i; + uintptr allocsize, npages; + + // Initialize the runtime·class_to_size table (and choose class sizes in the process). + runtime·class_to_size[0] = 0; + sizeclass = 1; // 0 means no class + align = 8; + for(size = align; size <= MaxSmallSize; size += align) { + if((size&(size-1)) == 0) { // bump alignment once in a while + if(size >= 2048) + align = 256; + else if(size >= 128) + align = size / 8; + else if(size >= 16) + align = 16; // required for x86 SSE instructions, if we want to use them + } + if((align&(align-1)) != 0) + runtime·throw("InitSizes - bug"); + + // Make the allocnpages big enough that + // the leftover is less than 1/8 of the total, + // so wasted space is at most 12.5%. + allocsize = PageSize; + while(allocsize%size > allocsize/8) + allocsize += PageSize; + npages = allocsize >> PageShift; + + // If the previous sizeclass chose the same + // allocation size and fit the same number of + // objects into the page, we might as well + // use just this size instead of having two + // different sizes. + if(sizeclass > 1 && + npages == runtime·class_to_allocnpages[sizeclass-1] && + allocsize/size == allocsize/runtime·class_to_size[sizeclass-1]) { + runtime·class_to_size[sizeclass-1] = size; + continue; + } + + runtime·class_to_allocnpages[sizeclass] = npages; + runtime·class_to_size[sizeclass] = size; + sizeclass++; + } + if(sizeclass != NumSizeClasses) { + runtime·printf("sizeclass=%d NumSizeClasses=%d\n", sizeclass, NumSizeClasses); + runtime·throw("InitSizes - bad NumSizeClasses"); + } + + // Initialize the size_to_class tables. + nextsize = 0; + for (sizeclass = 1; sizeclass < NumSizeClasses; sizeclass++) { + for(; nextsize < 1024 && nextsize <= runtime·class_to_size[sizeclass]; nextsize+=8) + runtime·size_to_class8[nextsize/8] = sizeclass; + if(nextsize >= 1024) + for(; nextsize <= runtime·class_to_size[sizeclass]; nextsize += 128) + runtime·size_to_class128[(nextsize-1024)/128] = sizeclass; + } + + // Double-check SizeToClass. + if(0) { + for(n=0; n < MaxSmallSize; n++) { + sizeclass = runtime·SizeToClass(n); + if(sizeclass < 1 || sizeclass >= NumSizeClasses || runtime·class_to_size[sizeclass] < n) { + runtime·printf("size=%d sizeclass=%d runtime·class_to_size=%d\n", n, sizeclass, runtime·class_to_size[sizeclass]); + runtime·printf("incorrect SizeToClass"); + goto dump; + } + if(sizeclass > 1 && runtime·class_to_size[sizeclass-1] >= n) { + runtime·printf("size=%d sizeclass=%d runtime·class_to_size=%d\n", n, sizeclass, runtime·class_to_size[sizeclass]); + runtime·printf("SizeToClass too big"); + goto dump; + } + } + } + + runtime·testdefersizes(); + + // Copy out for statistics table. + for(i=0; i<nelem(runtime·class_to_size); i++) + mstats.by_size[i].size = runtime·class_to_size[i]; + return; + +dump: + if(1){ + runtime·printf("NumSizeClasses=%d\n", NumSizeClasses); + runtime·printf("runtime·class_to_size:"); + for(sizeclass=0; sizeclass<NumSizeClasses; sizeclass++) + runtime·printf(" %d", runtime·class_to_size[sizeclass]); + runtime·printf("\n\n"); + runtime·printf("size_to_class8:"); + for(i=0; i<nelem(runtime·size_to_class8); i++) + runtime·printf(" %d=>%d(%d)\n", i*8, runtime·size_to_class8[i], + runtime·class_to_size[runtime·size_to_class8[i]]); + runtime·printf("\n"); + runtime·printf("size_to_class128:"); + for(i=0; i<nelem(runtime·size_to_class128); i++) + runtime·printf(" %d=>%d(%d)\n", i*128, runtime·size_to_class128[i], + runtime·class_to_size[runtime·size_to_class128[i]]); + runtime·printf("\n"); + } + runtime·throw("InitSizes failed"); +} + +// Returns size of the memory block that mallocgc will allocate if you ask for the size. +uintptr +runtime·roundupsize(uintptr size) +{ + if(size < MaxSmallSize) { + if(size <= 1024-8) + return runtime·class_to_size[runtime·size_to_class8[(size+7)>>3]]; + else + return runtime·class_to_size[runtime·size_to_class128[(size-1024+127) >> 7]]; + } + if(size + PageSize < size) + return size; + return ROUND(size, PageSize); +} |