Linux虚拟文件系统（节点路径搜索）

[cpp]

1. static int path_walk(const char *name, struct nameidata *nd)  


2. {  


3.     current->total_link_count = 0;  


4.     return link_path_walk(name, nd);  


5. }  

[cpp]

1. /* 


2.  * Wrapper to retry pathname resolution whenever the underlying 


3.  * file system returns an ESTALE. 


4.  * 


5.  * Retry the whole path once, forcing real lookup requests 


6.  * instead of relying on the dcache. 


7.  */  


8. static __always_inline int link_path_walk(const char *name, struct nameidata *nd)  


9. {  


10.     struct path save = nd->path;  


11.     int result;  


12.   


13.     /* make sure the stuff we saved doesn’t go away */  


14.     path_get(&save);/*递增path的引用计数*/  


15.     /*实际的工作*/  


16.     result = __link_path_walk(name, nd);  


17.     if (result == -ESTALE) {  


18.         /* nd->path had been dropped */  


19.         nd->path = save;  


20.         path_get(&nd->path);  


21.         nd->flags |= LOOKUP_REVAL;  


22.         result = __link_path_walk(name, nd);  


23.     }  


24.   


25.     path_put(&save);  


26.   


27.     return result;  


28. }  

[cpp]

1. /* 


2.  * Name resolution. 


3.  * This is the basic name resolution function, turning a pathname into 


4.  * the final dentry. We expect ‘base’ to be positive and a directory. 


5.  * 


6.  * Returns 0 and nd will have valid dentry and mnt on success. 


7.  * Returns error and drops reference to input namei data on failure. 


8.  */  


9. static int __link_path_walk(const char *name, struct nameidata *nd)  


