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.
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).
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.
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.
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 ;-)
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 :)
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.
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).
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.
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?
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.
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...
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.
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").
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...
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).
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.
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.
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.
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.
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.
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.
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.
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?
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.
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.)
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.
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.
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)
> .. The 68000 only had 24 address lines after all. This allowed a maximum of 16Mb of RAM ..
And now we need 16GB to do exactly the same thing! Long ago I made my own DOS/Netscape image that ran from a 1MB 3 1/4 inch floppy that did the exact same thing! It booted and loaded a compressed ramdisk into memory and ran from there.
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.
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
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.)
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.
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?")
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.
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.
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.
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.
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.
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.
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.
70 comments
[ 3.4 ms ] story [ 140 ms ] threadEg. 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.
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.
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.
I'm pretty sure this memory extension doesn't affect uniqueness of pointers... that would indeed break a lot of software ;-)
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 :)
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.
Std::set uses it of course.
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.
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").
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
Anyone needs more than 256 Terabytes of RAM?
In any case, I'd be quite surprised to see a 64-bit CPU doing such heavy lifting in 2040.
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.
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.
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.
EDIT: My math is bad, see comments below.
I can unsarcastically say that no one will ever need full 64bit addresses on this planet.
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)
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.
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.
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.
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)
And now we need 16GB to do exactly the same thing! Long ago I made my own DOS/Netscape image that ran from a 1MB 3 1/4 inch floppy that did the exact same thing! It booted and loaded a compressed ramdisk into memory and ran from there.
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
https://vimeo.com/366246134
https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
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.
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?")
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.
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.
Emacs Lisp is an example; here's its tagging apparatus.
https://git.savannah.gnu.org/cgit/emacs.git/tree/src/lisp.h#...
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.
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.
https://www.usenix.org/system/files/login/articles/login_sum...
https://www.kernel.org/doc/html/latest/core-api/protection-k...
Google plans to eventually make MTE a compulsory feature.
https://source.android.com/devices/tech/debug/tagged-pointer...