高并发内存池|二、Common

二、Common

这部分主要存放高并发内存池中三个 cache 都会使用到的共同的结构。如内存对齐规则、自由链表结构、SpanList 结构、内存池向堆申请内存等功能都在这部分实现。

1. 对齐规则实现

注意 _RoundUp() 中的对齐计算公式，是一个经典的内存对齐技巧：

((bytes + alignNum - 1) & ~(alignNum - 1));

例如，当 alignNum 为 8 时，~(alignNum - 1) 就是 7 取反，它的二进制为 …… 1111 1000 ，此时，这个数与任何一个大于 8 的正整数进行与操作，其结果都会是 8 的倍数。

而 (bytes + alignNum - 1) 的作用，就是要确定究竟要取 8 的多少倍，实际上，它就是在进行**“向上取整”，因为任何一个非零自然数加上 7，其结果都会大于等于 8，转换为二进制后，这个结果一定会有高于第四位的 1，而进行与操作后，小于第四位的二进制位，会被置零，即把低位对齐部分清零，保留高位（第四位）**。

2. 索引位置实现

注意 _Index() 中的索引计算公式：

((bytes + (1 << align_shift) - 1) >> align_shift) - 1;

这个公式是在将不同大小的内存块放进对应大小的桶的索引中，即在计算索引偏移量，以 8 对齐为例：

要注意，这个索引结果是相对于一个对齐规则的偏移量，在 Index() 中 group_array 存储的是每个对齐规则所占的索引数目，因此为了得到全局索引，除 8 对齐以外的对齐规则，还要加上前面的对齐规则所占用的索引数目，才能得到真正的索引。

3. PushRange()

PushRange() 是头插一个自由链表，如过在调用这个函数前，自由链表 _freeList 结构如下：

_freeList -> A -> B -> C -> ...

传入 PushRange() 的链表结构为：

start -> X -> Y -> Z (end)

执行代码后，Z(end) 的下一个就被设置为 _freeList 指向的内容，即 A，然后再更新 _freeList 指向的位置，最终完成了链表的头插：

X -> Y -> Z ->A -> B -> C -> ...

4. 避免使用malloc

由于高并发内存池的作用，就是在高并发的场景下，代替 malloc() 来给线程分配内存空间的，所以在代码中要避免使用 malloc() 和 new 来创建对象。我们可以使用 VirtualAlloc() （Windows 环境下）或者 mmap() （Linux 环境下）来绕过 malloc() 向系统申请内存空间：

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif __linux__
size_t size = page << 13;
void* ptr = mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

#endif
if (ptr == nullptr)
{
	throw std::bad_alloc();
}
return ptr;
}

template<class T>
class ObjectPool
{
public:
	T* New()
	{
		T* object = nullptr;
		//优先使用还回来的空间
		if (_freeList)
		{
			void* next = *((void**)_freeList);
			object = (T*)_freeList;
			_freeList = next;
		}

		//如果大空间不足
		if (_restBytes < sizeof(T))
		{
			_restBytes = 128 * 1024;	//一次申请128Kb的空间
			_memory = (char*)SystemAlloc(_restBytes >> 13);	//128Kb右移13位相当于16页
			if (_memory == nullptr)
			{
				throw std::bad_alloc();
			}
		}

		//从申请的大空间中截一块出来
		object = (T*)_memory;
		size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
		_memory += objSize;
		_restBytes -= objSize;

		//定位new，显示调用T的构造函数
		new(obj)T;

		return obj;
	}

	void Delete(T* obj)
	{
		obj->~T();
		*(void**)obj = _freeList;
		_freeList = obj;//把空间还回来
	}
private:
	char* _memory = nullptr;	//char类型为1字节大小方便申请任意大小的内存
	size_t _restBytes = 0;	//记录大内存在切分后的剩余比特数
	void* _freeList = nullptr;
};

5. SpanList

SpanList 是一个双向带头节点的双向链表结构，它的大部分功能和双向链表无异，只是在删除节点时，不会真的释放此处的空间，因为内存池还要回收内存进行再分配。

5.1 Span

Span 作为 SpanList 中的一个节点，主要包含以下内容：

class Span
{
public:
	PAGE_ID _pageID = 0;	//大块内存起始页的页号
	size_t _pageNum = 0;	//页的数量

	Span* _next = nullptr;
	Span* _prev = nullptr;

	bool _isUse = false;
	size_t _objSize = 0;	//切好的小对象大小

	size_t _useCount = 0;	//小内存块分配给thread cache的计数
	void* _freeList = nullptr;	//小内存块的自由链表
};

5.2 SpanList代码

class SpanList
{
public:
	SpanList()
	{
		static ObjectPool<Span> spanPool;
		_head = spanPool.New();
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	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;
	}
private:
	Span* _head;
public:
	std::mutex _mtx;
};

6. 完整代码

#pragma once
#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <time.h>
#include <assert.h>
#ifdef _WIN32
#include <Windows.h>
#endif
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32	

typedef size_t PAGE_ID;
#endif

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELIST = 208;	//为thread cache的哈希桶的数量
static const size_t NPAGES = 129;
static const size_t PAGE_SHIFT = 13;

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif __linux__
size_t size = kpage << 13;
void* ptr = mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

#endif

if (ptr == nullptr)
{
	DWORD error = GetLastError();
	printf("VirtualAlloc failed! Error code: %lu\n", error);
	throw std::bad_alloc();
}
return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

#include "ObjectPool.h"

static void*& NextObj(void* obj)
{
	//obj相当于指针的指针
	return *(void**)obj;
}

class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		//头插
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}

	//头插一串小内存
	void PushRange(void* start, void* end,size_t size)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += size;
	}

	void* Pop()
	{
		//头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		--_size;
		return obj;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	//_maxSize会在thread cache申请内存时增加
	size_t& MaxSize()
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}

	void PopRange(void*& start, void*& end, size_t rangeSize)
	{
		assert(rangeSize <= _size);
		start = _freeList;
		end = start;

		for (size_t i = 0; i < rangeSize - 1; i++)
		{
			//走到最后一个节点
			end = NextObj(end);
		}

		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= rangeSize;

	}

private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

class SizeClass
{
public:
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}

	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)	//8byte
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)	//16byte
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8192)	//128byte
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 65535)	//1024byte
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 262144)	//8*1024byte
		{
			return _RoundUp(size, 8192);
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		static int group_array[4] = { 16,56,56,56 };
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024)//这个区间有24个桶
		{
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else
		{
			assert(false);
		}
		return -1;
	}

	//一次thread cache从central cache中获得多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		int num = MAX_BYTES / size;
		if (num < 2)
		{
			num = 2;
		}
		if (num > 512)
		{
			num = 512;
		}

		return num;
	}

	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;

		npage >>= PAGE_SHIFT;
		if (npage == 0)
		{
			npage = 1;
		}
		return npage;
	}
};



class Span
{
public:
	PAGE_ID _pageID = 0;	//大块内存起始页的页号
	size_t _pageNum = 0;	//页的数量

	Span* _next = nullptr;
	Span* _prev = nullptr;

	bool _isUse = false;
	size_t _objSize = 0;	//切好的小对象大小

	size_t _useCount = 0;	//小内存块分配给thread cache的计数
	void* _freeList = nullptr;	//小内存块的自由链表
};

class SpanList
{
public:
	SpanList()
	{
		static ObjectPool<Span> spanPool;
		_head = spanPool.New();
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	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;
	}
private:
	Span* _head;
public:
	std::mutex _mtx;
};