本文先容CMA(Contiguous Memory Allocator)技能事理，从源码剖析CMA的初始化和分配流程，同时讲解涉及到的页面迁移、LRU(Least Rencntly Used)缓存、PCP(per cpu page)缓存等知识。
一、CMA概述
CMA是什么？为什么须要CMA？
Linux伙伴系统(Buddy)利用 Page 粒度来管理内存，每个页面大小为4K。伙伴系统按照空闲内存块的长度，把内存挂载到不同长度的 free_list链表中。free_list 的单位因此 (2^order个Page) 来递增的，即 1 page、2 page、… 2^n，常日情形下最大 order 为10 对应的空闲内存大小为 4M bytes。我们利用伙伴系统来申请连续的物理页面最大的页面最大小4M bytes，且系统内存碎片化严重的时候，也很难分配到高order的页面。
嵌入式系统上一些外设设备，如GPU、Camera，HDMI等都须要预留大量连续内存才能正常事情，且很多情形下仅4M连续内存是不敷以知足设备的需求的，当然我们也可以利用memblock预留内存的方法来保留更大的连续内存，但这部分内存只能被设备所利用而Buddy利用不到，会导致内存摧残浪费蹂躏。CMA由此而生，我们即要能分配连续的大的内存空间给设备利用，平时设备不用时又要把内存给系统用，最大化利用内存。
CMA连续内存分配器，紧张是为了可用于分配连续的大块内存。系统初始化的时候会通过保留一片物理内存区域，平时设备驱动不用时，内存管理系统将该区域用于分配和管理可移动类型页面，供应给APP或者内核movable页面利用。设备驱动利用时，此时已经分配的页面则进行迁移走，该区域用于连续内存分配。
在后续的章节中，我们紧张通过阅读源码的办法，来先容CMA的初始化、分配和页面迁移流程等。
注：后续文中所贴源码为kernel5.4版本，代码截图会省略次要代码，只保留关键代码。
二、CMA紧张数据构造和API
2.1 struct cma
利用struct cma来描述一个CMA区域：
base_pfn：CMA区域物理地址的起始page frame number(页帧号)
count: CMA区域的页面数量
bitmap：描述cma区域页面的分配情形，1表示已分配，0为空闲。
order_per_bit：表示bitmap中一个bit所代表的页面数量（2^order_per_bit）。
2.2 cma_init_reserved_mem
从保留内存块里面获取一块地址为base、大小为size的内存，用来创建和初始化struct cma。
2.3 cma_init_reserved_areas
为了提升内存利用率，该函数用来将这CMA内存标记后归还给 buddy 系统，供 buddy作为可移动页面内存申请。
2.4 cma_alloc
用来从指定的CMA 区域上分配count个连续的页面，按照align对齐。
2.5 cma_release
用来开释已经分配count个连续的页面。
三、CMA紧张流程剖析
3.1 CMA初始化流程
3.1.1 系统初始化：
系统初始化过程须要先创建CMA区域，创建方法有：dts的reserved memory或者通过命令行参数。这里我们看常常利用的通过dts的reserved memory办法，物理内存的描述放置在dts中配置，比如：
linux,cma 为CMA 区域名称。
compatible须为“shared-dma-pool”。
resuable 表示 cma 内存可被 buddy 系统利用。
size 表示cma区域的大小，单位为字节
alignment指定 CMA 区域的地址对齐大小。
linux,cma-default 属性表示当前 cma 内存将会作为默认的cma pool 用于cma 内存的申请。
在系统启动过程中，内核对上面描述的dtb文件进行解析，从而完成内存信息注册，调用流程为：
setup_arch
arm64_memblock_init
early_init_fdt_scan_reserved_mem
__reserved_mem_init_node
__reserved_mem_init_node会遍历__reservedmem_of_table section中的内容，检讨到dts中有compatible匹配（CMA这里为“shared-dma-pool”）就进一步实行对应的initfn。通过RESERVEDMEM_OF_DECLARE定义的都会被链接到__reservedmem_of_table这个section段中，终极会调到利用RESERVEDMEM_OF_DECLARE定义的函数，如下rmem_cma_setup：
3.1.2 rmem_cma_setup
@1 cma_init_reserved_mem 从保留内存块里面获取一块地址为base、大小为size的内存，这里用dtb中解析出来的地址信息来初始化CMA，用来创建和初始化struct cma，代码很大略：
@2 如果dts指定了linux,cma-default，则将dma_contiguous_set_default指向这个CMA区域，利用dma_alloc_contiguous从CMA分配内存时，默认会从该区域分。
实行到此， CMA和其它的保留内存是一样的，都是放在 memblock.reserved 中，这部分保留内存一样没能被 Buddy 系统用到。前面讲过为了提升内存利用率，还须要将CMA这部分内存标记后归还给 Buddy系统，供 Buddy作为可移动页面供应给APP或内核内存申请，由cma_init_reserved_areas来实现。
3.1.3 cma_init_reserved_areas
在内核初始化的后期会调用core_initcall描述的初始化函数：
cma_init_reserved_areas，它直接调用cma_activate_area来实现。cma_activate_area根据cma大小分配bitmap，然后循环调用init_cma_reserved_pageblock来操作CMA区域中所有的页面， 看下源码：
@1 CMA区域由一个bitmap来管理各个page的状态，cma_bitmap_maxno打算Bitmap须要多少内存，i变量表示该CMA eara有多少个pageblock（4M）。
@2 遍历该CM区域中的所有的pageblock
@3 确保CMA区域中的所有page都是在一个zone内
@4 终极调用init_cma_reserved_pageblock，以pageblock为单位进行处理，设置migrate type为MIGRATE_CMA，将页面添加到伙伴系统中并更新zone管理的页面总数。如下：
@1 将页面已经设置的reserved标志位打消掉。
@2 将migratetype设置为MIGRATE_CMA
@3 循环调用__free_pages函数，将CMA区域中所有的页面都开释到buddy系统中。
@4 更新伙伴系统管理的内存数量。
实行到此，后续这部分CMA内存就可以为buddy所申请。在伙伴系统中migratetype为movable并且分配flag带CMA，可以从CMA分配内存：
3.2CMA分配流程
在阅读cma分配流程代码前，我们先看下它的函数调用流程，后面将通过源码对流程及各个函数进行剖析。
3.2.1 cma_alloc
@1 bitmap的打算，紧张是获取bimap最大的可用bit数(bitmap_maxno)，这次分配须要多大的bitmap(bitmap_count)等。
@2 根据上面打算得到的bitmap信息，从bitmap中找到一块空闲的位置。
@3 一些特殊情形（在后面会讲到）常常会导致CMA分配失落败，当分配返回EBUSY时，须要msleep(100)再retry，默认会retry 5次。
@4 将要分配的页面的对应bitmap先置位为1，表示已经分配了。
@5 利用alloc_config_range来进行内存分配，在后面节详细剖析。
@6 分配失落败则打消掉bitmap。
3.2.2 内核中的“批处理”：LRU缓存和PCP缓存
在剖析alloc_config_range之前，先插讲两个知识点LRU缓存和PCP缓存，在阅读内核源码中，我们会创造内核很喜好利用一些“批处理”的方法来提升效率，减少一些拿锁开销。
1.LRU 缓存
经典的LRU（Least Rencntly Used）链表算法如下图：
注：详细的LRU算法先容可以参考内核工匠之前的文章：kswapd先容
新分配的页面不断地加入ACTIVE LRU链表中，同时ACTIVE LRU链表也不断地取出将页面放入 INACTIVE LRU链表。链表中的锁（pgdat->lru_lock）竞争力度是非常强烈的，如果页面转移是一个一个进行的，那对锁的竞争将会十分严重。
为了改进这种情形，内核加入了一个 PER-CPU的 LRU缓存（用 struct pagevec 表示），页面要加入LRU链表会先放入当前 CPU 的LRU缓存 中，直到LRU缓已经满了（一样平常为15个页面），再获取lru_lock，一次性将这些页面批量放入LRU链表。
2.PCP(PER-CPU PAGES)缓存
由于内存页面属于公共资源，系统中频繁分配开释页面，会由于得到开释锁（zone->lock），CPU之间的同步操作产生大量花费。同样为了改进这种情形，内核加入了per cpu page 缓存（struct per_cpu_pages表示），每个CPU都从Buddy批发申请少量的页面存放在本地。当系统须要申请内存时，优先从PCP缓存拿，用完了再从buddy批发。开释时也优先放回该PCP缓存，缓存满了再放回buddy系统。
内核之前只支持order=0的PCP，社区最新已经有补丁可以支持order>0的per-cpu。
3.2.3 alloc_config_range函数：
连续看cma_alloc流程的alloc_config_range要干哪些事情：
简而言之，目的便是想从一块“脏的”连续内存块（已经被各种类型的内存利用），得到一块干净的连续内存块，要么是回收掉，要么是迁移走，末了将这块干净的连续内存返回给调用者利用，如下图：
走读下代码：
@1 start_isolate_page_range：将目标内存块的pageblock 的迁移类型由MIGRATE_CMA 变更为 MIGRATE_ISOLATE。由于buddy系统不会从 MIGRATE_ISOLATE 迁移类型的pageblock 分配页面，可以防止在cma分配过程中，这些页面又被人从Buddy分走。
@2 drain_all_pages：回收per-cpu pages，前面已经有先容过PCP，回收过程须要先将放在PCP缓存页面归还给Buddy。
@3 __alloc_contig_migrate_range：将目标内存块已利用的页面进行迁移处理，迁移过程便是将页面内容复制到其他内存区域，并更新对该页面的引用。
@3.1 lru_cache_disable: 由于在LRU缓存的页面是无法迁移的，须要先将pagevec页面刷到LRU，即将准备添加到LRU链表上，却还未加入LRU的页面(还待在LRU缓存)添加到LRU上，并关闭LRU缓存功能。
@3.2 isolate_migratepages_range 隔离要分配区域已经被Buddy利用的page，存放到cc的链表中，返回的是末了扫描并处理的页框号。这里隔离紧张是防止后续迁移过程，page被开释或者被LRU回收路径利用。
@3.3 reclaim_clean_pages_from_list：对付干净的文件页，直接管受接收即可。
@3.4 migrate_pages：该函数是页面迁移在内核态的紧张接口，内核中涉及到页面迁移的功能大都会调到，它把可移动的物理页迁移到一个新分配的页面。
不才一节详细先容它。
@3.5 lru_cache_enable迁移过程完成，重新使能LRU PAGEVEC
@4.undo_isolate_page_range: @1的逆过程pageblock的迁移类型从 MIGRATE_ISOLATE 规复为 MIGRATE_CMA。
末了将这些页面返回给调用者。
3.3 CMA开释流程
cma_release开释CMA内存的代码很大略，便是把页面重新free给Buddy和清楚到cma的bitmap分配标识，这里直接贴一下代码：
四、页面迁移
系统要利用CMA区域的内存，内存上的页面必须是可迁移的，这样子当设备要利用CMA时页面才能迁移走，那么哪些页面可以迁移呢？有两种类型：
1. LRU上的页面，LRU链表上的页面为用户进程地址空间映射的页面，如匿名页和文件页，都是从buddy分配器migrate type为movable的pageblock上分来的。
2. 非LRU上，但是是movable页面。非LRU的页面常日是为kernel space分配的page，要实现迁移须要驱动实现page->mapping->a_ops中的干系方法。比如我们常见的zsmalloc内存分配器的页面就支持迁移。
migrate_pages()是页面迁移在内核态的紧张接口，内核中涉及到页面迁移的功能大都会调到它。如下图，migrate_pages()无非是要分配一个新的页面，断开旧页面的映射关系，重新简历映射到新的页面，并且要拷贝旧页面的内容到新页面、新页面的struct page属性要和旧页面设置得一样，末了开释旧的页面。下面来阅读下它的源码。
4.1 migrate_pages：
migrate_pages函数和参数：
from: 准备迁移页面的链表
get_new_page：申请新页面函数的指针
putnew_page：开释新页面函数的指针
private：传给get_new_page的参数，CMA这里没有利用到传NULL
mode：迁移模式，CMA的迁移模式会设置为MIGRATE_SYNC。共有下面几种：
reason：迁移缘故原由，记录是什么功能触发了迁移的行为。由于内核许多路径都须要用migrate_pages来迁移比如还有内存规整、热插拔等。CMA通报的为MR_CONTIG_RANG，表示调用alloc_contig_range()分配连续内存。
再看migrate_pages代码，它遍历 from链表，对每个page调用unmap_and_move来实现迁移处理。
4.2 unmap_and_move
unmap_and_move函数的参数同migrate_pages千篇一律，它调用get_new_page分配一个新页面，然后利用__unmap_and_move迁移页面到这个新分配的页面中，我们紧张看下__unmap_and_move
4.3 __unmap_and_move：
@1考试测验获取old page的页面锁PG_locked，若页面已经被其它进程持有了锁，则这里会考试测验获取锁失落败，对付MIGRATE_ASYNC模式的为异步迁移拿不到锁就直接跳过此页面。CMA迁移模式为MIGRATE_SYNC，这里一定利用lock_page一定要等到锁。
@2处理正在回写的页面，根据迁移模式判断是否等待页面回写完成。MIGRATE_SYNC_LIGHT和MIGRATE_ASYNC不等待，cma迁移模式为MIGRATE_SYNC，会调用wait_on_page_writeback()函数等待页面回写完成。
@3 对付匿名页，为了防止迁移过程anon_vma数据构造被开释了，须要利用page_get_anon_vma增加anon_vma->refcount引用计数。
@4 获取new page的页面锁PG_locked，正常情形都能获取到。
@5 判断这个页面是否属于非LRU页面，
如果页面为非LRU页面，则通过调用move_to_new_page来处理，该函数会回调驱动的miratepage函数来进行页面迁移。
如果是LRU页面，连续实行@6
@6 通过page_mapped()判断是否有用户PTE映射了改页面。如果有则调用try_to_unmap()，通过反向映射机制解除old page所有干系的PTE。
@7 调用move_to_new_page，拷贝old page的内容和struct page属性数据到new page。对付LRU页面 move_to_new_page是通过调用migrate_page做了两件事：复制struct page的属性和页面内容。
@8对页表进行迁移：remove_migration_ptes通过反向映射机制建立new page到进程的映射关系。
@9 迁移完成开释old、new页面的PG_locked，当然对付匿名页我们也要put_anon_vma减少的anon_vma->refcount引用计数
@10 对付非LRU页面，调用put_page，开释old page引用计数(_refcount减1)
对付传统LRU putback_lru_page把newpage添加到LRU链表中。
4.4 move_to_new_page
在@5和@7中，非LRU和LRU页面都是通过move_to_new_page来复制页面，我们来看下他的实现：
对付非LRU页面，该函数会回调驱动的miratepage函数来进行页面迁移
比如在zsmalloc内存分配器会注册迁移回调函数，迁移流程这里会调用到zsmalloc的zs_page_migrate来迁移其申请的页面。zsmalloc内存分配器这里就不展开讲了，有兴趣的读者可以阅读zsmalloc的源码。
2.对付LRU页面，调用migrate_page做了两件事：复制struct page的属性和页面内容。
@7.1 struct page属性的复制：
migrate_page_move_mapping 要先检讨page的refcount是否符合预期，符合后之后会复制页面的映射数据，比如page->index、page->mapping以及PG_swapbacked
这里顺带提一下refcount：refcount是struct page中重的引用计数，用来表示内核中引用改页面的次数。当refcount=0，表示该页面为空闲页面或即将要被开释的页面。当refcount的值>0，表示该页面已经被分配了且内核正在利用，暂时不会被开释。
内核中利用get_page、pin_user_pages、get_user_pages等函数来增加_refcount的引用计数，可以防止在进行某些操作过程（比如添加入LRU）页面被其它路径开释了，同时他也会导致refcount不符合预期，也便是在这里不能迁移。
@7.2 page页面内容的复制：
copy_highpage就很大略了，利用kmap映射两个页面，再将旧页面的内存复制到新的页面。
@7.3 migrate_page_states用来复制页面的flag，如PG_dirty，PG_XXX等标志位，也是属于struct page属性的复制。
4.5 小结：
全体迁移过程已经剖析完，画出流程图如下，
五、总结
从上面章节剖析，我们可以看到CMA的设计都是环绕这两点来做的：
1. 平时设备驱动不用时，CMA内存交给Buddy管理，这是在初始化流程cma_init_reserved_areas()或cma_release()来实现的。
2.设备驱动要利用时，通过cma_alloc来申请物理连续的CMA内存。对付已经在Buddy被APP或者内核movable分配走了的页面，要通过回收或迁移将这块内存清理“干净”，末了将这块物理连续“干净”的内存返回给设备驱动利用。核心实现在alloc_config_range()和migrate_pages()函数。
参考⽂献
1. 本⽂引⽤的和解读的代码都来⾃kernel-5.4https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/?h=v5.4.234
2. 《奔跑吧Linux内核》
3. 宋宝华：论Linux的页迁移（Page Migration）完全版:
https://blog.csdn.net/21cnbao/article/details/108067917
