文件系统结构

unix的文件系统相关知识

• unix将可用的磁盘空间划分为两种主要类型的区域：inode区域和数据区域。
• unix为每个文件分配一个inode，其中保存文件的关键元数据，如文件的stat属性和指向文件数据块的指针。
• 数据区域中的空间会被分成大小相同的数据块（就像内存管理中的分页）。数据块中存储文件数据和目录元数据。
• 目录条目包含文件名和指向inode的指针

jos的文件系统
jos对文件系统进行了简化——不使用inode。文件的所有元数据存储在目录条目中。
jos中的数据区域也会被划分为“块”

磁盘上的数据结构

磁盘不可能以字节为单位进行读写，而是以扇区为单位进行读写。jos 中扇区为512字节。
硬件层面，磁盘驱动以扇区为单位进行数据读写。
软件层面，操作系统以“块”为单位进行数据分配。
jos 中块的大小为4096字节。

超级块 superblocks

如上文所述，jos 的数据区域被划分为块。
jos 还会有一个超级块，位于磁盘的第1个块（第0个块中存放 引导加载器和分区表），由 inc/fs.h 中的 struct super 定义。内容如下：

struct Super {
	uint32_t s_magic;		// Magic number: FS_MAGIC
	uint32_t s_nblocks;		// Total number of blocks on disk
	struct File s_root;		// Root directory node
};

其中包含磁盘中存放的块的总量和文件系统的根目录。
超级块可能一个块存不下，所以会占据多个块。

文件元数据 File Meta data

文件元数据定义在 inc/fs.h 中的 struct File ， 内容如下：

struct File {
	char f_name[MAXNAMELEN];	// filename
	off_t f_size;			// file size in bytes
	uint32_t f_type;		// file type

	// Block pointers.
	// A block is allocated iff its value is != 0.
	uint32_t f_direct[NDIRECT];	// direct blocks
	uint32_t f_indirect;		// indirect block

	// Pad out to 256 bytes; must do arithmetic in case we're compiling
	// fsformat on a 64-bit machine.
	uint8_t f_pad[256 - MAXNAMELEN - 8 - 4*NDIRECT - 4];
} __attribute__((packed));	// required only on some 64-bit machines

其中包含文件名、大小、类型、数据块指针，以及pad（该结构保持256字节大小）。
一个 File struct 对应的数据块分为两种：直接块、间接块。

• 直接块有10个，可以存储40kb的文件，存储在 File struct 的数据块指针数组 f_direct 中。
• 间接块最多可以有1024个，如果直接块不够用， File struct 会被分配一个数据块（地址存储在 f_indirect )，里面全都用于保存数据块指针。（一个数据块大小为4096字节，一个数据块指针占据4字节，故间接块可以有4096/4=1024个）
  因此 jos 的文件最多可以 1034个块， 可以存储 $1034 times 4096kb$ 的数据。
  File的结构体的情况可以用下面的图片来理解：

目录文件和普通文件

jos 的 File struct 既可以用来表示普通文件，也可以代表目录文件，由 File struct 的 f_type 字段来区分。
文件系统管理普通文件和目录文件的方式完全相同，具体来说，文件系统不解析普通文件内的数据，但解析目录文件内的数据，因为其中是该目录下的文件的数据。
超级块中包含一个 File struct ， 其中包含了文件系统根目录的元数据。

文件系统

磁盘访问

在之前的 lab 中，我们通过汇编的 in 和 out 指令，向磁盘设备发送读写信号。但是这样果然还是好麻烦， jos 将 IDE 磁盘驱动程序作为用户级进程来实现。（传统的策略是将磁盘驱动加入至内核，然后以系统调用的形式供进程调用）。
为了能够让用户级进程在不使用磁盘中断的前提下，拥有执行特殊设备I/O指令的权限，需要使用 EFLAG 寄存器中的 IOPL 位。
因此，操作系统在创建我们的 用户级文件系统 进程时，应该对其 env struct 中的 eflag 成员置位。因此，我们需要对 lab3 编写的 env_create 进行修改。由于我们只允许 用户及文件系统进程 进行磁盘IO，所以需要将其他进程和 用户级文件系统进程 进行区分， jos 的方案是专为 用户及文件系统进程 设立一个 ENV_TYPE_FS 。具体任务见练习1.

