Roadmap 4: User Program

So far, every thread is an execution stream in the Nachos process, a UNIX process running on the underlying machine such as a SUN workstation. To understand the concept of process, how a user program is loaded into memory and runs on the CPU, Nachos simulates a MIPS machine. So we have complete control of the execution of a user program. In this roadmap, we study the following issues:

As in Threads, always read *.h to understand the data structures before reading *.cc

Let us start with the file main.cc (threads/main.cc). Here are a few lines of code from this routine.

int
main(int argc, char **argv)
{
    int argCount;                       // the number of arguments
                                        // for a particular command
    ...

#ifdef USER_PROGRAM
        if (!strcmp(*argv, "-x")) {             // run a user program
            ASSERT(argc > 1);
            StartProcess(*(argv + 1));
            argCount = 2;
        }
        ...
#endif // USER_PROGRAM
    ...
}

If we run the Nachos:

         ./nachos -x ../test/halt

void
StartProcess(char *filename)
{
    OpenFile *executable = fileSystem->Open(filename);
    AddrSpace *space;

    if (executable == NULL) {
        printf("Unable to open file %s\n", filename);
        return;
    }
    space = new AddrSpace(executable);
    currentThread->space = space;

    delete executable;                  // close file

    space->InitRegisters();
                                        // set the initial register values
    space->RestoreState();
                                        // load page table register

    machine->Run();    // jump to the user progam
    ASSERT(FALSE);                      // machine->Run never returns;
                                        // the address space exits
                                        // by doing the syscall "exit"
}

This function does the following:

- Calls the file system to open the object (executable) file. It takes a file name, a string, and returns a pointer executable to an instance of the class OpenFile. We will study the procedure of openning a file later in file system. Basically, it uses the file name to find the file header (called i-node in UNIX) on the disk and move the i-node from the disk to the memory and returns a pointer to the i-node. The file header contains the information about the file, such as the size of the file, disk sectors, etc. The OpenFile class has memeber functions like Read, Write, so we can read/write the file from/to the disk. Note that after openning the file, only the file header is in the memory, not yet the data of the file. Now, executable is a pointer to (address of) the file header object. Is it an address in kernel space or user space?
- Creates a new address space addrspace for the object (executable) file by calling the constructor AddrSpace()
- Assigns the newly created address space to current thread
- Closes the file (why we can close the file now?)
- Initializes the simulator MIPS machine registers by calling InitRegisters()
- Restores the machine state by calling RestoreState()
- Runs the program on the MIPS simulator by calling function Run()

For now, we assume that the constructor AddrSpace loads the executable, passed as an argument to the constructor, into the simulated physical memory. Also, for now we assume the starting address of the executable in the physical memory is 0. We will look into details later. Before running the program, we must set the MIPS registers properly.

void
AddrSpace::InitRegisters()
{
    int i;

    for (i = 0; i < NumTotalRegs; i++)
        machine->WriteRegister(i, 0);

    // Initial program counter -- must be location of "Start"
    machine->WriteRegister(PCReg, 0);

    // Need to also tell MIPS where next instruction is, because
    // of branch delay possibility
    machine->WriteRegister(NextPCReg, 4);

   // Set the stack register to the end of the address space, where we
   // allocated the stack; but subtract off a bit, to make sure we don't
   // accidentally reference off the end!
    machine->WriteRegister(StackReg, numPages * PageSize - 16);
    DEBUG('a', "Initializing stack register to %d\n", numPages * PageSize - 16);
}

This function sets the initial values for the user-level registers. (total of 40 registers defined in machine/machine.*) We write these directly into the "machine" registers, so that we can immediately jump to user code. Specifically, the program counter register PCReg is initialized to 0. Note that these will be saved/restored into the currentThread->userRegisters when the thread is context switched out. Now, we have two sets of registers. (What are they?)

For now, we assume that RestoreState() called by StartProcess() tells the machine where to find the page table. Then Run() is called to run the program on the MIPS machine.

void Machine::Run()
{
    Instruction *instr = new Instruction;  // storage for decoded instruction

    ...
    interrupt->setStatus(UserMode);
    for (;;) {
        OneInstruction(instr);
        interrupt->OneTick();
        ...
    }
}

