【项目设计】高并发内存池

举杯邀明月

发布于 2024-05-26 10:16:37

510

发布于 2024-05-26 10:16:37

文章被收录于专栏：C++&linuxC++&linux

一、项目定位

1.实现目标

源码地址

1. 本项目基于google公司的开源项目tcmalloc作为背景，简化实现一个高并发内存池，用该项目可以替代传统的malloc free函数来申请和释放内存，malloc和free作为我们最开始接触内存管理的元老级函数是在熟悉不过的了，有人说已经有malloc和free这样的内存管理函数了，我们搞一个tcmalloc真的有意义吗？其实不然，像malloc和free这种的函数是通用级别的，而通用的东西往往都带有一个特性，那就是适用性强，可移植性强，但是随之而带来的缺点就是针对性不够明显，比如对于某些高并发项目场景，项目内的线程数量众多，不断的调用malloc，可能会涉及到频繁的加锁和解锁，这对于项目性能的影响是不可小觑的，所以在某些高并发场景，同时对性能要求又高的情况下，malloc和free就显的没那么能打了，此时google公司召集了一批顶尖的cpp高手写出来了tcmalloc这样高效的内存管理项目，而我们的这个项目只是从tcmalloc里面摘取了精华部分，目的就是学习和理解高效的内存管理应该是什么样子的，而不是造一个更好的轮子出来。

二、具体实现

1.定长内存池

1. 在实现项目之前，可以先实现一个简单的定长内存池来熟悉一下池化技术，为后面搭建内存池做一些铺垫，有些小伙伴可能第一次听说池化技术，其实很简单，如果我们每次申请内存都向堆去申请，那就会频繁的进行系统调用，而一次系统调用的开销可不小，会涉及到线程的上下文保存和恢复，以及处理器级别的切换，所以这样申请释放内存的效率很低，一种办法便是提前向堆申请好一批的内存，然后将这批内存暂时缓存起来，可以用容器或者其他的数据结构来缓存，等到线程来申请的时候，便直接可以通过容器或者其他数据结构中存储的内存来分配，而无需向堆去申请，这样的效率就会高很多，而像这样预先用数据结构或者其他容器来缓存早就向堆申请好的一批内存的技术就是池化技术。

2. 实现一个定长内存池的基本思想就是，预先向堆申请一批的内存，然后当外部调用New接口时，每次从这一批内存中拿出前T类型大小的字节数据返回，这个定长内存池其实就是一个类模板，提供申请某个泛型大小的内存申请和释放的接口。由于malloc本身内部实现就采用了内存池的策略来分配内存，则在下面的定长内存池中，直接使用Windows下的系统调用接口VirtualAlloc来进行内存的申请，脱离开malloc的内存池实现策略。

3. 在下面的实现中，有些细节需要说明，例如当使用者New一个T大小的对象时，我们可以从_memory指针所指向的一块大内存中，切出头T大小的字节个数的内存返回给使用者使用，但当使用者使用这部分内存，要进行Delete释放时，这个定长内存池该如何处理呢？其实处理的思想较为简单，通过一个_freeList指针来链接起线程归还的内存块，有人可能有疑问，内存块又不是一个结构体，又不包含前后指针，这怎么连接的起来呢？其实每一个字节在计算机中都会有自己的地址编号，那32位计算机来说，虚拟地址空间的2^32个地址的编号就是从0x00000000到0xFFFFFFFF这个范围，而一个字节是8bit，所以存储一个32位地址只需要4字节的空间，同理，存储一个64位机器下的地址就需要8字节的空间，那链接内存块的操作其实就可以看作更改某一段地址空间内存储内容的操作，拿下图举例，只需要拿出4字节的空间存储下一个内存块的首地址即完成了链接图中内存块的操作。其实下图中默认的每个内存块的固定长度刚好是4字节大小，也就是一个int的大小，有些人可能会有疑问，如果申请的是char大小的内存块呢？这样的内存块大小不足4字节，那么在释放这样的内存块时，该如何链接内存块呢？其实在32位机器下，这样不足4字节内存的申请是需要特殊处理的，对于不够4B的内存申请，我们还是要给他开4B大小的空间，因为不开4B大小的空间，无法在释放内存时将归还的内存块链接起来，而在64位机器下，不足8字节的内存申请同样需要特殊处理，给对方返回一个至少8B大小的空间，对方用的时候可能还是只用不足8B大小的内存区域来操作，但这不属于我们关心的范畴了，我们只要保证返回来的内存足够4/8字节(32位/64位)供我们操作就可以了。那如何拿到一个指针所指向的空间的前4/8字节的数据呢？其实就像下图中的代码所示即可修改前4/8字节的数据，有人可能会不太懂这部分代码什么意思。其实我们在访问计算机中这一大块虚拟内存空间时，无论任何类型数据的增删查改操作，都是遵循一种模式，即基地址+偏移量，就拿下图的obj指针来说，obj变量内部存储了一个地址，这个地址就是obj指向的内存块的起始地址，但现在我们能知道这个内存块有多大吗？obj究竟管理了多大的内存块呢？其实我们是不知道的，那该如何确定呢？其实是通过类型来确定的，现在obj是void，也就是无类型的，在强转类型过后，obj就正式的可以操作从基地址开始，类型大小作为偏移量的这部分内存了，那下面强转成二级指针的类型有什么用呢？二级指针解引用拿到的就是一级指针类型的大小，而一级指针类型的大小恰好就是地址的大小，在32位下就是4B，在64位下就是8B，这样就可以顺利拿到指针类型大小的前4/8字节数据进行操作了。

