• 本篇为持久化技术的基础篇系列第三篇(文件与目录)。

Chapter Index

Files and Directories

  • CRUX:如何管理持久化存储设备?
    • 操作系统如何管理持久化存储设备
    • APIs 是什么样的
    • 实现的重要方面有哪些?

Files and Directories

  • Process 是 CPU 的虚拟化表现形式,Address Space 是内存的虚拟化表现形式,而存储的虚拟化表现形式即为 Files and Directories.
  • 文件 只是一个线性字节数组,每个字节都可以读写。文件通常会有一个 low-level 的名称,没有显示地暴露给用户,通常是指 inode number. 操作系统不知道文件的具体结构,而文件系统的作用就是保证你读取数据时和你当初存取时的数据完全一样,实现起来看似容易实则复杂。
  • 目录 也会有一个 low-level 的名称,如 inode number。但是相比于文件,目录的内容更为具体,即一些 low-level name 和用户可读 name 的数据对。比如,有一个文件 low-level name 为 “10”, user-readable name 为 “foo”,其所在的目录就将包含一个数据对信息 (“foo”, “10”)。目录中的每一个数据对都会有对应的文件或者子目录,从而形成一个目录树结构。
  • 目录树起始于 root 目录(基于 UNIX 的系统的根目录通常为 /),使用某种分隔符来命名后续的子目录,直到指定所需的文件或目录为止。而文件名又由两部分组成,以 . 进行分割,前半部分为文件的名称,后半部分为文件的格式。
  • 因此,在UNIX系统中,文件系统提供了一种统一的方式来访问磁盘、u盘、CD-ROM、许多其他设备上的文件,实际上还有许多其他东西上的文件,这些文件都位于单个目录树下
    20200721100631

The File System Interface

  • creating, accessing, and deleting files

Creating Files

  • 系统调用 open(),通过传递 O_CREAT 标识来创建文件。返回文件描述符。
int fd = open("foo", O_CREAT|O_WRONLY|O_TRUNC, S_IRUSR|S_IWUSR);
  • 参数解释:
    • O_CREAT:如果文件不存在则创建文件
    • O_WRONLY:文件只能被写入
    • O_TRUNC:如果文件已经存在,则将其截断为零字节大小,从而删除任何现有内容
    • S_IRUSR|S_IWUSR:第三个参数指定权限,在本例中使文件所有者可读和可写
  • 操作系统按进程管理文件描述符,一个文件描述符本质就是一个数字,每个进程都是私有的,在 UNIX 中用于访问文件。所以在进程对应的数据结构中,相应地保存了对应的文件描述符:最多保存 NOFILE 个描述符
struct proc {
  ...
  struct file *ofile[NOFILE]; // Open files
  ...
};

Reading And Writing Files

prompt> echo hello > foo
prompt> cat foo
hello
prompt>
  • 使用 strace 追踪命令 cat
    • 首先打开文件 open,只读模式 O_RDONLY,使用64位偏移量 O_LARGEFILE,返回了一个值为 3 的文件描述符。
      • 为什么返回 3,不是返回 0 或 1?因为每个运行的进程已经打开了三个文件,分别是标准输入(进程可以读取以接收输入)、标准输出(进程可以写入以将信息转储到屏幕上)和标准错误(进程可以向其中写入错误消息),分别对应了 0,1,2
    • read 读系统调用重复地从一个文件中读取一些字节:第一个参数对应文件描述符,表明读取哪一个文件,第二个参数执行了一个缓冲区,用于存放读取之后的数据,使用 strace 则显示了对应的读取结果;第三个参数对应缓冲区的大小 4KB,返回值为读取的数据的字节大写,即 hello 5 个字节加上 \n 共 6 字节。
    • write 将读取到的字符串写到标准输出的文件描述符中,但可能不是直接调用 write 系统调用,可能使用了 printf 封装进行格式化输出,最终再调用了 write
    • 然后继续 read,但是因为文件没有额外的数据需要读取,返回 0 即告知程序数据该文件数据读取结束
    • close 关闭读取完了的文件描述符,至此整个文件读取完毕。
prompt> strace cat foo
...
open("foo", O_RDONLY|O_LARGEFILE) = 3
read(3, "hello\n", 4096) = 6
write(1, "hello\n", 6) = 6
hello
read(3, "", 4096) = 0
close(3) = 0
...
prompt>
  • 写操作采用了类似的步骤,首先打开相应的文件,然后调用写操作,大文件可能会重复执行写操作很多次,最后关闭该文件。可以使用 strace 相应的操作,也可以追踪自己编写的程序。
