takeOneMVar?

14 Feb 2013

      Hi,

I ended up staring at the PrimOps.cmm file today, and porting tryPutMVar to
C so it can be used from the RTS.

During my staring, it occurred to me that it should be possible to
implement a wait-on-multiple MVars with mostly no overhead.  I am guessing
that this would be desirable, but I am not sure.

My rough idea is like this:

-- wait for all MVars, return the value of one of them, and the
corresponding index
takeOneMVar :: [MVar a] -> IO (a, Int)

This is implemented by this change:

typedef struct StgMVarTSOQueue_ {
    StgHeader                header;
    struct StgMVarTSOQueue_ *link;
*    // The group_head and group_link are used when a TSO is waiting on*
*    // multiple MVars.  Multiple StgMVarTSOQueue objects*
*    // are created, one for each MVar, and they are linked using the*
*    // group_link pointer.  group_head always points to the first*
*    // element. The tso pointer will always be the same in this case.*
*    // The group head acts as a synchronization element for the whole
group.*
*    // When the    group head lock is acquired, the owner can invalidate
the group*
*    struct StgMVarTSOQueue  *group_head;*
*    struct StgMVarTSOQueue  *group_link;*
    struct StgTSO_          *tso;
} StgMVarTSOQueue;

Now, whenever a TSO should be woken up by the MVar code, if

... putMVar(...) {
 ...
 queue = mvar->queue...

loop:
 if (end_of_queue(queue) {
    return 0;
 }
* if (marked_as_invalid(queue) {  // invalid = (queue->group_head == NULL)
for example*
*    queue = queue->link;*
*    goto loop;*
* }*
* if (queue->group_head != queue) {*
*    // Try to win race to wake up the TSO with *our* MVar.
*
*    won = TryLock(queue->group_head);*
*    if (!won) {*
*        // ignore this queue element for now, we can't get the lock, *
*        // and it will be marked_as_invalid at some point in the future
anyways.*
*        queue = queue->link;*
*        goto loop;  // try next*
*    }*
*    if (won) {*
*        for all in group, mark them as "invalid"*
*        Unlock(queue->group_head);*
*        goto wake_up_tso;*
*    } else {
*
*        // Did not win*
*        goto loop;*
*    }*
 } else {
   ..what is currently done..

wake_up_tso:
  ... do wake up

Alexander

takeOneMVar?

Alexander Kjeldaas