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

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_hookdetail::uproc_chan_list_tag, public boost::intrusive::list_base_hookdetail::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 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?