the head pointer came back

The compare-and-swap succeeded. Every node it had observed had already left the queue.

delayed read       head=D address=0x16f2c1ca0 generation=1 in-queue=1
delayed successor=A address=0x16f2c1c70

fast dequeue       head=A address=0x16f2c1c70 generation=1 in-queue=1
fast dequeue       head=B address=0x16f2c1c40 generation=1 in-queue=1

reused-node=D address=0x16f2c1ca0 generation=2 value=30
fast dequeue       head=D address=0x16f2c1ca0 generation=2 in-queue=1

stale-cas=1
expected-address=0x16f2c1ca0
observed-generation=1
current-generation=2
installed=A
installed-in-queue=0

The delayed operation read head pointer D, then stopped. Another operation removed D. The storage pool reused that exact address for a later node. Enough queue operations ran for the head pointer to contain D again.

The delayed operation compared only the address. Expected D, found D, exchanged it for the successor it had remembered. That successor was node A, which had also been removed. The atomic operation behaved exactly as requested and corrupted the queue.

The earlier address investigation ended with a warning that equality cannot distinguish an object from a later object at the same location. This queue made the consequence executable.

The deterministic probe ran on an Apple M4 with macOS 15.7.7, Apple clang 15.0.0, and eight-byte pointers. It keeps three Node objects alive for the complete schedule so the first failure is logical rather than accidental C++ use after free. in-queue and generation expose state that the pointer bits omit.

the first node contained no value

The queue begins as a singly linked list:

head
  |
  v
  D ------> A ------> B ------> null
                         ^
                         |
                        tail

A contains 10. B contains 20. D is a dummy node.

The dummy makes an empty queue representable without a special disconnected state:

head
  |
  v
  D
  ^
  |
 tail

Head and tail both point to the same node, and its next pointer is null. There is always a node at the front even when there is no value to return.

To remove 10, a dequeue does not make head null. It reads D->next, obtains A, and changes head from D to A. The value comes from A. The old dummy D is no longer in the list. A becomes the new dummy:

head
  |
  v
  A ------> B ------> null
             ^
             |
            tail

The node that supplied this dequeue’s value remains in the queue structure as the dummy until the next successful dequeue. This one-node delay is what lets enqueue and dequeue avoid editing the same end in the ordinary case.

After removing 20, B becomes the dummy and the queue is empty:

head, tail
     |
     v
     B ------> null

The original 1996 Michael and Scott non-blocking queue paper uses this head, tail, dummy shape. Its pseudocode also uses modification counters with pointers. The first probe deliberately removed those counters so the returned address could become visible.

three arguments decided the stale exchange

Compare-and-swap operates on one shared atomic object. It receives:

the atomic location to change
the value expected there
the desired replacement

In C++ the expected value is an input and an output:

Node* expected = delayed_head;
bool changed = head.compare_exchange_strong(
    expected, delayed_next);

If head equals expected, the operation writes delayed_next into head and returns true. If they differ, it leaves head unchanged, writes the value it actually found into expected, and returns false.

The current draft’s compare_exchange wording also permits a weak compare-and-exchange to fail spuriously. That is why weak operations normally appear inside retry loops. A strong operation avoids that permitted false failure when one attempt is the intended action.

Neither form asks how the value reached its present state. The comparison has no history:

delayed read:       head = address D
intervening state:  head = address A
intervening state:  head = address B
current state:      head = address D
comparison:         D == D

The operation compares pointer representations. It does not know that the first D meant generation 1 and the second meant generation 2.

This shape is called ABA. A thread observes A. Other threads change the location to B and later back to A. The equality test accepts A even though the state transition through B mattered.

The counter experiment in two threads to a task runtime did not expose this. If an integer counter changes from 10 to 11 and back to 10, a delayed operation that only requires the current count to be 10 may still be correct. For a pointer into a changing ownership graph, the intervening removal can end a lifetime, change links, and transfer storage to another object.

Atomicity protects the comparison and replacement from being torn apart. It does not make the expected value a complete description of the state.

a failed weak exchange rewrote the local expected value

The expected argument is passed by reference:

bool compare_exchange_weak(
    T& expected,
    T desired,
    memory_order success,
    memory_order failure);

On failure, C++ stores the atomic value it observed into expected. A retry loop can use that new value:

Node* expected = nullptr;

while (!predecessor->next.compare_exchange_weak(
    expected,
    pending,
    std::memory_order_release,
    std::memory_order_relaxed)) {
    // expected now contains the value that prevented this exchange
}

That exact loop would be wrong for queue enqueue. Once expected becomes a non-null successor, the operation must help tail or restart from a current tail. It must not retry with a non-null expected value and overwrite a link another enqueuer installed.

The queue therefore resets its logical attempt:

Node* expected = nullptr;
if (!tail->next.compare_exchange_weak(
        expected,
        pending,
        std::memory_order_release,
        std::memory_order_relaxed)) {
    retry_from_tail;
}

A weak exchange can also report failure when the comparison could have succeeded. The retry path must be correct both for real interference and for spurious failure.

A strong exchange is useful in the one-shot ABA probe because a false failure would hide the schedule being demonstrated. It does not add generation awareness. Strong still accepts generation-2 D when its expected bits contain the same pointer as generation-1 D.

Success and failure memory orders describe different actions. A successful compare-and-exchange is a read-modify-write. A failed one only reads the atomic. C++ does not permit a failure order that releases, because no write occurred to publish prior work.

The enqueue link uses release on success and relaxed on failure. A failed attempt does not dereference the value read back through expected; the algorithm restarts and protects a current tail. The successful release publishes construction of the pending node.

Head changes use sequential consistency in the local hazard implementation. That is stronger than the queue’s value publication alone requires because head changes also participate in the reclamation order.

The memory-order arguments are part of the algorithm. Replacing them with relaxed everywhere because pointer loads are atomic would preserve indivisibility while losing required visibility and protection ordering.

four completed operations rebuilt the old address

The deterministic schedule starts when the delayed dequeue records:

delayed_head = D, generation 1
delayed_next = A

It has not changed shared state yet.

The fast participant completes the first dequeue:

head: D -> A
returned value: 10
removed dummy: D

It completes a second:

head: A -> B
returned value: 20
removed dummy: A

The queue is empty at B. The pool now reuses the storage slot named D:

same numerical address
generation: 1 -> 2
new value: 30
next: null

Enqueue links this new D after B:

head
  |
  v
  B ------> D ------> null
             ^
             |
            tail

The fast participant dequeues 30. Head advances from B to the new D. The queue is empty again, and head has returned to the bits saved by the delayed participant:

head, tail
     |
     v
  D generation 2

The delayed compare-and-swap expects the address of D and requests A. It succeeds:

head
  |
  v
  A, already removed

No overlap had to be left to chance. The probe executes the logical actions in this order and asserts that the stale exchange succeeds.

The failure does not require pointer-sized writes to tear, a cache to return old bytes, or the compiler to reorder the source. Every individual atomic operation is correct. The snapshot carried too little identity.

one counter made the same comparison fail

I packed a node index and generation into one 64-bit atomic value:

low 32 bits:  node index
high 32 bits: generation

The delayed expected value became:

node D, generation 1

The current head became:

node D, generation 2

The control printed:

tagged-cas=0
expected-generation=1
actual-generation=2
atomic-u64-lock-free=1

The failed exchange also replaced the expected argument with the current tagged value, so the caller learned that generation 2 was present.

On this machine std::atomic<std::uint64_t> reports both compile-time and runtime lock-free support. The probe also found:

cplusplus=202002 pointer-bytes=8
atomic-pointer always-lock-free=1 runtime-lock-free=1 required-alignment=8
atomic-u64 always-lock-free=1 runtime-lock-free=1 required-alignment=8
standard-hazard-pointer-header=0

The working draft now contains safe-reclamation and hazard-pointer facilities. The installed C++20 libc++ 17.0.6 does not provide that header, so the later implementation uses a small local hazard domain and states its limits.

