系列文章 : [6.1810] 跟著 MIT 6.1810 學習基礎作業系統觀念

大綱

• xv6-riscv boot : 10.8 Inode layer
• kernel/fs.h/struct dinode
• kernel/file.h/inode
• kernel/fs.c/itable
• kernel/fs.c/iinit
• kernel/fs.c/iget
• kernel/fs.c/iput
• kernel/fs.c/idup
• kernel/fs.c/ilock
• kernel/fs.c/iunlock
• kernel/fs.c/iunlockput

xv6-riscv boot : 10.8 Inode layer

介紹 `struct-inode`, `struct-dinode`, `itable`。

`inode` 在這裡可能有兩個意思。

• on-disk data structure containing a file’s size and list of data block numbers
• in-memory inode, which contains a copy of the on-disk inode, 以及其他 kernel 需要的資訊。

on-disk-inode 被打包在 disk hardware 上的連續空間，被稱為 `inode blocks`。每一個 inode 都有相同的大小，所以只要給我們一個數字 `n`，我們就能很容易地找到在 disk 上的 `nth` inode。

這個數字 n，被稱為 `inode-number` 或是 `i-number`。在 xv6-riscv file-system 的實作中，使用 `i-number` 來辨別 inodes。

There are four lock or lock-like mechanisms in xv6’s inode code.

• itable.lock 保護 itable.inode[NINODE] 一次只有一個 process 可以讀寫
• in-memory inode 的 `ref` 欄位 : 計算有多少個指標指向這個 in-memory inode。
  • 假如一個 inode 的 ref > 0，會讓系統保持這個 inode 在 itable.inode[NINODE] ，並且不會讓其他的 inode reuse itable.inode[N] 的 entry。
• 每一個 in-memory inode 都有自己的 sleep-lock，保障每次只有一個 process 可以讀寫 inode 的欄位 ( e.g. size )。也保障每次只有一個 process 可以讀寫該 inode 所指向的 `file content blocks` 或是 `directory content blocks`。
• 每個 inode 都包含一個 nlink 欄位 ( 不論是在 disk hardware 裡面的 `struct dinode`， 或是在記憶體裡的 `in-memory struct inode`)，這代表參照到該 inode 的 directory entries 的數量。 假如 nlink 大於 0， xv6 將不會釋放這個 inode。

介紹 iget, iput, ilock, iunlock, iupdate。

• iget, iput : A struct inode pointer returned by iget() is guaranteed to be valid until the corresponding call to iput(), the inode won’t be deleted, and the memory referred to by the pointer won’t be re-used for a different inode.
• iget : iget() provides non-exclusive access to an inode. 這代表多個 process 可以`同時`取得 相同 inode 的指標.
  • Many parts of the file-system code depend on this behavior of iget()
    • hold long-term references to inodes (as open files and current directories)
    • prevent races while avoiding deadlock in code that manipulates multiple inodes (such as pathname lookup).
• ilock : 從 iget 取得的 in-memory struct inode 可能沒有任何有用的內容。為了確定這個 struct inode 包含了 on-disk inode ( struct dinode )，我們需要呼叫 `ilock`。ilock 會鎖住這個 inode （ 其他的 process 不可以同時 `ilock` 同個 inode )，並且把 on-disk struct dinode 的資訊讀取到 memory ( 假如它還沒有被讀取進 memory 的話 )。
• iunlock : iunlock 會釋放這個 inode 的 sleep-lock。Separating acquisition of inode pointers from locking helps avoid deadlock in some situations, for example during directory lookup.
• 多個 process 可以同時用 iget 拿到 inode 的 C pointer，但是只有一個 process 可以拿到 struct-inode 的 sleep-lock。
• The inode table only stores inodes to which kernel code or data structures hold C pointers.
• Its main job is synchronizing access by multiple processes.
• The inode table also happens to cache frequently-used inodes, but caching is secondary; if an inode is used frequently, the buffer cache will probably keep it in memory.
• iupdate : Code that modifies an in-memory inode writes it to disk with `iupdate`.

kernel/fs.h/struct dinode

// On-disk inode structure  
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  
};  

這是會放到 disk 裡面的 inode structure。

• type : 標示該 inode 所表示的意義
  • 0 : 代表該 inode 目前是閒置 ( free ) 的狀態。
  • T_DIR(1) : 表示這是一個 directory
  • T_FILE(2) : 表示這是一個 file
  • T_DEVICE(3) : 表示這是一個特殊檔案 ( devices )
• major : TODO … 目前還不知道這個欄位的意義，或許在往後的 layer 可以學習到。
• minor : TODO … 目前還不知道這個欄位的意義，或許在往後的 layer 可以學習到。
• nlink : 表示目前有幾個 directory entries 指向這個 inode。這個可以當作該 inode 該不該被 free 掉的一個指標。
• size : 表示這個檔案有多少 bytes。
• addrs : 是一個陣列，該陣列內的每一個元素都是 block number，用以表示哪些 block 擁有該 inode 的資料。

