ptmalloc源码学习

发表于

终于鼓起勇气写这么一篇博客，一直想把malloc.c的源码看一下，算是一篇总结吧。

说明：本篇文章的所有源码均来自glibc-2.29，主要是arena.c和malloc.c这两个源文件。

操作系统内存分配的相关函数

对于堆内存的分配，操作系统提供了brk系统调用，glibc中提供了sbrk()函数，start_brk指向进程堆的起始地址，brk是堆的当前最后地址，malloc通过内核的brk系统调用来增加brk的值，从而向操作系统申请内存。初始时start_brk和brk指向同一地址：

1
2
1. 未开启ASLR时，start_brk和brk指向bss段的末尾
2. 开启ASLR时，start_brk和brk指向bss段末尾后的随机偏移处。

mmap函数将一个文件或其他对象映射进内存，文件被映射到多个页上。munmap删除特定地址区域的对象映射。

数据结构

malloc_state

为了更有效的处理多线程的应用程序，glibc的malloc允许多块内存区域在同一时间处于active的状态，不同的线程可以互不干扰的访问不用的内存区域，这些内存区域就叫做“arenas”，“main_arena”是程序初始分配的内存区域，每个进程只有一个main_arena（主分配区），可以有多个non_main_arena（非主分配区）。每个arena结构体都有一个互斥锁，来控制线程对于arena的访问。管理arena的结构是malloc_state，每个分配区都是malloc_state的一个实例。主分配区通过sbrk()进行堆的扩展，非主分配区通过mmap函数来建立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//malloc.c
struct malloc_state
{
  /* Serialize access.  */
  //用于多个线程访问同一个分配区时进行串行化访问分配区
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* Fastbins */
  //存放每个fastbin链表中的头指针
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  //指向分配区的top chunk
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  //存储smallbins,largebins和unsorted bins
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  //标识该bit对应的bin中是否包含空闲的chunk
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  //将分配区以单链表的形式链接起来
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  //将空闲的分配区链接在单向链表中
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  //记录当前分配区已经分配的内存大小
  INTERNAL_SIZE_T system_mem;
  //记录当前分配区最大能分配的内存大小
  INTERNAL_SIZE_T max_system_mem;
};

ptmalloc使用结构体malloc_par来进行参数管理，只有一个malloc_par实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//malloc.c
struct malloc_par
{
  /* Tunable parameters */
  unsigned long trim_threshold; //收缩内存的阈值
  INTERNAL_SIZE_T top_pad; //分配内存时是否添加额外的pad
  INTERNAL_SIZE_T mmap_threshold;
  INTERNAL_SIZE_T arena_test;
  INTERNAL_SIZE_T arena_max;

  /* Memory map support */
  int n_mmaps; //当前进程使用mmap()分配的内存块的个数
  int n_mmaps_max; //进行使用mmap()分配的内存块的最大数量，默认为65536
  int max_n_mmaps; //当前进程使用mmap()分配的内存块数量的最大值
  /* the mmap_threshold is dynamic, until the user sets
     it manually, at which point we need to disable any
     dynamic behavior. */
  int no_dyn_threshold; //是否开启mmap分配阈值动态调整机制

  /* Statistics */
  //用于统计mmap分配的内存大小
  INTERNAL_SIZE_T mmapped_mem;
  INTERNAL_SIZE_T max_mmapped_mem;

  /* First address handed out by MORECORE/sbrk.  */
  char *sbrk_base; //堆的起始地址

#if USE_TCACHE
  /* Maximum number of buckets to use.  */
  size_t tcache_bins;  //当前tcache链表中的bins的个数
  size_t tcache_max_bytes; 
  /* Maximum number of chunks in each bucket.  */
  size_t tcache_count; //在每个bin中chunk的最大数量
  /* Maximum number of chunks to remove from the unsorted list, which
     aren't used to prefill the cache.  */
  size_t tcache_unsorted_limit;
#endif
};

