LWN: Comments on "Pointer tagging for x86 systems"

Pointer tagging for x86 systems

cavok — Wed, 27 Apr 2022 08:35:54 +0000

Wouldn't all this pointer tagging affect address randomization as well?

Pointer tagging for x86 systems

mrugiero — Thu, 07 Apr 2022 14:35:01 +0000

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

why not use low bit instead ?

anton — Wed, 06 Apr 2022 06:51:50 +0000

In many cases you know when using the address what the tag is, and then you can just use an offset at no or very low extra cost. E.g., if tag 3 means that we have a pointer to a cons cell, then car (aka head) accesses the machine word at offset -3, while cdr (tail) accesses the word at offset 5.

Low-bit tagging is used when 3, maybe 4 bits of tags are enough. If you need more, it becomes impractical, and you use high-bit tagging.

why not use low bit instead ?

dcoutts — Mon, 04 Apr 2022 12:01:23 +0000

Indeed, it would be a nightmare in C. I guess it'd be doable in C++.

This hardware feature is for almost certainly for performance though, not convenience. My guess is that it's primarily aimed at JVMs and similar.

I don't know for sure, but I'd guess that doing pointer tagging in software (and thus having to untag before dereferencing) is cheaper to do for the low bits than the high bits. That is, cheaper in terms of the extra instructions and their sizes. But then when doing it in hardware, a hardware impl can do it cheaply either way, and given that there's more bits available at the high end, it makes sense to use the high bits.

why not use low bit instead ?

mathstuf — Sun, 03 Apr 2022 12:08:40 +0000

That's fine in a language which hides raw pointers from you in the first place. I think I'd prefer using the upper bits in C if the CPU had support for ignoring them for me rather than asking "umm, did I remember to mask this out properly?" before any pointer dereference.

why not use low bit instead ?

dcoutts — Sun, 03 Apr 2022 09:57:57 +0000

This is exactly how GHC's pointer tagging works.

https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts...

why not use low bit instead ?

marcH — Fri, 01 Apr 2022 08:13:09 +0000

> After all unaligned accesses are not supported anymore

Says who?

> so all pointers start with 3 zero bits.

Yes as long as you use only 64 bits values.

Pointer tagging for x86 systems

marcH — Fri, 01 Apr 2022 08:07:57 +0000

> It sounds like a recipe for ongoing security problems, ...
> ....
> In the early days of Linux, kernel developers had to adapt to whatever the hardware manufacturers put out; the alternative was to not have hardware to run on at all. In 2022, though, those developers feel more confident in their ability to reject support for hardware features that, for whatever reason, they feel do not fit in well with the design of the system.

In the early days, software developers trusted CPU designs. Sure there were a couple bugs now and then but nothing huge. Then came spectre and friends...

Pointer tagging for x86 systems

ecm — Fri, 01 Apr 2022 07:57:07 +0000

While jl may work to branch depending on the most significant bit, the idiomatic choice is js/jns, "jump if (not) sign bit set".

Pointer tagging for x86 systems

azz — Fri, 01 Apr 2022 01:02:01 +0000

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...

why not use low bit instead ?

neilbrown — Wed, 30 Mar 2022 23:25:59 +0000

When accessing a single-byte (e.g. ASCII character) the low bit is a meaningful bit.

why not use low bit instead ?

mathstuf — Wed, 30 Mar 2022 17:17:30 +0000

That means you need to manually mask off the bits before any actual dereference instead of the hardware supporting "I ignore the upper bits" support.

why not use low bit instead ?

ballombe — Wed, 30 Mar 2022 16:00:29 +0000

Why not use low bit instead ?
After all unaligned accesses are not supported anymore so all pointers start with 3 zero bits.

Pointer tagging for x86 systems

BenHutchings — Wed, 30 Mar 2022 15:12:22 +0000

With UAI enabled the critiical bit becomes bit 56, not bit 63. All the existing checks - which could be written as (long)addr & BIT(63), or (long)addr < 0, or even implemented in assembly - would need to be updated.

Pointer tagging for x86 systems

farnz — Wed, 30 Mar 2022 13:59:36 +0000

