malloc和free的实现

程序员文章站 2022-05-12 11:33:55

...

背景

在嵌入式平台中，RAM空间有限，为了充分利用ram,就需要对利用动态进行内存的申请和释放。

实现机制

系统中存在两个双向链表：

1条是实链表将小的内存块连接起来，其头节点是固定的，其首地址和堆内存的首地址是一样的。
1条是空闲链表，将系统中空闲的内存块连接起来，其头节点是变化的，始终指向空闲块中首地址最小的空闲块

调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，变成已经分配的块，另一块的大小就是剩下的字节，变成新的空闲块）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到空闲链表上。

调用free函数时，系统将会根据传递的地址判断其有效性后，确定其在哪1个内存块（找到被释放的内存块的位置），然后判断其前后是否有空闲块，如果有的话先将这两个内存块合并成1个，然后更新空闲块链表首节点。

实现方案

1> 内存块的数据结构

struct node_s
{
	unsigned int size;
	unsigned int base;			//应用malloc后返回的地址
	unsigned char used_flag;	//标记该几点是否被使用

	struct node_s* p_prev;	    //指向和其紧邻的前1个节点
	struct node_s* p_next;		//指向和其紧邻的后1个节点
	
	struct node_s* p_free_prev;	//指向前1个空闲的节点	
	struct node_s* p_free_next;   //指向后1个空闲的节点
};

2>系统在某个阶段链表的状态示意图如下：

malloc和free的实现

在某个时刻1个堆内存，被划分成5个内存块，内存块1,3,5是已经分配的，内存块2,4空闲的，任意两个连续的内存块之间地址是连续的。

2> 接口定义如下：

MALLOC_MANAGER_FILLE_EXT void alg_malloc_init(unsigned int  start_addr, unsigned int length);

MALLOC_MANAGER_FILLE_EXT void* alg_malloc(unsigned int size);

MALLOC_MANAGER_FILLE_EXT void alg_free(void* p_free_addr);

MALLOC_MANAGER_FILLE_EXT void display_node(void);

MALLOC_MANAGER_FILLE_EXT void test_all_case(void);

MALLOC_MANAGER_FILLE_EXT void alg_mallo_deinit(void);

3>测试

Case1:申请的空间大于剩余内存块的大小时，申请失败

case2:只有1个空闲的内存块1，申请空间成功，此时系统有1个已经分配的内存块1和1个新的空闲内存块2，见下图：

malloc和free的实现