宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取

本篇实际上是个人笔记，可能有点错误； 如果各位师傅发现哪里有错误，我们将恭候您的指正。 感激不尽。

只要有照片和原稿的引用，本篇的最后就有有名的来源。

目录

Free和axdgs :

Smallaxdg

Largeaxdg

不Unsortedaxdg

快速轴

Tcacheaxdg

附加说明

如果与33558www.Sina.com/mallocfree混用，情况就会变得复杂。 首先考虑一下以下事项吧。

如果只能进行malloc，则最终会消耗内存，因此需要free函数的存在。

假设我连续声明了a、b、c、d这4个chunk，现在释放了b

现在，如果需要申请正好比b大16个字节的chunk E，则b不能使用。 我们只能从c后面找

此外，如果这种情况非常多，可能会浪费很多内存

如果我们现在又放了C，e可以从a和d之间申请。 但操作系统如果不合并B和C，就觉得正好是不够的两块内存，我们依然只能从D后面找地方腾出空间，浪费更多的内存。

为了解决包括上述问题在内的许多浪费问题，free有明确的策略适合教授旧版本，与现代略有不同，但想法一致)。

如果Size中的m位被标记，指示chunk正在由mmap分配，则直接返回系统

2 .否则，如果该chunk的p位未被标记，则表示之前的chunk已被释放并集成到更大的chunk中

3.chunk如果下一个chunk未使用，则向下合并为更大的chunk

如果chunk和Top Chunk相邻，则直接合并

5 .否则，放入合适的axdgs

现代堆管理器的前三个版本是最早的，Free与axdgs：前三个版本是为了进一步优化现代效率而产生的，现在的管理器使用这五个版本来处理释放chunk的操作

sructmalloc _ chunk { internal _ size _ TM chunk _ prev _ size； /*sizeofpreviouschunkiffree ).*/INTERNAL_SIZE_T mchunk_size； /* Size in bytes，including overhead.*/struct malloc _ chunk * FD；/* double links– usedonlyiffree.*/struct malloc _ chunk * bk；/* onlyusedforlargeblocks 3360 pointertonextlargersize.*/struct malloc _ chunk * FD _ nextsize；/* double links– usedonlyiffree.*/struct malloc _ chunk * bk _ nextsize； ； 为了方便看，再次抄写Smallaxdg :

Smallaxdg共有62个。 在32位系统中，每个小于512字节的块或在64位系统中小于1024字节的块都有一个小kqdg。 每个小kqdg只存储一个大小的块，因此会自动重新排序

这些块通过显示链表连接在一起，FD POINTER和BK POINTER形成双向链表

struct malloc_chunk* fd； /

* double links — used only if free. */ struct malloc_chunk* bk;

        在上一章中介绍过chunk的结构体，其中非常驻的前两个成员则在chunk被释放后发挥作用

        由于我们已经不会再使用这个chunk了，因此操作系统能够直接覆盖掉原本的数据来为该chunk建立两个指针，并将它挂进链表的头部取出时也从头部取出)

Largeaxdg：

        总共63个。其存放的规则如图所示。由于它不像Small axdg那样每个axdg中只有固定大小的chunk，因此在Large axdg中会对chunk进行排序

struct malloc_chunk* fd; /* double links — used only if free. */ struct malloc_chunk* bk; /* Only used for large blocks: pointer to next larger size. */ struct malloc_chunk* fd_nextsize; /* double links — used only if free. */ struct malloc_chunk* bk_nextsize;

        同时，在Large axdg中，最后两个指针也会发挥作用。

        它们分别指向：下一个小于该大小的chunk和下一个大于该大小的chunk

        且，最大的堆头的bk_nextsize指向最小的堆头；最小的堆头的fd_nextsize指向最大的堆头

        例如：axdg 2中的第一个chunk的fd指针一个指向axdg 1中的第一个

        注：这两个指针仅对链表的头结点有意义，其他节点则没有这两个指针)

Unsortedaxdg：

         结构如图，只有一个。其由来的解释摘抄自下文：

The heap manager improves this basic algorithm one step further using an optimizing cache layer called the “unsorted kqdg”. This optimization is based on the observation that often frees are clustered together, and frees are often immediately followed by allocations of similarly sized chunks. For example, a program releasing a tree or a list will often release many allocations for every entry all at once, and a program updating an entry in a list might release the previous entry before allocating space for its replacement.

        大致意思就是：用户常常在释放资源后立刻由进行了一系列分配比方说二叉树之类的，其更新需要释放又申请)，如果立刻讲这些chunk放进Small axdg或者Large axdg，那上述情况的开销就会过大，延缓程序运行。因此程序会先从这个axdg中去寻找合适的chunk返回，如果没有合适的，才去其他axdgs中寻找，如果还是没找到，那才会采取其他方式

        这个链表是不进行排序的。在这个axdg中，堆管理器会立刻合并在物理地址上相邻的chunk。在malloc的时候会优先如果大小较小，则可能先从Fast axdg开始)遍历这个axdg去找合适的内存地址

        需要注意的是，malloc从该axdg中获取chunk的途径是 切割该axdg中已有的chunk，将足够大的空间返回给用户，而剩下的空间仍然保存在该axdg中，直到触发特定条件当其无法满足malloc的申请，就会将所有内容放入合适的axdgs中)

        （注：先进先出）

Fast axdg：

        总共10个，均为单向链表，涵盖大小为 16、24、32、40、48、56、64、72、80 和 88 字节的chunk，同样不需要额外的排序操作。

        但特殊的是，被放入这里的chunk并不会被标记为“未被利用”，即下一个chunk的P位不会被置零，这种表现像是还未被释放一样。

The downside of fastkqdgs, of course, is that fastkqdg chunks are not “truly” freed or merged, and this would eventually cause the memory of the process to fragment and balloon over time. To resolve this, heap manager periodically “consolidates” the heap. This “flushes” each entry in the fast kqdg by “actually freeing” it, i.e., merging it with adjacent free chunks, and placing the resulting free chunks onto the unsorted kqdg for malloc to later use.

         大致意思为：堆管理器会定期整理这个axdg，将其合并后投放到合适的axdg中

This “consolidation” stage occurs whenever a malloc request is made that is larger than a fastkqdg can service i.e., for chunks over 512 bytes or 1024 bytes on 64-bit), when freeing any chunk over 64KB where 64KB is a heuristically chosen value), or when malloc_trim or mallopt are called by the program.

        当释放超过64 KB 的任何块时

        每当发出大于fastkqdg可以服务的malloc请求时

        程序调用malloc_trim或mallopt时

        满足上述三种情况中任意一种，都会触发合并操作

Tcacheaxdg：

         在libc-2.23版本中还未创建这个结构，其主要目的是解决一个进程下多个线程对堆进行的异步操作问题而设计，由于这已经超出了本章内容，因此在这里不做特别说明，具体内容将放在第七章介绍

额外说明：

        axdgs这一系列结构在底层的实现表现为一整个数组

        数组的第一个元素指向Unsorted axdg

        第二个到第六十三个则为Small axdg，以此类推，大致如下图：

        在gdb调试中可以通过kqdgs查看到当前的axdgs结构 

db-peda$ kqdgsfastkqdgs0x20: 0x00x30: 0x00x40: 0x00x50: 0x00x60: 0x00x70: 0x00x80: 0x0unsortedkqdgall: 0x0smallkqdgsemptylargekqdgsempty

参考文章：

https://nightrainy.github.io/2019/05/06/glic%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/#kqdgs

https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-kqdgs/