On 6/5/23 15:10, Linus Walleij wrote: > This is based on an earlier blog post at people.kernel.org, > it describes the concepts about page tables that were hardest > for me to grasp when dealing with them for the first time, > such as the prevalent three-letter acronyms pfn, pgd, p4d, > pud, pmd and pte. > > I don't know if this is what people want, but it's what I would > have wanted. > > I discussed at one point with Mike Rapoport to bring this into > the kernel documentation, so here is a small proposal. > > Cc: Mike Rapoport <rppt@xxxxxxxxxx> > Link: https://people.kernel.org/linusw/arm32-page-tables > Signed-off-by: Linus Walleij <linus.walleij@xxxxxxxxxx> > --- > Documentation/mm/page_tables.rst | 125 +++++++++++++++++++++++++++++++ > 1 file changed, 125 insertions(+) > > diff --git a/Documentation/mm/page_tables.rst b/Documentation/mm/page_tables.rst > index 96939571d7bc..a2e1671a0f1d 100644 > --- a/Documentation/mm/page_tables.rst > +++ b/Documentation/mm/page_tables.rst > @@ -3,3 +3,128 @@ > =========== > 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. > + > +The first computers with virtual memory had one single page table, but the > +increased size of physical memories demanded that the page tables be split in > +two hierarchical levels. This happens because a single page table cannot cover > +the desired amount of memory with the desired granualarity, such as a page size > +of 4KB. > + > +The physical address corresponding to the virtual address is commonly > +defined by the index point in the hierarchy, and this is called a **page frame > +number** or **pfn**. The first entry on the top level to the first entry in the > +second and so on down the hierarchy will point out the virtual address for the > +physical memory address 0, which 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 0x00004000, pfn 2 is at 0x00008000 > +and so on until we reach pfn 0x3ffff at 0xffffc000. > + > +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)` > + > +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 was referred to as *PTE*:s - page table entries. > + > +Over time the page table hierarchy has developed into this:: > + > + +-----+ > + | PGD | > + +-----+ > + ^ > + | +-----+ > + +---| P4D | > + +-----+ > + ^ > + | +-----+ > + +---| PUD | > + +-----+ > + ^ > + | +-----+ > + +---| PMD | > + +-----+ > + ^ > + | +-----+ > + +---| PTE | > + +-----+ > + > + > +Symbols on the different levels of the page table hierarchy have the following > +meaning: > + > +- **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. > + > +- **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 nee to replace *pgd*, *pmd*, *pud* etc with a figure indicating the need > + 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. > + > +- **pud**, `pud_t`, `pudval_t` = **Page Upper Directory** was introduced after > + the other levels to handle 4-level page tables. Like *p4d*, it is potentially > + unused. > + > +- **pmd**, `pmd_t`, `pmdval_t` = **Page Middle Directory**. > + > +- **pte**, `pte_t`, `pteval_t` = **Page Table Entry** - mentioned earlier. > + The name is a bit confusing because while in Linux 1.0 this did refer to a > + single page table entry in the top level page table, it was retrofitted > + to be "what the level above points to". So when two-level page tables were > + introduced, the *pte* became a list of pointers, which is why > + `PTRS_PER_PTE` exists. This oxymoronic term can be mildly confusing. > + > +As already mentioned, each level in the page table hierarchy is a *list 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. The most usual layout > +is the `PAGE_SIZE` of the system divided by the number of bytes in a virtual > +address on the system so each page table level is exactly one page worth of > +pointers, which is usually what computer architects choose:: > + > + PMD > + +-----+ PTE > + | ptr |-------> +-----+ > + | ptr |- | ptr |-------> PAGE > + | ptr | \ | ptr | > + | ptr | \ ... > + | ... | \ > + | ptr | \ PTE > + +-----+ +----> +-----+ > + | ptr |-------> PAGE > + | ptr | > + ... > + > + > +Each pointer in the lowest level of the page table hierarchy, i.e. each > +`pteval_t`-entry of the `PTRS_PER_PTE` entries in a `pte_t *`, will map exactly > +one `PAGE_SIZE`:d page of physical memory to exactly one page of virtual memory. > + > +The pte page table entries (pointers) on the lowest level of the hierarchy > +typically contain the high bits of a virtual address in its high bits, and in > +the lower bits it contains architecture-dependent control bits pertaining to > +the page. > + > +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 wish to be architecture-neutral, such as wishes > +the virtual memory manager, will however need to be written so that it > +traverses all of the currently five levels. Thanks for the documentation. -- ~Randy
