TLPI：动态内存分配

Posted 2024-10-22 Updated 2024-12- 8

By Ray Lyu

18~24 min read

堆内存

动态内存分配是一种很常见的行为，因为很多数据结构的大小只有当程序跑起来之后才能确定，此时我们一般从堆（heap）中申请（事实上也可以从栈上申请，但这里不谈）。堆是一段长度可变的连续虚拟内存，始于进程的“未初始化数据段末尾”，随着内存的分配和释放而增减。堆的末端称为“program break”，用户程序可以通过系统调用（e.g. brk、sbrk）对其进行增减。

malloc 和 free 原理

在 C 程序中基于堆进行动态内存分配最常用的库函数（分配器）就是 malloc 和 free 了。但它们并不会简单地增减 program break，而是存在一套灵活的内存管理机制，从而只在必要的时候基于系统调用来调整 program break。这样使得用户接口更简单，因为复杂的内存管理已经对用户透明。

在上述内存管理机制中，会为用户进程维护空闲内存块的列表（e.g. 双向链表）。malloc 会扫描空闲内存列表，并找到一块合适的空闲内存块（e.g. first-fit、best-fit）。如果找到的是一个较大的内存块，则需要将剩余内存切割出去，成为一个新的空闲内存块。如果在空闲内存列表中找不到合适的内存块，则会调用 sbrk() 以申请更多的内存。此时 malloc 往往不会仅申请用户指定的 size，而是一次性申请一块更大的内存空间加入内存块列表。free 将已使用的内存块标记为未使用并重新加入空闲内存块列表中。free 释放的过程中可能会将要释放的内存块与前后的空闲内存块进行合并。

吞吐率与内存使用率

作为一个内存管理模块，分配器需要满足下面两个目标，

最大化吞吐率
最大化内存使用率

类似于 k8s 调度器需要在调度吞吐和调度质量之间寻求一个平衡，内存分配器也需要在对分配请求的处理吞吐与内存使用率之间进行适当的平衡。

造成内存使用率低的主要原因是碎片。在内存分配器的场景下，碎片可以分为“内部碎片”和“外部碎片”。内部碎片是因实际分配的块比有效载荷（用户申请量）大时发生的。外部碎片则是当空闲内存总量足够，但是却没有某一个单独的块可以满足分配请求时发生的。外部碎片的量化要比内部碎片的量化困难得多，因为它与实际的分配请求有关。由于外部碎片难以量化和预测，所以分配器通常采用启发式的策略试图维持少量的大空闲块，而不是维持大量的小空闲块。

简单实现

在实现一个分配器时，我们必须要考虑以下问题：

如何组织空闲块
如何选择空闲块
选择一个较大的空闲块后做分割
释放一个空闲块后做合并

以下是 CSAPP malloc lab 的一个简单实现版本，功能正确，但性能较差。该实现参考书中的实现示例，基于隐式空闲链表，使用立即边界标记合并方式（详参 [2]）。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

#define WSIZE   4
#define DSIZE   8
#define ChUNKSIZE   (1<<12) // 初始空闲块的大小和扩展堆时的默认大小，4MB

#define MAX(x,y)    ((x) > (y) ? (x) : (y))

#define PACK(size, alloc)   ((size) | (alloc)) // 将块的大小和块是否分配的信息组合在一起，成为一个 Header 或者 Footer

#define GET(p)  (*(unsigned int*)(p)) // 64 位机器上，unsigned int 占 4 个字节
#define PUT(p, val)  (*(unsigned int*)(p) = (val))

#define GET_SIZE(p)     (GET(p) & ~0x7)
#define GET_ALLOC(p)    (GET(p) & 0x1)

#define HDRP(bp)    ((char*)(bp) - WSIZE) // 块紧跟在header之后，char* 强转是不可少的，否则 bp-4 就是按照bp的类型大小向前移动对应的4个单位
#define FTRP(bp)    ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE((char*)(bp) - WSIZE))
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE((char*)(bp) - DSIZE))

static char* headp_listp;

int is_epilogue(void *bp) {
    return GET_SIZE(HDRP(bp)) == 0;
}