A tag moves the ambiguity from pointer reuse to counter wrap. A 32-bit generation repeats after 2^32 changes to the relevant packed location. Whether that is practically unreachable depends on mutation rate and system lifetime. It is not a mathematical proof for an indefinitely running structure.

A pointer plus a full 64-bit generation would need more than 64 bits on this platform. An atomic object large enough to hold both is not automatically lock-free. Some machines offer a double-width compare-and-swap. Some encodings rely on unused address bits or array indices. Every choice needs an alignment, address-range, wrap, and hardware-support argument.

The tag control fixes the opening comparison. It does not answer when removed node memory may be deleted. A thread can hold a pointer and dereference it before reaching its tagged compare. Preventing an incorrect exchange and preventing use after free are related but separate obligations.

not reusing anything also removed ABA

The second control stopped before reusing D. Head remained B. The delayed expected pointer was D:

no-reuse-cas=0 observed-head=B

Keeping every removed node forever prevents an old address from returning. It also prevents the process from recovering queue memory.

That is a useful construction step. First make the concurrent list correct while removed nodes remain allocated. Then add reclamation without changing which histories the queue permits.

It is not a deployable answer for an unbounded service. If the queue transfers one million nodes per second and never reclaims them, memory consumption grows with total historical traffic rather than current queue length. A queue that is usually empty can still exhaust the process.

The desired rule is narrower:

reuse a removed node only after no thread can still dereference it

Finding that moment is the reclamation problem.

deleting the old dummy was already too early

I made the lifetime failure independent of ABA. One thread loaded the current head and paused. Another thread advanced head and immediately deleted the old node. The first thread then read the remembered node’s next field.

AddressSanitizer stopped it:

delayed-loaded=0x1030006f0
ERROR: AddressSanitizer: heap-use-after-free
READ of size 8 at 0x0001030006f0

The atomic head load was valid when it occurred. The pointer became unsafe before the next dereference.

This sequence cannot be repaired by changing only next to an atomic:

struct Node {
    std::atomic<Node*> next;
    int value;
};

An atomic member controls concurrent access while its object exists. It does not keep the containing Node alive. Calling load on an atomic member through a pointer to freed storage is still use after free.

Reference counting looks tempting:

load pointer
increment node reference count
read node
decrement reference count

The increment itself requires a live node. Another thread can delete the node between loading the pointer and incrementing its internal count. An external atomic shared owner can close that acquisition gap, but it changes the representation and may not be lock-free.

The reader needs a way to announce the pointer before the remover decides whether deletion is safe, then verify that the pointer still came from the shared location.

the announcement had to be followed by another read

A hazard pointer is a published non-owning pointer. One thread writes its own hazard slot. Reclaiming threads read every slot.

Protection follows this loop:

Node* candidate = source.load();

for (;;) {
    my_hazard.store(candidate);
    Node* observed = source.load();

    if (observed == candidate) {
        return candidate;
    }
    candidate = observed;
}

The first load alone is not protected. The hazard publication alone is not enough either. The second source load closes the race.

Consider removal before publication:

reader loads D
remover changes head from D to A
reader publishes D
reader reloads head and sees A
reader clears or replaces D without dereferencing it

If the remover scans before the publication, it can delete D. The reader’s validation sees that head changed and must not dereference the old candidate.

Consider publication before removal:

reader loads D
reader publishes D
reader reloads head and still sees D
remover changes head from D to A
remover scans hazards and finds D
remover retains D
reader safely dereferences D

Either the reader detects that the source changed, or the remover detects the hazard. The ordering rules must make that either-or argument true in the C++ abstract machine, not only in a diagram.

The current draft’s hazard pointer clause expresses the same protect shape through try_protect: associate a hazard with the candidate, load the source with acquire semantics, and end the protection if the value changed. It separates retirement from reclamation and requires an object to be retired at most once.

Maged Michael’s hazard-pointer paper develops the method as safe reclamation for lock-free objects and also connects delayed reuse to ABA prevention. The local implementation follows the publication, validation, retirement, and scan shape. It is not a drop-in reproduction of the paper’s performance claims.

The local implementation uses sequentially consistent publication, source validation, head changes, and hazard scans. That is stronger than every edge needs. It gives the first version one total order for the critical proof. Relaxing those operations belongs after the queue and reclaimer pass their adversarial schedules.

one dequeue needed two announcements

A dequeue touches two nodes:

head node: the current dummy
next node: the node containing the value

Protecting only head is insufficient. After the operation advances head to next, another dequeue can advance again and retire next while the first operation is still reading its value.

The implementation assigns two hazard slots to every participant:

slot 0 protects head
slot 1 protects head->next

The path is:

Node* head = protect(participant, 0, head_);
Node* next = head->next.load(std::memory_order_acquire);

if (head != head_.load()) {
    retry;
}

Node* protected_next =
    protect(participant, 1, head->next);

if (protected_next != next || head != head_.load()) {
    retry;
}

Head protection makes reading head->next safe. Next protection keeps the value node alive through the head exchange and value movement.

The queue restricts T to nothrow move construction and nothrow destruction. Head changes are the dequeue’s visible effect. If moving the returned value threw after that atomic change, the item would already be removed with no value delivered to the caller. A broader generic interface needs a different value-transfer design and exception contract.

The restriction is part of correctness, not an inconvenience hidden in a template error.

tail was allowed to be one node behind

Enqueue creates a node whose value is complete and whose next pointer is null:

std::unique_ptr<Node> pending(
    new Node(std::forward<U>(item)));

The unique pointer owns the unpublished node. If construction throws, no shared pointer can see it. If a compare-and-swap attempt fails, the same pending node can be retried. Ownership leaves the unique pointer only after the node is linked.

The loop protects tail, then reads the successor:

Node* tail = protect(participant, 0, tail_);
Node* next = tail->next.load(std::memory_order_acquire);

if (tail != tail_.load()) {
    continue;
}

When next is null, tail names the final node. Enqueue tries to publish the pending node there:

Node* expected = nullptr;
if (tail->next.compare_exchange_weak(
        expected,
        pending.get(),
        std::memory_order_release,
        std::memory_order_relaxed)) {
    Node* inserted = pending.release();
    tail_.compare_exchange_strong(tail, inserted);
    return;
}

The successful next exchange is the enqueue linearization point. Before it, no dequeue can reach the new node from head. After it, the value belongs to the queue even if the enqueuing thread stops before changing tail_.

Release publication on the link and acquire reading of the link make construction of the value visible to a consumer that reaches the node. The head and hazard operations remain sequentially consistent in this version because their reclamation proof uses one total order.

The tail update is an optimization. It points future enqueues closer to the actual end. That update can fail because another thread already advanced tail. The item is still enqueued.

This produces a deliberate intermediate state:

head, tail
     |
     v
  D ------> N ------> null

Tail is one node behind. A thread that observes non-null tail->next does not wait for the original enqueuer. It attempts to advance tail itself:

tail_.compare_exchange_weak(tail, next);

Helping turns another thread’s incomplete housekeeping into progress. It is essential to the queue’s liveness argument.

the consumer finished the paused producer’s update

I inserted a test hook immediately after the successful link and before the tail update. The producer published value 42, set a flag, and waited.

A consumer began while the producer remained paused. It saw:

head == tail
head->next != null

The queue was not empty. Tail was behind. The consumer advanced tail and retried, then advanced head and returned 42.

The output:

stalled-enqueuer observed=42
tail-helps=1
producer-returned-after-consumer=1

The consumer thread joined before the test released the producer. One delayed participant did not prevent another operation from completing.

A mutex queue has a different failure shape. If a producer pauses while holding the queue mutex, every consumer that needs the mutex waits. It does not matter that the paused producer used no CPU. Ownership of the lock is the dependency.

The lock-free queue has shared atomic locations and retry loops instead. It can still suffer contention, starvation of one participant, scheduler delay, page faults, and allocator stalls. The demonstrated property is narrower: this pause after link did not require the original producer to run before the consumer could complete.

