Skip to content

Latest commit

 

History

History
329 lines (251 loc) · 13.9 KB

一个简单的内存分配器.md

File metadata and controls

329 lines (251 loc) · 13.9 KB
Raw

Memory Allocator 101-写一个简单的内存分配器

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

与本文相关的代码： github.com/arjun024/memalloc

本文的话题是用C语言实现一个简单的内存分配器。我们将实现 malloc(), calloc(), realloc() and free() 。

这是一个入门水平的文章，不会涉及到每个细节。这个内存分配器不会追求速度和效率，也没有考虑内存分配的内存页对齐问题，我们的目标就是实现一个可以工作的内存分配器，仅此而已。

如果你想要查看完整的代码，可以访问github repo memalloc

在开始实现之前，我们需要先熟悉一个程序的内存布局。每个程序都运行在各自的虚拟地址空间中，这个虚拟地址空间包含5个部分：

Text section: 该部分包含供处理器执行的二进制指令序列 Data section: 包含已初始化的静态数据(non-zero initialized static data) BSS (Block Started by Symbol，以符号开头的块) : 包含未未初始化的数据. 未初始化的数据将会被初始化为0并被放在这个区域. Heap: 包含动态分配的数据. Stack: 包含自动分配的变量，函数参数，基指针拷贝等。

Memory layout

如图所示，stack 和 heap 的增长方向是相反的。有时候，我们将 data, BSS 和 heap 三个部分 统称为 "data segment"，data segment的结尾由一个指针确定，叫做 program break, 简称 brk ，brk 指向 heap 的末尾处。

现在，我们要在 heap 上 分配更多的空间，我们需要请求系统往内存增长方向移动 brk，同理，释放内存的时候，需要请求系统往内存减小的方向方向移动brk。

如果我们的系统环境是Linux或者其他的类Unix系统, 我们可以使用系统调用 sbrk() 来操纵 program break 。

调用 sbrk(0) 获取 program break 的当前地址 . 调用 sbrk(x) ，x 为正数时，请求分配 x bytes 的内存空间 . 调用 sbrk(x) , x 为负数时，请求释放 x bytes 的内存空间 .
失败时，sbrk() 返回 (void*) -1.

老实说，sbrk() 并不是我们现在的最佳选择，更好的选择是 mmap() , 而且sbrk() 也不是线程安全的。他只会按照 LIFO 的顺序 增长和缩小内存。 如果在mac 上你执行 man 2 sbrk 它会告诉你

The brk and sbrk functions are historical curiosities left over from earlier days before the advent of virtual memory management.

不过 glibc 的malloc实现 还也是使用 sbrk() 来分配 小尺寸的内存空间。这里我们暂且还是使用 sbrk 。 [1]

malloc()

malloc(size) 函数 分配 size bytes 的 内存，并返回一个指针，指向这块分配到的内存。下面是我们的简易版 malloc ：

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

如代码所示，我们调用sbrk(size). 如果成功，heap上会分配 size bytes 的内存. 这很简单，不是吗?

比较有难度的是如何释放这块内存. free(ptr) 函数释放ptr 指向的内存区域 , 这个ptr 必须是通过前面调用 malloc(), calloc() 或者 realloc() 得到的 . 要释放一块内存，首先需要知道要释放的这块内存的尺寸。 在目前的方案中，这是不可能的，因为尺寸信息没有保存在任何地方. 所有，我们首先需要确定哪里保存这个尺寸信息 。

更重要的一点是，我们需要明白这个由操作系统分配的heap memory是连续的，所有我们只能释放heap末端的内存。我们可以把heap想象成一个枕头面包，你可以在一端进行拉伸和压缩，但是必须保持还是完整的一块面包。 为了能够释放heap 中任意区域的内存，我们需要区分free memory 和 releasing memory 。 事实上，free 一块内存并不总是需要将内存 release 给操作系统，我们可以继续持有这块内存，只是把它标记成free，这是我能想到的最好的方法 .

到这里，我们需要为已分配的每个内存块保存2个信息：

  1. size
  2. 内存块的状态: free 或者 not-free ?

为了保存这些信息，我们需要为每个新分配的内存块增加一个header. 这个header 大体如下所示 :

struct header_t {
	size_t size;
	unsigned is_free;
};

这个Idea很简单，当一个程序请求 size bytes 的内存，我们计算 total_size = header_size + size, 然后调用 sbrk(total_size). 我们使用这个返回的内存空间来填充 header 和 实际的内存块 . 这个 header 在内部管理，对于调用的程序来说是完全透明的.

现在，每个内存块长这样:

memory block with header

