URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [runtime/] [msize.c] - Rev 756
Go to most recent revision | Compare with Previous | Blame | View Log
// 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.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, 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 && (int32)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) 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"); }
Go to most recent revision | Compare with Previous | Blame | View Log