Existe um algoritmo para decidir se um link simbólico faz um loop?

Os sistemas Unix geralmente apenas cometem erros de erro se forem confrontados com um caminho que contém um loop de link simbólico ou muitos links simbólicos, porque eles têm um limite para o número de links simbólicos que eles percorrerão em uma pesquisa de caminho. Mas existe uma maneira de realmente decidir se um determinado caminho resolve algo ou contém um loop, mesmo que contenha mais links do que um unix está disposto a seguir? Ou isso é um problema formalmente indecidível? E se puder ser decidido, pode ser decidido em uma quantidade razoável de tempo / memória (por exemplo, sem ter que visitar todos os arquivos em um sistema de arquivos)?

Alguns exemplos:

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

Editar :

Para esclarecer, não estou perguntando sobre encontrar loops no sistema de arquivos, estou perguntando sobre um algoritmo de decisão que decide um determinado caminho se ele resolve para um arquivo / diretório definido ou se não resolve. Por exemplo, no sistema a seguir, há um loop, mas o caminho fornecido ainda resolve bem:

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

Essa árvore de diretórios claramente possui um ciclo, mas o caminho a/b/b/b/b/bainda resolve bem /a.

Eu não entendo completamente o que você está perguntando. Se eu não soubesse melhor, acho que você estava perguntando se havia uma maneira de detectar isso enquanto lidava com um arquivo. Eu não acredito que isso seja possível.

O único método que posso conceber é encontrar onde você começa especificamente a procurar por um ramo específico na árvore de diretórios.

Exemplo

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

5 directories, 1 file

O findcomando detectará esse loop, mas não informará muito sobre isso.

$ 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

Eu escolhi arbitrariamente 15 níveis para bloquear qualquer saída exibida pelo find. No entanto, você pode soltar essa opção ( -mindepth) se não se importar com a árvore de diretórios que está sendo exibida. O findcomando ainda detecta o loop e para:

$ 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

Aliás, se você deseja substituir o padrão MAXSYMLINKSque aparentemente é 40 no Linux (versões 3.x mais recentes do kernel), você pode ver estas perguntas e respostas sobre U&L intituladas: Como você aumenta o MAXSYMLINKS .

Usando o comando symlinks

Existe uma ferramenta que os mantenedores do site FTP podem usar chamada symlinksque ajudará a expor problemas com as árvores longas ou pendentes da ferramenta causadas por links simbólicos.

Em certos casos, a symlinksferramenta também pode ser usada para excluir links incorretos.

Exemplo

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

A biblioteca glibc

A biblioteca glibc procura oferecer algumas funções C em torno disso, mas eu não conheço completamente o papel delas ou como usá-las. Então, eu apenas posso apontá-las para você.

A página do manual man symlinkmostra a definição de função para uma função chamada symlink(). A descrição é assim:

symlink () cria um link simbólico chamado newpath que contém a cadeia oldpath.

Um dos erros afirma que essa função retorna:

ELOOP Muitos links simbólicos foram encontrados na resolução de novo caminho.

Também direcionarei você para a página de manual, man path_resolutionque discute como o Unix determina os caminhos para os itens no disco. Especificamente este parágrafo.

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").

OK, depois de pensar um pouco mais, acho que tenho uma solução clara.

O insight crítico é que, se todo link que faz parte de um caminho se resolver para algo, o caminho inteiro será resolvido. Ou o contrário, se um caminho não for resolvido, deve haver um link simbólico específico que exija o deslocamento que não seja resolvido.

Enquanto pensava nesse problema anteriormente, estava usando um algoritmo que atravessava elementos de um caminho a partir da raiz e, quando encontrou um link simbólico, substituiu esse elemento do caminho pelo conteúdo do link simbólico e continuou a percorrer. Como essa abordagem não se lembra de qual link simbólico está sendo resolvido no momento, ela não pode detectar quando está em um loop sem solução.

Se o algoritmo acompanhar qual link simbólico está sendo resolvido no momento (ou quais links simbólicos no caso de links recursivos), ele poderá detectar se está tentando resolver um link novamente recursivamente, o que ainda está ocupado resolvendo.

Algoritmo:

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

editar :

Eu tenho uma implementação funcional disso em python em https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher .

O Python possui uma função chamada networkx.simple_cycles () que pode ser usada para isso. Mas sim, seria necessário ler todos os arquivos no sistema.

>>> 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']]

Em um sistema inativo (ou seja, quando nenhuma mudança está ocorrendo), sim, existe um algoritmo. Há um número finito de links simbólicos, portanto eles constituem um gráfico finito e a detecção de ciclos é um processo finitário.

Em um sistema ativo, não há como detectar ciclos, porque os links simbólicos podem mudar enquanto o detector de ciclo está em execução. Ler cada link simbólico é atômico, mas seguir um link simbólico não é. Se alguns links simbólicos continuarem mudando enquanto o kernel estiver fazendo a travessia, ele poderá terminar em um caminho infinito envolvendo links distintos.

Até onde eu posso ver, olhando para as fontes atuais do kernel Linux, tudo o que o kernel faz é manter uma contagem de quantos links são seguidos e errar se for maior que algum número. Veja a linha 1330 em namei.c para o comentário e a nested_symlink()função. A macro ELOOP (o número do erro retornado de umread(2) chamada do sistema para essa situação) aparece em vários locais nesse arquivo; portanto, pode não ser tão simples quanto a contagem dos links seguidos, mas isso é certo.

Existem vários algoritmos para encontrar "ciclos" em listas vinculadas ( algoritmo de detecção de ciclo de Floyd ) ou em gráficos direcionados . Não está claro para mim qual você precisaria fazer para detectar um "loop" ou "ciclo" real em um caminho específico. De qualquer forma, os algoritmos podem levar muito tempo para serem executados, por isso acho que apenas contar o número de links simbólicos seguidos leva você a 90% do seu objetivo.