If we change future CPUs to have a fast bt, then yes, we can use it instead of the test instruction that's faster on AMD EPYC processors.

But if we change UAI to not use bit 63 as part of the tag, then we could avoid the whole problem, too. And given that both Intel and AMD have changed from having bt reg, imm be as fast as test reg, reg to having test reg, reg be faster than bt reg, imm, I think a fix to UAI is almost certainly the simpler route.

This is especially true because UAI is the new thing - if making bt fast was worthwhile for things other than bt, then we'd have done it already. Making test reg, reg fast is worthwhile because it's a common idiom used by compilers for testing the relationship between a register and 0, so having it be fast speeds up other code.

Plus, your example code bt reg, 47 is buggy in its own right if AMD ever implement 5-level paging, and is buggy on Intel chips that exist today with 5 level paging. And, on top of that, if AMD do implement 5 level paging, UAI would leave no bit that can be uniquely used to distinguish kernel and user addresses, so there's no way to make the bt solution work reliably (with 5 level paging, bits 56 to 0 are VA bits, leaving 7 bits at bit 57 to 63 not translated, but UAI permits userspace processes to convert bits 63 to 56 into tag bits). Intel, at least, left bit 63 spare, and said that you get 6 tag bits with 5 level paging, or 15 with 4 level.

Pointer tagging for x86 systems

adobriyan — Wed, 30 Mar 2022 13:51:21 +0000

"test rax, rax; js" is smaller than "bt rax, 47; jc"

0000000000000000 <f>:
0: 48 85 c0 test rax,rax
3: 48 0f ba e0 3f bt rax,0x3f

Pointer tagging for x86 systems

khim — Wed, 30 Mar 2022 10:21:14 +0000

I'm not asking about why you would use 63th bit instead of 47th if you have a choice.

But we are discussing here AMD-only features and you say that one would need to free up a register, or accept the slowdown from accessing memory. That's not true. If these future CPUs have fast enough bt then there would be no slowdown (at least if that would be CPU-specific kernel build which is often acceptable for servers or things like ChromeOS).

Yes, you probably couldn't build an universal kernel which is both supporting UAI and Intel CPUs, but that's another, separate, issue.

Pointer tagging for x86 systems

farnz — Wed, 30 Mar 2022 08:33:50 +0000

Because test is friendlier to the OoOE machinery on modern CPUs than bt, and hence faster to execute. As this is pure overhead in the absence of bugs and/or malicious code attacking the kernel, we want it to be as lightweight as possible so as to spend more CPU resource doing useful work, and less CPU resource validating that userspace hasn't gone insane.

Using Agner's instruction table PDF, test reg, reg has had a lower reciprocal throughput than bt reg, imm since IvyBridge on Intel's high performance side, and since Intel Haswell processors, up until the latest Xeons, can be executed on more execution ports than bt reg,imm. On the low power Intel side (Atom from Silvermont onwards), test reg, reg takes one execution unit instead of both on Silvermont, and has 3x the throughput on Goldmont.

On the AMD side, test reg, reg becomes higher throughput than bt reg, imm in Excavator cores, returns to be equally cheap for Zen 1 and Zen 2, and then test reg, reg becomes cheaper than bt reg, imm in Zen 3. In the low power cores (Bobcat, Jaguar), the cost is the same for either instruction.

Hence the preference for test reg, reg over bt reg, imm - there are no CPUs on Agner's list where bt is faster than test, but there are several cores, including the current high performance µarches from Intel and AMD, where test is cheaper to execute than bt.

Pointer tagging for x86 systems

khim — Tue, 29 Mar 2022 22:00:37 +0000

Why would you need test for that? Just use bt rax, 47; jc error and that's it.

Pointer tagging for x86 systems

farnz — Tue, 29 Mar 2022 16:44:14 +0000

Bit 63 of a 64 bit register is the sign bit if you're interpreting the register contents as a signed integer; it thus has special handling to make it easier to check. test rax, rax ; jl error will jump to the label error if the pointer in rax has bit 63 set. test doesn't support a 64 bit immediate, so you need to free up a register, or accept the slowdown from accessing memory, if you want to check any bits other than 63.

