CODEWITHSUNDEEP
cgccstructatomicgcc6
nkvnkv
nkvnkv

Reputation: 954

atomic load/save on c struct (gcc) questions

trying my luck in making lock-free singly linked list implementation.

typedef _Atomic struct _node
  {
    void *data;
    struct _node *next;
  } Node;

does this make all members of struct with _Atomic atomic as well?

void add_head ( Linked_list* list, void* data )
{
  if ( debugging )
  {
      printf ( "%s\n", __func__ );
  }
  Node *node = ( Node* ) calloc ( 1, sizeof (Node ) );
  //init_node_mutex(node);
  //lock_node_mutex(node);
  atomic_exchange ( &node->next, NULL );
  atomic_exchange ( &node->data, data );

  if ( list->head == NULL )
  {
      Node* the_tail = atomic_load ( &list->tail );
      //  lock_node_mutex ( the_tail );
      atomic_exchange ( &node->next, NULL );
      atomic_compare_exchange_weak ( &list->tail, the_tail, node );

      //unlock_node_mutex ( the_tail );

  }
  else
  {

      Node* the_next = atomic_load ( &node->next );
      // lock_node_mutex ( the_next );
      atomic_compare_exchange_weak ( &node->next, the_next, list->head );
      // unlock_node_mutex ( the_next );
  }

  Node* the_head = atomic_load ( & list->head );
  //lock_node_mutex ( the_head );
  atomic_store ( &list->head, node );
  atomic_store ( &list->current, node );
  //unlock_node_mutex ( the_head );
  //unlock_node_mutex(node);
  atomic_fetch_add ( &list->size, 1 );
}

are usages are atomic_load and atomic_store correct?

Upvotes: 0

Views: 606

Answers (2)

Tim
Tim

Reputation: 1527

In addition to @MikeRobinson's comment, I would add that while your code is "lock-free" in the sense that it does not contain any explicit use of locks, it is now (somewhat ironically) no longer thread-safe. Writing lock-free code is enormously difficult. I recommend reading through this to get a bird's-eye view of the world, and then reading this to get some details or Chapter 7 of this book (it's in C++). You can always go look through the source of Boost.LockFree for inspiration.

Upvotes: 1

Mike Robinson
Mike Robinson

Reputation: 8945

Okay, I debated whether to post this as a "comment" or an "answer," but I'm going to go for broke here.

My instincts are rather screaming at me that "it really doesn't matter if the individual operations that you're performing are, or are not, "atomic," because you are executing many operations in a row in order to accomplish what you are ultimately trying to do. Even if those individual steps are "atomic," the operation as a whole is not.

An "atomic" operation is one that uses specialized machine instructions, such as the LOCK prefix on the x86 or "compare-and-swap" instructions on big-iron, to perform a single operation such that no other CPU (or core) will interfere with that single operation.

But, you can't do what you're trying to do in "a single instruction," atomic or not.

Therefore, I cordially recommend that you now abandon your present course, put those "mutex" calls back in, and remove the "atomics." Your code (and, all such code as this ...) needs those mutexes. In my opinion, you are chasing a white rabbit down a blind alley.

(And incidentally, "mutex" operations sometimes make very good use of those "atomic instructions," so they're probably a good bit more efficient than you might fear.)

Upvotes: 1

Related Questions