# 为什么使用内存池
1. 避免内存碎片。
2. 避免系统调用开销。

操作系统分用户态和内核态，我们只能在用户态进行操作。我们所使用的内存有栈和堆的，栈的内存自动分配和回收。对于程序员来说，主动申请和释放的内存是堆的内存。比如 `malloc()`、`free()`。
我们调用 `malloc()` 向堆申请内存，系统也分配给了我们。但是我们申请的这部分内存容易造成内部碎片，这会导致残缺的内存块不能被我们所利用。比如申请 4k 的内存块，系统剩余的内存空间也够。但是这些是不连续的，连续的块可能只有 2k 大小，那么就会发生内存分配失败的情况。
如果是公司级别的程序，不像个人写的 demo。那么随着服务器长久时间的运行，可能会出现不断蚕食剩余内存的情况，这种内存问题很难排查。
除此之外，malloc 是会涉及用户态和内核态转换的。经常这样转换会影响服务器性能，我们应尽量避免直接向系统申请内存。
因此我们需要内存池来解决上述问题，本质就是程序员自己设置一套管理内存的手段。我们向系统申请大块的内存并交由内存池来管理，编程中对应内存的申请和释放就交给内存池来处理了。这样出问题了，我们也可以从内存池那里先排查，更容易发现内存相关的问题。
**内存池实现不太容易，个人造内存相关的轮子容易出bug，企业级别的内存池更加有保障一些。比较出名的内存池有 jemalloc 和 tcmalloc，这两个都是全局内存池，比较推荐使用 tcmalloc。**
# 全局内存池还是局部内存池
如果现在有一个服务器，他时不时会接受新用户的连接。而我们将实现一个内存池用于管理内存，我们应该考虑将内存池设计成全局还是非全局形式。