这里说一下成员arena_test和arena_max，当每个进程的分配区数量小于等于arena_test时，不会重用已有的分配区；当系统分配区数量达到arena_max,就不会再创建新的分配区，只会重用已有的分配区。32位系统下arena_test默认值为2，arena_max为2 系统核数；64位系统下arena_test默认值为8，arena_max为8 系统核数。

malloc_chunk

ptmalloc使用chunk对内存进行管理，malloc_chunk被用来管理这些chunk的数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//malloc.c
struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */  //如果前一个chunk是空闲的，该变量表示前一个chunk的大小
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */ //当前chunk的大小以及一些属性信息

  //只有当chunk处于空闲状态时才会用到，当一个chunk被加入对应大小的空闲链表时，用fd和bk来标识它的前一个chunk和后一个chunk
  struct malloc_chunk* fd;         /* double links -- used only if free. */  
  struct malloc_chunk* bk;

  //这两个变量只会在largebin中用到，largebin中除了有一个空闲chunk的链表外，还有一个size的链表，chunk按照从小到大的顺序排列。
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

ptmalloc使用边界标记法对chunk进行管理，充分考虑到空间复用，已分配的chunk的结构如下，chunk指向一个chunk的起始地址，mem是使用malloc分配后返回给用户的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of previous chunk, if unallocated (P clear)  |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             User data starts here...                          .
	    .                                                               .
	    .             (malloc_usable_size() bytes)                      .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             (size of chunk, but used for application data)    |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of next chunk, in bytes                |A|0|1|
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

空闲的chunk被存储在循环的双向链表中，结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of previous chunk, if unallocated (P clear)  |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                     |A|0|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Forward pointer to next chunk in list             |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Back pointer to previous chunk in list            |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Unused space (may be 0 bytes long)                .
	    .                                                               .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of next chunk, in bytes                |A|0|0|
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

chunk的低三个bit用来标识chunk的属性：

1
2
3
P(PREV_INUSE):标识前一个chunk是否处于使用状态，若P=1，则上一个chunk处于使用状态；P=0则上一个chunk处于freed状态。
M(IS_MMAPED)：标识是否由mmap分配。若为1，则表示该chunk是从mmap映射区域分配的。
A(NON_MAIN_ARENA):标识该chunk是否来自main_arena，即是否是主线程分配的chunk，若为0，则该chunk来自main_arena，否则来自非主分配区。

几个数值

INTERNAL_SIZE_T和SIZE_SZ相同，在32位下是4个字节，64位下是8个字节的无符号整数。

1
2
3
4
5
#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif
/* The corresponding word size */
#define SIZE_SZ (sizeof(INTERNAL_SIZE_T))

MALLOC_ALIGNMENT在32位下是8个字节，64位下是16个字节的无符号整数。

1
2
3
4
5
6
#ifndef MALLOC_ALIGNMENT
#define MALLOC_ALIGNMENT (2 * SIZE_SZ)
#endif

/* The corresponding bit mask value */
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

相关宏

chunk指向一个chunk的起始地址，mem是使用malloc分配后返回给用户的指针，SIZE_SZ类型是size_t，在64位下是64位无符号整数，8个字节；在32位下是32位无符号整数，4个字节。所以64位下malloc headers是0x19个字节，在32位下是0x8个字节。

1
2
3
4
//malloc.c
/* conversion from malloc headers to user pointers, and back */
#define chunk2mem(p)   ((void*)((char*)(p) + 2*SIZE_SZ)) 
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))

最小的chunk大小，offsetof是计算fd_nextsize在结构体malloc_chunk的偏移，在64位下最小chunk是0x20个字节，在32位下最小chunk是0x10个字节。

1
2
3
//malloc.c
/* The smallest possible chunk */
#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))

最小申请的chunk大小，与MIN_CHUNK_SIZE大小相等。

