page cache
- 1 page cache的框架
- 2 central cache从page cache申请n页span的过程
- 3 page cache 的结构
- 3.1 page cache类框架
- 3.2 central cache向page cache申请span
- 3.3 获取k页的span
page cache的结构和central cache是一样的，都是哈希桶的结构，并且挂载的都是span。但是不同的是，central cache为thread cache服务，分配的是一个个freeList，所以需要和thread cache的映射规则一样，page cache为central cache服务，分配的是一个个span。所以page cache挂载的span不会进行切分。
1 page cache的框架
下面的图中，左边是central cache的结构，右边是page cache的结构。
我们假设page cache的桶为128页大小（这个可以根据实际情况更改），为了让桶号和页号对应起来，我们让0号桶为空，所以page cache的哈希桶个数要设置为129.
//page cache中哈希桶的个数
static const size_t NPAGES = 129;
2 central cache从page cache申请n页span的过程
下面是page cache的结构
当central cache向page cache申请n页的span时，page cache的做法如下:
3 page cache 的结构
1. page cache是否需要加锁？
需要。因为每个线程都拥有一份
thread cache，当thread cache中没有内存时，会向central cache中要。如果多个thread cache同时访问central cache的一个桶时，就会出现线程安全问题，就需要加桶锁。但是如果多个thread cache访问不同的central cache是不会出现线程安全问题的，也不需要加锁。而如果此时多个central cache同时访问page cache就会出现线程安全问题。
2. 那page cache加的锁是桶锁吗？
不是
central cache的分配方式是每个桶独立的，所以可以使用桶锁。而根据上面描述的page cache的分配方式，访问第n号桶很可能是从n + 1号桶中拿到span，分配给central cache后，再将剩余的span挂载到1号桶中。这种分配方式会涉及到多个桶，如果使用桶锁，锁住其中一个桶，其他的桶就无法进行协同了。所以page cache加的是一把大锁，能将整个page cache锁住。
4.page cache需要设计单例模式吗？
需要。整个进程中能有一个
page cache，所以page cache也需要设计一个单例模式。
3.1 page cache类框架
//单例模式
class PageCache
{
public://提供一个全局访问点static PageCache* GetInstance(){return &_sInst;}
private://static const size_t NPAGES = 129;SpanList _spanLists[NPAGES]; std::mutex _pageMtx; //大锁
private:PageCache() //构造函数私有{}PageCache(const PageCache&) = delete; //防拷贝static PageCache _sInst;
};3.2 central cache向page cache申请span
当thread cache向central cache申请span的时候，会从central cache中获取一个非空的span,在上篇文章中的实现是这样的：
Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{// 查看当前的spanlist中是否有还有未分配对象的spanSpan* it = list.Begin();while (it != list.End()){if (it->_freeList != nullptr){return it;}else{it = it->_next;}}// 先把central cache的桶锁解掉，这样如果其他线程释放内存对象回来，不会阻塞list._mtx.unlock();return span;
}
但是上篇文章没有考虑如果central cache中没有span了该怎么办。
当central cache中没有span了该怎么办？
需要向
page cache申请
central cache如何向page cache申请span?
1.计算出
thread cache一次向central cache申请的freeList的个数num
2. 将freeList的个数num和thread cache申请的size字节相乘，计算出要申请的总字节数npage
3. 将npage除以页的大小,最终得到central cache要向page cache申请多少个页。不满1页按1页算。
static size_t NumMovePage(size_t size){//计算thread cache找central cache要的freeList的个数size_t num = NumMoveSize(size);//计算申请的总的字节数size_t npage = num*size;//计算向page cache申请的总的页数npage >>= PAGE_SHIFT;//不满1页按1页算if (npage == 0)npage = 1;return npage;}
PAGE_SHIFT表示页的大小，这里为13，因为2<sup>13</sup> = 8KB
static const size_t PAGE_SHIFT = 13;
当central cache从page cache中申请到span之后，还需要将span进行切分，切分成符合大小的freeList挂在span下面。
central cache是如何进行切分的？
1.计算
span的大块内存的起始地址start：span的起始页号乘以一页的大小即可得到这个span的起始地址
2.计算span的大小（字节数）bytes：span的页数乘以一页的大小
3.计算span的结束位置的地址end：start + bytes
4.将span切分为size大小，全部尾插到原来的span->freeList后面。具体过程看下图。
Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{// 查看当前的spanlist中是否有还有未分配对象的spanSpan* it = list.Begin();while (it != list.End()){if (it->_freeList != nullptr){return it;}else{it = it->_next;}}// 先把central cache的桶锁解掉，这样如果其他线程释放内存对象回来，不会阻塞list._mtx.unlock();// 走到这里说没有空闲span了，只能找page cache要PageCache::GetInstance()->_pageMtx.lock();Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(size));span->_isUse = true;span->_objSize = size;PageCache::GetInstance()->_pageMtx.unlock();// 对获取span进行切分，不需要加锁，因为这会其他线程访问不到这个span// 计算span的大块内存的起始地址和大块内存的大小(字节数)char* start = (char*)(span->_pageId << PAGE_SHIFT);size_t bytes = span->_n << PAGE_SHIFT;char* end = start + bytes;// 把大块内存切成自由链表链接起来// 1、先切一块下来去做头，方便尾插span->_freeList = start; start += size; void* tail = span->_freeList; int i = 1;while (start < end){++i;NextObj(tail) = start; //相当于tail->next = starttail = NextObj(tail); // tail = start;start += size;}NextObj(tail) = nullptr;// 切好span以后，需要把span挂到桶里面去的时候，再加锁list._mtx.lock();list.PushFront(span);return span;
}
3.3 获取k页的span
Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(size));
上面是GetOneSpan函数中用到的从page cache中拿k页大小的span的调用过程。
当central cache向page cache申请一个k页的span时，如果page cache中有k页的span，就直接删除然后给central cache就行了，如果没有，就要去堆中申请一个128页大小的span了。
回顾之前central cache向page cache申请内存的过程。
当central cache向page cache申请一个k页大小的span时，由于page cache是直接映射，所以只需要去第k号桶中找是否有span就行了。如果没有，就去k + 1，k + 2…中找，直到找到第128号桶都没有时，再去堆中申请。
当page cache向堆中申请128页大小的内存时，得到的是128页内存的起始地址，我们需要将这份起始地址转换为对应的页号，也就是将起始地址除以1页的大小。
//获取一个k页的span
Span* PageCache::NewSpan(size_t k)
{assert(k > 0 && k < NPAGES);//先检查第k个桶里面有没有spanif (!_spanLists[k].Empty()){return _spanLists[k].PopFront();}//检查一下后面的桶里面有没有span，如果有可以将其进行切分for (size_t i = k + 1; i < NPAGES; i++){if (!_spanLists[i].Empty()){Span* nSpan = _spanLists[i].PopFront();Span* kSpan = new Span;//在nSpan的头部切k页下来kSpan->_pageId = nSpan->_pageId;kSpan->_n = k;nSpan->_pageId += k;nSpan->_n -= k;//将剩下的挂到对应映射的位置_spanLists[nSpan->_n].PushFront(nSpan);return kSpan;}}//走到这里说明后面没有大页的span了，这时就向堆申请一个128页的spanSpan* bigSpan = new Span;void* ptr = SystemAlloc(NPAGES - 1);bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;bigSpan->_n = NPAGES - 1;_spanLists[bigSpan->_n].PushFront(bigSpan);//尽量避免代码重复，递归调用自己return NewSpan(k);
}
为什么要递归调用？
因为
page cache向堆申请了128页大小的内存，需要将其切分成k页的span和128-k页的span。本来需要编写切分的代码，但是为了避免写重复的代码，就再递归调用该函数，后面会自行切分的。
当central cache向page cache申请内存时，central cache对应的哈希桶是处于加锁的状态的，那在访问page cache之前我们应不应该把central cache对应的桶锁解掉呢？
这里建议在访问
page cache前，先把central cache对应的桶锁解掉。虽然此时central cache的这个桶当中是没有内存供其他thread cache申请的，但thread cache除了申请内存还会释放内存，如果在访问page cache前将central cache对应的桶锁解掉，那么此时当其他thread cache想要归还内存到central cache的这个桶时就不会被阻塞。
因此在调用
NewSpan函数之前，我们需要先将central cache对应的桶锁解掉，然后再将page cache的大锁加上，当申请到k页的span后，我们需要将page cache的大锁解掉，但此时我们不需要立刻获取到central cache中对应的桶锁。因为central cache拿到k页的span后还会对其进行切分操作，因此我们可以在span切好后需要将其挂到central cache对应的桶上时，再获取对应的桶锁。
这里为了让代码清晰一点，只写出了加锁和解锁的逻辑，我们只需要将这些逻辑添加到之前实现的
GetOneSpan函数的对应位置即可。
spanList._mtx.unlock(); //解桶锁
PageCache::GetInstance()->_pageMtx.lock(); //加大锁//从page cache申请k页的spanPageCache::GetInstance()->_pageMtx.unlock(); //解大锁//进行span的切分...spanList._mtx.lock(); //加桶锁//将span挂到central cache对应的哈希桶
