网页代理访问,快速优化网站排名的方法,网站群建设进度,怎样让百度收取我的网站目录
ThreadCache的内存回收机制
补充内容1
补充内容2
补充内容3
补充内容4
ListTooLong函数的实现
CentralCache的内存回收机制
MapObjectToSpan函数的实现
ReleaseListToSpans函数的实现
PageCache的内存回收机制
补充内容1
补充内容2
ReleaseSpanToPageCache函…目录
ThreadCache的内存回收机制
补充内容1
补充内容2
补充内容3
补充内容4
ListTooLong函数的实现
CentralCache的内存回收机制
MapObjectToSpan函数的实现
ReleaseListToSpans函数的实现
PageCache的内存回收机制
补充内容1
补充内容2
ReleaseSpanToPageCache函数的实现
阶段性代码展示
Common.h
ObjectPool.h
ConcurrentAlloc.h
PageCache.h
CentralCache.h
ThreadCache.h
PageCache.cpp
CentralCache.cpp
ThreadCache.cpp
unitTest.cpp
调试过程
新增函数TestConcurrentAlloc2
内存释放流程图 ThreadCache的内存回收机制
补充内容1 在FreeList类中新增PopRange函数用于一次性删除_maxsize个内存结点 //头删n个内存结点或者叫剔除因为这些内存结点只不过是从freelist中拿出来了并未消失
void PopRange(void* start, void* end, size_t n)
{assert(n _size);//要剔除的结点个数不能大于当前链表中结点的个数start end _freeList;for (size_t i 0; i n - 1; i){end NextObj(end);}_freeList NextObj(end);NextObj(end) nullptr;_size - n;
} 补充内容2 在FreeList类中新增记录当前链表中内存结点个数的变量_size 同时在Pop、Push、PushRange、PopRange函数中增加计数操作 //管理切分好的小对象的自由链表
class FreeList
{
public:...//返回当前链表中结点的个数size_t Size(){return _size;}private:void* _freeList nullptr;size_t _maxSize 1;//记录当前freelist一次性最多向CentralCache申请多少个内存结点size_t _size 0;//当前链表中结点的个数
};补充内容3 在Deallocate函数中新增是否向CentralCache返回内存结点的判断 //释放ThreadCache中的内存
void ThreadCache::Deallocate(void* ptr, size_t size)
{assert(ptr);assert(size MAX_BYTES);//找对映射的自由链表桶并将用完的对象插入进去size_t index SizeClass::Index(size);_freeLists[index].Push(ptr);//当还回来后当前自由链表的内存结点个数大于当前链表一次性可以向CentralCache申请的内存结点个数_maxsize就将当前自由链表中_maxsize个内存结点归还给CentralCache//如果只归还多出的那一小部分内存结点_size-_maxsize会导致ThreadCache和CentralCache进行频繁的交互增加系统调用和锁竞争的次数从而降低整体性能if (_freeLists[index].Size() _freeLists[index].MaxSize()){ListTooLong(_freeLists[index], size);}
}补充内容4 在FetchFromCentralCache函数中调用PushRange函数时新增表示插入结点个数的参数 actualNum - 1是因为此时有一个已经被申请者使用了添加是为了_size的计数 ListTooLong函数的实现
注意事项记得在ThreadCache类中新增ListTooLong函数的声明
//释放内存结点导致自由链表结点个数过多时依据当前自由链表一次性最多向CentralCache申请的内存结点的个数向CentralCache归还这么多的内存结点
void ListTooLong(FreeList list, size_t size);
//链表结点过多
void ThreadCache::ListTooLong(FreeList list, size_t size)
{//输出型参数void* start nullptr;void* end nullptr;list.PopRange(start, end, list.MaxSize());CentralCache::GetInstance()-ReleaseListToSpans(start,size);
}
CentralCache的内存回收机制
MapObjectToSpan函数的实现
功能确定从ThreadCache归还回的内存结点都属于哪个span
注意事项记得在PageCache类中新增MapObjectToSpan函数的声明
//内存结点的地址-页号-span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{size_t id ((size_t)obj PAGE_SHIFT);//页号 内存结点的地址 / 页大小 auto ret _idSpanMap.find(id);//在_idSpanMap中寻找对应的span地址if (ret ! _idSpanMap.end()){return ret-second;//找到了就返回该span的地址}else{assert(false);//找不到就报错return nullptr;}
}
ReleaseListToSpans函数的实现
注意事项归还内存结点前先将当前的SpanList上锁在归还完成后再解锁每向某个span归还一个内存结点就将该span的_useCount--再判断该span的_useCount 0时将该span归还给PageCache最后记得在CentralCache类中新增ReleaseListToSpans函数的声明
//将从ThreadCache获得内存结点归还给它们所属的span因为这些内存结点可能是由CentralCache同一桶中的不同span分配的
//前一个span用完了从后一个span中获取同时前一个span可能还会接收从ThreadCache归还回来的内存结点下次分配时可能又可以从前面的span分配了多线程考虑的有点多
void CentralCache::ReleaseListToSpans(void* start, size_t size)
{size_t index SizeClass::Index(size);_spanLists[index]._mtx.lock();//start指向的是一串内存结点的头结点while (start){void* next NextObj(start);//归还的内存结点可能隶属于不同的span所以每次插入时需要判断Span* span PageCache::GetInstance()-MapObjectToSpan(start);//确定要归还的span//头插内存结点到span中NextObj(start) span-_freelist;span-_freelist start;span-_useCount--;//_useCount--表示有一个分配出去的小块内存回到当前span//当前span的_useCount为0表示当前span切分出去的所有小块内存都回来了直接将整个span还给PageCache,PageCache再尝试进行前后页的合并if (span-_useCount 0){_spanLists[index].Erase(span);//将当前的span从CentralCache的某个桶处的SpanList上取下//参与到PageCache中进行合并的span不需要自由链表等内容置空即可span-_freelist nullptr;span-_next nullptr;span-_prev nullptr;_spanLists[index]._mtx.unlock();//不用了就解锁,避免对CentralCache中同一桶的锁竞争PageCache::GetInstance()-_pageMtx.lock();//为PageCache上锁PageCache::GetInstance()-ReleaseSpanToPageCache(span);//尝试合并前后页PageCache::GetInstance()-_pageMtx.unlock();//为PageCache解锁_spanLists[index]._mtx.lock();//合并完后还要再上锁为了让当前线程走完ReleaseListToSpans函数 }start next;}_spanLists[index]._mtx.unlock();//当前线程走完ReleaseListToSpans函数解锁
} PageCache的内存回收机制
补充内容1 在PageCache类中新增unordered_map类型的成员变量_idSpanMap 在NewSpan分裂span以及从PageCache直接返回span时填写页号和span的映射关系 解释我们无法直接通过从Thread Cache中归还的内存结点的地址确定该内存结点要被归还给CentralCache中的哪个span需要先将该内存结点的地址转换为页号内存结点都是从页中分配的再通过页号和span的映射关系确定要归还的span是哪个
//建立页号和span间得映射关系
std::unordered_mapsize_t, Span* _idSpanMap; //获取一个非空span
Span* PageCache::NewSpan(size_t k)
{assert(k 0 k NPAGES);//先检查PageCache的第k个桶中有没有span,有就直接头删并返回if (!_spanLists[k].Empty()){Span* kSpan _spanLists[k].PopFront();//保存页号和span的映射关系//因为留在PacgeCache中的span只存放了其首尾页号和其的对应关系而此时该span要被分配给CentralCache了在CentralCache要被切分成小内存块小内存块从ThreadCache归还时需要依据小内存块的地址确定所属span故要简历该span中所有页号和该span的对应关系for (size_t i 0; i kSpan-_n; i){_idSpanMap[kSpan-_PageId i] kSpan;}return kSpan;}//走到这儿代表k号桶为空,检查后面的桶有没有大的span分裂一下for (size_t i k 1; i NPAGES; i)//因为第一个要询问的肯定是k桶的下一个桶所以i k 1{//k页的span返回给CentralCache,i-k页的span挂到i-k号桶中均需要存储页号和span的映射关系if (!_spanLists[i].Empty()){Span* nSpan _spanLists[i].PopFront();Span* kSpan _spanPool.New();//在nSpan头部切一个k页的span下来kSpan-_PageId nSpan-_PageId;kSpan-_n k;nSpan-_PageId k;//nSpan管理的首页页号变为了i knSpan-_n - k;//nSpan管理的页数变为了i - k_spanLists[nSpan-_n].PushFront(nSpan);//将nSpan重新挂到PageCache中的第nSpan-_n号桶中即第i - k号桶//存储nSpan的首尾页号跟nSpan的映射关系,便于PageCache回收内存时的合并查找_idSpanMap[nSpan-_PageId] nSpan;_idSpanMap[nSpan-_PageId nSpan-_n - 1] nSpan;//在span分裂后就建立页号和span得映射关系便于CentralCahe在回收来自ThreadCache的小块内存时找到那些小内存块所属的spanfor (size_t i 0; i kSpan-_n; i){_idSpanMap[kSpan-_PageId i] kSpan;}return kSpan;}}//走到这里就说明PageCache中没有合适的span了此时就去找堆申请一个管理128页的spanSpan* bigSpan _spanPool.New();void* ptr SystemAlloc(NPAGES - 1);//ptr指向从堆分配的内存空间的起始地址//计算新span的页号管理的页数等bigSpan-_PageId (size_t)ptr PAGE_SHIFT;//页号 起始地址 / 页大小bigSpan-_n NPAGES - 1;_spanLists[bigSpan-_n].PushFront(bigSpan);return NewSpan(k);//重新调用一次自己那么此时PageCache中就有一个管理k页的span了可以从PageCache中直接分配了在for循环中就会return//可以代码复用且循环只有128次的递归消耗的资源很小
}
补充内容2 在Span类中新增变量_isUse用于标记当前span的状态 为true表示在被使用为false表示未被使用 在PageCache为CentralCache分配span时将_isUse设为true 在GetOneSpan函数执行完NewSpan函数后 CentralCache归还的span在PageCache中挂起后将_isUse设为falseReleaseSpanToPageCache函数的末尾 struct Span
{...bool _isUse false;//初始时设为false因为所有span都是从PageCache中得到的
}ReleaseSpanToPageCache函数的实现
注意事项 记得在PageCache类中新增ReleaseSpanToPageCache函数的声明
//接收CentralCache中归还的span并尝试合并该span的相邻空闲页使得该span变成一个管理更多页的span
void ReleaseSpanToPageCache(Span* span);
停止合并原则
前/后页不存在通过页号查找不到span表示该span未在PageCache中出现过前/后页所属的span被占用该span在PageCache中出现过但此时被分给了CentralCache合并后的总页数大于128查找的span在PageCache中但和当前span合并后页数大于128
//合并页
void PageCache::ReleaseSpanToPageCache(Span* span)
{ //向前合并while (1){size_t prevId span-_PageId - 1;//获取前页的页号auto ret _idSpanMap.find(prevId);//由页号确定在哈希表中的位置//通过页号查找不到span表示该span未在PageCache中出现过不合并if (ret _idSpanMap.end()){break;}//该span在PageCache中出现过但此时被分给了CentralCache不合并Span* prevSpan ret-second;if (prevSpan-_isUse true){break;}//查找的span在PageCache中但和当前span合并后页数大于128不合并if (prevSpan-_n span-_n NPAGES - 1){break;}_spanLists[prevSpan-_n].Erase(prevSpan);//将PageCache中prevSpan-_n桶处的span进行删除span-_PageId prevSpan-_PageId;span-_n prevSpan-_n;delete prevSpan;}//向后合并while (1){size_t nextId span-_PageId span-_n;//当前span管理的页的后一个span的首页页号auto ret _idSpanMap.find(nextId);//获取页号对应的桶位置//通过页号查找不到span表示该span未在PageCache中出现过不合并if (ret _idSpanMap.end()){break;}//该span在PageCache中出现过但此时被分给了CentralCache不合并Span* nextSpan ret-second;if (nextSpan-_isUse true){break;}//查找的span在PageCache中但和当前span合并后页数大于128不合并if (nextSpan-_n span-_n NPAGES - 1){break;}span-_n nextSpan-_n;_spanLists[nextSpan-_n].Erase(nextSpan);delete nextSpan;}_spanLists[span-_n].PushFront(span);//将合并后的span在PageCache中挂起//重新存放首尾页的映射关系_idSpanMap[span-_PageId] span;_idSpanMap[span-_PageId span-_n - 1] span;span-_isUse false;//将当前span的_isUse设为false
}
阶段性代码展示
Common.h
#pragma once
#include iostream
#include vector
#include thread
#include unordered_map
#include time.h
#include assert.h
#include Windows.h
#include mutexusing std::cout;
using std::endl;//static const 和 const static 效果相同表示当前变量仅会在当前文件中出现static const size_t MAX_BYTES 256 * 1024;//规定单次向ThreadCache中申请的内存不超过256KB
static const size_t NFREELIST 208; //规定ThreadCache和CentralCache中哈希桶的数量为208
static const size_t NPAGES 129; //规定PageCache中span存放的最大页数为129
static const size_t PAGE_SHIFT 13; //规定一个页的大小为2的13次方字节即8KB//Windows环境下通过封装Windows提供的VirtualAlloc函数直接向堆申请以页为单位的内存而不使用malloc/new
inline static void* SystemAlloc(size_t kpage)//kpage表示页数
{
#ifdef _WIN32void* ptr VirtualAlloc(0, kpage PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#endifif (ptr nullptr)throw std::bad_alloc();//申请失败的抛异常return ptr;
}//调用Winodws提供的VirtualFree函数释放从堆申请的内存而不使用free/delete
inline static void SystemFree(void* ptr)
{VirtualFree(ptr, 0 ,MEM_RELEASE);
}//获取下一个结点的地址
//static限制NextObj的作用域防止其它文件使用extern访问NextObj函数传引用返回减少拷贝消耗
static void* NextObj(void* obj)
{return *(void**)obj;
}//管理切分好的小对象的自由链表
class FreeList
{
public://头插void Push(void* obj){assert(obj);NextObj(obj) _freeList;_freeList obj;_size;}//一次性插入n个结点void PushRange(void* start, void* end,size_t n){NextObj(end) _freeList;_freeList start;_size n;}//头删void* Pop(){assert(_freeList);//当前负责释放内存结点的自由链表不能为空void* obj _freeList;_freeList NextObj(obj);--_size;return obj;}//头删n个内存结点或者叫剔除因为这些内存结点只不过是从freelist中拿出来了并未消失void PopRange(void* start, void* end, size_t n){assert(n _size);//要剔除的结点个数不能大于当前链表中结点的个数start end _freeList;for (size_t i 0; i n - 1; i){end NextObj(end);}_freeList NextObj(end);NextObj(end) nullptr;_size - n;}//判空当前自由链表是否为空bool Empty(){return _freeList nullptr;}//返回当前freelist一次性最多向CentralCache申请多少个内存结点size_t MaxSize(){return _maxSize;}//返回当前链表中结点的个数size_t Size(){return _size;}private:void* _freeList nullptr;size_t _maxSize 1;//记录当前freelist一次性最多向CentralCache申请多少个内存结点size_t _size 0;//当前链表中结点的个数
};//存放常用计算函数的类
class SizeClass
{
public://基本原则申请的内存越大所需要的对齐数越大整体控制在最多10%左右的内碎片浪费如果要的内存是15byte那么在1,128范围内按8byte对齐后的内碎片应该为11/160.0625四舍五入就是百分之十//[1,128] 按8byte对齐 freelist[016) 128 / 8 16//[1281.1024] 按16byte对齐 freelist[1672) 896 / 16 56//[10241,8*1024] 按128byte对齐 freelist[72128) ...//[8*10241,64*1024] 按1024byte对齐 freelist[128184) ...//[64*10241,256*1024] 按8*1024byte对齐 freelist[184208) ...//内联函数在程序的编译期间在使用位置展开一般是简短且频繁使用的函数减少函数调用产生的消耗增加代码执行效率static inline size_t _RoundUp(size_t bytes, size_t alignNum)//申请的内存大小规定的对齐数{size_t alignSize 0;//对齐后的内存大小if (bytes % alignNum ! 0)//不能按与之配对的对齐数进行对齐的就按照与其一起传入的对齐数进行对齐计算{alignSize (bytes / alignNum 1) * alignNum;//bytes 50 alignNum 8对齐后大小就为56}else//能按与其配对的对齐数进行对齐的对齐后大小就是传入的申请内存大小{alignSize bytes;//bytes 16 alignNum 8对齐后大小就为16}return alignSize;}//内存对齐static inline size_t RoundUp(size_t size){if (size 128){return _RoundUp(size, 8);}else if (size 1024){return _RoundUp(size, 16);}else if (size 8 * 1024){return _RoundUp(size, 128);}else if (size 64 * 1024){return _RoundUp(size, 1024);}else if (size 256 * 1024){return _RoundUp(size, 8 * 1024);}else{assert(false);return -1;}}static inline size_t _Index(size_t bytes, size_t align_shift){return ((bytes (1 align_shift) - 1) align_shift) - 1;}//寻找桶位置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){return _Index(bytes - 128, 4) group_array[0];//加上上一个范围内的桶的个数}else if (bytes 8 * 1024){return _Index(bytes - 1024, 7) group_array[0] group_array[1];}else if (bytes 64 * 1024){return _Index(bytes - 8 * 1024, 10) group_array[0] group_array[1] group_array[2];}else if (bytes 256 * 1024){return _Index(bytes - 64 * 1024, 13) group_array[0] group_array[1] group_array[2] group_array[3];}else{assert(false);return -1;}}//理论上当前自由链表一次性要向CentralCache申请的结点个数static size_t NumMoveSize(size_t size){assert(size 0);//num∈[2,512]int num MAX_BYTES / size;if (num 2)//最少要給2个{//num 256KB / 512KB 0.5 ≈ 1 个//num越小表示单次申请所需的内存越大而给太少不合适num 2;}if (num 512)//最多能给512个{//num 256KB / 50Byte ≈ 5242个//num越大表示单次申请所需的内存越小而给太多不合适会导致分配耗时太大num 512;}return num;}//一次性要向堆申请多少个页static size_t NumMovePage(size_t size){size_t batchnum NumMoveSize(size);size_t npage (batchnum * size) PAGE_SHIFT;//最多可以分配的内存结点个数 * 单个内存结点的大小 / 每个页的大小if (npage 0)//所需页数小于1就主动给分配一个npage 1;return npage;}
};struct Span
{size_t _PageId 0;//当前span管理的连续页的起始页的页号size_t _n 0;//当前span管理的页的数量Span* _next nullptr;Span* _prev nullptr;size_t _useCount 0;//当前span中切好小块内存被分配给thread cache的数量void* _freelist nullptr; //管理当前span切分好的小块内存的自由链表bool _isUse false;//判断当前span是否在被使用如果没有则可以在PageCache中合成更大页
};//管理某个桶下所有span的数据结构带头双向循环链表
class SpanList
{
public://构造初始的SpanListSpanList(){_head new Span;_head-_next _head;_head-_prev _head;}//返回指向链表头结点的指针Span* Begin(){return _head-_next;}//返回指向链表尾结点的指针Span* End(){return _head;}//头插void PushFront(Span* span){Insert(Begin(), span);}//在pos位置前插入//位置描述:prev newspan posvoid Insert(Span* pos, Span* newSpan){assert(pos newSpan);Span* prev pos-_prev;prev-_next newSpan;newSpan-_prev prev;newSpan-_next pos;pos-_prev newSpan;}//头删Span* PopFront(){Span* front _head-_next;//_head-_next指向的是那个有用的第一个结点而不是哨兵位Erase(front);return front;//删掉后就要用所以要返回删掉的那块内存的地址 }//删除pos位置的span//位置描述prev pos nextvoid Erase(Span* pos){assert(pos pos ! _head);//指定位置不能为空且删除位置不能是头节点//暂存一下位置Span* prev pos-_prev;Span* next pos-_next;prev-_next next;next-_prev prev;}//判断是否为空bool Empty(){return _head-_next _head;}std::mutex _mtx; //桶锁
private:Span* _head nullptr;
};
ObjectPool.h
#include Common.h
templateclass T//模板参数T
class ObjectPool
{
public: //为T类型的对象构造一大块内存空间T* New(){T* obj nullptr;if (_freelist ! nullptr){//头删void* next *((void**)_freelist);obj _freelist;_freelist next;return obj;}else//自由链表没东西才会去用大块内存{//剩余内存不够一个T对象大小时重新开大块空间if (_remainBytes sizeof(T)){_remainBytes 128 * 1024;_memory (char*)SystemAlloc(_remainBytes 13);//SystemAlloc替换了原来这里的mallocif (_memory nullptr){throw std::bad_alloc();}}obj (T*)_memory;size_t objsize sizeof(T) sizeof(void*) ? sizeof(void*) : sizeof(T);_memory objsize;_remainBytes - objsize;}//定位new显示调用T的构造函数初始化new(obj)T;return obj;}//回收内存void Delete(T* obj)//obj指向要回收的对象的指针{//显示调用析构函数清理对象obj-~T();//头插*(void**)obj _freelist;_freelist obj;}private:char *_memory nullptr;//指向申请的大块内存的指针size_t _remainBytes 0;//大块内存中剩余可分配字节数void* _freelist nullptr;//指向存放归还回来内存结点的自由链表
};
ConcurrentAlloc.h
#pragma once
#include ThreadCache.h
#include PageCache.h//线程局部存储TLS是一种变量的存储方法这个变量在它所在的线程内是安全可访问的但是不能被其它线程访问这样就保持了数据的线程独立性。//后续代码完成后线程会通过调用本函数进行内存申请类似于malloc
static void* ConcurrentAlloc(size_t size)
{//通过TLS方法每个线程可以无锁的获取自己专属的ThreadCache对象if (pTLSThreadCache nullptr){pTLSThreadCache new ThreadCache;}//获取线程id检测两个线程是否分到两个不同的pTLSThreadCachecout std::this_thread::get_id() : pTLSThreadCache endl;//Allocate函数执行时可能会经历很多文件才能返回返回的结果就是申请到的内存的地址return pTLSThreadCache-Allocate(size);
}//线程会调用本函数释放内存类似于free
static void ConcurrentAlloc(void* ptr,size_t size)
{assert(pTLSThreadCache);//理论上释放时pTLSThreadCache不会为空pTLSThreadCache-Deallocate(ptr,size);//释放内存结点给ThreadCache
}
PageCache.h
#pragma once
#include Common.h
#include ObjectPool.hclass PageCache
{
public:static PageCache* GetInstance(){return _sInst;}//获取一个管理k页的span也许获取的是PageCache现存的span也许是向堆新申请的spanSpan* NewSpan(size_t k);//获取从内存结点的地址到span的映射Span* MapObjectToSpan(void* obj);//接收CentralCache中归还的span并尝试合并该span的相邻空闲页使得该span变成一个管理更多页的spanvoid ReleaseSpanToPageCache(Span* span);std::mutex _pageMtx;//pagecache不能用桶锁,只能用全局锁,因为后面可能会有span的合并和分裂
private:SpanList _spanLists[NPAGES];std::unordered_mapsize_t, Span* _idSpanMap;//存放页号和span的映射关系PageCache() {}PageCache(const PageCache) delete;static PageCache _sInst;
};
CentralCache.h
#pragma once
#include Common.hclass CentralCache
{
public://获取实例化好的CnetralCache类型的静态成员对象的地址static CentralCache* GetInstance(){return _sInst;}//为ThreadCache分配一定数量的内存结点size_t FetchRangeObj(void* start, void* end, size_t batchNum, size_t size);//从SpanList中获取一个非空的span如果SpanList没有则会去问PageCache申请Span* GetOneSpan(SpanList list, size_t size);//将ThreadCache归还的重新挂在CentralCache中的某个span上void ReleaseListToSpans(void* start, size_t size);private:SpanList _spanLists[NFREELIST];//单例模式的实现方式是构造函数和拷贝构造函数私有化CentralCache() {}CentralCache(const CentralCache) delete;static CentralCache _sInst;//静态成员变量在编译时就会被分配内存
};
ThreadCache.h
#pragma once
#include Common.hclass ThreadCache
{
public://分配ThreadCache中的内存void* Allocate(size_t bytes);//释放ThreadCache中的内存void Deallocate(void* ptr, size_t size);//从CentralCache中获取内存结点void* FetchFromCentralCache(size_t index, size_t size);//释放内存结点导致自由链表结点个数过多时依据当前自由链表一次性最多向CentralCache申请的内存结点的个数向CentralCache归还这么多的内存结点void ListTooLong(FreeList list, size_t size);
private:FreeList _freeLists[NFREELIST];//ThreadCache的208个桶下都是自由链表
};//TLS无锁技术
//static保证该指针只在当前文件可见防止因为多个头文件包含导致的链接时出现多个相同名称的指针
static _declspec(thread) ThreadCache* pTLSThreadCache nullptr;
PageCache.cpp
#include PageCache.hPageCache PageCache::_sInst;//int i 0;//内存申请的测试代码//从PageCache中获取一个新的非空span
Span* PageCache::NewSpan(size_t k)
{assert(k 0 k NPAGES);//i;//if (i 3)//{// cout 获取一个新的span endl;//}//先检查PageCache的第k个桶中有没有span,有就头删if (!_spanLists[k].Empty()){return _spanLists[k].PopFront();}//检查该桶后面的大桶中是否有span如果有就进行span分裂for (size_t i k 1; i NPAGES; i)//因为第一个要询问的肯定是k桶的下一个桶所以i k 1{//后续大桶有span执行span的分裂if (!_spanLists[i].Empty()){Span* nSpan _spanLists[i].PopFront();Span* kSpan new Span;//在nSpan头部切一个k页的span下来kSpan-_PageId nSpan-_PageId;kSpan-_n k;nSpan-_PageId k;nSpan-_n - k;_spanLists[nSpan-_n].PushFront(nSpan);//存储nSpan的首尾页号跟nSpan的映射关系,便于PageCache回收内存时的合并查找_idSpanMap[nSpan-_PageId] nSpan;_idSpanMap[nSpan-_PageId nSpan-_n - 1] nSpan;//在span分裂后就建立页号和span得映射关系便于CentralCahe在回收来自ThreadCache的小块内存时找到对应的spanfor (size_t i 0; i kSpan-_n; i){_idSpanMap[kSpan-_PageId i] kSpan;}return kSpan;}}//走到这里就说明PageCache中没有合适的span了此时就去找堆申请一个管理128页的spanSpan* bigSpan new Span;void* ptr SystemAlloc(NPAGES - 1);//ptr存放堆分配的span的起始地址bigSpan-_PageId (size_t)ptr PAGE_SHIFT;//由地址计算页号页号 起始地址 / 页大小使用位运算更快bigSpan-_n NPAGES - 1;//新的大span中管理的页的数量为128个_spanLists[bigSpan-_n].PushFront(bigSpan);return NewSpan(k);//重新调用一次自己那么此时PageCache中就有一个管理k页的span了可以从PageCache中直接分配了不需要再考虑该返回什么//可以代码复用递归消耗的资源很小
}//内存结点的地址-页号-span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{size_t id ((size_t)obj PAGE_SHIFT);//页号 内存结点的地址 / 页大小 auto ret _idSpanMap.find(id);//在_idSpanMap中寻找对应的span地址if (ret ! _idSpanMap.end()){return ret-second;//找到了就返回该span的地址}else{assert(false);//找不到就报错return nullptr;}
}//合并页
void PageCache::ReleaseSpanToPageCache(Span* span)
{ //向前合并while (1){size_t prevId span-_PageId - 1;//获取前页的页号auto ret _idSpanMap.find(prevId);//由页号确定在哈希表中的位置//通过页号查找不到span表示该span未在PageCache中出现过不合并if (ret _idSpanMap.end()){break;}//该span在PageCache中出现过但此时被分给了CentralCache不合并Span* prevSpan ret-second;if (prevSpan-_isUse true){break;}//查找的span在PageCache中但和当前span合并后页数大于128不合并if (prevSpan-_n span-_n NPAGES - 1){break;}_spanLists[prevSpan-_n].Erase(prevSpan);//将PageCache中prevSpan-_n桶处的span进行删除span-_PageId prevSpan-_PageId;span-_n prevSpan-_n;delete prevSpan;}//向后合并while (1){size_t nextId span-_PageId span-_n;//当前span管理的页的后一个span的首页页号auto ret _idSpanMap.find(nextId);//获取页号对应的桶位置//通过页号查找不到span表示该span未在PageCache中出现过不合并if (ret _idSpanMap.end()){break;}//该span在PageCache中出现过但此时被分给了CentralCache不合并Span* nextSpan ret-second;if (nextSpan-_isUse true){break;}//查找的span在PageCache中但和当前span合并后页数大于128不合并if (nextSpan-_n span-_n NPAGES - 1){break;}span-_n nextSpan-_n;_spanLists[nextSpan-_n].Erase(nextSpan);delete nextSpan;}_spanLists[span-_n].PushFront(span);//将合并后的span在PageCache中挂起//重新存放首尾页的映射关系_idSpanMap[span-_PageId] span;_idSpanMap[span-_PageId span-_n - 1] span;span-_isUse false;//将当前span的_isUse设为false
}
CentralCache.cpp
#include CentralCache.h
#include PageCache.h//定义
CentralCache CentralCache::_sInst;//实际可以从CentralCache中获取到的内存结点的个数
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);//获取一个非空span//span为空或者span管理的空间为空均不行assert(span);assert(span-_freelist);//尝试从span中获取batchNum个对象,若没有这么多对象的话,有多少就给多少start end span-_freelist;size_t actualNum 1;//已经判断过的自由链表不为空所以肯定有一个size_t i 0;//NextObj(end) ! nullptr用于防止actualNum小于bathcNum循环次数过多时NexeObj(end)中的end为nullptr导致的报错while (i batchNum - 1 NextObj(end) ! nullptr){end NextObj(end);i;actualNum;}//更新当前span的自由链表中span-_freelist NextObj(end);NextObj(end) nullptr;span-_useCount actualNum;//当前span中有actualNum个内存结点被分配给ThreadCache_spanLists[index]._mtx.unlock();//解桶锁return actualNum;
}//获取非空span
Span* CentralCache::GetOneSpan(SpanList list, size_t size)
{//遍历CentralCache当前桶中的SpanList寻找一个非空的spanSpan* it list.Begin();while (it ! list.End()){if (it-_freelist ! nullptr) {return it;}else{ it it-_next;}}//先把进来GetOneSpan前设置的桶锁解除避免其它线程释放内存时被阻塞list._mtx.unlock();size_t k SizeClass::NumMovePage(size);//SizeClass::NumMovePage(size)计算要向PageCache申请管理多少页的span即k//走到这里证明CentralCache当前桶中的SpanList中没有非空的span对象了需要向PageCache申请PageCache::GetInstance()-_pageMtx.lock();//为PageCache整体上锁Span* span PageCache::GetInstance()-NewSpan(k);PageCache::GetInstance()-_pageMtx.unlock();//为PageCache整体解锁span-_isUse true;//修改从PageCache获取到的span的状态为正在使用//从PageCache中获取的span是没有进行内存切分的需要进行切分并挂在其自由链表下//1、计算span管理下的大块内存的起始和结尾地址//起始地址 页号 * 页的大小char* start (char*)(span-_PageId PAGE_SHIFT);//选择char*而不是void*为了后续size的时移动size个字节//假设span-_PageId 5PAGE_SHIFT 135 13 40960字节//整数值 40960 表示内存中的一个地址位置通过 (char*) 显示类型转换后start 就指向了这个内存地址即span的起始地址char* end (char*)(start (span-_n PAGE_SHIFT));//end指向span的结束地址span管理的内存大小 span中页的个数 * 页大小 //2、将start和end指向的大块内存切成多个小块内存并尾插至自由链表中采用尾插使得即使被切割但在物理上仍为连续空间加快访问速度//①先切下来一块作为头结点便于尾插span-_freelist start;void* tail start;start size;//循环尾插while(start end){NextObj(tail) start;//当前tail指向的内存块的前4/8个字节存放下一个结点的起始地址即start指向的结点的地址start size;//更新starttail NextObj(tail);//更新tail}NextObj(tail) nullptr;//及时置空//向CentralCache中当前的SpanList头插前要上锁防止其它线程同时访问当前的SpanListlist._mtx.lock();list.PushFront(span);//将获取到的span插入当前桶中的SpanListreturn span;//此时该span已经放在了CentralCache的某个桶的SpanList中了返回该span的地址即可
}//将从ThreadCache获得内存结点归还给它们所属的span因为这些内存结点可能是由CentralCache同一桶中的不同span分配的
//前一个span用完了从后一个span中获取同时前一个span可能还会接收从ThreadCache归还回来的内存结点下次分配时可能又可以从前面的span分配了多线程考虑的有点多
void CentralCache::ReleaseListToSpans(void* start, size_t size)
{size_t index SizeClass::Index(size);_spanLists[index]._mtx.lock();//start指向的是一串内存结点的头结点while (start){void* next NextObj(start);Span* span PageCache::GetInstance()-MapObjectToSpan(start);//确定要归还的span//头插内存结点到span中NextObj(start) span-_freelist;span-_freelist start;span-_useCount--;//_useCount--表示有一个分配出去的小块内存回到当前span//当前span的_useCount为0表示当前span切分出去的所有小块内存都回来了直接将整个span还给PageCache,PageCache再尝试进行前后页的合并if (span-_useCount 0){_spanLists[index].Erase(span);//将当前的span从CentralCache的某个桶处的SpanList上取下//参与到PageCache中进行合并的span不需要自由链表等内容置空即可span-_freelist nullptr;span-_next nullptr;span-_prev nullptr;_spanLists[index]._mtx.unlock();//不用了就解锁,避免对CentralCache中同一桶的锁竞争PageCache::GetInstance()-_pageMtx.lock();//为PageCache上锁PageCache::GetInstance()-ReleaseSpanToPageCache(span);//尝试合并前后页PageCache::GetInstance()-_pageMtx.unlock();//为PageCache解锁_spanLists[index]._mtx.lock();//合并完后还要再上锁为了让当前线程走完ReleaseListToSpans函数 }start next;}_spanLists[index]._mtx.unlock();//当前线程走完ReleaseListToSpans函数解锁
}
ThreadCache.cpp
#include ThreadCache.h
#include CentralCache.h//分配ThreadCache中的内存
void* ThreadCache::Allocate(size_t size)
{assert(size MAX_BYTES);size_t allignSize SizeClass::RoundUp(size);//获取对齐后的大小size_t index SizeClass::Index(size);//确认桶的位置if (!_freeLists[index].Empty()){return _freeLists[index].Pop();//头删符合位置的桶的内存块表示释放出去一块可以使用的内存}else//ThreadCache中没有合适的内存空间{return FetchFromCentralCache(index, allignSize);//向CentralCache的相同位置处申请内存空间}
}//向CentralCache申请内存空间
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{//慢调节算法size_t batchNum min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));//bathcNum ∈ [2,512]if (_freeLists[index].MaxSize() batchNum){_freeLists[index].MaxSize() 1;}//上述部分是满调节算法得到的当前理论上一次性要向CentralCache申请的结点个数//下面是计算实际一次性可从CentralCache中申请到的结点个数//输出型参数传入FetchRangeObj函数的是它们的引用会对start和end进行填充void* start nullptr;void* end nullptr;//actualNum表示实际上可以从CentralCache中获取到的内存结点的个数size_t actualNum CentralCache::GetInstance()-FetchRangeObj(start, end, batchNum, size);assert(actualNum 1);//actualNum必定会大于等于1不可能为0因为FetchRangeObj还有GetOneSpan函数if (actualNum 1){assert(start end);//此时start和end应该都指向该结点return start;//直接返回start指向的结点即可}else{//如果从CentralCache中获取了多个内存结点,则将第一个返回给ThreadCache,然后再将剩余的内存挂在ThreadCache的自由链表中_freeLists[index].PushRange(NextObj(start), end,actualNum - 1);return start;}
}//释放ThreadCache中的内存
void ThreadCache::Deallocate(void* ptr, size_t size)
{assert(ptr);assert(size MAX_BYTES);//找对映射的自由链表桶并将用完的对象插入进去size_t index SizeClass::Index(size);_freeLists[index].Push(ptr);//当还回来后当前自由链表的内存结点个数大于当前链表一次性可以向CentralCache申请的内存结点个数_maxsize就将当前自由链表中_maxsize个内存结点归还给CentralCache//如果只归还多出的那一小部分内存结点_size-_maxsize会导致ThreadCache和CentralCache进行频繁的交互增加系统调用和锁竞争的次数从而降低整体性能if (_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());CentralCache::GetInstance()-ReleaseListToSpans(start,size);
}
unitTest.cpp
#include ObjectPool.h
#include ConcurrentAlloc.hvoid Alloc1()
{for (size_t i 0; i 5; i){void* ptr ConcurrentAlloc(6);}
}void Alloc2()
{for (size_t i 0; i 5; i){void* ptr ConcurrentAlloc(7);}
}void TLSTest()
{std::thread t1(Alloc1);//创建一个新的线程 t1并且在这个线程中执行 Alloc1 函数std::thread t2(Alloc2);//创建一个新的线程 t2并且在这个线程中执行 Alloc2 函数t1.join();t2.join();
}//申请内存过程的调试
void TestConcurrentAlloc()
{//void* p1 ConcurrentAlloc(6);//void* p2 ConcurrentAlloc(8);//void* p3 ConcurrentAlloc(1);//void* p4 ConcurrentAlloc(7);//void* p5 ConcurrentAlloc(8);//cout p1 endl;//cout p2 endl;//cout p3 endl;//cout p4 endl;//cout p5 endl;//尝试用完一整个spanfor (size_t i 0; i 1024; i){void* p1 ConcurrentAlloc(6);}//如果用完了一个新的span那么p2指向的地址应该是上一个用完的span的结尾地址void* p2 ConcurrentAlloc(8);cout p2 endl;
}int main()
{//TLSTest();//TestConcurrentAlloc()TestConcurrentAlloc2();return 0;
}
调试过程
新增函数TestConcurrentAlloc2
//释放内存过程的调试单线程
void TestConcurrentAlloc2()
{//比内存申请时的用例多加两个申请//因为只有这样才能成功使得某个span的_useCount 0进入PageCache中//初始_maxsize 1void* p1 ConcurrentAlloc(6);//分配一个_maxsize 2void* p2 ConcurrentAlloc(8);//不够再申请时因为_maxsize 2,所以分配2个用一剩一,_maxsize 3void* p3 ConcurrentAlloc(1);//用了剩的那个不用_maxsizevoid* p4 ConcurrentAlloc(7);//不够再申请时因为_maxsize 3,所以分配三个用一剩二_maxsize 4void* p5 ConcurrentAlloc(8);//用剩余的那两个不用_maxsizevoid* p6 ConcurrentAlloc(6);//用剩余的那两个不用_maxsizevoid* p7 ConcurrentAlloc(8);//不够再申请时因为_maxsize 4,所以分配4个用一剩三_maxsize 5void* p8 ConcurrentAlloc(6);//用剩余的三个不用_maxsize//此时_maxsize 5,_freeLists[0].size 2此时负责分配这10个8字节大小内存结点的span的_useCount 10后续调试时可以以此为标准//最终代码时不需要传入释放的大小这里我们先传入ConcurrentFree(p1, 6);ConcurrentFree(p2, 8);ConcurrentFree(p3, 1);ConcurrentFree(p4, 7);ConcurrentFree(p5, 8);ConcurrentFree(p6, 8);ConcurrentFree(p7, 8);ConcurrentFree(p8, 8);
}内存释放流程图 流程图有问题的话留下言我改一下 ~over~
