linux0.11内核之文件系统

操作系统 文件系统

简述

linux0.11内核的文件系统主要参考了 Andrew S.Tanenbaum 所著的《操作系统：设计与实现》一书，使用了其中的MINIX1.0版。高速缓冲区的工作原理可以参考 M.J.Bach 的《UNIX操作系统设计》第三章内容。

一些细节

1. 一个i节点结构一共32个字节，所以释放该i节点时采用的方法是 menset(inode,0,sizeof(*inode)),即置i节点结构所占内存区为0.
2. i节点结构中的文件具体数据部分采用的是 unsigned short 类型，所以寻址能力是 $2^{16}$=65536bytes=64MB.而4G大小的内存应该使用$2^{32}$大小即4bytes来进行寻址。

总体功能描述

这个部分的代码可以从功能上分为四个部分：
1. 有关高速缓冲区的管理程序，主要实现了对硬盘等设备进行数据高速存取的函数。该部分内容集中在buffer.c程序中实现。
2. 文件系统的底层通用函数。说明了文件索引节点的管理、磁盘数据块的分配和释放以及文件名与i节点的转换算法
3. 对文件中数据进行读写操作的部分，包括对字符设备、管道、块读写文件中数据的访问
4. 与文件的系统调用接口的实现有关，主要涉及文件打开、关闭、创建、以及有关文件目录操作等的系统调用。

MINIX 文件系统（v1.0）

一个360KB软盘的结构图

MINIX文件系统和标准UNIX的文件系统基本相同，它由6个部分组成。对于一个360K的软盘，其各部分的分部如图所示。

图中，整个磁盘被划分为以1KB为单位的磁盘块，上图中每个方格代表一个磁盘块，在MINIX 1.0 文件系统中，其逻辑块大小和磁盘块大小正好都是 1 KB。

引导块

• 引导块是计算机加电启动时可由ROM BIOS自动读入的执行代码和数据。 但不是所有的盘都用作引导设备，所以对于不用于引导的盘片，可以不含代码块。 但任何盘片都必须含有引导块空间，以保证MINIX 文件系统格式的统一。 *如果你把内核映像文件放在文件系统中，那你就可以在文件系统所在设备的第1个块（即引导块空间）存放实际的引导程序， 并由它来取得和加载文件系统中的内核映像文件。

硬盘块设备

• 对于硬盘块设备，通常会在其上划分出几个分区，并且会在每个分区中都存放一个不同的完整文件系统，如图。硬盘的第一个扇区是主引导扇区，其中存放着硬盘引导程序和分区表信息。分区表中的信息指明了硬盘上每个分区的类型、在硬盘中起始位置参数和结束位置参数以及占用的扇区总数，具体参见 kernel/blk_drv/hd.c 文件后的硬盘分区表结构。

超级块

• 超级块：超级块用于存放盘设备上文件系统结构的信息，说明各部分的大小。 其结构如下图 .

• 注意 : 在linux0.11系统中，被加载的文件系统超级块保存在超级块表（数组）super_block[] 中。该表共有8项 （我也不知道为什么是 8 ），因此 Linux 0.11 系统中同时最多加载 8 个文件系统。超级块表将在 super.c 程序的 mount_root() 函数中被初始化， 在 read_super() 函数中会为新加载的文件系统 在表中设置一个超级块项， 并在put_super() 函数中释放超级块表中指定的超级块项。

逻辑块位图

• 逻辑块位图用于描述每个数据块的使用情况。除第1个比特位(位 0 )以外，逻辑块位图中每个比特位依次代表盘上数据区中的一个逻辑块（磁盘块）。比如 逻辑块位图的比特位 1 代表 盘上 数据区 中第一个数据盘块，而非盘上的第一个磁盘块（引导块）。当一个数据盘块被占用时，则逻辑块位图中相应比特位被置位。 由于当所有磁盘数据盘块都被占用时查找空闲盘块的函数会返回 0 值，因此 逻辑块位图 最低比特位 （位 0 ）闲置不用，并且会在创建文件系统时预先设置为 1.

