内存池实现
1. 项目介绍
项目名称:memory-pool
项目地址:https://github.com/wunaiqiezixin/memory-pool
什么是内存池 ?
- 内存池是一种预分配内存并进行重复利用的技术,通过减少频繁的动态内存分配和释放操作,从而提高程序的运行效率。
- 内存池会预先向操作系统申请一大块内存区域,并将其划分为多个小块,当需要分配内存时,直接中这些小块中划分,而不是调用系统的动态内存分配函数(比如new/delete)
- 简而言之,内存池会申请一大块内存,之后将这块内存的管理放到应用层执行,减少系统调用带来的开销
为什么要做内存池 ?
性能优化:
- 减少动态内存分配的开销: 系统调用 (
malloc/free new/delete) 涉及复杂的内存管理操作(内存查找、碎片整理等),导致性能较低,而内存池通过预分配操作和简单的内存管理逻辑显著提高了内存的分配和释放效率。 - 避免内存碎片: 动态内存分配会产生内存碎片,尤其是在大量小对象频繁地分配和释放的场景中,导致的后果就是:当程序长时间运行时,由于所申请的内存块的大小不确定,频繁使用时会造成大量的内存碎片从而降低程序和操作系统的性能。内存池通过管理固定大小的内存块可以有效避免内存碎片化。
- 降低系统调用频率: 系统级内存分配(如
malloc)会进入内核态,频繁地调用会有很大的内存开销,内存池通过减少系统调用的次数,有效地提高程序效率。
确定性(实时性)
- 稳定的分配时间: 使用内存池可以使分配和释放操作的耗时更加可控和稳定,适合实时性用严格要求的系统。
内存池的应用场景
高频小对象的分配
- 游戏开发: 游戏中的大量小对象(如:子弹、粒子、NPC)的动态内存分配和释放操作非常的频繁,用内存池可以显著地优化性能。
- 网络编程: 在网络编程中,大量的请求和响应对象(如消息报文)的频繁创建和销毁非常适合使用内存池。
- 内存管理库: 一些容器或数据结构(std::vector std::deque等)内部可以使用内存池优化内存分配的性能。
实时系统
- 嵌入式设备或实时控制系统中,动态内存分配的延迟可以影响实时性,而使用内存池可以提供确定性的内存分配性能。
高性能计算
- 在高性能计算程序中,频繁地动态内存分配和释放操作会拖累整个程序的性能,而使用内存池可以优化内存管理。
服务器开发
- 数据库服务器、web服务器需要处理大量连接和请求,这些连接涉及大量内存分配,内存池可以有效提升服务。
内存池在代码中的应用
- 对动态分配内存的系统调用(
malloc/free new/delete)进行替换 - 对STL众多容器中的内存分配器(
std::allocator)进行替换
内存池的缺点
- 初始内存占用: 使用内存池需要预先分配一块较大的内存区域,可能造成部分内存浪费。
- 复杂性: 实现和调试内存池代码比直接调用
new/delete复杂得多。 - 不适合大对象的内存分配: 对于大对象,使用内存池分配内存可能并不划算。
项目整体介绍
这个项目实现了一个高效的内存池,旨在优化内存分配和释放的性能,特别是在多线程环境下。内存池通过分层缓存架构来管理内存,主要包括以下三层:
- ThreadCache(线程本地缓存)
每个线程独立的内存缓存
无锁操作,快速分配和释放
减少线程间竞争,提高并发性能
- CentralCache(中心缓存)
管理多个线程共享的内存块
通过自旋锁保护,确保线程安全
批量从PageCache获取内存,分配给ThreadCache
- PageCache(页缓存)
从操作系统获取大块内存
将大块内存切分成小块,供CentralCache使用
负责内存的回收和再利用
执行流程
+-------------------+
| 应用请求内存 |
+-------------------+
|
v
+-------------------+
| ThreadCache |
|-------------------|
| 检查本地缓存 |
| 有:直接分配 |
| 无:请求Central |
+-------------------+
|
v
+-------------------+
| CentralCache |
|-------------------|
| 检查共享缓存 |
| 有:分配给Thread |
| 无:请求Page |
+-------------------+
|
v
+-------------------+
| PageCache |
|-------------------|
| 从操作系统获取 |
| 切分成小块 |
| 返回给Central |
+-------------------+
线程本地缓存(ThreadCache)
1. ThreadCache的定义:
#pragma once
#include "Common.h"
namespace memoryPool
{
// 线程本地缓存
class ThreadCache
{
public:
//单例模式
static ThreadCache* getInstance()
{
static thread_local ThreadCache instance;
return &instance;
}
void* allocate(size_t size);
void deallocate(void* ptr, size_t size);
private:
ThreadCache()
{
// 初始化自由链表和大小统计
freeList_.fill(nullptr);
freeListSize_.fill(0);
}
// 从中心缓存获取内存
void* fetchFromCentralCache(size_t index);
// 归还内存到中心缓存
void returnToCentralCache(void* start, size_t size);
bool shouldReturnToCentralCache(size_t index);
private:
// 每个线程的自由链表数组
std::array<void*, FREE_LIST_SIZE> freeList_;
std::array<size_t, FREE_LIST_SIZE> freeListSize_; // 自由链表大小统计
};
} // namespace memoryPool
关键设计点
- 使用thread_local确保每个线程独立实例
- 自由链表数组管理不同大小的内存块
- 单例模式简化访问
2. 内存分配的实现:
申请一块大小为size的内存:
如果size > MAX_BYTES,直接进行系统调用(malloc)
不然直接从线程本地自由链表分配(线程安全),
如果线程本地自由链表为空,再向中心缓存申请
void* ThreadCache::allocate(size_t size)
{
// 处理0大小的分配请求
if (size == 0)
{
size = ALIGNMENT; // 至少分配一个对齐大小
}
if (size > MAX_BYTES)
{
// 大对象直接从系统分配
return malloc(size);
}
size_t index = SizeClass::getIndex(size);
// 更新对应自由链表的长度计数
freeListSize_[index]--;
// 检查线程本地自由链表
// 如果 freeList_[index] 不为空,表示该链表中有可用内存块
if (void* ptr = freeList_[index])
{
freeList_[index] = *reinterpret_cast<void**>(ptr); // 将freeList_[index]指向的内存块的下一个内存块地址(取决于内存块的实现)
return ptr;
}
// 如果线程本地自由链表为空,则从中心缓存获取一批内存
return fetchFromCentralCache(index);
}
优势:
- 快速路径:直接从自由链表分配
- 无锁操作:线程本地访问
- 分级处理:大小内存分开处理
3. 向中心缓存申请内存
当对应的线程本地自由链表(index)为空时,
此时需要向中心缓存申请内存(调用接口fetchRange(size_t index))
将第一块内存返回,并将其余内存块放入空闲链表
这里batchNum仍然时申请到的内存块的总数量,因为在allocate()中会更新
void* ThreadCache::fetchFromCentralCache(size_t index)
{
// 从中心缓存批量获取内存
void* start = CentralCache::getInstance().fetchRange(index);
if (!start) return nullptr;
// 取一个返回,其余放入自由链表
void* result = start;
freeList_[index] = *reinterpret_cast<void**>(start);
// 更新自由链表大小
size_t batchNum = 0;
void* current = start; // 从start开始遍历
// 计算从中心缓存获取的内存块数量
while (current != nullptr)
{
batchNum++;
current = *reinterpret_cast<void**>(current); // 遍历下一个内存块
}
// 更新freeListSize_,增加获取的内存块数量
freeListSize_[index] += batchNum;
return result;
}
设计考虑
- 批量获取:一次性从中心缓存中获取一定数量的对应大小内存块存入线程本地缓存的自由链表中管理,以减少与中心缓存的交互。
- 链表管理:将从中心缓存中获取的批量空闲内存块,用对应index的自由链表来维护。
- 延迟加载:按需从中心缓存获取。
4. 内存释放实现
将内存块插入线程本地自由链表头部即可
void ThreadCache::deallocate(void* ptr, size_t size)
{
if (size > MAX_BYTES)
{
free(ptr);
return;
}
size_t index = SizeClass::getIndex(size);
// 插入到线程本地自由链表
*reinterpret_cast<void**>(ptr) = freeList_[index];
freeList_[index] = ptr;
// 更新对应自由链表的长度计数
freeListSize_[index]++;
// 判断是否需要将部分内存回收给中心缓存
if (shouldReturnToCentralCache(index))
{
returnToCentralCache(freeList_[index], size);
}
}
特点:
- 快速释放:直接插入线程本地缓存对应链表头部
- 无锁操作:提高并发性能
- 内存复用:减少系统调用
5. 将内存归还给中心缓存
当用户调用deallocate时,如果对应的线程本地自由链表的内存块数量超过了阈值,就会将部分的内存块连成一个链表归还给中心缓存。
这使得能够让每一个线程本地缓存的内存块数量平衡。
void ThreadCache::returnToCentralCache(void* start, size_t size)
{
// 根据大小计算对应的索引
size_t index = SizeClass::getIndex(size);
// 获取对齐后的实际块大小
size_t alignedSize = SizeClass::roundUp(size);
// 计算要归还内存块数量
size_t batchNum = freeListSize_[index];
if (batchNum <= 1) return; // 如果只有一个块,则不归还
// 保留一部分在ThreadCache中(比如保留1/4)
size_t keepNum = std::max(batchNum / 4, size_t(1));
size_t returnNum = batchNum - keepNum;
// 将内存块串成链表
char* current = static_cast<char*>(start);
// 使用对齐后的大小计算分割点
char* splitNode = current;
for (size_t i = 0; i < keepNum - 1; ++i)
{
splitNode = reinterpret_cast<char*>(*reinterpret_cast<void**>(splitNode));
if (splitNode == nullptr)
{
// 如果链表提前结束,更新实际的返回数量
returnNum = batchNum - (i + 1);
break;
}
}
if (splitNode != nullptr)
{
// 将要返回的部分和要保留的部分断开
void* nextNode = *reinterpret_cast<void**>(splitNode);
*reinterpret_cast<void**>(splitNode) = nullptr; // 断开连接
// 更新ThreadCache的空闲链表
freeList_[index] = start;
// 更新自由链表大小
freeListSize_[index] = keepNum;
// 将剩余部分返回给CentralCache
if (returnNum > 0 && nextNode != nullptr)
{
//调用接口
CentralCache::getInstance().returnRange(nextNode, returnNum * alignedSize, index);
}
}
}
6. 为什么这样实现
- 性能优化
a. thread_local避免了线程间同步
b. 自由链表提供O(1)的分配和释放
c. 批量操作减少系统调用 - 内存管理
a. 按大小分类管理,减少碎片
b. 本地缓存提高复用率
c. 分级结构便于拓展 - 并发处理
a. 无锁设计提高并发性能
b. 线程隔离减少竞争
7. 内存池中的作用
作为第一级缓存,处理最频繁的内存请求
- 减轻中心缓存的压力
- 提供快速的内存分配和释放
- 优化多线程性能
这种实现方式使得ThreadCache成为了内存池的性能保证,特别适合:
- 频繁的小内存分配/释放
- 多线程高并发场景
- 对延迟敏感的应用
- 需要高性能的系统
ThradCache完整实现:
- ThreadCache.h
#pragma once
#include "Common.h"
namespace memoryPool
{
// 线程本地缓存
class ThreadCache
{
public:
static ThreadCache* getInstance()
{
static thread_local ThreadCache instance;
return &instance;
}
void* allocate(size_t size);
void deallocate(void* ptr, size_t size);
private:
ThreadCache()
{
// 初始化自由链表和大小统计
freeList_.fill(nullptr);
freeListSize_.fill(0);
}
// 从中心缓存获取内存
void* fetchFromCentralCache(size_t index);
// 归还内存到中心缓存
void returnToCentralCache(void* start, size_t size);
bool shouldReturnToCentralCache(size_t index);
private:
// 每个线程的自由链表数组
std::array<void*, FREE_LIST_SIZE> freeList_;
std::array<size_t, FREE_LIST_SIZE> freeListSize_; // 自由链表大小统计
};
} // namespace memoryPool
- ThreadCache.cpp
#include "../include/ThreadCache.h"
#include "../include/CentralCache.h"
namespace memoryPool
{
void* ThreadCache::allocate(size_t size)
{
// 处理0大小的分配请求
if (size == 0)
{
size = ALIGNMENT; // 至少分配一个对齐大小
}
if (size > MAX_BYTES)
{
// 大对象直接从系统分配
return malloc(size);
}
size_t index = SizeClass::getIndex(size);
// 更新对应自由链表的长度计数
freeListSize_[index]--;
// 检查线程本地自由链表
// 如果 freeList_[index] 不为空,表示该链表中有可用内存块
if (void* ptr = freeList_[index])
{
freeList_[index] = *reinterpret_cast<void**>(ptr); // 将freeList_[index]指向的内存块的下一个内存块地址(取决于内存块的实现)
return ptr;
}
// 如果线程本地自由链表为空,则从中心缓存获取一批内存
return fetchFromCentralCache(index);
}
void ThreadCache::deallocate(void* ptr, size_t size)
{
if (size > MAX_BYTES)
{
free(ptr);
return;
}
size_t index = SizeClass::getIndex(size);
// 插入到线程本地自由链表
*reinterpret_cast<void**>(ptr) = freeList_[index];
freeList_[index] = ptr;
// 更新对应自由链表的长度计数
freeListSize_[index]++;
// 判断是否需要将部分内存回收给中心缓存
if (shouldReturnToCentralCache(index))
{
returnToCentralCache(freeList_[index], size);
}
}
// 判断是否需要将内存回收给中心缓存
bool ThreadCache::shouldReturnToCentralCache(size_t index)
{
// 设定阈值,例如:当自由链表的大小超过一定数量时
size_t threshold = 256;
return (freeListSize_[index] > threshold);
}
void* ThreadCache::fetchFromCentralCache(size_t index)
{
// 从中心缓存批量获取内存
void* start = CentralCache::getInstance().fetchRange(index);
if (!start) return nullptr;
// 取一个返回,其余放入自由链表
void* result = start;
freeList_[index] = *reinterpret_cast<void**>(start);
// 更新自由链表大小
size_t batchNum = 0;
void* current = start; // 从start开始遍历
// 计算从中心缓存获取的内存块数量
while (current != nullptr)
{
batchNum++;
current = *reinterpret_cast<void**>(current); // 遍历下一个内存块
}
// 更新freeListSize_,增加获取的内存块数量
freeListSize_[index] += batchNum;
return result;
}
void ThreadCache::returnToCentralCache(void* start, size_t size)
{
// 根据大小计算对应的索引
size_t index = SizeClass::getIndex(size);
// 获取对齐后的实际块大小
size_t alignedSize = SizeClass::roundUp(size);
// 计算要归还内存块数量
size_t batchNum = freeListSize_[index];
if (batchNum <= 1) return; // 如果只有一个块,则不归还
// 保留一部分在ThreadCache中(比如保留1/4)
size_t keepNum = std::max(batchNum / 4, size_t(1));
size_t returnNum = batchNum - keepNum;
// 将内存块串成链表
char* current = static_cast<char*>(start);
// 使用对齐后的大小计算分割点
char* splitNode = current;
for (size_t i = 0; i < keepNum - 1; ++i)
{
splitNode = reinterpret_cast<char*>(*reinterpret_cast<void**>(splitNode));
if (splitNode == nullptr)
{
// 如果链表提前结束,更新实际的返回数量
returnNum = batchNum - (i + 1);
break;
}
}
if (splitNode != nullptr)
{
// 将要返回的部分和要保留的部分断开
void* nextNode = *reinterpret_cast<void**>(splitNode);
*reinterpret_cast<void**>(splitNode) = nullptr; // 断开连接
// 更新ThreadCache的空闲链表
freeList_[index] = start;
// 更新自由链表大小
freeListSize_[index] = keepNum;
// 将剩余部分返回给CentralCache
if (returnNum > 0 && nextNode != nullptr)
{
CentralCache::getInstance().returnRange(nextNode, returnNum * alignedSize, index);
}
}
}
} // namespace memoryPool
中心缓存(CentralCache)
1. ThreadCache的定位和作用
// 使用无锁的span信息存储
struct SpanTracker {
std::atomic<void*> spanAddr{nullptr};
std::atomic<size_t> numPages{0};
std::atomic<size_t> blockCount{0};
std::atomic<size_t> freeCount{0}; // 用于追踪spn中还有多少块是空闲的,如果所有块都空闲,则归还span给PageCache
};
class CentralCache
{
public:
static CentralCache& getInstance()
{
static CentralCache instance;
return instance;
}
void* fetchRange(size_t index);
void returnRange(void* start, size_t size, size_t index);
private:
// 相互是还所有原子指针为nullptr
CentralCache();
// 从页缓存获取内存
void* fetchFromPageCache(size_t size);
// 获取span信息
SpanTracker* getSpanTracker(void* blockAddr);
// 更新span的空闲计数并检查是否可以归还
void updateSpanFreeCount(SpanTracker* tracker, size_t newFreeBlocks, size_t index);
private:
// 中心缓存的自由链表
std::array<std::atomic<void*>, FREE_LIST_SIZE> centralFreeList_;
// 用于同步的自旋锁
std::array<std::atomic_flag, FREE_LIST_SIZE> locks_;
// 使用数组存储span信息,避免map的开销
std::array<SpanTracker, 1024> spanTrackers_;
std::atomic<size_t> spanCount_{0};
// 延迟归还相关的成员变量
static const size_t MAX_DELAY_COUNT = 48; // 最大延迟计数
std::array<std::atomic<size_t>, FREE_LIST_SIZE> delayCounts_; // 每个大小类的延迟计数
std::array<std::chrono::steady_clock::time_point, FREE_LIST_SIZE> lastReturnTimes_; // 上次归还时间
static const std::chrono::milliseconds DELAY_INTERVAL; // 延迟间隔
bool shouldPerformDelayedReturn(size_t index, size_t currentCount, std::chrono::steady_clock::time_point currentTime);
void performDelayedReturn(size_t index);
};
主要作用:
- 作为ThreadCache和PageCache之间的中间层
- 管理从PageCache获取的内存块
- 为多个ThreadCache提供内存分配服务
- 实现内存的跨线程复用
2. 从中心缓存获取内存块并返回给线程本地缓存
中心缓存会一次性从页缓存获取SPAN_PAGES页的内存,并将其划分为小块放入中心缓存自由链表中
用一个SpanTracker结构体存放从页缓存获取到的内存的信息。
中心缓存会优先从中心缓存自由链表中获取一个内存块,
如果中心缓存自由链表为空,会向页缓存申请一次内存(至少是SPAN_PAGES页),将申请到的内存首内存返回给线程本地缓存,其余按size划分为多个小块并连成链表放入中心缓存自由链表。
只要是从页缓存申请的内存都要记录到spanTrackers数组中。
void* CentralCache::fetchRange(size_t index)
{
// 索引检查,当索引大于等于FREE_LIST_SIZE时,说明申请内存过大应直接向系统申请
if (index >= FREE_LIST_SIZE)
return nullptr;
// 自旋锁保护
while (locks_[index].test_and_set(std::memory_order_acquire))
{
std::this_thread::yield(); // 添加线程让步,避免忙等待,避免过度消耗CPU
}
void* result = nullptr;
try
{
// 尝试从中心缓存获取内存块
result = centralFreeList_[index].load(std::memory_order_relaxed);
if (!result)
{
// 如果中心缓存为空,从页缓存获取新的内存块
size_t size = (index + 1) * ALIGNMENT;
result = fetchFromPageCache(size);
if (!result)
{
locks_[index].clear(std::memory_order_release);
return nullptr;
}
// 将获取的内存块切分成小块
char* start = static_cast<char*>(result);
// 计算实际分配的页数
size_t numPages = (size <= SPAN_PAGES * PageCache::PAGE_SIZE) ?
SPAN_PAGES : (size + PageCache::PAGE_SIZE - 1) / PageCache::PAGE_SIZE;
// 使用实际页数计算块数
size_t blockNum = (numPages * PageCache::PAGE_SIZE) / size;
if (blockNum > 1)
{ // 确保至少有两个块才构建链表
for (size_t i = 1; i < blockNum; ++i)
{
void* current = start + (i - 1) * size;
void* next = start + i * size;
*reinterpret_cast<void**>(current) = next;
}
*reinterpret_cast<void**>(start + (blockNum - 1) * size) = nullptr;
// 保存result的下一个节点
void* next = *reinterpret_cast<void**>(result);
// 将result与链表断开
*reinterpret_cast<void**>(result) = nullptr;
// 更新中心缓存
centralFreeList_[index].store(
next,
std::memory_order_release
);
// 使用无锁方式记录span信息
// 做记录是为了将中心缓存多余内存块归还给页缓存做准备。考虑点:
// 1.CentralCache 管理的是小块内存,这些内存可能不连续
// 2.PageCache 的 deallocateSpan 要求归还连续的内存
size_t trackerIndex = spanCount_++;
if (trackerIndex < spanTrackers_.size())
{
spanTrackers_[trackerIndex].spanAddr.store(start, std::memory_order_release);
spanTrackers_[trackerIndex].numPages.store(numPages, std::memory_order_release);
spanTrackers_[trackerIndex].blockCount.store(blockNum, std::memory_order_release); // 共分配了blockNum个内存块
spanTrackers_[trackerIndex].freeCount.store(blockNum - 1, std::memory_order_release); // 第一个块result已被分配出去,所以初始空闲块数为blockNum - 1
}
}
}
else
{
// 保存result的下一个节点
void* next = *reinterpret_cast<void**>(result);
// 将result与链表断开
*reinterpret_cast<void**>(result) = nullptr;
// 更新中心缓存
centralFreeList_[index].store(next, std::memory_order_release);
// 更新span的空闲计数
SpanTracker* tracker = getSpanTracker(result);
if (tracker)
{
// 减少一个空闲块
tracker->freeCount.fetch_sub(1, std::memory_order_release);
}
}
}
catch (...)
{
locks_[index].clear(std::memory_order_release);
throw;
}
// 释放锁
locks_[index].clear(std::memory_order_release);
return result;
}
3. 将线程本地缓存多余的内存块归还给中心缓存
给线程本地缓存的一个调用接口
void CentralCache::returnRange(void* start, size_t size, size_t index)
{
if (!start || index >= FREE_LIST_SIZE)
return;
size_t blockSize = (index + 1) * ALIGNMENT;
size_t blockCount = size / blockSize;
while (locks_[index].test_and_set(std::memory_order_acquire))
{
std::this_thread::yield();
}
try
{
// 1. 将归还的链表连接到中心缓存
void* end = start;
size_t count = 1;
while (*reinterpret_cast<void**>(end) != nullptr && count < blockCount) {
end = *reinterpret_cast<void**>(end);
count++;
}
void* current = centralFreeList_[index].load(std::memory_order_relaxed);
*reinterpret_cast<void**>(end) = current; // 头插法(将原有链表接在归还链表后边)
centralFreeList_[index].store(start, std::memory_order_release);
// 2. 更新延迟计数
size_t currentCount = delayCounts_[index].fetch_add(1, std::memory_order_relaxed) + 1;
auto currentTime = std::chrono::steady_clock::now();
// 3. 检查是否需要执行延迟归还
if (shouldPerformDelayedReturn(index, currentCount, currentTime))
{
performDelayedReturn(index);
}
}
catch (...)
{
locks_[index].clear(std::memory_order_release);
throw;
}
locks_[index].clear(std::memory_order_release);
}
将ThreadCache中多余内存块归还给CentralCache之后,会进行检查是否需要归还内存块给PageCache。
这里的检查归还总体经过两层:
- 首先是returnRange调用次数(也就是ThreadCache归还内存给CentralCache次数)和时间的检查。
- 其次,还要保证CentralCache中要归还的空闲内存块能够拼成完整的内存页(如分配时的内存页一样)。
满足上述两个条件才将CentralCache中的对应空闲内存归还给PageCache。
// 检查是否需要执行延迟归还
bool CentralCache::shouldPerformDelayedReturn(size_t index, size_t currentCount,
std::chrono::steady_clock::time_point currentTime)
{
// 基于计数和时间的双重检查
if (currentCount >= MAX_DELAY_COUNT)
{
return true;
}
auto lastTime = lastReturnTimes_[index];
return (currentTime - lastTime) >= DELAY_INTERVAL;
}
// 执行延迟归还
void CentralCache::performDelayedReturn(size_t index)
{
// 重置延迟计数
delayCounts_[index].store(0, std::memory_order_relaxed);
// 更新最后归还时间
lastReturnTimes_[index] = std::chrono::steady_clock::now();
// 统计每个span的空闲块数
std::unordered_map<SpanTracker*, size_t> spanFreeCounts;
void* currentBlock = centralFreeList_[index].load(std::memory_order_relaxed);
while (currentBlock)
{
SpanTracker* tracker = getSpanTracker(currentBlock);
if (tracker)
{
spanFreeCounts[tracker]++;
}
currentBlock = *reinterpret_cast<void**>(currentBlock);
}
// 更新每个span的空闲计数并检查是否可以归还
for (const auto& [tracker, newFreeBlocks] : spanFreeCounts)
{
updateSpanFreeCount(tracker, newFreeBlocks, index);
}
}
void CentralCache::updateSpanFreeCount(SpanTracker* tracker, size_t newFreeBlocks, size_t index)
{
size_t oldFreeCount = tracker->freeCount.load(std::memory_order_relaxed);
size_t newFreeCount = oldFreeCount + newFreeBlocks;
tracker->freeCount.store(newFreeCount, std::memory_order_release);
// 如果所有块都空闲,归还span
if (newFreeCount == tracker->blockCount.load(std::memory_order_relaxed))
{
void* spanAddr = tracker->spanAddr.load(std::memory_order_relaxed);
size_t numPages = tracker->numPages.load(std::memory_order_relaxed);
// 从自由链表中移除这些块
void* head = centralFreeList_[index].load(std::memory_order_relaxed);
void* newHead = nullptr;
void* prev = nullptr;
void* current = head;
while (current)
{
void* next = *reinterpret_cast<void**>(current);
if (current >= spanAddr &&
current < static_cast<char*>(spanAddr) + numPages * PageCache::PAGE_SIZE)
{
if (prev)
{
*reinterpret_cast<void**>(prev) = next;
}
else
{
newHead = next;
}
}
else
{
prev = current;
}
current = next;
}
centralFreeList_[index].store(newHead, std::memory_order_release);
PageCache::getInstance().deallocateSpan(spanAddr, numPages);
}
}
4. 设计特点
- 批量管理
static const size_t SPAN_PAGES = 8; // 固定8页的批量申请
原因:
- 减少向PageCache的请求次数
- 提高内存分配效率
- 降低锁竞争
- 细粒度锁
- 减少线程竞争
- 提高并发性能
- 避免全局锁的性能瓶颈
5. 为什么这么设计
-
三级缓存的必要性
a. ThreadCache:无锁,快速分配
b. CentralCache:平衡点,内存复用
c. PageCache:系统对接,大块管理 -
批量处理的优势
a. 减少锁竞争
b. 提高缓存命中率
c. 降低系统调用开销 -
内存规格管理
size_t size = (index + 1) * ALIGNMENT; // 8字节对齐
原因:
- 减少内存碎片
- 提高内存利用率
- 简化管理逻辑
CentralCache完整实现
CentralCache.h
#pragma once
#include "Common.h"
#include <mutex>
#include <unordered_map>
#include <array>
#include <atomic>
#include <chrono>
namespace memoryPool
{
// 使用无锁的span信息存储
struct SpanTracker {
std::atomic<void*> spanAddr{nullptr};
std::atomic<size_t> numPages{0};
std::atomic<size_t> blockCount{0};
std::atomic<size_t> freeCount{0}; // 用于追踪spn中还有多少块是空闲的,如果所有块都空闲,则归还span给PageCache
};
class CentralCache
{
public:
static CentralCache& getInstance()
{
static CentralCache instance;
return instance;
}
void* fetchRange(size_t index);
void returnRange(void* start, size_t size, size_t index);
private:
// 相互是还所有原子指针为nullptr
CentralCache();
// 从页缓存获取内存
void* fetchFromPageCache(size_t size);
// 获取span信息
SpanTracker* getSpanTracker(void* blockAddr);
// 更新span的空闲计数并检查是否可以归还
void updateSpanFreeCount(SpanTracker* tracker, size_t newFreeBlocks, size_t index);
private:
// 中心缓存的自由链表
std::array<std::atomic<void*>, FREE_LIST_SIZE> centralFreeList_;
// 用于同步的自旋锁
std::array<std::atomic_flag, FREE_LIST_SIZE> locks_;
// 使用数组存储span信息,避免map的开销
std::array<SpanTracker, 1024> spanTrackers_;
std::atomic<size_t> spanCount_{0};
// 延迟归还相关的成员变量
static const size_t MAX_DELAY_COUNT = 48; // 最大延迟计数
std::array<std::atomic<size_t>, FREE_LIST_SIZE> delayCounts_; // 每个大小类的延迟计数
std::array<std::chrono::steady_clock::time_point, FREE_LIST_SIZE> lastReturnTimes_; // 上次归还时间
static const std::chrono::milliseconds DELAY_INTERVAL; // 延迟间隔
bool shouldPerformDelayedReturn(size_t index, size_t currentCount, std::chrono::steady_clock::time_point currentTime);
void performDelayedReturn(size_t index);
};
} // namespace memoryPool
CentralCache.cpp
#include "../include/CentralCache.h"
#include "../include/PageCache.h"
#include <cassert>
#include <thread>
#include <chrono>
namespace memoryPool
{
const std::chrono::milliseconds CentralCache::DELAY_INTERVAL{1000};
// 每次从PageCache获取span大小(以页为单位)
static const size_t SPAN_PAGES = 8;
CentralCache::CentralCache()
{
for (auto& ptr : centralFreeList_)
{
ptr.store(nullptr, std::memory_order_relaxed);
}
for (auto& lock : locks_)
{
lock.clear();
}
// 初始化延迟归还相关的成员变量
for (auto& count : delayCounts_)
{
count.store(0, std::memory_order_relaxed);
}
for (auto& time : lastReturnTimes_)
{
time = std::chrono::steady_clock::now();
}
spanCount_.store(0, std::memory_order_relaxed);
}
void* CentralCache::fetchRange(size_t index)
{
// 索引检查,当索引大于等于FREE_LIST_SIZE时,说明申请内存过大应直接向系统申请
if (index >= FREE_LIST_SIZE)
return nullptr;
// 自旋锁保护
while (locks_[index].test_and_set(std::memory_order_acquire))
{
std::this_thread::yield(); // 添加线程让步,避免忙等待,避免过度消耗CPU
}
void* result = nullptr;
try
{
// 尝试从中心缓存获取内存块
result = centralFreeList_[index].load(std::memory_order_relaxed);
if (!result)
{
// 如果中心缓存为空,从页缓存获取新的内存块
size_t size = (index + 1) * ALIGNMENT;
result = fetchFromPageCache(size);
if (!result)
{
locks_[index].clear(std::memory_order_release);
return nullptr;
}
// 将获取的内存块切分成小块
char* start = static_cast<char*>(result);
// 计算实际分配的页数
size_t numPages = (size <= SPAN_PAGES * PageCache::PAGE_SIZE) ?
SPAN_PAGES : (size + PageCache::PAGE_SIZE - 1) / PageCache::PAGE_SIZE;
// 使用实际页数计算块数
size_t blockNum = (numPages * PageCache::PAGE_SIZE) / size;
if (blockNum > 1)
{ // 确保至少有两个块才构建链表
for (size_t i = 1; i < blockNum; ++i)
{
void* current = start + (i - 1) * size;
void* next = start + i * size;
*reinterpret_cast<void**>(current) = next;
}
*reinterpret_cast<void**>(start + (blockNum - 1) * size) = nullptr;
// 保存result的下一个节点
void* next = *reinterpret_cast<void**>(result);
// 将result与链表断开
*reinterpret_cast<void**>(result) = nullptr;
// 更新中心缓存
centralFreeList_[index].store(
next,
std::memory_order_release
);
// 使用无锁方式记录span信息
// 做记录是为了将中心缓存多余内存块归还给页缓存做准备。考虑点:
// 1.CentralCache 管理的是小块内存,这些内存可能不连续
// 2.PageCache 的 deallocateSpan 要求归还连续的内存
size_t trackerIndex = spanCount_++;
if (trackerIndex < spanTrackers_.size())
{
spanTrackers_[trackerIndex].spanAddr.store(start, std::memory_order_release);
spanTrackers_[trackerIndex].numPages.store(numPages, std::memory_order_release);
spanTrackers_[trackerIndex].blockCount.store(blockNum, std::memory_order_release); // 共分配了blockNum个内存块
spanTrackers_[trackerIndex].freeCount.store(blockNum - 1, std::memory_order_release); // 第一个块result已被分配出去,所以初始空闲块数为blockNum - 1
}
}
}
else
{
// 保存result的下一个节点
void* next = *reinterpret_cast<void**>(result);
// 将result与链表断开
*reinterpret_cast<void**>(result) = nullptr;
// 更新中心缓存
centralFreeList_[index].store(next, std::memory_order_release);
// 更新span的空闲计数
SpanTracker* tracker = getSpanTracker(result);
if (tracker)
{
// 减少一个空闲块
tracker->freeCount.fetch_sub(1, std::memory_order_release);
}
}
}
catch (...)
{
locks_[index].clear(std::memory_order_release);
throw;
}
// 释放锁
locks_[index].clear(std::memory_order_release);
return result;
}
void CentralCache::returnRange(void* start, size_t size, size_t index)
{
if (!start || index >= FREE_LIST_SIZE)
return;
size_t blockSize = (index + 1) * ALIGNMENT;
size_t blockCount = size / blockSize;
while (locks_[index].test_and_set(std::memory_order_acquire))
{
std::this_thread::yield();
}
try
{
// 1. 将归还的链表连接到中心缓存
void* end = start;
size_t count = 1;
while (*reinterpret_cast<void**>(end) != nullptr && count < blockCount) {
end = *reinterpret_cast<void**>(end);
count++;
}
void* current = centralFreeList_[index].load(std::memory_order_relaxed);
*reinterpret_cast<void**>(end) = current; // 头插法(将原有链表接在归还链表后边)
centralFreeList_[index].store(start, std::memory_order_release);
// 2. 更新延迟计数
size_t currentCount = delayCounts_[index].fetch_add(1, std::memory_order_relaxed) + 1;
auto currentTime = std::chrono::steady_clock::now();
// 3. 检查是否需要执行延迟归还
if (shouldPerformDelayedReturn(index, currentCount, currentTime))
{
performDelayedReturn(index);
}
}
catch (...)
{
locks_[index].clear(std::memory_order_release);
throw;
}
locks_[index].clear(std::memory_order_release);
}
// 检查是否需要执行延迟归还
bool CentralCache::shouldPerformDelayedReturn(size_t index, size_t currentCount,
std::chrono::steady_clock::time_point currentTime)
{
// 基于计数和时间的双重检查
if (currentCount >= MAX_DELAY_COUNT)
{
return true;
}
auto lastTime = lastReturnTimes_[index];
return (currentTime - lastTime) >= DELAY_INTERVAL;
}
// 执行延迟归还
void CentralCache::performDelayedReturn(size_t index)
{
// 重置延迟计数
delayCounts_[index].store(0, std::memory_order_relaxed);
// 更新最后归还时间
lastReturnTimes_[index] = std::chrono::steady_clock::now();
// 统计每个span的空闲块数
std::unordered_map<SpanTracker*, size_t> spanFreeCounts;
void* currentBlock = centralFreeList_[index].load(std::memory_order_relaxed);
while (currentBlock)
{
SpanTracker* tracker = getSpanTracker(currentBlock);
if (tracker)
{
spanFreeCounts[tracker]++;
}
currentBlock = *reinterpret_cast<void**>(currentBlock);
}
// 更新每个span的空闲计数并检查是否可以归还
for (const auto& [tracker, newFreeBlocks] : spanFreeCounts)
{
updateSpanFreeCount(tracker, newFreeBlocks, index);
}
}
void CentralCache::updateSpanFreeCount(SpanTracker* tracker, size_t newFreeBlocks, size_t index)
{
size_t oldFreeCount = tracker->freeCount.load(std::memory_order_relaxed);
size_t newFreeCount = oldFreeCount + newFreeBlocks;
tracker->freeCount.store(newFreeCount, std::memory_order_release);
// 如果所有块都空闲,归还span
if (newFreeCount == tracker->blockCount.load(std::memory_order_relaxed))
{
void* spanAddr = tracker->spanAddr.load(std::memory_order_relaxed);
size_t numPages = tracker->numPages.load(std::memory_order_relaxed);
// 从自由链表中移除这些块
void* head = centralFreeList_[index].load(std::memory_order_relaxed);
void* newHead = nullptr;
void* prev = nullptr;
void* current = head;
while (current)
{
void* next = *reinterpret_cast<void**>(current);
if (current >= spanAddr &&
current < static_cast<char*>(spanAddr) + numPages * PageCache::PAGE_SIZE)
{
if (prev)
{
*reinterpret_cast<void**>(prev) = next;
}
else
{
newHead = next;
}
}
else
{
prev = current;
}
current = next;
}
centralFreeList_[index].store(newHead, std::memory_order_release);
PageCache::getInstance().deallocateSpan(spanAddr, numPages);
}
}
void* CentralCache::fetchFromPageCache(size_t size)
{
// 1. 计算实际需要的页数
size_t numPages = (size + PageCache::PAGE_SIZE - 1) / PageCache::PAGE_SIZE;
// 2. 根据大小决定分配策略
if (size <= SPAN_PAGES * PageCache::PAGE_SIZE)
{
// 小于等于32KB的请求,使用固定8页
return PageCache::getInstance().allocateSpan(SPAN_PAGES);
}
else
{
// 大于32KB的请求,按实际需求分配
return PageCache::getInstance().allocateSpan(numPages);
}
}
SpanTracker* CentralCache::getSpanTracker(void* blockAddr)
{
// 遍历spanTrackers_数组,找到blockAddr所属的span
for (size_t i = 0; i < spanCount_.load(std::memory_order_relaxed); ++i)
{
void* spanAddr = spanTrackers_[i].spanAddr.load(std::memory_order_relaxed);
size_t numPages = spanTrackers_[i].numPages.load(std::memory_order_relaxed);
if (blockAddr >= spanAddr &&
blockAddr < static_cast<char*>(spanAddr) + numPages * PageCache::PAGE_SIZE)
{
return &spanTrackers_[i];
}
}
return nullptr;
}
} // namespace memoryPool
页缓存(PageCache)
PageCache是内存池中的大块内存管理器,主要负责:
-
系统内存申请
a. 直接与操作系统交互,通过mmap申请大块内存
b. 以页(4KB)为单位进行内存管理
c. 充当内存池与操作系统之间的桥梁 -
大块内存管理
a. 管理和组织空闲的内存页
b. 处理内存的分配和回收
c. 实现内存页的合并和分割
#pragma once
#include "Common.h"
#include <map>
#include <mutex>
namespace memoryPool
{
class PageCache
{
public:
static const size_t PAGE_SIZE = 4096; // 4K页大小
static PageCache& getInstance()
{
static PageCache instance;
return instance;
}
// 分配指定页数的span
void* allocateSpan(size_t numPages);
// 释放span
void deallocateSpan(void* ptr, size_t numPages);
private:
PageCache() = default;
// 向系统申请内存
void* systemAlloc(size_t numPages);
private:
struct Span
{
void* pageAddr; // 页起始地址
size_t numPages; // 页数
Span* next; // 链表指针
};
// 按页数管理空闲span,不同页数对应不同Span链表
std::map<size_t, Span*> freeSpans_;
// 页号到span的映射,用于回收
std::map<void*, Span*> spanMap_;
std::mutex mutex_;
};
} // namespace memoryPool
1. 内存分配流程
会找一个大于等于numPages的内存进行分配,如果找到的内存过大,则会将多余的页放入freeSpans_中
void* PageCache::allocateSpan(size_t numPages)
{
std::lock_guard<std::mutex> lock(mutex_);
// 查找合适的空闲span
// lower_bound函数返回第一个大于等于numPages的元素的迭代器
auto it = freeSpans_.lower_bound(numPages);
if (it != freeSpans_.end())
{
Span* span = it->second;
// 将取出的span从原有的空闲链表freeSpans_[it->first]中移除
if (span->next)
{
freeSpans_[it->first] = span->next;
}
else
{
freeSpans_.erase(it);
}
// 如果span大于需要的numPages则进行分割
if (span->numPages > numPages)
{
Span* newSpan = new Span;
newSpan->pageAddr = static_cast<char*>(span->pageAddr) +
numPages * PAGE_SIZE;
newSpan->numPages = span->numPages - numPages;
newSpan->next = nullptr;
// 将超出部分放回空闲Span*列表头部
auto& list = freeSpans_[newSpan->numPages];
newSpan->next = list;
list = newSpan;
span->numPages = numPages;
}
// 记录span信息用于回收
spanMap_[span->pageAddr] = span;
return span->pageAddr;
}
// 没有合适的span,向系统申请
void* memory = systemAlloc(numPages);
if (!memory) return nullptr;
// 创建新的span
Span* span = new Span;
span->pageAddr = memory;
span->numPages = numPages;
span->next = nullptr;
// 记录span信息用于回收
spanMap_[memory] = span;
return memory;
}
2. 内存回收流程
会尝试将当前页和后面的页(必须是空闲的)进行合并,得到更大的页
void PageCache::deallocateSpan(void* ptr, size_t numPages)
{
std::lock_guard<std::mutex> lock(mutex_);
// 查找对应的span,没找到代表不是PageCache分配的内存,直接返回
auto it = spanMap_.find(ptr);
if (it == spanMap_.end()) return;
Span* span = it->second;
// 尝试合并相邻的span
void* nextAddr = static_cast<char*>(ptr) + numPages * PAGE_SIZE;
auto nextIt = spanMap_.find(nextAddr);
if (nextIt != spanMap_.end())
{
Span* nextSpan = nextIt->second;
// 1. 首先检查nextSpan是否在空闲链表中
bool found = false;
auto& nextList = freeSpans_[nextSpan->numPages];
// 检查是否是头节点
if (nextList == nextSpan)
{
nextList = nextSpan->next;
found = true;
}
else if (nextList) // 只有在链表非空时才遍历
{
Span* prev = nextList;
while (prev->next)
{
if (prev->next == nextSpan)
{
// 将nextSpan从空闲链表中移除
prev->next = nextSpan->next;
found = true;
break;
}
prev = prev->next;
}
}
// 2. 只有在找到nextSpan的情况下才进行合并
if (found)
{
// 合并span
span->numPages += nextSpan->numPages;
spanMap_.erase(nextAddr);
delete nextSpan;
}
}
// 将合并后的span通过头插法插入空闲列表
auto& list = freeSpans_[span->numPages];
span->next = list;
list = span;
}
PageCache完整实现
#pragma once
#include "Common.h"
#include <map>
#include <mutex>
namespace memoryPool
{
class PageCache
{
public:
static const size_t PAGE_SIZE = 4096; // 4K页大小
static PageCache& getInstance()
{
static PageCache instance;
return instance;
}
// 分配指定页数的span
void* allocateSpan(size_t numPages);
// 释放span
void deallocateSpan(void* ptr, size_t numPages);
private:
PageCache() = default;
// 向系统申请内存
void* systemAlloc(size_t numPages);
private:
struct Span
{
void* pageAddr; // 页起始地址
size_t numPages; // 页数
Span* next; // 链表指针
};
// 按页数管理空闲span,不同页数对应不同Span链表
std::map<size_t, Span*> freeSpans_;
// 页号到span的映射,用于回收
std::map<void*, Span*> spanMap_;
std::mutex mutex_;
};
} // namespace memoryPool
#include "PageCache.h"
#include <sys/mman.h>
#include <cstring>
namespace memoryPool
{
void* PageCache::allocateSpan(size_t numPages)
{
std::lock_guard<std::mutex> lock(mutex_);
// 查找合适的空闲span
// lower_bound函数返回第一个大于等于numPages的元素的迭代器
auto it = freeSpans_.lower_bound(numPages);
if (it != freeSpans_.end())
{
Span* span = it->second;
// 将取出的span从原有的空闲链表freeSpans_[it->first]中移除
if (span->next)
{
freeSpans_[it->first] = span->next;
}
else
{
freeSpans_.erase(it);
}
// 如果span大于需要的numPages则进行分割
if (span->numPages > numPages)
{
Span* newSpan = new Span;
newSpan->pageAddr = static_cast<char*>(span->pageAddr) +
numPages * PAGE_SIZE;
newSpan->numPages = span->numPages - numPages;
newSpan->next = nullptr;
// 将超出部分放回空闲Span*列表头部
auto& list = freeSpans_[newSpan->numPages];
newSpan->next = list;
list = newSpan;
span->numPages = numPages;
}
// 记录span信息用于回收
spanMap_[span->pageAddr] = span;
return span->pageAddr;
}
// 没有合适的span,向系统申请
void* memory = systemAlloc(numPages);
if (!memory) return nullptr;
// 创建新的span
Span* span = new Span;
span->pageAddr = memory;
span->numPages = numPages;
span->next = nullptr;
// 记录span信息用于回收
spanMap_[memory] = span;
return memory;
}
void PageCache::deallocateSpan(void* ptr, size_t numPages)
{
std::lock_guard<std::mutex> lock(mutex_);
// 查找对应的span,没找到代表不是PageCache分配的内存,直接返回
auto it = spanMap_.find(ptr);
if (it == spanMap_.end()) return;
Span* span = it->second;
// 尝试合并相邻的span
void* nextAddr = static_cast<char*>(ptr) + numPages * PAGE_SIZE;
auto nextIt = spanMap_.find(nextAddr);
if (nextIt != spanMap_.end())
{
Span* nextSpan = nextIt->second;
// 1. 首先检查nextSpan是否在空闲链表中
bool found = false;
auto& nextList = freeSpans_[nextSpan->numPages];
// 检查是否是头节点
if (nextList == nextSpan)
{
nextList = nextSpan->next;
found = true;
}
else if (nextList) // 只有在链表非空时才遍历
{
Span* prev = nextList;
while (prev->next)
{
if (prev->next == nextSpan)
{
// 将nextSpan从空闲链表中移除
prev->next = nextSpan->next;
found = true;
break;
}
prev = prev->next;
}
}
// 2. 只有在找到nextSpan的情况下才进行合并
if (found)
{
// 合并span
span->numPages += nextSpan->numPages;
spanMap_.erase(nextAddr);
delete nextSpan;
}
}
// 将合并后的span通过头插法插入空闲列表
auto& list = freeSpans_[span->numPages];
span->next = list;
list = span;
}
void* PageCache::systemAlloc(size_t numPages)
{
size_t size = numPages * PAGE_SIZE;
// 使用mmap分配内存
void* ptr = mmap(nullptr, size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (ptr == MAP_FAILED) return nullptr;
// 清零内存
memset(ptr, 0, size);
return ptr;
}
} // namespace memoryPool
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目,面向数字基础设施四大核心场景(服务器、云计算、边缘计算、嵌入式),全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐

所有评论(0)