glic内存管理学习笔记

华庭师傅的glibc内存管理简直逆天,这里写一下笔记,更新中

内存经典布局

这里随便画一下QAQ

32位

Kernel <- 0xc00000000==TASK_SIZE
<- Random stack offset
——-
stack
——-
<-Random mmap offset
——-
Memory Mapping region <- 0x40000000
<- program break
——- <- brk
heap
——- <- start brk
BSS segment
——- <- end data
Data segment <- start data
——- <- end code
Text segment <- 0x08048000
——-
<- 0

64位

Kernel <- 0xFFFF800000000000
undefine region <- 0X00007FFFFFFFF000=TASK_SIZE
——-
stack
——-
——-
Memory Mapping region <- 0x00002AAAAAAAA000
——-
heap
——-
BSS segment
——-
Data segment
——-
Text segment <- 0x00000000040000
——-
<- 0

内容设计假设

6个假设

  • 对长生命周期的大内存分配使用mmap
  • 特别大的内存分配总使用mmap
  • 具有短生命周期的内存分配使用brk
  • 尽量只缓存临时使用的空闲小内存块
  • 空闲小内存块只会在malloc和free时合并,free时空闲内存块可能放入pool中,不一定归还给操作系统
  • 收缩堆的条件
    • 当前free块大小加上前后可合并chunk大于64kb
    • 堆顶大小达到阈值
    • 这样会把堆最顶端空闲内存返回给操作系统

记忆问题

  • 收缩堆的条件有?
  • 结果是?
  • 都有哪些假设?

总结

  • 大内存,长周期 -> mmap
  • 短周期 -> brk
  • 缓存的内存块尽可能时大小较小的
  • 空闲块只有在分配和free的时候会合并
  • free的时候不一定归还给操作系统(会成为cache)
  • 空闲chunk大小 > 64KB 时合并chunk ->收缩堆
  • 堆顶大小达到阈值 -> 收缩堆
  • 收缩堆会将堆最顶端空间内存返回给操作系统

数据结构概述

Main_arena 与 non_main_arena

原文概述

  • 在 Doug Lea 实现的内存分配器中只有一个主分配区（main arena）
  • 每次分配内存都必须对主分配区加锁，分配完成后释放锁
  • 在 SMP 多线程环境下，对主分配区的锁的争用很激烈，严重影响了malloc 的分配效率。于是Wolfram Gloger 在 Doug Lea 的基础上改进使得 Glibc 的malloc 可以支持多线程，增加了非主分配区（non main arena）支持
  • 主分配区与非主分配区用环形链表进行管理。每一个分配区利用互斥锁（mutex）使线程对于该分配区的访问互斥。
  • 每个进程只有一个主分配区，但可能存在多个非主分配区
  • ptmalloc 根据系统对分配区的争用情况动态增加非主分配区的数量，分配区的数量一旦增加，就不会再减少了。
  • 主分配 区可以访问进程的heap区域和mmap映射区域
  • 主分配区可以使用 sbrk 和mmap 向操作系统申请虚拟内存。而非主分配区只能访问进程的 mmap 映射区域
  • 非主分配区每次使用mmap()向操作系统“批发”HEAP_MAX_SIZE（32 位系统上默认为 1MB，64 位系统默 认为 64MB）大小的虚拟内存
  • 当用户向非主分配区请求分配内存时再切割成小块“零售” 出去
  • ptmalloc 在必要的情况下才会调用mmap()函数向操作系统申请虚拟内存。
  • 主分配区可以访问 heap 区域，如果用户不调用 brk()或是 sbrk()函数，分配程序就可以保证分配到连续的虚拟地址空间，因为每个进程只有一个主分配区使用 sbrk()分配 heap 区域的虚拟内存。
  • 内核对 brk 的实现可以看着是mmap 的一个精简版，相对高效一些。
  • 如果主 分配区的内存是通过mmap()向系统分配的，当free该内存时，主分配区会直接调用munmap() 将该内存归还给系统。
  • 当某一线程需要调用malloc()分配内存空间时，该线程先查看线程私有变量中是否已经存在一个分配区，如果存在，尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存， 如果失败，该线程搜索循环链表试图获得一个没有加锁的分配区。如果所有的分配区都已经 加锁那么malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁， 然后使用该分配区进行分配内存操作。在释放操作中，线程同样试图获得待释放内存块所在 分配区的锁，如果该分配区正在被别的线程使用，则需要等待直到其他线程释放该分配区的 互斥锁之后才可以进行释放操作。
  • 申请小块内存时会产生很多内存碎片，ptmalloc 在整理时也需要对分配区做加锁操作。
  • 每个加锁操作大概需要 5～10 个 cpu 指令，而且程序线程很多的情况下，锁等待的时间就会 延长，导致malloc性能下降。一次加锁操作需要消耗100ns左右，正是锁的缘故，导致ptmalloc 在多线程竞争情况下性能远远落后于 tcmalloc。最新版的 ptmalloc 对锁进行了优化，加入了 PER_THREAD和 ATOMIC_FASTBINS 优化，但默认编译不会启用该优化，这两个对锁的优化应 该能够提升多线程内存的分配的效率。

