Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #1077

New solution for ABA in lock-free lists?

Show all headers | View raw

I was experimenting with atomic operations in C++11, and wanted a lock-free FIFO with multiple readers and writers. The performance is so much better than the mutexed solution.

Since objects are re-inserted regularly in my application, the ABA problem turned out to be very real. So I came up with my own "solution" which appears to work very well in practice.

The basic idea is to introduce a new state to each pointer: NULL, node and BUSY. The BUSY state acts as a mutex, so if you are unlucky for two threads to access the same memory simultaneously, then the second thread must spin until the pointer becomes non-BUSY. Then I introduce two new operations, "acquire" and "release", implemented as follows (C++11):

        template<typename T>
        T acquire(std::atomic<T> & value, T busy)
        {
                T v;
                int spin_count=2000;
                for(;;)
                {
                        v = value.exchange(busy, std::memory_order_acquire);
                        if(v!=busy) return v;
                        else if(--spin_count==0)
                        {
                                // Yield
                                std::this_thread::sleep_for(std::chrono::seconds(0));
                                spin_count=2000;
                        }
                }
        }

        template<typename T>
        void release(std::atomic<T> & value, T new_value)
        {
                value.store(new_value, std::memory_order_release);
        }

We can implement a LIFO very simply using the above operations:

  struct atomic_node
  {
        atomic_node * next;
  } busy;

  class atomic_lifo
  {
  public:
        atomic_lifo();
        void push(atomic_node * n);
        atomic_node * pop();
  private:
        std::atomic<atomic_node*> list;
  };

  void active::atomic_lifo::push(atomic_node * n)
  {
        n->next=acquire(list,&busy);
        release(list,n);        
  }

  active::atomic_node * active::atomic_lifo::pop()
  {
        atomic_node * n = acquire(list,&busy);
        release(list,n?n->next:nullptr);
        return n;
  }

The FIFO is more complex but actually the push operation is both lock-free and wait-free. The full code is here:

http://code.google.com/p/cppao/source/browse/trunk/include/active/atomic_fifo.hpp
http://code.google.com/p/cppao/source/browse/trunk/include/active/atomic_lifo.hpp
http://code.google.com/p/cppao/source/browse/trunk/include/active/atomic_node.hpp
http://code.google.com/p/cppao/source/browse/trunk/lib/atomic.cpp

Performance-wise, this is as good if not better than the naive (but broken) slist algorithm, yet I have not seen it mentioned anywhere. Of course, the solution is not wait-free, but this does not seem to be hurting my throughput. I just want to ask if this solution is correct and how it compares to other approaches.

Cheers, Calum

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar

Thread

New solution for ABA in lock-free lists? calum74@gmail.com - 2012-09-17 03:13 -0700
  Re: New solution for ABA in lock-free lists? Marcel Müller <news.5.maazl@spamgourmet.org> - 2012-09-20 00:03 +0200
    Re: New solution for ABA in lock-free lists? calumg <spambox@calumgrant.net> - 2012-09-21 04:20 -0700
      Re: New solution for ABA in lock-free lists? Marcel Müller <news.5.maazl@spamgourmet.com> - 2012-09-28 00:58 +0200

csiph-web