Is the free() safe in the pop function of this lock free stack?

Question

I've been studying the lock free stack.
I was reading this link and the pop function got me wondering.

According to the link, the pop function is implemented as follows.

int lfstack_pop(_Atomic lfstack_t *lfstack)
{
    lfstack_t next, orig = atomic_load(lfstack);

    do{
       if(orig.head == NULL)
       {
            return -1;
       }
       next.head = orig.head->next;
       next.tag = orig.tag+1; //increase the "tag"
    }while(!atomic_compare_exchange_weak(lfstack,&orig,next));

    printf("poping value %d\n",orig.head->data);
    free(orig.head);

    return 0;
}

In the above implementation, we are solving the ABA problem by using separate tag information.
So far, so good.

But my question is this.
Is the line next.head = orig.head->next; thread-safe?

If the line next.head = orig.head->next; resumes in thread 2 after free(orig.head); in thread 1, isn't that an error because we're referencing next after orig.head has been deallocated?

The links I'm looking at don't mention this issue, so I'm wondering if this is safe.

Answer 1

Is the line next.head = orig.head->next; thread-safe?

If the line next.head = orig.head->next; resumes in thread 2 after free(orig.head); in thread 1, isn't that an error because we're referencing next after orig.head has been deallocated?

You have identified a bona fide flaw in the function. Good job.

It is indeed possible for two threads executing lfstack_pop() concurrently to load the same value into their respective orig locals. Although each thread's orig is local to that thread, both orig.head pointers point to the same object. In that case, if one thread proceeds through free()ing its orig.head before the other thread evaluates `orig.head->next then the second will reap undefined behavior on account of dereferencing an indeterminate pointer value. Nothing in particular prevents that.

Note well that the behavior is still undefined as far as the C language specification is concerned even in the event that in the interim, a new node is allocated at the address to which orig.head initially pointed. (This is the case in which the ABA problem arises that the code purports to solve.)