c++内存池项目

---

一、内存池介绍

二、ThreadCache实现

下面我们来实现项目的ThreadCache部分。我们将ThreadCache类的成员函数的声明和定义分别写到ThreadCache.h和ThreadCache.cc文件中。然后我们在Common.h文件中实现一些共用的类或函数。我们实现ThreadCache的初步思想和定长内存池类似，只不过内存池中申请的内存块不再是定长的，而是有可能为1、2、4、8、9、10…等字节的内存块，所以这些申请的内存块释放时，我们就不能挂载到同一个链表上，所以我们采用哈希桶类似的数据结构来管理这些大小不一的被释放的内存块。

因为会有很多个管理不同大小内存块的链表，所以我们将管理小内存块的链表封装为一个FreeList类，然后管理4字节大小内存块的链表创建一个FreeList对象，管理8字节大小内存块的链表创建一个FreeList对象等。这样我们就会有很多个链表，并且每一个链表用来管理不同大小的已经释放的内存块。我们为FreeList类实现一个Push函数和一个Pop函数，Push函数采用头插的方法将内存块插入链表中，Pop函数采用头删的方法将内存块的地址返回给用户使用。
因为每一个内存块就可以存储数据，所以我们实现链表时直接让每个内存块的前4(32位下)字节或前8(64位下)字节的内存用来存储下一个内存块的地址，然后我们让FreeList类中的_freeList成员变量来存储第一个内存块的地址。下图中为链表进行头插和头删的过程，我们在代码实现时需要先取到内存块的前4或前8字节的内存，然后将这4个字节或8个字节存储下一个内存块的地址。我们可以先将内存块的地址强转为void * * ，然后再解引用void * *，这样的话就是解引用一个指针变量的大小，即32位下向后取4字节空间，64位下向后取8字节空间，这样我们就不需要考虑32位还是64位操作系统的问题了。我们在下面直接将这个操作封装为NextObj函数了，即传入要管理的内存块地址，NextObj函数就会返回这个内存块的前4字节或前8字节的引用。这样就可以获取并且修改这个内存块的前4字节或前8字节的内容。


下面我们来实现ThreadCache类的框架，在ThreadCache类中有一个_freeLists成员变量，用来记录每一个大小不同的内存块存放的链表。ThreadCache类的Allocate函数就是类似于malloc函数，当用户调用Allocate函数并且传入申请的内存块的大小时，Allocate函数就会返回一个大于等于size大小的内存块。当用户调用Deallocate函数时就是将不需要的内存块进行释放，用户需要传入这个内存块的起始地址和内存块的大小，然后Deallocate函数中会将用户不需要的内存块根据内存块大小挂载到对应的FreeList中。我们将ThreadCache类中成员函数的声明和定义分开来写。下面就是ThreadCache类的大致框架。


下面我们需要解决一个问题，即上面我们说的如果将不同大小的内存块都设置一个对应的链表的话，因为我们设置的Allocate函数可以申请的最大的内存块为256KB=256 * 1024 Byte，所以我们就需要设置262144个链表来管理不同大小的内存块，这样的话创建的链表就太多了，并且当内存块大小为1、2等字节时就不够存一个地址的。所以我们就需要考虑将某个范围内的内存块都存到一个链表中，并且还需要考虑对齐，例如当申请[1,8]大小的内存块时就统一返回8字节大小的内存块，那么申请的[1,8]字节大小的内存块就存到一个链表中，[9,16]大小的内存块就统一返回16字节大小的内存块，那么申请的[9,16]字节大小的内存块就也存到了一个链表中。但是如果以8字节来对齐的话，那么还是需要创建32768个链表，这样链表还是太多了。所以我们可以采用下面的对齐映射规则来创建链表。
例如当用户申请的内存块大小为129时，此时对齐数为16，所以会为用户分配128+16=144大小的内存块，这样这个内存块就应该在freelists的下标为16的链表中存储。我们采用下面的这样的对齐映射规则的话就只需要创建208个链表即可，并且还将内碎片整体控制在最多10%左右的浪费。例如用户申请的内存块大小为129，实际分配的内存块大小为144，则有15个字节的空间被浪费，即$15/144=0.10$。

下面我们使用普通方法来求出当申请不同大小的内存块时，应该给用户的内存块大小。即我们根据对齐数算出用户申请的内存块大小是否为对齐数的整数倍，如果为对齐数的整数倍，那么就不需要进行对齐。而如果用户申请的内存块大小不是对齐数的整数倍，那么我们就需要返回给用户对齐后的内存块大小。

上面返回内存块大小的_RoundUp方法使用了取模、乘等运算，计算机进行这些运算是没有进行位运算效率高的，所以我们也可以将_RoundUp函数改为使用位运算来求出对齐后的内存块大小。然后我们将_RoundUp函数和RoundUp函数设置为SizeClass类的静态成员函数，并且还设置为内联函数。

然后我们在Allocate函数中就可以使用RoundUp函数算出实际返回给用户内存块的大小。

当我们求出来了内存块对齐后的大小后，我们还需要求出来内存块映射的是哪一个自由链表桶内。

上面的_Index函数用来算出不同大小的内存块在这个区域内的下标，然后加上之前内存块区域的下标，得到的就是该内存块在freeLists中应该链接的自由链表的下标。上面的_Index函数我们也可以改为使用位运算来实现。此时_Index的第二个参数为对齐数是2的几次方。例如当内存块大小为9时，9+7=16，16>>3=2，2-1=1，所以大小为9的内存块应该去freeLists的下标为1的自由链表中去找。

