User Programs and System Call in Nachos

How Nachos generates a user program

The Nachos uses gcc MIPS to compile a .c file to a COFF file, then uses coff2noff to translate it to NOFF to make it recognizable by Nachos CPU.

NOFF file

In bin directory, noff.h :

#define NOFFMAGIC	0xbadfad 	/* magic number denoting Nachos object code file */

typedef struct segment {
    int virtualAddr;	/* location of segment in virt addr space */
    int inFileAddr;		/* location of segment in this file */
    int size;			/* size of segment */
} Segment;

typedef struct noffHeader {
    int noffMagic;		/* should be NOFFMAGIC */
    Segment code;		/* executable code segment */ 
    Segment initData;	/* initialized data segment */
    Segment uninitData;	/* uninitialized data segment -- should be zero'ed before use */
} NoffHeader;

There are only three kinds of segment in Nachos file header: executable code, initialized data and uninitialized data. And the noffMagic is a special number to be recognized as a Nachos file.

Start Process

In main.cc in threads directory, we see:

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

StartProcess is in progtest.cc in userprog directory:

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;
    space->print();
    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"
}

Firstly it opens an executable file, then gives it address space, make the current thread to execute it, initialize all registers, load page table, then run.

For details, we should look into every function.

addrspace.cc

In userprog directory. See the constructor:

AddrSpace::AddrSpace(OpenFile *executable) {
    NoffHeader noffH;
    unsigned int i, size;
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && (WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);
	// 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;
    ASSERT(numPages <= NumPhysPages);		// check we're not trying to run anything too big
						// at least until we have virtual memory
    DEBUG('a', "Initializing address space, num pages %d, size %d\n", numPages, size);
	// 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) {
        DEBUG('a', "Initializing code segment, at 0x%x, size %d\n", 
			noffH.code.virtualAddr, noffH.code.size);
        executable->ReadAt(&(machine->mainMemory[noffH.code.virtualAddr]),
			noffH.code.size, noffH.code.inFileAddr);
    }
    if (noffH.initData.size > 0) {
        DEBUG('a', "Initializing data segment, at 0x%x, size %d\n", 
			noffH.initData.virtualAddr, noffH.initData.size);
        executable->ReadAt(&(machine->mainMemory[noffH.initData.virtualAddr]),
			noffH.initData.size, noffH.initData.inFileAddr);
    }
}

First it reads the file header, and make sure it’s big endian and it’s a NOFF file by the NOFF magic number. Then it calculates the size of address space, including the stack, after which the page numbers can be decided. Then it creates the page tables, initializing all the values in each page table. Currently the virtual page is the same as the physical page.

Then it clear all the address space. After that, copy the code and data into memory.

Page table

The last step we see the page table, the code of translation from virtual page to physical page is in translate in machine directory:

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.
};

ExceptionType Machine::Translate(int virtAddr, int* physAddr, int size, bool writing) {
    int i;
    unsigned int vpn, offset;
    TranslationEntry *entry;
    unsigned int pageFrame;
    DEBUG('a', "\tTranslate 0x%x, %s: ", virtAddr, writing ? "write" : "read");
	// check for alignment errors
    if (((size == 4) && (virtAddr & 0x3)) || ((size == 2) && (virtAddr & 0x1))) {
        DEBUG('a', "alignment problem at %d, size %d!\n", virtAddr, size);
        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;
    if (tlb == NULL) {		// => page table => vpn is index into table
        if (vpn >= pageTableSize) {
            DEBUG('a', "virtual page # %d too large for page table size %d!\n", 
                virtAddr, pageTableSize);
            return AddressErrorException;
        } else if (!pageTable[vpn].valid) {
            DEBUG('a', "virtual page # %d too large for page table size %d!\n", 
                virtAddr, pageTableSize);
            return PageFaultException;
        }
        entry = &pageTable[vpn];
	} else {
    	for (entry = NULL, i = 0; i < TLBSize; i++)
        	if (tlb[i].valid && ((unsigned int)tlb[i].virtualPage == vpn)) {
            	entry = &tlb[i];			// FOUND!
            	break;
       		}
		if (entry == NULL) {				// not found
    		DEBUG('a', "*** no valid TLB entry found for this virtual page!\n");
        	return PageFaultException;		// really, this is a TLB fault,
                            // the page may be in memory, but not in the TLB
    	}
    }
    if (entry->readOnly && writing) {	// trying to write to a read-only page
		DEBUG('a', "%d mapped read-only at %d in TLB!\n", virtAddr, i);
		return ReadOnlyException;
    }
    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) { 
        DEBUG('a', "*** frame %d > %d!\n", 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));
    DEBUG('a', "phys addr = 0x%x\n", *physAddr);
    return NoException;
}

