什么是內(nèi)存池

池化技術(shù)

所謂“池化技術(shù)”，就是程序先向系統(tǒng)申請(qǐng)過量的資源，然后自己管理以備不時(shí)之需。之所以要申請(qǐng)過量的資源，是因?yàn)槊看紊暾?qǐng)?jiān)撡Y源都有較大的開銷，不如提前申請(qǐng)好，這樣使用時(shí)就會(huì)變得非?？旖?，大大提高程序運(yùn)行效率。在計(jì)算機(jī)中，有很多使用“池”這種技術(shù)的地方，除了內(nèi)存池，還有連接池、線程池、對(duì)象池等。

以服務(wù)器上的線程池為例，它的主要思想是：先啟動(dòng)若干數(shù)量的線程，讓它們處于睡眠狀態(tài)，當(dāng)接收到客戶端的請(qǐng)求時(shí)，喚醒池中某個(gè)睡眠的線程，讓它來(lái)處理客戶端的請(qǐng)求，當(dāng)處理完這個(gè)請(qǐng)求，線程又進(jìn)入睡眠狀態(tài)。

內(nèi)存池

內(nèi)存池是指程序預(yù)先從操作系統(tǒng)申請(qǐng)一塊足夠大內(nèi)存，此后，當(dāng)程序中需要申請(qǐng)內(nèi)存的時(shí)候，不是直接向操作系統(tǒng)申請(qǐng)，而是直接從內(nèi)存池中獲取；同理，當(dāng)程序釋放內(nèi)存的時(shí)候，并不真正將內(nèi)存返回給操作系統(tǒng)，而是返回內(nèi)存池。當(dāng)程序退出(或者特定時(shí)間)時(shí)，內(nèi)存池才將之前申請(qǐng)的內(nèi)存真正釋放。

內(nèi)存池主要解決的問題

內(nèi)存池主要解決的當(dāng)然是效率的問題，其次,作為系統(tǒng)的內(nèi)存分配器的角度，還需要解決一下內(nèi)存碎片的問題。

內(nèi)存碎片

內(nèi)存碎片分為外碎片和內(nèi)碎片

• 外部碎片是一些空閑的連續(xù)內(nèi)存區(qū)域太小，這些內(nèi)存空間不連續(xù)，以至于合計(jì)的內(nèi)存足夠，但是不能滿足一些的內(nèi)存分配申請(qǐng)需求。
• 內(nèi)部碎片是由于一些對(duì)齊的需求，導(dǎo)致分配出去的空間中一些內(nèi)存無(wú)法被利用。

malloc

C/C++中我們要?jiǎng)討B(tài)申請(qǐng)內(nèi)存都是通過malloc去申請(qǐng)內(nèi)存，實(shí)際我們不是直接去堆獲取內(nèi)存的。

而malloc就是一個(gè)內(nèi)存池。malloc() 相當(dāng)于向操作系統(tǒng)申請(qǐng)了一塊較大的內(nèi)存空間。當(dāng)內(nèi)存用完或程序有大量的內(nèi)存需求時(shí)，再根據(jù)實(shí)際需求向操作系統(tǒng)“申請(qǐng)。

定長(zhǎng)內(nèi)存池

申請(qǐng)內(nèi)存使用的是malloc，什么場(chǎng)景下都可以用，但是意味著什么場(chǎng)景下都不會(huì)有很高的性能，下面我們就先來(lái)設(shè)計(jì)一個(gè)定長(zhǎng)內(nèi)存池

ObjectPool.h

#pragma once
#include <iostream>
#include <vector>
#include <time.h>

using std::cout;
using std::endl;
//定長(zhǎng)內(nèi)存池

//template <size_t N>
//class ObjectPool
//{};
#ifdef _WIN32
	#include <windows.h>
#else
	
#endif

inline static void* SystemAlloc(size_t kpage)//直接去堆上按頁(yè)申請(qǐng)內(nèi)存
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage<<13, MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}
template <class T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		if (_freeList)
		{
			//優(yōu)先把還回來(lái)的內(nèi)存塊再次重復(fù)利用
			void* next = (*(void**)_freeList);
			obj = (T*)_freeList;
			_freeList = next;
		}
		else
		{
			//剩余內(nèi)存不夠一個(gè)對(duì)象大小時(shí)，重新開大塊空間
			if (remainBytes < sizeof(T))
			{
				remainBytes = 128 * 1024 ;
				//_memory = (char*)malloc(remainBytes);
				_memory = (char*)SystemAlloc(remainBytes >> 13);
				if (_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}
			obj = (T*)_memory;
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objSize;
			remainBytes -= objSize;			
		}
		//定位new,顯示調(diào)用T的構(gòu)造函數(shù)初始化，對(duì)已有的空間初始化
		new(obj)T;

		return obj;

		
	}
	void Delete(T* obj)
	{
		
		//還回來(lái)
		
		//顯示調(diào)用析構(gòu)函數(shù)清理對(duì)象
		obj->~T();
		if (_freeList == nullptr)
		{
			_freeList = obj;
			//*(int*)obj = nullptr;//前四個(gè)字節(jié)用來(lái)保存下一個(gè)內(nèi)存的地址 把obj強(qiáng)轉(zhuǎn)成int* 再解引用->int 獲得此地址 64位下跑不了
			*(void**)obj = nullptr;//64位下解引用是void *,*(int**)也可以
		}
		else
		{
			//頭插
			*(void**)obj = _freeList;
			_freeList = obj;
		}
	}
private:
	char* _memory = nullptr;//指向大塊內(nèi)存，char是一個(gè)字節(jié)，好切分內(nèi)存
	size_t remainBytes = 0;//大塊內(nèi)存中剩余數(shù)
	void* _freeList = nullptr;//管理?yè)Q回來(lái)的內(nèi)存(鏈表)的頭指針
	
};

高并發(fā)內(nèi)存池整體框架

現(xiàn)代很多的開發(fā)環(huán)境都是多核多線程，在申請(qǐng)內(nèi)存的場(chǎng)景下，必然存在激烈的鎖競(jìng)爭(zhēng)問題。
內(nèi)存池需要考慮以下幾方面的問題。

1. 性能問題。
2. 多線程環(huán)境下，鎖競(jìng)爭(zhēng)問題。
3. 內(nèi)存碎片問題。

concurrent memory pool：

• thread cache：線程緩存是每個(gè)線程獨(dú)有的，用于小于256KB的內(nèi)存的分配，線程從這里申請(qǐng)內(nèi)存不需要加鎖，每個(gè)線程獨(dú)享一個(gè)cache，這也就是這個(gè)并發(fā)線程池高效的地方。
• central cache：中心緩存是所有線程所共享，thread cache是按需從central cache中獲取的對(duì)象。central cache合適的時(shí)機(jī)回收thread cache中的對(duì)象，避免一個(gè)線程占用了太多的內(nèi)存，而其他線程的內(nèi)存吃緊，達(dá)到內(nèi)存分配在多個(gè)線程中更均衡的按需調(diào)度的目的。central cache是存在競(jìng)爭(zhēng)的，所以從這里取內(nèi)存對(duì)象是需要加鎖，首先這里用的是桶鎖，其次只有thread cache的沒有內(nèi)存對(duì)象時(shí)才會(huì)找central cache，所以這里競(jìng)爭(zhēng)不會(huì)很激烈。
• page cache：頁(yè)緩存是在central cache緩存上面的一層緩存，存儲(chǔ)的內(nèi)存是以頁(yè)為單位存儲(chǔ)及分配的，central cache沒有內(nèi)存對(duì)象時(shí)，從page cache分配出一定數(shù)量的page，并切割成定長(zhǎng)大小的小塊內(nèi)存，分配給central cache。當(dāng)一個(gè)span的幾個(gè)跨度頁(yè)的對(duì)象都回收以后，page cache會(huì)回收central cache滿足條件的span對(duì)象，并且合并相鄰的頁(yè)，組成更大的頁(yè)，緩解內(nèi)存碎片的問題。

