MIT 6.S081 操作系统课程系列9 File System
https://pdos.csail.mit.edu/6.828/2020/labs/fs.html
本次实验需要读xv6手册第8章。看相关kernel代码。
理解文件系统的原理并实现一些相关功能(大文件和symbolic links软链接)。
文件系统的作用就是存储和管理数据。通常文件可供多个用户和程序共享。
xv6支持类unix的文件、目录、路径,把数据存在虚拟磁盘上。
做文件系统需要面临一些挑战
1. 需要一个树型结构来描述文件和目录。记录数据的归属、每个文件的内容、磁盘占用情况。
2. 需要支持崩溃后的恢复。比如执行某些事务时突然断电,重启后必须还能正常工作。
3. 多个进程可能会同时操作同个文件
4. 访问磁盘比访问内存慢了几个数量级,必须有cache机制。
概览
xv6文件系统分为七层。从下往上看。
层 | 功能 |
---|---|
file descriptor | unix的很多资源都抽象成fd(管道、设备、文件等等) |
pathname | 提供路径支持 |
directory | 特殊的inode。内容是一批目录或文件。 |
inode | 提供独立的文件,每个文件表述为一个incode,有唯一的编号,有一个或多个block保存文件内容。 |
logging | 可让上层把几个更新block的操作打包成事务,这样这些操作就是原子的,可解决崩溃时数据不一致的问题。 |
buffer cache | 缓存disk block。保证一个block在同一时刻最多只有一个kernel进程在对其操作。 |
disk | 读写虚拟硬盘上的block |
文件系统必须规划好inode和block怎么存在磁盘上。xv6把磁盘分成几个部分。
| boot | super | log | inodes | bitmap | data |
block 0 1 2 ...........
block 0(保存boot信息)是不用的。
block 1是superblock。保存文件系统的整体信息:总block数量,inode数量,log里的block数量。
block 2存log。
接着是inodes,每个block存数个inode。
bitmap保存block的使用状态。
实际的数据block。每个block要么是空的(bitmap里标注为空闲),要么存了文件或目录的内容。
superblock存一个单独的程序(mkfs),用来创建一个初始的文件系统。
Buffer cache层
两个功能
1. 对block做并发管理,保证一个block只有一个副本在内存里,而且同一时刻最多只能有一个kernel线程在使用这个副本。
2. 缓存常用的block。这样不用每次读磁盘。
buffer cache提供bread
和bwrite
接口。分别时读写block。
一个kernel线程使用完buffer后必须用brelse
进行释放。
buffer cache用对每个buffer都做一个sleep锁来保证同一时刻只有一个线程在使用同一个buffer。
bread
会返回一个已锁定的buffer。brelse
释放锁。
buffer cache用固定数量的buffer来保存磁盘block。当文件系统请求一个不存在于cache的block时,可能发生回收。
会回收最久没使用的block来给新的block用(假设越久没用意味着再次使用的概率越小)。
Logging层
文件系统一个有趣的点是可防灾。当一个操作包含多个写时,如果一部分写之后,系统崩溃,那么此时文件系统的一致性就会出现问题。
比如宕机发生在删除文件期间。可能会造成:1.indode包含了一个标记为free的block。2.遗留一个分配了但无主的block。
后者情况稍好,前者在机器重启后可能造成严重问题。
重启后,kernel可能把这个free的block分配给其他文件,造成两个文件包含了同一个block,可相互篡改。
xv6的system call不会直接写磁盘。它把所有写操作做成一个log
,需要执行时写一个commit
命令到这个log,这时system call才实际执行这些写操作。完成后把log删除。
如果系统崩溃、重启,在执行任何进程之前,检查log。
如果log标记了commit,执行log里的写操作。
如果没标记commit,直接忽略。
最后把log删除。
Log 设计
log存在superblock里。包含一个header(头block)和后续的block(成为logged blocks)。
header包含一串编号,即logged blocks的编号。和logged blocks的计数。
这个计数如果是0,说明log里没有事务(transaction)。否则说明存在已commit的事务。
xv6在事务commit之后写header,不是之前。把logged block复制到文件系统后把计数置0。
commit之后崩溃会导致非0的计数。
在可能崩溃的环境下,一系列的写操作必须时原子的。为了让不同的进程并发执行,logging系统能把多个system call的写操作放进一个事务里。
这样一个commit可能涵盖多个system call。为了防止一个system call被分割到多个事务,logging系统只会在没有文件相关的system call处于运行状态时才会commit。
多个事务同时commit称作group commit。这样能减少磁盘操作,因为分摊了固定的commit开销。
还有可能更快速的执行写操作,磁盘只需旋转一次就可完成。
xv6的虚拟驱动不支持这种批量操作,但文件系统是支持的。
xv6用磁盘上固定的空间存log。事务里的写block总数b必须在这个空间范围之内。
这样有两个后果:
1. 任何一个system call的写操作不能超出空间范围。
这对于多数system call没影响。除了write和unlink,会写大量block。
- 一个大文件的写可能会写很多block,和bitmap block,和一个inode。unlink一个大文件可能会写多个block和一个inode。
xv6的system call会把一个大的写操作分成小的写操作,放进log里。unlink不会造成这个问题。
其他后果是logging系统不会允许一个system call开始运行除非能确认它的写操作能放进log的剩余空间。
Inode层
inode可以指磁盘上的文件数据(包括文件大小,数据block列表),也可以指内存中的inode,包含磁盘inode的副本和一些其他信息。
磁盘inode是磁盘上一串连续的数据(inode block)。所有inode大小一样,所以给定一个n,很容易能取得磁盘上的第n个inode。
这个n被成为inode number或i-number。
inode可以看成一个无名的文件。
磁盘inode的c代码定义为dinode
(kernel/fs.h)。
type分为文件、目录、特殊文件(设备)。type为0代表inode为未使用状态。
nlink为引用此inode的目录计数。
size为此文件的字节数。
addrs为文件包含的block编号
使用中状态的inode放在内存里。c代码定义是inode
(file.h)。
处于内存中意味着有指针指向这个inode。ref就是这个计数,如果变为0,就会从内存中去除。
iget
和iput
获取和释放inode指针,加减引用计数。
有四种inode相关的锁或锁机制。
icache.lock保证一个inode只存在一份cache。并对ref进行保护。
inode结构体里有一个sleeplock,保证结构体数据修改的原子性。
ref如果大于0,系统会把inode放内存里,并保证这个份cache不会被同时使用。
nlink记录引用inode的目录数量。如果大于0,不会释放这个inode。
iget
返回的inode指针保证是有效的,直到调用相应的iput
。
iget
提供inode的非排外的接入,所以可能多个指针同时指向一个inode。
文件系统的很多部分都依赖这个性质。
iget
返回的inode也可能没有有效的信息。为了保证它指向一个好的磁盘inode,需要调用ilock
(保证其他进程不能再锁),再从磁盘读inode。
iunlock
用来解锁。
File descriptor层
fd层实现了把多数资源都表示成一个文件。
xv6里每个进程会维护自己打开的文件列表。文件的c代码结构体为file
(file.h),包含一个inode或pipe,和一个io偏移。
open
函数会创建一个新的file
。如果多个进程打开同一个文件,每个file会有不同的io偏移。
同个file也可能出现多次,在一个进程的文件列表甚至不同的进程中。这些情况可能是由dup
和fork
等导致。
每个打开的文件都有引用计数。
所有打开的文件也会存在全局的ftable里。
看代码
先看看文件系统的大致代码框架,比较繁琐。
buf结构体
buf.h里的buf结构体对应一个block数据。buf是一个链表结构。
一个buf有一个data数组,包含BSIZE(1024)个uint,每个uint有8位可用,共有1024*8位可用。
用这个data数组表示8k个block的使用情况。
bcache
用一个全局变量bcache存所有buf(NBUF=30个),和一个头block。用头可遍历所有buf。
main()里的binit把NBUF个buf首尾相连。并初始化相关的锁。
dinode结构体
磁盘上的inode抽象
inode的block数据存在uint addrs[NDIRECT+1]。
分为direct block和indirect block。
direc block存在addrs前12个位置。最后一个位置存indirect block数组的地址。
#define NINDIRECT (BSIZE / sizeof(uint))
NINDIRECT默认为1024/4=256
NDIRECT为12
例如:文件数据的第一个block,addrs[0],被分配了全局的3号block(addrs[0]=3),
第二个block,addrs[1],被分配了全局的200号block(addrs[1]=200)。
inode结构体
内存中的inode的数据结构
也包含一个和dinode一样的addrs。
icache
全局变量icache保存所有活跃的inode(NINODE=50个)。
main()里的iinit只是初始化这些inode相关的锁。
file结构体
一个文件的抽象。分为FD_PIPE, FD_INODE, FD_DEVICE三类。
ftable
全局变量ftable包含file的数组(NFILE=100个)。
main()里的fileinit只是初始化ftable的锁。
fsinit
proc.c里的fsinit只会在第一个fork后执行一次。
先readsb读superblock。superblock之前说过,包含了文件系统一些最基本的信息(fs.h)。
再initlog初始化logging系统。
recover_from_log即上述的崩溃恢复流程。
superblock结构体
文件系统的一些总体数据。比如文件系统总block数size,数据block总数nblocks,inode总数ninodes,log的block总数nlog。
这些初始化在mkfs.c里。
默认size=200000,nblocks=199930,ninodes=200,nlog=30。
一些常用函数
static uint balloc(uint dev)
分配一个空的block。
文件系统共200000个block。
一个buf有一个data数组,一共包含BPB(8k)个bit。
系统buf总数为NBUF,30个,每个包含8kbit,可以罩住200000个block。
balloc总体就是遍历所有block找一个空闲的,把它对应的bit设1。
返回的地址大致是0-200000之间的一个index。
static struct buf* bget(uint dev, uint blockno)
从dev设备根据block号读内存里的block数据。
struct buf* bread(uint dev, uint blockno)
先用bget取数据,如果数据是无效的,用virtio_disk_rw磁盘读取。
struct inode* idup(struct inode *ip)
复制inode指针,引用计数加一。
void ilock(struct inode *ip)
锁定inode并读取数据
static struct inode* iget(uint dev, uint inum)
返回相应inode的内存数据。
struct inode* ialloc(uint dev, short type)
在dev设备上新建一个inode。
遍历所有inode,用bread读其底层的block数据,找一个空闲的。修改状态并返回。
#define IPB (BSIZE / sizeof(struct dinode))
IPB实际是16。
struct inode* create(char *path, short type, short major, short minor)
给定路径和类型,创建一个inode,返回指针。
先nameiparent算出目标path的上一层目录,检查是否存在同名。
ialloc分配一个inode。再做一些设置。
struct file* filealloc(void)
申请一个file数据。
在ftable找一个空位。
static int fdalloc(struct file *f)
为file申请一个fd
每个进程的ofile存有它打开的文件的fd。找一个空闲的fd,和file绑定,返回fd。
打开或创建一个文件的流程
sys_open(sysfile.c)
begin_op(),所有fs相关的system call会先调这个做同步处理。
create创建或者namei打开inode。
filealloc,fdalloc申请file和fd。
把inode和file绑定起来。
返回fd。
static uint bmap(struct inode *ip, uint bn)
返回inode自己第bn个block所对应的全局block号。如果未分配,会分配block号。
inode的uint addrs[NDIRECT+1],有NDIRECT(12)个直接的block号,最后一个uint也是一个block号。
不同的是这个block的data(uchar data[BSIZE])存的是256个block号。
uchar是1字节,uint是4字节,BSIZE(1k)个uchar刚好存256个uint。
写文件流程
sys_write(sysfile.c)
先argfd用fd获取进程file数组里的file。
int filewrite(struct file *f, uint64 addr, int n)
把用户地址addr开始的n字节写到f。
对于FD_INODE类型,不断用writei写数据。每次循环只写几个block,因为log机制有事务容量的限制。
int writei(struct inode *ip, int user_src, uint64 src, uint off, uint n)
从地址scr开始,写n字节到inode,需要考虑offset。返回写成功的字节数。
遍历这个inode覆盖的block。按BSIZE(1k)字节来划分,每次读出对应的block数据,每次最多复制1k字节到buf的data里。
做题
1. Large files
xv6的默认文件最大是268个block,需要改造成65803个block。
看懂bmap流程,可以知道inode的addrs有12个direct block,另有1个block,里面包含256个block号。
所以默认代码一共268个block。
看bigfile.c,它每次循环写1k。默认最多只能写268,再写就报错。
跟踪一下发现报错在writei
if(off + n > MAXFILE*BSIZE)
{
printf("xc writei err 2");
return -1;
}
需要改造addrs。把1个direct block变成256×256的二级block。
即改成11个direct block,1个256的block数组和一个256256的二级block。
一共存11 + 256 + 256256 = 65803个block。
- 修改宏
NDIRECT改为11
NINDIRECT为256不变
MAXFILE改为(NDIRECT + NINDIRECT + NINDIRECT * NINDIRECT) -
inode和dinode的addrs长度改为NDIRECT+2
-
修改bmap
仿照默认的一层block,做一个两层的block分配即可。 -
itrunc里要free新加的两层block。
-
bigfile和usertests都通过即可。
主要添加的代码:
bmap函数里if(bn < NINDIRECT)后面加个else分支实现两层block分配。
else
{
bn -= NINDIRECT;
uint index_0 = NDIRECT + 1;
// check index_0
if((addr = ip->addrs[index_0]) == 0)
ip->addrs[index_0] = addr = balloc(ip->dev);
struct buf *bp_0 = bread(ip->dev, addr);
// check index_1
uint *data_1 = (uint*)bp_0->data;
uint index_1 = bn / NINDIRECT;
if((addr = data_1[index_1]) == 0)
{
data_1[index_1] = addr = balloc(ip->dev);
log_write(bp_0);
}
brelse(bp_0);
struct buf *bp_1 = bread(ip->dev, addr);
// check index_2
uint *data_2 = (uint*)bp_1->data;
uint index_2 = bn % NINDIRECT;
if((addr = data_2[index_2]) == 0)
{
data_2[index_2] = addr = balloc(ip->dev);
log_write(bp_1);
}
brelse(bp_1);
return addr;
}
2. Symbolic links
需要实现软链接的system call
搁置
总结
文件系统代码不直观,不好看。把block等配置打印出来,实际数值结合代码理解起来更容易一些。
了解了文件系统基本原理和代码流程。