2013年5月26日 星期日

[ Nachos 4.0 ] Nachos System Call Implementation Sample

來源自 這裡 
Preface: 
Nachos的全稱是“Not Another Completely Heuristic Operating System”,它是一個可修改和 trace 的操作系統教學軟件. 它給出了一個支持多線程和虛擬存儲的操作系統骨架,可讓學生在較短的時間內對操作系統中的基本原理和核心算法有一個全面和完整的了解. 該操作系統核心部分使用C++實現,代碼可讀性較強. 這邊我們實作的第一個實驗就是基於NachOS去撰寫 System Call. 

實作簡介: 
實作的內容是為 NachOS 添加幾個 System Call , 分別為 OSAdd(op1,op2)OSSub(op1,op2)OSDiv(op1,op2)OSMul(op1,op2) 與 Print(char *msg) (作用是在系統控制台上打印字符串). 從 code/threads/kernel.cccode/machine/machine.h 與 code/userprog/synchconsole.h 可知,操作系統預設可以使用的函數或類別有: 
  1. kernel->synchConsoleOut->PutChar( char ch);  //向控制台輸出字符  
  2. kernel->machine->ReadRegister( int num);    //讀暫存器  
  3. kernel->machine->WriteRegister( int num, int value);   //寫暫存器  
  4. kernel->machine->ReadMem( int addr, int size, int * value); //從用戶進程內存讀值  
系統虛擬機運行原理: 
使用 Nachos 運行 user program 可以使用命令: 
> nachos –x program_name

nachos 執行檔的 entry point 在 code/threads/main.cc啟動,創建了Kernel對象並進行初始化(啟動主線程、創建線程調度表、中斷處理模塊、CPU、控制台、文件系統、中斷等): 
 

之後,程序創建了用戶空間程序,初始化的時候加載了指令集並調用了kernel->machine->WriteRegister 填寫CPU寄存器,然後開始執行。執行由 kernel->machine->Run 實現: 
- /code/userprog/addrspace.cc 
  1. ...  
  2. void  
  3. AddrSpace::Execute()  
  4. {  
  5.   
  6.     kernel->currentThread->space = this;  
  7.   
  8.     this->InitRegisters();      // set the initial register values  
  9.     this->RestoreState();       // load page table register  
  10.   
  11.     kernel->machine->Run();     // jump to the user progam  
  12.   
  13.     ASSERTNOTREACHED();         // machine->Run never returns;  
  14.                     // the address space exits  
  15.                     // by doing the syscall "exit"  
  16. }  
  17. ...  


接著使用 OneInstruction 函數模擬 CPU 的逐條指令執行過程: 
- /code/machine/mipssim.cc 
  1. ...  
  2. //----------------------------------------------------------------------  
  3. // Machine::Run  
  4. //  Simulate the execution of a user-level program on Nachos.  
  5. //  Called by the kernel when the program starts up; never returns.  
  6. //  
  7. //  This routine is re-entrant, in that it can be called multiple  
  8. //  times concurrently -- one for each thread executing user code.  
  9. //----------------------------------------------------------------------  
  10.   
  11. void  
  12. Machine::Run()  
  13. {  
  14.     Instruction *instr = new Instruction;  // storage for decoded instruction  
  15.   
  16.     if (debug->IsEnabled('m')) {  
  17.         cout << "Starting program in thread: " << kernel->currentThread->getName();  
  18.     cout << ", at time: " << kernel->stats->totalTicks << "\n";  
  19.     }  
  20.     kernel->interrupt->setStatus(UserMode);  
  21.     for (;;) {  
  22.         OneInstruction(instr);  
  23.     kernel->interrupt->OneTick();  
  24.     if (singleStep && (runUntilTime <= kernel->stats->totalTicks))  
  25.       Debugger();  
  26.     }  
  27. }  
  28. ...  
當 user program 載入後, Fetch > Decode > Execute 的流程如下, 而 ExceptionHandler() 函數則是用來作為 System Call 的 dispatcher: 
 

系統調用的實現過程: 
如同 Linux 操作系統一樣,運行在虛擬機上的 NachOS 也使用中斷來實現 System Call(User Mode 程序調用操作系統內核服務的接口).實現方法為: 
0. 為了方便 debug, 我新增了一個 debug 類型 "dbJohn" 如下 
- /code/lib/debug.h 
  1. ...  
  2. const char dbJohn = 'j';        // Debug by John  
  3. ...  
之後可以使用參數 -d j 來打印我的除錯訊息. 

1. 當 System Call 發生的時候,首先把函數參數、系統調用號存入寄存器,然後引發系統中斷,通過中斷調用進入 Kernel mode. 以 System Call "OSAdd" 為範例: 
- /code/test/start.S 
  1.     .globl  OSAdd  /*聲明為外部函數*/  
  2.     .ent    OSAdd  /* OSAdd 函數開始*/  
  3. OSAdd:  
  4.     addiu $2,$0,SC_OSAdd  /* 將 system call 呼叫 case num 存入r2寄存器*/  
  5.     syscall  /* all parameter of this system call will be stored in register 4,5,6 and 7 by MIPS machine automatically.*/  
  6.     j   $31  
  7. .end OSAdd  
