高并发内存池_CentralCache（中心缓存）和PageCache（页缓存）申请内存的设计

三、CentralCache（中心缓存）_内存设计

（一）Span的创建

// 页编号类型，32位下是4byte类型，64位下是8byte类型
// 
#ifdef _WIN64 
    typedef unsigned long long PageID; 
#else _WIN32 
    typedef size_t PageID;
#endif

// Span
struct Span
{
    // 结合我们框架设计时的分析设计
    // 标识和管理以页为单位的大块内存（即 Span）的具体位置和大小
    // 页号和第几页
    PageID _pageId = 0;	// 大块内存的起始页号，用于标识和管理内存块的具体位置。
    size_t _n = 0;	// 管理的页数，表示Span对象占用了多少页内存。
    
    // Span可以组成双向链表
    Span* _prev = nullptr;
    Span* _next = nullptr;
    
    // Span下管理内存块的自由链表
    void* _list = nullptr;

    /* 这列三个变量不理解也没关系，后面还会再解释
     * 但是可以结合前面介绍的框架设计再理解       */

    // 当线程申请内存时，PageCache分配内存给CentralCache
    // 在给CentralCache分配Span时，判断此时的Span是不属于PageCache的
    // 而在线程释放内存时，回收到PageCache中的Span可以与未使用的、相邻的Span合并（注意其他因素）
    bool _isUse = true;
    
    // 当线程申请内存时，ThreadCache从CentralCache中申请内存块，对应的Span中的内存块使用数量++
    // 当线程释放内存时，CentralCache回收内存块的使用数量--，直到回到0.
    // 在CentralCache释放内存给PageCache时，可以得到此时的Span为空闲Span，可以回收进PageCache
    size_t _usecount = 0;
    
    // 当线程申请内存时，PageCache分配内存给CentralCache，
    // CentralCache需要对管理的内存进行分割挂在自由链表下
    // 如何判断分割对象的大小？
    size_t _objSize = 0;
};

PageID _pageId 和 size_t _n 的作用？

Span 对象通过 _pageId 和 _n 紧密地与物理内存页关联起来。当需要分配内存时，TCMalloc 会根据请求的大小从合适的 Span 中切分出足够的内存块。这些内存块随后被添加到对应的中心缓存（Central Cache）或线程缓存（Thread Cache）中，以供后续的内存分配请求使用。

关于**_pageId **的类型，

在32位平台下，进程地址空间的大小为 2³² ，如果每页固定为8KB（举例），那么 2³² / 2¹³ = 2¹⁹，那么32位平台下，进程地址空间可分为2¹⁹个页，页号和每个街道上的房号一样，都只是一个编号，只是这里用页号更方便找到对应的物理内存地址。

同理，在64位平台下，进程地址空间的大小为 2⁶⁴ ，如果每页固定为8KB（举例），那么 2⁶⁴ / 2¹³ = 2⁵¹，那么32位平台下，进程地址空间可分为2⁵¹个页。

因此要考虑一下不同平台下，**_pageId **的大小不同，使用条件编译重命名他们的类型。

需要注意的是，在32位下，_WIN32有定义，_WIN64没有定义；而在64位下，_WIN32和_WIN64都有定义。因此在条件编译时需要注意64位的环境下优先定义_WIN64。

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

**_pageId 是 Span 所管理的内存页的起始标识符（或索引），用于唯一标识 Span 所管理的内存页的起始位置。**在内存管理系统中，内存通常被划分为固定大小的页（例如4KB、8KB等），而 _pageId 就是这些页中的一个唯一编号或索引（需要通过某种映射机制（如页表）来找到实际的物理地址）。

**_n 是 Span 所管理的页数，一个Span中有多少个页的内存。**由于内存被划分为固定大小的页，因此 _n 实际上表示了 Span 覆盖了多少个这样的页。

**计算 Span 的总大小（以字节为单位）= 每页的大小与 _n 相乘。**如果每页是 4KB，并且 _n 是 10，那么 Span 的总大小就是 40KB。

申请回收内存时会使用的变量 _usecount 和 _isuse。

_usecount 是为了判断Span中的内存是否都回来了，Span中的内存都被回收到CentralCache中后，可以回收进PageCache。

