#Freestack exercise code#
That does not necessarily mean that the boost lock-free queue is also incorrect, but I don't know the code good enough to make a qualified statement about the boost implementation.įWIW - this is usually referred as the memory reclamation problem.
#Freestack exercise free#
If the free list would have been implemented as you described, i.e., the popped nodes would be added to some freelist ( unaltered, i.e., the freelist uses a different pointer than next) and only released once the stack is no longer used by any thread, then next could be a plain variable since it would not be change once the node has been pushed successfully. One strategy is to simply move them to a per-stack LIFO freelist until eventually all threads are done with the stack, at which point a single thread destroys all nodes in the stack and all nodes in the freelist.īut that is not how the freelist in Wellson's implementation works! Instead it tries to reuse nodes from the freelist, but then next also needs to be atomic as you observed correctly. This seems simple until we have to think about what to do with nodes after they've been popped. The important point here is what you mentioned at the very beginning of your question: I just wrote a long text trying to explain why there cannot be a race, until I took a closer look at how Wellson implemented the free list, and I came to the conclusion that you are correct! So I must have made a mistake in my reasoning. But I don't think the Boost implementation could be wrong in such a basic way without it having been noticed and fixed by now. If his implementation is wrong, then so is the Boost one, because the only way to fix (what appears to me to be) the race condition is to make next atomic. This races with the read to orig.node->next in thread 1.Ĭould Wellons's implementation simply be wrong? I doubt it. The freelist head node is atomically loaded, and node->next is set to point to the first node in the freelist. It then begins to call push in order to add node to the freelist. pop succeeds and returns node, a pointer to the node that has just been excised from the stack this is the same node that orig.node points to in thread 1. (Note that up until this point, only local variables have been modified, so it is impossible for anything that thread 1 has done so far to make a CAS fail in any other thread.) Meanwhile. Now, orig.node is a pointer to the node that was at the top of the stack just now. It atomically loads the head node's value into the local variable orig.
What I am unable to understand is: why is it that such accesses never race with each other? In particular, this means that all accesses to the next member of an lstack_node object are non-atomic. In Wellons's implementation, which can be found on GitHub here, all lstack_node objects are non-atomic. I will refer to the latter, because it's easier to read and the details are essentially the same, since C11 atomics are very similar to C++11 atomics. So does Chris Wellons's C11 implementation. One strategy is to simply move them to a per-stack LIFO freelist (from which nodes can be reused by subsequent push operations) until eventually all threads are done with the stack, at which point a single thread destroys all nodes in the stack and all nodes in the freelist. A lock-free stack can be implemented as a singly linked list.
0 kommentar(er)
