泽民博客 ☰ Menu

page

用户程序一般只面对虚拟内存，知道执行的时候才通过MMU根据内核中的页表将page和page frame进行对应。



首先，所有操作系统都是基于虚拟地址来进行内存管理，虚拟地址的空间就是cpu寻址空间来限定。例如32bit的cpu，寻址空间就是232Gb。不管机器上安装了多少实际的内存条，所有在上面运行的程序（包括内核）都认为自己有4Gb的内存可以使用。



内存布局就是如何安排这4Gb的内存。



内核空间、用户空间（堆、栈、代码域、静态数据域和mmap区）

内核空间和用户空间都需要对虚拟内存的分配进行管理，内核通过(kmalloc（小内存，但是物理和虚拟地址都连续）和vmalloc（大内存，但是不保证连续）)来使用内存，管理采用slab分配器和buddy机制。为什么需要管理机制，因为，无论虚拟内存还是物理内存，其最小分配单位是页（每页4k）。



用户空间通过（malloc(brk(堆上分配，小于128k),mmap（映射区分配，大于128k）)），管理采用ptmalloc，tcmalloc，jemalloc来进行。



用户空间有一些自己写的cache（情况简单时）和专用内存池（情况复杂时），这种机制通常基于通用内存管理malloc来运行，策略经常是：
1.当频繁（malloc/free）发生时，就可以采用长期占用（启动时申请后，一直不释放）一块大的内存作为cache使用的策略。减少大内存的申请操作（大内存都是在映射区进行，每次malloc/free会产生真正申请和释放内存（虚拟内存和物理内存），需要修改进程的页表，会产生mmap系统调用和缺页中断，这个太糟糕了）
2.专用内存池：基于连接的内存管理，就是类似于nginx这种服务器，基于connection的策略是：一次连接会有各种各样变长的字符串和小内存，连接建立时，create memory pool，创建专用的内存池进行（内存管理），连接进行时采用memory pool来对连接所需的数据结构进行管理，然后一次性释放（连接关闭时,delete memory pool）



Linux的虚拟内存管理有几个关键概念：


Linux 虚拟地址空间如何分布？malloc和free是如何分配和释放内存？如何查看堆内内存的碎片情况？既然堆内内存brk和sbrk不能直接释放，为什么不全部使用 mmap 来分配，munmap直接释放呢 ？



Linux 的虚拟内存管理有几个关键概念：
1、每个进程都有独立的虚拟地址空间，进程访问的虚拟地址并不是真正的物理地址；
2、虚拟地址可通过每个进程上的页表(在每个进程的内核虚拟地址空间)与物理地址进行映射，获得真正物理地址；
3、如果虚拟地址对应物理地址不在物理内存中，则产生缺页中断，真正分配物理地址，同时更新进程的页表；如果此时物理内存已耗尽，则根据内存替换算法淘汰部分页面至物理磁盘中。



TCMalloc的全称为Thread-Caching Malloc，是谷歌开发的开源工具google-perftools中的一个成员。与标准的glibc库的Malloc相比，TCMalloc库在内存分配效率和速度上要高很多，这在很大程度上提高了服务器在高并发情况下的性能，从而降低了系统的负载。



redis并没有自己实现内存池，没有在标准的系统内存分配器上再加上自己的东西。所以系统内存分配器的性能及碎片率会对redis造成一些性能上的影响



一、概念



物理地址(physical address)
用于内存芯片级的单元寻址，与处理器和CPU连接的地址总线相对应。
——这个概念应该是这几个概念中最好理解的一个，但是值得一提的是，虽然可以直接把物理地址理解成插在机器上那根内存本身，把内存看成一个从0字节一直到最大空量逐字节的编号的大数组，然后把这个数组叫做物理地址，但是事实上，这只是一个硬件提供给软件的抽像，内存的寻址方式并不是这样。所以，说它是“与地址总线相对应”，是更贴切一些，不过抛开对物理内存寻址方式的考虑，直接把物理地址与物理的内存一一对应，也是可以接受的。也许错误的理解更利于形而上的抽像。



虚拟内存(virtual memory)
这是对整个内存（不要与机器上插那条对上号）的抽像描述。它是相对于物理内存来讲的，可以直接理解成“不直实的”，“假的”内存，例如，一个0x08000000内存地址，它并不对就物理地址上那个大数组中0x08000000 - 1那个地址元素；
之所以是这样，是因为现代操作系统都提供了一种内存管理的抽像，即虚拟内存（virtual memory）。进程使用虚拟内存中的地址，由操作系统协助相关硬件，把它“转换”成真正的物理地址。这个“转换”，是所有问题讨论的关键。
有了这样的抽像，一个程序，就可以使用比真实物理地址大得多的地址空间。（拆东墙，补西墙，银行也是这样子做的），甚至多个进程可以使用相同的地址。不奇怪，因为转换后的物理地址并非相同的。
——可以把连接后的程序反编译看一下，发现连接器已经为程序分配了一个地址，例如，要调用某个函数A，代码不是call A，而是call 0x0811111111 ，也就是说，函数A的地址已经被定下来了。没有这样的“转换”，没有虚拟地址的概念，这样做是根本行不通的。
打住了，这个问题再说下去，就收不住了。



