//v1.2.0 src/malloc/malloc.c中 /* pretrim - trims a chunk _prior_ to removing it from its bin. * Must be called with i as the ideal bin for size n, j the bin * for the _free_ chunk self, and bin j locked. */ staticintpretrim(struct chunk *self, size_t n, int i, int j) { size_t n1; structchunk *next, *split;
/* We cannot pretrim if it would require re-binning. */ if (j < 40) return0;// 条件 1:j(大小最接近size的可用bin下标)大于 40 // 条件 2: j(大小最接近size的可用bin下标)与i(计算出来的bin下标)相隔 3 个 bin 或以上， // 或者j(大小最接近size的可用bin下标)等于63且size相差大于 MMAP_THRESHOLD(0x38000) if (j < i+3) { if (j != 63) return0; n1 = CHUNK_SIZE(self); if (n1-n <= MMAP_THRESHOLD) return0; } else { n1 = CHUNK_SIZE(self); } //条件3: size相差的数值属于bins[j]的范围内，即split与self属于同一个bin if (bin_index(n1-n) != j) return0;
// ldso/dynlink.c L526-L552 /* A huge hack: to make up for the wastefulness of shared libraries * needing at least a page of dirty memory even if they have no global * data, we reclaim the gaps at the beginning and end of writable maps * and "donate" them to the heap. */
staticvoidreclaim(struct dso *dso, size_t start, size_t end) { // 避开 RELRO 段 if (start >= dso->relro_start && start < dso->relro_end) start = dso->relro_end; if (end >= dso->relro_start && end < dso->relro_end) end = dso->relro_start; if (start >= end) return; char *base = laddr_pg(dso, start); // 使用 __malloc_donate 函数将内存释放到 bin 中 __malloc_donate(base, base+(end-start)); }
for i inrange(8): add_malloc(0x2c) edit(i,0x10,p8(i)*0x10) for i inrange(0,7): free(i) dbg() add_malloc(0x2c) add_malloc(0x2c) pause() add_malloc(0x2c) edit(10,0x10,p8(0x11)*0x10) pause()
//v1.2.1 /src/malloc/mallocng/malloc.c void *malloc(size_t n) { if (size_overflows(n)) return0;//是否超过申请的最大值，这个最大值不知道多少 /* static inline int size_overflows(size_t n) { if (n >= SIZE_MAX/2 - 4096) { errno = ENOMEM; return 1; } return 0; } */ structmeta *g; uint32_t mask, first; int sc; int idx; int ctr;
//mmap分配 #define MMAP_THRESHOLD 131052(0x1FFEC) if (n >= MMAP_THRESHOLD) { 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) return0; wrlock(); step_seq(); g = alloc_meta(); if (!g) { unlock(); munmap(p, needed); return0; } //记录分配信息 g->mem = p; g->mem->meta = g; g->last_idx = 0; g->freeable = 1; g->sizeclass = 63;//meta的sizeclass为63代表mmap分配 g->maplen = (needed+4095)/4096; g->avail_mask = g->freed_mask = 0; // use a global counter to cycle offset in // individually-mmapped allocations. //记录分配个数 ctx.mmap_counter++; idx = 0; goto success; }
//寻找size对应的meta，ctx.active[sc] sc = size_to_class(n); rdlock(); g = ctx.active[sc];
// 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. //对应size的meta为空且4=<sc<=32且不等于6且为偶数并且该sc没有正在使用的chunk //那么申请的chunk就会从sc+1开始申请，比如申请0x8c，对应的sc应该是8，但是由于 //满足这个条件，sc为8的meta没有正在使用的chunk，对应就会从sc+1=9处开始申请 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]; }
//取到avail_mask最低位的1，置零之后计算idx //根据idx从group中寻找可用chunk for (;;) { //meta中的可用内存的bitmap, 如果g为0那么就设为0, 表示没有可用chunk mask = g ? g->avail_mask : 0; //找到avail_mask的bit中第一个为1的bit first = mask&-mask; //如果没找到就停止 if (!first) break; //设置avail_mask中first对应的bit为0 //下面是锁机制，不太懂 if (RDLOCK_IS_EXCLUSIVE || !MT) g->avail_mask = mask-first; elseif (a_cas(&g->avail_mask, mask, mask-first)!=mask) continue; //找到之后设置avail_mask之后转为idx, 结束 idx = a_ctz_32(first); goto success; } upgradelock();
idx = alloc_slot(sc, n); if (idx < 0) { unlock(); return0; } //找到对应meta g = ctx.active[sc];
//v1.2.1 /src/malloc/mallocng/malloc.c staticuint32_ttry_avail(struct meta **pm) { structmeta *m = *pm; uint32_t first; if (!m) return0;//如果ctx.active[sc]==NULL, 即该队列为空，直接返回
//ctx.active[sc]对应的meta-group的avail_mask中无可用chunk uint32_t mask = m->avail_mask; if (!mask) { if (!m) return0; //ctx.active[sc]对应的meta-group的freed_mask中也没有chunk时 //代表都在使用中，从队列中弹出该meta-group if (!m->freed_mask) { dequeue(pm, m); m = *pm; if (!m) return0; } else { //获取队列中下一个meta-group m = m->next; *pm = m; } //如果这个meta-group中所有的chunk都被释放了, 那么就再下一个meta-group //即不从下一个全free或者没有申请chunk的meta-group中申请chunk mask = m->freed_mask; // skip fully-free group unless it's the only one // or it's a permanently non-freeable group 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. if (!(mask & ((2u<<m->mem->active_idx)-1))) { if (m->next != m) { 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; } } //重新设置这个meta-group，freed_mask和avail_mask的设置 mask = activate_group(m); /*其实也就是设置设置一下freed_mask和avail_mask static inline uint32_t activate_group(struct meta *m) { assert(!m->avail_mask); uint32_t mask, act = (2u<<m->mem->active_idx)-1; do mask = m->freed_mask; while (a_cas(&m->freed_mask, mask, mask&~act)!=mask); return m->avail_mask = mask & act; } */ assert(mask); decay_bounces(m->sizeclass); } //取出 first = mask&-mask; m->avail_mask = mask-first; return first; }
//v1.2.1 /src/malloc/mallocng/malloc.c //用来分配一个新的group static struct meta *alloc_group(int sc, size_t req) { size_t size = UNIT*size_classes[sc]; int i = 0, cnt; unsignedchar *p; //先分配一个meta管理group structmeta *m = alloc_meta(); if (!m) return0; 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); elseif ((sc&3)==1 && size*cnt>8*pagesize) cnt = 2; elseif ((sc&3)==2 && size*cnt>4*pagesize) cnt = 3; elseif ((sc&3)==0 && size*cnt>8*pagesize) cnt = 3; elseif ((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; } }
//v1.2.1 /src/malloc/mallocng/meta.h //分配chunk时，设置group用的函数 staticinlinevoid *enframe(struct meta *g, int idx, size_t n, int ctr) { size_t stride = get_stride(g); size_t slack = (stride-IB-n)/UNIT; unsignedchar *p = g->mem->storage + stride*idx; unsignedchar *end = p+stride-IB; // cycle offset within slot to increase interval to address // reuse, facilitate trapping double-free. 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; }
voidfree(void *p) { if (!p) return; //获取相关信息 structmeta *g = get_meta(p); int idx = get_slot_index(p); size_t stride = get_stride(g); unsignedchar *start = g->mem->storage + stride*idx; unsignedchar *end = start + stride - IB; get_nominal_size(p, end); //计算这个chunk对应avail_mask和freed_mask的bitmap uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1; ((unsignedchar *)p)[-3] = 255; // invalidate offset to group header, and cycle offset of // used region within slot if current offset is zero. *(uint16_t *)((char *)p-2) = 0;
// release any whole pages contained in the slot to be freed // unless it's a single-slot group that will be unmapped. if (((uintptr_t)(start-1) ^ (uintptr_t)end) >= 2*PGSZ && g->last_idx) { unsignedchar *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已经被释放了 for (;;) { uint32_t freed = g->freed_mask; uint32_t avail = g->avail_mask; uint32_t mask = freed | avail; assert(!(mask&self));//要释放的chunk应该既不在freed中, 也不在avail中 /* 1.如果满足 mask+self==all , 那就说明释放了这个chunk之后这个group 中所有chunk都被释放,就需要调用nontrivial_free回收整个meta-group 因此这个meta需要调用nontrivial_free()回收这个group 2.如果满足 !freed ,那么就说明该meta-group中没有被释放的chunk,有可能是第一次从该 有可能这个group全部被分配出去了, 这样group是会弹出avtive队列的, 而现在释放了一个 其中的chunk,所以需要调用nontrivial_free()把这个group重新加入队列 */ if (!freed || mask+self==all) break; //线程方面的一些知识，还不是太会 if (!MT) g->freed_mask = freed+self; elseif (a_cas(&g->freed_mask, freed, freed+self)!=freed) continue; return; }
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;
//如果meta-group中所有chunk要么被释放要么可使用 //并且g可以被释放(不是mmap出来的),那么就要回收掉整个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) { //检查sc释放合法, 不是mmap(63)的 assert(sc < 48); //如果g是队列中开头的meta, 那么弹出队列后, 要激活后一个 int activate_new = (ctx.active[sc]==g); dequeue(&ctx.active[sc], g); //激活后一个meta过程中需要完成avail_mask和free_mask的设置 //即free_mask向avail_maks进行转移 if (activate_new && ctx.active[sc]) activate_group(ctx.active[sc]); } //现在要释放这个meta-group,放入ctx.free_meta_head中 return free_group(g); } //如果mask==0, 也就是这个meta-group中所有的chunk都被分配出去了 elseif (!mask) { assert(sc < 48); // might still be active if there were no allocations // after last available slot was taken. //现在这个全部chunk被分配出去的group中有一个chunk要被释放了 //因此这个meta-group要重新入队 if (ctx.active[sc] != g) { queue(&ctx.active[sc], g); } } a_or(&g->freed_mask, self); return (struct mapinfo){ 0 }; }
②dequeue
1 2 3 4 5 6 7 8 9 10 11 12 13
//v1.2.1 /src/malloc/mallocng/meta.h //meta的出队操作，一般漏洞点出在这里 staticinlinevoiddequeue(struct meta **phead, struct meta *m) { if (m->next != m) { m->prev->next = m->next; m->next->prev = m->prev; if (*phead == m) *phead = m->next; } else { *phead = 0; } m->prev = m->next = 0; }
