Page Tables

역사, 주소 mapping과 PFN

Paged virtual memory는 virtual memory 개념과 함께 1962년 Ferranti Atlas Computer에서 발명되었습니다. Atlas는 paged virtual memory를 탑재한 최초의 computer였습니다. 이 기능은 이후 computer로 이어져 시간이 지나면서 모든 Unix 계열 system의 사실상 표준이 되었습니다. 1985년에는 Linux 1.0 개발 대상 CPU인 Intel 80386에도 포함되었습니다.

Page table은 CPU가 보는 virtual address를 external memory bus가 보는 physical address로 mapping합니다. Linux는 현재 높이 5단계인 hierarchy로 page table을 정의하며, 지원 architecture별 code가 이를 hardware 제약에 맞게 mapping합니다.

Virtual address에 해당하는 physical address는 흔히 underlying physical page frame으로 표현합니다. `page frame number`, 즉 `pfn`은 external memory bus가 보는 page의 physical address를 `PAGE_SIZE`로 나눈 값입니다. Physical address 0은 `pfn 0`이고, 가장 큰 PFN은 CPU external address bus가 지정할 수 있는 physical memory의 마지막 page입니다.

Page granularity가 4KB이고 address range가 32bit이면 `pfn 0`은 `0x00000000`, `pfn 1`은 `0x00001000`, `pfn 2`는 `0x00002000`이며 마지막 `pfn 0xfffff`는 `0xfffff000`입니다. 16KB page에서는 address가 `0x00004000`, `0x00008000`에서 `0xffffc000`까지이고 PFN은 0부터 `0x3ffff`까지입니다.

4KB page에서는 page base address가 address bit 12~31을 사용합니다. 그래서 이 경우 `PAGE_SHIFT`는 12이고, `PAGE_SIZE`는 보통 `(1 << PAGE_SHIFT)`로 정의합니다.

.. SPDX-License-Identifier: GPL-2.0

===========
Page Tables
===========

Paged virtual memory was invented along with virtual memory as a concept in
1962 on the Ferranti Atlas Computer which was the first computer with paged
virtual memory. The feature migrated to newer computers and became a de facto
feature of all Unix-like systems as time went by. In 1985 the feature was
included in the Intel 80386, which was the CPU Linux 1.0 was developed on.

Page tables map virtual addresses as seen by the CPU into physical addresses
as seen on the external memory bus.

Linux defines page tables as a hierarchy which is currently five levels in
height. The architecture code for each supported architecture will then
map this to the restrictions of the hardware.

The physical address corresponding to the virtual address is often referenced
by the underlying physical page frame. The **page frame number** or **pfn**
is the physical address of the page (as seen on the external memory bus)
divided by `PAGE_SIZE`.

Physical memory address 0 will be *pfn 0* and the highest pfn will be
the last page of physical memory the external address bus of the CPU can
address.

With a page granularity of 4KB and a address range of 32 bits, pfn 0 is at
address 0x00000000, pfn 1 is at address 0x00001000, pfn 2 is at 0x00002000
and so on until we reach pfn 0xfffff at 0xfffff000. With 16KB pages pfs are
at 0x00004000, 0x00008000 ... 0xffffc000 and pfn goes from 0 to 0x3ffff.

As you can see, with 4KB pages the page base address uses bits 12-31 of the
address, and this is why `PAGE_SHIFT` in this case is defined as 12 and
`PAGE_SIZE` is usually defined in terms of the page shift as `(1 << PAGE_SHIFT)`

계층이 깊어진 이유

Memory 크기가 증가하면서 page-table hierarchy도 깊어졌습니다. Linux가 처음 만들어졌을 때는 4KB page와 entry 1,024개인 `swapper_pg_dir`라는 단일 page table을 사용해 4MB를 다뤘습니다. 이는 Linus Torvalds의 첫 computer가 physical memory 4MB를 가졌던 것과 일치합니다. 이 단일 table의 entry를 PTE, 즉 page-table entry라고 불렀습니다.

Software page-table hierarchy는 hardware page table이 계층화된 현실을 반영합니다. Hardware가 계층을 쓰는 이유도 page-table memory를 절약하고 mapping 속도를 높이기 위해서입니다.

