Linux堆内存结构分析之PWN

　　printf的实现中，会调用 __vfprintf_internal这个内部函数：该函数主要用于将可变参数列表格式化为字符串并将其写入指定流。堆分配函数与内存结构
　　malloc通过brk()或mmap()​系统调用来获取内存，其区别点在于申请的内存是否大于128KB.
　　拿来一张超经典的图来说事
　　brk()
　　brk()​通过（发生中断）上移程序的brk指针来向内核申请获取内存。
　　最初start_brk和brk指向相同的位置
　　其中关于Random brk offset： 关闭ASLR：start_brk和brk​初始指向数据段（.data​）/.bss​段的结尾end_data 开启ASLR：start_brk和brk​初始指向数据段（.data​）/.bss​段的结尾end_data + Random brk offset
　　mmap()
　　malloc​使用mmap创建 私有匿名映射段。
　　私有匿名映射的主要目的是分配新内存（用0填充），并且这个新内存将由调用进程独占使用。
　　位于图中的Memory Mapping Segment段。 各个阶段堆内存分布#include  #include  #include  #include  #include  void* threadFunc(void* arg)  {         // int locate = 1;         printf(＂Before malloc in thread 1n＂);         getchar();         char* addr = (char*) malloc(1000);         printf(＂After malloc and before free in thread 1n＂);         getchar();         free(addr);         printf(＂After free in thread 1n＂);         getchar(); } int main()  {         pthread_t t1;         void* s;         int ret;         char* addr;         // printf(＂Welcome to per thread arena example::%dn＂,getpid());         // printf(＂Before malloc in main threadn＂);         // getchar();         addr = (char*) malloc(1000);         printf(＂After malloc and before free in main threadn＂);         getchar();         free(addr);         printf(＂After free in main threadn＂);         getchar();         ret = pthread_create(&t1, NULL, threadFunc, NULL);         if(ret)         {                 printf(＂Thread creation errorn＂);                 return -1;         }         ret = pthread_join(t1, &s);         if(ret)         {                 printf(＂Thread join errorn＂);                 return -1;         }         return 0; }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之前 __in main thread
　　此时由于没有调用malloc​所以内存中并不会存在heap段，并且在线程创建前也是没有线程堆栈的。
　　但注意，此处会有一个小的 ＂意外＂：
　　注意关注main​函数注释掉的三行，将他们注释掉的原因在于方便我们更清晰的关注malloc的分配策略：
　　首先说明，printf​的实现中，会调用 __vfprintf_internal这个内部函数：该函数主要用于将可变参数列表格式化为字符串并将其写入指定流。
　　在下列情况中它可能会申请堆空间来存储这些字符串： 可变参数列表中包含的参数数量较多，导致格式化后的字符串需要较多的内存来存储。 可变参数列表中包含的参数类型不确定，因此无法预先确定格式化后的字符串长度。
　　在这些情况下，__vfprintf_internal函数可能会动态申请堆空间来存储格式化后的字符串，以确保有足够的内存来容纳这些字符串。
　　于是就会出现这样的情况：
　　为了探明到底是谁调用了malloc于是在跟着往里走走，便发现：
　　果然在 __vfprintf_internal​中发生了malloc的调用（可真靠里啊….）
　　所以先将前面的printf注释掉：
　　此时没有调用malloc​前，并没有产生heap段。
　　主线程调用malloc__in main thread
　　之后主线程通过malloc​申请了1000​字节的空间，这明显是小于128KB​这个界限值的，所以此时会通过系统调用brk()上移堆区指针分配空间，一共分配了：
　　0x59000 - 0x7a000 = 0x21000​字节的空间，也就是135148 / 1024 = 132 KB​的空间，远远大于我们需要的1000字节的空间。
　　这132 KB​的空间的 ＂名号＂ 为：arena.
　　又因为他是在主线程中分配的，所以又被称为main arena.
　　每个arena​中又有多个以链表组织的chunk​，刚刚malloc​分配的1000​字节空间就属于main arena​下的一个chunk块。
　　看其中的Uable size​表示的就是可用大小，也就是刚刚申请的1000​字节，至于为啥块的总大小为1008字节会在后续说明。
　　为什么分配远大于申请的空间？
　　由于若每次分配都要进行系统调用切换状态是非常低效的，所以会维持一个类似内存池的结构，比方说上述例子，第一次在主线程中申请后堆空间后，若后续再继续申请堆空间，则会先从这分配的132 KB中剩余的部分申请。
　　直到不够的时候才会通过增加brk()​（视申请的空间大小而定）上移堆指针（增加program break location​）的方式（申请过大则使用mmap​内存映射）来增加main arena的大小。
　　同理，当main arena​中有过多空闲内存的时候，也会通过减小program break location​的方式来缩小main arena的大小。
　　主线程调用free__in main thread
　　可以看到，在主线程中free​掉刚刚申请的空间后，heap​段并没有被释放，有前面的描述这里很好理解，因为后续还有可能要申请堆空间所以堆空间不会直接还给系统，交给内存分配器ptmalloc来管理。
　　释放掉返还的空间并不会直接加入main arena​中的链表中，而是被加入到main arena bin​中，这是一种专门用于存储同类型free chunk的双链表。
　　【但注意，该双向链表并不是一个全新的结构，而是依次指向了原main arena​中被释放的chunk块】
　　这类用于记录释放后的空闲空间的双向链表称为bins.
　　只要有空间被free​后，加入了bins​，那么之后再通过malloc​申请空间时，就会先从bins​双链表中寻找符合要求的chunk.
　　thread 1调用malloc__in (thread 1) thread
　　为了通过gdb​观察thread 1​，直接在threadFunc打断点运行即可
　　由于Linux​中子线程是通过mmap​映射内存空间，所以其堆是通过mmap映射而来，且栈也位于内存映射区
　　详情见：
　　Where are the stacks for the other threads located in a process virtual address space?
　　此处若要向确认其栈空间确实位于mmap​的内存映射区可以用一个最简单的方案，在线程函数中创建一个变量，观察其地址int locate = 1;（原代码中已注释掉）
　　而由于该区域是紧邻libc.so.6这个位于映射区的动态库的，所以可以确认子线程的栈空间确实位于内存映射区中。
　　根据刚刚的内存分布图，内存中 栈区 内存映射去 堆区 的虚拟内存地址是依次递减的。
　　所以为该进程分配的堆区也确实位于刚刚栈区的上方（低地址），其大小于主线程中通过brk()​分配的大小相同，也是0x21000​也就是132 KB即thread1的arena.
　　thread 1调用free__in (thread 1) thread
　　流程同主线程 关于 Arena
　　结合前面的介绍，可知arena是一种用于组织堆分配块的数据结构。
　　该单词＂arena＂​的原意是一个大型的比赛场馆或活动场所，比如一个体育馆或剧院。在这种情况下，arena可能是因为它用来组织和管理大量的内存块，类似于一个体育馆用来组织和管理大量的比赛或活动
　　下述参考来源于网络，并没有进行验证：
　　虽然看似上述程序中每个进程申请堆空间时都会有一个独立的arena​，但arena的数量并不是可以随着现成的增加随意增加的，是有着最大值限制的。
　　systems
　　number of arena
　　32bits
　　2 x number of cpu cores + 1
　　64bits
　　8 x number of cpu cores + 1
　　若核心数对应的最大arena​数不足以支撑新产生的线程，则ptmalloc​则会遍历所有可用的arena​，并尝试加锁，若加锁成功则将该arena​返回给申请的线程，此arena​会被当前子线程和原来使用的线程共享使用，若找不到（当前所有的arena​都在使用中）则当前子线程的malloc被阻塞等待。 堆内存管理
　　在ptmalloc​中对于堆的管理，主要涉及到3种数据结构，但若是直接列出每种数据结构的结构体，未免过于枯燥且难以理解，所以我们还是从刚刚的程序分析，分析结构体中的每一个字段在内存中的位置。
　　首先出场的是_heap_info这个结构体 _heap_info
　　注意：该结构体main arena​中并不存在，子线程thread arena​中是存在的，而且每当剩余空间不足重新申请一块heap的时候就会产生一个该结构体。
　　其作用一种用于在程序中存储堆信息的数据结构，具体存储了什么信息先来看他的结构体。 typedef struct _heap_info {   mstate ar_ptr;                /* arena for this heap. */   struct _heap_info *prev;      /* Previous heap. */   size_t size;                  /* Current size in bytes. */   size_t mprotect_size;         /* Size in bytes that has been mprotected                                    PROT_READ|PROT_WRITE.  */    /* Make sure the following data is properly aligned, particularly       that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of       MALLOC_ALIGNMENT. */   char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK]; } heap_info;1.2.3.4.5.6.7.8.9.10.11.12.
　　// pad字段用来确保该结构在内存中是正确对齐的，无需特别关注其计算含义。
　　单 heap segment 情况
　　单heap​段时只有一个_heap_info结构，位于堆区的最开始。
　　拿出一张很经典的图
　　不过目前来说它过于复杂，所以先画一个简化版，再慢慢丰富它。1.
　　复制  嗯~这样就简单多啦！1.
　　此处就以刚刚程序中，线程里通过内存映射创建的一块堆区为示例：
　　【 注意：此处堆区指的是通过brk​上移获取的堆空间与通过mmap映射的内存空间】
　　线程thread 1中的堆区范围：
　　我们来看看这段堆区中_heap_info​结构体中的数值是什么（由于从第4 * 8 = 32​字节开始都为填充部分，所以只看前32字节的数据）。
　　依次对应下来： ar_ptr：0x00007ffff0000030​指向malloc_state​结构体的指针接下来会详细来讲 prev：0x0000000000000000​指向上一个堆的指针由于就一块所以为​NULL size：0x0000000000021000​当前堆的字节大小和刚才算出的一样​132 KB mprotect_size：0x0000000000021000​当前已被标记为可读写的堆的字节大小和刚才算出的一样​132 KB从刚刚的截图也可看出这段空间都是可读可写的
　　多 heap segment 情况
　　这很好理解，启用刚刚为NULL的prev指针就可以啦！
　　但注意，上面说了，prev​是指向上一个堆的指针，所以是将第二个heap_info​结构体的prev​成员指向了第一个heap_info​结构体的起始位置（ar_ptr），这样就构成了一个单链表，方便后续管理。
　　【先提前说一下：malloc_state​这个结构体只存在于第一块heap中，后续映射来的 heap 中是不存在该结构体的】
　　所以简化后的示意图为：
　　malloc_chunk
　　由于malloc_state​涉及到了整个arena​的管理，所以先介绍chunk​块的结构与其他的机制，最后再回归到malloc_state中将会更好理解。
　　前面说过，为了便于管理和更加高效的利用内存，第一次申请堆空间时，实际上是申请了一大块远大于所申请空间的arena​，而真正返回给用户实际申请大小的是 arena​中的一个 chunk​，但刚刚也同样观测到，最终返回的大小比用户实际申请的空间还要大8​字节，其中每个 chunk​都由一个结构体 malloc_chunk​表示，也称为 chunk header.
　　任何的堆管理器都是以chunk​为单位进行堆内存管理的，所以对于每一个 chunk 块中肯定要存在着控制信息，用于指示当前chunk的基本信息。
　　复制  struct malloc_chunk  {   /* #define INTERNAL_SIZE_T size_t */   INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */   INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */   struct malloc_chunk* fd;         /* double links -- used only if free. 这两个指针只在free chunk中存在*/   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; };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类： allocated chunk已被分配使用的 chunk 块 free chunk未被分配未使用的 chunk 块 top chunk last remainder chunk
　　chunk 的组织结构
　　先简单介绍一下 chunk 块的组织结构，详细的介绍，将在会后面说明。
　　chunk 在堆内存中是连续的，并不是直接由指针构成的链表，而是通过 prev_size 和 size 构成的隐式链表。
　　这样做的好处在于：在进行分配操作的时候，堆内存管理器可以通过遍历整个堆内存的 chunk，分析每个 chunk 的 size 字段，进而找到合适的 chunk，而且在合并不同 chunk 时，可以减少内存碎片。
　　若不这么做，chunk 的合并只能向下合并，必须从头遍历整个堆，然后加以合并，意味着每次进行 chunk 释放操作消耗的时间与堆的大小成线性关系。
　　allocated chunk
　　已被分配使用的chunk块
　　图 1-1
　　下图可能与上图存在差异，这并不是错误，后面会进行介绍：
　　图 1-2
　　相关参数含义： prev_size ：该参数为 malloc_chunk 中第一个字段，也就是上图中自上而下第一个的大方框中，根据当前 chunk 前一个 chunk 类型的不同，此处有两种含义：
　　若前一个 chunk 为 free chunk 则 prev_size 表示前一个 free chunk 的大小
　　若前一个 chunk 为 allocated chunk 则 prev_size 没有特殊含义，此处保存的是上一个 allocated chunk 块剩余的用户数据（主要是为了复用该控件） size ：该参数为 malloc_chunk 中第二个字段，也就是上图中自上而下第二个大方框中，该字段共由 4 部分组成：
　　前三位 N PREV_INUSE 前一个 chunk 是否为 allocated chunk M IS_MAPPED 当前 chunk 是否是通过 mmap 系统调用产生的 P NON_MAIN_ARENA 当前 chunk 是否属于 main arena (也就是主线程的 arena)
　　拿来之前的一张图来，当前可以看 flags ： PREV_INUSE 置位，说明前一个 chunk 为已分配 chunk 这么解释对于除第一个被分配的内存块的 size 字段以外内存块的 P 位是正确的，但由于该图中的分配是主线程中的第一次分配，对于堆中第一个被分配的内存块的 size 字段的 P 位都会被置为 1【目的在于：防止非法访问前面的内存】 IS_MMAPPED 没置位，说明当前堆是通过 brk() 上移分配的 NON_MAIN_ARENA 没置位，说明当前为主线程 arena
　　其余位：当前 chunk 大小大小必须是 SIZE_SZ 的整数倍，如果申请的大小不是其整数倍，会被填充。 32位系统 SIZE_SZ = 4 64位系统 SIZE_SZ = 8
　　上图中我们用 malloc 申请了 1000 字节的空间最终分配了 1008 字节的原因在于，由于该 chunk 的前一块不是 free chunk 所以并不存在第一个 prev_size 或者说 prev_size 的位置保存的是前一块中的数据，那么其实附加信息只有 size ，由于 64 位系统/程序 所以附加了 8 字节的空间，又因为 1008 是 2 * SIZE_SZ 的倍数，所以无需填充。
　　用户数据 for user_data用户数据区域会被置 0 ，准备存入用户的数据
　　free chunk
　　图 1-3
　　有了前面的图，此处就直接看原图了。
　　prev_size ：为了防止碎片化，堆中不存在两个相邻的 free chunk （如果存在，则会被堆管理器合并为一个），因此对于 free chunk ，其 prev_size 区域中一定包含的是上一个 chunk 中一部分的有效数据或者为了地址对齐所做的填充对齐 padding
　　size ：与 allocated chunk 一致，表示当前 chunk 的大小，其标志位 N M P 也同上述含义相同
　　fd ：前向指针指向当前 free chunk 在同一个 bin（一种用于加快内存分配和释放效率的显示链表）的下一个 free chunk
　　bk ：后向指针指向当前 free chunk 在同一个 bin 的上一个 free chunk
　　top chunk
　　该 chunk 位于一个 arena 的最顶部（即最高内存地址处），不属于任何 bin.
　　在当前的 heap 所有的 free chunk（无论哪种 bin 中）都无法满足用户请求的内存大小的时候，将会将该 chunk 的空间 ，分配给用户使用。
　　如果 top chunk 的大小比用户请求的大小要大的话，就将该 top chunk 分作两部分：用户请求的 chunk 和 剩余的部分。（成为新的 top chunk）
　　否则，就需要扩展 heap 或分配新的 heap 了，在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap.
　　Last Remainder Chunk
　　该 chunk 涉及到另一个非常重要的显示链表 bin ，在介绍完 bin 后再回来说他。
　　隐式链表
　　若不对 chunk 块进行分类，则默认所有的 chunk 块都是长成这个样子的：
　　假设当前有三个 chunk 块，分别将其命名为： FREE_A ALLOCATE_B FREE_C
　　通过其名字就可以知道当前三个 chunk 块的结构关系为：一个已经分配的块在两个未使用的块之间
　　那么就有了这样的问题，若要释放当前的 ALLOCATE_B 块，该如何将 FREE_A ALLOCATE_B FREE_C 合成一个 free chunk (之前说过是不存在相邻 free chunk 的)？
　　这里主要的问题在于如何合并 FREE_A 与 ALLOCATE_B FREE_C，因为 ALLOCATE_B 和 FREE_C 是很好合并的，ALLOCATE_B 只要向下获取到 FREE_C 的 chunk size 参数，也就知道了 FREE_C 的大小，直接合并即可。
　　但 ALLOCATE_B 块 和 FREE_A 之间该如何合并呢？
　　这就提出了带边界的标记的合并技术，而且要对 chunk 块进行分类，因为 allocated chunk 是不需要合并的，自然也就不存在这个问题。
　　所谓的带边界标记中的边界标记，也就是在原默认 chunk 块的边界处附加一个相邻 chunk 块的信息，于是自然而然，当前 chunk 块为 free chunk 时，就会为当前 free chunk 块 附加一个尾部，该尾部与其头部 size 字段一致。
　　【allocated chunk 是不会附加该尾部的】
　　但此时还是拥有优化空间的，当前 free chunk 没有必要完全复制一份其首部 chunk size到尾部，因为若该尾部交给 free chunk 来添加，那无论该 free chunk 所处什么位置，都需要添加一个尾部，所以完全可以将这个任务交给 allocated chunk 来完成，只有当 allocated chunk 前为 free chunk 时，在 allocated chunk 的 chunk size 前记录前一个 free chunk 的大小 size 即可，于是我们最常见的一种格式（图 1-2）便出现了：
　　若前面不是 free chunk 则 prev_size 用于保存前一个 chunk 块的剩余数据或 padding 填充即可
　　有了这样的结构，FREE_A 与 ALLOCATE_B 的合并就变得简单了。 malloc_state
　　malloc_state 用于表示 arena 的信息，因此也被称为 arena header ，每个线程只含有个 arena header. struct malloc_state {   /* Serialize access.  */   mutex_t mutex;      /* Flags (formerly in max_fast).  */   int flags;    /* Fastbins */   mfastbinptr fastbinsY[NFASTBINS];    /* Base of the topmost chunk -- not otherwise kept in a bin */   mchunkptr top;    /* The remainder from the most recent split of a small request */   mchunkptr last_remainder;    /* Normal bins packed as described above */   mchunkptr bins[NBINS * 2 - 2];    /* Bitmap of bins */   unsigned int binmap[BINMAPSIZE];    /* Linked list */   struct malloc_state *next;    /* Linked list for free arenas.  */   struct malloc_state *next_free;    /* Memory allocated from the system in this arena.  */   INTERNAL_SIZE_T system_mem;   INTERNAL_SIZE_T max_system_mem; };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 ，所以也在后续说明。