This function simulates the execution of a user-level program on Nachos. It is called by the kernel when the program starts up; never returns. This routine is re-entrant, in that it can be called multiple times concurrently -- one for each thread executing user code.
First, it sets the machine status to UserMode. (MachineStatus: IdleMode, SystemMode, UserMode) Then, it executes one instruction at a time: OneInstruction(). After each user instruction is executed, it calls OneTick().

void Machine::OneInstruction(Instruction *instr)
{
    int raw;
    int nextLoadReg = 0;
    int nextLoadValue = 0;      // record delayed load operation, to apply
                                // in the future

    // Fetch instruction
    if (!machine->ReadMem(registers[PCReg], 4, &raw))
        return;                 // exception occurred
    instr->value = raw;

    // Decode instruction
    instr->Decode();
    ...
    // Execute the instruction (cf. Kane's book)
    switch (instr->opCode) {

      case OP_ADD:

      ...

      case OP_SYSCALL
        RaiseException(SyscallException, 0);
        return;

      ...

    }

    // Now we have successfully executed the instruction.

    // Do any delayed load operation
    DelayedLoad(nextLoadReg, nextLoadValue);

    // Advance program counters.
    registers[PrevPCReg] = registers[PCReg];    // for debugging, in case we
                                                // are jumping into lala-land
    registers[PCReg] = registers[NextPCReg];
    registers[NextPCReg] = pcAfter;
}

This function performs a fetch-execute cycle of an instruction from a user-level program. It fetches an instruction (4 bytes) at the address given by the content of PCReg by calling ReadMem(). The address of the instruction in PCReg is a virtual address. The instruction is stored in the physical memory. The virtual address in PCReg must be translated into physical address where the instruction is stored. If there is any kind of exception (see machine/machine.h for exception types), we return to Run(). This allows us to re-start the instruction execution from the beginning, in case any of our state has changed. Then it decodes and executes the instruction. Finally, it advances PC and updates the delay slot. This routine is re-entrant, in that it can be called multiple times concurrently -- one for each thread executing user code.
What will it do if the instruction is syscall?

Suppose we have a C program:

        main() {
            ...
            Halt();
        }

After it is compiled, the assembly code looks like the following. Note that all nachos assembly codes start with Start.s (in test/).

                .globl  Start
                .ent    Start, 0
        Start:
                jal     main
                move    $4, $0
                jal     Exit
                .end    Start
                ...
                .globl  Halt
                .ent    Halt, 0
        Halt:
                addiu   $2, $0, SC_Halt
                syscall
                j       $31
                .end    Halt
                ...

        main:
                ...
                jal     Halt
                ...

void
Machine::RaiseException(ExceptionType which, int badVAddr)
{
    ...
    registers[BadVAddrReg] = badVAddr;
    DelayedLoad(0, 0);                  // finish anything in progress
    interrupt->setStatus(SystemMode);
    ExceptionHandler(which);            // interrupts are enabled at this point
    interrupt->setStatus(UserMode);
}

This function transfers control to the Nachos kernel from user mode, because the user program either invoked a system call, or some exception occured (such as the address translation failed). It calls ExceptionHandler to handle the system call or exception.

void
ExceptionHandler(ExceptionType which)
{
    int type = machine->ReadRegister(2);

    if ((which == SyscallException) && (type == SC_Halt)) {
        DEBUG('a', "Shutdown, initiated by user program.\n");
        interrupt->Halt();
    } else {
        printf("Unexpected user mode exception %d %d\n", which, type);
        ASSERT(FALSE);
    }
}

At this point, you should understand how a user program gets run and what happens when the user program makes a system call or an exception occurs.

In the above example, the system call halt() does not have any argument. How do you implement system calls which have arguments? (Think about two spaces: kernel and user.)

class AddrSpace {
  public:
     ...
  private:
    TranslationEntry *pageTable;        // Assume linear page table translation
                                        // for now!
    unsigned int numPages;              // Number of pages in the virtual
                                        // address space
};

