一. ThreadCache回收内存

1. 基本步骤

当线程释放对象空间的大小小于256KB时会将内存释放回ThreadCache，计算对象大小bytes映射ThreadCache自由链表桶的下标 i，将对象PushFront到_freeLists[ i ]。

当自由链表的长度过长，则回收自由链表中的所有小块定长内存到CentralCache。

2 FreeList类中的补充

补充一：增加一个获取自由链表中小块定长内存个数的接口FreeList::GetSize(...)

补充二：增加一个删除自由链表中头n个小块定长内存的接口FreeList::PopRangeFront(...)，注意还需要把要删除的一段小块定长内存通过输出型参数传出：

3. 线程缓存回收一个小块定长内存的实现

ThreadCache回收一个小块定长内存的接口我们在ThreadCache初步设计时就有简单的实现过，那时候的实现仅仅就是“回收一个小块定长内存到自由链表”，这个只是ThreadCache回收内存基本步骤中的第一步：

// ThreadCache初步设计时的释放一个小块定长内存
void ThreadCache::Deallocate(void* ptr, size_t bytes)
{
  assert(ptr);
  assert(bytes <= MAX_BYTES);
  // 1、计算映射到哪一个自由链表桶
  size_t index = SizeClass::Index(bytes);
  // 2、把小块定长内存头插到自由链表桶中
  _freeLists[index].PushFront(ptr);
}

现在继续实现基本步骤中的第二步：当自由链表的长度过长，则回收自由链表中的所有小块定长内存到CentralCache：

另外我们在线程缓存中新增一个private接口ThreadCache::ListToolong(...)专门用于归还自由链表中的小块定长内存给CenralCache：

下面是ThreadCache::ListToolong(...)函数的内部实现步骤：

把自由链表中的所有小块定长内存剥离。

把所有剥离出来的小块定长内存归还到CentralCache对应SpanList桶中的不同Span中。

// 归还一段list给CenralCache
void ThreadCache::ListToolong(FreeList& list, size_t bytes)
{
  assert(bytes > 0);
  void* start = nullptr;
  void* end = nullptr;
  // 1、把自由链表中的所有小块定长内存剥离
  list.PopRangeFront(start, end, list.GetSize());
  // 2、只需要传第一个小块定长内存的指针即可，因为它们是单链表结构组织起来的，最后会走到空
  CentralCache::GetInstance()->ReleaseListToSpans(start, SizeClass::Index(bytes));
}

PS：注意ThreadCache和CentralCache的哈希桶映射规则是一样的，所以我们从ThreadCache的某一个自由链表桶中剥离出来的小块定长内存应该回收到CentralCache相同下标的SpanList桶中。而且本来自由链表中存储的一个个小块内存是从中心缓存的某个SpanList桶中的不同Span对象“批发”出来的，具体小块定长内存归还给那个Span对象这个操作由中心缓存的CentralCache::ReleaseListToSpans(...)函数来完成。

二. CentralCache回收内存

1. 基本步骤

当ThreadCache中的自由链表过长时会将里面的所有小块定长内存释放回CentralCache的某个Span对象中，每释放回来一个小块定长内存，则Span对象的_useCount减一。

当_useCount从1减到0时说明这个Span对象分出去的所有小块定长内存都收回来了，这时我们可以将这个Span对象释放回PageCache，PageCache中会对这个Span对象的前后相邻空闲页进行合并以缓解外碎片问题。

2. PageCache类中的补充

前面说到ThreadCache某个自由链表桶中的每一个小块定长内存需要回收到CentralCache相同映射下标的SpanList桶中的不同Span对象里，那么每一个小块定长内存如何找到它与之对应的span的？

这里要再次说明申请小块定长内存的过程：每一个小块定长内存都是由连续大页内存切分而来的，即一开始申请内存时CentralCache向PageCache要一个k页的Span，然后CentralCache把这个k页连续大块内存切分成许多小块定长内存一部分分配给ThreadCache，另一部分留在Span中。