问题

  • 该结构有什么特点?
  • 主分配区和非主分配区的区别是什么?
  • 两者不同的分配方式分别时如何分配的?

总结

  • main_arena(MA)为主分配区;non_main_arena(N_MA)为非主分配区
  • 两者通过环形链表进行管理,每个分区采用互斥锁使线程的访问互斥
  • 每个分配区有一个MA,可能有多个N_MA;
  • N_MA数里只加不减
  • MA可访问进程的heap和mmap映射区域
    • MA可以使用Sbrk和mmap来向系统申请内存
    • N_MA只能访问进程的MMAP映射区域
  • 主分配区可访问heap区域,若用户不调用brk()/sbrk(),将可分配到连续的虚拟内存地址
  • malloc时先看线程是否有分配区,存在则先加锁,成功则分配内存,否则开辟新分配区,加入环形链表并加锁

chunk的组织

不管内存是在哪里被分配的，用什么方法分配，用户请求分配的空间在 ptmalloc 中都使用一个 chunk 来表示。用户调用 free()函数释放掉的内存也并不是立即就归还给操作系统， 相反，它们也会被表示为一个chunk，ptmalloc使用特定的数据结构来管理这些空闲的chunk

chunk格式

使用中的chunk

Size of pre chunk <-chunk
Size of chunk,in bytes A/M/P
——- <-mem
user data
——- <- next chunk
Size of chunk,in bytes
  • 在图中，chunk指针指向一个chunk的开始，一个chunk中包含了用户请求的内存区域和相关的控制信息。
  • 图中的mem指针才是真正返回给用户的内存指针。
  • chunk的第二个域的最低一位为P，它表示前一个块是否在使用中，P为0则表示前一个chunk为空闲，这时 chunk的第一个域prev_size才有效
  • prev_size表示前一个chunk的size，程序可以使用这个值来找到前一个chunk的开始地址。当P为1时，表示前一个chunk正在使用中，prev_size无效，程序也就不可以得到前一个chunk的大小。不能对前一个chunk进行任何操作。ptmalloc分配的第一个块总是将P设为1，以防止程序引用到不存在的区域。
  • Chunk的第二个域的倒数第二个位为M，他表示当前chunk是从哪个内存区域获得的虚拟内存。M为1表示该chunk是从mmap映射区域分配的，否则是从heap区域分配的。
  • Chunk的第二个域倒数第三个位为A，表示该chunk属于主分配区或者非主分配区，如果属于非主分配区，将该位置为1，否则置为0。

空闲的chunk

Size of pre chunk <-chunk
Size of chunk,in bytes A/ /P
——- <-mem
*fd
*bk
*fd_next size
*bk_next size
user data
——- <- next chunk
Size of chunk,in bytes
  • 当chunk空闲时，其M状态不存在，只有AP状态，
  • 原本是用户数据区的地方存储了四个指针，指针fd指向后一个空闲的chunk，而bk指向前一个空闲的chunk，ptmalloc通过这两个指针将大小相近的chunk连成一个双向链表。
  • 对于large bin中的空闲chunk，还有两个指针，fd_nextsize和bk_nextsize，这两个指针用于加快在large bin中查找最近匹配的空闲chunk。不同的chunk链表又是通过bins或者fastbins来组织的

问题

  • 使用中的chunk和空闲时有什么不同?
  • chunk的第二个域倒数几位都各自代表了什么?
  • 两者各自域都代表了什么?

总结

