97人人做人人添人人爱,番里H肉3D动漫在线观看网站,久久久噜噜噜久噜久久

malloc

本文梳理了一下malloc跟free的源碼。malloc()函數(shù)在源代碼中使用宏定義為public_mALLOc()。public_mALLOc()函數(shù)只是簡(jiǎn)單的封裝_int_malloc()函數(shù)，_int_malloc()函數(shù)才是內(nèi)存分配的核心實(shí)現(xiàn)。

public_mALLOc()

Void_t* public_mALLOc(size_t bytes)
{
mstate ar_ptr;
Void_t *victim;
__malloc_ptr_t (*hook) (size_t, __const __malloc_ptr_t)
= force_reg (__malloc_hook);
if (__builtin_expect (hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS (0));

首先檢查是否存在__malloc_hook。如果存在，則調(diào)用hook函數(shù)。注意hook函數(shù)的傳參為請(qǐng)求分配的內(nèi)存大小。

arena_lookup(ar_ptr);
arena_lock(ar_ptr, bytes);
if(!ar_ptr)
return 0;
victim = _int_malloc(ar_ptr, bytes);

獲取分配區(qū)指針，如果獲取分配區(qū)失敗，返回退出，否則，調(diào)用_int_malloc()函數(shù)分配內(nèi)存。

if(!victim)
{
/* Maybe the failure is due to running out of mmapped areas. */
if(ar_ptr != &main_arena)
{
(void)mutex_unlock(&ar_ptr->mutex);
ar_ptr = &main_arena;
(void)mutex_lock(&ar_ptr->mutex);
victim = _int_malloc(ar_ptr, bytes);
(void)mutex_unlock(&ar_ptr->mutex);
}

如果_int_malloc()函數(shù)分配內(nèi)存失敗，并且使用的分配區(qū)不是主分配區(qū)，這種情況可能是mmap區(qū)域的內(nèi)存被用光了。如果目前主分配區(qū)還可以從堆中分配內(nèi)存，則需要再嘗試從主分配區(qū)中分配內(nèi)存。首先釋放所使用分配區(qū)的鎖，然后獲得主分配區(qū)的鎖，并調(diào)用_int_malloc()函數(shù)分配內(nèi)存，最后釋放主分配區(qū)的鎖。

else
{
#if USE_ARENAS
/* ... or sbrk() has failed and there is still a chance to mmap() */
ar_ptr = arena_get2(ar_ptr->next ? ar_ptr : 0, bytes);
(void)mutex_unlock(&main_arena.mutex);
if(ar_ptr)
{
victim = _int_malloc(ar_ptr, bytes);
(void)mutex_unlock(&ar_ptr->mutex);
}
#endif
}
}

如果_int_malloc()函數(shù)分配內(nèi)存失敗，并且使用的分配區(qū)是主分配區(qū)，查看是否有非主分配區(qū)，如果有，調(diào)用arena_get2()獲取分配區(qū)，然后對(duì)主分配區(qū)解鎖，如果arena_get2()返回一個(gè)非分配區(qū)，嘗試調(diào)用_int_malloc()函數(shù)從該非主分配區(qū)分配內(nèi)存，最后釋放該非主分配區(qū)的鎖。

else
(void)mutex_unlock(&ar_ptr->mutex);
assert(!victim || chunk_is_mmapped(mem2chunk(victim)) || ar_ptr ==
arena_for_chunk(mem2chunk(victim)));
return victim;
}

如果_int_malloc()函數(shù)分配內(nèi)存成功，釋放所使用的分配區(qū)的鎖。返回分配的chunk。

_int_malloc

_int_malloc函數(shù)是內(nèi)存分配的核心，根據(jù)分配的內(nèi)存塊的大小，該函數(shù)中實(shí)現(xiàn)了了四種分配內(nèi)存的路徑。先給出_int_malloc()函數(shù)的定義及臨時(shí)變量的定義：

static Void_t* _int_malloc(mstate av, size_t bytes)
{
INTERNAL_SIZE_T nb; /* normalized request size */
unsigned int idx; /* associated bin index */
mbinptr bin; /* associated bin */

mchunkptr victim; /* inspected/selected chunk */
INTERNAL_SIZE_T size; /* its size */
int victim_index; /* its bin index */

mchunkptr remainder; /* remainder from a split */
unsigned long remainder_size; /* its size */

unsigned int block; /* bit map traverser */
unsigned int bit; /* bit map traverser */
unsigned int map; /* current word of binmap */

mchunkptr fwd; /* misc temp for linking */
mchunkptr bck; /* misc temp for linking */

const char *errstr = NULL;

/*
Convert request size to internal form by adding SIZE_SZ bytes
overhead plus possibly more to obtain necessary alignment and/or
to obtain a size of at least MINSIZE, the smallest allocatable
size. Also, checked_request 2size traps (returning 0) request sizes
that are so large that they wrap around zero when padded and
aligned.
*/

checked_request2size()函數(shù)將需要分配的內(nèi)存大小bytes轉(zhuǎn)換為需要分配的chunk大小nb，Ptmalloc內(nèi)部分配都是以chunk為單位，根據(jù)chunk的大小，決定如何獲得滿足條件的chunk。

分配fast bin chunk

/*
If the size qualifies as a fastbin, first check corresponding bin.
This code is safe to execute even if av is not yet initialized, so we
can try it without checking, which saves some time on this fast path.
*/
if ((unsigned long)(nb) <= (unsigned long)(get_max_fast ()))
{
idx = fastbin_index(nb);
mfastbinptr* fb = &fastbin (av, idx);
#ifdef ATOMIC_FASTBINS
mchunkptr pp = *fb;
do
{
victim = pp;
if (victim == NULL)
break;
} while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) != victim);
#else
victim = *fb;
#endif
if (victim != 0)
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim));
return NULL;
}
#ifndef ATOMIC_FASTBINS
*fb = victim->fd;
#endif
check_remalloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}
}

