Hacker News Reader

Comment by yvdriess | Hacker News Reader

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.

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.

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

There is also Levy's book https://homes.cs.washington.edu/~levy/capabook/

One of the original brains behind the R1000 has mentioned that the B5500 was one of the inspirations, but my personal impression is that he was talking more about the stack-based (vs. register-based) instruction set, than the memory management.

How would you address recursive functions this way?

Burroughs machines have 2 sorts of pointers - effectively pointers to offsets on the stack (indexed by a full display so you can do full algol scope semantics, more than just C) as well as pointers to heap memory (base and bounds, with paging for large objects)

So recursive routines get access to their own local variables

Sorry I meants "Can you give me an example of an address to a stack pointer where you are allowed to make recursive calls"?

I'm not quite sure what you mean - the Burroughs machines have full sets of display registers (hardware managed pointers to each of the stack frames that were currently in scope - Algol/etc had more complex scoping that modern C-style languages) - a stack pointer contained a lexical level (an index into the display registers) and an offset into that stack frame - there's a variant that's 'stuffed' (essentially a reference to a variable in a stack frame that's out of scope - based on the base of stack)

I think it's important to understand that it's not a C machine, doesn't have a linear address space in the normal sense

This is worth reading to understand more:

https://people.eecs.berkeley.edu/~kubitron/courses/cs252-F00...

> Addresses were not plain numbers; they were more like Unix paths, as in /program/function/variable/arrayindex.

How do I address a variable within a function that was recursed into twice?

you create an in-scope reference within the function - and then 'stuff' it which converts it into an offset from the base of the stack - converts an "indirect reference word" into a "stuffed indirect reference word"

it's what you use to pass by reference ..... but algol supports pass-by-name semantics (of which pass by reference is an optimisable subset) - to do fill pass by name (for a simple example a[i] where i is a global) the compiler will create a thunk (a tiny subroutine, in scope of the place where the parameter was passed) and pass a pointer to it - the tag of '7' means a PCW - when it gets dereferenced as a pointer the hardware does a subroutine call to the thunk in the correct scope

Detailed exposition here:

http://bitsavers.org/pdf/burroughs/B5000_5500_5700/Organick_...

> That model works, but is not compatible with C and UNIX.

The Unisys Clearpath line of systems have ISO C compliant compilers, and MCP provides a fairly complete POSIX environment. I've never actually programmed them, but I have the manuals. dlopen is conspicuously missing from the list of POSIX routines. I don't know how close the ISA is to 5500, but at least for Unisys Clearpath the only real incongruity in the environment is that unsigned arithmetic requires compiler-generated instrumentation as integers are sign-magnitude, which doesn't naturally provide the unsigned overflow semantics required by the standard.

ISO C has always tried to steer away from integer/pointer conversions for precisely this reason--pointers are special and might be opaque to the runtime environment. C99 adopted intptr_t, but it was optional and had restricted semantics. There's still no way in standard C to convert a function pointer to an object pointer or to intptr_t. But even in a full POSIX system this limitation only effects dlopen.

Reading the CHERI papers, porting all of FreeBSD to CHERI turned out to be surprisingly easy. dlopen and signals were two of the biggest headaches, IIRC. Very little application code had to change. Playing games with pointers just isn't particularly common in run-of-the-mill Unix applications, or even in open source generally, where writing standards-conformant code has always been valued. (Portability is even more valued, but usually the best way to achieve the latter is through the former.) It's more common in proprietary applications, like games, HPC, embedded, etc.

You lose the advantages of the tagged hardware when you declare a giant array of raw memory to be managed by C.

>You lose the advantages of the tagged hardware when you declare a giant array of raw memory to be managed by C.

Sure, but that's not how it works. What does happen is that real-world software written in C doesn't use all those nasty tricks all that often anymore, or isn't that hard to fix. There are a few tricks that _do_ get used, and CHERI provides accommodations for those. Take a look at https://papers.freebsd.org/2019/bsdcan/davis-cheriabi/.

Doesn't clearpath C really test ones assumptions about the sizes of pointers Vs function pointers etc?

Worth noting that CHERI _is_ definitely compatible with C and Unix; the default operating system for it is CheriBSD, a FreeBSD fork, and there is a growing number of purecap packages.

True, the CHERI paper[1] cites the Burroughs as well. Amusingly, it cites an article similar to the OP: "The architecture of the Burroughs B5000: 20 years later and still ahead of the times?"[2] - written in 1982...

[1] https://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201406...

[2] https://dl.acm.org/doi/pdf/10.1145/641542.641543

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

Reply on news.ycombinator.com