一. 申请内存流程梳理

二. 申请内存完整代码

1. Common.h

该头文件中包含公共的数据结构、方法、常量等。

#pragma once
#include <mutex>
#include <thread>
#include <iostream>
#include <assert.h>
#include <algorithm>
using std::cout;
using std::endl;
static const size_t NPAGES = 129;   // PageCache可申请的最大页数
static const size_t PAGE_SHIFT = 13;  // 通过移位运算计算页号和页的起始地址
static const size_t NFREELIST = 208;        // 小块定长内存自由链表桶的数量
static const size_t MAX_BYTES = 256 * 1024; // ThreadCache可申请的最大内存空间
// 条件编译不同平台、系统的页号类型
#ifdef _WIN64
  typedef unsigned long long PAGE_ID;
#elif _WIN32
  typedef size_t PAGE_ID;
#else 
  //Linux
#endif
// 条件编译不同系统的系统头文件
#ifdef _WIN32
  #include <windows.h>
#else
  // Linux
#endif
// 条件编译不同系统到堆上以页为单位申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
  void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
  // linux下brk mmap等
#endif
  if (ptr == nullptr)
  throw std::bad_alloc();
  return ptr;
}
// 返回传入空间的头4个或8个字节内容的引用
static inline void*& NextObj(void* obj)
{
  assert(obj);
  return *(void**)obj;
}
// 管理切分好的小块定长内存的自由链表
class FreeList
{
public:
  // 头插一个小块定长内存
  void PushFront(void* obj)
  {
  assert(obj);
  NextObj(obj) = _freeList;
  _freeList = obj;
  ++_size;
  }
  // 头删一个小块定长内存
  void* PopFront()
  {
  assert(!Empty());
  void* obj = _freeList;
  _freeList = NextObj(obj);
  --_size;
  return obj;
  }
  // 头插批量小块定长内存
  void PushRangeFront(void* start, void* end, size_t n)
  {
  assert(start);
  assert(end);
  assert(n > 0);
  NextObj(end) = _freeList;
  _freeList = start;
  _size += n;
  }
  // 判断自由链表是否为空
  bool Empty()
  {
  return _size == 0;
  }
  // 获取该链表像中心缓存申请内存时的慢启动调节值
  size_t GetAdjustSize()
  {
  return adjustSize;
  }
private:
  size_t _size = 0;     // 小块定长内存的数数量
  size_t adjustSize = 1;     // 向中心缓存申请内存的慢启动调节值
  void* _freeList = nullptr; // 存储小块定长内存的自由链表
};
// 计算传入对象大小和小块定长内存的对齐映射规则
class SizeClass
{
  // 整体控制在最多10%左右的内碎片浪费
  // [1,128]        8byte对齐      freelists[0,16)
  // [128+1,1024]       16byte对齐      freelists[16,72)
  // [1024+1,8*1024]      128byte对齐      freelists[72,128)
  // [8*1024+1,64*1024]    1024byte对齐     freelists[128,184)
  // [64*1024+1,256*1024]  8*1024byte对齐   freelists[184,208)
public:
  // 计算对齐后得到的定长块大小
  static inline size_t RoundUp(size_t bytes)
  {
  if (bytes <= 128)
  {
    return _RoundUp(bytes, 8);
  }
  else if (bytes <= 1024)
  {
    return _RoundUp(bytes, 16);
  }
  else if (bytes <= 8 * 1024)
  {
    return _RoundUp(bytes, 128);
  }
  else if (bytes <= 64 * 1024)
  {
    return _RoundUp(bytes, 1024);
  }
  else if (bytes <= 256 * 1024)
  {
    return _RoundUp(bytes, 8 * 1024);
  }
  else
  {
    assert("ThreadCache over 256k\n");
    return -1;
  }
  }
  // 计算映射到哪一个自由链表桶
  static inline size_t Index(size_t bytes)
  {
  // 记录每一个对齐区间有多少个桶
  static int group_array[4] = { 16, 56, 56, 56 };
  // 根据传入的对象大小映射得到自由链表桶对应的下标
  if (bytes <= 128) {
    return _Index(bytes, 3);
  }
  else if (bytes <= 1024) {
    return _Index(bytes - 128, 4) + group_array[0];
  }
  else if (bytes <= 8 * 1024) {
    return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
  }
  else if (bytes <= 64 * 1024) {
    return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
  }
  else if (bytes <= 256 * 1024) {
    return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
  }
  else {
    assert("ThreadCache over 256k\n");
    return -1;
  }
  }
  // ThreadCache一次从中心缓存批量获取小块定长内存数量的上、下限
  static size_t LimitSize(size_t alignBytes)
  {
  assert(alignBytes != 0);
  // [2, 512]，一次批量移动多少个对象的(慢启动)上限值
  // 大对象（最大256KB）一次批量下限为2个
  // 小对象（最小8字节）一次批量上限为512个
  size_t num = MAX_BYTES / alignBytes;
  if (num < 2)
    num = 2;
  if (num > 512)
    num = 512;
  return num;
  }
  // 计算一次向系统获取几个页合适
  // 单个对象 8byte --- 分给CentralCache一个1页的Span
  // ...
  // 单个对象 256KB --- 分给CentralCache一个64页的Span
  static size_t NumMovePage(size_t alignBytes)
  {
  size_t num = LimitSize(alignBytes);
  size_t npage = num * alignBytes;
  npage >>= PAGE_SHIFT;
  if (npage == 0)
    npage = 1;
  return npage;
  }
private:
  static inline size_t _RoundUp(size_t bytes, size_t alignNum)
  {
  return ((bytes + alignNum - 1) & ~(alignNum - 1));
  }
  static inline size_t _Index(size_t bytes, size_t align_shift)
  {
  return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
  }
};
// Span管理以页为单位一个的大块跨度内存
struct Span
{
  size_t _n = 0;       // 页的数量
  PAGE_ID _pageId = 0; // 大块跨度内存起始页的页号
  Span* _next = nullptr; // 指向双向链表中前一个大块跨度内存
  Span* _prev = nullptr; // 指向双向链表中后一个大块跨度内存
  size_t _useCount = 0;     // 被分配给ThreadCache的小块定长内存计数
  void* _freeList = nullptr;// 存储切好的小块定长内存的自由链表
};
// 管理span的带头双向循环链表
class SpanList
{
public:
  // 构造函数中new一个哨兵位的头结点
  SpanList()
  {
  _head = new Span;
  _head->_prev = _head;
  _head->_next = _head;
  }
  // 在pos位置插入一个新的大块跨度内存
  void Insert(Span* pos, Span* newSpan)
  {
  assert(pos);
  assert(newSpan);
  // 1、记录前一个节点
  Span* prev = pos->_prev;
  // 2、newSpan插入到中间位置：prev newSpan pos
  prev->_next = newSpan;
  newSpan->_prev = prev;
  newSpan->_next = pos;
  pos->_prev = newSpan;
  }
  // 移除pos位置的一个大块跨度内存
  void Erase(Span* pos)
  {
  assert(pos);
  assert(pos != _head); // 不能删除哨兵位的头结点 
  // 1、拿到pos位置的前后节点
  Span* prev = pos->_prev;
  Span* next = pos->_next;
  // 2、连接前后节点，pos不用delete这里只负责把它移出链表，外部会还对pos做处理
  prev->_next = next;
  next->_prev = prev;
  }
  // 获取第一个Span
  Span* Begin()
  {
  return _head->_next;
  }
  // 获取哨兵位头结点
  Span* End()
  {
  return _head;
  }
  // 判空
  bool Empty()
  {
  return Begin() == _head;
  }
  // 头删一个span对象并返回给外部
  Span* PopFront()
  {
  assert(!Empty());
  Span* ret = Begin();
  Erase(Begin());
  return ret;
  }
  // 头插一个span对象
  void PushFront(Span* span)
  {
  assert(span);
  Insert(Begin(), span);
  }
  // 获取桶锁
  std::mutex& GetSpanListMutex()
  {
  return _mtx;
  }
private:
  Span* _head;  // 哨兵位的头结点
  std::mutex _mtx; // 桶锁
};