具体的使用在后续的CentralCache释放内存中再提及，这里仅做了解。

（二）SpanList的创建

创建一条SpanList，首先我们要了解其结构和需求，是一条可供插入和删除的自由链表。

同时我们要了解到在访问每一个哈希桶（也就是每一条SpanList）时，都要访问桶锁。

// 带头双向循环链表
class SpanList
{
private:
	Span* _head;
public:
    std::mutex _mtx; // 每个桶被访问时要通过锁  注意头文件使用<mutex>

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;

		pos->_prev = newSpan;
		newSpan->_next = pos;
	}

	// 删除
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

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

		prev->_next = next;
		next->_prev = prev;
	}
};

（三）CentralCache的核心实现

一个线程通过TLS获得它独享到的 ThreadCache ，有内存可以直接使用，没有内存就要找CentralCache 申请内存（FetchFromCentralCache())。ThreadCache通过FetchFromCentralCache()函数如何获取CentralCache的对象呢，一般情况下是使用全局变量，但是更好的方式是期望全局只有一个CentralCache和PageCache。

也就是说最好的方式是CentralCache和PageCache在整个进程中只有一个实例。对于这种能创建一个对象的类，我们可以将其设置为 单例模式。

1.什么是单例模式？

单例模式（Singleton Pattern）是一种常用的软件设计模式，其目的是确保一个类仅有一个实例，并提供一个全局访问点来获取该实例。这个模式在多种场景中都非常有用，特别是在需要控制资源访问，或者管理全局状态信息时。单例模式又分为懒汉模式和饿汉模式，其中懒汉模式较为复杂。

在C++中，实现单例模式通常涉及以下几个关键点：

私有构造函数：将类的构造函数声明为私有，以防止外部代码通过new关键字创建类的实例。
私有静态实例变量：在类内部定义一个静态变量来保存类的唯一实例。这个变量是私有的，以防止外部直接访问。在类外部初始化静态成员变量。
公有静态访问方法：提供一个公有的静态方法，用于返回类的唯一实例。如果实例不存在，则创建它；如果实例已存在，则直接返回该实例。这个方法通常被命名为getInstance() 或类似的名称。
确保线程安全（可选）：在多线程环境中，需要确保getInstance()方法是线程安全的，以防止多个线程同时创建实例。这可以通过加锁来实现，但加锁会引入性能开销，因此需要根据实际情况权衡。

“懒汉式”单例–全局的单例实例在第一次被使用时构建

下面是一个简单的C++单例模式实现示例：

/* 懒汉模式 */
#include <iostream>  
#include <mutex>  
  
class Singleton {  
private:  
    static Singleton* instance; // 静态指针指向唯一实例  
    static std::mutex mtx; // 用于确保线程安全的互斥锁  
  
    Singleton() {} // 私有构造函数，防止外部创建实例  
  
    // 禁止拷贝构造函数和赋值运算符  
    Singleton(const Singleton&) = delete;  
    Singleton& operator=(const Singleton&) = delete;  
  
public:  
    // 公有静态方法，用于获取唯一实例  
    static Singleton* getInstance() {  
        std::lock_guard<std::mutex> lock(mtx); // 锁定互斥锁 
        
        if (!instance) { // 如果实例不存在，则创建实例  
            instance = new Singleton();  
        }        
        return instance; // 返回实例指针 
    }  
  
    // 示例方法，展示单例可以做什么  
    void doSomething() {  
        std::cout << "Doing something..." << std::endl;  
    }  
};  
  
// 初始化静态成员变量  
Singleton* Singleton::instance = nullptr;  
std::mutex Singleton::mtx;  
  
int main() {  
    Singleton* s1 = Singleton::getInstance();  
    Singleton* s2 = Singleton::getInstance();  
  
    // s1 和 s2 指向同一个实例  
    if (s1 == s2) {  
        std::cout << "s1 and s2 are the same instance." << std::endl;  
    }  
  
    s1->doSomething();  
    s2->doSomething(); // 通过另一个指针调用，但仍然是同一个实例  
  
    return 0;  
}

