6.828 Fall 2004 Lab 2: Memory Management

Handed out Wednesday, September 15, 2004
Due Thursday, September 30, 2004

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, where we set up the PC'S Memory Management Unit (MMU) hardware to map the virtual addresses used by software into different, physical addresses for purposes of accessing memory. You will set up the virtual memory layout for JOS according to the specification we provide. Your task will be to build a page table data structure to match our specification.

The second component is managing the physical memory of the computer so that the kernel can be dynamically allocate memory for various uses, and later deallocate that memory and re-assign it for different purposes. 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.

Getting started

Download the code for lab 2 from http://pdos.lcs.mit.edu/6.828/2004/labs/lab2/lab2.tar.gz and untar it into your 6.828 directory, just as you did for lab 1. You will then need to merge the changes between our lab 1 and lab 2 source code trees into your own kernel code resulting from completing lab 1.

In this and future labs you will progressively build on this same kernel. With each new lab we will hand out a source tree containing additional files and possibly some changes to existing files. You will need to compare the new source tree against the one we provided for the previous lab in order to figure out what new code you need to incorporate into your kernel. You may find it useful to keep a "pristine" copy of our source tree for each lab around along with your modified versions. You should expect to become intimately familiar with the Unix diff utility if you aren't already, and patch can be highly useful as well. If you're particularly organized you might try using cvs and learn how to deal with branches. "Diff-and-merge" is an important and unavoidable component of all real OS development activity, so any time you spend learning to do this effectively is time well spent.

One option is to just merge in your changes manually. If you remember what functions you modified, you can copy the changes into the lab2 code. To actually see what changes you made, and try to patch them in to the code, run the following sequence of commands. Be warned that these utilities are not perfect, and merging in the changes by hand may be simpler. 

cd ~/6.828

# this creates a tar of what you handed in, for backup purposes
tar czvf lab1-handin.tar.gz lab1

mkdir given-code
cd given-code
tar xzf ../lab1.tar.gz
cd ..
mv given-code/lab1 lab1-unchanged

# now we have the handed out lab1 code in lab1-unchanged

diff -r -u lab1-unchanged lab1 > lab1-changes.txt

# It is very important to look at the patch file.  All of the changes
# in it should be for code that you added to lab 1 and want to bring
# to lab 2.  If there are other changes (like changes to the
# makefiles), then you should NOT run the 'patch' command below.
# Instead, you should apply the patch by hand.  If you decide to apply
# it with patch, then run the commands below.

cd lab2
patch -p1 -u < ../lab1-changes.txt

# if any chunks failed, then you will need to look at the rejects
# files (.rej) and merge those changes in yourself.

Lab 2 contains the following new source files, which you should browse through as you merge them into your kernel:

The first two files provide a template for the kernel memory management code you will write. The second two files relate to the PC's battery-backed clock and CMOS RAM hardware, in which the BIOS records the amount of physical memory the PC contains, among other things. The code in pmap.c needs to read this device hardware in order to figure out how much physical memory there is, but that part of the code is done for you: you do not need to know the details of how the CMOS hardware works.

Lab Requirements

In this lab and subsequent labs, you will need to do all of the regular exercises described in the lab and at least one challenge problem. (Some challenge problems are more challenging than others, of course!) Additionally, you will need to write up brief answers to the questions posed in the lab and a short (e.g., one or two paragraph) description of what you did to solve your chosen challenge problem. If you implement more than one challenge problem, you only need to describe one of them in the write-up, though of course you are welcome to do more. Place the write-up in a file called answers.txt (plain text) or answers.html (HTML format) in the top level of your lab2 directory before handing in your work.

Hand-In Procedure

When you are ready to hand in your lab code and write-up, run gmake handin in the lab2 directory. This will first do a gmake clean to clean out any .o files and executables, and then tar up and submit the entire contents of your lab2 directory.

As before, we will be grading your solutions with a grading program. You can run gmake grade in the lab2 directory to test your kernel with the grading program. You may change any of the kernel source and header files you need to in order to complete the lab, but needless to say you must not change or otherwise subvert the grading code.

Part 1: Virtual Memory

Before doing anything else, you will need to familiarize yourself with the x86's protected-mode memory management architecture: namely segmentation and page translation.

