(2021 ) 25 [可持续化]文件系统实现： FAT与UNIX文件系统南京大学操作系统课无忧小蚂蚁老师的网络课堂笔记。
视频： https://www.bilibili.com/video/b v1hn 41197 ko？ p=25
讲座： http://jyywiki.cn/OS/2021/slides/15.slides /
背景APP应用程序映入眼帘的文件系统：一系列API
3358 www.Sina.com//mount 3358 www.Sina.com//mkdir、rmkdir、link、symlink、unlink…http://www.Sina.com/
实现FATUNIX文件系统/ext2文件系统：需求分析示例：初始化Linux文件系统最小系统镜像最小Linux系统镜像
下载并解压缩上面的最小镜像，构建Linux启动的“根文件系统”，然后与操作系统启动一起下载，就可以像调试你的oslab一样调试Linux了~
initramfsbusybox(init/busybox只有三行二进制文件elf 64位LSB executable和statically linked /init，实际上一件事只需要执行：
“几乎什么都没有”，但通过系统调用“创建”了一切。 包括以下内容
挂载-文件系统管理mkdir、rmkdir、link、symlink、unlink… -目录管理open、mmap、read、write、 lseek… -文件管理/busybox mkdir-p/Zr dxl/busybox mv/busybox/Zr dxl/C1=' archashbase 64 catchattrchgrpchmodchownconspycpcpiocttyhackdateddfdmesgdnsdomainnamedumpkmapechoedegrepfatatattttrfdfdflulu ipgziphostnamehushioniceiostatipcalckbd _ modekillinux 32 Linux 64 lnloginlslsattrlzopmakemimekdirmknon tempmoremountmountpointmpp f pingping6pipe _ progressprintenvpspwdreformimeresumerevrmrmdirrpmrun-PPP riptreplaysedsetarchsetprivsetserialshsleepstatsusususustatusustustusustatusus eepviwatchzcat ' C2=' [ awkbasenamebc ] iscardbunzip2bzcat bzip2 calchpstchrtchvtcksumclearcmpcommcrontabcryptpwcutdcdeallocvtdiffdos2unixdpkgdpkg-debdudumpleamp eamp ejectos xprfactorfallocatefgconsolefindflockfoldfreeftpgetftpputfusergroupshdheadhexdumphexedithostidid tallipcskilllalllllastlesslogogogid ilsscsilsusblzcatlzmamanmd5summesgmicrocommkfifomkpasswdncnlnmeternohup nprocnsenternslookupodopenvtpasswdpastepatchpgreppkillllpkilllllppkilppkill epwdxreadlinkrealpathreniceresetresizerpm 220 runsvdirrxscriptseqsetfattrsetkeycodessetsidsetuidgidsha1sha256sum sha3sha 512
t ssl_client strings sum sv svc svok tac tail taskset tcpsvd tee telnet test tftp time timeout top tr traceroute traceroute6 truncate ts tty ttysize udhcpc6 udpsvd unexpand uniq unix2dos unlink unlzma unshare unxz unzip uptime users uudecode uuencode vlock volname w wall wc wget which who whoami whois xargs xxd xz xzcat yes"for cmd in $c1 $c2 $c3; do /zrdxl/busybox ln -s /zrdxl/busybox /zrdxl/$cmddonemkdir -p /proc && mount -t proc none /procmkdir -p /sys && mount -t sysfs none /sys 文件系统的实现在一个 I/O 设备 (驱动) 上实现 “目录树” 的数据结构。
VFS：管理所有文件系统共享的部分
对象 (inode) 分配/回收、路径/符号链接解析、挂载定义了每个具体文件系统需要实现的接口具体的文件系统（如有设备的ext4，无设备的procfs）其实就是一组API，是将一个设备抽象成一棵树的代码。
利用块设备驱动：read_block, write_block，得到目录/文件 API：mkdir, rmdir, link, unlink, open, read, write, stat。
内存上的数据结构和磁盘上的数据结构实际上，我们平时所谈到的数据结构默认是内存上的数据结构，而文件系统相当于是在磁盘（更准确地说是 ”持久化的，不支持随机读写的存储设备“）上实现一种数据结构。
注意：我们的持久化存储设备（磁盘、SSD等）不支持像内存RAM那样的随机访问，即每次至少要访问一个块（如4KiB，512B）。
在内存上，我们拥有的API是访问一个字（节）（如malloc / free），在磁盘上我们拥有的API是读写一个块（read_block, write_block）, （可以称为balloc, bfree）。在这些API的基础上实现出我们想要的数据结构，实现出上面提到的文件、目录、文件系统管理的API，那这就是文件系统。
FAT （File Allocation Table）FAT是个简单而古老的文件系统，基本所有平台都支持这种文件系统。 一路走来有FAT12，FAT16，FAT32，exFAT等。
需求在很久很久以前，存储设备的空间远没有今天这么大。如5.25" 软盘：单面 180 KiB，360 个 512B 扇区 (sectors)，在这样的设备上持久化数据，应该选用怎样的数据结构？
抛开workload谈优化，就是耍流氓。
需求：
树状的目录结构系统中以小文件为主 (几个 block 以内)无需支持链接实现方式：链表。任何复杂的高级数据结构都显得浪费。
用链表存储数据：两种设计 两种选择 在每个数据块后放置指针 优点：实现简单、无须单独开辟存储空间缺点：数据的大小不是 2 k 2^k 2k； 单纯的 lseek 需要读整块数据 将指针集中存放在文件系统的某个区域 优点：局部性好；lseek 更快缺点：集中存放的数据损坏将导致数据丢失 (怎么办？)哪种方式的缺陷是致命、难以解决的？
集中保存所有指针FAT文件系统选择将指针集中存放在文件系统的某个区域，这个区域称为File Allocation Table，这也正是FAT名称的由来。
集中存储的指针容易损坏？存 n 份就行！FAT-12/16/32 (FAT entry，即 “next 指针” 的大小)。
“File Allocation Table” 文件系统RTFM 得到必要的细节
逻辑上，文件/目录都是字节序列 (虚拟化的磁盘)，以 cluster (簇) 为单位链接 (FAT 集中存储链表的 next)。目录也是文件，一个 (filename, size, firstblock) 的列表，顺序存储。 struct fat_volume { struct fat_header header; struct fat[FAT_NUM]; char clusters[CLUSTER_SZ][];}; FAT: 链接存储的文件“FAT” 的 “next” 数组
0: free; 2...MAX: allocated;ffffff7: bad cluster; ffffff8-ffffffe, -1: end-of-file更细节的信息如图。
以普通文件的方式存储 “目录” 这个数据结构
FAT: 目录 = 32-byte 定长目录项的集合操作系统在解析时把标记为目录的目录项 “当做” 目录即可。另外，可以用连续的若干个目录项存储 “长文件名”。FAT: 性能与可靠性 性能 优点： 小文件简直太合适了。缺点：但大文件的随机访问就不行了，4 GB 的文件跳到末尾 (4 KB cluster) 就要有 220 次链表 next 操作，缓存能部分解决这个问题。在 FAT 时代，磁盘连续访问性能更佳（现在也是连续访问更佳，但没差那么多），使用时间久的磁盘会产生碎片 (fragmentation)，malloc 也会产生碎片，不过对性能影响不太大。 可靠性 维护若干个 FAT 的副本防止元数据损坏，有额外的同步开销。损坏的 cluster 在 FAT 中标记。 ext2 / UNIX 文件系统 思考：更好的文件系统，需要做到什么
怎样才能支持更好的随机访问呢？
不能 “尽善尽美”，但可以在 “实际 workload” 下尽可能好。
SummaryFindingsMost files are smallRoughly 2K is the most common sizeAverage file size is growingAlmost 200K is the averageMost bytes are stored in large filesA few big files use most of the spaceFile systems contains lots of filesAlmost 100K on averageFile systems are roughly half fullEven as disks grow, file systems remain ~50% fullDirectories are typically smallMany have few entries; most have 20 or fewerext2 / UNIX文件系统 ext2按对象方式集中存储文件/目录元数据
增强局部性 (更易于缓存)
支持链接（名字不同，但是同一个文件）
为了支持链接，文件对象inode（包括文件元数据等）需要单独存储。
为大小文件区分 fast/slow path
小的时候应该用数组，连链表遍历都省了大的时候应该用树 (B-Tree; Radix-Tree; …)，快速的随机访问 ext2磁盘镜像格式对磁盘进行分组：
“superblock”：文件系统元数据
文件 (inode) 数量block group 信息 ext2.h 里有你需要知道的一切 ext2 innode ext2目录文件与 FAT 本质相同：在文件上建立目录的数据结构。
注意到 inode 统一存储，目录文件中存储文件名到 inode 编号的 key-value mapping。
ext2性能与可靠性大文件的随机读写性能提升明显 ( O ( 1 ) O(1) O(1))
支持链接 (一定程度减少空间浪费)inode 在磁盘上连续存储，便于缓存/预取依然有碎片的问题但可靠性依然是个很大的问题
存储 inode 的数据块损坏是很严重的，但现代的磁盘相对于FAT时代的软盘，设备可靠性要好一些。 寻找更高效的数据结构 — BTRFSbtrfs: Everything is a B-tree
The BTRFS B-tree… knows only about “keys, items, and block headers.”数据结构由多个 copy-on-write 的 tree 组成 subvolume, extent allocation tree, checksum tree, chunk and device tree, reloc tree, …O. Rodeth, et al. BTRFS: The Linux B-tree filesystem. ACM Transactions on Storage (ToS), 9(3), 2013. 总结 本次课内容与目标 理解两个文件系统的设计与实现 FAT: 链表 + 元数据存储在目录项UNIX 文件系统/ext2: bitmap + inode + 索引 Takeaway messages 文件系统是磁盘 (驱动) 上的数据结构