載酒讀堆源碼-malloc、free函數(shù)
學藝不精，歡迎大佬們批評指正
malloc函數(shù)執(zhí)行流程
【過程簡化】
1、一些預處理：獲得arena和堆申請塊大小做對齊
2、超超大chunk（>128kb）→mmap
3、fastbin范圍內(nèi)的chunk→直接fastbin中拿出
4、嘗試從smallbin和largebin中獲得chunk
5、遍歷處理unsortedbin
6、擴大arena并從topchunk中切割
這兩個情況下：
1、在申請large chunk時，fastbin會進行合并，合并后按照大小進入largebin和smallbin（這是因為，首先這能很好的解決碎片化問題，其次程序很少會連續(xù)的既使用小堆塊，又使用大堆塊）
2、申請的chunk大小大于等于top_chunk的大小時，嘗試將fastbin進行整理后再在smallbin和largebin中找
會產(chǎn)生塊的合并操作（這里是通過調(diào)用
malloc_consolidate函數(shù)實現(xiàn)的）
【示意圖】
（以x32環(huán)境下的malloc函數(shù)為例）
這里為方便師傅們粘貼到筆記，圖片就不水印了，還請不要盜用
【相關代碼】
這里是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數(shù)組中對應大小的元素（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 中倒數(shù)第二個 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 轉(zhuǎn)化為對應的 mem 狀態(tài)
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中取塊時，執(zhí)行以下代碼：
use_top:
victim = av->top;
size = chunksize (victim); // 獲取當前的top chunk，并計算得到其對應的大小
//判斷top_chunk_size是否夠用來分配
//1、若足夠，執(zhí)行以下邏輯進行正常的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函數(shù)會先進入__libc_malloc函數(shù)，該函數(shù)會嘗試從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請求的轉(zhuǎn)換后得到的chunk的size
? size_t tc_idx = csize2tidx (tbytes);? // 根據(jù)大小 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); // 調(diào)用 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失敗，就會調(diào)用_int_malloc 函數(shù)，該函數(shù)會按照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函數(shù)執(zhí)行流程
【過程簡化】
1、傳參檢查
2、將超超大塊用munmmap釋放
3、將此堆塊的指針存儲到bin中：
（1）如果大小是fastchunk：放入fastbin （2）否則如果其大小大于fastbin的閾值，將做如下操作：
{1} 先嘗試合并該freechunk前后的空閑塊，然后分別在向前合并完、向后合并完時對其前后的被合并的塊進行unlink操作，然后把最后合并得到的塊放入unsortedbin中
在這個操作中，因為prev_inuse位的設置，所以fastbin不會被合并進去
{2} 然后再遍歷所有fastbin對每個fastbin做前后合并的嘗試，然后不管嘗試結(jié)果如何，統(tǒng)一把做過嘗試的塊放入unsortedbin
這里在合并前會先將該fastchunk的物理相鄰的下一個chunk的prev_inuse位設為1，以便進行fastchunk的合并
4、調(diào)整當前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，若不是，則執(zhí)行以下合并后一個塊的邏輯
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數(shù)組中unsortedbin指針元素地址
fwd = bck->fd;// 獲取unsortedbin的第一個塊
if (__glibc_unlikely (fwd->bk != bck))// 一個安全監(jiān)測：看unsortedbin的第一個塊的bk域是否指向bins數(shù)組中的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，則執(zhí)行將當前塊合并入topchunk的操作，分為以下4步操作
else {
? ? size += nextsize;? // 1、將下一個塊的大小加入當前塊的大小
? ? set_head(p, size | PREV_INUSE);? // 2、設置當前塊的頭部大小和標志
? ? av->top = p;? // 3、更新頂部塊指針
? ? check_chunk(av, p);? // 4、檢查塊的完整性
}
這里是做unlink的代碼，實現(xiàn)在
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{
//執(zhí)行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;
}
}
}
}
【總結(jié)】
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函數(shù)
【定義】
C標準庫中的，用于設置 malloc() 函數(shù)的參數(shù)
【傳參】
第一個是選項，第二個是要給這個選項設置為多少值
【示例】
mallopt(1,0)：修改global_max_fast的值為0，并且按照修改后的global_max_fast去把原先在fastbin中的堆拿出來放到unsortedbin中去
關于擴大top chunk大小
一般來說，增加arena時，如果是mainthread就用sbrk，如果是nomainthread就用mmap
1、brk&sbrk函數(shù)
【定義】
對于堆的操作，操作系統(tǒng)提供了 brk 函數(shù)，glibc 庫提供了 sbrk 函數(shù)，brk是系統(tǒng)調(diào)用 而sbrk不是 ?，sbrk調(diào)用了brk
內(nèi)核維護一個進程控制塊（PCB），該結(jié)構(gòu)體中維護兩個指針：start_brk和brk，他們分別表示堆塊的開始地址和結(jié)束地址
【函數(shù)使用】
sbrk函數(shù)
定義：傳參0時可以獲取當前brk指針的值，傳參num時可以將當前brk指針的值增加拓展num字節(jié)(傳參整數(shù)是增加，傳參負數(shù)是減少)
返回值：若成功，brk()會返回0，否則返回-1。
brk函數(shù)
定義：可以改變brk指針內(nèi)存儲的地址（即堆結(jié)束地址，又叫堆頂），傳參多少就把brk設置為多少
返回值：若成功，brk()會返回0，否則返回-1。
示例
同樣是將堆地址拓展4096字節(jié)，有以下兩種寫法
1、使用sbrk函數(shù)進行拓展
#include <unistd.h>
#include <stdio.h>
int main() {
? ? void* original_brk = (void*)sbrk(0);? // 獲取當前堆頂?shù)刂?/p>
? ? printf("Original break: %p\n", original_brk);
? ? if (sbrk(4096) != (void*)-1) {? // 擴展堆頂?shù)刂?096字節(jié)
? ? ? ? void* updated_brk = (void*)sbrk(0);? // 獲取更新后的堆頂?shù)刂?/p>
? ? ? ? printf("Updated break: %p\n", updated_brk);
? ? } else {
? ? ? ? printf("Failed to update break.\n");
? ? }
? ? return 0;
}
2、使用brk函數(shù)進行拓展
#include <unistd.h>
#include <stdio.h>
int main() {
? ? void* new_brk = (void*)sbrk(0);? // 獲取當前堆頂?shù)刂?/p>
? ? printf("Original break: %p\n", new_brk);
? ? if (brk(new_brk + 4096) == 0) {? // 將堆頂?shù)刂窋U展4096字節(jié)
? ? ? ? void* updated_brk = (void*)sbrk(0);? // 獲取更新后的堆頂?shù)刂?/p>
? ? ? ? printf("Updated break: %p\n", updated_brk);
? ? } else {
? ? ? ? printf("Failed to update break.\n");
? ? }
? ? return 0;
}
2、mmap&munmap函數(shù)
詳見：
mmap段相關筆記，有時間再補上吧
總結(jié)-關于堆塊的合并
【定義】
一共有兩個合并機制：
一個是free了一個unsorted bin大小的塊時：先嘗試合并該freechunk前后的空閑塊，然后分別在向前合并完、向后合并完時對其前后的被合并的塊進行unlink操作，然后把最后合并得到的塊放入unsortedbin中
一個是專門用來做fastbin碎片整理的malloc_consolidate函數(shù)，而關于該函數(shù)，又有如下三種使用情境：
free了一個unsorted bin大小的塊時，會在進行被free堆塊的前后合并后，再調(diào)用malloc_consolidate函數(shù)
malloc在申請一個大于topchunk的塊時，調(diào)用malloc_consolidate函數(shù)嘗試對fastbin進行合并
malloc在申請large chunk時，會在查找largechunk之前調(diào)用malloc_consolidate函數(shù)嘗試對fastbin進行合并
【相關代碼】
這里是用于對fastbin做合并整理碎片的malloc_consolidate函數(shù)的相關代碼
/*
------------------------- malloc_consolidate -------------------------
malloc_consolidate是free()碎片整理的一個專門版本，用于清理fastbins中持有的內(nèi)存塊。不能直接使用free本身來實現(xiàn)此功能，因為其中可能會將內(nèi)存塊放回fastbins中。所以，我們需要使用稍微不同的代碼來實現(xiàn)此功能。
另外 ，由于malloc_consolidate在第一次調(diào)用malloc時需要被調(diào)用，因此它也是觸發(fā)初始化代碼的完美位置。
*/
static void malloc_consolidate(mstate av){// av 是 mstate 類型的指針，用于維護內(nèi)存分配器的狀態(tài)信息。
mfastbinptr* fb; // 當前正在合并的fastbin?
mfastbinptr maxfb; // 最后一個fastbin（用于循環(huán)控制）?
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已經(jīng)初始化，則執(zhí)行清理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 {// 循環(huán)遍歷所有 fastbins
? ? ? // 從 fastbin 中取出一個內(nèi)存塊
? ? ? p = atomic_exchange_acq(fb, 0);
? ? ? if (p != 0) {
? ? ? ? do {
? ? ? ? ? // 檢查當前內(nèi)存塊是否在使用中
? ? ? ? ? check_inuse_chunk(av, p);
? ? ? ? ? nextp = p->fd;? // 獲取下一個 fastbin 內(nèi)存塊
? ? ? ? ? // 稍微簡化了合并內(nèi)存塊的代碼，類似于 free() 函數(shù)中的合并代碼
? ? ? ? ? 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 范圍內(nèi)，則將 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);? // 循環(huán)遍歷所有 fastbins
} else {//###這里是從那個大if來的，如果global_max_fast為0，就表示av還沒有被初始化，則直接走到這里為其進行初始化即可~
malloc_init_state(av);
check_malloc_state(av);
}
}