4. 在New函数中，如果剩余字节数不够一个T对象大小，那就重新申请新的一块大内存，下图是以128KB为单位每次向堆申请一块大内存，你如果觉得128KB较小可以自行修改，如果够一个T对象大小，则需要自行判断是否大于当前平台下的指针所占内存大小，如果小于，那就需要返回当前平台下的指针所占内存大小，如果大于，则正常分配T大小的内存即可。在Delete函数中，使用头插法将归还的T类型obj内存块链入到_freeList中即可。由于后面定长内存池会作为一个小组件在高并发内存池中使用，而高并发内存池会涉及到多线程，为了保证线程安全，在定长内存池中多加了互斥锁。

2.项目实现

2.1 模块介绍+整体运行流程

1. 该项目总体分为三层模块，分别是ThreadCache，CentralCache，PageCache，当某一个线程申请内存时，该线程会首先获取到他自己的线程局部存储内部的localThreadCache对象，通过该对象来获取内存块，如果ThreadCache中的内存块不够了，则会向他的下一层CentralCache去要，CentralCache随着ThreadCache向自己索要次数的增多，同时也会不断给ThreadCache返回更多的一批数量的内存块，然后再由ThreadCache返回给索要的线程，那如果CentralCache也没有内存块呢？则CentralCache会向PageCache要一个span，span译为跨度，在此处之意为跨度多个page，span是一个结构体，内部会存储页号和页数，也就是说span管理着以页为单位的内存块，CentralCache向PageCache要到span之后，会将该span关联的以页为单位的那部分大内存块，切分为固定大小的一串的小内存块存储起来，以备ThreadCache向他要，这就是整体的项目框架，还是比较简单清晰的。

2. 下面是ThreadCache模块，作为暂时存储批量obj对象大小的模块，采用的存储方案类似于哈希表，即使用数组存储指针的方式来暂存一连串的obj对象，数组中每一个index中存储着一个FreeList对象，该对象其实就是封装了一个void类型的指针_freeList，这个指针链接着一串的obj对象，每个下标其实就是对应申请线程申请内存的大小，小于256KB的内存申请其实都会向ThreadCache去要，256KB按照8KB一页来算的话，那就是32页的内存，而大于256KB的内存申请实际上就不会向ThreadCache去要了，而是直接去找PageCache去要。（我们上面所说的8KB一页是指我们认为每页大小是8KB，那么以页为单位申请内存时，就按照8KB来申请，但实际虚拟地址空间中大多数是按照4KB为单位划分页的，但这并不影响我们在程序中定义8KB为一页，我们想怎么定义怎么定义，只不过在实际系统调用申请内存时，他自己内部实现可能是申请了两次4KB以达到我们想申请的8KB的页，两者并不冲突，你可以自己定义每次申请的以页为单位的内存是多大，4KB，8KB，16KB都可以）但如果我们以1B为单位的话，1B到256KB，这总共得有256×1024种大小的字节申请，那我们的数组就要开256×1024大小的空间吗？这显然是不合理的，所以为了减少桶的数量，后面详细再讲ThreadCache模块时，还需要对线程申请的字节数进行内存对齐，以此来减少哈希桶的数量，但同时也会带来内存内碎片的问题，有些伙伴可能不了解内碎片和外碎片，可以问问gpt或者google一下，这里我简单介绍一下，内碎片就是指你要5B的空间，我给你返回8B的空间，那就有3B的空间是不用的，那这3B的空间就会被浪费掉，外碎片指的是一段连续的大内存空间，由于申请时的大小较小，导致中间有一些内存被搁置，等到申请的内存特别大的时候，这段连续的大内存空间原本是够的，但是由于被切割划分出去了，从而导致无法分配大内存的申请，只能在虚拟地址空间的其他地方重新找一块大内存分配出去，这就是外碎片问题，我们的项目中外碎片问题不能完全解决，但是可以通过合并页内存的方式来缓解这种问题，至于内碎片他其实并不是大问题，因为内存换回来的时候，整个内存还是可以用来分配给别人的，不过我们也要保证内存的利用率。所以总结一句话，在后面的具体实现中，需要保证哈希桶的数量适中，同时保证内存的利用率不能太低，两个因素要均衡的当。

