Ⅰ. 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);
}