search

Winter-Win / ConcurrentMemoryPool

154 stars 41 forks source link

readme

ConcurrentMemoryPool

之前是在其它的仓库里面进行更新，现在把他拿出来，以便于更好的管理和分享，也为了让大家可以和我一起研究

实现一个高并发的内存池

1. 什么是内存池

1.1 池化技术

1.2 内存池

2.2 申请效率问题 例如：我们上学家里给生活费一样，假设一学期的生活费是6000块。 方式1：开学时6000块直接给你，自己保管，自己分配如何花。 方式2：每次要花钱时，联系父母，父母转钱。 同样是6000块钱，第一种方式的效率肯定更高，因为第二种方式跟父母的沟通交互成本太高了。 同样的道理，程序就像是上学的我们，操作系统就像父母，频繁申请内存的场景下，每次需要内存，都像系统申请效率必然有影响。

3.内存池设计

3.1 为什么要使用内存池

3.2 内存池的演变

注：怎么实现每个线程都拥有自己唯一的线程缓存呢？ 为了避免加锁带来的效率，在Thread Cache中使用（tls）thread local storage保存每个线程本地的Thread Cache的指针，这样Thread Cache在申请释放内存是不需要锁的。因为每一个线程都拥有了自己唯一的一个全局变量。 TLS分为静态的和动态的： 静态的TLS是：直接定义 动态的TLS是：调用系统的API去创建的，我们这个项目里面用到的就是静态的TLS https://blog.csdn.net/evilswords/article/details/8191230 https://blog.csdn.net/yusiguyuan/article/details/22938671 4.2 设计Thread Cache 在这里插入图片描述 ThreadCache.h:

#pragma once

#include "Common.h"

class ThreadCache
{
private:
    Freelist _freelist[NLISTS];//自由链表

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);
};

//静态的，不是所有可见
//每个线程有个自己的指针, 用(_declspec (thread))，我们在使用时，每次来都是自己的，就不用加锁了
//每个线程都有自己的tlslist
_declspec (thread) static ThreadCache* tlslist = nullptr;

申请内存:

释放内存：

4.3 对齐大小的设计（对齐规则）

//专门用来计算大小位置的类
class SizeClass
{
public:
    //获取Freelist的位置
    inline static size_t _Index(size_t size, size_t align)
    {
        size_t alignnum = 1 << align;  //库里实现的方法
        return ((size + alignnum - 1) >> align) - 1;
    }

    inline static size_t _Roundup(size_t size, size_t align)
    {
        size_t alignnum = 1 << align;
        return (size + alignnum - 1)&~(alignnum - 1);
    }

public:
    // 控制在12%左右的内碎片浪费
    // [1,128]              8byte对齐 freelist[0,16)
    // [129,1024]           16byte对齐 freelist[16,72)
    // [1025,8*1024]        128byte对齐 freelist[72,128)
    // [8*1024+1,64*1024]   1024byte对齐 freelist[128,184)

    inline static size_t Index(size_t size)
    {
        assert(size <= MAX_BYTES);

        // 每个区间有多少个链
        static int group_array[4] = { 16, 56, 56, 56 };
        if (size <= 128)
        {
            return _Index(size, 3);
        }
        else if (size <= 1024)
        {
            return _Index(size - 128, 4) + group_array[0];
        }
        else if (size <= 8192)
        {
            return _Index(size - 1024, 7) + group_array[0] + group_array[1];
        }
        else//if (size <= 65536)
        {
            return _Index(size - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
        }
    }

    // 对齐大小计算，向上取整
    static inline size_t Roundup(size_t bytes)
    {
        assert(bytes <= MAX_BYTES);

        if (bytes <= 128){
            return _Roundup(bytes, 3);
        }
        else if (bytes <= 1024){
            return _Roundup(bytes, 4);
        }
        else if (bytes <= 8192){
            return _Roundup(bytes, 7);
        }
        else {//if (bytes <= 65536){
            return _Roundup(bytes, 10);
        }
    }

    //动态计算从中心缓存分配多少个内存对象到ThreadCache中
    static size_t NumMoveSize(size_t size)
    {
        if (size == 0)
            return 0;

        int num = (int)(MAX_BYTES / size);
        if (num < 2)
            num = 2;

        if (num > 512)
            num = 512;

        return num;
    }

    // 根据size计算中心缓存要从页缓存获取多大的span对象
    static size_t NumMovePage(size_t size)
    {
        size_t num = NumMoveSize(size);
        size_t npage = num*size;
        npage >>= PAGE_SHIFT;
        if (npage == 0)
            npage = 1;
        return npage;
    }
};

4.4 设计Thread Cache

CentralCache.h:

#pragma once

#include "Common.h"

//上面的ThreadCache里面没有的话，要从中心获取

/*
进行资源的均衡，对于ThreadCache的某个资源过剩的时候，可以回收ThreadCache内部的的内存
从而可以分配给其他的ThreadCache
只有一个中心缓存，对于所有的线程来获取内存的时候都应该是一个中心缓存
所以对于中心缓存可以使用单例模式来进行创建中心缓存的类
对于中心缓存来说要加锁
*/

//设计成单例模式
class CentralCache
{
public:
    static CentralCache* Getinstence()
    {
        return &_inst;
    }

