Harden LightEpoch: make the epoch announce part of the slot-claim CAS by tiagonapoli · Pull Request #2015 · microsoft/garnet

Tiago Nápoli (tiagonapoli) · 2026-08-04T01:13:03Z

Note: this does not affect production use of Garnet. Tsavorite's CRUD paths (Read/Upsert/RMW/Delete) already issue interlocked operations and memory barriers around epoch protection, so the required ordering is established independently and the scenario below cannot occur there. This change hardens LightEpoch itself for non-Tsavorite-core paths that use it directly, without relying on the caller's barriers.

Summary

A thread entering a protected region announces its epoch with a plain store, which is not ordered against the reclaimer's later load of the same slot. A reclaimer can scan a live reader's slot, see it as free, raise SafeToReclaimEpoch past the reader's epoch, and free a page the reader is about to dereference.

The fix changes which word the claim CAS operates on - localCurrentEpoch instead of threadId. No barrier and no atomic is added — the lock cmpxchg was already there, it just lands on a different word.

Scoped to x86-64. ARM64 additionally need more fixes; that ordering work, along with herd7 models and TLA+ specs, is deliberately left out of this change.

The bug

ReserveEntryForThread(ref entry);                              // CAS: threadId 0 -> tid
(*(tableAligned + entry)).localCurrentEpoch = CurrentEpoch;    // plain store: the announce

Store-then-load-of-another-address is the one reordering TSO permits:

Reader	Reclaimer
CAS `threadId` = tid
store `localCurrentEpoch` = 5 (buffered)
	scan slot → reads 0, treats it as free
	`SafeToReclaimEpoch` = 5, free the page
load page → use-after-free

The fix

The CAS writes localCurrentEpoch directly, so claiming the slot and announcing the epoch are one locked RMW

if (Interlocked.CompareExchange(ref (tableAligned + entry)->localCurrentEpoch, epoch, 0) != 0)
    return false;

// The slot is now exclusively ours, so threadId needs no interlocked write.
(*(tableAligned + entry)).threadId = Metadata.threadId;

Violation proof

8-hour hardware run

Two Azure VMs, quarantine litmus, baseline vs fixed (2026-07-30, westus2, x86-64):

impl	violations	sampled rounds
baseline	3,680	8.97 × 10⁷
this fix	0	5.60 × 10⁸

Local repro

--buggy points the harness at BuggyLightEpoch, a frozen copy of main's version, so both arms run back to back on one machine (20 logical processors, x86-64, 15 s runs):

arm	run 1	run 2	run 3	run 4	exit
fixed	0	0	0	0	0 (pass)
buggy	34	77	131	245	1 (violation)

Benchmarks

BDN RawStringOperations, 3 interleaved runs per arm on a dedicated x86 VM (Xeon 8272CL, 16 vCPU): mean |Δ| 1.46%, 5 faster / 5 slower, 0 B allocated in both arms.

GetNotFound had the widest spread, so it was re-run alone with 8 interleaved runs per arm:

arm	mean	median	min	max
baseline	6.960 µs	6.848	6.519	7.761
this fix	6.846 µs	6.826	6.628	7.104

The fix is 1.65% faster, but the baseline's own run-to-run spread is far larger than that — it's host noise, not a real effect. No measurable cost.

A thread entering a protected region announced its epoch with a plain store, which is not ordered against the reclaimer's later load of the same slot. A reclaimer could scan a live reader's slot, see it as free, raise SafeToReclaimEpoch past the reader's epoch, and free a page the reader was about to dereference. The claim CAS now writes localCurrentEpoch directly, so claiming the slot and announcing the epoch are one locked RMW and the announce is globally visible before any load in the protected region can issue. No barrier and no atomic is added; the lock cmpxchg was already there. localCurrentEpoch doubles as the ownership word, sound because a protected thread never announces epoch 0. Release() correspondingly clears threadId before freeing the slot. LightEpoch moves to its own Garnet.LightEpoch project so it can be tested and disassembled in isolation, with unit tests and a quarantine litmus harness under playground/LightEpochLitmus. Co-authored-by: Copilot <[email protected]> Copilot-Session: 38cd2f3a-d460-407c-8a96-a7330974ce99

CodeQL builds the whole solution with 'dotnet build -f net8.0', which failed because the litmus project only targeted net10.0. Inherit the repo default net8.0;net10.0 and pin the Dockerfile/README commands to net10.0. Co-authored-by: Copilot <[email protected]> Copilot-Session: b5f062b9-2d72-4cf0-b6f3-4c9beb98d068

Drop the Garnet prefix from the epoch library and its unit test project so they match the Tsavorite.core / Tsavorite.test.* naming of the rest of the storage engine. Co-authored-by: Copilot <[email protected]> Copilot-Session: d306b783-4a33-4673-9e29-790995df8179

Undo the split of LightEpoch into a standalone project: the sources return to src/core/Epochs/ and the duplicated Murmur3 helper is dropped in favor of the existing Utility.Murmur3. LightEpochLitmus now references Tsavorite.core. Co-authored-by: Copilot <[email protected]> Copilot-Session: d306b783-4a33-4673-9e29-790995df8179

LightEpoch already exposed a public Dispose(); declaring the interface adds nothing and was not part of the fix. Co-authored-by: Copilot <[email protected]> Copilot-Session: d306b783-4a33-4673-9e29-790995df8179

