Heap Exploitation-内存的分配

Heap Exploitation - _libc_malloc源码分析

堆初始化

堆初始化是在用户第一次申请内存时执行 malloc_consolidate 再执行 malloc_init_state 实现的。

malloc_consolidate函数是定义在malloc.c中的一个函数，用于将fastbin中空闲的chunk合并整理到 unsorted_bin 中以及进行初始化堆的工作。该函数是free的一个小的变体，专门用于处理fastbin中的空闲chunk，并且负责堆管理中的初始化工作。

malloc_state 的初始化操作由函数 malloc_init_state(av) 完成，该函数先初始化除 fastbins 之外的所有的bins，再初始化 fastbins，清空 fastbins。判断当前 malloc_state 结构体中的 fastbin 是否为空，如果为空就说明整个 malloc_state 都没有完成初始化，需要对malloc_state 进行初始化。

源码：

/*
  ------------------------- malloc_consolidate -------------------------

  malloc_consolidate 是 free() 的一个专用版本，用于处理 fastbins 中的内存块。不能使用 free() 本身来执行此操作，因为它可能会将内存块重新放回 fastbins 中。因此，我们需要使用同样代码的一个小变体。

  此外，由于此例程需要在通过 malloc 第一次调用时进行初始化，因此它恰好是触发初始化代码的理想位置。
*/

static void malloc_consolidate(mstate av)
{
  mfastbinptr*    fb;                 /* 当前正在合并的 fastbin */
  mfastbinptr*    maxfb;              /* 最后一个 fastbin（用于循环控制） */
  mchunkptr       p;                  /* 当前正在合并的块 */
  mchunkptr       nextp;              /* 下一个要合并的块 */
  mchunkptr       unsorted_bin;       /* 未排序 bin 头 */
  mchunkptr       first_unsorted;     /* 要链接到的块 */

  /* 这些变量与 free() 中的用途相同 */
  mchunkptr       nextchunk;
  INTERNAL_SIZE_T size;
  INTERNAL_SIZE_T nextsize;
  INTERNAL_SIZE_T prevsize;
  int             nextinuse;
  mchunkptr       bck;
  mchunkptr       fwd;

  /*
    如果 max_fast 为 0，我们知道 av 尚未初始化，因此在下面进行初始化
  */
    
  /*get_max_fast()宏定义*/

  if (get_max_fast () != 0) {
    clear_fastchunks(av);

    unsorted_bin = unsorted_chunks(av);

    /*
      从 fast bin 中移除每个块并进行合并，然后将它们放入未排序 bin 中。做这个的原因包括：将块放入未排序 bin 中避免了需要在 malloc 确定块不会立即被重用之前计算实际的 bin。
    */

    maxfb = &fastbin (av, NFASTBINS - 1);
    fb = &fastbin (av, 0);
    do {
      p = atomic_exchange_acq (fb, NULL);
      if (p != 0) {
	do {
	  check_inuse_chunk(av, p);
	  nextp = p->fd;

	  /* 在 free() 中合并代码的稍微精简版本 */
	  size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
	  nextchunk = chunk_at_offset(p, size);
	  nextsize = chunksize(nextchunk);

	  if (!prev_inuse(p)) {
	    prevsize = p->prev_size;
	    size += prevsize;
	    p = chunk_at_offset(p, -((long) prevsize));
	    unlink(av, p, bck, fwd);
	  }

	  if (nextchunk != av->top) {
	    nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

	    if (!nextinuse) {
	      size += nextsize;
	      unlink(av, nextchunk, bck, fwd);
	    } else
	      clear_inuse_bit_at_offset(nextchunk, 0);

	    first_unsorted = unsorted_bin->fd;
	    unsorted_bin->fd = p;
	    first_unsorted->bk = p;

	    if (!in_smallbin_range (size)) {
	      p->fd_nextsize = NULL;
	      p->bk_nextsize = NULL;
	    }

	    set_head(p, size | PREV_INUSE);
	    p->bk = unsorted_bin;
	    p->fd = first_unsorted;
	    set_foot(p, size);
	  }

	  else {
	    size += nextsize;
	    set_head(p, size | PREV_INUSE);
	    av->top = p;
	  }

	} while ( (p = nextp) != 0);

      }
    } while (fb++ != maxfb);
  }
  else {
    malloc_init_state(av);
    check_malloc_state(av);
  }
}

未初始化

首先会通过get_max_fast()判断当前堆是否已经完成初始化，第一次调用malloc申请分配时，该函数返回值为0，此时会进行堆的初始化工作。初始化会调用malloc_init_state()函数。

if (get_max_fast () != 0) {
  ...
}
else {
  malloc_init_state(av);
  check_malloc_state(av);
}

