當(dāng)我們向 文件 append 一個(gè)單詞時(shí)，背后發(fā)生了啥？
一， 找到父親文件夾的inode
- 首先我們可能會(huì)打開（沒有的時(shí)候創(chuàng)建一個(gè)文件），這個(gè)是通過在用戶空間調(diào)用
fd = open(name, O_CREATE | O_RDWR);實(shí)現(xiàn)的。 - 接下來會(huì)去定位到這個(gè)路徑下的dir，他會(huì)從當(dāng)前路徑的inode，往下一路尋找。直到找到這個(gè)文件上一級(jí)的inode，就是這個(gè)文件上一級(jí)dir的inode。
struct inode {
uint dev; // Device number
uint inum; // Inode number
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];
};
- 下面講解下找
inode的過程
1705635681264.png
上圖中，inode塊里，存的是這樣的數(shù)據(jù)結(jié)構(gòu)的內(nèi)容：
struct dinode {
short type; // File type
short major; // Major device number (T_DEVICE only)
short minor; // Minor device number (T_DEVICE only)
short nlink; // Number of links to inode in file system
uint size; // Size of file (bytes)
uint addrs[NDIRECT+1]; // Data block addresses
};
我們需要把inode磁盤上的數(shù)據(jù)加載進(jìn)內(nèi)存里緩存起來（注，這里讀的不是磁盤上的文件內(nèi)容，而是inode的內(nèi)容，也就是文件里會(huì)存dinode這個(gè)數(shù)據(jù)結(jié)構(gòu)里的幾個(gè)數(shù)據(jù)），這個(gè)就是ilock這個(gè)方法做的事情。所以這里會(huì)第一次讀磁盤（存在bcache里）
a. 首先通過下面代碼定位當(dāng)前inode, 一種路徑是絕對(duì)路徑，一種是相對(duì)路徑。
if(*path == '/')
ip = iget(ROOTDEV, ROOTINO);
else
ip = idup(myproc()->cwd);
b. 循環(huán)彈出，每一級(jí)folder 的 folder名。 如a/b/c， 就依次遍歷a,b,c
c. 當(dāng)前inode必為dir, 查找彈出的名字，如a
d. 得到新的inode，繼續(xù)循環(huán)，知道到最后一級(jí)（不再是dir,是文件了），不再查找文件，直接返回父親dir 的inode
- 下面講解下在dir
inode中找下一級(jí)inode的過程
1705639931332.png
for(off = 0; off < dp->size; off += sizeof(de)){
if(readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
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;
return iget(dp->dev, inum);
}
}
a. 首先我們需要讀取當(dāng)前dir inode里的數(shù)據(jù)，因?yàn)閐ir存的就是下面有哪些dir或文件。我們要判斷我們這個(gè)文件名在不在里面，以及在什么位置。dir文件內(nèi)容是由下面的數(shù)據(jù)結(jié)構(gòu)組成的。inum 就是子文件或子DIR的inode編號(hào)
struct dirent {
ushort inum;
char name[DIRSIZ];
};
所以可以看到for 循環(huán)每次off += sizeof(de)
b. 那么有了偏移量和inode，就可以計(jì)算數(shù)據(jù)在磁盤上的物理地址. 就是用offset/BSIZE,得到一個(gè)序號(hào)，這個(gè)序號(hào)就可以從inode的addrs， 找到對(duì)應(yīng)磁盤的地址了。
c. 然后就是讀取磁盤的地址，有可能一個(gè)dirent ，會(huì)跨2個(gè)BBLOCK，所以我們要注意這種可能。這也是下面代碼m的作用：
for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
uint addr = bmap(ip, off/BSIZE);
if(addr == 0)
break;
bp = bread(ip->dev, addr);
m = min(n - tot, BSIZE - off%BSIZE);
if(either_copyout(user_dst, dst, bp->data + (off % BSIZE), m) == -1) {
brelse(bp);
tot = -1;
break;
}
brelse(bp);
}
- 綜上我們成功找到了要?jiǎng)?chuàng)建/打開的文件的父文件夾目錄。
二， 創(chuàng)建并返回文件inode
- 先用同樣的方法遍歷父文件夾下有沒有這個(gè)文件的文件名，有的話，直接返回該文件名的inode （實(shí)際只需要inum，其余的屬性會(huì)在ilock時(shí)去文件系統(tǒng)讀）
- 如果不存在，就代表要?jiǎng)?chuàng)建一個(gè)新文件，那么就調(diào)用
ialloc
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));
dip = (struct dinode*)bp->data + inum%IPB;
if(dip->type == 0){ // a free inode
memset(dip, 0, sizeof(*dip));
dip->type = type;
log_write(bp); // mark it allocated on the disk
brelse(bp);
return iget(dev, inum);
}
brelse(bp);
}
printf("ialloc: no inodes\n");
return 0;
}
- 讀取inum所屬的那個(gè)inode文件，找到對(duì)應(yīng)偏移量，判斷是不是freenode，是的話，就可以用來創(chuàng)建了。這邊有一個(gè)讀取inode區(qū)域的讀磁盤操作。
三，關(guān)聯(lián)file 和 fd
- 在ftable 里加一個(gè)新的file 的數(shù)據(jù)結(jié)構(gòu)
struct file {
enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE } type;
int ref; // reference count
char readable;
char writable;
struct pipe *pipe; // FD_PIPE
struct inode *ip; // FD_INODE and FD_DEVICE
uint off; // FD_INODE
short major; // FD_DEVICE
};
// Allocate a file structure.
struct file*
filealloc(void)
{
struct file *f;
acquire(&ftable.lock);
for(f = ftable.file; f < ftable.file + NFILE; f++){
if(f->ref == 0){
f->ref = 1;
release(&ftable.lock);
return f;
}
}
release(&ftable.lock);
return 0;
}
- 在該進(jìn)程下找到一個(gè)空閑的fd去存儲(chǔ)這個(gè)file
static int
fdalloc(struct file *f)
{
int fd;
struct proc *p = myproc();
for(fd = 0; fd < NOFILE; fd++){
if(p->ofile[fd] == 0){
p->ofile[fd] = f;
return fd;
}
}
return -1;
}
- 配置file的ip(inode)
f->ip = ip;
f->readable = !(omode & O_WRONLY);
f->writable = (omode & O_WRONLY) || (omode & O_RDWR);
- 返回文件描述符到用戶空間。 （此時(shí)文件描述符可以找到file, file可以找到inode， inode下可以找到file的metadata, 和data在磁盤上的地址。
四，開始寫一個(gè)單詞
現(xiàn)在我們?cè)谟脩艨臻g可以向fd 寫一些數(shù)據(jù)，具體操作如
write(fd, (void*)addr, 8192);分別描述向哪個(gè)文件描述符，從addr開始把里面8192長(zhǎng)度的數(shù)據(jù)寫進(jìn)fd所屬的文件里。鎖定inode, 寫數(shù)據(jù)，解鎖inode
if(f->type == FD_INODE){
// write a few blocks at a time to avoid exceeding
// the maximum log transaction size, including
// i-node, indirect block, allocation blocks,
// and 2 blocks of slop for non-aligned writes.
// this really belongs lower down, since writei()
// might be writing a device like the console.
int max = ((MAXOPBLOCKS-1-1-2) / 2) * BSIZE;
int i = 0;
while(i < n){
int n1 = n - i;
if(n1 > max)
n1 = max;
begin_op();
ilock(f->ip);
if ((r = writei(f->ip, 1, addr + i, f->off, n1)) > 0)
f->off += r;
iunlock(f->ip);
end_op();
if(r != n1){
// error from writei
break;
}
i += r;
}
ret = (i == n ? n : -1);
}
上面可以隱式看到 文件的off 被維護(hù)住了，隨著寫的發(fā)生，off值相應(yīng)增大。
- writei 就是根據(jù)off 去查在inode的哪個(gè)addr里，取到addr，把它從磁盤讀進(jìn)緩存，然后開始向緩存buf寫數(shù)據(jù).
- 最后更新inode的size 為新的off, 然后寫回磁盤的inode區(qū)域
int
writei(struct inode *ip, int user_src, uint64 src, uint off, uint n)
{
uint tot, m;
struct buf *bp;
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){
uint addr = bmap(ip, off/BSIZE);
if(addr == 0)
break;
bp = bread(ip->dev, addr);
m = min(n - tot, BSIZE - off%BSIZE);
if(either_copyin(bp->data + (off % BSIZE), user_src, src, m) == -1) {
brelse(bp);
break;
}
log_write(bp);
brelse(bp);
}
if(off > ip->size)
ip->size = off;
// write the i-node back to disk even if the size didn't change
// because the loop above might have called bmap() and added a new
// block to ip->addrs[].
iupdate(ip);
return tot;
}
綜上，我們完成了向文件系統(tǒng)寫一個(gè)單詞的操作。當(dāng)然具體的落盤會(huì)由log取真正的保證。下面我們會(huì)去講解LOG的部分。。
我們這里來回顧一下，當(dāng)我們往文件里寫一個(gè)單詞會(huì)發(fā)生什么？
- 首先，要定位路徑父親的inode，這里會(huì)用到
itable這個(gè)緩存，如果沒在緩存里找到，那么會(huì)建一個(gè)新的條目放進(jìn)itable里，并且之后通過ilock方法，會(huì)根據(jù)inum把這個(gè)inode相關(guān)缺失的屬性從文件系統(tǒng)中的inode區(qū)域里讀出來。 - 當(dāng)處理dir的inode時(shí)，他的數(shù)據(jù)存放的其實(shí)是這個(gè)DIR下所有的其他INUM。我們依次遍歷找到名字可以對(duì)的上的INUM，然后用這個(gè)inum用步驟1去找到對(duì)應(yīng)的inode.
- 如果名字沒有匹配，需要?jiǎng)?chuàng)建時(shí),通過在文件系統(tǒng)的inode區(qū)域找到一個(gè)空閑的inode，進(jìn)行寫入。
- 那么文件的inode創(chuàng)建出來后，就會(huì)在進(jìn)程下找到一個(gè)空閑的
fd去關(guān)聯(lián)這個(gè)file, file里面最重要的就是這個(gè)inode - 這個(gè)inode 具體文件內(nèi)容寫的地址，會(huì)在調(diào)用
readi或writei時(shí)調(diào)用bmap的時(shí)候，用balloc去分配 - bmap返回一個(gè)
addr, 隨后會(huì)調(diào)用bread去讀這個(gè)addr( 也就是blockno) - cache層會(huì)先找到一個(gè)可用的cache，然后把內(nèi)容從磁盤讀進(jìn)cache里，之后就是操作內(nèi)存。
- 最后通過
log的記錄會(huì)進(jìn)行數(shù)據(jù)落盤
Log是如何工作的？
這里的思想是，在任何一個(gè)寫操作前，我們會(huì)先記這個(gè)寫操作到LOG里. 然后通過寫一條commit的標(biāo)志，表示前面的操作要么全執(zhí)行成功，要么全部不執(zhí)行（如果沒有commit標(biāo)志，前面的LOG全部丟棄）
那么在任意時(shí)間斷電，我們就可以去讀取LOG FILE，根據(jù)里面的COMMIT的標(biāo)志，來恢復(fù)數(shù)據(jù)了。
在XV6中，以創(chuàng)建文件的sys_open為例（在sysfile.c文件中）每個(gè)文件系統(tǒng)操作，都有begin_op和end_op分別表示事物的開始和結(jié)束。在end_op中會(huì)實(shí)現(xiàn)commit操作。
中間的寫log操作
void
log_write(struct buf *b)
{
int i;
acquire(&log.lock);
if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1)
panic("too big a transaction");
if (log.outstanding < 1)
panic("log_write outside of trans");
for (i = 0; i < log.lh.n; i++) {
if (log.lh.block[i] == b->blockno) // log absorption
break;
}
log.lh.block[i] = b->blockno;
if (i == log.lh.n) { // Add new block to log?
bpin(b);
log.lh.n++;
}
release(&log.lock);
}
這里其實(shí)只是更新了log.lh 的總size（也就是有幾個(gè)BLOCK 需要落盤，然后存放了哪幾個(gè)）
比如寫block 45，我們已經(jīng)更新了block cache中的block 45。接下來我們需要在內(nèi)存中記錄，在稍后的commit中，要將block 45寫入到磁盤的log中。
這里的代碼先獲取log header的鎖，之后再更新log header。首先代碼會(huì)查看block 45是否已經(jīng)被log記錄了。如果是的話，其實(shí)不用做任何事情，因?yàn)閎lock 45已經(jīng)會(huì)被寫入了。這種忽略的行為稱為log absorbtion。如果block 45不在需要寫入到磁盤中的block列表中，接下來會(huì)對(duì)n加1，并將block 45記錄在列表的最后。
下面我們看下commit函數(shù)，是怎么實(shí)現(xiàn)的
static void
commit()
{
if (log.lh.n > 0) {
write_log(); // Write modified blocks from cache to log
write_head(); // Write header to disk -- the real commit
install_trans(0); // Now install writes to home locations
log.lh.n = 0;
write_head(); // Erase the transaction from the log
}
}
首先是write_log。這基本上就是將所有存在于內(nèi)存中的log header中的block編號(hào)對(duì)應(yīng)的block，從block cache寫入到磁盤上的log區(qū)域中（注，也就是將變化先從內(nèi)存拷貝到log中）。
write_head會(huì)將內(nèi)存中的log header寫入到磁盤中。
// Copy modified blocks from cache to log.
static void
write_log(void)
{
int tail;
for (tail = 0; tail < log.lh.n; tail++) {
struct buf *to = bread(log.dev, log.start+tail+1); // log block
struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block
memmove(to->data, from->data, BSIZE);
bwrite(to); // write the log
brelse(from);
brelse(to);
}
}
依次遍歷log中記錄的block，并寫入到log中。它首先讀出log block，將cache中的block拷貝到log block，最后再將log block寫回到磁盤中。這樣可以確保需要寫入的block都記錄在文件系統(tǒng)的log區(qū)域中。
但是在這個(gè)位置，我們還沒有commit，現(xiàn)在我們只是將block存放在了log中。如果我們?cè)谶@個(gè)位置也就是在write_head之前crash了，那么最終的表現(xiàn)就像是transaction從來沒有發(fā)生過。
接下來看一下write_head函數(shù)，我之前將write_head稱為commit point。
// Write in-memory log header to disk.
// This is the true point at which the
// current transaction commits.
static void
write_head(void)
{
struct buf *buf = bread(log.dev, log.start);
struct logheader *hb = (struct logheader *) (buf->data);
int i;
hb->n = log.lh.n;
for (i = 0; i < log.lh.n; i++) {
hb->block[i] = log.lh.block[i];
}
bwrite(buf);
brelse(buf);
}
上面的bwrite，就是真正的commit point. 在這部之前crash, 都會(huì)像transaction從來沒有發(fā)生過一樣。
install_trans實(shí)際上就是將block數(shù)據(jù)從log中拷貝到了實(shí)際的文件系統(tǒng)block中。當(dāng)然，可能在這里代碼的某個(gè)位置會(huì)出現(xiàn)問題，但是這應(yīng)該也沒問題，因?yàn)樵诨謴?fù)的時(shí)候，我們會(huì)從最開始重新執(zhí)行過。
災(zāi)難恢復(fù)
initlog基本上就是調(diào)用recover_from_log函數(shù)。
static void
recover_from_log(void)
{
read_head();
install_trans(1); // if committed, copy from log to disk
log.lh.n = 0;
write_head(); // clear the log
}
recover_from_log先調(diào)用read_head函數(shù)從磁盤中讀取header，之后調(diào)用install_trans函數(shù)。這個(gè)函數(shù)之前在commit函數(shù)中也調(diào)用過，它就是讀取log header中的n，然后根據(jù)n將所有的log block拷貝到文件系統(tǒng)的block中。recover_from_log在最后也會(huì)跟之前一樣清除log。
xv6文件系統(tǒng)的三個(gè)挑戰(zhàn)
1. Cache Eviction 問題
- 問題描述：當(dāng)進(jìn)行中的事務(wù)需要更新一個(gè)數(shù)據(jù)塊（如block 45），而緩沖區(qū)（buffer cache）已滿時(shí)，系統(tǒng)可能需要撤回（evict）這個(gè)剛剛更新的數(shù)據(jù)塊以騰出空間。如果這時(shí)直接將更新后的數(shù)據(jù)塊寫回磁盤，會(huì)違反事務(wù)的原子性和前寫規(guī)則（write ahead rule）。前寫規(guī)則要求在實(shí)際更新文件系統(tǒng)的數(shù)據(jù)塊之前，必須先將所有更改寫入日志。
- 解決方案：通過引用計(jì)數(shù)來“固定”（pin）相關(guān)的數(shù)據(jù)塊在緩沖區(qū)中，避免它們被撤回，直到相關(guān)的日志條目被寫入，從而保證了數(shù)據(jù)的一致性和事務(wù)的原子性。
2. 文件系統(tǒng)操作與日志大小的適配問題
- 問題描述：在XV6文件系統(tǒng)中，日志的大小是固定的（例如，30個(gè)數(shù)據(jù)塊），這意味著所有文件系統(tǒng)操作都必須適應(yīng)這個(gè)日志大小。如果一個(gè)操作嘗試寫入超過日志容量的數(shù)據(jù)塊，將違反前寫規(guī)則。
- 解決方案：將大的文件系統(tǒng)操作分割成多個(gè)小的操作，每個(gè)小操作作為獨(dú)立的事務(wù)處理，并逐個(gè)寫入日志。雖然這意味著大的寫操作不是原子的，但它遵守了不破壞文件系統(tǒng)一致性的原則。
3. 并發(fā)文件系統(tǒng)調(diào)用的挑戰(zhàn)
- 問題描述：如果有多個(gè)并發(fā)執(zhí)行的事務(wù)同時(shí)占用日志空間，可能會(huì)導(dǎo)致日志空間用盡，而沒有任何一個(gè)事務(wù)能夠完全完成。這種情況下，如果提交任何一個(gè)部分完成的事務(wù)，都將違反前寫規(guī)則，因?yàn)檫@樣會(huì)提交一個(gè)不完整的事務(wù)。
- 解決方案：XV6通過限制同時(shí)進(jìn)行的文件系統(tǒng)操作的數(shù)量來解決這個(gè)問題。如果當(dāng)前有太多操作正在執(zhí)行，在begin_op中, 系統(tǒng)會(huì)暫停新的文件系統(tǒng)操作，直到足夠多的操作完成并提交（commit）。這種方法有時(shí)被稱為“組提交”（group commit），因?yàn)樗试S多個(gè)操作像一個(gè)大事務(wù)一樣同時(shí)提交，確保它們要么全部成功，要么全部失敗，從而保證了事務(wù)的原子性和系統(tǒng)的一致性。
// called at the start of each FS system call.
void
begin_op(void)
{
acquire(&log.lock);
while(1){
if(log.committing){
sleep(&log, &log.lock);
} else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE){
// this op might exhaust log space; wait for commit.
sleep(&log, &log.lock);
} else {
log.outstanding += 1;
release(&log.lock);
break;
}
}
}
