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

5.7 内存分配malloc（）

 

Ptmalloc2 主要的内存分配函数为 malloc() ，但源代码中并不能找到该函数，该函数是用宏定义为 public_mALLOc() ，因为该函数在不同的编译条件下，具有不同的名称。 public_mALLOc() 函数只是简单的封装 _int_malloc() 函数， _int_malloc() 函数才是内存分配的核心实现。下面我们将分析 malloc 的实现。

 

5.7.1 public_mALLOc

    先给出源代码：

Void_t*
public_mALLOc(size_t bytes)
{
  mstate ar_ptr;
  Void_t *victim;

  __malloc_ptr_t (*hook) (size_t, __const __malloc_ptr_t)
    = force_reg (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));
首先检查是否存在内存分配的hook函数，如果存在，调用hook函数，并返回，hook函数主要用于进程在创建新线程过程中分配内存，或者支持用户提供的内存分配函数。请参考5.3节相关的描述。

  arena_lookup(ar_ptr);
  arena_lock(ar_ptr, bytes);
  if(!ar_ptr)
    return 0;
  victim = _int_malloc(ar_ptr, bytes);
获取分配区指针，如果获取分配区失败，返回退出，否则，调用_int_malloc()函数分配内存。

  if(!victim) {
    /* Maybe the failure is due to running out of mmapped areas. */
    if(ar_ptr != &main_arena) {
      (void)mutex_unlock(&ar_ptr->mutex);
      ar_ptr = &main_arena;
      (void)mutex_lock(&ar_ptr->mutex);
      victim = _int_malloc(ar_ptr, bytes);
      (void)mutex_unlock(&ar_ptr->mutex);
如果_int_malloc()函数分配内存失败，并且使用的分配区不是主分配区，这种情况可能是mmap区域的内存被用光了，当主分配区可以从堆中分配内存，所以需要再尝试从主分配区中分配内存。首先释放所使用分配区的锁，然后获得主分配区的锁，并调用_int_malloc()函数分配内存，最后释放主分配区的锁。

    } else {
#if USE_ARENAS
      /* ... or sbrk() has failed and there is still a chance to mmap() */
      ar_ptr = arena_get2(ar_ptr->next ? ar_ptr : 0, bytes);
      (void)mutex_unlock(&main_arena.mutex);
      if(ar_ptr) {
        victim = _int_malloc(ar_ptr, bytes);
        (void)mutex_unlock(&ar_ptr->mutex);
      }
如果_int_malloc()函数分配内存失败，并且使用的分配区是主分配区，查看是否有非主分配区，如果有，调用arena_get2()获取分配区，然后对主分配区解锁，如果arena_get2()返回一个非主分配区，尝试调用_int_malloc()函数从该非主分配区分配内存，最后释放该非主分配区的锁。
#endif
    }
  } else
(void)mutex_unlock(&ar_ptr->mutex);
如果_int_malloc()函数分配内存成功，释放所使用的分配区的锁。

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

5.7.2 _int_malloc()

_int_malloc() 函数是内存分配的核心，根据分配的内存块的大小，该函数中实现了四种分配内存的路径，下面将分别分析这四种分配路径。

先给出 _int_malloc() 函数的函数定义及临时变量的定义：

static Void_t*
_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.
  */
  checked_request2size(bytes, nb);

 checked_request2size() 函数将需要分配的内存大小 bytes 转换为需要分配的 chunk 大小 nb 。 Ptmalloc 内部分配都是以 chunk 为单位，根据 chunk 的大小，决定如何获得满足条件的 chunk 。

 

5.7.2.1 分配fast bin chunk

如果所需的 chunk 大小小于等于 fast bins 中的最大 chunk 大小，首先尝试从 fast bins 中分配 chunk 。源代码如下：

/*
    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.
  */
  if ((unsigned long)(nb) <= (unsigned long)(get_max_fast ())) {
    idx = fastbin_index(nb);
    mfastbinptr* fb = &fastbin (av, idx);
#ifdef ATOMIC_FASTBINS
    mchunkptr pp = *fb;
    do
      {
        victim = pp;
        if (victim == NULL)
          break;
      }
    while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
           != victim);
