Existe algum algoritmo para decidir se um symlink faz um loop?

Question

Os sistemas Unix geralmente só cometem erros se forem confrontados com um caminho que contenha um loop de links simbólicos ou apenas 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 este é 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 sobre um determinado caminho, se ele resolve um arquivo / diretório definido ou se não resolve nada. 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

Esta árvore de diretórios tem claramente um ciclo, mas o caminho a/b/b/b/b/b ainda resolve bem para /a .

    

Answer 1

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

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

Enquanto pensava sobre este problema anteriormente, eu estava usando um algoritmo que percorria elementos de um caminho a partir da raiz, e quando ele encontrou um symlink, ele substituiu o elemento path pelo conteúdo do symlink e continuou a travessia. Como essa abordagem não lembra qual link simbólico está resolvendo no momento, ela não pode detectar quando está em um loop não-resolvedor.

Se o algoritmo acompanhar qual link simbólico está resolvendo atualmente (ou quais links simbólicos no caso de links recursivos), ele pode detectar se está tentando resolver um link novamente de forma recursiva, 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 em Python no link .

    

Answer 2

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 estava lidando com um arquivo. Eu não acredito que isso seja possível.

O único método que posso conceber é fazer uma descoberta onde você especificamente começa a procurar por uma ramificação específica na árvore de diretórios.

Exemplo

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

5 directories, 1 file

O comando find detectará este loop, mas não lhe dirá 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 sendo exibida pelo find . Você pode, no entanto, descartar essa opção ( -mindepth ) se não se importar com a árvore de diretórios exibida. O comando find 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

Por acaso, se você quiser substituir o padrão MAXSYMLINKS , que aparentemente é 40 no Linux (versões 3.x mais recentes do kernel), você pode ver este U & Q e & A intitulado: Como você aumenta MAXSYMLINKS .

Usando o comando symlinks

Existe uma ferramenta que os mantenedores de sites FTP podem usar, chamada symlinks , que ajudará a expor problemas com árvores longas ou pendentes de ferramentas causadas por links simbólicos.

Em certos casos, a ferramenta symlinks também pode ser usada para excluir links ofensivos.

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 inteiramente o papel delas ou como realmente usá-las. Então, eu posso apenas indicá-los para você.

A página man, man symlink mostra a definição da função para uma função chamada symlink() . A descrição é assim:

symlink() creates a symbolic link named newpath which contains the string oldpath.

Um dos estados de erro que esta função retorna:

ELOOP Too many symbolic links were encountered in resolving newpath.

Também vou direcioná-lo para a página do manual, man path_resolution , que 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").

    

Answer 3

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

    

Answer 4

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

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. A leitura de cada link simbólico é atômica, mas seguir um link simbólico não é. Se alguns links simbólicos continuarem mudando enquanto o kernel está fazendo a travessia, ele pode acabar em um caminho infinito envolvendo links distintos.

    

Answer 5

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

Existem vários algoritmos para encontrar "ciclos" em listas vinculadas ( Algoritmo de detecção de ciclo do Floyd ) ou em gráficos direcionados . Não está claro para mim qual deles você teria que fazer para detectar um "loop" ou "ciclo" real em um determinado caminho. Em qualquer caso, os algoritmos podem levar muito tempo para serem executados, então acredito que apenas contar o número de links simbólicos seguidos fará com que você alcance 90% do seu objetivo.