2. ThreadCache相关文件

ThreadCache.h：包含线程缓存类的声明和创建线程自己的TLS。
#pragma once 
#include "Common.h"
// ThreadCache本质是由一个哈希映射的已切分好的小块定长内存组成的自由链表集合
class ThreadCache
{
public:
  // 申请一个小块定长内存
  void* Allocate(size_t bytes);
  // 释放一个小块定长内存
  void Deallocate(void* ptr, size_t bytes);
private:
  // 从中心缓存获取批量小块定长内存，并返回其中一个
  void* FetchFromCentralCache(size_t index, size_t alignBytes);
  FreeList _freeLists[NFREELIST]; // 哈希桶
};
// TLS thread local storage
static _declspec(thread) ThreadCache* pTLSThreadCache = nullptr;

ThreadCache.cpp：包含线程缓存成员函数的实现。

#include "ThreadCache.h"
#include "CentralCache.h"
// 申请一个小块定长内存
void* ThreadCache::Allocate(size_t bytes)
{
  // ThreadCache只能申请小于等于256KB的对象空间
  assert(bytes <= MAX_BYTES);
  // 1、确定对齐后的小块定长内存大小以及它映射到那个自由链表桶
  size_t index = SizeClass::Index(bytes);
  size_t alignBytes = SizeClass::RoundUp(bytes);
  // 2、如果自由链表桶不空的话，把第一个小块定长内存取出来
  //    如果桶中没有小块定长内存，就到CentralCache中去批量申请
  if (!_freeLists[index].Empty())
  {
  return _freeLists[index].PopFront();
  }
  else
  {
  return FetchFromCentralCache(index, alignBytes);
  }
}
// 释放一个小块定长内存
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);
}
// 从中心缓存获取“一批”小块定长内存，并返回给外部“一块”小块定长内存
void* ThreadCache::FetchFromCentralCache(size_t index, size_t alignBytes)
{
  // 慢启动反馈调节算法
  // 1、最开始不会一次向CentralCache批量太多，因为要太多了可能用不完
  // 2、每次批发的数量逐渐增多，直到上限
  // 3、alignBytes越小，一次向CentralCache要的batchNum就越大
  // 4、alignBytes越大，一次向CentralCache要的batchNum就越小
  assert(index >= 0);
  assert(alignBytes >= 8);
  // 1、计算需要向CentralCache申请的小块定长内存的数量
  size_t batchNum = min(_freeLists[index].GetAdjustSize(), SizeClass::LimitSize(alignBytes));
  if (_freeLists[index].GetAdjustSize() == batchNum)
  {
  _freeLists[index].GetAdjustSize() += 1;
  }
  // 2、传入输出型参数向CentralCache申请批量小块定长内存
  void* begin = nullptr;
  void* end = nullptr;
  size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(begin, end, batchNum, alignBytes);
  // 3、返回给外部第一个小块定长内存，其它的挂到自由链表桶中
  assert(actualNum > 0);
  if (actualNum == 1)
  {
  assert(begin == end);
  return begin;
  }
  else
  {
  _freeLists[index].PushRangeFront(NextObj(begin), end, actualNum-1);
  return begin;
  }
}

