tcmalloc

template<int kFreeListSizeMod64>
class CentralFreeListPaddedTo : public CentralFreeList {
 private:
  char pad_[64 - kFreeListSizeMod64];
};

template<>
class CentralFreeListPaddedTo<0> : public CentralFreeList {
};

class CentralFreeListPadded : public CentralFreeListPaddedTo<
  sizeof(CentralFreeList) % 64> {
};

class CentralFreeList {
 private:
  // TransferCache is used to cache transfers of
  // sizemap.num_objects_to_move(size_class) back and forth between
  // thread caches and the central cache for a given size class.
  struct TCEntry {
    void *head;  // Head of chain of objects.
    void *tail;  // Tail of chain of objects.
  };
  // A central cache freelist can have anywhere from 0 to kMaxNumTransferEntries
  // slots to put link list chains into.
#ifdef TCMALLOC_SMALL_BUT_SLOW
  // For the small memory model, the transfer cache is not used.
  static const int kMaxNumTransferEntries = 0;
#else
  // Starting point for the the maximum number of entries in the transfer cache.
  // This actual maximum for a given size class may be lower than this
  // maximum value.
  static const int kMaxNumTransferEntries = 64;
#endif
  // This lock protects all the data members.  cached_entries and cache_size_
  // may be looked at without holding the lock.
  SpinLock lock_;

  // We keep linked lists of empty and non-empty spans.
  size_t   size_class_;     // My size class
  Span     empty_;          // Dummy header for list of empty spans
  Span     nonempty_;       // Dummy header for list of non-empty spans
  size_t   num_spans_;      // Number of spans in empty_ plus nonempty_
  size_t   counter_;        // Number of free objects in cache entry

  // Here we reserve space for TCEntry cache slots.  Space is preallocated
  // for the largest possible number of entries than any one size class may
  // accumulate.  Not all size classes are allowed to accumulate
  // kMaxNumTransferEntries, so there is some wasted space for those size
  // classes.
  TCEntry tc_slots_[kMaxNumTransferEntries];

  // Number of currently used cached entries in tc_slots_.  This variable is
  // updated under a lock but can be read without one.
  int32_t used_slots_;  // 当前使用的tc entries.
  // The current number of slots for this size class.  This is an
  // adaptive value that is increased if there is lots of traffic
  // on a given size class.
  int32_t cache_size_; // 当前允许的最大的tc entries.
  // Maximum size of the cache for a given size class.
  int32_t max_cache_size_; // 最大允许多少个tc entries.
}

void CentralFreeList::Init(size_t cl) {
  size_class_ = cl;
  tcmalloc::DLL_Init(&empty_);
  tcmalloc::DLL_Init(&nonempty_);
  num_spans_ = 0;
  counter_ = 0;

  max_cache_size_ = kMaxNumTransferEntries;
#ifdef TCMALLOC_SMALL_BUT_SLOW
  // Disable the transfer cache for the small footprint case.
  cache_size_ = 0;
#else
  cache_size_ = 16;
#endif
  if (cl > 0) {
    int32_t bytes = Static::sizemap()->ByteSizeForClass(cl);
    int32_t objs_to_move = Static::sizemap()->num_objects_to_move(cl);
    max_cache_size_ = (min)(max_cache_size_,
                          (max)(1, (1024 * 1024) / (bytes * objs_to_move)));
    cache_size_ = (min)(cache_size_, max_cache_size_);
  }
  used_slots_ = 0;
  ASSERT(cache_size_ <= max_cache_size_);
}

void CentralFreeList::InsertRange(void *start, void *end, int N) {
  SpinLockHolder h(&lock_);
  if (N == Static::sizemap()->num_objects_to_move(size_class_) &&
    MakeCacheSpace()) { // 这里没有看懂MakeCacheSpace里面一个逻辑，我自己觉得是无关紧要的。
    // 因为看上去像是收缩其他的slab cc(EvictRandomSizeClass).
    // 这里我们可以简单地认为，它就是在计算tc_slots里面是否有slot可以分配.
    int slot = used_slots_++;
    ASSERT(slot >=0);
    ASSERT(slot < max_cache_size_);
    TCEntry *entry = &tc_slots_[slot]; // 如果分配成功的话，那么直接挂载.
    entry->head = start;
    entry->tail = end;
    return;
  }
  ReleaseListToSpans(start); // 如果不允许挂到tc的话，那么就需要单独处理.
}

void CentralFreeList::ReleaseToSpans(void* object) {
  Span* span = MapObjectToSpan(object); // 将object映射到span
  ASSERT(span != NULL);
  ASSERT(span->refcount > 0);

  // If span is empty, move it to non-empty list
  if (span->objects == NULL) { // 如果span上面没有任何free objects的话.
    tcmalloc::DLL_Remove(span); // 那么将span从原来挂载链表删除(empty).
    tcmalloc::DLL_Prepend(&nonempty_, span); // 挂载到这个cc的nonempty链表上.
    Event(span, 'N', 0);
  }

  counter_++; // 当前free objects增加了
  span->refcount--; // 这个span的ref count减少了.
  // span refcount表示里面有多少个objects分配出去了.
  if (span->refcount == 0) { // 如果==0的话，那么说明这个span可以回收了.
    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); // 将span回收pageheap里面去，这个地方可能会进行内存合并
    }
    lock_.Lock();
  } else {
    // 否则就将这个object挂在span链上.
    *(reinterpret_cast<void**>(object)) = span->objects;
    span->objects = object;
  }
}

