高并发内存池

1. 项目介绍

这个项目是基于google开源的tcmalloc，在经过简化后，拿出核心框架的内容所实现的一个高并发内存池。

2. 内存池

2.1 什么是池化技术？

池化技术指的是，程序先向系统申请一定数量的资源，然后自己管理这些资源的分配和清理。因为，我们每次在向系统申请资源时都有较大的开销，并且可能会造成内存碎片的问题。提前申请好一定数量的资源，就可以减少中间频繁申请资源带来的开销，从而大大提供程序的运行效率。

在计算机中，使用池化技术的地方还有连接池、线程池、对象池等等。

2.2 内存池的原理

内存池本质上是先通过向系统申请一大块内存空间，当后续需要申请某个对象的内存时，可以直接向内存池进行申请。同理，释放资源也是将内存还给内存池，内存池在程序退出的时候，会自动释放内存池的申请的内存，因此，可以不用考虑内存池的释放问题。

2.3 内存池解决的问题

内存池最主要的是提升了效率的问题，但除此之外，还解决了内存碎片的问题。

内存碎片可以分为内碎片和外碎片。外部碎片是因为内存存在大量的小内存，这些内存并不连续，当申请一个较大的内存时，因为这些内存空间不连续，以至于合计的内存足够，但是不能满足一些的内存分配申请需求。内部碎片是由于一些对齐的需求，导致分配出去的空间中一些内存无法被利用。

2.4 malloc

我们知道C++的new关键字底层调用的是operator new，然后调用的是malloc。

而malloc本质上也是一个内存池。

3. 设计一个定长内存池

定长内存池的定长指的是，申请的内存大小是固定的，也就是专门针对一个类或者指定大小来进行内存申请和释放。底层的memory是使用malloc申请的一大块连续的内存空间。而freeList是一个自由链表，来管理已经被释放的内存，而自由链表的头部有一个指针用来指向下一个自由链表的地址。

