Single Address Space Operating System | Hacker News Reader

Single Address Space Operating System

c2.com

72 pointsluu50 comments

Jeff Chase (http://www.cs.duke.edu/~chase/) was one of the authors on the 'Architectural Support for Single Address Operating Systems' paper in '92. I read that when I was at Sun and thought it was pretty amazing. It shaped a lot of my thinking about what the world would look like when we got to ubiquitous 64 bit address spaces.

That change is coming. You can statically link to addresses in that world. It makes for some really interesting optimizations in terms of code which falls through into optimizations in terms of JITs.

Do you have any insight for what the security implications would be (if any) for an OS like this?

Security is pretty solid in terms of things like libraries where every library entry point is a call to a particular address. That eliminates a number of dynamic linking vulnerabilities. Every process can have its own memory prefix (rather than everybody thinking they are at 0) which gives better visibility to memory incursion and excursions. Kernel space is distinct address from non-kernel space etc (this got really challenging on non-64 bit machines at the end of their reign)

Is it a net win? I think so, there would clearly be new ways in which it would be a challenge but you can make some useful reasoning about validity of addresses with a numerical compare that isn't nearly as efficient in a variable address OS.

Every process can have its own memory prefix (rather than everybody thinking they are at 0)

The way you describe this, it sounds like segmentation. Wouldn't the value of each processing having a memory prefix be that all its internal data would think they have an offset of zero?

I was thinking more along the lines of being able to do binary arithmetic on pointers for validation,

   ptr & prefixmask != prefix

means its out of range. That is a pretty cheap optimization, VMS and SunOS both used that sort of check in kernel space to insure that the kernel wasn't about to dereference a pointer outside of kernel space (potentially in some random process).

You could use something like Native Client to run multiple protected "processes" in a single address space.

The Apple Newton did this; used a single address space and some fine-grain protection capabilities of the MMU to get proper security. It was . . . okay, but it's unclear what the performance hit would have been if we had run out of hardware-level protection IDs (there were 15 or 16 domains, IIRC). ARM later deprecated the MMU features that we used (and properly so, I think).

There's a 1994 COMPCON paper on it.

Not only that, but the early ARM architecture was terrible at running unix or other non-single address space OS's.

If I remember correctly, the caches were virtually tagged, even on the StrongARM, making context switching on linux very expensive.

Tagged TLBs should make multitasking faster, not slower, unless I don't catch your meaning at all. On a non-tagged cache you have to dump the entire thing whenever you change address spaces. With tags you lazily invalidate only the entries that aren't part of the active virtual id.

Different kind of tagging.

salem is referring to how addresses are compared in the cache: http://en.wikipedia.org/wiki/CPU_cache#Virtual_tags_and_vhin...

you are referring to ASIDs which are the mechanism by which different address spaces can share space in the TLB at the same time: http://www.helenos.org/doc/design/html.chunked/mm.html#id253...

The very first versions of the Linux kernel (i386) did it too. Each process got 64MB of address space with a limit of 63 processes. It made task switching really fast since it was just twiddling some MMU related pointers.

Indeed, and here it is: http://waltersmith.us/newton/COMPCON-OS.pdf (I also updated the c2 wiki.)

The MMU features were available on ARMs for a surprisingly long time, and I remember seeing at least one embedded OS other than Newton that used them.

As shown in the article the system i from IBM (aka AS/400) is an example of this architecture. Originally 48bit it moved to 64bit when the RISC (power) processors came to the forefront. Yet that memory model is only element to the longevity and flexibility of the platform.

However their best trick was keeping the machine code and OS so separate than when migrating to RISC from CISC you didn't even need the source code for the majority of code running on the system to migrate.

The apps and most of the OS are distributed as the equivalent of high level byte code using 128 bit pointers. Once run it gets translated into the local machine code.

For anyone unfamiliar with the AS/400 and predecessors I highly recommend the expensive book by Frank Soltis who is largely the architect of it. Many things were done very differently than other operating systems and applications. http://www.amazon.com/Inside-AS-400-Second-Edition/dp/188241...

A 128bit address space would be fun. Of course as the page mentions, if you want to use IPv6 for this, you actually want something more like a 196bit address space or just round it up to a 256bit address space.

Imagine all the world's computers running in a single unified address space. All network access is abstracted away, loading a resource is as simple as loading a memory address.

It would be like a new golden era for C! Rather than using URIs or some sort of XML addressing schema or whatever else people decide to invent, instead, all the world's information and knowledge from all around the world (solar system, universe?) is available through one unified address space.

Although I imagine we'd still need some sort of DNS system running on top. ;)

Imagine all the world's computers running in a single unified address space. All network access is abstracted away, loading a resource is as simple as loading a memory address.

The standard rebuttal to this thinking is Waldo et al. "A Note on Distributed Computing" from 1994. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7...

"We argue that objects that interact in a distributed system need to be dealt with in ways that are intrinsically different from objects that interact in a single address space. These differences are required because distributed systems require that the programmer be aware of latency, have a different model of memory access, and take into account issues of concurrency and partial failure."

In nearly 20 years of building distributed systems, this has held true every. single. time. Trying to abstract away the distributed nature of a system inevitably leads to pain and sorrow. I think having explicit knowledge about what is local and what is remote is critical, but having a single, universal address space, so any application can reference any resource, anywhere, when it logically needs to, would be great. They are just different things.

I'd argue that at this point one has to be aware of latency and concurrency on the local system also, and any programming model ignores this at their peril.

It's the greatness of the potential of failure/hang on all actions that separates local RAM access from distributed computing. You don't generally need to worry about your app hanging indefinitely because of a memory read.

While true, there's enough orders of magnitude in play that the same mechanisms can only rarely be optimal for both. Reaching into a chunk of NUMA space you don't own vs. reaching out to a highly-contended hard drive on the other side of the world are forever likely to be too different to unify.

Compare order of magnitude for register access versus cache versus RAM versus HDD.

With page files, all of those are treated the same by the programmer.

Local HDD can already have access latency similar to the local network!

It is another order of magnitude to go beyond that. Meh.

Reliability is, IMHO, the bigger issue.

"Local HDD can already have access latency similar to the local network!"

Right, there are situations where "in RAM on that other computer" is closer than "on my disk".

"With page files, all of those are treated the same by the programmer."

In many cases we just don't care, because a CPU hooked up to RAM is still pretty fast for many use cases. When you do care, this abstraction is actually a huge problem!

I think this demonstrates my point, not refutes it.

It might be more interesting to treat these things as a memory mapped device, and just cough up whatever is currently there rather than fetching (blocking!) at every access. Would quite obviously have its own issues, though.

> All network access is abstracted away

Which is a BAD thing, because it's one hell of a leaky abstraction.

http://en.wikipedia.org/wiki/Fallacies_of_Distributed_Comput...

Working in embedded, I am used to assuming most of those working with just local resources.

> 1.The network is reliable.

I don't assume my file system is reliable. Flash fails.

> 2.Latency is zero.

Latency is non-0 even on local access! My team's requirements is that anything that may take more than ~1ms is done async. This includes memcopy!

> 3.Bandwidth is infinite.

Never has been, even locally.

> 4.The network is secure.

Local busses are not secure either.

> 5.Topology doesn't change.

I'll give'em that, although this is hopefully less of a problem now days, ignoring NATs...

> 6.There is one administrator.

Again, the industry has hopefully evolved to understand finer grained access controls.

> 7.Transport cost is zero.

Nope, never has been even locally. You doing something consumes resources from someone else.

> 8.The network is homogeneous.

Half the fun is in things being heterogeneous! Put work where it is best done at.

"It would be like a new golden era for C!"

Well, it'd certainly be a new golden era for DRAM manufacturers as every pointer in the system bloats up to 8x original size just to support a 0.1% use case...

Microsoft's Singularity http://en.wikipedia.org/wiki/Singularity_(operating_system) project was able to eschew the MMU and use verification to prove that programs couldn't harm the kernel or each other.

Structuring a kernel like this makes the micro-kernel idea much more palatable as context switch overheads drop dramatically.

Here's a crazy idea: single addresss space for the kernel, virtual memory for applications in userland since their memory grows more unpredictably. I guess this dual approach would need hardware support?

"40 bits can address a terabyte, two orders of magnitude beyond the primary and secondary storage capacity of all but the largest systems today"

Couldnt' help but smile when I read this.

I've just been learning about OSv from Cloudius Systems. More than just a single address space they have a single process (intended to run as a KVM guest). It makes some interesting optimizations possible and they get some incredible results: memcached, unmodified, runs faster in their KVM guest than it does on the bare metal. It seems limiting at first, but for the right use case their approach is really worth a look.

Surprised no one has mentioned that the Lisp Machine operating system worked this way.

Maybe it doesn't count because there was no protection against intentional reading or writing of memory belonging to other apps or the OS. But the protections against unintentional writing were good enough to make for a remarkably robust system, in a time when nobody cared about security.

For anyone interested, the Lisp Machine OS was called Genera:

http://en.wikipedia.org/wiki/Genera_%28operating_system%29

Fascinating thing.

This is basically what VxWorks (real-time OS) started doing in their 6.x series - the MMU is active and all memory addresses are virtual, but no two processes get access to the same virtual address range. That way you can debug with virtual addresses turned on and see page faults instead of whatever hilarity ensues from overwriting the operating system itself, then turn the MMU off and stop taking the execution speed hit of translating addresses. It turns out that almost everyone just leaves memory protection on all the time anyway, since duh, it's the only sane thing to do.

Fun fact, the most reliable indicator that you have this kind of setup is whether the Unix emulation layer (if present) offers fork() - if only one process can access a given address then you obviously can't create a copy of a process that uses pointers.

How is the process isolation implemented in such a setup ?

The traditional approach is to flush the tlb and load new a new memory map on a context switch in order implement isolation , though what you're talking about sounds like something else.

Henry M Levy's relevant 1984 book, Capability-Based Computer Systems, is available free in PDF form on the author's web site: http://homes.cs.washington.edu/~levy/capabook/

I was disappointed that there was no real discussion of why you would want to do this. I see some potential for interesting optimizations, but that's ... it.

In short, private virtual addressing is legacy cruft from a time when this was the only way to organize things due to a constrained memory block identifier namespace.

Think about it like IPv4 vs. IPv6, i.e. hacks like NAT, vs. "everything has its own IP address in a single flat address space of IPs".

It's the same, but with computer memory. And it has the same benefits.

That's true but I think the bigger reason is that a single address space makes system calls as cheap as regular function calls, since there is no kernel boundary any more.

Ironically, VxWorks's latest major rev was all about turning memory protection on since overwhelmingly people prefer the performance hit of kernel calls over the heisenbugs that come from stomping on the kernel's code and data structures.

But, like you said, you still need protection of kernel data, which means that you need to execute kernel code on a stack not writeable by the user, at a greater permission level that allows ONLY the kernel code to modify kernel pages. Single-address-space or not I can't see these needs being met in a cheaper way than what we already have, presuming that kernel code/data are in never-invalidated global pages available in every address space.

Edit: Oh, I see from your other comment that you're talking about the benefits to people who don't feel this need.

I'm still not seeing the real benefits.

What, specifically, is bad/wrong about the traditional way of doing process isolation, and what does this approach bring to the table ?

The folks at Microsoft Research who worked on Singularity claim the so called "Unsafe Code Tax" from the existing system is a 30-40% performance hit.

http://webcourse.cs.technion.ac.il/236376/Spring2013/ho/WCFi...

Sorry if this is a stupid question (I don't fully understand SASOS), but would an OS that does this make ROP chain exploitation easier?

It should not. The exploit cannot access any more libraries or addresses compared to traditional layout.

One bonus not mentioned in the article is context switches no longer need to flush the TLB (the MMU's cache which is indexed by virtual address). Thus you don't lose the cache entries for shared libraries or kernel space.

Could this be retrofitted onto any mainstream OS? I guess the answer is "no" for Unix, because of fork(). But how about Windows?

The mill CPU [1] has a single address space and they plan to port linux to it.

[1] http://millcomputing.com/

Amiga was fun.

I still miss Marble Madness and Hole-in-one Miniature Golf.

And Tom Rokicki was a god.

I thought that at first too, but the link isn't about architectures like the Amiga or Mac OS 9 that ran without any memory protection from other processes. Memory is still virtualized and protected like modern systems, but it also gives every process a unique address space, so that pointers are unique across the system.

Kind of an interesting idea. Seems like it would pair well with the NixOS way of doing things…

There are at least a couple of AROS developers that wants to retrofit some level of memory protection onto AROS (which is API compatible with AmigaOS), while remaining single address space.

In Amigaland virtual memory is still seen as a quaint but passing fad.

I mean, how are you going to write your own interrupt handlers and schedule your own DMA transfers if you can access neither the CPU's interrupt vector nor the custom chip registers from your process's address space?

Imagine this for our brains...

Reply on news.ycombinator.com