thread cache

thread cache是哈希桶結(jié)構(gòu)，每個(gè)桶是一個(gè)按桶位置映射大小的內(nèi)存塊對(duì)象的自由鏈表。每個(gè)線程都會(huì)有一個(gè)thread cache對(duì)象，這樣每個(gè)線程在這里獲取對(duì)象和釋放對(duì)象時(shí)是無(wú)鎖的。

自由鏈表的哈希桶跟對(duì)象大小的映射關(guān)系

class SizeClass//計(jì)算對(duì)象大小的對(duì)齊映射規(guī)則
{
public:
	// 整體控制在最多10%左右的內(nèi)碎片浪費(fèi)
	// [1,128] 8byte對(duì)齊       freelist[0,16)
	// [128+1,1024] 16byte對(duì)齊   freelist[16,72)
	// [1024+1,8*1024] 128byte對(duì)齊   freelist[72,128)
	// [8*1024+1,64*1024] 1024byte對(duì)齊     freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte對(duì)齊   freelist[184,208)
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)//計(jì)算對(duì)齊數(shù)
	{
		//size_t alignSize ;//對(duì)齊
		//if (size % 8 != 0)
		//{
		//	alignSize = (size / alignNum + 1) * alignNum;
		//}
		//else
		//{
		//	alignSize = size;
		//}
		//return alignSize;
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

映射哪一個(gè)自由鏈表桶

static inline size_t _Index(size_t bytes, size_t alignNum)
	{
		/*if (bytes % alignNum == 0)
		{
		return bytes / alignNum - 1;
		}
		else
		{
		return bytes / alignNum;
		}*/
		return ((bytes + (1 << alignNum) - 1) >> alignNum) - 1;
	}
	// 計(jì)算映射的哪一個(gè)自由鏈表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每個(gè)區(qū)間有多少個(gè)鏈
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);//8  2^3
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];//把前面128減掉，再加上前一個(gè)桶的數(shù)量
		}
		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) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

申請(qǐng)內(nèi)存：

• 當(dāng)內(nèi)存申請(qǐng)size<=256KB，先獲取到線程本地存儲(chǔ)的thread cache對(duì)象，計(jì)算size映射的哈希桶自由鏈表下標(biāo)i。
• 如果自由鏈表_freeLists[i]中有對(duì)象，則直接Pop一個(gè)內(nèi)存對(duì)象返回。
• 如果_freeLists[i]中沒有對(duì)象時(shí)，則批量從central cache中獲取一定數(shù)量的對(duì)象，插入到自由鏈表并返回一個(gè)對(duì)象。

釋放內(nèi)存

• 當(dāng)釋放內(nèi)存小于256k時(shí)將內(nèi)存釋放回thread cache，計(jì)算size映射自由鏈表桶位置i，將對(duì)象Push到_freeLists[i]。
• 當(dāng)鏈表的長(zhǎng)度過長(zhǎng)，則回收一部分內(nèi)存對(duì)象到central cache。

thread cache 設(shè)計(jì)

#pragma once
#include "Common.h"

class ThreadCache
{
public:
	//申請(qǐng)和釋放對(duì)象
	void* Allocate(size_t size);
	void Deallocate(void* ptr, size_t size);
	//從中心緩存獲取對(duì)象
	void* FetchFromCentralCache(size_t index, size_t size);

	void ListTooLong(FreeList& list, size_t size);//釋放對(duì)象時(shí)，鏈表過長(zhǎng)  ，回收內(nèi)存到centrral cache
private:
	FreeList _freeLists[NFREELISTS];//哈希表，每個(gè)位置掛的都是_freeList
};

// TLS:在線程內(nèi)全局可訪問，但不能被其他線程訪問到->保持?jǐn)?shù)據(jù)的獨(dú)立性，不需要鎖控制，減少成本
static _declspec(thread) ThreadCache * pTLSThreadCache = nullptr;

central cache

central cache也是一個(gè)哈希桶結(jié)構(gòu)(t桶鎖)，他的哈希桶的映射關(guān)系跟thread cache是一樣的。不同的是他的每個(gè)哈希桶位置掛是SpanList鏈表結(jié)構(gòu)，不過每個(gè)映射桶下面的span中的大內(nèi)存塊被按映射關(guān)系切成了一個(gè)個(gè)小內(nèi)存塊對(duì)象掛在span的自由鏈表中。

申請(qǐng)內(nèi)存：

• 當(dāng)thread cache中沒有內(nèi)存時(shí)，就會(huì)批量向central cache申請(qǐng)一些內(nèi)存對(duì)象，這里的批量獲取對(duì) 象的數(shù)量使用了類似網(wǎng)絡(luò)tcp協(xié)議擁塞控制的慢開始算法；central cache也有一個(gè)哈希映射的spanlist，spanlist中掛著span，從span中取出對(duì)象給thread cache，這個(gè)過程是需要加鎖的，這里使用的是一個(gè)桶鎖，盡可能提高效率。
• central cache映射的spanlist中所有span的都沒有內(nèi)存以后，則需要向page cache申請(qǐng)一個(gè)新的span對(duì)象，拿到span以后將span管理的內(nèi)存按大小切好作為自由鏈表鏈接到一起。然后從span中取對(duì)象給thread cache
• central cache的中掛的span中use_count記錄分配了多少個(gè)對(duì)象出去，分配一個(gè)對(duì)象給threadcache，就++use_count

釋放內(nèi)存

• 當(dāng)thread_cache過長(zhǎng)或者線程銷毀，則會(huì)將內(nèi)存釋放回central cache中的，釋放回來(lái)時(shí)–use_count。當(dāng)use_count減到0時(shí)則表示所有對(duì)象都回到了span，則將span釋放回page cache，page cache中會(huì)對(duì)前后相鄰的空閑頁(yè)進(jìn)行合并。

以頁(yè)為單位的大內(nèi)存管理span的定義及spanlist定義

struct Span//管理多個(gè)連續(xù)大塊內(nèi)存跨度結(jié)構(gòu)
{
	PAGE_ID _pageId = 0;//大塊內(nèi)存起始頁(yè)號(hào)
	size_t n = 0;//頁(yè)的數(shù)量
	Span* _next = nullptr;//雙向鏈表
	Span* _prev = nullptr;//雙向鏈表

	size_t _objSize = 0;//切好的小對(duì)象的大小
	size_t _useCount = 0;//切好的小塊內(nèi)存，被分給thread cache計(jì)數(shù)
	void* _freeList = nullptr;//切好的小塊內(nèi)存自由鏈表
	bool _isUse = false;//是否被使用

};
class SpanList//帶頭雙向鏈表
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	bool Empty()
	{
		//cout << "heool spanlist empty" << endl;
		return _head->_next == _head;
	}
	void PushFront(Span* span)
	{
		//cout << "hello common pushfront" << endl;
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		//cout << "hello commom popfront" << endl;
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	void Insert(Span* pos, Span* newSpan)
	{
		//cout << "hello commom insert" << endl;
		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;//桶鎖

};

central cache整體設(shè)計(jì)

#pragma once
#include "Common.h"

//單例模式
class CentralCache
{
public:
	static CentralCache* GetInstance()
	{
		return &_sInst;
	}

	// 獲取一個(gè)非空的span
	Span* GetOneSpan(SpanList& list, size_t byte_size);

	// 從中心緩存獲取一定數(shù)量的對(duì)象給thread cache
	size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size);

	// 將一定數(shù)量的對(duì)象釋放到span跨度
	void ReleaseListToSpans(void* start, size_t byte_size);

private:
	SpanList _spanLists[NFREELISTS];//在ThreadCache是幾號(hào)桶，在CentralCache就是幾號(hào)桶
private:
	CentralCache() //把構(gòu)造函數(shù)放在私有：別人不能創(chuàng)建對(duì)象
	{}
	CentralCache(const CentralCache&) = delete;
	static CentralCache _sInst;

};