请注意，上述示例中的单例**（懒汉式单例）**实现是线程安全的，因为它在 getInstance() 方法中使用了 std::mutex 来确保在多线程环境下只有一个线程能够创建实例。然而，对于某些应用来说，如果确定不会有多个线程同时尝试创建实例，那么可以省略线程安全的代码以提高性能。

C++11及以后的版本提供了更好的线程安全特性，包括局部静态变量的线程安全初始化，这可以用来实现一种更简洁的线程安全的懒汉式单例，而无需显式加锁。

“饿汉式”单例–全局的单例实例在类装载时构建

另外，还有一种常见的单例模式变体是“饿汉式”单例，它在程序启动时立即创建实例（饿汉模式在main函数之前对象已经初始化好了），而不是在第一次被请求时才创建。这种方法不需要考虑线程安全问题，但会稍微增加程序的启动时间。(在一般情况下饿汉已经够用了! )

// “饿汉式”单例
class Singleton {  
private:  
    static Singleton instance; // 静态实例，在程序启动时立即创建  
  
    Singleton() {} // 私有构造函数，防止外部创建实例  
  
    // 禁止拷贝构造函数 和 赋值运算符  
    Singleton(const Singleton&) = delete;  
    Singleton& operator=(const Singleton&) = delete;  
  
public:  
    static Singleton& getInstance() {  
        return instance; // 直接返回静态实例的引用  
    }  
  
    // 示例方法  
    void doSomething() {  
        // ...  
    }  
};  
  
// 在类外定义静态实例  
Singleton Singleton::instance;  
  
// 使用示例  
int main() {  
    Singleton& s1 = Singleton::getInstance();  
    Singleton& s2 = Singleton::getInstance();  
    // s1 和 s2 引用的是同一个实例  
}

2.创建CentralCache的单例模式（饿汉模式）

这里我们使用饿汉模式即可。

/* CentralCache的单例模式（饿汉模式） */
/* CentralCache.h */

class CentralCache
{
private:
	// 哈希桶结构
	SpanList _spanLists[NFREELISTS];
	// 从现在开始访问CentralCache的哈希桶，需要开始加锁进入

private:
	// 私有静态成员变量
	static CentralCache _inst;

	// 私有构造函数
	CentralCache(){}

	// 禁止拷贝构造和赋值运算符
	CentralCache(const CentralCache&) = delete;
	CentralCache& operator=(const CentralCache&) = delete;

public:
	// 公有静态访问方法
	static CentralCache& GetInstance()
	{
		return _inst;
	}

	// ThreadCache从CentralCache中获取内存块
	size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t  size);

	// 获取一个非空Span
	Span* GetOneSpan(SpanList& list, size_t size);
};


/* 在CentralCache.cpp */
// 初始化静态成员变量  
/* 在.h文件中直接初始化静态成员变量（如 CentralCache CentralCache::_instance;），
 * 并且这个头文件被多个源文件（.cpp）包含，那么每个包含这个头文件的源文件都会尝试定义并初始化这个静态变量
 * 这会导致链接器错误，因为链接器会发现多个相同的静态变量定义。
 */
CentralCache CentralCache::_inst;

3.运用慢开始反馈调节算法

创建好CentralCache的基本结构后，我们就需要将ThreadCache与 CentralCache链接起来了。

当ThreadCache需要从CentralCache中申请内存FetchFromCentralCache()时，CentralCache应该给出多少内存呢？

如果ThreadCache每次申请一个CentralCache就给一个，是否会导致线程在申请同一个桶的内存时竞争激烈，造成效率上的损失。但如果一次给太多，ThreadCache用不完也会产生资源浪费。怎么去控制这个适中的量？

因此这里可以使用 慢开始反馈调节算法 。当ThreadCache向CentralCache申请内存时，如果申请的是较小的对象，那么可以多给一点，但如果申请的是较大的对象，就可以少给一点。

通过下面这个函数，我们就可以根据所需申请的对象的大小计算出具体给出的对象个数，并且可以将给出的对象个数控制到2~512个之间。也就是说，当ThreadCache要申请的对象小时，最多给出512个对象；当ThreadCache要申请的对象时大，一次性给出2个对象。

