come trovare un loop nel file system?

Question

come trovare un loop nel file system in Linux? sto indicizzando tutti i file per rendere veloce la ricerca (O (1)) ... sto usando il linguaggio di programmazione c per implementare usando le funzioni della libreria in dir.h .... Posso scansionare l'intero file system ma entra un ciclo se c'è un loop nel filesystem (esempio loop mount) ... come trovare il loop nel file system .. ho visto il comando updatedb di segnalazione quando c'è un loop nel file system ... non capisco la logica ... Qualcuno può aiutare a trovare una soluzione per questo?

Answer 1

ho trovato questo interessante commento qui su finding loops in a DAG:

Steinar H. Gunderson ha scritto:

On Thu, 26 Feb 2004 00:28:32 +0100, Orlondow ha scritto:

... riprodotto anche nella Cormen-Leiserson-Rivest, IIC. Quale è più facile da trovare .

Sì, io in realtà sono Cormen et al, ma non è mai mi ha colpito per cercare "componenti fortemente connesse" quando volevo rilevamento ciclo. Grazie, lo invierò a . :-)

Per trovare un ciclo in un grafo orientato (non si cura quale ciclo) fintanto come esiste uno, non c'è bisogno di andare in mare con SCC. Pianura vecchia profondità prima ricerca DFS (nello stesso capitolo di CLRS) è sufficiente.

Quindi, grosso modo, mentre si attraversa l'albero delle directory, creare un DAG che rappresenta la struttura dell'albero con i dati sul nodo che si riferiscono all'inode del file. Quindi, è sufficiente verificare di non visitare più di una volta il nodo.

Answer 2

Questo è più comunemente indicato come un "ciclo". Quindi vuoi implementare il "rilevamento del ciclo". Ci sono molti modi per farlo; Non so se questo è per il lavoro a casa o meno, ma un metodo semplice, non necessariamente il più ottimale, è attraverso l'inseguimento del puntatore.

Answer 3

Il modo generale per impedire la scansione dei nodi in un grafico è contrassegnare i nodi mentre vengono passati e quindi ignorare i nodi contrassegnati. Questo non è molto pratico se non si desidera modificare il grafico su cui si sta eseguendo la scansione, quindi è necessario un modo per contrassegnare i nodi esternamente. Il modo più semplice con cui posso pensare di farlo sotto Linux è di memorizzare un dispositivo/inode per ogni directory che visiti. Quindi, quando guardi una directory, per prima cosa controlla di non aver già visto nessuna directory con lo stesso dispositivo/inode. Questo non solo gestisce i cicli, ma anche gli alberi che si fondono l'uno nell'altro.

Per ottenere il numero dispositivo/inode, dare un'occhiata alle funzioni stat/fstat e ai membri st_dev e st_ino della struttura delle statistiche.

Per la memorizzazione dei dati, probabilmente stai cercando uno hash-table o un albero binario.

Answer 4

Forse sto essendo un po 'debole qui, ma non sono i due modi in cui è possibile creare un ciclo:

• di creare un collegamento simbolico
• montando qualcosa di due volte

Per far fronte a questi, è possibile ottenere un elenco dei supporti prima di iniziare l'indicizzazione e, se non tutti, tranne il primo degli stessi file, e si possono ignorare i collegamenti quando li si incontra nel processo di indicizzazione.

Answer 5

Modo semplice. Basta fare una prima camminata dell'albero della directory, mantenendo una pila di nodi sopra di te mentre vai. In ogni nodo che visiti, se quel nodo è già nello stack, hai 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

Come altri hanno detto, non v'è alcuna cosa come un ciclo in un file system, se ci si rende conto che il percorso è parte di un nome di file, a meno che il suo un link simbolico ciclico.

Ad esempio, se si avvia qualche distro (diciamo Debian) su un dispositivo ad anello, o anche su una directory, e lo si fa su una macchina Debian, si è ora duplicato un sacco di cose.

Ad esempio, si supponga di eseguire Debian Lenny e di riavviarne una copia minima in/lenny.

/lenny/usr/* sarà uguale a/usr/*. Non esiste un modo "economico" per evitare questo.

Dal momento che si sta già chiamando uno stat() su ciascun nodo (sto supponendo che si sta utilizzando FTW()/ftw64(), si può anche:

• Avere FTW()' s callback inserisce il nome del nodo in una matrice, che ha membri della struttura che possono archiviare un hash del file che è improbabile collidere, md5 non lo taglierà per questo
• Aggiorna una tabella hash basata su quel digest e il nome del file (non il percorso)

Questo non è un pericolo di velocizzare la scansione, ma lo farà ridurre in modo significativo il tempo necessario per la ricerca.

Se si utilizzano i thread in modo corretto e si imposta l'affinità, l'hashing e l'indicizzazione possono avvenire su un core mentre l'altro è associato ai/o (quando sono disponibili più core).

Tuttavia, 'solo' il controllo di montaggi duplicati non sarà una cura, inoltre sono sicuro che il programma vorrebbe restituire le posizioni di tutti i file denominati 'foo', anche se ci sono quattro copie identiche a citare.

Answer 7

Btw. Non è necessario cercare il ciclo nel file system.

Si sta indicizzando l'intero disco. Quindi non è necessario seguire collegamenti simbolici poiché ogni file deve essere accessibile in modo normale (senza collegamenti simbolici). Hai solo bisogno di controllare i punti di mount se alcuni dischi sono montati più di una volta, ignorando semplicemente i punti di riposo del mount.