Glibc内存管理--ptmalloc2源代码分析（二十七）

5.7.2.3 分配large bin chunk（一）

如果所需的 chunk 不属于 small bins ，首先会执行如下的代码段：

/*
     If this is a large request, consolidate fastbins before continuing.
     While it might look excessive to kill all fastbins before
     even seeing if there is space available, this avoids
     fragmentation problems normally associated with fastbins.
     Also, in practice, programs tend to have runs of either small or
     large requests, but less often mixtures, so consolidation is not
     invoked all that often in most programs. And the programs that
     it is called frequently in otherwise tend to fragment.
  */

  else {
    idx = largebin_index(nb);
    if (have_fastchunks(av))
      malloc_consolidate(av);
  }

 所需chunk 不属于 small bins ，那么就一定属于 large bins ，首先根据 chunk 的大小获得对应的 large bin 的 index ，接着判断当前分配区的 fast bins 中是否包含 chunk ，如果存在，调用 malloc_consolidate() 函数合并 fast bins 中的 chunk ，并将这些空闲 chunk 加入 unsorted bin 中。

下面的源代码实现从 last remainder chunk ， large bins 和 top chunk 中分配所需的 chunk ，这里包含了多个多层循环，在这些循环中，主要工作是分配前两步都未分配成功的 small bin chunk ， large bin chunk 和 large chunk 。最外层的循环用于重新尝试分配 small bin chunk ，因为如果在前一步分配 small bin chunk 不成功，并没有调用 malloc_consolidate() 函数合并 fast bins 中的 chunk ，将空闲 chunk 加入 unsorted bin 中，如果第一尝试从 last remainder chunk ， top chunk 中分配 small bin chunk 都失败以后，如果 fast bins 中存在空闲 chunk ，会调用 malloc_consolidate() 函数，那么在 usorted bin 中就可能存在合适的 small bin chunk 供分配，所以需要再次尝试。

 /*
    Process recently freed or remaindered chunks, taking one only if
    it is exact fit, or, if this a small request, the chunk is remainder from
    the most recent non-exact fit.  Place other traversed chunks in
    bins.  Note that this step is the only place in any routine where
    chunks are placed in bins.

    The outer loop here is needed because we might not realize until
    near the end of malloc that we should have consolidated, so must
    do so and retry. This happens at most once, and only when we would
    otherwise need to expand memory to service a "small" request.
  */
  for(;;) {
    int iters = 0;
while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
反向遍历unsorted bin的双向循环链表，遍历结束的条件是循环链表中只剩下一个头结点。

      bck = victim->bk;
      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));
      size = chunksize(victim);

 检查当前遍历的 chunk 是否合法， chunk 的大小不能小于等于 2 * SIZE_SZ ，也不能超过该分配区总的内存分配量。然后获取 chunk 的大小并赋值给 size 。这里的检查似乎有点小问题，直接使用了 victim->size ，但 victim->size 中包含了相关的标志位信息，使用 chunksize(victim) 才比较合理，但在 unsorted bin 中的空闲 chunk 的所有标志位都清零了，所以这里直接 victim->size 没有问题。

 /*
         If a small request, try to use last remainder if it is the
         only chunk in unsorted bin.  This helps promote locality for
         runs of consecutive small requests. This is the only
         exception to best-fit, and applies only when there is
         no exact fit for a small chunk.
      */
      if (in_smallbin_range(nb) &&
          bck == unsorted_chunks(av) &&
          victim == av->last_remainder &&
          (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {

 如果需要分配一个 small bin chunk ，在 5.7.2.2 节中的 small bins 中没有匹配到合适的 chunk ，并且 unsorted bin 中只有一个 chunk ，并且这个 chunk 为 last remainder chunk ，并且这个 chunk 的大小大于所需 chunk 的大小加上 MINSIZE ，在满足这些条件的情况下，可以使用这个 chunk 切分出需要的 small bin chunk 。这是唯一的从 unsorted bin 中分配 small bin chunk 的情况，这种优化利于 cpu 的高速缓存命中。

 /* split and reattach remainder */
        remainder_size = size - nb;
        remainder = chunk_at_offset(victim, nb);
        unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = 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 中切分出所需大小的 chunk ，计算切分后剩下 chunk 的大小，将剩下的 chunk 加入 unsorted bin 的链表中，并将剩下的 chunk 作为分配区的 last remainder chunk ，若剩下的 chunk 属于 large bin chunk ，将该 chunk 的 fd_nextsize 和 bk_nextsize 设置为 NULL ，因为这个 chunk 仅仅存在于 unsorted bin 中，并且 unsorted bin 中有且仅有这一个 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);
        if (__builtin_expect (perturb_byte, 0))
          alloc_perturb (p, bytes);
        return p;

 设置分配出的 chunk 和 last remainder chunk 的相关信息，如 chunk 的 size ，状态标志位，对于 last remainder chunk ，需要调用 set_foot 宏，因为只有处于空闲状态的 chunk 的 foot 信息（ prev_size ）才是有效的，处于 inuse 状态的 chunk 的 foot 无效，该 foot 是返回给应用层的内存块的一部分。设置完成 chunk 的相关信息，调用 chunk2mem() 获得 chunk 中可用的内存指针，返回给应用层，退出。

      }

      /* remove from unsorted list */
      unsorted_chunks(av)->bk = bck;
      bck->fd = unsorted_chunks(av);
将双向循环链表中的最后一个chunk移除。

      /* Take now instead of binning if exact fit */
      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);
        if (__builtin_expect (perturb_byte, 0))
          alloc_perturb (p, bytes);
        return p;
      }

 如果当前遍历的 chunk 与所需的 chunk 大小一致，将当前 chunk 返回。首先设置当前 chunk 处于 inuse 状态，该标志位处于相邻的下一个 chunk 的 size 中，如果当前分配区不是主分配区，设置当前 chunk 的非主分配区标志位，最后调用 chunk2mem() 获得 chunk 中可用的内存指针，返回给应用层，退出。

      /* place chunk in bin */
      if (in_smallbin_range(size)) {
        victim_index = smallbin_index(size);
        bck = bin_at(av, victim_index);
        fwd = bck->fd;
如果当前chunk属于small bins，获得当前chunk所属small bin的index，并将该small bin的链表表头赋值给bck，第一个chunk赋值给fwd，也就是当前的chunk会插入到bck和fwd之间，作为small bin链表的第一个chunk。

      }
      else {
        victim_index = largebin_index(size);
        bck = bin_at(av, victim_index);
        fwd = bck->fd;
如果当前chunk属于large bins，获得当前chunk所属large bin的index，并将该large bin的链表表头赋值给bck，第一个chunk赋值给fwd，也就是当前的chunk会插入到bck和fwd之间，作为large bin链表的第一个chunk。

        /* maintain large bins in sorted order */
        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);

 如果fwd 不等于 bck ，意味着 large bin 中有空闲 chunk 存在，由于 large bin 中的空闲 chunk 是按照大小顺序排序的，需要将当前从 unsorted bin 中取出的 chunk 插入到 large bin 中合适的位置。将当前 chunk 的 size 的 inuse 标志 bit 置位，相当于加 1 ，便于加快 chunk 大小的比较，找到合适的地方插入当前 chunk 。这里还做了一次检查，断言在 large bin 双向循环链表中的最后一个 chunk 的 size 字段中的非主分配区的标志 bit 没有置位，因为所有在 large bin 中的 chunk 都处于空闲状态，该标志位一定是清零的。

         if ((unsigned long)(size) < (unsigned long)(bck->bk->size)) {
            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;

 如果当前 chunk 比 large bin 的最后一个 chunk 的大小还小，那么当前 chunk 就插入到 large bin 的链表的最后，作为最后一个 chunk 。可以看出 large bin 中的 chunk 是按照从大到小的顺序排序的，同时一个 chunk 存在于两个双向循环链表中，一个链表包含了 large bin 中所有的 chunk ，另一个链表为 chunk size 链表，该链表从每个相同大小的 chunk 的取出第一个 chunk 按照大小顺序链接在一起，便于一次跨域多个相同大小的 chunk 遍历下一个不同大小的 chunk ，这样可以加快在 large bin 链表中的遍历速度。

         }
          else {
            assert((fwd->size & NON_MAIN_ARENA) == 0);
            while ((unsigned long) size < fwd->size)
              {
                fwd = fwd->fd_nextsize;
                assert((fwd->size & NON_MAIN_ARENA) == 0);
              }
	正向遍历chunk size链表，直到找到第一个chunk大小小于等于当前chunk大小的chunk退出循环。

            if ((unsigned long) size == (unsigned long) fwd->size)
              /* Always insert in the second position.  */
              fwd = fwd->fd;
如果从large bin链表中找到了与当前chunk大小相同的chunk，则同一大小的chunk已经存在，那么chunk size链表中一定包含了fwd所指向的chunk，为了不修改chunk size链表，当前chunk只能插入fwd之后。

            else
              {
                victim->fd_nextsize = fwd;
                victim->bk_nextsize = fwd->bk_nextsize;
                fwd->bk_nextsize = victim;
                victim->bk_nextsize->fd_nextsize = victim;
如果chunk size链表中还没有包含当前chunk大小的chunk，也就是说当前chunk的大小大于fwd的大小，则将当前chunk作为该chunk size的代表加入chunk size链表，chunk size链表也是按照由大到小的顺序排序。

              }
            bck = fwd->bk;
          }
        } else
          victim->fd_nextsize = victim->bk_nextsize = victim;
