用于记录不同模块所需的共同功能，例如头文件等
哈希桶节点上挂的自由链表，不同模块都会使用
//存放自由链表的下一个内存块地址的位置
static void*& NextObj(void* obj)
{
return *(void**)obj; //指针大小自动识别系统位数
}
//切分好的小内存块的基本单位，构成内存块自由链表
class FreeList
{
public:
//头插，获得新的内存块
void* Push(void* obj)
{
assert(obj);
NextObj(obj) = _freeList;
_freeList = obj;
++_memSize;
return _freeList;
}
//头插范围插入，获得新的范围内存块
void PushRange(void* start, void* end, size_t size) //手动传入范围内存块的内存个数
{
NextObj(end) = _freeList;
_freeList = start;
_memSize += size;
/*int i = 0; //测试bug
void* cur = start;
while (cur)
{
cur = NextObj(cur);
++i;
}
if (size != i)
{
int x = 0;
}*/
}
//头删，消耗（归还）掉新的内存块
void* Pop()
{
assert(_freeList);
void* obj = _freeList;
_freeList = NextObj(obj);
_memSize--;
return obj;
}
//头删范围删除
void PopRange(void*& start, void*& end, size_t size)//输出行参数
{
assert(size <= _memSize);
start = _freeList;
end = start;
//让end走到要删除位置的末尾，因为要改指向下一个的指针。所以少走一步
for (size_t i = 0; i < size - 1; i++)
{
if (end == nullptr)
{
int x = 0;
}
end = NextObj(end);
}
_freeList = NextObj(end);//end 的下一个位置是新的链表起始位置
NextObj(end) = nullptr;
_memSize -= size;
}
bool Empty()
{
return _freeList == nullptr;
}
size_t& MaxSize()
{
return _maxSize;
}
size_t MemSize()
{
return _memSize;
}
private:
void* _freeList = nullptr;
size_t _maxSize = 1; //用于线程缓存区内存不够向中央内存区申请内存时，内存块数量的计数器
//用于慢启动。每次申请内存块后+1，逐步提升申请大小
//第一次就拥有一个内存块所以初始值是1
size_t _memSize = 0; //当前自由链表总共申请的总内存块个数
};
一开始至少要内存对齐到8，不然指针有可能放不下。但是不能都按8对齐，不然早256kb的情况下就要32786个桶，所以先将256划分成不同的大块区间，不同区间采取不同的内存对齐数，这样不同内存块的桶数就是不一样的。
// 线程申请内存范围?? ??? ??? ?内存对齐数?? ??? ?对应桶的范围
// [1,128]?? ??? ??? ??? ??? ?8byte对齐?? ? ? ?freelist[0,16) （0号，8字节）（1号，16字节）。。。
// [128+1,1024]?? ??? ??? ??? ?16byte对齐?? ? ? ?freelist[16,72)? ? （16号，144字节）（17号，160字节）。。。
// [1024+1,8*1024]?? ??? ??? ?128byte对齐?? ? ? ?freelist[72,128)
// [8*1024+1,64*1024]?? ??? ?1024byte对齐 ? ? freelist[128,184)
// [64*1024+1,256*1024]?? ??? ?8*1024byte对齐 ? freelist[184,208)
计算内碎片浪费
假设申请129，内存对齐到16就是144，浪费了15个字节（当前区间内浪费最多的情况），浪费了10.4%。由此类推?
桶数量越多，内存对齐数越小。 分段映射，后期整体内存变大，内存对齐数变大，整体保持平衡
计算申请的真实大小
//计算申请的真实内存大小（相上对齐）
static inline size_t _ApplicationSize(size_t bytes, size_t alignnum) //申请内存，对齐数
{
return (bytes + alignnum - 1) & ~(alignnum - 1);//先向上取到大于当前对齐数的情况（相加的数不能大于对齐数，否则会发生进位）
//再向下取整到alignnum的倍数。这样若内存无法整除alignum就会自动向上进位到alignum的整数倍
//例如假设要求内存为7字节，不发生对齐数进位的最大数是7+7=14,再向下取整到alignum就是8
//简单写法
// 需要进位 不需要进位
// 去掉余数后对齐在增加一个对齐数的大小
//(bytes/alignnum+1)*alignnum 直接返回
}
//计算不同内存大小的内存申请的真实大小
static inline size_t ApplicationSize(size_t bytes)
{
if (bytes <= 128) //不同区间采用不同的对齐数进行对齐
{
return _ApplicationSize(bytes, 8);
}
else if (bytes <= 1024)
{
return _ApplicationSize(bytes, 16);
}
else if (bytes <= 1024 * 8)
{
return _ApplicationSize(bytes, 128);
}
else if (bytes <= 1024 * 64)
{
return _ApplicationSize(bytes, 1024);
}
else if (bytes <= 1024 * 256)
{
return _ApplicationSize(bytes, 8 * 1024);
}
else
{
return _ApplicationSize(bytes, 1<<PAGE_SHIFT);
}
}
内存对齐的时候，对于大于256kb的情况，小于128页。可以按页对齐，这样就可以充分利用到页表结构
计算申请的桶下标
//计算内存块对应的桶的相对下标
//简单写法也可以if判断
static inline size_t _Index(size_t bytes, size_t alignum)
{
return ((bytes + alignum - 1) / alignum) - 1; //根据申请内存的大小向上取整，在算出是当前内存块桶区间你是第几个桶，下标从0开始在减1
}
//计算不同内存块对应的桶真实下标
static inline size_t Index(size_t bytes)
{
//需要将相对位置转化为真实位置
assert(bytes <= MAX_BYTES);
int group_array[4] = { 16,56,56,56 };//每个区间的链个数（计算方法：（当前内存块范围的最大值-上一范围的内存块最大值）/内存对齐数）
if (bytes <= 128)
{
return _Index(bytes, 8);
}
else if (bytes <= 1024)
{
return _Index(bytes - 128, 16) + group_array[0]; //计算出内存申请的相对大小。得减去前面部分的，前面不是按照当前对齐数对齐
}
else if (bytes <= 1024 * 8)
{
return _Index(bytes - 1024, 128) + group_array[0] + group_array[1];
}
else if (bytes <= 1024 * 64)
{
return _Index(bytes - 1024 * 8, 1024) + group_array[0] + group_array[1] + group_array[2];
}
else if (bytes <= 1024 * 256)
{
return _Index(bytes - 1024 * 64, 1024 * 8) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
}
else
{
assert(false);
return -1;
}
}
?尽量用移位操作，因为频繁调用。
需要通过页号来管理，跟地址类似。重点在于数据范围，假设页是8k的话，一共有?2^19,unsigend int就能放下，64位系统下 ，假设系统页8k?? ?2^64/2^13 = 2^51，需要usigned long long,所以需要采取条件编译
//在中央内存区管理多个连续页大块内存跨度结构（pagecache也用）
class Span
{
public:
PAGE_ID _pageid = 0; //大块内存起始页的页号，范围由系统内存大小和每一页的数据大小决定（可以用于计算物理地址）
//例如 32位系统下，假设系统页8k 2^32/2^13 = 2^19,unsigend int就能放下（4g就是2^32次方）
//64位系统下 ，假设系统页8k 2^64/2^13 = 2^51
size_t _n = 0; //页的数量
size_t _objSize = 0; //当前span内的小对象大小
Span* _next = nullptr; //双向链表
Span* _prev = nullptr;
size_t _useCount = 0; //记录下中央内存区小内存块分给线程缓冲区的使用情况
void* _freeList = nullptr; //挂提供给线程缓存区使用自由链表结构相同
bool _isUse = false; // 是否在被使用（内存合并的时候使用）
};
//管理中央内存区跨度结构，构成中央内存区的桶节点（pagecache也用）
//带头双向循环链表
class SpanList
{
public:
SpanList()
{
_head = new Span;
_head->_next = _head;
_head->_prev = _head;
}
std::mutex& Getmtx()
{
return _mtx;
}
Span* Begin()
{
return _head->_next;
}
Span* End()
{
return _head;
}
bool Empty()
{
return Begin() == End();
}
void PushFront(Span* span)
{
Insert(Begin(), span);
}
Span* PopFront()
{
Span* ret = _head->_next;
Erase(ret);
return ret;
}
void Insert(Span* pos, Span* newSpan) //双链表插入
{ //获得桶节点
assert(pos);
assert(newSpan);
Span* prev = pos->_prev;
prev->_next = newSpan;
newSpan->_prev = prev;
newSpan->_next = pos;
pos->_prev = newSpan;
}
void Erase(Span* pos) //归还桶节点给page，不用真的删还给下一层
{
assert(pos);
assert(pos != _head);
Span* prev = pos->_prev;
Span* next = pos->_next;
prev->_next = next;
next->_prev = prev;
}
private:
Span* _head; //循环链表头节点
std::mutex _mtx; // 每个桶节点的锁
};
//一次thread cache从中心缓存获取多少个
//慢启动类比拥塞控制
static size_t NumMovesize(size_t size)
{
assert(size > 0);
//[2, 512] ，一次批量移动多少个对象的(慢启动)上限值
//每次挪动数据的公式为 MAX_BYTES/当前想要获取的内存大小
//大内存每批次提供的内存块数量少
//小内存每批次提供的内存快数量大
size_t num = MAX_BYTES / size;
if (num < 2)
{
num = 2;
}
else if (num > 512)//防止每批提供的内存块数量过多或过少
{
num = 512;
}
return num;
}
//计算机一次获取几个页
static size_t NumMovePage(size_t size) //pagecache使用
{
//我们先要获得申请的内存块个数
//再根据这个大小计算出需要多少页才能放下
size_t num = NumMovesize(size);
size_t npage = num * size; //总共要申请的内存大小
npage >>= PAGE_SHIFT; //转换成对应的页大小（除8k）
if (npage == 0) //不足一页的要补成一页
{
npage = 1;
}
return npage;
}