Aur0r3
0%

堆基础知识

Posted on Edited on In

arena

  • 是管理堆的一个结构,
  • 一个线程只有一个arena
  • 主线程的arena称为main_arena，子线程的arena称为thread_arena

chunk结构体

  • 由 malloc 申请的内存为 chunk，用 malloc_chunk 结构体来表示。
  • 当程序申请的 chunk 被 free 后，会被加入到相应的空闲管理列表中。
  • 无论一个 chunk 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构（malloc_chunk）
  • 每次 malloc 申请得到的内存指针，指向 user data 的起始处
  • 如果一个 chunk 处于 free 状态，本身的 size 字段会记录和它后面的 chunk 会记录都会记录其大小
  • 当一个 chunk 处于已分配状态时，它的物理相邻的下一个 chunk 的 prev_size 字段可以被当前这个 chunk 使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  //user data begining
  struct malloc_chunk* fd;         /* double links -- used only if free. User data starts here...*/
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
 //fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
 //bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
};

alocated chunk

  • 已被分配给用户的chunk为allocated chunk
  • 当free chunk被分配时，返回给用户的指针为 该chunk首地址 + 2 x SIZE_SZ （即该chunk的成员fd指针的地址）

top chunk

  • 程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。
  • 是处于当前堆的物理地址最高的 chunk
  • 该 chunk 不属于 任何bin，只由arena直接管理
  • 当所有的 bin 都无法满足用户请求的大小时，如果top chunk大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配

bin

  • 根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：fast bins，small bins，large bins，unsorted bin

  • 在bin中任意两个物理相邻的空闲 chunk 不能在一起

  • bin被维护在一个数组中

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct malloc_state
    {
    /* Other members ... */

    /* Fastbins */
    mfastbinptr fastbinsY[NFASTBINS];

    /* Normal bins packed as described above */
    mchunkptr bins[NBINS * 2 - 2];

    /* Other members ... */
    };

bin链共有128条。但为什么在arena中，bins数组的大小为 NBINS * 2 - 2 呢？

答：每个bin链在bins数组中存储的是一个指针fd指针和一个bk指针，且数组bins中索引为0、1的指针是不使用的，所以要减去2

unsorted bin

  • unsorted bin只有 一个，位于arena中的 bin[1]。任何大小的chunk都可加入unsorted bin中
  • 无序双向链表
  • 当free的chunk大小大于等于144字节时，为了效率，glibc并不会马上将chunk放到相对应的bin中，而会先放到unsorted bin
  • FIFO

fastbin

  • fastbin采用单向链表， 只是使用fd指针，采取 LIFO 策略，最近释放的 chunk 会更早地被分配
  • 里面的chunk不会进行合并操作和释放
  • fastbin被存放在fastbinY数组中，该数组一共有10个元素，数组中相同的链表存放的chunk大小相同
  • 负责 SIZE_SZ 为 4B 的平台， 小于 64B 的 chunk 分配请求，和 SIZE_SZ 为 8B 的平台，小于 128B 的 chunk 分配请求
  • 下标相邻的数组元素中的chunk链表的chunk size相差8字节，默认情况下大小尾16到80字节的chunk会被分到fast chunk中
  • LIFO

smallbin

  • small bins 中一共有 62 个循环双向链表，每个链表中存储的 chunk 大小都一致。
  • small bins 中每个 bin 对应的链表采用 FIFO 的规则
  • chunk大小 小于512(0x200)（32位）/ 1024(0x400)（64位）字节的
  • FIFO

largebin

  • large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致
  • 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的差一致
  • 存放的是大于等于0x200（64位下0x400）字节的chunk
  • FIFO