10. {  


11.     struct path next;  


12.     struct inode *inode;  


13.     int err;  


14.     unsigned int lookup_flags = nd->flags;  


15.     /*如果路径名以’/’开头，就把他跳过去，因为在这种情况下nd中 


16.     path已经指向本进程的根目录了，注意，这里多个连续的’/’与一个 


17.     ‘/’是等价的，如果路径名中仅仅包含有’/’字符的话，那么其 


18.     目标就是根目录，所以任务完成，不然需要继续搜索*/  


19.     while (*name==‘/’)  


20.         name++;  


21.     if (!*name)  


22.         goto return_reval;  


23.     /*作为path_walk起点的节点必定是一个目录，一定有相应的索引节点 


24.     存在，所以指针inode一定是有效的，而不可能是空指针*/  


25.     inode = nd->path.dentry->d_inode;  


26.     /*进程的task_struct结构中有个计数器link_count.在搜索过程中有可能 


27.     碰到一个节点(目录项)只是指向另一个节点的链接，此时就用这个计数器来对 


28.     链的长度进行计数，这样，当链的长度达到某一个值时就可以终止搜索而失败 


29.     返回，以防陷入循环。另一方面，当顺着符号链接进入另一个设备上的文件系统 


30.     时，有可能会递归地调用path_walk。所以，进入path_walk后，如果发现这个 


31.     计数器值非0，就表示正在顺着符号链接递归调用path_walk往前搜索过程中， 


32.     此时不管怎样都把LOOKUP_FOLLOW标志位设成1.*/  


33.     if (nd->depth)  


34.         lookup_flags = LOOKUP_FOLLOW | (nd->flags & LOOKUP_CONTINUE);  


35.   


36.     /* At this point we know we have a real path component. */  


37.     for(;;) {  


38.         unsigned long hash;  


39.           


40.         struct qstr this;  


41.         unsigned int c;  


42.   


43.         nd->flags |= LOOKUP_CONTINUE;  


44.         /*检查当前进程对当前节点的访问权限，这里所检查的是相对路径中 


45.         的各层目录(而不是目标文件)的访问权限。注意，对于中间节点所需 


46.         的权限为执行权，即MAY_EXEC*/  


47.              err = exec_permission_lite(inode);  


48.         if (err)  


49.             break;  


50.   


51.         this.name = name;  


52.         c = *(const unsigned char *)name;  


53.   


54.         hash = init_name_hash();  


55.         do {  


56.             name++;  


57.             hash = partial_name_hash(c, hash);  


58.             c = *(const unsigned char *)name;  


59.         } while (c && (c != ‘/’));/*路径名中的节点定以‘/’字符分开的，*/  


60.         this.len = name – (const char *) this.name;  


61.         this.hash = end_name_hash(hash);  


62.   


63.         /* remove trailing slashes? */  


64.         if (!c)/*最后一个字符为’\0′,就是说当前节点已经是路径名中的最后一节*/  


65.             goto last_component;/*跳转*/  


66.         /*循环跳过’/’*/  


67.         while (*++name == ‘/’);  


68.         /*当前节点实际上已经是路径名的最后一个节点，只不过在此后面又多添加了 


69.         若干个’/’字符，这种情况常常发生在用户界面上，特别是在shell的命令中 


70.         当然这种情况要求最后的节点必须是个目录*/  


71.         if (!*name)  


72.             goto last_with_slashes;/*跳转*/  


73.   


74.             /*运行到这里，表示当前节点为中间节点，所以’/’字符后面还有其他字符*/  


75.         /* 


76.          * “.” and “..” are special – “..” especially so because it has 


77.          * to be able to know about the current root directory and 


78.          * parent relationships. 


79.          */  


80.          /*以’.’开头表示这是个隐藏的文件，而对于代表着目录的节点则只有在两种 


81.          情况下才是允许的。一种是节点名为’.’,表示当前目录，另一种是’..’,表示 


82.          当前目录的父目录*/  


83.         if (this.name[0] == ‘.’) switch (this.len) {  


84.             default:  


85.                 break;  


86.             case 2:   


87.                 if (this.name[1] != ‘.’)  


88.                     break;  


89.                 follow_dotdot(nd);/*为’..’，到父目录中去*/  


90.                 inode = nd->path.dentry->d_inode;  


91.                 /* fallthrough */  


92.             /*2中没有break语句，也就是所继续执行1中的语句， 


93.             将会跳到for语句的开头处理路径中的下一个节点*/  


94.             case 1:  


95.                 continue;  


96.         }  


97.         /* 


98.          * See if the low-level filesystem might want 


99.          * to use its own hash.. 


100.          */  


101.          /*特定文件系统提供他自己专用的杂凑函数，所以在这种情况下就通过这个 


102.          函数再计算一遍当前节点的杂凑值*/  


103.         if (nd->path.dentry->d_op && nd->path.dentry->d_op->d_hash) {  


104.             err = nd->path.dentry->d_op->d_hash(nd->path.dentry,  


105.                                 &this);  


106.             if (err < 0)  


107.                 break;  


108.         }  


109.         /* This does the actual lookups.. */  


110.         /*实际的搜索工作*/  


111.              err = do_lookup(nd, &this, &next);  


112.         if (err)  


113.             break;  


114.   


115.         err = -ENOENT;  


116.         inode = next.dentry->d_inode;  


117.         if (!inode)  


118.             goto out_dput;  


119.         /*涉及到具体文件系统的相关操作*/  


120.         if (inode->i_op->follow_link) {  


121.             err = do_follow_link(&next, nd);  


122.             if (err)  


123.                 goto return_err;  


124.             err = -ENOENT;  


125.             inode = nd->path.dentry->d_inode;  


126.             if (!inode)  


127.                 break;  


128.         } else/*将path中的相关内容转化到nd中*/  


129.             path_to_nameidata(&next, nd);  


130.         err = -ENOTDIR;   


131.         if (!inode->i_op->lookup)  


132.             break;  


133.         continue;  


134.         /* here ends the main loop */  


135.   


136. last_with_slashes:  


137.         lookup_flags |= LOOKUP_FOLLOW | LOOKUP_DIRECTORY;  


138. last_component:  


139.         /* Clear LOOKUP_CONTINUE iff it was previously unset */  


140.         nd->flags &= lookup_flags | ~LOOKUP_CONTINUE;  


141.         if (lookup_flags & LOOKUP_PARENT)/*要寻找的不是路径终点，而是他的上一层*/  


142.             goto lookup_parent;  


143.         if (this.name[0] == ‘.’) switch (this.len) {  


144.             default:  


145.                 break;  


146.             case 2:   


147.                 if (this.name[1] != ‘.’)  


148.                     break;  


149.                 follow_dotdot(nd);/*向上层移动*/  


150.                 inode = nd->path.dentry->d_inode;  


151.                 /* fallthrough */  


152.             case 1:  


153.                 goto return_reval;  


154.         }  


155.         /*具体文件系统的操作*/  


156.         if (nd->path.dentry->d_op && nd->path.dentry->d_op->d_hash) {  


157.             err = nd->path.dentry->d_op->d_hash(nd->path.dentry,  


158.                                 &this);  


159.             if (err < 0)  


160.                 break;  


161.         }/*顺次查找路径节点，下一个存放在next中*/  


162.         err = do_lookup(nd, &this, &next);  


163.         if (err)  


164.             break;  


165.         inode = next.dentry->d_inode;  


166.         if ((lookup_flags & LOOKUP_FOLLOW)/*当终点为符号链接时*/  


167.             && inode && inode->i_op->follow_link) {  


168.             err = do_follow_link(&next, nd);  


169.             if (err)  


170.                 goto return_err;  


171.             inode = nd->path.dentry->d_inode;  


172.         } else  


173.             /*path转化为nd*/  


174.             path_to_nameidata(&next, nd);  


175.         err = -ENOENT;  


176.         if (!inode)  


177.             break;  


178.         if (lookup_flags & LOOKUP_DIRECTORY) {  


179.             err = -ENOTDIR;   


180.             if (!inode->i_op->lookup)  


181.                 break;  


182.         }  


183.         goto return_base;  


184. lookup_parent:  


185.         nd->last = this;  


186.         nd->last_type = LAST_NORM;/*根据终点节点名设置*/  


187.         if (this.name[0] != ‘.’)  


188.             goto return_base;  


189.         if (this.len == 1)  


190.             nd->last_type = LAST_DOT;  


191.         else if (this.len == 2 && this.name[1] == ‘.’)  


192.             nd->last_type = LAST_DOTDOT;  


193.         else  


194.             goto return_base;  


195. return_reval:  


196.         /* 


197.          * We bypassed the ordinary revalidation routines. 


198.          * We may need to check the cached dentry for staleness. 


199.          */  


200.         if (nd->path.dentry && nd->path.dentry->d_sb &&  


201.             (nd->path.dentry->d_sb->s_type->fs_flags & FS_REVAL_DOT)) {  


202.             err = -ESTALE;  


203.             /* Note: we do not d_invalidate() */  


204.             if (!nd->path.dentry->d_op->d_revalidate(  


205.                     nd->path.dentry, nd))  


206.                 break;  


207.         }  


208. return_base:  


209.         return 0;  


210. out_dput:  


211.         path_put_conditional(&next, nd);  


212.         break;  


213.     }  


214.     path_put(&nd->path);  


215. return_err:  


216.     return err;  


217. }  

