23 ms·

Memory safety without borrow checking, reference counting, or garbage collection

111 points by modernerd 3y ago

rurban 3y ago
Now he just needs to look into parrot (the old perl6 vm) or pony, which do expand on single ownership and compiler-checked move semantics. Not just memory safe, but also concurrency safe. Concurrent Pascal was also similar.
- Hardliner66 3y ago
  I think Pony is one of the most interesting languages out there. I love actors, I love capabilities, I love whitelisting of C/C++ usage. Sadly no armv7 support, cross compiling itself is really hard too (never got it to work), the package management support is weird and deviates quite a bit from mainstream (IIRC having multiple versions of the same dependency is a feature ) and it lacks users. I honestly would love to have a mix between rust and pony.
- perlgeek 3y ago
  Too bad nobody was ever able to build a practical, concurrent programming language on top of parrot. (Nor any well-performing non-concurrent language, for that matter). And quite a few talented compiler writers tried (I'm thinking of Patrick Michaud and Jonathan Worthington at least, probably forget quite a few).
Hardliner66 3y ago
The example somehow reminds me of proof carrying code. If you obtain memory in pcc, you also get a proof that the memory is valid. If you want to use the memory, you need to pass the proof as well. Finally, the proof must be disposed and the only function that can do that for memory is free. This can be done for the reminder example as well.
davidatbu 3y ago
A great read! Might be worth pointing out: leptos, a Rust WASM UI library, uses the "store an index (or ID) into some central data structure" idea extensively. Sycamore, another Rust WASM UI library, has been using arena allocation, but will also be transitioning into the leptos approach in coming versions. (I believe) this is partly because the borrow checker's enforcement of a tree-like data structures / ownership doesn't always work well with the JS event loop.
- aatd86 3y ago
  Interesting. So basically the index storage is a way to create a reference to an object that is not compiler checked?
  - davidatbu 3y ago
    I would say that it's a way to trade compile-time checks of reference validity for runtime-checks of reference validity.
- danielheath 3y ago
  I feel like the "Store an index to get around the borrow checker" largely moves the problem - now you have A) array-bounds-checking bugs, and B) either "list was re-ordered, you now have the wrong item" or "can't compact the list, it just keeps growing even when old items are no longer used" bugs. Sure, you no longer have to satisfy the borrow checker - but it was a tool to help you catch bugs, and you've cleverly avoided getting that help.
  - davidatbu 3y ago
    > array-bounds-checking bugs. Rust tries very very hard to avoid bounds-checking bugs, because it's central to the safety promise, maybe I'm misunderstanding you? > either "list was re-ordered, you now have the wrong item" ... "can't compact the list, it just keeps growing even when old items are no longer used" bugs. I have no direct experience implementing this pattern, but it's good to know that leptos (and others) tend to use one well-tested library that addresses these concerns[1]. > Sure, you no longer have to satisfy the borrow checker - but it was a tool to help you catch bugs, and you've cleverly avoided getting that help. My impression is that one can perhaps claim "one traded compile-time checks of safety for runtime _panics_ when unsafe things are about to happen", and not that using this pattern exposes one to the same issues that the borrow checker avoids. [1] https://docs.rs/slotmap/latest/slotmap/index.html#why-not-index-a-vec-or-use-slab-stable-vec-etc https://docs.rs/slotmap/latest/slotmap/index.html#why-not-in...
    - 3y ago
deleted 3y ago
[deleted]
pjmlp 3y ago
So he mentions CHERI, but fails to look into SPARC ADI, ARM PAC and MTE, all already in production, with SPARC ADI for at least a decade.
- Brentward 3y ago
  He links to a page about ARM MTE in the section where he talks about memory tagging and CHERI for the first time.
  - pjmlp 3y ago
    Indeed, but then maybe it should have been more explicit. Memory tagging as concept is quite old, so I would even expect that link to point into Burroughs Large Systems, Lisp, or other hardware of similar vintage.