2. 函數調用則會在中斷發生時進行 ./userprog/exception.cc, 在此撰寫中斷發生時的 handler: 
- /code/userprog/exception.cc 
  1.   case SC_OSAdd:  
  2. DEBUG(dbJohn, "Add " << kernel->machine->ReadRegister(4) << " + " << kernel->machine->ReadRegister(5) << "\n");  
  3.       //int result;  
  4.       op1 = (int)kernel->machine->ReadRegister(4);  
  5.       op2 = (int)kernel->machine->ReadRegister(5);  
  6.       result = SysOSAdd(op1, op2);  
  7. DEBUG(dbJohn, "Add returning with " << result << "\n");  
  8.       kernel->machine->WriteRegister(2, (int)result); /* Prepare Result */  
  9.       /* Modify return point */  
  10.       {  
  11.               /* set previous programm counter (debugging only)*/  
  12.               kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));  
  13.   
  14.               /* set programm counter to next instruction (all Instructions are 4 byte wide)*/  
  15.               kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);  
  16.   
  17.               /* set next programm counter for brach execution */  
  18.               kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg)+4);  
  19.       }  
  20.   
  21.       return;  
  22.   
  23.       ASSERTNOTREACHED();  
  24.       break;  
這邊當 System Call "OSAdd" 發生時, 會進入 handler switch 的 case "SC_OSAdd", 這邊則將 System Call 的函數呼叫定義為 "SysOSAdd(op1, op2)", 並於呼叫完畢後將結果回存 2 號暫存器並增加 Program Counter 到下一個要執行的 instruction. 

3. 將 System Call "OSAdd" 的函數 "SysOSAdd" 定義在 "./userprog/ksyscall.h": 
- /code/userprog/ksyscall.h 
  1. //----------------------------------------------------------------------  
  2. // SysOSAdd  
  3. //  Operation Add.  
  4. //  
  5. //  Add "op1" with "op2".  
  6. //  
  7. //  "op1" and "op2" are operands of operation Add.  
  8. //      ex: SysOSAdd(1,2) = 1+2 = 3  
  9. //----------------------------------------------------------------------  
  10. int SysOSAdd(int op1, int op2)  
  11. {  
  12.     int result = op1 + op2;  
  13.     return result;  
  14. }  
4. 重新 compile Nachos 與調用 測試代碼. 假設你寫了 project1.c 來測試剛剛寫的 System call 並放在 test 目錄下, 接著你必須在 Makefile 添加下面代碼以編譯 project.c : 
  1. ...  
  2. PROGRAMS= add halt shell matmult sort segments project1  
  3. ...  
  4. project1.o:project1.c  
  5. $(CC) $(CFLAGS) -c project1.c  
  6.   
  7. project1: project1.o start.o  
  8. $(LD) $(LDFLAGS) start.o project1.o - o project1.coff  
  9. $(COFF2NOFF) project1.coff project1  
  10. ...  
上面的符號 需要替換成 "\t" 鍵. 接著可以在 test 目錄下執行 make 編譯 project1.c 

5. 使用 nachos 虛擬機載入 project1, 執行命令如下: 
> nachos -d j -x project1 # 開啟 debug 類別 'j'
Add 15 + 10

Add returning with 25

Machine halting!

Ticks: total 29, idle 0, system 10, user 19
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0


System Call Print(char* input, int length) 的具體實現: 
有了上面的介紹, System Call OSAdd(op1,op2)OSSub(op1,op2)OSDiv(op1,op2)OSMul(op1,op2) 的實現應該都不是問題, 這裡要針對 Print(char *msg) System Call 進行詳細實作說明. 第一步當然就是在 start.S 添加 System Call Print 的聲明: 
- /code/test/start.S 
  1.     .globl  Print  
  2.     .ent    Print  
  3. Print:  
  4.     addiu $2,$0,SC_Print  
  5.     syscall  
  6.     j   $31  
  7. .end Print  
接著增加 System Call handler case 宣告: 
- /code/userprog/syscall.h 
  1. #define SC_Print       60  
接著撰寫 System Call handler 的 SC_Print case : 
- /code/userprog/exception.cc 
  1. case SC_Print:  
  2.      DEBUG(dbJohn, "Print call...\n");  
  3.      result = SysPrint(/* int op1 */(char*)kernel->machine->ReadRegister(4),  
  4.                        /* int op2 */(int)kernel->machine->ReadRegister(5));  
  5.      kernel->machine->WriteRegister(2, (int)result); /* Prepare Result */  
  6.      /* Modify return point */  
  7.      {  
  8.         /* set previous programm counter (debugging only)*/  
  9.         kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg));  
  10.   
  11.         /* set programm counter to next instruction (all Instructions are 4 byte wide)*/  
  12.         kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4);  
  13.   
  14.         /* set next programm counter for brach execution */  
  15.         kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg)+4);  
  16.      }  
  17.      return;  
  18.      ASSERTNOTREACHED();  
  19.      break;  