如果所需的chunk大小小于等于fast bins中的最大chunk大小，首先嘗試從fast bin中分配chunk。1.根據(jù)所需的chunk大小獲得該chunk所屬的fast bin的index，根據(jù)該index獲得所屬fast bin的空閑chunk鏈表頭指針。如果沒有開啟ATOMIC_FASTBINS優(yōu)化，則按以下步驟：2.將頭指針的下一個(gè)chunk作為空閑chunk鏈表的頭部。3.取出第一個(gè)chunk，并調(diào)用chunk2mem()函數(shù)返回用戶所需的內(nèi)存塊。如果開啟了ATOMIC_FASTBINS優(yōu)化，則步驟與上述類似，只是在刪除fastbin頭節(jié)點(diǎn)的時(shí)候使用了lock-free技術(shù)，加快了分配速度。

check

fastbin分配對(duì)size做了檢查，如果分配chunk的size不等于分配時(shí)的idx，就會(huì)報(bào)錯(cuò)。使用chunksize()和fastbin_index函數(shù)計(jì)算chunk的size大小，所以我們無(wú)需管size的后三位(size_sz=8的情況下無(wú)需管后四位)，只需保證前幾位與idx相同即可。

分配small bin chunk

/*
If a small request, check regular bin. Since these "smallbins"
hold one size each, no search ing 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)
{
if (victim == 0) /* initialization check */
malloc_consolidate(av);
else
{
bck = victim->bk;
if (__builtin_expect (bck->fd != victim, 0))
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
set_inuse_bit_at_offset(victim, nb);
bin->bk = bck;
bck->fd = bin;

if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}
}
}

如果所需的chunk大小屬于small bin，則會(huì)執(zhí)行如下步驟：1.查找chunk對(duì)應(yīng)small bins數(shù)組的index，根據(jù)index獲得某個(gè)small bin的空閑chunk雙向循環(huán)鏈表表頭。2.將最后一個(gè)chunk賦值給victim，如果victim與表頭相同，表示該鏈表為空，不能從small bin的空閑chunk鏈表中分配，這里不做處理，等后面的步驟來處理。3.victim與表頭不同有兩種情況。

