MIT 6.1810 实验笔记：实现 xv6 的 find 程序

前言

做完 MIT 6.1810 第一个实验里的 sleep 和 memdump 之后，接下来就是写一个简化版的 find 用户程序（见 Lab Utilities 实验说明）。功能要求很简单：给一个起始目录和一个文件名，递归遍历底下所有的子目录，把同名文件的完整路径打印出来：

text

find . b

这里不用管 Linux find 那些复杂的通配符或者 -exec，只要文件名完全匹配就行。我在 9 月 11 日写完了第一版代码，当时跑几个简单目录能出结果；但最近回头重新看那几十行 C 代码时，才发现里面其实藏了好几处指针越界、字符串没封 \0 和忘关文件描述符的坑，干脆写篇笔记把原思路和问题一起记下来。

目录结构与读取方式

实验提示里让我们先去读 user/ls.c（源码链接）。在 xv6 里，目录本质上也是一个文件，打开之后用 read 每次读出一个 struct dirent 结构体（定义在 kernel/fs.h）：

#define DIRSIZ 14

struct dirent {
  ushort inum;
  char name[DIRSIZ];
};

如果读出来的 de.inum == 0，说明这一个目录项是空的，直接跳过；
如果非零，就把 de.name 拼到当前路径后面，再用 stat / fstat 看看它是普通文件还是子目录。

写递归遍历的时候有一条铁律：遇到 .（当前目录）和 ..（上级目录）一定要跳过，不然一递归马上就死循环把栈撑爆了。

初始实现流程

第一版写得比较省事，我把目标文件名 target、当前路径缓冲区 path、指向路径末尾的指针 p，还有 stat 和 dirent 全都扔在了全局变量里：

char *target;
struct stat st;
struct dirent de;
char *p;
char path[512];

main 函数把命令行传进来的起始路径拷进 path，让指针 p 指向字符串结尾，然后调无参的 find()。里面的逻辑大概是这样：

text

open 当前 path
   ↓
fstat 判断类型
   ├── 普通文件 / 设备：把路径最后一段名字拿出来跟 target 比对，一样就打印
   └── 目录：循环 read 目录项，跳过 "." 和 ".."，把子文件名接到 path 后面，递归调 find()

写完 user/find.c 之后，在 Makefile 的 UPROGS 里加上一行 $U/_find，跑 make qemu 就能在 xv6 里用 find 命令了。

边界问题分析与改进

虽然第一版在简单的测试目录里能打出结果，但仔细抠代码就会发现好几个 C 语言里很典型的边界漏洞。

1. 全局路径指针回退越界

第一版为了省内存，每次进子目录都直接改全局的 path 和指针 p；等子目录递归返回后，再用一个 for 循环从后往前找 '/'，想把路径截断回上一级目录：

for (; p > path && *(p - 1) != '/'; p--)
  ;
p--;
*p = '\0';

这段代码看着挺巧妙，但有个致命问题：如果起始路径本身不带斜杠（比如 find . b），或者退到最顶层目录，for 循环停下来的时候 p 已经等于 path 开头了。这时候下面紧跟着一句无条件的 p--，指针直接就退到了 path 数组前面，往越界的内存里写了一个 \0！

提示

改进思路其实最清晰的做法是别把 path 放全局，直接让递归函数接收当前路径参数 void find(char *path, const char *target)，每层用自己的局部变量拼子路径，返回时天然就恢复了。就算非要共用一个全局 path，进子目录前先拿个局部变量记一下长度 int old_len = p - path;，递归回来直接 p = path + old_len; *p = '\0';，根本用不着倒着找 '/'。另外 struct dirent de 和 struct stat st 也应该放进函数里当局部变量，免得下层递归把上层的数据冲掉。

2. 目录项名称的字符串终止符

第一版里我直接写了 strcmp(de.name, ".") 和 strlen(de.name)。

回头看 struct dirent 的定义：char name[DIRSIZ] 的长度固定是 14。在 xv6 文件系统里，如果一个文件名刚好有 14 个字符，这 14 个字节会全部塞满字符，末尾是没有 \0 结束符的。这时候直接对 de.name 调 strlen 或 strcmp，就会越过 de.name 继续往后面的内存读。

正确的做法是先拷到一个长度为 DIRSIZ + 1（15 字节）的数组里，手动在最后补上 \0：

char name[DIRSIZ + 1];

memmove(name, de.name, DIRSIZ);
name[DIRSIZ] = '\0';

if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0)
  continue;

3. 递归路径拼接的长度检查

第一版只在 main 开头检查了一次初始参数的长度（而且打完报错还忘了 exit）。实际上路径是在递归过程里一层一层变长的，应该在每一次往后拼接子文件名之前检查会不会塞爆 path 缓冲区。

把路径拼接单独抽成一个小函数，顺便还能处理好根目录 / 末尾自带斜杠的情况（避免拼出 //name）：

static int
join_path(char *out, uint cap, const char *parent, const char *name)
{
  uint base = strlen(parent);
  uint len = strlen(name);
  uint slash = base > 0 && parent[base - 1] != '/';

  if (cap == 0 || base >= cap)
    return -1;
  if (slash >= cap - base)
    return -1;
  if (len >= cap - base - slash)
    return -1;

  memmove(out, parent, base);
  if (slash)
    out[base++] = '/';
  memmove(out + base, name, len);
  out[base + len] = '\0';
  return 0;
}

4. 文件描述符回收与输出流规范

还有三个小细节也是看代码时发现的：

fstat 失败时直接 return 忘了 close(fd)：xv6 每个进程能同时打开的文件描述符很少，提前 return 前一定要先把已经 open 的 fd 关掉。
打印结果用了 fprintf(2, ...)：2 是标准错误（stderr），正常找到的文件路径应该用 printf(...)（即 fd 1 标准输出）打印，报错提示才走 fprintf(2, ...)，不然没法配合管道用。
参数不对时用了 exit(0)：参数个数不对属于出错退出，应该改成 exit(1)：

if (argc != 3) {
  fprintf(2, "usage: find path filename\n");
  exit(1);
}

功能测试与验证

进到 xv6 的 shell 之后，可以随手建几个目录和同名文件试试：

mkdir a
echo hello > a/b
mkdir c
echo hello > c/b
echo hello > b
find . b

正常的话会把 ./b、./a/b、./c/b 三个路径都打印出来，而且不会把 . 和 .. 绕进去。顺便提一句，仓库自带的 findtest.sh 脚本后面带了 -exec grep hello 参数（那是后面 Lab 扩展了 xargs / -exec 才用的），刚写完只收两个参数的基础版 find 时，还不能直接拿那个脚本来跑。