逻辑地址(logical address)
Intel为了兼容，将远古时代的段式内存管理方式保留了下来。逻辑地址指的是机器语言指令中，用来指定一个操作数或者是一条指令的地址。以上例，我们说的连接器为A分配的0x08111111这个地址就是逻辑地址。
——不过不好意思，这样说，好像又违背了Intel中段式管理中，对逻辑地址要求，“一个逻辑地址，是由一个段标识符加上一个指定段内相对地址的偏移量，表示为 [段标识符：段内偏移量]，也就是说，上例中那个0x08111111，应该表示为[A的代码段标识符: 0x08111111]，这样，才完整一些”



线性地址(linear address)或也叫虚拟地址(virtual address)
跟逻辑地址类似，它也是一个不真实的地址，如果逻辑地址是对应的硬件平台段式管理转换前地址的话，那么线性地址则对应了硬件页式内存的转换前地址。




CPU将一个虚拟内存空间中的地址转换为物理地址，需要进行两步：首先将给定一个逻辑地址（其实是段内偏移量，这个一定要理解！！！），CPU要利用其段式内存管理单元，先将为个逻辑地址转换成一个线程地址，再利用其页式内存管理单元，转换为最终物理地址。



这样做两次转换，的确是非常麻烦而且没有必要的，因为直接可以把线性地址抽像给进程。之所以这样冗余，Intel完全是为了兼容而已。



2、CPU段式内存管理，逻辑地址如何转换为线性地址
一个逻辑地址由两部份组成，段标识符: 段内偏移量。段标识符是由一个16位长的字段组成，称为段选择符。其中前13位是一个索引号。后面3位包含一些硬件细节，如图：



Snap1.jpg



最后两位涉及权限检查，本贴中不包含。



索引号，或者直接理解成数组下标——那它总要对应一个数组吧，它又是什么东东的索引呢？这个东东就是“段描述符(segment descriptor)”，呵呵，段描述符具体地址描述了一个段（对于“段”这个字眼的理解，我是把它想像成，拿了一把刀，把虚拟内存，砍成若干的截——段）。这样，很多个段描述符，就组了一个数组，叫“段描述符表”，这样，可以通过段标识符的前13位，直接在段描述符表中找到一个具体的段描述符，这个描述符就描述了一个段，我刚才对段的抽像不太准确，因为看看描述符里面究竟有什么东东——也就是它究竟是如何描述的，就理解段究竟有什么东东了，每一个段描述符由8个字节组成，如下图：



Snap2.jpg



这些东东很复杂，虽然可以利用一个数据结构来定义它，不过，我这里只关心一样，就是Base字段，它描述了一个段的开始位置的线性地址。



Intel设计的本意是，一些全局的段描述符，就放在“全局段描述符表(GDT)”中，一些局部的，例如每个进程自己的，就放在所谓的“局部段描述符表(LDT)”中。那究竟什么时候该用GDT，什么时候该用LDT呢？这是由段选择符中的T1字段表示的，=0，表示用GDT，=1表示用LDT。



GDT在内存中的地址和大小存放在CPU的gdtr控制寄存器中，而LDT则在ldtr寄存器中。



好多概念，像绕口令一样。这张图看起来要直观些：



Snap3.jpg



首先，给定一个完整的逻辑地址[段选择符：段内偏移地址]，
1、看段选择符的T1=0还是1，知道当前要转换是GDT中的段，还是LDT中的段，再根据相应寄存器，得到其地址和大小。我们就有了一个数组了。
2、拿出段选择符中前13位，可以在这个数组中，查找到对应的段描述符，这样，它了Base，即基地址就知道了。
3、把Base + offset，就是要转换的线性地址了。



还是挺简单的，对于软件来讲，原则上就需要把硬件转换所需的信息准备好，就可以让硬件来完成这个转换了。OK，来看看Linux怎么做的。



3、Linux的段式管理
Intel要求两次转换，这样虽说是兼容了，但是却是很冗余，呵呵，没办法，硬件要求这样做了，软件就只能照办，怎么着也得形式主义一样。
另一方面，其它某些硬件平台，没有二次转换的概念，Linux也需要提供一个高层抽像，来提供一个统一的界面。所以，Linux的段式管理，事实上只是“哄骗”了一下硬件而已。



按照Intel的本意，全局的用GDT，每个进程自己的用LDT——不过Linux则对所有的进程都使用了相同的段来对指令和数据寻址。即用户数据段，用户代码段，对应的，内核中的是内核数据段和内核代码段。这样做没有什么奇怪的，本来就是走形式嘛，像我们写年终总结一样。
include/asm-i386/segment.h



#define GDT_ENTRY_DEFAULT_USER_CS 14
#define __USER_CS (GDT_ENTRY_DEFAULT_USER_CS * 8 + 3)



#define GDT_ENTRY_DEFAULT_USER_DS 15
#define __USER_DS (GDT_ENTRY_DEFAULT_USER_DS * 8 + 3)



#define GDT_ENTRY_KERNEL_BASE 12



#define GDT_ENTRY_KERNEL_CS (GDT_ENTRY_KERNEL_BASE + 0)
#define __KERNEL_CS (GDT_ENTRY_KERNEL_CS * 8)



#define GDT_ENTRY_KERNEL_DS (GDT_ENTRY_KERNEL_BASE + 1)
#define __KERNEL_DS (GDT_ENTRY_KERNEL_DS * 8)
复制代码



