本文主要分析glibc-2.35中malloc的流程逻辑,并且对流程中一些重要的函数会单独进行讲解

__libc_malloc

malloc函数实际调用到的是__libc_malloc ,而__libc_malloc 实际只实现了从 tcache bin 分配的功能,如果tcache bin中没有满足的chunk,则还需调用_int_malloc函数来进行分配

void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;

  _Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2,
                  "PTRDIFF_MAX is not more than half of SIZE_MAX");

  if (!__malloc_initialized) // 检查 malloc 是否初始化
    ptmalloc_init (); // 没有初始化先进行初始化
#if USE_TCACHE  //条件编译,如果开启了tcache bin 就优先从tcache bin中取
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  if (!checked_request2size (bytes, &tbytes)) // 检查申请大小,将其转为实际的size大小,并写入arg2
    {									  // 实际size就是申请的 size 加上 0x10 的chunk头 
      __set_errno (ENOMEM);
      return NULL;
    }
  size_t tc_idx = csize2tidx (tbytes);//将大小转化为对应tcachebin的下标
                                   //比如0x20变成3,0x28也是3,而0x29就是4,0x30也是4

  MAYBE_INIT_TCACHE (); // 检查是否 tcache bin 是否初始化,并自动初始化

  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins 		  // 申请的大小是否在tcache bin 的范围内
      && tcache						// tcache bin是否已经初始化
      && tcache->counts[tc_idx] > 0)  // 检查tcache bin中是否有chunk可以返回,有就直接取出然后返回
    {
      victim = tcache_get (tc_idx);   // 从tcache bin取出 chunk
      return tag_new_usable (victim); // 处理内存标签确保内存安全
    }
  DIAG_POP_NEEDS_COMMENT;
#endif

  if (SINGLE_THREAD_P) // 如果程序是单线程的,就不需要获取私有的main_arena   
    {				 // 直接这里进入 _int_malloc
      victim = tag_new_usable (_int_malloc (&main_arena, bytes));
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          &main_arena == arena_for_chunk (mem2chunk (victim))); //检查 chunk 所属arena == main_arena
      return victim;
    }

  arena_get (ar_ptr, bytes); // 获取私有的 arena,并上锁

  victim = _int_malloc (ar_ptr, bytes); // 进入 _int_malloc 分配
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)  // 如果分配不到chunk,并且获取不到main_arena,就再重试一次
    {
      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) // 如果前面获取到了 arena,则现在给 arena解锁
    __libc_lock_unlock (ar_ptr->mutex);

  victim = tag_new_usable (victim);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}
libc_hidden_def (__libc_malloc)

总结:这个函数实现了从tcache bin中分配的功能,如果tcache bin 未开启或无满足条件的chunk,就获取当前线程的 arena 调用_int_malloc进行分配

_int_malloc

我们都知道arena 中的bin(除了fastbin以外),每个bin都是一个双向链表的节点,为了简化链表的管理,ptmalloc中将每个bin都看做是一个chunk来管理,每个bin中fd和bk都可以对应到chunk中fd和bk,fastbin也是同理只是fastbin没有使用到bk

typedef struct malloc_chunk *mbinptr;
typedef struct malloc_chunk * mfastbinptr;

因此在 bin 中的 free Chunk 指向的不是 bins 数组真实的物理首地址,而是bins的fd减去0x10 的虚拟的 chunk 头地址

static void *
 _int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* 标准化的请求大小 */
  unsigned int idx;                 /* 相关的 bin 的idx */
  mbinptr bin;                      /* 相关的 bin */

  mchunkptr victim;                 /* 正在检查或被选中的 chunk */
  INTERNAL_SIZE_T size;             /* victim chunk 的大小 */
  int victim_index;                 /* victim 所属的 bin 索引 */

  mchunkptr remainder;              /* 分割后剩余的部分(chunk) */
  unsigned long remainder_size;     /*  剩余部分的大小 */

  unsigned int block;               /* 位图遍历器(用于定位 block/数组下标) */
  unsigned int bit;                 /* 位图遍历器(用于定位 bit/位) */
  unsigned int map;                 /* binmap 中当前遍历到的字(数值) */

  mchunkptr fwd;                    /* 用于链表操作的临时变量(前向指针) */
  mchunkptr bck;                    /* 用于链表操作的临时变量(后向指针) */

#if USE_TCACHE
  size_t tcache_unsorted_count;	    /* 统计已处理并放入 Tcache 的 Unsorted Chunks 数量 */
