Linear Address Spaces: Unsafe at any speed

https://queue.acm.org/detail.cfm?id=3534854

by g0xA52A2A • 4 years ago

271 240 4 years ago

queue.acm.org

gralx• 4 years ago

Link didn't work for me. Direct link did:

https://dl.acm.org/doi/abs/10.1145/3534854

mwcremer• 4 years ago

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.

throw34• 4 years ago

"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.

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.

cmrdporcupine8• 4 years ago

"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.

bentcorner• 4 years ago

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.

nine_k2• 4 years ago

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.

mikepavone4• 4 years ago

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

phkamp20• 4 years ago

You are right that there is no lessons for "modern machines" as we build them now.

But that is precisely my point: Maybe there are better ways to build them ?

phkamp20• 4 years ago

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.

gpderetta7• 4 years ago

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.

cmrdporcupine8• 4 years ago

"The R1000 has many interesting aspects ... the data bus is 128 bits wide: 64-bit for the data and 64-bit for data's type"

what what what?

How on earth would you ever need to have a type enumeration 2^64 long?

Neat, though.

kimixa3• 4 years ago

The other option is to use those 64bits to double the total bandwidth in the "Traditional" page-table system.

All this extra complexity and bus width doesn't come for free, after all, there's opportunity cost.

KerrAvon2• 4 years ago

No idea, but consider that it could be a enum + bitfield rather than strictly an enum.

robotresearcher3• 4 years ago

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.

GUIDs for types.

btilly• 4 years ago

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.

phkamp20• 4 years ago

The type descriptions contain much more than that, for instance valid range for integers, field layout for structures and so on. Also privacy information.

cmrdporcupine8• 4 years ago

Ok thanks for the clarification

gpderetta7• 4 years ago

At Intel they probably still have nightmares about iAPX 432. They are not going to try an OO architecture again.

Having said that, I wouldn't be surprised if some form of segmentation became popular again.

gumby3• 4 years ago

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.

monocasa5• 4 years ago

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.

KerrAvon2• 4 years ago

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).

https://archive.org/details/432_complexity_paper/

kps• 4 years ago

They did the BiiN (i960MX) in the '80s.

gpderetta7• 4 years ago

The "Billions Invested In Nothing" project :).

kimixa3• 4 years ago

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.

monocasa5• 4 years ago

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.

marshray2• 4 years ago

with the "object ID" just being the masked first part of the address?

Doesn't that imply the minimum-sized object requires 4K physical ram?

Is that a problem?

kimixa3• 4 years ago

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.

mikepavone4• 4 years ago

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

avodonosov• 4 years ago

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".

monocasa5• 4 years ago

Yeah, x86 segments in the protected modes were intended to be used as a hardware object capability system like the author is getting at.

And yeah, it's probably a fixed 64bit lookup into an object descriptor table.

marshray2• 4 years ago

Wouldn't it be hilarious if the 21st century brought about the re-adoption of the security design features introduced in the 80286 (1982)?

cmrdporcupine8• 4 years ago

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.

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.

Gordonjcp• 4 years ago

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 :-/

cmrdporcupine8• 4 years ago

oops :-)

kwhitefoot• 4 years ago

Surely Linn is Scottish.

rjsw• 4 years ago

Maybe also look at MUSHROOM [1].

[1] http://www.wolczko.com/mushroom/index.html

kazinator7• 4 years ago

Why do we even have linear physical and virtual addresses in the first place, when pretty much everything today is object-oriented?

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.

MarkSweep• 4 years ago

The benefit-to-thunk ratio was not great either.

