<div dir="ltr"><br><div style>Ok, another round of fixes and insights:</div><div style><br></div><div style>I&#39;ve renamed the &quot;tso&quot; field in MVarGroup to &quot;blocked_tso&quot; and strenghtened invariants so that it is only defined in the state where the TSO is actually blocking.  I also used &#39;TAKEN&#39; instead of &#39;PUT&#39; in the state names.  That must have been confusing, sorry about that.  I&#39;ve renamed the states to be clearer.<br>

</div><div style><br></div><div style>It is important to understand that this MVarGroup is a &quot;one-shot&quot; animal.  It can be created, MVars can be registered, and then it is possible to block on it.  After that, no operation on it make any sense.  Another blocking operation will have to create a new MVarGroup.</div>

<div style><br></div><div style>There are good reasons for this, and I&#39;ll show why this is an almost necessary price to pay for not locking all MVars atomically.  A higher level API should be able to paper over this by keeping the MVar set that the user sees away from the RTS, and creating the MVarGroup inside the &#39;takeMVarGroup&#39; function.</div>

<div style><br></div><div style>So we assume we cannot atomically remove the MVarGroup from the TSOQueue of all of the MVars once one of the MVars have been &#39;put&#39;.  Instead we ask the MVars to ignore an INVALID MVarGroup and just remove it from the TSOQueue wait list.</div>

<div style><br></div><div style>If we ever were to change the state of an MVarGroup from INVALID back to one of the active states, then a random subset of the registered MVars will have the MVarGroup in their TSOQueue which wouldn&#39;t make sense.</div>

<div style><br></div><div style><b>Here is me trying to do a multi-shot (block multiple times) design:</b></div><div style>Another option would be to ask the MVars to <b>ignore, but not remove</b> an MVarGroup that is in a LATENT state.  This state would be &quot;we&#39;re still registering MVars, and haven&#39;t started blocking yet.  Nothing to see here, please ignore&quot;. From the MVar&#39;s point of view, this TSOQueue object is not on the wait list, but it is not removed either.  This means that we indeed can change the state of the MVarGroup and it will suddenly be active in all MVars.  </div>

<div style><br></div><div style>However there&#39;s a problem.  When calling putMVar and the only TSOQueue element is a LATENT one, it should be ignored, right?  So the putMVar&#39;s TSO wants to block.  This requires the TSO that calls &#39;takeMVarGroup&#39;, and that wants to change out from the LATENT state to go through all associated MVars to wake up a blocked one.  This seems to introduce a certain level of complexity, for example keeping track of all MVars associated with an MVarGroup.</div>

<div style><br></div><div style>All of these pointers firmly tie the lifetime of the MVarGroup to the set of MVars that refer to it.  The multi-shot MVarGroup requires manual resource management to disentangle it from MVars, or it will outlive the last MVar it has been associated with, even though it is not used.</div>

<div style><br></div><div style>Because of the lifetime problem, it will be &quot;necessary&quot; to support a &#39;unregisterMVar&#39; function that makes it possible to discard an MVarGroup, and possibly more set operations.</div>

<div style><br></div><div style>Unfortunately, unregisterMVar and being able to discard MVarGroups introduces empty MVarGroups.</div><div style><br></div><div style>Empty MVarGroups are invalid to block on.  Granted single-shot MVarGroups can only be blocked on once, so both APIs are fragile, but single-shot MVarGroups can naturally be wrapped in a safe higher-level construct that doesn&#39;t see the RTS&#39; MVarGroup.</div>

<div style><br></div><div style>Thus all in all, this adds somewhat more record-keeping and a slightly more fragile API because functions that couldn&#39;t fail now can fail, and care must be taken to not make GC of MVarGroups hard.</div>

<div style><b>// end of multi-shot discussion<br></b></div><div style><br></div><div style><br></div><div style>Another insight: unionMVarGroup is not well defined in all cases, and is thus probably not a good idea.  Both MVarGroups can have an MVar put, and thus the natural result would be to return both elements when blocking.  That&#39;s not a good primitive.</div>

<div style><br></div><div style>Another insight: MVars and MVarGroups are semantically equivalent enough that I think takeMVar can be implemented using an MVarGroup.  This means that they could conceptually be collapsed into one concept.  I think this is possible by conceptually splitting the &#39;put&#39; and &#39;take&#39; sides of the object.  Today we have:</div>

