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

5.8.2 _int_free()

_int_free() 函数的实现源代码如下：

static void
#ifdef ATOMIC_FASTBINS
_int_free(mstate av, mchunkptr p, int have_lock)
#else
_int_free(mstate av, mchunkptr p)
#endif
{
  INTERNAL_SIZE_T size;        /* its size */
  mfastbinptr*    fb;          /* associated fastbin */
  mchunkptr       nextchunk;   /* next contiguous chunk */
  INTERNAL_SIZE_T nextsize;    /* its size */
  int             nextinuse;   /* true if nextchunk is used */
  INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
  mchunkptr       bck;         /* misc temp for linking */
  mchunkptr       fwd;         /* misc temp for linking */

  const char *errstr = NULL;
#ifdef ATOMIC_FASTBINS
  int locked = 0;
#endif

  size = chunksize(p);
获取需要释放的chunk的大小。

  /* Little security check which won't hurt performance: the
     allocator never wrapps around at the end of the address space.
     Therefore we can exclude some size values which might appear
     here by accident or by "design" from some intruder.  */
  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
      || __builtin_expect (misaligned_chunk (p), 0))
    {
      errstr = "free(): invalid pointer";
    errout:
#ifdef ATOMIC_FASTBINS
      if (! have_lock && locked)
        (void)mutex_unlock(&av->mutex);
#endif
      malloc_printerr (check_action, errstr, chunk2mem(p));
      return;
    }
  /* We know that each chunk is at least MINSIZE bytes in size.  */
  if (__builtin_expect (size < MINSIZE, 0))
    {
      errstr = "free(): invalid size";
      goto errout;
    }

  check_inuse_chunk(av, p);

 上面的代码用于安全检查， chunk 的指针地址不能溢出， chunk 的大小必须大于等于 MINSIZE 。

  /*
    If eligible, place chunk on a fastbin so it can be found
    and used quickly in malloc.
  */
  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
      /*
        If TRIM_FASTBINS set, don't place chunks
        bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {

    if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
        || __builtin_expect (chunksize (chunk_at_offset (p, size))
                             >= av->system_mem, 0))
      {
#ifdef ATOMIC_FASTBINS
        /* We might not have a lock at this point and concurrent modifications
           of system_mem might have let to a false positive.  Redo the test
           after getting the lock.  */
        if (have_lock
            || ({ assert (locked == 0);
                  mutex_lock(&av->mutex);
                  locked = 1;
                  chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
                    || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
              }))
#endif
          {
            errstr = "free(): invalid next size (fast)";
            goto errout;
          }
#ifdef ATOMIC_FASTBINS
        if (! have_lock)
          {
            (void)mutex_unlock(&av->mutex);
            locked = 0;
          }
#endif
      }

 如果当前 free 的 chunk 属于 fast bins ，查看下一个相邻的 chunk 的大小是否小于等于 2*SIZE_SZ ，下一个相邻 chunk 的大小是否大于分配区所分配的内存总量，如果是，报错。这里计算下一个相邻 chunk 的大小似乎有点问题，因为 chunk 的 size 字段中包含了一些标志位，正常情况下下一个相邻 chunk 的 size 中的 PREV_INUSE 标志位会置位，但这里就是要检出错的情况，也就是下一个相邻 chunk 的 size 中标志位都没有置位，并且该 chunk 大小为 2*SIZE_SZ 的错误情况。如果开启了 ATOMIC_FASTBINS 优化，并且调用本函数前没有对分配区加锁， 所以读取分配区所分配的内存总量需要对分配区加锁，检查完以后，释放分配区的锁。

    if (__builtin_expect (perturb_byte, 0))
      free_perturb (chunk2mem(p), size - SIZE_SZ);

    set_fastchunks(av);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);
设置当前分配区的fast bin flag，表示当前分配区的fast bins中已有空闲chunk。然后根据当前free的chunk大小获取所属的fast bin。