/* ThreadCache.cpp */
// 从Cental Cache中申请缓存
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
    // 慢开始反馈调节算法
    size_t batchNum = SizeClass::NumMoveSize(size); // 一次要申请的数量

    return nullptr;
}

/* CommonPool.h */
/* 放置在class SizeClass 类中 */
// 慢开始反馈算法
// 一次从中心缓存获取多少个
static size_t NumMoveSize(size_t size)
{
    assert(size >0);
    
	// 申请数量的范围是[2, 512]，一次批量移动多少个对象的(慢启动)上限值 
	// 小对象一次批量上限高 
	// 小对象一次批量上限低 
	size_t num = MAX_BYTES / size; 
	if (num < 2) 
		num = 2; 
	if (num > 512) 
		num = 512; 
	return num;
}

慢开始反馈体验在哪里呢？

如果一个线程只需要申请1份，而给512份，剩下的511都浪费了，所以还要再控制一下申请的数量。怎么控制呢？

我们通过在FreeList结构中增加一个叫做_MaxSize的成员变量，该变量的初始值设置为1，并且提供一个公有成员函数用于获取这个变量。也就是说，现在ThreadCache中的每个自由链表都会有一个自己的_MaxSize。设置一个变量MaxSize()，取MaxSize()与NumMoveSize()中的最小值。

如果对象所申请的内存较小，batchNum就会越大，因为MaxSize()不断增长的，NumMoveSize()是不变的512；

如果对象所申请的内存较大，batchNum就会越小，因为MaxSize()增长到不等于batchNum时对batchNum无影响，NumMoveSize()是不变的2.

//创建哈希桶中的自由链表
class FreeList
{
private:
	void* _freeList = nullptr;
	size_t _MaxSize = 1;	// 控制

public:
	// 管理链表
	// 头删
	void* Pop()
	{
		void* obj = _freeList;
		_freeList = NextObj(obj);
		return obj;
	}

	// 头插
	void Push(void* obj)
	{
		NextObj(obj) = _freeList;
		_freeList = obj;
	}

	// 查看自由链表是否为空
    bool Empty()
    {
    	if (_freeList == nullptr)
    		return true;
    	return false;
    }

	// 判断链表的长度
	// 遍历查找 or 申请内存时++
	size_t& MaxSize()
	{
		return _MaxSize;
	}
};

/* ThreadCache.cpp */

// 从Cental Cache中申请缓存
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
	// 慢开始反馈算法计算要申请几份对象的内存
	/* 1、最开始不会一次向 central cache 一次批量要太多，因为要太多了可能用不完
	 * 2、如果你不要这个 size 大小内存需求，那么batchNum就会不断增长，直到上限
	 * 3、size越大，一次向 central cache 要的batchNum就越小		(MaxSize，2 )
	 * 4、size越小，一次向 central cache 要的batchNum就越大		(MaxSize,512)
     */
	size_t batchNum = std::min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));

    // 慢增长，直到申请内存的上限
	if (_freeLists[index].MaxSize() == batchNum)
	{
		_freeLists[index].MaxSize() += 1;
	}
}

从中心缓存中获取一定数量的对象给ThreadCache

每次ThreadCache向CentralCache申请对象时，先通过慢开始反馈调节算法计算出本次应该申请的对象的个数。

这里我们需要明白一件事情，通过计算出来的batchNum是我们计算出来的要申请对象的个数，也就相当于我们向CentralCache建议的给我们batchNum个对象。

但实际上CentralCache给我们的对象要看他span下有多少，可能只有一个，可能足够给我们batchNum个，也可能不足batchNum个，所以具体对象个数需要再通过FetchRangeObj()查看真实情况下CentralCache对应桶中span的自由链表上有几个内存对象（actualNum）。**如果只有一个就直接返回；如果申请到多个对象，除了将第一个对象返回给线程使用以外，还需要将剩下的对象挂到ThreadCache对应的哈希桶中。**根据需求，我们需要向封装的自由链表继续添加一个函数PushRange将多个内存对象链接到对应的桶中。