3. 下面是CentralCache的示例图，CentralCache的数据结构与ThreadCache非常类似，映射的方式相同，也就是说数组的大小是和ThreadCache完全相同的，唯一不同的是索引下存储的内容，CentralCache没有采用单链表结构来存储，而是使用双向循环链表，也就是SpanList，每个Span其实就是来自于PageCache为其分配的，而在每个Span结构体内部又会有一个成员变量_freeList，没错，你没看错，又是_freeList这个单链表头指针，_freeList负责指向Span所指向的以页为单位的内存被切割为一串串的单链表，等到ThreadCache向CentralCache要某个固定大小的obj对象的时候，便可以根据这个obj的大小，去对应的桶里面，拿到一个不为空的Span对象，从这个Span对象内部的_freeList里拿走一批的obj对象，然后ThreadCache把从CentralCache拿到的这一批对象再缓存到自己obj大小对应的哈希桶里面，以备申请线程申请内存块。

4. 下图是PageCache的示意图，PageCache用于缓存以页为单位的Span，最大的index是129，因为采用的是直接地址法映射，下标1对应的是1个页大小的Span，下标0弃用，所以这个数组的大小是129，与CentralCache相同的是，下标中存储的同样也是双向循环链表SpanList，只不过每个Span结点内部的_freeList指针均为nullptr罢了，因为用不到_freeList，PageCache只要负责能够给CentralCache提供Span对象即可，不过为了缓解外碎片，其实PageCache在向堆申请以页为单位的内存时，每次都会申请128page的大块内存，然后new一个Span关联到这块大内存上，如果CentralCache要小于128page的Span时，拿请求3page大小的Span为例子，如果PageCache的3Page对应的桶中没有Span，则会依次向后寻找，直到找到不为空的桶，找到后便会将这个较大页的Span进行切分，切分为3Page的Span和剩余的那个Span，把3Page的Span返回给CentralCache，把剩余的那个Span在挂到PageCache中的相应的桶里。而实际在项目刚开始运行时，所有的内存都来自于第一份PageCache向堆申请的128Page大小的Span，所以如果刚开始申请内存的线程要的内存较小，那么势必这个128Page大小的Span会不断的被切分成更小的Span，以供CentralCache拿走切分为小块的一连串obj对象，然后再由ThreadCache从CentralCache拿走一批obj对象，最后返回给申请线程。

2.2 ThreadCache

1. ThreadCache是申请内存的线程最先接触的模块，所以ThreadCache上来需要处理的第一个问题就是字节对齐的问题，既要保证哈希桶数量不能太多，又要保证内存利用率不能太低，而下面注释中给出的方案便是字节对齐的方案，对于字节数为1-128的内存申请，均使用8B对齐的方案，那其实就需要128/8也就是16个哈希桶便可以处理这些大小的内存申请，超过128B大小，也就是对于128+1 - 1024的内存申请，则改为使用16B对齐的方案，那就需要(1024-128)/16也就是56个桶，超过1024B之后，则改为使用128B对齐的方案，以此类推，从注释中可以看出，随着内存申请字节数的增大，对齐数也会越来越大，随之而来的内碎片的字节数其实就会更大，但内存利用率其实改变并不会很大，虽然浪费的字节数变多了，但是基数也相应着变大了，所以整体的内存利用率可以一直维持在10%左右，浪费不算严重，故而采用以下方案进行字节数对齐。 AlignUp内部调用_AlignUp拿到对齐后的字节数大小，代码实现难度不大，读者可自行阅读代码。 BucketLocation是通过对齐后的字节数大小来拿到哈希桶的位置，这个函数只会在ThreadCache和CentralCache中用到，因为只有这两个模块的哈希表的映射规则是相同的，PageCache采用的是直接地址法映射，与这两者不同，具体实现中，先定义了baseBucketNum数组，先通过bytes的大小确定基础位置在哪里，然后再通过能够整除几个字节数来计算从基础下标位置向后移动几步，所以这里其实也是用基地址+偏移量的思想来实现代码。 GetBatchFromCentral是ThreadCache内部某个桶下没有缓存的obj对象了，然后去CentralCache的桶里面去拿走一批obj对象继续缓存下来，MAX_BYTES大小即为ThreadCache可提供的最大内存也就是256KB，batch译为一批，即ThreadCache每次不够时，向CentralCache中拿走一批的obj对象，而在实际获取时，该函数会配合另一个策略来实现慢启动，即刚开始ThreadCache向CentralCache要的时候，CentralCache只给一点点，如果随着要的次数增多，那就说明申请内存的线程对这种大小的obj内存需求很大，那ThreadCache再来要的时候，CentralCache就会给较多的obj对象，这个慢启动算法在下面ThreadCache.cpp文件中会看到具体实现。 GetSpanFromPageCache是提供给CentralCache用的，如果CentralCache中的某个桶中没有span的时候，则会向PageCache要一个Span，而Span管理的页大小是多大呢？取决于当前alignBytes对应的ThreadCache从CentralCache中取的batch的数量×上alignBytes的大小，然后在除以一页的大小，最后得到页数量，然后返回即可。