• 从超级块的结构中得到，逻辑块位图最多使用8块缓冲块（s_zmap[8]），而每块缓冲块的大小是1024字节，每个比特表示一个盘块的占用状态，因此 一个缓冲块可代表8192个盘块，8个一共65536个盘块，64MB。所以MINIX文件系统1.0最大支持块设备容量为64MB。

i节点位图

• i节点位图用于说明 i 节点是否被使用， 同样是每个比特位代表一个 i 节点。 对于 1KB 大小的盘块来说，一个盘块 就可以表示 1024*8=8192 个 i 节点的使用状况。由于当所有 i 节点都被使用时 查找空闲 i 节点的函数会返回 0 值， 因此 i 节点位图的第一个字节的最低比特为（位0）和对应的 i 节点 0 都闲置不用 （即 从 i 节点 1 开始），并且在创建文件系统时 会预先把 i节点0对应比特位图中的比特置为 1 , i节点0的结构被初始化为全为0 .因此第一个 i 节点 只能表示 8191 个i节点的状况。

• 盘上的 i 节点部分存放着文件系统中文件或者目录名的索引节点，每个文件或者目录名下都有一个i节点。每个i节点结构中存放这对应为念的相关信息，如文件宿主的id（uid），文件所属组id（gid）、文件长度、访问修改时间以及为念数据块在盘上的位置等。整个结构共使用 32 个字节，结构如下图。

i_mode 字段

• i_mode 字段是用来保存文件的类型和访问权限属性的。具体如下图。下图中的数字为 8进制 。

文件的寻址

• 文件中的数据是放在磁盘块的数据区中的，而一个文件名则通过对应的 i 节点与这些数据磁盘块相联系，这些盘块的号码就存放在 i 节点的逻辑快数组 i_zone[] 中。其中， i_zone[] 数组用于存放i节点对应文件的盘块号。

• 从上图可以知道 最大支持 512*512+512+7=262663KB=256.5MB 一个文件。
• 之后会介绍MINIX v1.0之后的文件系统的架构。

关于逻辑块和磁盘块

• 对于pc机，一般以 一个扇区的长度（512字节）作为块设备的数据库长度。 而 MINIX文件系统则将连续的2个扇区数据 （1024字节） 作为一个数据块来处理，称之为一个磁盘块或者盘块。其长度与高速缓冲区中的缓冲块长度相同。而且编号是从盘上第一个盘块开始，也就是引导块为0号盘块。而一个逻辑块长度可以等于 1、2、4和8个盘块长度。但是在这个 Linux 内核中逻辑块的长度等于盘块长度。即在这里逻辑块和盘块两个术语含义相同，但是术语 数据逻辑块（或者数据盘块） 则是指盘设备上数据部分中， 从第一个数据盘块开始编号的盘块。

文件系统结构

MINIX文件系统的目录项结构定义在 include/linux/fs.h 文件中. 在文件系统的一个目录中， 其中所有文件名信息对应的目录项都存储在该目录文件名文件（即目录文件）的数据块中。
文件名目录项结构如下所示：

#define NAME_LEN 14          # 名字长度值
#define ROOT_INO 1           # 根 i 节点
# 大小 14 bytes
struct dir_entry{
    unsigned short inode;    # i 节点号  2 bytes
    char name[NAME_LEN];     # 文件名    14 bytes
};

从中可知：

• 一个磁盘块中能存储 1024/16=64 个目录项。
• 查找文件的过程如下：
• 初始的条件：
  
  • 查找的文件目录 /usr/bin/vi
  • i 节点号 inode = 1(根i节点号)
  • 匹配的 文件 nextfile=usr (初始条件) file = vi (最终匹配的文件)
  • 查找文件数据块的过程 在之前的内容中

文件的链接

