SHARE
TWEET

MCS atomic transferring cond var

a guest Jul 20th, 2011 1,427 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. // MCS Cond Var with atomic ownership transfer
  3. // by Charles Bloom (www.cbloom.com)
  4. // copyright 2011
  5. // public domain
  6.  
  7. struct mcs_node
  8. {
  9.         std::atomic<mcs_node *> m_next;
  10.         std::atomic<HANDLE> m_event;
  11.        
  12.         mcs_node()
  13.         {
  14.                 m_next($).store(0);
  15.                 m_event($).store(0);
  16.         }
  17. };
  18.  
  19. struct mcs_cond_var
  20. {
  21. public:
  22.         // m_lock points to the tail of the waiter list all the time
  23.         std::atomic<mcs_node *> m_tail;
  24.  
  25.         //-------------
  26.         std::mutex      m_waiter_mutex;
  27.         VAR_T(mcs_node *)  m_waiters;
  28.         //-------------
  29.        
  30.         mcs_cond_var() : m_waiters(NULL)
  31.         {
  32.                 m_tail($).store( NULL );
  33.         }
  34.         ~mcs_cond_var()
  35.         {
  36.                 RL_ASSERT( m_waiters($) == NULL );
  37.                 mcs_node * n = m_tail($).exchange(0);
  38.                 if ( n )
  39.                         delete n;
  40.         }
  41.        
  42.         // note : handle should come from TLS - no need to ever Create/Close
  43.         static HANDLE alloc_event() { return CreateEvent(NULL,0,0,NULL); }
  44.         static void free_event(HANDLE h) { if ( h ) CloseHandle(h); }
  45.        
  46.         struct guard
  47.         {
  48.                 mcs_node        m_node; // provide node on the stack
  49.                 guard() { }
  50.                 ~guard() { }
  51.         };
  52.        
  53.         void lock(guard & g)
  54.         {
  55.                 mcs_node * me = &(g.m_node);
  56.                
  57.                 ASSERT( me->m_next($).load(std::mo_relaxed) == NULL );
  58.                
  59.                 // publish my node as the new tail :
  60.                 VAR_T(mcs_node *) pred = m_tail($).exchange(me, std::mo_acq_rel);
  61.                 if ( pred($) != NULL )
  62.                 {
  63.                         // pred can't see me until I store to m_next
  64.                         // can choose if I want to spin or wait :
  65.                         HANDLE h = alloc_event();
  66.                         me->m_event($).store( h , std::mo_relaxed );
  67.                        
  68.                         // publish me to previous lock-holder :
  69.                         pred($)->m_next($).store(me, std::mo_release );
  70.                
  71.                         // now this is the spin -
  72.                         // wait on predecessor setting my flag -
  73.                         WaitForSingleObject(h,INFINITE);
  74.                
  75.                         free_event(h);
  76.                        
  77.                         RL_ASSERT( me->m_event($).load(std::mo_relaxed) == h );
  78.                         me->m_event($).store( 0 , std::mo_relaxed );
  79.                 }
  80.         }
  81.        
  82.         // unlock_internal does all the work up to but not including waking up the next owner
  83.         HANDLE unlock_internal(guard & g, mcs_node * new_tail)
  84.         {
  85.                 mcs_node * me = &(g.m_node);
  86.                
  87.                 VAR_T(mcs_node *) next = me->m_next($).load(std::mo_acquire);
  88.                 if ( next($) == NULL )
  89.                 {
  90.                         mcs_node * tail_was_me = me;
  91.                         if ( m_tail($).compare_exchange_strong( tail_was_me,new_tail,std::mo_acq_rel) )
  92.                         {
  93.                                 // got null in tail, mutex is unlocked
  94.                                 return 0;
  95.                         }
  96.                        
  97.                         // if tail was changed, then I will get something stored in my next
  98.                         //      wait for it ...
  99.                         rl::linear_backoff bo;
  100.                         for(;;)
  101.                         {
  102.                                 next($) = me->m_next($).load(std::mo_acquire);
  103.                                 if ( next($) != NULL )
  104.                                         break;
  105.                                 bo.yield($);
  106.                         }
  107.                 }
  108.                
  109.                 // let next guy in :
  110.                 HANDLE h = next($)->m_event($).load( std::mo_relaxed );
  111.                 RL_ASSERT( h != 0 );
  112.                 return h;
  113.         }
  114.        
  115.         void unlock(guard & g)
  116.         {
  117.                 HANDLE h = unlock_internal(g,NULL);
  118.                 if ( h )
  119.                         SetEvent(h);
  120.        
  121.                 // prep for reuse :
  122.                 g.m_node.m_next($).store(NULL,std::mo_relaxed);
  123.         }
  124.                
  125.         void signal_unlock(guard & g)
  126.         {
  127.                 mcs_node * me = &(g.m_node);
  128.                
  129.                 // if there is no waiter, just unlock
  130.                 // if there is a waiter, transfer the mutex directly to him
  131.                 //  he will then do the unlock that I would have done
  132.                
  133.                 // first, get the waiter while mutex is held
  134.                 VAR_T(mcs_node *) waiter = NULL;
  135.                
  136.                 {
  137.                 m_waiter_mutex.lock($);
  138.  
  139.                 // pop one off front :
  140.                 waiter($) = m_waiters($);
  141.                 if ( waiter($) != NULL )
  142.                         m_waiters($) = waiter($)->m_next($).load(std::mo_relaxed);
  143.                
  144.                 m_waiter_mutex.unlock($);
  145.                 }
  146.                
  147.                 if ( ! waiter($) )
  148.                 {
  149.                         unlock(g);
  150.                         return;
  151.                 }
  152.                
  153.                 // waiter might get put in tail, so make sure it's a valid lock node now :
  154.                 waiter($)->m_next($).store( NULL , std::mo_relaxed );
  155.                        
  156.                 // there's a race here just like in unlock
  157.                 // someone trying to grab the mutex may be trying to set me->m_next
  158.                 // I need to wait for him to be done :
  159.                 HANDLE next_locker = unlock_internal(g,waiter($));
  160.                 // now me->next should be set (if it will be set)
  161.                
  162.                 HANDLE waiter_h = waiter($)->m_event($).load(std::mo_relaxed);
  163.                 RL_ASSERT( waiter_h != 0 );
  164.                
  165.                 // if next_locker was 0, waiter got set to the tail, so don't touch waiter->next
  166.                 VAR_T(mcs_node *) next = me->m_next($).load(std::mo_relaxed);
  167.                 if ( next_locker != 0 )
  168.                 {
  169.                         RL_ASSERT( next($) != NULL );
  170.                         waiter($)->m_next($).store( next($) , std::mo_release );
  171.                 }
  172.                 else
  173.                 {
  174.                         // tail moved to waiter; he now holds the lock
  175.                         RL_ASSERT( next($) == NULL );
  176.                         //waiter->m_next($).store( NULL , std::mo_relaxed );
  177.                 }
  178.  
  179.                 // transfer mutex for him :
  180.                 SetEvent(waiter_h);
  181.                
  182.                 // me is not visible to anyone ; prep for reuse :
  183.                 me->m_next($).store(NULL,std::mo_relaxed);
  184.         }
  185.        
  186.         void broadcast_unlock(guard & g)
  187.         {
  188.                 mcs_node * me = &(g.m_node);
  189.                        
  190.                 // first, get the waiter while mutex is held
  191.                 mcs_node * waiters = NULL;
  192.                
  193.                 {
  194.                 m_waiter_mutex.lock($);
  195.  
  196.                 // exchange out the list
  197.                 waiters = m_waiters($);
  198.                 m_waiters($) = NULL;
  199.                
  200.                 m_waiter_mutex.unlock($);
  201.                 }
  202.                
  203.                 if ( ! waiters )
  204.                 {
  205.                         unlock(g);
  206.                         return;
  207.                 }
  208.                
  209.                 for(;;)
  210.                 {
  211.                         mcs_node * nextWaiter = waiters->m_next($).load(std::mo_relaxed);
  212.                         waiters->m_next($).store(NULL,std::mo_relaxed);
  213.                         VAR_T(mcs_node *) waiter = waiters;
  214.                        
  215.                         // waiter might get put in tail, so make sure it's a valid lock node now :
  216.                         waiter($)->m_next($).store( NULL , std::mo_relaxed );
  217.                
  218.                         // there's a race here just like in unlock
  219.                         // someone trying to grab the mutex may be trying to set me->m_next
  220.                         // I need to wait for him to be done :
  221.                         HANDLE next_locker = unlock_internal(g,waiter($));
  222.                         // now me->next should be set (if it will be set)
  223.                        
  224.                         HANDLE waiter_h = waiter($)->m_event($).load(std::mo_relaxed);
  225.                         RL_ASSERT( waiter_h != 0 );
  226.                        
  227.                         // if next_locker was 0, waiter got set to the tail, so don't touch waiter->next
  228.                         mcs_node * next = me->m_next($).load(std::mo_relaxed);
  229.                         if ( next_locker != 0 )
  230.                         {
  231.                                 RL_ASSERT( next != NULL );
  232.                                 waiter($)->m_next($).store( next , std::mo_relaxed );
  233.                         }
  234.                         else
  235.                         {
  236.                                 RL_ASSERT( next == NULL );
  237.                         }
  238.  
  239.                         // transfer mutex for him :
  240.                         SetEvent(waiter_h);
  241.                        
  242.                         // mutex is now locked by someone else
  243.                        
  244.                         me->m_next($).store(NULL,std::mo_relaxed);
  245.                                
  246.                         if ( nextWaiter == NULL )
  247.                                 return; // done signaling
  248.                        
  249.                         // relock mutex :
  250.                         lock(g);
  251.                        
  252.                         waiters = nextWaiter;
  253.                 }
  254.         }      
  255.        
  256.         void unlock_wait_lock(guard & g)
  257.         {
  258.                 HANDLE unlock_h;
  259.                
  260.                 HANDLE wait_handle = alloc_event();
  261.  
  262.                 {
  263.                 m_waiter_mutex.lock($);
  264.                
  265.                         // unlock must be inside waiter mutex ?
  266.                         //  yes, if not then signal can get missed between unlock and adding waiter
  267.                         //       and we go into a deadlock wait
  268.                         // you can move this out if signal incs an atomic count
  269.                         //      and you check the count before & after unlock and if they're not the same abort the wait
  270.                         unlock_h = unlock_internal(g,NULL);
  271.  
  272.                         // mutex may now be unlocked if tail was set to null
  273.  
  274.                         // after unlock, node is now mine to reuse :
  275.                         mcs_node * node = &(g.m_node);
  276.                         node->m_next($).store( 0 , std::mo_relaxed );
  277.                         node->m_event($).store( wait_handle , std::mo_relaxed );
  278.                
  279.                         // put on end of list :
  280.                         if ( m_waiters($) == NULL )
  281.                         {
  282.                                 m_waiters($) = node;
  283.                         }
  284.                         else
  285.                         {
  286.                                 // dumb way of doing FIFO but whatever for this sketch
  287.                                 mcs_node * parent = m_waiters($);
  288.                                 while ( parent->m_next($).load(std::mo_relaxed) != NULL )
  289.                                         parent = parent->m_next($).load(std::mo_relaxed);
  290.                                 parent->m_next($).store(node,std::mo_relaxed);
  291.                         }
  292.                        
  293.                 m_waiter_mutex.unlock($);
  294.                 }
  295.  
  296.                 if ( unlock_h )
  297.                 {
  298.                         // wake new lock-holder and also wait for the signal :
  299.                         SignalObjectAndWait(unlock_h,wait_handle,INFINITE,FALSE);
  300.                 }
  301.                 else
  302.                 {      
  303.                         WaitForSingleObject(wait_handle,INFINITE);
  304.                 }
  305.                
  306.                 // I am woken and now own the lock
  307.                 // my node has been filled with the guy I should unlock
  308.                
  309.                 free_event(wait_handle);
  310.                
  311.                 RL_ASSERT( g.m_node.m_event($).load(std::mo_relaxed) == wait_handle );
  312.                 g.m_node.m_event($).store(0,std::mo_relaxed);
  313.                
  314.         }
  315.        
  316. };
RAW Paste Data
Top