/* ThreadCache.cpp */
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
    // 从CentralCache中申请内存
    void* start = nullptr;
    void* end = nullptr;
    
    // 实际能从CentralCache中获取到的对象个数
    size_t actualNum = CentralCache::GetInstance().FetchRangObj(start, end, batchNum, size);
    
    // 将从CentralCache中获取到的对象数给ThreadCache
    assert(actualNum >= 1);
    
    if (actualNum == 1)
    {
    	assert(start == end);
    	return start;
    }
    else
    {
    	// 将第一个对象返回以外，还需要将剩下的对象挂到threadcache对应的哈希桶中
    	_freeLists[index].PushRange(NextObj(start), end, actualNum-1);
    	return start;
    }
}

如图，我们从CentralCache中申请到了3个对象，此时我们要将start所指的对象供申请内存的线程使用，后面多余的对象则要插入进对应的哈希桶的自由链表中。

完善PushRange()；

// 在FreeList中
void PushRange(void* start, void* end, size_t n)
{
	NextObj(end) = _freeList;
	_freeList = start;
}

// 没有空闲的内存块，需要向CentralCache申请内存
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
	// 要在CentralCache对应的哈希桶中找到非空Span
	// 在访问CentralCache中记得要使用桶锁
	
	// 1.首先，ThreadCache需要向CentralCache申请多少个size大小的内存？
	// 一次一个可能导致竞争激烈，效率不高；以此过多，可能造成浪费
	// 因此，使用慢开始反馈调节法，通过对象大小申请2~512个数量，内存小的多申请一些，内存大的少申请一些。
	// 一次批量的数量
	size_t batchNum = min(_freeLists[index].MaxSize(),  ClassSize::NumMoveSize(size));

	// 慢增长，直到申请内存的上限
	if (_freeLists[index].MaxSize() == batchNum)
	{
		_freeLists[index].MaxSize() += 1;
	}

	// 2.进入CentralCache中在对应的哈希桶中寻找非空Span
	// 获取非空Span中的空闲内存块，申请到的内存块数量可能是Span中剩余的所有内存块或者是actualNum个
	// 这时要从CentralCache中获取的内存对象可能不止一个
	void* start = nullptr;
	void* end = nullptr;

	// 从CentralCache中获取一定范围的对象,这里与CentralCache链接起来
	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,actualNum-1);
		return start;
	}
}

4.怎样设置FetchRangeObj？

从中心缓存获取一定数量的对象给ThreadCache。

我们首先要考虑中心缓存的内存是否足够提供内存对象给ThreadCache。

如果CentralCache对应的哈希桶中没有非空的Span，如何提供内存对象给ThreadCache？

这时候CentralCache就需要向PageCache申请一个新的Span放置在对应的哈希桶中，如何获取一个非空Span？

可以通过 GetOneSpan 来申请一个非空的Span放置在对应的哈希桶中。

/* CentralCache.cpp */

