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 int32 runtime_class_to_transfercount[NumSizeClasses];
  35
  36 // The SizeToClass lookup is implemented using two arrays,
  37 // one mapping sizes <= 1024 to their class and one mapping
  38 // sizes >= 1024 and <= MaxSmallSize to their class.
  39 // All objects are 8-aligned, so the first array is indexed by
  40 // the size divided by 8 (rounded up).  Objects >= 1024 bytes
  41 // are 128-aligned, so the second array is indexed by the
  42 // size divided by 128 (rounded up).  The arrays are filled in
  43 // by InitSizes.
  44
  45 static int32 size_to_class8[1024/8 + 1];
  46 static int32 size_to_class128[(MaxSmallSize-1024)/128 + 1];
  47
  48 int32
  49 runtime_SizeToClass(int32 size)
  50 {
  51         if(size > MaxSmallSize)
  52                 runtime_throw("SizeToClass - invalid size");
  53         if(size > 1024-8)
  54                 return size_to_class128[(size-1024+127) >> 7];
  55         return size_to_class8[(size+7)>>3];
  56 }
  57
  58 void
  59 runtime_InitSizes(void)
  60 {
  61         int32 align, sizeclass, size, nextsize, n;
  62         uint32 i;
  63         uintptr allocsize, npages;
  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                         size_to_class8[nextsize/8] = sizeclass;
 115                 if(nextsize >= 1024)
 116                         for(; nextsize <= runtime_class_to_size[sizeclass]; nextsize += 128)
 117                                 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         for(i=0; i<nelem(runtime_class_to_size); i++)
 139                 mstats.by_size[i].size = runtime_class_to_size[i];
 140
 141         // Initialize the runtime_class_to_transfercount table.
 142         for(sizeclass = 1; sizeclass < NumSizeClasses; sizeclass++) {
 143                 n = 64*1024 / runtime_class_to_size[sizeclass];
 144                 if(n < 2)
 145                         n = 2;
 146                 if(n > 32)
 147                         n = 32;
 148                 runtime_class_to_transfercount[sizeclass] = n;
 149         }
 150         return;
 151
 152 dump:
 153         if(1){
 154                 runtime_printf("NumSizeClasses=%d\n", NumSizeClasses);
 155                 runtime_printf("runtime_class_to_size:");
 156                 for(sizeclass=0; sizeclass<NumSizeClasses; sizeclass++)
 157                         runtime_printf(" %d", runtime_class_to_size[sizeclass]);
 158                 runtime_printf("\n\n");
 159                 runtime_printf("size_to_class8:");
 160                 for(i=0; i<nelem(size_to_class8); i++)
 161                         runtime_printf(" %d=>%d(%d)\n", i*8, size_to_class8[i], runtime_class_to_size[size_to_class8[i]]);
 162                 runtime_printf("\n");
 163                 runtime_printf("size_to_class128:");
 164                 for(i=0; i<nelem(size_to_class128); i++)
 165                         runtime_printf(" %d=>%d(%d)\n", i*128, size_to_class128[i], runtime_class_to_size[size_to_class128[i]]);
 166                 runtime_printf("\n");
 167         }
 168         runtime_throw("InitSizes failed");
 169 }