首页
论坛
课程
招聘
深度理解glibc内存分配
2022-1-28 19:34 24635

深度理解glibc内存分配

2022-1-28 19:34
24635

  如果对glibc内存管理的逻辑比较了解,在学习各种堆漏洞利用的方法时,就会更顺畅一些,而且glibc内存管理的代码,本身也很值得看一看,好几次决定写点总结,都是咬咬牙又放弃了,现在,我觉得已经不能再拖了。

1. 什么是分配/释放?

  在刚入门C语言编程时就知道:为了使用一块堆内存,要先分配。随着接触编程一段时间后,慢慢开始意识到:分配,就是底层代码把正在使用的内存区域记录下来,从而保证程序始终知道哪些空间是正在使用的,哪些空间当前是空闲的,进一步保证每次获取的内存,不会与正在使用的内存重叠。

  • 分配释放初级理解
  • 分配释放的本质
    1
    2
    // 32位系统
    *(char *)0x9d08008 = 0;
    执行:
    1
    2
    jmpcall@ubuntu:test$ ./a.out
    Segmentation fault
    进程刚启动时,空闲空间是很大的,很容易自己找到还未使用内存的地址,比如0x9d08008(<0xc0000000,所以为用户空间的地址,用户态无法访问内核空间稍后另外说明),但是执行时,却段错误了。
    这个段错误是怎么来的呢?
    猜想:系统给的。这样猜想就太笼统了,“系统”是什么,怎么“给的”,都没有具体的信息。“系统”如果是底层的代码逻辑(glibc或者内核),那如果底层代码本身执行这样的指令,就是允许的吗,还是说“系统”是个什么别的东西?
    反汇编一下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int main()
    {
     80483c3:    55                       push   %ebp
     80483c4:    89 e5                    mov    %esp,%ebp
            *(char *)0x9d08008 = 0;
     80483c6:    b8 08 80 d0 09           mov    $0x9d08008,%eax
     80483cb:    c6 00 00                 movb   $0x0,(%eax)
            return 0;
     80483ce:    b8 00 00 00 00           mov    $0x0,%eax
    }
    需要明白一点的是,即使以上是应用程序的代码,它的每一条指令,也是直接由CPU执行的,所以0x9d08008这个地址无法访问,是CPU在硬件层判断的,并不是glibc或者内核在软件层进行判断的。就是说,分配归根结底是为了让CPU硬件层“承认”哪些内存空间可用,换句话说,底层代码对已使用空间的记录,其实是给硬件层使用的(所以记录在哪,怎么记录,就必须按照CPU手册中的规范来做)。这样,以上代码绕开分配函数,直接使用0x9d08008这个地址,为什么产生段错误,就很好理解了:即使0x9d08008始终不与已使用的内存空间冲突,也会由于没记录到已分配空间,而不被CPU硬件层“承认”。所以,内存分配的本质,是按照硬件规范,对已使用空间进行记录
  • 分配/释放机制建立过程
    刚开机执行的第一条指令,就可以调用分配接口吗?
    很多硬件的功能都是可以切换的,比如沙发,也可以铺开变成一张床,而CPU同样身为一种硬件,它的功能和状态也是可以调节的(通过给一些寄存器的特定位加电)。比如,它可以切换为实模式或保护模式,保护模式下又可以调节到不同的权限级别(低权限状态下,相当于将CPU的部分功能“锁”起来了,执行不了特权指令)。CPU刚加电时,正是默认处于实模式(这是硬件设计保证的),内核启动的初级阶段,自然就是在CPU实模式下执行,指令中的地址,会被CPU直接加到地址总线上,也就是说,这个阶段,使用内存是不需要经过分配这个步骤的,甚至有些是人为安排的固定地址。
    内核在实模式运行阶段,会为进入保护模块做好准备(如同软件开发中“初始化”的概念),因为切换到保护模式的瞬间,CPU马上就会按照另外一套硬件逻辑,对软件的指令进行处理,这时再执行访问内存的指令,就不再像实模式那样直截了当了,而是必须先根据CR3寄存器,找到目录表、页表,查找跟指令包含地址对应的物理地址,并且通过一些检查后,才最终进行内存访问,所以目录表、页表的基础内容,以及CR3寄存器的指向,都要在实模式运行阶段设置好。
    进入保护模式后,指令中包含的地址,就是虚拟地址了,类似于数学符号(不过和数学符号也是有区别的,哪怕某个复杂的数学推导过程将α、β、γ、A-Z都用完了,也还有A0、A1、A10000..可以用,而虚拟地址的个数是有限的,比如对于32位系统,虚拟地址=指针值,也就是一个32位的值,所以只有2^32个),虚拟地址只是起到指代物理地址的作用,执行时具体由哪个物理地址“扮演”它,就可以通过软件层面进行设计了,换句话说就是,CPU保护模式的这种硬件特性,给了内核可以在底层进行地址映射的机会,从而让物理地址对上层程序透明。
  • 总结
    ① 早期CPU只支持模式,它直接“承认”指令中包含的地址,分配/释放机制只能给程序编写带来点便利,但起不到防止内存冲突的作用,因为即使记录了哪些空间正在被别的任务,甚至是系统使用,但只要某个任务有bug,甚至是故意的,仍然可以对这些空间进行随意访问和修改。
    ② CPU进入保护模式后,只会“承认”已经记录映射关系的地址,映射过程由硬件执行,映射关系由软件设置,这其实是硬件层向软件层提出了一种要求,也正是由于这种要求,内核才有机会限制用户态代码访问任意内存,将CPU的充分使用权,掌握在自己手里,从而保证系统的稳定性。

