深入理解Glibc堆的实现（下）

在 上一篇文章 中，我们已经看到，底层的malloc通过分配内存块来处理内存分配请求。每个块不仅存储 程序员 将与之交互的malloc返回的“用户数据”区域，还存储与该块关联的元数据。

我们不仅了解了堆管理器的基本块分配策略是如何工作的，还了解了在没有可用来服务请求的已释放块时，如何从堆的顶部创建新的块。

在这篇文章中，我想谈谈这种块回收策略是如何工作的，即如何将分配发送回free get并最终回收以服务未来的malloc请求。许多堆利用技术都依赖于利用这些内部机制。现在，就让我们看看当堆正常运行时，这些块是如何被回收的？

回收过程

当完成来自malloc的分配(或像calloc这样与malloc兼容的分配)时，程序员通过将其发送给free将其释放回堆管理器。C标准将free（NULL）定义为什么都不做，但对于其他free的调用，堆管理器的第一个工作是将指针解析回其相应的块。堆管理器通过从发送给free的指针中减去块元数据的大小来完成此操作。

这种从指针到块的转换之所以有效，是因为用户数据区域位于块内。但是，当然，只有当发送给free的指针确实来自malloc的活动分配时，它才是有效的。如果将其他指针被发送给free，则堆管理器可能会释放或回收一个无效块，从而导致内存损坏问题，进而导致进程崩溃，甚至可能让黑客远程接管进程。

出于这个原因，在尝试处理释放的指针之前，free首先进行一些基本的完整性检查，以查看释放的指针是否明显无效。如果检查失败，程序将中止。检查包括:

1.检查分配是否对齐到8字节或64位上的16字节，因为malloc确保所有分配都对齐。

2.检查块的大小字段是不是太小、太大或没有对齐的大小，甚至会重叠进程的地址空间。

3.检查块是否位于arena的边界内；

4.通过检查位于下一个块开始的元数据中对应的“P”位，来检查块是否已经标记为空闲。

上面所述的堆管理器的检查并不全面，攻击者控制的数据指针可能会绕过这些完整性检查，在进程中触发并损坏内存。

空闲的块元数据

上一篇文章中，我还介绍了活动块如何将元数据与程序员使用的“用户数据”区域一起存储。这些活动分配存储“块大小”，并在其元数据中存储称为“A”，“M”和“P”的三个位。这些位有助于堆管理器记住块是否从非主arena分配的，是否通过mmap在堆外分配，以及前面的块是否是空闲的。

空闲的块也存储元数据，与活动分配类似，它们存储“块大小”、“A”和“P”字段，但是它们不使用“M”字段，因为mmap-ed块总是在空闲期间被munmap-ed，而不是被转换为可回收的空闲块。

空闲块还使用一种称为“ 边界标记（boundary tags） ”的技术在用户数据区域之后存储信息。这些边界标记在块之前和之后携带大小信息。这允许从任何已知块开始，以任何方向遍历块，从而能够非常快速地合并相邻的空闲块。

这些释放的块存储在作为链表操作的相应“空闲箱”中。这要求每个空闲块还存储指向其他块的指针，由于释放的块中的“用户数据”可供堆管理器免费使用，因此堆管理器将释放的块中的“用户数据”区域重新用作此附加元数据所在的位置。

使用bin回收内存

在内部，堆管理器需要跟踪已释放的块，以便malloc可以在分配请求期间重用它们。在一个简单的实现中，堆管理器可以通过简单地将所有释放的块存储在一个巨大的链表中来实现这一点。这是可行的，但这会使malloc变慢。由于malloc是大多数程序的高利用率组件，因此这种速度会对系统上运行的程序的总体性能产生巨大的影响。

为了提高性能，堆管理器会管理一系列名为“bin”的列表，这些列表的设计目的是最大化分配和释放的速度。

每个线程有5种类型的bin:62个小bin、63个大bin、1个未排序bin、10个快速bin和64个tcachebin。小的、大的和未 排序 的bin是最古老的bin类型，用于实现堆的基本回收策略。快速bin和tcache bin是分层优化的结果。

令人困惑的是，小的、大的和未排序的bin都位于堆管理器源代码中的 同一个数组中 。索引0未使用，1为未排序的bin，bin 2-64为小bin，bin65-127为大bin。

块回收的基本策略

在进行tcache和快速bin优化之前，让我们先看看堆管理器使用的基本回收策略。

回忆一下，free的基本算法如下:

