载酒读堆源码-malloc、free函数
学艺不精，欢迎大佬们批评指正
malloc函数执行流程
【过程简化】
1、一些预处理：获得arena和堆申请块大小做对齐
2、超超大chunk（>128kb）→mmap
3、fastbin范围内的chunk→直接fastbin中拿出
4、尝试从smallbin和largebin中获得chunk
5、遍历处理unsortedbin
6、扩大arena并从topchunk中切割
这两个情况下：
1、在申请large chunk时，fastbin会进行合并，合并后按照大小进入largebin和smallbin（这是因为，首先这能很好的解决碎片化问题，其次程序很少会连续的既使用小堆块，又使用大堆块）
2、申请的chunk大小大于等于top_chunk的大小时，尝试将fastbin进行整理后再在smallbin和largebin中找
会产生块的合并操作（这里是通过调用
malloc_consolidate函数实现的）
【示意图】
（以x32环境下的malloc函数为例）
这里为方便师傅们粘贴到笔记，图片就不水印了，还请不要盗用
【相关代码】
这里是malloc在尝试回收利用smallbin和largebin时的相关代码
// malloc.c中第3405-3434行
//其中，nb为所申请的chunk的真实大小，av是一个指向main_arena的指针
// 若申请的chunk大小在smallbin中，则通过以下操作去尝试从smallbin中获取该chunk
if (in_smallbin_range (nb)){
idx = smallbin_index (nb);//获取smallbin的索引，记为idx
bin = bin_at (av, idx); //获取smallbin数组中对应大小的元素（p2chunk），记为bin
if ((victim = last (bin)) != bin){// 先获取 small bin 的最后一个chunk，记为victim。然后拿去检测：如果 victim == bin ，那说明该 bin 为空。如果不相等，那么会有两种情况
// 第一种情况，smallbin还没有初始化，则对其初始化之。
if (victim == 0)
malloc_consolidate(av);
// 第二种情况，smallbin中存在空闲的 chunk，则进行安全性检查之后，取出对应的chunk，并设置其相应的一些位
else{
// 1.安全性检查
bck = victim->bk; //获取 small bin 中倒数第二个 chunk，用于进行安全性检查
if (__glibc_unlikely (bck->fd != victim)){ // 检查 bck->fd 是不是 victim，防止伪造
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
// 2.设置相应的位并取出chunk
set_inuse_bit_at_offset (victim, nb); // 设置 victim 对应的 inuse 位
bin->bk = bck; //修改 smallbin 链表，将 small bin 的最后一个 chunk 取出来
bck->fd = bin;
// 3.再设置一些相应的位
if (av != &main_arena)// 如果不是 main_arena，设置对应的标志
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);// 细致的检查
void *p = chunk2mem (victim);// 将申请到的 chunk 转化为对应的 mem 状态
alloc_perturb (p, bytes);// 如果设置了 perturb_type , 则将获取到的chunk初始化为 perturb_type ^ 0xff
return p;
}
}
}
//若申请的大小不在smallbin中，就尝试从largebin中获取
else{
idx = largebin_index (nb); //获取largebin中的索引
if (have_fastchunks (av)) //判断是否有fastbin，若有的话，对他们进行整理
malloc_consolidate (av);
}
这里是在决定从topchunk中切割块时的相关代码
//malloc.c：第3777-3832行
//当决定从topchunk中取块时，执行以下代码：
use_top:
victim = av->top;
size = chunksize (victim); // 获取当前的top chunk，并计算得到其对应的大小
//判断top_chunk_size是否够用来分配
//1、若足够，执行以下逻辑进行正常的topchunk切割操作即可
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE)) {
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
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;
}
//2、若top_chunk_size不足够用来分配，但是存在fast_chunk，就尝试合并整理fast_chunk进入small&largebin，然后看整理完后的small&largebin里是否有符合要求的块
else if (have_fastchunks (av)){
malloc_consolidate (av); //先尝试对fastbin中的chunk进行合并
//合并后再尝试看看能否从合并后的smallbin和largebin中找到合适的块
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}
//3、若topchunksize不足够分配，然后又没有fastchunk可合并了，那就只能去扩展topchunk了
else{
void *p = sysmalloc (nb, av); //扩展top_chunk
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
【高版本下的tcache】
相关代码
malloc函数会先进入__libc_malloc函数，该函数会尝试从tcache bin中获取freechunk，代码如下：
__libc_malloc (size_t bytes){
.............
.............
.............
#if USE_TCACHE
/* int_free also calls request2size, be careful to not pad twice. */
size_t tbytes;
checked_request2size (bytes, tbytes); // tbytes为bytes请求的转换后得到的chunk的size
size_t tc_idx = csize2tidx (tbytes); // 根据大小 tbytes ，找到 tcache->entries 索引
MAYBE_INIT_TCACHE ();
DIAG_PUSH_NEEDS_COMMENT;
if (tc_idx < mp_.tcache_bins
/*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
&& tcache
&& tcache->entries[tc_idx] != NULL) // 如果tcache->entries[tc_idx]有chunk就返回
{
return tcache_get (tc_idx); // 调用 tcache_get 拿到 chunk 然后返回
}
DIAG_POP_NEEDS_COMMENT;
#endif
if (SINGLE_THREAD_P)
{
victim = _int_malloc (&main_arena, bytes);
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
&main_arena == arena_for_chunk (mem2chunk (victim)));
return victim;
}
arena_get (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
如果尝试从tcache bin中获取freechunk失败，就会调用_int_malloc 函数，该函数会按照fastbin→small bin&large bin→sorted bin的顺序去尝试获取chunk，代码如下：
// 从 fastbin里面移除 pp
#define REMOVE_FB(fb, victim, pp)
do{
victim = pp;
if (victim == NULL)
break;
}while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))!= victim);
free函数执行流程
【过程简化】
1、传参检查
2、将超超大块用munmmap释放
3、将此堆块的指针存储到bin中：
（1）如果大小是fastchunk：放入fastbin （2）否则如果其大小大于fastbin的阈值，将做如下操作：
{1} 先尝试合并该freechunk前后的空闲块，然后分别在向前合并完、向后合并完时对其前后的被合并的块进行unlink操作，然后把最后合并得到的块放入unsortedbin中
在这个操作中，因为prev_inuse位的设置，所以fastbin不会被合并进去
{2} 然后再遍历所有fastbin对每个fastbin做前后合并的尝试，然后不管尝试结果如何，统一把做过尝试的块放入unsortedbin
这里在合并前会先将该fastchunk的物理相邻的下一个chunk的prev_inuse位设为1，以便进行fastchunk的合并
4、调整当前arena大小
【示意图】
【相关代码】
free一个大于fastchunk的块时，进行前后合并且做unlink的部分代码
这里是进行前后合并的代码
//第一步：尝试向前合并
if (!prev_inuse(p)) {// 如果物理相邻的前一个块未被使用，则将其与当前块合并，分为以下三步操作
prevsize = prev_size(p);
size += prevsize; // 1、进行一个size的合并变化
p = chunk_at_offset(p, -((long) prevsize)); // 2、进行一个p2chunk的合并变化——将p2当前块指向合并完后的新块的块头
unlink(av, p, bck, fwd); // 3、进行一个unlink
}
//第二步：查看后一个块是否为topchunk，若不是，则执行以下合并后一个块的逻辑
if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize); // 通过下下个块的prev_inuse获取到下个块是否为空闲
if (!nextinuse) { // 如果下个块是空闲的，就对其进行合并操作，分为以下两步操作
unlink(av, nextchunk, bck, fwd); // 1、进行一个unlink
size += nextsize; // 2、进行一个size的合并变化
} else
clear_inuse_bit_at_offset(nextchunk, 0);// 如果下个块不空闲，我们就做正常的一个free后对下一个块的prev_inuse为的更新操作即可
//接下来就是把当前合并了两次的块放入到unsortedbin即可
bck = unsorted_chunks(av);// 获取bins数组中unsortedbin指针元素地址
fwd = bck->fd;// 获取unsortedbin的第一个块
if (__glibc_unlikely (fwd->bk != bck))// 一个安全监测：看unsortedbin的第一个块的bk域是否指向bins数组中的unsortedbin指针元素
malloc_printerr ("free(): corrupted unsorted chunks");
//双向链表的插入操作，将当前chunk插入进unsorted表头位置
p->fd = fwd;
p->bk = bck;
if (!in_smallbin_range(size)){
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
bck->fd = p;
fwd->bk = p;
set_head(p, size | PREV_INUSE);//设置当前块的size字段，包括prev_inuse位
set_foot(p, size);//设置当前块的foot字段
check_free_chunk(av, p);
}
//第三步：若后一个块是topchunk，则执行将当前块合并入topchunk的操作，分为以下4步操作
else {
size += nextsize; // 1、将下一个块的大小加入当前块的大小
set_head(p, size | PREV_INUSE); // 2、设置当前块的头部大小和标志
av->top = p; // 3、更新顶部块指针
check_chunk(av, p); // 4、检查块的完整性
}
这里是做unlink的代码，实现在
unlink(av, p, bck, fwd)宏定义中：
#define unlink(AV, P, BK, FD) {
// 安全性检测1：当前chunk的size是否等于物理相邻的下个chunk的prevsize
if (chunksize (p) != prev_size (next_chunk (p)))
malloc_printerr ("corrupted size vs. prev_size");
//获取当前chunk的fd和bk
mchunkptr fd = p->fd;
mchunkptr bk = p->bk;
//安全性检测2：查看当前chunk的fd->bk和bk->fd是否等于它自身
if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
malloc_printerr ("corrupted double-linked list");
else{
//执行unlink操作
fd->bk = bk;
bk->fd = fd;
//后面就是一些对于fd_nextsize和fd_nextsize的操作了，如果是当前块不属于
if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL){
if (p->fd_nextsize->bk_nextsize != p || p->bk_nextsize->fd_nextsize != p)// 安全性检测：检查是否fd_nextsize->bk_nextsize==bk_nextsize->fd_nextsize==p
malloc_printerr ("corrupted double-linked list (not small)");
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{// 否则，也就表示当前块属于smallbin，且其相同大小的链表只有这一个
p->fd_nextsize->bk_nextsize = p->bk_nextsize;
p->bk_nextsize->fd_nextsize = p->fd_nextsize;
}
}
}
}
【总结】
glibc2.23下，当free一个unsortedbin大小的chunk时（假设是使用指针p指向该chunk作为传参），会进行以下操作：
1、尝试合并前一个chunk，若可行（这里注意，fastchunk将不会被合并），对前一个chunk做unlink操作；
2、尝试合并后一个chunk，若可行（这里注意，fastchunk将不会被合并），对后一个chunk做unlink操作，若后一个chunk为topchunk，则当前chunk并入topchunk；
其中，unlink操作为：先检查
chunksize (p) == prev_size (next_chunk (p))是否成立（>2.27版本下），再检查FD->bk==P || BK->fd== P是否成立，若成立，进行双向链表的unlink操作
mallopt函数
【定义】
C标准库中的，用于设置 malloc() 函数的参数
【传参】
第一个是选项，第二个是要给这个选项设置为多少值
【示例】
mallopt(1,0)：修改global_max_fast的值为0，并且按照修改后的global_max_fast去把原先在fastbin中的堆拿出来放到unsortedbin中去
关于扩大top chunk大小
一般来说，增加arena时，如果是mainthread就用sbrk，如果是nomainthread就用mmap
1、brk&sbrk函数
【定义】
对于堆的操作，操作系统提供了 brk 函数，glibc 库提供了 sbrk 函数，brk是系统调用 而sbrk不是 ，sbrk调用了brk
内核维护一个进程控制块（PCB），该结构体中维护两个指针：start_brk和brk，他们分别表示堆块的开始地址和结束地址
【函数使用】
sbrk函数
定义：传参0时可以获取当前brk指针的值，传参num时可以将当前brk指针的值增加拓展num字节(传参整数是增加，传参负数是减少)
返回值：若成功，brk()会返回0，否则返回-1。
brk函数
定义：可以改变brk指针内存储的地址（即堆结束地址，又叫堆顶），传参多少就把brk设置为多少
返回值：若成功，brk()会返回0，否则返回-1。
示例
同样是将堆地址拓展4096字节，有以下两种写法
1、使用sbrk函数进行拓展
#include <unistd.h>
#include <stdio.h>
int main() {
void* original_brk = (void*)sbrk(0); // 获取当前堆顶地址
printf("Original break: %p\n", original_brk);
if (sbrk(4096) != (void*)-1) { // 扩展堆顶地址4096字节
void* updated_brk = (void*)sbrk(0); // 获取更新后的堆顶地址
printf("Updated break: %p\n", updated_brk);
} else {
printf("Failed to update break.\n");
}
return 0;
}
2、使用brk函数进行拓展
#include <unistd.h>
#include <stdio.h>
int main() {
void* new_brk = (void*)sbrk(0); // 获取当前堆顶地址
printf("Original break: %p\n", new_brk);
if (brk(new_brk + 4096) == 0) { // 将堆顶地址扩展4096字节
void* updated_brk = (void*)sbrk(0); // 获取更新后的堆顶地址
printf("Updated break: %p\n", updated_brk);
} else {
printf("Failed to update break.\n");
}
return 0;
}
2、mmap&munmap函数
详见：
mmap段相关笔记，有时间再补上吧
总结-关于堆块的合并
【定义】
一共有两个合并机制：
一个是free了一个unsorted bin大小的块时：先尝试合并该freechunk前后的空闲块，然后分别在向前合并完、向后合并完时对其前后的被合并的块进行unlink操作，然后把最后合并得到的块放入unsortedbin中
一个是专门用来做fastbin碎片整理的malloc_consolidate函数，而关于该函数，又有如下三种使用情境：
free了一个unsorted bin大小的块时，会在进行被free堆块的前后合并后，再调用malloc_consolidate函数
malloc在申请一个大于topchunk的块时，调用malloc_consolidate函数尝试对fastbin进行合并
malloc在申请large chunk时，会在查找largechunk之前调用malloc_consolidate函数尝试对fastbin进行合并
【相关代码】
这里是用于对fastbin做合并整理碎片的malloc_consolidate函数的相关代码
/*
------------------------- malloc_consolidate -------------------------
malloc_consolidate是free()碎片整理的一个专门版本，用于清理fastbins中持有的内存块。不能直接使用free本身来实现此功能，因为其中可能会将内存块放回fastbins中。所以，我们需要使用稍微不同的代码来实现此功能。
另外 ，由于malloc_consolidate在第一次调用malloc时需要被调用，因此它也是触发初始化代码的完美位置。
*/
static void malloc_consolidate(mstate av){// av 是 mstate 类型的指针，用于维护内存分配器的状态信息。
mfastbinptr* fb; // 当前正在合并的fastbin
mfastbinptr maxfb; // 最后一个fastbin（用于循环控制）
mchunkptr p; // 当前正在合并的块
mchunkptr nextp; // 下一个要合并的块
mchunkptr unsorted_bin; // 未排序的bin头
mchunkptr first_unsorted; // 要链接的块
// 这些与free()中的使用方式相同
mchunkptr nextchunk;
INTERNAL_SIZE_T size;
INTERNAL_SIZE_T nextsize;
INTERNAL_SIZE_T prevsize;
int nextinuse;
mchunkptr bck;
mchunkptr fwd;
//###这里是一个大的if，如果global_max_fast不为0，就表示av已经初始化，则执行清理fastchunk的逻辑
if (get_max_fast() != 0) {
if (get_max_fast() != 0) {
// 清空 fastbins
clear_fastchunks(av);
// 获取未排序的 bin 头
unsorted_bin = unsorted_chunks(av);
// 从fast bin中移除每个块并进行合并，然后放入unsorted bin中，之所以不是放入smallbin或largebin也是基于unsortedbin的一个类似于延迟绑定的思想
maxfb = &fastbin(av, NFASTBINS - 1); // 指向最后一个 fastbin 的指针
fb = &fastbin(av, 0); // 指向第一个 fastbin 的指针
do {// 循环遍历所有 fastbins
// 从 fastbin 中取出一个内存块
p = atomic_exchange_acq(fb, 0);
if (p != 0) {
do {
// 检查当前内存块是否在使用中
check_inuse_chunk(av, p);
nextp = p->fd; // 获取下一个 fastbin 内存块
// 稍微简化了合并内存块的代码，类似于 free() 函数中的合并代码
size = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);
// 如果前一个块是空闲块，则合并前一个块和当前块
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long)prevsize));
unlink(av, p, bck, fwd);
}
// 如果下一个块不是堆顶块，则尝试合并下一个块和当前块
if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
if (!nextinuse) {
size += nextsize;
unlink(av, nextchunk, bck, fwd);
} else
clear_inuse_bit_at_offset(nextchunk, 0);
// 将当前块插入未排序的 bin 中
first_unsorted = unsorted_bin->fd;
unsorted_bin->fd = p;
first_unsorted->bk = p;
// 如果块大小不在 smallbin 范围内，则将 fd_nextsize 和 bk_nextsize 置为 NULL
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); // 循环遍历所有 fastbins
} else {//###这里是从那个大if来的，如果global_max_fast为0，就表示av还没有被初始化，则直接走到这里为其进行初始化即可~
malloc_init_state(av);
check_malloc_state(av);
}
}