1
2
3
4
5
//malloc.c
/* The smallest size we can malloc is an aligned minimal chunk */

#define MINSIZE  \
  (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

检查chunk是否对齐：

1
2
3
4
5
//malloc.c
#define aligned_OK(m)  (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
#define misaligned_chunk(p) \
  ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
   & MALLOC_ALIGN_MASK)

检查申请的chunk是否太大，因为边界检查的数值类型是无符号整数，防止溢出又回到0.

1
2
3
4
5
6
7
8
9
10
//malloc.c
/*
   Check if a request is so large that it would wrap around zero when
   padded and aligned. To simplify some other code, the bound is made
   low enough so that adding MINSIZE will also not wrap around zero.
 */

#define REQUEST_OUT_OF_RANGE(req)                                 \
  ((unsigned long) (req) >=						      \
   (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))

以下将其用户实际请求的大小转化为实际chunk的大小。因为每一个chunk都要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//malloc.c
#define checked_request2size(req, sz) \
({				    \
  (sz) = request2size (req);	    \
  if (((sz) < (req))		    \
      || REQUEST_OUT_OF_RANGE (sz)) \
    {				    \
      __set_errno (ENOMEM);	    \
      return 0;			    \
    }				    \
})

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

标记chunk属性

上文提到每一个chunk的低三个比特用来标识chunk的三个属性，从低到高分别为是否分配(P)、是否由mmap分配(M)、是否由main_arena分配(A)。下面是与标志位相关的宏。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//malloc.c
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1

/* extract inuse bit of previous chunk */
#define prev_inuse(p)       ((p)->mchunk_size & PREV_INUSE)


/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
#define IS_MMAPPED 0x2

/* check for mmap()'ed chunk */
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)


/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
   from a non-main arena.  This is only set immediately before handing
   the chunk to the user, if necessary.  */
#define NON_MAIN_ARENA 0x4

/* Check for chunk from main arena.  */
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)

/* Mark a chunk as not being on the main arena.  */
#define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)

获取chunk的大小可以过滤掉3个标志位，或者通过malloc_chunk结构体的成员mchunk->size来获得。

1
2
3
4
5
6
7
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

/* Get size, ignoring use bits */
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))

/* Like chunksize, but do not mask SIZE_BITS.  */
#define chunksize_nomask(p)         ((p)->mchunk_size)

获取下一个相邻和上一个相邻的chunk，这两个函数比较重要，很多漏洞就是利用这个计算方式来逃避分配或释放时的一些检查。

1
2
3
4
5
6
7
8
/* Ptr to next physical malloc_chunk. */
#define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))

/* Ptr to previous physical malloc_chunk.  Only valid if !prev_inuse (P).  */
#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))

/* Size of the chunk below P.  Only valid if !prev_inuse (P).  */
#define prev_size(p) ((p)->mchunk_prev_size)

其他的函数用到的时候再说。

bins

对于空闲的chunk，ptmalloc采用分箱式的内存管理方式，根据空闲chunk的大小和处于的状态将其放在三类不同的bin中，这三类空闲chunk的容器分别是smallbin,largebin和unsorted bin。三类bins存储在一个数组中，这个数组对应结构体malloc_state中的成员bins：

1
2
3
4
#define NBINS             128

/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];

较小的空闲chunk被释放后并不会立即放到smallbins中，为了提高分配的速率，ptmalloc会先将较小的空闲chunk先放到fastbins中，fastbins是小内存块的高速缓存，在分配小内存时，首先会查看fastbins中是否由合适的chunk，如果存在，则直接返回fastbins中符合要求的内存块，提高了分配效率。bins中一些通用的宏如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct malloc_chunk *mbinptr;
/* addressing -- note that bin_at(0) does not exist */
//通过bin的索引获取bin的链表头
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			      \
             - offsetof (struct malloc_chunk, fd))

/* analog of ++bin */
//获取下一个bin
#define next_bin(b)  ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))

