Note: 本文基本上是Malloc Tutorial的整理和翻译。
malloc是做什么的?
malloc是C程序中用来分配内存的一个库函数。C++里的new也是调用malloc实现的。为了清楚内存是怎么分配的，我们用C来实现一个简单的malloc函数.
malloc,brk以及sbrk系统调用
首先，我们知道计算机内存一般是分为下面几部份的：
- Text Segment : 程序本身
- Data Segment : 所有初始化的全局变量和静态变量
- BSS Segment : 所有未初始化的全局变量
- Heap Segment : 程序中动态分配的内存区
- Stack Segment : 程序中局部变量的内存区
计算机内存组织一般如下图所示:
而其中Heap就是用malloc分配的内存，一般分为mapped region, unmapped region, 如下图所示:
malloc函数可以在Heap Segment里unmapped region区域分配指定大小的内存并返回起始地址。
清楚了内存和malloc的关系，我们可以定义malloc的函数原型如下:
void* malloc(size_t size);
从上面Heap Segment示意图中能够知道Heap Segment是由starting address, break point和maximum limit定义的一段连续内存空间。如果我们在Heap里分配内存，那我们必须知道break point的地址。我们可以借助brk和sbrk系统调用。
brk将break point设置到指定的地址，如果成功返回0，否则返回1。sbrk则将break point向前移动指定的字节大小。失败则返回(void*)-1,执行成功后的返回值根据不同实现而不同。
当增加地址为零时(
sbrk(0))，返回值是实际的break point地址
brk以及sbrk的函数原型
int brk(const void *addr);
void* sbrk(intptr_t incr);
malloc实现
有了上面背景知识，我们可以开始一步一步实现malloc。
一个简单的malloc实现
首先，借助于上面的sbrk我们可以很容易想到一个实现malloc的方法，即首先用sbrk(0)得到break point地址，然后调用sbrk来调整大小，如果成功则返回之前得到的break point的地址。代码如下:
#include <sys/types.h>
#include <unistd.h>
void *malloc(size_t size) {
void *p;
p = sbrk (0);
/* If sbrk fails , we return NULL */
if (sbrk(size) == (void*)-1)
return NULL;
return p;
}
一个简单的malloc函数就这么实现了。我们可以用这个简易版malloc来动态分配内存。但是很快问题就出现了，分配的内存我们没有办法去释放，还需要继续改进。
更实际的malloc实现
- 首先，为了让我们
malloc的memory能够free,我们需要定义free含义，如果一块memory能够再次被malloc分配使用，我们就说这块memory是free掉的。这样，我们很容易就想到使用一个结构体来保存当前分配memory的大小，释放等信息。
typedef struct s_block *t_block;
struct s_block {
size_t size; // size of current block
t_block next; // pointer to next block
int free; // sign to indicate free or not
};
#define BLOCK_SIZE sizeof(struct s_block)
void *base=NULL; // global pointer to the
需要注意的是我们每次调用sbrk的时候需要加上s_block的大小。使用s_block之后Heap Segment是下面这样分布的:
- 有了上面的
s_block之后，每次需要分配内存时我们简单的遍历s_block找到free并且大小满足的s_block就可以了。
t_block find_block(t_block *last , size_t size) {
t_block b=base; // start from the heap starting point
while (b && !(b->free && b->size >= size)) {
*last = b;
b = b->next;
}
return (b);
}
- 如果找不到合适的
s_block,我们需要调用sbrk()来分配内存
t_block extend_heap(t_block last , size_t s){
t_block b;
b = sbrk (0);
if (sbrk(BLOCK_SIZE + s) == (void*)-1)
/* sbrk fails , go to die */
return (NULL);
b->size = s;
b->next = NULL;
if (last)
last ->next = b;
b->free = 0;
return (b);
}
malloc实现
根据之前的思路，为了实现malloc需要下面这些操作:
- 如果是第一次调用
malloc,则调用extend_heap来分配内存并且设置全局变量base - 否则就调用
find_block
void *malloc(size_t size) {
t_block b,last;
if (base) {
/* First find a block */
last = base;
b = find_block(&last ,s);
if (b) {
b->free=0;
} else {
/* No fitting block , extend the heap */
b = extend_heap(last ,s);
if (!b)
return(NULL);
}
} else {
/* first time */
b = extend_heap(NULL ,s);
if (!b)
return NULL;
base = b;
}
return b+1;
}
calloc,free,ralloc实现
malloc类似函数还有:
calloc：除了实现malloc功能之外，还会初始化分配内存的值
void *calloc(size_t nelem, size_t size) {
size = nelem * size;
void *ptr = malloc(size);
memset(ptr, 0, size);
return p;
}
free: 释放malloc,calloc或ralloc分配的内存区域,简单的实现方式就是将s_block里的free标志位置为1
void *get_block_ptr(void *ptr) {
return (t_block)ptr - 1;
}
void free(void *ptr) {
if( !ptr )
return;
t_block p = get_block_ptr(ptr);
assert(p->free == 0);
p->free = 1;
}
ralloc: 调整之前分配的内存大小， 对于新的size小于当前size的，我们可以直接返回，否则重新分配并释放之前的内存
void *ralloc(void *ptr, size_t size) {
if( !ptr )
return malloc(size);
// if request size is smaller than current size, just return
t_block p = get_block_ptr(ptr);
if( p->size >= size )
return ptr;
// or request size is larger than current size, we need
// malloc the new size, copy old data and free old space
void *new_ptr = malloc(size);
if( !new_ptr )
return NULL;
memcpy(new_ptr, ptr, p->size);
free(ptr);
return new_ptr;
}
总结
上面实现了一个基本功能的malloc, 不过还有一些功能还需要完善，比如memory 对齐，分配时memory split和释放时memory fragment处理等