这个问题,像许多其他事情一样,比表面上看起来的要复杂得多。
文件系统中的每个实体都指向一个“inode”,该inode描述了文件的内容。实体是您看到的东西 - 文件、目录、套接字、块设备、字符设备等等...
单个“文件”的内容可以通过一个或多个路径访问 - 这些路径中的每一个被称为“硬链接”。硬链接只能指向同一文件系统上的文件,不能跨越文件系统的边界。
还可以使用路径来寻址“符号链接”,它可以指向另一个路径 - 该路径不必存在,它可以是另一个符号链接,它可以在另一个文件系统上,或者它可以指回原始路径,从而产生无限循环。
不可能定位指向特定实体的所有链接(符号或硬链接)而不扫描整个树。
在我们深入讨论之前,先说几句:
- 请看结尾处的一些基准测试。虽然这个文件系统是在一个六盘 ZFS 阵列上的 i7 上运行的,所以在使用低规格系统时会花费更长时间,但我并不认为这是一个重要问题...
- 考虑到在某个时刻无法避免需要对每个文件调用
stat()
,你可能很难找到一个更好的解决方案,而不会显著增加复杂性(例如维护索引数据库,并引入所有这些问题)。
如下所述,我们
必须扫描(索引)整个树。我知道这不是你想要做的,但如果不这样做就不可能...
为了做到这一点,你需要收集
inode而不是文件名,并在事后进行审查... 这里可能有一些优化,但我尝试保持简单以优先理解。
下面的函数将为我们生成这个结构:
def get_map(scan_root):
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
感兴趣,那么你可以看到,仅查看符号链接(忽略硬链接)会导致我们错过
./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'}
此演示的完整源代码如下。请注意,我使用了相对路径来保持简单,但最好更新为使用绝对路径。此外,任何指向树外部的符号链接当前都没有相应的
link
...这是读者自行解决的问题。
在填充树时收集数据也可能是一个好主意(如果这适用于您的过程)...您可以使用
inotify
来很好地处理这个问题 - 甚至有一个
Python 模块。
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):
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)
我出于好奇在我的系统上运行了这个测试。这是一个由6个磁盘组成的ZFS RAID-Z2池,搭载着i7-7700K处理器,并有足够的数据进行测试。不可否认的是,在规格较低的系统上速度会慢一些...
以下是一些参考性能指标:
- 包含约3.1k个文件和链接以及850个目录的数据集。
运行时间不到3.5秒,后续运行时间为约80毫秒
- 包含约30k个文件和链接以及2.2k个目录的数据集。
运行时间不到30秒,后续运行时间为约300毫秒
- 包含约73.5k个文件和链接以及8k个目录的数据集。
运行时间约为60秒,后续运行时间为约800毫秒
简单计算一下,这意味着每秒大约执行1140次
stat()
调用(在缓存为空的情况下),或者在缓存填充后,每秒执行约90k次
stat()
调用——我认为
stat()
并没有你想象中那么慢!