( one reference to thunks involving segmented memory: https://devblogs.microsoft.com/oldnewthing/20080207-00/?p=23... )

kazinator7• 4 years ago

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.

Stratoscope• 4 years ago

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.

323• 4 years ago

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.

gary_03• 4 years ago

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.

kazinator7• 4 years ago

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.

bawolff• 4 years ago

Perhaps im misunderstanding, but it seems like you are using object-oriented in a different sense than the article does

MaxBarraclough• 4 years ago

I'm reminded of an old comment that expressed a similar sentiment: we've discovered over time that OS Kernels aren't the place for Grand Abstractions.

[0] https://news.ycombinator.com/item?id=9807777

gumby3• 4 years ago

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.

pinewurst• 4 years ago

I think Multics had both segments and pages.

gumby3• 4 years ago

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.

anewpersonality• 4 years ago

CHERI is a gamechanger

ajb2• 4 years ago

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.

[1] https://en.wikipedia.org/wiki/CAP_computer

yvdriess• 4 years ago

Are you sure it wasn't done before by IBM in the '60s?

That's usually the case. For hardware, at least

For software, it usually was done before by Lisp in the '70s.

Animats2• 4 years ago

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.

monocasa5• 4 years ago

IBM didn't really play with hardware object capabilities until the S/38, and even the it's a bit of a stretch to call them that.

projektfu4• 4 years ago

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.

http://emulators.com/nx_toc.htm

martincmartin• 4 years ago

"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.

ineedasername2• 4 years ago

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.

loeg• 4 years ago

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).

cjensen• 4 years ago

Nader's book was also click bait. The Corvair was not any more dangerous in practice than any of its contemporaries.

Veserv• 4 years ago

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.

potatoalienof13• 4 years ago

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

https://en.wikipedia.org/wiki/Singularity_%28operating_syste... [1]

Genbox• 4 years ago

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.

Joe Duffy has some great blog posts on Midori (OS based on Singularity) here: http://joeduffyblog.com/2015/11/03/blogging-about-midori/

VogonPoetry• 4 years ago

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?

seoaeu• 4 years ago

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.

a-dub3• 4 years ago

Why do we even have linear physical and virtual addresses in the first place, when pretty much everything today is object-oriented?

are there alternatives to linearly growing call stacks?

robotresearcher3• 4 years ago

A stack is a list of objects with a LIFO interface. Doesn't have to be a contiguous byte sequence.

a-dub3• 4 years ago

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?

fulafel2• 4 years ago

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).

dragontamer3• 4 years ago

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.

cmrdporcupine8• 4 years ago

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.

roelschroeven• 4 years ago

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.

teddyh2• 4 years ago

Yes, see for instance the GNU C Library “obstacks” facility; It’s clearly not object-oriented:

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.”

hinkley4• 4 years ago

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.

dahart• 4 years ago

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.

fulafel2• 4 years ago

And AOS/SOA are not the only organiations, textures eg are often stored in a zig zag or tile style (traditionally called "swizzling" there).

kllrnohj2• 4 years ago

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.

dragontamer3• 4 years ago

GPUs only speak in objects, never linear addresses.

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.

kg• 4 years ago

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.

dragontamer3• 4 years ago

relatively new and modern

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.

edave64• 4 years ago

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.

infogulch2• 4 years ago

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).

[1]: My previous comment: https://news.ycombinator.com/item?id=27952660

pclmulqdq2• 4 years ago

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.

rsaxvc2• 4 years ago

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."

Symmetry3• 4 years ago

The obvious thing to do is put the address translation between the CPU cache and system level cache.

ansible• 4 years ago

Agree completely.

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.

infogulch2• 4 years ago

Reading over the article and this thread again, I realize that this isn't the 'opposite direction', this is exactly what the article is aiming at.

scottlamb3• 4 years ago

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.

* 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?

im3w1l• 4 years ago

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.

scottlamb3• 4 years ago

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.

trasz6• 4 years ago

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.

CHERI C programming guide might be helpful: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-947.pdf

trasz6• 4 years ago

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 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.

scottlamb3• 4 years ago

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.

akdor1154• 4 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.

That is absolutely terrifying.

buildbot• 4 years ago

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!

jacquesm• 4 years ago

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.

phkamp20• 4 years ago

We have a picture of the s100 backplane here:

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

jart• 4 years ago

You can avoid the five levels of indirection by using "unreal mode". I just wish it were possible to do with 64-bit code.

Const-me• 4 years ago

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.

eternalban• 4 years ago

An intro to CHERI: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-941.pdf

watersb• 4 years ago

The Slab Allocator for Linux keeps an object tag for each slab, which can be of different sizes.

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

verdagon2• 4 years ago

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.

[0] https://verdagon.dev/blog/fearless-ffi

ww520• 4 years ago

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.

Joker_vD• 4 years ago

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).