关于malloc_init_state函数

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

  /* 为普通 bin 建立循环链接 */
  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);
  av->flags |= FASTCHUNKS_BIT;

  av->top = initial_top (av);
}

在malloc_init_state()函数会进行堆的初始化工作，并且调用set_max_fast()设置global_max_fast为DEFAULT_MAXFAST，

• 首先会通过循环迭代初始化内存分配中的bins，bin->fd和bin->bk被初始化为指向自己，以建立循环链表。
• 如果内存管理状态不是主分配区（main_arena），则调用 set_noncontiguous 函数。这个函数用于设置内存管理状态的 noncontiguous 标志，表示内存分配不是连续的。
• 如果内存管理状态是主分配区（main_arena），则调用 set_max_fast 函数，将 DEFAULT_MXFAST 设置为最大的快速分配块大小。这个值用于确定哪些块可以放入 fastbin 中。
• 设置 FASTCHUNKS_BIT 标志：将 FASTCHUNKS_BIT 标志设置为内存管理状态的 flags 中，以表示 fastbin 可用。
• 初始化 top：调用 initial_top 函数，为内存管理状态初始化 top 指针，指向内存池的起始位置。

check_malloc_state()函数，用来检查内存管理器的状态是否合法，并且用于內部调试，用于内部调试和错误检测的函数，用于验证内存管理器的状态是否正确。

av：表示内存管理的状态（memory state）。这个参数是一个指向 malloc_state 结构体的指针，用于跟踪和管理内存分配和释放的状态信息。

DEFAULT_MXFAST 在 32 位系统上为 64，在 64 位系统上为 128。后面再次调用 malloc_consolidate() 的时候， get_max_fast() 返回值都不会等于 0，就不会再次进行初始化。

已初始化

如果get_max_state返回值不为0，那么就是堆已经完成初始化，接下来会将fastbin中的每一个chunk合并整理到unsorted_chunk或者top_chunk。

if (get_max_fast () != 0) {
  clear_fastchunks(av);

  ...
}

因为malloc_consolidate()会清空fastbin，因此先调用clear_fastchunks()清除标志位

接下来就会先遍历fastbinY数组，得到每一个固定尺寸的fastbin单链表，然后再遍历fastbin单链表得到相同大小的空闲chunk。

maxfb = &fastbin (av, NFASTBINS - 1);
   fb = &fastbin (av, 0);
   do {
     p = atomic_exchange_acq (fb, NULL);
     if (p != 0) {
do {
  check_inuse_chunk(av, p);
  nextp = p->fd;
    ...

   } while ( (p = nextp) != 0);

     }
   } while (fb++ != maxfb); 

对于每一个chunk会先尝试向后合并，合并操作就是更新p的size和指向，然后调用unlink宏将其从bin中脱离。

然后会尝试向前合并，如果前一个相邻top_chunk，那么就直接合并到top_chunk后，不管unsorted_bin；如果前一个不相邻top_chunk，则向前合并后插入到unsorted_bin。

if (!prev_inuse(p)) { //这个条件检查前一个块p是否被使用
  prevsize = p->prev_size;//获取前一个块 p 的大小信息
  size += prevsize;//将前一个块的大小添加到当前块 p 的大小中，以得到合并后的块的总大小。
  p = chunk_at_offset(p, -((long) prevsize));//将指针 p 移动到合并后的块的新位置，即前一个块的位置，这是为了合并两个块
  unlink(av, p, bck, fwd);//从链表中移除前一个块 p，以便进行合并
}//向后合并

if (nextchunk != av->top) {//这个条件检查下一个块 nextchunk 是否是内存池的顶部块（top chunk）。如果不是顶部块，就需要处理下一个块的合并
  nextinuse = inuse_bit_at_offset(nextchunk, nextsize);//检查下一个块 nextchunk 是否正在使用。这是通过检查下一个块的头部信息中的标志位来完成的。

  if (!nextinuse) {
    size += nextsize;
    unlink(av, nextchunk, bck, fwd);//从链表中移除下一个块 nextchunk，以便进行合并。
  } else//如果下一个块是正在使用的块，就需要清除它的 "in use" 标志位，以便进行合并。
    clear_inuse_bit_at_offset(nextchunk, 0);//获取未排序块链表的头部

  first_unsorted = unsorted_bin->fd;//获取未排序块链表的头部
  unsorted_bin->fd = p;//将当前块 p 添加到未排序块链表的前面
  first_unsorted->bk = p;//更新未排序块链表头部的 "bk" 指针，以链接到当前块 p

  if (!in_smallbin_range (size)) {
    p->fd_nextsize = NULL;
    p->bk_nextsize = NULL;
  }//：如果合并后的块的大小不在小块范围内，即它太大了，就需要清除 "fd_nextsize" 和 "bk_nextsize" 字段，以便将其视为一个独立的块

  set_head(p, size | PREV_INUSE);//设置合并后的块的头部信息，包括大小和前一个块的使用状态
  p->bk = unsorted_bin;//设置合并后的块的 "bk" 指针，以链接到未排序块链表
  p->fd = first_unsorted;//设置合并后的块的 "fd" 指针，以链接到未排序块链表的前面
  set_foot(p, size);//设置合并后的块的尾部信息
	}

  else {
    size += nextsize;
    set_head(p, size | PREV_INUSE);
    av->top = p;
  }//向前合并