下方代码定义在Common.h文件中

2. 下图是ThreadCache存储obj对象的结构，包括三个成员变量，分别是_freeList指向一个单链表，_size表示小对象obj的数量，_fetchSize表示下一次从CentralCache中拿多少数量的obj内存块对象。额外需要说的是便是NextObj函数，该函数负责拿到指针变量的前4/8字节的内容，同时将这部分内容以引用的方式进行返回。其余的接口难度并不大，可自行阅读代码

3. ThreadCache模块只需要实现下图所示的四个接口即可，为申请内存线程提供的Allocate和Deallocate，当ThreadCache自己的obj块不够时，则需要调用FetchFromCentralCache向下一个模块去拿。相对的，当申请内存线程不使用内存块时，便会调用Deallocate将内存块还给ThreadCache模块，当还回来的内存块过多时，ThreadCache模块要将部分的内存块回收到CentralCache模块。有人可能会有疑问，为什么还要将内存块唤回CentralCache呢？直接驻留在ThreadCache模块不好吗？之前我们谈到过CentralCache是单例模式，而ThreadCache对象独属于线程，如果一批obj块持续在ThreadCache中停留，则可能会造成其他线程无法直接从CentralCache拿走一批obj块，可能还会导致CentralCache中的obj块不足，进而去和PageCache要，但如果我们能回收ThreadCache的obj块，那CentralCache就可以实现类似负载均衡的功能，让每个ThreadCache的申请obj块的要求都能尽量满足，这就是回收的意义所在。在windows下，可以使用_declspec(thread)来声明线程局部存储的变量，这样就可以实现每个申请线程独享ThreadCache的目的，同时还不需要加锁，真正的并发访问，效率会很高。

下图是ThreadCache.h文件

4. 值得注意的是，只有Allocate和Dellocate的参数涉及到bytes，也就是申请的字节数，其他项目中所有函数的参数，只要涉及到字节数都是alignBytes，也就是说在这两个接口中会做对齐字节数的操作，后面涉及到字节数传参时，一概只传对齐后的字节数alignBytes。 Allocate的实现逻辑很简单，如果alignBytes对应的哈希桶中的FreeList对象中有obj内存块，则直接返回，如果没有，则调用FetchFromCentralCache。在FetchFromCentralCache中，首先需要拿到batch的大小，batch便是要从CentralCache中拿多少个obj内存块，min函数的第二个参数对于某个alignBytes是固定不变的，如果alignBytes较小，那第二个参数就会返回较大，如果alignBytes较大，那第二个参数就会返回较小，而min函数的第一个参数则是从1开始逐渐增大，当batch的值和自由链表中返回的FetchSize相同时，就会增加FetchSize的值，实现慢增长的效果，即batch的值会随着FetchFromCentralCache()函数调用次数的增多，也会逐渐增大。有了batch变量的值之后，则可以直接调用CentralCache向外提供的FetchRangeObj方法，从其内部对应的哈希桶中拿走一段obj内存块，使用start和end作为输出型参数传递给FetchRangeObj方法，根据actual的值在做判断，如果actual只有一个，那直接返回这一个内存块即可，如果actual的值大于1，则拿出第一个内存块返回，剩余的从NextObj(start)到end的内存块则缓存到ThreadCache模块中，以备下次线程继续申请内存。

下图是ThreadCache.cpp文件

5. 实现Deallocate的逻辑为，先将还回来的内存块挂到ThreadCache对应的哈希桶上，然后做一步判断，如果当前哈希桶内的obj对象数量已经>=下一次要去CentralCache取的obj对象数量，则调用ListTooLong，回收ThreadCache中的一段obj对象到CentralCache中。 ListTooLong实现逻辑即为直接调用CentralCache向外提供的ReleaseObjsToSpans，将obj还回到对应的Span中。

