RFC: Shared Thread Safe References

[shayanhabibi]

Issue

Concurrently allocating memory to ref objects while consuming (decrementing) the ref count in other threads in parallel results in undefined behaviour which causes SIGSEGVs. This is especially apparent in higher thread counts where the likelihood of this occurring increases dramatically (anything more than 2 threads on naive tests starts to hit SIGSEGVs pretty regularly).

Example

This issue is apparent on loony and was delved into further with evilcanary.

Source of SIGSEGV

Naturally, it came down to incref, decref and islastdecref not being atomic. Memory thread fences only applied a level of temporal coherency that did not apply to any changes to volatile memory after the elements were removed from the queue. While the allocator uses locks, this doesnt prevent dirty memory being accessed too soon by the allocating thread which can result in a SIGSEGV in the allocator algorithm.

Solution

After fiddling with the system arc file, I found that introducing atomic operations to the 3 key operations listed above completely absolved my tests of any undefined behaviour. These should/can be implemented through:

Shared Ref

A simple solution (but also the most annoying for it having to introduce another annoying keyword) is to create a new shared ref type that might be represented by sref( or something that looks less like shrek) and enforcing atomic operations.

Ref modification

Alternatively, we can simply use when hasThreadSupport expressions to change ref counting to use atomic operations.

Costs

Atomic writes have a significantly larger cost than loads. Because of the extra cost, I would like to minimize the use of Atomic operations wherever possible, therefore I prefer the first solution over the second.

But can't you just make a library that implements something like this?

Yes? But also the default ref "traced pointer" should do what's written on the label imo. Or developers should be provided with more primitives such as hooks to modify how their objects reference headers are interacted with.

[disruptek]

I'd say that making references work with threads is non-negotiable. An unshared keyword (or similar) could allow for better performance by relaxing the use of atomics, but I would rather opt-in to performance and unsafety than opt-out of safety by default. The atomics can obviously be omitted in single-threaded builds.

Consider libraries which use a ref keyword naively and don't anticipate cross-thread use of the shared heap -- or, essentially, every existing use of a ref today. It would be frustrating to tell people that they can now use all of their cores, except that they have to play a guessing game as to whether the stdlib or other 3rd-party libraries might crash their program. Obviously, the cases in which such use will crash your program are extremely trivial.

Multi-threaded programs do often offer performance advantages, while programs that don't run offer very little performance indeed.

[shayanhabibi]

I'm not sure what owned was supposed to do but I think that is a good keyword to indicate a thread now has sole ownership of a ref. But would that mean we turn it into a Owned[T]? It would be easier to just make it a proc which flips a bit switch. This would mean every incref/decref would be predicated by another atomic load to check the switch though

[saem]

Owned memory can be done by region, a region of memory that is owned by a thread will not have any allocation therein which can be referred to by another thread. IIUC this encoding should reduce the number of overall checks required.

Since a refs owned-ness is known statically we can determine dispatch to the appropriate allocator and hooks.

Hope I got all that right.

[shayanhabibi]

So long as extra semantics are required to make it owned and not the other way around. Default should be shared imo.

[saem]

So long as extra semantics are required to make it owned and not the other way around. Default should be shared imo.

could it not instead be as follows:

• everything is allocated as unshared and no fixed ownership
• when shared, we check if the ownership is fixed, if not, we trigger a move into shared space and share the ref
• if owned and then a share is attempted, we get a compile error as we tried to move fixed ownership memory into a shared region

later we can rework the language to make this whole thing more pleasant, for example, being able to note that something should be allocated as shared from the get go.

[disruptek]

It's an error to assume that any ref is not shared. Again, we need to default to safety and escape to performance. What you can do, is to allow the owned keyword to allocate locally.

[alaviss]

The cost of atomics IMO is too large for our case of ref-counting. At least in Python they found out that switching over degrades performance by 23%. I believe there are systems that opted for a tracing GC because it is cheaper than atomics everywhere. So I think to effectively implement this, we need to either:

• Figure out a way to not use atomics.

• Figure out a way to eliminate as many refcount operations as possible.

• Figure out a way to only incur atomic costs when it is required (regardless of --threads status).