二進(jìn)制安全之堆溢出（系列）——堆基礎(chǔ) & 結(jié)構(gòu)（三）
二進(jìn)制安全之堆溢出（系列）——“堆基礎(chǔ)&結(jié)構(gòu)”第三節(jié)上回書說到_int_malloc小總結(jié)本次咱們從calloc講起
calloc
calloc在動(dòng)態(tài)分配完內(nèi)存之后，自動(dòng)初始化該內(nèi)存空間為0，而malloc不初始化，里面數(shù)據(jù)是隨機(jī)的垃圾數(shù)據(jù)
_int_free
判斷是否在astbi的范圍內(nèi)
在就放入fastbin不在放入unsorted bin
當(dāng)放入unsorted bin檢查是否需要unlink
前向合并：向低地址合并后向合并：向高地址合并
滿足以下條件才會(huì)free
檢查當(dāng)前的塊的prev_inuse是否為0檢查下個(gè)塊的prev_insue是否為1檢查下下個(gè)塊的prev_insue是否為1此時(shí)發(fā)生前向合并如果下下個(gè)塊的prev_insue為0，則會(huì)前向合并之后再后向合并
__libc_free
用于封裝__int_free函數(shù)
主要包括三個(gè)部分
檢查是否有__free_hook ,利用：__free_hook->sysem如果堆塊是空則不進(jìn)行操作mmap的堆塊，使用ummap進(jìn)行釋放然后調(diào)用__int_free
? ?__malloc_hook
? ? void *weak_variable (*__malloc_hook)? (size_t __size, const void *) = malloc_hook_ini;void weak_variable (*__free_hook) (void *__ptr,? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?const void *) = NULL;
? ? malloc_hookl利用方法
1. 現(xiàn)在知道了system或一個(gè)shellcode的地址2. 要調(diào)這個(gè)shellcode的地址可以通過修改got表3. 在Partial RELRO保護(hù)機(jī)制下，無法寫入got表4. 這時(shí)候可以修改__malloc_hook地址為one_gadget的地址，構(gòu)造rop鏈，自5. 動(dòng)調(diào)用shellcode，起一個(gè)bin/sh。
6. 對(duì)于__free_hook，可以將其直接修改為system的地址，最簡單的就是傳入7. 7. 一個(gè)"bin/sh"的指針，這樣當(dāng)free某個(gè)堆塊的時(shí)候就會(huì)調(diào)用/bin/sh。8. 因?yàn)開_malloc_hook的參數(shù)類型為int,不能傳一個(gè)字符串的地址 "/bin/sh"9. 從而繞過Partial RELRO保護(hù)機(jī)制
__malloc_hook & fastbin attack
1. 將fastbin的fd指向[__malloc_hook+0x23] 或[ __free_hook]2. 再次malloc就會(huì)將[__malloc_hook+0x23] 或[ __free_hook]分配出來3. 在[__malloc_hook+0x23] 或[ __free_hook]寫一個(gè)地址，如"bin/sh"或shellcode，one_gadget的地址
unsorted bin
設(shè)計(jì)原則
釋放一個(gè)不屬于fastbin的chunk，并且該chunk不與top_chunk緊鄰時(shí)，就會(huì)進(jìn)入unsortedbin切割一個(gè)較大的chunk時(shí)，如果剩下的部分大于minsize時(shí)，就會(huì)被放到unsortedbin中unsortedbin管理bins鏈的原則 : 雙向循環(huán)鏈表，F(xiàn)IFOunsortedbin只有一個(gè)鏈表，即bin數(shù)組的第一個(gè)索引處當(dāng)unsorted bin被遍歷一次之后，會(huì)觸發(fā)整理，將相應(yīng)大小的chunk place in order
連接
當(dāng)chunk釋放到unsorted bin，當(dāng)前chunk內(nèi)就有l(wèi)ibc上的地址
0x7ffff7dd1000 0x7ffff7dd3000 rw-p 2000 1c4000 /lib/x86_64-linux-gnu/libc-2.23.solibc_arrd = libc_on - libc.symbol("main_arena") - 88
unsortedbin attack
1. 構(gòu)造overlap,控制一個(gè)釋放了還能修改的chunk
2. 修改當(dāng)前chunk的fd為target -0x23 的地址 3. 在進(jìn)行斷鏈操作時(shí)，當(dāng)前chunk的bk指向的地址bck賦給av->bk，將main_arena的地址賦給bck->fd，而bck->fd即當(dāng)前chunk的fd
4. 即我們將target - 0x23處寫入了main_arena的地址 a. main_arena為libc中的地址，以0x7f打頭b. target-0x23正好向size位寫入0x7f，只寫size的倒數(shù)第4位c. 這樣我們就在target中寫了一個(gè)0x7f的內(nèi)容d. 然后就可以結(jié)合fastbin，將target malloc出來，完成任意地址堆塊的創(chuàng)建和讀寫 5. 因?yàn)閙ain_arena的bk被修改了，unsortedbin的鏈表結(jié)構(gòu)被破壞
6. 因此再次分配堆塊的時(shí)候不能從unsortedbin上分配，而從fastedbin中分配(提前在fastedbin放幾個(gè)chunk)
? 3733 while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)) //當(dāng)前chunk為空是bk指向本身
? ? {
? ? bck = victim->bk;? ? ? //指向當(dāng)前chunk的bk指向的下一個(gè)chunk
? ? if (__builtin_expect (chunksize_nomask (victim) <= 2 * SIZE_SZ, 0)
? ? || __builtin_expect (chunksize_nomask (victim)
? ? > av->system_mem, 0))
? ? malloc_printerr ("malloc(): memory corruption");
? ? size = chunksize (victim);
? ? /*
? ? 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.
? ? */
? ? 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_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;
? ? }
? ? /* remove from unsorted list */
? ? unsorted_chunks (av)->bk = bck;? ?//斷鏈，將之前的chunk取出
? ? bck->fd = unsorted_chunks (av);
? ? last remainder
? ? 在用戶malloc請(qǐng)求分配內(nèi)存之后，ptmalloc找到的chunk與目標(biāo)申請(qǐng)的大小不一致時(shí)，會(huì)進(jìn)行切割，剩余部分稱為last remainder chunk，由 last_remainder 管理,存儲(chǔ)在unsortedbin中
? ? p main_arena可以查看last remainderlast_remainder = 0x6020a0
? ? 切割完成后會(huì)leak出<main_arena+376>的地址
? ? 0x602260 PREV_INUSE {
? ? prev_size = 0,
? ? size = 305,
? ? fd = 0x7ffff7dd1c98 <main_arena+376>,
? ? bk = 0x7ffff7dd1c98 <main_arena+376>,
? ? fd_nextsize = 0x0,
? ? bk_nextsize = 0x0
? ? }
? ? fast bin
設(shè)計(jì)原則
單向鏈表的管理結(jié)構(gòu),類似于C語言散列表的管理結(jié)構(gòu),分別以0x20，0x30，0x40到0x80為散列項(xiàng),相同的散列項(xiàng)被連接在一起ptmalloc專門設(shè)計(jì)了fastbin，用來管理程序在釋放一些較小的內(nèi)存塊，對(duì)應(yīng)malloc state結(jié)構(gòu)體中的fastbinY。
fastbin中的chunk的prev_inuse為1，故不會(huì)在遇到與之相鄰的chunk就發(fā)生合并，直到malloc_consolidate的時(shí)候會(huì)整理，實(shí)驗(yàn)在malloc大于0x400的時(shí)候兩個(gè)相鄰的fastbin會(huì)合并。每個(gè)bin管理的chunk默認(rèn)最大為0x80字節(jié)，但是可以最大支持到0xa0字節(jié)fastbin最多支持10個(gè)bin，從0x20到0xa0
管理原則
1. 當(dāng)用戶需要的chunk的大小小于fastbin中的最大大小的堆塊時(shí)，ptmalloc會(huì)首先判斷fastbin中相應(yīng)的bin中是否有對(duì)應(yīng)大小的空閑塊，如果有的話，直接獲取這個(gè)堆塊，沒有的話，從top_chunk中分配并進(jìn)行一系列操作。 2. 出入到fastbin的堆塊采用LIFO原則 : 最近free的chunk，與main_arena直接相連，從main_arena遍歷，并且最先被分配出去 3. main_arena開始對(duì)應(yīng)的散列項(xiàng)與0（null）相連,每插入一個(gè)chunk,在main_arena和0中間插一個(gè)，每個(gè)插入的堆塊都直接和main_arena相連
索引
ptmalloc默認(rèn)情況下會(huì)調(diào)用set_max_fast(DEFAULT_MAXFAST)將全局變量global_max_fast設(shè)置為DEFAULT_MAXFAST，即fastbin chunk的最大值。當(dāng)DEFAULT_MAXFAST設(shè)置為0時(shí)，系統(tǒng)就不會(huì)支持fastbinfastbin索引的計(jì)算方法：fastbin_idx(size)
連接
fastbin attack
1. 構(gòu)造一個(gè)fastbin的overlap(堆塊重疊)，造成釋放了當(dāng)前chunk還能對(duì)它修改 2. 修改當(dāng)前chunk的fd指向我們的target，當(dāng)釋放當(dāng)前chunk的時(shí)候，main_arena就會(huì)指向target?
3. 將偽造的地址的起始地址+0x8的內(nèi)存內(nèi)容即target的size修改為0x71或0x7f等,繞過chunk_size和prev_inuse的檢測，后面的內(nèi)容可以隨意寫入。（同一索引的chunk的大小在一個(gè)梯度內(nèi)，檢查是否在此梯度）tips ：libc的地址存在0x7fxxxx：0x7ffff7a0d000 0x7ffff7bcd000 r-xp 1c0000 0 /lib/x86_64-linux-gnu/libc-2.23.so4. 再次malloc的時(shí)候，就會(huì)malloc出來target的堆塊，比如target為got或任意地址，造成函數(shù)執(zhí)行和任意地址寫
? 斷鏈過程
? ? if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
? ? {
? ? idx = fastbin_index (nb);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //獲取散列號(hào)
? ? mfastbinptr *fb = &fastbin (av, idx);? ? ? ? ?//找到main_arena
? ? mchunkptr pp;
? ? victim = *fb;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//victim = main_arena->fd
? ? if (victim != NULL)
? ? {
? ? if (SINGLE_THREAD_P)
? ? *fb = victim->fd;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//將main_arena->fd->fd 賦給main_arena->fd,實(shí)現(xiàn)斷掉和main_arena直接相連的chunk
? ? else
? ? REMOVE_FB (fb, pp, victim);
? ? if (__glibc_likely (victim != NULL))
? ? {
? ? size_t victim_idx = fastbin_index (chunksize (victim)); //檢查chunk_size和散列表的大小是否一致以及prev_inuse=1
? ? if (__builtin_expect (victim_idx != idx, 0)) //檢測當(dāng)前的size和散列項(xiàng)的size是否一致
? ? malloc_printerr ("malloc(): memory corruption (fast)");
? ? check_remalloced_chunk (av, victim, nb);
small bin
管理原則
small bins中一共有62個(gè)循環(huán)雙向鏈表，每個(gè)鏈表中存儲(chǔ)的chunk大小一致
small bins中每個(gè)bin對(duì)應(yīng)的鏈表采取FIFO的規(guī)則
每次去bin鏈中的chunk是從bk指向的位置取的，bk指向目前最早釋放進(jìn)來的chunk
small bins中的每個(gè)chunk的大小與其所在的bin的index的關(guān)系是：chunk_size = 2 * SIZE_T * index
32位對(duì)應(yīng)的SIZE_T為4，64位對(duì)應(yīng)的SIZE_T為8small bins的index從2到62比如說對(duì)于64位機(jī)器，index = 2 ，chunk_size = 32；index = 62 ，chunk_size = 992
對(duì)于fastbin和small bin的重合問題的解釋
fastbin的chunk在經(jīng)過consolidate之后都會(huì)進(jìn)入到small bin中的0x20到0x80的對(duì)應(yīng)位置
small bin的結(jié)構(gòu)
large bin
管理原則
large bin一共包含63個(gè)bin，每個(gè)bin中的chunk的大小不一致，處于一個(gè)相同的范圍63個(gè)bin被分為公差一致的六組 ：第一組 : 索引64-95 數(shù)量32 起始大小1024 公差64 [1024,1024+64]第二組 : 索引96-111 數(shù)量16 起始大小xxxx 公差512第三組 : 索引112-119 數(shù)量8 起始大小xxxx 公差4096第四組 : 索引120-123 數(shù)量4 起始大小xxxx 公差32768第五組 : 索引124-125 數(shù)量2 起始大小xxxx 公差262144第六組 : 索引126 數(shù)量1 起始大小xxxx 公差無限制
與smallbin一樣采取FIFO的管理方式，不同的是largebin具有兩條雙向鏈表largebin中fd_nextsize和bk_nextsize按照chunk的大小排列，分別指向下一個(gè)更大size的chunk和更小的chunkfd和bk按照chunk的free順序排列(先來的和main_arena相連)·
結(jié)構(gòu)
largebin attack
要求target與當(dāng)前chunk在一個(gè)鏈上，大小范圍一致
碎塊合并
bin鏈的歸屬問題
fastbin：10個(gè)0x20-0x80,實(shí)際上malloc的大小為0x10-0x70
bin鏈 ：128個(gè)bin 1 為unsorted binbin 2 到63為small binbin 64到126為large bin
按照free的堆塊大小
0x20-0x80 --> 進(jìn)入fastbin
0x80以上 --> 進(jìn)入unsorted bin
bin鏈的整理分類
malloc_consolidate會(huì)整理fastbin，將能合并的fastbin合并一起放入unsortedbin，在unsortedbin的malloc的最后，會(huì)將unsortedbin上的堆塊進(jìn)行整理并放入到對(duì)應(yīng)的bin中
fastbin --->malloc_consolidate---> unsortedbin ----->整理后分配到相應(yīng)的bin鏈
在fastbin和unsortedbin，largebin，map上都沒有適合的堆塊才會(huì)從top_chunk中切割。
減少堆塊的碎片化
? ? consolidate
? ? fastbin范圍的chunk的inuse位始終為1，因此不會(huì)和其他釋放的chunk合并。當(dāng)釋放的chunk與該chunk相鄰的空閑chunk合并后的大小大于FAST_CONSOLIDATION_THRESHOLD時(shí)，內(nèi)存碎片可能性比較多了，我們需要把fastbins中的chunk都進(jìn)行合并，以減少內(nèi)存碎片對(duì)系統(tǒng)的影響。malloc_consolidate函數(shù)可以將fastbin中所有能和其它c(diǎn)hunk合并的chunk合并在一起。0. 碎片檢查針對(duì)于fastbin的碎片整理
? ? #define FAST_CONSOLIDATION_THRESHOLD (65536ul)
? ? 1. 觸發(fā)合并
? ? 第一次合并整理的時(shí)候malloc超過0x80的空間就會(huì)觸發(fā)合并
? ? /*
? ? 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))
? ? {
? ? idx = smallbin_index (nb);
? ? bin = bin_at (av, idx);
? ? if ((victim = last (bin)) != bin)
? ? {
? ? bck = victim->bk;
? ? if (__glibc_unlikely (bck->fd != victim))
? ? malloc_printerr ("malloc(): smallbin double linked list corrupted");
? ? set_inuse_bit_at_offset (victim, nb);
? ? bin->bk = bck;
? ? bck->fd = bin;
? ? if (av != &main_arena)
? ? set_non_main_arena (victim);
? ? check_malloced_chunk (av, victim, nb);
? ? #if USE_TCACHE
? ? /* While we're here, if we see other chunks of the same size,
? ? stash them in the tcache.? */
? ? size_t tc_idx = csize2tidx (nb);
? ? if (tcache && tc_idx < mp_.tcache_bins)
? ? {
? ? mchunkptr tc_victim;
? ? /* While bin not empty and tcache not full, copy chunks over.? */
? ? while (tcache->counts[tc_idx] < mp_.tcache_count
? ? && (tc_victim = last (bin)) != bin)
? ? {
? ? if (tc_victim != 0)
? ? {
? ? bck = tc_victim->bk;
? ? set_inuse_bit_at_offset (tc_victim, nb);
? ? if (av != &main_arena)
? ? set_non_main_arena (tc_victim);
? ? bin->bk = bck;
? ? bck->fd = bin;
? ? tcache_put (tc_victim, tc_idx);
? ? }
? ? }
? ? }
? ? #endif
? ? void *p = chunk2mem (victim);
? ? alloc_perturb (p, bytes);
? ? return p;
? ? }
? ? }
? ? /*
? ? If this is a large request, consolidate fastbins before continuing.
? ? While it might look excessive to kill all fastbins before
? ? even seeing if there is space available, this avoids
? ? fragmentation problems normally associated with fastbins.
? ? Also, in practice, programs tend to have runs of either small or
? ? large requests, but less often mixtures, so consolidation is not
? ? invoked all that often in most programs. And the programs that
? ? it is called frequently in otherwise tend to fragment.
? ? */
? ? else
? ? {
? ? idx = largebin_index (nb); //當(dāng)前chunk為largebin
? ? if (atomic_load_relaxed (&av->have_fastchunks)) //含有fastbin時(shí)觸發(fā)
? ? malloc_consolidate (av);
? ? }
? ? 2. 開始合并
? ? 將fastbin上取消的堆塊合并到unsortedbin
? ? static void malloc_consolidate(mstate av)
? ? {
? ? mfastbinptr*? ? fb;? ? ? ? ? ? ? ? ?/* current fastbin being consolidated */
? ? mfastbinptr*? ? maxfb;? ? ? ? ? ? ? /* last fastbin (for loop control) */
? ? mchunkptr? ? ? ?p;? ? ? ? ? ? ? ? ? /* current chunk being consolidated */
? ? mchunkptr? ? ? ?nextp;? ? ? ? ? ? ? /* next chunk to consolidate */
? ? mchunkptr? ? ? ?unsorted_bin;? ? ? ?/* bin header */
? ? mchunkptr? ? ? ?first_unsorted;? ? ?/* chunk to link to */
? ? /* These have same use as in free() */
? ? mchunkptr? ? ? ?nextchunk;
? ? INTERNAL_SIZE_T size;
? ? INTERNAL_SIZE_T nextsize;
? ? INTERNAL_SIZE_T prevsize;
? ? int? ? ? ? ? ? ?nextinuse;
? ? mchunkptr? ? ? ?bck;
? ? mchunkptr? ? ? ?fwd;
? ? atomic_store_relaxed (&av->have_fastchunks, false);
? ? unsorted_bin = unsorted_chunks(av);? //取un的bin頭
? ? /*
? ? 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.
? ? */
? ? maxfb = &fastbin (av, NFASTBINS - 1);
? ? fb = &fastbin (av, 0);
? ? do {
? ? p = atomic_exchange_acq (fb, NULL);
? ? if (p != 0) {
? ? do {
? ? {
? ? unsigned int idx = fastbin_index (chunksize (p)); //取fastbin的bin頭
? ? if ((&fastbin (av, idx)) != fb)
? ? malloc_printerr ("malloc_consolidate(): invalid chunk size");
? ? }
? ? check_inuse_chunk(av, p);? //檢測前項(xiàng)chunk是否正在使用
? ? nextp = p->fd;
? ? /* Slightly streamlined version of consolidation code in free() */
? ? size = chunksize (p);
? ? nextchunk = chunk_at_offset(p, size); //獲取fastbin的堆塊
? ? nextsize = chunksize(nextchunk);
? ? if (!prev_inuse(p)) {? ? ? //合并fastbin
? ? prevsize = prev_size (p);
? ? size += prevsize;
? ? p = chunk_at_offset(p, -((long) prevsize));
? ? unlink(av, p, bck, fwd);
? ? }
? ? if (nextchunk != av->top) {? ? ? //合并整理unsortedbin
? ? 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;? ? ? ? //p：fastbin取上的堆塊,將其合并到unsortedbin
? ? 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);
? ? }
? ? 3. 開始查找
? ? 遍歷查找當(dāng)前unsortedbin上合適的堆塊,必要的時(shí)候切割unsortedbin
? ? /*
? ? 1. 在unsortedbin上尋找有沒有適合的堆塊
? ? 2. 沒有的話有兩種情況
? ? 2.1 切割unsortedbin
? ? 2.2 再次觸發(fā)consolidate，然后切割topchunk
? ? */
? ? for (;; )
? ? {
? ? int iters = 0;
? ? while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)) //當(dāng)前chunk為空是bk指向本身
? ? {
? ? bck = victim->bk;? ? ? //指向當(dāng)前chunk的bk指向的下一個(gè)chunk
? ? if (__builtin_expect (chunksize_nomask (victim) <= 2 * SIZE_SZ, 0)
? ? || __builtin_expect (chunksize_nomask (victim)
? ? > av->system_mem, 0))
? ? malloc_printerr ("malloc(): memory corruption");
? ? size = chunksize (victim);
? ? /*
? ? 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.
? ? */
? ? //需要的chunk必須在0x20-0x400的時(shí)候才會(huì)切割unsortedbin
? ? if (in_smallbin_range (nb) &&
? ? bck == unsorted_chunks (av) &&
? ? victim == av->last_remainder &&
? ? (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
? ? { //切割完大于0x20
? ? /* split and reattach remainder */
? ? 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;
? ? }
? ? /* remove from unsorted list */
? ? unsorted_chunks (av)->bk = bck;? ?//斷鏈，將之前的chunk取出
? ? bck->fd = unsorted_chunks (av);
? ? /* Take now instead of binning if exact fit */
? ? if (size == nb)
? ? {
? ? set_inuse_bit_at_offset (victim, size);
? ? if (av != &main_arena)
? ? set_non_main_arena (victim);
? ? //當(dāng)前循環(huán)跳出表示unsortedbin找不到適合的堆塊
? ? 4.開始整理
? ? 將unsortedbin上找到的合適堆塊整理到相應(yīng)大小的bin鏈中
? ? /* place chunk in bin */
? ? if (in_smallbin_range (size))? //判斷從unsortedbin上取出的堆塊是否在smallbin
? ? {
? ? victim_index = smallbin_index (size); //放入smallbin
? ? bck = bin_at (av, victim_index);
? ? fwd = bck->fd;
? ? }
? ? else
? ? {
? ? victim_index = largebin_index (size); //放入largebin
? ? bck = bin_at (av, victim_index);
? ? fwd = bck->fd;
? ? /* 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 (chunk_main_arena (bck->bk));
? ? if ((unsigned long) (size)
? ? < (unsigned long) chunksize_nomask (bck->bk))
? ? {
? ? fwd = bck;
? ? bck = bck->bk;
? ? victim->fd_nextsize = fwd->fd;
? ? victim->bk_nextsize = fwd->fd->bk_nextsize;
? ? fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
? ? }
? ? else
? ? {
? ? assert (chunk_main_arena (fwd));
? ? while ((unsigned long) size < chunksize_nomask (fwd))
? ? {
? ? fwd = fwd->fd_nextsize;
? ? assert (chunk_main_arena (fwd));
? ? }
? ? if ((unsigned long) size
? ? == (unsigned long) chunksize_nomask (fwd))
? ? /* Always insert in the second position.? */
? ? fwd = fwd->fd;
? ? else
? ? {
? ? 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;
后續(xù)內(nèi)容請(qǐng)看下一篇哦~~