现在有一个结论就是：每一个小块定长内存的地址模上8KB（一页的大小）就能得到把它切分出来的那一页的页号：

因为每一页的页号都是页地址整除8KB得来的，那么该页切分出来的所有小块定长内存的地址肯定是不能整除8KB的，所以我们对小块定长内存的地址取模8KB得到的就是它所在那一页的页号，关于这个结论我们可以通过下面的代码来简单做个测试：

void TestObjAddressShift()
{
  PAGE_ID id1 = 2000;
  PAGE_ID id2 = 2001;
  char* p1 = (char*)(id1 << PAGE_SHIFT);
  char* p2 = (char*)(id2 << PAGE_SHIFT);
  // 模拟把页号为2000的一个页切分成许多8字节大小的小块定长内存
  // 打印每一个小块定长内存的地址和它取模一页得到的值
  while (p1 < p2)
  {
  cout << (void*)p1 << ":" << ((PAGE_ID)p1 >> PAGE_SHIFT) << endl;
  p1 += 8;
  }
}

编译运行，发现页号为2000的一个页切分出来的每一个小块8byte内存的地址取模一页大小（8KB）得到的值就是它所在页的编号：

那么如何找到CentralCache中分配这个小块定长内存的Span对象呢？通过上面的结论我们可以拿到小块定长内存所在页的页号，有一个方法是根据这个页号遍历中心缓存中与小块定长内存所挂自由链表相同映射下标的SpanList桶中的所有Span对象，看小块定长内存所属页页号是否在某个Span对象所包含的页范围内，这种查找的方法可以，但是效率太低了。想要高效率查找的话我们可以定义一个std::unordered_map类型的变量来专门映射页号和这个页所属的Span对象。

因为后面PageCache也有从CentralCache回收Span的功能，所以我们在PageCache中来定义页号和span对象的映射：

// 定义在PageCache中的private成员变量
// 关于页号和Span对象地址的映射
std::unordered_map<PAGE_ID, Span*> PageCache::_idSpanMap;

有了这个映射后我们可以根据页号直接拿到该页所属的Span对象，另外之前在页缓存中有一个函数叫做PageCache::NewSpan(size_t k)，它的功能是分配一个k页的Span给CentralCache，在拿到k页的Span后，我们还有必要对这个即将被CentralCache切分成许多小块定长内存的k页Span对象完成它的每一页页号和它本身的映射：

如果PageCache::_spanList[ k ]中有Span的话直接拿第一个Span给CentralCache：

如果PageCache::_spanList[ k ]中没有Span对象则找更大Span去切出k页的Span给CentralCache：

这一步其实也可以在CentralCache::GetOneSpan(...)中申请到k页Span后统一来完成，不过要把页缓存中的PageCache::_idSpanMap这个成员变量设为public或者提供一个公有接口获得这个私有的成员变量，这里我就不这样做了，最后还是把PageCache::_idSpanMap设为private并且在PageCache::NewSpan(size_t k)中完成新的k页Span对象和它拥有的所有页 页号的映射工作。

最后我们还需要在PageCache中封装一个PageCache::MapObjectToSpan(void* obj)的公有接口。关于这个函数的功能：我们只需传入小块定长内存的地址即可获得它所在页对应的Span。

下面是该函数的内部实现逻辑：

下面是PageCache::MapObjectToSpan(void* obj)的具体实现：

// 传入小块定长内存获得所在页对应的Span对象
Span* PageCache::MapObjectToSpan(void* obj)
{
  assert(obj);
  PAGE_ID id = ((PAGE_ID)obj >> PAGE_SHIFT);
  auto ret = _idSpanMap.find(id);
  if (ret != _idSpanMap.end())
  {
  return ret->second;
  }
  else
  {
  assert(false);
  return nullptr;
  }
}