3. CentralCache相关文件

CentralCache.h：包含中心缓存类的声明。

#pragma once
#include "Common.h"
// 饿汉的单例模式
class CentralCache
{
public:
  // 返回CentralCache的单例对象
  static CentralCache* GetInstance()
  {
  return &_sInst;
  }
  // 从中心缓存获取一定数量的小块定长内存给ThreadCache
  size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t alignBytes);
private:
  // 从特定的SpanList中获取一个非空的span
  Span* GetOneSpan(SpanList& list, size_t alignBytes);
  SpanList _spanLists[NFREELIST];// 哈希桶
private:
  CentralCache()
  {}
  CentralCache(const CentralCache&) = delete;
  static CentralCache _sInst;
};

CentralCache.cpp：包含中心缓存类的定义。

#include "PageCache.h"
#include "CentralCache.h"
CentralCache CentralCache::_sInst;
// 从特定的SpanList中获取一个非空的Span
Span* CentralCache::GetOneSpan(SpanList& list, size_t alignBytes)
{
  assert(alignBytes >= 8);
  // 1、先到链表中找非空的Span
  Span* it = list.Begin();
  while (it != list.End())
  {
  if (it->_freeList != nullptr)
  {
    return it;
  }
  else
  {
    it = it->_next;
  }
  }
  // 2、走到这里说明没有list中没有非空的Span，那么就需要到PageCache申请特定页大小的Span
  // 这里可以释放桶锁，后面逻辑不再访问该桶
  list.GetSpanListMutex().unlock();
  // 申请PageCache的表锁，到PageCache中申请特定页的Span过来
  PageCache::GetInstance()->GetPageMutex().lock();
  Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(alignBytes));
  PageCache::GetInstance()->GetPageMutex().unlock();
  // 把从PageCache申请到的Span切成一个个的小块定长内存
  char* start = (char*)(span->_pageId << PAGE_SHIFT);// 起始页地址
  size_t bytes = span->_n << PAGE_SHIFT;// 连续页的字节数
  char* end = start + bytes;// 最后一页的最后地址
  span->_freeList = start;
  start += alignBytes;
  void* tail = span->_freeList;
  while (start < end)
  {
  NextObj(tail) = start;
  tail = start;
  start += alignBytes;
  }
  NextObj(tail) = nullptr;
  // 3、重新申请桶锁，把切好的Span挂到桶上
  list.GetSpanListMutex().lock();
  list.PushFront(span);
  return span;
}
// 从中心缓存获取一定数量的小块定长内存给ThreadCache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t alignBytes)
{
  assert(batchNum > 0);
  assert(alignBytes >= 8);
  size_t index = SizeClass::Index(alignBytes);
  _spanLists[index].GetSpanListMutex().lock();
  // 从span中获取batchNum个小块定长内存
  // 如果不够batchNum个，有多少拿多少
  // 拿完后end存储的下一个节点要为置为空，span的自由链表也要对应更新
  Span* span = GetOneSpan(_spanLists[index], alignBytes);
  assert(span);
  assert(span->_freeList);
  start = span->_freeList;
  end = span->_freeList;
  size_t actualNum = 1;
  while (actualNum < batchNum && NextObj(end))
  {
  ++actualNum;
  end = NextObj(end);
  }
  span->_freeList = NextObj(end);
  NextObj(end) = nullptr;
  span->_useCount += actualNum;
  _spanLists[index].GetSpanListMutex().unlock();
  return actualNum;
}

