2.内存池

内存池是指程序预先从操作系统申请⼀块⾜够⼤内存，此后，当程序中需要申请内存的时候，不是直接向操作系统申请，⽽是直接从内存池中获取；同理，当程序释放内存的时候，并不真正将内存返回给操作系统，⽽是返回内存池。当程序退出(或者特定时间)时，内存池才将之前申请的内存真正释放。

3.内存池主要解决的问题

1.效率问题：不用每次都向操作系统申请内存，浪费时间

2.内存碎片化问题

        内碎片：由对齐规则产生，等于实际申请大小与对齐后块大小之间的差值

        外碎片：一些空间连续的内存太小，合计内存满足，但是不连续，所有不满足一些内存分配申请

4.malloc

C/C++中我们要动态申请内存都是通过malloc去申请内存，但是我们要知道，实际我们不是直接去堆获取内存的，⽽malloc就是⼀个内存池。malloc() 相当于向操作系统“批发”了⼀块较⼤的内存空间，然后“零售”给程序⽤。当全部“售完”或程序有⼤量的内存需求时，再根据实际需求向操作系统“进货”。

malloc的实现⽅式有很多种，⼀般不同编译器平台⽤的都是不同的。⽐如windows的vs系列⽤的微软⾃⼰写的⼀套，linux gcc⽤的glibc中的ptmalloc。下⾯有⼏篇关于这块的⽂章，⼤概可以去简单看看了解⼀下，关于ptmalloc，有兴趣⼤家可以去看看他的实现细节。

(18 封私信) 一文了解，Linux内存管理，malloc、free 实现原理 - 知乎
malloc()背后的实现原理——内存池 - 阿照的日志
 

三.开胃菜--先设计⼀个定长的内存池

作为程序员(C/C++)我们知道申请内存使⽤的是malloc，malloc其实就是⼀个通⽤的⼤众货，什么场景下都可以⽤，但是什么场景下都可以⽤就意味着什么场景下都不会有很⾼的性能，下⾯我们就先来设计⼀个定⻓内存池做个开胃菜，当然这个定⻓内存池在我们后⾯的⾼并发内存池中也是有价值的，所以学习他⽬的有两层，先熟悉⼀下简单内存池是如何控制的，第⼆他会作为我们后⾯内存池的⼀个基础组件。

windows和Linux下如何直接向堆申请⻚为单位的⼤块内存 ：

ObjectPool.h

#pragma once
#include "Common.h"

// 直接去堆上按⻚申请空间
inline static void* SystemAlloc(size_t kpage) //kpage表示页数
{
#ifdef _WIN32
    void* ptr = VirtualAlloc(0, kpage * (1 << 13), MEM_COMMIT | MEM_RESERVE,PAGE_READWRITE); //参数1：0代表系统随机分配内存，参数2：页数*一页（8k），参数3：MEM_RESERVE：预留一段虚拟地址空间（不占用物理内存）

​​​​MEM_COMMIT：为预留的地址空间分配物理内存（并映射到虚拟地址）参数 4：PAGE_READWRITE：设置分配的内存页权限为 “可读可写”；

#else
    // linux下brk mmap等
#endif
    if (ptr == nullptr)
        throw std::bad_alloc();//分配失败时抛出标准异常
    return ptr;
}
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
    VirtualFree(ptr, 0, MEM_RELEASE);//参数 1：ptr：要释放的内存起始地址,参数 2：0：配合 MEM_RELEASE 使用时，必须设为 0，表示释放整个预留 / 提交的内存块,参数 3：MEM_RELEASE：释放内存块（同时解除物理内存映射和虚拟地址预留）

#else
    // sbrk unmmap等
#endif
}

template<class T>//类型模板参数
class ObjectPool
{
public:
    T* New()
    {
        T* obj = nullptr;

        //优先考虑还回来的内存块对象再次重复利用
        if (_freelist)
        {
            void* next = *(void**)_freelist;//_freelist的下一个节点
            obj = (T*)_freelist;//取头
            _freelist = next;//next为头
        }
        else
        {
            //剩余内存不够一个对象大小时，则重新开大块空间
            if (_remainBytes < sizeof(T))
            {
                _remainBytes = 128 * 1024;//128KB
                //_memory = (char*)malloc(_remainBytes);
                _memory = (char*)SystemAlloc(_remainBytes >> 13);//16页
                if (_memory == nullptr)
                {
                    throw std::bad_alloc();//表示内存分配失败
                }
            }

            obj = (T*)_memory;
            size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);//强制切分出至少指针大小的块，保证释放时能连成链表
            _memory += objSize;//起始地址后移
            _remainBytes -= objSize;//剩余内存减去用了的
        }

        //定位new,显示调用T的构造函数初始化
        new(obj)T;//定位new，对已分配内存的未初始化的指针进行初始化