TazeTSchnitzel 3y ago
Vale's “generational references” sound like some kind of holy grail, which makes me worry I'm missing something. Surely someone has tried them before? Why aren't they already in common use? I think they would constrain memory allocation and promote heap fragmentation, which might be fine on a system with ample 64-bit address space, but could be troublesome for WebAssembly for example. They also don't seem like they avoid the concurrency issues that Rust's borrowing model can. Also, it's unfortunate that Vale is one letter away from Vala.
- malkia 3y ago
  ah! Reading about Vale, I was actually thinking about Vala, now I see! (I barely know Vala, just from compiling some GTK/Gnome related code).
- Findecanor 3y ago
  There are also programming languages named "Dala" and "Dale". Dala and Vale are memory-safe. Vala and Dale are not.
  - uzerfcwn 3y ago
    There's also "Val", again banking on safety.
- flohofwoe 3y ago
  The (related) idea of a generation counter combined with an index handle for spatial and temporal runtime memory safety has been quite popular recently in the gamedev space: - (shameless plug): https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html - Seb Aaltonen's recent engine design presentation (search for "Fast & safe object lifetime tracking"): https://enginearchitecture.realtimerendering.com/downloads/reac2023_modern_mobile_rendering_at_hypehype.pdf https://enginearchitecture.realtimerendering.com/downloads/r... Some gamedev engines probably invented a similar concept in parallel over the last two decades. ...having things like this baked into the language is quite a bit nicer of course, and should allow for better performance.
- 3y ago
lll-o-lll 3y ago
Great article, but the OCD is still twitching from that opening line - “once of those concepts”
- verdagon 3y ago
  Fixed, thanks =)
chc4 3y ago
This is not memory safe. Having generational pointers to do epoch checking on dereference is a stochastic mitigation. It is equivalent to PAC or Chromium MiraclePtr but with even less defense against adversarial attackers, because any infoleak of the generation allows for forging of UaF pointers. The "high RAII" concept is also not actually misuse proof. There doesn't look like there's actually anything preventing the user from calling free themselves instead of RemoveShipFromDisplayCache. The types are linear, but the final sink is always free which doesn't encode the full usage semantics.
- camgunz 3y ago
  Mostly I think you're right, though I don't think this is pointer tagging a la PAC or auto-zeroing (etc.) a la MiraclePtr, this just looks like compiler support for unique_ptr. I'm with you on the high RAII: it sounds like destructors with some important missing steps. It also looks like the idea of "SOPs must eventually be freed" runs into some immediate Turing problems, i.e. you can't know an SOP will be freed when you have if statements, or a cycle of functions passing an SOP around that conditionally free an SOP depending on some external state, or program behavior contingent on external messaging, etc. I think another place you'd run into problems with this is... you actually do want references to heap allocated memory. It's pretty laborious to get by with unique_ptr all on its own; you want to lend out shared references that you get back as their scopes close, and so on. It doesn't seem like there's any facility for that here. To people trying to build systems like this without building Rust's system: honestly just try it in C++. Sure there won't be compiler support for it, so you'll have to manually insert stuff, but just see how workable it is. If you were working with this system in a program of any appreciable complexity you'd immediately realize: - You don't reliably know when things haven't been freed - You really want references --- An interesting alternative way to look at what's proposed here is, this just an oblique message passing system.
- tgv 3y ago
  > There doesn't look like there's actually anything preventing the user from calling free themselves True, but wouldn't that still be memory safe? It seems to me that it could lead to a memory leak, but not to double use of memory. But another annotation to the type so that free() can only be called at one point (or perhaps a few points) might solve that.
dvh 3y ago
Is this hypothetical or can I actually use ^ in c?
- Dwedit 3y ago
  You can use it in C++/CLI, basically C# with much worse syntax.
- 4gotunameagain 3y ago
  You can, but it is the XOR operator. It says a bit above: If we were to craft a C-like language
