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 4,096 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.
The files you need for lab 3 are available in ~class/src/lab3.tar.gz. However, in this and future labs you will need to merge your changes in from the first lab, so that you progressively build on the same kernel. With each new lab we will hand out a source tree containing additional files and possibly some changes to existing files you must merge into your source tree.
You may wish to familiarize yourself with the diff and patch commands. For this class, we recommend that you use the CVS tool to manage your source tree, as this will automate some of the merging. This kind of "Diff-and-merge" is an important and unavoidable component of pretty much all real OS development activity, particularly for device drivers and other hardware support where free operating systems often track each other's driver updates. You will probably find that CVS is far from perfect, but that it makes the task of tracking software much easier. Since CVS is widely used, any time you spend learning to do this effectively is time well spent. You can also investigate other alternatives, including subversion, prcs, and arch.
Here is how you can set yourself up with a CVS repository. First, very importantly, save the work you did on lab 2 by renaming the lab2 directory containing your solution. The mv (move) command allows you to do this.
% mv lab2 lab2.saved
%
Next, you must create a CVS repository for your work. The repository will contain a revision history of all the changes you have made to the sources, as well as the versions of the lab software that we distribute for each lab. Note that you will never need to manipulate the contents of the CVS repository except through the cvs command, but CVS uses the information in the repository when updating your copies of files.
You must select a pathname for your CVS repository. We recommend ~/cvsroot (subdirectory cvsroot of your home directory. For most CVS commands, you will have to ensure the CVSROOT environment variable points to this path. To create the repository, use the cvs init command:
% setenv CVSROOT ~/cvsroot % cvs init %
Next, you will want to import a pristine copy of the lab2 files that we distributed, check the changes you made for the lab2 solution into the repository, import the files we distribute for lab3, and merge the lab3 changes into the man repository. To help you do this, CVS supports a notion of development branches. All the work you do will be check in along a revision history called the main trunk. However, you will import the lab files we distribute along what CVS calles the vendor branch.
The code we distributed for lab2 will be the initial code you import into the CVS repository. This code is a common ancestor both for your solution to lab2, and for the lab3 software we distribute. From then on, lab code we distribute will follow its own development path along the vendor branch, while your changes go on the main trunk. However, you can check changes in from the vendor branch to the main trunk. Thus, conceptually, your CVS repository will end up looking like this:
+------+ +------+ +--------+ ! LAB2 !--! SOL2 !--! merged !--... <- The main trunk +------+ +------+ +--------+ ! * ! * ! +------* +------+ "Vendor" branch -> +------! LAB3 !----! LAB4 !----... +------+ +------+
The first thing to do is to unpack and import the pristine lab2 sources into your newly created CVS repository. Make sure you have renamed the old lab2 directory before doing this, or you will lose your work!
% tar xzf ~class/src/lab2.tar.gz % cd lab2 % cvs import -m "lab2 import" jos JOS LAB2 N jos/CODING N jos/GNUmakefile N jos/.bochsrc ... N jos/lib/string.c No conflicts created by this import % cd .. % cvs co jos cvs checkout: Updating jos U jos/.bochsrc U jos/CODING ... U jos/lib/string.c %The cvs import command takes three arguments, first is the name of the module to import. Here, we are calling the operating system jos. This means that in ordinary circumstances, when you check the operating system code out of the repository it will be in a directory called jos. The second argument is a symbolic tag name for the vendor branch. What you call this doesn't really matter, as long as you are always consistent. Here we chose the name JOS. The third argument is a tag for this particular version of the software being imported. We chose LAB2 because we are importing the sources for lab 2. The third argument is important, because we will use this to refer to this particular version of the software. Note the -m argument simply specifies a change message to be included in the repository. This is useful later if you later are browsing the revision history with the cvs log command, as it can help remind you what particular changes are.
The cvs co command stands for "checkout". It extracts by default latest copy of the software from the main trunk (though you can specify other versions with the -r flag). You must specify the name of the module to check out, which in this case is jos. The checkout command then creates a directory called jos with the code. You can browse this directory. It looks exactly like the contents of lab2, except that there are extra directories called CVS where CVS keeps some extra information about what exactly you have checked out. You shouldn't ordinarily mess with the contents of the CVS directory.
Next, you will want to check in your solution to lab2. Assuming you moved the directory to lab2.saved, and assuming you only changed the printfmt.c and monitor.c files, you can do so as follows:
% cp lab2.saved/lib/printfmt.c jos/lib/ % cp lab2.saved/kern/monitor.c jos/kern/ % cd jos % cvs ci -m "my solution to lab 2" cvs commit: Examining . cvs commit: Examining boot cvs commit: Examining inc cvs commit: Examining kern cvs commit: Examining lib Checking in kern/monitor.c; /home/u1/dm/class/aos/mycvs/jos/kern/monitor.c,v <-- monitor.c new revision: 1.2; previous revision: 1.1 done Checking in lib/printfmt.c; /home/u1/dm/class/aos/mycvs/jos/lib/printfmt.c,v <-- printfmt.c new revision: 1.2; previous revision: 1.1 done % cvs tag SOL2 cvs tag: Tagging . T .bochsrc ... T lib/string.c % cd .. %The cvs ci command stands for "commit" (though the abbreviation is also probably inspired by the RCS, where "ci" stands for "check in"). cvs ci incorporates the local changes you have made back into the CVS repository. As with import, you should specify a message with the -m flag. (If you don't, CVS will put you in an editor to edit the message, effectively forcing you to compose some sort of log message.)
The cvs tag command assigns a symbolic tag to the currently checked-out version of the software. You don't need to use this command here, but in case you ever want to refer back to the exact version of the software you turned in as your solution for lab 2, this way you can do it with the SOL2 tag.
The final thing you must do is to import the lab 3 distribution along the vendor branch, merge the changes, and check them in.
% tar xzf ~class/src/lab3.tar.gz % cd lab3 % cvs import -m "lab3 import" jos JOS LAB3 U jos/CODING U jos/GNUmakefile U jos/.bochsrc U jos/lib/string.c No conflicts created by this import % cd ../jos % cvs up -dP -jLAB2 -jLAB3 cvs update: Updating . U grade.sh cvs update: Updating boot cvs update: Updating inc cvs update: Updating kern U kern/init.c U kern/kclock.c U kern/kclock.h U kern/pmap.c U kern/pmap.h cvs update: Updating lib % cvs ci -m "merged lab2 -> lab3 changes" cvs commit: Examining . cvs commit: Examining boot cvs commit: Examining inc cvs commit: Examining kern cvs commit: Examining lib %The cvs up command (short for "update") is used to update your current working copy of the sources. With no arguments, it updates your code to the latest version of the main trunk (or to the latest version of a particular branch, if you are working along a branch). You will usually want to give the -d and -P arguments to the cvs up command. -d says to create any new directories that have appeared in the repository. -P says to "prune" or eliminate any directories that are now empty. (One of CVS's limitations is that you cannot really delete directories, but if you always give the -P argument update, you can effectively delete a directory by deleting all the files inside of it.)
The -j option to cvs up specifies other versions to merge in. Here we specified that CVS should update the current code by merging in changes between source with tags LAB2 and LAB3. With only a single -j option, CVS will update from the version specified to the latest version on its particular branch. However, this sometimes doesn't handle new or deleted files properly, so we recommend specifying both versions always.
Note that the cvs ci command does not actually do anything in the above example, because the vendor branch is special in that newly added files automatically get added to the main trunk as well. However, if lab3 had modified any files that already existed in the repository, you would want to issue a commit at this point, which is why we included the command.
Some other CVS commands you need to know about:
You will notice that lab 2 contains the following new source files, which you should browse through:
When you are ready to hand in your lab code and write-up, commit your code to CVS, run cvs tag SOL3 if you wish, and then run gmake handin in the jos 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 jos directory.
As before, we will be grading your solutions with a grading program. You can run gmake grade in the jos 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.
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. |
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 the previous lab, 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 the next lab,
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:
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.
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.
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
|
Make sure you can answer these questions:
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?] |
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?
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:
|
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. |
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 |
Be able to answer the following questions:
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 freeThink of other commands or extensions to these commands that may be useful for debugging, and add them. |
This completes the lab.