toast0• 4 years ago

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.

kccqzy• 4 years ago

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.

pjmlp2• 4 years ago

Only because WASM's cargo cult that nothing like it ever came to be, thus its hipster adoption.

IshKebab• 4 years ago

I don't think using WASM would prevent spectre attacks so this idea is not really viable anymore.

bogomipz2• 4 years ago

"Show me somebody who calls the IBM S/360 a RISC design, and I will show you somebody who works with the s390 instruction set today."

Could someone explain this quote to me? I don't know enough about the IBM S/360 to understand this.

projektfu4• 4 years ago

Me neither. S/360 was CISC by every definition. It was a pretty clean design and could scale from small to big systems. Over time it acquired instructions to achieve things in hardware as desired by its designers and users.

I think they were really poking fun at RISC and how complicated the instruction sets became to support real world desires. We're a long way from the MIPS R2000.

bogomipz2• 4 years ago

Thanks. Was the MIPS R2000 one of the RISC designs that became really complicated then?

perryizgr8• 4 years ago

Physically, RAM chips have transistors in linear arrangments, one after the other.

Storage cell #1,334,455,224 is physically next to storage cell #1,334,455,223. Both may contain data from different "objects", or not. That does not change the physical reality.

Having a representation of reality in your system/software can be helpful in many cases. A nefarious example would be if you were attempting to write a rowhammer attack. How would you do that if the computer cannot reason about the physical location of storage cells in RAM?

phkamp20• 4 years ago

Hi everybody!

About the R1000:

We have pretty comprehensive user-side documentation of the R1000, but very, very little from the system/vendor side, so lots of things we simply do not know yet.

We have digitized everything we have here:

https://datamuseum.dk/wiki/Bits:Keyword/RATIONAL_1000

And our top-level wiki-page for the project is here:

https://datamuseum.dk/wiki/Rational/R1000s400

All the doc we have about the hardware type/object stuff and instruction set is in these course-slides:

https://datamuseum.dk/bits/30000916

If you are into data-archaeology and lack for challenges, we have several good outstanding questions for research. For instance the layout of the object-store/filesystem.

If you want to see a R1000 running, and experience the worlds first truly semantic IDE, come to Datamuseum.dk just outside Copenhagen, because we have the only approx 1.83 running R1000 computers.

(We also just started fundraisning for a new permanent building for our huge collection, we are at €113K of €3M goal. See top right corner or homepage or email.)

We know of only four surviving computers, we have two, one is privately owned in NZ and IBM donated one to CHM. The rest have been shredded because of classified mil-spec workload.

If you are local to/affiliated with CHM, and are interested/allowed, we would love to know more about their machine, and if possible, assist to get that running too.

PS: Here is a piece of Ada source code:

http://datamuseum.dk/aa/r1k_backup/13/1329b5ea7.html

And this may be what it compiles into:

http://datamuseum.dk/aa/r1k_backup/85/85b414c73.html

larsbrinkhoff• 4 years ago

I drove by Copenhagen the other day! Ah well, another time.

phkamp20• 4 years ago

Ping me next time you're in our area, I'll be more than happy to give you a tour!

phkamp20• 4 years ago

About Flat vs. Object stores

I wrote this piece, frustrated by, what looks to me, like the entire semiconductor industry is only exploring one single computer storage organization, despite the fact that recent inventions like flash practically begs for innovation.

For instance few people realize that the Flash Adaptation Layer in the SSD devices means that we literally run two filesystems on top of each other, because nobody has seriously tried to get rid of the "a disk is an array of individually rewritable sectors" despite this literally being untrue both for modern disks and in particular for Flash based storage.

Similarly, the "flat physical/flat virtual" MMU model is a relic from the days of IBM 360 and VAX 11/780 and utterly inefficient and unsuitable for what we do in userland these days.

As Robert has shown with CHERI, there is plenty of space to innovate without breaking existing code.

And yes, C can be object oriented, all you have to do is keep your hands from the primitives which are necessary to access hardware directly.

Architectually GPU's are a superoptimized distraction, like the vector-units on Cray and Convex computers were 40-50 years ago, but those too can function in a non-flat address-space.

