Introduction

In project 1, you wrote code that loaded a program into memory and prepared it to be run. The actual running of the program was handled by code that we supplied. The code was run in kernel mode, i.e. with full privileges, but in a potentially unsafe manner. In this project, you will add code to GeekOS that will allow it to run user programs, i.e. programs executing safely, at lower privilege.

Much of this project description provides background information on some operating system concepts, how the 386 processor works, and how GeekOS works. This should make it easier to understand the GeekOS code and to understand what you have to do for the project. If you already know all of this, you can skip ahead to the Project Requirements section, which describes exactly what you have to do for this project.

Safe Mode for Running User Programs

In writing an operating system, you want to make a distinction between the things that operating system code are allowed to do and the things user programs are allowed to do. The goal is to protect the system from incorrect or malicious code that a user may try to run. Bad things a program could do include:

• Making the operating system and/or other user programs crash
• Looking at data that belong to the system or to other programs
• Circumventing access control
• Using hardware incorrectly, with all the negative consequences that result e.g. machine crash or data corruption

Preventing these sorts of mistakes or attacks is accomplished by controlling the parts of memory that can be accessed when user code is running and limiting the set of machine operations that the user code can execute. The 386 processor provides the operating system with facilities to support these controls.

A program that is running in this sort of controlled way is said to be running in user mode.

(also see section 2.5.1 Dual-Mode Operation in the textbook, but note that the mode bit discussed in the textbook is replaced by a privilege level in GeekOS.)

Memory Segments (also see chapter 9 in the textbook)

The facility that the processor provides for dividing up memory is its handling of memory segments. A memory segment specifies a region of memory and the "privilege level" that is required to access that memory. Each user program has its own memory segments - one for code, one for data, one for its stack, plus a couple extra for various purposes. If the operating system sets up the segments properly, a program will be limited to accessing only its own memory.

Privilege levels range from 0 to 3. Level 0 processes have the most privileges, level 3 processes have the least. Protection levels are also called rings in 386 documentation. Kernel processes will run in ring 0, user processes will run in ring 3. Besides limiting access to different memory segments, the privilege level also determines the set of processor operations available to a process. A program's privilege level is determined by the privilege level of its code segment.

Any attempt to access memory outside of the current segment will result in the all-too-familiar segmentation fault, and the process will be halted.

Another important function of memory segments is that they allow programs to use relative memory references. All memory references are interpreted by the processor to be relative to the base of the current memory segment. Instruction addresses are relative to the base of the code segment, data addresses are relative to the base of the data segment. This means that when the linker creates an executable, it doesn't need to specify where a program will sit in memory, only where the parts of the program will be compared to the start of the executable image in memory.

Descriptor Tables

The information describing a segment is stored in a data structure called a segment descriptor. The descriptors are stored in descriptor tables. The descriptor tables are located in regular memory, but the format for them is exactly specified by the processor design. The functions in the processor that manipulate memory segments assume that the appropriate data structures have been created and populated by the operating system. You will see a similar approach used when you work with multi-level page tables in a future project.

There are two ¹ types of descriptor tables. There is a single Global Descriptor Table (GDT) that contains information for all of the processes. There are multiple Local Descriptor Tables (LDT), one for each user process, that keep track of the segment descriptors for each user program. There is one entry in the GDT for each user process which contains a descriptor for the memory containing the LDT for that process.

Since all kernel processes are allowed to access all of memory, they can all share a single set of descriptors, which are stored in the GDT.

Segment Descriptor Selectors

There are six registers in the processor that keep track of the active segments:

• CS - Code Segment
• SS - Stack Segment
• DS - (Default) Data Segment
• ES, FS, GS - Extra Data Segments

These registers do not contain the actual segment descriptors. Instead, they contain Segment Descriptor Selectors, which are essentially the indices of descriptors within the GDT and the current LDT.

In addition, there are GDTR and LDTR registers for keeping track of the location of the GDT and the current LDT

The memory segments are activated by loading the address of the LDT into the LDTR and the segment selectors into the various segment registers.