int CentralFreeList::RemoveRange(void **start, void **end, int N) {
  ASSERT(N > 0);
  lock_.Lock();
  if (N == Static::sizemap()->num_objects_to_move(size_class_) &&
      used_slots_ > 0) { // 如果可以直接从tc里面分配.
    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?
  tail = FetchFromSpansSafe(); // 逻辑是首先放在尾部,然后不断地在头部拼接.
  if (tail != NULL) {
    SLL_SetNext(tail, NULL);
    head = tail;
    result = 1;
    while (result < N) {
      void *t = FetchFromSpans();
      if (!t) break;
      SLL_Push(&head, t);
      result++;
    }
  }
  lock_.Unlock();
  *start = head;
  *end = tail;
  return result;
}

void* CentralFreeList::FetchFromSpansSafe() {
  void *t = FetchFromSpans();
  if (!t) {
    Populate(); // 尝试迁移
    t = FetchFromSpans();
  }
  return t;
}

void* CentralFreeList::FetchFromSpans() {
  if (tcmalloc::DLL_IsEmpty(&nonempty_)) return NULL; // 如果span里面都空了的.
  Span* span = nonempty_.next;

  ASSERT(span->objects != NULL);
  span->refcount++;
  void* result = span->objects; // 否则就会从span里面分配object.
  span->objects = *(reinterpret_cast<void**>(result));
  if (span->objects == NULL) {
    // Move to empty list
    tcmalloc::DLL_Remove(span);
    tcmalloc::DLL_Prepend(&empty_, span);
    Event(span, 'E', 0);
  }
  counter_--;
  return result;
}

void CentralFreeList::Populate() {
  // Release central list lock while operating on pageheap
  lock_.Unlock();  // 首先需要计算出我们需要多少个pages
  const size_t npages = Static::sizemap()->class_to_pages(size_class_);

  Span* span;
  {
    SpinLockHolder h(Static::pageheap_lock());
    span = Static::pageheap()->New(npages); // 分配到pages得到span.
    if (span) Static::pageheap()->RegisterSizeClass(span, size_class_);
  }
  if (span == NULL) {
    MESSAGE("tcmalloc: allocation failed", npages << kPageShift);
    lock_.Lock();
    return;
  }
  ASSERT(span->length == npages);
  for (int i = 0; i < npages; i++) { // 将span和size_class之间关联起来
    // 应该是为了后面查找方便，但是现在还不知道有什么用途。但是不影响阅读.
    Static::pageheap()->CacheSizeClass(span->start + i, size_class_);
  }

  // 对这个span里面的所有objects组织成链表形式
  // Split the block into pieces and add to the free-list
  // TODO: coloring of objects to avoid cache conflicts?
  void** tail = &span->objects;
  char* ptr = reinterpret_cast<char*>(span->start << kPageShift);
  char* limit = ptr + (npages << kPageShift);
  const size_t size = Static::sizemap()->ByteSizeForClass(size_class_);
  int num = 0;
  while (ptr + size <= limit) {
    *tail = ptr;
    tail = reinterpret_cast<void**>(ptr);
    ptr += size;
    num++;
  }
  ASSERT(ptr <= limit);
  *tail = NULL;
  span->refcount = 0; // No sub-object in use yet

  // 将这个span加入nonempty链表的话需要加锁。
  // Add span to list of non-empty spans
  lock_.Lock();
  tcmalloc::DLL_Prepend(&nonempty_, span);
  ++num_spans_;
  counter_ += num;
}

// We segregate spans of a given size into two circular linked
// lists: one for normal spans, and one for spans whose memory
// has been returned to the system.
struct SpanList {
  Span        normal;
  Span        returned; // 其实对于这个部分没有必要区分的，因为代码里面大部分都是挂在normal这个链上的。
};

// List of free spans of length >= kMaxPages
SpanList large_; // 对于>=kMaxPages的页面单独维护一个free list.

// Array mapping from span length to a doubly linked list of free spans
SpanList free_[kMaxPages]; // 针对每个页面大小做的free list.

// Selector class -- general selector uses 3-level map
template <int BITS> class MapSelector {
 public:
  typedef TCMalloc_PageMap3<BITS-kPageShift> Type;
  typedef PackedCache<BITS-kPageShift, uint64_t> CacheType;
};

  // Pick the appropriate map and cache types based on pointer size
  typedef MapSelector<kAddressBits>::Type PageMap;
  typedef MapSelector<kAddressBits>::CacheType PageMapCache;
  PageMap pagemap_;
  mutable PageMapCache pagemap_cache_;

#if defined __x86_64__
// All current and planned x86_64 processors only look at the lower 48 bits
// in virtual to physical address translation.  The top 16 are thus unused.
// TODO(rus): Under what operating systems can we increase it safely to 17?
// This lets us use smaller page maps.  On first allocation, a 36-bit page map
// uses only 96 KB instead of the 4.5 MB used by a 52-bit page map.
static const int kAddressBits = (sizeof(void*) < 8 ? (8 * sizeof(void*)) : 48); // __x86_64__就是64位
#else
static const int kAddressBits = 8 * sizeof(void*);
#endif

Span* PageHeap::New(Length n) {
  ASSERT(Check());
  ASSERT(n > 0);

  Span* result = SearchFreeAndLargeLists(n);  // free list然后在large里面查找
  if (result != NULL)
    return result;

  // Grow the heap and try again.
  if (!GrowHeap(n)) { // 不行的话尝试分配更多内存
    ASSERT(Check());
    return NULL;
  }
  return SearchFreeAndLargeLists(n); // 然后重新尝试分配
}

Span* PageHeap::SearchFreeAndLargeLists(Length n) {
  ASSERT(Check());
  ASSERT(n > 0);

  // Find first size >= n that has a non-empty list
  for (Length s = n; s < kMaxPages; s++) { // 遍历所有的Pages看看是否有合适的。
    Span* ll = &free_[s].normal;
    // If we're lucky, ll is non-empty, meaning it has a suitable span.
    if (!DLL_IsEmpty(ll)) {
      ASSERT(ll->next->location == Span::ON_NORMAL_FREELIST);
      return Carve(ll->next, n); // 如果有合适的话，那么可能需要切割一下,从里面切割出n pages出来
    }
    // Alternatively, maybe there's a usable returned span.
    ll = &free_[s].returned;
    if (!DLL_IsEmpty(ll)) {
      ASSERT(ll->next->location == Span::ON_RETURNED_FREELIST);
      return Carve(ll->next, n);
    }
  }
  // No luck in free lists, our last chance is in a larger class.
  return AllocLarge(n);  // May be NULL // 如果没有分配成功的话那么从AllocLarge里面分配
}

Span* PageHeap::Carve(Span* span, Length n) {
  ASSERT(n > 0);
  ASSERT(span->location != Span::IN_USE);
  const int old_location = span->location;
  RemoveFromFreeList(span); // 从freelist里面删除，同时记录信息也会更改。
  span->location = Span::IN_USE; // 修改一下location.
  Event(span, 'A', n);

  const int extra = span->length - n;
  ASSERT(extra >= 0);
  if (extra > 0) {
    Span* leftover = NewSpan(span->start + n, extra); // 创建一个新的span对象
    leftover->location = old_location; // 这个新的对象里面存放到是原来location.
    Event(leftover, 'S', extra);
    RecordSpan(leftover); // 将剩余的span记录下来并且插入到free list里面.
    PrependToFreeList(leftover);  // Skip coalescing - no candidates possible
    span->length = n;
    pagemap_.set(span->start + n - 1, span); // 同时标记span管理的范围.
  }
  ASSERT(Check());
  return span;
}

void RecordSpan(Span* span) {
  pagemap_.set(span->start, span); // 这时span开始
  if (span->length > 1) {
    pagemap_.set(span->start + span->length - 1, span); // 设置span结束
  }
}

// 这个就是相当于允许分配的最大Pages
static const Length kMaxValidPages = (~static_cast<Length>(0)) >> kPageShift;
static const int kMinSystemAlloc = kMaxPages; // 调用GrowHeap最小的页数

bool PageHeap::GrowHeap(Length n) {
  ASSERT(kMaxPages >= kMinSystemAlloc);
  if (n > kMaxValidPages) return false;
  Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc); // 会判断是否超过，如果没有超过的话，
  // 那么按照kMinSystemAlloc分配
  size_t actual_size;
  void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
  if (ptr == NULL) {
    if (n < ask) {
      // Try growing just "n" pages
      ask = n;
      ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); // 如果ask分配不了，那么尝试分配n
    }
    if (ptr == NULL) return false;
  }
  ask = actual_size >> kPageShift;
  RecordGrowth(ask << kPageShift);

  uint64_t old_system_bytes = stats_.system_bytes;
  stats_.system_bytes += (ask << kPageShift);
  const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
  ASSERT(p > 0);

  // If we have already a lot of pages allocated, just pre allocate a bunch of
  // memory for the page map. This prevents fragmentation by pagemap metadata
  // when a program keeps allocating and freeing large blocks.

  //  static const size_t kPageMapBigAllocationThreshold = 128 << 20;(128MB)
  // 这个地方判断，这次分配是不是已经越过了一个threshold
  // 如果越过的话，那么意味着pagemap里面可能需要分配更多的内存
  // 但是对于64位来说的话，里面没有任何逻辑.
  if (old_system_bytes < kPageMapBigAllocationThreshold
      && stats_.system_bytes >= kPageMapBigAllocationThreshold) {
    pagemap_.PreallocateMoreMemory();
  }

  // Make sure pagemap_ has entries for all of the new pages.
  // Plus ensure one before and one after so coalescing code
  // does not need bounds-checking.
  if (pagemap_.Ensure(p-1, ask+2)) {   // 因为需要插入新的span,所以必须确保这个pagemap确实存在.
    // Pretend the new area is allocated and then Delete() it to cause
    // any necessary coalescing to occur.
    Span* span = NewSpan(p, ask);
    RecordSpan(span);
    Delete(span); // 将这个Span返回给large_里等待下次分配
    ASSERT(Check());
    return true;
  } else {
    // We could not allocate memory within "pagemap_"
    // TODO: Once we can return memory to the system, return the new span
    return false;
  }
}

