inode、目录、路径
文件系统
本文继续来看 的文件系统部分， 将文件系统的设计分为 7 层：磁盘缓存区日志目录路径文件系统调用 ，磁盘、缓存区、日志三个部分在前文已经说了，本文接着讲述 ，目录，路径三个层次。
这部分的理论知识可以参考文章：[捋一捋文件系统] 。本文直接来看 xv6 的文件系统这部分是如何实现的。
文件系统布局
再来系统的看看 xv6 文件系统的布局图：
引导块、超级块
第 0 块是引导块，里面存放的启动程序也就是 ，详见前文：[实例讲解多处理器下的计算机启动]
第 1 块是超级块，存有文件系统的元信息，相关结构体定义如下：
struct superblock {
uint size; // Size of file system image (blocks) 文件系统大小，也就是一共多少块
uint nblocks; // Number of data blocks 数据块数量
uint ninodes; // Number of inodes. //i结点数量
uint nlog; // Number of log blocks //日志块数量
uint logstart; // Block number of first log block //第一个日志块块号
uint inodestart; // Block number of first inode block //第一个i结点所在块号
uint bmapstart; // Block number of first free map block //第一个位图块块号
};可以看出超级块实则就是文件系统布局的信息集合。在 中我们可以知道：
#define NINODES 200
#define MAXOPBLOCKS 10
#define LOGSIZE (MAXOPBLOCKS*3)
#define FSSIZE 1000
#define IPB (BSIZE / sizeof(struct dinode))
int nbitmap = FSSIZE/(BSIZE*8) + 1;
int ninodeblocks = NINODES / IPB + 1;
int nlog = LOGSIZE;
int nmeta = 2 + nlog + ninodeblocks + nbitmap;
int nblocks = FSSIZE - nmeta;
int logstart = 2;
int inodestart = 2 + nlog;
int bmapstart = 2 + nlog + ninodeblocks;从上述代码可以看出，文件系统的各个部分从哪开始，到哪结束都是可以明确计算出来的，所以其实不管将日志区安排在哪，我们都可以从超级块中获取相应的位置大小信息。
数据区
紧接着超级块的区域应该是 ，但是 的内容有些多有些复杂，我们放在后面讲，先来看看数据区中数据块的组织与管理。
数据块的分配和释放由位图来管理，但位图管理的区域不止数据区，而是整个文件系统。有关位图的宏定义如下：
// Bitmap bits per block 每个块能有多少个bit
#define BPB (BSIZE*8)
// Block of free map containing bit for block b 块b在哪个位图块上
#define BBLOCK(b, sb) (b/BPB + sb.bmapstart)分配回收
static uint balloc(uint dev)
{
int b, bi, m;
struct buf *bp;
bp = 0;
for(b = 0; b < sb.size; b += BPB){
bp = bread(dev, BBLOCK(b, sb)); //读取位图信息
for(bi = 0; bi < BPB && b + bi < sb.size; bi++){
m = 1 << (bi % 8);
if((bp->data[bi/8] & m) == 0){ // Is block free? 如果该块空闲
bp->data[bi/8] |= m; // Mark block in use. 标记该块使用
log_write(bp);
brelse(bp); //释放锁
bzero(dev, b + bi); //将该块置0
return b + bi; //返回块号
}
}
brelse(bp); //释放锁
}
panic("balloc: out of blocks");
}
static void bfree(int dev, uint b) //释放一个数据块，相应位图清零
{
struct buf *bp;
int bi, m;
bp = bread(dev, BBLOCK(b, sb));
bi = b % BPB;
m = 1 << (bi % 8);
if((bp->data[bi/8] & m) == 0)
panic("freeing free block");
bp->data[bi/8] &= ~m;
log_write(bp);
brelse(bp);
}位图块中每一位都代表着一块，该位置 1 表示相应的块正在使用，该位置 0 表示相应的块空闲。分配数据块就是在位图中寻找空闲位，然后将其置 1 就代表分配出去了。
上述代码涉及的都是比较简单的位运算，有详细的注释，就不说明了，释放一个数据块的操作就是分配的逆操作，也不再赘述。
inode
磁盘上的 dinode
紧接着超级块后面的区域是 区域， 定义的 共有 200 个，每个磁盘上的 定义如下：
struct dinode {
short type; // File type
short major; // Major device number (T_DEV only)
short minor; // Minor device number (T_DEV only)
short nlink; // Number of links to inode in file system
uint size; // Size of file (bytes)
uint addrs[NDIRECT+1]; // Data block addresses
};
#define NDIRECT 12表示该 指向的文件的类型，在 里面就只有三种类型，普通文件，目录文件，设备文**件**
表示该文件的链接数，链接分为硬链接和软连接，这里与链接数目直接相关的是硬链接，后面实现文件系统调用的时候我们会看到， 系统调用会创建一个新目录项并且增加一个链接数。 系统调用将链接数减 1，如果该文件在内存中的引用数和链接数都为 0 的话，则会删除该文件。这部分咱们后面再慢慢聊，本文只捎带提一下。
表示文件的大小，这里是以字节为单位。
在 里面使用 和 来区分设备，同一类设备有着相同的 ， 又表示该类设备中具体的某设备。后面我们会看到如果文件类型为设备，则读写的时候会根据 调用相应设备的读写程序。
每个 有 11 个一级指针，一个间接指针，用来指向数据块。这些都是可以改变的， 有个关于支持大文件的实现就是要增加一个间接索引来实现。
inode 缓存
磁盘上的 在内存中也有相应的缓存：
struct {
struct spinlock lock;
struct inode inode[NINODE];
} icache; //磁盘上i结点在内存中的缓存内存中的 定义如下：
struct inode {
uint dev; // Device number 设备号
uint inum; // Inode number inode 号
int ref; // Reference count 引用数
struct sleeplock lock; // protects everything below here
int valid; // inode has been read from disk? 是否有效
short type; // copy of disk inode
short major;
short minor;
short nlink;
uint size;
uint addrs[NDIRECT+1];
};内存中的 比磁盘上的 多了几个属性，首先是设备号， 里面一切皆文件，设备也是文件，所以设备号来表示什么设备。但是 xv6 没这么复杂，这里主要就是来区分磁盘的主盘和从盘。时为从盘， 时为主盘，这个值在读写磁盘的时候用到，用它来设置磁盘的 device 寄存器来指定主盘从盘。详见：[带你了解磁盘驱动程序]
表示引用数，这个要与 链接数作区别，目前可以暂且理解为 为磁盘上文件之间的关系，而 主要用于内存中引用该文件的次数，比如 关闭文件使引用数减 1。这部分在文件系统调用的时候再作详细讲解。
表示是否有效，跟磁盘那里缓存块中的数据是否有效一个意思，如果缓存中的数据是从磁盘中读取过来的，则有效。通常无效是因为 刚分配，所以里面的数据无效。
整个 缓存区有一把自旋锁，每个 缓存有把休眠锁，为什么如此，道理还是同磁盘和缓存块。首先它们都是公共资源，需要锁来避免竞争条件。再者 的作用就是组织管理 ，像是一个分配器，访问 的临界区的时间是很短的，使用自旋锁就行。而一个进程对某个 的使用时间可能很长，最好使用休眠锁，其他进程也想要获取该 的使用权时就休眠让出 提高性能。
分配 inode
对于磁盘上的 ， 并没有什么组织管理结构，分配空闲 的方法就是简单粗暴地从头至尾循环查找空闲 。
struct inode*
ialloc(uint dev, short type)
{
int inum;
struct buf *bp;
struct dinode *dip;
for(inum = 1; inum < sb.ninodes; inum++){
bp = bread(dev, IBLOCK(inum, sb)); //读取第inum个i结点所在的位置
dip = (struct dinode*)bp->data + inum%IPB; //该i结点地址
if(dip->type == 0){ // a free inode 找到空闲i结点
memset(dip, 0, sizeof(*dip));
dip->type = type;
log_write(bp); // mark it allocated on the disk
brelse(bp);
return iget(dev, inum); //以内存中的i结点形式返回
}
brelse(bp);
}
panic("ialloc: no inodes");
}
#define IBLOCK(i, sb) ((i) / IPB + sb.inodestart)
#define IPB (BSIZE / sizeof(struct dinode))先来看看下面两个宏定义， 表示一个块中能有几个 ， 表示第 个 在第几块。
分配数据块的时候有位图来组织管理，所以分配数据块的时候就“从头至尾”的查询空闲位，而 没有组织管理的机制，所以就直接从头至尾的查询 的使用情况。如果该 的 属性为 0 表示该 空闲，可以分配，反之正是用当中不可分配。
分配了之后将该 初始化，将其数据全部置 0，然后赋其 属性，表示该 指向一个 类型的文件。
分配了该 需要在磁盘上也将其标记为已分配，因为目前是在内存中操作的，得同步到磁盘上去，所以直接调用 将该 所在的缓存块同步到磁盘。当然并未真正地直接写到磁盘了，只是在将该缓存数据标记为脏，关于日志，读写磁盘的操作本文不赘述了，可以参考前文：[如何实现一个简单的日志系统]
回到分配 的函数上来，磁盘上的 已分配，得到了 号，但是文件系统实际工作的时候使用的是内存中的 缓存，所以调用 来分配(获取)一个内存中的 来缓存 数据：
static struct inode* iget(uint dev, uint inum)
{
struct inode *ip, *empty;
acquire(&icache.lock);
// Is the inode already cached? 如果该dinode在内存中已缓存
empty = 0;
for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){
if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){ //在缓存中找到该i结点
ip->ref++; //引用加1
release(&icache.lock);
return ip;
}
if(empty == 0 && ip->ref == 0) // Remember empty slot. 记录icache中空闲的inode
empty = ip;
}
// Recycle an inode cache entry.
if(empty == 0)
panic("iget: no inodes");
//该dinode在内存中没有缓存，分配一个空闲inode empty
//根据参数，初始化该空闲inode，还没读入数据，valid设为0
ip = empty;
ip->dev = dev;
ip->inum = inum;
ip->ref = 1;
ip->valid = 0;
release(&icache.lock);
return ip;
}如果磁盘上的 在 中已有缓存，那么直接将该 的引用数加 1，再返回该 就行。如果没有缓存则分配一个空闲的 ，根据参数初始化 ，因为没有实际读入 的数据，所以 的 属性置 0 表示无效。
使用修改 inode
使用 之前需要加锁：
void ilock(struct inode *ip)
{
struct buf *bp;
struct dinode *dip;
if(ip == 0 || ip->ref < 1) //空指针引用小于1都是错误的
panic("ilock");
acquiresleep(&ip->lock); //上锁
if(ip->valid == 0){ //有效位为0，从磁盘读入数据
bp = bread(ip->dev, IBLOCK(ip->inum, sb));
dip = (struct dinode*)bp->data + ip->inum%IPB;
ip->type = dip->type;
ip->major = dip->major;
ip->minor = dip->minor;
ip->nlink = dip->nlink;
ip->size = dip->size;
memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
brelse(bp);
ip->valid = 1;
if(ip->type == 0)
panic("ilock: no type");
}
}分配 的时候并未从磁盘中 读入数据，只是将 的 置 0 表示数据无效，正式读入 数据在这加锁的时候进行。
对缓存中 的修改需要同步到磁盘上的 ：
void iupdate(struct inode *ip)
{
struct buf *bp;
struct dinode *dip;
bp = bread(ip->dev, IBLOCK(ip->inum, sb)); //读取磁盘上的i结点
dip = (struct dinode*)bp->data + ip->inum%IPB;
dip->type = ip->type; //update
dip->major = ip->major;
dip->minor = ip->minor;
dip->nlink = ip->nlink;
dip->size = ip->size;
memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
log_write(bp);
brelse(bp);
}用完 需要 “放下” 它：
void iput(struct inode *ip)
{
acquiresleep(&ip->lock); //取锁
if(ip->valid && ip->nlink == 0){
//获取该i结点的引用数
acquire(&icache.lock);
int r = ip->ref;
release(&icache.lock);
if(r == 1){
// inode has no links and no other references: truncate and free.
itrunc(ip);
ip->type = 0;
iupdate(ip);
ip->valid = 0;
}
}
releasesleep(&ip->lock);
acquire(&icache.lock);
ip->ref--;
release(&icache.lock);
}该函数将 的引用数减 1，如果本身就是该 的最后一个引用，且链接数也为 0，那么调用 将该 指向的所有数据块全部释放，也就相当于删除了 指向的文件。
表示该 已释放，被回收到了 。将 信息更新到磁盘上的 之后将 置 0 表数据不再有效。
索引
的索引部分用来指向数据块
static uint bmap(struct inode *ip, uint bn) //给i结点第bn个索引指向的地方分配块
{
uint addr, *a;
struct buf *bp;
//bn为直接索引
if(bn < NDIRECT){
//如果第bn个索引指向的块还未分配，则分配，否则返回块号
if((addr = ip->addrs[bn]) == 0)
ip->addrs[bn] = addr = balloc(ip->dev);
return addr;
}
bn -= NDIRECT; //bn为间接索引
if(bn < NINDIRECT){
// Load indirect block, allocating if necessary.
if((addr = ip->addrs[NDIRECT]) == 0) //如果间接索引所在的块还未分配，分配
ip->addrs[NDIRECT] = addr = balloc(ip->dev);
bp = bread(ip->dev, addr); //读取一级索引块
a = (uint*)bp->data;
if((addr = a[bn]) == 0){ //如果该索引指向的块还未分配，分配
a[bn] = addr = balloc(ip->dev);
log_write(bp);
}
brelse(bp);
return addr; //返回索引bn指向的块的块号
}
panic("bmap: out of range");
}返回索引 指向的数据块块号，如果该数据块未分配，则分配之后再返回该块块号。
static void itrunc(struct inode *ip)
{
int i, j;
struct buf *bp;
uint *a;
for(i = 0; i < NDIRECT; i++){ //释放直接索引指向的数据块
if(ip->addrs[i]){
bfree(ip->dev, ip->addrs[i]);
ip->addrs[i] = 0;
}
}
if(ip->addrs[NDIRECT]){
bp = bread(ip->dev, ip->addrs[NDIRECT]); //读取一级索引块
a = (uint*)bp->data;
for(j = 0; j < NINDIRECT; j++){ //释放一级索引指向的块
if(a[j])
bfree(ip->dev, a[j]);
}
brelse(bp);
bfree(ip->dev, ip->addrs[NDIRECT]); //释放一级索引块
ip->addrs[NDIRECT] = 0;
}
ip->size = 0;
iupdate(ip);
}，截断 ，不知怎样翻译，但这个函数的实际工作就是将 所指向的数据块全部释放，也就相当于删除文件了。具体的工作方式就是一个个的判断索引是否有效，如果有效就调用 释放，然后将该索引置为无效。基本上就与 做相反的工作。
读写数据
int readi(struct inode *ip, char *dst, uint off, uint n) //从inode读取数据
{
uint tot, m;
struct buf *bp;
if(ip->type == T_DEV){ //如果该inode指向的是设备文件
if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read)
return -1;
return devsw[ip->major].read(ip, dst, n); //使用设备特有的读取方式
}
if(off > ip->size || off + n < off) //如果开始读取的位置超过文件末尾，如果读取的字节数是负数
return -1;
if(off + n > ip->size) //如果从偏移量开始的n字节超过文件末尾
n = ip->size - off; //则只能够再读取这么多字节
for(tot=0; tot<n; tot+=m, off+=m, dst+=m){ //tol:目前总共已读的字节数，n:需要读取的字节数,off:从这开始读,dst:目的地
bp = bread(ip->dev, bmap(ip, off/BSIZE)); //读取off所在的数据块到缓存块
m = min(n - tot, BSIZE - off%BSIZE); //一次性最多读取m字节
memmove(dst, bp->data + off%BSIZE, m); //赋值数据到dst
brelse(bp); //释放缓存块
}
return n;
}
int writei(struct inode *ip, char *src, uint off, uint n)
{
uint tot, m;
struct buf *bp;
if(ip->type == T_DEV){
if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write)
return -1;
return devsw[ip->major].write(ip, src, n);
}
if(off > ip->size || off + n < off)
return -1;
if(off + n > MAXFILE*BSIZE)
return -1;
for(tot=0; tot<n; tot+=m, off+=m, src+=m){
bp = bread(ip->dev, bmap(ip, off/BSIZE));
m = min(n - tot, BSIZE - off%BSIZE);
memmove(bp->data + off%BSIZE, src, m);
log_write(bp);
brelse(bp);
}
函数用来读取数据，从 ip 指向的文件中，从 开始读，读取 字节到 中去。
如果 指向的文件类型是设备，那么读取数据要使用专门的读取方式，比如说控制台有着自己专门的读入数据方式，这些设备的读取方法集合在 数组当中。关于这部分我们后面的文章再详述，这里只说磁盘上的文件的读写。
紧接着判断了一下参数的合理性，比如 不应超过文件末尾，读取的字节数 不应该是负数，如果 超过了文件末尾，那么最多只能读取 个字节数，要修改 的值。
文件数据可能有多块， 表示 所在的块数，这个块数是相对于该文件开头的块号，调用 获取 所在的绝对块号。拿到 所在数据块的绝对块号之后调用 读取该数据块的数据到缓存块 。
数据在内存中已经准备完毕，可以赋值移动数据了。但是每次读取的数据有上限，不能超过 ，这是还需要读取的字节数，不能超过 ，这是每次最多能够读取的字节数。不能超过这两者，所以两者之中取较小值。
，将数据源 中的数据写 字节到 指向的文件中，从偏移量为 的地方开始写。
基本上是与 相反的操作，只是最后需要更新 信息，因为像文件中写数据，该文件会变大， 是文件的代表与文件一一对应，需要更新 的 size 属性，然后再调用 将 同步到磁盘上的 。
目录
目录也是文件，只是它的数据有些特殊，其数据是一个个目录项，其主要属性有文件名， 编号。
是一个文件的代言人，一个文件与一个 一一对应，但是 的属性里面并没有文件名。文件名这个属性在目录项这指出，目录项的主要作用就是将 和文件名联系起来。
结构定义
struct dirent { //目录项结构
ushort inum;
char name[DIRSIZ];
};
#define DIRSIZ 14中目录项只由两项组成，文件名和 编号。
查找目录项
struct inode* dirlookup(struct inode *dp, char *name, uint *poff)
{
uint off, inum;
struct dirent de;
if(dp->type != T_DIR) //如果该文件不是目录文件
panic("dirlookup not DIR");
for(off = 0; off < dp->size; off += sizeof(de)){
if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) //读取dp指向的目录文件，每次读一个目录项
panic("dirlookup read");
if(de.inum == 0) //如果是根目录??????????????
continue;
if(namecmp(name, de.name) == 0){ //根据名字找文件
// entry matches path element
if(poff) //记录该目录项在目录中的偏移
*poff = off;
inum = de.inum; //name文件的inode编号
return iget(dp->dev, inum); //或取该inode
}
}
return 0;
}这个函数用来在 指向的目录文件下寻找名为 的目录项，将该目录项的偏移量记录在 中，最后返回名字为 的文件的 。
因此根据文件名查找文件的是指就是在目录文件中查找目录项的过程，具体的查找方式就是一个个的比对目录项的名称和要查找的文件名是否相同，如果相同，则找到，反之说明该目录下并没有要查找的文件。
添加目录项
int dirlink(struct inode *dp, char *name, uint inum)
{
int off;
struct dirent de;
struct inode *ip;
// Check that name is not present.
if((ip = dirlookup(dp, name, 0)) != 0){
iput(ip); //dirlookup调用iget使引用数加1，所以调用iput使引用数减1
return -1; //name目录项已存在，返回-1
}
// Look for an empty dirent.
for(off = 0; off < dp->size; off += sizeof(de)){
if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
panic("dirlink read");
if(de.inum == 0) //找到一个空闲目录项
break;
}
strncpy(de.name, name, DIRSIZ); //设置目录项的文件名字
de.inum = inum; //设置目录项的i结点编号
if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de)) //将该目录项写进dp指向的目录文件中
panic("dirlink");
return 0;
}此函数用来在 指向的目录文件中添加一个目录项，通常是创建了一个新文件，需要在该目录下添加这个新文件的信息。
首先查找该目录项是否存在，如果不存在则找一个空闲目录项位置，将新文件的 和文件名写进去。
路径
路径，何为路径，比如常见的 ，仔细观察，会发现，路径实则是一个个文件名组成的，这个文件可能是目录文件，也可能是普通文件。一般最后一项是普通文件名，中间的都是目录文件名。
另外像 这种路径以 '/' 开头表示绝对路径， 这种不以 '/' 开头的表示相对路径。这两种路径大家应该都很熟悉了，不再多做解释，或者可以参考文章[捋一捋文件系统] ，其中详细的捋了捋文件系统的理论知识。
不论哪一种路径表示，都需要一个路径解析函数，将其中一个个文件名给提取出来：
static char* skipelem(char *path, char *name)
{
char *s;
int len;
while(*path == '/') //跳过'/'
path++;
if(*path == 0) //路径空
return 0;
s = path;
while(*path != '/' && *path != 0) //path继续向后移，剥出最前面的目录名
path++;
len = path - s; //记录该目录名的长度
if(len >= DIRSIZ)
memmove(name, s, DIRSIZ); //将该目录名复制给name
else {
memmove(name, s, len);
name[len] = 0;
}
while(*path == '/') //继续跳过'/'
path++;
return path; //返回剩下的路径
}调用一次解析一个头部的文件名放在 中，返回剩下的路径。
用源码注释中的例子来说明：
skipelem("a/bb/c", name) = "bb/c", setting name = "a"
skipelem("///a//bb", name) = "bb", setting name = "a"
skipelem("a", name) = "", setting name = "a"
skipelem("", name) = skipelem("////", name) = 0static struct inode*
namex(char *path, int nameiparent, char *name)
{
struct inode *ip, *next;
if(*path == '/') //绝对路径
ip = iget(ROOTDEV, ROOTINO); //读取根目录
else //相对路径
ip = idup(myproc()->cwd); //读取当前工作目录
while((path = skipelem(path, name)) != 0){
ilock(ip);
if(ip->type != T_DIR){
iunlockput(ip);
return 0;
}
if(nameiparent && *path == '\0'){ //如果是要返回父结点，并且剩下的路径已经为空，则当前结点就是i结点直接返回
// Stop one level early.
iunlock(ip);
return ip;
}
if((next = dirlookup(ip, name, 0)) == 0){ //查询下一个目录
iunlockput(ip);
return 0;
}
iunlockput(ip);
ip = next; //当前目录指向下一个，然后while循环，直到解析到最后
}
if(nameiparent){
iput(ip);
return 0;
}
return ip;
}这个函数根据路径返回 ，比如说路径 ，如果 有效，则返回文件 的 ，如果 无效，则返回文件 的 。
这个函数主要是对路径解析函数 和查找目录项函数 函数的运用，根据路径查找文件的步骤大致如下：
- 获取当前目录的
- 根据 获取目录文件
- 在该目录文件下根据文件名查找文件/目录
- 循环上述过程直到文件被找到
函数就是上述过程的实现，至于这个函数的具体怎么实现的，就不详细说明了，可以自己举个例子根据代码模拟一下过程就明白了。在模拟的过程中主要注意几个条件判断：
(path = skipelem(path, name)) != 0，当 为空字符串的才返回 0，也就是说skipelem("", name) = 0。path 指向一个空字符串，并不是说 path 本身为空if(nameiparent && *path == '\0')， 为空字符串的时候也就是 "" 的时候*path = '\0'。
另外如果是相对路径的话，当前目录需要从进程 中的 属性中获取，相关内容后面进程再详述。
本文主要介绍了 文件系统 ，目录，路径三个层次的设计与实现，应该对这三个概念会有个更深刻的认识。 是文件的代表，与文件一一对应，目录也是文件，只是其数据是其他文件的信息，也就是一个个目录项。目录项是其他文件的文件名和相应的 编号组合而成。而路径呢？就是一个个文件名组合在一起的字符串。可以使用路径解析函数将一个个文件名解析出来，然后根据一层层目录中的目录项从上至下地查找文件。
好啦本文就到这里了，有什么错误还请批评指针，也欢迎大家来同我讨论交流一起学习进步。