malloc.c源码阅读之__libc_free

学堆的最好方式还是读malloc.c的源码，所以有了这篇文章，目前计划的是分两篇，一篇是读__libc_free函数，一篇是读__libc_malloc函数，本篇是读free函数的源码。之后有空可能还会写calloc或者realloc

读代码使用的是https://code.woboq.org/userspace/glibc/malloc/malloc.c.html

PS: 默认研究64位

首先是我画的总的流程图，顺着流程图来

__libc_free(void *mem)

free在malloc.c中定义在__libc_free函数中，只有一个参数void *mem，需要free的地址。

首先是检查__free_hook，在main_arena前面有个地方是储存malloc_hook和free_hook的地方(0CTF 2017 Babyheap中有涉及)，如果该值不为NULL(0)，则把mem当做参数，执行free_hook，执行结束后直接return，就不执行free的后续代码了

如果不存在free_hook，这一步是检查mem == 0，如果true，则直接return

如果false，则根据mem对p进行赋值，mem指向的是chunk中储存数据的地方，p是指向chunk header的地方。比如32位系统，p = mem-8，64位系统则是p=mem-16

然后根据chunk size的第二个标志位来判断该地址空间是否是由mmap分配的，如果true，也就是标志位为1，则执行一系列操作(暂不研究mmap相关的操作，先研究brk)，然后执行munmap_chunk(p)，然后执行return

如果标志位为0(false)，则根据第三个(最高位)标志位判断该chunk是否不属于main_arena，如果标志位为0，表示属于，则把main_arena的地址赋值给ar_ptr

接下来把ar_ptr和p当做参数，去执行_int_free函数：_int_free(ar_ptr, p, 0)

_int_free(mstate av, mchunkptr p, int have_lock)

这里提一下，参数中的mstate表示的是malloc_state结构体也就是main_arena的结构体，mchunkptr表示的是malloc_chunk的结构体（PS：如果结构体还不知道，就别来学堆了）

在写blog的过程中发现了一个别人做的流程图，而且做的挺不错了，所以我就懒得自己画了，而且画的挺全的，之后的malloc的流程图也直接用这个了：

未区分bin之前

在未通过size来判断该chunk free之后是处于哪个bin之前，有进行一些通用检测，代码不长，也挺简单的。

1. get chunksize，通过p->mchunksize，去掉标志位后获取chunk的size
2. 检查p的合法性
3. 检查size的合法性

####检查p的合法性

有两个判断，一个是需要p < (-size)，比如在64位系统中，地址最大是8byte的，如果p > (-size)，那么p + size就超出了合法的地址空间。还有一个检查是对齐的问题，比如64位系统是0x10对齐，所以一个合法的地址都是0x10的倍数，如果p & 0xf != 0就表示p不是16的倍数，则不是一个合法的地址。

总结下，如果p > (-size) || (p&0xf)为true ，判断出属于非法地址则报错(free(): invalid pointer)退出(报错具体的操作暂时不想详细研究)。

检查size的合法性

检查完地址的合法性后就是检查size的合法性，一个是大小问题，首先要size >= MINSIZE，然后因为地址已经是0x10对齐了，所以去掉标志位的size也应该要是0x10的倍数，size & 0xf == 0，其实我觉得这个检查没必要，因为size赋值的时候已经把标志位清零了，然后这期间也没有size的赋值操作了。

总结下，如果size < MINSIZE || size&0xf为true，则表示无效的size，报错(free(): invalid size)退出。

Fastbin

在进行chunk的一些简单的check之后，就是进入各个bin的分支了，首先是fastbin分支

(unsigned long)(size) <= (unsigned long)(get_max_fast ())

如果size小于等于fastbin的最大size，则进入fastbin分支。大致流程如下：

1. 下一个chunk的size要大于2*SIZE_SZ
2. 下一个chunk的size要小于arena->system_mem
3. arena->flags最后一bit清零
4. 根据size获取该chunk该放进哪个fastbin
5. fastbin中原本的值不能等于当前chunk的地址
6. 如果fastbin不为空，获取size对应的index
7. chunk的fd赋值为fastbin的值
8. fastbin赋值为当前chunk的地址
9. fastbin entry判断

fastbin的流程很简单，大致就上面9个步骤

next chunk size check

通过当前chunk的地址加上size，就可以得到下一个chunk。然后获取到下一个chunk的size，对其上下限进行判断，需要大于0x10，小于heap的总size

