前面几个章节，详细说明了thread cache、central cache、page cache层的结构以及申请内存的逻辑。本节就是讲述回收内存的过程，大致分为下边几步：

  • thread cache挂的自由链表过长，将内存释放回central cache
  • central cache管理的span的内存块全部回来后，将span释放回page cache
  • page cache合并前后相邻的空闲页

ThreadCache层回收内存

当线程释放内存块时，直接将内存块挂到相应的ThreadCache的自由链表，当自由链表的长度达到thread cache层向central cache层申请内存的一个批量的大小我们就进行释放，也就是到MaxSize（慢增长记录）

这里注意，我们增加了FreeList成员_size，并提供了返回它大小的函数Size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 释放内存
void ThreadCache::Deallocate(void* obj, size_t size)
{
	assert(obj);
	assert(size <= MAX_BYTES);

	size_t index = SizeClass::Index(size);
	_freeLists[index].Push(obj);

	// 如果自由链表的长度大于申请一个批量的长度就还给central cache 
	if (_freeLists[index].Size() >= _freeLists[index].MaxSize())
	{
		ListTooLong(_freeLists[index], size);
	}
}

高并发内存池，ConcurrentDealloc释放内存，内部调用thread cache层的Deallocate函数，Deallocate函数内部调用ListTooLong去处理长链表归还给central cache层

1
2
3
4
5
6
7
8
9
10
11
void ThreadCache::ListTooLong(FreeList& list, size_t size)
{
	void* start = nullptr;
	void* end = nullptr;

	// 先将MaxSize长度的内存，从thread cache层释放出来
	list.PopRange(start, end, list.MaxSize());

	CentralCache::GetInstance()->ReleaseListToSpans(start, size);
}

我们需要先调用PopRange释放挂在自由链表MaxSize长度（这个之前未实现），然后调用CentralCache层ReleaseListToSpans，来回收这段内存，接下来的工作交给CentralCache层进行处理

CentralCache层回收内存

thread cache层归还回了一段内存，这里就会有一个问题，我们直到Central Cache层的哈希桶结构和映射规则与thread cache层相同，但是central cache层挂的是一个个的span对象，那么这一段内存，应该归还给某个桶的哪个span对象呢？

image.png

在page cache中，申请内存都是按页申请，那么这一页内存到下一页的任何一个地址，右移PAGE_SHIFT位都是这页内存的页号。比如下图的例子，我们就以通过地址来算这块内存应该在那一页，然后去找到对应的span，但是现在我们没办法找到

image.png

为了能通过页号，找到对应span的地址，我们可以建立一个哈希表，映射关系为page_id号和对应span的指针，我们在PageCache类中增加一个哈希表，PageCache层也会用到

1
std::unordered_map<PAGE_ID, Span*> _idSpanMap;

这时候就需要记录页号和span* 的对应关系，PageCache的NewSpan函数，返回一个span，我们需要在这个函数里增加相关代码

1
2
3
4
5
6
7
8
9
10
11
12
// 存储nSpan的首尾页跟nSpan建立映射，方便page cache回收内存

_idSpanMap[nSpan->_pageId] = nSpan;
_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;  //原理如下图


// 返回的kSpan，也要建立id和span的映射，方便central cache回收小块内存时，查找对应的span
// 给central层返回的span，会被切分成小块内存，归还的时候地址换成页号就可能是其中的某一页
for (PAGE_ID i = 0; i < kSpan->_n; ++i)
{
	_idSpanMap[kSpan->_pageId + i] = kSpan;
}

image.png

记录完映射关系之后，可以继续在封装一个函数，功能就是给我一个地址，我就返回它应该所在的span的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 获取对象到span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{
	PAGE_ID id = ((PAGE_ID)obj >> PAGE_SHITF);
	if (_idSpanMap.find(id) != _idSpanMap.end())
	{
		return _idSpanMap[id];
	}
	else
	{
		assert(false);
		return nullptr;
	}
}

上边前置工作做完之后，可以写ReleaseListToSpans函数了，大致分为以下几点：

  1. 通过起始地址，不断向后走，找到对应的span，然后头插进span的自由链表
  2. 让对应的span的_useCount，当减到0说明，这个span的所有内存块都回来了，该span可以被回收
  3. 从spanlist中将对应的span删除掉，然后让pagecache回收
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void CentralCache::ReleaseListToSpans(void* start, size_t size)
{
	size_t index = SizeClass::Index(size);

	_spanLists[index]._mtx.lock();

	// 问题：换回来的内存挂到哪个span上？
	// 通过地址 start>>PAGE_SHIFT，就是span的页号，为了方便，我们可以建立页号和span指针的映射
	// 这里可以通过哈希表做- unordered_map<PAGE_ID, Span*> 
	while (start)
	{
		void* next = NextObj(start);
		Span* span = PageCache::GetInstance()->MapObjectToSpan(start);
		
		// 头插进span的管理的链表
		NextObj(start) = span->_freeList;
		span->_freeList = start;

		span->_useCount--;

		// span切分回去的小块内存都回来了
		// 将这个span 回收给page cache
		if (span->_useCount == 0)
		{
			_spanLists[index].Erase(span);
			span->_next = nullptr;
			span->_next = nullptr;
			// span管理内存，通过页号和页数就可以
			span->_freeList = nullptr;

			_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();


}

PageCache层回收内存

page cache就回收span，并且合并相邻的span，可以向前合并也可以向后合并，但是合并有个问题：只能合并没有用的span，如果有的span正在被用就不能合并，大致步骤如下：

首先判断span是否被使用？我们在Span类中增加成员，判断该span对象有没有被使用，默认是没有被使用

1
bool _isUse = false; //是否被使用

在Central Cache层中我们向PageCache申请新的span，这时需要将isUse改成true，标识这个span被用了

1
2
3
4
// 我们要计算向page cache层要多少页的span
Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(size));
span->_isUse = true;

然后就是向前向后合并span，需要注意：

  • 当合并到头了就不再合并了
  • 前后的页有被使用的也不合并
  • 合并的长度已经超过128也不再进行合并

向前合并逻辑

image.png

向后合并逻辑

image.png

整体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 释放空闲span回到PageCache，并合并相邻的span
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	// 合并相邻的span，向前合并，有问题：前面的span如果被用就不能进行合并
	while (1)
	{
		PAGE_ID prevId = span->_pageId - 1;
		
		auto ret = _idSpanMap.find(prevId);
		//前边的页号没有了就不和并了
		if (ret == _idSpanMap.end())
		{
			break;
		}

		// 前边相邻页在使用，不合并
		Span* prevSpan = ret->second;
		if (prevSpan->_isUse == true)
		{
			break;
		}

		//超过128页的span也不合并
		if (prevSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		}

		// 进入合并的逻辑

		//span->_pageId -= prevSpan->_n;
		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}


	while (1)
	{
		PAGE_ID nextID = span->_pageId + span->_n;
		
		auto ret = _idSpanMap.find(nextID);
		if (ret == _idSpanMap.end())
		{
			break;
		}

		Span* nextSpan = ret->second;
		if (nextSpan->_isUse == true)
		{
			break;
		}

		//超过128页的span也不合并
		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->_isUse = false;

	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span;
}