When thread 0 began its execution of pop, it saw that the current top element of the stack was A.
Then before thread 0 could remove A, thread 1 removed A, added D and added A again.
Now when thread 0 executes compare and swap, it sees that the top of the stack is still A. It assumes that this means the 2nd element in the stack is still B (even though it is now D!), so it sets stack->top to B.
This means D is removed from the stack as well.
This comment was marked helpful 6 times.
monster
Here the main idea is that when Thread 0 recognize A as the top of the stack, and know that the next top is B.
Thread 1 pop A, push some other things like D, then push A again.
Thread 0 still thinks it is valid in the compare-and-swap operation, therefore it pop two elements which makes stack corruption.
This comment was marked helpful 0 times.
markwongsk
I find this example a bit confusing. In the actual implementation top and new_top are both pointers, but this might not be so clear in this diagram.
In fact, correct me if I'm wrong, but the only time the above example can happen is if thread 1 had called free on A (the pointer) and the allocation of the new "A" pointer gives the same payload address as the just-freed pointer. An extension to that would be that the new pointer wouldn't even need to have "A" as its data, as long as the address of the pointer was that of the just-freed pointer. This is because the CAS signature is
int compare_and_swap (int* reg, int oldval, int newval)
and thus we are only checking for address equivalence (not data).
This comment was marked helpful 0 times.
kayvonf
@markwongsk: In this example, the labels A, B, C, etc. correspond to pointers to nodes. The example is that the node with address A is popped off the stack and maintained as a local variable in Thread 1. Later, thread 1 pushes this node back on the stack. The example is meant to be consistent with the code on the previous slide. As you state, the CAS operation is performed on these pointer values.
Not shown in the example, but another way to create the ABA problem is the case you state. Node A is popped and then deleted by T1. And then later a new node is allocated at the same address A and pushed onto the stack.
This comment was marked helpful 0 times.
markwongsk
@kayvonf okay that cleared things up. Just A,B,C are so generic variable names that I confused them for data values. I guess I should have just trusted typechecking and deduced that type(A) = (void *) given the top = A. Thanks!
This comment was marked helpful 0 times.
yingchal
More general and easy view of ABA problem: new pointer malloced happens to use the same memory location of removed old pointer, and some memory operations are taken between removing old pointer and malloc new pointer, which makes things bad.
When thread 0 began its execution of pop, it saw that the current top element of the stack was A. Then before thread 0 could remove A, thread 1 removed A, added D and added A again. Now when thread 0 executes compare and swap, it sees that the top of the stack is still A. It assumes that this means the 2nd element in the stack is still B (even though it is now D!), so it sets
stack->topto B. This means D is removed from the stack as well.This comment was marked helpful 6 times.
Here the main idea is that when Thread 0 recognize A as the top of the stack, and know that the next top is B. Thread 1 pop A, push some other things like D, then push A again. Thread 0 still thinks it is valid in the compare-and-swap operation, therefore it pop two elements which makes stack corruption.
This comment was marked helpful 0 times.
I find this example a bit confusing. In the actual implementation
topandnew_topare both pointers, but this might not be so clear in this diagram.In fact, correct me if I'm wrong, but the only time the above example can happen is if thread 1 had called free on A (the pointer) and the allocation of the new "A" pointer gives the same payload address as the just-freed pointer. An extension to that would be that the new pointer wouldn't even need to have "A" as its data, as long as the address of the pointer was that of the just-freed pointer. This is because the CAS signature is
int compare_and_swap (int* reg, int oldval, int newval)and thus we are only checking for address equivalence (not data).
This comment was marked helpful 0 times.
@markwongsk: In this example, the labels A, B, C, etc. correspond to pointers to nodes. The example is that the node with address A is popped off the stack and maintained as a local variable in Thread 1. Later, thread 1 pushes this node back on the stack. The example is meant to be consistent with the code on the previous slide. As you state, the CAS operation is performed on these pointer values.
Not shown in the example, but another way to create the ABA problem is the case you state. Node A is popped and then deleted by T1. And then later a new node is allocated at the same address A and pushed onto the stack.
This comment was marked helpful 0 times.
@kayvonf okay that cleared things up. Just A,B,C are so generic variable names that I confused them for data values. I guess I should have just trusted typechecking and deduced that type(A) = (void *) given the top = A. Thanks!
This comment was marked helpful 0 times.
More general and easy view of ABA problem: new pointer malloced happens to use the same memory location of removed old pointer, and some memory operations are taken between removing old pointer and malloc new pointer, which makes things bad.
This comment was marked helpful 0 times.