49 ms·

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

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/
  - phkamp 4y ago
    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.
- heavenlyblue 4y ago
  How would you address recursive functions this way?
  - Taniwha 4y ago
    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
    - heavenlyblue 4y ago
      Sorry I meants "Can you give me an example of an address to a stack pointer where you are allowed to make recursive calls"?
      - Taniwha 4y ago
        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/handouts/papers/burroughs.pdf https://people.eecs.berkeley.edu/~kubitron/courses/cs252-F00...
        heavenlyblue 4y ago
        > 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?
- wahern 4y ago
  > 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.
  - Animats 4y ago
    You lose the advantages of the tagged hardware when you declare a giant array of raw memory to be managed by C.
    - trasz 4y ago
      >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/ https://papers.freebsd.org/2019/bsdcan/davis-cheriabi/.
- trasz 4y ago
  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.
- ajb 4y ago
  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-isca2014-cheri.pdf https://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201406... [2] https://dl.acm.org/doi/pdf/10.1145/641542.641543 https://dl.acm.org/doi/pdf/10.1145/641542.641543
monocasa 4y ago
IBM didn't really play with hardware object capabilities until the S/38, and even the it's a bit of a stretch to call them that.

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/
- phkamp 4y ago
  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.
heavenlyblue 4y ago
How would you address recursive functions this way?
- Taniwha 4y ago
  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
  - heavenlyblue 4y ago
    Sorry I meants "Can you give me an example of an address to a stack pointer where you are allowed to make recursive calls"?
    - Taniwha 4y ago
      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/handouts/papers/burroughs.pdf https://people.eecs.berkeley.edu/~kubitron/courses/cs252-F00...
      - heavenlyblue 4y ago
        > 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?
wahern 4y ago
> 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.
- Animats 4y ago
  You lose the advantages of the tagged hardware when you declare a giant array of raw memory to be managed by C.
  - trasz 4y ago
    >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/ https://papers.freebsd.org/2019/bsdcan/davis-cheriabi/.
trasz 4y ago
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.
ajb 4y ago
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-isca2014-cheri.pdf https://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201406... [2] https://dl.acm.org/doi/pdf/10.1145/641542.641543 https://dl.acm.org/doi/pdf/10.1145/641542.641543

monocasa 4y ago

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