把其中的宏替换成数值，则为：
#define __USER_CS 115 [00000000 1110 0 11]
#define __USER_DS 123 [00000000 1111 0 11]
#define __KERNEL_CS 96 [00000000 1100 0 00]
#define __KERNEL_DS 104 [00000000 1101 0 00]
复制代码



方括号后是这四个段选择符的16位二制表示，它们的索引号和T1字段值也可以算出来了
__USER_CS index= 14 T1=0
__USER_DS index= 15 T1=0
__KERNEL_CS index= 12 T1=0
__KERNEL_DS index= 13 T1=0
复制代码



T1均为0，则表示都使用了GDT，再来看初始化GDT的内容中相应的12-15项(arch/i386/head.S)：
.quad 0x00cf9a000000ffff /* 0x60 kernel 4GB code at 0x00000000 /
.quad 0x00cf92000000ffff / 0x68 kernel 4GB data at 0x00000000 /
.quad 0x00cffa000000ffff / 0x73 user 4GB code at 0x00000000 /
.quad 0x00cff2000000ffff / 0x7b user 4GB data at 0x00000000 */
复制代码



按照前面段描述符表中的描述，可以把它们展开，发现其16-31位全为0，即四个段的基地址全为0。



这样，给定一个段内偏移地址，按照前面转换公式，0 + 段内偏移，转换为线性地址，可以得出重要的结论，“在Linux下，逻辑地址与线性地址总是一致（是一致，不是有些人说的相同）的，即逻辑地址的偏移量字段的值与线性地址的值总是相同的。！！！”



忽略了太多的细节，例如段的权限检查。呵呵。



Linux中，绝大部份进程并不例用LDT，除非使用Wine ，仿真Windows程序的时候。



4.CPU的页式内存管理



CPU的页式内存管理单元，负责把一个线性地址，最终翻译为一个物理地址。从管理和效率的角度出发，线性地址被分为以固定长度为单位的组，称为页(page)，例如一个32位的机器，线性地址最大可为4G，可以用4KB为一个页来划分，这页，整个线性地址就被划分为一个tatol_page[2^20]的大数组，共有2的20个次方个页。这个大数组我们称之为页目录。目录中的每一个目录项，就是一个地址——对应的页的地址。



另一类“页”，我们称之为物理页，或者是页框、页桢的。是分页单元把所有的物理内存也划分为固定长度的管理单位，它的长度一般与内存页是一一对应的。



这里注意到，这个total_page数组有2^20个成员，每个成员是一个地址（32位机，一个地址也就是4字节），那么要单单要表示这么一个数组，就要占去4MB的内存空间。为了节省空间，引入了一个二级管理模式的机器来组织分页单元。文字描述太累，看图直观一些：
Snap1.jpg
如上图，
1、分页单元中，页目录是唯一的，它的地址放在CPU的cr3寄存器中，是进行地址转换的开始点。万里长征就从此长始了。
2、每一个活动的进程，因为都有其独立的对应的虚似内存（页目录也是唯一的），那么它也对应了一个独立的页目录地址。——运行一个进程，需要将它的页目录地址放到cr3寄存器中，将别个的保存下来。
3、每一个32位的线性地址被划分为三部份，面目录索引(10位)：页表索引(10位)：偏移(12位)
依据以下步骤进行转换：
1、从cr3中取出进程的页目录地址（操作系统负责在调度进程的时候，把这个地址装入对应寄存器）；
2、根据线性地址前十位，在数组中，找到对应的索引项，因为引入了二级管理模式，页目录中的项，不再是页的地址，而是一个页表的地址。（又引入了一个数组），页的地址被放到页表中去了。
3、根据线性地址的中间十位，在页表（也是数组）中找到页的起始地址；
4、将页的起始地址与线性地址中最后12位相加，得到最终我们想要的葫芦；



这个转换过程，应该说还是非常简单地。全部由硬件完成，虽然多了一道手续，但是节约了大量的内存，还是值得的。那么再简单地验证一下：
1、这样的二级模式是否仍能够表示4G的地址；
页目录共有：2^10项，也就是说有这么多个页表
每个目表对应了：2^10页；
每个页中可寻址：2^12个字节。
还是2^32 = 4GB



2、这样的二级模式是否真的节约了空间；
也就是算一下页目录项和页表项共占空间 (2^10 * 4 + 2 ^10 *4) = 8KB。哎，……怎么说呢！！！
红色错误，标注一下，后文贴中有此讨论。。。。。。
按<深入理解计算机系统>中的解释,二级模式空间的节约是从两个方面实现的:
A、如果一级页表中的一个页表条目为空，那么那所指的二级页表就根本不会存在。这表现出一种巨大的潜在节约，因为对于一个典型的程序，4GB虚拟地址空间的大部份都会是未分配的；
B、只有一级页表才需要总是在主存中。虚拟存储器系统可以在需要时创建，并页面调入或调出二级页表，这就减少了主存的压力。只有最经常使用的二级页表才需要缓存在主存中。——不过Linux并没有完全享受这种福利，它的页表目录和与已分配页面相关的页表都是常驻内存的。



