高并发内存池

1

template<size_t N>

 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

// ObjectPool.h
#pragma once
#include "Common.h"

template<class T>
class ObjectPool
{
public:
	T* New()
	{
		T* Obj = nullptr;
		size_t objSize = sizeof(T);
		// 若申请内存大于剩余内存
		if (objSize > _remainBytes)
		{
			// 向系统申请 128KB
			_memory_ptr = (char*)malloc(128 * 1024);
			if (_memory_ptr == nullptr) // 申请失败抛异常
			{
				throw std::bad_alloc();
			}
			_remainBytes = 128 * 1024; // 更新剩余内存大小
		}
		else // 从内存池中分配
		{
			Obj = (T*)_memory_ptr;
			_memory_ptr += objSize; // 更新指针
			_remainBytes -= objSize; // 更新剩余内存大小
		}
		return Obj;
	}
	void Delete(T* obj)
	{
		if (_freeList_ptr == nullptr) // 自由链表没有结点
		{
			_freeList_ptr = obj;
			*((void**)obj) = nullptr; // 将结点的指针置空
		}
		else // 头插到自由链表中
		{
			*((void**)obj) = _freeList_ptr;
			_freeList_ptr = obj;
		}
	}
private:
	char* _memory_ptr = nullptr; // 指向未被划分内存的起始地址
	size_t _remainBytes = 0; // 剩余可分配字节数
	void* _freeList_ptr = nullptr; // 指向被归还的自由链表的起始地址
};

1
2
3
4
5
6

// Commond.h
// 
static void*& NextObj(void* ptr)
{
	return (*(void**)ptr);
}

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

// Commond.h

// 页大小转换偏移，每页 2^13 Bytes，即 8 KB
static const size_t PAGE_SHIFT = 13;

// 向堆按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux 下 brk mmap 等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

 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

template<class T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		size_t objSize = sizeof(T);
		// 首先使用自由链表中的小内存块
		if (_freeList_ptr != nullptr)
		{
			// 从头部取出一个
			obj = (T*)_freeList_ptr;
			_freeList_ptr = NextObj(_freeList_ptr);
		}
		else
		{
			// 确保一个小内存块能存下一个指针
			objSize = objSize > sizeof(void*) ? objSize : sizeof(void*);
			// 若申请内存大于剩余内存
			if (objSize > _remainBytes)
			{
				_remainBytes = 128 * 1024; // 更新剩余内存大小
				// 按页为单位向系统申请 128KB>>13=4*page
				_memory_ptr = (char*)SystemAlloc(_remainBytes >> PAGE_SHIFT);
				if (_memory_ptr == nullptr) // 申请失败抛异常
				{
					throw std::bad_alloc();
				}
			}
			// 从内存池中分配（切分）
			obj = (T*)_memory_ptr;
			_memory_ptr += objSize; // 更新未被划分内存的起始地址
			_remainBytes -= objSize; // 更新剩余内存大小
		}
		new (obj)T; // 定位 new，显式调用 T 的构造函数
		return obj;
	}
	void Delete(T* obj)
	{
		obj->~T(); // 显式调用 T 的析构函数
		// 头插到自由链表中
		NextObj(obj) = _freeList_ptr;
		_freeList_ptr = obj;
	}
private:
	char* _memory_ptr = nullptr; // 指向未被划分内存的起始地址
	size_t _remainBytes = 0; // 剩余可分配字节数
	void* _freeList_ptr = nullptr; // 指向被归还的自由链表的起始地址
};

 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

void ObjectPoolTest()
{
	int Round = 100; // 申请/释放的轮次
	int N = 100000; // 每轮申请/释放次数
	
	// malloc/free
	std::vector<Node*> v1;
	v1.reserve(N);
	time_t begin1 = clock();
	for (int i = 0; i < Round; i++)
	{
		for (int j = 0; j < N; j++)
		{
			v1.push_back(new Node);
		}
		for (int j = 0; j < N; j++)
		{
			delete v1[j];
		}
		v1.clear();
	}
	time_t end1 = clock();
	// ObjectPool
	ObjectPool<Node> NodePool;
	std::vector<Node*> v2;
	v2.reserve(N);
	time_t begin2 = clock();
	for (int i = 0; i < Round; i++)
	{
		for (int j = 0; j < N; j++)
		{
			v2.push_back(NodePool.New());
		}
		for (int j = 0; j < N; j++)
		{
			NodePool.Delete(v2[j]);
		}
		v2.clear();
	}
	time_t end2 = clock();
	std::cout << "malloc/free cost time: " << end1 - begin1 << "ms" << std::endl;
	std::cout << "Object Pool cost time: " << end2 - begin2 << "ms" << std::endl;
}

 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

