Czy istnieje algorytm decydujący, czy pętla dowiązania symbolicznego?

Systemy uniksowe zwykle po prostu mylą się, jeśli są skonfrontowane ze ścieżką zawierającą pętlę dowiązania symbolicznego lub po prostu zbyt wiele dowiązań symbolicznych, ponieważ mają ograniczenie liczby dowiązań symbolicznych, które przemierzają podczas jednego wyszukiwania ścieżki. Ale czy istnieje sposób, aby faktycznie zdecydować, czy dana ścieżka rozwiązuje coś lub zawiera pętlę, nawet jeśli zawiera więcej linków, niż unix jest skłonny podążać? Czy jest to formalnie nierozstrzygalny problem? A jeśli można to ustalić, czy można to zrobić w rozsądnym czasie / pamięci (np. Bez konieczności odwiedzania wszystkich plików w systemie plików)?

Kilka przykładów:

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

Edytuj :

Aby wyjaśnić, nie pytam o znalezienie pętli w systemie plików, pytam o algorytm decyzyjny, który decyduje o danej ścieżce, czy rozpoznaje określony plik / katalog, czy też wcale. Na przykład w następującym systemie istnieje pętla, ale podana ścieżka nadal rozwiązuje się dobrze:

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

To drzewo katalogów wyraźnie ma cykl, ale ścieżka a/b/b/b/b/bnadal dobrze się zgadza /a.

Nie do końca rozumiem, o co pytasz. Gdybym nie wiedział nic lepszego, myślę, że pytałeś, czy istnieje sposób na wykrycie tego w trakcie zajmowania się plikiem. Nie wierzę, że to jest możliwe.

Jedyną metodą, jaką mogę sobie wyobrazić, jest znalezienie, w którym konkretnie zaczniesz przeglądać określoną gałąź w drzewie katalogów.

Przykład

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

5 directories, 1 file

findPolecenie wykryje tę pętlę, ale naprawdę nie powiedzieć dużo o niej.

$ 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

Dowolnie wybrałem 15 poziomów, aby zablokować wszelkie dane wyjściowe wyświetlane przez find. Możesz jednak zrezygnować z przełącznika ( -mindepth), jeśli nie zależy Ci na wyświetleniu drzewa katalogów. findKomenda nadal wykrywa pętli i przystanków:

$ 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

Nawiasem mówiąc, jeśli chcesz zastąpić wartość domyślną, MAXSYMLINKSktóra najwyraźniej wynosi 40 w systemie Linux (nowsze wersje jądra 3.x), możesz zobaczyć następujące pytania i odpowiedzi U&L zatytułowane: Jak zwiększyć MAXSYMLINKS .

Za pomocą polecenia symlinks

Istnieje narzędzie, którego mogą używać opiekunowie stron FTP o nazwie symlinks które pomoże ujawnić problemy z długimi lub zwisającymi drzewami, które zostały spowodowane przez dowiązania symboliczne.

W niektórych przypadkach symlinksnarzędzie może być również użyte do usunięcia obraźliwych linków.

Przykład

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

Biblioteka glibc

Biblioteka glibc wygląda na to, że oferuje pewne funkcje C w tym zakresie, ale nie do końca znam ich rolę i sposób ich użycia. Więc mogę jedynie wskazać ci je.

Strona man symlinkpodręcznika pokazuje definicję funkcji o nazwie symlink(). Opis wygląda następująco:

symlink () tworzy dowiązanie symboliczne o nazwie newpath, które zawiera ciąg oldpath.

Jeden z błędów mówi, że ta funkcja zwraca:

ELOOP Napotkano zbyt wiele dowiązań symbolicznych podczas rozwiązywania nowej ścieżki.

Przekieruję cię również do strony man, man path_resolutionktóra omawia sposób, w jaki Unix określa ścieżki do elementów na dysku. W szczególności ten ustęp.

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

OK, po chwili namysłu myślę, że mam jasne rozwiązanie.

Krytyczny wgląd polega na tym, że jeśli każde łącze będące częścią ścieżki zostanie rozwiązane, wówczas cała ścieżka zostanie rozwiązana. Lub na odwrót, jeśli ścieżka nie rozwiązuje się, musi istnieć określone dowiązanie symboliczne, które wymaga przejścia, które nie rozwiązuje.

Myśląc o tym problemie, wcześniej korzystałem z algorytmu, który przemierzał elementy ścieżki zaczynając od korzenia, a kiedy napotkał dowiązanie symboliczne, zastąpił ten element ścieżki zawartością dowiązania symbolicznego, a następnie kontynuował przemierzanie. Ponieważ to podejście nie pamięta, które dowiązanie symboliczne obecnie przetwarza, nie może wykryć, gdy znajduje się w pętli nierozwiązanej.

Jeśli algorytm śledzi, które dowiązanie symboliczne aktualnie przetwarza (lub które dowiązania symboliczne w przypadku łączy rekurencyjnych), może wykryć, czy próbuje ponownie rozwiązać dowiązanie rekurencyjnie, które nadal jest zajęte.

Algorytm:

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

edycja :

Mam działającą implementację tego w python na https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher .

W Pythonie jest dostępna funkcja o nazwie networkx.simple_cycles (). Ale tak, musiałby odczytać każdy plik w systemie.

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

W systemie spoczynkowym (tzn. Gdy nie zachodzą żadne zmiany), tak, istnieje algorytm. Istnieje skończona liczba dowiązań symbolicznych, więc stanowią one skończony wykres, a wykrywanie cykli jest procesem skończonym.

W systemie na żywo nie ma możliwości wykrycia cykli, ponieważ dowiązania symboliczne mogą się zmieniać podczas działania detektora cykli. Odczytywanie każdego łącza symbolicznego jest atomowe, ale podążanie za nim nie jest. Jeśli niektóre dowiązania symboliczne ciągle się zmieniają, gdy jądro wykonuje przejście, może skończyć się na nieskończonej ścieżce zawierającej odrębne łącza.

Patrząc na obecne źródła jądra Linuksa, jak najbliżej, wszystko, co robi, to śledzenie liczby linków, które są śledzone, i błędy, jeśli jest większa niż pewna liczba. Zobacz linii 1330 w namei.c za komentarz, a nested_symlink()funkcję. Makro ELOOP (numer błędu zwrócony zread(2) wywołania systemowego dla tej sytuacji) pojawia się w wielu miejscach w tym pliku, więc może nie być tak proste, jak liczenie linków, ale na pewno tak to wygląda.

Istnieje wiele algorytmów służących do znajdowania „cykli” na połączonych listach ( algorytm wykrywania cyklu Floyda ) lub na ukierunkowanych wykresach . Nie jest dla mnie jasne, co należy zrobić, aby wykryć rzeczywistą „pętlę” lub „cykl” na określonej ścieżce. W każdym razie uruchomienie algorytmów może zająć dużo czasu, więc zgaduję, że samo zliczenie liczby dowiązań symbolicznych daje 90% drogi do celu.