【技术分享】musl-1.2.x堆部分源码分析

简 介

musl libc 是一个专门为嵌入式系统开发的轻量级 libc 库，以简单、轻量和高效率为特色。有不少 Linux 发行版将其设为默认的 libc 库，用来代替体积臃肿的 glibc ，如 Alpine Linux（做过 Docker 镜像的应该很熟悉）、OpenWrt（常用于路由器）和 Gentoo 等

1.2.x采用src/malloc/mallocng内的代码，其堆管理结构与早期版本几乎完全不同，而早期的堆管理器则放入了src/malloc/oldmalloc中。

数据结构

chunk: 最基础的管理单位, 关于0x10B对齐, 存在空间复用, musl里面没有专门的struct, 比较坑, 假设p指向用户数据开头

p[-2], p[-1]这2B数据组成的uint_16, 代表offset, 表示与group中第一个地址的偏移

p[-3]&31组成的5bit代表idx, 表示这是group中第几个slot

那么p-0x10到p均为元数据, 作为group的头, 定义可以看struct group

如果是group中第一个chunk,

如果不是第一个chunk, 那么p-4到p为元数据

如果一个chunk已经被释放, 那么就会设置offset为0, index为0xFF

因此申请0x2c空间, 最终分配到的chunk_size = (0x2c+4B元数据空间)align to 0x10 = 0x30

