编程语言研究书库
Linux 系统编程

目录层次 — 遍历、挂载与 pwd 的攀爬算法

目录层次 — 遍历、挂载与 pwd 的攀爬算法

这一章讲什么: 第 6 章讲了单个文件的元数据,这一章讲整个目录 树:怎么列目录、怎么递归下钻(find/du/tree 的底层)、怎么不越 过挂载点、以及一个反方向的问题——pwd 是怎么「爬」出当前路径的。 项目:四个版本的仿写 ls、仿写 du(后序遍历 + 按层累计数组)、 手写 pwd(逆树攀爬)。概念密度高,而且每个坑都是真坑。

1. 顶层全景:目录 API 的四个层次

  平铺一层:opendir → readdir → closedir(目录流 = 条目的有序序列)
      │   增强:spl_ls2(目录优先,靠 telldir/seekdir 存位置)
      │   一步到位:scandir(过滤函数 + 排序函数,自带排序数组)
      ▼
  递归下钻:手写递归(readdir 版 / scandir 版)
      │   或交给库:nftw(单函数 + 回调,ftw 已废弃)
      │   或更灵活:fts 一族(BSD,非 POSIX,可带程序状态)
      ▼
  语义约束:挂载点(inode 号跨文件系统不唯一、nftw 的 FTW_MOUNT)
      │   遍历方向反过来:pwd 沿 .. 爬树,靠 (dev, ino) 对认亲
      ▼
  项目:spl_ls1/2/3 → spl_du1(nftw 后序 + 按层累计)→ spl_pwd

图说:前一半「往下走」,后一半「往上爬」,挂载是横在中间的语义 分水岭。 主线例子:spl_du1 数一个目录树的磁盘占用—— 后序遍历 + 一个按层索引的累计数组,每个数都有来历。

2. 目录流三件套与 dirent 的可移植性

内核的 readdir(2)/getdents(2) 没有 glibc 包装,man 页明说 「这不是你要的接口」——要用的是 POSIX 库函数 readdir(3)1。 三件套:opendir(路径) 返回 DIR*(目录流,定位在第一条)、 readdir(DIR*) 每次返回下一条的 struct dirent*、读完返 NULL (出错也返 NULL——循环里照旧「先清 errno 再查」)、 closedir 收尾2。

struct dirent 只有 d_ino 和 d_name 是 POSIX 保证的; Linux 版还有 d_off(不是偏移!)、d_reclen、d_type3。三个可移植 性要点:

  1. d_name 长度不写死:存名字的缓冲区按 NAME_MAX+1 声明; NAME_MAX 是路径可变限制,运行时用 pathconf(dir, _PC_NAME_MAX) 查4。
  2. d_type 不是处处有:glibc 用 _DIRENT_HAVE_D_TYPE 宏告诉你 编译时有没有;没有就得 stat()。即使有,某些文件系统也不填类型 信息5。
  3. 返回指针指向库内静态存储,要留着用就先拷6。

DIR 本身是不完全类型——dirent.h 只 typedef 不定义成员, 「能声明 DIR* 指针、不能解引用、不能 sizeof」,这是 C 的信息隐藏 手法(glibc 里 struct __dirstream 的真身在 sysdeps/.../dirstream.h)7。

rewinddir 倒回流头(第二遍遍历时用);telldir/seekdir 一对 存取流内位置——别当它是字节偏移:现代文件系统用哈希表/搜索树 存目录,那个 long 值是个「cookie」,只能从哪来回哪去8。

3. scandir:把「过滤 + 排序 + 数组」一次做完

int scandir(const char *dirp, struct dirent ***namelist,
            int (*filter)(const struct dirent *),
            int (*compar)(const struct dirent **, const struct dirent **));

图说:两个函数指针参数——filter 决定谁进数组(返回 0 剔除), compar 决定排序;传 NULL 表示全收/不排。 库自带 alphasort (内部走 strcoll,locale 感知)和 versionsort。内存是 scandir 自己分配的(struct dirent** 三层间接——用完逐条 free 再 free 数组)9。示范用法一行:scandir(".", &dp_array, skipdot, alphasort)。自定义比较函数可以做任何事,比如按文件大小排 (在 compar 里调 stat)10。spl_ls3 用「目录优先 + 字母序」的 比较函数,十行代码拿到了排序且目录在前的 ls11。

