OS-Lab5

一.全局变量名词解释

#define NBLOCK 1024 //一块磁盘里面的block数目
uint32_t nbitblock; // 用于存储bitmap的block数目
uint32_t nextbno;   // 下一块可用的block编号

struct Super super; // 超级块
struct Block {
    uint8_t data[BY2BLK];
    uint32_t type;
} disk[NBLOCK];

///////////////////下面的内容在include里面的fs.h里面
#define BY2BLK		BY2PG//一个block对应的字节，也就是说，一个block正好等于一页大小
#define BIT2BLK		(BY2BLK*8)//一个block对应的*位数*，一字节等于8位，所以要乘8

#define MAXNAMELEN	128//用于存文件名的char数组大小，由于最后一个必定为'\0',所以只能存127个字符
#define MAXPATHLEN	1024//和上面的类似，只不过是用来存路径的

#define NDIRECT		10//直接引用的个数，可以认为是10个指针，这里用int存block的下标来代替了指针的作用
#define NINDIRECT	(BY2BLK/4)//间接引用块的指针个数，由于一个int是32位，也就是4byte，所以是除4

#define MAXFILESIZE	(NINDIRECT*BY2BLK)//最大文件大小，那么就是引用指针的个数*一块大小

#define BY2FILE     256//定义了一个FIle结构体（文件索引结构体）所占用的大小，实际上比FILE结构体实际占用大小要大，是为了保持扩展性？

struct File {//文件索引结构体
	u_char f_name[MAXNAMELEN];	// 文件名
	u_int f_size;			// 文件大小（字节），其实就是引用块所占的总大小
	u_int f_type;			// 文件类型，有两种，一种是普通文件，一种是目录
	u_int f_direct[NDIRECT];//直接引用指针
	u_int f_indirect;//指向间接引用块

	struct File *f_dir;		// 指向包含这个文件的目录，只在内存中存在着（真正写入文件之后没有这部分）
	u_char f_pad[BY2FILE - MAXNAMELEN - 4 - 4 - NDIRECT * 4 - 4 - 4];//为了填满by2file，而开了这部分内容
};

#define FILE2BLK	(BY2BLK/sizeof(struct File))//就是一个block能容纳多少个file索引

// File types
#define FTYPE_REG		0	// 普通文件
#define FTYPE_DIR		1	// 目录


// File system super-block (both in-memory and on-disk)

#define FS_MAGIC	0x68286097	// 神秘代码，用来表示这是个合法的文件

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

二.实验难点图示

1.文件系统层次关系梳理

文件系统可以分成四个层次：

文件系统用户接口、文件系统抽象层、文件系统具体实现、文件系统设备接口。

文件系统的逐级调用关系可以用下图表示：

2.多级目录与多级索引

多级目录用来管理文件间的层次关系，多级索引用来管理单个文件的数据。两者并不是一个概念。

在我们的实验中，目录文件的内容是文件控制块struct File，目录文件的每一个数据块由16个文件目录项组成，找到相应的文件名，找到对应文件的FCB，进而找到该文件的数据块。

多级索引用来管理文件的数据块，我们的实验中使用二级索引机制。在FCB中可以有一级索引数组f_direct[NDIRECT]，和一个二级索引f_indirect，二级索引找到的磁盘块为索引块，这个磁盘块可以存储1024的FCB。

目录文件综合体现了这一点，以下图来说明：

三.代码梳理

1.磁盘管理

完成文件系统的第一步就是要能够处理磁盘等外设的信息。

• lib/syscall_all.c

  处理磁盘的信息，最基本的就是对磁盘进行读写操作。
  sys_write_dev函数用于对外设进行写操作。首先是检查地址的合法性，写入的这段地址需要在规定地址范围之内，接着使用bcopy把数据复制过去即可。
  sys_read_dev函数用于读操作。过程与写类似。