page cache

申請(qǐng)內(nèi)存：

• 當(dāng)central cache向page cache申請(qǐng)內(nèi)存時(shí)，page cache先檢查對(duì)應(yīng)位置有沒有span，如果沒有則向更大頁(yè)尋找一個(gè)span，如果找到則分裂成兩個(gè)。比如：申請(qǐng)的是4頁(yè)page，4頁(yè)page后面沒有掛span，則向后面尋找更大的span，假設(shè)在10頁(yè)page位置找到一個(gè)span，則將10頁(yè)page span分裂為一個(gè)4頁(yè)pagespan和一個(gè)6頁(yè)page span
• 如果找到_spanList[128]都沒有合適的span，則向系統(tǒng)使用mmap、brk或者是VirtualAlloc等方式申請(qǐng)128頁(yè)page span掛在自由鏈表中，再重復(fù)1中的過程。
• 需要注意的是central cache和page cache 的核心結(jié)構(gòu)都是spanlist的哈希桶，但是他們是有本質(zhì)區(qū)別的，central cache中哈希桶，是按跟thread cache一樣的大小對(duì)齊關(guān)系映射的，他的spanlist中掛的span中的內(nèi)存都被按映射關(guān)系切好鏈接成小塊內(nèi)存的自由鏈表。而page cache 中的spanlist則是按下標(biāo)桶號(hào)映射的，也就是說(shuō)第i號(hào)桶中掛的span都是i頁(yè)內(nèi)存。

釋放內(nèi)存：

• 如果central cache釋放回一個(gè)span，則依次尋找span的前后page id的沒有在使用的空閑span，看是否可以合并，如果合并繼續(xù)向前尋找。這樣就可以將切小的內(nèi)存合并收縮成大的span，減少內(nèi)存碎片
• 如果Central Cache中的span usecount=0說(shuō)明切分給 thread cache的小塊內(nèi)存都回來(lái)了則Central Cache 把這個(gè)span還給page cache,page cache通過頁(yè)號(hào)查看前后相鄰頁(yè)是否空閑，是就合并出更大的頁(yè)

整體設(shè)計(jì)

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

class PageCache
{
public:
	static PageCache* GetInstance()
	{
		//cout << "hello Page cache getinstance" << endl;
		return &_sInst;
	}
	Span* MapObjectToSpan(void* obj);//獲取對(duì)象到span的映射

	Span* NewSpan(size_t k);//獲取一個(gè)k頁(yè)的span

	void ReleaseSpanToPageCache(Span* span);//釋放空閑span,合并相鄰的span
	std::mutex _pageMtx;
private:
	SpanList _spanList[NPAGES];
	ObjectPool<Span> spanPool;
	std::unordered_map<PAGE_ID,Span*> _idSpanMap;//頁(yè)號(hào)跟span的映射
	PageCache() {}
	PageCache(const PageCache&) = delete;
	static PageCache _sInst;
};

代碼總體實(shí)現(xiàn)

ObjectPool.h

#pragma once
#pragma once
#include <iostream>
#include <vector>
#include <time.h>
#include "Common.h"
using std::cout;
using std::endl;
//定長(zhǎng)內(nèi)存池

//template <size_t N>
//class ObjectPool
//{};

/*
#ifdef _WIN32
#include <windows.h>
#else

#endif
inline static void* SystemAlloc(size_t kpage)//直接去堆上按頁(yè)申請(qǐng)內(nèi)存
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}
*/
template <class T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		if (_freeList)
		{
			//優(yōu)先把還回來(lái)的內(nèi)存塊再次重復(fù)利用
			void* next = (*(void**)_freeList);
			obj = (T*)_freeList;
			_freeList = next;
			
		}
		else
		{
			//剩余內(nèi)存不夠一個(gè)對(duì)象大小時(shí)，重新開大塊空間
			if (remainBytes < sizeof(T))
			{
				remainBytes = 128 * 1024;
				//_memory = (char*)malloc(remainBytes);
				_memory = (char*)SystemAlloc(remainBytes >> 13);
				if (_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}
			obj = (T*)_memory;
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objSize;
			remainBytes -= objSize;
		}
		//定位new,顯示調(diào)用T的構(gòu)造函數(shù)初始化，對(duì)已有的空間初始化
		new(obj)T;

		return obj;


	}
	void Delete(T* obj)
	{

		//還回來(lái)

		//顯示調(diào)用析構(gòu)函數(shù)清理對(duì)象
		obj->~T();
		if (_freeList == nullptr)
		{
			_freeList = obj;
			//*(int*)obj = nullptr;//前四個(gè)字節(jié)用來(lái)保存下一個(gè)內(nèi)存的地址 把obj強(qiáng)轉(zhuǎn)成int* 再解引用->int 獲得此地址 64位下跑不了
			*(void**)obj = nullptr;//64位下解引用是void *,*(int**)也可以
		}
		else
		{
			//頭插
			*(void**)obj = _freeList;
			_freeList = obj;
		}
	}
private:
	char* _memory = nullptr;//指向大塊內(nèi)存，char是一個(gè)字節(jié)，好切分內(nèi)存
	size_t remainBytes = 0;//大塊內(nèi)存中剩余數(shù)
	void* _freeList = nullptr;//管理?yè)Q回來(lái)的內(nèi)存(鏈表)的頭指針

};

Common.h

#pragma once
//公共文件

#include <iostream>
#include <vector>
#include <time.h>
#include <assert.h>
#include <thread>
#include <mutex>
#include <algorithm>
#include <windows.h>
#include <unordered_map>
#include <map>
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;//256 KB
static const size_t NFREELISTS = 208;//桶的總數(shù)量
static const size_t NPAGES = 129;//頁(yè)的數(shù)量
static const size_t PAGE_SHIFT = 13;//

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#else
 //linux
#endif

inline static void* SystemAlloc(size_t kpage)//直接去堆上按頁(yè)申請(qǐng)內(nèi)存
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

