HigherOrderCO / HigherOrderCO/HVM4

Bug: recursive dups cause race conditions

Open
#21 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
121
Forks
28
PR merge metrics
No merged PRs in 30d

Description

This issue is related to the multi threaded implementation of HVM4 runtime.

The minimal example to reproduce the issue is the following program:
```
@c2 = λs. !S0&C=s; λx0.S0₀(S0₁(x0))
@k2 = λs. !S0&K=s; λx0.S0₀(S0₁(x0))
@main = @c2(@k2)
```

The manual full reduction of the term can be found here: https://gist.github.com/Lorenzobattistela/89c6d6ff07f01402a92f2f93540732e7

The bug is caused by the following term structure that is found middle reduction:
```
!A&K = G₁ ;
!B&K = x0 ;
!G&C = λy0.&C{A₀, B₀}(&C{A₁, B₁}(y0)) ;
λx0.G₀
```

Note how the `G` dup refers to the `A` dup, which itself refers to `G`. So we have a recursive dup structure, where one dup needs the other to be resolved.

In the single-threaded environment, this is not a problem as shown in the manual reduction, because the dups resolve correctly with the lazy evaluation. However, in a multi threaded environment, two different threads pick up each of this DUP's (example, thread A picks up the G dup, thread B picks up the A dup that was enqueued as a task and stolen by thread B).

Initial state of the heap:
```
heap[G_loc] = term_loc
heap[A_loc] = DP1 to G_loc
...
```

So, thread `A` will do `heap_take` in the dup `G` location and set it to 0.

```
heap[G_loc] = 0 // acquired by thread A
heap[A_loc] = DP1 to G_loc
...
```

And then, thread `B` steals a task and finds the `A` dup, so it does `heap_take` on it and sets it to 0.
```
heap[G_loc] = 0 // acquired by thread A
heap[A_loc] = 0 // acquired by thread B
...
```

However, now, thread A reaches a point where it needs the `A` dup to continue `G`'s reduction. So it tries to `heap_take` there. It finds a `0`, and spin waits there.

Finally, thread `B` reaches a point where it needs the `G` value to continue `A`'s reduction. Tries to `heap_take` there, and also finds `0`, spin waits there.

The general problem can be stated as:

```
-> Thread A starts reducing a term. At some point in that term, it finds a dup, DUP_A. It enqueues other work
-> Thread B steals work from A's queue and start reducing. At some point, it finds DUP_B and starts reducing it
-> While reducing DUP_A, thread A finds a DP0 or DP1 of DUP_B. It tries to heap_take on it and receives 0 because thread B is working on it, so spin wait until someone set the value.
-> Now thread B is reducing, but it now finds a DP0 or DP1 of DUP_A, tries heap_take and receives 0, because thread A is working on it, so spin wait.
```

The problem was confirmed by implementing a global deadlock on DUP's, which solved the issue (but is slow and not a complete / correct solution)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.