从操作系统内存管理来说，malloc申请一块内存的背后原理是什么？
linux操作系统的内存管理是通过分页机制来实现的，一个页项4KB，那在C语言程序中，malloc申请一块内存区域是怎样通过分页的机制来管理的呢，操作系统是怎样来进行分配的？就好比我申请5KB空间，操作系统去哪里找这5KB的空闲空间，又怎样通过分页的机制进行管理我看网上有人说操作系统将空闲的内存区域通过链表连接起来，使用的内存也用链表连接起来，然后从空闲链表中分配空间就可以了。但是现在的linux系统的内存管理不再是这种动态分区管理，而是采用了分页机制进行管理。
通过之前四篇关于内存管理的文章介绍，我们已经对Linux系统中的内存管理有了一个大致的了解，但是是不是有些读者感觉还是比较模糊或者感觉对自己工作或者学习并没有太大的帮助，那么我们今天就从实际出发，结合之前介绍的内存管理的知识，介绍一下我们比较常见的C语言的API函数：malloc与free
Linux系统中进程的内存分布
首先我们先来简单回忆一下《浅析进程与线程》这篇文章中对进程的描述
其中mm_struct结构就是进程中的虚拟内存管理的结构体，我们接着看下mm_struct的结构：
mm_struct在内存中的结构
如果对这部分还不是特别清楚的，建议读一下笔者的《浅析进程与线程》。
接下来我们简单介绍一下这些内存区域的含义：代码段，包括二进制可执行代码；数据段，包括已初始化的静态常量和全局变量；BSS 段，包括未初始化的静态变量和全局变量；堆段，包括动态分配的内存，从低地址开始向上增长；文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关 (opens new window)）；栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 。当然系统也提供了参数，以便我们自定义大小；
在这 6 个内存段中，堆和文件映射段的内存是动态分配的。比如说，使用 C 标准库的 或者 ，就可以分别在堆和文件映射段动态分配内存。一般来说，除了对于文件映射段之外，其余的内存空间大小已经在编译期间确定了，一般几乎不太会改变。除非调用系统函数调整栈内存的大小。
最原始的malloc与free是如何实现的？
malloc的实现方式
大家都知道，malloc只是个C语言的函数，并不是系统调用，那么在系统中，实现内存分配的方式有哪些呢？方式一：通过 brk（sbrk）系统调用从堆分配内存方式二：通过 mmap() 系统调用在文件映射区域分配内存；
方式一实现的方式很简单，就是通过 brk() 函数将「堆顶」指针向高地址移动，获得新的内存空间。
函数原型如下：
基本的实现方式如下图：
brk方式分配内存
方式二通过 mmap() 系统调用中「私有匿名映射」的方式，在文件映射区分配一块内存，
mmap的函数原型如下：
Mmap的第一种用法是映射此盘文件到内存中，一般我们在编程中使用的方式都是这种方式；
第二种用法是匿名映射，不映射磁盘文件，而向映射区申请一块内存。
Malloc使用的是mmap的第二种用法（匿名映射）。
malloc调用mmap的具体实现如下图：
mmap方式分配内存
注：在Linux系统中，默认以128K为分配的阈值，申请超过128K的内存一般是使用mmap方式，低于128K的内存分配使用brk方式来实现
那么大家可以想一下，为啥会存在这两种分配方式呢？
brk方式的内存分配
我们知道通过 brk 从堆空间分配的内存，由于brk方式是通过移动堆顶的指针方式来操作的，那么我们那考虑这样一个场景。
如果我们连续申请了 10k，20k，30k 这三片内存，如果 10k 和 20k 这两片释放了，变为了空闲内存空间，如果下次申请的内存小于 30k，那么就可以重用这个空闲内存空间。
brk方式分配
但是如果下次申请的内存大于 30k，没有可用的空闲内存空间，必须向 OS 申请，实际使用内存继续增大。
因此，随着系统频繁地 malloc 和 free ，尤其对于小块内存，堆内将产生越来越多不可用的碎片（外部碎片），导致“内存泄露”。而这种“泄露”现象使用 valgrind （其他的内存检测工具）是无法检测出来的。
所以使用brk方式，对于内存空洞问题并不能很好的解决。那么我们来看下mmap的方式是如何解决呢？
mmap方式的内存分配
为了避免brk方式产生碎片的问题，mmap 分配的内存每次释放的时候，都会归还给操作系统，但是mmap本身的实现也是存在问题的。
大家都清楚，mmap是系统调用，执行系统调用是要进入内核态的，然后在回到用户态，运行态的切换会耗费不少时间。
所以，申请内存的操作应该避免频繁的系统调用，如果都用 mmap 来分配内存，等于每次都要执行系统调用。
还有一个更为严重的问题就是，由于 mmap 分配的内存每次释放的时候，都会归还给操作系统，于是每次 mmap 分配的虚拟地址都是缺页状态的，然后在第一次访问该虚拟地址的时候，就会触发缺页中断，这个问题才是最严重的，缺页中断的性能消耗是十分严重的。
所以，频繁通过 mmap 分配的内存话，不仅每次都会发生运行态的切换（其实brk方式也会进行运行态的切换），还会发生缺页中断（在第一次访问虚拟地址后），这样会导致 CPU 消耗较大。
那么我们来进行总结一下：
由于mmap每次释放内存的时候，都会归还给操作系统，从而避免内存碎片的问题，所以针对大内存，使用mmap的方式进行分配，主要是为了解决内存碎片的问题。
针对brk方式，由于每次内存释放不一定归还给操作系统，所以会有内存碎片问题，如果使用brk方式来分配大内存，会造成比较严重的“内存泄漏”
所以在Linux操作系统中，采用两种方式并存的形式来进行内存分配管理，从而达到性能与内存碎片管理的相对平衡。
free的实现方式
free的函数原型如下：
free() 函数只传入一个内存地址，为什么能知道要释放多大的内存？
malloc 返回给用户态的内存起始地址比进程的堆空间起始地址多了 16 字节，大家可以看一下malloc给到用户的内存大致结构图：
malloc内存分配
这样当执行 free() 函数时，free 会对传入进来的内存地址向左偏移 16 字节，然后从这个 16 字节的分析出当前的内存块的大小，自然就知道要释放多大的内存了
针对不同的内存分配方式，free的实现是不一样的
针对brk方式申请的内存，如果释放的内存已经在堆顶，则可以直接操作brk指针的下移，从而达到内存释放的效果，如果不是在堆顶，而是在堆的中间位置，由于堆内存管理的限制，所以这部分内存是会被缓存起来，不会进行释放的。
针对mmap方式申请的内存，则直接调用unmmap方式进行内存释放，这时的释放会把内存归还给操作系统，内存得到真正的释放。
本小节给大家简单介绍了最原始的malloc与free的实现方式，通过介绍大家可以很清楚的看到，无论是使用brk方式还是使用mmap方式进行内存分配，对操作系统来说，都不太友好，因为首先他们都是系统调用，对性能影响比较大，另外就是外部内存碎片问题没办法解决，因为堆是从低地址到高地址，如果高地址的内存没有被释放，低地址的内存就不能被回收。所以针对这些问题，真正的Linux系统中，并不是使用最原始的方式来给malloc分配内存，下面我们来简单介绍一下实际Linux系统中是怎么进行内存分配及管理的。
基于PTmalloc的malloc实现
ptmalloc的基本组织单元--chunk
这里我们简单介绍一下，为啥我们是使用PTmalloc为蓝本进行介绍的，主要原因就是ptmalloc是glibc的标准库，相对于其他的jemalloc与tcmalloc库来说，这个版本的malloc是更加“官方”的，虽然他存在很多的性能问题，但是整体的设计还是值得我们学习的。
实际的Linux操作系统中，使用的ptmalloc本质就是一个内存池，Ptmalloc 采用边界标记法将内存划分成很多块，从而对内存的分配与回收进行管理。为了内存分配函数malloc的高效性，ptmalloc会预先向操作系统申请一块内存供用户使用，当我们申请和释放内存的时候，ptmalloc会将这些内存管理起来，并通过一些策略来判断是否将其回收给操作系统。这样做的最大好处就是，使用户申请和释放内存的时候更加高效，避免产生过多的内存碎片。
在ptmalloc中，最基本的逻辑单元室chunk，下面我们先简单认识一下这个结构，从而可以更加清楚的认识ptmalloc是如何对malloc的实现进行管理。
chunk的定义如下：
通过代码中的注释可以看出来，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，用于提升遍历空闲chunk的速度。与fd,bk变量类似，如果是非空闲状态，这两个字段也是不存在的。
chunk的结构图
上图与chunk的结构图是一一对应的，这里需要简单介绍一下size中的这个变量，这个变量中，抽出了几位空间用于存储一些状态信息。A=0 为主分配区分配；A=1 为非主分配区分配M=1 为mmap映射区域分配；M=0为heap区域分配p=0时，表示前一个chunk为空闲，prev_size才有效p=1时，表示前一个chunk正在使用，prev_size无效 p主要用于内存块的合并操作；ptmalloc 分配的第一个块总是将p设为1, 以防止程序引用到不存在的区域
chunk的组织形式--bins
malloc将相似大小的chunk用双向链表链接起来，这样一个链表被称为一个bin。ptmalloc一共维护了136bin。每个bins都维护了大小相近的双向链表的chunk。
基于chunk的大小，有下列几种可用bins：
1、Fast bin:是bins的高速缓冲区,大约有10个定长队列。
2、Unsorted bin：是队列使用 bins 数组的第一个，是bins的一个缓冲区，用于加快分配的速度。
3、Small bin：大小小于512字节的chunk被称为small chunk，而保存small chunks的bin被称为small bin。
4、Large bin：大小大于等于512字节的chunk被称为large chunk，而保存large chunks的bin被称为large bin，位于small bins后面。
这四种bins又可以根据其实现，分成两类，第一个就是fast bins，fast bins是一个单独的数据结构进行组织的，主要作用就是用来做快速缓存，当用户调用free的时候，如果释放的内存是在fast bins可以管理的范围之内，则直接将这部分内存交给fast bins进行管理。
下面我们通过一副图来简单描述一下这四类bins
全部bins的结构
我们对ptmalloc的基本管理动作有了初步的了解，相信大部分人其实还是比较懵的，因为这都是概念上的东西，如何把bins跟malloc和free结合在一起，根本没有提及，所以接下来我们会针对这四种bins对malloc及free的实现进行详细的分析。
不同bins的malloc与free
fast bins
首先需要明确的是，fast bins与其他三种bins是不一样的，fast bins的组织形式是单链表结构，其余的三中bins都是双链表进行组织的。
fast bins是bins的高速缓冲区，大约有10个定长队列。每个fast bin都记录着一条free chunk的单链表（称为binlist ，采用单链表是出于fast bin中链表中部的chunk不会被摘除的特点），增删chunk都发生在链表的前端。 fast bins 记录着大小以8字节递增的bin链表，所以他可以管理8字节到80字节的内存申请与释放。
当用户释放一块不大于max_fast（默认值64B）的chunk的时候，会默认会被放到fast bins上。当需要给用户分配的 chunk 小于或等于 max_fast 时,malloc 首先会到fast bins上寻找是否有合适的chunk，
除非特定情况，两个毗连的空闲chunk并不会被合并成一个空闲chunk。不合并可能会导致碎片化问题，但是却可以大大加速释放的过程！
分配时，binlist中被检索的第一个个chunk将被摘除并返回给用户。free掉的chunk将被添加在索引到的binlist的前端。
unsorted bins
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。
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链表的前端。
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 类似。
为什么需要fast bins与unsorted bins ?
笔者认为，存在fast bins的最主要原因就是缓存，因为fast bins 管理着很多小chunk的内存，当进行小内存的申请时，可以直接在fast bins上，并且fast bins有个特点就是不会进行chunk的合并，这样就可以保证我们之前申请的小内存，都可以在fastbins 中缓存下来。
unsorted bins存在的最主要原因，就是避免large chunk 或者small chunk上的chunk分裂，当存在之前申请过的相应大小的内存时，就可以直接在unsorted bins中找到，不需要分裂的过程。
另外笔者还认为，之所以存在这两个bins 的最主要原因就是物理内存的缓存，因为能够在这两个bins中的内存，都是之前分配过的内存，并且有可能都发生过缺页中断（也就是这批虚拟内存已经映射到物理内存中了），后续再次使用，就不需要进行缺页中断来重新映射物理内存了，大家知道，缺页中断对系统的开销还是很大的。
其实我们刚才分析的都是bins中有足够的内存，或者有相应大小的内存，如果bins中没有比用户申请内存更大的内存时，将发生什么呢？
例外情况的兜底
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。
基于ptmalloc的malloc过程
malloc分配过程
简而言之： 分配区(arena)并加锁–> fast bin –> unsorted bin –> small bin –> large bin –> top chunk –> 扩展堆
内存回收的过程分析
free过程
总结
本文从进程中的虚拟内存结构开始讲起，介绍了在进程中虚拟内存的管理结构，在对虚拟内存有了大致了解之后，开始介绍最朴素的malloc与free的方式，简单介绍了brk与mmap的内存分配方式，及两者的区别，然后根据这两实现方式所面临的问题，又进一步提出了Linux系统中的ptmalloc内存管理方式，介绍了fast bins、unsorted bin、small bins、large bins四种管理方式，并且介绍了整个malloc与free的过程。
希望通过本文的介绍，能对大家了解malloc与free有一定的帮助。