chunk in use

  • chunk指针指向chunk的开始,但是mem指针才是返回给用户的内存指针
  • chunk第二个域的倒数三位代表
    • A -> 是不是主分配区 .
      • 0-> MA ;
      • 1-> N_MA;
    • M -> 是不是由mmap分配的
      • 0-> heap
      • 1-> mmap;
    • P -> 前一个chunk是否在使用中
      • 0-> 空闲 此时prev_size有效
      • 1-> 使用中, 此时禁止对前一个chunk有任何操作,无法得到其大小

free chunk

  • chunk空闲时,M态不存在,只有AP状态
  • 此时用户区存储了四个指针
    • fd :指向后一个空闲的chunk
    • bk :指向前一个空闲的chunk
    • fd_nextsize :只有在large bin中才使用,因为相同大小的chunk可能有很多,因此为了方便查找,会指向后一个比他小的chunk
    • bk_nextsize :上同,但是会指向前一个比他小的chunk

chunk的空间复用

内容

  • 为了使得 chunk 所占用的空间最小，ptmalloc使用了空间复用
  • 一个 chunk或者正在被使用，或者已经被free掉，所以chunk的中的一些域可以在使用状态和空闲状态表示不同的意义，来达到空间复用的效果。
  • 以32位系统为例，
    • 空闲时，一个chunk中至少需要4个size_t（4B）大小的空间，用来存储prev_size，size，fd和bk （见上图），也就是16B，chunk的大小要对齐到8B。
    • 当一个chunk处于使用状态时，它的下一个chunk的prev_size域肯定是无效的。所以实际上，这个空间也可以被当前chunk使用
    • 故而实际上，一个使用中的chunk的大小的计算公式应该是：in_use_size = (用户请求大小+ 8 - 4 ) align to 8B，这里加8是因为需要存储prev_size和size，但又因为向下一个chunk“借”了4B，所以要减去4。
    • 最后，因为空闲的chunk 和使用中的chunk使用的是同一块空间。所以肯定要取其中最大者作为实际的分配空间。即最终的分配空间chunk_size = max(in_use_size, 16)。
    • 这就是当用户请求内存分配时，ptmalloc 实际需要分配的内存大小，在后面的介绍中。如果不是特别指明的地方，指的都是这个经过转换的实际需要分配的内存大小，而不是用户请求的内存分配大小。

问题

  • 如何空间复用?
  • 用户请求分配内存后会实际得到多少内存?

总结

  • P为1时,pre chunk size归上一个 chunk使用
  • size of(chunk in use )=(用户请求大小 + 8 -4 ) align to 8B
  • size of (free)min =16B

空闲chunk容器

bins

用户free掉的内存并不是都会马上归还给系统，ptmalloc会统一管理heap和mmap映射区域中的空闲的chunk，当用户进行下一次分配请求时，ptmalloc会首先试图在空闲的chunk中挑选一块给用户，这样就避免了频繁的系统调用，降低了内存分配的开销。ptmalloc将相似大小的chunk用双向链表链接起来，这样的一个链表被称为一个bin。Ptmalloc一共维护了128个bin，并使用一个数组来存储这些bin
avatar

概况

  • 数组中的第一个为unsorted bin，
  • 数组中从2开始编号的前64个bin称为small bins
    • 同一个small bin中的chunk具有相同的大小。
    • 两个相邻的small bin中的chunk大小相差8bytes。
    • small bins中的chunk按照最近使用顺序进行排列，最后释放的chunk被链接到链表的头部，而申请chunk是从链表尾部开始，这样，每一个chunk 都有相同的机会被ptmalloc选中。
    • Small bins后面的bin被称作large bins。large bins中的每一个bin分别包含了一个给定范围内的chunk，其中的chunk按大小序排列。相同大小的chunk同样按照最近使用顺序排列。
    • ptmalloc使用“smallest-first，best-fit”原则在空闲large bins中查找合适的chunk。
  • 当空闲的chunk被链接到bin中的时候，ptmalloc会把表示该chunk是否处于使用中的标志P设为0（注意，这个标志实际上处在下一个chunk中）同时ptmalloc还会检查它前后的chunk是否也是空闲的，如果是的话，ptmalloc会首先把它们合并为一个大的chunk，然后将合并后的chunk放到unstored bin中。
  • 要注意的是，并不是所有的chunk被释放后就立即被放到bin中。
  • ptmalloc为了提高分配的速度，会把一些小的的chunk先放到一个叫做fast bins的容器内。

