前言

? 前面我們將內存的申請流程都走通了，現在就是內存回收的過程，主要是從 thread cache 開始，一層一層往下回收，因為我們調用的申請內存接口也是從 thread cache 開始的！

? 而每一層回收內存的方式其實都不太一樣，因為我們還有一個負載均衡的機制，就是當一個線程緩存中內存塊太多了，我們要將這些內存塊合并成一個大的內存塊對象也就是 span 然后返回給中心緩存，而中心緩存則將那些線程都還回來的 span 對象再組織成一個更大的 span 對象返回給頁緩存保存起來！所以我們需要將它們分開來講解！

Ⅰ. thread cache的內存回收

? 線程緩存的內存回收其實并不難，就是將用戶不需要的小內存塊重新插入到對應哈希桶的空閑鏈表中，此時加入一個負載均衡的判斷：判斷一下此時如果對應空閑鏈表中的內存塊個數大于了當前申請內存塊的數量的時候，我們就認為當前申請內存塊的數量對應的內存塊是不用到的，就將它們從空閑鏈表中彈出，然后返回這些內存塊的起始地址 start 給中心緩存，這樣子做的目的是防止這些不用的內存塊被浪費了！

? 當然 tcmalloc 源碼中實現的會更加復雜，它還會判斷整個哈希桶中的內存塊的個數來進行負載均衡，而我們只是一個簡化版本，不過重要的是學習這個思想！

? 所以我們來完善一下之前 thread cache 中遺留下的 deallocate() 函數，如下所示：

// ThreadCache.cpp文件
// 釋放內存接口
void ThreadCache::deallocate(void* ptr, size_t size)
{assert(size <= THREAD_MAX_SIZE); // 要求申請的空間是小于256KB的assert(ptr != nullptr);// 將ptr指向的空間插入到對應的哈希桶中即可size_t index = AlignClass::get_index(size);_freelists[index].push(ptr);// 當一個桶中的內存塊超過了其當前申請內存塊的數量的時候，// 就將當前申請的內存塊數量的內存塊還給central cache，防止占用太多內存塊if (_freelists[index].get_size() > _freelists[index].get_maxsize())give_back_memory(_freelists[index], size);
}

? 此時需要提供一些細節，比如上面的獲取當前空閑鏈表的內存塊個數 get_size() 函數，以及待會 give_back_memory() 函數中需要用到將多個內存塊從空閑鏈表彈出的操作，所以要提供一個 pop_range() 接口，然后因為我們需要對內存塊進行計數，所以需要在之前的 push、pop、append 函數中處理一下計數，所以我們都在 FreeList 類中完善這些接口，具體看注釋部分即可：

// Common.h文件
class FreeList
{
private:void* _freelist = nullptr; // 指向空閑鏈表頭節點的指針size_t _size = 0;    // 表示當前空閑鏈表中內存塊的個數size_t _maxsize = 1; // 表示當前空閑鏈表申請空間塊時允許獲得的最大個數（會不斷遞增）
public:// 將單個內存對象頭插插入空閑鏈表void push(void* obj){assert(obj != nullptr);get_next(obj) = _freelist;_freelist = obj;_size++; // 記得累加個數}// 將多個內存對象頭插插入空閑鏈表void append(void* start, void* end, size_t size){assert(start != nullptr && end != nullptr);get_next(end) = _freelist;_freelist = start;_size += size; // 記得累加個數}// 頭刪方式取出空閑鏈表中的空間void* pop(){assert(_freelist != nullptr);void* obj = _freelist;_freelist = get_next(obj);_size--; // 記得減去個數return obj;}// 將多個內存塊從空閑鏈表彈出，通過輸出型參數獲取首尾地址void pop_range(void*& start, void*& end, size_t num){// 1. 先定位首尾位置（end要停在第num塊上，所以實際走的是num-1步）start = _freelist;end = start;for (int i = 0; i < num - 1; ++i)end = get_next(end);// 2. 將該區間的內存塊與空閑鏈表斷開，然后將end的next置為空即可_freelist = get_next(end);get_next(end) = nullptr;// 3. 最后別忘了內存塊個數要減少_size -= num;}bool empty() { return _freelist == nullptr; }size_t& get_maxsize() { return _maxsize; }size_t& get_size() { return _size; }
};

