18 Jun 2025

八股随写：Malloc

TOC

关于内存分配，看到什么就随便写什么。

在现代多核处理器架构下，内存分配器面临两个基本的性能瓶瓶颈：

伪共享 (False Sharing) 计算机系统的缓存与主存以缓存行（Cache Line，一般64字节）为单位交换数据。当一个CPU核心修改其缓存行中的数据时，为了保证数据一致性，其他CPU核心中包含相同内存地址的缓存行副本必须被置为无效。如果两个线程在不同核心上频繁读写两个独立的变量，而这两个变量恰好位于同一个缓存行内，就会导致缓存行在不同核心间被频繁地无效化和同步，即使这两个线程的操作逻辑上完全无关。这种现象称为伪共享，它会造成严重的性能下降。因此，需要考虑内存布局，避免将不同线程高频访问的数据分配在相邻的物理位置。
锁竞争 (Lock Contention) 进程的堆内存是所有线程共享的资源。如果一个全局锁保护内存分配和释放操作，那么在高并发场景下，所有线程都必须排队等待获取这把锁。此时，锁的竞争会成为系统瓶颈，导致CPU核心无法被有效利用，程序的伸缩性会受到限制。

上述挑战直接引出了内存分配器设计中必须面对的三个相互冲突的目标：分配速度、空间效率与多线程伸缩性。这三个目标之所以是主要且相互冲突的，我们来尝试将其中一个或两个目标推向极端，思考另外的目标会付出什么代价。

极端优化分配速度

方案：可以设计一个简单的Bump Allocator。它只维护一个指向大块连续内存的指针，每次分配请求，仅需将指针后移指定大小并返回原地址，free则完全不执行任何操作。
结果：分配速度很快。但空间效率会很低，因为内存永不回收，最终会耗尽。同时，为了在多线程下保证指针移动的原子性，必须引入全局锁，这将导致多线程伸缩性很差。

极端优化空间效率

方案：为了避免内存碎片，分配器在每次malloc时都必须遍历所有空闲块，寻找最合适的那一块。在每次free时，都必须检查能否与相邻的空闲块合并。在必要时，还需要执行 Compaction，移动已分配的对象来创造连续的大块空闲空间。
结果：内存利用率可能很高。但这种大量的遍历、计算和内存拷贝操作，将导致分配速度很慢。并且，管理全局内存布局的数据结构必须被全局锁保护，这同样会影响多线程伸缩性。

极端优化多线程伸缩性

方案：为每个线程都分配一个完全独立的、巨大的私有内存池，线程的所有内存操作都在自己的池内完成，线程间没有任何交互。
结果：由于无锁，多线程伸缩性可以做到很好。但空间效率会变得很差。内存无法在线程间流转，一个线程空闲的内存无法被另一个繁忙的线程使用。在后文将提到的生产者-消费者模型中，内存会单向地从生产者线程流向消费者线程，导致生产者不断申请新内存，而消费者持有的空闲内存却无法被重用。

通过这个分析可以看出，任何一个实用的内存分配器，其设计都是在这三个目标之间寻找一个平衡点。

分配速度：内存分配与释放是程序中的高频操作。分配延迟直接影响程序的整体执行性能。
空间效率：主要体现在对内存碎片的控制。碎片分为内部碎片（分配的块大于请求的尺寸）和外部碎片（空闲块不连续，无法满足大的分配请求）。低效的空间利用会导致进程常驻内存（RSS）持续增长，造成资源浪费。
多线程伸缩性：在多核处理器环境中，如果内存分配器依赖全局锁，那么在多线程并发申请内存时，该锁会成为性能瓶颈，导致程序无法通过增加CPU核心数来有效提升性能。

其他的考量因素，例如可移植性、安全性等也很重要，但上述三者是设计层面最根本的权衡，它们之间的内在矛盾决定了不同内存分配器的设计思路和适用场景。

ptmalloc的Arena模型与内存隔离

作为glibc的默认实现，ptmalloc可以理解为通用性与向后兼容。它从单线程的dlmalloc演化而来，其设计旨在解决多线程环境下的全局锁瓶颈问题。

该模型通过与线程独立的内存池（Arena）并配以独立的锁，将锁竞争分散开，提升了并发环境下的伸缩性。然而，这种设计因Arena之间严格的内存隔离，牺牲了部分场景下的空间效率。

这个问题在生产者-消费者这类内存跨线程传递的场景下尤为突出。举个例子：