1.如果块在元数据中设置了M位，则分配是在堆外分配的，应该进行munmap；

2.否则，如果此块之前的块是空闲的，则向后合并该块以创建更大的空闲块；

3.类似地，如果这个块之后的块是空闲的，那么这个块将向前合并，以创建一个更大的空闲块。

4.如果这个可能更大的块与堆的“顶部”相邻，那么整个块将被吸收到堆的末尾，而不是存储在“bin”中。

5.否则，块将被标记为空闲，并放置在适当的bin中。

小bin（SMALL BIN）

小bin是最容易理解的基本bin，它共有62个，每个小bin都存储着大小相同的块。在32位系统上，每个小于512字节的块(或者在64位系统上小于1024字节)都有一个对应的小bin。由于每个小bin只存储一种大小的块，所以它们是自动排序的，所以插入和删除这些列表中的条目非常快。

大bin（ LARGE BIN ）

小bin策略非常好，但是我们不能为每个可能的块都设置一个bin。对于512字节以上的块(64位上是1024字节)，堆管理器使用“大bin”。

这63个“大bin”中的每一个都与小bin的操作方式基本相同，但它们不是存储固定大小的块，而是存储在大小范围内的块。每个大bin的大小范围被设计成既不与小bin的块大小重叠，也不与其他大bin的范围重叠。

必须手动对bin中的插入进行排序，并且需要遍历列表中的分配。这使得大bin自然比小bin慢。然而，在大多数程序中，使用大bin的频率较低。这是因为程序倾向于分配并因此释放小的分配，其平均速率远远高于大的分配。出于同样的原因，最小的“大bin”只包含从512字节到576字节的64字节范围，最大的bin中也只有1MB多已释放的块。

未分类的bin（UNSORTED BIN）

堆管理器使用名为“未排序的bin”的优化缓存层进一步改进了这个基本算法。例如，释放树或列表的程序通常会同时为每个条目释放许多分配，而更新列表中的一个条目的程序可能会在为其替换分配空间之前释放前一个条目。

在这些情况下，在将结果较大的块放入正确的bin之前，合并这些已释放的块可以避免一些性能消耗，加快整个过程。

堆管理器引入未排序的bin来利用这些结果。堆管理器不会立即将新释放的块放到正确的bin中，而是将其与邻居合并，并将其转储到一个普通的未排序链表中。在malloc期间，将检查未排序的bin上的每一项，以确定它是否“适合”该请求。。如果是这样，malloc可以立即使用它。如果没有，则malloc将块放入相应的小bin或大bin中。

快速bin（FAST BIN）

快速bin则是进一步的优化，这些bin本质上还是保持了一个“快速周转队列”上最近释放的小bin，其目的就是保持块是活动的，而不是将块与其邻居合并。以便在块释放后不久，如果malloc请求该块大小，它可以立即重新使用。

和小bin一样，每个快速bin只负责一个固定的块大小。有10个这样的快速bin，包括大小为16、24、32、40、48、56、64、72、80和88字节的块以及块元数据。

与它们对应的小bin不同的是，快速bin从不与邻居合并。实际上，堆管理器不会在下一个块的开始处设置“P”位。如果你愿意，你可以从概念上将其看作堆管理器。

和它们的小bin一样，快速bin只包含一个块大小，因此会自动排序，因此插入和删除都非常快。此外，它们也可以存储在单链表中，而不需要存储在双链表中，以便在块合并时从列表中删除它们。

当然，快速bin的缺点是，它不会被真正释放或合并，因为这最终会导致进程的内存无限膨胀。为了解决这个问题，堆管理器定期合并堆。通过刷新快速bin中的每个条目，将其与相邻的空闲块合并，并将生成的空闲块放置到未排序的bin中，供malloc稍后使用。

每当malloc请求大于快速bin所能提供的服务时，即对于64位上超过512字节或1024字节的块，当释放任何超过64KB的块(其中64KB是启发式选择的值)，或者当程序调用malloc_trim或mallopt时，就会发生此合并。

TCACHE bin或每线程CACHE bin

堆管理器用于加速分配的最终优化是每线程缓存或“tcache”分配器。首先让我们来看看tcache试图解决的问题。

给定计算机系统上的每个进程都有一个或多个线程同时运行，拥有多个线程允许一个进程执行多个并发操作。例如，一个高容量的web服务器可能具有多个同时传入的请求，并且web服务器可能在自己的线程上为每个传入的请求提供服务，而不是让每个请求排队等待服务。

