Ⅰ. page cache页缓存的结构设计

​ 首先页缓存还是一个哈希桶的结构，但是和前两者不同的是，页缓存的哈希桶中存放的是一个或者多个 span 合并的大 span 对象，之前中心缓存的哈希桶虽然挂的也是 span 对象，但那些 span 对象都是一个独立的个体，而 页缓存则是将这些 span 对象根据不同的页大小进行合并然后映射到对应的哈希桶中，并且页缓存中的 span 对象就不切分为小内存块了，而是交给中心缓存自己去切分！

​ 其结构如下图所示：

​ 之所以要有不同的页大小，其实就是因为中心缓存可能会向页缓存申请的空间大小是比较大的，此时就需要有多个 span 对象组成的页才够用！

​ 并且对于页缓存的操作，我们是对整个页缓存进行加锁，而不是对单一的哈希桶进行加锁，这和页缓存的分配以及合并操作有关系，下面我们会解释！之所以这里不能用桶锁，其实不是因为真的不能用桶锁，而是因为用桶锁的话，我们对页缓存的一个操作可能涉及到多个桶，如果来来回回要开锁和解锁的话，其实会增加系统的消耗的，加桶锁和对整个页缓存加锁，就类比一个 for 循环中进行加锁，与一个 for 循环外面进行加锁的区别，后者的效率是会更高的！

​ 所以我们之所以选择对整个页缓存进行加锁也不是对单一的哈希桶进行加锁不是因为真的不能用桶锁，而是因为 效率问题！

​ 此外因为页缓存只有一个，所以 页缓存也要设计为单例模式！

申请内存的过程：

1. 当中心缓存向页缓存申请内存时，页缓存首先会检查对应页大小的哈希桶中有没有 span 对象可用，如果没有则 向更大页寻找可用的 span（之所以不找更小页是因为如果找小页的话，产生内存碎片的几率会变大），如果找到则将其进行分裂和分配。
   • 比如：申请的是 4 页 page，此时 4 页 page 后面没有挂 span，则向后面寻找更大的 span，假设在 10 页 page 位置找到一个 span，则将 10 页的大 span 分裂为一个 4 页大小的 span 和一个 6 页大小的 span，然后将 4 页大小的 span 返回给中心缓存，将 6 页大小的 span 插入到页缓存中对应 6 页 page 的链表中。
2. 如果页缓存中都没有合适的 span，则 向系统使用 mmap、brk 或者 VirtualAlloc 等方式申请 128 页大小的 span 挂在页缓存的空闲链表中，再重复第一步中的过程。
   • 之所以申请的是 128 页大小的 span，其实不是固定的方法，这个是可以自己调节的，因为我们规定一页大小就是 8KB，那么 128 页也就有 1MB 大小了，如果觉得不够的话是可以自主调大一些的！

释放内存的过程：

• 如果中心缓存释放了一个 span，那么页缓存就将该 span 插入到对应的 span 大小的哈希桶中，然后依次寻找该 span 对应的页号前后的空闲 span，判断是否可以合并，如果可以的话则将附近相邻的空闲 span 一块合并成大的 span，然后插入到大的 span 对应的哈希桶中，这样可以减少内存碎片。

​ 从申请内存的角度来看，span 大的会向上分配给 span 小的哈希桶，而 从释放内存的角度来看，span 小的会向下分配给 span 大的哈希桶，这是一个动态的过程，也是很好的减少了内存碎片的产生！

​ 下面是页缓存的主体框架：

// Common.h文件
static const size_t PAGELIST_NUMS = 129; // 页缓存中哈希桶的个数// PageCache.h文件
#pragma once
#include "Common.h"// 单例模式：饿汉方式
class PageCache
{
private:SpanList _spanlists[PAGELIST_NUMS];std::mutex _mtx; static PageCache _page_instance; // 该类的单例对象（需要在cpp文件中定义）
public:static PageCache* get_instance(){return &_page_instance;}// 获取一个k页大小的spanSpan* new_span(size_t k);std::mutex& get_mutex() { return _mtx; }
private:// 将构造函数私有化，将拷贝构造和赋值重载封掉PageCache() {}PageCache(const PageCache&) = delete;PageCache& operator=(const PageCache&) = delete;
};

Ⅱ. 完善central cache中的 get_span() 函数

​ 知道了页缓存的结构之后，我们就能实现一下之前中心缓存遗留下的申请一个 span 对象的函数了！因为涉及到遍历以及后面对 span 对象的头插和头删操作，所以这里我们就在 SpanList 类中添加几个接口，如下所示，只需要关注注释部分即可：

// Common.h
// 管理Span结构的带头双向链表
class SpanList
{
private:Span* _head;	std::mutex _mtx; 
public:SpanList();// 获取链表的首尾节点，用于遍历Span* begin() { return _head->_next; }Span* end() { return _head; }void insert(Span* pos, Span* node);void erase(Span* node);// 头插接口void push_front(Span* node){insert(begin(), node);}// 头删并且获取该span对象的接口Span* pop_front(){Span* front = begin();erase(front);return front;}bool empty() { return _head->_next == _head; }std::mutex& get_mutex() { return _mtx; }
};

​ 接下来就能实现 get_span() 函数了，具体参考代码的注释，如下所示：

