glibc2.35-malloc源码分析
malloc源码分析
本文主要分析glibc-2.35中malloc的流程逻辑,并且对流程中一些重要的函数会单独进行讲解
__libc_malloc
malloc函数实际调用到的是__libc_malloc ,而__libc_malloc 实际只实现了从 tcache bin 分配的功能,如果tcache bin中没有满足的chunk,则还需调用_int_malloc函数来进行分配
void *
__libc_malloc (size_t bytes)
{
mstate ar_ptr;
void *victim;
_Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2,
"PTRDIFF_MAX is not more than half of SIZE_MAX");
if (!__malloc_initialized) // 检查 malloc 是否初始化
ptmalloc_init (); // 没有初始化先进行初始化
#if USE_TCACHE //条件编译,如果开启了tcache bin 就优先从tcache bin中取
/* int_free also calls request2size, be careful to not pad twice. */
size_t tbytes;
if (!checked_request2size (bytes, &tbytes)) // 检查申请大小,将其转为实际的size大小,并写入arg2
{ // 实际size就是申请的 size 加上 0x10 的chunk头
__set_errno (ENOMEM);
return NULL;
}
size_t tc_idx = csize2tidx (tbytes);//将大小转化为对应tcachebin的下标
//比如0x20变成3,0x28也是3,而0x29就是4,0x30也是4
MAYBE_INIT_TCACHE (); // 检查是否 tcache bin 是否初始化,并自动初始化
DIAG_PUSH_NEEDS_COMMENT;
if (tc_idx < mp_.tcache_bins // 申请的大小是否在tcache bin 的范围内
&& tcache // tcache bin是否已经初始化
&& tcache->counts[tc_idx] > 0) // 检查tcache bin中是否有chunk可以返回,有就直接取出然后返回
{
victim = tcache_get (tc_idx); // 从tcache bin取出 chunk
return tag_new_usable (victim); // 处理内存标签确保内存安全
}
DIAG_POP_NEEDS_COMMENT;
#endif
if (SINGLE_THREAD_P) // 如果程序是单线程的,就不需要获取私有的main_arena
{ // 直接这里进入 _int_malloc
victim = tag_new_usable (_int_malloc (&main_arena, bytes));
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
&main_arena == arena_for_chunk (mem2chunk (victim))); //检查 chunk 所属arena == main_arena
return victim;
}
arena_get (ar_ptr, bytes); // 获取私有的 arena,并上锁
victim = _int_malloc (ar_ptr, bytes); // 进入 _int_malloc 分配
/* Retry with another arena only if we were able to find a usable arena
before. */
if (!victim && ar_ptr != NULL) // 如果分配不到chunk,并且获取不到main_arena,就再重试一次
{
LIBC_PROBE (memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}
if (ar_ptr != NULL) // 如果前面获取到了 arena,则现在给 arena解锁
__libc_lock_unlock (ar_ptr->mutex);
victim = tag_new_usable (victim);
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
ar_ptr == arena_for_chunk (mem2chunk (victim)));
return victim;
}
libc_hidden_def (__libc_malloc)总结:这个函数实现了从tcache bin中分配的功能,如果tcache bin 未开启或无满足条件的chunk,就获取当前线程的 arena 调用_int_malloc进行分配
_int_malloc
我们都知道arena 中的bin(除了fastbin以外),每个bin都是一个双向链表的节点,为了简化链表的管理,ptmalloc中将每个bin都看做是一个chunk来管理,每个bin中fd和bk都可以对应到chunk中fd和bk,fastbin也是同理只是fastbin没有使用到bk
typedef struct malloc_chunk *mbinptr;
typedef struct malloc_chunk * mfastbinptr;因此在 bin 中的 free Chunk 指向的不是 bins 数组真实的物理首地址,而是bins的fd减去0x10 的虚拟的 chunk 头地址
static void *
_int_malloc (mstate av, size_t bytes)
{
INTERNAL_SIZE_T nb; /* 标准化的请求大小 */
unsigned int idx; /* 相关的 bin 的idx */
mbinptr bin; /* 相关的 bin */
mchunkptr victim; /* 正在检查或被选中的 chunk */
INTERNAL_SIZE_T size; /* victim chunk 的大小 */
int victim_index; /* victim 所属的 bin 索引 */
mchunkptr remainder; /* 分割后剩余的部分(chunk) */
unsigned long remainder_size; /* 剩余部分的大小 */
unsigned int block; /* 位图遍历器(用于定位 block/数组下标) */
unsigned int bit; /* 位图遍历器(用于定位 bit/位) */
unsigned int map; /* binmap 中当前遍历到的字(数值) */
mchunkptr fwd; /* 用于链表操作的临时变量(前向指针) */
mchunkptr bck; /* 用于链表操作的临时变量(后向指针) */
#if USE_TCACHE
size_t tcache_unsorted_count; /* 统计已处理并放入 Tcache 的 Unsorted Chunks 数量 */
#endif
/*
将请求的大小转换为内部形式,具体做法是加上 SIZE_SZ 字节的开销(即 Chunk 头部的 size 字段大小), 并可能需要加上更多字节以满足必要的对齐要求,和/或确保大小至少达到 MINSIZE(即最小可分配大小)。
此外,如果请求的大小过大,导致在进行填充和对齐操作后发生溢出(即数值绕回 0)
checked_request2size 函数将返回 false
*/
if (!checked_request2size (bytes, &nb))
{
__set_errno (ENOMEM);
return NULL;
}
/* 如果没有arena,就调用 sysmalloc获得一块mmap的chunk */
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes); // 辅助调试用的,默认不开启不用管
return p;
}
/*
如果(请求的)大小符合 fastbin 的范围,首先检查对应的 bin。
即使 av(分配区结构体)尚未初始化,执行这段代码也是安全的,
因此我们可以不经检查直接尝试,从而在这一快速路径上节省一些时间。
*/
#define REMOVE_FB(fb, victim, pp) \
do \
{ \
victim = pp; \
if (victim == NULL) \
break; \
pp = REVEAL_PTR (victim->fd); \
if (__glibc_unlikely (pp != NULL && misaligned_chunk (pp))) \
malloc_printerr ("malloc(): unaligned fastbin chunk detected"); \
} \
while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
!= victim); // 原子交换比较,如果 *fb != victim(旧头)说明发生了抢占
// 将 *fb 的值赋给 pp 并重新循环
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
// 比较是否满足fastbin的大小(<= 0x80)如果满足的话先走fastbin分配
{
idx = fastbin_index (nb); // 获取申请大小在 fastbin中对应的idx
mfastbinptr *fb = &fastbin (av, idx); // 获取 fastbin
mchunkptr pp;
victim = *fb; //获取fastbin中的第一个chunk
if (victim != NULL)
{
if (__glibc_unlikely (misaligned_chunk (victim)))
malloc_printerr ("malloc(): unaligned fastbin chunk detected 2");
if (SINGLE_THREAD_P) // 根据是否为单线程,走不同的路径
*fb = REVEAL_PTR (victim->fd); //拿走fastbin中victim 并将其的fd解密后放回fastbin中
else
REMOVE_FB (fb, pp, victim); // 多了CAS处理多线程下的竞争情况,除此之外功能与上面一样
if (__glibc_likely (victim != NULL)) //再次检查 victim 不为 0
{
size_t victim_idx = fastbin_index (chunksize (victim));
if (__builtin_expect (victim_idx != idx, 0)) // 检查victim的大小对应的idx
malloc_printerr ("malloc(): memory corruption (fast)"); //与其所在的idx是否一致
check_remalloced_chunk (av, victim, nb);
#if USE_TCACHE
/* 尝试把 fastbin 中chunk放入到tcache bin中 */
size_t tc_idx = csize2tidx (nb);
if (tcache && tc_idx < mp_.tcache_bins)
{
mchunkptr tc_victim;
/* 当tcache bin 未满并且 fastbin还有chunk时,循环将fastbin中的chunk放到tcache bin中 */
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = *fb) != NULL)
{ // 与上面从 fastbin 中取chunk 一样
if (__glibc_unlikely (misaligned_chunk (tc_victim)))
malloc_printerr ("malloc(): unaligned fastbin chunk detected 3");
if (SINGLE_THREAD_P)
*fb = REVEAL_PTR (tc_victim->fd);
else
{
REMOVE_FB (fb, pp, tc_victim);
if (__glibc_unlikely (tc_victim == NULL))
break;
}
tcache_put (tc_victim, tc_idx); // 将取出的chunk 放入tcache bin中
}
}
#endif
void *p = chunk2mem (victim);
alloc_perturb (p, bytes); // 辅助调试用的,默认不开启不用管
return p;
}
}
}
/*
如果是小内存请求,检查常规 bin(即 smallbin)。
由于这些 'smallbins' 中的每一个都只存放一种固定大小的块,因此不需要在 bin 内部进行遍历搜索。
(对于大内存请求,我们需要等待 unsorted chunks 被处理(整理)完,才能找到最佳匹配(best fit)。
但对于小请求来说,反正匹配都是精确大小的,所以我们可以现在立刻检查,这样速度更快。)”
*/
if (in_smallbin_range (nb)) //是否满足small bin的大小 (<= 0x3ff),满足的话走small bin分配
{
idx = smallbin_index (nb); // 获取对应大小的 smallbin的 idx
bin = bin_at (av, idx); // 获取对应大小的small bin
if ((victim = last (bin)) != bin) // 通过比较bin中的fd与bk是否相等,来判断bin是否为空
{ // 这里我们可以看出small bin是从链表尾部开始查找的
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim)) // 安全性检查 victim->bk->fd == victim
malloc_printerr ("malloc(): smallbin double linked list corrupted");
set_inuse_bit_at_offset (victim, nb);
bin->bk = bck; // 取走victim后,将bck与bins进行链接
bck->fd = bin;
if (av != &main_arena)
set_non_main_arena (victim);
check_malloced_chunk (av, victim, nb);
#if USE_TCACHE
/* 尝试把 small bin 中的chunk放入到tcache bin中,与fastbin同理*/
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;
}
}
/*
如果这是一个大内存请求,在继续后续步骤之前,先整理(合并)fastbins。
虽然在确认是否有可用空间之前就清空所有 fastbins 看起来有些‘过度’(或是多此一举),
但这避免了通常与 fastbins 相关的内存碎片问题。
此外,在实际运行中,程序往往倾向于连续发起小额请求或连续发起大额请求,而混合交替的情况较少
因此在大多数程序中,这种合并操作并不会被频繁触发。
而对于那些确实频繁触发该操作的程序,它们本身往往就倾向于产生严重的内存碎片。
*/
else
{
idx = largebin_index (nb);
if (atomic_load_relaxed (&av->have_fastchunks))
malloc_consolidate (av); // 合并 chunk 此函数比较重要会下面详细分析
}
/*
处理最近释放的或切割剩余的 chunks。只有在以下情况才直接选用该 chunk:
1、它的大小与请求精确匹配(exact fit);
2、或者,如果这是一个小内存请求(small request),且该 chunk 是最近一次非精确匹配分割后产生的剩 余块。
将其他遍历到的 chunks 放入其对应的 bin 中。请注意,这一步是所有流程中唯一会将 chunks 放回 bin (指 Small/Large Bins)的地方。
这里之所以需要外层循环,是因为我们可能直到 malloc 流程快结束时,才意识到本应该先进行碎片整理(合 并),因此必须执行合并操作并重试。这种情况最多发生一次,且仅在我们需要通过扩展内存(如使用 Top Chunk)来满足一个‘小’内存请求时才会触发
*/
// 为后续将遍历到的 unsorted bin 放入到 tcache bin中
#if USE_TCACHE
INTERNAL_SIZE_T tcache_nb = 0;
size_t tc_idx = csize2tidx (nb);
if (tcache && tc_idx < mp_.tcache_bins)
tcache_nb = nb;
int return_cached = 0; // 标志位,如果成功放入tcache中,后续直接从tcache里取一块给用户
tcache_unsorted_count = 0; // 计数器,统计放入tcache 的堆块的数量
#endif
for (;; )
{
int iters = 0;
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{ // 这里可以看到 unsorted bin 与 small bin 一样是从 bin->bk 开始向后遍历
bck = victim->bk;
size = chunksize (victim);
mchunkptr next = chunk_at_offset (victim, size); //获取victim地址上的下一个chunk
if (__glibc_unlikely (size <= CHUNK_HDR_SZ) // 检查取出来的 victim 的size
|| __glibc_unlikely (size > av->system_mem))
malloc_printerr ("malloc(): invalid size (unsorted)");
if (__glibc_unlikely (chunksize_nomask (next) < CHUNK_HDR_SZ) //检查next的size合法性
|| __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
malloc_printerr ("malloc(): invalid next size (unsorted)");
if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size)) //检查prev_size
malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
if (__glibc_unlikely (bck->fd != victim) // bck 的 fd 一定等于 victim
|| __glibc_unlikely (victim->fd != unsorted_chunks (av)))//victim->fd一定等于bin
malloc_printerr ("malloc(): unsorted double linked list corrupted");
if (__glibc_unlikely (prev_inuse (next))) // 检查prev_inuse位
malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");
/*
如果是小内存请求(small request),且 Unsorted Bin 中仅有一个且刚刚被切割过的 chunk,
那么尝试直接使用它。
这有助于提升连续的一系列小内存请求的空间局部性
这是对‘最佳匹配’策略的唯一例外,且仅在小内存请求无法找到大小精确匹配的块时才会应用
*/
if (in_smallbin_range (nb) && // 是否为小内存请求
bck == unsorted_chunks (av) && // unsorted bin中是否只有一个 chunk
victim == av->last_remainder && // 这个chunk是否刚刚被切割过
(unsigned long) (size) > (unsigned long) (nb + MINSIZE)) // chunk大小是否满足
{
/* 分割 chunk 并将剩余部分重新接入链表 */
remainder_size = size - nb; // 切割后的 size
remainder = chunk_at_offset (victim, nb); // 切割后 chunk 地址
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder; // 链接 chunk
av->last_remainder = remainder; // 更新arena中的 last_remainder
remainder->bk = remainder->fd = unsorted_chunks (av); // 链接到 unsorted bin
if (!in_smallbin_range (remainder_size)) // 这里置零是为了防止在后面unlink时误判
{ // 以为是large bin中的unlink导致崩溃
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head (victim, nb | PREV_INUSE | // 设置 victim chunk的chunk 头
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE); // 设置remainder的chunk头
set_foot (remainder, remainder_size); // 设置 remainder的next的 prev_size
check_malloced_chunk (av, victim, nb); // 对 victim chunk做检查
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
/* 从 unsorted bin 中移除 */
if (__glibc_unlikely (bck->fd != victim)) // bck 的 fd 一定等于 victim
malloc_printerr ("malloc(): corrupted unsorted chunks 3");
unsorted_chunks (av)->bk = bck; // 这两步就是将 victim 移出 bin,并将victim->bk接入
bck->fd = unsorted_chunks (av);
/* 如果精准匹配就直接取出 */
if (size == nb)
{
set_inuse_bit_at_offset (victim, size); // 被取出的话就不是free状态了,设置inuse位
if (av != &main_arena)
set_non_main_arena (victim);
#if USE_TCACHE
/* 先放入 tcache bin */
if (tcache_nb
&& tcache->counts[tc_idx] < mp_.tcache_count)
{
tcache_put (victim, tc_idx);
return_cached = 1;
continue;
}
else
{
#endif //当tcache bin满了,大小不合适或者没有开启 tcache时,直接返回给 user
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
#if USE_TCACHE
}
#endif
}
/* 将chunk放入bin中 */
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
/* 保持 large bins 处于有序状态 */
if (fwd != bck)
{
/* 将大小与 PREV_INUSE 位进行“或”运算,以加速比较 */
size |= PREV_INUSE;
/* 如果比 bin 里最小的还要小,则跳过下面的搜索循环(Large Bin是按从大到小排序) */
assert (chunk_main_arena (bck->bk));
if ((unsigned long) (size)
< (unsigned long) chunksize_nomask (bck->bk))
{
fwd = bck; // fwd变成了bin头
bck = bck->bk; // bck变成原来的最小块
victim->fd_nextsize = fwd->fd; // fwd->fd 是链表头(最大的块)
victim->bk_nextsize = fwd->fd->bk_nextsize; // 指向原来的最小块
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
} // 最大块的 bk_nextsize和原来最小块的 fd_nextsize指向 victim
else
{
assert (chunk_main_arena (fwd));
while ((unsigned long) size < chunksize_nomask (fwd))
{
fwd = fwd->fd_nextsize; // 利用fd_nextsize进行跳跃式搜索
assert (chunk_main_arena (fwd));
}
if ((unsigned long) size
== (unsigned long) chunksize_nomask (fwd)) //如果插入点与victim大小正好相等
/* 始终插入到第二个位置(这样就不用修改其他chunk上的nextsize) */
fwd = fwd->fd;
else // 新的大小插入点
{ //链接 nextsize 指针
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
fwd->bk_nextsize = victim; // 双向绑定
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
if (bck->fd != fwd)
malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
}
}
else // large bin为空的情况
victim->fd_nextsize = victim->bk_nextsize = victim;
}
// 前面的逻辑是维护nextsize指针,下面是维护fd和bk指针
mark_bin (av, victim_index); // 标记 binmap
victim->bk = bck; // 将victim接入双向链表
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
#if USE_TCACHE
/* 如果在填充缓存 tcache 的过程中,我们要处理的 chunk 数量已经达到了允许的上限,
那么停止遍历,直接从缓存中取出一个返回给用户 */
++tcache_unsorted_count;
if (return_cached
&& mp_.tcache_unsorted_limit > 0
&& tcache_unsorted_count > mp_.tcache_unsorted_limit)
{
return tcache_get (tc_idx);
}
#endif
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS) // 如果达到最大遍历数了,停止遍历
break;
}
#if USE_TCACHE
/* 如果我们找到的所有小块最终都被放入了缓存(Tcache)中,那么现在就从缓存中取出一个返回 */
if (return_cached)
{
return tcache_get (tc_idx);
}
#endif
/*
如果是大内存请求,则按有序顺序扫描当前 bin 中的 chunks,以寻找能满足要求的最小 chunk
使用跳表(skip list)来执行此操作
*/
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx); // 获取 large bin
/* 如果large bin是空的,或者里面最大的chunk小于victim就跳过搜索 */
if ((victim = first (bin)) != bin
&& (unsigned long) chunksize_nomask (victim) // 从large bin的fd也就最大的chunk开始找
>= (unsigned long) (nb)) // 直到找到满足要求的最小 chunk
{
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb))) // 使用 bk_nextsize 由大到小进行跳跃搜索
victim = victim->bk_nextsize;
/* 避免移除同种大小chunk中的第一个条目
这样就不需要重新修改跳表指针。*/
if (victim != last (bin)
&& chunksize_nomask (victim)
== chunksize_nomask (victim->fd))
victim = victim->fd; // 选用victim->fd作为victim
remainder_size = size - nb;
unlink_chunk (av, victim); // 将 victim unlink,这是个关键的函数下面会重点讲
/* 耗尽 */
if (remainder_size < MINSIZE) //剩下的size小于0x20,就把多余的也给user
{
set_inuse_bit_at_offset (victim, size); // 设置地址相邻的next的prev_use位
if (av != &main_arena)
set_non_main_arena (victim);
}
/* 切割 */
else // 切完后剩下的chunk会放入 unsorted bin
{
remainder = chunk_at_offset (victim, nb); // 获取到remainder的内存地址
/* 我们不能假设unsorted list是空的,
因此必须在这里执行一次完整的插入操作 */
bck = unsorted_chunks (av); // 获取unsorted bin
fwd = bck->fd; // 获取unsorted bin中第一个chunk
if (__glibc_unlikely (fwd->bk != bck)) // 检查
malloc_printerr ("malloc(): corrupted unsorted chunks");
remainder->bk = bck; // 这四个操作就是将remainder链接到unsorted bin中
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
if (!in_smallbin_range (remainder_size)) // 同上为了防止unlink误判
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head (victim, nb | PREV_INUSE | // 设置chunk头和prev_size,然后返回
(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;
}
}
/*
通过扫描 bins 来搜寻 chunk,从(比当前请求大小)更大一级的 bin 开始。
这种搜索严格遵循‘最佳匹配(best-fit)’原则;即,选择能够满足要求且大小最小的那个 chunk
(如果有多个大小相同的 chunk,则倾向于选择大约最久未被使用的那个)。
使用位图(bitmap)避免了去检查大多数为空的 bin。
特别是在程序的‘预热’阶段(warm-up phases),此时尚未有 chunk 被释放归还,(利用位图)跳过 所有 bin 的操作实际上比看起来要快得多
*/
++idx;
bin = bin_at (av, idx);
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);
for (;; )
{
/* 如果当前 block 中没有更多被置为 1 的位,则跳过此block,直接开始遍历后面的block */
if (bit > map || bit == 0)
{
do
{
if (++block >= BINMAPSIZE) /* 超出bins范围 */
goto use_top; /* 遍历完了都没找到,就只能用top chunk分配 */
}
while ((map = av->binmap[block]) == 0);
bin = bin_at (av, (block << BINMAPSHIFT)); // 获取block的起始bin
bit = 1; // 重置bit掩码,准备从该block的第0位开始寻找
}
/* 推进到 bit 被置为 1 的那个 bin。肯定能找到一个(因为 map != 0) */
while ((bit & map) == 0)
{
bin = next_bin (bin);
bit <<= 1;
assert (bit != 0);
}
/* 检查取出来的bin,他很可能不是空的bin */
victim = last (bin);
/* 如果是假的(bin为空),就清空这个bin的bit位 */
if (victim == bin)
{
av->binmap[block] = map &= ~bit; /* Write through */
bin = next_bin (bin); // 既然是空,那就继续找下一个bin
bit <<= 1; // 掩码继续左移
}
else
{
size = chunksize (victim);
/* 找到的第一个 chunk 肯定比 nb 大 */
assert ((unsigned long) (size) >= (unsigned long) (nb));
// 接下来的操作跟large bin 中的切割操作差不多了
remainder_size = size - nb;
/* unlink */
unlink_chunk (av, victim);
/* 耗尽 */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
}
/* 切割 */
else // 走到此分支说明从bin中找到了合适的chunk
{
remainder = chunk_at_offset (victim, nb);
/* 我们不能假设unsorted bin是空的,
因此我们必须在这里执行一次完全的插入 */
bck = unsorted_chunks (av); // 获取unsorted bin
fwd = bck->fd; // 获取原来unsorted bin中的chunk(假设unsorted bin是非空的)
if (__glibc_unlikely (fwd->bk != bck))
malloc_printerr ("malloc(): corrupted unsorted chunks 2");
remainder->bk = bck; // 经典的四步操作将remainder链接到unsorted bin中
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
/* 更新为 last remainder */
/* 此外这里也可以看出arena中last remainder,只能是unsorted bin中chunk */
if (in_smallbin_range (nb))
av->last_remainder = remainder; // 更新arena中的last_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;
}
}
use_top:
/*
如果(Top Chunk)足够大,就从这个位于内存末端的 chunk(保存在 av->top 中)分割出一部分。
请注意,这实际上是符合‘最佳匹配(best-fit)’搜索规则的。
实际上,av->top 被视为比任何其他可用的 chunk 都要大(因此匹配度也最低/最不适合)
因为它的大小可以根据需要无限扩展(直到达到系统的限制)。
我们要求 av->top 在初始化后必须始终存在(即其大小至少为 MINSIZE)。
如果当前请求会导致 Top Chunk 被完全耗尽,我们就会对其进行补充(调用系统调用扩展堆内存)。
(确保它存在的首要原因是,我们在调用 sysmalloc 扩展内存时,可能需要 MINSIZE 大小的空间来放 置‘栅栏桩/哨兵块’(fenceposts)以维持内存结构。)
*/
victim = av->top; // 获取top chunk
size = chunksize (victim);
if (__glibc_unlikely (size > av->system_mem))
malloc_printerr ("malloc(): corrupted top size");
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{ // 如果top chunk 的大小满足要求就割一块给用户,切割的逻辑和之前差不多
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder; // 更新 top chunk
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 chunks 时,对于所有大小的请求,代码执行流都可能到达此处 */
else if (atomic_load_relaxed (&av->have_fastchunks)) // 检查fastbin是否为空
{
malloc_consolidate (av); // 有可能其他线程又释放了chunk到fastbin,因此将他们合并起来
/* restore original bin index */
if (in_smallbin_range (nb)) // 重新计算idx,然后程序跳回到214行处再次循环
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}
/*
否则转交(给 sysmalloc)去处理与系统底层相关的分配情况
*/
else
{
void *p = sysmalloc (nb, av); // top chunk不够用,sysmalloc调用sbrk分配新的top chunk
if (p != NULL) // 如果申请大小达到阈值,就直接用mmap分配不拓展top chunk
alloc_perturb (p, bytes);
return p;
}
}
}总结:该函数是最核心的malloc分配逻辑,大体流程为 fastbin查找,small bin查找,unsorted bin查找,large bin 查找,然后就是再所有bin中寻找能够满足要求且大小最小的chunk进行切割,最后如果全部bin都没有满足要求的才从top chunk进行切割
tcache_put
这个函数实现了将chunk放入指定 tcache bin 中,其中涉及fd指针加密以及 tcache bin的double free检测机制,比较关键。
typedef struct tcache_entry
{
struct tcache_entry *next;
/* This field exists to detect double frees. */
uintptr_t key;
} tcache_entry;
// 这里的加密机制是将存放fd的地址右移12位也就是 (&fd >> 12),然后再与fd指针异或,就得到了加密后的指针
// 解密就是再进行一次加密操作就好了
#define PROTECT_PTR(pos, ptr) \
((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
tcache_entry *e = (tcache_entry *) chunk2mem (chunk); // chunk地址转为meta data的地址
// 并且强转为 tcache_entry 结构体
/* 通过设置chunk的key(也就是bk字段),将chunk标记为已经free状态
在free的时候可以通过这个检测double free。 */
e->key = tcache_key;
/* 将tcache bin中原本的chunk地址加密并接到 e 的next字段中 */
e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
tcache->entries[tc_idx] = e; // 将新的chunk放到 tcache bin的头
++(tcache->counts[tc_idx]);
}unlink_chunk
这个函数作用顾名思义就是将chunk unlink,其内部会自动判断chunk是否在 large bin中,并进行专门的设置
static void
unlink_chunk (mstate av, mchunkptr p)
{
if (chunksize (p) != prev_size (next_chunk (p))) //检查unlink chunk(也就是p)的size是否合法
malloc_printerr ("corrupted size vs. prev_size");
mchunkptr fd = p->fd; // 获取 fd
mchunkptr bk = p->bk; // 获取 bk
if (__builtin_expect (fd->bk != p || bk->fd != p, 0)) // 双向链表的检查fd->bk 和 bk->fd都等于p
malloc_printerr ("corrupted double-linked list");
// 进行 unlink 操作
fd->bk = bk;
bk->fd = fd;
if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL)
{ // 检查是否是 Large Bin 中某个大小组的“头节点”(只有头节点才有 nextsize 指针
if (p->fd_nextsize->bk_nextsize != p // 同上一样的检查,只不过换成了nextsize指针
|| p->bk_nextsize->fd_nextsize != p)
malloc_printerr ("corrupted double-linked list (not small)");
if (fd->fd_nextsize == NULL) // 检查 p->fd 是否不是头节点
{
if (p->fd_nextsize == p) // 判断 Large Bin 中是否只有p这一种大小的 chunk
fd->fd_nextsize = fd->bk_nextsize = fd;
else //将p->fd链接到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从nextsize指针中移除
p->fd_nextsize->bk_nextsize = p->bk_nextsize;
p->bk_nextsize->fd_nextsize = p->fd_nextsize;
}
}
}malloc_consolidate
这个函数实现了合并fastbin中每一个chunk的功能,要么就是放入unsorted bin要么就是和top chunk合并
static void malloc_consolidate(mstate av)
{
mfastbinptr* fb; /* 当前被合并的fastbin */
mfastbinptr* maxfb; /* 最后一个 fastbin 指针(用于循环控制,作为遍历的终点) */
mchunkptr p; /* 当前被合并的chunk */
mchunkptr nextp; /* (链表中)下一个要合并整理的 chunk */
mchunkptr unsorted_bin; /* unsorted bin 的头指针 */
mchunkptr first_unsorted; /* 要链接到的 chunk(即unsorted bin中的第一个节点)*/
/* 以下变量的用途与 free() 函数中的完全相同 */
mchunkptr nextchunk; /* 内存地址中相邻的下一个 chunk */
INTERNAL_SIZE_T size; /* 当前 chunk 的大小 */
INTERNAL_SIZE_T nextsize; /* 地址相邻下一个 chunk 的大小 */
INTERNAL_SIZE_T prevsize; /* 地址相邻前一个 chunk 的大小 */
int nextinuse; /* 地址相邻下一个 chunk 的使用状态标志 */
atomic_store_relaxed (&av->have_fastchunks, false);
unsorted_bin = unsorted_chunks(av);
/*
将每个 chunk 从 fast bin 中移出并进行合并(整理),随后将其放入 unsorted bin 中。
这样做(放入 unsorted bin)的诸多原因之一是:这避免了立即计算该 chunk 实际上该属于哪个 bin
(指 Small/Large Bin)的开销,除非 malloc 确信这些 chunks 不会被立即复用
*/
maxfb = &fastbin (av, NFASTBINS - 1);
fb = &fastbin (av, 0);
do {
p = atomic_exchange_acq (fb, NULL); // 获取fastbin的头指针,并清空fastbin
if (p != 0) { // 遍历取出来的p的链表
do {
{
if (__glibc_unlikely (misaligned_chunk (p))) // 检查的对齐
malloc_printerr ("malloc_consolidate(): "
"unaligned fastbin chunk detected");
unsigned int idx = fastbin_index (chunksize (p)); // 检查大小是否合法
if ((&fastbin (av, idx)) != fb)
malloc_printerr ("malloc_consolidate(): invalid chunk size");
}
check_inuse_chunk(av, p); // 检查确保chunk是inuse(fastbin和tcache中chunk不会改变inuse位)
nextp = REVEAL_PTR (p->fd); // 解密获取 p 的fd
/* Slightly streamlined version of consolidation code in free() */
size = chunksize (p);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);
if (!prev_inuse(p)) { // 检查p 的prev_inuse位(向前合并)
prevsize = prev_size (p);
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize)); // 将p赋值为前一个chunk的地址
if (__glibc_unlikely (chunksize(p) != prevsize))
malloc_printerr ("corrupted size vs. prev_size in fastbins");
unlink_chunk (av, p); // 将前一个chunk解链
}
if (nextchunk != av->top) { // 检查next chunk是不是top chunk,是的话就可以直接合并走else分支
nextinuse = inuse_bit_at_offset(nextchunk, nextsize); // 检查nextchunk是否为空闲状态
if (!nextinuse) { // 是的话,向后合并
size += nextsize;
unlink_chunk (av, nextchunk);
} else
clear_inuse_bit_at_offset(nextchunk, 0); // 否则清空其的inuse位,因为p要进unsorted bin了
/* 经典链接操作(这里有可能触发了向前合并也可能没取决于是否进入过了if (!prev_inuse(p))分支 )
但是不管有没有向前合并,p都会进入unsorted bin) */
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);
}
// 如果nextchunk是top chunk,那么p直接与top chunk合并不进入unsorted bin
else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
}
} while ( (p = nextp) != 0); // 遍历p链表上的每一个chunk
}
} while (fb++ != maxfb); // 遍历每一个fastbin
}参考文章:https://arttnba3.cn/2021/01/15/GLIBC-0X00-MALLOC-2.23-PART-I/
本文深入解析glibc-2.35的malloc流程,重点分析tcache、fastbin及_int_malloc等核心分配逻辑。
由 AI 根据全文自动生成,仅供参考,以原文为准