11
$\begingroup$

I'm reading CSAPP and couldn't wrap my head around this part:

Summary of what the section says:

  • Intel Core i7 support a 48-bit virtual address space and 52-bit physical address space.
  • Core i7 uses a four-level page table hierarchy.

Then the book shows a picture of the breakdown of a PTE:

Breakdown of a PTE

Please note the 40-bit PPN.

It goes on to say that "the 40-bit PPN points to the beginning of the appropriate page table. Notice that this imposes a 4 KB alignment requirement on page tables".

My question is what does the bolded line mean? And why there is a 4 KB alignment requirement? I know (theoretically) how virtual memory and page tables work but don't get this alignment requirement.

To further explain my confusion: What does it mean to say "...alignment requirement on page tables"? Does it mean that the PTE has to be 4KB in chunk (this was described a page before and doesn't really seem to need any further proof), or something else?

$\endgroup$
6
  • $\begingroup$ I guess I get it, after thinking about it for a while. That photo is about a level 1/2/3 page table, that is, the page table physical base address actually points to the address to a child page table the next hierarchy. Now with physical address space of 52-bit, there are 12 bits left, which means each child page table should have exactly 2^12 bytes = 4 KB in size. Does this make sense? $\endgroup$ Dec 19, 2021 at 3:53
  • 1
    $\begingroup$ In general, CPUs really like alignments. You have an 8-byte integer? It better be 8-byte aligned! And so on. Apparently it makes the hardware simpler or something. So I'm not really surprised to see such a requirement here. $\endgroup$
    – Vilx-
    Dec 20, 2021 at 13:55
  • 4
    $\begingroup$ @Vilx-: x86-64 supports misaligned integer / FP data so that's not as convincing an argument as it would be for MIPS or Alpha. The reason alignment is required here is that there's literally nowhere to store the low address bits. The bottom 12 bits of a page directory entry is flags like present, accessed, dirty, kerne/user, etc. wiki.osdev.org/Paging#64-Bit_Paging. But yes, there'd be very little reason to want a misaligned page table, and it does simplify the HW: the physical address can just stick some bits together instead of adding with possible carry into the page-number bits. $\endgroup$ Dec 20, 2021 at 14:38
  • $\begingroup$ @PeterCordes I think that comment is a better answer than the accepted one $\endgroup$
    – Flexo
    Dec 20, 2021 at 17:15
  • $\begingroup$ @Flexo: Good point, posted as such. $\endgroup$ Dec 20, 2021 at 18:39

3 Answers 3

23
$\begingroup$

The physical address for the start of a page frame or page table is obtained by taking the 40-bit PPN and appending 12 zero bits. That gives you a 52-bit physical address, which is the start of the frame or page table.

A consequence is that frames or page tables must start at a physical address that is a multiple of $2^{12}=4096$, i.e., that is aligned at a multiple of 4KB.

$\endgroup$
2
  • 4
    $\begingroup$ Terminology nitpick: a "page table entry" is 8 bytes, a single translation mapping. There are 512 PTEs in a "page table" that fills an aligned 4kiB. (Why in x86-64 the virtual address are 4 bits shorter than physical (48 bits vs. 52 long)? has a nice diagram of x86-64's 4-level paging structures, with names for each level, e.g. a page directory is the next level up, containing 512 PDEs or largepage entries.) $\endgroup$ Dec 19, 2021 at 20:36
  • $\begingroup$ @PeterCordes, thank you for the correction! Edited. I appreciate it. $\endgroup$
    – D.W.
    Dec 19, 2021 at 20:45
11
$\begingroup$

Alignment is required for page tables because there's literally nowhere to store the low address bits.

The bottom 12 bits of a page directory entry is flags like present, accessed, user/supervisor, whether this is actually a largepage instead of a pointer to a page table, etc. https://wiki.osdev.org/Paging#64-Bit_Paging. Similar for the higher 2 levels of tables; see Why in x86-64 the virtual address are 4 bits shorter than physical (48 bits vs. 52 long)? for official names for different levels, and a nice diagram of how x86-64 4-level page tables work.

In theory the top-level page table pointer (set with mov cr3, rax or whatever) does have a full 64 bits, but the low 12 bits are ignored / reserved. Or with a control-register setting, repurposed as process-context ID (PCID) to tag non-global TLB entries so they can survive across CR3 updates, making frequent context switches somewhat less bad.


There'd be very little reason to want a misaligned page table, and it does simplify the HW: the physical address can just concatenate some bits together instead of adding with possible carry into the page-number bits. And since virt->phys mappings happen in aligned 4k blocks, free physical memory in aligned 4k blocks is what you want to track anyway.

(And with paging enabled, load/store instructions the kernel executes in functions that read and/or update page tables can only use virtual addresses. An aligned 4k of phys memory can be addressed through one virtual 4k page, instead of maybe costing the kernel multiple TLB misses when accessing 4kiB split across two virtual pages. Many kernels such as Linux will direct-map all of physical RAM, or large chunks of it, with 1G hugepages, but still...)


Actual physical pages (page frames) should always be aligned, so the offset-within-page virtual address bits are also the physical offset-from-4k-boundary address bits. Among other things, that lets an L1d cache have the speed of VIPT (indexing based on bits from the virt addr) without any aliasing problems if the cache is small enough and associative enough. The bits below the page offset effectively translate for free, without the TLB, so such a VIPT cache is effectively PIPT.

It also means two virtual pages can't partially overlap; they either map to the same physical page or not. (Not counting largepage / hugepage). And it would make each TLB entry larger, which is a Bad Thing. e.g. on an early x86-64 with 40-bit physical addresses, a 4k page's TLB entry only needs 28 bits of physical address, instead of 37 if we had only 8-byte alignment.

So that means an actual PTE shouldn't waste space on low address bits. Having a page directory entry use an identical format makes a ton of sense.

There are actually 11 unused high bits above the highest reserved bit (#52) in a PTE/PDE, so there actually is room if we didn't care about leaving more unused space for OSes to keep bookkeeping data. (They're fully ignore by HW.) So the HW page table design could have left only 3 physical bits implicitly zero (8-byte alignment), while still allowing up to 52-bit physical addresses, if anyone had thought that was worth doing.

Either by left-shifting the phys address field, or keeping flags at the top. Low bits are more efficient for software to manipulate on x86-64. But there's no good reason to make HW throw those bits around at all.

PAE and thus x86-64 use the same flag-bit layout at the bottom of each entry as 32-bit legacy page-tables (4 bytes per PTE, 2x 10-bit levels mapping 32-bit virt -> 32-bit phys which only had 3 unused PTE bits, in bits [11:9]).

One of AMD's major goals was to reduce barriers to entry, making porting of OSes and toolchains easier, to increase the chance of getting traction and not becoming dead weight in their CPUs. Also keeping HW as similar as possible so they could share transistors in decoders and so on, which meant not fixing many x86 warts. Fortunately Intel's PAE format is very reasonable, so they could literally use it directly, just adding 2 more levels.

$\endgroup$
2
$\begingroup$

What's not shown in the little bit assignment table you looked at is:

  1. The bits 51:12 of the PTE are also bits 51:12 of the page table address.

  2. The complete page table address consists of bits 51:12 of the PTE in bit positions 51:12, and zeroes elsewhere.

Perhaps this picture will make it clearer:

A depiction of how the bits 51 through 12 of the PTE get combined with zeroes to yield a physical table address.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.