void PageHeap::Delete(Span* span) {
  ASSERT(Check());
  ASSERT(span->location == Span::IN_USE);
  ASSERT(span->length > 0);
  ASSERT(GetDescriptor(span->start) == span);
  ASSERT(GetDescriptor(span->start + span->length - 1) == span);
  const Length n = span->length;
  span->sizeclass = 0;
  span->sample = 0;
  span->location = Span::ON_NORMAL_FREELIST;
  Event(span, 'D', span->length);
  MergeIntoFreeList(span);  // Coalesces if possible // 会尝试进行合并
  IncrementalScavenge(n); // 增量收集. 后面会仔细看这个函数的定义
  ASSERT(Check());
}

void PageHeap::MergeIntoFreeList(Span* span) {
  ASSERT(span->location != Span::IN_USE);
  const PageID p = span->start;
  const Length n = span->length;
  // 首先尝试合并p-1 pages这个span
  Span* prev = GetDescriptor(p-1);
  if (prev != NULL && prev->location == span->location) {
    // Merge preceding span into this span
    ASSERT(prev->start + prev->length == p);
    const Length len = prev->length;
    RemoveFromFreeList(prev);
    DeleteSpan(prev);
    span->start -= len;
    span->length += len;
    pagemap_.set(span->start, span);
    Event(span, 'L', len);
  }
 // 然后尝试合并p+n pages这个span.
  Span* next = GetDescriptor(p+n);
  if (next != NULL && next->location == span->location) {
    // Merge next span into this span
    ASSERT(next->start == p+n);
    const Length len = next->length;
    RemoveFromFreeList(next);
    DeleteSpan(next);
    span->length += len;
    pagemap_.set(span->start + span->length - 1, span);
    Event(span, 'R', len);
  }
  // 合并完成之后就会放入free list里面去
  PrependToFreeList(span);
}

