上一篇介绍了 TCMallocSysAllocator,处于最底层,该层负责直接和内核交互,申请和释放内存。紧邻 SysAllocator 的上一层,是 PageHeap,负责管理内存页面。
  TCMalloc 中的页面和 Linux 内核中的页面相似,事实上,组织方式也和内核接近。介绍 PageHeap 之前,先要介绍 Span,一个 Span 是一个或多个 Page,也是 PageHeap 管理的单元:

1
2
3
4
5
6
7
8
9
10
11
12
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?
  // What freelist the span is on: IN_USE if on none, or normal or returned
  enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST };
};

  start 是该 Span 的第一个页面的 pageidlength 是页面个数。objects 是该 Span 分割后的空闲 object 的链表头。refcount 是已经分配的 object 数。sizeclass 是该 Span 所属的 slab,关于 sizeclass,以后介绍 CentralFreeList 时候会详细介绍。location 标识该 Span 的状态/位置,有三种取值:IN_USE 表示正在使用;ON_NORMAL_FREELIST 表示用户已经归还;ON_RETURNED_FREELISTON_NORMAL_FREELIST 相似,但是该 Span 已经调用过 TCMalloc_SystemRelease,对应的物理内存已经释放。
  PageHeap 中对页面的管理,类似于内核中的页式管理,即多层次的页表管理方式。将虚拟地址划分为不同的区段,每一级都指向下级目录。不同的是,内核中的页表的最终目的是实现线性地址到物理地址的映射,末层页表的表项指向的是物理页帧。而 PageHeap 中的『页表』是为了定位某个地址(由地址可直接得到 pageid)或者页面所属的 Span,其末级表项指向的就是所属 Span 的地址。
  针对不同的地址宽度,TCMalloc 采用不同的层级。32 位中,使用二级映射,64 位中使用三级映射。此外,还定义了一级映射,用作缓存,完成地址到 sizeclass 的快速映射,类似于 CPUTLB。不同级数的映射由不同的类完成:TCMalloc_PageMap1TCMalloc_PageMap2TCMalloc_PageMap3,用 MapSelector 在编译期选择使用那种 PageMap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// page_heap.h
template <int BITS> class MapSelector {
 public:
  typedef TCMalloc_PageMap3<BITS-kPageShift> Type;
  typedef PackedCache<BITS-kPageShift, uint64_t> CacheType;
};
// A two-level map for 32-bit machines
template <> class MapSelector<32> {
 public:
  typedef TCMalloc_PageMap2<32-kPageShift> Type;
  typedef PackedCache<32-kPageShift, uint16_t> CacheType;
};
 
// Pick the appropriate map and cache types based on pointer size
typedef MapSelector<kAddressBits>::Type PageMap;
typedef MapSelector<kAddressBits>::CacheType PageMapCache;
// common.h
#if defined __x86_64__
static const int kAddressBits = (sizeof(void*) < 8 ? (8 * sizeof(void*)) : 48); // __x86_64__就是64位
#else
static const int kAddressBits = 8 * sizeof(void*);
#endif

  下面介绍 PageHeapPageMap3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class PageHeap {
public:
  // interfaces here
private:
  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_;
  // Array mapping from span length to a doubly linked list of free spans
  SpanList free_[kMaxPages];
  int release_index_;
  int64_t scavenge_counter_;
};

  kMaxPagescommon.h 中定义为 1 << (20 - kPageShift),默认为 128free_SpanList 数组,一共 128 个,第零个未使用,第 iSpanList 维护着大小为 iPageSpan。每个 SpanList 包含两个 List,一个保存着 Span::locationON_NORMAL_FREELIST,另一个为 ON_RETURNED_FREELIST。大于 127 pagesSpan 保存在 large_ 中。
  PageHeap 有几个重要的接口:

  • Span* New(Length n), 分配 nPage,返回对应的 Span
  • void Delete(Span *span), 删除 Span
  • Span* GetDescriptor(PageID id), 返回 Page 所属的 Span
  • Span* Split(Span* span, Length n), 切分 SpannPage,并返回剩下的 PageSpan,要求 SpanIN_USE
  • Span* Carve(Span* span, Length n), 类似 Split
  • Length ReleaseAtLeastNPages(Length n); 释放至少 nPage,返回实际释放的;
  • void RegisterSizeClass(Span* span, size_t sc); 注册 Span 对应的 sizeclass
  • void CacheSizeClass(PageID p, size_t cl);Page 对应的 sizeclass 放入 PageHeap::pagemap_cache_
  • size_t GetSizeClassIfCached(PageID p); 在 pagemap_cache_ 中查找对应 Page 的 sizeclass;

  New 调用 SearchFreeAndLargeLists(n),该函数首先试图在 free_[i] 中搜索空闲 Span,其中 i >= n,优先使用 normal,其次是 returned,若搜索到空闲 Span,进行必要的切分。若 free_ 无法满足,则在 large_ 中搜索。如果 SearchFreeAndLargeLists 分配失败,则调用 ReleaseAtLeastNPages,尝试释放和合并空闲 Page。再次调用 SearchFreeAndLargeLists,若仍失败,则调用 GrowHeap(n),该函数至少分配 kMaxPages 个页面,然后重新调用 SearchFreeAndLargeLists
  DeleteSpan 放入对应的 free_ 或者 large_normal free list,然后尝试和相邻 Span 合并。最后调用 IncrementalScavenge(n),这个函数增加 Scavenge 计数,用做 Scavenge 的参考,ScavengeTCMalloc 相比 PTMalloc2 的一个特色,以后会介绍。
  SplitCarve 相似,用于切分 Span,并将适当调整其 location 和所在链表。区别在于 Carve 是私有函数,用于 PageHeap 内部的切分,Span 对象不能是 IN_USE 状态,而 Split 要求 SpanIN_USE 的,较少用到。
  ReleaseAtLeastNPages 循环遍历 free_large_normal free list,释放最后一个 Span,直到释放了至少 nPage,或者没有空闲 Page 可以释放为止。

Tags: .
你好!除了代码,此处没有多少原创之物,皆为本人搜集、整理、总结之记录与心得,欢迎转载分享!转载时请尽量注明出处,将不胜感激。祝你健康、快乐!
Home

Be the first to comment on this entry.

You must be logged in to post a comment.