#ifdef ATOMIC_FASTBINS
    mchunkptr fd;
    mchunkptr old = *fb;
    unsigned int old_idx = ~0u;
    do
      {
        /* Another simple check: make sure the top of the bin is not the
           record we are going to add (i.e., double free).  */
        if (__builtin_expect (old == p, 0))
          {
            errstr = "double free or corruption (fasttop)";
            goto errout;
          }
        if (old != NULL)
          old_idx = fastbin_index(chunksize(old));
        p->fd = fd = old;
      }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, fd)) != fd);

    if (fd != NULL && __builtin_expect (old_idx != idx, 0))
      {
        errstr = "invalid fastbin entry (free)";
        goto errout;
      }

 如果开启了 ATOMIC_FASTBINS 优化，使用 lock-free 技术实现 fast bin 的单向链表插入操作。对 lock-free 的描述，请参见 5.7.2.1 节。这里也没有 ABA 问题，比如当前线程获取 *fb 并保存到 old 中，在调用 cas 原子操作前， B 线程将 *fb 修改为 x ，如果 B 线程加入了新的 chunk ，则 x->fb 指向 old ，如果 B 线程删除了 old ，则 x 为 old->fb 。如果 C 线程将 *fb 修改为 old ，则可能将 B 线程加入的 chunk x 删除，或者 C 将 B 删除的 old 又重新加入。这两种情况，都不会导致链表出错，所以不会有 ABA 问题。

#else
    /* Another simple check: make sure the top of the bin is not the
       record we are going to add (i.e., double free).  */
    if (__builtin_expect (*fb == p, 0))
      {
        errstr = "double free or corruption (fasttop)";
        goto errout;
      }
    if (*fb != NULL
        && __builtin_expect (fastbin_index(chunksize(*fb)) != idx, 0))
      {
        errstr = "invalid fastbin entry (free)";
        goto errout;
      }

    p->fd = *fb;
*fb = p;
如果没有开启了ATOMIC_FASTBINS优化，将free的chunk加入fast bin的单向链表中，修改过链表表头为当前free的chunk。同时需要校验是否为double free错误，校验表头不为NULL情况下，保证表头chunk的所属的fast bin与当前free的chunk所属的fast bin相同。
#endif
  }

  /*
    Consolidate other non-mmapped chunks as they arrive.
  */
  else if (!chunk_is_mmapped(p)) {
#ifdef ATOMIC_FASTBINS
    if (! have_lock) {
# if THREAD_STATS
      if(!mutex_trylock(&av->mutex))
        ++(av->stat_lock_direct);
      else {
        (void)mutex_lock(&av->mutex);
        ++(av->stat_lock_wait);
      }
# else
      (void)mutex_lock(&av->mutex);
# endif
      locked = 1;
    }
#endif
如果当前free的chunk不是通过mmap()分配的，并且当前还没有获得分配区的锁，获取分配区的锁。

    nextchunk = chunk_at_offset(p, size);
获取当前free的chunk的下一个相邻的chunk。

    /* Lightweight tests: check whether the block is already the
       top block.  */
    if (__builtin_expect (p == av->top, 0))
      {
        errstr = "double free or corruption (top)";
        goto errout;
      }
    /* Or whether the next chunk is beyond the boundaries of the arena.  */
    if (__builtin_expect (contiguous (av)
                          && (char *) nextchunk
                          >= ((char *) av->top + chunksize(av->top)), 0))
      {
        errstr = "double free or corruption (out)";
        goto errout;
      }
    /* Or whether the block is actually not marked used.  */
    if (__builtin_expect (!prev_inuse(nextchunk), 0))
      {
        errstr = "double free or corruption (!prev)";
        goto errout;
      }

 安全检查，当前 free 的 chunk 不能为 top chunk ，因为 top chunk 为空闲 chunk ，如果再次 free 就可能为 double free 错误了。如果当前 free 的 chunk 是通过 sbrk() 分配的，并且下一个相邻的 chunk 的地址已经超过了 top chunk 的结束地址，超过了当前分配区的结束地址，报错。如果当前 free 的 chunk 的下一个相邻 chunk 的 size 中标志位没有标识当前 free chunk 为 inuse 状态，可能为 double free 错误。

    nextsize = chunksize(nextchunk);
    if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
        || __builtin_expect (nextsize >= av->system_mem, 0))
      {
        errstr = "free(): invalid next size (normal)";
        goto errout;
      }

    if (__builtin_expect (perturb_byte, 0))
      free_perturb (chunk2mem(p), size - SIZE_SZ);