给定进程中的每个线程会共享相同的地址空间，也就是说，每个线程可以在内存中看到相同的代码和数据。每个线程都有自己的寄存器和堆栈来存储临时本地变量，但是全局变量和堆之类的资源在所有线程之间共享。

协调对全局资源(比如堆)的访问是一个复杂的主题，如果做错了，可能会导致一个称为“竞态条件”的问题，这会导致难以调试的崩溃，而这些崩溃通常也会被黑客利用。

在本文的示例中，我们假设了一个正在服务于一个线程的web请求试图更新数据库行，而另一个并发web请求试图从同一行读取数据。通常，我们希望确保第二个线程不会在写入的过程中看到该行，因为它被另一个线程覆盖，从而以某种部分或损坏的形式看到该行。数据库通过使读取和写入看起来以原子方式运行来解决此问题：如果两个线程同时尝试访问同一行，则必须在下一个操作开始之前完成一个操作。解决这些竞争条件的一种非常常见的方法是通过使用锁来强制以其他方式同时访问全局资源的请求进入顺序队列。

通常，锁通过一个线程“标记”它在使用之前获取全局资源的所有权，执行其操作后，然后标记该资源不再使用。如果另一个线程出现并想要使用该资源并看到其他一些线程正在使用它，那么该线程将一直等到另一个线程完成。这可确保全局资源一次仅由一个线程使用。但缺点是：这太浪费时间，该过程被称为“锁竞争(Lock Contention)”。

对于许多全局变量，这是可接受的浪费。但是发生锁竞争的话，如果被保护的代码需要完成的工作量越多，那么等待获得锁的线程也数量也变的越来越大。

堆管理器主要通过使用每个线程的arena来解决这个问题，每个线程都有自己的arena，直到达到阈值为止。此外，每个线程的tcache缓存旨在降低锁本身的成本，因为锁指令非常昂贵，最终会占用快速路径中相当大的一部分执行时间。现在，这个特性被添加到glibc 2.26中的malloc内存分配函数中，并在默认情况下启用。

每线程缓存通过为每个线程准备小bin来加快分配速度，这样，当线程请求一个块时，如果线程的tcache上有一个可用的块，那么它就可以为分配提供服务，而不需要等待堆锁（heap lock）。

默认情况下，每个线程有64个单独链接的tcache bin。每个bin最多包含7个大小相同的块，在64位系统上从24到1032字节不等，在32位系统上从12到516字节不等。

块 的分配 如何在TCACHE bin中结束?

当一个块被释放时，堆管理器会查看该块是否适合对应于块大小的tcache bin。与快速bin一样，tcache bin上的块被认为是“正在使用”的，不会与相邻的已释放块合并。

如果用于该块大小的tcache已满或者该块对于tcache bin来说太大，则堆管理器将恢复到我们以前的慢路径策略，即获取堆锁，然后像以前一样处理该块。

相应的tcache分配也非常简单，如果一个块在适当的tcache bin上可用，那么给定一个块的请求，堆将返回该块而不会获得堆锁。如果数据块对于tcache来说太大，我们则采取以前的办法继续。

在我们尝试进行分配的情况下，有一个对应的tcache bin，但是这个bin已经满了，我们执行一个稍微修改过的分配策略。

总结

现在，我们已经充分了解了malloc和free在glibc堆实现中的整个行为，以及算法。让我们回顾一下：

首先，每个分配都作为一个内存块存在，它是对齐的，包含元数据和程序员想要的区域。当程序员从堆中请求内存时，堆管理器首先计算出分配请求对应的块大小，然后按照以下顺序搜索内存:

1.如果大小与tcache bin对应，并且有一个可用的tcache块，那么立即返回。

2.如果请求很大，则通过mmap从堆外分配；

3.否则我们获取arena堆锁，然后执行以下策略:

3.1试试fastbin/smallbin回收策略；

3.2解析所有延迟释放；

3.3默认返回基本的回收策略；

3.4从头创建一个新块；

3.5如果所有操作都失败，则返回NULL。

相应的free策略有:

1.如果指针为NULL，则C标准将行为定义为“不执行任何操作”；

2.否则，通过减去块元数据的大小将指针转换回块；

3.对块执行一些完整性检查，如果完整性检查失败，则中止。

4.如果块适合放在tcache bin中，则将其存储在那里；

5.如果块设置了M位，则通过munmap将其返回给操作系；

6.否则我们将得到arena堆锁；