Page tables in Linux
Linux employs virtual addresses instead of physical addresses to isolate each process’s address space and provide greater security. But ultimately accessing the physical memory will require that the memory controller be provided with a physical address to access the physical memory.
In order to achieve this, Linux stores a table of mappings containing virtual to physical memory mappings of each process. But this is not a simple one-to-one mapping as this would require a lot of space in the physical memory. Instead Linux uses a 3 page table approach. The virtual address bits are seperated into four distinct fields each of which helps in naviagting the page table structures The 3 page tables are
Recently Linux has been updated to handle another page table between PGD and PMD called Page Upper Direcory (PUD). Note that page table implementation is architecture specific. But for the case of ARM 32 bit, there are only two page tables used, PGD and PTE as we will shortly see.
Walking the Table
The following diagram helps explain the page table layout better.
PGD is an array of pgd_t members, PMD is an array of pmd_t members and PTE is an array of pte_t members. Each process is represented by a task_struct structure which contains a pointer to mm_struct , another structure containing information on the virtual memory areas of the process. Within mm_struct a pointer to its own Page Global Directory exists. Before reading the page tables, we acquire the page table lock member of the mm_struct using spinlock API. The kernel API offers methods required to find the offset within each table. The offset within the PGD table is obtained by right shifting the bits of the virtual address by PGDIR_SHIFT and adding the value to the PGD pointer.
pgd_offset(mm, addr) *** mm is the `mm_struct` and addr is the virtual address From the previous step we have the PUD entry. To find the offset within PUD the pud_offset(pgd_offset_entry, addr) is used, but for ARMv7 there is no PUD table and this function simply returns the pgd offset entry from the previous step.
Next we have PMD table and the pmd_offset(pud_offset_entry, addr) provides the offset entry but as I observed that this value was simply the return of the pud_offset_entry which is in turn the pgd_offset_entry.
Finally the PTE table provides the pte_t entry containing the address to the page struct. The function pte_offset_map(pmd_offset_entry, addr) is used to handle this. Once we have located the page containing our address, we have to find the offset of the location within the page. Each page in ARMv7 is configured to be of 4096 bytes or 2^12. We find the offset within the page by using the lowermost 12 bits.
Experiment
I wanted to experiment with page tables and wrote a kernel module to perform page table traversal. It works as follows
- Provide the process ID (PID) and address of a variable to the kernel module’s device descriptor. This can be done using the echo command.
- The kernel module obtains the task_struct using the PID.
- Obtain the mm_struct and the pgd pointer. Traverse the page tables using the page table offset APIs.
- Find the page struct from the PTE entry
- Perform temporary mapping of the page using kmap_atomic and find offset within page from the virtual address.
- Read the value at the address and print the contents.
Test code
I used the following simple code and will try to read the contents of variable a
Running the program will print the address of a
$ ./test_code & [1] 614 0x7e9e6c24 The kernel module creates a char device interface to read the user arguments. Usage is as follows
$ echo "614 7e9e6c24 " > /dev/test_driver [ 122.536785] test driver device opened [ 122.537051] test driver device write [ 122.537227] user writes : 614 7e9e6c24 [ 122.537227] [ 122.537364] user 1st write 614 [ 122.537384] user 2nd write 7e9e6c24 [ 122.537462] task_struct pid : 614 [ 122.537532] virt addr :2124311588 7e9e6c24 [ 122.537621] pgd pointer: c8058000 pgd entry:c8059fa0 [ 122.537745] pud pointer: c8059fa0 [ 122.537812] pmd pointer: c8059fa0 [ 122.537880] pte pointer: c8269798 [ 122.537948] page address 574a1000 physical address 574a1c24 [ 122.537974] value at address : 8055 [ 122.538079] test driver device closed / released I have uploaded the driver code here.
What are page tables in Linux?
Page tables work by splitting the virtual address into chunks. Each chunk is used as an index into a table. The table points to either another table or the associated physical page. In Linux, the page tables consist of three levels. The multiple levels allow a sparsely populated address space, even on 64-bit machines.
What does a page table entry contain?
A page table entry contains information about an individual page in a process’s logical address space. It typically has a size of 4 bytes (32 bits). It contains two kinds of information: Bits to represent the frame number.
How pages are addressed in Linux?
Linux on Alpha AXP systems uses 8 Kbyte pages and on Intel x86 systems it uses 4 Kbyte pages. Each of these pages is given a unique number; the page frame number (PFN). In this paged model, a virtual address is composed of two parts; an offset and a virtual page frame number. To do this the processor uses page tables.
Where are page table entries stored?
physical memory
Typically, page tables are said to be stored in the kernel-owned physical memory. However page tables can get awfully big since each process have their own page tables (unless the OS uses inverted paging scheme).
Is page A table process?
Each process has its own page table in the kernel. Having a separate page table for each process is necessary for process isolation as they should not be allowed to stomp on each others memory. Since each process has a different page table, there is not one pmap that will work for every process.
What is difference between page and frame?
A page (or memory page, or virtual page, or logical page) is a fixed-length contiguous block of virtual memory. A frame (or memory frame, or physical page, or page frame) is a fixed-length block of RAM (ie. physical memory, it exists – as in “physical”.
How many entries are in a page table?
The page table needs one entry per page. Assuming a 4GB (2^32 byte) virtual and physical address space and a page size of 4kB (2^12 bytes), we see that the the 2^32 byte address space must be split into 2^20 pages. This means the page table must have 2^20 entries.
Why paging is used in OS?
Paging is used for faster access to data. When a program needs a page, it is available in the main memory as the OS copies a certain number of pages from your storage device to main memory. Paging allows the physical address space of a process to be noncontiguous.
How many frames are needed for each page?
Here, the main memory will be divided into the collection of 16 frames of 1 KB each. There are 4 separate processes in the system that is A1, A2, A3, and A4 of 4 KB each. Here, all the processes are divided into pages of 1 KB each so that operating system can store one page in one frame.
Is page table in physical memory?
To map virtual memory addresses to physical memory addresses, page tables are used. A page table consists of numerous page table entries (PTE). One memory page in a PTE contains data structures consisting of different sizes of ‘words’.
What is the page table mainly for?
A page table is the data structure used by a virtual memory system in a computer operating system to store the mapping between virtual addresses and physical addresses.
Can a process access its own page table?
Yes every process has its own pagetables. They might be shared with the parent process(copy on write) or with other processes(shared memory). But in general every process has its own. Yes, unless you use an inverted page table see this answer.