判断(我们的,不是书里的): scandir 的「函数指针参数」模式 是 C 里回调的标准长相(qsort 同款)。它的另一面在 nftw 那里会 看见:回调拿不到调用方的上下文(没有 void* 参数),只能往文件 作用域塞状态——设计回调接口时,「给不给 void 上下文」是 区分上世纪接口和现代接口的分水岭*。C 的新接口(如 pthread_create) 都带 void*;老的(qsort、nftw)没有。这是读老 API 时第一个 该检查的签名特征。 如果错,会错在: 有些老接口用别的方式补上下文(全局 errno、 线程局部存储),但那些都有各自的重入问题——判据不变:看签名里 有没有一个「用户数据」参数位。

4. 挂载:遍历语义的分水岭

mount 设备 目录 把文件系统接到目录树的某点,该目录原有的内容 被整个藏起(umount 后恢复);这个目录就是挂载点12。识别挂载点 的通用办法:目录与其父目录的设备 ID 不同——目录是被挂文件系统 的根,父目录属于宿主文件系统13。用户级工具:df --output=source, target、mount -t ext4、findmnt -o SOURCE,TARGET14。

挂载带来一个硬核事实:inode 号只在单个文件系统内唯一。Linux 里 每个文件系统的根目录都是 inode 2(1 记坏块,0 不用),所以根下 常能看到一堆 inode 号都是 2 的目录——它们全是各文件系统的挂载点。 唯一定位一个文件要靠 (inode 号， 设备 ID) 对——这也是内核 禁止跨文件系统硬链接的原因：两个文件系统里 inode 52 是两个 不同的 inode,链过去就天下大乱15。

5. 树遍历:从手写递归到 nftw

手写递归的两个经典坑

把 spl_ls1 改成递归,直觉写法会撞上两个坑16:

  1. 相对路径陷阱:readdir 给出的 d_name 只是最后一段名字; 在 jammy 里读到 drivers,直接 opendir("drivers") 会 ENOENT——它相对的是进程的当前工作目录,不是 jammy。解法是 把「父路径」一路传进递归函数,拼出 jammy/drivers 再开。
  2. ./.. 死循环:它们也是目录,不跳过就会无限递归。

修法后的骨架(spl_ls_rec1):跳过点项 → sprintf(pathname, "%s/%s", dirname, name) → 是目录就 opendir(pathname) 递归。 基于 scandir 的递归版(spl_ls_rec2)逻辑相同,白拿字母排序17。

nftw:库替你递归,但回调没有口袋

int nftw(const char *dirpath,
         int (*fn)(const char *fpath, const struct stat *sb,
                   int typeflag, struct FTW *ftwbuf),
         int nopenfd, int flags);

回调每到一个节点被调一次,拿到：路径、stat 结果、typeflag (FTW_F 普通文件 / FTW_D 目录 / FTW_DNR 不可读目录 / FTW_DP 目录且子孙已访问完(后序才有)/ FTW_SL 软链 / FTW_SLN 悬空软链)、以及 FTW 结构(base = 文件名在路径里的偏移、 level = 深度)18。四个控制 flags19:

flag作用
FTW_DEPTH后序:先处理完目录里的所有东西,再处理目录本身(du 需要的!)
FTW_PHYS物理遍历:不跟软链(du 需要,防止重复计数和越界)
FTW_MOUNT不跨挂载点(du 需要,单文件系统内统计)
FTW_CHDIR每处理一个目录先 chdir 进去

nopenfd 是允许同时打开的目录 fd 上限——树有多深就要多少 fd, 不够时 nftw 会关祖先的 fd 再来,性能变差；进程的单次打开数上限 (prlimit -n,典型 1024)是天花板20。演示程序 nftw_demo (-d/-p/-m 三选项)在带循环软链的测试目录上跑:不加 -p 时跟链接但 同一文件绝不访问两次(nftw 内置防环)21。

主线例子走查:spl_du1——按层累计数组

du 的输出格式(du -a testing):

  0 testing/dir1/b          ← 叶子文件,自身 0 块
  4 testing/dir1/adir       ← 目录:子项累计 + 自身 4(目录本身占一块)
  8 testing/dir1            ← 更深的目录,含子目录的累计
 32 testing                 ← 根:全树总和

图说:每个目录的数字 = 它所有子孙的累计 + 它自己。后序遍历时 「退栈」的瞬间正好拿到这个数。 nftw 回调拿不到上下文,所以 状态放文件作用域:

#define MAXDEPTH 50
static uintmax_t total_usage[MAXDEPTH];   /* 按层累计,每层一个格子 */
static int prev_level = -1;               /* 上一个访问节点的层 */