申请内存

_libc_malloc

malloc函数一般被用来申请内存块，该函数调用了_libc_malloc函数，该函数核心为int_malloc函数。

该函数会先检查是否有内存分配函数的hook函数（_malloc_hook），如果存在，它会调用该钩子函数来执行内存分配操作。如果没有用户定义的钩子函数，它会继续执行内存分配的默认逻辑。

// wapper for int_malloc
void *__libc_malloc(size_t bytes) {
    mstate ar_ptr;
    void * victim;
    // 检查是否有内存分配钩子，如果有，调用钩子并返回.
    void *(*hook)(size_t, const void *) = atomic_forced_read(__malloc_hook);
    if (__builtin_expect(hook != NULL, 0))
        return (*hook)(bytes, RETURN_ADDRESS(0));

然后会寻找一个arena来试图分配内存，再调用_int_malloc函数去申请内存

arena_get(ar_ptr, bytes);
victim = _int_malloc(ar_ptr, bytes);

分配失败就会去尝试寻找一个可以用的arena，并分配内存

/* Retry with another arena only if we were able to find a usable arena
   before.  */
if (!victim && ar_ptr != NULL) {
    LIBC_PROBE(memory_malloc_retry, 1, bytes);
    ar_ptr = arena_get_retry(ar_ptr, bytes);
    victim = _int_malloc(ar_ptr, bytes);
}

申请到了以后需要解锁（关于锁在基础知识里面有）

if (ar_ptr != NULL) __libc_lock_unlock(ar_ptr->mutex);

然后会判断目前的状态是否满足以下条件：

assert(!victim || chunk_is_mmapped(mem2chunk(victim)) ||
       ar_ptr == arena_for_chunk(mem2chunk(victim)));

• 没有申请到内存

• 是mmap的内存

• 申请到的内存必须在其分配的arena中

_int_malloc

上面说过，_int_malloc是内存分配的和核心函数，大致流程为：

• 会根据用户申请的内存块大小和相应大小的chunk使用频度来实现不同的分配方法
• 由小到大依次检查各种bin中是否有相应的内存块能够满足请求的内存
• 如果所有的空闲chunk都无法满足就会从top_chunk去找
• 如果top_chunk也无法满足，堆分配器就会进行内存申请

_int_malloc函数太长了，这里就不放全部的源码了

函数首先定义了一些变量，并且将用户申请的内存大小转换为内部的chunk大小

static void *
_int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* 规范化后的请求大小 */
  unsigned int idx;                 /* 相关的二进制索引 */
  mbinptr bin;                      /* 相关的二进制块指针 */

  mchunkptr victim;                 /* 被检查/选定的内存块 */
  INTERNAL_SIZE_T size;             /* 其大小 */
  int victim_index;                 /* 其二进制索引 */

  mchunkptr remainder;              /* 拆分后的剩余块 */
  unsigned long remainder_size;     /* 其大小 */

  unsigned int block;               /* 位图遍历器 */
  unsigned int bit;                 /* 位图遍历器 */
  unsigned int map;                 /* 当前二进制位图的字 */

  mchunkptr fwd;                    /* 链接的临时变量 */
  mchunkptr bck;                    /* 链接的临时变量 */

  const char *errstr = NULL;

  /*
     将请求大小转换为内部形式，通过添加 SIZE_SZ 字节的开销，
     可能还需要添加更多的开销以获得必要的对齐和/或
     以至少获得 MINSIZE，即可分配的最小大小。此外，
     checked_request2size 会检查并捕获（返回0）请求大小，
     如果在填充和对齐时太大而会绕过零。
   */
  checked_request2size (bytes, nb);

首先调用checked_request2size将需要分配的内存大小bytes转换为chunk的大小。checked_request2size是个宏定义，主要调用request2size进行计算

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

在学习结构的时候有这样一个地方，当一个chunk为空闲时，至少要有prev_size、size、fd和bk四个参数，因此MINISIZE就代表了这四个参数需要占用的内存大小，当一个chunk被使用时，prev_size可能会被前一个chunk用来存储，fd、bk会被用来存储数据，所以只剩下了size参数需要设置，request2size中的SIZE_SZ就是INTERNAL_SIZE_T类型的大小，因此至少需要req+SIZE_SZ的内存大小。MALLOC_ALIGN_MASK用来对齐，因此request2size就计算出了所需的chunk的大小。

参数av就是分配区指针，为null表示没有分配区可用，这时会调用sysmalloc通过mmap获取chunk。

arena

/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
	alloc_perturb (p, bytes);
      return p;
    }

