<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Feb 14, 2013 at 10:37 PM, Simon Marlow <span dir="ltr"><<a href="mailto:marlowsd@gmail.com" target="_blank">marlowsd@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class="im">On 14/02/13 20:54, Alexander Kjeldaas wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
I ended up staring at the PrimOps.cmm file today, and porting tryPutMVar<br>
to C so it can be used from the RTS.<br>
<br>
During my staring, it occurred to me that it should be possible to<br>
implement a wait-on-multiple MVars with mostly no overhead. I am<br>
guessing that this would be desirable, but I am not sure.<br>
<br>
My rough idea is like this:<br>
<br>
-- wait for all MVars, return the value of one of them, and the<br>
corresponding index<br>
takeOneMVar :: [MVar a] -> IO (a, Int)<br>
<br>
This is implemented by this change:<br>
</blockquote></div>
[snip]<br>
<br>
I've occasionally wondered whether we could do this. So I think you'll have some difficulty implementing the code that blocks, because you have to atomically add your queue element to multiple MVars. You could lock all the MVars, but you'll need to sort them to avoid lock-order problems, or do an STM-like two-phase locking thing. It could get pretty hairy.<br>
<br></blockquote><div><br></div><div style>That's true. First I didn't think of this. Then I thought I'd have to sort the MVars, but now after having slept on it, I have this modified design. I think this is much simpler.</div>
<div style><br></div><div style>Instead of the group_head and group_link, we replace the 'tso' link with a MVarGroup link in the multi-case.</div><div style><br></div><div style><div><div>typedef struct StgMVarTSOQueue_ {</div>
<div> StgHeader header;</div><div> struct StgMVarTSOQueue_ *link;</div><div><b> /* struct StgTSO_ *tso; */</b></div><div><b> StgClosure *tso_or_group;</b></div><div>} StgMVarTSOQueue;</div>
<div><br></div></div><div style>Then actually the MVarGroup doesn't know about the number of MVars, and MVars can be added one by one, but it has a simple state-machine.</div><div style><br></div><div style>What this design really does is decouple MVar registration from blocking.</div>
<div style><br></div><div style>The invariant that is relaxed in this scheme is this: An MVarGroup can be in an MVar queue <b>without the TSO blocking</b>. In this case, the "wakeup" and the MVar result is deferred and stored until the TSO actually does block on the MVarGroup.</div>
<div style><br></div><div style><div><div>/* An MVarGroup represents a group of MVars that a TSO waits on. An</div><div> MVarGroup must be locked to be investigated by the MVar code paths.</div><div><br></div><div> Locking:</div>
<div> Since an MVar also must be locked, the lock order is this: First</div><div> MVar, then MVarGroup.</div><div> Note that we never hold two MVars at the same time.</div><div><br></div><div> MVars can only be added to an MVarGroup, not removed from the</div>
<div> group. The MVarGroup does not know about the MVars, and the MVars</div><div> do not know about each others, so in theory this could possibly</div><div> work. The MVarGroup acts as a synchronization point that decides</div>
<div> which MVar "won" the 'put', and as a storage area for the result if</div><div> the TSO hasn't retrieved the result yet.</div><div><br></div><div> The MVarGroup has two boolean states that starts off as false, and</div>
<div> can only transition to true: 1) Whether the MVarGroup is taken, and</div><div> 2) whether the TSO is blocking.</div><div><br></div><div> The MVarGroup goes through the following states.</div><div><br></div><div>
NOT_TAKEN_NOT_BLOCKED (false, false):</div><div> None of the associated MVars have been 'put'. The TSO is *not</div><div> sleeping/blocking on the MVarGroup*. This is the state of the</div><div>
group in the normal case while MVars are being added to the</div><div> group. Next: TAKEN_NOT_BLOCKED or NOT_TAKEN_BLOCKED</div><div><br></div><div> TAKEN_NOT_BLOCKED (true, false):</div><div> One of the associated MVars have been 'put'. The value that is</div>
<div> 'put' is stored in the "deferred_result". This is the state</div><div> of the group when an MVar is 'put' while the TSO is adding</div><div> MVars to the group. When the TSO tries to block on the group,</div>
<div> this value will be immediately returned. Note that this is</div><div> the only state where "deferred_result" is used. Next: INVALID</div><div><br></div><div> NOT_TAKEN_BLOCKED (false, true):</div>
<div> The TSO is blocked on the MVarGroup. Getting to this state</div><div> means that the TSO has built the group of MVars without any</div><div> MVar having been 'put' while the TSO was doing this. Next:</div>
<div> INVALID</div><div><br></div><div> INVALID (true, true): One of the associated MVars have been</div><div> 'put', and the TSO has blocked. This really means that</div><div> everything is over, and the TSO is unblocked with a result.</div>
<div> The individual MVars that are not the first to 'put' a result</div><div> will see this in their TSO wait queues, and just ignore them.</div><div><br></div><div>*/</div><div><br></div><div>typedef struct StgMVarGroup_ {</div>
<div> StgHeader header;</div><div> // The TSO associated with the MVar group. The TSO might or might</div><div> // not currently be blocked, but eventually it will be. Immutable.</div><div> struct StgTSO_ *tso;</div>
<div> StgWord lock; // Protects everything below</div><div> /* The state of the MVarGroup */</div><div> StgWord state GUARDED_BY(mutex);</div><div> // When the TSO is "woken up" by a 'put' on an MVar</div>
<div> StgClosure *deferred_result GUARDED_BY(mutex);</div><div>}</div></div><div><br></div></div></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Also, what does the primop look like? Lists aren't a primitive type, and you can't put MVar# into an Array# (kind mismatch).<br>
<br></blockquote><div><br></div><div style>I didn't know that, but reading this is what forced the above design :-)</div><div style><br></div><div style>A very flexible API would be the following:</div><div style><br>
</div><div style>-- Create MVarGroup</div><div style>newMVarGroup :: IO (MVarGroup a)</div><div style><br></div><div style>-- Add an MVar to a MVarGroup. </div><div style>-- This will fail if the MVarGroup is not associated with the current process (if the MVarGroup's TSO is not the current TSO)!</div>
<div style>registerMVar :: MVarGroup a -> MVar a -> IO (MVarGroup a)</div><div style><br></div><div style>-- Block on the MVarGroup</div><div style>takeMVarGroup :: MVarGroup a -> IO a</div><div style><br></div>
<div style>
<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Don't forget to think about throwTo. Though I suspect that's not too hard (just invalidate the queue).<br>
<br></blockquote><div><br></div><div style>I haven't looked at this at all.</div><div style><br></div><div style>Alexander</div><div style><br></div></div></div></div>