// void show_blocks_status() {
//     printf("\n");
//     void *bp = headp_listp;
//     while (!is_epilogue(bp)) {
//         if (GET_ALLOC(HDRP(bp)) == 1) {
//             printf("\tused\t");
//         } else {
//             printf("\tunused\t");
//         }
//         printf("%d WSIZE\t\n", (GET_SIZE(HDRP(bp))) / WSIZE);
//         bp = NEXT_BLKP(bp);
//     }
//     printf("\n");
// }

// 合并块
static void *coalesce(void *bp) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 前一个块是否被分配
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 后一个块是否被分配
    size_t size = GET_SIZE(HDRP(bp));   // 当前块的大小
    if (prev_alloc && next_alloc) {
        return bp;
    }

    if (prev_alloc && !next_alloc) { // 合并后面的块
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0)); // 更新 header 块
        PUT(FTRP(bp), PACK(size, 0)); // 更新 footer 块
    } else if (!prev_alloc && next_alloc) { // 合并前面的块
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp); // 更新块指针
    } else { // 合并前面和后面的块
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))) + GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    return bp;
}

static void *extend_heap(size_t words) {
    char *bp;
    size_t size;

    size = (words % 2) ? ((words + 1) * WSIZE) : (words * WSIZE); // 申请空间要双字对齐
    bp = mem_sbrk(size);
    if (bp == (void *)-1) {
        return NULL;
    }
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

    return coalesce(bp);
}

int mm_init(void) {
    headp_listp = mem_sbrk(4 * WSIZE);
    if (headp_listp == (void *)-1) {
        return -1;
    }
    PUT(headp_listp, 0); // 起始位置
    PUT(headp_listp + 1 * WSIZE, PACK(DSIZE, 1));   // 序言块 header
    PUT(headp_listp + 2 * WSIZE, PACK(DSIZE, 1));   // 序言块 footer
    PUT(headp_listp + 3 * WSIZE, PACK(0, 1));       // 结尾块
    headp_listp += (2 * WSIZE);

    // 第一次扩展堆
    if (extend_heap(ChUNKSIZE / WSIZE) == NULL) {
        return -1;
    }
    // printf("\n\tafter initialization:");
    // show_blocks_status();

    return 0;
}

void mm_free(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

void *find_fit(size_t asize) {
    void *bp = headp_listp;
    while(!is_epilogue(bp)) {
        if (GET_SIZE(HDRP(bp)) >= asize && !GET_ALLOC(HDRP(bp))) {
            return bp;
        }
        bp = NEXT_BLKP(bp);
    }
    return NULL;
}

void place(char *bp, size_t asize) {
    size_t total_size = GET_SIZE(HDRP(bp));
    size_t remaining_size = total_size - asize;
    if (total_size - asize >= 2 * DSIZE) {  // 需要分割
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        PUT(HDRP(NEXT_BLKP(bp)), PACK(remaining_size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(remaining_size, 0));
    } else {                                // 不需要分割
        PUT(HDRP(bp), PACK(total_size, 1));
        PUT(FTRP(bp), PACK(total_size, 1));
    }
}

void *mm_malloc(size_t size) {
    size_t asize;   // adjusted block size
    size_t extendsize;
    void *bp;

    if (size == 0) {
        return NULL;
    }

    if (size <= DSIZE) {
        asize = 2 * DSIZE;  // 强制让最小块为 4 WSIZE，中间两个 WSIZE 满足对齐要求，首尾 SIZE 做 header 和 footer
    } else {
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
    }

    if ((bp = find_fit(asize)) != NULL) {
        // printf("\tbefore place:");
        // show_blocks_status();

        place(bp, asize);
        return bp;
    }

    extendsize = MAX(asize, ChUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
        return NULL;
    }
    place(bp, asize);
    return bp;
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    void *old_bp = ptr;
    void *new_bp;
    size_t copySize;

    new_bp = mm_malloc(size);
    if (new_bp == NULL) {
        return NULL;
    }
    copySize = GET_SIZE(HDRP(old_bp)) - DSIZE;
    if (size < copySize) {
        copySize = size;
    }
    memcpy(new_bp, old_bp, copySize);
    mm_free(old_bp);
    return new_bp;
}

参考资料

《Linux 系统编程》（Ch7）
《深入理解计算机系统》（Ch9）
http://csapp.cs.cmu.edu/3e/labs.html

计算机系统基础

Linux 系统编程

License: CC BY 4.0