下图是ThreadCache.cpp文件

2.3 CentralCache

1. CentralCache向外提供的接口也只有四个，由于采用的是饿汉单例模式，所以需要向外提供一个静态方法来获取单例的CentralCache对象。同时提供给CentralCache模块的方法分别是FetchRangeObj和ReleaseObjsToSpans，而GetOneSpan其实是实现FetchRangeObj的辅助接口。

下图是CentralCache.h文件

2. 下图是Span结点和SpanList双向循环链表的定义，Span结点中，页号和页数便可以指向虚拟地址空间中一段以页为单位的连续内存，这两个变量其实就分别代表着基地址和偏移量，页号左移页大小便可以拿到这段连续内存的起始地址，有了起始地址和页数量之后便可以知道这段连续内存有多大。还包括一个原生指针_freeList，这个原生指针指向的单链表即是Span指向的以页为单位的连续内存被切分为一个个的obj挂到上面来的。

下图是Common.h文件

3. 实现FetchRangeObj的逻辑为，先通过alignBytes同样的获取到哈希桶的位置，然后从该哈希桶中获取一个Span。获取Span的操作由于会对单例对象的哈希桶修改，而哈希桶有可能被多线程访问，所以需要加锁保护，获取到一个Span之后，接下来的操作就是从Span中的_freeList中获取到一段大小为batch参数的obj对象，但有可能出现的情况是，_freeList中的obj数量可能不够batch，所以还需要定义一个ret变量，用于返回实际从Span中拿到了多少个obj内存块。值得注意的是Span一直挂在哈希桶上，在GetOneSpan之后，要从Span中_freeList里拿走一段obj内存，这依旧是在对Span修改，所以在FetchRangeObj函数中，解锁的过程只能放在最后。(我当时脑子发抽，以为只要获得了Span之后就可以解锁了，以为Span从哈希桶上解下来了，实际并没有)

下图是CentralCache.cpp文件

4. 当ThreadCache的小内存驻留的太长时便会调用下面的接口将obj回收到CentralCache的哈希桶中的某个具体的span上，所以回收obj内存块的逻辑为，遍历start到nullptr的obj结点，然后拿到每个obj所对应的span结构体，该步骤通过PageCache单例模式向外提供的MapObjToSpan方法实现，然后将该obj头插到span内部的_freeList中，同时span内部的_useCount减1，表示span内部切分的小内存块被ThreadCache还回来一个，自然使用计数减减，然后判断该span的_useCount是否为0，如果为0，则说明span切分的小内存块全都被当初取走使用的ThreadCache还回来了，那间接的说明线程可能对于该大小的obj内存申请需求较低，则CentralCache便执行PageCache的ReleaseSpanToPageCache方法，将该Span回收回PageCache中，PageCache则可以尝试合并回收回来的Span指向的页内存，缓解内存外碎片问题。有两个不错的问题： 1.为什么非得找到obj当初所在的span进行回收呢？不可以将obj随便放到哈希桶里的某个span内部吗？如果这么做的话，假设现在一个span的_useCount减少到0了，但是他内部的_freeList中的内存块并不完全来自于span所指向的连续页内存，那就会出现一个问题，连续页内存中可能有一部分的obj还没有从ThreadCache释放回来，而此时CentralCache却将span回收到了PageCache中，那如果有其他线程申请内存，如果申请到了未释放的obj的那块内存的话，同一个obj就有可能在两个线程中被同时使用，所以obj在被回收时，一定要回收到当初切分成多个该obj的span内部，不能回收到随便的一个span中。 2.为什么调用ReleaseSpanToPageCache之前要解掉CentralCache的桶锁呢？解开CentralCache的桶锁后，其他线程执行流可以调用ReleaseObjsToSpans将obj对象还给CentralCache，或可以向CentralCache申请一串obj内存块，而刚刚的执行流同一时刻则可以进入到PageCache模块，执行回收span的逻辑，这样项目整体并发度就会提高，线程之间互不影响。

下图是CentralCache.cpp文件

