ABA Problem Lab

The pointer came back. The object did not.

This interactive Emacs Lisp simulator makes the ABA problem observable. A thread reads pointer A and pauses. Other threads remove A, mutate the structure, and recycle the same address for a new object. When the first thread resumes, a value-only compare-and-swap sees A == A and succeeds against the wrong lifetime.

Default finding: 50,160 invisible structural corruptions pass successful CAS checks across 15 million operations.

The lab compares raw pointer CAS, stamped pointers, hazard pointers, and epoch reclamation under the same deterministic workload. It puts correctness beside the retry, scan, latency, and retained-memory costs that each mitigation moves elsewhere.

Explore telemetry.sh to correlate the reader, allocator, CAS, and reclaimer signals that distinguish address equality from object identity.

Why this lab exists

An application-level success signal can be exactly right and operationally misleading:

thread 07 loads       A at 0x7F40, generation 41
thread 12 removes     A and B
allocator recycles    0x7F40
thread 03 pushes      A at 0x7F40, generation 42
thread 07 compares    0x7F40 == 0x7F40  → success
identity comparison   generation 41 != 42

The CAS did what it was asked to do. The missing invariant was object lifetime. Status, throughput, and value-only atomic metrics do not contain that proof.

This is distinct from the catalog's allocator-fragmentation and false-sharing labs. Those explain memory layout and performance. This lab explains a lock-free identity and safe-reclamation failure that can silently corrupt a data structure while atomic operations keep succeeding.

Technology

• Emacs Lisp 29 analytical model and dependency-free TCP/HTTP service
• Built-in JSON, network-process, byte compiler, and ERT facilities
• Vanilla HTML, CSS, JavaScript, and Canvas interface
• Non-root Ubuntu 24.04 production container
• No application packages or external runtime dependencies

Run it

You need GNU Emacs 29+, Node.js, Python 3, curl, and Make.

make run

Open http://127.0.0.1:8080.

Run only the model:

make model | jq

Model parameters may also be supplied as uppercase environment variables:

SURGE_REUSE_PERCENT=20 TAG_BITS=32 make model | jq

Run the production image:

docker build -t aba-problem-lab .
docker run --rm -p 8080:8080 aba-problem-lab

The four strategies

Strategy	Identity outcome	Cost exposed by the lab
Raw pointer CAS	Address reuse can pass a stale CAS	Silent structural corruption
Stamped pointer CAS	Address plus generation detects reuse	Wider state, retry work, finite tag horizon
Hazard pointers	Published readers prevent observed nodes from being recycled	Publication, scans, and retire-list memory
Epoch reclamation	Reuse waits for a grace period	Retained nodes and sensitivity to stalled readers

No strategy is presented as universally best. Tagged state still needs a sufficient generation space. Hazard pointers require correct publication and scanning. Epoch schemes depend on progress and a grace period longer than the reader pause. The UI lets you drive those assumptions past their safe boundary.

Default experiment

The deterministic 300-second run uses:

• 50,000 lock-free operations per second across 16 workers
• 2% of CAS attempts delayed by a 250 µs pause
• 5% baseline address reuse
• an 85% reuse surge from second 60 through second 239
• a 35% chance of interfering A → B → A mutation
• a 90% chance that a raw stale CAS commits
• a 24-bit generation tag
• a 50 ms epoch grace period

During the surge:

50,000 operations × 2% delayed                 = 1,000 delayed CAS
1,000 delayed CAS × 85% address reuse          =   850 reuse candidates
850 candidates × 35% interfering mutation      ≈   298 ABA windows
298 ABA windows × 90% unsafe raw CAS success    ≈   268 corruptions / second

The model rounds each workload stage independently because these are event counts, not fractional requests. Outside the surge, the 5% baseline reuse rate produces 16 modeled corruption events per second:

60s × 16 + 180s × 268 + 60s × 16 = 50,160

Every strategy still reports 100% application success. The raw strategy's integrity is 99.67%.

What telemetry.sh reveals

The decisive evidence spans multiple signals. Preserve these dimensions:

Field	Why it matters
trace_id	Connects the logical request to allocator and CAS work
operation_id	Joins the original load to its eventual compare-exchange
thread_id	Identifies paused readers and interfering writers
head.address	Shows that the same pointer bits returned
head.generation	Distinguishes two lifetimes at one address
cas.expected_address	Records the reader's value predicate
cas.expected_generation	Records the reader's identity predicate
cas.observed_address	Shows why value-only CAS succeeded
cas.observed_generation	Shows why the operation was structurally stale
reclaimer.strategy	Separates raw, stamped, hazard, and epoch behavior
reclaimer.epoch	Connects reuse to grace-period progress
retire_list.depth	Makes deferred-reclamation memory visible

A useful investigation joins reader spans, allocator logs, and CAS events on operation_id plus head.address. Filter successful CAS operations where the expected and observed generations differ, then group by reclamation strategy, thread, and epoch. Compare the corruption count to pause p99, retry rate, retire-list depth, and retained bytes.

That is the telemetry.sh advantage demonstrated here: reconstructing an invariant from traces, logs, and metrics even when every local operation claims success.

API

POST /api/simulate accepts a JSON object containing any model parameters:

curl http://127.0.0.1:8080/api/simulate \
  -H 'content-type: application/json' \
  -d '{
    "operations_per_second": 100000,
    "surge_reuse_percent": 95,
    "tag_bits": 16,
    "epoch_grace_ms": 10
  }'

The response contains normalized parameters, four strategy summaries, per-second timelines, the telemetry join fields, and a headline finding. Unknown fields are ignored. Known fields must be JSON numbers, values are clamped to safe ranges, and bodies are limited to 64 KiB.

Useful endpoints:

GET  /                  interactive lab
GET  /health            container health
POST /api/simulate      deterministic model

Verify it

make check
make container-test

make check byte-compiles the service with warnings promoted to errors, runs seven ERT behavioral tests, starts the live server on an ephemeral port, tests the API and validation failures, checks security headers, parses the JavaScript, and verifies desktop/tablet/mobile CSS breakpoints.

make container-test builds the final non-root image, probes the UI and model API, and waits for Docker's health transition.

Project layout

aba-problem-lab.el             model, CLI, HTTP service
public/                        interactive flight recorder and charts
tests/aba-problem-lab-test.el  deterministic ERT tests
tests/http-test.sh             live API, asset, and security checks
tests/container-test.sh        final-image smoke test
.github/workflows/ci.yml       clean native and container gates

Semantics and model boundaries

Rust's standard-library documentation warns that a pointer returning to the same address does not imply that the same object exists there, and explicitly identifies ABA as a risk of AtomicPtr.compare_exchange. Java's AtomicStampedReference demonstrates the address-plus-stamp technique by atomically comparing both a reference and an integer generation:

• Rust AtomicPtr::compare_exchange considerations
• Java AtomicStampedReference

This lab is an explanatory analytical simulation, not a lock-free container, memory-safety test, or throughput benchmark. It does not dereference reclaimed memory or predict a specific allocator. The event rates, pause costs, tag collisions, scan overhead, and retained-node counts are modeled estimates.

Real behavior depends on the algorithm, allocator reuse policy, address-space layout, compare-exchange width, memory ordering, scheduler, thread progress, hazard publication protocol, epoch implementation, tag packing, wraparound, and workload distribution. Validate a production hypothesis against the implementation and representative traffic.

License

MIT — see LICENSE.