        return obj;//返回指向申请内存的指针
    }
    void Delete(T* obj)
    {
        //显示调用析构函数
        obj->~T();//仅调用析构函数清理资源，不释放内存

        //头插
       *(void**)obj = (T*)_freelist;//obj指向旧的第一个节点
        _freelist = obj;//obj充当新的第一个节点
    }
private:
    char* _memory;//指向大块内存的指针
    size_t _remainBytes = 0;//大块内存在切分过程中剩余字节数

    void* _freelist;//还回来过程中链接的自由链表的头指针
};

四.高并发内存池整体框架设计

项目源码：项目代码: 关于项目的代码

现代很多的开发环境都是多核多线程，在申请内存的场景下，必然存在激烈的锁竞争问题。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.申请内存：

1. 当内存申请size<=256KB，先获取到线程本地存储的thread cache对象，计算size映射的哈希桶⾃由链表下标i。

2. 如果⾃由链表_freeLists[i]中有对象，则直接Pop⼀个内存对象返回。

3. 如果_freeLists[i]中没有对象时，则批量从central cache中获取⼀定数量的对象，插⼊到⾃由链表并返回⼀个对象。

2.释放内存：

1. 当释放内存⼩于256k时将内存释放回thread cache，计算size映射⾃由链表桶位置i，将对象Push到_freeLists[i]。

2. 当链表的⻓度过⻓，则回收⼀部分内存对象到central cache。

3.TLS--thread local storage：

(18 封私信) Thread Local Storage（线程局部存储）TLS - 知乎

ConcurrentAlloc.h

#pragma once
#include "ThreadCache.h"
#include "PageCache.h"
#include "Common.h"
#include "ObjectPool.h"

//ConcurrentAlloc 是线程安全的入口层，
// 它利用 TLS 为每个线程创建并绑定专属的 ThreadCache，
// 保证了多线程下内存分配的无锁、高效、安全；

static void* ConcurrentAlloc(size_t size)
{
    if (size > MAX_BYTES)
    {
        size_t alignsize = SizeClass::RoundUp(size);
        size_t kpage = alignsize >> PAGE_SHIFT;

        PageCache::GetInstance()->_pagemtx.lock();
        Span* span = PageCache::GetInstance()->NewSpan(kpage);
        span->_objsize = size;
        PageCache::GetInstance()->_pagemtx.unlock();

        void* ptr = (void*)(span->_page << PAGE_SHIFT);//页号 → 物理地址 的转换
        return ptr;
    }
    else
    {
        //通过TLS每个线程无锁的获取自己的专属的ThreadCache对象

        //检查当前线程的本地 ThreadCache 指针是否为空
        if (pTLSThreadCache == nullptr)
        {
            static ObjectPool<ThreadCache> tcpool;
            //如果为空：说明当前线程是第一次申请内存,需要创建专属的对象，并赋值给这个 TLS 指针；
            //pTLSThreadCache = new ThreadCache;//创建 ThreadCache 对象
            pTLSThreadCache = tcpool.New();
        }

        //std::cout << std::this_thread::get_id() << ":" << pTLSThreadCache << std::endl;

        return pTLSThreadCache->Allocate(size);
    }
}

static void ConcurrentFree(void* ptr)
{
    Span* span = PageCache::GetInstance()->MapObjectToSpan(ptr);//通过地址拿到对应的span
    size_t size = span->_objsize;

    if (size > MAX_BYTES)
    {
        Span* span = PageCache::GetInstance()->MapObjectToSpan(ptr);//通过地址拿到对应的span

        PageCache::GetInstance()->_pagemtx.lock();
        PageCache::GetInstance()->ReleaseSpanToPageCache(span);
        PageCache::GetInstance()->_pagemtx.unlock();
    }
    else
    {
        assert(pTLSThreadCache);
        pTLSThreadCache->Deallocate(ptr, size);
    }
}

4.thread cache代码框架：

首先我们先明白在ThreadCache中的一些名词含义。

1. 数组下标（全局桶下标）

• 含义：内存池核心管理数组（存储所有自由链表头指针）的索引值，是整个内存池范围内的全局唯一标识；
• 作用：通过下标可直接定位到对应桶，范围从 0 开始（如 0、1、20、72 等）；
• 举例：下标 0 对应 8B 桶，下标 20 对应 208B 桶，下标 72 对应 1152B 桶。

2. 桶

• 含义：数组下标对应的 “逻辑单元”，是 “固定大小内存块的专属管理单元”；
• 核心特征：一个桶唯一对应一种固定大小的内存块，且仅管理该大小的内存块；
• 本质：桶本身不是实体，是对 “数组下标 + 对应链表” 的统称（如下标 0=8B 桶，下标 20=208B 桶）。

3. 对齐粒度

