Expand description
§Four-Level Page Table of x86_64
One of the main roles of an operating system is resource abstraction. An important resource in a computer system is memory. Each process operates in its own memory space, which must be isolated from other processes. For instance, your web browser should not have access to the memory used by your music player. To ensure such isolation, hardware introduces a memory protection mechanism that isolates the memory between processes.
§Virtual Memory
The concept of virtual memory abstracts memory addresses from the underlying physical storage device. Instead of directly accessing the physical memory, addresses are translated through the Memory Management Unit (MMU). To distinguish between these two types of addresses:
- A virtual address is used by programs before translation.
- A physical address refers to the actual location in memory after translation.
A key distinction between virtual and physical addresses is that physical addresses are unique and always refer to the same memory location. In contrast, virtual addresses can be mapped to the same physical address or different physical addresses at different times.
§Paging
Paging is a memory management technique that divides both physical and
virtual memory into small, fixed-size chunks called pages. Typically, a
page is 4096 bytes in size. The mapping of physical and virtual memory is
managed via a page table, with each entry representing a page. The
active page table is typically managed through a special CPU register (e.g.,
cr3 in x86_64).
For every memory access, the CPU translates the virtual address to a physical address using the page table. Since checking the page table for every conversion would be inefficient, the CPU stores the results in a cache called the Translation Lookaside Buffer (TLB).
The TLB is a CPU cache that stores recent translations of virtual memory addresses to physical memory. The TLB is not updated automatically when the page table is modified, so the kernel must explicitly invalidate the TLB entries after a page table update. If you invalidate the entry, the kernel may be work with a stale memory.
§Paging in x86_64
x86_64 uses 4096-byte pages and employs a 4-level page table. Each table is 4096 bytes in size, which is the same size as the page, and each entry in the table is 8 bytes. This structure allows for a 48-bit physical address space to be covered by the page table.
The virtual address in x86_64 can be broken down into the following levels:
63 48 47 39 38 30 29 21 20 12 11 0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend | Page-Map | Page-Directory | Page-directory | Page-Table | Page |
| | Level-4 Offset | Pointer | Offset | Offset | Offset |
+-------------+----------------+----------------+----------------+-------------+------------+
| | | | | |
+------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
Virtual Address- The sign extend portion represents the higher bits, ensuring proper sign extension for the full address.
- The Page Map Level 4 (PM4) identifies the highest-level page directory.
- The subsequent levels (Page Directory, Page Table) map smaller chunks of virtual memory to physical memory.
- The page offset specifies the position within the 4096-byte page.
A page must be page-aligned, meaning the virtual address must be divisible by the page size (4096 bytes). The last 12 bits of the 64-bit virtual address represent the page offset, while the upper bits are used as indices for the page table.
The page table also defines various attributes for each page, such as access permissions (e.g., read/write/user). Note that the attributes from all levels are ANDed together. This means attributes of the intermediate level must contain all possible attributes.
In x86_64, the invlpg instruction invalidates a specific TLB entry based
on the given virtual address. Note that the entire TLB is also flushed when
the cr3 register is reloaded.
§Managing PageTable in KeOS
You need to implement x86_64’s 4-level page table scheme. The core
abstraction about page table is PageTable. With this abstraction, you
will implement page table walking, mapping, and unmapping. In addition to
mapping and unmapping pages, the page table must be clear the entries when
it deallocates an associated memory. This traverses the entire 4-level page
table, unmapping each mapped virtual address and deallocating
the corresponding physical pages. After calling this method, all page table
levels—including the Page Directory Pointer Table (PDP), Page Directory
(PD), and Page Table (PT)—will be deallocated, leaving only the root Page
Map Level 4 (PML4).
This PageTable represents a page table of a user process. Each process
has its own set of user pages, which reside below the kernel base address,
where pml4 index is lower than PageTableRoot::KBASE. The set of
kernel pages, however, is global and remains fixed in the virtual
address space, regardless of the running process or thread. These pages are
shared between multiple page tables, meaning that they MUST NOT
deallocated in any cases.
KeOS already provides several abstractions to work with page table.
- The virtual and physical addresses:
PaandVa. - The Memory Permission:
Permission. - Each table entry:
Pml4e,Pdpe,Pde, andPte. - Flag of each table entry:
Pml4eFlags,PdpeFlags,PdeFlags, andPteFlags. - Invalidate a TLB entry:
StaleTLBEntry::invalidate.
§Implementation Requirements
You need to implement the followings:
PtIndices::from_vaPageTable::do_mapPageTable::unmapPageTable::walkPageTable::walk_mutPageTable::clear
Make sure to implement the necessary functions for TLB invalidation, and ensure the correct handling of memory protection and access permissions for pages.
By the end of this part, you will have built an essential component for
memory management, ensuring that processes can access their memory securely
and efficiently through the page table.
When you finish implementing all tasks, move on to the next section.