It decides whether to use TLB or page table. Get page entry, then get physical page frame, make current page entry in use, if writing, make it dirty which means it’s modified, then get the physical address.

Registers

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);
}
void AddrSpace::RestoreState() {
    machine->pageTable = pageTable;
    machine->pageTableSize = numPages;
}

Run

void Machine::Run() {
    Instruction *instr = new Instruction;  // storage for decoded instruction
    if(DebugIsEnabled('m'))
        printf("Starting thread \"%s\" at time %d\n", currentThread->getName(), stats->totalTicks);
    interrupt->setStatus(UserMode);
    for (;;) {
        OneInstruction(instr);
		interrupt->OneTick();
		if (singleStep && (runUntilTime <= stats->totalTicks))
	  		Debugger();
    }
}

It runs the instructions one by one from registers. Below is how it’s fetched:

bool Machine::ReadMem(int addr, int size, int *value) {
    int data;
    ExceptionType exception;
    int physicalAddress;
    DEBUG('a', "Reading VA 0x%x, size %d\n", addr, size);
    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);
    }
    DEBUG('a', "\tvalue read = %8.8x\n", *value);
    return (TRUE);
}

First it translate virtual address to physical address, then read in main memory.

To do

test

In test directory, do below to halt.c :

int main() {
    int i, j, k;
    k = 3;
    i = 2;
    j = i - 1;
    k = i - j + k;
    Halt();
    /* not reached*/
}

Then make .

To Generate .s file, do below:

/usr/local/mips/bin/decstation-ultrix-gcc -I ../userprog -I ../threads -S halt.c

Then there is a halt.s :

	.file	1 "halt.c"
gcc2_compiled.:
__gnu_compiled_c:
	.text
	.align	2
	.globl	main
	.ent	main
main:
	.frame	$fp,40,$31		# vars= 16, regs= 2/0, args= 16, extra= 0
	.mask	0xc0000000,-4
	.fmask	0x00000000,0
	subu	$sp,$sp,40
	sw	$31,36($sp)
	sw	$fp,32($sp)
	move	$fp,$sp
	jal	__main
	li	$2,3			# 0x00000003
	sw	$2,24($fp)
	li	$2,2			# 0x00000002
	sw	$2,16($fp)
	lw	$2,16($fp)
	addu	$3,$2,-1
	sw	$3,20($fp)
	lw	$2,16($fp)
	lw	$3,20($fp)
	subu	$2,$2,$3
	lw	$3,24($fp)
	addu	$2,$3,$2
	sw	$2,24($fp)
	jal	Halt
$L1:
	move	$sp,$fp
	lw	$31,36($sp)
	lw	$fp,32($sp)
	addu	$sp,$sp,40
	j	$31
	.end	main

	.lcomm	a,160

In subu $sp,$sp,40 , it creates stack pointer. In addu $sp,$sp,40 , it takes back stack pointer.

User program

In userprog directory, first make clean , then make , then:

./nachos –d m –x ../test/halt.noff

Add below to addrspace :

void AddrSpace::print() {
    printf("page table dump: %d pages in total\n", numPages); 
    printf("============================================\n"); printf("\tVirtPage, \tPhysPage\n");
    for (int i = 0; i < numPages; i++) {
        printf("\t %d, \t\t%d\n", pageTable[i].virtualPage, pageTable[i].physicalPage);
    }
    printf("============================================\n\n");
}

And in progtest.cc , add space->print(); :

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;
    // here
    space->print();

Run nachos –d m –x ../test/halt.noff , we can see:

============================================
        VirtPage,       PhysPage
         0,             0
         1,             1
         2,             2
         3,             3
         4,             4
         5,             5
         6,             6
         7,             7
         8,             8
         9,             9
         10,            10
============================================

11 pages in total.

Back to halt.c, add static int a[40]; as global variable, then make. And in userprog run nachos –d m –x ../test/halt.noff , we can see:

page table dump: 12 pages in total
============================================
        VirtPage,       PhysPage
         0,             0
         1,             1
         2,             2
         3,             3
         4,             4
         5,             5
         6,             6
         7,             7
         8,             8
         9,             9
         10,            10
         11,            11
============================================

There are 12 pages.