// 从中心缓存获取一定数量的对象给ThreadCache
	/* 将这个span中的内存切割下来，挂在thread cache下，
	start: 从central cache 中取下来内存的头结点
	end:   从central cache 中取下来内存的尾结点
	batchNum: 申请的一批内存数量
	size: 要申请的内存大小(alignSize, 对齐后的内存)
	*/
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)
{
	
    // 访问哪个哈希桶？
    size_t index = SizeClass::Index(size);	

	// 从现在开始访问CentralCache的哈希桶，需要开始加锁进入
	_spanLists[index]._mtx.lock();

    // 找到对应哈希桶中的 非空Span给ThreadCache提供内存
    // 使用GetOneSpan获取一个非空Span
    Span* span = GetOneSpan(_spanLists[index], size);
	assert(span);
	assert(span->_list);
    
	start = span->_list;
	end = start;

    // 设置一个变量n，和一个实际可申请对象数量的变量actualNum，以及别忘了batchNum
	size_t n = 0, actualNum = 1; 
	while (n < batchNum - 1 && NextObj(end) != nullptr)
	{
		end = NextObj(end);
		++n;
		++actualNum;
	}
    
	// 把切割掉内存后的内存对象连接上,被切割下的内存尾端指向nullptr
	span->_list = NextObj(end);
	NextObj(end) = nullptr;

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

（三）从CentralCache中申请内存

CentralCache映射的Spanlist中没有非空Span时，则需要向PageCache申请一个新的Span对象，拿到Span以后将Span管理的内存按对应的大小切好作为自由链表链接到一起。然后从Span中取对象给ThreadCache。

获得非空的Span(一)-遍历CentralCache

首先是查看。

首先要从CentralCache对应的哈希桶中是否有非空的span，遍历按链表找出，因为是双向循环链表，所以我们可以使用迭代器（但是我们对迭代器的需求不频繁，所以使用一个不封装的迭代器即可）。
按照步骤1优先，可以优先分配由ThreadCache释放回来的Span，有效利用资源。
如果对应的哈希桶中没有非空的Span，那么就要我们先创建新的非空Span再利用。
从PageCache中获取一个非空Span，可以根据Span的信息，获取页数和几页，从而获取Span的起始地址和内存大小。
根据这个Span的起始地址进行对应哈希桶存储内存对象大小切割，切割好的对象按照自由链表方式链接起来，由上一内存块的前几字节存储下一内存块的地址。
无论是遍历找到的非空Span还是创建的新的Span，最后我们都要返回它们，才能通过调用函数获得。

    // SpanList
    // 迭代器
    Span* Begin()
    {
    	return _head->_next;
    }
    
    Span* End()
    {
    	return _head;
    }

/* CentralCache.cpp */
Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{
	// 1. central cache 直接找对应哈希桶中的非空Span
    // 返回非空Span，分配内存给ThreadCache
	Span* it = list.Begin();  // 在SpanList中定义Begin()和End()
	while (it != list.End())
	{
		if (it->_list != nullptr)
		{
			return it;
		}
		else
			it = it->_next;
	}

    // 2. 向page cache 申请到span
    // 会在后续部分讲解，步骤就如前面介绍的相同
}

三、PageCache（页缓存）_内存设计

功能：作为内存池的最上层缓存，以页为单位存储和分配内存。当CentralCache内存不足时，PageCache会向系统申请新的内存页，并切割成小块内存分配给CentralCache。当一个Span的几个跨度页的对象都回收以后，PageCache会回收CentralCache满足条件的Span对象，并且合并相邻的页组成更大的页，缓解内存碎片的问题。

结构：通常也采用哈希桶结构，但映射规则与ThreadCache和CentralCache不同，主要按页号进行映射。

内存管理：PageCache负责大块内存的分配和回收，以及与系统的内存交互。同时，也会合并相邻的空闲页，以减少内存碎片。

1.PageCache的结构

与CentralCache相同，进程中只有一个PageCache的实例。

// page cache 管理span list哈希表大小
static const size_t NPAGES = 129;

class PageCache {
public:
    // 加锁 注意锁的存在
    std::mutex _pageMtx;
public:
	// 公有静态访问方法
	static PageCache& GetInstance()
	{
		return _instance;
	}

private:
	// 私有的静态实例成员
	static PageCache _instance;

	// 私有的构造函数
	PageCache(){}
	
	// 禁止拷贝构造函数和运算符赋值
	PageCache(const PageCache&) = delete;
	PageCache& operator=(const PageCache&) = delete;

private:
	// 与ThreadCache和CentralCache不同，PageCache的哈希桶是以页号为单位，共128号桶
	// 这里设置129号桶，不使用0号桶，1号桶就对应1page，2号桶就对应2page，依次类推
	SpanList spanLists[NPAGES];
};

/* 放在cpp */
// 初始化静态成员变量  
PageCache PageCache::_instance;

2.CentralCache从PageCache中申请内存

也就是从PageCache中获取一个NewSpan

进入PageCache也存在竞争关系，记得加锁。

设计的哈希桶为129个，其中下标位0的哈希桶不使用，目的是让每个哈希桶中管理的Span页数与哈希桶下标对应。

从PageCache获取一个Span：

对应的哈希桶中有Span。比如要2页的Span，直接在下标为2的哈希桶中找到，可以使用；
对应的哈希桶中没有Span，向后查找，从后续的同种查找合适的可切分的Span。比如要35页的Span，但是下标为35的哈希桶中没有，一直找到102的哈希桶中才找到Span，这时候将该Span划分为35页Span和67页Span；
一直向后查找，都没有找到合适的可切分的Span。比如要98页Span，但是直到128哈希桶都没有找到，这时候只能向系统申请128页的内存，再切分。

条件1,2都不满足时，此时的PageCache中有许多零碎的内存块，但是这些内存块合并在一起可以满足我们申请的内存大小或者大于我们的需求，我们可以直接使用合并后的Span或切割合并后的Span，此时再忽视他们去申请一个128页的span是不合适的。

不过条件4中将零碎的Span合并后也就满足了条件1,2，这样问题就是什么时候合并？

再多思考一步，如果此时所有的Span都是空闲的，我们将它们合并在一起，是否会合并为一个128页或者多个128页的Span？然后我们将这些Span一并还给操作系统，此时的操作像是回收内存的步骤。

在上述条件1234中，我们将可以获取到一个NewSpan的过程都介绍了出来，其中条件4的后续操作也就是条件1和条件2。总的来说还是条件123获取一个NewSpan。至于合并Span的操作，我们放在后续回收内存时再介绍，观察如何满足条件4.

    // 判断SpanList是否为空
    bool Empty()
    {
    	return _head->next == _head;
    }

    // 头插
    void PushFront(Span* span)
    {
    	Insert( Begin(), span);
    }
    
    // 头删
    Span* PopFront()
    {
    	Span* span = _head->next;
    	Erase(span);
    	return span;
    }

Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

    // 位置一：如果在这里放置锁。怎么样？
    
    // 要一个K页的span
	// page cache 中对应的第k号桶有span
	if (!_spanlists[k].Empty())
	{
		return _spanlists[k].PopFront();
	}
	else
	{
		// k 号桶下没有span
		// 后续的桶中有span可以切分使用
        for (int i = k + 1; i < NPAGES; ++i)
        {
        	if (!_spanlists[i].Empty())
        	{
        		Span* kspan = new Span;					// 这个是最终要返回的切分好大小的span
        		Span* nspan = _spanlists[i].PopFront(); // 这个是作为切割用的span
        
        		kspan->_pageId = nspan->_pageId;		// 页号
        		kspan->_n = k;							// 页数
        		 
        		nspan->_pageId += k;
        		nspan->_n -= k;
        
        		// 切分好的Span也要放回对应的位置
        		_spanlists[i - k].PushFront(nspan);
        
        		return kspan;	// 给central cache
        	}
        }


		// 后续的桶中没有span可以用，要向系统申请
		Span* bigSpan = new Span;
		void* ptr = SystemAlloc(NPAGES - 1);	// 可回顾前面定长内存池向操作系统申请内存部分

		// 获取bigspan的 页号 和 页数
		bigSpan->_pageId = (PageID)ptr >> PAGE_SHIFT;
		bigSpan->_n = NPAGES - 1;

		// 插入
		_spanlists[bigSpan->_n].PushFront(bigSpan);
		
		// 重复切分128号桶为 k页和 128-k页
		// 重复上列切分步骤
		return NewSpan(k);
	}
}

