万字详解C++内存池：提高内存分配效率的利器（下）

整体控制在最多10%左右的内碎片浪费
内存大小          对齐数         桶下标
[1,128]         8byte对齐           freelist[0,16)
[128+1,1024]      16byte对齐          freelist[16,72)
[1024+1,8*1024]     128byte对齐       freelist[72,128)
[8*1024+1,64*1024]    1024byte对齐          freelist[128,184)
[64*1024+1,256*1024]  8*1024byte对齐      freelist[184,208)

//向CentralCache申请内存
void* ThreadCache::FetchFromCentralCache(size_t MemSize)
{
  //上层只申请了一块内存，ThreadCache也只向中心缓存要一块来供给上层，合情合理
  //但是ThreadCache也可以多申请几块（补充库存）
  //这样下次上层再向ThreadCache申请内存的时候，就能直接给上层分配，不用频繁向中心缓存申请了。
    //申请策略？慢增长
  size_t requestMemNum = min(_freeList[index].GetMaxUseNum(), SizeClass::RequestWay(MemSize));
}

//申请策略。计算实际向下层申请的内存数量
  //参数：申请的内存大小
  static size_t RequestWay(size_t MemSize)
  {
    assert(MemSize > 0);
    //算法：固定值 / 申请的内存大小
    //分母越大，结果越小
    //申请的内存越小，一次性可以多要一些
    //申请的内存越大，一次性要少点，否则对系统负担大
    size_t ret = MaxMemSize / MemSize;
    if (ret < 2) //下限
    {
      ret = 2;
    }
    if (ret > 512) //上限
    {
      ret = 512;
    }
    return ret;
  }

//释放内存
//ThreadCache桶链太长的话，应当回收一部分给CentralCache
//太长？长短的标准是什么？
//定义使用频数成员变量，当长度 > 使用频数的时候，就可以考虑回收一部分了：回收使用频数个

void* mem;

int main()
{
  //00000001 00001001 00001001 00001001
  //小端： 09 09 09 01 
  unsigned int i = 0x01090909;
  cout << i << endl << endl;
  cout << 0x09 << endl;
  char* p = (char*)&i;
  cout << "*p = " << (int)* p << endl << endl;  //9;
  //这里需要在打印的时候再把值强转成int类型，否则ASCII中，9对应的字符是'\t'
  //char类型把他当'\t'打印了，运行结果显示什么也没有。
  cout << 0x0909 << endl;
  wchar_t* q = (wchar_t*)&i;
  cout << "*q = " << (int)*q << endl << endl;
  unsigned int* r = &i;
  cout << "*r = " << *r << endl;
}

//已知void* m1指向一段内存,void* m2指向另一段内存
*(int*)(m1) = m2;

*(void**)(m1) = m2;

//从CentralCache的自由链表中取出一个Span
Span* CentralCache::GetOneSpan(SpanList&list, size_t MemSize)
{
    //....
    //若桶链中没有Span或所有Span都没有剩余内存
    //向PageCache申请Span
  //考虑到ThreadCache向CentralCache要内存并不是需要多少拿多少，而是多拿
  //如果原本CentralCache中有Span可用，有多少给多少，不一定够，尽量满足也就罢了
  //既然调到了这个函数，就说明CentralCache中没有Span，要再找PageCache申请Span
  //那既然要申请，那就理所当然申请一定能够满足ThreadCache的内存数
  //那就去计算这样大小的内存，上层实际会申请会申请多少个，转换成页是多少页？
  //再按照这样的页数报给PageCache去申请
    size_t pageNum = SizeClass::NumberOfPages(MemSize);
  //PageCache使用的是大锁，锁住整个PageCache
  PageCache::GetPageCache()->PageCacheLock();
  Span* newSpan = PageCache::GetPageCache()->GetSpanToUpper(pageNum);
  PageCache::GetPageCache()->PageCacheUnlock();
  assert(newSpan);
  // 为什么申请完Span就解锁了？切割不需要加锁吗？
  // 切割不需要加锁，因为切割是把新申请的Span切割，这个newSpan指针是只属于当前线程的局部变量
  // 也就是说只有当前线程能够看到这个Span。不存在线程安全问题，因此切割的时候不需要加锁。
  // 这样就能提高效率，如果有其他的CentralCache桶中无Span，也需要申请，但是PageCache只有一把大锁
  // 如果切割的时候没用到却没有释放掉，其他线程就只能阻塞了。
}

