CMA技术原理分析

　　前言
　　本文介绍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