The test also fixes the meaning of enqueue completion. The producer had not returned, but its operation had already taken effect at the link. Concurrent operations can linearize before their source-level functions return.

the linked node could not be half constructed

Node::value is not atomic. That is intentional. Only the producer writes it before publication, and only the winning consumer moves from it after publication. This is safe only if those ordinary accesses have a happens-before path between them.

The producer performs these actions in source order:

construct pending->value
initialize pending->next to null
release compare-and-exchange on predecessor->next

The consumer reaches the node through:

acquire load of predecessor->next
read or move pending->value

When the acquire load reads the pointer written by the release exchange, the release synchronizes with the acquire. Everything sequenced before publication, including construction of the optional value, happens before the consumer’s later ordinary read.

This is not a promise that release immediately flushes a complete cache line to DRAM. It is a language relation. The compiler and target instructions must preserve the visibility required by that relation.

Changing the successful link exchange to relaxed would leave the pointer indivisible:

predecessor->next.compare_exchange_weak(
    expected,
    pending,
    std::memory_order_relaxed,
    std::memory_order_relaxed);

Another thread could observe the new pointer without acquiring the preceding ordinary writes. Reading value would then lack the required inter-thread ordering. The source may appear to initialize value first, but source order inside the producer does not by itself order a different thread.

The first consumer might advance head before a later consumer arrives. The publication chain still has to reach that later consumer:

producer constructs N
producer release-publishes N through old_head->next
consumer 1 acquire-loads that link
consumer 1 changes shared head to N with a sequentially consistent exchange
consumer 2 sequentially consistently loads head as N
consumer 2 reads N->next

The sequentially consistent head exchange has release behavior, and the later sequentially consistent load has acquire behavior when it observes that value. Happens-before is transitive. Construction reaches later operations even after the node has become the dummy.

The next member is atomic for a different reason. An enqueuer can install a successor while dequeuers and helpers read the link. Those accesses overlap in time, so an ordinary pointer member would have a data race. Before a node is published, its next field has one owner. After publication, it is shared atomic state.

Clearing a consumed optional<T> happens after the winning head exchange. No other dequeuer can win that same exchange. The next successful dequeue treats this node as the old dummy and does not read its empty value. A scanner can delete it only after the winner’s hazard and every later hazard have cleared.

These are three separate orders:

value construction before link publication
one winning head exchange before value movement
last possible dereference before reclamation

One atomic<Node*> cannot establish all three merely by existing.

dequeue took effect before it moved the value

Once head and next are protected and consistent, dequeue examines tail.

If head == tail and next == nullptr, the queue is empty. No shared pointer changes.

If head == tail and next != nullptr, tail is behind. Dequeue helps tail and retries.

Otherwise it tries:

if (!head_.compare_exchange_weak(head, next)) {
    retry;
}

The successful head exchange is the dequeue linearization point. One contender changes head from the old dummy to the value node. Every other contender using the old head fails and must reload.

Only the winner moves the value:

T result = std::move(*next->value);
next->value.reset();

next remains protected by the winner’s second hazard slot. Another dequeue can make next an old dummy and retire it, but scanning must find the hazard and delay deletion.

The original Michael and Scott pseudocode copies the value before the head compare-and-swap because another dequeuer might free the next node after the exchange. Hazard protection changes that lifetime boundary. Moving only after winning avoids several contenders reading and modifying the same non-const value.

After taking the value, the winner clears protection of the old head, retires it, then clears protection of the new dummy:

clear_hazard(participant, 0);
retire(participant, old_head);
clear_hazard(participant, 1);

Retire does not mean delete. It means the node is unreachable from the queue and may become reclaimable after every hazard is inspected.

one atomic instant made a concurrent history ordinary

A sequential FIFO history has an obvious order:

enqueue 10
enqueue 20
dequeue -> 10
dequeue -> 20
dequeue -> empty

Concurrent calls overlap. Source start time alone cannot order them, and return time alone cannot order them.

Linearizability asks whether each completed operation can be placed at one instant between its invocation and response so that:

the resulting sequential order obeys the object specification
and
real-time order is preserved when calls do not overlap

If operation A returns before operation B begins, A must appear first. If their intervals overlap, either order may be legal if the returned values agree.

For this queue:

enqueue linearizes when predecessor->next changes from null
dequeue linearizes when head changes to next
empty dequeue linearizes at a consistent empty observation

Tail helping does not enqueue or dequeue a value. It repairs an optimization pointer.

The paper’s correctness section identifies the same enqueue and dequeue points. It also states list invariants:

the list remains connected
nodes enter only at the end
nodes leave only at the beginning
head names the first node
tail names a node still in the list

The local implementation adds another invariant:

a node is deleted only after it is retired
and absent from every hazard slot

FIFO safety and lifetime safety meet at the same nodes but require different arguments.

fifty histories each needed an independent ordering

The 100,000-item test checks bulk uniqueness and loss. It can miss a queue that returns every value once but violates real-time order in a rare interleaving.

I generated 50 smaller concurrent histories. Four threads each performed three fixed enqueue or dequeue calls. Every call recorded:

thread
operation kind
enqueued argument or dequeue result
invocation counter
response counter

An independent Python checker did not call queue code. For each history it built the real-time predecessor relation:

A must precede B when A.end < B.start

It then searched legal placements. An enqueue appends its argument to a model deque. A successful dequeue is legal only if its recorded result equals the model front. An empty result is legal only when the model is empty at that candidate instant.

The search memoized:

set of already placed operations
current model queue contents

The verifier produced 600 recorded calls:

linearizable histories=50
total-search-states=692
max-search-states=34

The state count changes with the observed schedules because different overlaps create different candidate orders. Every current history had at least one legal witness.

This is an attempt to falsify linearizability, not a proof over all executions. The checker can contain a bug. The generator covers twelve-operation histories, four threads, integers, and one machine’s schedules. A formal proof or model checker can quantify over states the run never reached.

The test still adds a different kind of evidence from a checksum. It rejects histories whose outputs cannot be explained by any legal FIFO order even when no value is duplicated.

an empty return could move between two overlapping calls

Consider one recorded shape:

operation A: dequeue begins ---------------- returns empty
operation B:              enqueue 10 begins -------- returns
operation C:                                      dequeue 10

A and B overlap. Either can linearize first.

The observed empty result requires A before B:

A: queue empty, return empty
B: append 10
C: remove 10

Placing B before A would make A’s empty result illegal. The checker discovers the first ordering and rejects the second.

Now change the intervals:

operation B: enqueue 10 returns
operation A:                    dequeue begins, returns empty

The calls do not overlap. Real-time order requires B before A. No legal FIFO state lets A return empty unless some other recorded dequeue removed 10 between them. The checker cannot simply reorder A earlier to explain the result.

This is the part a final checksum misses. Both histories can contain one enqueue and one later successful dequeue with the same total values, while an intervening impossible empty result exposes the bug.

The predecessor mask is built from strict interval separation:

if left.end < right.start:
    predecessors[right] |= 1 << left_index

For overlapping operations, the search tries both orders when queue semantics permit them.

At each candidate dequeue:

if operation.empty:
    candidate is legal only when model_queue is empty
else:
    candidate is legal only when model_queue.front == result

The checker does not use internal head or tail events. That independence is useful because it judges the public object behavior rather than repeating the implementation’s claimed linearization points.

Its timestamps are logical counters around source calls, not nanosecond clocks. Only relative invocation and response ordering matters. This avoids clock resolution and cross-core clock questions.

The generator cleans any values left after a round before starting the next history. Cleanup operations are outside the recorded interval set. The checker permits a history to end with queued values because linearizability does not require every enqueue to be consumed.

One risk remains: recording itself changes scheduling. Atomic timestamp increments add shared contention around every call. The checker validates the histories that instrumentation produced, not the schedules an uninstrumented queue would have produced.

