WebServer(8) 内存池模块

写在前面

1 为什么使用内存池

1. 避免内存碎片。
2. 避免系统调用开销。

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

2 全局内存池还是局部内存池

如果现在有一个服务器，他时不时会接受新用户的连接。而我们将实现一个内存池用于管理内存，我们应该考虑将内存池设计成全局还是非全局形式。

1. 使用一个全局内存池，这样实现比较困难。对于内存块的回收更是令人头疼（我们从内存池分配出来的内存），好在我们可以使用jemalloc/tcmalloc
2. 针对每一个连接建立一个内存池，连接销毁释放内存池。这种情况下，这个内存池的生命周期就和这个连接的生命周期是一样的了。我们就不考虑小块的回收问题了。

正文

1 内存池设计思想

这里参照 Nginx 的内存池设计思想，Nginx 内存池设计思路精巧简单，没有那么复杂。Nginx 每收到一个请求，就创建一个内存池给新连接使用，请求处理完成后释放内存池，因此内存池并非是单例模式的。
Nginx 将内存分为大块内存和小块内存来管理，对于小块内存，用户申请后不需要主动释放，而是等待释放内存池时再释放。对于大块内存，用户可以调用相关接口进行释放，也可以等内存池释放时再释放。因此，Nginx 对于小块内存的回收并不是很在意。
同时 Nginx 内存池支持增加回调函数，当内存池释放时，自动调用回调函数释放用户申请的资源。回调函数允许增加多个，通过链表进行链接，在内存池释放时被逐一调用。
Nginx 创建内存池会先申请 PAGE_SIZE 内存，我称为 block。一部分用来容纳 ngx_pool_t 结构体，另一部分内存则是用于满足用户申请。ngx_pool_data_t 结构体中的 last 指针和 end 指针之间的内存是空闲的，当用户申请小块内存时，如果空闲的内存大小满足用户的需求，则可以分配给用户。

2 管理内存块的结点

1. end_：指向当前 block 块的结尾。
2. last_：指向当前 block 块的使用位置。
3. quote_：表示该 block 块的被引用次数。
4. failed_：表示该 block 块的失效次数。
5. next_：指向下一个 block 块。

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_; // 指向下一个大块
};

3 内存池结构

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;    

};

4 创建内存池

使用 posix_memalign 函数可以向操作系统申请更大的内存，我们需要传入二级指针，在内部更改指针的指向。
创建内存池会为 pool_ 分配 PAGE_SIZE 大小内存，其中包含了 Pool 结构体，SmallNode 结构体，然后才是可用的内存。

void MemoryPool::CreatePool() {
  /**
   * int posix_memalign (void **memptr, size_t alignment, size_t size);
   * posix_memalign分配的内存块更大，malloc可能分配不了太大的内存块
   * 内部要让这个p指针指向新的内存，所以需要使用二级指针。
   */
  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;
}

5 分配小块内存

MemoryPool::Malloc 内部会判断向内存池申请内存的大小，如果大于 PAGE_SIZE 则调用 MallocLargeNode 直接申请一个大块内存。如果是小块内存，那么需要判断当前 block 剩余空间是否满足要求，如果不满足则去下一个 block 查看。若都不够，则需要调用 mallocSmallNode 重新申请一个 block 块。

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 让其向后跳过这五个块，避免遍历过久。

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

6 分配大块内存

先申请大块内存，然后在 pool 中找寻是否有可用的 largeNode 节点，因为可能某个节点之前释放了它所管理的内存，那么我们就不需要创建新的 largeNode 节点了。若找到，则 largeNode->address_ = addr 然后返回。

如果没找到可用的 largeNode 节点，则分配新的 largeNode，largeNode 节点的内存由 block 管理，故释放大块节点的时候也只是释放节点所管理的内存，largeNode 随着 block 的释放而释放。largeNode 使用头插法。

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 = (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;
}

7 释放内存

如果是大块内存，找到之后直接释放；如果是小块内存，将引用计数减1，如果引用计数为0则重置last。

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

8 销毁内存池

1. 从头遍历大块内存节点，将其所管理的大块内存释放。
2. 从头遍历小块内存节点，释放 block 块管理的内存。

void MemoryPool::DestroyPool() {
  LargeNode* large = pool_->largeList_;
  while (large != nullptr) {
    if (large->address_ != nullptr) {
      free(large->address_);
      large->address_ = nullptr;
    }
    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_);
}

9 重置内存池

1. 释放 LargeNode 节点管理的内存，将其置为空。
2. 从头遍历 SmallNode，重置其 last_，quote_，failed_。

void MemoryPool::ResetPool() {
  SmallNode* small = pool_->head_;
  LargeNode* large = pool_->largeList_;

  while (large != nullptr) {
    if (large->address_) {
      free(large->address_);
    }
    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_;
  }
}