实现一个FUSE文件系统的时候，通常使用一个普通的文件系统作为backend filesystem。而fuse操作传入的参数是inode id。因此需要设计数据结构，将inode id映射到backend filesystem中的具体文件。同时要考虑支持hard link，支持move等文件操作。
fuse操作接口：
| 操作 | 参数 | 返回值 | 说明 |
| lookup | （ino, name） | attr | 查询目录下面的文件，返回文件的属性 ino是父目录的inode id name，是文件名 |
| forget | （ino, count） | void | 释放inode的引用计数 |
| getattr | ino | attr | 读取属性 |
| setattr | ino | attr | 设置属性 |
| readlink | ino | 读取符号链接的内容 | |
mknod mkdir create | (ino, name) | attr | 新建字符设备、目录、普通文件 |
unlink rmdir | (ino, name) | errno | 删除文件或目录 |
| symlink | (ino, name, linkname) | attr | 创建符号链接 |
| rename | (ino old, name old, ino new, name new) | errno | 移动文件或目录 |
| link | (ino, name, target ino) | errno | 创建hard link |
open opendir | ino | handle | 打开文件 |
从上述接口看出，只有两种操作：
1 涉及目录项的，包括创建、删除、查找文件或目录。都是父目录的inode id + 子文件（文件夹）名
2 涉及到具体文件或目录的，比如读取、设置属性，打开文件，都是inode id。
在文件系统里面，inode表示具体的文件，dentry表示目录项。因此我们就直接采用这个概念。
设计两个结构体，inode和dentry。inode id存在inode结构体中。文件名存在dentry结构体中。
inode表示fuse操作的对象，也是一个文件节点。dentry是这个inode在后备文件系统的目录。因此有了一个雏形：
struct inode {
uint64_t ino;
};
struct dentry {
char *name;
};
引入两个接口，新建inode和dentry：
struct inode *inode_new(uint64_t ino);
struct dentry *dentry_new(char *name);
fuse传入的参数是inode id，因此为了根据inode id快速找到inode，我们需要为inode id建立哈希表。这样inode的结构体就变成这样：
struct hlist_head *hash_head;
struct inode {
struct hlist_node hash;
uint64_t ino;
};
引入一个接口，根据inode id查找inode
struct inode *inode_find(uint64_t ino);
dentry存在的目的，是为了知道这个inode在backend filesystem中的路径。fuse不care这个dentry，它操作的对象是inode。
为了有效的组织dentry，dentry需要有个parent，组成一个树形结构。这样就可以算出一个dentry的路径。
同时inode也需要指向一个dentry，这样就把inode映射到后备文件系统中具体的文件了。这样结构体就变成：
struct inode {
struct hlist_node hash;
uint64_t ino;
struct dentry *dentry;
};
struct dentry {
char *name;
struct dentry *parent;
};
引入一个接口，计算dentry的路径：
char *dentry_path(struct dentry *dentry)
这样getattr、setattr、readlink、open、opendir，这样操作inode的，就都能实现了。以getattr为例。
int getattr(uint64_t ino, struct stat *statbuf)
{
// 1 根据inode id找到对应的inode
struct inode *inode = inode_find(ino);
// 2 根据inode的dentry可以计算出路径
char *path = dentry_path(inode->dentry);
// 3 在后备文件系统中统计属性即可
return stat(back_path(path), statbuf)
}
lookup是fuse内核感知已有文件的接口，它查找一个目录的子文件的inode信息。
接口定义：int lookup(uint64_t ino, char *name, struct stat *statbuf);
lookup找到子文件，获得属性后，将添加子文件的inode和dentry。
找子文件是简单的。跟上面的getattr类似，计算出父目录的path。然后path后跟个name，就得到子文件的路径了。
在后备文件系统中读取子文件的属性。得到子文件的inode id：ino2
添加过程
struct inode *sub_ino = inode_new(ino2);
struct inode *sub_dentry = dentry_new(name);
sub_ino->dentry = sub_dentry;
sub_dentry->parent = inode->dentry;
现在的问题是，对于相同的文件，我们不能重复添加，对于inode是简单的，因为我们有inode id的哈希索引。
可以找出旧的，如果旧的不存在，才添加新的。
struct inode *sub_ino = inode_find(ino2)
if (!sub_Ino)
sub_ino = inode_new(ino2);
对于dentry，情况变的复杂：
1 如果我们直接使用后备文件系统的inode id，且只有一个后备文件系统，且后备文件系统不会被fuse之外的地方修改。
那么问题就简化了。因为这种情况下，不考虑hard link，那么inode和dentry是一一对应的。
如果sub_ino找到了，那么对应的dentry就是我们要添加的dentry。dentry也可以直接不用添加了。可以确保dentry不会重复。
struct inode *sub_ino = inode_find(ino2)
if (!sub_Ino) {
sub_ino = inode_new(ino2);
struct inode *sub_dentry = dentry_new(name);
sub_ino->dentry = sub_dentry;
sub_dentry->parent = inode->dentry;
}
2 inode id会变或者动态分配的场景
比如我们第一次lookup目录a下的文件b。此时b的inode id是3，然后在fuse之外，删除b，再创建一个新的b，此时inode id是4。
如果此时再次lookup。我们find 4发现是空白。但是 b 这个dentry已经存在了，且id为3的inode也存在了。我们会创建一个新的b。
这样就有两个b了。对于访问新的b，是没问题的。问题是访问inode 3，将访问的是新的文件，这也不符合逻辑。
对于动态分配的场景，比如b是个目录，如果是第一次lookup，就分配一个inode id，后续就复用那个inode id。
因此这两种需求，都要我们能查找旧的dentry。因此就需要建立一个dentry的哈希索引。
索引的key是（parent, name）。这唯一标识了一个dentry。
对于inode id变化的情况，我们希望dentry对应的旧inode不可以再访问，返回ENOENT。
因此又需要得到dentry的inode。因此dentry添加两个字段，一个支持hash索引，一个支持获得dentry的inode。
这样结构体变成：
struct inode {
struct hlist_node hash;
uint64_t ino;
struct dentry *dentry;
};
struct dentry {
struct hlist_node hash;
char *name;
struct dentry *parent;
struct inode *inode;
};
引入新的接口
struct dentry *dentry_find(struct dentry *parent, char *name);
这样添加动作变成
struct inode *sub_ino = inode_find(ino2)
if (!sub_ino)
sub_ino = inode_new(ino2);
struct dentry *sub_dentry = dentry_find(inode->dentry, name)
if (sub_dentry) {
// 如果旧dentry的inode和现在的inode不同，将之前inode的dentry设置成NULL
if (sub_dentry->inode != sub_ino)
sub_dentry->inode->dentry = NULL;
}
else
sub_dentry = dentry_new(inode->dentry, name)
sub_dentry->inode = sub_ino;
sub_ino->dentry = sub_dentry
新建文件的操作和lookup是完全一样的，为新建的文件，添加inode和dentry。
删除文件夹，没有啥特别的，不需要额外的数据字段了。以删除文件为例：
unlink(uint64_t ino, char *name)
1 找出父目录的inode和dentry
struct inode *inode = inode_find(ino)
struct dentry *parent = inode->dentry。
2 拼出路径，删除后备文件系统的文件
char *path = dentry_path(parent) + "/" + name
3 删除子文件对应的dentry。
注意此时子文件的dentry可能还没被lookup进来。
但是如果是fuse开启了default_permissions挂载选项，内核会先lookup儿子，来检查是否具有删除权限，此时子dentry是lookup了的。
删除dentry时，我们应当将其inode的dentry置为NULL，否则inode会访问已经释放的内存。因此dentry需要持有inode指针。
struct dentry *child = dentry_find(parent, name);
if (child) {
child->inode->dentry = NULL;
dentry_free(child);
}
注意，删除文件我们不释放inode，见下面的reference count。
移动文件夹也没有啥特别的。inode没有变，只是把dentry的父亲修改一下，dentry名字变一下。
例如移动a目录下的b，到c目录下的d。
那么：
struct inode *a = inode_find(ino_a)
struct dentry *b = dentry_find(a->dentry, "b")
struct inode *c = inode_find(ino_c)
struct dentry *d = dentry_find(c->dentry, "d")
如果b和d已经提前lookup了。d可能存在，也可能不存在。
b->parent = c
b->name = "d"
// b的名字变了，hash的key发生了改变，需要重新哈希
rehash(b)
if (d) {
d->inode->dentry = NULL;
dentry_free(d);
}
硬链接会有多个dentry指向同一个inode。删除一个dentry，仍然可以通过另外的dentry访问。因此需要修改下dentry，添加链表支持。
struct inode {
struct hlist_node hash;
uint64_t ino;
struct dentry *dentry;
};
struct dentry {
struct hlist_node hash;
char *name;
struct dentry *parent;
struct inode *inode;
struct dentry *next;
};
这样inode->dentry指向第一个硬链，next指向下一个硬链。移除一个dentry，就把dentry从单链中拿掉。
如果硬链很多，硬链有性能问题，此时可以用双向链表。具体的操作就不示例了。
根据fuse的设计，inode引用计数，完全由内核持有。内核不需要的时候，我们才释放inode。删除文件不释放inode。
fuse不关心dentry，dentry存在的唯一目的，就是为了inode找到后备文件系统中对应的文件。因此dentry的引用计数由inode持有。
由于dentry是棵树，儿子也持有父亲的引用计数。当dentry的引用计数到达0的时候，释放dentry。
添加引用计数后，结构体变成：
struct inode {
struct hlist_node hash;
unsigned refcnt;
uint64_t ino;
struct dentry *dentry;
};
struct dentry {
struct hlist_node hash;
unsigned refcnt;
char *name;
struct dentry *parent;
struct inode *inode;
struct dentry *next;
};
dentry不持有inode指针的利弊？
在第4节lookup中，我们分析，如果本次lookup的inode发生了变化，那么之前的inode的dentry应该设置为NULL。这样确保之前的
inode无法再访问后备文件系统的文件。
但是如果lookup发生inode变化，内核是不是会确保不再访问此inode呢？如果是这样的话，那么dentry是没有必要持有inode的指针。
另外删除文件，需要dentry持有inode指针，这样可以将dentry的inode的dentry指针置空，否则，可能访问空指针。