static void*& NextObj(void* obj)//取對(duì)象的頭4/8字節(jié)
{
	return *(void**)obj;
}
class FreeList //管理切分好的小對(duì)象的自由鏈表
{
public:
	void Push(void* obj)//插入
	{
		//頭插
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;
		_size++;
	}
	void PushRange(void* start, void* end, size_t n)
	{
		//cout << "hello common pushrange" << endl;
		NextObj(end) = _freeList;
		_freeList = start;

		/*
		//測(cè)試驗(yàn)證+條件斷點(diǎn)
		int i = 0;
		void* cur = start;
		while (cur)
		{
			i++;
			cur = NextObj(cur);
		}
		if (n != i)
		{
			//int x = 0;
			cout << "不匹配" << endl;
		}
		*/
		_size += n;

	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		
		assert(n >= _size);
		start = _freeList;
		end = start;
		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	void* Pop()//彈出對(duì)象
	{
		//頭刪
		assert(_freeList);
		void* obj = _freeList;
		_freeList = NextObj(obj);
		_size--;
		return obj;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;//
	size_t _size = 0;//個(gè)數(shù)
};

class SizeClass//計(jì)算對(duì)象大小的對(duì)齊映射規(guī)則
{
public:
	// 整體控制在最多10%左右的內(nèi)碎片浪費(fèi)
	// [1,128] 8byte對(duì)齊       freelist[0,16)
	// [128+1,1024] 16byte對(duì)齊   freelist[16,72)
	// [1024+1,8*1024] 128byte對(duì)齊   freelist[72,128)
	// [8*1024+1,64*1024] 1024byte對(duì)齊     freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte對(duì)齊   freelist[184,208)
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)//計(jì)算對(duì)齊數(shù)
	{
		//size_t alignSize ;//對(duì)齊
		//if (size % 8 != 0)
		//{
		//	alignSize = (size / alignNum + 1) * alignNum;
		//}
		//else
		//{
		//	alignSize = size;
		//}
		//return alignSize;
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}
	static inline size_t RoundUp(size_t size)//計(jì)算對(duì)齊數(shù)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
			//assert(false);
			//return -1;
		}
	}

	static inline size_t _Index(size_t bytes, size_t alignNum)
	{
		/*if (bytes % alignNum == 0)
		{
		return bytes / alignNum - 1;
		}
		else
		{
		return bytes / alignNum;
		}*/
		return ((bytes + (1 << alignNum) - 1) >> alignNum) - 1;
	}
	// 計(jì)算映射的哪一個(gè)自由鏈表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每個(gè)區(qū)間有多少個(gè)鏈
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);//8  2^3
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];//把前面128減掉，再加上前一個(gè)桶的數(shù)量
		}
		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) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}
	static size_t NumMoveSize(size_t size)// 一次thread cache從中心緩存獲取多少個(gè)對(duì)象
	{
		assert(size > 0);
		// [2, 512]，一次批量移動(dòng)多少個(gè)對(duì)象的(慢啟動(dòng))上限值
		// 小對(duì)象一次批量上限高
		// 小對(duì)象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}


	static size_t NumMovePage(size_t size)// 計(jì)算一次向系統(tǒng)獲取幾個(gè)頁(yè)
	{
		// 單個(gè)對(duì)象 8byte
		// ...
		// 單個(gè)對(duì)象 256KB
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;
		return npage;
	}
};

struct Span//管理多個(gè)連續(xù)大塊內(nèi)存跨度結(jié)構(gòu)
{
	PAGE_ID _pageId = 0;//大塊內(nèi)存起始頁(yè)號(hào)
	size_t n = 0;//頁(yè)的數(shù)量
	Span* _next = nullptr;//雙向鏈表
	Span* _prev = nullptr;//雙向鏈表

	size_t _objSize = 0;//切好的小對(duì)象的大小
	size_t _useCount = 0;//切好的小塊內(nèi)存，被分給thread cache計(jì)數(shù)
	void* _freeList = nullptr;//切好的小塊內(nèi)存自由鏈表
	bool _isUse = false;//是否被使用

};
class SpanList//帶頭雙向鏈表
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	bool Empty()
	{
		//cout << "heool spanlist empty" << endl;
		return _head->_next == _head;
	}
	void PushFront(Span* span)
	{
		//cout << "hello common pushfront" << endl;
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		//cout << "hello commom popfront" << endl;
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	void Insert(Span* pos, Span* newSpan)
	{
		//cout << "hello commom insert" << endl;
		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);

		//1、條件斷點(diǎn)
		//2、查看棧幀
		/*
		if (pos = _head)
		{
			int x = 0;
		}
		*/
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;

	}
private:
	Span* _head;
public:

	std::mutex _mtx;//桶鎖

};

ConcurrentAlloc.h

#pragma once
#include "Common.h"
#include "ThreadCache.h"
#include "PageCache.h"
#include "ObjectPool.h"
static void* ConcurrentAlloc(size_t  size)//線程調(diào)用申請(qǐng)內(nèi)存
{
	//通過TLS 每個(gè)線程無(wú)鎖的獲取自己的專屬ThreadCache對(duì)象
	if (size > MAX_BYTES)
	{
		size_t alignSize = SizeClass::RoundUp(size);//對(duì)齊
		size_t kpage = alignSize >> PAGE_SHIFT;//獲取頁(yè)數(shù)

		PageCache::GetInstance()->_pageMtx.lock();
		Span* span = PageCache::GetInstance()->NewSpan(kpage);
		//span->_objSize = size;
		PageCache::GetInstance()->_pageMtx.unlock();

		void* ptr = (void*)(span->_pageId << PAGE_SHIFT);
		return ptr;
	}
	else
	{
		if (pTLSThreadCache == nullptr)
		{
			
			//pTLSThreadCache = new ThreadCache;
			static ObjectPool<ThreadCache> tcPool;
			pTLSThreadCache = tcPool.New();
		}
		cout << std::this_thread::get_id() << ":" << pTLSThreadCache << endl;
		return pTLSThreadCache->Allocate(size);
	}
	
}
static void ConcurrentFree(void* ptr)
{
	//size:不給大小不知道要還給桶的哪個(gè)位置
	Span* span = PageCache::GetInstance()->MapObjectToSpan(ptr);
	size_t size = span->_objSize;//對(duì)齊以后的大小
	if (size > MAX_BYTES)
	{
	
		

		PageCache::GetInstance()->_pageMtx.lock();
		
		
		PageCache::GetInstance()->ReleaseSpanToPageCache(span);
		PageCache::GetInstance()->_pageMtx.unlock();
	}
	else
	{
		assert(pTLSThreadCache);
		pTLSThreadCache->Deallocate(ptr, size);
	}

	
}

ThreadCache.h

#pragma once
#include "Common.h"

class ThreadCache
{
public:
	//申請(qǐng)和釋放對(duì)象
	void* Allocate(size_t size);
	void Deallocate(void* ptr, size_t size);
	//從中心緩存獲取對(duì)象
	void* FetchFromCentralCache(size_t index, size_t size);

	void ListTooLong(FreeList& list, size_t size);//釋放對(duì)象時(shí)，鏈表過長(zhǎng)  ，回收內(nèi)存到centrral cache
private:
	FreeList _freeLists[NFREELISTS];//哈希表，每個(gè)位置掛的都是_freeList
};

// TLS:在線程內(nèi)全局可訪問，但不能被其他線程訪問到->保持?jǐn)?shù)據(jù)的獨(dú)立性，不需要鎖控制，減少成本
static _declspec(thread) ThreadCache * pTLSThreadCache = nullptr;

ThreadCache.cpp

#include "ThreadCache.h"
#include "CentralCache.h"
#include "Common.h"