如下图，是从文件名获取数据块的图示：

从上图可以知道：
1. 在文件系统中，不同目录中的文件可以是同一个 i 节点，即存储时只存储一份，然后在对应的目录数据块中加入对应的目录项。
2. 每个i节点结构中都有一个链接计数字段 i_nlinks 记录着指向该i节点的目录项数，即文件的 硬链接数 。
3. 在执行删除文件的操作时， 只有当i节点链接计数值等于0时内核才会真正删除磁盘上该文件的数据。

硬链接

• 硬链接就是之前所说的：在对应的目录项中加入被链接文件的目录项。因此 对于同一份文件，每一个指向于该文件的硬链接都是平等的。
• 每一个硬链接都会使 i_nlinks 加1
• 因为i节点只适用于当前文件系统，所以硬链接不能跨越文件系统。

软链接（符号链接）

• 与硬链接不同，符号链接不是直接指向对应的i节点，而是在对应文件的数据块中存放 某一文件的 路径字符串 。当访问 符号链接目录项时，内核就会读取该文件中的内容，依据其中的路径字符串来访问指定的文件。
• 符号链接不局限于一个文件系统。

特殊的文件目录项

在每个目录中还包括两个特殊的文件目录项，分别是 '.' ,'..'。

• '.' 目录项给出了当前目录的i节点号。

• '..' 目录项给出了父目录的i节点号。不过root目录的呢？

重要

• 目录文件j中的目录项也算是链接到j目录文件的连接数
• 每个目录文件中的链接数 i_nlinks 最小为 2（'.','..'）
• 那 如何删除文件？因为当文件的 链接数为0时才会真正删除文件， 但是文件的链接数最少为2。所以只有删除'.', '..' 链接才能真正删除文件 ??????

缓冲区

高速缓冲区

是文件系统访问块设备中数据的必经要道，是为了提高系统性能而设计的。

简述

• 在linux系统内核中，高速缓冲区位于内核代码和主内存区之间。如下图

• 高速缓冲区中存放着 最近被使用过的各个块设备中的数据库。
• 当需要从块设备中读取数据时，缓冲区管理程序会首先从高速缓冲区中寻找，找不到再从块设备中读取。
• 当需要把数据写入到块设备中去时，系统就会在高速缓冲区中申请一块空闲的缓冲块（大小：1KB）来临时存放这些数据。数据真正写入到设备中去是通过设备数据同步实现的
• 实现的程序在 buffer.c 中。

文件系统底层函数

文件系统的底层处理函数包括在以下5个文件中：

bitmap.c

包括对 i节点位图和逻辑块位图进行释放和占用处理函数。

truncate.c

包括对数据文件长度截断为0的函数 truncate().这个函数将i节点指定的设备上文件长度截为0，并释放文件数据占用的设备逻辑块。

inode.c

包括分配i节点函数 iget()和放回对内存i节点存取函数 iput() 以及根据i节点信息取文件数据块在设备上对应的逻辑块号函数 bmap()

namei.c

主要包括函数 namei().该函数使用 iget()、iput()、bmap()将给定的文件路径名映射到其 i节点。

super.c

专门用于处理文件系统超级块，包括 函数 get_super(),put_super(),free_super()等。还包括几个文件系统加载/卸载处理函数和系统调用，如sys_mount()等

这些文件中函数之间的层次关系如下图所示：

文件中数据的访问操作

关于文件中数据的访问操作，主要涉及5个文件：blk_dev.c,file_dev.c,char_dev.c,pipe.c和read_write.c。前四个可以认为是块设备、普通文件、字符设备、管道设备与文件读写系统调用的接口程序， 它们共同实现了read_write.c 中的read()和write()系统调用。 通过对被操作文件属性的判断，这两个系统调用会分别调用这些文件中的相关处理函数进行操作。这些函数之间的关系如下图：

block_dev.c

