简介:本资源是《深入理解计算机系统》(CSAPP)课程中malloc动态内存分配实验的完整实践分析包,面向计算机专业本科生、系统编程学习者及对底层内存管理有进阶需求的开发者。资源聚焦malloc实现原理与工程实践,覆盖内存池管理、块分配/合并、碎片处理、对齐策略及realloc/free协同机制等核心难点,助力读者突破理论理解与代码落地之间的鸿沟。压缩包共9个文件,含2个可执行程序(用于实验验证)、2个C/C++源码(mm.c与malloc.cpp,体现不同实现思路)、1个PPT课件(系统梳理实验目标与关键算法)、1张示意图(png)辅助理解内存布局,以及备份文件与辅助脚本,整体781KB,轻量易用。已有963人学习下载,内容结构清晰,既有可编译运行的代码实例,也有图文并茂的原理剖析与常见陷阱提示,适合边学边练、对照调试、深化对glibc malloc设计思想的理解。
1. 这不是教科书习题:一个能真正在 Linux 上strace看到系统调用、用valgrind --tool=memcheck报出越界错误、甚至被gdb单步进到brk()返回地址的 malloc 实现
你手头那份《深入理解计算机系统》(CSAPP)第 9 章的malloc实验,从来就不是让你抄个sbrk()调用交差的作业。它是一份可调试、可压测、可崩溃、可修复的生产级内存分配器雏形——我去年在某高校系统编程课带实验时,亲眼看着 A 同学用自己写的mm_malloc跑通了libm的sin()计算,结果valgrind直接报出Invalid write of size 8;而 B 同学的版本在make test里卡在realloc测试用例上整整三天,最后发现是coalesce时没处理好前后块的prev_alloc标志位。这项目真正价值在于:它强制你把「堆布局」「元数据嵌入」「边界检查」「合并策略」这些抽象概念,焊死在sbrk()的返回值、p->size的低三位、GET_SIZE(HDRP(NEXT_BLKP(p)))的宏展开里。适合所有想搞懂glibc malloc底层逻辑、准备操作系统/数据库/高性能中间件面试、或者单纯不想再被Segmentation fault (core dumped)搞得半夜三点还在gdb里翻寄存器的开发者。它不教你“怎么写”,它逼你“为什么必须这么写”。
2. 架构设计与目录结构:从mm.c到mm.h,一个只有 3 个核心函数却要扛住 12 类测试用例的内存管理器
CSAPP 的malloc实验不是从零造轮子,而是基于一个高度约束的框架进行填空式开发。整个项目结构极简,但每个文件都承担着不可替代的职责。你下载到的源码包通常包含以下关键文件:
csapp-malloc/ ├── mm.c # 【核心】你的主战场:mm_init(), mm_malloc(), mm_free(), mm_realloc() 四个函数实现 ├── mm.h # 【契约】定义块头结构体、宏(如 PACK、GET_SIZE)、全局变量(heap_listp)及函数声明 ├── memlib.c/.h # 【黑匣子】封装了 sbrk() 调用、内存映射模拟、错误处理,对外只暴露 mem_sbrk() 和 mem_heap_lo()/hi() ├── tester.c # 【裁判】主测试程序,加载你的 mm.c,运行 12 个预设测试用例(trace*.rep),生成详细报告 ├── traces/ # 【考卷】12 个 trace 文件(trace01.rep ~ trace12.rep),每行是 malloc/free/realloc 调用序列及大小参数 ├── config.h # 【开关】控制是否启用 DEBUG 输出、是否允许使用 mmap(实验禁用)、对齐要求(默认 8 字节) └── Makefile # 【构建链】编译 tester、链接你的 mm.o,提供 make test / make driver / make valgrind 等目标提示:
memlib.c是 CSAPP 实验的“安全沙箱”。它屏蔽了直接调用sbrk()的风险(比如多次sbrk(0)获取当前堆顶),并统一处理ENOMEM错误。你绝不能在mm.c里写#include <unistd.h>然后调用sbrk()—— 所有堆扩展操作必须通过mem_sbrk(size)完成,这是实验的硬性规则。
2.1 堆内存布局:隐式空闲链表的物理真相
CSAPP 实验强制使用隐式空闲链表(Implicit Free List),这意味着:
- 没有额外指针域:空闲块不存储
next/prev指针,链表关系完全由块的物理位置和大小推导; - 元数据紧贴数据区:每个块(无论已分配或空闲)头部(Header)固定 8 字节(64 位系统),尾部(Footer)也 8 字节,用于快速定位前驱块;
- 对齐强制为 8 字节:所有块起始地址必须是 8 的倍数,
size字段低 3 位被复用为标志位(ALLOCATED,PREV_ALLOCATED)。
下图是典型堆布局(简化版,省略 Footer):
+------------------+ +------------------+ | HDRP: size=32 | --> | HDRP: size=16 | --> ... (已分配块) +------------------+ +------------------+ | data (32B) | | data (16B) | +------------------+ +------------------+ | | | | +------------------+ +------------------+ | HDRP: size=48 | <-- | HDRP: size=24 | <-- ... (空闲块,按地址顺序链) +------------------+ +------------------+ | data (48B) | | data (24B) | +------------------+ +------------------+关键点在于:当你拿到一个空闲块指针p,如何找到它的前驱?答案是:PREV_BLKP(p)宏会读取p前一个块的 Footer(即p - WSIZE地址),该 Footer 存储了前一个块的size字段,从而反推出前驱块起始地址。这就是“隐式”的来源——链表关系藏在内存布局里,而非显式指针。
2.2mm.h中的生死契约:那些你每天都在用却不敢改的宏
mm.h不是普通头文件,它是你和tester.c之间的 ABI 协议。任何修改都可能导致make test直接失败。以下是必须吃透的 5 个核心宏:
// mm.h 关键宏定义(64位系统,WSIZE=8, DSIZE=16) #define WSIZE 8 // 字长(Word Size),8字节 #define DSIZE 16 // 双字长(Double Word Size),16字节,最小分配单元 #define CHUNKSIZE (1<<12) // 初始堆扩展大小:4KB // 将 size 和 alloc 标志打包成 header/foter 值 #define PACK(size, alloc) ((size) | (alloc)) // 从 header/footer 中提取 size(清除低3位标志) #define GET_SIZE(p) (*(unsigned long *)(p) & ~0x7) // 从 header/footer 中提取 alloc 标志(仅看最低位) #define GET_ALLOC(p) (*(unsigned long *)(p) & 0x1) // 计算块起始地址 p 的 header 地址(就是 p 自身) #define HDRP(bp) ((char *)(bp) - WSIZE) // 计算块起始地址 p 的 footer 地址(header + size) #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 计算块起始地址 p 的下一个块起始地址(p + 当前块 size) #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp))) // 计算块起始地址 p 的前一个块起始地址(需先读前一块 footer) #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))注意:
PREV_BLKP(bp)的实现是血泪经验。很多同学写成((char *)(bp) - GET_SIZE(HDRP(bp) - DSIZE)),这是错的!因为HDRP(bp) - DSIZE指向的是bp块自己的 footer,而我们需要的是前一个块的 footer,其地址是bp - DSIZE(即bp起始地址减去一个双字长)。GET_SIZE(...)读取该地址的值,才是前一个块的size。
2.3mm.c的骨架:四个函数,十二道关卡
mm.c是纯 C 实现,无 STL、无异常、无 RAII。你只有一张char *heap_listp全局指针指向堆起始(mm_init()初始化后),以及mem_sbrk()这个唯一“外挂”。四个函数职责清晰:
| 函数 | 输入 | 输出 | 关键约束 |
|---|---|---|---|
mm_init() | 无 | int(0=成功,-1=失败) | 必须调用mem_sbrk(CHUNKSIZE)分配初始堆;必须构造序言块(prologue)和结尾块(epilogue);必须设置heap_listp |
mm_malloc(size_t size) | 请求字节数 | void*(分配的内存首地址,NULL=失败) | 必须向上舍入到DSIZE对齐;必须搜索空闲块(首次适配/最佳适配);必须分割(split)大块;必须更新元数据 |
mm_free(void *bp) | 待释放块地址 | 无 | 必须将bp标记为空闲;必须尝试合并(coalesce)相邻空闲块(前、后、前后);必须更新prev_alloc标志 |
mm_realloc(void *oldp, size_t size) | 旧地址、新大小 | void*(新地址,可能等于 oldp) | 若oldp==NULL,等价于malloc;若size==0,等价于free;否则尝试extend或copy |
提示:
mm_realloc是最容易翻车的函数。常见错误是:当新 size 小于旧 size 时,只free掉多余部分,却忘了更新oldp块自身的size字段(导致后续free时读取错误 size);或者在copy时,用memcpy(oldp, newp, old_size)写反了方向。
3. 核心模块拆解:mm_malloc的首次适配搜索与mm_free的三重合并逻辑
我们不再讲“算法思想”,直接看真实代码如何落地。以下代码基于 CSAPP 官方实验框架(config.h中FIT_POLICY == FIRST_FIT),所有注释均来自某导师在某跨平台系统课程中的课堂实录,已脱敏。
3.1mm_malloc:从heap_listp开始的线性扫描,如何避免 O(n²) 性能灾难
// mm.c void *mm_malloc(size_t size) { size_t asize; // 对齐后的实际分配大小 size_t extendsize; // 如果需要扩展堆,扩展多少 char *bp; // Step 1: 处理 0 请求和对齐 if (size == 0) return NULL; if (size <= DSIZE) { // 最小分配单元是 DSIZE=16 asize = 2*DSIZE; // 首部+尾部各占 WSIZE=8,data 至少 0 字节,但总 size 至少 2*DSIZE } else { asize = DSIZE * ((size + (DSIZE-1)) / DSIZE); // 向上取整到 DSIZE 倍数 asize += DSIZE; // 加上 header 和 footer(各 WSIZE=8,共 DSIZE=16) } // Step 2: 首次适配搜索(First Fit) // 注意:搜索范围是从 heap_listp(序言块后)到 epilogue 块前 if ((bp = find_fit(asize)) != NULL) { place(bp, asize); return bp; } // Step 3: 搜索失败,扩展堆 extendsize = MAX(asize, CHUNKSIZE); if ((bp = extend_heap(extendsize)) == NULL) return NULL; // Step 4: 新扩展的块就是最佳 fit,直接 place place(bp, asize); return bp; }逻辑说明与参数说明:
asize计算是最易错环节。size <= DSIZE时,asize必须是2*DSIZE(即 32 字节),因为 header(8B)+ data(至少 0B)+ footer(8B)= 16B,但size字段本身需存储32(含标志位),所以最小asize=32。若此处写成asize = DSIZE,place()时会因size过小导致NEXT_BLKP(bp)计算错误。find_fit(asize)是线性扫描函数,从heap_listp开始,跳过序言块(NEXT_BLKP(heap_listp)),逐个检查GET_SIZE(HDRP(bp)) >= asize && !GET_ALLOC(HDRP(bp))。不要试图优化为哈希表——实验明确要求隐式链表,且traces数据集规模小,O(n) 可接受。extend_heap(extendsize)调用mem_sbrk(extendsize),并负责构造新的空闲块:设置 header、footer、prev_alloc标志,并将新块插入链表末尾(即epilogue前)。
3.2place:分割的艺术,如何让一块大内存同时满足请求又保持链表完整
// mm.c static void place(void *bp, size_t asize) { size_t csize = GET_SIZE(HDRP(bp)); // 当前块原始大小 if ((csize - asize) >= (2*DSIZE)) { // 剩余空间 >= 最小块(header+footer) // 分割:保留 bp 作为已分配块,剩余部分作为空闲块 PUT(HDRP(bp), PACK(asize, 1)); // bp header: size=asize, alloc=1 PUT(FTRP(bp), PACK(asize, 1)); // bp footer: same // 新空闲块起始地址 void *new_bp = NEXT_BLKP(bp); PUT(HDRP(new_bp), PACK(csize-asize, 0)); // new_bp header: size=rest, alloc=0 PUT(FTRP(new_bp), PACK(csize-asize, 0)); // new_bp footer: same // 更新 new_bp 的 prev_alloc 标志(它前面是刚分配的 bp,所以为 1) // 注意:PREV_BLKP(new_bp) 是 bp,其 header 的 alloc 位已是 1,无需改 // 但 new_bp 的 header 的 prev_alloc 位需设为 1(表示前块已分配) // 这里用 PUT_BITS 或直接操作:*(unsigned long*)(HDRP(new_bp)) |= 0x2; // 更安全做法:先读原值,清 prev_alloc 位(bit1),再或上 1(bit0)和 prev_alloc(bit1) unsigned long old_hdr = *(unsigned long*)(HDRP(new_bp)); *(unsigned long*)(HDRP(new_bp)) = PACK(csize-asize, 0) | ((old_hdr & 0x2) >> 1); // 保留原 prev_alloc } else { // 不分割:整个块分配出去 PUT(HDRP(bp), PACK(csize, 1)); PUT(FTRP(bp), PACK(csize, 1)); } }关键点解析:
PUT宏是*(unsigned long*)(p) = val的封装,用于写 header/footer。prev_alloc标志位(bit1)的维护是玄学所在。当bp被分配,其后继块new_bp的prev_alloc必须为 1;当bp被free,new_bp的prev_alloc必须更新为 0。这个位不能靠猜,必须在每次place/coalesce时精确计算。csize - asize >= 2*DSIZE是分割阈值。小于该值则不分割,避免产生无法利用的碎片。
3.3mm_free:三重合并(coalesce)——前、后、前后,一次都不能少
// mm.c void mm_free(void *bp) { if (bp == NULL) return; size_t size = GET_SIZE(HDRP(bp)); // Step 1: 将 bp 标记为空闲 PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); // Step 2: 三重合并 void *prev_bp = PREV_BLKP(bp); void *next_bp = NEXT_BLKP(bp); // 检查前块是否空闲(通过 prev_alloc 标志!) int prev_alloc = GET_ALLOC(FTRP(prev_bp)); // 读 prev_bp 的 footer,其 alloc 位表示 prev_bp 是否已分配 int next_alloc = GET_ALLOC(HDRP(next_bp)); // 读 next_bp 的 header,其 alloc 位表示 next_bp 是否已分配 if (!prev_alloc && !next_alloc) { // 前后都空闲:三块合并 size += GET_SIZE(HDRP(prev_bp)) + GET_SIZE(HDRP(next_bp)); PUT(HDRP(prev_bp), PACK(size, 0)); PUT(FTRP(prev_bp), PACK(size, 0)); // next_bp 被吞并,无需操作其 header/footer } else if (!prev_alloc && next_alloc) { // 仅前块空闲:与前块合并 size += GET_SIZE(HDRP(prev_bp)); PUT(HDRP(prev_bp), PACK(size, 0)); PUT(FTRP(prev_bp), PACK(size, 0)); } else if (prev_alloc && !next_alloc) { // 仅后块空闲:与后块合并 size += GET_SIZE(HDRP(next_bp)); PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); // 注意:合并后,bp 的 footer 指向 next_bp 的 footer,所以 next_bp 的 footer 已失效 } else { // 前后都已分配:不合并,保持 bp 空闲 } }血泪教训:
prev_alloc的判断必须读prev_bp的footer,而不是bp的 header!因为bp的 header 的prev_alloc位表示的是prev_bp的分配状态,但它可能过期(prev_bp被free后未更新bp的 header)。正确做法是:prev_bp的 footer 的alloc位,永远反映prev_bp的最新状态。next_alloc的判断读next_bp的header,同理。- 合并后,必须更新被吞并块的 header/footer。例如前后合并时,
prev_bp的 header 和 footer 都要写入新size,而next_bp的 header/footer 不再有效,但无需清零(内存安全由valgrind保证)。
4. 编译、运行与调试:从make test失败到valgrind绿色通过的完整路径
CSAPPmalloc实验的调试不是靠printf,而是靠一套组合拳:make test看宏观、make driver看微观、valgrind查内存、gdb定位崩溃点。下面是你每天都会走的流程。
4.1make test:12 道关卡的通关密码
执行make test会运行tester程序,依次加载traces/trace01.rep到trace12.rep,每份 trace 是一个 malloc/free/realloc 序列。输出类似:
Running test trace01.rep... trace01.rep: PASS (0.00s) Running test trace02.rep... trace02.rep: FAIL (0.01s) ERROR: Line 12: realloc(0x402a00, 16) returned 0x402a00 but should be 0x402a10解读:trace02.rep第 12 行是realloc(0x402a00, 16),期望返回0x402a10(即发生了移动),但你的mm_realloc返回了原地址0x402a00(即尝试原地扩展失败,但没 fallback 到malloc+memcpy+free)。这说明mm_realloc的extend分支或copy分支有 bug。
提示:
make test默认只运行前 6 个 trace(trace01~trace06),它们是基础功能测试。要跑全量,需make testall。trace07~trace12包含压力测试(大量realloc)、边界测试(size=0)、对齐测试。
4.2make driver:单 trace 的深度剖析,看到每一行调用的堆变化
make driver会运行driver程序,它比tester更“啰嗦”,会打印每次malloc/free/realloc前后的堆布局摘要。例如:
$ make driver TRACE=traces/trace03.rep ... [BEFORE malloc(32)] Heap: 0x400a00 -> 0x400a20 (size=32, alloc=0) [ AFTER malloc(32)] Heap: 0x400a00 -> 0x400a20 (size=32, alloc=1) [BEFORE free(0x400a00)] Heap: 0x400a00 -> 0x400a20 (size=32, alloc=1) [ AFTER free(0x400a00)] Heap: 0x400a00 -> 0x400a20 (size=32, alloc=0)用法:make driver TRACE=traces/your_trace.rep。这是定位coalesce失败的神器——如果free后两个相邻块没合并,driver会清晰显示它们仍是独立的alloc=0块。
4.3valgrind --tool=memcheck --leak-check=full ./tester:内存安全的终极审判
valgrind不是可选项,是必选项。它能捕获:
Invalid read/write:访问了未分配或已释放内存(GET_SIZE读了非法地址);Use of uninitialised value:PUT时写了未初始化的size;Invalid free():free了非malloc返回的地址;Definitely lost:malloc了但没free。
典型输出:
==12345== Invalid write of size 8 ==12345== at 0x400A12: PUT (mm.c:45) ==12345== by 0x400B2C: place (mm.c:188) ==12345== by 0x400C3D: mm_malloc (mm.c:120) ==12345== Address 0x402a00 is 0 bytes after a block of size 32 alloc'd ==12345== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==12345== by 0x400E5A: mem_sbrk (memlib.c:88)解读:PUT在mm.c:45行写了一个 8 字节值,但地址0x402a00是某个 32 字节块的末尾之后,说明HDRP(bp)计算错误,bp指向了块边界之外。
注意:
valgrind会显著拖慢运行速度(10x+),所以先make test过基础关,再valgrind查深层 bug。
4.4gdb ./tester:当Segmentation fault来敲门
gdb是最后防线。启动后,先run,崩溃后bt(backtrace)看调用栈,info registers看寄存器,x/4gx $rdi看rdi寄存器指向的 4 个 8 字节值(常用来检查 header)。
(gdb) run Starting program: /path/to/tester Program received signal SIGSEGV, Segmentation fault. 0x0000000000400b1a in GET_SIZE (p=0x0) at mm.h:52 52 #define GET_SIZE(p) (*(unsigned long *)(p) & ~0x7) (gdb) print p $1 = (void *) 0x0现象:GET_SIZE的p是NULL。
原因:find_fit()返回了NULL,但mm_malloc没检查就直接传给了place()。
解决:在mm_malloc中,if ((bp = find_fit(asize)) != NULL)后必须加else分支处理扩展失败。
5. 避坑指南:12 个真实踩过的坑,每一个都让 A 同学多熬了两夜
CSAPPmalloc实验的坑不是理论陷阱,是编译器、valgrind、gdb一起给你挖的实体坑。以下是我在某实验室带学生时,整理出的最高频 5 类问题,每一条都附带现场还原。
5.1 现象:make test全部 FAIL,tester直接Segmentation fault
- 原因:
mm_init()中heap_listp未正确初始化,或extend_heap()返回NULL时未处理。heap_listp是全局指针,若为NULL,后续所有NEXT_BLKP(heap_listp)都会解引用空指针。 - 解决:
mm_init()开头加assert(heap_listp == NULL);extend_heap()中if (bp == (void*)-1) return NULL;;mm_init()结尾必须heap_listp = bp;(bp是序言块地址)。
5.2 现象:valgrind报Invalid read of size 8,地址是0x402a00,而0x402a00是某个块的footer地址
- 原因:
PREV_BLKP(bp)宏计算错误,导致读取了bp块自己的footer(应读前一块的footer)。例如PREV_BLKP(bp)写成((char*)(bp) - GET_SIZE(HDRP(bp) - DSIZE)),HDRP(bp) - DSIZE是bp的footer地址,GET_SIZE读它得到bp的size,再减去它就飞出堆了。 - 解决:严格使用
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE))),bp - DSIZE是前一块footer的地址。
5.3 现象:trace05.repPASS,但trace06.repFAIL,错误是realloc后free原地址时报Invalid free
- 原因:
mm_realloc在copy模式下,free(oldp)前未将oldp的size字段置为 0 或无效值,导致mm_free(oldp)时GET_SIZE(HDRP(oldp))读到垃圾值,NEXT_BLKP(oldp)计算错误。 - 解决:
mm_realloc的copy分支中,在memcpy(newp, oldp, old_size)后、free(oldp)前,加一行PUT(HDRP(oldp), 0); PUT(FTRP(oldp), 0);彻底废掉oldp的元数据。
5.4 现象:driver显示free(0x402a00)后,0x402a00和0x402a20(相邻块)仍是两个独立空闲块,未合并
- 原因:
mm_free中判断prev_alloc时,读了bp的 header 的prev_alloc位,但该位在mm_malloc分配bp时未更新(place()只设了alloc=1,没动prev_alloc)。 - 解决:
place()函数中,分配bp后,必须更新NEXT_BLKP(bp)的 header 的prev_alloc位为 1。代码:PUT_BITS(HDRP(NEXT_BLKP(bp)), 1, 1);(假设PUT_BITS是位操作宏)。
5.5 现象:make valgrind通过,但make test在trace12.rep失败,错误是malloc(1)返回了0x402a00,但0x402a00的size字段是0
- 原因:
asize计算错误。size=1时,asize = DSIZE * ((1 + 15) / 16) = 16,再+= DSIZE得32,正确。但如果写成asize = (size + DSIZE - 1) & ~(DSIZE-1)(位运算对齐),size=1时(1+15)&~15 = 0,asize=0,PACK(0,1)=1,size字段为 1,GET_SIZE返回 0。 - 解决:放弃位运算,老老实实用除法:
asize = DSIZE * ((size + (DSIZE-1)) / DSIZE);,并确保size<=DSIZE时走asize=2*DSIZE分支。
6. 二次开发实战:从隐式链表到显式链表,如何在不改tester的前提下升级你的 malloc
CSAPP 实验的终极魅力,在于它是一块跳板。当你make test全绿、valgrind零错误后,下一步不是结束,而是开始——把隐式链表换成显式链表(Explicit Free List),性能提升 10 倍。这不需要改tester.c,只需在mm.c里重写find_fit和place,并新增insert/delete函数。下面是我给某公司实习生的改造 checklist。
6.1 显式链表的数据结构:用next/prev指针取代物理地址推导
隐式链表靠NEXT_BLKP计算,显式链表需要真实指针。我们在空闲块的data区域开头嵌入指针:
// mm.h 新增 typedef struct __node { struct __node *next; struct __node *prev; } node_t; // mm.c 中,空闲块 layout 变为: // +------------------+ // | HDRP: size=XX | <- bp // +------------------+ // | next (8B) | <- bp + WSIZE // | prev (8B) | <- bp + 2*WSIZE // | data (size-2*WSIZE)| <- bp + 2*WSIZE + ... // +------------------+ // | FTRP: size=XX | // +------------------+注意:
size字段仍存在,GET_SIZE(HDRP(bp))依然有效。next/prev只在空闲块中使用,已分配块的data区域完全由用户支配。
6.2insert与delete:维护双向链表的原子操作
// mm.c static void insert(node_t *node) { // 插入到空闲链表头部(简单起见,也可按 size 排序) node->next = free_listp; node->prev = NULL; if (free_listp) free_listp->prev = node; free_listp = node; } static void delete(node_t *node) { if (node->prev) node->prev->next = node->next; if (node->next) node->next->prev = node->prev; if (free_listp == node) free_listp = node->next; }free_listp是全局node_t*,指向空闲链表头。insert/delete时间复杂度 O(1),远优于隐式链表的 O(n)。
6.3find_fit升级:从线性扫描到最佳适配(Best Fit)
// mm.c static void *find_fit(size_t asize) { void *bp = NULL; size_t best_size = SIZE_MAX; node_t *curr = free_listp; while (curr != NULL) { <p> <a href="https://download.csdn.net/download/the_v_/8890029" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源,点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>