kernel/file.h/inode

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

• uint dev : device number，代表目前我們是使用哪一個 physical disk 或是 partition。xv6-riscv 的 root disk 的 device number 為 ROOTDEV (1)。
• uint inum : inode number，用來辨別 inode 的標示。
• int ref : ref count，指向該 inode 的指標的數量，歸零的話，會釋放這個 struct-inode。
• struct sleeplock lock : 當我們只希望一個 process 來處理這個 inode 相關的資料的時候 ( e.g. ilock )，就可以用上這個 sleep-lock。
• int valid : 這個 struct-inode 有把 disk hardware 內的 struct-dinode 讀取進來了嗎 ? ( e.g. `ilock` function )

`struct inode` 是 `struct dinode` 的 in-memory copy。

而 `struct inode` 這個 in-memory 依據 xv6-riscv system software 的需求，多開了幾個欄位 ( e.g. dev, inum, ref … )。

struct-inode 是 struct-dinode( 在 disk hardware ) 在 memory 裡的副本。僅在有人使用 C pointer 指向一個 struct-inode 的時候，才會把 struct-dinode ( in disk hardware ) 複製到 struct-inode ( in memory )。

ref 欄位 : 計算 C pointers 指向 in-memory inode 的數量。 當 ref 歸 0 的時候，kernel 會丟棄這個 inode。

• iget()
  • acquire pointers to an inode
  • ref++
• iput
  • release pointers to an inode
  • ref--

kernel/fs.c/itable

struct {  
  struct spinlock lock;  
  struct inode inode\[NINODE\];  
} itable;  

xv6-riscv 會把目前在 memory 裡面有的 active inodes，存放到 `itable` 裡面。

要注意到 struct-inode->inum 指的`並不是` itable->inode[N] 陣列的 index。

kernel/fs.c/iinit

