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

16

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.

JanKanis
fuente
¿Qué dice la herramienta de línea de comando readlink ...sobre las situaciones anteriores?
slm
1
¿Estás preguntando si podemos distinguir solo por el nombre de ruta si hay bucles? ¿O podemos hacer esto en un sistema operativo real, usando las herramientas estándar y verificando a qué se resuelven los diversos componentes del nombre de ruta?
Mike Diehn el
@MikeDiehn Obviamente, uno no puede distinguir solo una ruta si se resuelve sin realizar operaciones del sistema de archivos. Pero también con un entorno de sistema operativo no es sencillo distinguir una ruta que simplemente requiere atravesar muchos enlaces simbólicos para resolver de uno que no se resuelve en absoluto.
JanKanis

Respuestas:

10

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").
slm
fuente
Si es posible, me gustaría una forma de detectar un bucle de enlace simbólico cuando se le da una sola ruta, y resolver los enlaces simbólicos manualmente en un programa en lugar de dejar que el sistema operativo lo haga. Pero me pregunto si esto es posible en absoluto. La solución de búsqueda parece interesante, pero ¿tiene alguna idea / cómo / find detecta los bucles de enlace simbólico, y si el método que utiliza está completo (es decir, detecta todos los bucles posibles y no identifica erróneamente ninguna ruta sin bucle)?
JanKanis
@Somejan: vea mis actualizaciones a la A. Avíseme si eso tiene sentido.
slm
5

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 .

JanKanis
fuente
3

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']]
Back2Basics
fuente
También pensé en usar algún tipo de algoritmo gráfico, pero no estoy seguro de si un árbol de directorios con enlaces simbólicos puede representarse adecuadamente en un gráfico simple. En un árbol de directorios abc donde c es un enlace simbólico a ..., hay un bucle, pero las rutas como a / b / c / b / c / b aún se resuelven ya que solo siguen el bucle un número finito de veces y no sigue en bucle.
JanKanis
@Somejan: un espacio de nombres del sistema de archivos es un gráfico, y un nombre de archivo es una ruta elegida sobre ese gráfico.
ninjalj
@ninjalj: Sí, un sistema de archivos es un gráfico, pero no creo que un nombre de archivo sea simplemente una ruta sobre ese gráfico. El nombre de archivo se puede ver como un conjunto de instrucciones sobre cómo recorrer el gráfico. Incluso si el gráfico contiene ciclos que no significan que un nombre de archivo que sigue ese ciclo no necesariamente se resuelve, vea mi ejemplo en mi comentario anterior.
JanKanis
3

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.

Gilles 'SO- deja de ser malvado'
fuente
Hay maneras de mitigar esos cambios para lograr una precisión del 98-99%. Podrías hacer que preste atención a las marcas de tiempo en los archivos y no sugeriría seguir los enlaces. Como es recursivo desde la raíz, encontrará el directorio real más tarde.
Back2Basics
1
@ Back2Basics Estos números no tienen ningún significado. Esta es una interfaz del núcleo. Si no funciona todo el tiempo, no funciona, punto.
Gilles 'SO- deja de ser malvado'
2

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.

Bruce Ediger
fuente
Para usos prácticos, solo contar el número de enlaces recorridos está bien, especialmente porque eso es lo que hace el núcleo, por lo que incluso si encuentra una ruta de resolución correcta que tiene demasiados enlaces simbólicos, aún no puede usar esa ruta para nada práctico ( es decir, eso no implica la resolución manual de enlaces simbólicos)
JanKanis