值得一提的是，虽然页目录和页表中的项，都是4个字节，32位，但是它们都只用高20位，低12位屏蔽为0——把页表的低12屏蔽为0，是很好理解的，因为这样，它刚好和一个页面大小对应起来，大家都成整数增加。计算起来就方便多了。但是，为什么同时也要把页目录低12位屏蔽掉呢？因为按同样的道理，只要屏蔽其低10位就可以了，不过我想，因为12>10，这样，可以让页目录和页表使用相同的数据结构，方便。



本贴只介绍一般性转换的原理，扩展分页、页的保护机制、PAE模式的分页这些麻烦点的东东就不啰嗦了……可以参考其它专业书籍。



5.Linux的页式内存管理
原理上来讲，Linux只需要为每个进程分配好所需数据结构，放到内存中，然后在调度进程的时候，切换寄存器cr3，剩下的就交给硬件来完成了（呵呵，事实上要复杂得多，不过偶只分析最基本的流程）。



前面说了i386的二级页管理架构，不过有些CPU，还有三级，甚至四级架构，Linux为了在更高层次提供抽像，为每个CPU提供统一的界面。提供了一个四层页管理架构，来兼容这些二级、三级、四级管理架构的CPU。这四级分别为：



页全局目录PGD（对应刚才的页目录）
页上级目录PUD（新引进的）
页中间目录PMD（也就新引进的）
页表PT（对应刚才的页表）。



整个转换依据硬件转换原理，只是多了二次数组的索引罢了，如下图：
Snap2.jpg
那么，对于使用二级管理架构32位的硬件，现在又是四级转换了，它们怎么能够协调地工作起来呢？嗯，来看这种情况下，怎么来划分线性地址吧！
从硬件的角度，32位地址被分成了三部份——也就是说，不管理软件怎么做，最终落实到硬件，也只认识这三位老大。
从软件的角度，由于多引入了两部份，，也就是说，共有五部份。——要让二层架构的硬件认识五部份也很容易，在地址划分的时候，将页上级目录和页中间目录的长度设置为0就可以了。
这样，操作系统见到的是五部份，硬件还是按它死板的三部份划分，也不会出错，也就是说大家共建了和谐计算机系统。



这样，虽说是多此一举，但是考虑到64位地址，使用四层转换架构的CPU，我们就不再把中间两个设为0了，这样，软件与硬件再次和谐——抽像就是强大呀！！！



例如，一个逻辑地址已经被转换成了线性地址，0x08147258，换成二制进，也就是：
0000100000 0101000111 001001011000
内核对这个地址进行划分
PGD = 0000100000
PUD = 0
PMD = 0
PT = 0101000111
offset = 001001011000



现在来理解Linux针对硬件的花招，因为硬件根本看不到所谓PUD,PMD，所以，本质上要求PGD索引，直接就对应了PT的地址。而不是再到PUD和PMD中去查数组（虽然它们两个在线性地址中，长度为0，2^0 =1，也就是说，它们都是有一个数组元素的数组），那么，内核如何合理安排地址呢？
从软件的角度上来讲，因为它的项只有一个，32位，刚好可以存放与PGD中长度一样的地址指针。那么所谓先到PUD，到到PMD中做映射转换，就变成了保持原值不变，一一转手就可以了。这样，就实现了“逻辑上指向一个PUD，再指向一个PDM，但在物理上是直接指向相应的PT的这个抽像，因为硬件根本不知道有PUD、PMD这个东西”。



然后交给硬件，硬件对这个地址进行划分，看到的是：
页目录 = 0000100000
PT = 0101000111
offset = 001001011000
嗯，先根据0000100000(32)，在页目录数组中索引，找到其元素中的地址，取其高20位，找到页表的地址，页表的地址是由内核动态分配的，接着，再加一个offset，就是最终的物理地址了。



第一层理解





  1. 每个进程都有自己独立的4G内存空间，各个进程的内存空间具有类似的结构




  2. 一个新进程建立的时候，将会建立起自己的内存空间，此进程的数据，代码等从磁盘拷贝到自己的进程空间，





哪些数据在哪里，都由进程控制表中的task_struct记录，task_struct中记录中一条链表，记录中内存空间的分配



情况，哪些地址有数据，哪些地址无数据，哪些可读，哪些可写，都可以通过这个链表记录




  1. 每个进程已经分配的内存空间，都与对应的磁盘空间映射



问题：



计算机明明没有那么多内存（n个进程的话就需要n*4G）内存



建立一个进程，就要把磁盘上的程序文件拷贝到进程对应的内存中去，对于一个程序对应的多个进程这种情况，



浪费内存！



第二层理解





  1. 每个进程的4G内存空间只是虚拟内存空间，每次访问内存空间的某个地址，都需要把地址翻译为实际物理内存地址




  2. 所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。




  3. 进程要知道哪些内存地址上的数据在物理内存上，哪些不在，还有在物理内存上的哪里，需要用页表来记录




  4. 页表的每一个表项分两部分，第一部分记录此页是否在物理内存上，第二部分记录物理内存页的地址（如果在的话）




  5. 当进程访问某个虚拟地址，去看页表，如果发现对应的数据不在物理内存中，则缺页异常





6.缺页异常的处理过程，就是把进程需要的数据从磁盘上拷贝到物理内存中，如果内存已经满了，没有空地方了，



那就找一个页覆盖，当然如果被覆盖的页曾经被修改过，需要将此页写回磁盘



