1.背景
2.环境准备
2.1编译带源码信息的glibc
2.1.1下载glibc源码文件
2.1.2编译64位的glibc源码
tar -zxvf glibc-2.23.tar.gz
cd glibc-2.23
mkdir build_x64
cd build_x64
mkdir glibc_x64
CFLAGS="-g -g3 -ggdb -gdwarf-4 -Og -Wno-error"
CXXFLAGS="-g -g3 -ggdb -gdwarf-4 -Og"
../configure --prefix=/home/g0fl1er/Desktop/glibc-2.23/build_x64/glibc_x64
make -j4
make install
2.1.3编译32位的glibc源码
tar -zxvf glibc-2.23.tar.gz
cd glibc-2.23
mkdir build_x32
cd build_x32
mkdir glibc_x32
CC="gcc -m32 -Wno-error=attributes"
CXX="g++ -m32"
CFLAGS="-g -g3 -ggdb -gdwarf-4 -Og -Wno-error"
CXXFLAGS="-g -g3 -ggdb -gdwarf-4 -Og"
../configure --prefix=/home/g0fl1er/Desktop/glibc-2.23/build_x32/glibc_x32/ --host=i686-linux-gnu
make -j4
make install
2.1.4Patchelf替换
patchelf --set-interpreter /home/admin/Desktop/glibc-2.23/build_x64/glib64/lib/ld-linux-x86-64.so.2 --set-rpath /home/admin/Desktop/glibc-2.23/build_x64/glib64/lib/ 1
3.malloc
#include <stdlib.h>
#include <stdio.h>
void main()
{
char *a = (char *)malloc(20);
}
gcc 1.c -o 1
3.1开始分析
gdb -q 1
b main
r
一路ni，走过这个dl_resolve的过程，直接到他的malloc的开始，也就是到__libc_malloc这个函数这里。
size做校验以后，如果不通过则会返回为0，反之则调用request2size函数对该申请的size进行对齐操作。#define checked_request2size(req, sz)
if (REQUEST_OUT_OF_RANGE (req)) {
__set_errno (ENOMEM);
return 0;
}
(sz) = request2size (req);
-0x41| 变量 | 值 |
|---|---|
| MIN_SIZE | 0x20 |
#define REQUEST_OUT_OF_RANGE(req)
((unsigned long) (req) >=
(unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
#define request2size(req)
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ?
MINSIZE :
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
real_size = (req+8+15)&0xfffffffffffffff0 
arena是否为空，既进入到int_malloc函数前如果没有通过arena_get函数获取到，则通过sysmalloc函数申请对齐后size大小的空间，然后判断申请到的空间如果不为空，则调用alloc_perturb函数对该空间的数据进行填充size大小的00数据。 if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
memset将p指向的地址空间设置n大小的00数据。alloc_perturb (char *p, size_t n)
{
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte ^ 0xff, n);
}
#define get_max_fast() global_max_fast
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
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);
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), av);
return NULL;
}
check_remalloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
size对齐以后得到的size没有比get_max_fast函数的返回值值大的时候 ，则会进入到该函数体中，这里get_max_fast函数的返回值如果初始化过后是128，既我们所申请的size如果没有超过128字节，会先进入到fastbin这里。idx = fastbin_index (nb);
#define fastbin_index(sz)
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
chunk链表的末尾。 do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd, victim))
!= victim);
如果链表非空，则开始检查链表最后一个 chunk 的属性是否符合要求。首先通过反向查找用 chunksize 函数获取该 chunk 的大小，然后根据这个大小使用 fastbin_index 函数查找该 chunk 的索引 idx，并检查这个 idx 是否与之前获取的 idx 相同，如果不相同则报错。
chunk做了个合规检查。 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), av);
return NULL;
}
chunk的size没有问题后，会调用check_remalloced_chunk函数去对该chunk的size等属性再次进行校验，该校验流程可以进入到check_remalloced_chunk函数中看到。# define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
size，去掉其中的mmap和inuse的标志位。 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
chunk的分配arena是否正确，假如是main_arena分配的，那av就必须是main_arena，反之一样。if (!chunk_is_mmapped (p))
{
assert (av == arena_for_chunk (p));
if (chunk_non_main_arena (p))
assert (av != &main_arena);
else
assert (av == &main_arena);
}
chunk的结构是否合规。next的chunk指针，然后会调用do_check_chunk函数来检查传入的chunk。 mchunkptr next;
do_check_chunk (av, p);
do_check_chunk函数可以看到其具体实现，首先会对调用chunsize函数获取该chunk的大小，其次就是获取一些固定的值，比如可申请内存空间的最大地址和最小地址，其中最大的大小就是top_chunk加上其size，即是最大的地址，而最小地址则是最大地址减去system_mem，就是最小地址。 unsigned long sz = chunksize (p);
/* min and max possible addresses assuming contiguous allocation */
char *max_address = (char *) (av->top) + chunksize (av->top);
char *min_address = max_address - av->system_mem;
size的获取和可分配的最大最小地址的初始化以后，将会调用is_mmapped函数来对该chunk进行校验，判断其是否是由main_arena分配的chunk，如果不是则进入下面的判断中继续。 if (!chunk_is_mmapped (p))
#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
main_arena分配的chunk，首先会对判断该chunk是否是top_chunk，如果不是，则调用contiguous函数对arena的flags的第二个bit做校验，判断是否为0，如果是0，就必须要求该chunk的size大于可申请的内存大小的最小size。最后假设p是top_chunk，则会要求其大小必须要大于最小大小，并且其上一个chunk块必须是在使用中。if (!chunk_is_mmapped (p))
{
/* Has legal address ... */
if (p != av->top)
{
if (contiguous (av))
{
assert (((char *) p) >= min_address);
assert (((char *) p + sz) <= ((char *) (av->top)));
}
}
else
{
/* top size is always at least MINSIZE */
assert ((unsigned long) (sz) >= MINSIZE);
/* top predecessor always marked inuse */
assert (prev_inuse (p));
}
chunk的逻辑以后，该分析这个chunk是mmap分配的逻辑。首先会调用contiguous函数来对arena的分配模式进行校验，如果不是连续模式就返回0，并且top_chunk不是unsorted_bin中的chunk，则校验其chunk的地址是否在可分配的最大最小的地址范围内。chunk的size对齐页和内存。if (!chunk_is_mmapped (p))
{
//...........
//...........
//...........
}
else
{
/* address is outside main heap */
if (contiguous (av) && av->top != initial_top (av))
{
assert (((char *) p) < min_address || ((char *) p) >= max_address);
}
/* chunk is page-aligned */
assert (((p->prev_size + sz) & (GLRO (dl_pagesize) - 1)) == 0);
/* mem is aligned */
assert (aligned_OK (chunk2mem (p)));
}
chunk是main_arena分配的，以上的这个do_check_chunk函数其实只是校验了一下chunk的size是否处在可分配的最大和最小的size范围内。 if (chunk_is_mmapped (p))
return; /* mmapped chunks have no next/prev */
chunk是否是在使用中，assert函数则要求该chunk必须是在使用中，既Inuse位的值为1。assert (inuse (p));
chunk的下一个chunk的prev_inuse位是否为1来判断当前的chunk是否在使用中。#define inuse(p)
((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
chunk的下一个chunknext = next_chunk (p);
chunk是free状态(未使用)的，则利用上一个chunk来对当前chunk进行校验。并且调用do_check_free_chunk函数来再次检查上一个chunk是否是free状态(未使用)。if(!prev_inuse(p)) //如果上一个chunk是free状态的
{
/* Note that we cannot even look at prev unless it is not inuse */
mchunkptr prv = prev_chunk(p);
assert(next_chunk(prv) == p);
do_check_free_chunk(av, prv);
}
chunk的size，然后利用该size获取下一个chunk，接着调用do_check_chunk函数检查该chunk的size和arena的大小是否合规(这里上面分析过do_check_chunk函数了,就不分析了)。之后调用assert函数来校验当前p的inuse位和mmap位是否为0，assert函数要求chunk必须是main_arena分配并且必须是free的。/* Chunk must claim to be free ... */
assert (!inuse (p));
assert (!chunk_is_mmapped (p));
chunk的size是否大于等于MIN_SIZE。chunk中的size和user_data的地址必须是对齐的chunk必须是在使用状态chunk的prev_size必须和当前chunk的size一样chunk必须是在使用状态或者下一个chunk是top_chunkchunk和下一个chunk的fd和bk指针必须指向的是当前chunkif ((unsigned long) (sz) >= MINSIZE)
{
assert ((sz & MALLOC_ALIGN_MASK) == 0);
assert (aligned_OK (chunk2mem (p)));
/* ... matching footer field */
assert (next->prev_size == sz);
/* ... and is fully consolidated */
assert (prev_inuse (p));
assert (next == av->top || inuse (next));
/* ... and has minimally sane links */
assert (p->fd->bk == p);
assert (p->bk->fd == p);
}
else /* markers are always of size SIZE_SZ */
assert (sz == SIZE_SZ);
chunk必须是在使用chunk的size必须大于等于MIN_SIZE if (next == av->top)
{
assert (prev_inuse (next));
assert (chunksize (next) >= MINSIZE);
}
else if (!inuse (next))
do_check_free_chunk (av, next);
chunk的使用状态的检测后，将继续回到do_check_remalloced_chunk函数，对剩下的部分进行分析。assert函数对该chunk的size进行一系列的合规要求：size必须对齐size必须要大于MIN_SIZEuser_data必须要对齐 /* Legal size ... */
assert ((sz & MALLOC_ALIGN_MASK) == 0);
assert ((unsigned long) (sz) >= MINSIZE);
/* ... and alignment */
assert (aligned_OK (chunk2mem (p)));
/* chunk is less than MINSIZE more than request */
assert ((long) (sz) - (long) (s) >= 0);
assert ((long) (sz) - (long) (s + MINSIZE) < 0);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
if (in_smallbin_range (nb))
size是否小于MIN_LARGE_SIZE的大小，而MIN_LARGE_SIZE大小为((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)，因为本次环境是64位的程序，所以MIN_LARGE_SIZE大小为0x400(1024) Byte。#define NBINS 128
#define NSMALLBINS 64
#define SMALLBIN_WIDTH MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
#define in_smallbin_range(sz)
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
size对应small_bin中的idx下标。之后调用bin_at函数来根据其下标，到arena的结构体中取出对应的chunk。 idx = smallbin_index (nb);
bin = bin_at (av, idx);
small_bin_idx = size >> 4。此时这里所用到的标志的值为：| 变量 | 值 |
|---|---|
| INTERNAL_SIZE_T | 0x8 |
| MINSIZE | 0x20 |
| SIZE_SZ | 0x8 |
| MALLOC_ALIGN_MASK | 0xf |
| MALLOC_ALIGNMENT | 0x10 |
#define smallbin_index(sz)
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))
+ SMALLBIN_CORRECTION)
bin[(idx-1)*2]-chunk结构体中fd指针的偏移得来的。chunk结构体中,fd指针的偏移是0x10。chunk_ptr = arena->bin[(idx -1) * 2] - 16
#define bin_at(m, i)
(mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))
- offsetof (struct malloc_chunk, fd))
small_bin的fd和bk指针都有作用，一个fd和bk指针占2SIZE_T，故这里下标需要需要乘2，最后返回的是该chunk的fd指针(当然这里说法不一，具体左右还需自己调试理解。)size处在最小MIN_SIZE(0x20)到MIN_LARGE_SIZE(0x400)之间，下标一共有：buf = set()
for idx in range(0x20,0x400):
buf.add(((idx>>4) -1) * 2)
print len(buf)
small_bin中一共用着62个下标的数据块。idx下标对应的chunk链表的最后一个chunk，来判断是否跟头链表是否一样。如果不一样，则证明该chunk链表不为空，否则证明当前下标的chunk链表为空。 if ((victim = last (bin)) != bin)
chunk进行校验，如果最后一个chunk为0，则意味着bin中数据没有初始化，将会调用malloc_consolidate函数对当前的arena进行初始化，否则就将当前的chunk的上一个chunk的地址给到bck这个指针，然后利用该bck指向的上一个chunk的fd指针来对当前chunk进行校验是否一致。chunk加size偏移来获取下一个chunk，然后将下一个chunk的prev_inuse位设置为1，意味着当前chunk已被使用。chunk从bin的双向链表中移除，然后校验arena是否是main_arena，如果不是就需要设置该chunk的size位置的mmap的标志位为1。if ((victim = last (bin)) != bin)
{
if (victim == 0) /* initialization check */
malloc_consolidate (av);
else
{
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
{
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);
alloc_perturb (p, bytes);
return p;
}
}
chunk的size和用户申请的size(nb变量)是否一致，这里校验跟上面do_check_remalloced_chunk函数几乎一样，唯独最后多了一个要求当前chunk的上一个chunk必须为使用状态。static void
do_check_malloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
{
/* same as recycled case ... */
do_check_remalloced_chunk (av, p, s);
/*
... plus, must obey implementation invariant that prev_inuse is
always true of any allocated chunk; i.e., that each allocated
chunk borders either a previously allocated and still in-use
chunk, or the base of its memory arena. This is ensured
by making all allocations from the `lowest' part of any found
chunk. This does not necessarily hold however for chunks
recycled via fastbins.
*/
assert (prev_inuse (p));
}
chunk2mem获取user_data的地址，alloc_perturb函数负责将user_data区域的值设置为00字节，最后将获取到的user_data的地址返回给用户。small_bin的过程。但是这里没有提到malloc_consolidate函数，所以放到这里继续分析。get_max_fast()函数的返回值是否为0，如果是0的话，就将调用malloc_init_state函数和check_malloc_state函数对arena进行初始化操作。 if (get_max_fast () != 0) {
//这里先省略不做分析
//......
}
else {
malloc_init_state(av);
check_malloc_state(av);
}
int i;
mbinptr bin;
/* Establish circular links for normal bins */
for (i = 1; i < NBINS; ++i)
{
bin = bin_at (av, i);
bin->fd = bin->bk = bin;
}
arena，如果不是main_arena就调用set_noncontiguous函数，将arena的flags的第二个bit设置为1.#if MORECORE_CONTIGUOUS
if (av != &main_arena)
#endif
set_noncontiguous (av);
if (av == &main_arena)
set_max_fast (DEFAULT_MXFAST);
global_max_fast=128，所以下次再次触发get_fast_max()函数，得到的返回值将会是128，不再是0了。#define set_max_fast(s)
global_max_fast = (((s) == 0)
? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
arnea的flags的第1个bit位设置为1，最后把调用initial_top函数将当前arena的bin[0]-0x10位置的chunk传给arena的top，意味着先将bin[0]-0x10位置的chunk当做top_chunk。 av->flags |= FASTCHUNKS_BIT;
av->top = initial_top (av);
get_max_fast函数不为0时，会先调用clear_fastchunks函数，将arena中flags第一个bit的值设置为1，既清空fastbin中的chunk。bin[0]-0x10位置的chunk给到unsorted_bin，之后获取第一个和最后一个fastbin数组的chunk链表 if (get_max_fast () != 0) {
clear_fastchunks(av);
unsorted_bin = unsorted_chunks(av);
/*
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);
p = atomic_exchange_acq (fb, 0);
p是否为空，如果p不为空，则意味着当前chunk链表不为空，将执行第二个do_while循环，开始循环该链表中的每一个chunkif (p != 0) {
do {
check_inuse_chunk(av, p);
nextp = p->fd;
/* Slightly streamlined version of consolidation code in free() */
size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
if (nextchunk != av->top) {
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;
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);
check_inuse_chunk函数对该chunk链表中的chunk进行校验，要求当前chunk的下一个chunk的prev_inuse位的值必须为1(这里因为fastbin中的chunk在free的时候，默认不会清空inuse位的值，所以这里不是代表该chunk是在使用中)check_inuse_chunk(av, p);
chunk的真实的size大小，然后利用该size获取当前chunk的下一个chunk的地址和size size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
chunk从small_bin和large_bin的两个双向链表中移除。fd和bk指针，然后利用fd指针和bk指针的值来对当前的chunk做校验，确保p的fd和bk指针没有被修改，如果被修改了就会报"corrupted double-linked list"错误。/* Take a chunk off a bin list */
#define unlink(AV, P, BK, FD) {
FD = P->fd;
BK = P->bk;
if (__builtin_expect (FD->bk != P || BK->fd != P, 0))
malloc_printerr (check_action, "corrupted double-linked list", P, AV);
fd和bk指针的值，将当前的Chunk移除链表。接下来还需要考虑如何移除第二条双向链表，fd_nextsize和bk_nextsize的情况。FD->bk = BK;
BK->fd = FD;
chunk是否符合small_bin的范围，并且chunk的fd_nextsize指针位置不为空，如果满足这两个条件，则会认为该chunk是large_bin中的chunk，因为small_bin中保存的chunk不存在使用fd_nextsize和bk_nextsize的情况)。if (!in_smallbin_range (P->size)
&& __builtin_expect (P->fd_nextsize != NULL, 0))
chunk的fd_nextsize和bk_nextsize指针来进行校验自身，判断其fd_nextsize和bk_nextsize是否被修改。if (!in_smallbin_range (P->size)
&& __builtin_expect (P->fd_nextsize != NULL, 0)) {
if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)
|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))
malloc_printerr (check_action,
"corrupted double-linked list (not small)",
P, AV);
fd_nextsize和bk_nextsize的知识，fd_nextsize指向的是比自身小的下一个size，bk_nextsize指向的是比自身大的第一个size，然后当chunk大小相同时，则会在同一个chunk的双向链表中，而这个双向链表只有头chunk有fd_nextsize和bk_nextsize，这里的fd_nextsize和bk_nextsize是指向比自身chunk大和小的第一个chunk。这里随便放一张large_bin的结构图(size是随便编的,主要参考结构)：
fd_nextsize和bk_nextsize指针并未被修改，则开始判断要移除的chunk的下一个chunk的fd_nextsize指针是否为NULL，如果为NULL则代表要判断移除chunk的size和下一个chunk的size一样，处在同一个双向链表中，这时就要接着判断移除chunk的fd_nextsize是否指向自身，如果指向自身则代表，该large_bin的chunk链表中只有这一个size的chunk双向链表，想要移除该chunk，只需要将fd_nextsize和bk_nextsize指向它的下一个chunk自身即可。if (FD->fd_nextsize == NULL) {
if (P->fd_nextsize == P)
FD->fd_nextsize = FD->bk_nextsize = FD;
else {
.......
}
} else {
........
}
}
chunk的fd_nextsize并没有指向自身，则代表该large_bin中，还有其他的size的chunk双向链表，需要将当前chunk的fd_nextsize和bk_nextsize都指向下一个size的chunk链表，然后同理再将下一个size的chunk双向链表的表头的fd_nextsize和bk_nextsize也指向移除chunk的下一个chunk。if (FD->fd_nextsize == NULL) {
if (P->fd_nextsize == P)
..........
else {
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 {
........
........
}
}
chunk的fd_nextsize指针不为空，则代表移除的chunk和下一个chunk的size不一样，就正常进行该size的chunk的双向链表的移除操作即可。if (FD->fd_nextsize == NULL) {
if (P->fd_nextsize == P)
........
else {
........
}
} else {
P->fd_nextsize->bk_nextsize = P->bk_nextsize;
P->bk_nextsize->fd_nextsize = P->fd_nextsize;
}
}
unlink的过程。chunk如果是free状态的，就会执行对该空闲chunk执行unlink操作，将其从对应的bin中的双向链表中移除。if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
chunk是否是top_chunk，如果不是，则调用inuse_bit_at_offset函数，结合下一个chunk的size，来获取下一个chunk的使用状态。 if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
inuse_bit_at_offset函数的宏定义如下：#define inuse_bit_at_offset(p, s)
(((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
chunk也是free状态的话，也是一样，将其大小合并到size，然后调用unlink函数将其从对应的bin的双向链表中移除。chunk是使用状态，则调用clear_inuse_bit_at_offset函数，将其prev_inuse位设置为0，既将当前**chunk设置为free状态。if (!nextinuse) {
size += nextsize;
unlink(av, nextchunk, bck, fwd);
} else
clear_inuse_bit_at_offset(nextchunk, 0);
chunk和下一个chunk的状态的校验后，会发现，如果上下两个相邻的chunk如果是free状态的，那么就会合并，并且将其移出对应的bin的双向链表。Unsorted_bin的第一个chunk，然后将当前Chunk接入到Unsorbin中。first_unsorted = unsorted_bin->fd;
unsorted_bin->fd = p;
first_unsorted->bk = p;
size是否大于等于0x400，如果大于small_bin的范围，则将fd_nextsize和bk_nextsize指向为NULL。if (!in_smallbin_range (size)) {
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
chunk的size的prev_inuse位设置为1，然后再调用set_foot函数，将当前chunk的下一个chunk的prev_size的位置设置为该chunk的size，最后把fd和bk指向到unsorted_bin中，既完成合并unsorted_bin的最终操作。set_head(p, size | PREV_INUSE);
p->bk = unsorted_bin;
p->fd = first_unsorted;
set_foot(p, size);
chunk是top_chunk，就将下一个chunk的size合并到当前chunk的size中，然后将该size的prev_inuse位设置为1，再把该size设置为当前chunk的size，最后将arena中的top_chunk设置为当前chunk，既将当前chunk合并到top_chunk。 if (nextchunk != av->top) {
//......
//......
//......
}
else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
}
fastbin中chunk的合并以后，将继续循环当前chunk链表中的其他的chunk，进行合并。 do {
//........
} while ( (p = nextp) != 0);
chunk链表遍历完毕以后，将继续循环fastbin中下一个idx的chunk链表，直到fastbin中最大的idx对应的chunk链表。 do {
//.......
//.......
do {
//........
} while ( (p = nextp) != 0);
} while (fb++ != maxfb);
_int_malloc函数。small_bin中的内容分析，接下来，如果size的大小，超过了small_bin的范围，则调用largebin_index函数根据用户申请的size来找到对应的idx，然再调用have_fastchunks函数，判断arena中的fast_bin是否存在空闲chunk，如果存在，就调用malloc_consolidate函数，对arena中fast_bin中的free的chunk进行合并。 if (in_smallbin_range (nb))
{
//......
//.......
}
else
{
idx = largebin_index (nb);
if (have_fastchunks (av))
malloc_consolidate (av);
}
进入到largebin_index函数可以看到具体的宏定义实现，主要计算过程如下：
1 当 ((sz) >> 6) <= 48：
-
如果
sz右移 6 位后，结果小于等于 48，则sz在0x100（256）到0x1800（6144）字节之间。 -
idx计算：
48 + ((sz) >> 6)。2 当 ((sz) >> 9) <= 20： -
如果
sz右移 9 位后，结果小于等于 20，则sz在0x1800（6144）到0x4000（16384）字节之间。 -
idx计算：
91 + ((sz) >> 9)。3 当
((sz) >> 12) <= 10： -
如果
sz右移 12 位后，结果小于等于 10，则sz在0x4000（16384）到0xA000（40960）字节之间。 -
idx计算：
110 + ((sz) >> 12)。4 当
((sz) >> 15) <= 4： -
如果
sz右移 15 位后，结果小于等于 4，则sz在0xA000（40960）到0x28000（163840）字节之间。 -
idx计算：
119 + ((sz) >> 15)。5 当
((sz) >> 18) <= 2： -
如果
sz右移 18 位后，结果小于等于 2，则sz在0x28000（163840）到0x100000（1048576）字节之间。 -
idx计算：
124 + ((sz) >> 18)。6 否则：
-
如果
sz超过 1 MB（即sz >> 18大于 2），索引固定为126。其中 size超过了0x400的chunk，就会开始在large_bin的范围内开始找了。
#define largebin_index_64(sz)
(((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :
((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :
126)
arena->flags的最低位bit是否为0来判断fast_bin是否为空。#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
for (;; )
{
//......
//......
//.....
//.....
}
unsorted_bin中进行chunk的分配操作，最大循环次数是10000。unsorted_bin中的第一个chunk进行比较，如果一样就停止循环，其中victim是跟unsorted_bin的first_chunk循环比较的每一个chunk。 int iters = 0;
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}
chunk的上一个chunk，将其保存到bck中。然后将开始校验该chunk的size是否合规，如果不合规将报“malloc(): memory corruption”错误。size的合规检测，将调用checksize函数获取当前循环chunk的size，将其保存到size变量中。 while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
bck = victim->bk; //获取最后一个unsorted_bin中的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);
size = chunksize (victim);
//......
//.......
}
之后就是一个多条件判断：
size是否在small_bin的范围内unsorted_bin中的first_chunk，判断当前chunk的上一个chunk是否是unsorted_bin的first_chunkchunk是否是arena中的remainder分割的剩余chunk，既remainder_chunk。chunk的size是否大于用户申请的size+MINSZIE,判断当前chunk的size是否可以满足用户申请的sizenb(用户申请的size) < 0x400、上一个chunk是unsorted_bin的first_chunk、当前chunk是remainder_chunk并且size大小满足用户所申请的size大小，就将当前的chunk进行分割，分为用户申请的size大小和reamin_size大小两部分。chunk的size减去用户所申请的size还剩下多少size，将其保存到remainder_size变量中，之后调用chunk_at_offset函数获取remainder_chunk的地址，然后将这个remainder_chunk当做新的unsorted_bin。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);
remainder_size大于等于0x400，则代表其在large_bin的范围内，将remainder_chunk的fd_nextsize和bk_nextsize的指针置空。if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
chunk和剩余的remainder_chunk的size部分进行设置，将对应的prev_inuse位和mmap位设置为对应的值，最后将remainder_chunk的next_chunk的prev_size也设置为remainder_size。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;
chunk移出unsorted_bin的chunk链表中 /* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
chunk的size是否和用户所申请的一致，如果size一致则调用set_inuse_bit_at_offset函数设置一下chunk的size部分的内容，然后直接将当前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);
alloc_perturb (p, bytes);
return p;
}
chunk的size是否处在small_bin范围内，如果在就调用smallbin_index函数根据当前chunk的size获取small_bin中的idx，然后再调用bin_at函数获取arena->bin中对应idx的chunk链表的头指针，保存到bck变量中，然后将头指针指向的第一个chunk保存到fwd变量中。 if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
chunk的size并未在small_bin范围中，而是在large_bin中，那么同理先调用largebin_index函数根据当前chunk的size获取large_bin中的idx，然后再调用bin_at函数获取arena->bin中对应idx的chunk链表的头指针，保存到bck变量中，然后将头指针指向的第一个chunk保存到fwd变量中。 if (in_smallbin_range (size))
{
//.....
//......
}
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
bck和fwd进行判断。chunk的链表头指针bck和第一个chunk的fwd指针不相等，则认为当前bin[idx]对应chunk链表中有chunk，不为空。然后会将当前chunk的size的prev_inuse位设置为1。完成上述内容后，会调用assert函数对该chunk链表的最后一个chunk的size进行校验，要求其必须为main_arena分配的chunk。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的size是否比large_bin的对应idx的chunk链表的最后一个chunk的size还小。chunk的size比large_bin中idx的chunk链表的最后一个chunk的size还小，那么就会把当前循环的chunk接入到large_bin中idx的chunk链表的末尾。if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) //bck->bk是该idx的chunk链表中最后一个chunk
{
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链表中的第一个chunk必须是main_arena分配的chunk，然后开始利用fd_nextsize指针，循环遍历当前chunk链表中每一个不同size的chunk，之后调用assert函数，又一次对chunk的arena进行校验，必须是main_arena分配的chunk，该循环直到找到比当前chunk的size大于等于的第一个chunk为止。
if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) //bck->bk是该idx的chunk链表中最后一个chunk
{
//.....
//.........
//............
}
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相同，直接将当前fwd的位置放到fwd的下边。
if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;
else{
//........
//........
}
fd_nextsize和bk_nextsize指针，将当前chunk接入的位置放到fwd的右边，一会儿便于插入使用。
chunk的链表头指针bck和第一个chunk的fwd指针相等，则代表该chunk的链表为空，那么就直接将当前chunk的fd_nextsize和bk_nextsize指针全都指向自身。 /* maintain large bins in sorted order */
if (fwd != bck)
{
//........
//........
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
samll_bin和large_bin中的fwd和bck的获取后，将开始调用mark_bin函数，先获取small_bin或large_bin中当前chunk的size对应的idx，然后将bin_map中对应idx位置的bit位设置为1，最后利用头插法，将上面找了半天的当前chunk的插入位置，插入当前循环的chunk。 mark_bin (av, victim_index);
victim->bk = bck; //采用头插法，插入到chunk链表中。
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
#define mark_bin(m, i) ((m)->binmap[idx2block (i)] |= idx2bit (i))
BINMAPSHIFT = 5，相当于是将当前的idx右移5位，相当于是除以32，以此来得到当前idx在binmap的第几个block中。#define idx2block(i) ((i) >> BINMAPSHIFT)
#define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}
chunk，那么就开始调用in_smallbin_range函数对用户申请的size进行校验，假如用户申请的size没有在small_bin中，那么就从large_bin中去找。if (!in_smallbin_range(nb))
{
//.......
//.......
}
size在large_bin的idx了，所以这里直接用bin_at函数，直接在bin中取对应idx的chunk链表。然后调用first函数获取该chunk链表的第一个chunk，来跟头chunk进行比较，如果不一样，则代表当前chunk链表不为空，并且第一个chunk的size是否大于等于用户申请的大小，如果一切成立才继续执行判断内的代码，否则就跳出larget_bin的查找。if (!in_smallbin_range(nb))
{
//.......
//.......
if ((victim = first(bin)) != bin && (unsigned long)(victim->size) >= (unsigned long)(nb))
{
//......
}
}
large_bin中，chunk链表的第一个chunk一般是size最大的chunk，然后一直由大到小排列。这里假如用户所申请的size刚好满足，并且large_bin中的chunk不为空。size大小的chunk。 victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize(victim)) < (unsigned long) (nb)))
victim = victim->bk_nextsize;
chunk是否和用户申请的size一样，并且判断当前chunk是否是最后一个chunk，如果size一样的，并且当前chunk不是最后一个chunk，直接操作fd指针，将当前chunk的fd指针指向的chunk给到victimif (victim != last(bin) && victim->size == victim->fd->size)
victim = victim->fd;
chunk的size进行分割，计算剩余size，然后将其从large_bin的chunk双向链表中移除。/* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
size，是否小于MIN_SIZE，如果小于MIN_SIZE，则调用set_inuse_bit_at_offset函数，将该chunk的next_chunk的prev_inuse位设置为1，代表将当前的chunk的状态修改为使用状态。最后判断一下mmap的状态，如果是main_arena分配的chunk则将size中mmap位标志设置为0，反之则为1。if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
if (remainder_size < MINSIZE)
{
//......
//......
}
/* 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;
}
arena->bin主要就是通过bin_map实现，这里上面说过了bin_map的原理了，就不再叙述了。 ++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)
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 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;
}
}
bin_map中也没找到能够分配的chunk，那么就直接从top_chunk中直接进行分割。use_top:
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;
}
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
//......
}
/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
else if (have_fastchunks (av))
{
//......
}
/*
Otherwise, relay to handle system-dependent cases
*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
原文始发于微信公众号（弱口令安全实验室）：Glibc 2.23 Ptmalloc源码分析
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论