- pajko 3y ago
  ^ actually is a language symbol of Apple's C compilers, used for a different purpose (lambdas): https://en.wikipedia.org/wiki/Blocks_(C_language_extension) https://en.wikipedia.org/wiki/Blocks_(C_language_extension)
  - zokier 3y ago
    Microsofts C++ extension is probably more relevant here: Foo^ foo = ref new Foo(); https://en.m.wikipedia.org/wiki/C%2B%2B/CX#Objects https://en.m.wikipedia.org/wiki/C%2B%2B/CX#Objects
- edflsafoiewq 3y ago
  It's hypothetical. The use of ^ for pointers comes from Pascal.
notacoward 3y ago
It would be nice if this explained how to deal with data structures containing cycles. Want to solve a Traveling Salesman problem? Each city object would logically have pointers to neighbors. Multiple pointers to each city, no clear rule for which ones own which others, cycles everywhere. Yes, you can solve this by putting the owning pointers into an array and using indices elsewhere, or similar tricks, but that still leaves you prone to leaks. It's easy to get memory safety - no use after free, buffer overflow, etc. - if you don't care about leaks. The real trick is to come up with something that's also provably leak-free even in the presence of cycles.
- sirwhinesalot 3y ago
  This should work just fine in Vale, instead what will happen is once you delete a city, and you try to access it from another city through a reference, your program will panic. Generational references are nothing new, they are often used whenever you have an object pool. The novelty is in applying them to the whole program, effectively turning use-after-free into an out-of-bounds panic of sorts.
  - notacoward 3y ago
    I'm not sure that "it's possible for your program to do this thing and if it does the program will panic" really qualifies as memory-safe. Maybe it's better than what you'd get in C, but in some kinds of programs it could still be a DoS vector. In a garbage-collected language or unsafe-free Rust it would not be possible to crash because of a deleted city, and that would be strictly better.
    - sirwhinesalot 3y ago
      The vast majority of rust application code has unwrap()s everywhere, not to mention bounds checks on arrays, both of which trigger panics. You can always check the validity of a generational reference before every use, just as you can check the array length or the Result<T,E>