one hundred thousand values appeared exactly once

Four producers each enqueued 25,000 unique integers. Four consumers removed values until the total reached 100,000. An atomic array counted how often every ID appeared.

One AddressSanitizer and UndefinedBehaviorSanitizer run reported:

mpmc produced=100000 consumed=100000
duplicates=0 missing=0
checksum=4999950000
enqueue-retries=54814
dequeue-retries=173275
tail-helps=34040
scans=1570
retained=0

The expected checksum is:

100000 * 99999 / 2 = 4,999,950,000

The checksum alone could allow one missing value and another duplicated value to cancel. The per-ID counters close that hole for this input range.

The retry and help counts are schedule-dependent. A ThreadSanitizer run of the same program had:

enqueue-retries=127384
dequeue-retries=194255
tail-helps=63067
scans=1580

Instrumentation changes timing enough to change contention. Both runs returned every value exactly once and left no retired nodes.

ThreadSanitizer reported no data race in the current run. Its documentation describes compiler instrumentation and its own runtime limits. A clean report means no instrumented race was observed on these executions. It does not prove the memory-order argument or make an untested path safe.

AddressSanitizer answered the lifetime side. UndefinedBehaviorSanitizer checked instrumented undefined operations. The offline history checker answered the FIFO side. None substitutes for the others.

the retries were evidence that someone else moved

One thread can fail a weak compare-and-swap spuriously. Repeated queue retries also happen when another thread changes a shared pointer between observation and exchange.

For enqueue, a failed link exchange means another enqueuer can have linked a node at that predecessor. A changed tail means another participant advanced it.

For dequeue, a changed head means another dequeue completed. A lagging tail causes helping rather than waiting.

This supports the lock-free progress argument for the pointer-manipulation core:

if my head exchange repeatedly loses, other dequeues repeatedly win
if my link exchange repeatedly loses, other enqueues repeatedly win
if tail repeatedly changes, some participant keeps advancing shared state

System-wide progress does not imply per-thread progress. One unlucky participant can lose every exchange while others complete. That is starvation.

A wait-free operation would give every participating call a finite bound on its own steps, independent of interference. These retry loops do not. The queue core is not wait-free.

An obstruction-free operation completes when it eventually runs without interference. The C++ draft’s forward progress section uses the related terms when discussing lock-free atomic executions. It distinguishes progress when one nonblocked thread runs from the recommendation that at least one of several concurrent lock-free executions complete.

Algorithm papers and language specifications do not always use every progress term identically. The useful discipline is to state the quantified subject:

this call completes
some active call completes
the data structure remains usable if one participant stops
the atomic instruction itself uses no hidden lock

Those are different claims.

the list proof had five moving edges

The history checker tries executions. The structural argument has to cover executions the scheduler did not produce.

Start with the empty representation:

head == tail
head->next == null

There is one allocated dummy, and following next from head reaches tail. Assume before an operation that:

following next from head reaches null without a cycle
tail names some node on that path
only the final node can have a null successor
every non-dummy reachable node owns one unconsumed value
every node before head is unreachable and retired or awaiting retirement

An enqueue allocates a node with null successor. It only attempts to change a null successor of a protected node that it has validated as the current tail. A successful link therefore adds one new final edge:

old final node -> pending node
pending node -> null

No other enqueuer can successfully replace the same null with a different node. Compare-and-exchange permits one winner. Losers reload instead of overwriting the installed edge.

Tail can still name the old final node. Advancing it along an observed next edge preserves the claim that tail names a reachable node. A helper never invents a target and never moves tail backward through the list.

A dequeue reads the successor of protected head. If there is none at a validated observation, returning empty preserves every edge. If there is a successor, a successful head exchange removes exactly the first edge from the reachable prefix:

old head -> next

becomes

head == next

The old head becomes unreachable from the shared head. No operation writes head to an arbitrary remembered node in the protected implementation. It can only change from a currently validated head to that head’s currently protected successor.

This last restriction is exactly what the opening ABA exchange violated. Its desired pointer A had once been D->next, but it was no longer the successor belonging to the current generation of D. Address equality allowed an old edge to masquerade as a current edge.

The hazard protocol prevents reclaiming the source nodes while these observations are checked. It does not establish the list invariants by itself. A queue could protect every pointer perfectly and still link a node twice, create a cycle, return the wrong value, or move tail to an unreachable node.

The value argument follows the edge argument. A successful enqueue link contributes one value. A successful dequeue head exchange consumes the value in its new dummy. Since only one exchange can change a particular head value, only one consumer moves that value. Nodes enter at the final edge and head advances along the first edge, so successful dequeues preserve FIFO order.

This induction assumes node storage is not placed back into a producer’s pool until reclamation permits reuse. Otherwise a write through the pool can change next while the old logical node remains part of the proof.

every infinite retry needed infinitely many winners

The system-wide progress argument can be checked branch by branch.

An enqueuer restarts after protecting tail when:

tail no longer equals the shared tail

Shared tail changes only when some participant advances it toward a linked successor. A single enqueue can leave it one node behind. Repeated changes require repeated link progress or helping progress.

An enqueuer fails the tail->next exchange when:

the link is no longer null
or
the weak exchange fails spuriously

If the link is non-null, another enqueuer published a node. One enqueue linearized.

Spurious failure needs a platform forward-progress assumption about the lock-free atomic operation. The C++ draft recommends that at least one of concurrent lock-free executions complete under expected conditions. It does not promise that one selected thread eventually wins.

A dequeuer restarts when protected head is no longer current. Head changes only at a successful dequeue linearization point.

It restarts after head == tail with non-null next because it helps tail. If this state recurs indefinitely, enqueues keep linking nodes or other helpers keep changing tail.

It fails the head exchange when another participant changed head or the weak atomic failed spuriously. A real changed head means another dequeue completed.

Now freeze one participant at each point:

before publishing a pending node:
    no shared queue state changed

after linking but before tail update:
    other participants can help tail

after protecting head but before head exchange:
    hazards retain nodes, other dequeuers can change head

after head exchange but before retirement:
    the value node is protected, but the removed dummy has not entered
    reclamation metadata

during a retired-list scan:
    other participants operate on their own lists and queue atomics

The after-head-exchange pause exposes an implementation boundary. The current thread already removed an item but has not returned it or retired the old dummy. Other queue operations can continue. The stalled call itself remains incomplete, and one node may remain outside reclamation tracking until it resumes.

If the process terminates that thread permanently at this source point, C++ does not run arbitrary stack cleanup. The returned value and old dummy can leak. Lock-free progress does not imply recoverability from killing a thread in the middle of a language operation.

A mutex pause before acquiring the lock delays only that caller. A pause after acquiring delays every caller that needs the lock. Lock-free design shifts the dangerous pause points but does not remove all partial operation state.

This branch audit is more useful than spotting a compare-and-swap and declaring the function lock-free.

a lock-free atomic could still hide a different implementation elsewhere

The feature probe printed:

atomic-pointer always-lock-free=1 runtime-lock-free=1
atomic-u64 always-lock-free=1 runtime-lock-free=1

is_always_lock_free is a property of that atomic specialization across executions of this implementation. is_lock_free() checks the current object.

A larger atomic representation can return false. The library may then use an internal lock. An algorithm built from that object loses the progress property expected from one-word compare-and-swap even if the source contains no std::mutex.

Alignment can affect which hardware instruction is possible. Constructing an atomic_ref over inadequately aligned storage violates its precondition. Packing an atomic into a wire or file structure can therefore change correctness before performance is measured.

Even when pointer atomics are lock-free, the queue calls library operations that are not:

operator new
operator delete
thread creation and join in the harness
yield after an empty poll
I/O used for diagnostics

The term must attach to a delimited operation path and target. “This class is lock-free” is too broad when construction, registration, value construction, or destruction can take another path.

new and delete remained outside the proof

The measured queue’s public enqueue starts with:

new Node(value)