块缓存(练习2@fs/bc.c)

在之前的 lab 中，我们访问磁盘是通过分区号来访问的。但是这样果然好麻烦，要是能像内存一样用线性地址访问就好了。

块缓存的编址
为了实现上面的目标， jos 将 用户级文件系统进程的虚拟地址空间中 0x1000_0000 (DISKMAP) 到 0xD000_0000 (DISKMAP+DISKMAX) 部分用于和磁盘的存储空间进行映射。

具体来说，首先将块号和内存地址进行映射，当我们访问块缓存中的地址时，先将地址转化为块号，然后再进行读写。然后将块缓存的地址通过页表、页目录进行管理。

顺带一提，DISKMAX 大小为 0xC000_0000B = 3GB ， 因此 jos 仅支持 3GB 大小的磁盘存储空间。

块缓存的同步方案
为了同步内存中的磁盘数据，和磁盘中实际存储的数据，我们利用 PTE 的 PTE_D 位追踪数据是否被改动。（当内存地址addr所指页被改动时，MMU会将其对应的PTE中的 PTE_D 置位）。

将整个磁盘都读入内存很浪费时间，我们可以参考“写时复制”实现一种“读时加载”的页错误处理程序。当程序读取的块缓存地址对应的数据尚未被加载时，触发页错误，然后将对应的数据从磁盘中加载到其块缓存地址。

块缓存的是同步的实现，即是练习2的内容。

块缓存的实现
jos 对块缓存的实现，主要位于 fs/bc.c 中。其中包含如下函数：

void * diskaddr(uint32_t blockno)

将块号转化为对应的块缓存地址

void*
diskaddr(uint32_t blockno)
{
	if (blockno == 0 || (super && blockno >= super->s_nblocks))
		panic("bad block number %08x in diskaddr", blockno);
	return (char*) (DISKMAP + blockno * BLKSIZE);
}

bool va_is_mapped(void *va)

检查块缓存 va 是否已经被映射到页目录。
具体方法：检查 va 对应的 PDE 和 PTE 的 PTE_P 是否置位。

bool
va_is_mapped(void *va)
{
	return (uvpd[PDX(va)] & PTE_P) && (uvpt[PGNUM(va)] & PTE_P);
}

bool va_is_dirty(void *va)

检查块缓存 VA 是否"脏"。脏指的是数据是否被改动。
具体方法：检查 va 对应的 PTE 的 PTE_D 是否置位。

bool
va_is_dirty(void *va)
{
	return (uvpt[PGNUM(va)] & PTE_D) != 0;
}

static void bc_pgfault(struct UTrapframe *utf)

缺页中断，当块缓存范围内地址触发页错误时会被调用。

