Central Cache框架设计
当申请对象时，thread cache层对应的自由链表为空时，需要向central cache层申请内存。central cache层框架图如下：
central cache整体也是一个哈希桶结构，类似于thread cache层，但是central cache层所挂的是span的链表
- span是管理大块内存的数据结构，页为单位
- span里面有个自由链表，管理切割出来的小内存块
- 映射关系和对齐规则同thread cache
Central Cache具体结构
span结构
span是管理多个连续页大块内存的跨度结构，具体结构代码如下；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
struct Span
{
PAGE_ID _pageId = 0;
size_t _n = 0;
Span* _next = nullptr;
Span* _prev = nullptr;
size_t _useCount = 0;
void* _freeList =nullptr;
};
|
首先需要注意的是，span是双向链表的结构，双向链表删除元素非常方便，当将某个span对象归还给page cache层时，双向链表删除非常简单
span是管理以页为单位的大块内存，当归还给page cache层时，为了方便相邻页的合并需要一个页号 pageID，我们用了typedef的类型PAGE_ID
假设一页为8k
32位下 进程地址空间有4G，能分 2^32/2^13 = 2^19 个页
64位下 进程地址空间有16G，能分 2^64/2^13 = 2^51 个页
所以不同平台下，PAGE_ID 的类型需要动态调整，这里我们用条件编译实现
1
2
3
4
5
6
7
|
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif
|
这里注意先判断 _WIN64
SpanList结构
我们知道central cache层每个哈希桶中挂的是span的链表，我们将这个链表结构定义成带头双向的循环链表
我们目前的核心成员有两个
- Span*
- mutex锁（桶锁，多个线程同时申请一个桶的对象时需要加锁）
提供，插入和删除和删除的接口
void Insert(Span* pos, Span* newSpan)void Eerase(Span *pos)
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
| 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;
newSpan->_next = pos;
pos->_prev = newSpan;
prev->_next = newSpan;
newSpan->_prev = prev;
}
void Eerase(Span *pos)
{
assert(pos);
assert(pos != _head);
Span* prev = pos->_prev;
Span* next = pos->_next;
next->_prev = prev;
prev->_next = next;
}
private:
Span* _head;
public:
std::mutex _mtx;
};
|
注意，erase时，不需要delete，只需要从链表移除即可，会归还给下一层的page cache
Central Cache结构
首先Central Cache是哈希桶结构，然后我们期望，每个线程都有属于自己的Thread Cache（用TLS实现无锁），但是Central Cache在整个进程中只有一个，所以我们可以设计成单例模式
单例模式采用饿汉模式，构造函数私有，在静态区创建一个对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class CentralCache
{
public:
static CentralCache* GetInstance()
{
return &_sInst;
}
private:
static CentralCache _sInst;
private:
CentralCache(){}
CentralCache(const CentralCache& c) = delete;
private:
SpanList _spanLists[NFREELIST];
};
|
Central Cache逻辑实现
thread cache层，申请对象，对应自由链表为空时，需要向central cache层申请内存，我们在thread cache部分提供了一个接口FetchFromCentralCache，我们先从这里开始，逐步扩展到整体的central cache的逻辑实现
1
2
3
4
5
|
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
}
|
thread cache向central申请内存时，最好多给一些，避免频繁申请，那么该给多少比较合适呢？这里提出一个慢开始反馈算法，我们核心想法如下：
- 最开始不会一次向central cache一次批量的要太多，要太多可能会用不完
- 如果不断有要size大小内存的的需求，batchNum也会不断的增长直到上限
- size越大，一次向central cache要的batchNum越小
- size越小，一次向central cache要的batchNum越大。
根据上述规则，我们在SizeClass类增加下述函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
static size_t NumMoveSize(size_t size)
{
assert(size > 0);
size_t num = MAX_BYTES / size;
if (num < 2)
num = 2;
if (num > 512)
num = 512;
return num;
}
|
我们就可以在FetchFromCentralCache函数中调用上面函数获取应该给central cache批量层要多少个对象的个数
1
| size_t batchNum = SizeClass::NumMoveSize(size);
|
但是若size比较小，batchNum刚开始的时候还是比较大，怎么让小对象它开始的时候也没那么大，满足规则2呢？
我们可以这样处理，在FreeList结构中，增加一个成员 _ maxSize，并初始化为1，这样thread cache层每一个桶的自由链表都有它的maxSize。并可以写下边的逻辑。
当batchNum和当前所在自由链表的MaxSize相同时，说明上边MaxSize是较小的那个，我们让MaxSize加1，若不断申请size大小的对象，MaxSize就会不断增大，而【2，512】就可以做这个增加的上限
1
2
3
4
5
| size_t batchNum = std::min(SizeClass::NumMoveSize(size),_freeLists[index].MaxSize());
if (_freeLists[index].MaxSize() == batchNum)
{
_freeLists[index].MaxSize() += 1;
}
|
知道要多少个对象后就向central cache层要batchNum个对象，但是这里就会出现一些问题，central cache层可能不够batchNum个对象，我们看下边处理
首先是给CentralCache类提供两个接口。一个是获取非空的Span，另一个就是获取batchNum个对象
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
|
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)
{
size_t index = SizeClass::Index(size);
_spanLists[index]._mtx.lock();
Span* span = GetOneSpan(_spanLists[index], size);
assert(span);
assert(span->_freeList);
start = span->_freeList;
end = start;
int actualNum = 1;
size_t i = 0;
while (i<batchNum && NextObj(end) != nullptr)
{
end = NextObj(end);
++i;
++actualNum;
}
span->_freeList = NextObj(end);
NextObj(end) = nullptr;
_spanLists[index]._mtx.unlock();
return actualNum;
}
|
完善完成上述内容后，我们回到最开始，thread cache向central cache申请内存
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
|
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
size_t batchNum = std::min(SizeClass::NumMoveSize(size),_freeLists[index].MaxSize());
if (_freeLists[index].MaxSize() == batchNum)
{
_freeLists[index].MaxSize() += 1;
}
void* start;
void* end;
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;
}
}
|
微信
支付宝