#endif

  /*
    将请求的大小转换为内部形式,具体做法是加上 SIZE_SZ 字节的开销(即 Chunk 头部的 size 字段大小),	   并可能需要加上更多字节以满足必要的对齐要求,和/或确保大小至少达到 MINSIZE(即最小可分配大小)。
    此外,如果请求的大小过大,导致在进行填充和对齐操作后发生溢出(即数值绕回 0)		  
    checked_request2size 函数将返回 false
   */

  if (!checked_request2size (bytes, &nb))
    {
      __set_errno (ENOMEM);
      return NULL;
    }

  /* 如果没有arena,就调用 sysmalloc获得一块mmap的chunk */
  if (__glibc_unlikely (av == NULL)) 
    {
      void *p = sysmalloc (nb, av); 
      if (p != NULL)
    alloc_perturb (p, bytes); // 辅助调试用的,默认不开启不用管
      return p; 
    }

  /*
      如果(请求的)大小符合 fastbin 的范围,首先检查对应的 bin。
	  即使 av(分配区结构体)尚未初始化,执行这段代码也是安全的,
	  因此我们可以不经检查直接尝试,从而在这一快速路径上节省一些时间。
   */

#define REMOVE_FB(fb, victim, pp)			\
  do							\
    {							\
      victim = pp;					\
      if (victim == NULL)				\
    break;						\
      pp = REVEAL_PTR (victim->fd);                                     \
      if (__glibc_unlikely (pp != NULL && misaligned_chunk (pp)))       \
    malloc_printerr ("malloc(): unaligned fastbin chunk detected"); \
    }							\
  while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
     != victim); // 原子交换比较,如果 *fb != victim(旧头)说明发生了抢占
                // 将 *fb 的值赋给 pp 并重新循环
  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ())) 
    // 比较是否满足fastbin的大小(<= 0x80)如果满足的话先走fastbin分配
    {
      idx = fastbin_index (nb); // 获取申请大小在 fastbin中对应的idx
      mfastbinptr *fb = &fastbin (av, idx); // 获取 fastbin
      mchunkptr pp;
      victim = *fb; //获取fastbin中的第一个chunk

      if (victim != NULL)
    {
      if (__glibc_unlikely (misaligned_chunk (victim)))
        malloc_printerr ("malloc(): unaligned fastbin chunk detected 2");

      if (SINGLE_THREAD_P) // 根据是否为单线程,走不同的路径
        *fb = REVEAL_PTR (victim->fd); //拿走fastbin中victim 并将其的fd解密后放回fastbin中
      else
        REMOVE_FB (fb, pp, victim); // 多了CAS处理多线程下的竞争情况,除此之外功能与上面一样
      if (__glibc_likely (victim != NULL)) //再次检查 victim 不为 0
        {
          size_t victim_idx = fastbin_index (chunksize (victim));
          if (__builtin_expect (victim_idx != idx, 0)) // 检查victim的大小对应的idx
        malloc_printerr ("malloc(): memory corruption (fast)"); //与其所在的idx是否一致
          check_remalloced_chunk (av, victim, nb);
#if USE_TCACHE
          /* 尝试把 fastbin 中chunk放入到tcache bin中  */
          size_t tc_idx = csize2tidx (nb); 
          if (tcache && tc_idx < mp_.tcache_bins) 
        {
          mchunkptr tc_victim;

         /* 当tcache bin 未满并且 fastbin还有chunk时,循环将fastbin中的chunk放到tcache bin中 */
          while (tcache->counts[tc_idx] < mp_.tcache_count
             && (tc_victim = *fb) != NULL)
            { // 与上面从 fastbin 中取chunk 一样
              if (__glibc_unlikely (misaligned_chunk (tc_victim)))
            malloc_printerr ("malloc(): unaligned fastbin chunk detected 3");
              if (SINGLE_THREAD_P)
            *fb = REVEAL_PTR (tc_victim->fd);
              else
            {
              REMOVE_FB (fb, pp, tc_victim);
              if (__glibc_unlikely (tc_victim == NULL))
                break;
            }
              tcache_put (tc_victim, tc_idx); // 将取出的chunk 放入tcache bin中
            }
        }
#endif
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes); // 辅助调试用的,默认不开启不用管
          return p;
        }
    }
    }

  /*
     如果是小内存请求,检查常规 bin(即 smallbin)。
     由于这些 'smallbins' 中的每一个都只存放一种固定大小的块,因此不需要在 bin 内部进行遍历搜索。
    (对于大内存请求,我们需要等待 unsorted chunks 被处理(整理)完,才能找到最佳匹配(best fit)。
     但对于小请求来说,反正匹配都是精确大小的,所以我们可以现在立刻检查,这样速度更快。)”
   */

  if (in_smallbin_range (nb)) //是否满足small bin的大小 (<= 0x3ff),满足的话走small bin分配
    {
      idx = smallbin_index (nb); // 获取对应大小的 smallbin的 idx
      bin = bin_at (av, idx); // 获取对应大小的small bin

      if ((victim = last (bin)) != bin) // 通过比较bin中的fd与bk是否相等,来判断bin是否为空
        {							 // 这里我们可以看出small bin是从链表尾部开始查找的
          bck = victim->bk;
      if (__glibc_unlikely (bck->fd != victim)) // 安全性检查 victim->bk->fd == victim
        malloc_printerr ("malloc(): smallbin double linked list corrupted");
          set_inuse_bit_at_offset (victim, nb);
          bin->bk = bck;  // 取走victim后,将bck与bins进行链接
          bck->fd = bin;

          if (av != &main_arena)
        set_non_main_arena (victim);
          check_malloced_chunk (av, victim, nb);
#if USE_TCACHE
      /* 尝试把 small bin 中的chunk放入到tcache bin中,与fastbin同理*/
      size_t tc_idx = csize2tidx (nb);
      if (tcache && tc_idx < mp_.tcache_bins)
        {
          mchunkptr tc_victim;

          /* While bin not empty and tcache not full, copy chunks over.  */
          while (tcache->counts[tc_idx] < mp_.tcache_count
             && (tc_victim = last (bin)) != bin)
        {
          if (tc_victim != 0)
            {
              bck = tc_victim->bk;
              set_inuse_bit_at_offset (tc_victim, nb);
              if (av != &main_arena)
            set_non_main_arena (tc_victim);
              bin->bk = bck;
              bck->fd = bin;

              tcache_put (tc_victim, tc_idx);
                }
        }
        }
#endif
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }

  /*
    如果这是一个大内存请求,在继续后续步骤之前,先整理(合并)fastbins。
    虽然在确认是否有可用空间之前就清空所有 fastbins 看起来有些‘过度’(或是多此一举),
    但这避免了通常与 fastbins 相关的内存碎片问题。
    此外,在实际运行中,程序往往倾向于连续发起小额请求或连续发起大额请求,而混合交替的情况较少	
    因此在大多数程序中,这种合并操作并不会被频繁触发。
    而对于那些确实频繁触发该操作的程序,它们本身往往就倾向于产生严重的内存碎片。  
  */

  else
    {
      idx = largebin_index (nb);
      if (atomic_load_relaxed (&av->have_fastchunks))
        malloc_consolidate (av); // 合并 chunk 此函数比较重要会下面详细分析
    }

  /*
    处理最近释放的或切割剩余的 chunks。只有在以下情况才直接选用该 chunk:
    1、它的大小与请求精确匹配(exact fit);
    2、或者,如果这是一个小内存请求(small request),且该 chunk 是最近一次非精确匹配分割后产生的剩		余块。
    将其他遍历到的 chunks 放入其对应的 bin 中。请注意,这一步是所有流程中唯一会将 chunks 放回 bin		(指 Small/Large Bins)的地方。
    这里之所以需要外层循环,是因为我们可能直到 malloc 流程快结束时,才意识到本应该先进行碎片整理(合	并),因此必须执行合并操作并重试。这种情况最多发生一次,且仅在我们需要通过扩展内存(如使用 Top 	  Chunk)来满足一个‘小’内存请求时才会触发
   */
// 为后续将遍历到的 unsorted bin 放入到 tcache bin中
#if USE_TCACHE
  INTERNAL_SIZE_T tcache_nb = 0;
  size_t tc_idx = csize2tidx (nb);
  if (tcache && tc_idx < mp_.tcache_bins)
    tcache_nb = nb;
  int return_cached = 0; // 标志位,如果成功放入tcache中,后续直接从tcache里取一块给用户

  tcache_unsorted_count = 0; // 计数器,统计放入tcache 的堆块的数量
#endif

  for (;; )
    {
      int iters = 0;
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        { // 这里可以看到 unsorted bin 与 small bin 一样是从 bin->bk 开始向后遍历
          bck = victim->bk;
          size = chunksize (victim);
          mchunkptr next = chunk_at_offset (victim, size); //获取victim地址上的下一个chunk

          if (__glibc_unlikely (size <= CHUNK_HDR_SZ) // 检查取出来的 victim 的size
              || __glibc_unlikely (size > av->system_mem))
            malloc_printerr ("malloc(): invalid size (unsorted)");
          if (__glibc_unlikely (chunksize_nomask (next) < CHUNK_HDR_SZ) //检查next的size合法性
              || __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
            malloc_printerr ("malloc(): invalid next size (unsorted)");
          if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size)) //检查prev_size
            malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
          if (__glibc_unlikely (bck->fd != victim) // bck 的 fd 一定等于 victim
              || __glibc_unlikely (victim->fd != unsorted_chunks (av)))//victim->fd一定等于bin
            malloc_printerr ("malloc(): unsorted double linked list corrupted");
          if (__glibc_unlikely (prev_inuse (next))) // 检查prev_inuse位
            malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

          /*
            如果是小内存请求(small request),且 Unsorted Bin 中仅有一个且刚刚被切割过的 chunk,
            那么尝试直接使用它。
            这有助于提升连续的一系列小内存请求的空间局部性
            这是对‘最佳匹配’策略的唯一例外,且仅在小内存请求无法找到大小精确匹配的块时才会应用
           */

          if (in_smallbin_range (nb) && // 是否为小内存请求
              bck == unsorted_chunks (av) && // unsorted bin中是否只有一个 chunk
              victim == av->last_remainder && // 这个chunk是否刚刚被切割过
              (unsigned long) (size) > (unsigned long) (nb + MINSIZE)) // chunk大小是否满足
            {
              /* 分割 chunk 并将剩余部分重新接入链表 */
              remainder_size = size - nb; // 切割后的 size
              remainder = chunk_at_offset (victim, nb); // 切割后 chunk 地址
              unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder; // 链接 chunk
              av->last_remainder = remainder; // 更新arena中的 last_remainder
              remainder->bk = remainder->fd = unsorted_chunks (av); // 链接到 unsorted bin
              if (!in_smallbin_range (remainder_size)) // 这里置零是为了防止在后面unlink时误判
                {									// 以为是large bin中的unlink导致崩溃
                  remainder->fd_nextsize = NULL;
                  remainder->bk_nextsize = NULL;
                }

              set_head (victim, nb | PREV_INUSE |  // 设置 victim chunk的chunk 头
                        (av != &main_arena ? NON_MAIN_ARENA : 0));
              set_head (remainder, remainder_size | PREV_INUSE); // 设置remainder的chunk头
              set_foot (remainder, remainder_size); // 设置 remainder的next的 prev_size

              check_malloced_chunk (av, victim, nb); // 对 victim chunk做检查
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }

          /* 从 unsorted bin 中移除 */
          if (__glibc_unlikely (bck->fd != victim)) // bck 的 fd 一定等于 victim
            malloc_printerr ("malloc(): corrupted unsorted chunks 3");
          unsorted_chunks (av)->bk = bck; // 这两步就是将 victim 移出 bin,并将victim->bk接入 
          bck->fd = unsorted_chunks (av);

          /* 如果精准匹配就直接取出 */

          if (size == nb)
            {
              set_inuse_bit_at_offset (victim, size); // 被取出的话就不是free状态了,设置inuse位
              if (av != &main_arena)
        set_non_main_arena (victim);
#if USE_TCACHE
          /* 先放入 tcache bin */
          if (tcache_nb
          && tcache->counts[tc_idx] < mp_.tcache_count)
        {
          tcache_put (victim, tc_idx);
          return_cached = 1;
          continue;
        }
          else
        {
#endif       //当tcache bin满了,大小不合适或者没有开启 tcache时,直接返回给 user
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
#if USE_TCACHE
        }
#endif
            }

          /* 将chunk放入bin中 */

          if (in_smallbin_range (size))
            {
              victim_index = smallbin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;
            }
          else
            {
              victim_index = largebin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;

              /* 保持 large bins 处于有序状态  */
              if (fwd != bck)
                {
                  /*  将大小与 PREV_INUSE 位进行“或”运算,以加速比较 */
                  size |= PREV_INUSE;
                  /* 如果比 bin 里最小的还要小,则跳过下面的搜索循环(Large Bin是按从大到小排序) */
                  assert (chunk_main_arena (bck->bk));
                  if ((unsigned long) (size)
              < (unsigned long) chunksize_nomask (bck->bk))
                    {
                      fwd = bck; // fwd变成了bin头
                      bck = bck->bk; // bck变成原来的最小块

                      victim->fd_nextsize = fwd->fd; // fwd->fd 是链表头(最大的块)
                      victim->bk_nextsize = fwd->fd->bk_nextsize; // 指向原来的最小块
                      fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
                    } // 最大块的 bk_nextsize和原来最小块的 fd_nextsize指向 victim
                  else
                    {
                      assert (chunk_main_arena (fwd));
                      while ((unsigned long) size < chunksize_nomask (fwd))
                        {
                          fwd = fwd->fd_nextsize; // 利用fd_nextsize进行跳跃式搜索
              assert (chunk_main_arena (fwd));
                        }

                      if ((unsigned long) size
              == (unsigned long) chunksize_nomask (fwd)) //如果插入点与victim大小正好相等
                        /* 始终插入到第二个位置(这样就不用修改其他chunk上的nextsize)  */
                        fwd = fwd->fd;
                      else // 新的大小插入点
                        { //链接 nextsize 指针
                          victim->fd_nextsize = fwd; 
                          victim->bk_nextsize = fwd->bk_nextsize;
                          if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
                            malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
                          fwd->bk_nextsize = victim; // 双向绑定
                          victim->bk_nextsize->fd_nextsize = victim;
                        }
                      bck = fwd->bk;
                      if (bck->fd != fwd)
                        malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
                    }
                }
              else //  large bin为空的情况
                victim->fd_nextsize = victim->bk_nextsize = victim;
            }
         // 前面的逻辑是维护nextsize指针,下面是维护fd和bk指针
          mark_bin (av, victim_index); // 标记 binmap
          victim->bk = bck;  // 将victim接入双向链表
          victim->fd = fwd;
          fwd->bk = victim;
          bck->fd = victim;

#if USE_TCACHE
      /* 如果在填充缓存 tcache 的过程中,我们要处理的 chunk 数量已经达到了允许的上限,
      那么停止遍历,直接从缓存中取出一个返回给用户  */
      ++tcache_unsorted_count;
      if (return_cached
      && mp_.tcache_unsorted_limit > 0
      && tcache_unsorted_count > mp_.tcache_unsorted_limit)
    {
      return tcache_get (tc_idx);
    }
#endif

#define MAX_ITERS       10000
          if (++iters >= MAX_ITERS) // 如果达到最大遍历数了,停止遍历
            break;
        }

#if USE_TCACHE
      /* 如果我们找到的所有小块最终都被放入了缓存(Tcache)中,那么现在就从缓存中取出一个返回  */
      if (return_cached)
    {
      return tcache_get (tc_idx);
    }
#endif

      /*
         如果是大内存请求,则按有序顺序扫描当前 bin 中的 chunks,以寻找能满足要求的最小 chunk
         使用跳表(skip list)来执行此操作
       */

      if (!in_smallbin_range (nb))
        {
          bin = bin_at (av, idx); // 获取 large bin

          /* 如果large bin是空的,或者里面最大的chunk小于victim就跳过搜索 */
          if ((victim = first (bin)) != bin
          && (unsigned long) chunksize_nomask (victim) // 从large bin的fd也就最大的chunk开始找
            >= (unsigned long) (nb))                   // 直到找到满足要求的最小 chunk
            {                        
              victim = victim->bk_nextsize;
              while (((unsigned long) (size = chunksize (victim)) <
                      (unsigned long) (nb))) // 使用 bk_nextsize 由大到小进行跳跃搜索
                victim = victim->bk_nextsize;

              /* 避免移除同种大小chunk中的第一个条目
                 这样就不需要重新修改跳表指针。*/
              if (victim != last (bin)
          && chunksize_nomask (victim)
            == chunksize_nomask (victim->fd))
                victim = victim->fd; // 选用victim->fd作为victim

              remainder_size = size - nb; 
              unlink_chunk (av, victim); // 将 victim unlink,这是个关键的函数下面会重点讲

              /* 耗尽 */
              if (remainder_size < MINSIZE) //剩下的size小于0x20,就把多余的也给user
                {
                  set_inuse_bit_at_offset (victim, size); // 设置地址相邻的next的prev_use位
                  if (av != &main_arena)
            set_non_main_arena (victim);
                }
              /* 切割 */
              else // 切完后剩下的chunk会放入 unsorted bin
                {
                  remainder = chunk_at_offset (victim, nb); // 获取到remainder的内存地址
                  /* 我们不能假设unsorted list是空的,
                     因此必须在这里执行一次完整的插入操作  */
                  bck = unsorted_chunks (av); // 获取unsorted bin
                  fwd = bck->fd; // 获取unsorted bin中第一个chunk
          if (__glibc_unlikely (fwd->bk != bck)) // 检查
            malloc_printerr ("malloc(): corrupted unsorted chunks");
                  remainder->bk = bck; // 这四个操作就是将remainder链接到unsorted bin中
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;
                  if (!in_smallbin_range (remainder_size)) // 同上为了防止unlink误判
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_nextsize = NULL;
                    }
                  set_head (victim, nb | PREV_INUSE |  // 设置chunk头和prev_size,然后返回
                            (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;
            }
        }

      /*
        通过扫描 bins 来搜寻 chunk,从(比当前请求大小)更大一级的 bin 开始。
        这种搜索严格遵循‘最佳匹配(best-fit)’原则;即,选择能够满足要求且大小最小的那个 chunk
        (如果有多个大小相同的 chunk,则倾向于选择大约最久未被使用的那个)。
        使用位图(bitmap)避免了去检查大多数为空的 bin。
        特别是在程序的‘预热’阶段(warm-up phases),此时尚未有 chunk 被释放归还,(利用位图)跳过		所有 bin 的操作实际上比看起来要快得多
       */

      ++idx;
      bin = bin_at (av, idx);
      block = idx2block (idx);
      map = av->binmap[block];
      bit = idx2bit (idx);

      for (;; )
        {
          /* 如果当前 block 中没有更多被置为 1 的位,则跳过此block,直接开始遍历后面的block  */
          if (bit > map || bit == 0)
            {
              do
                {
                  if (++block >= BINMAPSIZE) /* 超出bins范围 */
                    goto use_top;			/* 遍历完了都没找到,就只能用top chunk分配 */
                }
              while ((map = av->binmap[block]) == 0);

              bin = bin_at (av, (block << BINMAPSHIFT)); // 获取block的起始bin
              bit = 1; // 重置bit掩码,准备从该block的第0位开始寻找
            }

          /* 推进到 bit 被置为 1 的那个 bin。肯定能找到一个(因为 map != 0) */
          while ((bit & map) == 0)
            {
              bin = next_bin (bin);
              bit <<= 1;
              assert (bit != 0);
            }

          /* 检查取出来的bin,他很可能不是空的bin */
          victim = last (bin);

          /*  如果是假的(bin为空),就清空这个bin的bit位 */
          if (victim == bin)
            {
              av->binmap[block] = map &= ~bit; /* Write through */
              bin = next_bin (bin); // 既然是空,那就继续找下一个bin
              bit <<= 1; // 掩码继续左移
            }

          else
            {
              size = chunksize (victim);

              /* 找到的第一个 chunk 肯定比 nb 大 */
              assert ((unsigned long) (size) >= (unsigned long) (nb));
              // 接下来的操作跟large bin 中的切割操作差不多了
              remainder_size = size - nb;

              /* unlink */
              unlink_chunk (av, victim);

              /* 耗尽 */
              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
            set_non_main_arena (victim);
                }

              /* 切割 */
              else  // 走到此分支说明从bin中找到了合适的chunk
                {
                  remainder = chunk_at_offset (victim, nb);

                  /* 我们不能假设unsorted bin是空的,
                     因此我们必须在这里执行一次完全的插入  */
                  bck = unsorted_chunks (av); // 获取unsorted bin
                  fwd = bck->fd; // 获取原来unsorted bin中的chunk(假设unsorted bin是非空的)
          if (__glibc_unlikely (fwd->bk != bck))
            malloc_printerr ("malloc(): corrupted unsorted chunks 2");
                  remainder->bk = bck;  // 经典的四步操作将remainder链接到unsorted bin中
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;

                  /* 更新为 last remainder */
                  /* 此外这里也可以看出arena中last remainder,只能是unsorted bin中chunk */
                  if (in_smallbin_range (nb))
                    av->last_remainder = remainder; // 更新arena中的last_remainder
                  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);
              alloc_perturb (p, bytes);
              return p;
            }
        }

    use_top:
      /*
         如果(Top Chunk)足够大,就从这个位于内存末端的 chunk(保存在 av->top 中)分割出一部分。
        请注意,这实际上是符合‘最佳匹配(best-fit)’搜索规则的。
        实际上,av->top 被视为比任何其他可用的 chunk 都要大(因此匹配度也最低/最不适合)
        因为它的大小可以根据需要无限扩展(直到达到系统的限制)。
        我们要求 av->top 在初始化后必须始终存在(即其大小至少为 MINSIZE)。
        如果当前请求会导致 Top Chunk 被完全耗尽,我们就会对其进行补充(调用系统调用扩展堆内存)。
        (确保它存在的首要原因是,我们在调用 sysmalloc 扩展内存时,可能需要 MINSIZE 大小的空间来放			置‘栅栏桩/哨兵块’(fenceposts)以维持内存结构。)
       */

      victim = av->top;  // 获取top chunk
      size = chunksize (victim); 

      if (__glibc_unlikely (size > av->system_mem))
        malloc_printerr ("malloc(): corrupted top size");

      if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE)) 
        { // 如果top chunk 的大小满足要求就割一块给用户,切割的逻辑和之前差不多
          remainder_size = size - nb;
          remainder = chunk_at_offset (victim, nb);
          av->top = remainder; // 更新 top chunk
          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 chunks 时,对于所有大小的请求,代码执行流都可能到达此处  */
      else if (atomic_load_relaxed (&av->have_fastchunks)) // 检查fastbin是否为空
        {
          malloc_consolidate (av); // 有可能其他线程又释放了chunk到fastbin,因此将他们合并起来
          /* restore original bin index */
          if (in_smallbin_range (nb)) // 重新计算idx,然后程序跳回到214行处再次循环
            idx = smallbin_index (nb);
          else
            idx = largebin_index (nb);
        }

      /*
        否则转交(给 sysmalloc)去处理与系统底层相关的分配情况
       */
      else
        {
          void *p = sysmalloc (nb, av); // top chunk不够用,sysmalloc调用sbrk分配新的top chunk
          if (p != NULL)			   // 如果申请大小达到阈值,就直接用mmap分配不拓展top chunk
            alloc_perturb (p, bytes);
          return p;
        }
    }
}