我们无法保证，用 malloc 配到的内存块都是相互连续的。想象一下，调用程序另外调用了 sbrk()，或者存在一块 内存，在我们的内存块之间被 mmap() 请求所分配，这些情况下内存块都是不连续的。因此，我们还需要一个方法来遍历我们所有的内存块(为什么要遍历，在实现free()的时候，我们就会知道原因)。，为了保存追踪 malloc 分配到的内存，我们将这些内存库放进一个链表中，此时，header 变成这样：

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

内存块链表变成这样：

linked list of memory blocks

现在，我们将header结构体 和 一个 16字节的stub 封装进一个 union . 这个header 最终会指向一个对齐16字节的地址（因为union的尺寸等于成员中的最大尺寸 ）, 这就保证header的尾部是内存对齐 。header尾部是实际内存块 开始的地方，因此提供给调用者的内存会按16字节对齐。

typedef char ALIGN[16];

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

然后，我们用 head 和 tail 指针 来 跟踪 这个列表。

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，且尺寸合适的内存块. 这里，我们采用First-Fit 方法（首次适配方法）。

如果有找到，我们就将这个内存块标记为 not-free，然后释放全局锁，返回这个内存块的指针。这种情况下，header指针会指向这个找到内存块的header部分，记住，这个header对外部是完全隐藏的。当我们执行 (header + 1) 时，指针指向header尾部的下一个位置，它也是实际内存块的第一个字节，这也是调用者想要的，它会被转换成 (void*)返回。

如果没有找到合适的内存块，就调用 sbrk()来扩充 heap。heap 扩充的长度必须满足请求和size和 header的size。所以，我们首先计算total_size : total_size = sizeof(header_t) + size;. 然后我们请求操作系统来正向移动 program break: sbrk(total_size).

在操作系统给的这块内存中, 我们首先为header分配空间 . 在C语言中, 不需要将void*转换成任意指针的类型，这被认为是始终安全的。 这就是为什么我们没有显示的做转换: header = (header_t *)block; 我们按请求的size填充header，并将它标记为 not-free，然后更新 next指针，并更新 head tail，即更新链表的最新状态。 就像前面说的那样，我们对调用者隐藏了header，只返回 (void*)(header + 1)，然后释放全局锁。

free()

现在，我们看看 free() 应该做些什么。free() 首先要确定，待free的内存块是否在heap的尾部，如果是，我们可以直接release给操作系统，否则，我们将它标记为 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);
}

首先要获取待free的内存块的header，也就是通过一个固定的header大小,获取这个块的header，这里，我我们将block转换成 header 指针，并往前移动一个单元

header = (header_t*)block - 1;

sbrk(0) 获取 program break 的当前位置。为了检查 这个 block 是否是 heap的末尾，我们首先获取当前 block的末尾，这个末尾位置end 可以通过 (char*)block + header->s.size 计算得来。然后用这个end 和 program break 做比较。

如果该block就是program break的末尾，则我们可以直接 缩小 heap的空间，将内存释放给操作系统。我们首先修改链表的 head和tail，即从链表中移除这个 block；然后计算内存需要释放的总量 total_release_size ，sizeof(header_t) + header->s.size。 为了释放这个数量的内存，我们可以 调用 sbrk( -total_release_size )

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;
}

这里，我们检查一下是否越界，然后调用我们的 malloc()，然后使用 memset() 进行初始化。

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 ,然后检查当前 size >= 新size ，如果是，则什么也不干；如果小于，则使用 malloc() 来获取一个 新 size 的block, 然后使用memcpy() 将上下文重定向到这个新的block，并free 旧的block。

Compiling and using our memory allocator.

你可以从作者的github 仓库获取完整的代码 - memalloc. 我们编译这个内存分配器，然后在 这个内存分配器之上 运行 ls .

这里，我们首先将它编译成一个动态库.

$ gcc -o memalloc.so -fPIC -shared memalloc.c

-fPIC 和 -shared 选项 ,前者确保编译输出的是位置无关的代码，后者告诉链接器产生动态链接库。

在linux上，如果你设置环境变量 LD_PRELOAD 为 某个链接库的路径，这个文件会在其他库之前加载。我们可以使用这个技巧来首先加载我们编译好的链接库，在这个shell中执行的后续命令都将使用我们开发的 malloc(), free(), calloc() 和 realloc() .

$ export LD_PRELOAD=$PWD/memalloc.so

Now,

$ ls
memalloc.c		memalloc.so

看呀，这是基于我们的内存分配器的ls. 如果你不信的话，可以在maloc()函数里打印一些debug信息，来验证这是不是真的.

See a list of memory allocators: liballoc [Doug Lea’s Memory Allocator](http://oswego.edu/dl/html/malloc.html dlmalloc). TCMalloc ptmalloc

[1] The GNU C Library: Malloc Tunable Parameters OSDev - Memory allocation Memory Allocators 101 - James Golick