高并发内存池
目录
项目介绍：
什么是内存池：
内存池主要解决的问题：
定长内存池：
高并发内存池整体框架设计
高并发内存池--thread cache
申请内存：
释放内存：
thread cache代码框架：
详细解析：
高并发内存池--central cache
申请内存：
释放内存：
CentralCache 代码框架：
详细解析：
高并发内存池--page cache
申请内存：
释放内存：
PageCache 代码框架：
详细解析：
项目介绍：
当前项目是实现一个高并发的内存池，他的原型是google的一个开源项目tcmalloc，tcmalloc全称 Thread-Caching Malloc，即线程缓存的malloc，实现了高效的多线程内存管理，用于替代系统的内存 分配相关的函数（malloc、free）。
什么是内存池：
内存池是指程序预先从操作系统申请一块足够大内存，此后，当程序中需要申请内存的时候，不是直接 向操作系统申请，而是直接从内存池中获取。
同理，当程序释放内存的时候，并不真正将内存返回给操 作系统，而是返回内存池。当程序退出(或者特定时间)时，内存池才将之前申请的内存真正释放。
内存池主要解决的问题：
内存池主要解决的当然是效率的问题，其次如果作为系统的内存分配器的角度，还需要解决一下内存碎 片的问题。
那么什么是内存碎片呢？
定长内存池：
直接朝堆进行申请内存
高并发内存池整体框架设计
现代很多的开发环境都是多核多线程，在申请内存的场景下，必然存在激烈的锁竞争问题。
malloc本身 其实已经很优秀，那么我们项目的原型tcmalloc就是在多线程高并发的场景下更胜一筹，所以这次我们 实现的内存池需要考虑以下几方面的问题：
- 性能问题。
- 多线程环境下，锁竞争问题。
- 内存碎片问题。
concurrent memory pool主要由以下3个部分构成：
thread cache：
线程缓存是每个线程独有的，用于小于256KB的内存的分配，线程从这里申请内 存不需要加锁，每个线程独享一个cache，这也就是这个并发线程池高效的地方。
central cache：
中心缓存是所有线程所共享，thread cache是按需从central cache中获取的对 象。
central cache合适的时机回收thread cache中的对象，避免一个线程占用了太多的内存，而 其他线程的内存吃紧，达到内存分配在多个线程中更均衡的按需调度的目的。
central cache是存 在竞争的，所以从这里取内存对象是需要加锁，首先这里用的是桶锁，其次只有thread cache的 没有内存对象时才会找central cache，所以这里竞争不会很激烈。
page cache：
页缓存是在central cache缓存上面的一层缓存，存储的内存是以页为单位存储及分 配的，central cache没有内存对象时，从page cache分配出一定数量的page，并切割成定长大小 的小块内存，分配给central cache。
当一个span的几个跨度页的对象都回收以后，page cache 会回收central cache满足条件的span对象，并且合并相邻的页，组成更大的页，缓解内存碎片 的问题
高并发内存池--thread cache
thread cache是哈希桶结构，每个桶是一个按桶位置映射大小的内存块对象的自由链表。每个线程都会 有一个thread cache对象，这样每个线程在这里获取对象和释放对象时是无锁的。
申请内存：
- 当内存申请size<=256KB，先获取到线程本地存储的thread cache对象，计算size映射的哈希桶自 由链表下标i。
- 如果自由链表_freeLists[i]中有对象，则直接Pop一个内存对象返回。
- 如果_freeLists[i]中没有对象时，则批量从central cache中获取一定数量的对象，插入到自由链表 并返回一个对象。
释放内存：
- 当释放内存小于256k时将内存释放回thread cache，计算size映射自由链表桶位置i，将对象Push 到_freeLists[i]。
- 当链表的长度过长，则回收一部分内存对象到central cache。
高并发内存池 完整版/ThreadCache.cpp · start/malloc - 码云 - 开源中国 (gitee.com)
thread cache代码框架：
#pragma once
#include"Common.h"class ThreadCache
{public://提供两个接口，申请和释放空间void* Allocate(size_t size);//申请空间void Deallocate(void* ptr, size_t size);//释放空间// 从中心缓存获取对象void* FetchFromCentralCache(size_t index, size_t size);// 释放对象时，链表过长时，回收内存回到中心缓存void ListTooLong(FreeList& list, size_t size);private://因为要有多个自由链表，每个自由链表都是指定某个字节的，所以使用哈希桶的操作FreeList _freeLists[NFREELITS];
};//设置一个TLS也就是线程缓存的锁 声明后每一个线程都会有这个指针
//每一个线程起来之后都需要取调用相关接口 也就是concurrentAlloc 这个文件内部接口
static _declspec(thread) ThreadCache* pTLSThreadCache = nullptr;详细解析：
高并发内存池--central cache
central cache也是一个哈希桶结构，他的哈希桶的映射关系跟thread cache是一样的。不同的是他的每 个哈希桶位置挂是SpanList链表结构，不过每个映射桶下面的span中的大内存块被按映射关系切成了一 个个小内存块对象挂在span的自由链表中。
申请内存：
- 当thread cache中没有内存时，就会批量向central cache申请一些内存对象，这里的批量获取对 象的数量使用了类似网络tcp协议拥塞控制的慢开始算法；central cache也有一个哈希映射的 spanlist，spanlist中挂着span，从span中取出对象给thread cache，这个过程是需要加锁的，不 过这里使用的是一个桶锁，尽可能提高效率。
- central cache映射的spanlist中所有span的都没有内存以后，则需要向page cache申请一个新的 span对象，拿到span以后将span管理的内存按大小切好作为自由链表链接到一起。然后从span 中取对象给thread cache。
- central cache的中挂的span中use_count记录分配了多少个对象出去，分配一个对象给thread cache，就++use_count
释放内存：
- 当thread_cache过长或者线程销毁，则会将内存释放回central cache中的，释放回来时-- use_count。当use_count减到0时则表示所有对象都回到了span，则将span释放回page cache， page cache中会对前后相邻的空闲页进行合并。
高并发内存池 完整版/CentralCache.h · start/malloc - 码云 - 开源中国 (gitee.com)
CentralCache 代码框架：
#pragma once
#include"Common.h"
class CentralCache
{//单例模式
public:static CentralCache* GetInstance(){return &_sInst;}// 从中心缓存获取一定数量的对象给thread cache //参数分别是： 起始地址，末尾地址，拿多少内存，多大字节的/哪一个自由链表的size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size);// 获取一个非空的span//因为central内部的自由链表上的span很多，且会有内存归还和内存被瓜分干净的操作//所以我们需要对内存块进行寻找，寻找一个非空的spanSpan* GetOneSpan(SpanList& list, size_t byte_size);// 将一定数量的对象释放到span跨度void ReleaseListToSpans(void* start, size_t byte_size);private://中心层内部挂载的是一个以页位单位的大块内存块//挂载的每一个大块内存叫做span 而例如16字节自由链表内部挂载的span//而且span会将自己切割成许多个16字节的内存//当自由链表内部的span没有了，那么是去找下一层进行寻找//同时span这个内存块内部可能也没有内存 存在，同时一个span的内存也不会全给一个线程//当一个span用完了就会申请一个span，当span指向空后，表示span的内存全部被分配了//同时span内部有时候有内存有时候没内存，这是因为线程会还一些内存回来//同时span是一个双向链表，是因为当span内部的内存被归还后，span要把内存还给下一层也就是page层//还给page层做好一个上下页的合并，处理内存碎片问题//设置双向链表这就是为了删除好操作SpanList _spanLists[NFREELITS];//表示自由链表的数量和tread一样
private://初始化构造CentralCache(){}CentralCache(const CentralCache&) = delete;static CentralCache _sInst;};详细解析：
高并发内存池--page cache
申请内存：
- 当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。
- 如果找到_spanList[128]都没有合适的span，则向系统使用mmap、brk或者是VirtualAlloc等方式 申请128页page span挂在自由链表中，再重复1中的过程。
- 需要注意的是central cache和page cache 的核心结构都是spanlist的哈希桶，但是他们是有本质 区别的，central cache中哈希桶，是按跟thread cache一样的大小对齐关系映射的，他的spanlist 中挂的span中的内存都被按映射关系切好链接成小块内存的自由链表。而page cache 中的 spanlist则是按下标桶号映射的，也就是说第i号桶中挂的span都是i页内存。
释放内存：
- 如果central cache释放回一个span，则依次寻找span的前后page id的没有在使用的空闲span， 看是否可以合并，如果合并继续向前寻找。这样就可以将切小的内存合并收缩成大的span，减少 内存碎片
高并发内存池 完整版/PageCache.h · start/malloc - 码云 - 开源中国 (gitee.com)
PageCache 代码框架：
#pragma once
#include"Common.h"
#include"ObjectPool.h"//page cache 内部自由链表挂在的也是span
//且自由链表的映射规则和之前的不一致！它总共有128个自由链表1~128，且它自由链表内部的span不进行切割
//central cache朝page cache 申请的内存是内存块，是页数
class PageCache
{
public:static PageCache* GetInstance(){return &_sInstan;}// 获取从对象到span的映射Span* MapObjectToSpan(void* obj);// 释放空闲span回到Pagecache，并合并相邻的spanvoid ReleaseSpanToPageCache(Span* span);//获取一个k页的span//涉及锁的问题，假设2页的自由链表内部的span没有了，//因为没有所以可能会产生一个误区，会去找堆申请，但是堆给与的内存不一定是连续的//所以如果两页没有，那么会去找3页的自由链表找3页大小的span// 把3页的span进行切割变成一个2页和一个页的//这样1页的可以进行挂起，之后这个2页的回归后可以进行合并//同时最开始的自由链表是没有东西的，如果这时候要2页的span是往后面的自由链表寻找比2页大的//直到最后都没有页数，那就只能向系统申请一个128页的span 空间，然后挂到128自由链表位置上//然后现在需要的页数是2所以把128链表位置上的128页进行切割126页和2页，Span* NewSpan(size_t k);//再把126页放在126自由链表位置上，2页的放在2页的自由链表位置上，同时返回给central cache上//同时central 的span会进行切割成数个小内存块给thread 当thread把内存块归还给central时//central 的一个计数遍历会记载小内存块的数量，小内存块切割越多，这个计数变量++//小内存块回归这个计数变量会-- 当计数遍历不能--后，就表示central的这个span已经完全回归//central的一个span完全回归后，将把这个span归还给page cache//换回来的span 也就是页数，可以以页号基准，查看前方页号和后方页号，中是否有页是空闲的，//如果有空闲的页，则进行合并，前方查完查后方，前方合并完合并后方，这样就解决内存碎片问题了//锁std::mutex _pageMtx;private://表示自由链表有128个 但是为了映射设置为129，数组是从0开始的SpanList _spanLists[NPAGES];ObjectPool<Span>_spanPool;//设置一个页号和span的映射 //知道页号就可以直到地址，所以知道页号和span之间的映射，就可以找到span指针//就可以把对应的链表挂载对应的span上std::unordered_map<PAGE_ID, Span*> _idSpanMap;//设置成单例模式PageCache(){}PageCache(const PageCache&) = delete;static PageCache _sInstan;
};详细解析：