然后我们就可以将ThreadCache中的哈希桶表的长度设置为208了。

下面写出来FreeList类的Empty方法。

然后我们就可以实现ThreadCache类的Allocate函数，即当用户申请的内存块大小在自由链表中可以找到时，那么就不需要向中心缓存中获取空间，如果当用户申请的内存块大小在自由链表中没有时，就需要从中心缓存中获取内存空间。


下面我们来将ThreadCache变为单例模式，即使一个线程中创建一个ThreadCache对象。我们使用ConcurrentAlloc函数来将ThreadCache类中的Allocate函数进行封装，当用户需要申请空间时，就使用ConcurrentAlloc函数来进行申请空间。但是我们记录pTLSThreadCache的指针变量是一个全局变量，那么就相当于主线程创建的新线程中使用的都是这个共享的pTLSThreadCache的指针变量，而其中一个线程将这个指针变量改变时，其它线程也会收到影响，并且还会存在线程安全问题。所以我们需要让每一个线程都有一个属于自己的pTLSThreadCache指针。我们可以使用线程局部存储，在每个线程的局部存储空间内存储当前线程的pTLSThreadCache变量，那么每个线程在访问pTLSThreadCache变量时，就会去自己的局部存储空间中访问pTLSThreadCache变量。这样我们就解决了问题，使每个线程既有自己专属的pTLSThreadCache变量，也不需要使用锁来保证线程安全。


下面我们创建两个线程，并且让这两个线程调用不同的回调函数，然后回调函数都调用ConcurrentAlloc函数来申请空间。

当我们运行时发现报出来了多重定义的错误，这是因为在头文件中定义的函数，在两个或多个.cpp文件引用这个头文件时，都会将这个头文件进行展开，那么这两个或多个.cpp文件就都定义了这个函数，所以需要将这个函数使用static修饰，那么这个函数或者变量就只能在当前的.cpp文件中使用了。



下面我们在ConcurrentAlloc函数中打印出来当前线程的tid和当前线程的指向ThreadCache对象的pTLSThreadCache指针。可以看到两个线程的tid和pTLSThreadCache指针的值都不相同。


下面我们来实现ThreadCache类的Deallocate函数，Deallocate函数可以将释放的内存块插入到对应的自由链表中。

然后我们在ConcurrentFree函数中对Deallocate函数进行进一步封装。用户就可以调用ConcurrentFree函数来释放不需要的内存空间。不过用户需要传入这片内存空间的地址和这片内存空间的大小。

三、CentralCache实现

我们上面实现的threadcache中，每个线程都有自己的threadcache，所以每个线程从threadcache中申请内存块时，都是向自己的threadcache申请，所以并不会涉及到线程安全问题。而如果当线程的threadcache中没有内存块时，就需要调用FetchFromCentralCache函数向centralcache中申请内存。因为centralcache只有一个，所以如果多个线程的threadcache同时调用FetchFromCentralCache函数向centralcache申请内存时，那么就会出现线程安全的问题了，所以我们需要在centralcache中加锁来保证线程安全。

我们设计的central cache也是一个哈希桶结构，它的哈希桶的映射关系跟thread cache是一样的。不同的是它的每个哈希桶位置挂是SpanList链表结构，不过每个映射桶下面的span中的大内存块被按映射关系切成了一个个小内存块对象挂在span的自由链表中。所以当多个线程的threadcache向centralcache中申请不同大小的内存块时，是可以同时访问centralcache的不同桶的，而如果多个线程的threadcache向centralcache申请相同大小的内存块时，此时就会多个线程同时访问centralcache的同一个桶的情况，这种情况是线程不安全的。所以我们对ccentralcache的每一个桶都加上一个锁，即称为桶锁，这样多个线程的threadcache就不可以同时访问centralcache的同一个桶了。这样做的好处就是当只有多个线程的threadcache同时访问centralcache的同一个桶时，这些线程才会产生锁的竞争，而如果多个线程的threadcache同时访问centralcache的不同桶时，这些线程是不会产生锁的竞争的，这样就减少了线程之间进行锁竞争的开销。

下面我们来定义Span结构体。

_pageId记录了计算机的内存中的页号，如果我们将一页的大小定为8KB，即2^13字节。下面我们来分别计算32位计算机和64位计算机下内存可以分割为多少页。因为32位下和64位下的页数是不同的，所以_pageId的类型也是需要变化的，即当在32位下_pageId为size_t 类型，而在64位下时_pageId需要为unsigned long long类型，所以我们需要使用条件编译来判断当前为32位还是64位，然后来确定PAGD_ID的类型。

我们可以通过预定义常量_WIN32和_WIN64来判断当前是为32位下还是64位下。
1、_WIN32可以用来判断是否为Windows系统。
2、_WIN64可以用来判断编译环境是x86(32位)还是x64(64位)。
- 在Win32配置下，_WIN32有定义，_WIN64没有定义。
- 在x64配置下，_WIN32和_WIN64都有定义。

所以我们在写条件编译时需要注意判断的顺序，即我们需要先判断_WIN64是否定义，然后再判断_WIN32是否定义。

下面我们再来对Span结构体中定义的成员变量进行初始化，我们可以直接写缺省值来对这些成员变量进行初始化，也可以写出Span的构造函数，然后在构造函数的初始化列表中对成员变量进行初始化。