• 含义：内存大小向上取整的 “最小步长”，是按区间划分的统一规则；
• 作用：将任意申请的内存大小规整为桶能管理的固定大小，避免碎片化；
• 区间规则：
  • [1,128B]：对齐粒度 8B；
  • (128,1024B]：对齐粒度 16B；
  • (1024,8192B]：对齐粒度 128B；
  • 以此类推。

4. 链表（自由链表 / 空闲链表）

• 含义：每个桶绑定的单向链表，节点是该桶对应大小的空闲内存块；
• 作用：管理同大小的空闲内存块，实现高效分配 / 释放（分配时头删、释放时头插）；
• 核心特征：一个桶对应且仅对应一个链表，链表中所有节点的内存块大小完全一致。

关键关联逻辑

通过对齐粒度将任意申请的内存大小规整为固定值 → 根据固定值计算出桶的下标（数组下标） → 定位到唯一的桶 → 该桶通过专属的链表管理所有同大小的空闲内存块。

ThreadCache.h

#pragma once
#include "Common.h"

//ThreadCache本质是由一个哈希映射的对象自由链表构成
//ThreadCache 是线程级内存缓存的外壳，_freelist 是它的内脏——_freelist 
//数组把不同大小的内存块分级管理，ThreadCache 用这套结构实现了无锁、低碎片的内存分配服务。
class ThreadCache
{
public:
    //申请和释放空间
    void* Allocate(size_t size);
    void Deallocate(void* ptr, size_t size);
    //从中心缓存获取对象
    void* FetchFromCentralCache(size_t index, size_t size);

    // 释放对象时，链表过⻓时，回收内存回到中⼼缓存
    void ListTooLong(FreeList& list, size_t size);
private:
    FreeList _freelist[NFREE_LIST];//自由链表数组定义,数组的每个元素都是一个 FreeList 对象，对应一个哈希桶
};

//TLS thread local storage线程本地存储
//为每一个线程创建独立的 pTLSThreadCache 指针副本，每个线程只能访问自己的副本，线程间互不干扰。
static _declspec(thread) ThreadCache* pTLSThreadCache = nullptr;//定义线程本地变量

ThreadCache.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "ThreadCache.h"
#include "CentralCache.h"

void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
    //慢开始反馈调节算法
    //1.最开始不会向centralcache一次批量要太多，可能用不完
    //2.如果不断有这个size大小内存的需求，那么就会不断增长直到上限
    //3.size越大，一次向Central Cache要的batchNum就越小
    //4.size越小，一次向Central Cache要的batchNum就越大
    size_t batchNum=min(_freelist[index].MaxSize(),SizeClass::NumMoveSize(size));//计算一次拿取size大小个数
    if (_freelist[index].MaxSize() == batchNum)
    {
        _freelist[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;//直接返回地址给ptr
    }
    else
    {
        _freelist[index].PushRange(NextObj(start), end, actualNum - 1);//把从第2个开始的内存块插入到链表
        return start;//直接返回第一个内存块地址给ptr
    }
}

void* ThreadCache::Allocate(size_t size)
{
    //空间申请
    assert(size <= MAX_BYTES);
    size_t alignSize = SizeClass::RoundUp(size);//计算实际所分配的大小
    size_t index = SizeClass::Index(size);//计算是桶的全局下标

    //判断此下标桶是否为空
    if (!_freelist[index].Empty())
    {
        //不为空，则Pop出去
        return _freelist[index].Pop(); 
    }
    else
    {
        //为空，没有内存块，向中心缓存获取
        return FetchFromCentralCache(index, alignSize);
    }
}

void ThreadCache::Deallocate(void* ptr, size_t size)
{
    //空间释放
    assert(size <= MAX_BYTES);
    assert(ptr);

    //找出映射的自由链表桶，对象插入进入
    size_t index = SizeClass::Index(size);
    _freelist[index].Push(ptr);

    //当链表长度大于一次批量申请的内存时就开始还一段list给centralcache
    if (_freelist[index].Size() > _freelist[index].MaxSize())
    {
        ThreadCache::ListTooLong(_freelist[index], size);
    }
}

void ThreadCache::ListTooLong(FreeList& list, size_t size)
{
    void* start = nullptr;
    void* end = nullptr;
    list.PopRange(start, end, list.MaxSize());

    CentralCache::GetInstance()->ReleaseListToSpans(start,size);
}

5.自由链表的哈希桶跟对象大小的映射关系

Common.h

#pragma once

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <new> 
#include <thread>
#include <mutex>
#include <assert.h>
#include <time.h>

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;//桶的内存256KB

static const size_t NFREE_LIST = 208;//桶的数量

#ifdef _WIN64
    typedef unsigned long long PAGE_ID;//_WIN64下面_WIN64和_WIN32都会被定义
#elif _WIN32
    typedef size_t PAGE_ID;//_WIN32下面只会定义_WIN32