PageCache不适合用桶锁，会造成效率低下，因为光是得到一个k页的Span的情况是申请一个128页的Span，将128页的Span拆分，得到第k页的Span，如果进行桶锁，这里面每一次访问桶都要加锁解锁，会导致效率降低（线程不断地睡眠唤醒）。

4.解决PageCache上锁解锁的问题

1.上述代码中位置一处放置锁合适吗？

不合适，因为如果出现递归调用的话，锁无法解开。但是可以选择使用支持递归的锁[ recursive_mutex ]；

2.分离一个子函数进行加锁。

将上列代码设置为子函数_NewSpan，使用NewSpan调用，在NewSpan中加锁。

或者在调用NewSpan函数前后加上锁，如后面的代码所示。

5.关于CentralCache桶锁的疑问

在CentralCache向PageCache获取内存对象时，CentralCache桶锁要解开吗？

在CentralCache向PageCache获取内存对象时，CentralCache中已经存在了一个桶锁，在向PageCache中申请内存对象前，这个桶锁要解开吗？

解开更好。

当线程一按照ThreadCache->CentralCache->PageCache的顺序申请内存时，在CentralCache没有内存并向PageCache获取内存对象时，如果桶锁不解开，对线程二或线程三的申请是没有影响的，因为此刻CentralCache没有内存，无法申请。