fast bin

  • 程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的chunk之后，也许马上就会有另一个小块内存的请求，这样分配器又需要从大的空闲内存中切分出一块，这样无疑是比较低效的，故而，ptmalloc中在分配过程中引入了fast bins，不大于max_fast （默认值为64B）的chunk被释放后，首先会被放到fast bins
  • fast bins中的chunk并不改变它的使用标志P。这样也就无法将它们合并
  • 当需要给用户分配的chunk小于或等于max_fast时，ptmalloc首先会在fast bins中查找相应的空闲块，然后才会去查找bins中的空闲chunk。
  • 在某个特定的时候，ptmalloc会遍历fast bins中的chunk，将相邻的空闲chunk进行合并，并将合并后的chunk加入unsorted bin中，然后再将usorted bin里的chunk加入bins中。

Unsorted Bin

  • unsorted bin的队列使用bins数组的第一个
  • 如果被用户释放的chunk大于max_fast，或者fast bins中的空闲chunk合并后，这些chunk首先会被放到unsorted bin队列中
  • 在进行malloc操作的时候，如果在fast bins中没有找到合适的chunk，则ptmalloc会先在unsorted bin中查找合适的空闲chunk，然后才查找bins。
  • 如果unsorted bin不能满足分配要求。malloc便会将unsorted bin中的chunk加入bins中。然后再从bins中继续进行查找和分配过程。
  • unsorted bin可以看做是bins的一个缓冲区，增加它只是为了加快分配的速度。

并不是所有的chunk都按照上面的方式来组织，实际上，有三种例外情况。Top chunk，mmaped chunk和last remainder

Top chunk

top chunk对于主分配区和非主分配区是不一样的。

  • 非主分配区
    • 对于非主分配区会预先从mmap区域分配一块较大的空闲内存模拟sub-heap，通过管理sub-heap来响应用户的需求
    • 因为内存是按地址从低向高进行分配的，在空闲内存的最高处，必然存在着一块空闲chunk，叫做top chunk。
    • 当bins和fast bins都不能满足分配需要的时候，ptmalloc会设法在top chunk中分出一块内存给用户 .如果top chunk本身不够大，分配程序会重新分配一个sub-heap，并将top chunk迁移到新的sub-heap上，新的sub-heap与已有的sub-heap用单向链表连接起来，然后在新的top chunk上分配所需的内存以满足分配的需要
    • 实际上，top chunk在分配时总是在fast bins和bins之后被考虑，所以，不论top chunk有多大，它都不会被放到fast bins或者是bins中。
    • Top chunk的大小是随着分配和回收不停变换的，如果从top chunk分配内存会导致top chunk减小，如果回收的chunk恰好与top chunk相邻，那么这两个chunk就会合并成新的top chunk，从而使top chunk变大。
    • 如果在free时回收的内存大于某个阈值，并且top chunk的大小也超过了收缩阈值，ptmalloc会收缩sub-heap，如果top-chunk包含了整个sub-heap，ptmalloc会调用munmap把整个sub-heap的内存返回给操作系统。
  • 主分配区
    • 由于主分配区是唯一能够映射进程heap区域的分配区，它可以通过sbrk()来增大或是收缩进程heap的大小
    • ptmalloc在开始时会预先分配一块较大的空闲内存（也就是所谓的 heap），主分配区的top chunk在第一次调用malloc时会分配一块(chunk_size + 128KB) align 4KB大小的空间作为初始的heap
    • 用户从top chunk分配内存时，可以直接取出一块内存给用户。在回收内存时，回收的内存恰好与top chunk相邻则合并成新的top chunk，当该次回收的空闲内存大小达到某个阈值，并且top chunk的大小也超过了收缩阈值，会执行内存收缩，减小top chunk的大小，但至少要保留一个页大小的空闲内存，从而把内存归还给操作系统。
    • 如果向主分配区的top chunk申请内存，而top chunk中没有空闲内存，ptmalloc会调用sbrk()将的进程heap的边界brk上移，然后修改top chunk的大小。

mmaped chunk

当需要分配的chunk足够大，而且fast bins和bins都不能满足要求，甚至top chunk本身也不能满足分配需求时，ptmalloc会使用mmap来直接使用内存映射来将页映射到进程空间。

chunk在被free时将直接解除映射，于是就将内存归还给了操作系统，再次对这样的内存区的引用将导致segmentation fault错误。这样的chunk也不会包含在任何bin中

