21 ms·

Linear Address Spaces: Unsafe at any speed

271 points by g0xA52A2A 4y ago

cmrdporcupine 4y 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.
- kimixa 4y 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.
- KerrAvon 4y ago
  No idea, but consider that it could be a enum + bitfield rather than strictly an enum.
- robotresearcher 4y 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 4y 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.
- phkamp 4y 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.
  - cmrdporcupine 4y ago
    Ok thanks for the clarification
gpderetta 4y 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.
- gumby 4y 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.
- monocasa 4y 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.
- KerrAvon 4y 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/ https://archive.org/details/432_complexity_paper/
- kps 4y ago
  They did the BiiN (i960MX) in the '80s.
  - gpderetta 4y ago
    The "Billions Invested In Nothing" project :).
StillBored 4y 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 4y 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 4y 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.
gralx 4y ago
Link didn't work for me. Direct link did: https://dl.acm.org/doi/abs/10.1145/3534854 https://dl.acm.org/doi/abs/10.1145/3534854
mwcremer 4y 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 https://dl.acm.org/doi/10.5555/2665671.2665740) increases code safety by treating pointers and integers as distinct types.
throw34 4y 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.pdf 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.
- cmrdporcupine 4y 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 4y ago
kimixa 4y 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.
- monocasa 4y 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.
avodonosov 4y 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".
- monocasa 4y 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.
  - marshray 4y 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)?
    - monocasa 4y ago
      I came this close to ordering custom "Make the LDT Great Again" hats after spectre was released, lol.
cmrdporcupine 4y 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 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 4y 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 :-/
  - cmrdporcupine 4y ago
    oops :-)
- kwhitefoot 4y ago
  Surely Linn is Scottish.
- rjsw 4y ago
  Maybe also look at MUSHROOM [1]. [1] http://www.wolczko.com/mushroom/index.html http://www.wolczko.com/mushroom/index.html
kazinator 4y 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 4y 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=23533 https://devblogs.microsoft.com/oldnewthing/20080207-00/?p=23... )
  - kazinator 4y 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.
    - StillBored 4y ago
      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 https://stackoverflow.com/questions/4039325/assembly-segmented-model-32bit-memory-limit https://stackoverflow.com/questions/4039325/assembly-segment... (although i'm probably agreeing with you)
  - 4y ago
gumby 4y 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 4y ago
  I think Multics had both segments and pages.
  - gumby 4y 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 4y ago
CHERI is a gamechanger
ajb 4y 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 https://en.wikipedia.org/wiki/CAP_computer
- yvdriess 4y 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.
  - Animats 4y 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.
    - EvanAnderson 4y ago
      You beat me! CHERI totally made me think about those machines. There's some good background here for those who are interested: https://www.smecc.org/The%20Architecture%20%20of%20the%20Burroughs%20B-5000.htm 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.
      - ratmice 4y ago
        There is also Levy's book https://homes.cs.washington.edu/~levy/capabook/ https://homes.cs.washington.edu/~levy/capabook/
      - 4y ago
martincmartin 4y 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.
- ineedasername 4y 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 4y 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 4y ago
    Nader's book was also click bait. The Corvair was not any more dangerous in practice than any of its contemporaries.
    - ineedasername 4y ago
      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.
    - projektfu 4y ago
      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.
Veserv 4y 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 4y 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_system%29 https://en.wikipedia.org/wiki/Singularity_%28operating_syste... [1]
  - Genbox 4y 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/ http://joeduffyblog.com/2015/11/03/blogging-about-midori/
a-dub 4y 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?
- fulafel 4y 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).
- robotresearcher 4y ago
  A stack is a list of objects with a LIFO interface. Doesn't have to be a contiguous byte sequence.
  - a-dub 4y 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?
    - robotresearcher 4y ago
      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.)
dragontamer 4y 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.
- cmrdporcupine 4y 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.
edave64 4y 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.
infogulch 4y 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 https://news.ycombinator.com/item?id=27952660
- pclmulqdq 4y 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.
scottlamb 4y 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 https://queue.acm.org/detail.cfm?id=1814327 [2] https://news.ycombinator.com/item?id=31814804 https://news.ycombinator.com/item?id=31814804 [3] http://millcomputing.com/wiki/Memory#Address_Translation 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 4y 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.
akdor1154 4y 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 4y 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 4y 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.
- phkamp 4y ago
  We have a picture of the s100 backplane here: https://datamuseum.dk/wiki/Fil:R1000_s100_Backplane_2.jpg 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 https://datamuseum.dk/wiki/Rational/R1000s400