2. 内存管理的环节

  刚才已经说了,CPU的权限是支持调节的,最高权限时,可以执行所有指令,包括将权限调低,但低权限向高权限调节,就需要接受额外的条件(否则权限如果可以随意调高,那么权限设计的意义就没了),那就是必须穿过“门”进行提升,而在穿过“门”的同时,也要求执行一次代码跳转(这种要求,以及“门”的设计,也是硬件层实现的),而内核代码是在CPU刚上电时就开始执行了,相比用户程序,内核具有设置这个跳转地址的先机,所以当然会将其设置为内核代码的地址。这样,内核代码就总能在最高权限执行,而用户代码总是在低权限执行,同时又有路径从用户态(低CPU权限下执行用户代码的状态)回到内核态(最高CPU权限下执行内核代码的状态)。很多特权指令,只在CPU高权限状态时有效,比如CR3寄存器的读/写指令,从而“强制”用户程序使用内核接口,对进程本身的虚拟空间和占用的物理内存,进行管理。

  • 内核与glibc

    CPU保护模式下,指令中包含的地址是虚拟地址,最终能访问到哪个物理地址,完全由底层的内核代码决定,而内核对3G~4G虚拟空间的映射,只会记录一份,对0~3G虚拟空间的映射,为每个进程单独记录一份。所有进程访问3G~4G虚拟空间,会访问到相同的物理内存,因此也是所有进程的公共空间,为了防止被某个进程任意读写,内核在映射3G~4G范围的地址时,同时也会向硬件标记,只有最高权限才能访问,从而使进程希望访问内核空间时,必须切换到内核态,由内核代码代为执行,正是这个原因,3G~4G虚拟空间被称为“内核空间”;不同进程访问0~3G虚拟空间,访问到的都是内核只为自己映射的物理内存,称为“用户空间”。
    • 内核中的内存管理
      • 物理内存
      • 虚拟空间--所有进程公共的内核空间
      • 虚拟空间--各个进程私有的用户空间
    • glibc中的内存管理
      • 当前进程用户空间中已分配的部分(内核侧)
      • 还未分配给应用程序的部分(业务侧)
  • glibc内存管理目的
    为什么要在内核管理的外面,加一层glibc管理?
    反正肯定不是因为开发内核的大佬都是菜鸟,能力已经发挥到极限了,只能提供brk()、mmap()/munmap()这几个简陋的接口给用户程序使用,而是因为内核处于最底层,不能对上层应用场景的具体要求做过多的假设。比如除了ptmalloc,还有google开发的TCMalloc等其它内存管理库,它们对内存利用率、分配性能、最佳适合场景的权衡都不一样,所以内核如果在最底层偏向任何一方,就会在上层损失灵活性,因此内核的接口就只能提供最基础、最原始功能。内核是按照段或页为单位进行内存管理的,其中,段式内存管理目前几乎已经淘汰了,因此可以认为内核的接口,必须按页进行分配/释放(这是由CPU的硬件特性决定的,这样设计的好处是,记录1对虚拟页面地址和物理页面地址的映射关系,就为4K个地址都建立了映射),所以,如果用户程序直接使用系统调用,哪怕只分配1个字节,也会得到4K大小的内存,如果希望尽可能的利用剩下的(4K-1)空间,需要用户程序自己实现逻辑进行控制,可以认为glibc正是为用户程序提供一套这样的接口,glibc按chunk为单位对内存进行再次划分,最小chunk只有16字节。
    另外,glibc会将应用程序已经释放的内存,准确说,只是业务层已经不需要的内存,仍然维持在用户态,当业务层再次需要内存时,再将它们返回给业务层,相比每次直接使用系统调用分配/释放,可以避免用户态和内核态之间频繁切换,从而提高程序的性能。可以将glibc理解为业务层与内核之间的缓存,当缓存达到一定阈值后,仍然会通过系统调用最终释放(它的释放时机始终存在,跟由内存泄漏是两回事),业务层释放的内存不管是内核“保管”,还是glibc“保管”,从逻辑意义上来讲,这块内存肯定不会跟正使用内存冲突了(否则就是业务层本身有bug),所以再次返回给业务层,也是没有问题的。

