tl;dr page-based linear addressing induces performance loss with complicated access policies, e.g. multilevel page tables. Mr. Kamp would prefer an object model of memory access and protection. Also, CHERI (https://dl.acm.org/doi/10.5555/2665671.2665740) increases code safety by treating pointers and integers as distinct types.
"The R1000 addresses 64 bits of address space instantly in every single memory access. And before you tell me this is impossible: The computer is in the next room, built with 74xx-TTL (transistor-transistor logic) chips in the late 1980s. It worked back then, and it still works today."
That statement has to be coming with some hidden caveats. 64 bits of address space is crazy huge so it's unlikely the entire range was even present. If only a subset of the range was "instantly" available, we have that now. Turn off main memory and run right out of the L1 cache. Done.
This does seem pretty neat though. "CHERI makes pointers a different data type than integers in hardware and prevents conversion between the two types."
I'm definitely curious how the runtime loader works.
"We need to keep in mind, the DRAM ICs themselves have a hierarchy with latency trade-offs" Yes this is the thing -- I'm not a hardware engineer or hardware architecture expert, but -- it seems to me that what we have now is a set of abstractions presented by the hardware to the software based on a model of what hardware "used to" look like, mostly what it used to look like in a 1970s minicomputer, when most of the intensive key R&D in operating systems architecture was done.
One can reasonably ask, like Mr Kamp is, why we should stick to these architectural idols at this point in time. It's reasonable enough, except that the alternative of heterodox, alternative architectures is also heterogenous -- new concepts that don't necessarily "play well with others." All our compiler technology, all our OS conventions, our tooling, etc. would need to be rethought under new abstractions.
And those are fun hobby or thought exercises, but in the real world of industry, they just won't happen. (Though I guess from TFA it could happen in a more specialized domain like aerospace/defence)
In the meantime, hardware engineering is doing amazing things building powerfully performing systems that give us some nice convenient consistent (if sometimes insecure and awkward) myths about how our systems work, and they're making them faster every year.
Makes me wonder if 50 years from now we'll still be stuck with the hardware equivalent of the floppy disk icon, only because retooling the universe over from scratch is too expensive.
As they say, C was designed for the PDP-11 architecture, and modern computers are forced to emulate it, because the tools to describe software (languages and OSes) which we have can't easily describe other architectures.
There were modern semi-successful attempts though, see PS3 / Cell architecture. It did not stick though.
I'd say that the modern heterodox architecture domain is GPUs, but we have one proprietary and successful interface for them (CUDA), and the open alternatives (openCL) are markedly weaker yet. And it's not even touching the OS abstractions.
> As they say, C was designed for the PDP-11 architecture
Not really though. A linear address space was not particularly specific to the PDP-11. The one point where C really was made to fit the PDP-11 was the addition of a byte datatype (aka char), but the PDP-11 wasn't unique in that regard either.
PDP-11 wasn't unique. To the contrary, it had many typical features.
- Uniform memory, cache memory is small, optional and transparent.
- A single linear address space; no pages, stack in the same RAM as data.
- A single CPU, with a single scalar ALU, and completely in-order execution; no need for memory barriers.
A typical modern machine larger than an MCU has several level of memory hierarchy which affect performance enormously, the physical RAM is mapped all over the address space, several execution units process data in parallel and often out of strict order, there are many variants of vector (SIMD) instructions, and usually a whole vector co-processor ("graphics card"). This breaks many of the assumptions that C initially ha made, and hardware tries hard to conceal the memory hierarchy (well, your OS may allow you to schedule your threads to the same NUMA domain), to conceal the parallel execution, to conceal the memory incoherence between processing nodes, etc. Well, you sort of can make the compiler infer that mean a vectorized operation, or use an intrinsic.
In my eyes, the C's assumptions about hardware show their age, and also hold the hardware back.
My memory of the PDP-11 is different.
However, the pdp11 is/was a weird collection of systems, from tiny little single chip implementations to run a VAX console, upto large racks of boards to make up a cpu and fpu like the 11/70.
I mainly worked on 11/44's an 11/73's which both shared a 16bit paged address space, (with no cache that I remember).
They had more physical memory (256k and I think 4M) than could be addressed by the instructions(64k).
The pages where 8k - so eight of them, and waving them around required an OS mapping function call.
The IO controllers where asynchronous, and the OS did preemptive multiprocessing and the problem-space was larger than 64k, and faster than the disk-drive, so multi-processing and locks where required to address it.
We used C and assembler on them. C was nicer than assembler to work with.
I don't see a difference of-kind between the pdp-11 and current computers.
I do see a difference of 'know-ability' of the software stack that makes up a system.
There are so many external dependencies in the systems I have worked on since, many of them larger than the systems that loaded into that pdp-11, so being certain that there is no fault was almost always a pipe-dream. Automated tests helped - somewhat.
Often, confidence is based on the 'trajectory' of the rate of bugs discovered.
> That statement has to be coming with some hidden caveats. 64 bits of address space is crazy huge so it's unlikely the entire range was even present. If only a subset of the range was "instantly" available, we have that now. Turn off main memory and run right out of the L1 cache. Done.
So I did some digging around for documentation about this machine and it looks like it puts the upper 54-bits of the address through a hash function to select an entry in a set associative tag RAM which is then used to select a physical page. This has the possibility for collisions, but it can get away with that because RAM is just a cache for disk contents.
Certain parts of the address technically mean something, but apart from leveraging that in the design of their hash function it has no real relevance to the way the hardware works. This scheme would work with linear 64-bit addresses just fine with an appropriate hash implementation. Basically all that's happening here is that the TLB is large enough to have an entry for reach physical page in the system and a TLB miss means you have to fetch a whole page from disk rather than walking a tree of page tables in memory.
I think the other thing going on here is that the R1000 is a microcoded machine from the 80s with no cache (well unless you're counting main RAM as cache, so it probably has a relatively leisurely memory read cycle which makes it more straightforward to have a very large TLB relative to the size of main memory. There's no magic here and no lessons for modern machines when it comes to how virtual address translation is done
I'm sure there are improvements to be made but there are pretty fundamental physical reasons why reading a random piece of data from a large pool of memory is going to take longer than reading random piece of data from a small pool of memory. Hence, as memory pools have gotten bigger since the days of the R1000 we use caches both in memory itself and in address translation.
What I mean is that the R1000 memory architecture is not fundamentally different from modern hardware in a way that seems to solve any modern design problems. The tag RAM is functionally equivalent to the TLB on a modern CPU, but it's much larger relative to the size of the RAM it's used with. The 2MB memory boards described in US Patent 4,736,287 (presumably an earlier version of the 32MB boards present in the R1000/s400) have a whopping 2K tag RAM entries. This is the same size as the 2nd level data TLB in Zen 2 which is supporting address lookup for a much larger main memory.
If you were to try and make a modern version of the R1000 architecture you're going to run into the same size vs speed tradeoffs that you see in conventional architectures. The server oriented Rome SKus of Zen 2 support 4 TB max RAM. Even if you bump the page size to 4MB, you still would need 1M TLB/tag RAM entries to support that with an R1000-style implementation.
Sorry, but you are simply wrong there. The TLB is just one of many hacks made necessary by the ever-deeper page-table-tree.
What the R1000 does is collapse the obj->phys lookup in the DRAM memory cycle, and if we did that today, we wouldn't need any page-tables to begin with, much less TLBs.
>Sorry, but you are simply wrong there. The TLB is just one of many hacks made necessary by the ever-deeper page-table-tree.
>
>What the R1000 does is collapse the obj->phys lookup in the DRAM memory cycle, and if we did that today, we wouldn't need any page-tables to begin with, much less TLBs.
You would need a TLB even with a completely flat page table because hitting the DRAM bus (some flavor of DDR on modern systems, but it's still fundamentally DRAM) on every access would absolutely destroy performance on a modern machine even if translation itself was "free". You need translation structures that can keep up with the various on-chip cache levels which means they need to be small and hierarchical. You can't have some huge flat translation structure like you have on the R1000 and have it be fast.
Anyway, my point is that at a mechanical level TLB and tag RAM work the same way. You take a large virtual address, hash the upper bits and use them to do a lookup in a set-associative memory (so basically a hash table with a fixed number of buckets for conflicts). In some CPUs (it's a little unclear to me how common it is for cache to be virtually or physically addressed these days) this even happens in parallel with data fetch from cache just like tag RAM lookup on the R1000 was done in parallel with data fetch from DRAM. This is not some forgotten technique, it's just moved inside the CPU die and various speed and die space constraints keep it from covering all the physical pages of a modern system.
Now, could you perhaps use a more R1000-like approach for the final layer of translation, sure. Integrating it tightly with system memory probably doesn't make sense given the need to be able to map other things like VRAM into a virtual address space, but you could have a flat hashtable like arrangement even if it's just a structure in main RAM. You can even implement such a thing on an existing CPU with a software managed TLB (MIPS, some Sparc)
The entire address space (64 address bits, addressing bits, so "only" 61 bit addresses for bytes, but also 3 "kind" bits, separating code/data/control etc.) were available at all times.
The crucial point is that the RAM wasn't laid out as a linear array, but as a page-cache.
In a flat memory space, to allocate a single page far away from all others, you will need four additional pages (the fifth level is always present) for the page-tables, and four memory accesses to look them up before you get to the data.
In the R1000, you present the address you want on the bus, the memory board (think: DIMM) looks that address up in its tag-ram to see if it is present, completes the transaction or generates a memory fault, all in one single memory cycle, always taking the same time.
The problem is that there is a limit on how fast you can make the look-up in hardware. Today, given the large amounts of physical memory and the high frequency that CPUs are clocked at, single cycle lookup would be impossible. In fact today CPUs already have such lookup tables in the form of TLBs as hitting the page table every time would have very high latency; still TLBs cannot cover the whole address space and still need multi-level structures even for a subset of it.
Single Address Space OSs are an option, but it means that you are restricted to memory safe languages, it is very vulnerable to spectre-like attacks, and any bug in the runtime means game over.
I don't know if this machine supported it, but it could allow you to have a system-wide unique type for this-struct-in-this-thread-in-this-process, with strong type checking all the way through the compiler into run time. Which would be pretty cool.
My guess is that it is an object oriented system. The data's type is a pointer to the address that defines the type. Which could be anywhere in the system.
This is also a security feature. If you find a way to randomly change the data's type, you're unlikely to successfully change it to another type.
The type descriptions contain much more than that, for instance valid range for integers, field layout for structures and so on. Also privacy information.
The underexplored value of early segmentation was the discretionary segment level permissions enforced by hardware.
Years ago I prototyped a system that had filesystem permission support at the segment level. The idea was you could have a secure dynamic library for, say, manipulating the passwd file (you can tell how long ago that was). You could call into it if you had the execute bit set appropriately, even if you didn't have the read bit set, so you couldn't read the memory but could call into it at the allowed locations (i.e. PLT was x only).
However it was clear everyone wanted to get rid of the segment support, so that idea never went anywhere.
They made a decent go at it again in 16 and 32 bit protected mode. The GDT and LDT along with task gates were intended to be used as an hardware object capability system like the iAPX 432's.
I'd hope that anyone at Intel with said nightmares would have read this paper by now (wherein Bob Colwell, et al, argue that the 432 could have been faster with some minor fixes, and competitive with contemporary CPUs with some additional larger modifications).
I'm a little confused about how the object base is looked up in these systems, and if they're sparse or dense and have any size or total object count limitations, and if that ends up having the same limitations on total count as page tables that required the current multi-level approach.
As surely you could consider page table as effectively implementing a fixed-size "object cache"? It is just a lookup for an offset into physical memory, after all, with the "object ID" just being the masked first part of the address? And if the objects are variable sized, is it possible to end up with physical address fragmentation as objects of different sizes are allocated and freed?
The claim of single-cycle lookups today would require an on-chip fixed-size (and small!) fast sram, as there's a pretty hard limit on the amount of memory you can get to read in a single clock cycle, no matter how fancy or simple the logic behind deciding to lookup. If we call this area the "TLB" haven't we got back to pagetables again?
And for the size of sram holding the TLB/object cache entries - increasing the amount of data stored in them means you have less total too. A current x86_64 CPU supports 2^48 of physical address space, reduced to 36 bits if you know it's 4k aligned - and 2^57 of virtual address space as the tag, again reduced to 45 bits if we know it's 4k aligned. That means to store the tag and physical address you need a total of 81 bits of SRRAM. A 64-bit object ID, plus 64-bit physical address plus 64-bit size is 192bits, over 2x that, so you could pack 2x the number of TLB entries into the same sram block. To match the capabilities of the example above, 57 bits of physical address (cannot be reduced as arbitrary sizes means it's not aligned), plus a similarly reduced to 48 bit object ID and size still adds up to 153, only slightly less than 2x, though I'm sure people could argue that reducing the capabilities here have merit, I don't know how many objects or their maximum possible size in such a system. And that's "worst case" 4k pages for the pagetable system too.
I can't see how this idea could be implemented without extreme limitations - look at the TLB size of modern processors and that's the maximum number of objects you could have while meeting the claims of speed and simplicity. There may be some advantage in making them flexible in terms of size, rather than fixed-size, but then you run into the same fragmentation issues, and need to keep that size somewhere in the extremely-tight TLB memory.
> As surely you could consider page table as effectively implementing a fixed-size "object cache"? It is just a lookup for an offset into physical memory, after all, with the "object ID" just being the masked first part of the address? And if the objects are variable sized, is it possible to end up with physical address fragmentation as objects of different sizes are allocated and freed?
Because that's only a base, not a limit. The right pointer arithmetic can spill over to any other object base's memory.
Maybe? If you just round up each "object" to 4k then you can implement this using the current PTE on x86_64, but this removes the (supposed) advantage of only requiring a single PTE for each object (or "object cache" lookup entry or whatever you want to call it) in the cases when an object spans multiple page-sizes of data.
Having arbitrary sizes objects will likely be possible in hardware - it's just an extra size being stored in the PTE if you can mask out the objectID from the address (in the example in the original post, it's a whole 64-bit object ID, allowing a full 64-bits of offset within each object, but totaling a HUGE 128bit effectively address)
But arbitrary sizes feels like it pushes the issues that many current userspace allocators have to deal with today to the hardware/microcode - namely about packing to cope with fragmentation and similar (only instead of virtual address space they'll have to deal with physical address space). The solutions to this today are certainly non-trivial and still can fail in many ways, so far away from being solved, let along solved in a simple enough way to be implemented that close to hardware.
So I commented on this a bit elsewhere, but the whole object business is irrelevant for how the address translation hardware in this machine actually works. While the subfields of the address are exploited to optimize hash function used, the hardware is otherwise agnostic to what the upper bits of the address mean. The TLB is just huge relative to the amount of memory it had such that there's one entry for each physical page in the system and it deals with collisions in the TLB by evicting pages to disk
Since this addressing scheme is <object, offset>, and as these pairs need to fit in 64 bits, I am curious, is the numjer of bits for each part is fixed and what are those fixed widths. In other words what is the maximum possible offset within one object and the max number of objects?
Probably segment registers in x86 can be thought as object identifiers, thus allowing the same non-linear approach?(Isn't that the purpose of segments even?)
Update: BTW, another term for what the author calls "linear" is "flat".
Another system that had an object-based non-linear address space I believe was the "Rekursiv" CPU developed at Linn (yes, the Swedish audio/drum machine company;
EDIT: Linn. Scottish. Not drum machine. Thanks for the corrections. In fact I even knew this at one time. Yay brain.) in the 80s.
> Linn (yes, the Swedish audio/drum machine company) in the 80s
Uhm.
Linn the audio company, known as Linn Products, are Scottish, being based a little to the south of Glasgow, and named after the park the original workshop was beside.
Linn the drum machine company, known as Linn Electronics, were American, being founded by and named after Roger Linn.
Two totally different companies, run by totally different people, not connected in any way, and neither of them Swedish.
The Linn Rekursiv was designed by the audio company, and was largely unsuccessful, and none exist any more - not even bits of them :-/
Real segmentation would have solved the problem described in the article. Under virtual memory segments like on the 80386 (and mainframes before that), you can physically relocate a segment and while adjusting its descriptor so that the addressing doesn't change.
The problem was mainly caused by having no MMU, so moving around objects in order to save space required adjusting pointers. Today, a copying garbage collector will do the same thing; rewrite all the links among the moved objects. You'd have similar hacks on Apple Macintoshes, with their MC68K processors and flat space, like doubly indirected objeccts managed by "handles" and whatnot.
The 386 segmentation system exists above the paging portion of the MMU, so it is possible to move them around without physically copying memory (or adjusting the segment+offset).
Here is a somewhat reasonable diagram of how it all works
It's fun to see that old article again. (I wrote the FixDS program Raymond mentions at the end.)
One pain point in 16-bit Windows programming was that you had to do two special things for any callback function in your application: EXPORT the function in your .DEF file, and call MakeProcInstance() on your callback function to get an "instance thunk".
FixDS made a simple patch to the compiled function prologs that rendered all of this unnecessary. You could just use your callback function directly, like we expect today.
Yet in practice the stack on x64 is separate from the heap, GPU memory is general is separate from system memory, and even inside the GPU you have at least a 3 level segmented memory hierarchy.
Even in C-land, you're technically not supposed to fabricate arbitrary heap pointers, you're supposed to offset something you get from malloc(). The Standard says (if memory serves) that only pointers from the beginning of a malloc() to 1-past-the-end have defined behavior (when it comes to the heap).
Of course, there are probably lots of in-practice exceptions when it comes to embedded, kernel code, mmap() shenanigans, etc.
Oh boy, welcome to the exciting world of C pointer provenance :) What you just described is what compiler people call pointer provenance, where each pointer has, in addition to the address, a second piece of info attached to it that describes all the places to which the pointer can point.
This is an extremely simplified and probably incorrect view of https://open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1434r0.... This is complicated because nobody agrees on what the correct behaviour should be, and we have mountains of legacy codebases that all rely on something slightly different when pointers get converted to ints and back.
That's what makes C programming fun: doing what the compiler/language people say you shouldn't be doing and seeing if it works anyways. At least, it works on my machine...
Rational built a truly semantic IDE, and the result of that is that if you change a line of source-code somewhere in a huge complicated project, it will know precisely what the consequences of that change are.
Ultimately, this allows it often just recompile that single line.
To be clear, that metadata only (generally) exists in principle - it is not actually materialized and stored anywhere, even at compile time (definitely not at runtime). There may be cases where the compiler actually tracks it, but most often it is only tracked "best effort" - the compiler only needs to prove that two pointers can't be aliased based on any possible value of that metadata, not actually compute that metadata and use it.
The part of this that I most enjoy is that you cannot even obtain some memory from your own allocator implemented on top of mmap or on top of malloc, store ints in it, return it to the allocator, ask the allocator for memory again and receive the same memory back, and store doubles in it.
I've implemented a pools allocator for embedded devices a couple of times. Allocating memory for callers out of a block of static memory. I thought it was portable C. Which detail of the standard did I not realise I was running into?
Although you shouldn't be on a modern system, you'd instead be implementing malloc on top of mmap. So remove sbrk, and make mmap the "object allocator", and tada! You don't really need linear virtual address spaces anymore.
Yes, this is why malloc() can't actually be implemented in C. Actual implementations of it exist because of special compiler dispensation, or mostly that the callers and implementations are in separate libraries so the implementation isn't visible to the caller.
> Attribute malloc indicates that a function is malloc-like, i.e., that the pointer P returned by the function cannot alias any other pointer valid when the function returns, and moreover no pointers to valid objects occur in any storage addressed by P. In addition, the GCC predicts that a function with the attribute returns non-null in most cases.
But it doesn't provide any operations to do the things in this paragraph (create new pointers). The operation that does this is malloc itself.
This will typically not cause problems, but it would if LTO got so good you could include libc in it.
Standard C provides only a few ways to obtain valid pointers. implementations can define behaviors in cases that the standard leaves undefined, such as allowing more cases of casts of integers to pointers than the standard defines (common in embedded-land), or functions like mmap or sbrk. so you or your chip vendor could define FOO_REG as (uint32_t )0x80001234 and use it as if it were a variable.
Olde C used to just let you use integers as struct pointers, and there was only one struct member namespace. so code like this was valid and did an integer-size write to address 0177770. old unix did this for device register access; see the lions book.
So what? In a bitmask, such as a hardware register or database Bloom filter, two adjacent bits may be unrelated, and their relative position entirely coincidental and insignificant.
That doesn't mean we need a memory model in which bits are separate objects, in some sense.
The Multics system was designed to have segments (for this discussion == pages) that were handled the way he described, down to the pointer handling. Not bad for the 1960s, though Unix was designed for machines with a lot fewer transistors back at the time when that mattered a lot.
Things like TLBs (not a new invention, but going back to the 1960s) really only matter to systems programmers, as he says, and judicious use simplifies and has simplified programming for a long time. I think if he really wants to go down this path he'll discover that the worst case behavior (five probes to find a page) really is worth it in the long run.
On the 645 it did, and I think in any realistic alternative it would have too as segments could be of different sizes and the working set could vary.
However for my simplified comment I said "for this discussion == pages" simply because the difference is simply an extra indirection table in memory, with the segment carrying the access control (like a process address space in unix) and the pages being indexed within it.
All of which was an attempt to say that the post to which we are all commenting is a bit overwrought in its complaint about the worst case search required to find a page. After all, that's what systems programming is all about: the grotty complex plumbing required so other people can worry about the performance of their algorithms that do actual work.
This article compares CHERI to an 80's computer, the Rational R1000 (which I'm glad to know of). It's worth noting that CHERI's main idea was explored in the 70's by the CAP computer[1]. CAP and CHERI are both projects of the University of Cambridge's Computer Lab. It's fairly clear that CAP inspired CHERI.
The original machines like that were the Burroughs 5000 (1961), and the Burroughs 5500 (1964), which was quite successful. Memory was allocated by the OS in variable length chunks. Addresses were not plain numbers; they were more like Unix paths, as in /program/function/variable/arrayindex.
That model works, but is not compatible with C and UNIX.
The architecture of the B5000 / B5500 / B6500 lives on today in the Unisys ClearPath line. I believe the OS, MCP, is one of the longest-maintained software operating systems still in active use, too.
One of the original brains behind the R1000 has mentioned that the B5500 was one of the inspirations, but my personal impression is that he was talking more about the stack-based (vs. register-based) instruction set, than the memory management.
Burroughs machines have 2 sorts of pointers - effectively pointers to offsets on the stack (indexed by a full display so you can do full algol scope semantics, more than just C) as well as pointers to heap memory (base and bounds, with paging for large objects)
So recursive routines get access to their own local variables
I'm not quite sure what you mean - the Burroughs machines have full sets of display registers (hardware managed pointers to each of the stack frames that were currently in scope - Algol/etc had more complex scoping that modern C-style languages) - a stack pointer contained a lexical level (an index into the display registers) and an offset into that stack frame - there's a variant that's 'stuffed' (essentially a reference to a variable in a stack frame that's out of scope - based on the base of stack)
I think it's important to understand that it's not a C machine, doesn't have a linear address space in the normal sense
you create an in-scope reference within the function - and then 'stuff' it which converts it into an offset from the base of the stack - converts an "indirect reference word" into a "stuffed indirect reference word"
it's what you use to pass by reference ..... but algol supports pass-by-name semantics (of which pass by reference is an optimisable subset) - to do fill pass by name (for a simple example a[i] where i is a global) the compiler will create a thunk (a tiny subroutine, in scope of the place where the parameter was passed) and pass a pointer to it - the tag of '7' means a PCW - when it gets dereferenced as a pointer the hardware does a subroutine call to the thunk in the correct scope
> That model works, but is not compatible with C and UNIX.
The Unisys Clearpath line of systems have ISO C compliant compilers, and MCP provides a fairly complete POSIX environment. I've never actually programmed them, but I have the manuals. dlopen is conspicuously missing from the list of POSIX routines. I don't know how close the ISA is to 5500, but at least for Unisys Clearpath the only real incongruity in the environment is that unsigned arithmetic requires compiler-generated instrumentation as integers are sign-magnitude, which doesn't naturally provide the unsigned overflow semantics required by the standard.
ISO C has always tried to steer away from integer/pointer conversions for precisely this reason--pointers are special and might be opaque to the runtime environment. C99 adopted intptr_t, but it was optional and had restricted semantics. There's still no way in standard C to convert a function pointer to an object pointer or to intptr_t. But even in a full POSIX system this limitation only effects dlopen.
Reading the CHERI papers, porting all of FreeBSD to CHERI turned out to be surprisingly easy. dlopen and signals were two of the biggest headaches, IIRC. Very little application code had to change. Playing games with pointers just isn't particularly common in run-of-the-mill Unix applications, or even in open source generally, where writing standards-conformant code has always been valued. (Portability is even more valued, but usually the best way to achieve the latter is through the former.) It's more common in proprietary applications, like games, HPC, embedded, etc.
>You lose the advantages of the tagged hardware when you declare a giant array of raw memory to be managed by C.
Sure, but that's not how it works. What does happen is that real-world software written in C doesn't use all those nasty tricks all that often anymore, or isn't that hard to fix. There are a few tricks that _do_ get used, and CHERI provides accommodations for those. Take a look at https://papers.freebsd.org/2019/bsdcan/davis-cheriabi/.
Worth noting that CHERI _is_ definitely compatible with C and Unix; the default operating system for it is CheriBSD, a FreeBSD fork, and there is a growing number of purecap packages.
True, the CHERI paper[1] cites the Burroughs as well. Amusingly, it cites an article similar to the OP: "The architecture of the Burroughs B5000: 20 years later and still ahead of the times?"[2] - written in 1982...
For a micro, see iAPX 432. It was considered over-complicated for its time but if CHERI catches on, perhaps far ahead of its time.
Also interesting to me was the idea in Darek Mihocka's blog NO EXECUTE! about using emulation to implement advanced processor features rather than forcing everything through a one size fits all hardware policy. Of course emulation will always have a performance hit, but the concept is interesting.
"Unsafe at Any Speed" is the name of Ralph Nader's book on car manufacturers resisting car safety measures. It resulted in the creation of the United States Department of Transportation in 1966 and the predecessor agencies of the National Highway Traffic Safety Administration in 1970.
Which makes this article's reference to such an extreme situation a bit click-baity. Generally not something I'd expect of ACM, though maybe I don't read it enough to know if its descended into that realm on a more regular basis.
I have a much dimmer view of the ACM than you. This is exactly the kind of crank, throwaway op-ed I’d expect out of them (and Poul-Henning Kamp in particular — notable for loudly conflating Judaism and the Israeli government).
So long as you kept the tires inflated. It had a strange motorcycle-like difference between rear and front tires. I don't know if you could feel the handling get bad if that wasn't preserved or if it would surprise you in extreme situations.
Perhaps "any speed" was exaggerated but I wouldn't call the thing click bait when it legitimately called out manufacturing practices and reluctance to put resources into safety which thereby resulted in trivially preventable deaths.
The greater awareness of safety factors brought to light by the book resulted in a culture of safety around automobiles & consumer buying practices that made safety features primary marketing & selling points.
That's all a pretty high bar to reach when using "unsafe at any speed" in the context of address spaces.
Of course things would be faster if we did away with coarse grained virtual memory protection and instead merged everything into a single address space and guaranteed protection using fine grained permission mechanisms.
The problem with that is that a single error in the fine grained mechanism anywhere in the entire system can quite easily cause complete system compromise. To achieve any safety guarantees requires achieving perfect safety guarantees across all arbitrary code in your entire deployed system. This is astronomically harder than ensuring safety guarantees using virtual memory protection where you only need to analyze the small trusted code base establishing the linear address space and do not need to be able to analyze or even understand arbitrary code to enforce safety and separation.
For that matter, fine grained permissions are a strict superset of the prevailing virtual memory paradigm as you can trivially model the existing coarse grained protection by just making the fine grained protection more coarse. So, if you can make a safe system using fine grained permissions then you can trivially create a safe system using coarse grained virtual memory protection. And, if you can do that then you can create a unhackable operating system right now using those techniques. So where is it?
Anybody who claims to be able to solve this problem should first start by demonstrating a mathematically proven unhackable operating system as that is strictly easier than what is being proposed. Until they do that, the entire idea is a total pipedream with respect to multi-tenant systems.
You have misunderstood the article. It is not advocating for the return to single address space systems. It is advocating for potential alternatives to the linear address space model.
Here [1] is an operating system that I think fits under the description of what you were talking about
The more I research Singularity, the more I like it. I deep dived into all the design docs years ago and the amount of rethinking existing OS infrastructure is astounding.
I think that the plague of speculative execution bugs qualify as a single error in virtual memory systems that cause complete system compromise. This was not a logic error in code, but a flaw in the hardware. It isn't clear to me if CHERI would have been immune to speculative execution problems, but access issues would likely have shown up if the memory ownership tests were in the wrong place.
I have been following CHERI. I note that in order to create the first FPGA implementation they had to first define the HDL for a virtual memory system -- all of the research "processor" models that were available did not have working / complete VM implementations. CHERI doesn't replace VM, it is in addition to having VM.
I've found that memory bugs (including virtual memory ones) are difficult to debug, because the error is almost never in the place where the failures show up and there is no easy way to track back who ought to own the object or how long ago the error happened. CHERI can help with this by at least being able to identify the owner.
Virtual memory systems are usually pretty complex. Take a look at the list of issues for the design of L3 <https://pdos.csail.mit.edu/6.828/2007/lec/l3.html>. The largest section there is for creating address spaces. For the Linux kernel, in this diagram a lot of the MM code is colored green <https://i.stack.imgur.com/1dyzH.png>, it is a significant portion. More code means more bugs and much harder to formally verify.
I am not convinced by the argument that it is possible to take a fine grained system and trivially expand it to a coarse grained system. How is shared memory handled, mmap'ed dylibs, page level copy-on-write?
Speculative execution vulnerabilities largely don’t cause system compromise and instead are constrained by virtual memory. That’s why much of the focus was on the OS kernel: modern operating systems generally include all physical memory in their virtual address space.
is there an example of machine code that doesn't make use of a linear contiguous call stack?
what would the alternative be? compute the size of all the stack frames a-priori in the compiler and then spray them all over main memory and then maintain a linear contiguous list of addresses? doesn't the linear contiguous nature of function call stacks in machine code preserve locality in order to make more efficient use of caches? or would the caches have to become smarter in order to know to preserve "nearby" stack frames when possible?
also, why not just make the addresses wider and put the pid in the high bits? they're already doing this masking stuff for the security descriptors, why not just throw the pid in there as well and be done with it?
The linked article doesn't mention call stacks explicitly, but describes the R1000 arch was object+offset addressed in HW. So unless they restricted the call stack to fit into one object and use only offsets, then yes, they must have chained objects together for the stack.
When you have a page-based memory model, you've created the importance of address locality. If you have object-based memory model, and the working set is of objects, not pages, then address locality between objects doesn't matter.
Of course, page-based based memory models are by FAR the most common in practice.
(Note: pages ARE objects, but the objects are significant to the VM system and not to your program. So strictly, page-based models are a corner case of object-based models, where the objects are obscure.)
would be interesting to see how the actual call stack is implemented. they must either have a fixed width object as you mention or some kind of linear chaining like you're describing.
memory and disk are unified into one address space, code is represented by this "diana" structure which can be compressed text, text, ast or machine code. would be curious how procedures are represented in machine code.
When you reverse engineer "normal" code, you know the CPU can handle integers of X, 2X, 4X bit widths, you know it wants things aligned this way or that way etc.
The R1000 is bit addressed, and integers can be any width from 1 to 64 bits, structures can be "variant" (See: Ada) so reverse engineering the storage layout is ... not an accomplished feat yet.
Since the primary task for the R1000 was Ada program development, and since there were a standardized semantic representation of Ada programs ("DIANA"), one of the fundamental hardware/microcode data-types is "DianaTree", which is, I think a pretty generic CS tree of some kind.
These "DianaTree" types seem to also have been used for other stuff, like directories in the object store etc.
> is there an example of machine code that doesn't make use of a linear contiguous call stack?
Early CPUs didn’t have support for a stack, and some early languages such as COBOL and Fortran didn’t need one. They didn’t allow recursive function calls, so return addresses could be stored at fixed addresses, and a return could either be an indirect jump reading from that address or a direct jump whose target address got modified when writing to that fixed address (see https://people.cs.clemson.edu/~mark/subroutines.html for the history of subroutine calls)
If you put the pid in the high bits of every pointer you run into problems when you want to support fork(). The child gets a new pid but keeps all the same pointers as its parent.
And that only protects you against one process trying to read/write another process's memory. We already have good support for this type of protection on current hardware/OSes. What is desired is something that prevents a process from reading/writing its own memory, through an out of bounds pointer. This would prevent buffer overflows, stash smashing, etc. and be a good defense against RCE.
Non-contiguous stacks are typically just linked-lists of call frames, or groups or call frames. One of the examples that used to be regularly trotted out comp.lang.c 15+ years ago was an IBM mainframe environments, where stacks were linked lists but still managed by hardware.
Off the top of my head, current examples of non-contiguous stacks on more familiar system with supporting code compiled directly to machine code (i.e. not language interpreters and VMs, where this is actually very common), include
1) gccgo, which compiles Go code to use split stacks.
2) gcc with -fsplit-stacks, which permits compiling C (and C++?) code which uses the same stack discipline as gccgo.
3) OCaml's new concurrency work utilizes non-contiguous stacks. I'm not familiar with OCaml toolchains, but notably they do generate DWARF and related tables so both debuggers and the garbage collector can properly walk logical stacks. See https://arxiv.org/abs/2104.00250
4) There's a stack-smashing and ROP prevention technique call shadow stacks, where a single logical call stack is implemented using two contiguous stacks, one primarily for return addresses (or related metadata) and the other primarily for objects. See https://en.wikipedia.org/wiki/Shadow_stack Both GCC and clang support software-implemented shadow stack disciplines (SafeStacks), and some newer Intel and ARM ISA extensions implement hardware-enforced shadow stacks.
Fun fact: for many languages a linear memory block doesn't work - because execution context lifetimes aren't strictly FIFO. For example continuations are a language feature that causes this (unless they're restricted eg to single-shot).
> Why do we even have linear physical and virtual addresses in the first place, when pretty much everything today is object-oriented?
Well, GPU code is certainly not object-oriented, and I hope it never becomes that. SIMD code won't be able to jump between objects like typical CPU-oriented OOP does (unless all objects within a warp/workgroup jump to the same function pointers?)
GPU code is common in video games. DirectX needs to lay out its memory very specifically as you write out the triangles and other vertex/pixel data for the GPU to later process. This memory layout is then memcopy'd over to PCIe using the linear address space mechanism, and GPUs are now cohesive with this space (thanks to Shared Virtual Memory).
So today, thanks to shared virtual memory and advanced atomics, we can have atomic compare-and-swap coordinate CPU and GPU code operating over the same data (and copies of that data can be cached in CPU-ram or GPU-VRAM and transferred over automatically with PCIe memory barriers and whatnot).
----------
Similarly, shared linear address spaces operate over rDMA (remote direct memory access), a protocol built on top of Ethernet. This means that your linear memory space is mmap'd on your CPU, but then asks for access to someone else's RAM over the network. The mmap then causes this whole "inefficient pointer-traversals" to then get turned into Ethernet packets to share RAM between CPUs.
Ultimately, when you start dealing with high-speed data-sharing between "external" compute units (ie: a GPU, or a ethernet-connected far-away CPU), rather than "just" a NUMA-node or other nearby CPU, the linear address space seems ideal.
--------
Even the most basic laptop, or even Cell Phone, these days, is a distributed system consisting of a CPU + GPU. Apple chips even have a DSP and a few other elements. Passing data between all of these things makes sense in a distributed linear address space (albeit really wonky with PCIe, mmaps, base address pointers and all sorts of complications... but they are figured out, and it does work every day)
I/O devices working directly in memory is going to only become more common. 100Gbps network connections exist in supercomputer labs, 10Gbps Ethernet is around the corner for consumers. NVMe drives are pushing I/O to such high bandwidths that'd make DDR2 RAM blush. GPUs are growing more complicated and are rumored to start turning into distributed chiplets soon. USB3.0 and beyond are high-speed links that directly drop off data into linear address spaces (or so I've been told). Etc. etc.
Thing is that I think TFA author isn't speaking of "object-oriented" in the typical sense. I believe it's more about how the VM paging system and cache and etc. is really working with abstract segment "objects" that are blobs of memory but presented to the process as a single linear address space. I don't think the author means OO as in "Smalltalk" or "Java" [methods + objects + inheritance] but more "object based" in a more generic sense of "there's blobs of stuff with abstract handles pointing to them" that then gets painted to the process as if it's a single linear sequence of bytes when in the actual machine... it's not.
Since "pretty much everything today is object-oriented" is such an important point in the article, I feel the author does his readers and himself a disservice by not defining what he means by object-oriented, especially if he uses it in a different sense than everybody else.
Maybe. But in the OS world "object" does have an established meaning.
I think the broader point is that you can build an "object-oriented" system in the sense that you're expecting overtop of the "object-based" systems he is describing and it will give you much of the base level semantics of an OO system (object allocation, tagging, encapsulation) without enforcing any particular OO language semantics (inheritance, typing, methods, etc.) and while also allowing for non-OO (blob of memory) semantics if you need it.
Think of each C allocation via malloc/free as an object. It's just in his system the pointers that point to those allocations are not describable as a series of integer offsets into a big linear memory, but really are handles or unique IDs which map directly into the VM subsystem of the OS and to some action happening in the MMU.
In essence most object-oriented language VMs/runtimes are doing this themselves, essentially building abstract handles (object references, etc.) overtop of the "linear memory" abstraction that the OS provides. If I understand his gist he's really just talking about cutting out the middleman.
I suspect, though, that there's not really a lot of efficiency gains anyways. This path has been so heavily optimized (in both hardware and software) over the decades that it likely matters little.
The security argument maybe is more compelling. There's good argument for the concept of never being able to turn an integer into a pointer or into an integer and back again. Except this would break probably the majority of C programs out there.
Maybe the middle road is for the OS to present a sandboxed "legacy" or "emulation" environment for programs that do pointer arithmetic and to provide enhanced compilers that flag these kinds of things and encourage/offer alternatives.
Given the prevalence of virtualization tech now, there's probably more room for experimentation in this type of thing these days without breaking compat...
“An obstack is a pool of memory containing a stack of objects. You can create any number of separate obstacks, and then allocate objects in specified obstacks. Within each obstack, the last object allocated must always be the first one freed, but distinct obstacks are independent of each other.
Aside from this one constraint of order of freeing, obstacks are totally general: an obstack can contain any number of objects of any size. They are implemented with macros, so allocation is usually very fast as long as the objects are usually small. And the only space overhead per object is the padding needed to start each object on a suitable boundary.”
I love obstacks, after a lead at a job I was at a decade ago pointed them out to me I always look for a chance to use them, but haven't really had much of a chance.
There isn't a lot of info about them though. Go hunting for performance metrics on them, or discussion of them generally and you won't find much. The glibc pages themselves don't give much justification why you would use them vs malloc, or an arena allocator, etc.
> Well, GPU code is certainly not object-oriented, and I hope it never becomes that.
Jonathan Blow has been experimenting a lot with arrays of structs versus structs of arrays, particularly in making them both first class instead of assuming one and ignoring the other. This is essentially the column- versus row-oriented data question answered with a question: why not both?
I think if you had a first class language that supported both, that you wouldn't mind so much if GPU code became object oriented.
I haven’t heard much about JAI for a few years, is this idea catching on?
I don’t know why not both, is it maybe because one of the two layouts will almost always have worse performance for any given access pattern? I can see uses for having both for the non-critical-path parts, though maybe once you’re indexing it in the awkward but perf-friendly way, you’ve already done the hard work and there’s little point to proving the other style of indexing? (Isn’t the best perf always found using whatever layout & indexing is the most difficult… there must be some eponymous law for this, right?) I guess it is possible to have multiple critical paths each favoring a different layout. Not sure how often I’ve ever seen that in practice, I would guess it’s probably rather rare.
The most obvious one to me is what if you change your mind?
What if 90% of these objects should be compactly slab allocated, but you also run small, very disjointed numbers of them through an editor or an undo list or whatever and so they need to live separate from this array?
I don't know what the answer is, but I feel like a few good candidates will come out of the conversations started by Rust. You can't replace an object with a new object while it's globally readable. But if you own the parent object, you can rewrite it however you want, or whichever ways are compatible with the other invariants you want for the system, like max time per frame or response time.
Those change the type annotations for a memory location. Also if you tell me there are no concurrency gotchas for this then I’ll tell you that you have a single threaded interpreter or you’re lying.
We are talking about retaining the type and swapping the pointers from an independent object to a set of offsets into a struct of arrays.
> if you tell me there are no concurrency gotchas for this then I’ll tell you that you have a single threaded interpreter or you’re lying
You are making a big assumption. Neither common lisp nor smalltalk specify the semantics of concurrent programs, but it is certainly possible to implement such a feature without, as you say, concurrency gotchas. Perhaps a better example is concurrently compacting gcs for java.
As far as I can tell, the 'structure of arrays' design pattern appeared in the game development world some time around 1998-2005. Columnar layouts have been known for upwards of 50 years now, as has the general notion that the way you lay out and represent your data matters and can be adjusted at will for your use cases. Many different layouts and optimisation structures are known and have been used, esp. in databases.
Blow isn’t inventing structs of arrays. It’s as you say a common gaming idiom and one he’s used before. What he was doing is trying to make it a first class citizen. Very few languages do anything for these. None of the language I use have iterator that work for this. You have to write your own bookkeeping logic every time.
The memory layout can be better this way depending on how the fields of a strict are laid out. It also gives the data better locality.
Let's say you're iterating over position coordinates of some set of objects in a game. With an array-of-structs you can lose ou on cache locality if unrelated fields are nearby. If you use a struct-of-arrays you get cache locality advantages anytime you do something like "iterate over this 1 field for each object"
In this case GPUs are actually the perfect argument in favor of the article. GPUs only speak in objects, never linear addresses. You allocate a type of object and that allocation just now is that type. eg, a texture is always a texture, never a vertex buffer. Which is a different object altogether. And you never work with addresses. You can point objects at other objects. You can point at an offset from an object. But you can never do arbitrary pointer manipulation, and you never have any idea if the address space is linear or not.
By making pointers treated the same on CPU or GPU (by allowing their 64-address spaces to be identical by sharing the same memory regions + using PCIe to keep those memory regions in sync), you can perform high-speed CPU / GPU communications of even linked data structures (linked lists, trees, graphs).
GPUs utilize many linked data-structures. Oct-trees accelerate bounds testing, BVH trees help raytracing. Etc. etc. The GPU addresses must be linear because they're synchronized to the CPU's memory space.
GPU stuff has been "object oriented" for a long time. The ability to just arbitrarily address data as bytes from shaders is relatively new and modern and still constrained.
If you want to talk to a GPU via vulkan or d3d12 you're going to navigate a maze of descriptor sets, pipeline objects, buffers of various types, samplers, etc. These are all Objects with distinct types and data and the GPU hardware will interact with them in specific ways, even if it's also a general purpose computing device that will run some shader code you throw at it. When I was writing bare-metal graphics code for the PS4 there was still a lot of Object Orientation there too even if there weren't vtables or a garbage collector involved.
Seeing RAM as a collection of linear addresses on GPUs (especially as shared virtual memory, pinned memory, or other such GPU/CPU virtual memory sharing features) is a feature from 2010-era, be it from OpenCL, DirectCompute, or CUDA.
DirectCompute just sees the data as a collection of bytes.
There is often a quite significant distance between the beautiful, elegant and efficient design that brings tears to the eyes of a designer, and being pragmatic and financially viable.
Building a new competitive processor architecture isn't feasible if you can't at least ensure compile-time compatibility with existing programs. People won't buy a processor that won't run their programs.
The Mill's memory model is one of its most interesting features IMO [1] and solves some of the same problems, but by going the other way.
On the Mill the whole processor bank uses a global virtual address space. TLB and mapping to physical memory happens at the memory controller. Everything above the memory controller is in the same virtual address space, including L1-L3+ caches. This solves a lot of problems, for example: If you go out to main memory you're already paying ~300 cycles of latency, so having a large silicon area / data structure for translation is no longer a 1-cycle latency problem. Writes to main memory are flushed down the same memory hierarchy that reads come from and succeed as soon as they hit L1. Since all cache lines are in the same virtual address space you don't have to track and synchronize reads and writes across translation zones within the cache hierarchy. When you request an unallocated page you get the whole pre-zeroed page back instantly, since it doesn't need to be mapped to physical pages until writes are flushed out of L3. This means its possible for a page to be allocated, written to, read, and deallocated which never actually touches physical memory throughout the whole sequence and the whole workload is served purely within the cache hierarchy.
Protection is a separate system ("PLB") and can be much smaller and more streamlined since it's not trying to do two jobs at once. The PLB allows processes to give fine-grained temporary access of a portion of its memory to another process; RW, Ro, Wo, byte-addressed ranges, for one call or longer etc. Processes get allocated available address space on start, they can't just assume they own the whole address space or start at some specific address (you should be using ASLR anyways so this should have no effect on well-formed programs, though there is a legacy fallback).
The Mill model is kind of cool, but today, many peripherals (including GPUs and NICs) have the ability to dump bytes straight into L3 cache. This improves latency in a lot of tasks, including the server-side ones that the Mill is designed for. This is possible due to the fact that MMUs are above the L3 cache.
Honestly, I'm happy waiting for 4k pages to die and be replaced by huge pages. Page tables were added to the x86 architecture in 1985, when 1MB of memory was a ton of memory to have. Having 256 pages worth of memory in your computer was weird and exotic. Fast forward to today, and the average user has several GB of memory - mainstream computers can be expanded to over 128 GB today - and we still mainly use 4k pages. That is the problem here. If we could swap to 2M pages in most applications, we would be able to reduce page table sizes by a factor of 512, and they would still be a lot larger than page tables when virtual memory was invented. And we wouldn't waste much memory!
But no, 4k pages for backwards compatibility. 4k pages forever. And while we're at it, let's add features to Linux (like TCP zero copy) that rely on having 4k pages.
Once on an embedded system, we found 30% of our processing time was spent handling TLB misses.
We also didn't have access to the code that set up the page tables. Somehow I got the linker to emit a function hook which I used to defrag the page tables after they were written but before the MMU was enabled.
I remember thinking, "This is not what I learned about in school."
I can probably guess the OS you were running, but lets just say, some OS's put a lot more effort into assure that virtually continuous mappings tend to also be physically continuous because it then becomes possible to map larger blocks of ram continuously.
AKA, both X86 and ARM (as do various other processors) have intermediate bits in their page directory structures that flag 'instead of using another level of PTE/etc below this level assume we are just pointing at an equal size physical range" which on x86-64 can be 2M or 1G. Given the latest Intel x86's have a multilevel TLB, with 8 1G L1 entries, and 1K of L2 TLB entries it should be fairly straightforward to fix with appropriate huge page tweaks unless your data structure exceeds a TB. And even if it does, keeping everything in 1G pages means that the data caches should be able to keep the top level global page directory/etc cached avoiding main ram hits, and resulting in fairly quick TLB refills.
tl;dr: conventional design bad, me smart, capability-based pointers (base+offset with provenance) can replace virtual memory, CHERI good (a real modern implementation of capability-based pointers).
The first two points are similar to other Poul-Henning Kamp articles [1]. The last two are more interesting.
I'm inclined to agree with "CHERI good". Memory safety is a huge problem. I'm a fan of improving it by software means (e.g. Rust) but CHERI seems attractive at least for the huge corpus of existing C/C++ software. The cost is doubling the size of pointers, but I think it's worth it in many cases.
I would have liked to see more explanation of how capability-based pointers replacing virtual memory would actually work on a modern system.
* Would we give up fork() and other COW sorts of tricks? Personally I'd be fine with that, but it's worth mentioning.
* What about paging/swap/mmap (to compressed memory contents, SSD/disk, the recently-discussed "transparent memory offload" [2], etc)? That seems more problematic. Or would we do a more intermediate thing like The Mill [3] where there's still a virtual address space but only one rather than per-process mappings?
* What bookkeeping is needed, and how does it compare with the status quo? My understanding with CHERI is that the hardware verifies provenance [4]. The OS would still need to handle the assignment. My best guess is the OS would maintain analogous data structures to track assignment to processes (or maybe an extent-based system rather than pages) but maybe the hardware wouldn't need them?
* How would performance compare? I'm not sure. On the one hand, double pointer size => more memory, worse cache usage. On the other hand, I've seen large systems spend >15% of their time waiting on the TLB. Huge pages have taken a chunk out of that already, so maybe the benefit isn't as much as it seemed a few years ago. Still, if this nearly eliminates that time, that may be significant, and it's something you can measure with e.g. "perf"/"pmu-tools"/"toplev" on Linux.
[4] I haven't dug into how when fetching pointers from RAM rather than pure register operations, but for the moment I'll just assume it works, unless it's probabilistic?
> I'm inclined to agree with "CHERI good". Memory safety is a huge problem. I'm a fan of improving it by software means (e.g. Rust) but CHERI seems attractive at least for the huge corpus of existing C/C++ software
A lot of C/C++ code assumes that pointers are integers are pointers, so I dunno how big the corpus would actually be. People will cast between them but that's not the end of it, they will also make unions, and they will memcpy from one to another. It wouldn't surprise me if there is a lot of code that even assumes pointers are exactly 64-bit wide.
Yeah, some source changes would be needed, including removing some clever optimizations. Still much easier than changing languages entirely. I rewrote a small C++ application into Rust. Only a few thousand lines iirc, and I was the sole author of both versions. Even that was a significant effort.
Note that it's not like with CHERI you can't cast a pointer to int or something. Sure you can, that's one of the main accomplishments: to demonstrate that hardware capabilities can work with real-world source code, like PostgreSQL.
So, it's not like you can't typecast; rather, there are some specific things the hardware will prevent you from doing, eg '(void *)42' - if you force clang to accept it, it will crash at runtime due to missing tag.
As things stand now, CHERI doesn't replace virtual memory. MMU is still there; CHERI is a layer placed on top (so it's CHERI capabilities -> linear local addresses -> hardware addresses). Which is why things generally work as usual, even though the entire FreeBSD userspace and (sometimes) the kernel are compiled as purecap binaries, using capabilities instead of pointers.
The fork(2) isn't a problem when running like this, but it does become a problem if you want to colocate processes in a single address space. It's not as much of a problem as I'd previously expect: there's vfork(2) and posix_spawn(2); fork is only a problem until subsequent execve(2); and also because many systems don't support fork(2) anyway, userspace had to adapt.
> As things stand now, CHERI doesn't replace virtual memory.
Yeah, he's proposing...something else. It's not clear to me exactly what, except sort of like this obscure historic machine he vaguely described. See e.g. this paragraph:
> The linear address space as a concept is unsafe at any speed, and it badly needs mandatory CHERI seat belts. But even better would be to get rid of linear address spaces entirely and go back to the future, as successfully implemented in the Rational R1000 computer 30-plus years ago.
> They also made it a four-CPU system, with all CPUs operating in the same 64-bit global address space. It also needed a good 1,000 amperes at 5 volts delivered to the backplane through a dozen welding cables.
These days you just use 12v and convert right next to or on die - but we are still in that range of amps for big chips!
Take for example a 3090 at 500w @12v, the core is running at 1.056v, that’s 473 Amps!
That goes a long way to explaining the pin count on those chips! The idea of that much current running through a bunch of angelhair thickness gold wire is horrifying.
The hardware and modern OSes support large 2MB pages, and huge 1GB pages. They trim 1 or 2 levels from that tree, respectively. With huge pages a single node of that tree addresses 512GB of memory, for most practical applications you’re pretty much guaranteed to translate these addresses without TLB cache misses.
There’re some limitations about them, on Windows the process needs a special security privilege, also these pages are never swapped to a page file. But still, AFAIK when programmers really need the performance, like in a database engine, they do use these things when available.
Doing tagged slab allocation seems like a reasonable thing for a hardware microarchitecture to consider.
The article starts by complaining about modern CPU complexity, five-level page tables to maintain the illusion of a linear, uniform memory space.
Then goes on to juxtapose that complexity with the an architecture that would use that complexity to support tagged memory objects more directly, part of the system ABI.
If we're going to spend all of our time manipulating memory objects anyway, why mess around?
Was the Intel iAPX so much of a disaster, compared to a modern x86_64 architecture, that we are forever forbidden to even consider such hardware?
The linear address space is the root reason why any language with FFI support will be inherently unsafe, unfortunately. Any errant pointer from C can accidentally (or intentionally) corrupt objects in the safe language. It's a difficult problem to solve.
Vale's "Fearless FFI" designs [0] says we could sandbox entire third-party libraries using a WebAssembly compilation step, which might work well. Sometimes I wonder what would happen if we made an entire OS using Vale, and what kind of security improvements it might bring.
I think he's advocating fitting a high level language like Ada in the kernel or in the CPU(?), with one global addressing space and no separate individual process addressing space for memory protection, but rather relying on the high language to provide memory protection. That's where his bizarre hyping of "object oriented" addressing space came from.
It has been done. See Singularity project from Microsoft Research, which used C# as the language to provide memory protection, no process, all programs running in the same global memory space, and all of them running in ring-0. It was a fun research project, but never really made it out. There were other research projects like it.
Also his (object, offset) addressing space is essentially a segmented memory model. The object id is the segment id. I bet the object id is in a linear space.
It's been done way earlier than MSFT's SingularityOS: see e.g. Hansen's book "The Architecture of Concurrent Programs" (from 1977) where he writes an OS in Pascal with exactly this approach to process separation.
Heck, I'd argue everyone who writes their own toy OS should probably start with this approach and then retrofit memory protection later because it simplifies things tremendously and you get something actually usable much earlier (context switching between is not that hard but it's complicated, especially on x86).
Memory protection is nice to have because then you're likely to get crashes when you screw up pointer stuff. And crashes are easier to debug than writes to the wrong place.
Of course, you can do identity memory mapping and skip virtual vs physical questions (for x86, memory protection requires using virtual memory, because the protection information is in the page tables, and iiuc, amd64 also requires using virtual memory, but it's still a useful simplification to do identity mapping so the virtual address is the physical address). My toy OS only runs one process, so there was never going to be more than one memory map anyway.
> It has been done. See Singularity project from Microsoft Research, which used C# as the language to provide memory protection, no process, all programs running in the same global memory space, and all of them running in ring-0. It was a fun research project, but never really made it out.
The problem is basically the choice of C#. If today people use WASM, with no process distinctions, same address space, all in ring0 it would already be a much more successful project.
243 comments
[ 4.9 ms ] story [ 154 ms ] threadhttps://dl.acm.org/doi/abs/10.1145/3534854
That statement has to be coming with some hidden caveats. 64 bits of address space is crazy huge so it's unlikely the entire range was even present. If only a subset of the range was "instantly" available, we have that now. Turn off main memory and run right out of the L1 cache. Done.
We need to keep in mind, the DRAM ICs themselves have a hierarchy with latency trade-offs. https://www.cse.iitk.ac.in/users/biswap/CS698Y/lectures/L15....
This does seem pretty neat though. "CHERI makes pointers a different data type than integers in hardware and prevents conversion between the two types."
I'm definitely curious how the runtime loader works.
One can reasonably ask, like Mr Kamp is, why we should stick to these architectural idols at this point in time. It's reasonable enough, except that the alternative of heterodox, alternative architectures is also heterogenous -- new concepts that don't necessarily "play well with others." All our compiler technology, all our OS conventions, our tooling, etc. would need to be rethought under new abstractions.
And those are fun hobby or thought exercises, but in the real world of industry, they just won't happen. (Though I guess from TFA it could happen in a more specialized domain like aerospace/defence)
In the meantime, hardware engineering is doing amazing things building powerfully performing systems that give us some nice convenient consistent (if sometimes insecure and awkward) myths about how our systems work, and they're making them faster every year.
There were modern semi-successful attempts though, see PS3 / Cell architecture. It did not stick though.
I'd say that the modern heterodox architecture domain is GPUs, but we have one proprietary and successful interface for them (CUDA), and the open alternatives (openCL) are markedly weaker yet. And it's not even touching the OS abstractions.
Not really though. A linear address space was not particularly specific to the PDP-11. The one point where C really was made to fit the PDP-11 was the addition of a byte datatype (aka char), but the PDP-11 wasn't unique in that regard either.
- Uniform memory, cache memory is small, optional and transparent.
- A single linear address space; no pages, stack in the same RAM as data.
- A single CPU, with a single scalar ALU, and completely in-order execution; no need for memory barriers.
A typical modern machine larger than an MCU has several level of memory hierarchy which affect performance enormously, the physical RAM is mapped all over the address space, several execution units process data in parallel and often out of strict order, there are many variants of vector (SIMD) instructions, and usually a whole vector co-processor ("graphics card"). This breaks many of the assumptions that C initially ha made, and hardware tries hard to conceal the memory hierarchy (well, your OS may allow you to schedule your threads to the same NUMA domain), to conceal the parallel execution, to conceal the memory incoherence between processing nodes, etc. Well, you sort of can make the compiler infer that mean a vectorized operation, or use an intrinsic.
In my eyes, the C's assumptions about hardware show their age, and also hold the hardware back.
They had more physical memory (256k and I think 4M) than could be addressed by the instructions(64k).
The pages where 8k - so eight of them, and waving them around required an OS mapping function call.
The IO controllers where asynchronous, and the OS did preemptive multiprocessing and the problem-space was larger than 64k, and faster than the disk-drive, so multi-processing and locks where required to address it.
We used C and assembler on them. C was nicer than assembler to work with.
I don't see a difference of-kind between the pdp-11 and current computers. I do see a difference of 'know-ability' of the software stack that makes up a system.
There are so many external dependencies in the systems I have worked on since, many of them larger than the systems that loaded into that pdp-11, so being certain that there is no fault was almost always a pipe-dream. Automated tests helped - somewhat.
Often, confidence is based on the 'trajectory' of the rate of bugs discovered.
So I did some digging around for documentation about this machine and it looks like it puts the upper 54-bits of the address through a hash function to select an entry in a set associative tag RAM which is then used to select a physical page. This has the possibility for collisions, but it can get away with that because RAM is just a cache for disk contents.
Certain parts of the address technically mean something, but apart from leveraging that in the design of their hash function it has no real relevance to the way the hardware works. This scheme would work with linear 64-bit addresses just fine with an appropriate hash implementation. Basically all that's happening here is that the TLB is large enough to have an entry for reach physical page in the system and a TLB miss means you have to fetch a whole page from disk rather than walking a tree of page tables in memory.
I think the other thing going on here is that the R1000 is a microcoded machine from the 80s with no cache (well unless you're counting main RAM as cache, so it probably has a relatively leisurely memory read cycle which makes it more straightforward to have a very large TLB relative to the size of main memory. There's no magic here and no lessons for modern machines when it comes to how virtual address translation is done
But that is precisely my point: Maybe there are better ways to build them ?
If you were to try and make a modern version of the R1000 architecture you're going to run into the same size vs speed tradeoffs that you see in conventional architectures. The server oriented Rome SKus of Zen 2 support 4 TB max RAM. Even if you bump the page size to 4MB, you still would need 1M TLB/tag RAM entries to support that with an R1000-style implementation.
What the R1000 does is collapse the obj->phys lookup in the DRAM memory cycle, and if we did that today, we wouldn't need any page-tables to begin with, much less TLBs.
You would need a TLB even with a completely flat page table because hitting the DRAM bus (some flavor of DDR on modern systems, but it's still fundamentally DRAM) on every access would absolutely destroy performance on a modern machine even if translation itself was "free". You need translation structures that can keep up with the various on-chip cache levels which means they need to be small and hierarchical. You can't have some huge flat translation structure like you have on the R1000 and have it be fast.
Anyway, my point is that at a mechanical level TLB and tag RAM work the same way. You take a large virtual address, hash the upper bits and use them to do a lookup in a set-associative memory (so basically a hash table with a fixed number of buckets for conflicts). In some CPUs (it's a little unclear to me how common it is for cache to be virtually or physically addressed these days) this even happens in parallel with data fetch from cache just like tag RAM lookup on the R1000 was done in parallel with data fetch from DRAM. This is not some forgotten technique, it's just moved inside the CPU die and various speed and die space constraints keep it from covering all the physical pages of a modern system.
Now, could you perhaps use a more R1000-like approach for the final layer of translation, sure. Integrating it tightly with system memory probably doesn't make sense given the need to be able to map other things like VRAM into a virtual address space, but you could have a flat hashtable like arrangement even if it's just a structure in main RAM. You can even implement such a thing on an existing CPU with a software managed TLB (MIPS, some Sparc)
If you do away with the page-table-tree, there is no problem for the TLB to mitigate.
The crucial point is that the RAM wasn't laid out as a linear array, but as a page-cache.
In a flat memory space, to allocate a single page far away from all others, you will need four additional pages (the fifth level is always present) for the page-tables, and four memory accesses to look them up before you get to the data.
In the R1000, you present the address you want on the bus, the memory board (think: DIMM) looks that address up in its tag-ram to see if it is present, completes the transaction or generates a memory fault, all in one single memory cycle, always taking the same time.
Single Address Space OSs are an option, but it means that you are restricted to memory safe languages, it is very vulnerable to spectre-like attacks, and any bug in the runtime means game over.
CHERI works just fine for enforcing memory protection within an address space.
what what what?
How on earth would you ever need to have a type enumeration 2^64 long?
Neat, though.
All this extra complexity and bus width doesn't come for free, after all, there's opportunity cost.
GUIDs for types.
This is also a security feature. If you find a way to randomly change the data's type, you're unlikely to successfully change it to another type.
Having said that, I wouldn't be surprised if some form of segmentation became popular again.
Years ago I prototyped a system that had filesystem permission support at the segment level. The idea was you could have a secure dynamic library for, say, manipulating the passwd file (you can tell how long ago that was). You could call into it if you had the execute bit set appropriately, even if you didn't have the read bit set, so you couldn't read the memory but could call into it at the allowed locations (i.e. PLT was x only).
However it was clear everyone wanted to get rid of the segment support, so that idea never went anywhere.
https://archive.org/details/432_complexity_paper/
As surely you could consider page table as effectively implementing a fixed-size "object cache"? It is just a lookup for an offset into physical memory, after all, with the "object ID" just being the masked first part of the address? And if the objects are variable sized, is it possible to end up with physical address fragmentation as objects of different sizes are allocated and freed?
The claim of single-cycle lookups today would require an on-chip fixed-size (and small!) fast sram, as there's a pretty hard limit on the amount of memory you can get to read in a single clock cycle, no matter how fancy or simple the logic behind deciding to lookup. If we call this area the "TLB" haven't we got back to pagetables again?
And for the size of sram holding the TLB/object cache entries - increasing the amount of data stored in them means you have less total too. A current x86_64 CPU supports 2^48 of physical address space, reduced to 36 bits if you know it's 4k aligned - and 2^57 of virtual address space as the tag, again reduced to 45 bits if we know it's 4k aligned. That means to store the tag and physical address you need a total of 81 bits of SRRAM. A 64-bit object ID, plus 64-bit physical address plus 64-bit size is 192bits, over 2x that, so you could pack 2x the number of TLB entries into the same sram block. To match the capabilities of the example above, 57 bits of physical address (cannot be reduced as arbitrary sizes means it's not aligned), plus a similarly reduced to 48 bit object ID and size still adds up to 153, only slightly less than 2x, though I'm sure people could argue that reducing the capabilities here have merit, I don't know how many objects or their maximum possible size in such a system. And that's "worst case" 4k pages for the pagetable system too.
I can't see how this idea could be implemented without extreme limitations - look at the TLB size of modern processors and that's the maximum number of objects you could have while meeting the claims of speed and simplicity. There may be some advantage in making them flexible in terms of size, rather than fixed-size, but then you run into the same fragmentation issues, and need to keep that size somewhere in the extremely-tight TLB memory.
Because that's only a base, not a limit. The right pointer arithmetic can spill over to any other object base's memory.
Doesn't that imply the minimum-sized object requires 4K physical ram?
Is that a problem?
Having arbitrary sizes objects will likely be possible in hardware - it's just an extra size being stored in the PTE if you can mask out the objectID from the address (in the example in the original post, it's a whole 64-bit object ID, allowing a full 64-bits of offset within each object, but totaling a HUGE 128bit effectively address)
But arbitrary sizes feels like it pushes the issues that many current userspace allocators have to deal with today to the hardware/microcode - namely about packing to cope with fragmentation and similar (only instead of virtual address space they'll have to deal with physical address space). The solutions to this today are certainly non-trivial and still can fail in many ways, so far away from being solved, let along solved in a simple enough way to be implemented that close to hardware.
Probably segment registers in x86 can be thought as object identifiers, thus allowing the same non-linear approach?(Isn't that the purpose of segments even?)
Update: BTW, another term for what the author calls "linear" is "flat".
And yeah, it's probably a fixed 64bit lookup into an object descriptor table.
https://en.wikipedia.org/wiki/Rekursiv
I actually have a copy of the book they wrote about it here somewhere. I often fantasize about implementing a version of it in FPGA someday.
Uhm.
Linn the audio company, known as Linn Products, are Scottish, being based a little to the south of Glasgow, and named after the park the original workshop was beside.
Linn the drum machine company, known as Linn Electronics, were American, being founded by and named after Roger Linn.
Two totally different companies, run by totally different people, not connected in any way, and neither of them Swedish.
The Linn Rekursiv was designed by the audio company, and was largely unsuccessful, and none exist any more - not even bits of them :-/
[1] http://www.wolczko.com/mushroom/index.html
Simple: we don't want some low level kernel memory management dictating what constitutes an "object".
Everything isn't object-oriented. E.g. large arrays, memory-mapped files, including executables and libraries.
Linear memory sucks, but every other organization sucks more.
Segmented has been done; the benefit-to-clunk ratio was negligible.
( one reference to thunks involving segmented memory: https://devblogs.microsoft.com/oldnewthing/20080207-00/?p=23... )
The problem was mainly caused by having no MMU, so moving around objects in order to save space required adjusting pointers. Today, a copying garbage collector will do the same thing; rewrite all the links among the moved objects. You'd have similar hacks on Apple Macintoshes, with their MC68K processors and flat space, like doubly indirected objeccts managed by "handles" and whatnot.
Here is a somewhat reasonable diagram of how it all works
https://stackoverflow.com/questions/4039325/assembly-segment...
(although i'm probably agreeing with you)
One pain point in 16-bit Windows programming was that you had to do two special things for any callback function in your application: EXPORT the function in your .DEF file, and call MakeProcInstance() on your callback function to get an "instance thunk".
FixDS made a simple patch to the compiled function prologs that rendered all of this unnecessary. You could just use your callback function directly, like we expect today.
Of course, there are probably lots of in-practice exceptions when it comes to embedded, kernel code, mmap() shenanigans, etc.
This is an extremely simplified and probably incorrect view of https://open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1434r0.... This is complicated because nobody agrees on what the correct behaviour should be, and we have mountains of legacy codebases that all rely on something slightly different when pointers get converted to ints and back.
Rational built a truly semantic IDE, and the result of that is that if you change a line of source-code somewhere in a huge complicated project, it will know precisely what the consequences of that change are.
Ultimately, this allows it often just recompile that single line.
I love the approach, it's a way to get a lot more memory safety while not giving up a program's flexibility, especially in C's case.
Some languages are opting to disallow pointer arithmetic and conversion between integers and pointers. We'll see how it works out!
[0] https://verdagon.dev/blog/generational-references
[1] https://developer.arm.com/-/media/Arm%20Developer%20Communit...
"hey you allocated it you should know about it right?" right yeah
In C++, I think they added enough magic in that you should now be able to do it (placement new, std::launder and numerous other hacks).
My understanding that reusing the storage would violate the aliasing rules[1] and the rules against overlapping object lifetimes.
[1] while char ptrs can be used to access everything, the reverse is not allowed.
[0] https://github.com/microsoft/mimalloc
https://webassembly.org/docs/faq/#what-about-mmap
> Attribute malloc indicates that a function is malloc-like, i.e., that the pointer P returned by the function cannot alias any other pointer valid when the function returns, and moreover no pointers to valid objects occur in any storage addressed by P. In addition, the GCC predicts that a function with the attribute returns non-null in most cases.
But it doesn't provide any operations to do the things in this paragraph (create new pointers). The operation that does this is malloc itself.
This will typically not cause problems, but it would if LTO got so good you could include libc in it.
Olde C used to just let you use integers as struct pointers, and there was only one struct member namespace. so code like this was valid and did an integer-size write to address 0177770. old unix did this for device register access; see the lions book.
struct { int integ; };
f() { 0177770->integ = 012345; }
That doesn't mean we need a memory model in which bits are separate objects, in some sense.
[0] https://news.ycombinator.com/item?id=9807777
Things like TLBs (not a new invention, but going back to the 1960s) really only matter to systems programmers, as he says, and judicious use simplifies and has simplified programming for a long time. I think if he really wants to go down this path he'll discover that the worst case behavior (five probes to find a page) really is worth it in the long run.
However for my simplified comment I said "for this discussion == pages" simply because the difference is simply an extra indirection table in memory, with the segment carrying the access control (like a process address space in unix) and the pages being indexed within it.
All of which was an attempt to say that the post to which we are all commenting is a bit overwrought in its complaint about the worst case search required to find a page. After all, that's what systems programming is all about: the grotty complex plumbing required so other people can worry about the performance of their algorithms that do actual work.
[1] https://en.wikipedia.org/wiki/CAP_computer
That's usually the case. For hardware, at least
For software, it usually was done before by Lisp in the '70s.
That model works, but is not compatible with C and UNIX.
There's some good background here for those who are interested: https://www.smecc.org/The%20Architecture%20%20of%20the%20Bur...
The architecture of the B5000 / B5500 / B6500 lives on today in the Unisys ClearPath line. I believe the OS, MCP, is one of the longest-maintained software operating systems still in active use, too.
So recursive routines get access to their own local variables
I think it's important to understand that it's not a C machine, doesn't have a linear address space in the normal sense
This is worth reading to understand more:
https://people.eecs.berkeley.edu/~kubitron/courses/cs252-F00...
How do I address a variable within a function that was recursed into twice?
http://bitsavers.org/pdf/burroughs/B5000_5500_5700/Organick_...
The Unisys Clearpath line of systems have ISO C compliant compilers, and MCP provides a fairly complete POSIX environment. I've never actually programmed them, but I have the manuals. dlopen is conspicuously missing from the list of POSIX routines. I don't know how close the ISA is to 5500, but at least for Unisys Clearpath the only real incongruity in the environment is that unsigned arithmetic requires compiler-generated instrumentation as integers are sign-magnitude, which doesn't naturally provide the unsigned overflow semantics required by the standard.
ISO C has always tried to steer away from integer/pointer conversions for precisely this reason--pointers are special and might be opaque to the runtime environment. C99 adopted intptr_t, but it was optional and had restricted semantics. There's still no way in standard C to convert a function pointer to an object pointer or to intptr_t. But even in a full POSIX system this limitation only effects dlopen.
Reading the CHERI papers, porting all of FreeBSD to CHERI turned out to be surprisingly easy. dlopen and signals were two of the biggest headaches, IIRC. Very little application code had to change. Playing games with pointers just isn't particularly common in run-of-the-mill Unix applications, or even in open source generally, where writing standards-conformant code has always been valued. (Portability is even more valued, but usually the best way to achieve the latter is through the former.) It's more common in proprietary applications, like games, HPC, embedded, etc.
Sure, but that's not how it works. What does happen is that real-world software written in C doesn't use all those nasty tricks all that often anymore, or isn't that hard to fix. There are a few tricks that _do_ get used, and CHERI provides accommodations for those. Take a look at https://papers.freebsd.org/2019/bsdcan/davis-cheriabi/.
[1] https://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201406...
[2] https://dl.acm.org/doi/pdf/10.1145/641542.641543
Also interesting to me was the idea in Darek Mihocka's blog NO EXECUTE! about using emulation to implement advanced processor features rather than forcing everything through a one size fits all hardware policy. Of course emulation will always have a performance hit, but the concept is interesting.
http://emulators.com/nx_toc.htm
The greater awareness of safety factors brought to light by the book resulted in a culture of safety around automobiles & consumer buying practices that made safety features primary marketing & selling points.
That's all a pretty high bar to reach when using "unsafe at any speed" in the context of address spaces.
The problem with that is that a single error in the fine grained mechanism anywhere in the entire system can quite easily cause complete system compromise. To achieve any safety guarantees requires achieving perfect safety guarantees across all arbitrary code in your entire deployed system. This is astronomically harder than ensuring safety guarantees using virtual memory protection where you only need to analyze the small trusted code base establishing the linear address space and do not need to be able to analyze or even understand arbitrary code to enforce safety and separation.
For that matter, fine grained permissions are a strict superset of the prevailing virtual memory paradigm as you can trivially model the existing coarse grained protection by just making the fine grained protection more coarse. So, if you can make a safe system using fine grained permissions then you can trivially create a safe system using coarse grained virtual memory protection. And, if you can do that then you can create a unhackable operating system right now using those techniques. So where is it?
Anybody who claims to be able to solve this problem should first start by demonstrating a mathematically proven unhackable operating system as that is strictly easier than what is being proposed. Until they do that, the entire idea is a total pipedream with respect to multi-tenant systems.
https://en.wikipedia.org/wiki/Singularity_%28operating_syste... [1]
Joe Duffy has some great blog posts on Midori (OS based on Singularity) here: http://joeduffyblog.com/2015/11/03/blogging-about-midori/
I have been following CHERI. I note that in order to create the first FPGA implementation they had to first define the HDL for a virtual memory system -- all of the research "processor" models that were available did not have working / complete VM implementations. CHERI doesn't replace VM, it is in addition to having VM.
I've found that memory bugs (including virtual memory ones) are difficult to debug, because the error is almost never in the place where the failures show up and there is no easy way to track back who ought to own the object or how long ago the error happened. CHERI can help with this by at least being able to identify the owner.
Virtual memory systems are usually pretty complex. Take a look at the list of issues for the design of L3 <https://pdos.csail.mit.edu/6.828/2007/lec/l3.html>. The largest section there is for creating address spaces. For the Linux kernel, in this diagram a lot of the MM code is colored green <https://i.stack.imgur.com/1dyzH.png>, it is a significant portion. More code means more bugs and much harder to formally verify.
I am not convinced by the argument that it is possible to take a fine grained system and trivially expand it to a coarse grained system. How is shared memory handled, mmap'ed dylibs, page level copy-on-write?
are there alternatives to linearly growing call stacks?
what would the alternative be? compute the size of all the stack frames a-priori in the compiler and then spray them all over main memory and then maintain a linear contiguous list of addresses? doesn't the linear contiguous nature of function call stacks in machine code preserve locality in order to make more efficient use of caches? or would the caches have to become smarter in order to know to preserve "nearby" stack frames when possible?
also, why not just make the addresses wider and put the pid in the high bits? they're already doing this masking stuff for the security descriptors, why not just throw the pid in there as well and be done with it?
When you have a page-based memory model, you've created the importance of address locality. If you have object-based memory model, and the working set is of objects, not pages, then address locality between objects doesn't matter.
Of course, page-based based memory models are by FAR the most common in practice.
(Note: pages ARE objects, but the objects are significant to the VM system and not to your program. So strictly, page-based models are a corner case of object-based models, where the objects are obscure.)
found this on wikipedia: https://resources.sei.cmu.edu/asset_files/TechnicalReport/19...
memory and disk are unified into one address space, code is represented by this "diana" structure which can be compressed text, text, ast or machine code. would be curious how procedures are represented in machine code.
what a fascinating machine!
When you reverse engineer "normal" code, you know the CPU can handle integers of X, 2X, 4X bit widths, you know it wants things aligned this way or that way etc.
The R1000 is bit addressed, and integers can be any width from 1 to 64 bits, structures can be "variant" (See: Ada) so reverse engineering the storage layout is ... not an accomplished feat yet.
Since the primary task for the R1000 was Ada program development, and since there were a standardized semantic representation of Ada programs ("DIANA"), one of the fundamental hardware/microcode data-types is "DianaTree", which is, I think a pretty generic CS tree of some kind.
These "DianaTree" types seem to also have been used for other stuff, like directories in the object store etc.
Early CPUs didn’t have support for a stack, and some early languages such as COBOL and Fortran didn’t need one. They didn’t allow recursive function calls, so return addresses could be stored at fixed addresses, and a return could either be an indirect jump reading from that address or a direct jump whose target address got modified when writing to that fixed address (see https://people.cs.clemson.edu/~mark/subroutines.html for the history of subroutine calls)
Both go (https://blog.cloudflare.com/how-stacks-are-handled-in-go) and rust (https://mail.mozilla.org/pipermail/rust-dev/2013-November/00...) initially had split stacks (https://releases.llvm.org/3.0/docs/SegmentedStacks.html, https://gcc.gnu.org/wiki/SplitStacks)
If you put the pid in the high bits of every pointer you run into problems when you want to support fork(). The child gets a new pid but keeps all the same pointers as its parent.
And that only protects you against one process trying to read/write another process's memory. We already have good support for this type of protection on current hardware/OSes. What is desired is something that prevents a process from reading/writing its own memory, through an out of bounds pointer. This would prevent buffer overflows, stash smashing, etc. and be a good defense against RCE.
This allows threads with very small initial stacks to take turns temporarily reserving a larger stack for doing a rare complex operation.
Outside of reserving the stack, it takes a handful of instructions to call and then return from the temporary stack.
Off the top of my head, current examples of non-contiguous stacks on more familiar system with supporting code compiled directly to machine code (i.e. not language interpreters and VMs, where this is actually very common), include
1) gccgo, which compiles Go code to use split stacks.
2) gcc with -fsplit-stacks, which permits compiling C (and C++?) code which uses the same stack discipline as gccgo.
3) OCaml's new concurrency work utilizes non-contiguous stacks. I'm not familiar with OCaml toolchains, but notably they do generate DWARF and related tables so both debuggers and the garbage collector can properly walk logical stacks. See https://arxiv.org/abs/2104.00250
4) There's a stack-smashing and ROP prevention technique call shadow stacks, where a single logical call stack is implemented using two contiguous stacks, one primarily for return addresses (or related metadata) and the other primarily for objects. See https://en.wikipedia.org/wiki/Shadow_stack Both GCC and clang support software-implemented shadow stack disciplines (SafeStacks), and some newer Intel and ARM ISA extensions implement hardware-enforced shadow stacks.
Well, GPU code is certainly not object-oriented, and I hope it never becomes that. SIMD code won't be able to jump between objects like typical CPU-oriented OOP does (unless all objects within a warp/workgroup jump to the same function pointers?)
GPU code is common in video games. DirectX needs to lay out its memory very specifically as you write out the triangles and other vertex/pixel data for the GPU to later process. This memory layout is then memcopy'd over to PCIe using the linear address space mechanism, and GPUs are now cohesive with this space (thanks to Shared Virtual Memory).
So today, thanks to shared virtual memory and advanced atomics, we can have atomic compare-and-swap coordinate CPU and GPU code operating over the same data (and copies of that data can be cached in CPU-ram or GPU-VRAM and transferred over automatically with PCIe memory barriers and whatnot).
----------
Similarly, shared linear address spaces operate over rDMA (remote direct memory access), a protocol built on top of Ethernet. This means that your linear memory space is mmap'd on your CPU, but then asks for access to someone else's RAM over the network. The mmap then causes this whole "inefficient pointer-traversals" to then get turned into Ethernet packets to share RAM between CPUs.
Ultimately, when you start dealing with high-speed data-sharing between "external" compute units (ie: a GPU, or a ethernet-connected far-away CPU), rather than "just" a NUMA-node or other nearby CPU, the linear address space seems ideal.
--------
Even the most basic laptop, or even Cell Phone, these days, is a distributed system consisting of a CPU + GPU. Apple chips even have a DSP and a few other elements. Passing data between all of these things makes sense in a distributed linear address space (albeit really wonky with PCIe, mmaps, base address pointers and all sorts of complications... but they are figured out, and it does work every day)
I/O devices working directly in memory is going to only become more common. 100Gbps network connections exist in supercomputer labs, 10Gbps Ethernet is around the corner for consumers. NVMe drives are pushing I/O to such high bandwidths that'd make DDR2 RAM blush. GPUs are growing more complicated and are rumored to start turning into distributed chiplets soon. USB3.0 and beyond are high-speed links that directly drop off data into linear address spaces (or so I've been told). Etc. etc.
I think the broader point is that you can build an "object-oriented" system in the sense that you're expecting overtop of the "object-based" systems he is describing and it will give you much of the base level semantics of an OO system (object allocation, tagging, encapsulation) without enforcing any particular OO language semantics (inheritance, typing, methods, etc.) and while also allowing for non-OO (blob of memory) semantics if you need it.
Think of each C allocation via malloc/free as an object. It's just in his system the pointers that point to those allocations are not describable as a series of integer offsets into a big linear memory, but really are handles or unique IDs which map directly into the VM subsystem of the OS and to some action happening in the MMU.
In essence most object-oriented language VMs/runtimes are doing this themselves, essentially building abstract handles (object references, etc.) overtop of the "linear memory" abstraction that the OS provides. If I understand his gist he's really just talking about cutting out the middleman.
I suspect, though, that there's not really a lot of efficiency gains anyways. This path has been so heavily optimized (in both hardware and software) over the decades that it likely matters little.
The security argument maybe is more compelling. There's good argument for the concept of never being able to turn an integer into a pointer or into an integer and back again. Except this would break probably the majority of C programs out there.
Maybe the middle road is for the OS to present a sandboxed "legacy" or "emulation" environment for programs that do pointer arithmetic and to provide enhanced compilers that flag these kinds of things and encourage/offer alternatives.
Given the prevalence of virtualization tech now, there's probably more room for experimentation in this type of thing these days without breaking compat...
https://www.gnu.org/software/libc/manual/html_node/Obstacks....
“An obstack is a pool of memory containing a stack of objects. You can create any number of separate obstacks, and then allocate objects in specified obstacks. Within each obstack, the last object allocated must always be the first one freed, but distinct obstacks are independent of each other.
Aside from this one constraint of order of freeing, obstacks are totally general: an obstack can contain any number of objects of any size. They are implemented with macros, so allocation is usually very fast as long as the objects are usually small. And the only space overhead per object is the padding needed to start each object on a suitable boundary.”
There isn't a lot of info about them though. Go hunting for performance metrics on them, or discussion of them generally and you won't find much. The glibc pages themselves don't give much justification why you would use them vs malloc, or an arena allocator, etc.
Jonathan Blow has been experimenting a lot with arrays of structs versus structs of arrays, particularly in making them both first class instead of assuming one and ignoring the other. This is essentially the column- versus row-oriented data question answered with a question: why not both?
I think if you had a first class language that supported both, that you wouldn't mind so much if GPU code became object oriented.
I don’t know why not both, is it maybe because one of the two layouts will almost always have worse performance for any given access pattern? I can see uses for having both for the non-critical-path parts, though maybe once you’re indexing it in the awkward but perf-friendly way, you’ve already done the hard work and there’s little point to proving the other style of indexing? (Isn’t the best perf always found using whatever layout & indexing is the most difficult… there must be some eponymous law for this, right?) I guess it is possible to have multiple critical paths each favoring a different layout. Not sure how often I’ve ever seen that in practice, I would guess it’s probably rather rare.
What if 90% of these objects should be compactly slab allocated, but you also run small, very disjointed numbers of them through an editor or an undo list or whatever and so they need to live separate from this array?
I don't know what the answer is, but I feel like a few good candidates will come out of the conversations started by Rust. You can't replace an object with a new object while it's globally readable. But if you own the parent object, you can rewrite it however you want, or whichever ways are compatible with the other invariants you want for the system, like max time per frame or response time.
Sure you can. This is the whole point of smalltalk become: and common lisp CHANGE-CLASS.
We are talking about retaining the type and swapping the pointers from an independent object to a set of offsets into a struct of arrays.
You are making a big assumption. Neither common lisp nor smalltalk specify the semantics of concurrent programs, but it is certainly possible to implement such a feature without, as you say, concurrency gotchas. Perhaps a better example is concurrently compacting gcs for java.
Let's say you're iterating over position coordinates of some set of objects in a game. With an array-of-structs you can lose ou on cache locality if unrelated fields are nearby. If you use a struct-of-arrays you get cache locality advantages anytime you do something like "iterate over this 1 field for each object"
The latter approach is called data oriented programming btw, and seems to have been around for a while. Andrew Kelley gave a good talk about it recently while using Zig: https://media.handmade-seattle.com/practical-data-oriented-d...
Shared Virtual Memory is literally "GPU sees X region the same as the CPU sees it". And is implemented on all desktop GPUs today: https://www.intel.com/content/www/us/en/developer/articles/t...
By making pointers treated the same on CPU or GPU (by allowing their 64-address spaces to be identical by sharing the same memory regions + using PCIe to keep those memory regions in sync), you can perform high-speed CPU / GPU communications of even linked data structures (linked lists, trees, graphs).
GPUs utilize many linked data-structures. Oct-trees accelerate bounds testing, BVH trees help raytracing. Etc. etc. The GPU addresses must be linear because they're synchronized to the CPU's memory space.
If you want to talk to a GPU via vulkan or d3d12 you're going to navigate a maze of descriptor sets, pipeline objects, buffers of various types, samplers, etc. These are all Objects with distinct types and data and the GPU hardware will interact with them in specific ways, even if it's also a general purpose computing device that will run some shader code you throw at it. When I was writing bare-metal graphics code for the PS4 there was still a lot of Object Orientation there too even if there weren't vtables or a garbage collector involved.
Seeing RAM as a collection of linear addresses on GPUs (especially as shared virtual memory, pinned memory, or other such GPU/CPU virtual memory sharing features) is a feature from 2010-era, be it from OpenCL, DirectCompute, or CUDA.
DirectCompute just sees the data as a collection of bytes.
Building a new competitive processor architecture isn't feasible if you can't at least ensure compile-time compatibility with existing programs. People won't buy a processor that won't run their programs.
On the Mill the whole processor bank uses a global virtual address space. TLB and mapping to physical memory happens at the memory controller. Everything above the memory controller is in the same virtual address space, including L1-L3+ caches. This solves a lot of problems, for example: If you go out to main memory you're already paying ~300 cycles of latency, so having a large silicon area / data structure for translation is no longer a 1-cycle latency problem. Writes to main memory are flushed down the same memory hierarchy that reads come from and succeed as soon as they hit L1. Since all cache lines are in the same virtual address space you don't have to track and synchronize reads and writes across translation zones within the cache hierarchy. When you request an unallocated page you get the whole pre-zeroed page back instantly, since it doesn't need to be mapped to physical pages until writes are flushed out of L3. This means its possible for a page to be allocated, written to, read, and deallocated which never actually touches physical memory throughout the whole sequence and the whole workload is served purely within the cache hierarchy.
Protection is a separate system ("PLB") and can be much smaller and more streamlined since it's not trying to do two jobs at once. The PLB allows processes to give fine-grained temporary access of a portion of its memory to another process; RW, Ro, Wo, byte-addressed ranges, for one call or longer etc. Processes get allocated available address space on start, they can't just assume they own the whole address space or start at some specific address (you should be using ASLR anyways so this should have no effect on well-formed programs, though there is a legacy fallback).
[1]: My previous comment: https://news.ycombinator.com/item?id=27952660
Honestly, I'm happy waiting for 4k pages to die and be replaced by huge pages. Page tables were added to the x86 architecture in 1985, when 1MB of memory was a ton of memory to have. Having 256 pages worth of memory in your computer was weird and exotic. Fast forward to today, and the average user has several GB of memory - mainstream computers can be expanded to over 128 GB today - and we still mainly use 4k pages. That is the problem here. If we could swap to 2M pages in most applications, we would be able to reduce page table sizes by a factor of 512, and they would still be a lot larger than page tables when virtual memory was invented. And we wouldn't waste much memory!
But no, 4k pages for backwards compatibility. 4k pages forever. And while we're at it, let's add features to Linux (like TCP zero copy) that rely on having 4k pages.
We also didn't have access to the code that set up the page tables. Somehow I got the linker to emit a function hook which I used to defrag the page tables after they were written but before the MMU was enabled.
I remember thinking, "This is not what I learned about in school."
That was nuts to me. It could have been 0.
AKA, both X86 and ARM (as do various other processors) have intermediate bits in their page directory structures that flag 'instead of using another level of PTE/etc below this level assume we are just pointing at an equal size physical range" which on x86-64 can be 2M or 1G. Given the latest Intel x86's have a multilevel TLB, with 8 1G L1 entries, and 1K of L2 TLB entries it should be fairly straightforward to fix with appropriate huge page tweaks unless your data structure exceeds a TB. And even if it does, keeping everything in 1G pages means that the data caches should be able to keep the top level global page directory/etc cached avoiding main ram hits, and resulting in fairly quick TLB refills.
If you have any interest at all in the design of CPUs and instruction sets, I recommend viewing the entire series of video lectures by Ivan Godard:
https://www.youtube.com/playlist?list=PLFls3Q5bBInj_FfNLrV7g...
Warning: Viewing these is likely to make you at least a little bit upset with the current state-of-the-art architectures.
The first two points are similar to other Poul-Henning Kamp articles [1]. The last two are more interesting.
I'm inclined to agree with "CHERI good". Memory safety is a huge problem. I'm a fan of improving it by software means (e.g. Rust) but CHERI seems attractive at least for the huge corpus of existing C/C++ software. The cost is doubling the size of pointers, but I think it's worth it in many cases.
I would have liked to see more explanation of how capability-based pointers replacing virtual memory would actually work on a modern system.
* Would we give up fork() and other COW sorts of tricks? Personally I'd be fine with that, but it's worth mentioning.
* What about paging/swap/mmap (to compressed memory contents, SSD/disk, the recently-discussed "transparent memory offload" [2], etc)? That seems more problematic. Or would we do a more intermediate thing like The Mill [3] where there's still a virtual address space but only one rather than per-process mappings?
* What bookkeeping is needed, and how does it compare with the status quo? My understanding with CHERI is that the hardware verifies provenance [4]. The OS would still need to handle the assignment. My best guess is the OS would maintain analogous data structures to track assignment to processes (or maybe an extent-based system rather than pages) but maybe the hardware wouldn't need them?
* How would performance compare? I'm not sure. On the one hand, double pointer size => more memory, worse cache usage. On the other hand, I've seen large systems spend >15% of their time waiting on the TLB. Huge pages have taken a chunk out of that already, so maybe the benefit isn't as much as it seemed a few years ago. Still, if this nearly eliminates that time, that may be significant, and it's something you can measure with e.g. "perf"/"pmu-tools"/"toplev" on Linux.
* etc
[1] eyeroll at https://queue.acm.org/detail.cfm?id=1814327
[2] https://news.ycombinator.com/item?id=31814804
[3] http://millcomputing.com/wiki/Memory#Address_Translation
[4] I haven't dug into how when fetching pointers from RAM rather than pure register operations, but for the moment I'll just assume it works, unless it's probabilistic?
A lot of C/C++ code assumes that pointers are integers are pointers, so I dunno how big the corpus would actually be. People will cast between them but that's not the end of it, they will also make unions, and they will memcpy from one to another. It wouldn't surprise me if there is a lot of code that even assumes pointers are exactly 64-bit wide.
So, it's not like you can't typecast; rather, there are some specific things the hardware will prevent you from doing, eg '(void *)42' - if you force clang to accept it, it will crash at runtime due to missing tag.
CHERI C programming guide might be helpful: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-947.pdf
The fork(2) isn't a problem when running like this, but it does become a problem if you want to colocate processes in a single address space. It's not as much of a problem as I'd previously expect: there's vfork(2) and posix_spawn(2); fork is only a problem until subsequent execve(2); and also because many systems don't support fork(2) anyway, userspace had to adapt.
As for performance: there are some (somewhat old) numbers at https://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201904..., measured on FPGA; benchmarks on real silicon are still pending.
Yeah, he's proposing...something else. It's not clear to me exactly what, except sort of like this obscure historic machine he vaguely described. See e.g. this paragraph:
> The linear address space as a concept is unsafe at any speed, and it badly needs mandatory CHERI seat belts. But even better would be to get rid of linear address spaces entirely and go back to the future, as successfully implemented in the Rational R1000 computer 30-plus years ago.
That is absolutely terrifying.
https://datamuseum.dk/wiki/Fil:R1000_s100_Backplane_2.jpg
The metal blocks at the bottom is where the welding cables from the PSUs connect.
To read more about the R1000, start here:
https://datamuseum.dk/wiki/Rational/R1000s400
There’re some limitations about them, on Windows the process needs a special security privilege, also these pages are never swapped to a page file. But still, AFAIK when programmers really need the performance, like in a database engine, they do use these things when available.
Then we get the ZFS extent allocator, written mostly by the same programmer (Jeff Bonwick).
https://en.m.wikipedia.org/wiki/Slab_allocation
Doing tagged slab allocation seems like a reasonable thing for a hardware microarchitecture to consider.
The article starts by complaining about modern CPU complexity, five-level page tables to maintain the illusion of a linear, uniform memory space.
Then goes on to juxtapose that complexity with the an architecture that would use that complexity to support tagged memory objects more directly, part of the system ABI.
If we're going to spend all of our time manipulating memory objects anyway, why mess around?
Was the Intel iAPX so much of a disaster, compared to a modern x86_64 architecture, that we are forever forbidden to even consider such hardware?
https://en.m.wikipedia.org/wiki/Intel_iAPX_432
Vale's "Fearless FFI" designs [0] says we could sandbox entire third-party libraries using a WebAssembly compilation step, which might work well. Sometimes I wonder what would happen if we made an entire OS using Vale, and what kind of security improvements it might bring.
[0] https://verdagon.dev/blog/fearless-ffi
It has been done. See Singularity project from Microsoft Research, which used C# as the language to provide memory protection, no process, all programs running in the same global memory space, and all of them running in ring-0. It was a fun research project, but never really made it out. There were other research projects like it.
Also his (object, offset) addressing space is essentially a segmented memory model. The object id is the segment id. I bet the object id is in a linear space.
Heck, I'd argue everyone who writes their own toy OS should probably start with this approach and then retrofit memory protection later because it simplifies things tremendously and you get something actually usable much earlier (context switching between is not that hard but it's complicated, especially on x86).
Of course, you can do identity memory mapping and skip virtual vs physical questions (for x86, memory protection requires using virtual memory, because the protection information is in the page tables, and iiuc, amd64 also requires using virtual memory, but it's still a useful simplification to do identity mapping so the virtual address is the physical address). My toy OS only runs one process, so there was never going to be more than one memory map anyway.
The problem is basically the choice of C#. If today people use WASM, with no process distinctions, same address space, all in ring0 it would already be a much more successful project.