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/b
nadal dobrze się zgadza /a
.
źródło
readlink ...
mówi o powyższych sytuacjach?Odpowiedzi:
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
find
Polecenie wykryje tę pętlę, ale naprawdę nie powiedzieć dużo o niej.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.find
Komenda nadal wykrywa pętli i przystanków:Nawiasem mówiąc, jeśli chcesz zastąpić wartość domyślną,
MAXSYMLINKS
któ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
symlinks
narzędzie może być również użyte do usunięcia obraźliwych linków.Przykład
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 symlink
podręcznika pokazuje definicję funkcji o nazwiesymlink()
. Opis wygląda następująco:Jeden z błędów mówi, że ta funkcja zwraca:
Przekieruję cię również do strony man,
man path_resolution
która omawia sposób, w jaki Unix określa ścieżki do elementów na dysku. W szczególności ten ustęp.źródło
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:
edycja :
Mam działającą implementację tego w python na https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher .
źródło
W Pythonie jest dostępna funkcja o nazwie networkx.simple_cycles (). Ale tak, musiałby odczytać każdy plik w systemie.
źródło
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.
źródło
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.
źródło