---

1 前情提要

前面我们实现了高并发内存池的三层结构：线程缓存，中心缓存，页缓存：

1. 线程缓存：每个线程中都有的一个内存块链表数组，按照TLS(线程本地存储)设计。根据申请的size对齐后的大小找到对应的链表。如果有没有使用的内存块直接使用，没有就去中心缓存中进行申请一批内存块！
2. 中心缓存： 所有线程共同使用一个中心缓存，其本质是spanlist(span用来管理大块内存和内存块)数组，按照单例模式设计。根据线程缓存申请内存块的size找到对应的spanlist，如果有合适的span就返回span中的一批内存块，没有就向页缓存中进行申请对应页数的span！
3. 页缓存：所有线程共同使用一个页缓存，按照单例模式设计，其本质是一个管理不同页数span的链表数组。根据中心缓存申请的页数找到对应的spanlist,如果有就直接返回，没有就去页数更大的链表中查找是否有，有就进行拆分，如果没有向系统申请一块最大的span。

在这里，特别强调一下span。申请和回收操作中都会依赖span这个特殊结构：

struct Span
{
	//起始页的页号
	PAGE_ID _pageid = 0;
	//页的数量
	size_t _n = 0;
	Span* _next = nullptr;
	Span* _prev = nullptr;
	//引用计数
	size_t _usecount = 0;
	//被切分好的对象的大小
	size_t _objsize = 0;
	//储存切分好的对象的自由链表
	void* _freelist = nullptr;
	//是否被使用
	bool _isuse = false;
};

• _pageid页号：在向系统申请空间时，是按照页来申请的。当我们有了一个页号在乘以页的大小就可以找到页的起始位置，在这里页的大小是2^13，即向左移动13位就可以得到页空间的起始位置
• _n页数：表明span管理着多少页，即管理着多大的空间！

根据这两个成员变量我们就可以确定span管理的空间范围，然后就可以在中心缓存中将他们按照对应内存块的大小插入到 _freelist自由链表中！

好的，接下来我们就来进行回收机制的处理

2 线程缓存的内存回收

我们明确几个要素：

1. 线程缓存回收的是内存块，将内存块重新挂载到对应的自由链表中。
2. 线程缓存中的自由链表挂载着内存块，当对应链表挂载的内存块数量超出一个标准，就需要进行回收。
3. 线程缓存回收不是进行释放，而是将这一串内存块从自由链表中取出，传回给中心缓存，让中心缓存将这一批内存块重新储存起来！

根据这三个要素，我们可以写出一个线程回收的代码。我们就按照：当挂载的数量超出了自由链表申请内存块的最大数量，就释放所有挂载的内存块。释放时需要获取到这一串内存块链表的头尾节点地址，方便后续中心缓存处理！

void ThreadCache::Deallocate(void* ptr, size_t size)
{
	assert(ptr);
	assert(size < MAX_BYTES);
	//根据Index找到对应桶
	size_t index = SizeClass::Index(size);

	_freelist[index].Push(ptr);

	//如果_freelist[index]中的挂载的内存块过多 进行回收
	if (_freelist[index].Size() >= _freelist[index].MaxSize())
	{
		ListTooLong(_freelist[index], size);
	}

}
void ThreadCache::ListTooLong(FreeList& list, size_t size)
{
	//将_freelist中所有的内存块进行回收
	void* start = nullptr; // 开始节点的地址
	void* end = nullptr;   // 结束节点的地址
	list.PopRange(start, end, list.Size());
	//已经从_freelist[index]中将 size() 个数的内存块取出来
	//起始地址为start 结束地址是 end
	//将start 到 end 的内存块返回给中心缓存
	CentralCache::GetInstance()->ReleaseListToSpan(start, size);

	return;
}

原理图大致是这样！线程缓存中已经将需要释放的内存块链表传给了中心缓存，线程缓存已经完成了他的使命！

3 中心缓存的内存回收

对于中心缓存我们也要明确几个要素：

1. 中心缓存需要处理线程缓存传来的一串内存块，通过内存块的地址找到其对应的页，通过页 - span的映射哈希表找到对应的span，进行回收
2. 中心缓存中的spanlist是挂载着span的，当一个span的引用计数回到0时，就对其进行释放。
3. 中心缓存释放span不是真的进行释放，是将其从中心缓存中取出来，还给页缓存进行处理

根据这三点要素，我们可以构建其基础的框架。处理的内部还有很多细节：；

• 中心缓存是临界区，需要使用桶锁将桶锁住，离开中心缓存，进行页缓存处理时还要解桶锁，加上页缓存的锁！
• 需要遍历内存块链表，依次进行处理。因为这些内存块不一定属于同一个span。每还回一个内存块需要减少引用计数！
• 当引用计数为0时，调用页缓存对该span进行处理！

