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。




#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)。













#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。



















    // 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

NDIRECT值由12改為10


    #define NDIRECT 10

修改dinode的定義，新增child1、child2、checksum。













    // 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;
    };

於最後新增以下片段










	#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()






































//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




# 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()





void
iupdate(struct inode *ip)
{
  iupdate_ext(ip, 0);
}

iupdate_ext()

將inode值寫入dinode (mermory → disk) 中。

skip值為0時須更新inode的child值，1則否。































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值。





























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()





int
ilock (struct inode *ip)
{
  return ilock_ext(ip, 1);
}

ilock_ext()

lock指定的inode，確保其在讀取或寫入過程中不會產生 deadlock 或 races 現象。

大部分是原本ilock內容，加入了child1、child2、checksum值的同步。

此外還需要檢查inode的checksum值是否正確，若否則須嘗試修正。













































































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錯誤訊息。























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。






























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中。




















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。


















  // 依據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);
    }
  }

寫入前先檢查是否會寫入到不合法的區域，寫入後檢查是否需要更新檔案資訊。















    // 如果是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;











  // 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);

writei()

修改使其成為呼叫write_ext()的介面，新增的skip參數預設為0，這樣便與呼叫writei()的結果一樣。

修改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。






	// 若nameiparent為1，則在結束前一個迴圈unlock ip並跳出
    if(nameiparent && *path == '\0'){
      // 提早離開
      iunlock(ip);
      return ip;
    }






	// 依據trans來判斷要用ilock_trans()還是ilock()
    if (trans) {
      if (ilock_trans(ip) != 0) return 0;	// recover和lock失敗
    } else {
      if (ilock(ip) != 0) return 0;			// lock失敗
    }

namei_ext()

namei_ext()為因應namex()修改而增加的介面(原為namei())，預設需要多傳入namex()多了的參數trans。

nameiparent_ext()

nameiparent_ext()為因應namex()修改而增加的介面(原為nameiparent())，預設需要多傳入namex()多了的參數trans。

namei()

因namei()需提供與原本相符的功能，所以必須使namex()的trans=0，也就是呼叫namei_ext()時trans傳入0。

nameiparent()

因nameiparent()需提供與原本相符的功能，所以必須使namex()的trans=0，也就是呼叫nameiparent_ext時trans傳入0。

namei_trans()

namei_trans()則與namei()相反，為trans傳入1的版本。

nameiparent_trans()

nameiparent_trans()則與nameiparent()相反，為trans傳入1的版本。

distance_to_root()

distance_to_root()為新增的函式，傳入一個合法的path，並利用傳進來的path計算其距離root有多少層，藉以實做3層內2個，或者6層內1個ditto block等功能。
















    // 利用..不斷向上一層爬
    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;
    }

exec.c

將namei(path)改為namei_trans(path)。







...
if((ip = namei_trans(path)) == 0){
    end_op();
    cprintf("exec: fail\n");
    return -1;
}
 ...

將ilock(ip)改為ilock_trans(ip)，並在錯誤時returnE_CORRUPTED值。


  if (ilock_trans(ip))
    return E_CORRUPTED;

file.c

filestat()

將ilock(f->ip)改為ilock_trans(f->ip)，並在錯誤時returnE_CORRUPTED值。




...	
    if (ilock_trans(f->ip) == E_CORRUPTED)
      return E_CORRUPTED;
...

fileread()

將ilock(f->ip)改為ilock_trans(f->ip)

filewrite()

將ilock(ip)改為ilock_trans(ip)，並在錯誤時returnE_CORRUPTED值。




...
	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。
































































































































































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()

同上，不再贅述。

























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中。



































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中。
























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。

















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。











// 抓取該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。







// 抓取該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。



// 抓取該dev與inum。
if (argint(0, &path) < 0 || argint(1, &&omode) < 0)
    return -1;

sys_iopen()

打開對應devNumber、inodeNumber的file。







// 抓取該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)。



// 如果已存在一個child以上則直接return 1。
if(st.child)
    return 1

Application

sh.c

在runcmd新增file CORRUPTED時的錯誤訊息。


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 保護文件。






//確認該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。







//將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功能。














// 用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。







  // 從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 而減少原本的最大定址數量。真的是做了才知道，讓我學習到了很多，也進一步明白現今的作業系統是多少人智慧的結晶。

📅 組員分工

組員＼工作	kernal	Syacall	C libary	Applicaion
蔡奇霖	✓
徐晟鈞	✓		✓
湯智超		✓	✓	✓