学习虚拟内存，对于其中的malloc的实现有一定兴趣，所以深入研究一下

研究

首先我们知道malloc的函数原型：

1	void * malloc(size_t size);

我们可以用它申请一个指定大小的内存空间，其中size是我们申请的空间，于是我们我们可以简单的实现这个功能：

#include <assert.h>
#include <sys/types.h>
#include <unistd.h>

void * malloc(size_t size){
	void *p = sbrk(0);
	void *request = sbrk(size);
  if(request == (void*)-1){
		return NULL;
	}else{
		assert(request == p+size);
		return p;
	}
}

注意到这里我们使用了一个函数sbrk()

1	void* sbrk(intptr_t increment);

它可以它通过调整堆指针(brk)从而实现对堆的大小的动态调整，其中的参数increment是将要分配的内存空间大小。如果为正数就是增加，如果是负数就是减少，如果为0就返回当前的堆指针。

接下来回过头来看我们的malloc函数，这里我们只实现了分配空间的功能，我们并不能实现free这片空间的效果。

那么我们再来看看free函数是什么样的：

1	void free(void* ptr);

之前使用malloc分配的内存空间，我们可以通过向free提供指向内存块的指针，从而实现对这片空间的”释放”，本质上就是对这篇空间进行标记，标记为可分配的内存空间。

但是我们看看我们的malloc函数，我们将返回的指针传递给free，我们怎么知道应该释放多大的空间呢？所以我们需要一片额外的空间来存储这个内存块的信息。

为了实现这个功能，我们可以将关于内存区域的元信息存储在指针的下方。可能听起来很抽象，我们可以仔细理解一下。我们使用0x10大小的空间去存储这些信息，也就是说当我们分配0x400大小的空间时，实际上分配的是0x410大小的空间。假设指向这片内存空间的指针为p，那么从[p,p+0x10]的部分，存储了我们的元信息，而[p+0x10,p+0x410]的部分则是我们申请的空间，malloc最终返回的地址是p+0x10，也就是说这些信息被隐藏了起来，所以我们说 元信息被存储在指针的下方

现在我们可以将内存块给释放了，但是之后呢？我们从内存中的堆空间应该是连续的，所以我们不能直接将释放的内存块返回给操作系统，这样会导致内存的碎片话。也许你可能会想到，将下方的内存空间上移填补这个内存空缺，但是这样会导致我们难以管理我们的指针，因为内存块的指针仍然指向原来的地址，你也难以修改他。

实现

相反，我们不应该将内存块直接返回给操作系统。我们将其标记为已释放。然后我们尝试解决这个问题。

我们直接将整个内存块的元信息视作一个结构，从而使用链表来简化这个问题:

struct block_meta{
    size_t size;
    struct block_meta *next;
    int free;
    int magic;	// for debug
}

我们可以通过它知道内存块的大小，下一个内存块是什么，以及该内存块是否被释放了，最后还有一个魔法数字（它可以是任何数，用于判断是谁修改了这个内存块）

同时我们为这个链表设置一个头节点

1	void * global_base = NULL;

对于我们的malloc，我们希望它尽可能的使用已经分配了的空间，如果不够再额外请求空间。我们有了这个链表结构之后，我们可以在接受空间申请的请求之后，遍历查询链表，查看我们是否有足够的空闲块。


struct block_meta * find_free_block(struct block_meta ** last,size_t size){
	struct block_meta * current = global_base;	//从第一个内存块开始
	while (current && !(current->free && current->size >= size)){
		*last = current;
		current = current->next;
	}
	return current;
}

如果出现空闲块无法满足内存空间的申请需求时，我们使用sbrk()申请调用更多的堆空间：

struct block_meta * request_space(struct block_meta * last,size_t size){
	struct block_meta * block;
	block = sbrk(0);
	void * request = sbrk(size + META_SIZE);
//	assert(request == (void *)block + size + META_SIZE);
	if(request == (void *)-1){
		return NULL;
	}
	if(last){	//如果不是第一次请求，就更新前一个块
		last->next = block;
	}
	block->size = size;
	block->next = NULL;
	block->free = 0;
	block->magic = 0x12345678;
	return block;
}

