Virtual memory

* Basic virtual memory

Example h/w system: 16-bit virtual address and 16-bit physical address.

Consider the following snippet of assembly
mov $0x802e, %rcx
mov (%rcx), %rbx

The 16-bit address 0x802e is a virtual address (VA)

 CPU---VA---> MMU ---PA--->Memory 
(MMU usually reside on the CPU chip)

Virtual address space                                
        ____
0xffff |____|
       |____|
       |    |


0x0000 |____|

Physical address space (16K memory, smaller than VA address)
0x3fff  _____
      |_____|
      |     |



0x000 |_____|

Suppose Page size is 64 bytes
How many pages are there in the VA space?
2^16/2^6 = 2^10 = 1024 pages
How many pages are there in the PA space?
2^14/2^6 = 2^8 = 256 pages

What's the address of the first virtual page?  0x0000 
What's the address of the second virtual page? 0x0040 (i.e. 0x0000 0000 0100 0000)
...                                            
What's the address of the last virtual page?   0xffc0 (i.e. 0x1111 1111 1100 0000)

What's the address of the first physical page? 0x0000
What's the address of the second physical page? 0x0040
...
What's the address of the last physical page?   0x3fc0 (i.e. 0x0011 1111 1100 0000)

Suppose virtual page  0x0040 is mapped to physical page 0x0000
Then what's VA 0x005e mapped to?  (0000 0000 0101 1110) 0x001e

     16-bit VA
|_____VPN______|___VPO___|
    10-bit         6-bit


|_____PPN_____ |___PPO___|

One-level page table.
How many entries are there from VPN to PPN? Every VPN should have its own entry
   ______________
00 |________|?srwxp|
01 |_____________|
02 |_____________|
...
ff |___________|

Draw MMU performing VA lookup 

typedef enum {
  READ = 0,
  WRITE,
  EXE,
} access_type_t;

unsigned short pagetable[1 << 10];

int curr_exe_mode; //1 for kernel 0 for user

//return 1 if there's a page fault, return 0 if okay
int
mmu_va2pa(unsigned short va, access_type_t access, unsigned short *pa) {
    unsigned short vpn = va >> 6; 
    unsigned short offset = va & 0x003f;
    unsigned short pte = pagetable[vpn];
    if (!(pte & 0x1)) {
        return 1;
    } else if (access == EXE & !(pte & 0x1 << 1)) {
        return 1;
    } else if (access == WRITE & !(pte & 0x1 << 2)) {
       return 1;
    } else if (access == READ & !(pte & 0x1 << 3)) {
       return 1;
    } else if (!curr_exe_mode && (pte & 0x1 << 4)) {
       return 1;
    }
    *pa = (pte & ffc0) | offset;
    return 0;
}

* Multi-level page table

One level page table for x-86 64-bit, how many PTE? 48-bit VA, 4K page size

In our example, suppose 1024 page table entries are too much 

Organize into a two-level page table
32 page tables each with 32 PTE entries

Draw one page table pointing to 16 second-level page tables

Given an address 0001 0011 1110 0001, which of the second-level page tables should MMU lookup?
|_____00010____|____01111____|____100001___|

    5-bit           5-bit       6-bit

Draw picture of 2-level page table

Why does multi-level page table save space?

* OS, processes

VM is managed by OS
What is OS?

Draw picture

Chrome, rklab, gcc, 
__________________
|____  OS _______|
|_____h/w________|

OS: a layer of software between app and h/w
two purposes: 1) hides (messy) details of h/w
              2) manages resources among many running user programs

OS' concrete jobs:
* scheduling (illusion of excluse use of CPU)
* VM management (illusion of excluse use of memory)
* file system, networking, other I/O