Есть ли алгоритм, чтобы решить, если петли символической ссылки?

16

Системы Unix обычно просто выдают ошибку, если сталкиваются с путем, который содержит цикл символьных ссылок или просто слишком много символических ссылок, потому что у них есть ограничение на количество символических ссылок, которые они будут проходить в одном поиске пути. Но есть ли способ действительно решить, разрешает ли данный путь что-то или содержит цикл, даже если он содержит больше ссылок, чем желает следовать unix? Или это формально неразрешимая проблема? И если это может быть решено, может ли это быть решено за разумное количество времени / памяти (например, без необходимости посещать все файлы в файловой системе)?

Несколько примеров:

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

Редактировать :

Чтобы уточнить, я не спрашиваю о поиске петель в файловой системе, я спрашиваю об алгоритме принятия решения, который решает, задан ли данный путь, разрешает ли он определенный файл / каталог или не разрешает вообще. Например, в следующей системе есть цикл, но указанный путь все еще разрешается нормально:

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

Это дерево каталогов явно имеет цикл, но путь a/b/b/b/b/bвсе равно разрешается /a.

JanKanis
источник
Что говорит инструмент командной строки readlink ...о вышеупомянутых ситуациях?
slm
1
Вы спрашиваете, можем ли мы просто сказать по пути, есть ли петли? Или мы можем сделать это в реальной операционной системе, используя стандартные инструменты и проверяя, к чему обращаются различные компоненты пути?
Майк Дин
@MikeDiehn Очевидно, что по пути невозможно определить, разрешается ли он без выполнения операций с файловой системой. Но также и в среде ОС нелегко отличить путь, который просто требует обхода множества символических ссылок, чтобы разрешить тот, который вообще не разрешается.
JanKanis

Ответы:

10

Я не до конца понимаю, что вы спрашиваете. Если бы я не знал ничего лучше, я думаю, что вы спрашивали, есть ли способ обнаружить это в разгар работы с файлом. Я не верю, что это возможно.

Единственный способ, который я могу придумать, - это найти, где вы специально начинаете просматривать определенную ветку в дереве каталогов.

пример

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

5 directories, 1 file

Команда findобнаружит этот цикл, но не очень много расскажет об этом.

$ 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

Я произвольно выбрал 15 уровней, чтобы заблокировать любой вывод, отображаемый find. Однако вы можете удалить этот переключатель ( -mindepth), если вас не волнует отображение дерева каталогов. Команда findвсе еще обнаруживает цикл и останавливается:

$ 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

Кстати, если вы хотите переопределить значение по умолчанию, MAXSYMLINKSкоторое, по-видимому, составляет 40 в Linux (более новые версии ядра 3.x), вы можете увидеть этот вопрос и ответ по U & L под названием: Как вы увеличиваете MAXSYMLINKS .

Использование команды symlinks

Существует инструмент, который могут использовать сопровождающие FTP-сайта, symlinksкоторый поможет выявить проблемы с длинными инструментами или висячими деревьями, которые были вызваны символическими ссылками.

В некоторых случаях этот symlinksинструмент можно использовать и для удаления оскорбительных ссылок.

пример

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

Библиотека glibc

Библиотека glibc, похоже, предлагает некоторые функции C для этого, но я не совсем знаю их роль или как на самом деле их использовать. Так что я могу только указать на них.

Страница man, man symlinkпоказывает определение функции для вызываемой функции symlink(). Описание выглядит так:

symlink () создает символическую ссылку с именем newpath, которая содержит строку oldpath.

Одна из ошибок гласит, что эта функция возвращает:

ELOOP Слишком много символических ссылок было найдено при разрешении newpath.

Я также направлю вас на страницу руководства, man path_resolutionгде рассказывается, как Unix определяет пути к элементам на диске. Конкретно этот абзац.

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
источник
Если возможно, я бы хотел, чтобы был обнаружен цикл символьных ссылок при задании единственного пути, и разрешение символических ссылок вручную в программе вместо того, чтобы позволить ОС делать это. Но мне интересно, возможно ли это вообще. Решение поиска выглядит интересно, но есть ли у вас какая-либо идея / как / find обнаруживает циклы символьных ссылок, и если метод, который он использует, завершен (то есть обнаруживает все возможные циклы и не ошибочно идентифицирует какие-либо нециклические пути)?
JanKanis
@Somejan - посмотрите мои обновления для А. Дайте мне знать, если это имеет смысл.
SLM
5

