分类： LINUX
2011-10-08 15:43:09
在initStaticVars()里面首先会调用SizeMap.init。SizeMap是一个非常关键的数据结构，下面我们对他先进行分析。
关于SizeMap结构（common.cc和common.h）
SizeMap里面涉及到几个关键的数据结构class_array_，class_to_size_，class_to_pages_，num_objects_to_move_。其中class_array将一个size映射成为一个class num（总共61个num），根据这个num可以从class_to_size_和class_to_pages_拿出这个class可分配obj的最大size，以及一次从系统中alloc出多少个页面。地址映射到class_array的index方法按照下图所示：
// Sizes <= 1024 have an alignment >= 8. So for such sizes we have an
// array indexed by ceil(size/8). Sizes > 1024 have an alignment >= 128.
// So for these larger sizes we have an array indexed by ceil(size/128).
//
// We flatten both logical arrays into one physical array and use
// arithmetic to compute an appropriate index. The constants used by
// ClassIndex() were selected to make the flattening work.
//
// Examples:
// Size Expression Index
// -------------------------------------------------------
// 0 (0 + 7) / 8 0
// 1 (1 + 7) / 8 1
// ...
// 1024 (1024 + 7) / 8 128
// 1025 (1025 + 127 + (120<<7)) / 128 129
// ...
// 32768 (32768 + 127 + (120<<7)) / 128 376
num_objects_to_move_保存了每次在主heap区和per-thread heap区之间移动相应kClassNum指定obj的数量。这样是为了平衡移动obj数量的开销，次数和内存浪费数量之间的平衡。以下函数就是主要做上面四个数据结构的初始化工作。
void SizeMap::Init() {
// Do some sanity checking on add_amount[]/shift_amount[]/class_array[]
if (ClassIndex(0) < 0) {
CRASH("Invalid class index %d for size 0\n", ClassIndex(0));
}
if (ClassIndex(kMaxSize) >= sizeof(class_array_)) {
CRASH("Invalid class index %d for kMaxSize\n", ClassIndex(kMaxSize));
}
// Compute the size classes we want to use
int sc = 1; // Next size class to assign
int alignment = kAlignment;
CHECK_CONDITION(kAlignment <= 16);
int last_lg = -1;
for (size_t size = kAlignment; size <= kMaxSize; size += alignment) {
int lg = LgFloor(size);//LgFloor根据提供的size算出需要几bits来对齐
if (lg > last_lg) {
// Increase alignment every so often to reduce number of size classes.
alignment = AlignmentForSize(size);
// separated by 8 bytes（小于16bytes）, larger sizes by 16 bytes（16到128）, even larger sizes by 32 bytes（128到2K，(1 << LgFloor(size)) / 8）, and so forth. The maximal spacing (for sizes >= ~2K) is 256 bytes.
last_lg = lg;
}
CHECK_CONDITION((size % alignment) == 0);
// Allocate enough pages so leftover is less than 1/8 of total.
// This bounds wasted space to at most 12.5%.
size_t psize = kPageSize;
while ((psize % size) > (psize >> 3)) {
psize += kPageSize;
}//此处保证alloc的page数组成的空间在被划分为size的obj的同时确保遗留小于1/8的空余空间
const size_t my_pages = psize >> kPageShift;
if (sc > 1 && my_pages == class_to_pages_[sc-1]) {
// See if we can merge this into the previous class without
// increasing the fragmentation of the previous class.
const size_t my_objects = (my_pages << kPageShift) / size;
const size_t prev_objects = (class_to_pages_[sc-1] << kPageShift)
/ class_to_size_[sc-1];
if (my_objects == prev_objects) {
// Adjust last class to include this size
class_to_size_[sc-1] = size;
continue;
/*这部分比较难理解，举例说明，假设my_pages 为1而size现在为1024，那么my_objects =4，而前面已经建立的class_to_size_=1023，那么prev_objects 也为4那么就用现在的size替换原来的size，这部分的意思就是在同样的page数量和obj数量的情况下得找到每个obj的最大值*/
}
}
// Add new class
class_to_pages_[sc] = my_pages;//初始化class_to_pages_和class_to_size_两个数组
class_to_size_[sc] = size;
sc++;
}
if (sc != kNumClasses) {
CRASH("wrong number of size classes: found %d instead of %d\n",
sc, int(kNumClasses));
}
// Initialize the mapping arrays
int next_size = 0;
for (int c = 1; c < kNumClasses; c++) {
const int max_size_in_class = class_to_size_[c];
for (int s = next_size; s <= max_size_in_class; s += kAlignment) {
class_array_[ClassIndex(s)] = c;//初始化class_array，具体可以查看ClassIndex函数
}
next_size = max_size_in_class + kAlignment;
}
// Double-check sizes just to be safe
for (size_t size = 0; size <= kMaxSize; size++) {
const int sc = SizeClass(size);
if (sc <= 0 || sc >= kNumClasses) {
CRASH("Bad size class %d for %" PRIuS "\n", sc, size);
}
if (sc > 1 && size <= class_to_size_[sc-1]) {
CRASH("Allocating unnecessarily large class %d for %" PRIuS
"\n", sc, size);
}
const size_t s = class_to_size_[sc];
if (size > s) {
CRASH("Bad size %" PRIuS " for %" PRIuS " (sc = %d)\n", s, size, sc);
}
if (s == 0) {
CRASH("Bad size %" PRIuS " for %" PRIuS " (sc = %d)\n", s, size, sc);
}
}
// Initialize the num_objects_to_move array.
for (size_t cl = 1; cl < kNumClasses; ++cl) {
num_objects_to_move_[cl] = NumMoveSize(ByteSizeForClass(cl));
}
}