当我们定义了Span结构体后，就可以来实现SpanList带头双向循环链表了。然后centralcache哈希桶表的每个桶就是一个带头双向循环链表，链表中的每一个结点就是一个Span，Span中有一个_freeList自由链表，这个链表中就是大小相等的切分好的内存块。当threadcache向centralcache的桶中申请内存时，centralcache就会在对应的桶中查找_freeList不为空的Span，然后将该Span的_freeList中的内存块分配给threadcache。下面就是SpanList的大致框架。

接下来我们实现SpanList中插入Span和删除Span的函数。

然后我们就需要给每个桶都加上一个桶锁，这样同一时间就只能有一个线程访问这个桶。

然后我们来实现CentralCache类，因为CentralCache在整个进程中只需要一个，所以我们使用单例模式来实现CentralCache类。我们将CentralCache类的构造函数和拷贝构造函数设为私有。然后创建一个GetInstance函数返回_sInst的地址。通过GetInstance函数来获取一个CentralCache对象。需要注意的是我们要将GetInstance设置为静态函数，这样就可以不需要对象调用GetInstance函数来获取一个CentralCache对象了。

静态成员变量在.cpp中进行初始化。

下面我们来实现threadcache中的FetchFromCentralCache函数，当threadcache的自由链表中没有可以使用的内存块时就会调用FetchFromCentralCache函数去centralcache中申请空间。每次threadcache调用FetchFromCentralCache函数向centralcache申请空间时，centralcache会分配多一点空间给threadcache，从而避免threadcache频繁的向centralcache申请空间，因为threadcache申请空间需要进行锁的竞争，增加程序开销。那么每一次centralcache会向threadcache分配多少内存块合适呢，我们实现了一个NumMoveSize函数来计算centralcache向threadcache分配的内存块个数，NumMoveSize函数中根据传进来的单个内存块大小来计算内存块个数，如果内存块比较小时，就一次多分配些内存块给threadcache，但是最多不超过512个内存块。如果内存块比较大时，就一次少分配一些内存块给threadcache，但是最少也要分配2个内存块。

但是如果threadcache申请了内存块后，centralcache返回了512个内存块，而threadcache只用了一两百个，那么就造成了浪费。所以采用了一个慢增长的方法来使centralcache并不会一开始就返回512个内存块。我们先在FreeList类中新添加一个_maxSize变量，然后实现一个MaxSize函数返回_maxSize的引用。下面这样实现后threadcache第一次向centralcache就是只申请1个内存块，然后第二次申请2个，第三次申请3个，这样我们就实现了一个慢增长的算法，我们还可以修改每次增加2、3、4等等。


然后我们在CentralCache中实现一个FetchRangeObj函数，该函数用来分配内存给threadcache。第一个参数和第二个参数为返回型参数，当调用时传入想要的内存块数量和内存块大小，那么调用时传入的start和end之间就会有分配的内存了。并且因为有可能centralcache的内存不够，所以FetchRangeObj函数的返回值为实际返回的内存块个数。start为这片内存块空间的起始地址，end为这片内存块空间的结束地址。

如果FetchRangeObj函数返回的实际内存块个数为1时，那么直接将这个内存块的首地址返回即可。

而如果FetchRangeObj函数返回的内存块个数大于1时，我们就需要将第一个内存块返回，然后将第二个内存块到最后一个内存块插入到threadcache对应的自由链表中。所以我们在FreeList中实现了一个PushRange函数，该函数将一段内存块头插到freeList中。然后我们就可以调用PushRange函数来完成操作了。



上面我们实现了threadcache向centralcache申请内存，下面我们来实现centralcache中的FetchRangeObj函数，该函数会访问centralcache的_spanLists哈希桶表，所以我们在进行访问哈希桶表中的桶时，需要先进行加锁。我们在FetchRangeObj函数中调用GetOneSpan函数来得到一个非空的span，然后从这个span中切割出来threadcache需要的内存。


下面我们来看从span中切割内存给threadcache的逻辑。


但是上面的代码还是存在问题的，例如当batchNum为时，而span的内存块个数不够时，那么此时函数就会崩溃。因为end就会为空，而对空指针进行解引用就会出错。所以我们需要改变逻辑，即span中有多少内存块就返回多少内存块。这样就不会出现上面说的情况了。

四、PageCache实现

在centralcache中的GetOneSpan函数中，如果centralcache中的_spanLists中没有不为空的span后，那么centralcache就会去PageCache中申请span。
PageCache也是采用哈希桶结构，只不过PageCache的映射规则和前面的threadcache、centralcache的映射规则不同。在PageCache的哈希桶中，每一个范围都有一个span链表，如果centralcache想要申请2页内存，那么就去PageCache的2page桶中去拿取span，centralcache最多能申请的就是128页。因为128*8KB=1024KB=1MB了，已经够centralcache使用的了，当然如果想要设置的更多也可以。

