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

16

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.

JanKanis
fonte
O que a ferramenta de linha de comando readlink ...diz sobre as situações acima?
slm
11
Você está perguntando se podemos dizer apenas a partir do nome do caminho se existem loops? Ou podemos fazer isso em um sistema operacional real, usando as ferramentas padrão e verificando o que os vários componentes do nome do caminho resolvem?
Mike Diehn
@MikeDiehn Obviamente, não se pode dizer apenas de um caminho se ele resolver sem executar operações do sistema de arquivos. Mas também com um ambiente de sistema operacional, não é fácil distinguir um caminho que requer apenas atravessar muitos links simbólicos para resolver de um que não resolve de maneira alguma.
JanKanis

Respostas:

10

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").
slm
fonte
Se possível, eu gostaria de uma maneira de detectar um loop de link simbólico quando receber um único caminho e resolver os links simbólicos manualmente em um programa, em vez de permitir que o SO faça isso. Mas estou me perguntando se isso é possível. A solução find parece interessante, mas você tem alguma idéia / como / find detecta loops de link simbólico e se o método usado é completo (ou seja, detecta todos os loops possíveis e não identifica erroneamente nenhum caminho sem loop)?
JanKanis
@ Somejan - veja minhas atualizações para o A. Deixe-me saber se isso faz sentido.
slm
5

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 .

JanKanis
fonte
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']]
Back2Basics
fonte
Também pensei em usar algum tipo de algoritmo de gráfico, mas não tenho certeza se uma árvore de diretórios com links simbólicos pode ser adequadamente representada em um gráfico simples. Em uma árvore de diretórios abc em que c é um link simbólico para .., existe um loop, mas caminhos como a / b / c / b / c / b ainda são resolvidos, pois eles seguem o loop apenas um número finito de vezes e não continue dando laços.
JanKanis
@Somejan: um espaço para nome do sistema de arquivos é um gráfico e um nome de arquivo é um caminho escolhido sobre esse gráfico.
Ninjalj 7/11
@ ninjalj: Sim, um sistema de arquivos é um gráfico, mas não acho que um nome de arquivo seja simplesmente um caminho sobre esse gráfico. O nome do arquivo pode ser visto como um conjunto de instruções sobre como percorrer o gráfico. Mesmo se o gráfico contiver ciclos que não significam que um nome de arquivo que segue esse ciclo necessariamente não seja resolvido, veja meu exemplo no meu comentário anterior.
JanKanis
3

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.

Gilles 'SO- parar de ser mau'
fonte
Existem maneiras de atenuar essas alterações para aumentar a precisão de 98 a 99%. Você poderia fazê-lo prestar atenção aos carimbos de data e hora nos arquivos e eu não sugeriria realmente seguir os links. Como é recursivo a partir da raiz, ele encontrará o diretório real posteriormente.
Back2Basics
11
@ Back2Basics Estes números são completamente sem sentido. Esta é uma interface do kernel. Se não funcionar o tempo todo, não funciona, ponto final.
Gilles 'SO- stop be evil'
2

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.

Bruce Ediger
fonte
Para usos práticos, basta contar o número de links percorridos, especialmente porque é isso que o kernel faz; portanto, mesmo se você encontrar um caminho de resolução correta com muitos links simbólicos, você ainda não poderá usá-lo para algo prático ( ou seja, que não envolvem ligações simbólicas resolver manualmente)
JanKanis