struct chunk{ char prev_user_data[];    uint8_t idx;  //第5bit作为idx表示这是group中第几个chunk, 高3bit作为reserved    uint16_t offset; //与第一个chunk的偏移    char user_data[];};

group: 多个相同size的chunk的集合, 这些chunk是物理相邻的

offset = slot_n[-2]

group = chunk_first = slot_n – offset*0x10

meta = group->meta

一片内存中, storage用来保存多个chunk, 元数据放在这片内存开头

一个group中第一个chunk的data为一个指针, 指向这个group的meta元数据, 对应meta结构体

其余chunk使用offset表示与所属group中第一个chunk的偏移, 通过offset找到第一个chunk后, 再找到这个group对应的meta

index = p[-3]&31, 表示这是一个group中第几个slot

综上, 任何一个chunk都可以通过(group, index)这样的二元地址来定位

#define UNIT 16#define IB 4
struct group{    //以下是group中第一个slot的头0x10B struct meta *meta;       //0x80B指针 unsigned char active_idx : 5;    //5bit idx char pad[UNIT - sizeof(struct meta *) - 1]; //padding为0x10B
    //以下为第一个chunk的用户数据区域+剩余所有chunk unsigned char storage[];     //chunk};

meta: meta通过bitmap来管理group中的chunk

meta之间以双向链表的形式形成一个队列结构, 如果说group是一纬的话, 那么meta队列就是二维的结构

一个meta对应一个group,

通过mem找到管理的group

通过sizeclass来追踪group中chunk的size

freed_mask是已经被释放的chunk的bitmap, 4B

avail_mask是目前可用的bitmap, 4B

由于bitmap的限制, 因此一个group中最多只能有32个chunk

meta可以是brk分配的, 可以是mmap映射的, 但是group只能是mmap映射的, 原因在后面

struct meta{ struct meta *prev, *next; //双向链表 struct group *mem;    //管理的内存 volatile int avail_mask, freed_mask; uintptr_t last_idx : 5; uintptr_t freeable : 1; uintptr_t sizeclass : 6; uintptr_t maplen : 8 * sizeof(uintptr_t) - 12;};

meta_area: 是多个meta的集合,

mallocng分配meta时, 总是先分配一页的内存, 然后划分为多个带分配的meta区域

meta_arena描述就是一页内存的最开始部分, slots可视为struct meta的集合

由于meta_arena位于一页内存的开头, 当meta被使用时, 通过清空12bit指针就可以找到meta_arena结构体

为了保证meta结构体是有效的, 并且不会被伪造, mallocng实现了一个验证机制, 保证meta是被meta_arena保护的

检查: 把一个arena指针的低12bit清空, 当做meta_arena结构体, 然后检查其中的check与__malloc_context中的secret是否一致

struct meta_area{ uint64_t check;   //校验值 struct meta_area *next; //下一个分配区 int nslots;    //多少个槽 struct meta slots[]; //留给剩余的meta的槽};
/*- 逻辑视图__malloc_context.avtive[sc]|meta->|group头 | chunk | chunk| ...||meta->|group头 | chunk | chunk| ...||meta->|group头 | chunk | chunk| ...||
一个group视为一纬的, 是一个线性的结构, 包含多个chunk一个meta通过bitmap来管理一个group中的chunk一个avtive则是多个meta形成的循环队列头, 是一个二维的结构, 里面包含多个metaactive就是多个队列头组成的数组, 是一个三纬结构, 保护各个大小的meta队列*/

__malloc_context

所有运行时信息都记录再ctx中, ctx是一个malloc_context结构体, 定义在so的data段

//malloc状态struct malloc_context{ uint64_t secret;#ifndef PAGESIZE size_t pagesize;#endif int init_done;     //有无完成初始化 unsigned mmap_counter;   //mmap内存总数 struct meta *free_meta_head; //释放的meta组成的队列 struct meta *avail_meta;  //指向可用meta数组 size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift; struct meta_area *meta_area_head, *meta_area_tail; //分配区头尾指针 unsigned char *avail_meta_areas; struct meta *active[48];   //活动的meta size_t usage_by_class[48]; //这个大小级别使用了多少内存 uint8_t unmap_seq[32], bounces[32]; uint8_t seq; uintptr_t brk;};
struct malloc_context ctx = {0};

基础操作

meta形成的队列相关操作

//入队: meta组成一个双向链表的队列, queue(phead, m)会在phead指向的meta队列尾部插入mstatic inline void queue(struct meta **phead, struct meta *m){ //要求m->next m->prev都是NULL assert(!m->next); assert(!m->prev); if (*phead) { //把m插入到head前面, 属于队列的尾部插入, *phead仍然指向head  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; }}
//出队: 从队列中删除m节点static inline void dequeue(struct meta **phead, struct meta *m){ if (m->next != m) //队列不只m自己 {  //队列中删除m  m->prev->next = m->next;  m->next->prev = m->prev;
  //如果删除的是头, 那么就把队列头设置为下一个  if (*phead == m)   *phead = m->next; } else //如果只有m自己, 那么队列就空了 {  *phead = 0; }
 //清理m中的prev和next指针 m->prev = m->next = 0;}
//获取队列头元素static inline struct meta *dequeue_head(struct meta **phead){ struct meta *m = *phead; if (m)  dequeue(phead, m); return m;}

内存指针转meta对象

原理:

p – 固定偏移 => group结构体

group->meta指针, 得到所属的meta对象

meta地址与4K向下对齐, 就可找到位于一页开头的meta_area结构体, 但是检查多

static inline struct meta *get_meta(const unsigned char *p){ assert(!((uintptr_t)p & 15));    //地址关于0x10对齐 int offset = *(const uint16_t *)(p - 2); //偏移 int index = get_slot_index(p);    //获取slot的下标 if (p[-4])         //如果offset不为0，表示不是group里的首个chunk，抛出异常 {  assert(!offset);  offset = *(uint32_t *)(p - 8);  assert(offset > 0xffff); } const struct group *base = (const void *)(p - UNIT * offset - UNIT); //根据内存地址获得group结构地址 const struct meta *meta = base->meta;         //根据meta指针获取管理这个group的meta对象
 //检查 assert(meta->mem == base);      //自闭检查: meta->mem==base, base->meta==meta assert(index <= meta->last_idx);    //? assert(!(meta->avail_mask & (1u << index))); //? assert(!(meta->freed_mask & (1u << index))); //?
 const struct meta_area *area = (void *)((uintptr_t)meta & -4096); //一个arena放在4K的开头
 //canary检查 assert(area->check == ctx.secret);
 //检查sizeclass if (meta->sizeclass < 48) {  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;}

根据size找到对应的size类别, 这部分和larege bin的机制类似

//size转对应类别static inline int size_to_class(size_t n){n = (n + IB - 1) >> 4;if (n < 10)return n;n++;int i = (28 - a_clz_32(n)) * 4 + 8;if (n > size_classes[i + 1])i += 2;if (n > size_classes[i])i++;return i;}

malloc()

先判断有无超过mmap的阈值, 如果超过就mmap分配

如果没有超过, size转sc之后, 通过ctx.active[sc]找到对应的meta队列, 尝试从队列中首个meta里分配chunk

如果这个队列为空, 或者这个meta的avail里面没有合适的chunk, 那就调用alloc_slot()获取chunk

找到group与idx之后通过enframe()分配出这个chunk

void *malloc(size_t n){ if (size_overflows(n)) //是否溢出  return 0; struct meta *g; uint32_t mask, first; int sc; int idx; int ctr;
 if (n >= MMAP_THRESHOLD) //太大了, 直接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  if (!g)  {   unlock();   munmap(p, needed);   return 0;  }
  //mmap得到的内存相关信息记录在这个meta对象中  g->mem = p;    //内存指针  g->mem->meta = g; //meta指针  g->last_idx = 0;  g->freeable = 1;  g->sizeclass = 63;     //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; }
 //先从ctx中找meta
 sc = size_to_class(n); //计算size类别 rdlock();      //对malloc上锁 g = ctx.active[sc];    //根据size类别找到对应的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. /*  当没有任何合适的size的group时使用更粗粒度的size classes */ //对应meta为空 AND 4<=sc<32 AND sc!=6 AND sc是偶数 AND 这个sc没使用过内存 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.  //下面大概意思就是如果这个sc是空的, 那么就是使用更大的sc中的meta  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; //meta中的可用内存的bitmap, 如果g为0那么就设为0, 表示没有可用chunk  first = mask & -mask;    //一个小技巧, 作用是找到mask的bit中第一个为1的bit  if (!first)       //如果没找到就停止   break;
  //设置avail_mask中first对应的bit为0  if (RDLOCK_IS_EXCLUSIVE || !MT) //如果是排它锁, 那么下面保证成功   g->avail_mask = mask - first;  else if (a_cas(&g->avail_mask, mask, mask - first) != mask) //如果是cas原子操作则需要for(;;)来自旋   continue;
  //成功找到并设置avail_mask之后转为idx, 结束  idx = a_ctz_32(first);  goto success; } upgradelock();
 /*  - 如果这个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(); //从g中分配第idx个chunk, 大小为n return enframe(g, idx, n, ctr);}

alloc_slot()

freed_mask中

这个队列别的meta中

首先会通过try_avail()在以下位置寻找可用的chunk,

如果失败,或者这个队列本来就空, 那么就会调用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]); //尝试正在active[sc]队列内部分配chunk: 使用别的group, 移出freed_mask if (first)          //分配成功  return a_ctz_32(first);
 struct meta *g = alloc_group(sc, req); //如果还不行, 那就只能为这个sc分配一个group if (!g)  return -1;
 g->avail_mask--; queue(&ctx.active[sc], g); //新分配的g入队 return 0;}

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) //如果ctx.active[sc]==NULL, 那么就无法尝试使用avail  return 0; uint32_t mask = m->avail_mask; if (!mask) //如果avail中没有可用的, 有可能其他线程释放了chunk {  if (!m) //同上   return 0;  if (!m->freed_mask) //如果freed_mask也为空  {   dequeue(pm, m); //那么就从队列中弹出   m = *pm;   if (!m)    return 0;  }  else  {   m = m->next; //否则pm使用m的下一个作为队列开头, 应该是为了每次malloc与free的时间均衡   *pm = m;  }
  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  //如果这个group所有的chunk都被释放了, 那么就尝试使用下一个group, 应该是为了每次malloc与free的时间均衡  if (mask == (2u << m->last_idx) - 1 && m->freeable)  {   m = m->next;   *pm = m;   mask = m->freed_mask;  }
  //((2u << m->mem->active_idx) - 1)建立一个掩码, 如果acctive_idx为3, 那么就是0b1111  if (!(mask & ((2u << m->mem->active_idx) - 1))) //如果这个group中有free的chunk, 但是不满足avtive_idx的要求  {   //如果meta后面还有meta, 那么就切换到后一个meta, 由于avail与free都为0的group已经在上一步出队了, 因此后一个group一定有满足要求的chunk   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;   }  }  mask = activate_group(m);  //激活这个group, 把free的chunk转移到avail中,其实就是交换下bitmap的事  assert(mask);     //由于group中freed_mask非空, 因此一定会找到可用的chunk, 所以返回的avail_mask一定非0  decay_bounces(m->sizeclass); //? } //经过上面的操作, 已经使得m的group中有可用的mask, 因此取出就好 first = mask & -mask; m->avail_mask = mask - first; return first;}

alloc_group()

首先会通过alloc_meta()分配一个meta, 用来管理后面分配的group

计算好需要的长度后通过mmap()匿名映射一片内存作为group

然后初始化meta中相关信息

//新分配一个size_class为sc的groupstatic 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 {  ... }
 // 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)  {   ...  }  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; //这个sc又增加了cnt个chunk 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;}

alloc_meta()

先通过brk分配1页,

如果brk失败的话则会通过mmap()分配许多页内存, 但是这些内存都是PROT_NONE的, 属于guard page, 堆溢出到这些页面会引发SIGV, 而meta不使用开头与结尾的一页, 防止被溢出

先看有无初始化设置ctx的随机数

如果ctx的free_meta_head链表中有空闲的meta, 那么直接从这里分配一个meta

如果没有可用的, 那么就说明需要向OS申请内存存放meta

然后设置ctx中的meta_area_tail, avail_meta_cnt等信息, 把新分配的一页作为待划分的meta

//分配一个meta对象, 有可能是用的空闲的meta, 也可能是新分配一页划分的struct meta *alloc_meta(void){ struct meta *m; unsigned char *p;
 //如果还没初始化, 就设置secret if (!ctx.init_done) {#ifndef PAGESIZE  ctx.pagesize = get_page_size();#endif  ctx.secret = get_random_secret(); //设置secret为随机数  ctx.init_done = 1; }
 //设置pagesize size_t pagesize = PGSZ; if (pagesize < 4096)  pagesize = 4096;
 //如果能从空闲meta队列free_meta_head中得到一个meta, 就可直接返回 if ((m = dequeue_head(&ctx.free_meta_head)))  return m;
 //如果没有空闲的, 并且ctx中也没有可用的, 就通过mmap映射一页作为meta数组 if (!ctx.avail_meta_count) {  int need_unprotect = 1;
  //如果ctx中没有可用的meta, 并且brk不为-1  if (!ctx.avail_meta_area_count && ctx.brk != -1)  {   uintptr_t new = ctx.brk + pagesize; //新分配一页   int need_guard = 0;   if (!ctx.brk) //如果cnt中brk为0   {    need_guard = 1;    ctx.brk = brk(0); //那就调用brk()获取当前的heap地址    // some ancient kernels returned _ebss    // instead of next page as initial brk.    ctx.brk += -ctx.brk & (pagesize - 1); //设置ctx.brk与new    new = ctx.brk + 2 * pagesize;   }   if (brk(new) != new) //brk()分配heap到new地址失败   {    ctx.brk = -1;   }   else //如果brk()分批额成功   {    if (need_guard) //保护页, 在brk后面映射一个不可用的页(PROT_NONE), 如果堆溢出到这里就会发送SIGV     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); //把这一页全划分为meta    ctx.avail_meta_area_count = pagesize >> 12;    need_unprotect = 0;   }  }
  if (!ctx.avail_meta_area_count) //如果前面brk()分配失败了, 直接mmap匿名映射一片PROT_NONE的内存再划分  {   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++;  }
  //如果avail_meta_areas与4K对齐, 那么就说明这片区域是刚刚申请的一页, 所以需要修改内存的权限  p = ctx.avail_meta_areas;  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)  {   ctx.meta_area_tail->next = (void *)p;  }  else  {   ctx.meta_area_head = (void *)p;  }
  //ctx中记录下相关信息  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;  ctx.avail_meta = ctx.meta_area_tail->slots; }
 //ctx的可用meta数组中有能用的, 就直接分配一个出来 ctx.avail_meta_count--; m = ctx.avail_meta++;  //取出一个meta m->prev = m->next = 0; //这俩指针初始化为0 return m;}

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; //设置与group中第一个chunk的偏移 p[-3] = idx;             //设置idx set_size(p, end, n); return p;}

总结，mallocng有如下特性

chunk按照bitmap从低到高依次分配

被free掉的内存会先进入freed_mask, 当avail_mask耗尽时才会使用freed_mask中的

mallocng把meta与group隔离开来, 来减缓堆溢出的危害

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);  //获取chunk所属的meta int idx = get_slot_index(p);   //这是group中第几个chunk size_t stride = get_stride(g); //这个group负责的大小 unsigned char *start = g->mem->storage + stride * idx; unsigned char *end = start + stride - IB; 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;
 // release any whole pages contained in the slot to be freed // unless it's a single-slot group that will be unmapped. //释放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 (;;) {  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  */  if (!freed || mask + self == all)   break;
  //设置freed_mask, 表示这个chunk被释放了  if (!MT) //如果是单线程,直接写就好了   g->freed_mask = freed + self;  else if (a_cas(&g->freed_mask, freed, freed + self) != freed) //如遇多线程使用原子操作, 一直循环到g->freed_mask为freed+self为止   continue;  return; }
 wrlock(); struct mapinfo mi = nontrivial_free(g, idx); //处理涉及到meta之间的操作 unlock(); if (mi.len)  munmap(mi.base, mi.len);}

nontrivial_free()

那么说明malloc分配出最后一个chunk的时候已经把这个meta给弹出队列了

但是现在里面有一个chunk被释放了, 这个meta就应该再次回归队列, 因此调用queue()再次入队

先调用dequeue从队列中出队

如果队里中后面还有meta的话, 就会激活后一个meta

然后调用free_group()释放整个group

根据free()进入这个函数的方式可以知道, 此时还没有设置freed_mask

如果发现这个group中所有的chunk要么被free, 要么是可用的, 那么就会回收掉这个group

如果发现mask为空

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) //如果g有下一个  {   assert(sc < 48);        //检查: sc合法, 不是mmap的   int activate_new = (ctx.active[sc] == g); //如果g是队列中开头的meta, 那么弹出队列后, 要激活后一个   dequeue(&ctx.active[sc], g);     //这个meta出队
   //如果队列存在后一个meta, 那么就激活他, 因为之前为了free的快速, 只是用freed_mask标记了一下而已, 现在要转移到avail_mask中了   if (activate_new && ctx.active[sc])    activate_group(ctx.active[sc]);  }  return free_group(g); //meta已经取出, 现在要释放这个meta } else if (!mask) //如果mask==0, 也就是这个group中所有的chunk都被分配出去了 {    //那么这个meta在malloc()=>alloc_slot()=>try_avail()最终就被弹出队列了, 目的取出队列中不可能再被分配的, 提高效率     //现在这个全部chunk被分配出去的group中有一个chunk被释放了, 因此这个meta要重新入队  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); return (struct mapinfo){0};}

可利用的点

mallocng防御堆溢出的方法是meta与分配chunk的group在地址上分离, 并且在meta所在页的前后设置一个NON_PROT的guard page, 来防止发生在group上的堆溢出影响到meta, 产生arbitrary alloc, 因此无法从溢出meta队列

但是队列操作中并没有对mete的prev与next指针进行检查, 属于unsafe unlink, 原因可以能是作者认为, 既然meta无法被修改, 那么meta中的指针一定是正确的

其实不然, 我们确实无法直接溢出meta, 但是这不代表这我们无法伪造meta结构体。

思路：我们可以溢出一个chunk, 伪造他的offset与next, 使其指向我们伪造的group，然后伪造group中的meta指针, 使其指向我们伪造的meta。此时伪造meta中的prev next指针, 并且伪造freed_mask与avail_mask, 做出一副这个meta中的chunk已经全部被释放了的样子, 这样就会调用:free()=>nontrivial_free()=>dequeue()完成攻击