Last remainder

  • Last remainder是另外一种特殊的chunk，就像top chunk和mmaped chunk一样，不会在任何bins中找到这种chunk。
  • 当需要分配一个small chunk，但在small bins中找不到合适的chunk，如果last remainder chunk的大小大于所需的small chunk大小，last remainder chunk被分裂成两个chunk，其中一个chunk返回给用户，另一个chunk变成新的last remainder chuk

问题

  • bins是以何种结构存在的?
  • 都有哪些bins?各自的特点如何?
  • 有哪三种不同的bins?各自在什么地方使用?
  • top chunk的主分配区和非主分配区在使用时有什么不一样?

总结

  • bin

    • 用户free掉的内存不都还给系统,ptmalloc会将相似大小的chunk用双向链表连起来,这就是Bin
    • 一共维护有128个bin,第一个为unsorted bins
    • 2-64为small bins
    • 两相邻大小bins相差8bytes(small bins)
    • 除了FAST BINS 都使用 FIFO原则
    • 64-128为large bins ,每一个大小都在一定范围内,按大小排序,一样大的类似small bins使用
    • 空闲的chunk连入bin时,会将 P 设为 0 , 并检查前后chunk是否空闲,若空闲则合并后加入unsorted bins中

  • fast bins

    • size < max_fast的chunk被free后先放入fastbins中,且不改变P
    • 用户所要Chunk < max_fast 时先便利fast bin
    • 有时会便利fast bin,将相邻的chunk合并后放入unsorted bin中,然后将unsorted中的chunk 加入bin中

  • unsorted bins

    • 使用bins数组的第一个,若free的chunk>max_fast,或fast bins 合并后,先放入unsorted bin中
    • malloc时若fastbin中没有合适的,就现在unsorted中找,最后才是bins
    • 若unsorted也不能满足分配,malloc会将其内的chunk放入bins中再分配
    • 可以看作时bins的缓冲区,用来加快分配速度

  • top chunk

    • 主分配区和非主分配区不一样
    • N_MA
      • 预先从mmap中分配一块较大的空闲内存模拟sub-heap(内存从低到高分配)
      • 内存最高处必有空闲chunk为Top chunk
      • bins和fast bins都没有满足的时,会在TOP中分配
      • 永远不会放入fastbins和bins中
      • 若回收的chunk和top相连,会将它们合并,若大小大于某只且top大于收缩阈值,将收缩sub-heap,返回给系统
    • MA
      • 先预先分配空闲内存(sub-heap)
      • MA的top首先malloc时会分配(chunk+128KB)align 4KB的空间为初始HEAP
      • 回收大于阈值,top也大于阈值,则内存收缩.减少TOP但至少保留一页大小,剩下的归还给系统
      • 申请内存时,top无空闲,将会用sbrk上移heap边界
      • 若本身不够大,则重新分配sub-heap,并将top迁移到新的sub-heap上,以链表连接,重新分配

  • mmap chunk

    • 若分配内存太大,且fast和bins中都不能满足时,甚至连TOP也不够时,用mmap直接映射页到进程空间
    • 分配的chunk被free时直接解除映射,还给系统

  • last remainder

    • 需要分配small bins,但small中无合适的chunk时,若last大小大于所需的small chunk,将会分裂成两个chunk,一个给用户,一个变成新的last

sbrk和mmap