一个生产者线程T1在首次分配内存时，被绑定到Arena A。它从Arena A获取内存块用于生产数据。如果Arena A内存耗尽，它会向操作系统申请更多内存，导致进程的常驻内存增长。
生产者T1将包含数据的内存块传递给消费者线程T2。
消费者线程T2隶属于另一个内存池Arena B。当T2处理完数据并调用free释放该内存块时，这块源自Arena A的内存，会被归还到T2当前所在的Arena B的空闲列表中。

对于ptmalloc这个固有的设计缺陷，jemalloc和tcmalloc都给出了各自的解决方案，其思路不同，也体现了它们的设计差异。

jemalloc的策略是内存归属权 jemalloc的设计中，一块内存从哪个Arena分配出来，就属于那个Arena。当任何线程调用free(ptr)时，jemalloc能通过指针地址ptr本身，直接计算出这块内存的来源，并将其精确地归还给它最初的Arena。这从机制上避免了内存的单向流动和失衡。
tcmalloc的策略是中心化调配 tcmalloc则采用了一种更动态的策略。当一个线程的本地缓存（ThreadCache）中积累了过多的空闲内存块时，它不会一直持有这些内存，而是会将一批（batch）内存对象交还给一个所有线程共享的“中央缓存”（CentralCache）。这样，其他需要内存的线程就可以从这个中央缓存中获取，实现了内存资源在所有线程间的动态再平衡。

这个过程导致了内存资源的失衡：生产者的Arena A内存只出不进，会持续消耗并向系统申请新内存；而消费者的Arena B则不断接收被释放的内存，堆积了大量空闲块。最终，尽管Arena B中有大量可用内存，但Arena A无法复用它们，导致进程整体的RSS随时间持续膨胀，即便应用实际使用的内存总量是稳定的。后续glibc版本中引入的tcache是一个在Arena之上的无锁线程缓存，它提升了小对象分配的速度，但并未改变底层Arena内存隔离的模型。

jemalloc

jemalloc由Jason Evans开发，最初为FreeBSD操作系统设计，后来被Facebook规模采用并深度发展。现在已经终止迭代了，详情看Jason Evans的博客。jemalloc的设计目标是将空间效率和可预测的内存行为置于较高优先级，这使其非常适合需要长期稳定运行的服务端应用。

jemalloc内部采用了清晰的内存单元层级：Arena -> Extent -> Run -> Region。一个Arena管理多个Extent（早期版本中称为Chunk），Extent是从操作系统申请的大块连续内存。Extent内部被划分为一个或多个Run，Run是用于分配一批相同尺寸小内存块的单元。而Run内部则被切割成最终交付给用户的Region。

jemalloc的一项机制是尺寸等级隔离。这并非其最初的设计，早期版本因采用统一的内存分配方式，在实际负载下暴露了严重的碎片化问题，这促使其架构被重构为将一个Extent专用于服务唯一一种尺寸等级（即一种Region大小）分配请求的模式。这种在物理上将同尺寸对象聚集在一起的做法，抑制了外部碎片。

另一项机制是在其4.x版本系列中引入的主动脏页回收。它并非完整的垃圾回收器，而是一个基于时间衰减的机制。jemalloc以页为单位追踪内存的使用情况，当一个内存页在一段时间内完全空闲（干净），jemalloc会认为它短期内不会被使用。此时，它会通过madvise等系统调用主动通知操作系统，该虚拟地址对应的物理内存可以被回收。这使得进程的RSS能够在负载高峰过去后回落。

根据作者的博客，jemalloc的演进与其在Facebook基础设施中的应用密不可分，海量的遥测数据和多样化的服务负载，为性能优化和碎片抑制策略的调整提供了帮助，可惜啊，infra不赚钱。

这里提到的“尺寸等级隔离”和“主动脏页回收”两个机制，通过与其它分配器的对比，可以更清晰地看出其设计侧重。

关于尺寸等级隔离： tcmalloc也采用了同样严格的尺寸等级隔离策略，让一个Span（类似jemalloc的Extent/Run）专用于一种尺寸。这已成为现代高性能分配器抑制外部碎片的通用实践。相比之下，ptmalloc的模型则较为灵活，一个从OS获取的大块内存可能被用于多种不同尺寸的分配，这使其在碎片控制方面不如前两者。
关于主动脏页回收：现代tcmalloc也具备类似的“回收”（Scavenging）机制，能够通过后台任务或在分配路径上，将长期空闲的物理内存归还给操作系统。 ptmalloc在这方面是一个弱点，其内存归还机制比较被动，主要依赖于堆顶部的收缩，很难回收堆中间形成的“空洞”，导致进程RSS易涨难降。因此，主动回收是jemalloc和tcmalloc共有的一个特性。而jemalloc的特点在于，它通过丰富的mallctl接口，将回收策略（如衰减时间decay time）的控制权暴露给用户，体现了其追求可预测性与可控性的设计思路。

