Lab 5: File system, Spawn and Shell tags: mit 6.828 os 概述 本lab將實現JOS的文件系統,只要包括如下四部分: 1. 引入一個 文件系統進程(FS進程) 的特殊進程,該進程提供文件操作的介面。 2. 建立RPC機制 ,客戶端進程向FS進程發送 ...
Lab 5: File system, Spawn and Shell
tags: mit-6.828 os
概述
本lab將實現JOS的文件系統,只要包括如下四部分:
- 引入一個文件系統進程(FS進程)的特殊進程,該進程提供文件操作的介面。
- 建立RPC機制,客戶端進程向FS進程發送請求,FS進程真正執行文件操作,並將數組返回給客戶端進程。
- 更高級的抽象,引入文件描述符。通過文件描述符這一層抽象就可以將控制台,pipe,普通文件,統統按照文件來對待。(文件描述符和pipe實現原理)
- 支持從磁碟載入程式並運行。
File system preliminaries
我們將要實現的文件系統會比真正的文件系統要簡單,但是能滿足基本的創建,讀,寫,刪除文件的功能。但是不支持鏈接,符號鏈接,時間戳等特性。
On-Disk File System Structure
JOS的文件系統不使用inodes,所有文件的元數據都被存儲在directory entry中。
文件和目錄邏輯上都是由一系列數據blocks組成,這些blocks分散在磁碟中,文件系統屏蔽blocks分佈的細節,提供一個可以順序讀寫文件的介面。JOS文件系統允許用戶讀目錄元數據,這就意味著用戶可以掃描目錄來像實現ls這種程式,UNIX沒有採用這種方式的原因是,這種方式使得應用程式過度依賴目錄元數據格式。
Sectors and Blocks
大部分磁碟都是以Sector為粒度進行讀寫,JOS中Sectors為512位元組。文件系統以block為單位分配和使用磁碟。註意區別,sector size是磁碟的屬性,block size是操作系統使用磁碟的粒度。JOS的文件系統的block size被定為4096位元組。
Superblocks
文件系統使用一些特殊的block保存文件系統屬性元數據,比如block size, disk size, 根目錄位置等。這些特殊的block叫做superblocks。
我們的文件系統使用一個superblock,位於磁碟的block 1。block 0被用來保存boot loader和分區表。很多文件系統維護多個superblock,這樣當一個損壞時,依然可以正常運行。
磁碟結構如下:
File Meta-data
我們的文件系統使用struct File結構描述文件,該結構包含文件名,大小,類型,保存文件內容的block號。struct File結構的f_direct數組保存前NDIRECT(10)個block號,這樣對於10*4096=40KB的文件不需要額外的空間來記錄內容block號。對於更大的文件我們分配一個額外的block來保存4096/4=1024 block號。所以我們的文件系統允許文件最多擁有1034個block。File結構如下:
Directories versus Regular Files
File結構既能代表文件也能代表目錄,由type欄位區分,文件系統以相同的方式管理文件和目錄,只是目錄文件的內容是一系列File結構,這些File結構描述了在該目錄下的文件或者子目錄。
超級塊中包含一個File結構,代表文件系統的根目錄。
The File System
Disk Access
到目前為止內核還沒有訪問磁碟的能力。JOS不像其他操作系統一樣在內核添加磁碟驅動,然後提供系統調用。我們實現一個文件系統進程來作為磁碟驅動。
x86處理器使用EFLAGS寄存器的IOPL為來控制保護模式下代碼是否能執行設備IO指令,比如in和out。我們希望文件系統進程能訪問IO空間,其他進程不能。
Exercise 1
文件系統進程的type為ENV_TYPE_FS,需要修改env_create(),如果type是ENV_TYPE_FS,需要給該進程IO許可權。
在env_create()中添加如下代碼:
if (type == ENV_TYPE_FS) {
e->env_tf.tf_eflags |= FL_IOPL_MASK;
}
The Block Cache
我們的文件系統最大支持3GB,文件系統進程保留從0x10000000 (DISKMAP)到0xD0000000 (DISKMAP+DISKMAX)固定3GB的記憶體空間作為磁碟的緩存。比如block 0被映射到虛擬地址0x10000000,block 1被映射到虛擬地址0x10001000以此類推。
如果將整個磁碟全部讀到記憶體將非常耗時,所以我們將實現按需載入,只有當訪問某個bolck對應的記憶體地址時出現頁錯誤,才將該block從磁碟載入到對應的記憶體區域,然後重新執行記憶體訪問指令。
Exercise 2
實現bc_pgfault()和flush_block()。
bc_pgfault()是FS進程缺頁處理函數,負責將數據從磁碟讀取到對應的記憶體。可以回顧下lab4。
bc_pgfault(struct UTrapframe *utf)
{
void *addr = (void *) utf->utf_fault_va;
uint32_t blockno = ((uint32_t)addr - DISKMAP) / BLKSIZE;
int r;
// Check that the fault was within the block cache region
if (addr < (void*)DISKMAP || addr >= (void*)(DISKMAP + DISKSIZE))
panic("page fault in FS: eip %08x, va %08x, err %04x",
utf->utf_eip, addr, utf->utf_err);
// Sanity check the block number.
if (super && blockno >= super->s_nblocks)
panic("reading non-existent block %08x\n", blockno);
// Allocate a page in the disk map region, read the contents
// of the block from the disk into that page.
// Hint: first round addr to page boundary. fs/ide.c has code to read
// the disk.
//
// LAB 5: you code here:
addr = ROUNDDOWN(addr, PGSIZE);
sys_page_alloc(0, addr, PTE_W|PTE_U|PTE_P);
if ((r = ide_read(blockno * BLKSECTS, addr, BLKSECTS)) < 0)
panic("ide_read: %e", r);
// Clear the dirty bit for the disk block page since we just read the
// block from disk
if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)
panic("in bc_pgfault, sys_page_map: %e", r);
// Check that the block we read was allocated. (exercise for
// the reader: why do we do this *after* reading the block
// in?)
if (bitmap && block_is_free(blockno))
panic("reading free block %08x\n", blockno);
}
flush_block()將一個block寫入磁碟。flush_block()不需要做任何操作,如果block沒有在記憶體或者block沒有被寫過。可以通過PTE的PTE_D位判斷該block有沒有被寫過。
void
flush_block(void *addr)
{
uint32_t blockno = ((uint32_t)addr - DISKMAP) / BLKSIZE;
int r;
if (addr < (void*)DISKMAP || addr >= (void*)(DISKMAP + DISKSIZE))
panic("flush_block of bad va %08x", addr);
// LAB 5: Your code here.
addr = ROUNDDOWN(addr, PGSIZE);
if (!va_is_mapped(addr) || !va_is_dirty(addr)) { //如果addr還沒有映射過或者該頁載入到記憶體後還沒有被寫過,不用做任何事
return;
}
if ((r = ide_write(blockno * BLKSECTS, addr, BLKSECTS)) < 0) { //寫回到磁碟
panic("in flush_block, ide_write(): %e", r);
}
if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0) //清空PTE_D位
panic("in bc_pgfault, sys_page_map: %e", r);
}
fs/fs.c中的fs_init()將會初始化super和bitmap全局指針變數。至此對於文件系統進程只要訪問虛擬記憶體[DISKMAP, DISKMAP+DISKMAX]範圍中的地址addr,就會訪問到磁碟((uint32_t)addr - DISKMAP) / BLKSIZE block中的數據。如果block數據還沒複製到記憶體物理頁,bc_pgfault()缺頁處理函數會將數據從磁碟拷貝到某個物理頁,並且將addr映射到該物理頁。這樣FS進程只需要訪問虛擬地址空間[DISKMAP, DISKMAP+DISKMAX]就能訪問磁碟了。
The Block Bitmap
fs_init()中已經初始化了bitmap,我們能通過bitmap訪問磁碟的block 1,也就是位數組,每一位代表一個block,1表示該block未被使用,0表示已被使用。我們實現一系列管理函數來管理這個位數組。
Exercise 3
實現fs/fs.c中的alloc_block(),該函數搜索bitmap位數組,返回一個未使用的block,並將其標記為已使用。
alloc_block(void)
{
// The bitmap consists of one or more blocks. A single bitmap block
// contains the in-use bits for BLKBITSIZE blocks. There are
// super->s_nblocks blocks in the disk altogether.
// LAB 5: Your code here.
uint32_t bmpblock_start = 2;
for (uint32_t blockno = 0; blockno < super->s_nblocks; blockno++) {
if (block_is_free(blockno)) { //搜索free的block
bitmap[blockno / 32] &= ~(1 << (blockno % 32)); //標記為已使用
flush_block(diskaddr(bmpblock_start + (blockno / 32) / NINDIRECT)); //將剛剛修改的bitmap block寫到磁碟中
return blockno;
}
}
return -E_NO_DISK;
}
File Operations
fs/fs.c文件提供了一系列函數用於管理File結構,掃描和管理目錄文件,解析絕對路徑。
基本的文件系統操作:
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
:查找f指向文件結構的第filebno個block的存儲地址,保存到ppdiskbno中。如果f->f_indirect還沒有分配,且alloc為真,那麼將分配要給新的block作為該文件的f->f_indirect。類比頁表管理的pgdir_walk()。file_get_block(struct File *f, uint32_t filebno, char **blk)
:該函數查找文件第filebno個block對應的虛擬地址addr,將其保存到blk地址處。walk_path(const char *path, struct File **pdir, struct File **pf, char *lastelem)
:解析路徑path,填充pdir和pf地址處的File結構。比如/aa/bb/cc.c那麼pdir指向代表bb目錄的File結構,pf指向代表cc.c文件的File結構。又比如/aa/bb/cc.c,但是cc.c此時還不存在,那麼pdir依舊指向代表bb目錄的File結構,但是pf地址處應該為0,lastelem指向的字元串應該是cc.c。dir_lookup(struct File *dir, const char *name, struct File **file)
:該函數查找dir指向的文件內容,尋找File.name為name的File結構,並保存到file地址處。dir_alloc_file(struct File *dir, struct File **file)
:在dir目錄文件的內容中尋找一個未被使用的File結構,將其地址保存到file的地址處。
文件操作:
file_create(const char *path, struct File **pf)
:創建path,如果創建成功pf指向新創建的File指針。file_open(const char *path, struct File **pf)
:尋找path對應的File結構地址,保存到pf地址處。file_read(struct File *f, void *buf, size_t count, off_t offset)
:從文件f中的offset位元組處讀取count位元組到buf處。file_write(struct File *f, const void *buf, size_t count, off_t offset)
:將buf處的count位元組寫到文件f的offset開始的位置。
Exercise 4
實現file_block_walk()和file_get_block()。
file_block_walk():
static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
// LAB 5: Your code here.
int bn;
uint32_t *indirects;
if (filebno >= NDIRECT + NINDIRECT)
return -E_INVAL;
if (filebno < NDIRECT) {
*ppdiskbno = &(f->f_direct[filebno]);
} else {
if (f->f_indirect) {
indirects = diskaddr(f->f_indirect);
*ppdiskbno = &(indirects[filebno - NDIRECT]);
} else {
if (!alloc)
return -E_NOT_FOUND;
if ((bn = alloc_block()) < 0)
return bn;
f->f_indirect = bn;
flush_block(diskaddr(bn));
indirects = diskaddr(bn);
*ppdiskbno = &(indirects[filebno - NDIRECT]);
}
}
return 0;
}
file_get_block():
int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{
// LAB 5: Your code here.
int r;
uint32_t *pdiskbno;
if ((r = file_block_walk(f, filebno, &pdiskbno, true)) < 0) {
return r;
}
int bn;
if (*pdiskbno == 0) { //此時*pdiskbno保存著文件f第filebno塊block的索引
if ((bn = alloc_block()) < 0) {
return bn;
}
*pdiskbno = bn;
flush_block(diskaddr(bn));
}
*blk = diskaddr(*pdiskbno);
return 0;
}
踩坑記錄
包括後面的Exercise 10都遇到相同的問題。
寫完Exercise4後執行make grade,無法通過測試,提示"file_get_block returned wrong data"。在實驗目錄下搜索該字元串,發現是在fs/test.c文件中,
if ((r = file_open("/newmotd", &f)) < 0)
panic("file_open /newmotd: %e", r);
if ((r = file_get_block(f, 0, &blk)) < 0)
panic("file_get_block: %e", r);
if (strcmp(blk, msg) != 0)
panic("file_get_block returned wrong data");
也就是說只有當blk和msg指向的字元串不一樣時才會報這個錯,msg定義在fs/test.c中static char *msg = "This is the NEW message of the day!\n\n"
。blk指向/newmotd文件的開頭。/newmotd文件在fs/newmotd中,打開後發現內容也是"This is the NEW message of the day!"。照理來說應該沒有問題啊。但是通過xxd fs/newmotd指令查看文件二進位發現如下:
1. 00000000: 5468 6973 2069 7320 7468 6520 4e45 5720 This is the NEW
2. 00000010: 6d65 7373 6167 6520 6f66 2074 6865 2064 message of the d
3. 00000020: 6179 210d 0a0d 0a ay!....
最後的兩個換行符是0d0a 0d0a,也就是\r\n\r\n。但是msg中末尾卻是\n\n。\r\n應該是windows上的換行符,不知道為什麼fs/newmotd中的換行符居然是windows上的換行符。找到問題了所在,我們用vim打開fs/newmotd,然後使用命令set ff=unix,保存退出。現在再用xxd fs/newmotd指令查看文件二進位發現,換行符已經變成了\n(0x0a)。這樣就可以通過該實驗了。在Exercise 10中同樣需要將fs文件夾下的lorem,script,testshell.sh文件中的換行符轉成UNIX下的。
The file system interface
到目前為止,文件系統進程已經能提供各種操作文件的功能了,但是其他用戶進程不能直接調用這些函數。我們通過進程間函數調用(RPC)對其它進程提供文件系統服務。RPC機制原理如下:
Regular env FS env
+---------------+ +---------------+
| read | | file_read |
| (lib/fd.c) | | (fs/fs.c) |
...|.......|.......|...|.......^.......|...............
| v | | | | RPC mechanism
| devfile_read | | serve_read |
| (lib/file.c) | | (fs/serv.c) |
| | | | ^ |
| v | | | |
| fsipc | | serve |
| (lib/file.c) | | (fs/serv.c) |
| | | | ^ |
| v | | | |
| ipc_send | | ipc_recv |
| | | | ^ |
+-------|-------+ +-------|-------+
| |
+-------------------+
本質上RPC還是藉助IPC機制實現的,普通進程通過IPC向FS進程間發送具體操作和操作數據,然後FS進程執行文件操作,最後又將結果通過IPC返回給普通進程。從上圖中可以看到客戶端的代碼在lib/fd.c和lib/file.c兩個文件中。服務端的代碼在fs/fs.c和fs/serv.c兩個文件中。
相關數據結構之間的關係可用下圖來表示:
文件系統服務端代碼在fs/serv.c中,serve()中有一個無限迴圈,接收IPC請求,將對應的請求分配到對應的處理函數,然後將結果通過IPC發送回去。
對於客戶端來說:發送一個32位的值作為請求類型,發送一個Fsipc結構作為請求參數,該數據結構通過IPC的頁共用發給FS進程,在FS進程可以通過訪問fsreq(0x0ffff000)來訪問客戶進程發來的Fsipc結構。
對於服務端來說:FS進程返回一個32位的值作為返回碼,對於FSREQ_READ和FSREQ_STAT這兩種請求類型,還額外通過IPC返回一些數據。
Exercise 5
實現fs/serv.c中的serve_read()。這是服務端也就是FS進程中的函數。直接調用更底層的fs/fs.c中的函數來實現。
int
serve_read(envid_t envid, union Fsipc *ipc)
{
struct Fsreq_read *req = &ipc->read;
struct Fsret_read *ret = &ipc->readRet;
if (debug)
cprintf("serve_read %08x %08x %08x\n", envid, req->req_fileid, req->req_n);
// Lab 5: Your code here:
struct OpenFile *o;
int r;
r = openfile_lookup(envid, req->req_fileid, &o);
if (r < 0) //通過fileid找到Openfile結構
return r;
if ((r = file_read(o->o_file, ret->ret_buf, req->req_n, o->o_fd->fd_offset)) < 0) //調用fs.c中函數進行真正的讀操作
return r;
o->o_fd->fd_offset += r;
return r;
}
Exercise 6
實現fs/serv.c中的serve_write()和lib/file.c中的devfile_write()。
serve_write():
int
serve_write(envid_t envid, struct Fsreq_write *req)
{
if (debug)
cprintf("serve_write %08x %08x %08x\n", envid, req->req_fileid, req->req_n);
// LAB 5: Your code here.
struct OpenFile *o;
int r;
if ((r = openfile_lookup(envid, req->req_fileid, &o)) < 0) {
return r;
}
int total = 0;
while (1) {
r = file_write(o->o_file, req->req_buf, req->req_n, o->o_fd->fd_offset);
if (r < 0) return r;
total += r;
o->o_fd->fd_offset += r;
if (req->req_n <= total)
break;
}
return total;
}
devfile_write():客戶端進程函數,包裝一下參數,直接調用fsipc()將參數發送給FS進程處理。
static ssize_t
devfile_write(struct Fd *fd, const void *buf, size_t n)
{
// Make an FSREQ_WRITE request to the file system server. Be
// careful: fsipcbuf.write.req_buf is only so large, but
// remember that write is always allowed to write *fewer*
// bytes than requested.
// LAB 5: Your code here
int r;
fsipcbuf.write.req_fileid = fd->fd_file.id;
fsipcbuf.write.req_n = n;
memmove(fsipcbuf.write.req_buf, buf, n);
return fsipc(FSREQ_WRITE, NULL);
}
Spawning Processes
lib/spawn.c中的spawn()創建一個新的進程,從文件系統載入用戶程式,然後啟動該進程來運行這個程式。spawn()就像UNIX中的fork()後面馬上跟著exec()。
spawn(const char *prog, const char **argv)
做如下一系列動作:
- 從文件系統打開prog程式文件
- 調用系統調用sys_exofork()創建一個新的Env結構
- 調用系統調用sys_env_set_trapframe(),設置新的Env結構的Trapframe欄位(該欄位包含寄存器信息)。
- 根據ELF文件中program herder,將用戶程式以Segment讀入記憶體,並映射到指定的線性地址處。
- 調用系統調用sys_env_set_status()設置新的Env結構狀態為ENV_RUNNABLE。
Exercise 7
實現sys_env_set_trapframe()系統調用。
static int
sys_env_set_trapframe(envid_t envid, struct Trapframe *tf)
{
// LAB 5: Your code here.
// Remember to check whether the user has supplied us with a good
// address!
int r;
struct Env *e;
if ((r = envid2env(envid, &e, 1)) < 0) {
return r;
}
tf->tf_eflags = FL_IF;
tf->tf_eflags &= ~FL_IOPL_MASK; //普通進程不能有IO許可權
tf->tf_cs = GD_UT | 3;
e->env_tf = *tf;
return 0;
}
Sharing library state across fork and spawn
UNIX文件描述符是一個大的概念,包含pipe,控制台I/O。在JOS中每種設備對應一個struct Dev結構,該結構包含函數指針,指向真正實現讀寫操作的函數。
lib/fd.c文件實現了UNIX文件描述符介面,但大部分函數都是簡單對struct Dev結構指向的函數的包裝。
我們希望共用文件描述符,JOS中定義PTE新的標誌位PTE_SHARE,如果有個頁表條目的PTE_SHARE標誌位為1,那麼這個PTE在fork()和spawn()中將被直接拷貝到子進程頁表,從而讓父進程和子進程共用相同的頁映射關係,從而達到父子進程共用文件描述符的目的。
Exercise 8
修改lib/fork.c中的duppage(),使之正確處理有PTE_SHARE標誌的頁表條目。同時實現lib/spawn.c中的copy_shared_pages()。
static int
duppage(envid_t envid, unsigned pn)
{
int r;
// LAB 4: Your code here.
void *addr = (void*) (pn * PGSIZE);
if (uvpt[pn] & PTE_SHARE) {
sys_page_map(0, addr, envid, addr, PTE_SYSCALL); //對於標識為PTE_SHARE的頁,拷貝映射關係,並且兩個進程都有讀寫許可權
} else if ((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)) { //對於UTOP以下的可寫的或者寫時拷貝的頁,拷貝映射關係的同時,需要同時標記當前進程和子進程的頁表項為PTE_COW
if ((r = sys_page_map(0, addr, envid, addr, PTE_COW|PTE_U|PTE_P)) < 0)
panic("sys_page_map:%e", r);
if ((r = sys_page_map(0, addr, 0, addr, PTE_COW|PTE_U|PTE_P)) < 0)
panic("sys_page_map:%e", r);
} else {
sys_page_map(0, addr, envid, addr, PTE_U|PTE_P); //對於只讀的頁,只需要拷貝映射關係即可
}
return 0;
}
copy_shared_pages()
static int
copy_shared_pages(envid_t child)
{
// LAB 5: Your code here.
uintptr_t addr;
for (addr = 0; addr < UTOP; addr += PGSIZE) {
if ((uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P) &&
(uvpt[PGNUM(addr)] & PTE_U) && (uvpt[PGNUM(addr)] & PTE_SHARE)) {
sys_page_map(0, (void*)addr, child, (void*)addr, (uvpt[PGNUM(addr)] & PTE_SYSCALL));
}
}
return 0;
}
The Shell
運行make run-icode,將會執行user/icode,user/icode又會執行inti,然後會spawn sh。然後就能運行如下指令:
echo hello world | cat
cat lorem |cat
cat lorem |num
cat lorem |num |num |num |num |num
lsfd
Exercise 10
目前shell還不支持IO重定向,修改user/sh.c,增加IO該功能。
runcmd(char* s) {
...
if ((fd = open(t, O_RDONLY)) < 0) {
cprintf("open %s for write: %e", t, fd);
exit();
}
if (fd != 0) {
dup(fd, 0);
close(fd);
}
...
}
總結回顧
- 構建文件系統:
- 引入一個文件系統進程(FS進程)的特殊進程,該進程提供文件操作的介面。具體實現在fs/bc.c,fs/fs.c,fs/serv.c中。
- 建立RPC機制,客戶端進程向FS進程發送請求,FS進程真正執行文件操作。客戶端進程的實現在lib/file.c,lib/fd.c中。客戶端進程和FS進程交互可總結為下圖:
- 更高級的抽象,引入文件描述符。通過文件描述符這一層抽象就可以將控制台,pipe,普通文件,統統按照文件來對待。文件描述符和pipe的原理總結如下:
- 支持從磁碟載入程式並運行。實現spawn(),該函數創建一個新的進程,並從磁碟載入程式運行,類似UNIX中的fork()後執行exec()。
具體代碼在:https://github.com/gatsbyd/mit_6.828_jos
如有錯誤,歡迎指正(*^_^*):
15313676365