void PageHeap::IncrementalScavenge(Length n) {
  // Fast path; not yet time to release memory
  scavenge_counter_ -= n;
  if (scavenge_counter_ >= 0) return;  // Not yet time to scavenge

  // 默认值的话是1.0,这个可以有环境变量设置.
  // 如果回收率很低的哈，那么相当于不会归还给系统内存
  const double rate = FLAGS_tcmalloc_release_rate;
  if (rate <= 1e-6) {
    // Tiny release rate means that releasing is disabled.
    //   static const int kDefaultReleaseDelay = 1 << 18;
    scavenge_counter_ = kDefaultReleaseDelay;
    return;
  }

  // 尝试至归还一个页面.
  // 具体这个函数实现在后面会提到.
  Length released_pages = ReleaseAtLeastNPages(1);

  // 如果实际上没有归还的话，那么下次需要等待这么多次之后尝试归还.
  if (released_pages == 0) {
    // Nothing to scavenge, delay for a while.
    scavenge_counter_ = kDefaultReleaseDelay;
  } else { // 否则会按照一定的策略设定次数然后尝试归还
    // Compute how long to wait until we return memory.
    // FLAGS_tcmalloc_release_rate==1 means wait for 1000 pages
    // after releasing one page.
    const double mult = 1000.0 / rate;
    double wait = mult * static_cast<double>(released_pages);
    if (wait > kMaxReleaseDelay) {
      // Avoid overflow and bound to reasonable range.
       // static const int kMaxReleaseDelay = 1 << 20;
      wait = kMaxReleaseDelay;
    }
    scavenge_counter_ = static_cast<int64_t>(wait);
  }
}

Length PageHeap::ReleaseAtLeastNPages(Length num_pages) {
  Length released_pages = 0;
  Length prev_released_pages = -1;

  // Round robin through the lists of free spans, releasing the last
  // span in each list.  Stop after releasing at least num_pages.
  while (released_pages < num_pages) {
    if (released_pages == prev_released_pages) { // 如果自上次依赖没有多余释放的话
      // Last iteration of while loop made no progress.
      break;
    }
    prev_released_pages = released_pages;

    for (int i = 0; i < kMaxPages+1 && released_pages < num_pages;
         i++, release_index_++) { // 每个大小类型都会尝试释放一个.
      if (release_index_ > kMaxPages) release_index_ = 0;
      SpanList* slist = (release_index_ == kMaxPages) ?
          &large_ : &free_[release_index_];
      if (!DLL_IsEmpty(&slist->normal)) {
        Length released_len = ReleaseLastNormalSpan(slist);
        released_pages += released_len;
      }
    }
  }
  return released_pages;
}