内容

  • 从进程的内存布局可知，.bss 段之上的这块分配给用户程序的空间被称为 heap （堆）。
  • start_brk 指向 heap 的开始，而 brk 指向 heap 的顶部。
  • 可以使用系统调用 brk()和 sbrk()来增 加标识 heap 顶部的 brk 值，从而线性的增加分配给用户的 heap 空间。
  • 在使用malloc 之前， brk的值等于start_brk，也就是说heap大小为0。
  • ptmalloc在开始时，若请求的空间小于 mmap 分配阈值（mmap threshold，默认值为 128KB）时
    • 主分配区会调用 sbrk()增加一块大小为 (128 KB + chunk_size) align 4KB 的空间作为 heap。
    • 非主分配区会调用 mmap 映射一块大小为 HEAP_MAX_SIZE（32 位系统上默认为1MB，64 位系统上默认为64MB）的空间作为 sub-heap。 这就是前面所说的 ptmalloc 所维护的分配空间，
    • 当用户请求内存分配时，首先会在这个区域内找一块合适的 chunk 给用户。
  • 当用户释放了 heap 中的 chunk 时，ptmalloc 又会使用 fast bins 和 bins 来组织空闲 chunk。以备用户的下一次分配。
  • 若需要分配的 chunk 大小小于mmap 分配阈值，而 heap 空间又不够
    • 此时主分配区会通过 sbrk()调用来增加 heap 大小
    • 非主分配区会调用mmap 映射一块新的 sub-heap，也就是增加 top chunk 的大小，每次 heap 增 加的值都会对齐到 4KB。
    • 当用户的请求超过mmap 分配阈值，并且主分配区使用 sbrk()分配失败的时候，或是非主分配区在 top chunk 中不能分配到需要的内存时，ptmalloc 会尝试使用mmap()直接映射一块内存到进程内存空间。使用 mmap()直接映射的 chunk 在释放时直接解除映射，而不再属于进程的内存空间。任何对该内存的访问都会产生段错误。而在 heap 中或是 sub-heap中分配的空间则可能会留在进程内存空间内，还可以再次引用（当然是很危险的）。
  • 当 ptmalloc munmap chunk 时，如果回收的 chunk 空间大小大于mmap 分配阈值的当前值，并且小于 DEFAULT_MMAP_THRESHOLD_MAX（32 位系统默认为 512KB，64 位系统默认 为 32MB），ptmalloc 会把 mmap 分配阈值调整为当前回收的 chunk 的大小，并将 mmap 收 缩阈值（mmap trim threshold）设置为mmap 分配阈值的 2 倍。这就是 ptmalloc 的对mmap 分配阈值的动态调整机制，该机制是默认开启的，当然也可以用mallopt()关闭该机制。

问题

  • 有什么不同的机制?
  • sbrk和mmap的区别是?

总结

  • ptmalloc开始时,若小于mmap的分配阈值(128KB)
    • 则主分配区用sbrk增加一块大小为(128KB+chunk_size) align 4KB的内存作为heap
    • 非主分配区会使用mmap映射一块大小为HEAP_SIZE(32-1MB,64-64MB)的空间为sub-heap
    • 请求分配时,现在期内寻找相应的chunk
    • 用户free chunk后会放入fast bins中
  • 若chunk < mmap的分配阈值,但heap空间不足时
    • 主分配区会使用sbrk来增加大小
    • 非主会用mmap映射新的sub-heap(对齐到4KB)
  • 若chunk >mmap的分配阈值,但主分配区sbrk失败,非主分配区top chunk不足,就会用mmap映射内存
  • ptmalloc munmap chunk时 ,DEFAULT_MMAP_THRESHOLD_MAX(32 - 512kb , 64 - 32MB) > 回收的chunk > mmap分配阈值时
    1. 将把mmap分配阈值调整为当前回收的chunk大小
    2. 将mmap收缩阈值设置为mmap分配阈值的2倍

内存分配概述

分配算法概述，以 32 系统为例，64 位系统类似。

内容

  • 小于等于 64 字节：用 pool 算法分配。
  • 64 到 512 字节之间：在最佳匹配算法分配和 pool 算法分配中取一种合适的。
  • 大于等于 512 字节：用最佳匹配算法分配。
  • 大于等于mmap 分配阈值（默认值 128KB）：根据设置的 mmap 的分配策略进行分配
    • 如果没有开启mmap分配阈值的动态调整机制，大于等于 128KB 就直接调用mmap分配。
    • 否则，大于等于mmap分配阈值时才直接调用mmap()分配。