void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
	cout << "hello common fecthcenrercache" << endl;
	//慢開始反饋調(diào)節(jié)算法
	//最開始不會(huì)向 central cache要太多因?yàn)榭赡苡貌煌?，如果不要size大小需求batchNum會(huì)不斷增長(zhǎng)直到上限;
	//size越大一次向central cache要的越小，size越小一次向central cache要的越大
	size_t batchNum = min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));

	if (_freeLists[index].MaxSize() == batchNum)
	{
		_freeLists[index].MaxSize() += 1;
	}

	void* start = nullptr;
	void* end = nullptr;
	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum,size);

	

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

	return nullptr;
}
void* ThreadCache::Allocate(size_t size)//申請(qǐng)對(duì)象
{
	//
	assert(size <= MAX_BYTES);
	size_t alignSize = SizeClass::RoundUp(size);//獲取對(duì)其數(shù)
	size_t index = SizeClass::Index(size);//在哪一個(gè)桶-》獲取桶的位置
	if (!_freeLists[index].Empty())
	{
		return _freeLists[index].Pop();
	}
	else
	{
		return FetchFromCentralCache(index,alignSize);//從中心緩存獲取對(duì)象
	}
}
void ThreadCache::Deallocate(void* ptr, size_t size)//釋放對(duì)象
{
	assert(size <= MAX_BYTES);
	assert(ptr);

	//找出自由鏈表映射的桶，對(duì)象插入
	size_t index = SizeClass::Index(size);//屬于哪個(gè)桶
	_freeLists[index].Push(ptr);

	//當(dāng)鏈表長(zhǎng)度大于等于一次批量申請(qǐng)的內(nèi)存時(shí)就開始還一段內(nèi)存給central cache
	if (_freeLists[index].Size() >= _freeLists[index].MaxSize())
	{	ListTooLong(_freeLists[index], size);
	}
}
void ThreadCache::ListTooLong(FreeList& list, size_t size)
{
	void* start = nullptr;
	void* end = nullptr;
	list.PopRange(start,end,list.MaxSize());//取出內(nèi)存

	//把內(nèi)存還給下一層：central cache
	CentralCache::GetInstance()->ReleaseListToSpans(start,size);
}

CentralCache.h

#include "CentralCache.h"
#include "PageCache.h"
CentralCache CentralCache::_sInst;
Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{
	//cout << "hello central getonspan" << endl;
	
	// 從SpanLists或者Page cache 獲取一個(gè)非空的span
	//查看當(dāng)前spanlist中是否還有非空的/還未分配對(duì)象的
	Span* it = list.Begin();
	
	while (it != list.End())
	{
		if (it->_freeList != nullptr)
		{
			//掛著對(duì)象
			return it;
		}
		else
		{
			it = it->_next;
		}

	}
	
	//先把central cache的桶鎖解掉，這樣如果其他線程釋放內(nèi)存對(duì)象回來(lái)不會(huì)阻塞
	list._mtx.unlock();

	//沒有空閑span,找 page cache要
	PageCache::GetInstance()->_pageMtx.lock();
	Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(size));
	span->_isUse = true;
	span->_objSize = size;
	PageCache::GetInstance()->_pageMtx.unlock();

	//對(duì)獲取的span進(jìn)行切分吧、，不需要加鎖，因?yàn)槠渌€程訪問不到這個(gè)span

	//通過頁(yè)號(hào)計(jì)算起始地址: 頁(yè)號(hào)<<PAGE_SHIFT
	char* start = (char*)(span->_pageId << PAGE_SHIFT);
	size_t bytes = span->n << PAGE_SHIFT;//計(jì)算span的大塊起始地址和大塊內(nèi)存的大小(字節(jié)數(shù))
	char* end = start + bytes;

	//把大塊內(nèi)存切成自由鏈表連接起來(lái)
	//先切一塊下來(lái)去做頭，方便尾插
	span->_freeList = start;
	start += size;
	int i = 1;
	void* tail = span->_freeList;
	while (start < end)
	{
		i++;
		NextObj(tail) = start;
		tail = NextObj(tail);//tail = start
		start += size;
	}
	NextObj(tail) = nullptr;//尾插最后一位需要置空

	list._mtx.lock();//切好span以后需要把span掛到桶里去再加鎖
	list.PushFront(span);

	return span;
}

size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)// 從中心緩存獲取一定數(shù)量的對(duì)象給thread cache
{
	//cout << "hello hello central getonspan" << endl;
	size_t index = SizeClass::Index(size);//先查看是哪個(gè)桶的
	_spanLists[index]._mtx.lock();

	Span* span = GetOneSpan(_spanLists[index], size);//先去找一個(gè)非空的span
	assert(span);
	assert(span->_freeList);

	//從span中獲取batchNum個(gè)對(duì)象
	//如果不夠batchNum,有多少拿多少

	start = span->_freeList;
	end = start;
	size_t i = 0;
	size_t actualNum = 1;
	while (i < batchNum - 1 && NextObj(end) != nullptr)//end 往后走batchNum -1個(gè)
	{
		end = NextObj(end);
		++i;
		++actualNum;
	}

	span->_freeList = NextObj(end);
	NextObj(end) = nullptr;
	span->_useCount += actualNum;//被使用的個(gè)數(shù) 

	_spanLists[index]._mtx.unlock();
	return actualNum;
	

}
void CentralCache::ReleaseListToSpans(void* start, size_t size)
{
	size_t index = SizeClass::Index(size);//屬于哪一個(gè)桶
	_spanLists[index]._mtx.lock();
	while (start)
	{
		void* next = NextObj(start);
		Span* span = PageCache::GetInstance()->MapObjectToSpan(start);//找出對(duì)應(yīng)的span
		NextObj(start) = span->_freeList;
		span->_freeList = start;
		span->_useCount--;
		if (span->_useCount == 0)//說(shuō)明span切分出去的的所有小內(nèi)存都回來(lái)了，
		{//該span可以歸還給page cache,page cache再可以去做前后頁(yè)的合并
			_spanLists[index].Erase(span);
			span->_freeList = nullptr;
			span->_next = nullptr;
			span->_prev = nullptr;

			//span還給下一層
			_spanLists[index]._mtx.unlock();

			//釋放span給Page cache時(shí)，使用page cache鎖
			//這時(shí)把桶鎖解掉
			PageCache::GetInstance()->_pageMtx.lock();
			PageCache::GetInstance()->ReleaseSpanToPageCache(span);
			PageCache::GetInstance()->_pageMtx.unlock();

			_spanLists[index]._mtx.lock();
		}
		start = next;
	}


	_spanLists[index]._mtx.unlock();


}

Pagecache.h

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

class PageCache
{
public:
	static PageCache* GetInstance()
	{
		//cout << "hello Page cache getinstance" << endl;
		return &_sInst;
	}
	Span* MapObjectToSpan(void* obj);//獲取對(duì)象到span的映射

	Span* NewSpan(size_t k);//獲取一個(gè)k頁(yè)的span

	void ReleaseSpanToPageCache(Span* span);//釋放空閑span,合并相鄰的span
	std::mutex _pageMtx;
private:
	SpanList _spanList[NPAGES];
	ObjectPool<Span> spanPool;
	std::map<PAGE_ID, Span*> _idSpanMap;//頁(yè)號(hào)跟span的映射
	//std::unordered_map<PAGE_ID,Span*> _idSpanMap;//頁(yè)號(hào)跟span的映射

	PageCache() {}
	PageCache(const PageCache&) = delete;
	static PageCache _sInst;
};

PageCache.cpp

#include "PageCache.h"
PageCache PageCache::_sInst;