不变式(每次回调结束必须成立):total_usage[L] = 当前层 L 上、 当前节点及其全部左兄弟子树的块数之和22。处理规则按 prev_level 与 cur_level(=ftwbuf->level)的关系分两种:

  • prev < cur(下降或起步):到了新底层。total_usage[cur] = 本文件块数。
  • prev >= cur(平移或回升):当前节点和上一层累计是同辈或上卷。 先把上一层的累计上卷:total_usage[prev] 归入 total_usage[cur] (逐层归并);再 total_usage[cur] += 本文件块数。回升多层时 逐层结算,每结算一层,那一层的目录就该打印自己的总数了 (FTW_DP 标志恰好标记「目录且子孙已完」)23。

st_blocks 是 512 字节块,du 按 1024 字节报,所以除以 2。 图说:这棵树的访问序列是 srcs, cpy, bin, pics, stuff, data, work……数字像雪崩一样往第 0 层滚——数组的每个格子恰好对应 递归调用栈的一帧,这就是「递归的本质是栈」的迭代版。

fts:BSD 的可控遍历(进阶)

fts_open/fts_read/fts_children/fts_set/fts_close 一族(来自 4.4BSD,不是 POSIX):目录进、出各访问一次(自带后序), fts_number/fts_pointer 两个成员专门留给应用程序塞状态—— 正好补上 nftw 没有上下文口袋的短板;还能指定访问顺序、拿父节点 指针、检测环(FTS_DC + fts_cycle)24。代价:不可移植。

6. 反方向:手写 pwd 的攀爬算法

pwd 要打印当前目录的绝对路径,但进程手里只有「当前目录的 fd」, 没有任何路径信息。唯一的路是往上爬:.. 条目是目录树里 唯一的「反向链接」25。算法(spl_pwd 的策略):

  循环:
    1. lstat(".") → 当前目录的 (dev, ino),记作 dir_dev_ino
    2. chdir("..") 进到父目录
    3. 若当前目录的 (dev, ino) == 预先存好的根 (dev, ino) → 到顶,停
    4. 在父目录里 readdir,对每个条目 lstat,
       找 (dev, ino) == dir_dev_ino 的那条 → 它的 d_name 就是
       「刚才那个目录」的名字
    5. 把这个名字**前插**进路径缓冲区,前面再前插一个 '/'
    6. 回到 1

图说:名字是倒着发现的(从最深目录往上),所以路径要从缓冲区 右端往左填:front 指针从 PATH_MAX-1 起,每次 front -= strlen(name); memcpy(pathname+front, name, len); front--; pathname[front]='/'26。

三个细节全是真知:用 lstat 而不是 stat(父目录里的条目可能是软链, stat 会追到链外去);跨文件系统必须用 (dev, ino) 对(挂载点两侧 inode 会撞号,§4);判定到根用「当前 == 预先存的 / 的 dev_ino」 (另一个等价判据：根的 . 和 .. 指向同一 inode)27。 路径超长就报「未完全构造」、用点号顶罪28。getcwd() 系统调用 和库函数现成的,但本章的意义就是「不调用它,自己长出它来」29。

7. 作者的判断与证据

有明证的:

  • 挂载点识别(父目录 dev 不同)、inode 2 = 文件系统根、 跨文件系统硬链接禁令的推理,链条完整且可实验验证1315。
  • nftw 的 flags 语义、FTW_DP/FTW_SLN 的触发条件,逐条来自 man 页原文1819。
  • 递归的两个坑(相对路径、点项死循环)都有具体失败演示16。
  • du 的按层累计不变式是原书自己形式化写出来的22——这本书 少有的「带不变式的算法教学」。

作者的判断:

  • 「nftw 回调没上下文,所以状态放文件作用域」——接受了这个 设计缺陷的 workaround,没有抱怨18。(fts 才被当作正解提及。)
  • 「pwd 用 readdir 而不用 scandir」——明说两种都行、性能相当, 选了可控性高的27。
  • MAXDEPTH=50 拍脑袋、「生产版应查进程资源上限动态分配」20—— 诚实的教学简化。

8. 边界与局限

  • fts 非 POSIX——用它就得放弃可移植性24。
  • nftw 的 nopenfd 上限受进程资源限制约束,深树性能会退化 (关祖先 fd 重开)20;资源限制本身(prlimit/rlimit)只是 点到为止,第 10 章才展开。
  • 手写递归不处理软链环——会死循环;nftw 不跟 FTW_PHYS 时 有内置防重复,跟了就没环的问题,但本章没演示带环目录的手写 递归解法(那是fts 的 FTS_DC 的主场)21。
  • spl_du1 是 du -a 的简化:不处理硬链接去重(真 du 对同一 inode 只计一次)、不支持块大小环境变量、不跨挂载点23。
  • spl_pwd 跳过错误恢复细节;路径超长的处理也只是「报错了事」28。