总结:该函数是最核心的malloc分配逻辑,大体流程为 fastbin查找,small bin查找,unsorted bin查找,large bin 查找,然后就是再所有bin中寻找能够满足要求且大小最小的chunk进行切割,最后如果全部bin都没有满足要求的才从top chunk进行切割

tcache_put

这个函数实现了将chunk放入指定 tcache bin 中,其中涉及fd指针加密以及 tcache bin的double free检测机制,比较关键。

typedef struct tcache_entry
{
  struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  uintptr_t key;
} tcache_entry;

// 这里的加密机制是将存放fd的地址右移12位也就是 (&fd >> 12),然后再与fd指针异或,就得到了加密后的指针
// 解密就是再进行一次加密操作就好了
#define PROTECT_PTR(pos, ptr) \ 
  ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
#define REVEAL_PTR(ptr)  PROTECT_PTR (&ptr, ptr)

static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk); // chunk地址转为meta data的地址
                                                   // 并且强转为 tcache_entry 结构体
  /* 通过设置chunk的key(也就是bk字段),将chunk标记为已经free状态
      在free的时候可以通过这个检测double free。 */
  e->key = tcache_key; 

  /* 将tcache bin中原本的chunk地址加密并接到 e 的next字段中 */
  e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
  tcache->entries[tc_idx] = e; // 将新的chunk放到 tcache bin的头
  ++(tcache->counts[tc_idx]);
}