2.2.1 处理double dot

所谓double dot为访问上层目录

[cpp]

1. static __always_inline void follow_dotdot(struct nameidata *nd)  


2. {  


3.     set_root(nd);  


4.   


5.     while(1) {  


6.         struct vfsmount *parent;  


7.         struct dentry *old = nd->path.dentry;  


8.         /*如果已经达到本进程的根节点，这时不能再往上跑了 


9.         所以保持不变*/  


10.         if (nd->path.dentry == nd->root.dentry &&  


11.             nd->path.mnt == nd->root.mnt) {  


12.             break;  


13.         }  


14.         spin_lock(&dcache_lock);  


15.             /*已经到达节点与其父节点在同一个设备上。在这种情况下 


16.             既然已经到达的这个节点的dentry结构已经建立，则其父节点的 


17.             dentry结构也必然已经建立在内存中，而且dentry结构中的指针 


18.             d_parent就指向其父节点，所以往上跑一层是很简单的事情*/  


19.         if (nd->path.dentry != nd->path.mnt->mnt_root) {  


20.             nd->path.dentry = dget(nd->path.dentry->d_parent);/*往上走一层，并且对应用计数加一*/  


21.             spin_unlock(&dcache_lock);  


22.             dput(old);/*释放就得目录的引用*/  


23.             break;  


24.         }  


25.         spin_unlock(&dcache_lock);  


26.         spin_lock(&vfsmount_lock);  


27.             /*运行到这里，表示已经到达节点就是其所在设备上的根节点 


28.             往上跑一层就要跑到另一个设备上去了,当将一个存储设备安装到 


29.             另一个设备上的某个节点时，内核会分配和设置一个vfsmount 


30.             结构，通过这个结构将两个设备以及两个节点连接起来。 


31.             所以，每个已经安装的存储设备都有一个vfsmount结构，结构 


32.             中有个指针mnt_parent指向其父设备，另一个指针mnt_mountpoint 


33.             指向代表这安装点的dentry结构*/  


34.         /*保存nd指定的mnt的父mnt*/  


35.         parent = nd->path.mnt->mnt_parent;  


36.              /*当前的vfsmount结构代表这跟设备*/  


37.         if (parent == nd->path.mnt) {  


38.             spin_unlock(&vfsmount_lock);  


39.             break;  


40.         }  


41.           /*当前设备不是跟设备*/  


42.           


43.         mntget(parent);  


44.         /*指向该设备上的安装点的上一层目录*/          


45.         nd->path.dentry = dget(nd->path.mnt->mnt_mountpoint);  


46.         spin_unlock(&vfsmount_lock);  


47.         dput(old);  


48.         mntput(nd->path.mnt);  


49.         nd->path.mnt = parent;/*指向上层设备上的vfsmount 结构*/  


50.     }  


51.     follow_mount(&nd->path);/*mnt向子节点移动一个*/  


52. }  