Length PageHeap::ReleaseLastNormalSpan(SpanList* slist) {
  Span* s = slist->normal.prev;
  ASSERT(s->location == Span::ON_NORMAL_FREELIST);
  RemoveFromFreeList(s); // 从当前链中释放掉.
  const Length n = s->length;
  // 实际上这个部分并没有释放哦.
  TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
                         static_cast<size_t>(s->length << kPageShift));
  s->location = Span::ON_RETURNED_FREELIST; // 标记为returned状态
   // 丢回return free list时候会尝试合并.
  MergeIntoFreeList(s);  // Coalesces if possible.
  return n;
}

struct MallocRange {
  // 这个malloc范围是什么类型
  enum Type {
    INUSE,                // Application is using this range
    FREE,                 // Range is currently free
    UNMAPPED,             // Backing physical memory has been returned to the OS
    UNKNOWN,
    // More enum values may be added in the future
  };
  // 地址，长度，类型
  uintptr_t address;    // Address of range
  size_t length;        // Byte length of range
  Type type;            // Type of this range
  // =0 !INUSE,如果=1表示这个被当做page使用
  // 如果[0,1]之间的话，表明被做成了小对象分配
  double fraction;      // Fraction of range that is being used (0 if !INUSE)
};

bool PageHeap::GetNextRange(PageID start, base::MallocRange* r) {
  Span* span = reinterpret_cast<Span*>(pagemap_.Next(start));
  if (span == NULL) {
    return false;
  }
  r->address = span->start << kPageShift;
  r->length = span->length << kPageShift;
  r->fraction = 0;
  switch (span->location) {
    case Span::IN_USE:
      r->type = base::MallocRange::INUSE;
      r->fraction = 1;
      if (span->sizeclass > 0) {
        // Only some of the objects in this span may be in use.
        const size_t osize = Static::sizemap()->class_to_size(span->sizeclass); // 首先知道这个class每个object size多少
       // refcount表示已经使用了多少个objects.,这样就可以得到使用率
        r->fraction = (1.0 * osize * span->refcount) / r->length;
      }
      break;
    case Span::ON_NORMAL_FREELIST:
      r->type = base::MallocRange::FREE;
      break;
    case Span::ON_RETURNED_FREELIST:
      r->type = base::MallocRange::UNMAPPED;
      break;
    default:
      r->type = base::MallocRange::UNKNOWN;
      break;
  }
  return true;
}

namespace tcmalloc {

static bool phinited = false;

volatile size_t ThreadCache::per_thread_cache_size_ = kMaxThreadCacheSize; // 每个tc的大小 (4 << 20,4MB)
size_t ThreadCache::overall_thread_cache_size_ = kDefaultOverallThreadCacheSize;// 所有tc大小 (8 * kMaxThreadCacheSize = 32MB)
ssize_t ThreadCache::unclaimed_cache_space_ = kDefaultOverallThreadCacheSize;  // 管理对象所持有的tc大小(相当于总tc里面还有多少可用).
// (= overall_thread_cache_size_ - sum(tc.max_size))
PageHeapAllocator<ThreadCache> threadcache_allocator; // tc sample alloc.
ThreadCache* ThreadCache::thread_heaps_ = NULL; // tc链.
int ThreadCache::thread_heap_count_ = 0; // 多少个tc
ThreadCache* ThreadCache::next_memory_steal_ = NULL; // 下一次steal的tc.
bool ThreadCache::tsd_inited_ = false; // 是否已经初始化了线程局部数据
pthread_key_t ThreadCache::heap_key_; // 如果使用pthread线程局部数据解决办法

}

void ThreadCache::InitModule() {
  SpinLockHolder h(Static::pageheap_lock());  // 全局自选锁
  if (!phinited) {
    Static::InitStaticVars(); // 初始化一些静态数据
    threadcache_allocator.Init(); // PageHeapAllocator<ThreadCache>,sample_alloc初始化
    phinited = 1;
  }
}

void ThreadCache::InitTSD() {
  ASSERT(!tsd_inited_); // 这个变量标记是否已经初始化了线程局部变量，如果没有的话那么是没有任何tc的.
  perftools_pthread_key_create(&heap_key_, DestroyThreadCache); // 这个就是设置好线程局部变量
  // 因为每一个线程都会有一个线程局部变量thread cache.
  tsd_inited_ = true;
}

void ThreadCache::DestroyThreadCache(void* ptr) {
  // Note that "ptr" cannot be NULL since pthread promises not
  // to invoke the destructor on NULL values, but for safety,
  // we check anyway.
  if (ptr == NULL) return;
  DeleteCache(reinterpret_cast<ThreadCache*>(ptr));
}

inline ThreadCache* ThreadCache::GetCache() {
  ThreadCache* ptr = NULL;
  if (!tsd_inited_) {
    InitModule(); // 初始化模块
  } else {
    ptr = GetThreadHeap(); // 直接查看是否存在
  }
  if (ptr == NULL) ptr = CreateCacheIfNecessary(); // 如果不存在的话那么就创建
  return ptr;
}