<div style><br></div><div style><div>data MVar a = MVar (MVar# RealWorld a)</div><div><br></div><div style>we could instead have something like</div><div style><br></div><div style>data MVar a = MVar (MVar# RealWorld a, [MVar# RealWorld a])</div>

<div><br></div><div style>where the first tuple element is  used for &#39;put&#39;, and the set consisting of the first and second tuple elements are used for &#39;take&#39;, with one-shot MVarGroups used in the background.</div>

</div><div style><br></div><div style>Here&#39;s a new version of the comment with better invariants and naming for one-shot MVarGroup:</div><div style><br></div><div style><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><b>   Invariants:</b></div><div><b>   - At least one MVarTSOQueue element must point to an MVarGroup.</b></div><div><b>   - &quot;blocked_tso&quot; is only defined in state NOT_PUT_WITH_TSO</b></div>

<div><b>   - &quot;deferred_result&quot; is only defined in state PUT_NO_TSO</b></div><div><br></div><div><b>   In the higher-level API we further strenghten the first invarant:</b></div><div><b>   - MVars can only be added to an MVarGroup, not removed.</b></div>

<div><br></div><div>   The MVarGroup acts as a synchronization point that decides which</div><div>   MVar &quot;won&quot; the &#39;put&#39;, and as a storage area for the result <b>if no</b></div><div><b>   TSO has blocked on the group yet</b>.</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 an MVar in the MVarGroup is</div><div>   &#39;put&#39;, and <b>2) whether a TSO is blocking</b>.</div>

<div><br></div><div>   The MVarGroup goes through the following states.</div><div><br></div><div>   <b>NOT_PUT_NO_TSO</b> (false, false):</div><div>        No MVars have been &#39;put&#39;. No TSO associated.  This is the state of the</div>

<div>        group in the normal case while MVars are being added to the</div><div>        group.  Next: PUT_NO_TSO or NOT_PUT_WITH_TSO</div><div><br></div><div>   <b>PUT_NO_TSO</b> (true, false):</div><div>        One MVar has been &#39;put&#39; without an associated TSO. The value</div>

<div>        that is &#39;put&#39; is stored in the &quot;deferred_result&quot;. When a TSO</div><div>        later tries to block on the group, this value will be</div><div>        immediately returned.  Note that this is the only state where</div>

<div>        &quot;deferred_result&quot; is defined.  Next: INVALID</div><div><br></div><div>   <b>NOT_PUT_WITH_TSO</b> (false, true):</div><div>        A 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. Note that</div><div>        this is the only state where &quot;blocked_tso&quot; is defined.</div>

<div>        Next: 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><br>
</div>
<div>typedef struct StgMVarGroup_ {</div><div>    StgHeader        header;</div><div>    StgWord          lock;  // Protects everything below</div><div>    /* The state of the MVarGroup */</div><div>    StgWord          state GUARDED_BY(lock);</div>

<div><b>    // When the TSO is &quot;woken up&quot; by a &#39;put&#39; on an MVar.  Only defined</b></div><div><b>    // in state &#39;PUT_NO_TSO&#39;</b></div><div><b>    StgClosure      *deferred_result GUARDED_BY(lock);</b></div>

<div><b>    // The blocked TSO associated with the MVar group. Only defined in</b></div><div><b>    // state &#39;NOT_PUT_WITH_TSO&#39;</b></div><div><b>    struct StgTSO_  *blocked_tso GUARDED_BY(lock);</b></div><div>}</div>

</div><div style><br></div><div style>Alexander</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Feb 15, 2013 at 9:09 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">On Fri, Feb 15, 2013 at 8:54 AM, Edward Z. Yang <span dir="ltr">&lt;<a href="mailto:ezyang@mit.edu" target="_blank">ezyang@mit.edu</a>&gt;</span> wrote:<br>

<div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Apologies for the kibitzing.<br>
<div><br></div></blockquote><div><br></div><div>If anyone, it&#39;s me proposing weird stuff :-)</div><div class="im"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


<div>
&gt; -- This will fail if the MVarGroup is not associated with the current<br>
&gt; process (if the MVarGroup&#39;s TSO is not the current TSO)!<br>
<br>
</div>I&#39;m not super keen about this requirement. What if I want to create an MVarGroup<br>
but pass it to another thread?<br>
<span><font color="#888888"><br></font></span></blockquote><div><br></div></div><div>Our emails crossed each other :-).  As you can see, I think this is solvable.</div><div><br></div><div>Alexander</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span><font color="#888888">
Edward<br>
</font></span></blockquote></div><br></div></div>
</blockquote></div><br></div>