Re: [PATCH] Documentation/mm: Initial page table documentation

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Tue, 2023-06-06 at 00:10 +0200, 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.

pfn 1 is at 0x00001000.
pfn 2 is at 0x00002000.

And so on until we reach pfn 0xfffff at 0xfffff000.

> +
> +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
> +  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
> +the virtual memory manager, will however need to be written so that
> it
> +traverses all of the currently five levels.




[Index of Archives]     [Linux ARM Kernel]     [Linux ARM]     [Linux Omap]     [Fedora ARM]     [IETF Annouce]     [Bugtraq]     [Linux OMAP]     [Linux MIPS]     [eCos]     [Asterisk Internet PBX]     [Linux API]

  Powered by Linux