¿Existe un algoritmo para decidir si un enlace simbólico se repite?

Los sistemas Unix generalmente solo se equivocan si se enfrentan a una ruta que contiene un bucle de enlace simbólico o demasiados enlaces simbólicos, porque tienen un límite en la cantidad de enlaces simbólicos que atravesarán en una búsqueda de ruta. Pero, ¿hay alguna manera de decidir si una ruta determinada se resuelve en algo o contiene un bucle, incluso si contiene más enlaces de los que un Unix está dispuesto a seguir? ¿O es este un problema formalmente indecidible? Y si puede decidirse, ¿puede decidirse en una cantidad de tiempo / memoria razonable (por ejemplo, sin tener que visitar todos los archivos en un sistema de archivos)?

Algunos ejemplos:

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

Editar :

Para aclarar, no estoy preguntando sobre la búsqueda de bucles en el sistema de archivos, estoy preguntando sobre un algoritmo de decisión que decida de una ruta dada si se resuelve en un archivo / directorio definido o si no se resuelve en absoluto. Por ejemplo, en el siguiente sistema, hay un bucle, pero la ruta dada aún se resuelve bien:

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

Este árbol de directorios claramente tiene un ciclo, pero la ruta a/b/b/b/b/baún se resuelve bien /a.

No entiendo completamente lo que estás preguntando. Si no supiera nada mejor, creo que me preguntaba si había una manera de detectar esto mientras se trataba de un archivo. No creo que esto sea posible.

El único método que puedo concebir es hacer una búsqueda en la que empiezas específicamente a buscar a través de una rama en particular en el árbol de directorios.

Ejemplo

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

5 directories, 1 file

El findcomando detectará este bucle pero en realidad no le dirá mucho al respecto.

$ 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

Elegí arbitrariamente 15 niveles para bloquear cualquier salida que muestre el find. Sin embargo, puede soltar ese interruptor ( -mindepth) si no le importa que se muestre el árbol de directorios. El findcomando aún detecta el bucle y se detiene:

$ 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

Por cierto, si desea anular el valor predeterminado MAXSYMLINKSque aparentemente es 40 en Linux (versiones 3.x más nuevas del núcleo), puede ver estas preguntas y respuestas de U&L tituladas: ¿Cómo aumentar MAXSYMLINKS ?

Usando el comando symlinks

Hay una herramienta que los mantenedores de sitios FTP podrían usar llamada symlinksque ayudará a exponer problemas con la herramienta de árboles largos o colgantes que fueron causados ​​por enlaces simbólicos.

En ciertos casos, la symlinksherramienta también podría usarse para eliminar enlaces ofensivos.

Ejemplo

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

La biblioteca glibc

La biblioteca glibc parece ofrecer algunas funciones C en torno a esto, pero no conozco completamente su función o cómo usarlas realmente. Así que solo puedo señalarlos.

La página del manual, man symlinkmuestra la definición de función para una función llamada symlink(). La descripción es así:

symlink () crea un enlace simbólico llamado newpath que contiene la cadena oldpath.

Uno de los errores indica que esta función devuelve:

ELOOP Se encontraron demasiados enlaces simbólicos al resolver newpath.

También lo dirigiré a la página de manual, man path_resolutionque analiza cómo Unix determina las rutas a los elementos en el disco. Específicamente este párrafo.

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").

Bien, después de pensarlo más, creo que tengo una solución clara.

La idea fundamental es que si cada enlace que forma parte de una ruta se resuelve en algo, entonces se resuelve toda la ruta. O al revés, si una ruta no se resuelve, entonces debe haber un enlace simbólico específico que requiera un recorrido que no se resuelva.

Mientras pensaba en este problema anteriormente, estaba usando un algoritmo que atravesaba elementos de una ruta comenzando desde la raíz, y cuando encontró un enlace simbólico, reemplazó ese elemento de ruta con el contenido del enlace simbólico y luego continuó atravesando. Dado que este enfoque no recuerda qué enlace simbólico está resolviendo actualmente, no puede detectar cuándo está en un bucle sin resolución.

Si el algoritmo realiza un seguimiento de qué enlace simbólico está resolviendo actualmente (o qué enlaces simbólicos en caso de enlaces recursivos), puede detectar si está intentando resolver un enlace de forma recursiva que todavía está ocupado resolviendo.

Algoritmo:

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

editar :

Tengo una implementación funcional de esto en Python en https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher .

Python tiene una función llamada networkx.simple_cycles () que se puede usar para esto. Pero sí, necesitaría leer todos los archivos del sistema.

>>> 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']]

En un sistema inactivo (es decir, cuando no se producen cambios), sí, hay un algoritmo. Hay un número finito de enlaces simbólicos, por lo que constituyen un gráfico finito, y la detección de ciclos es un proceso finitario.

En un sistema en vivo, no hay forma de detectar ciclos, porque los enlaces simbólicos pueden cambiar mientras el detector de ciclos está funcionando. Leer cada enlace simbólico es atómico, pero seguir un enlace simbólico no lo es. Si algunos enlaces simbólicos siguen cambiando mientras el núcleo está haciendo el recorrido, podría terminar en una ruta infinita que involucra enlaces distintos.

Por lo que puedo ver al observar las fuentes actuales del kernel de Linux, todo lo que hace el kernel es llevar un recuento de la cantidad de enlaces que se siguen y se equivoca si es mayor que algún número. Vea la línea 1330 en namei.c para el comentario y la nested_symlink()función. La macro ELOOP (el número de error devuelto por una read(2)llamada del sistema para esta situación) aparece en varios lugares en ese archivo, por lo que puede que no sea tan simple como contar los enlaces seguidos, pero eso es seguro.

Existen varios algoritmos para encontrar "ciclos" en listas vinculadas ( algoritmo de detección de ciclos de Floyd ) o en gráficos dirigidos . No me queda claro cuál tendría que hacer para detectar un "ciclo" o "ciclo" real en una ruta en particular. En cualquier caso, los algoritmos pueden tardar mucho tiempo en ejecutarse, por lo que supongo que solo contando el número de enlaces simbólicos seguidos le lleva el 90% del camino hacia su objetivo.