Skip to main content

fastbin

Explaination

An array of lists holding recently freed small chunks. Fastbins are not doubly linked. It is faster to single-link them, and since chunks are never removed from the middles of these lists, double linking is not necessary. Also, unlike regular bins, they are not even processed in FIFO order (they use faster LIFO) since ordering doesn't much matter in the transient contexts in which fastbins are normally used.

Chunks in fastbins keep their inuse bit set, so they cannot be consolidated with other free chunks. malloc_consolidate releases all chunks in fastbins and consolidates them with other free chunks.

fastbin 的特点​

fastbin 作为一种 LIFO 的单链表快速 bin，保存了一些较小的 chunk，并在 bin 的回收利用中存在较高的优先级（在 2.26 Tcache 之前为第一顺位），且在入 bin 时不会将其 prev_inuse 位置 0 —— 这也意味着 fastbin 不会和其他的空闲 chunk 进行合并。

fastbin 具有以下特点：

  • fastbin 存储于 fastbinsY Array 当中，该 Array 的大小为 NFASTBINS。
  • fastbin 由 fastbin_index 宏确定其在 fastbinsY Array 中的 index。
  • fastbin 的范围由 MAX_FAST_SIZE 宏 以及 MINSIZE 宏决定，为 MINSIZE ~ MAX_FAST_SIZE。
  • 两个相邻的 fastbin 相差 2*SIZE_SZ 字节。
tip

在 32 位系统下， SIZE_SZ 一般为 4

在 64 位系统下， SIZE_SZ 一般为 8

/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)
note

在 64 位下可以计算出如下结果：

MAX_FAST_SIZE = 160 = 0xA0 NFASTBINS = 10

在 32 位下可以计算出如下结果：

MAX_FAST_SIZE = 80 = 0x50 NFASTBINS = 10

值得注意的是，在 malloc_init_state 中，如果满足 init 的 arena 为 main_arena，还会执行一个 set_max_fast 宏

#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)

#define set_max_fast(s) \
  global_max_fast = (((s) == 0)						      \
                     ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))

if (av == &main_arena)
  set_max_fast (DEFAULT_MXFAST);

这会对应的修改 fastbin 的范围到 MINSIZE ~ DEFAULT_MXFAST

note

在绝大部分情况下，我们可以有以下结论

32 位

fastbinsY 存储了 10 个 fastbin 每个相邻的 bin 大小相差 8 chunk 范围是 16, 24, 32, ..., 64

64 位

fastbinsY 存储了 10 个 fastbin 每个相邻的 bin 大小相差 16 chunk 范围是 32, 48, 64, ..., 128

fastbin 的取用​

在 2.23 版本下，并不存在 tcache 这种类型的 bin。

在 _int_malloc 函数中可以观察到，调用 malloc 函数的情况下，如果存在可用 arena，则会第一顺位检查 fastbin 是否符合条件。

static void *
_int_malloc (mstate av, size_t bytes)
{
  ...
  /*
    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);
      mchunkptr pp = *fb;
      do
        {
          victim = pp;
          if (victim == NULL)
            break;
        }
      while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
            != victim);
      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), av);
              return NULL;
            }
          check_remalloced_chunk (av, victim, nb);
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }

2.23 版本下，fastbin 的取出并不存在太多保护。

只要求取出 chunk 的 size 与所要求的 chunk size 相同。即 fastbin_index (chunksize (victim)) == fastbin_index (nb) 需要成立。为了满足这一点，在 fastbin 类型的攻击时，伪造 chunk_size 是必须的。 事实上，我们常使用 _free_hook-0x23 这里存在的 0x7f 这个字节来作为 chunk_size 伪造一个 fastbin ，从而在取出它后改写 _free_hook。关于攻击的内容在 攻击手法 Use After Free 中有更详细的介绍。

fastbin 的放入​

在 2.23 版本下，并不存在 tcache 这种类型的 bin。

因为 __libc_free 并不涉及 fastbin 相关，所以我们直接跳到 _int_free 函数。

static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  ...
  check_inuse_chunk(av, p);

  /*
    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))
      {
	/* 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;
	      }))
	  {
	    errstr = "free(): invalid next size (fast)";
	    goto errout;
	  }
	if (! have_lock)
	  {
	    (void)mutex_unlock(&av->mutex);
	    locked = 0;
	  }
      }

    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

    set_fastchunks(av);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;
    unsigned int old_idx = ~0u;
    do
      {
	/* Check that 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;
	  }
	/* Check that size of fastbin chunk at the top is the same as
	   size of the chunk that we are adding.  We can dereference OLD
	   only if we have the lock, otherwise it might have already been
	   deallocated.  See use of OLD_IDX below for the actual check.  */
	if (have_lock && old != NULL)
	  old_idx = fastbin_index(chunksize(old));
	p->fd = old2 = old;
      }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);

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

对于操作的 chunk，程序首先检查该 chunk 是否在 fastbin 范围内，如果上述条件成立，程序则继续检查 next chunk size 是否大于 MINSIZE 且小于 heap size。 如果满足条件，则运行 free_perturb 函数，将 chunk 的 data 填充为 perturb_byte，但若 perturb_byte 为 空（即 \x00，默认值） 则会跳过。

之后正式进入放入 fastbin 的过程，首先根据 chunk size 取出对应的 fastbin，如果 fastbin 不为空，则存在两个检查：

  • 检查这个 chunk 是否与 fastbin 的头部 chunk 相同
  • 检查 fastbin 头部 chunk 应在的 fastbin 是否为取出的 fastbin（fastbin_index(chunksize(&fastbin (av, idx))) == idx）

当两个检查都通过后，执行 *fb = p; p->fd = old;，free 完成。

对于第一个检查，因为它仅检查了 fastbin 的头部 chunk 是否与即将 free 的 chunk 相同，所以我们只需要构造 free(a); free(b); free(a) 即可绕过检查，这就是非常经典的 fastbin double free。

tip

这里的 chunk 指的是 mem2chunk 宏返回的指针对应的 chunk，包括了 size 位和标志位等。

例如：在一般 64 位条件下，fastbin 最大为 0x80 的大小，此时若执行 a = malloc(0x80); free(a); a 并不会被放入 fastbin，因为 chunksize(p) 为 0x90 大小，大于 get_max_fast()。