1. 当central cache向page cache申请内存时，page cache先检查对应位置有没有span，如果没有则向更大页寻找一个span，如果找到则分裂成两个。比如：申请的是4页page，4页page后面没有挂span，则向后面寻找更大的span，假设在10页page位置找到一个span，则将10页pagespan分裂为一个4页page span和一个6页page span。
2. 如果找到_spanList[128]都没有合适的span，则向系统使用mmap、brk或者是VirtualAlloc等方式申请128页page span挂在自由链表中，再重复1中的过程。
3. 需要注意的是central cache和page cache 的核心结构都是spanlist的哈希桶，但是他们是有本质区别的，central cache中哈希桶，是按跟thread cache一样的大小对齐关系映射的，他的spanlist中挂的span中的内存都被按映射关系切好链接成小块内存的自由链表。而page cache 中的spanlist则是按下标桶号映射的，也就是说第i号桶中挂的span都是i页内存。
   
   下面我们来实现PageCache的大致框架，我们需要注意的是PageCache也是需要锁的。因为threadcache1可能申请8字节大小的内存块，然后通过centralcache向pagecache申请空间，同时threadcache2也可能申请16字节的内存块，然后通过centralcache向pagecache申请空间。而这两个线程都可能从pagecache的同一个桶中申请span，所以pagecache需要加一个全局锁，即同一时间只能让一个centralcache来pagecache的桶中申请span。
   因为PageCache一个进程中只有一个，所以我们采用单例模式设计。
   
   
   在PageCache中，如果当_spanLists中没有对应的大小的span时，就会去下面找更大的，然后分割为符合的span。如果PageCache刚开始一个span也没有时，那么就会使用系统调用接口向系统申请一个128页的span。
   
   当centralcache还回来span时，pagecache会做一个检测，然后合并相邻的空闲span，以此来减少内存碎片。例如如果centralcache中的span的usecount为0时，就说明切分给threadcache的小块内存都回来了，则centralcache把这个span还给pagecache，pagecache通过页号，查看前后的相邻页是否空间，如果空闲的话就合并，合并出更大的页，解决内存碎片的问题。
   
   下面我们来实现GetOneSpan这个函数，GetOneSpan函数中需要返回一个不为空的span，它会先去centralcache的对应的spanList中去寻找span，如果没有找到非空的span，那么就会去向pagecache要span。GetOneSpan函数想要查找对应的spanList中的span，需要先遍历spanList，下面我们在SpanList中实现Begin和End方法，以便在GetOneSpan函数中可以遍历SpanList。
   
   下面我们来遍历当前的SpanList，看是否还有不为空的Span。
   
   
   我们还需要在pagecache中实现一个NewSpan函数，用来返回一个k页的span给centralcache使用。
   
   
   下面我们来实现一个NumMovePage函数来计算一次向pagecache获取几个页。因为我们需要根据centralcache向threadcache中返回多少内存块和一个内存块的大小来分析pagecache需要向centralcache返回一个几页的span。
   
   

当GetOneSpan函数中如果在SpanList中没有查找到空闲span，那么就可以调用NewSpan函数从pagecache中获取一个合适的span来使用了。

因为NewSpan函数返回的是一个大块内存，所以我们还需要将这个大块内存分割为centralcache要求的小块的内存块然后链接起来，这样才将这个大块内存变为了一个可以供centralcache使用的span。我们需要先通过这个大块内存span中的起始页的页号计算出这个大块内存的起始地址，然后再通过这个大块内存中页的数量来计算这个大块内存实际有多少字节，然后用起始地址+大块内存大小计算出这个大块内存的末尾地址。


然后我们知道了这个大块内存的起始地址和结束地址，我们开始将这个大块内存切割为一块一块的小块内存然后链接起来挂到span的_freeList中。下面我们使用尾插法来将大块内存分割成的小块内存插入到span中的_freelist自由链表中。


当将大块内存分割完后，然后此时span就可以被centralcache使用了，所以此时我们需要将这个span添加到当前SpanList中，我们使用头插法将这个span插入到对应的哈希桶中。所以我们需要在SpanList中实现一个PushFront函数来将span头插到哈希桶中。

这样我们就实现了GetOneSpan函数了。

然后我们再来实现NewSpan函数，NewSpan函数就是获取一个k页的span，NewSpan中需要先检查pagecache中的_spanLists中的第k个桶里面是否还有span，如果有了直接返回，如果没有了那么就需要检查第k+1个桶中是否有span，如果有就将span切割为一个k页的span。如果没有那么继续向上查找。所以我们需要先实现SpanList中的Empty函数和一个头删PopFront函数返回span。

如果指定桶中没有k页的span，就去上面的桶中找比k页大的span，然后分割。例如如果找到一个n页的span，将这个span切分成一个k页的span和一个n-k页的span，k页的span返回给centralcache，n-k页的span挂到第n-k个桶中去。


如果_spanLists的后面一个span都找不到，例如当第一次申请时，那么此时就需要向系统申请一个128页的大块内存，然后根据这个大块内存来创建一个span挂载到对应的桶中。下面我们封装一个SystemAlloc函数，该函数可以在堆区上按页申请空间，所以我们可以使用该函数来向系统申请一个128页大小的大块内存。将128页的span插入后，然后递归调用自己，复用上面切割k页span的代码。


下面我们来进行加锁。在centralcache中，_spanLists的每个桶中如果有线程申请span或者有线程将内存块释放回来span都会改变对应的桶的结构，所以改变桶结构的操作都需要进行加锁。在GetOneSpan函数中，我们不需要将全部代码进行加锁，因为如果这样的话那么当有线程想要释放span时，还需要与申请span的线程来竞争锁，我们可以在刚开始就将桶锁解掉，这样释放span的线程就可以拿到锁来使用了。然后GetOneSpan函数只需要在向桶内插入span时进行加锁即可。还有在GetOneSpan中调用NewSpan函数返回空闲span时访问了pagecache，所以这个操作需要加上pagecache的全局锁。

五、回收内存

