关于如何理解Glibc堆管理器(Ⅱ——Free与Bins)

2024-04-15 05:58
文章标签 理解 free 管理器 glibc bins

本文主要是介绍关于如何理解Glibc堆管理器(Ⅱ——Free与Bins),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本篇实为个人笔记,可能存在些许错误;若各位师傅发现哪里存在错误,还望指正。感激不尽。

若有图片及文稿引用,将在本篇结尾处著名来源。

目录

Free与Bins:

SmallBin

LargeBin

UnsortedBin

Fast Bin

TcacheBin

额外说明


Free与Bins:

        malloc如果一旦和free混用,情况就变得复杂了。我们可以先思考一下下面的问题:

        如果只能malloc的话,那么内存最终必然会被消耗殆尽,因此free函数的存在是必须的。

        假设我连续申明了A,B,C,D四个chunk,并且现在释放掉了B

        倘若我现在需要申请一块刚好比B大16字节的chunk E,那么B就不能使用了,我们只能从C后面去找

        又倘若这种情况非常多,那么就可能会有很多的内存被这样浪费掉了

        如果我们现在又释放掉了C,那么E就能够从A和D之间申请了,但操作系统如果没有将B和C进行合并,那么就会以为是两块刚好不足的内存,我们仍然只能从D后面去找地方开辟空间,就会浪费更多的内存。

        为了解决包括上述问题在内的诸多浪费问题,free有一套明确的策略(适用于教早的版本,与现代稍有出入,但思路是一致的):

1.如果Size中M位被标记,表明chunk由mmap分配,则直接将其归还给系统

2.否则,如果该chunk的P位未标记,表明上一个chunk处于释放,向上合并成更大的chunk

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

4.如果chunk与Top Chunk相邻,就直接与其合并

5.否则,放入适当的Bins中

        现代堆管理器建立了一系列的Bins以储存不久前被释放的chunk,包括:SmallBin,LargeBin,UnsortedBin,FastBin,TcacheBin,前三种是最古老的版本,而后两种则是近代为了进一步优化效率而产生的,现在的管理器使用这五种来处理释放chunk的操作

struct malloc_chunk {INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).*/INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead.*/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;};
//再次抄写以方便查阅

SmallBin:

        SmallBin共有62个。在 32 位系统上,小于 512 字节(或在 64 位系统上小于 1024 字节)的每个块都有一个相应的小 bin。由于每个小 bin 仅存储一种大小的块,因此它们会自动排序 

        这些块则通过显示链表相互连接,通过FD POINTER和BK POINTER形成双向链表

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

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

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

LargeBin:

        总共63个。其存放的规则如图所示。由于它不像Small Bin那样每个Bin中只有固定大小的chunk,因此在Large Bin中会对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 Bin中,最后两个指针也会发挥作用。

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

        且,最大的堆头的bk_nextsize指向最小的堆头;最小的堆头的fd_nextsize指向最大的堆头

        例如:Bin 2中的第一个chunk的fd指针一个指向Bin 1中的第一个

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

UnsortedBin:

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

The heap manager improves this basic algorithm one step further using an optimizing cache layer called the “unsorted bin”. 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 Bin或者Large Bin,那上述情况的开销就会过大,延缓程序运行。因此程序会先从这个Bin中去寻找合适的chunk返回,如果没有合适的,才去其他Bins中寻找,如果还是没找到,那才会采取其他方式

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

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

        (注:先进先出)

Fast Bin:

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

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

The downside of fastbins, of course, is that fastbin 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 bin by “actually freeing” it, i.e., merging it with adjacent free chunks, and placing the resulting free chunks onto the unsorted bin for malloc to later use.

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

This “consolidation” stage occurs whenever a malloc request is made that is larger than a fastbin 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 的任何块时

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

        程序调用malloc_trim或mallopt时

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

TcacheBin:

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

额外说明:

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

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

        第二个到第六十三个则为Small Bin,以此类推,大致如下图:

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

db-peda$ bins
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
unsortedbin
all: 0x0
smallbins
empty
largebins
empty

参考文章:

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/#bins

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

这篇关于关于如何理解Glibc堆管理器(Ⅱ——Free与Bins)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/905014

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

深入理解RxJava:响应式编程的现代方式

在当今的软件开发世界中,异步编程和事件驱动的架构变得越来越重要。RxJava,作为响应式编程(Reactive Programming)的一个流行库,为Java和Android开发者提供了一种强大的方式来处理异步任务和事件流。本文将深入探讨RxJava的核心概念、优势以及如何在实际项目中应用它。 文章目录 💯 什么是RxJava?💯 响应式编程的优势💯 RxJava的核心概念

如何通俗理解注意力机制?

1、注意力机制(Attention Mechanism)是机器学习和深度学习中一种模拟人类注意力的方法,用于提高模型在处理大量信息时的效率和效果。通俗地理解,它就像是在一堆信息中找到最重要的部分,把注意力集中在这些关键点上,从而更好地完成任务。以下是几个简单的比喻来帮助理解注意力机制: 2、寻找重点:想象一下,你在阅读一篇文章的时候,有些段落特别重要,你会特别注意这些段落,反复阅读,而对其他部分

深入理解数据库的 4NF:多值依赖与消除数据异常

在数据库设计中, "范式" 是一个常常被提到的重要概念。许多初学者在学习数据库设计时,经常听到第一范式(1NF)、第二范式(2NF)、第三范式(3NF)以及 BCNF(Boyce-Codd范式)。这些范式都旨在通过消除数据冗余和异常来优化数据库结构。然而,当我们谈到 4NF(第四范式)时,事情变得更加复杂。本文将带你深入了解 多值依赖 和 4NF,帮助你在数据库设计中消除更高级别的异常。 什么是

分布式系统的个人理解小结

分布式系统:分的微小服务,以小而独立的业务为单位,形成子系统。 然后分布式系统中需要有统一的调用,形成大的聚合服务。 同时,微服务群,需要有交流(通讯,注册中心,同步,异步),有管理(监控,调度)。 对外服务,需要有控制的对外开发,安全网关。

Java IO 操作——个人理解

之前一直Java的IO操作一知半解。今天看到一个便文章觉得很有道理( 原文章),记录一下。 首先,理解Java的IO操作到底操作的什么内容,过程又是怎么样子。          数据来源的操作: 来源有文件,网络数据。使用File类和Sockets等。这里操作的是数据本身,1,0结构。    File file = new File("path");   字

理解java虚拟机内存收集

学习《深入理解Java虚拟机》时个人的理解笔记 1、为什么要去了解垃圾收集和内存回收技术? 当需要排查各种内存溢出、内存泄漏问题时,当垃圾收集成为系统达到更高并发量的瓶颈时,我们就必须对这些“自动化”的技术实施必要的监控和调节。 2、“哲学三问”内存收集 what?when?how? 那些内存需要回收?什么时候回收?如何回收? 这是一个整体的问题,确定了什么状态的内存可以

理解分类器(linear)为什么可以做语义方向的指导?(解纠缠)

Attribute Manipulation(属性编辑)、disentanglement(解纠缠)常用的两种做法:线性探针和PCA_disentanglement和alignment-CSDN博客 在解纠缠的过程中,有一种非常简单的方法来引导G向某个方向进行生成,然后我们通过向不同的方向进行行走,那么就会得到这个属性上的图像。那么你利用多个方向进行生成,便得到了各种方向的图像,每个方向对应了很多