victim為0
1.表示small bin還沒有初始化為雙向循環(huán)鏈表，調(diào)用malloc_consolidete()函數(shù)將fast bins中的chunk合并。
victim不為0
1.設(shè)置victim chunk的inuse標(biāo)志，該標(biāo)志處于vimctim chunk的下一個(gè)相鄰chunk的size字段的第一個(gè)bit。2.做與unlink類似的操作將chunk從small bin中脫鏈。

4.判斷當(dāng)前分配區(qū)是否屬于非主分配區(qū)，如果是，將victim chunk的size字段中的標(biāo)志非主分配區(qū)的標(biāo)志bit清零。5.調(diào)用chunk2mem()函數(shù)獲得chunk的實(shí)際可用的內(nèi)存指針，將該內(nèi)存指針返回給應(yīng)用層。

check

申請(qǐng)的chunk需滿足chunk->bk->fd = chunk

分配large bin chunk

/*
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);
if (have_fastchunks(av))
malloc_consolidate(av);
}

所需chunk不屬于small bins，那么就在large bins的范圍內(nèi)，則

1.根據(jù)chunk的大小獲得對(duì)應(yīng)large bin的index

2.判斷當(dāng)前分配區(qū)的fast bins中是否包含chunk，如果存在，調(diào)用malloc_consolidate()函數(shù)合并fast bins中的chunk，并將這些空閑chunk加入unsorted bin中。

下面的源代碼實(shí)現(xiàn)從last remainder chunk，large bins和top chunk中分配所需的chunk，這里包含了多個(gè)多層循環(huán)，在這些循環(huán)中，主要工作是分配前兩步都未分配成功的small bin chunk、large bin chunk和large chunk。最外層的循環(huán)用于重新嘗試分配small bin chunk，因?yàn)槿绻谇耙徊椒峙鋝mallbin chunk不成功，并沒有調(diào)用malloc_consolidate()函數(shù)合并fast bins中的chunk，將空閑chunk加入unsorted bin中，如果第一嘗試從last remainder chunk、top chunk中分配small bin chunk都失敗以后，如果fast bins中存在空閑chunk，會(huì)調(diào)用malloc_consolidate()函數(shù)，那么在usorted bin中就可能存在合適的small bin chunk供分配，所以需要再次嘗試。

/*
Process recently freed or remaindered chunks, taking one only if
it is exact fit, or, if this a small request, the chunk is remainder from
the most recent non - exact fit. Place other traversed chunks in
bins. Note that this step is the onl y place in any routine where
chunks are placed in bins.

The outer loop here is needed because we might not realize until
near the end of malloc that we should have consolidated, so must
do so and retry. This happens at most once, and only when we would
otherwise need to expand memory to service a "small" request.
*/
for(;;)
{
int iters = 0;
while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av))
{

反向遍歷unsorted bin的雙向鏈表，遍歷結(jié)束的條件是循環(huán)鏈表中只剩一個(gè)頭節(jié)點(diǎn)。

bck = victim->bk;
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (victim->size > av->system_mem, 0))
malloc_printerr (check_action, "malloc(): memory corruption",
chunk2mem (victim));
size = chunksize(victim);

1.檢查當(dāng)前遍歷的chunk是否合法，chunk的大小不能小于等于2*SIZE_SZ，也不能超過該分配區(qū)總的內(nèi)存分配量。

2.獲取chunk的大小并賦值給size。

