C/C++调试---堆数据结构

堆数据结构

因为C/C++语言赋予程序员通过引用和指针来操纵内存对象的最大自由，所以毫不奇怪的是这些程序中的大多数bug都与错误的内存访问有关。

根据错误发生的位置是栈还是堆，内存错误可分为两种：栈错误和堆错误。

栈

栈是分配给给一个独立的控制流(线程)的来纳许内存区域，用于追踪线程的动态调用链。每个函数在进入时会分配一个栈帧，即一个内存块。

主线程(进程创建时的第一个线程)的大小由生成这个进程的shell的栈大小ulimit设置决定的。

堆

堆是程序代码显式创建和释放动态数据对象的内存区域。堆服务于同一进程下的所有线程，它的地址通常紧接在可执行文件的全局数据段之后。

全局数据

存放在data节(初始化的数据)或者.bss节(未初始化的数据)。生命周期与包含它的模块相同。

内存管理器

内存管理器记录着每个堆内存块的大小和状态，即内存块是空闲的还是在使用中。这个简要信息常常可以帮助我们缩小一个棘手问题的范围，并提供强有力的证据来证明或者证伪一个理论。

ptmalloc

通过两个关键的数据结构来管理堆内存块：边界标签和盒子。它们被声明在malloc/malloc.c中，源代码可以在GNU C运行库glibc里面找到。

边界标签

边界标签也称块标签，在ptmalloc中叫做malloc_chunk，每个内存块都有，用来记录当前内存块的大小和状态。


上图灰色框的是边界标签。

size大小字段放在内存块的开始位置，它最低的两个比特分别表示当前块和前一个内存块是空闲的还是在使用中。
使用中的块和空闲块的边界标签的内容和大小是不一样的。正在使用中的块标签只使用了大小字段，但是空闲的内存块的标签使用了结构体malloc_chunk所有的4个字段。

prev-size字段是放置在空闲内存块末尾的另一个大小字段，目的是让内存管理器可以由地址低端向上合并地址高端的空闲块。

fd和bk，指向其他空闲块，ptmalloc会使用它们来构建空闲块的双链表。当应用程序请求一个新的内存块时，ptmalloc会搜索这个链表来寻找最合适的空闲块。

因为标签数据结构的存在，一个ptmalloc管理的最小内存块不会小于结构体malloc_chunk的大小，对于64位应用程序来说，是32字节。

被分配出去的内存块的实际空间消耗仅仅只有8字节，也就是size字段使用的空间。不同于空闲块，使用中的内存块不需要双链表的下一个和前一个指针，同时它把末尾的紧邻块的prev-size字段给占用了，因为当它在使用的时候，我们不需要合并这个块。

盒子

所有的空闲块被收集到盒子bins里，这些盒子被实现为双向链表数组，并按块大小进行索引。这个数组被声明为ptmalloc管理堆的顶层元数据结构体malloc_state的数据成员：


盒子中空闲块的大小随着数组索引的增大而增大。盒子之间的间距是仔细选择过的。因为大部分用户请求都是小块的内存，从24字节到512字节的盒子都是精确的大小，以8字节隔开。这些盒子被叫作小盒子(Small Bin)。剩下的盒子以大小的对数间隔。

上图显示24字节大小的盒子有3个空闲块，40字节大小的盒子有1个空闲块，576字节大小的盒子有两个空闲块，大小在512字节和576字节之间。盒子的空闲块大小大于512字节的，按大小排好序并用最好匹配方法分配。

• 请求内存

