Linux路径名查找

╰半夏微凉° 2022-08-22 00:05 197阅读 0赞

对于文件系统的大部分操作（open、stat、unlink等等）都要涉及多多少少的路径解析。路劲解析是根据路径名（name string）得到对应的dentry对象，通过路径行走的方式。本文就来介绍路径行走。

### **路径行走解释** ###

路径是由一个开始字符（根目录、当前工作目录或者fd指向的目录），和一串其他的文件名组成的，path中的每一个文件名用/分割开。名称查找（Name Lookup）就是希望根据已知的path和name的开始指针找到path中的最后一个文件名或者最后一个文件的父文件名。根据name指针找path中要求的当前父亲文件的孩子文件，如果孩子并不是最后一个path组件（component），孩子文件称为新的父文件，迭代这个过程，就像是在path上行走一样，因此被称为路径行走。  
  这个过程要求父亲必须是一个目录，并且我们对父亲文件的inode节点拥有读权限。为了下一步查找把孩子文件变成父亲文件的时候，要求更多的检测规程。符号链接实质上是链接所指向文件的替代，符号链接要求递归的路径行走。挂载点必须被跟踪(因此改变vfsmount的后续路径元素引用),从挂载点路径切换到特定的安装vfsmount的根目录。这些不同的修改行为取决于具体的路径行走标志。

### **路径行走必须做下面几件事：** ###

>  *  找到行走的起点
>  *  执行权限和有效性检查
>  *  执行目录项缓存元组上的的哈希name查找
>  *  遍历挂载点
>  *  遍历符号链接
>  *  查找或者创建要求路径中的文件

路径行走有两个模式：rcu\_walk模式和ref\_walk模式。ref-walk是传统的使用自旋锁（d\_lock）去并发修改目录项。比起rcu-walk这个模式，ref-walk是操作简单，但是在在路劲行走的过程中，对于每一个目录项的操作可能需要睡眠、得到锁等等这些操作。rcu-walk是基于顺序锁的目录项查找，可以不用存储任何共享数据在目录项或inode里，查找中间的元素。rcu-walk并不适合与任何一种情况，比如说：如果文件系统必须沉睡或者执行不重要的操作，就需要切换到ref-walk模式。  
  在 rcu-walk 期间将会禁止抢占，也决不能出现进程阻塞，所以其效率很高；ref-walk 会在 rcu-walk 失败、进程需要随眠或者需要取得某结构的引用计数（reference count）的情况下切换进来，很明显它的效率大大低于

### **路径行走的过程总结** ###

路径行走到底是在找什么呢？说的简单一点，就是在找路径所指向的文件的父目录项。因为整个查找过程是一个分量一个分量的查找的，就像是在路径上行走一样，因此成为路径行走。行走结束，得到对应的dentry。

#### 1.中间数据 ####

nd变量：用来保存找到的当前分量dentry我们需要的信息，而且这个分量一定是一个普通的、真正的目录。  
path变量：既然nd变量只能保存真正目录的信息，如果我们得到了一个分量，我们在确定这个分量是真正的目录之前，找到的dentry信息就用path变量保存。  
name变量：指向路径中当前的分量开始位置

#### 2.大致过程 ####

在内核空间申请一页空间，把存储在用户空间的路径信息拷贝到内核空间，初次创建nd结构体。  
初始化nd结构体，理想情况下，nd保存的是name指针指向的分量的上一个分量信息，原因还是因为nd结构体要求保存真正的目录的信息。如果路径是绝对路径，nd结构体初始化为根目录的dentry信息，如果路径是相对路径，nd结构体初始化位当前进程cwd的dentry信息。  
开始”行走“第一个分量，这个分量信息在初始化的时候填充完成，因此第一次行走要做的工作并不多。然后移动name指针指向第二个分量，如果这个分量是普通目录，行走这个分量：

根据分量名的hash值在内核缓冲区查找dentry
    如果没有找到，调用文件系统自身的lookup，

