“编写你自己的内存分配器”

在这篇文章中我将带着大家实现一个自己的内存分配器。这个内存分配器 十分简单 ，它旨用于帮助大家对操作系统内部的内存分配过程有更深的理解。所以它并不会很高效。简单的说，这个内存分配器 只是能用 ( Just works )。

我们主要会使用 C 语言来进行编程。但在编程前，我们首先要对我们操作系统的内存存储方式有一定的了解。

操作系统的内存存储

我们的操作系统的内存中，主要存在着 5 个部分。这 5 个部分分别是：

kernel: 存储着我们的操作系统的内核。
stack: 存储着程序的变量。
heap: 存储着程序动态申请的内存。
data: 存储着静态变量。
text: 存储着程序的代码段。

其中，相对动态的 heap 和 stack 的大小是不固定的，heap 可以往上（往高内存地址）生长，stack 可以往下（往低内存地址）生长。所以当我们在 C 中使用 malloc 等命令时，实际上就是 heap 区域往上生长了一点。我们可以从图中看出在 heap 的顶部有一个 brk 指针，这个指针限定了 heap 的区域范围。所以当我们要 malloc 一段新内存的时候，就是把 brk 指针往上移。移动 brk 的过程在 Unix/Linux 系统下有一个专门的函数叫做 sbrk。这个函数有 3 个用法：

sbrk(0) 会返回当前的 brk 地址。
sbrk(n) 会将 brk 向上扩展 n 个字节。这里 n 是正数。
sbrk(-n) 会将 brk 向下扩展 n 个字节。这里 n 是正数。

sbrk() 分配成功的话会返回分配的区域的启始地址。若 sbrk() 内存分配失败，他会返回 (void *) -1 （即 0xFFFFFFFF）

sbrk() 实际上已经被现代操作系统给弃用了，因为已经有了更好的内存分配方法，例如 mmap()。但由于 sbrk() 简单且直观，所以我们在这里仍然使用 sbrk() 来做内存分配。

实现 `malloc(size_t size)`

malloc(size_t size) 接受一个参数代表需要分配的内存大小。我们很直观的就可以想到是不是直接调用 sbrk(size) 就完事儿了？

确实，直接调用的话可以分配出新的内存，但当我们使用完这段内存，对它进行 free() 释放的时候就出问题了。因为我们不知道这一段需要被释放的内存有多大，所以我们没有办法释放。

另外，由于 brk 指针是始终指向 heap 的顶部的，而我们是通过调整 brk 的位置来将内存还给操作系统。所以我们其实只能 真正释放 （还给操作系统）处于 heap 顶部的内存分配，中间的内存其实是很难被真正释放的（你可以做一个整体迁移，但这样消耗太大了）。虽然我们无法真正释放处于中间的内存，但我们可以把它们有效的利用起来，即 标记被释放的内存，使这一段内存可以被另一段程序给「分配」 。所以，我们 malloc 的时候实际上包括一个循环所有我们所有已经分配的内存，查询其是否被释放以及其大小是否足够满足我们要求的过程。

最后，sbrk() 命令并不是只有我们才可以调用，而是任何程序都可以调用。所以在我们分配一段内存的时候，完全有可能出现另一个程序也来分配一段内存的情况。换句话说，我们没有办法保证我们分配的内存在物理地址上是连续的， 这将使我们在上一段所说的「循环」过程无法进行 。所以我们要通过链表的方式把我们分配的每一段内存链接起来。

所以我们在 malloc 时要把关于这一段分配的内存的一些必要信息一起写入。准确的讲是写在分配的内存的前面。这些必要信息包括 分配的内存大小，是否被释放 以及 下一个内存分配的地址。

struct header_t {
    size_t size;
    unsigned is_free;   /* shorthand for unsigned int */
    union header *next; /* linked list for our heap */
}

然后，为了方便处理，我们希望我们所有分配的内存的头部信息的大小是一样的。所以我们要做一个对齐，使所有头部信息的大小都是 16 比特。