You might want to review sections 3.1, 3.4, 3.4.1, 3.4.3 (pages 3-1, 3-6 thru 3-12) in the Intel manual for details.

Anatomy of a User Thread

In GeekOS, there is a distinction between Kernel Threads and User Threads. As you would expect, kernel processes run as kernel threads, while user processes run in user threads.

A kernel thread is represented by a Kernel_Thread structure:

  struct Kernel_Thread {
    unsigned long esp;                  // offset 0
    volatile unsigned long numTicks;    // offset 4
    int priority;
    DEFINE_LINK( Thread_Queue, Kernel_Thread );
    void* stackPage;
    struct User_Context* userContext;
    struct Kernel_Thread* owner;
    int refCount;
 
    // These fields are used to implement the Join() function
    Boolean alive;

    // helpful fields
    int pid;
  };

In a sense, the most important fields of a kernel thread structure are those that specify where the thread's stack is, namely stackPage and esp. Each kernel thread has a stack associated with it. Besides being used as a regular program stack (for keeping track of local variables, function arguments, return addresses and so forth), the kernel stack is where the operating system stores execution context when it switches away from a thread (either to run a different thread or to handle an interrupt.)

The kernel thread contains all of the mechanisms necessary to run and schedule a process. In order to represent user threads, GeekOS includes an extra field in the Kernel_Thread structure that points to a User_Context structure. In a thread representing a kernel process, the User_Context will be null.

In a user thread, the User_Context structure will contain all of the information that only applies to user processes, like the location of the process' LDT and the location of the executable image. The "kernel" parts of the thread are used by the O/S to schedule the thread, while the "user" parts represent the specific user program being run.

Two stacks?

User threads have two different stacks associated with them. The kernel part of the thread has a stack that is created when the thread is created. The executable image has a stack that you created when you set up the executable image. The kernel stack (sometimes called the thread stack), is used by O/S for saving context information, and for local variables used by the user process when running in kernel mode. The user stack is used as the program stack for local variables and so forth.

InitialThread State

As discussed above, before a context switch, the O/S saves out thread context information by pushing it onto the kernel stack associated with the thread. (The 386 provides a different mechanism for saving thread state, via the TSS structure, but GeekOS does not use this mechanism.)

To prepare a thread to be run for the first time, GeekOS sets up the kernel stack to look as if the thread had previously been running and had been context switched to the ready queue. This requires pushing the initial values for all of the processor registers onto the kernel stack when the thread is created. When the thread is scheduled for the first time, these initial values will be loaded into the processor registers and the thread can run.

One example of an initial value that will be loaded into a register is the instruction pointer (EIP). GeekOS pushes the entry point for the process and this value will be subsequently loaded into EIP. In the case of a kernel process, this will be the function that was passed to Start_Kernel_Thread() to create the thread.

Syscalls (also see chapter 3 of the textbook)

The operating system uses segmented memory to limit a process to only accessing memory belonging to that process. But sometimes a program will need to interact with the system in ways that require it to access other memory. For example, if the program wants to write to the screen, it may need to access video memory, which will be outside of the process' segment. Or a program may want to call an O/S routine - the Print routine, for example - which is stored outside of the process' segment.

To provide controlled access to system memory to a user program, the operating system provides a series of System Calls, also known as Syscalls. A syscall is an operating system routine that carries out some operation for the user program that calls it. But since these routines are themselves in protected memory, the O/S provides a special mechanism for making syscalls.

In order to call a syscall, a user program calls a processor interrupt. GeekOS has provided an interrupt handler that is installed as interrupt 0x90. This routine, called Syscall_Handler, examines the current value in the register eax and calls the appropriate system routine to handle the syscall request. The value in eax is called the Syscall Number. The routine that handles the syscall request is passed a copy of the caller's context state, so the values in general registers (ebx, ecx, edx) can be used by the user program to pass parameters to the handler routine and can be used to return values to the user program.

To add routines to the syscall handler to handle new syscalls, GeekOS provides a function Register_Syscall().

