常用的宏定义
关于程序移植性所定义的固定大小
#define INTERNAL_SIZE_T size_t 为4或8
#define SIZE_SZ (sizeof(INTERNAL_SIZE_T)）4或8
#define MALLOC_ALIGNMENT (2 * SIZE_SZ) 8或16
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1) 7或15关于fastbins
#ifndef M_MXFAST
#define M_MXFAST 1
#endif
#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST (64 * SIZE_SZ / 4) //64位下为 64*8/4 == 0x80 即最大fastbin chunk
#endif关于指针转换
/* conversion from malloc headers to user pointers, and back */
#define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ)) //由mchunkptr转换为memptr
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ)) //由memptr转换为mchunkptr关于最小chunk
/* The smallest possible chunk 可以存在最小chunk*/
#define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
====>offsetof宏：获取结构体中某个元素的偏移,此处fd_nextsize的偏移为：sizeof(mchunk_prev_size)+sizeof(mchunk_size)+sizeof(fd)+sizeof(bk) == 0x20 64位
/* The smallest size we can malloc is an aligned minimal chunk 使用malloc能分配的最小chunk*/
#define MINSIZE \
(unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)) //0x20+0xf & ~0xf == 0x20 64位关于chunk大小检查
/* Same, except also perform an argument and result check. First, we check
that the padding done by request2size didn't result in an integer
overflow. Then we check (using REQUEST_OUT_OF_RANGE) that the resulting
size isn't so large that a later alignment would lead to another integer
overflow. 赋值后确保对齐后的大小没有越界，过大 */
#define checked_request2size(req, sz) \
({ \
(sz) = request2size (req); \
if (((sz) < (req)) \
|| REQUEST_OUT_OF_RANGE (sz)) \
{ \
__set_errno (ENOMEM); \
return 0; \
} \
})关于对齐操作
/* Check if m has acceptable alignment 检查空间是否对齐*/
#define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0) //对空间大小检查是不是16字节对齐，是则返回1
/*请求字节数判断*/
#define misaligned_chunk(p) \
((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
& MALLOC_ALIGN_MASK)
#define REQUEST_OUT_OF_RANGE(req) \
((unsigned long) (req) >= \
(unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
/* pad request bytes into a usable size -- internal version 如果申请的req大小如果太小就返回MINSIZE，否则就将用户请求内存大小转为实际分配内存大小*/
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
MINSIZE : \
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)关于对实际chunk的操作
/*
--------------- Physical chunk operations ---------------
*/
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1
/* extract inuse bit of previous chunk 获取PREV_INUSE位*/
#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 获取IS_MMAPPED位*/
#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. 如果来自main_arena则返回值为1 */
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)
/* Mark a chunk as not being on the main arena. 将size的NON_MAIN_ARENA位置1 */
#define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)
/*
Bits to mask off when extracting size
Note: IS_MMAPPED is intentionally not masked off from size field in
macros for which mmapped chunks should never be seen. This should
cause helpful core dumps to occur if it is tried by accident by
people extending or adapting this malloc.设置标志位
*/
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
/* Get size, ignoring use bits 获取chunk_size并将mchunk_size的后三bits置零*/
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))
/* Like chunksize, but do not mask SIZE_BITS. p指向malloc_chunk */
#define chunksize_nomask(p) ((p)->mchunk_size)
/* Ptr to next physical malloc_chunk. 本chunk的指针+自己的大小就是下一个物理相邻chunk的地址*/
#define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))
/* Size of the chunk below P. Only valid if !prev_inuse (P).获取benchunk p物理相邻的前一个chunk的大小 只有p的PREV_INUSE位为0才有效 */
#define prev_size(p) ((p)->mchunk_prev_size)
/* Set the size of the chunk below P. Only valid if !prev_inuse (P). 设置mchunk_prev_size为sz，当p的prev_inuse位是0的时候 */
#define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))
/* Ptr to previous physical malloc_chunk. Only valid if !prev_inuse (P). 自身的chunk地址减去前一个物理相邻的free chunk大小即可获得他的地址 */
#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))
/* Treat space at ptr + offset as a chunk 把从p开始以s为偏移的地址当作chunk指针*/
#define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s)))
/* extract p's inuse bit 为了获得当前chunk p的使用状态，提取物理相邻的下一个chunk的PREV_INUSE位*/
#define inuse(p) \
((((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size) & PREV_INUSE)
/* set/clear chunk as being inuse without otherwise disturbing 为了置当前chunk p的使用状态，提取并设置物理相邻的下一个chunk的PREV_INUSE位为1或0*/
#define set_inuse(p) \
((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size |= PREV_INUSE
#define clear_inuse(p) \
((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size &= ~(PREV_INUSE)
/* check/set/clear inuse bits in known places 功能和上面一样只不过通过给定的偏移s来确定unkown chunk的位置*/
#define inuse_bit_at_offset(p, s) \
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size & PREV_INUSE) //获取
#define set_inuse_bit_at_offset(p, s) \
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size |= PREV_INUSE) //设置
#define clear_inuse_bit_at_offset(p, s) \
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size &= ~(PREV_INUSE)) //设置
/* Set size at head, without disturbing its use bit 设置chunk p的size大小而不改变SIZE_BITS位*/
#define set_head_size(p, s) ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))
/* Set size/use field 这里直接把chunk p的mchunk_size赋值为s*/
#define set_head(p, s) ((p)->mchunk_size = (s))
/* Set size at footer (only when chunk is not in use) 根据偏移s设置prev_size为s*/
#define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->mchunk_prev_size = (s))关于mallc_state的数据结构
/*
-------------------- Internal data structures --------------------
*/
/* addressing -- note that bin_at(0) does not exist
bin_at(m, i) 通过 bin index 获得 bin 的链表头，m 指的是分配区，i 是索引
*/
#define bin_at(m, i) \
(mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \ //这个*2就说明了bins下标都是偶数
- 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 */
#define first(b) ((b)->fd) //获取 bin 的位于链表头的 chunk
#define last(b) ((b)->bk) //获取 bin 的位于链表尾的 chunk
#define NBINS 128
#define NSMALLBINS 64
#define SMALLBIN_WIDTH MALLOC_ALIGNMENT //16 64位
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ) //bool值为0
#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH) //(64-0)*16 == 1024
#define in_smallbin_range(sz) \
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE) //bool值，判断sz在smallbins中
/*获取size对应的smallbin index*/
#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION) //如 size==0x100, (0x100 >> 4 + 0) == 0x10
/*获取size对应的largebin index 32位下*/
#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)
#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)
#define largebin_index(sz) \
(SIZE_SZ == 8 ? largebin_index_64 (sz) \
: MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \
: largebin_index_32 (sz))
/*获取size对应的bins index，不是small bins 就是large bins*/
#define bin_index(sz) \
((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))关于unsorted bin在bins中的位置
/* The otherwise unindexable 1-bin is used to hold unsorted chunks. 前面提到的无序bin即bin[1]就是这个unsortedbin*/
#define unsorted_chunks(M) (bin_at (M, 1)) //M 即main_arenamalloc_state
该结构用于管理堆，记录每个 arena 当前申请的内存的具体状态，比如说是否有空闲 chunk，有什么大小的空闲 chunk 等等。无论是 thread arena 还是 main arena，它们都只有一个 malloc state 结构。由于 thread 的 arena 可能有多个，malloc state 结构会在最新申请的 arena 中。
注意malloc_state在libc.so中作为一个全局变量，存在于libc.so的数据段
/*sourcecode980行包含头文件*/
#include <malloc.h>
===>struct malloc_state;
typedef struct malloc_state *mstate; //定义mastate指针，指向malloc_state结构体
===>struct malloc_state
{
/* Serialize access. 该变量用于控制程序串行访问同一个分配区，当一个线程获取了分配区之后，其它线程要想访问该分配区，就必须等待该线程分配完成后才能够使用。 */
__libc_lock_define (, mutex);
/* Flags (formerly in max_fast). flags 记录了分配区的一些标志 */
int flags;
/* Set if the fastbin chunks contain recently inserted free blocks. 如果 fastbins包含free chunk 就被置1 */
/* Note this is a bool but not all targets support atomics on booleans. */
int have_fastchunks;
/* Fastbins 存放每个 fast chunk 链表头部的指针*/
mfastbinptr fastbinsY[NFASTBINS]; //64位下 size_t==8 可以算出NFASTBINS==9
/* 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 最后一次响应一个小的chunk被切出，所剩的chunk*/
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2]; //128*2-2==254
/* Bitmap of bins ptmalloc 用一个 bit 来标识某一个 bin 中是否包含空闲 chunk*/
unsigned int binmap[BINMAPSIZE]; //128/(1<<5) == 4
/* 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. 当前arena从系统中分配的内存 */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};fastbins
大多数程序经常会申请以及释放一些比较小的内存块。如果将一些较小的 chunk 释放之后发现存在与之相邻的空闲的 chunk 并将它们进行合并，那么当下一次再次申请相应大小的 chunk 时，就需要对 chunk 进行分割，这样就大大降低了堆的利用效率。因为我们把大部分时间花在了合并、分割以及中间检查的过程中。因此，ptmalloc 中专门设计了 fast bin，对应的变量就是 malloc state 中的 fastbinsY—-ctf_wiki
typedef struct malloc_chunk *mfastbinptr;
/*
This is in malloc_state.
/* Fastbins */
mfastbinptr fastbinsY[ NFASTBINS ];
*/并且每个 bin 采取 LIFO 策略,ptmalloc 会首先判断 fastbin 中相应的 bin 中是否有对应大小的空闲块，如果有的话，就会直接从这个 bin 中获取 chunk这是在引入tcache之前的情况
需要特别注意的是，fastbin 范围的 chunk 的 inuse 始终被置为 1。因此它们不会和其它被释放的 chunk 合并。但是当释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 FASTBIN_CONSOLIDATION_THRESHOLD 时，内存碎片可能比较多了，我们就需要把 fast bins 中的 chunk 都进行合并，以减少内存碎片对系统的影响
smallbins
small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为：chunk_size = 2 * SIZE_SZ index，具体如下
small bins 中一共有 62 个循环双向链表，每个链表中存储的 chunk 大小都一致。比如对于 32 位系统来说，下标 2 对应的双向链表中存储的 chunk 大小为均为 16 字节。每个链表都有链表头结点，这样可以方便对于链表内部结点的管理。此外，*small bins 中每个 bin 对应的链表采用 FIFO 的规则，所以同一个链表中先被释放的 chunk 会先被分配出去。**
largebins
arge bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致，具体如下：
这里我们以 32 位平台的 large bin 为例，第一个 large bin 的起始 chunk 大小为 512 字节，位于第一组，所以该 bin 可以存储的 chunk 的大小范围为 [512,512+64)。
unsorted bin
*
Unsorted chunks
All remainders from chunk splits(分割chunk后的剩余块), as well as all returned chunks(所有被free的 chunk),
are first placed in the "unsorted" bin. They are then placed
in regular bins after malloc gives them ONE chance to be used before
binning(之后他们都有机会进入属于他们的常规bins). So, basically, the unsorted_chunks list acts as a queue,
with chunks being placed on it in free (and malloc_consolidate),
and taken off (to be either used or placed in bins) in malloc.
The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
does not have to be taken into account in size comparisons(不会考虑他们的大小顺序).
*/就是把unsorted bin作为其他bins的缓冲区
注意bins和fastbins是区分开的
举一例子：
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
int main()
{
void* p = malloc(0x81);
void* p1 = malloc(0x80);
void* p2 = malloc(0x90);
/*void* p1 = malloc(0x90);
void* p2 = malloc(0x90);
void* p3 = malloc(0x90);
void* p4 = malloc(0x90);
void* p5 = malloc(0x100);
*/
free(p);
free(p2);
return 0;
}在执行第一个free后：
pwndbg> parseheap
addr prev size status fd bk
0x602000 0x0 0x90 Freed 0x7ffff7dd1b78 0x7ffff7dd1b78
0x602090 0x90 0x90 Used None None
0x602120 0x0 0xa0 Used None None
pwndbg> bins
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
unsortedbin
all: 0x0
smallbins
empty
largebins
empty
pwndbg> 按照规则，p应该会被放到unsorted bin，但是在parseheap中却没看到，我们可以看一下main_arena:
pwndbg> x/32gx &main_arena
0x7ffff7dd1b20 <main_arena>: 0x0000000100000000 0x0000000000000000
0x7ffff7dd1b30 <main_arena+16>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b40 <main_arena+32>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b50 <main_arena+48>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b60 <main_arena+64>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b70 <main_arena+80>: 0x0000000000000000 0x00000000006021c0 <========top chunk
0x7ffff7dd1b80 <main_arena+96>: 0x0000000000000000 0x0000000000602000 <========unsorted bin
0x7ffff7dd1b90 <main_arena+112>: 0x0000000000602000 0x00007ffff7dd1b88
0x7ffff7dd1ba0 <main_arena+128>: 0x00007ffff7dd1b88 0x00007ffff7dd1b98
0x7ffff7dd1bb0 <main_arena+144>: 0x00007ffff7dd1b98 0x00007ffff7dd1ba8
0x7ffff7dd1bc0 <main_arena+160>: 0x00007ffff7dd1ba8 0x00007ffff7dd1bb8
0x7ffff7dd1bd0 <main_arena+176>: 0x00007ffff7dd1bb8 0x00007ffff7dd1bc8
0x7ffff7dd1be0 <main_arena+192>: 0x00007ffff7dd1bc8 0x00007ffff7dd1bd8
0x7ffff7dd1bf0 <main_arena+208>: 0x00007ffff7dd1bd8 0x00007ffff7dd1be8
0x7ffff7dd1c00 <main_arena+224>: 0x00007ffff7dd1be8 0x00007ffff7dd1bf8
0x7ffff7dd1c10 <main_arena+240>: 0x00007ffff7dd1bf8 0x00007ffff7dd1c08可以看到p chunk已经被放到了unsorted bin的链表中，只是插件没显示出来，很常见
unlink
unlink 用来将一个双向链表（只存储空闲的 chunk）中的一个元素取出来，可能在以下地方使用
- malloc
- 从恰好大小合适的 large bin 中获取 chunk。
- 这里需要注意的是 fastbin 与 small bin 就没有使用 unlink，这就是为什么漏洞会经常出现在它们这里的原因。
- 依次遍历处理 unsorted bin 时也没有使用 unlink 。
- 从比请求的 chunk 所在的 bin 大的 bin 中取 chunk。
- 从恰好大小合适的 large bin 中获取 chunk。
- free
- 后向合并，合并物理相邻低地址空闲 chunk。
- 前向合并，合并物理相邻高地址空闲 chunk（除了 top chunk）。
- malloc_consolidate
- 后向合并，合并物理相邻低地址空闲 chunk。
- 前向合并，合并物理相邻高地址空闲 chunk（除了 top chunk）。
- realloc
- 前向扩展，合并物理相邻高地址空闲 chunk（除了 top chunk）。
unlink在libc中直接被定义成了一个宏
\/* Take a chunk off a bin list. Unlink操作 They are all free chunk*/
/*
1：检查两个记录chunk p size的字段是否相等
2：检查fd，bk是否回指chunk p
3：进行unlink
4：如果size属于smallbins范围内则结束该函数
*/
/* Take a chunk off a bin list av==arena P==目标 FD==下一个 BK==前一个*/
#define unlink(AV, P, BK, FD) { \
/*由于 P 已经在双向链表中，所以有两个地方记录其大小，所以检查一下其大小是否一致。*/
if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0)) \
malloc_printerr ("corrupted size vs. prev_size"); \
/*获取寻找其他两个chunk*/
FD = P->fd; \
BK = P->bk; \
/*检查：要求fd->bk=p,以及bk->fd=p,两边指中间*/
if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
malloc_printerr (check_action, "corrupted double-linked list", P, AV); \
else { \
FD->bk = BK; \
BK->fd = FD; \
/*检查：如果size范围在smallbins中则完成unlink，否则对largebin进行操作*/
if (!in_smallbin_range (P->size) \
&& __builtin_expect (P->fd_nextsize != NULL, 0)) { \
if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0) \
|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) \
malloc_printerr (check_action, \
"corrupted double-linked list (not small)", \
P, AV); \
if (FD->fd_nextsize == NULL) { \
if (P->fd_nextsize == P) \
FD->fd_nextsize = FD->bk_nextsize = FD; \
else { \
FD->fd_nextsize = P->fd_nextsize; \
FD->bk_nextsize = P->bk_nextsize; \
P->fd_nextsize->bk_nextsize = FD; \
P->bk_nextsize->fd_nextsize = FD; \
} \
} else { \
P->fd_nextsize->bk_nextsize = P->bk_nextsize; \
P->bk_nextsize->fd_nextsize = P->fd_nextsize; \
} \
} \
} \
}以smallbins中的unlink为例：
malloc_init_state–malloc_state初始化
static void malloc_init_state(mstate av) {
int i;
mbinptr bin;
/* Establish circular links for normal bins 从bins[1]开始为其初始化fd,bk指针*/
for (i = 1; i < NBINS; ++i) { //每次初始化两个bins数组，这里只是都指向自己地址-0x10
bin = bin_at(av, i);
bin->fd = bin->bk = bin;
}
#if MORECORE_CONTIGUOUS
if (av != &main_arena)
#endif
set_noncontiguous(av);
if (av == &main_arena) set_max_fast(DEFAULT_MXFAST);
// 设置 flags 标记目前没有fast chunk
av->flags |= FASTCHUNKS_BIT;
// 就是 unsorted bin
av->top = initial_top(av);
}我们对第一次malloc来跟踪一下：
► 0x7ffff7aae550 <malloc> push rbp
0x7ffff7aae551 <malloc+1> push rbx
0x7ffff7aae552 <malloc+2> sub rsp, 8
0x7ffff7aae556 <malloc+6> mov rax, qword ptr [rip + 0x322993]
0x7ffff7aae55d <malloc+13> mov rax, qword ptr [rax]
0x7ffff7aae560 <malloc+16> test rax, rax
──────────────────────────────────────────────────────────────[ SOURCE (CODE) ]──────────────────────────────────────────────────────────────
In file: /glibc/source/glibc-2.23/malloc/malloc.c
2898
2899 /*------------------------ Public wrappers. --------------------------------*/
2900
2901 void *
2902 __libc_malloc (size_t bytes)
► 2903 {
2904 mstate ar_ptr;
2905 void *victim;
2906
2907 void *(*hook) (size_t, const void *)
2908 = atomic_forced_read (__malloc_hook);这个时候main_arena应该都是0：
pwndbg> x/32gx &main_arena
0x7ffff7dd1b20 <main_arena>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b30 <main_arena+16>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b40 <main_arena+32>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b50 <main_arena+48>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b60 <main_arena+64>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b70 <main_arena+80>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b80 <main_arena+96>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b90 <main_arena+112>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1ba0 <main_arena+128>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1bb0 <main_arena+144>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1bc0 <main_arena+160>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1bd0 <main_arena+176>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1be0 <main_arena+192>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1bf0 <main_arena+208>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1c00 <main_arena+224>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1c10 <main_arena+240>: 0x0000000000000000 0x0000000000000000
pwndbg> 继续在将会执行malloc_consolidate：
──────────────────────────────────────────────────────────────[ SOURCE (CODE) ]──────────────────────────────────────────────────────────────
In file: /glibc/source/glibc-2.23/malloc/malloc.c
3446
3447 else
3448 {
3449 idx = largebin_index (nb);
3450 if (have_fastchunks (av))
► 3451 malloc_consolidate (av);
3452 }
3453
3454 /*
3455 Process recently freed or remaindered chunks, taking one only if
3456 it is exact fit, or, if this a small request, the chunk is remainder from最后会到：
──────────────────────────────────────────────────────────────[ SOURCE (CODE) ]──────────────────────────────────────────────────────────────
In file: /glibc/source/glibc-2.23/malloc/malloc.c
4210
4211 }
4212 } while (fb++ != maxfb);
4213 }
4214 else {
► 4215 malloc_init_state(av);
4216 check_malloc_state(av);
4217 }
4218 }
4219
4220
pwndbg> x/32gx &main_arena
0x7ffff7dd1b20 <main_arena>: 0x0000000000000001 0x0000000000000000
0x7ffff7dd1b30 <main_arena+16>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b40 <main_arena+32>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b50 <main_arena+48>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b60 <main_arena+64>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b70 <main_arena+80>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b80 <main_arena+96>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b90 <main_arena+112>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1ba0 <main_arena+128>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1bb0 <main_arena+144>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1bc0 <main_arena+160>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1bd0 <main_arena+176>: 0x0000000000000000 0x0000000000000000执行完malloc_consolidate 后就会将bins初始化为指向自己地址-0x10，并且可以看到malloc_init_state中这样的定义：mbinptr bin;说明这里在对bins进行复制操作时把他们看作了chunk，利用其fd，和bk成员。所以其实这些bins就可以看作是一个chunk，不完整的chunk有效部分只有fd，和bk段作为双向链表的表头。当malloc_init_state执行完后：
pwndbg> x/32gx &main_arena
0x7ffff7dd1b20 <main_arena>: 0x0000000000000001 0x0000000000000000
0x7ffff7dd1b30 <main_arena+16>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b40 <main_arena+32>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b50 <main_arena+48>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b60 <main_arena+64>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b70 <main_arena+80>: 0x0000000000000000 0x0000000000000000
0x7ffff7dd1b80 <main_arena+96>: 0x0000000000000000 0x00007ffff7dd1b78 <=======注意他们的值与自己地址的关系
0x7ffff7dd1b90 <main_arena+112>: 0x00007ffff7dd1b78 0x00007ffff7dd1b88
0x7ffff7dd1ba0 <main_arena+128>: 0x00007ffff7dd1b88 0x00007ffff7dd1b98
0x7ffff7dd1bb0 <main_arena+144>: 0x00007ffff7dd1b98 0x00007ffff7dd1ba8
0x7ffff7dd1bc0 <main_arena+160>: 0x00007ffff7dd1ba8 0x00007ffff7dd1bb8
0x7ffff7dd1bd0 <main_arena+176>: 0x00007ffff7dd1bb8 0x00007ffff7dd1bc8
0x7ffff7dd1be0 <main_arena+192>: 0x00007ffff7dd1bc8 0x00007ffff7dd1bd8
0x7ffff7dd1bf0 <main_arena+208>: 0x00007ffff7dd1bd8 0x00007ffff7dd1be8
0x7ffff7dd1c00 <main_arena+224>: 0x00007ffff7dd1be8 0x00007ffff7dd1bf8
0x7ffff7dd1c10 <main_arena+240>: 0x00007ffff7dd1bf8 0x00007ffff7dd1c08
pwndbg> malloc_consolidate
该函数主要有两个功能
若 fastbin 未初始化，即 global_max_fast 为 0，那就初始化 malloc_state。
如果已经初始化的话，就合并 fastbin 中的 chunk。
/* If max_fast is 0, we know that av hasn't yet been initialized, in which case do so below */ // 说明 fastbin 已经初始化 if (get_max_fast() != 0) { // 清空 fastbin 标记 // 因为要合并 fastbin 中的 chunk 了。 clear_fastchunks(av); // unsorted_bin = unsorted_chunks(av); /* Remove each chunk from fast bin and consolidate it, placing it then in unsorted bin. Among other reasons for doing this, placing in unsorted bin avoids needing to calculate actual bins until malloc is sure that chunks aren't immediately going to be reused anyway. */ // 按照 fd 顺序遍历 fastbin 的每一个 bin，将 bin 中的每一个 chunk 合并掉。 maxfb = &fastbin(av, NFASTBINS - 1); fb = &fastbin(av, 0); do { p = atomic_exchange_acq(fb, NULL); if (p != 0) { do { check_inuse_chunk(av, p); nextp = p->fd; /* Slightly streamlined version of consolidation code in * free() */ size = chunksize(p); nextchunk = chunk_at_offset(p, size); nextsize = chunksize(nextchunk); if (!prev_inuse(p)) { prevsize = prev_size(p); size += prevsize; p = chunk_at_offset(p, -((long) prevsize)); unlink(av, p, bck, fwd); } if (nextchunk != av->top) { // 判断 nextchunk 是否是空闲的。 nextinuse = inuse_bit_at_offset(nextchunk, nextsize); if (!nextinuse) { size += nextsize; unlink(av, nextchunk, bck, fwd); } else // 设置 nextchunk 的 prev inuse 为0，以表明可以合并当前 fast chunk。 clear_inuse_bit_at_offset(nextchunk, 0); first_unsorted = unsorted_bin->fd; unsorted_bin->fd = p; first_unsorted->bk = p; if (!in_smallbin_range(size)) { p->fd_nextsize = NULL; p->bk_nextsize = NULL; } set_head(p, size | PREV_INUSE); p->bk = unsorted_bin; p->fd = first_unsorted; set_foot(p, size); } else { size += nextsize; set_head(p, size | PREV_INUSE); av->top = p; } } while ((p = nextp) != 0); } } while (fb++ != maxfb);
__libc_malloc
一般我们会使用 malloc 函数来申请内存块，可是当仔细看 glibc 的源码实现时，其实并没有 malloc 函数。其实该函数真正调用的是 libc_malloc 函数。为什么不直接写个 malloc 函数呢，因为有时候我们可能需要不同的名称。此外，libc_malloc 函数只是用来简单封装 _int_malloc 函数。_int_malloc 才是申请内存块的核心，注意：用户申请的字节一旦进入申请内存函数中就变成了无符号整数。
void *
__libc_malloc (size_t bytes)
{
mstate ar_ptr;
void *victim;
void *(*hook) (size_t, const void *)
= atomic_forced_read (__malloc_hook); //检查钩子函数
if (__builtin_expect (hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS (0)); //如果hook != Null则执行hook中的函数
arena_get (ar_ptr, bytes); //寻找对应arena
victim = _int_malloc (ar_ptr, bytes); //_int_malloc 函数去申请对应的内存
/* Retry with another arena only if we were able to find a usable arena
before. */
if (!victim && ar_ptr != NULL) //如果分配失败的话，ptmalloc 会尝试再去寻找一个可用的 arena，并分配内存
{
LIBC_PROBE (memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}
if (ar_ptr != NULL)
(void) mutex_unlock (&ar_ptr->mutex);
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
ar_ptr == arena_for_chunk (mem2chunk (victim)));
return victim; //返回内存
}
libc_hidden_def (__libc_malloc)_int_malloc
_int_malloc 是内存分配的核心函数，其核心思路有如下
1：它根据用户申请的内存块大小以及相应大小 chunk 通常使用的频度（fastbin chunk, small chunk, large chunk），依次实现了不同的分配方法。
2：它由小到大依次检查不同的 bin 中是否有相应的空闲块可以满足用户请求的内存。
3：当所有的空闲 chunk 都无法满足时，它会考虑 top chunk。
4：当 top chunk 也无法满足时，堆分配器才会进行内存块申请。
在进入该函数后，函数立马定义了一系列自己需要的变量，并将用户申请的内存大小转换为内部的 chunk 大小。
初始数据
static void *_int_malloc(mstate av, size_t bytes) { //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); //将bytes规范对齐，并赋值给nbarena
/* There are no usable arenas. Fall back to sysmalloc to get a chunk from mmap. 如果没有可用的arena那么将会调用sysmalloc来获得chunk */
if (__glibc_unlikely(av == NULL)) {
void *p = sysmalloc(nb, av);
if (p != NULL) alloc_perturb(p, bytes);
return p;
}fastbins
如果申请的 chunk 的大小位于 fastbin 范围内，需要注意的是这里比较的是无符号整数。此外，是从 fastbin 的头结点开始取 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())) {
//由nb获取对应fastbins的index
idx = fastbin_index(nb); //可以看出这是exact fit
//fastbinsY中获取对应index的free chunk
mfastbinptr *fb = &fastbin(av, idx);
mchunkptr pp = *fb; //fb中存放&fastbinsY[index]，mchunkptr存放fastbinsY[index]的free chunk地址
// 利用fd遍历对应的bin内是否有空闲的chunk块，
do {
victim = pp;
if (victim == NULL) break;
} while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd,
victim)) != victim);
// 存在可以利用的chunk
if (victim != 0) {
// 检查取到的 chunk 大小是否与相应的 fastbin 索引一致。
// 根据取得的 victim ，利用 chunksize 计算其大小。
// 利用fastbin_index 计算 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;
}
// 细致的检查。。只有在 DEBUG 的时候有用
check_remalloced_chunk(av, victim, nb);
// 将获取的到chunk转换为mem模式
void *p = chunk2mem(victim);
// 如果设置了perturb_type, 则将获取到的chunk初始化为 perturb_type ^ 0xff
alloc_perturb(p, bytes);
return p; //返回mem地址
}
}smallbins
/*
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.)
*/
if (in_smallbin_range(nb)) {
// 获取 small bin 的索引
idx = smallbin_index(nb);
// 获取对应 small bin 中的 chunk 指针
bin = bin_at(av, idx); //可以看出这是exact fit
// 先执行 victim = last(bin)，获取 small bin 的最后一个 chunk
// 如果 victim = bin ，那说明该 bin 为空。
// 如果不相等，那么会有两种情况
if ((victim = last(bin)) != bin) { //如果这里对应的bin没有插入freechunk 则last (bin) == bin
// 第一种情况，small bin 还没有初始化。
if (victim == 0) /* initialization check */
// 执行初始化，将 fast bins 中的 chunk 进行合并，并给bins初始化
malloc_consolidate(av);
// 第二种情况，small bin 中存在空闲的 chunk
else {
// 获取 small bin 中倒数第二个 chunk 。
bck = victim->bk;
// 检查 bck->fd 是不是 victim，防止伪造
if (__glibc_unlikely(bck->fd != victim)) { //如果victim->bk还指向这一个free chunk 那么该free chunk的fd是要回指victim的
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
//设置物理相邻的下一个chunk的inuse位为1，因为本chunk已经是要被使用了
set_inuse_bit_at_offset(victim, nb);
// 修改 small bin 链表，将 small bin 的最后一个 chunk 取出来，FIFO
bin->bk = bck;//恢复链表
bck->fd = bin;
// 如果不是 main_arena，设置对应的标志
if (av != &main_arena) set_non_main_arena(victim);
// 细致的检查，非调试状态没有作用
check_malloced_chunk(av, victim, nb);
// 将申请到的 chunk 转化为对应的 mem 状态
void *p = chunk2mem(victim);
// 如果设置了 perturb_type , 则将获取到的chunk初始化为 perturb_type ^ 0xff
alloc_perturb(p, bytes);
return p;
}
}
}放入largebins
当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时，就会考虑是不是 large bin。但是，其实在 large bin 中并没有直接去扫描对应 bin 中的 chunk，而是先利用 malloc_consolidate（参见 malloc_state 相关函数） 函数处理 fast bin 中的 chunk，将有可能能够合并的 chunk 先进行合并后放到 unsorted bin 中，不能够合并的就直接放到 unsorted bin 中，然后再在下面的大循环中进行相应的处理。为什么不直接从相应的 bin 中取出 large chunk 呢？这是 ptmalloc 的机制，它会在分配 large chunk 之前对堆中碎片 chunk 进行合并，以便减少堆中的碎片。
_int_malloc:
.....
....
..
else {
// 获取large bin的下标。
idx = largebin_index(nb);
// 如果存在fastbin的话，会处理 fastbin
if (have_fastchunks(av)) malloc_consolidate(av);
}遍历 unsorted bin
如果在之前的遍历中(smallbins fastbins)无法满足best fit则遍历 unsorted bin
在接下来的这个循环中，主要做了以下的操作
- 按照 FIFO 的方式逐个将 unsorted bin 中的 chunk 取出来
- 如果是 small request，则考虑是不是恰好满足，是的话，直接返回。
- 如果不是的话，放到对应的 bin 中。
- 尝试从 large bin 中分配用户所需的内存
先考虑 unsorted bin，再考虑 last remainder 但是对于 small bin chunk 的请求会有所例外 （SMALL REQUEST）：
// 如果 unsorted bin 不为空
// First In First Out
while ((victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
// victim 为 unsorted bin 的最后一个 chunk
// bck 为 unsorted bin 的倒数第二个 chunk
bck = victim->bk;
// 判断得到的 chunk 是否满足要求，不能过小，也不能过大
// 一般 system_mem 的大小为132K
if (__builtin_expect(chunksize_nomask(victim) <= 2 * SIZE_SZ, 0) ||
__builtin_expect(chunksize_nomask(victim) > av->system_mem, 0))
malloc_printerr(check_action, "malloc(): memory corruption",
chunk2mem(victim), av);
// 得到victim对应的chunk大小。
size = chunksize(victim);如果用户的请求为 small bin chunk，那么我们首先考虑 last remainder，如果 last remainder 是 unsorted bin 中的唯一一块的话， 并且 last remainder 的大小分割后还可以作为一个 chunk
/*
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.
*/
/*1处于smallbinsfanwei 2存在last_remainder 3 size大于nb + MINSIZE，保证可以进行切割 */
if (in_smallbin_range(nb) && bck == unsorted_chunks(av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE)) {
/* split and reattach remainder */
// 获取新的 remainder 的大小
remainder_size = size - nb;
// 获取新的 remainder 的位置
remainder = chunk_at_offset(victim, nb);
// 更新 unsorted bin 的情况
unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
// 更新 av 中记录的 last_remainder
av->last_remainder = remainder;
// 更新last remainder的指针
remainder->bk = remainder->fd = unsorted_chunks(av);
if (!in_smallbin_range(remainder_size)) {
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
// 设置victim的头部，
set_head(victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
// 设置 remainder 的头部
set_head(remainder, remainder_size | PREV_INUSE);
// 设置记录 remainder 大小的 prev_size 字段，因为此时 remainder 处于空闲状态。
set_foot(remainder, remainder_size);
// 细致的检查，非调试状态下没有作用
check_malloced_chunk(av, victim, nb);
// 将 victim 从 chunk 模式转化为mem模式
void *p = chunk2mem(victim);
// 如果设置了perturb_type, 则将获取到的chunk初始化为 perturb_type ^ 0xff
alloc_perturb(p, bytes);
return p;
}这部分代码的整体意思就是遍历unsortedbin，从中查找是否有符合用户要求大小的chunk并返回。
第一个while循环从尾到头依次取出unsortedbin中的所有chunk，将该chunk对应的前一个chunk保存在bck中，并将大小保存在size中。
如果用户需要分配的内存大小对应的chunk属于smallbin，unsortedbin中只有这一个chunk，并且该chunk属于last remainder chunk且其大小大于用户需要分配内存大小对应的chunk大小加上最小的chunk大小（保证可以拆开成两个chunk），就将该chunk拆开成两个chunk，分别为victim和remainder，进行相应的设置后，将用户需要的victim返回。
如果不能拆开，就从unsortedbin中取出该chunk（victim）。
再下来，如果刚刚从unsortedbin中取出的victim正好是用户需要的大小nb，就设置相应的标志位，直接返回该victim
取出：
/* remove from unsorted list 最后的chunk解除链接 */
unsorted_chunks(av)->bk = bck;
bck->fd = unsorted_chunks(av);如果从 unsorted bin 中取出来的 chunk 大小正好合适，就直接使用。
/* Take now instead of binning if exact fit */
if (size == nb)
{
set_inuse_bit_at_offset (victim, size); //设置物理相邻的下一个chunk的inuse位为1
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;
}如果不适合那就看其大小，来放到smallbins或者largebins中
smallbins:
/* place chunk in bin */
if (in_smallbin_range(size)) {
victim_index = smallbin_index(size); //获取下标
bck = bin_at(av, victim_index); //获取表头
fwd = bck->fd; //获取第一个chunk
......
....
...
/*
mark_bin (av, victim_index); //标记
victim->bk = bck; //vim的前一个chunk指针，指向表头
victim->fd = fwd; //vim的下一个chunk指针，指向原来的第一个chunk （FIFO，chunk是从队列的尾部提取的）
fwd->bk = victim; //bk指针恢复
bck->fd = victim; //fd指针恢复largebins
如果largebins中没有chunk
victim_index = largebin_index (size); //下标
bck = bin_at (av, victim_index); //获取表头
fwd = bck->fd; //获取第一个chunk
/* maintain large bins in sorted order */
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); //是否属于main_arena
}
......
....
..
else
victim->fd_nextsize = victim->bk_nextsize = victim; //如果largebins没有chunk，则fd_nextsize和bk_nextsize都指向自己
.....
...
..
mark_bin (av, victim_index);
/*插入对应largebins，并作为第一个*/
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;如果有chunk，且victim是最小的
/* maintain large bins in sorted order */
if (fwd != bck) //存在chunk
{
/* 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); //属于main_arena
if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) //bck->bk bin中最后一个chunk也是largbin中最小的chunk
{
fwd = bck; //表头
bck = bck->bk; //指向最min_chunk
victim->fd_nextsize = fwd->fd; //victim->fd_nextsize指向bin中第一个chunk
victim->bk_nextsize = fwd->fd->bk_nextsize; //victim->bk_nextsize指向原min_chunk
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim; //原max_chunk的bk_nextsize 指向victim
}
.......
.....
...
/*插入最后的位置，恢复链接*/
mark_bin (av, victim_index);
victim->bk = bck; //victim->bk指向原min
victim->fd = fwd; //fd指向表头
fwd->bk = victim;
bck->fd = victim; 有chunk，但victim不是最小的
{
assert ((fwd->size & NON_MAIN_ARENA) == 0);
/*循环寻找size的合使位置*/
while ((unsigned long) size < fwd->size)
{
fwd = fwd->fd_nextsize; //更新下一个fwd
assert ((fwd->size & NON_MAIN_ARENA) == 0); //属于main_arena
}
/*如果能有幸找到完全一样的size，直接插入该chunk后*/
if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;
/*没一样的size就建立nextsize链接*/
else
{
/*其实是一个宏观的双向链表插入操作*/
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk; //前一个chunk
}
.....
...
..
/*双向链表插入操作 */
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim; 这个从unsortedbin中提取chunk的操作会最多循环1000次
再次进行chunk提取
先尝试largebin提取
/*在largebins中提取*/
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx); //获取表头
/* skip scan if empty or largest chunk is too small */
/*bin有chunk，并且有足够大chunk*/
if ((victim = first (bin)) != bin &&
(unsigned long) (victim->size) >= (unsigned long) (nb))
{ //first(bin)->size是最大的
victim = victim->bk_nextsize; //反向遍历，从最小开始
/*遍历寻找第一个足够大的chunk*/
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. */
/*1取到的chunk不是bin中的最后一个chunk 2该chunk与下一个chunk大小相等*/
if (victim != last (bin) && victim->size == victim->fd->size)
victim = victim->fd; //取该nextsize的下一个chunk，因为第一个chunk存放了nextsize，取出比较麻烦
remainder_size = size - nb; //计算切割后的size，即lastremainder
unlink (av, victim, bck, fwd); //unlink操作
/* Exhaust */
/*如果remainder不能单独成chunk*/
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size); //置1物理相邻下一个chunk的inuse位物理相邻下一个chunk的inuse位
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
else
{
remainder = chunk_at_offset (victim, nb); //截取剩下的部分，视为remainder
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks (av); //获取unsortedbin表头
fwd = bck->fd; //第一个chunk
/*判断unsortedbin是否被破坏*/
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
/*双向链表插入unsortedbin*/
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
/*如果不处于smallbins范围*/
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
/*设置victim的size字段*/
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
/*设置remainder的size字段*/
set_head (remainder, remainder_size | PREV_INUSE);
/*设置remainder物理相邻的下一个chunk的prev_size为remainder_size*/
set_foot (remainder, remainder_size);
}
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim); //指针转换
alloc_perturb (p, bytes);
return p; //用户地址返回
}
}如果还没找到
++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;
}
}这一部分的整体意思是，前面在
largebin中寻找特定大小的空闲chunk，如果没找到，这里就要遍历largebin中的其他更大的chunk双向链表，继续寻找。
开头的++idx就表示，这里要从largebin中下一个更大的chunk双向链表开始遍历。ptmalloc中用一个bit表示malloc_state的bins数组中对应的位置上是否有空闲chunk，bit为1表示有，为0则没有。ptmalloc通过4个block（一个block4字节）一共128个bit管理bins数组。因此，代码中计算的block表示对应的idx属于哪一个block，map就表是block对应的bit组成的二进制数字。
接下来进入for循环，如果bit > map，表示该map对应的整个block里都没有大于bit位置的空闲的chunk，因此就要找下一个block。因为后面的block只要不等于0，就肯定有空闲chunk，并且其大小大于bit位置对应的chunk，下面就根据block，取出block对应的第一个双向链表的头指针。这里也可以看出，设置map和block也是为了加快查找的速度。如果遍历完所有block都没有空闲chunk，这时只能从top chunk里分配chunk了，因此跳转到use_top。
如果有空闲chunk，接下来就通过一个while循环依次比较找出到底在哪个双向链表里存在空闲chunk，最后获得空闲chunk所在的双向链表的头指针bin和位置bit。
接下来，如果找到的双向链表又为空，则继续前面的遍历，找到空闲chunk所在的双向链表的头指针bin和位置bit。如果找到的双向链表不为空，就和上面一部分再largebin中找到空闲chunk的操作一样了
Top
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.)
*/
victim = av->top; //获取top
size = chunksize (victim); //获取top size
/*1top_size够大 2切割后的remainder能成chunk 那么直接切割*/
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
/*设置标记字段*/
// 这里设置 PREV_INUSE 是因为 top chunk 前面的 chunk 如果不是 fastbin，就必然会和
// top chunk 合并，所以这里设置了 PREV_INUSE。
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. */
/*如果上述条件不满足 判断是否有fast chunk*/
else if (have_fastchunks (av))
{
/*用于fastbins chunk 合并*/
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
*/
/*最后的方法就是系统调用sysmalloc了*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}
}总结
第一步：如果进程没有关联的分配区，就通过sysmalloc从操作系统分配内存。
第二步：从fastbin查找对应大小的chunk并返回，如果失败进入第三步。
第三步：从smallbin查找对应大小的chunk并返回，或者将fastbin中的空闲chunk合并放入unsortedbin中，如果失败进入第四步。
第四步：遍历unsortedbin，从unsortedbin中查找对应大小的chunk并返回，根据大小将unsortedbin中的空闲chunk插入smallbin或者largebin中。进入第五步。
第五步：从largebin指定位置查找对应大小的chunk并返回，如果失败进入第六步。
第六步：从largebin中大于指定位置的双向链表中查找对应大小的chunk并返回，如果失败进入第七步。
第七步：从topchunk中分配对应大小的chunk并返回，topchunk中没有足够的空间，就查找fastbin中是否有空闲chunk，如果有，就合并fastbin中的chunk并加入到unsortedbin中，然后跳回第四步。如果fastbin中没有空闲chunk，就通过sysmalloc从操作系统分配内存。
参考：https://elixir.bootlin.com/glibc/glibc-2.23.90/source/malloc/malloc.c
https://blog.csdn.net/conansonic/article/details/50241523
https://ctf-wiki.github.io/ctf-wiki/pwn/linux/glibc-heap/implementation/malloc-zh/
