前面对linux虚拟文件系统的架构以及设计到的数据结构有了一个整体的认识,这里看看linux内核怎么根据给定的文件路径名在内存中找到和建立代表着目标文件或目录的dentry结构和inode结构。文件路径的搜索是文件系统中最基本也是最重要的一部分之一,后面我们会看到,文件的打开、关闭等等操作都将涉及到文件路径的搜索。下面我们看看linux内核中时怎么实现的。
一、搜索中所用数据结构
-
-
-
struct nameidata {
-
struct path path;
-
struct qstr last;
-
struct path root;
-
unsigned int flags;
-
int last_type;
-
unsigned depth;
-
char *saved_names[MAX_NESTED_LINKS + 1];
-
-
-
union {
-
struct open_intent open;
-
} intent;
-
};
-
-
struct qstr {
-
unsigned int hash;
-
unsigned int len;
-
const unsigned char *name;
-
};
二、搜索
-
-
-
-
int path_lookup(const char *name, unsigned int flags,
-
struct nameidata *nd)
-
{
-
return do_path_lookup(AT_FDCWD, name, flags, nd);
-
}
实际工作都是由上面的do_path_lookup()函数实现的,在这里我们就他进行分析。
-
-
static int do_path_lookup(int dfd, const char *name,
-
unsigned int flags, struct nameidata *nd)
-
{
-
int retval = path_init(dfd, name, flags, nd);
-
if (!retval)
-
-
-
retval = path_walk(name, nd);
-
if (unlikely(!retval && !audit_dummy_context() && nd->path.dentry &&
-
nd->path.dentry->d_inode))
-
audit_inode(name, nd->path.dentry);
-
if (nd->root.mnt) {
-
path_put(&nd->root);
-
nd->root.mnt = NULL;
-
}
-
return retval;
-
}
2.1 初始化阶段
初始化阶段是由函数path_init()函数实现
-
-
-
-
-
-
static int path_init(int dfd, const char *name, unsigned int flags, struct nameidata *nd)
-
{
-
int retval = 0;
-
int fput_needed;
-
struct file *file;
-
-
-
-
nd->last_type = LAST_ROOT;
-
nd->flags = flags;
-
nd->depth = 0;
-
nd->root.mnt = NULL;
-
-
if (*name=='/') {
-
set_root(nd);
-
nd->path = nd->root;
-
path_get(&nd->root);
-
} else if (dfd == AT_FDCWD) {
-
struct fs_struct *fs = current->fs;
-
read_lock(&fs->lock);
-
nd->path = fs->pwd;
-
path_get(&fs->pwd);
-
read_unlock(&fs->lock);
-
} else {
-
struct dentry *dentry;
-
-
-
-
-
-
file = fget_light(dfd, &fput_needed);
-
retval = -EBADF;
-
if (!file)
-
goto out_fail;
-
-
dentry = file->f_path.dentry;
-
-
retval = -ENOTDIR;
-
if (!S_ISDIR(dentry->d_inode->i_mode))
-
goto fput_fail;
-
-
retval = file_permission(file, MAY_EXEC);
-
if (retval)
-
goto fput_fail;
-
-
nd->path = file->f_path;
-
path_get(&file->f_path);
-
-
fput_light(file, fput_needed);
-
}
-
return 0;
-
-
fput_fail:
-
fput_light(file, fput_needed);
-
out_fail:
-
return retval;
-
}
2.2 实际搜索操作
-
static int path_walk(const char *name, struct nameidata *nd)
-
{
-
current->total_link_count = 0;
-
return link_path_walk(name, nd);
-
}
-
-
-
-
-
-
-
-
static __always_inline int link_path_walk(const char *name, struct nameidata *nd)
-
{
-
struct path save = nd->path;
-
int result;
-
-
-
path_get(&save);
-
-
result = __link_path_walk(name, nd);
-
if (result == -ESTALE) {
-
-
nd->path = save;
-
path_get(&nd->path);
-
nd->flags |= LOOKUP_REVAL;
-
result = __link_path_walk(name, nd);
-
}
-
-
path_put(&save);
-
-
return result;
-
}
-
-
-
-
-
-
-
-
-
static int __link_path_walk(const char *name, struct nameidata *nd)
-
{
-
struct path next;
-
struct inode *inode;
-
int err;
-
unsigned int lookup_flags = nd->flags;
-
-
-
-
-
while (*name=='/')
-
name++;
-
if (!*name)
-
goto return_reval;
-
-
-
inode = nd->path.dentry->d_inode;
-
-
-
-
-
-
-
-
if (nd->depth)
-
lookup_flags = LOOKUP_FOLLOW | (nd->flags & LOOKUP_CONTINUE);
-
-
-
for(;;) {
-
unsigned long hash;
-
-
struct qstr this;
-
unsigned int c;
-
-
nd->flags |= LOOKUP_CONTINUE;
-
-
-
-
err = exec_permission_lite(inode);
-
if (err)
-
break;
-
-
this.name = name;
-
c = *(const unsigned char *)name;
-
-
hash = init_name_hash();
-
do {
-
name++;
-
hash = partial_name_hash(c, hash);
-
c = *(const unsigned char *)name;
-
} while (c && (c != '/'));
-
this.len = name - (const char *) this.name;
-
this.hash = end_name_hash(hash);
-
-
-
if (!c)
-
goto last_component;
-
-
while (*++name == '/');
-
-
-
-
if (!*name)
-
goto last_with_slashes;
-
-
-
-
-
-
-
-
-
-
-
if (this.name[0] == '.') switch (this.len) {
-
default:
-
break;
-
case 2:
-
if (this.name[1] != '.')
-
break;
-
follow_dotdot(nd);
-
inode = nd->path.dentry->d_inode;
-
-
-
-
case 1:
-
continue;
-
}
-
-
-
-
-
-
-
if (nd->path.dentry->d_op && nd->path.dentry->d_op->d_hash) {
-
err = nd->path.dentry->d_op->d_hash(nd->path.dentry,
-
&this);
-
if (err < 0)
-
break;
-
}
-
-
-
err = do_lookup(nd, &this, &next);
-
if (err)
-
break;
-
-
err = -ENOENT;
-
inode = next.dentry->d_inode;
-
if (!inode)
-
goto out_dput;
-
-
if (inode->i_op->follow_link) {
-
err = do_follow_link(&next, nd);
-
if (err)
-
goto return_err;
-
err = -ENOENT;
-
inode = nd->path.dentry->d_inode;
-
if (!inode)
-
break;
-
} else
-
path_to_nameidata(&next, nd);
-
err = -ENOTDIR;
-
if (!inode->i_op->lookup)
-
break;
-
continue;
-
-
-
last_with_slashes:
-
lookup_flags |= LOOKUP_FOLLOW | LOOKUP_DIRECTORY;
-
last_component:
-
-
nd->flags &= lookup_flags | ~LOOKUP_CONTINUE;
-
if (lookup_flags & LOOKUP_PARENT)
-
goto lookup_parent;
-
if (this.name[0] == '.') switch (this.len) {
-
default:
-
break;
-
case 2:
-
if (this.name[1] != '.')
-
break;
-
follow_dotdot(nd);
-
inode = nd->path.dentry->d_inode;
-
-
case 1:
-
goto return_reval;
-
}
-
-
if (nd->path.dentry->d_op && nd->path.dentry->d_op->d_hash) {
-
err = nd->path.dentry->d_op->d_hash(nd->path.dentry,
-
&this);
-
if (err < 0)
-
break;
-
}
-
err = do_lookup(nd, &this, &next);
-
if (err)
-
break;
-
inode = next.dentry->d_inode;
-
if ((lookup_flags & LOOKUP_FOLLOW)
-
&& inode && inode->i_op->follow_link) {
-
err = do_follow_link(&next, nd);
-
if (err)
-
goto return_err;
-
inode = nd->path.dentry->d_inode;
-
} else
-
-
path_to_nameidata(&next, nd);
-
err = -ENOENT;
-
if (!inode)
-
break;
-
if (lookup_flags & LOOKUP_DIRECTORY) {
-
err = -ENOTDIR;
-
if (!inode->i_op->lookup)
-
break;
-
}
-
goto return_base;
-
lookup_parent:
-
nd->last = this;
-
nd->last_type = LAST_NORM;
-
if (this.name[0] != '.')
-
goto return_base;
-
if (this.len == 1)
-
nd->last_type = LAST_DOT;
-
else if (this.len == 2 && this.name[1] == '.')
-
nd->last_type = LAST_DOTDOT;
-
else
-
goto return_base;
-
return_reval:
-
-
-
-
-
if (nd->path.dentry && nd->path.dentry->d_sb &&
-
(nd->path.dentry->d_sb->s_type->fs_flags & FS_REVAL_DOT)) {
-
err = -ESTALE;
-
-
if (!nd->path.dentry->d_op->d_revalidate(
-
nd->path.dentry, nd))
-
break;
-
}
-
return_base:
-
return 0;
-
out_dput:
-
path_put_conditional(&next, nd);
-
break;
-
}
-
path_put(&nd->path);
-
return_err:
-
return err;
-
}
2.2.1 处理double dot
所谓double dot为访问上层目录
-
static __always_inline void follow_dotdot(struct nameidata *nd)
-
{
-
set_root(nd);
-
-
while(1) {
-
struct vfsmount *parent;
-
struct dentry *old = nd->path.dentry;
-
-
-
if (nd->path.dentry == nd->root.dentry &&
-
nd->path.mnt == nd->root.mnt) {
-
break;
-
}
-
spin_lock(&dcache_lock);
-
-
-
-
-
if (nd->path.dentry != nd->path.mnt->mnt_root) {
-
nd->path.dentry = dget(nd->path.dentry->d_parent);
-
spin_unlock(&dcache_lock);
-
dput(old);
-
break;
-
}
-
spin_unlock(&dcache_lock);
-
spin_lock(&vfsmount_lock);
-
-
-
-
-
-
-
-
-
parent = nd->path.mnt->mnt_parent;
-
-
if (parent == nd->path.mnt) {
-
spin_unlock(&vfsmount_lock);
-
break;
-
}
-
-
-
mntget(parent);
-
-
nd->path.dentry = dget(nd->path.mnt->mnt_mountpoint);
-
spin_unlock(&vfsmount_lock);
-
dput(old);
-
mntput(nd->path.mnt);
-
nd->path.mnt = parent;
-
}
-
follow_mount(&nd->path);
-
}
-
static void follow_mount(struct path *path)
-
{
-
while (d_mountpoint(path->dentry)) {
-
-
struct vfsmount *mounted = lookup_mnt(path);
-
if (!mounted)
-
break;
-
-
dput(path->dentry);
-
mntput(path->mnt);
-
path->mnt = mounted;
-
path->dentry = dget(mounted->mnt_root);
-
}
-
}
2.2.2 实际的路径搜索工作
-
-
-
-
-
-
static int do_lookup(struct nameidata *nd, struct qstr *name,
-
struct path *path)
-
{
-
struct vfsmount *mnt = nd->path.mnt;
-
-
-
-
-
struct dentry *dentry = __d_lookup(nd->path.dentry, name);
-
-
if (!dentry)
-
goto need_lookup;
-
if (dentry->d_op && dentry->d_op->d_revalidate)
-
goto need_revalidate;
-
done:
-
path->mnt = mnt;
-
path->dentry = dentry;
-
-
__follow_mount(path);
-
return 0;
-
-
need_lookup:
-
-
-
dentry = real_lookup(nd->path.dentry, name, nd);
-
if (IS_ERR(dentry))
-
goto fail;
-
goto done;
-
-
need_revalidate:
-
dentry = do_revalidate(dentry, nd);
-
if (!dentry)
-
goto need_lookup;
-
if (IS_ERR(dentry))
-
goto fail;
-
goto done;
-
-
fail:
-
return PTR_ERR(dentry);
-
}
-
-
-
-
-
-
-
-
-
static struct dentry * real_lookup(struct dentry * parent, struct qstr * name, struct nameidata *nd)
-
{
-
struct dentry * result;
-
struct inode *dir = parent->d_inode;
-
-
mutex_lock(&dir->i_mutex);
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
result = d_lookup(parent, name);
-
if (!result) {
-
struct dentry *dentry;
-
-
-
result = ERR_PTR(-ENOENT);
-
if (IS_DEADDIR(dir))
-
goto out_unlock;
-
-
dentry = d_alloc(parent, name);
-
result = ERR_PTR(-ENOMEM);
-
if (dentry) {
-
-
result = dir->i_op->lookup(dir, dentry, nd);
-
if (result)
-
dput(dentry);
-
else
-
result = dentry;
-
}
-
out_unlock:
-
mutex_unlock(&dir->i_mutex);
-
return result;
-
}
-
-
-
-
-
-
mutex_unlock(&dir->i_mutex);
-
if (result->d_op && result->d_op->d_revalidate) {
-
result = do_revalidate(result, nd);
-
if (!result)
-
result = ERR_PTR(-ENOENT);
-
}
-
return result;
-
}
2.2.2.1 分配dentry并且初始化
-
struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
-
{
-
struct dentry *dentry;
-
char *dname;
-
-
dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
-
if (!dentry)
-
return NULL;
-
-
if (name->len > DNAME_INLINE_LEN-1) {
-
dname = kmalloc(name->len + 1, GFP_KERNEL);
-
if (!dname) {
-
kmem_cache_free(dentry_cache, dentry);
-
return NULL;
-
}
-
} else {
-
dname = dentry->d_iname;
-
}
-
-
dentry->d_name.name = dname;
-
-
dentry->d_name.len = name->len;
-
dentry->d_name.hash = name->hash;
-
memcpy(dname, name->name, name->len);
-
dname[name->len] = 0;
-
-
atomic_set(&dentry->d_count, 1);
-
dentry->d_flags = DCACHE_UNHASHED;
-
spin_lock_init(&dentry->d_lock);
-
dentry->d_inode = NULL;
-
dentry->d_parent = NULL;
-
dentry->d_sb = NULL;
-
dentry->d_op = NULL;
-
dentry->d_fsdata = NULL;
-
dentry->d_mounted = 0;
-
INIT_HLIST_NODE(&dentry->d_hash);
-
INIT_LIST_HEAD(&dentry->d_lru);
-
INIT_LIST_HEAD(&dentry->d_subdirs);
-
INIT_LIST_HEAD(&dentry->d_alias);
-
-
if (parent) {
-
dentry->d_parent = dget(parent);
-
dentry->d_sb = parent->d_sb;
-
} else {
-
INIT_LIST_HEAD(&dentry->d_u.d_child);
-
}
-
-
spin_lock(&dcache_lock);
-
if (parent)
-
list_add(&dentry->d_u.d_child, &parent->d_subdirs);
-
dentry_stat.nr_dentry++;
-
spin_unlock(&dcache_lock);
-
-
return dentry;
-
}
从上面的代码中可以看到,linux内核中的路径搜索大体工作如下:
1,初始化查询,设置nd结构指向查询开始处的文件;
2,从起点开始路径的搜索,其中nd用来返回搜索结果,在搜索过程中需要根据路径名称一步一步的访问,包括字符‘/‘的处理、访问上层目录的处理(需要考虑超出本文件系统)以及访问的dentry在内存中不存在需要从新分配的情况等;
程序返回后,参数中的nd结构保存了当前的搜索结果信息,包括目标文件或目录的dentry结构和inode结构。
阅读(1458) | 评论(0) | 转发(0) |