inline ThreadCache* ThreadCache::GetThreadHeap() {
  return reinterpret_cast<ThreadCache *>(
      perftools_pthread_getspecific(heap_key_));
}
inline ThreadCache* ThreadCache::GetCacheIfPresent() {
  if (!tsd_inited_) return NULL;
  return GetThreadHeap();
}

ThreadCache* ThreadCache::CreateCacheIfNecessary() {
  // Initialize per-thread data if necessary
  ThreadCache* heap = NULL;
  {
    SpinLockHolder h(Static::pageheap_lock());
    const pthread_t me = pthread_self();
    // 查找里面是否已经存在,每个线程都创建一个ThreadCache.
    // 并且这个是按照链组织起来的。
    for (ThreadCache* h = thread_heaps_; h != NULL; h = h->next_) {
      if (h->tid_ == me) {
        heap = h;
        break;
      }
    }
    if (heap == NULL) heap = NewHeap(me);
  }
  if (!heap->in_setspecific_ && tsd_inited_) {
    heap->in_setspecific_ = true; // 避免setspecific里面还调用
    perftools_pthread_setspecific(heap_key_, heap);
    heap->in_setspecific_ = false;
  }
  return heap;
}

ThreadCache* ThreadCache::NewHeap(pthread_t tid) {
  // Create the heap and add it to the linked list
  ThreadCache *heap = threadcache_allocator.New();
  heap->Init(tid); // 调用Init
  heap->next_ = thread_heaps_; // 组织成为一个双向链表
  heap->prev_ = NULL;
  if (thread_heaps_ != NULL) {
    thread_heaps_->prev_ = heap;
  } else {
    // This is the only thread heap at the momment.
    ASSERT(next_memory_steal_ == NULL);
    next_memory_steal_ = heap; // 如果这个是第一个元素的话，那么设置next_memory_steal.
  }
  thread_heaps_ = heap;
  thread_heap_count_++; // tc数量.
  return heap;
}

void ThreadCache::BecomeIdle() {
  if (!tsd_inited_) return;              // No caches yet
  ThreadCache* heap = GetThreadHeap();
  if (heap == NULL) return;             // No thread cache to remove
  if (heap->in_setspecific_) return;    // Do not disturb the active caller

  heap->in_setspecific_ = true; // 防止递归调用
  perftools_pthread_setspecific(heap_key_, NULL);
  heap->in_setspecific_ = false;
  if (GetThreadHeap() == heap) { // 应该是不会调用这个部分逻辑的.
    // Somehow heap got reinstated by a recursive call to malloc
    // from pthread_setspecific.  We give up in this case.
    return;
  }
  // 然后将这个heap释放掉
  // We can now get rid of the heap
  DeleteCache(heap);
}

#include <cstdio>
#include <pthread.h>

char buf[1024*1024];
void* foo(void* arg){
  return NULL;
}
int main() {
  pthread_t tid;
  for(int i=0;i<10;i++){
    pthread_create(&tid,NULL,foo,NULL);
    pthread_join(tid,NULL);
    printf("%zu\n",static_cast<size_t>(tid));
    pthread_create(&tid,NULL,foo,NULL);
    pthread_join(tid,NULL);
    printf("%zu\n",static_cast<size_t>(tid));
  }
  return 0;
}

void ThreadCache::Init(pthread_t tid) {
  size_ = 0;

  max_size_ = 0;
  IncreaseCacheLimitLocked(); // 这个地方在计算到底可以分配多少max size.
  if (max_size_ == 0) {
    // There isn't enough memory to go around.  Just give the minimum to
    // this thread.
    // static const size_t kMaxSize    = 256 * 1024;(256K)
    // static const size_t kMinThreadCacheSize = kMaxSize * 2;(512K)
    max_size_ = kMinThreadCacheSize; // 512K.

    // Take unclaimed_cache_space_ negative.
    unclaimed_cache_space_ -= kMinThreadCacheSize; // 那么相当于tc持有空闲空间也对应减少
    ASSERT(unclaimed_cache_space_ < 0);
  }

  next_ = NULL;
  prev_ = NULL;
  tid_  = tid;
  in_setspecific_ = false;
  for (size_t cl = 0; cl < kNumClasses; ++cl) {
    list_[cl].Init(); // 初始化每个slab
  }

  uint32_t sampler_seed;
  memcpy(&sampler_seed, &tid, sizeof(sampler_seed));
  sampler_.Init(sampler_seed); // 初始化sampler
}

class FreeList {
 private:
  void*    list_;       // Linked list of nodes

  // On 64-bit hardware, manipulating 16-bit values may be slightly slow.
  uint32_t length_;      // Current length. // 当前长度多少
  uint32_t lowater_;     // Low water mark for list length. // 长度最少时候达到了多少
  uint32_t max_length_;  // Dynamic max list length based on usage. // 认为的最大长度多少
  // Tracks the number of times a deallocation has caused
  // length_ > max_length_.  After the kMaxOverages'th time, max_length_
  // shrinks and length_overages_ is reset to zero.
  uint32_t length_overages_; // 超过最大长度的次数
};