Pointer tagging for x86 systems

imMute — Tue, 29 Mar 2022 16:36:12 +0000

How would checking if bit 47 was set be any more expensive than checking bit 63?

Pointer tagging for x86 systems

willy — Tue, 29 Mar 2022 15:11:00 +0000

But the Mill is legit crazy. I forget whether they track dirtiness on a per byte or per bit level, but that level of detail in tracking dirtiness can only hurt. If anything, we should track dirtiness at a super-cache-line level and move things around in a group of two or four cache lines. Of course, that comes with a false sharing problem, which is why it hasn't happened yet.

There's always trade-offs and people can have a real conversation about whether 32, 64 or 128 bytes is the correct size of a cache line, but there's a knee to this curve and 1-4 bytes is outside the scope of sane conversation.

Pointer tagging for x86 systems

farnz — Tue, 29 Mar 2022 13:24:21 +0000

CHERI has a decent chance, because it's designed to let you have a "legacy" capability that gives code all the permissions it had before CHERI came into existence; the theory is that you'll start your porting with all of the kernel and userspace pointers living in the legacy capability, and then gradually narrow things down over time, rather than having to do a big bang port. The idea is that you can put capabilities in place at the edges, and move inwards over time, to have a tiny trustworthy core that has "full" capabilities, and that simply restricts the capabilities on offer as you head further from the core.

One more thing I'd add to your Itanium example; the simulations that justified Itanium's design compared hand-written "perfect" Itanium code to current compiler output for x86. With hindsight, the thing that they could easily have seen up-front and didn't spot is that the compiler improvements needed for EPIC also improved performance of compiled code for OoOE, and thus their predicted performance advantage wasn't nearly as good as it could be because OoOE also benefited from their compiler improvements.

Pointer tagging for x86 systems

jem — Tue, 29 Mar 2022 12:33:22 +0000

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

james — Tue, 29 Mar 2022 10:38:26 +0000

