【项目设计】高并发内存池(五)[释放内存流程及调通]
🎇C++学习历程:入门
- 博客主页:一起去看日落吗
- 持续分享博主的C++学习历程
- 博主的能力有限,出现错误希望大家不吝赐教
- 分享给大家一句我很喜欢的话: 也许你现在做的事情,暂时看不到成果,但不要忘记,树🌿成长之前也要扎根,也要在漫长的时光🌞中沉淀养分。静下来想一想,哪有这么多的天赋异禀,那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。
🍁 🍃 🍂 🌿
目录
- 🌿1. threadcache 回收内存
- 🌿2. centralcache 回收内存
- 🌿3. pagecache 回收内存
- 🌿4. 释放内存过程联调
🌿1. threadcache 回收内存
当某个线程申请的对象不用了,可以将其释放给thread cache,然后thread cache将该对象插入到对应哈希桶的自由链表当中即可。
但是随着线程不断的释放,对应自由链表的长度也会越来越长,这些内存堆积在一个thread cache中就是一种浪费,我们应该将这些内存还给central cache,这样一来,这些内存对其他线程来说也是可申请的,因此当thread cache某个桶当中的自由链表太长时我们可以进行一些处理。
如果thread cache某个桶当中自由链表的长度超过它一次批量向central cache申请的对象个数,那么此时我们就要把该自由链表当中的这些对象还给central cache。
//释放内存对象 void ThreadCache::Deallocate(void* ptr, size_t size) { assert(ptr); assert(size = _freeLists[index].MaxSize()) { ListTooLong(_freeLists[index], size); } }
当自由链表的长度大于一次批量申请的对象时,我们具体的做法就是,从该自由链表中取出一次批量个数的对象,然后将取出的这些对象还给central cache中对应的span即可。
(图片来源网络,侵删)//释放对象导致链表过长,回收内存到中心缓存 void ThreadCache::ListTooLong(FreeList& list, size_t size) { void* start = nullptr; void* end = nullptr; //从list中取出一次批量个数的对象 list.PopRange(start, end, list.MaxSize()); //将取出的对象还给central cache中对应的span CentralCache::GetInstance()->ReleaseListToSpans(start, size); }
从上述代码可以看出,FreeList类需要支持用Size函数获取自由链表中对象的个数,还需要支持用PopRange函数从自由链表中取出指定个数的对象。因此我们需要给FreeList类增加一个对应的PopRange函数,然后再增加一个_size成员变量,该成员变量用于记录当前自由链表中对象的个数,当我们向自由链表插入或删除对象时,都应该更新_size的值。
//管理切分好的小对象的自由链表 class FreeList { public: //将释放的对象头插到自由链表 void Push(void* obj) { assert(obj); //头插 NextObj(obj) = _freeList; _freeList = obj; _size++; } //从自由链表头部获取一个对象 void* Pop() { assert(_freeList); //头删 void* obj = _freeList; _freeList = NextObj(_freeList); _size--; return obj; } //插入一段范围的对象到自由链表 void PushRange(void* start, void* end, size_t n) { assert(start); assert(end); //头插 NextObj(end) = _freeList; _freeList = start; _size += n; } //从自由链表获取一段范围的对象 void PopRange(void*& start, void*& end, size_t n) { assert(n end = NextObj(end); } _freeList = NextObj(end); //自由链表指向end的下一个对象 NextObj(end) = nullptr; //取出的一段链表的表尾置空 _size -= n; } bool Empty() { return _freeList == nullptr; } size_t& MaxSize() { return _maxSize; } size_t Size() { return _size; } private: void* _freeList = nullptr; //自由链表 size_t _maxSize = 1; size_t _size = 0; }; public: //获取从对象到span的映射 Span* MapObjectToSpan(void* obj); private: std::unordered_map assert(k 0 && k _pageId = nSpan->_pageId; kSpan->_n = k; nSpan->_pageId += k; nSpan->_n -= k; //将剩下的挂到对应映射的位置 _spanLists[nSpan->_n].PushFront(nSpan); //建立页号与span的映射,方便central cache回收小块内存时查找对应的span for (PAGE_ID i = 0; i _n; i++) { _idSpanMap[kSpan->_pageId + i] = kSpan; } return kSpan; } } //走到这里说明后面没有大页的span了,这时就向堆申请一个128页的span Span* bigSpan = new Span; void* ptr = SystemAlloc(NPAGES - 1); bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT; bigSpan->_n = NPAGES - 1; _spanLists[bigSpan->_n].PushFront(bigSpan); //尽量避免代码重复,递归调用自己 return NewSpan(k); }
此时我们就可以通过对象的地址找到该对象对应的span了,直接将该对象的地址除以页的大小得到页号,然后在unordered_map当中找到其对应的span即可。
//获取从对象到span的映射 Span* PageCache::MapObjectToSpan(void* obj) { PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT; //页号 auto ret = _idSpanMap.find(id); if (ret != _idSpanMap.end()) { return ret->second; } else { assert(false); return nullptr; } }
当我们要通过某个页号查找其对应的span时,该页号与其span之间的映射一定是建立过的,如果此时我们没有在unordered_map当中找到,则说明我们之前的代码逻辑有问题,因此当没有找到对应的span时可以直接用断言结束程序,以表明程序逻辑出错。
- central cache回收内存
这时当thread cache还对象给central cache时,就可以依次遍历这些对象,将这些对象插入到其对应span的自由链表当中,并且及时更新该span的_usseCount计数即可。
在thread cache还对象给central cache的过程中,如果central cache中某个span的_useCount减到0时,说明这个span分配出去的对象全部都还回来了,那么此时就可以将这个span再进一步还给page cache。
//将一定数量的对象还给对应的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); //记录下一个 Span* span = PageCache::GetInstance()->MapObjectToSpan(start); //将对象头插到span的自由链表 NextObj(start) = span->_freeList; span->_freeList = start; span->_useCount--; //更新被分配给thread cache的计数 if (span->_useCount == 0) //说明这个span分配出去的对象全部都回来了 { //此时这个span就可以再回收给page cache,page cache可以再尝试去做前后页的合并 _spanLists[index].Erase(span); span->_freeList = nullptr; //自由链表置空 span->_next = nullptr; span->_prev = nullptr; //释放span给page cache时,使用page cache的锁就可以了,这时把桶锁解掉 _spanLists[index]._mtx.unlock(); //解桶锁 PageCache::GetInstance()->_pageMtx.lock(); //加大锁 PageCache::GetInstance()->ReleaseSpanToPageCache(span); PageCache::GetInstance()->_pageMtx.unlock(); //解大锁 _spanLists[index]._mtx.lock(); //加桶锁 } start = next; } _spanLists[index]._mtx.unlock(); //解锁 }
需要注意,如果要把某个span还给page cache,我们需要先将这个span从central cache对应的双链表中移除,然后再将该span的自由链表置空,因为page cache中的span是不需要切分成一个个的小对象的,以及该span的前后指针也都应该置空,因为之后要将其插入到page cache对应的双链表中。但span当中记录的起始页号以及它管理的页数是不能清除的,否则对应内存块就找不到了。
并且在central cache还span给page cache时也存在锁的问题,此时需要先将central cache中对应的桶锁解掉,然后再加上page cache的大锁之后才能进入page cache进行相关操作,当处理完毕回到central cache时,除了将page cache的大锁解掉,还需要立刻获得central cache对应的桶锁,然后将还未还完对象继续还给central cache中对应的span。
🌿3. pagecache 回收内存
如果central cache中有某个span的_useCount减到0了,那么central cache就需要将这个span还给page cache了。
这个过程看似是非常简单的,page cache只需将还回来的span挂到对应的哈希桶上就行了。但实际为了缓解内存碎片的问题,page cache还需要尝试将还回来的span与其他空闲的span进行合并。
- page cache进行前后页的合并
合并的过程可以分为向前合并和向后合并。如果还回来的span的起始页号是num,该span所管理的页数是n。那么在向前合并时,就需要判断第num-1页对应span是否空闲,如果空闲则可以将其进行合并,并且合并后还需要继续向前尝试进行合并,直到不能进行合并为止。而在向后合并时,就需要判断第num+n页对应的span是否空闲,如果空闲则可以将其进行合并,并且合并后还需要继续向后尝试进行合并,直到不能进行合并为止。
因此page cache在合并span时,是需要通过页号获取到对应的span的,这就是我们要把页号与span之间的映射关系存储到page cache的原因。
但需要注意的是,当我们通过页号找到其对应的span时,这个span此时可能挂在page cache,也可能挂在central cache。而在合并时我们只能合并挂在page cache的span,因为挂在central cache的span当中的对象正在被其他线程使用。
可是我们不能通过span结构当中的_useCount成员,来判断某个span到底是在central cache还是在page cache。因为当central cache刚向page cache申请到一个span时,这个span的_useCount就是等于0的,这时可能当我们正在对该span进行切分的时候,page cache就把这个span拿去进行合并了,这显然是不合理的。
鉴于此,我们可以在span结构中再增加一个_isUse成员,用于标记这个span是否正在被使用,而当一个span结构被创建时我们默认该span是没有被使用的。
//管理以页为单位的大块内存 struct Span { PAGE_ID _pageId = 0; //大块内存起始页的页号 size_t _n = 0; //页的数量 Span* _next = nullptr; //双链表结构 Span* _prev = nullptr; size_t _useCount = 0; //切好的小块内存,被分配给thread cache的计数 void* _freeList = nullptr; //切好的小块内存的自由链表 bool _isUse = false; //是否在被使用 };
由于在合并page cache当中的span时,需要通过页号找到其对应的span,而一个span是在被分配给central cache时,才建立的各个页号与span之间的映射关系,因此page cache当中的span也需要建立页号与span之间的映射关系。
与central cache中的span不同的是,在page cache中,只需建立一个span的首尾页号与该span之间的映射关系。因为当一个span在尝试进行合并时,如果是往前合并,那么只需要通过一个span的尾页找到这个span,如果是向后合并,那么只需要通过一个span的首页找到这个span。也就是说,在进行合并时我们只需要用到span与其首尾页之间的映射关系就够了。
因此当我们申请k页的span时,如果是将n页的span切成了一个k页的span和一个n-k页的span,我们除了需要建立k页span中每个页与该span之间的映射关系之外,还需要建立剩下的n-k页的span与其首尾页之间的映射关系。
//获取一个k页的span Span* PageCache::NewSpan(size_t k) { assert(k > 0 && k _pageId = nSpan->_pageId; kSpan->_n = k; nSpan->_pageId += k; nSpan->_n -= k; //将剩下的挂到对应映射的位置 _spanLists[nSpan->_n].PushFront(nSpan); //存储nSpan的首尾页号与nSpan之间的映射,方便page cache合并span时进行前后页的查找 _idSpanMap[nSpan->_pageId] = nSpan; _idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan; //建立页号与span的映射,方便central cache回收小块内存时查找对应的span for (PAGE_ID i = 0; i _n; i++) { _idSpanMap[kSpan->_pageId + i] = kSpan; } return kSpan; } } //走到这里说明后面没有大页的span了,这时就向堆申请一个128页的span Span* bigSpan = new Span; void* ptr = SystemAlloc(NPAGES - 1); bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT; bigSpan->_n = NPAGES - 1; _spanLists[bigSpan->_n].PushFront(bigSpan); //尽量避免代码重复,递归调用自己 return NewSpan(k); }
此时page cache当中的span就都与其首尾页之间建立了映射关系,现在我们就可以进行span的合并了
//释放空闲的span回到PageCache,并合并相邻的span void PageCache::ReleaseSpanToPageCache(Span* span) { //对span的前后页,尝试进行合并,缓解内存碎片问题 //1、向前合并 while (1) { 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; //将prevSpan从对应的双链表中移除 _spanLists[prevSpan->_n].Erase(prevSpan); delete prevSpan; } //2、向后合并 while (1) { PAGE_ID nextId = span->_pageId + span->_n; auto ret = _idSpanMap.find(nextId); //后面的页号没有(还未向系统申请),停止向后合并 if (ret == _idSpanMap.end()) { break; } //后面的页号对应的span正在被使用,停止向后合并 Span* nextSpan = ret->second; if (nextSpan->_isUse == true) { break; } //合并出超过128页的span无法进行管理,停止向后合并 if (nextSpan->_n + span->_n > NPAGES - 1) { break; } //进行向后合并 span->_n += nextSpan->_n; //将nextSpan从对应的双链表中移除 _spanLists[nextSpan->_n].Erase(nextSpan); delete nextSpan; } //将合并后的span挂到对应的双链表当中 _spanLists[span->_n].PushFront(span); //建立该span与其首尾页的映射 _idSpanMap[span->_pageId] = span; _idSpanMap[span->_pageId + span->_n - 1] = span; //将该span设置为未被使用的状态 span->_isUse = false; }
需要注意的是,在向前或向后进行合并的过程中:
- 如果没有通过页号获取到其对应的span,说明对应到该页的内存块还未申请,此时需要停止合并。
- 如果通过页号获取到了其对应的span,但该span处于被使用的状态,那我们也必须停止合并。
- 如果合并后大于128页则不能进行本次合并,因为page cache无法对大于128页的span进行管理。
在合并span时,由于这个span是在page cache的某个哈希桶的双链表当中的,因此在合并后需要将其从对应的双链表中移除,然后再将这个被合并了的span结构进行delete。
除此之外,在合并结束后,除了将合并后的span挂到page cache对应哈希桶的双链表当中,还需要建立该span与其首位页之间的映射关系,便于此后合并出更大的span。
🌿4. 释放内存过程联调
- ConcurrentFree函数
至此我们将thread cache、central cache以及page cache的释放流程也都写完了,此时我们就可以向外提供一个ConcurrentFree函数,用于释放内存块,释放内存块时每个线程通过自己的thread cache对象,调用thread cache中释放内存对象的接口即可。
static void ConcurrentFree(void* ptr, size_t size/*暂时*/) { assert(pTLSThreadCache); pTLSThreadCache->Deallocate(ptr, size); }
- ConcurrentFree函数
- page cache进行前后页的合并
- central cache回收内存
还没有评论,来说两句吧...