10/25: Introduction to Virtual Memory and the x86-64 MMU

Please place your answers on today's survey.

Let's start off by reviewing a few definitions from last time:

Physical address space This is the actual memory (DRAM) in your computer. Your laptop probably has something like 4, 8, or 16 GB. Current x86-64 machines let you have up to 52-bits of physical address space (or 2⁵² bytes).

Virtual address space This is the memory that programs (processes) think they have all to themselves. (This is what we've been drawing each time we draw memory and place things like code/text, data, heap, stack in memory.) the x86-64 supports a 48-bit virtual address space (2⁴⁸ bytes of memory). Despite this, x86-64 pointers are 64 bits wide. In current processors, the upper 16 bits of each pointer must be zero, but future extensions to the architecture may make more bits accessible.

Virtual address When we say virtual address, that refers to a location in a process's address space. In other words, a pointer!

Although your virtual address space can be as large as 2⁴⁸ bytes, in reality, the processes you run are significantly smaller and take up only a tiny part of that space. When your process tries to access a part of the address space that doesn't contain anything, the processor generates a fault. When you see the error message segmentation fault that's typically because your program is trying to access parts of the address space that it's not supposed to.

Pagesize The x86-64 manipulates virtual memory in units of pages which are 4096 bytes.

Warming Up

Question 1 If we say that a pointer occupies 64 bits (8 bytes), how large is a virtual address?

Question 2 If we have a 4096 byte page size, how many bits represent the offset of an address in a page?

Question 3 While processes access memory in terms of virtual addresses, we know that the processor must translate those virtual addresses to physical addresses and that the process does this translation in units of pages. Let's see what would happen if we implemented one big flat mapping table for the x86-64 -- that is, let's imagine a big array, indexed by a virtual page number containing a physical address (8 bytes). If the virtual address space can be as large as 2⁴⁸ bytes and we have a 4096 byte page size, how many entries would this big array have? And how much space would it consume?

Question 4 Given your answer to question 3, why doesn't the x86 use a flat array to translate addresses?

Memory Management

Supporting virtual memory is a hardware/software partnership. A piece of hardware, called the memory management unit (MMU) is responsible for mapping virtual addresses to physical addresses.

The software (operating system) is responsible for setting up the data structures that the MMU uses, so that the translations happen correctly.

Consider the following simple machine (this was version 0.1 of the ENIAC). This machine is teeny tiny. It has 8-bit virtual addresses and a 16-byte page size. However, it can support a much (?) larger physical address space: physical addresses are 12 bits long.

Question 5: How many bits in the virtual address are consumed by the page offset?

Question 6: How many entries would an MMU need to convert from virtual to physical addresses?

Question 7: Why might it be useful to have a larger physical address space than a virtual one?

Question 8: Is it ever useful to have a larger virtual address space than a physical one?

Question 9: What is the minimum number of bits that each entry in the MMU must hold?

For questions 10-13, use the mappings below to translate each virtual address to the correct physical address. If there is no translation for an address, write fault.

Question 10: 0x1E

Question 11: 0x7D

Question 12: 0x32

Question 13: NULL (0x00)

Question 14: You have probably noticed that if you dereference a NULL pointer, your program experiences a segmentation fault. Given what you know about MMUs, explain what that means.

The x86-64 MMU

Since a flat array doesn't work, the x86 needs a slightly more complicated data structure to map virtual page numbers to physical page numbers. The goal of this data structure is to make its size proportional to the amount of memory a process uses rather than the amount it might possibly use. So, while we might think of a virtual address like one of these (recall that the maximum virtual address size is 2⁴⁸ not 2⁶⁴):

the x86 hardware thinks about it like this:

That is, while the ENIAC above uses the entire virtual page number to index into its MMU translation table (which we will now call a page table), on the x86, we use different parts of the virtual page number to index into different levels of page tables. The figure below illustrates that.

Question 15: We use 9 bits to index into a page table, regardless of the level of the page table. How many entries will be in each page table?

Question 16: If each entry is 8 bytes, how large is each page table

Question 17: How much virtual memory can be mapped by a single L4 page table?

Question 18: How much virtual memory does a single L3 page table map?

Question 19: What is the maximum number of L3 page tables a process can have?