Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 22: 目录与链接（Directories and Links）

目录 · ← l15 · l17 →

概述

上一讲解决”给定 inode 找数据块”，本讲解决”给定名字找 inode”：i-number 与 inode 数组、目录（directory）如何存储 <名字, i-number> 对、路径名查找（open("/a/b/c")）的逐级解析、工作目录，以及硬链接（hard link）与符号链接（symbolic link）的区别与使用场景。

核心概念与系统机制图解

i-number 与 inode 数组

  • i-number：inode 数组的下标，唯一标识一个 inode；OS 内部用 i-number 标识文件。
  • inode 数组存储在磁盘上：早期 Unix 放在磁盘起始处；后来移到中部（缩短寻道）；BSD FS 分散为多块分布全盘（inode 靠近数据块）。

目录（Directory）

  • 定义：把”名字 → i-number”映射起来的特殊结构。现代系统用层级目录树。
  • Unix/Linux 目录：目录本身就是一个文件（inode 的 type == directory），内容是无序的 <name, i-number> 对列表；只有 OS 能写。根目录 / 的 i-number 固定为 1。
    assign0 目录内容(例子):
movietest.cc  96      questions.txt  656
samples       228     movie.cc       780
movie.h       1441    buggy.c        6312
Makefile      1443    ...

路径名查找：open(“/a/b/c”)

1. 读 inode 1 (根目录 "/")
2. 在根目录块中找 "a" → i-number 17
3. 读 inode 17 (目录 a)
4. 在 a 的块中找 "b" → i-number 23
5. 读 inode 23 (目录 b)
6. 在 b 的块中找 "c" → i-number 42
7. 读 inode 42 (文件 c), open 完成
每次目录查找 = 读目录 inode + 读其数据块
  • 工作目录（working directory）：OS 为每进程保存一个”当前目录”；不以 / 开头的路径从工作目录开始查找；pwd 打印它。
  • 定义：目录项就是”链接”——一个 <name, i-number> 对。多个目录项可以指向同一个 i-number → 多个名字引用同一文件。
  • 引用计数：inode 中记录链接数（nlink）；rm 只是删除一个目录项（减少链接数）；计数归零才真正释放文件数据。
  • 你天天见的硬链接：rm（删链接）、每个目录里的 .（指向自身）与 ..（指向父目录）。
    ln /a/b/c  t        → 在 /g 下创建 t: {t, 42}
目录b: {c, 42}      目录g: {t, 42}       inode 42: nlink=2
  • 硬链接的限制：
    1. 不能链接到目录（防止目录图出现环）；
    2. 不能跨文件系统（i-number 只在同一文件系统内有意义）。
  • → 因此 BSD Unix 增加了符号链接。

符号链接（Symbolic Link / Symlink）

  • 定义：一种特殊文件（inode type == symbolic link），内容就是另一个路径名。
  • 查找规则：解析路径时遇到符号链接，把其内容拼接到剩余路径前继续查找；若内容以 / 开头则从根目录重新开始。
    cd /a;  ln -s e/f b;  cat /a/b/c
→ 查找 /a 发现 b 是符号链接 "e/f"
→ 继续查找 e/f/c → 等价于 cat /a/e/f/c
  • 优点：可跨文件系统、可链接目录。
  • 缺点：可形成环（无限循环）；容易产生悬空链接（指向不存在的文件）。

代码示例与系统调用解说

示例：硬链接与符号链接（shell + C）

echo "hello" > f1
ln f1 f2                # 硬链接: f1 与 f2 指向同一 inode
ln -s f1 f3             # 符号链接: f3 的内容是 "f1"
ls -li                  # -i 显示 i-number: f1/f2 相同, f3 不同
rm f1                   # 删除一个硬链接; f2 仍可读("hello" 未丢)
cat f2                  # → hello
cat f3                  # → hello (符号链接仍解析到 f2? 不: f3→"f1" 已不存在 → 悬空!)
ls -l f3                # f3 -> f1 (悬空符号链接)

#include <cstdio>
#include <unistd.h>
#include <sys/stat.h>

int main() {
    link("f1", "f2");              // 创建硬链接 (相当于 ln f1 f2)
    symlink("f1", "f3");           // 创建符号链接 (相当于 ln -s f1 f3)

    struct stat st1, st2;
    stat("f1", &st1);              // 跟随符号链接的 stat
    stat("f2", &st2);
    printf("same inode: %s\n", st1.st_ino == st2.st_ino ? "yes" : "no");

    struct stat st3;
    lstat("f3", &st3);             // lstat 不跟随符号链接: 看到的是链接本身
    printf("f3 is symlink: %s\n", S_ISLNK(st3.st_mode) ? "yes" : "no");
    return 0;
}

【代码做了什么？】 用 link/symlink 系统调用创建两类链接，用 stat（跟随链接）与 lstat（不跟随）区分它们。

【系统机制透视】

  • 硬链接不复制数据——两个名字共享 inode 与数据块，删除一个名字只是 nlink–；文件”真正删除”发生在 nlink 归零且没有进程打开它时。
  • 符号链接是一个独立的小文件（存路径字符串），解析由路径名查找过程完成；删除目标文件后，符号链接变成悬空链接（读取报 ENOENT）——它不参与 inode 计数。
  • 目录项的 nlink 就是 Lecture 10 讲的引用计数在文件系统中的应用；fsck 会检查目录链接数是否与目录项数一致（Lecture 23）。

关键要点

  1. i-number 唯一标识文件；inode 数组存于磁盘（位置从起始→中部→分散演化）。
  2. 目录 = <名字, i-number> 对的文件；open("/a/b/c") 沿路径逐级查目录。
  3. 硬链接 = 共享 inode 的多个目录项；rm 删链接、计数归零才释放文件。
  4. 硬链接不能指向目录、不能跨文件系统；符号链接是”存路径的文件”，可跨 FS、可指向目录，但会悬空/成环。
  5. stat vs lstat：是否跟随符号链接。

常见陷阱与注意事项

  • 把硬链接当拷贝：修改任一名字下的内容，另一名字可见（同一文件）。
  • 创建指向目录的硬链接：系统禁止（ln dir 报错）。
  • 符号链接悬空：目标被删除后链接仍在但不可用。
  • 符号链接环：ln -s b a; ln -s a b 之类会造成查找无限循环（OS 有循环上限检测）。
  • rm 后以为数据没了：若还有其它硬链接，数据仍在。

思考题

  1. 问题：为什么硬链接不能指向目录？
    • 答案：目录是树的节点；若允许目录硬链接，目录图可能出现环（如目录 a 的子项指向祖先目录），路径查找将无限循环，且”删除子树”的语义变得复杂。. 与 .. 是仅有的例外（不增加可导航环）。
  2. 问题：符号链接与硬链接在”删除原文件”后的行为有何不同？
    • 答案：硬链接下删除一个名字，其它名字仍有效（数据与 inode 因计数未归零而保留）；符号链接下删除目标文件，链接变成悬空链接——因为它只是存了一个不再存在的路径字符串。
  3. 问题：open("/a/b/c") 最坏情况需要多少次磁盘访问（无缓存）？
    • 答案：每个路径分量至少一次”读目录 inode + 读目录数据块”，即 3 个目录 × 2 ≈ 6 次以上访问；块缓存命中目录块时可大幅减少（这正是块缓存存在的理由之一）。