musl 1.2.2 源码分析

2022-04-30

musl1.2.1及之后,它的堆管理结构发生了巨大变化,因为musl1.2.0以及以前的代码存在巨大缺陷

所以musl1.2.2相当于重新看一遍源码(哭

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的最高地址
};
malloc_context

(一个程序中有且只有一个,声明为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_area

结构是管理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

每个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高了不少

参考

新版musl-libc malloc源码分析与调试

musl 知:内存管理

musl-1.2.x堆部分源码分析

借助DefCon Quals 2021的mooosl学习musl mallocng(源码审计篇)

[https://www.anquanke.com/post/id/202253#h3-8]