typedef char ALIGH[16]; /* ALIGH is 16 bits */

union header {
    struct {
        size_t size;
        unsigned is_free;   /* shorthand for unsigned int */
        union header *next; /* linked list for our heap */
    } s;
    ALIGH stub;
};

typedef union header header_t;  /* so header_t will have a fixed 16 bytes size */

为了方面循环链表和释放，我们还要有两个指针来指向链表的头部和尾部。

/* a head and tail pointer to track our heap */
header_t *head, *tail;

最后，我们为了避免竞争，还要引入 互斥锁。

/* set a mutex lock to prevent concurrently accessing memory */
pthread_mutex_t global_malloc_lock;

这样，我们就终于可以来完成我们的 malloc() 函数了。

header_t *get_free_block(size_t size);

/* sbrk(0) => return the current address of program break
 * sbrk(x) => increase brk by x bytes
 * sbrk(-x) => decrease brk by x bytes
 * if sbrk() fails, it will return (void *) -1 / 0xFFFFFFFF
 * */
void *malloc(size_t size) {
    if (!size)  /* if the requested size is zero, return */
        return NULL;
    size_t total_size;  /* header size + block size */
    void *block;
    header_t *header;

    pthread_mutex_lock(&global_malloc_lock);    /* acquire the lock */
    header = get_free_block(size);  /* check if there have available free block that has a size of bigger than ‘size’ */
    if (header) {   /* exists */
        header -> s.is_free = 0;    /* this block is not free */
        pthread_mutex_unlock(&global_malloc_lock);  /* release the lock */
        return (void *)(header + 1);    /* return the address of the block instead of the header */
    }

    total_size = sizeof(header_t) + size;   /* not exists, we have to create one */
    block = sbrk(total_size);
    if (block == (void *) -1) { /* malloc failed */
        pthread_mutex_unlock(&global_malloc_lock);  /* release the lock */
        return NULL;
    }

    header = block;
    header -> s.size = size;
    header -> s.is_free = 0;
    header -> s.next = NULL;

    if (!head)  /* if the head pointer of the heap not exists, make header be the head */
        head = header;
    if (tail)   /* if the tail pointer of the heap exists, */
        tail -> s.next = header;
    tail = header; /* make this header be the tail (or the new tail) */
    pthread_mutex_unlock(&global_malloc_lock);  /* release the lock */
    return (void *)(header + 1);    /* return the address of the block instead of the header */
}

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

malloc() 的流程如下：首先检验传入的参数 size 是否合法。若合法，则继续尝试取得互斥锁。成功得到锁🔒后，通过 get_free_block() 寻找内存分配链表中的被释放的、空间足够大的内存块。若找到了，则将其标记为未释放，然后释放互斥锁，返回这块内存地址。注意这里 (void *)(header + 1) 的意思是返回分配的 内存块 地址，因为 header 是头部信息的地址，头部信息又占用 16 比特。另一方面，如果没有在已分配的内存中找到合适的内存块，我们就需要通过 sbrk 新申请一块。这里我们申请的大小等于我们的头部信息大小和内存块大小之和。申请若成功，则将其链接到我们的链表上，返回内存块地址。

实现 `free(void *block)`

free(void *block) 接受内存块的地址，并将其释放。释放策略如下：如果这块内存刚好在链表的末尾，即 brk 上，我们可以调用 sbrk() 把这块内存还给操作系统。若这块内存在链表中间，则我们简单的将其标记为「释放」。

/* if the block-to-be-freed is at the end of the heap, then we return it to the OS.
 * otherwise we simply mark it as ‘free’
 * */