/* Reminders about list directionality within bins */
//b是链表头指针，获取bin链表中第一个可用hunk
#define first(b)     ((b)->fd)

//获取bin链表中最后一个可用chunk
#define last(b)      ((b)->bk)

fastbin

它是小内存块的高速缓存，采用单链表结构对bin进行组织，每个链表中的bin采用FIFO策略。当用户所需的chunk小于fastbin的最大大小时，会先在fastbin中寻找是否有符合要求的chunk，如果有的话，直接分配该chunk。fastbin由malloc_state中的成员来维护：

1
2
3
typedef struct malloc_chunk *mfastbinptr;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];

fastbin的默认最大大小规定如下，在32位下是64字节，在64位下是128字节。在默认最大大小情况下，32位平台中的fastbin链表一共有7个，大小分别是0x10,0x18,0x20,0x28,0x30,0x38,0x40。64位平台中的fastbin链表有7个，大小分别是0x20,0x30,0x40,0x50,0x60,0x70,0x80。

1
2
3
4
5
6
7
8
/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
#ifndef M_MXFAST
#define M_MXFAST            1
#endif

#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)
#endif

ptmalloc在默认情况下会调用set_max_fast(s)函数将global_max_fast设置为DEFAULT_MXFAST：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Maximum size of memory handled in fastbins.  */
static INTERNAL_SIZE_T global_max_fast;

/*
   Set value of max_fast.
   Use impossibly small value if 0.
   Precondition: there are no existing fastbin chunks in the main arena.
   Since do_check_malloc_state () checks this, we call malloc_consolidate ()
   before changing max_fast.  Note other arenas will leak their fast bin
   entries if max_fast is reduced.
 */

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

fastbin规定了最大的fastbin大小MAX_FAST_SIZE，在32位下最大大小是80 4 / 4 = 80字节，；在64位下最大大小是80 8 / 4 = 160字节。当MAX_FAST_SIZE为0时，系统不再支持fastbin。可以使用get_max_fast函数获取当前规定的最大的fastbin大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

static inline INTERNAL_SIZE_T
get_max_fast (void)
{
  /* Tell the GCC optimizers that global_max_fast is never larger
     than MAX_FAST_SIZE.  This avoids out-of-bounds array accesses in
     _int_malloc after constant propagation of the size parameter.
     (The code never executes because malloc preserves the
     global_max_fast invariant, but the optimizers may not recognize
     this.)  */
  if (global_max_fast > MAX_FAST_SIZE)
    __builtin_unreachable ();
  return global_max_fast;
}

fastbin链表中的inuse位始终置1，在释放时不会反生改变，因此它在释放后不会与其他相邻的空闲chunk合并。但是当释放的chunk与该chunk相邻的空闲chunk合并大小大于FASTBIN_CONSOLIDATION_THRESHOLD时，就认为当前系统中存在的内存碎片较多，需要把fastbin中的所有chunk进行合并，以减少内存碎片对系统的影响，合并由malloc_consolidate函数执行。

1
#define FASTBIN_CONSOLIDATION_THRESHOLD  (65536UL)

fastbin与索引相关的宏如下：

1
2
3
4
5
6
7
8
typedef struct malloc_chunk *mfastbinptr;
//根据索引idx获取fastbin的地址
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

/* offset 2 to use otherwise unindexable first 2 bins */
//根据sz计算索引值，前两个bin没有使用，因此需要减2
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

fastbin其他宏如下，malloc_state->Flags中的bit1如果为0，表示MORECORE返回的是连续的虚拟地址空间；bit1为1表示MORECORE返回的是非连续地址空间。对于主分配区，默认返回连续地址空间；对于线程中的非主分配区，使用mmap分配大块虚拟内存，然后进行切分满足相应分配需求，默认情况下mmap映射区域不保证虚拟地址空间是连续的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
   regions.  Otherwise, contiguity is exploited in merging together,
   when possible, results from consecutive MORECORE calls.

   The initial value comes from MORECORE_CONTIGUOUS, but is
   changed dynamically if mmap is ever used as an sbrk substitute.
 */