// 自由链表：管理相同大小的小内存块（不大于 256KB)
class FreeList
{
public:
	// 头插
	void Push(void* obj)
	{
		assert(obj);

		NextObj(obj) = _freeList_ptr;
		_freeList_ptr = obj;
		_size++;
	}
	// 头删
	void* Pop()
	{
		assert(_freeList_ptr); // 链表不为空

		void* ptr = _freeList_ptr;
		_freeList_ptr = NextObj(_freeList_ptr);

		_size--;

		return ptr;
	}

	bool Empty()
	{
		return _freeList_ptr == nullptr;
	}
	size_t Size()
	{
		return _size;
	}
public:
	void* _freeList_ptr = nullptr; // 自由链表的起始地址
	size_t _size = 0; // 自由链表的结点个数
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

struct Node
{
	int _val;
	Node(int val = 0)
		:_val(val)
	{}
};
void FreeListTest()
{
	FreeList* freeList = new FreeList;
	for (int i = 0; i < 5; i++)
	{
		Node* ptr = new Node(i);
		std::cout << ptr << std::endl;
		freeList->Push(ptr);
	}
	std::cout << "----------" << std::endl;
	while (!freeList->Empty())
	{
		Node* ptr = (Node*)freeList->Pop();
		std::cout << ptr << std::endl;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// bytes：字节数		alignNum：对齐数
size_t _RoundUp(size_t bytes, size_t alignNum)
{
	size_t alignSize = 0;
	if (bytes%alignNum != 0)
	{
		alignSize = (bytes / alignNum + 1)*alignNum;
	}
	else
	{
		alignSize = bytes;
	}
	return alignSize;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

size_t _Index(size_t bytes, size_t alignNum)
{
	size_t index = 0;
	if (bytes%alignNum != 0)
	{
		index = bytes / alignNum;
	}
	else
	{
		index = bytes / alignNum - 1;
	}
	return index;
}

 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
75
76
77
78
79
80
81

// Common.h

// 管理内存对齐和单位转换
class SizeClass
{
public:
	// 子函数
    // bytes：字节数		alignNum：对齐数
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}

	// 获取向上对齐后的字节数
	static inline size_t RoundUp(size_t bytes)
	{
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 8 * 1024);
		}
		else // 大于 256KB 的内存申请先不管
		{
			assert(false);
			return -1;
		}
	}

	// 子函数
	static inline size_t _Index(size_t bytes, size_t alignShift)
	{
		return ((bytes + (1 << alignShift) - 1) >> alignShift) - 1;
	}

	// 从字节数转换为哈希桶的下标
	static inline size_t Index(size_t bytes)
	{
		// 每个字节范围有多少个自由链表
		static size_t groupArray[4] = { 16, 56, 56, 56 };
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + groupArray[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + groupArray[0] + groupArray[1];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + groupArray[0] + groupArray[1] + groupArray[2];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 64 * 1024, 13) + groupArray[0] + groupArray[1] + groupArray[2] + groupArray[3];
		}
		else
		{
			assert(false);
			return -1;
		}
	}
};

1
2
3
4

// ThreadCache 最大能分配的内存块大小
static const size_t TC_MAX_BYTES = 256 * 1024;
// ThreadCache 和 CentralCache 中自由链表（哈希桶）的个数
static const size_t NUM_CLASSES = 208;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// ThreadCache.h
class ThreadCache
{
public:
	// 分配内存
	void* Allocate(size_t bytes);
	// 回收内存
	void Deallocate(void* ptr, size_t bytes);
	// 从 CentralCache 中获取 Object
	void* FetchFromCentralCache(size_t index, size_t bytes);
    // ...
private:
	FreeList _freeLists[NUM_CLASSES]; // 哈希桶
};

 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

