심볼릭 링크가 순환인지 확인하는 알고리즘이 있습니까?

나는 당신이 무엇을 요구하는지 완전히 이해하지 못합니다. 제가 잘 몰랐다면, 파일을 처리하면서 이를 감지할 수 있는 방법이 없냐고 묻는 것 같은데요. 나는 이것이 가능하다고 믿지 않습니다.

내가 생각할 수 있는 유일한 방법은 디렉토리 트리에서 특정 분기를 찾기 시작하는 곳을 찾는 것입니다.

예

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

5 directories, 1 file

이 find명령은 이 루프를 감지하지만 실제로 모든 정보를 알려주지는 않습니다.

$ 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

을 차단하기 위해 임의로 15레벨을 선택했습니다 find. 그러나 -mindepth표시되는 디렉토리 트리에 관심이 없다면 스위치( )를 제거할 수 있습니다. 이 find명령은 여전히 ​​루프를 감지하고 중지합니다.

$ 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

MAXSYMLINKS그런데 Linux(최신 3.x 버전 커널)에서 기본값인 40을 재정의하려면 다음 U&L Q&A를 참조하세요.MAXSYMLINKS를 ​​늘리는 방법.

심볼릭 링크 명령 사용

symlinksFTP 사이트 관리자는 기호 링크로 인해 지나치게 길거나 매달려 있는 트리 문제를 노출하는 데 도움이 되는 도구를 사용할 수 있습니다 .

어떤 경우에는 이 symlinks도구를 사용하여 문제가 되는 링크를 제거할 수도 있습니다.

예

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

glibc 라이브러리

glibc 라이브러리는 이와 관련된 일부 C 함수를 제공하는 것 같지만, 이들이 수행하는 작업이나 실제로 사용하는 방법을 완전히 이해하지 못합니다. 그래서 나는 단지 그것들을 여러분에게 지적할 수 있을 뿐입니다.

매뉴얼 페이지에는 man symlink이름이 지정된 함수에 대한 함수 정의가 표시됩니다 symlink(). 설명은 이렇습니다.

Symlink()는 oldpath 문자열을 포함하는 newpath라는 이름의 심볼릭 링크를 만듭니다.

오류 중 하나에는 함수가 다음을 반환한다고 명시되어 있습니다.

ELOOP는 newpath를 구문 분석하는 동안 너무 많은 기호 링크를 발견했습니다.

man path_resolution또한 Unix가 디스크 항목의 경로를 결정하는 방법을 설명하는 매뉴얼 페이지로 안내하겠습니다 . 특히 이 섹션.

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

글쎄요, 좀 생각해 본 결과 명확한 해결책이 있다고 생각합니다.

중요한 통찰력은 경로의 모든 링크가 무언가로 해결되면 전체 경로가 해결된다는 것입니다. 또는 반대로 경로를 확인할 수 없는 경우 통과해야 하지만 확인할 수 없는 특정 심볼릭 링크가 있어야 합니다.

이전에 이 문제에 대해 생각할 때 루트부터 시작하여 경로 요소를 순회하는 알고리즘을 사용했는데, 심볼릭 링크를 만나면 해당 경로 요소를 심볼릭 링크의 내용으로 대체한 다음 순회를 계속했습니다. 이 메서드는 현재 해결 중인 심볼릭 링크를 기억하지 못하기 때문에 해결되지 않는 루프에 있는 경우를 감지할 수 없습니다.

알고리즘이 현재 확인 중인 심볼릭 링크(또는 재귀 링크의 경우 심볼릭 링크)를 추적하는 경우 여전히 확인 중인 링크를 다시 재귀적으로 확인하려고 시도하는지 여부를 감지할 수 있습니다.

연산:

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

편집하다:

Python으로 구현된 작업이 있습니다.https://bitbucket.org/JanKanis/python-inotify/src/853ed903e870cbfa283e6ce7a5e41aeffe16d4e7/inotify/pathresolver.py?at=pathwatcher.

편집 2: Bitbucket이 Mercurial 저장소 호스팅을 중단했습니다. 전체 파일은 다음과 같습니다.

# pathresolver.py - This module contains an iterator that iterates over all
# elements of a path including any symlinks. 

# Copyright 2012-2013 Jan Kanis

# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Lesser General Public
# License as published by the Free Software Foundation; either
# version 2.1 of the License, or (at your option) any later version.


"""
This module contains a few functions that help traverse paths with
symlinks.

`resolve_symlinks` is a generator that yields pairs of paths, with one
yield for each path element that is traversed to reach the final
target of a path. This includes path elements and paths from symlinks.

`resolve_path` is a wrapper around `resolve_symlinks` that takes a
single path as an argument and sets up the other arguments to
`resolve_symlinks`.

`get_symlinkmax` is a function that determines the maximum number of
symlinks the system will traverse in a path.

Note: this module forms part of python-inotify, but is considered an
internal module. As such there are no stability guarantees regarding
the api's of these functions.
"""


__author__ = "Jan Kanis"


import sys, os, errno
import tempfile, shutil
from pathlib import PosixPath


_curdir = PosixPath('.')
_root = PosixPath('/')
_parentdir = PosixPath('..')


def resolve_path(path):
    '''Resolve the symlinks in path, yielding all filesystem locations that are traversed.

    The yielded value is a tuple, of which the first element is a symlink-free
    path, and the second element is a path relative to the first element that
    has not yet been traversed. This second element may contain more symlinks.
    
    The resolution implementation will follow an unbounded number of symlinks
    but will still detect symlink loops if they prevent a path from resolving.

    path can be given as a string or as a pathlib object. The yielded values
    are pathlib.PosixPath objects.

    '''
    linkcache = {}
    linkcounter = [0]
    for p in resolve_symlink(_curdir, PosixPath(path), set(),
                                  linkcache, linkcounter):
        yield p


def resolve_symlink(location, link_contents, active_links, known_links, linkcounter):
    '''Recursively resolve a symlink (or another path) to the file or
    directory it ultimately points to. This function handles an
    unlimited number of symlinks, and correctly detects symlink
    loops. All path parameters should be given as pathlib.PosixPath
    instances.

    location: The directory in which the currently to be resolved link resides.

    link_contents: The path stored in the symlink as returned by readlink().

    active_links: a set of symlinks that is currently being resolved.

    linkcache: a dictionary of link location -> resolved target paths. This
    cache prevents this function from having to resolve the same symlink
    twice. (Note that having to traverse the same symlink multiple times
    does not necessarily mean that the path does not resolve to anything.)

    linkcounter: A list containing a single number. (We use a list so that the
    value can be passed by reference.) This number is updated to indicate the
    total number of symlinks that has been traversed.

    '''

    while True:
        if link_contents.is_absolute():
            location = _root
            link_contents = link_contents.relative()

        yield location, link_contents
        if link_contents == _curdir:
            return

        if link_contents.parts[0] == '..':
            # We need to choose here if we allow traversing of a path above
            # the root or above the current directory. Going above CWD
            # should be allowed as long as we don't go above / by doing
            # so. The OS allows going to /.. (which just ends up at /
            # again), so for consistency with that we also allow it,
            # although a path that requires us to do this is probably a bug
            # somewhere.
            if all(p in ('/', '..') for p in location.parts):
                location = location['..']
            else:
                location = location.parent()
            # Strip the first part of link_contents off
            link_contents = link_contents.parts[1:]
            continue

        try:
            nextpath = location[link_contents.parts[0]]
            newlink = PosixPath(os.readlink(str(nextpath)))
        except OSError as e:
            if e.errno == errno.EINVAL:
                # The entry is not a symbolic link, assume it is a normal file
                # or directory. If it is a file and we need it to be a
                # directory that will be detected the next time through the
                # loop in the os.errno.ENOTDIR check. Checking it here would be
                # possible, but keeping the number of system calls at one per
                # loop makes reasoning about race conditions easier.
                location = nextpath
                link_contents = link_contents.parts[1:]
                continue
            if e.errno == errno.ENOENT:
                # The entry does not exist
                raise FileNotFoundError(nextpath)
            if e.errno == errno.ENOTDIR:
                # At this point we know the path is not valid, but we can not
                # determine with certainty what is wrong. If there were no
                # concurrent modifications we can safely make an is_dir()
                # call. If concurrent modifications did happen the is_dir()
                # check may succeed erroneously but we can't detect all
                # concurrent modifications anyway. If the check fails
                # (erroneously or not) that indicates a concurrent modification
                # so we fall through.
                if not location.is_dir():
                    raise NotADirectoryError(location)
                # We should not be able to get here, unless there is a bug
                # or some relevant part of the file system was changed
                # concurrently while we were resolving this link.
                raise ConcurrentFilesystemModificationError(nextpath)
            if e.errno == errno.ELOOP:
                # Can only happen if a path component was changed concurrently
                raise ConcurrentFilesystemModificationError(nextpath)
            # For other OSErrors (such as in case of EACCESS) we propagate to
            # the caller. 
            raise

        # It is a symlink!
        if nextpath in active_links:
            raise SymlinkLoopError(nextpath)

        link_contents = link_contents.parts[1:]
        # We have not yet attempted traversing this symlink during the
        # current call or any of its parents.
        if nextpath in known_links:
            # known_links stores fully resolved paths, so we don't need to
            # traverse the cached path and can just continue our traversal from
            # there.
            location = known_links[nextpath]
            continue
        
        # An unknown link, resolve it recursively
        linkcounter[0] += 1
        # Don't yield the very last result of this recursive call immediately,
        # we still want to process that further. 
        lastloc, lastlink = None, None
        for loc, link in resolve_symlink(location, newlink,
                          active_links.union((nextpath,)), known_links, linkcounter):
            if lastloc:
                yield lastloc, lastlink[link_contents]
            lastloc, lastlink = loc, link
        # The last yielded location is the final resolution of the symlink. The
        # last yielded link_contents is always '.' so we can ignore that.
        known_links[nextpath] = loc
        location = loc
        continue