if (in_smallbin_range(nb) &&
bck == unsorted_chunks(av) &&
victim == av->last_remainder &&
(unsigned long)(size) > (unsigned long)(nb + MINSIZE))
{

如果需要分配一個(gè)small bin chunk，并且unsorted bin中只有一個(gè)chunk，并且這個(gè)chunk為last remainder chunk，并且這個(gè)chunk的大小大于所需chunk的大小加上MINSIZE，在滿足這些條件的情況下，可以使用這個(gè)chunk切分出需要的small bin chunk。這是唯一的從unsorted bin中分配small bin chunk的情況。

/* 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;
}

1.從chunk中切分出所需大小的chunk。

2.計(jì)算切分后剩下chunk的大小，將剩下的chunk加入unsorted bin的鏈表中，并將剩下的chunk作為分配區(qū)的last remainder chunk。

3.如果剩下的chunk屬于large bin chunk，將該chunk的fd_nextsize和bk_nextsize設(shè)置為NULL，因?yàn)檫@個(gè)chunk僅僅存在于unsorted bin中，并且unsorted bin中有且僅有這一個(gè)chunk。

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);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p；
}

設(shè)置分配出的chunk和last remainder chunk的相關(guān)信息。，調(diào)用chunk2mem()獲得chunk中可用的內(nèi)存指針，返回給應(yīng)用層，退出。

/* remove from unsorted list */
unsorted_chunks(av)->bk = bck;
bck->fd = unsorted_chunks(av);

將雙向循環(huán)鏈表中的最后一個(gè)chunk移除。

if (size == nb)
{
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}

如果當(dāng)前chunk與所需的chunk大小一致 1.設(shè)置當(dāng)前chunk處于inuse狀態(tài) 2.設(shè)置分配區(qū)標(biāo)志位 3.調(diào)用chunk2mem()獲得chunk中的可用內(nèi)存指針，返回給應(yīng)用層。

/* place chunk in bin */
if (in_smallbin_range(size))
{
victim_index = smallbin_index(size);
bck = bin_at(av, victim_index);
fwd = bck->fd;
}

如果當(dāng)前chunk屬于small bins，獲得當(dāng)前chunk所屬small bin的index，并將該small bin的鏈表表頭復(fù)制給bck，第一個(gè)chunk賦值給fwd，也就是當(dāng)前的chunk會(huì)插入到bck和fwd之間，作為small bin比鏈表的第一個(gè)chunk。

else
{
victim_index = largebin_index(size);
bck = bin_at(av, victim_index);
fwd = bck->fd;

如果當(dāng)前chunk屬于large bins，獲得當(dāng)前chunk所屬large bin的index，并將該large bin的鏈表表頭賦值給bck，第一個(gè)chunk賦值給fwd，也就是當(dāng)前的chunk會(huì)插入到bck和fwd之間，作為large bin鏈表的第一個(gè)chunk。

/* maintain large bins in sorted order */
if (fwd != bck)
{
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smalle r than smallest, bypass loop below */
assert((bck->bk->size & NON_MAIN_ARENA) == 0);

如果fwd不等于bck，意味著large bin中有空閑chunk存在，由于large bin中的空閑chunk是按照大小排序的，需要將當(dāng)前從unsorted bin中取出的chunk插入到large bin中合適的位置。將當(dāng)前的chunk的size的inuse標(biāo)志bit置位，相當(dāng)于加1，便于加快chunk大小的比較，找到合適的地方插入當(dāng)前chunk。

if ((unsigned long)(size) < (unsigned long)(bck->bk->size))
{
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;
}

如果當(dāng)前的chunk比large bin的最后一個(gè)chunk的大小還小，那么當(dāng)前chunk1就插入到large bin的鏈表的最后，作為最后一個(gè)chunk?？梢钥闯鰈arge bin中的chunk是按照從大到小的順序排序的，同時(shí)一個(gè)chunk存在于兩個(gè)雙向循環(huán)鏈表中，一個(gè)鏈表包含了large bin中所有的chunk，另一個(gè)鏈表為chunk size鏈表，該鏈表從每個(gè)相同大小的chunk中取除第一個(gè)chunk按照大小順序鏈接在一起，便于一次跨域多個(gè)相同大小的chunk遍歷下一個(gè)不同大小的chunk，這樣可以加快在large bin鏈表中的遍歷速度。

else
{
assert((fwd->size & NON_MAIN_ARENA) == 0);
while ((unsigned long) size < fwd->size)
{
fwd = fwd->fd_nextsize;
assert((fwd->size & NON_MAIN_ARENA) == 0);
}

正向遍歷chunk size鏈表，直到找到第一個(gè)chunk大小小于等于當(dāng)前chunk大小的chunk退出循環(huán)。

if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;

如果從large bin鏈表中找到了與當(dāng)前chunk大小相同的chunk，則統(tǒng)一大小的chunk已經(jīng)存在，那么chunk size一定包含了fwd指向的chunk，為了不久改chunk size鏈表，當(dāng)前chunk只能插入fwd之后。

else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}

如果chunk size鏈表中還沒有包含當(dāng)前chunk大小的chunk，也就是說當(dāng)前chunk的大小大于fwd的大小，則將當(dāng)前chunk作為該chunk size的代表加入chunk size鏈表，chunk size鏈表也是按照由大到小的順序排序。

bck = fwd->bk;
}
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}

如果large bin鏈表中沒有chunk，直接將當(dāng)前chunk加入chunk size鏈表。

mark_bin(av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

將當(dāng)前chunk插入到對(duì)應(yīng)的空閑的chunk鏈表中，并將large bin所對(duì)應(yīng)binmap的相應(yīng)bit置位。

#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break；
}

如果unsorted bin中的chunk超過了10000個(gè)，最多遍歷一萬(wàn)個(gè)就退出，避免長(zhǎng)時(shí)間處理unsorted bin影響內(nèi)存分配的效率。當(dāng)unsorted bin中的空閑chunk加入到相應(yīng)的small bins和large bins后，將使用最佳匹配法分配large bin chunk。

/*
If a large request, scan through the chunks of current bin in
sorted order to find smallest that fits. Use the skip list for this.
*/
if (!in_smallbin_range(nb))
{
bin = bin_at(av, idx);

/* skip scan if empty or largest chunk is too small */
if ((victim = first(bin)) != bin &&
(unsigned long)(victim->size) >= (unsigned long)(nb))
{

如果所需分配的chunk為large bin chunk，查詢對(duì)應(yīng)的large bin鏈表，如果large bin鏈表為空，或者鏈表中最大的chunk也不能滿足要求，則不能從large bin中分配。否則，遍歷large bin鏈表，找到合適的chunk。

victim = victim->bk_nextsize;
while (((unsigned long)(size = chunksize(victim)) <
(unsigned long)(nb)))
victim = victim->bk_nextsize;

反向遍歷chunk size鏈表，直到找到第一個(gè)大于等于所需chunk大小的chunk退出循環(huán)。

/* Avoid removing the first entry for a size so that the skip
list does not have to be rerouted. */
if (victim != last(bin) && victim->size == victim->fd->size)
victim = victim->fd;

如果large bin鏈表中選取的chunk civtim不是鏈表中的最后一個(gè)chunk，并且與victim大小相同的chunk不止一個(gè)，那么意味著victim為chunk size鏈表中的節(jié)點(diǎn)，為了不調(diào)整chunk size鏈表，需要避免將chunk size鏈表中取出，所以取victim->fd節(jié)點(diǎn)對(duì)應(yīng)的chunk作為候選chunk。由于large bin鏈表中的chunk也是按照大小排序，同一大小的chunk有多個(gè)時(shí)，這些chunk必定排在一起，所以victim->fd節(jié)點(diǎn)對(duì)應(yīng)的chunk的大小必定與victim的大小一樣。

remainder_size = size - nb;
unlink(victim, bck, fwd);

計(jì)算將victim切分后剩余大小，并調(diào)用unlink()宏函數(shù)將victim從large bin鏈表中取出。

if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}

如果將victim切分后剩余大小小于MINSIZE，則將整個(gè)victim分配給應(yīng)用層，設(shè)置victim的inuse標(biāo)志，inuse標(biāo)志位于下一個(gè)相鄰的chunk的size字段中。如果當(dāng)前分配區(qū)不是主分配區(qū)，將victim的size字段中的非主分配區(qū)標(biāo)志置位。

/* Split */
else
{
remainder = chunk_at_offset(victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__builtin_expect (fwd->bk != bck, 0))
{
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;
}

從victim中切分出所需的chunk，剩余部分作為一個(gè)新的chunk加入到unsorted bin中。如果剩余部分chunk屬于large bins，將剩余部分chunk的chunk size鏈表指針設(shè)置為NULL，因?yàn)閡nsorted bin中的chunk是不排序的，這兩個(gè)指針無(wú)用，必須清零。

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);
}