下面我们来实现内存的回收。
当用户将不需要的内存块释放后，这个内存块先插入到threadcache的_freeLists的对应的桶中，如果这个桶插入的内存块太多时，我们就可以考虑将这个桶中的一些内存块返回到centralcache对应的桶的span的_freeList中去。这样就避免了某一个线程独占过多的内存并且空闲的现象。下面我们就根据_freeLists的桶中的内存块个数与这个桶的MaxSize来比较，如果这个桶中的内存块个数大于这个桶的MaxSize，那么我们就调用ListTooLong函数来将一些内存块还给centralcache，即当链表长度大于一次批量申请的内存时就开始还一段list给centralcache。


在ListTooLong函数中需要先调用PopRange函数来将threadcache的_freeLists中的对应桶的内存块拿出来MaxSize个，我们没有将桶内的内存块拿出来完还给centralcache，因为如果拿出来完了，当线程使用内存块时，还需要再向centralcache去申请，我们只是把大多数空闲的内存块还给centralcache。然后我们将这些内存块组成的自由链表的首地址和内存块个数传给centralcache的ReleaseListToSpans函数，该函数会将这个自由链表中的内存块一一挂载到centralcache的_spanLists中的对应的span上。



到这里我们就大概知道了threadcache中的内存块还给centralcache的大致流程。下面我们来FreeList添加一个size成员变量，用来记录FreeList中的内存块个数，即threadcache中的_freeLists的每个桶中内存块的个数。然后我们还需要实现一个PopRange函数用来将FreeList中的前n个内存块进行头删。

当threadcache将内存块组成的自由链表的首地址和内存块大小返回给centralcache后，centralcache在收到这个自由链表后，因为这个自由链表中的内存块属于centralcache中的不同span的freeList，所以我们需要算出内存块自由链表中每个内存块属于centralcache的桶中哪一个span。我们可以使用下面的方法来计算内存块属于哪一个span，即我们根据内存块的地址除8K来得到这个内存块属于哪一页，然后再算出这一页属于centralcache的哪一个span，这样就得到了内存块属于哪一个span。

因为span中只标识了这个大块内存的起始页号和包含的页数，所以并不能方便的计算出内存块属于哪一个span。下面我们在pagecache中添加一个unordered_map容器用来记录页号和span的映射，这样当centralcache中算出每一个内存块属于哪一页后，通过idSpanMap就可以查到这一页内存对应的span了。


因为我们将idSpanMap定义在了pagecache中，所以centralcache想要访问这个容器来查找span需要调用pagecache提供的函数来访问。下面我们在pagecache中实现一个MapObjectToSpan函数，该函数可以根据传进来的内存块地址来查找并且返回这个内存块地址属于哪一个span，并且将这个span的指针返回。


当解决了内存块找对应的span的问题，下面我们就可以来实现centralcache中的ReleaseListToSpans函数了，该函数会根据传入的内存块自由链表首地址和内存块的大小来将内存块一个个分离出来，然后调用pagecache中的MapObjectToSpan函数来查找每个内存块属于哪一个span，然后将每个内存块头插到所属的span的freeList中去。

然后我们再来判断当centralcache中的桶中，如果有span中的所有内存块都被还回来了，即该span的_useCount成员变量的值为0了，那么就说明这个span的所有内存块都被还回来了，此时我们可以将这个span再返回给上一层pagecache。我们可以调用PageCache提供的ReleaseSpanToPageCache函数来向pagecache返回一个span。



下面我们再来看锁的问题，因为有可能一个线程会向pagecache返回span的时候，另一个线程也想要向centralcache返回内存块，那么这个时候这个线程就需要等待第一个线程把span返回给pagecache后，然后才能向centralcache返回内存块，这样就影响了线程向centralcache返回内存块的效率，并且向pagecache中返回span的过程并没有改变centralcache桶中的span，所以我们在当centralcache向pagecache返回span之前先将桶锁进行释放，那么其它线程在这期间就可以拿到桶锁然后在该桶的span中的释放添加内存块或申请内存块了。并且因为pagecache的ReleaseSpanToPageCache函数会改变pagecache的哈希桶，所以需要进行加锁。

下面我们来实现PageCache中的ReleaseSpanToPageCache函数，该函数中会检查还回来的span中包含相邻页号的span是否也被返回，如果相邻的span也被返回，那么就会将这些相邻的span合并为一个大的span，这样就可以解决外碎片的问题，即例如如果不执行合并span的操作，那么有可能会出现3page中都是包含3页的span，但是如果用户想要申请一个4页的span，却申请不出来，因为大span全都分为了3页的span。而通过合并span的操作就可以防止上述的问题发生。

那么我们就需要判断一个span是否还在被使用了，但是span的_useCount==0不能作为判断span是否还在被使用的依据，因为有可能刚申请的span此时_useCount=0，还没来得及_useCount++，然后pagecache的ReleaseSpanToPageCache函数中检查到这个span的_useCount=0，又把这个span给合并了。所以我们在span中再添加一个成员变量标识span是否在被使用。然后在centralcache的GetOneSpan函数中，当从pagecache中申请到一个span时，先将这个span标识为正在被使用，在还这个span给pagecache时将这个span标识为不被使用。



然后再将pagecache中的NewSpan函数中被切割的span的首尾页号和对应span的映射放到_idSpanMap容器中，这样方便在ReleaseSpanToPageCache函数中进行span的合并。

下面我们先实现向前合并相邻的空闲的span。