Exercise 1. Read chapters 5 and 6 of the Intel 80386 Reference Manual, if you haven't done so already. Although JOS relies most heavily on page translation, you will also need a basic understanding of how segmentation works in protected mode to understand what's going on in JOS.

Virtual, Linear, and Physical Addresses

In x86 terminology, a virtual address is a "segment:offset"-style address before segment translation is performed; a linear address is what you get after segmentation but before page translation; and a physical address is what you finally get after both segmentation and page translation. Be sure you understand the difference between these three types or "levels" of addresses!

Exercise 2. Review the debugger section in the Bochs user manual, and make sure you understand which debugger commands deal with which kinds of addresses. In particular, note the various vb, lb, and pb breakpoint commands to set breakpoints at virtual, linear, and physical addresses. The default b command breaks at a physical address. Also note that the x command examines data at a linear address, while the command xp takes a physical address. Sadly there is no xv at all.

In Part 3 of Lab 1 we noted that the boot loader sets up the x86 segmentation hardware so that the kernel appears to run at its link address of 0xf0100020, even though it is actually loaded in physical memory just above the ROM BIOS at 0x00100020. In other words, the kernel's virtual starting address at this point is 0xf0100020, but its linear and physical starting addresses are both 0x00100020. The kernel's linear and physical addresses are the same because we have not yet initialized or enabled page translation.

In the virtual memory layout you are going to set up for JOS, we will stop using the x86 segmentation hardware for anything interesting, and instead start using page translation to accomplish everything we've already done with segmentation and much more. That is, after you finish this lab and the JOS kernel successfully enables paging, linear addresses will be the same as (the offset portion of) the kernel's virtual addresses, rather than being the same as physical addresses as they are when the boot loader first enters the kernel.

In JOS, we divide the processor's 32-bit linear address space into two parts. User environments (processes), which we will begin loading and running in lab 3, will have control over the layout and contents of the lower part, while the kernel always maintains complete control over the upper part. The dividing line is defined somewhat arbitrarily by the symbol ULIM in inc/pmap.h, reserving approximately 256MB of linear (and therefore virtual) address space for the kernel. This explains why we needed to give the kernel such a high link address in lab 1: otherwise there would not be enough room in the kernel's linear address space to map in a user environment below it at the same time.

Permissions and Fault Isolation

Since the kernel and user environment will effectively co-exist in each environment's address space, we will have to use permission bits in our x86 page tables to prevent user code from accessing the kernel's memory: i.e., to enforce fault isolation. We do this as follows.

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

Initializing the Kernel Portion of the Linear Address Space

In this lab, you are going to set up the address space above UTOP - the kernel part of the address space. The layout of this portion of the virtual address space will be handled by the i386_vm_init() function, defined in kern/pmap.c. The actual layout is as described is diagrammed in inc/pmap.h. It would behoove you to become familiar with this file as well as inc/mmu.h, which contains useful macros and definitions relating to the x86 memory management hardware.

Exercise 3. Implement the following functions in kern/pmap.c: 
	alloc()
	boot_pgdir_walk()
	boot_map_segment()
	i386_vm_init()
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. The other functions are helper routines you will find useful.

