图文并茂-深度剖析C语言中动态内存分配的幕后实现（2）

上一篇文章介绍了C语言中动态内存分配的基础知识，这篇文章将着重介绍其幕后的实现思路和方法。

对于每一个内存块，都需要存储其大小和是否已被分配的状态。而为了存储这些信息，需要分配2个字（8个byte）的大小，是不是觉得挺浪费的内存的？我也这么觉得。

浪费内存

惯用技巧

如果内存块的起始地址是对齐的，那么一些低位的地址bit位必然一直是0。例如，2字节对齐，那么bit0必然一直为0，4字节对齐的话bit0和bit1一直为0。因此，这些低bit位可以用来存储内存块的状态，而不是一直为0。当需要读内存块的大小时，必须将对应的低bit位用掩码与掉。

已分配或空闲内存块的格式

隐形链表的示例

堆中内存块是双字对齐的，在32位系统中，一个字是4字节，双字就是8字节对齐。下图以32位系统为基础，给出了一个内存块的链表示例。

隐形链表的详细示例

接下来，我们逐块进行分析：

1. 8/0，8表示该内存块大小为8字节，0表示该块为空闲态。那么实际申请的大小为4字节，因为自身的头占了4字节。由于申请到的内存地址需要2字对齐，因此头之前1个字的内存并未被使用。
2. 16/1，16表示该内存块的大小为16字节，1表示已被分配。由于前一个内存块的结束位置正好是单数字地址位，加上一个字的头，分配到的地址正好是双字对齐。那么，这两个块之间不需要进行地址对齐，可以看到没有内存浪费。
3. 32/0，32表示该内存块的大小为32字节，0表示该块为空闲块。由于上一个块的结束位置是双数字地址位，而头只占一个字，因此需要在前面补齐一个字。可以看到在头之前有1个字的内存用于对齐双字，而浪费掉了。后面的两个块，以此类推。

一个有趣的细节

最后一个块比较特殊，分配了0个字节，而且是已分配态。这意味着，虽然用户应用程序并没有得到可用的内存块，但申请0个字节也是占用了内存的。

选择第一个能满足大小要求的块

从表头开始搜索，然后选择第一个大小满足要求的块，示例代码如下。

p = start; while ( (p < end) && ( (*p & 1) || (*p <= len )) ) { p = p (*p & -2); \\ 到下一个块 }

选择下一个合适的块

跟上一个方法类似，但是搜索的起始地址是上一次搜索完成的地方。该方法避免了重复扫描之前被扫描过的块，经常比第一种方法快。但是，该方法可能会让碎片化更严重。

选择最适合的块

搜索链表，选择最适合的空闲块。最适合的意思就是减去需要的空间，剩余空间最小的块，这样可以让碎片化程度最低，但是比第一种方法要慢很多。

分配过程其实就是分裂找到的空闲块的过程，因为需要的空间可能小于空闲块的空间。为了避免浪费，需要将该空闲块进行分裂，如下图所示。

分裂找到空闲块等于添加一个新的内存块

下面的代码是分配内存代码，相当于添加了一个新的内存块，并修改了原来内存块的大小及状态。

void addblock(ptr p, int len) { int newsize = ((len 1) >> 1) << 1; // 对齐到偶数 int oldsize = *p & -2; //mask掉低位的状态bit *p = newsize | 1; //设置新的大小，并更改状态位为已分配 if (newsize < oldsize) *(p newsize) = oldsize - newsize; //将剩余的大小设置到新增块的头中 }释放一个内存块的过程

一个最简单的实现就是只需要清除状态位标志。

void free_block(ptr p) { *p = *p & -2 }

但是，该方法会导致出现假内存碎片，如下图所示。

假内存碎片的产生

因此，在释放内存后，如果邻近的内存块是空闲的，就需要与其进行合并，实现原理及代码如下。

合并临近空闲块的过程

void free_block(ptr p) { *p = *p & -2; //清除状态bit位 next = p *p; //找到下一个块 if ((*next & 1) == 0) *p = *p *next; //如果下一个块未被分配则将其大小添加到当前块中 }

但是问题来了，上面的方法只能合并前向的空闲块，那么后向的如何处理呢？下篇文章，将给大家带来答案。

如果错过了前一篇文章，可以通过下面链接进行了解，以免漏掉一些基础概念。

在后续《深度剖析C语言中动态内存分配的幕后实现（3）》一文中，将详细介绍如何实现双向空闲块合并，并进行总结，分享个人感悟及如何在工作项目中使用。