然后我们再来实现向后合并span。并且当合并完后，我们将这个span的首尾页和对应span也添加到_idSpanMap中，以便再次进行合并使用。

六、大于256KB的内存申请与释放

我们上面实现的内存池中定义了最大能申请的内存块为256KB，而当要申请的内存块大于256KB时，我们没有做处理。下面我们来分析大块内存的申请。

大块内存的申请分为两种情况：
1. 当内存块大于256KB但小于128*8KB时，此时可以直接去pagecache中申请大块内存，因为pagecache中最大的span为128页，所以此时128页的span还够使用。
2. 当内存块大于128*8KB时，此时pagecache中的128页的span的内存也不够了，所以这样的内存块就需要直接向系统中的堆中申请了。

下面我们来实现大块内存的申请。
我们需要在ConcurrentAlloc函数中进行判断，当申请的内存块大小大于MAX_BYTES时，先计算出对齐后的内存块需要多少页的内存，然后直接向pagecache中申请对应页的内存，而不走内存池的三级缓存了。

当申请的内存块大于MAX_BYTES时，我们就让这个内存块以页为单位来进行对齐。

在pagecache的NewSpan中，我们再进行判断，如果申请页数大于128页的span时，就不从pagecache的桶中找span返回，而是直接从系统中申请大块内存返回。

然后我们再来看大块内存的释放。
我们需要先将这个记录大块内存的span的起始页号和该span放到_idSpanMap容器中，因为这样在释放这个内存块时，才能在PageCache中的MapObjectToSpan函数中通过内存块的地址得到该内存块所在的span。然后再根据这个span来释放这个大块内存。

然后我们在ConcurrentFree函数中判断当大块内存释放时，就直接调用pagecache的ReleaseSpanToPageCache函数来将这个span进行释放。

然后我们在pagecache的ReleaseSpanToPageCache函数中进行判断，当要释放的span的页数大于NPAGES-1时，就直接调用SystemFree函数将内存还给系统。

七、将new和delete换为定长内存池

我们在上面的代码实现中，使用到了new来申请空间，使用了delete来释放空间，这是肯定不行的。因为我们实现的内存池就是用来替代malloc和free的，而new和delete底层还是调用的malloc和free，所以我们需要将new和delete来替换掉。因为我们前面写了一个定长内存池，该内存池只能申请和释放大小一定的内存块，而我们的程序中只使用new申请了span，所以使用定长内存块来代替malloc是可以的。
下面我们来进行具体实现。我们在pagecache中添加一个_spanPool定长内存池，然后将pagecache中的new span的操作都改为从定长内存池中申请，这样就将new使用定长内存池进行替换了。


然后再将delete替换为调用_spanPool的Delete成员函数。

然后将ConcurrentAlloc函数中的new ThreadCache也替换为使用tcPool的New。

下面我们再来完善程序，使程序在释放内存时不需要传递大小。我们前面在pagecache中设置了一个map容器，里面存了页的页号和对应的span，我们也可以使用内存块地址来求出来这个内存块属于那一页，所以我们就能确定一个内存块属于哪一个span，而且这个span中包含的都是大小一致的内存块。所以我们可以在span结构体中再添加一个_objSize成员变量用来记录span中切好的小对象的大小。

然后我们在知道span中存的内存块大小后，就将该span的_objSize成员变量的值进行更新。然后再调用ConcurrentFree函数释放内存时就不需要传入内存块大小了，因为在ConcurrentFree函数中先得到了这个内存块属于哪一个span，然后获取了这个span的_objSize成员变量的值。



下面我们进行测试，可以看到程序正常运行了。

下面我们再来看访问pagecache中的map容器需要加锁的问题，我们在pagecache中的NewSpan函数中对map容器中的数据进行了修改，按理来说我们应该在修改map容器中的数据时进行加锁，但是因为调用NewSpan函数的地方都进行了加锁，所以已经可以确定同一时间只能有一个线程进入到NewSpan函数，所以NewSpan函数中的对map容器进行修改在同一时间也只能有一个线程对map容器内的数据进行修改，这样就保证了线程安全问题。但是除了在修改map容器的地方进行加锁外，在读取map时也要进行加锁，因为map容器底层为红黑树，unorder_map容器底层为哈希桶，有可能线程在读取数据时，容器底层的红黑树因为数据的添加而进行了旋转，那么读取数据的线程读取到的数据就可能会出错。或者线程在读取数据时，unorder_map底层的哈希桶进行了扩容，那么读取数据的线程读取到的数据也可能会出错，因为C++的STL提供的容器不是线程安全的。所以我们需要在读取容器的地方进行加锁。

如果我们在PageCache的MapObjectToSpan函数中已经进行加锁的话，在调用该函数时又进行了一次加锁，而且两次加锁都申请的同一把锁，那么这时就会形成死锁。所以我们应该避免这样的情况出现。

八、多线程环境下对比malloc进行基准测试

至此我们的内存池就算完成了，下面我们就需要进行基准测试，来测试这个程序还会出现哪些问题。
我们使用下面的测试案例来对内存池进行测试。

#define _CRT_SECURE_NO_WARNINGS
#include"ConcurrentAlloc.h"
#include<thread>
#include<stdio.h>