#endif

#ifdef _WIN32
    #include <Windows.h>
#else
    //linux
#endif

//&是引用，且是 void* 类型的引用，核心作用是让函数返回值可以被赋值（作为左值）
static void*& NextObj(void* obj)
{
    assert(obj != nullptr);
    return *(void**)obj;
}

//管理切分好的小对象的自由链表
//自由链表类---Thread Cache
class FreeList
{
public:
    void Push(void* obj)
    {
        assert(obj);

        //头插
        //*(void**)obj = _freelist;
        NextObj(obj) = _freelist;
        _freelist = obj;
        ++_size;
    }
    void PushRange(void* start, void* end, size_t n)
    {

        //头插入多个
        NextObj(end) = _freelist;
        _freelist = start;
        _size += n;
    }
    void PopRange(void*& start, void*& end, size_t n)
    {

        //头删多个
        assert(n <= _size);
        start = _freelist;
        end = start;
        for (size_t i = 0; i < n - 1; i++)
        {
            if (end == nullptr)
            {
                break;
            }
            end = NextObj(end);
        }
        if(end==nullptr)
        {
            _freelist = nullptr;
        }
        else
        {
            _freelist = NextObj(end);
            NextObj(end) = nullptr;
        }
        _size -= n;
    }

    void* Pop()
    {
        assert(_freelist);

        //头删
        void* obj = _freelist;
        _freelist = NextObj(obj);
        --_size;

        return obj;
    }
    bool Empty()
    {
        //判空
        return _freelist == nullptr;
    }

    size_t& MaxSize() { return _maxsize; }
    size_t Size() { return _size; }
private:
    void* _freelist = nullptr;
    size_t _maxsize = 1;
    size_t _size = 0;
};

class SizeClass
{
    // 整体控制在最多10%左右的内碎⽚浪费
    // 内存大小区间 (字节)     对齐粒度                 对应 freelist 下标区间    桶数量
    // [1,128]                         8byte对⻬                 freelist[0,16)                    16
    // [128+1,1024]                16byte对⻬               freelist[16,72)                 56
    // [1024+1,81024]            128byte对⻬              freelist[72,128)              56
    // [8*1024+1,641024]       1024byte对⻬            freelist[128,184)            56
    // [64*1024+1,256*1024]    8*1024byte对⻬      freelist[184,208)            24

    //size_t _RoundUp(size_t size, size_t alignNum)//普通方法
    //{
    //    size_t alignSize;
    //    if (size % alignNum != 0)
    //    {
    //        alignSize = (size / alignNum + 1) * alignNum;
    //        //计算对齐数  size为9，需要分配16， (9/8 + 1)*8=16
    //    }
    //    else
    //    {
    //        alignSize = size;
    //    }
    //    return alignSize;
    //}

public:

    //计算对象大小的对齐映射规则
    static inline size_t _RoundUp(size_t bytes, size_t align)//性能方法
    {
        return (((bytes)+align - 1) & ~(align - 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*1024字节对齐
        }
        else
        {
            return _RoundUp(size, 1 << PAGE_SHIFT);//以页为单位对齐
        }
    }

    // 计算映射的哪一个自由链表桶
    //size_t _Index(size_t bytes,size_t alignNum)//普通方法
    //{
    //    if (bytes % alignNum == 0)
    //    {
    //        return  bytes / alignNum - 1;// 8/8-1=0
    //    }
    //    else
    //    {
    //        return bytes / alignNum;//9/8=1
    //    }
    //}
    static inline size_t _Index(size_t bytes, size_t align_shift)//性能方法
    {
        return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
        //以8为例，  (8+1<<3-1) >> 3 -1=(8+7)>>3-1=0;
    }
    static inline size_t Index(size_t bytes)
    {
        assert(bytes <= MAX_BYTES);

        // 每个区间有多少个链（16: [1,128]区间桶数；56: 后续三个区间桶数）
        static int group_array[4] = { 16, 56, 56, 56 };

        if (bytes <= 128) 
        {
            return _Index(bytes, 3);//这里的3是2^3=8
        }
        else if (bytes <= 1024) 
        {
            return _Index(bytes - 128, 4) + group_array[0];
        }
        else if (bytes <= 8192) 
        { 
            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;
    }

    //// ⼀次从中⼼缓存获取多少个
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0);

        // 核心公式：用最大可处理字节数 / 单个内存块大小 = 理论最大批量数
        int num = MAX_BYTES / size;

        // 下限：至少批量拿2个（避免频繁向CentralCache申请，减少锁竞争）
        if (num < 2)
            num = 2;

        // 上限：最多批量拿512个（避免一次性拿太多，导致内存浪费/其他线程饥饿）
        if (num > 512)
            num = 512;

        return num;
    }
};

六.central cache