一、内存池原理及使用
服务器为什么要使用内存池?
在客户端进行连接（如果有分配内存的需求）的时候，内存会频繁分配和使用
如果有大量客户端连接，并且每次只占用一点内存，会出现很多的内存碎片。
内存池就是为了避免频繁分配，释放以及减少内存碎片的问题)。
内存池的使用场景?
1.全局内存池
2.一个连接做一个内存池
如何去实现一个内存池？
二、方案一：
通过一个链表节点，节点的结构体包含四个内容，第一个是指向的内存块地址，第二个是下一个链表节点，通过这种方式将内存组织起来，第三个是 每个节点还有（flag） 分配的内存大小，第四个是否可以使用(已经释放了)
使用方式:
如果有新的分配请求，就会依次遍历，查找能用的节点（flag来标记是否已经分配或者释放），用该节点分配的内存。如果没有能用的，就会在末尾添加新的节点。
存在缺点：
如果第一次使用64字节的内存块，并释放了，下次再使用50字节的呢，还要再末尾继续添加，这样会造成很多无法利用的内存碎片
对于内存比较大的呢？
直接进行分配，而不用加入到链表中。因为内存池本身解决的问题就是减少内存碎片，大内存的分配，往往是有利的，不需要用内存池管理。
三、方案二：
可以在方案一基础上，固定内存块大小，划分几个大小，符合要求最小大小的内存块，就分配给它，这样可以避免生成太多碎片，并且不会使得链表太长。
于是可以将内存池改成下面的结构，索引找到对应的固定内存 链表，然后遍历链表，找到能用的。
缺点：
查找速度慢(使用链表)，小块的回收会出现间隙
四、方案三：
对于内存可以 划分为大块和小块
可以划定一个值，对大于该值的可以认定为大块，小于该值可以认定为小块，大块直接用链表去存储(因为内存池最关心的，以及解决的是小块的内存碎片问题，而大块是最希望看到的，不需要内存池去解决，它的碎片少,因此使用链表去管理就行)
对于小块，可以放入一个比较大的块(block)里面，在block里面分配一块空间给小块去使用。如果当前block内小块都没在使用了，那么就将整个block一起释放。block之间也用链表进行连接起来，可以动态地管理分配和释放block（这些都是用来存储小块内存）。通过block可以方便小块内存地管理，可以减少内存碎片。
1.block用于管理小块内存
一个block的头部，有last,end，next以及其他参数组成，通过链表将blocks组织起来(next指针)
比如这个block大小为4k，此时要使用一块8bytes的内存空间，只要把8bytes的首地址(last指向的内存)返回即可，然后把last指向8bytes的内存空间末尾，用于下一次分配使用
2.整体结构
小块往右侧block里面放
大块往下边直接整块从链表头部插入进去
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) #define mp_align(n, alignment) (((n)+(alignment-1)) & ~(alignment-1)) //用来做对齐的，比如以4个字节对齐， 那么0x35-->0x36 #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; }; //block的头 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;//能分配的最大size struct mp_node_s *current;//block当前的指针(遍历查找的起点) struct mp_large_s *large;//大块 struct mp_node_s head[0];//第一个block(第一个block是放在mp_pool_s中的，剩下的用链表连接。大小为 头+数据,因为数据大小size不确定，因此用柔性数组) }; 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); //API struct mp_pool_s *mp_create_pool(size_t size) { struct mp_pool_s *p; 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; } //API 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; 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 += 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) { if (p->failed++ > 4) {//如果failed > 4, 就漏过这个node(也就是说每个块，在查找块的时候只允许失败4次，失败4次后，让current指向该节点的下一个) current = p->next; } } p->next = new_node; 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; for (large = pool->large; large; large = large->next) { if (large->alloc == NULL) { large->alloc = p; return p; } if (n ++ > 3) break; } 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; } //API void *mp_alloc(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 = mp_align_ptr(p->last, MP_ALIGNMENT);//内存对齐 if ((size_t)(p->end - m) >= size) {//block中要有足够空间能放下当前的size p->last = m + size; return m; } p = p->next;//查找有空间可以装下的block } while (p); return mp_alloc_block(pool, size);//没有block可以装了，那就创建一个小块,并分配 } 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; } //API 只释放大块 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); // mp_free(mp); } //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)); //printf("mp_align_ptr(p->current, 32): %lx, p->current: %lx, mp_align(p->large, 32): %lx, p->large: %lx\n", mp_align_ptr(p->current, 32), p->current, mp_align_ptr(p->large, 32), p->large); 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; }