#else
    victim = *fb;
#endif
    if (victim != 0) {
      if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
        {
          errstr = "malloc(): memory corruption (fast)";
        errout:
          malloc_printerr (check_action, errstr, chunk2mem (victim));
          return NULL;
        }
#ifndef ATOMIC_FASTBINS
      *fb = victim->fd;
#endif
      check_remalloced_chunk(av, victim, nb);
      void *p = chunk2mem(victim);
      if (__builtin_expect (perturb_byte, 0))
        alloc_perturb (p, bytes);
      return p;
    }
  }

 如果没有开启 ATOMIC_FASTBINS 优化，从 fast bins 中分配一个 chunk 相当简单，首先根据所需 chunk 的大小获得该 chunk 所属 fast bin 的 index ，根据该 index 获得所需 fast bin 的空闲 chunk 链表的头指针，然后将头指针的下一个 chunk 作为空闲 chunk 链表的头部。为了加快从 fast bins 中分配 chunk ，处于 fast bins 中 chunk 的状态仍然保持为 inuse 状态，避免被相邻的空闲 chunk 合并，从 fast bins 中分配 chunk ，只需取出第一个 chunk ，并调用 chunk2mem() 函数返回用户所需的内存块。

如果开启 ATOMIC_FASTBINS 优化，这里使用了 lock-free 的技术实现单向链表删除第一个 node 的操作。 Lock-free 算法的基础是 CAS (Compareand-Swap) 原子操作。当某个地址的原始值等于某个比较值时，把值改成新值，无论有否修改，返回这个地址的原始值。目前的 cpu 支持最多 64 位的 CAS ，并且指针 p 必须对齐。原子操作指一个 cpu 时钟周期内就可以完成的操作，不会被其他线程干扰。

一般的 CAS 使用方式是：假设有指针 p ，它指向一个 32 位或者 64 位数，

1.       复制 p 的内容（ *p ）到比较量 cmp （原子操作）。

2.       基于这个比较量计算一个新值 xchg （非原子操作）。

3.       调用 CAS 比较当前 *p 和 cmp ，如果相等把 *p 替换成 xchg （原子操作）。

4.       如果成功退出，否则回到第一步重新进行。

第 3 步的 CAS 操作保证了写入的同时 p 没有被其他线程更改。如果 *p 已经被其他线程更改，那么第 2 步计算新值所使用的值（ cmp ）已经过期了，因此这个整个过程失败，重新来过。多线程环境下，由于 3 是一个原子操作，那么起码有一个线程（最快执行到 3 ）的 CAS 操作可以成功，这样整体上看，就保证了所有的线程上在“前进”，而不需要使用效率低下的锁来协调线程，更不会导致死锁之类的麻烦。

ABA 问题，当 A 线程执行 2 的时候，被 B 线程更改了 *p 为 x ，而 C 线程又把它改回了原始值，这时回到 A 线程， A 线程无法监测到原始值已经被更改过了， CAS 操作会成功（实际上应该失败）。 ABA 大部分情况下会造成一些问题，因为 p 的内容一般不可能是独立的，其他内容已经更改，而 A 线程认为它没有更改就会带来不可预知的结果。

如果开启 ATOMIC_FASTBINS 优化，这里的实现会出现 ABA 问题吗？不会出现，如果开启了 ATOMIC_FASTBINS 优化，在 free 时，如果释放的 chunk 属于 fast bin ，不需要对分配区加锁，可以通过 lock-free 技术将该 chunk 加入 fast bins 的链表中。当从分配区分配内存时，需要对分配区加锁，所以当 A 线程获得了分配区的锁，并从 fast bin 中分配内存执行 2 的时候，被 B 线程调用 free 函数向 fast bin 的链表中加入了一个新的 chunk ，即更改了 *fb 为 x ，但不会存在 C 线程将 *fb 改回原值，如果存在，意味着 C 线程先分配了 *fb 所存的 chunk ，并将该 chunk 释放回了 fast bin ，但 C 线程分配 *fb 所存的 chunk 需要获得分配区的锁，但分配区的锁被 A 线程持有，所以 C 线程不可能将 *fb 改回原值，也就不会存在 ABA 问题。