[foreign-memaccess] on confinement

Tue Jun 4 11:34:12 UTC 2019

Hi,
as promised, here's a more detailed analysis on the state of confinement 
in the foreign-memaccess branch.

The working theory, explained in [1] is that:

* all scopes have an owner thread

* all critical scope operation (close/fork/allocate) are confined to the 
owner

* access to regions created by that scope is un-confined

This proposal was well received - but I now realized that it was flawed, 
at least in part, and I think that this tension is now influencing some 
of the discussions happening in [2]. So let's try to make some order.

Yes, this approach gives the scope owner some guarantees, as the scope 
can never be closed behind the owner's back by some other thread. So far 
so good. But a big reason for doing this, beside cleanliness of user 
model is also another one: to avoid very costly synchronization whenever 
memory is accessed.

I now realize that this goal is not met by the above proposal: that is, 
confining scope critical operations is not enough to completely free us 
from synchronization. Why? Well, while only the owner thread can close a 
scope, if multiple threads have concurrent access to the same region 
owned by the same scope - these threads would have to synchronize when 
accessing memory, in order to make sure that memory is really alive at 
the point of access; a failure to do so could result in accessing 
already freed memory (= VM crash).

In other words, I believe the current implementation is still broken 
when it comes to multi-threaded access to the same region (perhaps more 
subtly so).

The only way to add multi threaded access w/o incurring in heavy 
on-access synchronization cost is to make sure that, at any given point 
in time, only one thread has access to a segment's memory. And, if this 
thread is the only one that can perform 'close' operations, then we're 
in the clear. There's really nothing bad that can happen in such a case.

So, of course if the only thing we wanted to support was confined 
access, we could simply enforce confinement all the way down and be done 
with it. But, in doing so, we would not be able to support all use cases 
where some co-operation between multiple threads is required.

How do we add back some support for sharing a scope/segment across 
multiple threads? This is where things get nasty:

1) segments starts off in a neutral state (no access) and to gain access 
clients must perform an explicit 'acquire' operation (and then 'release' 
to go back to the neutral state). This is, essentially, John's proposal 
in [3].

2) segments starts off in a confined state (with respect to thread T). 
But thread T is also allowed to transfer ownership to a different thread S.

I think that, while being more general, (1) has a lot more surface area 
in the API/programming model. Now user have to become aware of this 
state machine, where segments/scopes can go from neutral (John's call it 
'queued') to owned, back to neutral. Note also that we already using 
try-with-resources to allow for resource collection after use. 
Implementing (1) would mean to add yet another orthogonal dimension - 
that is, a segment/scope will support 'close' (to free memory), 
'acquire' (to set ownership) and 'release' (to unset ownership). Also, 
we have to worry about things like a thread calling 'acquire' 5 times, 
but release only 4 times. In other words, I see that if we go down this 
path, some kind of 'ownership counting' is probably unavoidable.

On the other hand, (2) is much simpler. A scope/segment only has a 
single owner at any given point in time, but the twist is, that owner 
can also transfer his powers to another thread (which will then become 
the new owner). The obvious problem with this approach is that the 
segment owner has to 'know' the thread is transferring ownership to - 
which, I guess, could be too strict of an assumption in certain cases 
(think about a pool of worker thread, where a master thread - the owner 
of the original scope - might not necessarily know who's going to pick 
up the pieces ahead of time).

And, worse, both (1) and (2) suffer from issues when it comes to 
creating 'restricted views' of existing segments. Let's consider this 
use case:

* thread A created a segment S

* thread A slices S into two sub-slices S1 and S2

* ownership of S1 is assigned to thread B, while ownership of S2 is 
assigned to thread C (either using approach (1) or (2))

* when can thread A access S again?

The issue here is that, thanks to slicing, the root region S ends up 
with _two_ owners at the same time (this can scale to the case of _n_ 
owners, of course). So things are quite more convoluted than (1) and (2) 
can lead to imagine.

Here it would seem that (1) has an edge. After all, A can release 
ownership, then slice S up into segments. Threads B and C can acquire S1 
and S2 respectively. But this means that the acquire operation must have 
a side-effect on the original region S too - that is, it has to 
transition to an 'owned' state, so that A cannot acquire it again, at 
least not until both B and C have released S1 and S2, respectively. Note 
also that there's a time where thread A doesn't have ownership, but it 
is still able to do operations on S (such as slicing it up into S1 and 
S2) - which seems at odds with the 'only the owner can perform 
segment/scope operation' rule. So, things are not as clean as they first 
appear.

What about (2)? Surely a single-ownership mechanism cannot cope with a 
de-facto multi-ownership scenario? Well, I think it can, although it's 
not immediate to see. Let's see what the ownership transitions would be 
like under (2):

* A starts off owning segment S

* A creates S1 and S2, which are both owned by A

* A transfers ownership of S1 to B - as a side-effect, this operation 
effectively makes S a mixed ownership segment, so A has no longer access 
to it (but note, A can still access S2!)

* A also transfer ownership of S2 to C. Now A doesn't have access to S 
(see above) but also doesn't have access to S1 and S2 either.

* B terminates and transfer ownership of S1 back to A.

* C terminates and transfer ownership of S2 back to A.

* Now A can access both S1 and S2 - but if we're smart enough, we can 
also detect that it has again access to the full S, which is again only 
owned fully by A

So, it seems that, even with the complexity of (1), we still don't have 
a clear cut way to think about the problem outlined above. And I'd 
really really like to avoid exposing such complex state transitions into 
the final API. I think the cross product of alive/dead state with 
neutral/owned state leads to place where it's really hard to think about 
who can do what at any given point in time (in addition to make the 
implementation more convoluted and direct which might result in more 
places for bugs to hide, as well as a potential for performance 
degradation).

On the other hand, it seems like something like (2) would not only lead 
to something more desirable API/programming model-wise, but also to a 
cleaner path to supporting a multi-ownership scenario such as the one 
described above. Whether the fact that (2) requires explicit ownership 
transfers is too strict, is something that we don't have enough data 
points, at this stage, to work with.

Of course I would have preferred to side-step all this and leave all 
synchronization cost to the user - making only minimal assumptions; but, 
as we have shown, this approach (which was my opening position!) has a 
flaw in the sense that it leaves concurrent access exposed to the risk 
of accessing a segment that's already been closed (which can result in a 
VM crash). While this is an acceptable answer for an unsafe API, we 
wouldn't want something like this to happen in a safe API.

Maurizio

[1] - 
https://mail.openjdk.java.net/pipermail/panama-dev/2019-May/005494.html
[2] - 
https://mail.openjdk.java.net/pipermail/panama-dev/2019-May/005644.html
[3] - 
https://mail.openjdk.java.net/pipermail/panama-dev/2019-June/005651.html