전체 memory를 page 단위로 나눈 entry가 엄청나게 많은 단일 linear page table을 상상할 수는 있습니다. 그러나 virtual memory의 큰 부분은 보통 사용하지 않으므로 table이 매우 sparse해집니다. Hierarchical page table은 virtual-address space의 큰 hole을 상위 단계에서 unmapped로 표시할 수 있어, 빈 영역 때문에 귀중한 page-table memory를 낭비하지 않습니다.

Modern CPU에서는 상위 page-table entry가 physical-memory range를 직접 가리킬 수도 있습니다. 하나의 high-level entry로 연속된 수 MB 또는 수 GB를 mapping해 virtual-to-physical 변환의 지름길을 만들 수 있습니다. 이런 large mapped range를 찾으면 hierarchy를 더 깊이 순회할 필요가 없습니다.

Over time a deeper hierarchy has been developed in response to increasing memory
sizes. When Linux was created, 4KB pages and a single page table called
`swapper_pg_dir` with 1024 entries was used, covering 4MB which coincided with
the fact that Torvald's first computer had 4MB of physical memory. Entries in
this single table were referred to as *PTE*:s - page table entries.

The software page table hierarchy reflects the fact that page table hardware has
become hierarchical and that in turn is done to save page table memory and
speed up mapping.

One could of course imagine a single, linear page table with enormous amounts
of entries, breaking down the whole memory into single pages. Such a page table
would be very sparse, because large portions of the virtual memory usually
remains unused. By using hierarchical page tables large holes in the virtual
address space does not waste valuable page table memory, because it will suffice
to mark large areas as unmapped at a higher level in the page table hierarchy.

Additionally, on modern CPUs, a higher level page table entry can point directly
to a physical memory range, which allows mapping a contiguous range of several
megabytes or even gigabytes in a single high-level page table entry, taking
shortcuts in mapping virtual memory to physical memory: there is no need to
traverse deeper in the hierarchy when you find a large mapped range like this.

5단계 page-table hierarchy

현재 page-table hierarchy는 위에서부터 `PGD → P4D → PUD → PMD → PTE` 순서입니다. 각 단계 symbol의 의미를 가장 아래부터 설명하면 다음과 같습니다.

• `pte`, `pte_t`, `pteval_t`: Page Table Entry입니다. `pte`는 `pteval_t` 유형 element `PTRS_PER_PTE`개로 된 array이며, 각 element가 virtual-memory page 하나를 physical-memory page 하나에 mapping합니다. `pteval_t`의 크기와 내용은 architecture가 정의합니다.
• 일반적인 `pteval_t`는 32bit 또는 64bit 값입니다. 상위 bit는 PFN이고 하위 bit는 memory protection 같은 architecture별 bit입니다.
• `entry`라는 이름은 다소 혼동을 줍니다. Linux 1.0에서는 단일 top-level page table의 entry 하나를 가리켰지만, 2단계 page table 도입 때 mapping element array라는 의미로 바뀌었습니다. 따라서 현재 `pte`는 page-table entry 하나가 아니라 가장 아래쪽 page table입니다.
• `pmd`, `pmd_t`, `pmdval_t`: Page Middle Directory입니다. `pte` 바로 위 hierarchy이며 `pte`를 가리키는 reference `PTRS_PER_PMD`개를 가집니다.
• `pud`, `pud_t`, `pudval_t`: Page Upper Directory입니다. 4단계 page table을 다루려고 다른 단계 뒤에 도입했습니다. 사용하지 않거나 뒤에서 설명할 방식으로 folded될 수 있습니다.
• `p4d`, `p4d_t`, `p4dval_t`: Page Level 4 Directory입니다. `pud` 도입 뒤 5단계 page table을 다루려고 추가했습니다. `pgd`, `pmd`, `pud` 같은 임시 이름을 계속 만들 수 없고 directory level을 숫자로 표시해야 한다는 점이 분명해졌습니다. 실제 5단계 page table을 쓰는 system에서만 사용하며 나머지에서는 folded됩니다.
• `pgd`, `pgd_t`, `pgdval_t`: Page Global Directory입니다. Kernel memory의 PGD를 다루는 Linux kernel 주 page table은 여전히 `swapper_pg_dir`에 있습니다. System의 각 userspace process도 자체 memory context와 `pgd`를 가지며, `struct task_struct`가 참조하는 `struct mm_struct`에서 이를 찾습니다.