Before the system handles a system call - actually, before handling any kind of interrupt - the thread context is saved and the active segments are switched to the kernel segments, so all of memory can be legally accessed. Before returning from the syscall, the previous context is restored so that the program can continue running. A pointer to the stored copy of the context - on the kernel stack - is actually what is passed to the Syscall_Handler.

Inline Assembly Coding

Calling an interrupt on the 386 is done through the machine instruction INT. Since C does not provide a mechanism for making this call - since it's entirely platform-dependent - you will need to include assembly code to make the system calls. This can be done either by writing the a routine in a .asm file and exporting it so that it can be called from C, or by including inline assembly code in your C files.

The gcc compiler supports a syntax for inline assembly. The idea is that you can include snippets of assembly code in your C files and it will be assembled and incorporated with the compiled C in an appropriate way. An example of inline assembly used to make a syscall is in userProgs/libuser.c that is included in the base code for the project:

       #define SYSCALL "int $0x90"
     
       int Null( void )
       {

         int num = SYS_NULL, rc;

         __asm__ __volatile__ (
           SYSCALL
           : "=a" (rc)// system call returns value in eax
           : "a" (num)// system call number specified in eax
         );

         return rc;

       }

The inline assembly is prefaced with

  __asm__ __volatile__. 

A single machine operation is specified:

  int $0x90

The line

  : "=a" (rc)

The line

  : "a" (num)

In order to pass arguments to the syscall, you can assign values to other registers by adding clauses to the line that assigns values to variables. For example:

  : "a" (num), "b" (arg1)

This will put the value of the C variable arg1 into the register ebx.

Passing pointers to syscalls

Because arguments are always passed to syscalls through registers, you are limited to passing 32-bit values, such as ints. If you want to pass a larger argument, a structure, say, or you want to pass a string, you will need to pass a pointer to the argument instead of passing the argument.

A problem arises when the syscall handling function wants to use the pointer. Because the pointer is generated by the user program, it will be a pointer that is relative to the base of the user program's memory. When the interrupt handler is running, it will be using a data segment that spans all of memory. The handler will need to convert the pointer from user space to kernel space. You will write code to do this conversion as part of the Copy_From_User function described below.

It is also critical that your Copy_From_User function ensures that any memory to be copied from a user program really belongs to that user program. This is necessary to prevent a malicious user program from passing a bad pointer which could cause the kernel to access memory that does not belong to the user process (or worse yet invalid memory and thus causing the kernel to crash).

Project Requirements

For project 2, you will need to add the code necessary to create user threads running executables from files in the filesystem. You will also need to implement a collection of syscalls and a user library of functions to call the syscalls.

Spawn_User_Program

The top-level function for launching user programs is Spawn_User_Program in the file spawn.c. This function calls the Read_Elf_Executable function you wrote in project 1, then uses the information in the Loadable_Program structure to setup the user thread.

You should copy your implementation of Read_Elf_Executable from Project 1 into the new elf.c. When you add space for the stack, you need to change the size from 4096 to STACK_SIZE (defined in lprog.h) to give the program more stack space.

To implement Spawn_User_Program, you will need to do the following things:

• create an LDT for the process
• add a descriptor to the GDT that describes the location of the LDT
• create a selector that contains the location of the LDT descriptor within the GDT
• create descriptors for the code and data segments of the user program and add these descriptors to the LDT
• create selectors that contain the locations of the two descriptors within the LDT
• create a User_Context structure and store in it all of the information that will be needed to setup and run the user thread.

Notes on these steps:

There will only be two segments for each user program: code and data. The data segment, the stack segment, and the extra data segments will all be in a single segment that we will call the data segment.

Even though the vaddr for the data segment indicates that the start of the data segment is offset from the start of the executable image, the data segment you create should always have its base at the start of the executable image. The files we will be working with are linked such that the memory references in the data segment are aligned as if the data segment started at the beginning of the executable image. For example, say the data.vaddr were 100. If there were a data item in the first address of the data segment, its address would not be 0 - even though it is at the very start of the data segment. Its address would be 100, since the address is calculated as the offset from the beginning of the executable image.

