glibc malloc 源碼分析
malloc
本文梳理了一下 malloc 跟 free 的源碼。malloc() 函數在源代碼中使用宏定義爲 public_mALLOc()。public_mALLOc() 函數只是簡單的封裝_int_malloc() 函數，_int_malloc() 函數纔是內存分配的核心實現。
public_mALLOc()
首先檢查是否存在__malloc_hook。如果存在，則調用 hook 函數。注意 hook 函數的傳參爲請求分配的內存大小。
arena_lookup(ar_ptr);
arena_lock(ar_ptr, bytes);
if(!ar_ptr)
return 0;
victim = _int_malloc(ar_ptr, bytes);獲取分配區指針，如果獲取分配區失敗，返回退出，否則，調用_int_malloc() 函數分配內存。
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() 函數分配內存失敗，並且使用的分配區不是主分配區，這種情況可能是 mmap 區域的內存被用光了。如果目前主分配區還可以從堆中分配內存，則需要再嘗試從主分配區中分配內存。首先釋放所使用分配區的鎖，然後獲得主分配區的鎖，並調用_int_malloc() 函數分配內存，最後釋放主分配區的鎖。
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() 函數分配內存失敗，並且使用的分配區是主分配區，查看是否有非主分配區，如果有，調用 arena_get2() 獲取分配區，然後對主分配區解鎖，如果 arena_get2() 返回一個非分配區，嘗試調用_int_malloc() 函數從該非主分配區分配內存，最後釋放該非主分配區的鎖。
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() 函數分配內存成功，釋放所使用的分配區的鎖。返回分配的 chunk。
_int_malloc
_int_malloc 函數是內存分配的核心，根據分配的內存塊的大小，該函數中實現了了四種分配內存的路徑。先給出_int_malloc() 函數的定義及臨時變量的定義：
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() 函數將需要分配的內存大小 bytes 轉換爲需要分配的 chunk 大小 nb，Ptmalloc 內部分配都是以 chunk 爲單位，根據 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. 根據所需的 chunk 大小獲得該 chunk 所屬的 fast bin 的 index，根據該 index 獲得所屬 fast bin 的空閒 chunk 鏈表頭指針。如果沒有開啓 ATOMIC_FASTBINS 優化，則按以下步驟：2. 將頭指針的下一個 chunk 作爲空閒 chunk 鏈表的頭部。3. 取出第一個 chunk，並調用 chunk2mem() 函數返回用戶所需的內存塊。如果開啓了 ATOMIC_FASTBINS 優化，則步驟與上述類似，只是在刪除 fastbin 頭節點的時候使用了 lock-free 技術，加快了分配速度。
check
fastbin 分配對 size 做了檢查，如果分配 chunk 的 size 不等於分配時的 idx，就會報錯。使用 chunksize() 和 fastbin_index 函數計算 chunk 的 size 大小，所以我們無需管 size 的後三位 (size_sz=8 的情況下無需管後四位)，只需保證前幾位與 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，則會執行如下步驟：1. 查找 chunk 對應 small bins 數組的 index，根據 index 獲得某個 small bin 的空閒 chunk 雙向循環鏈表表頭。2. 將最後一個 chunk 賦值給 victim，如果 victim 與表頭相同，表示該鏈表爲空，不能從 small bin 的空閒 chunk 鏈表中分配，這裏不做處理，等後面的步驟來處理。3.victim 與表頭不同有兩種情況。
-
victim 爲 0 1. 表示 small bin 還沒有初始化爲雙向循環鏈表，調用 malloc_consolidete() 函數將 fast bins 中的 chunk 合併。
-
victim 不爲 0 1. 設置 victim chunk 的 inuse 標誌，該標誌處於 vimctim chunk 的下一個相鄰 chunk 的 size 字段的第一個 bit。2. 做與 unlink 類似的操作將 chunk 從 small bin 中脫鏈。
- 判斷當前分配區是否屬於非主分配區，如果是，將 victim chunk 的 size 字段中的標誌非主分配區的標誌 bit 清零。5. 調用 chunk2mem() 函數獲得 chunk 的實際可用的內存指針，將該內存指針返回給應用層。
check
申請的 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 的範圍內，則
-
根據 chunk 的大小獲得對應 large bin 的 index
-
判斷當前分配區的 fast bins 中是否包含 chunk，如果存在，調用 malloc_consolidate() 函數合併 fast bins 中的 chunk，並將這些空閒 chunk 加入 unsorted bin 中。
下面的源代碼實現從 last remainder chunk，large bins 和 top chunk 中分配所需的 chunk，這裏包含了多個多層循環，在這些循環中，主要工作是分配前兩步都未分配成功的 small bin chunk、large bin chunk 和 large chunk。最外層的循環用於重新嘗試分配 small bin chunk，因爲如果在前一步分配 smallbin chunk 不成功，並沒有調用 malloc_consolidate() 函數合併 fast bins 中的 chunk，將空閒 chunk 加入 unsorted bin 中，如果第一嘗試從 last remainder chunk、top chunk 中分配 small bin chunk 都失敗以後，如果 fast bins 中存在空閒 chunk，會調用 malloc_consolidate() 函數，那麼在 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 的雙向鏈表，遍歷結束的條件是循環鏈表中只剩一個頭節點。
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);-
檢查當前遍歷的 chunk 是否合法，chunk 的大小不能小於等於 2*SIZE_SZ，也不能超過該分配區總的內存分配量。
-
獲取 chunk 的大小並賦值給 size。
if (in_smallbin_range(nb) &&
bck == unsorted_chunks(av) &&
victim == av->last_remainder &&
(unsigned long)(size) > (unsigned long)(nb + MINSIZE))
{如果需要分配一個 small bin chunk，並且 unsorted bin 中只有一個 chunk，並且這個 chunk 爲 last remainder chunk，並且這個 chunk 的大小大於所需 chunk 的大小加上 MINSIZE，在滿足這些條件的情況下，可以使用這個 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;
}-
從 chunk 中切分出所需大小的 chunk。
-
計算切分後剩下 chunk 的大小，將剩下的 chunk 加入 unsorted bin 的鏈表中，並將剩下的 chunk 作爲分配區的 last remainder chunk。
-
如果剩下的 chunk 屬於 large bin chunk，將該 chunk 的 fd_nextsize 和 bk_nextsize 設置爲 NULL，因爲這個 chunk 僅僅存在於 unsorted bin 中，並且 unsorted bin 中有且僅有這一個 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；
}設置分配出的 chunk 和 last remainder chunk 的相關信息。，調用 chunk2mem() 獲得 chunk 中可用的內存指針，返回給應用層，退出。
/* remove from unsorted list */
unsorted_chunks(av)->bk = bck;
bck->fd = unsorted_chunks(av);將雙向循環鏈表中的最後一個 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;
}如果當前 chunk 與所需的 chunk 大小一致 1. 設置當前 chunk 處於 inuse 狀態 2. 設置分配區標誌位 3. 調用 chunk2mem() 獲得 chunk 中的可用內存指針，返回給應用層。
/* place chunk in bin */
if (in_smallbin_range(size))
{
victim_index = smallbin_index(size);
bck = bin_at(av, victim_index);
fwd = bck->fd;
}如果當前 chunk 屬於 small bins，獲得當前 chunk 所屬 small bin 的 index，並將該 small bin 的鏈表表頭複製給 bck，第一個 chunk 賦值給 fwd，也就是當前的 chunk 會插入到 bck 和 fwd 之間，作爲 small bin 比鏈表的第一個 chunk。
else
{
victim_index = largebin_index(size);
bck = bin_at(av, victim_index);
fwd = bck->fd;如果當前 chunk 屬於 large bins，獲得當前 chunk 所屬 large bin 的 index，並將該 large bin 的鏈表表頭賦值給 bck，第一個 chunk 賦值給 fwd，也就是當前的 chunk 會插入到 bck 和 fwd 之間，作爲 large bin 鏈表的第一個 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 是按照大小排序的，需要將當前從 unsorted bin 中取出的 chunk 插入到 large bin 中合適的位置。將當前的 chunk 的 size 的 inuse 標誌 bit 置位，相當於加 1，便於加快 chunk 大小的比較，找到合適的地方插入當前 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;
}如果當前的 chunk 比 large bin 的最後一個 chunk 的大小還小，那麼當前 chunk1 就插入到 large bin 的鏈表的最後，作爲最後一個 chunk。可以看出 large bin 中的 chunk 是按照從大到小的順序排序的，同時一個 chunk 存在於兩個雙向循環鏈表中，一個鏈表包含了 large bin 中所有的 chunk，另一個鏈表爲 chunk size 鏈表，該鏈表從每個相同大小的 chunk 中取除第一個 chunk 按照大小順序鏈接在一起，便於一次跨域多個相同大小的 chunk 遍歷下一個不同大小的 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 鏈表，直到找到第一個 chunk 大小小於等於當前 chunk 大小的 chunk 退出循環。
if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;如果從 large bin 鏈表中找到了與當前 chunk 大小相同的 chunk，則統一大小的 chunk 已經存在，那麼 chunk size 一定包含了 fwd 指向的 chunk，爲了不久改 chunk size 鏈表，當前 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 鏈表中還沒有包含當前 chunk 大小的 chunk，也就是說當前 chunk 的大小大於 fwd 的大小，則將當前 chunk 作爲該 chunk size 的代表加入 chunk size 鏈表，chunk size 鏈表也是按照由大到小的順序排序。
bck = fwd->bk;
}
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}如果 large bin 鏈表中沒有 chunk，直接將當前 chunk 加入 chunk size 鏈表。
mark_bin(av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;將當前 chunk 插入到對應的空閒的 chunk 鏈表中，並將 large bin 所對應 binmap 的相應 bit 置位。
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break；
}如果 unsorted bin 中的 chunk 超過了 10000 個，最多遍歷一萬個就退出，避免長時間處理 unsorted bin 影響內存分配的效率。當 unsorted bin 中的空閒 chunk 加入到相應的 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，查詢對應的 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 鏈表，直到找到第一個大於等於所需 chunk 大小的 chunk 退出循環。
/* 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 不是鏈表中的最後一個 chunk，並且與 victim 大小相同的 chunk 不止一個，那麼意味着 victim 爲 chunk size 鏈表中的節點，爲了不調整 chunk size 鏈表，需要避免將 chunk size 鏈表中取出，所以取 victim->fd 節點對應的 chunk 作爲候選 chunk。由於 large bin 鏈表中的 chunk 也是按照大小排序，同一大小的 chunk 有多個時，這些 chunk 必定排在一起，所以 victim->fd 節點對應的 chunk 的大小必定與 victim 的大小一樣。
remainder_size = size - nb;
unlink(victim, bck, fwd);計算將 victim 切分後剩餘大小，並調用 unlink() 宏函數將 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，則將整個 victim 分配給應用層，設置 victim 的 inuse 標誌，inuse 標誌位於下一個相鄰的 chunk 的 size 字段中。如果當前分配區不是主分配區，將 victim 的 size 字段中的非主分配區標誌置位。
/* 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，剩餘部分作爲一個新的 chunk 加入到 unsorted bin 中。如果剩餘部分 chunk 屬於 large bins，將剩餘部分 chunk 的 chunk size 鏈表指針設置爲 NULL，因爲 unsorted bin 中的 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);
}設置 victim 和 remainder 的狀態，由於 remainder 爲空閒 chunk，所以需要設置該 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，調用 chunk2mem() 獲得 chunk 中可用的內存指針，返回給應用層，退出。如果通過上面的方式從最合適的 small bin 或 large bin 中都沒有分配到需要的 chunk，則查看比當前 bin 的 index 大的 small bin 或 large bin 是否有空閒 chunk 可利用來分配所需的 chunk。源代碼實現如下：
++idx;
bin = bin_at(av,idx);
block = idx2block(idx);
map = av->binmap[block];
bit = idx2bit(idx);獲取下一個相鄰 bin 的空閒 chunk 鏈表，並獲取該 bin 對於 binmap 中的 bit 位的值。Binmap 中的標識了相應的 bin 中是否有空閒 chunk 存在。Binmap 按 block 管理，每個 block 爲一個 int，共 32 個 bit，可以表示 32 個 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 指定的位設置爲 1，其它位清零，map 表示一個 block 值，如果 bit 大於 map，意味着 map 爲 0，該 block 所對應的所有 bins 中都沒有空閒 chunk，於是遍歷 binmap 的下一個 block，直到找到一個不爲 0 的 block 或者遍歷完所有的 block。退出循環遍歷後，設置 bin 指向 block 的第一個 bit 對應的 bin，並將 bit 置爲 1，表示該 block 中 bit 1 對應的 bin，這個 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);在一個 block 遍歷對應的 bin，直到找到一個 bit 不爲 0 退出遍歷，則該 bit 對於的 bin 中有空閒 chunk 存在。將 bin 鏈表中的最後一個 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 中的相應位設置不準確，將 binmap 的相應 bit 位清零，獲取當前 bin 下一個 bin，將 bit 移到下一個 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);當前 bin 中的最後一個 chunk 滿足要求，獲取該 chunk 的大小，計算切分出所需 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，將整個 chunk 分配給應用層 (代碼在後面)，設置 victim 的狀態爲 inuse，如果當前分配區爲非分配區，設置 victim 的非主分配區標誌位。
/* 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;
}從 victim 中切分出所需的 chunk，剩餘部分作爲一個新的 chunk 加入到 unsorted bin 中。如果剩餘部分 chunk 屬於 large bins，將剩餘部分 chunk 的 chunk size 鏈表指針設置爲 NULL，因爲 unsorted bin 中的 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);
}設置 victim 和 remainder 的狀態，由於 remainder 爲空閒 chunk，所以需要設置該 chunk 的 foot。
check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
if (__builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}
}調用 chunk2mem() 獲得 chunk 中可用的內存指針，返回給應用層，退出。如果從所有的 bins 中都沒有獲得所需的 chunk，可能的情況爲 bins 中沒有空閒 chunk，或者所需的 chunk 大小很大，下一步將嘗試從 top chunk 中分配所需 chunk。源代碼實現如下：
use_top:
victim = av->top;
size = chunksize(victim);將當前分配區的 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 這個條件，才能從 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 優化情況下，free 屬於 fast bins 的 chunk 時不需要獲得分配區的鎖，所以在調用_int_malloc() 函數時，有可能有其它線程已經向 fast bins 中加入了新的空閒 chunk，也有可能是所需的 chunk 屬於 small bins，但通過前面的步驟都沒有分配到所需的 chunk，由於分配 small bin chunk 時在前面的步驟都不會調用 malloc_consolidate() 函數將 fast bins 中的 chunk 合併加入到 unsorted bin 中。所在這裏如果 fast bin 中有 chunk 存在，調用 malloc_consolidate() 函數，並重新設置當前 bin 的 index。並轉到最外層的循環，嘗試重新分配 small bin chunk 或是 large bin chunk。如果開啓了 ATOMIC_FASTBINS 優化，有可能在由其它線程加入到 fast bins 中的 chunk 被合併後加入 unsorted bin 中，從 unsorted bin 中就可以分配出所需的 large bin chunk 了，所以對沒有成功分配的 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 優化的情況下，只有一種可能，那就是所需的 chunk 屬於 small bins，但通過前面的步驟都沒有分配到所需的 small bin chunk，由於分配 small bin chunk 時在前面的步驟都不會調用 malloc_consolidate() 函數將 fast bins 中的空閒 chunk 合併加入到 unsorted bin 中。所在這裏如果 fast bins 中有空閒 chunk 存在，調用 malloc_consolidate() 函數，並重新設置當前 bin 的 index。並轉到最外層的循環，嘗試重新分配 small bin chunk。
else
{
void *p = sYSMALLOc(nb, av);
if (p != NULL && __builtin_expect (perturb_byte, 0))
alloc_perturb (p, bytes);
return p;
}
}
}山窮水盡了，只能想系統申請內存了。sYSMALLOc() 函數可能分配的 chun 包括 small bin chunk，large bin chunk 和 large chunk。
check
1.fastbin 頭部的 chunk 的 idx 與 fastbin 的 idx 要一致。2.unsorted bin 中的 chunk1 大小不能小於等於 2*SIZE_SZ，也不能超過該分配區總的內存分配量。3. 將 chunk 從 unsorted bin 取出放入 small bin 和 large bin 時用到了 unlink() 宏，注意繞過 unlink() 宏中的檢測。4. 切出的 remainder 在重新放入 unsorted bin 時需要滿足 unsorted_chunks(av)->fd->bk = unsorted_chunks(av)。
總結
malloc 分配步驟大致如下：1. 檢查有沒有_malloc_hook，有則調用 hook 函數。2. 獲得分配區的鎖，調用函數_int_malloc()分配內存。3. 如果申請大小在 fast bin 範圍內，則從 fast bin 分配 chunk，成功則返回用戶指針，否則進行下一步。(當對應的 bin 爲空時，就會跳過第 5 步操作) 4. 如果申請大小在 small bin 範圍內，則從 small bin 中分配 chunk，成功則返回用戶指針，否則進行下一步。5. 調用 malloc_consolidate()函數合併 fast bin，並鏈接進 unsorted bin 中。6. 如果申請大小在 small bin 範圍內，且此時 unsorted bin 只有一個 chunk，並且這個 chunk 爲 last remainder chunk 且大小夠大，則從這個 chunk 中切分出需要的大小，成功則返回用戶指針，否則進行下一步。7. 反向遍歷 unsorted bin，如果當前 chunk 與所需 chunk 大小一致，則分配，成功則返回用戶指針，否則將當前 chunk 放入 small bin 或者 large bin 中合適的位置。8. 使用最佳匹配算法在 large bin 中找到合適的 chunk 進行分配，成功則返回用戶指針，否則進行下一步。9. 到了這一步，說明沒有大小正好合適的 chunk，則看看比當前 bin 的 index 大的 small bin 或者 large bin 中有沒有空閒 chunk 可用來分配。成功則返回用戶指針，否則進行下一步。10. 嘗試從 top chunk 中分配，成功則返回用戶指針，否則進行下一步。11. 如果 fast bin 中還有 chunk，調用 malloc_consolidate()回到第 6 步 (因爲第 3 步對應 bin 爲空時會跳過第五步，而 fast bin 合併之後有可能出現能夠分配的 small bin)。12. 到了這步還不行，則調用 sYSMALLOc() 函數向系統申請內存。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/sWgIHELIOifN0Az-iEMK4w