内存池的实现

引入内存池是为了解决内存碎片的问题。内存碎片内存实际没有占满但由于大量碎片化的内存导致无法分配内存导致的内存耗尽的问题。如下图所示对于未使用的内存夹在已经使用的内存之间这样会导致什么问题如果下次再次分配内存时假如大块内存分配区中的一小块内存为4096B如果需要8KB此时虽然总剩余内存大小大于8KB但是实际可分配的连续内存却小于8KB这就是内存碎片。内存碎片还分为内部碎片和外部碎片内部碎片:即分配的内存大于实际需要的内存外部碎片:就是上述图片中的例子为了解决这个问题我们引入内存池进行管理内存。原理很简单就是事先拿出一大块内存然后用指针管理这段内存用户需要多少就分配多少最后统一再释放内存。这样就避免了内存碎片的问题。下面是内存池的简单实现。代码的逻辑是采用pool进行逻辑层的管理管理两个内存链表一个是小块内存链表一个是大块内存链表。每次malloc时会根据malloc的size大小去往不同的链表。#include stdio.h#include stdlib.h#include string.h#include kvstore.htypedef struct mp_node_s {unsigned char *last;unsigned char *end;struct mp_node_s *next;} mp_node_t;typedef struct mp_large_s {struct mp_large_s *next;void *alloc;} mp_large_t;typedef struct mp_pool_s {size_t max; /*小块内存的最大可用空间*/struct mp_node_s *head;struct mp_large_s *large;} mp_pool_t;// size : 4096int kvs_mp_create(mp_pool_t *pool, size_t size) {if (!pool || size 0) return -1;void *mem malloc(size sizeof(mp_node_t));if(mem NULL){return -1;}struct mp_node_s *node (struct mp_node_s *)mem;/*将内存池起始地址强转为node_s*/node-last (char *)mem sizeof(struct mp_node_s);/*起始地址从头节点后开始*/node-end (char *)mem size sizeof(mp_node_t);/*结束地址为mem起始地址加上size*/node-next NULL;pool-head node;pool-max size - sizeof(struct mp_node_s);pool-large NULL;return 0;}void kvs_mp_destory(mp_pool_t *pool) {mp_large_t *l;for (l pool-large;l;l l-next) {if (l-alloc) {free(l-alloc);}}pool-large NULL;mp_node_t *node pool-head;while (node) {mp_node_t *tmp node-next;free(node);node tmp;}}//static void *mp_alloc_block(mp_pool_t *pool, size_t size) {void *mem malloc(size sizeof(mp_node_t));if(mem NULL) return NULL;struct mp_node_s *node (struct mp_node_s *)mem;node-last (char *)mem sizeof(struct mp_node_s);node-end (char *)mem size sizeof(mp_node_t);node-next NULL;// 新块的可用内存起始是 node-last结构体之后void *ptr node-last;// 检查剩余空间是否足够必须加避免越界if (node-end - node-last size) {node-last size;} else {free(node); // 分配失败释放新块return NULL;}// tail insert -- head insertmp_node_t *iter pool-head;while (iter-next ! NULL) {iter iter-next;}iter-next node;return ptr;}//static void *mp_alloc_large(mp_pool_t *pool, size_t size) {if (!pool || size 0) return NULL;void *ptr malloc(size sizeof(mp_large_t));/*malloc return any type,you can trans it */if (ptr NULL) return NULL;/*先在已有的大内存块中找有没有空闲的但是size大小并没有进行判断*/mp_large_t *l;for (l pool-large;l;l l-next) {if (l-alloc NULL) {l-alloc ptr;return ptr;}}//l used to manage struct,ptr is the real memoryl kvs_mp_alloc(pool, sizeof(mp_large_t));if (l NULL) {free(ptr);return NULL;}/*采用头插法时间复杂度为O(1)*/l-alloc ptr;l-next pool-large;pool-large l;return ptr;}void *kvs_mp_alloc(mp_pool_t *pool, size_t size) {if(pool NULL || size 0) return NULL;if (size pool-max) {// malloc_large;return mp_alloc_large(pool, size);}// size pool-maxvoid *ptr NULL;mp_node_t *node pool-head;do {if (node-end - node-last size) {/*check there if have enough space*/ptr node-last;/*point last*/node-last size;/*update last*/return ptr;/*返回给用户可用地址*/}node node-next;} while (node);/*node内存不足就分配新node*/return mp_alloc_block(pool, size);}/*用于单独释放大块内存*/void kvs_mp_free(mp_pool_t *pool, void *ptr) {mp_large_t *l;for (l pool-large;l;l l-next) {if (l-alloc ptr) {free(l-alloc);l-alloc NULL;return ;}}//}https://github.com/0voice