Guest User

MCS atomic transferring cond var

a guest
Jul 20th, 2011
1,903
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