这段代码会先检查是否存在可用的分配区（arena），如果没有，就使用malloc函数通过mmap系统调用来获取一块内存块，获取内存块成功后，还会对这块内存块进行填充（perturb），以提高内存分配的安全性。

fast bin

/*
   如果请求的内存大小符合快速分配的条件，首先检查相应的快速分配区块。
   即使在内存池（av）尚未初始化的情况下，这段代码也是安全的，因此我们可以在不进行检查的情况下尝试执行它，这有助于提高执行效率。
*/

if ((unsigned long)(nb) <= (unsigned long)(get_max_fast()))
{
  // 计算请求内存大小所对应的快速分配区块的索引。
  idx = fastbin_index(nb);

  // 获取对应快速分配区块的指针。
  mfastbinptr *fb = &fastbin(av, idx);

  // 从快速分配区块中取出一块内存块，利用fd遍历对应的bin内是否有空闲的chunk块，
  mchunkptr pp = *fb;
  do
  {
    // 选择一块内存块作为候选（victim）。
    victim = pp;
    if (victim == NULL)
      break;
  }
  while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd, victim))
         != victim);

  // 如果成功找到一块内存块，进行处理。
  if (victim != 0)
  {
    // 如果发现内存块的大小与索引不匹配，说明存在内存损坏。
    // 根据取得的 victim ，利用 chunksize 计算其大小。
    // 利用fastbin_index 计算 chunk 的索引。
    if (__builtin_expect(fastbin_index(chunksize(victim)) != idx, 0))
    {
      errstr = "malloc(): memory corruption (fast)";
    errout:
      // 打印错误信息并返回NULL。
      malloc_printerr(check_action, errstr, chunk2mem(victim), av);
      return NULL;
    }

    // 针对重新分配的内存块进行检查。调试有用。
    check_remalloced_chunk(av, victim, nb);

    // 返回分配到的内存块指针。
    void *p = chunk2mem(victim);

    // 对内存块进行填充以增强安全性。
    alloc_perturb(p, bytes);

    return p;
  }
}

这段代码主要用于快速分配内存块，首先检查请求的内存大小是否符合快速分配的条件，然后在快速分配区块中查找可用的内存块。如果找到符合要求的内存块，就返回该内存块的指针，否则返回NULL。同时，如果发现内存块的大小与索引不匹配，会报告内存损坏错误。从fastbin的头结点开始取chunk。

small bin

/*
   如果是一个小内存请求，检查常规的内存块分配区（smallbins）。
   由于这些 "smallbins" 每个都包含一种大小的内存块，所以无需在内部进行搜索。
   （对于大内存请求，我们需要等待未分类的内存块被处理以找到最佳匹配。
   但对于小内存请求，匹配是精确的，所以我们可以立即检查，这更快。）
*/

// 如果fast bin无法满足需求，并且所申请的chunk大小满足small chunk的范围
if (in_smallbin_range (nb))
{
  // 计算请求内存大小所对应的小内存块分配区（smallbins）的索引。
  idx = smallbin_index (nb);

  // 获取对应的小内存块分配区（smallbins）的chunk指针。
  bin = bin_at (av, idx);

  // 尝试从分配区中取出一个内存块作为候选（victim）。获取 small bin 的最后一个 chunk
  // 如果 victim = bin ，那说明该 bin 为空。有两种情况
  if ((victim = last (bin)) != bin)
  {
    // 第一种，如果victim等于0，表示分配区未初始化，需要执行内存整理（malloc_consolidate）。
    if (victim == 0) /* 初始化检查 */
      malloc_consolidate (av);
    else
    {
      // 第二种情况，small bin 中存在空闲的 chunk
      // 取出候选内存块的前一个和后一个块。
      bck = victim->bk;

      // 检查候选内存块的前一个块是否与其后一个块的前驱一致，用于确保链表完整性。
      if (__glibc_unlikely (bck->fd != victim))
      {
        errstr = "malloc(): smallbin double linked list corrupted";
        goto errout;
      }

      // 标记候选内存块为已分配状态，并从分配区中移除。
      set_inuse_bit_at_offset (victim, nb);
      bin->bk = bck;
      bck->fd = bin;

      // 如果内存分配不是主分配区（main arena），设置相应的标志位。
      if (av != &main_arena)
        victim->size |= NON_MAIN_ARENA;

      // 对分配的内存块进行检查。
      check_malloced_chunk (av, victim, nb);

      // 返回分配到的内存块指针。将申请到的 chunk 转化为对应的 mem 状态
      void *p = chunk2mem (victim);

      // 对内存块进行填充以增强安全性。
      alloc_perturb (p, bytes);

      return p;
    }
  }
}

