central cache

申请内存

也是一个哈希桶结构，映射规则与thread cache 类似，桶锁减小竞争。

central cache 哈希映射的spnlist， spanlist中挂着span，从span中取出对象给thread cache，这个过程是加锁的（桶锁）

spanlist中所有span都没有内存之后需要向 page cache 申请一个新的span对象给thread cache。 span用一个结构体来实现，span中的 use_count 记录分配了多少对象出去 use_count++。

释放内存

当thread_cache过长或者线程销毁，则会将内存释放回central cache中的，释放回来时– use_count。当use_count减到0时则表示所有对象都回到了span，则将span释放回page cache， page cache中会对前后相邻的空闲页进行合并。

span 和 spanlist的设计

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
// 管理多个连续页大块内存跨度结构=
struct Span {
	PAGE_ID _pageId = 0; //大块内存起始页的页号
	size_t _n = 0; //页的数量

	//双向链表的结构
	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _use_Count = 0; // 切好的小块内存被分配给threadCache的计数
	void* _freeList = nullptr; //切好的小块内存的自由链表

};

//带有双向循环链表
class SpanList {
public:
	SpanList() {
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	void Insert(Span* pos, Span* newSpan) {
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	// 内存不需要delete, span内存最后会处理，这里不用管
	void Erase(Span* pos) {
		assert(pos);
		assert(pos != _head);
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;
	}

private:
	Span* _head;
};

CentralCache要设计成单例模式，

然后要实现threadcache如何从centralcache 中申请内存

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
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size) {
	// 获取central cache 中的内存

	// 小对象给多i一点，大对象给少一些
	// size 越小 batchNum 越大
	size_t batchNum = std::min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
	//慢开始反馈调节算法
	if (_freeLists[index].MaxSize() == batchNum) {
		_freeLists[index].MaxSize() += 2;
	}
	void* start = nullptr;
	void* end = nullptr;

	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
	assert(actualNum >= 1);

	if (actualNum == 1) {
		assert(start == end);
		return start;
	}
	else {
		_freeLists[index].PushRange(NextObj(start), end);
		return start;
	}
}

实现FetchRangeObj， 如何给threadCache内存

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
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t n, size_t byte_size) {
	size_t index = SizeClass::Index(byte_size);
	_spanLists[index]._mtx.lock();
	
    // 获取span, 遍历_spanLists[index], 如果没有就取page cache中获取
	Span* span = GetOneSpan(_spanLists[index], byte_size);

	assert(span);
	assert(span->_freeList);
	start = span->_freeList;
	end = start;
	size_t i = 0;
	size_t actualNum = 1;
	while(i < n - 1 && NextObj(end) != nullptr) {
		end = NextObj(end);
		i++;
		actualNum++;
	}  
	span->_freeList = NextObj(end);
	NextObj(end) = nullptr;

	_spanLists[index]._mtx.unlock();

	return actualNum;

}

从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
Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size) {
	//查看当前spanlist中是否有还未分配对象的span
	Span* it = list.Begin();
	while (it != list.End()) {
		if (it->_freeList != nullptr) {
			return it;
		}
		else {
			it = it->_next;
		}
	}

	//走到这里，只能像page cache中申请
	//先解锁
	list._mtx.unlock();
	PageCache::GetInstance()->_pageMtx.lock();
	Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(byte_size));
	PageCache::GetInstance()->_pageMtx.unlock();

	//对获取的span进行切分， 不需要加锁

	assert(span);
	// 计算span
	char* start = (char*)(span->_pageId << PAGE_SHIFT);
	size_t bytes = span->_n << PAGE_SHIFT;
	char* end = start + bytes;

	//先切一块下来做头
	span->_freeList = start;
	//尾插
	start += byte_size;
	void* tail = span->_freeList;

	while (start < end) {
		NextObj(tail) = start;
		tail = NextObj(tail);
		start += byte_size;
	}
	//把Span挂到桶里面时要加锁
	list._mtx.lock();
	list.PushFront(span);


	return span;
}

目前为止实现了 threadcache 和 central cache 的申请功能， 释放内存部分还未实现。

page cache

central cache 像 page cache申请内存

pageCache初步设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class PageCache {

public:
	static PageCache* GetInstance() {
		return &_sInst;
	}
	//获取k页的span
	Span* NewSpan(size_t k);

private:
	SpanList _spanLists[NPAGES];
	std::mutex _pageMtx;
	PageCache() {};
	PageCache(const PageCache&) = delete;

	static PageCache _sInst;
};
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

//pageCache向下分内存和向堆申请内存

Span* PageCache::NewSpan(size_t k) {
	assert(k > 0 && k < NPAGES);
	if (!_spanLists[k].Empty()) {
		return _spanLists->PopFront();
	}
	//第k个桶是空的，检查后续的桶中有咩有span
	for (size_t i = k + 1; i < NPAGES; i++) {
		if (!_spanLists[i].Empty()) {
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;
			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_n -= k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);
			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);
}