//参数：上层要拿k页
Span* PageCache::GetSpanToUpper(size_t k)
{
  assert(k > 0);
  //申请页数 > 128，直接向堆申请
  if (k > NPage - 1)
  {
    //Span* p = (Span*)SystemAlloc(k); //不能这么写
    //栈上的局部变量,出了作用域就销毁了
    //但是我们在释放的时候，还要用Span来释放，所以必须在堆上开Span避免被自动销毁
    void* ptr = SystemAlloc(k);
    //Span* span = new Span; 
    Span* span = _spanPool.New(); 
    span->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
    span->_n = k;
    span->_isUse = true;
    _pageMapSpan[span->_pageId] = span;
    return span;
  }
  else
  {
    //页数 = 桶下标
    //到对应桶中拿Span
    if (!_pclist[k].Empty())
    {
      Span* kSpan = _pclist[k].PopFront();
      kSpan->_isUse = true;
      for (int i = 0; i < kSpan->_n; ++i)
      {
        _pageMapSpan[kSpan->_pageId + i] = kSpan;
      }
      return kSpan;
    }
    //走到这里说明对应页的桶中无Span，往下面的桶里找
    size_t n = k + 1;
    while (n < NPage)
    {
      //往下找，找到了非空页桶，取出其中的span拿来切割成pages页 和 i - pages页
      if (!_pclist[n].Empty())
      {
        Span* nPages = nPages = _pclist[n].PopFront();
        //Span* kPages = new Span;
        Span* kPages = _spanPool.New();
        //切割成两部分
        //前一部分的页号就是原本的页号 不需要改动
        kPages->_pageId = nPages->_pageId;
        kPages->_n = k;
        nPages->_pageId += k; //后一部分的起始页号 = 原本的起始页号 + 前一部分的页数
        nPages->_n -= k; //切割后的页数要改一下
        //建立id和Span的映射，方便查找
        for (PAGE_ID i = 0; i < kPages->_n; ++i)
        {
          _pageMapSpan[kPages->_pageId + i] = kPages;
        }
        //没有向上交付的页，即nPages的首尾页映射一下即可
        //kPage要把Span中的每一页都映射是因为CentralCache中没有页的概念
        //对于CentralCache而言，它拿到的就是一个Span，然后把这个Span不断切割成等量小块内存
        //因此中间页的内存也会被切割，和大Span在逻辑上分离。
        // 例如： 某Span有 100 101 102 三个页
        //假设我们CentralCache层也只映射首尾页，当某个内存需要回收,那它首先需要根据地址找到它所在的页
        //如果它所在的页是101页，当我们拿着这个页去映射它对应的Span时，就会发现映射不到Span
        //因为我们只映射了首尾：100 102
        //但nPages不同，nPages映射的目的是为了在回收内存的时候去合并更大的页，
        //因此就要找某页的前后页，如果它的前后页也没有被使用，那么它们就能合并
        //例如： 页号为200的Span被回收，并尝试合并
        //它会向前找页号199的Span（Span中可能有多页，199是该Span的最后一页）， 向后找页号201的Span（201是该Span的第一页）,看它们是否被使用
        //但首尾位置是相对的，我们无法预知
        //就像如果199所在的Span有3页：197 198 199
        //对于200来说，它通过且只能通过199页去找所在的它所在Span是否被使用,
        //因为程序无法确定198是不是和199在同一个Span,如果不是，那么200要合并的是199所在的Span
        //而不是198所在的Span,因为200的Span只和199所在的Span连续
        //但对于196来说，他需要的却是197而不是199
        //因此相对位置无法确定，首尾页都必须映射。
        //并且上述例子又再次印证了为什么nPage不需要映射中间页
        //就像200不能够使用198去映射一样，中间页在Span中是没有被切割的，并且在这一层使用中间页映射是不合逻辑的
        _pageMapSpan[nPages->_pageId] = nPages;
        _pageMapSpan[nPages->_pageId + nPages->_n - 1] = nPages; //最后一页的页号 = _pageId + n - 1
        //将 i - page页的Span插入相应的页桶中, 然后将page页的Span交付上层。
        _pclist[nPages->_n].PushFront(nPages);
        //PushVmap();
        return kPages;
      }
      n++;
    }
    //走到这里，说明直到最后一个桶都没找到未分配的Span
    //需要直接向堆申请内存页。直接申请一个最大内存页:128页
    //Span* newSpan = new Span;
    Span* newSpan = _spanPool.New();
    void* ptr = SystemAlloc(NPage - 1);
    newSpan->_pageId = (PAGE_ID)ptr >> 13; // 页号 = 地址 / 8k
    newSpan->_n = NPage - 1;
    //链接到128页对应的桶
    _pclist[newSpan->_n].PushFront(newSpan);
    return GetSpanToUpper(k);  //再调一次该函数，自动完成切割并向上交付
  }
}