分配的具体步骤

  1. 获取分配区的锁，为了防止多个线程同时访问同一个分配区，在进行分配之前需要 取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区，如果存 在尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，否则，该线程搜 索分配区循环链表试图获得一个空闲（没有加锁）的分配区。如果所有的分配区都 已经加锁，那么 ptmalloc 会开辟一个新的分配区，把该分配区加入到全局分配区循 环链表和线程的私有实例中并加锁，然后使用该分配区进行分配操作。开辟出来的 新分配区一定为非主分配区，因为主分配区是从父进程那里继承来的。开辟非主分 配区时会调用mmap()创建一个 sub-heap，并设置好 top chunk。
  2. 将用户的请求大小转换为实际需要分配的 chunk 空间大小。
  3. 判断所需分配chunk的大小是否满足chunk_size <= max_fast (max_fast 默认为 64B)， 如果是的话，则转下一步，否则跳到第 5 步。
  4. 首先尝试在 fast bins 中取一个所需大小的 chunk 分配给用户。如果可以找到，则分 配结束。否则转到下一步。
  5. 判断所需大小是否处在 small bins 中，即判断 chunk_size < 512B 是否成立。如果 chunk 大小处在 small bins 中，则转下一步，否则转到第 6 步。
  6. 根据所需分配的 chunk 的大小，找到具体所在的某个 small bin，从该 bin 的尾部摘 取一个恰好满足大小的 chunk。若成功，则分配结束，否则，转到下一步。
  7. 到了这一步，说明需要分配的是一块大的内存，或者 small bins 中找不到合适的 chunk。于是，ptmalloc 首先会遍历 fast bins 中的 chunk，将相邻的 chunk 进行合并， 并链接到 unsorted bin 中，然后遍历 unsorted bin 中的 chunk，如果 unsorted bin 只 有一个 chunk，并且这个 chunk 在上次分配时被使用过，并且所需分配的 chunk 大 小属于 small bins，并且 chunk 的大小大于等于需要分配的大小，这种情况下就直 接将该 chunk 进行切割，分配结束，否则将根据 chunk 的空间大小将其放入 small bins 或是 large bins 中，遍历完成后，转入下一步。
  8. 到了这一步，说明需要分配的是一块大的内存，或者 small bins 和 unsorted bin 中 都找不到合适的 chunk，并且 fast bins 和 unsorted bin 中所有的 chunk 都清除干净 了。从 large bins 中按照“smallest-first，best-fit”原则，找一个合适的 chunk，从 中划分一块所需大小的 chunk，并将剩下的部分链接回到 bins 中。若操作成功，则 分配结束，否则转到下一步。
  9. 如果搜索 fast bins 和 bins 都没有找到合适的 chunk，那么就需要操作 top chunk 来 进行分配了。判断 top chunk 大小是否满足所需 chunk 的大小，如果是，则从 top chunk 中分出一块来。否则转到下一步。
  10. 到了这一步，说明 top chunk 也不能满足分配要求，所以，于是就有了两个选择: 如 果是主分配区，调用 sbrk()，增加 top chunk 大小；如果是非主分配区，调用mmap 来分配一个新的 sub-heap，增加 top chunk 大小；或者使用mmap()来直接分配。在 这里，需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值，如果是的话，则转下一步，调用mmap 分配， 否则跳到第 12 步，增加 top chunk 的大小。
  11. 使用mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。 然后将内存指针返回给用户。
  12. 判断是否为第一次调用malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初 始化过了，主分配区则调用 sbrk()增加 heap 空间，分主分配区则在 top chunk 中切 割出一个 chunk，使之满足分配需求，并将内存指针返回给用户。

问题

  • 用了什么算法?
  • 分配的步骤大概为?

总结

这里用了华庭师傅的总结

  • 根据用户请求分配的内存的大小，ptmalloc 有可能会在两个地方为用户分配内存空间。
  • 在第一次分配内存时，一般情况下只存在一个主分配区，但也有可能从父进程那里继承来了多个非主分配区，在这里主要讨论主分配区的情况.
  • 开始时brk 值等于 start_brk，所以实际上 heap 大小为 0，top chunk 大小也是 0。这时，如果不增加 heap 大小，就不能满足任何分配要求。
  • 若用户的请求的内存大小小于mmap 分配阈值， 则 ptmalloc 会初始 heap。然后在 heap 中分配空间给用户，以后的分配就基于这个 heap 进行。
  • 若第一次用户的请求就大于 mmap 分配阈值，则 ptmalloc 直接使用 mmap()分配 一块内存给用户，而 heap 也就没有被初始化，直到用户第一次请求小于 mmap 分配阈 值的内存分配。
  • 第一次以后的分配就比较复杂了
    • 简单说来，ptmalloc首先会查找fast bins
    • 如果不能找到匹配的 chunk，则查找 small bins。
    • 若还是不行，合并 fast bins，把 chunk 加入 unsorted bin，在 unsorted bin 中查找
    • 若还是不行，把 unsorted bin 中的 chunk 全 加入 large bins 中，并查找 large bins。
    • 在 fast bins 和 small bins 中的查找都需要精确匹配， 而在 large bins 中查找时，则遵循“smallest-first，best-fit”的原则，不需要精确匹配。
    • 若以上方法都失败了，则 ptmalloc 会考虑使用 top chunk。
    • 若 top chunk 也不能满足分配 要求。而且所需 chunk 大小大于 mmap 分配阈值，则使用 mmap 进行分配。否则增加 heap，增大 top chunk。以满足分配要求