The mental picture of the addrspace data structure looks something like:

        |------------------|
        | pageTable        | pointer to a table of
        |                  | TranslationEntry
        |------------------|
        | numPages         | number of pages in the virtual address space
        |------------------|    

Note that the addrspace does not have the program. All it has is a page table.

AddrSpace::AddrSpace(OpenFile *executable)
{
    NoffHeader noffH;
    unsigned int i, size;

    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    ...

// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size
                        + UserStackSize;        // we need to increase the size
                                                // to leave room for the stack
    numPages = divRoundUp(size, PageSize);
    size = numPages * PageSize;
    ...

// first, set up the translation
    pageTable = new TranslationEntry[numPages];
    for (i = 0; i < numPages; i++) {
        pageTable[i].virtualPage = i;   // for now, virtual page # = phys page #
        pageTable[i].physicalPage = i;
        pageTable[i].valid = TRUE;
        pageTable[i].use = FALSE;
        pageTable[i].dirty = FALSE;
        pageTable[i].readOnly = FALSE;  // if the code segment was entirely on
                                        // a separate page, we could set its
                                        // pages to be read-only
    }

// zero out the entire address space, to zero the unitialized data segment
// and the stack segment
    bzero(machine->mainMemory, size);

// then, copy in the code and data segments into memory
    if (noffH.code.size > 0) {
     ...
        executable->ReadAt(&(machine->mainMemory[noffH.code.virtualAddr]),
                        noffH.code.size, noffH.code.inFileAddr);
    }
    if (noffH.initData.size > 0) {
     ...
        executable->ReadAt(&(machine->mainMemory[noffH.initData.virtualAddr]),
                        noffH.initData.size, noffH.initData.inFileAddr);
    }

}

This constructor does the following:

bin/noff.h

        --------------------------------
        |         magic number         |
        --------------------------------
        |               |     size     |
        |               |--------------|
        |    code       | virtual addr |
        |               |--------------|
        |               | infile addr  | byte offset from the
        |------------------------------| beginning of the file
        |               |     size     |
        | initialized   |--------------|
        |    data       | virtual addr |
        |               |--------------|
        |               | infile addr  | byte offset from the
        |------------------------------| beginning of the file
        |               |     size     |
        | uninitialized |--------------|
        |    data       | virtual addr |
        |               |--------------|
        |               | infile addr  | byte offset from the
        |------------------------------| beginning of the file

You should think about how this mechanism (page table) can protect the kernel and processes each other.

The page table is an array of TranslationEntry.

class TranslationEntry {
  public:
    int virtualPage;    // The page number in virtual memory.
    int physicalPage;   // The page number in real memory (relative to the
                        //  start of "mainMemory"
    bool valid;         // If this bit is set, the translation is ignored.
                        // (In other words, the entry hasn't been initialized.)
    bool readOnly;      // If this bit is set, the user program is not allowed
                        // to modify the contents of the page.
    bool use;           // This bit is set by the hardware every time the
                        // page is referenced or modified.
    bool dirty;         // This bit is set by the hardware every time the
                        // page is modified.
};

The above class defines an entry in a translation table -- either in a page table or a TLB (translation lookaside buffer). Each entry defines a mapping from one virtual page to one physical page. In addition, there are some extra bits for access control (valid and read-only) and some bits for information about usage (use) and write modification (dirty).

After an address space is constructed, it is assigned to the current thread.

class Thread {
  private:
    // NOTE: DO NOT CHANGE the order of these first two members.
    // THEY MUST be in this position for SWITCH to work.
    int* stackTop;                       // the current stack pointer
    int machineState[MachineStateSize];  // all registers except for stackTop

  public:

    ...

  private:
    // some of the private data for this class is listed above

    int* stack;                         // Bottom of the stack
                                        // NULL if this is the main thread
                                        // (If NULL, don't deallocate stack)
    ThreadStatus status;                // ready, running or blocked
    char* name;

    ...

#ifdef USER_PROGRAM
// A thread running a user program actually has *two* sets of CPU registers --
// one for its state while executing user code, one for its state
// while executing kernel code.

    int userRegisters[NumTotalRegs];    // user-level CPU register state

