Subj : Lock free t-safe smart pointer based on double linked list
To   : comp.programming.threads
From : rGlory
Date : Tue May 10 2005 08:28 am

Hi,

I spent some time breaking my head on this topic recently. I got some
interesting results (at least for me) and would like to discuss it.
Mostly I would be happy if somebody could point that I am reinventing
my wheel here. It is rather interesting and challenging problem for me
but I got into a point where I do not want to spend more of my time on
something that's already known.

So I tried to make algorithms on lock free thread safe double linked
list element removal and insertion. Since I am trying to implement
smart pointer I do not need a traversal algorithm. But to find one
would not hurt :).  So I have this:
struct item {
   item *forward, *backward;
};
and item is initialized so forward and backward point to itself.

and two atomic operations:
item *set_forward( item *to, item *it );
item *set_backward( item *to, item *it );

they set "to->forward" or "to->backward" pointer to "it"
and return old value atomically. So the first algorithm is
insert_right:
void insert_right( item *left, item* it )
{
   set_backward( it, left );
   item *right = set_forward( left, it );
   item *tmp = set_forward( it, right );
   set_backward( right, it );
}

I made a small program to check all combinations of atomic operations
happened from different threads and it looks like that insert_right is
safe to another insert_right independend of where that insertion
happened. (I checked combinations of operations up to 3 threads) Now
trivial implementation of removal:
void remove( item *it )
{
   item *left = set_backward( it, it );
   item *right = set_forward( it, it );
   item *tmp = set_forward( left, right );
   set_backward( right, left );
}

This removal algorithm works safe if running in parallel of
insert_right where left is the same as it for remove. Which is not the
case when item being removed is left->forward. There are some
combinations of operations where double linked list is broken. And what
is interesting that all such combinations can be detected by tmp value
in insert_right and remove functions. But it is not simple to solve
such situation (at least for me). Also I tried another insertion
algorithm "insert_left" which is a reflection of
"insert_right". Again it looks to safe to use them together if the
same element used as first argument. But not the case when insert_right
uses on item and insert_left uses another one. (if there are two
elements already in the list).

There is another problem though. To use such structure as SP I need to
put a pointer into struct item. It is not clear to me how to safely
assign such pointer when "everything can change any time".

Any ideas?

.