Tcmalloc

Posted by MegaBillow on Thursday, September 2, 2021

TCmalloc 中的 TC 代表 Thread Caching。

主要优势

  • 在高并发应用中更好的性能扩展性
  • 利用 C++14 和 C++17 的增强

两种工作模式

  • per-CPU caching 默认

    维护的 memory cache 对应于每一个独立的逻辑 cpu core。在支持 restartable sequences （RSEQ） 的 Linux kernel （4.18后支持）中被启用。

  • per-thread caching

    维护的 memory cache 对应于每一个应用线程。如果 RSEQ 不可用，TCmalloc 使用这种模式。

两种模式都能够在多数情况下的内存分配和释放避免用到锁。

特点

  • 管理特定大小的内存块（pages），统一内存块大小使得 bookkeeping 的工作得以简化，并且提高空间利用率。
  • 将 pages （连续的 pages 称为 span）针对不同的 object 大小进行对应，从而简化内存的分配和释放。
  • 为多数对象实现快速、无竞争的分配和释放。以per-logical-cpu、per-thread 两种模式支持对象 cache。由于多数情况不需要 lock，在多线程应用中有更低的竞争和更好的扩展性。
  • 将内存保持在 caches 中加速常用对象的访问。在释放之后继续持有 caches 避免后续的重新分配而进行系统调用的开销。
  • 采样开销低，利于应用使用内存的监控。

cache 的大小影响性能。cache 越大，cache 移除或者耗尽的情况越少，因而减少了请求更多内存而需要的锁操作。cache 的大小是可配置的。

整体架构

img

也是分层 multi-tier 的概念。

  • The front-end，是支持内存快速分配和释放的 cache 。只能有一个 thread 访问（如何保证？），所以不需要锁。然而如果 thread 数量较多的话，会占用大量的内存，或者每个 thread 的 caches 很小。分为：per-thread 和 per-cpu 两种模式。依赖内核支持（4.18+）。
  • The middle-end，负责重新填满 front-end cache
  • The back-end，负责从 OS 获取 memory

当请求一定大小的对象空间时，通过 SizeMap::GetSizeClass() 方法返回在 size-class 中对应的大小。

超过 kMaxSize 大小的空间直接从 backend 中分配，并且不会在 front 或 middle 中被 cache。大对象的空间向上对齐到 TCMalloc page size。

释放时，如果是小对象则会放回到 front 的 cache，如果超过 kMaxSize 则直接返回到 pageheap。

front per-cpu 模式

从某个 size-class的 array 中分配给对象及释放时，如何实现 remove 和 add？标记？ array 的空闲容量耗尽或溢出时，如何与 middle 进行交互？如果从 middle 申请更多的 size-class array ，地址与原来的 array 是否不连续？

每个 cpu 可以缓存的 memory 数量由 MallocExtension::SetMaxPerCpuCacheSize 确定。MallocExtension::ReleaseCpuMemory 释放不再使用的对象。

某个 size-class 的大小在总容量不超过 per-cpu limit 和 size-class 对应的 hard limit时，可以从其他空闲的 size-class 中调取容量。

通过 RSEQ 实现 per-cpu array 获取与释放的无锁操作。

front per-thread 模式

thread cache 包含理每个 size-class 的空闲对象采用单链表。初始化时，每个链表的大小是多少？还是 lazy 管理？

所有 per-thread的cache 容量上限由 MallocExtension::SetMaxTotalThreadCacheBytes 确定。但是总大小可能超过这个现实，因为 per-thread cache 的最小值为 KMinThreadCacheSize 通常为 512KB。当一个thread要增加其 cache 容量时，需要从其他 thread 调取。

当线程退出时，其 cache memory 返回给 middle。

img

front 大小的运行时调整

front cache 过大过小都会影响效率。per-thread 和 per-cpu 模式的动态调整 cache size 的实现不同。

middle end

作为 front 和 back 之间内存的中介，包括 Transfer cache 和 Central free list，每个 size-class 都有对应一对 transfter cache 和 central free list。都有 mutex lock 进行保护，所以有访问代价。

  • transfer cache 保持指向空闲内存的指针 array。如果其不能满足内存请求，或不能接受释放的对象，会访问 central free list。
  • central free list 以 spans 的形式管理内存，span 由一个或多个 TCMalloc page 组成。同 backend 的交互也是以 span 的形式进行。

transfer cache 和 central free list 如何交互？

pagemap 和 span

span 是连续的 page。采用2级或3级 radix tree 实现 memory 地址到 span 的映射。

img

