Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

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

Please indicate your answer 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 252 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 (248 bytes of memory.

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 248 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?

A pointer is a virtual address, so if a pointer is 8 bytes, so 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?

12 (212 = 4096)

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 248 bytes and we have a 4096 byte page size, how many entries would this big array have? And how much space would it consume?

Our total address space is 248, but twelve of those bits are page offsets, so we are left with 48 - 12 = 36 bits of virtual page number. We need one element in this big array to translate each page number, so that's 236 entries. Each entry is 8 bytes (23), so the table would occupy 239 bytes of memory.

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

It takes up way too much space! 239 is half a terabyte! None of our machines have that much memory (machines that large do exist, but they aren't yet the norm).

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.

File:Abstract-translation.png

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-byte virtual addresses and a 16-byte page size. However, it can support a much (?) larger physical address space: physical addresses are 12 bytes!

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

If the page is 16 bytes, then you need 4 bits to represent the page offset.

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

If 4 of the 8 bits are page offset, that leaves 4 bits for page number, so the MMU would have 16 entries, one for each page.

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

You could have multiple processes, all of whom have full address spaces (i.e., every page is allocated), and they could all be in memory at the same time.

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

Sure -- that's the state of the world on our laptops and most machines all the time! A typical laptop might have anywhere from 4-16GB of memory, but the x86 virtual address space is 248. Having a large virtual address space lets us run programs that are larger than our physical memory.

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

This is a bit subtle, so let's walk through it. Each MMU entry must convert from a virtual page number to a physical one -- but the page offset just carries through from virtual to physical. The physical address space is 12 bits, of which the lowest four bits are page offset -- that leaves 8 bits of page number. So, that is the minimum number of bits that we'd need in an MMU entry.

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.

File:Eniac.png

Question 10: 0x1E

The virtual page number is 1, so we look at the entry at index 1, which is 0xAD. So, we form the address by keeping the page offset (E) and tacking it on the end of the physical page number, producing 0xADE.

Question 11: 0x7D

Virtual page numberi s 7; corresponding entry is 0xBE, final physical address is 0xBED.

Question 12: 0x32

The entry at index 3 is invalid, so this is a fault.

Question 13: NULL

NULL is 0, the entry there is 0xB0, so we would get 0xB00.

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.

Well, a fault means that there is no valid mapping, so that must mean that processes do not have a valid entry in their MMU for virtual page 0. That's pretty cool. How could you test that? What happens if you reference 4 or 8 or any value less than 4096?

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 248 not 264):

File:Flatva.png

the x86 hardware thinks about it like this:

File:Hierarchical va.png

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

File:X86tables.png

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?

9 bits is 512.

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

512 * 8 = 4096 (as does 29+3 (This is a really good time to be on top of your powers of two and to be comfortable doing these kinds of manipulations.)

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

OK, the L4 has 512 entries, each of which maps a 4KB page. So (512 * 4096) = 29 * 212 = 221 = 2 MB.

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

We still have 512 entries, but this time, each entry references an L4 page table, so we would multiple 512 by the amount of memory mapped by an L4 page table, which we conveniently computed above. So (512 * 2MB) = 29 * 221 = 230 = 1 GB.

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

There are a couple of ways we might figure this out, but we'll do this top down. There is 1 L1 table; it has 512 entries, so there are a maximum of 512 L2 page tables. Each of those page tables can reference a maximum of 512 L3 page tables, So: 512 * 512 = 29 * 29 = 218 = ~256,000