9. 可带走的

主线例子,一行复述: nftw(FTW_DEPTH|FTW_PHYS|FTW_MOUNT) 后序遍历 → 回调里 total_usage[level] 按不变式累计 (下降重置、平移/回升上卷)→ FTW_DP 时打 total_usage[level]。

  1. 目录用 opendir/readdir/closedir(库函数,不是系统调用); readdir 的 NULL 既可能是 EOF 也可能是错——errno 先行清零。
  2. dirent 只有 d_ino/d_name 可移植;d_name 按 NAME_MAX+1 存; d_type 用 _DIRENT_HAVE_D_TYPE 条件编译包住。
  3. telldir 的返回值是 cookie 不是偏移,只能 seekdir 回原位。
  4. scandir = 遍历 + 过滤回调 + 排序回调 + 动态数组,内存全自己 分配,用完逐条 free。
  5. 回调接口先看签名有没有 void 上下文——没有就是老接口, 状态只能放文件作用域(nftw),这就是 bug 和重入问题的温床。*
  6. 挂载点 = 与父目录 dev 不同的目录;inode 号跨文件系统不唯一, 每个文件系统的根都是 inode 2;(dev, ino) 对才是文件的身份。
  7. nftw 四件套:回调、nopenfd 上限、FTW_DEPTH(后序)、 FTW_PHYS(不跟软链)、FTW_MOUNT(不跨挂载)。
  8. 手写递归两个坑:相对路径(把父路径传下去)、./.. (必须跳过)。
  9. du 的后序累计 = 按层数组 + 上卷结算;数组的一格就是递归 栈的一帧。
  10. pwd = 存 (dev,ino) → chdir("..") → 父目录里 lstat 找同号 条目 → 名字前插路径 → 到根停止;跨文件系统和软链场景下 lstat 与 dev_ino 一个都不能省。

10. 原文地图

主题原书章原文位置
内核 readdir/getdents 的警告Chapter 7: The Directory Hierarchytext/13-ch07-chapter-7-the-directory-hierarchy.txt:149(搜「not the function you are interested in」)
readdir 三查与静态存储同上:218(搜「Successive calls」) · :224(搜「overwritten」)
dirent 可移植字段与 NAME_MAX同上:233(搜「d_ino and d_name」) · :260(搜「pathconf」)
d_type 与条件编译同上:294(搜「_DIRENT_HAVE_D_TYPE」)
DIR 不完全类型同上:346(搜「incomplete type」)
telldir/seekdir 与 cookie同上:645(搜「cookie」)
scandir 机制与函数指针同上:904(搜「no sorting takes place」) · :915(搜「cmpbysize」)
spl_ls 系列同上:969(搜「dirsfirstsort」) · :1466(搜「sprintf」)
挂载机制与挂载点识别同上:1195(搜「hidden」) · :1259(搜「different from」)
df/mount/findmnt同上:1272(搜「--output=source」) · :1293(搜「mount -t ext4」)
inode 2 与跨文件系统硬链接禁令同上:1329(搜「inode number 2」) · :1340(搜「different filesystem」)
递归两坑同上:1424(搜「is relative only」)
nftw 接口与 typeflag同上:1655(搜「nftw」) · :1703(搜「FTW_F」)
FTW flags 全集同上:1785(搜「FTW_DEPTH」)
nopenfd 与资源限制同上:1771(搜「1024」)
nftw 防重复与演示同上:1954(搜「any file twice」)
du 的不变式与算法同上:2049(搜「invariant」) · :2065(搜「cur_usage」)
fts 一族同上:2486(搜「specify this order」) · :2547(搜「fts_number」)
.. 是反向链接同上:2814(搜「backlinks」)
pwd 算法细节同上:2916(搜「lstat() rather than stat()」) · :2960(搜「same inode」) · :2977(搜「front = front - strlen」) · :3013(搜「not constructed」)