{ https://github.com/mit-pdos/xv6-riscv/blob/xv6-riscv-rev5/kernel/fs.c#L183 }

• 在 kernel 在進行初始化的時候，會被 `main` 呼叫。
• 初始化 itable.lock
• 初始化在 itable.inode[N] 陣列裡面的 struct-inode 裡面的 sleeplock。

kernel/fs.c/iget

// Find the inode with number inum on device dev  
// and return the in-memory copy. Does not lock  
// the inode and does not read it from disk.  
static struct inode\*  
iget(uint dev, uint inum)  
{  

這個 function 會嘗試用 `dev` 以及 `inum` 去拿出一個 in-memory copy struct-inode。
雖然拿到了 struct-inode，但這不代表這個 inode 的資訊已經從 disk hardware 讀取出來了 ( 需要用 ilock 讀取出來 )。

• dev : device number
• inum : inode number

  struct inode \*ip, \*empty;

  acquire(\&itable.lock);

  // Is the inode already in the table?  
  empty \= 0;  
  for(ip \= \&itable.inode\[0\]; ip \< \&itable.inode\[NINODE\]; ip++){  
    if(ip-\>ref \> 0 && ip-\>dev \== dev && ip-\>inum \== inum){  
      ip-\>ref++;  
      release(\&itable.lock);  
      return ip;  
    }  
    if(empty \== 0 && ip-\>ref \== 0\)    // Remember empty slot.  
      empty \= ip;  
  }  

嘗試去 itable.inode 裡面看看，想要找的 inode 是不是已經在這個陣列裡面了。
並且同時找找看有沒有空的 itable.inode[N] entry。

  // Recycle an inode entry.  
  if(empty \== 0\)  
    panic("iget: no inodes");

  ip \= empty;  
  ip-\>dev \= dev;  
  ip-\>inum \= inum;  
  ip-\>ref \= 1;  
  ip-\>valid \= 0;  
  release(\&itable.lock);

  return ip;  
}  

在 itable.inode[N] 裡面找不到的話，就回收那個空的 entry ( 在這裡以 empty 變數表示 )。
把 dev, inum, ref, valid 初始化，要注意到這時候 `type, major, minor, nlink, size, addrs` 都還沒初始化，要等待未來的某個時刻，從 disk hardware 讀取。

跟 ialloc 相比

• iget : 拿出一個已經存在的 inode。可能是已經存在於 disk hardware 裡，又或是 in-memory 的 itable.inode[N] 裡面。
• ialloc : 創造出一個新的 inode，把這個新的 inode 放進 disk hardware，並也複製一份在 in-memory struct-inode。

kernel/fs.c/iput

// Drop a reference to an in-memory inode.  
// If that was the last reference, the inode table entry can  
// be recycled.  
// If that was the last reference and the inode has no links  
// to it, free the inode (and its content) on disk.  
// All calls to iput() must be inside a transaction in  
// case it has to free the inode.  
void  
iput(struct inode \*ip)  
{  

這個 function 表示某個 C pointer 不需要再指向這個 inode 了，

• ip->ref--
• 只有 ip->ref == 0，而 ip->nlink != 0 的話
  • iget 有機會回收這個 itable.inode[N] entry
  • 但是檔案的內容不會用 itrunc 砍掉

  acquire(\&itable.lock);

  if(ip-\>ref \== 1 && ip-\>valid && ip-\>nlink \== 0){  
    // inode has no links and no other references: truncate and free.

    // ip-\>ref \== 1 means no other process can have ip locked,  
    // so this acquiresleep() won't block (or deadlock).  
    acquiresleep(\&ip-\>lock);  

因為這邊準備操作這個 struct-inode 所代表的 disk hardware 內的 data blocks，所以需要取用該 inode 的 sleeplock。

    release(\&itable.lock);

    itrunc(ip);  
    ip-\>type \= 0;  
    iupdate(ip);  
    ip-\>valid \= 0;  

• itrunc
  • 會把 struct-inode 所指向的 disk-hardware 內的 data blocks 給丟棄。
  • caller 需要先擁有 struct-inode 的 sleep-lock。
• ip->type = 0 : type 等於 0 代表該 inode 目前是閒置 ( free ) 的狀態。
• iupdate
  • 把一個被修改的 in-memory struct-inode 的內容，寫入到 disk-hardware 中的 struct-dinode。
  • caller 需要擁有 inode 的 sleep-lock。
• ip->valid = 0 : 代表目前該 in-memory-struct-inode 並不包含 disk-hardware 內的 struct-dinode 的內容。

    releasesleep(\&ip-\>lock);

    acquire(\&itable.lock);  
  }

  ip-\>ref--;  
  release(\&itable.lock);  
}  

因為少一個 C pointer 指向這個 inode，所以 ip->ref--

kernel/fs.c/idup

// Increment reference count for ip.  
// Returns ip to enable ip \= idup(ip1) idiom.  
struct inode\*  
idup(struct inode \*ip)  
{  
  acquire(\&itable.lock);  
  ip-\>ref++;  
  release(\&itable.lock);  
  return ip;  
}  

單純的把 ip->ref++，表示給定某一個 struct-inode，有新的 process 也想要有個 C pointer 指向該 inode。

kernel/fs.c/ilock

// Lock the given inode.  
// Reads the inode from disk if necessary.  
void  
ilock(struct inode \*ip)  
{  
  struct buf \*bp;  
  struct dinode \*dip;  

這個 function 會嘗試去拿取一個 in-memory-struct-inode 的 sleep-lock，
並且需要的話，從 disk-hardware 裡面讀取相對應的 struct-dinode 的內容。

  if(ip \== 0 || ip-\>ref \< 1\)  
    panic("ilock");  

沒有人正在用這個 struct-inode，怎麼還會需要拿這個 struct-inode 的 sleep-lock ? 怪怪的，直接發一個 panic。

  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;  
    memmove(ip-\>addrs, dip-\>addrs, sizeof(ip-\>addrs));  
    brelse(bp);  
    ip-\>valid \= 1;  
    if(ip-\>type \== 0\)  
      panic("ilock: no type");  
  }  
}  

• IPB ( inode per block ) : 每一個 block 會有多少個 struct-dinode
• IBLOCK(i, sb) : inode-number 為 i 的 struct-dinode，會是在 disk-hardware 裡面的哪一個 block。
• bp : struct-buf，buffer-cache-layer，把 disk-hardware 資料載入到 buffer-cache 裡面。
• dip : 從 buffer-cache 裡面拿到相對應的 struct-dinode。

接下來把 struct-dinode 的資料載入到相對應的 in-memory-struct-inode。

• brelse(bp) : 不需要這個 struct-buf 了，可以把它釋放掉。
• ip->valid = 1 : 代表目前該 in-memory-struct-inode 並`已經`包含 disk-hardware 內的 struct-dinode 的內容。
• if (ip->type == 0) : 讀取出來，卻發現這個 struct-dinode 標示為閒置的... 肯定是某個環節出了問題，直些發 panic。

kernel/fs.c/iunlock

// Unlock the given inode.  
void  
iunlock(struct inode \*ip)  
{  
  if(ip \== 0 || \!holdingsleep(\&ip-\>lock) || ip-\>ref \< 1\)  
    panic("iunlock");

  releasesleep(\&ip-\>lock);  
}  

釋放這個 in-memory-struct-inode 的 sleep-lock，喚醒其他等待這個 sleep-lock 的 process。

kernel/fs.c/iunlockput

// Common idiom: unlock, then put.  
void  
iunlockput(struct inode \*ip)  
{  
  iunlock(ip);  
  iput(ip);  
}  

就是把 iunlock 跟 iput 放在一起。
這個順序很常被使用，索性放在同一個 function。