Span* PageCache::NewSpan(size_t k)//獲取k頁(yè)的span
{
	//eg:只有一個(gè)128頁(yè)的，需要兩頁(yè)的-》128分為2span和126span，2返回給central cache,126掛道對(duì)應(yīng)的桶上
	//如果central cache中的span usecount=0,說(shuō)明切分給thread cache小塊內(nèi)存都還回來(lái)了，
	//則central cache把span還給page cache,page cache通過頁(yè)號(hào)查看相鄰頁(yè)是否空閑，是就合并出更大的page,解決內(nèi)存碎片問題
	assert(k > 0 && k < NPAGES);
	
	if (k > NPAGES - 1)
	{
		void* ptr = SystemAlloc(k);//大于最大頁(yè)數(shù)直接找堆要
		//Span* span = new Span;
		Span* span = spanPool.New();
		span->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
		span->n = k;
		_idSpanMap[span->_pageId] = span;
		return span;
	}
	
	if (!_spanList[k].Empty())//第k個(gè)桶里面有沒有span
	{
		
		Span* KSpan = _spanList[k].PopFront();
		
		//建立id和span的映射關(guān)系方便centralcache回收小塊內(nèi)存時(shí)查找對(duì)應(yīng)的span
		for (PAGE_ID i = 0; i < KSpan->n; i++)
		{
			_idSpanMap[KSpan->_pageId + i] = KSpan;

		}
		
		return KSpan;
	}

	//第k個(gè)桶里是空的,檢測(cè)后面的桶里有沒有span,如果有進(jìn)行切分
	//切分成一個(gè)k頁(yè)的span和一個(gè) n-k 頁(yè)的span
	//k頁(yè)的span返回給central cache,n-k 頁(yè)的span掛到第 n-k 號(hào)桶中去
	for (size_t i = k ; i < NPAGES; i++)
	{		
		if (!_spanList[i].Empty())
		{
			Span* nSpan = _spanList[i].PopFront();
			//Span* KSpan = new Span;
			Span* KSpan = spanPool.New();
			

			//在nSpan的頭部切下K頁(yè)
			//k頁(yè)span返回，nSpan再掛到對(duì)應(yīng)映射
			KSpan->_pageId = nSpan->_pageId;
			KSpan->n = k;//kSpan頁(yè)數(shù)變?yōu)閗
			nSpan->_pageId += k;//nSpan 頁(yè)號(hào)變?yōu)?+= k
			nSpan->n -= k;
			
			_spanList[nSpan->n].PushFront(nSpan);//把剩余的頁(yè)掛到對(duì)應(yīng)的位置

			
			//存儲(chǔ)nSpan的首尾頁(yè)號(hào)跟span映射,方便page cache回收內(nèi)存時(shí)進(jìn)行合并查找
			_idSpanMap[nSpan->_pageId] = nSpan;
			_idSpanMap[nSpan->_pageId + nSpan->n - 1] = nSpan;
			

			//建立id和span的映射，方便central cache回收查找對(duì)應(yīng)的span
			for (PAGE_ID i = 0; i < KSpan->n; i++)
			{
				_idSpanMap[KSpan->_pageId + i] = KSpan;
			}
			
			
			return KSpan;
		}
	}

	//沒有大頁(yè)span
	//找堆要128頁(yè)的span
	Span* bigSpan = spanPool.New();
	//Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->n = NPAGES - 1;
	_spanList[bigSpan->n].PushFront(bigSpan);
	return NewSpan(k);

}

Span* PageCache::MapObjectToSpan(void* obj)
{
	
	PAGE_ID id = ((PAGE_ID)obj >> PAGE_SHIFT);//找出頁(yè)號(hào)
	std::unique_lock<std::mutex> lock(_pageMtx);
	auto ret = _idSpanMap.find(id);
	if (ret != _idSpanMap.end())
	{
		return ret->second;//返回span的指針
	}
	else
	{
		assert(false);
		return nullptr;
	}
}
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	//對(duì)span前后的頁(yè)進(jìn)行合并，解決內(nèi)存碎片問題

	if (span->n > NPAGES - 1)
	{
		//大于128頁(yè)的直接還給堆
		void* ptr = (void*)(span->_pageId << PAGE_SHIFT);
		SystemFree(ptr);
		//delete span;
		spanPool.Delete(span);
		return;
	}
	//向前合并
	while (1)
	{
		PAGE_ID prevId = span->_pageId - 1;
		auto ret = _idSpanMap.find(prevId);

		if (ret == _idSpanMap.end())
		{//前面的頁(yè)號(hào)沒有，不合并
			break;
		}
		Span* prevspan = ret->second;
		if (prevspan->_isUse == true)
		{//前面相鄰頁(yè)的span在使用
			break;
		}
		if (prevspan->n + span->n > NPAGES - 1)
		{
			//合并數(shù)超過128，沒辦法管理
			break;
		}
		//合并
		span->_pageId = prevspan->_pageId;
		span->n += prevspan->n;
		_spanList[prevspan->n].Erase(prevspan);
		//delete prevspan;
		
		spanPool.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;
		}
		if (nextspan->n + span->n > NPAGES - 1)
		{
			break;
		}
		span->n += nextspan->n;
		_spanList[nextspan->n].Erase(nextspan);
		//delete(nextspan);
		spanPool.Delete(nextspan);

	}
	//前后都合并過了

	_spanList[span->n].PushFront(span);
	span->_isUse = false;

	//方便其他把此span合并
	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->n - 1] = span;

}

復(fù)雜問題的調(diào)試技巧

• 條件斷點(diǎn):一般情況下可以直接運(yùn)行程序，通過報(bào)錯(cuò)來(lái)查找問題。如果是斷言錯(cuò)誤，那么可以直接定位到報(bào)錯(cuò)位置，然后將此處的斷言改為與if判斷，在if語(yǔ)句里面打上一個(gè)斷點(diǎn)(空語(yǔ)句是無(wú)法打斷點(diǎn)可以隨便在if里面加上一句代碼)，條件斷點(diǎn)也客設(shè)置為普通斷點(diǎn)，設(shè)置相應(yīng)的條件，程序滿足該條件則會(huì)停下。
• 查看函數(shù)棧幀：當(dāng)前函數(shù)棧幀的調(diào)用情況(黃色箭頭指向的是當(dāng)前所在的函數(shù)棧幀)雙擊函數(shù)棧幀中的其他函數(shù)可以跳轉(zhuǎn)對(duì)應(yīng)的棧幀(淺灰色箭頭指向的就是當(dāng)前跳轉(zhuǎn)到的函數(shù)棧幀)
• 死循環(huán)時(shí)中斷程序：調(diào)試→全部中斷，程序會(huì)在當(dāng)前運(yùn)行的地方停下

vs2013性能分析

調(diào)試-》性能與診斷-》開始-》檢測(cè)

實(shí)現(xiàn)基數(shù)樹進(jìn)行優(yōu)化

單層基數(shù)樹

實(shí)際采用的就是直接定址法，每一個(gè)頁(yè)號(hào)對(duì)應(yīng)span的地址就存儲(chǔ)數(shù)組中在以該頁(yè)號(hào)為下標(biāo)的位置

二層基數(shù)樹

這里還是以32位平臺(tái)下，一頁(yè)的大小為8K為例來(lái)說(shuō)明，此時(shí)存儲(chǔ)頁(yè)號(hào)最多需要19個(gè)比特位。而二層基數(shù)樹實(shí)際上就是把這19個(gè)比特位分為兩次進(jìn)行映射。

三層基數(shù)樹

上面一層基數(shù)樹和二層基數(shù)樹都適用于32位平臺(tái)，而對(duì)于64位的平臺(tái)就需要用三層基數(shù)樹了。三層基數(shù)樹與二層基數(shù)樹類似，三層基數(shù)樹實(shí)際上就是把存儲(chǔ)頁(yè)號(hào)的若干比特位分為三次進(jìn)行映射。

代碼實(shí)現(xiàn)

PageMap.h

