Glibc内存管理笔记

0x0 胡话

计划：

  • Linux 下的内存管理：Glibc
  • Windows 下的内存管理：HeapApi
  • Double Free
  • UAF

windows 闭源，所以从Linux的内存管理开始学习

0x1 这篇笔记在写什么鬼

这篇文章主要目的是，记录我在学习Glibc内存管理的过程中阅读的优秀参考文章，遇到的问题和对应的自主解答（见经典自问自答环节）。对读者的作用仅仅是推荐一些学习这部分知识的优秀参考文章，顶多再参考下我遇到的问题。并不是详细讲解Glibc的源码，也没有对Glibc内存管理策略的系统性描述。为什么不写？因为不想重复造轮，我写的怎么可能超过拥有多年内核层经验的前辈。

Glibc就是GNU C库，是GNU计划所实现的C标准库。尽管其名字中带有“C库”，但它现在也直接支持C++（以及间接支持其他编程语言）。它为GNU系统，GNU/Linux系统和一些其他的类Unix系统提供了系统核心库。这些库提供了关键的API，包括ISO C11、POSIX.1-2008和BSD所规定的API和一些底层API，包括open、read、write、malloc、printf、getaddrinfo、dlopen、pthread_create、crypt、login、exit等。

ref: GNU C库 - 维基百科，自由的百科全书 (wikipedia.org)

像这种底层内核源码库，乍一看感觉很难读懂，实际上就是不懂的知识点太多了，使用了大量的自定义的数据结构，眼花缭乱的宏定义，让人一下子抓不住要点，理解不了整体框架。就好像刚学完高中英语4500词，给我一篇二进制学术论文，没见过的单词太多了，当然理解不了文章。所以说不要着急，从别人的分析文章开始看，最后读一读源码，这样的过程多反复进行几遍就能对它有个很好的理解了。我是属于天资愚钝的那类人😥，这种源码阅读一般都要耗费个把月，但是沃觉得很值，也是必要的，毕竟基本功要打扎实。

0x2 知识点?

chunk 相关

ref: (22条消息) linux堆内存管理malloc分析（3）_dongyu_1989的博客-CSDN博客

文章内容：

  • samll bins & large bins 中chunk的申请与释放

  • large bins中每个双向循环链表chunk size的大小区间

  • 给出一张较为详细且清晰的Bins snapshot

  • Bins的初始化

img

这是一个系列，感觉这个作者写的比较易懂，且语病相对较少，可以读一读同系列其他文章。

核心结构体

malloc_state

每个分配区是struct malloc_state的一个实例，ptmalloc使用malloc_state来管理分配区.

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* 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.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

malloc_par

参数管理使用struct malloc_par，全局拥有一个唯一的malloc_par实例.

struct malloc_par
{
  /* Tunable parameters */
  unsigned long trim_threshold;
  INTERNAL_SIZE_T top_pad;
  INTERNAL_SIZE_T mmap_threshold;
  INTERNAL_SIZE_T arena_test;
  INTERNAL_SIZE_T arena_max;

  /* Memory map support */
  int n_mmaps;
  int n_mmaps_max;
  int max_n_mmaps;
  /* the mmap_threshold is dynamic, until the user sets
     it manually, at which point we need to disable any
     dynamic behavior. */
  int no_dyn_threshold;

  /* Statistics */
  INTERNAL_SIZE_T mmapped_mem;
  INTERNAL_SIZE_T max_mmapped_mem;

  /* First address handed out by MORECORE/sbrk.  */
  char *sbrk_base;

#if USE_TCACHE
  /* Maximum number of buckets to use.  */
  size_t tcache_bins;
  size_t tcache_max_bytes;
  /* Maximum number of chunks in each bucket.  */
  size_t tcache_count;
  /* Maximum number of chunks to remove from the unsorted list, which
     aren't used to prefill the cache.  */
  size_t tcache_unsorted_limit;
#endif
};

malloc_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;
};

heap_info

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;

0x-1经典自问自答环节

