1 概述
在 glibc-2.3.x. 之後，glibc 中內建了ptmalloc2。
可以下載下傳glibc源碼檢視ptmalloc
http://ftp.gnu.org/gnu/glibc/
檢視glibc版本
| [email protected]:~/tmp$ ldd --version ldd (Ubuntu GLIBC 2.23-0ubuntu9) 2.23 |
這裡主要參考：
https://ctf-wiki.github.io/ctf-wiki/pwn/heap
本文參考的glibc源碼是glibc-2.25.tar.xz
了解ptmalloc堆最後的辦法是檢視相關資料後看源碼。word文檔拷貝的時候顔色丢失了，格式也有丢失。先這樣。
2 API
2.1 其它
2.1.1 catomic_compare_and_exchange_val_acq
如果*MEM等于OLDVAL，則将*MEM存儲為NEWVAL，傳回OLDVAL；
#ifndef catomic_compare_and_exchange_val_acq
# ifdef __arch_c_compare_and_exchange_val_32_acq
# define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
__atomic_val_bysize (__arch_c_compare_and_exchange_val,acq, \
mem, newval, oldval)
# else
# define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
atomic_compare_and_exchange_val_acq (mem, newval, oldval)
# endif
#endif
2.1.2 catomic_compare_and_exchange_val_rel
如果*MEM等于OLDVAL，則将*MEM存儲為NEWVAL，傳回OLDVAL；
#ifndef catomic_compare_and_exchange_val_rel
# ifndef atomic_compare_and_exchange_val_rel
# define catomic_compare_and_exchange_val_rel(mem, newval, oldval) \
catomic_compare_and_exchange_val_acq (mem, newval, oldval)
# else
# define catomic_compare_and_exchange_val_rel(mem, newval, oldval) \
atomic_compare_and_exchange_val_rel (mem, newval, oldval)
# endif
#endif
2.1.3 Perturb_byte
l perturb_byte：一個位元組，用于初始化配置設定的記憶體，出于調試的目的。
l __libc_mallopt(int param_number, int value)：設定perturb_byte
l alloc_perturb (char *p, size_t n)：記憶體初始化為perturb_byte^0xff
l free_perturb (char *p, size_t n)：記憶體初始化為perturb_byte
l do_set_perturb_byte (int32_t value)：設定perturb_byte
static int perturb_byte;
static void
alloc_perturb (char *p, size_t n)
{
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte ^ 0xff, n);
}
static void
free_perturb (char *p, size_t n)
{
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte, n);
}
static inline int
__always_inline
do_set_perturb_byte (int32_t value)
{
LIBC_PROBE (memory_mallopt_perturb, 2, value, perturb_byte);
perturb_byte = value;
return 1;
}
int
__libc_mallopt (int param_number, int value){
//......
switch (param_number)
{
case M_PERTURB:
do_set_perturb_byte (value);
break;
}
//......
}
2.2 malloc_init_state
l 初始化arena header(malloc_state)結構：
初始化bins數組，構造bin雙連結清單；
設定NONCONTIGUOUS_BIT标記；
設定fastbin使用者資料的最大值：global_max_fast；
設定FASTCHUNKS_BIT标記；
初始化top chunk；
static void
malloc_init_state (mstate av)
{
int i;
mbinptr bin;
for (i = 1; i < NBINS; ++i)
{
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);
av->flags |= FASTCHUNKS_BIT;
av->top = initial_top (av);
}
2.3 Unlink
unlink 用來将一個雙向 bin 連結清單中的一個 chunk 取出來
參數：
AV：arena header(malloc_state)
P ：将要unlink的chunk
BK：P後面的chunk <--
FD：P前面的chunk -->
3個chunk的順序
-------->位址增加
BK P FD
具體過程如下：
将chunk從FD/BK連結清單中摘除；
如果是large chunk，則将chunk從fd_nextsize/bk_nextsize連結清單中摘除
| #define unlink(AV, P, BK, FD) { \ FD = P->fd; \ BK = P->bk; \ // 檢查3個chunk的BK/FD連結是否一緻 if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \ malloc_printerr (check_action, "corrupted double-linked list", P, AV); \ else { \ // unlink P FD->bk = BK; \ BK->fd = FD; \ // 如果P的大小不屬于small bin if (!in_smallbin_range (chunksize_nomask (P)) \ // P的fd_nextsize字段非空，即位于large bin中 // 這裡期望fd_nextsize字段為NULL，即大機率為unsorted bin，小機率為large bin && __builtin_expect (P->fd_nextsize != NULL, 0)) { \ // 檢查3個chunk的fd_nextsize/bk_nextsize連結是否一緻 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); \ // 此時P在fd_nextsize連結清單中 // 如果FD不在fd_nextsize連結清單中，則将FD加傳入連結表中 if (FD->fd_nextsize == NULL) { \ // 如果P連結到自身，則令FD也連結到自身 if (P->fd_nextsize == P) \ FD->fd_nextsize = FD->bk_nextsize = FD; \ else { \ // 否則我們需要将 FD 插入到 nextsize 形成的雙連結清單中 // 更新FD的fd_nextsize/bk_nextsize // 更新P->fd_nextsize/P->bk_nextsize 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都在fd_nextsize連結清單中，将P從fd_nextsize連結清單中摘除 P->fd_nextsize->bk_nextsize = P->bk_nextsize; \ P->bk_nextsize->fd_nextsize = P->fd_nextsize; \ } \ } \ } \ } |
1. __builtin_expect
l 函數__builtin_expect()是GCC v2.96版本引入的, 其聲明如下:
long __builtin_expect(long exp, long c);
參數
exp 為一個整型表達式, 例如: (ptr != NULL)
c 必須是一個編譯期常量, 不能使用變量
傳回值
等于 第一個參數 exp
功能
GCC 提供了這個内建函數來幫助程式員處理分支預測.
允許程式員将最有可能執行的分支告訴編譯，即exp的值很可能是c；
GCC在編譯過程中，會将可能性更大的代碼緊跟着前面的代碼，進而減少指令跳轉帶來的性能上的下降, 達到優化程式的目的。（此時CPU流水線預取指令會起作用）
2.4 Malloc
見注釋，最終調用的是_int_malloc
| strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, 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)); //接着會尋找一個 arena 來試圖配置設定記憶體 arena_get (ar_ptr, bytes); //調用 _int_malloc 函數去申請對應的記憶體 victim = _int_malloc (ar_ptr, bytes); //嘗試再去尋找一個可用的 arena，并配置設定記憶體 if (!victim && ar_ptr != NULL) { LIBC_PROBE (memory_malloc_retry, 1, bytes); ar_ptr = arena_get_retry (ar_ptr, bytes); victim = _int_malloc (ar_ptr, bytes); } //unlock if (ar_ptr != NULL) __libc_lock_unlock (ar_ptr->mutex); //判斷目前的狀态是否滿足以下條件 //要麼沒有申請到記憶體 //要麼是 mmap 的記憶體 //要麼申請到的記憶體必須在其所配置設定的arena中 assert (!victim || chunk_is_mmapped (mem2chunk (victim)) || ar_ptr == arena_for_chunk (mem2chunk (victim))); return victim; } libc_hidden_def (__libc_malloc) |
2.5 _int_malloc
static void *
_int_malloc (mstate av, size_t bytes)
_int_malloc 是記憶體配置設定的核心函數，其核心思路有如下
1. Fast bin服務請求
2. Small bin服務請求
3. 如果是large chunk，則合并fast bin
4. 循環處理
1) Unsorted bin服務請求
（周遊的unsorted chunk要麼比對使用者請求被傳回，要麼放入對應的bin中）
2) Large bin服務請求
3) next largest bin服務請求
4) top chunk服務請求
5) 合并fast bin，下次嘗試
6) 從系統請求記憶體
具體過程如下：
1. 沒有可用的arena，則使用sysmalloc從mmap擷取chunk;
2. chunk大小屬于fast bin，嘗試從fast bin（單連結清單）連結清單頭部擷取;
3. chunk大小屬于small bin，嘗試從small bin(環形雙連結清單）連結清單尾部擷取;
4. chunk大小屬于large bin，先合并 fast bin以解決分片問題；
5. 循環處理
l 這裡使用外循環，是因為我們可能在進行中合并了一個滿足要求的chunk，需要重新嘗試。最多重新嘗試一次，否則我們将擴充記憶體來服務請求。
l unsorted bin服務請求
Ø last remainder chunk服務請求
（使用者請求為 small chunk；
last remainder chunk是 unsorted bin 中的唯一的chunk；
Last remainder大小大于使用者請求的大小；）
Ø 嚴格比對(exact fit)服務請求
Ø 如果是small chunk，則插入到small bin連結清單的開頭
Ø 如果為large chunk，則按大小降序放入large bin（大小相同時總是插入第二個位置）；同時構造fd_nextsize/bk_nextsize連結清單；
l Large bin服務large chunk請求
如果找到則切分後将剩餘的部分放入unsorted bin
l next largest bin服務請求
在下一個非空bin（bin數組中下一個索引）中擷取chunk，切分後返還給使用者
l top chunk服務請求
l 合并fast bin，下次嘗試
l 從系統請求記憶體
2.5.1 convert
将使用者申請的記憶體大小轉換為内部的chunk大小
checked_request2size (bytes, nb);
2.5.2 arena
如果沒有可用的arena，則使用sysmalloc從mmap擷取chunk
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
2.5.3 Fastbin
l 如果申請的 chunk 的大小位于 fast bin 範圍内，則從對應的fast bin連結清單的頭部中擷取并傳回free chunk；(fast bin是單連結清單）
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
// 擷取fast bin連結清單中的第一個元素，同時更新fastbinsY中的fast bin頭指針
// 如果fast bin連結清單是空的，則退出循環
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
!= victim);
if (victim != 0)
{
// 檢查取到的 chunk 大小是否與相應的 fastbin 索引一緻。
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);
void *p = chunk2mem (victim);
// 如果設定了perturb_type, 則将擷取到的chunk初始化為 perturb_type ^ 0xff
alloc_perturb (p, bytes);
return p;
}
}
2.5.4 Small bin
l 如果申請的 chunk 的大小位于 small bin 範圍内（small bin是環形循環雙連結清單），則從連結清單中取出small bin的最後一個chunk傳回給使用者；
if (in_smallbin_range (nb))
{
idx = smallbin_index (nb);
bin = bin_at (av, idx);
// 先執行 victim = last(bin)，擷取 small bin 的最後一個 chunk
// 如果 victim = bin ，那說明該 bin 為空。
// 如果不相等，那麼會有兩種情況
if ((victim = last (bin)) != bin)
{
// 第一種情況，small bin 還沒有初始化。
if (victim == 0)
malloc_consolidate (av);
// 第二種情況，small bin 中存在空閑的 chunk
else
{
// 擷取 small bin 中倒數第二個 chunk
bck = victim->bk;
// 擷取 small bin 中倒數第二個 chunk
if (__glibc_unlikely (bck->fd != victim))
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
set_inuse_bit_at_offset (victim, nb);
// 修改 small bin 連結清單，将 small bin 的最後一個 chunk 取出來
bin->bk = bck;
bck->fd = bin;
if (av != &main_arena)
set_non_main_arena (victim);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
}
2.5.5 malloc_consolidate
如果是large chunk，繼續之前，先合并 fastbins。這可以解決一般由fastbins帶來的分片問題。實際上，程式要麼請求small chunk，要麼請求large chunk，很少會混合請求。是以合并在大多數程式中不會被調用。
else
{
idx = largebin_index (nb);
if (have_fastchunks (av))
malloc_consolidate (av);
}
2.5.6 大循環
l unsorted bin服務請求
Ø last remainder chunk服務請求
（使用者請求為 small chunk；
last remainder chunk是 unsorted bin 中的唯一的chunk；
Last remainder大小大于使用者請求的大小；）
Ø 嚴格比對(exact fit)服務請求
Ø 如果是small chunk，則插入到small bin連結清單的開頭
Ø 如果為large chunk，則按大小降序放入large bin（大小相同時總是插入第二個位置）；同時構造fd_nextsize/bk_nextsize連結清單；
l Large bin服務large chunk請求
如果找到則切分後将剩餘的部分放入unsorted bin
l next largest bin服務請求
在下一個非空bin（bin數組中下一個索引）中擷取chunk，切分後返還給使用者
l top chunk服務請求
l fast bin服務請求
l 從系統請求記憶體
1. 這裡使用外循環，是因為我們可能在進行中合并了一個滿足要求的chunk，需要重新嘗試。最多重新嘗試一次，否則我們将擴充記憶體來服務請求。
for (;; )
{
int iters = 0;
//......
}
2.5.7 大循環-unsorted bin周遊
使用bk周遊unsorted bin
2.5.7.1 擷取一個unsorted chunk
// 如果 unsorted bin 不為空
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
// victim 為 unsorted bin 的最後一個 chunk
// bck 為 unsorted bin 的倒數第二個 chunk
bck = victim->bk;
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);
2.5.7.2 last remainder chunk中擷取
如果滿足以下條件，則使用last remainder chunk服務請求。這會有助于使得連續的small chunk的請求得到的位置相鄰。
1) 使用者請求為 small chunk
2) last remainder chunk是 unsorted bin 中的唯一的chunk
3) Last remainder大小大于使用者請求的大小
//滿足3個條件
if (in_smallbin_range (nb) &&
bck == unsorted_chunks (av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
//從last remainder chunk中取出使用者請求的chunk，更新unsorted bin連結清單和标志
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
av->last_remainder = remainder;
remainder->bk = remainder->fd = unsorted_chunks (av);
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;
}
2.5.7.3 将Unsorted chunk從連結清單中移除
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
移除後要麼被使用，要麼傳回給使用者（exact fit），要麼放入相關的bin中；
2.5.7.4 精确比對
如果取出的unsorted chunk精确比對，則設定标志後，傳回給使用者；
if (size == nb)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
2.5.7.5 unsorted chunk放入small bin
如果是small chunk，則插入到small bin連結清單的開頭
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
else ......
// 放到對應的 bin 中，插入victim，構成 bck<-->victim<-->fwd
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
2.5.7.6 unsorted chunk放入large bin
如果為large chunk，則按大小降序放入large bin（大小相同時總是插入第二個位置）；同時構造fd_nextsize/bk_nextsize連結清單；
else
{
// large bin範圍，bck為頭結點，fwd為第一個結點
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
// bin為非空連結清單
if (fwd != bck)
{
// 加速比較，連結清單裡的chunk都會設定該位
size |= PREV_INUSE;
//為什麼最後一個chunk屬于main arena呢？
assert (chunk_main_arena (bck->bk));
//周遊的chunk比目前最小的還要小
if ((unsigned long) (size) < (unsigned long) chunksize_nomask (bck->bk))
{
//bck為最後一個結點，fw為頭結點
fwd = bck;
bck = bck->bk;
//victim插入fd_nextsize/bk_nextsize連結清單
victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
else
{//周遊的chunk比目前最小的要大于等于
//為什麼第一個chunk屬于main arena呢？
assert (chunk_main_arena (fwd));
// 從連結清單頭部開始找到大小小于等于 victim 的 chunk
while ((unsigned long) size < chunksize_nomask (fwd))
{
fwd = fwd->fd_nextsize;
//為什麼每個chunk都屬于main arena呢？
assert (chunk_main_arena (fwd));
}
// 如果大小一樣，插入第二個位置，nextsize指針沒有改變，不需要修改
if ((unsigned long) size == (unsigned long) chunksize_nomask (fwd))
fwd = fwd->fd;
else
{// 如果大小不一樣，則插入fd_nextsize/bk_nextsize雙連結清單
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
}
else//空連結清單
victim->fd_nextsize = victim->bk_nextsize = victim;
}
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
2.5.8 大循環-large bin服務large chunk請求
如果請求的是large chunk，就在large bin 中從小到大進行掃描，找到第一個合适的。如果找到則切分後将剩餘的部分放入unsorted bin；
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);
// 如果對應的 bin 為空或者其中最大的chunk也小于使用者的請求，那就跳過
if ((victim = first (bin)) != bin && (unsigned long) chunksize_nomask (victim) >= (unsigned long) (nb))
{
victim = victim->bk_nextsize;
// 反向周遊連結清單，直到找到第一個不小于使用者請求大小的chunk
while (((unsigned long) (size = chunksize (victim)) < (unsigned long) (nb)))
victim = victim->bk_nextsize;
// 如果最終取到的chunk不是該bin中的最後一個chunk，并且該chunk與其前面的chunk（fd）
// 的大小相同，那麼我們就取其前面的chunk，這樣可以避免調整bk_nextsize,fd_nextsize
// 連結清單。因為大小相同的chunk隻有一個會被串在nextsize鍊上
if (victim != last (bin) && chunksize_nomask (victim) == chunksize_nomask (victim->fd))
victim = victim->fd;
remainder_size = size - nb;
unlink (av, victim, bck, fwd);
// 剩下的大小不足以當做一個塊，設定标志，不切分
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
}
else // 剩下的大小還可以作為一個chunk，進行分割，剩餘部分放入unsorted bin
{
remainder = chunk_at_offset (victim, nb);
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = 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;
}
}
2.5.9 大循環-尋找next largest bin
如果走到了這裡，那說明對于使用者所需的chunk，不能直接從其對應的bin中擷取chunk，此時我們在下一個非空bin（bin數組中下一個索引）中擷取chunk，切分後返還給使用者。
【準備工作】
// 從下一個更大的bin開始掃描最小比對的chunk。
// 利用bitmap可以避免掃描空的bin。
// 擷取下一個更大的bin
++idx;
bin = bin_at (av, idx);
//擷取對應的bitmap标記
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);
for (;; )
{
//......
}
【找到合适的map--跳過位沒有設定的block】
//bit > map: bit中隻有一個1，這說明map中這個1對應的高位均為0，
//為0表示對應的bin為空，則此block可以跳過
//bit <= map && bit == 0: bit = idx2bit (idx);
//bit初始化時不可能為0（有一個位置1），但是後面有左移位操作，如果剛好移到了最高位，則會為0
//bit為0時會進入下一個block，bit重新初始化為1
if (bit > map || bit == 0)
{
do
{
//跳過block
if (++block >= BINMAPSIZE)
goto use_top;
}
while ((map = av->binmap[block]) == 0);//map為0表示此block所有的位均為0，跳過
bin = bin_at (av, (block << BINMAPSHIFT));
bit = 1;
}
【找到合适的bin】
//找到一個非空的bin
while ((bit & map) == 0)
{
bin = next_bin (bin);
bit <<= 1;
assert (bit != 0);
}
【檢查bin是否為空】
為空時清空binMap中對應的标志位
victim = last (bin);
if (victim == bin)
{
av->binmap[block] = map &= ~bit;
bin = next_bin (bin);
bit <<= 1;
}
【unlink-切分-擷取chunk】
這部分的代碼和一般的切分代碼流程差不多，在“大循環-large bin服務large chunk請求”中也可以看到；
else
{
size = chunksize (victim);
assert ((unsigned long) (size) >= (unsigned long) (nb));
remainder_size = size - nb;
unlink (av, victim, bck, fwd);
// 剩下的大小不足以當做一個塊，設定标志，不切分
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
}
else // 剩下的大小還可以作為一個chunk，進行分割，剩餘部分放入unsorted bin
{
remainder = chunk_at_offset (victim, nb);
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;
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;
}
2.5.10 大循環-使用top chunk
如果所有的 bin 中的 chunk 都沒有辦法直接滿足要求（即不合并），或者說都沒有空閑的 chunk。那麼我們就隻能使用 top chunk 了。
l Top chunk服務請求
l 合并fast bin，下次嘗試
l 從系統請求記憶體
use_top:
victim = av->top;
size = chunksize (victim);
// 如果分割之後，top chunk 大小仍然滿足 chunk 的最小大小，那麼就可以直接進行分割
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;
}
// 否則，判斷是否有 fast chunk
else if (have_fastchunks (av))
{
// 先執行一次fast bin的合并
malloc_consolidate (av);
// 判斷需要的chunk是在small bin範圍内還是large bin範圍内
// 并計算對應的索引
// 等待下次再看看是否可以
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}
// 否則的話，我們就隻能從系統中再次申請一點記憶體了
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
2.6 Free
見注釋，最終調用的是_int_free
// 除非使用mallopt關閉，釋放非常大的空間會自動觸發将不使用的記憶體歸還給系統
void __libc_free(void*);
libc_hidden_proto (__libc_free)
strong_alias (__libc_free, __cfree) weak_alias (__libc_free, cfree)
strong_alias (__libc_free, __free) strong_alias (__libc_free, free)
void
__libc_free (void *mem)
{
mstate ar_ptr;
mchunkptr p;
void (*hook) (void *, const void *) = atomic_forced_read (__free_hook);
// 判斷是否有鈎子函數 __free_hook
if (__builtin_expect (hook != NULL, 0))
{
(*hook)(mem, RETURN_ADDRESS (0));
return;
}
if (mem == 0)
return;
p = mem2chunk (mem);
// 如果該塊記憶體是mmap得到的
if (chunk_is_mmapped (p))
{
if (!mp_.no_dyn_threshold
&& chunksize_nomask (p) > mp_.mmap_threshold
&& chunksize_nomask (p) <= DEFAULT_MMAP_THRESHOLD_MAX
&& !DUMPED_MAIN_ARENA_CHUNK (p))
{
mp_.mmap_threshold = chunksize (p);
mp_.trim_threshold = 2 * mp_.mmap_threshold;
LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
mp_.mmap_threshold, mp_.trim_threshold);
}
munmap_chunk (p);
return;
}
ar_ptr = arena_for_chunk (p);
_int_free (ar_ptr, p, 0);
}
2.7 _int_free
static void
_int_free (mstate av, mchunkptr p, int have_lock)
功能：釋放chunk，放入fast bin或合并後放入unsorted bin或合并到top chunk
具體過程如下：
如果屬于fast bin，則插入fast bin連結清單頭部；
否則如果不是mmap的記憶體，則進行合并；
後向合并-合并低位址 CHUNK
下一塊不是top chunk-前向合并-合并高位址chunk
合并後把 chunk 放在 unsorted chunk 連結清單的頭部
下一塊是top chunk-合并到top chunk
如果合并後chunk大小大于64KB，則合并fast chunk，收縮top;
否則如果是mmap的記憶體，則釋放mmap的chunk
2.7.1 簡單的檢查
檢查大小與對齊
size = chunksize (p);
//如果p+size繞過了位址空間的結尾，或者p沒有對齊，則出錯了
if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
|| __builtin_expect (misaligned_chunk (p), 0))
{
errstr = "free(): invalid pointer";
errout:
if (!have_lock && locked)
__libc_lock_unlock (av->mutex);
malloc_printerr (check_action, errstr, chunk2mem (p), av);
return;
}
// 大小沒有最小的chunk大，或者說，大小不是MALLOC_ALIGNMENT的整數倍，則有問題
if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
{
errstr = "free(): invalid size";
goto errout;
}
// 檢查該chunk是否處于使用狀态，非調試狀态下沒有作用
check_inuse_chunk(av, p);
2.7.2 Fast bin
如果屬于fast bin，則插入fast bin連結清單頭部；
//大小屬于fast bin
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
#if TRIM_FASTBINS
//預設 #define TRIM_FASTBINS 0，是以預設情況下下面的語句不會執行
//如果目前chunk是fast chunk，并且下一個chunk是top chunk，則不能插入
//此時由于定義了TRIM_FASTBINS，這個chunk會和top chunk合并
&& (chunk_at_offset(p, size) != av->top)
#endif
)
{
//檢查下一個chunk的大小上限和下限
// 下一個chunk的大小不能小于兩倍的SIZE_SZ,并且
// 下一個chunk的大小不能大于system_mem， 一般為132k
// 如果出現這樣的情況，就報錯
if (__builtin_expect (chunksize_nomask (chunk_at_offset (p, size))
<= 2 * SIZE_SZ, 0)
|| __builtin_expect (chunksize (chunk_at_offset (p, size))
>= av->system_mem, 0))
{
if (have_lock
|| ({ assert (locked == 0);
__libc_lock_lock (av->mutex);
locked = 1;
chunksize_nomask (chunk_at_offset (p, size)) <= 2 * SIZE_SZ
|| chunksize (chunk_at_offset (p, size)) >= av->system_mem;
}))
{
errstr = "free(): invalid next size (fast)";
goto errout;
}
if (! have_lock)
{
__libc_lock_unlock (av->mutex);
locked = 0;
}
}
// 将chunk的mem部分全部設定為perturb_byte
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
// 設定fast chunk的标記位
set_fastchunks(av);
unsigned int idx = fastbin_index(size);
fb = &fastbin (av, idx);
//将P插入fast bin連結清單頭部
mchunkptr old = *fb, old2;
unsigned int old_idx = ~0u;
do
{
// 防止對 fast bin double free
if (__builtin_expect (old == p, 0))
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
if (have_lock && old != NULL)
old_idx = fastbin_index(chunksize(old));
//P插入fast bin連結清單頭部
p->fd = old2 = old;
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
{
errstr = "invalid fastbin entry (free)";
goto errout;
}
}
2.7.3 合并非 mmap 的空閑 chunk
合并其他非mmap的chunks。
else if (!chunk_is_mmapped(p)) {
if (! have_lock) {
__libc_lock_lock (av->mutex);
locked = 1;
}
nextchunk = chunk_at_offset(p, size);
檢查是否有異常情況
// 目前free的chunk不能是top chunk
if (__glibc_unlikely (p == av->top))
{
errstr = "double free or corruption (top)";
goto errout;
}
// 目前free的chunk的下一個chunk不能超過arena的邊界
if (__builtin_expect (contiguous (av)
&& (char *) nextchunk
>= ((char *) av->top + chunksize(av->top)), 0))
{
errstr = "double free or corruption (out)";
goto errout;
}
// 目前要free的chunk的使用标記沒有被标記，double free
if (__glibc_unlikely (!prev_inuse(nextchunk)))
{
errstr = "double free or corruption (!prev)";
goto errout;
}
//下一個chunk的大小是否超出範圍
nextsize = chunksize(nextchunk);
if (__builtin_expect (chunksize_nomask (nextchunk) <= 2 * SIZE_SZ, 0)
|| __builtin_expect (nextsize >= av->system_mem, 0))
{
errstr = "free(): invalid next size (normal)";
goto errout;
}
填充
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
後向合并-合并低位址 CHUNK
//如果低位址chunk空閑，則合并後unlink
if (!prev_inuse(p)) {
prevsize = prev_size (p);
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
下一塊不是top chunk-前向合并-合并高位址chunk
合并後把 chunk 放在 unsorted chunk 連結清單的頭部
if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
// 如果不在使用，合并，否則清空目前chunk的使用狀态
if (!nextinuse) {
unlink(av, nextchunk, bck, fwd);
size += nextsize;
} else
clear_inuse_bit_at_offset(nextchunk, 0);
// 把 chunk 放在 unsorted chunk 連結清單的頭部
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "free(): corrupted unsorted chunks";
goto errout;
}
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);
set_foot(p, size);
check_free_chunk(av, p);
}
下一塊是top chunk-合并到top chunk
else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
check_chunk(av, p);
}
向系統返還記憶體
如果合并後chunk大小大于64KB，則合并fast chunk，收縮top;
//如果釋放大的空間，會合并周邊的chunks。
//然後，如果top超過了trim的門檻值，則使用malloc_trim來減少top
//在此之前，我們要先合并fast bin
//我們并不想每一次free都執行合并,作為一種折中，
//如果到達FASTBIN_CONSOLIDATION_THRESHOLD（64KB）才合并fast bin
//合并才執行top的收縮
if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
if (have_fastchunks(av))
malloc_consolidate(av);
if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
if ((unsigned long)(chunksize(av->top)) >=(unsigned long)(mp_.trim_threshold))
systrim(mp_.top_pad, av);
#endif
} else {
heap_info *heap = heap_for_ptr(top(av));
assert(heap->ar_ptr == av);
heap_trim(heap, mp_.top_pad);
}
}
if (! have_lock) {
assert (locked);
__libc_lock_unlock (av->mutex);
}
2.7.4 釋放mmap的chunk
else {
munmap_chunk (p);
}
1.8 malloc_consolidate
功能：清除fast chunk，能合并則合并，放入unsorted bin或并入top chunk。
具體過程如下：
如果fast bin已經初始化
周遊fast bin
周遊fast chunk
如果低位址chunk空閑，合并之，unlink
如果高位址不是top chunk
如果chunk空閑，合并之，unlink
Fast chunk放入unsorted bin的頭部
如果高位址是top chunk
合并到 top中
如果fast bin沒有初始化
調用malloc_init_state初始化malloc_state
//合并fast bin或初始化malloc_state
static void malloc_consolidate(mstate av)
合并fast chunk
// fast bin已經初始化
if (get_max_fast () != 0) {
// 清除fastbin 标記
clear_fastchunks(av);
unsorted_bin = unsorted_chunks(av);
//移除并合并fast bin中的每個chunk，将其放入unsorted bin
maxfb = &fastbin (av, NFASTBINS - 1); //最大的索引：9，實際上周遊的是fast bin 0~8
fb = &fastbin (av, 0);
do {
p = atomic_exchange_acq (fb, NULL);
if (p != 0) {
do {//周遊某個fast bin中的fast chunk
check_inuse_chunk(av, p);
nextp = p->fd;
//free()中的合并代碼的簡單流線型版本
size = chunksize (p);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);
//如果低位址chunk空閑，則合并後unlink，後面會放入unsorted chunk
if (!prev_inuse(p)) {
prevsize = prev_size (p);
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
//下一塊不是top chunk-前向合并-合并高位址chunk
//合并後把 chunk 放在 unsorted chunk 連結清單的頭部
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);
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 {//下一塊是top chunk-合并到top chunk
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
}
} while ( (p = nextp) != 0);
}
} while (fb++ != maxfb);
}
初始化malloc_state
else {
malloc_init_state(av);
check_malloc_state(av);
}
3 結論
【主要的API】
1. malloc_consolidate
功能：
清空fast bins，fast chunk能合并則合并，放入unsorted bin或并入top chunk。
具體過程如下：
如果fast bin已經初始化
周遊fast bin
周遊fast chunk
如果低位址chunk空閑，合并之，unlink
如果高位址不是top chunk
如果chunk空閑，合并之，unlink
Fast chunk放入unsorted bin的頭部
如果高位址是top chunk
合并到 top中
如果fast bin沒有初始化
調用malloc_init_state初始化malloc_state
2. Unlink
unlink 用來将一個雙向 bin 連結清單中的一個 chunk 取出來
參數：
AV：arena header(malloc_state)
P ：将要unlink的chunk
BK：P後面的chunk <--
FD：P前面的chunk -->
3個chunk的順序
-------->位址增加
BK P FD
具體過程如下：
将chunk從FD/BK連結清單中摘除；
如果是large chunk，則将chunk從fd_nextsize/bk_nextsize連結清單中摘除
3. _int_malloc
1．Fast bin服務請求
2．Small bin服務請求
3．如果是large chunk，則合并fast bin
4．循環處理
1) Unsorted bin服務請求
（周遊的unsorted chunk要麼比對使用者請求被傳回，要麼放入對應的bin中）
2) Large bin服務請求
3) next largest bin服務請求
4) top chunk服務請求
5) 合并fast bin，下次嘗試
6) 從系統請求記憶體
4. _int_free
功能：釋放chunk，放入fast bin或合并後放入unsorted bin或合并到top chunk
具體過程如下：
如果屬于fast bin，則插入fast bin連結清單頭部；
否則如果不是mmap的記憶體，則進行合并；
後向合并-合并低位址 CHUNK
下一塊不是top chunk-前向合并-合并高位址chunk
合并後把 chunk 放在 unsorted chunk 連結清單的頭部
下一塊是top chunk-合并到top chunk
如果合并後chunk大小大于64KB，則合并fast chunk，收縮top;
否則如果是mmap的記憶體，則釋放mmap的chunk
3 參考文檔
1. https://ctf-wiki.github.io/ctf-wiki/pwn/heap/heap_structure/
2. https://ctf-wiki.github.io/ctf-wiki/pwn/heap/heap_implementation_details/
![使用Docker進行Pwn題環境部署使用Docker進行Pwn題環境部署Pwn部署架構國賽Pwn之一[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)