#define NONCONTIGUOUS_BIT     (2U)

#define contiguous(M)          (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M)       (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M)   ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M)      ((M)->flags &= ~NONCONTIGUOUS_BIT)

smallbin

在bins数组中，索引2-63的bin称为smallbin，同一个smallbin双向链表中的chunk的大小相同，两个相邻索引的smallbin链表中的chunk的大小相差2*SIZE_SZ个字节。在32位平台中相差8个字节，最小的chunk大小为16字节，最大的chunk是504个字节，一共有62个双向链表。在64位平台中，相邻双向链表中相差16个字节，最小的chunk大小为32字节，最大的chunk大小为1008字节。smallbins中每个双向链表采用FIFO的规则，同一链表中先被释放的chunk会先被分配出去。相关宏如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

//判断chunk大小sz是否在smallbin的范围内
#define in_smallbin_range(sz)  \
  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

//根据sz计算其在bins中的下标
#define smallbin_index(sz) \
  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
   + SMALLBIN_CORRECTION)

largebin

在32位平台中，largebins指的大于等于512字节的空闲chunk；在64位平台中，指的是大于等于1024字节的空闲chunk。largebins一共包含63个bin，每个bin中chunk大小不相同，这些bins一共被分为6组，每组bin是一个有固定公差的等差数列，不同平台每组公差如下所示：

1
2
组数          1      2      3       4       5       6
公差(字节)    64    512     4096    32768   262144  --

32位平台计算largebin在bins中的索引的宏如下，比如第一个largebin的起始大小是512字节，512 >> 8 = 6，6 + 56 = 64，这是第一个largebin的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define largebin_index_32(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

#define largebin_index_32_big(sz)                                            \
  (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

64位的宏如下，第一个largebin的起始大小是1024字节，1024 >> 6 = 16, 16 + 48 = 64，这是第一个largebin的下标。

1
2
3
4
5
6
7
#define largebin_index_64(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

这个宏就是根据sz大小来计算其在bins中的索引，从而定位到smallbins或largebins对应大小的双向链表。

1
2
#define bin_index(sz) \
  ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))

unsorted bin

unsorted bin是smallbins和largebins的缓存，只有一个，以双向链表的形式管理chunk，所有符合进入unsorted bins中的chunk按照FIFO的规则管理。当释放的chunk不符合进入fastbin的大小要求时，且与top chunk不相邻，则会进入到unsorted bin中；当unsorted bin中的一个较大的chunk被分割后，且剩余部分大于MINSIZE时，剩余的chunk会保留在unsorted bin链表中。相关宏如下，可以看到，unsorted bin在bins中的索引为1.

1
2
/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
#define unsorted_chunks(M)          (bin_at (M, 1))

top chunk

在第一次分配时，堆会被分割成两部分，一部分分配给用户，剩下的就是top chunk，当用户请求的chunk每一个bin都不能满足其分配要求时，如果top chunk的大小小于用户请求大小，就要从top chunk中进行chunk的分割，并分配给用户，并将剩余的部分作为新的top chunk。当top chunk不满足用户分配要求时，在main_arena中通过sbrk进行heap的扩展，在non_main_arena中使用mmap进行heap的扩展。另外，top chunk的prev_iuse位始终置1，否则它前面的chunk就会被合并到top chunk中。

last remainder

当用户请求的chunk和系统找到的chunk可能存在大小不一致的情况，比如在unsorted bin中会将空闲chunk进行分割，一部分返回给用户，剩下的就是last remainder，但top chunk不是last remainder。

参考

https://sourceware.org/glibc/wiki/MallocInternals
https://ctf-wiki.github.io/ctf-wiki/pwn/linux/glibc-heap/heap_structure-zh/
《glibc内存管理ptmalloc源代码分析@华庭》