Re: [Boost-users] [intrusive] lock-free algorithms

From: Zeljko Vrba (zvrba_at_[hidden])
Date: 2007-06-13 03:59:14

On Wed, Jun 13, 2007 at 08:11:45AM +0200, Ion Gaztañaga wrote:
> 
> I haven't thought about this, but it sounds interesting. But lock-free 
> is far beyond by possibilities.
> 
It's not _that_ hard; good papers have all algorithms in pseudo-code
which is mostly enough :)

> 
> Are you sure these new containers fit in Intrusive? Maybe a new, 
> lock-free containers library is what we need.
> 
Actually, I'm not sure.  Lock-free objects support a very limited set of
operations..

> 
> This is a big problem. First, Intrusive does not support (for the 
> moment) SunCC. Second, we will need portable containers to admit them in 
> Intrusive.
> 
BTW, SunCC works fine with base hooks.  Code like

namespace detail {
struct uproc_chan_list_tag;
struct uproc_sched_list_tag;
}

class user_process :
        public bvt_acct,
        public boost::intrusive::list_base_hook<detail::uproc_chan_list_tag>,
        public boost::intrusive::list_base_hook<detail::uproc_sched_list_tag>
{
...
};

works for me with no problems!  Now that you've mentioned it, did you come
a bit further with debugging member hooks under SunCC?

> 
> Maybe you could join with other lock-free experts to develop the 
> library. Just curious: Do you support all the Intrusive interface? What 
> thread-safety do you achieve with containers, hooks, and algorithms?
> 
I didn't yet design the classes, but:

- stack: push_front, pop_front
- queue: push_back,  pop_front

These are pretty much the only safe operations that do not require locks.
Plus, some trickery with either SMR or double-wide CAS, but this is just
an implementation detail.  As for hooks, my own doubly-linked list class
had an interface like:

template<typename NodeT>
struct list_node_traits {
        /* Get prev/next values in the node. */
        static NodeT *prev(const NodeT&) { THROW("list_node_traits"); }
        static NodeT *next(const NodeT&) { THROW("list_node_traits"); }
                
        /* Set prev/next values in the node. */
        static void prev(NodeT&, NodeT*) { THROW("list_node_traits"); }
        static void next(NodeT&, NodeT*) { THROW("list_node_traits"); }
};

Instead of inventing "hook classes", I let the user allocate hooks manually,
and specialize as many traits classes as he needs.  (One traits class per hook
in the "target" structure).  If the user is consistent in naming of the links
(e.g. next/prev), one traits class can be reused for many node types.

A design question for you: Why did you introduce explicit hook classes which
hide this machinery from the user instead of letting the traits be a part of
the public interface?

In my case, automatic hooks (like yours) would be kinda "over-engineering"
(besides, I do not know how to do it myself in reasonable time...)

The design space I have in mind is something as follows:

- implementation of atomic instructions (external function, inline ASM)
- optional locking atomic operations (think x86 LOCK prefix; it is not
  needed if it can be assured that the data structure will NOT be accessed
  by multiple CPUs)
- safety level (more safety = increasing overhead: CAS, CAS2, SMR)

The instantiation would be like

lf_fifo<my_traits> fifo;

my_traits would contain all configuration data: how to access hooks and
implementations of operations, eg:

struct my_traits : public lf_atomic_up_ext, public lf_safety_cas2 {
 // custom code for hook access
};

Now, neccessary hooks differ for different safety levels, and SMR requires
thread-private and thread-global storage.

Hmm, I might be overengineering, but I want to write a single generic
algorithm with easy compile-time configuration.  Any suggestions?