TCMalloc源码学习-3-CentralFreeList ·

26 April 2016

TCMalloc源码学习-3-CentralFreeList

这一篇该讲CentralFreeList，CentralFreeList在TCMalloc中扮演一个承上启下的作用，它负责给上层的ThreadCache提供object，并且负责向PageHeap申请页，还是比较重要的，下面慢慢讲

结构

CentralFreeList全局有86个，对应第一篇说的86种小内存的分配策略，先看下主要结构：

class CentralFreeList {
  Span     empty_;          // Dummy header for list of empty spans
  Span     nonempty_;       // Dummy header for list of non-empty spans
  TCEntry tc_slots_[kMaxNumTransferEntries];
}

主要就这么3个数组，empty_ 和 nonempty_ 是两个Span的链表，empty保存着他从PageCache中申请过来的一批页对应的Span，每页都已经按照预先规定的大小划分成等大的object，当上层的ThreadCache向它申请一批object时，它便从nonempty_ 链表的取出第一个Span，将这个Span对应的页里剩余还没有分配出去的object分配出去，假如这个Span里所有的object都已经分配出去，那么就把这个Span从empty_ 摘掉，放到empty_ ，tc_slots_ 是缓存从ThreadCache还回来的一批object，TCEntry保存还回来的object链表的start和end，没错，上层是一批一批的申请，还的时候也是一批一批的返回，其实就是链表，主要的三个数组讲完了，现在来看下代码，先来看一下申请一批object的函数：

int CentralFreeList::RemoveRange(void **start, void **end, int N) {
  //这个是上层ThreadCache向本层申请内存时调用的接口，N是要申请多少个object，申请完
  //之后start和end就指向这些object的第一个和最后一个，返回的一批object其实是个链表
  ASSERT(N > 0);
  lock_.Lock();
  //先从缓存里面找，这里面存着最近被换回来的一批批object
  if (N == Static::sizemap()->num_objects_to_move(size_class_) &&
      used_slots_ > 0) {
    int slot = --used_slots_;
    ASSERT(slot >= 0);
    TCEntry *entry = &tc_slots_[slot];
    *start = entry->head;
    *end = entry->tail;
    lock_.Unlock();
    return N;
  }

  int result = 0;
  void* head = NULL;
  void* tail = NULL;
  // TODO: Prefetch multiple TCEntries?
  //这个函数就是之所以叫safe就是他在从empty_链表里取Span之前，先判断有没有，如果
  //当前已经没有可用的Span，则调用populate向PageHeap申请,返回第一个可用的object的地址
  tail = FetchFromSpansSafe();
  if (tail != NULL) {
    SLL_SetNext(tail, NULL);
    head = tail;
    result = 1;
    while (result < N) {
      // 因为需要N个object，所以不断的调用FetchFromSpans，每次获取一个object，将
      // 他们连成链表
      void *t = FetchFromSpans();
      if (!t) break;
      SLL_Push(&head, t);
      result++;
    }
  }
  lock_.Unlock();
  //最终start指向链表头，end指向链表尾
  *start = head;
  *end = tail;
  return result;
}

逻辑还是非常清晰的，这里重点说一个东西，返回的一批object虽然说是链表，可没有多花一个字节去存节点间的关系，类似于数组链表的实现，虽然每个object是连续的，但是每个object的前4个字节是下一个object的地址，即使object的前4个字节被用了，但当这个object分出去以后，这个字节是可以被用户覆盖掉的，当它还回来以后，再把这个object的前四个字节赋值为当前链表head对应的object的地址，就是插到链表头，然后再将head指向这个object

补充一句，上面代码里说的populate就是向PageHeap申请N个页，将这N个也对应的span插入到nonempty链表，将页划分成等大小的object，除此之外，还有两步重要的操作，第一是RegisterSizeClass，他会把在PageHeap的page_map中这个span的N个页对应的leaf节点的指针指向这个span，方便用地址映射到对应的span，第二个是CacheSizeClass，这个主要记录N个页的每个页属于86个class_size_中的哪一个，这会在用户free的时候用到，比如用户free(ptr)，通过在缓存里查找ptr对应的页属于哪个size_class，就知道该把它放回86个策略的哪个缓存链表里，另外大内存的cachesizeclass一律将每一页记录成0，free的时候只要查到ptr对应的是0就知道这个地址对应的是个大内存，不应该走小内存的归还步骤

