Lock free thread safe smart pointer based on double linked list

Discussion in 'C++' started by Vyacheslav Kononenko, May 13, 2005.

  1. 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
    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?

    Vyacheslav Kononenko, May 13, 2005
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sydex
    Victor Bazarov
    Feb 17, 2005
  2. Protoman
    Aug 14, 2006
  3. Chris Thomasson
    Casper H.S. Dik
    Sep 22, 2007
  4. Gabriel Rossetti
    Gabriel Rossetti
    Aug 29, 2008
  5. John Nagle
    John Nagle
    Mar 12, 2012

Share This Page