News for hackers. Stuff that matters.
Re:The Arm64 memory tagging extension in Linux by cesaref on Monday October 19, 2020 @08:15AM (#24825617)
Not sure if this has been mentioned, but this exact technique (storing extra data in addresses) was used in the early days of the MacOS, with 24 bits for the address, and 8 bits for extra info (not sure if I can remember exactly what they were for). The 68000 only had 24 address lines after all. This allowed a maximum of 16Mb of RAM which was of course far more than would ever be in a computer...

By the time the Mac II came out (68020 with 32 bit address bus), it was apparent that this was going to be an issue, and there was an effort to remove this logic. Those early machines were a combination of ROM and loaded OSes, so there was an effort to clean the code for both the distributed OS and the stuff included in the ROMs of the machines.

I think if memory serves the Mac IIcx from around '89 or so was the first machine with 32 bit clean roms, and with the right OS version you were good for >16mb of RAM.

I've also got a hazy memory of some architecture (i'm going to guess DEC Alpha) which only read from 32 bit boundaries, and where the bottom 2 bits of the address were masked out, so you could store data there too...

Anyhow, the real take home from all that was that misusing addresses to store additional information, which might seem like a clever trick is likely to bite you at some point in the future.

Re:The Arm64 memory tagging extension in Linux by Someone on Monday October 19, 2020 @09:35AM (#24826215)
The extra bits stored flags that indicated whether handles were movable, could be purged at will, or came from a resource (on disk)

IIRC Excel went a bit further by using the leftover bits and even bit(s) starting at bit 24. That worked until hardware stopped wrapping around memory. Apple created a launch error “program had special memory requirements” which actually meant “this is Excel version so-and-so”.

And yes, that can bite you in the future, but the gains today can (appear to) outweigh that.

It also is perfectly valid when you control both the side that determines the constraints and the side that runs extremely close to them. For example, Cocoa’s tagged pointers (https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-bui...) are fine, given that Apple both controlled the memory allocator and the library assuming it aligned allocations (they also are safer in that they won’t try to read from addresses that don’t point to valid memory. That’s essential for their use)

Re:The Arm64 memory tagging extension in Linux by Dylan16807 on Wednesday October 21, 2020 @01:52PM (#24850312)
The biggest problem there was programs hiding away state and then not masking it out when using the addresses. This meant they couldn't just use the lower part of memory on new chips, they were completely incompatible. The lesson has been learned from that, and CPUs don't ignore reserved bits.

But also this is a hardware feature so the code will continue to be compatible anyway.

Even if this acts like a permanent truncation of the address space by 4 bits, so what? If you think you can keep Moore's law going strongly enough to hit that cap, you're probably going to hit the 64 bit wall soon enough after; might as well focus on that shift to 128 bit addresses

Re:The Arm64 memory tagging extension in Linux by rjsw on Monday October 19, 2020 @08:34AM (#24825738)
The Mac IIci was the first 32 bit clean machine.

Plenty of dynamically typed languages have used the bottom bits in an address to store tags. You have two available on a 32 bit machine, three on 64 bit. The SPARCv7 has instructions that will do arithmetic on tagged values.

Re:The Arm64 memory tagging extension in Linux by jacobush on Monday October 19, 2020 @10:48AM (#24826865)
AmigaBASIC
Re:The Arm64 memory tagging extension in Linux by kjs3 on Monday October 19, 2020 @12:52PM (#24828184)
While conceptually similar (and made me think of the same thing), this doesn't really look like the same thing. In the Mac case, it was (ab)using technically unused addressed bits in unintended ways. In the ARM case, it is an explicit architectural feature. More like pointer tags in Lisp machines.
Re:The Arm64 memory tagging extension in Linux by crocktucker on Monday October 19, 2020 @09:26AM (#24826136)
" ... if memory serves ... ", well done.
Re:The Arm64 memory tagging extension in Linux by shard on Monday October 19, 2020 @02:16PM (#24829160)
Here is a Google engineer explaining how memory tagging extension works in more detail in a white paper. According to the paper, about 2/3 of all CVEs are memory safety bugs, and memory tagging will help with catching undiscovered ones.

https://www.usenix.org/system/files/login/articles/login_sum...

Re:The Arm64 memory tagging extension in Linux by pjmlp on Monday October 19, 2020 @05:26PM (#24831214)
It does, as proven by Solaris on SPARC ADI, a similar technic with almost one decade of use by now.
Re:The Arm64 memory tagging extension in Linux by londons_explore on Monday October 19, 2020 @06:28AM (#24824962)
4 bit keys seems a bit limiting... I could imagine lots of scenarios where a 1 in 16 chance of an exploit succeeding is still a big issue...
Re:The Arm64 memory tagging extension in Linux by flohofwoe on Monday October 19, 2020 @06:49AM (#24825066)
IMHO it's less of a security feature, and more of a debugging aid (the overlap with security is when a failed check causes program termination). You might get more fine-grained overflow checks (vs guard pages), or dangling pointer checks (depending on how that key is stored, e.g. more than one key per memory page?).

It's faster then doing the same in code (e.g. via 'tagged handles': https://floooh.github.io/2018/06/17/handles-vs-pointers.html), or memory debugging tools like Valgrind or clang ASAN (and unlike Valgrind or ASAN, the checks are always enabled, also in the "release version").

Re:The Arm64 memory tagging extension in Linux by robocat on Monday October 19, 2020 @03:49PM (#24830176)
In the most extremely sensitive environments:

1. It still helps with defence in depth

2. The threat of detection prevents attackers that need 100% stealth

3. Failures are likely to be detected which is still valuable as you can now mitigate damage

4. Failures are likely to be detected which helps get software faults fixed - which allows the ecology of security to improve over time

Re:The Arm64 memory tagging extension in Linux by londons_explore on Monday October 19, 2020 @06:30AM (#24824971)
It's a shame we're using the top of pointers for other data... It's almost as if we didn't learn from the "3gb memory hole", the "gate a20 memory limit", and countless other times when using special address bits came back to bite system designers as RAM got bigger...
Re:The Arm64 memory tagging extension in Linux by flohofwoe on Monday October 19, 2020 @06:37AM (#24825007)
Is this really still a problem with virtual memory management? The virtual address space size could be a property of the process (e.g. 48 bits vs the full 64 bits). The vast majority of applications today doesn't even need more than 32-bits of address space and could use the top 32-bits for something else if the memory mapping hardware ignores the unused bits).
Re:The Arm64 memory tagging extension in Linux by five-robert on Monday October 19, 2020 @07:04AM (#24825159)
2^48 == 256TB.

Anyone needs more than 256 Terabytes of RAM?

Re:The Arm64 memory tagging extension in Linux by jcranmer on Monday October 19, 2020 @01:20PM (#24828544)
It's 256TiB of virtual address space. If you include NVMe drives memory-mapped into the address space, hitting that cap is not entirely unreasonable.

Intel added support for 5-level page tables (bumping virtual memory to 2^57 bytes) a few years ago: https://en.wikipedia.org/wiki/Intel_5-level_paging.

Re:The Arm64 memory tagging extension in Linux by nnx on Monday October 19, 2020 @08:15AM (#24825615)
Note this is for the virtual address space, not only for actual physical RAM. Having 256TB mmap’ed (to another kind of storage) does not seems totally out of reach.
Re:The Arm64 memory tagging extension in Linux by ljhsiung on Monday October 19, 2020 @10:45AM (#24826834)
True, but also note that a 52b mode (i.e. 12 bit tag) is also supported.

I can't imagine anyone needing more than 4PB in the next 30 years, and the security gains now is (in my opinion) worth the potential refactoring in 30+ years that would be required.

Re:The Arm64 memory tagging extension in Linux by StillBored on Monday October 19, 2020 @12:06PM (#24827673)
The couple year old power9 E980, can take 64T of ram. So there are people who have problems that need lots of addressable memory today.

Even so, it wouldn't be that hard to actually build a system that could in theory try and map 4PB of storage via mmap today, its about 1/2 a rack of fairly common equipment. Given there are various companies selling 50T ssd (https://www.anandtech.com/show/11639/viking-ships-uhcsilo-ss...) its probably possible to do it in under 10U.

Re:The Arm64 memory tagging extension in Linux by guenthert on Monday October 19, 2020 @12:58PM (#24828274)
Hmmh? A few years ago there were already a few sites with more than a PiB of storage total. I don't know of any which used some virtual memory or single address space scheme to access those, but I wouldn't want to rule it out.
Re:The Arm64 memory tagging extension in Linux by saagarjha on Monday October 19, 2020 @10:09AM (#24826495)
And in fact support for 5-level page tables was recently merged into the Linux kernel because people were coming close to this limit and needed more virtual address space.
Re:The Arm64 memory tagging extension in Linux by tpxl on Monday October 19, 2020 @08:08AM (#24825569)
I am flirting with the idea of having 1TB of RAM on my servers as a small start-up. Having 256TB in 20 years seems reasonable.
Re:The Arm64 memory tagging extension in Linux by bitwize on Monday October 19, 2020 @08:57AM (#24825884)
You're gonna need at least that much to run the Electron apps of 20 years from now...
Re:The Arm64 memory tagging extension in Linux by rbanffy on Monday October 19, 2020 @12:53PM (#24828200)
A 128-bit CPU is not something I'd find outlandish in 20 years. OTOH, I was reading my e-mail on a 64-bit workstation (largely by accident, but still).

In any case, I'd be quite surprised to see a 64-bit CPU doing such heavy lifting in 2040.

Re:The Arm64 memory tagging extension in Linux by cptnapalm on Monday October 19, 2020 @10:07AM (#24826474)
A Javascript website has entered the chat
Re:The Arm64 memory tagging extension in Linux by throwaway2048 on Monday October 19, 2020 @07:26AM (#24825303)
It ought to be enough for anyone
Re:The Arm64 memory tagging extension in Linux by sherincall on Monday October 19, 2020 @07:05AM (#24825167)
The estimated number of atoms on earth is on the order of 1e50, which is 60 bits. If you take the 4 bits out of the 64bit address for tagging, you can still address individual atoms.

EDIT: My math is bad, see comments below.

I can unsarcastically say that no one will ever need full 64bit addresses on this planet.

Re:The Arm64 memory tagging extension in Linux by five-robert on Monday October 19, 2020 @07:11AM (#24825206)
2^66 bits - estimated storage space at Google data warehouse as of 2013 [0]

2^71 bits - total hard drive capacity shipped in 2016 [0]

I doubt your calculations.

[0] https://en.wikipedia.org/wiki/Orders_of_magnitude_(data)

Re:The Arm64 memory tagging extension in Linux by sherincall on Monday October 19, 2020 @07:25AM (#24825296)
Yes, you're totally right, my math is way off.
Re:The Arm64 memory tagging extension in Linux by jmgao on Monday October 19, 2020 @07:22AM (#24825283)
10^50 is definitely not 60 bits: log_2(10^50) = 50 * log_2(10), and log_2(10) > 3
Re:The Arm64 memory tagging extension in Linux by pjmlp on Monday October 19, 2020 @05:25PM (#24831202)
They are ignoring Android here as customer of the Linux kernel.

Google plans to eventually make MTE a compulsory feature.

https://source.android.com/devices/tech/debug/tagged-pointer...

Re:The Arm64 memory tagging extension in Linux by londons_explore on Monday October 19, 2020 @06:22AM (#24824931)
How does this impact software that does memory pointer comparisons?

Eg. Store pointers to all these objects into a std::set? The memory tag will now form part of the keys to this set, and would affect iteration order etc... It could cause breakage in existing applications.

Re:The Arm64 memory tagging extension in Linux by flohofwoe on Monday October 19, 2020 @06:42AM (#24825035)
Memory allocators are already returning more or less "random" pointers, so using pointers for sorting is already a bad idea. Even using pointers for equality-comparison isn't usually a good idea because the same memory location might be reused when the allocator recycles memory (those tags could actually help with making such "recycled" pointers unique over time).
Re:The Arm64 memory tagging extension in Linux by jackewiehose on Monday October 19, 2020 @08:02AM (#24825532)
Using pointers for sorting is fine as long as you don't care about the order (parent referenced std::set and it's not uncommon to use a set of pointers if you just want to store some objects). Likewise it's fine to use pointers for equality-comparisons as long as the pointer is valid (of course you have to dismiss the pointer when the memory is freed).

I'm pretty sure this memory extension doesn't affect uniqueness of pointers... that would indeed break a lot of software ;-)

Re:The Arm64 memory tagging extension in Linux by flohofwoe on Monday October 19, 2020 @10:24AM (#24826638)
> uniqueness of pointers...

What I mean is for example: you get a pointer by allocating memory, then free that memory, then you allocate again and get a pointer to the same memory location. Without a tag those two pointers would be equal, even though they come from separate memory allocations. This can be a source of bugs if the pointer is also used as some sort of object id, and I know that at least I stumbled over this embarrassing problem more than once in C++ until I switched to tagged handles :)

Re:The Arm64 memory tagging extension in Linux by jackewiehose on Monday October 19, 2020 @11:12AM (#24827073)
You can use the pointer as an object id, but only for living objects. The pointer becomes invalid the moment the memory is freed. Your bug was that you used an invalid pointer.
Re:The Arm64 memory tagging extension in Linux by Matt3o12_ on Monday October 19, 2020 @11:49AM (#24827450)
But doesn't this feature exactly help with this bug? Two memory allocations should now return different pointers (because the MTE nibble is different) therefore the comparision should fail. Unless ofcourse the application was using this undefined behavior (which would be very buggy since malloc can randomly refuse to reuse the same address even though it was freed and therefore create extremely hard and difficult to track bugs).
Re:The Arm64 memory tagging extension in Linux by flohofwoe on Monday October 19, 2020 @12:00PM (#24827603)
> Your bug was that you used an invalid pointer.

Exactly, but just declaring that a pointer is "invalid" doesn't help much with debugging such dangling pointer problems, while tagged pointers do.

It's not like an "invalid pointer" is any different from a "valid pointer" when you look at it. With the extra tag bits, an invalid pointer can actually be identified as such.

Re:The Arm64 memory tagging extension in Linux by sherincall on Monday October 19, 2020 @07:08AM (#24825187)
Be that as it may, existing software that used to work will no longer work, and the developers might not be around/able to fix it.

There are also cases of custom suballocators or arrays of objects - Looking at an address makes it possibly to figure out which array it belongs to. This code would break.

Granted, it would still be possible to do all this if you just mask off the tag bits, but it requires a software change.

Re:The Arm64 memory tagging extension in Linux by pm215 on Monday October 19, 2020 @07:27AM (#24825312)
The "suballocate out of some arrays" code should not break, because the whole array would be allocated at once and so would have the same tag for the whole range. Code that does a simple "is this pointer value inside the "array_base + size" range" continues to work, because array_base has whatever tag malloc() handed out for that array, and so do the pointer values that the suballocator handed out. I think for MTE to break your code you would have to be doing some pretty weird stuff with pointer arithmetic (beyond just the usual "technically maybe this is undefined behaviour but it works" level stuff).

It's always the case that some software that does things that are not valid-by-the-language-standard might break if run on a newer version of the OS or a newer system library version (remember the big flap about glibc memcpy() changing its behaviour when called for overlapping regions?). You don't want to break lots of software gratuitously, but sometimes the tradeoff is worth making.

Re:The Arm64 memory tagging extension in Linux by enedil on Monday October 19, 2020 @09:48AM (#24826317)
Comparing pointers not coming from the same allocation is undefined behaviour per C++ standard.
Re:The Arm64 memory tagging extension in Linux by gpderetta on Monday October 19, 2020 @11:13AM (#24827081)
... unless you use std::less and friends which guarantees an unspecified total order among all pointers of the same type.

Std::set uses it of course.

Re:The Arm64 memory tagging extension in Linux by jpcooper on Monday October 19, 2020 @06:33AM (#24824988)
So a key is stored in the unused portion of memory pointers which should match the key associated to the memory it points to. I couldn’t figure out from the article where the key is stored in the corresponding memory. Can anyone explain?
Re:The Arm64 memory tagging extension in Linux by pm215 on Monday October 19, 2020 @07:16AM (#24825244)
mwsealey's comment on the LWN article (in response to somebody asking that question there) has a good explanation of it. Basically exactly where the keys are stored is up to the implementation, but one reasonable implementation is for the memory controller to put them in the top part of the system DRAM (which is then not made available as 'normal' RAM). Architecturally the allocation tag space is entirely separate from system memory, though, and the only way to get at it is with the provided instructions for reading/writing tags, so any particular implementation can put any kind of storage it likes underneath. (A software model, for instance, might just allocate a separate lump of host RAM for storing the tags. QEMU's MTE emulation does that.)
Re:The Arm64 memory tagging extension in Linux by jpcooper on Monday October 19, 2020 @08:30AM (#24825713)
Thanks for the explanation.
Re:The Arm64 memory tagging extension in Linux by Symmetry on Monday October 19, 2020 @06:37AM (#24825012)
I'd assume the key is stored in the hardware memory translation structures like the TLB.
Re:The Arm64 memory tagging extension in Linux by rjsw on Monday October 19, 2020 @08:40AM (#24825765)
It doesn't look like it to me.

I did propose storing type values in a TLB a long time ago but haven't run any simulations for it. Had started building some hardware to do type checking on an Atari ST but didn't finish it.

Re:The Arm64 memory tagging extension in Linux by londons_explore on Monday October 19, 2020 @06:27AM (#24824955)
Random read and write of a big memory region could now presumably cause double the number of DRAM accesses, and half the performance, since the tag mapping will need to be read in addition to the actual data. If the read of a memory address could have side effects (as is common with memory mapped hardware), does the hardware give guarantees that the tag will be checked before the memory is read or written? If so, that'll be an even bigger performance hit...
Re:The Arm64 memory tagging extension in Linux by bitwize on Monday October 19, 2020 @08:50AM (#24825824)
It seems that the tag mappings will need to live in separate physical RAM, so that info could be pulled from the tagmap RAM chips at the same time as the data is pulled from the data RAM chips.

Using multiple RAM chips to increase throughput is an old computer engineering technique; it was, for instance, the entire justification for planar graphics modes in early graphics hardware.

Re:The Arm64 memory tagging extension in Linux by Retr0spectrum on Monday October 19, 2020 @12:53PM (#24828197)
You're overlooking a) existing page table lookup overhead b) hierarchical caching.
Re:The Arm64 memory tagging extension in Linux by lsllc on Monday October 19, 2020 @05:02PM (#24830991)
This sounds a bit like the pkey API and MPK (Memory Protection Keys) on more recent Intel processors.

https://www.kernel.org/doc/html/latest/core-api/protection-k...

Re:The Arm64 memory tagging extension in Linux by znpy on Monday October 19, 2020 @10:15AM (#24826543)
isn't like, memory tagging explicitly forbidden in x86-64 ?

iirc it was used in lisp compilers/interpreters to speed up object unboxing (as in answering the question: "what class does the object pointed by this pointer belong to?")

Re:The Arm64 memory tagging extension in Linux by colejohnson66 on Monday October 19, 2020 @10:38AM (#24826773)
Correct. x86-64 mandates “canonical” addresses where all the upper bits must be the same in order to dereference a pointer.[0] So on a processor with 48 physical address lines, the upper 16 must be either all set or all unset. This is obviously to prevent people using those upper bits to store extra data.

Of course, this doesn’t stop you from being able to[a], it just makes it harder.

[a]: The processor doesn’t know the “type” of a register’s value; It’s just bits. It could be a pointer, integer, floating point, etc. until you tell the processor to do something with it. So one could obviously use those extra bits to store data, then when a dereference is needed, store those bits in another register, dereference, then put the bits back. But that’s a lot of work to save a byte or two.

[0]: Intel SDM Volume 1 §3.3.7.1:

> In 64-bit mode, an address is considered to be in canonical form if address bits 63 through to the most-significant implemented bit by the microarchitecture are set to either all ones or all zeros.

Re:The Arm64 memory tagging extension in Linux by staticassertion on Monday October 19, 2020 @01:48PM (#24828829)
> But that’s a lot of work to save a byte or two.

Is it? It's something like two xors on a register. If that's a byte or two per pointer (ie: it's pointer metadata that you'd have to store anyway, which I assume is the use case) that's actually a pretty significant win, and could help reduce cache pressure, thereby buying you back the performance (and then some).

Addresses are also XOR'd all the time with a secret as a mitigation, I don't know that there's much of an impact at all.

Re:The Arm64 memory tagging extension in Linux by StillBored on Monday October 19, 2020 @11:54AM (#24827519)
And common javascript engines. Turns out a lot of interpreters hide bits away in what they precieve to be unused address bits.

Its one of those lessons that everyone seems to be constantly relearning. Address spaces grow.

One of my first "real" jobs, when this topic came up a very senior person said something to the effect. We continue to find ways to use up one of those bits roughly every year. Moving from 32-64 bit VA's is going to get beyond the end of my career but someone will have to deal with it in the future. So its a little slower than 1 bit a year, but everyone is adding a few more bits (52/56/etc) because there are actual commercial computer systems with a few tens of TB of ram today. If persistent memory ever becomes a thing, someone _WILL_ want to mmap their multi PB storage cluster, and then there will be a scramble for more address bits.

Re:The Arm64 memory tagging extension in Linux by guenthert on Monday October 19, 2020 @12:42PM (#24828063)
Value tagging may (and often does) use the lower bits to distinguish pointers from other values (integer, boolean, character, etc.) as objects are memory aligned. In those schemes the growth of the address space doesn't matter.
Re:The Arm64 memory tagging extension in Linux by monocasa on Monday October 19, 2020 @12:56PM (#24828248)
You can use the upper bits too. It's fairly common to use the top bit to discriminate between a pointer or an integer, since you can just test if the value is negative, which can be free on some architectures.
Re:The Arm64 memory tagging extension in Linux by fulafel on Monday October 19, 2020 @12:29PM (#24827916)
No, like on most other archs, people use tagged pointers in lisp and other runtimes on amd64 all the time. But the machine (like most ISAs) doesn't ignore any bits so you have to clear the tag bits before dereferencing.

You may be thinking of the fact that a full 64 bit VA space isn't supported in current implementations. But this has no impact on use of tagging compared to most other archs.

Re:The Arm64 memory tagging extension in Linux by imglorp on Monday October 19, 2020 @10:45AM (#24826831)
Absolutely, or in the low bits of word aligned pointers as someone else mentioned above.

Emacs Lisp is an example; here's its tagging apparatus.

https://git.savannah.gnu.org/cgit/emacs.git/tree/src/lisp.h#...

Re:The Arm64 memory tagging extension in Linux by londons_explore on Monday October 19, 2020 @06:23AM (#24824935)
Where are these keys stored? A 4 bit key for each 16 byte granule of memory in the system sounds substantial. Does the Linux kernel have to give the CPU a memory region to keep those mappings?
Re:The Arm64 memory tagging extension in Linux by dan-robertson on Monday October 19, 2020 @06:29AM (#24824965)
The keys are stored in the bottom nibble of the top byte of pointers (I.e. bits 56-59)
Re:The Arm64 memory tagging extension in Linux by londons_explore on Monday October 19, 2020 @06:31AM (#24824979)
Yes, but they also need to be stored somewhere else for the CPU to compare them against something... Where else are they stored...
Re:The Arm64 memory tagging extension in Linux by Liquid_Fire on Monday October 19, 2020 @06:43AM (#24825043)
It's implementation defined (by the hardware). They could be stored in a reserved part of the RAM, or you could build special RAM that can store the extra bits alongside the data, or any other compatible solution.
Re:The Arm64 memory tagging extension in Linux by swills on Monday October 19, 2020 @10:04AM (#24826437)
Re:The Arm64 memory tagging extension in Linux by saagarjha on Monday October 19, 2020 @10:06AM (#24826460)
It’s similar, but CHERI provides much stronger guarantees. (The ARM implementation will use 128-bit pointers, with the top half being used to store much more granular keys.)
Re:The Arm64 memory tagging extension in Linux by cmarinas on Monday October 19, 2020 @01:33PM (#24828682)
CHERI provides spatial protection and is very strong at this but does not handle temporal protection well (use-after-free for example). Once a pointer is given to another code entity/compartment it is hard to revoke the permission since that's tied to the (capability) pointer itself, not the memory it points to. There are workarounds but not that nice.

MTE, OTOH, was specifically designed for detecting temporal bugs. For example, a freed object has the allocation tag (stored in memory) changed by the heap allocator so that the original pointer (with the original tag) can no longer access it. Of course, the trade-off is the 4 bits per 16-byte granule that need to be stored somewhere and the probabilistic nature (1 in 16 chance of hitting it).

But I think CHERI and MTE would complement each other nicely.