Soptq

Soptq

Probably a full-stack, mainly focusing on Distributed System / Consensus / Privacy-preserving Tech etc. Decentralization is a trend, privacy must be protected.
twitter
github
bilibili

编写你自己的内存分配器

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

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

操作系统的内存存储#

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

Different partitions in the RAM

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

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

  1. sbrk(0) 会返回当前的 brk 地址。
  2. sbrk(n) 会将 brk 向上扩展 n 个字节。这里 n 是正数。
  3. 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 指着说明这块内存是可以被释放给操作系统的。释放时注意还要更新链表。

这样,内存分配中核心的两个函数就被我们实现了。接下来我们继续实现两个非常有用的函数:callocrealloc

实现 calloc(size_t num, size_t nsize)#

calloc(size_t num, size_t nsize) 接受一个数量参数 num 和一个大小参数 nsize,然后分配 numnsize 大小的内存块,并将所有分配的内存赋 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;
}
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。