但是不仅仅是申请内存才会访问CentralCache，释放内存也同样需要访问CentralCache，所以在线程一申请内存时，线程二和线程三，以至于线程XXX都在释放内存，这些释放的内存本可以被及时使用的，现在不仅不能被及时利用，还要等线程一申请完内存后才能再操作。

**也就是说线程释放内存时，如果申请内存一直未完成，那么本该释放到对应哈希桶上的内存过程会被阻塞，这样不利于内存的使用。释放后的内存可以再利用，但因为申请新的内存，而无法被利用。**因此将桶锁解开更好。

CentralCache桶锁要立刻续上吗？

不需要。

加锁解锁的过程可以参考是否访问到被操作的对象，主要还要看是否是多个线程竞争时。

多个线程竞争才要加锁，PageCache的锁解开后，是对新申请到的Span拆分的过程，这个过程不存在线程竞争，不需要加锁。因为这个时间，其他线程访问不到Span（还没有和list产生关系）

往SpanList中插入时，需要加锁，因为这个过程中可能会有其他线程的操作，导致SpanList的结构发生变化，加锁可以保护该桶内数据的完整性和一致性。

6.获取非空span(二)-从PageCache中获取

// 页大小转换偏移, 即一页定义为2^13,也就是8KB
static const size_t PAGE_SHIFT = 13;

CentralCache从PageCache中获取一个新的Span，这个Span的大小怎么得到？

由对齐数得到NumMoveSize(size)，申请多少个对象，由对象*对齐数=要申请的大小，要申请的内存÷每页内存大小=要申请的页数。

/* 单个对象size大小向系统获取多少页 */
/* SizeClass */
static size_t NumMovePage(size_t size) 
{ 
	size_t num = NumMoveSize(size); 
	size_t npage = num * size; 
	npage >>= PAGE_SHIFT; // 每页 8KB
	if (npage == 0) 
		npage = 1; 
	return npage; 
}

Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{
	// CentralCache中就存在,自制迭代器
	Span* it = list.Begin();
	while (it != list.End())
	{
		if (it->_list != nullptr)
			return it;
		else
			it = it->_next;
	}

	list._mtx.unlock();	// 解开CentralCache的锁

	//需要向PageCache中申请到非空Span,进入PageCache时记得解锁加锁
	PageCache::GetInstance()._pageMtx.lock();
	Span* span = PageCache::GetInstance().NewSpan(ClassSize::NumMovePage(size));
	PageCache::GetInstance()._pageMtx.unlock();

	// 对这个非空Span做处理，切割内存挂在自由链表下。
	// 通过页号计算页的起始地址
	// 起始地址 = 页号 * 每页的大小 = _pageId << PAGE_SHIFT   
	char* start = (char*)(span->_pageId << PAGE_SHIFT);
	// span下的总内存 = 页数 * 每页大小 = _n << PAGE_SHIFT   
	size_t bytes = span->_n << PAGE_SHIFT;
	char* end = start + bytes;

	// 将span切割为对应大小的内存对象，悬挂在_list下
	span->_list = start;
	start += size;
	void* tail = span->_list;
	while (start < end)
	{
		NextObj(tail) = start;
		start += size;
		tail = NextObj(tail);
	}
	NextObj(tail) = nullptr; 	// 对一份指针做好处理

	list._mtx.lock();
	//将span挂到桶里面去
	list.PushFront(span);

	return span;
}

这是获取申请的span中的可得到的内存对象数量(个数)，span中的可用内存对象可能小于batchNum，那样得到的actualNum也小于batchNum，反之，则为batchNum：

四、调试查看申请内存的问题

我们创建一个p1对象来申请内存，观察我们申请内存的方式是否正确。

	// 测试申请内存合理
    void TestConcurrentAlloc()
    {
    	void* p1 = concurrentAlloc(136);
    }
    
    int main()
    {
    	// 测试申请内存合理
    	TestConcurrentAlloc();
    	return 0;
    }