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 "malloc.h"
  30
  31 int32 runtime_class_to_size[NumSizeClasses];
  32 int32 runtime_class_to_allocnpages[NumSizeClasses];
  33 int32 runtime_class_to_transfercount[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 static int32 size_to_class8[1024/8 + 1];
  45 static int32 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 size_to_class128[(size-1024+127) >> 7];
  54         return 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
  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                         size_to_class8[nextsize/8] = sizeclass;
 114                 if(nextsize >= 1024)
 115                         for(; nextsize <= runtime_class_to_size[sizeclass]; nextsize += 128)
 116                                 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
 140         // Initialize the runtime_class_to_transfercount table.
 141         for(sizeclass = 1; sizeclass < NumSizeClasses; sizeclass++) {
 142                 n = 64*1024 / runtime_class_to_size[sizeclass];
 143                 if(n < 2)
 144                         n = 2;
 145                 if(n > 32)
 146                         n = 32;
 147                 runtime_class_to_transfercount[sizeclass] = n;
 148         }
 149         return;
 150
 151 dump:
 152         if(1){
 153                 runtime_printf("NumSizeClasses=%d\n", NumSizeClasses);
 154                 runtime_printf("runtime_class_to_size:");
 155                 for(sizeclass=0; sizeclass<NumSizeClasses; sizeclass++)
 156                         runtime_printf(" %d", runtime_class_to_size[sizeclass]);
 157                 runtime_printf("\n\n");
 158                 runtime_printf("size_to_class8:");
 159                 for(i=0; i<nelem(size_to_class8); i++)
 160                         runtime_printf(" %d=>%d(%d)\n", i*8, size_to_class8[i], runtime_class_to_size[size_to_class8[i]]);
 161                 runtime_printf("\n");
 162                 runtime_printf("size_to_class128:");
 163                 for(i=0; i<nelem(size_to_class128); i++)
 164                         runtime_printf(" %d=>%d(%d)\n", i*128, size_to_class128[i], runtime_class_to_size[size_to_class128[i]]);
 165                 runtime_printf("\n");
 166         }
 167         runtime_throw("InitSizes failed");
 168 }