Linux组件之内存池的实现-阿里云开发者社区

一、为什么需要内存池

应用程序使用内存，需要先申请内存，使用完之后再释放内存。比如c语言中使用malloc/free来分配/释放内存，c++中使用new/delete来分配/释放内存。内存申请与释放都需要与操作系统进行交互，具体来说就是系统维护一个内存链表，当有一个内存申请过来时，根据分配算法在链表找一个合适的内存分配给它。分配的内存块可能会大于所申请的内存大小，这样需要进行切割，将剩余的内存插入到空闲链表中。释放的时候，系统要判断释放的内存块的前后是否有空闲，若有的话还要进行合并。可见，调用库中的内存分配函数，十分耗时。

另外，频繁的申请、释放内存，会使得一块大内存可能被分割成多块不连续的小内存。当需要再分配连续的大内存时候，尽管剩余内存的总和可能大于所要分配的内存大小，但系统就找不到连续的内存。这就是内存碎片的存在，从而导致分配错误。

综上所述，总结一下使用内存池的几个主要原因：

1）提高内存分配效率：传统的内存分配方式会涉及到频繁的系统调用和内存管理开销，而内存池可以在初始化时一次性地分配一块连续的内存空间，然后根据需要从该池中快速分配内存，避免了频繁的系统调用，从而提高了内存分配的效率。
2）降低内存碎片化：内存池会事先分配一定数量的连续内存块，当需要分配内存时，直接从这些预分配的内存块中获取，不涉及内存的分配和释放，减少了内存碎片的产生，提高了内存的利用率。
3）减少动态内存分配次数：内存池可以在程序初始化的时候一次性分配好所需的内存，然后在运行时通过内存池进行内存分配，避免了频繁的动态内存分配，从而减少了内存管理的开销和潜在的内存泄漏风险。
4）控制内存分配的策略：内存池可以自定义内存分配的策略，例如按照固定大小的内存块进行分配，或者按需动态调整内存池的大小等。这可以根据具体应用场景和需求来选择最合适的内存管理策略。

总之，内存池是一种有效管理内存的机制，通过提高内存分配和释放的效率，减少内存碎片化，降低动态内存分配的次数，能够帮助提高程序的性能和可靠性。

二、内存池的工作流程

1）开始时，申请一块大的内存（在该块内存不够用时在二次分配），

2）需要时，从这块内存中取出，并标记下这块内存被用了

3）释放时，标记此内存被释放了。注意此时并不真的把内存释放给操作系统，而是当一大块内存都空闲的时候，才释放给操作系统。

4）调用内存分配函数的时，小块内存每次都分配固定大小的内存块，这样就避免了内存碎片产生的可能。

参考 nginx 内存池的设计，以大、小块作为内存管理分配的方式。

具体来说，内存池中分大小块，申请内存大小大于某个值定为大块、否则是小块，内部使用链表串联。

72e17d71520c93e3d83cf0fc7b48a050_ad5926fa0b1e461faca7cb46aae3e87e.png

三、内存池的实现

3.1 数据结构

大块内存结构

struct mp_large_s {
  struct mp_large_s *next;  // 指向下一个大块内存
  void *alloc;        // 指向实际分配的大块内存
};

小块内存结构

struct mp_node_s {
  unsigned char *last;    // 指向内存池中已分配结点的末尾，即下次可分配内存结点的首地址
  unsigned char *end;     // 指向内存池的末尾
  struct mp_node_s *next;   // 指向下一个结点
  size_t failed;        // 当前的内存池分配失败的次数
};

内存池结构

struct mp_pool_s {
  size_t max;         // 内存池可分配的最大空间，超过的话用大块内存
  struct mp_node_s *current;  // 指向当前内存池
  struct mp_large_s *large; // 指向大块内存链表
  struct mp_node_s head[0]; // 指向小块内存链表
};

6becbdb0e83a3fe13db0356ef839f4e7_8b95357d971a474084df1ddd1d3d9c6c.png

3.2 接口设计

3.2.1 创建内存池

内存池创建的时候分三块，一块存储mp_pool_s结构体，一块存储mp_node_s结构体，一块为申请的内存块。返回指向整个内存池的指针p。

