Borrow Checking, RC, GC, and Eleven Other Memory Safety Approaches

More people need to read up on C#&#x27;s ref&#x27;s:<p><a href="https:&#x2F;&#x2F;em-tg.github.io&#x2F;csborrow&#x2F;" rel="nofollow">https:&#x2F;&#x2F;em-tg.github.io&#x2F;csborrow&#x2F;</a><p>These kinda-sorta fall under borrow checking or regions, just without any annotations. Then again, Ada&#x2F;Spark&#x27;s strategy also technically falls under Tofte-Talpin regions:<p><a href="https:&#x2F;&#x2F;www.cs.cornell.edu&#x2F;people&#x2F;fluet&#x2F;research&#x2F;substruct-regions&#x2F;ESOP06&#x2F;esop06.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.cornell.edu&#x2F;people&#x2F;fluet&#x2F;research&#x2F;substruct-r...</a>

&gt; <i>Curséd</i><p>With an acute accent, that should be roughly &#x2F;ˌkɜːrˈseɪd&#x2F; “curse-ay-d”. (Think “café” or “sashayed”.)<p>The stylised pronunciation being evoked is roughly &#x2F;ˈkɜːrˌsɛd&#x2F;, “curse-ed”, and would be written with a grave accent: “cursèd”.

The list gets very woolly by the end. CHERI exists (though not at volume), Cornucopia Reloaded is a research paper, &quot;plus some techniques to prevent use-after-free on the stack&quot; is entirely hand waving.<p>It is really good as food for thought though.

Meta comment, but I really like the formatting of the blog post!<p>It reminds me of the early days of the web, when text was king and content was king. I particularly like the sidenotes in the margins approach.<p>(Hope the author sees this comment :) Hats off)

I&#x27;m kinda torn. It seems there are only three approaches.<p>1. laissez-faire &#x2F; manual memory management (c, c++, etc)<p>In this approach, the programmer decides everything.<p>2. dictatorship &#x2F; garbage collection (java, go, etc)<p>In this approach, the runtime decides everything.<p>3. deterministic &#x2F; lifetime memory management (rust, c with arenas, etc)<p>In this approach, the problem determines everything.

The fact that re-using a slot for a different object of the same type is considered a memory safety technique is ridiculous.

That is very informational. Thank you.<p>I am interested in Vale and it feels very promising, though because my interested in bootstrapping I don&#x27;t like that it is written in Scala. I know, that is shallow, but that&#x27;s a thing that limits my enthusiasm.<p>If you are like me and don&#x27;t like jumping around between notes and text and you prefer to read the notes anyway, here is a little snippet you can run in Web Inspector&#x27;s Console:<p><pre><code> document.querySelectorAll(&quot;.slice-contents a[data-noteid]&quot;).forEach(e =&gt; {document.querySelectorAll(&#x27;.slice-notes [data-noteid=&quot;&#x27; + e.attributes[&quot;data-noteid&quot;].nodeValue + &#x27;&quot;] p&#x27;).forEach(p =&gt; {p.style.fontSize = &#x27;smaller&#x27;; e.parentNode.insertBefore(p, e)}); e.remove() }) </code></pre> It will replace note links with notes themselves making them smaller, because they will not always fit smoothly.

Previous discussion:<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=40146615">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=40146615</a><p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=41974185">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=41974185</a>

From <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=33560227#33563857">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=33560227#33563857</a> :<p>- Type safety &gt; Memory management and type safety: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Type_safety#Memory_management_and_type_safety" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Type_safety#Memory_management_...</a><p>- Memory safety &gt; Classification of memory safety errors: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Memory_safety#Classification_of_memory_safety_errors" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Memory_safety#Classification_o...</a><p>- Template:Memory management <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Template:Memory_management" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Template:Memory_management</a><p>- Category:Memory_management <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Category:Memory_management" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Category:Memory_management</a>

Not mentioned: do not do any dynamic allocation at all. Never ever. Everything is either a global variable or goes on the stack. Doesn&#x27;t work when you need to handle unknown input size, but when you need to make sure you don&#x27;t OOM ever, it&#x27;s the only way. Stack overflow is still a possibility, unfortunately, because existing languages cannot provide any guarantee here (Zig tried, but didn&#x27;t got it done afair).<p>The only real problem with this approach is code reuse, because library writers will insist on opaque structs and malloc rather than letting the caller allocate.