ericpauley 3y ago
Obligatory link on memory safety without garbage collection: https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98125 https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98...
abnercoimbre 3y ago
It was an absolute pleasure having Verdagon speak in detail [0] about memory safety at Handmade Cities [1] last year. Check out the conversation if you were left wanting more after this essay. [0] https://handmade.network/podcast/ep/afc72ed0-f05f-4bee-a658-9ad02c0453da https://handmade.network/podcast/ep/afc72ed0-f05f-4bee-a658-... [1] https://handmadecities.com https://handmadecities.com
perlgeek 3y ago
I'm a bit confused on the meta level. If it actually works well in practice, why aren't there quite a few memory-safe, single owner-based systems programming languages out there? Is it such a new idea? (The author argues that it's not, C programmers have been doing it without compiler support for ages). Or is only a part of it new? If yes, which part?
codedokode 3y ago
> Rule 4: When we move out of a variable, we can't use it anymore. > C++ doesn't have rule 4, in C++ the compiler lets us accidentally use the variable after we move out of it. Why is it so? Moving is not a legacy operation, why did they allow to use moved-out variable?
- gary_0 3y ago
  C++ move semantics was added to the existing standard library and class syntax in a way that avoided breaking old code. The language added "move constructor" conventions and the like, rather than making more drastic internal changes. So moving from a std::string variable means it's still a valid object, only its internal state is now owned by someone else, and the std::string is required to now be in an "empty" (but still valid) state. Most of the "moving" is actually handled by extra code in std::string rather than the core language having rules for how the underlying bytes are moved around, because the core language wasn't changed that much.
MichaelMoser123 3y ago
i think Rust is actually encouraging programmers to make extra copies of objects, because that's the most simple path to get things done. Did I miss anything?
- dralley 3y ago
  That it's often similar in C/C++, except instead of the borrow checker being in the way it's fear of memory management or concurrency bugs.
  - MichaelMoser123 3y ago
    still, in c++ you would pass an object by reference to a function call (if that object is not expected to be of very small in size). However in Rust you do have a strong incentive to do otherwise.

111 points by modernerd 3y ago

Now he just needs to look into parrot (the old perl6 vm) or pony, which do expand on single ownership and compiler-checked move semantics. Not just memory safe, but also concurrency safe. Concurrent Pascal was also similar.

Hardliner66 3y ago
I think Pony is one of the most interesting languages out there. I love actors, I love capabilities, I love whitelisting of C/C++ usage. Sadly no armv7 support, cross compiling itself is really hard too (never got it to work), the package management support is weird and deviates quite a bit from mainstream (IIRC having multiple versions of the same dependency is a feature ) and it lacks users. I honestly would love to have a mix between rust and pony.
perlgeek 3y ago
Too bad nobody was ever able to build a practical, concurrent programming language on top of parrot. (Nor any well-performing non-concurrent language, for that matter). And quite a few talented compiler writers tried (I'm thinking of Patrick Michaud and Jonathan Worthington at least, probably forget quite a few).

Hardliner66 3y ago

The example somehow reminds me of proof carrying code. If you obtain memory in pcc, you also get a proof that the memory is valid. If you want to use the memory, you need to pass the proof as well. Finally, the proof must be disposed and the only function that can do that for memory is free. This can be done for the reminder example as well.

davidatbu 3y ago

A great read! Might be worth pointing out: leptos, a Rust WASM UI library, uses the "store an index (or ID) into some central data structure" idea extensively. Sycamore, another Rust WASM UI library, has been using arena allocation, but will also be transitioning into the leptos approach in coming versions. (I believe) this is partly because the borrow checker's enforcement of a tree-like data structures / ownership doesn't always work well with the JS event loop.

aatd86 3y ago
Interesting. So basically the index storage is a way to create a reference to an object that is not compiler checked?
- davidatbu 3y ago
  I would say that it's a way to trade compile-time checks of reference validity for runtime-checks of reference validity.
danielheath 3y ago
I feel like the "Store an index to get around the borrow checker" largely moves the problem - now you have A) array-bounds-checking bugs, and B) either "list was re-ordered, you now have the wrong item" or "can't compact the list, it just keeps growing even when old items are no longer used" bugs. Sure, you no longer have to satisfy the borrow checker - but it was a tool to help you catch bugs, and you've cleverly avoided getting that help.
- davidatbu 3y ago
  > array-bounds-checking bugs. Rust tries very very hard to avoid bounds-checking bugs, because it's central to the safety promise, maybe I'm misunderstanding you? > either "list was re-ordered, you now have the wrong item" ... "can't compact the list, it just keeps growing even when old items are no longer used" bugs. I have no direct experience implementing this pattern, but it's good to know that leptos (and others) tend to use one well-tested library that addresses these concerns[1]. > Sure, you no longer have to satisfy the borrow checker - but it was a tool to help you catch bugs, and you've cleverly avoided getting that help. My impression is that one can perhaps claim "one traded compile-time checks of safety for runtime _panics_ when unsafe things are about to happen", and not that using this pattern exposes one to the same issues that the borrow checker avoids. [1] https://docs.rs/slotmap/latest/slotmap/index.html#why-not-index-a-vec-or-use-slab-stable-vec-etc https://docs.rs/slotmap/latest/slotmap/index.html#why-not-in...
  - 3y ago

deleted 3y ago

[deleted]

pjmlp 3y ago

So he mentions CHERI, but fails to look into SPARC ADI, ARM PAC and MTE, all already in production, with SPARC ADI for at least a decade.

Brentward 3y ago
He links to a page about ARM MTE in the section where he talks about memory tagging and CHERI for the first time.
- pjmlp 3y ago
  Indeed, but then maybe it should have been more explicit. Memory tagging as concept is quite old, so I would even expect that link to point into Burroughs Large Systems, Lisp, or other hardware of similar vintage.

TazeTSchnitzel 3y ago