즉 task는 `struct mm_struct` 형태의 memory context를 갖고, 이 구조에는 대응하는 page-global directory를 가리키는 `struct pgt_t *pgd` pointer가 있습니다. 이 선언은 원문 표기대로 보존했습니다.

The page table hierarchy has now developed into this::

  +-----+
  | PGD |
  +-----+
     |
     |   +-----+
     +-->| P4D |
         +-----+
            |
            |   +-----+
            +-->| PUD |
                +-----+
                   |
                   |   +-----+
                   +-->| PMD |
                       +-----+
                          |
                          |   +-----+
                          +-->| PTE |
                              +-----+


Symbols on the different levels of the page table hierarchy have the following
meaning beginning from the bottom:

- **pte**, `pte_t`, `pteval_t` = **Page Table Entry** - mentioned earlier.
  The *pte* is an array of `PTRS_PER_PTE` elements of the `pteval_t` type, each
  mapping a single page of virtual memory to a single page of physical memory.
  The architecture defines the size and contents of `pteval_t`.

  A typical example is that the `pteval_t` is a 32- or 64-bit value with the
  upper bits being a **pfn** (page frame number), and the lower bits being some
  architecture-specific bits such as memory protection.

  The **entry** part of the name is a bit confusing because while in Linux 1.0
  this did refer to a single page table entry in the single top level page
  table, it was retrofitted to be an array of mapping elements when two-level
  page tables were first introduced, so the *pte* is the lowermost page
  *table*, not a page table *entry*.

- **pmd**, `pmd_t`, `pmdval_t` = **Page Middle Directory**, the hierarchy right
  above the *pte*, with `PTRS_PER_PMD` references to the *pte*:s.

- **pud**, `pud_t`, `pudval_t` = **Page Upper Directory** was introduced after
  the other levels to handle 4-level page tables. It is potentially unused,
  or *folded* as we will discuss later.

- **p4d**, `p4d_t`, `p4dval_t` = **Page Level 4 Directory** was introduced to
  handle 5-level page tables after the *pud* was introduced. Now it was clear
  that we needed to replace *pgd*, *pmd*, *pud* etc with a figure indicating the
  directory level and that we cannot go on with ad hoc names any more. This
  is only used on systems which actually have 5 levels of page tables, otherwise
  it is folded.

- **pgd**, `pgd_t`, `pgdval_t` = **Page Global Directory** - the Linux kernel
  main page table handling the PGD for the kernel memory is still found in
  `swapper_pg_dir`, but each userspace process in the system also has its own
  memory context and thus its own *pgd*, found in `struct mm_struct` which
  in turn is referenced to in each `struct task_struct`. So tasks have memory
  context in the form of a `struct mm_struct` and this in turn has a
  `struct pgt_t *pgd` pointer to the corresponding page global directory.

Pointer array 구조와 folding

Page-table hierarchy의 각 단계는 pointer array입니다. `pgd`에는 다음 하위 단계로 가는 pointer `PTRS_PER_PGD`개가 있고, `p4d`에는 `pud` item을 가리키는 pointer `PTRS_PER_P4D`개가 있으며 나머지도 같은 방식입니다. 각 단계의 pointer 수는 architecture가 정합니다.

원문의 두 번째 구조도는 PMD의 여러 pointer가 서로 다른 PTE table을 가리키고, 각 PTE의 pointer가 실제 PAGE를 가리키는 분기 구조를 보여 줍니다.

Architecture가 모든 page-table level을 사용하지 않으면 일부 level을 folded할 수 있습니다. Folding은 그 level을 건너뛴다는 뜻이며, page-table operation은 compile time에 확장되어 다음 하위 level에 접근할 때 해당 level을 생략합니다.

Virtual-memory manager처럼 architecture-neutral해야 하는 page-table code는 현재 5단계를 모두 순회하도록 작성해야 합니다. 향후 변경에 견고하도록 architecture-specific code도 이 style을 따르는 편이 좋습니다.