// ThreadCache.cpp
// 分配内存
void* ThreadCache::Allocate(size_t bytes)
{
	assert(bytes <= TC_MAX_BYTES); // 最大可分配 256KB
	size_t index = SizeClass::Index(bytes); // 哈希桶下标
	if (!_freeLists[index].Empty()) // 该桶不为空
	{
		return _freeLists[index].Pop();
	}
	else // 从 CentralCache 中获取内存
	{
		size_t alignSize = SizeClass::RoundUp(bytes);
		return FetchFromCentralCache(index, alignSize);
	}
}
// 回收内存
void ThreadCache::Deallocate(void* ptr, size_t bytes)
{
	assert(ptr);
	assert(bytes <= TC_MAX_BYTES);

	size_t index = SizeClass::Index(bytes); // 定位到哈希桶
	_freeLists[index].Push(ptr); // 插入到桶中
}
// 从 CentralCache 中获取内存
void* ThreadCache::FetchFromCentralCache(size_t index, size_t bytes)
{
	// ...
	return nullptr;
}

1

__declspec( thread ) int tls_i = 1;

1
2
3
4

//ThreadCache.h

// 用 TLS 声明线程管理 ThreadCache 资源的入口地址
static __declspec(thread) ThreadCache* TLSThreadCache_ptr = nullptr;

 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

#include "ThreadCache.h"

static void* ConcurrentAlloc(size_t bytes)
{
	if (bytes > TC_MAX_BYTES) // 大于 256KB 的内存申请
	{
		// 向 PageHeap 申请
	}
	else
	{
		if (TLSThreadCache_ptr == nullptr)
		{
			TLSThreadCache_ptr = new ThreadCache;
		}
	}
    // for test
    std::cout << std::this_thread::get_id() << ":" << TLSThreadCache_ptr << std::endl;
	return TLSThreadCache_ptr->Allocate(bytes);
}

