浅析malloc&free工作原理

平时我们在码程序的时候，经常会遇到要动态申请内存，申请之后当然要记得释放，我们用的最多的当然就是malloc(申请)/free(释放)，现在来简单分析一下其基本工作原理：

图1 到 图8 给出了 malloc & free 的基于链表简单实现

图1

图2

图3

图4

图5

图6

图7

图8

 

图中白色背景的框表示malloc管理的空闲内存块，深灰色背景的框不归malloc管，可能是已分配给用户的内存块，也可能是不属于当前进程；break之上的地址不属于当前进程，需要通过brk系统调用向内核申请。每个内存块都有一个头节点，里面有一个指针字段和一个长度字段，指针字段把所有空闲块的头节点串在一起，组成一个环形链表，长度字段记录着头节点和后面的内存块加起来一共有多长，以8字节为单位(也就是以头节点的长度为单位)：

图1：一开始堆空间由一个空闲块组成，长度为7*8=56字节，除头节点之外的长度为48字节；

图2：调用malloc分配8字节，要在这个空闲快的末尾截出16个字节，其中新的节点占用8个字节，另外8个字节给用户使用，注意返回的指针p1指向头节点后面的内存块；

图3: 又调用malloc分配16个字节，又在空闲块的末尾截出24个字节，步骤和上一步类似；

图4：调用free释放p1所指向的内存块，内存块(包括头节点在内)归还给了malloc，现在malloc管理者两块不连续的内存，用环形链表串起来。注意这时p1成了野指针，指向不属于用户的内存，p1所指向的内存地址在break之下，是属于当前进程的，所以访问p1时不会出现段错误，但在访问p1时这段内存可能已经被malloc再次分配出去了，可能会读到意外改写数据。另外注意，此时如果通过p2向右写越界，有可能覆盖右边的头节点，从而破坏malloc管理的环形链表，malloc就无法从一个空闲块的指针字段找到下一个空闲块了，找到哪去都不一定，全乱套了。

图5：调用malloc分配16字节，现在虽然有两个空闲块，各有8个字节可分配，但是这两块不连续，malloc只好通过brk系统调用抬高break，获得新的内存空间。每次调用sbrk函数时申请1024*8=8192个字节，在linux系统上sbrk函数也是通过brk实现的，这里为了画图方便，我们假设每次调用sbrk申请32个字节，建立一个新的空闲块；

图6：新申请的空闲块和前一个空闲块连续，因此可以合并成一个。在能合并时要尽量合并，以免空闲块越来越小，无法满足大的分配请求；

图7：在合并后的这个空闲块末尾截出24个字节，新的头结点占8字节，另外16个字节返回给用户使用；

图8：调用free(p3)释放这个内存块，由于它和前一个空闲块连续，又重新合并成一个空闲块。注意，break只能抬高而不能降低，从内核申请到的内存以后都归malloc管了，即使调用free也不会还给内核。



//感觉这篇文章说的比较好