To repeat: each level in the page table hierarchy is a *array of pointers*, so
the **pgd** contains `PTRS_PER_PGD` pointers to the next level below, **p4d**
contains `PTRS_PER_P4D` pointers to **pud** items and so on. The number of
pointers on each level is architecture-defined.::

        PMD
  --> +-----+           PTE
      | ptr |-------> +-----+
      | ptr |-        | ptr |-------> PAGE
      | ptr | \       | ptr |
      | ptr |  \        ...
      | ... |   \
      | ptr |    \         PTE
      +-----+     +----> +-----+
                         | ptr |-------> PAGE
                         | ptr |
                           ...


Page Table Folding
==================

If the architecture does not use all the page table levels, they can be *folded*
which means skipped, and all operations performed on page tables will be
compile-time augmented to just skip a level when accessing the next lower
level.

Page table handling code that wishes to be architecture-neutral, such as the
virtual memory manager, will need to be written so that it traverses all of the
currently five levels. This style should also be preferred for
architecture-specific code, so as to be robust to future changes.

MMU, TLB와 page fault 기본 동작

`Memory Management Unit (MMU)`은 virtual address를 physical address로 변환하는 hardware component입니다. 변환 속도를 높이려고 hardware의 비교적 작은 cache인 `Translation Lookaside Buffer (TLB)`와 `Page Walk Cache`를 사용할 수 있습니다.

CPU가 memory location에 접근하면 MMU에 virtual address를 제공합니다. MMU는 TLB 또는 이를 지원하는 architecture의 Page Walk Cache에 기존 translation이 있는지 검사합니다. Translation이 없으면 page walk로 physical address를 결정하고 map을 만듭니다.

Page에 write하면 dirty bit를 set합니다. 각 memory page에는 permission bit와 dirty bit가 있으며, dirty bit는 memory에 load된 뒤 page가 수정되었음을 나타냅니다.

접근을 막는 조건이 없으면 최종적으로 physical memory에 접근해 요청한 operation을 physical frame에 수행합니다.

MMU가 translation을 찾지 못하는 이유는 여러 가지입니다. CPU가 current task에 허용되지 않은 memory에 접근하거나 data가 physical memory에 없을 수 있습니다. 이런 조건에서는 MMU가 page fault라는 exception을 일으켜 CPU가 현재 실행을 멈추고 exception 처리용 특별한 함수를 실행하게 합니다.

MMU, TLB, and Page Faults
=========================

The `Memory Management Unit (MMU)` is a hardware component that handles virtual
to physical address translations. It may use relatively small caches in hardware
called `Translation Lookaside Buffers (TLBs)` and `Page Walk Caches` to speed up
these translations.

When CPU accesses a memory location, it provides a virtual address to the MMU,
which checks if there is the existing translation in the TLB or in the Page
Walk Caches (on architectures that support them). If no translation is found,
MMU uses the page walks to determine the physical address and create the map.

The dirty bit for a page is set (i.e., turned on) when the page is written to.
Each page of memory has associated permission and dirty bits. The latter
indicate that the page has been modified since it was loaded into memory.

If nothing prevents it, eventually the physical memory can be accessed and the
requested operation on the physical frame is performed.

There are several reasons why the MMU can't find certain translations. It could
happen because the CPU is trying to access memory that the current task is not
permitted to, or because the data is not present into physical memory.

When these conditions happen, the MMU triggers page faults, which are types of
exceptions that signal the CPU to pause the current execution and run a special
function to handle the mentioned exceptions.

Page fault 원인과 결과

흔하고 정상적인 page fault 원인에는 process-management 최적화 기법인 Lazy Allocation과 Copy-on-Write가 있습니다. Frame이 swap partition이나 file 같은 persistent storage로 swap out되어 physical 위치에서 evict된 경우에도 page fault가 발생합니다.

이 기법들은 memory 효율을 높이고 latency와 공간 사용을 줄입니다. Lazy Allocation과 Copy-on-Write는 Process Address Management에 속해 이 문서의 범위를 벗어나므로 더 깊이 다루지 않습니다.

Swapping은 심한 memory pressure에서 memory 사용을 줄이기 위한 바람직하지 않은 수단이라는 점에서 다른 기법과 구별됩니다.

Kernel logical address로 mapping된 memory에는 swapping을 적용할 수 없습니다. Logical-address 영역은 연속된 physical-memory range를 직접 mapping하는 kernel virtual space의 일부입니다. Logical address가 주어지면 단순한 offset 산술로 physical address를 구합니다. 복잡한 page-table lookup을 피하므로 접근은 빠르지만, 그 대가로 frame을 evict하거나 page out할 수 없습니다.

