SHARE
TWEET

MCS atomic transferring cond var 2

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