关注、星标公众号，直达精彩内容
文章来源：技术让梦想更伟大
整理：李肖遥
由于malloc()的源码十分的繁琐，并且会调用OS所提供的API，所以我不在对malloc()的源码进行分析了，而只是会分析malloc()的动作，这就已经足够了。
在前边的文章中已经提及到了，当malloc()分配空间时，并不是要多少就分配多少，而是会额外的加上首部和尾部，其中一些较为简单的部分我会在这里进行解释，而较为重要的部分我会在本文下面的分析中逐步的完善。图片取自侯捷C++内存分配系列教程讲义
这张图片去除掉了上下两块cookie和下边的填补区pad。
浅绿色的fill是调用malloc()时向系统申请的内存，该函数返回时，也会返回这块区域开头的指针。这里申请了0x100 byte的内存.
fill上下两块gap预先被填充为了0xfdfdfdfd，用来分隔客户可以使用的内存区和不可使用的内存区，同时，当这块内存被归还时，编辑器也可以通过下gap的值区判断当前内存块是否被越界使用了。
上gap向上连续的7个内存空间共同组成了debug header，从上向下标号为1-7
首先，在进入程序之前，系统就已经分配出了一个结构去管理内存，我们先来看看这个结构
代码比较难看懂，我这里分析一下。
系统首先会调用__cdecl_heap_init()函数去分配一个堆空间，用在这里分配的堆空间去管理程序中会产生的动态分配内存的请求。而在__cdecl_heap_init()这个函数中，回去创建一个长度为16的类型为HEADER的链表，这个链表的每个节点将在以后的程序中去管理1MB的内存。
我们去看下这个链表的节点的结构：
这里需要重点关注的是两根指针：
这张图对应了上边的关系
在这个图中显示的，pHeapData指向的是虚拟地址空间，没错，现在还是虚拟的，并没有为其分配内存，我们可以将他想象成门牌号的集合。这里只保存了门牌号，但是房子还没有建起来。这里以后将要分配的空间一共是1MB，将被分为32个32KB的内存段。
接下来我们详细去看pRegion所指向的结构，也就是tagRegion；
indGroupUse表示了当前会提供内存的group编号，从0开始
cntRegionSize[64]用64个字节去对应后边group所将会展开链表，当对应链表挂在有内存时，将会变成1.
bitvGroupHi和bitvGroupLo共同构成了一个的byteMap共64个byte(分为32组)，将来用于对应每个group中所挂载的64条双向链表，当对应的位置挂载有内存时，会变成1.
grpHeadList就是32个group，每个group负责32KB
这里的cntEntries代表当前链表中挂载的内存块被切分的次数
listHead对应64对指针，也就是形成了64条链表，用于挂载不同大小的内存块，间隔为16byte，最后一条链表将挂载所有大于等于1K的内存块
编号1就是上边所说的每grop中的那64条双向链表现在只有最后一条双向链表中挂载有内存页。
编号2是这个group所对应的那32K的内存段，将他分为了8份，每份就是4K，将这8个内存页串成链表，由于每一个内存页都大于1K，所以都将挂载在最后一条链表上。
当一切准备好，挂载的对应方式如下图：
编号1是当前header所管理的1MB的空间，将其32等分，每一份的32KB由一个group去负责分配
编号2是一个group所管理的32K的空间，将其分为8个4KB大小的内存页挂载于最后一条链表上
编号3是分割好的内存页链表，他们被串成一个双向链表。
编号4是一个group中的64条链表
下面我们来看每个崭新的内存页的内容
这是一个4K大小的内存页：
当申请一个内存空间时，首先先去符合的链表中寻找，如果链表中没有挂载内存块，就从编号较大的链表中最近的挂有内存块的链表中划分。
最左边原先是一个崭新的内存页(4K = ff0)，然后我们从内存页中划分出0x130 byte的空间：
当这块内存被分配出去之后，原来内存页中的cookie = ff0-130 = ec0，此时仍然大于1KB，所以不用转移挂载的位置。
我们刚刚分配出了0x130的空间，我们先看看这个空间分配出去之后的动作
此时page1中剩余空间为ec0 byte;
当某一次分配时，group0中没有比当前需求大的内存块了，此时就需要开辟另一个group去服务了
此时再分配内存就会从group中去分配了
当多次连续分配之后，出现了一次归还空间的动作
我们来探讨几个问题：
答案很简单，夹杀法：我们知道每一个group对应内存的起始地址和结尾地址，我们只需要去判断被归还的指针中地址的大小是否在这二者之间，就能判断出是否属于当前的group。而去寻找所对应的header的方法也是如此。
这里时malloc和之前讲过的分配器本质上的区别，我们能将收回的内存还给操作系统，具体步骤如下：
这里我们假设还的的1号空间，我们能看到 2、3两个空间的cookie结尾都是0，所以也是空闲的，也就是说这三块连续的空间可以合并。
向下合并：我们首先有一个指向1号空间的指针，他通过cookie可以知道自己有多大，所以下调对应的大小就可以到达2号空间的开头，查看2号空间的cookie可以知道他的大小，也可以知道它是空闲的，所以可以将他们两个合并。
向上合并：我们首先有一个指向1号空间的指针，他向上调整两个int的长度，可以到达3号空间的cookie，通过三号空间的cookie可以知道3号空间的大小，也可以知道3号空间是空闲的，所以就可以将他们两个合并。重复上边两个步骤，我们可以将相连的N块空闲内存全部合并，并计算大小调整连接位置。
这也很简单，我们再每个group都记录了分配出去的次数，每当我们回收的时候，就将这个值-1，所以当它再次为0的时候，就证明这个group的内存全部回收了。
由于有上边的合并机制，所以当一个group的内存全回收之后，他的状态就和最开始时一样，也就是最后一个链表上连接着8个4KB大小的内存块，这时我们就可以将他还给操作系统了。
答案肯定是否定的，因为如果我们全回收一个就还一个，那么当下一次在需要分配时，我们还需要重新分配。所以全回收的group不会立刻被还给系统，而是等待下一个全回收的group出现，就会将前一个group对应的内存free掉。
参考原文链接：https://blog.csdn.net/qq_34269632
‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ END ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧
关注我的微信公众号，回复“加群”按规则加入技术交流群。
点击“阅读原文”查看更多分享，欢迎点分享、收藏、点赞、在看。