The base of the code segment will also be at the beginning of the executable image. In this case, the vaddr actually indicates this.

There are examples in the GeekOS code of how to create descriptors and selectors, though these examples are always putting the descriptors in the GDT. You can also look at the code that we included for project 1, which contains another example. GeekOS provides a variety of functions for these operations, so look around before you start writing.

Start_User_Thread

After setting up the memory segments for the new process, Spawn_User_Program will call Start_User_Thread() in kthread.c. Start_User_Thread, which you will write, does the following:

• creates a new thread
• sets its UserContext field to the new User_Context
• initializes the stack as described above
• makes the thread runnable, so that it will be scheduled and run

Notes on these steps:

The steps involved in creating a new user thread are very similar to those involved in creating a new kernel thread. Tracing through the Start_Kernel_Thread function will help you understand what you need to do and what functions already in GeekOS can be useful.

The initial stack state for a user thread should look like:

The items at the top of this diagram are pushed first, the items at the bottom are pushed last.

The routine Push (kthread.c) can be used to push individual values and the routine Push_General_Registers (kthread.c) will push all of the general-purpose registers at once. For Eflags, you can follow the model used for setting up a kernel thread.

The stack pointer should indicate an empty stack. The user process stack you created starts at the very end of the executable image (stacks typically grow down from higher memory addresses to lower ones.) The stack pointer should be specified as an address relative to the beginning of the executable image, not as an absolute address in memory.

The final step in creating the user process it to modify the function Entry in libuser.c to call Main(argc, argv) followed by Exit

Testing Spawn_User_Program

After you have completed the project to this point, your code is able to load a user program and spawn it. In order to test this out, you can try loading the user program null.exe. This program just calls the NULL syscall, which we have implemented for you. If the program is able to call the NULL syscall successfully, you are in good shape.

The project has code in main.c that spawns /c/shell.exe when the operating system boots up. To test, you will need to replace this code with a call to load /c/null.exe.

Adding System Calls

You will need to add five syscalls to GeekOS. (There are six listed below, but we have already implemented SYS_NULL for you.)

You will need to write handler functions for the syscalls. These functions should be put into syscall.c.

You will need to install the syscall handlers with the appropriate syscall numbers, via Register_Syscall()

You will need to add user-level functions to the libuser.c library that will call the syscalls. There are already stubs for these functions in the libuser.c file.

Your kernel should support the following system calls:

Copy From User

In order to implement SYS_PRINT and SYS_SPAWN, you will need to write the function Copy_From_User that is stubbed in spawn.c. These will be needed so that you can access the strings that are passed as arguments to these functions. You should also implement Copy_To_User.

The point of validating the pointer is that we do not want to allow an incorrect or malicious program to view the contents of protected memory by passing a pointer that is outside of the process' data segment. This is even more important for Copy_To_User, where a program could cause the kernel to write arbitrary data to an arbitrary location in memory - which is a bad thing.

Copy_From_User must do the following:

• validate the passed pointer is within the user process' data segment
• validate that the end of the memory is not beyond the end of the data segment.
• convert the pointer from user space to kernel space
• copy from abolute (e.g converted) value of srcInUser to destInKernel
• return TRUE if srcInUser was legal (even if copy was truncated, see below)
• return FALSE if srcInUser was illegal i.e. out of bounds

Note: Copy_To_User/Copy_From_User do not allocate/free any buffers. The caller takes care of that.

For the SYS_PRINT and SYS_SPAWN should ensure that the supplied string is both null terminated and not larger than MAX_USER_STRING-1. They should use Copy_From_User to validate the memory region and perform a copy and then ensure that destInKernel is terminated with a \0 at either the user-supplied size or MAX_USER_STRING (whichever is smaller). You may use a third function to do this or put the code directly in both SYS_PRINT and SYS_SPAWN

Grading Criteria