    //从page cache获取一个span
    Span* GetOneSpan(SpanList& spanlist, size_t byte_size);

    //从中心缓存获取一定数量的对象给threa cache
    size_t FetchRangeObj(void*& start, void*& end, size_t n, size_t byte_size);

    //将一定数量的对象释放给span跨度
    void ReleaseListToSpans(void* start, size_t size);

private:
    SpanList _spanlist[NLISTS];

private:
    CentralCache(){}//声明不实现，防止默认构造，自己创建

    CentralCache(CentralCache&) = delete;
    static CentralCache _inst;
};

申请内存：

释放内存：

特别关心：什么是span?一个span是由多个页组成的一个span对象。一页大小是4k。

//Span是一个跨度，既可以分配内存出去，也是负责将内存回收回来到PageCache合并
//是一链式结构，定义为结构体就行，避免需要很多的友元
struct Span
{
    PageID _pageid = 0;//页号
    size_t _npage = 0;//页数

    Span* _prev = nullptr;
    Span* _next = nullptr;

    void* _list = nullptr;//链接对象的自由链表，后面有对象就不为空，没有对象就是空
    size_t _objsize = 0;//对象的大小

    size_t _usecount = 0;//对象使用计数,
};

特别关心：关于spanlist，设计为一个双向链表，插入删除效率较高。

//和上面的Freelist一样，各个接口自己实现，双向带头循环的Span链表
class SpanList
{
public:
    Span* _head;
    std::mutex _mutex;

public:
    SpanList()
    {
        _head = new Span;
        _head->_next = _head;
        _head->_prev = _head;
    }

    ~SpanList()//释放链表的每个节点
    {
        Span * cur = _head->_next;
        while (cur != _head)
        {
            Span* next = cur->_next;
            delete cur;
            cur = next;
        }
        delete _head;
        _head = nullptr;
    }

    //防止拷贝构造和赋值构造，将其封死，没有拷贝的必要，不然就自己会实现浅拷贝
    SpanList(const SpanList&) = delete;
    SpanList& operator=(const SpanList&) = delete;

    //左闭右开
    Span* Begin()//返回的一个数据的指针
    {
        return _head->_next;
    }

    Span* End()//最后一个的下一个指针
    {
        return _head;
    }

    bool Empty()
    {
        return _head->_next == _head;
    }

    //在pos位置的前面插入一个newspan
    void Insert(Span* cur, Span* newspan)
    {
        Span* prev = cur->_prev;

        //prev newspan cur
        prev->_next = newspan;
        newspan->_next = cur;

        newspan->_prev = prev;
        cur->_prev = newspan;
    }

    //删除pos位置的节点
    void Erase(Span* cur)//此处只是单纯的把pos拿出来，并没有释放掉，后面还有用处
    {
        Span* prev = cur->_prev;
        Span* next = cur->_next;

        prev->_next = next;
        next->_prev = prev;
    }

    //尾插
    void PushBack(Span* newspan)
    {
        Insert(End(), newspan);
    }

    //头插
    void PushFront(Span* newspan)
    {
        Insert(Begin(), newspan);
    }

    //尾删
    Span* PopBack()//实际是将尾部位置的节点拿出来
    {
        Span* span = _head->_prev;
        Erase(span);

        return span;
    }

    //头删
    Span* PopFront()//实际是将头部位置节点拿出来
    {
        Span* span = _head->_next;
        Erase(span);

        return span;
    }

    void Lock()
    {
        _mutex.lock();
    }

    void Unlock()
    {
        _mutex.unlock();
    }
};

特别关心：怎么才能将Thread Cache中的内存对象还给它原来的span呢？ 答：可以在Page Cache中维护一个页号到span的映射，当Span Cache给Central Cache分配一个span时，将这个映射更新到unordered_map中去，在Thread Cache还给Central Cache时，可以查这个unordered_map找到对应的span。 4.5 设计Page Cache

PageCache.h

#pragma once

#include "Common.h"

//对于Page Cache也要设置为单例，对于Central Cache获取span的时候
//每次都是从同一个page数组中获取span
//单例模式
class PageCache
{
public:
    static PageCache* GetInstence()
    {
        return &_inst;
    }

    Span* AllocBigPageObj(size_t size);
    void FreeBigPageObj(void* ptr, Span* span);

    Span* _NewSpan(size_t n);
    Span* NewSpan(size_t n);//获取的是以页为单位

    //获取从对象到span的映射
    Span* MapObjectToSpan(void* obj);

    //释放空间span回到PageCache，并合并相邻的span
    void ReleaseSpanToPageCache(Span* span);

private:
    SpanList _spanlist[NPAGES];
    //std::map<PageID, Span*> _idspanmap;
    std::unordered_map<PageID, Span*> _idspanmap;

    std::mutex _mutex;
private:
    PageCache(){}

    PageCache(const PageCache&) = delete;
    static PageCache _inst;
};

申请内存：

释放内存：

4.6 向系统申请内存