106 OS homework 2-2 成果報告書
===
> 組長：B10415009、徐晟鈞
> 組員：B10415014、湯志超
> 組員：B10415042、蔡奇霖
> github: https://github.com/chengchunhsu/xv6-public
---
# 🙂 使用情境說明(包含流程圖)
我們打算增加保護文件系統(file system protection)的功能。
參考ZFS，我們將為文件系統添加一個重複區塊(ditto blocks)的概念，所謂ditto block如同字面意思，即為資料區塊的備份。實際上來說就是一個原文件inode的鏡像(mirror)，並讓指標(pointer)指向一個複製原始內容新的資料區(data blocks)。
(圖1 資料結構)
新增一個`checksum()`的函式，使其以inode作為argument產生一個數值。讓所有data block都以這個函式產生一個數值並儲存於自身資料區。
接著以後每次存取file的時候(call `ilock()`)，系統都會重新計算一次並與儲存資料內數值比較來校驗資料的正確性，若是不同則代表數據的損壞。
偵測到文件損壞後，則試圖在ditto block尋找之前備份完好的資料。
若是找到，則用它取代損壞的資料以及其他ditto block。若是找不到，則中止`ilock()`函式並返回錯誤訊息。
(圖二 救援inode流程圖)
---
# 😇 成功畫面
先使用`mkdir`創建一個路徑在xv6裡面。
再以`ls`確認是否有出現在root裡。
`ls`輸出內容依序為：
| FileName | DevNumber | InodeNumber | Child1 | Child2 | Checksum |
| :------: | :-------: | :---------: | :----: | :----: | :------: |
使用`idesignate`，將test標記為重要，將其內容備份至兩ditto blocks(`child1`、`child2`)中。
再以`ls`確認test的`child1`、`child2`是否已更新。
以`pchecksum`、`pinode`、`pcat`確認 test (inodeNumber=26)與其`child1 ` (inodeNumber=27)、`child2` (inodeNumber=28) checksum值、內容無異。
---
# 🏃 實作過程(修改哪些檔案[含圖片])
## Kernal
### stat.h
* 新增`T_DITTO`。
```clike=
#define T_DIR 1 // Directory
#define T_FILE 2 // File
#define T_DEV 3 // Device
#define T_DITTO 4 // Ditto inode
```
---
### param.h
- 將`NINODE`值由`50`改為`100`。
- 將`LOGSIZE`值由`MAXOPBLOCKS*3 (30)`改為`MAXOPBLOCKS*6 (60)`。
- 將`NBUF`值由`MAXOPBLOCKS*3 (30)`改為`MAXOPBLOCKS*6 (60)`。
- 將`FSSIZE`值由`1000`改為`2048`(=2mb)。
```clike=
#define NPROC 64 // maximum number of processes
#define KSTACKSIZE 4096 // size of per-process kernel stack
#define NCPU 8 // maximum number of CPUs
#define NOFILE 16 // open files per process
#define NFILE 100 // open files per system
#define NINODE 100 // maximum number of active i-nodes
#define NDEV 10 // maximum major device number
#define ROOTDEV 1 // device number of file system root disk
#define MAXARG 32 // max exec arguments
#define MAXOPBLOCKS 10 // max # of blocks any FS op writes
#define LOGSIZE (MAXOPBLOCKS*6) // max data blocks in on-disk log
#define NBUF (MAXOPBLOCKS*6) // size of disk block cache
#define FSSIZE 2048 // size of file system in blocks
```
---
### file.h
* 修改`inode`的定義，新增`child1`、`child2`、`checksum`。
```clike=
// in-memory copy of an 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];
short child1;
short child2;
uint checksum;
};
```
---
### fs.h
[](https://i.imgur.com/qcFhyZW.jpg)
* `NDIRECT`值由12改為10
```clike=
#define NDIRECT 10
```
* 修改dinode的定義，新增`child1`、`child2`、`checksum`。
```clike=
// On-disk inode structure
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
short child1;
short child2;
uint checksum;
};
```
* 於最後新增以下片段
```clike=
#define DITTO_LOWER 3 // 離root的level數 < 3，建立2個Ditto block
#define DITTO_HIGHER 6 // 3 < 離root的level數 < 6，建立1個Ditto blocks
enum {
REPLICA_SELF,
REPLICA_CHILD_1,
REPLICA_CHILD_2
} ditto_replica; // ditto副本類型
#define E_CORRUPTED -10 // 傳回此值代表文件損壞
```
----
### fs.c
* 修改`ilock`、`writei`、`iupdate`等函式來處理子節點的更新及寫入。
* 新增`ilock_trans`、`ilock_ext`、`writei_ext`、`cupdate`等函式來更新子節點、`checksums`值，並使kernal在recovery階段時不需去計算`checksum`值且傳回error。
* 新增`iduplicate`、`irescue`等函式來執行文件備份及救援。
* 新增`ichecksum`函式來計算`inode`的`checksums`值
#### ichecksum()
```clike=
//Compute inode checksum
uint
ichecksum(struct inode *ip) {
// We do not want to checksum files like console
if (ip->type == T_DEV) // 註1
return 0;
unsigned int buf[512];
char* cbuf = (char*) buf; // sets cbuf to point to buf's pointee
uint n = sizeof(buf);
uint off = 0;
uint r, i;
unsigned int checksum = 0;
memset((void*) cbuf, 0, n); // 將cbuf全部值設為0
unsigned int * bp;
// readi不停將ip值寫入cbuf中(一次大小為n):
// for迴圈遍歷buf(cbuf)中所有uint值:
// 一一取出buf中的值，checksum ^= *bp (XOR運算)
// bp指針隨for迴圈持續前進，直到迴圈跳出
while ((r = readi(ip, cbuf, off, n)) > 0) { // 將ip中的資料依序讀入cbuf中(註2)
off += r; // r == n
bp = (unsigned int *)buf; // sets bp to point to buf's pointee
// 讀取存在buf中的每個unsigned int
for (i = 0; i < sizeof(buf) / sizeof(uint); i++){
// buf == char* cbuf
// *bp == (unsigned int *)buf
checksum ^= *bp;
bp++;
}
memset((void *) cbuf, 0, n); // 將cbuf全部值重設為0
}
return checksum;
}
```
> 註1
> ```clike=
> # define T_DIR 1 // Directory
> # define T_FILE 2 // File
> # define T_DEV 3 // Device
> # define T_DITTO 4 // Ditto inode
> ```
>
>
> 註2
> readi(struct inode *ip, char *dst, uint off, uint n)
> reads **n** blocks in inode **ip** starting from **off** into **dst**, return **n** or **-1**(failed)
---
* 修改`iupdate`函式。
* 新增`iupdate_ext`函式，並將`iupdate`實作移至此函式內。
* 新增`cupdate`，用來更新`inode`的`child1`、`child2`值。
#### iupdate()
```clike=
void
iupdate(struct inode *ip)
{
iupdate_ext(ip, 0);
}
```
#### iupdate_ext()
將`inode`值寫入`dinode` (mermory → disk) 中。
`skip`值為`0`時須更新`inode`的`child`值，`1`則否。
```clike=
void iupdate_ext(struct inode *ip, uint skip)
{
struct buf *bp;
struct dinode *dip;
bp = bread(ip->dev, IBLOCK(ip->inum, sb));
dip = (struct dinode *)bp->data + ip->inum % IPB;
dip->type = ip->type;
dip->major = ip->major;
dip->minor = ip->minor;
dip->nlink = ip->nlink;
dip->size = ip->size;
dip->child1 = ip->child1; // 將inode的child1值寫入dinode
dip->child2 = ip->child2; // 將inode的child2值寫入dinode
ip->checksum = ichecksum(ip); // 更新inode的checksum值
dip->checksum = ip->checksum;
memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
log_write(bp);
brelse(bp);
// 如果skip值為0，則須更新child值
if (skip == 0)
{
if (ip->child1)
cupdate(ip, iget(ip->dev, ip->child1));
if (ip->child2)
cupdate(ip, iget(ip->dev, ip->child2));
}
}
```
#### cupdate()
更新`inode* ip`的`child1`、`child2`值。
```clike=
void cupdate(struct inode *ip, struct inode *ic)
{
ilock_ext(ic, 0);
// 檢查ic是否為ditto block
if (ic->type != T_DITTO)
panic("trying to update a \"child\" that is not a ditto block!\n");
struct buf *bp;
struct dinode *dic;
bp = bread(ip->dev, IBLOCK(ip->inum, sb));
dic = (struct dinode *)bp->data + ic->inum % IPB;
dic->type = ic->type;
dic->major = ic->major;
dic->minor = ic->minor;
dic->nlink = 1;
ic->size = ip->size; // 直接沿用 parent size
dic->size = ic->size;
dic->child1 = ic->child1;
dic->child2 = ic->child2;
ic->checksum = ip->checksum; // 直接沿用 parent checksum
dic->checksum = ic->checksum;
memmove(dic->addrs, ic->addrs, sizeof(ic->addrs));
log_write(bp);
brelse(bp);
iunlock(ic);
}
```
---
- 修改`ilock`函式。
- 新增`ilock_ext`、`ilock_trans`函式。
- 將`ilock`實作移至`ilock_ext`函式內。
#### ilock()
```clike=
int
ilock (struct inode *ip)
{
return ilock_ext(ip, 1);
}
```
#### ilock_ext()
lock指定的`inode`，確保其在讀取或寫入過程中不會產生 deadlock 或 races 現象。
大部分是原本`ilock`內容，加入了`child1`、`child2`、`checksum`值的同步。
此外還需要檢查`inode`的`checksum`值是否正確，若否則須嘗試修正。
```clike=
int ilock_ext(struct inode *ip, int checksum)
{
struct buf *bp;
struct dinode *dip;
if (ip == 0 || ip->ref < 1)
panic("ilock");
acquiresleep(&ip->lock);
if (ip->valid == 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;
ip->child1 = dip->child1; // 同步child1值
ip->child2 = dip->child2; // 同步child2值
ip->checksum = dip->checksum; // 同步checksum值
memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
brelse(bp);
// Initialize some checking variables
uint replica = REPLICA_SELF;
ushort rinum;
struct inode *rinode;
if (checksum == 0)
goto zc_success;
zc_verify:
if (ichecksum(ip) == ip->checksum) { // 檢查ip之checksum值是否正確
goto zc_success; // 符合
} else { // 不符合 -> 試著從child中獲取備份
replica++; // REPLICA_SELF -> REPLICA_CHILD_1 -> REPLICA_CHILD_2
// 檢查備份是否存在 (child1、child2)
if (replica == REPLICA_CHILD_1)
rinum = ip->child1;
else if (replica == REPLICA_CHILD_2)
rinum = ip->child2;
else
goto zc_failure;
// 獲取備份之inode number是否為有效值
if (!rinum)
goto zc_failure;
// 透過iget取得該備份inode的內容，並lock它
rinode = iget(ip->dev, rinum);
if (ilock(rinode) == 0)
{
iunlock(rinode); // 解鎖rinode
iunlock(ip); // 解鎖ip
return rinum; // 傳回rinode的inum
}
goto zc_verify; // verify again
}
zc_failure: // 失敗
iunlock(ip); // 解鎖ip
return E_CORRUPTED; // 告知caller檔案已損壞
zc_success: // 同步成功
ip->valid = 1; // ip已與對應dinode完成同步
if (ip->type == 0) // 檢查inode type是否為正常
panic("ilock: no type");
}
return 0;
}
```
#### ilock_trans()
在傳輸(transaction)前鎖定`inode *ip`，成功後傳回`0`。
若文件損壞則從child取得備份，嘗試救援。
若依然失敗，則呼叫panic錯誤訊息。
```clike=
int
ilock_trans(struct inode *ip)
{
int r = ilock(ip);
struct inode *ic;
if (r == 0) return 0; // ilock(ip) 執行成功，傳回0
if (r == E_CORRUPTED) return E_CORRUPTED; // ip已損壞，傳回E_CORRUPTED
if (r > 0) { // 獲得備份inode之inum
ic = iget(ip->dev, r); // 取得該備份inode之內容，並存入ic中
irescue(ip, ic); // 利用ic修正ip
}
r = ilock(ip); // 救援後再次嘗試ilock(ip)
if (r == 0) return 0; // ilock(ip)執行成功，傳回0
// 救援後依然失敗，呼叫panic
panic("ilock_trans attempted to recover but still failed to unlock");
}
```
---
#### irescue()
從`replica inode`複製`size`、`checksum`、和`inode data`至`parent inode`中。
以修復`parent inode`。
```clike=
void
irescue(struct inode *ip, struct inode *rinode)
{
int max = ((LOGSIZE-1-1-2) / 4) * 512;
int i = 0;
uint off = 0;
ilock_ext(rinode, 0); // 鎖定rinode
ilock_ext(ip, 0); // 鎖定ip
int n = ip->size;
while(i < n){
int n1 = n - i;
if(n1 > max)
n1 = max; // 一個循環最多遍歷max大小的資料
begin_trans(); // begin transaction
iduplicate(rinode, ip, off, n1); // 從rinode的off位址複製n1大小的data至ip中
commit_trans(); // end transaction
off += n1;
i += n1;
}
iunlock(rinode); // 解鎖rinode
iunlock(ip); // 解鎖ip
}
```
#### iduplicate()
從`inode *src`複製`size`、`checksum`、和`inode data`至`inode *dst`中。
```clike=
void
iduplicate(struct inode *src, struct inode *dst, uint off, uint ntotal)
{
char buf[512];
uint n = sizeof(buf);
memset((void*) buf, 0, n);
uint r;
uint _off = off;
dst->checksum = src->checksum; // 同步checksum值
dst->size = src->size; // 同步size值
// 檢查讀取成敗及是否out of range後，將buf內容寫入dst中
while (((r = readi(src, buf, off, n)) > 0) && (off < (ntotal+_off)) ) {
writei_ext(dst, buf, off, r, 1);
off += r;
memset((void *) buf, 0, n);
}
}
```
---
* 修改`writei()`函式。
* 新增`write_ext()`函式。
* 將`writei()`實做移至`write_ext()`函式。
#### **write_ext()**
* 以`writei()`為範本的更改，新增了parameter `skip`，並根據`skip`來決定是否要複寫`child1`與`child2`。
```clike=
// 依據skip來判斷是否要連child都去做複寫
if (skip == 0) {
if (ip->child1) {
ci = iget(ip->dev, ip->child1);
ilock_ext(ci, 0);
// 注意呼叫的是writei()而非write_ext()，亦即不會再有複寫，防止無限循環
writei(ci, _src, _off, n);
iunlock(ci);
}
if (ip->child2) {
ci = iget(ip->dev, ip->child2);
ilock_ext(ci, 0);
// 注意呼叫的是writei()而非write_ext()，亦即不會再有複寫，防止無限循環
writei(ci, _src, _off, n);
iunlock(ci);
}
}
```
* 寫入前先檢查是否會寫入到不合法的區域，寫入後檢查是否需要更新檔案資訊。
```clike=
// 如果是device則另外處理
if(ip->type == T_DEV){
// 如果是非法的裝置，則回傳-1代表失敗
if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write)
return -1;
// 如果是合法的裝置，則就由負責的去寫入
return devsw[ip->major].write(ip, src, n);
}
// 如果被寫入的起始位址超過檔案範圍，或者寫入大小為負數，則傳回-1代表失敗
if(off > ip->size || off + n < off)
return -1;
// 如果寫入後的大小超越最大單檔限制，則傳回-1代表失敗
if(off + n > MAXFILE*BSIZE)
return -1;
```
```clike=
// ditto block的資訊會由parent更新，所以提早返回
if (ip->type == T_DITTO)
return n;
// 若寫入後超過原本大小，則更新大小資訊
if (n > 0 && off > ip->size)
ip->size = off;
// 將修改過後inode寫入disk
if (ip->type != T_DEV)
iupdate_ext(ip, skip);
```
[](https://i.imgur.com/cCCr1Ku.jpg)
---
#### **writei()**
* 修改使其成為呼叫`write_ext()`的介面，新增的`skip`參數預設為`0`，這樣便與呼叫`writei()`的結果一樣。
[](https://i.imgur.com/sfVZTwN.jpg)
---
* 修改`namex()`、`namei()`、`nameiparent()`函式。
* 新增`namei_ext()`、`nameiparent_ext()`、`namei_trans()`、` nameiparent_trans()`函式。
* 將`namei()`、`nameiparent()`實做移至`namei_ext()`、`nameiparent_ext()`函式。
#### **namex()**
* 為name系列函式的最底層，`namei()`等就是呼叫不同參數的`namex()`的介面，實際上根據路徑將`inode`找出來就是在這邊。
* namei 系列和 nameiparent 系列差別即為 parameter `int nameiparent`的差別，此參數為`1`時會提早一層跳出迴圈，藉此得到傳入`path`的母目錄。
* 這邊因為recover的關係，需要使用不同的`ilock`。
```clike=
// 若nameiparent為1，則在結束前一個迴圈unlock ip並跳出
if(nameiparent && *path == '\0'){
// 提早離開
iunlock(ip);
return ip;
}
```
```clike=
// 依據trans來判斷要用ilock_trans()還是ilock()
if (trans) {
if (ilock_trans(ip) != 0) return 0; // recover和lock失敗
} else {
if (ilock(ip) != 0) return 0; // lock失敗
}
```
[](https://i.imgur.com/NED5zQk.jpg)
---
#### **namei_ext()**
* `namei_ext()`為因應`namex()`修改而增加的介面(`原為namei()`)，預設需要多傳入`namex()`多了的參數`trans`。
[](https://i.imgur.com/GPBtkfI.jpg)
---
#### **nameiparent_ext()**
* `nameiparent_ext()`為因應`namex()`修改而增加的介面(原為`nameiparent()`)，預設需要多傳入`namex()`多了的參數`trans`。
[](https://i.imgur.com/DiPVJEq.jpg)
---
#### **namei()**
* 因`namei()`需提供與原本相符的功能，所以必須使`namex()`的`trans=0`，也就是呼叫`namei_ext()`時`trans`傳入`0`。
[](https://i.imgur.com/NEaZcqA.jpg)
---
#### **nameiparent()**
* 因`nameiparent()`需提供與原本相符的功能，所以必須使`namex()`的`trans=0`，也就是呼叫nameiparent_ext時`trans`傳入`0`。
[](https://i.imgur.com/C2jdq5N.jpg)
---
#### **namei_trans()**
* `namei_trans()`則與`namei()`相反，為`trans`傳入`1`的版本。
[](https://i.imgur.com/dmhKXck.jpg)
---
#### **nameiparent_trans()**
* `nameiparent_trans()`則與`nameiparent()`相反，為`trans`傳入`1`的版本。
[](https://i.imgur.com/3hTpZTk.jpg)
---
#### **distance_to_root()**
* `distance_to_root()`為新增的函式，傳入一個合法的`path`，並利用傳進來的`path`計算其距離`root`有多少層，藉以實做3層內2個，或者6層內1個`ditto block`等功能。
```clike=
// 利用..不斷向上一層爬
while((ip = dirlookup(dp,"..", &off) ) != 0){
inum1 = dp->inum;
iunlockput(dp); // 得到父目錄ip，所以紀錄完inum後，dp就不需要，可以解鎖並釋放了
dp = ip;
ilock_trans(dp);
inum2 = dp->inum;
// 找到root的話
if(inum1 == inum2){
iunlockput(dp); // 解鎖inode並釋放
break; // 已經找到，中止迴圈
}
counter++; // 沒找到root則counter+1，繼續往上一層找
off = 0;
}
```
[](https://i.imgur.com/BgKLchQ.jpg)
---
### exec.c
* 將`namei(path)`改為`namei_trans(path)`。
```clike=
...
if((ip = namei_trans(path)) == 0){
end_op();
cprintf("exec: fail\n");
return -1;
}
...
```
* 將`ilock(ip)`改為`ilock_trans(ip)`，並在錯誤時return`E_CORRUPTED`值。
```clike=
if (ilock_trans(ip))
return E_CORRUPTED;
```
---
### file.c
#### filestat()
* 將`ilock(f->ip)`改為`ilock_trans(f->ip)`，並在錯誤時return`E_CORRUPTED`值。
```clike=
...
if (ilock_trans(f->ip) == E_CORRUPTED)
return E_CORRUPTED;
...
```
#### fileread()
* 將`ilock(f->ip)`改為`ilock_trans(f->ip)`
#### filewrite()
* 將`ilock(ip)`改為`ilock_trans(ip)`，並在錯誤時return`E_CORRUPTED`值。
```clike=
...
if (ilock_trans(f->ip) == E_CORRUPTED)
return E_CORRUPTED;
...
```
---
### mkfs.c
- 修改`main`函式，加入計算`checksum`值，及建置`ditto blocks`的片段。
- 新增`ichecksum`、`readi`、`rblock`函式，用來計算checksum值。
#### main()
* 初始化file system。
* 初始化`root inode`的`checksum`值及`ditto blocks`。
```clike=
int main(int argc, char *argv[])
{
int i, cc, fd;
uint rootino, inum, off;
struct dirent de;
char buf[BSIZE];
struct dinode din, din2;
unsigned int checksum;
static_assert(sizeof(int) == 4, "Integers must be 4 bytes!");
if (argc < 2)
{
fprintf(stderr, "Usage: mkfs fs.img files...\n");
exit(1);
}
assert((BSIZE % sizeof(struct dinode)) == 0);
assert((BSIZE % sizeof(struct dirent)) == 0);
fsfd = open(argv[1], O_RDWR | O_CREAT | O_TRUNC, 0666);
if (fsfd < 0)
{
perror(argv[1]);
exit(1);
}
// 1 fs block = 1 disk sector
nmeta = 2 + nlog + ninodeblocks + nbitmap;
nblocks = FSSIZE - nmeta;
sb.size = xint(FSSIZE);
sb.nblocks = xint(nblocks);
sb.ninodes = xint(NINODES);
sb.nlog = xint(nlog);
sb.logstart = xint(2);
sb.inodestart = xint(2 + nlog);
sb.bmapstart = xint(2 + nlog + ninodeblocks);
freeblock = nmeta; // the first free block that we can allocate
for (i = 0; i < FSSIZE; i++)
wsect(i, zeroes);
memset(buf, 0, sizeof(buf));
memmove(buf, &sb, sizeof(sb));
wsect(1, buf);
rootino = ialloc(T_DIR);
assert(rootino == ROOTINO);
bzero(&de, sizeof(de));
de.inum = xshort(rootino);
strcpy(de.name, ".");
iappend(rootino, &de, sizeof(de));
bzero(&de, sizeof(de));
de.inum = xshort(rootino);
strcpy(de.name, "..");
iappend(rootino, &de, sizeof(de));
for (i = 2; i < argc; i++)
{
assert(index(argv[i], '/') == 0);
if ((fd = open(argv[i], 0)) < 0)
{
perror(argv[i]);
exit(1);
}
// Skip leading _ in name when writing to file system.
// The binaries are named _rm, _cat, etc. to keep the
// build operating system from trying to execute them
// in place of system binaries like rm and cat.
if (argv[i][0] == '_')
++argv[i];
inum = ialloc(T_FILE);
bzero(&de, sizeof(de));
de.inum = xshort(inum);
strncpy(de.name, argv[i], DIRSIZ);
iappend(rootino, &de, sizeof(de));
// 計算fd的checksum值
checksum = 0;
int counter2 = 0;
char *cbuf = (char *)buf;
memset((void *)cbuf, 0, sizeof(buf));
while ((cc = read(fd, buf, sizeof(buf))) > 0)
{
counter2 += cc;
uint i;
unsigned int *bp = (unsigned int *)buf;
char *cbuf = (char *)buf;
memset((void *)cbuf + cc, 0, sizeof(buf) - cc);
for (i = 0; i < sizeof(buf) / sizeof(uint); i++)
{
checksum ^= *bp;
bp++;
}
iappend(inum, buf, cc);
}
// 讀取剛剛寫入的inode並將其存入din2中
// 計算並更新din2的checksum值
// 將din2的值寫回inode
rinode(inum, &din2);
char temp_buf[BSIZE];
readi(&din2, (char *)temp_buf, 0, BSIZE);
unsigned int checksum2 = 0;
checksum2 = ichecksum(&din2);
din2.checksum = xint(checksum2);
winode(inum, &din2);
close(fd);
}
// 讀取root inode並將其存入din中
// 計算並更新din的checksum值
// 將din的值寫回root inode
rinode(rootino, &din); // 讀取root inode並將其存入din中
off = xint(din.size);
off = ((off / BSIZE) + 1) * BSIZE;
din.size = xint(off); // 更新din.size值
checksum = ichecksum(&din);
din.checksum = xint(checksum); // 更新din.checksum值
winode(rootino, &din); // 將din內容寫回至root inode中
// 建立root inode的ditto blocks
rinode(rootino, &din); // 讀取root inode並將其存入din中
uint ditto_inum1, ditto_inum2;
struct dinode ditto_din1, ditto_din2;
ditto_inum1 = ialloc(T_DITTO); // alloc ditto block1
ditto_inum2 = ialloc(T_DITTO); // alloc ditto block2
copy_dinode_content(&din, ditto_inum1); // 將din內容拷貝至ditto block1中
rinode(ditto_inum1, &ditto_din1); // 讀取ditto block1並將其存入ditto_din1中
ditto_din1.checksum = din.checksum; // 完成checksum值同步 (din -> ditto_din1)
ditto_din1.size = din.size; // 完成size值同步 (din -> ditto_din1)
winode(ditto_inum1, &ditto_din1); // 將ditto_din1內容寫回至ditto block1中
copy_dinode_content(&din, ditto_inum2); // 同上
rinode(ditto_inum2, &ditto_din2);
ditto_din2.checksum = din.checksum;
ditto_din2.size = din.size;
winode(ditto_inum2, &ditto_din2);
rinode(rootino, &din); // 讀取root inode並將其存入din中
din.child1 = xshort(ditto_inum1); // 更新din.child1
din.child2 = xshort(ditto_inum2); // 更新din.child2
winode(rootino, &din); // 將din內容寫回至root inode中
//writes the bitmap to fs.img
balloc(freeblock);
exit(0);
}
```
----
#### ichecksum()
同[上](https://hackmd.io/EYRgLAhgxsDsCmBaAnMiATRYAMYkA4IBmZRbZeMdCfAVmzliA===?view#ichecksum)，不再贅述。
```clike=
uint ichecksum(struct dinode *din)
{
unsigned int buf[512];
char *cbuf = (char *)buf;
uint n = sizeof(buf);
uint off = 0;
uint r, i;
unsigned int checksum = 0;
memset((void *)cbuf, 0, n);
unsigned int *bp;
while ((r = readi(din, cbuf, off, n)) > 0)
{
off += r;
bp = (unsigned int *)buf;
for (i = 0; i < sizeof(buf) / sizeof(uint); i++)
{
checksum ^= *bp;
bp++;
}
memset((void *)cbuf, 0, n);
}
return checksum;
}
```
----
#### readi()
將`dinode *din`內 data 存入`*dst`中。
```clike=
int readi(struct dinode *din, char *dst, uint off, uint n)
{
uint tot, m, fbn;
char data[BSIZE];
char *cdata = (char *)data;
// 檢查din是否為device，是則報錯
if (xint(din->type) == T_DEV)
{
fprintf(stderr, "Reading DEV file. Not implemented in readi in mkfs\n");
return -1;
}
// 檢查是否out of range，是則報錯
if (off > xint(din->size) || off + n < off)
{
return -1;
}
// 檢查 off + n 是否out of range，是則重置n值
if (off + n > xint(din->size))
{
n = xint(din->size) - off;
}
// 將din內data存入dst中
for (tot = 0; tot < n; tot += m, off += m, dst += m)
{
fbn = off / BSIZE;
rblock(din, fbn, (char *)data);
m = min(n - tot, BSIZE - off % BSIZE);
memmove(dst, cdata + off % BSIZE, m);
}
return n;
}
```
----
#### rblock()
將`dinode *din`的第 bn 個 block 內容存入`char *dst`中。
```clike=
void rblock(struct dinode *din, uint bn, char *dst)
{
uint indirect[NINDIRECT];
uint addr;
// 若bn < NDIRECT，開始寫入dst
if (bn < NDIRECT)
{
rsect(xint(din->addrs[bn]), dst);
return;
}
// 將bn轉為indirect block之編號
bn -= NDIRECT;
// 若bn < NINDIRECT，開始寫入dst
if (bn < NINDIRECT)
{
rsect(xint(din->addrs[NDIRECT]), (char *)indirect);
addr = xint(indirect[bn]);
rsect(addr, dst);
return;
}
}
```
----
#### copy_dinode_content()
複製`dinode *src`內容至`dst`。
```clike=
void copy_dinode_content(struct dinode *src, uint dst)
{
char buf[512];
char *cbuf = (char *)buf;
uint n = sizeof(buf);
uint off = 0;
uint r;
memset((void *)cbuf, 0, n); // 清空cbuf
// 檢查讀取是否成功
while ((r = readi(src, cbuf, off, n)) > 0)
{
off += r; // 更新off值
iappend(dst, cbuf, r); // 寫入dst
memset((void *)cbuf, 0, n); // 清空cbuf
}
}
```
---
## Syscall Handler
### usys.s
* 新增syscall：
* iopen
* cps
* ichecksum
* duplicate
* forceopen
---
### syscall.c
* 將`iopen` `cps`等syscall加進去。
---
### sysfile.c
#### sys_ichecksum()
* 確認傳入參數無誤後會call `ichecksum`(實作在fs.c)，計算檢驗值大小，並更新回file。
```clike=
// 抓取該dev與inum，若錯誤會回傳-1。
if (argint(0, &dev) < 0 || argint(1, &inum) < 0)
return -1;
// 用dev.inum去找該inode，若沒找到會return 0，當iget==0，則會回傳-2。
if(ip=iget((uint)dev,inum)==0)
return -2;
// 判斷是否已損毀，判斷無誤後更新ip的ichecksum。
if (ilock_trans(ip) == E_CORRUPTED)
return E_CORRUPTED;
```
---
#### sys_duplicate()
* 確認傳入參數無誤後會call `duplicate`(實作在fs.c)，備份此檔案到`child1`、`child2`。備份成功會return 0。
```clike=
// 抓取該path與ndittos，並直接duplicate child給ip，如果已存在child會直接回傳-1。
if (argstr(0, &path) < 0 || argint(1, &ndittos) < 0 ||
(ip = duplicate(path, ndittos)) == 0)
{
return -1;
}
```
---
#### sys_forceopen()
* 開啟檔案並回傳此檔案inode。
* 相較於`sys_open`，`sys_forceopen`不會檢查file是否 CORRUPTED。
```clike=
// 抓取該dev與inum。
if (argint(0, &path) < 0 || argint(1, &&omode) < 0)
return -1;
```
---
#### sys_iopen()
* 打開對應`devNumber`、`inodeNumber`的file。
```clike=
// 抓取該dev與inum。
if (argint(0, &dev) < 0 || argint(1, &inum) < 0)
return -1;
// 用dev.inum去找該inode 若沒找到會return 0。
if(ip=iget((uint)dev,inum)==0)
return -2;
```
---
#### duplicate()
* 先確認`path`輸入正確，獲得`ip`且此`ip`不是`CORRUPTED`後建立`ditto block`。
* 依據`ndittos`的值，建立1至2個`child`，若已存在`child`則return 0。
* 最後call `ipropagate`更新ip的值
---
#### ipropagate()
* `max`為`ditto block`的最大size
* 如果`ip->child`不是0，會call `iduplicate`來複製`ip` `inode`的資訊到`ic`。
---
#### create()
* `create`將新創的`inode`新增在`path`下。
* call `nameiparent_trans`來找到device中的`path`路徑。
* call `dirlook up`來找到memory中的`path`路徑。
* call `ialloc` 來為`inode` allocate一段空間，並更新其值。
* call `iupdate` 來同步`inode`和`dinode`內容。
---
### proc.c
* 新增`cps`函式，印出正在執行的process。
---
## C Library
### cat.c
* 新增`-f`的功能，在argv[1]打`-f`，可以`forceopen`的方式來打開file。
---
---
### user.h
宣告syscall。
---
---
### ulib.c
#### hasdittos()
* 檢驗此path的file是否已經有ditto block(備份`child1`、`child2`)。
``` clike=
// 如果已存在一個child以上則直接return 1。
if(st.child)
return 1
```
---
---
## Application
### sh.c
* 在`runcmd`新增file CORRUPTED時的錯誤訊息。
```clike=
if(r==E_CORRUPTED) //確認該檔案是否已經損毀。
printf(2,": %s is corrupted",ecmd->argv[0]);
```
---
---
### ls.c
* 在原有檔案無法開啟的錯誤訊息中，新增CORRUPTED的提示。
* 開啟檔案輸出訊息新增child1、child2、checksum值。
---
---
### 新增 User Command 實作及使用
#### 1. idesignate.c
* Usage：idesignate [path] [improtance]
* `improtance`：可為 1 or 2。
* 功用：允許使用者以透過此指令將檔案標記為 "重要"，並選擇使用 1 或 2 個 ditto blocks 保護文件。
```clike=
//確認該file是否有ditto block。
if(hasdittos(argv[1]) == 0)
{
//依據argv[2]之值建立child1，2。
r = duplicate(argv[1], atoi(argv[2]));
}
```
---
#### 2. pchecksum.c
* Usage：pchecksum [devNumber] [iNodeNumber]。
* `devNumber`：通常為1。
* `iNodeNumber`：可使用ls得知。
* 功用：可顯示指定文件的 device number 及 inode number。
```clike=
//將devnum inum 從字串轉數字
dev = atoi(devnum)
iint = atoi(inum)
//計算並確認其ichecksum執行過程中沒有錯誤
if ((checksum = ichecksum(dev, iint)) < 0)
//輸出該inode的ichecksum值
printf(1, "%d %d: %x\n", dev, iint, checksum)
```
---
#### 3. pinode.c
* Usage：pinode [devNumber] [iNodeNumber]。
* `devNumber`：通常為1。
* `iNodeNumber`：可使用ls得知。
* 功用：可允許使用者藉由指定文件的 device number 或 inode number 來執行ls功能。
```clike=
// 用iopen抓到此inode的值。
if ((fd = iopen(dev, iint)) < 0
{
printf(2, "pinode: cannot open inode %d on dev %d\n", iint, dev);
return;
}
// 用fstat取得指定inode的資訊。
if (fstat(fd, &st) < 0)
{
printf(2, "pinode： cannot stat inode %d on dev %d (fd=%d)\n", iint, dev, fd);
close(fd);
return;
}
```
---
#### 4. pcat.c
* Usage：pcat [devNumber][iNodeNumber]。
* `devNumber`：通常為1。
* `iNodeNumber`：可使用ls得知。
* 功用：可允許使用者藉由指定文件的 device number或inode number來執行cat功能，從buffer寫至標準輸出，可用來cat ditto blocks。
```clike=
// 從fd讀檔案到buf 每次讀 sizeof(buf)。
while((n = read(fd, buf, sizeof(buf))) > 0
{
// 將buf輸出到標準輸出。
write(1, buf, n);
printf(1,"%s",buf);
}
```
---
#### 5. ps.c
* Usage：ps
- 功用：印出現正執行的process及其狀態。
----
# 😎 結論
本來這次的實做宗旨是為了增加 file system 的安全機制，結果卻多次被 xv6 code 中原有的安全檢查給提示自己的修改錯誤，讓我明白 file system 牽一髮而動全身，實做起來相當不易，也讓我認識到了作業系統之精妙與其心細。
透過這次實做 file system 的安全備份功能 ditto block，我明白了為了提高安全性，勢必得有一些犧牲，除了備份需要犧牲額外的空間外，也需要為了 dittoblock 而減少原本的最大定址數量。真的是做了才知道，讓我學習到了很多，也進一步明白現今的作業系統是多少人智慧的結晶。
---
# 📅 組員分工
:::success
| 組員＼工作 | kernal | Syacall | C libary | Applicaion |
| ----- | ------ | ------- | -------- | ---------- |
| 蔡奇霖 | ✓ | | | |
| 徐晟鈞 | ✓ | | ✓ | |
| 湯智超 | | ✓ | ✓ | ✓ |
:::
---
Google Drive
Gist
Clipboard
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
