[Info-vax] writing a lock free linked list

[Joshua Lehrer]

I am trying to write a lock-free linked list.  I belive I have the
general
idea down.  What I am having trouble with is:

1) do I need memory barriers anywhere?  I'm not even sure what a
memory barrier is. :(

2) Is the check m_pFreelist for null legal?  I'm not sure that is
right.

3) I am using __CMP_SWAP_QUAD, but there are also __CMP_SWAP_QUAD_ACQ
and
__CMP_SWAP_QUAD_REL routines.  What do those do?

Here is my code for adding to the linked list.  m_pFreelist is the
shared global variable:

//add "addr" to the linked list of nodes called "m_pFreelist"
  node * const new_head = (node*)addr;
  while (1) {
    node * const old_head = m_pFreelist;
    new_head->m_pNext = old_head;

    //m_pFreelist = new_head iff (m_pFreelist==old_head);
    if (__CMP_SWAP_QUAD(&m_pFreelist,
     reinterpret_cast<__int64>(old_head),
     reinterpret_cast<__int64>(new_head))) {
      break;
    }
  }


and here is my code for removing from the linked list:

 while (1) {
    node * const old_head = m_pFreelist;

    if (!old_head)
      return NULL;

    node * const new_head = old_head->m_pNext;

    //m_pFreelist = new_head iff (m_pFreelist == old_head)
    if (__CMP_SWAP_QUAD(&m_pFreelist,
     reinterpret_cast<__int64>(old_head),
     reinterpret_cast<__int64>(new_head))) {
      return old_head;
    }
  }



I *think* this code is okay, but I am not sure if I need a memory
barrier
anywhere, and, if so, is it a read barrier, write barrier, or both.
Also,
is that test for NULL valid?  I think it doesn't need to be "guarded",
but I'm not sure.  Finally, can
I use the acquire or release versions of compare and swap instead of
the generic one.  What do they do?

This is the only code that modifies m_pFreelist.  No other code will
touch that variable.

Thanks,

joshua