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

5.7.2.3 分配large bin chunk（二）

 如果通过上面的方式从最合适的 small bin 或 large bin 中都没有分配到需要的 chunk ，则查看比当前 bin 的 index 大的 small bin 或 large bin 是否有空闲 chunk 可利用来分配所需的 chunk 。源代码实现如下

/*
      Search for a chunk by scanning bins, starting with next largest
      bin. This search is strictly by best-fit; i.e., the smallest
      (with ties going to approximately the least recently used) chunk
      that fits is selected.

      The bitmap avoids needing to check that most blocks are nonempty.
      The particular case of skipping all bins during warm-up phases
      when no chunks have been returned yet is faster than it might look.
    */
    ++idx;
    bin = bin_at(av,idx);
    block = idx2block(idx);
    map = av->binmap[block];
    bit = idx2bit(idx);

  获取下一个相邻 bin 的空闲 chunk 链表，并获取该 bin 对于 binmap 中的 bit 位的值。 Binmap 中的标识了相应的 bin 中是否有空闲 chunk 存在。 Binmap 按 block 管理，每个 block 为一个 int ，共 32 个 bit ，可以表示 32 个 bin 中是否有空闲 chunk 存在。使用 binmap 可以加快查找 bin 是否包含空闲 chunk 。这里只查询比所需 chunk 大的 bin 中是否有空闲 chunk 可用。

    for (;;) {
      /* Skip rest of block if there are no more set bits in this block.  */
      if (bit > map || bit == 0) {
        do {
          if (++block >= BINMAPSIZE)  /* out of bins */
            goto use_top;
        } while ( (map = av->binmap[block]) == 0);

        bin = bin_at(av, (block << BINMAPSHIFT));
        bit = 1;
      }

 Idx2bit() 宏将 idx 指定的位设置为 1 ，其它位清零， map 表示一个 block （ unsigned int ）值，如果 bit 大于 map ，意味着 map 为 0 ，该 block 所对应的所有 bins 中都没有空闲 chunk ，于是遍历 binmap 的下一个 block ，直到找到一个不为 0 的 block 或者遍历完所有的 block 。退出循环遍历后，设置 bin 指向 block 的第一个 bit 对应的 bin ，并将 bit 置为 1 ，表示该 block 中 bit 1 对应的 bin ，这个 bin 中如果有空闲 chunk ，该 chunk 的大小一定满足要求。

      /* Advance to bin with set bit. There must be one. */
      while ((bit & map) == 0) {
        bin = next_bin(bin);
        bit <<= 1;
        assert(bit != 0);
      }
在一个block遍历对应的bin，直到找到一个bit不为0退出遍历，则该bit对于的bin中有空闲chunk存在。

      /* Inspect the bin. It is likely to be non-empty */
      victim = last(bin);
将bin链表中的最后一个chunk赋值为victim。

      /*  If a false alarm (empty bin), clear the bit. */
      if (victim == bin) {
        av->binmap[block] = map &= ~bit; /* Write through */
        bin = next_bin(bin);
        bit <<= 1;
如果victim与bin链表头指针相同，表示该bin中没有空闲chunk，binmap中的相应位设置不准确，将binmap的相应bit位清零，获取当前bin下一个bin，将bit移到下一个bit位，即乘以2。

      }
      else {
        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(victim, bck, fwd);
当前bin中的最后一个chunk满足要求，获取该chunk的大小，计算切分出所需chunk后剩余部分的大小，然后将victim从bin的链表中取出。

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

 如果剩余部分的大小小于 MINSIZE ，将整个 chunk 分配给应用层，设置 victim 的状态为 inuse ，如果当前分配区为非主分配区，设置 victim 的非主分配区标志位。

        }
        /* 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 2";
              goto errout;
            }
          remainder->bk = bck;
          remainder->fd = fwd;
          bck->fd = remainder;
          fwd->bk = remainder;

          /* advertise as last 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 中切分出所需的 chunk ，剩余部分作为一个新的 chunk 加入到 unsorted bin 中。如果剩余部分 chunk 属于 small bins ，将分配区的 last remainder chunk 设置为剩余部分构成的 chunk ；如果剩余部分 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;
	调用chunk2mem()获得chunk中可用的内存指针，返回给应用层，退出。
      }
    }

 如果从所有的 bins 中都没有获得所需的 chunk ，可能的情况为 bins 中没有空闲 chunk ，或者所需的 chunk 大小很大，下一步将尝试从 top chunk 中分配所需 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.)
    */
    victim = av->top;
    size = chunksize(victim);
将当前分配区的top chunk赋值给victim，并获得victim的大小。

    if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {
      remainder_size = size - nb;
      remainder = chunk_at_offset(victim, nb);
      av->top = remainder;
      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);
      if (__builtin_expect (perturb_byte, 0))
        alloc_perturb (p, bytes);
      return p;
    }

 由于top chunk 切分出所需 chunk 后，还需要 MINSIZE 的空间来作为 fencepost ，所需必须满足 top chunk 的大小大于所需 chunk 的大小加上 MINSIZE 这个条件，才能从 top chunk 中分配所需 chunk 。从 top chunk 切分出所需 chunk 的处理过程跟前面的 chunk 切分类似，不同的是，原 top chunk 切分后的剩余部分将作为新的 top chunk ，原 top chunk 的 fencepost 仍然作为新的 top chunk 的 fencepost ，所以切分之后剩余的 chunk 不用 set_foot 。