Physical frame에 있어야 하는 data를 위한 공간을 kernel이 확보하지 못하면 OOM killer를 호출합니다. Pressure가 안전한 threshold 아래로 내려갈 때까지 priority가 낮은 process를 종료해 공간을 만듭니다.

Code bug 또는 악의적으로 만든 address 때문에도 page fault가 날 수 있습니다. Process thread가 자기 address space에 속하지 않는 non-shared memory를 가리키는 instruction을 사용하거나, read-only location에 쓰는 instruction을 실행하려 할 수 있습니다.

이 조건이 userspace에서 발생하면 kernel은 current thread에 `Segmentation Fault`, 즉 `SIGSEGV` signal을 보냅니다. 보통 해당 thread와 그 thread가 속한 process가 종료됩니다.

이 문서는 Linux kernel이 page fault를 처리하고 table과 entry를 만들며, memory가 present인지 검사하고 없으면 persistent storage 또는 다른 device에서 data load를 요청한 뒤 MMU와 cache를 갱신하는 과정을 높은 수준에서 단순화해 설명합니다.

There are common and expected causes of page faults. These are triggered by
process management optimization techniques called "Lazy Allocation" and
"Copy-on-Write". Page faults may also happen when frames have been swapped out
to persistent storage (swap partition or file) and evicted from their physical
locations.

These techniques improve memory efficiency, reduce latency, and minimize space
occupation. This document won't go deeper into the details of "Lazy Allocation"
and "Copy-on-Write" because these subjects are out of scope as they belong to
Process Address Management.

Swapping differentiates itself from the other mentioned techniques because it's
undesirable since it's performed as a means to reduce memory under heavy
pressure.

Swapping can't work for memory mapped by kernel logical addresses. These are a
subset of the kernel virtual space that directly maps a contiguous range of
physical memory. Given any logical address, its physical address is determined
with simple arithmetic on an offset. Accesses to logical addresses are fast
because they avoid the need for complex page table lookups at the expenses of
frames not being evictable and pageable out.

If the kernel fails to make room for the data that must be present in the
physical frames, the kernel invokes the out-of-memory (OOM) killer to make room
by terminating lower priority processes until pressure reduces under a safe
threshold.

Additionally, page faults may be also caused by code bugs or by maliciously
crafted addresses that the CPU is instructed to access. A thread of a process
could use instructions to address (non-shared) memory which does not belong to
its own address space, or could try to execute an instruction that want to write
to a read-only location.

If the above-mentioned conditions happen in user-space, the kernel sends a
`Segmentation Fault` (SIGSEGV) signal to the current thread. That signal usually
causes the termination of the thread and of the process it belongs to.

This document is going to simplify and show an high altitude view of how the
Linux kernel handles these page faults, creates tables and tables' entries,
check if memory is present and, if not, requests to load data from persistent
storage or from other devices, and updates the MMU and its caches.

Architecture별 fault 진입과 table allocation

첫 단계는 architecture에 따라 다릅니다. 대부분의 architecture는 `do_page_fault()`로 이동합니다. x86 interrupt handler는 `DEFINE_IDTENTRY_RAW_ERRORCODE()` macro로 정의되며 `handle_page_fault()`를 호출합니다.

경로가 무엇이든 모든 architecture는 결국 `handle_mm_fault()`를 호출하고, 이 함수는 실제 page-table allocation 작업을 하는 `__handle_mm_fault()`를 호출할 가능성이 큽니다.

`__handle_mm_fault()`를 호출할 수 없는 불운한 경우는 virtual address가 current context에서 접근이 허용되지 않은 physical-memory 영역을 가리킨다는 뜻입니다. Kernel은 앞서 설명한 `SIGSEGV`를 process에 보내고 같은 결과로 이어집니다.

`__handle_mm_fault()`는 여러 함수를 호출해 page table 상위 layer의 entry offset을 찾고 필요한 table을 할당합니다.

Offset을 찾는 함수 이름은 `*_offset()` 형식이며 `*` 자리에 `pgd`, `p4d`, `pud`, `pmd`, `pte`가 들어갑니다. 대응 table을 layer별로 할당하는 함수는 같은 naming convention을 사용한 `*_alloc`입니다.

