(protected-mode) address translation on the x86

Required reading: Chapter 3 (Protected-Mode Memory)

Handout: x86 translation diagram

PC block diagram
  - physical address
  - base, IO hole, extended memory
  - Physical address == what is on CPU's address pins

translation
  - selector:offset (logical addr)
     ==SEGMENTATION==> 
  - linear address
     ==PAGING ==>
  - physical address

segmentation
 - logical address "selector:offset" => linear
 - implicit in instruction
   * DS:REG
     - ex1: Write 'A' to top left corner of screen
       movl $0xb8000, %eax; movb 0x41, (%eax)
       (or movb $0x41, 0xb8000)
     - ex2: flag = 1; 
       movl $0x1, _flag
   * SS:ESP
     - ex: pushl %ecx, pushl $_i
     - ex: popl %ecx
   * CS:EIP
     - ex: instruction fetch
 - how to setup (lgdt)
 - segment descriptor cache
   - thus: common to reload seg register following lgdt
 - always on

paging
 - linear => physical
 - page size 4096
 - linear address 10:10:12 (pdir offset, ptbl offset, pg offset)
 - pg tbl terminology: (Intel usage vs General usage)
     - root ==> page directory 
     - 2-lvl ==> page tables 
 - cr3 -- PA of root of page table 
 - (2-level) pg tbl data structure

 - The steps taken by the MMU (specifically the paging part of the
   MMU) are shown in pseudo-code.  

   The pseudo-code is in some sense not faithful to the actions of the
   MMU.  For example, the hardware doesn't really do shifts; it is just a
   question of running wires differently.

   void
   access (uint x, bool kernel, bool write)
   {
     if (!(x & PG_P)  
        => page fault -- page not present
     if (!(x & PG_U) && user)
        => page fault -- not access for user
   
     if (write && !(x & PG_W))
       if (user)   
          => page fault -- not writable
       else if (!(x & PG_U))
         => page fault -- not writable
       else if (%CR0 & CR0_WP) 
         => page fault -- not writable
   }
   
   // maps va => pa
   uint
   translate (uint va, bool kernel, bool write)
   {
     uint pde; 
     pde = read_mem (%CR3 + 4*(va >> 22));
     access (pde, kernel, read);
     pte = read_mem ( (pde & ~0xfff) + 4*((va >> 12) & 0x3ff));
     access (pte, kernel, read);
     return (pte & ~0xfff) + (va & 0xfff);
   }

 - intuitive picture: VA space => PA space (vpn => ppn)

 Virtual                                 Physical
 Address                                 Address
 Space                                   Space

+------+                                +------+   
|2^20-1|             /----------------> |2^20-1|
+------+          /                     +------+
|2^20-2|\      /                        |2^20-2|
+------+   \/                           +------+
|2^20-3| /    \                         |2^20-3|
+------+         \                      +------+
   .                \                      .
   .                    \                  .
   .                        \              .
+------+                        \       +------+
|  2   |                           \--> |  2   |
+------+                                +------+
|vpn=1 | -----------------------------> |ppn=1 |
+------+                                +------+
|vpn=0 |                                |ppn=0 |
+------+                                +------+

arbitrary mapping from VPN to PPN (pg offset is untouched). 
VPN = virtual page number
PPN = physical page number

 - permissions
   - apply to virtual (NOT physical) address
 - TLB -- caches vpn -> ppn mappings
 - how to turn on (set CR0_PE bit of %cr0)