The global 64-bit address space is not linear; it is an object cache addressed with an (object + offset) tuple, and if that page of the object is not cached, a microcode trap will bring it in from disk.
I’m having trouble understanding how an address could be not linear. You can view a linear address as a (page + offset) tuple. So what makes (page + offset) linear, but (object + offset) not linear?
Does the object cache prevent you from misinterpreting a number as an address? Or misinterpreting a large offset as a different object?
In most of the systems that I’ve seen along these lines, there’s a linear address space somewhere. The thing that phk is complaining about is, I believe, linear address spaces as a programmer abstraction. In particular, virtualised linear address spaces as a programmer abstraction. As a programmer, I want objects and pointers to (offsets within) objects. The fact that the hardware exposes a linear address space to me and then does a virtual-to-pseudophysical and then pseudophysical-to-virtual translation doesn’t really buy me much, other than a (quite large, power-and-performance) overhead from page-table walks and TLBs.
He’s glossing over a lot of the details though. Something needs to allocate objects. Virtualised linear address spaces make it easy to provide a separation of concerns between allocators. The hypervisor allocates pages to the VM, the VM allocates pages to the process, and a userspace malloc assigns objects to user code. If you have an object-based memory then the object allocator must be shared. This is a bit scary for security (it’s now a part of the TCB that can violate both process and VM isolation if it’s wrong) and it has to be generic. Different languages have markedly different allocation patterns and there’s a lot of performance gained by tuning an allocator.
For security, if the allocator is used across security contexts then it must also enforce temporal safety. Building a set of abstractions that make this safe is hard. Systems like the B5500 made the allocator and GC part of the OS (and made the compiler part of the TCB: you could break process isolation if you were able to run arbitrary unprivileged instructions). This comes with some overhead. Even among managed languages, it’s hard to build a GC that’s efficient for everything.
Any system that wants to build GC into its TCB needs to do one of two things:
Provide a tracing mechanism that scans all of memory.
Provide an indirection table that is used for all memory accesses.
A lot of the historic object-memory systems picked the latter and were killed by RISCy systems that didn’t because their load-to-store penalties were much higher. For CHERI, we opt for the former and have done a load of work to optimise this. Even so, we gain a huge benefit from the virtualised address space because a memory capability is relative to some specific address space and so we don’t need to scan all of physical memory (actually, physical memory + swap) to determine that there are no capabilities to an address, we ‘just’ need to scan a process’s address space (and, within that, only the pages that have had pointers stored to them, which typically ends up being around 20%). That dramatically increases revocation throughput relative to a multi-tenant single-address-space object-memory system.
Project Maxwell from Sun Labs is probably the most interesting example of a modern object memory system but it was tailored quite aggressively to Java and explicitly placed the JVM in the TCB. I don’t think you’d want to run code from two distinct security contexts in the same object memory space, even with it. In particular, Maxwell did young generation GC in the cache in hardware and provided hooks for old-generation GC in software. Every user needs to trust the software GC. A Java GC is a lot more complex than the small subset of a hypervisor that’s required to maintain page tables for tenant isolation.
Given Ada’s reputation for strong typing, handling the type information in hardware rather than in the compiler may sound strange, but there is a catch: Ada’s variant data structures can make it a pretty daunting task to figure out how big an object is and where to find things in it. Handling data+type as a unit in hardware makes that fast.
A page address is just a number, while an object has as type and a size. This means the hardware can check that the object is being used in a proper manner, and particularly that the access is not outside of the object.
The Rational R1000 looks interesting and I’d like to know more, but it’s not the only machine with this kind of addressing. I think the Burroughs B5000 did something similar, with hardware support for arrays, and the Intel iAPX 432 is another one with object-oriented memory. I’m sure the various Lisp machines also did this sort of stuff.
The C language is actually designed to work on these types of machines. If you convert a pointer to an integer then you lose some information, and can’t convert that integer back to a pointer to the same object as you started with. (Except in implementations that support that sort of conversion, of course). On the Lisp machine I think they represented C pointers as a pair of (object,offset) and converting that to an integer meant you dropped the object reference.
I have some small experience of my own with hardware-checked pointers and I think they’re great. My Scheme implementation’s runtime (Loko Scheme) runs on AMD64 with alignment checking turned on and uses the low bits in pointers for hardware-based type checking. I’ve found numerous bugs, even deep in the runtime (like in the GC), because the hardware automatically trapped a reference where it e.g. had tried to use a fixnum as a pointer to a procedure, or tried to use a vector as a pair. Without the hardware checking these things for free on each memory reference, it would have corrupted some memory or read from some weird location, and crashed much later in some incomprehensible manner. (It’s only a few select type checks that can be supported with alignment checking on AMD64; range checking needs extra instructions).
I’m having trouble understanding how an address could be not linear. You can view a linear address as a (page + offset) tuple. So what makes (page + offset) linear, but (object + offset) not linear?
Does the object cache prevent you from misinterpreting a number as an address? Or misinterpreting a large offset as a different object?
In most of the systems that I’ve seen along these lines, there’s a linear address space somewhere. The thing that phk is complaining about is, I believe, linear address spaces as a programmer abstraction. In particular, virtualised linear address spaces as a programmer abstraction. As a programmer, I want objects and pointers to (offsets within) objects. The fact that the hardware exposes a linear address space to me and then does a virtual-to-pseudophysical and then pseudophysical-to-virtual translation doesn’t really buy me much, other than a (quite large, power-and-performance) overhead from page-table walks and TLBs.
He’s glossing over a lot of the details though. Something needs to allocate objects. Virtualised linear address spaces make it easy to provide a separation of concerns between allocators. The hypervisor allocates pages to the VM, the VM allocates pages to the process, and a userspace malloc assigns objects to user code. If you have an object-based memory then the object allocator must be shared. This is a bit scary for security (it’s now a part of the TCB that can violate both process and VM isolation if it’s wrong) and it has to be generic. Different languages have markedly different allocation patterns and there’s a lot of performance gained by tuning an allocator.
For security, if the allocator is used across security contexts then it must also enforce temporal safety. Building a set of abstractions that make this safe is hard. Systems like the B5500 made the allocator and GC part of the OS (and made the compiler part of the TCB: you could break process isolation if you were able to run arbitrary unprivileged instructions). This comes with some overhead. Even among managed languages, it’s hard to build a GC that’s efficient for everything.
Any system that wants to build GC into its TCB needs to do one of two things:
A lot of the historic object-memory systems picked the latter and were killed by RISCy systems that didn’t because their load-to-store penalties were much higher. For CHERI, we opt for the former and have done a load of work to optimise this. Even so, we gain a huge benefit from the virtualised address space because a memory capability is relative to some specific address space and so we don’t need to scan all of physical memory (actually, physical memory + swap) to determine that there are no capabilities to an address, we ‘just’ need to scan a process’s address space (and, within that, only the pages that have had pointers stored to them, which typically ends up being around 20%). That dramatically increases revocation throughput relative to a multi-tenant single-address-space object-memory system.
Project Maxwell from Sun Labs is probably the most interesting example of a modern object memory system but it was tailored quite aggressively to Java and explicitly placed the JVM in the TCB. I don’t think you’d want to run code from two distinct security contexts in the same object memory space, even with it. In particular, Maxwell did young generation GC in the cache in hardware and provided hooks for old-generation GC in software. Every user needs to trust the software GC. A Java GC is a lot more complex than the small subset of a hypervisor that’s required to maintain page tables for tenant isolation.
Here’s a clue:
A page address is just a number, while an object has as type and a size. This means the hardware can check that the object is being used in a proper manner, and particularly that the access is not outside of the object.
The Rational R1000 looks interesting and I’d like to know more, but it’s not the only machine with this kind of addressing. I think the Burroughs B5000 did something similar, with hardware support for arrays, and the Intel iAPX 432 is another one with object-oriented memory. I’m sure the various Lisp machines also did this sort of stuff.
The C language is actually designed to work on these types of machines. If you convert a pointer to an integer then you lose some information, and can’t convert that integer back to a pointer to the same object as you started with. (Except in implementations that support that sort of conversion, of course). On the Lisp machine I think they represented C pointers as a pair of (object,offset) and converting that to an integer meant you dropped the object reference.
I have some small experience of my own with hardware-checked pointers and I think they’re great. My Scheme implementation’s runtime (Loko Scheme) runs on AMD64 with alignment checking turned on and uses the low bits in pointers for hardware-based type checking. I’ve found numerous bugs, even deep in the runtime (like in the GC), because the hardware automatically trapped a reference where it e.g. had tried to use a fixnum as a pointer to a procedure, or tried to use a vector as a pair. Without the hardware checking these things for free on each memory reference, it would have corrupted some memory or read from some weird location, and crashed much later in some incomprehensible manner. (It’s only a few select type checks that can be supported with alignment checking on AMD64; range checking needs extra instructions).
AIUI pages are within the same address space, an object is its own address.
Two (page + offset) tuples, with unique page values, can refer to the same underlying memory by tweaking the offset.
Each unique object is its own address space. The hardware isolates the objects as opposed to all the software mitigations we use now.