? 最后就是來實現另一個輔助接口 give_back_memory()，因為我們上面 deallocate() 接口只是負責判斷是否需要啟動負載均衡操作，而具體操作要交給該函數來實現！
? 其實并不難，其內部就是調用中心緩存的一個接口 merge_memory_from_ThreadCache() 來合并到中心緩存中，具體的實現我們到中心緩存部分再講，下面是 give_back_memory() 函數的實現：

// ThreadCache.cpp
// 釋放對象時，鏈表過長時，歸還對應數量的內存塊給central cache
void ThreadCache::give_back_memory(FreeList& list, size_t size)
{// 1. 先從當前空閑鏈表中取出當前申請內存塊的數量個內存塊void* start = nullptr;void* end = nullptr;list.pop_range(start, end, list.get_maxsize());// 2. 然后調用central cache的接口將這些內存塊合并到central cache中CentralCache::get_instance()->merge_memory_from_ThreadCache(start, size);
}

Ⅱ. central cache的內存回收

? 現在中心緩存要完成的無非就是上面遺留下的 merge_memory_from_ThreadCache() 接口，但是現在有個問題就是，我們拿到了要回收到中心緩存的一串小內存塊鏈表的起始地址 start，并且知道它們的總大小為 size，此時我們需要找到這些小內存塊對應的是中心緩存中的哪個 span 對象呀，這怎么辦??

? 其實可以 用得到的每個小內存塊的地址 start 來除以一頁的大小（我們規定是 8K），就能得到該小內存塊對應的起始頁號，然后我們可以暴力一點，去中心緩存或者頁緩存中遍歷所有的 span 對象的頁號進行比對，就能確認每個小內存塊對應的是哪個 span 對象了（因為小內存塊的排序也是混亂的，所以需要每個小內存塊都去查找），但問題是這種查找方式的時間復雜度比較高，是 O(n^2)，這是我們無法接受的！

? 既然說到了比對，我們就想到可以用哈希表來快速索引，所以我們可以 在 PageCache 類中添加一個哈希表，建立一下每個頁號與對應 span 對象的映射關系，這樣子我們得到了頁號就能快速找到其對應的 span 對象了，時間是非常快的！（至于為什么不是在 CentralCache 類中添加哈希表，是因為后面 PageCache 也會用到頁號來查找對應內存塊的對象，那我們干脆就存放在 PageCache 類中就行了，就不用再多存一份了！）

? 下面只需要關心注釋部分：

// PageCache.h
#pragma once
#include "Common.h"class PageCache
{
private:SpanList _spanlists[PAGELIST_NUMS];std::mutex _mtx; static PageCache _page_instance; std::unordered_map<page_t, Span*> _tables; // 存放頁號與對應span對象的映射關系
public:static PageCache* get_instance() { return &_page_instance; }Span* new_span(size_t k);std::mutex& get_mutex() { return _mtx; }
private:PageCache() {}PageCache(const PageCache&) = delete;PageCache& operator=(const PageCache&) = delete;
};

? 然后我們需要 在 new_span() 函數中添加上建立頁號和對應 span 對象關系的操作，也就兩行代碼，如下所示：（也是只需要關心注釋部分）