3. 中心缓存回收自由链表中批量小块定长内存的实现

对接上面线程缓存的ThreadCache::ListToolong(...)接口：

接下来我们具体实现中心缓存的CentralCache::ReleaseListToSpans(...)：

首先遍历小块定长内存通过PageCache::MapObjectToSpan(void* obj)直接拿到其对应的Span地址。

然后把这个小块定长内存头插到Span管理切好的小块定长内存的单链表中。

头插完成后让Span对象的_useCount减一，表示有一个分出去的小块定长内存收回来了。

如果这个Span对象的_useCount等于0说明Span切好分出去的所有小块定长内存都收回来了这时可以把这个Span回收到下一层PageCache中合并出更大页的Span。

// 回收自由链表中的所有小块定长内存到它们各自对应的Span中
void CentralCache::ReleaseListToSpans(void* start, size_t index)
{
  assert(start);
  assert(index >= 0);
  // 自由链表中的所有小块定长内存都来自于_spanLists[index]所存储的Span中
  _spanLists[index].GetSpanListMutex().lock();
  while (start)// 把每一个小块定长内存头插到对应Span的_freeList中
  {
  void* next = NextObj(start);
  Span* span = PageCache::GetInstance()->MapObjectToSpan(start);
  NextObj(start) = span->_freeList;
  span->_freeList = start;
  --span->_useCount;
  // 如果发现回收一个之后Span的_useCount等于0说明Span切好分出去的所有小块定长内存都收回来了
  // 这时可以把这个Span回收到下一层PageCache中合并出更大页的Span
  if (span->_useCount == 0)
  {
    _spanLists[index].Erase(span);
    span->_freeList = nullptr;
    span->_next = nullptr;
    span->_prev = nullptr;
    //下面逻辑不再访问_spanList[index]桶的数据，所以可以暂时释放桶锁
    _spanLists[index].GetSpanListMutex().unlock();
    PageCache::GetInstance()->GetPageMutex().lock();
    PageCache::GetInstance()->ReleaseSpanToPageCache(span);
    PageCache::GetInstance()->GetPageMutex().unlock();
    _spanLists[index].GetSpanListMutex().lock();
  }
  start = next;
  }
  _spanLists[index].GetSpanListMutex().unlock();
}

PS：具体Span对象回收到PageCache合并成更大页的这个操作由页缓存的PageCache::ReleaseSpanToPageCache(Span* span)来完成，这是我们下面要讲的。

三. PageCache回收内存

1. 基本步骤

如果CentralCache释放回一个Span，则PageCache依次寻找这个Span的前一页页号和后一页页号中空闲的Span来合并，合并之后继续向前后寻找。这样就可以将切小的Span合并收缩成大的Span，减少外碎片。

2. Span类中的补充

CentralCache和PageCache的核心成员变量都是SpanList组成的哈希桶，它们每一个桶中都挂着很多Span，PageCache在回收一个Span时根据Span::_pageId拿到不属于这个Span的前一页的页号：_pageId - 1和不属于这个Span的后一页的页号：_pageId + Span的页数_n，然后根据页号我们可以拿到存储这个页的Span对象，如果这个Span在PageCache中的话就可以参与合并，而如果这个Span在CentralCache中的话说明还在使用中，不能参与合并。

现在的问题是如何确定已经拿到的Span对象是否能正在使用？能否使用Span中的Span::_useCount这个成员变量呢？即如果Span::_useCount等于0说明这个Span没有在被使用可以参与合并，反之不能参与合并。答案是这种判断方法不可取，试想可能存在如下情况：当多线程运行时页缓存通过PageCache::NewSpan(size_t k)返回给中心缓存一个全新未切分的k页Span对象，注意我们在上面在PageCache中的补充中有说到在NewSpan(…)函数中先映射好了k页Span和它所有页号的映射关系：