[cpp]

1. static void follow_mount(struct path *path)  


2. {  


3.     while (d_mountpoint(path->dentry)) {/*如果该文件系统已经安装*/  


4.         /*找到指定的孩子mnt*/   


5.         struct vfsmount *mounted = lookup_mnt(path);  


6.         if (!mounted)/*如果没有孩子mnt了*/  


7.             break;  


8.         /*递减引用计数*/  


9.         dput(path->dentry);  


10.         mntput(path->mnt);  


11.         path->mnt = mounted;/*找到的mnt作为path的mnt*/  


12.         path->dentry = dget(mounted->mnt_root);/*递增引用计数，将找到的mnt文件系统的根目录赋给path*/  


13.     }  


14. }  

2.2.2 实际的路径搜索工作

[cpp]

1. /* 


2.  *  It’s more convoluted than I’d like it to be, but… it’s still fairly 


3.  *  small and for now I’d prefer to have fast path as straight as possible. 


4.  *  It _is_ time-critical. 


5.  */  


6. static int do_lookup(struct nameidata *nd, struct qstr *name,  


7.              struct path *path)  


8. {  


9.     struct vfsmount *mnt = nd->path.mnt;  


10.     /*在内存中寻找该节点已经建立的dentry结构。内核中有个hash表dentry_hashtable 


11.     是一个list_head指针数组，一旦在内存中建立起一个目录节点的dentry结构 


12.     就根据其节点名的hash值挂入hash表中的某个队列，需要寻找时则还是根据hash值从 


13.     hash表着手*/  


14.     struct dentry *dentry = __d_lookup(nd->path.dentry, name);  


15.   


16.     if (!dentry)/*如果没有找到,转向下面*/  


17.         goto need_lookup;  


18.     if (dentry->d_op && dentry->d_op->d_revalidate)  


19.         goto need_revalidate;  


20. done:/*内存中找到了dentry*/  


21.     path->mnt = mnt;  


22.     path->dentry = dentry;  


23.     /*访问下一个mnt，其实就是现在mnt的子mnt*/  


24.     __follow_mount(path);  


25.     return 0;  


26.   


27. need_lookup:/*到这里是在内存中没有找到dentry结构*/  


28.      /*到磁盘上通过其所在的目录寻找，找到后在内存中为其建立起 


29.      dentry结构并将之挂入hash表中某个队列中*/  


30.     dentry = real_lookup(nd->path.dentry, name, nd);  


31.     if (IS_ERR(dentry))  


32.         goto fail;  


33.     goto done;  


34.   


35. need_revalidate:  


36.     dentry = do_revalidate(dentry, nd);  


37.     if (!dentry)  


38.         goto need_lookup;  


39.     if (IS_ERR(dentry))  


40.         goto fail;  


41.     goto done;  


42.   


43. fail:  


44.     return PTR_ERR(dentry);  


45. }  

[cpp]

1. /* 


2.  * This is called when everything else fails, and we actually have 


3.  * to go to the low-level filesystem to find out what we should do.. 


4.  * 


5.  * We get the directory semaphore, and after getting that we also 


6.  * make sure that nobody added the entry to the dcache in the meantime.. 


7.  * SMP-safe 


8.  */  


9. static struct dentry * real_lookup(struct dentry * parent, struct qstr * name, struct nameidata *nd)  