unlink_chunk

这个函数作用顾名思义就是将chunk unlink,其内部会自动判断chunk是否在 large bin中,并进行专门的设置

static void
unlink_chunk (mstate av, mchunkptr p)
{
  if (chunksize (p) != prev_size (next_chunk (p))) //检查unlink chunk(也就是p)的size是否合法
    malloc_printerr ("corrupted size vs. prev_size");

  mchunkptr fd = p->fd;  // 获取 fd
  mchunkptr bk = p->bk;  // 获取 bk

  if (__builtin_expect (fd->bk != p || bk->fd != p, 0)) // 双向链表的检查fd->bk 和 bk->fd都等于p
    malloc_printerr ("corrupted double-linked list");
  // 进行 unlink 操作
  fd->bk = bk;
  bk->fd = fd;
  if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL)
    {		// 检查是否是 Large Bin 中某个大小组的“头节点”(只有头节点才有 nextsize 指针		
      if (p->fd_nextsize->bk_nextsize != p  // 同上一样的检查,只不过换成了nextsize指针
      || p->bk_nextsize->fd_nextsize != p)
    malloc_printerr ("corrupted double-linked list (not small)");

      if (fd->fd_nextsize == NULL) // 检查 p->fd 是否不是头节点
    {
      if (p->fd_nextsize == p) // 判断 Large Bin 中是否只有p这一种大小的 chunk
        fd->fd_nextsize = fd->bk_nextsize = fd;
      else //将p->fd链接到nextsize指针中
        {
          fd->fd_nextsize = p->fd_nextsize;
          fd->bk_nextsize = p->bk_nextsize;
          p->fd_nextsize->bk_nextsize = fd;
          p->bk_nextsize->fd_nextsize = fd;
        }
    }
      else 
    { // 直接将p从nextsize指针中移除
      p->fd_nextsize->bk_nextsize = p->bk_nextsize;
      p->bk_nextsize->fd_nextsize = p->fd_nextsize;
    }
    }
}

