glibc内存管理ptmalloc源代码分析读书笔记

1 基础知识

1.1 Linux 进程内存布局

Linux 系统加载ELF文件时，会调用Loader将ELF文件中的各个段一次载入到某一地址开始的空间中。

首先被载入的是.text 段（代码段），然后是.data段，最后是.bss段。

以32位系统为例，.text 段会被加载到0x804800，即128M处。程序能访问的最大的地址为 0xBFFFFFFF，也就是到3G地址处，3G以上的1G空间是内核使用的，应用程序不可以直 接访问。

.bss段至栈之间的内存是空闲的，被分为heap区域和mmap映射区域。

Heap 和 mmap 区域都可以供用户自由使用，但是它在一开始并没有映射到相应的物理地址，是不可访问的。在向内核请求分配该空间之前，对这个空间的访问会导致segmentation fault。

用户程序可以直接使用系统调用来管理 heap 和 mmap 映射区域，但更多的时候程序都是使用 C 语言提供的 malloc()和 free()函数来动态的分配和释放内存。Stack区域是唯一不需要映射，用户却可以访问的内存区域，这也是利用堆栈溢出进行攻击的基础。

• X86 32位平台下 Linux 经典进程内存布局

  

  上图是 Linux 2.6.7 以前的默认进程内存布局形式，mmap 区域与栈区域相对增 长，这意味着堆只有 1GB 的虚拟地址空间可以使用，继续增长就会进入 mmap 映射区域。

  这是由于 32 模式地址空间限制造成的，所以内核引入了另一种虚 拟地址空间的布局形式，将在后面介绍。但对于 64 位系统，提供了巨大的虚拟地址空间， 这种布局就相当好。

• X86 32位平台下 Linux默认进程内存布局

  

  这是Linux 2.6.7之后引入的内存布局，区别与前一幅图的是mmap区域向下扩展不再受到0x40000000的限制，而是和heap区域相对扩展，直到耗尽为止。

• X86 64位平台下 Linux 进程内存布局（未开启PIE）

  64位模式下类似32位模式的经典布局，text段 的起始地址为 0x0000000000400000（开启PIE时起始地址为0x555555554000），heap紧接着 BSS 段向上增长，mmap 映射区域开始位置一般设为 TASK_SIZE/3。

  TASK_SIZE的宏定义：

  #define TASK_SIZE_MAX
  ((1UL << 47) - PAGE_SIZE)
  #define TASK_SIZE
  (test_thread_flag(TIF_IA32) ? \
  IA32_PAGE_OFFSET : TASK_SIZE_MAX)
  #define STACK_TOP TASK_SIZE
  #define TASK_UNMAPPED_BASE (PAGE_ALIGN(TASK_SIZE / 3))
  

  

  进程的栈和 mmap 映射区域并不是从一个固定地址开始，并且每次启动时的值都不一样，这是程序在启动时随机改变这些值的设置，使得使用缓冲区溢出进行攻击更加困难。

  当然也可以让进程的栈和 mmap 映射区域从一个固定位置开始，只需要设置全局变量 randomize_va_space值 为0 ， 这 个 变 量 默 认 值 为1 。

  用 户 可 以 通 过 设 置/proc/sys/kernel/randomize_va_space 来停用该特性，也可以用如下命令： sudo sysctl -w kernel.randomize_va_space=0