The language does not promise that general allocation is lock-free. The allocator may use locks, ask the operating system for pages, run out of memory, or spend an unbounded interval in implementation work.

Reclamation eventually calls:

delete node;

That path has the same limitation.

Participant registration uses a fixed atomic claimed bit in this implementation, so it does not allocate. The retired list is a fixed array of 4,096 pointers per participant, so appending does not grow a vector. If a scan cannot create space before the fixed array fills, the implementation terminates rather than silently overflow metadata.

These choices let the retry and hazard mechanics remain bounded enough to inspect. They do not make the entire enqueue and dequeue API unconditionally lock-free because node allocation and deletion remain.

The precise claim is:

on this machine, the head, tail, hazard, and 64-bit tag atomics report
lock-free operation

the linked-queue pointer core has the Michael-Scott system-wide
progress argument

the measured end-to-end API includes general allocation and deletion,
whose progress is not promised here

A preallocated node source can remove general allocation from the hot path. It then needs its own concurrent free-node algorithm, exhaustion behavior, ABA defense, and reclamation integration. Calling a lock-free queue from a mutex-backed pool merely moves the blocking point.

The opening failure came from exactly such a free list. Allocation is not an implementation footnote for a dynamic lock-free structure. It participates in the proof.

the pool could reproduce the same failure one layer lower

A simple pool keeps unused slots in another singly linked list:

free_head -> slot 7 -> slot 3 -> slot 12 -> null

Allocation removes the first slot. Deallocation pushes a slot onto the front. It is tempting to implement both with a compare-and-exchange on free_head.

That free list has the same snapshot problem:

thread 1 reads free_head = slot 7 and next = slot 3
thread 2 removes slot 7
thread 2 removes slot 3
thread 2 pushes slot 7 back
thread 1 sees free_head = slot 7 and installs stale slot 3

The queue can have correct hazard protection while its allocator corrupts its own free list. A pool does not inherit the queue’s proof because both contain atomics and linked nodes.

The handoff order must be:

queue removes node from its reachable list
queue retires node
scanner proves no queue hazard protects node
node value and node lifetime end as required
storage is returned to the pool
pool may make storage available for a later node

Returning storage before the scan reverses the critical middle edge. A new node can be constructed at the same address while a delayed queue participant still reads the old node.

If the pool keeps Node objects permanently alive and merely resets fields, the language lifetime issue changes, but the logical generation issue remains. A delayed queue operation can still combine a current address with a successor read from an earlier use. The opening probe chose permanent objects precisely to isolate that logical corruption from use after free.

If the pool manages raw slots instead, placement construction begins a new Node lifetime:

Node* node = std::construct_at(slot, value);

Reclamation eventually ends it:

std::destroy_at(node);
pool.deallocate_slot(slot);

The old pointer value may compare equal to the new one. Lifetime boundaries do not insert a generation into pointer bits.

A generation-tagged pool head can reject the four-step free-list schedule until its tag wraps. Hazard-protecting the pool head can prevent the first slot from being reused while a pop is inspecting it. An epoch shared by queue and pool can delay reuse until every relevant participant leaves its old interval. These are allocator design choices, not flags applied to new.

Per-thread pools reduce shared free-list traffic when allocation and deallocation stay on the same thread. This queue transfers ownership across threads. A producer can allocate a node, and an unrelated consumer eventually retires it. Returning the slot to its original owner requires a remote-free path, while returning it locally changes which cache and memory domain own the slot.

NUMA adds another boundary. Reusing a node on the socket that freed it may make allocation cheap while placing a later producer’s writes in remote memory. Sending every slot home can add cross-socket synchronization. Neither outcome can be selected from the word “pool.”

The current benchmark uses general new and delete, so it measures none of these alternatives. I did not add a pooled timing result because the safe pool would be another concurrent data structure requiring its own failure schedules and reclamation tests. The claim here stays mechanical: reuse must occur after the queue’s last possible dereference, and the mechanism that stores reusable slots needs an independent ABA and progress argument.

a stalled thread blocked one deletion but not the queue

The forced reclamation test enqueued values 1 and 2. A delayed dequeue protected the old head and its successor, then paused before attempting the head exchange.

The active participant dequeued 1, retired the old dummy, and scanned. The scanner found that old dummy in the delayed thread’s hazard slot:

retained-while-paused=1

It did not delete the node.

The active participant then completed 2,000 enqueues and 2,000 dequeues while the delayed operation remained paused:

active-operations=4000

Newly retired nodes that were not protected could be reclaimed. One old dummy remained.

After release, the delayed compare-and-swap failed because head had changed. It protected the current head and successor, retried, and eventually returned the final remaining value:

delayed-value=2999
dequeue-retries=1

A scan after its hazard slots cleared produced:

retained-after-release=0

The stopped thread delayed reclamation of one node. It did not prevent other queue operations from completing.

This distinction matters operationally. Hazard pointers can preserve availability while memory retention grows because stalled or dead participants keep hazards published. A thread that never clears a slot can keep the corresponding node forever.

Progress needs two dashboards:

are queue operations completing?
are retired nodes becoming reclaimable?

High throughput can coexist with a reclamation leak.

retirement was a third state between live and deleted

The vector investigation had two important states:

object is live
object lifetime has ended

A concurrent queue needs a state between reachable and reclaimed:

linked:
    reachable from head and available to queue operations

retired:
    no longer reachable as a queue node, but some participant may hold it

reclaimed:
    no hazard can still refer to it, so its lifetime may end and storage
    may be released or reused

The successful head exchange moves the old dummy from linked to retired. Scanning can move it from retired to reclaimed.

Each participant owns one fixed retired array:

struct RetiredList {
    std::array<Node*, 4096> nodes{};
    std::size_t size = 0;
};

Only that participant appends and compacts its list during concurrent execution. This avoids another shared lock inside retirement.

At a threshold of 64 nodes, the participant scans every hazard:

for (Node* node : my_retired_nodes) {
    bool protected_now = false;

    for (const auto& hazard : all_hazards) {
        if (hazard.load() == node) {
            protected_now = true;
            break;
        }
    }

    if (protected_now) {
        keep(node);
    } else {
        delete node;
    }
}

With P participants and two slots each, a scan of R retired nodes performs at most 2PR pointer comparisons in this direct implementation. Scanning every removal would add that cost to every dequeue. Batching amortizes it.

A larger threshold reduces scan frequency and increases retained memory. A smaller threshold releases sooner and reads the shared hazard array more often. The correct threshold depends on participants, node size, allocation behavior, cache traffic, and acceptable transient memory.

The scan itself reads hazard slots that other cores write. The hazard array can become a shared-memory cost even though different participants own different slots. Padding every slot might reduce false sharing while expanding the scanned footprint. The layout needs measurement rather than a universal padding constant.

a participant owned exactly two writable slots

The standard draft describes a hazard pointer as single-writer and multi-reader. The local domain makes that ownership static:

participant i owns slots 2*i and 2*i+1
all scanners may read every slot

Registration claims a participant index through one atomic Boolean. The caller creates participants before starting worker threads in the tests. One participant object is then used by one thread.

This prevents two threads from racing to publish different nodes through the same slot. It also bounds the scan:

maximum hazards = 2 * maximum participants

The bound is paid in API flexibility. A thread that enters without a participant cannot safely touch the queue. A process with dynamically created threads needs registration, pooling, thread-local ownership, or a standard library facility that manages hazard records.

Destroying a participant clears both slots. It does not scan another participant’s retired array. The test keeps participant objects alive until worker threads join, clears hazards, then performs final scans. Destroying the queue while a participant remains claimed terminates the probe because that is a lifetime contract violation.

The queue and its participant tokens form an ownership graph:

queue owns head, tail, hazard slots, and retired arrays
participant borrows one slot pair from the queue
worker exclusively owns the participant during operations
queue outlives every participant and worker

Making the token move-only prevents accidental copying of slot ownership.

sequential consistency made the first proof shorter