• fs/ide.c

  在实现了对外设基本的读写后，对于磁盘，为了方便上层用户操作，还需要一个封装好的磁盘驱动程序，也就是这里的ide_read和ide_write函数。
  ide_read函数用于从特定的磁盘块读取一定量的数据。首先需要做的就是根据起始扇区和扇区数计算首尾地址，接着是循环读取数据，具体来说首先是向控制磁盘的几个地址写入对应的信息，接着检查磁盘状态，如果正常则读取一个扇区。
  ide_write函数和ide_read函数类似，不同在于，读取磁盘状态是在写操作结束后读取检查。

  

• fs/fs.c

  完成了磁盘读写后，我们需要对磁盘的信息进行管理，也就是对磁盘块的使用状态进行管理。

  

  磁盘最开始的一个扇区被当成是启动扇区和分区表使用；接着是一个超级块，这个超级块结构体定义在include/fs.h中，里面定义了魔数、磁盘块数量和根目录的文件控制块。接下来存储的是位图信息，用来记录磁盘块的使用信息，每一个二进制位到代表了一个磁盘块。剩余的内容都是存储数据的数据块。

  diskaddr函数用于求出某一个磁盘块的地址。首先需要判断磁盘块号的合法性，接着计算偏移加上基地址即可。块大小为BY2BLK。
  block_is_mapped函数用于检查这个块是否已经映射到了页表中。也就是通过diskaddr计算出地址后使用va_is_mapped检查是否存在于页表。
  block_is_dirty函数用于确定这个块的数据是否已经被修改。具体做法类似，检查页表项的PTE_D标志位即可。
  map_block函数用于分配一页内存映射到一个数据块。首先检查这个数据块是否已经映射，没被映射再使用syscall_mem_alloc完成映射。
  unmap_block函数用于移除数据块的映射关系。首先检查这个数据块是否被映射了；然后检查这个数据块是否被修改过，如果被修改了则需要把数据写入到磁盘块中；接着使用syscall_mem_unmap移除映射关系。
  read_block函数用于读入数据块的数据到内存中。首先需要判断数据块号合法性和数据块是否被使用；然后取得数据块地址；检查这个数据块是否在内存中，如果不在则需要分配一页映射到数据块，然后调用ide_read读入数据；检查blk是否为NULL，如果不是则把虚拟地址赋值。
  write_block函数用于把内存数据块的信息写入到磁盘中。首先判断数据块是否被映射；取得地址后调用ide_write写磁盘块，最后移除这个映射。
  block_is_free函数用于判断数据块是否被释放。具体来说就是检查位图对应的信息是否为1。
  free_block函数用于释放一个数据块，更新位图。也就是将位图的信息置0。
  alloc_block_num函数用于查找分配一个空闲的数据块。也就是从3号开始，搜索位图检查是否有空闲的数据块，并返回空闲数据块号。
  alloc_block函数用于获得一个空闲数据块并映射到内存中。首先通过alloc_block_num获得一个空闲的磁盘块号，然后将对应的磁盘用map_block映射到内存中。
  read_super用于读取和检验超级块。首先使用read_block将超级块信息读入内存；然后检查魔数；最后检查磁盘大小信息是否吻合。
  read_bitmap用于读取和检查位图。类似的，首先是读入位图，然后检查前两个磁盘块是否在使用，最后检查位图块全部在使用。
  check_write_block用于检查wrtie_block函数功能正常。

  到这里，磁盘块的管理操作就完成了。

2.文件系统

磁盘管理完成后，就可以在这个基础上完成文件系统的搭建了。

首先是管理文件的文件控制块File。这个结构体定义在include/fs.h中，定义了文件名、文件大小、文件类型、文件数据块索引、文件上级目录，为了保证每个文件控制块大小固定，还设置了f_pad，用填充0的方法，保证了文件控制块大小为256字节。

• fs/fsformat.c

  这个文件中定义了实验的文件系统的形式。里面定义了初始化磁盘、大端转换为小端、刷新位图等操作。

  reverse函数用于将大端存储的数据转换为小端格式。
  reverse_block函数用于将磁盘块的数据格式都转换过来。
  init_disk函数用于初始化磁盘。
  flush_bitmap函数用于刷新位图。
  finish_fs函数用于将设置好的磁盘写入到镜像文件中。
  save_block_link函数用于将被引用的磁盘块存进文件的索引中。
  make_link_block用于建立一个新的数据块引用。
  create_file用于在给定的目录中创建一个新的文件控制块指针。简单来说就是找到一个数据块中的空闲的文件索引，也就是没有存储信息的文件控制块，返回这个地址；如果没有数据块或者没找到空闲索引则使用make_link_block加入一个新的数据块。
  write_file用于在给定的目录下的一个文件写入到磁盘中。

  通过了解这个文件，我们大概了解了文件和磁盘的关系。

• fs/fs.c

  接下来我们就来完成具体的文件和磁盘交互的函数。

  fs_init函数完成了文件系统的初始化，也就是检查了超级块等信息是否正常。
  file_block_walk函数用于查找一个文件中某个文件块所在的磁盘块，并返回磁盘块的虚拟地址，这里所指的文件块就是文件控制块中索引的数据块。对于在直接索引中的文件块，直接返回那个块的地址即可；对于间接索引，如果没有间接索引且需要分配一个数据块，则使用alloc_block分配一个数据块，否则就报错，然后用read_block把这个块读入内存中，获得这个块的虚拟地址，加上文件块号的偏移；最后返回磁盘块的虚拟地址。
  file_map_block函数用于设置*diskbno为指定的文件块，也就是用一个。首先通过file_block_walk找到需要的文件块，如果没有且alloc被置位，则需要新建一个索引块，最后将这个块的编号赋给*diskbno。
  file_clear_block函数用于用于把一个文件块从文件中移除。先找到这个块，然后使用free_block释放这个块。
  file_get_block函数用于将文件块的数据读入blk中，也就是将*blk指向这个文件块。首先是用file_map_block找到磁盘块号，接着用read_block将这个块的地址赋给blk。
  file_dirty函数用于标记某个块为dirty。*(volatile char *)blk = *(volatile char *)blk;，这个倒是很神奇的一条语句，我也不知道怎么就能标记为dirty。
  dir_lookup函数用于查找目录下指定文件名的文件。做法也很简单，就是遍历目录文件的所有文件块，通过file_get_block读取数据，再检查这个块内所有文件控制块的文件名是否符合。
  dir_alloc_file函数用于在特定的目录下建立一个新的文件控制块。过程与dir_lookup类似，找到一个空白的文件控制块返回地址即可，而如果没找到，则需要建立新的文件块存放。
  walk_path函数用于给定一个路径，查找这个路径指向的文件。简单来说就是每一级目录查找下一级目录是否存在，直到找到目标文件。
  file_open函数利用walk_path函数实现打开一个给定路径的文件，也就是返回这个文件控制块的地址。
  file_create函数根据给出的路径创建对应的文件。做法就是通过walk_path找到文件地址，然后使用dir_alloc_file建立一个文件控制块，最后把文件名复制到对应的变量。
  file_truncate函数用于把一个文件截断到一个新的大小。做法也很容易，计算出前后两个文件块的数量，然后使用file_clear_block删除文件块即可，最后设置新的文件大小。
  file_set_size函数完成了将一个文件设置为新的大小。对于大于这个大小的文件，使用file_truncate截断文件，然后需要利用file_flush刷新文件所在的目录。
  file_flush函数用于更新磁盘的内容，具体做法就是遍历文件的所有文件块，检查每个文件块是否为dirty，然后写入磁盘。
  fs_sync函数则是刷新整个文件系统所有文件。
  file_close函数则是为关闭文件做准备，也就是将文件和所在目录刷新。
  file_remove函数则是删除一个文件。首先是通过walk_path找到文件，接着通过file_truncate将文件大小减到0，也就是删掉了文件内容，接着把文件名删除，最后更新这个文件和所在的目录。

  到这里，我们已经能够进行查找文件、删除文件、更新文件(或许保存更贴切？)等宏观的操作，完成了文件系统与磁盘的接口。但对于用户来说，具体打开一个文件，对一个文件进行细致的读写操作我们还没有实现。

3.用户接口

接下来我们需要设计文件系统与用户的交互接口，对于用户来说，对文件的操作无外乎打开、读写、关闭等操作，而并不太关心文件索引块的信息，因此就有了一个新的结构体：文件描述符Fd。但在此之前，先来看另一个结构体Dev。
Dev结构体定义了一个外设的信息，如外设的编号、外设名、外设的读写等函数指针。在这个操作系统中，对外设的读写在用户层面来看可以认为就是读写一个文件，而每一种外设都有自己的特定读写函数，我猜测这些信息都存放在了设备控制表中。
接下来来看文件描述符Fd。这个结构体首先定义了fd_dev_id，这个指的是文件所在的设备编号，与Dev应该是对应的，接着是fd_offset，这个变量存放着文件读写头的位置，也就是当前读写文件的指针相对于文件头的偏移，最后是fd_omode，这个指的是文件打开的类型，比如只读、只写、读写。

• 在这个文件中定义了一系列与Fd有关的函数。在文件的开头定义了全局变量devtab，也就是这个操作系统中支持的三种设备：文件devfile、终端devcons、管道devpipe。

  dev_lookup函数用于根据设备编号查找设备，也就是在devtab中查找设备。
  fd_alloc函数用于分配一个空闲的描述符。具体做法就是找到没有被使用的页面返回其地址。
  fd_close函数用于关闭一个文件描述符。具体做法就是移除所在页面的映射关系。
  fd_lookup函数用于根据一个文件描述符的编号得到对应的文件描述符。先检查编号的合法性，接着通过INDEX2FD获得描述符的地址，检查对应描述符的页表项有效后返回地址即可。
  fd2data函数通过给定的文件描述符返回文件起始数据地址。
  fd2num函数通过给定的描述符返回其编号。
  num2fd函数通过编号得到描述符。
  close函数通过给定的编号关闭对应的描述符。首先是获得文件描述符和设备；接着关闭设备和文件描述符。
  close_all是关闭所有的文件描述符。
  dup函数用于将一个文件复制到一个新的文件中。首先是找到旧的文件描述符，接着关闭新的描述符，获得新的描述符(这个操作到lab6就清楚了)；接着把旧的描述符映射到新的描述符处；最后把相关的页面都映射过去。
  read函数用于从fd_offset处读取n字节到buf中。同样，先找到描述符和设备；接着检查打开模式fd_omode是否有权限；然后调用*dev_read读取内容，更新fd_offset后返回。这个函数不一定最终会读取n字节。
  readn函数与read函数类似，不过这个函数只有在读取n字节后才会结束。具体来说就是不断调用read使得最后读取的字节数达到n。
  write函数与read类似，操作也基本一致，将读换成写即可。
  seek函数用于调整文件的读写头到指定位置，具体来说就是修改fd_offset。

  到这里，我们就能够通过操作文件描述符来进行对文件内容的读写操作了。但是具体到每一个设备，我们还需要补全具体设备的相关函数即*dev_read等才能实现在用户界面对外设的读写。对于文件类的外设，具体的函数定义在了user/file.c中。

在具体实现文件类外设的读写时，实际上并不是直接操作File，而是通过文件系统来完成，为了方便与文件系统交互又设计了一种结构体Filefd，简单来说就是结合了Fd和File的结构体。这样即能够获取文件与用户的交互信息Fd，又能够知道文件与磁盘的交互信息File。而更精巧的是，得到Filefd并不困难，可以直接通过结构体的强制转换，从Fd转到Filefd，原因就在于Filefd利用Fd占位，这样就保证了后面的变量f_fileid和f_file访问地址正确。