jart 4y 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 4y 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 4y ago
An intro to CHERI: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-941.pdf https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-941.pdf
watersb 4y 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 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 https://en.m.wikipedia.org/wiki/Intel_iAPX_432
verdagon 4y 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 https://verdagon.dev/blog/fearless-ffi
ww520 4y 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 4y 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 4y 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 4y 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.
bogomipz 4y 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.
- projektfu 4y 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.
  - bogomipz 4y ago
    Thanks. Was the MIPS R2000 one of the RISC designs that became really complicated then?
    - projektfu 4y ago
      Yeah, MIPS eventually supported SIMD instructions and the MIPS16 short-length instructions. I'm sure other things were thrown in there. Other instruction sets inspired by early RISC also added lots of things. Most have stayed true to the fundamental separating memory instructions from arithmetic instructions. What makes an instruction set CISC, in my opinion, is allowing memory operands in arithmetic. Most RISC instruction sets also provide lots of registers to avoid reuse. The idea is generally that the compiler should be responsible for optimally scheduling instructions. But then, modern RISC are usually out-of-order processors anyway.
perryizgr8 4y 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?
phkamp 4y 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 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 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 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 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 http://datamuseum.dk/aa/r1k_backup/85/85b414c73.html
- larsbrinkhoff 4y ago
  I drove by Copenhagen the other day! Ah well, another time.
  - phkamp 4y ago
    Ping me next time you're in our area, I'll be more than happy to give you a tour!
phkamp 4y 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.
- eru 4y 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/33100-1/papers/hotos-jeremiad.pdf 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.
  - phkamp 4y 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.
anonymoushn 4y 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 4y 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 4y 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 https://en.wikipedia.org/wiki/X86_memory_segmentation
pabs3 4y ago
I wonder what the author thinks of the design of the Mill architecture. https://millcomputing.com/ https://millcomputing.com/

271 points by g0xA52A2A 4y 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.

kimixa 4y 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.
KerrAvon 4y ago
No idea, but consider that it could be a enum + bitfield rather than strictly an enum.
robotresearcher 4y 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 4y 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.
phkamp 4y 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.
- cmrdporcupine 4y ago
  Ok thanks for the clarification

gpderetta 4y 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.

gumby 4y 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.
monocasa 4y 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.
KerrAvon 4y 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/ https://archive.org/details/432_complexity_paper/
kps 4y ago
They did the BiiN (i960MX) in the '80s.
- gpderetta 4y ago
  The "Billions Invested In Nothing" project :).

StillBored 4y 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 4y 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 4y 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.

gralx 4y ago

Link didn't work for me. Direct link did: https://dl.acm.org/doi/abs/10.1145/3534854 https://dl.acm.org/doi/abs/10.1145/3534854

mwcremer 4y 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 https://dl.acm.org/doi/10.5555/2665671.2665740) increases code safety by treating pointers and integers as distinct types.

throw34 4y 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.pdf 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.

cmrdporcupine 4y 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 4y ago

kimixa 4y 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.

monocasa 4y 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.

avodonosov 4y 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".

monocasa 4y 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.
- marshray 4y 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)?
  - monocasa 4y ago
    I came this close to ordering custom "Make the LDT Great Again" hats after spectre was released, lol.

cmrdporcupine 4y 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 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 4y 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 :-/
- cmrdporcupine 4y ago
  oops :-)
kwhitefoot 4y ago
Surely Linn is Scottish.
rjsw 4y ago
Maybe also look at MUSHROOM [1]. [1] http://www.wolczko.com/mushroom/index.html http://www.wolczko.com/mushroom/index.html

kazinator 4y 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 4y 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=23533 https://devblogs.microsoft.com/oldnewthing/20080207-00/?p=23... )
- kazinator 4y 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.
  - StillBored 4y ago
    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 https://stackoverflow.com/questions/4039325/assembly-segmented-model-32bit-memory-limit https://stackoverflow.com/questions/4039325/assembly-segment... (although i'm probably agreeing with you)