struct mp_pool_s *mp_create_pool(size_t size) {
  struct mp_pool_s *p;
  // posix_memalign 用于分配内存块，并保证所分配的内存块以指定的对齐方式进行对齐。
  // 参数:1)一个指向指针的指针，用于保存分配得到的内存块的地址。2)所需的内存对齐方式. 3)要分配的内存块的大小
  // 一开始并不知道大块内存具体大小，因此只需要分配：申请空间的大小 + 内存池结构体大小 + 小块内存结点
  int ret = posix_memalign((void **)&p, MP_ALIGNMENT, size + sizeof(struct mp_pool_s) + sizeof(struct mp_node_s));
  if (ret) {
    return NULL;
  }
  p->max = (size < MP_MAX_ALLOC_FROM_POOL) ? size : MP_MAX_ALLOC_FROM_POOL; // 设置小块内存可分配的最大空间
  p->current = p->head;                             // 设置当前指向的内存块
  p->large = NULL;                              // 设置大块内存
  p->head->last = (unsigned char *)p + sizeof(struct mp_pool_s) + sizeof(struct mp_node_s);
  p->head->end = p->head->last + size;
  p->head->failed = 0;
  return p;
}

3.2.2 内存池销毁

void mp_destory_pool(struct mp_pool_s *pool) {
  struct mp_node_s *h, *n;
  struct mp_large_s *l;
  // 释放大块内存
  for (l = pool->large; l; l = l->next) {
    if (l->alloc) {
      free(l->alloc);
    }
  }
  // 释放小块内存
  h = pool->head->next;
  while (h) {
    n = h->next;
    free(h);
    h = n;
  }
  // 释放内存池
  free(pool);
}

3.2.3 内存分配

通过mp_alloc向内存池申请内存，如果用户申请的内存大于pool->max，则认为是大块内存，直接向 OS 申请。否则就是小块内存，直接在内存池里面分配。

如果申请小块内存，遍历现有的小块内存链表，寻找是否有满足需求的内存块

1）如果有，返回待分配内存块的首地址

2）如果没有，创新新的小块内存

void *mp_alloc(struct mp_pool_s *pool, size_t size) {
  unsigned char *m;
  struct mp_node_s *p;
  // 1、申请小块内存
  if (size <= pool->max) {
    p = pool->current;
    do {
      // 遍历小块内存链表，寻找可用的空间分配内存
      m = mp_align_ptr(p->last, MP_ALIGNMENT);
      // 若当前结点的剩余空间足够分配
      if ((size_t)(p->end - m) >= size) {
        p->last = m + size;
        return m;
      }
      // 若当前内存块的剩余内存小于所需内存，则到下一个内存块中寻找
      p = p->next;
    } while (p);
    // 没找到合适的小块内存，则申请小块内存
    return mp_alloc_block(pool, size);
  }
  // 2、申请大块内存
  return mp_alloc_large(pool, size);
}

1. 分配小块内存

调用mp_alloc_block创建新的小块内存，并插入到小块内存链表的末尾。

有一种情况，每个小块内存最后都剩下一小块，比如A内存块剩下5，B内存块剩下16。current指向的是A。此时需要申请大小20的内存，从current开始查，A不满足。再申请大小10的内存，从current开始查，A还是不满足。每次都从A开始，就很费时间，因此引入failed。

每次调用mp_alloc_block函数，代表内存池现有小块内存的空间分配失败，此时，所有可用的小块内存的 failed + 1，表示不满足用户的需求增加1次。若某个小块内存若连续 5 次不满足用户需求，则不再使用它，遍历时跳过。

961feaf4c1e18b81818f49b03e2891c2_13b1e7cdd8df48aa9128a41ba2a31352.png

static void *mp_alloc_block(struct mp_pool_s *pool, size_t size) {
  unsigned char *m;
  struct mp_node_s *h = pool->head;
  // 第一个小块内存中，可分配的内存大小
  size_t psize = (size_t)(h->end - (unsigned char *)h);
  // 申请内存，大小与第一个小块内存一样
  int ret = posix_memalign((void **)&m, MP_ALIGNMENT, psize);
  if (ret) return NULL;
  struct mp_node_s *p, *new_node, *current;
  // 初始化新的内存块
  new_node = (struct mp_node_s*)m;
  new_node->end = m + psize;
  new_node->next = NULL;
  new_node->failed = 0;
  // 将指针m移动到可分配内存的开始位置
  m += sizeof(struct mp_node_s);
  m = mp_align_ptr(m, MP_ALIGNMENT);
  new_node->last = m + size;
  // 从当前指向的内存块开始，寻找最后一个内存块链表的结点
  current = pool->current;
  for (p = current; p->next; p = p->next) {
    // 若某个小块内存连续5次都分配失败，则跳过这个小块内存，下次不再遍历它
    if (p->failed++ > 4) { //
      current = p->next;
    }
  }
  // 将新创建的内存块，尾插到小内存块链表
  p->next = new_node;
  // 更新pool->current指针，判断 current 是否为空？
  // 若非空，指向current指向的结点；若为空，代表之前所有的内存块都分配失败，则指向新的内存块
  pool->current = current ? current : new_node;
  return m;
}