并循环执行上面过程。  
如果这个分量是.目录或者..目录，则：

如果是.目录，直接返回0。对于当前目录并不需要做任何操作
    如果是..目录，找到父目录的dentry，填充nd结构体

如果这个分量是符号链接：  
找到符号链接指向的文件的dentry，填充nd结构体。

### **代码解释** ###

函数user\_path\_parent主要执行path walking，我们下面来看看这个函数的内核实现。函数原型如下：

static struct filename *
    user_path_parent(int dfd, const char __user *path, struct nameidata *nd, 
             unsigned int flags)

函数返回值是filename结构体，参数分别是系统调用传入的dfd参数，存储在用户空间的path，带填充的nameidata结构体（这个结构体在路径行走的过程中，主要用来保存一些临时数据），最后是一个标志位。我们看到参数里面有一个nameidata结构体，这个结构体在整个路径行走过程中至关重要，所以还是在看函数之前还是看看这个结构体。定义如下：

struct nameidata {
        struct path path;               //存储文件挂载点和dentry地址
        struct qstr last;               //路径名最后分量
        struct path root;               //存在文件所在文件系统根的信息
        struct inode    *inode;         //path.dentry.d_inode 
        unsigned int    flags;          //标志
        unsigned    seq, m_seq;      //seq 是相关目录项的顺序锁序号； m_seq 是相关文件系统（其实是mount）的顺序锁序号
        int     last_type;          //路径最后的文件类型
        unsigned    depth;              //解析符号链接过程中的递归深度
        char *saved_names[MAX_NESTED_LINKS + 1];            //相应递归深度的符号链接的路径
    };
    //其中type的取值是一个枚举类型，如下
    enum {LAST_NORM, LAST_ROOT, LAST_DOT, LAST_DOTDOT, LAST_BIND};
    //分别代表了普通文件，根文件，.文件，..文件和符号链接文件

下面我们还需要看看filename结构体是什么样子，因为我们需要分析的函数的返回值是这个类型的，我们必须知道我们的函数是返回了一个什么东西。定义如下：

struct filename {
            const char      *name;    //真实的名字
        const __user char   *uptr;       //原来的用户指针
        struct audit_names  *aname;
        bool            separate;       //name是不是应该被释放
    };

这里面的前两个指针变量不是很理解，没关系，等会分析完函数就明白了。接下来我们才来分析user\_path\_parent函数，函数代码如下：

struct filename *s = getname(path);
        int error;
    
        /* only LOOKUP_REVAL is allowed in extra flags */
        //设置LOOKUP_REVAL标志
        flags &= LOOKUP_REVAL;
    
        if (IS_ERR(s))
            return s;
    
        error = filename_lookup(dfd, s, flags | LOOKUP_PARENT, nd);
        if (error) {
            putname(s);
            return ERR_PTR(error);
        }
    
        return s;

很明显，可以看到除了一些出错处理，函数user\_path\_parent函数主要调用了getname函数和filename\_loopup函数。所以我们还是分析这两个函数。显示分析getname函数：

result = __getname();
        if (unlikely(!result))
            return ERR_PTR(-ENOMEM);
    
        /*
         * First, try to embed the struct filename inside the names_cache
         * allocation
            */
        kname = (char *)result + sizeof(*result);
        result->name = kname;
        result->separate = false;
        max = EMBEDDED_NAME_MAX;
    recopy:
        len = strncpy_from_user(kname, filename, max);
        if (unlikely(len < 0)) {
            err = ERR_PTR(len);
            goto error;
        }