接著實作上面調用的函數 SysPrint : 
- /code/userprog/ksyscall.h 
  1. #include "kernel.h"  
  2. #include "synchconsole.h"  
  3. #include "utility.h"  
  4. #include "stdio.h"  
  5. ...  
  6. //----------------------------------------------------------------------  
  7. // SysPrint  
  8. //  Print Message to Nachos Console Output.  
  9. //  
  10. //  Output message from with chars.  
  11. //  
  12. //  "input" is the char* which pointer to output message; "length" tells the length of output message.  
  13. //      ex: SysPrint("John", 4) -> Output "John" to console.  
  14. //----------------------------------------------------------------------  
  15. int SysPrint(char* input, int length)  
  16. {  
  17.     int i;  
  18.     int memVal = 0;  
  19.     int memPt = (int)input;  
  20.     for(i=0; i
  21.     {  
  22.         kernel->machine->ReadMem(int(memPt+i),1,&memVal); /* 從用戶程序內存空間讀取字符串的值*/  
  23.         if(0 == memVal) return i;  
  24.         kernel->synchConsoleOut->PutChar((char)memVal);  
  25.     }  
  26.     return length;  
  27. }  
上面代碼記得要包含標頭檔 "synchconsole.h" 並透過函數 kernel->synchConsoleOut->PutChar(char) 將 output message 一次取一個 char 輸出. 接著重新編譯 Nachos: 
../code/test/build.linux> make
g++ -g -Wall -I../network -I../filesys -I../userprog -I../threads -I../machine -I../lib -I- -DFILESYS_STUB -DRDATA -DSIM_FIX -Dx86 -DLINUX -DCHANGED -m32 -c ../userprog/exception.cc
...
/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h:400:0: note: this is the location of the previous definition
g++ bitmap.o debug.o libtest.o sysdep.o interrupt.o stats.o timer.o console.o machine.o mipssim.o translate.o network.o disk.o alarm.o kernel.o main.o scheduler.o synch.o thread.o addrspace.o exception.o synchconsole.o directory.o filehdr.o filesys.o pbitmap.o openfile.o synchdisk.o post.o switch.o -m32 -o nachos

接著來寫測試代碼: 
- /code/test/project1.c 
  1. #include "syscall.h"  
  2.   
  3. int main()  
  4. {  
  5.     Print("Hello, I am John K Lee.\n" , 24);  
  6.     Halt();  
  7. }  
編譯完測試代碼後, 如下將 project1 program 載入 Nachos 虛擬機: 
> nachos -d j -x project1
Print call... # Caused by DEBUG

Hello, I am John K Lee.
Machine halting!

Ticks: total 3230, idle 2390, system 820, user 20
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 24
Paging: faults 0
Network I/O: packets received 0, sent 0

參考事項: 
- Duplicate definition on ConsoleInput & ConsoleOutput 
在實作 SysPrint 函數時, 為了使用 kernel->synchConsoleOut 來輸出字元, 你可能會包含進 "synchconsole.h". 此時在編譯 Nachos 時可能會出現下面錯誤訊息: 
../userprog/synchconsole.h:31:5: error: expected unqualified-id before numeric constant
../userprog/synchconsole.h:46:5: error: expected unqualified-id before numeric constant
make: *** [exception.o] Error 1

而可能的原因是在 "/code/userprog/syscall.h" 約 116 行: 
  1. #define ConsoleInput 0  
  2. #define ConsoleOutput    1  
與 "/code/machine/console.h" 約 47 行 與 70 行 
  1. ...  
  2. class ConsoleInput : public CallBackObj {  
  3. ...  
  4. class ConsoleOutput : public CallBackObj {  
  5. ...  
重複定義了 ConsoleInput & ConsoleOutput. 我的解法方法是將 "/code/userprog/syscall.h" 上面定義改為: 
  1. #define SysCallConsoleInput 0  
  2. #define SysCallConsoleOutput    1  
再重新編譯, 便可以解決這裡的問題. 

- Nachos Debugging 
基本上有兩種方法來 debug Nachos: external & internal. external debugger 透過外部載入 Nachos 的程式, 並使用 interactive 方法與使用者互動, 你可以一行行 debug 程式並檢查相關變數的設定, 常見的有 GDB. internal debugger 就是在你的程式加入 debug message, 透過這些訊息來判斷問題出在哪裡, 最常用也最沒有效率, 因為你無法一步步除錯, 且無法知道執行當下的變數(除非你把他們都印出來 orz)與執行環境. 詳細的介紹可以參考 [ Nachos 4.0 ] Debugging Nachos

2 則留言:

  1. 作者已經移除這則留言。

    回覆刪除
  2. 如果system call print部分的test case是這樣的話
    #include "syscall.h"
    int main()
    {
    int n;
    for (n=1;n<5;n++) {
    Print(n);
    }
    Halt();
    }
    又要怎麼寫呢?

    回覆刪除

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...