优点：



1.既然每个进程的内存空间都是一致而且固定的，所以链接器在链接可执行文件时，可以设定内存地址，而不用



去管这些数据最终实际的内存地址，这是有独立内存空间的好处



2.当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程



只需要把自己的虚拟内存映射过去就可以了，节省内存



3.在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续



空间，可以利用碎片。



另外，事实上，在每个进程创建加载时，内核只是为进程“创建”了虚拟内存的布局，具体就是初始化进程控制表中



内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data段）拷贝到物理内存中，



只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射），等到运行到对应的程序时，才会通过缺页异常，



来拷贝数据。还有进程运行过程中，要动态分配内存，比如malloc时，也只是分配了虚拟内存，即为这块虚拟内存



对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。



补充理解：



虚拟存储器涉及三个概念： 虚拟存储空间，磁盘空间，内存空间



可以认为虚拟空间都被映射到了磁盘空间中，（事实上也是按需要映射到磁盘空间上，通过mmap），并且由页表记录



映射位置，当访问到某个地址的时候，通过页表中的有效位，可以得知此数据是否在内存中，如果不是，则通过缺页异常，将磁盘对应的数据拷贝到内存中，如果没有空闲内存，则选择牺牲页面，替换其他页面。



mmap是用来建立从虚拟空间到磁盘空间的映射的，可以将一个虚拟空间地址映射到一个磁盘文件上，当不设置这个



地址时，则由系统自动设置，函数返回对应的内存地址（虚拟地址），当访问这个地址的时候，就需要把磁盘上的内容



拷贝到内存了，然后就可以读或者写，最后通过manmap可以将内存上的数据换回到磁盘，也就是解除虚拟空间和内存



空间的映射，这也是一种读写磁盘文件的方法，也是一种进程共享数据的方法 共享内存



物理内存：



在内核态申请内存比在用户态申请内存要更为直接，它没有采用用户态那种延迟分配内存技术。内核认为一旦有内核函数申请



内存，那么就必须立刻满足该申请内存的请求，并且这个请求一定是正确合理的。相反，对于用户态申请内存的请求，内核总是



尽量延后分配物理内存，用户进程总是先获得一个虚拟内存区的使用权，最终通过缺页异常获得一块真正的物理内存。



1.物理内存的内核映射



IA32架构中内核虚拟地址空间只有1GB大小（从3GB到4GB），因此可以直接将1GB大小的物理内存（即常规内存）映射到内核



地址空间，但超出1GB大小的物理内存（即高端内存）就不能映射到内核空间。为此，内核采取了下面的方法使得内核可以使用



所有的物理内存。



   1).高端内存不能全部映射到内核空间，也就是说这些物理内存没有对应的线性地址。不过，内核为每个物理页框都分配了对应的页框描述符，所有的页框描述符都保存在mem_map数组中，因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用alloc_pages()和alloc_page()来分配高端内存，因为这些函数返回页框描述符的线性地址。





   2).内核地址空间的后128MB专门用于映射高端内存，否则，没有线性地址的高端内存不能被内核所访问。这些高端内存的内核映射显然是暂时映射的，否则也只能映射128MB的高端内存。当内核需要访问高端内存时就临时在这个区域进行地址映射，使用完毕之后再用来进行其他高端内存的映射。 由于要进行高端内存的内核映射，因此直接能够映射的物理内存大小只有896MB，该值保存在high_memory中。


内核采用了三种机制将高端内存映射到内核空间：永久内核映射，固定映射和vmalloc机制。



2.物理内存管理机制
基于物理内存在内核空间中的映射原理，物理内存的管理方式也有所不同。内核中物理内存的管理机制主要有伙伴算法，slab高速缓存和vmalloc机制。其中伙伴算法和slab高速缓存都在物理内存映射区分配物理内存，而vmalloc机制则在高端内存映射区分配物理内存。
伙伴算法
伙伴算法负责大块连续物理内存的分配和释放，以页框为基本单位。该机制可以避免外部碎片。
per-CPU页框高速缓存
内核经常请求和释放单个页框，该缓存包含预先分配的页框，用于满足本地CPU发出的单一页框请求。
slab缓存
slab缓存负责小块物理内存的分配，并且它也作为高速缓存，主要针对内核中经常分配并释放的对象。
vmalloc机制
vmalloc机制使得内核通过连续的线性地址来访问非连续的物理页框，这样可以最大限度的使用高端物理内存。



3.物理内存的分配
内核发出内存申请的请求时，根据内核函数调用接口将启用不同的内存分配器。
3.1 分区页框分配器
分区页框分配器 (zoned page frame allocator) ,处理对连续页框的内存分配请求。分区页框管理器分为两大部分:前端的管理区分配器和伙伴系统



管理区分配器负责搜索一个能满足请求页框块大小的管理区。在每个管理区中,具体的页框分配工作由伙伴系统负责。为了达到更好的系统性能,单个页框的申请工作直接通过per-CPU页框高速缓存完成。
该分配器通过几个函数和宏来请求页框,



这些函数和宏将核心的分配函数__alloc_pages_nodemask()封装,形成满足不同分配需求的分配函数。其中，alloc_pages()系列函数返回物理内存首页框描述符，__get_free_pages()系列函数返回内存的线性地址。
3.2 slab分配器
slab 分配器最初是为了解决物理内存的内部碎片而提出的，它将内核中常用的数据结构看做对象。slab分配器为每一种对象建立高速缓存。内核对该对象的分配和释放均是在这块高速缓存中操作。