void free(void *block){
    header_t *header, *tmp;
    void *programbreak;

    if (!block) /* if this block not exists */
        return;

    pthread_mutex_lock(&global_malloc_lock);
    header = (header_t *)block - 1; /* header address */

    programbreak = sbrk(0); /* get current brk location */

    if ((char *)block + header -> s.size == programbreak) { /* this is the end of the heap */
        if (head == tail) { /* currently there is only one block in the heap, we will erase it */
            head = tail = NULL;
        } else {    /* otherwise we will remove the tail */
            tmp = head;
            while (tmp) {
                if (tmp -> s.next == tail) {
                    tmp -> s.next = NULL;
                    tail = tmp;
                }
                tmp = tmp -> s.next;
            }
        }
        /* release the space */
        sbrk(0 - sizeof(header_t) - header -> s.size);
        pthread_mutex_unlock(&global_malloc_lock);
        return;
    }

    /* if this block is in the middle of our heap, we mark it as ‘free’ */
    header -> s.is_free = 1;
    pthread_mutex_unlock(&global_malloc_lock);
}

这段代码中，(header_t *)block - 1 的意思是将内存块地址映射到 header * 后，-1 得到头部信息的地址。 (char *)block 是内存块的初始地址，初始地址加上内存块大小就是终止地址，若终止地址被 brk 指着说明这块内存是可以被释放给操作系统的。释放时注意还要更新链表。

这样，内存分配中核心的两个函数就被我们实现了。接下来我们继续实现两个非常有用的函数：calloc 和 realloc

实现 `calloc(size_t num, size_t nsize)`

calloc(size_t num, size_t nsize) 接受一个数量参数 num 和一个大小参数 nsize，然后分配 num 个 nsize 大小的内存块，并将所有分配的内存赋 0 然后将初始地址返回。

/* calloc allocates ‘num’ elements with size of ‘nsize’.
 * */
void *calloc(size_t num, size_t nsize) {
    if (!num || !nsize)
        return NULL;    /* num and nsize must be valid */

    size_t size;
    void *block;
    size = num * nsize;
    if (nsize != size / num)
        return NULL;    /* multiply overflow */
    block = malloc(size);
    if (!block)
        return NULL;    /* malloc failed */
    memset(block, 0, size); /* reset all value in this block */
    return block;
}

值得注意的是中间有一个判断溢出的过程。其他的应该问题都不大。

实现 `realloc(void *block, size_t size)`

realloc(void *block, size_t size) 将一个内存块重新分配大小。实际上这里的逻辑是这样的：若重新分配的大小 小于等于 原来的内存块大小，那么函数直接返回原来的内存块地址，即不动它。若重新分配的大小大于原来的内存块大小，则调用 malloc 新分配一块内存块，然后将原来的内存块里的内容复制过去，再返回新的内存块地址。

/* change the given block’s size
 * */
void *realloc(void *block, size_t size){
    if (!block || !size)    /* block and size must be valid */
        return NULL;

    header_t *header;
    void *ret;
    header = (header_t *)block - 1;
    if (header -> s.size >= size)   /* if the original block already has enough space for the data */
        return block;
    ret = malloc(size); /* allocate a new space */
    if (ret) {
        memcpy(ret, block, header -> s.size);   /* move data in block to ret */
        free(block);    /* free original block */
    }
    return ret;
}

本文作者 Auther：Soptq

本文链接 Link： https://soptq.me/2020/07/18/mem-allocator/

发现存在错别字或者事实错误？请麻烦您点击这里汇报。谢谢您！

Make your own memory allocator

操作系统的内存存储

实现 `malloc(size_t size)`

实现 `free(void *block)`

实现 `calloc(size_t num, size_t nsize)`

实现 `realloc(void *block, size_t size)`

CATALOG

RELATED POSTS

FEATURED TAGS

FRIENDS

操作系统的内存存储

实现 malloc(size_t size)

实现 free(void *block)

实现 calloc(size_t num, size_t nsize)

实现 realloc(void *block, size_t size)

CATALOG

RELATED POSTS

FEATURED TAGS

FRIENDS

实现 `malloc(size_t size)`

实现 `free(void *block)`

实现 `calloc(size_t num, size_t nsize)`

实现 `realloc(void *block, size_t size)`