用于处理小内存块的分配请求。它首先检查请求的内存大小是否在小内存块的分配范围内，然后在相应的小内存块分配区（smallbins）中查找合适的内存块。如果找到一个合适的内存块，就将其标记为已分配并从分配区中移除，然后返回该内存块的指针。如果分配区尚未初始化，会进行内存整理。同时，还会检查链表完整性，以确保内部数据结构的正确性。最后，分配成功后，还会对内存块进行检查和填充，以提高安全性。

large bin

当fast bin和large bin中的chunk都不能满足用户申请的chunk大小时，就会从large bin中尝试寻找。但是在这里并没有直接扫描对应bin中的chunk，调用了malloc_consolidata函数处理fast bin中的chunk，如果能合并就合并后放到unsorted bin中，不能合并就直接放到unsorted bin中。这里在还不知道是否有可用内存就执行合并操作，以便减少内存碎片。实际上，合并操作在大多数程序并不频繁，需要频繁调用合并操作的程序通常容易出现内存问题。

/*
   如果这是一个大内存请求，在继续之前合并快速分配区块（fastbins）。
   尽管看起来在查看是否有可用内存之前杀掉所有的快速分配区块似乎有些过多，
   但这样做可以避免通常与快速分配区块相关的内存碎片问题。
   此外，在实际应用中，程序通常会连续地发出小内存或大内存的请求，而较少混合使用，
   因此在大多数程序中合并操作并不那么频繁。而那些需要频繁调用合并操作的程序，通常容易出现内存碎片问题。
*/

else
{
  // 计算请求内存大小所对应的大内存块分配区（largebins）的索引。
  idx = largebin_index (nb);

  // 如果快速分配区块中仍有未释放的内存块，进行合并操作。
  if (have_fastchunks (av))
    malloc_consolidate (av);
}

大循环

如果程序执行到了这里，说明与chunk大小一致的bin没有符合要求的，就会进入下面的大循环。

在大循环中，主要完成了以下操作：

• 按照FIFO的方式将unsored bin取出，如果是small request并且满足，满足就返回，不是的话就返回bin
• 从large bin分配所需内存

虽然会首先使用large bin、top chunk来满足请求，但是在上面由于没有分配small bin，并没有对fast bin中的chunk进行合并，所以在这儿会进行fast bin chunk的合并，并使用一个大循环来尝试再次分配small bin chunk。

/*
   处理最近释放或剩余的内存块，仅当它正好符合要求时才获取一个内存块，或者如果这是一个小内存请求，且内存块是最近的非精确匹配的剩余部分。将其他遍历过的内存块放入相应的分配区（bins）。请注意，这个步骤是程序中唯一一个将内存块放入分配区的地方。

   外部循环是必要的，因为我们可能直到 malloc 的最后阶段才意识到需要进行内存合并，所以必须执行合并操作并重试。这种情况最多发生一次，只有在需要扩展内存以满足一个 "小" 请求时才会发生。
*/

遍历unsorted bin

先遍历unsorted bin，遍历顺序为bk

while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
    {
      bck = victim->bk;
      // 进行unsorted chunk 大小检测，异常小或异常大都会导致出错
      if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
          || __builtin_expect (victim->size > av->system_mem, 0))
        malloc_printerr (check_action, "malloc(): memory corruption",
                          chunk2mem (victim), av);
      // 获取当前遍历到的unsorted chunk的size
      size = chunksize (victim);

如果用户的请求是small bin chunk，那么首先考虑last remainder，如果unsorted bin中唯一