5. GetOneSpan的实现逻辑即为，在CentralCache相应的哈希桶里，也就是一个SpanList中找到一个不为空的Span，同时这个Span的_freeList也不能为空，因为这个接口的功能就是返回一个_freeList指向连续内存块的单链表。如果哈希桶中有，那直接返回即可，如果没有，则可以先解开桶锁，然后从PageCache中获得一个Span，即调用PageCache单例模式的NewSpan接口，PageCache的锁不再是桶锁，而是能够锁住其整体的一把大锁，所以调用接口前后需要加锁和解锁，获取到Span之后，则需要对span所指向的页单位内存一个个切分为alignBytes大小，同时用_freeList将其链接为单链表。完成Span所指向页内存的切分之后，则需要将来自于PageCache的span头插到CentralCache的SpanList中，头插之前需要将桶锁加上，因为此时在对共享资源哈希桶做操作。同样的问题，为什么调用PageCache的NewSpan之前要解开桶锁？其实目的依旧是提高并发度，当解开桶锁后，虽然申请内存的线程有可能无法继续从当前这个哈希桶中拿到obj内存块，但是释放obj的线程可以申请到桶锁，将obj释放回span内部的_freeList中，而刚刚的线程依旧可以执行PageCache中的NewSpan接口，双方可以真正并发的跑，所以效率会比较高。

下图是CentralCache.cpp文件

2.4 PageCache

2.4.1 tcmalloc源码的基数树分析

1. 由于实现PageCache过程中，为了优化项目的性能，采用了tcmalloc中的基数树来代替哈希表存储页号与span的映射关系。之前我们谈论ReleaseObjsToSpans的时候，需要通过obj找到其对应的span，实际查找的过程其实是先用obj的地址右移PAGE_SHIFT位，这样就能够拿到obj所在的页内存的页号，然后再通过哈希桶查找页号对应的span结构体，最终将obj头插到span中的_freeList中，完成CentralCache对ThreadCache的内存回收。虽然用哈希表可以存储页号与span的映射关系，但是他有两个缺点，1.该哈希表既被读又被写，所以无论是读之前还是写之前都需要加锁，而该哈希表又被频繁访问，所以线程间竞争PageCache的锁会很激烈，导致项目的性能达到瓶颈。2.STL容器所占用的内存空间本身就是由malloc开辟的，既然项目本身就是内存池，所以尽量就不要用应用层的接口，最好直接用系统调用申请堆内存，不去关联malloc自己的内存池策略。正因为如此，放弃使用STL提供的unordered_map容器，而是用tcmalloc中的基数树来代替，基数树数据结构纯是用数组和结构体的方式设计的，所以很好的解决了上面的第2个问题，即关联到malloc自己的内存池策略，但同时基数树更大的价值在于，在本项目中，多线程读取或修改基数树时，是不需要加锁的，这是基数树最有价值的地方，具体为什么不需要加锁，在下面分析完基数树的代码之后谈论。

2. 下面是单层array构成的数据结构，适用于32位下的页号和span映射关系存储，无法在64位机器下发挥作用，非类型模板参数BITS其实是32位减去页大小的位数，在本项目中我们设计一页大小为8KB，所以BITS就是32位-13位，也就是19位，代表在虚拟地址空间中共有2 ^ 19个页号，所以array_指向的指针数组的大小刚好就是2^BITS的大小，数组的每个下标位置代表的就是页号，下标中存储的内容就是页号对应的span指针，在下面的接口中，实际上Next接口不需要考虑，但是为了代码的完整性，也就贴上来了。构造函数其实就是开辟好2^BITS大小的一维指针数组，然后用二级指针array_指向这个数组即可。 Ensure其实是保证从x开始直到n的页号在基数树里面能够有对应的span，只有Ensure调用之后，才能调用set或get方法，同时这个n参数其实是开区间，传参的时候直接传页号和页大小即可，比如页号是1，页大小是3，那其实所在的页就是1 2 3，页号+页数正好就是开区间，该接口这么设计也是方便外界在调用的时候好传参。在单层的基数树这里，调不调用Ensure其实也无所谓，因为所有的空间在构造函数一开始就全部初始化好了。对于get和set的作用就是获取页号对应的span结构体指针，与设置页号和span结构体指针的映射关系。

3. 下面是双层的基数树，在本项目中非类型模板参数BITS的大小是19，也就是32-13，因为自定义的一页大小为8KB，该基数树将19个比特位划分成两部分分别存储在根节点和叶子节点上，叶子结点的结构体只包含一个2 ^ 10大小的一级指针数组，该基数树成员变量只包含一个存储叶子结点指针的一维数组，该根结点数组大小是2 ^ 9。在构造函数中，只开辟了根节点数组的空间，这意味着，该双层基数树的叶子节点空间开辟类似于懒汉模式，等到需要的时候才会去开辟空间，不需要的时候就先为空等待着。在Ensure中，获取根节点上的下标位置，其实就是将页号右移叶子节点的比特位大小，这样剩下来的就刚好是32位页号中低9位的比特位，因为这32位页号其实只有低19位是有效的，右移掉低10位，剩余的低9位自然就是根节点上的下标位置，获取下标位置之后，就判断该下标中存储的叶子指针是否为nullptr，如果为nullptr，则分配一个叶子结点的指针，然后继续向后迭代页号。在set和get中，比较重要的就是i1和i2的下标计算，i1的计算上面也说到过，i2的计算其实就是保留低10位，那按位与LEAF_LENGTH-1正好就保留了低10位。在调用set和get之前，需要调用Ensure保证页号对应的span指针存在，这点与单层的基数树就不同了。

