Background

• Read the fucking source code! –By Lu Xun

• A picture is worth a thousand words. –By Gorky

Note:

1. Kernel Version: 4.14

2. ARM64 Processor, Cortex-A53, Dual-core

3. Tools Used: Source Insight 3.5, Visio

1. Introduction

To understand Linux page table mapping well, it is necessary to be familiar with the MMU mechanism, so these two modules are introduced together. The main reference document regarding ARMv8 MMU is: 《ARM Cortex-A Series Programmer’s Guide for ARMv8-A》.

2. ARMv8 MMU

2.1 Overview of MMU/TLB/Cache

1. MMU: Its job is to perform the translation from virtual addresses to physical addresses, allowing multiple programs in the system to run in their own independent virtual address space without affecting each other. Programs can be completely unaware of the underlying physical memory, which can be non-contiguous, but this does not prevent mapping to a contiguous virtual address space.

2. TLB: The process of the MMU working is essentially the process of querying the page table. When the page table is stored in memory, the query overhead is too high, so a small area of faster access is specially allocated for storing translation entries to improve lookup efficiency. When the content of the page table changes, the TLB needs to be cleared to prevent address mapping errors.

3. Cache: A caching mechanism between the processor and memory to improve access speed. On ARMv8, there are multiple levels of cache, where L1 Cache is divided into Instruction Cache and Data Cache, supporting virtual address addressing internally in the CPU Core; L2 Cache has a larger capacity, storing both instructions and data, shared among multiple CPU Cores, which together form a Cluster.

The light yellow part in the diagram below describes an address translation process.

Since the above diagram does not illustrate the relationship between L1 and L2 Cache and MMU, let’s take another look at a diagram:

So how is access actually performed? Here’s another diagram:

2.2 Translation from Virtual Address to Physical Address

The mapping from virtual addresses to physical addresses is implemented through a table lookup mechanism. In ARMv8, the base address of the page table for Kernel Space is stored in the TTBR1_EL1 register, while the base address for User Space is stored in the TTBR0_EL0 register. The high bits of the kernel address space are all 1s, (0xFFFF0000_00000000 ~ 0xFFFFFFFF_FFFFFFFF), while the high bits of the user address space are all 0s, (0x00000000_00000000 ~ 0x0000FFFF_FFFFFFFF).

In ARMv8:

• Virtual Address Support: In 64-bit virtual addressing, not all bits are used. Aside from the high 16 bits used to distinguish between kernel space and user space, the effective bit configurations can be: 36, 39, 42, 47. This determines the size of the address space in the Linux kernel. For instance, in the kernel I am using, the effective bit configuration is CONFIG_ARM64_VA_BITS=39, resulting in a user space address range of 0x00000000_00000000 ~ 0x0000007f_ffffffff, with a size of 512G, and a kernel space address range of 0xffffff80_00000000 ~ 0xffffffff_ffffffff, also with a size of 512G.

• Page Size Support: Supports three page sizes: 4KB, 16KB, 64KB.

• Page Table Support: Supports at least two levels of page tables, and at most four levels, Level 0 ~ Level 3.

Combining effective virtual address bits, page size, and the number of levels in the page table, different page table mapping methods can be formed. The kernel configuration I am using is: 39 effective bits, 4KB page size, and a 3-level page table, so I will introduce it based on this combination. In the ARMv8 manual, I found the following diagram, which describes the entire translation process, simply perfect:

1. The virtual address [63:39] is used to distinguish between kernel space and user space, thus selecting different TTBRn registers to obtain the Level 1 page table base address;

2. The virtual address [38:30] is used as the index in the Level 1 page table to find the corresponding descriptor address and obtain the descriptor content, which is then used to obtain the Level 2 page table base address;

3. The virtual address [29:21] serves as the index in the Level 2 page table to find the corresponding descriptor address and obtain the descriptor content, which is then used to obtain the Level 3 page table base address;

4. The virtual address [20:12] serves as the index in the Level 3 page table to find the corresponding descriptor address and obtain the descriptor content, which is used to obtain the high 36 bits of the physical address, aligned to 4K;

5. The virtual address [11:0] contains the offset of the physical address, which, combined with the obtained high bits of the physical address, results in the final physical address.

At this point, it’s not over yet; it’s time to take a look at the Table Descriptor, which is the content stored in the page table, with the following four types: the type is determined by the lower two bits, where the Table Descriptor in Level 0 can only output the address of the Level 1 page table, and the Table Descriptor in Level 3 can only output block addresses.

