Unlinking does not establish safe deallocation
A reader loads stack head A and pauses. Another thread can remove A from the structure while the first still holds its reference. Freeing A merely because it is no longer reachable from the head can make the resumed reader access invalid storage. Logical removal and safe physical reuse occur at different boundaries.
Lock-free updates do not automatically solve reclamation progress or memory retention. A paused reader may delay freeing nodes even when other operations continue. This guide does not deliberately execute a use-after-free example. It uses deterministic node identities, protection records and retired sets to expose the lifecycle. That is a model for understanding protocols, not a production concurrent allocator whose memory-ordering and reclamation properties have all been implemented and proved.
Separate ABA from access after lifetime ends
An address can leave the head, be reused for another node and return with the same numeric value. A CAS comparison may then miss an intervening change: one form of ABA. Separately, reading a freed node is already a lifetime violation even before that address is reused. Equality of compared addresses and validity of dereferencing them are different requirements.
A version tag can help detect some stale comparisons without extending the lifetime of referenced storage. Conversely delayed physical reclamation in a garbage-collected environment does not erase every logical state-change issue. Track comparison identity, membership in the structure and storage lifetime on separate diagram rows. That makes it possible to say which problem a particular protocol actually addresses instead of treating every pointer hazard as one interchangeable bug.
| Stage | Meaning | Not implied |
|---|---|---|
| Protect | Publish reader protection | Acquisition protocol is automatically complete |
| Retire | Unlink from the structure | All readers have released it |
| Reclaim | Free after the scheme's safety condition | Always possible immediately after unlink |
Protect and then validate a hazard reference
A reader loads the head, publishes that node as protected and validates that the head still matches. If it changed, retry the acquisition protocol. This addresses the window in which removal could happen between reading a pointer and making protection visible. Merely saying that a read pointer is protected does not explain how that intervening race is closed.
A remover retires nodes instead of immediately freeing them. Scanning protection records identifies candidates no longer referenced by readers. Publication order, scanning and validation are crucial in a real memory model. The Python dictionary example is deliberately a sequential metadata model, not a correct concurrent hazard-pointer library. A production API must specify the protection scope and release rules, and clients must follow those rather than transferring the model's simplicity into unsafe raw-pointer code.
Execute retirement and reclamation as distinct states
Reader A protects node one and validates the head. The remover advances the head to two and retires one. The first scan must retain node one because it is protected. Only after A releases protection may the next scan move it into the reclaimed set. Assertions check both stages instead of pretending unlinking itself frees memory.
This is metadata set arithmetic, with no actual concurrent dereference or deallocation. Its purpose is to show the relationship between retired and protected sets. Label that scope in the source and evidence. An extension can add a second protecting reader and show that releasing only one protection is insufficient. Track which reader protects which identity rather than substituting an unrelated count that loses the relationship needed by the scan.
head=1;hazards={};retired=set();freed=set()
# Reader publishes protection, then validates that head still matches.
read=head;hazards['A']=read;assert read==head
head=2;retired.add(1)
def scan():
reclaim=retired-set(hazards.values());freed.update(reclaim);retired.difference_update(reclaim)
scan();assert retired=={1} and freed==set()
del hazards['A'];scan();assert retired==set() and freed=={1}
print('protected node retained; released node reclaimed')
print('deterministic metadata model; not a concurrent allocator implementation')
Track reader periods in epoch schemes
Epoch schemes record reader participation in periods and delay reclamation until relevant earlier readers have passed a safe point. This differs from protecting individual node identities. Per-read bookkeeping, scan cost and the effect of paused readers can therefore differ from hazard pointers. Neither name establishes a universally superior choice; read-section duration, update rate and thread-exit policy matter.
A reader paused inside an old interval can delay reclamation while other operations continue, allowing retired storage to grow. Capacity planning must account for that retention rather than assume unlimited memory. Hazard protections forgotten on an exception can also keep particular nodes alive. Both approaches need explicit entry, exit and cleanup rules. Update correctness alone does not establish a bound on operational memory use.
Evaluate reclamation work separately from update progress
A push/pop algorithm may be described as lock-free while its allocation or reclamation path still uses locks. Read the boundary of the claimed progress property. A large scan attached to one operation can also increase individual latency even when system-wide progress continues. Throughput, tail latency and retained retired memory are different measurements.
A real library needs contracts for registration, memory ordering, nested protection, exception cleanup and thread exit. The metadata example is not a replacement for that complete implementation. Benchmarks should not omit all reclamation merely to improve an operation-time number while ignoring retained storage afterward. Record allocation and reclamation inside the measured boundary, and compare protocols under the retention and latency requirements the application actually has.
Assign responsibility for releasing protection
An exception should not leave protection records indefinitely when the protected use has ended. A scoped guard can make ownership explicit, but releasing too early exposes a reader still using the node. Align the end of protection with the final dereference, not merely a convenient source-code line.
Registered-thread schemes also need a cleanup owner when a thread terminates. A paused thread differs from a terminated one: inactivity alone does not authorize deleting its protection because it may resume. The model checks one explicit release path. Adding exception, forced-exit or registration-failure handling creates new lifetime histories requiring separate analysis. Do not claim those paths were tested merely because the normal release worked. Protection duration, record ownership and safe reclamation must describe one consistent lifecycle under each supported exit condition.
Treat delayed reclamation as a capacity concern
A correct algorithm can retain many retired nodes when updates are frequent and readers stay protected for a long time. Observe retirement rate and longest relevant protection interval. Their simple product can guide an initial estimate, while overlapping readers, scan periods and batched freeing add further conditions. Do not present an approximate planning number as a strict bound beyond the measured workload.
Garbage-collected structures can also retain old versions through live references, but their mechanism and guarantees are not identical. Distinguish deliberate safe retention from permanently forgotten protection. Record retired counts, retention duration and reclamation time alongside update throughput. Those dimensions reveal operational tradeoffs hidden by a benchmark measuring only how quickly nodes disappear from the logical structure. Safe removal and sustainable memory use need evidence at different boundaries.
Exercise: explain a remaining reader’s protection
If A and B both protect node one, removing A's protection after retirement is insufficient. B still references that identity. Reclamation becomes a candidate only after B also releases and a valid scan establishes no relevant protections remain. Looking only at the current head would miss references held outside the structure.
Adding a version tag to the address does not by itself permit immediate freeing: detecting changed comparison identity and preserving reader lifetime remain separate. Finish by stating the model's evidence accurately. It checked retention while protected and reclamation after release, not a real concurrent allocator or its progress guarantee. That scoped explanation is the learning outcome, alongside an understanding of why removal, retirement, protection and reuse are distinct events.