内存回收概述

free() 函数接受一个指向分配区域的指针作为参数，释放该指针所指向的 chunk。而具体的释放方法则看该 chunk 所处的位置和该 chunk 的大小

工作步骤

  1. free()函数同样首先需要获取分配区的锁，来保证线程安全。
  2. 判断传入的指针是否为 0，如果为 0，则什么都不做，直接 return。否则转下一步。
  3. 判断所需释放的 chunk 是否为 mmaped chunk，如果是，则调用 munmap()释放 mmaped chunk，解除内存空间映射，该该空间不再有效。如果开启了mmap 分配 阈值的动态调整机制，并且当前回收的 chunk 大小大于mmap 分配阈值，将mmap 分配阈值设置为该 chunk 的大小，将 mmap 收缩阈值设定为 mmap 分配阈值的 2 倍，释放完成，否则跳到下一步。
  4. 判断 chunk 的大小和所处的位置，若 chunk_size <= max_fast，并且 chunk 并不位于 heap 的顶部，也就是说并不与 top chunk 相邻，则转到下一步，否则跳到第 6 步。 （因为与 top chunk 相邻的小 chunk 也和 top chunk 进行合并，所以这里不仅需要 判断大小，还需要判断相邻情况）
  5. 将 chunk 放到 fast bins 中，chunk 放入到 fast bins 中时，并不修改该 chunk 使用状 态位 P。也不与相邻的 chunk 进行合并。只是放进去，如此而已。这一步做完之后 释放便结束了，程序从 free()函数中返回。
  6. 判断前一个 chunk 是否处在使用中，如果前一个块也是空闲块，则合并。并转下一 步。
  7. 判断当前释放 chunk 的下一个块是否为 top chunk，如果是，则转第 9 步，否则转 下一步。
  8. 判断下一个 chunk 是否处在使用中，如果下一个 chunk 也是空闲的，则合并，并将合并后的 chunk 放到 unsorted bin 中。注意，这里在合并的过程中，要更新 chunk 的大小，以反映合并后的 chunk 的大小。并转到第 10 步。
  9. 如果执行到这一步，说明释放了一个与 top chunk 相邻的 chunk。则无论它有多大， 都将它与 top chunk 合并，并更新 top chunk 的大小等信息。转下一步。
  10. 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD（默认 64KB），如果是的话，则会触发进行 fast bins 的合并操作，fast bins 中的 chunk 将被 遍历，并与相邻的空闲 chunk 进行合并，合并后的 chunk 会被放到 unsorted bin 中。 fast bins 将变为空，操作完成之后转下一步。
  11. 判断 top chunk 的大小是否大于mmap 收缩阈值（默认为 128KB），如果是的话，对 于主分配区，则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的 128KB 空间是不会归还的，ptmalloc 会一直管理这部分内存，用于响应用户的分配 请求；如果为非主分配区，会进行 sub-heap 收缩，将 top chunk 的一部分返回给操作系统，如果 top chunk 为整个 sub-heap，会把整个 sub-heap 还回给操作系统。做 完这一步之后，释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前 free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k，并且要 top chunk 的大 小要达到mmap 收缩阈值，才有可能收缩堆。

问题

  • 概述一下大概过程?
  • 有什么特点?

总结

  1. 先获取锁,然后判断指针是否为0,为0就直接return
  2. 否则判断是否时mmap分配的,是就直接删除映射,进行动态阈值调整
  3. 否则就判断chunk的大小和位置,如果 chunk < max_fast 并且不位于heap顶部,就放入fast bins中
  4. 否则判断前一个chunk是否在使用中,如果前一个也是空闲块就合并然后放入unsorted bins中
  5. 判断是否大于FASTBIM_CONNSOLIDATION_THRESHOLD,若大于就合并fast bins然后放入unsorted中,此时Fast bins变为空
  6. 判断top chunk大小是否大于mmap收缩阈值,若是
    • 主分配区就归还top chunk的一部分给系统,开始的128KB不会归还
    • 非主分配区会进行sub-heap的收缩,将其中一部分归还给操作系统,若top chunk为整个sub-heap就全部归还
    • 如果chunk与top chunk相邻也要如此操作

关于源代码的相关分析部分这里就不记了,读完华庭师傅的文章收益良多,可能得多读几遍才能领会其中奥秘

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！