void ThreadCache::IncreaseCacheLimitLocked() {
  if (unclaimed_cache_space_ > 0) { // 如果tc里面还有空闲的内容的话，那么获取64KB过来
    // static const size_t kStealAmount = 1 << 16;(64KB)
    // Possibly make unclaimed_cache_space_ negative.
    unclaimed_cache_space_ -= kStealAmount;
    max_size_ += kStealAmount;
    return;
  }
  // 如果发现依然不够的话，那么会从每一个以后的tc里面获取偷取部分出来.
  // 这个链是按照next_memory_steal_取出来的，如果==NULL那么从头开始。
  // 但是很快会发现这个max_size其实并不是一成不变的.
  // Don't hold pageheap_lock too long.  Try to steal from 10 other
  // threads before giving up.  The i < 10 condition also prevents an
  // infinite loop in case none of the existing thread heaps are
  // suitable places to steal from.
  for (int i = 0; i < 10;
       ++i, next_memory_steal_ = next_memory_steal_->next_) {
    // Reached the end of the linked list.  Start at the beginning.
    if (next_memory_steal_ == NULL) {
      ASSERT(thread_heaps_ != NULL);
      next_memory_steal_ = thread_heaps_;
    }
    if (next_memory_steal_ == this ||
        next_memory_steal_->max_size_ <= kMinThreadCacheSize) {
      continue;
    }
    next_memory_steal_->max_size_ -= kStealAmount;
    max_size_ += kStealAmount;

    next_memory_steal_ = next_memory_steal_->next_;
    return;
  }
}

void ThreadCache::DeleteCache(ThreadCache* heap) {
  // Remove all memory from heap
  heap->Cleanup(); // 稍后我们查看Cleanup实现。

  // Remove from linked list
  SpinLockHolder h(Static::pageheap_lock());
  if (heap->next_ != NULL) heap->next_->prev_ = heap->prev_;
  if (heap->prev_ != NULL) heap->prev_->next_ = heap->next_;
  if (thread_heaps_ == heap) thread_heaps_ = heap->next_;
  thread_heap_count_--;

  if (next_memory_steal_ == heap) next_memory_steal_ = heap->next_;
  if (next_memory_steal_ == NULL) next_memory_steal_ = thread_heaps_;
  unclaimed_cache_space_ += heap->max_size_;

  threadcache_allocator.Delete(heap);
}

void ThreadCache::Cleanup() {
  // Put unused memory back into central cache
  for (int cl = 0; cl < kNumClasses; ++cl) {
    if (list_[cl].length() > 0) {
      ReleaseToCentralCache(&list_[cl], cl, list_[cl].length());
    }
  }
}

void ThreadCache::ReleaseToCentralCache(FreeList* src, size_t cl, int N) {
  ASSERT(src == &list_[cl]);
  if (N > src->length()) N = src->length(); // 这个地方感觉不是很有必要.不过其他地方的话可能这两个参数不同
  size_t delta_bytes = N * Static::sizemap()->ByteSizeForClass(cl); // 了解有多少个对象占用内存大小释放.

  // We return prepackaged chains of the correct size to the central cache.
  // TODO: Use the same format internally in the thread caches?
  int batch_size = Static::sizemap()->num_objects_to_move(cl);
  while (N > batch_size) { // 每次归还batch_size个内容，这样central cache可以放在transfer cache里面
    void *tail, *head;
    src->PopRange(batch_size, &head, &tail);
    Static::central_cache()[cl].InsertRange(head, tail, batch_size);
    N -= batch_size;
  }
  void *tail, *head;
  src->PopRange(N, &head, &tail);
  Static::central_cache()[cl].InsertRange(head, tail, N);
  size_ -= delta_bytes;
}

void PopRange(int N, void **start, void **end) {
  SLL_PopRange(&list_, N, start, end);
  ASSERT(length_ >= N);
  length_ -= N;
  if (length_ < lowater_) lowater_ = length_;
}

inline void* ThreadCache::Allocate(size_t size, size_t cl) {
  ASSERT(size <= kMaxSize);
  ASSERT(size == Static::sizemap()->ByteSizeForClass(cl));

  FreeList* list = &list_[cl];
  if (list->empty()) {
    return FetchFromCentralCache(cl, size); // 如果list里面为空的话，那么尝试从cc的cl里面分配size出来.
  }
  size_ -= size; // 如果存在的话那么就直接-size并且弹出一个元素
  return list->Pop();
}

