欢迎大家来到今天的技术讲座，我们即将深入探讨一个在现代高性能系统设计中至关重要的主题：内存分配架构。特别是，我们将聚焦于受到Google TCMalloc启发的设计理念，剖析其核心组件——mspan、mcache和mcentral——如何协同工作，共同构建一个高效、并发且低碎片的内存管理系统。
在多线程、高并发的应用场景下，传统通用的malloc实现（例如glibc的ptmalloc）往往面临着严峻的挑战。全局锁竞争、内存碎片、以及不够理想的缓存局部性，都可能成为系统性能的瓶颈。TCMalloc的出现，正是为了应对这些问题，它通过精巧的分层设计和细致的策略，在速度、并发性和内存效率之间找到了一个卓越的平衡点。
我们将以一名经验丰富的编程专家的视角，带领大家一步步揭开TCMalloc架构的神秘面纱。理解这些核心概念，不仅能帮助我们更好地利用现有库，更能为我们设计和优化自己的内存管理方案提供宝贵的洞察。
内存分配的挑战：为何需要TCMalloc？
在我们深入TCMalloc的具体组件之前，非常有必要先理解为什么我们需要像TCMalloc这样复杂的内存分配器。一个看似简单的malloc(size)调用背后，隐藏着诸多性能陷阱和设计难题。
1. 性能瓶颈：锁竞争与系统调用开销
在多线程环境中，如果所有线程都尝试从一个共享的全局堆中分配内存，那么为了保证数据的一致性，就必须引入锁机制。当大量线程同时请求内存时，这些锁会成为严重的瓶颈，导致线程串行化，显著降低程序的并发性能。这种现象被称为“锁竞争”（Lock Contention）。
此外，从操作系统获取原始内存（例如通过sbrk或mmap系统调用）是相对昂贵的操作。频繁地进行系统调用会引入用户态到内核态的切换开销，这在高性能应用中是不可接受的。因此，高效的分配器需要尽可能地减少直接与操作系统交互的次数。
2. 内存碎片：内外部碎片化
内存碎片是内存管理中一个永恒的难题，它分为两种主要类型：
- 内部碎片（Internal Fragmentation）：当分配器为了满足一个请求而分配了比实际请求更大的内存块时，多余的部分就形成了内部碎片。例如，如果分配器只能以8字节的倍数分配内存，而用户请求了7字节，那么实际会分配8字节，浪费了1字节。虽然单次浪费很小，但累积起来可能很可观。
- 外部碎片（External Fragmentation）：当内存中存在足够的总空闲空间来满足一个请求，但这些空闲空间不连续，无法组成一个足够大的连续块时，就发生了外部碎片。这导致即使有大量空闲内存，也无法满足较大的分配请求，最终可能导致内存耗尽。
高效的分配器需要设计策略来最小化这两种碎片，例如通过“大小分类”（Size Classing）来减少内部碎片，并通过合并相邻的空闲块来缓解外部碎片。
3. 缓存局部性：CPU缓存的利用
现代CPU的性能远超内存，因此，有效地利用CPU缓存对于提高程序性能至关重要。内存分配器如果能将相关联的数据分配到物理上或逻辑上更接近的内存区域，就能提高缓存命中率，从而加速数据访问。如果分配器导致内存布局混乱，频繁的缓存失效会严重拖慢程序。
4. 对象生命周期与回收：
内存的分配和回收必须是高效且正确的。一个好的分配器不仅要快速分配，还要能够快速回收，并且将回收的内存有效地重新利用起来，避免内存泄漏，同时也要避免“Use-After-Free”等安全问题。
TCMalloc正是针对上述挑战，提出了一套分层、并发、细粒度的解决方案。其核心思想是：将不同大小的内存请求分而治之，并利用线程局部缓存来消除锁竞争，同时通过精巧的内存块管理来减少碎片。这套方案的基石便是我们今天将要深入探讨的mspan、mcache和mcentral。
TCMalloc的整体架构概览
TCMalloc的设计哲学可以概括为以下几点：
- 线程局部缓存（Thread-Local Caching）：每个线程维护一个独立的内存缓存 (
mcache)，用于处理小对象分配。这极大地减少了全局锁的竞争。 - 大小分类（Size Classing）：将内存请求按大小划分为不同的“大小类”。每个大小类对应一个预设的、固定大小的对象块。这有助于减少内部碎片，并简化内存管理。
- 页（Page）作为基本单位：TCMalloc从操作系统获取内存的基本单位是页（通常为4KB）。然后，这些页被进一步细分为更小的对象。
- 分层管理：整个系统分为三层：
mcache(Thread-Local Cache)：处理小对象分配，无锁。mcentral(Central List of Spans)：负责在mcache和全局页堆之间协调mspan的分配与回收，有锁保护。- Page Heap (Global Page Allocator)：从操作系统获取大块内存页，并管理它们的分配与合并，提供给
mcentral。
这三层结构协同工作，形成了TCMalloc高效的核心。现在，让我们逐一深入这些组件。
mspan：内存管理的基本单元
首先，我们来认识一下mspan。它是TCMalloc中管理连续内存页的基本单元。你可以把它想象成一个“内存块的管理者”，它负责将从操作系统获取到的一段连续的物理页（或虚拟页）划分为更小的、相同大小的对象，并管理这些对象的分配与回收。
1. mspan的定义与目的
一个mspan本质上是一个或多个连续的内存页。它从TCMalloc的全局页堆（Page Heap）中获取，并被赋予一个特定的“大小类”（size class）。这意味着一个mspan一旦被配置，就只能用于分配特定大小的对象。
目的：
- 管理连续页面：将从操作系统获取的零散页面整合成可管理的大块。
- 细分内存：根据特定的大小类，将大块页面细分为多个小对象，供应用程序使用。
- 跟踪对象状态：记录
mspan内每个小对象的分配状态（已分配或空闲）。 - 支持回收与合并：当
mspan中的所有对象都被释放时，它可能被回收并与相邻的空闲mspan合并，以形成更大的连续空闲页块，最终可能返还给操作系统，从而减少外部碎片。
2. mspan的结构与属性
一个mspan对象通常包含以下关键属性：
| 属性名称 | 类型 | 描述 |
|---|---|---|
start_address |
void* |
mspan管理的这段连续内存的起始虚拟地址。 |
num_pages |
size_t |
mspan所包含的页数。 |
size_class |
int |
mspan被配置来分配的对象的“大小类”ID。 |
object_size |
size_t |
根据size_class计算出的实际对象大小。 |
num_objects_total |
size_t |
mspan在完全细分后能容纳的总对象数。 |
num_free_objects |
size_t |
当前mspan中可用的空闲对象数。 |
free_list |
ObjectHeader* |
一个链表头指针，指向mspan内所有空闲对象的链表。每次分配/回收都操作此链表。 |
next, prev |
mspan* |
指针，用于将mspan链接到mcentral的列表中（例如，非空闲列表或空闲列表）。 |
allocated_bitmap |
std::vector<bool> 或 uint64_t[] |
一个位图，用于更高效地追踪mspan内每个对象的分配状态。位图比链表在某些情况下更优。 |
3. mspan的生命周期与操作
- 获取：当
mcentral需要一个mspan来为某个size_class提供内存时，它会从全局页堆请求一个或多个连续的内存页，并用这些页初始化一个新的mspan对象。 - 初始化与细分：
mspan被初始化其start_address、num_pages和size_class。- 根据
size_class，计算出object_size和num_objects_total。 mspan将其管理的连续内存块细分为num_objects_total个大小为object_size的小对象。这些对象最初都被添加到free_list中。
- 分配对象：当
mcache（或直接mcentral）从mspan请求一个对象时，mspan会从其free_list中取出一个对象并返回，同时递减num_free_objects。 - 回收对象：当一个对象被释放时，它会被重新添加到其所属
mspan的free_list中，并递增num_free_objects。 - 状态变化：
- 当
num_free_objects变为0时，mspan被认为是“满的”（fully allocated）。 - 当
num_free_objects等于num_objects_total时，mspan被认为是“空的”或“完全空闲的”（fully free）。
- 当
- 返回与合并：当一个
mspan完全空闲时，它会被返回给mcentral。mcentral会尝试将这个mspan与相邻的空闲mspan进行合并，形成更大的连续空闲页块，然后这些大块可能最终被返还给全局页堆，甚至系统。
4. 概念代码示例：mspan结构与初始化
#include <cstddef> // For size_t
#include <vector> // For std::vector (conceptual bitmap)
#include <iostream>
// 假设一页内存大小为4KB
const size_t kPageSize = 4096;
const int kNumSizeClasses = 85; // TCMalloc typically has many size classes
// 前向声明，用于GetSizeForSizeClass
size_t GetSizeForSizeClass(int size_class);
// 定义一个简单的对象头，用于构建空闲链表
struct ObjectHeader {
ObjectHeader* next;
};
// mspan 结构体定义
struct Span {
void* start_address; // 管理内存的起始地址
size_t num_pages; // 包含的页数
int size_class; // 所属大小类
size_t object_size; // 每个对象的大小
size_t num_objects_total; // 总对象数
size_t num_free_objects; // 当前空闲对象数
ObjectHeader* free_list; // 空闲对象链表头
Span* next; // 用于在链表中连接
Span* prev; // 用于在链表中连接
// 构造函数
Span() : start_address(nullptr), num_pages(0), size_class(0),
object_size(0), num_objects_total(0), num_free_objects(0),
free_list(nullptr), next(nullptr), prev(nullptr) {}
// 初始化 Span，将其细分为指定大小的对象
void Init(void* start, size_t pages, int sc) {
start_address = start;
num_pages = pages;
size_class = sc;
object_size = GetSizeForSizeClass(sc); // 获取实际对象大小
// 确保object_size至少为sizeof(ObjectHeader)以便能形成链表
if (object_size < sizeof(ObjectHeader)) {
object_size = sizeof(ObjectHeader);
}
num_objects_total = (num_pages * kPageSize) / object_size;
num_free_objects = num_objects_total;
// 构建空闲链表
free_list = nullptr;
for (size_t i = 0; i < num_objects_total; ++i) {
// 计算当前对象的地址
void* obj_ptr = static_cast<char*>(start_address) + i * object_size;
ObjectHeader* header = static_cast<ObjectHeader*>(obj_ptr);
header->next = free_list; // 将新对象添加到链表头部
free_list = header;
}
std::cout << "Span initialized: start=" << start_address
<< ", pages=" << num_pages
<< ", size_class=" << size_class
<< ", object_size=" << object_size
<< ", total_objects=" << num_objects_total << std::endl;
}
// 从 Span 分配一个对象
void* AllocateObject() {
if (num_free_objects == 0) {
return nullptr; // 没有空闲对象
}
ObjectHeader* obj = free_list;
free_list = free_list->next;
num_free_objects--;
// 注意：这里没有清空内存，实际生产级分配器通常不会在分配时清空
return obj;
}
// 将一个对象归还给 Span
void DeallocateObject(void* ptr) {
if (!ptr) return; // 避免空指针解引用
// 简单检查ptr是否在span范围内 (更严谨的检查需要page map)
if (ptr < start_address || ptr >= static_cast<char*>(start_address) + num_pages * kPageSize) {
// Error: pointer not belonging to this span
std::cerr << "Error: Pointer " << ptr << " does not belong to this span." << std::endl;
return;
}
ObjectHeader* header = static_cast<ObjectHeader*>(ptr);
header->next = free_list; // 将对象添加到空闲链表头部
free_list = header;
num_free_objects++;
std::cout << "Object " << ptr << " deallocated to span " << start_address
<< ", free_objects=" << num_free_objects << std::endl;
}
// 检查 Span 是否完全空闲
bool IsFullyFree() const {
return num_free_objects == num_objects_total;
}
// 检查 Span 是否已满（没有空闲对象）
bool IsFull() const {
return num_free_objects == 0;
}
};
// 辅助函数：根据大小类获取实际分配大小
// 实际的TCMalloc有复杂的规则，这里简化为一个示例
size_t GetSizeForSizeClass(int size_class) {
if (size_class == 0) return 8;
if (size_class == 1) return 16;
if (size_class == 2) return 32;
if (size_class == 3) return 64;
if (size_class == 4) return 128;
if (size_class == 5) return 256;
if (size_class == 6) return 512;
if (size_class == 7) return 1024;
if (size_class == 8) return 2048;
if (size_class == 9) return 4096; // 一个页
// ... 更多的size classes
return 0; // Invalid size class
}
// 辅助函数：根据请求大小获取大小类
int GetSizeClass(size_t bytes) {
if (bytes <= 8) return 0;
if (bytes <= 16) return 1;
if (bytes <= 32) return 2;
if (bytes <= 64) return 3;
if (bytes <= 128) return 4;
if (bytes <= 256) return 5;
if (bytes <= 512) return 6;
if (bytes <= 1024) return 7;
if (bytes <= 2048) return 8;
if (bytes <= 4096) return 9;
// For larger sizes, TCMalloc has different strategies (large object allocation)
return -1; // Indicate a large object or error
}在实际的TCMalloc中，mspan的空闲对象管理通常会使用位图（bitmap）而非简单的链表，尤其是在对象数量较多且对象较小的情况下。位图可以更紧凑地表示空闲状态，并且在查找下一个空闲对象时，结合CPU的位操作指令（如__builtin_ffs）可以非常高效。然而，链表实现概念上更直观，且在某些场景下（如对象数量不多时）性能也足够。
mcache：线程局部的快速缓存
现在我们来到TCMalloc性能的关键所在——mcache。mcache是每个线程私有的内存缓存。它的核心设计思想是：消除锁竞争，实现极速的小对象分配。
1. mcache的定义与目的
每个应用程序线程在首次请求内存时，TCMalloc都会为其创建一个独立的mcache实例。这个mcache不与其他线程共享，因此对它的所有操作都是无锁的。
目的：
- 无锁分配：通过线程局部性，避免了在分配小对象时对全局数据结构加锁，显著提升并发性能。
- 缓存局部性：线程分配的内存块倾向于位于该线程自己的
mcache所管理的mspan中，这有助于提高数据访问的缓存命中率。 - 减少系统调用：
mcache从mcentral批量获取mspan或对象，减少了与中央分配器的交互频率，进而减少了潜在的锁开销。
2. mcache的结构与属性
一个mcache通常包含以下关键属性：
| 属性名称 | 类型 | 描述 |
|---|---|---|
current_spans |
Span*[] |
一个mspan指针数组，索引是size_class。每个元素指向当前线程为该大小类正在使用的mspan。 |
transfer_cache |
ObjectHeader*[] |
对于某些大小类，可能有一个中间缓存，用于批量从mcentral获取或返还对象，进一步平摊锁开销。 |
num_cached_bytes |
size_t |
跟踪mcache当前缓存的总字节数，用于控制缓存大小和决定何时将空闲内存返还给mcentral。 |
3. mcache的分配流程
当一个线程请求分配N字节的内存时：
- 大小类映射：
N字节被映射到最近的、预定义好的size_class。 - 检查
current_spans：mcache查找其current_spans数组中对应size_class的mspan。 - 直接分配（快路径）：如果找到的
mspan存在且有空闲对象，mcache直接从该mspan的free_list中取出一个对象并返回。这是一个O(1)的无锁操作，是TCMalloc最快的分配路径。 mspan耗尽（慢路径）：如果current_spans中对应的mspan为空或已无空闲对象：- 旧
mspan处理：如果mcache之前有为该size_class服务的mspan（现在已耗尽），它会将这个mspan返回给mcentral的empty_spans列表。 - 请求新
mspan：mcache向mcentral发出请求，索取一个新的、包含空闲对象的mspan（或直接一批空闲对象）。mcentral会从其nonempty_spans列表中提供一个mspan，或者在没有可用mspan时，从全局页堆获取新页并初始化一个mspan。 - 更新
current_spans：mcache将新获得的mspan设置为其current_spans中对应size_class的mspan。 - 分配：最后，从这个新获得的
mspan中分配一个对象并返回。
- 旧
4. mcache的回收流程
当一个线程释放一个指针P时：
- 查找所属
mspan：TCMalloc需要快速确定P所属的mspan。这通常通过一个全局的“页映射”（Page Map）来实现，该映射将内存地址（或其所在的页地址）映射到对应的mspan结构。 - 归还对象：一旦确定了
mspan，对象P会被归还到该mspan的free_list中，并递增mspan的num_free_objects计数。 mspan状态更新：- 如果
mspan中的空闲对象数量达到一定阈值，或者mspan变得完全空闲（num_free_objects == num_objects_total），mcache可能会决定将其返还给mcentral。这是为了防止mcache持有过多空闲内存，造成内存浪费，并为mcentral提供碎片合并的机会。 mcache通常会维护一个“溢出计数器”或“回收批次大小”的策略，只有当累积的空闲对象达到一定数量时，才批量返还给mcentral，以减少与mcentral的交互频率。
- 如果
5. 概念代码示例：mcache结构与分配/回收
// 前向声明 MCentral
class MCentral;
// 假设有一个全局的 PageMap 实例，可以将任意指针映射到其所属的 Span
// 这是一个关键组件，后面会详细介绍
Span* GetSpanForPointer(void* ptr);
// MCache 结构体定义
struct MCachedSpan {
Span* span;
// 实际TCMalloc会在这里存储一些统计信息，
// 或者一个小的free list用于批量操作，减少与span的直接交互
ObjectHeader* current_batch_free_list;
size_t current_batch_size;
};
class MCachedSpanManager {
public:
MCachedSpan m_spans[kNumSizeClasses]; // 为每个大小类维护一个MCachedSpan
// 缓存中的总字节数，用于控制缓存大小
size_t total_cached_bytes;
MCachedSpanManager() : total_cached_bytes(0) {
for (int i = 0; i < kNumSizeClasses; ++i) {
m_spans[i].span = nullptr;
m_spans[i].current_batch_free_list = nullptr;
m_spans[i].current_batch_size = 0;
}
}
void* Allocate(size_t bytes);
void Deallocate(void* ptr);
private:
// 从 MCentral 获取一个 Span 或一批对象来填充 mcache
Span* RefillSpan(int size_class);
// 将空闲 Span 返回给 MCentral
void ReturnSpanToCentral(Span* span, int size_class);
};
// 假设我们有一个全局的 MCentral 实例
extern MCentral* g_mcentral;
void* MCachedSpanManager::Allocate(size_t bytes) {
int sc = GetSizeClass(bytes);
if (sc == -1) { // 如果是大对象，或者无效大小类
// 大对象通常直接从全局页堆分配，不经过 mcache/mcentral 的对象分配逻辑
// 这里只是一个占位符，实际需要调用 PageHeap::AllocateLargeObject()
std::cerr << "Attempted to allocate large object or invalid size class: " << bytes << " bytes" << std::endl;
return nullptr;
}
// 尝试从当前 span 分配
MCachedSpan& mc_span = m_spans[sc];
if (mc_span.span == nullptr || mc_span.span->num_free_objects == 0) {
// 当前 Span 已用尽或不存在，需要从 MCentral 填充
Span* new_span = RefillSpan(sc);
if (new_span == nullptr) {
std::cerr << "Failed to refill span for size_class " << sc << std::endl;
return nullptr; // 内存耗尽
}
mc_span.span = new_span;
}
void* obj = mc_span.span->AllocateObject();
if (obj) {
// 更新缓存统计信息
total_cached_bytes -= GetSizeForSizeClass(sc); // 之前计入缓存的空闲对象现在被使用了
}
return obj;
}
void MCachedSpanManager::Deallocate(void* ptr) {
if (!ptr) return;
// 1. 查找指针所属的 Span
Span* span = GetSpanForPointer(ptr);
if (!span) {
// 这通常意味着这是一个TCMalloc未管理的内存，或者是一个大对象
std::cerr << "Deallocating pointer " << ptr << " not managed by a known span." << std::endl;
// 对于大对象，需要调用 PageHeap::DeallocateLargeObject()
return;
}
int sc = span->size_class;
size_t obj_size = span->object_size;
// 2. 将对象归还给 Span
span->DeallocateObject(ptr);
// 3. 更新 mcache 统计信息
total_cached_bytes += obj_size;
// 4. 检查 Span 是否完全空闲，并决定是否返还给 MCentral
// 实际的TCMalloc有更复杂的策略来决定何时将Span返回给MCentral，
// 例如当mcache的缓存大小超过某个阈值时，或者线程退出时。
// 这里简化为：如果span完全空闲，就返回。
if (span->IsFullyFree()) {
ReturnSpanToCentral(span, sc);
// 如果这个 span 恰好是当前线程正在使用的 span，则需要清空
if (m_spans[sc].span == span) {
m_spans[sc].span = nullptr;
}
}
}
Span* MCachedSpanManager::RefillSpan(int size_class) {
std::cout << "MCache: Refilling span for size_class " << size_class << std::endl;
// 如果当前有旧的 Span 已经耗尽，先将其返还给 MCentral
if (m_spans[size_class].span != nullptr && m_spans[size_class].span->IsFull()) {
// 将旧的、已耗尽的 span 返回给 MCentral 的 empty_spans 列表
// MCentral 负责将它从 empty_spans 移到 nonempty_spans 如果有对象被释放回来
g_mcentral->ReturnSpan(m_spans[size_class].span, size_class);
}
// 向 MCentral 请求一个新的 Span
Span* new_span = g_mcentral->GetSpanForSizeClass(size_class);
if (new_span) {
// 更新 mcache 的缓存字节数（这里假设 new_span 刚被分配，所有对象都空闲）
total_cached_bytes += new_span->num_free_objects * new_span->object_size;
}
return new_span;
}
void MCachedSpanManager::ReturnSpanToCentral(Span* span, int size_class) {
std::cout << "MCache: Returning fully free span " << span->start_address
<< " to MCentral for size_class " << size_class << std::endl;
total_cached_bytes -= span->num_objects_total * span->object_size; // 从缓存计数中减去
g_mcentral->ReturnSpan(span, size_class);
}请注意，上述代码中的MCachedSpanManager是TCMalloc中ThreadCache或PerCpuCache的概念简化。实际的TCMalloc会更复杂，例如它可能会维护一个“批量”的空闲对象列表，每次从mspan取一批对象到mcache的局部列表，然后从局部列表快速分配，以进一步减少对mspan的直接访问。
mcentral：全局协调者与碎片整理
mcentral是TCMalloc架构的中央枢纽，扮演着“协调者”的角色。它负责在各个mcache和底层的全局页堆之间平衡mspan的分配与回收。
1. mcentral的定义与目的
mcentral是TCMalloc中唯一的全局组件，因此对它的访问是需要锁保护的。但是，由于mcache的存在，mcentral的锁竞争频率远低于传统全局堆。
目的：
- 平衡负载：当一个
mcache需要新的mspan时，mcentral提供；当mcache有空闲mspan时，mcentral接收。 - 集中管理
mspan：维护所有mspan的状态，包括哪些mspan有空闲对象（可供mcache使用），哪些mspan已被mcache取走并已满，以及哪些mspan已完全空闲。 - 碎片整理与回收：当
mspan完全空闲时，mcentral尝试将它们与相邻的空闲mspan合并，形成更大的连续页块，并最终将这些页块返还给全局页堆，甚至操作系统，从而有效减少外部碎片。 - 分配新页：当没有可用的
mspan时，mcentral会向全局页堆请求新的原始内存页。
2. mcentral的结构与属性
mcentral的核心数据结构是针对每个size_class维护的两组mspan链表：
| 属性名称 | 类型 | 描述 |
|---|---|---|
nonempty_spans |
SpanList[] |
一个SpanList数组，每个元素对应一个size_class。列表中的mspan都至少有一个空闲对象，可以提供给mcache。 |
empty_spans |
SpanList[] |
一个SpanList数组，每个元素对应一个size_class。列表中的mspan都被mcache取走，并且目前已无空闲对象（从mcentral的视角看）。当mcache有对象返还到这些mspan时，它们可能被移回nonempty_spans。 |
lock |
SpinLock 或 Mutex |
保护mcentral内部数据结构的一致性，防止多线程同时修改。 |
3. mcentral与mcache的交互流程
mcache请求mspan：当mcache需要一个mspan时，它会调用mcentral的GetSpanForSizeClass方法。mcentral首先检查对应size_class的nonempty_spans列表。- 如果找到一个
mspan，mcentral会将其从nonempty_spans中移除，并添加到empty_spans中（因为这个mspan现在被mcache完全持有，从mcentral的角度看，它暂时“空”了，直到mcache将对象释放回它）。然后将这个mspan返回给mcache。 - 如果没有可用的
nonempty_spans，mcentral会向全局页堆请求新的内存页，初始化一个新的mspan，将其细分为小对象，然后将其添加到empty_spans并返回给mcache。
mcache返还mspan：当mcache中的一个mspan变得空闲（部分空闲或完全空闲）时，它会调用mcentral的ReturnSpan方法。mcentral首先将该mspan从其empty_spans列表中移除（如果它在那里）。- 如果
mspan现在是部分空闲（num_free_objects > 0），它会被添加到nonempty_spans列表中，以便将来可以被其他mcache使用。 - 如果
mspan现在是完全空闲（IsFullyFree()为真），mcentral会尝试将其与相邻的空闲mspan进行合并。合并后形成更大的连续空闲页块，这些页块可能会被返还给全局页堆。
4. 概念代码示例：mcentral结构与核心逻辑
#include <mutex> // For std::mutex or similar lock
// 假设我们有一个全局的 PageHeap 实例用于获取和返还页
class PageHeap {
public:
Span* AllocatePages(size_t num_pages) {
// 模拟从操作系统获取页面
static char* mock_memory = new char[1024 * 1024 * 10]; // 10MB mock heap
static size_t current_offset = 0;
if (current_offset + num_pages * kPageSize > 1024 * 1024 * 10) {
return nullptr; // 模拟内存不足
}
void* allocated_addr = mock_memory + current_offset;
current_offset += num_pages * kPageSize;
Span* new_span = new Span(); // 实际TCMalloc会从SpanPool中获取
new_span->start_address = allocated_addr;
new_span->num_pages = num_pages;
// 注意：这里没有初始化size_class和对象，这在MCentral中完成
std::cout << "PageHeap: Allocated " << num_pages << " pages at " << allocated_addr << std::endl;
return new_span;
}
void ReleasePages(Span* span) {
// 模拟将页返还给操作系统
std::cout << "PageHeap: Released " << span->num_pages << " pages at " << span->start_address << std::endl;
// 实际的PageHeap会有复杂的逻辑来合并和管理空闲页
delete span; // 模拟释放Span对象本身
}
// 实际的PageHeap会有一个复杂的结构（如buddy allocator）来管理不同大小的页块
};
extern PageHeap g_page_heap; // 全局页堆实例
// SpanList 用于管理 Span 链表
struct SpanList {
Span* head;
Span* tail;
int count;
SpanList() : head(nullptr), tail(nullptr), count(0) {}
void PushFront(Span* s) {
s->next = head;
s->prev = nullptr;
if (head) {
head->prev = s;
}
head = s;
if (!tail) {
tail = s;
}
count++;
}
Span* PopFront() {
if (!head) return nullptr;
Span* s = head;
head = head->next;
if (head) {
head->prev = nullptr;
} else {
tail = nullptr;
}
s->next = nullptr;
s->prev = nullptr;
count--;
return s;
}
void Remove(Span* s) {
if (!s) return;
if (s->prev) {
s->prev->next = s->next;
} else {
head = s->next;
}
if (s->next) {
s->next->prev = s->prev;
} else {
tail = s->prev;
}
s->next = nullptr;
s->prev = nullptr;
count--;
}
};
// MCentral 结构体定义
class MCentral {
public:
static MCentral* GetInstance() {
static MCentral instance;
return &instance;
}
SpanList nonempty_spans[kNumSizeClasses]; // 有空闲对象的 Span 列表
SpanList empty_spans[kNumSizeClasses]; // 已完全分配（被 MCache 取走）的 Span 列表
std::mutex lock; // 保护 MCentral 的操作
MCentral() {} // 构造函数
// 由 MCache 调用，获取一个 Span
Span* GetSpanForSizeClass(int size_class);
// 由 MCache 调用，返还一个 Span (部分空闲或完全空闲)
void ReturnSpan(Span* span, int size_class);
private:
// 辅助函数：从 PageHeap 获取新页并初始化 Span
Span* FetchNewPages(int size_class);
};
// MCentral 的全局实例指针
MCentral* g_mcentral = MCentral::GetInstance();
Span* MCentral::GetSpanForSizeClass(int size_class) {
std::lock_guard<std::mutex> guard(lock); // 加锁保护
Span* span = nonempty_spans[size_class].PopFront();
if (span) {
// 找到一个有空闲对象的 Span，将其移到 empty_spans 列表
// 因为它现在被 MCache 取走了，从 MCentral 角度看是“空”的
empty_spans[size_class].PushFront(span);
std::cout << "MCentral: Provided existing span " << span->start_address
<< " (size_class " << size_class << ") from nonempty list." << std::endl;
} else {
// 没有可用的 Span，需要从 PageHeap 获取新页
span = FetchNewPages(size_class);
if (span) {
// 新 Span 默认所有对象都是空闲的，但它现在被 MCache 取走，所以也放到 empty_spans
empty_spans[size_class].PushFront(span);
std::cout << "MCentral: Provided new span " << span->start_address
<< " (size_class " << size_class << ") from new pages." << std::endl;
} else {
std::cerr << "MCentral: Failed to fetch new pages for size_class " << size_class << std::endl;
}
}
return span;
}
void MCentral::ReturnSpan(Span* span, int size_class) {
std::lock_guard<std::mutex> guard(lock); // 加锁保护
// 首先从 empty_spans 列表中移除，因为它可能之前在那里
empty_spans[size_class].Remove(span);
if (span->IsFullyFree()) {
// Span 完全空闲，尝试合并并返还给 PageHeap
// 这一步在实际TCMalloc中非常复杂，涉及查找相邻的Span，检查它们的空闲状态，
// 合并，然后将合并后的Span（如果足够大）返还给PageHeap。
// 为了简化，这里直接返还给 PageHeap。
std::cout << "MCentral: Span " << span->start_address
<< " fully free, returning to PageHeap." << std::endl;
g_page_heap.ReleasePages(span);
// 在实际TCMalloc中，这里会将其添加到PageHeap的空闲页列表中，而不是直接删除
} else {
// Span 仍然部分空闲，将其放回 nonempty_spans 列表
nonempty_spans[size_class].PushFront(span);
std::cout << "MCentral: Span " << span->start_address
<< " partially free, returned to nonempty list." << std::endl;
}
}
// 获取页数的逻辑，实际TCMalloc会根据size_class和系统页大小计算
// 例如，对于8字节对象，可能一个4KB页能分512个对象，
// 但对于2048字节对象，一个4KB页只能分2个对象。
// 为了减少与MCentral的交互，通常会一次性为mcache提供包含多个对象的span。
// 这里简化为总是请求一个页，然后根据size_class细分
Span* MCentral::FetchNewPages(int size_class) {
// 实际TCMalloc会根据 size_class 和当前的 Span 需求，计算需要多少页。
// 例如，对于非常小的对象，一次可能请求4个页，以提供更多对象。
// 对于较大的对象，可能只请求1个或2个页。
size_t pages_to_request = 1; // 简化为总是请求1页
size_t obj_size = GetSizeForSizeClass(size_class);
if (obj_size == 0) return nullptr; // 无效的大小类
// 考虑一个批次能提供多少对象，来确定请求多少页
// 例如，对于小对象，我们希望一个span能提供至少16个对象给mcache
size_t desired_objects_per_span = 16;
if (obj_size > 256) desired_objects_per_span = 4; // 大对象批次小一点
if (obj_size > 1024) desired_objects_per_span = 1; // 接近一页的对象，1个就好
pages_to_request = (desired_objects_per_span * obj_size + kPageSize - 1) / kPageSize;
if (pages_to_request == 0) pages_to_request = 1; // 至少1页
Span* new_span = g_page_heap.AllocatePages(pages_to_request);
if (new_span) {
new_span->Init(new_span->start_address, new_span->num_pages, size_class);
// 在实际TCMalloc中，这里会将新span的页范围注册到全局页映射中
// GetPageMap()->RegisterSpan(new_span);
}
return new_span;
}
// MCentral 的全局实例指针 (需在 main 函数或全局作用域初始化)
// MCentral* g_mcentral = MCentral::GetInstance();
// PageHeap g_page_heap; // 全局页堆实例mcentral的合并逻辑是其复杂且高效的关键部分。当一个mspan完全空闲并返回给mcentral时，mcentral不会立即将其返还给全局页堆。相反，它会检查这个mspan的虚拟地址相邻的mspan是否也处于完全空闲状态。如果相邻的mspan也是空闲的，并且它们可以合并成一个更大的连续页块，那么mcentral就会执行合并操作。合并后的更大的mspan会被返还给全局页堆，从而减少外部碎片，并为将来分配大对象提供更大的连续内存块。这种策略被称为“伙伴系统”（Buddy System）或者类似的页管理算法。
Page Map：指针到Span的快速映射
在TCMalloc中，当一个对象被释放时，我们只知道它的地址，但需要知道它属于哪个mspan才能正确地将其归还。这就是Page Map的作用。
1. Page Map的目的
- 快速查找
mspan：给定任意一个由TCMalloc分配的内存地址，能够以O(1)或O(logN)的时间复杂度，快速找到该地址所属的mspan结构。 - 支持回收：这是
mcache或mcentral能够正确回收对象到其对应mspan的关键机制。
2. Page Map的实现方式
Page Map通常是一个全局的数据结构，它将内存地址映射到mspan指针。由于内存地址空间可能非常稀疏，直接使用一个巨大的数组是不切实际的。TCMalloc通常采用以下策略：
- 多级数组（Radix Tree / 基数树）：这是一种分层的数据结构，通过将虚拟地址分解为多个部分，逐级查找来定位到对应的
mspan。例如，一个64位地址可以分为几段，每段用作数组索引。 - 页粒度映射：
Page Map并不映射每个字节，而是映射每个内存页的起始地址。这意味着，如果一个mspan管理了N个页，那么这N个页的起始地址都会在Page Map中指向同一个mspan结构。
当mcentral从全局页堆获取到一个新的mspan（即一段连续的内存页）时，它会将这个mspan的页范围注册到Page Map中。
3. 概念代码示例：PageMap
// 假设虚拟地址空间是 48 位（常见于64位系统），页大小 4KB
// 那么页号大约是 2^36
// 一个简单的多级页映射 (Radix Tree 简化版)
// 假设我们只关心一个较小的虚拟地址范围，例如 0x0 - 0x100000000 (4GB)
// 1024 * 1024 pages.
// 实际的 PageMap 是非常复杂的，这里仅作概念性示意
class PageMap {
public:
static PageMap* GetInstance() {
static PageMap instance;
return &instance;
}
// 简单数组映射，只适用于小范围连续地址空间
// 实际TCMalloc会用更复杂的结构，如多级页表或Radix Tree
Span** map_array;
size_t max_pages_to_map;
PageMap() {
// 假设我们映射 1GB 内存，即 1GB / 4KB = 256K 页
max_pages_to_map = (1ULL << 30) / kPageSize; // 1GB / 4KB
map_array = new Span*[max_pages_to_map]{nullptr};
}
~PageMap() {
delete[] map_array;
}
// 将物理地址对齐到页边界
static void* GetPageStart(void* ptr) {
return (void*)((uintptr_t)ptr & ~(kPageSize - 1));
}
// 获取页号
static size_t GetPageNumber(void* page_addr) {
// 假设我们从 0 地址开始映射
return (uintptr_t)page_addr / kPageSize;
}
// 注册 Span
void RegisterSpan(Span* s) {
if (!s || !s->start_address || s->num_pages == 0) return;
size_t start_page_num = GetPageNumber(GetPageStart(s->start_address));
for (size_t i = 0; i < s->num_pages; ++i) {
size_t current_page_num = start_page_num + i;
if (current_page_num < max_pages_to_map) {
map_array[current_page_num] = s;
} else {
std::cerr << "PageMap: Warning, cannot register page " << current_page_num
<< ", out of mapped range." << std::endl;
}
}
std::cout << "PageMap: Registered span " << s->start_address << " for " << s->num_pages << " pages." << std::endl;
}
// 查找 Span
Span* LookupSpan(void* ptr) {
if (!ptr) return nullptr;
size_t page_num = GetPageNumber(GetPageStart(ptr));
if (page_num < max_pages_to_map) {
return map_array[page_num];
}
return nullptr;
}
};
// 全局 PageMap 实例
PageMap* g_page_map = PageMap::GetInstance();
// 重新定义 GetSpanForPointer 使用 PageMap
Span* GetSpanForPointer(void* ptr) {
return g_page_map->LookupSpan(ptr);
}
// 需要在 MCentral::FetchNewPages 中调用 PageMap::RegisterSpan
// 在 FetchNewPages 函数的末尾添加：
/*
Span* MCentral::FetchNewPages(int size_class) {
// ... (现有代码) ...
if (new_span) {
new_span->Init(new_span->start_address, new_span->num_pages, size_class);
g_page_map->RegisterSpan(new_span); // 注册到 PageMap
}
return new_span;
}
*/在实际的TCMalloc中，PageMap的实现会更加精妙和健壮，例如通过使用一个基于多级页表的Radix Tree结构，能够高效地处理稀疏和巨大的虚拟地址空间，同时保持查找性能接近O(1)。
Size Classes：内存分配的粒度
TCMalloc成功减少内存碎片的一个关键策略是“大小分类”（Size Classing）。它不像传统的malloc那样为每个精确的请求大小分配一个块，而是将请求大小向上取整到预定义的一组固定大小。
1. 动机
- 减少内部碎片：通过选择合适的大小类，可以最小化四舍五入带来的浪费。
- 简化管理：每个
mspan都只管理一种大小类的对象，这大大简化了mspan的内部管理逻辑。 - 提高重用率：相同大小类的对象可以互相重用，提高了内存池的利用率。
2. 工作原理
当应用程序请求N字节内存时，TCMalloc会将其向上取整到最接近且不小于N的预定义size_class。例如，TCMalloc可能有8字节、16字节、32字节等大小类。如果请求10字节，它会被分配到16字节的大小类。
3. 典型的Size Class分布
TCMalloc通常会定义几十个到上百个大小类，它们的分布并非均匀的，而是按照一定的步长或增长因子递增。
- 小对象（Small Objects）：通常步长较小（例如8字节或16字节），覆盖从几字节到几百字节的范围。这是为了尽量减少小对象的内部碎片，因为小对象数量最多。
- 中等对象（Medium Objects）：步长逐渐增大，覆盖几百字节到几十甚至几百KB的范围。
- 大对象（Large Objects）：超过某个阈值（例如256KB或1MB）的对象，TCMalloc会直接从全局页堆分配连续的原始内存页，而不经过
mspan的细分过程。这些对象通常被视为一个特殊的size_class，直接对应一个或多个完整的页。
示例大小类表格：
| 请求大小范围 (bytes) | 分配大小 (bytes) | 对应大小类ID (示例) | 每页可容纳对象数 (基于4KB页) |
|---|---|---|---|
| 1 – 8 | 8 | 0 | 512 |
| 9 – 16 | 16 | 1 | 256 |
| 17 – 32 | 32 | 2 | 128 |
| 33 – 64 | 64 | 3 | 64 |
| 65 – 128 | 128 | 4 | 32 |
| 129 – 256 | 256 | 5 | 16 |
| 257 – 512 | 512 | 6 | 8 |
| 513 – 1024 | 1024 | 7 | 4 |
| 1025 – 2048 | 2048 | 8 | 2 |
| 2049 – 4096 | 4096 | 9 | 1 |
| 4097 – 8192 | 8192 (2页) | 10 | 1 |
| … | … | … | … |
| > 256KB | N * kPageSize | (特殊处理) | 1 (多页) |
GetSizeForSizeClass和GetSizeClass这两个辅助函数正是实现这种映射的关键。
全局页堆（Page Heap）：原始内存的最终来源
虽然mspan、mcache和mcentral构成了TCMalloc的核心，但它们仍然需要一个底层的机制来从操作系统获取和管理大块的原始内存页。这就是全局页堆（Page Heap）的角色。
1. 角色与职责
- 与操作系统交互：负责通过
mmap或sbrk等系统调用，从操作系统申请或释放大块连续的虚拟内存。 - 管理大块空闲页：维护一个内部数据结构，用于跟踪和管理所有空闲的内存页块。
- 提供连续页块：当
mcentral需要新的mspan时，它会向全局页堆请求一个或多个连续的内存页。 - 合并和回收：当
mcentral返还完全空闲的mspan时，全局页堆会尝试将这些mspan（页块）与已有的空闲页块合并，形成更大的连续空闲块，并在合适的时机将这些大块返还给操作系统，以减少物理内存的占用。
2. 常见实现
全局页堆通常采用伙伴系统（Buddy System）算法或其变种来实现。伙伴系统能够高效地进行内存块的分配、分裂和合并，以满足不同大小的请求，并有效地缓解外部碎片。
虽然全局页堆是TCMalloc架构不可或缺的一部分，但它的管理细节超出了mspan、mcache和mcentral的直接范畴。可以将其视为这些核心组件的更底层支持。
TCMalloc架构的优势与考量
理解了mspan、mcache和mcentral的协同工作原理，我们就能总结TCMalloc架构的显著优势：
优势：
- 极高的分配速度：对于小对象，
mcache提供了无锁的O(1)分配路径，这是其性能卓越的核心原因。 - 优异的并发性能：线程局部缓存将大部分内存操作本地化，显著减少了全局锁竞争。
- 显著减少内存碎片：
- 内部碎片：通过大小分类，将内部碎片控制在可接受的范围内。
- 外部碎片：
mcentral和全局页堆的合并策略能够有效整合空闲页块，减少外部碎片。
- 良好的缓存局部性：线程倾向于从自己的
mcache中获取内存，使得相关数据通常分配在物理上更接近的区域。 - 可扩展性：能够很好地扩展到多核和高并发环境。
考量与挑战：
- 内存开销：每个线程都拥有一个
mcache，即使线程不活跃，也会占用一定的内存。如果线程数量非常多，这可能导致较高的内存开销。 - 复杂性：相比简单的全局堆，TCMalloc的设计和实现更为复杂，维护成本也更高。
- 大对象处理：TCMalloc主要优化小对象和中等对象的分配。对于大对象，它通常直接委托给全局页堆，其性能优势相对不明显。
- 跨线程所有权转移：如果一个线程分配的内存被另一个线程释放，这需要通过
Page Map查找mspan，然后将对象归还到mspan。虽然可行，但相对于线程内部的分配和释放，会稍微慢一些。
总结
TCMalloc通过引入mspan、mcache和mcentral这三个核心组件，巧妙地构建了一个分层、并发且高效的内存分配系统。mspan作为内存块的基本管理单元，mcache提供无锁的线程局部快速分配，而mcentral则作为全局协调者，平衡mspan并执行碎片整理。这种设计理念不仅显著提升了多线程应用的性能和可扩展性，也为后续的现代内存分配器（如jemalloc和Go语言运行时分配器）奠定了基础，是高性能系统设计中不可或缺的宝贵经验。