4. PageCache相关文件

PageCache.h：包含页缓存的声明。

#pragma once
#include "Common.h"
// 饿汉的单例模式
class PageCache
{
public:
  // 返回PageCache的单例对象
  static PageCache* GetInstance()
  {
  return &_sInst;
  }
  // 返回给CentralCache一个k页的Span
  Span* NewSpan(size_t k);
  // 获取表锁
  std::mutex& GetPageMutex();
private:
  std::mutex _pageMtx;// 表锁
  SpanList _spanLists[NPAGES];// 存储未切分的span
private:
  PageCache()
  {}
  PageCache(const PageCache&) = delete;
  static PageCache _sInst;
};

PageCache.cpp：包含页缓存的定义。

#include "PageCache.h"
PageCache PageCache::_sInst;
std::mutex& PageCache::GetPageMutex()
{
  return _pageMtx;
}
// 返回给CentralCache一个k页的Span
Span* PageCache::NewSpan(size_t k)
{
  assert(k > 0 && k < NPAGES);
  // 1、根据k直接定址映射，看对应SpanList桶中是否挂有Span
  if (!_spanLists[k].Empty())
  {
  return _spanLists[k].PopFront();
  }
  // 2、走到这里说明定址映射的桶中没有Span，那么看更大页的桶是否有Span
  for (size_t n = k + 1; n < NPAGES; ++n)
  {
  // 更大页的桶有Span的话就对其进行切分
  if (!_spanLists[n].Empty())
  {
    Span* kSpan = new Span();
    Span* nSpan = _spanLists[n].PopFront();
    kSpan->_n = k;
    kSpan->_pageId = nSpan->_pageId;
    nSpan->_n -= k;
    nSpan->_pageId += k;
    _spanLists[nSpan->_n].PushFront(nSpan);
    return kSpan;
  }
  }
  // 3、走到这一步说明整个PageCache中找不到一个>=k页的Span，这时向堆申请一个128页的Span
  Span* bigSpan = new Span;
  void* ptr = SystemAlloc(NPAGES - 1);
  bigSpan->_n = NPAGES - 1;
  bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
  _spanLists[NPAGES - 1].PushFront(bigSpan);
  return NewSpan(k);
}

5. ConcurrentAlloc.h

该头文件中包含线程申请、释放小于128KB对象空间的接口。

#pragma once
#include "Common.h"
#include "ThreadCache.h"
static void* ConcurrentAlloc(size_t bytes)
{
  // 通过TLS 每个线程无锁的获取自己的专属的ThreadCache对象
  if (pTLSThreadCache == nullptr)
  {
  pTLSThreadCache = new ThreadCache;
  }
  return pTLSThreadCache->Allocate(bytes);
}
static void ConcurrentFree(void* ptr, size_t bytes)
{
  assert(pTLSThreadCache);
  pTLSThreadCache->Deallocate(ptr, bytes);
}

三. 单线程申请内存联调

1. 测试一

