TCMalloc源码阅读（二）--线程局部缓存ClassSize分析
TCMalloc小对象分配机制首先我们回顾下TCMalloc文档的小对象分配机制。文档中说明TCMalloc给每个线程都保存一个缓存池，缓存池里有各种大小的内存对象。小内存分配过程如下：
1. 将要分配的大小映射到对应的对齐对象。
2. 在当前线程的局部缓存中查找该对齐对象链表。
3. 如果该链表不为空，删除链表第一个节点并返回给调用者。

问题

1. 小对象是如何划分的？

2. 对于任意一个小于kMaxSize的size是如何映射到某一种缓存对象上？

本文将通过分析源代码来弄清楚这两个问题。

SizeMap分析在do_malloc函数中有如下两行代码：
size_t cl = Static::sizemap()->SizeClass(size);
size = Static::sizemap()->class_to_size(cl);
不难理解，这两行代码就是size映射到它最接近的缓存对象上。接下来继续探究SizeClass(size_t)和class_to_(size_t)两个函数,这两个函数在common.h文件中，代码如下：

static inline int LgFloor(size_t n) {  int log = 0;  for (int i = 4; i >= 0; --i) {    int shift = (1 << i);    size_t x = n >> shift;    if (x != 0) {      n = x;      log += shift;    }  }  ASSERT(n == 1);  return log;}int AlignmentForSize(size_t size) {  int alignment = kAlignment;  if (size > kMaxSize) {    // Cap alignment at kPageSize for large sizes.    alignment = kPageSize;  } else if (size >= 128) {    // Space wasted due to alignment is at most 1/8, i.e., 12.5%.    alignment = (1 << LgFloor(size)) / 8;  } else if (size >= 16) {    // We need an alignment of at least 16 bytes to satisfy    // requirements for some SSE types.    alignment = 16;  }  // Maximum alignment allowed is page size alignment.  if (alignment > kPageSize) {    alignment = kPageSize;  }  CHECK_CONDITION(size < 16 || alignment >= 16);  CHECK_CONDITION((alignment & (alignment - 1)) == 0);  return alignment;}

先说下LgFloor函数，该函数的功能是返回size值的最高位1的位置。

例如，LgFloor(8)=3, LgFloor(9)=3, LgFloor(10)=3,...,LgFloor(16)=4,...

通过AlignmentForSize函数，我们不难得知class_to_size_的分类规则大致如下：
size在[16,128]之间按16字节对齐，size在[129,256*1024]之间按(2^(n+1)-2^n)/8对齐，n为7~18,
即[129,130,...,256*1024]会被映射为[128+16,128+2*16,...,128+8*16,256+32,256+2*32,...,256+8*32],超过256*1024以上的按页对齐。
因为ClassIndex计算出来的结果还是太密集了，因此需要通过class_array_来索引到其真正映射到的对齐类。

总结1. 线程局部缓存将[0~256*1024]范围的内存按如下规则对齐：
size<16,8字节对齐，对齐结果[8,16]
size在[16,128)之间，按16字节对齐，对齐结果[32,48,...,128]
size在[128,256*1024)，按(2^(n+1)-2^n)/8对齐，对齐结果[128+16,128+2*16,...,128+8*16,256+32,256+2*32,...,256+8*32]
2. 用class_to_size_保存所有对齐结果。
3. class_array_保存ClassIndex(size)到class_to_size_的映射关系。
4. ClassIndex(size)通过简单的字节对齐算法计算class_array_的索引。