Central cache
threadcache是每個線程獨享，而centralcache是多線程共享，需要加鎖（桶鎖）一個桶一個鎖
解決外碎片問題：內碎片：申請大小超過實際大小；外碎片：空間碎片不連續，導致無法申請大塊空間
span
在存儲管理中，"span"是一個術語，用于描述連續的內存塊或磁盤塊的范圍。
在內存管理中，一個span通常是一系列連續的內存頁或內存塊，它們被分配給一個進程或數據結構。一個span的大小可以根據需求而變化，通常是以頁的大小為單位進行分配。
在磁盤管理中，一個span通常是一系列連續的磁盤塊，它們被分配給一個文件或數據結構。一個span的大小可以根據需求而變化，通常是以磁盤塊的大小為單位進行分配。
使用span的好處是可以提高內存或磁盤的利用率，避免了碎片化的問題。通過分配連續的span，可以更有效地利用存儲資源，并提高數據的讀寫性能。
span設計成雙向鏈表 帶頭雙向循環，插入刪除更加高效
32位機器和64位機器的頁數不同！！！！！！！！！
使用條件編譯在預處理階段解決
#ifdef _WIN32typedef size_t PAGE_ID;
#elif _WIN64typedef unsigned long long PAGE_ID;
#endif
但是在64位下還是會有問題
所有要調換順序
#ifdef _WIN64typedef unsigned long long PAGE_ID;
#elif _WIN32typedef size_t PAGE_ID;
#endif
// 管理多個連續頁大塊內存跨度結構
struct Span
{PAGE_ID _pageId = 0; // 大塊內存起始頁的頁號size_t _n = 0; // 頁的數量Span* _next = nullptr; // 雙向鏈表結構Span* _prev = nullptr;size_t _useCount = 0; // 切好小塊內存，被分配給thread cache的計數void* _freeList = nullptr; // 切好的小塊內存的自由鏈表
};// 帶頭雙向循環鏈表
class SpanList
{
public:SpanList(){_head = new Span;_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 newspan posprev->_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; // 桶鎖
};
CentralCache類
只能有一個，所以采用單例模式
// 單例模式
class CentralCache
{
public:static CentralCache* GetInstance(){return &_sInst;}// 獲取一個非空的spanSpan* GetOneSpan(SpanList& list, size_t byte_size);// 從中心緩存獲取一定數量的對象給thread cachesize_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size);private:SpanList _spanLists[NFREELIST];private:CentralCache(){}CentralCache(const CentralCache&) = delete;static CentralCache _sInst;
};
threadcache從centralcache中獲取span
首先明確一次獲取的數量
// 一次thread cache從中心緩存獲取多少個static size_t NumMoveSize(size_t size){assert(size > 0);// [2, 512]，一次批量移動多少個對象的(慢啟動)上限值// 小對象一次批量上限高// 小對象一次批量上限低int num = MAX_BYTES / size;if (num < 2)num = 2;if (num > 512)num = 512;return num;}
實現獲取，逐步遞增。獲取一個時直接返回就行，不是一個時先將其串聯起來再返回頭
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{// 慢開始反饋調節算法// 1、最開始不會一次向central cache一次批量要太多，因為要太多了可能用不完// 2、如果你不要這個size大小內存需求，那么batchNum就會不斷增長，直到上限// 3、size越大，一次向central cache要的batchNum就越小// 4、size越小，一次向central cache要的batchNum就越大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);return start;}
}
完善自由鏈表
//管理切分好的小對象的自由鏈表
class FreeList
{
public:void Push(void* obj){assert(obj);// 頭插//*(void**)obj = _freeList;NextObj(obj) = _freeList;_freeList = obj;}void PushRange(void* start, void* end){NextObj(end) = _freeList;_freeList = start;}void* Pop(){assert(_freeList);// 頭刪void* obj = _freeList;_freeList = NextObj(obj);return obj;}bool Empty(){return _freeList == nullptr;}size_t& MaxSize(){return _maxSize;}
private:void* _freeList;size_t _maxSize = 1;
};
實現FetchRangobj
// 從中心緩存獲取一定數量的對象給thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)
{size_t index = SizeClass::Index(size);_spanLists[index]._mtx.lock();Span* span = GetOneSpan(_spanLists[index], size);assert(span);assert(span->_freeList);// 從span中獲取batchNum個對象// 如果不夠batchNum個，有多少拿多少start = span->_freeList;end = start;size_t i = 0;size_t actualNum = 1;while (i < batchNum - 1 && NextObj(end) != nullptr){end = NextObj(end);++i;++actualNum;}span->_freeList = NextObj(end);NextObj(end) = nullptr;span->_useCount += actualNum;_spanLists[index]._mtx.unlock();return actualNum;
}
