-
Notifications
You must be signed in to change notification settings - Fork 5
The Virtual Memory Challenge
Virtual Memory (VM) is an important abstraction provided by modern OSes. It gives each process its own virtual address space, and enables protection by limiting which physical addresses (real memory) that process has access to. http://en.wikipedia.org/wiki/Virtual_memory
I'm going to use VM as a motivating example to jump into a few cans of worms (source code-bases). This is structured as a set of questions that you should answer in small groups to better understand the workings of some of the systems. VM support in OSes is split between the hardware, and software. The hardware requires that the software describe the mapping between virtual addresses and physical addresses (address 4598 in a process should access physical memory 87123874198) using a radix trie called a page-table (see "multi-level page-table" in http://en.wikipedia.org/wiki/Page_table). When an address is accessed (4598), it is looked up in the page-table, and the resulting entry in the page-tables is used as the actual memory to access (87123874198). However, what happens when there is no mapping in the page-table? A fault occurs (fault #14 on x86), and most OSes make this execute the "page fault handler".
Radix tries are awesome, and are my favorite data-structure. A simple radix trie that maps between an integer, and an pointer to some object associated with that id is the cvect in Composite (see https://github.com/gparmer/Composite/blob/ppos/src/components/include/cvect.h).
The key path that you want to optimize is generally the lookup function (pass in the id, return the point to the object).
Embedded radix tries (ERTs) are the new Composite implementation.
- Code: https://github.com/gparmer/Composite/blob/ppos/src/kernel/include/ertrie.h
- Test code: https://github.com/gparmer/Composite/blob/ppos/src/platform/tests/ert/ert.c
- Page-table code based on erts: https://github.com/gparmer/Composite/blob/ppos/src/kernel/include/pgtbl.h
ERTs are quite generic. They can be used to describe radix tries with different "width", and the last level in the radix trie can have data-structures "embedded" in the tries. The functions for looking up in the tries are generic. Why all this hassle? We want the implementation to work for page-tables, capability tables, lookup tables (like cvect), etc...
The question: The lookup function must be fast. It should include no loops. Few conditions. It should take less than 16 cycles. Look these implementations. How does the compiler take something that is so generic and complicated, and generate a lookup function that is optimal?
If memory is not in the page-table, it traps to a page-fault handler. Lets check those out!
The question: Find the page-fault handler in NetBSD and in xv6. How do the two differ? What are the general functionalities that each of them perform?
When the page-fault handler is executed, it must know a few pieces of information:
- What address was the fault at?
- What type of an access caused the fault? Was it a write to a read-only mapping? Was it read from a non-existent mapping?
How is this data given to the page-fault handler?
GLHF