131–140 of 143 posts
No mention of RCU?
RCU, despite the name, is indeed a reclamation algorithm, but not a general one. I.e. you would use RCU (or some other deferred reclamation algorithm like hazard pointers) for specific data structures when you do not have generalized garbage collection. A generalized RCU is just a tracing GC.
Earlier quoted context omitted.
Even in their own list of features "Memory Safety" does not pop up, and none of the listed features indicate to me that they would entail memory safety. Academics aren't publishing droves of work on separation logic for a problem that can be solved by 1980s static analyzers.
They say that they can prove the absence of classes of bugs that make up memory safety: * out-of-bounds array indexing, * erroneous pointer manipulation and dereferencing (NULL, uninitialized and dangling pointers), * read access to uninitialized variables, NIST gave them a glowing review: https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8304.pdf It is possible to make sound static analyzers that can prove code to b…
After pondering, my single favorite capability of rust is this: fn modify(val: &mut u8) { // ... } 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's memory model, or an unrelated language insight?
How is a mutable reference as an argument to a function in any way unique? C++ has mutable references as arguments to functions.
This is automatically thread-safe, without any locks. It's guaranteed that there can't be any side effects that could affect this memory, no matter what code you call. You don't need any defensive coding copying the memory just in case. It optimizes well, because it's certain that it won't overlap with any other region.
C++ doesn't have that kind of strong no-alias guarantee. Even memory behind const pointers can be mutated by something else at distance. The closest equivalent is C's restrict pointers, but they're more coarse-grained, and aren't checked by the compiler.
Earlier quoted context omitted.
> The literature does not always put the “tracing” in front of the “garbage collection”. Not always, but often enough that an introductory article that presents an overview of different memory managment techniques should maybe use the longer name to avoid confusion. And I kinda agree with you, using the name "garbage collection" for RC doesn't really make sense, there is no metaphorical garbage truck driving around t…
> Not always, but often enough that an introductory article that presents an overview of different memory managment techniques should maybe use the longer name to avoid confusion. Referring to garbage collection as tracing garbage collection creates more confusion and should be avoided. It confuses folks into thinking that there is some garbage collection that isn’t tracing. There’s no such thing. > What's your opini…
It is standard to consider reference counting as garbage collection.
Bacon, D.F., Cheng, P. and Rajan, V.T. 2004. A unified theory of garbage collection. ACM SIGPLAN Notices. 39, 10 (Oct. 2004), 50–68. DOI: https://doi.org/10.1145/1035292.1028982
Abstract:
Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties. [...] Using this framework, we show that all high-performance collectors (for example, deferred reference counting and generational collection) are in fact hybrids of tracing and reference counting.
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.
Earlier quoted context omitted.
They say that they can prove the absence of classes of bugs that make up memory safety: * out-of-bounds array indexing, * erroneous pointer manipulation and dereferencing (NULL, uninitialized and dangling pointers), * read access to uninitialized variables, NIST gave them a glowing review: https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8304.pdf It is possible to make sound static analyzers that can prove code to b…
I'm published in formal methods and see plenty of papers on static analysis of C. They ALL fail against a well designed type system.
Astree uses the theory of abstract interpretation that most of those in the formal methods community publishing papers do not touch as far as I know. It is therefore a different kind of tool for verifying properties of code than the techniques put forth in most formal methods papers.
NIST evaluated Astree and it got a perfect score on their test suite. It was actually a better than perfect score, as it found flaws in the test suite that NIST had not known existed. I have not heard of runtime errors in the Astree verified C/C++ code running on Boeing airliners or ESA space probes, unlike the prominent Toyota issues where they did not use any such tools and their slogan “always moving forward” became literal. So far, those who can afford it seem to be avoiding runtime issues in C/C++ code, which would be impossible if it did not work as advertised.
I acknowledge that correctness by external observation is not airtight logic. However, substantially similar reasoning applies to the security of RSA, since the RSA hardness assumption is an assumption and not a verifiable proof. A key difference is that with Astree, a claim is made that the software can make proofs internally to justify its claims, but we can scrutinize neither the proofs nor its source code. I choose to believe claims about Astree until they are proven otherwise given that Astree appears to be preventing runtime errors in a great number of mission critical applications and the independent NIST review found no flaws in its ability to statically detect sources of runtime errors.
Not mentioned: do not do any dynamic allocation at all. Never ever. Everything is either a global variable or goes on the stack. Doesn't work when you need to handle unknown input size, but when you need to make sure you don't OOM ever, it's the only way. Stack overflow is still a possibility, unfortunately, because existing languages cannot provide any guarantee here (Zig tried, but didn't got it done afair). The on…
https://www.absint.com/astree/index.htm
None make any mention of stack exhaustion that I can find in a cursory search.
Not mentioned: do not do any dynamic allocation at all. Never ever. Everything is either a global variable or goes on the stack. Doesn't work when you need to handle unknown input size, but when you need to make sure you don't OOM ever, it's the only way. Stack overflow is still a possibility, unfortunately, because existing languages cannot provide any guarantee here (Zig tried, but didn't got it done afair). The on…
What you describe is stack exhaustion. Stack overflow is running past the end of an object on the stack. “Memory safe” languages claim to protect against stack overflows, as does the astree sound static analyzer for C/C++: https://www.absint.com/astree/index.htm None make any mention of stack exhaustion that I can find in a cursory search.
https://en.wikipedia.org/wiki/Stack_overflow
> In software, a stack overflow occurs if the call stack pointer exceeds the stack bound.
Also your searching astree site reveals:
> StackAnalyzer automatically determines the worst-case stack usage of the tasks in your application. It lets you find any stack overflows, or formally prove the absence thereof.
Earlier quoted context omitted.
What you describe is stack exhaustion. Stack overflow is running past the end of an object on the stack. “Memory safe” languages claim to protect against stack overflows, as does the astree sound static analyzer for C/C++: https://www.absint.com/astree/index.htm None make any mention of stack exhaustion that I can find in a cursory search.
Wikipedia doesn't agree. https://en.wikipedia.org/wiki/Stack_overflow > In software, a stack overflow occurs if the call stack pointer exceeds the stack bound. Also your searching astree site reveals: > StackAnalyzer automatically determines the worst-case stack usage of the tasks in your application. It lets you find any stack overflows, or formally prove the absence thereof.
https://en.wikipedia.org/wiki/Stack_buffer_overflow
What you call stack overflow appears to be what I call stack exhaustion. The two different cases are very different things when you look at what happens in memory. In computers, the stack grows down, so exhausting the stack occurs in a downward direction. When you overflow an object on the stack, this typically occurs in an upward direction, and continues until older stack frames. Downward is also possible for that case, but it is rare and when it happens it can also be the other issue at the same time.
Hearing stack overflow used to describe the other kind of issue is what prompted my reply. I had not known that others use these terms differently. In all cases, we are describing something going past a boundary, with the only difference being what, so the ambiguous usage makes sense. The ambiguous usage appears to be acknowledged by Wikipedia:
https://en.wikipedia.org/wiki/Stack_overflow_(disambiguation...
I will continue to use stack exhaustion for this, as it is more accurate.
There is also a third case, which is jumping the stack guard page. I am not sure if you consider this to be a “stack overflow” too. It is a third class of bug. Wikipedia appears to lump it together with stack exhaustion under stack overflow.
I never expected bug taxonomy to be controversial, yet here we are.
Earlier quoted context omitted.
I stand corrected on C++. Can you think of any other languages? Of the ones I listed, I use all of, and am continuously frustrated by this limitation.
Most low-level languages support this, references in C++, pointers in C, ref keyword in C# and Dlang, and so on. It's mostly higher-level languages that do not support such things because it's in the VM semantics that dictate how objects are passed (i.e. in Lua tables are passed by reference, non-table values are passed by copy).