Mit 6.828 Lab 3 Report

part 1: User Environments and Exception Handling

Environment State

The user environments’ information is stored in Env structure. We can see its structure in inc/env.h

This will be useful later.

Allocating the Environments Array

Exercises 1. Modify mem_init() in kern/pmap.c to allocate and map the envs array. This array consists of exactly NENV instances of the Env structure allocated much like how you allocated the pages array. Also like the pages array, the memory backing envsshould also be mapped user read-only at UENVS (defined in inc/memlayout.h) so user processes can read from this array.

You should run your code and make sure check_kern_pgdir() succeeds.

The envs array allocation is as same as the pages array allocation.

Then set the envs array to [UENVS, UENVS+PTSIZE) with the permission

user read-only.

Creating and Running Environments

In Exercise 2, we need to finish some functions in kern/env.c.

Exercise 2. In the file env.c, finish coding the following functions:

  • env_init()

    Initialize all of the Env structures in the envs array and add them to the env_free_list. Also calls env_init_percpu, which configures the segmentation hardware with separate segments for privilege level 0 (kernel) and privilege level 3 (user).

  • env_setup_vm()

    Allocate a page directory for a new environment and initialize the kernel portion of the new environment’s address space.

  • region_alloc()

    Allocates and maps physical memory for an environment

  • load_icode()

    You will need to parse an ELF binary image, much like the boot loader already does, and load its contents into the user address space of a new environment.

  • env_create()

    Allocate an environment with env_alloc and call load_icode to load an ELF binary into it.

  • env_run()

    Start a given environment running in user mode.

As you write these functions, you might find the new cprintf verb %e useful — it prints a description corresponding to an error code. For example,

will panic with the message “env_alloc: out of memory”.

In env_init() function, we need to set up the array. Cause we need to prove the environments are in the free list in the same order they are in the envs array, create the env_free_list in reverse order is a good idea.

In env_setup_vm() function, we need to set e->env_pgdir and initialize the page directory. The code has already alloc a page p, we just set the e->env_pgdir to p. At first the environment page dictionary is as same as kernel page dictionary, so we can use memcpy to copy the kernel page dictionary to p. At last, remember to set p->pp_ref to the right number.

In region_alloc(), we need to alloc a memory region for load_icode(). This is very similar to boot_region(). Remember to align its length.

load_icode() is the hardest part in this exercises. We need to load the binary to the memory. Traversing all Proghdr in elf header, if we need to load the program alloc the region, copy the part to the region. And then set the %eip of the environment trap frame to the entry point. Another important point is using the user environment page dictionary instead of the kernel page dictionary when copy alloc the region.

env_create() is easy after we finish the function above. Alloc an environment structure, load the binary file and set the environment type.

