Unixシステムでは、1回のパス検索で通過できるシンボリックリンクの数が制限されているため、シンボリックリンクサイクルを含むパスや、シンボリックリンクが多すぎるパスを検出するとエラーが発生することがよくあります。しかし、UNIXがフォローしようとするよりも多くのリンクが含まれていても、与えられたパスがどのように解決されるか、またはループを含むかどうかを実際に判断する方法はありますか?それとも正式に決定できない質問ですか?決定できれば、合理的な時間/メモリ内で(たとえば、ファイルシステム内のすべてのファイルにアクセスせずに)決定できますか?
いくつかの例:
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
編集する:
明確にするために、ファイルシステム内のループを見つけるのではなく、指定されたパスが決定されたファイル/ディレクトリで解決されるのか、まったく解決されないのかを決定する決定アルゴリズムを尋ねることです。たとえば、次のシステムにはループがありますが、指定されたパスはまだ正常にチェックされます。
/ -- a -- b
where b is a symlink to /a
明らかにディレクトリツリーにループがありますが、パスはa/b/b/b/b/b
まだ/a
。
答え1
私はあなたが何を求めているのか完全に理解していません。私がよく知らなかったら、ファイルを処理しながらこれを検出する方法がないかと尋ねるようです。私はこれが可能だとは思わない。
私が考えることができる唯一の方法は、ディレクトリツリーで特定のブランチを探し始める場所を見つけることです。
はい
$ 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を増やす方法。
シンボリックリンクコマンドの使用
symlinks
FTPサイト管理者は、シンボリックリンクのために長すぎるまたはぶら下がっているツリーの問題を公開するのに役立つツールを使用できます。
場合によっては、この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 という名前のシンボリックリンクを作成します。
エラーの1つは、関数が次を返すことを示しています。
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").
答え2
まあ、ちょっと考えてみた結果、明確な解決策があると思います。
重要な洞察は、パス内のすべてのリンクが何かで解決されると、パス全体が解決されることです。あるいは、逆にパスを確認できない場合は、パスする必要があるが確認できない特定のシンボリックリンクが必要です。
以前は、この問題について考えたときにルートから始まり、パス要素を巡回するアルゴリズムを使用していましたが、シンボリックリンクに会うと、そのパス要素をシンボリックリンクの内容に置き換えてから巡回を続けました。このメソッドは、現在解決中のシンボリックリンクを覚えていないため、未解決のループ内にある場合を検出できません。
アルゴリズムが現在確認しているシンボリックリンク(または再帰リンクの場合はシンボリックリンク)を追跡している場合は、まだ確認されているリンクを再帰的に確認しようとするかどうかを検出できます。
操作:
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)
答え3
静的システム(つまり、何も変更されない場合)にはそうです。アルゴリズムがあります。シンボリックリンクの数は有限なので有限のグラフを構成し、周期を検出することは有限のプロセスです。
ライブシステムでは、ループ検出器の実行中にシンボリックリンクが変更される可能性があるため、ループを検出できません。各シンボリックリンクを読むことは原子性ですが、次のシンボリックリンクはそうではありません。カーネルが巡回している間にいくつかのシンボリックリンクが変更され続けると、他のリンクを含む無限パスになる可能性があります。
答え4
現在のLinuxカーネルのソースコードを見てみると、カーネルが何をしているのかはリンク数を追跡するだけで、その数が特定の数より大きいとエラーが発生します。バラよりnamei.cの1330行レビューとnested_symlink()
機能を確認してください。 ELOOPマクロ(この場合はシステムコールから返されたエラー番号read(2)
)はこのファイルのさまざまな場所に表示されるため、後続のリンクを計算するのと同じくらい簡単ではないかもしれませんが、確かにその外観です。
リンクリストから「サイクル」を見つけるための多くのアルゴリズムがあります(フロイドサイクル検出アルゴリズム) または有向グラフ。特定のパスで実際の「ループ」または「ループ」を検出するために何をすべきかは不明です。とにかくアルゴリズムの実行には長い時間がかかる可能性があるため、従うシンボリックリンクの数を数えるだけで目標の90%を達成できると推測します。