可以看到每种对象的高速缓存是由若干个slab组成，每个slab是由若干个页框组成的。虽然slab分配器可以分配比单个页框更小的内存块，但它所需的所有内存都是通过伙伴算法分配的。
slab高速缓存分专用缓存和通用缓存。专用缓存是对特定的对象，比如为内存描述符创建高速缓存。通用缓存则是针对一般情况，适合分配任意大小的物理内存，其接口即为kmalloc()。
3.3 非连续内存区内存的分配
内核通过vmalloc()来申请非连续的物理内存，若申请成功，该函数返回连续内存区的起始地址，否则，返回NULL。vmalloc()和kmalloc()申请的内存有所不同，kmalloc()所申请内存的线性地址与物理地址都是连续的，而vmalloc()所申请的内存线性地址连续而物理地址则是离散的，两个地址之间通过内核页表进行映射。
vmalloc()的工作方式理解起来很简单：
1).寻找一个新的连续线性地址空间；
2).依次分配一组非连续的页框；
3).为线性地址空间和非连续页框建立映射关系，即修改内核页表；
vmalloc()的内存分配原理与用户态的内存分配相似，都是通过连续的虚拟内存来访问离散的物理内存，并且虚拟地址和物理地址之间是通过页表进行连接的，通过这种方式可以有效的使用物理内存。但是应该注意的是，vmalloc()申请物理内存时是立即分配的，因为内核认为这种内存分配请求是正当而且紧急的；相反，用户态有内存请求时，内核总是尽可能的延后，毕竟用户态跟内核态不在一个特权级。



二、malloc和free是如何分配和释放内存？



如何查看进程发生缺页中断的次数？



用# ps -o majflt,minflt -C program 命令查看



majflt代表major fault，中文名叫大错误，minflt代表minor fault，中文名叫小错误。



这两个数值表示一个进程自启动以来所发生的缺页中断的次数。



可以用命令ps -o majflt minflt -C program来查看进程的majflt, minflt的值，这两个值都是累加值，从进程启动开始累加。在对高性能要求的程序做压力测试的时候，我们可以多关注一下这两个值。
如果一个进程使用了mmap将很大的数据文件映射到进程的虚拟地址空间，我们需要重点关注majflt的值，因为相比minflt，majflt对于性能的损害是致命的，随机读一次磁盘的耗时数量级在几个毫秒，而minflt只有在大量的时候才会对性能产生影响。



发成缺页中断后，执行了那些操作？



当一个进程发生缺页中断的时候，进程会陷入内核态，执行以下操作：
1、检查要访问的虚拟地址是否合法
2、查找/分配一个物理页
3、填充物理页内容（读取磁盘，或者直接置0，或者啥也不干）
4、建立映射关系（虚拟地址到物理地址）
重新执行发生缺页中断的那条指令
如果第3步，需要读取磁盘，那么这次缺页中断就是majflt，否则就是minflt。



内存分配的原理



从操作系统角度来看，进程分配内存有两种方式，分别由两个系统调用完成：brk和mmap（不考虑共享内存）。



1、brk是将数据段(.data)的最高地址指针_edata往高地址推；



2、mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。



这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。



在标准C库中，提供了malloc/free函数分配释放内存，这两个函数底层是由brk，mmap，munmap这些系统调用实现的。



下面以一个例子来说明内存分配的原理：



情况一、malloc小于128k的内存，使用brk分配内存，将_edata往高地址推(只分配虚拟空间，不对应物理内存(因此没有初始化)，第一次读/写数据时，引起内核缺页中断，内核才分配对应的物理内存，然后虚拟地址空间建立映射关系)，如下图：



1、进程启动的时候，其（虚拟）内存空间的初始布局如图1所示。



其中，mmap内存映射文件是在堆和栈的中间（例如libc-2.2.93.so，其它数据文件等），为了简单起见，省略了内存映射文件。



_edata指针（glibc里面定义）指向数据段的最高地址。
2、进程调用A=malloc(30K)以后，内存空间如图2：



  malloc函数会调用brk系统调用，将_edata指针往高地址推30K，就完成虚拟内存分配。


你可能会问：只要把_edata+30K就完成内存分配了？



事实是这样的，_edata+30K只是完成虚拟地址的分配，A这块内存现在还是没有物理页与之对应的，等到进程第一次读写A这块内存的时候，发生缺页中断，这个时候，内核才分配A这块内存对应的物理页。也就是说，如果用malloc分配了A这块内容，然后从来不访问它，那么，A对应的物理页是不会被分配的。
3、进程调用B=malloc(40K)以后，内存空间如图3。



情况二、malloc大于128k的内存，使用mmap分配内存，在堆和栈之间找一块空闲内存分配(对应独立内存，而且初始化为0)，如下图：



4、进程调用C=malloc(200K)以后，内存空间如图4：



默认情况下，malloc函数分配内存，如果请求内存大于128K（可由M_MMAP_THRESHOLD选项调节），那就不是去推_edata指针了，而是利用mmap系统调用，从堆和栈的中间分配一块虚拟内存。



这样子做主要是因为::