1. 使用一个全局内存池，这样实现比较困难。对于内存块的回收更是令人头疼（我们从内存池分配出来的内存），好在我们可以使用jemalloc/tcmalloc
2. 针对每一个连接建立一个内存池，连接销毁释放内存池。这种情况下，这个内存池的生命周期就和这个连接的生命周期是一样的了。我们就不考虑小块的回收问题了。
# 内存池设计思想
这里参照 Nginx 的内存池设计思想，Nginx 内存池设计思路精巧简单，没有那么复杂。Nginx 每收到一个请求，就创建一个内存池给新连接使用，请求处理完成后释放内存池，因此内存池并非是单例模式的。
Ngin 将内存分为大块内存和小块内存来管理，对于小块内存，用户申请后不需要主动释放，而是等待释放内存池时再释放。对于大块内存，用户可以调用相关接口进行释放，也可以等内存池释放时再释放。因此，Nginx 对于小块内存的回收并不是很在意。
同时 Nginx 内存池支持增加回调函数，当内存池释放时，自动调用回调函数释放用户申请的资源。回调函数允许增加多个，通过链表进行链接，在内存池释放时被逐一调用。
Nginx 创建内存池会先申请 PAGE_SIZE 内存，我称为 block。一部分用来容纳 ngx_pool_t 结构体，另一部分内存则是用于满足用户申请。ngx_pool_data_t 结构体中的 last 指针和 end 指针之间的内存是空闲的，当用户申请小块内存时，如果空闲的内存大小满足用户的需求，则可以分配给用户。
## 管理内存块的结点
![1669112895386.png](https://cdn.nlark.com/yuque/0/2022/png/26752078/1669112902652-afae0f9d-d616-435f-b40d-540c1b055bc9.png#averageHue=%23fcf0ca&clientId=u8e162442-b6f3-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=600&id=ucea5d58c&margin=%5Bobject%20Object%5D&name=1669112895386.png&originHeight=750&originWidth=1151&originalType=binary&ratio=1&rotation=0&showTitle=false&size=35521&status=done&style=none&taskId=u46ccc8da-09b7-4970-98dc-ab02aaad40c&title=&width=920.8)

1. end_：指向当前 block 块的结尾。
2. last_：指向当前 block 块的使用位置。
3. quote_：表示该 block 块的被引用次数。
4. failed_：表示该 block 块的失效次数。
5. next_：指向下一个 block 块。
```cpp
struct SmallNode
{
    unsigned char* end_;     // 该块的结尾
    unsigned char* last_;    // 该块目前使用位置
    unsigned int quote_;     // 该块被引用次数
    unsigned int failed_;    // 该块失效次数
    struct SmallNode* next_; // 指向下一个块
}; 

struct LargeNode
{
    void* address_;          // 该块的起始地址
    unsigned int size_;      // 该块大小
    struct LargeNode* next_; // 指向下一个大块
};
```
## 内存池结构
```cpp
struct Pool
{
    LargeNode* largeList_;   // 管理大块内存链表
    SmallNode* head_;        // 头节点
    SmallNode* current_;     // 指向当前分配的块，这样可以避免遍历前面已经不能分配的块  
};

class MemoryPool
{
public:
    /**
     * @brief 默认构造，真正初始化工作交给 createPool
     */
    MemoryPool() = default;

    /**
     * @brief 默认析构，真正销毁工作交给 destroyPool
     */
    ~MemoryPool() = default;

    /**
     * @brief 初始化内存池，为 pool_ 分配 PAGE_SIZE 内存
     */
    void createPool();

    /**
     * @brief 销毁内存池，遍历大块内存和小块内存且释放它们
     */
    void destroyPool();

    /**
     * @brief 申请内存的接口，内部会判断创建大块还是小块内存
     * @param[in] size 分配内存大小
     */
    void* malloc(unsigned long size);

    /**
     * @brief 申请内存且将内存清零，内部调用 malloc
     * @param[in] size 分配内存大小
     */    
    void* calloc(unsigned long size);

    /**
     * @brief 释放内存指定内存
     * @param[in] p 释放内存头地址
     */    
    void freeMemory(void* p);

    /**
     * @brief 重置内存池
     */    
    void resetPool();

    Pool* getPool() { return pool_; }

private:
    /**
     * @brief 分配大块节点，被 malloc 调用
     * @param[in] size 分配内存大小
     */
    void* mallocLargeNode(unsigned long size);

    /**
     * @brief 分配小块节点，被 malloc 调用
     * @param[in] size 分配内存大小
     */
    void* mallocSmallNode(unsigned long size);
    
    Pool* pool_ = nullptr;    
};
```
## 创建内存池
使用 posix_memalign 函数可以向操作系统申请更大的内存，我们需要传入二级指针，在内部更改指针的指向。
创建内存池会为 pool_ 分配 PAGE_SIZE 大小内存，其中包含了 Pool 结构体，SmallNode 结构体，然后才是可用的内存。
![](https://cdn.nlark.com/yuque/0/2022/png/26752078/1669112902652-afae0f9d-d616-435f-b40d-540c1b055bc9.png#averageHue=%23fcf0ca&crop=0&crop=0&crop=1&crop=1&from=url&id=hCkNY&margin=%5Bobject%20Object%5D&originHeight=750&originWidth=1151&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
```cpp
void MemoryPool::createPool()
{
    int ret = posix_memalign((void **)&pool_, MP_ALIGNMENT, PAGE_SIZE);
    if (ret) 
    {
        printf("posix_memalign failed\n");
        return;
    }

    // 分配 PAGE_SIZE 内存：Pool + SmallNode + 剩余可用内存
    pool_->largeList_ = nullptr;
    pool_->head_ = (SmallNode *)((unsigned char*)pool_ + sizeof(Pool));
    pool_->head_->last_ = (unsigned char*)pool_ + sizeof(Pool) + sizeof(SmallNode);
    pool_->head_->end_ = (unsigned char*)pool_ + PAGE_SIZE;
    pool_->head_->failed_ = 0;
    pool_->current_ = pool_->head_;

    return;
}
```
## 分配小块内存
MemoryPool::malloc 内部会判断向内存池申请内存的大小，如果大于 PAGE_SIZE 则调用 mallocLargeNode 直接申请一个大块内存。如果是小块内存，那么需要判断当前 block 剩余空间是否满足要求，如果不满足则去下一个 block 查看。若都不够，则需要调用 mallocSmallNode 重新申请一个 block 块。
![1669114288241.png](https://cdn.nlark.com/yuque/0/2022/png/26752078/1669114301921-19452868-4a68-4ab4-87e9-48e252b2c9a4.png#averageHue=%23faefca&clientId=u8e162442-b6f3-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=555&id=u0c847d75&margin=%5Bobject%20Object%5D&name=1669114288241.png&originHeight=694&originWidth=962&originalType=binary&ratio=1&rotation=0&showTitle=false&size=44099&status=done&style=none&taskId=ud074f01b-06e9-480e-a0fc-dbd7f69059c&title=&width=769.6)
```cpp
void* MemoryPool::malloc(unsigned long size)
{
    if (size <= 0)
    {
        return nullptr;
    }


    // 申请大块内存
    if (size > PAGE_SIZE - sizeof(SmallNode))
    {
        return mallocLargeNode(size);
    }


    // 申请小块内存
    unsigned char* addr = nullptr;
    SmallNode* cur = pool_->current_;
    while (cur) 
    {
        // 将cur->last指向处，格式化成16整数倍
        // 比如 15->16 31->32
        addr = (unsigned char*)mp_align_ptr(cur->last_, MP_ALIGNMENT);
        // 「当前 block 结尾 - 初始地址」 >= 「申请地址」
        // 说明该 block 剩余位置足够分配
        if (cur->end_ - addr >= size)
        {
            cur->quote_++; // 该 block 被引用次数增加
            cur->last_ = addr + size; // 更新已使用位置
            return addr;
        }
        // 此block不够用，去下一个block
        cur = cur->next_;
    }
    // 说明已有的 block 都不够用，需要创建新的 block
    return mallocSmallNode(size);
}
```
当前 block 不够，创建新的 block 并分配内存。除此之外，我们还需要让两个块连接起来，因此会遍历 block 块，并让最后一个 block 块的 next 指针指向新分配的 block 块。
这个过程中，如果超过了五个不能用的 block 块，我们就会更新 `pool.current` 让其向后跳过这五个块，避免遍历过久。
![1669115099452.png](https://cdn.nlark.com/yuque/0/2022/png/26752078/1669115103834-2be88686-ec5f-4ddb-b9b4-d3bb66a8b424.png#averageHue=%23f6eeca&clientId=u8e162442-b6f3-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=642&id=u2f0ac106&margin=%5Bobject%20Object%5D&name=1669115099452.png&originHeight=803&originWidth=1321&originalType=binary&ratio=1&rotation=0&showTitle=false&size=50812&status=done&style=none&taskId=u69a9a069-4c3c-407b-9842-0c08179eef7&title=&width=1056.8)
```cpp
// 分配小块内存
void* MemoryPool::mallocSmallNode(unsigned long size)
{
    unsigned char* block;
    int ret = posix_memalign((void**)&block, MP_ALIGNMENT, PAGE_SIZE);
    if (ret)
    {
        return nullptr;
    }

    // 获取新块的 smallnode 节点
    SmallNode* smallNode = (SmallNode*)block;
    smallNode->end_ = block + PAGE_SIZE;
    smallNode->next_ = nullptr;

    // 分配新块的起始位置
    unsigned char* addr = (unsigned char*)mp_align_ptr(block + sizeof(SmallNode), MP_ALIGNMENT);
    smallNode->last_ = addr + size;
    smallNode->quote_++;

    // 重新设置current
    SmallNode* current = pool_->current_;
    SmallNode* cur = current;
    while (cur->next_ != nullptr)
    {
        // 失效 block 数量过大，我们直接跳过这些 block，减少遍历次数
        // 超过五个不能用的块，我们再更新current指针
        if (cur->failed_ >= 5)
        {
            current = cur->next_;
        }
        cur->failed_++;
        cur = cur->next_;
    }
    // now cur = last node
    cur->next_ = smallNode;
    pool_->current_ = current;
    return addr;
}
```
## 分配大块内存
先申请大块内存，然后在 pool 中找寻是否有可用的 largeNode 节点，因为可能某个节点之前释放了它所管理的内存，那么我们就不需要创建新的 largeNode 节点了。若找到，则 `largeNode->address_ = addr` 然后返回。
如果没找到可用的 largeNode 节点，则分配新的 largeNode，largeNode 节点的内存由 block 管理，故释放大块节点的时候也只是释放节点所管理的内存，largeNode 随着 block 的释放而释放。largeNode 使用头插法。
![1669116675172.png](https://cdn.nlark.com/yuque/0/2022/png/26752078/1669116681431-a63a92f5-a9f8-4551-a087-2fee99dccdcd.png#averageHue=%23cee1ca&clientId=u8e162442-b6f3-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=610&id=u80a8f6cd&margin=%5Bobject%20Object%5D&name=1669116675172.png&originHeight=762&originWidth=799&originalType=binary&ratio=1&rotation=0&showTitle=false&size=33719&status=done&style=none&taskId=ua6e92a25-c476-48cb-be94-bb526d6724f&title=&width=639.2)
```cpp
// 分配大块内存
void* MemoryPool::mallocLargeNode(unsigned long size)
{
    unsigned char* addr;
    int ret = posix_memalign((void**)&addr, MP_ALIGNMENT, size);
    if (ret)
    {
        return nullptr;
    }

    int count = 0;
    LargeNode* largeNode = pool_->largeList_;
    while (largeNode != nullptr)
    {
        if (largeNode->address_ == nullptr)
        {
            largeNode->size_ = size;
            largeNode->address_ = addr;
            return addr;
        }
        if (count++ > 3)
        {
            // 为了避免过多的遍历，限制次数
            break;
        }
        largeNode = largeNode->next_;
    }

    // 没有找到空闲的large结构体，分配一个新的large
    // 比如第一次分配large的时候
    // largeNode节点空间在block中被分配，释放大块的时候也只是释放节点管理的内存
    // largeNode依靠block的释放函数
    largeNode = (LargeNode*)this->malloc(sizeof(LargeNode));
    if (largeNode == nullptr)
    {
        free(addr); // 申请节点内存失败，需要释放之前申请的大内存
        return nullptr;
    }

    largeNode->size_ = size;    // 设置新块大小
    largeNode->address_ = addr; // 设置新块地址
    // 下面用头插法方式将新块加入到 largeList 的头部
    largeNode->next_ = pool_->largeList_; 
    pool_->largeList_ = largeNode;
    return addr;
}
```
# 释放内存
如果是大块内存，找到之后直接释放；如果是小块内存，将引用计数减1，如果引用计数为0则重置last。
```cpp
void MemoryPool::freeMemory(void* p)
{
    LargeNode* large = pool_->largeList_;
    while (large != nullptr)
    {
        if (large->address_ == p)
        {
            free(large->address_);
            large->size_ = 0;
            large->address_ = nullptr;
            return;
        }
        large = large->next_;
    }

    SmallNode* small = pool_->head_;
    while (small != nullptr)
    {
        if ((unsigned char*)small <= (unsigned char*)p &&
            (unsigned char *) p <= (unsigned char *)small->end_)
        {
            small->quote_--;
            // 引用计数为0才释放
            if (small->quote_ == 0)
            {
                if (small == pool_->head_)
                {
                    pool_->head_->last_ = (unsigned char *)pool_ + sizeof(Pool) + sizeof(SmallNode);
                }
                else
                {
                    // last指针回到node节点尾处
                    small->last_ = (unsigned char *)small + sizeof(SmallNode);
                }
                small->failed_ = 0;
                pool_->current_ = pool_->head_;
            }
            return;
        }
        small = small->next_;
    }
}
```
## 销毁内存池

1. 从头遍历大块内存节点，将其所管理的大块内存释放。
2. 从头遍历小块内存节点，释放 block 块管理的内存。
```cpp
void MemoryPool::destroyPool()
{
    LargeNode* large = pool_->largeList_;
    while (large != nullptr)
    {
        if (large->address_ != nullptr)
        {
            free(large->address_);
        }
        large = large->next_;
    }

    SmallNode* cur = pool_->head_->next_;
    SmallNode* next = nullptr;
    while (cur != nullptr)
    {
        next = cur->next_;
        free(cur);
        cur = cur->next_;
    }
    // TODO:有错误
    free(pool_);
}
```
## 重置内存池

1. 释放 LargeNode 节点管理的内存，将其置为空。
2. 从头遍历 SmallNode，重置其 last_，quote_，failed_。
```cpp
void MemoryPool::resetPool()
{
    SmallNode* small = pool_->head_;
    LargeNode* large = pool_->largeList_;

    while (large != nullptr)
    {
        if (large->address_)
        {
            free(large->address_);
            large->address_ = nullptr;
        }
        large = large->next_;
    }

    pool_->largeList_ = nullptr;
    pool_->current_ = pool_->head_;
    while (small != nullptr)
    {
        small->last_ = (unsigned char*)small + sizeof(SmallNode);
        small->failed_ = 0;
        small->quote_ = 0;
        small = small->next_;
    }
}
```
# 参考
[Nginx：内存池的实现](https://zhuanlan.zhihu.com/p/584670074)
