1. Introduction

In this lab, your will write the memory management code for your operating system. Memory management is comprised of two components.

The first component that comes under the umbrella of memory management is virtual memory. You will set up the virtual memory layout for your operating system according to the specification we provide. Your task will be to build the page table data structure which matches our specification.

The second component is managing the physical memory of the computer. The x86 divides physical memory up into 4096 byte regions called pages. Your task will be to maintain data structures that record which pages are free and allocated and how many processes are sharing each allocated page. You will also write the routines to allocate and free pages of memory.

You should now download the code for the lab and untar it into your 6.097 directory. For example,

athena% add gnu 6.097 sipb
athena% mkdir ~/6.097
athena% cd ~/6.097
athena% wget http://pdos.lcs.mit.edu/6.097/labs/lab2.tar.gz
athena% gtar -zxf lab2.tar.gz
drwxr-xr-x cates/wheel       0 Sep 15 19:34 2002 ossrc/
drwxr-xr-x cates/wheel       0 Sep 15 19:34 2002 ossrc/kern/
drwxr-xr-x cates/wheel       0 Sep 15 19:34 2002 ossrc/kern/inc/
-rw-r--r-- cates/wheel    2528 Sep 14 17:00 2002 ossrc/kern/inc/asm.h
.
.
.

2. Getting started

athena% cd ossrc

# build the OS and the bochs disk image
athena% gmake
      .
   [ gmake output goes here ] 
      .
      .

# this is the disk image
athena% ls -l kern/obj/bochs.img
-rw-r--r--  1 cates  wheel  5120000 Sep 15 19:48 kern/obj/bochs.img

# there is a bochsrc file in this directory (which boots this image)
athena% cat .bochsrc | grep diskc
diskc: file="./kern/obj/bochs.img", cyl=200, heads=16, spt=63

# so let's see what this OS does!
athena% bochs

panic: i386_vm_init: This function is not finished                              

3. Background

The VM layout you are going to setup divides the address space into two parts. The user process has complete control over the lower part, while the kernel maintains control over the top part. The dividing line is defined, somewhat arbitrarily by ULIM in kern/inc/mmu.h (roughly, 256MB from the top of the virtual address space).

Since, the kernel and user process co-exist in each address space, we will have to use permission bits to prevent the user from accessing the kernel's memory (ie. to enforce fault isolation). We do this as follows:

The user process will have no permission to any of the memory above ULIM, while the kernel will be able to read/write this memory. For the address range (UTOP,ULIM], both the kernel and the user process have the same permission: they can read but not write this address range. This range of address is used to expose kernel data structures, read-only to the user process. Lastly, the address space below UTOP is for the user process to use; the user process will set permissions for accessing this memory.

In this lab, you are going to setup the address space above UTOP--the kernel part of the address space.

You might want to consult chapter 3 of IA-32 Intel Architecture Software Developer's Manual, Volume 3: System programming guide for reference.

4. Turn-in procedure

You are to turn in this lab in the form of a web page. When you are done email the URL to 6.097-handin@pdos.lcs.mit.edu. Your web page should contain your answers to the questions posed in this lab and a link to your kern/pmap.c.

5. Exercises

Exercise 1: VM layout (of the kernel part of the VA space)

The layout of the kernel portion of the virtual address space will be handled by the i386_vm_init() function, defined in kern/pmap.c. The actual lay out is as described above and is diagrammed in kern/inc/mmu.h. It would behoove you to become familiar with this file as it also contains useful macros and definitions.

The comments in i386_vm_init() specify the virtual memory layout. Your task is to fill in the missing code to build a 2-level page table fulfilling this specification.

Once you have done this, run the code. The function check_boot_page_directory() (it's located about half way down the i386_vm_init()) will check over the page table you have built and report any problems. Do not continue until you pass this check. You may find it helpful to add your own assert()s to verify that your own assumptions are, in fact, correct.

Questions:

1. What entries (rows) in the page directory have been filled in at this point? What addresses do they map and where do they point? In other words, fill out this table as much as possible:

   Entry	Base Virtual Address	Points to (logically):
   1023	?	Page table for top 4MB of phys memory
   1022	?	?
   .	?	?
   .	?	?
   .	?	?
   2	0x00800000	?
   1	0x00400000	?
   0	0x00000000	[see next question?]

2. In i386_vm_init(), after check_boot_page_directory, we map the first entry of the page directory to the page table of the first four MB of RAM, but delete this mapping at the end of the function. Why is this necessary? What would happen if it were omitted? Does this actually limit our kernel to be 4MB? What must be true if our kernel were larger than 4MB?

Exercise 2: Physical page management

In the file kern/pmap.c you must implement code for the five function listed below:

ppage_init ()
ppage_alloc ()
ppage_free ()
ppage_insert ()
ppage_remove ()

Once you are done call the function ppage_check() from i386_init(), to test these functions. You must get ppage_check() to run successfully.

You may find reading kern/inc/pmap.h useful.

Questions:

1. What is the maximum amount of physical memory that this operating system can support? Why?
2. How much overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this broken down?

Exercise 3: Thinking about design decisions

Questions:

1. (From Lecture 5) On the x86, we place the kernel and user process in the same address space. What specific mechanism (i.e., what register, memory address, or bit thereof) is used to protect the kernel's memory against a malicious user process?

   Is there a comparable mechanism on the PDP-11/40 which would provide the fault isolation necessary to allow the kernel and the user process to run in the same address space? (read: "same address space" as "with the same set of PARs/PDRs")

Exercise 4: Printf Potpourri

Questions:

1. Explain the interface between printf.c and console.c. Specifically, what function does console.c export? How is this function used by printf.c?
2. Explain the following from console.c:

   1  if (crt_pos >= CRT_SIZE) {
   2    int i;
   3    bcopy (crt_buf + CRT_COLS, crt_buf, CRT_SIZE << 1);
   4    for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
   5      crt_buf[i] = 0x0700 | ' ';
   6    crt_pos -= CRT_COLS;
   7  }
   

3. For the follow questions you might wish to consult lecture notes 2. Those notes cover GCC's calling convention on the x86.

   Trace the execution of the following code step-by-step:

   int x = 1, y = 3, z = 4;
   warn ("x %d, y %x, z %d\n", x, y, z);
   

   • First, in the call to kprintf(), to what does fmt point? to what does ap point?
   • Second, list (in-order of execution) each call to cnputc, va_arg, and ksprintn. For cnputc, list its argument as well. For va_arg, list what ap points to before and after the call. For ksprintn list the values of it's first two arguments.
4. Run the following code.

       u_int i = 0x00646c72;
       warn ("H%x Wo%s", 57616, &i);
   

   What is the output? Explain how this output is arrived out in the step-by-step manner of the previous exercise.

   The output depends on that fact that Intel is little-endian. If Intel were instead big-endian what would you set i to in order to yield the same output? Would you need to change 57616 to a different value?

   Here's a description of little- and big-endian

5. If warn in the above code were replaced by printf the code fails to compile. Why? And why does the code, as shown above, compile?
6. In the following code, what is going to be printed after 'y='? (note: the answer is not a specific value.) Why does this happen?

       warn ("x=%d y=%d", 3);
   

7. Let's say that GCC changed it's calling convention so that it passed arguments in declaration order (i.e., the opposite of reverse order). How would you have to change printf or its interface so that it would still be possible to pass it a variable number of arguments?

This completes the lab.