diff options
Diffstat (limited to 'libgo/runtime/msize.c')
| -rw-r--r-- | libgo/runtime/msize.c | 169 |
1 files changed, 169 insertions, 0 deletions
diff --git a/libgo/runtime/msize.c b/libgo/runtime/msize.c new file mode 100644 index 00000000000..8b021a2b6b3 --- /dev/null +++ b/libgo/runtime/msize.c @@ -0,0 +1,169 @@ +// 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 "malloc.h" + +int32 runtime_class_to_size[NumSizeClasses]; +int32 runtime_class_to_allocnpages[NumSizeClasses]; +int32 runtime_class_to_transfercount[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. + +static int32 size_to_class8[1024/8 + 1]; +static int32 size_to_class128[(MaxSmallSize-1024)/128 + 1]; + +int32 +runtime_SizeToClass(int32 size) +{ + if(size > MaxSmallSize) + runtime_throw("SizeToClass - invalid size"); + if(size > 1024-8) + return size_to_class128[(size-1024+127) >> 7]; + return size_to_class8[(size+7)>>3]; +} + +void +runtime_InitSizes(void) +{ + int32 align, sizeclass, size, osize, 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; + osize = size + RefcountOverhead; + while(allocsize%osize > (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 + && (int32)npages == runtime_class_to_allocnpages[sizeclass-1] + && allocsize/osize == allocsize/(runtime_class_to_size[sizeclass-1]+RefcountOverhead)) { + 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) + size_to_class8[nextsize/8] = sizeclass; + if(nextsize >= 1024) + for(; nextsize <= runtime_class_to_size[sizeclass]; nextsize += 128) + 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; + } + } + } + + // 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]; + + // Initialize the runtime_class_to_transfercount table. + for(sizeclass = 1; sizeclass < NumSizeClasses; sizeclass++) { + n = 64*1024 / runtime_class_to_size[sizeclass]; + if(n < 2) + n = 2; + if(n > 32) + n = 32; + runtime_class_to_transfercount[sizeclass] = n; + } + 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(size_to_class8); i++) + runtime_printf(" %d=>%d(%d)\n", i*8, size_to_class8[i], runtime_class_to_size[size_to_class8[i]]); + runtime_printf("\n"); + runtime_printf("size_to_class128:"); + for(i=0; i<nelem(size_to_class128); i++) + runtime_printf(" %d=>%d(%d)\n", i*128, size_to_class128[i], runtime_class_to_size[size_to_class128[i]]); + runtime_printf("\n"); + } + runtime_throw("InitSizes failed"); +} |