tc_malloc过程涉及到这些关键的数据结构

以上主要是tc_malloc过程，在这里涉及到这些关键的数据结构：

（版权所有 ）

1、CentralFreeListPadded Static::central_cache_[kNumClasses]

central_cache_其实是一个CentralFreeList通过pad的方式保证64bytes对齐，总共有kNumClasses（61）个CentralFreeList。CentralFreeList的主要数据结构包括

  size_t   size_class_;     // My size class是本class的size_num

  Span     empty_;          // Dummy header for list of empty spans此Span列表表示在此列表中的Span已经被用完了，空了

  Span     nonempty_;       // Dummy header for list of non-empty spans表示在此列表中的Span还有可用的object

  size_t   counter_;        // Number of free objects in cache entry

 

  // Here we reserve space for TCEntry cache slots.  Since one size class can

  // end up getting all the TCEntries quota in the system we just preallocate

  // sufficient number of entries here.

  TCEntry tc_slots_[kNumTransferEntries];//么个slots包含了num_objects_to_move个可用obj。

 

  // 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_;//表示slots非空的slots

  // 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_;

2、Span这个struct主要包含了本Span的起始page num以及本Span的长度之类的信息，Span通过指针next和prev将同一列表的span连在一起。Span里面比较重要的数据结构是void* objects，他指向本Span的第一个free obj。其他比较重要的数据结构包含一个location，location定义为enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST };中的一个。

struct Span {

  PageID        start;          // Starting page number

  Length        length;         // Number of pages in span

  Span*         next;           // Used when in link list

  Span*         prev;           // Used when in link list

  void*         objects;        // Linked list of free objects

  unsigned int  refcount : 16;  // Number of non-free objects

  unsigned int  sizeclass : 8;  // Size-class for small objects (or 0)

  unsigned int  location : 2;   // Is the span on a freelist, and if so, which?

  unsigned int  sample : 1;     // Sampled object?

 

#undef SPAN_HISTORY

#ifdef SPAN_HISTORY

  // For debugging, we can keep a log events per span

  int nexthistory;

  char history[64];

  int value[64];

#endif

 

  // What freelist the span is on: IN_USE if on none, or normal or returned

  enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST };

};

3、PageHeap主要用来handle系统中page level的allocation主要是针对span的allocate和free。主要包含的数据结构如下所示：

  // Allocates a big block of memory for the pagemap once we reach more than

  // 128MB

  static const size_t kPageMapBigAllocationThreshold = 128 << 20;

 

  // Minimum number of pages to fetch from system at a time.  Must be

  // significantly bigger than kBlockSize to amortize system-call

  // overhead, and also to reduce external fragementation.  Also, we

  // should keep this value big because various incarnations of Linux

  // have small limits on the number of mmap() regions per

  // address-space.

  static const int kMinSystemAlloc = 1 << (20 - kPageShift);

 

  // For all span-lengths < kMaxPages we keep an exact-size list.

  // REQUIRED: kMaxPages >= kMinSystemAlloc;

  static const size_t kMaxPages = kMinSystemAlloc;

 

  // Never delay scavenging for more than the following number of

  // deallocated pages.  With 4K pages, this comes to 4GB of

  // deallocation.

  static const int kMaxReleaseDelay = 1 << 20;

 

  // If there is nothing to release, wait for so many pages before

  // scavenging again.  With 4K pages, this comes to 1GB of memory.

  static const int kDefaultReleaseDelay = 1 << 18;

//这两个map比较重要，pagemap_是一颗三层的radix tree，用来存放每个span的信息。而pagemap_cache_是个二元组，用来存放ptr和size的关系。

  // Pick the appropriate map and cache types based on pointer size

  typedef MapSelector<8*sizeof(uintptr_t)>::Type PageMap;

  typedef MapSelector<8*sizeof(uintptr_t)>::CacheType PageMapCache;

  PageMap pagemap_;

  mutable PageMapCache pagemap_cache_;

 

  // 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;

  };

  // List of free spans of length >= kMaxPages

  SpanList large_;// 用来存放length>= kMaxPages的大的obj。

 

  // Array mapping from span length to a doubly linked list of free spans

  SpanList free_[kMaxPages]; //按照span的length存放span

 

  // Statistics on system, free, and unmapped bytes

  Stats stats_;

 

  // Number of pages to deallocate before doing more scavenging

  int64_t scavenge_counter_;

 

  // Index of last free list where we released memory to the OS.

  int release_index_;

}

4、ThreadCache负责每个thread的内存管理，里面最重要的数据结构是list_[kNumClasses]。每个list_存放了相同classNum的obj。其他相关的数据，会在遇到的时候在解释。