musl1.2.1及之后,它的堆管理结构发生了巨大变化,因为musl1.2.0以及以前的代码存在巨大缺陷
所以musl1.2.2相当于重新看一遍源码(哭
- musl1.2.0以及之前的版本存在的缺陷
- musl1.2.2源码分析
- 结构体分析
- 基础操作函数
- static inline void queue(struct meta **phead, struct meta *m)
- static inline void dequeue(struct meta **phead, struct meta *m)
- static inline struct meta *dequeue_head(struct meta **phead)
- static inline struct meta *get_meta(const unsigned char *p)
- static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
- malloc
- alloc_meta
- size_to_class
- enframe
- alloc_slot
- try_avail
- alloc_group
- free
- nontrivial_free
- free_group
- 总结
- 参考
musl1.2.0以及之前的版本存在的缺陷
1.堆内存无限增长
我们在讲到小内存的时候,从操作系统申请的小内存释放后都由合适的bin表进行管理,下次再申请时,可以从合适的bin中取出可用的空闲小内存,如果找不到合适的小内存,再向操作系统申请新的小内存。这种只借不还的方式,若是管理不当,将会导致内存持续增长
glibc中有特殊机制,当持有的chunk满足一定条件后,会向系统返还内存
2.多线程场景下fork,子进程调用malloc存在死锁
linux下fork会只fork当前线程到子进程中,假设原进程有2个线程,其中一个线程持有了一个锁,另一个线程运行fork,这回导致新进程在申请持有这个锁时,会发生死锁(因为锁基本实现在用户态,方便快捷)
musl1.2.2源码分析
结构体分析
首先看第一个结构体
//全局变量
struct malloc_context {
uint64_t secret;//在每页的开头,用于校验,检查meta_area的check
#ifndef PAGESIZE
size_t pagesize; //没有定义pagesize就定义一个,一般都是4096
#endif
int init_done;//是否初始化完成
unsigned mmap_counter;//mmap内存总数
struct meta *free_meta_head;//freed meta组成的双向链表
struct meta *avail_meta;//指向可用的meta数组
size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift; //可用meta数量,可用的meta_area数量
struct meta_area *meta_area_head, *meta_area_tail;
unsigned char *avail_meta_areas;//当前可用meta_area位置
struct meta *active[48];//正在使用的meta数组,将chunk按大小分为了48类
size_t usage_by_class[48];//对应的大小使用了多少内存
uint8_t unmap_seq[32], bounces[32];
uint8_t seq;
uintptr_t brk;//使用brk开拓的heap的最高地址
};
(一个程序中有且只有一个,声明为ctx,位于bss段中)
它是 管理内存的最上级结构
下一个是 meta_area结构
struct meta_area {
uint64_t check;//用于校验,检查meta_area的check
struct meta_area *next;//下一个meta_area结构
int nslots;//当前使用的meta数量
struct meta slots[];//meta部分
};
结构是管理meta的
一般情况下,在初始化时,会申请一个pagesize(一般情况是4096)的内存(如果有heap,就在heap里,如果没有heap,就会用mmap申请)
然后这个page,开头放的是meta_area,剩下的全部都是meta(即一个meta_area里有很多个meta)
接下来看meta结构
struct meta {
struct meta *prev, *next;
struct group *mem;//该meta管理的group
volatile int avail_mask, freed_mask;//目前可用的bitmap,已经被释放的chunk的bitmap
uintptr_t last_idx:5;
uintptr_t freeable:1;
uintptr_t sizeclass:6;
uintptr_t maplen:8*sizeof(uintptr_t)-12;
};
每个meta对应一个group
group结构
struct group {
struct meta *meta;//指向管理该group的meta
unsigned char active_idx:5;
char pad[UNIT - sizeof(struct meta *) - 1];
unsigned char storage[];//分配给用户的内存
};
group结构是跟分配给 用户的内存 的最相关结构了。注意,一个group中的chunk大小都是一致的
用户的chunk结构(没有定义的,但是我们可用自己知道
struct chunk{
char prev_user_data[]; //一般情况下,这个字节都是保留项目'\x00'
uint8_t idx; //低5bit作为idx表示这是group中第几个chunk, 高3bit作为reserved
uint16_t offset; //与第一个chunk的偏移
char user_data[];
};
基础操作函数
基础操作部分函数都定义在meta.h内
static inline void queue(struct meta **phead, struct meta *m)
static inline void queue(struct meta **phead, struct meta *m)
{
assert(!m->next);//都必须是空指针
assert(!m->prev);
if (*phead) {
struct meta *head = *phead;
m->next = head;
m->prev = head->prev;
m->next->prev = m->prev->next = m;//插入双向链表
} else {//队列式空的, 就只有m自己
m->prev = m->next = m;
*phead = m;
}
}
static inline void dequeue(struct meta **phead, struct meta *m)
static inline void dequeue(struct meta **phead, struct meta *m)
{
if (m->next != m) {//如果队列里有多个meta
m->prev->next = m->next;
m->next->prev = m->prev;
//如果删除的是头, 那么就把队列头设置为下一个
if (*phead == m) *phead = m->next;
} else {
*phead = 0;
}
m->prev = m->next = 0;
}
static inline struct meta *dequeue_head(struct meta **phead)
static inline struct meta *dequeue_head(struct meta **phead)
{ //很简单
struct meta *m = *phead;
if (m) dequeue(phead, m);
return m;
}
static inline struct meta *get_meta(const unsigned char *p)
static inline struct meta *get_meta(const unsigned char *p)
{
assert(!((uintptr_t)p & 15));//p不是0x10的倍数就报错
int offset = *(const uint16_t *)(p - 2);//偏移
int index = get_slot_index(p);//获取slot的下标(
if (p[-4]) {//如果p[-4]有值不为0,说明是group的第一个chunk
assert(!offset);//如果offset不为0就抛出异常(因为是第一个chunk
offset = *(uint32_t *)(p - 8);
assert(offset > 0xffff);
}
const struct group *base = (const void *)(p - UNIT*offset - UNIT);//group base
const struct meta *meta = base->meta;//获得meta
assert(meta->mem == base);//check meta的mem必须和base相等
assert(index <= meta->last_idx);//check index必须小于等于last_idx
assert(!(meta->avail_mask & (1u<<index)));//如果这个块是可用块,报错
assert(!(meta->freed_mask & (1u<<index)));//这个块是free块,报错
const struct meta_area *area = (void *)((uintptr_t)meta & -4096);//获取meta_area的首地址
assert(area->check == ctx.secret);//check是否相同
if (meta->sizeclass < 48) {//sizeclass check
assert(offset >= size_classes[meta->sizeclass]*index);
assert(offset < size_classes[meta->sizeclass]*(index+1));
} else {
assert(meta->sizeclass == 63);
}
if (meta->maplen) {
assert(offset <= meta->maplen*4096UL/UNIT - 1);
}
return (struct meta *)meta;
}
static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
/*enframe()
先找到g中第idx个chunk的开始地址与结束地址
然后设置idx与offset等信息*/
static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
{
size_t stride = get_stride(g);//g负责多大的内存
size_t slack = (stride-IB-n)/UNIT;//chunk分配后的剩余内存: (0x30 - 4 - 0x20)/0x10 = 0
unsigned char *p = g->mem->storage + stride*idx;//使用这个meta管理的内存中第idx个chunk
unsigned char *end = p+stride-IB;////这个chunk结束的地方
// cycle offset within slot to increase interval to address
// reuse, facilitate trapping double-free.
//slot内循环偏移增加地址复用之间的间隔
//如果idx!=0, 那么就用chunk->offset设置off, 否则就用ctr
int off = (p[-3] ? *(uint16_t *)(p-2) + 1 : ctr) & 255;
assert(!p[-4]);
if (off > slack) {
size_t m = slack;
m |= m>>1; m |= m>>2; m |= m>>4;
off &= m;
if (off > slack) off -= slack+1;
assert(off <= slack);
}
if (off) {
// store offset in unused header at offset zero
// if enframing at non-zero offset.
*(uint16_t *)(p-2) = off;
p[-3] = 7<<5;
p += UNIT*off;
// for nonzero offset there is no permanent check
// byte, so make one.
p[-4] = 0;
}
*(uint16_t *)(p-2) = (size_t)(p-g->mem->storage)/UNIT;
p[-3] = idx;
set_size(p, end, n);
return p;
}
malloc
void *malloc(size_t n)
{
if (size_overflows(n)) return 0;//n太大,申请失败
struct meta *g;
uint32_t mask, first;
int sc;
int idx;
int ctr;
if (n >= MMAP_THRESHOLD) {//0x1ffec用mmap
size_t needed = n + IB + UNIT;
void *p = mmap(0, needed, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_ANON, -1, 0);
if (p==MAP_FAILED) return 0;
wrlock();
step_seq();
g = alloc_meta();//在已有的meta_arena中看看能不能找到可用的meta
if (!g) {//没有meta可用,分配失败,还需要解除p的map
unlock();
munmap(p, needed);
return 0;
}
g->mem = p;//mmap得到的内存相关信息记录在这个meta对象中
g->mem->meta = g;
g->last_idx = 0;
g->freeable = 1;
g->sizeclass = 63;//63表示mmap的
g->maplen = (needed+4095)/4096;//关于4096对齐
g->avail_mask = g->freed_mask = 0;//这时候申请了一个超大内存,group里也就一个chunk,所以这些mask都置0
// use a global counter to cycle offset in
// individually-mmapped allocations.
ctx.mmap_counter++;
idx = 0;
goto success;
}
sc = size_to_class(n);//将size转化为内部的类,musl把chunk大小分为48类,用size_to_class进行计算。与*active[48]对应,得到对应的索引
rdlock();
g = ctx.active[sc];//看看相应的meta是否已经存在了
// use coarse size classes initially when there are not yet
// any groups of desired size. this allows counts of 2 or 3
// to be allocated at first rather than having to start with
// 7 or 5, the min counts for even size classes.
if (!g && sc>=4 && sc<32 && sc!=6 && !(sc&1) && !ctx.usage_by_class[sc]) {//这个逻辑很怪(看起来像是一种策略,或者说是一种倾向
size_t usage = ctx.usage_by_class[sc|1];
// if a new group may be allocated, count it toward
// usage in deciding if we can use coarse class.
if (!ctx.active[sc|1] || (!ctx.active[sc|1]->avail_mask
&& !ctx.active[sc|1]->freed_mask))
usage += 3;
if (usage <= 12)
sc |= 1;
g = ctx.active[sc];
}
//在此meta中寻找一个chunk
for (;;) {
mask = g ? g->avail_mask : 0;// 取 avail_mask
first = mask&-mask; // 取第一个可用的chunk
if (!first) break;//没有可用chunk
if (RDLOCK_IS_EXCLUSIVE || !MT)
g->avail_mask = mask-first; // 将对应的mask置位,下面将要取出它
else if (a_cas(&g->avail_mask, mask, mask-first)!=mask)
continue;// 无锁时使用原子操作保证 avail_mask 的更新
idx = a_ctz_32(first); // 取2的指数,计算在group的idx
goto success;
}
upgradelock();
// 到这里表明对应的 meta 没有可用的chunk,需要寻找新的 meta 也说明对应 active 的项没有可用的空间需要更新
/*
- 如果这个group没法满足, 那就尝试从别的地方获取:
- 使用group中被free的chunk
- 使用队列中别的group
- 分配一个group
*/
idx = alloc_slot(sc, n);
if (idx < 0) {
unlock();
return 0;
}
g = ctx.active[sc];// 更新 meta
success:
ctr = ctx.mmap_counter;
unlock();
return enframe(g, idx, n, ctr); // 设置头部字段并将内存返回给用户
}
有几个注意的点,如果meta管理的group中有可用的空闲块的话,都是从avali_mask里面判断的,那么free_mask有什么用?这个之后会讲到。
看完大致的malloc后,里面有几个函数需要细看
alloc_meta
/*
alloc_meta()
先看有无初始化设置ctx的随机数
如果ctx的free_meta_head链表中有空闲的meta, 那么直接从这里分配一个meta
如果没有可用的, 那么就说明需要向OS申请内存存放meta
先通过brk分配1页,
如果brk失败的话则会通过mmap()分配许多页内存, 但是这些内存都是PROT_NONE的, 属于guard page, 堆溢出到这些页面会引发SIGV, 而meta不使用开头与结尾的一页, 防止被溢出
然后设置ctx中的meta_area_tail, avail_meta_cnt等信息, 把新分配的一页作为待划分的meta
*/
struct meta *alloc_meta(void)
{
struct meta *m;
unsigned char *p;
if (!ctx.init_done) {
#ifndef PAGESIZE
ctx.pagesize = get_page_size();
#endif
ctx.secret = get_random_secret();
ctx.init_done = 1;
}
size_t pagesize = PGSZ;
if (pagesize < 4096) pagesize = 4096;//pagesize 最大为4096
if ((m = dequeue_head(&ctx.free_meta_head))) return m;//如果能直接找到空闲meta,脱链后直接返回就行
if (!ctx.avail_meta_count) { // 没有空闲meta,需要开拓新的meta_area
int need_unprotect = 1;
if (!ctx.avail_meta_area_count && ctx.brk!=-1) {//没有可用meta_area并且有heap堆的
uintptr_t new = ctx.brk + pagesize;
int need_guard = 0;
if (!ctx.brk) {
need_guard = 1;
ctx.brk = brk(0);
// some ancient kernels returned _ebss
// instead of next page as initial brk.
ctx.brk += -ctx.brk & (pagesize-1);
new = ctx.brk + 2*pagesize;
}
if (brk(new) != new) {
ctx.brk = -1;
} else {
if (need_guard) mmap((void *)ctx.brk, pagesize,
PROT_NONE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
ctx.brk = new;
ctx.avail_meta_areas = (void *)(new - pagesize);
ctx.avail_meta_area_count = pagesize>>12;//4096算一个meta_area
need_unprotect = 0;
}
}
if (!ctx.avail_meta_area_count) {//没有可用meta_area,但是没有heap堆的,需要mmap
size_t n = 2UL << ctx.meta_alloc_shift;
p = mmap(0, n*pagesize, PROT_NONE,
MAP_PRIVATE|MAP_ANON, -1, 0);
if (p==MAP_FAILED) return 0;
ctx.avail_meta_areas = p + pagesize;
ctx.avail_meta_area_count = (n-1)*(pagesize>>12);
ctx.meta_alloc_shift++;
}
p = ctx.avail_meta_areas; //如果avail_meta_areas与4K对齐, 那么就说明这片区域是刚刚申请的一页, 所以需要修改内存的权限
if ((uintptr_t)p & (pagesize-1)) need_unprotect = 0;
if (need_unprotect)
if (mprotect(p, pagesize, PROT_READ|PROT_WRITE)
&& errno != ENOSYS)
return 0;
ctx.avail_meta_area_count--;
ctx.avail_meta_areas = p + 4096;
if (ctx.meta_area_tail) {//插入meta_area链表
ctx.meta_area_tail->next = (void *)p;
} else {
ctx.meta_area_head = (void *)p;
}
ctx.meta_area_tail = (void *)p;
ctx.meta_area_tail->check = ctx.secret;
ctx.avail_meta_count = ctx.meta_area_tail->nslots
= (4096-sizeof(struct meta_area))/sizeof *m;//更新可用meta
ctx.avail_meta = ctx.meta_area_tail->slots;
}
ctx.avail_meta_count--; //可用meta的数量减1
m = ctx.avail_meta++;//可用meta数组指针+1,指向下一个可用meta
m->prev = m->next = 0;
return m;
}
从 alloc_meta里可用看出 在没有meta可用时,会申请一个PAGESIZE的空间作为新的meta_arena来存放meta(如果有堆就从堆里拿,没有堆就mmap),meta_arena是有限的。这一部分的逻辑还是很清楚的。
size_to_class
根据申请的大小划分成不同的chunk,这个逻辑我没有看,直接用人现成的结论了
0x0 ~ 0xc ->0
0xd ~ 0x1c ->1
0x1d ~ 0x2c ->2
0x2d ~ 0x3c ->3
0x3d ~ 0x4c ->4
0x4d ~ 0x5c ->5
0x5d ~ 0x6c ->6
0x6d ~ 0x7c ->7
0x7d ~ 0x8c ->8
0x8d ~ 0x9c ->9
0x9d ~ 0xbc ->10
0xbd ~ 0xec ->11
0xed ~ 0x11c ->12
0x11d ~ 0x13c ->13
0x13d ~ 0x18c ->14
0x18d ~ 0x1ec ->15
0x1ed ~ 0x23c ->16
0x23d ~ 0x29c ->17
0x29d ~ 0x31c ->18
0x31d ~ 0x3ec ->19
0x3ed ~ 0x47c ->20
0x47d ~ 0x53c ->21
0x53d ~ 0x65c ->22
0x65d ~ 0x7ec ->23
0x7ed ~ 0x91c ->24
0x91d ~ 0xa9c ->25
0xa9d ~ 0xcbc ->26
0xcbd ~ 0xfec ->27
0xfed ~ 0x123c ->28
0x123d ~ 0x153c ->29
0x153d ~ 0x198c ->30
0x198d ~ 0x1fec ->31
0x1fed ~ 0x247c ->32
0x247d ~ 0x2a9c ->33
0x2a9d ~ 0x331c ->34
0x331d ~ 0x3fec ->35
0x3fed ~ 0x490c ->36
0x490d ~ 0x553c ->37
0x553d ~ 0x664c ->38
0x664d ~ 0x7fec ->39
0x7fed ~ 0x923c ->40
0x923d ~ 0xaa9c ->41
0xaa9d ~ 0xccbc ->42
0xccbd ~ 0xffec ->43
0xffed ~ 0x1247c ->44
0x1247d ~ 0x1553c ->45
0x1553d ~ 0x1997c ->46
enframe
/*enframe()
先找到g中第idx个chunk的开始地址与结束地址
然后设置idx与offset等信息*/
static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
{
size_t stride = get_stride(g);//g负责多大的内存
size_t slack = (stride-IB-n)/UNIT;//chunk分配后的剩余内存: (0x30 - 4 - 0x20)/0x10 = 0
unsigned char *p = g->mem->storage + stride*idx;//使用这个meta管理的内存中第idx个chunk
unsigned char *end = p+stride-IB;////这个chunk结束的地方
// cycle offset within slot to increase interval to address
// reuse, facilitate trapping double-free.
//slot内循环偏移增加地址复用之间的间隔
//如果idx!=0, 那么就用chunk->offset设置off, 否则就用ctr
int off = (p[-3] ? *(uint16_t *)(p-2) + 1 : ctr) & 255;
assert(!p[-4]);
if (off > slack) {
size_t m = slack;
m |= m>>1; m |= m>>2; m |= m>>4;
off &= m;
if (off > slack) off -= slack+1;
assert(off <= slack);
}
if (off) {
// store offset in unused header at offset zero
// if enframing at non-zero offset.
*(uint16_t *)(p-2) = off;
p[-3] = 7<<5;
p += UNIT*off;
// for nonzero offset there is no permanent check
// byte, so make one.
p[-4] = 0;
}
*(uint16_t *)(p-2) = (size_t)(p-g->mem->storage)/UNIT;
p[-3] = idx;
set_size(p, end, n);
return p;
}
alloc_slot
这个函数还是比较重要的,在对应的可用meta中没有可用chunk了,说明可用meta链表需要更新了
/*
首先会通过try_avail()在以下位置寻找可用的chunk,
freed_mask中
这个队列别的meta中
如果失败,或者这个队列本来就空, 那么就会调用alloc_group()直接分配一个新的meta与对应的group
然后调用queue插入ctx.avtive[sc]这个队列中
*/
static int alloc_slot(int sc, size_t req)
{
uint32_t first = try_avail(&ctx.active[sc]);// 尝试在对应类的meta的链表寻找可分配的内存
if (first) return a_ctz_32(first);
struct meta *g = alloc_group(sc, req);// 找不到对应的meta,开始申请group ,当然,同时间找一个meta和它对应
if (!g) return -1;
g->avail_mask--; // 第一个chunk被使用了,因为是刚刚申请的,所以avali要减1
queue(&ctx.active[sc], g);//加入队列
return 0;
}
这里面还有几个函数需要了解
try_avail
/*
try_avail()
首先会再次尝试从avail_mask分配
然后查看这个meta中freed_mask中有无chunk,
如果freed_mask为空, 说明这个meta全部分配出去了, 就从队列中取出
如果有的话就会通过active_group()把freed_mask中的chunk转移到avail_mask中
*/
static uint32_t try_avail(struct meta **pm)
{
struct meta *m = *pm;
uint32_t first;
if (!m) return 0;//链上没有其他meta了
uint32_t mask = m->avail_mask;
if (!mask) {// 没有可用的chunk
if (!m) return 0;
if (!m->freed_mask) {// 没有被free的chunk,说明所有的chunk都被分配出去了
dequeue(pm, m);// 将当前meta从链表中取出,unlink操作,更新对应数组项,即脱链
m = *pm;// 更新后的meta
if (!m) return 0;// 如果更新后的为null,直接返回
} else {
m = m->next; // 这里应该是优先使用下一个meta,这样链表中的meta都是循环使用的,减少了dequeue操作
*pm = m; //否则pm使用m的下一个作为队列开头, 应该是为了每次malloc与free的时间均衡
}
mask = m->freed_mask;//看一下group中被free的chunk
// skip fully-free group unless it's the only one
// or it's a permanently non-freeable group
// 如果当前meta中的chunk全被free,并且当前meta管理的内存可用被free
// 那么优先使用下一个,这里应该是为了将全被free的内存返回给系统,减少占用
//如果这个group所有的chunk都被释放了, 那么就尝试使用下一个group, 应该是为了每次malloc与free的时间均衡
if (mask == (2u<<m->last_idx)-1 && m->freeable) {
m = m->next;
*pm = m;
mask = m->freed_mask;
}
// activate more slots in a not-fully-active group
// if needed, but only as a last resort. prefer using
// any other group with free slots. this avoids
// touching & dirtying as-yet-unused pages.
// ((2u << m->mem->active_idx) - 1)建立一个掩码, 如果acctive_idx为3, 那么就是0b1111
if (!(mask & ((2u<<m->mem->active_idx)-1))) {// //如果这个group中有free的chunk, 但是不满足avtive_idx的要求
if (m->next != m) {// //如果meta后面还有meta, 那么就切换到后一个meta, 由于avail与free都为0的group已经在上一步出队了, 因此后一个group一定有满足要求的chunk
m = m->next;
*pm = m;
} else {
int cnt = m->mem->active_idx + 2;
int size = size_classes[m->sizeclass]*UNIT;
int span = UNIT + size*cnt;
// activate up to next 4k boundary
while ((span^(span+size-1)) < 4096) {
cnt++;
span += size;
}
if (cnt > m->last_idx+1)
cnt = m->last_idx+1;
m->mem->active_idx = cnt-1;
}
}
mask = activate_group(m);//激活这个group, 把free的chunk转移到avail中,其实就是交换下bitmap的事
assert(mask);
decay_bounces(m->sizeclass);
}
first = mask&-mask;
m->avail_mask = mask-first;
return first;
}
可用看到,如果可用的meta上所有的内存都被分配出去了,那么需要把它从可用meta链上脱去
总之就是让chunk从free状态变成可用状态。换句话说,释放的chunk没有立刻返还给系统,而是自己保留并置为free之后可用再用
alloc_group
/*
首先会通过alloc_meta()分配一个meta, 用来管理后面分配的group
计算好需要的长度后通过mmap()匿名映射一片内存作为group
然后初始化meta中相关信息*/
static struct meta *alloc_group(int sc, size_t req)
{
size_t size = UNIT*size_classes[sc];//计算大小
int i = 0, cnt;
unsigned char *p;
struct meta *m = alloc_meta();//分配group前先分配一个meta用来管理group
if (!m) return 0;
size_t usage = ctx.usage_by_class[sc];
size_t pagesize = PGSZ;
int active_idx;
if (sc < 9) {
while (i<2 && 4*small_cnt_tab[sc][i] > usage)
i++;
cnt = small_cnt_tab[sc][i];
} else {
// lookup max number of slots fitting in power-of-two size
// from a table, along with number of factors of two we
// can divide out without a remainder or reaching 1.
cnt = med_cnt_tab[sc&3];
// reduce cnt to avoid excessive eagar allocation.
while (!(cnt&1) && 4*cnt > usage)
cnt >>= 1;
// data structures don't support groups whose slot offsets
// in units don't fit in 16 bits.
while (size*cnt >= 65536*UNIT)
cnt >>= 1;
}
// If we selected a count of 1 above but it's not sufficient to use
// mmap, increase to 2. Then it might be; if not it will nest.
if (cnt==1 && size*cnt+UNIT <= pagesize/2) cnt = 2;
// All choices of size*cnt are "just below" a power of two, so anything
// larger than half the page size should be allocated as whole pages.
if (size*cnt+UNIT > pagesize/2) {
// check/update bounce counter to start/increase retention
// of freed maps, and inhibit use of low-count, odd-size
// small mappings and single-slot groups if activated.
int nosmall = is_bouncing(sc);
account_bounce(sc);
step_seq();
// since the following count reduction opportunities have
// an absolute memory usage cost, don't overdo them. count
// coarse usage as part of usage.
if (!(sc&1) && sc<32) usage += ctx.usage_by_class[sc+1];
// try to drop to a lower count if the one found above
// increases usage by more than 25%. these reduced counts
// roughly fill an integral number of pages, just not a
// power of two, limiting amount of unusable space.
if (4*cnt > usage && !nosmall) {
if (0);
else if ((sc&3)==1 && size*cnt>8*pagesize) cnt = 2;
else if ((sc&3)==2 && size*cnt>4*pagesize) cnt = 3;
else if ((sc&3)==0 && size*cnt>8*pagesize) cnt = 3;
else if ((sc&3)==0 && size*cnt>2*pagesize) cnt = 5;
}
size_t needed = size*cnt + UNIT;
needed += -needed & (pagesize-1);
// produce an individually-mmapped allocation if usage is low,
// bounce counter hasn't triggered, and either it saves memory
// or it avoids eagar slot allocation without wasting too much.
if (!nosmall && cnt<=7) {
req += IB + UNIT;
req += -req & (pagesize-1);
if (req<size+UNIT || (req>=4*pagesize && 2*cnt>usage)) {
cnt = 1;
needed = req;
}
}
//映射一片内存作为group, 被一开始分配的meta管理
p = mmap(0, needed, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0);
if (p==MAP_FAILED) {
free_meta(m);
return 0;
}
m->maplen = needed>>12;
ctx.mmap_counter++;
active_idx = (4096-UNIT)/size-1;
if (active_idx > cnt-1) active_idx = cnt-1;
if (active_idx < 0) active_idx = 0;
} else {
int j = size_to_class(UNIT+cnt*size-IB);
int idx = alloc_slot(j, UNIT+cnt*size-IB);
if (idx < 0) {
free_meta(m);
return 0;
}
struct meta *g = ctx.active[j];
p = enframe(g, idx, UNIT*size_classes[j]-IB, ctx.mmap_counter);
m->maplen = 0;
p[-3] = (p[-3]&31) | (6<<5);
for (int i=0; i<=cnt; i++)
p[UNIT+i*size-4] = 0;
active_idx = cnt-1;
}
ctx.usage_by_class[sc] += cnt;
m->avail_mask = (2u<<active_idx)-1;
m->freed_mask = (2u<<(cnt-1))-1 - m->avail_mask;
m->mem = (void *)p;
m->mem->meta = m;
m->mem->active_idx = active_idx;
m->last_idx = cnt-1;
m->freeable = 1;
m->sizeclass = sc;
return m;
}
这段逻辑也挺迷的,总之就是mmap了一个需要size的内存空间交给group来使用(group里不只有一个chunk)。
free
看完malloc相关,接下来我们来看看free相关的源码
/*先通过get_meta()找到chunk对应的meta
然后重置idx与offset
然后再meta的freed_mask中标记一下就算释放完毕了
然后调用nontrivial_free()处理meta相关操作*/
void free(void *p)
{
if (!p) return;
struct meta *g = get_meta(p);//获得对应的meta
int idx = get_slot_index(p);//看看位于meta中的第几个chunk
size_t stride = get_stride(g); // 获取group中一个chunk的大小,步幅
unsigned char *start = g->mem->storage + stride*idx;// chunk的起始地址
unsigned char *end = start + stride - IB;// chunk的结尾地址,减去一个chunk的头部大小
get_nominal_size(p, end);// 根据reserved来算真实大小
uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1;//计算这个chunk的bitmap
((unsigned char *)p)[-3] = 255;//idx与offset都无效
// invalidate offset to group header, and cycle offset of
// used region within slot if current offset is zero.
*(uint16_t *)((char *)p-2) = 0;//idx与offset都无效
// release any whole pages contained in the slot to be freed
// unless it's a single-slot group that will be unmapped.
// 如果该group中的chunk比页大,并且包含多个chunk,则将group到这个chunk的这段空间交给操作系统处置,程序提出建议free。madvise的操作不再赘述
//释放slot中的一整页
if (((uintptr_t)(start-1) ^ (uintptr_t)end) >= 2*PGSZ && g->last_idx) {
unsigned char *base = start + (-(uintptr_t)start & (PGSZ-1));
size_t len = (end-base) & -PGSZ;
if (len) madvise(base, len, MADV_FREE);
}
// atomic free without locking if this is neither first or last slot
//在meta->freed_mask中标记一下, 表示这个chunk已经被释放了
//如果既不是中间的slot也不是末尾的slot, 那么释放时不需要锁
for (;;) {// 设置对应的mask,但是free的chunk并不会马上avail
uint32_t freed = g->freed_mask;
uint32_t avail = g->avail_mask;
uint32_t mask = freed | avail;//mask = 所有被释放的chunk + 现在可用的chunk
assert(!(mask&self));//要释放的chunk应该既不在freed中, 也不在avail中
/*
- 两种不能只设置meta的mask的情况, 这两种情况不设置mask, break后调用nontrivial_free()处理
- 如果!freed, 就说明meta中没有被释放的chunk, 有可能这个group全部被分配出去了, 这样group是会弹出avtive队列的,
而现在释放了一个其中的chunk, 需要条用nontrivial_free()把这个group重新加入队列
- 如果mask+self==all, 那就说明释放了这个chunk, 那么这个group中所有的chunk都被回收了,
因此这个meta需要调用nontrivial_free()回收这个group
*/
//设置freed_mask, 表示这个chunk被释放了
if (!freed || mask+self==all) break;
if (!MT)//如果是单线程,直接写就好了
g->freed_mask = freed+self;
else if (a_cas(&g->freed_mask, freed, freed+self)!=freed)
continue;//如遇多线程使用原子操作, 一直循环到g->freed_mask为freed+self为止
return;
}
wrlock();
struct mapinfo mi = nontrivial_free(g, idx);//处理涉及到meta之间的操作
unlock();
if (mi.len) munmap(mi.base, mi.len);//free
}
这里看到,一般情况下free只是设置free_mask,除非这个group所有的chunk都是free的
会跳到nontrivial_free函数来进行
当group全空闲,会释放group,group会被unmap掉
nontrivial_free
/*nontrivial_free()
根据free()进入这个函数的方式可以知道, 此时还没有设置freed_mask
如果发现这个group中所有的chunk要么被free, 要么是可用的, 那么就会回收掉这个group
先调用dequeue从队列中出队
如果队里中后面还有meta的话, 就会激活后一个meta
然后调用free_group()释放整个group
如果发现mask为空
那么说明malloc分配出最后一个chunk的时候已经把这个meta给弹出队列了
但是现在里面有一个chunk被释放了, 这个meta就应该再次回归队列, 因此调用queue()再次入队*/
static struct mapinfo nontrivial_free(struct meta *g, int i)
{
uint32_t self = 1u<<i;
int sc = g->sizeclass;
uint32_t mask = g->freed_mask | g->avail_mask;
// //如果group中所有chunk要么被释放要么可使用, 并且g可以被释放, 那么就要回收掉整个meta
if (mask+self == (2u<<g->last_idx)-1 && okay_to_free(g)) {
// any multi-slot group is necessarily on an active list
// here, but single-slot groups might or might not be.
if (g->next) {
assert(sc < 48);
int activate_new = (ctx.active[sc]==g);
dequeue(&ctx.active[sc], g);//出队
if (activate_new && ctx.active[sc])
activate_group(ctx.active[sc]);//激活下一个meta,因为之前为了free的快速, 只是用freed_mask标记了一下而已, 现在要转移到avail_mask中了
}
return free_group(g); // free掉这个group,也会free掉对应的meta将其加入free_meta链表
} else if (!mask) {
assert(sc < 48);
// might still be active if there were no allocations
// after last available slot was taken.
if (ctx.active[sc] != g) {
queue(&ctx.active[sc], g);//入队
}
}
a_or(&g->freed_mask, self);// 更新mask
return (struct mapinfo){ 0 };
}
free_group
static struct mapinfo free_group(struct meta *g)
{
struct mapinfo mi = { 0 };
int sc = g->sizeclass;
if (sc < 48) {
ctx.usage_by_class[sc] -= g->last_idx+1;
}
if (g->maplen) {
step_seq();
record_seq(sc);
mi.base = g->mem;
mi.len = g->maplen*4096UL;
} else {
void *p = g->mem;
struct meta *m = get_meta(p);
int idx = get_slot_index(p);
g->mem->meta = 0;
// not checking size/reserved here; it's intentionally invalid
mi = nontrivial_free(m, idx);
}
free_meta(g);
return mi;
}
到这一部分,解除group和meta的联系,meta加入了free_meta链中
总结
这个流程比之前不知道复杂了多少,而且可能还加入了一些人的行为特征分析的新操作
但是还是有迹可循的,安全问题也比之前的1.1.24高了不少