Do you see the attributes in the diagram? These can be used for memory permission control, memory ordering, cache policy operations, etc.

In ARMv8, the registers related to the page table include: TCR_EL1, TTBRx_EL1.

3. Linux Page Table Mapping

3.1 Basic Operations of Linux Page Table

Students who have read Understanding the Linux Kernel should be very familiar with the image below, which illustrates Linux’s paging mode (the example uses X86, where the page table base address is specified by the CR3 register):

The Linux kernel supports a model with four levels of page tables, suitable for both 32-bit and 64-bit systems.

So how does ARMv8 integrate with the Linux kernel? Taking my actual settings as an example (39 effective bits, 4KB page size, 3-level page table), as shown in the diagram below:

Basically, all operations related to page tables in the kernel revolve around the diagram above. It seems inappropriate to stray from the code, so let’s analyze some fucking source code, mainly discussing various page table-related APIs.

Code paths:

arch/arm64/include/asm/pgtable-types.h: Defines pgd_t, pud_t, pmd_t, pte_t and other types;

arch/arm64/include/asm/pgtable-prot.h: Sets permissions in the entries of the page table;

arch/arm64/include/asm/pgtable-hwdef.h: Mainly includes the divisions of PGD/PMD/PUD, which relate to the valid bits of the virtual address and page size, and also includes definitions of the hardware page table, settings in the TCR register, etc.;

arch/arm64/include/asm/pgtable.h: Related to page table settings;

In these codes, you can see:

• When CONFIG_PGTABLE_LEVELS=4: pgd-->pud-->pmd-->pte;

• When CONFIG_PGTABLE_LEVELS=3: No PUD page table: pgd(pud)-->pmd-->pte;

• When CONFIG_PGTABLE_LEVELS=2: No PUD and PMD page tables: pgd(pud, pmd)-->pte

Common Macro Definitions:

Page Table Processing

/* Describes the page table entries in each level of the page table */typedef struct { pteval_t pte; } pte_t;typedef struct { pmdval_t pmd; } pmd_t;typedef struct { pudval_t pud; } pud_t;typedef struct { pgdval_t pgd; } pgd_t;/* Convert page table entry type to unsigned type */#define pte_val(x) ((x).pte)#define pmd_val(x) ((x).pmd)#define pud_val(x) ((x).pud)#define pgd_val(x) ((x).pgd)/* Convert unsigned type to page table entry type */#define __pte(x) ((pte_t) { (x) })#define __pmd(x) ((pmd_t) { (x) })#define __pud(x) ((pud_t) { (x) })#define __pgd(x) ((pgd_t) { (x) })/* Get the index value of the page table entry */#define pgd_index(addr) (((addr) >> PGDIR_SHIFT) & (PTRS_PER_PGD - 1))#define pud_index(addr) (((addr) >> PUD_SHIFT) & (PTRS_PER_PUD - 1))#define pmd_index(addr) (((addr) >> PMD_SHIFT) & (PTRS_PER_PMD - 1))#define pte_index(addr) (((addr) >> PAGE_SHIFT) & (PTRS_PER_PTE - 1))/* Get the offset value of the entry in the page table */#define pgd_offset(mm, addr) (pgd_offset_raw((mm)->pgd, (addr)))#define pgd_offset_k(addr) pgd_offset(&init_mm, addr)#define pud_offset_phys(dir, addr) (pgd_page_paddr(*(dir)) + pud_index(addr) * sizeof(pud_t))#define pud_offset(dir, addr) ((pud_t *)__va(pud_offset_phys((dir), (addr))))#define pmd_offset_phys(dir, addr) (pud_page_paddr(*(dir)) + pmd_index(addr) * sizeof(pmd_t))#define pmd_offset(dir, addr) ((pmd_t *)__va(pmd_offset_phys((dir), (addr))))#define pte_offset_phys(dir, addr) (pmd_page_paddr(READ_ONCE(*(dir))) + pte_index(addr) * sizeof(pte_t))#define pte_offset_kernel(dir, addr) ((pte_t *)__va(pte_offset_phys((dir), (addr))))

3.2 Page Table Mapping in head.S

3.2.1 Temporary Page Tables idmap_pg_dir and swapper_pg_dir

It’s time for an instance analysis to see the page table creation process. Code path: arch/arm64/kernel/head.S.

During the kernel startup process, before the actual physical memory is added to the system and the page table is initialized, two temporary global page tables need to be established to ensure the system runs normally: idmap_pg_dir and swapper_pg_dir: The definitions of these two global page tables are in arch/arm64/kernel/vmlinux.lds.S, placed after the BSS section:

. = ALIGN(PAGE_SIZE); idmap_pg_dir = .; . += IDMAP_DIR_SIZE; swapper_pg_dir = .; . += SWAPPER_DIR_SIZE;

/* Defines several contiguous pages, storing PGD, PMD, PTE, etc., continuously together, this is also filled in head.S */#define SWAPPER_DIR_SIZE (SWAPPER_PGTABLE_LEVELS * PAGE_SIZE)#define IDMAP_DIR_SIZE (IDMAP_PGTABLE_LEVELS * PAGE_SIZE)

• idmap_pg_dir: As the name suggests, identify map, meaning that the physical address and virtual address are equal. Why is such a mapping necessary? We all know that before the MMU is turned on, the CPU accesses physical addresses, and when the MMU is turned on, it accesses virtual addresses. This page table mapping is to map the physical addresses of the code before the MMU is turned on to prevent loss of access to the page table after enabling the MMU. This can be checked in the System.map file:

• swapper_pg_dir: After compiling the Linux kernel, the kernel image needs to be mapped, including various sections like text, data.

3.2.2 Page Table Creation

In head.S, there are three macros related to creating page tables:

1. create_pgd_entry

/* * Macro to populate the PGD (and possibly PUD) for the corresponding * block entry in the next level (tbl) for the given virtual address. * * Preserves: tbl, next, virt * Corrupts: tmp1, tmp2 */ .macro create_pgd_entry, tbl, virt, tmp1, tmp2 create_table_entry 	bl, ort, PGDIR_SHIFT, PTRS_PER_PGD, 	mp1, 	mp2 #if SWAPPER_PGTABLE_LEVELS > 3 create_table_entry 	bl, ort, PUD_SHIFT, PTRS_PER_PUD, 	mp1, 	mp2 #endif #if SWAPPER_PGTABLE_LEVELS > 2 create_table_entry 	bl, ort, SWAPPER_TABLE_SHIFT, PTRS_PER_PTE, 	mp1, 	mp2 #endif .endm

The above function mainly calls create_table_entry. Since SWAPPER_PGTABLES is configured to 3, it effectively creates pgd and pmd two levels of page tables. It is important to note that after executing the create_table_entry function, the tbl parameter is automatically incremented by PAGE_SIZE, meaning that the pgd and pmd two levels of page tables are physically contiguous.

1. create_block_map

/* * Macro to populate block entries in the page table for the start..end * virtual range (inclusive). * * Preserves: tbl, flags * Corrupts: phys, start, end, pstate */ .macro create_block_map, tbl, flags, phys, start, end lsr phys, phys, #SWAPPER_BLOCK_SHIFT lsr start, start, #SWAPPER_BLOCK_SHIFT and start, start, #PTRS_PER_PTE - 1 // table index orr phys, flags, phys, lsl #SWAPPER_BLOCK_SHIFT // table entry lsr end, end, #SWAPPER_BLOCK_SHIFT and end, end, #PTRS_PER_PTE - 1 // table end index 9999: str phys, [	bl, start, lsl #3] // store the entry add start, start, #1 // next entry add phys, phys, #SWAPPER_BLOCK_SIZE // next block cmp start, end b.ls 9999b .endm

The above function mainly fills in pte entry in the block, creating the mapping from virtual addresses to physical addresses, in the range: start ~ end.

1. create_table_entry

/* * Macro to create a table entry to the next page. * * tbl: page table address * virt: virtual address * shift: #imm page table shift * ptrs: #imm pointers per table page * * Preserves: virt * Corrupts: tmp1, tmp2 * Returns: tbl -> next level table page address */ .macro create_table_entry, tbl, virt, shift, ptrs, tmp1, tmp2 lsr 	mp1, ort, #shift and 	mp1, 	mp1, #ptrs - 1 // table index add 	mp2, 	bl, #PAGE_SIZE orr 	mp2, 	mp2, #PMD_TYPE_TABLE // address of next table and entry type str 	mp2, [	bl, 	mp1, lsl #3] add 	bl, 	bl, #PAGE_SIZE // next level table page .endm

The above function creates a page table entry and returns the address of the next level page table.

The three isolated functions above are not very intuitive, so here’s a diagram:

Overall, the page table creation process is relatively easy to understand. Mastering the multi-level page table and the bit fields occupied by the index of each level of the page table, as well as familiarizing oneself with the entry formats in each level of the page table, will make understanding much smoother.

Attention to detail is crucial; one should avoid being blinded by a single leaf and losing sight of the mountain. That’s a wrap!