The local hazard operations use memory_order_seq_cst for:

head and tail observations and changes
hazard publication and clearing
hazard scans
source validation in protect

Sequential consistency gives these atomic operations one total order consistent with each thread’s source order.

That makes the protection argument concrete. Suppose a reader publishes hazard D, validates head, and a remover changes head then scans:

reader hazard store
reader validating head load
remover head exchange
remover hazard load

In the total order, the scanner is after the publication and must observe it or a later hazard value in that slot.

If the remover’s head exchange and scan occur first:

reader initial candidate load
remover head exchange
remover hazard scan
reader hazard store
reader validating head load

The validating load is after the head exchange in the same total order and sees that its source no longer contains the old head. The reader retries before dereferencing.

The new-node link uses release on successful publication and consumers use acquire when loading it:

construct Node value and next
release link into predecessor->next
acquire load of predecessor->next
read Node value

The release and acquiring observation establish visibility of construction.

This is intentionally conservative. The standard hazard-pointer facility can express protection epochs without requiring application code to reproduce a global sequentially consistent scheme. Hand-written domains can use weaker operations and fences, but the proof becomes easier to get wrong.

The earlier thread article showed that memory order is not a speed label. Relaxed does not mean fast enough to justify missing synchronization, and sequentially consistent does not mean the entire algorithm is sequential.

tail and head occupied separate destructive regions

The queue declares:

alignas(128) std::atomic<Node*> head_;
alignas(128) std::atomic<Node*> tail_;

Enqueuers write tail and predecessor links. Dequeuers write head. Placing head and tail in one cache line would create avoidable ownership transfers between opposite-end traffic.

The 128-byte separation is a measured-machine-oriented choice carried from the false-sharing investigation. It is not a language guarantee about cache-line size and not a value every type should use.

Hazard publication adds another write path. Every dequeue writes two slots, often several times after validation failures. Scanners read all of them. The benchmark later measures the complete implementation, so these costs remain present rather than being subtracted as bookkeeping.

Node layout also matters:

struct Node {
    std::atomic<Node*> next;
    std::optional<T> value;
};

An enqueue writes next and value before publication. A dequeue reads next, later moves value, then another thread may eventually delete the node. Nodes from a general allocator can share allocator pages but not one contiguous queue array.

A bounded ring queue uses a different layout and avoids per-item node allocation. It also has capacity and publication rules that are separate from this linked-list investigation. “Lock-free queue” does not identify one memory path.

the empty result also needed an instant

Returning a value has a successful head exchange. Returning empty changes no pointer, so its linearization point is an observation.

The implementation protects head, loads next, validates that head is still current, then examines:

next == null

If next is null at that consistent observation, no linked item follows the dummy. A concurrent enqueue that links afterward linearizes afterward, so the empty result remains legal.

If an enqueue linked before the validating observation, the acquire load can find a non-null next and dequeue must not return empty from that state.

Tail alone cannot define emptiness because it is allowed to lag:

head == tail and next != null

means a published item exists and tail needs help.

This is why the condition uses both node relationship and link:

head == tail and next == null: empty
head == tail and next != null: tail behind
head != tail: value path

Removing the dummy node can make empty and one-element transitions much harder. The unused front node buys a uniform head exchange at the cost of one retained allocation.

the mutex won the local benchmark

I compared two nonblocking try_dequeue interfaces:

std::deque protected by one std::mutex
linked queue with atomics, helping, hazard publication, scanning,
general new, and general delete

The mutex version does not sleep on an empty condition variable. Consumers yield after an empty attempt. This isolates transfer paths rather than comparing a blocking API with a spinning one.

Each trial transferred 65,536 unique integers. Three rounds warmed the process. Fifteen measured rounds shuffled method order deterministically. The reported median includes thread startup because both paths create the same producer and consumer population for every trial. Checksums had to match the sum from zero through 65,535.

One complete process:

mutex  producers=1 consumers=1
min=1,048,291 ns median=1,191,208 ns max=1,308,750 ns
median=18.18 ns/item

hazard producers=1 consumers=1
min=7,165,959 ns median=9,351,167 ns max=10,923,459 ns
median=142.69 ns/item

The mutex path was 7.85 times lower median time per transferred item.

With four producers and four consumers:

mutex  min=2,980,667 ns median=3,270,666 ns max=4,050,208 ns
median=49.91 ns/item

hazard min=4,371,042 ns median=46,228,417 ns max=52,658,125 ns
median=705.39 ns/item

The hazard median was 14.13 times higher. Its unusually low minimum is a warning that scheduling creates distinct timing regimes. The median, spread, and repeated process matter more than the fastest sample.

The second complete process preserved the conclusion:

mutex  1p1c median=1,254,209 ns, 19.14 ns/item
hazard 1p1c median=9,113,834 ns, 139.07 ns/item

mutex  4p4c median=3,466,667 ns, 52.90 ns/item
hazard 4p4c median=45,697,750 ns, 697.29 ns/item

The queue without a lock was much slower here.

one producer and one consumer removed the contested exchange

The linked queue supports many producers and many consumers. A pipeline with exactly one of each has stronger ownership:

only the producer writes the tail index and destination slot
only the consumer writes the head index and clears the source slot

I implemented a bounded ring with 1,024 physical slots. One slot remains empty so equal indices have one meaning:

head == tail: empty
increment(tail) == head: full

Usable capacity is 1,023.

The producer path:

std::size_t tail = tail_.load(std::memory_order_relaxed);
std::size_t next = increment(tail);

if (next == head_.load(std::memory_order_acquire)) {
    return false;
}

slots_[tail].emplace(value);
tail_.store(next, std::memory_order_release);
return true;

The producer owns the current tail slot, so no compare-and-swap is necessary. It constructs the value, then publishes the new tail with release.

The consumer:

std::size_t head = head_.load(std::memory_order_relaxed);

if (head == tail_.load(std::memory_order_acquire)) {
    return empty;
}

T value = std::move(*slots_[head]);
slots_[head].reset();
head_.store(increment(head), std::memory_order_release);
return value;

The acquire load of tail observes producer publication before reading the slot. The producer’s acquire load of head observes that destruction completed before reusing the slot.

For the measured std::uint32_t value, each try_push and try_pop performs a fixed sequence of index and slot operations. There is no interference retry loop. Under this fixed-capacity, single-producer, single-consumer contract, those integer transfer methods are wait-free at the data-structure level. A generic T can execute arbitrary work in its constructor, move constructor, or destructor, so nothrow alone would not prove a bounded step count for every specialization. The caller may also choose to retry after full or empty, and that outer loop is not a bounded wait.

This progress result came from reducing concurrency and accepting capacity. It was not obtained by making the multi-party linked algorithm more clever.

one million ring values stayed in order

The producer pushed integers zero through 999,999. The consumer required every next integer to equal its expected position.

AddressSanitizer and UndefinedBehaviorSanitizer reported:

spsc items=1000000
mismatch=0
checksum=499999500000
usable-capacity=1023
index-atomics-lock-free=1

There are no per-item allocations, retired nodes, hazard slots, scans, tags, or ABA opportunity in the fixed slot ownership. An index wraps, but a slot cannot be reused until the consumer’s released head makes that reuse visible to the producer.

The restriction is substantial:

a second producer would race on tail and slot construction
a second consumer would race on head and value movement
an item cannot be accepted when the ring is full
capacity is fixed at construction

Turning the indices into fetch-add reservations does not automatically create a correct multi-party queue. A producer can reserve a slot and pause before publishing it, leaving later reservations visible in an order consumers cannot safely skip. Per-slot sequence numbers or another publication protocol become necessary, and their progress classification must include the paused reservation.

The simplest correct queue is often the one whose topology matches the actual producer and consumer graph.

seven nanoseconds belonged to one scheduling regime

The first complete SPSC benchmark process moved 65,536 integers with:

min=413250 ns median=484750 ns max=560084 ns
median=7.40 ns/item

The second complete process, with identical code and input, reported:

