本文共 14099 字,大约阅读时间需要 46 分钟。
序言
在编程过程中,尤其是对于C语言开发者,其实编程就是在使用内存,不停地变化内存中的数据。当我们想开辟一片新的内存使用时,就会使用malloc实现。但是通过查阅很多资料,发现频繁的使用malloc并不是很好的选择。原因就是如果频繁的申请、释放内存,操作系统由于内存管理算法原因,导致出现内存碎片。其实产生碎片是一件很平常的事情,为何会这样,我想主要是内存利用率与性能的一个平衡。如果操作系统很抠门,肯定会把内存分配的逻辑算的很严密,“见缝插针”这四个字能很到的诠释内存分配策略。正因为见缝插针,经过很长的使用,内存上会遍布“针眼”,但是由于针眼普遍很小,当你再去插一个较粗的针的时候,往往很久“插不进去”。因为需要判断这么多针眼哪个足够宽松的能插进去这根针。所以,如果我们不那么抠的去实现内存分配,是不是在性能上会有很大的提高呢?答案绝对是肯定的,而且随着硬件技术的提升,内存已经不是当年的容量,服务器起步也得是16G吧,32 64也是很常见的。就连现在手机都有6G内存的,实在令台式机服务器都汗颜。
在内存池的实现结尾,会加入一块内存池使用率监测打印,开发一种内存池,通吃所有的项目场景,显然是不可取的。说一个比较时尚的名词“机器学习”。这块的目的在于通过观测内存池的使用率,从而发现哪些长度的内存比较受项目的欢迎,需要多设,哪些长度的内存使用较少,需要少设。哪些长度的没有,需要新设等等。目前这块是纯手动的,并不是动态变化的,有些调优的感觉。
现在结束序言,开始真正介绍内存池的实现吧!
正文
首先,我们来介绍一下本内存池实现的数据总结构,如下图所示:我们来详细的介绍一下该数据结构,主要有如下分结构:
第一结构:如下图(从总图截图而来) 其实途中已经注明了结构的各个元素的含义,不用多解释,从总图中可以看出,这种结构是用 数组 形式穿起来的。不用链表是因为可以用 array[i] 这种形式快速找到所需要内存池型号,这也是很多内存池实现的方法。第二结构:更简单,它的任务就是描述一个内存节点,如下图(从总图截图而来)
同样的待遇,图片已将很好的诠释了元素的作用,这里需要解释的是,为何搞个列编号,这个编号其实就是 第一个数组结构的数组编号,此处记录列编号是不是多此一举??其实不是的,这里主要是考虑到内存回收时使用,内存分配的单位不是 传统的 malloc 返回值 unsigned char 而是,一个结构体指针,也就是这第二结构,如果没有列编号,回收内存需要遍历所有内存节点,找到地址匹配之节点,而有了列编号,直接去遍历编号所在池就可以,性能上肯定会有提升。我们不仅要考虑申请内存高效,也得考虑释放内存高效。
第三结构:如下图,同样来自总图截图。
这就是整体结构的最小单位,相当于最后的粮仓,真实的数据区,直接在初始化的时候,调用malloc申请的。这个就不解释了。最后一个东西,就是总图标注的 “总指针”,在内存池初始化之前,只有这个一个指针是存在的,为全局变量,其他的都是malloc而来。
经过上面的讲解,相信高手已经了解了 8 9 成,新手也懂了 5 6成吧,毕竟一种算法或者功能,最重要的就是看懂数据结构,数据结构懂了,代码自然能看懂,数据结构不懂,代码永远理解不了。从上面的总图来看,内存节点在下面挂的参差不齐,这个是故意这么画的,意思就是没列的容量是可以自定义的,举个栗子,16字节内存池竟发现用的较多,分配10000个吧!! 1024字节用的很少,分配100个吧 !! 项目由于特定因素, 申请400字节特别多,那就加一列,定一个 410字节,个数20000吧!!这段话很重要,说明该结构是可以灵活配置的,并且经过某个项目使用,可以修改这些参数,达到优化的目的。
到这里数据定义告一段落,下面讲解源码
1.数据结构定义部分 这部分其实在上面已经定义很清楚了,这里只是国际惯例贴上去,如下代码段。typedef struct bpn memory_pool_node;
struct bpn{ unsigned int column; unsigned char * data; memory_pool_node * next; }; typedef struct{ unsigned int total_count; unsigned int used_count; unsigned int block_len; memory_pool_node * free_header; memory_pool_node * used_header; }memory_pool_colume; 2.全局变量 memory_pool_colume * b_p = NULL; int buffer_pool_no = 0; 全局变量有两个,一个是 上面说的“总指针”,是内存池的首地址。另个是buffer_pool_no , 为内存池长度种类的个数,因为内存池采用数组形式组织,为防止越界,所以需要记录。 3.初始化函数实现 原型: int buffer_pool_init(unsigned int colume_no, unsigned int block_len[], unsigned int block_count[]);输入参数:
colume_no 这个参数就是初始化列的个数, 8字节的算一列,16字节的算一列,64算一列, 这个值就是列的总和。block_len 这个参数是一个数组,数组长度就是第一个参数的值,数组中每个元素,描述了某一列的内存节点的长度。
block_count 这个参数是一个数组,数组长度就是第一个参数的值,数组中每个元素,描述了某一列的内存节点的个数。
返回值:
成功返回0,失败返回-1.具体实现的逻辑:
1.为第一结构的存放申请内存,用于管理内存池的列,长度为第一参数所决定,首地址交给 “头指针”。2.在for循环中,根据传入的第二第三参数,频繁生成第三结构以及第二结构,绑定两者,将第二结构挂在在每个列结构的 free指针上,以单链表的形式挂载。
init执行完以后,上述的结构总图就构建完毕,不一样的就是,第二结构全部挂载在 free指针上,used指针下面没有挂载任何内存节点。
代码:
int buffer_pool_init(unsigned int colume_no, unsigned int block_len[] , unsigned int block_count[]) { b_p = (memory_pool_colume *)malloc(sizeof(memory_pool_colume) * colume_no); if (b_p == NULL) return -1; memset(b_p , 0 , sizeof(memory_pool_colume) * colume_no); buffer_pool_no = colume_no; memory_pool_node * curr_node = NULL; memory_pool_node * new_node = NULL; for (int i = 0; i < colume_no; i++) { b_p[i].block_len = block_len[i]; b_p[i].total_count = block_count[i]; for (int j = 0; j < block_count[i]; j++) { new_node =(memory_pool_node *)malloc(sizeof(memory_pool_node)); new_node->column = i; new_node->data =(unsigned char *) malloc(block_len[i]); memset(new_node->data , 0 ,block_len[i]); if (new_node == NULL || new_node->data == NULL) return -1; new_node->next = NULL; if (j == 0) { b_p[i].free_header = new_node; curr_node = b_p[i].free_header; } else { curr_node->next = new_node; curr_node = curr_node->next; } } } return 0; } 4.内存申请函数实现 原型: memory_pool_node * buffer_malloc(unsigned int size);输入参数:
size 需要申请内存的大小,输入参数雷同malloc用法。返回值:
成功返回一个memory_pool_node 类型的指针,指向一个内存节点,这里与malloc有较大不同!!失败返回NULL。具体实现的逻辑:
1.判断输入参数大小,是否比内存池最长节点都大,如果成立,说明目前的节点都不满足分配要求,需要重新分配一个节点,这个节点不属于内存池,所以列编号定义了一个999死值,当列编号为9999,则该节点不属于内存池,节点生成成功后,直接返回节点的指针。2.如果1描述不成立,证明此次内存分配是可以从内存池获取的。
3.接下来如何从内存池中找到匹配节点呢? 用for循环遍历 第一结构,如果 当前列的内存长度 >= 申请size,则说明这列满足申请要求,进而去查询这列还有没有free节点,如果有,从单链头部取出一个节点,并且将该节添加到used链表头部,且返回该节点的地址。 如果这列很抢手,全被用光,则continue,去下一列看看有没有free,如果所有列都没有,则现生成一个内存节点,标记9999,地址返回给调用者。
代码:
memory_pool_node * buffer_malloc(unsigned int size) { memory_pool_node * node = NULL; if (size > b_p[buffer_pool_no - 1].block_len) { printf("malloc size[%d] so big ,need new from stack!!\n" , size); a: node = (memory_pool_node *)malloc(sizeof(memory_pool_node)); node->column = 9999; node->data = (unsigned char *)malloc(size); memset(node->data, 0, size); if (node == NULL || node->data == NULL) return NULL; node->next = NULL; return node; } for (int i = 0 ; i < buffer_pool_no ; i++) { if (size > b_p[i].block_len) continue; if (b_p[i].total_count - b_p[i].used_count == 0) { printf("warning!!!! size[%d]pool use up!!!! \n" , b_p[i].block_len); continue; } node = b_p[i].free_header; b_p[i].free_header = b_p[i].free_header->next; b_p[i].used_count++; node->next = b_p[i].used_header; b_p[i].used_header = node; return node; } printf("warning!!!! all of pool used up!!!! \n"); goto a; } 5.内存释放函数实现 原型: int buffer_free(memory_pool_node * buffer);输入参数:
buffer 申请的内存节点指针。返回值:
返回0 ,永远不会失败。具体实现的逻辑:
1.判断归还的内存节点的列编号,如果为9999,直接free掉这个node,返回0即可。2.如果列编号不为9999, 数组定位到那一列的第一结构,从uesd链表中找出这个node,断链删除,加在free链的头部。返回0.
代码:
int buffer_free(memory_pool_node * buffer) { memory_pool_node * node_cur = b_p[buffer->column].used_header; memory_pool_node * node_pre = NULL; if (buffer->column == 9999) { free(buffer->data); free(buffer); buffer = NULL; return MP_OK; } while(node_cur != NULL) { if (node_cur != buffer) { node_pre = node_cur; node_cur = node_cur->next; continue; } if (node_pre == NULL) { b_p[buffer->column].used_header = b_p[buffer->column].used_header->next; } else { node_pre->next = node_cur->next; } b_p[buffer->column].used_count--; node_cur->next = b_p[buffer->column].free_header; b_p[buffer->column].free_header = node_cur; break; } return MP_OK; } 6.内存池销毁 原型: int buffer_pool_destory(void);输入参数:
void返回值:
成功返回0 ,失败返回错误值。具体实现的逻辑:
1.这部分逻辑没什么好说的,就是通过 for以及while 遍历所有节点,free所有节点, 再free掉 第一结构的数组。代码:
int buffer_pool_destory(void) { memory_pool_node * node_cur = NULL; memory_pool_node * node_del = NULL; if (b_p == NULL) return MP_NOT_INIT; for (int i = 0; i < buffer_pool_no; i++) { node_cur = b_p[i].used_header; while (node_cur != NULL) { node_del = node_cur; node_cur = node_cur->next; free(node_del->data); free(node_del); } node_cur = b_p[i].free_header; while (node_cur != NULL) { node_del = node_cur; node_cur = node_cur->next; free(node_del->data); free(node_del); } } free(b_p); b_p = NULL; buffer_pool_no = 0; return MP_OK; } 6.内存池实时使用率打印 原型: int buffer_runtime_print(void);输入参数:
void返回值:
成功返回0 ,失败返回错误值。具体实现的逻辑:
1.这部分逻辑也很简单,就是for循环所有列,计算每列的使用率百分比打印出来。代码:
int buffer_runtime_print(void) { if (b_p == NULL) { printf("buffer pool not init yet!!!\n"); return MP_NOT_INIT; } printf("\n*********************** memory pool runtime report start************************\n"); for (int i = 0; i < buffer_pool_no; i++) { printf("pool no[%d] blocksize[%d] blockTotalCount[%d] usedBlock[%d] used percentage[%d%%]\n" \ , i , b_p[i].block_len , b_p[i].total_count , b_p[i].used_count , b_p[i].used_count*100/ b_p[i].total_count); } printf("*********************** memory pool runtime report end**************************\n"); return MP_OK; }到这里,所有代码已经介绍完毕,相信如果细心看肯定会全部了解。
使用场景模拟 1.init调用: 举个例子,代码如下:unsigned int a[10] = { 8 ,16 ,32 ,64 ,128 , 256 , 512 , 1024 ,2028 , 4096};
unsigned int b[10] = { 100 ,500 ,1000 ,1500 ,2000 , 3000 , 4000 , 5000 ,4000 , 2000}; buffer_pool_init(10, a , b); 看代码已经很好的能反映出init如何使用,8字节的申请100个 16字节的,申请500个 ...................... 2.buffer_malloc调用: memory_pool_node * node3 = buffer_malloc(186); 3.buffer_free调用: buffer_free(node3); 4.buffer_destory调用: buffer_pool_destory(); 5.buffer_runtime_print调用: buffer_runtime_print(); 遗留问题 1.init生效后,内存池结构固话,无法动态扩展,这部分后续可以添加,尤其是带有自动学习功能,需要的内存大小多生成,不需要的自动减少。2.从代码上看,used链表其实没什么卵用,当时设计的主要目的是管理所有内存节点,所有内存即使用户不归还,也可以做一个自动回收机制,回收内存。但是这部分没做。既然没做,所以used目前是可以去除的,意思就是用户申请内存,把这个节点直接给用户,内存池不再管理,如果用户不归还,那就是内存泄露了。。。。这样做有好处,高效。
3.内存使用率打印函数可以增加一些统计功能,比如 用户申请内存不是在池中分配的,最好也记录下来,这样为修改init参数提供依据。
所有源代码
头文件 memory_pool.h #ifndef MEMORY_POOL_H #define MEMORY_POOL_H #include<stdio.h> #include<stdlib.h> #include<string.h> #define MP_OK 0 #define MP_MALLOC_FIAL -1 #define MP_NOT_INIT -2 typedef struct bpn memory_pool_node; struct bpn{ unsigned int column; unsigned char * data; memory_pool_node * next; }; typedef struct{ unsigned int total_count; unsigned int used_count; unsigned int block_len; memory_pool_node * free_header; memory_pool_node * used_header; }memory_pool_colume; int buffer_pool_init(unsigned int colume_no, unsigned int block_len[], unsigned int block_count[]); memory_pool_node * buffer_malloc(unsigned int size); int buffer_free(memory_pool_node * buffer); int buffer_pool_destory(void); int buffer_runtime_print(void); #endif 主文件 memory_pool.cpp #include"memory_pool.h" memory_pool_colume * b_p = NULL; int buffer_pool_no = 0; int buffer_pool_init(unsigned int colume_no, unsigned int block_len[] , unsigned int block_count[]) { b_p = (memory_pool_colume *)malloc(sizeof(memory_pool_colume) * colume_no); if (b_p == NULL) return MP_MALLOC_FIAL; memset(b_p , 0 , sizeof(memory_pool_colume) * colume_no); buffer_pool_no = colume_no; memory_pool_node * curr_node = NULL; memory_pool_node * new_node = NULL; for (int i = 0; i < colume_no; i++) { b_p[i].block_len = block_len[i]; b_p[i].total_count = block_count[i]; for (int j = 0; j < block_count[i]; j++) { new_node =(memory_pool_node *)malloc(sizeof(memory_pool_node)); new_node->column = i; new_node->data =(unsigned char *) malloc(block_len[i]); memset(new_node->data , 0 ,block_len[i]); if (new_node == NULL || new_node->data == NULL) return MP_MALLOC_FIAL; new_node->next = NULL; if (j == 0) { b_p[i].free_header = new_node; curr_node = b_p[i].free_header; } else { curr_node->next = new_node; curr_node = curr_node->next; } } } return MP_OK; } memory_pool_node * buffer_malloc(unsigned int size) { memory_pool_node * node = NULL; if (size > b_p[buffer_pool_no - 1].block_len) { printf("malloc size[%d] so big ,need new from stack!!\n" , size); a: node = (memory_pool_node *)malloc(sizeof(memory_pool_node)); node->column = 9999; node->data = (unsigned char *)malloc(size); memset(node->data, 0, size); if (node == NULL || node->data == NULL) return NULL; node->next = NULL; return node; } for (int i = 0 ; i < buffer_pool_no ; i++) { if (size > b_p[i].block_len) continue; if (b_p[i].total_count - b_p[i].used_count == 0) { printf("warning!!!! size[%d]pool use up!!!! \n" , b_p[i].block_len); continue; } node = b_p[i].free_header; b_p[i].free_header = b_p[i].free_header->next; b_p[i].used_count++; node->next = b_p[i].used_header; b_p[i].used_header = node; return node; } printf("warning!!!! all of pool used up!!!! \n"); goto a; } int buffer_free(memory_pool_node * buffer) { memory_pool_node * node_cur = b_p[buffer->column].used_header; memory_pool_node * node_pre = NULL; if (buffer->column == 9999) { free(buffer->data); free(buffer); buffer = NULL; return MP_OK; } while(node_cur != NULL) { if (node_cur != buffer) { node_pre = node_cur; node_cur = node_cur->next; continue; } if (node_pre == NULL) { b_p[buffer->column].used_header = b_p[buffer->column].used_header->next; } else { node_pre->next = node_cur->next; } b_p[buffer->column].used_count--; node_cur->next = b_p[buffer->column].free_header; b_p[buffer->column].free_header = node_cur; break; } return MP_OK; } int buffer_pool_destory(void) { memory_pool_node * node_cur = NULL; memory_pool_node * node_del = NULL; if (b_p == NULL) return MP_NOT_INIT; for (int i = 0; i < buffer_pool_no; i++) { node_cur = b_p[i].used_header; while (node_cur != NULL) { node_del = node_cur; node_cur = node_cur->next; free(node_del->data); free(node_del); } node_cur = b_p[i].free_header; while (node_cur != NULL) { node_del = node_cur; node_cur = node_cur->next; free(node_del->data); free(node_del); } } free(b_p); b_p = NULL; buffer_pool_no = 0; return MP_OK; } int buffer_runtime_print(void) { if (b_p == NULL) { printf("buffer pool not init yet!!!\n"); return MP_NOT_INIT; } printf("\n*********************** memory pool runtime report start************************\n"); for (int i = 0; i < buffer_pool_no; i++) { printf("pool no[%d] blocksize[%d] blockTotalCount[%d] usedBlock[%d] used percentage[%d%%]\n" \ , i , b_p[i].block_len , b_p[i].total_count , b_p[i].used_count , b_p[i].used_count*100/ b_p[i].total_count); } printf("*********************** memory pool runtime report end**************************\n"); return MP_OK; }测试文件 test.cpp
#include"memory_pool.h" #include<time.h> #include<Windows.h> int main() { printf("press any key to start init and malloc memory pool\n"); getchar(); unsigned int a[10] = { 8 ,16 ,32 ,64 ,128 , 256 , 512 , 1024 ,2028 , 4096}; unsigned int b[10] = { 100 ,500 ,1000 ,1500 ,2000 , 3000 , 4000 , 5000 ,4000 , 2000}; buffer_pool_init(10, a , b); int i = 455; memory_pool_node * node = NULL; #if 0 while (i > 0) { node = buffer_malloc(6); if (node != NULL) { printf("pool no[%d] get memory success!!!\n" , node->column); node->data[0] = i; } else { printf("malloc fail !!!\n"); getchar(); } i--; Sleep(10); } getchar(); #endif memory_pool_node * node1 = buffer_malloc(6); memory_pool_node * node2 = buffer_malloc(172); memory_pool_node * node3 = buffer_malloc(186); memory_pool_node * node4 = buffer_malloc(1300); memory_pool_node * node5 = buffer_malloc(2100); buffer_malloc(40); buffer_malloc(60); buffer_malloc(80); buffer_malloc(100); buffer_malloc(120); buffer_malloc(130); buffer_malloc(150); buffer_malloc(180); buffer_malloc(700); buffer_malloc(900); buffer_runtime_print(); printf("press any key to free memory pool\n"); getchar(); buffer_free(node5); buffer_free(node4); buffer_free(node3); buffer_runtime_print(); buffer_free(node2); buffer_free(node1); buffer_runtime_print(); printf("press any key to destory memory pool\n"); getchar(); buffer_pool_destory(); printf("press any key to quit\n"); getchar(); return 0; } 运行环境:VS2015---------------------
作者:forever1980s 来源:CSDN 原文:https://blog.csdn.net/forever5312/article/details/78029672 版权声明:本文为博主原创文章,转载请附上博文链接!