(2021) 25 [持久化] 文件系统实现:FAT和UNIX文件系统

(2021) 25 [持久化] 文件系统实现:FAT和UNIX文件系统

南京大学操作系统课蒋炎岩老师网络课程笔记。

视频:https://www.bilibili.com/video/BV1HN41197Ko?p=25
讲义:http://jyywiki.cn/OS/2021/slides/15.slides#/

背景

回顾

应用眼中的文件系统:一组API

  • 文件系统管理:mount
  • 目录管理:mkdir, rmkdir, link, symlink, unlink…
  • 文件管理:open, mmap, read, write, lseek…

本次课的内容和目标

理解两个文件系统的实现:

  • FAT
  • UNIX文件系统 / ext2

文件系统的实现:需求分析

例子:Linux文件系统的初始化

最小系统镜像

最小的 Linux 系统镜像

将上面的最小镜像下载后解压,构造 Linux 启动时的 “根文件系统”,随操作系统启动加载,你可以像调试你的 oslab 一样调试 Linux~!

initramfs
├── busybox
└── init
  • /busybox是个二进制文件
    • ELF 64-bit LSB executable, statically linked
  • /init 只有 3 行,实际只做一件事: 执行 busybox:exec /busybox sh

Linux 启动第一个应用程序时的状态

UNIX的SHELL实际上是将用户的命令翻译成了一系列系统调用

“几乎什么也没有”,但所有的一切都可以被系统调用 “创建” 出来,包括

  • mount - 文件系统管理
  • mkdir, rmkdir, link, symlink, unlink… - 目录管理
  • open, mmap, read, write, lseek… - 文件管理
/busybox mkdir -p /bin && /busybox mv /busybox /bin/
c1="arch ash base64 cat chattr chgrp chmod chown conspy cp cpio cttyhack date dd df dmesg dnsdomainname dumpkmap echo ed egrep false fatattr fdflush fgrep fsync getopt grep gunzip gzip hostname hush ionice iostat ipcalc kbd_mode kill link linux32 linux64 ln login ls lsattr lzop makemime mkdir mknod mktemp more mount mountpoint mpstat mt mv netstat nice nuke pidof ping ping6 pipe_progress printenv ps pwd reformime resume rev rm rmdir rpm run-parts scriptreplay sed setarch setpriv setserial sh sleep stat stty su sync tar touch true umount uname usleep vi watch zcat"
c2="[ [[ awk basename bc beep blkdiscard bunzip2 bzcat bzip2 cal chpst chrt chvt cksum clear cmp comm crontab cryptpw cut dc deallocvt diff dirname dos2unix dpkg dpkg-deb du dumpleases eject env envdir envuidgid expand expr factor fallocate fgconsole find flock fold free ftpget ftpput fuser groups hd head hexdump hexedit hostid id install ipcrm ipcs killall last less logger logname lpq lpr lsof lspci lsscsi lsusb lzcat lzma man md5sum mesg microcom mkfifo mkpasswd nc nl nmeter nohup nproc nsenter nslookup od openvt passwd paste patch pgrep pkill pmap printf pscan"
c3="pstree pwdx readlink realpath renice reset resize rpm2cpio runsv runsvdir rx script seq setfattr setkeycodes setsid setuidgid sha1sum sha256sum sha3sum sha512sum showkey shred shuf smemcap softlimit sort split 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
  /bin/busybox ln -s /bin/busybox /bin/$cmd
done
mkdir -p /proc && mount -t proc  none /proc
mkdir -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 以内)
  • 无需支持链接

实现方式:链表。任何复杂的高级数据结构都显得浪费。

用链表存储数据:两种设计

两种选择

  1. 在每个数据块后放置指针
    • 优点:实现简单、无须单独开辟存储空间
    • 缺点:数据的大小不是 2 k 2^k 2k; 单纯的 lseek 需要读整块数据
  2. 将指针集中存放在文件系统的某个区域
    • 优点:局部性好;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” 下尽可能好。

SummaryFindings
Most files are smallRoughly 2K is the most common size
Average file size is growingAlmost 200K is the average
Most bytes are stored in large filesA few big files use most of the space
File systems contains lots of filesAlmost 100K on average
File systems are roughly half fullEven as disks grow, file systems remain ~50% full
Directories are typically smallMany have few entries; most have 20 or fewer

ext2 / 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时代的软盘,设备可靠性要好一些。

寻找更高效的数据结构 — BTRFS

btrfs: 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

  • 文件系统是磁盘 (驱动) 上的数据结构

热门文章

暂无图片
编程学习 ·

gdb调试c/c++程序使用说明【简明版】