// PageCache.cpp
// 獲取一個k頁大小的span
Span* PageCache::new_span(size_t k)
{// 看看當前k頁大小的哈希桶中是否有可用的span對象，找到了直接將其取出然后進行返回即可if (!_spanlists[k].empty()){Span* span = _spanlists[k].pop_front();// 建立back中每個頁號和span的映射，方便central cache回收小塊內存時，查找對應的spanfor (page_t i = 0; i < span->_num; ++i)_tables[span->_pid + i] = span;return span;}for (int i = k + 1; i < PAGELIST_NUMS; ++i){if (!_spanlists[i].empty()){Span* front = _spanlists[i].pop_front();Span* back = new Span;back->_pid = front->_pid;back->_num = k;front->_pid += k;front->_num -= k;_spanlists[front->_num].push_front(front);/*對于front中每個頁號與span的映射，我們只需要記錄首尾頁號即可，因為front是沒有分配中心緩存使用的，所以后面我們再合并已經分配的那些內存塊的時候，是中心發散的去查找內存塊左右臨近的內存塊進行合并的，此時我們對于front的頁號與span的映射只需要記錄下首尾即可，而不需要向back一頁每個小內存塊的頁號都要去進行映射，因為back是被分配去使用的，所以需要進行每個頁號的映射*/_tables[front->_pid] = front;_tables[front->_pid + front->_num - 1] = front;// 建立頁號和span的映射，方便central cache回收小塊內存時，查找對應的spanfor (page_t i = 0; i < back->_num - 1; ++i)_tables[back->_pid + i] = back;return back;}}void* ptr = SystemAlloc(PAGELIST_NUMS - 1);Span* newspan = new Span;newspan->_num = PAGELIST_NUMS - 1;newspan->_pid = (page_t)ptr >> PAGE_SHIFT;_spanlists[PAGELIST_NUMS - 1].push_front(newspan);return new_span(k);
}

? 此時我們可以提供一個功能函數，用于將傳入的內存塊地址獲取對應的 span 對象指針，如下所示：

// PageCache.cpp
// 根據傳入的內存塊地址返回對應的span對象的指針
Span* PageCache::get_span_from_pageID(void* ptr)
{// 1. 先根據地址求出其所屬的頁號page_t pid = ((page_t)ptr >> PAGE_SHIFT);// 2. 找到對應的頁號對應的span指針進行返回auto it = _tables.find(pid);if (it != _tables.end())return it->second;elsereturn nullptr;
}

? 有了上面的鋪墊，我們就能實現 merge_memory_from_ThreadCache() 函數了，但是需要借助到頁緩存中實現的 merge_memory_from_CentralCache() 接口，這個接口等下面我們將頁緩存的回收內存再來講！剩下的具體步驟參考下面代碼以及注釋：

// CentralCache.cpp
// 將size大小的內存塊合并到對應的span哈希桶中
void CentralCache::merge_memory_from_ThreadCache(void* start, size_t size)
{// 1. 獲取對應哈希桶下標并且加上桶鎖size_t index = AlignClass::get_index(size);_spanlists[index].get_mutex().lock();// 2. 遍歷每一個小內存塊while (start != nullptr){// 3. 找到小內存塊對應的span對象，并將該小內存塊鏈接到該span上面（先記錄下start后面的指針next，防止start修改連接后丟失）void* next = get_next(start);Span* span = PageCache::get_instance()->get_span_from_pageID(start);get_next(start) = span->_freelist;span->_freelist = start;// 4. 減少span的使用個數，然后判斷是否可以回收給PageCachespan->_use_count--;if (span->_use_count == 0){// 可以的話調用PageCache對應的接口回收該span對象// 再次之前要先將該span對象從central cache中彈出，并且修改span的鏈接屬性_spanlists[index].erase(span);span->_freelist = nullptr;span->_next = span->_prev = nullptr;// 因為涉及到頁緩存操作，所以需要加鎖，并且此時可以順便先將中心緩存的鎖給釋放，讓其它線程可以執行，提高效率_spanlists[index].get_mutex().unlock();PageCache::get_instance()->get_mutex().lock();PageCache::get_instance()->merge_memory_from_CentralCache(span); // 這步就是PageCache回收span對象的操作PageCache::get_instance()->get_mutex().unlock();_spanlists[index].get_mutex().lock();}// 5. 別忘了讓start迭代start = next;}// 6. 最后別忘了釋放桶鎖_spanlists[index].get_mutex().unlock();
}

