Thread-safety in the C rts gc

[shlevy]

In implementing and discussing the implementation of #802, it came to light that the C rts gc is not thread-safe for 4 reasons:

1. copy changes the type of the VAL to FWD and modifies the union to set the fwd pointer
2. cheney changes the pointer in newly-copied STROFFSETs and CONs, and pointer updates are not guaranteed atomic
3. The gc function updates the values on the stack/in the inbox non-atomically
4. There is nothing stopping the gc from freeing the old heap while some thread still has an STROFFSET or CON that points to it

1 can be solved by moving the FWD pointer out of the union and synchronizing access to the VAL type for the few functions that access it

2 and 3 can be solved by properly synchronizing the pointers and stack/inbox VALs properly, respectively. In at least the pointer case C11 atomics could be used.

4 is a bit harder. Two possibilities

a) have a per-heap "stack/inbox" rwlock, take readlocks on the current lock when reading the stack, and require a writelock on the old heap's lock before freeing it
b) have an rwlock per slot in the stack/inbox, take a readlock when accessing a slot, and require a writelock before copying the stack/inbox VAL

Either case will require ensuring taking readlocks properly in key points in the rts.

For all of these solutions, we should be able to optimize much of the overhead away at runtime if the VM is known to be single-threaded.

Thoughts?

cc @IreneKnapp

[shlevy]

Note that solution b to problem 4 also solves 3

[shlevy]

Or perhaps it makes more sense to have a per-thread stack?

[edwinb]

Each thread has its own heap (its own VM pointer, that is) and there is, in general, no shared memory. The only situation where two threads have access to the same heap is when passing a message from one to the other, which copies the object completely. That is all locked.

It's pretty inefficient compared to the way it should be, though.

Edwin.

On 29 Jan 2014, at 15:49, Shea Levy [email protected] wrote:

In implementing and discussing the implementation of #802, it came to light that the C rts gc is not thread-safe for 4 reasons:

• copy changes the type of the VAL to FWD and modifies the union to set the fwd pointer
• cheney changes the pointer in newly-copied STROFFSETs and CONs, and pointer updates are not guaranteed atomic
• The gc function updates the values on the stack/in the inbox non-atomically
• There is nothing stopping the gc from freeing the old heap while some thread still has an STROFFSET or CON that points to it
1 can be solved by moving the FWD pointer out of the union and synchronizing access to the VAL type for the few functions that access it

2 and 3 can be solved by properly synchronizing the pointers and stack/inbox VALs properly, respectively. In at least the pointer case C11 atomics could be used.

4 is a bit harder. Two possibilities

a) have a per-heap "stack/inbox" rwlock, take readlocks on the current lock when reading the stack, and require a writelock on the old heap's lock before freeing it
b) have an rwlock per slot in the stack/inbox, take a readlock when accessing a slot, and require a writelock before copying the stack/inbox VAL

Either case will require ensuring taking readlocks properly in key points in the rts.

For all of these solutions, we should be able to optimize much of the overhead away at runtime if the VM is known to be single-threaded.

Thoughts?

cc @IreneKnapp

—
Reply to this email directly or view it on GitHub.

[shlevy]

What is the max_threads field in the VM struct for?

[edwinb]

It's a relic of an aborted attempt to implement parallelism. Probably better that it's removed, actually.

Edwin.

On 29 Jan 2014, at 16:09, Shea Levy [email protected] wrote:

What is the max_threads field in the VM struct for?

—
Reply to this email directly or view it on GitHub.

[shlevy]

Ah OK, this issue is invalid then.