函数getname第一步就是调用\_\_getname函数，为了避免本文边的很冗长，这个函数我们暂且不具体分析。他的功能就是在内核空间分配4096字节的空间，然后把地址赋给result，kname保存分配到的这篇空间的尾地址，并且把这个地址赋给filename的name成员变量，这里我们可以猜测一下，不管将来name里面保存了什么变量，肯定是存储在这片空间的末尾的，并且设置这个name不能被释放。EMBEDDED\_NAME\_MAX这个宏变量的是这页空间存储完filename结构体以后，还剩多少字节空间，把这个值赋给max变量。开始把存储在用户空间的path拷贝到内核空间，并且返回拷贝字节数，并且判断拷贝动作是否成功，若出错进行出错处理。

if (len == EMBEDDED_NAME_MAX && max == EMBEDDED_NAME_MAX) {
            kname = (char *)result;
            result = kzalloc(sizeof(*result), GFP_KERNEL);
            if (!result) {
                err = ERR_PTR(-ENOMEM);
                result = (struct filename *)kname;
                goto error;
            }
    
            result->name = kname;
            result->separate = true;
    
            max = PATH_MAX;
        /* The empty path is special. */
        if (unlikely(!len)) {
            if (empty)
                *empty = 1;
            err = ERR_PTR(-ENOENT);
            if (!(flags & LOOKUP_EMPTY))
                goto error;
        }
    
        err = ERR_PTR(-ENAMETOOLONG);
        if (unlikely(len >= PATH_MAX))
            goto error;
    
        result->uptr = filename;
        result->aname = NULL;
        audit_getname(result);
        return result;

判断如果拷贝到内核空间的path把新分配的这页占满了，kname指向这个空间开始的位置（kname时刻指向path开始的位置）,然后调用kalloc函数分配再分配一页空间。成功以后，把kname的地址（也就是path存储在内核空间的首地址赋给result的name域，设置name可以被释放。）并且把之前春初在user空间的地址存储在result的utpr域 （现在明白了这个原来的用户是什么意思了吧）。获取到aname域，并且填充。最后返回result。这个getname函数我们就分析完成了。下面来看看filename\_lookup函数：

err = path_init(dfd, name, flags | LOOKUP_PARENT, nd, &base);
    
        if (unlikely(err))
            return err;
    
        current->total_link_count = 0;              //设置当前进程描述符符号链接数
    
        //路径名查找操作的核心
    
        err = link_path_walk(name, nd);
    
        ...

这个函数功能就比较复杂了，我们先来大概讲讲这些函数的功能，并且展开一部分函数仔细分析。首先是path\_init函数，顾名思义就是初始化path函数，我们前面说了整个路径查找的过程其实就是填充nameidata的过程，所以这个函数肯定就是初始化nameidata，然后是就函数link\_path\_walk，这个函数是整个路径名查找过程的核心功能实现函数，经过这个函数，我们就找到了路径中的最后一个目录的dentry和inode信息了。然后后面的我还没有研究清楚是做什么的函数,所以这里暂不分析。我们接下来看看path\_init函数，

static int path_init(int dfd, const char *name, unsigned int flags,
                 struct nameidata *nd, struct file **fp)
    {
        int retval = 0;
    
        nd->last_type = LAST_ROOT; /* if there are only slashes... */
        nd->flags = flags | LOOKUP_JUMPED;
        nd->depth = 0;    
    
        if (flags & LOOKUP_ROOT) {
            }

首先将 last\_type 设置成 LAST\_ROOT，意思就是在路径名中只有“/”。为方便叙述，我们把一个路径名分成三部分：起点（根目录或工作目录）、子路径（以“/”分隔的一系列子字符串）和最终目标（最后一个子路径），Kernel 会一个子路径一个子路径的遍历整个路径。所以 last\_type 表示的是当前子路径（不是 dentry 或 inode）的类型。LOOKUP\_ROOT标志 可以提供一个路径作为根路径，主要用于两个系统调用 open\_by\_handle\_at 和 sysctl，这里不做分析了。

nd->root.mnt = NULL;
    
        nd->m_seq = read_seqbegin(&mount_lock);
        if (*name=='/') {                   
            if (flags & LOOKUP_RCU) {
                rcu_read_lock();
                nd->seq = set_root_rcu(nd
    else {
                set_root(nd);
                path_get(&nd->root);
            }
            nd->path = nd->root;                    
        } else if (dfd == AT_FDCWD) {                   //表示path应该是当前进程的cwd 
                if (flags & LOOKUP_RCU) {
                struct fs_struct *fs = current->fs;             //获取进程的fs结构体， 
                unsigned seq;
    
                rcu_read_lock();
    
                do {
                    seq = read_seqcount_begin(&fs->seq);
                    nd->path = fs->pwd;
                    nd->seq = __read_seqcount_begin(&nd->path.dentry->d_seq);
                } while (read_seqcount_retry(&fs->seq, seq));
            } else {
                get_fs_pwd(current->fs, &nd->path);
            }
    }

设置vfsmount域是空，初始化相关文件系统的的顺序锁序号。然后根据给定的path内容，设置其实位置。如果给定的是绝对路径（第一个字符是’/’），就把path指向进程的根目录，如果dfd==AF\_FDCWD,表示path是调用进程的当前工作路径，获取current（这个在前面分析do\_fork的博文里面解释了这个宏表示当前进程）的当前工作路径，把path执行这个路径。

else {                       //这个else选择表示 path不是一个绝对路径，而且dfd不是一个特殊的值
            /* Caller must check execute permissions on the starting path component */
            struct fd f = fdget_raw(dfd);               
            struct dentry *dentry;
    
            if (!f.file)
                return -EBADF;
    
            dentry = f.file->f_path.dentry;            
    
            if (*name) {
                if (!d_can_lookup(dentry)) {
                    fdput(f);
                    return -ENOTDIR;
                }
    
            nd->path = f.file->f_path;                  
            if (flags & LOOKUP_RCU) {
                if (f.flags & FDPUT_FPUT)
                    *fp = f.file;
                nd->seq = __read_seqcount_begin(&nd->path.dentry->d_seq);
                rcu_read_lock();
            } else {
                path_get(&nd->path);
                fdput(f);
            }
        }
    
        nd->inode = nd->path.dentry->d_inode;              
        return 0;

如果传入的path不是一个绝对路径，而且dfd不是一个特殊的值。根据这个dfd得到对应的fd结构体，然后获取这个dfd所指向文件的dentry结构体，把path指向这个目录。  
  所以大概来说，path\_init函数就是根据传入的不同参数初始化nd的path域。  
分析完了path\_init函数，我们接下来分析path walk的核心函数——link\_path\_walk函数。

static int link_path_walk(const char *name, struct nameidata *nd)
    {
        struct path next;
        int err;
    
        while (*name=='/')             
            name++;                     
        if (!*name)                    
            return 0;
    
        /* At this point we know we have a real path component. */
    
        for(;;) {
    
            struct qstr this;
            long len;
            int type;
    
            err = may_lookup(nd);
            if (err)
                break;
    
            len = hash_name(name, &this.hash);
    
            //填充quick string结构体
            this.name = name;
            this.len = len;
    
            type = LAST_NORM;               
    
            if (name[0] == '.') switch (len) {
                case 2:
                    if (name[1] == '.') {
                        type = LAST_DOTDOT;

函数头解释：函数返回一个int值可以判断查找操作是否出错，参数name就是从用户空间复制来的path，nd表示查找过程中用来存储临时数据的nameidata结构体。  
  首先跳过多个连续的/（内核是有这样的容错的，你可以试试输入一个 ls ///和ls /输出是不是一样的），这样做是为了是的name指针指向一个真正的path中的第一个文件名 判断name是不是空的，空返回。因为如果是/开始的，在path\_init函数中nd填充的就是根文件的信息，如果此时name为空表示path就是根目录，那么就不需要pathwalk已经找到了对应的dentry和其他的信息。现在开始一个很大的死循环，可以肯定我们所有的查找操作都是在这个循环里。在查找之前要先检测权限。如果权限检测出错，跳出循环。计算name（系统调用传入的path），填充quick string结构体。初始化name的第一个文件的文件类型，（分为普通文件，.文件和..文件）。

if (name[1] == '.') {
                        type = LAST_DOTDOT;
                        nd->flags |= LOOKUP_JUMPED;
                    }
                    break;
                case 1:
                    type = LAST_DOT;
            }
            if (likely(type == LAST_NORM)) {            //说明path的第一个component并不是.或者..开始的，那就接着查询>下一个
                struct dentry *parent = nd->path.dentry;
                nd->flags &= ~LOOKUP_JUMPED;                //清除查找jumped标志
                if (unlikely(parent->d_flags & DCACHE_OP_HASH)) {
                    err = parent->d_op->d_hash(parent, &this);
                    if (err < 0)
                        break;
                }
            }
    
            nd->last = this;            //设置nameidata的路径名最后分量是当前路径，
            nd->last_type = type;           //设置type
            do {
                len++;     
            } while (unlikely(name[len] == '/'));
            if (!name[len])
                return 0;
    
            //使name再次指向下一个path component
            name += len;

如果第一个分量是普通文件，得到path中的第一个分量的dentry（这个在path\_init这个函数在填充nd的path时候填充好了），nd中的last设置为当前的文件，。name\[len\]访问待查找路径中的下一个分量，判断如果下一个分量的第一个字符是空的，表示当前的文件是带查找路径的最后一个分量。跳过两个分量中间的斜线（这里和开始的时候相似，有可能用户输入了多个斜线），跳过以后再进行一次前面的判断。如果不空，name指针就指向下一个分量的开始位置（注意这里len并不是第一个分量的长度了，应该是前一个分量加上一个或者多个斜线），为下一次循环做准备。**这里要注意修改name指针的时候，必须要确定后指针移动后指向的空间是可以访问的，在最高特权级下访问了不该访问的内存是一个不可挽回的错误**。

捋一下，刚才的过程大概就是“走过”路径的第一个分量，如果路径以.或者..开头，设置nd的type成员是对应的类型。如果path是以/开始的，跳过前面的不止一个/，访问完第一个分量（访问是指根据该分量的信息填充nd的last和last\_type成员），name指针指向下一个分量。

现在我们已经知道了name此时指向的空间存储的是一个中间分量，调用walk\_component“走过这个节点”，walk\_component定义如下：

static inline int walk_component(struct nameidata *nd, struct path *path,
            int follow)
    {
        struct inode *inode;
        int err;
    
        if (unlikely(nd->last_type != LAST_NORM))
            return handle_dots(nd, nd->last_type);
    
        //填充path结构体,在rcuwalk模式下，
        err = lookup_fast(nd, path, &inode);
        if (unlikely(err)) {
            if (err < 0)
                goto out_err;
    
            err = lookup_slow(nd, path);
            if (err < 0)
                goto out_err;
                inode = path->dentry->d_inode;
        }

在遍历的时候我们看到了，子目录被分成三种情况，.目录或者..目录、普通目录或者一个符号链接。在walk\_component函数开始的时候就判断了是不是.目录或者..目录，如果是执行handle\_dots,这个函数不展开分析了，大概执行的功能是：如果是.目录就直接返回0，如果是..目录表示要走进父目录，返回的时候，nd结构体已经“站在了”父目录上（nd结构体中填充的是父目录的信息）。  
如果当前的目录是一个普通目录，我们前面说了路径行走有两个策略：先在效率高的rcu-walk模式下“行走”，如果失败了就在效率较低的ref-walk模式下“行走。lookshihouup\_fast函数应该就是指的两个查找策略，先调用lookup\_fast，当返回值大于0的时候，才会调用lookup\_slow函数当我们先来分析lookup\_fast（rcu-walk模式），这里有必要澄清一下，ref-walk模式并不是一定可以找到的，有可能也会失败。

static int lookup_fast(struct nameidata *nd,
                   struct path *path, struct inode **inode)
    {
    
        if (nd->flags & LOOKUP_RCU) {
            unsigned seq;
            //找到nameidata last的目录项,__d_lookup_rcu函数查找dentry必须要求拥有rcu锁
            dentry = __d_lookup_rcu(parent, &nd->last, &seq);
    
            //如果找到的dentry是空的，则进行切换到ref_mode模式进行再次查找
            if (!dentry)
                goto unlazy;
    
           *inode = dentry->d_inode;
            if (read_seqcount_retry(&dentry->d_seq, seq))
                return -ECHILD;
    
                    if (__read_seqcount_retry(&parent->d_seq, nd->seq))
                return -ECHILD;
            nd->seq = seq;
    
            if (unlikely(dentry->d_flags & DCACHE_OP_REVALIDATE)) {
                status = d_revalidate(dentry, nd->flags);
                if (unlikely(status <= 0)) {
                    if (status != -ECHILD)
                        need_reval = 0;
                    goto unlazy;
                }
            }
            path->mnt = mnt;
            path->dentry = dentry;
            if (unlikely(!__follow_mount_rcu(nd, path, inode)))
                goto unlazy;
    
            reurn 0；

调用\_\_d\_lookup\_rcu函数在哈希桶中找到对应的dentry（这是哪个dentry还记得吗？这个是name指向的那个目录分量的dentry），如果找到了就返回dentry，如果没找到就跳转到unlazy标记处（切换到ref-walk模式继续查找）。根据这个dentry得到对应的inode，进行一系列的检查操作，这样是为了确保在读取的时候，并没有其他进程对这些结构进行修改操作（rcu-walk模式并没有加锁），更新的临时变量path，这时候不能直接修改nd变量，因为不能确定这个分量是不是目录，nd记录的信息必须是目录，然后结束。  
其中有很多个跳转到unlazy标志的语句，我们前面说了，跳到unlazy标志表示rcu模式查找失败，用ref模式进行查找。ref模式的fast查找还是在内核缓冲区查找相应的dentry，和上述过程类似，这就不深入讲了。下来大概看看lookup\_slow函数：

static int lookup_slow(struct nameidata *nd, struct path *path)
    {
        ...
        mutex_lock(&parent->d_inode->i_mutex);
        dentry = __lookup_hash(&nd->last, parent, nd->flags);
        mutex_unlock(&parent->d_inode->i_mutex);
        ...
    }

看到这里，大家应该就明白了，为什么这种查找方法很慢呢，因为这种查找是互斥操作，进程可能会阻塞。而且lookup\_hash函数还是再会回到dcache中在找一遍，如果没有找到的话就调用文件系统自己的lookup函数从头开始找，所以这种方式比lookup\_fast方式比起来慢多了。  
看完了这两个lookup函数，我们还是回到walk\_component函数，剩下的也不多了。

if (should_follow_link(path->dentry, follow)) {
            if (nd->flags & LOOKUP_RCU) {
                if (unlikely(nd->path.mnt != path->mnt ||
                         unlazy_walk(nd, path->dentry))) {
                    err = -ECHILD;
                    goto out_err;
                }
            }
            BUG_ON(inode != path->dentry->d_inode);
            return 1;
        }
        path_to_nameidata(path, nd);
        nd->inode = inode;
        return 0;

询问是否需要跟踪符号链接，还记得我们之前说的分类吗？在路径行走的时候，子分量被分为三种：.开头的目录、普通目录和符号链接。如果这个自分量是符号链接，根据这个链接找到指向的目标文件，用目标文件替代该链接文件。如果这个分量不是符号链接，这时候我们可以确定这个分量就是一个普通的目录，根据path的值，填充nameidata，也就是nd变量。此时nd已经“站在”了子分量上，通过这样的递归调用，最终nd回“站在”最后一个目录上。  
到此路径名查找就结束了。