Linux虛擬文件系統（節點路徑搜索）

前面（見 http://www.linuxidc.com/Linux/2012-02/53694.htm ）對linux虛擬文件系統的架構以及設計到的數據結構有了一個整體的認識，這裡看看linux內核怎麼根據給定的文件路徑名在內存中找到和建立代表著目標文件或目錄的dentry結構和inode結構。文件路徑的搜索是文件系統中最基本也是最重要的一部分之一，後面我們會看到，文件的打開、關閉等等操作都將涉及到文件路徑的搜索。下面我們看看linux內核中時怎麼實現的。

一、搜索中所用數據結構

1. /*這個數據結構是臨時的，只在路徑搜索的過程中返回搜索的結果。 
2. */  
3. struct nameidata {  
4.     struct path path;/*將目錄結構和mount結構封裝在path結構中*/  
5.     struct qstr last;  
6.     struct path root;  
7.     unsigned int    flags;/*對應搜索的標志*/  
8.     int     last_type;  
9.     unsigned    depth;  
10.     char *saved_names[MAX_NESTED_LINKS + 1];  
11.   
12.     /* Intent data */  
13.     union {  
14.         struct open_intent open;  
15.     } intent;  
16. };  

1. /*用來存放路徑名中當前節點的雜湊值以及節點名的長度*/  
2. struct qstr {  
3.     unsigned int hash;  
4.     unsigned int len;  
5.     const unsigned char *name;  
6. };  

二、搜索

1. /*name指向在用戶空間的路徑名; 
2. flag為一些標志位，nd為搜索返回值 
3. */  
4. int path_lookup(const char *name, unsigned int flags,  
5.             struct nameidata *nd)  
6. {  
7.     return do_path_lookup(AT_FDCWD, name, flags, nd);  
8. }  

實際工作都是由上面的do_path_lookup()函數實現的，在這裡我們就他進行分析。

1. /* Returns 0 and nd will be valid on success; Retuns error, otherwise. */  
2. static int do_path_lookup(int dfd, const char *name,  
3.                 unsigned int flags, struct nameidata *nd)  
4. {   /*找到搜索的起點，保存在nd中*/  
5.     int retval = path_init(dfd, name, flags, nd);  
6.     if (!retval)  
7.             /*一旦找到了搜索的起點，從起點開始路徑的搜索 
8.         其中nd用來返回搜索結果*/  
9.         retval = path_walk(name, nd);  
10.     if (unlikely(!retval && !audit_dummy_context() && nd->path.dentry &&  
11.                 nd->path.dentry->d_inode))  
12.         audit_inode(name, nd->path.dentry);  
13.     if (nd->root.mnt) {  
14.         path_put(&nd->root);  
15.         nd->root.mnt = NULL;  
16.     }  
17.     return retval;  
18. }  

2.1 初始化階段

初始化階段是由函數path_init()函數實現

1. /*path_init主要是初始化查詢，設置nd結構指向查詢開始處的文件，這裡分兩種情況： 
2.     a，絕對路徑(以／開始)，獲得根目錄的dentry。它存儲在task_struct中fs指向的fs_struct結構中。 
3.     b，相對路徑，直接從當前進程task_struct結構中的獲得指針fs，它指向的一個fs_struct， 
4.     fs_struct中有一個指向“當前工作目錄”的dentry。 
5. */  
6. static int path_init(int dfd, const char *name, unsigned int flags, struct nameidata *nd)  
7. {  
8.     int retval = 0;  
9.     int fput_needed;  
10.     struct file *file;  
11.     /*在搜索的過程中，這個字段的值會隨著路徑名當前搜索結果而變； 
12.     例如，如果成功找到目標文件，那麼這個字段的值就變成了LAST_NORM 
13.     而如果最後停留在了一個.上，則變成LAST_DOT(*/  
14.     nd->last_type = LAST_ROOT; /* if there are only slashes... */  
15.     nd->flags = flags;  
16.     nd->depth = 0;  
17.     nd->root.mnt = NULL;  
18.   
19.     if (*name=='/') {/*路徑名以'/'開頭*/  
20.         set_root(nd);/*設置nd的root為當前進程fs的root*/  
21.         nd->path = nd->root;/*保存根目錄*/  
22.         path_get(&nd->root);/*遞增引用計數*/  
23.     } else if (dfd == AT_FDCWD) {/*相對路徑*/  
24.         struct fs_struct *fs = current->fs;  
25.         read_lock(&fs->lock);  
26.         nd->path = fs->pwd;/*保存當前路徑*/  
27.         path_get(&fs->pwd);/*遞增引用計數*/  
28.         read_unlock(&fs->lock);  
29.     } else {/*???*/  
30.         struct dentry *dentry;  
31.          /*fget_light在當前進程的struct files_struct中根據所謂的用戶空間 
32.         文件描述符fd來獲取文件描述符。另外，根據當前fs_struct 
33.         是否被多各進程共享來判斷是否需要對文件描述符進行加 
34.          鎖，並將加鎖結果存到一個int中返回 
35.         */  
36.         file = fget_light(dfd, &fput_needed);  
37.         retval = -EBADF;  
38.         if (!file)  
39.             goto out_fail;  
40.   
41.         dentry = file->f_path.dentry;  
42.   
43.         retval = -ENOTDIR;  
44.         if (!S_ISDIR(dentry->d_inode->i_mode))  
45.             goto fput_fail;  
46.         /*權限檢查*/  
47.         retval = file_permission(file, MAY_EXEC);  
48.         if (retval)  
49.             goto fput_fail;  
50.         /*獲得path*/  
51.         nd->path = file->f_path;  
52.         path_get(&file->f_path);  
53.         /*解鎖*/  
54.         fput_light(file, fput_needed);  
55.     }  
56.     return 0;  
57.   
58. fput_fail:  
59.     fput_light(file, fput_needed);  
60. out_fail:  
61.     return retval;  
62. }  

2.2 實際搜索操作

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. }  

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. }  

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. }