tcmalloc

tcmalloc的设计目标是在大规模并发下，提供高的分配速度和吞吐量。它通过一个多级缓存系统来实现这一目标。

此处的缓存指的是内存分配器预先持有的一批空闲内存对象的集合，用于快速响应分配请求。

tcmalloc的实现建立在一个三级缓存架构上：

ThreadCache (线程缓存) ：这是最前端的一层。每个线程都拥有一个私有的ThreadCache，它为不同尺寸的小对象维护了独立的空闲链表。由于完全是线程本地操作，从这里分配和释放内存无需加锁，速度很快。多数的小对象分配都在这一层完成。
CentralCache (中心缓存) ：当ThreadCache中缺少某个尺寸的对象时，它会向CentralCache申请。CentralCache是所有线程共享的，同样按尺寸等级管理空闲对象。它作为各ThreadCache的内存来源和回收目的地。对CentralCache的访问需要加锁，但tcmalloc通过批量交换机制（ThreadCache一次性向CentralCache申请或归还一批对象，而不是一个），分摊了锁的开销。
PageHeap (页堆) ：这是最底层的内存管理器。当CentralCache也空了，它会向PageHeap申请更大的内存单元——Span（由一个或多个连续的物理页组成）。PageHeap负责与操作系统交互（如mmap），管理进程的虚拟内存空间。大对象的分配也会直接绕过前两级缓存，由PageHeap处理。

这个分层架构，确保了多数高频操作都发生在无锁的ThreadCache中，从而实现了良好的多线程伸缩性。

其现代实现采用Per-CPU缓存。它不是为每个线程分配缓存，而是为每个CPU逻辑核心分配一个。线程在哪个核心上执行，就使用哪个核心的缓存。这种设计利用了Linux内核的RSEQ (Restartable Sequences)特性来实现无锁访问。

RSEQ是一种用户态与内核的协作机制。用户态代码在执行一段被标记为RSEQ的关键序列前注册。如果内核在该序列执行期间因为调度或中断需要将当前线程换下CPU，那么当该线程被重新调度执行时，内核会强制将其指令指针重置到这段RSEQ代码的起始位置。这个机制保证了这段代码要么就完整执行完毕，要么就等于完全没有执行过。它以协作的方式实现了操作的原子性，允许多个线程在同一个CPU核心上安全地访问共享的Per-CPU缓存，而无需使用任何锁或原子指令，从而获得了很低的延迟。

jemalloc的尺寸等级隔离

jemalloc通过让一块从操作系统申请来的连续物理内存（Extent）只为一种特定大小的分配请求服务，来抑制外部碎片。

jemalloc在小内存分配的“慢路径”中严格执行此策略。当线程本地缓存（tcache）用尽，且对应Arena的Bin（特定尺寸的Region管理器）中也无可用内存时，分配流程会调用arena_slab_alloc申请一块全新的Extent。

其中一步是调用物理内存分配器pa_alloc，当前Bin的索引（binind）会被作为szind参数传入，这个szind字段会被记录在新创建的Extent元数据中，将这块物理内存绑定到了一个特定的尺寸等级。

 1// arena.c
 2static edata_t *
 3arena_slab_alloc(/* ... */ szind_t binind, /* ... */) {
 4    // ...
 5    // 1. 调用物理分配器(PA)，将`binind`作为`szind`参数传入。
 6    //    这就在创建时将`Extent`与Size Class绑定了。
 7    edata_t *slab = pa_alloc(tsdn, &arena->pa_shard, /* ... */
 8        /* slab */ true, /* szind */ binind, /* ... */);
 9    
10    // ...
11
12    // 2. 初始化Slab元数据，如设置`nfree`和`bitmap`。
13    //    这个位图就是逻辑上将大内存块“切割”成小`Region`的管理工具。
14    slab_data_t *slab_data = edata_slab_data_get(slab);
15    edata_nfree_binshard_set(slab, bin_info->nregs, binshard);
16    bitmap_init(slab_data->bitmap, &bin_info->bitmap_info, false);
17
18    return slab;
19}

