Trying to implement linkedlist

Question

        public void Push(Node newNode)
    {
        while (true)
        {
            Node tmp = this.head;
            newNode.next = tmp;
            if (Interlocked.CompareExchange(ref this.head, newNode, tmp) == tmp)
            {
                break;
            }
        }
    }

    public Node Pop()
    {
        Node pop=null;

        while (this.head != null)
        {
            pop = this.head;
            var oldcount = this.popcount;
            var newcount = oldcount + 1;

            if (Interlocked.CompareExchange(ref this.popcount, newcount, oldcount) == oldcount)
            {
                pop = Interlocked.CompareExchange(ref head, head.next, head);
                break;
            }
            pop = null;
        }
            return pop;
    }
    //---------------------------------------------------------
    while (count < 10000) // 4 thread run this code
        {
            for (int i = 0; i < 2; i++)
            {
                Node temp;
                if (freelist.head != null)
                {
                    temp = freelist.Pop();
                    headlist.Push(temp);
                }
            }
            for (int j = 0; j < 1; j++)
            {
                Node temp;
                if (headlist.head != null)
                {
                    temp = headlist.Pop();
                    freelist.Push(temp);
                }
            }
            count++;
            Console.WriteLine(count);
        }

I'm trying to implement lock free linkedlist. I add popcount to avoid aba problem. And I implement Push and Pop using CAS. When I run this code, It is not working as I think.

    class Node
{
    public int data;
    public Node next;

    public Node(int data)
    {
        this.data = data;
    }

}

When I run code, a Node.next points itself. For example, Node.data = 99720 and Node.next = Node So, When I go to Node.next It is still 99720 Node. Can't figure out why it happen...

Answer 1

It looks like you are trying to build a lock-free stack. I'm not sure what (pseudo-) code you used as basis for your implementation, but your attempt to solve the ABA problem with popcount cannot work. When you are using a version tag to prevent ABA, it has to be combined with the pointer, i.e., the pointer and the tag have to be updated in a single atomic operation. Java provides AtomicStampedReference for exactly this purpose, but unfortunately .NET does not provide anything similar.

However, since you are working with .NET you have the luxury of a garbage collector, so you don't really need to worry about the ABA problem as long as you don't reuse your nodes.

BTW: your pop function is missing a loop.