- 4y ago

gumby 4y 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 4y ago
I think Multics had both segments and pages.
- gumby 4y 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 4y ago

CHERI is a gamechanger

ajb 4y 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 https://en.wikipedia.org/wiki/CAP_computer

yvdriess 4y 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.
- Animats 4y 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.
  - EvanAnderson 4y ago
    You beat me! CHERI totally made me think about those machines. There's some good background here for those who are interested: https://www.smecc.org/The%20Architecture%20%20of%20the%20Burroughs%20B-5000.htm 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.
    - ratmice 4y ago
      There is also Levy's book https://homes.cs.washington.edu/~levy/capabook/ https://homes.cs.washington.edu/~levy/capabook/
    - 4y ago

martincmartin 4y 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.

ineedasername 4y 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 4y 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 4y ago
  Nader's book was also click bait. The Corvair was not any more dangerous in practice than any of its contemporaries.
  - ineedasername 4y ago
    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.
  - projektfu 4y ago
    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.

Veserv 4y 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 4y 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_system%29 https://en.wikipedia.org/wiki/Singularity_%28operating_syste... [1]
- Genbox 4y 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/ http://joeduffyblog.com/2015/11/03/blogging-about-midori/

a-dub 4y 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?

fulafel 4y 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).
robotresearcher 4y ago
A stack is a list of objects with a LIFO interface. Doesn't have to be a contiguous byte sequence.
- a-dub 4y 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?
  - robotresearcher 4y ago
    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.)

dragontamer 4y 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.

cmrdporcupine 4y 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.

edave64 4y 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.

infogulch 4y 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 https://news.ycombinator.com/item?id=27952660

pclmulqdq 4y 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.

scottlamb 4y 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 https://queue.acm.org/detail.cfm?id=1814327 [2] https://news.ycombinator.com/item?id=31814804 https://news.ycombinator.com/item?id=31814804 [3] http://millcomputing.com/wiki/Memory#Address_Translation 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 4y 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.

akdor1154 4y 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 4y 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 4y 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.
phkamp 4y ago
We have a picture of the s100 backplane here: https://datamuseum.dk/wiki/Fil:R1000_s100_Backplane_2.jpg 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 https://datamuseum.dk/wiki/Rational/R1000s400

jart 4y 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 4y 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 4y ago

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

watersb 4y 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 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 https://en.m.wikipedia.org/wiki/Intel_iAPX_432

verdagon 4y 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 https://verdagon.dev/blog/fearless-ffi

ww520 4y 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 4y 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 4y 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 4y 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.

bogomipz 4y 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.

projektfu 4y 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.
- bogomipz 4y ago
  Thanks. Was the MIPS R2000 one of the RISC designs that became really complicated then?
  - projektfu 4y ago
    Yeah, MIPS eventually supported SIMD instructions and the MIPS16 short-length instructions. I'm sure other things were thrown in there. Other instruction sets inspired by early RISC also added lots of things. Most have stayed true to the fundamental separating memory instructions from arithmetic instructions. What makes an instruction set CISC, in my opinion, is allowing memory operands in arithmetic. Most RISC instruction sets also provide lots of registers to avoid reuse. The idea is generally that the compiler should be responsible for optimally scheduling instructions. But then, modern RISC are usually out-of-order processors anyway.

perryizgr8 4y 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?

phkamp 4y 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 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 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 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 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 http://datamuseum.dk/aa/r1k_backup/85/85b414c73.html

larsbrinkhoff 4y ago
I drove by Copenhagen the other day! Ah well, another time.
- phkamp 4y ago
  Ping me next time you're in our area, I'll be more than happy to give you a tour!

phkamp 4y 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.

eru 4y 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/33100-1/papers/hotos-jeremiad.pdf 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.
- phkamp 4y 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.

anonymoushn 4y 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 4y 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 4y 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 https://en.wikipedia.org/wiki/X86_memory_segmentation

pabs3 4y ago

I wonder what the author thinks of the design of the Mill architecture. https://millcomputing.com/ https://millcomputing.com/