Previous | Next --- Slide 21 of 31
Back to Lecture Thumbnails
kayvonf

Question: What is the bug in this lock-free stack implementation?

dsaksena

The bug is that we assume that when we pop, the only element in stack that must remain same is the stack_top.

Before thread 0s cmp_and_swap completes and after I assign old_top and new_top, kernel could context switch and thread 1 could pop out the stack do whatever it wants with the rest of my stack and put the old_top back as it is and boom, new_top is god knows where.

Specifically as shown in slide 22 also, after popping old_top(A) could push a new element(D) and push back the old_top (A) and thread 0 cmp_and_swap succeeds and pops out old_top but skips the element thread 1 had pushed (D) and top becomes the 2nd element in the stack(B).

step 1:thread 0 sees, assigns local variable new_top = B


A <-Stack top


B


/////Context switch to thread 1 before cmp_and_swap of thread 0 pop//////

step 2:thread 1 sees and pops A


B <-Stack top


step 3:thread 1 pushes D then pushes back A


A <-Stack top


D


B


/////Context switch to thread 0//////

step 4:cmp_and_swap succeeds and pop A stack_top is B now


B <-Stack top


rojo

This lock free implementation does not take into account the change in the stack below the current top of the stack. This description is similar to slide 22.

It can happen if the stack below the current top (say A) changes. Eg: If the initial state is A->B->C and thread 1 pops the top which is A. If the thread 1 is context switched before compare and swap and another thread (thread 2) modifies the stack to A->D->B->C. If thread 1 runs again it checks the old top from memory (which is A) and sets the new top to the local value of B. This results in a list B->C. In this case D is lost and this implementation is hence not correct.

rflood

I think the main issue here, as put by @rojo is that it does not consider a change in the stack

Specifically, the new top uses stale data as the next pointer for the lock.

If there were `compare_two_and_swap(orig_1,expected_1,orig_2,expected_2,new) we could compare the node and pointer at the same time.

We could also define some custom comparison which looked not at nodes addresses, but their address and next (this would not be supportable in compare_and_swap though)

solovoy

Try to make it even concise: same value of s->top and old_top in compare_and_swap can't ensure the stack hasn't changed.