Vale's “generational references” sound like some kind of holy grail, which makes me worry I'm missing something. Surely someone has tried them before? Why aren't they already in common use? I think they would constrain memory allocation and promote heap fragmentation, which might be fine on a system with ample 64-bit address space, but could be troublesome for WebAssembly for example. They also don't seem like they avoid the concurrency issues that Rust's borrowing model can. Also, it's unfortunate that Vale is one letter away from Vala.

malkia 3y ago
ah! Reading about Vale, I was actually thinking about Vala, now I see! (I barely know Vala, just from compiling some GTK/Gnome related code).
Findecanor 3y ago
There are also programming languages named "Dala" and "Dale". Dala and Vale are memory-safe. Vala and Dale are not.
- uzerfcwn 3y ago
  There's also "Val", again banking on safety.
flohofwoe 3y ago
The (related) idea of a generation counter combined with an index handle for spatial and temporal runtime memory safety has been quite popular recently in the gamedev space: - (shameless plug): https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html - Seb Aaltonen's recent engine design presentation (search for "Fast & safe object lifetime tracking"): https://enginearchitecture.realtimerendering.com/downloads/reac2023_modern_mobile_rendering_at_hypehype.pdf https://enginearchitecture.realtimerendering.com/downloads/r... Some gamedev engines probably invented a similar concept in parallel over the last two decades. ...having things like this baked into the language is quite a bit nicer of course, and should allow for better performance.
3y ago

lll-o-lll 3y ago

Great article, but the OCD is still twitching from that opening line - “once of those concepts”

verdagon 3y ago
Fixed, thanks =)

chc4 3y ago

This is not memory safe. Having generational pointers to do epoch checking on dereference is a stochastic mitigation. It is equivalent to PAC or Chromium MiraclePtr but with even less defense against adversarial attackers, because any infoleak of the generation allows for forging of UaF pointers. The "high RAII" concept is also not actually misuse proof. There doesn't look like there's actually anything preventing the user from calling free themselves instead of RemoveShipFromDisplayCache. The types are linear, but the final sink is always free which doesn't encode the full usage semantics.

camgunz 3y ago
Mostly I think you're right, though I don't think this is pointer tagging a la PAC or auto-zeroing (etc.) a la MiraclePtr, this just looks like compiler support for unique_ptr. I'm with you on the high RAII: it sounds like destructors with some important missing steps. It also looks like the idea of "SOPs must eventually be freed" runs into some immediate Turing problems, i.e. you can't know an SOP will be freed when you have if statements, or a cycle of functions passing an SOP around that conditionally free an SOP depending on some external state, or program behavior contingent on external messaging, etc. I think another place you'd run into problems with this is... you actually do want references to heap allocated memory. It's pretty laborious to get by with unique_ptr all on its own; you want to lend out shared references that you get back as their scopes close, and so on. It doesn't seem like there's any facility for that here. To people trying to build systems like this without building Rust's system: honestly just try it in C++. Sure there won't be compiler support for it, so you'll have to manually insert stuff, but just see how workable it is. If you were working with this system in a program of any appreciable complexity you'd immediately realize: - You don't reliably know when things haven't been freed - You really want references --- An interesting alternative way to look at what's proposed here is, this just an oblique message passing system.
tgv 3y ago
> There doesn't look like there's actually anything preventing the user from calling free themselves True, but wouldn't that still be memory safe? It seems to me that it could lead to a memory leak, but not to double use of memory. But another annotation to the type so that free() can only be called at one point (or perhaps a few points) might solve that.

dvh 3y ago

Is this hypothetical or can I actually use ^ in c?

Dwedit 3y ago
You can use it in C++/CLI, basically C# with much worse syntax.
4gotunameagain 3y ago
You can, but it is the XOR operator. It says a bit above: If we were to craft a C-like language
pajko 3y ago
^ actually is a language symbol of Apple's C compilers, used for a different purpose (lambdas): https://en.wikipedia.org/wiki/Blocks_(C_language_extension) https://en.wikipedia.org/wiki/Blocks_(C_language_extension)
- zokier 3y ago
  Microsofts C++ extension is probably more relevant here: Foo^ foo = ref new Foo(); https://en.m.wikipedia.org/wiki/C%2B%2B/CX#Objects https://en.m.wikipedia.org/wiki/C%2B%2B/CX#Objects
