(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

• real mode
  • segment*16+offset ==> physical address
• protected mode
  • selector:offset (logical addr)
    ==SEGMENTATION==>
  • linear address
    ==PAGING ==>
  • physical address

Segmentation

• segment register holds selector
• logical address "selector:offset" => linear
• seg register usually 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, SS:EBP
    • ex: pushl %ecx, pushl $_i
    • ex: popl %ecx
    • ex: movl 4(%ebp),%eax
  • CS:EIP
    • ex: instruction fetch
  • String instructions: read from DS:ESI, write to ES:EDI
    • ex: rep movsb
  • Exception: segment register overrides
    • ex: fs:movl _fromhere,%eax
• how to setup (lgdt)
• segment descriptor cache
  • thus: common to reload seg register following lgdt
• always on

• 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: linear space => physical 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 linear (NOT physical) address
• TLB -- caches vpn -> ppn mappings
• how to turn on (set CR0_PE bit of %cr0)

• DOS: real mode, 16-bit, unprotected
• OS/2, Windows/286, 80s Unix: protected mode, 16-bit segmented model
• Current: protected mode, 32-bit flat model
  • paging provides protection and virtual memory
    • generally, virtual address = linear address
  • segmentation only used for special tricks
    • thread-local storage
    • fast context switching for small processes