计算当前free的chunk的下一个相邻chunk的大小，该大小如果小于等于2*SIZE_SZ或是大于了分配区所分配区的内存总量，报错。

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

 如果当前 free 的 chunk 的前一个相邻 chunk 为空闲状态，与前一个空闲 chunk 合并。计算合并后的 chunk 大小，并将前一个相邻空闲 chunk 从空闲 chunk 链表中删除。

    if (nextchunk != av->top) {
      /* get and clear inuse bit */
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
如果与当前free的chunk相邻的下一个chunk不是分配区的top chunk，查看与当前chunk相邻的下一个chunk是否处于inuse状态。

      /* consolidate forward */
      if (!nextinuse) {
        unlink(nextchunk, bck, fwd);
        size += nextsize;
      } else
        clear_inuse_bit_at_offset(nextchunk, 0);
如果与当前free的chunk相邻的下一个chunk处于inuse状态，清除当前chunk的inuse状态，则当前chunk空闲了。否则，将相邻的下一个空闲chunk从空闲链表中删除，并计算当前chunk与下一个chunk合并后的chunk大小。

      /*
        Place the chunk in unsorted chunk list. Chunks are
        not placed into regular bins until after they have
        been given one chance to be used in malloc.
      */
      bck = unsorted_chunks(av);
      fwd = bck->fd;
      if (__builtin_expect (fwd->bk != bck, 0))
        {
          errstr = "free(): corrupted unsorted chunks";
          goto errout;
        }
      p->fd = fwd;
      p->bk = bck;
      if (!in_smallbin_range(size))
        {
          p->fd_nextsize = NULL;
          p->bk_nextsize = NULL;
        }
      bck->fd = p;
      fwd->bk = p;
将合并后的chunk加入unsorted bin的双向循环链表中。如果合并后的chunk属于large bins，将chunk的fd_nextsize和bk_nextsize设置为NULL，因为在unsorted bin中这两个字段无用。

      set_head(p, size | PREV_INUSE);
      set_foot(p, size);
设置合并后的空闲chunk大小，并标识前一个chunk处于inuse状态，因为必须保证不能有两个相邻的chunk都处于空闲状态。然后将合并后的chunk加入unsorted bin的双向循环链表中。最后设置合并后的空闲chunk的foot，chunk空闲时必须设置foot，该foot处于下一个chunk的prev_size中，只有chunk空闲是foot才是有效的。

      check_free_chunk(av, p);
    }

    /*
      If the chunk borders the current high end of memory,
      consolidate into top
    */
    else {
      size += nextsize;
      set_head(p, size | PREV_INUSE);
      av->top = p;
      check_chunk(av, p);
    }

 如果当前 free 的 chunk 下一个相邻的 chunk 为 top chunk ，则将当前 chunk 合并入 top chunk ，修改 top chunk 的大小。

    /*
      If freeing a large space, consolidate possibly-surrounding
      chunks. Then, if the total unused topmost memory exceeds trim
      threshold, ask malloc_trim to reduce top.

      Unless max_fast is 0, we don't know if there are fastbins
      bordering top, so we cannot tell for sure whether threshold
      has been reached unless fastbins are consolidated.  But we
      don't want to consolidate on each free.  As a compromise,
      consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
      is reached.
    */
    if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
      if (have_fastchunks(av))
        malloc_consolidate(av);
如果合并后的chunk大小大于64KB，并且fast bins中存在空闲chunk，调用malloc_consolidate()函数合并fast bins中的空闲chunk到unsorted bin中。

      if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
        if ((unsigned long)(chunksize(av->top)) >=
            (unsigned long)(mp_.trim_threshold))
          sYSTRIm(mp_.top_pad, av);
如果当前分配区为主分配区，并且top chunk的大小大于heap的收缩阈值，调用sYSTRIm()函数首先heap。
#endif
      } else {
        /* Always try heap_trim(), even if the top chunk is not
           large, because the corresponding heap might go away.  */
        heap_info *heap = heap_for_ptr(top(av));

        assert(heap->ar_ptr == av);
        heap_trim(heap, mp_.top_pad);
如果为非主分配区，调用heap_trim()函数收缩非主分配区的sub_heap。
      }
    }

#ifdef ATOMIC_FASTBINS
    if (! have_lock) {
      assert (locked);
      (void)mutex_unlock(&av->mutex);
    }
#endif
如果开启了ATOMIC_FASTBINS优化并获得分配区的锁，则对分配区解锁。
  }
  /*
    If the chunk was allocated via mmap, release via munmap(). Note
    that if HAVE_MMAP is false but chunk_is_mmapped is true, then
    user must have overwritten memory. There's nothing we can do to
    catch this error unless MALLOC_DEBUG is set, in which case
    check_inuse_chunk (above) will have triggered error.
  */
  else {
#if HAVE_MMAP
munmap_chunk (p);
如果当前free的chunk是通过mmap()分配的，调用munma_chunk()释放内存。
#endif
  }
}