But even C in OO-mode, and C++, Go, Rust, PHP and for that matter LISP and SmallTalk, would benefit from an HW/MMU architecture which focused on delivering fast object service, rather than flat address-spaces which software must then convert into objects.

But to innovate, we must first realize that we are currently stuck in a box, and dare to look outside it.

eru4• 4 years ago

Thanks for writing the article and explaining some background here.

Are you familiar with exokernels? They were an attempt to remove abstractions from kernel land and leave that to applications.

See https://www.classes.cs.uchicago.edu/archive/2019/winter/3310...

That way innovation can be much faster, because applications can generally move quicker than kernels.

Btw, I'm not a fan of object orientation; and I don't think our hardware design should be infected by that fad. But I think your criticism of the badly fitting abstraction of flat address spaces is still valid. I am just not sure that 'fast object service' is necessarily the remedy.

phkamp20• 4 years ago

I'm not a fan of any archtectural radicalism, and tend to think that there are things best done in both hardware, kernel and libraries and applications :-)

That is not to say that the boundaries should be cast in stone, they should obviously be flexible enough that you do not need a complete multi-user management system in a single-service jail or container nor a full-blown journaled COW storage-manager on a small embedded system.

In other words: I am firmly for the "Software Tools" paradigm.

zasdffaa6• 4 years ago

It's a rant and it's not information heavy. I've never heard of this processor (and provide a link, don't tell me to look it up).

