高并发内存池 - central cache 回收内存接下来我们从 Thread Cache 层中进入到 Central Cache 层中完善回收内存的逻辑。对于从 Thread Cache 中截取的自由链表我们怎么处理呢要清楚一点自由链表中的空间可能属于不同的 Span我们要归还到它归属的 Span 中问题是现在如何确定它属于哪个 Span 呢答案就藏在地址中我们在 Span 中记录了它的页号在计算机系统中地址分配是由页为单位的如果我们能确定地址属于哪个页计算出它归属的页号再去查找对应的 Span就可以正确归还。所以具体的操作就是右移 PAGE_SHIFT 位去屏蔽它的页内偏移量算出页号。PAGE_SHIFT 是页框大小为 2 的几次幂这里我们假设页框大小为 8KB所以为 13但是现在有新的问题出现了难道我们每次都要遍历 Central Cache 桶中的 Span去确定页号么那最终的时间复杂度为O(n^2)这显然不能接受。我们需要一种映射关系让我们尽量使用O(1)的时间复杂度就可以查到对应的 Span自然想到了哈希表 unordered_map那将它定义在哪一层呢Central Cache 还是 Page Cache 呢定义在 Page Cache 中因为后续在 Page Cache 层中也要根据哈希表进行操作到那时我们再进行讲解。所以 Page Cache 的实现中要添加进哈希表classPageCache{public:staticPageCache*GetInstance(){return_sInst;}Span*NewSpan(size_t k);//要的 Span 长度为几页std::mutex _pageMtx;//桶锁在 PageCache 中是行不通的需要整体上锁staticPageCache _sInst;private:SpanList _spanLists[NPAGES];std::unordered_mapPAGE_ID,Span*_idSpanMap;//记录页号和对应起始地址的哈希表PageCache(){}PageCache(constPageCache)delete;};在将哈希表定义后我们还需确定什么时候将 Span 添加进哈希表中哈希表一定是 Central Cache 层进行调用查找那意味着不分配给 Central Cache 层中的 Span 进入哈希表中无意义所以是在分割 Span 时将要分配给 Central Cache 层的 Span 推入哈希表中。那对于占据多页的 Span 怎么操作呢又时 Span 的大小可能不止为一页它可能跨越多个页号所以需要将他的所有页号都指向它的地址这就是解决多页 Span 的方法。在将疑惑解开后我们便可以对 NewSpan() 函数进行改造Span*PageCache::NewSpan(size_t k){assert(k0kNPAGES);//先检查第 k 个桶中是否还有 Spanif(!_spanLists[k].Empty())return_spanLists[k].PopFront();//猜的第三个坑没有加上 [k]//走到这里说明桶中为空要遍历 Page Cache 是否有大页 Span 可分割for(intik;iNPAGES;i){if(!_spanLists[i].Empty()){Span*spanN_spanLists[i].PopFront();Span*spanKnewSpan;//踩的第一个坑没有申请空间野指针直接使用spanK-_pageIdspanN-_pageId;spanK-_nk;spanN-_pageIdk;spanN-_n-k;_spanLists[spanN-_n].PushFront(spanN);//踩的第三个坑把 spanK 挂上去了//将要分配给 Thread Cache 的 Span 建立页号和地址的映射方便归还时寻找对应地址for(inti0;ispanK-_n;i){_idSpanMap[spanK-_pageIdi]spanK;//添加进哈希表中}returnspanK;}}//走到这里说明也没有大页 Span所以此时需要向堆申请空间Span*bigSpannewSpan;void*ptrSystemAlloc(NPAGES-1);//申请一个最大页数的 SpanbigSpan-_pageId(PAGE_ID)ptrPAGE_SHIFT;//踩的第二个坑左移右移逻辑踩坑bigSpan-_nNPAGES-1;_spanLists[bigSpan-_n].PushFront(bigSpan);returnNewSpan(k);//递归调用自己此时一定有大页 Span 可供分割}哈希表的部分解决还有一个问题Page Cache 还需实现从地址到页号的转换因为将哈希表定义在了 Page Cache 层中还需实现一个转换函数 MapObjectToSpan()将自由链表地址传入传回 Span 的地址。Span*MapObjectToSpan(void*obj);//实现页号到 Span 地址的转化代码实现Span*PageCache::MapObjectToSpan(void*obj){PAGE_ID id((PAGE_ID)objPAGE_SHIFT);autoret_idSpanMap.find(id);if(ret!_idSpanMap.end()){returnret-second;}else{assert(false);//如果找不到直接断言因为分配出的内存一定会被记录在哈希表中说明代码逻辑出现错误returnnullptr;}}那现在我们就可以回到 Central Cache 层中继续梳理逻辑在获取 Span 的地址后便将空间插入它的自由链表中归还空间我们还在 Span 中定义过一个 _useCount 参数使它--体现归还一个空间循环遍历需要归还的自由链表不断归还直至为 nullptr。不要忘记上桶锁因为会对 SpanList 中的 Span 的结构发生改变。代码实现voidCentralCache::RealeaseListToSpan(void*start,size_t byte_size){intindexSizeClass::Index(byte_size);_spanlists[index]._mtu.lock();//不要忘记上桶锁会对 Span 结构进行改变while(start){Span*spanPageCache::GetInstance()-MapObjectToSpan(start);//获取对应页号的 Span 地址void*nextObjNext(start);ObjNext(start)span-_freelist;span-_freeliststart;span-_useCount--;startnext;}_spanlists[index]._mtu.unlock();}那这个函数真的就到此结束了么并没有其中不用的 Span 应该被归还到 Page Cache 层中但满足什么条件下该 Span 才应该被归还呢我们记录了每个 Span 的 _useCount当它为 0 时说明此时它的空间没有一个被分配到 Thread Cache 中它是完整的没有使用的所以此时它就应该被归还到 Page Cache 层中。此时 Page Cahce 层中将归还函数命名为 RealeaseSpanToPageCache()。voidRealeaseSpanToPageCache(Span*span);//将 Span 归还到 PageCache 中不要忘记在调用此函数时将整个 Page Cache 上锁。同样的在调用此函数时将 Central Cache 的桶锁解开因为此时并不会影响 SpanList 的结构其他线程可能有归还与申请的请求他们仍要使用。所以最后 Central Cache 的回收函数实现voidCentralCache::RealeaseListToSpan(void*start,size_t byte_size){intindexSizeClass::Index(byte_size);_spanlists[index]._mtu.lock();while(start){Span*spanPageCache::GetInstance()-MapObjectToSpan(start);//获取对应页号的 Span 地址void*nextObjNext(start);ObjNext(start)span-_freelist;span-_freeliststart;span-_useCount--;if(span-_useCount0)//如果 Span 的空间都已经被悉数归还{_spanlists[index].Erase(span);span-_nextnullptr;span-_prevnullptr;span-_freelistnullptr;//此时可以把桶锁解开因为 Page Cache 中的操作不会影响同便于别的线程归还和申请空间_spanlists[index]._mtu.unlock();PageCache::GetInstance()-_pageMtx.lock();PageCache::GetInstance()-RealeaseSpanToPageCache(span);PageCache::GetInstance()-_pageMtx.unlock();_spanlists[index]._mtu.lock();}startnext;}_spanlists[index]._mtu.unlock();}下一篇文章我们会进入 Page Cache 中去实现回收函数的逻辑我们下一篇文章见。