4. 在64位下，单层和双层的基数树就不够用了，因为每层需要表示的比特位太多了，无法开辟这么大的空间，所以这时候就只能靠三层的基数树了，拿13bit位表示的页来算，三层基数树需要能够表示51个bit位，因为页号共有2 ^ 51个，就算是均分为3层，每层也就是17左右的样子，那开辟2^17的数组也就是128KB的大小，开这点空间对于堆来说微不足道，值得注意的是，我们开辟的数组全部都是在堆上，函数栈帧中仅仅只存储指向堆上数组的指针变量而已，所以不会出现栈溢出的问题。在Ensure接口中的逻辑其实与上面双层基数树相同，只要指向下一层结点的指针为空，则分配下一层结点的空间，第三层的结点是Leaf类型的，但是第二层的数组元素类型是Node，所以在存储的时候，需要将Leaf强转为Node类型进行存储，等到get或set访问时，只需要将第二层结点中的存储元素强转回Leaf类型，然后就可以正常访问第三层结点内部的元素了，也就是span指针。对于get和set中取下标的原理与上面的双层基数树相同，这里不再赘述。

5. 上面谈到过关于基数树被多线程读取+修改时，不需要加锁，而轮到哈希表却需要加锁，这是为什么呢？主要因为哈希表存在哈希冲突，即一个下标位置可能会被多个页号映射到，这就可能存在一个桶被多个线程访问+修改，则势必有线程安全的问题，这个桶其实就是单链表，试想，某个线程正对单链表进行头插，头插肯定不是一个原子操作，那在头插一半的时候，另一个线程又来遍历单链表，那一定会出问题的，比如空指针访问，越界访问什么的，各种离谱的问题就可能接踵而至了。但基数树不一样，基数树不会出现多个线程同时对一个叶子的同一个index位置修改+访问，无论是单层，双层，三层基数树，当某个线程在向叶子的某个下标中分配span指针的时候，也就是所谓的修改，其他线程是不可能在同一时刻访问的，只有在修改完毕之后，其他线程才有可能访问，因为在修改的时候，这块页内存还没有被挂到PageCache中，其他线程是访问不到这个页内存的，只有在挂完之后，其他线程才有可能访问。总而言之，主要是基数树没有哈希冲突的担忧，每个页号对应的span所占用的空间都是独一无二的，同时修改和访问的操作并不会同时并发的在某一个叶子结点的index上发生，所以对于基数树的增删查就无需加锁控制，虽然确实多线程操作了基数树，但操作是有时序的，同时操作的位置也都是不同的，修改的index与被访问读取的index不可能是相同的，所以不必担心基数树的线程安全问题。在之前linux的POSIX信号量文章中，当时讲了一个生产消费模型的环形队列，内个环形队列也无需加锁控制，原理和基数树也是类似的，消费线程和生产线程随时并发跑的，但由于有信号量的控制，所以两个线程操作的位置不会在同一个index处，自然就不会有安全问题。

2.4.2 PageCache接口实现

1. PageCache需要实现的核心接口只有三个，向外提供一个管理以页为单位的Span接口NewSpan，通过基数树来返回内存块obj对应的span结构体指针MapObjToSpan，回收CentralCache返回的span接口ReleaseSpanToPageCache。另外创建span结构体可以用new来实现，但new底层用的还是malloc自己的内存池策略，所以PageCache中分配span结构体不再用new，而是用刚开始实现的定长内存池ObjectPool来分配Span结构体。从tcmalloc搬过来的基数树还需要我们自己的改一下，如果你是在32位下运行，用TCMalloc_PageMap1和TCMalloc_PageMap2都可以，如果在64位下运行，则只能用TCMalloc_PageMap3来存储映射关系，如果不想自己手动传递模板参数的话，其实也可以用条件编译来实现不同平台下调用不同的基数树，这个并不难，在下面的测试环节我会把3位与64位下都测试一遍。

