Linux堆内存结构分析之PWN

　　printf的实现中，会调用vfprintfinternal这个内部函数：该函数主要用于将可变参数列表格式化为字符串并将其写入指定流。堆分配函数与内存结构
　　malloc通过brk（）或mmap（）系统调用来获取内存，其区别点在于申请的内存是否大于128KB。
　　拿来一张超经典的图来说事
　　brk（）
　　brk（）通过（发生中断）上移程序的brk指针来向内核申请获取内存。
　　最初startbrk和brk指向相同的位置
　　其中关于Randombrkoffset：关闭ASLR：startbrk和brk初始指向数据段（。data）。bss段的结尾enddata开启ASLR：startbrk和brk初始指向数据段（。data）。bss段的结尾enddataRandombrkoffset
　　mmap（）
　　malloc使用mmap创建私有匿名映射段。
　　私有匿名映射的主要目的是分配新内存（用0填充），并且这个新内存将由调用进程独占使用。
　　位于图中的MemoryMappingSegment段。各个阶段堆内存分布includestdio。hincludestdlib。hincludepthread。hincludeunistd。hincludesystypes。hvoidthreadFunc（voidarg）｛intlocate1；printf（Beforemallocinthread1n）；getchar（）；charaddr（char）malloc（1000）；printf（Aftermallocandbeforefreeinthread1n）；getchar（）；free（addr）；printf（Afterfreeinthread1n）；getchar（）；｝intmain（）｛pthreadtt1；printf（Welcometoperthreadarenaexample：：dn，getpid（））；printf（Beforemallocinmainthreadn）；getchar（）；addr（char）malloc（1000）；printf（Aftermallocandbeforefreeinmainthreadn）；getchar（）；free（addr）；printf（Afterfreeinmainthreadn）；getchar（）；retpthreadcreate（t1，NULL，threadFunc，NULL）；if（ret）｛printf（Threadcreationerrorn）；return1；｝retpthreadjoin（t1，s）；if（ret）｛printf（Threadjoinerrorn）；return1；｝return0；｝1。2。3。4。5。6。7。8。9。10。11。12。13。14。15。16。17。18。19。20。21。22。23。24。25。26。27。28。29。30。31。32。33。34。35。36。37。38。39。40。41。42。43。44。45。46。
　　主线程调用malloc之前inmainthread
　　此时由于没有调用malloc所以内存中并不会存在heap段，并且在线程创建前也是没有线程堆栈的。
　　但注意，此处会有一个小的意外：
　　注意关注main函数注释掉的三行，将他们注释掉的原因在于方便我们更清晰的关注malloc的分配策略：
　　首先说明，printf的实现中，会调用vfprintfinternal这个内部函数：该函数主要用于将可变参数列表格式化为字符串并将其写入指定流。
　　在下列情况中它可能会申请堆空间来存储这些字符串：可变参数列表中包含的参数数量较多，导致格式化后的字符串需要较多的内存来存储。可变参数列表中包含的参数类型不确定，因此无法预先确定格式化后的字符串长度。
　　在这些情况下，vfprintfinternal函数可能会动态申请堆空间来存储格式化后的字符串，以确保有足够的内存来容纳这些字符串。
　　于是就会出现这样的情况：
　　为了探明到底是谁调用了malloc于是在跟着往里走走，便发现：
　　果然在vfprintfinternal中发生了malloc的调用（可真靠里啊。）
　　所以先将前面的printf注释掉：
　　此时没有调用malloc前，并没有产生heap段。
　　主线程调用mallocinmainthread
　　之后主线程通过malloc申请了1000字节的空间，这明显是小于128KB这个界限值的，所以此时会通过系统调用brk（）上移堆区指针分配空间，一共分配了：
　　0x590000x7a0000x21000字节的空间，也就是1351481024132KB的空间，远远大于我们需要的1000字节的空间。
　　这132KB的空间的名号为：arena。
　　又因为他是在主线程中分配的，所以又被称为mainarena。
　　每个arena中又有多个以链表组织的chunk，刚刚malloc分配的1000字节空间就属于mainarena下的一个chunk块。
　　看其中的Uablesize表示的就是可用大小，也就是刚刚申请的1000字节，至于为啥块的总大小为1008字节会在后续说明。
　　为什么分配远大于申请的空间？
　　由于若每次分配都要进行系统调用切换状态是非常低效的，所以会维持一个类似内存池的结构，比方说上述例子，第一次在主线程中申请后堆空间后，若后续再继续申请堆空间，则会先从这分配的132KB中剩余的部分申请。
　　直到不够的时候才会通过增加brk（）（视申请的空间大小而定）上移堆指针（增加programbreaklocation）的方式（申请过大则使用mmap内存映射）来增加mainarena的大小。
　　同理，当mainarena中有过多空闲内存的时候，也会通过减小programbreaklocation的方式来缩小mainarena的大小。
　　主线程调用freeinmainthread
　　可以看到，在主线程中free掉刚刚申请的空间后，heap段并没有被释放，有前面的描述这里很好理解，因为后续还有可能要申请堆空间所以堆空间不会直接还给系统，交给内存分配器ptmalloc来管理。
　　释放掉返还的空间并不会直接加入mainarena中的链表中，而是被加入到mainarenabin中，这是一种专门用于存储同类型freechunk的双链表。
　　【但注意，该双向链表并不是一个全新的结构，而是依次指向了原mainarena中被释放的chunk块】
　　这类用于记录释放后的空闲空间的双向链表称为bins。
　　只要有空间被free后，加入了bins，那么之后再通过malloc申请空间时，就会先从bins双链表中寻找符合要求的chunk。
　　thread1调用mallocin（thread1）thread
　　为了通过gdb观察thread1，直接在threadFunc打断点运行即可
　　由于Linux中子线程是通过mmap映射内存空间，所以其堆是通过mmap映射而来，且栈也位于内存映射区
　　详情见：
　　Wherearethestacksfortheotherthreadslocatedinaprocessvirtualaddressspace？
　　此处若要向确认其栈空间确实位于mmap的内存映射区可以用一个最简单的方案，在线程函数中创建一个变量，观察其地址intlocate1；（原代码中已注释掉）
　　而由于该区域是紧邻libc。so。6这个位于映射区的动态库的，所以可以确认子线程的栈空间确实位于内存映射区中。
　　根据刚刚的内存分布图，内存中栈区内存映射去堆区的虚拟内存地址是依次递减的。
　　所以为该进程分配的堆区也确实位于刚刚栈区的上方（低地址），其大小于主线程中通过brk（）分配的大小相同，也是0x21000也就是132KB即thread1的arena。
　　thread1调用freein（thread1）thread
　　流程同主线程关于Arena
　　结合前面的介绍，可知arena是一种用于组织堆分配块的数据结构。
　　该单词arena的原意是一个大型的比赛场馆或活动场所，比如一个体育馆或剧院。在这种情况下，arena可能是因为它用来组织和管理大量的内存块，类似于一个体育馆用来组织和管理大量的比赛或活动
　　下述参考来源于网络，并没有进行验证：
　　虽然看似上述程序中每个进程申请堆空间时都会有一个独立的arena，但arena的数量并不是可以随着现成的增加随意增加的，是有着最大值限制的。
　　systems
　　numberofarena
　　32bits
　　2xnumberofcpucores1
　　64bits
　　8xnumberofcpucores1
　　若核心数对应的最大arena数不足以支撑新产生的线程，则ptmalloc则会遍历所有可用的arena，并尝试加锁，若加锁成功则将该arena返回给申请的线程，此arena会被当前子线程和原来使用的线程共享使用，若找不到（当前所有的arena都在使用中）则当前子线程的malloc被阻塞等待。堆内存管理
　　在ptmalloc中对于堆的管理，主要涉及到3种数据结构，但若是直接列出每种数据结构的结构体，未免过于枯燥且难以理解，所以我们还是从刚刚的程序分析，分析结构体中的每一个字段在内存中的位置。
　　首先出场的是heapinfo这个结构体heapinfo
　　注意：该结构体mainarena中并不存在，子线程threadarena中是存在的，而且每当剩余空间不足重新申请一块heap的时候就会产生一个该结构体。
　　其作用一种用于在程序中存储堆信息的数据结构，具体存储了什么信息先来看他的结构体。typedefstructheapinfo｛arenaforthisheap。Previousheap。Currentsizeinbytes。SizeinbytesthathasbeenmprotectedPROTREADPROTWRITE。Makesurethefollowingdataisproperlyaligned，particularlythatsizeof（heapinfo）2SIZESZisamultipleofMALLOCALIGNMENT。charpad〔6SIZESZMALLOCALIGNMASK〕；｝1。2。3。4。5。6。7。8。9。10。11。12。
　　pad字段用来确保该结构在内存中是正确对齐的，无需特别关注其计算含义。
　　单heapsegment情况
　　单heap段时只有一个heapinfo结构，位于堆区的最开始。
　　拿出一张很经典的图
　　不过目前来说它过于复杂，所以先画一个简化版，再慢慢丰富它。1。
　　复制嗯这样就简单多啦！1。
　　此处就以刚刚程序中，线程里通过内存映射创建的一块堆区为示例：
　　【注意：此处堆区指的是通过brk上移获取的堆空间与通过mmap映射的内存空间】
　　线程thread1中的堆区范围：
　　我们来看看这段堆区中heapinfo结构体中的数值是什么（由于从第4832字节开始都为填充部分，所以只看前32字节的数据）。
　　依次对应下来：arptr：0x00007ffff0000030指向mallocstate结构体的指针接下来会详细来讲prev：0x0000000000000000指向上一个堆的指针由于就一块所以为NULLsize：0x0000000000021000当前堆的字节大小和刚才算出的一样132KBmprotectsize：0x0000000000021000当前已被标记为可读写的堆的字节大小和刚才算出的一样132KB从刚刚的截图也可看出这段空间都是可读可写的
　　多heapsegment情况
　　这很好理解，启用刚刚为NULL的prev指针就可以啦！
　　但注意，上面说了，prev是指向上一个堆的指针，所以是将第二个heapinfo结构体的prev成员指向了第一个heapinfo结构体的起始位置（arptr），这样就构成了一个单链表，方便后续管理。
　　【先提前说一下：mallocstate这个结构体只存在于第一块heap中，后续映射来的heap中是不存在该结构体的】
　　所以简化后的示意图为：
　　mallocchunk
　　由于mallocstate涉及到了整个arena的管理，所以先介绍chunk块的结构与其他的机制，最后再回归到mallocstate中将会更好理解。
　　前面说过，为了便于管理和更加高效的利用内存，第一次申请堆空间时，实际上是申请了一大块远大于所申请空间的arena，而真正返回给用户实际申请大小的是arena中的一个chunk，但刚刚也同样观测到，最终返回的大小比用户实际申请的空间还要大8字节，其中每个chunk都由一个结构体mallocchunk表示，也称为chunkheader。
　　任何的堆管理器都是以chunk为单位进行堆内存管理的，所以对于每一个chunk块中肯定要存在着控制信息，用于指示当前chunk的基本信息。
　　复制structmallocchunk｛defineINTERNALSIZETsizetINTERNALSIZETSizeofpreviouschunk（iffree）。INTERNALSIZETSizeinbytes，includingoverhead。doublelinksusedonlyiffree。这两个指针只在freechunk中存在Onlyusedforlargeblocks：pointertonextlargersize。doublelinksusedonlyiffree。｝；1。2。3。4。5。6。7。8。9。10。11。12。
　　堆内存管理器要求每个chunk块的大小必须为8的整数倍，而通过上述结构体的size字段正是用于描述当前chunk块大小的，既然必须是8的整数倍，那么对于size这个数二进制下，低3位就无效了。（简单来说：一旦这三位有哪些位被置1了，都会导致最终的数一定不是8的倍数）
　　所以这空出来的3位，就被当作了当前chunk的标志位，每一位都表示这当前chunk块一个状态信息，具体的含义会在接下来说明。
　　chunk块的分类
　　chunk总共分为4类：allocatedchunk已被分配使用的chunk块freechunk未被分配未使用的chunk块topchunklastremainderchunk
　　chunk的组织结构
　　先简单介绍一下chunk块的组织结构，详细的介绍，将在会后面说明。
　　chunk在堆内存中是连续的，并不是直接由指针构成的链表，而是通过prevsize和size构成的隐式链表。
　　这样做的好处在于：在进行分配操作的时候，堆内存管理器可以通过遍历整个堆内存的chunk，分析每个chunk的size字段，进而找到合适的chunk，而且在合并不同chunk时，可以减少内存碎片。
　　若不这么做，chunk的合并只能向下合并，必须从头遍历整个堆，然后加以合并，意味着每次进行chunk释放操作消耗的时间与堆的大小成线性关系。
　　allocatedchunk
　　已被分配使用的chunk块
　　图11
　　下图可能与上图存在差异，这并不是错误，后面会进行介绍：
　　图12
　　相关参数含义：prevsize：该参数为mallocchunk中第一个字段，也就是上图中自上而下第一个的大方框中，根据当前chunk前一个chunk类型的不同，此处有两种含义：
　　若前一个chunk为freechunk则prevsize表示前一个freechunk的大小
　　若前一个chunk为allocatedchunk则prevsize没有特殊含义，此处保存的是上一个allocatedchunk块剩余的用户数据（主要是为了复用该控件）size：该参数为mallocchunk中第二个字段，也就是上图中自上而下第二个大方框中，该字段共由4部分组成：
　　前三位NPREVINUSE前一个chunk是否为allocatedchunkMISMAPPED当前chunk是否是通过mmap系统调用产生的PNONMAINARENA当前chunk是否属于mainarena（也就是主线程的arena）
　　拿来之前的一张图来，当前可以看flags：PREVINUSE置位，说明前一个chunk为已分配chunk这么解释对于除第一个被分配的内存块的size字段以外内存块的P位是正确的，但由于该图中的分配是主线程中的第一次分配，对于堆中第一个被分配的内存块的size字段的P位都会被置为1【目的在于：防止非法访问前面的内存】ISMMAPPED没置位，说明当前堆是通过brk（）上移分配的NONMAINARENA没置位，说明当前为主线程arena
　　其余位：当前chunk大小大小必须是SIZESZ的整数倍，如果申请的大小不是其整数倍，会被填充。32位系统SIZESZ464位系统SIZESZ8
　　上图中我们用malloc申请了1000字节的空间最终分配了1008字节的原因在于，由于该chunk的前一块不是freechunk所以并不存在第一个prevsize或者说prevsize的位置保存的是前一块中的数据，那么其实附加信息只有size，由于64位系统程序所以附加了8字节的空间，又因为1008是2SIZESZ的倍数，所以无需填充。
　　用户数据foruserdata用户数据区域会被置0，准备存入用户的数据
　　freechunk
　　图13
　　有了前面的图，此处就直接看原图了。
　　prevsize：为了防止碎片化，堆中不存在两个相邻的freechunk（如果存在，则会被堆管理器合并为一个），因此对于freechunk，其prevsize区域中一定包含的是上一个chunk中一部分的有效数据或者为了地址对齐所做的填充对齐padding
　　size：与allocatedchunk一致，表示当前chunk的大小，其标志位NMP也同上述含义相同
　　fd：前向指针指向当前freechunk在同一个bin（一种用于加快内存分配和释放效率的显示链表）的下一个freechunk
　　bk：后向指针指向当前freechunk在同一个bin的上一个freechunk
　　topchunk
　　该chunk位于一个arena的最顶部（即最高内存地址处），不属于任何bin。
　　在当前的heap所有的freechunk（无论哪种bin中）都无法满足用户请求的内存大小的时候，将会将该chunk的空间，分配给用户使用。
　　如果topchunk的大小比用户请求的大小要大的话，就将该topchunk分作两部分：用户请求的chunk和剩余的部分。（成为新的topchunk）
　　否则，就需要扩展heap或分配新的heap了，在mainarena中通过sbrk扩展heap，而在threadarena中通过mmap分配新的heap。
　　LastRemainderChunk
　　该chunk涉及到另一个非常重要的显示链表bin，在介绍完bin后再回来说他。
　　隐式链表
　　若不对chunk块进行分类，则默认所有的chunk块都是长成这个样子的：
　　假设当前有三个chunk块，分别将其命名为：FREEAALLOCATEBFREEC
　　通过其名字就可以知道当前三个chunk块的结构关系为：一个已经分配的块在两个未使用的块之间
　　那么就有了这样的问题，若要释放当前的ALLOCATEB块，该如何将FREEAALLOCATEBFREEC合成一个freechunk（之前说过是不存在相邻freechunk的）？
　　这里主要的问题在于如何合并FREEA与ALLOCATEBFREEC，因为ALLOCATEB和FREEC是很好合并的，ALLOCATEB只要向下获取到FREEC的chunksize参数，也就知道了FREEC的大小，直接合并即可。
　　但ALLOCATEB块和FREEA之间该如何合并呢？
　　这就提出了带边界的标记的合并技术，而且要对chunk块进行分类，因为allocatedchunk是不需要合并的，自然也就不存在这个问题。
　　所谓的带边界标记中的边界标记，也就是在原默认chunk块的边界处附加一个相邻chunk块的信息，于是自然而然，当前chunk块为freechunk时，就会为当前freechunk块附加一个尾部，该尾部与其头部size字段一致。
　　【allocatedchunk是不会附加该尾部的】
　　但此时还是拥有优化空间的，当前freechunk没有必要完全复制一份其首部chunksize到尾部，因为若该尾部交给freechunk来添加，那无论该freechunk所处什么位置，都需要添加一个尾部，所以完全可以将这个任务交给allocatedchunk来完成，只有当allocatedchunk前为freechunk时，在allocatedchunk的chunksize前记录前一个freechunk的大小size即可，于是我们最常见的一种格式（图12）便出现了：
　　若前面不是freechunk则prevsize用于保存前一个chunk块的剩余数据或padding填充即可
　　有了这样的结构，FREEA与ALLOCATEB的合并就变得简单了。mallocstate
　　mallocstate用于表示arena的信息，因此也被称为arenaheader，每个线程只含有个arenaheader。structmallocstate｛Serializeaccess。Flags（formerlyinmaxfast）。FastbinsmfastbinptrfastbinsY〔NFASTBINS〕；BTNormalbinspackedasdescribedabovemchunkptrbins〔NBINS22〕；Bitmapofbinsunsignedintbinmap〔BINMAPSIZE〕；LLinkedlistforfreearenas。Memoryallocatedfromthesysteminthisarena。INTERNALSIZETINTERNALSIZET｝；1。2。3。4。5。6。7。8。9。10。11。12。13。14。15。16。17。18。19。20。21。22。23。24。25。26。27。28。29。30。31。32。33。
　　该结构的介绍同样需要先说bin，所以也在后续说明。