10. {  


11.     struct dentry * result;  


12.     struct inode *dir = parent->d_inode;  


13.   


14.     mutex_lock(&dir->i_mutex);  


15.     /* 


16.      * First re-do the cached lookup just in case it was created 


17.      * while we waited for the directory semaphore.. 


18.      * 


19.      * FIXME! This could use version numbering or similar to 


20.      * avoid unnecessary cache lookups. 


21.      * 


22.      * The “dcache_lock” is purely to protect the RCU list walker 


23.      * from concurrent renames at this point (we mustn’t get false 


24.      * negatives from the RCU list walk here, unlike the optimistic 


25.      * fast walk). 


26.      * 


27.      * so doing d_lookup() (with seqlock), instead of lockfree __d_lookup 


28.      */  


29.     result = d_lookup(parent, name);  


30.     if (!result) {  


31.         struct dentry *dentry;  


32.   


33.         /* Don’t create child dentry for a dead directory. */  


34.         result = ERR_PTR(-ENOENT);  


35.         if (IS_DEADDIR(dir))  


36.             goto out_unlock;  


37.         /*从slab中分配dentry并且初始化*/  


38.         dentry = d_alloc(parent, name);  


39.         result = ERR_PTR(-ENOMEM);  


40.         if (dentry) {  


41.                     /*调用具体文件系统的loopup函数*/  


42.             result = dir->i_op->lookup(dir, dentry, nd);  


43.             if (result)  


44.                 dput(dentry);  


45.             else  


46.                 result = dentry;  


47.         }  


48. out_unlock:  


49.         mutex_unlock(&dir->i_mutex);  


50.         return result;  


51.     }  


52.   


53.     /* 


54.      * Uhhuh! Nasty case: the cache was re-populated while 


55.      * we waited on the semaphore. Need to revalidate. 


56.      */  


57.     mutex_unlock(&dir->i_mutex);  


58.     if (result->d_op && result->d_op->d_revalidate) {  


59.         result = do_revalidate(result, nd);  


60.         if (!result)  


61.             result = ERR_PTR(-ENOENT);  


62.     }  


63.     return result;  


64. }  

2.2.2.1 分配dentry并且初始化

[cpp]

1. struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)  


2. {  


3.     struct dentry *dentry;  


4.     char *dname;  


5.     /*从slab中非配dentry*/  


6.     dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);  


7.     if (!dentry)  


8.         return NULL;  


9.   


10.     if (name->len > DNAME_INLINE_LEN-1) {  


11.         dname = kmalloc(name->len + 1, GFP_KERNEL);  


12.         if (!dname) {  


13.             kmem_cache_free(dentry_cache, dentry);   


14.             return NULL;  


15.         }  


16.     } else  {  


17.         dname = dentry->d_iname;  


18.     }  


19.         /*初始化非配的dentry结构*/  


20.     dentry->d_name.name = dname;  


21.   


22.     dentry->d_name.len = name->len;  


23.     dentry->d_name.hash = name->hash;  


24.     memcpy(dname, name->name, name->len);  


25.     dname[name->len] = 0;  


26.   


27.     atomic_set(&dentry->d_count, 1);  


28.     dentry->d_flags = DCACHE_UNHASHED;  


29.     spin_lock_init(&dentry->d_lock);  


30.     dentry->d_inode = NULL;  


31.     dentry->d_parent = NULL;  


32.     dentry->d_sb = NULL;  


33.     dentry->d_op = NULL;  


34.     dentry->d_fsdata = NULL;  


35.     dentry->d_mounted = 0;  


36.     INIT_HLIST_NODE(&dentry->d_hash);  


37.     INIT_LIST_HEAD(&dentry->d_lru);  


38.     INIT_LIST_HEAD(&dentry->d_subdirs);  


39.     INIT_LIST_HEAD(&dentry->d_alias);  


40.   


41.     if (parent) {  


42.         dentry->d_parent = dget(parent);  


43.         dentry->d_sb = parent->d_sb;  


44.     } else {  


45.         INIT_LIST_HEAD(&dentry->d_u.d_child);  


46.     }  


47.   


48.     spin_lock(&dcache_lock);  


49.     if (parent)  


50.         list_add(&dentry->d_u.d_child, &parent->d_subdirs);  


51.     dentry_stat.nr_dentry++;  


52.     spin_unlock(&dcache_lock);  


53.   


54.     return dentry;  


55. }  

从上面的代码中可以看到，linux内核中的路径搜索大体工作如下：

1，初始化查询，设置nd结构指向查询开始处的文件；

2，从起点开始路径的搜索，其中nd用来返回搜索结果，在搜索过程中需要根据路径名称一步一步的访问，包括字符‘/‘的处理、访问上层目录的处理（需要考虑超出本文件系统）以及访问的dentry在内存中不存在需要从新分配的情况等；

程序返回后，参数中的nd结构保存了当前的搜索结果信息，包括目标文件或目录的dentry结构和inode结构。