void* ThreadCache::FetchFromCentralCache(size_t cl, size_t byte_size) {
  FreeList* list = &list_[cl];
  ASSERT(list->empty());
  const int batch_size = Static::sizemap()->num_objects_to_move(cl);

  // 看看每次允许的分配的个数是多少
  const int num_to_move = min<int>(list->max_length(), batch_size);
  void *start, *end;
  int fetch_count = Static::central_cache()[cl].RemoveRange(
      &start, &end, num_to_move);

  ASSERT((start == NULL) == (fetch_count == 0));
  // 取出来并且设置一下当前维护的空闲大小是多少
  if (--fetch_count >= 0) {
    size_ += byte_size * fetch_count;
    list->PushRange(fetch_count, SLL_Next(start), end);
  }
  // 这里需要增长max_length.如果<batch_size的话那么+1
  // 如果>=batch_size的话，那么会设置成为某个上线
  // static const int kMaxDynamicFreeListLength = 8192;
  if (list->max_length() < batch_size) {
    list->set_max_length(list->max_length() + 1);
  } else {
    int new_length = min<int>(list->max_length() + batch_size,
                              kMaxDynamicFreeListLength);
    // 这里也非常好理解，按照batch_size来分配的话，可以直接从tc里面得到
    // 使用这个作为max_kength的话通常意味着分配速度会更快.
    new_length -= new_length % batch_size;
    ASSERT(new_length % batch_size == 0);
    list->set_max_length(new_length);
  }
  return start;
}

inline void ThreadCache::Deallocate(void* ptr, size_t cl) {
  FreeList* list = &list_[cl];
  size_ += Static::sizemap()->ByteSizeForClass(cl); // 释放了这个内存所以空闲大小增大
  ssize_t size_headroom = max_size_ - size_ - 1;  // 在size上面的话还有多少空闲.

  list->Push(ptr); // 归还
  ssize_t list_headroom =
      static_cast<ssize_t>(list->max_length()) - list->length(); // 在长度上还有多少空闲

  // There are two relatively uncommon things that require further work.
  // In the common case we're done, and in that case we need a single branch
  // because of the bitwise-or trick that follows.
  if ((list_headroom | size_headroom) < 0) { // 这个部分应该是有任意一个<0的话，那么就应该进入。优化手段吧.
    if (list_headroom < 0) { // 如果当前长度>max_length的话，那么需要重新设置max_length.
      ListTooLong(list, cl);
    }
    // 条件相当 if(size_headroom < 0)
    // 因为ListTooLog会尝试修改size_所以这里重新判断..:(tricky:(.
    if (size_ >= max_size_) Scavenge(); // 如果当前size>max_size的话，那么需要进行GC.
  }
}

void ThreadCache::ListTooLong(FreeList* list, size_t cl) {
  const int batch_size = Static::sizemap()->num_objects_to_move(cl);
  ReleaseToCentralCache(list, cl, batch_size); // 首先尝试将batch_size的内容归还到tc里面取

  // If the list is too long, we need to transfer some number of
  // objects to the central cache.  Ideally, we would transfer
  // num_objects_to_move, so the code below tries to make max_length
  // converge on num_objects_to_move.

  if (list->max_length() < batch_size) {
    // Slow start the max_length so we don't overreserve.
    list->set_max_length(list->max_length() + 1);
  } else if (list->max_length() > batch_size) {
    // If we consistently go over max_length, shrink max_length.  If we don't
    // shrink it, some amount of memory will always stay in this freelist.
    list->set_length_overages(list->length_overages() + 1); // 记录下overage的次数
    if (list->length_overages() > kMaxOverages) { // > kMaxOverages的话那么需要对max_length进行缩减.
      ASSERT(list->max_length() > batch_size);
      list->set_max_length(list->max_length() - batch_size); // 缩减batch_size.
      list->set_length_overages(0);
    }
  }
}

// Release idle memory to the central cache
void ThreadCache::Scavenge() {
  // If the low-water mark for the free list is L, it means we would
  // not have had to allocate anything from the central cache even if
  // we had reduced the free list size by L.  We aim to get closer to
  // that situation by dropping L/2 nodes from the free list.  This
  // may not release much memory, but if so we will call scavenge again
  // pretty soon and the low-water marks will be high on that call.
  //int64 start = CycleClock::Now();
  for (int cl = 0; cl < kNumClasses; cl++) {
    FreeList* list = &list_[cl];
    const int lowmark = list->lowwatermark(); // 上一次最短的free list length是多少.如果free list length越长
    // 意味着在大多数时候有很多空闲内存是没有使用，所以可以将其归还.
    if (lowmark > 0) {
      const int drop = (lowmark > 1) ? lowmark/2 : 1; // 将最最短的部分的1/2归还给cc.
      ReleaseToCentralCache(list, cl, drop);

      // Shrink the max length if it isn't used.  Only shrink down to
      // batch_size -- if the thread was active enough to get the max_length
      // above batch_size, it will likely be that active again.  If
      // max_length shinks below batch_size, the thread will have to
      // go through the slow-start behavior again.  The slow-start is useful
      // mainly for threads that stay relatively idle for their entire
      // lifetime.
      const int batch_size = Static::sizemap()->num_objects_to_move(cl);
      if (list->max_length() > batch_size) { // 调整max_length.
        list->set_max_length(
            max<int>(list->max_length() - batch_size, batch_size));
      }
    }
    list->clear_lowwatermark();
  }

  IncreaseCacheLimit(); // 触发这个Scavenge本身的原因就是因为size_>max_size_所以有必要提高max_size_.
}