Once you have done this, run the code. The function call to check_boot_pgdir() (it's located about half way down the i386_vm_init()) will check over the page table you have built and report any problems it finds. 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.

Make sure you can answer these 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??
    .??
    .??
    .??
    20x00800000?
    10x00400000?
    00x00000000[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?
  3. (From Lecture 4) On the x86, we place the kernel and user environment 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 environment to run in the same address space? (read: "same address space" as "with the same set of PARs/PDRs")

Challenge! We wasted a lot of page tables to allocate the KERNBASE mapping. Do a better job using the PTE_PS ("Page Size") bit in the page directory entries. This bit was not supported in the original 80386, but is supported on more recent x86 processors. You will therefore have to refer to Volume 3 of the current Intel manuals. Make sure you design the kernel to use this optimization only on processors that support it!
Note: If you compiled bochs yourself, be sure that the appropriate configuration options were specified. By default bochs does not support some extended page table features, and the tools.html page did not include them at the beginning of the term.

Challenge! Extend the JOS kernel monitor with commands to:
  • Display in a useful and easy-to-read format all of the physical page mappings (or lack thereof) that apply to a particular range of virtual/linear addresses in the currently active address space. For example, you might enter 'showmappings 0x3000 0x5000' to display the physical page mappings and corresponding permission bits that apply to the pages at virtual addresses 0x3000, 0x4000, and 0x5000.
  • Explicitly set, clear, or change the permissions of any mapping in the current address space.
  • Dump the contents of a range of memory given either a virtual or physical address range. Be sure the dump code behaves correctly when the range extends across page boundaries!
  • Do anything else that you think might be useful later for debugging the kernel. (There's a good chance it will be!)

Address Space Layout Alternatives

Many other address space layout schemes besides the one we chose for JOS are certainly possible; all of this is up to the operating system. It is possible, for example, to map the kernel at low linear addresses while leaving the upper part of the linear address space for user processes to use. x86 kernels generally do not take this approach, however, because one of the x86's backward-compatibility modes, known as virtual 8086 mode, is "hard-wired" in the processor to use the bottom part of the linear address space, and thus cannot be used at all if the kernel is mapped there.

It is even possible, though much more difficult, to design the kernel so as not to have to reserve any fixed portion of the processor's linear or virtual address space for itself, but instead effectively to allow allow user-level processes unrestricted use of the entire 4GB of virtual address space - while still fully protecting the kernel from these processes and protecting different processes from each other!

Challenge! Write up an outline of how a kernel could be designed to allow user environments unrestricted use of the full 4GB virtual and linear address space. Hint: the technique is sometimes known as "follow the bouncing kernel." In your design, be sure to address exactly what has to happen when the processor transitions between kernel and user modes, and how the kernel would accomplish such transitions. Also describe how the kernel would access physical memory and I/O devices in this scheme, and how the kernel would access a user environment's virtual address space during system calls and the like. Finally, think about and describe the advantages and disadvantages of such a scheme in terms of flexibility, performance, kernel complexity, and other factors you can think of.

Part 2: Physical Page Management

Besides setting up the processor hardware to translate virtual addresses correctly into physical addresses, the operating system must also keep track of which parts of available RAM are free and which are currently in use for various purposes. In JOS we will manage the PC's physical memory strictly on a page granularity: i.e., only in units of whole, page-aligned 4KB pages. This design simplifies the memory management system and nicely matches the 4KB page size that the processor uses for page translation purposes.

Exercise 4. In the file kern/pmap.c, you must implement code for the five functions listed below: You may find it useful to read inc/pmap.h and kern/pmap.h. 
	page_init()
	page_alloc()
	page_free()
	pgdir_walk()
	page_insert()
	page_remove()

The function page_check(), called from i386_init(), tests these functions. You must get page_check() to run successfully.

Be able to answer the following questions:

  1. What is the maximum amount of physical memory that this operating system can support? Why?
  2. 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?
Challenge! Since our JOS kernel's memory management system only allocates and frees memory on page granularity, we do not have anything comparable to a general-purpose malloc/free facility that we can use within the kernel. This could be a problem if we want to support certain types of I/O devices that require physically contiguous buffers larger than 4KB in size, or if we want user-level environments, and not just the kernel, to be able to allocate and map 4MB superpages for maximum processor efficiency. (See the earlier challenge problem about PTE_PS.)
Note: If you compiled bochs yourself, be sure that the appropriate configuration options were specified. By default bochs does not support some extended page table features, and the tools.html page did not include them at the beginning of the term.

Generalize the kernel's memory allocation system to support pages of a variety of power-of-two allocation unit sizes from 4KB up to some reasonable maximum of your choice. Be sure you have some way to divide larger allocation units into smaller ones on demand, and to coalesce multiple small allocation units back into larger units when possible. Think about the issues that might arise in such a system.

Challenge! Extend the JOS kernel monitor with commands to allocate and free pages explicitly, and display whether or not any given page of physical memory is currently allocated. For example: 
	K> alloc_page
		0x13000
	K> page_status 0x13000
		allocated
	K> free_page 0x13000
	K> page_status 0x13000
		free
Think of other commands or extensions to these commands that may be useful for debugging, and add them.

This completes the lab.

Version: $Revision: 1.8 $. Last modified: $Date: 2004/09/19 20:50:32 $