malloc_consolidate

这个函数实现了合并fastbin中每一个chunk的功能,要么就是放入unsorted bin要么就是和top chunk合并

static void malloc_consolidate(mstate av)
{
  mfastbinptr*    fb;                 /* 当前被合并的fastbin */
  mfastbinptr*    maxfb;              /* 最后一个 fastbin 指针(用于循环控制,作为遍历的终点) */
  mchunkptr       p;                  /* 当前被合并的chunk */
  mchunkptr       nextp;              /* (链表中)下一个要合并整理的 chunk */
  mchunkptr       unsorted_bin;       /* unsorted bin 的头指针 */
  mchunkptr       first_unsorted;     /* 要链接到的 chunk(即unsorted bin中的第一个节点)*/

  /* 以下变量的用途与 free() 函数中的完全相同  */
  mchunkptr       nextchunk;		  /* 内存地址中相邻的下一个 chunk */
  INTERNAL_SIZE_T size;				 /* 当前 chunk 的大小 */
  INTERNAL_SIZE_T nextsize;			 /* 地址相邻下一个 chunk 的大小 */
  INTERNAL_SIZE_T prevsize;			 /* 地址相邻前一个 chunk 的大小 */
  int             nextinuse;		 /* 地址相邻下一个 chunk 的使用状态标志 */

  atomic_store_relaxed (&av->have_fastchunks, false);

  unsorted_bin = unsorted_chunks(av);

  /*
    将每个 chunk 从 fast bin 中移出并进行合并(整理),随后将其放入 unsorted bin 中。
    这样做(放入 unsorted bin)的诸多原因之一是:这避免了立即计算该 chunk 实际上该属于哪个 bin
    (指 	Small/Large Bin)的开销,除非 malloc 确信这些 chunks 不会被立即复用
  */

  maxfb = &fastbin (av, NFASTBINS - 1);
  fb = &fastbin (av, 0);
  do {
    p = atomic_exchange_acq (fb, NULL); // 获取fastbin的头指针,并清空fastbin
    if (p != 0) { // 遍历取出来的p的链表
      do {
    {
      if (__glibc_unlikely (misaligned_chunk (p))) // 检查的对齐
        malloc_printerr ("malloc_consolidate(): "
                 "unaligned fastbin chunk detected");

      unsigned int idx = fastbin_index (chunksize (p)); // 检查大小是否合法
      if ((&fastbin (av, idx)) != fb)
        malloc_printerr ("malloc_consolidate(): invalid chunk size");
    }

    check_inuse_chunk(av, p); // 检查确保chunk是inuse(fastbin和tcache中chunk不会改变inuse位)
    nextp = REVEAL_PTR (p->fd); // 解密获取 p 的fd

    /* Slightly streamlined version of consolidation code in free() */
    size = chunksize (p);
    nextchunk = chunk_at_offset(p, size);
    nextsize = chunksize(nextchunk);

    if (!prev_inuse(p)) { // 检查p 的prev_inuse位(向前合并)
      prevsize = prev_size (p);
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize)); // 将p赋值为前一个chunk的地址
      if (__glibc_unlikely (chunksize(p) != prevsize))
        malloc_printerr ("corrupted size vs. prev_size in fastbins");
      unlink_chunk (av, p); // 将前一个chunk解链
    }

    if (nextchunk != av->top) {  // 检查next chunk是不是top chunk,是的话就可以直接合并走else分支
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize); // 检查nextchunk是否为空闲状态

      if (!nextinuse) { // 是的话,向后合并
        size += nextsize;
        unlink_chunk (av, nextchunk);
      } else
        clear_inuse_bit_at_offset(nextchunk, 0); // 否则清空其的inuse位,因为p要进unsorted bin了
      /* 经典链接操作(这里有可能触发了向前合并也可能没取决于是否进入过了if (!prev_inuse(p))分支 )
      	 但是不管有没有向前合并,p都会进入unsorted bin) */
      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);
    }
    // 如果nextchunk是top chunk,那么p直接与top chunk合并不进入unsorted bin
    else {
      size += nextsize;
      set_head(p, size | PREV_INUSE);
      av->top = p;
    }

      } while ( (p = nextp) != 0); // 遍历p链表上的每一个chunk

    }
  } while (fb++ != maxfb); // 遍历每一个fastbin
}

参考文章:https://arttnba3.cn/2021/01/15/GLIBC-0X00-MALLOC-2.23-PART-I/

​

​