Chunk 大小的计算公式？

  • 一个使用中的chunk的大小：in_use_size = (用户请求大小+2*SIZE_SZ-SIZE_SZ) align to 8B，准确来说是malloc分配的bins上的chunk

    参见：glibc/malloc.c at master · lattera/glibc (github.com)

    mmap分配时没有相邻的上下chunk，此时in_use_size = (用户请求大小+2*SIZE_SZ) align to 8B

  • 空闲chunk至少需要4个SIZE_SZ的大小，用于存储prev_size，size，fd和bk

    参见：glibc/malloc.c at master · lattera/glibc (github.com)

  • 由于空闲chunk和使用中的chunk使用同一块空间，所以肯定要取两者最大的一个作为最终的分配空间：chunk_size = max(in_use_size, 16)

为什么使用中的Chunk可以占用下一个chunk的prev_size域？

prev_size字段虽然在当前chunk块结构体内，记录的却是前一个邻接chunk块的信息，这样做的好处，或者说目的，就是我们通过本块chunk结构体就可以直接获取到前一chunk块的地址，从而方便做进一步的处理操作。相对的，当前chunk块的foot信息就存在于下一个邻接chunk块的结构体内。字段prev_size记录的信息，有两种情况：

1）如果前一个邻接chunk块空闲，那么当前chunk块结构体内的prev_size字段记录的是前一个邻接chunk块的大小。这就是由当前chunk指针获得前一个空闲chunk地址的依据。宏prev_chunk§就是依赖这个假设实现的。

2）如果前一个邻接chunk在使用中，则当前chunk的prev_size的空间被前一个chunk借用中，其中的值是前一个chunk的内存内容，对当前chunk没有任何意义。此时上一个chunk不能用作分配，管理器不需要获取上一个chunk的地址，所以这个prev_size也就没有用了。字段size记录了本chunk的大小，无论下一个chunk是空闲状态或是被使用状态，都可以通过本chunk的地址加上本chunk的大小，得到下一个chunk的地址，由于size的低3个bit记录了控制信息，需要屏蔽掉这些控制信息，取出实际的size在进行计算下一个chunk地址，这是next_chunk§的实现原理。

/* Ptr to previous physical malloc_chunk.  Only valid if !prev_inuse (P).  */
#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))
/* Ptr to next physical malloc_chunk. */
#define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))

宏chunksize§用于获得chunk的实际大小，需要屏蔽掉size中的控制信息。

/* Get size, ignoring use bits */
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))

宏chunk_at_offset(p, s)将p+s的地址强制看作一个chunk。

/* Treat space at ptr + offset as a chunk */
#define chunk_at_offset(p, s)  ((mchunkptr) (((char *) (p)) + (s)))

为什么Chunk的size域低三位可以复用？

chunk在分割时总是以地址对齐，默认是8字节对齐，对齐值可以自定义，但是必须比默认值大且是2n2^n，这样的话低三位总是0，就可以复用。

  • 以第0位作为P状态位，标记前一chunk块是否在使用中，为1表示使用，为0表示空闲。

  • 以第1位作为M状态位，标记本chunk块是否是使用mmap()直接从进程的mmap映射区域分配的，为1表示是，为0表示否。

  • 以第2位作为A状态位，标记本chunk是否属于非主分配区，为1表示是，为0表示否。

Chunk Bins 如何初始化？

分配区main_arena初始化函数:

static void
malloc_init_state (mstate av)//mstate == malloc_state
{
  int i;
  mbinptr bin;

  /* Establish circular links for normal bins */
  for (i = 1; i < NBINS; ++i)
    {
      bin = bin_at (av, i);
      bin->fd = bin->bk = bin;
    }

#if MORECORE_CONTIGUOUS
  if (av != &main_arena)
#endif
  set_noncontiguous (av);//对于非主分配区 设置为分配非连续虚拟地址空间
  if (av == &main_arena)
    set_max_fast (DEFAULT_MXFAST);//设置fastbins中最大chunk大小
  atomic_store_relaxed (&av->have_fastchunks, false);//分配区中是否有fastchunk 初始化置非

  av->top = initial_top (av);
}

上述代码中bin_at(m, i)是取分配区的实例m中第i个bin:

typedef struct malloc_chunk *mbinptr;

/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			      \
             - offsetof (struct malloc_chunk, fd))
#define NONCONTIGUOUS_BIT     (2U)

#define contiguous(M)          (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M)       (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M)   ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M)      ((M)->flags &= ~NONCONTIGUOUS_BIT)