• X86 64位平台下 Linux 进程内存布局（开启PIE）

  未开启PIE时的内存布局：

  

  开启PIE时的内存布局：

  

  对比上面两张图片，可以看到开启PIE时text段和heap区域的起始地址均发生了变化。

  各个段的说明（ 深入浅出 OS 的内存管理 | 阿日哥的向量空间 (arg.pub) ）：

  • 保留区：位于虚拟地址空间的最底部，未赋予物理地址。任何对它的引用都是非法的，程序中的空指针（NULL）指向的就是这块内存地址。
  • .text 段：代码段也称正文段或文本段，用于存放程序的执行代码 (即 CPU 执行的机器指令），代码段一般情况下是只读的，这是对执行代码的一种保护机制。
  • .data 段：数据段通常用于存放程序中已初始化且初值不为 0 的全局变量和静态变量。数 据段属于静态内存分配 (静态存储区)，可读可写。
  • .bss 段：未初始化以及初始为 0 的全局变量和静态变量，操作系统会将这些未初始化的变量初始化为 0。
  • 堆（heap）：用于存放进程运行时动态分配的内存。
  • • 堆中内容是匿名的，不能按名字直接访问，只能通过指针间接访问。
    • 堆向高地址扩展（即 “向上生长”），是不连续的内存区域。这是由于系统用链表来存储空闲 内存地址，自然不连续，而链表从低地址向高地址遍历。
  • 内存映射区（mmap）：作为内存映射区加载磁盘文件，或者加载程序运作过程中需要调 用的动态库。
  • 栈（stack）：存储函数内部声明的非静态局部变量，函数参数，函数返回地址等信息，栈内存由编译器自动分配释放。栈和堆相向而生，地址” 向下生长”，分配的内存是连续的。

1.2 操作系统内存分配的相关函数

堆区域和mmap区域都是可以提供给用户程序使用的虚拟内存空间，对于堆空间的操作，由 sbrk()函数 进行，对于mmap区域的操作，由 mmap()和munmap()函数进行。

2 内存管理概述

主流的内存管理方式由以下几种：

• C 风格的内存管理程序
• 池式内存管理
• 引用计数
• 垃圾收集

2.1 Ptmalloc 内存管理概述

2.1.1 简介

Linux 中 malloc 的早期版本是由 Doug Lea 实现的，它有一个重要问题就是在并行处理时多个线程共享进程的内存空间，各线程可能并发请求内存，在这种情况下应该如何保证分配

和回收的正确和高效。Wolfram Gloger 在 Doug Lea 的基础上改进使得 Glibc 的 malloc 可以支持多线程——ptmalloc，在glibc-2.3.x.中已经集成了ptmalloc2，这就是我们平时使用的malloc，目前 ptmalloc 的最新版本 ptmalloc3。ptmalloc2 的性能略微比 ptmalloc3 要高一点点。

2.1.2 内存管理的设计假设

Ptmalloc 在设计时折中了高效率，高空间利用率，高可用性等设计目标。在其实现代码 中，隐藏着内存管理中的一些设计假设，由于某些设计假设，导致了在某些情况下 ptmalloc 的行为很诡异。这些设计假设包括：

Ptmalloc 在设计时折中了高效率，高空间利用率，高可用性等设计目标。在其实现代码 中，隐藏着内存管理中的一些设计假设，由于某些设计假设，导致了在某些情况下 ptmalloc 的行为很诡异。这些设计假设包括：

1. 具有长生命周期的大内存分配使用 mmap。
2. 特别大的内存分配总是使用 mmap。
3. 具有短生命周期的内存分配使用 brk，因为用 mmap 映射匿名页，当发生缺页异常时，linux 内核为缺页分配一个新物理页，并将该物理页清 0，一个 mmap 的内存块需要映射多个物理页，导致多次清 0 操作，很浪费系统资源，所以引入了 mmap分配阈值动态调整机制，保证在必要的情况下才使用 mmap 分配内存。
4. 尽量只缓存临时使用的空闲小内存块，对大内存块或是长生命周期的大内存块在释放时都直接归还给操作系统。
5. 对空闲的小内存块只会在 malloc 和 free 的时候进行合并，free 时空闲内存块可能放入 pool 中，不一定归还给操作系统。
6. 收缩堆的条件是当前 free 的块大小加上前后能合并 chunk 的大小大于 64KB、，并且堆顶的大小达到阈值，才有可能收缩堆，把堆最顶端的空闲内存返回给操作系统。
7. 需要保持长期存储的程序不适合用 ptmalloc 来管理内存。
8. 为了支持多线程，多个线程可以从同一个分配区（arena）中分配内存，ptmalloc假设线程 A 释放掉一块内存后，线程 B 会申请类似大小的内存，但是 A 释放的内存跟 B 需要的内存不一定完全相等，可能有一个小的误差，就需要不停地对内存块作切割和合并，这个过程中可能产生内存碎片。

2.1.3 内存管理数据结构概述

2.1.3.1 main_arena 与 non_main_arena

在 Doug Lea 实现的内存分配器中只有一个主分配区（main arena），每次分配内存都必须对主分配区加锁，分配完成后释放锁，在 SMP 多线程环境下，对主分配区的锁的争用很激烈，严重影响了 malloc 的分配效率。于是 Wolfram Gloger 在 Doug Lea 的基础上改进使得Glibc 的 malloc 可以支持多线程，增加了非主分配区（non main arena）支持，主分配区与非主分配区用环形链表进行管理。每一个分配区利用互斥锁（mutex）使线程对于该分配区的访问互斥。

每个进程只有一个主分配区，但可能存在多个非主分配区，ptmalloc 根据系统对分配区的争用情况动态增加非主分配区的数量，分配区的数量一旦增加，就不会再减少了。主分配区可以访问进程的 heap 区域和 mmap 映射区域，也就是说主分配区可以使用 sbrk 和 mmap向操作系统申请虚拟内存。而非主分配区只能访问进程的 mmap 映射区域，非主分配区每次使用 mmap()向操作系统“批发”HEAP_MAX_SIZE（32 位系统上默认为 1MB，64 位系统默认为 64MB）大小的虚拟内存，当用户向非主分配区请求分配内存时再切割成小块“零售”出去，毕竟系统调用是相对低效的，直接从用户空间分配内存快多了。所以 ptmalloc 在必要的情况下才会调用 mmap()函数向操作系统申请虚拟内存。

主分配区可以访问 heap 区域，如果用户不调用 brk()或是 sbrk()函数，分配程序就可以保证分配到连续的虚拟地址空间，因为每个进程只有一个主分配区使用 sbrk()分配 heap 区域的虚拟内存。内核对 brk 的实现可以看着是 mmap 的一个精简版，相对高效一些。如果主分配区的内存是通过 mmap()向系统分配的，当 free 该内存时，主分配区会直接调用 munmap()将该内存归还给系统。

当某一线程需要调用 malloc()分配内存空间时，该线程先查看线程私有变量中是否已经存在一个分配区，如果存在，尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，如果失败，该线程搜索循环链表试图获得一个没有加锁的分配区。如果所有的分配区都已经加锁，那么 malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁，然后使用该分配区进行分配内存操作。在释放操作中，线程同样试图获得待释放内存块所在分配区的锁，如果该分配区正在被别的线程使用，则需要等待直到其他线程释放该分配区的互斥锁之后才可以进行释放操作。

2.1.3.2 chunk 的组织

通过malloc()函数申请的内存空间需要一定的数据结构来保存其信息，即chunk。

1. chunk的格式

   free chunk的状态如下：

   /*    
       Free chunks are stored in circular doubly-linked lists, and look like this:
       chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             Size of previous chunk, if unallocated (P clear)  |
               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       `head:' |             Size of chunk, in bytes                     |A|0|P|
         mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             Forward pointer to next chunk in list             |
               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             Back pointer to previous chunk in list            |
               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             Unused space (may be 0 bytes long)                .
               .                                                               .
               .                                                               |
   nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       `foot:' |             Size of chunk, in bytes                           |
               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             Size of next chunk, in bytes                |A|0|0|
               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       The P (PREV_INUSE) bit, stored in the unused low-order bit of the
       chunk size (which is always a multiple of two words), is an in-use
       bit for the *previous* chunk.  If that bit is *clear*, then the
       word before the current chunk size contains the previous chunk
       size, and can be used to find the front of the previous chunk.
       The very first chunk allocated always has this bit set,
       preventing access to non-existent (or non-owned) memory. If
       prev_inuse is set for any given chunk, then you CANNOT determine
       the size of the previous chunk, and might even get a memory
       addressing fault when trying to do so.
       The A (NON_MAIN_ARENA) bit is cleared for chunks on the initial,
       main arena, described by the main_arena variable.  When additional
       threads are spawned, each thread receives its own arena (up to a
       configurable limit, after which arenas are reused for multiple
       threads), and the chunks in these arenas have the A bit set.  To
       find the arena for a chunk on such a non-main arena, heap_for_ptr
       performs a bit mask operation and indirection through the ar_ptr
       member of the per-heap header heap_info (see arena.c).
       Note that the `foot' of the current chunk is actually represented
       as the prev_size of the NEXT chunk. This makes it easier to
       deal with alignments etc but can be very confusing when trying
       to extend or adapt this code.
   
       The three exceptions to all this are:
        1. The special chunk `top' doesn't bother using the
           trailing size field since there is no next contiguous chunk
           that would have to index off it. After initialization, `top'
           is forced to always exist.  If it would become less than
           MINSIZE bytes long, it is replenished.
        2. Chunks allocated via mmap, which have the second-lowest-order
           bit M (IS_MMAPPED) set in their size fields.  Because they are
           allocated one-by-one, each must contain its own trailing size
           field.  If the M bit is set, the other bits are ignored
           (because mmapped chunks are neither in an arena, nor adjacent
           to a freed chunk).  The M bit is also used for chunks which
           originally came from a dumped heap via malloc_set_state in
           hooks.c.
        3. Chunks in fastbins are treated as allocated chunks from the
           point of view of the chunk allocator.  They are consolidated
           with their neighbors only in bulk, in malloc_consolidate.
   */
   

   未被free的chunk（allocated chunk/malloced chunk）的格式如下：

   /*
   An allocated chunk looks like this:
   chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             Size of previous chunk, if unallocated (P clear)  |
               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             Size of chunk, in bytes                     |A|M|P|
         mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             User data starts here...                          .
               .                                                               .
               .             (malloc_usable_size() bytes)                      .
               .                                                               |
   nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             (size of chunk, but used for application data)    |
               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
               |             Size of next chunk, in bytes                |A|0|1|
               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       Where "chunk" is the front of the chunk for the purpose of most of
       the malloc code, but "mem" is the pointer that is returned to the
       user.  "Nextchunk" is the beginning of the next contiguous chunk.
       Chunks always begin on even word boundaries, so the mem portion
       (which is returned to the user) is also on an even word boundary, and
       thus at least double-word aligned.
   */
   

   chunk中除供用户使用的内存区域（mem）外，还有一些辅助信息。

   在chunk的头部保存着前一个chunk和当前chunk的大小信息，因此chunk的大小有最小值，至少需要这两个字段的大小（size_t）之和的空间。

   另外由于内存对齐的缘故，32位下malloc的返回地址需要8字节对齐（long long长度为8字节）。

   综上，chunk的大小为8的倍数，因此我们可以用size of chunk的低3位保存其他信息。即chunk的分配状态A、是否为mmap的chunk M以及前一个chunk的分配状态P。

   此外，top chunk不存在prev_size字段，因为它没有前一个chunk。

   需要注意，堆是从低地址向高地址增长的，我们说的前一个/上一个是指较低地址处的chunk，后一个/下一个是指较高地址处的chunk

2. chunk的空间复用

   对于allocated chunk而言，他的下一个chunk的prev_size字段是没有意义的，该字段的空间会被allocated chunk供用户保存数据使用。

   这是因为glibc使用了边界标记法（ CSAPP Malloc Lab#如何保存内存块的信息 ）。

   /*
   malloc_chunk details:
       (The following includes lightly edited explanations by Colin Plumb.)
       Chunks of memory are maintained using a `boundary tag' method as
       described in e.g., Knuth or Standish.  (See the paper by Paul
       Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
       survey of such techniques.)  Sizes of free chunks are stored both
       in the front of each chunk and at the end.  This makes
       consolidating fragmented chunks into bigger chunks very fast.  The
       size fields also hold bits representing whether chunks are free or
       in use.
   */
   

   不过与传统的边界标记法不同，其不是在chunk尾部保存当前chunk的大小，而是在chunk的头部保存前一个chunk的大小，两种方法都可以快速地帮助我们定位到前一个chunk。

   借用CSAPP中的图片来进行说明，chunk的结构如下图：

   

   与glibc的实现稍有不同，这里的chunk没有prev_inuse位，这样我们在向前合并时就必须借助前一个chunk块的脚部来定位到前一个chunk，从而判断其是否正在被使用。这样脚部在正在被使用的chunk中也必须存在，否则我们无法正常向前合并。

   glibc添加了prev_inuse位，这样我们直接通过prev_inuse位即可判断前一个堆块是否空闲，如果不是空闲堆块，我们不需要定位到那个堆块来进行合并，这样非空闲块脚部的空间就可以给用户使用了。

   剩下唯一的区别就是glibc把脚部放在了开始，而且其保存的是上一个chunk的大小，其实实际上是没有什么区别的，如果上一个chunk正在使用中，那么我们也不需要关心当前chunk的prev size字段，可以将其借给上一个chunk来当作用户空间来使用。

2.1.3.3 free chunk的容器

1. bins

   用户通过free()释放的内存并不会马上归还给操作系统，实际上也可能无法归还：我们通过sbrk()来增大堆的大小，其中不仅有free chunk，还有allocated chunk，如果我们要收缩堆，那么我们必须处理其中的allocated chunk。