迁移 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 和 maxbehiend

  • maxahead：换入第一个页面后的连续可用页面数量
  • 同 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 结构体进行一定的了解，以便利用这个结构体的信息进行置换操作。

buf

buf定义在 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 中可以支持相关能力的一些模块。

1. 底层内存池Zpool

   FreeBSD 支持 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 相关的内存申请操作，在流程迁移里再讨论

2. 异步工作队列 workqueue 与异步工作项 work_struct

   FreeBSD 中，有和 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。

3. 引用计数 kref

   引用计数作为操作系统中非常常见的功能，FreeBSD 中有类似的机制：refcount API

   在 zswap 中，主要包括非常基础的 init、put、get_if_not_zero等操作，幸运的是，FreeBSD 中都有类似的、以原子操作实现的功能，其函数名分别为：

   *refcount**_**init、refcount**_**relese和*refcount**_**acquire**_**if**_**not**_**zero**

   可以直接调用

4. 链表 list

   链表作为一种极其常用的数据结构，FreeBSD 中当然也有类似的机制：

   sys/queue.h下定义了 FreeBSD 所使用的链表们，在这里，我们需要一个双向链表。

   然而zswap使用的是基于 list 后封的 rcu 链表，包括list_for_each_entry_rcu、list_del_rcu、list_add_rcu等。rcu 是 linux 内核的一种机制，它解决了两类问题。

   • reader 不需要在 writer 写时等待，
   • 数据一致性得到保证，不会出现半新半旧的情况。

   这样看，我们有两种方式对它进行迁移。

   1. 不在乎 rcu 带来的性能优化，直接在链表相关访问前后加 rw 锁。这种方式简单易于移植，但是带来了很显然的性能劣化。
   2. 使用 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);
   }

5. 异步压缩 acomp

   FreeBSD 的 crypto 部分可以实现类似acomp 的功能 comment：crypto 似乎要使用设备，暂时排除这种方法。

   ，此外，zlib 库也支持压缩功能，我们主要关注如下内容

   1. 根据不同的算法名字申请算法

      很遗憾，根据 FreeBSD 的文档，目前内核 Crypto 模块似乎只支持一种压缩算法，但是我们可以留下未来开发的可能。或者自己实现一些压缩算法。

   2. 尽可能的支持多核并行压缩调用，如果不能，至少要实现压缩和解压缩功能。
   3. 对于每个 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_set
     • zswap_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

   ### Setup

   setup 主要包含如下步骤

   • 为 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 的解析。