#pragma once
#include "Common.h"
#include "ObjectPool.h"
template <int BITS>
class TCMalloc_PageMap1 {
private:
	static const int LENGTH = 1 << BITS;
	void** array_;
public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap1(void* (*allocator)(size_t)) {
		//array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
		size_t size = sizeof(void*) << BITS;
		size_t  alignSize = SizeClass::_RoundUp(size,1 << PAGE_SHIFT);

		array_ = SystemAlloc(alignSize >> PAGE_SHIFT);
		memset(array_, 0, sizeof(void*) << BITS);
	}
	// Return the current value for KEY. Returns NULL if not yet set,
	// or if k is out of range.
	void* get(Number k) const {
		if ((k >> BITS) > 0) {
			return NULL;
		}
		return array_[k];
	}
	// REQUIRES "k" is in range "[0,2^BITS-1]".
	// REQUIRES "k" has been ensured before.
	//
	// Sets the value 'v' for key 'k'.
	void set(Number k, void* v) {
		array_[k] = v;
	}
};
// Two-level radix tree
template <int BITS>
class TCMalloc_PageMap2 {
private:
	// Put 32 entries in the root and (2^BITS)/32 entries in each leaf.
	static const int ROOT_BITS = 5;
	static const int ROOT_LENGTH = 1 << ROOT_BITS;
	static const int LEAF_BITS = BITS - ROOT_BITS;
	static const int LEAF_LENGTH = 1 << LEAF_BITS;
	
		// Leaf node
		struct Leaf {
		void* values[LEAF_LENGTH];
	};
	Leaf* root_[ROOT_LENGTH];             // Pointers to 32 child nodes
	void* (*allocator_)(size_t);          // Memory allocator
public:
	typedef uintptr_t Number;
	//explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) 
	explicit TCMalloc_PageMap2() {
		//allocator_ = allocator;
		memset(root_, 0, sizeof(root_));
	}
	void* get(Number k) const {
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 || root_[i1] == NULL) {
			return NULL;
		}
		return root_[i1]->values[i2];
	}
	void set(Number k, void* v) {
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		ASSERT(i1 < ROOT_LENGTH);
		root_[i1]->values[i2] = v;
	}
	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> LEAF_BITS;
			// Check for overflow
			if (i1 >= ROOT_LENGTH)
				return false;
			// Make 2nd level node if necessary
			if (root_[i1] == NULL) {
				//Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
				//if (leaf == NULL) return false;
				static ObjectPool<Leaf> leafpool;
				//Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)
				Leaf* leaf = (Leaf*)leafpool.New();
				memset(leaf, 0, sizeof(*leaf));
				root_[i1] = leaf;
			}
			// Advance key past whatever is covered by this leaf node
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}
	void PreallocateMoreMemory() {
		// Allocate enough to keep track of all possible pages
		
			Ensure(0, 1 << BITS);
	}
};
// Three-level radix tree
template <int BITS>
class TCMalloc_PageMap3 {
private:
	// How many bits should we consume at each interior level
	static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up
	static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;
	// How many bits should we consume at leaf level
	static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS;
	static const int LEAF_LENGTH = 1 << LEAF_BITS;
	// Interior node
	struct Node {
		Node* ptrs[INTERIOR_LENGTH];
	};
	// Leaf node
	struct Leaf {
		void* values[LEAF_LENGTH];
	};
	Node* root_;                          // Root of radix tree
	void* (*allocator_)(size_t);          // Memory allocator
	Node* NewNode() {
		Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
		if (result != NULL) {
			memset(result, 0, sizeof(*result));
		}
		return result;
	}
public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {
		allocator_ = allocator;
		root_ = NewNode();
	}
	void* get(Number k) const {
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 ||
			root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) {
			return NULL;
		}
		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
	}
	void set(Number k, void* v) {
		ASSERT(k >> BITS == 0);
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);
		reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
	}
	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
			const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
			// Check for overflow
			if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
				return false;
			// Make 2nd level node if necessary
			if (root_->ptrs[i1] == NULL) {
				Node* n = NewNode();
				if (n == NULL) return false;
				root_->ptrs[i1] = n;
			}
			// Make leaf node if necessary
			if (root_->ptrs[i1]->ptrs[i2] == NULL) {
				Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)
					(sizeof(Leaf)));
				if (leaf == NULL) return false;
				memset(leaf, 0, sizeof(*leaf));
				root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
			}
			// Advance key past whatever is covered by this leaf node
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}
	void PreallocateMoreMemory() {
	}
};

PageCache.h

#pragma once
#include "Common.h"
#include "ObjectPool.h"
template <int BITS>
class TCMalloc_PageMap1 {
private:
	static const int LENGTH = 1 << BITS;
	void** array_;
public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap1(void* (*allocator)(size_t)) {
		//array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
		size_t size = sizeof(void*) << BITS;
		size_t  alignSize = SizeClass::_RoundUp(size,1 << PAGE_SHIFT);

		array_ = SystemAlloc(alignSize >> PAGE_SHIFT);
		memset(array_, 0, sizeof(void*) << BITS);
	}
	// Return the current value for KEY. Returns NULL if not yet set,
	// or if k is out of range.
	void* get(Number k) const {
		if ((k >> BITS) > 0) {
			return NULL;
		}
		return array_[k];
	}
	// REQUIRES "k" is in range "[0,2^BITS-1]".
	// REQUIRES "k" has been ensured before.
	//
	// Sets the value 'v' for key 'k'.
	void set(Number k, void* v) {
		array_[k] = v;
	}
};
// Two-level radix tree
template <int BITS>
class TCMalloc_PageMap2 {
private:
	// Put 32 entries in the root and (2^BITS)/32 entries in each leaf.
	static const int ROOT_BITS = 5;
	static const int ROOT_LENGTH = 1 << ROOT_BITS;
	static const int LEAF_BITS = BITS - ROOT_BITS;
	static const int LEAF_LENGTH = 1 << LEAF_BITS;
	比特就業(yè)課
		// Leaf node
		struct Leaf {
		void* values[LEAF_LENGTH];
	};
	Leaf* root_[ROOT_LENGTH];             // Pointers to 32 child nodes
	void* (*allocator_)(size_t);          // Memory allocator
public:
	typedef uintptr_t Number;
	//explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) 
	explicit TCMalloc_PageMap2() {
		//allocator_ = allocator;
		memset(root_, 0, sizeof(root_));
	}
	void* get(Number k) const {
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 || root_[i1] == NULL) {
			return NULL;
		}
		return root_[i1]->values[i2];
	}
	void set(Number k, void* v) {
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		ASSERT(i1 < ROOT_LENGTH);
		root_[i1]->values[i2] = v;
	}
	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> LEAF_BITS;
			// Check for overflow
			if (i1 >= ROOT_LENGTH)
				return false;
			// Make 2nd level node if necessary
			if (root_[i1] == NULL) {
				//Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
				//if (leaf == NULL) return false;
				static ObjectPool<Leaf> leafpool;
				//Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)
				Leaf* leaf = (Leaf*)leafpool.New();
				memset(leaf, 0, sizeof(*leaf));
				root_[i1] = leaf;
			}
			// Advance key past whatever is covered by this leaf node
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}
	void PreallocateMoreMemory() {
		// Allocate enough to keep track of all possible pages
		
			Ensure(0, 1 << BITS);
	}
};
// Three-level radix tree
template <int BITS>
class TCMalloc_PageMap3 {
private:
	// How many bits should we consume at each interior level
	static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up
	static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;
	// How many bits should we consume at leaf level
	static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS;
	static const int LEAF_LENGTH = 1 << LEAF_BITS;
	// Interior node
	struct Node {
		Node* ptrs[INTERIOR_LENGTH];
	};
	// Leaf node
	struct Leaf {
		void* values[LEAF_LENGTH];
	};
	Node* root_;                          // Root of radix tree
	void* (*allocator_)(size_t);          // Memory allocator
	Node* NewNode() {
		Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
		if (result != NULL) {
			memset(result, 0, sizeof(*result));
		}
		return result;
	}
public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {
		allocator_ = allocator;
		root_ = NewNode();
	}
	void* get(Number k) const {
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 ||
			root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) {
			return NULL;
		}
		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
	}
	void set(Number k, void* v) {
		ASSERT(k >> BITS == 0);
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);
		reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
	}
	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
			const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
			// Check for overflow
			if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
				return false;
			// Make 2nd level node if necessary
			if (root_->ptrs[i1] == NULL) {
				Node* n = NewNode();
				if (n == NULL) return false;
				root_->ptrs[i1] = n;
			}
			// Make leaf node if necessary
			if (root_->ptrs[i1]->ptrs[i2] == NULL) {
				Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)
					(sizeof(Leaf)));
				if (leaf == NULL) return false;
				memset(leaf, 0, sizeof(*leaf));
				root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
			}
			// Advance key past whatever is covered by this leaf node
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}
	void PreallocateMoreMemory() {
	}
};