設(shè)置victim和remainder的狀態(tài)，由于remainder為空閑chunk，所以需要設(shè)置該chunk的foot。

check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}
}

從large bin中使用最佳匹配法找到了合適的chunk，調(diào)用chunk2mem()獲得chunk中可用的內(nèi)存指針，返回給應(yīng)用層，退出。如果通過上面的方式從最合適的small bin或large bin中都沒有分配到需要的chunk，則查看比當(dāng)前bin的index大的small bin或large bin是否有空閑chunk可利用來分配所需的chunk。源代碼實(shí)現(xiàn)如下：

++idx;
bin = bin_at(av,idx);
block = idx2block(idx);
map = av->binmap[block];
bit = idx2bit(idx);

獲取下一個(gè)相鄰bin的空閑chunk鏈表，并獲取該bin對(duì)于binmap中的bit位的值。Binmap中的標(biāo)識(shí)了相應(yīng)的bin中是否有空閑 chunk 存在。Binmap按block管理，每個(gè)block為一個(gè)int，共32個(gè)bit，可以表示32個(gè)bin中是否有空閑chunk存在。使用binmap可以加快查找bin是否包含空閑chunk。這里只查詢比所需chunk大的bin中是否有空閑chunk 可用。

for (;;)
{
/* Skip rest of block if there are no more set bits in this block. */
if (bit > map || bit == 0)
{
do
{
if (++block >= BINMAPSIZE) /* out of bins */
goto use_top;
}while ( (map = av->binmap[block]) == 0);
bin = bin_at(av, (block << BINMAPSHIFT));
bit = 1;
}

Idx2bit()宏將idx指定的位設(shè)置為1，其它位清零，map表示一個(gè)block值，如果bit大于map，意味著map為0，該block所對(duì)應(yīng)的所有bins中都沒有空閑chunk，于是遍歷binmap的下一個(gè)block，直到找到一個(gè)不為0的block或者遍歷完所有的 block。退出循環(huán)遍歷后，設(shè)置 bin 指向 block 的第一個(gè) bit 對(duì)應(yīng)的 bin，并將 bit 置為 1，表示該 block 中 bit 1 對(duì)應(yīng)的 bin，這個(gè) bin 中如果有空閑 chunk，該 chunk 的大小一定滿足要求。

/* Advance to bin with set bit. There must be one. */
while ((bit & map) == 0)
{
bin = next_bin(bin);
bit <<= 1;
assert(bit != 0);
}
/* Inspect the bin. It is likely to be non - empty */
victim = last(bin);

在一個(gè)block遍歷對(duì)應(yīng)的bin，直到找到一個(gè)bit不為0退出遍歷，則該bit對(duì)于的bin中有空閑chunk存在。將bin鏈表中的最后一個(gè)chunk賦值為victim。

/* If a false alarm (empty bin), clear the bit. */
if (victim == bin)
{
av->binmap[block] = map &= ~bit;
/* Write through */
bin = next_bin(bin);
bit <<= 1;
}

如果victim與bin鏈表頭指針相同，表示該bin中沒有空閑chunk，binmap中的相應(yīng)位設(shè)置不準(zhǔn)確，將binmap的相應(yīng)bit位清零，獲取當(dāng)前bin下一個(gè)bin，將bit移到下一個(gè)bit位，即乘以2。

else
{
size = chunksize(victim);
/* We know the first chunk in this bin is big enough to use. */
assert((unsigned long)(size) >= (unsigned long)(nb));
remainder_size = size - nb;
/* unlink */
unlink(victim, bck, fwd);

當(dāng)前bin中的最后一個(gè)chunk滿足要求，獲取該chunk的大小，計(jì)算切分出所需chunk后剩余部分的大小，然后將victim從bin的鏈表中取出。

/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA
}

如果剩余部分的大小小于MINSIZE，將整個(gè)chunk分配給應(yīng)用層(代碼在后面)，設(shè)置victim的狀態(tài)為inuse，如果當(dāng)前分配區(qū)為非分配區(qū)，設(shè)置victim的非主分配區(qū)標(biāo)志位。

/* Split */
else
{
remainder = chunk_at_offset(victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__builtin_expect (fwd->bk != bck, 0))
{
errstr = "malloc(): corrupted unsorted chunks 2";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
/* advertise as last 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);
}

設(shè)置victim和remainder的狀態(tài)，由于remainder為空閑chunk，所以需要設(shè)置該chunk的foot。

check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}
}

調(diào)用chunk2mem()獲得chunk中可用的內(nèi)存指針，返回給應(yīng)用層，退出。如果從所有的bins中都沒有獲得所需的chunk，可能的情況為bins中沒有空閑chunk，或者所需的chunk大小很大，下一步將嘗試從top chunk中分配所需chunk。源代碼實(shí)現(xiàn)如下：

use_top:
victim = av->top;
size = chunksize(victim);

將當(dāng)前分配區(qū)的top chunk賦值給victim，并獲得victim的大小。

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);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}

由于top chunk切分出所需chunk后，還需要MINSIZE的空間來作為fencepost，所需必須滿足top chunk的大小大于所需chunk的大小加上MINSIZE這個(gè)條件，才能從top chunk中分配所需chunk。從top chunk切分出所需chunk的處理過程跟前面的chunk切分類似，不同的是，原top chunk切分后的剩余部分將作為新的top chunk，原top chunk的fencepost仍然作為新的top chunk的fencepost，所以切分之后剩余的chunk不用set_foot。

#ifdef ATOMIC_FASTBINS
/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
else if (have_fastchunks(av))
{
malloc_consolidate(av);
/* restore original bin index */
if (in_smallbin_range(nb))
idx = smallbin_index(nb);
else
idx = largebin_index(nb);
}

如果top chunk也不能滿足要求，查看fast bins中是否有空閑chunk存在，由于開啟了ATOMIC_FASTBINS優(yōu)化情況下，free屬于fast bins的chunk時(shí)不需要獲得分配區(qū)的鎖，所以在調(diào)用_int_malloc()函數(shù)時(shí)，有可能有其它線程已經(jīng)向fast bins中加入了新的空閑chunk，也有可能是所需的chunk屬于small bins，但通過前面的步驟都沒有分配到所需的chunk，由于分配small bin chunk時(shí)在前面的步驟都不會(huì)調(diào)用malloc_consolidate()函數(shù)將fast bins中的 chunk合并加入到unsorted bin中。所在這里如果fast bin中有chunk存在，調(diào)用malloc_consolidate()函數(shù)，并重新設(shè)置當(dāng)前bin的index。并轉(zhuǎn)到最外層的循環(huán)，嘗試重新分配small bin chunk或是large bin chunk。如果開啟了ATOMIC_FASTBINS優(yōu)化，有可能在由其它線程加入到fast bins中的chunk被合并后加入unsorted bin中，從unsorted bin中就可以分配出所需的large bin chunk了，所以對(duì)沒有成功分配的large bin chunk也需要重試。

#else
else if (have_fastchunks(av))
{
assert(in_smallbin_range(nb));
malloc_consolidate(av);
idx = smallbin_index(nb); /* restore original bin index */
}

如果top chunk也不能滿足要求，查看fast bins中是否有空閑chunk存在，如果fast bins中有空閑chunk存在，在沒有開啟ATOMIC_FASTBINS優(yōu)化的情況下，只有一種可能，那就是所需的chunk屬于small bins，但通過前面的步驟都沒有分配到所需的small bin chunk，由于分配small bin chunk時(shí)在前面的步驟都不會(huì)調(diào)用malloc_consolidate()函數(shù)將fast bins中的空閑chunk合并加入到unsorted bin中。所在這里如果fast bins中有空閑chunk存在，調(diào)用 malloc_consolidate()函數(shù)，并重新設(shè)置當(dāng)前bin的index。并轉(zhuǎn)到最外層的循環(huán)，嘗試重新分配small bin chunk。

else
{
void *p = sYSMALLOc(nb, av);
if (p != NULL && __builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}
}
}

山窮水盡了，只能想系統(tǒng)申請(qǐng)內(nèi)存了。sYSMALLOc()函數(shù)可能分配的chun 包括small bin chunk，large bin chunk 和large chunk。

check

1.fastbin頭部的chunk的idx與fastbin的idx要一致。2.unsorted bin中的chunk1大小不能小于等于2*SIZE_SZ，也不能超過該分配區(qū)總的內(nèi)存分配量。3.將chunk從unsorted bin取出放入small bin和large bin時(shí)用到了unlink()宏，注意繞過unlink()宏中的檢測(cè)。4.切出的remainder在重新放入unsorted bin時(shí)需要滿足 unsorted_chunks(av)->fd->bk = unsorted_chunks(av)。

總結(jié)

malloc分配步驟大致如下：1.檢查有沒有_malloc_hook，有則調(diào)用hook函數(shù)。2.獲得分配區(qū)的鎖，調(diào)用函數(shù)_int_malloc()分配內(nèi)存。3.如果申請(qǐng)大小在fast bin范圍內(nèi)，則從fast bin分配chunk，成功則返回用戶指針，否則進(jìn)行下一步。(當(dāng)對(duì)應(yīng)的bin為空時(shí)，就會(huì)跳過第5步操作) 4.如果申請(qǐng)大小在small bin范圍內(nèi)，則從small bin中分配chunk，成功則返回用戶指針，否則進(jìn)行下一步。5.調(diào)用malloc_consolidate()函數(shù)合并fast bin，并鏈接進(jìn)unsorted bin中。6.如果申請(qǐng)大小在small bin范圍內(nèi)，且此時(shí)unsorted bin只有一個(gè)chunk，并且這個(gè)chunk為last remainder chunk且大小夠大，則從這個(gè)chunk中切分出需要的大小，成功則返回用戶指針，否則進(jìn)行下一步。7.反向遍歷unsorted bin，如果當(dāng)前chunk與所需chunk大小一致，則分配，成功則返回用戶指針，否則將當(dāng)前chunk放入small bin或者large bin中合適的位置。8.使用最佳匹配算法在large bin中找到合適的chunk進(jìn)行分配，成功則返回用戶指針，否則進(jìn)行下一步。9.到了這一步，說明沒有大小正好合適的chunk，則看看比當(dāng)前bin的index大的small bin或者large bin中有沒有空閑chunk可用來分配。成功則返回用戶指針，否則進(jìn)行下一步。10.嘗試從top chunk中分配，成功則返回用戶指針，否則進(jìn)行下一步。11.如果fast bin中還有chunk，調(diào)用malloc_consolidate()回到第6步(因?yàn)榈?步對(duì)應(yīng)bin為空時(shí)會(huì)跳過第五步，而fast bin合并之后有可能出現(xiàn)能夠分配的small bin)。12.到了這步還不行，則調(diào)用sYSMALLOc()函數(shù)向系統(tǒng)申請(qǐng)內(nèi)存。

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請(qǐng)聯(lián)系本站處理。舉報(bào)投訴