本项目实现了一个高并发内存池，项目原型是google的开源项目tcmalloc，通过对核心代码的总结，实现了高效的多线程内存管理，用于替代系统的内存分配相关的函数（malloc、free）。
项目需要的技术栈：C/C++，数据结构（链表、哈希桶），操作系统内存管理，单例模式，多线程，互斥锁。
所谓“池化技术”，就是程序先向系统申请过量的资源，然后自己管理，以备不时之需。之所以要申请过量的资源，是因为每次申请该资源都有较大的开销，不如提前申请好了，这样使用时就会变得非常快捷，大大提高程序运行效率。
在计算机中，有很多使用“池”这种技术的地方，除了内存池，还有连接池、线程池、对象池等。以服务器上的线程池为例，它的主要思想是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程又进入睡眠状态。
内存池是指程序预先从操作系统申请一块足够大内存，此后，当程序中需要申请内存的时候，不是直接向操作系统申请，而是直接从内存池中获取；同理，当程序释放内存的时候，并不真正将内存返回给操作系统，而是返回内存池。当程序退出(或者特定时间)时，内存池才将之前申请的内存真正释放。
内存池最关注的问题有两点：一是效率问题，二是内存碎片的问题。
由于现代开发环境，很多都是在多线程环境的，所以还需要考虑锁竞争问题。
concurrent memory pool主要由以下3个部分构成：
thread cache：线程缓存是每个线程独有的，用于小于256KB的内存的分配，线程在这里申请内存不需要加锁，因为每个线程独享一个Cache，这也是并发内存池高效的原因之一。
central cache：中心缓存是所有线程共享，thread cache是按需从central cache中获取对象。central cache合适的时机回收thread cache中的对象，避免一个线程占用了太多的内存，而其他线程的内存吃紧，达到内存分配在多个线程中更均衡的按需调度的目的。central cache是存在竞争的，所以从这里取内存对象是需要加锁，首先这里用的是桶锁，其次只有thread cache没有内存对象时才会找central cache一次申请批量的内存对象，所以这里竞争不会很激烈。
page cache：页缓存则是更下一层的缓存，存储的内存以页为单位。central cache没有内存对象时，从page cache分配出一定数量的page，并切割成定长大小的小块内存，分配给central cache。当一个span的几个跨度页的对象都回收以后，page cache会回收central cache满足条件的span对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问题。
ThreadCache是哈希桶结构，一共有208个桶，每个桶对应了一个自由链表。每个自由链表中，分配的块的大小是固定的。每个桶是按照自由链表中内存块的大小来对应映射位置的。 如果从1B到256KB每个字节都分配一个哈希桶，这并不现实。因此，可以采用对齐数的方式。
每个线程都会有一个thread cache对象，这样每个线程在这里获取对象和释放对象时是无锁的。这里用到了线程局部存储，即TLS的技术。
-
当内存大小小于256KB，先到线程自己的threadCache下申请内存对象，计算size大小的内存对象在哪个桶。
-
如果自由链表中有对象，则直接Pop一个内存对象返回。
-
如果自由链表没有对象，则批量地从central cache中申请一定数量的内存对象，并返回一个对象。
当内存大小小于256KB，先计算内存对象size映射的哪个桶，并将对象Push到freelist中。
当链表过长，回收一部分对象到central cache中。
central cache也是一个哈希桶结构，他的哈希桶的映射关系跟thread cache是一样的。不同的是他的每个哈希桶位置挂是SpanList链表结构。
这里有一个新的概念:Span。所谓Span，是一个若干页大小的内存对象。Span用带头双向循环链表的形式串联。方便后续过程中PageCache对Span的回收。Span里面挂的是一个freelist链表结构，是将Span以对象大小进行切割。比如，8B的桶下挂的Span，里面的freelist的对象大小都是8B。
当ThreadCache没有对象时，会从批量地CentralCache中申请内存对象，这里的批量申请用的类似于TCP拥塞控制里面的慢开始算法。如果对于某个内存对象的需求较高，批量数会慢慢增长到一个阈值。由于centralcache的映射规则和threadcache相同，会遍历对应桶下面的Span，如果这个Span存在且不为空，那么就从这个Span的freelist中取出一定数量的内存对象。
如果没有对应桶的所有span都没有内存对象了，会进一步向PageCache申请Span，得到Span后以对象大小进行切割。然后像上一步一样，取出一定的内存对象给threadcache。
每个span中有一个计数use_count，用来计算当前span有多少个内存对象给了threadcache，每分配一个内存对象，就会将计数++。
当threadcache过长或者线程销毁时，会将内存释放给centralcache，释放回来时use_count--，如果这个计数成为0，那么就说明当前span的所有内存对象都被返还了，此时则会将span返还给pagecache，papagecache则会根据前后的空闲页进行合并。
这里有两个问题需要注意：
第一，由于有可能两个线程会同时从一个桶下申请内存对象，因此每个桶必须有一个锁，申请和释放内存时，桶都必须上锁。
第二，threadcache给pagecache返还对象时，怎么挂到对应的span下。这里用到了哈希表，哈希表里面记录了已分配span的所有页号与span的映射，而内存地址又可以很好的转化成页号，因此就可以快速找到对应的span。
PageCache依然用的桶结构，每个桶下挂的一个Span链表。不过此时的映射规则与ThreadCache和CentralCache不同，一共128个桶，即1页到128页。
1.最开始，pagecache中没有任何span对象，只有当有线程申请内存时，pagecache会先使用系统调用，一次性申请128页的span。
2.每次从pagecache中取span时，会先到对应的桶下去找，如果没有，则会遍历后面的桶，直到找到一个桶中有可用的span，然后会把这个span分裂成两个小span。比如申请的是4页的page，最后找到了一个10页大小的span，就会分裂成一个6页的和一个4页的，4页的给上层的centralcache，6页的span挂到对应的桶下。
如果centralcache返还给一个span，就会先根据span里的页号搜寻前一个span和后一个，如果可以合并，就合并，一直循环，直到无法合并。
这里要找到前一个页号对应的span，也需要用到哈希表，pagecache中每个span的第一个页和最后一个页都会与span进行映射。
第一，线程安全的问题，什么时候加锁，什么时候解锁，如果错误程序都会崩溃。
第二，内存碎片的解决，这里主要使用了哈希表这种数据结构，
什么时候要对哈希表进行写？
一是GetOneSpan中，即从把Span从PageCache取到CentralCache时，需要对Span中每一页的页号与Span进行映射。
二是将Span从CentralCache取回PageCache，合并完成后，对Span表示内存块的第一个页号和最后一个页号与Span进行映射。方便下次合并。
什么时候要对哈希表进行读？
一是ReleaseListToSpans中，即把ThreadCache中的Freelist还给ThreadCache时。
二是ConcurrentFree中，要将对应的大内存块释放，需要先得到Span再取出Span中的页号时。
可以看出，哈希表中对同一个页号的读写是分离的！
但是！哈希表依然有线程安全的问题！因为一个线程写的时候可能会改变哈希表结构，因此也就可能造成另一个线程读错误，因此需要加锁。而加锁又会影响效率，能够明显看出，由于读哈希表加锁，导致释放内存比free慢了十倍！
所谓基数树，本质上类似于页表，在项目中我使用了二层基数树，类似于二级页表。基数树在一开始就开辟好了空间，使用过程中不会对基数树的结构有影响。而且读写分离，所以不需要加锁。
最后经过测试，4个线程的环境下，每个线程10000次申请和释放，性能大概在malloc和free的十倍左右。