浅谈定长内存池

· · 科技·工程

0. 前言

很多人在第一次实现内存池时都会比较迷茫（比如我），完全不知道内存应该如何分配，哪些开销是必须的，就很需要一个简单易懂的示例。这里讲解的是较为简单的定长内存池，即每次分配出的内存格大小是固定的。

下为一个windows 64-bit gcc -std=c++11下的no_std实现：

extern"C"{
    void*VirtualAlloc(void*,size_t,unsigned long,unsigned long);
    int VirtualFree(void*,size_t,unsigned long);
}
template<size_t Slot>
struct malloc_pool{
    static_assert((Slot&(Slot-1))==0);
    static_assert(Slot>=0x8);
    static_assert(Slot<=0x10000);
    constexpr static size_t slot=Slot;
    void*first{},*last{},*current{},*block{};
    malloc_pool(){}
    ~malloc_pool(){
        while(block){
            void*to=*reinterpret_cast<void**>(block);
            VirtualFree(block,0,0x02);
            block=to;
        }
    }
    void*allocate(){
        if(first!=last){
            void*ret=first;
            first=reinterpret_cast<void*>(reinterpret_cast<size_t>(first)+slot);
            return ret;
        }else if(current){
            void*ret=current;
            current=*reinterpret_cast<void**>(current);
            return ret;
        }else{
            void*origin=VirtualAlloc(0,0x10000,0x00001000,0x04);
            if(!origin){
                return 0;
            }
            *reinterpret_cast<void**>(origin)=block;
            block=origin;
            void*ret=reinterpret_cast<void*>(reinterpret_cast<size_t>(origin)+slot);
            first=reinterpret_cast<void*>(reinterpret_cast<size_t>(ret)+slot);
            last=reinterpret_cast<void*>(reinterpret_cast<size_t>(origin)+0x10000);
            return ret;
        }
    }
    void deallocate(void*p){
        if(p){
            *reinterpret_cast<void**>(p)=current;
            current=p;
        }
    }
};

下为模式图，其中黄色表示malloc_pool的成员，箭头起点存储了一个指针，指向终点。

1. 可用部分

图中青色部分，利用first（图中第三个黄色正方形）和last（图中第四个黄色正方形表示）存储，代表[first,last)可以使用。

allocate()中的第一个if处理的就是该情况，如果这部分不为空，则返回first并使first后一一格（也就是slot字节）

2. 回收部分

图中蓝色部分，利用current（图中第二个黄色正方形）存储，代表以current为起始的链表上的所有内存格均可用。

首先看deallocate()的实现，让被释放的p指向current，再将current设为p可以将p加入链表。

然后看allocate()中第二个if，如果链表不为空（可以发现如果为空current一定等于0），则返回current并将current设为current指向的地址。注意由于current是一个void*类型的指针，所以指向它的指针应当是void**类型的，所以要先将current转换为void**然后再使用*进行访问。

3. 扩容部分

注意分辨块和格，块包含多个（图中为16个，代码中为0x10000/slot）格。

图中黑色部分，考虑可用部分和回收部分均为空的情况，这是就需要额外开一个块用于存放新的格。

观察allocate()的最后一部分，将first设为新的一块的开头，last设为新的一块的结尾，返回first并将其后移一格。

4. 析构部分

你可能注意到上一节中提到的将first设为新的一块的开头与代码不符，这其实是为了析构函数~malloc_pool()的实现，如果你不需要可以按照上一节提到的方式编写代码。

图中红色部分，考虑析构时应当释放申请的内存。为了确保所有申请的块均被释放，可以在每个块的开头预留出一个格用于存储链表，仿照回收部分实现链表。

分析allocate()的最后一部分和~malloc_pool()，可以看到其逻辑几乎与回收部分相同。

5. 补充说明

一个格内既可以存储数据（恰好一格长）也可以存储指针（可能不满一格），所以Slot必须不小于8。存储指针带来的不佳的空间利用是无法避免的（你可以尝试一下，会发现不太可做）。

回收部分的实现非常重要，在类似vector的使用场景中，会释放大量的空间，如果你不回收这些空间，则问题可能不止MLE：由于没有回收的空间，allocate()会频繁的调用第三部分申请内存，而申请内存通常是极大的开销（也是内存池存在的原因），所以回收部分时不推荐被简化掉的。

0x10000是一页（对于Windows）一块（对于程序）的长度，VirtualFree(block,0,0x02)是释放block，VirtualAlloc(0,0x10000,0x00001000,0x04)是申请块。

6. 定长内存池组装动态长度内存池

namespace malloc_pool_group{
    malloc_pool<0x8>p3;
    malloc_pool<0x10>p4;
    malloc_pool<0x20>p5;
    malloc_pool<0x40>p6;
    malloc_pool<0x80>p7;
    malloc_pool<0x100>p8;
    malloc_pool<0x200>p9;
    malloc_pool<0x400>p10;
    malloc_pool<0x800>p11;
    malloc_pool<0x1000>p12;
    void*allocate(size_t n){
        if(n<=0x8){
            return p3.allocate();
        }
        switch(__builtin_clz(n-1)){
            case 28:{return p4.allocate();}
            case 27:{return p5.allocate();}
            case 26:{return p6.allocate();}
            case 25:{return p7.allocate();}
            case 24:{return p8.allocate();}
            case 23:{return p9.allocate();}
            case 22:{return p10.allocate();}
            case 21:{return p11.allocate();}
            case 20:{return p12.allocate();}
        }
        return VirtualAlloc(0,n,0x00001000,0x04);
    }
    void deallocate(void*p,size_t n){
        if(n<=8){
            p3.deallocate(p);
            return;
        }
        switch(__builtin_clz(n-1)){
            case 28:{p4.deallocate(p);return;}
            case 27:{p5.deallocate(p);return;}
            case 26:{p6.deallocate(p);return;}
            case 25:{p7.deallocate(p);return;}
            case 24:{p8.deallocate(p);return;}
            case 23:{p9.deallocate(p);return;}
            case 22:{p10.deallocate(p);return;}
            case 21:{p11.deallocate(p);return;}
            case 20:{p12.deallocate(p);return;}
        }
        VirtualFree(p,0,0x02);
    }
}
template<typename T>
struct allocator{
    T*allocate(size_t n){
        return static_cast<T*>(malloc_pool_group::allocate(n*sizeof(T)));
    }
    void deallocate(T*p,size_t n){
        malloc_pool_group::deallocate(static_cast<void*>(p),n*sizeof(T));
    }
};

很容易理解，对于每一次allocate(n)，只需找出slot>=n的所有malloc_pool中slot最小的一个。

实现细节：申请段越短，申请越频繁，所以要按照段顺序进行判断；不使用函数指针数组/元模板是因为经测试switch更快；如果太大（大于0x1000）就直接申请；如果不合理（大于0xffffffff）是不用处理的，所以可以用__builtin_clz而非__builtin_clzll。