精华内容
下载资源
问答
  • 其底层采取了分箱式内存管理机制,也就是实现了一个类似哈希桶结构的内存池,当我们通过malloc和free申请和释放内存的时候,ptmalloc就会代替我们将这些内存进行管理,通过一系列的内存合并、申请策略,来让用户申请...


    C++ STL : SGI-STL空间配置器源码剖析
    Linux 内存管理 | 物理内存管理:物理内存、内存碎片、伙伴系统、slab分配器
    Linux 内存管理 | 虚拟内存管理:虚拟内存空间、虚拟内存分配

    在之前的几篇博客中,我曾经介绍过STL空间配置器、BuddySystem、Slab分配器等内存管理机制,也曾经简单的提及过linux用户态内存分配的策略,这一次就来深入讲一讲在用户态进行内存分配时,到底做了什么。


    ptmalloc

    在Linux中,当我们申请的内存小于128K时,malloc会使用sbrk或者brk区分配内存。而当我们申请大于128K的大块空间时,会使用mmap映射区进行分配。

    但是由于上述的brk/sbrk/mmap都属于系统调用,因此当我们每次调用它们时,就会从用户态切换至内核态,在内核态完成内存分配后再返回用户态。

    倘若每次申请内存都要因为系统调用而产生大量的CPU开销,那么性能会大打折扣。并且从上面的图我们也可以看出来,堆是从低地址往高地址增长,如果低地址的内存没有被释放,则高地址的内存就不能被回收,就会产生内存碎片的问题。

    那么Linux中的malloc是如何实现解决这个问题的呢?

    这就要提到大名鼎鼎的ptmalloc了,ptmalloc是glibc中默认的内存管理器。其底层采取了分箱式内存管理机制,也就是实现了一个类似哈希桶结构的内存池,当我们通过mallocfree申请和释放内存的时候,ptmalloc就会代替我们将这些内存进行管理,通过一系列的内存合并、申请策略,来让用户申请和释放内存的时候更加的高效且安全。

    下面就来详细的介绍一下ptmalloc的工作原理


    设计假设

    ptmalloc在设计时集合了高效率、高空间利用率、高可用等目标,因此有了如下几种设计假设

    1. 具有长生命周期的大内存分配使用 mmap
    2. 特别大的内存分配总是使用 mmap
    3. 具有短生命周期的内存分配使用 brk,因为用 mmap 映射匿名页,当发生缺页异常
      时,linux 内核为缺页分配一个新物理页,并将该物理页清 0,一个 mmap 的内存块
      需要映射多个物理页,导致多次清 0 操作,很浪费系统资源,所以引入了 mmap
      分配阈值动态调整机制,保证在必要的情况下才使用 mmap 分配内存。
    4. 尽量只缓存临时使用的空闲小内存块,对大内存块或是长生命周期的大内存块在释
      放时都直接归还给操作系统。
    5. 对空闲的小内存块只会在 mallocfree 的时候进行合并,free 时空闲内存块可能放入 内存池中,不一定归还给操作系统。
    6. 收缩堆的条件是当前 free 的块大小加上前后能合并 chunk 的大小大于 64KB、,并且
      堆顶的大小达到阈值,才有可能收缩堆,把堆最顶端的空闲内存返回给操作系统。
    7. 需要保持长期存储的程序不适合用 ptmalloc 来管理内存。
    8. 为了支持多线程,多个线程可以从同一个分配区(arena)中分配内存,ptmalloc
      假设线程 A 释放掉一块内存后,线程 B 会申请类似大小的内存,但是 A 释放的内
      存跟 B 需要的内存不一定完全相等,可能有一个小的误差,就需要不停地对内存块
      作切割和合并,这个过程中可能产生内存碎片。

    Arena

    在老版本的glibc中使用的内存分配器是dlmalloc,其底层对于多线程的支持并不友好,因为所有线程共享同一个内存管理结构。所以当多个线程并发执行malloc时,为了保证线程安全,其通过使用互斥锁进行加锁,使得只能有一个线程能够访问临界资源,因此在并发环境下使用dlmalloc时会花费大量的时间在互斥锁的阻塞等待上,因此整个应用的效率极低。

    而在ptmalloc中,为了解决多线程并发争抢锁的问题, 其设定了主分配区main_arean和非主分配区non_main_arena

    • 每个进程有一个主分配区,以及多个非主分配区
    • 主分配区可以使用brkmmap来分配空间,而非主分配区只能使用mmap
    • 非主分配区的数量只能增加,不能减少
    • 主分配区和非主分配区使用环形链表进行管理,并使用互斥锁保证线程安全

    通过引入多个非主分配区,就可以将线程分发到不同的分配区中,将原先多个线程共享一个分配区变为了多个线程共享多个分配区,在一定程度上减轻了并发的压力。


    Chunk

    和其他内存管理机制一样,ptmalloc通过一个名为chunk的数据结构来管理和组织内存单元。为了节约内存,在使用时它的结构分为空闲的chuck使用中的chuck两个版本

    使用中的chuck:
    在这里插入图片描述

    • chuck指针指向chuck的起始地址,mem指针指向用户使用的内存块的起始地址,而next chunk则指向下一个chuck。
    • 在第二个域中,最低的一位p表示前一个chuck是否空闲,主要用于合并内存块的操作。当p=1时代表着上一次chunk正在使用,此时prev_size无效。p=0时代表前一个chuck空闲,prev_size有效。在ptmalloc分配第一个chuck时,总会将p置为1,防止程序越界访问。
    • M用于表示内存所处的区域,当M=1时为mmap映射区域分配,M=0为heap区域分配。
    • A用于标示分配区,A=1为非主分配区分配,A=0为主分配区分配。

    空闲的chuck:
    在这里插入图片描述

    • 空闲的chuck会被放到空闲的链表bins上,当用户申请内存时,其会先去bins上查找是否存在合适的内存。
    • 对于空闲的chuck,为了方便其在空闲链表上快速查找合适大小的chuck,他有指向上一个和下一个空闲chuck的指针,同时还有指向上一个和下一个空闲chuck的内存大小的指针。

    Bins

    对于空闲的shunk,ptmalloc采用分箱式内存管理,通过bins来维护这些空闲的chunk。ptmalloc一共维护了128个bin,同时每个bin中又维护了一个大小相近的chunk链表,如下图
    在这里插入图片描述
    根据chunk的大小以及状态不同,bins又分为以下四个种类

    • fast bins:fast bins是small bins的高速缓冲区,享有最快的内存分配、释放速度。当用户释放一块小于等于MAX_FAST(默认为64字节)的chunk时,会默认将其存放到fast bins中。当用户需要分配小内存时,会首先查看fast bins中是否存在合适的内存块,如果有则直接返回,如果没有才会去查看small bins上的空闲chunk。同时,ptmalloc会遍历fast bins,查看是否有合适的chunk需要合并,则将其合并后放入unsorted bin中
    • unsorted bin:unsorted bin只有一个,是bins的第一个位置。当用户释放的内存大雨MAX_FAST或者fast bins合并后的chunk都会进入unsorted bin上,当用户malloc的时候会先到unsorted bin上查找是否存在合适的bin,如果没有合适的bin,ptmalloc则会将unsorted bin伤的chunk放入bins上,然后再到bins上查找合适的空闲chunk。
    • small bins:用于存放固定大小的chunk,总共有64个bin,bin的大小从16字节开始,以8字节不断递增。当我们需要分配小内存块时,会采用精确匹配的方式从small bins中查找到合适的chunk。
    • large bins:用于存放大于512字节的空闲chunk,共有64个bin,bin按照顺序不定长升序排列,同时每个bin中的chunk按照大小降序排列

    从上面我们可以得出以下结论

    • fast bins相当于small bins的cache,用于提高小内存的分配、释放效率,但也同时可能加剧内存碎片化
    • unsorted bin其实就是最近释放的内存集合,它会保留最近释放的chunk,从而消除了寻找合适的bin的时间开销,提高了内存分配和释放的效率
    • small bins和large bins可以合并相邻的空闲chunk,减轻了内存碎片化,但也同时降低了效率

    当然,如果在上面的任何一个bin中都没办法找到合适的内存块,ptmalloc中还预留了其他的一些后备方式。

    • top chunk:在分配区中最顶部的chunk被称为top chunk,它不属于任何一个bin。当所有bin中都没有合适的内存时,就由它来响应用户请求。当用户申请的内存小于top chunk的内存时,其会将自己分割为两部分,一部分返回,另一部分则成为新的top chunk。如果用户申请的内存大于top chunk的内存,则top chunk会根据分配区的不同,分别调用sbrk或者mmap来进行扩容。
    • last remainder chunk:即最后一次small request中因分割而得到的剩余部分,它有利于改进局部性,当在small bins中找不到合适的chunk时,如果last remainded chunk的大小大于所需要的small chunk大小时,其就会将用户需要的那一部分分出去,剩余的部分则成为新的last remainded chunk,因此后续请求的chunk最终将被分配得彼此接近。
    • mmaped chunk:当分配的内存非常大的时候(大于128K),此时就需要通过mmap来申请内存,通过mmap申请的内存会被放到mmaped chunk上。同时,在释放的时候会通过判断chunk中的M是否为1来判断是否属于mmaped chunk,如果是则直接将内存交还给操作系统

    内存分配、释放流程

    分配流程:

    1. 获取分配区的锁
    2. 计算出需要分配内存的chunk大小
    3. 判断chunk的大小,如果小于MAX_FAST则到fast_bins上查找,如果小于512字节,则到small bins上查找
    4. 如果还没有找到,此时则进入unsorted bin上查找,如果找到合适的chunk并进行分配后还有剩余的空间,则根据其空间大小将其放入small bins或者large bins中。
    5. 进入large bins中查找,找到合适的bin后反向进行遍历,找到第一个大小满足的chunk进行分配,如果chunk分配完后还有剩余的空间,则将其放入unsorted bin中。
    6. 如果查找了所有的bin都没有找到合适的chunk,此时就需要操作top chunk来进行分配,如果满足大小小于top chunk,则切割top chunk来进行分配。如果大小大于top chunk,则此时会申请内存来满足分配需求。

    释放流程:

    1. 获取分配区的锁
    2. 判断free的参数是否为空节点,如果是则什么都不做
    3. 判断当前chunk是否是mmap映射出的大块内存(M=1),如果是的话直接munmap释放掉
    4. 判断当前chunk是否和top chunk连续,如果连续则直接和top chunk合并
    5. 判断chunk大小是否大于MAX_FAST,如果大于则放入unsorted bin中,并检查是否能够进行合并,如果不能合并则直接free,如果能则进入步骤8
    6. 如果chunk大小小于MAX_FAST,则放入fast bins中,并判断是否有合并的情况,如果没有合并则free,如果有则进入下一步骤
    7. 在fast bin中,如果当前当前chunk能够进行合并,则将合并后的chunk放入unsorted bin中。
    8. 判断top chunk的大小是否大于mmap收缩阈值,如果满足则试图归还多出的那一部分给操作系统

    总结

    从上面的内容我们可以看出,ptmalloc虽然能够很好的进行内存管理,但是仍然存在着一系列的小问题,如:

    • 由于ptmalloc收缩内存是从top chunk开始,如果与top chunk相邻的chunk不能够释放,则top chunk以下的chunk都无法释放(即使后分配的内存先释放,也无法及时归还给系统)
    • 每个chunk至少为8字节(可能导致内存内碎片)
    • 虽然采用了主分配区+非主分配区的策略来优化多线程环境下的并发问题,但是在内存分配和释放的时候仍会首先进行加锁(影响性能)
    • 由于采用了非主分配区,导致内存不能在不同分配区间移动,内存使用不均衡(内存浪费)
    • 不定期分配长生命周期的内存(不利于回收,容易导致内存碎片)

    所以后来各大厂商为了能够提升效率,开发出了如tcmallocjemalloc等内存分配器,但作为linux默认内存管理器的ptmalloc,以其稳定性始终占据着一席之地。

    展开全文
  • 结合网上的一些文章和个人的理解,对ptmalloc实现原理做一些总结。 内存布局  介绍ptmalloc之前,我们先了解一下内存布局,以x86的32位系统为例:    从上图可以看到,栈至顶向下扩展,堆至底向上扩展...

    本文转载自:https://blog.csdn.net/z_ryan/article/details/79950737

      本文主要介绍了ptmalloc对于内存分配的管理。结合网上的一些文章和个人的理解,对ptmalloc的实现原理做一些总结。

    内存布局

      介绍ptmalloc之前,我们先了解一下内存布局,以x86的32位系统为例:
      这里写图片描述
      从上图可以看到,栈至顶向下扩展,堆至底向上扩展, mmap 映射区域至顶向下扩展。 mmap 映射区域和堆相对扩展,直至耗尽虚拟地址空间中的剩余区域,这种结构便于 C 运行时库使用 mmap 映射区域和堆进行内存分配。

    brk(sbrk)和mmap函数

      首先,linux系统向用户提供申请的内存有brk(sbrk)和mmap函数。下面我们先来了解一下这几个函数。

    brk() 和 sbrk()

    #include <unistd.h>
    int brk( const void *addr )
    void* sbrk ( intptr_t incr );
     
    • 1
    • 2
    • 3

    两者的作用是扩展heap的上界brk
    Brk()的参数设置为新的brk上界地址,成功返回1,失败返回0;
    Sbrk()的参数为申请内存的大小,返回heap新的上界brk的地址

    mmap()

    #include <sys/mman.h>
    void *mmap(void *addr, size\_t length, int prot, int flags, int fd, off\_t offset);
    int munmap(void *addr, size_t length);
     
    • 1
    • 2
    • 3

    Mmap的第一种用法是映射此盘文件到内存中;第二种用法是匿名映射,不映射磁盘文件,而向映射区申请一块内存。
    Malloc使用的是mmap的第二种用法(匿名映射)。
    Munmap函数用于释放内存。

    主分配区和非主分配区

    Allocate的内存分配器中,为了解决多线程锁争夺问题,分为主分配区main_area和非主分配区no_main_area。
     1. 主分配区和非主分配区形成一个环形链表进行管理。
     2. 每一个分配区利用互斥锁使线程对于该分配区的访问互斥。
     3. 每个进程只有一个主分配区,也可以允许有多个非主分配区。
     4. ptmalloc根据系统对分配区的争用动态增加分配区的大小,分配区的数量一旦增加,则不会减少。
     5. 主分配区可以使用brk和mmap来分配,而非主分配区只能使用mmap来映射内存块
     6. 申请小内存时会产生很多内存碎片,ptmalloc在整理时也需要对分配区做加锁操作。

    当一个线程需要使用malloc分配内存的时候,会先查看该线程的私有变量中是否已经存在一个分配区。若是存在。会尝试对其进行加锁操作。若是加锁成功,就在使用该分配区分配内存,若是失败,就会遍历循环链表中获取一个未加锁的分配区。若是整个链表中都没有未加锁的分配区,则malloc会开辟一个新的分配区,将其加入全局的循环链表并加锁,然后使用该分配区进行内存分配。当释放这块内存时,同样会先获取待释放内存块所在的分配区的锁。若是有其他线程正在使用该分配区,则必须等待其他线程释放该分配区互斥锁之后才能进行释放内存的操作。

    Malloc实现原理:

      因为brk、sbrk、mmap都属于系统调用,若每次申请内存,都调用这三个,那么每次都会产生系统调用,影响性能;其次,这样申请的内存容易产生碎片,因为堆是从低地址到高地址,如果高地址的内存没有被释放,低地址的内存就不能被回收。
      
      所以malloc采用的是内存池的管理方式(ptmalloc),Ptmalloc 采用边界标记法将内存划分成很多块,从而对内存的分配与回收进行管理。为了内存分配函数malloc的高效性,ptmalloc会预先向操作系统申请一块内存供用户使用,当我们申请和释放内存的时候,ptmalloc会将这些内存管理起来,并通过一些策略来判断是否将其回收给操作系统。这样做的最大好处就是,使用户申请和释放内存的时候更加高效,避免产生过多的内存碎片。

    chunk 内存块的基本组织单元

    在 ptmalloc 的实现源码中定义结构体 malloc_chunk 来描述这些块。malloc_chunk 定义如下:

    1.struct malloc_chunk {  
    2.  INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */  
    3.  INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */  
    4.  
    5.  struct malloc_chunk* fd;           /* double links -- used only if free. */  
    6.  struct malloc_chunk* bk;  
    7.  
    8.  /* Only used for large blocks: pointer to next larger size.  */  
    9.  struct malloc_chunk* fd_nextsize;      /* double links -- used only if free. */  
    10.  struct malloc_chunk* bk_nextsize; 
    11.};  
     
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    chunk 的定义相当简单明了,对各个域做一下简单介绍 :
      prev_size: 如果前一个 chunk 是空闲的,该域表示前一个 chunk 的大小,如果前一个 chunk 不空闲,该域无意义。
      size :当前 chunk 的大小,并且记录了当前 chunk 和前一个 chunk 的一些属性,包括前一个 chunk 是否在使用中,当前 chunk 是否是通过 mmap 获得的内存,当前 chunk 是否属于非主分配区。
       fd 和 bk : 指针 fd 和 bk 只有当该 chunk 块空闲时才存在,其作用是用于将对应的空闲 chunk 块加入到空闲chunk 块链表中统一管理,如果该 chunk 块被分配给应用程序使用,那么这两个指针也就没有用(该 chunk 块已经从空闲链中拆出)了,所以也当作应用程序的使用空间,而不至于浪费。
      fd_nextsize 和 bk_nextsize: 当当前的 chunk 存在于 large bins 中时, large bins 中的空闲 chunk 是按照大小排序的,但同一个大小的 chunk 可能有多个,增加了这两个字段可以加快遍历空闲 chunk ,并查找满足需要的空闲 chunk , fd_nextsize 指向下一个比当前 chunk 大小大的第一个空闲 chunk , bk_nextszie 指向前一个比当前 chunk 大小小的第一个空闲 chunk 。 如果该 chunk 块被分配给应用程序使用,那么这两个指针也就没有用(该chunk 块已经从 size 链中拆出)了,所以也当作应用程序的使用空间,而不至于浪费。

    chunk的结构

      chunk的结构可以分为使用中的chunk和空闲的chunk。使用中的chunk和空闲的chunk数据结构基本项同,但是会有一些设计上的小技巧,巧妙的节省了内存。

    使用中的chunk:

    使用中的chunk:

    说明:
      1、 chunk指针指向chunk开始的地址;mem指针指向用户内存块开始的地址。
      2、 p=0时,表示前一个chunk为空闲,prev_size才有效
      3、p=1时,表示前一个chunk正在使用,prev_size无效 p主要用于内存块的合并操作;ptmalloc 分配的第一个块总是将p设为1, 以防止程序引用到不存在的区域
      4、M=1 为mmap映射区域分配;M=0为heap区域分配
      5、 A=0 为主分配区分配;A=1 为非主分配区分配。

    空闲的chunk:

    空间中的chunk

    说明:
      1、当chunk空闲时,其M状态是不存在的,只有AP状态,
      2、原本是用户数据区的地方存储了四个指针,
        指针fd指向后一个空闲的chunk,而bk指向前一个空闲的chunk,malloc通过这两个指针将大小相近的chunk连成一个双向链表。
        在large bin中的空闲chunk,还有两个指针,fd_nextsize和bk_nextsize,用于加快在large bin中查找最近匹配的空闲chunk。不同的chunk链表又是通过bins或者fastbins来组织的。

    空闲链表bins

      当用户使用free函数释放掉的内存,ptmalloc并不会马上交还给操作系统,而是被ptmalloc本身的空闲链表bins管理起来了,这样当下次进程需要malloc一块内存的时候,ptmalloc就会从空闲的bins上寻找一块合适大小的内存块分配给用户使用。这样的好处可以避免频繁的系统调用,降低内存分配的开销。
      malloc将相似大小的chunk用双向链表链接起来,这样一个链表被称为一个bin。ptmalloc一共维护了128bin。每个bins都维护了大小相近的双向链表的chunk。基于chunk的大小,有下列几种可用bins:
      1、Fast bin
      2、Unsorted bin
      3、Small bin
      4、Large bin
      
      保存这些bin的数据结构为:
      fastbinsY:这个数组用以保存fast bins。
      bins:这个数组用以保存unsorted、small以及large bins,共计可容纳126个:

      当用户调用malloc的时候,能很快找到用户需要分配的内存大小是否在维护的bin上,如果在某一个bin上,就可以通过双向链表去查找合适的chunk内存块给用户使用。
      这里写图片描述

      1. fast bins
      程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后,也许马上就会有另一个小块内存的请求,这样分配器又需要从大的空闲内存中切分出一块,这样无疑是比较低效的,故而,malloc 中在分配过程中引入了 fast bins,
      fast bins是bins的高速缓冲区,大约有10个定长队列。每个fast bin都记录着一条free chunk的单链表(称为binlist ,采用单链表是出于fast bin中链表中部的chunk不会被摘除的特点),增删chunk都发生在链表的前端。 fast bins 记录着大小以8字节递增的bin链表。
      当用户释放一块不大于max_fast(默认值64B)的chunk的时候,会默认会被放到fast bins上。当需要给用户分配的 chunk 小于或等于 max_fast 时,malloc 首先会到fast bins上寻找是否有合适的chunk,
      除非特定情况,两个毗连的空闲chunk并不会被合并成一个空闲chunk。不合并可能会导致碎片化问题,但是却可以大大加速释放的过程!
      分配时,binlist中被检索的第一个个chunk将被摘除并返回给用户。free掉的chunk将被添加在索引到的binlist的前端。
      这里写图片描述
      2. unsorted bin
      unsorted bin 的队列使用 bins 数组的第一个,是bins的一个缓冲区,加快分配的速度。当用户释放的内存大于max_fast或者fast bins合并后的chunk都会首先进入unsorted bin上。chunk大小 – 无尺寸限制,任何大小chunk都可以添加进这里。这种途径给予 ‘glibc malloc’ 第二次机会以重新使用最近free掉的chunk,这样寻找合适bin的时间开销就被抹掉了,因此内存的分配和释放会更快一些。
      用户malloc时,如果在 fast bins 中没有找到合适的 chunk,则malloc 会先在 unsorted bin 中查找合适的空闲 chunk,如果没有合适的bin,ptmalloc会将unsorted bin上的chunk放入bins上,然后到bins上查找合适的空闲chunk。
      3. small bins
      大小小于512字节的chunk被称为small chunk,而保存small chunks的bin被称为small bin。数组从2开始编号,前64个bin为small bins,small bin每个bin之间相差8个字节,同一个small bin中的chunk具有相同大小。
      每个small bin都包括一个空闲区块的双向循环链表(也称binlist)。free掉的chunk添加在链表的前端,而所需chunk则从链表后端摘除。
      两个毗连的空闲chunk会被合并成一个空闲chunk。合并消除了碎片化的影响但是减慢了free的速度。
      分配时,当samll bin非空后,相应的bin会摘除binlist中最后一个chunk并返回给用户。在free一个chunk的时候,检查其前或其后的chunk是否空闲,若是则合并,也即把它们从所属的链表中摘除并合并成一个新的chunk,新chunk会添加在unsorted bin链表的前端。
      4.large bins
      大小大于等于512字节的chunk被称为large chunk,而保存large chunks的bin被称为large bin,位于small bins后面。large bins中的每一个bin分别包含了一个给定范围内的chunk,其中的chunk按大小递减排序,大小相同则按照最近使用时间排列。
      两个毗连的空闲chunk会被合并成一个空闲chunk。
      分配时,遵循原则“smallest-first , best-fit”,从顶部遍历到底部以找到一个大小最接近用户需求的chunk。一旦找到,相应chunk就会分成两块User chunk(用户请求大小)返回给用户。
    Remainder chunk(剩余大小添加到unsorted bin。free时和small bin 类似。

    并不是所有chunk都按照上面的方式来组织,有三种列外情况。top chunk,mmaped chunk 和last remainder chunk
      1. Top chunk
      top chunk相当于分配区的顶部空闲内存,当bins上都不能满足内存分配要求的时候,就会来top chunk上分配。
      当top chunk大小比用户所请求大小还大的时候,top chunk会分为两个部分:User chunk(用户请求大小)和Remainder chunk(剩余大小)。其中Remainder chunk成为新的top chunk。
      当top chunk大小小于用户所请求的大小时,top chunk就通过sbrk(main arena)或mmap(thread arena)系统调用来扩容。
      2. mmaped chunk
      当分配的内存非常大(大于分配阀值,默认128K)的时候,需要被mmap映射,则会放到mmaped chunk上,当释放mmaped chunk上的内存的时候会直接交还给操作系统。
      3、Last remainder chunk
      Last remainder chunk是另外一种特殊的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 chunk。

    sbrk与mmap

      在堆区中, 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 又会使用 fastbins 和 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 中分配的空间则可能会留在进程内存空间内,还可以再次引用(当然是很危险的)。
      

    内存分配malloc流程

    1. 获取分配区的锁,防止多线程冲突。
    2. 计算出实际需要分配的内存的chunk实际大小。
    3. 判断chunk的大小,如果小于max_fast(64B),则尝试去fast bins上取适合的chunk,如果有则分配结束。否则,下一步;
    4. 判断chunk大小是否小于512B,如果是,则从small bins上去查找chunk,如果有合适的,则分配结束。否则下一步;
    5. ptmalloc首先会遍历fast bins中的chunk,将相邻的chunk进行合并,并链接到unsorted bin中然后遍历 unsorted bins。如果unsorted bins上只有一个chunk并且大于待分配的chunk,则进行切割,并且剩余的chunk继续扔回unsorted bins;如果unsorted bins上有大小和待分配chunk相等的,则返回,并从unsorted bins删除;如果unsorted bins中的某一chunk大小 属于small bins的范围,则放入small bins的头部;如果unsorted bins中的某一chunk大小 属于large bins的范围,则找到合适的位置放入。若未分配成功,转入下一步;
    6. 从large bins中查找找到合适的chunk之后,然后进行切割,一部分分配给用户,剩下的放入unsorted bin中。
    7. 如果搜索fast bins和bins都没有找到合适的chunk,那么就需要操作top chunk来进行分配了
      当top chunk大小比用户所请求大小还大的时候,top chunk会分为两个部分:User chunk(用户请求大小)和Remainder chunk(剩余大小)。其中Remainder chunk成为新的top chunk。
        当top chunk大小小于用户所请求的大小时,top chunk就通过sbrk(main arena)或mmap(thread arena)系统调用来扩容。
    8. 到了这一步,说明 top chunk 也不能满足分配要求,所以,于是就有了两个选择: 如 果是主分配区,调用 sbrk(),增加 top chunk 大小;如果是非主分配区,调用 mmap 来分配一个新的 sub-heap,增加 top chunk 大小;或者使用 mmap()来直接分配。在 这里,需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值,如果是的话,则转下一步,调用 mmap 分配, 否则跳到第 10 步,增加 top chunk 的大小。
    9. 使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。 然后将内存指针返回给用户。
    10. 判断是否为第一次调用 malloc,若是主分配区,则需要进行一次初始化工作,分配 一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初 始化过了,主分配区则调用 sbrk()增加 heap 空间,分主分配区则在 top chunk 中切 割出一个 chunk,使之满足分配需求,并将内存指针返回给用户。

    简而言之: 获取分配区(arena)并加锁–> fast bin –> unsorted bin –> small bin –> large bin –> top chunk –> 扩展堆

    内存回收流程

    1. 获取分配区的锁,保证线程安全。
    2. 如果free的是空指针,则返回,什么都不做。
    3. 判断当前chunk是否是mmap映射区域映射的内存,如果是,则直接munmap()释放这块内存。前面的已使用chunk的数据结构中,我们可以看到有M来标识是否是mmap映射的内存。
    4. 判断chunk是否与top chunk相邻,如果相邻,则直接和top chunk合并(和top chunk相邻相当于和分配区中的空闲内存块相邻)。转到步骤8
    5. 如果chunk的大小大于max_fast(64b),则放入unsorted bin,并且检查是否有合并,有合并情况并且和top chunk相邻,则转到步骤8;没有合并情况则free。
    6. 如果chunk的大小小于 max_fast(64b),则直接放入fast bin,fast bin并没有改变chunk的状态。没有合并情况,则free;有合并情况,转到步骤7
    7. 在fast bin,如果当前chunk的下一个chunk也是空闲的,则将这两个chunk合并,放入unsorted bin上面。合并后的大小如果大于64B,会触发进行fast bins的合并操作,fast bins中的chunk将被遍历,并与相邻的空闲chunk进行合并,合并后的chunk会被放到unsorted bin中,fast bin会变为空。合并后的chunk和topchunk相邻,则会合并到topchunk中。转到步骤8
    8. 判断top chunk的大小是否大于mmap收缩阈值(默认为128KB),如果是的话,对于主分配区,则会试图归还top chunk中的一部分给操作系统。free结束。

    使用注意事项

    为了避免Glibc内存暴增,需要注意:
      1. 后分配的内存先释放,因为ptmalloc收缩内存是从top chunk开始,如果与top chunk相邻的chunk不能释放,top chunk以下的chunk都无法释放。
      2. Ptmalloc不适合用于管理长生命周期的内存,特别是持续不定期分配和释放长生命周期的内存,这将导致ptmalloc内存暴增。
      3. 不要关闭 ptmalloc 的 mmap 分配阈值动态调整机制,因为这种机制保证了短生命周期的 内存分配尽量从 ptmalloc 缓存的内存 chunk 中分配,更高效,浪费更少的内存。
      4. 多线程分阶段执行的程序不适合用ptmalloc,这种程序的内存更适合用内存池管理
      5. 尽量减少程序的线程数量和避免频繁分配/释放内存。频繁分配,会导致锁的竞争,最终导致非主分配区增加,内存碎片增高,并且性能降低。
      6. 防止内存泄露,ptmalloc对内存泄露是相当敏感的,根据它的内存收缩机制,如果与top chunk相邻的那个chunk没有回收,将导致top chunk一下很多的空闲内存都无法返回给操作系统。
      7. 防止程序分配过多的内存,或是由于glibc内存暴增,导致系统内存耗尽,程序因为OOM被系统杀掉。预估程序可以使用的最大物理内存的大小,配置系统的/proc/sys/vm/overcommit_memory ,/proc/sys/vm/overcommit_ratio,以及使用ulimit -v限制程序能使用的虚拟内存的大小,防止程序因OOM被杀死掉。

    参考:Glibc内存管理 华庭
    http://www.valleytalk.org/wp-content/uploads/2015/02/glibc%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86ptmalloc%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%901.pdf

    展开全文
  • https://blog.csdn.net/z_ryan/article/details/79950737 ... 实现细节请看:https://blog.csdn.net/songchuwang1868/article/details/90144080 目录 一、前言 二、内存布局 三、...

    https://blog.csdn.net/z_ryan/article/details/79950737

    https://blog.csdn.net/phenics/article/details/777053

    实现细节请看:https://blog.csdn.net/songchuwang1868/article/details/90144080

    目录

    一、前言

    二、内存布局

    三、brk(sbrk)和mmap函数

    1、brk() 和 sbrk()

    2、mmap()

    四、Allocator

    五、Malloc实现原理

    1、chunk 内存块的基本组织单元

    2、chunk的结构

    a、使用中的chunk

    b、空闲的chunk

    c、chunk中的空间复用

    2、空闲链表bins

    a、fast bins 

    b、unsorted bin 

    c、small bins 

    d、large bins 

    3、三种特殊的chunk

    a、top chunk 

    b、mmaped chunk 

    c、last remainder chunk 

    六、sbrk与mmap

    七、主分配区和非主分配区

    八、内存分配malloc流程

    九、内存回收流程

    十、使用注意事项


     

    一、前言

    C语言提供了动态内存管理功能, 在C语言中, 程序员可以使用 malloc() 和 free() 函数显式的分配和释放内存. 关于 malloc() 和free() 函数, C语言标准只是规定了它们需要实现的功能, 而没有对实现方式有什么限制, 这多少让那些追根究底的人感到有些许迷茫, 比如对于 free() 函数, 它规定一旦一个内存区域被释放掉, 那么就不应该再对其进行任何引用, 任何对释放区域的引用都会导致不可预知的后果 (unperdictable effects). 那么, 到底是什么样的不可预知后果呢? 这完全取决于内存分配器(memory allocator)使用的算法. 这篇文章试图对 Linux glibc 提供的 allocator 的工作方式进行一些描述, 并希望可以解答上述类似的问题. 虽然这里的描述局限于特定的平台, 但一般的事实是, 相同功能的软件基本上都会采用相似的技术. 这里所描述的原理也许在别的环境下会仍然有效. 另外还要强调的一点是, 本文只是侧重于一般原理的描述, 而不会过分纠缠于细节, 如果需要特定的细节知识, 请参考特定 allocator 的源代码. 最后, 本文描述的硬件平台是 Intel 80x86, 其中涉及的有些原理和数据可能是平台相关的.

    二、内存布局

    介绍ptmalloc之前,我们先了解一下内存布局,以x86的32位系统为例: 
      
      从上图可以看到,栈至顶向下扩展,堆至底向上扩展, mmap 映射区域至顶向下扩展。 mmap 映射区域和堆相对扩展,直至耗尽虚拟地址空间中的剩余区域,这种结构便于 C 运行时库使用 mmap 映射区域和堆进行内存分配。

    三、brk(sbrk)和mmap函数

    首先,linux系统向用户提供申请的内存有brk(sbrk)和mmap函数。下面我们先来了解一下这几个函数。

    1、brk() 和 sbrk()

    #include <unistd.h>
    int brk( const void *addr )
    void* sbrk ( intptr_t incr );

    两者的作用是扩展heap的上界brk 
    Brk()的参数设置为新的brk上界地址,成功返回1,失败返回0; 
    Sbrk()的参数为申请内存的大小,返回heap新的上界brk的地址

    2、mmap()

    #include <sys/mman.h>
    void *mmap(void *addr, size\_t length, int prot, int flags, int fd, off\_t offset);
    int munmap(void *addr, size_t length);

    Mmap的第一种用法是映射此盘文件到内存中;第二种用法是匿名映射,不映射磁盘文件,而向映射区申请一块内存。 
    Malloc使用的是mmap的第二种用法(匿名映射)。 
    Munmap函数用于释放内存。

    四、Allocator

    GNU Libc 的内存分配器( allocator ) — ptmalloc 起源于 Doug Lea 的 malloc (请参看[1]). ptmalloc 实现了 malloc() , free() 以及一组其它的函数. 以提供动态内存管理的支持. allocator 处在用户程序和内核之间, 它响应用户的分配请求, 向操作系统申请内存, 然后将其返回给用户程序, 为了保持高效的分配, allocator 一般都会预先分配一块大于用户请求的内存, 并通过某种算法管理这块内存. 来满足用户的内存分配要求, 用户 free 掉的内存也并不是立即就返回给操作系统, 相反, allocator 会管理这些被 free 掉的空闲空间, 以应对用户以后的内存分配要求. 也就是说, allocator 不但要管理已分配的内存块, 还需要管理空闲的内存块, 当响应用户分配要求时, allocator 会首先在空闲空间中寻找一块合适的内存给用户, 在空闲空间中找不到的情况下才分配一块新的内存. 为实现一个高效的 allocator, 需要考虑很多的因素. 比如, allocator 本身管理内存块所占用的内存空间必须很小, 分配算法必须要足够的快. Jonathan Bartlett 给出了一个简单的 allocator 实现[2], 事先看看或许会对理解本文有所帮助. 另外插一句, Jonathan Bartlett 的书 “Programming from Ground Up” 对想要了解 linux 汇编和工作方式的入门者是个不错的选择.

    五、Malloc实现原理

           因为brk、sbrk、mmap都属于系统调用,若每次申请内存,都调用这三个,那么每次都会产生系统调用,影响性能;其次,这样申请的内存容易产生碎片,因为堆是从低地址到高地址,如果高地址的内存没有被释放,低地址的内存就不能被回收。 
       
      所以malloc采用的是内存池的管理方式(ptmalloc),Ptmalloc 采用边界标记法将内存划分成很多块,从而对内存的分配与回收进行管理。为了内存分配函数malloc的高效性,ptmalloc会预先向操作系统申请一块内存供用户使用,当我们申请和释放内存的时候,ptmalloc会将这些内存管理起来,并通过一些策略来判断是否将其回收给操作系统。这样做的最大好处就是,使用户申请和释放内存的时候更加高效,避免产生过多的内存碎片。

    1、chunk 内存块的基本组织单元

    在 ptmalloc 的实现源码中定义结构体 malloc_chunk 来描述这些块。malloc_chunk 定义如下:

    struct malloc_chunk {  
      INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */  
      INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */  
      
      struct malloc_chunk* fd;           /* double links -- used only if free. */  
      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; 
    };  

    chunk 的定义相当简单明了,对各个域做一下简单介绍 : 
      prev_size: 如果前一个 chunk 是空闲的,该域表示前一个 chunk 的大小,如果前一个 chunk 不空闲,该域无意义。 (这里的描述有点模糊,一段连续的内存被分成多个chunk,prev_size记录的就是相邻的前一个chunk的size,知道当前chunk的地址,减去prev_size便是前一个chunk的地址。prev_size主要用于相邻空闲chunk的合并)
      size :当前 chunk 的大小,并且记录了当前 chunk 和前一个 chunk 的一些属性,包括前一个 chunk 是否在使用中,当前 chunk 是否是通过 mmap 获得的内存,当前 chunk 是否属于非主分配区。 
       fd 和 bk : 指针 fd 和 bk 只有当该 chunk 块空闲时才存在,其作用是用于将对应的空闲 chunk 块加入到空闲chunk 块链表中统一管理,如果该 chunk 块被分配给应用程序使用,那么这两个指针也就没有用(该 chunk 块已经从空闲链中拆出)了,所以也当作应用程序的使用空间,而不至于浪费。 
      fd_nextsize 和 bk_nextsize: 当前的 chunk 存在于 large bins 中时, large bins 中的空闲 chunk 是按照大小排序的,但同一个大小的 chunk 可能有多个,增加了这两个字段可以加快遍历空闲 chunk ,并查找满足需要的空闲 chunk , fd_nextsize 指向下一个比当前 chunk 大小大的第一个空闲 chunk , bk_nextszie 指向前一个比当前 chunk 大小小的第一个空闲 chunk 。(同一大小的chunk可能有多块,在总体大小有序的情况下,要想找到下一个比自己大或小的chunk,需要遍历所有相同的chunk,所以才有fd_nextsize和bk_nextsize这种设计) 如果该 chunk 块被分配给应用程序使用,那么这两个指针也就没有用(该chunk 块已经从 size 链中拆出)了,所以也当作应用程序的使用空间,而不至于浪费。

          (下面马上可以看到,当chunk为空时才有fd、bk、fd_nextsize、bd_nextsize四个指针,当chunk不为空,这四个指针的空间是直接交给用户使用的) 

    2、chunk的结构

    chunk的结构可以分为使用中的chunk和空闲的chunk。使用中的chunk和空闲的chunk数据结构基本相同,但是会有一些设计上的小技巧,巧妙的节省了内存。

    a、使用中的chunk


    说明: 
      1、 chunk指针指向chunk开始的地址;mem指针指向用户内存块开始的地址。 
      2、 p=0时,表示前一个chunk为空闲,prev_size才有效 
      3、p=1时,表示前一个chunk正在使用,prev_size无效 p主要用于内存块的合并操作;ptmalloc 分配的第一个块总是将p设为1, 以防止程序引用到不存在的区域 
      4、M=1 为mmap映射区域分配;M=0为heap区域分配 
      5、 A=0 为主分配区分配;A=1 为非主分配区分配

    b、空闲的chunk


    说明: 
      1、当chunk空闲时,其M状态是不存在的,只有AP状态(因为M表示是由brk还是mmap分配的内存,而mmap分配的内存free时直接ummap,不会放到空闲链表中。换言之空闲链表中的都死brk分配的,所以不用额外记录) 
      2、原本是用户数据区的地方存储了四个指针, 
          指针fd指向后一个空闲的chunk,而bk指向前一个空闲的chunk,malloc通过这两个指针将大小相近的chunk连成一个双向链表。 
       在large bin中的空闲chunk,还有两个指针,fd_nextsize和bk_nextsize,用于加快在large bin中查找最近匹配的空闲chunk。不同的chunk链表又是通过bins或者fastbins来组织的。

    c、chunk中的空间复用

    为了使得 chunk 所占用的空间最小, ptmalloc 使用了空间复用, 一个 chunk 或者正在被使用, 或者已经被 free 掉, 所以 chunk 的中的一些域可以在使用状态和空闲状态表示不同的意义, 来达到空间复用的效果. 空闲时, 一个 chunk 中至少要4个 size_t 大小的空间, 用来存储 prev_size, size , fd 和 bk , 也就是16 bytes(??为什么不是6个size_t呢?不是还有fd_nextsize和bk_nextsize吗?——并不是所有bin中都需要这两个指针,比如在fast_bin中,每隔8个Byte就有一个链表,每个链表中的所有chunk的size都是一样的,显然不用这两个指针) chuck 的大小要 align 到8 bytes. 当一个 chunk 处于使用状态时, 它的下一个 chunk 的 prev_size 域肯定是无效的. 所以实际上, 这个空间也可以被当前 chunk 使用. 这听起来有点不可思议, 但确实是合理空间复用的例子. 故而实际上, 一个使用中的 chunk 的大小的计算公式应该是:

     in_use_size = ( 用户请求大小 + 8 - 4 ) align to 8 bytes 这里加8是因为需要存储 prev_size 和 size, 但又因为向下一个 chunk “借”了4个bytes, 所以要减去4. 最后, 因为空闲的 chunk 和使用中的 chunk 使用的是同一块空间. 所以肯定要取其中最大者作为实际的分配空间. 即最终的分配空间 chunk_size = max(in_use_size, 16). 这就是当用户请求内存分配时, ptmalloc 实际需要分配的内存大小, 在后面的介绍中. 如果不是特别指明的地方, 指的都是这个经过转换的实际需要分配的内存大小, 而不是用户请求的内存分配大小.

    2、空闲链表bins

    当用户使用free函数释放掉的内存,ptmalloc并不会马上交还给操作系统,而是被ptmalloc本身的空闲链表bins管理起来了,这样当下次进程需要malloc一块内存的时候,ptmalloc就会从空闲的bins上寻找一块合适大小的内存块分配给用户使用。这样的好处可以避免频繁的系统调用,降低内存分配的开销。 
      malloc将相似大小的chunk用双向链表链接起来,这样一个链表被称为一个bin。ptmalloc一共维护了128bin。每个bins都维护了大小相近的双向链表的chunk。基于chunk的大小,有下列几种可用bins: 
      1、Fast bin 
      2、Unsorted bin 
      3、Small bin 
      4、Large bin 
       
      保存这些bin的数据结构为: 
      fastbinsY:这个数组用以保存fast bins。 
      bins:这个数组用以保存unsorted、small以及large bins,共计可容纳126个:

      当用户调用malloc的时候,能很快找到用户需要分配的内存大小是否在维护的bin上,如果在某一个bin上,就可以通过双向链表去查找合适的chunk内存块给用户使用。 
      

    a、fast bins 

    程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后,也许马上就会有另一个小块内存的请求,这样分配器又需要从大的空闲内存中切分出一块,这样无疑是比较低效的,故而,malloc 中在分配过程中引入了 fast bins


      fast bins是bins的高速缓冲区,大约有10个定长队列。每个fast bin都记录着一条free chunk的单链表(称为binlist ,采用单链表是出于fast bin中链表中的chunk不会被摘除的特点),增删chunk都发生在链表的前端。 fast bins 记录着大小以8字节递增的bin链表(??从上面的图看好像是4字节递增啊——4字节递增是因为指针占4字节,下面挂的块的确是8字节递增)。 
      当用户释放一块不大于max_fast(默认值64B)的chunk的时候,会默认会被放到fast bins上。当需要给用户分配的 chunk 小于或等于 max_fast 时,malloc 首先会到fast bins上寻找是否有合适的chunk。(一定大小内的chunk无论是分配还是释放,都会先在fast bin中过一遍)
      除非特定情况,两个毗连的空闲chunk并不会被合并成一个空闲chunk。不合并可能会导致碎片化问题,但是却可以大大加速释放的过程! 
      分配时,binlist中被检索的第一个个chunk将被摘除并返回给用户。free掉的chunk将被添加在索引到的binlist的前端。 

    b、unsorted bin 

      unsorted bin 的队列使用 bins 数组的第一个,是bins的一个缓冲区,加快分配的速度。当用户释放的内存大于max_fast或者fast bins合并后的chunk都会首先进入unsorted bin上。chunk大小 – 无尺寸限制,任何大小chunk都可以添加进这里。这种途径给予 ‘glibc malloc’ 第二次机会以重新使用最近free掉的chunk,这样寻找合适bin的时间开销就被抹掉了,因此内存的分配和释放会更快一些。 
      用户malloc时,如果在 fast bins 中没有找到合适的 chunk,则malloc 会先在 unsorted bin 中查找合适的空闲 chunk,如果没有合适的bin,ptmalloc会将unsorted bin上的chunk放入bins上,然后到bins上查找合适的空闲chunk。 

    c、small bins 

      大小小于512字节的chunk被称为small chunk,而保存small chunks的bin被称为small bin。数组从2开始编号,前64个bin为small bins,small bin每个bin之间相差8个字节,同一个small bin中的chunk具有相同大小。 
      每个small bin都包括一个空闲区块的双向循环链表(也称binlist)。free掉的chunk添加在链表的前端,而所需chunk则从链表后端摘除。 
      两个毗连的空闲chunk会被合并成一个空闲chunk。合并消除了碎片化的影响但是减慢了free的速度。 
      分配时,当samll bin非空后,相应的bin会摘除binlist中最后一个chunk并返回给用户。在free一个chunk的时候,检查其前或其后的chunk是否空闲,若是则合并,也即把它们从所属的链表中摘除并合并成一个新的chunk,新chunk会添加在unsorted bin链表的前端。 

    d、large bins 

      大小大于等于512字节的chunk被称为large chunk,而保存large chunks的bin被称为large bin,位于small bins后面。large bins中的每一个bin分别包含了一个给定范围内的chunk,其中的chunk按大小递减排序,大小相同则按照最近使用时间排列。 
      两个毗连的空闲chunk会被合并成一个空闲chunk。 
      分配时,遵循原则“smallest-first , best-fit”,从顶部遍历到底部以找到一个大小最接近用户需求的chunk。一旦找到,相应chunk就会分成两块User chunk(用户请求大小)返回给用户。 
    Remainder chunk 剩余部分添加到unsorted binfree时和small bin 类似。

    3、三种特殊的chunk

    并不是所有chunk都按照上面的方式来组织,有三种列外情况。top chunk,mmaped chunk 和last remainder chunk 

    a、top chunk 

      top chunk相当于分配区的顶部空闲内存(可能就是由brk调用控制的brk指针),当bins上都不能满足内存分配要求的时候,就会来top chunk上分配。 
      当top chunk大小比用户所请求大小还大的时候,top chunk会分为两个部分:User chunk(用户请求大小)和Remainder chunk(剩余大小)。其中Remainder chunk成为新的top chunk。 
      当top chunk大小小于用户所请求的大小时,top chunk就通过sbrk(main arena)或mmap(thread arena)系统调用来扩容。 

    b、mmaped chunk 

      当分配的内存非常大(大于分配阀值,默认128K)的时候,需要被mmap映射,则会放到mmaped chunk上,当释放mmaped chunk上的内存的时候会直接交还给操作系统。 (chunk中的M标志位置1)

    c、last remainder chunk 

      Last remainder chunk是另外一种特殊的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 chunk。

    六、sbrk与mmap

      在堆区中, 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 又会使用 fastbins 和 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 中分配的空间则可能会留在进程内存空间内,还可以再次引用(当然是很危险的)。 

    七、主分配区和非主分配区

    内存分配器中,为了解决多线程锁争夺问题,分为主分配区main_area(分配区的本质就是内存池,管理着chunk,一般用英文area表示)和非主分配区no_main_area。 (主分配区和非主分配区的区别)
     1. 主分配区和非主分配区形成一个环形链表进行管理。 
     2. 每一个分配区利用互斥锁使线程对于该分配区的访问互斥。 
     3. 每个进程只有一个主分配区,也可以允许有多个非主分配区。 
     4. ptmalloc根据系统对分配区的争用动态增加分配区的大小,分配区的数量一旦增加,则不会减少。 
     5. 主分配区可以使用brk和mmap来分配,而非主分配区只能使用mmap来映射内存块 
     6. 申请小内存时会产生很多内存碎片,ptmalloc在整理时也需要对分配区做加锁操作。

    当一个线程需要使用malloc分配内存的时候,会先查看该线程的私有变量中是否已经存在一个分配区。若是存在。会尝试对其进行加锁操作。若是加锁成功,就在使用该分配区分配内存,若是失败,就会遍历循环链表中获取一个未加锁的分配区若是整个链表中都没有未加锁的分配区,则malloc会开辟一个新的分配区,将其加入全局的循环链表并加锁,然后使用该分配区进行内存分配。当释放这块内存时,同样会先获取待释放内存块所在的分配区的锁。若是有其他线程正在使用该分配区,则必须等待其他线程释放该分配区互斥锁之后才能进行释放内存的操作。

    需要注意几个点:

    • 主分配区通过brk进行分配,非主分配区通过mmap进行分配
    • 从分配区虽然是mmap分配,但是和大于128K直接使用mmap分配没有任何联系。大于128K的内存使用mmap分配,使用完之后直接用ummap还给系统
    • 每个线程在malloc会先获取一个area,使用area内存池分配自己的内存,这里存在竞争问题
    • 为了避免竞争,我们可以使用线程局部存储,thread cache(tcmalloc中的tc正是此意),线程局部存储对area的改进原理如下:
    1. 如果需要在一个线程内部的各个函数调用都能访问、但其它线程不能访问的变量(被称为static memory local to a thread 线程局部静态变量),就需要新的机制来实现。这就是TLS。
    2. thread cache本质上是在static区为每一个thread开辟一个独有的空间,因为独有,不再有竞争
    3. 每次malloc时,先去线程局部存储空间中找area,用thread cache中的area分配存在thread area中的chunk。当不够时才去找堆区的area
    4. C++11中提供thread_local方便于线程局部存储
    • 可以看出主分配区其实是鸡肋,实际上tcmalloc和jemalloc都不再使用主分配区,直接使用非主分配区

    八、内存分配malloc流程

    1、获取分配区的锁,防止多线程冲突。(一个进程有一个malloc管理器,而一个进程中的多个线程共享这一个管理器,有竞争,加锁)

    2、计算出实际需要分配的内存的chunk实际大小。

    3、判断chunk的大小,如果小于max_fast(64B),则尝试去fast bins上取适合的chunk,如果有则分配结束。否则,下一步;

    4、判断chunk大小是否小于512B,如果是,则从small bins上去查找chunk,如果有合适的,则分配结束。否则下一步;

    5、ptmalloc首先会遍历fast bins(注:这里是第二次遍历fast bins了,虽然fast bins一般不会合并,但此时会)中的chunk,将相邻的chunk进行合并,并链接到unsorted bin中然后遍历 unsorted bins。(总体而言,第五部遍历unsorted bin,只是在遍历前先合并fast bin,遍历unsorted bin时一边遍历,一边放到small bin和large bin中)

    • 如果unsorted bins上只有一个chunk并且大于待分配的chunk,则进行切割,并且剩余的chunk继续扔回unsorted bins;
    • 如果unsorted bins上有大小和待分配chunk相等的,则返回,并从unsorted bins删除;
    • 如果unsorted bins中的某一chunk大小 属于small bins的范围,则放入small bins的头部;
    • 如果unsorted bins中的某一chunk大小 属于large bins的范围,则找到合适的位置放入。若未分配成功,转入下一步

    6、从large bins中查找找到合适的chunk之后,然后进行切割,一部分分配给用户,剩下的放入unsorted bin中。

    7、如果搜索fast bins和bins都没有找到合适的chunk,那么就需要操作top chunk来进行分配了 。当top chunk大小比用户所请求大小还大的时候,top chunk会分为两个部分:User chunk(用户请求大小)和Remainder chunk(剩余大小)。其中Remainder chunk成为新的top chunk。 当top chunk大小小于用户所请求的大小时,top chunk就通过sbrk(main arena)或mmap(thread arena)系统调用来扩容。

    8、到了这一步,说明 top chunk 也不能满足分配要求,所以,于是就有了两个选择: 如 果是主分配区,调用 sbrk(),增加 top chunk 大小;如果是非主分配区,调用 mmap 来分配一个新的 sub-heap,增加 top chunk 大小;或者使用 mmap()来直接分配。在 这里,需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值,如果是的话,则转下一步,调用 mmap 分配, 否则跳到第 10 步,增加 top chunk 的大小。

    9、使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。 然后将内存指针返回给用户。

    10、判断是否为第一次调用 malloc,若是主分配区,则需要进行一次初始化工作,分配 一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初 始化过了,主分配区则调用 sbrk()增加 heap 空间,分主分配区则在 top chunk 中切 割出一个 chunk,使之满足分配需求,并将内存指针返回给用户。

     

    九、内存回收流程

    1. 获取分配区的锁,保证线程安全。
    2. 如果free的是空指针,则返回,什么都不做。
    3. 判断当前chunk是否是mmap映射区域映射的内存,如果是,则直接munmap()释放这块内存。前面的已使用chunk的数据结构中,我们可以看到有M来标识是否是mmap映射的内存
    4. 判断chunk是否与top chunk相邻,如果相邻,则直接和top chunk合并(和top chunk相邻相当于和分配区中的空闲内存块相邻)。转到步骤8
    5. 如果chunk的大小大于max_fast(64b),则放入unsorted bin,并且检查是否有合并,有合并情况并且和top chunk相邻,则转到步骤8;没有合并情况则free。
    6. 如果chunk的大小小于 max_fast(64b),则直接放入fast bin,fast bin并没有改变chunk的状态。没有合并情况,则free;有合并情况,转到步骤7
    7. 在fast bin,如果当前chunk的下一个chunk也是空闲的,则将这两个chunk合并,放入unsorted bin上面。合并后的大小如果大于64B,会触发进行fast bins的合并操作,fast bins中的chunk将被遍历,并与相邻的空闲chunk进行合并,合并后的chunk会被放到unsorted bin中,fast bin会变为空。合并后的chunk和topchunk相邻,则会合并到topchunk中。转到步骤8
    8. 判断top chunk的大小是否大于mmap收缩阈值(默认为128KB),如果是的话,对于主分配区,则会试图归还top chunk中的一部分给操作系统free结束。

    十、使用注意事项

    为了避免Glibc内存暴增,需要注意: 
      1. 后分配的内存先释放,因为ptmalloc收缩内存是从top chunk开始,如果与top chunk相邻的chunk不能释放,top chunk以下的chunk都无法释放。 
      2. Ptmalloc不适合用于管理长生命周期的内存,特别是持续不定期分配和释放长生命周期的内存,这将导致ptmalloc内存暴增。 
      3. 不要关闭 ptmalloc 的 mmap 分配阈值动态调整机制,因为这种机制保证了短生命周期的 内存分配尽量从 ptmalloc 缓存的内存 chunk 中分配,更高效,浪费更少的内存。 
      4. 多线程分阶段执行的程序不适合用ptmalloc,这种程序的内存更适合用内存池管理 (因为同一个进程下的多线程要加锁后才能使用malloc分配器)
      5. 尽量减少程序的线程数量和避免频繁分配/释放内存。频繁分配,会导致锁的竞争,最终导致非主分配区增加,内存碎片增高,并且性能降低。 
      6. 防止内存泄露,ptmalloc对内存泄露是相当敏感的,根据它的内存收缩机制,如果与top chunk相邻的那个chunk没有回收,将导致top chunk一下很多的空闲内存都无法返回给操作系统。 
      7. 防止程序分配过多的内存,或是由于glibc内存暴增,导致系统内存耗尽,程序因为OOM被系统杀掉。预估程序可以使用的最大物理内存的大小,配置系统的/proc/sys/vm/overcommit_memory ,/proc/sys/vm/overcommit_ratio,以及使用ulimit -v限制程序能使用的虚拟内存的大小,防止程序因OOM被杀死掉。
     

    展开全文
  • 前言:本文剖析了glibc内存管理ptmalloc的底层实现原理,以及用到的各种数据结构的分析。源码在本文中暂未剖析,接下来会学习。如果你想了解ptmalloc的底层实现,欢迎阅读。 一、基础知识: X86平台Linux进程内存...


    前言:本文剖析了glibc内存管理ptmalloc的底层实现原理,以及用到的各种数据结构的分析。源码在本文中暂未剖析,接下来会学习。如果你想了解ptmalloc的底层实现,欢迎阅读。

    一、基础知识: X86平台Linux进程内存布局
    32位模式下进程内存经典布局
    这里写图片描述
    32位模式进程默认内存布局
    这里写图片描述
    从上图可以看到,栈至顶向下扩展,并且栈是有界的。堆至底向上扩展, mmap 映射区域至顶向下扩展, mmap 映射区域和堆相对扩展,直至耗尽虚拟地址空间中的剩余区域,这种结构便于 C 运行时库使用 mmap 映射区域和堆进行内存分配。上图的布局形式是在内核2.6.7 以后才引入的,这是 32 位模式下进程的默认内存布局形式

    二、操作系统内存分配的相关函数
    对 heap 的操作,操作系统提供了 brk()函数, C 运行时库提供了 sbrk()函数;对 mmap 映射区域的操作,操作系统提供了 mmap()和 munmap()函数。 sbrk(), brk() 或者 mmap() 都可以用来向我们的进程添加额外的虚拟内存。 Glibc 同样是使用这些函数向操作系统申请虚拟内存。

    这里要提到一个很重要的概念,内存的延迟分配, 只有在真正访问一个地址的时候才建立这个地址的物理映射,这是 Linux 内存管理的基本思想之一。 Linux 内核在用户申请内存的时候,只是给它分配了一个线性区(也就是虚拟内存),并没有分配实际物理内存;只有当用户使用这块内存的时候,内核才会分配具体的物理页面给用户,这时候才占用宝贵的物理内存。内核释放物理页面是通过释放线性区,找到其所对应的物理页面,将其全部释放的过程。


    1.heap操作的相关函数
    Heap 操作函数主要有两个, brk()为系统调用, sbrk()为 C 库函数。系统调用通常提供一种最小功能,而库函数通常提供比较复杂的功能。 Glibc 的 malloc 函数族( realloc, calloc 等)就调用 sbrk()函数将数据段的下界移动, sbrk()函数在内核的管理下将虚拟地址空间映射到内
    存,供 malloc()函数使用。

    内核数据结构 mm_struct 中的成员变量 start_code 和 end_code 是进程代码段的起始和终止地址, start_data 和 end_data 是进程数据段的起始和终止地址, start_stack 是进程堆栈段起始地址, start_brk 是进程动态内存分配起始地址(堆的起始地址),还有一个 brk(堆的当前最后地址),就是动态内存分配当前的终止地址。 C 语言的动态内存分配基本函数是malloc(),在 Linux 上的实现是通过内核的 brk 系统调用。 brk()是一个非常简单的系统调用,只是简单地改变 mm_struct 结构的成员变量 brk 的值。
    这两个函数的定义如下:
    int brk(void *addr);
    void *sbrk(intptr_t increment);
    需要说明的是,但 sbrk()的参数 increment 为 0 时, sbrk()返回的是进程的当前 brk 值,
    increment 为正数时扩展 brk 值,当 increment 为负值时收缩 brk 值


    2.Mmap映射区域操作相关函数
    mmap()函数将一个文件或者其它对象映射进内存。文件被映射到多个页上,如果文件的大小不是所有页的大小之和,最后一个页不被使用的空间将会清零。 munmap 执行相反的操作,删除特定地址区域的对象映射。 函数的定义如下:

    void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
    int munmap(void *addr, size_t length);
    在这里不准备对这两个函数做详细介绍,只是对 ptmalloc 中用到的功能做一下介绍,其他的用法请参看相关资料。
    参数:
    start:映射区的开始地址。

    length:映射区的长度。

    prot:期望的内存保护标志,不能与文件的打开模式冲突。是以下的某个值,可以通过or 运算合理地组合在一起。 Ptmalloc 中主要使用了如下的几个标志:

    PROT_EXEC //页内容可以被执行, ptmalloc 中没有使用

    PROT_READ //页内容可以被读取, ptmalloc 直接用 mmap 分配内存并立即返回给用户时设置该标志

    PROT_WRITE //页可以被写入, ptmalloc 直接用 mmap 分配内存并立即返回给用户时设置该标志

    PROT_NONE //页不可访问, ptmalloc 用 mmap 向系统“批发”一块内存进行管理时设置该标志

    flags:指定映射对象的类型,映射选项和映射页是否可以共享。它的值可以是一个或者多个以下位的组合体

    MAP_FIXED //使用指定的映射起始地址,如果由 start 和 len 参数指定的内存区重叠于现存的映射空间,重叠部分将会被丢弃。如果指定的起始地址不可用,操作将会失败。并且起始地址必须落在页的边界上。
    Ptmalloc 在回收从系统中“批发”的内存时设置该标志。

    MAP_PRIVATE //建立一个写入时拷贝的私有映射。内存区域的写入不会影响到原文件。这个标志和以上标志是互斥的,只能使用其中一个。Ptmalloc每次调用 mmap都设置该标志。

    MAP_NORESERVE //不要为这个映射保留交换空间。当交换空间被保留,对映射区修改的可能会得到保证。当交换空间不被保留,同时内存不足,对映射区的修改会引起段违例信号。 Ptmalloc 向系统“批发”内存块时设置该标志。

    MAP_ANONYMOUS //匿名映射,映射区不与任何文件关联。 Ptmalloc 每次调用 mmap都设置该标志。

    fd:有效的文件描述词。如果 MAP_ANONYMOUS 被设定,为了兼容问题,其值应为-1。

    offset:被映射对象内容的起点。

    三、ptmalloc
    1.简述:ptmalloc 实现了 malloc(), free()以及一组其它的函数. 以提供动态内存管理的支持。 分配器处在用户程序和内核之间,它响应用户的分配请求,向操作系统申请内存,然后将其返回给用户程序,为了保持高效的分配, 分配器一般都会预先分配一块大于用户请求的内存,并通过某种算法管理这块内存。来满足用户的内存分配要求,用户释放掉的内存也并不是立即就返回给操作系统,相反, 分配器会管理这些被释放掉的空闲空间,以应对用户以后的内存分配要求。也就是说, 分配器不但要管理已分配的内存块,还需要管理空闲的内存块,当响应用户分配要求时, 分配器会首先在空闲空间中寻找一块合适的内存给用户,在空闲空间中找不到的情况下才分配一块新的内存。 为实现一个高效的分配器,需要考虑很多的因素。比如, 分配器本身管理内存块所占用的内存空间必须很小,分配算法必须要足够的快。
    2.内存管理的数据结构
    注:要想透彻理解ptmalloc管理内存的原理,接下来的这些数据结构非常重要,只有理解并掌握这些数据结构,才能对整体的流程有较深的认识。
    ①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()函数向操作系统申请虚拟内存。
    接下来用一张图表示分配区的相关知识:
    这里写图片描述
    ②chunk的组织
    不管内存是在哪里被分配的,用什么方法分配,用户请求分配的空间在 ptmalloc 中都使用一个 chunk 来表示。用户调用 free()函数释放掉的内存也并不是立即就归还给操作系统,相反,它们也会被表示为一个 chunk,ptmalloc 使用特定的数据结构来管理这些空闲的 chunk。
    正在使用中的chunk如下图:
    这里写图片描述
    在图中, chunk 指针指向一个 chunk 的开始,一个 chunk 中包含了用户请求的内存区域和相关的控制信息。图中的 mem 指针才是真正返回给用户的内存指针。 chunk 的第二个域的最低一位为 P,它表示前一个块是否在使用中, P 为 0 则表示前一个 chunk 为空闲,这时chunk 的第一个域 prev_size 才有效, prev_size 表示前一个 chunk 的 size,程序可以使用这个值来找到前一个 chunk 的开始地址。当 P 为 1 时,表示前一个 chunk 正在使用中, prev_size16无效,程序也就不可以得到前一个 chunk的大小。不能对前一个 chunk进行任何操作。ptmalloc分配的第一个块总是将 P 设为 1,以防止程序引用到不存在的区域。
    Chunk 的第二个域的倒数第二个位为 M,他表示当前 chunk 是从哪个内存区域获得的虚拟内存。 M 为 1 表示该 chunk 是从 mmap 映射区域分配的,否则是从 heap 区域分配的。
    Chunk 的第二个域倒数第三个位为 A, 表示该 chunk 属于主分配区或者非主分配区,如果属于非主分配区,将该位置为 1,否则置为 0。
    空闲 chunk 在内存中的结构如图所示:
    这里写图片描述
    当 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 的 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 实际需要分配的内存大小, 在后面的介绍中。 如果不是特别指明的地方, 指的都是这个经过转换的实际需要分配的内存大小, 而不是用户请求的内存分配大小。

    空闲chunk容器:
    1.Bins
    用户 free 掉的内存并不是都会马上归还给系统, ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk,当用户进行下一次分配请求时, ptmalloc 会首先试图在空闲的chunk 中挑选一块给用户,这样就避免了频繁的系统调用,降低了内存分配的开销。 ptmalloc将相似大小的 chunk 用双向链表链接起来,这样的一个链表被称为一个 bin。 Ptmalloc 一共维护了 128 个 bin,并使用一个数组来存储这些 bin( 如下图所示)。
    这里写图片描述
    数组中的第一个为 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 的容器内。
    2.Fast bins:
    一般的情况是, 程序在运行时会经常需要申请和释放一些较小的内存空间。 当分配器合并了相邻的几个小的 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,18将相邻的空闲 chunk 进行合并, 并将合并后的 chunk 加入 unsorted bin 中,然后再将 usorted
    bin 里的 chunk 加入 bins 中.
    3.unsorted bin
    unsorted bin 的队列使用 bins 数组的第一个, 如果被用户释放的 chunk 大于 max_fast,或者 fast bins 中的空闲 chunk 合并后, 这些 chunk 首先会被放到 unsorted bin 队列中, 在进
    行 malloc 操作的时候,如果在 fast bins 中没有找到合适的 chunk,则 ptmalloc 会先在 unsortedbin 中查找合适的空闲 chunk, 然后才查找 bins。 如果 unsorted bin 不能满足分配要求。 malloc便会将 unsorted bin 中的 chunk 加入 bins 中。 然后再从 bins 中继续进行查找和分配过程。 从这个过程可以看出来, unsorted bin 可以看做是 bins 的一个缓冲区, 增加它只是为了加快分配的速度。
    4. Top chunk
    并不是所有的 chunk 都按照上面的方式来组织,实际上,有三种例外情况。 Top chunk,mmaped chunk 和 last remainder,下面会分别介绍这三类特殊的 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 的大小。
    5. mmaped chunk
    当需要分配的 chunk 足够大, 而且 fast bins 和 bins 都不能满足要求, 甚至 top chunk 本身也不能满足分配需求时, ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。 这样分配的 chunk 在被 free 时将直接解除映射, 于是就将内存归还给了操作系统, 再次对这样的内存区的引用将导致 segmentation fault 错误。 这样的 chunk 也不会包含在任何bin 中。
    6. 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。


    总结:
    1.ptmalloc 的响应用户内存分配要求的具体步骤为:
    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 的空间大小将其放入 smallbins 或是 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 的大小, 如果是, 则从 topchunk 中分出一块来。 否则转到下一步。

    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, 若是主分配区, 则需要进行一次初始化工作, 分配21一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。 若已经初始化过了, 主分配区则调用 sbrk()增加 heap 空间, 分主分配区则在 top chunk 中切割出一个 chunk, 使之满足分配需求, 并将内存指针返回给用户。
    这里写图片描述
    2.内存回收概述
    free() 函数接受一个指向分配区域的指针作为参数,释放该指针所指向的 chunk。而具体的释放方法则看该 chunk 所处的位置和该 chunk 的大小。 free()函数的工作步骤如下:
    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 也是空闲的, 则合并, 并将22合并后的 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 收缩阈值,才有可能收缩堆。
    这里写图片描述

    展开全文
  • ptmalloc实现细节

    2019-05-12 19:52:04
    如果对ptmalloc的基本设计还不熟悉,请先看:https://blog.csdn.net/songchuwang1868/article/details/89951543 一、bin数组 bin数组大体分成三个部分: 1、unsored bin数组 暂存一些没有排序的数据 unsored ...
  • 前几年阅读过华庭的《glibc内存管理ptmalloc源代码分析》文章,并做过一篇笔记 今年打算重点阅读一下glibc里面,malloc部分的具体实现机制。 ptmalloc简介 Linux早期的版本,是由Doug Lea实现的,但是早期的版本...
  • 浅析malloc的底层实现原理(ptmalloc

    千次阅读 2019-05-30 19:48:54
    内存布局 、brk(sbrk)与mmap函数 、内存管理的一般方法、ptmalloc简介 、内存管理数据结构概述 、内存分配、回收概述
  • malloc的底层实现ptmalloc

    万次阅读 多人点赞 2018-04-15 16:54:44
    结合网上的一些文章和个人的理解,对ptmalloc实现原理做一些总结。 内存布局  介绍ptmalloc之前,我们先了解一下内存布局,以x86的32位系统为例:    从上图可以看到,栈至顶向下扩展,堆至底向上扩展, ...
  • 1、获取分配区的锁,保证线程安全 2、如果free的是空指针,则返回,什么都不做 3、判断当前chunk是否是mmap映射区域映射的内存,如果是,则直接munmap()释放这块内存。...
  • ptmalloc实现

    2018-05-10 15:08:05
    之后,glibc 中集成了ptmalloc2。 可以下载glibc源码查看ptmallochttp://ftp.gnu.org/gnu/glibc/ 查看glibc版本millionsky@ubuntu-16:~/tmp$ ldd --versionldd (Ubuntu GLIBC 2.23-0ubuntu9) 2.23 这里主要参考...
  • ptmalloc

    2019-05-10 15:03:19
    本文主要介绍了glibc malloc的实现,及其替代品 一个优秀的通用内存分配器应具有以下特性: 额外的空间损耗尽量少 分配速度尽可能快 尽量避免内存碎片 缓存本地化友好 通用性,兼容性,可移植性,...
  • ptmalloc 内存管理概述

    2019-06-01 22:12:36
    文章目录ptmalloc引入ptmalloc简述内存管理的设计假设内存管理数据结构概述主分配区(main_arena) 与 非主分配区(non_main_arena)chunk的组织chunk 格式空闲 chunk 容器binsfast binsunsorted bintop chunkmmaped...
  • ptmalloc2

    2018-02-22 18:58:00
    ptmalloc实现了malloc(),free()以及一组其他函数,以提供动态内存管理,同时支持多线程。分配器处于用户空间和内核空间之间,响应用户的分配请求,向操作系统申请内存。总体思想是先“批发”一块大内存,而后“零售...
  • ptmalloc堆概述

    2018-05-10 14:42:04
    ptmalloc堆概述1 概述堆的概念在程序运行过程中,堆可以提供动态分配的内存,允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域,它由低地址向高地址方向增长。 堆管理器我们一般称...
  • glibc内存管理之ptmalloc

    2018-05-03 20:14:13
    本文参考了华庭的《glibc内存管理ptmalloc源代码分析》和优秀博客。一、基础知识 下图为Linux内核32位模式下进程经典布局图:上面个段的含义如下:text:存放程序代码的,编译时确定,只读;data:存放程序运行时就...
  • 3.概述 3.1内存管理一般性描述 当不知道程序的每个部分将需要多少内存时,系统内存空间有限,而内存需求又是变化的,...C 风格的内存管理程序主要实现 malloc()和 free()函数。内存管理程序主要通过调用 brk()或者...
  • ptmalloc 实现了 malloc(),free()以及一组其它的函数. 以提供动态内存管理的支持。 malloc实现原理: 因为brk、sbrk、mmap都属于系统调用,若每次申请内存,都调用这三个,那么每次都会产生系统调用,影响...
  • glibc除了封装linux操作系统所提供的系统服务外,它本身也提供了许多其它一些必要功能服务的实现。由于 glibc 囊括了几乎所有的 UNIX 通行的标准,可以想见其内容包罗万象。而就像其他的 UNIX 系统一样,其内含的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,375
精华内容 550
关键字:

ptmalloc实现