新创建并初始化好的Extent返回后，会被设置为对应Bin的当前活动Slab（bin->slabcur），并立即投入专属服务。

1// arena.c
2static void
3arena_bin_refill_slabcur_with_fresh_slab(/* ... */ edata_t *fresh_slab) {
4    // ...
5    // 将新申请并初始化好的`Extent` (`fresh_slab`)
6    // 设置为这个`Bin`当前用于分配的`Extent` (`slabcur`)。
7    bin->slabcur = fresh_slab;
8}

通过这种机制，jemalloc减少了外部碎片产生的条件。一个Extent内部所有被释放的Region大小完全均一，都能被同一尺寸等级的下一次分配请求有效重用，不会留下畸零的、无法利用的内存空间。

jemalloc的主动回收触发

Jemalloc的主动回收机制，即基于时间衰减的脏页清除（Purging），存在两种工作模式，可通过配置项background_thread进行切换。

默认模式 (background_thread: false)

这是jemalloc的默认配置。在此模式下，jemalloc不创建任何专用的后台线程。脏页的检查和清除工作被同步地“搭载”在应用程序线程自身的malloc或free调用路径上。

为避免性能损耗，这个检查并非在每次内存操作时都发生，而是仅在“慢路径”（Slow Path）上被触发。例如，在tcache为空，需要从Arena填充时：

1// arena.c
2void
3arena_tcache_fill_small(/* ... */) {
4    // ... (tcache填充逻辑) ...
5    arena_decay_tick(tsdn, arena); // <--- 触发点
6}

arena_decay_tick会检查计时器是否到期。如果到期，它会进一步调用arena_decay_epoch_advance：

 1// arena.c
 2static void
 3arena_decay_epoch_advance(/* ... */) {
 4    // ...
 5    /*
 6     * 如果后台线程被禁用，或者当前线程就是后台线程，
 7     * 那么就执行清除操作。
 8     */
 9    if (!background_thread_enabled() || is_background_thread) {
10        arena_decay_try_purge(/* ... */);
11    }
12}

在默认模式下，!background_thread_enabled()为true，因此应用程序线程会自己同步地调用arena_decay_try_purge，最终执行madvise。

后台线程模式 (background_thread: true)

通过配置显式开启此模式后，jemalloc会创建专用的后台线程异步地负责回收工作，将回收操作从应用程序的关键路径中解耦出来。

主循环：后台线程在其主循环background_work_sleep_once中，会遍历它负责的Arena，并主动调用arena_decay发起检查。

 1// background_thread.c
 2static inline void
 3background_work_sleep_once(/* ... */) {
 4    // ...
 5    for (/* ... */) {
 6        /* 'true' 代表 "is_background_thread" */
 7        arena_decay(tsdn, arena, true, false);
 8    }
 9    // ...
10}

智能睡眠：后台线程并非以固定频率唤醒。它会根据每个Arena的“肮脏”程度，动态计算下一次需要唤醒的时间，避免空转浪费CPU。
响应式唤醒机制：为避免后台线程在长时间睡眠期间，应用线程突然释放大量内存而无法及时回收，jemalloc设计了“提前唤醒”机制。当应用线程在慢路径上发现有大量新产生的空闲页时，会调用background_thread_interval_check。

 1// background_thread.c
 2void
 3background_thread_interval_check(/* ... */) {
 4    // ...
 5    bool should_signal;
 6    if (info->npages_to_purge_new > BACKGROUND_THREAD_NPAGES_THRESHOLD ||
 7        unlikely(background_thread_indefinite_sleep(info))) {
 8        should_signal = true;
 9    }
10    if (should_signal) {
11        pthread_cond_signal(&info->cond);
12    }
13}

Fork安全性：jemalloc妥善处理了系统调用fork()。在fork之后，子进程中的后台线程状态会被完全重置并禁用，回退到默认的同步模式。

 1// background_thread.c
 2void
 3background_thread_postfork_child(tsdn_t *tsdn) {
 4    // ...
 5    background_thread_enabled_set(tsdn, false);
 6    for (unsigned i = 0; i < max_background_threads; i++) {
 7        background_thread_info[i].state = background_thread_stopped;
 8    }
 9    // ...
10}

tcmalloc的多级缓存架构

tcmalloc的内存管理建立在一个三层缓存体系之上，该体系旨在将高频的、小对象的分配和释放操作限制在无锁的线程本地环境中，仅在必要时才与需要加锁的全局资源交互。