如果large bin链表中没有chunk，直接将当前chunk加入chunk size链表。
      }

      mark_bin(av, victim_index);
      victim->bk = bck;
      victim->fd = fwd;
      fwd->bk = victim;
      bck->fd = victim;
上面的代码将当前chunk插入到large bin的空闲chunk链表中，并将large bin所对应binmap的相应bit置位。

#define MAX_ITERS       10000
      if (++iters >= MAX_ITERS)
        break;
如果unsorted bin中的chunk超过了10000个，最多遍历10000个就退出，避免长时间处理unsorted bin影响内存分配的效率。
    }

当将unsorted bin中的空闲chunk加入到相应的small bins和large bins后，将使用最佳匹配法分配large bin chunk。源代码如下：
    /*
      If a large request, scan through the chunks of current bin in
      sorted order to find smallest that fits.  Use the skip list for this.
    */
    if (!in_smallbin_range(nb)) {
      bin = bin_at(av, idx);

      /* skip scan if empty or largest chunk is too small */
      if ((victim = first(bin)) != bin &&
          (unsigned long)(victim->size) >= (unsigned long)(nb)) {
如果所需分配的chunk为large bin chunk，查询对应的large bin链表，如果large bin链表为空，或者链表中最大的chunk也不能满足要求，则不能从large bin中分配。否则，遍历large bin链表，找到合适的chunk。

        victim = victim->bk_nextsize;
        while (((unsigned long)(size = chunksize(victim)) <
                (unsigned long)(nb)))
          victim = victim->bk_nextsize;
反向遍历chunk size链表，直到找到第一个大于等于所需chunk大小的chunk退出循环。

        /* Avoid removing the first entry for a size so that the skip
           list does not have to be rerouted.  */
        if (victim != last(bin) && victim->size == victim->fd->size)
          victim = victim->fd;

 如果从 large bin 链表中选取的 chunk victim 不是链表中的最后一个 chunk ，并且与 victim 大小相同的 chunk 不止一个，那么意味着 victim 为 chunk size 链表中的节点，为了不调整 chunk size 链表，需要避免将 chunk size 链表中的节点取出，所以取 victim->fd 节点对应的 chunk 作为候选 chunk 。由于 large bin 链表中的 chunk 也是按大小排序，同一大小的 chunk 有多个时，这些 chunk 必定排在一起，所以 victim->fd 节点对应的 chunk 的大小必定与 victim 的大小一样。

        remainder_size = size - nb;
        unlink(victim, bck, fwd);
计算将victim切分后剩余大小，并调用unlink()宏函数将victim从large bin链表中取出。

        /* Exhaust */
        if (remainder_size < MINSIZE)  {
          set_inuse_bit_at_offset(victim, size);
          if (av != &main_arena)
            victim->size |= NON_MAIN_ARENA;

 如果将 victim 切分后剩余大小小于 MINSIZE ，则将真个 victim 分配给应用层，这种情况下，实际分配的 chunk 比所需的 chunk 要大一些。以 64 位系统为例， remainder_size 的可能大小为 0 和 16 ，如果为 0 ，表示 victim 的大小刚好等于所需 chunk 的大小，设置 victim 的 inuse 标志， inuse 标志位于下一个相邻的 chunk 的 size 字段中。如果 remainder_size 为 16 ，则这 16 字节就浪费掉了。 如果当前分配区不是主分配区， 将 victim 的 size 字段中的非主分配区标志置位。

        }
        /* Split */
        else {
          remainder = chunk_at_offset(victim, nb);
          /* We cannot assume the unsorted list is empty and therefore
             have to perform a complete insert here.  */
          bck = unsorted_chunks(av);
          fwd = bck->fd;
          if (__builtin_expect (fwd->bk != bck, 0))
            {
              errstr = "malloc(): corrupted unsorted chunks";
              goto errout;
            }
          remainder->bk = bck;
          remainder->fd = fwd;
          bck->fd = remainder;
          fwd->bk = remainder;
          if (!in_smallbin_range(remainder_size))
            {
              remainder->fd_nextsize = NULL;
              remainder->bk_nextsize = NULL;
            }
从victim中切分出所需的chunk，剩余部分作为一个新的chunk加入到unsorted bin中。如果剩余部分chunk属于large bins，将剩余部分chunk的chunk size链表指针设置为NULL，因为unsorted bin中的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);
设置victim和remainder的状态，由于remainder为空闲chunk，所以需要设置该chunk的foot。

        }
        check_malloced_chunk(av, victim, nb);
        void *p = chunk2mem(victim);
        if (__builtin_expect (perturb_byte, 0))
          alloc_perturb (p, bytes);
        return p;
	从large bin中使用最佳匹配法找到了合适的chunk，调用chunk2mem()获得chunk中可用的内存指针，返回给应用层，退出。
      }
    }