Guest User

MCS atomic transferring cond var 2

a guest
Jul 25th, 2011
1,825
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