ThreadCache 这是最高层级的缓存，每个应用程序线程都拥有一个独立的ThreadCache实例。它内部包含一个按尺寸等级组织的空闲对象链表数组。
```
1// thread_cache.h
2class ABSL_CACHELINE_ALIGNED ThreadCache {
3 private:
4  // ...
5  FreeList list_[kNumClasses];  // Array indexed by size-class
6  // ...
7};
```
当线程申请内存时，tcmalloc会首先尝试从这个线程私有的缓存中获取。由于访问是线程本地的，这个过程不需要任何锁，执行速度很快。
CentralCache 当ThreadCache中缺少某个尺寸的空闲对象时，它会向下一级的CentralCache申请。CentralCache是所有线程共享的资源，它同样按尺寸等级管理着空闲对象列表。它的作用是在不同线程的ThreadCache之间进行内存对象的调配。对CentralCache的访问需要加锁。
PageAllocator PageAllocator是tcmalloc最底层的内存管理器。当CentralCache自身也没有足够的空闲对象来满足ThreadCache的请求时，它会向PageAllocator申请一块更大的内存。PageAllocator以内存页（Page）为单位管理内存，它持有的内存单元被称为Span（一个或多个连续的页）。PageAllocator是tcmalloc与操作系统进行内存交互（例如通过mmap申请内存）的唯一接口。 CentralCache从PageAllocator获取一个Span后，会将其切割成一批特定尺寸的小对象，以补充自己的空闲列表。
```
1// central_free_list.cc
2Span* StaticForwarder::AllocateSpan(/* ... */) {
3  // ...
4  Span* span =
5      tc_globals.page_allocator().New(pages_per_span, span_alloc_info, tag);
6  // ...
7  return span;
8}
```
这个调用展示了CentralCache的填充逻辑如何向PageAllocator请求新的Span。

tcmalloc的批量内存交换

ThreadCache与CentralCache之间的数据交换并非以单个对象为单位，而是以“批量”的方式进行。这种设计可以分摊访问共享资源（CentralCache）时获取锁的成本。

当ThreadCache的某个空闲链表为空时，它会执行FetchFromTransferCache函数，向CentralCache请求一批对象。

 1// thread_cache.cc
 2void* ThreadCache::FetchFromTransferCache(size_t size_class, size_t byte_size) {
 3  FreeList* list = &list_[size_class];
 4  // 1. 根据尺寸等级，确定合适的批量大小
 5  const int batch_size = tc_globals.sizemap().num_objects_to_move(size_class);
 6  const int num_to_move = std::min<int>(list->max_length(), batch_size);
 7  void* batch[kMaxObjectsToMove];
 8  
 9  // 2. 从中央缓存（TransferCache）一次性移除一批对象
10  int fetch_count = tc_globals.transfer_cache().RemoveRange(
11      size_class, absl::MakeSpan(batch, num_to_move));
12  if (fetch_count == 0) {
13    return nullptr;
14  }
15
16  // 3. 将获取到的对象（除了第一个）放入自己的空闲链表
17  if (--fetch_count > 0) {
18    list->PushBatch(fetch_count, batch + 1);
19  }
20
21  // 4. 返回第一个对象给应用程序
22  return batch[0];
23}

这个过程获取了fetch_count个对象，但只产生了一次到CentralCache的调用。ThreadCache将fetch_count - 1个对象缓存起来，一个立即返回使用，从而为后续的分配请求做好了准备。

反之，当线程释放内存导致ThreadCache中某个尺寸的空闲对象过多时，它会触发归还机制，将一批对象交还给CentralCache。这一过程由ReleaseToTransferCache函数完成。

 1// thread_cache.cc
 2void ThreadCache::ReleaseToTransferCache(FreeList* src, size_t size_class,
 3                                         int N) {
 4  // ...
 5  void* batch[kMaxObjectsToMove];
 6  
 7  // 1. 从ThreadCache的空闲链表中一次性弹出一批（N个）对象
 8  src->PopBatch(N, batch);
 9
10  // 2. 将整批对象一次性插入到中央缓存（TransferCache）
11  tc_globals.transfer_cache().InsertRange(size_class,
12                                          absl::Span<void*>(batch, N));
13  // ...
14}

当某个空闲链表长度超过其动态调整的max_length阈值时，ListTooLong函数会被调用，它会确定一个合适的批量大小（batch_size）并调用ReleaseToTransferCache执行归还操作。这种机制避免了ThreadCache无限制地囤积空闲内存，并将不再活跃的对象重新放回共享池，供其他线程使用。

WUJS

I'm here