分配区的初始化函数默认分配区的实例av是全局静态变量或是已经将av中的所有字段都清0了。初始化函数做的工作比较简单，首先遍历所有的bins，初始化每个bin的空闲链表为空，即将bin的fb和bk都指向bin本身。由于av中所有字段默认为0，即默认分配连续的虚拟地址空间，但只有主分配区才能分配连续的虚拟地址空间，所以对于非主分配区，需要设置为分配非连续虚拟地址空间。如果初始化的是主分配区，需要设置fastbins中最大chunk大小，由于主分配区只有一个，并且一定是最先初始化，这就保证了对全局变量global_max_fast只初始化了一次，只要该全局变量的值非0，也就意味着主分配区初始化了。最后初始化top chunk.

分配区(arena)怎么理解？

并发条件下，main_arena引发的竞争将会成为限制程序性能的瓶颈所在，因此glibc采用了多arena机制，线程A分配内存时获取main_arena锁成功，将在main_arena所管理的内存中分配；此时线程B获取main_arena失败，glibc会新建一个arena1，此次内存分配从arena1中进行。
这种策略，一定程度上解决了多线程下竞争的问题；但是随着arena的增多，内存碎片出现的可能性也变大了。例如，main_arena中有10k、20k的空闲内存，线程B要获取20k的空闲内存，但是获取main_arena锁失败，导致留下20k的碎片，降低了内存使用率。

普通arena的内部结构:

普通arena结构

  1. 一个arena由多个Heap构成
  2. 每个Heap通过mmap获得，最大为1M，多个Heap间可能不相邻
  3. Heap由_heap_info结构体组织，Heap之间有struct _heap_info *prev指针指向前一个Heap
  4. 最上面的Heap，也有top chunk

每个Heap里面也是由chunk组成，使用和main_arena完全相同的管理方式管理空闲chunk。
arena使用malloc_state结构体描述，多个arena之间是通过struct malloc_state *next以链表连接的。如下图:

arena链表

ref: glibc内存管理那些事儿 - 简书 (jianshu.com)

main arena主分配区&non main arena 非主分配区（普通arena）如何区分？

主分配区&非主分配区

main_arena&non_main_arena

我猜应该是下面的定义：

1. Primary / Main memory:
Primary memory is the computer memory that is directly accessible by CPU. It is comprised of DRAM and provides the actual working space to the processor. It holds the data and instructions that the processor is currently working on.

2. Secondary Memory / Mass Storage:
The contents of the secondary memory first get transferred to the primary memory and then are accessed by the processor, this is because the processor does not directly interact with the secondary memory.

ref: Difference between Primary and Secondary Memory - GeeksforGeeks

区别：

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

ref: glibc内存管理ptmalloc源代码分析.pdf – 华庭（庄明强）

main arena和普通arena(non main arena)的区别

main_arena是为一个使用brk指针的arena，由于brk是堆顶指针，一个进程中只可能有一个，因此普通arena无法使用brk进行内存分配。普通arena建立在mmap的机制上，内存管理方式和main_arena类似，只有一点区别，普通arena只有在整个arena都空闲时，才会调用munmap把内存还给操作系统。

ref: glibc内存管理那些事儿 - 简书 (jianshu.com)

malloc中mmap和brk的区别

从操作系统角度来看，进程分配内存有两种方式，分别由两个系统调用完成：brk和mmap（不考虑共享内存）。

1、brk是将数据段(.data)的最高地址指针_edata往高地址推；

2、mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。

注意这两种方式分配的都是虚拟内存，如果在第一次访问已分配的虚拟内存时发生中断，则由OS负责分配物理内存.

ref: https://www.huaweicloud.com/articles/914992dae65b7f7c6635c93e10d3ae1c.html

ref: https://leviathan.vip/2019/01/13/mmap源码分析/

内存碎片出现的原因

top chunk不收缩，内存就无法归还给操作系统，导致内存碎片的出现.

推荐顺序阅读：

Glibc内存管理Ptmalloc2源代码分析华庭（庄明强）2011/4/17.pdf

glibc内存管理那些事儿 - 简书 (jianshu.com)

源码：

source code: glibc/malloc.c at master · lattera/glibc (github.com)

source code: glibc/arena.c at master · lattera/glibc (github.com)

附加参考：

linux_ptmalloc下malloc()的过程：有 ptmalloc 源码 - 安全客，安全资讯平台 (anquanke.com)

glibc malloc学习笔记之fastbin (seebug.org) #在Pwn题中fastbin的利用