static void
bc_pgfault(struct UTrapframe *utf)
{
    void *addr = (void *) utf->utf_fault_va;                    //取出引发错误的地址
    uint32_t blockno = ((uint32_t)addr - DISKMAP) / BLKSIZE;    //转化为块号
	int r;

	// 检查地址是否越界
	if (addr = (void*)(DISKMAP + DISKSIZE))
		panic("page fault in FS: eip %08x, va %08x, err %04x",
		      utf->utf_eip, addr, utf->utf_err);

	// 检查块号是否越界
	if (super && blockno >= super->s_nblocks)
		panic("reading non-existent block %08xn", blockno);

	// Allocate a page in the disk map region, read the contents
	// of the block from the disk into that page.
	// Hint: first round addr to page boundary. fs/ide.c has code to read
	// the disk.
	//
	// LAB 5: you code here:
	//申请一块物理页，将其映射到addr处
	addr  = ROUNDDOWN(addr, PGSIZE);		//对齐需要读取的地址
	sys_page_alloc(0, addr, PTE_W|PTE_U|PTE_P);	//调用page_alloc的syscall，申请内存页
	// 将磁盘中的数据读入内存
	// 磁盘以扇区为单位读取数据，一个扇区512字节
	// 文件系统以块为单位管理数据，一个块4096字节（一页）
	if((r=ide_read(blockno * BLKSECTS, addr, BLKSECTS))

void flush_block(void *addr)

刷新块缓存地址 addr

void
flush_block(void *addr)
{
	//将addr转换位块号
	uint32_t blockno = ((uint32_t)addr - DISKMAP) / BLKSIZE;

	//检查addr是否越界
	if (addr = (void*)(DISKMAP + DISKSIZE))
		panic("flush_block of bad va %08x", addr);

	// LAB 5: Your code here.
	// panic("flush_block not implemented");
	//addr向下对齐
	addr = ROUNDDOWN(addr, PGSIZE);

	//检查数据是否已经读入，数据页是否有脏位
	if(!va_is_mapped(addr) || !va_is_dirty(addr))
	{
		return ;
	}
	int r = 0;
	//将数据写回至磁盘
	if((r = ide_write(blockno*BLKSECTS, addr, BLKSECTS))

boid bc_init(void)

初始化块缓存

void
bc_init(void)
{
	struct Super super;
	//设置文件系统的缺页处理函数
	set_pgfault_handler(bc_pgfault);
	check_bc();

	// cache the super block by reading it once
	// 对super块的块缓存地址读取，并给super
	// 首先会触发缺页中断，将block#1加载至diskaddr(1)处
	// 然后再进行memmove，将读取到的数据填充super struct
	memmove(&super, diskaddr(1), sizeof super);
}

块位图

为什么需要块位图？

块缓存实现之后，我们拥有了从磁盘中读写、改写数据块的能力。接下来考虑一个问题，我们如何删除某个块的内容？将其数据用0覆盖吗？磁盘的磁头听到这种方案内心一定是麻的。一种简单的方案是用一个位图来表示所有块的状态，每个位代表一个块，1代表空闲，0代表占用。这样，当我们要"删除"一个块的数据时，只要在位图中将对应位置0即可。

块位图本身也是占用磁盘数据空间的， jos 的块位图存储在磁盘的第2个块以及之后，块位图一个块存不下。（手册中只有一张示意图提到这个点）

jos 的位图是一个u32int型数组，一个u32int有32个位，对应32个块。3GB磁盘空间共有 $$frac{3times 1024 times 1024 times 1024 B}{4times 1024 B} = 768times 1024 个$$一个块共有 $4096times 8bit = 32 times 1024 bit$ 因此，bitmap应该占据 $frac{768}{32} = 24$ 个块
磁盘的存储空间示意图如下：

维护块位图 （练习3@fs/fs.c）

当我们想要使用 free 的块时，需要将对应位置0。当我们想释放 non-free 块时，应将对应位置1。 练习3 让我们实现 fs/fs.c 中的 free_block 和 alloc_block 来实现这些内容。值得注意的是，无论是 free_block 还是 alloc_block 我们一定都会影响 bitmap 占用的block，因此需要调用 flush_block 刷新 bitmap 占用的 block。

void free_block(uint32_t blockno)

void
free_block(uint32_t blockno)
{
	// Blockno zero is the null pointer of block numbers.
	if (blockno == 0)
		panic("attempt to free zero block");
	bitmap[blockno/32] |= 1

free_block 中最核心的就是 bitmap[blockno/32] |= 1
blockno/32 得到 blockno 在bitmap 的哪个uint32_t，因为 bitmap 的定义如下：

//bitmap 是一个uint32_t类型的数组
uint32_t *bitmap;       // bitmap blocks mapped in memory

blockno%32 得到 blockno 位于这个uint32_t 的哪一位

int alloc_block(void)

allock_block 根据块位图寻找一个空闲块，返回这个空闲块的块号，并更新块位图

int
alloc_block(void)
{
	uint32_t bitmap_start = 2;
	//一个block大小为4096B，bitmap的一项是uint32_t，大小为4B,故一个block够装下4096/4项
	uint32_t bitmap_item_num_in_block = 4096/4;

	for (uint32_t blockno = 0; blockno s_nblocks; blockno++) {//遍历整个bitmap，寻找空闲块
		if(block_is_free(blockno)){
			bitmap[blockno / 32] &= ~(1 

文件操作(练习4@fs/fs.c)

有了块缓存和块位图机制，我们现在有了以块为单位的读写硬盘数据的能力。但是块中的数据是以文件的形式存储。jos 在 fs/fs.c 中还有一些函数，用来实现对文件的基本操作。包括：

• 从块中解析文件结构
• 扫描目录中的文件条目
• 从根目录寻找指定文件
  练习4 让我们实现 file_block_walk 、 file_get_block，并且通读 fs/fs.c

file_block_walk : 从文件中的快便宜映射到结构文件中该块的指针或间接块
file_get_block : 映射到实际的磁盘块

static int file_block_walk

根据文件 File f 内的块号 filebno，寻找该块对应的硬盘块号 ppdiskbno
如果 File f 的 indirects 没有初始化，且 alloc 置位，则初始化 indirects
如果输入合法，这个函数保证一定完成 filebno 到 diskbno 的映射，但不保证 diskbno 所指的块已经在块位图中申请。
申请工作由 file_get_block 负责

static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
	uint32_t * indirects;
	if(filebno >= NDIRECT + NINDIRECT)		//检查 filebno 是否超出 File结构体 能存储的上限
		return -E_NO_DISK;

	if(filebno f_direct[filebno]);	//如果 filebno 位于 直接块内，直接返回
	}
	else if(f->f_indirect)						// 如果 filebno 位于 非直接块，且该File已经申请了直接块
	{
		indirects = diskaddr(f->f_indirect);	//获取非直接块所在的地址
		*ppdiskbno = &(indirects[filebno - NDIRECT]);
	}
	else if(alloc)								// 如果 filebno 位于 非直接块，且该File未申请非直接块，且alloc置位
	{
		int bn;
		if ((bn = alloc_block()) f_indirect = bn;	//初始化 indirect
		flush_block(diskaddr(bn));	//刷新 indirect块 不太理解为什么要刷新这个块，这个块应该是未修改的
		indirects = diskaddr(bn);
		*ppdiskbno = &(indirects[filebno - NDIRECT]);
	}
	else										// 如果 filebno 位于 非直接块，且该File未申请非直接块，且alloc未置位
	{
		return -E_NOT_FOUND;
	}
	return 0;
}

file_get_block

负责读取文件 File f 的第 filebnoe 个块，将数据存储在 blk 所指内存地址。

int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{
	uint32_t * pdiskbno;
	int r;
	//先通过 file_block_walk 获取 filebno 对应的 diskbno
	if((r = file_block_walk(f, filebno, &pdiskbno, true)) 

static int dir_lookup

查找 dir 中文件名为 name 的文件，保存在 file 中。

static int
dir_lookup(struct File *dir, const char *name, struct File **file)
{
	int r;
	uint32_t i, j, nblock;
	char *blk;
	struct File *f;

	assert((dir->f_size % BLKSIZE) == 0);
	nblock = dir->f_size / BLKSIZE;			//dir中共有 nblock 个块
	for (i = 0; i 

static int dir_alloc_file

在目录 dir 下申请一个文件 file

static int
dir_alloc_file(struct File *dir, struct File **file)
{
	int r;
	uint32_t nblock, i, j;
	char *blk;
	struct File *f;

	assert((dir->f_size % BLKSIZE) == 0);
	nblock = dir->f_size / BLKSIZE;
	//遍历 dir 中所有的块
	for (i = 0; i