// 如果当前请求位于small chunks的大小范围内
      // 同时，unsorted bin里只有一个chunk，该chunk还是last_remainder
      // 并且该last_remainder的大小足够分配
      if (in_smallbin_range (nb) &&
          bck == unsorted_chunks (av) &&
          victim == av->last_remainder &&
          (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
      {
        /* split and reattach remainder */

        // 将该last_remainder 分割
        remainder_size = size - nb;
        remainder = chunk_at_offset (victim, nb);
        // 同时，将这部分last_remainder放回unsorted bin里
        unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
        // 并把剩余部分置为新的last_remainder
        av->last_remainder = remainder;
        remainder->bk = remainder->fd = unsorted_chunks (av);
        if (!in_smallbin_range (remainder_size))
        {
          remainder->fd_nextsize = NULL;
          remainder->bk_nextsize = NULL;
        }
        // 最后对切割出来的chunk进行一些常规操作并返回
        set_head (victim, nb | PREV_INUSE |
                  (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head (remainder, remainder_size | PREV_INUSE);
        set_foot (remainder, remainder_size);

        check_malloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
      }

      /* remove from unsorted list */
      // 将当前遍历到的unsorted chunk从unsorted bin里断开
      unsorted_chunks (av)->bk = bck;
      bck->fd = unsorted_chunks (av);c

如果取出的大小正好合适，就直接使用

// 如果遍历到的这个unsorted chunk，它的大小与所申请的chunk大小刚刚好
      // 直接分配
      if (size == nb)
      {
        set_inuse_bit_at_offset (victim, size);
        if (av != &main_arena)
          victim->size |= NON_MAIN_ARENA;
        check_malloced_chunk (av, victim, nb);
        void *p = chunk2mem (victim);
        alloc_perturb (p, bytes);
        return p;
      }

判断大小，取出来的chunk放到small bin和large bin中，

// 将所遍历到的unsorted chunk，按照chunk大小，分类放置进small bin或large bin中
if (in_smallbin_range (size))
{
  victim_index = smallbin_index (size);
  bck = bin_at (av, victim_index);
  fwd = bck->fd;
}
else
{
  // 将遍历到的unsorted chunk放置进large bin里
  victim_index = largebin_index (size);
  bck = bin_at (av, victim_index);
  fwd = bck->fd;

  /* maintain large bins in sorted order */
  // 如果large bin非空
  if (fwd != bck)
  {
    /* Or with inuse bit to speed comparisons */
    size |= PREV_INUSE;
    /* if smaller than smallest, bypass loop below */
    assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
    // 如果遍历到的unsorted chunk的size，小于 large bin链上large chunks的最小size
    if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
    {
      //将当前遍历到的unsorted chunk接到当前large bin的链尾
      fwd = bck;
      bck = bck->bk;

      victim->fd_nextsize = fwd->fd;
      victim->bk_nextsize = fwd->fd->bk_nextsize;
      fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
    }
    else
    {
      assert ((fwd->size & NON_MAIN_ARENA) == 0);
      // 从large bin的链头到链尾，从size大的chunk到size小的chunk，依次遍历，直到找到第一个 大小不大于该unsorted chunk的 第一个chunk
      while ((unsigned long) size < fwd->size)
      {
        fwd = fwd->fd_nextsize;
        assert ((fwd->size & NON_MAIN_ARENA) == 0);
      }

      // 如果当前遍历到的large chunk的大小刚好等于即将插入的unsorted chunk的大小
      // 总是选择插入到这个large chunk的后面
      if ((unsigned long) size == (unsigned long) fwd->size)
        /* Always insert in the second position.  */
        fwd = fwd->fd;
      else
      {
        victim->fd_nextsize = fwd;
        victim->bk_nextsize = fwd->bk_nextsize;
        fwd->bk_nextsize = victim;
        victim->bk_nextsize->fd_nextsize = victim;
      }
      bck = fwd->bk;
    }
  }
  else
    victim->fd_nextsize = victim->bk_nextsize = victim;
}

取出，并设定最多循环1000次

mark_bin (av, victim_index);
      victim->bk = bck;
      victim->fd = fwd;
      fwd->bk = victim;
      bck->fd = victim;

#define MAX_ITERS       10000
      if (++iters >= MAX_ITERS)
        break;
    }

large chunk

如果申请的chunk在large chunk范围内，就在对应的bin中从小到大扫描，找到合适的

    // 如果请求的内存块大小大于 smallbin 范围，执行以下操作
if (!in_smallbin_range(nb)) {
  // 在对应 bin 中查找适合大小的内存块（以排序顺序）
  bin = bin_at(av, idx);

  // 跳过扫描如果 bin 为空或最大的块太小
  if ((victim = first(bin)) != bin &&
      (unsigned long)(victim->size) >= (unsigned long)(nb)) {
    // 从 bin 中找到第一个适合大小的内存块
    // 反向遍历链表，直到找到第一个不小于所需chunk大小的chunk
    victim = victim->bk_nextsize;
    while ((unsigned long)(size = chunksize(victim)) < (unsigned long)(nb))
      victim = victim->bk_nextsize;

    // 避免移除相同大小的内存块中的第一个，以减少跳表的操作
    // 如果最终取到的chunk不是该bin中的最后一个chunk，并且该chunk与其前面的chunk
    //的大小相同，那么我们就取其前面的chunk，这样可以避免调整bk_nextsize,fd_nextsize
    // 链表。因为大小相同的chunk只有一个会被串在nextsize链上。
    if (victim != last(bin) && victim->size == victim->fd->size)
      victim = victim->fd;

    // 计算剩余的内存块大小
    remainder_size = size - nb;

    // 从 bin 中移除选中的内存块
    unlink(av, victim, bck, fwd);

    // 如果剩余的内存块不足以分配（小于 MINSIZE）
    if (remainder_size < MINSIZE) {
      // 将整块内存分配给用户
      set_inuse_bit_at_offset(victim, size);
      if (av != &main_arena)
        victim->size |= NON_MAIN_ARENA;
    }
    // 否则，将内存块分割
    else {
      // 分割内存块，将剩余部分放入未排序 bin 中
      remainder = chunk_at_offset(victim, nb);

      // 确保未排序 bin 中没有破坏的指针
      bck = unsorted_chunks(av);
      fwd = bck->fd;

      if (__glibc_unlikely(fwd->bk != bck)) {
        errstr = "malloc(): corrupted unsorted chunks";
        goto errout;
      }

      remainder->bk = bck;
      remainder->fd = fwd;
      bck->fd = remainder;
      fwd->bk = remainder;

      // 如果剩余的内存块大小不在 smallbin 范围内，清除其 nextsize 指针
      if (!in_smallbin_range(remainder_size)) {
        remainder->fd_nextsize = NULL;
        remainder->bk_nextsize = NULL;
      }

      // 设置分配给用户的内存块头和脚，标记为已分配
      set_head(victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
      set_head(remainder, remainder_size | PREV_INUSE);
      set_foot(remainder, remainder_size);
    }

    // 检查分配的内存块是否有效，并返回指向分配内存块的指针
    check_malloced_chunk(av, victim, nb);
    void *p = chunk2mem(victim);
    // 如果设置了perturb_type, 则将获取到的chunk初始化为 perturb_type ^ 0xff
    alloc_perturb(p, bytes);
    return p;
  }
}

执行到这里，说明没有从对应的合适的bin中获取合适的chunk，所以需要查找比当前bin更大的fast bin、small bin或者是large bin。

++idx;
      // 获取对应的bin
      bin   = bin_at(av, idx);
      // 获取当前索引在binmap中的block索引
      // #define idx2block(i) ((i) >> BINMAPSHIFT)  ,BINMAPSHIFT=5
      // Binmap按block管理，每个block为一个int，共32个bit，可以表示32个bin中是否有空闲chunk存在
      // 所以这里是右移5
      block = idx2block(idx);
      // 获取当前块大小对应的映射，这里可以得知相应的bin中是否有空闲块
      map   = av->binmap[ block ];
      // #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
      // 将idx对应的比特位设置为1，其它位为0
      bit   = idx2bit(idx);
      for (;;) {

找到合适的map

/* Skip rest of block if there are no more set bits in this block.
 */
// 如果bit>map，则表示该 map 中没有比当前所需要chunk大的空闲块
// 如果bit为0，那么说明，上面idx2bit带入的参数为0。
if (bit > map || bit == 0) {
    do {
        // 寻找下一个block，直到其对应的map不为0。
        // 如果已经不存在的话，那就只能使用top chunk了
        if (++block >= BINMAPSIZE) /* out of bins */
            goto use_top;
    } while ((map = av->binmap[ block ]) == 0);
    // 获取其对应的bin，因为该map中的chunk大小都比所需的chunk大，而且
    // map本身不为0，所以必然存在满足需求的chunk。
    bin = bin_at(av, (block << BINMAPSHIFT));
    bit = 1;
}

找到合适的bin

/* Advance to bin with set bit. There must be one. */
// 从当前map的最小的bin一直找，直到找到合适的bin。
// 这里是一定存在的
while ((bit & map) == 0) {
    bin = next_bin(bin);
    bit <<= 1;
    assert(bit != 0);
}

检查chunk

/* Inspect the bin. It is likely to be non-empty */
// 获取对应的bin
victim = last(bin);

/*  If a false alarm (empty bin), clear the bit. */
// 如果victim=bin，那么我们就将map对应的位清0，然后获取下一个bin
// 这种情况发生的概率应该很小。
if (victim == bin) {
    av->binmap[ block ] = map &= ~bit; /* Write through */
    bin                 = next_bin(bin);
    bit <<= 1;
}

取出chunk

else {
    // 获取对应victim的大小
    size = chunksize(victim);

    /*  We know the first chunk in this bin is big enough to use. */
    assert((unsigned long) (size) >= (unsigned long) (nb));
    // 计算分割后剩余的大小
    remainder_size = size - nb;

    /* unlink */
    unlink(av, victim, bck, fwd);

    /* Exhaust */
    // 如果分割后不够一个chunk怎么办？
    if (remainder_size < MINSIZE) {
        set_inuse_bit_at_offset(victim, size);
        if (av != &main_arena) set_non_main_arena(victim);
    }

    /* Split */
    // 如果够，尽管分割
    else {
        // 计算剩余的chunk的偏移
        remainder = chunk_at_offset(victim, nb);

        /* We cannot assume the unsorted list is empty and therefore
           have to perform a complete insert here.  */
        // 将剩余的chunk插入到unsorted bin中
        bck = unsorted_chunks(av);
        fwd = bck->fd;
        if (__glibc_unlikely(fwd->bk != bck)) {
            errstr = "malloc(): corrupted unsorted chunks 2";
            goto errout;
        }
        remainder->bk = bck;
        remainder->fd = fwd;
        bck->fd       = remainder;
        fwd->bk       = remainder;

        /* advertise as last remainder */
        // 如果在small bin范围内，就将其标记为remainder
        if (in_smallbin_range(nb)) av->last_remainder = remainder;
        if (!in_smallbin_range(remainder_size)) {
            remainder->fd_nextsize = NULL;
            remainder->bk_nextsize = NULL;
        }
        // 设置victim的使用状态
        set_head(victim,
                 nb | PREV_INUSE |
                     (av != &main_arena ? NON_MAIN_ARENA : 0));
        // 设置remainder的使用状态，这里是为什么呢？
        set_head(remainder, remainder_size | PREV_INUSE);
        // 设置remainder的大小
        set_foot(remainder, remainder_size);
    }
    // 检查
    check_malloced_chunk(av, victim, nb);
    // chunk状态转换到mem状态
    void *p = chunk2mem(victim);
    // 如果设置了perturb_type, 则将获取到的chunk初始化为 perturb_type ^ 0xff
    alloc_perturb(p, bytes);
    return p;
}

使用top chunk

use_top:
    /*
       If large enough, split off the chunk bordering the end of memory
       (held in av->top). Note that this is in accord with the best-fit
       search rule.  In effect, av->top is treated as larger (and thus
       less well fitting) than any other available chunk since it can
       be extended to be as large as necessary (up to system
       limitations).

       We require that av->top always exists (i.e., has size >=
       MINSIZE) after initialization, so if it would otherwise be
       exhausted by current request, it is replenished. (The main
       reason for ensuring it exists is that we may need MINSIZE space
       to put in fenceposts in sysmalloc.)
     */
    // 获取当前的top chunk，并计算其对应的大小
    victim = av->top;
    size   = chunksize(victim);
    // 如果分割之后，top chunk 大小仍然满足 chunk 的最小大小，那么就可以直接进行分割。
    if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE)) {
        remainder_size = size - nb;
        remainder      = chunk_at_offset(victim, nb);
        av->top        = remainder;
        // 这里设置 PREV_INUSE 是因为 top chunk 前面的 chunk 如果不是 fastbin，就必然会和
        // top chunk 合并，所以这里设置了 PREV_INUSE。
        set_head(victim, nb | PREV_INUSE |
                             (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head(remainder, remainder_size | PREV_INUSE);

        check_malloced_chunk(av, victim, nb);
        void *p = chunk2mem(victim);
        alloc_perturb(p, bytes);
        return p;
    }
    // 否则，判断是否有 fast chunk
    /* When we are using atomic ops to free fast chunks we can get
       here for all block sizes.  */
    else if (have_fastchunks(av)) {
        // 先执行一次fast bin的合并
        malloc_consolidate(av);
        /* restore original bin index */
        // 判断需要的chunk是在small bin范围内还是large bin范围内
        // 并计算对应的索引
        // 等待下次再看看是否可以
        if (in_smallbin_range(nb))
            idx = smallbin_index(nb);
        else
            idx = largebin_index(nb);
    }

堆内存不够

/*
   Otherwise, relay to handle system-dependent cases
 */
// 否则的话，我们就只能从系统中再次申请一点内存了。
else {
    void *p = sysmalloc(nb, av);
    if (p != NULL) alloc_perturb(p, bytes);
    return p;
}

_libc_calloc

calloc 也是 libc 中的一种申请内存块的函数。在 libc中的封装为 _libc_calloc

/*
  calloc(size_t n_elements, size_t element_size);
  Returns a pointer to n_elements * element_size bytes, with all locations
  set to zero.
*/
void*  __libc_calloc(size_t, size_t);

未完待续。。。

参考

• 申请内存块 - CTF Wiki (ctf-wiki.org)
• malloc.c - malloc/malloc.c - Glibc source code (glibc-2.24) - Bootlin
• Glibc：浅谈 malloc_consolidate() 函数具体实现-CSDN博客
• [heap - 7 - _int_malloc 源码及其部分分析 | Kiprey’s Blog](https://kiprey.github.io/2020/04/heap-7- __int_malloc_source/)