当接收到用户请求时，分配器首先检查并调整请求块的大小。如果有必要，取整到不小于最小块的大小（64位程序是32字节），另外为了满足对齐要求可能会增加一些填充。如果调整过的请求块大小落在精确大小的小盒子（24～512字节）上，那么计算得到对应的数组索引并检查其中的空闲链表。
如果链表具有空闲块，那么会移除链表头部空闲块并返回给用户。因为链表所有的空闲块都是同样大小，所以没有必要遍历链表。
如果链表是空的，那么下一个比较大的缓存着的盒子就会被检查。如果有一个空闲块大于请求的大小，那么它会被分割成两部分：一部分满足请求并返回给用户；另外一部分叫作剩余块，会放到相应盒子中以备将来使用。
如果下一个盒子没有空闲块，分配器会继续搜索更大的盒子，直到合适的空闲块被找到。
如果所有的盒子都被用光并且没有可以满足申请大小的候选内存块，ptmalloc会转向系统的VMM（虚拟机管理器）来获取一大块内存，并分割成两个内存块：一个返回给用户，一个被存入相应的盒子里。

• 释放内存

当内存块被用户释放时，分配器从镶嵌的块标签中获取它的大小。如果当前内存块的前面和后面也是空闲的，ptmalloc会试图合并它们，此时前一个和后一个空闲块会从它们相应的双链表中移除。合并后的空闲块会被放到未排序的链表列表中。

补充

ptmalloc还采用了其他一些有趣的技术来提高性能和减少内存消耗。

• 快速盒子(Fast Bin)
  保存在快速盒子中的最大空闲块更小，默认值是80字节。如果用户释放的内存块的大小小于快速盒子的最大内存块的大小，它会被直接放入对应的快速盒子里，且不更改它的块标签，这一点非常重要。即使可以合并，它也不会跟周围的空闲块合并。当新的请求到来时，在检查常规的盒子前，会先检查快速盒子。如果有合适的，这个缓存的内存块会立即返回。同样的它的标签不需要被调整。在这种情况下，请求可以尽可能快地被满足。这个算法在经常需要构建和析构小对象的C++程序中工作得很好。为了避免碎片化，快速盒子的空闲块在一些条件下会被合并。如果一个请求大于小盒子的最大块的大小或者没有空闲的块可以满足小的请求，在快速盒子中的内存块就会被处理，也就是先与邻近的空闲块合并然后放到对应的常规盒子里。

• 未排序chunks
  这个盒子里包含了暂时的最近内存分割带来的剩余部分或者是用户刚刚释放的空闲块。如果快速盒子和小盒子都不能够满足一个请求，那么在未排序的chunks里的空闲块会一个接一个地被考虑。如果找到一个匹配的空闲块，那么这个块会被返回给用户；否则，它会被放入常规盒子里。当搜索遍历完所有空闲块后，它们会重新分配到合适的盒子里。
  这种对最近空闲块的处理是为了提高内存的局部性和性能，因为程序往往会申请一组相关的内存块，比如一个数组的所有单元结构体，分配器采用上述考虑提高了数组内存地址顺序排列的可能性。

• mmap
  如果用户请求的大小超出了一个可调整的阈值（默认是128KB），并且ptmalloc无法找到一个足够大的缓存内存块来满足该请求，那么它会从VMM分配一块匿名的mmaped内存并直接返回给用户。为了减少内存碎片和程序占用的系统内存，当这样的内存块被用户释放时，ptmalloc不会缓存它，而是直接返回给VMM。这在很大程度上保证了进程在运行了很长时间后，还可以保持低内存占用。

tmalloc

TCMalloc(Thread-Caching Malloc)是一种高性能的内存管理器，由Google开发。它是一个优化过的内存分配器，旨在为C和C++应用程序提供更快、更高效的内存分配和释放。

利用堆元数据

堆元数据告诉我们应用程序数据对象的基本状态，它可以为查找内存损坏的原因提供重要线索。

在ptmalloc中，每个内存块之前都有一个名为malloc_chunk的小数据结构，即块标签。如果用户输入一个由函数malloc返回的有效地址，则内存块的标签正好在这个地址的前面。块标签的size字段说明当前块的大小。为了知道当前块是在使用中还是空闲的，需要计算下一个块的地址。当前块的状态编码在下一个块的size字段中。

https://github.com/yanqi27
参考： 高效C/C++调试