2. 在NewSpan中，分为三种情况，如果申请的页数很大，已经大于整个PageCache哈希表能存储的最大页数也就是128page时，此时就不需要我们的内存池技术了，直接调用win的系统调用申请内存即可了，但申请完之后，还要保存页号与span的关系，保存时，只需要保存起始页号即可。如果申请的页数在[1, 128]之间，则先看看k位置对应的哈希桶中是否有缓存的span，如果有，则将该span从哈希桶上解下来，然后返回给CentralCache，如果没有，则只能遍历后面的桶，看是否有span，如果有，则将该span切分为两个span，一个span用于k页span的返回，另一个剩余的span则再继续挂到对应的哈希桶里。如果从k+1开始后面没有一个桶里有span，则向堆申请一个128页的内存，然后通过_spanPool这个定长内存池构造一个maxSpan出来，让这个maxSpan关联到128page的内存，再把maxSpan挂到相应的桶中，然后代码复用的地方来了，我们只需再调用一遍NewSpan(k)即可，因为在调用一次NewSpan时，从k+1开始遍历，遍历到最后肯定能拿到不为空的span，这就是代码复用，是不是很方便呢？上面只说了关于如何返回span的逻辑，还需要说的是关于_idSpanMap存储页号与span的逻辑，由于要返回的kSpan被切分为obj之后，每个obj在被返回时，都需要找到obj对应的span，所以存储关系时，需要存储kSpan包含的所有页号与kSpan的映射关系，只有这样才能让所有的obj都找到对应的span。对于不需要返回给CentralCache的span，也就是缓存在PageCache里的Span，同样需要缓存页号与Span的映射关系，主要原因是回收CentralCache返回的span时，PageCache要尝试进行页合并，对于缓存在PageCache中的span，就不必缓存所有的页号和span的映射关系了，只缓存首尾页号与span的映射关系即可，只有交给CentralCache的span才需要缓存所有span中所有页号与span的映射关系。

3. 映射obj到span，需要先用obj地址除以一页大小，拿到页号之后，直接调用_idSpanMap的get方法即可拿到页号对应的span结构体指针。

4. 下面是回收CentralCache还回来的span，这意味着span关联的连续页内存暂时不用了，则可以尝试将这块页内存与PageCache中驻留着的span所指向的连续页内存们进行合并，如果能够合并出更大的页内存，便可以缓解内存外碎片问题，同时满足大内存的申请需求，即使没有大内存的申请需求，那大内存也可以再切分为小内存，所以合并页的好处不言而喻。对于大于128page的span内存释放，则直接还给堆，对于合理的span则进行页合并。在页合并这里，需要两个while循环，不断的向前进行页合并与不断的向后进行页合并，遇到页号对应的span不存在为nullptr时，则跳出循环。在合并页的逻辑中，span的_is_using成员变量就发挥作用了，我们需要一个标志位来区分驻留在PageCache里的Span和在CentralCache中被使用的Span，如果不区分，则可能存在合并span时，前面的span并不在PageCache中，而是在CentralCache中，此时合并则要出大问题了，内存有可能正在被用着，然后你就合并了，这不合理，所以需要_is_using成员变量来区分Span当前的状态。只有Span不在使用中，同时合并的两个span的页数之和不能超过128，两个条件同时满足时，才能进行页合并，有人可能对第二个条件有疑问，寻思两个span的页数怎么可能超过128呢？在NewSpan那里，最大申请的页内存也只有128page啊，其实是有可能，如果向堆连续申请两次128page，而这两个128page的内存刚好是连续的，那在进行页合并的时候是有可能超出128page大小的，而超出128page的span是无法存储在PageCache的哈希桶里面的，故两个条件都需要满足。

2.5 测试结果

1. PageCache.h文件中借用了条件编译来实现32位与64位不同架构下的代码实现，实现起来也较为简单，64位下只能用三层基数树，32位下一层与两层皆可，性能差别不大。

下方是借用tcmalloc中的基数树到本项目中，删去了部分接口，同时内存分配器成员变量也删去了，申请内存则直接调用windows下的系统调用申请，由于三个基数树的接口设计都相同，这使得项目中需要更改的代码非常少，这也是设计接口一致性的好处，用起来很省心。

2. 下面是项目的最外层，直接交给申请内存的多个线程使用，在ConcurrentAlloc中，大于256KB的内存申请，则交给PageCache来处理，不走当前项目的三层模型，在NewSpan中会分两种情况处理，一种是大于128page的内存申请，一种是[1, 128]之间的内存申请，前者NewSpan会直接找堆要，后者则会在PageCache的SpanLists中找合适的Span。在ConcurrentDealloc中，则只需要先找到obj对应的span，如果span中的_objSize小于256KB，则走三层模型释放内存，如果大于256KB，则调用PageCache的ReleaseSpanToPageCache将obj对应的span释放，与NewSpan对应的，在ReleaseSpanToPageCache内部也会对span进行分类讨论，如果大于128page，则直接释放给堆，如果小于，则挂到SpanLists中。