//  ntimes: 执行malloc和free的次数  nworks:线程的个数  rounds:执行几轮
void BenchmarkMalloc(size_t ntimes, size_t nworks, size_t rounds)
{
	std::vector<std::thread> vthread(nworks);
	size_t malloc_costtime = 0;
	size_t free_costtime = 0;

	for (size_t k = 0; k < nworks; ++k)
	{
		//创建线程，让线程执行下面的操作
		vthread[k] = std::thread([&, k]() {
			std::vector<void*> v;
			v.reserve(ntimes);

			//执行rounds轮
			for (size_t j = 0; j < rounds; ++j)
			{
				size_t begin1 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					v.push_back(malloc(16));  //申请大小相同的内存块
					//v.push_back(malloc((16 + i) % 8192 + 1));   //申请大小不同的内存块
				}
				size_t end1 = clock();

				size_t begin2 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					free(v[i]);
				}
				size_t end2 = clock();

				v.clear();

				malloc_costtime += (end1 - begin1);
				free_costtime += (end2 - begin2);
			}
		});
		
		//等待线程
		for (auto& t : vthread)
		{
			t.join();
		}

		printf("%u个线程并发执行%u轮次，每轮次malloc %u次：花费：%u ms\n", nworks, rounds, ntimes, malloc_costtime);
		printf("%u个线程并发执行%u轮次，每轮次free %u次：花费：%u ms\n", nworks, rounds, ntimes, free_costtime);
		printf("%u个线程并发malloc&free %u次，总计花费：%u ms\n", nworks, nworks * rounds * ntimes, malloc_costtime + free_costtime);
	}

}



//  ntimes: 执行malloc和free的次数  nworks:线程的个数  rounds:执行几轮
void BenchmarkConcurrentMalloc(size_t ntimes, size_t nworks, size_t rounds)
{
	std::vector<std::thread> vthread(nworks);
	size_t malloc_costtime = 0;
	size_t free_costtime = 0;

	for (size_t k = 0; k < nworks; ++k)
	{
		//创建线程，让线程执行下面的操作
		vthread[k] = std::thread([&, k]() {
			std::vector<void*> v;
			v.reserve(ntimes);

			//执行rounds轮
			for (size_t j = 0; j < rounds; ++j)
			{
				size_t begin1 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					v.push_back(ConcurrentAlloc(16));  //申请大小相同的内存块
					//v.push_back(ConcurrentAlloc((16 + i) % 8192 + 1));   //申请大小不同的内存块
				}
				size_t end1 = clock();

				size_t begin2 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					ConcurrentFree(v[i]);
				}
				size_t end2 = clock();

				v.clear();

				malloc_costtime += (end1 - begin1);
				free_costtime += (end2 - begin2);
			}
			});

		//等待线程
		for (auto& t : vthread)
		{
			t.join();
		}

		printf("%u个线程并发执行%u轮次，每轮次malloc %u次：花费：%u ms\n", nworks, rounds, ntimes, malloc_costtime);
		printf("%u个线程并发执行%u轮次，每轮次free %u次：花费：%u ms\n", nworks, rounds, ntimes, free_costtime);
		printf("%u个线程并发malloc&free %u次，总计花费：%u ms\n", nworks, nworks * rounds * ntimes, malloc_costtime + free_costtime);
	}

}



int main()
{
	size_t n = 1000;
	std::cout << "===============================================" << std::endl;
	BenchmarkConcurrentMalloc(n, 4, 10);   //创建4个线程执行10论，每轮申请释放n次

	std::cout << std::endl << std::endl;

	BenchmarkMalloc(n, 4, 10);
	std::cout << "===============================================" << std::endl;

	return 0;
}

然后我们发现程序报出了错误，根据我们的断言信息，我们可以直接确定在执行Common.h中的352行时出现了问题。


我们可以在这个地方打一个条件断点，这样可以快速的复现错误。

我们看到pos指针变量和_head指针变量的值确实相等。

然后我们可以打开调用堆栈窗口，这样我们就可以查看当前函数被调用的关系，即哪个函数调用哪个函数最终调用了当前函数，然后造成了错误。我们可以双击这些函数，然后就可以返回到这个函数中。


我们根据调用堆栈依次返回到上一个函数，发现了错误，即在pagecache的NewSpan函数中，我们在返回span时，先去pagecache的_spanLists的对应的桶中检查是否有span，如果有span就直接将这个桶中的span采用头删法删去并返回给centralcache，但是我们写成了将_spanLists返回，所以就会将_spanLists的第一个桶进行头删，并且将第一个桶中的span返回，但是我们并没有使用第一个桶，所以第一个桶中的_head的next和prev都指向自己，当调用PopFront函数后返回的就是第一个桶的_head头结点，而且此时_head=_head->_next还是指向自己，所以就出现了_head==pos的情况。

我们将这个错误进行修改。然后再次运行程序。

我们发现再次运行程序又出现了异常，这个异常显示在FreeList类的PopRange成员函数中出现了end为空指针的情况。PopRange函数为通过返回型参数start和end返回一个包含n个内存块大小的自由链表的首地址和尾地址。然后将这个自由链表包含的内存块都从FreeList中删除。

我们通过监视窗口看到实际要删除的内存块个数为92，但是当i为72时end就为nullptr了，说明这个_freeList链表中并没有n个内存块，而只有72个内存块，最后一个内存块的前4或8个字节存的就是nullptr，所以当执行end = NextObj(end)时才会出现end为nullptr的情况。