/* @brief 调用不同系统底层的获取内存函数* @param[in] kpage 申请的页大小* @return 申请的内存空间
*/
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr = VirtualAlloc(0, kpage * (1 << 12), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE); // 1 << 12 = 4k
#else // linux brk mmap
#endifif (ptr == nullptr){throw std::bad_alloc();}return ptr;
}/* @brief 定长内存池* @tparam T 申请的类型
*/
template<class T>
class ObjectPool
{
public:/* @brief 申请类型T的大小的内存* @return 指向这块内存的指针*/T* New(){T* obj = nullptr;// 如果自由链表有对象，就直接获取if (_freeList){obj = (T*)_freeList;_freeList = *((void**)_freeList);}else{// 剩余内存不够一个大小的时候if (_leftBytes < sizeof(T)){_leftBytes = 128 * 1024; // 申请128k_memory = (char*)SystemAlloc(_leftBytes >> 13);}obj = (T*)_memory;size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T); // 至少申请一个指针的大小_memory += objSize;_leftBytes -= objSize;}new(obj)T; // 调用T的构造函数return obj;}/* @brief 释放通过New申请的内存* @param[in] obj 释放的内存对象*/void Delete(T* obj){// 调用T的析构函数obj->~T();// 头插到freeList*((void**)obj) = _freeList;_freeList = obj;}private:/// 指向内存块的指针char* _memory = nullptr;/// 内存块中剩余的字节数size_t _leftBytes = 0;/// 管理还回来的内存对象的自由链表void* _freeList = nullptr;
};

效率测试（对比malloc）：

struct TreeNode
{int _val;TreeNode* _left;TreeNode* _right;TreeNode():_val(0), _left(nullptr), _right(nullptr){}
};void TestObjectPool()
{// 申请释放的轮次const size_t Rounds = 3;// 每轮申请释放多少次const size_t N = 100000;size_t begin1 = clock();std::vector<TreeNode*> v1;v1.reserve(N);for (size_t j = 0; j < Rounds; ++j){for (int i = 0; i < N; ++i){v1.push_back(new TreeNode);}for (int i = 0; i < N; ++i){delete v1[i];}v1.clear();}size_t end1 = clock();ObjectPool<TreeNode> TNPool;size_t begin2 = clock();std::vector<TreeNode*> v2;v2.reserve(N);for (size_t j = 0; j < Rounds; ++j){for (int i = 0; i < N; ++i){v2.push_back(TNPool.New());}for (int i = 0; i < 100000; ++i){TNPool.Delete(v2[i]);}v2.clear();}size_t end2 = clock();std::cout << "new cost time:" << end1 - begin1 << std::endl;std::cout << "object pool cost time:" << end2 - begin2 << std::endl;
}int main()
{TestObjectPool();
}

Debug下，x64平台：

4. 高并发内存池整体框架设计

我们的这个内存池是在多线程环境下进行的，在申请内存的时候，必然会有进程抢占资源的问题，所以要是用锁来解决。并且，内存池还要考虑性能和内存碎片的问题。在设计的时候主要是由以下三个部分构成：

1. thread_cache：线程缓存，这个是每个线程独有的一个模块，线程在这里进行申请内存时不需要加锁，用于小块内存分配。
2. central_cache：中心缓存，是所有线程共享的一个模块，是用来给thread_cache进行内存分配和回收对象。这里是存在竞争的，这里采用的是桶锁。而且当thead_cache没有内存时才会向central_cache进行申请，所以竞争并不激烈。
3. page_cache：页缓存是在central_cache缓存上面的一层缓存，存储的内存是以页为单位进行存储和分配的，当central_cache没有内存时，会从page_cache分配一定数量的page，并且切割成定长大小的小块内存，分配给central_cache。并且分割出去的小块内存，也会进行回收，并且合并更大的页，缓解内存碎片的问题。

5. thread cache部分

thread_cache是一个哈希桶结构，每个桶都是按照桶位置映射大小的内存块对象的自由链表。并且这里的thread_cache对象是一个线程局部对象，不需要考虑锁的问题。

5.1 基本实现

// ThreadCache.h/* @brief 线程缓存
*/
class ThreadCache
{
public:/* @brief 分配空间* @param[in] size 分配的大小* @return 分配的内存地址*/void* Allocate(size_t size);/* @brief 释放空间* @param[in] ptr 要释放的地址* @param[in] size 释放的大小*/void Deallocate(void* ptr, size_t size);private:/// 自由链表的哈希桶结构FreeList _freeLists[NFREELISTS];
};static thread_local ThreadCache* t_threadcache = nullptr;

// common.h/// threadcache哈希桶中的最大字节数
static constexpr size_t MAX_BYTES = 256 * 1024; // 256k
/// 哈希桶的数量
static constexpr size_t NFREELISTS = 208;
/// 页大小转换偏移
static constexpr size_t PAGE_SHIFT = 13; // 一般是1 << 13，也就是8k/* @brief 调用不同系统底层的获取内存函数* @param[in] kpage 申请的页大小* @return 申请的内存空间
*/
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr = VirtualAlloc(0, kpage * (1 << 12), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE); // 1<<12 = 4k
#else // linux brk mmap
#endifif (ptr == nullptr){throw std::bad_alloc();}return ptr;
}/* @brief 调用不同系统底层的释放内存函数* @param[in] ptr 释放的结点指针
*/
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32VirtualFree(ptr, 0, MEM_RELEASE);
#else// sbrk unmmap等
#endif
}/// 获取自由链表的下一个结点
static void*& NextObj(void* obj)
{return *(void**)obj;
}/* @brief 自由链表
*/
class FreeList
{
public:/* @brief 插入一个结点* @param[in] obj 插入的对象*/void Push(void* obj){assert(obj);// 头插NextObj(obj) = _head;_head = obj;++_size;}/* @brief 弹出一个结点* @return 弹出的结点指针*/void* Pop(){assert(_head);void* obj = _head;_head = NextObj(obj);--_size;return obj;}/* @brief 返回自由链表的个数* @return 返回大小*/size_t Size() const{return _size;}/* @brief 判断是否为空*/bool Empty() const{return _head == nullptr;}
private:/// 自由链表的头部void* _head = nullptr;/// 自由链表的大小size_t _size = 0;
};/* @brief 计算对象大小的对齐规则
*/
class SizeClass
{
public:// 整体控制在最多10%左右的内碎片浪费// [1,128]					8byte对齐			freelist[0,16)// [128+1,1024]				16byte对齐			freelist[16,72)// [1024+1,8*1024]			128byte对齐			freelist[72,128)// [8*1024+1,64*1024]		1024byte对齐			freelist[128,184)// [64*1024+1,256*1024]		8*1024byte对齐		freelist[184,208)/* @brief 向指定对齐数对齐* @param[in] bytes 大小* @param[in] align 对齐数* @return 对齐之后的大小*/static inline size_t _RoundUp(size_t bytes, size_t align){// align是2^n，~(2^n次方-1)表示二进制的低n位全为0，高位全为1。// 在使用&，相当于将bytes + align - 1 的低n位置为0。return ((bytes + align - 1) & ~(align - 1));}/* @brief 根据指定大小来选取对齐数，对应到哈希桶的位置* @param[in] bytes 要对齐的大小* @return 对齐之后的结果*/static inline size_t RoundUp(size_t bytes){if (bytes <= 128){return _RoundUp(bytes, 8);}else if (bytes <= 1024){return _RoundUp(bytes, 16);}else if (bytes <= 8 * 1024){return _RoundUp(bytes, 128);}else if (bytes <= 64 * 1024){return _RoundUp(bytes, 1024);}else if (bytes <= 256 * 1024){return _RoundUp(bytes, 8 * 1024);}else{return _RoundUp(bytes, 1 << PAGE_SHIFT); // 以页为单位对齐}return -1;}/* @brief 根据对齐偏移量计算对应哈希桶的索引下标* @param[in] bytes 对齐后的大小* @param[in] align_shift 对齐偏移量 比如按8字节对齐，也就是1 << 3, 3是偏移量* @return 哈希桶的索引下标*/static inline size_t _Index(size_t bytes, size_t align_shift){// 假如传入的是32，相当于((32 + 8 - 1) / 8) - 1return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;}/* @brief 计算映射到哪一个自由链表桶中* @param[in] bytes 对齐后的大小* @return 哈希桶的索引下标*/static inline size_t Index(size_t bytes){assert(bytes <= MAX_BYTES);// 每个区间有多少个桶static int group_array[4] = { 16,56,56,56 };if (bytes <= 128){return _Index(bytes, 3);}else if (bytes <= 1024){// 从bytes-上一层最大的大小开始，按照指定的对齐偏移量，加上上一层最大下标return _Index(bytes - 128, 4) + group_array[0];}else if (bytes <= 8 * 1024){return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];}else if (bytes <= 64 * 1024){return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];}else if (bytes <= 256 * 1024){return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];}else{assert(false);}return -1;}};

// ThreadCache.cc#include "ThreadCache.h"void* ThreadCache::Allocate(size_t size)
{assert(size <= MAX_BYTES);size_t alignSize = SizeClass::RoundUp(size); // 将大小对齐size_t index = SizeClass::Index(alignSize); // 计算映射的桶的位置if (!_freeLists[index].Empty()){return _freeLists[index].Pop();}else {// 否则从central_cache获取}
}void ThreadCache::Deallocate(void* ptr, size_t size)
{assert(ptr);assert(size <= MAX_BYTES);size_t index = SizeClass::Index(size);// 找到对应桶的自由链表，并插入_freeLists[index].Push(ptr);}

5.2 问题

基本模块实现完成后，我们可以做到分配256kb大小以下的内存，当我们哈希桶某个链表长度过长的时候，就会有大量该大小的内存块，我们需要将其回收一部分，返回给我们的上一层central_cache。这样才不会导致内存碎片的问题发送。

// ThreadCache.h
class ThreadCache
{
public:/* @brief 释放对象时，链表过长时，回收内存回到中心缓存* @param[in] list 释放的自由链表* @param[in] size 释放的大小*/void ListTooLong(FreeList& list, size_t size);
};// ThreadCache.cc
void ThreadCache::Deallocate(void* ptr, size_t size)
{assert(ptr);assert(size <= MAX_BYTES);size_t index = SizeClass::Index(size);// 找到对应桶的自由链表，并插入_freeLists[index].Push(ptr);// 当链表的长度大于一次批量申请的内存时就开始还一段list给central_cacheif (_freeLists[index].Size() >= _freeLists[index].MaxSize()){ListTooLong(_freeLists[index], size);}
}void ThreadCache::ListTooLong(FreeList& list, size_t size)
{void* start = nullptr;void* end = nullptr;list.PopRange(start, end, list.MaxSize());// 由上一层来合并
}// common.h
class FreeList
{
public:/* @brief 批量插入自由链表* @param[in] start 插入的起始位置* @param[in] end 插入的末尾位置* @param[in] n 插入的个数*/void PushRange(void* start, void* end, size_t n){// 头插NextObj(end) = _head;_head = start;_size += n;}/* @brief 弹出批量的结点* @param[out] start * @param[out] end * @param[in] n */void PopRange(void*& start, void*& end, size_t n){assert(n <= _size);start = _head;end = start;for (size_t i = 0; i < n - 1; ++i){end = NextObj(end);}_head = NextObj(end);NextObj(end) = nullptr;_size -= n;}/* @brief 返回Maxsize*/size_t& MaxSize(){return _maxSize;}private:/// 自由链表所能接受的最大大小size_t _maxSize = 1;
};

最后，就是如何从CentralCache获取内存，接下来需要了解CentralCache的机制。

6. central cache部分

central cache也是一个哈希桶结构，他的哈希桶的映射关系跟thread cache是一样的。不同的是他的每
个哈希桶位置挂是SpanList链表结构，不过每个映射桶下面的span中的大内存块被按映射关系切成了一
个个小内存块对象挂在span的自由链表中。

申请内存：

1. 当thread cache中没有内存时，就会批量向central cache申请一些内存对象，这里的批量获取对象的数量使用了类似网络tcp协议拥塞控制的慢开始算法；central cache也有一个哈希映射的spanlist，spanlist中挂着span，从span中取出对象给thread cache，这个过程是需要加锁的，不过这里使用的是一个桶锁，尽可能提高效率。
2. central cache映射的spanlist中所有span的都没有内存以后，则需要向page cache申请一个新的span对象，拿到span以后将span管理的内存按大小切好作为自由链表链接到一起。然后从span中取对象给thread cache。
3. central cache的中挂的span中use_count记录分配了多少个对象出去，分配一个对象给threadcache，就++use_count。

释放内存：

1. 当thread_cache过长或者线程销毁，则会将内存释放回central cache中的，释放回来时--use_count。当use_count减到0时则表示所有对象都回到了span，则将span释放回page cache，page cache中会对前后相邻的空闲页进行合并。

6.1 基本实现

// ThreadCache.h
class ThreadCache
{
public:/* @brief 从中心缓存获取内存对象* @param[in] index 哈希桶的索引* @param[in] size 获取的内存大小* @return 获取到的内存对象*/void* FetchFromCentralCache(size_t index, size_t size);
};// ThreadCache.cc
void* ThreadCache::Allocate(size_t size)
{assert(size <= MAX_BYTES);size_t alignSize = SizeClass::RoundUp(size); // 将大小对齐size_t index = SizeClass::Index(alignSize); // 计算映射的桶的位置if (!_freeLists[index].Empty()){return _freeLists[index].Pop();}else{// 否则从central_cache获取return FetchFromCentralCache(index, alignSize);}return nullptr;
}void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{/// 慢开始反馈算法// 最开始一次不会向central cache要太多，可能用不完// batchNum会不断增长，NumMoveSize()就是对应的上限// size越大，一次向central_cache要的batchNum越小// size越小，一次向central_cache要的batchNum越大size_t batchNum = _freeLists[index].MaxSize() > SizeClass::NumMoveSize(size) ? SizeClass::NumMoveSize(size) : _freeLists[index].MaxSize();if (batchNum == _freeLists[index].MaxSize())++_freeLists[index].MaxSize();void* start = nullptr;void* end = nullptr;size_t actualNum = CentralCache::GetInstace()->FetchRangeObj(start, end, batchNum, size);assert(actualNum > 0);_freeLists[index].PushRange(NextObj(start), end, actualNum - 1);return start;
}

CentralCache部分：

/* @brief 单例模式下的中心缓存模块
*/
class CentralCache
{
public:/* @brief 获取对象实例* @return 返回当前对象实例*/static CentralCache* GetInstace(){return &_sIntanse;}/* @brief  从SpanList或者page cache获取一个非空的span* @param[in] list 哪个SpanList* @param[in] size  哈希桶指定位置的大小* @return 返回Span对象*/Span* GetOneSpan(SpanList& list, size_t size);/* @brief 从中心缓存获取一定数量的对象给thread cache* @param[out] start 返回的自由链表的头* @param[out] end 返回的自由链表的尾* @param[in] batchNum 想要获取的个数* @param[in] size 哈希桶指定位置的大小* @return 返回实际获取的自由链表个数*/size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size);private:/// SpanList链表SpanList _spanLists[NFREELISTS];
private:/// 构造函数私有化CentralCache() {}/// 拷贝构造删除CentralCache(const CentralCache&) = delete;/// 对象实例static CentralCache _sIntanse;
};

具体实现：

#include "CentralCache.h"CentralCache CentralCache::_sIntanse;Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{// TODOreturn nullptr;
}size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)
{size_t index = SizeClass::Index(size);_spanLists[index]._mtx.lock(); // 加锁，只对该桶生效Span* span = GetOneSpan(_spanLists[index], size);assert(span);assert(span->freeList);start = span->freeList;end = start;size_t i = 0;while (i < batchNum - 1 && NextObj(end) != nullptr){end = NextObj(end);++i;}size_t actualNum = i + 1; // 实际上获取的数量span->freeList = NextObj(end);NextObj(end) = nullptr;span->useCount += actualNum;_spanLists[index]._mtx.unlock();return actualNum;
}

公共部分：

class SizeClass
{
public:/* @brief 一次thread cache从中心缓存获取多少个size* @param[in] size* @return*/static size_t NumMoveSize(size_t size){assert(size > 0);int num = MAX_BYTES / size;if (num < 2)num = 2;if (num > 512)num = 512;return num;}
};/* @brief 大块内存Span结构
*/
struct Span
{/// 指向前一个结点的指针Span* prev = nullptr;/// 指向下一个结点的指针Span* next = nullptr;/// 切好的小对象的大小size_t objSize = 0;/// 分配给threadcache的小块内存的个数size_t useCount = 0;/// 小块内存的自由链表void* freeList = nullptr;
};/* @brief 带头双向循环的Span链表
*/
class SpanList
{
public:/* @brief 构造函数*/SpanList(){_head = new Span;_head->next = _head;_head->prev = _head;}/* @brief 获取头部Span* @return 返回头部Span*/Span* Begin(){return _head->next;}/* @brief 获取尾部Span* @return 返回尾部Span*/Span* End(){return _head;}/* @brief 判断是否为空*/bool Empty() const{return _head->next == _head;}/* @brief 头插* @param[in] span span对象*/void PushFront(Span* span){Insert(Begin(), span);}/* @brief 头删* @return 返回弹出的span对象*/Span* PopFront(){Span* front = _head->next;Erase(front);return front;}/* @brief 在指定位置前插入新的元素* @param[in] pos 插入位置的元素* @param[in] newSpan 要插入的元素*/void Insert(Span* pos, Span* newSpan){assert(pos);assert(newSpan);Span* prev = pos->prev;// prev newspan posprev->next = newSpan;newSpan->prev = prev;newSpan->next = pos;pos->prev = newSpan;}/* @brief 删除指定元素* @param[in] pos 要删除的元素*/void Erase(Span* pos){assert(pos);assert(pos != _head);pos->prev->next = pos->next;pos->prev->prev = pos->prev;}
public:std::mutex _mtx; // 桶锁
private:Span* _head = nullptr;
};

6.2 问题

同样，中心缓存部分也要考虑对于将所有分配给thread_cache的对象都回收回来后，将span释放返回给page_cache，接下来就由上层的page_cache来处理。而底层的thread_cache回收的时候将数据交由到本层处理，来回收span分配出去的小对象。

class CentralCache
{
public:/* @brief 将一定数量的对象释放到span跨度* @param[in] start 回收对象的起始位置* @param[in] size 哈希桶指定位置的大小*/void ReleaseListToSpans(void* start, size_t size);
};// ThreadCache.cc
void ThreadCache::ListTooLong(FreeList& list, size_t size)
{void* start = nullptr;void* end = nullptr;list.PopRange(start, end, list.MaxSize());// 由上一层来合并CentralCache::GetInstace()->ReleaseListToSpans(start, size);
}

7. page cache部分

申请内存：

1. 当central cache向page cache申请内存时，page cache先检查对应位置有没有span，如果没有则向更大页寻找一个span，如果找到则分裂成两个。比如：申请的是4页page，4页page后面没有挂span，则向后面寻找更大的span，假设在10页page位置找到一个span，则将10页page span分裂为一个4页page span和一个6页page span。
2. 如果找到_spanList[128]都没有合适的span，则向系统使用mmap、brk或者是VirtualAlloc等方式申请128页page span挂在自由链表中，再重复1中的过程。
3. 需要注意的是central cache和page cache 的核心结构都是spanlist的哈希桶，但是他们是有本质区别的，central cache中哈希桶，是按跟thread cache一样的大小对齐关系映射的，他的spanlist中挂的span中的内存都被按映射关系切好链接成小块内存的自由链表。而page cache 中的spanlist则是按下标桶号映射的，也就是说第i号桶中挂的span都是i页内存。

释放内存：

1. 如果central cache释放回一个span，则依次寻找span的前后page id的没有在使用的空闲span，看是否可以合并，如果合并继续向前寻找。这样就可以将切小的内存合并收缩成大的span，减少内存碎片。

7.1 基本实现

// PageCache.h/* @brief 页缓存的单例模式
*/
class PageCache
{
public:static PageCache* GetInstance(){return &_sInstance;}/* @brief 获取从对象到span的映射* @param[in] obj 传入的对象* @return 返回该对象是在哪个Span上*/Span* MapObjectToSpan(void* obj);/* @brief 获取第k页的span* @param[in] k 获取的页数* @return 获取到的Span对象*/Span* NewSpan(size_t k);/* @brief 释放空闲span回到Pagecache，并合并相邻的span* @param[in] span 释放的Span对象*/void ReleaseSpanToPageCache(Span* span);private:/// 哈希桶结构，每个桶存的是span链表SpanList _spanLists[NPAGES];/// 用来分配Span的内存池ObjectPool<Span> _spanPool;/// 页数id到Span对象的映射std::unordered_map<PAGE_ID, Span*> _idSpanMap;
private:PageCache(){}PageCache(const PageCache&) = delete;static PageCache _sInstance;
};// PageCache.cc
#include "PageCache.h"PageCache PageCache::_sInstance;Span* PageCache::MapObjectToSpan(void* obj)
{PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;auto ret = (Span*)_idSpanMap[id];assert(ret != nullptr);return ret;
}Span* PageCache::NewSpan(size_t k)
{assert(k > 0);if (k > NPAGES - 1) // 比128 * 8k 还大的{// 从堆上申请void* ptr = SystemAlloc(k);Span* span = _spanPool.New();span->pageId = (PAGE_ID)ptr >> PAGE_SHIFT;span->n = k;_idSpanMap[span->pageId] = span;return span;}if (!_spanLists[k].Empty()) // 对应页有span{// 取出一个Span页Span* kSpan = _spanLists[k].PopFront();// 建立id和span的映射for (PAGE_ID i = 0; i < kSpan->n; ++i){_idSpanMap[kSpan->pageId + i] = kSpan;}return kSpan;}// 对应的页没有span// 检查后面的桶有没有spanfor (size_t i = k + 1; i < NPAGES; ++i){if (!_spanLists[i].Empty()){// 切分Span* nSpan = _spanLists[i].PopFront();Span* kSpan = _spanPool.New();// 在nSpan的头部切一个k下来kSpan->pageId = nSpan->pageId;kSpan->n = k;nSpan->pageId += k;nSpan->n -= k;_spanLists[nSpan->n].PushFront(nSpan);// 存储nSpan的首尾页号跟nSpan的映射,方便page cache回收内存时的合并查找_idSpanMap[nSpan->pageId] = nSpan;_idSpanMap[nSpan->pageId + nSpan->n - 1] = nSpan;// 建立id和span的映射for (PAGE_ID i = 0; i < kSpan->n; ++i){_idSpanMap[kSpan->pageId + i] = kSpan;}return kSpan;}}// 说明128页没有span，需要从堆区申请Span* bigSpan = _spanPool.New();void* ptr = SystemAlloc(NPAGES - 1);bigSpan->pageId = (PAGE_ID)ptr >> PAGE_SHIFT;bigSpan->n = NPAGES - 1;_spanLists[bigSpan->n].PushFront(bigSpan);return NewSpan(k);
}void PageCache::ReleaseSpanToPageCache(Span* span)
{// 大于128页的内存直接还给堆区if (span->n > NPAGES - 1){void* ptr = (void*)(span->pageId << PAGE_SHIFT);SystemFree(ptr);_spanPool.Delete(span);return;}// 尝试将前后页进行合并，缓解内存碎片的问题while (true){PAGE_ID prevId = span->pageId - 1;auto ret = _idSpanMap.find(prevId);// 前面的页号没有，不合并if (ret == _idSpanMap.end())break;// 前面相邻页的span在使用Span* prevSpan = ret->second;if (prevSpan->isUse == true)break;// 合并出超过128的span，没办法管理，不合并if (prevSpan->n + span->n > NPAGES - 1)break;span->pageId = prevSpan->pageId;span->n += prevSpan->n;_spanLists[prevSpan->n].Erase(prevSpan);_spanPool.Delete(prevSpan);}// 向后合并while (true){PAGE_ID nextId = span->pageId + span->n;auto ret = _idSpanMap.find(nextId);if (ret == _idSpanMap.end())break;Span* nextSpan = ret->second;if (nextSpan->isUse == true)break;if (nextSpan->n + span->n > NPAGES - 1)break;span->n += nextSpan->n;_spanLists[nextSpan->n].Erase(nextSpan);_spanPool.Delete(nextSpan);}// 合并后的span放到对应位置_spanLists[span->n].PushFront(span);span->isUse = false;_idSpanMap[span->pageId] = span;_idSpanMap[span->pageId + span->n - 1] = span;
}// common.h
/// page cache 管理span list哈希表大小
static constexpr size_t NPAGES = 129;// 64位有_WIN64和_WIN32,32位只有_WIN32
#ifdef _WIN64
using PAGE_ID = unsigned long long;
#elif _WIN32
using PAGE_ID = size_t ;
#endif/* @brief 大块内存Span结构
*/
struct Span
{/// 大块内存起始页的页号PAGE_ID pageId = 0;/// 页的数量size_t n = 0;		  /// 指向前一个结点的指针Span* prev = nullptr;/// 指向下一个结点的指针Span* next = nullptr;/// 切好的小对象的大小size_t objSize = 0;/// 分配给threadcache的小块内存的个数size_t useCount = 0;/// 小块内存的自由链表void* freeList = nullptr;/// 是否在被使用bool isUse = false;
};

7.2 遗留问题

CentralCache层将Span还给PageCache，这里要注意锁之间的申请和释放。

class SizeClass
{
public:/* @brief 计算一次向系统获取几个页* @param[in] size 获取的页数*/static size_t NumMovePage(size_t size){size_t num = NumMoveSize(size);size_t npage = num * size;npage >>= PAGE_SHIFT;if (npage == 0)npage = 1;return npage;}
};// 申请一个Span，如果不够向PageCache申请
Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{// 查看当前的spanlist是否还有未分配对象的spanSpan* it = list.Begin();while (it != list.End()){if (it->freeList != nullptr)return it;it = it->next;}// 先把central cache的桶锁解掉，如果其他线程释放内存对象回来，不会阻塞list._mtx.unlock();// 说明没有空闲的span，从page cache申请PageCache::GetInstance()->_pageMtx.lock();Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(size));span->isUse = true;span->objSize = size;PageCache::GetInstance()->_pageMtx.unlock();// 对获取的span进行切分，不需要加锁，因为其他线程访问不到这个span// 计算span的大块内存的起始地址和大块内存的大小char* start = (char*)(span->pageId << PAGE_SHIFT);size_t bytes = span->n << PAGE_SHIFT;char* end = start + bytes;// 把大块内存切成自由链表链接起来// 切一块做头span->freeList = start;start += size;void* tail = span->freeList;// 尾插while (start < end){NextObj(tail) = start;tail = NextObj(tail);start += size;}NextObj(tail) = nullptr;// 切好span以后，需要把span的锁恢复list._mtx.lock();list.PushFront(span);return span;
}void CentralCache::ReleaseListToSpans(void* start, size_t size)
{size_t index = SizeClass::Index(size);_spanLists[index]._mtx.lock(); // 加锁while (start){void* next = NextObj(start);// 获取start对应在那个span，由上层来完成// TODOSpan* span = PageCache::GetInstance()->MapObjectToSpan(start);NextObj(start) = span->freeList;span->freeList = start;span->useCount--;// 当useCount = 0 时表示，切分出去的小块内存都回来了if (span->useCount == 0){_spanLists[index].Erase(span);span->freeList = nullptr;span->next = nullptr;span->prev = nullptr;// 需要暂时解锁_spanLists[index]._mtx.unlock();PageCache::GetInstance()->_pageMtx.lock();PageCache::GetInstance()->ReleaseSpanToPageCache(span);PageCache::GetInstance()->_pageMtx.unlock();_spanLists[index]._mtx.lock();}start = next;}_spanLists->_mtx.unlock();
}

8. 总结

实现一个头文件，使用线程局部对象的t_threadCache来分配内存和释放内存。

#pragma once#include "Common.h"
#include "ThreadCache.h"
#include "PageCache.h"
#include "ObjectPool.h"static void* ConcurrentAlloc(size_t size)
{if (size > MAX_BYTES){size_t alginSzie = SizeClass::RoundUp(size);size_t kpage = alginSzie >> PAGE_SHIFT;PageCache::GetInstance()->_pageMtx.lock();Span* span = PageCache::GetInstance()->NewSpan(kpage);span->objSize = size;PageCache::GetInstance()->_pageMtx.unlock();void* ptr = (void*)(span->pageId << PAGE_SHIFT);return ptr;}else{// 通过无锁的获取自己的ThreadCache对象if (t_threadcache == nullptr){static ObjectPool<ThreadCache> tcPool;t_threadcache = tcPool.New();}//cout << std::this_thread::get_id() << " : " << tls_threadcache << endl;return t_threadcache->Allocate(size);}
}static void ConcurrentFree(void* ptr)
{Span* span = PageCache::GetInstance()->MapObjectToSpan(ptr);size_t size = span->objSize;if (size > MAX_BYTES){PageCache::GetInstance()->_pageMtx.lock();PageCache::GetInstance()->ReleaseSpanToPageCache(span);PageCache::GetInstance()->_pageMtx.unlock();}else{assert(t_threadcache);t_threadcache->Deallocate(ptr, size);}
}

性能测试：

#include "ConcurrentAlloc.h"// ntimes 一轮申请和释放的次数
// rounds 轮次
// nworks 线程数
void BenchmarkMalloc(size_t ntimes, size_t nworks, size_t rounds)
{std::vector<std::thread> vthread(nworks);std::atomic<size_t> malloc_costtime = 0;std::atomic<size_t> free_costtime = 0;for (size_t k = 0; k < nworks; ++k){vthread[k] = std::thread([&, k]() {std::vector<void*> v;v.reserve(ntimes);for (size_t j = 0; j < rounds; ++j){size_t begin1 = clock();for (size_t i = 0; i < ntimes; i++){v.push_back(malloc(16));//v.push_back(malloc((16 + i) % 8192 + 1));}size_t end1 = clock();size_t begin2 = clock();for (size_t i = 0; i < ntimes; i++){free(v[i]);}size_t end2 = clock();v.clear();malloc_costtime += (end1 - begin1);free_costtime += (end2 - begin2);}});}for (auto& t : vthread){t.join();}printf("%u个线程并发执行%u轮次，每轮次malloc %u次: 花费：%u ms\\n",nworks, rounds, ntimes, (size_t)malloc_costtime);printf("%u个线程并发执行%u轮次，每轮次free %u次: 花费：%u ms\\n",nworks, rounds, ntimes, (size_t)free_costtime);printf("%u个线程并发malloc&free %u次，总计花费：%u ms\\n",nworks, nworks * rounds * ntimes, (size_t)(malloc_costtime + free_costtime));
}// 单轮次申请释放次数 线程数 轮次
void BenchmarkConcurrentMalloc(size_t ntimes, size_t nworks, size_t rounds)
{std::vector<std::thread> vthread(nworks);std::atomic<size_t> malloc_costtime = 0;std::atomic<size_t> free_costtime = 0;for (size_t k = 0; k < nworks; ++k){vthread[k] = std::thread([&]() {std::vector<void*> v;v.reserve(ntimes);for (size_t j = 0; j < rounds; ++j){size_t begin1 = clock();for (size_t i = 0; i < ntimes; i++){v.push_back(ConcurrentAlloc(16));//v.push_back(ConcurrentAlloc((16 + i) % 8192 + 1));}size_t end1 = clock();size_t begin2 = clock();for (size_t i = 0; i < ntimes; i++){ConcurrentFree(v[i]);}size_t end2 = clock();v.clear();malloc_costtime += (end1 - begin1);free_costtime += (end2 - begin2);}});}for (auto& t : vthread){t.join();}printf("%u个线程并发执行%u轮次，每轮次malloc %u次: 花费：%u ms\\n",nworks, rounds, ntimes, (size_t)malloc_costtime);printf("%u个线程并发执行%u轮次，每轮次free %u次: 花费：%u ms\\n",nworks, rounds, ntimes, (size_t)free_costtime);printf("%u个线程并发malloc&free %u次，总计花费：%u ms\\n",nworks, nworks * rounds * ntimes, (size_t)(malloc_costtime + free_costtime));
}
int main()
{size_t n = 10000;std::cout << "==========================================================" << std::endl;BenchmarkConcurrentMalloc(n, 4, 10);std::cout << std::endl << std::endl;BenchmarkMalloc(n, 4, 10);std::cout << "==========================================================" << std::endl;return 0;
}

9. 使用tcmalloc源码中实现基数树进行优化

#pragma once
#include "Common.h"
#include "ObjectPool.h"// Single-level array
template <int BITS>
class TCMalloc_PageMap1 {
private:static const int LENGTH = 1 << BITS;void** array_;
public:typedef uintptr_t Number;explicit TCMalloc_PageMap1() {size_t size = sizeof(void*) << BITS;size_t alignSize = SizeClass::_RoundUp(size, 1 << PAGE_SHIFT);array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT);memset(array_, 0, sizeof(void*) << BITS);}// Return the current value for KEY. Returns NULL if not yet set,// or if k is out of range.void* get(Number k) const {if ((k >> BITS) > 0) {return NULL;}return array_[k];}// REQUIRES "k" is in range "[0,2^BITS-1]".// REQUIRES "k" has been ensured before.//// Sets the value 'v' for key 'k'.void set(Number k, void* v) {array_[k] = v;}
};
// Two-level radix tree
template <int BITS>
class TCMalloc_PageMap2 {
private:// Put 32 entries in the root and (2^BITS)/32 entries in each leaf.static const int ROOT_BITS = 5;static const int ROOT_LENGTH = 1 << ROOT_BITS;static const int LEAF_BITS = BITS - ROOT_BITS;static const int LEAF_LENGTH = 1 << LEAF_BITS;// Leaf nodestruct Leaf {void* values[LEAF_LENGTH];};Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodesvoid* (*allocator_)(size_t); // Memory allocator
public:typedef uintptr_t Number;explicit TCMalloc_PageMap2() {memset(root_, 0, sizeof(root_));PreallocateMoreMemory();}void* get(Number k) const {const Number i1 = k >> LEAF_BITS;const Number i2 = k & (LEAF_LENGTH - 1);if ((k >> BITS) > 0 || root_[i1] == NULL) {return NULL;}return root_[i1]->values[i2];}void set(Number k, void* v) {const Number i1 = k >> LEAF_BITS;const Number i2 = k & (LEAF_LENGTH - 1);ASSERT(i1 < ROOT_LENGTH);root_[i1]->values[i2] = v;}bool Ensure(Number start, size_t n) {for (Number key = start; key <= start + n - 1;) {const Number i1 = key >> LEAF_BITS;// Check for overflowif (i1 >= ROOT_LENGTH)return false;// Make 2nd level node if necessaryif (root_[i1] == NULL) {/*Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));if (leaf == NULL) return false;*/static ObjectPool<Leaf> leafPool;Leaf* leaf = leafPool.New();memset(leaf, 0, sizeof(*leaf));root_[i1] = leaf;}// Advance key past whatever is covered by this leaf nodekey = ((key >> LEAF_BITS) + 1) << LEAF_BITS;}return true;}void PreallocateMoreMemory() {// Allocate enough to keep track of all possible pagesEnsure(0, 1 << BITS);}
};// Three-level radix tree
template <int BITS>
class TCMalloc_PageMap3 {
private:// How many bits should we consume at each interior levelstatic const int INTERIOR_BITS = (BITS + 2) / 3; // Round-upstatic const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;// How many bits should we consume at leaf levelstatic const int LEAF_BITS = BITS - 2 * INTERIOR_BITS;static const int LEAF_LENGTH = 1 << LEAF_BITS;// Interior nodestruct Node {Node* ptrs[INTERIOR_LENGTH];};// Leaf nodestruct Leaf {void* values[LEAF_LENGTH];};Node* root_; // Root of radix treevoid* (*allocator_)(size_t); // Memory allocatorNode* NewNode() {Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));if (result != NULL) {memset(result, 0, sizeof(*result));}return result;}
public:typedef uintptr_t Number;explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {allocator_ = allocator;root_ = NewNode();}void* get(Number k) const {const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);const Number i3 = k & (LEAF_LENGTH - 1);if ((k >> BITS) > 0 ||root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) {return NULL;}return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];}void set(Number k, void* v) {ASSERT(k >> BITS == 0);const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);const Number i3 = k & (LEAF_LENGTH - 1);reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;}bool Ensure(Number start, size_t n) {for (Number key = start; key <= start + n - 1;) {const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1);// Check for overflowif (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)return false;// Make 2nd level node if necessaryif (root_->ptrs[i1] == NULL) {Node* n = NewNode();if (n == NULL) return false;root_->ptrs[i1] = n;}// Make leaf node if necessaryif (root_->ptrs[i1]->ptrs[i2] == NULL) {Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));if (leaf == NULL) return false;memset(leaf, 0, sizeof(*leaf));root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);}// Advance key past whatever is covered by this leaf nodekey = ((key >> LEAF_BITS) + 1) << LEAF_BITS;}return true;}void PreallocateMoreMemory() {}
};