FreeBSD Kernel-VM System FreeBSD Kernel-VM System1. VM Objects每个用户进程都看到一个单独的、私有的、连续的VM地址空间。该空间包含了不同种类的内存对象。程序的代码段和数据段实际上是一个内存映射的文件，代码段只读，数据段写时复制（copy-on-write）， BSS段按需分配，并且填充 0 （demand zero page fill）。任意文件也可以被映射到地址空间，如共享库。对于一个写时复制的基本页，当它被加载到虚拟内存空间中，只初始化内存映射，并在之后直接返回程序的二进制段。允许VM系统可以释放或者重用这个页面，并在晚些时候把它再加载回来。当进程修改这些数据时，VM系统必须为进程提供一份私有的复制。因为这个私有复制已经被修改过了，VM系统可能不会释放它，因为以后无法恢复。当发生fork系统调用时，复杂性会进一步增加，两个进程都有自己的私有地址空间。显然，在fork发生时制作完整的内存副本是非常不优雅的，FreeBSD通过分层的VM对象模型管理这些内容。原始的程序文件是最低的VM对象层。当进程启动后，VM系统创建一个对象层AA表示可以从物理介质调入调出的文件页面。从磁盘调入是正常操作，但是我们往往不想覆写可执行程序，因此VM系统创建一个由Swap提供物理支持的对象层B当第一次发生写操作时，在B中创建一个新的页面，该页面的内容从A初始化而来，该页面可以调度到swap设备上。当程序 fork 时，VM系统创建两个新的对象层：C1和C2，其中C1是父进程、C2是子进程在此情况下，当B中的一个页面被父进程修改，则该进程触发一个COW错误，并在C1中复制这个页面，并把原始的页面留存在B中。当子进程修改同一个页面时，也会触发一个COW错误，并在C2中复制这个页面。此时原始的页面在B中已经完全隐去了，当B不代表真实文件时，可能会被销毁，然而FreeBSD没有做这种优化。假设此时，子进程执行了exec()，它的当前地址空间会被代表新文件的新地址空间替换，此时C2被破坏。此时B只有一个子层，并且对B的访问全部都会通过C1，因此B和C1会折叠在一起，同时存在与B和C1的页面会在这种过程中被删除。这种模型带来了一些问题，第一个是VM对象栈很深，会导致触发错误的时候扫描时间。第二个问题是可以能会在对象栈深处遇到死页面、不可访问的页面。（凭我理解，死页应该是永远不会被访问到的页面，比如当进程A执行完毕，进程B永远不会访问到数据A'）。FreeBSD 提供了一种名为 All Shadowed Case 的特殊优化来解决这种过深层栈导致的问题。如果C1或C2导致的COW错误已经足以完全隐藏B中的层，以C1为例，我们就可以让C1跳过B，变为C1-> A和C2->B->A，此时B只有一个子层引用（C2），B和C2可以被折叠到一起，表现得结果就是B被完全删除。

Linux Kernel-Zpool 接口阅读 Linux Kernel-Zpool 接口阅读最近还是在做zswap的迁移，需要整理一下zpool的接口功能，以决定是迁移过去一个现成的还是自己实现一个简单的。1 Zpool作用Zpool只是一个接口层，由zbud、zsmalloc等进行具体实现。Zpool提供了一个内存池，用以存放被压缩的内存。因为它是一个接口，其实我们只需要简单的关注注册数据结构，就能了解到它的一些关键作用。2 Driver Structstruct zpool_driver { char *type; struct module *owner; atomic_t refcount; struct list_head list; void *(*create)(const char *name, gfp_t gfp, const struct zpool_ops *ops, struct zpool *zpool); void (*destroy)(void *pool); bool malloc_support_movable; int (*malloc)(void *pool, size_t size, gfp_t gfp, unsigned long *handle); void (*free)(void *pool, unsigned long handle); int (*shrink)(void *pool, unsigned int pages, unsigned int *reclaimed); bool sleep_mapped; void *(*map)(void *pool, unsigned long handle, enum zpool_mapmode mm); void (*unmap)(void *pool, unsigned long handle); u64 (*total_size)(void *pool); };refcount、list的作用都是字面意思。Type是当前driver的名字，索引driver的时候会用到。下面的函数是zpool后端提供给接口的实现，我们会在下一节里介绍其作用。3 暴露接口3.1 zpool_register_drivervoid zpool_register_driver(struct zpool_driver *driver); int zpool_unregister_driver(struct zpool_driver *driver)该函数暴露给所有zpool的实现，由他们在启动时注册。该函数初始化了引用计数、将被注册的driver加入到zpool的链表中。与其相对应的是zpool_unregister_driver，注销driver该接口评估为不需要迁移。3.2 zpool_get_driverstatic struct zpool_driver *zpool_get_driver(const char *type) static void zpool_put_driver(struct zpool_driver *driver)给定一个zpool驱动名字，返回对应的zpool_driver。并且增加对应driver的引用计数。与其相对应的是zpool_put_driver该接口评估为不需要迁移。3.3 zpool_has_pool、zpool_create_pool、zpool_destry_poolbool zpool_has_pool(char *type) struct zpool *zpool_create_pool(const char *type, const char *name, gfp_t gfp, const struct zpool_ops *ops) void zpool_destroy_pool(struct zpool *zpool)分别承担检测给定的driver是否可用、创建一个指定类型的zpool和销毁一个已经存在的zpool。该接口评估为不需要迁移3.4 zpool_malloc_support_movablebool zpool_malloc_support_movable(struct zpool *zpool)返回driver是否支持迁移的字段，评估为不需要迁移。3.5 driver实现函数3.5.1 zpool_malloc、zpool_free、zpool_shrinkint zpool_malloc(struct zpool *zpool, size_t size, gfp_t gfp, unsigned long *handle) void zpool_free(struct zpool *zpool, unsigned long handle) int zpool_shrink(struct zpool *zpool, unsigned int pages, unsigned int *reclaimed)在给定的zpool中申请大小为size的空间，并把申请得到的句柄放在handle中在给定的zpool中释放给定的handle的空间。zpool_shrink可能未被实现，如果实现，尝试驱逐当前正在使用的句柄。3.5.2 zpool_map_handle、zpool_unmap_handlevoid *zpool_map_handle(struct zpool *zpool, unsigned long handle, enum zpool_mapmode mapmode) void zpool_unmap_handle(struct zpool *zpool, unsigned long handle)根据给定的pool和handle，映射到连续的地址上取消映射，解锁相关的锁3.5.3 zpool_get_total_sizeu64 zpool_get_total_size(struct zpool *zpool)获取zpool所占用的内存空间