brk分配的内存需要等到高地址内存释放以后才能释放（例如，在B释放之前，A是不可能释放的，这就是内存碎片产生的原因，什么时候紧缩看下面），而mmap分配的内存可以单独释放。



当然，还有其它的好处，也有坏处，再具体下去，有兴趣的同学可以去看glibc里面malloc的代码了。
5、进程调用D=malloc(100K)以后，内存空间如图5；
6、进程调用free(C)以后，C对应的虚拟内存和物理内存一起释放。



7、进程调用free(B)以后，如图7所示：



    B对应的虚拟内存和物理内存都没有释放，因为只有一个_edata指针，如果往回推，那么D这块内存怎么办呢？


当然，B这块内存，是可以重用的，如果这个时候再来一个40K的请求，那么malloc很可能就把B这块内存返回回去了。
8、进程调用free(D)以后，如图8所示：



    B和D连接起来，变成一块140K的空闲内存。


9、默认情况下：



当最高地址空间的空闲内存超过128K（可由M_TRIM_THRESHOLD选项调节）时，执行内存紧缩操作（trim）。在上一个步骤free的时候，发现最高地址空闲内存超过128K，于是内存紧缩，变成图9所示。



真相大白
说完内存分配的原理，那么被测模块在内核态cpu消耗高的原因就很清楚了：每次请求来都malloc一块2M的内存，默认情况下，malloc调用 mmap分配内存，请求结束的时候，调用munmap释放内存。假设每个请求需要6个物理页，那么每个请求就会产生6个缺页中断，在2000的压力下，每 秒就产生了10000多次缺页中断，这些缺页中断不需要读取磁盘解决，所以叫做minflt；缺页中断在内核态执行，因此进程的内核态cpu消耗很大。缺 页中断分散在整个请求的处理过程中，所以表现为分配语句耗时（10us）相对于整条请求的处理时间（1000us）比重很小。
解决办法
将动态内存改为静态分配，或者启动的时候，用malloc为每个线程分配，然后保存在threaddata里面。但是，由于这个模块的特殊性，静态分配，或者启动时候分配都不可行。另外，Linux下默认栈的大小限制是10M，如果在栈上分配几M的内存，有风险。
禁止malloc调用mmap分配内存，禁止内存紧缩。
在进程启动时候，加入以下两行代码：
mallopt(M_MMAP_MAX, 0); // 禁止malloc调用mmap分配内存
mallopt(M_TRIM_THRESHOLD, -1); // 禁止内存紧缩
效果：加入这两行代码以后，用ps命令观察，压力稳定以后，majlt和minflt都为0。进程的系统态cpu从20降到10。



三、如何查看堆内内存的碎片情况 ？



glibc 提供了以下结构和接口来查看堆内内存和 mmap 的使用情况。
struct mallinfo {
int arena; /* non-mmapped space allocated from system /
int ordblks; / number of free chunks /
int smblks; / number of fastbin blocks /
int hblks; / number of mmapped regions /
int hblkhd; / space in mmapped regions /
int usmblks; / maximum total allocated space /
int fsmblks; / space available in freed fastbin blocks /
int uordblks; / total allocated space /
int fordblks; / total free space /
int keepcost; / top-most, releasable (via malloc_trim) space */
};



/*返回heap(main_arena)的内存使用情况，以 mallinfo 结构返回 */
struct mallinfo mallinfo();



/* 将heap和mmap的使用情况输出到stderr*/
void malloc_stats();



可通过以下例子来验证mallinfo和malloc_stats输出结果。
#include
#include
#include
#include
#include <sys/mman.h>
#include



size_t heap_malloc_total, heap_free_total,mmap_total, mmap_count;



void print_info()
{
struct mallinfo mi = mallinfo();
printf(“count by itself:\n”);
printf(“\theap_malloc_total=%lu heap_free_total=%lu heap_in_use=%lu\n\tmmap_total=%lu mmap_count=%lu\n”,
heap_malloc_total1024, heap_free_total1024, heap_malloc_total1024-heap_free_total1024,
mmap_total*1024, mmap_count);
printf(“count by mallinfo:\n”);
printf(“\theap_malloc_total=%lu heap_free_total=%lu heap_in_use=%lu\n\tmmap_total=%lu mmap_count=%lu\n”,
mi.arena, mi.fordblks, mi.uordblks,
mi.hblkhd, mi.hblks);
printf(“from malloc_stats:\n”);
malloc_stats();
}



#define ARRAY_SIZE 200
int main(int argc, char** argv)
{
char** ptr_arr[ARRAY_SIZE];
int i;

for( i = 0; i < ARRAY_SIZE; i++)
{
ptr_arr[i] = malloc(i * 1024);

if ( i < 128) //glibc默认128k以上使用mmap
{
heap_malloc_total += i;
}
else
{
mmap_total += i;
mmap_count++;
}
}

print_info();



for( i = 0; i < ARRAY_SIZE; i++) 

{ 

       if ( i % 2 == 0) 

            continue; 

       free(ptr_arr[i]);



       if ( i < 128) 

       { 

               heap_free_total += i; 

       } 

       else 

       { 

              mmap_total -= i; 

              mmap_count--; 

       } 

}  

printf("\nafter free\n"); 

print_info();



return 1;  }