检查完以后，下面执行了两个函数，一个是free_perturb，目的是对chunk的data块通过memset赋值，但是默认情况下是不进行操作。也就是说，我们可以通过设置，把free后的chunk的data区域赋值，但是不能赋值成\x00

然后是set_fastchunks，作用是对arena的flags标志位的最低bit清零

判断fastbin大小

之前我写个fastbin专题的博客，如果有基础的就知道，fastbin其实是一个长度为10的数组fastbinsY

index从0，1，2……开始长度是0x20，0x30，0x40……(放不满的问题之前博客中说过)

所以首先是根据size获取到index，具体的运算是(size >> 4) - 2，

然后根据index从fastbinY中取地址和取值：

fd = &fastbinsY[index];
old = *fd;

2free check

fastbin中也有一个简单的对2free的check，如果old == p，则报2free的error(double free or corruption(fasttop))

逻辑很简单，old是在fastbin中的值，表示已经被free过，如果再free就是2free了

要bypass也很简单：

free(a)
free(b)
free(a)

单链表插入

fastbin是一个单向链表，所以下面就是单链表插入操作，逻辑也挺简单的：

p->fd = old
fastbinsY[index] = p

PS: 实际代码这里很迷，是一个循环，但是我觉得是循环不起来的

fastbin entry check

最后是对fastbin entry进行检查，在单链表插入操作之前还有一个操作，如果old!=NULL，也就是说当前index的fastbin如果不是空链表，我们就要获取原本fastbinsY[index]的index，具体操作是old_index = (old->chunksize >> 4) - 2，最后再对两个index进行判断，如果index != old_index，则表示两个index不同的chunk竟然放在同一个链表中，肯定有问题啊，然后报错退出(invalid fastbin entry (free))

如果是free一个fastbin chunk的话，执行完上面的逻辑，free函数就可以return了，我们可以看到fastbin的free过程只做了一些简单的判断，然后只进行了单链表操作，对于inuse标志位却没有处理

PS: 这之中还有一些的多线程情况下lock的问题，暂不研究

非fastbin的情况

对smallbin, largenbin, unsortbin的操作都在这个分支中，基本流程如下：

1. 判断是否是使用mmap分配的内存空间
2. 获取下一个chunk的地址
3. 进行3个double free check
4. 获取下一个chunk的size，并对其进行check
5. 调用free_perturb函数，上面讲过
6. 前置合并操作，逻辑如下：
7. 上一个chunk处于空闲状态
8. 获取上一个chunk的size，并加到当前chunk的size中去
9. 获取上一个chunk的地址
10. unlink上一个chunk
11. 判断下一个chunk是否是top chunk，如果是见下面流程，不是，跳到8
12. 当前size加上下一个chunk的size
13. 把加好后的size赋值给当前chunk的size
14. arena执行top chunk的指针改指向当前chunk
15. 判断下一个chunk是否是空闲状态，如果是见下面流程，如果不是，跳到9
16. unlink下一个chunk
17. 当前size加上下一个chunk的size
18. 清除下一个chunk的inuse标志位
19. 获取unsortbin地址
20. 获取unsortbin->fd地址
21. 进行unsort chunk check
22. 当前chunk->fd = unsortbin->fd
23. 当前chunk->bk = unsortbin
24. 如果当前chunk不是smallbin，把fd_nextsize/bk_nextsize清零
25. unsortbin->fd->bk = 当前chunk
26. unsortbin->fd = 当前chunk
27. 设置当前chunk的size，inuse标志位为1，设置下一个chunk的pre_size
28. 如果size>65536则…….

double free check

共有三个check，首先是当前chunk不能是top chunk，也就是top chunk不能被free，第二个check是检查下一个chunk的地址不能大于top chunk的地址加上top chunk的size，因为在brk分配得到的一个堆中，top chunk是末尾的chunk，所以top chunk之后是不存在其他chunk的，第三个是检查下一个chunk的inuse标志位，只有当前chunk是inuse状态，才能被free。

之后是对下一个chunk的size进行check，也就是上下限检查。

前向合并操作

如果上一个chunk是处于空闲状态，当前chunk就要和上一个chunk进行合并。逻辑也很简单，因为上一次chunk是处于空闲状态，所以当前chunk的pre_size可以获取到上一个chunk的size，和当前chunk的size相加，形成新的size，当前chunk的地址减去pre_size，获得上一个chunk的地址，而上一个chunk的地址将赋值给当前chunk。然后对上一个chunk进行unlink操作，把上一个chunk从bin的链表中删除。

向后合并操作

