Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

verdagon.dev

Post reply on HN
Print view View original

121–130 of 143 posts

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

#121

Post by gpderetta »

obl wrote: post #22
mgaunard wrote: post #11

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

It is not ridiculous at all. Those things have pretty precise definitions and type segregation absolutely does remove a bunch of soundness issues related to type confusion. You can think of it as the rather classic "Vec of struct + numeric IDs" that is used a lot e.g. in Rust to represent complex graph-like structures. This combined with bound checking is absolutely memory safe. It has a bunch of correctness issue th…

> but those are not safety issues.

there are not memory safety issues. But they definitely can lead to security issues with some sort of confused deputy attack.

For example a capability based system that relied on just this form of memory safety would be pointless.

Of course this can be mitigated by adding version counters to objects and object selectors.

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

#122

Post by gpderetta »

eklitzke wrote: post #112

I don't understand why they say that reference counting is "slow". Slow compared to what? Atomic increments/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. This isn't to say reference counting is without problems (there are plenty of them…

Atomic reference counting per se is fairly slow compared to other simple operations [1]. But the biggest issue with reference counting is that it doesn't scale well in multithreaded programs: even pure readers have to write to shared memory locations. Also acquiring a new reference from a shared atomic pointer is complex and need something like hazard pointers or a lock.

[1] an atomic inc on x86 is typically ~30 clock cycles, doesn't really pipeline well and will stall at the very least other load operations.

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

#123

Post by gpderetta »

pizlonator wrote: post #61
azornathogron wrote: post #58

Earlier quoted context omitted.

Using concurrent GC has various advantages but in no way makes it deterministic .

True, not by itself. But concurrent GC is the basis for making deterministic GC, since it gives you the option of scheduling GC work whenever you like rather than pausing the world. Some concurrent GCs are also deterministic while others aren’t. I’ve written both kinds.

you have some very non-standard definition of determinism.

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

#124

Post by gpderetta »

nemetroid wrote: post #19

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.

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

#125

Post by pjmlp »

dwattttt wrote: post #107
pjmlp wrote: post #37

Earlier quoted context omitted.

Even with critical timing, real time GCs exist for decades now, PTC and Aicas are two surviving companies selling software tooling for embedded markets, including their own JVM implementations, with AOT compilers, bare metal deployments and real time GC. Many of their customers are factory processes and military deployments with weapons control, two scenarios where any kind of stall might produce deadly results.

While I agree with the point, the word "surviving" doesn't do that point any favours.

Sadly in modern times many devs aren't willing to pay for their tools...

Yet they surely appreciate the income they earn by using them.

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

#126

Post by mgaunard »

IshKebab wrote: post #105
mgaunard wrote: post #103

Earlier quoted context omitted.

It just shows memory safety is a joke, simply replacing a class of bugs with another.

It isn't a joke. With memory safety bugs the value of an object can unexpectedly be any bit pattern . That breaks the assumptions of basically every language and leads to pretty much anything happening. If you have an array of objects of the same type and you just pick the wrong one, then the data still has to be a valid bit pattern. Yes it might still be a security bug, but it's much less likely because you aren't c…

It takes a lot more for a program to be correct than having valid bit patterns.

To begin with, the whole point of classes is to maintain invariants. Guaranteeing that a location in memory matches the valid bit patterns of its members is far from sufficient.

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

#127

Post by IshKebab »

mgaunard wrote: post #126
IshKebab wrote: post #105

Earlier quoted context omitted.

It isn't a joke. With memory safety bugs the value of an object can unexpectedly be any bit pattern . That breaks the assumptions of basically every language and leads to pretty much anything happening. If you have an array of objects of the same type and you just pick the wrong one, then the data still has to be a valid bit pattern. Yes it might still be a security bug, but it's much less likely because you aren't c…

It takes a lot more for a program to be correct than having valid bit patterns. To begin with, the whole point of classes is to maintain invariants. Guaranteeing that a location in memory matches the valid bit patterns of its members is far from sufficient.

> It takes a lot more for a program to be correct than having valid bit patterns.

Obviously. I never said otherwise. What's your point?

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

#128

Post by bluGill »

foota wrote: post #93
bluGill wrote: post #53

Why is garbage collection called memory safety? Garbage collection in whatever form is only memory safe if it doesn'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). Use after free is important, but in my experience not common and not too hard…

To answer your question, I'd say it's memory safe when it's a part of the runtime. At some point, you're relying on your runtime to be correct, so if it says it does garbage collection then you can rely on it, in the same way you rely on the allocator not to randomly trash your memory etc.,.

You misunderstand. Sure that is a part of memory safe, but why is the much larger problem of running off the end of the buffer into something else not considered a larger part. In my experience the later is a worse problem (the blame for issues goes to someone else who's code is working perfectly correct and so they spend months trying to find a logic error before someone finally looks elsewhere - often the fix is just a random fix by those who are at fault and so the team will spend months more looking before closed as "doesn't happen anymore, no idea why". Memory leaks by contrast are hard to track down, but at least they leave obvious clues and so the blame doesn't go to the wrong person.

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

#129

Post by ryao »

voxl wrote: post #116
ryao wrote: post #111

Earlier quoted context omitted.

There is another option, which is to use a sound static analyzer that can prove the absence of memory safety issues like astree, and fix things that cause it to complain until it stops complaining: https://www.absint.com/astree/index.htm For those who think static analyzers cannot do that, notice the word “sound”. This is a different type of static analyzer than the more common ones that do not catch everything. Sadl…

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 be free from memory safety bugs, but it is difficult and you need to implement checks that either complain or mathematically prove the absence of each class to do it.

These tools have been used for years in the aviation and nuclear industries, but almost nobody outside of those industries knows anything about them. If others had broader awareness of the existence of these tools, we could get open source equivalents and memory safety issues would be a thing of the past in C/C++ code.

Finally, your 1980s remark reveals enormous ignorance of what the field of formal methods has produced. Astree was not available in the 1980s. It took over 40 years of work to make and only became available about 20 years ago. C++ support took much longer for it to add, with it only adding it around 6 years ago if my recollection of the public documentation is correct. Some other things in this space are the Polyspace Code Prover and Frama-C.

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

#130

Post by pizlonator »

gpderetta wrote: post #123
pizlonator wrote: post #61

Earlier quoted context omitted.

True, not by itself. But concurrent GC is the basis for making deterministic GC, since it gives you the option of scheduling GC work whenever you like rather than pausing the world. Some concurrent GCs are also deterministic while others aren’t. I’ve written both kinds.

you have some very non-standard definition of determinism.

How so?
Post reply on HN