cómo encontrar un bucle en el sistema de archivos?

Question

cómo encontrar un bucle en el sistema de archivos en Linux? estoy indexando todos los archivos para hacer la búsqueda rápida (O (1)) ... estoy usando el lenguaje de programación c para implementar usando las funciones de la biblioteca en dir.h .... Puedo escanear a través de un sistema de archivos completo pero entra un bucle si hay un bucle en el sistema de archivos (ejemplo bucle de montaje) ... cómo encontrar el bucle en el sistema de archivos ... he visto updatedb comando de informes cuando hay bucle en el sistema de archivos ... no entiendo la lógica ... ¿alguien puede ayudar a encontrar una solución para esto?

Answer 1

yo encontramos este interesante comentario aquí sobre finding loops in a DAG:

Steinar H. Gunderson escribió:

En Jue 26 Feb de 2004 00:28:32 +0100, Orlondow escribió:

... también se reproducen en Cormen-Leiserson-Rivest, IIC. ¿Cuál es más fácil para encontrar.

Sí, en realidad tengo Cormen y otros, pero nunca me llamó la atención al mirar hacia arriba " componentes fuertemente conectados" cuando quería detección de ciclo. Gracias, voy a echarle un vistazo. :-)

Para encontrar un ciclo en un grafo dirigido (no le importa qué ciclo), siempre y ya que existe uno, usted no tiene que ir por la borda con SCC. Profundo antiguo profundidad primera búsqueda DFS (en el mismo capítulo de CLRS) es suficiente.

Por lo tanto, en términos generales, mientras recorre el árbol de directorios, cree un DAG que represente la estructura del árbol con los datos en el nodo que hace referencia al inodo del archivo. Luego, solo verifica que no visites un nodo más de una vez.

Answer 2

Esto se conoce más comúnmente como un "ciclo". Entonces quiere implementar "detección de ciclo". Hay muchas maneras de hacer esto; No sé si esto es para el trabajo a domicilio o no, pero un método simple, no necesariamente el más óptimo, es a través de la búsqueda de punteros.

Answer 3

La forma general de evitar volver a escanear nodos en un gráfico es marcar los nodos a medida que los pasa, y luego ignorar los nodos que están marcados. Esto no es demasiado práctico si no desea modificar el gráfico que está escaneando, por lo que necesita una forma de marcar los nodos externamente. La manera más fácil que se me ocurre para hacer esto en Linux sería almacenar un dispositivo/inodo para cada directorio que visite. Luego, cuando mira un directorio, primero verifique que aún no haya visto ningún directorio con el mismo dispositivo/inode. Esto no solo maneja ciclos, sino también árboles que se fusionan entre sí.

Para obtener el número de dispositivo/inodo eche un vistazo a las funciones stat/fstat y los miembros st_dev y st_ino de la estructura estadística.

Para almacenar los datos, es probable que desee ver un hash-table o un árbol binario.

Answer 4

Tal vez estoy siendo un poco oscuro aquí, pero no son las dos formas en que podría crear un ciclo:

• mediante la creación de un enlace simbólico
• montando algo dos veces

Para lidiar con esto, puede obtener una lista de los montajes antes de comenzar a indexar, y si no todos, excepto el primero de los mismos, y puede ignorar los enlaces a medida que los encuentre en el proceso de indexación.

Answer 5

Manera simple. Solo haga una caminata en el árbol de directorios en profundidad, manteniendo una pila de nodos sobre usted a medida que avanza. En cada nodo que visitas, si ese nodo ya está en la pila, tienes un ciclo.

// here's a stack of nodes 
node stack[1000]; 

walk(node, level){ 
    if (node in stack[0..level-1]) then there is a cycle 
    else 
     stack[level] = node 
     for each subnode x of node 
      walk(x, level+1) 
} 

Answer 6

Como otros han dicho, no hay tal cosa como un bucle en un sistema de archivos si se da cuenta de que el camino es parte de un nombre de archivo, a menos que su un enlace simbólico cíclico.

Por ejemplo, si arranca un poco de distro (digamos Debian) en un dispositivo de bucle, o incluso en un directorio, y lo hace en un equipo Debian, ahora ha duplicado muchas cosas.

Por ejemplo, supongamos que ejecuta Debian Lenny y arranca una copia mínima de/lenny.

/lenny/usr/* va a ser lo mismo que/usr/*. No hay una forma "barata" de evitar esto.

Puesto que ya está llamando a un stat() en cada nodo (estoy asumiendo que usted está utilizando ftw()/ftw64(), es posible que así:

• Tener ftw()' s callback inserta el nombre del nodo en una matriz, que tiene miembros de estructura que pueden almacenar un hash del archivo que es poco probable que colisione. md5 no va a cortarlo.
• Actualizar una tabla hash basada en ese compendio y el nombre del archivo (no la ruta).

No hay peligro de acelerar su escaneo, pero lo hará reduce significativamente el tiempo que se tarda en buscar.

Si usa los subprocesos correctamente y establece afinidad, el hashing y la indexación pueden ocurrir en un núcleo mientras que el otro está enlazado de E/S (cuando hay varios núcleos disponibles).

Sin embargo, 'solo' verificar duplicados no será una cura, y estoy seguro de que su programa querrá devolver las ubicaciones de todos los archivos llamados 'foo', incluso si hay cuatro copias idénticas a mencionar.

Answer 7

Btw. No necesita buscar el bucle en el sistema de archivos.

Usted está indexando todo el disco. Por lo tanto, no necesita seguir enlaces simbólicos, ya que cada archivo debe ser accesible de forma normal (sin enlaces simbólicos). Solo necesita comprobar los puntos de montaje si algún disco está montado más de una vez, simplemente ignore los puntos de apoyo de la montura.