Хорошо, после еще нескольких мыслей, я думаю, у меня есть четкое решение.

Критическое понимание заключается в том, что если каждая ссылка, являющаяся частью пути, разрешается к чему-либо, то разрешается весь путь. Или наоборот, если путь не разрешается, то должна быть определенная символическая ссылка, которая требует обхода, который не разрешается.

Размышляя об этой проблеме ранее, я использовал алгоритм, который проходил по элементам пути, начиная с корня, и когда он встречал символическую ссылку, он заменял этот элемент пути содержимым символической ссылки, а затем продолжал обход. Поскольку этот подход не запоминает, какую символическую ссылку он разрешает в настоящее время, он не может определить, когда он находится в неразрешимом цикле.

Если алгоритм отслеживает, какую символическую ссылку он в настоящее время разрешает (или какие символические ссылки в случае рекурсивных ссылок), он может определить, пытается ли он рекурсивно разрешить ссылку снова, и он все еще занят разрешением.

Алгоритм:

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

редактировать :

У меня есть рабочая реализация этого в python по адресу https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher .

JanKanis
источник
3

В Python есть функция networkx.simple_cycles (), которую можно использовать для этого. Но да, это должно было бы прочитать каждый файл в системе.

>>> 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
источник
Я также думал об использовании какого-либо алгоритма графа, но я не уверен, что дерево каталогов с символическими ссылками может быть адекватно представлено в простом графе. В дереве каталогов abc, где c является символической ссылкой на .., есть цикл, но пути типа a / b / c / b / c / b все еще разрешаются, так как они следуют за циклом конечное число раз и не делают продолжайте цикл
JanKanis
@Somejan: пространство имен файловой системы - это граф, а имя файла - это путь, выбранный над этим графом.
ниндзя
@ninjalj: Да, файловая система - это граф, но я не думаю, что имя файла - это просто путь над этим графом. Имя файла можно рассматривать как набор инструкций о том, как пройти по графику. Даже если график содержит циклы, это не означает, что имя файла, которое следует за этим циклом, обязательно не разрешается, см. Мой пример в моем предыдущем комментарии.
JanKanis
3

В спокойной системе (то есть, когда никаких изменений не происходит), да, есть алгоритм. Существует конечное число символических связей, поэтому они составляют конечный граф, а обнаружение циклов - это конечный процесс.

В действующей системе невозможно обнаружить циклы, потому что символические ссылки могут изменяться во время работы детектора циклов. Чтение каждой символической ссылки является атомарным, но после символической ссылки нет. Если некоторые символические ссылки продолжают изменяться, пока ядро ​​выполняет обход, это может привести к бесконечному пути, включающему различные ссылки.

Жиль "ТАК - перестань быть злым"
источник
Существуют способы смягчения этих изменений, чтобы повысить точность до 98-99%. Вы могли бы обратить внимание на временные метки на файлах, и я бы не советовал на самом деле переходить по ссылкам. Поскольку он является рекурсивным из корня, он найдет фактический каталог позже.
Back2Basics
1
@ Back2Basics Эти цифры совершенно бессмысленны. Это интерфейс ядра. Если это не работает все время, это не работает, точка.
Жиль "ТАК - перестань быть злым"
2

Насколько я могу судить по текущим источникам ядра Linux, все ядро ​​ведет подсчет количества ссылок, по которым оно идет, и выдает ошибки, если оно больше некоторого числа. Смотрите строку 1330 в namei.c для комментария и nested_symlink()функции. Макрос ELOOP (номер ошибки, возвращаемый read(2)системным вызовом для этой ситуации) появляется в ряде мест в этом файле, поэтому он может быть не таким простым, как подсчет ссылок, за которыми следуют, но это точно, как он выглядит.

Существует ряд алгоритмов для нахождения «циклов» в связанных списках (алгоритм обнаружения циклов Флойда ) или в ориентированных графах . Мне не ясно, что вам нужно сделать, чтобы обнаружить фактический «цикл» или «цикл» на определенном пути. В любом случае, выполнение алгоритмов может занять много времени, поэтому я предполагаю, что просто подсчет количества символических ссылок приведет вас к 90% пути к вашей цели.

Брюс Эдигер
источник
Для практического использования достаточно просто подсчитать количество пройденных ссылок, тем более что это то, что делает ядро, поэтому даже если вы встретите правильно разрешенный путь, который содержит слишком много символических ссылок, вы все равно не сможете использовать этот путь для чего-либо практического ( то есть это не требует ручного разрешения символических ссылок)
JanKanis