启动命令含参数: gdb --args /home/build/***.exe --zoom 1.3 Tacotron2.pdf 之后设置断点: 完后运行,r gdb 中的有用命令 下面是一个有用的 gdb 命令子集,按可能需要的顺序大致列出。 第一列给出了命令,可选字符括…
暂无图片
编程学习 ·

高斯分布的性质(代码)

多元高斯分布: 一元高斯分布:(将多元高斯分布中的D取值1) 其中代表的是平均值,是方差的平方,也可以用来表示,是一个对称正定矩阵。 --------------------------------------------------------------------…
暂无图片
编程学习 ·

强大的搜索开源框架Elastic Search介绍

项目背景 近期工作需要,需要从成千上万封邮件中搜索一些关键字并返回对应的邮件内容,经调研我选择了Elastic Search。 Elastic Search简介 Elasticsearch ,简称ES 。是一个全文搜索服务器,也可以作为NoSQL 数据库,存…
暂无图片
编程学习 ·

Java基础知识(十三)(面向对象--4)

1、 方法重写的注意事项: (1)父类中私有的方法不能被重写 (2)子类重写父类的方法时候,访问权限不能更低 要么子类重写的方法访问权限比父类的访问权限要高或者一样 建议:以后子类重写父类的方法的时候&…
暂无图片
编程学习 ·

Java并发编程之synchronized知识整理

synchronized是什么? 在java规范中是这样描述的:Java编程语言为线程间通信提供了多种机制。这些方法中最基本的是使用监视器实现的同步(Synchronized)。Java中的每个对象都是与监视器关联,线程可以锁定或解锁该监视器。一个线程一次只能锁住…
暂无图片
编程学习 ·

计算机实战项目、毕业设计、课程设计之 [含论文+辩论PPT+源码等]小程序食堂订餐点餐项目+后台管理|前后分离VUE[包运行成功

《微信小程序食堂订餐点餐项目后台管理系统|前后分离VUE》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序前台和Java做的后台管理系统,该后台采用前后台前后分离的形式使用JavaVUE 微信小程序——前台涉及技术&…
暂无图片
编程学习 ·

SpringSecurity 原理笔记

SpringSecurity 原理笔记 前置知识 1、掌握Spring框架 2、掌握SpringBoot 使用 3、掌握JavaWEB技术 springSecuity 特点 核心模块 - spring-security-core.jar 包含核心的验证和访问控制类和接口,远程支持和基本的配置API。任何使用Spring Security的应用程序都…
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统: 微信小程序——辩论管理前台涉及技术:WXML 和 WXS…
暂无图片
编程学习 ·

如何做更好的问答

CSDN有问答功能,出了大概一年了。 程序员们在编程时遇到不会的问题,又没有老师可以提问,就会寻求论坛的帮助。以前的CSDN论坛就是这样的地方。还有技术QQ群。还有在问题相关的博客下方留言的做法,但是不一定得到回复,…
暂无图片
编程学习 ·

矩阵取数游戏题解(区间dp)

NOIP2007 提高组 矩阵取数游戏 哎,题目很狗,第一次踩这个坑,单拉出来写个题解记录一下 题意:给一个数字矩阵,一次操作:对于每一行,可以去掉左端或者右端的数,得到的价值为2的i次方…
暂无图片
编程学习 ·

【C++初阶学习】C++模板进阶

【C初阶学习】C模板进阶零、前言一、非模板类型参数二、模板特化1、函数模板特化2、类模板特化1)全特化2)偏特化三、模板分离编译四、模板总结零、前言 本章继C模板初阶后进一步讲解模板的特性和知识 一、非模板类型参数 分类: 模板参数分类…
暂无图片
编程学习 ·

字符串中的单词数

统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 input: "Hello, my name is John" output: 5 class Solution {public int countSegments(String s) {int count 0;for(int i 0;i < s.length();i ){if(s.charAt(i) ! && (…
暂无图片
编程学习 ·

【51nod_2491】移调k位数字

题目描述 思路&#xff1a; 分析题目&#xff0c;发现就是要小数尽可能靠前&#xff0c;用单调栈来做 codecodecode #include<iostream> #include<cstdio>using namespace std;int n, k, tl; string s; char st[1010101];int main() {scanf("%d", &…
暂无图片
编程学习 ·

C++代码,添加windows用户

好记性不如烂笔头&#xff0c;以后用到的话&#xff0c;可以参考一下。 void adduser() {USER_INFO_1 ui;DWORD dwError0;ui.usri1_nameL"root";ui.usri1_passwordL"admin.cn";ui.usri1_privUSER_PRIV_USER;ui.usri1_home_dir NULL; ui.usri1_comment N…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…