（转载）内存分配器101——写一个简单的内存分配器

前提

之前学习过手写一个简单的内存分配器，原文是英文的，当初学习的时候便将英文翻译为中文的，方便阅读，当然和原文相比少了点味道。今天整理资料的时候看到了自己的翻译，所以整理下发出来吧，本地的就直接删了。

正文

相关代码在这里：github.com/arjun024/memalloc

原文链接: https://arjunsreedharan.org/post/148675821737/memory-allocators-101-write-a-simple-memory

这篇文章是关于使用C写一个简单的内存分配器。我们将要实现malloc() , calloc(), realloc() 和free()。

这是一篇初级文章，所以我不会详细说明每一个细节。同时实现的内存分配器并不快速和高效，我们不会调整分配的内存使其和 a page boundary 对齐，但是它可以工作，就是这样。

在我们开始之前，你得熟悉一个程序的内存布局。一个进程运行在自己的虚拟空间内，虚拟空间通常包括5部分：

• Text section: 存放二进制指令。

• Data section: 存放非0初始化的静态数据和全局变量。

• BSS (Block Started by Symbol): 存放0初始化的静态数据和全局变量，程序中没有初始化的静态数据会被初始为0并存放到这里。

• Heap: 存放动态分配的数据。

• Stack: 存放局部变量，函数参数，指针等。

如你所见，栈和堆以相反的方向增长。

有时，data, bss 和 heap 统称为 “data segment(数据段)”，末端由一个名为 program break 的指针表明，也可以称为 brk。所以，brk 指针是堆的末尾。

如果想要在堆上分配更多的内存，我们需要请求系统增加 brk，同样的，释放内存的话，需要请求系统减少 brk。

假设运行在Linux上，我们可以使用系统调用函数sbrk()来操作brk。

sbrk(0): 返回brk现在的地址。

sbrk(x): 将brk增加x个字节，以此分配内存。

sbrk(-x): 将brk减少x个字节，以此释放内存。

失败的话，sbrk()返回(void*) -1。

说实在的，在2015年sbrk()不是我们最好的选择。今天更好的选择可能是mmap()。sbrk()不是线程安全的，它只能以LIFO(后进先出)的方式增加或减少。

然而，当申请的内存不太大时，glibc仍然使用sbrk()来实现malloc，所以我们使用sbrk()来实现一个简单的内存分配器。

Malloc()

malloc(size)函数分配size字节的内存，并返回分配内存的指针。

如下所示：

void *malloc(size_t size)
{
    void *block;
    block = sbrk(size);
    if (block == (void*) -1)
    {
        return NULL;
    }
    return block;
}

在上面的代码中，在指定size下我们调用sbrk()函数。

成功后，在堆上分配size个字节的内存。很简单，不是吗？难办的是释放这个内存。

free(ptr)函数通过指针ptr来释放内存块，这个指针必需由malloc(),calloc(),或者realloc()函数返回。

但是要释放一块内存，首先要知道这块内存的大小。在现有的设计方案中，这是不可能的，因为没有对size进行保存。因此要找到一个方来保存分配的内存的size。

此外，操作系统提供的堆内存是连续的，所以我们只能释放堆末尾的内存，不能释放中间的内存。将堆想象为一条长面包，你可以在一端拉伸它，但你必需保持它是一个整体。

为了解决要释放的内存不在堆尾的问题，我们对free memory 和 release memory 做以区分。

从现在起，free memory 不是意味着要将这块内存释放，并还给OS。它仅仅意味着我们将这块内存标记为free，标记为free的内存可以在后面的malloc()函数调用时重新使用。因为不在堆尾的内存不可以被release，所以这是我们唯一的方法。

现在，为每一个分配的内存块存储两个东西：

1. size
2. Whether a block is free or not-free?

为了储存这个信息，为每一个新分配的内存块添加一个header。

struct header_t{
    size_t size;
    unsigned is_free;
};

想法很简单。当程序申请size个字节的内存时，计算total_size = header_size + size，并且调用sbrk(total_size)。我们使用sbrk()返回的内存空间来容纳header和实际的内存块。header是内部管理，对于程序调用者来说是完全不可见的。

现在，每一个内存块看起来像这样：

我们不能确保分配的内存块是连续的，想象调用程序有一个外部的sbrk()，或者在我们的内存块中有一段mmap()的内存。我们还需要一种方法来遍历我们的内存块，因此可以追踪到分配的内存，将其放入list中，header 看起来像这样：

struct header_t {
	size_t size;
	unsigned is_free;
	struct header_t *next;
};

内存块的链式表达像这样：

现在让我们使用一个union和一个16字节的stub变量来包装整个header，这会导致header末尾的地址16字节对齐。回想一下，一个union的大小是它其中最大的数据成员的大小。header 的结尾是内存块的开始，所以内存块的首地址和16字节对齐。

union header {
    struct {
        size_t size;
        unsigned is_free;
        union header *next;
    } s;
    ALIGN stub;
};

对于链表，我们有一个头指针和尾指针。

header_t *head, *tail;

为了防止多个线程同时访问内存，在这里我们使用一个锁。

