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

16

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.

JanKanis
źródło
Co narzędzie wiersza poleceń readlink ...mówi o powyższych sytuacjach?
slm
1
Czy pytasz, czy na podstawie nazwy ścieżki możemy stwierdzić, czy istnieją pętle? Czy możemy to zrobić w prawdziwym systemie operacyjnym, przy użyciu standardowych narzędzi i sprawdzając, na czym polegają różne składniki nazwy ścieżki?
Mike Diehn
@MikeDiehn Oczywiście nie można stwierdzić na podstawie ścieżki tylko, czy rozwiązuje się to bez wykonywania operacji na systemie plików. Ale także w środowisku systemu operacyjnego nie jest łatwo odróżnić ścieżkę, która wymaga jedynie przejścia wielu dowiązań symbolicznych w celu rozwiązania od ścieżki, która w ogóle nie rozwiązuje.
JanKanis,

Odpowiedzi:

10

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").
slm
źródło
Jeśli to możliwe, chciałbym znaleźć sposób na wykrycie pętli dowiązań symbolicznych, gdy podano jedną ścieżkę, i ręczne rozwiązanie dowiązań symbolicznych w programie zamiast pozwalania na to systemowi operacyjnemu. Ale zastanawiam się, czy to w ogóle możliwe. Rozwiązanie find wygląda interesująco, ale czy masz jakiś pomysł / how / find wykrywa pętle dowiązań symbolicznych i czy metoda, której używa jest kompletna (tj. Wykrywa wszystkie możliwe pętle i nie identyfikuje błędnie żadnych ścieżek nie zapętlających)?
JanKanis,
@ Somejan - zobacz moje aktualizacje do A. Daj mi znać, czy to ma sens.
slm
5

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 .

JanKanis
źródło
3

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']]
Back2Basics
źródło
Zastanawiałem się również nad zastosowaniem pewnego rodzaju algorytmu grafowego, ale nie jestem pewien, czy drzewo katalogów z dowiązaniami symbolicznymi można odpowiednio przedstawić na prostym grafie. W drzewie katalogów abc, gdzie c jest dowiązaniem symbolicznym do .., istnieje pętla, ale ścieżki takie jak / b / c / b / c / b nadal rozpoznają się, ponieważ podążają za pętlą tylko skończoną liczbę razy i nie zapętlać.
JanKanis,
@ Somejan: przestrzeń nazw systemu plików to wykres, a nazwa pliku to ścieżka wybrana nad tym wykresem.
ninjalj
@ninjalj: Tak, system plików to wykres, ale nie sądzę, że nazwa pliku to po prostu ścieżka nad tym wykresem. Nazwa pliku może być postrzegana jako zestaw instrukcji dotyczących przechodzenia przez wykres. Nawet jeśli wykres zawiera cykle, co nie oznacza, że ​​nazwa pliku następująca po tym cyklu niekoniecznie się rozwiązuje, zobacz mój przykład w poprzednim komentarzu.
JanKanis,
3

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.

Gilles „SO- przestań być zły”
źródło
Istnieją sposoby na złagodzenie tych zmian, aby zwiększyć ich dokładność do 98–99%. Możesz sprawić, że zwróci uwagę na znaczniki czasu w plikach, a ja nie sugerowałbym, żebym faktycznie podążał za linkami. Ponieważ jest rekurencyjny z katalogu głównego, później znajdzie właściwy katalog.
Back2Basics
1
@ Back2Basics Liczby te są całkowicie bez znaczenia. To jest interfejs jądra. Jeśli to nie działa cały czas, to nie działa, kropka.
Gilles „SO- przestań być zły”
2

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.

Bruce Ediger
źródło
Dla praktycznych zastosowań samo liczenie liczby przeglądanych łączy jest w porządku, zwłaszcza, że ​​właśnie to robi jądro, więc nawet jeśli napotkasz poprawnie rozdzielającą ścieżkę, która ma zbyt wiele dowiązań symbolicznych, nadal nie możesz użyć tej ścieżki do niczego praktycznego ( tzn. że nie wymaga ręcznego rozwiązywania dowiązań symbolicznych)
JanKanis,