【技術分享】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()完成攻擊