In this lab, you will write the memory management code for your operating system. Memory management has two components.
The first component is a physical memory allocator for the kernel, so that the kernel can allocate memory and later free it. Your allocator will operate in units of 4096 bytes, called pages. Your task will be to maintain data structures that record which physical pages are free and which are allocated, and how many processes are sharing each allocated page. You will also write the routines to allocate and free pages of memory.
The second component of memory management is virtual memory, which maps the virtual addresses used by kernel and user software to addresses in physical memory. The x86 hardware's memory management unit (MMU) performs the mapping when instructions use memory, consulting a set of page tables. You will modify JOS to set up the MMU's page tables according to a specification we provide.
You can consider adding your answers to lab 1 to git:
$ git add lab1-questionary.txt
Use the same syntax to add any new files to version control when needed. Note that git commit is required to finalize the adding (git status will tell you about all pending changes). Other commands you may find useful are git diff, git gui, gitk and man gittutorial.
In this and future labs you will progressively build up your kernel. We will also provide you with some additional source. To fetch that source, use Git to commit your lab 1 source, fetch the latest version of the course repository, and then create a local branch called lab2 based on our lab2 branch, origin/lab2:
$ git status # On branch lab1 # Changes to be committed: # (use "git reset HEAD
..." to unstage) # # new file: lab1-questionary.txt # # Changed but not updated: # (use "git add ..." to update what will be committed) # (use "git checkout -- ..." to discard changes in working directory) # # modified: kern/kdebug.c # modified: kern/monitor.c # modified: lib/printfmt.c # $ git commit -am 'my solution to lab1' [lab1 e3f54b3] my solution to lab1 4 files changed, 149 insertions(+), 6 deletions(-) create mode 100644 lab1-questionary.txt $ git pull From http://www.cs.technion.ac.il/~cs236366/jos * [new branch] lab2 -> origin/lab2 Already up-to-date. $ git checkout -b lab2 origin/lab2 Branch lab2 set up to track remote branch lab2 from origin. Switched to a new branch 'lab2' $
The git checkout -b command shown above actually does two things: it first creates a local branch lab2 that is based on the origin/lab2 branch provided by the course staff, and second, it changes the contents of your lab directory to reflect the files stored on the lab2 branch. Git allows switching between existing branches using git checkout branch-name, though you should commit any outstanding changes on one branch before switching to a different one.
You will now need to merge the changes you made in your lab1 branch into the lab2 branch, as follows:
$ git merge lab1 Merge made by recursive. kern/kdebug.c | 11 +++++++++-- kern/monitor.c | 19 +++++++++++++++++++ lib/printfmt.c | 7 +++---- 3 files changed, 31 insertions(+), 6 deletions(-) $
In some cases, Git may not be able to figure out how to merge your changes with the new lab assignment (e.g. if you modified some of the code that is changed in the second lab assignment). In that case, the git merge command will tell you which files are conflicted, and you should first resolve the conflict (by editing the relevant files) and then commit the resulting files with git commit -a.
Lab 2 contains the following new source files, which you should browse through:
memlayout.h describes the layout of the virtual address space that you must implement by modifying pmap.c. memlayout.h and pmap.h define the Page structure that you'll use to keep track of which pages of physical memory are free. kclock.c and kclock.h manipulate 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.
Pay particular attention to memlayout.h and pmap.h, since this lab requires you to use and understand many of the definitions they contain. You may want to review inc/mmu.h, too, as it also contains a number of definitions that will be useful for this lab.
In this lab and subsequent labs, 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!) As usual, write the answers in the questionary. This time include a short description of what you did to solve your chosen challenge problem (e.g., one or two paragraph). 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.
Strive to write clean, maintainable code. This includes wise use of functions and macros which are already defined. Sometimes it's much more easier to write the "raw" expression instead of "wrapping" it in the right macros/function calls. This is because you are not familiar with the source yet. Don't do it! Search through the code to find the most coherent way to express yourself. Gradually you'll know the source better and this task will be easier. You will appreciate it later, when you'll need to read your code or search through it. If you aren't convinced yet, look at it this way: if we decide to read your code, clean and nice code will make us happier than the ugly one, and happier homework checker leads to higher homework grade ☺.
When you are ready to hand in your lab (including the filled lab2-questionary.txt), run make handin in the source directory. This will make a tar file for you, which you can then submit via webcourse site. You can list the contents of the tar file with tar -tvzf lab2-handin.tar.gz or unpack it (in another directory) with tar -xzf lab2-handin.tar.gz.
We will be grading your solutions with a grading program. You can run make grade to test your code with the grading program (no test for the questionary is provided). Grading program may rely on some in-kernel code for the check. Needless to say, that altering this code or otherwise deceiving automatic testing is considered severe cheating.
The operating system must keep track of which parts of physical RAM are free and which are currently in use. JOS manages the PC's physical memory with page granularity so that it can use the MMU to map and protect each piece of allocated memory.
You'll now write the physical page allocator. It keeps track of
which pages are free with a linked list of
objects, each corresponding to a physical page. You need to write
the physical page allocator before you can write the rest of the
virtual memory implementation, because your page table management
code will need to allocate physical memory in which to store page
Read through inc/memlayout.h and probably other files and answer the related questions in the questionary.
In the file kern/pmap.c, you must implement code for the following functions.
boot_alloc() page_init() page_alloc() page_free()
You also need to add some code to
in pmap.c, as indicated by comments there. For now, just
add the code needed leading up to the call to
You probably want to work on
check_page_alloc() tests your physical page
allocator. You should boot JOS and see whether
check_page_alloc() reports success. Fix your code so
that it passes. You may find it helpful to add your own
assert()s to verify that your assumptions are
This lab, as well as other labs, will require you to do a bit of detective work to figure out exactly what you need to do. This assignment does not describe all the details of the code you'll have to add to JOS. Look for comments in the parts of the JOS source that you have to modify; those comments often contain specifications and hints. You will need to look at related parts of JOS, at the Intel manuals, etc. You may also find it helpful to revise parts of Computer Architecture (234267 "MAMAS") lecture on virtual memory, though it has more details than we need here.
Before doing anything else, familiarize yourself with the x86's protected-mode memory management architecture: namely segmentation and page translation.
Read chapters 5 and 6 of the Intel 80386 Reference Manual, if you haven't done so already. You can skip 6.3. 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. Answer the related questions in the questionary.
In x86 terminology, a virtual address consists of a segment selector and an offset within the segment. A linear address is what you get after segment translation but before page translation. A physical address is what you finally get after both segment and page translation and what ultimately goes out on the hardware bus to your RAM. Be sure you understand the difference between these three types or "levels" of addresses!
Selector +--------------+ +-----------+ ---------->| | | | | Segmentation | | Paging | Software | |-------->| |----------> RAM Offset | Mechanism | | Mechanism | ---------->| | | | +--------------+ +-----------+ Virtual Linear Physical
While GDB can only access QEMU's memory by virtual address, it's often useful to be able to inspect physical memory while setting up virtual memory. Review the QEMU monitor commands, especially the xp command, which lets you inspect physical memory. To access the QEMU monitor, press Ctrl-a c in the terminal (the same binding returns to the serial console).
Use the xp command in the QEMU monitor and the x command in GDB to inspect memory at corresponding physical and virtual addresses and make sure you see the same data.
QEMU's info mem command may also prove useful in the lab. Our version of QEMU has also info pg command that prints out the current page table.
The JOS kernel often needs to manipulate addresses as opaque
values or as integers, without dereferencing them, for example in
the physical memory allocator. Sometimes these are virtual
addresses, and sometimes they are physical addresses. To help
document the code, the JOS source distinguishes the two cases: the
uintptr_t represents virtual addresses, and
physaddr_t represents physical addresses. Both these
types are really just synonyms for 32-bit integers
uint32_t), so the compiler won't stop you from
assigning one type to another! Since they are integer types (not
pointers), the compiler will complain if you try to
The JOS kernel can dereference a
uintptr_t by first
casting it to a pointer type. In contrast, the kernel can't
sensibly dereference a physical address, since the MMU translates
all memory references. If you cast a
physaddr_t to a
pointer and dereference it, you may be able to load and store to
the resulting address (the hardware will interpret it as a virtual
address), but you probably won't get the memory location you
|C type||Address type|
mystery_t x; char* value = return_a_pointer(); *value = 10; x = (mystery_t) value;
Recall that in part 3 of lab 1, we explored how the boot loader sets up the x86 segmentation hardware so that the kernel runs at its link address of 0xf0100000, even though it is actually loaded in physical memory just above the ROM BIOS at 0x00100000. In other words, the kernel's virtual starting address at this point is 0xf0100000, but its linear and physical starting addresses are both 0x00100000. The kernel's virtual and linear addresses differ because of the segmentation hardware, while its linear and physical addresses are the same because we have not yet enabled page translation.
In the virtual memory layout you are going to set up for JOS in this lab, we will switch from using the x86 segmentation hardware for virtual memory to using page translation instead. Using page translation, we will accomplish the same virtual memory layout we currently use segmentation for, plus much more. While we can't actually disable the segmentation hardware, we will stop using it for anything interesting, effectively disabling it by giving it segments with zero offsets. After you finish this lab and the JOS kernel successfully enables paging and "disables" segmentation, the kernel's virtual and linear addresses will be the same, while its linear and physical addresses will differ because of page translation. We'll have the same overall mapping from virtual to physical addresses, but will achieve it in a different way.
However, the JOS kernel sometimes needs to read or modify memory
for which it only knows the physical address. For example, adding a
mapping to a page table may require allocating physical memory to
store a page directory and then initializing that memory. However,
the kernel, like any other software, cannot bypass virtual memory
translation and thus cannot directly load and store to physical
addresses. One reason JOS remaps of all of physical memory starting
from physical address 0 at virtual address 0xf0000000 is to help
the kernel read and write memory for which it knows just the
physical address. In order to translate a physical address into a
virtual address that the kernel can actually read and write, the
kernel must add 0xf0000000 to the physical address to find its
corresponding virtual address in the remapped region. You should
KADDR(pa) to do that addition.
The JOS kernel also sometimes needs to be able to find a
physical address given the virtual address of the memory in which a
kernel data structure is stored. Kernel global variables and memory
boot_alloc() are in the region where the
kernel was loaded, starting at 0xf0000000, the very region where we
mapped all of physical memory. Thus, to turn a virtual address in
this region into a physical address, the kernel can simply subtract
0xf0000000. You should use
PADDR(va) to do that
In future labs you will often have the same physical page mapped
at multiple virtual addresses simultaneously (or in the address
spaces of multiple environments). You will keep a count of the
number of references to each physical page in the
pp_ref field of the
corresponding to the physical page. When this count goes to zero
for a physical page, that page can be freed because it is no longer
used. In general, this count should equal the number of times the
physical page appears below
UTOP in all page
tables (the mappings above
UTOP are mostly set up at
boot time by the kernel and should never be freed, so there's no
need to reference count them). We'll also use it to keep track of
the number of pointers we keep to the page directory pages and, in
turn, of the number of references the page directories have to page
Be careful when using page_alloc. The page it returns will always have a reference count of 0, so pp_ref should be incremented as soon as you've done something with the returned page (like inserting it into a page table). Sometimes this is handled by other functions (for example, page_insert) and sometimes the function calling page_alloc must do it directly.
Now you'll write a set of routines to manage page tables: to insert and remove linear-to-physical mappings, and to create page table pages when needed.
In the file kern/pmap.c, you must implement code for the following functions.
pgdir_walk() boot_map_segment() page_lookup() page_remove() page_insert()
page_check(), called from
i386_vm_init(), tests your page table management
routines. You should make sure it reports success before
JOS divides 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
inc/memlayout.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 virtual
address space to map in a user environment below it at the same
You'll find it helpful to refer to the JOS memory layout diagram in inc/memlayout.h (or its more colorful version) both for this part and for later labs.
Since kernel and user memory are both present in each environment's address space, we will have to use permission bits in our x86 page tables to allow user code access only to the user part of the address space. Otherwise bugs in user code might overwrite kernel data, causing a crash or more subtle malfunction; user code might also be able to steal other environments' private data.
The user environment will have no permission to any of the
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
UTOP is for the user environment to use;
the user environment will set permissions for accessing this
Now you'll set up the address space above
kernel part of the address space. inc/memlayout.h shows
the layout you should use. You'll use the functions you just wrote
to set up the appropriate linear to physical mappings.
Fill in the missing
i386_vm_init() after the call to
Your code should now pass the
i386_vm_init()maps the first four MB of virtual address space to the first four MB of physical memory, then deletes this mapping at the end of the function. Why is this mapping 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?
We consumed many
physical pages to hold the page tables for the KERNBASE mapping.
Do a more space-efficient 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!
Extend the JOS kernel monitor with commands to:
The address space layout we use in JOS is not the only one possible. An operating system might map the kernel at low linear addresses while leaving the upper part of the linear address space for user processes. 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!
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.
Since our JOS kernel's
memory management system only allocates and frees memory on page
granularity, we do not have anything comparable to a
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
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.
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. You can submit you work now.