2. 分配大块内存

调用mp_alloc_large()分配一个新的大块内存，插入到链表的开头，头插法。

static void *mp_alloc_large(struct mp_pool_s *pool, size_t size) {
  void *p = malloc(size);
  if (p == NULL) return NULL;
  size_t n = 0;
  struct mp_large_s *large;
  // 遍历大块内存链表，找到可以挂载 p 的位置
  for (large = pool->large; large; large = large->next) {
    // 找到可以挂载的地方
    if (large->alloc == NULL) {
      large->alloc = p;
      return p;
    }
    // 若连续 4 次都没找到，就不再寻找了
    if (n ++ > 3) break;
  }
  // 创建一个新的大块内存结点，用来挂载p
  large = mp_alloc(pool, sizeof(struct mp_large_s));
  if (large == NULL) {
    free(p);
    return NULL;
  }
  // 将新创建的结点，头插到大块内存链表中
  large->alloc = p;
  large->next = pool->large;
  pool->large = large;
  return p;
}

3.2.4 内存池的释放

Nginx 内存池内部仅提供大块内存的释放接口

void mp_free(struct mp_pool_s *pool, void *p) {
  struct mp_large_s *l;
  for (l = pool->large; l; l = l->next) {
    if (p == l->alloc) {
      free(l->alloc);
      l->alloc = NULL;
      return ;
    }
  }
}

3.2.5 内存池重置

nginx的小块内存是无法释放的，因为这个小块内存的分配都是通过last指针偏移的。

如果1和3分配出去了。但现在2不使用了，怎么归还到小块内存里？mp_node_s 结构通过指针last和end标识空闲内存，因此不能把2这块内存给拉进去空闲内存空间里面。

2d0a594438466a738fac76ad34ec7d01_72c5bf2ef7724040821ebe5a0837ba72.png

但是如果不释放小块内存，小块内存随着分配越来越大，系统的内存分配失败的概率越大。因此引入内存池重置。

当一个内存池被使用过一段时间后，可能会有一些内存块被分配出去，但是在后续的使用中，这些内存块可能已经不再需要了。此时，可以选择重置内存池，将所有已经分配的内存块释放回来，并重新初始化内存池的状态，使其恢复到最初的状态，以便重新利用这些内存空间。

void mp_reset_pool(struct mp_pool_s *pool) {
  struct mp_node_s *h;
  struct mp_large_s *l;
  // 释放大块内存
  for (l = pool->large; l; l = l->next) {
    if (l->alloc) {
      free(l->alloc);
    }
  }
  pool->large = NULL;
  // 通过指针复位重置小块内存（不调用free归还内存）
  for (h = pool->head; h; h = h->next) {
    h->last = (unsigned char *)h + sizeof(struct mp_node_s);
  }
}