[[email protected] shunzitest]# strace echo hello > foo
execve("/usr/bin/echo", ["echo", "hello"], [/* 32 vars */]) = 0
brk(NULL)                               = 0x802000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7efd61a1e000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=104858, ...}) = 0
mmap(NULL, 104858, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7efd61a04000
close(3)                                = 0
open("/lib64/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\340$\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=2151672, ...}) = 0
mmap(NULL, 3981792, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7efd61431000
mprotect(0x7efd615f3000, 2097152, PROT_NONE) = 0
mmap(0x7efd617f3000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1c2000) = 0x7efd617f3000
mmap(0x7efd617f9000, 16864, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7efd617f9000
close(3)                                = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7efd61a03000
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7efd61a01000
arch_prctl(ARCH_SET_FS, 0x7efd61a01740) = 0
mprotect(0x7efd617f3000, 16384, PROT_READ) = 0
mprotect(0x606000, 4096, PROT_READ)     = 0
mprotect(0x7efd61a1f000, 4096, PROT_READ) = 0
munmap(0x7efd61a04000, 104858)          = 0
brk(NULL)                               = 0x802000
brk(0x823000)                           = 0x823000
brk(NULL)                               = 0x823000
open("/usr/lib/locale/locale-archive", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=106075056, ...}) = 0
mmap(NULL, 106075056, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7efd5af07000
close(3)                                = 0
fstat(1, {st_mode=S_IFREG|0644, st_size=0, ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7efd61a1d000
write(1, "hello\n", 6)                  = 6
close(1)                                = 0
munmap(0x7efd61a1d000, 4096)            = 0
close(2)                                = 0
exit_group(0)                           = ?
+++ exited with 0 +++

OPEN FILE TABLE:每个进程维护一个文件描述符数组,每个描述符引用系统范围内打开的文件表中的一个条目。该表中的每个条目跟踪描述符引用的基础文件、当前偏移量和其他相关细节,比如文件是可读还是可写。

Reading And Writing, But Not Sequentially

  • 目前讨论的读写都是顺序的,即必须从头到尾的读取或者写入文件。然后有的场景里,在指定偏移量上进行读写是很有必要的,例如索引查找,很可能是随机的。此时将使用到 lseek
    • 参数一 fildes 文件描述符
    • 参数二 offset 在文件中的偏移量
    • 参数三 whence 决定 seek 如何进行
      • whence is SEEK_SET 参数 offset 即为新的读写位置
      • whence is SEEK_CUR 以目前的读写位置往后增加 offset 个位移量
      • whence is SEEK_END 将读写位置指向文件尾后再增加 offset 个位移量.
off_t lseek(int fildes, off_t offset, int whence);
  • 偏移量存储在进程对应的文件描述符的文件数据结构中:
struct file {
  int ref; // 引用计数
  char readable; // 可读
  char writable; // 可写
  struct inode *ip; // inode pointer
  uint off; // offset
};

lseek vs seek:调用 lseek 操作不会执行磁盘的 seek 操作,lseek() 调用只是更改操作系统内存中的一个变量,该变量为特定进程跟踪下一个读或写偏移量的起始位置,磁盘的 seek 是当对磁盘发出的读或写不在与最近一次读或写在同一轨道上的时候。调用lseek()可能导致在即将进行的读或写中进行查找,但绝对不会导致任何磁盘I/O本身发生。

  • 这些数据结构合在一起有时候又被称作 open file table,xv6 内核会以数组的形式进行维护,并有锁来控制并发访问。
struct {
  struct spinlock lock;
  struct file file[NFILE];
} ftable;
  • 打开一个 300B 的文件,调用四次读操作,每次读 100B。不难发现 open 时,当前偏移量置为 0,每读一次后将移动指针到读取的字节大小处的偏移量,文件读取完毕之后,偏移量就不再移动了。
    20200721140600

  • 一个进程打开相同的文件两次,并对每一个文件描述符发起读操作,两次 open 操作分别分配了 3 和 4 的文件描述符,对应了 Open File Table (OFT) 中两个不同的项,entry 10 和 11。不难发现,每一个 entry 的偏移量都是自己独立移动的,互不干扰。
    20200721140644

  • 最后的例子中使用了 lseek() 在读操作之前来重新定位当前偏移量。lseek() 首先将偏移量设置为 200,然后读操作继续移动到 250。
    20200721140748

Shared File Table Entries: fork() And dup()

  • 在许多情况下(如上面的示例所示),文件描述符到打开的文件表中的一个条目的映射是一对一的映射,例如,当进程运行时,它可能决定打开一个文件,读取它,然后关闭它;在这个例子中,文件在打开的文件表中有一个唯一的条目。即使其他进程同时读取相同的文件,每个进程在打开的文件表中都有自己的条目。这样的逻辑下,每个读写操作都是完全独立的,都有自己的偏移量。
  • 但在某些情况下,Open FIle Table 中的数据信息是共享的。其中一种情况发生在父进程使用fork()创建子进程时,如下代码所示,父进程创建了子进程并等待他执行结束,然后子进程移动了偏移量之后退出,父进程等待完后直接输出当前偏移量。
int main(int argc, char *argv[]) {
  int fd = open("file.txt", O_RDONLY);
  assert(fd >= 0);
  int rc = fork();
  if (rc == 0) {
    rc = lseek(fd, 10, SEEK_SET);
    printf("child: offset %d\n", rc);
  } else if (rc > 0) {
    (void) wait(NULL);
    printf("parent: offset %d\n", (int) lseek(fd, 0, SEEK_CUR));
  }
  return 0;
}
  • 输出如下:
prompt> ./fork-seek
child: offset 10
parent: offset 10
prompt>
  • 如图所示了连接每个进程的私有描述符数组、共享打开的文件表条目以及它对底层文件系统inode的引用的关系。此时就使用到了引用计数,当一个文件表项被共享的时候,引用计数相应地就会增加,知道所有进程都关闭了文件之后,该表项才会从 Open File Table 中移除。
  • 在父级和子级之间共享打开的文件表条目有时是有用的。比如你创建了大量的进程来协同工作完成一个任务,不用额外的协同就可以写到同一个输出文件中。
    20200721142527
  • 除了 fork 以外,还有 dup() (以及 dup2(), dup3())。dup允许进程创建一个新的文件描述符,但与现有的文件描述符引用了相同的底层文件描述符。使用示例如下。dup 操作在一些输出重定向的操作中是十分有用的,比如把标准输入重定向到文件中。
int main(int argc, char *argv[]) {
  int fd = open("README", O_RDONLY);
  assert(fd >= 0);
  int fd2 = dup(fd);
  // now fd and fd2 can be used interchangeably
  return 0;
}

Writing Immediately With fsync()

  • write 调用的实质是告诉文件系统,需要将某个数据在未来的某个时间点写入持久化存储中。文件系统出于性能的考虑会把写操作缓存在内存中一段时间,5s 或者 30s,之后才会把对应的写操作给实际写入到持久化设备中。从调用者的角度来看,写操作仿佛很快就完成了,但是如果机器在写操作完成,但未实际写入到磁盘的这一段时间内发生了故障,这段数据就将丢失。
  • 然而上层应用中会有一些如 DBMS 一样的对数据一致性要求极高的应用,DBMS 中的故障恢复协议就常常需要强制将写操作刷回到磁盘。因此大多数文件系统对此提供了额外的支持,UNIX 中即为 fsync(),强制将脏数据刷回磁盘,知道所有数据落盘之后才会返回具体的值。
  • 使用示例如下。但是这样的执行顺序也不能完全保证所有的操作如我们所期望的执行,在一些场景下,还需要 fsync 当前文件所在的目录,从而确保不仅该文件同步到了磁盘,文件所在的目录也同步到了磁盘,因为文件很多时候可能是新创建的,也是目录的一部分。
int fd = open("foo", O_CREAT|O_WRONLY|O_TRUNC, S_IRUSR|S_IWUSR);
assert(fd > -1);
int rc = write(fd, buffer, size);
assert(rc == size);
rc = fsync(fd);
assert(rc == 0);

Renaming Files

  • strace mv 我们不难发现该操作调用了 rename(char*old, char *new),该系统调用是一个原子操作,因此,rename() 对于支持某些需要对文件状态进行原子更新的应用程序非常重要。
prompt> mv foo bar
  • 使用示例:该编辑器将数据写入到了一个临时文件中,并使用 fsync 强制同步,然后应用就能确保新的文件元数据和文件数据已经落盘,再把临时文件更名为原始的文件名,最后一步原子地将新文件交换到适当的位置,同时 删除文件的旧版本,从而实现原子文件更新。(注意这里写入的时新版本的文件数据,即读取了原有的数据并合并了相应的更新
int fd = open("foo.txt.tmp", O_WRONLY|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR);
write(fd, buffer, size); // write out new version of file
fsync(fd);
close(fd);
rename("foo.txt.tmp", "foo.txt"); // 会覆盖原有的 foo.txt

Getting Information About Files

  • 除了文件访问之外,我们希望文件系统保存关于它所存储的每个文件的相当数量的信息,即我们常说的元数据 metadata。可以使用系统调用 stat() 或者 fstat()
struct stat {
  dev_t st_dev; // ID of device containing file
  ino_t st_ino; // inode number
  mode_t st_mode; // protection
  nlink_t st_nlink; // number of hard links
  uid_t st_uid; // user ID of owner
  gid_t st_gid; // group ID of owner
  dev_t st_rdev; // device ID (if special file)
  off_t st_size; // total size, in bytes
  blksize_t st_blksize; // blocksize for filesystem I/O
  blkcnt_t st_blocks; // number of blocks allocated
  time_t st_atime; // time of last access
  time_t st_mtime; // time of last modification
  time_t st_ctime; // time of last status change
};
  • state 输出。每个文件系统通常将这种类型的信息保存在一个称为inode的结构中,inode看作由文件系统保存的持久数据结构,其中包含我们以下看到的信息,所有inode都驻留在磁盘上;活跃的文件的 inode 的副本通常缓存在内存中以加速访问。
prompt> echo hello > file
prompt> stat file
File: ‘file’
Size: 6 Blocks: 8 IO Block: 4096 regular file
Device: 811h/2065d Inode: 67158084 Links: 1
Access: (0640/-rw-r-----) Uid: (30686/remzi)
Gid: (30686/remzi)
Access: 2011-05-03 15:50:20.157594748 -0500
Modify: 2011-05-03 15:50:20.157594748 -0500
Change: 2011-05-03 15:50:20.157594748 -0500

Removing Files

  • unlink() 只接受要删除的文件名称作为参数,删除成功后返回 0。
prompt> strace rm foo
...
unlink("foo") = 0
...

Making Directories

  • 目录也允许做上述的大量操作,但是不能直接递对目录进行操作,因为目录本质是文件系统的元数据,由文件系统完全负责。
  • 如下所示创建了一个空目录,但是对应了两条数据,一条指向他自己 .,一条指向它的父目录 ..
prompt> strace mkdir foo
...
mkdir("foo", 0777) = 0
...
prompt>

prompt> ls -a
./ ../
prompt> ls -al
total 8
drwxr-x--- 2 remzi remzi 6 Apr 30 16:17 ./
drwxr-x--- 26 remzi remzi 4096 Apr 30 16:17 ../

Reading Directories

  • opendir(), readdir(), closedir() 使用示例:
int main(int argc, char *argv[]) {
  DIR *dp = opendir(".");
  assert(dp != NULL);
  struct dirent *d;
  while ((d = readdir(dp)) != NULL) {
    printf("%lu %s\n", (unsigned long) d->d_ino, d->d_name);
  }
  closedir(dp);
  return 0;
}
  • 每一个目录对应的数据结构信息:目录提供的信息很少(基本上,只是将名称映射到inode号,以及一些其他细节)
struct dirent {
  char d_name[256]; // filename
  ino_t d_ino; // inode number
  off_t d_off; // offset to the next dirent
  unsigned short d_reclen; // length of this record
  unsigned char d_type; // type of file
};

Deleting Directories

  • rmdir() 要求目录为空。
  • link() 系统调用使用两个参数,一个老的路径名和一个新的,当使用 link 时就是创建了一个引用了同一个文件的指针,命令 ln 就是做这样的操作
prompt> echo hello > file
prompt> cat file
hello
prompt> ln file file2
prompt> cat file2
hello
  • link() 的工作方式是在创建链接的目录中创建另一个名称,并将其引用到相同的 inode 编号的原始文件,没有发生任何的数据拷贝,只是给原始文件多取了一个名字,inode 号完全相同。
prompt> ls -i file file2
67158084 file
67158084 file2
prompt>
  • 所以在创建文件时,相当于做了两件事情。
    • 首先,创建了一个 inode,包含了对应的文件信息;
    • 然后,把一个命名给链接到了这个 inode,并把这个链接放在了一个目录下。
  • 如果使用 unlink 删除上述例子中的任何一个文件名,对于另一个文件名的访问仍然不受任何影响。因为在 unlink 的时候,文件系统会检查对应 inode number 的引用计数,来看有多少个文件引用了当前 inode,使用 unlink 则相应地删除该 inode 上对应的一个链接,并对引用计数减一,只有当引用计数为 0 的时候,文件系统才会释放这个 inode 和相应的数据块信息,从而实现真正地删除文件。
prompt> rm file
removed ‘file’
prompt> cat file2
hello


prompt> echo hello > file
prompt> stat file
... Inode: 67158084 Links: 1 ...
prompt> ln file file2
prompt> stat file
... Inode: 67158084 Links: 2 ...
prompt> stat file2
... Inode: 67158084 Links: 2 ...
prompt> ln file2 file3
prompt> stat file
... Inode: 67158084 Links: 3 ...
prompt> rm file
prompt> stat file2
... Inode: 67158084 Links: 2 ...
prompt> rm file2
prompt> stat file3
... Inode: 6715808
  • 硬链接是有一定的限制的,因此产生了软连接(符号链接)
    • 即你不能创建对目录的硬链接,因为这样做可能会造成一个环
    • 不能创建不同磁盘分区之间硬链接,因为 inode 只针对于某一个特定的文件系统,无法跨文件系统
  • ln -s 示例:
prompt> echo hello > file
prompt> ln -s file file2
prompt> cat file2
hello
  • 软链接表面看着与硬链接相似,实际完全不同。

    • 第一个区别是符号链接实际上是不同类型的文件本身。常规文件、目录和符号链接是文件系统知道的三种类型.
      • file2 为 4 字节的原因是符号链接的形成方式是将链接到的文件的路径名作为链接文件的数据。如果文件名更长,相应的链接大小就更大
    prompt> stat file
    ... regular file ...
    prompt> stat file2
    ... symbolic link ...
    
    prompt> ls -al
    drwxr-x--- 2 remzi remzi 29 May 3 19:10 ./
    drwxr-x--- 27 remzi remzi 4096 May 3 15:14 ../
    -rw-r----- 1 remzi remzi 6 May 3 19:10 file
    lrwxrwxrwx 1 remzi remzi 4 May 3 19:10 file2 -> file
    
    • 因为软链接的形成方式,所以可能出现 dangling reference 虚引用的情况,即链接了个空气。
    prompt> echo hello > file
    prompt> ln -s file file2
    prompt> cat file2
    hello
    prompt> rm file
    prompt> cat file2
    cat: file2: No such file or directory
    
    • 软链接的本质就是我们常用的 win 系统中的 快捷方式

Permission Bits And Access Control Lists

  • 底层的操作系统使用各种技术在相互竞争的实体之间以安全的方式共享有限的物理资源,文件系统提供了存储资源的虚拟化,但和 CPU 以及内存的虚拟化的不同之处在于 文件很多时候在不同的用户或者进程之间是共享的,不总是私有的。
Permission bits
  • permission bits-rw-r--r--. 第一个- 表示为一个常规文件, d 为目录,l 为软连接。所以 rw-r--r-- 才是权限相关的位,表示对于每一个实体,谁能访问以及如何访问。由三组组成:
    • 文件所有者可以对文件做什么 rw-
    • 组中的其他人可以对文件做什么 r--
    • 任何人(有时称为其他人)可以做什么 r--
prompt> ls -l foo.txt
-rw-r--r-- 1 remzi wheel 0 Aug 24 16:29 foo.txt
  • 文件的所有者可以使用 chmod 更改权限,比如:其中 6 = 可读(4)+ 可写(2),但是另外两个组都设置为 0,因此对应的权限即为 rw-------。7 = 可读(4)+ 可写(2)+ 执行(1)
# 移除所有人访问该文件的权限
prompt> chmod 600 foo.txt   
# 给所有人添加所有权限
prompt> chmod 777 hello.sh
ACL
  • 常用于分布式文件系统的访问控制,即 Access Control List。比如 AFS 中:
prompt> fs listacl private
Access list for private is
  Normal rights:
  system:administrators rlidwka
  remzi rlidwka

Making And Mounting A File System

  • 如何从许多底层文件系统组装一个完整的目录树? 格式化文件系统并挂载,从而提供访问入口。
  • mkfs 命令用于格式化指定的文件系统,需要指定对应的需要格式化的设备。
  • 格式化完成之后,需要借助mount命令将文件系统挂载某一个挂载点,从而对外提供该文件系统的目录树入口。如下例子中的 /home/users 即为新创建的文件系统的根目录
prompt> mount -t ext3 /dev/sda1 /home/users
prompt> ls /home/users/
a b

Homework

  • 实现 Stat, List Files, Tail, Recusive Search