Paging
Paging is a system which allows each process to see a full virtual address space, without actually requiring the full amount of physical memory to be available or present. 32-bit x86 processors support 32-bit virtual addresses and 4-GiB virtual address spaces, and current 64-bit processors support 48-bit virtual addressing and 256-TiB virtual address spaces. Intel has released documentation for a extension to 57-bit virtual addressing and 128-PiB virtual address spaces. Currently, implementations of x86-64 have a limit of between 4 GiB and 256 TiB of physical address space (and an architectural limit of 4 PiB of physical address space).
In addition to this, paging introduces the benefit of page-level protection. In this system, user processes can only see and modify data which is paged in on their own address space, providing hardware-based isolation. System pages are also protected from user processes. On the x86-64 architecture, page-level protection now completely supersedes Segmentation as the memory protection mechanism. On the IA-32 architecture, both paging and segmentation exist, but segmentation is now considered 'legacy'.
Once an Operating System has paging, it can also make use of other benefits and workarounds, such as linear framebuffer simulation for memory-mapped IO and paging out to disk, where disk storage space is used to free up physical RAM.
MMU
Paging is achieved through the use of the Memory Management Unit (MMU). On the x86, the MMU maps memory through a series of tables, two to be exact. They are the paging directory (PD), and the paging table (PT).
Both tables contain 1024 4-byte entries, making them 4 KiB each. In the page directory, each entry points to a page table. In the page table, each entry points to a physical address that is then mapped to the virtual address found by calculating the offset within the directory and the offset within the table. This can be done as the entire table system represents a linear 4-GiB virtual memory map.
Page Directory
The topmost paging structure is the page directory. It is essentially an array of page directory entries that take the following form.
When PS=0, the page table address field represents the physical address of the page table that manages the four megabytes at that point. Please note that it is very important that this address be 4-KiB aligned. This is needed, due to the fact that the last 12 bits of the 32-bit value are overwritten by access bits and such. Similarly, when PS=1, the address must be 4-MiB aligned.
- PAT, or Page Attribute Table. If PAT is supported, then PAT along with PCD and PWT shall indicate the memory caching type. Otherwise, it must be 0.
- G, or 'Global tells the processor not to invalidate the TLB entry corresponding to the page upon a MOV to CR3 instruction. Bit 7 (PGE) in CR4 must be set to enable global pages.
- PS, or 'Page Size' stores the page size for that specific entry. If the bit is set, then the PDE maps to a page that is 4 MiB in size. Otherwise, it maps to a 4 KiB page table. Please note that 4-MiB pages require PSE to be enabled.
- A, or 'Accessed' is used to discover whether a page has been read or written to. If it has, then the bit is set, otherwise, it is not. Note that, this bit will not be cleared by the CPU, so that burden falls on the OS (if it needs this bit at all).
- PCD, is the 'Cache Disable' bit. If the bit is set, the page will not be cached. Otherwise, it will be.
- PWT, controls Write-Through' abilities of the page. If the bit is set, write-through caching is enabled. If not, then write-back is enabled instead.
- U/S, the 'User/Supervisor' bit, controls access to the page based on privilege level. If the bit is set, then the page may be accessed by all; if the bit is not set, however, only the supervisor can access it. For a page directory entry, the user bit controls access to all the pages referenced by the page directory entry. Therefore if you wish to make a page a user page, you must set the user bit in the relevant page directory entry as well as the page table entry.
- R/W, the 'Read/Write' permissions flag. If the bit is set, the page is read/write. Otherwise when it is not set, the page is read-only. The WP bit in CR0 determines if this is only applied to userland, always giving the kernel write access (the default) or both userland and the kernel (see Intel Manuals 3A 2-20).
- P, or 'Present'. If the bit is set, the page is actually in physical memory at the moment. For example, when a page is swapped out, it is not in physical memory and therefore not 'Present'. If a page is called, but not present, a page fault will occur, and the OS should handle it. (See below.)
The remaining bits 9 through 11 (if PS=0, also bits 6 & 8) are not used by the processor, and are free for the OS to store some of its own accounting information. In addition, when P is not set, the processor ignores the rest of the entry and you can use all remaining 31 bits for extra information, like recording where the page has ended up in swap space.
Setting the PS bit makes the page directory entry point directly to a 4-MiB page. There is no paging table involved in the address translation. Note: With 4-MiB pages, whether or not bits 21 through 13 are reserved depends on PSE being enabled and how many PSE bits are supported by the processor. CPUID should be used to determine this. Thus, the physical address must also be 4-MiB-aligned. Physical addresses above 4 GiB can only be mapped using 4 MiB PDEs.
Page Table
In each page table, as it is, there are also 1024 entries. These are called page table entries, and are very similar to page directory entries.
The first item, is once again, a 4-KiB aligned physical address. Unlike previously, however, the address is not that of a page table, but instead a 4 KiB block of physical memory that is then mapped to that location in the page table and directory. Note that the PAT bit is bit 7 instead of bit 12 as in the 4 MiB PDE.
Example
Say the kernel is loaded to 0x100000. However, it needed to be remapped to 0xC0000000. After loading the kernel, it'll initiate paging, and set up the appropriate tables. (See Higher Half Kernel) After Identity Paging the first megabyte, it'll need to create a second table (ie. at entry #768 in the paging directory.) to map 0x100000 to 0xC0000000. The code may be like:
mov eax, 0x0
mov ebx, 0x100000
.fill_table:
mov ecx, ebx
or ecx, 3
mov [table_768+eax*4], ecx
add ebx, 4096
inc eax
cmp eax, 1024
je .end
jmp .fill_table
.end:
Enabling
Enabling paging is actually very simple. All that is needed is to load CR3 with the address of the page directory and to set the paging (PG) and protection (PE) bits of CR0. Note: setting the paging flag when the protection flag is clear causes a general-protection exception.
mov eax, page_directory
mov cr3, eax
mov eax, cr0
or eax, 0x80000001
mov cr0, eax
If you want to set pages as read-only for both userspace and supervisor, replace 0x80000001 above with 0x80010001, which also sets the WP bit.
To enable PSE (4 MiB pages) the following code is required.
mov eax, cr4
or eax, 0x00000010
mov cr4, eax
Physical Address Extension
All Intel processors since Pentium Pro (with exception of the Pentium M at 400 Mhz) and all AMD since the Athlon series implement the Physical Address Extension (PAE). This feature allows you to access up to 64 GiB (2^36) of RAM. You can check for this feature using CPUID. Once checked, you can activate this feature by setting bit 5 in CR4. Once active, the CR3 register points to a table of 4 64-bit entries, each one pointing to a page directory made of 4096 bytes (like in normal paging), divided into 512 64-bit entries, each pointing to a 4096 byte page table, divided into 512 64bit page entries.
If paging is to be used, then PAE must be enabled before entering long mode. Failure to do so will trigger a general protection fault.
Usage
Due to the simplicity in the design of paging, it has many uses.
Virtual Address Spaces
In a paged system, each process may execute in its own 4 GiB area of memory, without any chance of effecting any other process's memory, or the kernel's.
Virtual Memory
Because paging allows for the dynamic handling of unallocated page tables, an OS can swap entire pages, not in current use, to the hard drive where they can wait until they are called. In the mean time, however, the physical memory that they were using can be used elsewhere. In this way, the OS can manipulate the system so that programs actually seem to have more RAM than there actually is.
More...
Manipulation
The CR3 value, that is, the value containing the address of the page directory, is in physical form. Once, then, the computer is in paging mode, only recognizing those virtual addresses mapped into the paging tables, how can the tables be edited and dynamically changed?
Many prefer to map the last PDE to itself. The page directory will look like a page table to the system. To get the physical address of any virtual address in the range 0x00000000-0xFFFFF000 is then just a matter of:
void *get_physaddr(void *virtualaddr) {
unsigned long pdindex = (unsigned long)virtualaddr >> 22;
unsigned long ptindex = (unsigned long)virtualaddr >> 12 & 0x03FF;
unsigned long *pd = (unsigned long *)0xFFFFF000;
// Here you need to check whether the PD entry is present.
unsigned long *pt = ((unsigned long *)0xFFC00000) + (0x400 * pdindex);
// Here you need to check whether the PT entry is present.
return (void *)((pt[ptindex] & ~0xFFF) + ((unsigned long)virtualaddr & 0xFFF));
}
To map a virtual address to a physical address can be done as follows:
void map_page(void *physaddr, void *virtualaddr, unsigned int flags) {
// Make sure that both addresses are page-aligned.
unsigned long pdindex = (unsigned long)virtualaddr >> 22;
unsigned long ptindex = (unsigned long)virtualaddr >> 12 & 0x03FF;
unsigned long *pd = (unsigned long *)0xFFFFF000;
// Here you need to check whether the PD entry is present.
// When it is not present, you need to create a new empty PT and
// adjust the PDE accordingly.
unsigned long *pt = ((unsigned long *)0xFFC00000) + (0x400 * pdindex);
// Here you need to check whether the PT entry is present.
// When it is, then there is already a mapping present. What do you do now?
pt[ptindex] = ((unsigned long)physaddr) | (flags & 0xFFF) | 0x01; // Present
// Now you need to flush the entry in the TLB
// or you might not notice the change.
}
Unmapping an entry is essentially the same as above, but instead of assigning the pt[ptindex] a value, you set it to 0x00000000 (i.e. not present). When the entire page table is empty, you may want to remove it and mark the page directory entry 'not present'. Of course you don't need the 'flags' or 'physaddr' for unmapping.
Page Faults
A page fault exception is caused when a process is seeking to access an area of virtual memory that is not mapped to any physical memory, when a write is attempted on a read-only page, when accessing a PTE or PDE with the reserved bit or when permissions are inadequate.
Handling
The CPU pushes an error code on the stack before firing a page fault exception. The error code must be analyzed by the exception handler to determine how to handle the exception. The following bits are the only ones used, all others are reserved.
Bit 0 (P) is the Present flag. Bit 1 (R/W) is the Read/Write flag. Bit 2 (U/S) is the User/Supervisor flag. Bit 3 (RSVD) indicates whether a reserved bit was set in some page-structure entry Bit 4 (I/D) is the Instruction/Data flag (1=instruction fetch, 0=data access) Bit 5 (PK) indicates a protection-key violation Bit 6 (SS) indicates a shadow-stack access fault Bit 15 (SGX) indicates an SGX violaton
The combination of these flags specify the details of the page fault and indicate what action to take:
US RW P - Description 0 0 0 - Supervisory process tried to read a non-present page entry 0 0 1 - Supervisory process tried to read a page and caused a protection fault 0 1 0 - Supervisory process tried to write to a non-present page entry 0 1 1 - Supervisory process tried to write a page and caused a protection fault 1 0 0 - User process tried to read a non-present page entry 1 0 1 - User process tried to read a page and caused a protection fault 1 1 0 - User process tried to write to a non-present page entry 1 1 1 - User process tried to write a page and caused a protection fault
When the CPU fires a page-not-present exception the CR2 register is populated with the linear address that caused the exception. The upper 10 bits specify the page directory entry (PDE) and the middle 10 bits specify the page table entry (PTE). First check the PDE and see if it's present bit is set, if not setup a page table and point the PDE to the base address of the page table, set the present bit and iretd. If the PDE is present then the present bit of the PTE will be cleared. You'll need to map some physical memory to the page table, set the present bit and then iretd to continue processing.
INVLPG
INVLPG is an instruction available since the i486 that invalidates a single page in the TLB. Intel notes that this instruction may be implemented differently on future processes, but that this alternate behavior must be explicitly enabled. INVLPG modifies no flags.
NASM example:
invlpg [0]
Inline assembly for GCC (from Linux kernel source):
static inline void __native_flush_tlb_single(unsigned long addr) {
asm volatile("invlpg (%0)" ::"r" (addr) : "memory");
}
This only invalidates the page on the current processor. If you're using SMP, you'll need to send an IPI to the other processors so that they can also invalidate the page (this is called a TLB shootdown; it's very slow), making sure to avoid any nasty race conditions. You may only want to do this when removing a mapping, and just make your page fault handler invalidate a page if it you didn't invalidate a mapping addition on that processor by looking through the page directory, again avoiding race conditions.
When you modify an entry in the page directory, rather than just a page table, you'll need to invalidate each page in the table. Alternatively, you could reload CR3 which will invalidates the whole directory, but this may be slower. (TODO time this)
Paging Tricks
The processor always fires a page fault exception when the present bit is cleared in the PDE or PTE regardless of the address. This means the contents of the PTE or PDE can be used to indicate a location of the page saved on mass storage and to quickly load it. When a page gets swapped to disk, use these entries to identify the location in the paging file where they can be quickly loaded from then set the present bit to 0.