向后合并操作有两种情况，一种是下一chunk是处于空闲状态的chunk，另一种是下一个chunk是top chunk。如果下一个chunk是top chunk，首先获取到下一个chunk的size加上当前chunk的size形成新的size，并储存到当前chunk的size位，然后把arena的top chunk指针设置成当前chunk的地址，这样就完成了把当前chunk合并进top chunk的操作。

可以通过下下个chunk的inuse标志位判断下一个chunk是否处于空闲状态，如果处于inuse状态，这把下一个chunk的inuse标志位置零，表示当前chunk处于空闲状态，如果下一个chunk处于空闲状态，则需要进行向后合并操作。首先是unlink下一个chunk，把下一个chunk从bin的链表中删去，然后当前size加上下一个chunk的size。

unlink

首先是获取下一个chunk的pre_size，和当前chunk的size进行比较，因为传入unlink的chunk都是处于空闲状态，所以下一个chunk的pre_size位是有效值。之后是进行一个比较经典的check：P->fd->bk == P && P->bk->fd == P，当该check通过后就是删除当前链表的操作了：

P->fd = FD
P->bk = BK

这些都算是链表中比较经典的操作了。

然后是，如果当前chunk是largebin，还会对fd_nextsize和bk_nextsize进行一些操作。这两个也是指针变量，但是在free函数中基本没有对这两个指针进行操作赋值，所以还不清楚具体含义，等看完malloc函数再进行研究。

把当前chunk加入到unsortbin中

1678	struct malloc_state
1679	{
1680	  /* Serialize access.  */
1681	  __libc_lock_define (, mutex);
1682	
1683	  /* Flags (formerly in max_fast).  */
1684	  int flags;
1685	
1686	  /* Fastbins */
1687	  mfastbinptr fastbinsY[NFASTBINS];
1688	
1689	  /* Base of the topmost chunk -- not otherwise kept in a bin */
1690	  mchunkptr top;
1691	
1692	  /* The remainder from the most recent split of a small request */
1693	  mchunkptr last_remainder;
1694	
1695	  /* Normal bins packed as described above */
1696	  mchunkptr bins[NBINS * 2 - 2];
1697	
1698	  /* Bitmap of bins */
1699	  unsigned int binmap[BINMAPSIZE];
1700	
1701	  /* Linked list */
1702	  struct malloc_state *next;
1703	
1704	  /* Linked list for free arenas.  Access to this field is serialized
1705	     by free_list_lock in arena.c.  */
1706	  struct malloc_state *next_free;
1707	
1708	  /* Number of threads attached to this arena.  0 if the arena is on
1709	     the free list.  Access to this field is serialized by
1710	     free_list_lock in arena.c.  */
1711	  INTERNAL_SIZE_T attached_threads;
1712	
1713	  /* Memory allocated from the system in this arena.  */
1714	  INTERNAL_SIZE_T system_mem;
1715	  INTERNAL_SIZE_T max_system_mem;
1716	};

这是arena的结构体，其中fastbinsY数组存放的是fastbin，而bins数组中存放的是unsortbin，smallbin和largebin，其中bins[0]和bins[1]存放的是unsortbin。

在free函数中，free一个chunk，是把他放入到unsortbin之中。源代码中是这样的两句：

4333	      bck = unsorted_chunks(av);
4334	      fwd = bck->fd;

链表插入的操作:

4340	      p->fd = fwd;
4341	      p->bk = bck;
......
4347	      bck->fd = p;
4348	      fwd->bk = p;

其中，bck的值为arena中top chunk的地址，fwd是bins[0]的值，arena的结构如下，

top chunk	last_remainder
bins[0]	bins[1]

上面这样的结构形成一个chunk和当前chunk形成一个双向循环链表

当largenbin的情况，会吧fd_nextsize和bk_nextsize置空(NULL)

最后就是设置当前chunk的inuse标志位和更新size，并设置下一个chunk的pre_size

所以chunk在进行free操作后，如果存在上一个chunk，肯定是处于inuse状态，如果不是上面就和当前chunk合并了，同理下一个也肯定是处于inuse状态的chunk

最后，当size>65536时还会有一波猜测，大致过了一遍，是处理arena的，所以暂不做研究.

总结

这次看free代码虽然花了挺长时间，但是其实代码挺简单的，主要是三天打鱼两天晒网的缘故。最难看懂的代码应该是内联汇编了，比如这句：

4255	    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);

看了半天这内联汇编实在是难看，也不好理解，最后我把自己电脑上的libc.so，丢到ida中，找到这句对应的汇编，就好理解多了

cmpxchg [rdx], rbx