在CentralCache刚拿到这个k页Span、释放表锁后正欲对Span进行切分时，如果其它线程插刚好去PageCache中进行合并操作查找前后页时映射到这个还未来得及切分的k页Span，发现其_useCount等于0，导致本来已经属于CentralCache的k页Span被其他Span合并了到PageCache中，就此出现了线程不安全的问题：

最后正确的做法是直接在Span类的声明中增加一个bool类型的成员变量Span::_isUse，默认等于false表示这个Span对象没有在被使用：

加入了这个成员变量后，相应的我们也要更新CentralCache::GetOneSpan(...)，在从PageCache中拿到一个k页Span之后、释放表锁之前把这个k页Span的_isUse的值改为true表示这个Span已经属于CentralCache：

3. 页缓存拿到回收的Span对象后进行前后页的合并

对接上面CentralCache::ReleaseListToSpans(...)，该函数回收小块定长内存时检测到某个Span对象的_useCount等于0的话就把这个Span对象传给PageCache让其对这个Span进行前后页的合并：

具体合并Span的逻辑封装到PageCache::ReleaseSpanToPageCache(Span* span)这个函数里实现。下面我们说明合该如何去合并这个传入的Span对象：

PageCache在回收一个Span对象时根据Span::_pageId拿到不属于这个Span对象的前一页的页号：_pageId - 1和不属于这个Span对象的后一页的页号：_pageId + Span的页数_n，根据页号我们可以拿到存储前一页的prevSpan和存储后一页的nextSpan：

并不是说找到了前一页所属的prevSpan或后一页所属的nextSpan就能直接根Span合并的，还有以下两种情况不能合并：

找到了prevSpan或nextSpan，但是它们正在被使用。

找到了prevSpan或nextSpan，但是它们和Span的页数加起来超过了128页（即NPAGES - 1），超过了PageCache桶所能挂的SPan对象的范围。

下面是PageCache::ReleaseSpanToPageCache(Span* span)函数的具体实现：

// 对span前后的页，尝试进行合并，缓解外碎片问题
void PageCache::ReleaseSpanToPageCache(Span* span)
{
  assert(span);
  // 向前合并
  while (1)
  {
  PAGE_ID prevId = span->_pageId - 1;
  auto ret = _idSpanMap.find(prevId);
  // 前面的页号没有，不合并了
  if (ret == _idSpanMap.end())
  {
    break;
  }
  // 前面相邻页的span在使用，不合并了
  Span* prevSpan = ret->second;
  if (prevSpan->_isUse == true)
  {
    break;
  }
  // 合并出超过128页的span没办法管理，不合并了
  if (prevSpan->_n + span->_n > NPAGES-1)
  {
    break;
  }
  // 合并操作只需调整Span的起始页页号和它的页数即可
  // 合并完成后把之前PageCache中挂的prevSpan移除并delete
  span->_n += prevSpan->_n;
  span->_pageId = prevSpan->_pageId;
  _spanLists[prevSpan->_n].Erase(prevSpan);
  delete prevSpan;
  }
  // 向后合并
  while (1)
  {
  PAGE_ID nextId = span->_pageId + span->_n;
  auto ret = _idSpanMap.find(nextId);
  if (ret == _idSpanMap.end())
  {
    break;
  }
  Span* nextSpan = ret->second;
  if (nextSpan->_isUse == true)
  {
    break;
  }
  if (span->_n + nextSpan->_n > NPAGES - 1)
  {
    break;
  }
  span->_n += nextSpan->_n;
  _spanLists[nextSpan->_n].Erase(nextSpan);
  delete nextSpan;
  }
  // 前后都合并好了之后，把这个Span挂到PageCache对应页数的哈希桶中
  // 并处理好这个新Span首尾页的映射关系
  _spanLists[span->_n].PushFront(span);
  span->_isUse = false;
  _idSpanMap[span->_pageId] = span;
  _idSpanMap[span->_pageId + span->_n - 1] = span;
}