static void ConcurrentFree(void* ptr)
{
	assert(ptr);
	size_t bytes;
	// bytes = ptr->size();
	if (bytes > TC_MAX_BYTES) // 大于 256KB 的内存释放
	{
		// 归还给 PageHeap
	}
	else
	{
		return TLSThreadCache_ptr->Deallocate(ptr, bytes);
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void Alloc1()
{
	for (int i = 0; i < 5; i++)
	{
		void* ptr = ConcurrentAlloc(5);
	}
}
void Alloc2()
{
	for (int i = 0; i < 4; i++)
	{
		void* ptr = ConcurrentAlloc(4);
	}
}
void TLSTest()
{
	std::thread t1(Alloc1);
	std::thread t2(Alloc2);

	t1.join();
	t2.join();
}

1
2
3
4
5
6
7
8

// Common.h
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef unsigned int PAGE_ID;
#else
	// Linux
#endif

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

//Common.h
// Span：双向链表的结点，管理一个以页为单位的自由链表 (Objets)
struct Span
{
	PAGE_ID _pageId = 0; // 页号，描述 Span 的起始位置
	size_t _nPage = 0; // Span 中的页数

	Span* _prev = nullptr; // 前后结点指针
	Span* _next = nullptr;
	void* _objectsList = nullptr; // 指向由未被分配的 Object 组成的链表

	size_t _objSize= 0; // Span 中 Object 的大小
	size_t _usedCount = 0; // 记录分配给 ThreadCache 的 Object 个数
};

 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

// SpanList：双向链表，管理若干相同规格的 Span
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	bool Empty()
	{
		return _head == _head->_next;
	}
	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;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head); // 不能删除哨兵位的头结点

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
	~SpanList() {}
private:
	Span* _head;
public:
	std::mutex _mtx; // 桶锁
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// CentralCache.h
class CentralCache
{
public:
	// 获取对象地址
	static CentralCache* GetInstance() 
	{
		return &_sInst;
	}
	// ThreadCache 从 CentralCache 申请一段范围的 Object
	size_t FetchRangeObj(void*& start, void*& end, size_t n, size_t bytes);
	// 获取一个非空的 Span
	Span* GetOneSpan(SpanList& spanList, size_t bytes);
	// ThreadCache 释放若干 Object 到 CentralCache 的某个 Span 中
	void ReleaseListToSpans(void* start, size_t bytes);
private:
	SpanList _spanLists[NUM_CLASSES];
private: // 单例模式
	CentralCache() {}
	CentralCache(const CentralCache&) = delete;
	static CentralCache _sInst; // 创建对象
};

1
2

// ThreadCache.cpp
CentralCache CentralCache::_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

class SizeClass
{
public:	
    // ...
    
	// 返回 ThreadCache 向 CentralCache 获取 Object 的个数
	// objSize：单个对象的大小
	static size_t NumMoveSize(size_t objSize)
	{
		assert(objSize);
		// ThreadCache（空）最多能获取的对象个数
		int num = TC_MAX_BYTES / objSize;

		if (num < 2) // 对象大，分少一点
		{
			num = 2;
		}
		else if (num > 512) // 对象小，分多一点
		{
			num = 512;
		}
		return num;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class FreeList
{
public:
	// ...
	size_t& MaxSize()
	{
		return _maxSize;
	}
public:
    // ...
	size_t _maxSize = 1; // Object 的最大个数
};

 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

// CentralCache.cpp

// ThreadCache 从 CentralCache 申请若干 Object
// start/end：对象范围	n: Object 的个数
// bytes: 所需内存的字节数
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t n, size_t bytes)
{
	size_t index = SizeClass::Index(bytes); // 哈希桶下标
	_spanLists[index]._mtx.lock(); // 加桶锁

	// 在哈希桶中取一个非空的 Span
	Span* span = GetOneSpan(_spanLists[index], bytes);
	assert(span && span->_objectsList); // Span 及自由链表不为空

	// 在 Span 中取出 n 个 Object
	// 如果不够取，则取整个 Span 中的 Object
	start = end = span->_objectsList; // 输出型参数
	size_t actualNum = 1;
	while (NextObj(end) && n - 1)
	{
		end = NextObj(end); // 链表迭代
		n--;
		actualNum++;
	}
	// 将剩下的 Object 拼接回去
	span->_objectsList = NextObj(end);
	// 将分配出去的最后一个 Object 指向空
	NextObj(end) = nullptr;
	// 更新这个 Span 的 Object 被分配数
	span->_usedCount += actualNum;

	_spanLists[index]._mtx.unlock(); // 解桶锁
	return actualNum;
}

 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

class FreeList
{
public:
	// ...
    
	// 插入一段范围的 Object 到自由链表
	// start/end：地址范围	n: Object 个数
	void PushRange(void* start, void* end, size_t n)
	{
		assert(start);
		assert(end);

		// 头插
		NextObj(end) = _freeList_ptr;
		_freeList_ptr = start;
		_size += n;
	}
	// 从自由链表获取一段范围的 Object
	// start/end：输出型参数
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);
        
		// 头删
		start = _freeList_ptr;
		end = start;
		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList_ptr = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	// ...
};

 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

// ThreadCache.cpp

// ThreadCache 从 CentralCache 中获取 Object
// index: 哈希桶索引		bytes: 所需内存字节数
void* ThreadCache::FetchFromCentralCache(size_t index, size_t bytes)
{
	// 慢开始反馈调节
	size_t batchNum = min(SizeClass::NumMoveSize(bytes), _freeLists[index].MaxSize());
	// 在未到 NumMoveSize(bytes) 之前，batchNum 线性增长
	if (batchNum == _freeLists[index].MaxSize())
	{
		_freeLists[index].MaxSize() += 1; // 线性增长
	}
	// 从 CentralCache 中获取 Object
	void* start = nullptr;
	void* end = nullptr;
	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, bytes);
	assert(actualNum >= 1); // 保证至少获取一个 Object

	if (actualNum == 1) // 只有一个直接返回给线程
	{
		assert(start == end);
		return start;
	}
	else 
	{
		// 将剩下的 Objects 插入到 ThreadCache 的桶中
		_freeLists[index].PushRange(NextObj(start), end, actualNum - 1);
		return start; // 将第一个 Object 返回给线程
	}
}

1
2