#ifdef ATOMIC_FASTBINS
    /* When we are using atomic ops to free fast chunks we can get
       here for all block sizes.  */
    else if (have_fastchunks(av)) {
      malloc_consolidate(av);
      /* restore original bin index */
      if (in_smallbin_range(nb))
        idx = smallbin_index(nb);
      else
        idx = largebin_index(nb);
}

 如果top chunk 也不能满足要求，查看 fast bins 中是否有空闲 chunk 存在，由于开启了 ATOMIC_FASTBINS 优化情况下， free 属于 fast bins 的 chunk 时不需要获得分配区的锁，所以在调用 _int_malloc() 函数时，有可能有其它线程已经向 fast bins 中加入了新的空闲 chunk ，也有可能是所需的 chunk 属于 small bins ，但通过前面的步骤都没有分配到所需的 chunk ，由于分配 small bin chunk 时在前面的步骤都不会调用 malloc_consolidate() 函数将 fast bins 中的 chunk 合并加入到 unsorted bin 中。所在这里如果 fast bin 中有 chunk 存在，调用 malloc_consolidate() 函数，并重新设置当前 bin 的 index 。并转到最外层的循环，尝试重新分配 small bin chunk 或是 large bin chunk 。如果开启了 ATOMIC_FASTBINS 优化，有可能在由其它线程加入到 fast bins 中的 chunk 被合并后加入 unsorted bin 中，从 unsorted bin 中就可以分配出所需的 large bin chunk 了，所以对没有成功分配的 large bin chunk 也需要重试。

#else
    /*
      If there is space available in fastbins, consolidate and retry,
      to possibly avoid expanding memory. This can occur only if nb is
      in smallbin range so we didn't consolidate upon entry.
    */
    else if (have_fastchunks(av)) {
      assert(in_smallbin_range(nb));
      malloc_consolidate(av);
      idx = smallbin_index(nb); /* restore original bin index */
}

 如果top chunk 也不能满足要求，查看 fast bins 中是否有空闲 chunk 存在，如果 fast bins 中有空闲 chunk 存在，在没有开启 ATOMIC_FASTBINS 优化的情况下，只有一种可能，那就是所需的 chunk 属于 small bins ，但通过前面的步骤都没有分配到所需的 small bin chunk ，由于分配 small bin chunk 时在前面的步骤都不会调用 malloc_consolidate() 函数将 fast bins 中的空闲 chunk 合并加入到 unsorted bin 中。所在这里如果 fast bins 中有空闲 chunk 存在，调用 malloc_consolidate() 函数，并重新设置当前 bin 的 index 。并转到最外层的循环，尝试重新分配 small bin chunk 。

#endif
    /*
       Otherwise, relay to handle system-dependent cases
    */
    else {
      void *p = sYSMALLOc(nb, av);
      if (p != NULL && __builtin_expect (perturb_byte, 0))
        alloc_perturb (p, bytes);
      return p;
山穷水尽了，只能想系统申请内存了。sYSMALLOc()函数可能分配的chunk包括small bin chunk，large bin chunk和large chunk。将在下一节中介绍该函数的实现。
    }
  }

 至此， _int_malloc() 函数的代码就罗列完了，当还有两个关键函数没有分析，一个为 malloc_consolidate() ，另一个为 sYSMALLOc() ，将在下面的章节介绍其实现。