在主线程中执行如下测试代码：

主线程从ThreadCache中申请五个8字节的小块定长内存。

按照申请顺序打印申请出来的每个小块定长内存的起始地址。

void TestConcurrentAlloc1()
{
  // 1、从ThreadCache中申请五个8字节的小块定长内存
  void* p1 = ConcurrentAlloc(6);
  void* p2 = ConcurrentAlloc(8);
  void* p3 = ConcurrentAlloc(1);
  void* p4 = ConcurrentAlloc(7);
  void* p5 = ConcurrentAlloc(8);
  // 2、按照申请顺序打印每个小块定长内存的起始地址
  cout << p1 << endl;
  cout << p2 << endl;
  cout << p3 << endl;
  cout << p4 << endl;
  cout << p5 << endl;
}

接下来我们从第一步p1申请6字节的对象空间开始执行：

首先主线程无锁的获取自己的专属的ThreadCache对象，然后调用ThreadCache::Allocate(...)函数到ThreadCache中申请一个6字节的对象空间：

进入ThreadCache::Allocate(...)后，检测到我们申请的对象空间大小是6字节，对齐后分配给我们的小块定长内存大小是8字节，然后到ThreadCache的0号桶中去找，发现里面没有小块定长内存所以调用ThreadCache::FetchFromCentralCache(...)函数去CentralCache中批量申请8字节的小块定长内存，申请到了就返回一个给Allocate()函数，其它挂到线程缓存的0号自由链表桶中：

通过慢启动反馈调节算法，ThreadCache存储8字节大小的小块定长内存的0号自由链表桶一次向CentralCache要的小块定长内存数量上限为512个，但第一次只能申请到一个，之后每次该自由链表桶申请时加一个直到最大数量。计算好需要申请的数量之后调用CentralCache::FetchRangeObj(...)函数到CentralCache中计划拿batchNum个小块定长内存过来：

进入CentralCache::FetchRangeObj(...)后，内部继续调用CentralCache::GetOneSpan(...)去中心缓存相同下标的SpanList桶拿一个非空、已切好的Span出来，拿到后把里面的小块定长内存对象批量拨给ThreadCache，不够batchNum的话也无所谓，有多少给多少就是了：

进入CentralCache::GetOneSpan(...)后发现下标为index的中心缓存桶中没有Span对象，这时调用PageCache::NewSpan(...)去页缓存中申请特定页大小、未切分的Span对象过来，申请到之后回到GetOneSpan(…)函数对这个新的Span进行切分并挂到中心缓存下标为index的SpanList桶中，最后把这个Span返回给CentralCache::FetchRangeObj(...)函数：

至于需要向页缓存申请多少页的Span这个由SizeClass::NumMovePage(...)函数决定，要申请的小块定长内存是8字节，经过计算得到只需申请一页的Span即可：

主逻辑进入到PageCache::NewSpan(...)后，一开始页缓存所有桶都没有Span，这时只能去找系统的堆申请一个128页的大块Span过来，申请到之后递归调用PageCache::NewSpan(...)完成对这个128页大块Span的切分：

PS：在递归调用之前我们可以来验证一下新申请的128页大块Span记录的起始页页号和内存地址之间的转换关系是否正确：

接着上一步递归再次进入PageCache::NewSpan(...)函数，这次和第一次不同了，页缓冲的第128号桶上挂有Span，我们把这个Span切成一个1页的Span和一个127页的Span，1页Span返回给给CentralCache::GetOneSpan(...)，127页Span挂到页缓冲的_spanList[127]桶上：

剩下的代码就不在调试了，我们直接编译运行得到最终结果：

2. 测试二

这次我们一直申请8字节的小块定长内存，第一次从PageCache哪里申请了一页的Span，它可以被切成1024个小块定长内存，我们把这些小块定长内存申请完之后再次申请8字节小块定长内存就需要重新在PageCache申请一个1页的Span，下面测试PageCache再次申请一个1页的Span是否正常运行：

void TestConcurrentAlloc2()
{
  // 消耗完第一次从PageCache哪里申请的一页Span
  for (size_t i = 0; i < 1024; ++i)
  {
  void* p1 = ConcurrentAlloc(6);
  cout << p1 << endl;
  }
  // 重新从PageCache哪里申请一页的Span
  void* p2 = ConcurrentAlloc(8);
  cout << p2 << endl;
}

编译运行，128页的Span分配没问题：

【高并发内存池】第五篇：申请内存过程调通