The first steps are architecture dependent. Most architectures jump to
`do_page_fault()`, whereas the x86 interrupt handler is defined by the
`DEFINE_IDTENTRY_RAW_ERRORCODE()` macro which calls `handle_page_fault()`.

Whatever the routes, all architectures end up to the invocation of
`handle_mm_fault()` which, in turn, (likely) ends up calling
`__handle_mm_fault()` to carry out the actual work of allocating the page
tables.

The unfortunate case of not being able to call `__handle_mm_fault()` means
that the virtual address is pointing to areas of physical memory which are not
permitted to be accessed (at least from the current context). This
condition resolves to the kernel sending the above-mentioned SIGSEGV signal
to the process and leads to the consequences already explained.

`__handle_mm_fault()` carries out its work by calling several functions to
find the entry's offsets of the upper layers of the page tables and allocate
the tables that it may need.

The functions that look for the offset have names like `*_offset()`, where the
"*" is for pgd, p4d, pud, pmd, pte; instead the functions to allocate the
corresponding tables, layer by layer, are called `*_alloc`, using the
above-mentioned convention to name them after the corresponding types of tables
in the hierarchy.

Huge page와 fault 처리 완료

Page-table walk는 PMD나 PUD 같은 middle 또는 upper layer에서 끝날 수 있습니다.

Linux는 일반적인 4KB보다 큰 `huge page`를 지원합니다. 큰 page를 사용하면 high-level entry가 이를 직접 mapping하므로 하위 PTE가 필요 없습니다. Huge page는 보통 2MB부터 1GB까지의 큰 연속 physical 영역이며, 각각 PMD와 PUD entry가 mapping합니다.

Huge page는 TLB pressure와 page-table overhead를 줄이고 memory-allocation 효율과 일부 workload 성능을 높입니다. 반면 memory 낭비와 allocation 난이도라는 trade-off가 있습니다.

Allocation을 포함한 walk가 error 없이 끝까지 가면 `__handle_mm_fault()`가 마지막으로 `handle_pte_fault()`를 호출합니다. 이 함수는 `do_fault()`를 통해 `do_read_fault()`, `do_cow_fault()`, `do_shared_fault()` 중 하나를 수행합니다. 이름의 `read`, `cow`, `shared`가 처리 중인 fault의 원인과 종류를 암시합니다.

실제 workflow 구현은 매우 복잡합니다. Linux가 공통된 전체 구조를 공유하면서도 architecture별 특성에 맞춰 page fault를 처리할 수 있게 설계되었습니다.

Page-fault handler는 각각 `pagefault_disable()`과 `pagefault_enable()`로 disable하고 enable할 수 있습니다. 여러 code path가 주로 deadlock을 막기 위해 page-fault handler trap을 잠시 disable할 필요가 있어 이 두 함수를 사용합니다.

The page table walk may end at one of the middle or upper layers (PMD, PUD).

Linux supports larger page sizes than the usual 4KB (i.e., the so called
`huge pages`). When using these kinds of larger pages, higher level pages can
directly map them, with no need to use lower level page entries (PTE). Huge
pages contain large contiguous physical regions that usually span from 2MB to
1GB. They are respectively mapped by the PMD and PUD page entries.

The huge pages bring with them several benefits like reduced TLB pressure,
reduced page table overhead, memory allocation efficiency, and performance
improvement for certain workloads. However, these benefits come with
trade-offs, like wasted memory and allocation challenges.

At the very end of the walk with allocations, if it didn't return errors,
`__handle_mm_fault()` finally calls `handle_pte_fault()`, which via `do_fault()`
performs one of `do_read_fault()`, `do_cow_fault()`, `do_shared_fault()`.
"read", "cow", "shared" give hints about the reasons and the kind of fault it's
handling.

The actual implementation of the workflow is very complex. Its design allows
Linux to handle page faults in a way that is tailored to the specific
characteristics of each architecture, while still sharing a common overall
structure.

To conclude this high altitude view of how Linux handles page faults, let's
add that the page faults handler can be disabled and enabled respectively with
`pagefault_disable()` and `pagefault_enable()`.

Several code path make use of the latter two functions because they need to
disable traps into the page faults handler, mostly to prevent deadlocks.