The big problem with "next" architectures is that they don't have access to all the decades of experience conventional architectures do, but the first generation is expected to be at least competitive. If the general conclusion is that "this would be good if they changed x, y and z", it's probably too late (especially if changing those features can't be done while keeping compatibility). I'm hoping that ARM has learnt that lesson and aren't trying to productise CHERI too soon.

Examples
Take MIPS and SPARC as successful "next" architectures -- tremendously influential, but with a number of features which later RISC designs dropped.

i432 -- Bob Colwell (one of the lead designers of the Pentium Pro and Pentium 4) is fascinating on the subject: he says that both hardware and software engineers dropped the ball on performance. If they hadn't -- if they'd got to within 50% of competitive on performance, with security and reliability improvements, there would have been a market for the chip.

Itanium -- the big lesson they should have learnt before they ploughed billions into hardware and software is "can we actually provide compilers that do what we say they can", but it's at least arguable there were other mistakes. I seem to remember that when compilers scheduled Itanium programs, they used cycle timings from the current processors -- in particular, fast level 1 cache. That meant that a (theoretical) high-clocking Itanium with caches that were slower in terms of cycles (but not in nanoseconds) would spend a disproportionate amount of time waiting for data from cache when running existing binaries, so Intel didn't produce a system like that.

I really don't think that Alpha counts as "next" for anything other than performance -- and dominating the CPU performance tables throughout the 1990s, then getting dropped for business reasons, doesn't exactly count as an engineering failure.

Pointer tagging for x86 systems

farnz — Tue, 29 Mar 2022 09:31:43 +0000

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.

Pointer tagging for x86 systems

wtarreau — Tue, 29 Mar 2022 06:07:26 +0000

> 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

pabs — Tue, 29 Mar 2022 05:03:50 +0000

Is there any prospect of Mill resulting in some gateware or hardware that people can use? Or will it remain something that doesn't exist outside the designers minds, talks, documentation and patents?

Pointer tagging for x86 systems

willy — Tue, 29 Mar 2022 03:10:09 +0000

Do you have experience in CPU design?

Pointer tagging for x86 systems

mtaht — Tue, 29 Mar 2022 03:01:52 +0000

Everywhere I turn I see portions of the ideas that were in the mill computer's far more unified versions, gradually being retrofitted into existing architectures.

I wish they'd build it, even just as a virtual machine. It would help people to think better about where we should have started going in the 90s, especially securitywise, when it came to cpu architectures.

Take out some popcorn and watch their talk about security... https://millcomputing.com/docs/#security

Pointer tagging for x86 systems

dullfire — Mon, 28 Mar 2022 23:36:25 +0000

That would add significant overhead to basically all code paths that need to check a pointers validity

(to be clear: any overhead to those code paths will be significant)

Pointer tagging for x86 systems

dullfire — Mon, 28 Mar 2022 23:33:12 +0000

Maybe you should take another look at protected mode segmentation then.

It's very very much like a capabilities bases permissions system (and very very much unlike the 8086 segmentation that was only for getting around the 16-bit limit).

Pointer tagging for x86 systems

jrtc27 — Mon, 28 Mar 2022 23:21:17 +0000

> x86-CFI, ARM memory tagging extensions and CHERI

CHERI is not like the other two, it *is* full capability-based addressing; the C stands for Capability

Pointer tagging for x86 systems

Paf — Mon, 28 Mar 2022 22:39:24 +0000

You know, “next” architectures have been tried before - several times, including with huge amounts of $$$ behind them (Alpha, Itanic, others). For the last few decades at least, they’ve been losing out to extensions/cleanups of the existing models.

It’s not obvious to me these thoughts about addressing will be different.

Pointer tagging for x86 systems

Paf — Mon, 28 Mar 2022 22:35:09 +0000

I think his point is basically “doesn’t this also mess up Windows? Who on earth *was* it designed for?”

Pointer tagging for x86 systems

JoeBuck — Mon, 28 Mar 2022 22:11:02 +0000

Perhaps the most fundamental of those is that UAI allows the most-significant bit of the address to be used by user space. In current systems, only kernel-space addresses have that bit set. Turning on UAI would allow user space to create pointer values that look like kernel addresses, but which would actually be valid user-space pointers.

Couldn't this be changed so that the most significant non-UAI bit, instead of the most significant bit, would be used to distinguish kernel addresses?

Pointer tagging for x86 systems

abufrejoval — Mon, 28 Mar 2022 22:05:46 +0000

While I do agree with you in a way, this topic keeps reminding me of the climate change debate: we all know something needs to be done, but nobody seems to work on solutions with the proper level of forward looking research.

And we should at least invest into making sure that new code can be written without fully qualified pointers (somewhat like Rust vs. Cx).

Finding ways to defuse pointers seems pretty easy compared to saving the planet, especially when potential architectures have already been proposed decades ago...

Pointer tagging for x86 systems

abufrejoval — Mon, 28 Mar 2022 21:58:41 +0000

Please leave the Intel box: the PDP-11 (and many others) was segmented, long before the 8086 did it with a static offset.

But generally speaking the old guys in the 1960's were much less restrained by todays VAX legacy and had some pretty cool ideas (and implementations like the IBM i-Series). There is a lot of inspiration to be found by looking back at what they had theorized on and implemented back then.

Please note that capability based security is finding its way back in projects like Google's Fuchsia and many others really concerned about the long term viability of the von Neumann/Princeton memory model.

Pointer tagging for x86 systems

calumapplepie — Mon, 28 Mar 2022 21:48:30 +0000

I'm not worried about the legacy added by these new measures: we'll need a whole new architecture for (insert new memory addressing scheme here), which means we can ignore most portability problems. Since apps already have to account for systems that don't support this newfangled technology anyways, and porting to an entirely new addressing scheme will probably require work for any application doing low-level shenanigans like memory tagging, it's not like this hurts anything.

Besides, inventing a new magic CPU architecture that fixes all our problems will take years. In the meantime, lets try and use the stopgap measures to get as much performance and power efficiency as we can.

Pointer tagging for x86 systems

dullfire — Mon, 28 Mar 2022 21:42:24 +0000

> ultimately capability based addressing or something similar needs to break these PDP/VAX based notions of a fully qualified global shared address space.

you mean you want x86 segmentation fully reinstated for AMD64?