Linux Kernel-THP阅读分析[Hang up] THP阅读分析[WIP]本文由于工作优先级原因暂时搁置，专心转向zswap// TODO[x] 配置源码阅读环境 第三部分-Linux源码阅读环境[ ] 理清如下几个先决问题[x] 什么是THP？THP要做什么？[ ] 为什么在虚拟化和嵌套页表的情况下，THP对TLB和TLB miss的优化更明显[x] THP和HP的相关性与区别[ ] THP和HugeTLB的相关性与区别[ ] 梳理THP相关核心流程[x] khugepaged守护进程如何工作？[x] khugepaged与huge_memory关系如何？[ ] huge_memory如何管理大页面，更一般的，理清下面两个问题[ ] 一次内存访问中发生了什么[ ] 一次页错误中发生了什么[ ] 梳理THP相关核心数据结构[ ] 理清如下几个逻辑问题[ ] 一个mm是管理一个进程内存空间的数据结构？核心代码：huge_memory.ckhugepaged.c官方文档：Transparent Hugepage Support概述 （暂时性的，不一定正确）Hugepage：现代操作系统使用的页式内存管理通常以4K为一个标准页面。在内存越来越大的今天，4K大小的页面对于使用大量内存的应用会产生一些问题，即大量产生的缺页中断。大量的缺页中断会带来两个问题 1. 进入内核的次数更多，带来更多的切换上下文开销。 2. 带来更多的TLB Miss，这也是Hugepage优化的主要问题。 对于问题a，大页带来的性能优化可能较低。一方面更大的页面要求在一次页错误中复制更多的内容。另一方面，进出内核的频率降低只在内存映射的生命周期内第一次访存时才重要。对于问题b，因为TLB的容量是有限的，更大的页面也代表着更少的页面，这会带来两点好处 1. TLB miss会变快 2. 一个TLB表项可以映射更大的内存，来减少TLB miss THP：THP和Hugepage的区别是：Hugepage是一个操作系统管理的、用户显式请求的机制，THP是操作系统自动的，对用户透明的行为。THP无需用户修改代码，具有更高的普适性。khugepaged负责合并，huge_memory.c中的函数负责管理透过现象看本质，这是一种用单页面大小和扫描时间换系统整体效率的机制部分概念/缩写介绍[WIP]页表条目现在的Linux内核采用四级页表目录的方式，分别为PGD ：Page Global DirectoryPUD ：Page Upper DirectoryPMD ：Page Middle DirectoryPTE ：Page Table Entry来复习下基础：每个进程都有自己独立的PGD，虚拟地址的从高到底的k位（典型的是9，最低12位是页框内地址，共48位的地址）分别用来索引PGD（在PGD中找到这个地址对应的PUD）、索引PUD、索引PMD、索引PTE进而找到自己对应的物理页框，最低几位在该页框中索引具体的内存地址。PUD、PMD和PTE的最低位是存储是否有效的标志位。其中PTE指示页框的是48...12这36位。THP运转流程-合并概述在系统启动时，内核会启动khugepaged守护进程，该进程启动一个核心循环，扫描系统中的页面，检测是否有多个连续的页面可以合并为一个透明大页（事实上，我认为不是任意连续2M页面，而必须是已经存在的PMD表项所对应的2M页面，待确认）。当它发现了可以合并的页面后进行大量的检查操作，然后进入合并函数。先进行申请和double-check，移除CPU中的TLB对应表项，复制巨页内容，更新相关参数。khugepaged如何初始化在hugememory.c中，有一个被subsys_initcall注册的初始化函数：hugepage_init, 该函数调用了两个khugepaged相关的函数：khugepaged_init 和 start_stop_khugepaged，在此处，我们暂时先不关心其他的初始化流程，把它们放到管理中去考虑，先只看khugepaged相关的部分khugepaged_init申请一段slab内存，初始化四个参数常量 HPAGE_PMD_NR 根据它的定义，我推测它在数量上和一个HPAGE所含的一般页面数量相等(512)khugepaged_pages_to_scan : 每次扫描页面的数量，默认为 512 * 8khugepaged_max_ptes_none：最多有多少个页表项是空页面（存疑）khugepaged_max_ptes_swap：最多有多少个页面在swap中未被映射，默认是512/8khugepaged_max_ptes_shared：最多有多少页面是被共享的，默认是512/2start_stop_khugepaged获取互斥锁，检测hugepage是否开启了，若开启了则检查static变量khugepaged_thread，存在则关闭该线程启动一个内核线程，目标函数为khugepaged函数，该函数为khugepaged扫描的核心循环若有错误，清理并释放锁khugepaged如何扫描khugepaged设置一些状态，把当前线程优先级变低，进入循环如果收到KTHREAD_SHOULD_STOP，则退出调用khugepaged_do_scan函数调用khugepaged_wait_work函数，进入等待根据khugepaged_scan_sleep_millisecs，转换成中断次数，进入等待获取自旋锁，进行一些清理工作，释放锁khugepaged_do_scan该函数有一个参数：khugepaged_collapse_control，只透传给下层初始化一些变量progress：记录THP扫描进度pages：读取init中初始化的khugepaged_pages_to_scanwait：布尔量，用于下面过程的重试result：记录扫描结果的状态调用lru_add_drain_all函数，把脏页从LRU列表干掉（加到写回缓冲区）进入一个无限循环，降低自己的优先级检查是否要退出获取一个自旋锁如果当前kugepaged_scan的mm_slot字段为空，累加“pass_through_head”计数器如果kugepaged_scan的mm_head不为空，且pass_through_head < 2（我理解就是第一次进入，记录一个TODO，为什么要把0的情况算进去，即什么情况下存在刚进入do_scan函数但是mm_slot不为空）调用kugepaged_scan_mm_slot函数，并把结果累加给progress变量，更新result变量kugepaged_scan_mm_slotstatic unsigned int khugepaged_scan_mm_slot(unsigned int pages, int *result, struct collapse_control *cc) __releases(&khugepaged_mm_lock) __acquires(&khugepaged_mm_lock)该函数是scan步骤的关键函数，它接受的参数包括：pages：要扫描的页数result：结果指针cc：透传来的 collapse_control结构该函数首先进行一些初始化与验证操作，包括对参数与锁的断言，对 result 的初始化检测是否已经有正在进行的扫描，如果有，获取相应的 mm_slot和 slot（扫描当前头部未扫描完的进程），如果没有，初始化一组新的 slot 和 mm_slot（扫描下一个进程）khugepaged如何合并kugepaged_collapse_pte_mapped_thps进行一些验证操作与锁的获取便利当前 slot 的所有 Hugepage 的页表项，调用collapse_pte_mapped_thp函数对这些页表项进行合并操作。collapse_pte_mapped_thpint collapse_pte_mapped_thp(struct mm_struct *mm, unsigned long addr, bool install_pmd)该函数有三个参数● mm：将要被聚合的进程地址空间● addr：要发生聚合的地址● install_pmd：布尔，决定是否应当设置一个 PMD 表项该函数检测是否一个 PMD 中的所有 PTE 表项都指向了正确的 THP，如果是的话，撤销相关的页表项，这样 THP 可以触发一个新的页错误，使得使用一个 huge PMD 映射这个 THP把地址按掩码对齐，获取当前地址对应的 vma，获取锁。调用find_pmd_or_thp_or_none 查找页表中对应当前地址的 PMD 或是 THP 或是空指针。如果当前页面已经被 PMD 映射，返回。如果所有检测都没有命中，返回 SCAN_SUCCEED。// TODO:这些检测都是什么检查获取的 vma 是否正确，如果不正确，返回 VMA_CHECK，表示需要检查虚拟内存区域到此为止，我门已经成功的把页缓存中的本地页面替换成了单个的 hugepage，如果 mm 触发缺页错误，当前 hugepage 就会被一个 PMD 映射，而不考虑 sysfs 中对 THP 的设置是什么样的。检查是否存在使用 userfaultfd_wp的情况，如果是，返回通过 find_lock_page 尝试获取页面，且验证页面是一个 Hugepage，并且检测页面是否为一个复合页面。如果不是 Hugepage 或者页面复合阶数和 HPAGE_PMD_ORDER不相等，则 drop_hpage。接下来操作页表，首先获取当前 vma 的锁、当前文件映射的锁、当前虚拟地址对应 PTE 的锁。STEP1：检测是否所有的已映射页表项指向了期望的 Hugepage● 遍历当前 PMD 对应的所有 PTE● 如果当前 PTE 是空，跳过● 如果当前 PTE 没有物理页映射，发生了非法情况，终止（swapped out）● 获取 PTE 指向的物理页面 ● 检测是否是设备内存，如果是，WARN，并设置页面指针为 NULL● 检测 PTE 指向的页面和期望的巨页对应的小页面是否一致，不一致则终止● 累加计数器STEP2：对小页面的反向映射进行调整● 遍历当前 HugePage 的页表项● 如果当前 PTE 是空的，跳过● 获取当前物理页，检测是否是设备内存，若是 WARN 并 abort● 调用 page_remove_rmap，从页的反向映射表中移除页面与 VMA 的映射关系● 解锁 PTE 的映射STEP3、4：设置正确的引用计数、移除 PTE 条目● 如果 count 不是 0，说明签名的步骤中找到了一些映射到 hpage 的 PTE 条目，折叠后会删除 PTE，所以更新 hpage 的引用计数、把 vma 的 mm 计数器也减掉相应的数量● 如果有匿名 vma，获取锁，然后调用 collapse_and_free_pmd折叠并释放 haddr 处的 PMD 条目STEP5：● 根据 install_pmd 参数的情况，决定是否要安装 PMD，若 PMD 安装成功或者不需要，则返回 SCAN_SUCCEEDcollapse_and_free_pmdhugepage_vma_checkkhugepaged的重要数据结构khugepagd_scanstruct khugepaged_scan { struct list_head mm_head; struct khugepaged_mm_slot *mm_slot; unsigned long address; }; 这个数据结构是一个指引扫描的“光标”，跟踪khugepaged扫描时的状态。该数据结构只会有一个全局实例。mm_head：要扫描的mm的头部，维护需要扫描内存区的链表mm_slot：指向当前正在扫描的kuhugepaged_mm_slotaddress：是mm_slot内下一个即将被扫描的地址khugepaged_mm_slotstruct khugepaged_mm_slot { struct mm_slot slot; /* pte-mapped THP in this mm */ int nr_pte_mapped_thp; unsigned long pte_mapped_thp[MAX_PTE_MAPPED_THP]; };这个数据结构用来跟踪正在扫描的每个内存区域slot:依赖的一个外部数据结构，实现了从mm到mm_slot的哈希查找nr_pte_mapped_thp:表示在该mm中已经被映射的THP的数量pte_mapped_thp:存放该mm中已映射的THP的地址在我的理解中，khugepaged_scan指导scan工作，而其中的mm_slot指向当前正在被扫描的那个进程的mm_slot，(一个进程通常只有一个kugepaged_mm_slot, 暂不确定什么情况下会有多个)THP运转流程-管理

