heap - 7 - _int_malloc 源码及其部分分析

__int_malloc —— 核心内存分配函数

所有的分析都以注释的形式添加进源代码中，方便阅读

static void *
_int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* normalized request size */
  unsigned int idx;                 /* associated bin index */
  mbinptr bin;                      /* associated bin */

  mchunkptr victim;                 /* inspected/selected chunk */
  INTERNAL_SIZE_T size;             /* its size */
  int victim_index;                 /* its bin index */

  mchunkptr remainder;              /* remainder from a split */
  unsigned long remainder_size;     /* its size */

  unsigned int block;               /* bit map traverser */
  unsigned int bit;                 /* bit map traverser */
  unsigned int map;                 /* current word of binmap */

  mchunkptr fwd;                    /* misc temp for linking */
  mchunkptr bck;                    /* misc temp for linking */

  const char *errstr = NULL;

  /*
     Convert request size to internal form by adding SIZE_SZ bytes
     overhead plus possibly more to obtain necessary alignment and/or
     to obtain a size of at least MINSIZE, the smallest allocatable
     size. Also, checked_request2size traps (returning 0) request sizes
     that are so large that they wrap around zero when padded and
     aligned.
   */

  // 将用户申请的内存大小，在检测后，转换为申请的chunk大小
  checked_request2size (bytes, nb);

  /* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
  
  // 如果arena是空的，那就直接调用sysmalloc分配一块内存给用户
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
  alloc_perturb (p, bytes);
      return p;
    }

  /*
     If the size qualifies as a fastbin, first check corresponding bin.
     This code is safe to execute even if av is not yet initialized, so we
     can try it without checking, which saves some time on this fast path.
   */

  // 如果request chunk size满足fast chunk的大小
  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
  {
    // 根据request chunk size,找出应当被分配的fast bin索引与地址
    idx = fastbin_index (nb);
    mfastbinptr *fb = &fastbin (av, idx);
    mchunkptr pp = *fb;
    // 遍历出第一个fast chunk
    do
    {
      victim = pp;
      if (victim == NULL)
        break;
    }
    while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
            != victim);
    // 如果遍历出的fast chunk 地址不是空的
    if (victim != 0)
    {
      // 做一些常规fast chunk检查
      if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
      {
        errstr = "malloc(): memory corruption (fast)";
      errout:
        malloc_printerr (check_action, errstr, chunk2mem (victim), av);
        return NULL;
      }
      // 既然该fast chunk是可被分配的，那就做chunk检测
      check_remalloced_chunk (av, victim, nb);
      // 将chunk地址转换为用户所使用的地址
      void *p = chunk2mem (victim);
      // 如果相关位已设置，那就初始化该内存
      alloc_perturb (p, bytes);
      return p;
    }
  }

  /*
     If a small request, check regular bin.  Since these "smallbins"
     hold one size each, no searching within bins is necessary.
     (For a large request, we need to wait until unsorted chunks are
     processed to find best fit. But for small ones, fits are exact
     anyway, so we can check now, which is faster.)
   */

  // 如果fast bin无法满足需求，并且所申请的chunk大小满足small chunk的范围
  if (in_smallbin_range (nb))
  {
    // 取出相关索引与small bin地址
    idx = smallbin_index (nb);
    bin = bin_at (av, idx);

    // 取出small bin的链尾chunk的地址
    if ((victim = last (bin)) != bin)
    {
      // 如果这是第一次执行该代码语句
      if (victim == 0) /* initialization check */
        malloc_consolidate (av);
      else
      {
        // 如果有满足条件的small chunk
        // 那就将其从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;

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

  /*
     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
  {
    // 取出largebin的索引
    idx = largebin_index (nb);
    // 如果有空闲的fast chunks，则执行malloc_consolidate
    if (have_fastchunks (av))
      malloc_consolidate (av);
  }

  /*
     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 大循环
  for (;; )
  {
    int iters = 0;
    // 遍历所有unsorted chunk
    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);

      /*
          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.
        */

      // 如果当前请求位于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);

      /* Take now instead of binning if exact fit */

      // 如果遍历到的这个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;
      }

      /* place chunk in 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;
      }

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

    // 在对unsorted chunks进行排列放置进对应bin之后

    /*
        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.
      */

    //判断所申请的chunks是否为large chunk
    if (!in_smallbin_range (nb))
    {
      bin = bin_at (av, idx);

      /* skip scan if empty or largest chunk is too small */
      // 如果当前large bin链不为空，以及该链上的large chunks大小足够
      if ((victim = first (bin)) != bin &&
          (unsigned long) (victim->size) >= (unsigned long) (nb))
      {
        victim = victim->bk_nextsize;
        while (((unsigned long) (size = chunksize (victim)) <
                (unsigned long) (nb)))
          victim = victim->bk_nextsize;

        /* Avoid removing the first entry for a size so that the skip
            list does not have to be rerouted.  */

        // 如果满足大小的chunks不止一个，则始终取走第二个，以减小指针操作
        if (victim != last (bin) && victim->size == victim->fd->size)
          victim = victim->fd;

        // 计算出该large chunks分割后剩余的chunk大小
        remainder_size = size - nb;
        // 该large chunks解链
        unlink (av, victim, bck, fwd);

        /* Exhaust */

        // 如果该large chunks分割后剩余的chunk大小小于最小chunk大小

        if (remainder_size < MINSIZE)
        {
          // 剩余的这点空间，一起附赠给用户
          set_inuse_bit_at_offset (victim, size);
          if (av != &main_arena)
            victim->size |= NON_MAIN_ARENA;
        }
        /* Split */

        // 否则，切割chunk
        else
        {
          // 切割该large 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";
            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;
          }
          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;
      }
    }

    /*
        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.
      */

    // 既然当前large bin里没有适合的large chunk
    // 则使用binmap遍历索引更高、大小更大的bin，以满足用户需求

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

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

      /* Advance to bin with set bit. There must be one. */
      while ((bit & map) == 0)
      {
        bin = next_bin (bin);
        bit <<= 1;
        assert (bit != 0);
      }

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

      /*  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;
      }

      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 (av, victim, bck, fwd);

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

        /* 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 (__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 */
          if (in_smallbin_range (nb))
            av->last_remainder = 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:
    /*
        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.)
      */

    // 既然上面真的什么chunk都分配不出来，那就尝试使用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;
      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;
    }

    /* When we are using atomic ops to free fast chunks we can get
        here for all block sizes.  */

    // 如果top chunk也不够大，则尝试执行malloc_consolidate，并尝试重新从small bin和large bin中分配chunk
    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);
    }

    /*
        Otherwise, relay to handle system-dependent cases
      */

    // 如果真的是山穷水尽了，一个free chunk都挤不出来了
    else
    {
      // 就勉为其难的调用sysmalloc分配内存
      void *p = sysmalloc (nb, av);
      if (p != NULL)
        alloc_perturb (p, bytes);
      return p;
    }
  }
}