3. glibc内存管理的实现

  这块内容是参考《Glibc内存管理--Ptmalloc2源代码分析.pdf》学习的,这份pdf文件总共129页,分析过程非常详细、深刻,为了防止遗忘,我整理了一个主要过程出来,并且为有些部分添加了配图和个人的理解。

  • 进程空间布局

    32位高版本内核采用的内存布局,是mmap区域的最高地址固定,向下增长,而64位内存布局和32位经典内存布局是同一种布局,都是mmap区域的最低地址固定,向上增长,更细节的内容可以参考:https://www.iteye.com/blog/mqzhuang-901602
    需要知道的是,内核就是从heap区域和mmap区域,分配虚拟空间给用户程序,其中,heap底部位置始终固定不动,从heap区域分配就是抬高heap顶部的位置,因此只可能存在一个heap已分配空间,而从mmap区域分配,可以取mmap区域中任意一块空闲的区间,因此可以存在多个mmap已分配空间,并且每个分配空间的起始和结束位置,是固定不动的。另外,heap和mmap区域的分配/释放接口(系统调用)分别为skb()、mmap()/munmap(),参数中表示分配位置或分配大小的值,必须按页对齐。
  • Arena
    (下图引用于:https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/)

    glibc介于内核与业务层之间,所以它的任务就是,通过内核分配Arena,再从Arena上切割Chunk,提供给业务层,并对所有的Arena和Chunk进行管理。
    • Main Arena
      Main Arena对应heap已分配区域,所以有且只有一个,并且它的Top Chunk顶部位置,是随着heap已分配区域的顶部变化的。其中的Allocated Chunk,表示正在被业务层使用的空间,Free Chunk表示空闲空间,比如业务层使用完释放掉的空间,除此之外还有其它信息需要记录,都是通过一个malloc_state结构的全局变量进行管理的。
    • Thread Arena
      Thread Arena对应一个或多个mmap已分配区域,和Main Arena不同,Thread Arena可以有多个,每个Thread Arena也可以包含多个mmap已分配区域,并且它们的Top Chunk顶端都不会变动。另外,Thread Arena的malloc_state管理结构,直接嵌套在它包含的首个mmap已分配区域中,并且其中的每个mmap已分配区域的开始位置,都会有一个heap_info结构(这是因为mmap分配区域需要一点额外的管理信息,比如这块区域中有多少部分已经映射为可读写区域了,以及,当Thread Arena包含多个mmap已分配区域时,还需要有链表结点,将它们链在一起)。
      • 问题1:为什么需要Thread Arena?
      • 问题2:Thread Arena可以扩充,为什么还需要多个Thread Arena?
        问题1(Main Arena也是可以扩充的)和问题2实际上是一样的,都可以转换为:为什么需要多个Arena?原因其实很简单,Thread Arena是为了避免或减小多线程之间的竞争,额外创建的Arena,这也是“Thread Arena”这个名称的来历,所以Thread Arena和Main Arena在使用时,是平等的,主线程可以用Thread Arena,子线程也可以用Main Arena,千万不能望文生义的认为,主线程只能使用Main Arena,或者Main Arena只提供给主线程专用。
    • malloc_state结构
      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
      struct malloc_state {
        /* Serialize access.  */
        mutex_t mutex;
        /* Flags (formerly in max_fast).  */
        int flags;
      #if THREAD_STATS
        /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
        long stat_lock_direct, stat_lock_loop, stat_lock_wait;
      #endif
        /* 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;
      #ifdef PER_THREAD
        /* Linked list for free arenas.  */
        struct malloc_state *next_free;
      #endif
        /* Memory allocated from the system in this arena.  */
        INTERNAL_SIZE_T system_mem;
        INTERNAL_SIZE_T max_system_mem;
      };
      malloc_state结构用于记录Arena管理信息:
      • mutex:防止不同线程同时使用同一个Arena;
      • top:描述Arena的Top Chunk信息;
      • next:将进程的所有Arena链成一条链表;
      • next_free:将当前未被任何线程使用的Arena链成一条链表;
      • system_mem:Arena中已分配给业务层的空间大小;
      • max_system_mem:Arena最多能分配给业务层的空间大小,max_system_mem-system_mem即为Arena中空闲空间的大小;
      • 其余主要成员,通过后续内容一一介绍。
    • heap_info结构
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      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;
      • ar_ptr:所属的Arena;
      • prev:与同一Arena中的其它heap链在一起;
      • size:heap大小;
      • mprotect_size:还未设置可读写属性的区域大小;
      • pad:使heap_info对象按MALLOC_ALIGNMENT对齐(其实是为了让紧挨着的Chunk起始地址按MALLOC_ALIGNMENT对齐),由于pad以上的成员大小加起来已经满足对齐要求,所以pad数组的大小为0即可(不管32位还是64位环境下,-6 * SIZE_SZ & MALLOC_ALIGN_MASK算出来都是0,这里还没有理解为什么要写的这么奇怪)。
  • Chunk
    说到这里,已经很容易明白,glibc与内核之间,是按Arena(对于Thread Arena,是其中包含的heap)为单位分配/释放,glibc与业务层之间,是按Chunk为单位分配/释放。
    • 每个Chunk头部,包含一个malloc_chunk管理结构
      1
      2
      3
      4
      5
      6
      7
      8
      9
      struct malloc_chunk {
        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. */
        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;
      };
      • prev_size:紧挨着当前Chunk的上个Chunk的大小;
      • size:最低3位为属性位(稍后说明),属性位清零即为当前Chunk的大小(包括管理信息部分,即以下结构说明图中橙色、蓝色、灰色空间的大小);
      • fd:当前Chunk如果是Free Chunk,会与其它Free Chunk链在一起,fd表示链在当前Chunk前面的Free Chunk;
      • bk:当前Chunk如果是Free Chunk,会与其它Free Chunk链在一起,bk表示链在当前Chunk后面的Free Chunk;
      • fd_nextsize:后面说明;
      • bk_nextsize:后面说明。
    • 结构说明
      • 空间复用
        • 这个结构并不是从当前Chunk的头部开始,而是从上个Chunk的最后4个字节处开始。原因:只有在释放当前Chunk,并且上个Chunk为Free Chunk,从而需要合并当前Chunk和上个Chunk的时候,才需要根据prev_size找上个Chunk,而既然上个Chunk这时为Free Chunk,所以自然可以使用上个Chunk自己的空间记录prev_size,这样当前Chunk就可以少花4字节记录空间,进一步而言,业务层就可以从当前Chunk中多使用4个字节。
        • fd和bk只在当前Chunk是Free Chunk时有意义,当前Chunk如果为Allocated Chunk,fd和bk所在的空间,会作为user data(业务层使用空间)的一部分。原因:fd,bk只为了方便搜索和组织不同大小的Free Chunk(如果不考虑性能,直接从Arena中也能找出所有的Free Chunk),所以也只有Free Chunk才需要fd,bk,而既然已经是Free Chunk了,自然可以使用user data记录fd,bk。也正是由于Free Chunk必须记录size,fd,bk,以及为下个Chunk提供记录prev_size的空间,所以Chunk最小大小为16字节。
        • fd_nextsize和bk_nextsize,只在当前Chunk是Free Chunk,并且大小≥512字节时有意义。首先,和fd,bk一样,Free Chunk的fd_nextsize和bk_nextsize,复用了Allocated Chunk的user data空间;另外,chunk的大小是按8字节对齐的,所以[16,512)字节区间的Chunk,只有62种大小,每种大小都有一一对应的链表头,而≥512的Free Chunk,不同大小是要链在同一链表中的,fd_nextsize和bk_nextsize是为了提高插入排序的性能,相同大小的多个Free Chunk,只用比较一次。
    • 标志位
      • P:表示上个Chunk是否空闲
        • 当前Chunk本身是否空闲,可以通过当前Chunk的size,找到下一个Chunk,进而根据下一个Chunk的P标志位进行判断;
        • P标志用于判断prev_size是否有意义(如果P标志用于表示当前Chunk自己是否空闲,就矛盾了:想知道prev_size是否有意义,必须先用prev_size计算上个Chunk的位置,进而才能获取P标志位的值)。
      • M:表示是否直接从mmap区域分配
        这个标志容易理解错,虽然Thread Arena是从mmap区域分配的,但Thread Arena上的Chunk,并不设置M标志位,所以M标志位的含义,其实可以换个说法,即表示是否从Arena分配。相应的,M=1时,释放必须通过munmap()直接归还到mmap区域。
      • A:表示是否从Main Arena分配
  • Bins
    为避免混淆,在此声明一下:通过我在学习过程中看到的一些文档,都认为Bins = unsorted bin + small bins + large bins,而Fast bins不属于Bins,bin也是指Bins中的某个bin,而跟Fast bins无关。

    Fast bins和Bins其实就是两个数组,数组中的元素都是用于悬挂Free Chunk的链表头。Fast bins用于存放大小为16~80字节的Free Chunk(默认为16~64字节,业务层可以通过mallopt()函数设置Fast bins有效部分的大小),small bins用于存放大小为16~504字节的Free Chunk,large bins用于存放≥512字节的Free Chunk。
    • bin结构

      Fast bins中都是单向链表头,而bin都是双向链表头,需要说一下的是,glibc代码对bin的使用方式有点特别,比如使用bin1的时候,它是通过bin_at(1),将bin0+bin1视为一个malloc_chunk结构,然后通过这个结构,使用bin1中的fd,bk成员。
    • large bins
      bins中第一个bin不使用、第二个bin作为unsorted bin,剩余部分从整体上看划分成了7份,分别包含64、32、16、8、4、2、1个bin,前面6份都包含多个bin,相邻两个bin允许存放的最小Free Chunk的公差分别为8、8^2、8^3、8^4、8^5、8^6,由于Chunk大小最小也相差8字节,所以第1份,即small bins中的每个bin,存放的Free Chunk,大小肯定都是相等的,而后面6份,即large bins中的每个bin,存放的Free Chunk,大小都是一个区间。
      1
      2
      3
      4
      5
      6
      7
      #define largebin_index_32(sz)                                                \
      (((((unsigned long)(sz)) >>  6) <= 38)?  56 + (((unsigned long)(sz)) >>  6): \
       ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
       ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
       ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
       ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
                      126)
      通过上述规律,再来看largebin_index_32()这个宏的逻辑,就不至于摸不清东南西北了。既然执行到这个宏,说明sz肯定是属于large bins范围的,宏里面就是要进一步确定,sz属于6个部分中的哪一个,然后根据相应的公差最终计算所属bin的下标值。
      • 右移6、9、12、15、18,分别表示除以不同部分的公差8^2、8^3、8^4、8^5、8^6;
      • small bins中有8个8^2,large bins第1部分有32个8^2,所以除以8^2如果达到40,那必须在第2部分的范围,但代码中是38,可能是由于除法计算会损失1,下标也要减1;
      • large bins的下标从64开始,但是small bins有8个8^2,所以large bins第1部分范围中的大小,除以8^2,至少是8,所以是基于56相加。
    • “Bins缓存”
      Fast bins可以理解为small bins部分区间的缓存(16~64/80),并且是“一级缓存”,unsorted bin可以理解为整个small bins和large bins的缓存,并且是“二级缓存”。
  • malloc()、free()流程
    详细过程,建议参考这里直接借个图,引用于:https://www.cnblogs.com/unr4v31/p/14446412.html

参考

《Glibc内存管理--ptmalloc2源代码分析》博客系列:https://www.iteye.com/blog/user/mqzhuang


看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

收藏
点赞4
打赏
分享
最新回复 (4)
雪    币: 1371
活跃值: 活跃值 (1094)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
pukrquq 活跃值 1 2022-4-4 14:58
2
0
综合您这篇文章,搜索了两天的资料,关于内存分布的问题终于懂了,感激不尽。
雪    币: 1371
活跃值: 活跃值 (1094)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
pukrquq 活跃值 1 2022-4-4 14:59
3
0
pukrquq 综合您这篇文章,搜索了两天的资料,关于内存分布的问题终于懂了,感激不尽。
在学house of mind,以前关于arena的各种问题在这两天得到了解答
雪    币: 1125
活跃值: 活跃值 (1186)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
fengyunabc 活跃值 1 2022-4-4 18:10
4
0
感谢分享!
雪    币: 3701
活跃值: 活跃值 (4597)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
jmpcall 活跃值 3 2022-4-6 09:50
5
0
pukrquq 在学house of mind,以前关于arena的各种问题在这两天得到了解答[em_13]
这将是载入史册的两天
游客
登录 | 注册 方可回帖
返回