libgo/runtime/msize.c

   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
  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
  58 runtime_InitSizes(void)
  59 {
  60         int32 align, sizeclass, size, nextsize, n;
  61         uint32 i;
  62         uintptr allocsize, npages;
  63         MStats *pmstats;
  64
  65         // Initialize the runtime_class_to_size table (and choose class sizes in the process).
  66         runtime_class_to_size[0] = 0;
  67         sizeclass = 1;  // 0 means no class
  68         align = 8;
  69         for(size = align; size <= MaxSmallSize; size += align) {
  70                 if((size&(size-1)) == 0) {      // bump alignment once in a while
  71                         if(size >= 2048)
  72                                 align = 256;
  73                         else if(size >= 128)
  74                                 align = size / 8;
  75                         else if(size >= 16)
  76                                 align = 16;     // required for x86 SSE instructions, if we want to use them
  77                 }
  78                 if((align&(align-1)) != 0)
  79                         runtime_throw("InitSizes - bug");
  80
  81                 // Make the allocnpages big enough that
  82                 // the leftover is less than 1/8 of the total,
  83                 // so wasted space is at most 12.5%.
  84                 allocsize = PageSize;
  85                 while(allocsize%size > allocsize/8)
  86                         allocsize += PageSize;
  87                 npages = allocsize >> PageShift;
  88
  89                 // If the previous sizeclass chose the same
  90                 // allocation size and fit the same number of
  91                 // objects into the page, we might as well
  92                 // use just this size instead of having two
  93                 // different sizes.
  94                 if(sizeclass > 1 &&
  95                         (int32)npages == runtime_class_to_allocnpages[sizeclass-1] &&
  96                         allocsize/size == allocsize/runtime_class_to_size[sizeclass-1]) {
  97                         runtime_class_to_size[sizeclass-1] = size;
  98                         continue;
  99                 }
 100
 101                 runtime_class_to_allocnpages[sizeclass] = npages;
 102                 runtime_class_to_size[sizeclass] = size;
 103                 sizeclass++;
 104         }
 105         if(sizeclass != _NumSizeClasses) {
 106                 runtime_printf("sizeclass=%d _NumSizeClasses=%d\n", sizeclass, _NumSizeClasses);
 107                 runtime_throw("InitSizes - bad _NumSizeClasses");
 108         }
 109
 110         // Initialize the size_to_class tables.
 111         nextsize = 0;
 112         for (sizeclass = 1; sizeclass < _NumSizeClasses; sizeclass++) {
 113                 for(; nextsize < 1024 && nextsize <= runtime_class_to_size[sizeclass]; nextsize+=8)
 114                         runtime_size_to_class8[nextsize/8] = sizeclass;
 115                 if(nextsize >= 1024)
 116                         for(; nextsize <= runtime_class_to_size[sizeclass]; nextsize += 128)
 117                                 runtime_size_to_class128[(nextsize-1024)/128] = sizeclass;
 118         }
 119
 120         // Double-check SizeToClass.
 121         if(0) {
 122                 for(n=0; n < MaxSmallSize; n++) {
 123                         sizeclass = runtime_SizeToClass(n);
 124                         if(sizeclass < 1 || sizeclass >= _NumSizeClasses || runtime_class_to_size[sizeclass] < n) {
 125                                 runtime_printf("size=%d sizeclass=%d runtime_class_to_size=%d\n", n, sizeclass, runtime_class_to_size[sizeclass]);
 126                                 runtime_printf("incorrect SizeToClass");
 127                                 goto dump;
 128                         }
 129                         if(sizeclass > 1 && runtime_class_to_size[sizeclass-1] >= n) {
 130                                 runtime_printf("size=%d sizeclass=%d runtime_class_to_size=%d\n", n, sizeclass, runtime_class_to_size[sizeclass]);
 131                                 runtime_printf("SizeToClass too big");
 132                                 goto dump;
 133                         }
 134                 }
 135         }
 136
 137         // Copy out for statistics table.
 138         pmstats = mstats();
 139         for(i=0; i<nelem(runtime_class_to_size); i++)
 140                 pmstats->by_size[i].size = runtime_class_to_size[i];
 141         return;
 142
 143 dump:
 144         if(1){
 145                 runtime_printf("NumSizeClasses=%d\n", _NumSizeClasses);
 146                 runtime_printf("runtime_class_to_size:");
 147                 for(sizeclass=0; sizeclass<_NumSizeClasses; sizeclass++)
 148                         runtime_printf(" %d", runtime_class_to_size[sizeclass]);
 149                 runtime_printf("\n\n");
 150                 runtime_printf("size_to_class8:");
 151                 for(i=0; i<nelem(runtime_size_to_class8); i++)
 152                         runtime_printf(" %d=>%d(%d)\n", i*8, runtime_size_to_class8[i],
 153                                 runtime_class_to_size[runtime_size_to_class8[i]]);
 154                 runtime_printf("\n");
 155                 runtime_printf("size_to_class128:");
 156                 for(i=0; i<nelem(runtime_size_to_class128); i++)
 157                         runtime_printf(" %d=>%d(%d)\n", i*128, runtime_size_to_class128[i],
 158                                 runtime_class_to_size[runtime_size_to_class128[i]]);
 159                 runtime_printf("\n");
 160         }
 161         runtime_throw("InitSizes failed");
 162 }
 163
 164 // Returns size of the memory block that mallocgc will allocate if you ask for the size.
 165 uintptr
 166 runtime_roundupsize(uintptr size)
 167 {
 168         if(size < MaxSmallSize) {
 169                 if(size <= 1024-8)
 170                         return runtime_class_to_size[runtime_size_to_class8[(size+7)>>3]];
 171                 else
 172                         return runtime_class_to_size[runtime_size_to_class128[(size-1024+127) >> 7]];
 173         }
 174         if(size + PageSize < size)
 175                 return size;
 176         return ROUND(size, PageSize);
 177 }