Writing Lock-Free Code: A Corrected Queue

General issues: "If you don't yet have ordered atomic variables yet on your language and platform, you can emulate them by using ordinary but aligned variables whose reads and writes are guaranteed to be naturally atomic, and enforce ordering by using either platform-specific ordered API calls (such as Win32's InterlockedCompareExchange for compare-and-swap) or platform-specific explicit memory fences/barriers (for example, Linux mb)."

This is incorrect. A lot of memory models in languages provide no such guarantees, even of aligned variables (this includes C, even with volatile variables). This not only applies to regular loads/stores but even to RMW.

Produce/Consume function: We store to last->next and then to last. If we assume total store ordering, insertion itself is fine. However, it should be made clear that an explicit store fence is needed after updating the next pointer. The article gives the impression (due to statement above) that this algorithm is suitable for other languages.

In the consumer, we also need an explicit load fence. If the atomic is completely serializing, we are fine but in other languages even with aligned variables, these semantics are incorrect.

The "trim" functionality is broken as it makes no use of safe memory reclamation. It is fine to re-use nodes (assuming you don't have a concurrent lock-free traversal going on) but you need to be careful with destruction. Assume consumer is at some time T where divider != last (but divider = first). Let us say consumer is at result = divider->next->value. Pause execution of consumer after it has acquired divider->next. Producer enqueues another node and sees that first != divider (yet consumer has an earlier snapshot of divider), so it trims first. Consumer is now active again and dereferences the earlier snapshot it had of divider->next to get to value, but now this yields undefined behavior (crash or worse).