CS202: Lab 4: WeensyOS
Goal
You will implement complete and correct memory isolation for WeensyOS processes. Then you’ll implement full virtual memory, which will improve utilization. You’ll implement fork() (creating new processes at runtime) and for extra credit, you?ll implement exit() (destroying processes at runtime).
We have provided you with a lot of support code for this assignment; the code you will need to write is in fact limited in extent. Our complete solution (for all 5 stages) consists of well under 300 lines of code beyond what we initially hand out to you. All the code you write will go in kernel.c (except for part of step 6).
Testing, checking, and validation
For this assignment, your primary checking method will be to run your instance of Weensy OS and visually compare it to the images you see below in the assignment.
Studying these graphical memory maps carefully is the best way to determine whether your WeensyOS code for each stage is working correctly. Therefore, you will definitely want to make sure you understand how to read these maps before you startto code.
We supply some grading scripts, outlined at the end of the lab, but those will not be your principal source of feedback. For the most part, they indicate only whether a given step is passing or failing; look to the memory maps to understand why.
Initial state
Enter the Docker environment:
$ ./cs202-run-docker
cs202-user@172b6e333e91:~/cs202-labs$ cd lab4/
cs202-user@172b6e333e91:~/cs202-labs/lab4$ make run
The rest of these instructions presume that you are in the Docker environment. We omit the cs202-user@172b6e333e91:~/cs202-labs part of the prompt.
make run should cause you to see something like the below, which shows four processes running in parallel,each running a version of the program in p-allocator:
This image loops forever; in an actual run, the bars will move to the right and stay there. Don’t worry if your image has different numbers of K’s or otherwise has different details.
If your bars run painfully slowly, edit the p-allocator.c file and reduce the ALLOC_SLOWDOWN constant.
Stop now to read and understand p-allocator.c.
Here?s how to interpret the memory map display:
WeensyOS displays the current state of physical and virtual memory. Each character represents 4 KB of memory: a single page. There are 2 MB of physical memory in total. (Ask yourself: how many pages is this?)
WeensyOS runs four processes, 1 through 4. Each process is compiled from the same source code (pallocator.c), but linked to use a different region of memory.
Each process asks the kernel for more heap memory, one page at a time, until it runs out of room. As usual, each process’s heap begins just above its code and global data, and ends just below its stack.The processes allocate heap memory at different rates: compared to Process 1, Process 2 allocates twice as quickly, Process 3 goes three times faster, and Process 4 goes four times faster. (A random number generator is used, so the exact rates may vary.) The marching rows of numbers show how quickly the heap spaces for processes 1, 2, 3, and 4 are allocated.
Here are two labeled memory diagrams, showing what the characters mean and how memory is arranged.
The virtual memory display is similar.
The virtual memory display cycles successively among the four processes? address spaces. In the base version of the WeensyOS code we give you to start from, all four processes? address spaces are the same (your job will be to change that!).
Blank spaces in the virtual memory display correspond to unmapped addresses. If a process (or the kernel) tries to access such an address, the processor will page fault.
The character shown at address X in the virtual memory display identifies the owner of the corresponding physical page.
In the virtual memory display, a character is reverse video if an application process is allowed to access the corresponding address. Initially, any process can modify all of physical memory, including the kernel. Memory is not properly isolated.
Running WeensyOS
Read the README-OS.md file for information on how to run WeensyOS.
There are several ways to debug WeensyOS. We recommend adding log_printf statements to your code.
The output of log_printf is written to the file /tmp/log.txt outside QEMU, into your lab4 working directory.
We also recommend that you use assertions (of which we saw a few in lab 1) to catch problems early. For example, call the helper functions we?ve provided, check_page_table_mappings and check_page_table_ownership to test a page table for obvious errors.
Memory system layout
The WeensyOS memory system layout is defined by several constants:
Constant Meaning
KERNEL_START_ Start of kernel code.
ADDR
KERNEL_STACK_ Top of kernel stack. The kernel stack is one page long.
TOP
console Address of CGA console memory.
PROC_START_AD Start of application code. Applications should not be able to access memory below this address, except for the single page at console.
DR
MEMSIZE_PHYSI Size of physical memory in bytes. WeensyOS does not support physical addresses ≥ this value. Defined as 0x200000 (2MB).
CAL
MEMSIZE_VIRTU Size of virtual memory. WeensyOS does not support virtual addresses ≥ this value.Defined as 0x300000 (3MB).
AL
Writing expressions for addresses
WeensyOS uses several C macros to handle addresses. They are defined at the top of x86-64.h. The most important include:
Macro Meaning
PAGESIZE Size of a memory page. Equals 4096 (or, equivalently, 1 << 12).
PAGENUMBER(addr) Page number for the page containing addr. Expands to an expression analogous to addr / PAGESIZE.
PAGEADDRESS(pn) The initial address (zeroth byte) in page number pn. Expands to an expression analogous to pn * PAGESIZE.
PAGEINDEX(addr, level) The index in the levelth page table for addr. level must be between 0 and 3; 0 returns the level-1 page table index (address bits 39–47), 1 returns the level-2 index (bits 30–38), 2 returns the level-3 index (bits 21–29), and 3 returns the level-4 index (bits 12–20).
PTE_ADDR(pe) The physical address contained in page table entry pe. Obtained by masking off the flag bits (setting the low-order 12 bits to zero).
Before you begin coding, you should both understand what these macros represent and be able to derive values for them if you were given a different page size.
Kernel and process address spaces
The version of WeensyOS you receive at the start of lab4 places the kernel and all processes in a single,shared address space. This address space is defined by the kernel_pagetable page table.
kernel_pagetable is initialized to the identity mapping: virtual address X maps to physical address X.
As you work through the lab, you will shift processes to using their own independent address spaces, where each process can access only a subset of physical memory.
The kernel, though, must remain able to access any location in physical memory. Therefore, all kernel functions run using the kernel_pagetable page table. Thus, in kernel functions, each virtual address maps to the physical address with the same number. The exception() function explicitly installs kernel_pagetable when it begins.
WeensyOS system calls are more expensive than they need to be, since every system call switches address spaces twice (once to kernel_pagetable and once back to the process?s page table). Real-world operating systems avoid this overhead. To do so, real-world kernels access memory using process page tables, rather than a kernel-specific kernel_pagetable. This makes a kernel?s code more complicated, since kernels can?t always access all of physical memory directly under that design.
Step 1: Kernel isolation
In the starting code we?ve given you, WeensyOS processes could stomp all over the kernel?s memory if they wanted to. Better prevent that. Change kernel(), the kernel initialization function, so that kernel memory is inaccessible to applications, except for the memory holding the CGA console (the single page at (uintptr_t) console == 0xB8000).
When you are done, WeensyOS should look like the below. In the virtual map, kernel memory is no longer reverse-video, since the user can?t access it. Note the lonely CGA console memory block in reverse video in the virtual address space.
Hints:
Use virtual_memory_map. A description of this function is in kernel.h. You will benefit from reading all the function descriptions in kernel.h. You can supply NULL for the allocator argument for now.
If you really want to look at the code for virtual_memory_map, it is in k-hardware.c, along with many other hardware-related functions.
The perm argument to virtual_memory_map is a bitwise-or of zero or more PTE flags, PTE_P, PTE_W, and PTE_U. PTE_P marks Present pages (pages that are mapped). PTE_W marks Writable pages. PTE_U marks User-accessible pages—pages accessible to applications. You want kernel memory to be mapped with permissions PTE_P|PTE_W, which will prevent applications from reading or writing the memory, while allowing the kernel to both read and write.
Make sure that your sys_page_alloc system call preserves kernel isolation: Applications shouldn?t be able to use sys_page_alloc to screw up the kernel.
When you’re done with this step, make sure to commit and push your code!
Step 2: Isolated address spaces
Implement process isolation by giving each process its own independent page table. Your OS memory map should look something like this when you are done:
…………