• user/file.c

  文件的开头完善了devfile的信息。具体实现在下面。

  open函数实现了根据路径和模式打开一个文件。首先需要通过fd_alloc获得一个文件描述符；接着通过fsipc_open请求文件系统打开文件；接下来通过强制转换得到Filefd，设置相关的变量；最后请求文件系统分配内存将文件载入到内存中，返回描述符编号。
  file_close函数则是关闭一个文件。首先是获得Filefd的信息，接着得到文件数据的起始地址；遍历整个文件，请求文件系统处理dirty信息；请求文件系统关闭文件；如果这时的size还不为0，则需要手动通过syscall_mem_unmap移除文件的映射关系。
  file_read函数用于读取n字节信息。首先是得到文件的大小，检查能不能读n字节；如果可以，则使用user_bcopy将文件的信息复制到buf中。
  read_map函数用于找到文件内容所在的文件块。首先找到描述符，判断设备编号是否吻合，接着利用fd2data找到地址，判断这个地址是否有效，最后返回这个地址。
  file_write函数用于向当前读写的位置写入n字节数据。首先是利用ftruncate将文件扩大，接着把内容写到指定的位置。
  ftruncate函数用于截断或增长文件。首先找到文件描述符转成Filefd；接着请求文件系统申请更多的页面来存储信息或者使用系统调用移除多余的映射。
  remove函数用于删除文件或目录。
  sync函数用于更新磁盘。

  到这里我们就完成了对于文件类设备的各种常用操作。但在开头我也提到，这些操作都需要请求文件系统才能完成。因此我们还缺少处理这些请求的函数。这些函数主要在user/fsipc.c和fs/serv.c中。

4.文件服务

服务分为两部分，一边是用户程序将各种请求分类，统一成fsipc和请求类型发送给文件系统，一边是文件系统通过传入的请求类型进入相应的处理函数进行处理。

• user/fsipc.c

  这个文件就定义了一系列发送请求的函数，最终都统一成fsipc函数发送。

  fsipc函数就是最终发送请求的函数，通过进程间通信完成，也就是利用ipc_send向文件系统进程发送信息，然后利用ipc_recv返回处理结果。
  而剩下的函数则大同小异，都是预处理一些信息，然后调用fsipc完成。

• fs/serv.c

  这个文件定义了文件系统处理一系列请求的函数。主体函数是serve函数，这个函数是一个死循环，不断通过ipc_recv接收请求，申请一页临时处理内存，根据请求类型调用对应的处理函数完成处理，最后释放这块内存。

  在文件开头定义了一个结构体Open，这个结构体就是文件系统内部处理文件时描述文件的结构体，包含了文件控制块、文件编号、打开方式、Filefd。从这里我们会发现，对于同一个文件，不同的视角来看，就会有不同的信息，比如底层看到的是文件控制块File，用户看到的是描述符Fd和Filefd，文件服务系统看到的是Open。

  serve_init函数用于初始化文件服务进程。
  open_alloc函数用于分配一个Open，也就是找到一个空闲的Open结构体。
  open_lookup函数用于查找一个进程打开的文件。

  serve_open函数用于处理打开文件的请求。首先得到文件路径，然后分配一个Open结构体，接着调用file_open打开文件，最后天写相关的信息，再通过ipc_send发回给用户进程即可。
  serve_map函数用于获得一个数据块。首先用open_lookup查找文件的Open结构体，接着计算需要查找的文件块，并通过file_get_block获得，把结果发送给用户。
  剩下的函数基本是一个写法，通过open_lookup查找文件信息，调用fs.c中的函数完成具体处理，再通过ipc_send返回信息给用户进程。

到这里，用户进程与文件服务系统进程的交互也完成了，现在一个用户进程就能够完成从磁盘读取一个文件、加载到内存中、打开这个文件对文件进行读写操作、并写回磁盘关闭文件的完整操作。文件系统就算是搭建完成了。