glibc下malloc实现原理
2022-12-16
18 min read
在分析源码之前得先去了解各种有关的数据类型，可以参照下面这个网址。
https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/heap-structure
一般情况下我们申请一个内存通常是使用malloc函数，但是看glibc的源码我们就可以知道，其实malloc函数只是对__libc__malloc函数的一个封装。但是在__libc__malloc函数中，主要是调用的_int_malloc函数，所以我们读源码的重点就是_int_malloc函数
变量定义&初始检查
static void *
_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_request2size traps (returning 0) request sizes
that are so large that they wrap around zero when padded and
aligned.
*/
checked_request2size (bytes, nb);
/* There are no usable arenas. Fall back to sysmalloc to get a chunk from
mmap. */
//没有可用的arena，去系统调用获取一个来自mmap的chunk
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
关于在该函数中所用到的定义都在最开始给出了，在前面主要关注几个变量，nb和victim，nb是需要申请的内存的大小，victim是指向满足需求的chunk的指针，最后会返回victim指向的chunk的fd字段的地址。在定义完成这些变量后，判断了一下是否有可用的线程arena，如果没有就通过系统调用去获取。
从fastbins中获取chunk
//如果申请的大小小于fastbin最大的大小
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
//记录这个大小的fastbin的索引
idx = fastbin_index (nb);
//得到这个fastbin对应的头指针
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
!= victim);
//存在可以利用的chunk
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);
//chunk转化成mem的形式
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
最外层的if判断需要申请的内存大小是否小于fastbin的最大大小，在if循环体中，获取了相应大小的fastbin的索引和这个fastbin对应的头指针，在do-while循环中有一个catomic_compare_and_exchange_val_acq宏，他的作用如下:
对于catomic_compare_and_exchange_val_acq(mem, newval, oldval)
如果mem指向的内容和oldval相等，会把mem指向的内容改为newval，并且返回oldval
if(*mem == oldver){ *mem = newval; return oldver; }
对于执行该函数前的各个变量的值，看下图
一般情况下来说，这个宏函数只执行一次，对于catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)，此时fb和victim都指向的是chunk1，该宏函数就是把victim->fd给到了fb，并且返回了victim所以此时fb应该是指向的chunk2，所以执行后的各个变量如图
此时的chunk1已经脱离链表了，可以看出，fastbin是LIFO表了(Last In First Out)。
从smallbins获取chunk
if (in_smallbin_range (nb))
{
//获取smallbin中大小为内存块大小的索引
idx = smallbin_index (nb);
//获取对应smallbin中的chunk指针
bin = bin_at (av, idx);
//如果victim=bin 则说明bin为空
//如果victim!=bin，则有两种情况
//一种是victim为0，说明smallbin还没有初始化
if ((victim = last (bin)) != bin)
{
if (victim == 0) /* initialization check */
//还没有初始化，把fastbins中的chunk合并
malloc_consolidate (av);
else
{
//获取victim后的一个chunk
bck = victim->bk;
//这里防止chunk伪造
if (__glibc_unlikely (bck->fd != victim))
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
//设置 victim 对应的 inuse 位
set_inuse_bit_at_offset (victim, nb);
//这里就完成了取出victim，从bin和bck中间取出
bin->bk = bck;
bck->fd = bin;
// 如果不是 main_arena，设置对应的标志
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
}
判断如果请求的内存大小在smallbins的范围中，获取smallbin中大小为请求的内存块大小的索引，然后获取了对应的smallbin中的chunk指针，并且通过(victim = last (bin)) != bin判断bin是否是空的。通过bck->fd != victim来验证chunk是否是伪造的。然后设置inuse位，从bin和bck中间取出victim，判断是否是主线程，设置了对应的值。这里的smallbin是FIFO表(First In First Out)
取出chunk1前
取出chunk1后
此时chunk1已经从bin中脱离出来了。
从largebins中获取chunk
else
{
//获取下标
idx = largebin_index (nb);
//如果有fastbin的话，会处理fastbin
if (have_fastchunks (av))
malloc_consolidate (av);
}
从unsortedbin中获取chunk
获取对应chunk的size
for (;; )
{
int iters = 0;
//如果unsorted bin 不为空
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
//victim为最后一个chunk，
//bck为倒数第二个chunk
bck = victim->bk;
//限定chunk的大小
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), av);
//获取了chunk的size
size = chunksize (victim);
尝试分割last_remainder
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的大小
remainder_size = size - nb;
//获取新的remainder的位置
remainder = chunk_at_offset (victim, nb);
//更新unsorted bin的情况
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
//更新av中的last_remainder
av->last_remainder = remainder;
//更新remainder的指针
remainder->bk = remainder->fd = unsorted_chunks (av);
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
//设置victim的头部
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
//设置remainder的头部
set_head (remainder, remainder_size | PREV_INUSE);
//设置remainder的foot
set_foot (remainder, remainder_size);
//
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
开始判断了申请的内存大小是否在smallbin的范围内，并且要满足下面三个条件:
- unsorted bin中只有一个唯一的chunk
- 唯一的chunk是last_remainder
- last_remainder的大小要大于申请的大小加上最小值
然后就进行了一些分割last_remainder的操作以及创建一个新的chunk
移除当前元素与直接返回
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
/* Take now instead of binning if exact fit */
//如果取出来的大小和想要的大小刚好合适，那就直接取出
if (size == nb)
{
//设置inuse位
set_inuse_bit_at_offset (victim, size);
//如果av不是main_arena，设置victim->size
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
将当前元素放入对应的bin中
if (in_smallbin_range (size))
{
//获取对应chunk的下标 把取出来的 chunk 放到对应的 small bin 中。
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;
/* maintain large bins in sorted order */
//bin不为空
if (fwd != bck)
{
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
//如果
assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
//如果chunk的大小小于bck->bk的大小
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;
}
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);
}
if ((unsigned long) size == (unsigned long) fwd->size)
/* 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;
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}
判断了size属于smallbin还是largebin的范围，然后执行对应的代码，比如chunk在smallbin支持的范围内时，会把victim放到smallbins当中
if (in_smallbin_range (size))
{
//获取对应chunk的下标 把取出来的 chunk 放到对应的 small bin 中。
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
执行完if中的语句后，执行如下语句，完成了把victim插入到smallbins的过程
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
执行的结果如下
对于largebins，情况又与smallbins不同，largebin中存储的chunk的size不相同，在一个区间里，所以就需要进行一些判断。
这里的话分为两种情况，一种是 victim的size小于当前bin中最小chunk的size，第二种是 victim的size不小于当前bin中最小chunk的size
victim的size小于当前bin中最小chunk的size
此时执行的代码如下
执行前的结果如下，让fwd指向bin，自己指向bin->bk
执行到if (fwd != bck)的时候，数据结构布局如下
执行后的结果如下
最后在执行
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
结果如下
victim的size不小于当前bin中最小chunk的size
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);
}
if ((unsigned long) size == (unsigned long) fwd->size)
/* 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;
}
用fd_nextsieze遍历链表，遇到size相同的时候，会插入到第二个位置
在victim和chunk1的size相等的时候，会在chunk1的fd方向插入这个bin链表，并且不会处理victim的两个nextsize字段，当victim的size和chunk1不相等的时候会对nextsize进行处理
在else块中，会把victim插入到chunk1和chunk2之间。
从largebin中获取chunk
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))
{
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb)))
victim = victim->bk_nextsize;
/* 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;
remainder_size = size - nb;
unlink (av, victim, bck, fwd);
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
/* 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 (__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;
}
}
第一个if确保他不在smallbin的范围内，第二个if确保victim的size大于要申请的空间大小，也就是确保bin中最大的chunk大于要申请的空间，如果不满足就之间跳过这个if了。然后一直遍历bin，从大的开始找找到小于需要申请空间的大小的victim。并且这个victim不能是最后一个。然后会重新计算remainder大小，调用unlink把victim从链中脱出来，并且对remainder的size进行比较，如果小于minsize，就不需要切割了。如果大于minsize，则需要切割，会先把他加入到unsortedbin中，为victim_remainder构造相应的chunk信息
从更大的bin获取chunk
/*
Search for a chunk by scanning bins, starting with next largest
bin. This search is strictly by best-fit; i.e., the smallest
(with ties going to approximately the least recently used) chunk
that fits is selected.
The bitmap avoids needing to check that most blocks are nonempty.
The particular case of skipping all bins during warm-up phases
when no chunks have been returned yet is faster than it might look.
*/
++idx;
bin = bin_at(av, idx);
block = idx2block(idx);
map = av->binmap[ block ];
bit = idx2bit(idx);
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;
}
/* 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);
/* 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;
}
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(av, victim, bck, fwd);
/* Exhaust */
if (remainder_size < MINSIZE) {
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena) set_non_main_arena(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 (__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;
/* 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);
}
check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
alloc_perturb(p, bytes);
return p;
}
}
前面是通过idx获取了一个bin，这里的idx是前面没有成果取出chunk的那个bin的idx，可能是smallbins也可能是largebins
第一个if语句在逻辑上的含义为：当前map数字中是否存在位阶比bit更高的二进制位不为0，如果不存在，也就是bit > map成立，就说明当前map对应的一系列bins中不存在size比nb大的chunk
然后程序会判定更高的map中是否含有chunk，如果都没有的话，就去切割top chunk来获得返回的chunk。如果有，就获取这个map对应的一系列bin中序号最小的bin
然后程序会开始寻找这个map中第一个含有chunk的bin
总之，这个被找到的bin，其最后一个chunk会被分割，分割出来的部分返回给用户，剩余部分，如果还满足MINSIZE的话，就加入unsorted bin
从topchunk中获取chunk
use_top:
/*
If large enough, split off the chunk bordering the end of memory
(held in av->top). Note that this is in accord with the best-fit
search rule. In effect, av->top is treated as larger (and thus
less well fitting) than any other available chunk since it can
be extended to be as large as necessary (up to system
limitations).
We require that av->top always exists (i.e., has size >=
MINSIZE) after initialization, so if it would otherwise be
exhausted by current request, it is replenished. (The main
reason for ensuring it exists is that we may need MINSIZE space
to put in fenceposts in sysmalloc.)
*/
victim = av->top;
size = chunksize (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);
alloc_perturb (p, bytes);
return p;
}
/* 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);
}
/*
Otherwise, relay to handle system-dependent cases
*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}
直接从topchunk中切割。
- 检查大小
- 更新
malloc_state中的top chunk的地址 - 为切割后的top chunk构造相关数据
参考
https://blog.csdn.net/weixin_44215692/article/details/123930658