相关结构体
malloc_state
struct malloc_state
{
/* Serialize access. */
mutex_t mutex;
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
malloc_chunk
struct malloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
初次创建堆
非mmap
源程序
#include <stdlib.h>
int main(int argc, char **argv){
malloc(0x30);
return 0;
}
运行过程
进入
__libc_malloc
调用
__malloc_hook
中的函数来完成堆分配并返回,若为默认值则向下运行void *(*hook) (size_t, const void *) = atomic_forced_read (__malloc_hook); if (__builtin_expect (hook != NULL, 0)) return (*hook)(bytes, RETURN_ADDRESS (0));
程序第一次运行
__libc_malloc
时,__malloc_hook
中的值是hook.c
中的malloc_hook_ini
函数,因此会调用该函数,用于对__malloc_hook
进行初始化,初始化结束后值为0,后续再创建堆就是默认值0malloc_hook_ini (size_t sz, const void *caller) { __malloc_hook = NULL; ptmalloc_init (); return __libc_malloc (sz); }
初始化过程:设置
__malloc_hook
为NULL,再调用arena.c
中的ptmalloc_init
进行初始化,__malloc_initialized > 0
表示初始化完成补充:
__builtin_expect
作用:允许程序员将最有可能执行的分支告诉编译器
写法:
__builtin_expect(EXP, N)
含义:
EXP==N
的概率很大返回值:当
EXP==N
时返回0,反之返回1#define unlikely(x) __builtin_expect(!!(x), 0) //x很可能为假 #define likely(x) __builtin_expect(!!(x), 1) //x很可能为真
//if成立的条件是hook != NULL成立,即hook不为空,则去调用hook中的函数 if (__builtin_expect (hook != NULL, 0))
调用
arena_get
获取到管理空闲空间的分配区地址,申请的堆块就在这里arena_get (ar_ptr, bytes);
进入
_int_malloc
函数victim = _int_malloc (ar_ptr, bytes);
victim
指向_int_malloc
分配的内存计算分配的实际大小
checked_request2size (bytes, nb);
ptmalloc
以 chunk 为单位分配空间,传入的bytes 是用户提交的原始的空间大小nb
是为计算得到的 chunk 的大小检查是否有可用空间
if (__glibc_unlikely (av == NULL))
av = ar_ptr
是arena_get
获取到的分配区地址指针判断是否属于
fastbin
通过判断
nb <= get_max_fast()
即申请的实际大小是否小于fastbin
最大值来判断是否属于fastbin
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
属于
fastbin
则继续运行获取实际大小
nb
所在的fastbin
链表的index
,并且获取指向该链表的第一个结点的指针idx = fastbin_index (nb); 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))
该 chunk 为空,说明当前
fastbin
中没有刚好匹配nb
大小的空闲chunk
判断是否属于
smallbin
通过调用
in_smallbin_range
函数判断是否属于smallbin
if (in_smallbin_range (nb))
获取该大小所在的链表的
index
idx = smallbin_index (nb); bin = bin_at (av, idx);
判断
smallbin
是否为空,为空则跳过剩下的代码if ((victim = last (bin)) != bin) { if (victim == 0) /* initialization check */
victim
指向smallbin
中的最后一个bin,若其为空则smallbin
为空
调用
malloc_consolidate
整理fastbins
判断完不属于
smallbin
之后说明空间在largebin
,不会立即检查largebin
而是调用malloc_consolidate
将fastbins
里面的空闲chunk
合并整理到unsortedbin
中判断
fastbins
为空,跳过else { idx = largebin_index (nb); if (have_fastchunks (av)) malloc_consolidate (av); }
尝试切割top分配空间
获取到 top chunk 的大小
victim = av->top; size = chunksize (victim);
victim
指向av
内存空间中的top chunk
和申请的空间大小做比较:如果 top chunk 在满足分配后还能剩余空间大小大于最小的 chunk 的大小,则开始进行切割,并把剩余的 chunk 作为新的 top chunk
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; }
否则先判断fastbin是否非空,非空则重整理,fastbin和unsorted bin
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); }
不为空,调用sysmalloc直接向系统申请内存
else { void *p = sysmalloc (nb, av); if (p != NULL) alloc_perturb (p, bytes); return p; }
fastbin
free到fastbin
源程序
#include <stdlib.h>
int main(int argc, char **argv){
void *p;
p = malloc(0x30);
free(p);
return 0;
}
运行过程
由源码中
strong_alias (__libc_free, free)
得出:free
就是__libc_free
的别名调用
__libc_free
函数,传入的参数*mem
是要释放的堆的user data
地址的指针void __libc_free(void *mem)
调用
__free_hook
中的函数来完成释放,默认值为0,没有初始化的过程void (*hook) (void *, const void *) = atomic_forced_read (__free_hook); if (__builtin_expect (hook != NULL, 0)) { (*hook)(mem, RETURN_ADDRESS (0)); return; }
判断传入的指针值是否为0,free(0)无效
if (mem == 0) /* free(0) has no effect */ return;
调用
mem2chunk
函数,将user data
的指针mem
转换为对应的chunk head
指针p
//mem2chunk函数宏定义 //chunk head与user data之间相差prev_size和size字段,分别占一个机器字节,因此从user data到chunlk head只需减去两个机器字长,即2*SIZE_SZ #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
p = mem2chunk (mem); //p指向chunk head
调用
chunk_is_mmapped
函数判断该chunk是否由mmap
分配//chunk_is_mmapped宏定义 //检查size最低三位中的标志位,若为2则是mmap分配的内存 #define IS_MMAPPED 0x2 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
补充:使用
malloc
、free
等函数动态申请和释放内存时真正与系统交互用于系统调用的函数主要是(s)brk
函数以及mmap
brk
用于分配小空间,将数据段(.data)的最高地址指针_edata
往高地址推mmap
用于分配大空间,是在进程的虚拟地址空间中(堆和栈中间,称为文件映射区域的地方)找一块空闲的虚拟内存- 这两种方式分配的都是虚拟内存,没有分配物理内存
源程序中释放的堆不是由
mmap
分配的因此跳过if
中的内容调用
arena_for_chunk
获取该chunk
的分配区指针ar_ptr
ar_ptr = arena_for_chunk (p);
调用
_int_free
函数释放堆_int_free (ar_ptr, p, 0);
//_int_free函数定义,参数中的mstate表示的是malloc_state结构体也就是main_arena的结构体,mchunkptr表示的是malloc_chunk的结构体,av指向该chunk的分配区,p指向该chunk的chunk head static void _int_free (mstate av, mchunkptr p, int have_lock)
调用
chunksize
函数获取该chunk
的大小//chunksize宏定义,取p所指向的chunk的size位 #define chunksize(p) ((p)->size & ~(SIZE_BITS))
size = chunksize (p);
检查地址的合理性
//分配器永远不会在地址空间的末尾环绕,因此我们可以排除一些可能出现的尺寸值 //判断堆地址不在空间末尾且是对齐的,否则报无效地址的错误 //若互斥锁开启则关闭互斥锁 if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0) || __builtin_expect (misaligned_chunk (p), 0)) { errstr = "free(): invalid pointer"; errout: if (!have_lock && locked) (void) mutex_unlock (&av->mutex); malloc_printerr (check_action, errstr, chunk2mem (p), av); return; }
检查大小合理性
//判断堆大小是大于最小值 //判断大小对齐,即是机器字长的整数倍数 if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size))) { errstr = "free(): invalid size"; goto errout; }
//MINSIZE宏定义 //MALLOC_ALIGN_MASK = 两倍机器字长-1,结果将MIN_CHUNK_SIZE进行两倍机器字长对齐 #define MINSIZE \ (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
//aligned_OK宏定义,结果是判断是否是机器字长的整数倍 #define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0) //MALLOC_ALIGN_MASK宏定义 #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
//MIN_CHUNK_SIZE宏定义 #define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
判断堆是否在
fastbin
里//大小小于等于fastbin最大值 if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
安全性检查:检查要释放的堆的下一个堆的大小是否合法
//互斥锁是否开启 //下一个堆的大小是否小于最小堆大小或大于该内存池的user data最大值 //av指向chunk分配区 if (have_lock || ({ assert (locked == 0); mutex_lock(&av->mutex); locked = 1; chunk_at_offset (p, size)->size <= 2 * SIZE_SZ || chunksize (chunk_at_offset (p, size)) >= av->system_mem; })) { errstr = "free(): invalid next size (fast)"; goto errout; }
如果互斥锁开启则关闭
if (! have_lock) { (void)mutex_unlock(&av->mutex); locked = 0; }
清空堆中的内容
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
//free_perturb函数定义 //p指向user data, n 为实际堆实际大小,即不含chunk head //perturb:扰乱 //perturb_byte为0时,将堆的user data部分清空为0 static void free_perturb (char *p, size_t n) { if (__glibc_unlikely (perturb_byte)) memset (p, perturb_byte, n); }
设置分配区的标志位表示
fastbin
有空闲chunk
//av的标志位设置为1 set_fastchunks(av);
//set_fastchunks宏定义 #define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT) //FASTCHUNKS_BIT宏定义 #define FASTCHUNKS_BIT (1U)
根据
size
获得即将添加的chunk在fastbin中的索引idx
,并通过该索引获得头指针fb
//fastbin_index宏定义 #define fastbin_index宏定义(sz) \ ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2) //SIZE_SZ等于一个机器字长,32位右移1,64位右移2(除)
//fb指向chunk大小所在的fastbin链的头指针 unsigned int idx = fastbin_index(size); fb = &fastbin (av, idx);
安全性检查:检查
double free
//如果头指针等于要释放的堆,则判定double free //old等于要释放的堆所属的fastbin链的头结点 mchunkptr old = *fb, old2; unsigned int old_idx = ~0u; if (__builtin_expect (old == p, 0)) { errstr = "double free or corruption (fasttop)"; goto errout; }
将
chunk
添加到顶部之后检查顶部的fastbin
块的大小是否与我们要添加的块的大小相同。只有在我们拥有锁的情况下,我们才能解除对OLD
的引用//检查互斥锁 //old_idx为头结点所在的fastbin链的下标 //该chunk添加到fastbin中,即将fd设置为原来的头结点,并且把该chunk设置为头指针 //idx和old_idx不相等的时候报错 if (have_lock && old != NULL) old_idx = fastbin_index(chunksize(old)); p->fd = old2 = old; } while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2); if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0)) { errstr = "invalid fastbin entry (free)"; goto errout; } }
从fastbin取出chunk
源程序
#include <stdlib.h>
int main(int argc, char **argv){
void *p;
p = malloc(0x30);
free(p);
malloc(0x30);
return 0;
}
运行过程
运行至初次创建堆的判断申请实际大小所在的
fastbin
链表的第一个结点是否为空第一个结点不为空,则更改链表头指向第二个结点
do { victim = pp; if (victim == NULL) break; } while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) != victim);
安全性检查:判断所取到的堆的大小所在
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; }
计算并返回从fastbin获取的chunk的user data起始地址
void *p = chunk2mem (victim); alloc_perturb (p, bytes); return p;
fastbin相关漏洞和绕过利用原理
double free
在free到fastbin中有对double free
的判断机制
//如果头指针等于要释放的堆,则判定double free
//old等于要释放的堆所属的fastbin链的头结点
mchunkptr old = *fb, old2;
unsigned int old_idx = ~0u;
if (__builtin_expect (old == p, 0))
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
原理:连续两次释放同一个堆
利用:判断要释放的堆所属的fastbin
链的第一个chunk
地址是否和要释放的堆的地址相同,若相同则判定为double free
,因此绕过只需要保证二者地址不同即可,所以绕过方法是在第二次释放之前先释放一个属于这个链的堆使得第一个地址不是实际要释放的地址,第二次释放需要释放的地址时链表第一个地址就是两次释放之间释放的堆的地址,不会触发double free
的报错。
绕过对取出的堆的大小检查
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;
}
利用find_fake_fast
工具寻找离所求地址最近的可以伪造size
位符合要求的堆
unsorted bin
free到unsorted bin
源程序
#include <stdlib.h>
int main(int argc, char **argv){
void *p;
p = malloc(0x100);
malloc(0x100);
free(p);
return 0;
}
运行过程
运行至free到fastbin的判断堆是否在
fastbin
里不在
fastbin
之后判断是否是mmap
分配的,不是则继续运行else if (!chunk_is_mmapped(p)) {
如果没有互斥锁则加锁
if (! have_lock) { (void)mutex_lock(&av->mutex); locked = 1; }
获得下一个
chunk
的大小和指针到p
和size
,即p
指向下一个chunk
的地址,size
为下一个堆的大小nextchunk = chunk_at_offset(p, size);
检查该地址是否在分配区顶部,是则报错
if (__glibc_unlikely (p == av->top)) { errstr = "double free or corruption (top)"; goto errout; }
其中,
av
为堆所在的分配区地址判断下一个堆是否超出分配区的范围,判断方式:判断下一个堆的地址是否大于等于
av->top
加上av->top
的大小if (__builtin_expect (contiguous (av) && (char *) nextchunk >= ((char *) av->top + chunksize(av->top)), 0)) { errstr = "double free or corruption (out)"; goto errout; }
判断要释放的堆是否在
inuse
状态,判断方式:获取下一个堆的prev_inuse
值if (__glibc_unlikely (!prev_inuse(nextchunk))) { errstr = "double free or corruption (!prev)"; goto errout; }
获取下一个堆的大小并且判断下一个堆的大小是否合法
nextsize = chunksize(nextchunk); if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0) || __builtin_expect (nextsize >= av->system_mem, 0)) { errstr = "free(): invalid next size (normal)"; goto errout; }
清空堆中的内容
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
判断前一个堆是否被释放,如果被释放了则和前一个堆合并:获取前一个堆的大小,加到当前要释放的堆的
size
,并通过unlink将该chunk从空闲链表中脱离if (!prev_inuse(p)) { prevsize = p->prev_size; size += prevsize; p = chunk_at_offset(p, -((long) prevsize)); unlink(av, p, bck, fwd); }
判断下一个堆是否是
top chunk
,若是则与top chunk
合并,结束释放过程if (!prev_inuse(p)) { ... } else { size += nextsize; set_head(p, size | PREV_INUSE); av->top = p; check_chunk(av, p); }
如果不是,获取下一个堆的
inuse
位nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
判断下一个堆是否在使用,若已经被释放则合并到当前要释放的堆,并通过
unlink
将该chunk从空闲链表中脱离if (!nextinuse) { unlink(av, nextchunk, bck, fwd); size += nextsize;
若还在使用则将
prev_inuse
设为0表示当前堆已经被释放了} else clear_inuse_bit_at_offset(nextchunk, 0);
获取分配区中的
unsorted_bin
的第一个堆的地址到bck
,获取头结点fwd
bck = unsorted_chunks(av); fwd = bck->fd;
检查
fwd
的bk
是否是bck
,不是则报错if (__glibc_unlikely (fwd->bk != bck)) { errstr = "free(): corrupted unsorted chunks"; goto errout; }
将堆连接到
unsorted bin
中,即将要释放的堆的fd
改成fwd
,bk
改成bck
,bck
的fd
和fwd
的bk
设置成p
,将p
连到fwd
和bck
之间成为第一个,并且堆大小不在smallbin
范围内时设置其fd_nextsize
和bk_nextsize
为NULLp->fd = fwd; p->bk = bck; if (!in_smallbin_range(size)) { p->fd_nextsize = NULL; p->bk_nextsize = NULL; } bck->fd = p; fwd->bk = p;
从unsorted bin取出chunk
源代码
#include <stdlib.h>
int main(int argc, char **argv){
void *p;
p = malloc(0x100);
malloc(0x100);
free(p);
malloc(0x100);
return 0;
}
运行过程
运行到初次创建堆的调用
malloc_consolidate
整理fastbins
进入整理
unsorted bin
的大循环,一边整理一边查找合适的chunk
,找到即返回,结束创建过程int iters = 0; while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)) bck = victim->bk;
结束条件:遍历整理完
unsorted bin
或整理次数超过10000#define MAX_ITERS 10000 if (++iters >= MAX_ITERS) break;
获取
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), av);
获取
unsorted bin
的第一个chunk
的大小size = chunksize (victim);
将
bck->fd
的位置写入本 Unsorted Bin 的位置/* remove from unsorted list */ unsorted_chunks (av)->bk = bck; bck->fd = unsorted_chunks (av);
unsorted bin
的第一个chunk
与所申请chunk
精确匹配则直接返回/* Take now instead of binning if exact fit */ if (size == nb) { set_inuse_bit_at_offset (victim, size); //将匹配的的chunk设置为inuse if (av != &main_arena) victim->size |= NON_MAIN_ARENA; //若分配区非main_arena则设置为NON_MAIN_ARENA check_malloced_chunk (av, victim, nb); void *p = chunk2mem (victim); //返回堆的user data地址 alloc_perturb (p, bytes); return p; }
unsorted bin相关漏洞和绕过利用原理
利用unsorted bin泄露libc地址
释放一个堆到
unsorted bin
之后输出这个堆的fd
- 原理:将
p
连到fwd
和bck
之间成为倒数第二个堆的过程中时fwd = bck = main_arena
,连接之后被释放的堆的fd
和bk
均指向main_arena
- 原理:将
两个相同大小的unsorted bin合并,申请一个相同大小的堆块,此时残留fd,可以泄露libc
原理: 判断下一个堆已经被释放合并到当前要释放的堆并通过
unlink
将该chunk从空闲链表中脱离的时候不会清空堆里的内容,所以两个堆合并的时候保留了fd
和bk
,在申请的时候只要不覆盖掉堆里的内容就能够把main_arena
地址申请出来,两个堆必须地址连续if (!nextinuse) { unlink(av, nextchunk, bck, fwd); size += nextsize;
任意地址写为一个很大的数值
原理:将 bck->fd
的位置写入本 unsorted Bin
的位置,控制了bk
即可将unsorted_chunks (av)
写到任意地址(写入的地址要减两倍机器字长),将该堆申请出来就可以实现任意地址改为一个不可控的很大的数值
/* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
small bin
free到small bin
源代码
#include <stdlib.h>
int main(int argc, char **argv){
void *p;
p = malloc(0x100);
malloc(0x100);
free(p);
malloc(0x110);
return 0;
}
运行过程
运行到[从unsorted bin取出chunk](#从unsorted bin取出chunk)的将
bck->fd
的位置写入本 Unsorted Bin 的位置判断
unsorted bin
中循环到的堆是否和申请的堆大小精确匹配,不匹配则跳过if (size == nb)
判断是否属于
small bin
,属于则获取所在的small bin
链下标和头结点和首结点,并且将循环到的堆连接到small bin
的头部if (in_smallbin_range (size)) { victim_index = smallbin_index (size); bck = bin_at (av, victim_index); fwd = bck->fd; }
victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim;if (in_smallbin_range (size)) { victim_index = smallbin_index (size); bck = bin_at (av, victim_index); fwd = bck->fd; }
从small bin取出chunk
源代码
#include <stdlib.h>
int main(int argc, char **argv){
void *p;
p = malloc(0x100);
malloc(0x100);
free(p);
malloc(0x110);
malloc(0x100);
return 0;
}
运行过程
运行到初次创建堆的判断是否属于
smallbin
if (in_smallbin_range (nb))
获取申请的堆的大小所在的下标和地址
idx = smallbin_index (nb); bin = bin_at (av, idx);
判断所在的下标的链是否为空,为空则说明获取失败跳过该部分
if ((victim = last (bin)) != bin)
不为空则判断获取到的链表尾部的堆是否为空,为空则说明
small bin
未初始化,调用malloc_consolidate
进行初始化if ((victim = last (bin)) != bin) { if (victim == 0) /* initialization check */ malloc_consolidate (av);
不为空则先获取最后一个结点的下一个结点,判断下一个结点的
fd
是否为最后一个结点,不是则报错else { bck = victim->bk; if (__glibc_unlikely (bck->fd != victim)) { errstr = "malloc(): smallbin double linked list corrupted"; goto errout; }
通过安全检查之后将最后一个结点设置
inuse
和NON_MAIN_ARENA
位并且从链表中取出,返回该堆的地址指针
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;
large bin
free到large bin
源代码
#include <stdlib.h>
int main(int argc, char **argv){
void *p;
p = malloc(0x500);
malloc(0x500);
free(p);
malloc(0x550);
return 0;
}
运行过程
运行到[从unsorted bin取出chunk](#从unsorted bin取出chunk)的将
bck->fd
的位置写入本 Unsorted Bin 的位置判断是否在
small bin
,如果不在则在large bin
if (in_smallbin_range (size))
获取循环到的堆在
large bin
中的下标并且取得该链表的首结点bck
和头结点fwd
victim_index = largebin_index (size); bck = bin_at (av, victim_index); fwd = bck->fd;
判断头结点和首结点是否相同,相同则说明该链表为空,直接跳过一些判断和连接,将该堆插入在
fd
bk
双向链表的头部,并且设置其fd_nextsize
和bk_nextsize
都为其本身if (fwd != bck)
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;
若不相同,即
if
成立则说明该链中还有其他堆,首先获取到循环到的堆的大小去掉inuse
位之后的大小/* Or with inuse bit to speed comparisons */ size |= PREV_INUSE;
如果最后一个堆在
main_arena
则报错assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
如果循环到的堆的大小小于最小的堆那么插入在
fd_nextsize
nk_nextsize
链中最小的堆的后面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
,遍历中判断每一个堆是否属于main_arena
,属于则报错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); }
如果遍历到的堆和循环中的堆的大小相同则在
fd
bk
链表中插入到与其相同大小的堆的后面if ((unsigned long) size == (unsigned long) fwd->size) /* Always insert in the second position. */ fwd = fwd->fd;
否则就插入在
fd_nextsize
nk_nextsize
链中遍历到的堆的后面else { victim->fd_nextsize = fwd; victim->bk_nextsize = fwd->bk_nextsize; fwd->bk_nextsize = victim; victim->bk_nextsize->fd_nextsize = victim; }
并且插入到
fd
bk
链表中bck = fwd->bk;
mark_bin (av, victim_index); victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim;
从large bin取出chunk
源代码
#include <stdlib.h>
int main(int argc, char **argv){
void *p;
p = malloc(0x500);
malloc(0x500);
free(p);
malloc(0x550);
malloc(0x500);
return 0;
}
运行过程
运行到[free到large bin](#free到large bin)结束
判断是否不属于
small bin
,即是否属于large bin
if (!in_smallbin_range (nb))
获取申请的堆所在的
large bin
链的地址bin = bin_at (av, idx);
判断是否该链为空或者最大的堆太小不能符合申请的堆的大小,若是则直接结束对
large bin
中申请堆的判断,若符合则获取了第一个堆到victim
if ((victim = first (bin)) != bin && (unsigned long) (victim->size) >= (unsigned long) (nb))
在
fd_nextsize
bk_nextsize
链中循环遍历到第一个不小于申请的大小的堆victim = victim->bk_nextsize; while (((unsigned long) (size = chunksize (victim)) < (unsigned long) (nb))) victim = victim->bk_nextsize;
判断遍历到的堆不是尾结点并且它的大小等于它在
fd
bk
链上的上一个堆的大小if (victim != last (bin) && victim->size == victim->fd->size)
获取该大小的堆在
fd
bk
链上的第二个堆,因为第一个堆在fd_nextsize
bk_nextsize
链中,取出需要调整该链,但取出第二个堆就不需要调整链表victim = victim->fd;
保存该堆大小减去申请的大小的差值并且通过unlink操作从
large bin
链表中取出该堆remainder_size = size - nb; unlink (av, victim, bck, fwd);
如果差值小于最小的堆的大小,则直接将该堆返回
if (remainder_size < MINSIZE) { set_inuse_bit_at_offset (victim, size); //设置inuse位 if (av != &main_arena) victim->size |= NON_MAIN_ARENA;//设置NON_MAIN_ARENA位 }
void *p = chunk2mem (victim); alloc_perturb (p, bytes); return p; //获取并返回该堆的地址
如果差值大于最小的堆的大小则切割
large bin
,获取上面取到的堆切割了申请的大小的堆之后剩余的堆else { remainder = chunk_at_offset (victim, nb);
获取
unsorted bin
的首结点和头结点bck = unsorted_chunks (av); fwd = bck->fd;
检查头结点的
bk
指向的堆是否是首结点,若不是则报错if (__glibc_unlikely (fwd->bk != bck)) //检查头结点后面一个结点是否是首结点 { errstr = "malloc(): corrupted unsorted chunks"; goto errout; }
将剩余的堆插入
unsorted bin
remainder->bk = bck; remainder->fd = fwd; bck->fd = remainder; fwd->bk = remainder;
如果剩余的堆不在
small bin
的范围内则设置fd_nextsize
和bk_nextsize
if (!in_smallbin_range (remainder_size)) { remainder->fd_nextsize = NULL; remainder->bk_nextsize = NULL; }
返回切割的符合大小要求的堆的地址
check_malloced_chunk (av, victim, nb); void *p = chunk2mem (victim); alloc_perturb (p, bytes); //返回切割出来的申请的大小的堆地址 return p;
unlink
用来将一个双向链表(只存储空闲的 chunk)中的一个元素取出来
/* Take a chunk off a bin list */
// unlink p
#define unlink(AV, P, BK, FD) {
// 由于 P 已经在双向链表中,所以有两个地方记录其大小,所以检查一下其大小是否一致。
if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0))
malloc_printerr ("corrupted size vs. prev_size");
FD = P->fd;
BK = P->bk;
// 防止攻击者简单篡改空闲的 chunk 的 fd 与 bk 来实现任意写的效果。
if (__builtin_expect (FD->bk != P || BK->fd != P, 0))
malloc_printerr (check_action, "corrupted double-linked list", P, AV);
else {
FD->bk = BK;
BK->fd = FD;
// 下面主要考虑 P 对应的 nextsize 双向链表的修改
if (!in_smallbin_range (chunksize_nomask (P))
// 如果P->fd_nextsize为 NULL,表明 P 未插入到 nextsize 链表中。
// 那么其实也就没有必要对 nextsize 字段进行修改了。
// 这里没有去判断 bk_nextsize 字段,可能会出问题。
&& __builtin_expect (P->fd_nextsize != NULL, 0)) {
// 类似于小的 chunk 的检查思路
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);
// 这里说明 P 已经在 nextsize 链表中了。
// 如果 FD 没有在 nextsize 链表中
if (FD->fd_nextsize == NULL) {
// 如果 nextsize 串起来的双链表只有 P 本身,那就直接拿走 P
// 令 FD 为 nextsize 串起来的
if (P->fd_nextsize == P)
FD->fd_nextsize = FD->bk_nextsize = FD;
else {
// 否则我们需要将 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->fd_nextsize->bk_nextsize = P->bk_nextsize;
P->bk_nextsize->fd_nextsize = P->fd_nextsize;
}
}
}
}