min=2012250 ns median=2723291 ns max=3429708 ns
median=41.55 ns/item

That is more than a fivefold median change between processes.

The M4 contains performance and efficiency cores, and this macOS test does not pin threads to verified core IDs. Thread placement, frequency, and scheduling can create distinct bands. The one-producer and one-consumer ring has little shared work beyond the indices, so differences in where those two tight loops run are exposed directly.

The first process was faster than both mutex and hazard medians from their recorded processes. The second was slower than the fastest mutex runs but still faster than the hazard median. Selecting only the 7.40 ns result would turn scheduler luck into an algorithm claim.

The correctness result is stable. The timing needs CPU placement evidence and more processes before it supports a capacity decision.

lock-free had never meant faster

The hazard path performs more work:

one allocation per enqueue
atomic link retry
tail validation and possible help
hazard publication and validation
atomic head retry
retired-array append
periodic scan across every hazard slot
one deletion after reclamation

The mutex protects optimized std::deque operations. In one-producer and one-consumer traffic, its critical sections are short. In four-by-four traffic, the M4 still completed this fixed workload much sooner.

Lock-free progress addresses dependency on stalled participants. It does not promise fewer instructions, less coherence traffic, lower median latency, or higher throughput.

The stalled-enqueuer test showed a property the throughput benchmark did not measure: a consumer completed while the producer was stopped at an adversarial point. A mutex benchmark with no preempted lock holder can make the blocking design look excellent, because it is excellent for that measured schedule.

Choosing between them requires the failure model:

Can a thread be paused for an unbounded time while inside the operation?
Must another participant continue during that pause?
Is allocator progress controlled?
Can the workload tolerate spinning?
What are throughput and tail-latency targets?
How expensive is memory retention from delayed reclamation?

A production task runtime often needs a blocking wait when no work exists even if its internal queue operations are lock-free. Otherwise idle workers burn CPU polling. Atomic wait, a semaphore, an event count, or a condition variable can provide the sleeping layer without changing the queue’s transfer algorithm.

“Contains no mutex” is a code property. It is not a complete service behavior.

the benchmark mixed allocation with synchronization on purpose

A queue benchmark can preallocate nodes, pin threads, batch transfers, keep the queue at a fixed depth, and report only successful operations. Each choice removes a production cost or selects a workload.

This benchmark keeps per-node allocation because the article is about dynamic reclamation. Removing it would answer a different question.

The method still has limitations:

one Apple M4
one compiler and standard library
one integer payload
one total item count
one yield policy after empty
no CPU affinity on macOS
no page-fault or cache counter capture
no producer work between enqueues
no consumer work after dequeues
no bounded admission
no power or thermal measurement

The workload keeps every participant busy around one queue. Real tasks may perform microseconds or milliseconds of work between transfers, making queue cost a smaller fraction.

The mutex minimum and median varied substantially in some verifier processes. Thread startup, scheduling placement, frequency, and contention phase all remain in the wall time. A stronger campaign would record per-operation distributions, queue depth, retry distributions by participant, CPU placement, and long-running steady state.

The current result supports one claim: this hazard-pointer implementation did not buy throughput on the tested transfer workloads. It does not establish that mutex queues always win.

the retire threshold bounded one kind of growth

With a scan threshold of 64 and eight participants, the four-by-four run performed about 1,570 scans for 100,000 dequeues.

The ideal count from threshold alone is:

100000 retired nodes / 64 nodes per scan = 1562.5 scans

The observed count is close, with final participant scans and temporarily protected nodes accounting for the difference.

At most sixteen hazard slots exist. After a complete scan, only nodes matching a currently published hazard need remain in that participant’s retired list. The fixed 4,096-entry capacity is far above the threshold plus the current hazard bound.

This argument assumes:

participants obey exclusive slot ownership
every dereferenced retired candidate was protected
hazards eventually clear for final reclamation
nodes are retired exactly once
the scan sees publications with the required ordering

Breaking any assumption can turn a capacity estimate into use after free or unbounded retention.

The implementation terminates if a retired array fills after a scan. A production library needs a defined response, perhaps another fixed batch, a global retired structure with its own progress proof, backpressure, or deliberate leak under resource exhaustion. Quietly allocating a bigger vector would reintroduce an allocator call into the claimed path.

the scan bound had units

The threshold calculation can be turned into a memory bound for this fixed domain.

There are eight participant records and two hazard slots per record:

P = 8 participants
H = 2 hazards per participant
P * H = 16 published pointers at most

Each removed node belongs to one retired list. A scan keeps a retired node only if its address equals one of those sixteen published values. Hazards may point at live nodes, and two slots may repeat one address, so sixteen is an upper bound rather than an expected retained count.

After one participant scans, that participant can retain at most sixteen retired nodes. New retirements grow its list until the threshold of 64 triggers another scan. Between completed scans its list is therefore below 64 entries. Across eight participants, the simple bound after operations return is:

8 participants * 63 retired entries = 504 entries

During the operation that reaches the threshold, a list transiently contains 64 before compaction. A thread paused after changing head but before appending the old dummy can also hold one removed node outside its retired list. Those details matter if the bound is used for a hard memory reservation.

Let S be the allocated bytes per node, including allocator rounding, and let L be the number of live reachable nodes. The queue-related node memory is approximately:

(L + 1 dummy + retired nodes + in-flight pending nodes) * S

If allocator rounding makes each node consume 64 bytes, the 504-entry retired-list bound corresponds to:

504 nodes * 64 bytes/node = 32,256 bytes

That number is an arithmetic example, not a measurement of this allocator’s usable size. A real report needs the allocator’s size class and metadata.

Metadata has a separate bound:

8 lists * 4096 pointers/list * 8 bytes/pointer
= 262,144 bytes

The implementation deliberately reserves much more retired capacity than the normal threshold argument needs. That quarter mebibyte exists even when the queue is empty. It buys a fixed append path and room to fail loudly if an invariant is broken.

Scan work also has units. At threshold 64:

64 retired candidates * 16 hazard loads
= at most 1,024 pointer comparisons per scan

At 100,000 dequeues and roughly 1,570 scans, the direct upper bound is about:

1,570 scans * 1,024 comparisons/scan
= 1,607,680 pointer comparisons

The actual loop can stop early when it finds a match, but most retired nodes are unprotected and require checking every slot. Those shared atomic loads are part of the measured hazard cost.

The threshold does not bound live backlog. If producers add one million nodes per second and consumers remove nine hundred thousand, live depth grows by one hundred thousand nodes per second:

1,000,000 enqueues/s - 900,000 dequeues/s
= 100,000 live nodes/s

At an illustrative 64 allocated bytes per node, that is 6.4 MB/s of growing live memory. Tuning reclamation from 64 retired nodes to 32 would not address it. Admission control or more consumer capacity would.

It also does not bound a broken hazard protocol. A participant that leaks one hazard retains at most the node matching that pointer in this scheme, but a participant that stops retiring its locally removed nodes can strand its entire private list. The progress test paused before the head exchange, so active threads performed the retirements. Different pause sites have different memory consequences.

The formula makes the diagnostic split explicit:

reachable nodes grow:
    service backlog or missing admission control

retired nodes grow:
    hazard retention, stalled owner, scan failure, or retirement bug

metadata is large while both counts are small:
    fixed provisioning choice

Bytes identify which problem the queue is actually creating.

an epoch moved the announcement from pointer to interval

Hazard pointers announce exact nodes. Epoch-based reclamation announces that a participant is inside a read-side interval.

A simplified epoch design records:

global epoch
each participant's active flag and observed epoch
retirement epoch on each removed node

A node retired in epoch e can be reclaimed after every participant that could have observed it has either exited its interval or advanced beyond the relevant epoch.

This reduces per-pointer publication. A traversal can read several nodes inside one protected interval. Scanning participant epochs can be cheaper than comparing every retired node against every hazard pointer.