该例子第一个循环为指针数组每个成员分配索引位置 (KB) 大小的内存块，并通过 128 为分界分别对 heap 和 mmap 内存分配情况进行计数；
第二个循环是 free 索引下标为奇数的项，同时更新计数情况。通过程序的计数与mallinfo/malloc_stats 接口得到结果进行对比，并通过 print_info打印到终端。



下面是一个执行结果：
count by itself:
heap_malloc_total=8323072 heap_free_total=0 heap_in_use=8323072
mmap_total=12054528 mmap_count=72
count by mallinfo:
heap_malloc_total=8327168 heap_free_total=2032 heap_in_use=8325136
mmap_total=12238848 mmap_count=72



from malloc_stats:
Arena 0:
system bytes = 8327168
in use bytes = 8325136
Total (incl. mmap):
system bytes = 20566016
in use bytes = 20563984
max mmap regions = 72
max mmap bytes = 12238848



after free
count by itself:
heap_malloc_total=8323072 heap_free_total=4194304 heap_in_use=4128768
mmap_total=6008832 mmap_count=36



count by mallinfo:
heap_malloc_total=8327168 heap_free_total=4197360 heap_in_use=4129808
mmap_total=6119424 mmap_count=36



from malloc_stats:
Arena 0:
system bytes = 8327168
in use bytes = 4129808
Total (incl. mmap):
system bytes = 14446592
in use bytes = 10249232
max mmap regions = 72
max mmap bytes = 12238848



由上可知，程序统计和mallinfo 得到的信息基本吻合，其中 heap_free_total 表示堆内已释放的内存碎片总和。
如果想知道堆内究竟有多少碎片，可通过 mallinfo 结构中的 fsmblks 、smblks 、ordblks 值得到，这些值表示不同大小区间的碎片总个数，这些区间分别是 0~80 字节，80~512 字节，512~128k。如果 fsmblks 、 smblks 的值过大，那碎片问题可能比较严重了。
不过， mallinfo 结构有一个很致命的问题，就是其成员定义全部都是 int ，在 64 位环境中，其结构中的 uordblks/fordblks/arena/usmblks 很容易就会导致溢出，应该是历史遗留问题，使用时要注意！



四、既然堆内内存brk和sbrk不能直接释放，为什么不全部使用 mmap 来分配，munmap直接释放呢？
既然堆内碎片不能直接释放，导致疑似“内存泄露”问题，为什么 malloc 不全部使用 mmap 来实现呢(mmap分配的内存可以会通过 munmap 进行 free ，实现真正释放)？而是仅仅对于大于 128k 的大块内存才使用 mmap ？



其实，进程向 OS 申请和释放地址空间的接口 sbrk/mmap/munmap 都是系统调用，频繁调用系统调用都比较消耗系统资源的。并且， mmap 申请的内存被 munmap 后，重新申请会产生更多的缺页中断。例如使用 mmap 分配 1M 空间，第一次调用产生了大量缺页中断 (1M/4K 次 ) ，当munmap 后再次分配 1M 空间，会再次产生大量缺页中断。缺页中断是内核行为，会导致内核态CPU消耗较大。另外，如果使用 mmap 分配小内存，会导致地址空间的分片更多，内核的管理负担更大。
同时堆是一个连续空间，并且堆内碎片由于没有归还 OS ，如果可重用碎片，再次访问该内存很可能不需产生任何系统调用和缺页中断，这将大大降低 CPU 的消耗。 因此， glibc 的 malloc 实现中，充分考虑了 sbrk 和 mmap 行为上的差异及优缺点，默认分配大块内存 (128k) 才使用 mmap 获得地址空间，也可通过 mallopt(M_MMAP_THRESHOLD, ) 来修改这个临界值。



五、如何查看进程的缺页中断信息？
可通过以下命令查看缺页中断信息
ps -o majflt,minflt -C
ps -o majflt,minflt -p
其中:: majflt 代表 major fault ，指大错误；



       minflt 代表 minor fault ，指小错误。


这两个数值表示一个进程自启动以来所发生的缺页中断的次数。
其中 majflt 与 minflt 的不同是::



    majflt 表示需要读写磁盘，可能是内存对应页面在磁盘中需要load 到物理内存中，也可能是此时物理内存不足，需要淘汰部分物理页面至磁盘中。


参看:: http://blog.163.com/xychenbaihu@yeah/blog/static/132229655201210975312473/



六、除了 glibc 的 malloc/free ，还有其他第三方实现吗？



其实，很多人开始诟病 glibc 内存管理的实现，特别是高并发性能低下和内存碎片化问题都比较严重，因此，陆续出现一些第三方工具来替换 glibc 的实现，最著名的当属 google 的tcmalloc和facebook 的jemalloc 。
网上有很多资源，可以自己查(只用使用第三方库，代码不用修改，就可以使用第三方库中的malloc)。



参考资料：
《深入理解计算机系统》第 10 章
http://www.kernel.org/doc/Documentation/x86/x86_64/mm.txt



https://www.ibm.com/developerworks/cn/linux/l-lvm64/



http://www.kerneltravel.net/journal/v/mem.htm



http://blog.csdn.net/baiduforum/article/details/6126337



http://www.nosqlnotes.net/archives/105



http://www.man7.org/linux/man-pages/man3/mallinfo.3.html


Category linux