The last function is `env_running() . What should env_run do in the hint has been made very clear. We are not making more descriptions here.

Handling Interrupts and Exceptions

Exercise 3. Read Chapter 9, Exceptions and Interrupts in the 80386 Programmer’s Manual (or Chapter 5 of the IA-32 Developer’s Manual), if you haven’t already.

One thing to be mentions is the table 9-7 in 80386 Programmer’s Manual. We will used it later.

Description Number Interrupt Error Code
Divide error 0 No
Debug exceptions 1 No
Breakpoint 3 No
Overflow 4 No
Bounds check 5 No
Invalid opcode 6 No
Coprocessor not available 7 No
System error 8 Yes (always 0)
Coprocessor Segment Overrun 9 No
Invalid TSS 10 Yes
Segment not present 11 Yes
Stack exception 12 Yes
General protection fault 13 Yes
Page fault 14 Yes
Coprocessor error 15 No
Two-byte SW interrupt 0~255 No

Basics of Protected Control Transfer

This part we introduce two mechanisms to provide the exception and interrupts protection: The Interrupt Descriptor Table (IDT) and The Task State Segment. IDT is a table to define the interrupt entry-points. The task state segment is a place to save the old processor state before the interrupt or exception handler occurred. In this way the exception handler can later restore that old state and resume the interrupted code from where it left off.

Types of Exceptions and Interrupts

In JOS, we only need to care about the exceptions 0~31 and 48 (System Call)

Setting Up the IDT

Exercise 4. Edit trapentry.S and trap.c and implement the features described above. The macros TRAPHANDLER and TRAPHANDLER_NOEC in trapentry.S should help you, as well as the T_* defines in inc/trap.h. You will need to add an entry point in trapentry.S (using those macros) for each trap defined in inc/trap.h, and you’ll have to provide _alltraps which the TRAPHANDLERmacros refer to. You will also need to modify trap_init() to initialize the idt to point to each of these entry points defined in trapentry.S; the SETGATE macro will be helpful here.

Your _alltraps should:

  1. push values to make the stack look like a struct Trapframe

  2. load GD_KD into %ds and %es

  3. pushl %esp to pass a pointer to the Trapframe as an argument to trap()

  4. call trap (can trap ever return?)

Consider using the pushal instruction; it fits nicely with the layout of the struct Trapframe.

Test your trap handling code using some of the test programs in the user directory that cause exceptions before making any system calls, such as user/divzero. You should be able to get make grade to succeed on the divzero, softint, and badsegmenttests at this point.

We do this exercise with challenge 1.

Challenge 1

Challenge! You probably have a lot of very similar code right now, between the lists of TRAPHANDLER in trapentry.S and their installations in trap.c. Clean this up. Change the macros in trapentry.S to automatically generate a table for trap.c to use. Note that you can switch between laying down code and data in the assembler by using the directives .text and .data.

_alltraps is a function to call into the trap function. Follow the instructions in the exercise description.

Then we need to set the trap handler. Every trap description and its’ type and other information is list in the table above. More over, in challenge 1 we need to automatically generate a table, so we manage these handler as an array.

At last we set the trap gate in trap_init(). Since we have map all the trap handler to vectors, we can easily set it with a loop.

Questions

Answer the following questions in your answers-lab3.txt:

  1. What is the purpose of having an individual handler function for each exception/interrupt? (i.e., if all exceptions/interrupts were delivered to the same handler, what feature that exists in the current implementation could not be provided?)

  2. Did you have to do anything to make the user/softint program behave correctly? The grade script expects it to produce a general protection fault (trap 13), but softint‘s code says int $14. Whyshould this produce interrupt vector 13? What happens if the kernel actually allows softint‘s int $14 instruction to invoke the kernel’s page fault handler (which is interrupt vector 14)?

  1. Because different interrupt need to have different handler function. Some interrupt have a error code while some haven’t.

  2. Because the user space can’t generate a page fault directly. (The page fault’s IDL is 0) So it get a general protection. If it allow a page fault interrupt, the page fault can handler in user mode. However, in user mode we can’t modify the page table, so the page fault handler can’t work normally.

This is part A end.

Part B: Page Faults, Breakpoints Exceptions, and System Calls

Handling Page Faults & The Breakpoint Exception

Exercise 5. Modify trap_dispatch() to dispatch page fault exceptions to page_fault_handler(). You should now be able to get make grade to succeed on the faultread, faultreadkernel, faultwrite, and faultwritekernel tests. If any of them don’t work, figure out why and fix them. Remember that you can boot JOS into a particular user program using make run-x or make run-x-nox. For instance, make run-hello-nox runs the hello user program.

Exercise 6. Modify trap_dispatch() to make breakpoint exceptions invoke the kernel monitor. You should now be able to get make grade to succeed on the breakpoint test.

Just check the tf->tf_trapno. For each type of the fault, do the corresponding handler function.

Questions

  1. The break point test case will either generate a break point exception or a general protection fault depending on how you initialized the break point entry in the IDT (i.e., your call to SETGATE from trap_init). Why? How do you need to set it up in order to get the breakpoint exception to work as specified above and what incorrect setup would cause it to trigger a general protection fault?

  2. What do you think is the point of these mechanisms, particularly in light of what the user/softint test program does?

  1. If the breakpoint exception’s CPL is 0, it will get a general protection. Otherwise (the CPL is 3) it will get a breakpoint exception.

  2. This is necessary for user to debug their progress just like challenge 2 do.

System calls

Exercise 7. Add a handler in the kernel for interrupt vector T_SYSCALL. You will have to edit kern/trapentry.S and kern/trap.c‘s trap_init(). You also need to change trap_dispatch() to handle the system call interrupt by calling syscall() (defined in kern/syscall.c) with the appropriate arguments, and then arranging for the return value to be passed back to the user process in %eax. Finally, you need to implement syscall() in kern/syscall.c. Make sure syscall() returns -E_INVAL if the system call number is invalid. You should read and understand lib/syscall.c (especially the inline assembly routine) in order to confirm your understanding of the system call interface. Handle all the system calls listed in inc/syscall.h by invoking the corresponding kernel function for each call.

Run the user/hello program under your kernel (make run-hello). It should print “hello, world” on the console and then cause a page fault in user mode. If this does not happen, it probably means your system call handler isn’t quite right. You should also now be able to get make grade to succeed on the testbss test

First we need to call the syscall() function like what we do exercise 5&6. It’s parameter is in tf->tf_regs and it’s return value is saved in tf->tf_regs.reg_eax

sys_call() is similar to trap_dispatch(). call different function based on syscallno

Challenge 3

Challenge! Implement system calls using the sysenter and sysexit instructions instead of using int 0x30 and iret.

The sysenter/sysexit instructions were designed by Intel to be faster than int/iret. They do this by using registers instead of the stack and by making assumptions about how the segmentation registers are used. The exact details of these instructions can be found in Volume 2B of the Intel reference manuals.

The easiest way to add support for these instructions in JOS is to add a sysenter_handler in kern/trapentry.S that saves enough information about the user environment to return to it, sets up the kernel environment, pushes the arguments to syscall() and calls syscall() directly. Once syscall() returns, set everything up for and execute the sysexit instruction. You will also need to add code to kern/init.c to set up the necessary model specific registers (MSRs). Section 6.1.2 in Volume 2 of the AMD Architecture Programmer’s Manual and the reference on SYSENTER in Volume 2B of the Intel reference manuals give good descriptions of the relevant MSRs. You can find an implementation of wrmsr to add to inc/x86.h for writing to these MSRs here.

Finally, lib/syscall.c must be changed to support making a system call with sysenter. Here is a possible register layout for the sysenter instruction:

GCC’s inline assembler will automatically save registers that you tell it to load values directly into. Don’t forget to either save (push) and restore (pop) other registers that you clobber, or tell the inline assembler that you’re clobbering them. The inline assembler doesn’t support saving %ebp, so you will need to add code to save and restore it yourself. The return address can be put into %esi by using an instruction like leal after_sysenter_label, %%esi.

Note that this only supports 4 arguments, so you will need to leave the old method of doing system calls around to support 5 argument system calls. Furthermore, because this fast path doesn’t update the current environment’s trap frame, it won’t be suitable for some of the system calls we add in later labs.

You may have to revisit your code once we enable asynchronous interrupts in the next lab. Specifically, you’ll need to enable interrupts when returning to the user process, which sysexit doesn’t do for you.

This is a really hard challenge. First we need to know how to set up the necessary model specific registers (MSRs). We add the wrmsr function to inc/x86.h

Then we used the wrmsr to set 3 register in trap_init:

The three constant is define as follow:

So we place it in syscall.h

Next is syscall_handler, similar to _alltraps, but syscall_trap will return, so we need pop the frame we push before.After that, since sysexit will fetch the target instruction in EDX and Update ESP in ECX. We need to set this two register.

And syscall_trap is just like what we do in trap_dispatch. Call the syscall function with the parameter in the trap frame.

last is syscall , we need to save the EBP and put the return address into ESI (In fact I don’t know why the after_sysenter_label is 0f and why just simply put the ESP to EBP can save and restore EBP

User-mode startup

Exercise 8. Add the required code to the user library, then boot your kernel. You should see user/hello print “hello, world” and then print “i am environment 00001000“. user/hello then attempts to “exit” by calling sys_env_destroy() (see lib/libmain.c and lib/exit.c). Since the kernel currently only supports one user environment, it should report that it has destroyed the only environment and then drop into the kernel monitor. You should be able to get make grade to succeed on the hello test.

The last 3 exercises is petty easy. This exercises ask us to get thisenv in lib/libmain.c

Page faults and memory protection

Exercise 9. Change kern/trap.c to panic if a page fault happens in kernel mode.

Hint: to determine whether a fault happened in user mode or in kernel mode, check the low bits of the tf_cs.

Read user_mem_assert in kern/pmap.c and implement user_mem_check in that same file.

Change kern/syscall.c to sanity check arguments to system calls.

vBoot your kernel, running user/buggyhello. The environment should be destroyed, and the kernel should not panic. You should see:

Finally, change debuginfo_eip in kern/kdebug.c to call user_mem_check on usd, stabs, and stabstr. If you now run user/breakpoint, you should be able to run backtrace from the kernel monitor and see the backtrace traverse into lib/libmain.c before the kernel panics with a page fault. What causes this page fault? You don’t need to fix it, but you should understand why it happens.

We just check the low bit of the tf_cs in page_fault_handler

Then finish the user_mem_check in kern/pmap.c. Just travel the memory region and check the permission bit using page_lookup .

Last add the memory check when a user system call happened. Only the sys_cputs need to be checked.

Exercise 10. Boot your kernel, running user/evilhello. The environment should be destroyed, and the kernel should not panic. You should see:

Now we can run make grade.

Lab 3 End

Mit6.828 Lab 2 Report

Part 1: Physical Page Management

Exercise 1.

In the file kern/pmap.c, you must implement code for the following functions (probably in the order given).

boot_alloc() is used to alloc the memory without page structure. We just simply follow its guide.

mem_init() is used to initial the memory. Before check_page_free_list(1), the part we needed to finish is allocate the memory for pages array. It needs npages*sizeof(struct PageInfo) byte. After allocate it, we initialize all fields of each struct PageInfo to 0.

page_init() is used to initial the page structure.

Looking into the inc\memlayout.h, we can know PageInfo has two members: pp_link to record the next page on the free list, pp_ref to record the pointers to this page. So for the free pages, we can treat as below:

page_alloc() is used to allocate a page.

page_free() is used to free a page. Remember to assert the page have no reference.

For the alloced pages, we just set the pp_link to NULL.

Then follow the instructions, we can find out all the free page and initial the page in [0, EXTPHYMEM).

As the pages in [EXTPHYMEM, ...), we can know the memory from next_free to 4GB in the virtual memory is free. So the page in [(int)(boot_alloc(0)) - KERNBASE) / PGSIZE, ...) is free.( Because the physical in (0, 1GB) is mapped to (3GB, 4GB) )

Part 2: Virtual Memory

Exercise 2.

I have learning something about the page mechanism in ICS and OS last year. So I don’t take too much time in this exercise.

Virtual, Linear, and Physical Addresses

Exercise 3.

Try the commands info pg info mem xp and x , the result showed as follow:

Question1.

The answer is uintptr_t because char* is a virtual address. So we have to used uintptr_t to dereference a virtual address.

Reference counting

Page Table Management

Exercise 4. Implement code for the functions:

This exercise need us to use some functions and definition written in pmap.c and mmu.h to code robust and readable. Here are some functions description:

First is pgdir_walk(). This function is used to get the pointer of page table in page directory. Looking into mmu.h , we can know how the linear address translate in to a physical address.

Remember to create a empty page table when the page table is not exist.

Next is boot_map_region(), this function map virtual address to physical address in the page table. We just traverse every page table entry and map it to corresponding address.

The last 3 function: page_lookup(), page_remove() and page_insert() all have the same mode. First find the page table entry (PTE) of the virtual address using pgdir_walk(), and then return the value, remove the value or insert a new value of the PTE.

Part 3: Kernel Address Space

The address space is divided into two part: user address space for user at low address and kernel address space at high address. So we need a mechanism to prevent user modify the kernel space.

Permissions and Fault Isolation

OS using permissions bits in page table to limit user and kernel’s read and write in memory.

Initializing the Kernel Address Space

Exercise 5. Fill in the missing code in mem_init() after the call to check_page().

we need to map three part of the physical address to linear address: page table space, kernel stack space and the kernel in the physical address.

Question 2: Fill out the table
Entry Base Virtual Address Points to (logically):
1023 0xffc00000 Page table for top 4MB of phys memory
1022 0xff800000
..
960 0xf0000000 KERNBASE
956 0xef000000 UPAGE
0 0x00000000 Empty Memory
Question 3:

We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel’s memory? What specific mechanisms protect the kernel memory?

Using the permission bit in the page table to control the permissions.

Question 4:

What is the maximum amount of physical memory that this operating system can support? Why?

Because the pages array take up to 4MB of space, each PageInfo need 4 byte to allocate, so there are most page. The maximum amount of physical memory is

Question 5:

How much space overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this overhead broken down?

If we actually had the maximum amount of physical memory, we need a page for page dictionary and 1024 page for page table. So the overhead is .

So we need including the pages array.

Question 6:

Revisit the page table setup in kern/entry.S and kern/entrypgdir.c. Immediately after we turn on paging, EIP is still a low number (a little over 1MB). At what point do we transition to running at an EIP above KERNBASE? What makes it possible for us to continue executing at a low EIP between when we enable paging and when we begin running at an EIP above KERNBASE? Why is this transition necessary?

In kern/entry.S, at jmp *%eax we transition to running at an EIP above KERNBASE. Because we map the virtual address 0~4MB and KERNBASE ~ KEANBASE + 4 MB to the physical address 0~4MB, so EIP can work both in high number and low number. If we don’t do so, it will crash after enable the paging mechanism. Before enable paging mechanism, the EIP is point to the physical address. After that, the EIP is point to the virtual address.

Try make grade , the result is shown below: