函数malloc一个简单的实现

现在的位置: 首页 > 综合 > 正文

函数malloc一个简单的实现

2017年10月17日 ⁄ 综合 ⁄ 共 7768字 ⁄ 字号小中大 ⁄ 评论关闭

网上对sbrk到底是system call 还是 library function说法不一

这里通过调用sbrk实现了一个简略的malloc函数，用双向链表管理内存块，内存块的分配用了首次适应算法。

据说linux源码里又插了一个红黑树数据结构将首次适应算法改进为最佳适应，好像很厉害的样子。

#include<unistd.h>
#include<stdio.h>
#include<time.h>
#include<string.h>

/************************************************************
 * 目的：模拟标准库函数malloc和free，实现进程堆上的内存管理。
 * 实现细节：1.使用显示双向链表，按地址顺序维护内存块。
 *           2.使用首次适配算法进行空闲块的选择。
 ***********************************************************/
#define has_used 1
#define has_not_used 0
#define MINSIZE 32
#define SIZE(p) (p->size)
#define USED(p) (p->is_used)
#define PRED(p) (p->pred)
#define SUCC(p) (p->succ)

void malloc_init();
void* my_malloc(long numbytes);
void my_free(void *p);


/*内存块数据结构*/
struct mem_block{
	int is_used;
	long size;
	struct mem_block* pred;
	struct mem_block* succ;
};


/**********************************
 * 全局变量定义：
 * 1.内存块头指针
 * 2.内存块尾指针
 * 3.分配器初始化标记
 *********************************/
struct mem_block* head;
struct mem_block* tail;
int has_initialized = 0;

/*初始化分配器*/
void malloc_init(){
	head = sbrk(sizeof(struct mem_block));
	tail = sbrk(sizeof(struct mem_block));
	USED(head) = USED(tail) = has_used;
	PRED(head) = NULL;
	PRED(tail) = head;
	SUCC(head) = tail;
	SUCC(tail) = NULL;
	has_initialized = 1;
}


void* my_malloc(long numbytes){
	
	struct mem_block *cur_block;
	struct mem_block *pred_block;
	void *mem_location = NULL;
	long block_size = numbytes + sizeof(struct mem_block);
	struct mem_block *alloc_block = NULL;

	if(numbytes <= 0)
		return NULL;

	if(!has_initialized){
		malloc_init();
	}
	cur_block = head;
	while(cur_block){
		if(!USED(cur_block)){
			if(SIZE(cur_block) >= numbytes){       /*将cur_block标记为已分配*/
				USED(cur_block) = has_used;
				mem_location = (void*) cur_block + sizeof(struct mem_block);
				if(SIZE(cur_block) - numbytes > sizeof(struct mem_block)){          /*判断是否需要分割当前块*/
					pred_block = SUCC(cur_block);
					alloc_block = (void*) cur_block + block_size;
					USED(alloc_block) = has_not_used;
					SIZE(alloc_block) = SIZE(cur_block) - numbytes - sizeof(struct mem_block);
					PRED(alloc_block) = cur_block;
					SUCC(alloc_block) = pred_block;
					SUCC(cur_block) = alloc_block;
					SIZE(cur_block) = numbytes;
					PRED(pred_block) = alloc_block;
				}
				break;
			}
		}
		cur_block=SUCC(cur_block);
	}

	/*没有找到合适的块，申请新的空间*/
	/*这一步很关键，必须注意将tail块放置到最后才能保证链表中块的地址顺序*/
	if(!mem_location){
		pred_block = PRED(tail);

		sbrk(-1*sizeof(struct mem_block));
		if( (long) (alloc_block = sbrk(block_size)) == -1){
			printf("申请内存失败!\n");
			return NULL;
		}
		tail = sbrk(sizeof(struct mem_block));

		SIZE(alloc_block) = numbytes;
		USED(alloc_block) = has_used;
		SUCC(alloc_block) = tail;
		PRED(alloc_block) = pred_block;
		SUCC(pred_block) = alloc_block;

		PRED(tail) = alloc_block;
		SUCC(tail) = NULL;
		USED(tail) = has_used;
		SIZE(tail) = 0;
	
		mem_location = (void*) alloc_block + sizeof(struct mem_block);
	}

	return mem_location;
}


