[Syllable-kernel] preparing for 64-bit in the kernel

[Jake H. <jh...@po...>]

I've just finished taking some notes on how 64-bit virtual memory is 
handled on x86-64.  The good news is that 64-bit virtual memory 
structures are based on the PAE 36-bit extension introduced with the 
Pentium Pro processor to add support for up to 64GB of physical memory. 
If we add support for PAE, we can test it on our existing 32-bit 
machines, gain support for systems with >4GB of physical memory, *and* 
prepare Syllable for full x86-64 support later on.

Here's a quick summary of the existing Intel virtual memory system, then 
PAE-36, and finally the 64-bit "native" memory mapping.  Set your e-mail 
client to use a nonproportional font for the box graphics to render 
correctly.  :-)

The 32-bit x86 CPUs use a page size of 4K.  A 32-bit linear address 
(which is equivalent to a physical memory address as long as your 
segment base is set to 0, which is always true on Syllable) maps to a 
32-bit virtual address like this:

31                22 21                12 11                0
-------------------------------------------------------------
|    Directory      |    Page Table      | Offset w/in page |
-------------------------------------------------------------

The upper 10 bits select one of 1024 page table pointers from the page 
directory (a 4K page pointed to by register CR3) and the middle 10 bits 
select one of 1024 entries in the page table pointed to by the page 
directory entry.

The Pentium Pro introduced the PSE feature, which allows you to use 4K 
pages and large 4MB pages at the same time (one useful optimization we 
could add in the future is to map the kernel and kernel module code into 
a single 4MB page to free up TLB entries for caching user page lookups):

31                22 21                                     0
-------------------------------------------------------------
|    Directory      |         Offset w/in 4MB page          |
-------------------------------------------------------------

In this case, the page directory entries point directly to the page 
instead of pointing to a page table.

Moving right along, the PAE extension, also introduced with the PPro, 
expands the size of each entry in the page directory and the page tables 
from 4 bytes to 8 bytes, so now there are only 512 entries in a 4K table 
instead of 1024.  The extra space can be used to map up to 64GB (36 
bits) of physical memory into the 4GB virtual address space. With 4K 
page mapping, PAE looks like this:

31 30 29                21 20                12 11                0
-------------------------------------------------------------------
|D.P.|     Directory      |    Page Table      | Offset w/in page |
-------------------------------------------------------------------

The page table and page directory indexes are one bit smaller, since 
there are now half the number of entries (512) in each table.  The upper 
two bits are new and add an extra layer of indirection.  With PAE 
enabled, the CR3 register now points to a page-directory-pointer table 
(must be on a 32-byte boundary) and the D.P. bits select one of four 
entries from it.  Each entry is 64 bits in size and the selected entry 
contains a pointer to the 36-bit linear base address of the page-table 
directory to use.

Only one more type of page and then we can move on to x86-64:  PAE mode 
with large pages.  This time the offset within the page is one bit 
smaller than with PSE, so each large page is 2MB instead of 4MB:

31 30 29                21 20                                     0
-------------------------------------------------------------------
|D.P.|     Directory      |        Offset within 2MB page         |
-------------------------------------------------------------------

On to the 64-bit stuff, which Intel calls EM64T and AMD calls AMD64. I 
gathered this info from the Intel docs, available here:
http://www.intel.com/technology/64bitextensions/
If you don't already have a copy of the IA-32 manuals, then you should 
definitely download them from here:
http://developer.intel.com/design/pentium4/manuals/index_new.htm

In PAE, each entry is 8 bytes instead of 4.  The 64-bit extensions take 
advantage of the extra space to allow each entry to point to a 40-bit 
physical address, which allows for up to 1024TB of memory (to paraphrase 
billg: 1024TB of RAM should be enough for anyone!).  Presently, only 48 
bits in a 64-bit linear (virtual) address are used and the page sizes 
remain 4K and 2MB:

47     39 38    30 29         21 20           12 11                0
--------------------------------------------------------------------
|  PML4  |  D.P.  |  Directory  |  Page Table   | Offset w/in page |
--------------------------------------------------------------------

47     39 38    30 29         21 20                                0
--------------------------------------------------------------------
|  PML4  |  D.P.  |  Directory  |     Offset within 2MB page       |
--------------------------------------------------------------------

Compared to 32-bit PAE, the previous page directory pointer (PDP) has 
been expanded from 2 bits to 9, and can now select one of 512 page 
directories from a 4K PDP table.  Like the 32-bit PDP table, each entry 
is 64 bits in size.  x86-64 adds a new table called the page map level 4 
table, or PML4 for short, which works the same way as the PDP table, 
giving an awkward five levels of indirection in total:

PML4 -> PDP -> PDE -> PTE -> physical page

For comparison, the DEC Alpha has one fewer level of page tables to 
decode up to 43 bits (8192TB) of virtual memory, using 8K pages:

63        43 42       33 32       23 22       13 12                0
--------------------------------------------------------------------
|  unused   |  Level 1  |  Level 2  |  Level 3  | Offset w/in page |
--------------------------------------------------------------------

Jake