• block_dev.c 中的函数 block_read()和block_write()是用于读写块设备特殊文件中的数据，使用的参数指定了 要访问的设备号、读写的起始位置和长度。

file_dev.c

• file_dev.c 中的file_read()和file_write()函数是用来访问一般的正规文件，通过文件名获取对应的i节点号和文件信息，从而进行读写操作。

pipe.c

管道

管道主要用于在进程之间按照先进先出的方式传送数据，也可以用于使进程同步执行。

• 分类：
  
  • 有名管道，是使用文件系统的open调用建立的
  • 无名管道，使用系统调用 pipe()创建的
• 使用管道：用正规问文件的read()、write()、close()函数。 只有发出pipe调用的后代才能共享对无名管道的存取，而所有进程只要权限许可，都可以访问有名管道
• 与一般正规文件存取相比：内核存取管道中数据的方式不同，管道只使用i节点的直接块，不分配数据块(not sure)。内核直接将 i节点的直接块当作一个循环队列来管理，通过修改读写指针来保证先进先出的顺序。
• pipe.c 实现了管道读写函数read_pipe()和write_pipe().另外还实现了创建无名管道的系统调用 pipe().

char_dev.c

• 字符设备包括控制台终端(tty),串口终端(ttyx)和内存字符设备。
• 对于字符设备文件，系统调用read()与write()会调用char_dev.c中的 rw_char() 函数来操作。

实现机制

• 一些数据结构

  • 文件结构 file

  struct file{
      unsigned short f_mode;       // 文件类型和访问属性,和文件i节点结构中i_mode字段的含义相同
      unsigned short f_flags;      // 文件打开和控制的标志， 标志定义在下文有说明
      unsigned short f_count;      // 对应文件句柄引用计数
      struct m_inode * f_inode;    // 指向对应内存i节点，即内存i节点表中
      off_t f_pos;                 // 文件当前读写指针位置
  };

  它用于在文件句柄和内存i节点表i节点项之间建立联系。
  f_flags 字段标志定义

  // 打开文件open()和文件控制函数 fcntl()使用的文件访问模式，同时只能使用三者之一
  #define 0_RDONLY 00     // 以只读方式打开文件
  #define 0_WRONLY 01     // 以只写方式打开文件
  #define 0_RDWR   02     // 以读写方式打开文件
  // 下面是文件创建和操作标志，用于open().可以与上面访问模式用'位或'的方式一起使用
  #define 0_CREAT  00100  // 如果文件不存在就创建。fcntl函数不用
  #define 0_EXCL   00200  // 独占使用文件标志
  #define 0_NOCTTY 00400  // 不分配控制终端
  #define 0_TRUNC  01000  // 若文件已存在且是写操作，则长度截为0
  #define 0_APPEND 02000  // 以添加方式打开，文件指针置为文件尾
  #define 0_NONBLOCK 04000 // 非阻塞方式打开和操作文件
  #define 0_NDELAY 0_NONBLOCK // 非阻塞方式打开和操作文件 ？

  • 文件表 file 最长为64项，所以整个系统同时最多能打开64个文件。

    struct file file_table[NR_FILE]  // 文件表数组， NR_FILE = 64

  • 进程的数据结构（ 进程控制块 或者 进程描述符 ）中专门定义了本进程打开文件的文件结构指针数组 filp[NR_OPEN] 字段。其中 NR_OPEN=20。因此每个进程最多可同时打开20个文件。

  • 内核中i节点表 inode_table[NR_INODE]是由内存i节点结构组成的数组，其中NR_INODE=32,因此在某一时刻内核中同时只能保存32个内存i节点信息。
• 一个进程打开的文件和内核文件表以及对应内存i节点的关系如下图所示

文件系统调用的上层实现

主要有五个文件，其层次结构如下图：