void my_free(void *p){
	if(!p)
		return;

	struct mem_block* cur_block = p - sizeof(struct mem_block);
	/* 判断是否合并，四种情况，1.不合并。2.前合并。3.后合并。4.前后同时合并 */
	/* 边界上的问题已经通过初始化解决了*/

	struct mem_block* pred_block = PRED(cur_block);
	struct mem_block* succ_block = SUCC(cur_block);

	if(USED(pred_block)&&USED(succ_block)){
		USED(cur_block) = has_not_used;
	}

	else if(!USED(pred_block)&&USED(succ_block)){
		SIZE(pred_block) = SIZE(pred_block) + SIZE(cur_block) + sizeof(struct mem_block);
		SUCC(pred_block) = SUCC(cur_block);
		PRED(succ_block) = pred_block;
	}
	
	else if(USED(pred_block)&&!USED(succ_block)){
		USED(cur_block) = has_not_used;
		SIZE(cur_block) = SIZE(cur_block) + SIZE(succ_block) + sizeof(struct mem_block);
		SUCC(cur_block) = SUCC(succ_block);
		if(SUCC(succ_block))
			PRED(SUCC(succ_block)) = cur_block;
	
	}

	else if(!USED(pred_block)&&!USED(succ_block)){
		SIZE(pred_block) = SIZE(pred_block) + SIZE(cur_block) + SIZE(succ_block) + 2 * sizeof(struct mem_block);
		SUCC(pred_block) = SUCC(succ_block);
		if(SUCC(succ_block))
			PRED(SUCC(succ_block)) = pred_block;
	}
}
		

void memory_state(){
	struct mem_block* cur_block = head;
	while(cur_block){
		printf("size: %ld, used: %d,address: %p\n",SIZE(cur_block),USED(cur_block),cur_block);
		cur_block = SUCC(cur_block);
	}
	printf("\n");
}


int main(){
	int i,j,k;
	void* test[100];
	
	memset(test,NULL,sizeof(test));
	srand(time(NULL));

	for(i=0;i<=3000000;i++){
		j=rand()%100;
		if(test[j]){
			//printf("释放\n");
			my_free(test[j]);
			test[j] = NULL;
		}
		else{
			k = rand()%1000;
			//printf("申请%d内存空间\n",k);
			test[j] = my_malloc(k);
		}
	}
	memory_state();
	return 0;
}

当然上面的实现再效率上来说是比较坑爹的= =！

稍微改进一下使用循环适配算法

#include<unistd.h>
#include<stdio.h>
#include<time.h>
#include<string.h>

/************************************************************
 * 目的：模拟标准库函数malloc和free，实现进程堆上的内存管理。
 * 实现细节：1.使用显示双向链表，按地址顺序维护内存块。
 *           2.使用循环首次适应算法进行空闲块的选择。
 ***********************************************************/
#define has_used 1
#define has_not_used 0
#define MINSIZE 32
#define SIZE(p) (p->size)
#define USED(p) (p->is_used)
#define PRED(p) (p->pred)
#define SUCC(p) (p->succ)

void malloc_init();
void* my_malloc(long numbytes);
void my_free(void *p);


/*内存块数据结构*/
struct mem_block{
	int is_used;
	long size;
	struct mem_block* pred;
	struct mem_block* succ;
};


/**********************************
 * 全局变量定义：
 * 1.内存块头指针
 * 2.内存块尾指针
 * 3.分配器初始化标记
 * 4.遍历内存块的标记
 *********************************/
struct mem_block* head;
struct mem_block* tail;
struct mem_block* flag;
int has_initialized = 0;

/*初始化分配器*/
void malloc_init(){
	head = sbrk(sizeof(struct mem_block));
	tail = sbrk(sizeof(struct mem_block));
	USED(head) = USED(tail) = has_used;
	PRED(head) = tail;
	PRED(tail) = head;
	SUCC(head) = tail;
	SUCC(tail) = head;
	flag = head;
	has_initialized = 1;
}