在 middle 中 span 用来确定如何放置释放的 object，在 back 中管理 page 范围的处理。

span 可以用来管理小对象和大对象。 pagemap 用来查找object 对应的 span，或确定一个 object 对应的 size-class 。 在实现上使用了 union 来实现 span 在多种场景下的不同角色。

span 可能存在多种状态，可执行的方法与当前的状态有关。不同状态包括：

  • SMALL_OBJECT

    span 包含多个小对象。位于 CentralFreeList 中，通常在 CentralFreeList::nonempty_ list。 location_ == IN_USE

  • LARGE_OBJECT

    包含一个大对象。被用户使用。location_ == IN_USE

  • SAMPLED

    包含一个采样对象（什么作用？）。被用户使用。location_ == IN_USE && sampled_ == 1

  • ON_NORMAL_FREELIST

    没有分配的对象，属于 PageHeap ，在 normal PageHeap 中。location_ == ON_NORMAL_FREELIST

  • ON_RETURNED_FREELIST

    没有分配对象，属于 PageHeap ，在 returned PageHeap 中。location_ == ON_RETURNED_FREELIST

TCMalloc page size

小的 page size 以更小的内存开销满足应用。

大的 page size 降低与 back 交互内存的次数。以及降低 pagemap 中 entry 的数量。

backend

3个作用

  • 管理大块的未使用内存
  • 当不能满足分配请求时 负责从 OS 获取内存
  • 将不使用的内存归还给 OS

有两类 backend

  • legacy pageheap

    管理 TCMalloc page 大小的内存块。分配 k pages 时，逐级查找 list 是否有空闲的 pages ，查找失败时通过 mmap 获取内存。 如果在 m > k 的 list 中找到空闲pages， 则把剩余 m - k 大小的 pages 置入对应 list。 归还时，查看邻接pages 是否可以组成更大的连续 pages ，放入对应的空闲 list。

img

  • hugepage aware pageheap

    管理 hugepage 大小的内存块，可以降低 TLB miss 从而提高应用性能。在 X86 中 hugepage 是 2MB。通过三个 caches 来管理：

    1. filler cache， 类似 legacy pageheap，维护特定 pages 大小的空闲链表。小于 hugepage 大小的请求由此分配。
    2. region cache，跨多个 hugepage 的请求，组成一个连续的 region。适合处理稍稍大于 hugepage （2.1MB）的请求，在运行时确定该模式是否有启动的收益。
    3. hugepage cache，处理大于 hugepage 的请求，与 region cache 有重叠。

    在 https://google.github.io/tcmalloc/temeraire.html 中有详细的设计介绍。

TCMalloc API

针对 C++：

  • ::operator new, ::operator delete 以及针对 array 方法
  • C++14 sized ::operator delete
  • C++17 overaligned ::operator new 和 ::operator delete

不同于标准库的实现，在分配失败时不会抛出异常，而是直接 crash。

针对C 包括：

  • malloc, calloc, realloc, free

需要注意

在运行中的二进制不要加载 TCMalloc （例如：JNI）。通过系统 malloc 分配的对象可能会传递到 TCMalloc 中被释放，而导致未知错误。

扩展：RSEQ

原子化操作，相比 CAS 等更加高效。类似于数据库中的 transaction 。（引申，CAS 的一些问题。）

https://www.efficios.com/blog/2019/02/08/linux-restartable-sequences/

代码流程 除了最终存储到memory 的部分，需要支持 starting over。分为 abort sequence、restart sequence 两部分。

当 PC 在 restartable sequence 中发生 context 切换时， restart sequence 被触发执行。如果PC不是 restartable sequence 中，则线程重启在 abort sequence 中，abort sequence 确定被中断的 restartable sequence，将控制转到 restart sequence 的开始。

需要保存足够的状态信息来重启代码段，包括：函数参数，以及 CPU ID 等，重新计算所需的数值。

分配 N 个 TcmallocSlab::Slabs 的 array，通过逻辑 CPU ID 来索引。每个逻辑 CPU 对应其中的一个 region。

img

__rseq_cs_TcmallocSlab_Pop 是一个只读数据结构，包含特定 restartable sequence 的 metadata。当内核抢占当前线程时会检查这个数据结构。如果当前指令指针位于 [start, commit) 之间，则将控制在 abort 中转移到指定的 per-sequence restart header。在分配过程中会预取下一个 object，因为很有可能会有下一个分配。

用到了类似 goto 的 label，包含：restart, start, commit, underflow, abort 。

相关结构的图示 img

FEATURED TAGS
data tools