xv6文件系统详解

xv6文件系统由inode组成，每个inode是单个未命名的文件。整个磁盘读写的最小单元为block (xv6为512字节)，其中整个磁盘分布如下图

 

第0个block为启动区，第1个block为超级块 (也是根目录所在的块),接下来是连续分布的dinode，最后是连续分布的BPB(块位图)

假设块大小为BSIZE, 则

1. 每个块包含的dinode结构体的数量为: IPB = BSIZE/sizeof(dinode)。等价于第i个dinode所在的block为IBLOCK(i) = i/IPB+2
2. 第i个block所在的位图块为： BBLOCK(b, ninodes) = b/BPB+ninodes/IPB+3

 

一、位图块 (BPB)
      xv6文件系统采用位图块来管理磁盘中的块，每个块可以管理的大小为 BPB = BSIZE * 8，若该标志为0，则块空闲，否则已经使用。

获取块时调用balloc，首先读取该dev的superblock，从而获取文件系统的所有块的大小sb.size，对于每个BPB依次检测是否有空闲块，若该块对应的位图块的标志位0，则为说明该块空闲，返回即可。
static uintballoc(uint dev){ int b, bi, m; struct buf *bp; struct superblock sb; bp = 0; readsb(dev, &sb); for(b = 0; b < sb.size; b += BPB) { bp = bread(dev, BBLOCK(b, sb.ninodes)); for(bi = 0; bi < BPB; bi++) { m = 1 << (bi % 8); if((bp->data[bi/8] & m) == 0) { //第b+bi个block为空闲，则标志它为使用并返回块号 bp->data[bi/8] |= m; bwrite(bp); brelse(bp); return b + bi; } } brelse(bp); } panic("balloc: out of blocks");}

需要说明的是，每个dev的ninodes、size大小都是固定的。

 

二、inode文件系统

   xv6只将active的dinode保存在内存的inode数组icache中

struct inode { uint dev; // Device number uint inum; // Inode number int ref; // Reference count int flags; // I_BUSY, I_VALID //以下为dinode的in-memory拷贝 short type; // 有T_DEV=1, T_FILE=2, T_DIR=3 short major; short minor; short nlink; uint size; uint addrs[NDIRECT+1];};

对于on-disk的dinode结构，它是块列表数据保存在addrs数组中，其中addrs[0...NDIRECT-1]直接存储的块号，而adds[NDIRECT]相当于一个指针，指向了一个块，这个块中保存了间接的块号构成的一个数组。

从程序员的角度来看，文件是一种字节流，程序从0到size进行顺序访问，但是实际文件是分割成多个块存储在磁盘中的，那么文件系统中的bmap就实现从逻辑块到物理块的一个映射。

static uintbmap(struct inode *ip, uint bn){ uint addr, *a; struct buf *bp; if(bn < NDIRECT) { //数组中直接存储的块 if((addr = ip->addrs[bn]) == 0) ip->addrs[bn] = addr = balloc(ip->dev); return addr; } bn -= NDIRECT; if(bn < NINDIRECT) { // 间接存储的块 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); bwrite(bp); } brelse(bp); return addr; } panic("bmap: out of range");}

如果是一个文件，则可以根据inode中的addrs获取文件内容所在的块，但是如果是一个目录呢？其实，目录也是一个文件，文件中包含有多个目录项，其结构为

struct dirent { ushort inum; char name[DIRSIZ];};

其中name为文件名，inum为inode号。

     在解析路径时，我们可能需要在目录中查找下一个文件，并返回相应的inode结点，基本做法是把inode目录文件的内容逐块导入到内存中，如果目录项的名字dirent->name和查找的名字相同，则查找到了匹配项，返回相应的inode (第inum个inode，若没有in-memory拷贝，则会创建一个：找出一个空闲的inode,并替换元数据)struct inode*dirlookup(struct inode *dp, char *name, uint *poff){ uint off, inum; struct buf *bp; struct dirent *de; for(off = 0; off < dp->size; off += BSIZE) { bp = bread(dp->dev, bmap(dp, off / BSIZE)); for(de = (struct dirent*)bp->data; de < (struct dirent*)(bp->data + BSIZE); de++) { if(de->inum == 0) continue; if(namecmp(name, de->name) == 0) { //找到匹配项 if(poff) *poff = off + (uchar*)de - bp->data; inum = de->inum; brelse(bp); return iget(dp->dev, inum); } } brelse(bp); } return 0;}

 

三、文件路径解析

    到现在一切似乎水到渠成了，那么我们可以直面最激动人心的问题了：如果碰到这样/usr/home/zl.txt的路径，我们应该怎样解析呢？

 static struct inode*namex(char *path, char *name){ struct inode *ip, *next; if(*path == '/') ip = iget(ROOTDEV, ROOTINO); else ip = idup(proc->cwd); while((path = skipelem(path, name)) != 0) { ilock(ip); if(ip->type != T_DIR) { iunlockput(ip); return 0; } if((next = dirlookup(ip, name, 0)) == 0) { iunlockput(ip); return 0; } iunlockput(ip); ip = next; } return ip;}

其实方法很简单，逐步的解析路径，得到下层的inode结点。

1. name="usr", path="home/zl.txt", 在根目录中查找并返回名为"usr" 对应的inode

2. name="home", path="zl.txt"，在上级inode中查找并返回名为"home"对应的inode

3. name="zl.txt", path=""，在上级inode中查找并返回名为"zl.txt"对于的inode

4. path=0, 跳出while循环