退还一批object的实现也很简单，来看代码：

//start，end是object链表的头和尾，N是个数
void CentralFreeList::InsertRange(void *start, void *end, int N) {
  SpinLockHolder h(&lock_);
  // 如果N等于自己对应的size，将这批object放在缓存里，MakeCacheSpace其实就是
  // 如果缓存满了，就从里面踢一条，也就是一批object，把他们还给所属的span
  if (N == Static::sizemap()->num_objects_to_move(size_class_) &&
    MakeCacheSpace()) {
    int slot = used_slots_++;
    ASSERT(slot >=0);
    ASSERT(slot < max_cache_size_);
    TCEntry *entry = &tc_slots_[slot];
    entry->head = start;
    entry->tail = end;
    return;
  }
  //否则，直接还给所属的span
  ReleaseListToSpans(start);
}

void CentralFreeList::ReleaseListToSpans(void* start) {
  //遍历链表，一个一个还，注意数组链表的实现，虽然每个object相邻，但数组序和
  //链表序不应定相同，初次返回一批object给上层的ThreadCache肯定是一样的，但
  //这批object在ThreadCache中分出去的顺序和每个object还回来的顺序不一定一样，
  //所以从ThreadCache还回来的Object链表的链表序不一定和数组序一样，所以链表
  //关系的next值记录在每个object的前四个字节，只要知道start第一个节点，就可
  //以遍历完链表
  while (start) {
    void *next = SLL_Next(start);
    ReleaseToSpans(start);
    start = next;
  }
}

void CentralFreeList::ReleaseToSpans(void* object) {
  //找到object对应的span，PageHeap里不是有一个page_map吗？从那个里面找
  Span* span = MapObjectToSpan(object);
  ASSERT(span != NULL);
  ASSERT(span->refcount > 0);

  // If span is empty, move it to non-empty list
  //如果所属的span之前已经没有可用的object了，那么肯定会被加到empty链表，
  //现在还了一个，所以将他移回nonempty
  if (span->objects == NULL) {
    tcmalloc::DLL_Remove(span);
    tcmalloc::DLL_Prepend(&nonempty_, span);
    Event(span, 'N', 0);
  }

  // The following check is expensive, so it is disabled by default
  if (false) {
    // Check that object does not occur in list
    int got = 0;
    for (void* p = span->objects; p != NULL; p = *((void**) p)) {
      ASSERT(p != object);
      got++;
    }
    ASSERT(got + span->refcount ==
           (span->length<<kPageShift) /
           Static::sizemap()->ByteSizeForClass(span->sizeclass));
  }

  counter_++; //可用的object的数加1
  span->refcount--;  //引用数减1，当为0的时候就代表这个span完全没被用
  if (span->refcount == 0) {
    //当span的所有object都被还回来，就将这个span从empty链表去掉，还回PageHeap
    Event(span, '#', 0);
    counter_ -= ((span->length<<kPageShift) /
                 Static::sizemap()->ByteSizeForClass(span->sizeclass));
    tcmalloc::DLL_Remove(span);
    --num_spans_;

    // Release central list lock while operating on pageheap
    lock_.Unlock();
    {
      SpinLockHolder h(Static::pageheap_lock());
      Static::pageheap()->Delete(span);
    }
    lock_.Lock();
  } else {
    //将还回来的object插入到可用object链表表头
    *(reinterpret_cast<void**>(object)) = span->objects;
    span->objects = object;
  }
}

归还策略

我们看到CentralFreeList并没有刻意的去缓存从PageHeap中申请到的页Span，在nonempty的span链表中，只要有一个span内的所有object都还回来了，他就会把这个span还回PageHeap，没有多做缓存，其实呢，也真没必要，因为PageHeap会对这个span做缓存的

总结

CentralFreeList的实现其实也不难，不过一些细节还是值得细扣的，比如object数组链表，RegisterSizeClass，CacheSizeClass，还是挺好玩的

对了，有一个东西上一篇忘讲了，Span是用来管理一批页的，不过Span自身是怎么New出来的呢，其实用的是PageHeapAllocator，它的实现和CentralFreeList还挺像，一次申请一批页，划成等Span大小的object，构造成一个数组链表，每次用的时候分出去一个，还回来的时候插入链表头

好了，下一篇讲ThreadCache，下篇见^^