Other OO processors: Rekursiv (https://en.wikipedia.org/wiki/Rekursiv) and that famously slooow intel iAPX 432 (https://en.wikipedia.org/wiki/Intel_iAPX_432)

Interesting but neither (esp. the latter) were known as racehorses.

I'd prefer to keep the hardware simple and fast and push the complexity into the software, and prove stuff.

would benefit from an HW/MMU architecture which focused on delivering fast object service, rather than flat address-spaces which software must then convert into objects.

That conversion may not be cheap (edit: badly phrased, the object mapping process and hardware may not be cheaper (edit again: = faster) than that mapping done by the MMU for conventional memory) - can you exaplain how it would be done such that it would be cheaper in time than the current mapping in the common/hot/optimistic path, and how it would not be worse than it is now on the rare/cold/pessimistic path? And how it would behave on average, between those 2 extremes?

And why objects everywhere would be better all-round?

klelatti• 4 years ago

On the subject of the iAPX 432 is anyone aware of an emulator? The only material I’ve seen is quite high level and doesn’t go down to ISA level.

p_l• 4 years ago

iAPX 432 arguably wasn't bad due to OOP orientation, but due to a bunch of several issues in how intel went about executing the idea. To the point that if they mismanaged a "normal" cpu this way they would have bungled it similarily.

kragen9• 4 years ago

Probably if you haven't heard of CHERI and can't be bothered to Google it when one of the most respected systems architects around tells you it's worth looking at, you aren't going to put in the effort needed to read the CHERI tech reports so you can have an informed opinion on the performance cost of putting this kind of protection into hardware. And if the only historical "OO" processors you can think of are Rekursiv and iAPX432, and not the Dorado or the Symbolics line or the B5000/B5500/ClearPath line, it sounds like you have a lot of reading to do to get to having an informed opinion.

benreesman3• 4 years ago

It’s a big thread (by virtue of being a cool piece), so maybe someone said this already, but isn’t there kind of a middle ground where we let existing software continue to run but acknowledge a changing hardware landscape by really cranking up (default) page sizes?

Userland allocators already work pretty hard to hit in the TLB [1], but huge-page tuning and whatnot is, to your point, only hitting the sweet spot on modern gear via effort/luck.

[1] https://engineering.fb.com/2011/01/03/core-data/scalable-mem...

phkamp20• 4 years ago

I think that is a false dictomy.

CHERI has shown that this kind of fundamental architectural improvements can happen with very little impact to running code.

Symmetry3• 4 years ago

Channeling my inner Linux, defaulting to larger pages means a drastic loss in memory efficiency when mmaping lots of small files as happens when someone compiles the Linux kernel. If you've got a 2kb file and 4kb pages then half the memory you allocate when the file is paged in is wasted. For larger pages that goes way up.

FunnyBadger• 4 years ago

This is correct.

A lot of this due to the hardware architecture itself. The software abstractions dictated/limited by the HW itself causes many of the risks!

If you designed BOTH HW and SW up to and including the OS, you _might_ have a chance to control the risks better. But by the very separation of duties and roles, papered over by abstraction itself, you create problems. ALL abstractions throw away information and eventually those abstractions bite you in the ass.

This was the case with digital logic once HW speeds rose to a critical level - suddenly the reality that digital is merely an abstraction upon analog and the very abstraction of lumped-model analog started failing which caused digital fail as well.

We definitely can have and have had the same failure occurring with von Neumann architecture - there's NOTHING magical about it that immunizing against model abstraction failure and it can creation "intrinsic failures" that can never be fixed thanks to Gödel's incompleteness theorem.

titzer2• 4 years ago

I am very sympathetic to this argument overall and trace the hardware industry's failure back to the spread of C, UNIX, and worse-is-better.

With Wasm I see an opportunity to virtualize away the old world of C and linear address spaces. While we designed it to be low level and sandboxed to get C/C++ and Rust on board, I and others have always had in mind a future world where Wasm has managed (GC'd) data, first-class typed functions, and more. Those features should support a wide variety of source languages.

Wasm should become the new, final ISA. It should become like Unicode; the final, most widely-supported[1] format for executable code. When all languages and programs can run easily on Wasm, then hardware can easily be swapped out.

[1] Sure, Unicode has flaws, and it doesn't support everything equally as well. But it had the property that basically everyone dropped everything else in favor it, because it gained all the momentum.

duped• 4 years ago

As I understand it, wasm modules depend heavily on linear memory in growable buffers in each module.

kazinator7• 4 years ago

Re: flash.

A flash adaptation layer solves the following problem: I have M filesystems, that I'd like to use on any one of N different flash technologies. I don't want to complicate each M filesystem with support for N flashes.

I don't think both layers are "filesystem" in the same sense. We don't need the lower filesystem to provide permissions, ownerships, time stamps, directories, symbolic links and such.

Re: linear

A machine address is a word of bits. A word of bits always has a linear interpretation as a binary number. For instance if we have a 16 bit segment ID, and a 32 bit offset, then we can still pretend that it's a 48 bit linear address. We can compare two pointers for inequality, for instance: p0 < p1, as 48 bit words. That space may be sparsely populated, but that doesn't make it nonlinear; the spaces you are calling linear can also be sparsely populated and have numeric conventions about regions.

You say physical memories are linear, but they are also sparsely populated in the same way: such and such a range is a ROM, such and such a range is certain memory mapped registers, DRAM is over there. Generally speaking, hardware treats some part of an address as an ID that it recognizes, and then the bits below that as an offset. When there is a bus read or write, if the ID part matches that hardware device, then it selects itself for that I/O operation, and uses the offset bits to provide access to the right thing. So physical memory is arguably nonlinear; it is like a subclassed IP address space.

Physical addresses can have bits which are not used for addressing; e.g. a certain range of memory might be available as uncached if you enable a certain upper bit in the address. That looks like linear, but with aliasing between distant regions. Linear virtual memory is sparsely populated; there are mapped pages and unmapped pages. Pages can alias: the same object can be mapped in multiple places, so a write here can be read there.

If you want to split an address into an object ID and offset, you have to gamble about how many bits you need for each one. One application has hundreds of millions of tiny objects: it wants a big object ID part of the address, and a small offset. Another one has a small number of huge objects: it doesn't care for large object ID, but wants big offsets. Either you make that configurable (slow gets even slower), or else waste bits on making both spaces larger at the same time, perhaps ending up with wasteful 128 bit pointers on a system where 64 is more than enough.

All interpretations of the bits of an address above and beyond "pure binary number" add complication and overhead. The hardware (e.g. DMA bus master) isn't going to understand objects; it will always want a simple address.

Re: C, C++, Go, Rust, PHP, Lisp, Smalltalk

No two implementations of these can agree with each other on what exactly is an object. Implementations will just carry their existing respective portable object representations into the non-linear model. Architectures without flat memory, like the JVM and WebAssembly, tend to only cause pain for Lisp and its ilk.

A Lisp is not going to want some weird object model from the operating system; it will want to do things like packing cons cells tightly together into one larger heap object. That heap object could be a segment. We had those; they are also from the 1960's. Operating systems started ignoring them, opting for just the demand paging support the VM hardware.

rkangel2• 4 years ago

A flash adaptation layer solves the following problem: I have M filesystems, that I'd like to use on any one of N different flash technologies. I don't want to complicate each M filesystem with support for N flashes.

I think you could argue that certain file system designs are better suited to different storage hardware. Maybe it's appropriate that the kernel runs different code depending on the underlying storage type?

We already have JEDEC standards for flash devices to report block layout, because it's important in microcontrollers where there is no adapation layer. We could have an SSD/M2 standard that reported that information, and then architecturally kernel FS stuff would probably split into a couple of layers. The 'top' that provides the filesystem features that you're used to in something like ZFS, and the bottom storage layer that has a couple of different implementations for 'linear' and 'blocks'.

phkamp20• 4 years ago

No, that is actually not what the Flash Adaptation Layer does.

The FAL's primary job is to make the Flash array look like a disk, despite the fact that individual "sectors" are not individually rewriteable.

To do this, the FAL implements which is for all practical purposes a filesystem, where the files are all a single sector long and where the filename is the sector number exposed by the "disk".

In other words: Now we have two filesystems on top of each other, one lying to the other, which does a lot of unnecessary work, because it is being lied to.

anonymoushn2• 4 years ago

Huge pages cause 10-20% speedups for all sorts of applications by nearly eliminating the pain of looking at a bunch of page tables all the time. Unfortunately they are completely unusable on Windows even though it's been at least 26 years since they first shipped in consumer CPUs.

nielsbot• 4 years ago

This article makes me wonder, now that Apple makes its own CPUs and owns the "whole widget" if they might do something more radical with their CPU architecture. They could build in Swift-specific hardware support for example. Apple could get an "unfair" power and performance advantage over their CPU competition.

ur-whale• 4 years ago

Why do we even have linear physical and virtual addresses in the first place

Mmmh, there was a time when PC's had non-linear memory [1]

Coding for this was IIRC an effing nightmare.

[1] https://en.wikipedia.org/wiki/X86_memory_segmentation

pabs3• 4 years ago

I wonder what the author thinks of the design of the Mill architecture.

https://millcomputing.com/

StillBored4• 4 years ago

Its amazes me that articles like this can talk about obscure architectures, and now CHERI but completely fail to notice that just about every PC in use is actually a lightweight capability machine! AKA all that "cruft" everyone complains about in ia32, you know the LDT/GDT/IDT, the variable length segments referenced there, the selector+offset (aka CS, SS, ES, DS, FS, GS) format maps perfectly to the concept of a data structure, and its offset. The task gates, call gates, interrupt gate etc all are there to support a proper per segment security model.

We have these machines, although granted over the past few decades those mostly unused operations have gotten quite slow, and the model harkens back to a time where people didn't have a lot of ram, so there aren't a lot of "caches" (aka segment registers/etc) in place to support modern computing.

Which is why I find these articles amusing, suddenly its in vogue to rediscover what most computer architects of the 60-80's were doing, until RISC and UNIX basically destroyed it all, with leaky abstractions and insecure designs.

And since the PC is just a pile of legacy garbage no one looks at it close enough to discover they have the HW sitting on their desk to try out some of these ideas.

peter_d_sherman• 4 years ago

"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."

Nice! (This is nothing short of a miracle considering that this technology originated in the 1980's and was built with TTL!)

pvillano• 4 years ago

so right now we have

process thinks it has a linear memory to itself, imagines it can write anywhere. writes trigger the expansion of a complex sparse tree data structure transparently converts virtual linear address space to non-contiguous actual locations in main memory

the R1000 is

program can repeatedly ask for an x KiB page, is given an id, which is actually an index into an array that holds the actual RAM address. data is fetched with an id+offset, which is range/pid checked against metadata in the array. the ids a program gets back aren't guaranteed to be sequential. BUT the array is dense, which is why no tree structure is needed.

dynamic stacks have a little extra work to do, a data return pointer in addition to an instruction return pointer.

Linear Address Spaces: Unsafe at any speed

Related Stories