现在我们有了检查空闲空间和分配空闲空间的辅助函数，我们可以在此基础上实现malloc。如果我们的全局基地指针是NULL，那么我们需要设置一个新的块作为我们的基地指针，如果不是NULL我们就可以检查现有的块。

void * malloc(size_t size){
	struct block_meta * block;
	if(size <= 0){
		return NULL;
	}

	if(!global_base){
		block = request_space(NULL,size);
		if(!block){
			return NULL;
		}
		global_base = block;
	}else{
		struct block_meta * last = global_base;
		block = find_free_block(&last,size);
		if(!block){
			block = request_space(last,size);
			if(!block){
				return NULL;
			}
		}else{
			block->free = 0;
			block->magic = 0x77777777;
		}
	}
	return (block + 1);	//block实际上是结构体的指针，这里加上一，指针指向分配的内存空间起点
}

我们对malloc所作的一切都是为了我们的free,接下来，我们将在malloc的基础上实现我们的free。它要做的主要工作就是将结构体中的free设置为0，为了准确的定位到结构体的地址，我们先定义一个函数：

1
2
3

struct block_meta * get_block_ptr(void * ptr){
    return (struct block_meta *)ptr - 1;
}

现在我们有了这个，我们就可以写出：


void free(void * ptr){
	if(!ptr){	//free函数需要考虑free(NULL)的情况下，不会释放任何地方
		return;
	}
	struct block_meta * block_ptr = get_block_ptr(ptr);
	assert(block_ptr->free == 0);
	assert(block_ptr->magic == 0x77777777 || block_ptr->magic == 0x12345678);
	block_ptr->free = 1;
	block_ptr->magic = 0x55555555;
}

现在我们就有了自己的malloc和free函数了

既然我们已经实现了malloc和free，我们为什么不在此基础上实现其他的函数便于我们的内存分配和使用呢？

我们再实现一个realloc和calloc：

1	void realloc(void ptr, size_t size)

这个时realloc的函数原型，我们传递一个已分配的指针，然后重新分配它的大小。

基于我们的malloc，它的实现较为简洁：

void * realloc(void *ptr,size_t size){
	if(!ptr){	//包含malloc的功能
		return malloc(size);
	}
	struct block_meta * block_ptr = get_block_ptr(ptr);
	if(block_ptr->size >= size){	//如果现有的内存空间大于想要的内存空间，就返回当前指针
		return ptr;
	}

	void * new_ptr;
	new_ptr = malloc(size);
	if(!new_ptr){
		return NULL;
	}
	memcpy(new_ptr,ptr,block_ptr->size);	//将原来的内存块中的程序移动到新的内存空间中
	free(ptr);
	return new_ptr;
}

这样我们就实现了realloc的实现，然后我们再尝试一下calloc:

1	void *calloc(size_t num, size_t size);

它的作用是分配num个大小为size的内存块，并将其内存初始化为0

在malloc的基础上，它的实现也比较简单：

void *calloc(size_t num, size_t size){
	size_t m_size = num * size;
	void * ptr = malloc(m_size);
	memset(ptr,0,m_size);
	return ptr;
}

到此为止，我们就实现了基本的内存分配和释放管理，我们可以使用这些函数来进行一些日常的操作。

使用

写一个test函数测试以下我们的程序的功能性：

#include <stdio.h>
#include "malloc.h"

int main(){
	int *arr = calloc(10,sizeof(int));
	int **p_arr = calloc(10,sizeof(int*));
	int i;
	for(i=0;i<10;i++){
		arr[i] = i;
		p_arr[i] = &arr[i];
	}

	printf("arr : %p\n",arr);

	for(i=0;i<10;i++){
		printf("[%p] : %d\n",p_arr[i],*p_arr[i]);
	}
}

这里记录一下输出：

中间那一串十六进制数据是我们内存块的结构体数据，还是很神奇的

Ylin's Blog

46:动手实现内存分配

研究

实现

更多

使用