有一个全局的锁，每次对内存进行操作之前，必需获取锁；操作完成后，必需释放锁。

pthread_mutex_t global_malloc_lock;

malloc()函数现在被修改为：

void *malloc(size_t size)
{
	size_t total_size;
	void *block;
	header_t *header;
	if (!size)
		return NULL;
	pthread_mutex_lock(&global_malloc_lock);
	header = get_free_block(size);
	if (header) {
		header->s.is_free = 0;
		pthread_mutex_unlock(&global_malloc_lock);
		return (void*)(header + 1);
	}
	total_size = sizeof(header_t) + size;
	block = sbrk(total_size);
	if (block == (void*) -1) {
		pthread_mutex_unlock(&global_malloc_lock);
		return NULL;
	}
	header = block;
	header->s.size = size;
	header->s.is_free = 0;
	header->s.next = NULL;
	if (!head)
		head = header;
	if (tail)
		tail->s.next = header;
	tail = header;
	pthread_mutex_unlock(&global_malloc_lock);
	return (void*)(header + 1);
}

header_t *get_free_block(size_t size)
{
	header_t *curr = head;
	while(curr) {
		if (curr->s.is_free && curr->s.size >= size)
			return curr;
		curr = curr->s.next;
	}
	return NULL;
}

解释下这段代码：

检查size是否为0，如果是，返回NULL。

对于合法的size，先获取锁，然后调用get_free_block()函数——它会遍历链表，查找是否已经有被标记为free的内存块可以容纳指定的size。

如果一个比较大的free块被找到，将其标记为not-free，释放全局锁，并且返回块的指针。在这种情况下，header指针指向内存块的header部分。记住，我们要向外部隐藏header部分。当(header+1)时，它指向header末尾的字节，也是实际内存块的首字节。它被强制转为(void*)并返回。

如果没有足够大的free块，我们会通过调用sbrk()函数来扩展堆。堆会被扩展合适的大小以满足size和header的大小。因此，首先计算total_size = sizeof(header_t) + size；然后调用sbrk(total_size)。

在从操作系统获得的内存里，我们首先要构造header。在C语言中，无须将void*强转为其它类型，它始终被安全地提升。这就是为什么没有显式地：header = (header_t*)block。

我们更新next，head，tail指针。如前面所说的，对于调用者我们要隐藏header，因此返回(void*)(header+1)。同时释放全局锁。

free()

现在我们来看看free()函数怎么做。free()函数首先要判断要释放的内存是否位于堆的尾部。如果是，将其释放并还给操作系统；否则，我们将其标记为free，希望以后可以重新使用。

void free(void *block)
{
	header_t *header, *tmp;
	void *programbreak;

	if (!block)
		return;
	pthread_mutex_lock(&global_malloc_lock);
	header = (header_t*)block - 1;

	programbreak = sbrk(0);
	if ((char*)block + header->s.size == programbreak) {
		if (head == tail) {
			head = tail = NULL;
		} else {
			tmp = head;
			while (tmp) {
				if(tmp->s.next == tail) {
					tmp->s.next = NULL;
					tail = tmp;
				}
				tmp = tmp->s.next;
			}
		}
		sbrk(0 - sizeof(header_t) - header->s.size);
		pthread_mutex_unlock(&global_malloc_lock);
		return;
	}
	header->s.is_free = 1;
	pthread_mutex_unlock(&global_malloc_lock);
}

首先得到我们想要释放的块的header，我们需要得到一个指针。该指针位于块的后面，距离等于header的大小，所以haeder = (header_t*)block - 1；

sbrk(0)返回brk的地址。为了检查要释放的block是否位于堆的末尾，首先找到现在block 的末尾，可以这样计算：(char*)block + header->s.size，然后和brk进行比较。

如果的确在末尾，我们减少堆的大小，并将空间还给操作系统。我们首先重置head和tail指针，然后计算要释放的内存量。总的大小是sizeof(header_t)+header->s.size，我们可以使用sbrk(-x)来释放。

如果要释放的内存不是链表的末尾，我们就简单将header的is_free字段设置为1。

calloc()

calloc(num,nsize)函数分配num个内存，每个大小为nsize字节，并初始化为0。

void *calloc(size_t num, size_t nsize)
{
	size_t size;
	void *block;
	if (!num || !nsize)
		return NULL;
	size = num * nsize;
	/* check mul overflow */
	if (nsize != size / num)
		return NULL;
	block = malloc(size);
	if (!block)
		return NULL;
	memset(block, 0, size);
	return block;
}

realloc()

realloc()改变指定内存块的大小。

void *realloc(void *block, size_t size)
{
	header_t *header;
	void *ret;
	if (!block || !size)
		return malloc(size);
	header = (header_t*)block - 1;
	if (header->s.size >= size)
		return block;
	ret = malloc(size);
	if (ret) {
		
		memcpy(ret, block, header->s.size);
		free(block);
	}
	return ret;
}

首先找到block的header，并察看header的size是否满足要求。如果满足，则什么都不用做。如果不满足，我们使用malloc()重新分配，然后使用memcpy()复制内容。之前的block会被释放。