3.3 完整代码

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#define MP_ALIGNMENT          32
#define MP_PAGE_SIZE      4096
#define MP_MAX_ALLOC_FROM_POOL  (MP_PAGE_SIZE-1)
// 按指定的对齐方式 alignment 对齐。
#define mp_align(n, alignment) (((n)+(alignment-1)) & ~(alignment-1))
#define mp_align_ptr(p, alignment) (void *)((((size_t)p)+(alignment-1)) & ~(alignment-1))
// 大块内存结构
struct mp_large_s {
  struct mp_large_s *next;  // 指向下一个大块内存
  void *alloc;        // 指向实际分配的大块内存
};
// 小块内存结构
struct mp_node_s {
  unsigned char *last;    // 指向内存池中已分配结点的末尾，即下次可分配内存结点的首地址
  unsigned char *end;     // 指向内存池的末尾
  struct mp_node_s *next;   // 指向下一个结点
  size_t failed;        // 当前的内存池分配失败的次数
};
// 内存池结构
struct mp_pool_s {
  size_t max;         // 内存池可分配的最大空间，超过的话用大块内存
  struct mp_node_s *current;  // 指向当前内存池
  struct mp_large_s *large; // 指向大块内存链表
  struct mp_node_s head[0]; // 指向小块内存链表
};
struct mp_pool_s *mp_create_pool(size_t size);
void mp_destory_pool(struct mp_pool_s *pool);
void *mp_alloc(struct mp_pool_s *pool, size_t size);
void *mp_nalloc(struct mp_pool_s *pool, size_t size);
void *mp_calloc(struct mp_pool_s *pool, size_t size);
void mp_free(struct mp_pool_s *pool, void *p);
// 创建内存池
struct mp_pool_s *mp_create_pool(size_t size) {
  struct mp_pool_s *p;
  // posix_memalign 用于分配内存块，并保证所分配的内存块以指定的对齐方式进行对齐。
  // 参数:1)一个指向指针的指针，用于保存分配得到的内存块的地址。2)所需的内存对齐方式. 3)要分配的内存块的大小
  // 一开始并不知道大块内存具体大小，因此只需要分配：申请空间的大小 + 内存池结构体大小 + 小块内存结点
  int ret = posix_memalign((void **)&p, MP_ALIGNMENT, size + sizeof(struct mp_pool_s) + sizeof(struct mp_node_s));
  if (ret) {
    return NULL;
  }
  p->max = (size < MP_MAX_ALLOC_FROM_POOL) ? size : MP_MAX_ALLOC_FROM_POOL; // 设置小块内存可分配的最大空间
  p->current = p->head;                             // 设置当前指向的内存块
  p->large = NULL;                              // 设置大块内存
  p->head->last = (unsigned char *)p + sizeof(struct mp_pool_s) + sizeof(struct mp_node_s);
  p->head->end = p->head->last + size;
  p->head->failed = 0;
  return p;
}
// 内存池销毁
void mp_destory_pool(struct mp_pool_s *pool) {
  struct mp_node_s *h, *n;
  struct mp_large_s *l;
  // 释放大块内存
  for (l = pool->large; l; l = l->next) {
    if (l->alloc) {
      free(l->alloc);
    }
  }
  // 释放小块内存
  h = pool->head->next;
  while (h) {
    n = h->next;
    free(h);
    h = n;
  }
  // 释放内存池
  free(pool);
}
// 重置内存池
void mp_reset_pool(struct mp_pool_s *pool) {
  struct mp_node_s *h;
  struct mp_large_s *l;
  // 释放大块内存
  for (l = pool->large; l; l = l->next) {
    if (l->alloc) {
      free(l->alloc);
    }
  }
  pool->large = NULL;
  // 通过指针复位重置小块内存（不调用free归还内存）
  for (h = pool->head; h; h = h->next) {
    h->last = (unsigned char *)h + sizeof(struct mp_node_s);
  }
}
// 分配小块内存
static void *mp_alloc_block(struct mp_pool_s *pool, size_t size) {
  unsigned char *m;
  struct mp_node_s *h = pool->head;
  // 第一个小块内存中，可分配的内存大小
  size_t psize = (size_t)(h->end - (unsigned char *)h);
  // 申请内存，大小与第一个小块内存一样
  int ret = posix_memalign((void **)&m, MP_ALIGNMENT, psize);
  if (ret) return NULL;
  struct mp_node_s *p, *new_node, *current;
  // 初始化新的内存块
  new_node = (struct mp_node_s*)m;
  new_node->end = m + psize;
  new_node->next = NULL;
  new_node->failed = 0;
  // 将指针m移动到可分配内存的开始位置
  m += sizeof(struct mp_node_s);
  m = mp_align_ptr(m, MP_ALIGNMENT);
  new_node->last = m + size;
  // 从当前指向的内存块开始，寻找最后一个内存块链表的结点
  current = pool->current;
  for (p = current; p->next; p = p->next) {
    // 若某个小块内存连续5次都分配失败，则跳过这个小块内存，下次不再遍历它
    if (p->failed++ > 4) { //
      current = p->next;
    }
  }
  // 将新创建的内存块，尾插到小内存块链表
  p->next = new_node;
  // 更新pool->current指针，判断 current 是否为空？
  // 若非空，指向current指向的结点；若为空，代表之前所有的内存块都分配失败，则指向新的内存块
  pool->current = current ? current : new_node;
  return m;
}
// 分配大块内存
static void *mp_alloc_large(struct mp_pool_s *pool, size_t size) {
  void *p = malloc(size);
  if (p == NULL) return NULL;
  size_t n = 0;
  struct mp_large_s *large;
  // 遍历大块内存链表，找到可以挂载 p 的位置
  for (large = pool->large; large; large = large->next) {
    // 找到可以挂载的地方
    if (large->alloc == NULL) {
      large->alloc = p;
      return p;
    }
    // 若连续 4 次都没找到，就不再寻找了
    if (n ++ > 3) break;
  }
  // 创建一个新的大块内存结点，用来挂载p
  large = mp_alloc(pool, sizeof(struct mp_large_s));
  if (large == NULL) {
    free(p);
    return NULL;
  }
  // 将新创建的结点，头插到大块内存链表中
  large->alloc = p;
  large->next = pool->large;
  pool->large = large;
  return p;
}
// 对齐方式分配内存池
void *mp_memalign(struct mp_pool_s *pool, size_t size, size_t alignment) {
  void *p;
  int ret = posix_memalign(&p, alignment, size);
  if (ret) {
    return NULL;
  }
  struct mp_large_s *large = mp_alloc(pool, sizeof(struct mp_large_s));
  if (large == NULL) {
    free(p);
    return NULL;
  }
  large->alloc = p;
  large->next = pool->large;
  pool->large = large;
  return p;
}
// 非对齐方式分配内存池
void *mp_alloc(struct mp_pool_s *pool, size_t size) {
  unsigned char *m;
  struct mp_node_s *p;
  // 1、申请小块内存
  if (size <= pool->max) {
    p = pool->current;
    do {
      // 遍历小块内存链表，寻找可用的空间分配内存
      m = mp_align_ptr(p->last, MP_ALIGNMENT);
      // 若当前结点的剩余空间足够分配
      if ((size_t)(p->end - m) >= size) {
        p->last = m + size;
        return m;
      }
      // 若当前内存块的剩余内存小于所需内存，则到下一个内存块中寻找
      p = p->next;
    } while (p);
    // 没找到合适的小块内存，则申请小块内存
    return mp_alloc_block(pool, size);
  }
  // 2、申请大块内存
  return mp_alloc_large(pool, size);
}
// 非对齐分配内存池
void *mp_nalloc(struct mp_pool_s *pool, size_t size) {
  unsigned char *m;
  struct mp_node_s *p;
  if (size <= pool->max) {
    p = pool->current;
    do {
      m = p->last;
      if ((size_t)(p->end - m) >= size) {
        p->last = m+size;
        return m;
      }
      p = p->next;
    } while (p);
    return mp_alloc_block(pool, size);
  }
  return mp_alloc_large(pool, size);
}
// 分配并清零内存空间。
void *mp_calloc(struct mp_pool_s *pool, size_t size) {
  // 在给定的内存池中进行内存分配
  void *p = mp_alloc(pool, size);
  if (p) {
    //将分配到的内存块清零
    memset(p, 0, size);
  }
  return p;
}
// 内存池释放，只针对大块内存
void mp_free(struct mp_pool_s *pool, void *p) {
  struct mp_large_s *l;
  for (l = pool->large; l; l = l->next) {
    if (p == l->alloc) {
      free(l->alloc);
      l->alloc = NULL;
      return ;
    }
  }
}
int main(int argc, char *argv[]) {
  int size = 1 << 12;
  struct mp_pool_s *p = mp_create_pool(size);
  int i = 0;
  for (i = 0;i < 10;i ++) {
    void *mp = mp_alloc(p, 512);
  }
  printf("mp_create_pool: %ld\n", p->max);
  printf("mp_align(123, 32): %d, mp_align(17, 32): %d\n", mp_align(24, 32), mp_align(17, 32));
  int j = 0;
  for (i = 0;i < 5;i ++) {
    char *pp = mp_calloc(p, 32);
    for (j = 0;j < 32;j ++) {
      if (pp[j]) {
        printf("calloc wrong\n");
      }
      printf("calloc success\n");
    }
  }
  printf("mp_reset_pool\n");
  for (i = 0;i < 5;i ++) {
    void *l = mp_alloc(p, 8192);
    mp_free(p, l);
  }
  mp_reset_pool(p);
  printf("mp_destory_pool\n");
  for (i = 0;i < 58;i ++) {
    mp_alloc(p, 256);
  }
  mp_destory_pool(p);
  return 0;
}

参考资料：

https://www.cnblogs.com/xiekeli/archive/2012/10/17/2727432.html

http://senlinzhan.github.io/2017/04/24/nginx-memory-pool/

Linux组件之内存池的实现

一、为什么需要内存池

二、内存池的工作流程

三、内存池的实现

3.1 数据结构

3.2 接口设计

3.2.1 创建内存池

3.2.2 内存池销毁

3.2.3 内存分配

1. 分配小块内存

2. 分配大块内存

3.2.4 内存池的释放

3.2.5 内存池重置

3.3 完整代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像