前言
前面我们知道了关于物理页面，以及对于物理内存管理的数据结构 page和zone。接下来看看很关键的内存分配。
对于分配是物理内存很关键的知识点。
这里涉及到一个大名鼎鼎的伙伴系统算法实现对物理内存的分配，但是这个算法不是linux独有的。
1、伙伴系统
这个系统干啥的呢？那肯定是你申请需要内存的时候，这个系统就给你安排一块，不需要的时候就负责把内存回收回去。
比较独特的就是，在伙伴系统中，它将内存分为了2的order次幂。这个order通常是0到11，这个11是一个MAX_ORDER定义的，这个不是一点必须是11，可以设置。
这个意思就是伙伴系统它提供了12中商品（内存），这些数字就是代表了从1、2、4…1024不同大小的内存块（不同的内存块包含的页面数量不同）。大概样子口说不太利索，看看图
有种提供了一个链表，链表上整了十二内存池。
为什么叫伙伴呢？根据我的感觉是因为内存回收的时候，会将相邻的4 4合为8，然后一直合到不能再合并。
对于这个算法了解以后，那么来看看对于页面的具体分配的函数api
2、页面分配函数
linux内核提供了常用的页面分配函数接口，函数都是以页为分配单位。
核心接口函数
static inline struct page * alloc_pages(gfp_t gfp_mask, unsigned int order)
这个函数就是用来分配2的order次幂物理页面的函数，通过这个参数可以看出来。
至于这个gfp_mask掩码，咱们后面会讲到。
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
__get_free_pages()函数返回的是所分配内存的内核空间的虚拟地址，如果是线性映射的物理内存，则直接返回线性映射区域的内核空间虚拟地址；如果是高端映射的内存，则返回动态映射的虚拟地址。
虚拟地址的转换–>使用page_address()函数
这两个的区别，上是物理内存页面，下面是虚拟内存。
如果你需要分配一个物理页面，还可以使用下面两个封装好的接口，不过这两个底层还是通过alloc_page实现，知识order为0：
#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0) #define __get_free_page(gfp_mask) \__get_free_pages((gfp_mask), 0)
如果需要返回一个全填充为0的页面，可以使用如下这个接口函数。
unsigned long get_zeroed_page(gfp_t gfp_mask)
使用 alloc_page()分配的物理页面，理论上讲有可能被随机地填充了某些垃圾信息，因此在有些敏感的场合是需要把分配的内存进行清零，然后使用，这样可以减少不必要的麻烦。
3、页面释放
页面申请了，那么肯定页面需要释放，页面释放的函数是：
void __free_pages(struct page *page, unsigned int order); #define __free_page(page) __free_pages((page), 0)
估计这个底层的实现还是大同小异
对于这个部分我们知道了伙伴系统算法大概思想，也对物理页面的申请释放有了一定认识。下面来解决刚刚那个问题，gfp_mask是什么？
4、gfp_mask
这个标识在刚刚alloc_page的函数中，看到了，其实内存分配会面临很多的情况，还希望其能一直保持工作的高效状态。而gfp_mask作为一个修饰符，影响着整个内存的分配流程，通过不同的值，告诉内存分配应该走什么流程。（这个的值类似于寄存器的配置，通过位的值，继续往后看，你就知道了。）
gfp_mask其实被定义成一个unsigned类型的变量。
typedef unsigned __bitwise__ gfp_t;
gfp_mask分配掩码定义在include/linux/gfp.h文件中，这些标志位在Linux 4.4内核中被重新归类，大致可以分成几类。
内存管理区修饰符（zone modifier）。
移动修饰符（mobility and placement modifier）。
水位修饰符（watermark modifier）。
页面回收修饰符（page reclaim modifier）。
行动修饰符（action modifier）。
下面详细介绍各种修饰符。
（1）内存管理区修饰符
这个就是告诉你从哪个区获取内存（zone），内存管理区修饰符使用gfp_mask的最低4个比特位来表示，如表7.1所示。
（2）移动修饰符
移动修饰符主要用来指示分配出来的页面具有的迁移属性，如表 7.2 所示。在 Linux 2.6.24内核中，为了解决外碎片化的问题，引入了迁移类型，因此在分配内存时也需要指定所分配的页面具有哪些移动属性。
（3）水位修饰符
是否可以访问系统预留的紧急内存，水位高了，才紧急。
（第二个标识符 我觉得应该也是可以的）
（4）页面回收修饰符
（5）行动修饰符
上表列出了5大类的分配掩码，对于内核开发者或者驱动开发者来说，要正确使用这些标志位是一件很困难的事情，因此定义一些常用的分配掩码的组合，叫作类型标志（Type Flag），如表7.6所示。类型标志提供了内核开发中常用的分配掩码的组合，推荐开发者使用这些类型标志。（nice啊，真的一个个配置，还是有点打老壳，不过对于经常玩寄存器的人来说，倒也还行，就是各种组合还是有点繁琐）
分配掩码的组合
上面这些都是常用的分配掩码，在实际使用过程中需要注意以下事项。
1）GFP_KERNEL是最常见的内存分配掩码之一，主要用于分配内核使用的内存，需要注意的是分配过程会引起睡眠，这在中断上下文以及不能睡眠的内核路径里调用该分配掩码需要特别警惕，因为会引起死锁或者其他系统异常。
2）GFP_ATOMIC这个标志位正好和GFP_KERNEL相反，它可以使用在不能睡眠的内存分配路径上，比如中断处理程序、软中断以及tasklet等。GFP_KERNEL可以让调用者睡眠等待系统页面回收来释放一些内存，但GFP_ATOMIC不可以，所以有可能会分配失败。
3）GFP_USER、GFP_HIGHUSER和GFP_HIGHUSER_MOVABLE。这几个标志位都是为用户空间进程分配内存的。不同之处在于，GFP_HIGHUSER 首先使用高端内存（Highmem），GFP_HIGHUSER_MOVABLE 优先使用高端内存并且分配的内存具有可迁移属性。
4）GFP_NOIO 和 GFP_NOFS 都会产生阻塞，它们用来避免某些其他的操作。GFP_NOIO表示分配过程中绝不会启动任何磁盘I/O的操作。GFP_NOFS表示可以启动磁盘I/O，但是不会启动文件系统的相关操作。举个例子，假设进程 A 在执行打开文件的操作中需要分配内存，这时内存短缺，那么进程A会睡眠等待，系统的OOM Killer机制会选择一个进程来杀掉。假设选择了进程B，而进程B退出时需要执行一些文件系统的操作，这些操作可能会去申请锁，而恰巧进程A持有这个锁，所以死锁就发生了。
5）使用这些分配掩码需要注意页面的迁移类型，GFP_KERNEL分配的页面通常是不可迁移的，GFP_HIGHUSER_MOVABLE分配的页面是可迁移的。
（在这里如果你在一定的内存申请分配场景下，使用了不合适的修饰符，就会引起内存的bug，而如果你看过这个，你会猜测这里就会是一个可能引起故障的点。）
5、内存碎片化
前面我们知道了内存的分配，但是我们知道内存的不断分配，会产生一些碎片，小的用不掉，大的不够用。我们在日常生活中电脑用久了，会变得很慢，这就是因为内存的碎片太多了，我们的很多操作其实都是在内存上操作的，所以内存碎片太多了后，你申请获得所满足要求的内存时间就变长了，所以就变慢了，所以为了提升速度，网上会推荐你内存整理一下。（还有磁盘整理）
当然最好是从源头减少问题发生，让我们的内存分配算法能尽量少的减少内存的碎片。这下来真的认识一下为什么叫伙伴系统。伙伴是什么？
在伙伴系统算法中，什么样的内存块可以成为伙伴呢？
其实伙伴系统算法有如下3个基本条件。
- 1）两个块大小相同。
- 2）两个块地址连续。
- 3）两个块必须是同一个大块中分离出来的。
一个8个页面的大内存A0，可以切割成两个小内存块B0和B1，它们大小都是4个页面。B0还可以继续切割成C0和C1，它们是2个页面大小的内存块。C0可以继续切割成P0和P1两个小内存块，它们的大小是一个物理页面。
第一个条件是说两个块大小必须相同，如图7.11所示，B0内存块和B1内存块就是大小相同的。第二个条件是说两个内存块地址连续，伙伴就是类似邻居的意思。第三个条件，两个内存块必须是从同一个大内存块中分离出来的，下面来具体解释。
如图7.13所示，P0和P1为伙伴，它们都是从C0分割出来的，P2和P3为伙伴，它们也是从C1分割出来的。假设P1和P2合并成一个新的内存块C_new0，然后P4、P5、P6和P7合并成一个大的内存块B_new0，会发现即使P0和P3变成空闲页面之后，这8个页面的内存块也无法继续合并成一个新的大内存块了。P0和C_new0无法合并成一个大内存，因为它们两个大小不一样，同样C_new0和P3也不能继续合并。因此P0和P3就变成了一个个的空洞，这就产生了外碎片化（External Fragmentation）。随着时间的推移，外碎片化会变得越来越严重，内存利用率也随之下降。
这就是碎片的产生。
外碎片化的一个比较严重的后果是明明系统有足够的内存，但是无法分配出一大段连续的物理内存供页面分配器使用。因此，伙伴系统算法在设计时就考虑避免图 7.13 所示的内存碎片化。
学术上常用的解决外碎片化的技术叫作内存规整（Memory Compaction），也就是利用移动页面的位置让空闲页面连成一片。但是在早期的Linux内核中，这种方法不一定有效。内核分配的物理内存有很多种用途，比如内核本身使用的内存、硬件需要使用的内存，如DMA缓冲区、用户进程分配的内存如匿名页面等。如果从页面的迁移属性来看，用户进程分配使用的内存是可以迁移的，但是内核本身使用的内存页面是不能随便迁移的。假设在一大块物理内存中，中间有一小块内存被内核本身使用，但是因为这小块内存不能被迁移，导致这一大块内存不能变成连续的物理内存。如图7.14所示，C1是分配给内核使用的内存，即使C0、C2和C3都是空闲内存块，它们也不能被合并一大块连续的物理内存。
为什么内核本身使用的页面不能被迁移呢？因为要迁移这个页面，首先需要把物理页面映射关系断开，然后重新去建立映射关系。
在这个断开映射关系的过程中，如果内核继续访问这个物理页面，就会访问不正确的指针和内存，导致内核出现 oops 错误，甚至导致系统崩溃（Crash）。
内核是一个敏感区域，它必须保证使用的内存是安全的。这和用户进程不太一样，用户进程使用的页面在断开映射关系之后，如果用户进程继续访问这个页面，就会产生一个缺页异常。在缺页异常处理中，会去重新分配一个物理页面，然后和虚拟内存建立映射关系。这个过程对于用户进程来说是安全的。
（就是内核你可不能随便再映射，但是用户进程断了就断了，大不了再来）
在 Linux 2.6.24 开发阶段，社区专家就引入了防止碎片的功能，叫作反碎片法（Anti-Fragmentation）。这里说的反碎片法，其实就是利用迁移类型来实现的。迁移类型是按照页块（PageBlock）来划分的，一个页块正好是页面分配器最大的分配大小，即 2 的MAX_ORDER-1次方，通常是4MB。
不可移动类型 UNMOVABLE：其特点就是在内存中有固定的位置，不能移动到其他地方，比如内核本身需要使用的内存就属于此类。
使用GFP_KERNEL这个标志位分配的内存，就是不能迁移的。简单来说，内核使用的内存都属于此类，包括DMA Buffer等。
可回收的页面：这些页面不能直接移动，但是可以回收。页面的内容可以重新读回或者取回，最典型的一个例子就是映射来自文件的页面缓存。
因此，伙伴系统中的free_area数据结构中包含了MIGRATE_TYPES个链表，这里相当于内存管理区中根据order的大小有0到MAX_ORDER−1个free_area。每个free_area根据MIGRATE_TYPES类型又有几个相应的链表，如图7.15所示，读者可以比较图7.11和图7.15之间的区别。
这就是在伙伴系统的早期基础上，在每个order又细分了页面的类型，产生了不同类型，不同的链表。在运用这种技术的Linux内核中，所有的页块里面的页面都是同一个迁移类型的，中间不会再掺杂其他类型的页面。
这就让能迁移的到一起，不能迁移的到一起，能回收的到一起。
小结
这一章我们了解了伙伴系统算法对于内存页面的管理
然后了解了常用的页面的申请释放函数
再对函数中的gfp_mask有了个功能和常见值的认识
最后对于内存这个碎片化的预防和减轻的方法有了一丢丢认识
对于内存碎片规整，我猜测是内存里面会有标志位，当需要整理的时候，就安排人手去做这个事情。
问题
为什么内核映射不能断开，而用户进程的想断就断了，重新映射就行？
这样分配以后，对于不可移动的内存，是不是内存碎片还是会越来越多？
内存整理中的移动合并成大内存、和内存回收有什么区别，对于不能移动和回收内存有什么策略吗，还是由其摆烂？
今天不想想问题答案了，小少爷休息一下，明天还要加班呢！
参考资料：
《奔跑吧 Linux内核》
