Linux 内核源代码情景分析（三）（中）：https://developer.aliyun.com/article/1597990
Ⓑ cached_lookup
// fs/namei.c /* * Internal lookup() using the new generic dcache. * SMP-safe */ static struct dentry * cached_lookup(struct dentry * parent, struct qstr * name, int flags) { struct dentry * dentry = d_lookup(parent, name); // 回到 cached_lookup() 的代码中，具体的文件系统可能通过其 dentry_operations 结构提供一个对找 // 到的dentry结构进行验证（和处理）的函数，如果验证失败就要通过 d_invalidate() 将这个数据结构从 // 杂凑队列中脱链，这种安排对有些文件系统是必要的，例如在 “网络文件系统” NFS中，如果一个远 // 程的进程是其惟一的用户，又有很长时间没有访问这个结构了，那就应该将其视作无效，而根据磁盘 // 上的父目录内容来重新构造。具体的函数由该文件系统的 dentry_operations 结构中通过函数指针 // d_revalidate 提供，最后则根据验证的结果返回一个dentry指针或出错代码。不过，有的文件系统根本 // 就不提供 dentry_operations 数据结构，所以其dentry结构中的d_op 是 0，表示按Linux默认的方式处 // 理各项目录项操作。事实上，Ext2 就不提供其自己的 dentry_operations 结构，因为Linux默认的方式就 // 是Ext2。进一步，即使某个文件系统提供了自己的dentry_operations数据结构，也并不一定提供自己 // 的 d_revalidate 操作。所以，代码中要先对这两个指针加以检验。由于Ext2并不提供其自己的 // dentry_operations结构，我们就把它跳过了。 // 至此，cached„lookup() 就完成了。 if (dentry && dentry->d_op && dentry->d_op->d_revalidate) { if (!dentry->d_op->d_revalidate(dentry, flags) && !d_invalidate(dentry)) { dput(dentry); dentry = NULL; } } return dentry; }
这里主要是通过 d_lookup() ，在杂凑表中寻找，其代码在 fs/dcache.c 中。
ⓐ d_lookup
// fs/dcache.c /** * d_lookup - search for a dentry * @parent: parent dentry * @name: qstr of name we wish to find * * Searches the children of the parent dentry for the name in question. If * the dentry is found its reference count is incremented and the dentry * is returned. The caller must use d_put to free the entry when it has * finished using it. %NULL is returned on failure. */ // 参数parent指向上一层节点的dentry结构，而name指向刚才在path_walk中建立的qstr结构。 struct dentry * d_lookup(struct dentry * parent, struct qstr * name) { unsigned int len = name->len; unsigned int hash = name->hash; const unsigned char *str = name->name; struct list_head *head = d_hash(parent,hash); struct list_head *tmp; spin_lock(&dcache_lock); tmp = head->next; for (;;) { struct dentry * dentry = list_entry(tmp, struct dentry, d_hash); if (tmp == head) break; tmp = tmp->next; if (dentry->d_name.hash != hash) continue; if (dentry->d_parent != parent) continue; if (parent->d_op && parent->d_op->d_compare) { if (parent->d_op->d_compare(parent, &dentry->d_name, name)) continue; } else { if (dentry->d_name.len != len) continue; if (memcmp(dentry->d_name.name, str, len)) continue; } __dget_locked(dentry); dentry->d_flags |= DCACHE_REFERENCED; spin_unlock(&dcache_lock); return dentry; } spin_unlock(&dcache_lock); return NULL; }
首先是要根据节点名的杂凑值从杂凑表中找到相应的队列指针，本来，以已经计算好的杂凑值作为下标从 list_head 指针数组 dentry_hashtable 中找到相应的表项是再简单不过的，可是这里（719行）还要通过一个函数 d_hash() 来做这件事，让我们来看看为什么：
// fs/dcache.c static inline struct list_head * d_hash(struct dentry * parent, unsigned long hash) { hash += (unsigned long) parent / L1_CACHE_BYTES; hash = hash ^ (hash >> D_HASHBITS) ^ (hash >> D_HASHBITS*2); return dentry_hashtable + (hash & D_HASHMASK); }
就是说，在已经根据节点名计算好的杂凑值基础上还要再进行一次杂凑，把父节点的 dentry 结构的地址也结合进杂凑值中。这无疑是很巧妙的做法。试想一下学校的计算机实验室，那里的系统可能为上百个学生分别在 /home 下面建立了子目录，而每个学生的子目录下可能都有子目录 “project1”。如果光是对节点名 “project1” 杂凑，则势必至少有上百个 dentry 结构都挂在同队列中而需要线性搜索。 即使把父节点名也一起杂凑还是解决不了问题，因为每个学生都可能会有例如 “projec1/src” ，所有此类路径中的 “src” 节点又会在同一个队列中，对全路径名进行杂凑当然可以解决问题，但是那样代价又太高了。
找到了相应的队列头部以后，d_lookup() 中的 for 循环是简单的。惟一特殊之处是具体的文件系统可能通过其 dentry_operalions 结构提供自己的节点名比对函数（比方说，有些文件系统可能在比对时跳过所有的空格），没有的话就用普通的 memcmp() 。
Ⓒ real_lookup
// fs/namei.c /* * This is called when everything else fails, and we actually have * to go to the low-level filesystem to find out what we should do.. * * We get the directory semaphore, and after getting that we also * make sure that nobody added the entry to the dcache in the meantime.. * SMP-safe */ static struct dentry * real_lookup(struct dentry * parent, struct qstr * name, int flags) { struct dentry * result; struct inode *dir = parent->d_inode; down(&dir->i_sem); /* * First re-do the cached lookup just in case it was created * while we waited for the directory semaphore.. * * FIXME! This could use version numbering or similar to * avoid unnecessary cache lookups. */ result = d_lookup(parent, name); if (!result) { struct dentry * dentry = d_alloc(parent, name); result = ERR_PTR(-ENOMEM); // 回到 real_lookup() 的代码中。分配了空间以后，就要从磁盘上由父节点代表的那个目录中寻找当 // 前节点的目录项并设置结构中的其他信息。如果寻找失败，就通过 dput() 撤销已经分配空间的 dentry // 结构。如果成功，就通过函数 real_lookup() 的295行的return语句返回指向该dentry结构的指针。 if (dentry) { lock_kernel(); // 从磁盘上寻找的过程因文件系统而异，所以要通过父节点 inode 结构中的指针 i_op 找到相应的 // inode_operations 数据结构。对于代表着目录的inode和代表着文件的 inode，其 // inode_operatians 结构常常是不同的。就 Ext2 而言，对于目录节点的函数跳转结构为 // ext2_dir_inode_operations，定义见 fs/ext2/namei.c result = dir->i_op->lookup(dir, dentry); unlock_kernel(); if (result) dput(dentry); else result = dentry; } up(&dir->i_sem); return result; } /* * Uhhuh! Nasty case: the cache was re-populated while * we waited on the semaphore. Need to revalidate. */ up(&dir->i_sem); if (result->d_op && result->d_op->d_revalidate) { if (!result->d_op->d_revalidate(result, flags) && !d_invalidate(result)) { dput(result); result = ERR_PTR(-ENOENT); } } return result; }
建立 dentry 结构的过程不容许受到其他进程的干扰，所以必须通过信号量放在临界区中进行。但是，在通过 down() 进入临界区时可能会经历一段睡眠等待的时间，而其他进程有可能已经在这段时间中把所需的 dentry 结构建立好，再建立一个就重复了。所以，在进入临界区以后，还要再通过 d_Iookup() 确认一下所需的 dentry 结构确实不在杂凑表队列中。读者在前面几章中也看到过类似的情况，总的来说，这是一种规范性的处理方式。万一真的发生了这种情况，那就根据具体文件系统的要求而（可能） 调用一个函数进行一些验证和处理（与 cached_Iookup() 中相似）。当然，发生这种情况的概率是很低的， 在多数情况下都需要建立 dentry 结构。
ⓐ d_alloc
要建立起一个 dentry 结构，首先当然要为之分配空间并初始化，这是由283行的 d_alloc() 完成的， 其代码在 dcache.c 中。
// fs/dcache.c /** * d_alloc - allocate a dcache entry * @parent: parent of entry to allocate * @name: qstr of the name * * Allocates a dentry. It returns %NULL if there is insufficient memory * available. On a success the dentry is returned. The name passed in is * copied and the copy passed in may be reused after this call. */ struct dentry * d_alloc(struct dentry * parent, const struct qstr *name) { char * str; struct dentry *dentry; dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL); if (!dentry) return NULL; if (name->len > DNAME_INLINE_LEN-1) { str = kmalloc(NAME_ALLOC_LEN(name->len), GFP_KERNEL); if (!str) { kmem_cache_free(dentry_cache, dentry); return NULL; } } else str = dentry->d_iname; memcpy(str, name->name, name->len); str[name->len] = 0; atomic_set(&dentry->d_count, 1); dentry->d_flags = 0; dentry->d_inode = NULL; dentry->d_parent = NULL; dentry->d_sb = NULL; dentry->d_name.name = str; dentry->d_name.len = name->len; dentry->d_name.hash = name->hash; dentry->d_op = NULL; dentry->d_fsdata = NULL; INIT_LIST_HEAD(&dentry->d_vfsmnt); INIT_LIST_HEAD(&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; spin_lock(&dcache_lock); list_add(&dentry->d_child, &parent->d_subdirs); spin_unlock(&dcache_lock); } else INIT_LIST_HEAD(&dentry->d_child); dentry_stat.nr_dentry++; return dentry; }
从这段程序中我们可以看到，dentry 数据结构是通过 kmem_alloc() 从为这种数据结构专设的 slab 队列中分配的。当节点名较短时，dentry 结构中有个字符数组 d_iname 用来保存节点名，不然就要另行为之分配空间。不管怎样，dentry 结构中的 d_name.name 总是指向这个字符串。此外，dentry 结构中指向超级块结构的指针 d_sb 是从其父节点（目录）继承下来的。每当建立了一个 dentry 结构时，就要将其父节点（ “/” 除外，它没有父节点）的共享计数通过 dget() 递增，所以这个新建的 dentry 结构就成了其父节点的 dentry 结构的一个"用户"，并且要挂入父节点的 d_subdirs 队列中。注意父节点的 d_subdirs 队列中只包含在内存中建有 dentry 结构的目录项。
ⓑ ext2_dir_inode_operations
// fs/ext2/namei.c /* * directories can handle most operations... */ struct inode_operations ext2_dir_inode_operations = { create: ext2_create, lookup: ext2_lookup, link: ext2_link, unlink: ext2_unlink, symlink: ext2_symlink, mkdir: ext2_mkdir, rmdir: ext2_rmdir, mknod: ext2_mknod, rename: ext2_rename, };
ⓒ ext2_lookup
// fs/ext2/namei.c static struct dentry *ext2_lookup(struct inode * dir, struct dentry *dentry) { struct inode * inode; struct ext2_dir_entry_2 * de; struct buffer_head * bh; if (dentry->d_name.len > EXT2_NAME_LEN) return ERR_PTR(-ENAMETOOLONG); bh = ext2_find_entry (dir, dentry->d_name.name, dentry->d_name.len, &de); inode = NULL; if (bh) { unsigned long ino = le32_to_cpu(de->inode); brelse (bh); // 回到ext2_lookup() 的代码中，下一步是根据查得的索引节点号通过iget() 找到或建立起所需的 // inode 结构，这里的 iget() 是个 inline 函数，定义于 indude/linux/fs.h: inode = iget(dir->i_sb, ino); if (!inode) return ERR_PTR(-EACCES); } d_add(dentry, inode); return NULL; }
这里先由 ext2_find_entry() 从磁盘上找到并读入当前节点的目录项，然后通过 iget() 根据索引节点号从磁盘读入相应索引节点并在内存中建立起相对的 inode 结构，最后，由 d_add 完成 dentry 结构的设置并将其挂入杂凑表中的某个队列。
ⓓ ext2_find_entry
函数 ext2_find_entry() 的代码也在 fs/ext2/namei.c 中。
// fs/ext2/namei.c /* * ext2_find_entry() * * finds an entry in the specified directory with the wanted name. It * returns the cache buffer in which the entry was found, and the entry * itself (as a parameter - res_dir). It does NOT read the inode of the * entry - you'll have to do that yourself if you want to. */ static struct buffer_head * ext2_find_entry (struct inode * dir, const char * const name, int namelen, struct ext2_dir_entry_2 ** res_dir) { struct super_block * sb; struct buffer_head * bh_use[NAMEI_RA_SIZE]; struct buffer_head * bh_read[NAMEI_RA_SIZE]; unsigned long offset; int block, toread, i, err; *res_dir = NULL; sb = dir->i_sb; if (namelen > EXT2_NAME_LEN) return NULL; memset (bh_use, 0, sizeof (bh_use)); toread = 0; for (block = 0; block < NAMEI_RA_SIZE; ++block) { struct buffer_head * bh; if ((block << EXT2_BLOCK_SIZE_BITS (sb)) >= dir->i_size) break; bh = ext2_getblk (dir, block, 0, &err); bh_use[block] = bh; if (bh && !buffer_uptodate(bh)) bh_read[toread++] = bh; } for (block = 0, offset = 0; offset < dir->i_size; block++) { struct buffer_head * bh; struct ext2_dir_entry_2 * de; char * dlimit; if ((block % NAMEI_RA_BLOCKS) == 0 && toread) { ll_rw_block (READ, toread, bh_read); toread = 0; } bh = bh_use[block % NAMEI_RA_SIZE]; if (!bh) { #if 0 ext2_error (sb, "ext2_find_entry", "directory #%lu contains a hole at offset %lu", dir->i_ino, offset); #endif offset += sb->s_blocksize; continue; } wait_on_buffer (bh); if (!buffer_uptodate(bh)) { /* * read error: all bets are off */ break; } de = (struct ext2_dir_entry_2 *) bh->b_data; dlimit = bh->b_data + sb->s_blocksize; while ((char *) de < dlimit) { /* this code is executed quadratically often */ /* do minimal checking `by hand' */ int de_len; if ((char *) de + namelen <= dlimit && ext2_match (namelen, name, de)) { /* found a match - just to be sure, do a full check */ if (!ext2_check_dir_entry("ext2_find_entry", dir, de, bh, offset)) goto failure; for (i = 0; i < NAMEI_RA_SIZE; ++i) { if (bh_use[i] != bh) brelse (bh_use[i]); } *res_dir = de; return bh; } /* prevent looping on a bad block */ de_len = le16_to_cpu(de->rec_len); if (de_len <= 0) goto failure; offset += de_len; de = (struct ext2_dir_entry_2 *) ((char *) de + de_len); } brelse (bh); if (((block + NAMEI_RA_SIZE) << EXT2_BLOCK_SIZE_BITS (sb)) >= dir->i_size) bh = NULL; else bh = ext2_getblk (dir, block + NAMEI_RA_SIZE, 0, &err); bh_use[block % NAMEI_RA_SIZE] = bh; if (bh && !buffer_uptodate(bh)) bh_read[toread++] = bh; } failure: for (i = 0; i < NAMEI_RA_SIZE; ++i) brelse (bh_use[i]); return NULL; }
这段程序涉及文件的读操作，读者可以在学习了 “文件的读写” 一节以及本书下册 “设备驱动” 一章后再回过来仔细阅读，这里只作一些必要的说明。目录其实只是一种特殊格式的文件，就 Ext2 文件系统而言，目录文件的内容在概念上就是一个 ext2_dir_entry_2 结构数组（见前节），其目的仅在于根据节点名（最长可达 255 个字符）得到相应的索引节点号，所以从逻辑的角度讲是很简单的。为什么只是说 “概念上” 是 ext2_dir_entry_2 结构数组呢？因为实际上不是。前一节中讲过，ext2_dir_entry_2 结构的长度是不固定的（节点名可长达 255，但通常只是几个字符，而一个文件系统中也许有数万个目录项），结构中有个字段 rec_len 指明本结构的长度。既然不是固定长度的，就不能像真正的数组那样通过下标来计算出具体元素的位置，而只好采用线性搜索的办法（这是一个 “以时间换空间” 的例子）。 不过，为了避免因目录项跨磁盘记录块而造成处理上的不便，Ext2 文件系统在为目录项分配磁盘空间时不让跨记录块。如果一个记录块中剩下的空间已经不够就另起一个记录块。
不同的处理器在存取数据时在字节的排列次序上有所谓 “big ending” 和 “little ending" 之分。例 如，i386 就是 “little ending” 的处理器，它在存储一个 16 位数据 0x1234 时实际存储的却是 0x3412， 对于 32 位数据也与此类似。这里的索引节点号与记录长度都作为 32 位或 16 位无符号整数存储在磁盘上的，而同一磁盘既可以安装在采用 “ little ending ” 方式的 CPU 的机器上，也可能安装在采用 “ big ending " 方式的 CPU 的机器上，所以要选择一种形式作为标准。事实上，Ext2 采用的标准是 “little ending” ， 所以在使用存储在磁盘上大于 8 位的整数时要先通过 le32_to_cpu() 、le16_to_cpu() 等函数将这些数据从 “little ending” 形式转换成具体CPU所采用的形式。当然，在 i386 处理器上访问 Ext2 文件系统时这些函数实际上不作任何转换。
由于磁盘的物理特性，从磁盘读一个记录块需要一定的时间，而这些时间主要消耗在准备工作上。 一旦准备好了，读一个记录块修读几个记录块所需时间其实相差不大。所以比较好的办法是既然读了就往前 “预读” （Read Ahead）一些记录块，因为紧接着的这些记录块很可能马上就要用到。另一方面， 从磁盘读记录块的操作一经启动便由磁盘自行完成，而无需 CPU 介入。所以，从读的第一批记录块到位以后，CPU 对记录块的处理就可以跟后续记录块的读入相平行，从而形成流水操作。那么往前多少块比较合适呢？那要看具体情况了，对于从磁盘读入目录内容这个特定的目的，代码中定义了几个常数（见文件 ext2/namei.c ）：
// fs/ext2/namei.c /* * define how far ahead to read directories while searching them. */ #define NAMEI_RA_CHUNKS 2 #define NAMEI_RA_BLOCKS 4 #define NAMEI_RA_SIZE (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS) #define NAMEI_RA_INDEX(c,b) (((c) * NAMEI_RA_BLOCKS) + (b))
所以，预读的提前量为 8 个记录块，也就是说，估计在读入一个记录块所需的时间内 CPU 可以处理 8 个记录块。
对于从磁盘读入的记录块都要在前面加上一个头部，即 buffer_head 数据结构以便管理。由于从磁盘读入一个记录块的代价不小，对已经读入的记录块都不是用了即扔的，而是要在内存中加以缓冲存储。所以，有时候并不需要真的到磁盘上去读。但是，这样一来有时候缓冲存储着的记录块与磁盘上的记录块就可能不一致了。
代码中为记录块设置了两个指针数组，一个是 bh_use[]，另一个是 bh_read[]，大小都是 NAMEI_RA_SIZE，即 8 。首先通过一个 for 循环，调用 ext2_getblk() 从缓冲着的记录块中找到给定目录文件的开头 8 个逻辑记录块，或者就为之分配缓冲区，并将它们的 buffer_head 结构指针写入数组 bh_use[]，将 bh_use[] 填满。这就是要搜索的第一批次。当然，如果这个目录文件的大小还不够 8 个记录块（见78行）那又另作别论（注意，参数 dir 指向其 inode 结构，而不是 dentry 结构）。在这 8 个记录块中，如果有的已经与磁盘上不一致（见85行），则要在另一个数组 bh_read[] 中记录下来，这就是真正要从磁盘上读的。至于新分配的缓冲区，那当然与磁盘上不一致。
接着是对目录文件中所有记录块的 for 循环，对目标节点的搜索就是扫描所有记录块中的所有目录项。循环从 block 0 开始，每隔 NAMEI_RA_BLOCKS 个就启动一次读磁盘操作（如果需要的话），每次最多读 8 块，而数组 bh_read[] 则给出所需记录块的 “名单”。第一次把 8 个缓冲区填满以后，再往后的从磁盘读入与CPU的处理就可以形成一种流水线式的操作了。由于从磁盘读入是异步的，CPU 在每处理一个记录块之前都要通过 wait_on_buffer() 等待该记录块到位。但是只要预读的参数合适就可以达到基本上不需要什么等待的程度。
至于在记录块中搜索的过程，那就很简单了（见116~144行）。虽然 Ext2 的目录项是可变大小的， 但是却不会跨记录块存储，所以每个记录块的开始必然也是一个目录项的开始（见116行），而一个记录块内有几个目录项那就不一定了。在找到了所需的目录项以后，要将其他的记录块缓冲区释放，只留下该目录项所在的那个记录块（见130〜133行）。最后返回目录项所在的记录块，并通过参数 res_dir 返回目录项指针。