但是为什么会出现_freeList链表中的内存块不够呢？我们通过调用堆栈看到在ThreadCache中先判断_freeLists的size大于MaxSize时，然后才进行的调用ListTooLong函数，在ListTooLong函数中调用PopRange函数来将_freeLists中的MaxSize个内存块进行删除，那么就说明_freeLists中的内存块个数一定是大于等于MaxSize的，但是在PosRange中却出现了内存块个数小于MaxSize的情况。那么说明我们在实际插入时并没有插入对应的内存块，这才造成了内存块的实际个数与_freeLists的size不相等的情况。

我们初步怀疑是FreeList类中的PushRange成员函数出现了问题，因为如果在插入的时候少插入了内存块，那么就会造成内存块实际个数和_freeLists的size不相等的情况。下面我们在PushRange函数中打一个条件断点，来查看通过PushRange函数插入到_freeLists中的内存块实际有多少个，我们可以看到start到end中的内存块实际只有70个，而表示这次插入的内存块个数的n为90，而且_freeLists的size加了n个。所以这就是为什么内存块的实际个数与_freeLists的size不相等的原因。

我们看到传入PushRange的参数n是调用FetchRangeObj函数返回的实际内存块个数。

我们在FetchRangeObj函数中打一个条件断点，然后算出以start为首地址的自由链表的内存块个数j为71，而上面代码算出来的实际返回的内存块个数actualNum为91。这个start是span的_freeList指向的自由链表，而span是通过GetOneSpan函数获取的。

然后我们在GetOneSpan函数中打一个条件断点，判断该函数中将大块内存分割为小块内存后，小块内存形成的自由链表中内存块个数和span中记录的内存块个数是否相同。我们看到程序好像陷入了死循环，此时我们可以中断程序，程序就会在正在运行的地方停下来。


然后我们看到j已经为随机数了，我们知道了程序刚刚一直在while中进行死循环，即该span中的内存块自由链表没有结束的地方。这才使cur一直不为nullptr，一直向后运行。

我们向上找发现是在将内存块进行尾插形成自由链表时，当最后一个内存块尾插入自由链表后，我们没有将最后一个内存块的前4或8个字节置为nullptr，所以这个自由链表会一直越界向后访问，这就造成了这个自由链表中实际内存块个数和span中记录的内存块个数不同的情况。所以我们在后面将最后一个内存块的前4或8个字节置为nullptr即可。

然后我们看到当申请和释放相同大小的内存块时，内存池和malloc比较的话效率还是很低的。

当我们换为测试申请和释放大小不同的内存块时，我们看到又出现了程序错误。

这个错误是一个断言错误，我们到指定的地方查看错误，我们看到在使用pagecache中的map容器查找内存块属于哪一个span时，发现map容器中并没有查到这个内存块属于哪一个span。所以进行了断言报错。

我们打一个断点，然后通过调用堆栈看到是在将这个内存块进行释放时没有在pagecache的map容器中找到对应的span。

然后我们通过计算得到当前要释放的内存块所在页为13449，但是在map中只有13448和13480页id和对应的span，而没有13449对应的span。那么肯定是在添加页id和对应span时少添加了。

我们知道map容器中添加元素只在NewSpan函数中有，所以我们可以确定问题出在NewSpan函数中。我们看到在NewSpan函数中，如果查到了当前第k个桶中有span时，那么直接就将span返回了，但是此时还没有将该span中包含的页和对应span添加到map中，所以这就是为什么会出现上面的错误的原因。

然后我们将该span中包含的页id和span建立映射存到map容器中。

然后我们运行内存池看到内存池的申请和释放效率还是没有malloc和free快。而且尤其是当申请和释放内存块大小相同时，两者的效率差距更大。

九、使用基数树进行性能优化

下面我们就来分析内存池的效率低在哪里。
我们使用VS中的性能分析工具来进行测试。


我们通过检测分析报告看到锁竞争占用了大部分的运行时间。而且花费时间最多的锁是pagecache的全局锁，这个锁在调用pagecache的函数改变_spanLists时需要进行申请，这个是无法避免的。还有在通过pagecache的map容器查找内存块对应的span时也需要申请这个锁，这就造成了锁竞争占用大部分运行时间。因为每一次申请内存和释放内存都需要访问map容器，那么就需要进行申请锁和释放锁，所以锁竞争增加程序开销的主要原因就在这里。


那么我们分析出来了性能瓶颈之后，应该怎么提高性能呢？我们知道了最主要的原因还是我们使用的map容器不是一个线程安全的容器，所以在每次访问map容器时，都需要进行加锁。我们可以将存储页号和对应span的容器改为使用基数树。

然后我们将pagecache的_idSpanMap使用基数树。再将修改_idSpanMap的地方都改为调用get函数和set函数。




然后我们再进行测试，可以看到内存池的效率就更高了。

那么为什么使用基数树不需要加锁呢？这是因为使用map或unordermap时，map底层为红黑树，unordermap底层为哈希表。当多个线程同时访问时，如果一个线程在读取数据，而一个线程向红黑树中添加数据时，可能红黑树要发生旋转，而红黑树旋转时需要改变指针等变量，此时读取数据的线程如果读到了还没有彻底完成旋转但是已经改变指针等变量的结点，那么读取的数据就错了。而在哈希桶中同样也是，例如当哈希表进行扩容时，此时读取数据的线程读取的是旧哈希表的数据，然后新哈希表更新了，那么也会出错；或者当向桶里面插入或删除结点时，还有线程在这个桶中读取数据也会出错。所以map和unordermap需要加锁。而基数树是直接开好空间，后面就不会动结构了。基数树的读写是分离的，例如当线程1对一个位置读写的时候，线程2不可能对这个位置读写。