Co-authored-by: Copilot <[email protected]> Copilot-Session: d306b783-4a33-4673-9e29-790995df8179

Tiago Nápoli (tiagonapoli) · 2026-08-04T17:40:50Z

Epoch BDN results — no regression

Ran EpochTests (BDN-Tsavorite.Benchmark) on a dedicated Azure Standard_D16ds_v5 (Ice Lake), Ubuntu 24.04, .NET 10.0.302, DOTNET_TieredPGO=0, taskset-pinned. Baseline main @ 4c004e2a vs PR 6e72265e, 5 rounds alternating main/PR, fresh process each round.

Benchmark	`main` mean	PR mean	Δ	baseline spread	Verdict
`ResumeSuspend`	8.768 ms	8.781 ms	+0.15%	0.30%	noise
`ProtectAndDrain`	1.439 ms	1.225 ms	−14.9%	0.07%	artifact — pinned-heap placement, reproduces `main`
`BumpCurrentEpoch`	18.837 ms	18.892 ms	+0.29%	0.68%	noise

For ResumeSuspend/BumpCurrentEpoch the two arms' ranges fully overlap and the baseline alone wanders as much as the reported delta. Same 5-round protocol against the merge-base (c6cc866b) gave the same picture.

Bottom line

No regression on any of the three epoch benchmarks. ResumeSuspend and BumpCurrentEpoch are flat within noise, and ProtectAndDrain is genuinely unchanged — its apparent 15% gain is an allocator-placement artifact I reproduced on unpatched main, so please don't read it as a win either.

Rewrite the ProtectAndDrain docs to state that it refreshes an already-held slot rather than entering the protected region, that SafeToReclaimEpoch is gated on the minimum announced epoch so a holder that never refreshes stalls reclamation process-wide, and that a refresh relinquishes protection for the previously announced epoch. Read CurrentEpoch volatile when announcing and inline ReserveEntry into ReserveEntryForThread. Co-authored-by: Copilot <[email protected]> Copilot-Session: b6f65ef0-7c7f-40d9-a95f-3ecb62de9d5a

Co-authored-by: Copilot <[email protected]> Copilot-Session: b6f65ef0-7c7f-40d9-a95f-3ecb62de9d5a

Make the ProtectAndDrain announce a release store and the reclaimer's ComputeNewSafeToReclaimEpoch scan an acquire load, so a slot's announced epoch cannot be observed out of order with the work it guards. Hoist the announced epoch into a local so Drain reuses it instead of re-reading the slot. Co-authored-by: Copilot <[email protected]> Copilot-Session: 8b507896-826f-444c-b958-51c19863f429

Copilot AI review requested due to automatic review settings August 4, 2026 01:13

Copilot started reviewing on behalf of Tiago Nápoli (tiagonapoli) August 4, 2026 01:13 View session

This comment was marked as resolved.

Sign in to view

Tiago Nápoli (tiagonapoli) force-pushed the workstream/lightepoch-x86-minimal-v2 branch from 30d3992 to 216b7b3 Compare August 4, 2026 01:23

Tiago Nápoli (tiagonapoli) requested review from Ted Hart (TedHartMS), Badrish Chandramouli (badrishc), kevin-montrose and Vasileios Zois (vazois) August 4, 2026 01:26

Tiago Napoli and others added 5 commits August 3, 2026 18:35

Drop redundant IDisposable declaration from LightEpoch

b807c4e

LightEpoch already exposed a public Dispose(); declaring the interface adds nothing and was not part of the fix. Co-authored-by: Copilot <[email protected]> Copilot-Session: d306b783-4a33-4673-9e29-790995df8179

Restore .github/copilot-instructions.md to match main

02fc0a0

Co-authored-by: Copilot <[email protected]> Copilot-Session: d306b783-4a33-4673-9e29-790995df8179

hexonal (hexonal) mentioned this pull request Aug 4, 2026

Fix non-positive count on LMPOP and LPOP/RPOP #2010

Merged

Tiago Nápoli (tiagonapoli) added 2 commits August 4, 2026 08:55

Merge branch 'main' into workstream/lightepoch-x86-minimal-v2

6e72265

Merge branch 'main' into workstream/lightepoch-x86-minimal-v2

6e86007

Merge branch 'main' into workstream/lightepoch-x86-minimal-v2

e538802

Tiago Nápoli (tiagonapoli) changed the title ~~Fix unfenced epoch announce in LightEpoch (x86-64)~~ LightEpoch: make the epoch announce part of the slot-claim CAS (x86-64) Aug 5, 2026

Tiago Nápoli (tiagonapoli) changed the title ~~LightEpoch: make the epoch announce part of the slot-claim CAS (x86-64)~~ Harden LightEpoch: make the epoch announce part of the slot-claim CAS (x86-64) Aug 5, 2026

Tiago Nápoli (tiagonapoli) changed the title ~~Harden LightEpoch: make the epoch announce part of the slot-claim CAS (x86-64)~~ Harden LightEpoch: make the epoch announce part of the slot-claim CAS Aug 5, 2026

Merge branch 'main' into workstream/lightepoch-x86-minimal-v2

89eba86

Badrish Chandramouli (badrishc) approved these changes Aug 5, 2026

View reviewed changes