The stalled-thread consequence is broader. A participant that remains active in an old epoch can delay reclamation of every node retired after its observation boundary, not only the exact two nodes it currently holds.

Hazard pointers made the forced delay retain one node. An epoch version of the same test could retain thousands while queue operations continue.

Neither method is universally better. Access pattern, number of simultaneously held pointers, thread churn, tolerance for stalled participants, deletion cost, and memory bound decide.

Read-copy update uses another read-side and grace-period model, especially in kernels and systems with scheduler integration. Garbage collection can make pointer discovery automatic in managed environments. Reference counting makes lifetime changes eager but adds shared counter traffic and cycle issues.

The central question stays the same:

what evidence proves that no future dereference can reach this removed object?

Different reclamation schemes collect different evidence.

the packed generation was not a reclaimer

The tagged control rejected generation 1 when generation 2 occupied the same slot. It can protect a compare-and-swap snapshot if the counter does not wrap.

It does not stop this:

reader loads pointer D and generation 1
remover removes D and deletes it
reader dereferences D before performing its tagged comparison

The comparison would eventually fail, but the invalid dereference happened first.

A safe tagged algorithm must ensure nodes remain alive through every dereference, perhaps through hazard pointers, epochs, reference management, or a pool that never destroys node objects during concurrent use.

The original Michael and Scott algorithm combines counted pointers with a free-list design suited to its target assumptions. Translating pseudocode into modern C++ requires mapping every multiword snapshot, counter, allocation action, and memory order onto facilities the platform actually supplies.

An std::atomic<struct { Node* pointer; uint64_t tag; }> is not guaranteed lock-free merely because each member is. Calling is_lock_free on the actual type and target is necessary. Alignment can also change the result.

Packing an index and generation into 64 bits worked because the probe used three known slots. A general process pointer does not come with a 32-bit index.

hazard pointers did not make every pointer safe

Protection applies only to pointers acquired through the protected source-validation loop.

This is wrong:

Node* node = head.load();
Node* next = node->next.load();
my_hazard.store(node);

The dereference occurs before publication. A remover can delete node in the gap.

This is also wrong:

Node* node = head.load();
my_hazard.store(node);
return node->next.load();

There is no re-read of head. A remover can change head and scan before the publication, then the reader can publish an already deleted address.

Publishing the head does not automatically protect the successor after head changes. The second slot exists for that reason.

Keeping a hazard published while a pointer escapes into another object can retain memory indefinitely. Clearing it too early creates a dangling escape. A protected-pointer wrapper can tie slot reset to lexical lifetime, but moving and storing that wrapper need defined ownership.

The standard draft’s hazard pointer object is move-only and owns one hazard record. That shape turns record ownership into RAII. The protected node remains non-owning, and retirement remains a separate action.

The local Participant is coarser. It owns two fixed slots for its whole registration lifetime and explicitly clears them on every operation path.

Every continue, empty return, failed exchange, exception boundary, and success path needs the slots to contain either the pointer currently used or null. A stale hazard is usually a memory-retention bug rather than immediate corruption, which makes it easy to miss in correctness tests.

ThreadSanitizer could not certify reclamation

ThreadSanitizer finds conflicting memory accesses without a sufficient synchronization relation on the executed path. The immediate-delete probe uses atomics for coordination, so the invalid access is not necessarily a data race. AddressSanitizer identifies that the object was already freed.

The ABA schedule keeps node objects alive and uses atomic head changes. It can corrupt a logical invariant without a data race or an invalid allocation access. Neither sanitizer knows that head must name an in-queue node.

The history checker knows FIFO behavior but not whether a retired object was freed too early.

The MPMC uniqueness counters know that values were returned once but allow some real-time order violations unless histories expose them.

The evidence layers are:

sanitizers:
    observed language-level memory errors and races

reference counters and checksums:
    value conservation for selected runs

history checker:
    existence of legal sequential witnesses

invariant and progress argument:
    why all permitted interleavings preserve structure and system progress

reclamation argument:
    why every actual dereference precedes object deletion

Concurrent data structures are difficult because passing one layer leaves the others open.

a queue API still needed waiting and shutdown

try_dequeue returns empty immediately. A task worker normally needs to sleep until work arrives or shutdown begins.

Putting a condition variable around an otherwise lock-free queue is not contradictory if the public operation honestly describes both paths. The transfer can be lock-free while the empty wait blocks.

The runtime needs durable state for:

work may be present
submission has closed
workers must drain or abandon
waiting threads need wakeup
capacity may require backpressure

An unbounded linked queue offers no admission control. Producers can allocate nodes faster than consumers remove them. Reclamation only handles nodes that already left; it does nothing for a growing live backlog.

A bounded queue turns overload into a failed or waiting enqueue. Its capacity and progress properties differ from this dynamic list.

Shutdown adds participant lifetime. A queue cannot destroy hazard records, retired arrays, or live nodes while workers can enter another operation. Joining threads is a blocking outer protocol even when transfers are lock-free.

The small implementation refuses to hide that protocol. Its destructor requires every participant token to be gone. Tests join workers, scan after hazards clear, then destroy the queue.

values larger than an integer changed the contract

The probe transfers integers with nothrow movement. A production queue may carry owning tasks, strings, or request records.

Constructing a node can throw before publication. The unique pending owner cleans that path.

Moving a value out after the head exchange must not throw in this design. The static assertion makes that requirement compile-time visible.

Destroying a retired value also needs a nonthrowing destructor. An exception leaving reclamation would break cleanup from a path with no caller prepared to repair queue state.

Large values increase allocation size and cache traffic. Storing an owning pointer in each node keeps the node small and makes payload lifetime another allocation. Storing values inline reduces indirection but makes every node movement and cache fill larger.

Multiple consumers cannot all move from a value before one wins the head exchange. This implementation moves only after the winning exchange while protecting the new dummy.

A peek operation would be much harder to expose safely. Returning T& or T* would let a pointer escape after the hazard slots clear. The API would need a protected handle whose lifetime retains a hazard, a value copy, or an ownership transfer.

API shape determines how far the lifetime proof must extend.

a retry counter was not enough to diagnose a stall

The 100,000-item run had tens or hundreds of thousands of retries depending on instrumentation. One total cannot identify:

which participant starved
which shared location caused retries
whether tail helping dominated
whether scans interrupted useful work
whether allocation stalled
whether consumers mostly found empty

Per-participant distributions and phase timestamps would be needed.

Progress failures also need distinct telemetry:

time since last successful enqueue
time since last successful dequeue
current live queue depth
retired nodes by participant
oldest published hazard age
scan duration and reclaimed count
allocation failures
empty polling rate

An old hazard with continuing transfers points at reclamation retention. No successful operation with active contenders points at a queue or execution problem. Growing live depth with successful enqueues points at service capacity, not reclamation.

A production alert named “lock-free queue stuck” compresses these mechanisms into one phrase and delays diagnosis.

the returned address now failed the protection test

The opening delayed operation loaded D and immediately remembered A. It published no hazard. Fast operations removed D and A, reused D, and brought that address back to head. Pointer-only compare-and-swap accepted it.

With protection, the delayed path must first publish D, then re-read head. If fast removal happens before publication, validation finds a different head and the delayed path never dereferences its stale successor.

If publication happens first, removal can retire D, but scanning finds the hazard. The pool cannot reclaim and reuse that storage as generation 2 while the hazard remains.

The two possible schedules become:

head changed before protection became valid:
    validation fails, retry

protection became valid before head changed:
    retirement succeeds, reclamation waits

There is no schedule in the sequentially consistent protection order where the reader validates old D, the scanner misses its hazard, and the same storage is safely returned for reuse before the reader clears protection.

The tag supplied missing historical identity to one atomic comparison. The hazard supplied missing lifetime evidence to every dereference. Retirement separated logical removal from physical reuse. Helping separated one participant’s delay from system-wide progress. The benchmark showed that none of those properties promised speed.

The head pointer could return. The old node could not return while somebody still held it.