<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Feb 15, 2013 at 5:38 AM, Alexander Kjeldaas <span dir="ltr">&lt;<a href="mailto:alexander.kjeldaas@gmail.com" target="_blank">alexander.kjeldaas@gmail.com</a>&gt;</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 dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">

<div class="im">On Thu, Feb 14, 2013 at 10:37 PM, Simon Marlow <span dir="ltr">&lt;<a href="mailto:marlowsd@gmail.com" target="_blank">marlowsd@gmail.com</a>&gt;</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>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] -&gt; IO (a, Int)<br>
<br>
This is implemented by this change:<br>
</blockquote></div>
[snip]<br>
<br>
I&#39;ve occasionally wondered whether we could do this.  So I think you&#39;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&#39;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><div>That&#39;s true.  First I didn&#39;t think of this.  Then I thought I&#39;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><br></div><div>Instead of the group_head and group_link, we replace the &#39;tso&#39; link with a MVarGroup link in the multi-case.</div><div><br></div><div><div><div class="im"><div>typedef struct StgMVarTSOQueue_ {</div>


<div>    StgHeader                header;</div><div>    struct StgMVarTSOQueue_ *link;</div></div><div><b>    /* struct StgTSO_          *tso; */</b></div><div><b>    StgClosure              *tso_or_group;</b></div><div>

} StgMVarTSOQueue;</div>
<div><br></div></div><div>Then actually the MVarGroup doesn&#39;t know about the number of MVars, and MVars can be added one by one, but it has a simple state-machine.</div><div><br></div><div>What this design really does is decouple MVar registration from blocking.</div>


<div><br></div><div>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 &quot;wakeup&quot; and the MVar result is deferred and stored until the TSO actually does block on the MVarGroup.</div>


<div><br></div><div><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 &quot;won&quot; the &#39;put&#39;, and as a storage area for the result if</div><div>   the TSO hasn&#39;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 &#39;put&#39;.  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 &#39;put&#39;. The value that is</div>


<div>        &#39;put&#39; is stored in the &quot;deferred_result&quot;.  This is the state</div><div>        of the group when an MVar is &#39;put&#39; 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 &quot;deferred_result&quot; 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 &#39;put&#39; 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>        &#39;put&#39;, 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 &#39;put&#39; 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 &quot;woken up&quot; by a &#39;put&#39; on an MVar</div>


<div>    StgClosure      *deferred_result GUARDED_BY(mutex);</div><div>}</div></div><div><br></div></div></div><div class="im"><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&#39;t a primitive type, and you can&#39;t put MVar# into an Array# (kind mismatch).<br>
<br></blockquote><div><br></div></div><div>I didn&#39;t know that, but reading this is what forced the above design :-)</div><div><br></div><div>A very flexible API would be the following:</div><div><br>
</div><div>-- Create MVarGroup</div><div>newMVarGroup :: IO (MVarGroup a)</div><div><br></div></div></div></div></blockquote><div><br></div><div><div>Now I understand why it must be illegal to remove an MVar from an MVarGroup.</div>

<div>An invariant that must hold for a MVarGroup is this:  <b>The group can never be empty when a TSO is blocked on it.</b></div><div><br></div><div>One way of doing this is to have a counter in the MVarGroup structure, and support the full set of set operations, but that creates an API where &#39;takeMVarGroup&#39; can sometimes fail.  That leads to fragile software.</div>

<div><br></div><div>A better way is to make it impossible to create empty MVarGroups by changing newMVarGroup like this:</div><div><br></div><div>-- Create MVarGroup with a single element.</div><div>newMVarGroup :: <b>MVar a -&gt; </b>IO (MVarGroup a)</div>

</div><div><br></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"><div dir="ltr"><div class="gmail_extra">

<div class="gmail_quote"><div>-- Add an MVar to a MVarGroup. </div><div>-- This will fail if the MVarGroup is not associated with the current process (if the MVarGroup&#39;s TSO is not the current TSO)!</div>
<div>registerMVar :: MVarGroup a -&gt; MVar a -&gt; IO (MVarGroup a)</div><div><br></div></div></div></div></blockquote><div><br></div><div><div>The following is probably clearer about the mutation going on:</div><div style>

-- Add an MVar to a MVarGroup</div><div>registerMVar :: MVarGroup a -&gt; MVar a -&gt; IO ()<br></div></div><div><br></div><div><div>Now I think that the &quot;same-TSO&quot; restriction on registerMVar can be removed as well.</div>

<div>There is no code-path where the &quot;tso&quot; field of the MVarGroup need to be accessed until after the TSO is blocked on &#39;takeMVarGroup&#39;.</div><div><br></div><div>That leaves a pretty flexible API where MVarGroup can be passed freely between processes, but more importantly &#39;registerMVar&#39; should never fail.</div>

</div><div><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"><div dir="ltr">

<div class="gmail_extra"><div class="gmail_quote"><div></div><div>-- Block on the MVarGroup</div><div>takeMVarGroup :: MVarGroup a -&gt; IO a</div><div class="im"><div><br></div></div></div></div></div></blockquote><div>
<br>
</div><div style>A fourth operation that is consistent with these invariants is:</div><div style><br></div><div style>-- Makes both MVarGroups aliases for the same set of MVars</div><div style>unionMVarGroup :: MVarGroup a -&gt; MVarGroup a -&gt; IO ()</div>

<div style><br></div><div style><div>This can be supported by either overloading the &quot;tso&quot; field of MVarGroup, or adding a &quot;parent&quot; pointer that points to another MVarGroup.<br></div><div></div></div>
<div style>
<br></div><div style>This adds a lock order invariant:  Child MVarGroups must be locked before parent MVarGroups.</div><div><div style><div><br></div></div><div style>Alexander</div><div style><br></div></div></div></div>

</div>