Ⅲ. page cache的內存回收

? 頁緩存的內存回收，就是嘗試將中心緩存返回的小 span 對象以及其相鄰的空閑的 span 對象合并成一個頁。比如中心緩存中一個 span 對象中有 3 頁，其左邊有一個空閑的 span 對象為 2 頁大小，那么就將它們兩個合并成一個 5 頁大小的 span 對象交給頁緩存管理！

? 但此時有一個問題，就是我們得知道其相鄰的 span 對象是否為空閑狀態，如果我們用 _use_count == 0 去判斷為空閑的話，是不合適的，因為有可能別的線程正在準備使用該相鄰的內存塊，但是還沒有將其 _use_count 進行改變，此時如果我們就將其判斷為空閑然后回收的話，那么別的線程就出錯了！

? 所以需要 在 Span 結構體中再添加一個布爾值變量 _is_used 來表示當前對象是否被線程使用著。

// 管理以頁為單位的大內存塊
struct Span
{page_t _pid = 0; // 大塊內存起始頁的頁號size_t _num = 0; // 頁的個數Span* _next = nullptr; // 雙向鏈表結構Span* _prev = nullptr;size_t _use_count = 0;	   // 當前分配給ThreadCache對象的小內存塊個數void* _freelist = nullptr; // 當前大內存塊對應的空閑鏈表bool _is_used = false; // 表示當前對象是否被線程使用著
};

? 然后我們只需要用中心擴散法，向前和向后合并空閑的內存塊即可，最后再將合并好的內存塊掛到 page cache 中，如下所示，具體參考代碼注釋：

// PageCache.cpp
// 將CentralCache傳來的span對象合并到頁緩存中管理
void PageCache::merge_memory_from_CentralCache(Span* span)
{// 1. 向前合并空閑的span對象while (true){// 獲取前面一個span對象（如果沒有則直接退出）page_t prev_pid = span->_pid - 1;auto it = _tables.find(prev_pid);if (it == _tables.end())break;// 如果span對象被使用著，或者和當前span的頁數加起來超過了PAGELIST_NUMS-1頁的話，則直接退出Span* prev_span = it->second;if (prev_span->_is_used == true)break;if (prev_span->_num + span->_num > PAGELIST_NUMS - 1)break;// 走到這說明prev_span對象是可以合并的，則將其進行合并操作// 合并操作其實只需要修改span的屬性即可，然后將原本prev_span從哈希表中去除，最后釋放prev_span空間的內容即可span->_pid = prev_span->_pid;span->_num += prev_span->_num;_spanlists[prev_span->_num].erase(prev_span);delete prev_span;}// 2. 向后合并空閑的span對象（和上面是類似的操作，就是位置變了而已）while (true){// 獲取后面一個span對象（如果沒有則直接退出）page_t next_pid = span->_pid + span->_num;auto it = _tables.find(next_pid);if (it == _tables.end())break;// 如果span對象被使用著，或者和當前span的頁數加起來超過了PAGELIST_NUMS-1頁的話，則直接退出Span* next_span = it->second;if (next_span->_is_used == true)break;if (next_span->_num + span->_num > PAGELIST_NUMS - 1)break;// 走到這說明next_span對象是可以合并的，則將其進行合并操作// 合并操作其實只需要修改span的屬性即可，然后將原本next_span從哈希表中去除，最后釋放next_span空間的內容即可span->_num += next_span->_num;_spanlists[next_span->_num].erase(next_span);delete next_span;}// 3. 將合并后的span對象插入到page cache的哈希桶中，然后設置其映射關系_spanlists[span->_num].push_front(span);span->_is_used = false;_tables[span->_pid] = span;_tables[span->_pid + span->_num - 1] = span;
}