Stacked up (Hard Version)

This is the hard version of LockFreeStack. The only differences between this and the easy version are the memory reclamation strategy required and the type constraints on stored elements. Solving one problem does not guarantee solving the other.

Implement the class LockFreeStack, which is an unbounded lock-free multi-producer multi-consumer stack with safe memory reclamation.

Constructor

LockFreeStack()

• Constructs an empty stack.

Methods

push(value)

• Pushes value onto the top of the stack.
• This operation always succeeds (the stack is unbounded).
• Multiple threads may call push concurrently.

pop(out)

• Attempts to pop the top element and store it in out.
• Returns true if the pop succeeds.
• Returns false if the stack is empty at the operation's linearization point (no spurious failures).
• Multiple threads may call pop concurrently.

Notes

• The implementation must be lock-free (no std::mutex, no condition variables, etc.). Using a lock may result in a compilation error.
• Multiple producers and multiple consumers may call push/pop concurrently.
• You do not need to write any input/output parsing.
• Your submission will be tested with a multithreaded grader and heavy stress tests.
• Safe memory reclamation is required. A tagged-pointer scheme alone is not sufficient — it prevents ABA on the CAS but does not prevent a read-after-free on node->next between loading the head and completing the CAS. The grader will detect implementations that read freed memory.
  • Acceptable strategies include hazard pointers, epoch-based reclamation, or any other technique that provably defers node deletion until no thread can still be reading it.
  • You may not leak nodes indefinitely. The grader checks total memory usage after sustained operation.
• Type constraints (hard version):
  • The stored type T is not guaranteed to be default-constructible.
  • pop(out) must store the popped value into the existing out object via copy or move assignment, not by default-constructing a new one.
  • Slot/node lifetime must be managed with placement new and manual destruction as appropriate.
• We run strong stress tests to catch common concurrency bugs (duplicate pops, lost pushes, ABA-triggered corruption, use-after-free, leaks), but this does not prove the absence of all data races.
• You may assume the stack will not be destroyed during concurrent push or pop operations.
• The grader uses a node-reuse pattern with rapid pop-push cycles to actively trigger ABA and use-after-free in vulnerable implementations. A solution that "works in practice" but is theoretically vulnerable will fail.
• The grader runs on a less constrained environment than the easy version, so the additional overhead of safe reclamation will not cause spurious timeouts.
• The grader compiles your submission with AddressSanitizer (-fsanitize=address). Implementations with use-after-free, double-free, or memory leaks will be detected immediately, even if the bug is "benign in practice" on common platforms. A tagged-pointer-only solution (which leaves a read-after-free window between loading the head and reading node->next) will not pass — ASan catches the gap on the first concurrent test.