2

As the title implies, the question is regarding alignment of aggregate types in x86-64 on Linux.

In our lecture, the professor introduced alignment of structs (and the elements thereof) with the attached slide. Hence, I would assume (in accordance with wikipedia and other lecture material) that for any aggregate type, the alignment is in accordance to its largest member. Unfortunately, this does not seem to be the case in a former exam question, in which it said:

"Assuming that each page table [4kB, each PTE 64b] is stored in memory at a “naturally aligned” physical address (i.e. an address which is an integer multiple of the size of the table), ..."

How come that for a page table (which afaik is basically an array of 8 byte values in memory), alignment rules are not according to the largest element, but to the size of the whole table?

Clarification is greatly appreciated!
Felix Lecture slide

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
iMrFelix
  • 335
  • 2
  • 18
  • *according to the largest element*. That's not the rule for normal structs either. You want `max(alignof(member))` not `max(sizeof(member))`. So "according to the most-aligned element" would be a better way to describe the required alignment of a normal struct. e.g. in the i386 System V ABI, `double` has sizeof = 8 but alignof = 4, so `alignof(struct S1) = 4`. – Peter Cordes Jan 29 '20 at 23:46

2 Answers2

7

Why page tables are aligned on their size

For a given level on the process of translating the virtual address, requiring the current page table to be aligned on its size in bytes speeds up the indexing operation.
The CPU doesn't need to perform an actual addition to find the base of the next level page table, it can scale the index and then replace the lowest bits in the current level base.

You can convince yourself this is indeed the case with a few examples.
It's not a coincidence x86s follow this alignment too.

For example, regarding the 4-level paging for 4KiB pages of the x86 CPUs, the Page Directory Pointer field of a 64-bit address is 9 bits wide.
Each entry in that table (a PDPTE) is 64 bits, so the page size is 4096KiB and the last entry has offset 511 * 8 = 4088 (0xff8 in hex, so only 12 bits used at most).
The address of a Page Directory Pointer table is given by a PML4 entry, these entries have don't specify the lower 12 bits of the base (which are used for other purposes), only the upper bits.
The CPU can then simply replace the lower 12 bits in the PML4 entry with the offset of the PDPTE since we have seen it has size 12 bits.

This is fast and cheap to do in hardware (no carry, easy to do with registers).

Assume that a country has ZIP codes made of two fields: a city code (C) and a block code (D), added together.
Also, assume that there can be at most 100 block codes for a given city, so D is 2 digits long.
Requiring that the city code is aligned on 100 (which means that the last two digits of C are zero) makes C + D like replacing the last two digits of C with D. (1200 + 34 = 12|34).

Relation with the alignment of aggregates

A page table is not regarded as an aggregate, i.e. as an array of 8 byte elements. It is regarded as a type of its own, defined by the ISA of the CPU and that must satisfy the requirement of the particular part of the CPU that uses it.
The page walker finds convenient to have a page table aligned on their size, so this is the requirement.

The alignment of aggregates is a set of rules used by the compiler to allocate objects in memory, it guarantees that every element alignment is satisfied so that instructions can access any element without alignment penalties/fault.
The execution units for loads and stores are a different part of the CPU than the page walker, so different needs.

You should use the aggregates alignment to know how the compiler will align your structs and then check if that's enough for your use case.

Exceptions exist

Note that the professor went a long way with explaining what alignment on their natural boundary means for page tables.
Exceptions exist, if you are told that a datum must be aligned on X, you can assume there's some hardware trick/simplification involved and try to see which one but in the end you just do the alignment and move on.

Community
  • 1
  • 1
Margaret Bloom
  • 41,768
  • 5
  • 78
  • 124
1

Margaret explained why page tables are special, I'm only answer this other part of the question.

according to the largest element.

That's not the rule for normal structs either. You want max(alignof(member)) not max(sizeof(member)). So "according to the most-aligned element" would be a better way to describe the required alignment of a normal struct.

e.g. in the i386 System V ABI, double has sizeof = 8 but alignof = 4, so alignof(struct S1) = 41

Even if the char member had been last, sizeof(struct S1) still has to be padded to a multiple of its alignof(), so all the usual invariants are maintained (e.g. sizeof( array ) = N * sizeof(struct S1)), and so stepping by sizeof always gets you to a sufficiently-aligned boundary for the start of a new struct.

Footnote 1: That ABI was designed before CPUs could efficiently load/store 8 bytes at once. Modern compilers try to give double and [u]int64_t 8-byte alignment, e.g. as globals or locals outside of structs. But the ABI's struct layout rules fix the layout based on the minimum guaranteed alignment for any double or int64_t object, which is alignof(T) = 4 for those types.

x86-64 System V has alignof(T) = sizeof(T) for all the primitive types, including the 8-byte ones. This makes atomic operations on any properly-aligned int64_t possible, for example, simplifying the implementation of C++20 std::atomic_ref to not have to check for sufficient alignment. (Why is integer assignment on a naturally aligned variable atomic on x86?)

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847