void CentralCache::ReleaseListToSpan(void* start, size_t size)
{
	//将start指向的内存块链表 头插到对应的链表中

	size_t index = SizeClass::Index(size);
	//上锁
	_spanlists[index].GetMutex().lock();
	//遍历链表
	while (start != nullptr)
	{
		void* next = NextObj(start);
		Span* span = PageCache::GetInstance()->MapObjectToSpan(start);
		//找到对应的span之后
		//将数据块头插到span中的_freelist中！
		NextObj(start) = span->_freelist;
		span->_freelist = start;
		span->_usecount--;
		//start向后移动！
		start = next;
		//判断span是否需要回收
		if (span->_usecount == 0)
		{
			_spanlists[index].Erease(span);
			//进行回收
			span->_freelist = nullptr;
			span->_next = nullptr;
			span->_prev = nullptr;
			//页缓存进行回收
			_spanlists[index].GetMutex().unlock();
			//页锁
			PageCache::GetInstance()->GetMutex().lock();
			PageCache::GetInstance()->ReleaseSpanToPageCache(span);
			PageCache::GetInstance()->GetMutex().unlock();
			//重新上锁
			_spanlists[index].GetMutex().lock();
		}
	}

	_spanlists[index].GetMutex().unlock();
}

原理图为：

4 页缓存的内存回收

页缓存中我们也明确几个要素：

1. 页缓存是管理不同页数的span，根据我们申请span的过程，我们知道span都是来源于原始的一个128页span的，所以每当还回一个span，就要进行span的合并
2. 合并过程根据span的页号和页数找到前面和后面的span，如果他们没有在使用就可以进行合并。合并后将被合并的span进行释放
3. 合并的过程是要合并到不能合并为止！

页缓存的合并需要完成前后两部分的合并，为了保证现在可以快递找到的页号对应的span,需要在页缓存创建span的模块中加入将未使用的span建立首尾页号的映射

//将nspan的 首尾页号 进行映射
//方便PageCache回收span时进行合并
_SpanMap[nspan->_pageid] = nspan; //方便向后查找
_SpanMap[nspan->_pageid + nspan->_n - 1] = nspan;//方便先前查找

这样就可以完成页缓存的内存回收了！

void PageCache::ReleaseSpanToPageCache(Span* span)
{
	//将回收的span进行合并
	// 向前合并 + 向后合并
	//进行合并的基础是前后的span都通过哈希表进行了映射
	//所以要在PageCache传给CentralCache时将span的首尾页号进行映射
	
	//向前寻找
	while (1)
	{
		PAGE_ID prev = span->_pageid - 1;
		auto ret = _SpanMap.find(prev);
		//检查是否查找到
		if (ret == _SpanMap.end())
		{
			break;
		}
		Span* pspan = ret->second;
		//检查是否在使用
		if (pspan->_isuse == true)
		{
			break;
		}
		//防止合并的页过大 , 超出管理的范围
		if (pspan->_n + span->_n > PAGENUM - 1)
		{
			break;
		}
		//进行合并
		span->_pageid = pspan->_pageid;
		span->_n += pspan->_n;

		//将被合并页释放
		_pageList[pspan->_n].Erease(pspan);
		//取消哈希映射
		_SpanMap.erase(pspan->_pageid);
		delete pspan;
		//继续向前合并
	}
	//向后合并
	while (1)
	{
		PAGE_ID next = span->_pageid + span->_n;
		auto ret = _SpanMap.find(next);
		//检查是否查找到
		if (ret == _SpanMap.end())
		{
			break;
		}
		Span* nspan = ret->second;
		//检查是否在使用
		if (nspan->_isuse == true)
		{
			break;
		}
		//防止合并的页过大 , 超出管理的范围
		if (nspan->_n + span->_n > PAGENUM - 1)
		{
			break;
		}
		//进行合并
		span->_pageid = nspan->_pageid;
		span->_n += nspan->_n;

		//将被合并页释放
		_pageList[nspan->_n].Erease(nspan);
		//取消哈希映射
		_SpanMap.erase(nspan->_pageid);
		delete nspan;
		//继续向后合并
	}
	//合并完成 --- 将span挂载到合适位置
	_pageList[span->_n].PushFront(span);
	_SpanMap[span->_pageid] = span;
	_SpanMap[span->_pageid + span->_n - 1] = span;
	span->_isuse = false;

	//回收完成！！！
}

原理图为：

这样就完成了最终的页缓存的内存回收！！！

5 调试检查

调试检查的过程是很繁琐的，需要一步一步对代码的结果进行处理，首先编写一个简单的demo，然后进入调试，一步一步的进行调试。我调试老很久，解决2个主要的bug:

1. ListTooLong函数参数没有传引用，导致对中心缓存的span的引用计数无法改变，导致程序崩溃！一开始以为是中心缓存没有对_usecount进行处理的问题。
2. 线程缓存调用_freelist[index].Pop()时没有写[index]，导致一开始测试1-8字节的时候没有出错，测试较大字节的时候程序崩溃！

经过漫长的Debug过程，最终是终于是在调试中确认了内存回收过程没有问题！

接下来就来测试多线程情况下能否成功运行：

没有问题!!!

这样高并发内存池的核心框架我们就写好了！！！
后续会继续进行性能测试和性能优化！！！敬请期待！！！