ctFS: Replacing File Indexing with Hardware Memory Translation through Contiguous File Allocation for Persistent Memory

Introduction

傲腾内存的出现降低了非易失性内存和DRAM的性能差距，并且带来了byte访问的特性。许多新的文件系统（ext4, xfs, and ext2）已经开始利用PM的DAX降低page cache的使用以此提高性能。

然而上述的文件系统索引的结构还是传统的tree-based。这种树型的索引结构是在unix系统时期提出的，当时持久性存储和DRAM的性能还存在很大的差距，主要的开销主要是在持久化的外存。然而随着二者性能差距的减少，关键路径来到了IO软件栈，据作者的实验显示，即便是ext4-dax模式，内存索引的开销也有45%。

替代内存索引的思路就是连续文件分配，一般存在两种分配方法，固定大小和可变大小，存在以下的问题

• 固定大小文件分配存在分区内碎片
• 可变大小文件分配存在分区外碎片
• 在文件re-size的过程中，需要数据迁移

本文提出了一种基于地址转换的持久性内存连续文件分配思路，类似于伙伴分配算法，给文件分配虚拟地址，当需要虚拟地址到物理地址转换时，OS查看在PM中的持久性页表，然后将这个映射放到DRAM的页表中，之后可以用MMU加速地址转换。

Background

File Indexing Overhead

本文测试了SpiltFs和ext4-dax下的索引开销，因为SpiltFs存在relink，mmap, 并且索引同时在内核态和用户态，它的索引开销占比会比ext4更大。

Design

总体设计

ctFS的设计主要分为两个部分，用户态的文件系统抽象ctU，和内核态的虚拟地址页表ctK。当发生页错误时，在用户态文件系统范围的虚拟地址范围被内核态ctK处理，当这个映射不存在持久性页表PPT中，那么ctK就会分配一个PM页并且将映射保存在PPT和page table中。

ctU

ctFS采用类似于Linux 的伙伴分配算法来管理虚拟地址空间，分为10个level，每个level之间的大小差距是8倍，因为要和page table的多级页表先匹配，和地址的对应的关系对应如下

对于空闲页的查找，ctFS设置了一个表头来加速查找，对于L4-L9，会利用第一个页去保存使用状态，对于后面的三个层级，用一个页去表述空闲资源有些浪费，转为利用bitmap去表示。

ctK

ctK 负责管理PPT，对于虚拟地址和物理地址，ctFS都采用的相对地址，为每个进程映射到不同的虚拟地址

Pswap

​ ctFS将一个文件分配在刚好容纳该文件的分区中，当文件超出其分区时，它会被移动到虚拟内存中更大的分区，而无需进行任何物理页的拷贝。 ctFS 通过使用pswap 将文件的物理页面重新映射到新分区来做到这一点，这是一种新的操作系统系统调用，可以原子地交换虚拟到物理的映射。原子交换还可以在多块写入时实现高效的崩溃一致性，而无需重复写入数据。 ctFS 中的原子写入只是将数据写入新空间，然后将其与旧数据进行 pswap。

​ 一个例子如下图，其中 pswap 需要交换两个页面序列 A 和 B， 两个序列都包含 262,658 (512 × 512 + 512 + 2) 个页面。 交换两个序列的数据时，使用pswap 只需要交换 4 对页表条目或目录，因为所有 262,658 个页面都被单个 PUD 条目覆盖（覆盖 512×512 个页面），单个 PMD 条目（涵盖 512 页）和两个 PTE 条目（涵盖 2 页）。

文件系统操作

• read() ctU获得文件的inode，进一步获得文件的起始地址，然后起始地址和偏移相加获得读的地址，使用memcpy()读到用户buffer
• write() ctFS会分配一个尽量小的满足第一次写要求的空间给文件，当后续的写操作使得文件超出了当前空间大小，ctFS会进行扩容操作，然后再进行写操作。