Section 6: Virtual Memory and Pagetables #

In virtual memory, instead of each process directly working with addresses in physical memory, each process has its own virtual memory space. Processes work with addresses in their own virtual memory, and every address in this virtual memory space maps to a unique address in physical memory. Each process can thus only access memory at physical addresses that its virtual addresses map to, effectively stopping it from interfering with any other processes; this is known as process isolation. That is to say, if Eve tried to change the memory in a physical address belonging to a different process, she simply couldn't. Eve's process can only work with virtual addresses, and all of Eve's virtual addresses map to physical addresses designated for her own process! Eve could get herself into an infinite loop, but thanks to process isolation, there's no way for her to mess with the kernel or other processes.

When we use virtual memory, the virtual address used by a process doesn't have to directly map to the same physical address. In other words, the memory mappings for individual processes do not need to match physical memory. The memory allocated for a process in virtual memory may form a contiguous segment, but the actual physical memory those virtual addresses map to doesn't need to be contiguous. This means we can allocate noncontiguous physical blocks, but treat them as contiguous for a process like process 4.

This means that instead of allocating massive contiguous segments for each process, the kernel can just allocate one page at a time; when a process needs additional memory, the kernel simply allocates the next available page of physical memory and maps the desired page in virtual memory map to this new physical page. Despite the pages not being contiguous in physical memory, they are one contiguous block in virtual memory! This prevents us from allocating too little or too much memory to each process.

Pagetables keep track of the physical address that each virtual address maps to.

There are 4 levels of page tables: L4, L3, L2, and L1:

• A L4 pagetable contains 512 entries, each of which can hold the physical address of a L3 pagetable.
• A L3 pagetable contains 512 entries, each of which can hold the physical address of a L2 pagetable.
• A L3 pagetable contains 512 entries, each of which can hold the physical address of a L1 pagetable.
• A L1 pagetable contains 512 entries, each of which can hold the physical address of a page of memory. A page is a large block of memory (typically 4096 bytes/4 KB).

Each page table takes up a single page of memory. Since a page is 4096=2^12 bytes and an address is (8=2^3) bytes, page tables can store (2^12)/(2^3)=(2^9=512) unique addresses. (That's where this number comes from!)

Pagetables may seem like they take up a lot of space (a process can have up to (512^3) L1 pagetables), but a lot of space can be saved by simply not mapping addresses not present in a virtual address space.

A "sparse" data structure ignores empty data by not tracking it. In the case of pagetables, this means not storing data corresponding to unmapped virtual addresses. This is important for pagetables since for most processes, the majority of virtual address space will not be mapped, saving memory.

The physical address of a process' L4 pagetable is stored in the special register %cr3. Since this register determines the virtual memory view of a process, only the kernel can modify this register. When a virtual address needs to be translated into a physical address, the translation hardware uses the physical address in the %cr3 register to find the L4 page table to start at.

Despite virtual addresses consisting of 8 bytes (64 bits total) like physical addresses, only the lower 48 bits get used during virtual address translation. 36 of these bits are used to find the right page of physical memory by indexing into page tables. The remaining 12 bits are the offset into the physical page. They tell us the address within the page.

Recall that each level of page table has 512 = 2^9 indexes, each storing an address for another page table (or in the case of the L1 page table, physical page addresses). Each of these indexes can be expressed using 9 bits total (this enumerates all indexes of 0 through 512).

The 47th through 39th bit (9 total) in the virtual address correspond to the index within the L4 page table. The 38th through 30th bit correspond to the index within the L3 page table. The 29th through 21st bit the L2 page table, and the 20th through 12th bit to the L1 page table.

A single page consists of 2^12=4096 bytes. Each of these bytes should be accessible. Once we access the right physical page by using the address in the corresponding index of the L1 page table, we need to know which byte our virtual address corresponds to. This is where the 12 final bytes for the virtual address come in. They tell us which byte within the page (the offset) this virtual address corresponds to.

The 63rd through 48th bits are unused for virtual address translation. They may, however, store additional information, such as if the page of memory this virtual address belongs to is executable or non-executable.

In order to translate a virtual address to the physical address, the hardware finds the process' L4 page table using the %cr3 register, indexes into it using bits 47 through 39 to obtain the L3 page table, indexes into the L3 page table using bits 38 though 30 to obtain the L2 page table, indexes into the L2 page table using bits 29 through 21 to obtain the L1 page table, and uses the 20 through 12 bit to obtain the L1 page table. The remaining 11 bits are used to determine the offset into the resulting page.

In the example:

• The L4 index is 254, and the L3 page table is therefore at 0x3000000.
• The L3 index is 282, so translation uses the L2 page table at 0x9007000.
• The L2 index is 215, so translation uses the L1 page table at 0x4500000.
• The L1 index is 5, so the relevant entry is 0b 1000 0000 0000 0000 0000 1010 1100 0010 1011 0001 0000 1000 0101 0000 0000 0111.
• The top 16 bits of the entry are unused (except for the NX bit in position 63), which leaves 0b 0000 1010 1100 0010 1011 0001 0000 1000 0101 0000 0000 0111.
• The bottom 12 bits hold protection flags and get replaced by the offset into the page from the original virtual address. The offset is 0100 0100 0101.
• Hence, the resulting 48-bit physical address is 0b 0000 1010 1100 0010 1011 0001 0000 1000 0101 0100 0100 0101, which converted to hex gives 0x0ac2 b108 5445.

A 4 KB page is 4096 = 2^12 bytes. Addresses are now 4 = 2^2 bytes. To determine how many unique addresses we can hold in a page, we can divide the size of a page (in bytes) by the size of an address (in bytes).

Since (2^12)/(2^2)=2^10, we know that a 4 KB page can hold 2^10 unique 4 byte addresses.

We know that a 4 KB page can hold 2^10 unique 4 byte addresses. In order to access each of these, we need a series of bits that can take on at least 2^10 different values. We can keep track of a page table index using 10 bits of a 4 byte (32 bit) virtual address.

Even with 4 byte virtual addresses, virtual address will still consist of a page offset and indexes for page tables

For page offsets, the size of pages have not changed. They're still 4096 = 2^12 bytes, so in order every byte within the page, we'll still need to use 12 bits.

We know that it requires 10 bits to access each index of a 4 KB page table that stores 4 byte addresses. We have 2 levels of page tables, so this will require 20 bits in total

In a 4 byte virtual address, we only have 32 bits we could possibly use for virtual address translation. 12 of these bits are used for calculating the page offset, leaving us with 20 bits for page table indexing. Each level of page table requires 10 bits, which gives us just enough bits for 2 whole levels of page tables!