Footnotes

  1. 出处:「Chapter 7: The Directory Hierarchy」第 128–175 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:149,搜「not the function you are interested in」)。 ↩

  2. 出处:「Chapter 7: The Directory Hierarchy」第 177–231 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:218,搜「Successive calls」)。 ↩

  3. 出处:「Chapter 7: The Directory Hierarchy」第 232–251 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:233,搜「d_ino and d_name」)。 ↩

  4. 出处:「Chapter 7: The Directory Hierarchy」第 252–283 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:260,搜「pathconf」)。 ↩

  5. 出处:「Chapter 7: The Directory Hierarchy」第 284–313 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:294,搜「_DIRENT_HAVE_D_TYPE」)。 ↩

  6. 出处:「Chapter 7: The Directory Hierarchy」第 224–228 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:224,搜「overwritten」)。 ↩

  7. 出处:「Chapter 7: The Directory Hierarchy」第 339–362 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:346,搜「incomplete type」)。 ↩

  8. 出处:「Chapter 7: The Directory Hierarchy」第 624–646 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:645,搜「cookie」)。 ↩

  9. 出处:「Chapter 7: The Directory Hierarchy」第 895–960 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:904,搜「no sorting takes place」)。 ↩

  10. 出处:「Chapter 7: The Directory Hierarchy」第 913–934 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:915,搜「cmpbysize」)。 ↩

  11. 出处:「Chapter 7: The Directory Hierarchy」第 961–1087 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:969,搜「dirsfirstsort」)。 ↩

  12. 出处:「Chapter 7: The Directory Hierarchy」第 1179–1197 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1195,搜「hidden」)。 ↩

  13. 出处:「Chapter 7: The Directory Hierarchy」第 1252–1260 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1259,搜「different from」)。 ↩ ↩2

  14. 出处:「Chapter 7: The Directory Hierarchy」第 1262–1321 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1272,搜「--output=source」) · :1293(搜「mount -t ext4」)。 ↩

  15. 出处:「Chapter 7: The Directory Hierarchy」第 1323–1353 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1329,搜「inode number 2」) · :1340(搜「different filesystem」)。 ↩ ↩2

  16. 出处:「Chapter 7: The Directory Hierarchy」第 1364–1442 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1424,搜「is relative only」)。 ↩ ↩2

  17. 出处:「Chapter 7: The Directory Hierarchy」第 1448–1536 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1466,搜「sprintf」)与第 1538–1594 段。 ↩

  18. 出处:「Chapter 7: The Directory Hierarchy」第 1645–1745 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1655,搜「nftw」) · :1703(搜「FTW_F」)。 ↩ ↩2 ↩3

  19. 出处:「Chapter 7: The Directory Hierarchy」第 1777–1806 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1785,搜「FTW_DEPTH」)。 ↩ ↩2

  20. 出处:「Chapter 7: The Directory Hierarchy」第 1746–1776 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1771,搜「1024」)。 ↩ ↩2 ↩3

  21. 出处:「Chapter 7: The Directory Hierarchy」第 1816–1954 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:1954,搜「any file twice」)。 ↩ ↩2

  22. 出处:「Chapter 7: The Directory Hierarchy」第 1989–2063 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:2049,搜「invariant」)。 ↩ ↩2

  23. 出处:「Chapter 7: The Directory Hierarchy」第 2065–2140 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:2065,搜「cur_usage」)。 ↩ ↩2

  24. 出处:「Chapter 7: The Directory Hierarchy」第 2467–2566 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:2486,搜「specify this order」) · :2547(搜「fts_number」)。 ↩ ↩2

  25. 出处:「Chapter 7: The Directory Hierarchy」第 2720–2831 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:2814,搜「backlinks」)。 ↩

  26. 出处:「Chapter 7: The Directory Hierarchy」第 2964–3013 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:2977,搜「front = front - strlen」)。 ↩

  27. 出处:「Chapter 7: The Directory Hierarchy」第 2953–2963 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:2960,搜「same inode」) · :2916(搜「lstat() rather than stat()」)。 ↩ ↩2

  28. 出处:「Chapter 7: The Directory Hierarchy」第 3010–3013 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:3013,搜「not constructed」)。 ↩ ↩2

  29. 出处:「Chapter 7: The Directory Hierarchy」第 2846–2851 段(text/13-ch07-chapter-7-the-directory-hierarchy.txt:2850,搜「not an option」)。 ↩

文件系统与文件 — 从磁盘块到 statx

Previous Page

信号 — 空消息、处置与阻塞

Next Page

On this page

目录层次 — 遍历、挂载与 pwd 的攀爬算法1. 顶层全景:目录 API 的四个层次2. 目录流三件套与 dirent 的可移植性3. scandir:把「过滤 + 排序 + 数组」一次做完4. 挂载:遍历语义的分水岭5. 树遍历:从手写递归到 nftw手写递归的两个经典坑nftw:库替你递归,但回调没有口袋主线例子走查:spl_du1——按层累计数组fts:BSD 的可控遍历(进阶)6. 反方向:手写 pwd 的攀爬算法7. 作者的判断与证据8. 边界与局限9. 可带走的10. 原文地图Footnotes