Pointer tagging for x86 systems

Posted Mar 28, 2022 20:29 UTC (Mon) by willy (subscriber, #9762)
Parent article: Pointer tagging for x86 systems

I know that Our Benevolent Editor knows this is misleading (and this is presumably just clumsy wording):

> There are no systems (yet) that require — or can provide — all of the memory that can be addressed by 64 bits, meaning that there are ranges of address space that do not map to physical memory.

This conflates userspace addressing and kernel addressing. Userspace would love to have more address space available. Even with 64 bit pointers, address space fragmentation is a real thing, and prevents doing things like mmap() of an entire multi-petabyte file.

The real problem is with the CPU. More virtual address bits available to userspace means more levels of page table or larger tables at each level or some other undesirable expansion that affects performance. It also affects how the L3 (perhaps also L2 and L1?) caches are implemented as more address bits must be checked, and thus also stored. Five level page tables come with some real costs beyond the obvious extra level of lookup!

It is my opinion (based on precisely zero inside information) that Intel and AMD have decided that their current architectures will stop at five levels (57 bits of virtual address). When they need to go beyond this, we're talking about a 128 bit architecture with a rather different approach to page tables. So they're using the last few top bits to provide useful functionality like pointer tagging that people actually want.

Pointer tagging for x86 systems

Posted Mar 28, 2022 21:29 UTC (Mon) by jhoblitt (subscriber, #77733) [Link] (5 responses)

128b would be wasteful in terms of I/D cache space. 80b/95b would probably be a reasonable next step. There is also an argument to be made for having the size of memory addresses != size of integers.

Pointer tagging for x86 systems

Posted Mar 29, 2022 3:10 UTC (Tue) by willy (subscriber, #9762) [Link]

Do you have experience in CPU design?

Pointer tagging for x86 systems

Posted Mar 29, 2022 6:07 UTC (Tue) by wtarreau (subscriber, #51152) [Link] (3 responses)

> There is also an argument to be made for having the size of memory addresses != size of integers.

This argument can only come from those nostalgic of the 8086/8088! What a disaster it was!

Pointer tagging for x86 systems

Posted Mar 29, 2022 12:33 UTC (Tue) by jem (subscriber, #24231) [Link] (1 responses)

Or the PDP-10, which had a word size of 36 bits, and an address size of half a word (18 bits). The PDP-10 was word addressable, i.e. the address pointed to a 36-bit word, but there were also "byte instructions", which used special 36-bit byte pointers. Instructions using these byte pointers could load or store any number of bits (1-36) starting from any bit position. (I don't know what happened if the offset+size exceeded the number of bits in a word.)

sizeof (int) == 5 according to a C compiler I got to try out on a DEC-20.

http://pdp10.nocrew.org/docs/instruction-set/Byte.html

Pointer tagging for x86 systems

Posted Apr 1, 2022 1:02 UTC (Fri) by azz (subscriber, #371) [Link]

It's also idiomatic on the PDP-10 to use 36-bit "AOBJN" pointers where the low 18 bits contains the address, and the high 18 bits contains a negated count of words following the address - so each pointer also contains the length of the thing it points at, and you can easily do bounds checks and iteration.

C is really not a good fit for the PDP-10. There's at least one PDP-10 C compiler (Alan Snyder's) where all the primitive types, including char, are 36 bits...

Pointer tagging for x86 systems

Posted Apr 7, 2022 14:35 UTC (Thu) by mrugiero (guest, #153040) [Link]

Not quite: https://nw0.github.io/cheri-rust.pdf

Pointer tagging for x86 systems

Posted Mar 29, 2022 9:31 UTC (Tue) by farnz (subscriber, #17727) [Link]

One thing that adds weight to your notion that they'll not go beyond 57 bits of VA space is that thus far, each page level in x86-64 adds 9 bits of VA space (because that fills an entire 4K page), and apart from the PTEs having their PAT bit in a different place to PDE and PDPTE (the PTE place for PAT is used in all higher level tables for "stop paging here, this is a large page"), the levels are all identical layouts.

And a second thing is the existence of Arm Morello as an implementation that supports the CHERI capabilities model (effectively 129 bit pointers consisting of a hidden "is a valid pointer" bit, then 64 bits used for compressed bounds, permissions and an object type field, 64 bits for an address). If Morello demonstrates that CHERI capabilities can be made to work well and have significant benefits while not hurting existing code, then Intel or AMD may well want to expand chapter 6 of the CHERI paper into a full design.