Paging

The paging system is responsible for the management, construction, updating and destruction of page tables. It provides the functionality to amend mappings in kernel and user page tables to reflect mappings held in the kernel’s virtual address space structures.

The paging system is also responsible for the page fault handler, in which these mappings will typically be applied to the system’s page tables.

Management, allocation and de-allocation of physical page frames is covered in the next section.

It should be noted that the paging subsystem is not directly used to configure the virtual address space of a task. The data structures and functions used are described in the virtual memory section.

Page Tables

As the structure of page tables is an architecture-specific topic, architecture implementations are expected to provide a set of mandatory functions and definitions that can be used by the kernel to manipulate page tables. These definitions will be called from architecture-independent code, allowing the logical flow of page table operations to remain the same across all platforms.

The majority of these implementations are likely to reside in <arch/ptable.h>.

Currently, four data structures are defined to represent page tables on any architecture. These data structures must be defined on all architectures, but are defined in architecture-specific code. They are:

• struct pde: Represents a top-level page directory entry, that will describe and point to a page table.
• struct pte: Represents a page table entry, mapping and describing a single page of memory.
• struct pgt: Contains all top-level page directory (struct pde) entries, and can be considered the reference to a whole page table.
• struct pgd: Contains all page table entries (struct pte) for a single page directory (struct pde).

A set of macros and functions are defined by each architecture, that can be used to manipulate these structures on their particular platforms. They include:

• MAKE_PDE(addr, flags): Constructs a valid page directory entry for a given address.
• MAKE_PTE(addr, flags): Constructs a valid page table entry for a given address.
• GET_PDE(pgd, va): Retrieves the page directory entry within a page global directory.
• GET_PTE(pgt, va): Retrieves the page table entry within a page table for a given address.
• PDE_TO_PGT(pde): Returns the page table described by a page directory entry.

These definitions and macros are then used within architecture-independent code, to ensure that logic such as page table manipulation can be the same on all systems, with architecture-specific operations performed as needed. Functions to manipulate page tables on all systems can be found in kernel/mm/ptable.c.

Kernel Page Table Initialisation

The kernel’s page table is initialised by architecture-specific code in arch/<arch>/kernel/paging.c, via the paging_setup_kernel_pgd() function. This function makes use of the data structures and macros described above to construct the kernel’s initial page table, that will be shared by all kernel tasks.

This function sets up identity mapping for the kernel, mapping approximately ~768MB of low physical memory to the highest 1GB of virtual memory (starting at 0xC0000000 on 32-bit platforms). This enables the kernel’s higher-half model.

The function also sets up space for kmap(), which can provide temporary virtual mappings of high memory pages that are not normally mapped into kernel memory. These high memory pages are sections of memory that are not by default covered in the kernel’s ~1GB of mapped memory.

kmap() mappings are always constructed using 4KB pages, allowing for more granularity, while ordinary kernel mappings are mapped with 4MB or large pages if possible. Each struct pte constructed for kmap() memory is also cleared during this stage.

Page Fault Handling

The system’s page fault handler is also located in architecture-specific code, in the function paging_handle_page_fault(). This function is responsible for handling any page fault encountered. Currently, this function retrieves the current running task and fault address, which is then passed to the virtual memory subsystem (vm_space_page_fault()) to assess whether the faulted page is mapped in the current task’s virtual address space.

As Rotary makes use of demand paging, the page tables of a task are not immediately populated with entries for each of its virtual address mappings. Instead, upon a page fault the kernel will consult the current task’s list of virtual address mappings, and identify whether the faulted address lies within any of them. If the faulted address belongs to the task’s virtual memory space, the kernel allocates a physical page, updates the page table, and resumes execution.

If the fault address is not found within the current task’s virtual address mappings, the kernel page fault handler (paging_handle_page_fault()) is responsible for handling the failure.

More detailed information on how Rotary represents the virtual address space of tasks can be found in the virtual memory section.

This approach provides an additional level of efficiency, as memory is only allocated to back pages that are provably in use by the task.

Architecture-specific Configuration

The following defines, macros and configuration options are used by an architecture implementation to specify characteristics of the architecture, such as page size. These will be used throughout architecture-independent code by the kernel.

Definitions

• PAGE_SIZE: Defines the size of a page on the architecture (e.g. 4096 bytes on x86).
• KERNEL_START_VIRT: The virtual address at which kernel memory begins (e.g. 0xC0000000 on x86).
• KMAP_START_VIRT: The virtual address at which kmap() memory begins.

Macros

• VIR_TO_PHY(addr): Converts a virtual address to a physical address.
• PHY_TO_VIR(addr): Converts a physical address to a virtual address.

Relevant Source

• kernel/mm/ptable.c - Architecture-independent functions to manipulate page tables with consist logic across platforms using architecture-specific functions.
• arch/<arch>/kernel/paging.c - Architecture-specific paging system initialisation and handling.
• include/rotary/mm/ptable.h - Architecture-independent definitions (e.g. PTC_SHARE) and function prototypes (e.g. ptable_map())
• arch/<arch>/include/arch/ptable.h - Architecture-specific definitions such as struct pde, and macros (e.g. MAKE_PDE)

Example: Creating and Updating a New Page Table

In the following example, a new page table is created, and a simple one-page mapping is created within it.

struct pgd * new_pgd = ptable_pgd_new();
ptable_map(new_pgd, 0xC0000, 0x00000, VM_MAP_WRITE);