как найти петлю в файловой системе?

Question

как найти петлю в файловой системе в Linux? я индексирую все файлы для быстрого поиска (O (1)) ... я использую язык программирования c для реализации с помощью библиотечных функций в dir.h .... я могу сканировать всю файловую систему, но она идет в цикл, если в файловой системе есть цикл (пример монтирования цикла) ... как найти цикл в файловой системе ... я видел отчет команды updatedb, когда в файловой системе есть цикл ... я не понимаю логику ... кто-нибудь может помочь найти решение для этого?

Answer 1

Общий способ предотвратить повторное сканирование узлов на графике - пометить узлы при их прохождении, а затем игнорировать отмеченные узлы. Это не очень практично, если вы не хотите изменять график, который вы сканируете, поэтому вам нужен способ внешней маркировки узлов. Самый простой способ сделать это в Linux - это сохранить устройство / inode для каждого каталога, который вы посещаете. Затем, когда вы просматриваете каталог, сначала убедитесь, что вы еще не видели ни одного каталога с тем же устройством / индексом. Это не только обрабатывает циклы, но также и деревья, которые сливаются друг с другом.

Чтобы узнать номер устройства / индекса, взгляните на функции stat / fstat и члены st_dev и st_ino структуры stat.

Для хранения данных вы, вероятно, захотите взглянуть на хеш-таблицу или двоичное дерево.

Answer 2

Btw. Вам не нужно искать цикл в файловой системе.

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

Answer 3

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

Например, если вы загружаете какой-то дистрибутив (скажем, Debian) на устройство цикла или даже в каталог и делаете это на машине Debian, вы теперь дублировали много вещей.

Например, предположим, что вы работаете с Debian Lenny, и загрузите минимальную копию в / lenny.

/ lenny / usr / * будет таким же, как / usr / *. Не существует «дешевого» способа избежать этого.

Поскольку вы уже вызываете stat () для каждого узла (я предполагаю, что вы используете ftw () / ftw64 (), вы также можете:

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

Это не опасно для ускорения вашего сканирования, но это значительно сократит время, необходимое для поиска.

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

Однако «просто» проверка на наличие дублирующих монтирований не будет лекарством, плюс я уверен, что ваша программа захочет вернуть расположение всех файлов с именем «foo», даже если упомянуть четыре идентичные копии .

Answer 4

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

 // here's a stack of nodes
node stack[1000];

walk(node, level){
    if (node in stack[0..level-1]) then there is a cycle
    else
        stack[level] = node
        for each subnode x of node
            walk(x, level+1)
}

Answer 5

Возможно, я немного потускнел, но это не два способа создать цикл:

• путем создания символической ссылки
• , монтируя что-то дважды

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

Answer 6

Я нашел здесь этот интересный комментарий о поиске циклов в DAG :

Стейнар Х. Гандерсон писал:

В четверг, 26 февраля 2004 г. 00:28:32 +0100, Орлондов написал:

... также воспроизведено в Cormen-Leiserson-Rivest, IIC. Который простой найти.

Да, у меня действительно есть Кормен и др., Но мне никогда не удавалось посмотреть «сильно связанные компоненты», когда я хотел обнаружения цикла. Спасибо я буду Посмотри на это. : -)

Чтобы найти цикл в ориентированном графе (вам не важно, какой цикл), как долго поскольку существует, вам не нужно идти за борт с SCC. Обычная старая глубина Первый поиск DFS (в той же главе CLRS) достаточно.

Итак, грубо говоря, пока вы просматриваете дерево каталогов, создайте группу обеспечения доступности баз данных, которая представляет структуру дерева с данными в узле, ссылающимися на индекс файла. Затем вы просто проверяете, не посещаете ли вы узел более одного раза.

Answer 7

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