<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">&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 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] -&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 style>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 style><br></div><div style>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 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&#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 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 &quot;wakeup&quot; 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 &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> </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 style>I didn&#39;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&#39;s TSO is not the current TSO)!</div>

<div style>registerMVar :: MVarGroup a -&gt; MVar a -&gt; IO (MVarGroup a)</div><div style><br></div><div style>-- Block on the MVarGroup</div><div style>takeMVarGroup :: MVarGroup a -&gt; 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&#39;t forget to think about throwTo.  Though I suspect that&#39;s not too hard (just invalidate the queue).<br>
<br></blockquote><div><br></div><div style>I haven&#39;t looked at this at all.</div><div style><br></div><div style>Alexander</div><div style><br></div></div></div></div>