_symlinkmax = None
def get_symlinkmax():
  '''Returns the maximum number of symlinks that this system will traverse in
  resolving a file path.

  '''
  global _symlinkmax
  if _symlinkmax is not None:
    return _symlinkmax

  try:
    tempdir = tempfile.mkdtemp(prefix='inotify-symlinkmax-tmpdir-')
    open(tempdir+'/testfile', 'w').close()

    target = 'testfile'
    for i in range(1, 60):
      name = 'l'+str(i)
      os.symlink(target, tempdir+'/'+name)
      target = name

      try:
        open(tempdir+'/'+name).close()
      except IOError as e:
        if e.errno == errno.ELOOP:
          _symlinkmax = i - 1
          break
        raise
    
  finally:
    if tempdir:
      shutil.rmtree(tempdir)
  return _symlinkmax



class InvalidPathError (OSError):
    def __init__(self, msg, path, errno=None, *args):
        self.filename = path
        self.errno = errno
        if errno:
            self.strerror = os.strerror(errno)
        OSError.__init__(self, msg, *args)

class SymlinkLoopError (InvalidPathError):
    def __init__(self, path, *args):
        msg = "Path not valid: The symlink at '{}' forms a symlink loop".format(path)
        InvalidPathError.__init__(self, msg, path, errno=errno.ELOOP, *args)

class ConcurrentFilesystemModificationError (InvalidPathError):
    def __init__(self, path, *args):
        msg = "Path not valid: A concurrent change was detected while traversing '{}'".format(path)
        InvalidPathError.__init__(self, msg, path, errno=None, *args)


# To be Python 2 and 3 compatible and also inherit from the right exception
# types in python 3, we need some boilerplate.

fnf_msg = "Path not valid: '{}' does not exist"
nad_msg = "Path not valid: '{}' is not a directory"

if sys.version_info >= (3, 3):
    class FileNotFoundError (InvalidPathError, FileNotFoundError):
        def __init__(self, path, *args):
            InvalidPathError.__init__(self, fnf_msg.format(path), path,
                                          errno=ENOENT, *args)

    class NotADirectoryError (InvalidPathError, NotADirectoryError):
        def __init__(self, path, *args):
            InvalidPathError.__init__(self, nad_msg.format(path), path,
                                          errno=errno.ENOTDIR, *args)

else:
    class FileNotFoundError (InvalidPathError):
        def __init__(self, path, *args):
            InvalidPathError.__init__(self, fnf_msg.format(path), path,
                                          errno=errno.ENOENT, *args)

    class NotADirectoryError (InvalidPathError):
        def __init__(self, path, *args):
            InvalidPathError.__init__(self, nad_msg.format(path), path,
                                          errno=errno.ENOTDIR, *args)

정적 시스템(즉, 아무것도 변경되지 않는 경우)에는 그렇습니다. 알고리즘이 있습니다. 심볼릭 링크의 수는 유한하므로 유한한 그래프를 구성하며, 주기를 감지하는 것은 유한한 프로세스입니다.

라이브 시스템에서는 루프 감지기가 실행되는 동안 기호 링크가 변경될 수 있으므로 루프를 감지할 수 없습니다. 각 심볼릭 링크를 읽는 것은 원자성이지만 다음 심볼릭 링크는 그렇지 않습니다. 커널이 순회하는 동안 일부 심볼릭 링크가 계속 변경되면 다른 링크를 포함하는 무한 경로가 될 수 있습니다.

현재 Linux 커널 소스 코드를 살펴보면 알 수 있듯이 커널이 수행하는 작업은 링크 수를 추적하는 것뿐이며 해당 수가 특정 수보다 크면 오류가 발생합니다. 바라보다namei.c의 1330행리뷰 및 nested_symlink()기능을 확인하세요. ELOOP 매크로(이 경우 시스템 호출에서 반환된 오류 번호 read(2))는 이 파일의 여러 위치에 나타나므로 후속 링크를 계산하는 것만큼 간단하지 않을 수 있지만 확실히 그 모양입니다.

연결된 목록에서 "주기"를 찾는 많은 알고리즘이 있습니다(플로이드 사이클 감지 알고리즘) 또는유향 그래프. 특정 경로에서 실제 "루프" 또는 "루프"를 감지하기 위해 어떤 작업을 수행해야 하는지는 확실하지 않습니다. 어쨌든 알고리즘을 실행하는 데 오랜 시간이 걸릴 수 있으므로 따라가는 심볼릭 링크 수를 세는 것만으로도 목표의 90%를 달성할 수 있다고 추측합니다.