// PageHeap 中哈希桶的个数
static const size_t PH_MAX_PAGES = 129;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class PageHeap
{
public:
	static PageHeap* GetInstance()
	{
		return &_sInst;
	}
	// 获取一个 k 页的 span
	Span* NewSpan(size_t k);
	// 返回从 Object 到 Span 的映射
	Span* MapObjectToSpan(void* obj);
	// PageHeap 回收空闲的 Span，并合并相邻的 Span
	void ReleaseSpanToPageHeap(Span* span);
public:
	std::mutex _pageMtx;
    private:
	SpanList _spanLists[PH_MAX_PAGES];

	PageHeap() {}
	PageHeap(const PageHeap&) = delete;

	static PageHeap _sInst;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class SizeClass
{
public:
    // ...
    
    // 返回 CentralCache 向 PageHeap 申请的页数
	// bytes: ThreadCache 向 CentralCache 申请 Object 的字节数
	static size_t NumMovePage(size_t objBytes)
	{
		size_t num = NumMoveSize(objBytes); // Object 个数
		size_t size = num * objBytes; // 一次性申请的最大字节数

		size_t nPage = size >> PAGE_SHIFT;
		if (nPage == 0)
		{
			nPage = 1; // 至少给 1 页
		}
		return nPage;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class SpanList
{
public:
    
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
};

 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
// spanList: CentralCache 的某个哈希桶		bytes: Object 的字节数
Span* CentralCache::GetOneSpan(SpanList& spanList, size_t objBytes)
{
	// 尝试寻找一个非空的 Span
	Span* it = spanList.Begin();
	while (it != spanList.End())
	{
		if (it->_objectsList != nullptr)
		{
			return it;
		}
		else
		{
			it = it->_next;
		}
	}
	// spanList 是空的，向 PageHeap 申请（单位是页）
	Span* span = PageHeap::GetInstance()->NewSpan(SizeClass::NumMovePage(objBytes));
	// Span 的起始/终止地址和跨度
	char* start = (char*)(span->_pageId << PAGE_SHIFT); // 注意类型转换
	char* end = (char*)(start + (span->_n << PAGE_SHIFT));

	// 将 Span 切割成若干 Object
	// 1. 将内存挂到 FreeList 上
	span->_objectsList = start;
	// 2. 切分 Span 为多个 Object（单位是 objBytes)
	// 让 start 向后走一步以迭代
	void* tail = start;
	start += objBytes;

	// 在 [start, end] 中构建 FreeList
	while (start < end)
	{
		NextObj(tail) = start;
		tail = NextObj(tail);
		start += objBytes;
	}
	// 3. 将最后一个 Object 的 next 指针置空
	NextObj(tail) = nullptr;
	// 将划分好的 Span 挂到 CentralCache 的 SpanList 上
	spanList.PushFront(span);

	return span;
}

 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

// PageHeap.cpp

// PageHeap 取一个 k 页的 Span 给 CentralCache
Span* PageHeap::NewSpan(size_t k)
{
	assert(k > 0 && k < PH_MAX_PAGES); // 申请的有效页数

	// 大于 128 页
	if (k > PH_MAX_PAGES - 1)
	{
		void* ptr = SystemAlloc(k); // 向系统申请，得到地址
		Span* kSpan = new Span;
		kSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT; // 将地址转换为页号
		kSpan->_nPage = k;

		return kSpan;
	}
	// 首先看自己有没有空闲的 k 页 Span
	if (!_spanLists[k].Empty()) 
	{
		Span* kSpan = _spanLists[k].PopFront();
		return kSpan;
	}
	else // 没有 k 页 Span，从 k+1 号桶往后找 n 页 Span 切分
	{
		for (int i = k + 1; i < PH_MAX_PAGES; i++)
		{
			if (!_spanLists[i].Empty())
			{
				Span* nSpan = _spanLists[i].PopFront();
				Span* kSpan = new Span;

				// 将 n 页 Span 的前 k 页切下来，并两者的更新页号和页数
				kSpan->_pageId = nSpan->_pageId;
				kSpan->_nPage = k;

				nSpan->_pageId += k;
				nSpan->_nPage -= k;
				//将剩下的 n-k 页挂到桶中
				_spanLists[nSpan->_nPage].PushFront(nSpan);

				return kSpan;
			}
		}
	}
	// 走到这里说明一个大于 k 页的 Span 都没有
	// 向系统申请一个 128 页的 Span
	void* ptr = SystemAlloc(PH_MAX_PAGES - 1);
	Span* newSpan = new Span; // 用一个新 Span 管理新内存

	// 更新页号和页数
	newSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	newSpan->_nPage = PH_MAX_PAGES - 1;
	// 将新 Span 挂到 128 号桶上
	_spanLists[newSpan->_nPage].PushFront(newSpan);

	// 递归调用，返回 k 页 Span
	return NewSpan(k);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void AlignTest() // 测试对齐
{
	void* ptr1 = ConcurrentAlloc(6);
	void* ptr2 = ConcurrentAlloc(8);
	void* ptr3 = ConcurrentAlloc(10);

	std::cout << ptr1 << std::endl;
	std::cout << ptr2 << std::endl;
	std::cout << ptr3 << std::endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

1. 由于申请的 bytes=6 小于 256KB，所以由 ThreadCache::Allocate(bytes) 分配
  2. 通过 bytes 算出对齐数 alignSize=8 和桶索引 index=0，但是 index 位置的桶是空的，进入 FetchFromCentralCache(index, alignSize) 从 CentralCache 获取
    3. 慢开始反馈调节：batchNum=1（一次从 Span 取出多少个 Object），_maxSize(+1)=2。进入 CentralCache::FetchRangeObj(start, end, batchNum, bytes)，拿出一段 Objects 给 ThreadCache
      4. 通过 bytes 求出 index，进入 CentralCache::GetOneSpan(_spanLists[index], bytes)，从对应的桶中取一个 Span。但是初始情况它是空的，所以要向 PageHeap 申请，申请肯定不能只申请 8Bytes，至少是 1 个 Page。
        5. 通过 bytes 算出 CentralCache 向 PageHeap 申请的页数 k=1，进入 PageHeap::NewSpan(k)
          6. 初始情况 PageHeap 是空的，所以会调用 SystemAlloc(PH_MAX_PAGES - 1) 给最大桶向系统申请 128 个 Page。这块新内存被挂到 128 号桶，然后递归调用自己：将 128 页切分成 k=1 页和 128-k=127 页，将 k=1 页的 Span 返回给 CentralCache，将剩下的挂到 127 号桶上
-----------------------------------------------------------------------------
      return 4. 返回 CentralCache::GetOneSpan()，将获取到的 k=1 页 Span 以 bytes 为单位构建自由链表，这样 Span 就由若干 8Bytes 的 Object 组成，然后返回链表的起始地址
    return 3. 返回 CentralCache::FetchRangeObj()。现在 index 桶上有了 Span，足够取出 batchNum=1 个 Object，将剩下的拼接回 Span 上
  return 2. 返回 ThreadCache::FetchFromCentralCache()，将一个大小为 alignSize 的 Object 的地址返回给线程
return 1. 线程通过地址使用申请到的内存

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void AlignTest2()
{
	for (int i = 0; i < 1024; i++)
	{
		void* ptr = ConcurrentAlloc(8);
		std::cout << ptr << std::endl;
	}
	void* ptr = ConcurrentAlloc(8); // 在这里打断点
	std::cout << ptr << std::endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 回收内存
void ThreadCache::Deallocate(void* ptr, size_t bytes)
{
	assert(ptr);
	assert(bytes <= TC_MAX_BYTES);

	size_t index = SizeClass::Index(bytes); // 定位到哈希桶
	_freeLists[index].Push(ptr); // 插入到桶中

	// 当自由链表长度大于等于一次向 CentralCache 申请的个数，再归还这部分
	if (_freeLists[index].Size() >= _freeLists[index].MaxSize())
	{
		ListTooLong(_freeLists[index], bytes);
	}
}

void ThreadCache::ListTooLong(FreeList& list, size_t bytes)
{
	void* start = nullptr;
	void* end = nullptr;

	list.PopRange(start, end, list.MaxSize());
	CentralCache::GetInstance()->ReleaseListToSpans(start, bytes);
}

 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

class FreeList
{
public:
	// 从自由链表获取一段范围的 Object
	// start/end：输出型参数
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);

		// 头删
		start = _freeList_ptr;
		end = start;
		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList_ptr = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	size_t Size()
	{
		return _size;
	}
public:
	void* _freeList_ptr = nullptr; // 自由链表的起始地址
	size_t _size = 0; // 自由链表的结点个数
};

1

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 返回从 Object 地址到 Span 首地址的映射
Span* PageHeap::MapObjectToSpan(void* objAdr)
{
	PAGE_ID id = (PAGE_ID)objAdr >> PAGE_SHIFT; // 将地址转换为页号
	std::unordered_map<PAGE_ID, Span*>::iterator it = _idSpanMap.find(id); // 查表
	if (it != _idSpanMap.end())
	{
		return it->second;
	}
	else
	{
		assert(false); // 没有映射一定有错误
		return nullptr;	// 仅为通过编译，不会执行
	}
}