Linux Kernel-Zswap 2.上下层依赖 上下层依赖重要数据结构zswap_poolstruct zswap_pool { // 挂 zswap 所用的内存池 struct zpool *zpool; struct crypto_acomp_ctx __percpu *acomp_ctx; struct kref kref; struct list_head list; struct work_struct release_work; struct work_struct shrink_work; struct hlist_node node; char tfm_name[CRYPTO_MAX_ALG_NAME]; };struct zpool *zpool：指向 zpool 对象的指针，用于表示当前 zswap 池所对应的 zpool。可能需要基于 uma 进一步封装实现。struct crypto_acomp_ctx __percpu *acomp_ctx：指向压缩算法。struct crypto_acomp_ctx { struct crypto_acomp *acomp; struct acomp_req *req; struct crypto_wait wait; u8 *dstmem; struct mutex *mutex; };struct kref kref：用于实现引用计数技术的 kref 对象，用于管理 zswap 池对象的生命周期。当一个 zswap 池对象被创建时，其引用计数值初始化为 1；当该对象被使用时，其引用计数值增加；当不再需要该对象时，其引用计数值减少，当引用计数值降为 0 时，该对象将会被释放。 FreeBSD 支持 refcount 特性，我们认为是可以迁移的。struct list_head list：用于实现链表的 list_head 结构体，用于将当前 zswap 池对象添加到 zswap 的池列表中。普通链表头，可以迁移。struct work_struct release_work：表示一个工作队列对象，用于异步释放当前 zswap 池对象。在该工作队列中执行的操作会在一个单独的内核线程上运行，从而避免阻塞当前进程。struct work_struct shrink_work：表示一个工作队列对象，用于在 zswap 池中的页面数量超过一定阈值时触发缩减操作。该工作队列也是异步执行的，在单独的内核线程上运行。FreeBSD 的 taskqueue 和 workqueue类似，都支持异步调用，可以迁移。struct hlist_node node：表示一个哈希表节点，用于将当前 zswap 池对象添加到 zswap 的池哈希表中。char tfm_name[CRYPTO_MAX_ALG_NAME]：表示保存压缩算法名称的字符数组，用于指定 zswap 池所使用的压缩算法名称。在进行前端交换时，内核将会根据该名称来查找相应的压缩算法，并使用其进行数据压缩处理。zswap_entrystruct zswap_entry { struct rb_node rbnode; pgoff_t offset; int refcount; unsigned int length; struct zswap_pool *pool; union { unsigned long handle; unsigned long value; }; struct obj_cgroup *objcg; };struct zswap_entry 表示单个被压缩页面元数据。struct rb_node rbnode：红黑树节点pgoff_t offset：表示该页面在交换分区中的偏移量，也是红黑树的 idxint refcount：表示对该页面的引用计数，用于保证在页面同时被加载、失效和写回等操作时不会出现条件竞争，从而避免页面被过早地释放。unsigned int length：被压缩后页面长度。struct zswap_pool *pool：标识该页面所属的 zswap 池。union：a) unsigned long handle：压缩页面数据句柄。这个是 zpool 用的。b) unsigned long value：内容相同的空白页面填充值。struct obj_cgroup *objcg：指向 obj_cgroup 结构体的指针，用于标识该页面所属的 cgroup（如果按 cgroup 进行回收）。zswap_treestruct zswap_tree { struct rb_root rbroot; spinlock_t lock; };这个结构体代表了一个 zswap 树的元信息，分别有一个红黑树的根和一个自旋锁。一点对 zswap_pool\entry\tree的理解enrty 是页面单元，包括该页在内存中的位置大小等信息，pool是实际存储 entry 元信息对应页面压缩后数据的内存池，tree 维护了一颗平衡树，用于找到对应 type+offset 的元信息entry。zswap_header一个 ulong其他全局变量一般为 config 或者全局状态量，易于迁移。page篇幅过长，Linux 的基础页面数据结构重要依赖模块内存管理池 zpoolzpool 是 linux 的一类内存管理 API，是 zswap 所依赖的最底层的数据结构。zswap_pool 通过 zpool 的各类内存管理工具，包括申请、映射、收缩等关键操作异步压缩 acompressacompress 是 linux crypto 下的模块，它提供了类似队列式的异步的压缩和解压缩能力同时，crypto 模块还提供了统一的同步方式swap 框架 frontswap提供了一种 swap 接口层，通过实现 frontswap 提供的函数指针，可以自定义swap 的实现方式有了 frontswap，我们只需要关注 swap 后端的设计，并向对应的初始化、存入、取出等接口实现逻辑、提供功能即可。frontswap 是zswap 最重要的依赖之一平衡树 rbtree维护 zswap_tree 的核心数据结构，保证插入和索引 offset 对应的页面的时候的复杂度。工作队列work_queue提供一个异步工作的机制，包括对 pool 的 shrink 和 release引用计数 kref需要一个引用计数器，主要是保证在 pool 和 entry被释放时的内存安全性锁与信号量主要需要关于自旋锁和互斥锁的 aquire/release的实现，避免线程竞争带来的各类安全和数据访问问题。原子操作一般依赖模块认为一般依赖模块仅是为了某些特性准备，不影响 swap 的关键流程scatterlist为了支持 acomp 的参数而依赖，属于间接依赖多 CPU 系列的宏和回调注册有的为了支持 CPU 热插拔事件、有的为了实现 acomp 在多 CPU 上的真并行kmem_cacheentry_cache 的底层申请与管理依赖于 kmem_cache，属于性能优化。

Linux Kernel-Zswap 3.迁移到FreeBSD思路 迁移 FreeBSD需求分析：FreeBSD 目前仅支持默认的Swap 操作，为了优化其表现，尝试设计一套类似于 zswap 的机制，使得在FreeBSD 中，当需要进行页面交换时可以把页面交换至硬盘的链路改为压缩后仍存放在内存中需要换入时，可以正确的解压缩页面并换回内存内存空间不足/达到设计的上限时，有合理的机制把当前压缩页面池中的内容踢出，放入硬盘兜底对于已放入硬盘的页面，有合理的机制在换入时可以找到。设计思路：对于 zswap 所依赖的大部分内容，FreeBSD 中都有相应的模块可以替代，部分可能需要进一步封装或 patch，如 zstd 之于acompress，uma 之于 zpool，但是有一个最核心的点 FreeBSD 没有支持，即 Frontswap。我们可以考虑这样的链路：→内核调用换出→Hook劫持至我们的 SwapHook→将相应页面压缩后放入压缩页面池→返回成功，若失败，继续正常的换出流程，否则返回。→内核调用换入→Hook劫持至我们的 SwapHook→寻找相应页面，若不存在，返回失败→解压相应页面，返回内容和成果。过程中的任意失败都会导致进入正常的换入流程。FreeBSD Swap 是如何工作的我们假定从缺页错误开始，一直到如何调用 Swap开始，对我们都是透明的，（好处是很多其他原因触发的缺页错误我们都无需关注）则：在换出时：调用 swap_pager_putpages()，传入参数包括object：指向虚拟内存对象的vm_object_t的指针ma：一个指向要换出的物理页面数组的指针count：ma 中物理页面的数量flags：操作行为rtvals：return values，存储每个换出页面的操作结果。assert 检查 ma 和 object 的一致性解锁 object通过调用方是否为 pageproc 和 VM_PAGER_PUT_SYNC 参数设置情况判断是否要一步操作初始化释放范围开始换出操作：循环处理要换出的每个页面，判断当前剩下的页面数量和单词 IO 可以操作的最大页面数量，判断本次循环要操作的数量获取一个异步写资源，设置 nsw_wcount_async获取本批次要写的页面的空间，为后面向 swap 设备写做准备如果没申请到需要的空间，释放 nsw_wcount_async，（如果为 1）唤醒其他等待的资源，设置本批次返回值为失败对当前虚拟内存对象上锁循环处理本批次的每个页面：赋值当前要处理的页面给 mreq 变量清除页面的 PGA SWAP FREE 标记建立一个元信息，包括当前页所在的 object、在 object 中的 index 和要存放到的 swap block 块号更新操作完成后释放的 swap 空间范围校验 dirty，确认是不是一个脏页设置 swaping 标志解锁这个虚拟内存对象为 buf 结构分配一个空间，使用 uma 获取校验、设置一些标志，我们暂时不关心设置缓冲大小、缓冲块号、页面信息和页数信息计数，把当前这些页面的返回值设为 VM_PAGER_PEND根据是否异步的情况，把对应 buf 发给 swp_pager_strategy函数，并决定是 wait 还是 continue由对应函数进行换出操作释放相关的页面、锁定对应的 object在换入时：调用 swap_pager_getpages()，传入参数包括object：指向虚拟内存对象的vm_object_t的指针ma：一个指向要换入的物理页面的指针count：ma 中物理页面的数量rbehind、rahead：当前页面之前和之后的页面数量锁定当前 object，调用 locked函数检查第一个页面是否在对象的 swap 空间中，并获取前后最多有多少页，如果不在，解锁并返回VM_PAGER_FAIL检查请求的页面数量是否超过设备上的页面范围判断当前 vm_obj 的标记，并根据 SPLIT 和 DEAD 的情况决定是否重新设置 maxahead 和 maxbehiendmaxahead：换入第一个页面后的连续可用页面数量同 ahead，换入页面前的根据 max 和 rahead、rbehind 决定实际要换入的页面范围，目的是排除已经在内存中的页面根据 ahead 和 behind，申请足够数量的页面，把这些页面标记为 VP0_SWAPINPROG根据实际申请到的页面数量，更新 rbehind、rahead 和 count对虚拟内存的页面增加引用计数通过 object 和 index 查询 swap 设备上的 swap 元信息。并 assert 相应页在 swap 设备上解锁 vm_object，为 buf 申请内存，并填充相关数据，具体数据和换出差不多计数把缓冲区和内核 PROC 关联调用 swp_pager_strategy()，把请求借助 buf 发送给 swap 设备锁定虚拟内存对象，while(swap_flag) Sleep 20s等换入操作结束。若超时，打印一些信息解锁对象，遍历页面，检查 valid 属性，如果有问题则返回 ERROR返回 OK经过对 FreeBSD Swap 流程的了解，我们发现除了在之前想到的对 swap 进行 Hook 之外，是否还存在一种方式：自定义一个虚拟的 Swap 设备，向 FreeBSD 注册实现支持blist_alloc()实现支持sw_strategy，接受 buf，执行相关操作。要求能确保在开启之后，该虚拟设备要在 swtailq 的第一位。这样做的好处是显而易见的：我们不必破坏或大量修改 swap 和内核本身，而实现一个虚拟设备驱动就可以完成相应的目标。并且，这其中的相关 flag 及策略判断，FreeBSD 都已经替我们做好了。无论使用在 swap 前 hook，还是使用驱动的方式，我们都有必要对这个 buf 结构体进行一定的了解，以便利用这个结构体的信息进行置换操作。bufbuf定义在 FreeBSD 的 /sys/buf.h中fxr.watson.org: sys/sys/buf.h我们借助源码和 FreeBSD 系统结构手册进行理解handbook这是一个非常庞大的结构体，我们尽量只挑选需要的字段进行理解。可以看到，在 buf 结构体中，有 struct vm_page *b_pages[]和caddr_t b_data依赖迁移：敲定 frontswap 的替代方式后，最重要的工作内容就是如何封装 FreeBSD 所拥有的依赖，使它能适应zswap 的需求，使得可以直接把 zswap 整个文件的核心逻辑都迁移过来或如何修改 zswap 对外部逻辑的调用，使得它能使用 FreeBSD 提供的能力为了合理的安排我的工作，我选择的工作路径是：数据结构迁移→按流程的函数迁移。具体选择封装还是修改视具体情况决定。在分点上自顶向下的递归解决所有依赖问题。数据结构迁移zswap_pool能力梳理：zswap_pool 主要提供了如下能力：提供一个底层数据结构 zpool，使得可以把压缩页面存入并获得 handle和 使用 handler取出对应页面对每个 CPU 提供一个异步压缩上下文，使得可以把数据传入，进行异步压缩和解压缩，此外，还可以提供自定义的压缩算法名字来注册这个异步压缩上下文。其中，这个上下文主要依赖了 crypto_acomp，包括使用它的压缩功能和同步功能。一个引用计数器，防止多线程出现的一些安全问题，保证pool不会被错误释放，并且在 ref 为 0 时可以释放。两个工作项，在需要释放或压缩的时候挂到队列中，进而完成异步的释放或压缩。一个链表头，保证可以 RCU 的遍历所有 zswap_pool现在，我们尝试逐一找到 FreeBSD 中可以支持相关能力的一些模块。底层内存池ZpoolFreeBSD 支持 UMA 内存架构，它实现了 Slab 内存池来管理内核内存的分配与释放，我将基于 UMA，尝试给出 Zpool 的替代方案。UPD：UMA 的 Slab 不支持任意大小的内存池，然而我们还是可以通过一些 Trick 来实现我们想要的东西，详情见 entry 的迁移。为了统一说法，我们会称内存池为 pool，内存池条目为 entry，即使在 FreeBSD 中它们似乎应该成为 zone 和 item。但是在直接出现 FreeBSD 源码的时候，我们选择使用源码说法。uma(9)申请pool：zpool的申请发生在zswap_pool_create() 函数中，它先通过 kzalloc 在内核中申请了一段用于存放 zpool 指针的内存，然后调用zpool_create_pool() 函数获得一个 pool，相关的参数如下：type : 指定使用的池类型，它由 Config 指定，默认为 z3fold。name：池名称，为 “zswap{num_of_pool}”gfp：指导内存分配的标志，这里为 不重试-不告警-允许内核进程回收ops：一些Hook 函数，这里是指导当池空间不足时，调用zswap_writeback_entry进行页面写回，会把需要写回的 handle 传递给该函数。再来看一下 uma 中内存池申请的函数定义name：无需变化size：可以支持设置，我们参考z3fold的内存大小设置，在典型的 4K 页面时可能会设置为 64KB 这个 size 应当是单个对象的 size，根据后面的妥协算法，我们目前采用 4K * 70%其余参数我们暂时认为无需设置当然，仅仅这样申请到了一个 pool（uma 中称为 zone，下同）还不够，我们发现 evict 这个 callback 函数没有用到。幸运的是，uma 提供了**uma**_**zone**_**set**_**maxaction**()函数，支持在 pool 已满并且申请新条目失败时回调。 这里给出了函数和其需要实现的回调函数的定义，看来我们可以非常方便的设置这个回调了。然而它和 zpool 的回调**还不太一样**，它只会返回已满的内存pool。 - 销毁 pool - uma要求在销毁 pool 前，必须释放所有的 entry，在这之后，我们就可以使用 `uma_zdestroy()`函数来释放所有内存 其余和 entry 相关的内存申请操作，在流程迁移里再讨论 异步工作队列 workqueue 与异步工作项 work_structFreeBSD 中，有和 workqueue 极其类似的机制 taskqueue。在 zswap 中，release 和 shrink 队列采用 INIT_WORK 注册工作队列和工作函数，区别是 shrink 预先创建了一个队列，而 release 直接 INIT ，注册到系统工作队列了。同时，shrink 采用 queue_work()方式调用 work，而 release 采用 schedule 方式调用 work，它们的区别是 queue_work会先挂队列，择机执行，而 release 会立即尝试执行。根据资料，这和它们的释放方式有关。但是幸运的是，在迁移过程中我们没有必要对这两种方式过度关心，首先要确保的是迁移的可行性。FreeBSD 采用 taskqueue_create来创建新的队列，主要参数包括队列名字和需要被调用的函数。在 taskqueue 被创建后调用 taskqueue_start_threads()等一系列函数来启动 taskqueue 的线程。采用 taskqueue_enqueue把任务添加到队列里，因此，我们的 work_struct可以直接被修改为 FreeBSD 中的 task。引用计数 kref引用计数作为操作系统中非常常见的功能，FreeBSD 中有类似的机制：refcount API在 zswap 中，主要包括非常基础的 init、put、get_if_not_zero等操作，幸运的是，FreeBSD 中都有类似的、以原子操作实现的功能，其函数名分别为：*refcount**_**init、refcount**_**relese和*refcount**_**acquire**_**if**_**not**_**zero**可以直接调用链表 list链表作为一种极其常用的数据结构，FreeBSD 中当然也有类似的机制：sys/queue.h下定义了 FreeBSD 所使用的链表们，在这里，我们需要一个双向链表。然而zswap使用的是基于 list 后封的 rcu 链表，包括list_for_each_entry_rcu、list_del_rcu、list_add_rcu等。rcu 是 linux 内核的一种机制，它解决了两类问题。reader 不需要在 writer 写时等待，数据一致性得到保证，不会出现半新半旧的情况。这样看，我们有两种方式对它进行迁移。不在乎 rcu 带来的性能优化，直接在链表相关访问前后加 rw 锁。这种方式简单易于移植，但是带来了很显然的性能劣化。使用 FreeBSD 提供的 SMP 机制，完成对 FreeBSD 链表的 rcu 封装。这里我想给出一个简单的基于 rw 锁的示例，（未验证，甚至未验证能否编译）#include <sys/queue.h> #include <sys/rwlock.h> struct data { int val; LIST_ENTRY(data) entries; }; struct rwlock list_rwlock; rw_init(&list_rwlock); LIST_HEAD(head_name, data) head; #define list_for_each_entry_rw(pos, head, member) \ rw_rlock(&list_rwlock); \ for ((pos) = LIST_FIRST((head)); (pos) != NULL; (pos) = LIST_NEXT((pos), member)) void sample() { struct data *p; list_for_each_entry_rw(p, &head, entries) { // read val } rw_runlock(&list_rwlock); }异步压缩 acompFreeBSD 的 crypto 部分可以实现类似acomp 的功能 comment：crypto 似乎要使用设备，暂时排除这种方法。，此外，zlib 库也支持压缩功能，我们主要关注如下内容根据不同的算法名字申请算法很遗憾，根据 FreeBSD 的文档，目前内核 Crypto 模块似乎只支持一种压缩算法，但是我们可以留下未来开发的可能。或者自己实现一些压缩算法。尽可能的支持多核并行压缩调用，如果不能，至少要实现压缩和解压缩功能。对于每个 pool 可以维护一个实例，单 pool 使用实例时要线程安全。快速了解zlib 的使用后，我想尝试如下的方式：ctx 结构struct ctx { z_stream compression_stream; z_stream decompression_stream; struct mtx mutex; };初始化：int ctx_init(struct ctx *ctx) { bzero(&ctx->compression_stream, sizeof(z_stream)); bzero(&ctx->decompression_stream, sizeof(z_stream)); int ret = deflateInit(&ctx->compression_stream, Z_DEFAULT_COMPRESSION); if (ret != Z_OK) { return ret; } ret = inflateInit(&ctx->decompression_stream); if (ret != Z_OK) { deflateEnd(&ctx->compression_stream); return ret; } // 初始化 mutex return Z_OK; }以压缩为例int compress_page(struct crypto_acomp_ctx *ctx, vm_page_t src) { // 映射 src page 到内存 为 src_addr // 申请 dst 空间 // 加锁 int ret = compress2(dst_addr, &dest_len, src_addr, PAGE_SIZE, Z_DEFAULT_COMPRESSION); mtx_unlock(&ctx->mutex); // 解除映射 // free 空间 return ret; }compress2 是同步过程，但是异步的工作队列给了我启发，我想我们可以不太麻烦的自己实现 Linux 内核对应的 crypto_acomp异步过程，步骤如下：ctx 扩充两个字段，一个是工作项 task，一个是等待信号 wait需要压缩时，工作项挂队列，并 suggest 立即执行主线程等待 wait压缩完毕的 callback 中，通过container_of找到对应的结构，进而释放 wait这样就实现了一个简易的异步过程。然而，还是有个工作项需要确认：[ ] 工作队列的异步模式，能否真的满足原 zswap 的构思，即单核同步，多核异步并行？但是我们现在已经完成了这个内容，暂时就把它放在这里最后看吧。### 至此，我想已经基本上给出了 zswap_pool的可行迁移方案，然而由于对 FreeBSD 各内核 API 的了解不够，可能还要进一步学习 FreeBSD 的内核原来来确认确实能满足我们的工作。### 压缩页面表项 zswap_entry暂时忽略了 cgroup 特性，可以作为一个 TODO。struct z_entry_key { vm_object_t object; vm_pindex_t pindex; }; struct zswap_entry { RB_ENTRY(zswap_entry) rbnode; struct z_entry_key rbkey; int refcount; unsigned int length; struct zswap_pool *pool; //uma zone uintptr_t handle; };static inline int zswap_entry_key_cmp(struct z_entry_key k1, struct z_entry_key k2) { /* Compare the vm_object */ if (k1.object < k2.object) return -1; else if (k1.object > k2.object) return 1; /* Compare the pindex */ return k1.pindex < k2.pindex ? -1 : (k1.pindex > k2.pindex ? 1 : 0); } struct zswap_entry *zswap_rb_find_entry(vm_object_t object, vm_pindex_t pindex) { struct rb_node *node = zswap_rb_root.rb_node; int result; while (node) { struct zswap_entry *entry = container_of(node, struct zswap_entry, rb_node); struct z_entry_key key = {.object = object, .pindex = pindex}; result = zswap_entry_key_cmp(key, entry->key); if (result < 0) node = node->rb_left; else if (result > 0) node = node->rb_right; else return entry; } /* Entry not found */ return NULL; }对于 RB_Tree，我想没有必要过多的描述，FreeBSD 内核中已经有红黑树相关的 API 了。不幸的是，在这一步我发现 uma 的 zone 不支持任意大小的块的申请。一点其他的思考：我猜测 zpool 底层应该也是固定大小的块的，当我们需要任意大小的内容时，zpool 提供了一层映射封装，即通过 handle 来把各个分散的块组装起来，这样我猜测 zpool 一定也会浪费一定的空间。---### 补充：关于 z3fold 内存管理在了解 z3fold 之后，我验证了之前的猜想，z3fold 底层也是固定的页面大小，但是 z3fold 把一个页面分为多个固定大小的 chunks，当收到新的内存分配请求时，z3fold 根据请求的大小计算需要 chunks 的数量，尝试在现有的页面中找到足够的连续空闲 chunks，如果找不到，分配一个新的页面容纳请求。---因此，要么我们自定义一个支持任意大小申请、支持失败回调的内存池要么就要规定一个压缩比率，假设我们把压缩率不足 70%的所有页面都直接 swap 到外部设备，压缩率高于 70%的页都放入内存池，我们就可以使用固定 PAGE_SIZE * 70% 的 zone 来实现这个功能了（考虑到我们的目的是 CPU 时间换 IO 时间，我觉得均摊意义上对 CPU 的浪费是可以接受的）在我的设计中，我将会选择第二种方式，当然，70% 这个阈值仍需要实践后来确定，这就是后话了。### 树根结构 zswap_tree树根没什么太多好说的，存放 rb_tree的根和访问树的互斥量。前面都有提到了。到此为止，我认为迁移数据结构整体的框架就已经完成了，后续还需要部分调研和验证工作。---## 流程迁移在流程迁移部分，我会从初始化流程→核心流程（即 frontswap 的 api 函数）→各类回调流程→逐一介绍*关于数据结构操作，目前观察都是同质化很严重的操作（如 rbtree），没有迁移层面的太大难度，后续再查缺补漏。### 初始化在 zswap 中，我认为初始化主要有如下几个部分参数设置zswap_enabled_param_setzswap_compressor_param_set…这一类函数通过实现kernel_param_ops，调用module_param_cb()宏创建相关参数zswap_setup(zswap_init)这个函数初始化了一些数据结构，开辟空间，并且注册部分回调zswap_cpu_comp_prepare这个函数是 CPU 热插拔状态变更的回调，主要用于对 comp 算法的注册。### 参数设置我不是特别了解 FreeBSD 的模块参数设置方式，但是根据我查找到的资料，可以提供一个方式做参数绑定：static int zswap_enabled = 0; SYSCTL_NODE("vm", OID_AUTO, "zswap", CTLFLAG_RW, 0, "Zswap VM sysctls"); TUNABLE_INT("vm.zswap.enabled", &zswap_enabled); SYSCTL_INT("vm.zswap", OID_AUTO, enabled, CTLFLAG_RD, &zswap_enabled, 0, "zswap enabled");这样模块就可以在加载的时候获得这个参数了通过实现一个注册函数，并且引用 DECLARE_MODULE的方式就可以注册这个模块了，并且可以通过注册函数参数的不同来确定当前系统是要 LOAD 还是 UNLOAD，进而获取相关参数并初始化。### 参数设置中的其他动作除了绑定相关的参数内容之外，zswap还做了一些诸如参数验证（比如 compressor 是否存在，pool_type是否存在）、另外，由于 zswap的参数设置可能不会只发生在系统启动时，zswap 还对这种情况做了判断，针对不同的时期做不同的初始化和绑定工作。### Summary因此，在参数设置部分，我们主要关注需要迁移的内容包括向系统注册模块的过程，即 DECLARE_MODULE及初始化函数参数绑定的过程，可能需要 TUNABLE_INT 的特性来设置由于 FreeBSD 可能不包含“其他动作”所判断的 system_state因此需要把不同 State 的处理拆出来，在 DECLARE_MODULE 注册的注册函数中，判断不同的 state我们不再需要注册 compressor，因为统一采用 zlib### Setupsetup 主要包含如下步骤为 zswap_entry申请 CACHE 空间注册 CPU 热插拔申请一个 有兜底逻辑的 Pool创建 shrink 队列设置初始化状态对于 CPU 热插拔，相关方案我们在下一步概述对于 Pool，Shrink，我们在数据结构迁移部分都已给出解决方案所以，本部分主要给出为 zswap_entry申请 CACHE 空间的解决方案给出方案前，我确信 KMEM 的存在是为了管理 zswap_entry这个又小又使用频繁的结构，因为它的结构固定，我不得不想到之前对我们没那么好用的 uma zone 好像更适合当前的场景。我们以zswap_entry为单元对象大小，申请一个 uma zone 来作为它的缓存空间。 具体的方式已经在前文介绍过了。### CPU 热插拔相关的初始化实际上，我觉得这两部分的函数并不是针对热插拔进行处理的，我猜测 Linux 内核应该是在初始化的阶段会主动触发一次 CPU 热插拔的回调，来确保用统一的方式初始化各 CPU 的数据。因此，在我的迁移构思中将会按照这种思路，即不考虑真正的热插拔情况，而是直接考虑对每个 CPU 一次初始化需要 per_cpu的内容。zswap 对于每个 CPU：申请了用于多线程压缩/解压结果的一个空间，大小为 2*PAGESIZE根据压缩算法名字申请了一个压缩实例初始化了压缩的其他内容，包括压缩异步调用的回调（释放 wait）、申请 req 空间等。这样看来，我们只需要找到 FreeBSD 中支持 per-CPU申请空间的特性，并给每个 CPU 申请一个 comp_ctx 和 pDst 就可以了。幸运的是，FreeBSD 显然会有这样的特性，即sys/kernel.h 中的 DPCPU_DEFINE()，用于给每个 CPU 定义变量DPCPU_PTR(var, cpuid)这样看来，这个问题也得到解决了。### 核心流程核心流程其实在主文档中已经描述过了，这里只会给出需要修改的接口处，我将以 store 函数为例，逐一过一遍流程中需要替换的内容，对应的其他核心流程，其实用到的接口都差不多，无需赘述。store参数判断我们目前先忽略了 cgroups 特性对于 透明巨页，暂时忽略，因为我还没有找到资料确定 FreeBSD 是否支持这种 HugePage，我猜测如果出现也可以直接判定 page 结构体的数据。对于各类已满的判定，可以直接迁移entry 申请与填充kcache 已经解决判断页面是否全相同：freeBSD 似乎可以利用 pmap_map() 来映射内存压缩可以通过之前提到的 DPCPU 特性来获取当前 cpu 的 comp_ctx我们不再需要 scatterlist，因为我们实现的加密接口不需要散列表因为我们定义的内存池已经支持回收，所以认为需要把 hdr 和内存拆开，以便未来回收暂时不考虑 movable 的特性存储使用我们定义的内存池进行存储，申请相应的空间因为是固定大小的块，直接把压缩好的内容判断是否符合块大小，然后填充进去即可。挂树挂树以红黑树操作为主，FreeBSD 的基础红黑树能实现我们需要的 insert、find_by_index、erase 等操作。记录、日志FreeBSD 有相应的原子操作，可以提供记录### 回调这部分其实主要关注的就是 zswap_writeback_entry，尤其是其中的写回 swap 设备部分，因为其他部分的依赖其实已经都给出解决方案了。然而，因为 uma 的回调并不会给出一个内存池 LRU 好的 handle，我们可能需要维护另外一个数据结构。这里给出一点不太成熟的构想：我们使用 Treap 平衡树，节点值仍为 index，节点权值为 LRU 参数。对于每次访问：更新该 LRU 参数，使得最近最少访问的节点永远在树顶。这样当回调的时候，我们自然而然的可以选择树顶的这一块内存进行清理和回收。---### 补充：关于 z3fold 的 LRU实际上，z3fold 的 LRU 没有那么复杂，在z3fold_pool中，定义了一个名为 lru 的双向链表，用于存储最近使用顺序排列的 z3fold 页面在 z3fold_alloc中，当找到一个空闲的 z3fold 页面时，如果该页面未在 LRU 列表中，添加到 LRU 列表开头，表示它是最近使用的，如果已经在，则移动到列表开头，保持最近使用顺序。从 LRU 列表末尾回收页面。---言归正传，我觉得这种方式是比较合理的方式，其他方式可能要研究一下 zpool 的 LRU 实现。然而由于 Treap 是基于随机的复杂度，我暂时还没有办法保证这种复杂度的正确。以及当 LRU 参数溢出后应该怎么操作。（但是可以想见的是，达到LRU 参数溢出后所需要的时间量级后，我们完全可以把树重建以保证复杂度和不溢出）好，现在已经确定将要被换出的页面了，接下来要做的事是判断当前 entry 是否已经存在于 swap_cache中，freeBSD 没有提供__read_swap_cache_async函数，但是我们有vm_page_lookup()函数，可以确定我们提供的 offset 是否已经在 swap 中。如果已经在，则和远函数的 ZSWAP_SWAPCACHE_EXIST流程相同，否则，调用vm_page_alloc()函数，并根据结果确定是ZSWAP_SWAPCACHE_NEW还是ZSWAP_SWAPCACHE_FAIL。当结果是ZSWAP_SWAPCACHE_NEW时，证明 swap 空间已经为我们要放回的页面准备好了。接下来进行解压步骤，已经在前文有所叙述。并把解压的结果放在刚刚准备完毕的 swap 空间中。FreeBSD 没有 SetPageUptodate()，但是可以改变 vm_page结构的 flags 实现FreeBSD 没有 SetPageReclaim()，也不需要设置相关标志对于写回，在我阅读了 FreeBSD 的swap 策略后，我发现可以直接通过构造一个 buf+swp_strategy来直接使用其他设备写回，具体方案请参见之前的对 swap 的解析。