简介一套帮助开发者动手实现内存分配函数的示例代码面向希望深入理解 malloc 工作原理的 C 语言开发者与操作系统学习者。项目围绕 my_malloc 的完整实现展开通过自定义头文件、核心分配器实现与配套测试用例演示堆内存管理、空闲块拆分合并、内存碎片控制等关键环节并引出首次适配、最佳适配等常见分配策略便于从零观察内存分配器的基本骨架。资源共 3 个文件包含 2 个 C 源文件与 1 个头文件分别对应接口声明、分配器实现与测试验证压缩包仅 3KB结构紧凑适合快速阅读和本地编译运行。已有 1827 人学习下载可用于操作系统实验、内存管理专题或自行扩展 malloc 的练手项目。代码覆盖内存池初始化、按块分配、释放合并及空闲不足时向系统申请更多内存的完整流程配合测试文件可验证基本行为也能帮助理解真实 malloc 在内存对齐、多线程并发等场景下的复杂度。1. 自己动手写malloc先从内存分配器的黑匣子说起malloc就是黑匣子调用拿地址不用了free翻车就段错误。直到有次在模拟项目X里排查内存泄漏被追问“malloc到底怎么把内存给你的”才发现自己对堆管理几乎一无所知。于是花两天翻了常见分配器的实现照样子写了一个能跑的最小malloc函数。这篇就是当时的踩坑记录先讲清楚brk、mmap与128KB阈值再设计header和空闲链表最后给一份能运行的最小实现与避坑清单。适合面试前想弄懂动态内存分配的读者也适合需要定制分配器、替换默认malloc的开发者。2. 前置知识brk、mmap与128KB阈值malloc的两种“进货”方式2.1 sbrk/brk与mmap的适用边界用户态申请内存并不是每次malloc都直接触发系统调用。常见C运行库里的分配器比如ptmalloc一族会把请求分类小请求走brk大请求走mmap。这里有个关键数字MMAP_THRESHOLD默认是128KB。请求大小不超过它时分配器通过sbrk/brk调整程序断点program break来扩大堆超过它时直接用mmap向内核要一块独立的匿名映射。为什么要有两条路brk的好处是开销小、路径短堆整体是一段连续地址小对象密集分配时缓存更友好。但brk的局限也很明显break指针只能在堆顶部整体推进堆中间如果碎成若干小块break无法单独缩回来。mmap则不同它按页映射free时可以直接munmap把内存还给操作系统适合超大块。我在模拟项目X里验证过一个现象频繁malloc/free交替堆顶部被某块长期占用即便其他块都free了break也降不回来top看到的RSS居高不下。这并不一定是泄漏而是brk机制的正常表现。自己动手写时最朴素的策略就是统一用sbrk扩展。完整实现才需要考虑128KB阈值分流因为sbrk拿到的内存一旦破了洞很难归还。这种简化对学习分配器数据结构完全够用但写之前一定要知道有brk和mmap两条腿否则做不到128KB以上大块时你的分配器会吃掉大量虚拟地址空间。2.2 free不等于归还堆的伸缩与内存碎片从哪来很多人误以为free之后内存就立刻还给操作系统了。实际上对于brk分配的小块free只是把块标记为空闲并挂到空闲链表上真正的归还发生在堆顶整块空闲时才有机会trim。这带来一个很有价值的视角malloc管理的是一块“自己的仓库”仓库只在需要扩充时找OS要缩回去是很少见的操作。碎片问题也因此产生。内部碎片是给多了用户要13字节但chunk和header对齐后实际占用48字节多出来的是对齐和头部开销。外部碎片是零散点太多多次malloc/free后堆里出现大量不连续的小空闲块单个块都不够下一个请求用总和却足够。我调试某跨平台系统时遇到过类似场景分配器明明统计出空闲总量有200MB一个32字节的请求却失败就是因为空洞平均分配不均匀没有一块连续空间能覆盖请求。设计分配器时通常用最小块大小和首次适配来抑制外部碎片。最小块保证空闲块不会碎成连header都放不下的渣首次适配从链表头部快速找到第一个能装下的块又避免了遍历整个堆。理解碎片来源之后就能解释为什么很多分配器要维护“空闲链表按大小分类”的bins结构——本质是让不同大小的请求都能找到“刚好够用”的空闲块减少切割造成的二次碎片。2.3 chunk的最小单位对齐、头部开销与top chunkmalloc返回的指针在64位平台必须16字节对齐不只是历史遗留现代SIMD指令和原子操作都依赖对齐。为了做到16字节对齐每个chunk的起址也应当按16字节对齐文件里所有size都必须是16的倍数。头部开销最少是两个size_t一个存当前块大小一个存前一块的大小这是实现前后合并的基础。还有一个特殊chunk叫top chunk它位于堆的最顶端永远处于空闲状态不进入普通空闲链表。malloc时若空闲链表找不到合适块就从top chunk里切一块下来free时如果被释放块正好与top chunk相邻直接合并回top chunk这样操作系统在极少数情况下才能把整块尾部内存收缩掉。自己实现最小版时维护一个heap_end哨兵值用指针比较代替真正的top chunk可以减少很多边界判断这是我在实现过程中比较实用的一个取舍。3. 核心数据结构header设计与双向链表空闲区3.1 header 只放必要字段size、prev_size和两个链表指针一个块的基本形态是“header 数据区”。header必须包含当前块总大小、前一块总大小以及空闲链表指针。空闲链表指针不必单独占空间因为在“空闲”状态下数据区本来就没有用户数据可以直接复用数据区的前16字节来挂next和prev。这样设计后最小块大小是header(32字节) 最小数据区(16字节)向上对齐到16的倍数即48字节。#define ALIGN16(x) (((x) 15UL) ~15UL) typedef struct block { size_t size; // 当前块总大小bit0本块是否空闲 size_t prev_size; // 前一块总大小bit0前一块是否空闲 struct block *next; // 空闲链表后继仅空闲时有效 struct block *prev; // 空闲链表前驱仅空闲时有效 } block_t; #define HEADER_SIZE ALIGN16(sizeof(block_t)) #define MIN_BLOCK_SIZE (HEADER_SIZE ALIGN16(16)) #define BLOCK_FREE 0x1UL这段是数据结构的骨架。注意size的最低1位用来标记当前块是否空闲prev_size的最低1位用来标记前一块是否空闲真正的块大小用高位表示。HEADER_SIZE在64位平台下是32字节本身就满足16字节对齐条件。实现时不要直接写sizeof(block_t)而不用宏因为不同编译器可能插入Padding。用ALIGN16(sizeof(block_t))可以让头部尺寸在任何目标平台都对齐到16字节边界这一步直接影响后面返回指针的对齐性。3.2 空闲块如何组织双向链表与unlink操作空闲块组织成双向链表删节点时需要同时修改前驱和后继否则链表会断。头插法最省事新空闲块插在链表头部malloc查找时从头部开始扫。为什么不用数组或哈希表因为早期分配器的目标不是O(1)查找而是保持简单、稳定、易于合并真实环境中请求大小分布很散链表配合分类bins已经足够优秀。static block_t *free_list NULL; static void unlink(block_t *b) { if (b-prev) b-prev-next b-next; else free_list b-next; if (b-next) b-next-prev b-prev; b-next b-prev NULL; }这段unlink是整个free逻辑里最容易写错的地方只改next不改prev链表就会在某次遍历中突然断掉表现为“malloc偶尔能成功长时间运行后必现段错误”。我的检查习惯是每次unlink后立即打印free_list和相邻节点的前驱后继确认双向一致性再进入下一步功能开发。3.3 first fit vs best fit真实分配器怎么选确定一个块能不能用常见两种策略。首次适配first fit从链表头开始找找到第一个能装下请求的块就返回速度最快但容易产生很多小的“边角料”最佳适配best fit遍历全部空闲块挑一个最接近请求大小的内存密度高但遍历成本高还会留下大量极小的碎块反而加剧外部碎片。我在这份资源里用的是first fit理由有三个一是代码量小、行为直觉二是分配快不追求极致内存密度三是配合split逻辑切分剩余空间能控制碎片规模。ptmalloc在实际实现中用了更复杂的bins分类按大小分桶再配合last remainder技巧减少递归切割。这些属于进阶优化等你的基础版能跑稳定了再引入不迟。4. 实现malloc函数从init到free的一小套可运行代码4.1 初始化堆懒初始化的典型写法分配器的第一个困难是“第一次调用时堆还不存在”。常见做法是懒初始化free_list为空就调用sbrk申请一块初始堆并把整块作为一个大空闲块挂到链表上。#include stdint.h #include unistd.h #define INIT_HEAP (4096 * 4) static block_t *heap_end NULL; static void init_heap(void) { free_list (block_t *)sbrk(INIT_HEAP); if (free_list (void *)-1) { free_list NULL; return; } free_list-prev_size 0; free_list-size INIT_HEAP | BLOCK_FREE; free_list-next NULL; free_list-prev NULL; heap_end (block_t *)((char *)free_list INIT_HEAP); }sbrk(INIT_HEAP)让程序断点向上移动16KB返回值是移动前的老断点也就是新堆的起始地址。这里用4KB的整数倍是因为sbrk本身可能会对齐到页边界但我们不依赖这个假设。INIT_HEAP取16KB足够容纳几百个平均大小为32字节的小对象避免频繁触发二次sbrk。如果sbrk失败返回(void *)-1必须处理错误而不是直接崩溃。注意这里没有用perror打印因为在分配器内部打印可能再次触发内存分配形成死递归最稳妥的是返回NULL把错误交给上层。4.2 分配主流程查找、切分、扩展malloc的核心算法可以压缩成三步对齐请求大小在空闲链表里找块找不到就扩展堆找到后把块切分出需要的部分返回数据区指针。static block_t *find_fit(size_t need) { block_t *p free_list; while (p) { if (p-size need) return p; p p-next; } return NULL; } static block_t *extend_heap(size_t need) { size_t sz ALIGN16(need); block_t *nb (block_t *)sbrk(sz); if (nb (void *)-1) return NULL; if (heap_end nb heap_end) { // 与旧堆尾相邻可以把新块直接接到旧堆尾部 } else { // 地址不连续这里简化处理仍当作独立块 } nb-prev_size 0; nb-size sz | BLOCK_FREE; nb-next free_list; nb-prev NULL; if (free_list) free_list-prev nb; free_list nb; heap_end (block_t *)((char *)nb sz); return nb; } static void split_and_take(block_t *b, size_t need) { size_t raw b-size ~BLOCK_FREE; if (raw - need MIN_BLOCK_SIZE) { block_t *rem (block_t *)((char *)b need); rem-size (raw - need) | BLOCK_FREE; rem-prev_size need; rem-next free_list; rem-prev NULL; if (free_list) free_list-prev rem; free_list rem; b-size need; } b-size ~BLOCK_FREE; block_t *nxt (block_t *)((char *)b (b-size ~BLOCK_FREE)); if (nxt heap_end) nxt-prev_size b-size; }find_fit返回第一个size need的块。need必须是已经对齐并包含header的总块大小。extend_heap直接调用sbrk拿新内存放进空闲链表。有一个特殊情况值得留神如果sbrk返回的地址恰好等于旧heap_end说明新内存与旧堆是连续的这时应该尝试与最后一个空闲块合并示例代码里用注释标出实际实现建议合并否则会留下一个永远无法利用的边界洞。split_and_take处理切分剩余部分若还够一个最小块就切出来放回空闲链表不够就整块给出宁可给大了也不产生垃圾碎片。判断条件raw - need MIN_BLOCK_SIZE是核心如果去掉这个约束剩余8字节的空闲块既挂不进链表又会在下次查找时被误用最终破坏堆结构。void *my_malloc(size_t bytes) { if (bytes 0) return NULL; if (!free_list) init_heap(); if (!free_list) return NULL; size_t need ALIGN16(ALIGN16(bytes) HEADER_SIZE); if (need MIN_BLOCK_SIZE) need MIN_BLOCK_SIZE; block_t *b find_fit(need); if (!b) { b extend_heap(need); if (!b) return NULL; } split_and_take(b, need); return (void *)(b 1); }need计算必须先对用户请求对齐再加header并再次对齐这样返回的b1天然满足16字节对齐。heap_end作为全局哨兵在split时用来判断右边是否还有合法邻居避免指针越过堆边界。4.3 free与合并向前合并、向后合并、头插空闲链表free的难点不在释放本身而在合并。如果一个块左右邻居都是空闲的不合并会让大请求在碎片堆里永远失败。合并分三种情况只向左、只向右、左右都合并。void my_free(void *ptr) { if (!ptr) return; block_t *b (block_t *)ptr - 1; block_t *right (block_t *)((char *)b (b-size ~BLOCK_FREE)); block_t *left (block_t *)((char *)b - (b-prev_size ~BLOCK_FREE)); // 向左合并 if ((b-prev_size BLOCK_FREE) left b) { left-size (left-size ~BLOCK_FREE) (b-size ~BLOCK_FREE); b left; } // 向右合并 if (right heap_end (right-size BLOCK_FREE)) { b-size (b-size ~BLOCK_FREE) (right-size ~BLOCK_FREE); unlink(right); } b-size | BLOCK_FREE; b-next free_list; b-prev NULL; if (free_list) free_list-prev b; free_list b; block_t *nxt (block_t *)((char *)b (b-size ~BLOCK_FREE)); if (nxt heap_end) nxt-prev_size b-size | BLOCK_FREE; }left的计算依赖于prev_size长久维护每个块在分配和释放时都会更新右邻居的prev_size因此free时可以快速算出左邻居地址。向右合并前必须检查right heap_end否则最后一个块没有右邻居解引用会读到堆外的数据。合并完成后再写入右邻居的prev_size保证后续操作能继续向前合并。这段逻辑里最容易出错的是“先改left-size再改b指针”的顺序。如果先改b-sizeleft的合并结果会丢失。我通常用一个临时变量记录原始size再把合并后的值一次性写回。4.4 一个最小可用的main验证把以上函数组合起来用一个简单的main做基本功能验证确认malloc/free能跑通链表链路。#include string.h #include stdio.h int main(void) { char *p1 (char *)my_malloc(100); char *p2 (char *)my_malloc(200); strcpy(p1, hello malloc); strcpy(p2, world); printf(%s %s\n, p1, p2); my_free(p1); my_free(p2); char *p3 (char *)my_malloc(50); strcpy(p3, reuse); printf(%s\n, p3); my_free(p3); return 0; }这段程序覆盖了一条完整链路连续分配两块、释放两块、再分配一块。如果合并逻辑正确第三次my_malloc(50)应该能复用前两次释放后合并出的大块而不是再次触发sbrk。运行后可以通过打印free_list-size观察块大小变化确认合并是否发生。5. 避坑排查实现malloc时踩过的5类典型错误5.1 指针偏移算错free(ptr)直接段错误现象my_free(p)一调用就崩溃gdb回溯显示在my_free里访问(block_t *)ptr - 1时Segmentation Fault。原因用户指针和block指针之间的偏移计算不对。如果header是32字节ptr - 1在指针算术中实际偏移了sizeof(block_t)而非32字节。当编译器给block_t加了Paddingsizeof(block_t)可能大于32导致ptr - 1落在错误位置。解决强制用#define HEADER_SIZE ALIGN16(sizeof(block_t))统一偏移量并始终用(block_t *)((char *)ptr - HEADER_SIZE)计算块头而不是ptr - 1。从那以后我每次free之前都打印块头地址跟分配时的返回地址对比一遍再放行。5.2 16字节对齐不达标SSE指令跑起来就崩现象代码在x86-64上编译运行时偶发非法指令错误且崩溃位置集中在浮点或者向量运算附近。原因返回指针没有对齐到16字节。很多简化版实现只让header按8字节对齐忽略了对齐到16字节的硬要求。AVX指令读取未对齐地址直接触发#GP异常由操作系统转为SIGILL。解决在my_malloc返回值前加assert(((uintptr_t)p 15) 0)。如果失败多半是need计算时少做了一次16字节对齐。正确的做法是ALIGN16(ALIGN16(bytes) HEADER_SIZE)保证块大小和起点都是16的倍数。调试时用gdb的watchpoint监视返回指针可以快速定位是哪次分配产生了未对齐地址。5.3 合并方向判断失误左右邻居认错现象free后再次malloc申请一个较大的块却失败但空闲链表明明有足够的连续空间。原因合并逻辑把右邻居当成了左邻居。prev_size在没有维护好的情况下指向了一个已分配的块导致free时把错误的块合并进来或者跳过真正空闲的邻居。解决在free入口先打印b-prev_size、b-size手动算一遍左右邻居地址和空闲链表里的节点比对。我修复这类问题的方法是用left b作为前置条件严格判断左邻居是否合法同时要求right heap_end两处都成立才允许合并。这类bug不会稳定复现常常是分配若干次后才出现必须靠打印和断言缩小范围。5.4 first fit死循环链表成环现象程序运行到某个时刻CPU占用100%find_fit一直不返回。原因unlink时没有同时修复前驱节点。比如链表A-B-C删除B时只改了A-next C忘了C-prev A后续另一个节点free后头插C-prev仍指向BB又指回C形成环。find_fit从此无限遍历。解决unlink里同时更新前后两个节点并在调试版里加遍历计数器超过链表长度就打印链表节点地址。我后来每次free都顺手校验free_list的prev必须为NULL每个节点的next/prev必须互相指向对方。5.5 线程安全多线程同时malloc会串链现象两个线程同时my_malloc返回的指针偶尔相同或者free后链表结构错乱。原因free_list是全局变量没有加锁。线程A执行到find_fit时线程B已经unlink了当前节点A拿到一个已被移除的块写坏堆结构。解决最小做法是在my_malloc和my_free入口加一把互斥锁。性能敏感时可以拆成per-thread arena或者用原子CAS做无锁链表那是另一个层次的话题。初版分配器先把正确性放在第一位我一般用pthread_mutex直接包住整个函数体测试通过后再考虑优化锁粒度。6. 验证与细化随机压测脚本和两种必看的调试技巧写完分配器不能只跑hello world那只能证明“能走通”证明不了“没写坏内存”。我的一贯做法是写一个随机读写程序让它长时间运行用断言和memset双重校验越界与对齐。#include assert.h #include stdlib.h #include stdio.h #include string.h void *ptrs[4096]; int main(void) { for (int i 0; i 200000; i) { int idx rand() % 4096; if (ptrs[idx] ! NULL) { my_free(ptrs[idx]); ptrs[idx] NULL; } else { size_t n (rand() % 2048) 1; void *p my_malloc(n); if (p) { assert(((uintptr_t)p 15) 0); memset(p, 0x5A, n); // 写满整个请求区域 ptrs[idx] p; } } } for (int i 0; i 4096; i) { if (ptrs[i]) my_free(ptrs[i]); } printf(stress pass\n); return 0; }随机压测的价值在于每次写入都覆盖用户请求的完整区域如果header被越界写坏后续malloc/free很可能崩在一个莫名其妙的位置。断言则保证对齐不达标时立刻暴露。运行环境加上-fsanitizeaddress还能把越界读写直接变成可读的报错。我自己习惯先不加sanitizer跑一遍确认基本逻辑稳定再加sanitizer查边界这样两步分开问题定位更快。另一个实用技巧是观察sbrk的涨幅在my_malloc里打印每次sbrk前后的断点差值如果压测结束后断点持续增长说明合并没生效堆只扩不收。这个数字比任何理论分析都直观。从那以后我每次实现分配器都会强制走一遍随机压测加边界检测再谈优化。希望帮到你。本文还有配套的精品资源点击获取