void* my_malloc(long numbytes){
	
	struct mem_block *cur_block;
	struct mem_block *pred_block;
	void *mem_location = NULL;
	long block_size = numbytes + sizeof(struct mem_block);
	struct mem_block *alloc_block = NULL;

	if(numbytes <= 0)
		return NULL;

	if(!has_initialized){
		malloc_init();
	}
	cur_block = flag;
	while(cur_block){
		if(!USED(cur_block)){
			if(SIZE(cur_block) >= numbytes){       /*将cur_block标记为已分配*/
				USED(cur_block) = has_used;
				mem_location = (void*) cur_block + sizeof(struct mem_block);
				if(SIZE(cur_block) - numbytes > sizeof(struct mem_block)){          /*判断是否需要分割当前块*/
					pred_block = SUCC(cur_block);
					alloc_block = (void*) cur_block + block_size;
					USED(alloc_block) = has_not_used;
					SIZE(alloc_block) = SIZE(cur_block) - numbytes - sizeof(struct mem_block);
					PRED(alloc_block) = cur_block;
					SUCC(alloc_block) = pred_block;
					SUCC(cur_block) = alloc_block;
					SIZE(cur_block) = numbytes;
					PRED(pred_block) = alloc_block;
				}
				break;
			}
		}
		cur_block=SUCC(cur_block);
		if(cur_block == flag)
			break;
	}
	flag = cur_block;

	/*没有找到合适的块，申请新的空间*/
	/*这一步很关键，必须注意将tail块放置到最后才能保证链表中块的地址顺序*/
	if(!mem_location){
		pred_block = PRED(tail);

		sbrk(-1*sizeof(struct mem_block));
		if( (long) (alloc_block = sbrk(block_size)) == -1){
			printf("申请内存失败!\n");
			return NULL;
		}
		tail = sbrk(sizeof(struct mem_block));

		SIZE(alloc_block) = numbytes;
		USED(alloc_block) = has_used;
		SUCC(alloc_block) = tail;
		PRED(alloc_block) = pred_block;
		SUCC(pred_block) = alloc_block;

		PRED(tail) = alloc_block;
		SUCC(tail) = head;
		USED(tail) = has_used;
		SIZE(tail) = 0;

		PRED(head) = tail;
	
		mem_location = (void*) alloc_block + sizeof(struct mem_block);
	}

	return mem_location;
}


void my_free(void *p){
	if(!p)
		return;

	struct mem_block* cur_block = p - sizeof(struct mem_block);
	/* 判断是否合并，四种情况，1.不合并。2.前合并。3.后合并。4.前后同时合并 */
	/* 边界上的问题已经通过初始化解决了*/

	struct mem_block* pred_block = PRED(cur_block);
	struct mem_block* succ_block = SUCC(cur_block);

	if(USED(pred_block)&&USED(succ_block)){
		USED(cur_block) = has_not_used;
	}

	else if(!USED(pred_block)&&USED(succ_block)){
		SIZE(pred_block) = SIZE(pred_block) + SIZE(cur_block) + sizeof(struct mem_block);
		SUCC(pred_block) = SUCC(cur_block);
		PRED(succ_block) = pred_block;
		flag = pred_block;
	}
	
	else if(USED(pred_block)&&!USED(succ_block)){
		USED(cur_block) = has_not_used;
		SIZE(cur_block) = SIZE(cur_block) + SIZE(succ_block) + sizeof(struct mem_block);
		SUCC(cur_block) = SUCC(succ_block);
		PRED(SUCC(succ_block)) = cur_block;
	  	flag = cur_block;	
	}

	else if(!USED(pred_block)&&!USED(succ_block)){
		SIZE(pred_block) = SIZE(pred_block) + SIZE(cur_block) + SIZE(succ_block) + 2 * sizeof(struct mem_block);
		SUCC(pred_block) = SUCC(succ_block);
		PRED(SUCC(succ_block)) = pred_block;
		flag = pred_block;
	}
}
		

void memory_state(){
	struct mem_block* cur_block = head;
	while(cur_block){
		printf("size: %ld, used: %d,address: %p\n",SIZE(cur_block),USED(cur_block),cur_block);
		cur_block = SUCC(cur_block);
		if(cur_block == head)
			break;
	}
	printf("\n");
}


int main(){
	int i,j,k;
	void* test[100000];
	
	memset(test,NULL,sizeof(test));
	srand(time(NULL));
	for(i=0;i<=50000000;i++){
		j=rand()%100;
		if(test[j]){
	//		printf("释放\n");
			my_free(test[j]);
			test[j] = NULL;
		}
		else{
			k = rand()%1000;
	//		printf("申请%d内存空间\n",k);
			test[j] = my_malloc(k);
		}
	}
	memory_state();

	
	return 0;
}

【上篇】SICP读后总结+对函数式编程的理解
【下篇】图的几种表示方法

作者: bountiful

该日志由 bountiful 于7年前发表在综合分类下，最后更新于 2017年10月17日.
转载请注明: 函数malloc一个简单的实现 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

函数malloc一个简单的实现

作者: bountiful

书签

最新文章New

本站推荐

返回首页