MMM++ is a variation of standard malloc&#x2F;free. You can still UAF, but only to another object of the same type, which may or may not prevent an exploit.<p>Something that&#x27;s missing is full-on formal verification where you write unrestricted C code and then mathematically prove it doesn&#x27;t have any bugs. Nobody does this because proving a C program is correct is harder than mining a bitcoin block by hand, but it&#x27;s useful to anchor one end of the safety&#x2F;freedom spectrum. Many other approaches (such as borrow checking) can also be viewed as variants of this where you restrict the allowed program constructs to ones that are easier to prove things about.

It&#x27;s surprising to see an article with such a large encompassing of different techniques, hybrid techniques and design interactions with the type system, but is more surprising that a whole dimension of memory (un)management was left out: memory fragmentation

I don&#x27;t understand why they say that reference counting is &quot;slow&quot;. Slow compared to what? Atomic increments&#x2F;decrements to integers are one of the fastest operations you can do on modern x86 and ARM hardware, and except in pathological cases will pretty much always be faster than pointer chasing done in a traditional mark and sweep VMs.<p>This isn&#x27;t to say reference counting is without problems (there are plenty of them, inability to collect cyclical references being the most well known), but I don&#x27;t normally think of it as a slow technique, particularly on modern CPUs.

I am not experienced with rust and borrow checkers, but my impression is that borrow checkers also statically ensures thread&#x2F;async safety while most other memory safety systems don&#x27;t. Is this accurate?

I don&#x27;t see any mention of epoch-based garbage collection (see crossbeam <a href="https:&#x2F;&#x2F;docs.rs&#x2F;crossbeam&#x2F;latest&#x2F;crossbeam&#x2F;epoch&#x2F;index.html" rel="nofollow">https:&#x2F;&#x2F;docs.rs&#x2F;crossbeam&#x2F;latest&#x2F;crossbeam&#x2F;epoch&#x2F;index.html</a>). Generational References sounds like a related concept but it&#x27;s not the same. I&#x27;m also surprised nobody&#x27;s mentioned that one lance corporal goat yet.

The way you make garbage collection deterministic is not by doing regions but by making it concurrent. That’s increasingly common, though fully concurrent GCs are not as common as “sorta concurrent” ones because there is a throughput hit to going fully concurrent (albeit probably a smaller one than if you partitioned your heap as the article suggests).<p>Also, no point in calling it “tracing garbage collection”. Its just “garbage collection”. If you’re garbage collecting, you’re tracing.

After pondering, my single favorite capability of rust is this:<p><pre><code> fn modify(val: &amp;mut u8) { &#x2F;&#x2F; ... } </code></pre> No other language appears to have this seemingly trivial capability; their canonical alternatives are all, IMO, clumsier. In light of the article, is this due to Rust&#x27;s memory model, or an unrelated language insight?

I’d love to see a language that kept everything as familiar as possible and implement memory safety as “the hard bit”, instead of the Rust approach of cooking in multiple different new sub languages and concepts.

Not a fan of the framing of the article. Firstly, there are millions of Mayans alive today,<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Maya_peoples" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Maya_peoples</a><p>and secondly, the reason why the pre-Colombian cultural texts and script are not in use today, even by the people who speak the 28 Mayan languages currently in use, is because of genocide by Columbus and those that followed. The Catholic church destroyed every piece of Mayan script they could get their hands on.<p>The article reads like the author is not aware of these basic facts of American geography and history.

&gt; Interaction nets are a very fast way to manage purely immutable data without garbage collection or reference counting.[...] HVM starts with affine types (like move-only programming), but then adds an extremely efficient lazy .clone() primitive, so it can strategically clone objects instead of referencing them.<p>This is wrong, Interaction nets (and combinators) can model any kind of computational systems, including ones that use mutation. In fact, ICs are not really about types at all, although they do come from a generalization of Girard&#x27;s proofs nets, which came from work in linear logic.<p>The interesting thing about ICs is that they are beta-optimal (any encoding of a computation will be done in the minimum number of steps required -- there is no <i>useless</i> work being done), and maximum-parallel with only local synchonization (all reduction steps are local, and all work that <i>can</i> be parallelized <i>will</i> be parallelized).<p>Additionally ICs have the property that any encoding of a different computational system in ICs will preserve the asymptotic behavior of all programs written for the encoded computational system. In fact, ICs are the only computational system with this property.<p>Interaction nets absolutely require garbage collection in the general sense. However, interaction combinators are linear and all garbage collection is explicit (but still exists). HVMs innovation is that by restricting the class of programs encoded in the ICs you can get very cheap lambda duplication and eschew the need for complex garbage collection while also reducing the overhead of implementing ICs on regular CPUs (no croissants or brackets, see Asperti[1] for what that means).<p>Having a linear language with the above restriction allows for a very efficient implementation with a very simple GC, while maximizing the benefits of ICs. In principle <i>any</i> language can be implemented on top of ICs, but to get most benefits you want a language with these properties. It&#x27;s not that HVM starts with affine types and an efficient lazy clone operation, it&#x27;s that a linear language allows extremely efficient lazy cloning (including lambda cloning) to be implemented on top of ICs, and the result of that is HVM.<p>&gt; The HVM runtime implements this for Haskell.<p>This is very wrong. HVM has nothing to do with Haskell. HVM3 is written in C[2], HVM2 has three implementations, one in C[3], one in Rust[4], and a CUDA[5] one. HVM1 was just a prototype and was written in Rust[6].<p>HOC[7], the company behing HVM provides two languages that compile to HVM, Bend[8], and Kind[9]. Bend is a usual functional language, while Kind is a theorem prover based on self types.<p>Haskell is not involved in any of these things except that the HVM compiler (not runtime) is written in Haskell, but that is irrelevant, before Haskell it used to be written in TypeScript and then in Agda (Twitter discussion, sorry, no reference). It&#x27;s an implementation detail, it&#x27;s not something the user sees.<p>Please note that HVM adds some stuff on top of ICs that makes it not strictly beta-optimal, but nevertheless the stuff added is useful in practice and the practical downgrade from theoretical behaviour is minimal.<p>[1] Andrea Asperti, The Optimal Implementation of Functional Programming Languages, ISBN-13: 978-0060815424<p>[2] <a href="https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM3&#x2F;blob&#x2F;main&#x2F;src&#x2F;HVML&#x2F;Runtime.c">https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM3&#x2F;blob&#x2F;main&#x2F;src&#x2F;HVML&#x2F;Run...</a><p>[3] <a href="https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM&#x2F;blob&#x2F;main&#x2F;src&#x2F;hvm.c">https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM&#x2F;blob&#x2F;main&#x2F;src&#x2F;hvm.c</a><p>[4] <a href="https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM&#x2F;blob&#x2F;main&#x2F;src&#x2F;hvm.rs">https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM&#x2F;blob&#x2F;main&#x2F;src&#x2F;hvm.rs</a><p>[5] <a href="https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM&#x2F;blob&#x2F;main&#x2F;src&#x2F;hvm.cu">https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM&#x2F;blob&#x2F;main&#x2F;src&#x2F;hvm.cu</a><p>[6] <a href="https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM1">https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;HVM1</a><p>[7] <a href="https:&#x2F;&#x2F;higherorderco.com" rel="nofollow">https:&#x2F;&#x2F;higherorderco.com</a><p>[8] <a href="https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;bend">https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;bend</a><p>[9] <a href="https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;kind">https:&#x2F;&#x2F;github.com&#x2F;HigherOrderCO&#x2F;kind</a>

No mention of RCU?

I like many of the ideas of Rust, but I still think it is an unsuitable language for most projects.<p>The problem is that it is very easy to write non-GC&#x27;d code in a GC&#x27;d language, but the other way around it is much much harder.<p>Therefore, I think the fundamental choice of Rust to not support a GC is wrong.

Why is garbage collection called memory safety? Garbage collection in whatever form is only memory safe if it doesn&#x27;t free memory that will still be used. (which means if you actually get all your free calls correct C is memory safe - most long lived C code bases have been beat on enough that they get this right for even the obscure paths).<p>Use after free is important, but in my experience not common and not too hard to track down when it happens (maybe I&#x27;m lucky? - we generally used a referenced counted GC for the cases where ownership is hard to track down in C++)<p>I&#x27;m more worried about other issues of memory safety that are not addressed: write into someone else&#x27;s buffer - which is generally caused by write off the end of your buffer.