// Common.h
static const size_t PAGE_SHIFT = 13; // 一页大小对应以2为底的指数，这里我们规定一页为8KB，所以指数为13// CentralCache.cpp
// 获取一个非空的span对象
Span* CentralCache::get_span(SpanList& list, size_t size)
{// 1. 遍历当前的spanlist中是否还有未分配对象的spanSpan* it = list.begin();while (it != list.end()){// 存在未分配对象的话直接返回该span即可if (it->_freelist != nullptr)return it;it = it->_next;}// 2. 因为下面就是向page cache申请内存的操作了，就涉及到page cache的加锁，那么此时/*我们可以把中心缓存当前的桶锁释放，这样子就算释放了其它线程，它们也需要进来这个函数，当他们访问下面的new_span()函数的时候还是需要被锁住，不需要担心线程安全问题！不过我们在这提前释放锁的好处就是如果其他线程是释放内存对象回来的话，因为不会被阻塞而提高效率！*/list.get_mutex().unlock();// 3. 走到这里说没有空闲span了，只能找page cache要/*此时先计算要申请多少页，然后再去申请，并且这个过程要进行加锁！之所以不到new_span()函数中去加锁，其实是因为内部有递归调用自己的操作，所以我们就统一在这里处理加锁问题！当然如果new_span()函数中使用的是递归锁，或者不使用递归调用自己的操作，那是可用在其内部处理锁问题的！*/PageCache::get_instance()->get_mutex().lock();Span* newspan = PageCache::get_instance()->new_span(AlignClass::get_nums_of_page(size));PageCache::get_instance()->get_mutex().unlock();// 4. 先计算获取到的span的大小以及span的起始地址（方便后面的遍历切分）size_t span_size = newspan->_num << PAGE_SHIFT;char* start = reinterpret_cast<char*>(newspan->_pid << PAGE_SHIFT);char* end = start + span_size;// 5. 然后对获取到的span进行切分，此时不需要加锁，因为这个时候其他线程访问不到这个span局部对象！//  5.1 先切一块下来做头节点，方便尾插（头插的话地址是倒着链起来的，缓存命中率会降低）void* tail = start;newspan->_freelist = tail;start += span_size;//  5.2 将剩下的内存块进行尾插while (start < end){get_next(tail) = start;tail = start;start += size;}get_next(tail) = nullptr; // 关键点// 6. 切好之后将内存块链接到对应的SpanList上（这里采用头插），但是因为涉及线程安全问题，这里要重新上桶锁list.get_mutex().lock();list.push_front(newspan);return newspan;
}

Ⅲ. 实现页缓存获取span对象的接口

​ new_span() 函数其实并不难实现，就是先看看对应页数大小的哈希桶中是否有可用的 span 对象，没有的话再去更大的页数哈希桶中找，实在找不到的话才去向系统申请空间！

​ 具体细节参考代码：

// Common.h
#ifdef _WIN32#include <Windows.h>
#else//linux等相关头文件...
#endif// 直接去堆上申请按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// linux下brk mmap等
#endifif (ptr == nullptr)throw std::bad_alloc();return ptr;
}------------------------------------------------------------------------------------------------
// PageCache.cpp
#include "PageCache.h"PageCache PageCache::_page_instance; // 静态单例对象的定义// 获取一个k页大小的span
Span* PageCache::new_span(size_t k)
{// 1. 看看当前k页大小的哈希桶中是否有可用的span对象，找到了直接将其取出然后进行返回即可if (!_spanlists[k].empty())return _spanlists[k].pop_front();// 2. 没有的话向更大的页大小的哈希桶中查找是否有可用的span对象for (int i = k + 1; i < PAGELIST_NUMS; ++i){if (!_spanlists[i].empty()){// 找到了可用的span对象之后，进行切分操作（只需要改变span对象中的属性以及链接关系即可）// 这里采用将前i-k大小的span对象也就是front继续留在该哈希桶中，然后将后半部分k大小的span对象也就是back进行返回！Span* front = _spanlists[i].pop_front();Span* back = new Span;// back就是我们要返回的span对象，设置其属性back->_pid = front->_pid;back->_num = k;// 修改front的属性，然后将其插入到i-k大小的哈希桶中！front->_pid += k;front->_num -= k;_spanlists[front->_num].push_front(front);return back;}}// 3. 如果所有哈希桶都没有可用的span对象，那么就得向系统申请内存了//    当前为windows环境，所以调用的就是windows的接口，这里申请的是128页大小的内存！void* ptr = SystemAlloc(PAGELIST_NUMS - 1);// 4. 将申请到的内存与span对象进行属性绑定（页号为ptr的地址然后按一页大小进行编号得到即可）Span* newspan = new Span;newspan->_num = PAGELIST_NUMS - 1;newspan->_pid = (page_t)ptr >> PAGE_SHIFT;_spanlists[PAGELIST_NUMS - 1].push_front(newspan);// 5. 这里可用按照上面切分的步骤那样子再写一遍，但是没必要，有更妙的方法：再调用当前函数一次/*   因为当前新申请到的内存插入到了哈希桶中，但是没有返回给中心缓存使用，如果此时我们再调用一次当前函数的话，此时哈希桶中就有span对象挂着了，就会走到上面的第二步去进行span对象的切分和返回，就不需要再写一遍同样的逻辑了！这点调用函数的开销，对于程序执行速度来说，是无足挂齿的，并且因为内存是比较连续的，效率也是不低的，所以无需多虑！*/ return new_span(k);
}