是否有算法来决定符号链接是否循环？

Question

如果 Unix 系统遇到包含符号链接循环或太多符号链接的路径，它们通常只会出错，因为它们对在一次路径查找中将遍历的符号链接数量有限制。但是有没有办法真正确定给定的路径是否解析为某些内容或包含循环，即使它包含的链接多于 unix 愿意遵循的链接？或者这是一个形式上不可判定的问题？如果可以决定，是否可以在合理的时间/内存量内决定（例如，不必访问文件系统上的所有文件）？

一些例子：

a/b/c/d
where a/b is a symlink to ../e
and e is a symlink to f
and f is a symlink to a/b

a/b/c/d
where a/b/c is a symlink to ../c

a/b/c/d
where a/b/c is a symlink to ../c/d

a/b/c/d
where a/b/c is a symlink to /a/b/e
where a/b/e is a symlink to /a/b/f
where a/b/f is a symlink to /a/b/g

编辑：

澄清一下，我不是在问在文件系统中查找循环，而是在问一种决策算法，该算法决定给定的路径是解析为确定的文件/目录还是根本不解析。例如在下面的系统中，有一个循环，但给定的路径仍然可以正常解析：

/ -- a -- b
where b is a symlink to /a

这个目录树显然有一个循环，但路径a/b/b/b/b/b仍然可以很好地解析为/a.

Answer 1

我不完全明白你在问什么。如果我不知道更好，我想你是在问是否有办法在处理文件的过程中检测到这一点。我不相信这是可能的。

我能想到的唯一方法是进行查找，您可以在其中专门开始查看目录树中的特定分支。

例子

$ tree 
.
`-- a
    `-- b
        |-- c
        |   `-- d
        |       `-- e -> ../../../../a/b
        `-- e -> e

5 directories, 1 file

该find命令会检测到这个循环，但不会真正告诉你很多关于它的信息。

$ find -L . -mindepth 15
find: File system loop detected; `./a/b/c/d/e' is part of the same file system loop as `./a/b'.
find: `./a/b/e': Too many levels of symbolic links

我随意选择了 15 个级别，以阻止find. 但是，-mindepth如果您不关心正在显示的目录树，则可以删除该开关 ( )。该find命令仍然检测到循环并停止：

$ find -L . 
.
./a
./a/b
./a/b/c
./a/b/c/d
find: File system loop detected; `./a/b/c/d/e' is part of the same file system loop as `./a/b'.
find: `./a/b/e': Too many levels of symbolic links

顺便说一句，如果您想覆盖MAXSYMLINKSLinux（内核的较新 3.x 版本）上显然为 40的默认值，您可以看到此 U&L 问答题为：How do you increase MAXSYMLINKS。

使用符号链接命令

FTP 站点维护人员可以使用一个名为的工具，该工具symlinks将有助于暴露由符号链接引起的树过长或悬空的问题。

在某些情况下，该symlinks工具也可用于删除违规链接。

例子

$ symlinks -srv a
lengthy:  /home/saml/tst/99159/a/b/c/d/e -> ../../../../a/b
dangling: /home/saml/tst/99159/a/b/e -> e

glibc 库

glibc 库看起来为此提供了一些 C 函数，但我并不完全了解它们的作用或如何实际使用它们。所以我只能给你们指出来。

手册页man symlink显示了名为 的函数的函数定义symlink()。描述是这样的：

symlink() 创建一个名为 newpath 的符号链接，其中包含字符串 oldpath。

错误之一表明此函数返回：

ELOOP 在解析 newpath 时遇到太多符号链接。

我还将引导您查看手册页，man path_resolution其中讨论了 Unix 如何确定磁盘上项目的路径。特别是这一段。

If  the component is found and is a symbolic link (symlink), we first 
resolve this symbolic link (with the current lookup directory as starting 
lookup directory).  Upon error, that error is returned.  If the result is 
not a directory, an ENOTDIR error is returned.  If the resolution of the 
symlink is successful and returns a directory, we set the current lookup
directory to that directory, and go to the next component.  Note that the 
resolution process here involves recursion.  In order  to  protect  the 
kernel against stack overflow, and also to protect against denial of 
service, there are limits on the maximum recursion depth, and on the maximum 
number of symbolic links followed.  An ELOOP error is returned  when  the
maximum is exceeded ("Too many levels of symbolic links").

Answer 2

好的，经过一些思考，我想我有一个明确的解决方案。

关键的见解是，如果作为路径一部分的每个链接都解析为某些内容，那么整个路径都会解析。或者反过来，如果路径无法解析，那么必须有一个特定的符号链接需要遍历但无法解析。

之前在考虑这个问题时，我使用了一种算法，该算法从根开始遍历路径的元素，当它遇到符号链接时，它会用符号链接的内容替换该路径元素，然后继续遍历。由于这种方法不记得它当前正在解析哪个符号链接，因此无法检测到它何时处于非解析循环中。

如果算法跟踪它当前正在解析哪个符号链接（或者在递归链接的情况下是哪个符号链接），它可以检测它是否正在尝试再次递归解析它仍在忙于解析的链接。

算法：

initialize `location` to the current working directory
initialize `link_contents` to the path we want to resolve
initialize `active_symlinks` to the empty set

def resolve_symlink(location, link_contents, active_symlinks) :
    loop forever:
        next_location = location / [first element of link_contents]
        see if next_location is a symlink.
        if so:
            if next_location in active_symlinks: abort, we have a loop
            location = resolve_symlink(location, readlink(next_location), active_symlinks ? {next_location})
        else:
            location = next_location
        strip first element of link_contents
        if link_contents is empty: 
            return location

编辑：

我在https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher在 python 中有一个工作实现。

编辑 2：Bitbucket 停止托管 mercurial 存储库。这是完整的文件：

initialize `location` to the current working directory
initialize `link_contents` to the path we want to resolve
initialize `active_symlinks` to the empty set

def resolve_symlink(location, link_contents, active_symlinks) :
    loop forever:
        next_location = location / [first element of link_contents]
        see if next_location is a symlink.
        if so:
            if next_location in active_symlinks: abort, we have a loop
            location = resolve_symlink(location, readlink(next_location), active_symlinks ? {next_location})
        else:
            location = next_location
        strip first element of link_contents
        if link_contents is empty: 
            return location

Answer 3

在静止系统（即没有发生变化时），是的，有一个算法。符号链接的数量是有限的，所以它们构成了一个有限的图，检测循环是一个有限的过程。

在实时系统上，无法检测循环，因为符号链接可能会在循环检测器运行时发生变化。读取每个符号链接是原子的，但跟随符号链接不是。如果在内核进行遍历时某些符号链接不断更改，则最终可能会出现在涉及不同链接的无限路径上。