edflsafoiewq 3y ago
It's hypothetical. The use of ^ for pointers comes from Pascal.

notacoward 3y ago

It would be nice if this explained how to deal with data structures containing cycles. Want to solve a Traveling Salesman problem? Each city object would logically have pointers to neighbors. Multiple pointers to each city, no clear rule for which ones own which others, cycles everywhere. Yes, you can solve this by putting the owning pointers into an array and using indices elsewhere, or similar tricks, but that still leaves you prone to leaks. It's easy to get memory safety - no use after free, buffer overflow, etc. - if you don't care about leaks. The real trick is to come up with something that's also provably leak-free even in the presence of cycles.

sirwhinesalot 3y ago
This should work just fine in Vale, instead what will happen is once you delete a city, and you try to access it from another city through a reference, your program will panic. Generational references are nothing new, they are often used whenever you have an object pool. The novelty is in applying them to the whole program, effectively turning use-after-free into an out-of-bounds panic of sorts.
- notacoward 3y ago
  I'm not sure that "it's possible for your program to do this thing and if it does the program will panic" really qualifies as memory-safe. Maybe it's better than what you'd get in C, but in some kinds of programs it could still be a DoS vector. In a garbage-collected language or unsafe-free Rust it would not be possible to crash because of a deleted city, and that would be strictly better.
  - sirwhinesalot 3y ago
    The vast majority of rust application code has unwrap()s everywhere, not to mention bounds checks on arrays, both of which trigger panics. You can always check the validity of a generational reference before every use, just as you can check the array length or the Result<T,E>

ericpauley 3y ago

Obligatory link on memory safety without garbage collection: https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98125 https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98...

abnercoimbre 3y ago

It was an absolute pleasure having Verdagon speak in detail [0] about memory safety at Handmade Cities [1] last year. Check out the conversation if you were left wanting more after this essay. [0] https://handmade.network/podcast/ep/afc72ed0-f05f-4bee-a658-9ad02c0453da https://handmade.network/podcast/ep/afc72ed0-f05f-4bee-a658-... [1] https://handmadecities.com https://handmadecities.com

perlgeek 3y ago

I'm a bit confused on the meta level. If it actually works well in practice, why aren't there quite a few memory-safe, single owner-based systems programming languages out there? Is it such a new idea? (The author argues that it's not, C programmers have been doing it without compiler support for ages). Or is only a part of it new? If yes, which part?

codedokode 3y ago

> Rule 4: When we move out of a variable, we can't use it anymore. > C++ doesn't have rule 4, in C++ the compiler lets us accidentally use the variable after we move out of it. Why is it so? Moving is not a legacy operation, why did they allow to use moved-out variable?

gary_0 3y ago
C++ move semantics was added to the existing standard library and class syntax in a way that avoided breaking old code. The language added "move constructor" conventions and the like, rather than making more drastic internal changes. So moving from a std::string variable means it's still a valid object, only its internal state is now owned by someone else, and the std::string is required to now be in an "empty" (but still valid) state. Most of the "moving" is actually handled by extra code in std::string rather than the core language having rules for how the underlying bytes are moved around, because the core language wasn't changed that much.

MichaelMoser123 3y ago

i think Rust is actually encouraging programmers to make extra copies of objects, because that's the most simple path to get things done. Did I miss anything?

dralley 3y ago
That it's often similar in C/C++, except instead of the borrow checker being in the way it's fear of memory management or concurrency bugs.
- MichaelMoser123 3y ago
  still, in c++ you would pass an object by reference to a function call (if that object is not expected to be of very small in size). However in Rust you do have a strong incentive to do otherwise.