本文共 7248 字，大约阅读时间需要 24 分钟。

为了减少内存碎片，实现了一个简单的快速内存分配器。

优点： 无内存碎片 O(1)的分配算法。 O(1)的回收算法。 缺点： 底层仍旧使用了malloc。进一步考虑采用mmap 内存大小不可动态扩展。考虑是否支持动态扩展 分配的每快内存都是固定大小。考虑是否支持不同大小的块。   基本算法: 采用链表管理可用内存与已使用内存。 分配内存时候，从freelist的头取得一个可用块。此块被放到usedlist中。 回收的时候，从usedlist中将回收的块放回freelist。 这两个操作都可以在O(1)内实现。   具体代码如下：

#include <stdio.h>#include <stdlib.h>#include <unistd.h>#include <pthread.h>#pragma pack(1)#define MAGIC 0x43782struct alloc_chunck{ unsigned int chunck_indx; unsigned int chunck_flag; unsigned int chunck_prev; unsigned int chunck_next;};struct alloc_head{ pthread_mutex_t alloc_lock; unsigned int alloc_magic; void * alloc_mem; unsigned int alloc_num; unsigned int alloc_size; struct alloc_chunck alloc_free; struct alloc_chunck alloc_used;};enum{ EARG = 1, EMEM, EBIG, ENONE};#pragma pack()struct alloc_head g_alloc;int alloc_init(unsigned int num, unsigned int size){ //XXX //here we just have one process to run //so we dont need a lock if (num == 0 || size == 0) return -EARG; pthread_mutex_init(&g_alloc.alloc_lock, NULL); g_alloc.alloc_mem = malloc(num * (size + sizeof(struct alloc_chunck))); if (g_alloc.alloc_mem == NULL) return -EMEM; g_alloc.alloc_num = num; g_alloc.alloc_size = size; //none chunck have been used g_alloc.alloc_free.chunck_indx = -1; g_alloc.alloc_free.chunck_flag = 1; g_alloc.alloc_free.chunck_prev = -1; g_alloc.alloc_free.chunck_next = 0; g_alloc.alloc_used.chunck_indx = -1; g_alloc.alloc_used.chunck_flag = 1; g_alloc.alloc_used.chunck_prev = -1; g_alloc.alloc_used.chunck_next = -1; struct alloc_chunck * p = (struct alloc_chunck*)g_alloc.alloc_mem; for (unsigned int i = 0; i < num; i++) { p = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + size) * i); p->chunck_indx = i; p->chunck_flag = 0; p->chunck_prev = g_alloc.alloc_free.chunck_indx; p->chunck_next = i + 1; } p->chunck_next = g_alloc.alloc_free.chunck_indx; g_alloc.alloc_magic = MAGIC; return 0;}void * alloc_one(){ if (g_alloc.alloc_magic != MAGIC) return NULL; pthread_mutex_lock(&g_alloc.alloc_lock); if (g_alloc.alloc_free.chunck_next == g_alloc.alloc_free.chunck_indx) { pthread_mutex_unlock(&g_alloc.alloc_lock); return NULL; } struct alloc_chunck * p = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * g_alloc.alloc_free.chunck_next); if (p->chunck_next == g_alloc.alloc_free.chunck_indx) { g_alloc.alloc_free.chunck_next = g_alloc.alloc_free.chunck_indx; } else { struct alloc_chunck * pn = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * p->chunck_next); g_alloc.alloc_free.chunck_next = p->chunck_next; pn->chunck_prev = p->chunck_prev; } p->chunck_flag = 1; if (g_alloc.alloc_used.chunck_next == g_alloc.alloc_used.chunck_indx) { p->chunck_next = g_alloc.alloc_used.chunck_next; p->chunck_prev = g_alloc.alloc_used.chunck_prev; g_alloc.alloc_used.chunck_next = p->chunck_indx; } else { struct alloc_chunck * pu = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * g_alloc.alloc_used.chunck_next); p->chunck_next = g_alloc.alloc_used.chunck_next; g_alloc.alloc_used.chunck_next = p->chunck_indx; p->chunck_prev = g_alloc.alloc_used.chunck_indx; pu->chunck_prev = p->chunck_indx; } pthread_mutex_unlock(&g_alloc.alloc_lock); return (void*)((char*)p + sizeof(struct alloc_chunck));}void alloc_free(void * p){ pthread_mutex_lock(&g_alloc.alloc_lock); struct alloc_chunck * cp = (struct alloc_chunck*)((char*)p - sizeof(struct alloc_chunck)); if (cp->chunck_next == g_alloc.alloc_used.chunck_indx && cp->chunck_prev == g_alloc.alloc_used.chunck_indx) { g_alloc.alloc_used.chunck_next = g_alloc.alloc_used.chunck_indx; g_alloc.alloc_used.chunck_prev = g_alloc.alloc_used.chunck_indx; } else if (cp->chunck_next == g_alloc.alloc_used.chunck_indx && cp->chunck_prev != g_alloc.alloc_used.chunck_indx) { struct alloc_chunck *pp = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * cp->chunck_prev); pp->chunck_next = g_alloc.alloc_used.chunck_indx; } else if (cp->chunck_next != g_alloc.alloc_used.chunck_indx && cp->chunck_prev == g_alloc.alloc_used.chunck_indx) { struct alloc_chunck *pn = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * cp->chunck_next); g_alloc.alloc_used.chunck_next = pn->chunck_indx; pn->chunck_prev = g_alloc.alloc_used.chunck_indx; } else { struct alloc_chunck *pp = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * cp->chunck_prev); struct alloc_chunck *pn = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * cp->chunck_next); pp->chunck_next = pn->chunck_indx; pn->chunck_prev = pp->chunck_indx; } cp->chunck_flag = 0; cp->chunck_next = g_alloc.alloc_free.chunck_next; g_alloc.alloc_free.chunck_next = cp->chunck_indx; cp->chunck_prev = g_alloc.alloc_free.chunck_indx; pthread_mutex_unlock(&g_alloc.alloc_lock);}void alloc_free_travel(){ struct alloc_chunck * p = NULL; printf("free chunck/n"); for (unsigned int indx = g_alloc.alloc_free.chunck_next; indx != -1;) { p = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * indx); indx = p->chunck_next; printf("index = %d flag = %d prev = %d next = %d/n", p->chunck_indx, p->chunck_flag, p->chunck_prev, p->chunck_next); }}void alloc_used_travel(){ struct alloc_chunck * p = NULL; printf("used chunck/n"); for (unsigned int indx = g_alloc.alloc_used.chunck_next; indx != -1;) { p = (struct alloc_chunck*)((char*)g_alloc.alloc_mem + (sizeof(struct alloc_chunck) + g_alloc.alloc_size) * indx); indx = p->chunck_next; printf("index = %d flag = %d prev = %d next = %d/n", p->chunck_indx, p->chunck_flag, p->chunck_prev, p->chunck_next); }}void alloc_stat(){ printf("alloc stat/n"); printf("alloc num = %d alloc size = %d alloc free = %d alloc used = %d/n", g_alloc.alloc_num, g_alloc.alloc_size, g_alloc.alloc_free.chunck_next, g_alloc.alloc_used.chunck_next);}#ifdef ALLOC_DEBUGvoid * runtine(void * arg){ int tid = *(int*)arg; printf("thread id = %d/n", tid); for(;;) { char *p = (char*)alloc_one(); if (p == NULL) { //printf("%d none mem/n", tid); //alloc_free_travel(); //alloc_used_travel(); usleep(tid+5000); continue; } snprintf(p, 10, "$ %d $", tid); printf("%s/n", p); alloc_free(p); }}int main(){ int ret = alloc_init(20, 100000000); printf("ret = %d/n", ret); printf("init stat/n"); alloc_stat(); alloc_free_travel(); alloc_used_travel(); printf("alloc one chuncks stat/n"); char *p1 = (char*)alloc_one(); alloc_free_travel(); alloc_used_travel(); printf("alloc one chuncks stat/n"); char *p2 = (char*)alloc_one(); alloc_free_travel(); alloc_used_travel(); printf("free one chuncks stat/n"); alloc_free(p1); alloc_free_travel(); alloc_used_travel(); printf("free one chuncks stat/n"); alloc_free(p2); alloc_free_travel(); alloc_used_travel(); pthread_t tids[100]; for(int i = 0; i < 100; i++) { pthread_create(&tids[i], NULL, runtine, &i); usleep(100000); } for(int i = 0; i < 100; i++) { pthread_join(tids[i], NULL); } return 0;}#endif   

 

转载地址：http://itgxi.baihongyu.com/