确定文件相对于目录的路径，包括符号链接
Determine a file's path(s) relative to a directory, including symlinks
我有一个包含数千个后代的目录（至少 1,000 个，可能不超过 20,000 个）。给定一个文件路径（保证存在），我想知道在该目录中可以找到该文件的位置——包括通过符号链接。
例如，给定：
- 目录路径为
/base.
- 真正的文件路径是
/elsewhere/myfile.
/base 是 /realbase/realbase/foo 是 /elsewhere./realbase/bar/baz 是 /elsewhere/myfile.
我想找到路径 /base/foo/myfile 和 /base/bar/baz。
我可以通过递归检查 /base 中的每个符号链接来做到这一点，但这会非常慢。我希望有一个更优雅的解决方案。
动机
这是一个 Sublime Text 插件。当用户保存文件时，我们要检测它是否在 Sublime 配置目录中。特别是，即使文件是从 config 目录内部进行符号链接并且用户正在其物理路径（例如，在他们的 Dropbox 目录中）编辑文件，我们也希望这样做。可能还有其他应用。
Sublime 在 Linux、Windows 和 Mac OS 上运行，因此理想情况下应该是解决方案。
符号链接不允许使用快捷方式。您必须了解可能指向感兴趣文件的所有相关 FS 条目。这对应于创建一个空目录然后监听其下的所有文件创建事件，或者扫描当前在其下的所有文件。 运行 以下。
#! /usr/bin/env python
from pathlib import Path
import collections
import os
import pprint
import stat
class LinkFinder:
def __init__(self):
self.target_to_orig = collections.defaultdict(set)
def scan(self, folder='/tmp'):
for fspec, target in self._get_links(folder):
self.target_to_orig[target].add(fspec)
def _get_links(self, folder):
for root, dirs, files in os.walk(Path(folder).resolve()):
for file in files:
fspec = os.path.join(root, file)
if stat.S_ISLNK(os.lstat(fspec).st_mode):
target = os.path.abspath(os.readlink(fspec))
yield fspec, target
if __name__ == '__main__':
lf = LinkFinder()
for folder in '/base /realbase'.split():
lf.scan(folder)
pprint.pprint(lf.target_to_orig)
您最终得到了从所有符号链接的文件规范到一组别名的映射，通过这些别名可以访问该文件规范。
符号链接目标可以是文件或目录，因此要在给定的文件规范上正确使用映射，您必须重复 t运行cate 它，询问父目录或祖先目录是否出现在映射中。
悬空符号链接没有特殊处理，它们只是允许悬空。
您可以选择序列化映射，可能是按排序顺序。如果您反复重新扫描一个大目录，则有机会在 运行 秒内记住目录 mod 次，并避免重新扫描该目录中的文件。不幸的是，如果 它们 中的任何一个最近发生了变化，您仍然必须递归到它的后代目录中。
您的子树可能会展示足够的结构，让您避免递归超过 K 级深度，或避免进入名称与某些正则表达式匹配的目录。
如果大多数 FS 更改是由少数几个程序产生的，例如包管理器或构建系统，那么让这些程序记录它们的操作可能会产生性能上的优势。也就是说，如果您每个午夜都进行一次全面扫描，然后您 运行 make 只扫描一千个目录中的两个，您可以选择只重新扫描那对子树。
与许多事情一样，这比表面上看起来要复杂得多。
文件系统中的每个实体都指向一个描述文件内容的inode。实体是您看到的东西 - 文件、目录、套接字、块设备、字符设备等...
可以通过一个或多个路径访问单个“文件”的内容——这些路径中的每一个都称为“hard link”。硬 links 只能指向同一文件系统上的文件，它们不能跨越文件系统的边界。
路径也可以指向“符号 link”，它可以指向另一条路径——该路径不一定存在，它可以是另一个符号 link，它可以在另一个文件系统上，或者它可以指向产生无限循环的原始路径。
如果不扫描整棵树，就不可能找到所有指向特定实体的 link（符号或硬）。
在我们开始之前...一些评论：
- 查看结尾部分的一些基准测试。我不相信这是一个重大问题，尽管不可否认这个文件系统是在 i7 上的 6 磁盘 ZFS 阵列上，因此使用较低规格的系统将花费更长的时间...
- 鉴于这是 不可能的 如果不在某个时候对每个文件调用
stat()，你会很挣扎提出一个不会复杂得多的更好的解决方案（例如维护索引数据库，以及引入的所有问题）
如前所述，我们必须扫描（索引）整棵树。我知道这不是你想做的，但不这样做是不可能的...
为此，您需要收集 inodes，而不是文件名，并在事后查看它们...这里可能会有一些优化，但我已经尝试过保持理解的优先级简单。
下面的函数将为我们生成这个结构：
def get_map(scan_root):
# this dict will have device IDs at the first level (major / minor) ...
# ... and inodes IDs at the second level
# each inode will have the following keys:
# - 'type' the entity's type - i.e: dir, file, socket, etc...
# - 'links' a list of all found hard links to the inode
# - 'symlinks' a list of all found symlinks to the inode
# e.g: entities[2049][4756]['links'][0] path to a hard link for inode 4756
# entities[2049][4756]['symlinks'][0] path to a symlink that points at an entity with inode 4756
entity_map = {}
for root, dirs, files in os.walk(scan_root):
root = '.' + root[len(scan_root):]
for path in [ os.path.join(root, _) for _ in files ]:
try:
p_stat = os.stat(path)
except OSError as e:
if e.errno == 2:
print('Broken symlink [%s]... skipping' % ( path ))
continue
if e.errno == 40:
print('Too many levels of symbolic links [%s]... skipping' % ( path ))
continue
raise
p_dev = p_stat.st_dev
p_ino = p_stat.st_ino
if p_dev not in entity_map:
entity_map[p_dev] = {}
e_dev = entity_map[p_dev]
if p_ino not in e_dev:
e_dev[p_ino] = {
'type': get_type(p_stat.st_mode),
'links': [],
'symlinks': [],
}
e_ino = e_dev[p_ino]
if os.lstat(path).st_ino == p_ino:
e_ino['links'].append(path)
else:
e_ino['symlinks'].append(path)
return entity_map
我制作了一个示例树，如下所示：
$ tree --inodes
.
├── [ 67687] 4 -> 5
├── [ 67676] 5 -> 4
├── [ 67675] 6 -> dead
├── [ 67676] a
│ └── [ 67679] 1
├── [ 67677] b
│ └── [ 67679] 2 -> ../a/1
├── [ 67678] c
│ └── [ 67679] 3
└── [ 67687] d
└── [ 67688] 4
4 directories, 7 files
这个函数的输出是：
$ places
Broken symlink [./6]... skipping
Too many levels of symbolic links [./5]... skipping
Too many levels of symbolic links [./4]... skipping
{201: {67679: {'links': ['./a/1', './c/3'],
'symlinks': ['./b/2'],
'type': 'file'},
67688: {'links': ['./d/4'], 'symlinks': [], 'type': 'file'}}}
如果我们对 ./c/3 感兴趣，那么您可以看到仅查看 symlinks（并忽略 hard links）会导致我们错过 ./a/1...
通过随后搜索我们感兴趣的路径，我们可以找到该树中的所有其他引用：
def filter_map(entity_map, filename):
for dev, inodes in entity_map.items():
for inode, info in inodes.items():
if filename in info['links'] or filename in info['symlinks']:
return info
$ places ./a/1
Broken symlink [./6]... skipping
Too many levels of symbolic links [./5]... skipping
Too many levels of symbolic links [./4]... skipping
{'links': ['./a/1', './c/3'], 'symlinks': ['./b/2'], 'type': 'file'}
此演示的完整源代码如下。请注意，为了简单起见，我使用了相对路径，但将其更新为使用绝对路径是明智的。此外，任何指向树外的 symlink 目前不会有相应的 link... 这是 reader.
的练习
在填充树的同时收集数据也可能是个好主意（如果这对您的过程有用的话）...您可以使用 inotify to deal with this nicely - there's even a python module.
#!/usr/bin/env python3
import os, sys, stat
from pprint import pprint
def get_type(mode):
if stat.S_ISDIR(mode):
return 'directory'
if stat.S_ISCHR(mode):
return 'character'
if stat.S_ISBLK(mode):
return 'block'
if stat.S_ISREG(mode):
return 'file'
if stat.S_ISFIFO(mode):
return 'fifo'
if stat.S_ISLNK(mode):
return 'symlink'
if stat.S_ISSOCK(mode):
return 'socket'
return 'unknown'
def get_map(scan_root):
# this dict will have device IDs at the first level (major / minor) ...
# ... and inodes IDs at the second level
# each inode will have the following keys:
# - 'type' the entity's type - i.e: dir, file, socket, etc...
# - 'links' a list of all found hard links to the inode
# - 'symlinks' a list of all found symlinks to the inode
# e.g: entities[2049][4756]['links'][0] path to a hard link for inode 4756
# entities[2049][4756]['symlinks'][0] path to a symlink that points at an entity with inode 4756
entity_map = {}
for root, dirs, files in os.walk(scan_root):
root = '.' + root[len(scan_root):]
for path in [ os.path.join(root, _) for _ in files ]:
try:
p_stat = os.stat(path)
except OSError as e:
if e.errno == 2:
print('Broken symlink [%s]... skipping' % ( path ))
continue
if e.errno == 40:
print('Too many levels of symbolic links [%s]... skipping' % ( path ))
continue
raise
p_dev = p_stat.st_dev
p_ino = p_stat.st_ino
if p_dev not in entity_map:
entity_map[p_dev] = {}
e_dev = entity_map[p_dev]
if p_ino not in e_dev:
e_dev[p_ino] = {
'type': get_type(p_stat.st_mode),
'links': [],
'symlinks': [],
}
e_ino = e_dev[p_ino]
if os.lstat(path).st_ino == p_ino:
e_ino['links'].append(path)
else:
e_ino['symlinks'].append(path)
return entity_map
def filter_map(entity_map, filename):
for dev, inodes in entity_map.items():
for inode, info in inodes.items():
if filename in info['links'] or filename in info['symlinks']:
return info
entity_map = get_map(os.getcwd())
if len(sys.argv) == 2:
entity_info = filter_map(entity_map, sys.argv[1])
pprint(entity_info)
else:
pprint(entity_map)
出于好奇，我已经 运行 在我的系统上安装了这个。它是 i7-7700K 上的 6x 磁盘 ZFS RAID-Z2 池，有大量数据可供使用。诚然，这会 运行 在低规格系统上稍微慢一些...
需要考虑的一些基准：
- 约 3.1k 个文件和约 850 个目录中的 links 的数据集。
这个 运行s 不到 3.5 秒，后续 运行s
~80ms
- 约 30k 个文件和约 2.2k 个目录中的 links 的数据集。
这 运行 秒不到 30 秒，随后的 运行 秒
约 300 毫秒
- 约 73.5k 文件和约 8k 目录中的 links 的数据集。
这个 运行s 在大约 60 秒内，随后的 运行s
~800ms
使用简单的数学计算，在缓存为空的情况下每秒大约有 1140 stat() 次调用，或者在缓存已满后每秒大约 90k stat() 次调用 - 我不认为 stat() 和你想象的一样慢！
我的第一直觉是让 OS 或某些服务在文件系统树发生更改时通知您，而不是您寻找更改。本质上不要重新发明轮子。
也许：
Windows 具体：5 tools to monitor folder changes
我有一个包含数千个后代的目录（至少 1,000 个，可能不超过 20,000 个）。给定一个文件路径（保证存在），我想知道在该目录中可以找到该文件的位置——包括通过符号链接。
例如，给定：
- 目录路径为
/base. - 真正的文件路径是
/elsewhere/myfile. /base是/realbase 的符号链接
/realbase/foo是/elsewhere. 的符号链接
/realbase/bar/baz是/elsewhere/myfile. 的符号链接
我想找到路径 /base/foo/myfile 和 /base/bar/baz。
我可以通过递归检查 /base 中的每个符号链接来做到这一点，但这会非常慢。我希望有一个更优雅的解决方案。
动机
这是一个 Sublime Text 插件。当用户保存文件时，我们要检测它是否在 Sublime 配置目录中。特别是，即使文件是从 config 目录内部进行符号链接并且用户正在其物理路径（例如，在他们的 Dropbox 目录中）编辑文件，我们也希望这样做。可能还有其他应用。
Sublime 在 Linux、Windows 和 Mac OS 上运行，因此理想情况下应该是解决方案。
符号链接不允许使用快捷方式。您必须了解可能指向感兴趣文件的所有相关 FS 条目。这对应于创建一个空目录然后监听其下的所有文件创建事件，或者扫描当前在其下的所有文件。 运行 以下。
#! /usr/bin/env python
from pathlib import Path
import collections
import os
import pprint
import stat
class LinkFinder:
def __init__(self):
self.target_to_orig = collections.defaultdict(set)
def scan(self, folder='/tmp'):
for fspec, target in self._get_links(folder):
self.target_to_orig[target].add(fspec)
def _get_links(self, folder):
for root, dirs, files in os.walk(Path(folder).resolve()):
for file in files:
fspec = os.path.join(root, file)
if stat.S_ISLNK(os.lstat(fspec).st_mode):
target = os.path.abspath(os.readlink(fspec))
yield fspec, target
if __name__ == '__main__':
lf = LinkFinder()
for folder in '/base /realbase'.split():
lf.scan(folder)
pprint.pprint(lf.target_to_orig)
您最终得到了从所有符号链接的文件规范到一组别名的映射，通过这些别名可以访问该文件规范。
符号链接目标可以是文件或目录，因此要在给定的文件规范上正确使用映射，您必须重复 t运行cate 它，询问父目录或祖先目录是否出现在映射中。
悬空符号链接没有特殊处理，它们只是允许悬空。
您可以选择序列化映射，可能是按排序顺序。如果您反复重新扫描一个大目录，则有机会在 运行 秒内记住目录 mod 次，并避免重新扫描该目录中的文件。不幸的是，如果 它们 中的任何一个最近发生了变化，您仍然必须递归到它的后代目录中。 您的子树可能会展示足够的结构，让您避免递归超过 K 级深度，或避免进入名称与某些正则表达式匹配的目录。
如果大多数 FS 更改是由少数几个程序产生的，例如包管理器或构建系统，那么让这些程序记录它们的操作可能会产生性能上的优势。也就是说，如果您每个午夜都进行一次全面扫描，然后您 运行 make 只扫描一千个目录中的两个，您可以选择只重新扫描那对子树。
与许多事情一样，这比表面上看起来要复杂得多。
文件系统中的每个实体都指向一个描述文件内容的inode。实体是您看到的东西 - 文件、目录、套接字、块设备、字符设备等...
可以通过一个或多个路径访问单个“文件”的内容——这些路径中的每一个都称为“hard link”。硬 links 只能指向同一文件系统上的文件，它们不能跨越文件系统的边界。
路径也可以指向“符号 link”，它可以指向另一条路径——该路径不一定存在，它可以是另一个符号 link，它可以在另一个文件系统上，或者它可以指向产生无限循环的原始路径。
如果不扫描整棵树，就不可能找到所有指向特定实体的 link（符号或硬）。
在我们开始之前...一些评论：
- 查看结尾部分的一些基准测试。我不相信这是一个重大问题，尽管不可否认这个文件系统是在 i7 上的 6 磁盘 ZFS 阵列上，因此使用较低规格的系统将花费更长的时间...
- 鉴于这是 不可能的 如果不在某个时候对每个文件调用
stat()，你会很挣扎提出一个不会复杂得多的更好的解决方案（例如维护索引数据库，以及引入的所有问题）
如前所述，我们必须扫描（索引）整棵树。我知道这不是你想做的，但不这样做是不可能的...
为此，您需要收集 inodes，而不是文件名，并在事后查看它们...这里可能会有一些优化，但我已经尝试过保持理解的优先级简单。
下面的函数将为我们生成这个结构：
def get_map(scan_root):
# this dict will have device IDs at the first level (major / minor) ...
# ... and inodes IDs at the second level
# each inode will have the following keys:
# - 'type' the entity's type - i.e: dir, file, socket, etc...
# - 'links' a list of all found hard links to the inode
# - 'symlinks' a list of all found symlinks to the inode
# e.g: entities[2049][4756]['links'][0] path to a hard link for inode 4756
# entities[2049][4756]['symlinks'][0] path to a symlink that points at an entity with inode 4756
entity_map = {}
for root, dirs, files in os.walk(scan_root):
root = '.' + root[len(scan_root):]
for path in [ os.path.join(root, _) for _ in files ]:
try:
p_stat = os.stat(path)
except OSError as e:
if e.errno == 2:
print('Broken symlink [%s]... skipping' % ( path ))
continue
if e.errno == 40:
print('Too many levels of symbolic links [%s]... skipping' % ( path ))
continue
raise
p_dev = p_stat.st_dev
p_ino = p_stat.st_ino
if p_dev not in entity_map:
entity_map[p_dev] = {}
e_dev = entity_map[p_dev]
if p_ino not in e_dev:
e_dev[p_ino] = {
'type': get_type(p_stat.st_mode),
'links': [],
'symlinks': [],
}
e_ino = e_dev[p_ino]
if os.lstat(path).st_ino == p_ino:
e_ino['links'].append(path)
else:
e_ino['symlinks'].append(path)
return entity_map
我制作了一个示例树，如下所示：
$ tree --inodes
.
├── [ 67687] 4 -> 5
├── [ 67676] 5 -> 4
├── [ 67675] 6 -> dead
├── [ 67676] a
│ └── [ 67679] 1
├── [ 67677] b
│ └── [ 67679] 2 -> ../a/1
├── [ 67678] c
│ └── [ 67679] 3
└── [ 67687] d
└── [ 67688] 4
4 directories, 7 files
这个函数的输出是：
$ places
Broken symlink [./6]... skipping
Too many levels of symbolic links [./5]... skipping
Too many levels of symbolic links [./4]... skipping
{201: {67679: {'links': ['./a/1', './c/3'],
'symlinks': ['./b/2'],
'type': 'file'},
67688: {'links': ['./d/4'], 'symlinks': [], 'type': 'file'}}}
如果我们对 ./c/3 感兴趣，那么您可以看到仅查看 symlinks（并忽略 hard links）会导致我们错过 ./a/1...
通过随后搜索我们感兴趣的路径，我们可以找到该树中的所有其他引用：
def filter_map(entity_map, filename):
for dev, inodes in entity_map.items():
for inode, info in inodes.items():
if filename in info['links'] or filename in info['symlinks']:
return info
$ places ./a/1
Broken symlink [./6]... skipping
Too many levels of symbolic links [./5]... skipping
Too many levels of symbolic links [./4]... skipping
{'links': ['./a/1', './c/3'], 'symlinks': ['./b/2'], 'type': 'file'}
此演示的完整源代码如下。请注意，为了简单起见，我使用了相对路径，但将其更新为使用绝对路径是明智的。此外，任何指向树外的 symlink 目前不会有相应的 link... 这是 reader.
在填充树的同时收集数据也可能是个好主意（如果这对您的过程有用的话）...您可以使用 inotify to deal with this nicely - there's even a python module.
#!/usr/bin/env python3
import os, sys, stat
from pprint import pprint
def get_type(mode):
if stat.S_ISDIR(mode):
return 'directory'
if stat.S_ISCHR(mode):
return 'character'
if stat.S_ISBLK(mode):
return 'block'
if stat.S_ISREG(mode):
return 'file'
if stat.S_ISFIFO(mode):
return 'fifo'
if stat.S_ISLNK(mode):
return 'symlink'
if stat.S_ISSOCK(mode):
return 'socket'
return 'unknown'
def get_map(scan_root):
# this dict will have device IDs at the first level (major / minor) ...
# ... and inodes IDs at the second level
# each inode will have the following keys:
# - 'type' the entity's type - i.e: dir, file, socket, etc...
# - 'links' a list of all found hard links to the inode
# - 'symlinks' a list of all found symlinks to the inode
# e.g: entities[2049][4756]['links'][0] path to a hard link for inode 4756
# entities[2049][4756]['symlinks'][0] path to a symlink that points at an entity with inode 4756
entity_map = {}
for root, dirs, files in os.walk(scan_root):
root = '.' + root[len(scan_root):]
for path in [ os.path.join(root, _) for _ in files ]:
try:
p_stat = os.stat(path)
except OSError as e:
if e.errno == 2:
print('Broken symlink [%s]... skipping' % ( path ))
continue
if e.errno == 40:
print('Too many levels of symbolic links [%s]... skipping' % ( path ))
continue
raise
p_dev = p_stat.st_dev
p_ino = p_stat.st_ino
if p_dev not in entity_map:
entity_map[p_dev] = {}
e_dev = entity_map[p_dev]
if p_ino not in e_dev:
e_dev[p_ino] = {
'type': get_type(p_stat.st_mode),
'links': [],
'symlinks': [],
}
e_ino = e_dev[p_ino]
if os.lstat(path).st_ino == p_ino:
e_ino['links'].append(path)
else:
e_ino['symlinks'].append(path)
return entity_map
def filter_map(entity_map, filename):
for dev, inodes in entity_map.items():
for inode, info in inodes.items():
if filename in info['links'] or filename in info['symlinks']:
return info
entity_map = get_map(os.getcwd())
if len(sys.argv) == 2:
entity_info = filter_map(entity_map, sys.argv[1])
pprint(entity_info)
else:
pprint(entity_map)
出于好奇，我已经 运行 在我的系统上安装了这个。它是 i7-7700K 上的 6x 磁盘 ZFS RAID-Z2 池，有大量数据可供使用。诚然，这会 运行 在低规格系统上稍微慢一些...
需要考虑的一些基准：
- 约 3.1k 个文件和约 850 个目录中的 links 的数据集。 这个 运行s 不到 3.5 秒，后续 运行s ~80ms
- 约 30k 个文件和约 2.2k 个目录中的 links 的数据集。 这 运行 秒不到 30 秒，随后的 运行 秒 约 300 毫秒
- 约 73.5k 文件和约 8k 目录中的 links 的数据集。 这个 运行s 在大约 60 秒内，随后的 运行s ~800ms
使用简单的数学计算，在缓存为空的情况下每秒大约有 1140 stat() 次调用，或者在缓存已满后每秒大约 90k stat() 次调用 - 我不认为 stat() 和你想象的一样慢！
我的第一直觉是让 OS 或某些服务在文件系统树发生更改时通知您，而不是您寻找更改。本质上不要重新发明轮子。
也许：
Windows 具体：5 tools to monitor folder changes