16

Unix systems usually just error out if they are confronted with a path that contains a symlink loop or just too many symlinks, because they have a limit to the number of symlinks they will traverse in one path lookup. But is there a way to actually decide if a given path resolves to something or contains a loop, even if it contains more links than a unix is willing to follow? Or is this a formally undecidable problem? And if it can be decided, can it be decided in a reasonable amount of time/memory (e.g. without having to visit all files on a filesystem)?

Some examples:

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

Edit:

To clarify, I am not asking about finding loops in the file system, I am asking about a decision algorithm that decides of a given path whether it resolves to a definite file/directory or whether it does not resolve at all. For example in the following system, there is a loop, but the given path still resolves fine:

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

This directory tree clearly has a cycle, but the path a/b/b/b/b/b still resolves fine to /a.

  • What does the command line tool readlink ... say about the above situations? – slm Nov 6 '13 at 23:42
  • 1
    Are you asking if we can tell just from the pathname if there are loops? Or can we do this in a real operating system, using the standard tools and checking what the various components of the pathname resolve to? – Mike Diehn Nov 7 '13 at 2:14
  • @MikeDiehn Obviously one can't tell from just a path if it resolves without doing filesystem operations. But also with an OS environment it is not straightforward to distinguish a path that merely requires traversing a lot of symlinks to resolve from one that does not resolve at all. – JanKanis Nov 7 '13 at 8:57
10

I don't fully understand what you're asking. If I didn't know any better I think you were asking if there was a way to detect this while in the midst of dealing with a file. I don't believe this is possible.

The only method I can conceive of is doing a find where you specifically start looking through a particular branch in the directory tree.

Example

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

5 directories, 1 file

The find command will detect this loop but not really tell you a whole lot about it.

$ 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

I arbitrarily picked 15 levels so as to block any output being displayed by the find. You can however drop that switch (-mindepth) if you don't care about the directory tree being displayed. The find command still detects the loop and stops:

$ 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

Incidentally, if you want to override the default MAXSYMLINKS which is apparently 40 on Linux (newer 3.x versions of the kernel) you can see this U&L Q&A titled: How do you increase MAXSYMLINKS.

Using the symlinks command

There is a tool that FTP site maintainers could use called symlinks which will help expose issues with tool long or dangling trees that were caused by symbolic links.

In certain cases the symlinks tool could be used to delete offending links too.

Example

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

The glibc library

The glibc library looks to offer some C functions around this, but I don't entirely know their role or how to actually use them. So I can only merely point them out to you.

The man page, man symlink shows the function definition for a function called symlink(). The description goes like this:

symlink() creates a symbolic link named newpath which contains the string oldpath.

One of the error states that this function returns:

ELOOP Too many symbolic links were encountered in resolving newpath.

I'll also direct you to the man page, man path_resolution which discusses how Unix determines paths to items on disk. Specifically this paragraph.

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").
  • If possible I would like a way to detect a symlink loop when given a single path, and resolving the symlinks manually in a program instead of letting the OS do it. But I am wondering if this is possible at all. The find solution looks interesting, but do you have any idea /how/ find detects symlink loops, and if the method it uses is complete (i.e. detects all possible loops and doesn't misidentify any non-looping paths)? – JanKanis Nov 7 '13 at 9:04
  • @Somejan - see my updates to the A. Let me know if that makes sense. – slm Nov 7 '13 at 13:14
5

OK, after some more thought I think I have a clear solution.

The critical insight is that if every link that is part of a path resolves to something, then the entire path resolves. Or the other way around, if a path does not resolve then there must be a specific symlink that requires traversing that does not resolve.

While thinking about this problem previously I was using an algorithm that traversed elements of a path starting from the root, and when it encountered a symlink it replaced that path element with the contents of the symlink and then continued traversing. Since this approach doesn't remember which symlink it is currently resolving it cannot detect when it is in a nonresolving loop.

If the algorithm keeps track of which symlink it is currently resolving (or which symlinks in case of recursive links), it can detect if it is attempting to resolve a link again recursively which it is still busy resolving.

Algorithm:

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

edit:

I have a working implementation of this in python at https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher.

3

Python has a function called networkx.simple_cycles() that can be used for this. But yes it would need to read every file on the system.

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge('A', 'B')
>>> G.add_edge('B', 'C')
>>> G.add_edge('C', 'D')
>>> G.add_edge('C', 'A')
>>> nx.simple_cycles(G)
[['A', 'B', 'C', 'A']]
  • I also thought about using some kind of graph algorithm, but I'm not sure if a directory tree with symlinks can be adequately represented in a simple graph. In a directory tree a-b-c where c is a symlink to .., there is a loop, but paths like a/b/c/b/c/b still resolve as they only follow the loop a finite number of times and don't keep looping. – JanKanis Nov 7 '13 at 9:09
  • @Somejan: a filesystem namespace is a graph, and a filename is a path chosen over that graph. – ninjalj Nov 7 '13 at 11:55
  • @ninjalj: Yes a filesystem is a graph, but I don't think a filename is simply a path over that graph. The filename can be seen as a set of instructions on how to traverse the graph. Even if the graph contains cycles that does not mean that a filename that follows that cycle necessarily does not resolve, see my example in my previous comment. – JanKanis Nov 8 '13 at 0:09
3

On a quiescent system (i.e. when no changes are taking place), yes, there is an algorithm. There is a finite number of symbolic links, so they constitute a finite graph, and detecting cycles is a finitary process.

On a live system, there is no way to detect cycles, because symbolic links can change while the cycle detector is running. Reading each symbolic link is atomic, but following a symbolic link is not. If some symlinks keep changing while the kernel is doing the traversal, it could end up on an infinite path involving distinct links.

  • There are ways to mitigate those changes to bring it up to 98-99% accuracy. You could make it pay attention to the time stamps on files and I wouldn't suggesting actually following the links. Since it is recursive from the root it will find the actual directory later. – Back2Basics Nov 13 '13 at 6:06
  • 1
    @Back2Basics These numbers are completely meaningless. This is a kernel interface. If it doesn't work all the time, it doesn't work, period. – Gilles Nov 13 '13 at 8:18
2

As near as I can tell from looking at current Linux kernel sources, all the kernel does is keep a count of how many links it's followed, and it errors out if that's bigger than some number. See line 1330 in namei.c for the comment, and the nested_symlink() function. The ELOOP macro (the error number returned from a read(2) system call for this situation) shows up in a number of places in that file, so it may not be as simple as counting links followed, but that's sure what it looks like.

There are a number of algorithms for finding "cycles" in linked lists (Floyd's cycle detection algorithm) or in directed graphs. It's not clear to me which one you'd have to do to detect an actual "loop" or "cycle" in a particular path. In any case, the algorithms could take a long time to run, so I'm guessing that just counting the number of symbolic links followed gets you 90% of the way to your goal.

  • For practical uses, just counting the number of links traversed is fine, especially since that is what the kernel does, so even if you encounter a correctly resolving path that has too many symlinks, you still can't use that path for anything practical (i.e. that does not involve manually resolving symlinks) – JanKanis Nov 8 '13 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.