[foreign-memaccess] on confinement

Tue Jun 4 15:11:25 UTC 2019

Thanks for this clear problem statement.

I think that a multiple-segregated-owner model is a good way to support 
divide and conquer algorithms. Also, going with approach (2) seems to 
allow users to implement (1) as well; instead of cutting up a master 
segment S into multiple subsegments S1, S2, ... we instead create a view 
of the entire segment S', which is then transferred to another thread 
(acquire()). This thread can then later on transfer it back again 
(release()). The thread owning S can keep it private, and not access it 
itself (immutable state). This effectively implements (1) I think.

For (2) I think we need one more rule: Any 2 arbitrary subsegments Sx 
and Sy of a common master segment S can not have an overlapping view of 
the underlying memory region, since this would effectively break 
confinement again.

It also brings up the question of how the access of a thread A to a 
master segment S is controlled when we transfer control of a subsegment 
to another thread B. How do we detect, implementation wise, if A has 
access to S or not?

One idea that comes to mind is to track every created subsegment, and 
every time A accesses S we check that the set of subsegments is empty 
for S. Similarly, when creating view segments we verify them against the 
set of existing subsegments to make sure that there is no overlap.

Jorn

Maurizio Cimadamore schreef op 2019-06-04 13:34:
> 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