  public:
    void SaveUserState();               // save user-level register state
    void RestoreUserState();            // restore user-level register state

    AddrSpace *space;                   // User code this thread is running.
#endif
};

In addition to the data structures discussed previously, there is an array for the user-level registers. A thread running a user program actually has two sets of CPU registers -- one for its state while executing user code. This is the set of the registers in the MIPS simulator. Another is for its state while executing kernel code. This set is machine dependent (SUN/sparc, MIPS, etc). There is also a pointer to this process address space.

        |---------------|
        |  stackTop     |
        |---------------|
        |               |
        | machineState  |
        |               |
        |---------------|
        |    stack      |
        |---------------|
        |    status     |
        |---------------|
        |    name       |
        |===============|
        |               |
        |               |
        | userRegisters |
        |               |
        |               |
        |---------------|
        |    space      | pointer to the address space
        |---------------| of this thread

In StartProcess(), before running the user program, we need to restore the machine state. Specifically, we tell the machine which page table should be used for address translation.

void AddrSpace::RestoreState()
{
    machine->pageTable = pageTable;
    machine->pageTableSize = numPages;
}

This function assigns the current thread's page table to the machine page table. Thus whenever the machine reads the memory (to fetch an instruction or data), it uses the page table to translate the virtual address to physical address. The baseline Nachos is a uniprogramming system, RestoreState() just tells the machine where to find the page table when a process starts and SaveState() (not needed) has nothing. In multiprogramming, on a context switch (see Run() in threads/scheduler.cc), what should SaveState() and RestoreState() do?

bool Machine::ReadMem(int addr, int size, int *value)
{
    int data;
    ExceptionType exception;
    int physicalAddress;

    ...
    exception = Translate(addr, &physicalAddress, size, FALSE);
    if (exception != NoException) {
        machine->RaiseException(exception, addr);
        return FALSE;
    }
    switch (size) {
      case 1:
        data = machine->mainMemory[physicalAddress];
        *value = data;
        break;

      case 2:
        data = *(unsigned short *) &machine->mainMemory[physicalAddress];
        *value = ShortToHost(data);
        break;

      case 4:
        data = *(unsigned int *) &machine->mainMemory[physicalAddress];
        *value = WordToHost(data);
        break;

      default: ASSERT(FALSE);
    }
    ...
    return (TRUE);
}

This function translates a virtual address to physical address by calling Translate(). Then it checks the returned value from Translate() function, if NoException, it gets the instruction from the physical memory, else calls exception handler RaiseException().

ExceptionType
Machine::Translate(int virtAddr, int* physAddr, int size, bool writing)
{
    int i;
    unsigned int vpn, offset;
    TranslationEntry *entry;
    unsigned int pageFrame;

    ...
// check for alignment errors
    if (((size == 4) && (virtAddr & 0x3)) || ((size == 2) && (virtAddr & 0x1))){
        return AddressErrorException;
    }

    // we must have either a TLB or a page table, but not both!
    ASSERT(tlb == NULL || pageTable == NULL);
    ASSERT(tlb != NULL || pageTable != NULL);

// calculate the virtual page number, and offset within the page,
// from the virtual address
    vpn = (unsigned) virtAddr / PageSize;
    offset = (unsigned) virtAddr % PageSize;

// check for all sorts of other errors
   if (...)
        return ...                   //ExceptionType

    pageFrame = entry->physicalPage;

    // if the pageFrame is too big, there is something really wrong!
    // An invalid translation was loaded into the page table or TLB.
    if (pageFrame >= NumPhysPages) {
        return BusErrorException;
    }
    entry->use = TRUE;          // set the use, dirty bits
    if (writing)
        entry->dirty = TRUE;
    *physAddr = pageFrame * PageSize + offset;
    ASSERT((*physAddr >= 0) && ((*physAddr + size) <= MemorySize));
    return NoException;
}

This function translates a virtual address into a physical address, using either a page table or a TLB.
What does this function return? How is OS protected? (user should not be able to directly touch the kernel)
Types of exceptions are defined in machine/machine.h. For example, page fault (will not happen until virtual memory), read only voilation; bus error (exceed physical memory limit), address error (alignment or exceed address space limit).