[Cryptography] Oracle archeologists discover memory tagging

[Henry Baker]

At 01:40 AM 10/29/2015, John Gilmore wrote:
>> Apparently, Oracle has been doing archeology research on old Burroughs...:
>
>What Oracle (Sun) has done here is quite a bit different from the Burroughs tagged memory.
>
>Here's a developer tip on how it works:
>
>https://community.oracle.com/docs/DOC-912448
>
>The hardware is storing an extra software-controlled 4-bit value along with each 64-byte cache line in main memory.
>
>When enabled, hardware compares this value to the top bits of the address being used to access the memory, and faults if they don't match.
>
>This is an interesting use of the copious spare bits available in 64-bit addresses.
>
>It requires an extra ~1% of main memory and cache memory width, and probably some extra pins on the processor.
>
>Oracle enables this feature using surprisingly simple modifications to malloc(), so that adjacent objects (and objects re-allocated on top of freed objects) are always 64-byte aligned and always get a different 4-bit tag.
>
>User programs can write these memory tags.
>
>Of course, not every object will have its own tag (there are only 13 tags available) so a wild access has a 12-in-13 chance of faulting -- still vastly better odds than without this feature.
>
>This works even with old binaries, since they link with the new malloc.
>
>If the memory-tag-writing overhead is low enough, the compiler could also generate code in new programs to do the same thing with each stack frame (giving each frame (one or more) tags different from adjacent frames).
>
>By contrast, old Burroughs system memory tagged each 48-bit memory word based on what kind of data it contained (for a small number of kinds defined specifically by hardware).
>
>E.g. all data words in all objects had tag 0, whereas array descriptors had tag 3.
>
>The tags were not checked against bits in the address used to access them, but instead against the type of instruction used to access them.
>
>User programs could not change these tags.
>
>This did not provide protection against pointers accessing data from outside their arrays, which is what the Sun/Oracle feature is designed to do.
>
>(That was done by a separate descriptor mechanism in Burroughs machines, unrelated to the tagged memory.)

The reason I mentioned the MIT Lisp Machine is that Lisp implementations have exhaustively explored essentially every method of memory tagging, including the use of caches.

For example, MIT's Maclisp segregated objects of the same type onto the same "pages"; a table lookup of the top address bits would tell you the type of the object.  This scheme is still used by GCL (nee KCL), I believe.

Additional tagging schemes were explored by the various Xerox Lisp machines, including various kinds of hash tables & caches.

And then there was the Intel iAPX_432, Justin Rattner's attempt at the implementation in real-time of every academic architectural wet dream fad, including object orientation.

IBM's 360/370 systems also offered various kinds of "protection" schemes, including additional bits for each 2k (?) byte block in memory; I believe that these IBM protection schemes were also respected by the I/O controllers -- perhaps the first time that asynchronous & independent I/O devices could be locked out of protected main memory.

----
Accessing Lisp Machine vectors from *outside* the vector was not only permitted; it was a *feature*.  By construction, a Lisp Machine vector was *simultaneously* a sequentially-allocated vector and a "linked list".  Therefore, the "tail" of such a vector could be accessed and passed as a vector-cum-linked-list.  The garbage collector noticed when the "head" of such a vector was no longer referenced, and shortened the vector during GC operation.

Thus, the Lisp Machine operated in a completely type-safe & memory-safe manner -- something that the Oracle technology still can't achieve.