目录
项⽬介绍
1.这个项⽬做的是什么？
当前项⽬是实现⼀个⾼并发的内存池，他的原型是google的⼀个开源项⽬tcmalloc，tcmalloc全称 Thread-Caching Malloc，即线程缓存的malloc，实现了⾼效的多线程内存管理，⽤于替代系统的内存分配相关的函数（malloc、free）。
2.用到的知识
这个项⽬会⽤到C/C++、数据结构（链表、哈希桶）、操作系统内存管理、单例模式、多线程、互斥锁等等⽅⾯的知识。
小知识点补充
定位new
new(obj) T; 这一行代码是 placement new（定位 new）的使用，它是 C++ 中的一种特殊的内存分配方式。下面我将详细解释它的含义和工作原理，以及如何使用。
什么是 Placement New？
在 C++ 中，new 通常用于动态分配内存并构造对象，例如：
T* obj = new T(); // 这会分配内存并调用T的构造函数
然而，new(obj) T; 则是定位 new（Placement New）的用法。它并不分配内存，而是在指定的内存位置（由 obj 指向的地址）上构造对象。也就是说，obj 必须是一个指向已经分配内存的指针，这块内存已经存在并且足够大来容纳一个 T 类型的对象。
语法结构
new (pointer) T(args);
pointer：指向已分配内存的位置。这块内存已经预先分配好，通常由
malloc、内存池（如你的代码中所示）或者其他方式分配。T：对象的类型。你希望在
pointer指向的内存位置构造一个类型为T的对象。args：传递给
T类型构造函数的参数（如果有的话）。
为什么需要 Placement New？
在常规的 new 操作中，new 关键字不仅分配内存，还会调用构造函数来初始化对象。这样会额外的进行一次内存分配。然而，在很多情况下，你可能已经分配了内存，并且只想在这些内存位置上创建对象。这时，placement new 就非常有用了。
在你的代码中，new(obj) T; 是用来在已经分配好的内存（由 obj 指向）上构造一个类型为 T 的对象。
示例说明
假设你有一个类 MyClass，并且已经预先分配了一块足够大的内存，我们希望在这块内存上构造一个 MyClass 对象。以下是一个简单示例：
1. 传统 new 示例：
class MyClass {
public:
MyClass() {
std::cout << "MyClass Constructor Called!" << std::endl;
}
};
int main() {
MyClass* obj = new MyClass(); // 分配内存并构造对象
delete obj; // 释放内存
return 0;
}
new MyClass()会分配内存并构造一个MyClass对象。使用
delete释放内存。
2. Placement new 示例：
class MyClass {
public:
MyClass() {
std::cout << "MyClass Constructor Called!" << std::endl;
}
};
int main() {
char buffer[sizeof(MyClass)]; // 分配足够大的内存，存放 MyClass 对象
MyClass* obj = new (buffer) MyClass(); // 在 buffer 上构造 MyClass 对象
// 在这里，我们并没有调用 `new MyClass()`，而是直接在 buffer 上构造了对象
return 0;
}
buffer是一个已分配的内存块（大小足够存放一个MyClass对象）。new (buffer) MyClass();在buffer上直接调用MyClass的构造函数，而不需要重新分配内存。
3. 在内存池中使用 Placement New：
在你提供的 ObjectPool 示例中，new(obj) T; 是在已经分配好的内存上构造 T 类型的对象。例如，内存池可能已经为多个对象分配了一大块内存（比如128KB），然后通过 new(obj) T; 在这些内存区域上逐个构造对象。
工作原理
1. 不进行内存分配
placement new 不会调用 operator new（即不会分配内存）。它假定内存已经由你提供，且这块内存足够大。因此，你必须确保传递给 new 的地址指向的内存足够存放一个 T 类型的对象。
2. 调用构造函数
placement new 只是用来调用指定内存位置的构造函数。它实际上是在指定的内存地址上调用了 T 类型的构造函数。
3. 返回对象的指针
new(obj) T; 会返回指向 obj 的指针，指向已经初始化的对象。
为什么不直接使用 new？
通常使用 new 会执行内存分配和对象构造，但是有时你已经有一块内存（例如通过 malloc 或内存池）并且不需要重新分配内存。此时，placement new 就非常有用。
内存池场景中的应用
在内存池的实现中，常常会通过一次性分配大块内存，并在这块内存上“定位”地创建多个对象。例如，你可能为内存池分配了128KB的内存，然后在这个内存块中管理多个对象。当你需要一个新的对象时，你只需在这块内存上调用 placement new 来构造对象。
销毁对象有序列表
使用 placement new 构造的对象并不使用普通的 delete 来销毁。普通 delete 会调用析构函数并释放内存，而 placement new 并不负责释放内存。因此，如果你通过 placement new 构造了对象，你需要显式调用对象的析构函数，并确保内存不会泄漏：
obj->~T(); // 显式调用析构函数
总结
new (obj) T;是 placement new，用于在已分配的内存上构造对象。它不会分配内存，而是直接在指定的内存位置上调用构造函数。
适用于内存池、缓存池等需要手动管理内存的场景。
使用时需要保证内存已经分配且足够容纳对象，并且在不再需要时显式销毁对象，释放资源。
这种方法常用于需要精细控制内存和对象生命周期的场合，特别是在内存池管理中，能有效提高性能和内存利用率。
英语单词：
cache:高速缓冲储存器
Align:对齐
concurrent:并发
batch:批量
fetch:拿来
actual:实际
range:范围
benchmark:基准；标准；基准测试
什么是内存池
1.池化技术
所谓 “池化技术”，就是程序先向系统申请过量的资源，然后自己管理，以备不时之需。之所以要请过量的资源，是因为每次申请该资源都有较大的开销，不如提前申请好了，这样使用时就会变得非常快捷，大大提高程序运行效率。
在计算机中，有很多使用 “池” 这种技术的地方，除了内存池，还有连接池、 线程池、对象池等。以服务器上的线程池为例，它的主要思想是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程又进入睡眠状态。
2.内存池
内存池是指程序预先从操作系统申请一块足够大内存，此后，当程序中需要申请内存的时候，不是直接向操作系统申请，而是直接从内存池中获取；同理，当程序释放内存的时候，并不真正将内存返回给操作系统，而是返回内存池。 当程序退出（或者特定时间）时，内存池才将之前申请的内存真正释放。
3.内存池主要解决的问题
内存池主要解决的当然是效率的问题，其次如果作为系统的内存分配器的⻆度，还需要解决⼀下内存碎⽚的问题。那么什么是内存碎⽚呢？
3.1 效率问题
打个通俗的比方就是：问爸爸妈妈要钱买东西，一次次的要效率太低，如果估算好一个月要用到生活费，直接给一个月的，就不用一次一次的要，可以提交很多的效率。
3.2 碎片化
再需要补充说明的是内存碎片分为外碎片和内碎片，上面我们讲的外碎片问题。外部碎片是一些空的连续内存区域太小，这些内存空间不连续，以至于合计的内存足够，但是不能满足一些的内存分配请需求。内部碎片是由于一些对齐的需求 ，导致分配出去的空间中一些内存无法被利用。内碎片问题，我们后面项目就会看到，那会再进行更准确的理解。（创建时申请空间连续，释放时不按申请的顺序释放，会导致这些内存空间不连续）
3.2.1 外碎片
4.了解一下malloc
C/C++中我们要动态申请内存都是通过malloc去申请内存，但是我们要知道，实际我们不是直接去堆获取内存的。
而malloc就是一个内存池。 mallocO相当于向操作系统 “批发”了一块较大的内存空间，然后“零售” 给程序用。当全部 “售完” 或程序有大量的内存需求时，再根据实际需求向操作系统“进货”malloc的实现方式有很多种，一般不同编译器平台用的都是不同的。比如windows的vs系列用的微软自己写的一套，linux gcc用的glibc中的ptmalloc。
一文了解，Linux内存管理，malloc、free 实现原理
先设计⼀个定⻓的内存池
作为程序员（C/C++）我们知道申请内存使用的是malloc， malloc其实就是一个通用的大众货，什么场景下都可以用，但是什么场景下都可以用就意味着什么场景下都不会有很高的性能，下面我们就先来设计一个定长内存池做个开胃菜，当然这个定长内存池在我们后面的高并发内存池中也是有价值的，所以学习他目的有两层，先熟悉一下简单内存池是如何控制的，第二他会作为我们后面内存池的一个基础组件。
创建一个并发内存池(ConcurrentMemoryPool)项目
New的实现
Delete的实现
如果申请的大块内存空间没有用完，freeList又不为空，，可以先将还回来的内存块对象，再次重复利用
处理一下不足
性能测试
脱离malloc直接在堆中
VirtualAlloc:VirtualAlloc_百度百科
brk和mmap:Linux进程分配内存的两种方式--brk() 和mmap() - VinoZhu - 博客园
ObjectPool.h
#pragma once
#include<iostream>
#include<vector>
#include <new>
#include <time.h>
using std::cout;
using std::endl;
#ifdef _WIN32
#include <Windows.h>
#else
// linux下brk mmap等 linux中的头文件
#endif
// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
// linux下brk mmap等
#endif
if (ptr == nullptr)
throw std::bad_alloc();
return ptr;
}
定长内存池
//template<size_t N>
//class ObjectPool
//{};
//用T也可以使定长内存池，因为T也是固定的
template<class T>
class ObjectPool
{
public:
T* New()
{
T* obj = nullptr;
//优先把还回来内存块对象，再次重复利用
if (_freeList)
{
void* next = *((void**)_freeList);
obj = (T*)_freeList;
_freeList = next;
}
else
{
//剩余内存不够一个对象大小时，则重新开大块空间
if (_remainByrtes < sizeof(T))
{
_remainByrtes = 128 * 1024;
//_memory = (char*)malloc(_remainByrtes);//128k的空间
_memory = (char*)SystemAlloc(_remainByrtes >> 13);//128k的空间
//记得检查一下
if (_memory == nullptr)
{
throw std::bad_alloc();
}
}
obj = (T*)_memory;
size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
_memory += objSize;
_remainByrtes -= objSize;
}
//对已经有的空间进行初始化
//定位new，显示调用T的构造对象初始化
//new(obj) T; 是一种在已分配内存中直接构造对象的方法，
//它不会重新分配内存，而是将对象的数据构造到指定的内存位置上。
new(obj)T;
return obj;
}
void Delete(T* obj)
{
//显示调用析构函数清理对象
obj->~T();
//头插
*(void**)obj = _freeList;
_freeList = obj;
}
private:
//用char*更方便因为一个一个字节的加更方便，1字节好控制
//void* _memory;
char* _memory = nullptr;//指向大块内存的指针
void* _freeList = nullptr;//还回来过程链接的自由链表的头指针
size_t _remainByrtes = 0;//大块内存在切分过程中剩余字节空间大小
};
//测试性能
struct TreeNode
{
int _val;
TreeNode* _left;
TreeNode* _right;
TreeNode()
:_val(0)
, _left(nullptr)
, _right(nullptr)
{}
};
void TestObjectPool()
{
// 申请释放的轮次
const size_t Rounds = 3;
// 每轮申请释放多少次
const size_t N = 100000;
std::vector<TreeNode*> v1;
v1.reserve(N);
size_t begin1 = clock();
for (size_t j = 0; j < Rounds; ++j)
{
for (int i = 0; i < N; ++i)
{
v1.push_back(new TreeNode);
}
for (int i = 0; i < N; ++i)
{
delete v1[i];
}
v1.clear();
}
size_t end1 = clock();
std::vector<TreeNode*> v2;
v2.reserve(N);
ObjectPool<TreeNode> TNPool;
size_t begin2 = clock();
for (size_t j = 0; j < Rounds; ++j)
{
for (int i = 0; i < N; ++i)
{
v2.push_back(TNPool.New());
}
for (int i = 0; i < N; ++i)
{
TNPool.Delete(v2[i]);
}
v2.clear();
}
size_t end2 = clock();
cout << "new cost time:" << end1 - begin1 << endl;
cout << "object pool cost time:" << end2 - begin2 << endl;
}
Test.cpp
#include"ObjectPool.h"
int main()
{
TestObjectPool();
return 0;
}
⾼并发内存池整体框架设计
现代很多的开发环境都是多核多线程，在申请内存的场景下，必然存在激烈的锁竞争问题。malloc本身其实已经很优秀，那么我们项目的原型tcmalloc就是在多线程高并发的场景下更胜一筹，所以这次我们实现的内存池需要考虑以下几方面的问题
1. 性能问题。
2. 多线程环境下，锁竞争问题。
3. 内存碎⽚问题
concurrent memory pool主要由以下3个部分构成：
1. thread cache：线程缓存是每个线程独有的，⽤于⼩于256KB的内存的分配，线程从这里申请内存，不需要加锁，每个线程独享⼀个cache，这也就是这个并发线程池高效的地⽅。
2. central cache：中心缓存是所有线程所共享，thread cache是按需从central cache中获取的对
象。central cache合适的时机回收thread cache中的对象，避免⼀个线程占用了太多的内存，而其
他线程的内存吃紧，达到内存分配在多个线程中更均衡的按需调度的目的。central cache是存在竞
争的，所以从这⾥取内存对象是需要加锁，⾸先这⾥⽤的是桶锁，其次只有thread cache的没有内
存对象时才会找central cache，所以这⾥竞争不会很激烈。
3. page cache：页缓存是在central cache缓存上⾯的⼀层缓存，存储的内存是以页为单位存储及分
配的，central cache没有内存对象时，从page cache分配出⼀定数量的page，并切割成定长大小
的小块内存，分配给central cache。当⼀个span的几个跨度页的对象都回收以后，page cache会
回收central cache满⾜条件的span对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问
题。
⾼并发内存池--thread cache
thread cache是哈希桶结构，每个桶是⼀个按桶位置映射⼤⼩的内存块对象的自由链表。每个线程都会有⼀个thread cache对象，这样每个线程在这⾥获取对象和释放对象时是无锁的。
申请内存：
1. 当内存申请size
2. 如果自由链表_freeLists[i]中有对象，则直接Pop⼀个内存对象返回。
3. 如果_freeLists[i]中没有对象时，则批量从central cache中获取⼀定数量的对象，插⼊到自由链表并返回⼀个对象。
释放内存：
1. 当释放内存⼩于256k时将内存释放回thread cache，计算size映射自由链表桶位置i，将对象Push 到_freeLists[i]。
2. 当链表的⻓度过⻓，则回收⼀部分内存对象到central cache。
计算对象大小的对齐映射规则
// 整体控制在最多10%左右的内碎⽚浪费
// [1,128] 8byte对⻬ freelist[0,16)
// [128+1,1024] 16byte对⻬ freelist[16,72)
// [1024+1,81024] 128byte对⻬ freelist[72,128)
// [8*1024+1,641024] 1024byte对⻬ freelist[128,184)
// [64*1024+1,256*1024] 8*1024byte对⻬ freelist[184,208)
//计算对象大小的对齐映射规则
class SizeClass
{
public:
// 整体控制在最多10%左右的内碎片浪费
// [1,128] 8byte对齐 freelist[0,16)
// [128+1,1024] 16byte对齐 freelist[16,72)
// [1024+1,81024] 128byte对齐 freelist[72,128)
// [8*1024+1,641024] 1024byte对齐 freelist[128,184)
// [64*1024+1,256*1024] 8*1024byte对齐 freelist[184,208)
//简单版本计算对齐数
//size_t _RoundUp(size_t size, size_t alignNum)
//{
// size_t alignSize;
// if (size % alignNum != 0)
// {
// alignSize = (size / alignNum + 1) * alignNum;
// }
// else
// {
// alignSize = size;
// }
// return alignSize;
//}
//复杂版本计算对齐数
static inline size_t _RoundUp(size_t bytes, size_t AlignNum)
{
return (((bytes)+AlignNum - 1) & ~(AlignNum - 1));
}
//对齐大小计算
static inline size_t RoundUp(size_t size)
{
if (size <= 128)
{
return _RoundUp(size, 8);//8字节对齐
}
else if (size <= 1024)
{
return _RoundUp(size, 16);//16字节对齐
}
else if (size <= 8*1024)
{
return _RoundUp(size, 128);//128字节对齐
}
else if (size <= 64*1024)
{
return _RoundUp(size, 1024);//1024字节对齐
}
else if (size <= 256*1024)
{
return _RoundUp(size, 8*1024);//8字节对齐
}
else
{
assert(false);
return -1;
}
}
};
代码实现：
Common.h
#pragma once
#include<iostream>
#include<vector>
#include <new>
#include <time.h>
#include <assert.h>
using std::cout;
using std::endl;
void*& NextObj(void* obj)
{
return *(void**)obj;
}
//管理切分好的小对象的自由链表
class FreeList
{
public:
void Push(void* obj)
{
assert(obj);
//头插
//*(void**)obj = _freeList;
NextObj(obj) = _freeList;
_freeList = obj;
}
void* Pop()
{
assert(_freeList);
//头删
void* obj = _freeList;
_freeList = NextObj(obj);
}
private:
void* _freeList;
};
ThreadCache.h
#pragma once
#include"Common.h"
class ThreadCache
{
public:
// 申请和释放内存对象
void* Allocate(size_t size);
void Deallocate(void* ptr, size_t size);
private:
FreeList _freeLists[];
};解决thread cache的锁问题
⾼并发内存池--central cache
central cache也是一个哈希桶结构，他的哈希桶的映射关系跟thread cache是一样的。不同的是他的每个哈希桶位置挂是SpanList链表结构，不过每个映射桶下面的span中的大内存块被按映射关系切成了一个个小内存块对象挂在span的自由链表中。
申请内存：
1. 当thread cache中没有内存时，就会批量向central cache申请⼀些内存对象，这⾥的批量获取对象 的数量使⽤了类似⽹络tcp协议拥塞控制的慢开始算法；central cache也有⼀个哈希映射的 spanlist，spanlist中挂着span，从span中取出对象给thread cache，这个过程是需要加锁的，不 过这⾥使⽤的是⼀个桶锁，尽可能提⾼效率。
2. central cache映射的spanlist中所有span的都没有内存以后，则需要向page cache申请⼀个新的 span对象，拿到span以后将span管理的内存按⼤⼩切好作为⾃由链表链接到⼀起。然后从span中 取对象给thread cache。
3. central cache的中挂的span中use_count记录分配了多少个对象出去，分配⼀个对象给thread cache，就++use_count
释放内存：
1. 当thread_cache过⻓或者线程销毁，则会将内存释放回central cache中的，释放回来时-- use_count。当use_count减到0时则表⽰所有对象都回到了span，则将span释放回page cache， page cache中会对前后相邻的空闲⻚进⾏合并。
CentralCache.h
#pragma once
#include"Common.h"
//单例模式（饿汉）
class CentralCache
{
public:
static CentralCache* GetInstance()
{
//饿汉模式在main函数之前就创建了，main函数之前不存在多线程，没有线程安全问题
return &_sInst;
}
// 获取一个非空的span
Span* GetOneSpan(SpanList& list, size_t byte_size);
// 从中心缓存获取一定数量的对象给 thread cache
size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t byte_size);
private:
//构造函数初始化，初始化列表阶段，
// 不写构造函数，默认会对自定义类型成员进行初始化
SpanList _spanLists[NFREELIST];
private:
CentralCache() {}
//防拷贝
CentralCache(const CentralCache&) = delete;
//只是声明，不是定义，因为是static
static CentralCache _sInst;
};Common.h
#pragma once
#include<iostream>
#include<thread>
#include<vector>
#include<algorithm>
#include <new>
#include <time.h>
#include <assert.h>
#include <mutex>
using std::cout;
using std::endl;
static const size_t MAX_BYTES = 256;//最大内存k
static const size_t NFREELIST = 256;//总的桶个数
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#elif
//Linux的
#endif
static void*& NextObj(void* obj)
{
return *(void**)obj;
}
//管理切分好的小对象的自由链表
class FreeList
{
public:
void Push(void* obj)
{
assert(obj);
//头插
//*(void**)obj = _freeList;
NextObj(obj) = _freeList;
_freeList = obj;
}
void PushRange(void* start, void* end)
{
NextObj(end) = _freeList;
_freeList = start;
}
void* Pop()
{
assert(_freeList);
//头删
void* obj = _freeList;
_freeList = NextObj(obj);
return obj;
}
bool Empty()
{
return _freeList == nullptr;
}
size_t& MaxSize()
{
return _maxSize;
}
private:
void* _freeList = nullptr;
size_t _maxSize = 1;
};
//计算对象大小的对齐映射规则
class SizeClass
{
public:
// 整体控制在最多10%左右的内碎片浪费
// [1,128] 8byte对齐 freelist[0,16)
// [128+1,1024] 16byte对齐 freelist[16,72)
// [1024+1,81024] 128byte对齐 freelist[72,128)
// [8*1024+1,641024] 1024byte对齐 freelist[128,184)
// [64*1024+1,256*1024] 8*1024byte对齐 freelist[184,208)
//简单版本计算对齐数
//size_t _RoundUp(size_t size, size_t alignNum)
//{
// size_t alignSize;
// if (size % alignNum != 0)
// {
// alignSize = (size / alignNum + 1) * alignNum;
// }
// else
// {
// alignSize = size;
// }
// return alignSize;
//}
//复杂版本计算对齐数
static inline size_t _RoundUp(size_t bytes, size_t AlignNum)
{
return (((bytes)+AlignNum - 1) & ~(AlignNum - 1));
}
//对齐大小计算
static inline size_t RoundUp(size_t size)
{
if (size <= 128)
{
return _RoundUp(size, 8);//8字节对齐
}
else if (size <= 1024)
{
return _RoundUp(size, 16);//16字节对齐
}
else if (size <= 8*1024)
{
return _RoundUp(size, 128);//128字节对齐
}
else if (size <= 64*1024)
{
return _RoundUp(size, 1024);//1024字节对齐
}
else if (size <= 256*1024)
{
return _RoundUp(size, 8*1024);//8字节对齐
}
else
{
assert(false);
return -1;
}
}
//简单计算桶的下标
//size_t _Index(size_t bytes, size_t alignNum)
//{
// if (bytes % alignNum == 0)
// {
// return bytes / alignNum - 1;
// }
// else
// {
// return bytes / alignNum;
// }
//}
//复杂计算桶的下标
static inline size_t _Index(size_t bytes, size_t align_shift)
{
return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
}
// 计算映射的哪⼀个自由链表桶
static inline size_t Index(size_t bytes)
{
assert(bytes <= MAX_BYTES);
// 每个区间有多少个链
static int group_array[4] = { 16, 56, 56, 56 };
if (bytes <= 128) {
return _Index(bytes, 3);
}
else if (bytes <= 1024) {
return _Index(bytes - 128, 4) + group_array[0];
}
else if (bytes <= 81024) {
return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
}
else if (bytes <= 64 * 1024) {
return _Index(bytes - 8 * 1024, 10) + group_array[2] +
group_array[1] + group_array[0];
}
else if (bytes <= 256 * 1024) {
return _Index(bytes - 64 * 1024, 13) + group_array[3] +
group_array[2] + group_array[1] + group_array[0];
}
else {
assert(false);
}
return -1;
}
// 一次thread cache从中心缓存获取多少个
static size_t NumMoveSize(size_t size)
{
assert(size > 0);
// [2, 512], 一次批量移动多少个对象的(慢启动)上限值
// 小对象一次批量上限高
// 小对象一次批量上限低
int num = MAX_BYTES / size;
if (num < 2)
num = 2;
if (num > 512)
num = 512;
return num;
}
};
// 管理多个连续页大块内存跨度结构
struct Span {
PAGE_ID _pageId = 0; // 大块内存起始页的页号
size_t _n = 0; // 页的数量
Span* _next = nullptr; // 双向链表的结构
Span* _prev = nullptr;
size_t _useCount = 0; // 切好小块内存，被分配给thread cache的计数
void* _freeList = nullptr; // 切好的小块内存的自由链表
};
class SpanList
{
public:
SpanList()
{
_head = new Span;
_head->_next = _head;
_head->_prev = _head;
}
void Insert(Span*pos,Span*newSpan)
{
assert(newSpan);
assert(pos);
Span* prev = pos->_prev;
// prev newspan pos
prev->_next = newSpan;
newSpan->_prev = prev;
newSpan->_next = pos;
pos->_prev = newSpan;
}
void Erase(Span* pos)
{
assert(pos);
assert(pos != _head);
Span* prev = pos->_prev;
Span* next = pos->_next;
prev->_next = next;
next->_prev = prev;
}
private:
Span* _head;
public:
std::mutex _mtx;//桶锁
};
CentralCache.cpp
#include "CentralCache.h"
CentralCache CentralCache::_sInst;
// 获取一个非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
{
// ...
return nullptr;
}
// 从中心缓存获取一定数量的对象给thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)
{
size_t index = SizeClass::Index(size);
_spanLists[index]._mtx.lock();
Span* span = GetOneSpan(_spanLists[index], size);
assert(span);
assert(span->_freeList);
//从span中获取batchNum个对象
//如果不够batchNum个，有多少拿多少
start = span->_freeList;
end = start;
size_t i = 0;
size_t actualNum = 1;
while ((i < batchNum - 1 && NextObj(end) != nullptr))
{
end = NextObj(end);
++i;
++actualNum;
}
span->_freeList = NextObj(end);
NextObj(end) = nullptr;
_spanLists[index]._mtx.unlock();
return actualNum;
}
ThreadCache.cpp
#include"ThreadCache.h"
#include"CentralCache.h"
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size) {
// 慢开始反馈调节算法
// 1. 最开始不会一次向central cache一次批量要太多，因为要太多了可能用不完
// 2. 如果你不断需要这个size大小内存需求，那么batchNum就会不断增长，直到上限
// 3. size越大，一次向central cache要的batchNum就越小
// 4. size越小，一次向central cache要的batchNum就越大
size_t batchNum = std::min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
if (_freeLists[index].MaxSize() == batchNum)
{
_freeLists[index].MaxSize() += 1;
}
void* start = nullptr;
void* end = nullptr;
//实际多少个，因为可能存在供不应求，但至少有一个
size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
assert(actualNum > 1);
if (actualNum == 1)
{
assert(start == end);
return start;
}
else
{
_freeLists[index].PushRange(NextObj(start), end);
return start;
}
}
// 申请和释放内存对象
void* ThreadCache::Allocate(size_t size)
{
assert(size <= MAX_BYTES);
//算一下对齐大小
size_t alignSize = SizeClass::RoundUp(size);
//哪一个桶里面 下标值index
size_t index = SizeClass::Index(size);
if (!_freeLists[index].Empty())
{
return _freeLists[index].Pop();
}
else
{
//else说明这一个桶对应的自由链表没有 就要去下一层去取了// 从中心缓存获取对象
// void* FetchFromCentralCache(size_t index, size_t size);
return FetchFromCentralCache(index, alignSize);//对齐后的大小
}
}
void ThreadCache::Deallocate(void* ptr, size_t size)
{
assert(size <= MAX_BYTES);
assert(ptr);
//找对映射的自由链表桶，对象插入进去
size_t index = SizeClass::Index(size);
_freeLists[index].Push(ptr);
}⾼并发内存池--page cache
申请内存：
1. 当central cache向page cache申请内存时，page cache先检查对应位置有没有span，如果没有则 向更⼤⻚寻找⼀个span，如果找到则分裂成两个。⽐如：申请的是4⻚page，4⻚page后⾯没有挂 span，则向后⾯寻找更⼤的span，假设在10⻚page位置找到⼀个span，则将10⻚page span分裂 为⼀个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⻚内存。
释放内存：
1. 如果central cache释放回⼀个span，则依次寻找span的前后page id的没有在使⽤的空闲span， 看是否可以合并，如果合并继续向前寻找。这样就可以将切⼩的内存合并收缩成⼤的span，减少内存碎⽚。
从堆中申请内存，页号和地址的关系
在操作系统中，堆内存管理通常涉及将内存分为多个页面，每个页面通常是4KB大小（这个大小可能会根据不同的系统架构而有所不同）。页号和地址之间的关系是直接的，可以通过以下方式计算：
假设我们有以下定义：
PAGE_SIZE是每个页的大小，通常是4KB（即 4096字节）。page_number是页号，一个非负整数。address是内存中的某个地址。
页号和物理地址之间的关系可以通过以下公式计算：
复制
address = page_number * PAGE_SIZE
反过来，如果你有一个内存地址，你可以通过以下公式计算它所在的页号：
复制
page_number = address / PAGE_SIZE
这里的除法是整数除法，它会丢弃任何余数，只保留结果的整数部分。
以下是一个简单的示例，假设PAGE_SIZE是4096：
#include <iostream>
#define PAGE_SIZE 4096 // 4KB
// 函数：根据页号计算地址
uintptr_t getPageAddress(int page_number) {
return static_cast<uintptr_t>(page_number) * PAGE_SIZE;
}
// 函数：根据地址计算页号
int getAddressPageNumber(uintptr_t address) {
return static_cast<int>(address / PAGE_SIZE);
}
int main() {
int page_number = 10; // 示例页号
uintptr_t address = getPageAddress(page_number);
std::cout << "Page " << page_number << " starts at address " << address << std::endl;
// 反过来，根据地址计算页号
int calculated_page_number = getAddressPageNumber(address);
std::cout << "Address " << address << " is on page " << calculated_page_number << std::endl;
return 0;
}
在这个例子中，如果你调用getPageAddress(10)，它将返回页号为10的起始地址，即10 * 4096。如果你有一个地址，比如0x10000（它是4096的十六进制表示），调用getAddressPageNumber(0x10000)将返回页号2，因为0x10000 / 4096 = 2。
内存回收
测试
高并发内存池-使用定长内存池配合脱离使用new
释放对象时优化为不传对象大小
测试+改错
性能优化
