Эффективный способ обхода дерева каталогов, содержащего циклы ссылок

Question

Есть ли более эффективный способ обхода дерева каталогов, которое содержит циклы ссылок, чем отслеживание, какие файлы уже были посещены?

Например, рассмотрите прогулку по каталогу, содержащему эти файлы:

symlink "parent" -> ".."
symlink "uh_oh" -> "/"
regular file "reg"
symlink "reg2" -> "reg"

Answer 1

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

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

Теоретически, вы можете получить "идентификатор файловой системы" из stafvfs интерфейс, но на практике это не совсем переносимо. квотирование man statfs из дистрибутива Linux:

Никто не знает что f_fsid должен содержать...

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

Это последнее ограничение - это f_fsid представляется как 0 для непривилегированных пользователей - не нарушает упомянутый выше стандарт Posix, потому что этот стандарт включает очень общий отказ от ответственности: "Не указано, все ли члены statvfs структура имеет значимые значения во всех файловых системах."

Answer 2

Алгоритм обхода дерева гарантирует, что вы будете посещать каждый файл в каталоге, поэтому вместо отслеживания отдельных файлов вы можете вести список "корней" поиска:

• Добавьте начальный каталог в список корней
• Пройдите по дереву каталогов для каждого корня поиска
• Для каждой найденной символической ссылки проверьте, содержится ли она уже в корне поиска. Если это не так, добавьте его в качестве нового корня поиска.

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