Important update: Your git repos are being updated with a modification to the system call wrapper for this assignment. Updates will start at at 11:45pm on 11/16/12, and may take up to an hour to update all groups. Please be sure to git pull.
A process' page table serves to map virtual memory addresses to physical memory addresses. In addition to this basic mapping, the page table also includes information such as, which pages are readable in userspace, which are dirty, which are read only, and more. Ordinarily, a process' page table is privileged information that is largely only accessible from within the kernel. In this assignment, inspired by Dune, we want to allow processes to view their own page table, including all the extra bits of information stored along with the physical address mapping. The Dune paper goes into detail on some of the advantages exposing this information provides, among the most notable being usefulness for garbage collectors. This would be particularly helpful for Android as user-level programs are Java-based and efficient garbage collection for these Java-based programs on a memory-constrained mobile device could have noticeable performance benefits.
In the Linux kernel, as you'll soon learn in class, the page table does not exist simply as a flat table with an entry for each virtual address. Instead, it is broken into layers. In userspace, we have much more leeway when it comes to how we can store our page table and so there we shall treat it as if it was just one large basic table with an entry for every page. We can do this by mapping each individual page table entry in the kernel into a memory region in userspace. By doing a remapping, updates to the page table entries will seamlessly appear in the userspace memory region. We can also do the mapping in such a way that sections of the page table without any page table entries present will appear as empty (null) just as they would in the kernel (this part has been done for you). This can even be done without incurring RAM usage overhead.
Your task is to create a system call, which after calling, will expose the processes' page table in a read-only form and will remain up to date as the process executes. Do not allow the process to modify the page table. You will do this by remapping page table entries in the kernel into a memory region mapped in userspace (not by copying any data!).
Obtaining the Mapping:
To set up the page table mapping in user space, you are to implement the following system call:
/* Map the current processes' page table into userspace. * After successfully completing this call, addr will contain * the current process' page table indexed by page number with * each index containing the corresponding page table entry for * that page number (i.e. virtual address). * @addr A previously mmap'ed memory region prepped for use * with this system call. A wrapper has been provided * for you to prep this memory region. */ int expose_page_table(void *addr);The address space passed to expose_page_table() must be of sufficient size and accessibility, otherwise it is an error. Errors should be handled appropriately. On success, 0 is to be returned. On failure, the appropriate negative errno is to be returned.
Hints:
- Although the overall design of the page table in the Linux
kernel is a four-layer system, the ARM architecture actually only
has two layers. The diagram below shows a snippet of this overall structure:
- Remapping of kernel memory into userspace is page based and so a partial page cannot be remapped.
- remap_pfn_range() will be of use to you.
- After successfully implementing the system call, if you call it with the argument page_table, you will be able to view any page table entry by reading get_page(page_table, page num) (which will be NULL if there is no page present). The get_page macro has been added to the test.c file in the latest git update.
-
Implementing this system call on ARM adds an extra hurdle. On ARM, the pte
is allocated as a page, but only half is really used for storing page table
entries. This is best described using a comment from
arch/arm/include/asm/pgtable.h:
/* * Hardware-wise, we have a two level page table structure, where the first * level has 4096 entries, and the second level has 256 entries. Each entry * is one 32-bit word. Most of the bits in the second level entry are used * by hardware, and there aren't any "accessed" and "dirty" bits. * * Linux on the other hand has a four level page table structure, which can * be wrapped to fit a two level page table structure easily - using the PGD * and PTE only. However, Linux also expects one "PTE" table per page, and * at least a "dirty" bit. * * Therefore, we tweak the implementation slightly - we tell Linux that we * have 2048 entries in the first level, each of which is 8 bytes (iow, two * hardware pointers to the second level.) The second level contains two * hardware PTE tables arranged contiguously, preceded by Linux versions * which contain the state information Linux needs. We, therefore, end up * with 512 entries in the "PTE" level. * * This leads to the page tables having the following layout: * * pgd pte * | | * +--------+ * | | +------------+ +0 * +- - - - + | Linux pt 0 | * | | +------------+ +1024 * +--------+ +0 | Linux pt 1 | * | |-----> +------------+ +2048 * +- - - - + +4 | h/w pt 0 | * | |-----> +------------+ +3072 * +--------+ +8 | h/w pt 1 | * | | +------------+ +4096 */
Due to this, you cannot cleanly remap the page table entries into userspace memory as part of a table (since you can't remap with granularity finer than a page). Instead, you must account for the extra, essentially wasted space, that comes with each pte that's remapped. To do this, you can remap full pte structures into a memory region double the size of the page table and then adjust your indexing accordingly. A macro for indexing into the table, called get_page(), has been provided in test.c in the latest git update.
Citations:
Demonstrate that your system call works with a test program that prints out the page table in the following format:
[page num] [virt addr] [phys addr] [young bit] [file bit] [dirty bit] [read only bit] [user bit] e.g. 266789 0x41225000 0xafffb 1 1 0 1 1Example updated above.
If a page is not present, do not print it.
In addition to the above test program, framework for another test program has been provided. In this program there exists two functions in an already compiled object file:
/** * Hides a message somewhere in memory. */ void store_super_double_secret_msg(void); /** * Decodes a message hidden in memory. * @addr - Address of the page the message is stored in. * Returns 0 on success, -1 on failure. */ int super_double_secret_msg_decoder(void *addr);You should record the state of the page table prior to calling store_super_double_secret_msg(), then check the state again after calling it. Look for newly paged-in pages and pass the virtual address for each new page you find into super_double_secret_msg_decoder() to decode the super secret secret message.
Implement this test program so that it can decode the message. You do not have to write the message down anywhere, just be sure your test program can find it when run.