佛山网站如何制作,网页美工设计岗前培训,百度自媒体注册入口,小程序制作预览TcMalloc 的核心是分层缓存#xff0c;前端没有锁竞争#xff0c;可以快速分配和释放较小的内存对象#xff08;一般是 256 KB#xff09;前端有两种实现#xff0c;分别是 pre-CPU 和 pre-Thread 模式#xff0c;前者申请一块大的连续内存#xff0c;每一个逻辑 CPU 将…TcMalloc 的核心是分层缓存前端没有锁竞争可以快速分配和释放较小的内存对象一般是 256 KB前端有两种实现分别是 pre-CPU 和 pre-Thread 模式前者申请一块大的连续内存每一个逻辑 CPU 将获得其中的一段。这种模式下 TcMalloc 通过保存额外的元数据来动态地调整每种大小类的实际缓存大小。Per-Thread 模式为每个线程分配一个本地缓存线程缓存中每种大小类的可用对象通过链表连接。
当前端缓存耗尽时将会向中端请求新的缓存中端分为两部分传输缓存和中央空闲列表。传输缓存可以将其他前端返还给中端的内存快速分配给请求申请内存的前端如果传输缓存无法满足就会向中央空闲列表申请中央空闲列表以 Span 为单位管理内存Span 是一组连续的 TcMalloc 页Span 通过基数树管理。
当中端缓存耗尽或应用申请较大内存时需要后端参与后端一方面会管理一部分已经申请的页面同时还需要与 OS 交互真正申请和释放内存。后端有两种传统 pageheap 通过一个 256 位的链表数组管理特定长度的连续页面Hugepage Aware Allocator 包含三种缓存可以根据请求的内存大小动态确定使用哪种缓存。 【译】TcMalloc: Thread-Caching Malloc 原文链接 动力
TcMalloc 是一种内存分配器它作为系统默认分配器的一种替代方案被设计具有以下特征
快他可以无竞争地分配和释放大部分的对象。根据模式不同这些对象是按线程per-thread或逻辑 CPU per-CPU缓存的。大部分的分配不需要抢占锁因此在多线程程序中它的锁竞争更少伸缩性也更好。内存使用更灵活因为释放的内存可以用于其他不同大小的对象或返回给操作系统。通过分配拥有相同大小的对象的“页面”来降低每个对象的内存开销。使得对小对象的空间表示更高效。采样开销更低能够详细地了解应用程序的内存使用情况。
使用
您可以通过将 Bazel 中二进制规则的 Malloc 属性指定为 TCMalloc 来使用它。
概览
下面的框图显示了 TCMalloc 的大致内部结构 我们可以将 TCMalloc 分为三个组件前端、中端和后端。我们将在下面的部分中更详细地讨论这些。职责的大致划分如下:
前端是一个缓存为应用程序提供快速的内存分配和回收。中间端负责重新填充前端缓存。后端处理从操作系统获取内存。
请注意前端既可以在 per-CPU(逻辑 CPU) 模式下运行也可以在传统的 per-thread 模式下运行而后端既可以支持巨型页面堆hugepage也可以支持传统的页面堆legacy pageheap。
TcMalloc 前端
前端处理特定大小的内存请求。前端有一个内存缓存它可以用于分配或持有空闲内存。该缓存一次只能被一个线程访问应此不需要任何锁因此大多数的分配和释放是很快的。
对于任何请求如果前端有适当大小的内存缓存它就可以满足。如果特定大小的缓存为空前端将从中端请求一批内存来重新填充缓存。中端包括 CentralFreeList 和 TransferCache。、
如果中端内存已耗尽或者请求的大小大于前端缓存所能处理的最大大小则请求将转到后端以满足较大的分配或者重新填充中端缓存。后端也称为 PageHeap。
TCMalloc 前端有两种实现
开始时只支持的 per-thread每线程缓存(这也是 TcMalloc 名字的由来)。但是这会导致内存占用随着线程数量的增加而增加。现代应用程序可能有很多的线程数这导致要么聚集大量的 per-thread 内存要么许多线程拥有非常小的 per-thread 缓存。最近TCMalloc 支持 per-CPU 模式。在这种模式下系统中的每个逻辑 CPU 都有自己的缓存来分配内存。注意: 在 x86 上逻辑 CPU 相当于超线程(hyperthread)。
per-thread 和 per-CPU 模式之间的差异完全局限于 malloc/new 和 free/delete 的实现。
小对象和大对象分配
小对象的分配被映射到 60 80 个可分配大小类中的一个。例如一个 12 字节的分配将被四舍五入到 16 字节大小类。大小类的设计目的是尽量减少四舍五入到下一个最大大小类时所浪费的内存。
当用 __STDCPP_DEFAULT_NEW_ALIGNMENT__ 8 编译时对于用 ::operator new 分配的原始存储我们使用一组大小与 8 字节对齐的大小类。对于许多常见的分配大小(24、40 等)这种更小的对齐可以最大限度地减少浪费的内存否则这些大小将被四舍五入到 16 字节的倍数。在许多编译器上此行为由 -fnew-alignment... 标志控制。当没有指定 __STDCPP_DEFAULT_NEW_ALIGNMENT__ 或指定的值大于 8 字节时对 ::operator new 我们使用标准的 16 字节对齐然而对于16字节以下的分配我们可能会返回一个对齐较低的对象因为空间中不能分配具有较大对齐要求的对象。
当请求给定大小的对象时使用 SizeMap::GetSizeClass() 函数将该请求映射到特定大小类的请求返回的内存来自该大小类。这意味着返回的内存至少与请求的大小一样大。大小类的分配由前端处理。
大于 kMaxSize 大小的对象直接从后端分配。因此它们不会缓存在前端或中间端。大对象分配请求的大小将被四舍五入到 TCMalloc 页面大小(TCMalloc page size) 。
释放
当对象呗释放时编译器会提供对象的大小但如果不知道大小将会在页面映射中查找。如果对象很小它会被放回前端缓存。如果大小大于 kMaxSize 它将会被直接返回给 pageheap。
Pre-CPU 模式
在 Pre-CPU 模式下只会有一个大的内存块被分配。下图展示了这个内存片是如何在 CPU 之间进行分配的以及每个 CPU 如何使用片的一部分来保存元数据以及指向可用对象的指针。 每个逻辑 CPU 都被分配了该内存的一部分以保存元数据和指向特定大小类的可用对象的指针。元数据包括每个大小类的一个 /header/ 块。header 有一个指向每个大小类数组头部的指针Begin以及一个指向当前动态最大容量End和该数组段中的当前位置Current的指针。每个每个大小类指针数组的静态最大容量在开始时由该大小类的数组的开始和下一个下一个类的数组的开始之间的差确定。 header 有三个指针Begin 指向当前大小类内存起始位置Current 指向当前大小类已分配的内存位置end 指向动态可分配的最大内存地址动态可分配不是可分配这部分区域是已经划给当前大小类的但并不是说大小类只能分配到 End 在运行时可以存储在每个 CPU 块中的特定大小类的最大条目数量会有所变化但它永远不会超过启动时静态确定的最大容量。
当请求特定大小类的对象时将从该数组中删除该对象当释放该对象时将其添加到数组中。如果数组耗尽则使用中端的一批对象重新填充数组。如果数组溢出则从数组中删除一批对象并返回到中端。
每个 CPU 可以缓存的内存量由参数 MallocExtension::SetMaxPerCpuCacheSize 限制。这意味着缓存的内存总量取决于活跃的每个 CPU 中缓存的数量。因此具有更多 CPU 数量的机器可以缓存更多的内存。
为了避免不长时间运行程序的 CPU 占用大量内存MallocExtension::ReleaseCpuMemory 会释放保存在指定 CPU 缓存中的对象。
在 CPU 中内存的分布是跨所有大小类管理的以便使缓存的最大内存量低于限制。注意它管理的是可缓存的最大数量而不是当前缓存的数量。平均而言实际缓存的量应该是限制的一半左右。
当某一大小类的对象耗尽时该大小类的容量会增加。同时当申请较多对象时也会考虑增加该大小类的容量。我们可以扩大某一大小类的容量直到总缓存占用达到每个 CPU 的限制或某一大小类的容量达到该大小类硬编码的限制。如果大小类没有达到硬编码的限制那么为了增加容量它可以从同一 CPU 上的另一个大小类窃取容量。
可重启序列和 Pre-CPU TCMalloc
为了正确工作Pre-CPU 模式依赖于可重启序列(man rseq(2))。可重新启动序列只是(汇编语言)指令块很大程度上像一个典型的函数。可重启序列的一个限制是它们不能将部分状态写入内存最终指令必须是更新状态的单次写入。可重启序列的想法是如果一个线程在执行可重启序列时从 CPU 中换出(例如上下文切换)该序列将从从头开始执行。因此序列要么不间断地完成要么反复重启直到它不间断地完成。这是在不使用任何锁定或原子指令的情况下实现的从而避免了序列本身的任何竞争。
这对 TCMalloc 的实际意义是代码可以使用可重启的序列(如 TcMallocSLab_Internal_Push)从每个 CPU 数组中获取元素或将元素返回到该数组而不需要锁定。可重新启动序列可以确保在不中断线程的情况下更新数组或者在线程中断时重新启动序列(例如通过上下文切换允许在该 CPU 上运行另一个线程)。
关于设计选择和实现的其他信息将在特定的设计文档中进行讨论。
传统的 Per-Thread 模式
在 Per-Thread 模式中TCMalloc 为每个线程分配一个线程本地缓存。这个线程本地缓存满足较小的分配。根据需要将对象从中端移动到线程本地缓存中或从线程本地缓存中移出。
一个线程缓存包含每个大小类的一个空闲对象列表的单独的链表(所以如果有 N 个大小类就会有 N 个相应的链表)如下图所示。 在分配时将从对应大小类链表中删除一个对象释放时将会将对象插入到链表头部。可以访问中端以获取更多对象和返回一些对象到中端来处理下溢或溢出。
每个线程缓存的最大容量是由参数 MallocExtension::SetMaxTotalThreadCacheBytes 设置的。但是总大小可能会超过这个限制因为每个线程缓存的最小大小 KMinThreadCacheSize 通常是 512KiB。如果一个线程希望增加它的容量它需要从其他线程中窃取容量。
当线程退出时他们的缓存内存将返还给中端。
前端缓存的运行时大小
对前端缓存空闲列表的大小进行优化调整非常重要。如果空闲列表太小我们将需要经常访问中端空闲列表。如果空闲列表太大我们将浪费内存因为对象在其中处于空闲状态。
请注意缓存对于回收和分配的重要性是一样的。如果没有缓存每次释放都需要将内存移动到中央空闲列表Central free。
Pre-CPU 和 Pre-Thread 模式有不同的动态缓存大小算法的实现。
在 Pre-Thread 模式中每当需要从中间端获取更多对象时可以存储的最大对象数量都会增加到一个限制。同样当我们发现缓存了太多对象时容量也会降低。如果缓存对象的总大小超过每个线程的限制缓存的大小也会减小。在 Pre-CPU 模式中空闲列表的容量增加取决于我们是否在下溢和上溢之间交替(这表明更大的缓存可能会停止这种交替)。当容量一段时间没有增长因此可能会出现容量过剩时就会减少容量。
TcMalloc 中端
中端负责向前端提供内存并将内存返回给后端。中端包括 传输缓存 Transfer Cache 和 中央空闲列表Central free list。虽然它们通常写作单数但每个大小类都有一个传输缓存和一个中央空闲列表。这些缓存都由互斥锁保护 —— 因此访问它们需要序列化代价。
传输缓存
当前端申请或返还内存时它将接触到传输缓存。
传输缓存持有一个指向空闲内存指针的数组他可以快速地将对象移动到这个数组中或者代表前端从此数组中获取对象。
传输缓存得名于这样一种情况: 一个 CPU(或线程) 分配到由另一个 CPU(或线程) 释放的内存。传输缓存允许内存在两个不同的 CPU(或线程) 之间快速流动。
如果传输缓存无法满足内存请求或者没有足够的空间来保存返回的对象它将访问中央空闲列表。
中央空闲列表
中央空闲列表以 span 为单位管理内存一个 span 是一个或多个 “TCMalloc 内存页” 的集合。这些术语将在接下来的几节中进行解释。
对于申请一个或多个对象的请求中央空闲列表会不断通过向 Span 获取对象直到该请求被满足。如果 span 中没有足够的可用对象则会向后端请求更多 span。
当对象返还到中央空闲列表时每个对象被映射并释放到它所属的 span (使用页面映射 Pagemap )。如果驻留在特定 span 中的所有对象都返还给了它则整个 span 返还给后端。
Pagemap 和 span
由 TCMalloc 管理的堆被分为多个页其大小由编译时确定。连续页面的运行由一个 Span 对象表示。一个 Span 可以用于管理交付给应用程序的大对象也可以作为已经被拆分成一系列小对象的页运行。如果 span 管理的是小对象则 span 中会记录对象的大小类。
pagemap 用于查找对象所属的 span 或标识给定对象的大小类。
TCMalloc使用两层或三层的 基数树 radix-tree 将所有可能的内存位置映射到 span 上.
下面的图显示了如何使用两层 radix-tree 将对象的地址映射到控制对象所在页面的 span 上。在图中span A 涵盖两页span B 涵盖三页。 span 在中端用来确定将返回的对象放在哪里并在后端用来管理页面范围的处理。
在 span 中存储小对象
span 包含一个指向 TcMalloc span 控制页面基地址的指针。对于小对象这些页面最多分为 2162^{16}216 个对象。选择这个值是为了在 span 内通过两个字节的索引引用对象。
这意味着我们可以使用松散链表来保存对象。例如如果我们有 8 个字节的对象如果我们有八个字节的对象我们可以存储三个随时可用的对象的索引并使用第四个槽来存储链中下一个对象的索引。这种数据结构减少了全链接列表上的缓存丢失。
使用两个字节索引的另一个好处是我们可以使用 span 本身的空闲容量来缓存四个对象。
当某大小类没有可用对象时需要从页面堆中获取一个新的 span 并填充它。
TCMalloc 页大小
可以使用不同的页大小构建 TCMalloc。请注意这些与底层硬件的 TLB 中使用的页面大小不对应。TCMalloc 的页面大小目前为 4KiB、8KiB、32KiB 和 256KiB。
TcMalloc 的页可以容纳特定大小的多个对象也可以作为容纳超出单个页大小的对象的一组页面的一部分。如果整个页面空闲了它将被返还给后端。以后可以重新利用它来保存不同大小的对象(或返回到操作系统)。
较小的页面能够以较少的开销更好地处理应用程序的内存需求。例如使用了一半的 4KiB 页面将剩余 2KiB而32KiB 的页面将剩余 16KiB。小页面也更有可能变得空闲。再例如4KiB 页可以容纳 8 个 512 字节的对象而32KiB 页可以容纳 64 个对象64 个对象同时空闲的可能性比 8 个对象空闲的可能性要小得多。
大页面减少了从后端获取和返回内存的需要。单个 32KiB 页面可以容纳 8 倍于 4KiB 页面的对象这可能会导致管理较大页面的成本较小。映射整个虚拟地址空间所需的大页面也更少。TCMalloc 有一个页面映射它将虚拟地址映射到管理该地址范围内的对象的结构上。较大的页面意味着页面映射需要较少的条目因此较小。
因此对于内存占用小的应用程序或者对内存占用大小敏感的应用程序使用较小的 TCMalloc 页面大小是有意义的。占用较大内存的应用程序可能会受益于较大的 TCMalloc 页面大小。
TcMalloc 后端
TcMalloc 后端干三件事
管理未使用的大块内存。当没有合适大小的内存来满足分配请求时它负责从操作系统获取内存。它负责将不需要的内存返回给操作系统。
TcMalloc 后端有两种
管理 TcMalloc 中 page 大小内存块的 Legacy pageheap 传统页堆以 hugepage 大小为单位管理内存的 hugepage aware pageheap超大页感知分配器。以 hugepage 为单位管理内存使分配器能够通过减少 TLB 未命中来提高应用程序性能。
Legacy pageheap
传统页堆是一个可用内存中连续页面的特定长度的空闲列表的数组。当 k 256 时它的第 k 个节点就是一个由 k 个 TcMalloc 页组成的空闲运行列表。第 256 个节点是长度大于 256 页的空闲运行列表。 大白话就是 Legacy pageheap 是一个长度为 256 的数组数组每一位保存一个可用内存的链表链表的每个节点都是连续的 i 个 TcMalloc 页。i 由链表在数组中的位置决定大于 255 的 i 都保存在数组最后一位。 我们可以通过查找第 k 个空闲列表来满足 k 个页面的分配。如果那个空闲列表是空的我们就查找下一个空闲列表依此类推。最后如果需要当我们查找到最后一个空闲列表依然失败时我们将通过系统的 mmap 获取内存。
如果长度大于 k 的页面满足了对 k 个页面的分配则结点剩余的部分将被重新插入到适当的空闲列表中。 假设要申请两个页面但第二条空闲列表空了第三条列表中每个节点有三个页面分配掉两个后余下一个会被插入到第一条列表中 当向页面堆返回一定范围的页面时将检查相邻的页面以确定它们现在是否形成了一个连续的区域如果是这样则将这些页面连接起来并放置到适当的空闲列表中。 尽量减少碎片 Hugepage Aware Allocator
Hugepage Aware Allocator 的目标是将内存保存在 hugepage 大小的块中。在 x86 上一个 hugepage 的大小是 2MiB。为此后端有三个不同的缓存 填充缓存filler cache保存已从其分配了一些内存的 hugepage。可以认为这类似于 Legacy pageheap 因为它保存特定数量的 TCMalloc 页的内存链表。(通常)从填充缓存返回对小于 hugepage 大小的大小的分配请求。如果填充缓存没有足够的可用内存它将请求额外的 hugepage 来分配。 区域缓存region cache用于处理大于一个 hugepage 的分配。这个缓存允许跨多个 hugepage 的分配并将多个这样的分配打包到一个连续的区域中。这对于稍微超过一个大页面大小的分配尤其有用(例如2.1 MiB)。 Essentially, the path of an allocation goes like this:(本质上分配思路是这样的) If it is sufficiently small and we have the space we take an existing, backed, partially empty hugepage and fit our allocation within it.(如果它足够小并且我们有足够的空间我们就使用一个现有的、有支持的、部分空的 hugepage并将我们的分配放在其中。) If it is too large to fit in a single hugepage, but too small to simply round up to an integral number of hugepages, we best-fit it into one of several larger slabs (whose allocations can cross hugepage boundaries). We will back hugepages as needed for the allocation.(如果它太大了不能放在一个 hugepage 中但又太小了不能简单地四舍五入到一个整数 hugepage那么我们最好把它放在几个更大的 slab 中(它们的分配可以跨越 hugepage 边界)。我们将根据分配的需要支持 hugepage。) Sufficiently large allocations are rounded up to the nearest hugepage; the extra space may be used for smaller allocations.(足够大的分配被四舍五入到最近的 hugepage额外的空间可用于较小的分配。) hugepage 缓存处理至少一个 hugepage 的大量分配。与区域缓存的使用有重叠但区域缓存仅在确定(在运行时)分配模式将使其受益时才启用。
有关 HPAA 的设计和选择的其他信息在其特定设计文档中进行讨论。
注意事项
TCMalloc 将在启动时为元数据保留一些内存。元数据的数量将随着堆的增长而增长。特别是页面映射将随着TCMalloc 使用的虚拟地址范围而增长span 将随着内存的活动页面数量的增长而增长。在 pre-CPU 模式下TCMalloc 将为每个 CPU 保留一个内存片(通常为 256 KiB)这在具有大量逻辑 CPU 的系统上可能会导致几兆字节的占用空间。
值得注意的是TCMalloc 以大块(通常为 1 GiB 区域)的形式向操作系统请求内存。地址空间是保留的但在使用之前不会得到物理内存的支持。由于该方法应用的 VSS 可以比 RSS 大得多。这样做的一个副作用是在应用程序使用了那么多物理内存之前试图通过限制 VSS 来限制应用程序的内存使用将会失败很久。
不要试图将 TCMalloc 加载到运行的二进制文件中(例如在 Java 程序中使用 JNI)。二进制文件将使用系统 Malloc 分配一些对象并可能尝试将它们传递给 TCMalloc 以进行释放。TCMalloc 将无法处理此类对象。
