# Trace code ## a. > Trace the SC_Halt system call to understand the implementation of a system call. ### Run() 當有system call是,可以看到是用OneInstrucion()一次執行一個指令,此時user program是在user mode下執行的。 ```cpp= void Machine::Run() { Instruction *instr = new Instruction; // storage for decoded instruction if (debug->IsEnabled('m')) { cout << "Starting program in thread: " << kernel->currentThread->getName(); cout << ", at time: " << kernel->stats->totalTicks << "\n"; } kernel->interrupt->setStatus(UserMode); for (;;) { DEBUG(dbgTraCode, "In Machine::Run(), into OneInstruction " << "== Tick " << kernel->stats->totalTicks << " =="); OneInstruction(instr); DEBUG(dbgTraCode, "In Machine::Run(), return from OneInstruction " << "== Tick " << kernel->stats->totalTicks << " =="); DEBUG(dbgTraCode, "In Machine::Run(), into OneTick " << "== Tick " << kernel->stats->totalTicks << " =="); kernel->interrupt->OneTick(); DEBUG(dbgTraCode, "In Machine::Run(), return from OneTick " << "== Tick " << kernel->stats->totalTicks << " =="); if (singleStep && (runUntilTime <= kernel->stats->totalTicks)) Debugger(); } } ``` ### OneInstruction() 當OneInstruction()接收system call後,會跳到這段程式碼,去執行對應的操作,也就是調用RaiseException()。 ```cpp= case OP_SYSCALL: DEBUG(dbgTraCode, "In Machine::OneInstruction, RaiseException(SyscallException, 0), " << kernel->stats->totalTicks); RaiseException(SyscallException, 0); return; ``` ### RaiseException() 會先把發生例外的記憶體位置儲存起來,然後會先轉成system mode去處裡interrupt,之後再轉回user mode。這過程中會調用ExceptionHandler(),並傳入ExceptionType類型的參數。 ```cpp= void Machine::RaiseException(ExceptionType which, int badVAddr) { DEBUG(dbgMach, "Exception: " << exceptionNames[which]); registers[BadVAddrReg] = badVAddr; DelayedLoad(0, 0); // finish anything in progress kernel->interrupt->setStatus(SystemMode); ExceptionHandler(which); // interrupts are enabled at this point kernel->interrupt->setStatus(UserMode); } ``` ### exception handler() 接收到的ExceptionType包含不同類型的exception,我們要看的是system call,接收exception,並判斷是否跟system call有關,是的話會根據system call類別作處理,也就是根據system call的類型調用對應的function call。 ##### ExceptionType的實作 ```cpp= enum ExceptionType { NoException, // Everything ok! SyscallException, // A program executed a system call. PageFaultException, // No valid translation found ReadOnlyException, // Write attempted to page marked // "read-only" BusErrorException, // Translation resulted in an // invalid physical address AddressErrorException, // Unaligned reference or one that // was beyond the end of the // address space OverflowException, // Integer overflow in add or sub. IllegalInstrException, // Unimplemented or reserved instr. NumExceptionTypes }; ``` 由於關注的是SC_Halt,它會呼叫SysHalt()。 ```cpp void ExceptionHandler(ExceptionType which) { char ch; int val; int type = kernel->machine->ReadRegister(2); int status, exit, threadID, programID, fileID, numChar; DEBUG(dbgSys, "Received Exception " << which << " type: " << type << "\n"); DEBUG(dbgTraCode, "In ExceptionHandler(), Received Exception " << which << " type: " << type << ", " << kernel->stats->totalTicks); switch (which) { case SyscallException: switch (type) { case SC_Halt: DEBUG(dbgSys, "Shutdown, initiated by user program.\n"); SysHalt(); cout << "in exception\n"; ASSERTNOTREACHED(); break; case SC_PrintInt: DEBUG(dbgSys, "Print Int\n"); val = kernel->machine->ReadRegister(4); DEBUG(dbgTraCode, "In ExceptionHandler(), into SysPrintInt, " << kernel->stats->totalTicks); SysPrintInt(val); DEBUG(dbgTraCode, "In ExceptionHandler(), return from SysPrintInt, " << kernel->stats->totalTicks); // Set Program Counter kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg)); kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4); kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4); return; ASSERTNOTREACHED(); break; case SC_MSG: DEBUG(dbgSys, "Message received.\n"); val = kernel->machine->ReadRegister(4); { char *msg = &(kernel->machine->mainMemory[val]); cout << msg << endl; } SysHalt(); ASSERTNOTREACHED(); break; case SC_Create: val = kernel->machine->ReadRegister(4); { char *filename = &(kernel->machine->mainMemory[val]); // cout << filename << endl; status = SysCreate(filename); kernel->machine->WriteRegister(2, (int)status); } kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg)); kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4); kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4); return; ASSERTNOTREACHED(); break; case SC_Add: DEBUG(dbgSys, "Add " << kernel->machine->ReadRegister(4) << " + " << kernel->machine->ReadRegister(5) << "\n"); /* Process SysAdd Systemcall*/ int result; result = SysAdd(/* int op1 */ (int)kernel->machine->ReadRegister(4), /* int op2 */ (int)kernel->machine->ReadRegister(5)); DEBUG(dbgSys, "Add returning with " << result << "\n"); /* Prepare Result */ kernel->machine->WriteRegister(2, (int)result); /* Modify return point */ { /* set previous programm counter (debugging only)*/ kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg)); /* set programm counter to next instruction (all Instructions are 4 byte wide)*/ kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4); /* set next programm counter for brach execution */ kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4); } cout << "result is " << result << "\n"; return; ASSERTNOTREACHED(); break; case SC_Exit: DEBUG(dbgAddr, "Program exit\n"); val = kernel->machine->ReadRegister(4); cout << "return value:" << val << endl; kernel->currentThread->Finish(); break; default: cerr << "Unexpected system call " << type << "\n"; break; } break; default: cerr << "Unexpected user mode exception " << (int)which << "\n"; break; } ASSERTNOTREACHED(); } ``` ### ksyscall.h 一個包裝用的函式,去調用interrupt的Halt()。 ```cpp= void SysHalt() { kernel->interrupt->Halt(); } ``` ### Halt() 把目前kernel的狀態輸出出來。透過delete kernel把所有os的功能停掉。 ```cpp= //---------------------------------------------------------------------- // Interrupt::Halt // Shut down Nachos cleanly, printing out performance statistics. //---------------------------------------------------------------------- void Interrupt::Halt() { cout << "Machine halting!\n\n"; cout << "This is halt\n"; kernel->stats->Print(); delete kernel; // Never returns. } ``` ## b. > understand basic operation and data structure in a file system。 ### ExceptonHandler() 創建檔案也屬於system call的類別,在ExceptonHandler()是由SC_Create來處理的。透過呼叫SysCreate來創建檔案。 ```cpp= case SC_Create: val = kernel->machine->ReadRegister(4); { char *filename = &(kernel->machine->mainMemory[val]); // cout << filename << endl; status = SysCreate(filename); kernel->machine->WriteRegister(2, (int)status); } kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg)); kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4); kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4); return; ASSERTNOTREACHED(); break; ``` 除此之外,還會更新對應的program counter的值。透過以下操作去更新。 ```cpp= /* set previous programm counter (debugging only)*/ kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg)); /* set programm counter to next instruction (all Instructions are 4 byte wide)*/ kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4); /* set next programm counter for brach execution */ kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg)+4); ``` WriteRegister的具體實作如下。 用assert去檢查要寫入的register有沒有滿足大於等於零,而且小於等於register的總數量,這作法的概念memory protection相似,合法的話,就把value寫入register。 ```cpp= void Machine::WriteRegister(int num, int value) { ASSERT((num >= 0) && (num < NumTotalRegs)); registers[num] = value; } ``` ### SysCreate() 呼叫fileSystem的Create()。 ```cpp= int SysCreate(char *filename) { // return value // 1: success // 0: failed return kernel->fileSystem->Create(filename); } ``` ### Create() 先呼叫OpenForWrite,它的實作在sysdep.cc裡,之後透過回傳的fileDscriptor來判定檔案有無創建成功。在呼叫c++內建的close()關閉檔案。 ```cpp= bool Create(char *name) { int fileDescriptor = OpenForWrite(name); if (fileDescriptor == -1) return FALSE; Close(fileDescriptor); return TRUE; } ``` OpenForWrite的實作,基本上底層就呼叫了c++內建的open funciton。 ```cpp= int OpenForWrite(char *name) { int fd = open(name, O_RDWR|O_CREAT|O_TRUNC, 0666); ASSERT(fd >= 0); return fd; } ``` ## c. > Trace the SC_PrintInt system call to understand how NachOS implements asynchronized I/O using CallBack functions and register schedule events. ### ExceptonHandler 直接呼叫SysPrintInt(val)。 ```cpp= case SC_PrintInt: DEBUG(dbgSys, "Print Int\n"); val = kernel->machine->ReadRegister(4); DEBUG(dbgTraCode, "In ExceptionHandler(), into SysPrintInt, " << kernel->stats->totalTicks); SysPrintInt(val); DEBUG(dbgTraCode, "In ExceptionHandler(), return from SysPrintInt, " << kernel->stats->totalTicks); // Set Program Counter kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg)); kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4); kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4); return; ASSERTNOTREACHED(); break; ``` ### SysPrintInt() ksycall.h的SysPrintInt直接調用synchConsoleOut的PutInt(val) ```cpp= void SysPrintInt(int val) { DEBUG(dbgTraCode, "In ksyscall.h:SysPrintInt, into synchConsoleOut->PutInt, " << kernel->stats->totalTicks); kernel->synchConsoleOut->PutInt(val); DEBUG(dbgTraCode, "In ksyscall.h:SysPrintInt, return from synchConsoleOut->PutInt, " << kernel->stats->totalTicks); } ``` ### PutInt() 一開始用sprintf把value存到str,並透過lock去綁定資源,透過idx++,我們能夠把字元一個一個讓PutChar作處理, waitFor->P()是讓還沒處理到的字元先等待,等退出while loop後再讓lock解除綁定。 ```cpp= void SynchConsoleOutput::PutInt(int value) { char str[15]; int idx=0; //sprintf(str, "%d\n\0", value); the true one sprintf(str, "%d\n\0", value); //simply for trace code lock->Acquire(); do{ DEBUG(dbgTraCode, "In SynchConsoleOutput::PutChar, into consoleOutput->PutChar, " << kernel->stats->totalTicks); consoleOutput->PutChar(str[idx]); DEBUG(dbgTraCode, "In SynchConsoleOutput::PutChar, return from consoleOutput->PutChar, " << kernel->stats->totalTicks); idx++; DEBUG(dbgTraCode, "In SynchConsoleOutput::PutChar, into waitFor->P(), " << kernel->stats->totalTicks); waitFor->P(); DEBUG(dbgTraCode, "In SynchConsoleOutput::PutChar, return form waitFor->P(), " << kernel->stats->totalTicks); } while (str[idx] != '\0'); lock->Release(); } ``` ### PutChar() 先檢查putBusy是不是false,因為我們一次只能執行一次操作,若為false,透過WriteFile把字元一個一個寫入檔案,之後呼叫Schedule()。 ```cpp= void ConsoleOutput::PutChar(char ch) { ASSERT(putBusy == FALSE); WriteFile(writeFileNo, &ch, sizeof(char)); putBusy = TRUE; kernel->interrupt->Schedule(this, ConsoleTime, ConsoleWriteInt); } ``` ### Schedule() 透過pending這資料結構去插入interrupt,在這過程中會算出interrupt的時間,並紀錄interrupt發生時,並記錄toCall也就是callback執行的函式對象。 ```cpp= void Interrupt::Schedule(CallBackObj *toCall, int fromNow, IntType type) { int when = kernel->stats->totalTicks + fromNow; PendingInterrupt *toOccur = new PendingInterrupt(toCall, when, type); DEBUG(dbgInt, "Scheduling interrupt handler the " << intTypeNames[type] << " at time = " << when); ASSERT(fromNow > 0); pending->Insert(toOccur); } ``` ### Run() 在a.的部分已經提過了,machine會逐一執行instruction,並進到OneTick這個function。 ```cpp= kernel->interrupt->setStatus(UserMode); for (;;) { DEBUG(dbgTraCode, "In Machine::Run(), into OneInstruction " << "== Tick " << kernel->stats->totalTicks << " =="); OneInstruction(instr); DEBUG(dbgTraCode, "In Machine::Run(), return from OneInstruction " << "== Tick " << kernel->stats->totalTicks << " =="); DEBUG(dbgTraCode, "In Machine::Run(), into OneTick " << "== Tick " << kernel->stats->totalTicks << " =="); kernel->interrupt->OneTick(); DEBUG(dbgTraCode, "In Machine::Run(), return from OneTick " << "== Tick " << kernel->stats->totalTicks << " =="); if (singleStep && (runUntilTime <= kernel->stats->totalTicks)) Debugger(); } ``` ### OneTick ChangelLevel會決定kernel level在一段時間內能不能接受interrupt,然後他去檢查這段時間interrupt去處理。 在檢查現在有多少interrupt等著處裡時,會先讓kernel暫時不能接收interrupt,等到檢查完後,才會重新開啟,這段時間會去呼叫checkifdue()去處理interrupt。可以看到底層維護timer的時間。 以下是ChangeLevel()的實作。 ```cpp= void Interrupt::ChangeLevel(IntStatus old, IntStatus now) { level = now; DEBUG(dbgInt, "\tinterrupts: " << intLevelNames[old] << " -> " << intLevelNames[now]); } ``` 以下是OneTick()的實作。 ```cpp= void Interrupt::OneTick() { MachineStatus oldStatus = status; Statistics *stats = kernel->stats; // advance simulated time if (status == SystemMode) { stats->totalTicks += SystemTick; stats->systemTicks += SystemTick; } else { stats->totalTicks += UserTick; stats->userTicks += UserTick; } DEBUG(dbgInt, "== Tick " << stats->totalTicks << " =="); // check any pending interrupts are now ready to fire ChangeLevel(IntOn, IntOff); // first, turn off interrupts // (interrupt handlers run with // interrupts disabled) CheckIfDue(FALSE); // check for pending interrupts ChangeLevel(IntOff, IntOn); // re-enable interrupts if (yieldOnReturn) { // if the timer device handler asked // for a context switch, ok to do it now yieldOnReturn = FALSE; status = SystemMode; // yield is a kernel routine kernel->currentThread->Yield(); status = oldStatus; } } ``` ### checkifdue() pending存放著待處理的interrupt,在這段程式碼中,它會去檢查interrupt有沒有如期執行完,有的話,return true,否則return false。 ```cpp= bool Interrupt::CheckIfDue(bool advanceClock) { PendingInterrupt *next; Statistics *stats = kernel->stats; ASSERT(level == IntOff); // interrupts need to be disabled, // to invoke an interrupt handler if (debug->IsEnabled(dbgInt)) { DumpState(); } if (pending->IsEmpty()) { // no pending interrupts return FALSE; } next = pending->Front(); if (next->when > stats->totalTicks) { if (!advanceClock) { // not time yet return FALSE; } else { // advance the clock to next interrupt stats->idleTicks += (next->when - stats->totalTicks); stats->totalTicks = next->when; // UDelay(1000L); // rcgood - to stop nachos from spinning. } } DEBUG(dbgInt, "Invoking interrupt handler for the "); DEBUG(dbgInt, intTypeNames[next->type] << " at time " << next->when); if (kernel->machine != NULL) { kernel->machine->DelayedLoad(0, 0); } inHandler = TRUE; do { next = pending->RemoveFront(); // pull interrupt off list DEBUG(dbgTraCode, "In Interrupt::CheckIfDue, into callOnInterrupt->CallBack, " << stats->totalTicks); next->callOnInterrupt->CallBack();// call the interrupt handler DEBUG(dbgTraCode, "In Interrupt::CheckIfDue, return from callOnInterrupt->CallBack, " << stats->totalTicks); delete next; } while (!pending->IsEmpty() && (pending->Front()->when <= stats->totalTicks)); inHandler = FALSE; return TRUE; } ``` ### ConsoleOutput::CallBack() 更新putBusy的狀態,更新numConsoleCharsWritten,呼叫SynchConsoleOutput::CallBack()。 ```cpp= void ConsoleOutput::CallBack() { DEBUG(dbgTraCode, "In ConsoleOutput::CallBack(), " << kernel->stats->totalTicks); putBusy = FALSE; kernel->stats->numConsoleCharsWritten++; callWhenDone->CallBack(); } ``` ### SynchConsoleOutput::CallBack() 呼叫waitFor->V()。 ```cpp= void SynchConsoleOutput::CallBack() { DEBUG(dbgTraCode, "In SynchConsoleOutput::CallBack(), " << kernel->stats->totalTicks); waitFor->V(); } ``` ## d. //TODO > Trace the Makefile in code/test/Makefile to understand how test files are compiled ```cmake= include Makefile.dep CC = $(GCCDIR)gcc AS = $(GCCDIR)as LD = $(GCCDIR)ld INCDIR =-I../userprog -I../lib CFLAGS = -g -G 0 -c $(INCDIR) -B/usr/bin/local/nachos/lib/gcc-lib/decstation-ultrix/2.95.2/ -B/usr/bin/local/nachos/decstation-ultrix/bin/ ifeq ($(hosttype),unknown) PROGRAMS = unknownhost else # change this if you create a new test program! #PROGRAMS = add halt shell matmult sort segments test1 test2 a PROGRAMS = add halt createFile fileIO_test1 fileIO_test2 LotOfAdd endif all: $(PROGRAMS) start.o: start.S ../userprog/syscall.h $(CC) $(CFLAGS) $(ASFLAGS) -c start.S halt.o: halt.c halt: halt.o start.o $(LD) $(LDFLAGS) start.o halt.o -o halt.coff $(COFF2NOFF) halt.coff halt add.o: add.c $(CC) $(CFLAGS) -c add.c add: add.o start.o $(LD) $(LDFLAGS) start.o add.o -o add.coff $(COFF2NOFF) add.coff add LotOfAdd.o: LotOfAdd.c $(CC) $(CFLAGS) -c LotOfAdd.c LotOfAdd: LotOfAdd.o start.o $(LD) $(LDFLAGS) start.o LotOfAdd.o -o LotOfAdd.coff $(COFF2NOFF) LotOfAdd.coff LotOfAdd shell.o: shell.c $(CC) $(CFLAGS) -c shell.c shell: shell.o start.o $(LD) $(LDFLAGS) start.o shell.o -o shell.coff $(COFF2NOFF) shell.coff shell sort.o: sort.c $(CC) $(CFLAGS) -c sort.c sort: sort.o start.o $(LD) $(LDFLAGS) start.o sort.o -o sort.coff $(COFF2NOFF) sort.coff sort segments.o: segments.c $(CC) $(CFLAGS) -c segments.c segments: segments.o start.o $(LD) $(LDFLAGS) start.o segments.o -o segments.coff $(COFF2NOFF) segments.coff segments matmult.o: matmult.c $(CC) $(CFLAGS) -c matmult.c matmult: matmult.o start.o $(LD) $(LDFLAGS) start.o matmult.o -o matmult.coff $(COFF2NOFF) matmult.coff matmult consoleIO_test1.o: consoleIO_test1.c $(CC) $(CFLAGS) -c consoleIO_test1.c consoleIO_test1: consoleIO_test1.o start.o $(LD) $(LDFLAGS) start.o consoleIO_test1.o -o consoleIO_test1.coff $(COFF2NOFF) consoleIO_test1.coff consoleIO_test1 consoleIO_test2.o: consoleIO_test2.c $(CC) $(CFLAGS) -c consoleIO_test2.c consoleIO_test2: consoleIO_test2.o start.o $(LD) $(LDFLAGS) start.o consoleIO_test2.o -o consoleIO_test2.coff $(COFF2NOFF) consoleIO_test2.coff consoleIO_test2 consoleIO_test3.o: consoleIO_test3.c $(CC) $(CFLAGS) -c consoleIO_test3.c consoleIO_test3: consoleIO_test3.o start.o $(LD) $(LDFLAGS) start.o consoleIO_test3.o -o consoleIO_test3.coff $(COFF2NOFF) consoleIO_test3.coff consoleIO_test3 fileIO_test1.o: fileIO_test1.c $(CC) $(CFLAGS) -c fileIO_test1.c fileIO_test1: fileIO_test1.o start.o $(LD) $(LDFLAGS) start.o fileIO_test1.o -o fileIO_test1.coff $(COFF2NOFF) fileIO_test1.coff fileIO_test1 fileIO_test2.o: fileIO_test2.c $(CC) $(CFLAGS) -c fileIO_test2.c fileIO_test2: fileIO_test2.o start.o $(LD) $(LDFLAGS) start.o fileIO_test2.o -o fileIO_test2.coff $(COFF2NOFF) fileIO_test2.coff fileIO_test2 createFile.o: createFile.c $(CC) $(CFLAGS) -c createFile.c createFile: createFile.o start.o $(LD) $(LDFLAGS) start.o createFile.o -o createFile.coff $(COFF2NOFF) createFile.coff createFile clean: $(RM) -f *.o *.ii $(RM) -f *.coff distclean: clean $(RM) -f $(PROGRAMS) unknownhost: @echo Host type could not be determined. @echo make is terminating. @echo If you are on an MFCF machine, contact the instructor to report this problem @echo Otherwise, edit Makefile.dep and try again. ``` # Implementation 進到syscall.h,把//刪除。 ```cpp= #define SC_Open 6 #define SC_Read 7 #define SC_Write 8 #define SC_Close 10 ``` 在到exception handler去新增SC_Open,SC_Read,SC_WriteSC_Close ```cpp= case SC_Create: val = kernel->machine->ReadRegister(4); { char *filename = &(kernel->machine->mainMemory[val]); // cout << filename << endl; status = SysCreate(filename); kernel->machine->WriteRegister(2, (int)status); } kernel->machine->WriteRegister(PrevPCReg, kernel->machine->ReadRegister(PCReg)); kernel->machine->WriteRegister(PCReg, kernel->machine->ReadRegister(PCReg) + 4); kernel->machine->WriteRegister(NextPCReg, kernel->machine->ReadRegister(PCReg) + 4); return; ASSERTNOTREACHED(); break; ``` 看到SysCreate,應該要去fileSystem改。 ```cpp= int SysCreate(char *filename) { // return value // 1: success // 0: failed return kernel->fileSystem->Create(filename); } ``` 因為ksyscall.h只是調用kernel的function call,所以就照著寫,在fileSystem有對應的函數可以用,就呼叫它們。 ```cpp= OpenFileId SysOpen(char *filename) { return kernel->fileSystem->OpenAFile(filename); } int SysWrite(char *buffer, int size, OpenFileId id) { return kernel->fileSystem->WriteFile(buffer, size, id); } int SysRead(char *buffer, int size, OpenFileId id) { return kernel->fileSystem->ReadFile(buffer, size, id); } int SysClose(OpenFileId id) { return kernel->fileSystem->CloseFile(id); } ```