PageCache.cpp

#include "PageCache.h"
PageCache PageCache::_sInst;

Span* PageCache::NewSpan(size_t k)//獲取k頁(yè)的span
{
	//eg:只有一個(gè)128頁(yè)的，需要兩頁(yè)的-》128分為2span和126span，2返回給central cache,126掛道對(duì)應(yīng)的桶上
	//如果central cache中的span usecount=0,說(shuō)明切分給thread cache小塊內(nèi)存都還回來(lái)了，
	//則central cache把span還給page cache,page cache通過頁(yè)號(hào)查看相鄰頁(yè)是否空閑，是就合并出更大的page,解決內(nèi)存碎片問題
	assert(k > 0 && k < NPAGES);
	
	if (k > NPAGES - 1)
	{
		void* ptr = SystemAlloc(k);//大于最大頁(yè)數(shù)直接找堆要
		//Span* span = new Span;
		Span* span = spanPool.New();
		span->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
		span->n = k;
		//_idSpanMap[span->_pageId] = span;
		_idSpanMap.set(span->_pageId,span);
		return span;
	}
	
	if (!_spanList[k].Empty())//第k個(gè)桶里面有沒有span
	{
		
		Span* KSpan = _spanList[k].PopFront();
		
		//建立id和span的映射關(guān)系方便centralcache回收小塊內(nèi)存時(shí)查找對(duì)應(yīng)的span
		for (PAGE_ID i = 0; i < KSpan->n; i++)
		{
			//_idSpanMap[KSpan->_pageId + i] = KSpan;
			_idSpanMap.set(KSpan->_pageId + i, KSpan);
		}
		
		return KSpan;
	}

	//第k個(gè)桶里是空的,檢測(cè)后面的桶里有沒有span,如果有進(jìn)行切分
	//切分成一個(gè)k頁(yè)的span和一個(gè) n-k 頁(yè)的span
	//k頁(yè)的span返回給central cache,n-k 頁(yè)的span掛到第 n-k 號(hào)桶中去
	for (size_t i = k ; i < NPAGES; i++)
	{		
		if (!_spanList[i].Empty())
		{
			Span* nSpan = _spanList[i].PopFront();
			//Span* KSpan = new Span;
			Span* KSpan = spanPool.New();
			

			//在nSpan的頭部切下K頁(yè)
			//k頁(yè)span返回，nSpan再掛到對(duì)應(yīng)映射
			KSpan->_pageId = nSpan->_pageId;
			KSpan->n = k;//kSpan頁(yè)數(shù)變?yōu)閗
			nSpan->_pageId += k;//nSpan 頁(yè)號(hào)變?yōu)?+= k
			nSpan->n -= k;
			
			_spanList[nSpan->n].PushFront(nSpan);//把剩余的頁(yè)掛到對(duì)應(yīng)的位置

			
			//存儲(chǔ)nSpan的首尾頁(yè)號(hào)跟span映射,方便page cache回收內(nèi)存時(shí)進(jìn)行合并查找
			//_idSpanMap[nSpan->_pageId] = nSpan;
			//_idSpanMap[nSpan->_pageId + nSpan->n - 1] = nSpan
			_idSpanMap.set(nSpan->_pageId, nSpan);
			_idSpanMap.set(nSpan->_pageId + nSpan->n - 1, nSpan);
			

			//建立id和span的映射，方便central cache回收查找對(duì)應(yīng)的span
			for (PAGE_ID i = 0; i < KSpan->n; i++)
			{
				//_idSpanMap[KSpan->_pageId + i] = KSpan;
				_idSpanMap.set(KSpan->_pageId + i, KSpan);
			}
			
			
			return KSpan;
		}
	}

	//沒有大頁(yè)span
	//找堆要128頁(yè)的span
	Span* bigSpan = spanPool.New();
	//Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->n = NPAGES - 1;
	_spanList[bigSpan->n].PushFront(bigSpan);
	return NewSpan(k);

}

Span* PageCache::MapObjectToSpan(void* obj)
{
	
	PAGE_ID id = ((PAGE_ID)obj >> PAGE_SHIFT);//找出頁(yè)號(hào)


	
	auto ret = (Span*)_idSpanMap.get(id);
	assert(ret != nullptr);
	return ret;
}
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	//對(duì)span前后的頁(yè)進(jìn)行合并，解決內(nèi)存碎片問題

	if (span->n > NPAGES - 1)
	{
		//大于128頁(yè)的直接還給堆
		void* ptr = (void*)(span->_pageId << PAGE_SHIFT);
		SystemFree(ptr);
		//delete span;
		spanPool.Delete(span);
		return;
	}
	//向前合并
	while (1)
	{
		PAGE_ID prevId = span->_pageId - 1;
	
		auto ret = (Span*)_idSpanMap.get(prevId);
		if (ret == nullptr)
		{
			break;
		}
		
		Span* prevspan = ret;
		if (prevspan->_isUse == true)
		{//前面相鄰頁(yè)的span在使用
			break;
		}
		if (prevspan->n + span->n > NPAGES - 1)
		{
			//合并數(shù)超過128，沒辦法管理
			break;
		}
		//合并
		span->_pageId = prevspan->_pageId;
		span->n += prevspan->n;
		_spanList[prevspan->n].Erase(prevspan);
		//delete prevspan;
		
		spanPool.Delete(prevspan);
	}

	//向后合并
	while (1)
	{
		PAGE_ID nextId = span->_pageId + span->n;
		
		auto ret = (Span*)_idSpanMap.get(nextId);
		if (ret == nullptr)
		{
			break;
		}
		Span* nextspan = ret;
		if (nextspan->_isUse == true)
		{
			break;
		}
		if (nextspan->n + span->n > NPAGES - 1)
		{
			break;
		}
		span->n += nextspan->n;
		_spanList[nextspan->n].Erase(nextspan);
		//delete(nextspan);
		spanPool.Delete(nextspan);

	}
	//前后都合并過了

	_spanList[span->n].PushFront(span);
	span->_isUse = false;

	//方便其他把此span合并
	//_idSpanMap[span->_pageId] = span;
	//_idSpanMap[span->_pageId + span->n - 1] = span;

	_idSpanMap.set(span->_pageId, span);
	_idSpanMap.set(span->_pageId + span->n - 1, span);

}
//只有Span* NewSpan(size_t k)   void ReleaseSpanToPageCache(Span* span)
//這兩個(gè)函數(shù)中去建立id和span的映射(回去寫)
//基數(shù)樹，寫之前會(huì)提前開好空間，寫數(shù)據(jù)過程中，不會(huì)動(dòng)數(shù)據(jù)結(jié)構(gòu)
//讀寫是分離的。線程1對(duì)一個(gè)位置讀寫的時(shí)候，線程2不可以對(duì)這個(gè)位置讀寫

轉(zhuǎn)載至：https://zhuanlan.zhihu.com/p/582514123文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-731693.html

到了這里，關(guān)于實(shí)現(xiàn)高并發(fā)內(nèi)存池（C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！