• open.c 文件用于实现与文件操作相关的系统调用。主要有文件的创建、打开和关闭，文件宿主和属性的修改、文件访问权限的修改、文件操作时间的修改和系统文件结构root的变动等
• exec.c 程序实现对二进制可执行文件和 shell 脚本文件的加载和执行。其中主要的函数是函数do_execve(),它是系统中断调用(int 0x80)功能号_NR_execve()调用的c处理函数，是 exec() 函数簇的主要实现函数。
• fcntl.c 实现了文件控制系统调用 fcntl()和两个文件句柄(描述符)复制系统调用 dup() 和 dup2()。dup2()指定了新句柄的数值，而dup()则返回当前值最小的未用句柄。句柄复制操作主要用在文件的标准输入/输出重定向和管道操作方面。
• ioctl.c 文件实现了输入/输出控制系统调用ioctl() 。主要调用 tty_ioctl() 函数，对终端的I/O进行控制。
• stat.c 文件用于实现取文件状态信息系统调用 stat() 和 fstat().stat() 是利用文件名取信息。而 fstat() 是使用文件句柄来取信息。

360KB软盘中文件系统实例分析

创建

利用linux0.11 系统在 360KB规格软盘映像中使用 mkfs 命令建立一个MINIXv1.0文件系统，其中只存放了一个名为hello.c的文件。

软盘数据

引导块部分

从之前的描述可以知道，MINIX 1.0 文件系统中 第1个盘块是 一个引导盘块。而且无论这个盘是否是引导盘，都会有引导盘块。对于这个例子，引导盘块应该全部为0，但是由于数据的遗留，所以没有全部为0.

超级块部分

超级块

是记录文件系统信息的。

盘块(0x0400-0x07ff,1KB)是超级块部分。我们已经知道超级块数据结构中共有18个字节中含有有效内容。由于每逻辑块对磁盘块的大小之比的对数值为 0， 所以 逻辑块大小等于 磁盘块大小。
具体数据如下

i节点位图

• 盘块2(0x0800-0x0bff,1KB)包括i节点位图信息。由于只用120个i节点，所以只占用 120/8=15个字节。其中 0 表示未被占用， 1 表示被占用或者保留。盘块中其他不用的字节比特位 均被 mkfs 命令初始化为 1.
• 从 软盘数据中可以得到，有效数据只有:0x0007,除去第一个比特位（位0）保留不用。说明只占用了两个i节点：1号和2号。实际上，1号节点 被用作文件系统的根root节点，2号节点被用作 hello.c文件。

逻辑块位图

• 盘块3(0x0c00 - 0x0fff,1KB)是逻辑块位图内容。由于文件系统只有 360KB大小 。即 360/8 = 45 个字节。但是由于 逻辑块位图只表示 数据区中盘块占用的情况， 所以除去 非数据区盘块(8个)，再加上第一个比特位(位0)保留不用，实际上使用的容量为 360 - 8 + 1 = 353 bits.
  所以最后一个(第 45)字节(0xfe）只有1个比特位为0.
• 逻辑块位图中比特位偏移值 nr 和 对应磁盘上盘块号 block 的换算

block = nr + s_firstdatazone - 1
nr = blcok - s_firstdatazone + 1

i节点结构信息

• 盘块4-7(0x1000 - 0x1fff, 4KB)4个盘块专门用来存放i节点结构信息。因为共有 120个i节点，而每个i节点占用 32 个字节。所以共需要 120 x 32 = 3840 bytes,即占用4个盘块。
• 由 i节点位图可以知道，已经有了两个i节点1和2.具体信息如下：

• 由上表可知，
  
  • i_zone[] 中存的 数值不是只计算数据区,而是盘块号。即 0x0008 表示 盘块8.
  • 根 i 节点结构内容中， 目录项为48/16=3个，但是 链接数 为3.?

数据区

• 盘块8(0x2000-0x23ff,1KB)就是1号根i节点的数据。其中 存有48个字节的3个目录项结构信息。具体如下：

• 盘块9(0x2400-0x27ff,1KB)是 hello.c文件内容，长度 74字节。

代码分析

问题