Системы 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
.
источник
readlink ...
о вышеупомянутых ситуациях?Ответы:
Я не до конца понимаю, что вы спрашиваете. Если бы я не знал ничего лучше, я думаю, что вы спрашивали, есть ли способ обнаружить это в разгар работы с файлом. Я не верю, что это возможно.
Единственный способ, который я могу придумать, - это найти, где вы специально начинаете просматривать определенную ветку в дереве каталогов.
пример
Команда
find
обнаружит этот цикл, но не очень много расскажет об этом.Я произвольно выбрал 15 уровней, чтобы заблокировать любой вывод, отображаемый
find
. Однако вы можете удалить этот переключатель (-mindepth
), если вас не волнует отображение дерева каталогов. Командаfind
все еще обнаруживает цикл и останавливается:Кстати, если вы хотите переопределить значение по умолчанию,
MAXSYMLINKS
которое, по-видимому, составляет 40 в Linux (более новые версии ядра 3.x), вы можете увидеть этот вопрос и ответ по U & L под названием: Как вы увеличиваете MAXSYMLINKS .Использование команды symlinks
Существует инструмент, который могут использовать сопровождающие FTP-сайта,
symlinks
который поможет выявить проблемы с длинными инструментами или висячими деревьями, которые были вызваны символическими ссылками.В некоторых случаях этот
symlinks
инструмент можно использовать и для удаления оскорбительных ссылок.пример
Библиотека glibc
Библиотека glibc, похоже, предлагает некоторые функции C для этого, но я не совсем знаю их роль или как на самом деле их использовать. Так что я могу только указать на них.
Страница man,
man symlink
показывает определение функции для вызываемой функцииsymlink()
. Описание выглядит так:Одна из ошибок гласит, что эта функция возвращает:
Я также направлю вас на страницу руководства,
man path_resolution
где рассказывается, как Unix определяет пути к элементам на диске. Конкретно этот абзац.источник
Хорошо, после еще нескольких мыслей, я думаю, у меня есть четкое решение.
Критическое понимание заключается в том, что если каждая ссылка, являющаяся частью пути, разрешается к чему-либо, то разрешается весь путь. Или наоборот, если путь не разрешается, то должна быть определенная символическая ссылка, которая требует обхода, который не разрешается.
Размышляя об этой проблеме ранее, я использовал алгоритм, который проходил по элементам пути, начиная с корня, и когда он встречал символическую ссылку, он заменял этот элемент пути содержимым символической ссылки, а затем продолжал обход. Поскольку этот подход не запоминает, какую символическую ссылку он разрешает в настоящее время, он не может определить, когда он находится в неразрешимом цикле.
Если алгоритм отслеживает, какую символическую ссылку он в настоящее время разрешает (или какие символические ссылки в случае рекурсивных ссылок), он может определить, пытается ли он рекурсивно разрешить ссылку снова, и он все еще занят разрешением.
Алгоритм:
редактировать :
У меня есть рабочая реализация этого в python по адресу https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher .
источник
В Python есть функция networkx.simple_cycles (), которую можно использовать для этого. Но да, это должно было бы прочитать каждый файл в системе.
источник
В спокойной системе (то есть, когда никаких изменений не происходит), да, есть алгоритм. Существует конечное число символических связей, поэтому они составляют конечный граф, а обнаружение циклов - это конечный процесс.
В действующей системе невозможно обнаружить циклы, потому что символические ссылки могут изменяться во время работы детектора циклов. Чтение каждой символической ссылки является атомарным, но после символической ссылки нет. Если некоторые символические ссылки продолжают изменяться, пока ядро выполняет обход, это может привести к бесконечному пути, включающему различные ссылки.
источник
Насколько я могу судить по текущим источникам ядра Linux, все ядро ведет подсчет количества ссылок, по которым оно идет, и выдает ошибки, если оно больше некоторого числа. Смотрите строку 1330 в namei.c для комментария и
nested_symlink()
функции. Макрос ELOOP (номер ошибки, возвращаемыйread(2)
системным вызовом для этой ситуации) появляется в ряде мест в этом файле, поэтому он может быть не таким простым, как подсчет ссылок, за которыми следуют, но это точно, как он выглядит.Существует ряд алгоритмов для нахождения «циклов» в связанных списках (алгоритм обнаружения циклов Флойда ) или в ориентированных графах . Мне не ясно, что вам нужно сделать, чтобы обнаружить фактический «цикл» или «цикл» на определенном пути. В любом случае, выполнение алгоритмов может занять много времени, поэтому я предполагаю, что просто подсчет количества символических ссылок приведет вас к 90% пути к вашей цели.
источник