package hostlife import ( "fmt" "os" "strings" "testing" ) // Witness scenarios (moves spec §14.2, rev 7.3). // // The random sweep reaches some interleavings rarely, and every new biased // schedule reshuffles every seed, so a rare rule's catch can vanish from // one revision to the next (lost-return-park in rev 7.1, // generation-conditional in rev 7.2). A witness is one fixed, hand-scheduled // scenario for one rule: it forces exactly the interleaving the rule // exists for, as a sequence of protocol steps the witness chooses, with a // quiet RNG that injects nothing. It must hold (no invariant violated) with // the rules in place, and violate an invariant when the rule's mutation is // applied, alone or in the stated combination. // // Witnesses never draw from a seed's RNG and never run inside the sweep's // seeds, so adding one reshuffles nothing. They are the deterministic half // of the mutation evidence; mutate.sh runs TestWitnesses beside the sweep // and reports both. // quiet is the witness's RNG: every draw takes the branch that injects // nothing (no fault, no stall, no duplicate, no late completion, no // second process), so a scenario is exactly the steps the witness scripts. type quiet struct{} func (quiet) Intn(n int) int { if n <= 1 { return 0 } return 1 } type witness struct { rule string // the rule it is for needs string // the mutation set under which it must violate: the rule alone, or a combination the rule belongs to want string // the failure the scenario names: a substring of the first violation (R3 review) note string // what it shows run func(t *testing.T, w *world) } var witnesses = []witness{ {"generation-conditional", "generation-conditional", "cannot start the host", "an earlier push's generation.json PUT completes after a later push's; unconditional, it puts the old generation back and the serving box cannot start", wGenerationConditional}, {"fence-converts-moving", "fence-converts-moving", "INV-3", "the source of a pre-flip move is terminated in a one-box region; the fence converts the move to relocating at pinning with exec none and the lane's park owed, the operator is alerted once, nothing loops while no box exists, and the relocation completes on the replacement box region HA enrolls; without the rule the move never converges", wFenceConvertsMoving}, {"lost-return-park", "lost-return-park", "ended with residue", "a target stopped after its first return PUT is declared lost; without the park the lane stays in the source region at the release (INV-10)", wLostReturnPark}, {"declare-lost-compute", "declare-lost-compute", "INV-1", "a frozen target's lease expires; declared lost on expiry alone, it resumes beside the recovered source (INV-1)", wDeclareLostCompute}, {"watchdog-independent", "declare-lost-compute,watchdog-independent", "INV-1", "redundant alone: with compute fencing a paused agent cannot be declared lost; with expiry-based declare-lost, a watchdog inside the paused agent never fences, and the target runs beside the recovered source (INV-1)", wWatchdogIndependent}, {"lost-quarantine", "lost-quarantine", "holds local state", "a lost box starts again with its old disk; without the quarantine it keeps a database and files for a host served elsewhere (INV-10)", wLostQuarantine}, {"markers-last", "markers-last", "acknowledged timer", "the target's agent crashes between extracting the files and writing the marker; a marker written first vouches for timers that were never installed (INV-2)", wMarkersLast}, {"rollback-journal", "rollback-journal", "cold restore", "the source's agent restarts during a dirty rollback's probe; without the journal it restarts at `claimed`, parks the return generation it had replicated into, and a durable write is lost on cold restore (INV-2)", wRollbackJournal}, {"seal-by-version", "seal-by-version", "cold restore", "a pre-cut staging round completes after the seal; a landing that copies the current version installs the stale round and loses the writes made after it (INV-2)", wSealByVersion}, {"staging-quiet", "staging-quiet", "ended with residue", "a staging round completes after the landing's staging park acknowledged; retired at the seal rather than after the writers' horizon, the round is residue at the release (INV-10)", wStagingQuiet}, {"claim-cas-opid", "claim-cas-opid,revalidate-before-effect", "store of app", "redundant alone: the source closes the rollback's record and stalls before its release (rev 7.23, record first); the recovery pass releases from last_move, a purge claims the host, and the stalled goroutine resumes into its release with the rollback's last read; revalidation stops it, and so does the op-id condition on its release CAS; with both gone the release overwrites the purge and the store is torn down under a serving host", wClaimCasOpID}, {"dirty-return", "dirty-return", "INV-2", "the target writes during its probe and replicates; the rollback is dirty and the return lane carries the write to the source; treated as clean with the source's replica covering the stop, the source's admission is covered clean-return, declares nothing, and the serving database lacks the target's write (INV-2 local at the final recovery, rev 7.12; rev 7.11 saw INV-15 at the declaration, rev 7.10 INV-2 on the serving database)", wDirtyReturn}, {"commit-before-open", "commit-before-open", "INV-5", "a public request reaches the target's edge while its probe runs; a row opened at the probe routes it before the commit (INV-5, R3-5)", wCommitBeforeOpen}, {"exec-admission", "exec-admission,hold-op-open,start-check-claim-gen,exec-writer", "INV-1", "one of four admission fences (J2-R2-8, claim rev 6.8.1): a paused open from an earlier operation makes the old source ready after the commit; hold_op refuses the open, the exec check refuses the wake, the generation check refuses the start, AdmitWriter refuses a box that is not op.exec; with all four gone the source's wake is a cold admission by a non-exec box into a fresh generation restored from its own region's old files, and it serves beside the target (INV-1; its installing CAS also moves holder.stamp under the target, INV-6 a step later)", wAdmissionTriple}, {"hold-op-open", "exec-admission,hold-op-open,start-check-claim-gen,exec-writer", "INV-1", "one of four admission fences (see exec-admission)", wAdmissionTriple}, {"start-check-claim-gen", "exec-admission,hold-op-open,start-check-claim-gen,exec-writer", "INV-1", "one of four admission fences (see exec-admission)", wAdmissionTriple}, {"exec-writer", "exec-admission,hold-op-open,start-check-claim-gen,exec-writer", "INV-1", "a paused open from an earlier operation lands after the commit while the source's row is still held; the source's AdmitWriter CAS requires op.exec to be the source, which it no longer is, and refuses (claim rev 6.8.1); with the three box-side fences gone as well, the non-exec source is admitted cold and two boxes run the host (INV-1)", wAdmissionTriple}, {"strict-spawn", "strict-spawn,evidence-whole-tree", "INV-1", "redundant alone: an escaped descendant is killed by the whole-tree cleanup; with evidence blind to escapees, a non-strict descendant survives the cut and writes beside the target (INV-1)", wStrictSpawn}, {"touched-incomplete", "touched-incomplete,legacy-discovery", "freed with residue", "redundant alone: discovery at adoption parks the other regions; without discovery, an incomplete touched set must park every region at delete, or a pre-release replica is residue after free (INV-10)", wTouchedIncomplete}, {"registration-check", "registration-check,fence-etag", "store of app", "a cheap extra: a creator paused across a whole purge resumes; the fence and the ETag condition refuse it without the re-read; with the ETag condition gone the re-read is what stops it", wRegistrationCheck}, {"registration-check", "registration-check,purge-claim-fence", "store of app", "the same, with the fence gone instead", wRegistrationCheck}, // rev 7.4 {"fence-by-installation", "fence-by-installation", "refused by the box's own installation record", "a round trip UK→US→UK (R3-3): the second landing replaces the retired marker UK wrote after the first move; a marker for the whole incarnation refuses the probe, the move back rolls back, and the instance never serves on UK again", wRoundTrip}, {"orphan-order", "orphan-order", "orphan cleanup deleted the record", "the cleanup reads the claim first and pauses; a create removes the orphan, claims and publishes; the cleanup reads that record, judges it by the stale claim and deletes it (R3-2)", wOrphanOrder}, {"sweep-namespace", "sweep-namespace", "residue never retired", "a replication PUT of incarnation 1 completes after 33 recreates dropped it from retired_incarnations; a sweep reading that list never finds it (R3-4)", wSweepNamespace}, {"recovery-current-inputs", "recovery-current-inputs", "stuck: source could not recover", "a bundle is published after admission and the target writes; the dirty recovery renders current inputs; gated on move.inputs it never passes its probe (R2-5, §7.8)", wRecoveryInputs}, // rev 7.5 {"fence-stamp", "fence-stamp,hostguard", "INV-6", "a config pass selected under the first installation pauses across a retire-and-reinstall (UK→US→UK) and a bundle change; the host guard's fresh check refuses its stale bundle, the stamp refuses its retired installation; with both gone it writes host state for a retired installation (R4-2)", wStaleWriter}, {"live-set-region", "live-set-region", "residue never retired", "a legacy host serving in UK with an earlier replica in US; discovery parks US; an old US replication PUT lands after; the live set is region-qualified, so the US sweep parks it; exempted by key alone it stays for good (R4-3)", wLiveSetRegion}, {"restore-overlap", "restore-overlap", "INV-3", "a generation's snapshot ends at TXID 11 and the only continuation is a compacted file [10,15]; litestream's planner takes it and restores through 15; rev 7.4's rule (min == current+1) discards it, the restore stops short of the certificate's max_txid, and the box never starts again (R4-1; since rev 7.10 the certified position is checked before the start, where rev 7.4's rule lost four acknowledged writes)", wRestoreOverlap}, {"restore-gap-closed", "restore-gap-closed", "INV-2 (cold restore)", "a generation's snapshot ends at TXID n, the file [n+1,n+1] is missing and [n+2,n+2] is current: a genuine gap; the restore refuses; returning what it has would wake the host without durable transactions (R4-1)", wRestoreGap}, // rev 7.6 {"restore-anchor", "restore-anchor", "INV-2", "a snapshot-only install (a push), then writes and replication, then the disk is lost: without the level-0 anchor litestream's position restarts at 1, the new files sit below the snapshot, and the cold restore loses the writes (R5-1; litestreamfacts TestFact_R5_1_*)", wSnapshotOnlyInstall}, {"root-advance", "root-advance", "INV-3 (witness): woken cold", "after a push, four compaction-and-snapshot rotations with retention; the disk is lost; a restore rooted at the pinned snapshot finds its continuation expired and refuses, while one rooted at the newest current successor snapshot succeeds (R5-3; litestreamfacts TestFact_R5_3_SnapshotRetention)", wRootAdvance}, // rev 7.7 {"anchor-acked", "anchor-acked", "before its anchor", "a push installs a snapshot alone and its anchor PUT is slow; litestream reads its position from the remote level-0 listing, so the host must not open replication until the anchor is acknowledged; opened at once it runs from TXID 1 below the snapshot and a cold restore loses the writes (R6-1)", wAnchorHeld}, {"return-stamp", "return-stamp", "issued for box", "a dirty rollback whose source lost its local stamp record; the return CAS writes the source installation's stamp back and the source re-initializes from it; left as the target's stamp, the source activates an installation that was never its own (claim rev 6.5, R6-4)", wReturnLostRecord}, // rev 7.8 {"recovery-generation", "recovery-generation", "INV-2", "writer A's level-0 upload [N+1] is in flight when A dies with its disk; B recovers cold into a fresh generation and replicates its own [N+1]; A's upload lands after B's; in the same generation it would replace B's file and the next cold restore loses B's acknowledged write (R7-1, completion order A after B)", wLateUploadAfter}, {"recovery-generation", "recovery-generation", "INV-2", "as above, but A's upload lands after B initialized its position and before B's own upload; in the same generation litestream's upload loop takes the remote [N+1] as already uploaded and skips B's, which is then lost (R7-1, the initialization/remote-position race)", wLateUploadRace}, {"recovery-generation", "recovery-generation", "INV-2", "A's in-flight write updated K and was declared lost with A's disk; B durably updates K; A's stale upload lands and restores K's old value; coverage by write identity sees B's write missing where a TXID bound and a per-key mask did not (R7-2)", wExemptKeyRestored}, {"recovery-generation", "recovery-generation", "no cold recovery", "a clean stop whose uploads all returned, then a crash before closed.json was written: no marker, so the next wake is a cold recovery into a fresh generation (claim rev 6.6 §6.4a)", wCrashBeforeMarker}, {"closed-marker", "closed-marker", "INV-2", "a stale closed.json (max_txid behind the remote maximum) beside a dead writer's in-flight upload; the stale marker forces a cold recovery; taken as intact, the box continues in place and the late upload replaces its file (claim rev 6.6 §6.4a, R7-1)", wStaleMarker}, {"close-waits", "close-waits", "before every upload returned", "a clean stop with an upload still in flight: closed.json is written only once the upload returned; written at once, the marker vouches for an upload that may still fail or land late (claim rev 6.6 §6.4a)", wCloseWaits}, {"newest-l0", "newest-l0", "newest level-0", "the local position runs ahead of the uploads; two compactions and snapshot rotations later, retention below the previous snapshot would remove the newest uploaded level-0 file, which litestream never does (R7-3)", wNewestL0}, {"evidence-whole-tree", "evidence-whole-tree", "INV-1", "an adopted legacy host runs a descendant outside the cgroup; the move's stop evidence must cover the whole tree, or the escaped descendant survives the cut and two boxes run the host (§6.1, J-D3)", wEvidenceWholeTree}, {"timer-freeze", "timer-freeze", "stuck", "the source has a registered timer; the move stops and holds it; the runner's refused deliveries while held must not advance its bookkeeping, or a clean rollback's digest check finds the timers changed and the source is stuck (J-N14)", wTimerFreeze}, // rev 7.9 {"writer-session", "writer-session", "INV-2", "a dead session's certificate, with a max_txid that still matches the remote maximum because the next writer's upload is in flight: the session moved forward when that writer was admitted, so the certificate authorizes nothing; taken by stamp and TXID alone it readmits a writer into the generation and the late upload replaces that writer's file (claim rev 6.8 §6.4a, R8-1)", wDeadSessionCertificate}, {"admit-everywhere", "admit-everywhere", "INV-2", "a committed move's target serves while the claim is still landing; it dies with its disk and an upload in flight; the next wake must be an AdmitWriter within the landing, a cold one into a fresh generation; gated for ordinary wakes only, the target continues the generation and the late upload replaces its file (claim rev 6.8 §6.4a, R8-2)", wCommittedLandingCrash}, {"admit-everywhere", "admit-everywhere", "INV-2", "a landing's probe dies with its disk and an upload in flight; the restarted probe must be a cold AdmitWriter within the landing, into a fresh install generation; gated for ordinary wakes only, the restarted probe reuses the generation and the late upload replaces its file (R8-2)", wProbeRestart}, {"valid-ltx", "valid-ltx", "INV-12", "a created incarnation's first wake is a cold admission into an empty generation with no LTX file, and a move of the still-empty incarnation installs nothing at position 0; the mutation installs a snapshot [1,0] and an anchor [0,0], files the pinned encoder refuses (R8-3)", wEmptyBootstrap}, // rev 7.10 {"remote-baseline", "remote-baseline", "INV-2", "a session closes cleanly through N+1 and its certificate stands; the box's local database is a cached copy through N (R9-1's clean-close variant); the next wake must purge it and restore the certified remote; keeping it serves a database without an acknowledged write, and its own upload for N+1 is skipped at the remote position (claim rev 6.9)", wStaleLocalAfterClose}, {"writes-lost", "writes-lost", "INV-2", "a writer acknowledges a write and crashes before uploading it; the next wake is cold and restores the remote, which lacks the write: the admission must record writes_lost {box, generation, session, remote_max_txid} and alert; silently, the serving database differs from the acknowledged writes (claim rev 6.9, R9-2)", wSilentLoss}, {"admit-bind-op", "admit-bind-op,claim-cas-opid", "INV-13", "a wake's admission closure is computed under serving (op.id \"\"); a delete begins, preserving session, generation and executor; the stale closure resumes: bound to the observed op.id, phase and kind it is refused; the model's general CAS condition on op.id (C2, claim-cas-opid) refuses it too, so the two must go together for a writer to be admitted into a host being deleted (claim rev 6.9, R9-4)", wStaleClosureDelete}, // rev 7.11 {"admit-before-start", "admit-before-start", "INV-2", "a background worker acknowledges a write right after the app starts, and the box crashes before replication opens; admitted before the start, the acknowledgement is the session's and the next cold admission declares it; admitted after readiness (rev 7.10's order), it is in a database the next warm admission purges silently (claim rev 6.10, R10-1)", wAckBeforeAdmission}, {"baseline-live", "baseline-live", "INV-2", "a cold admission into a fresh generation; the box crashes before the first upload, so the generation is empty and the marker names the predecessor; the predecessor is the unfinished admission's baseline and stays live until the marker names the new generation; with the retire chore queued at the CAS, the predecessor is parked and the recovery restores nothing (claim rev 6.10, R10-2)", wBaselineParked}, {"clean-return-identity", "clean-return-identity", "INV-16", "a move's target is probed and writes nothing; the rollback is clean and the seal recorded src_covered; the source's re-admission journals the target's writer as its predecessor and coverage clean-return, declaring nothing; the mutation journals the target's session and box with the source's generation, a writer that never was, and declares a loss (claim rev 6.12, R11-4)", wCleanReturnIdentity}, {"absent-marker-origin", "absent-marker-origin", "INV-2", "an adopted host's origin replica holds durable writes and no generation.json; a cold admission into a fresh generation crashes before its first upload; the ordinary serving-time sweep runs before the recovery; with the absent marker read as the origin the chain protects it, and under the mutation (rev 7.11's sweep, which read absence as agreement) the sweep parks the origin and the recovery restores nothing (R11-1; isolated from baseline-live in rev 7.13, R12 evidence)", wOriginSwept}, {"session-scoped-loss", "session-scoped-loss", "INV-18", "two writer sessions of one box each acknowledged a write that never uploaded; a writes_lost record for the second session exempts only its own write; matched box-wide (rev 7.12), the record absolves the first session's undeclared write too (R12-1)", wTwoSessionDeclaration}, {"foreign-region-uncovered", "foreign-region-uncovered", "INV-2", "a landing's probe publishes the target's generation; the source's generation, in another region, stays uncovered with no chore; a chore queued into the source's region from here parks the rollback's baseline within the horizon, and the clean rollback's return restores an empty database (claim rev 6.14 item 5, R12-3)", wRollbackBaselinePreserved}, {"cover-at-park", "cover-at-park", "INV-17", "a committed move: the CAS that queues the source region's whole-location park covers the target's record, whose predecessor is the source's generation there; without CoverRegionPredecessors the record stays uncovered after the park retired its predecessor (claim rev 6.14 item 6, R12-3)", wCommitCoverage}, {"cover-at-park", "cover-at-park", "INV-17", "the commit is interrupted between the record's flip and the claim's CAS: every actor pauses past the horizon; whoever follows the record later performs the one CAS, parks and coverage together (R12-3, interruption)", wCommitInterrupted}, {"cover-at-park", "cover-at-park", "INV-17", "the commit's CAS is followed again by another reader: the replay is refused, the park is queued once and the coverage stands (R12-3, replay)", wCommitReplayed}, {"persisted-park-scope", "persisted-park-scope", "INV-9", "a committed move's source-region park binds its scope, the original evidence time, in the claim; the region's agent restarts mid-park; with the box-local evidence map (rev 7.13) the horizon starts again from the restart and the acknowledgement comes late (claim rev 6.15 §2, R13-4)", wParkScopeSurvivesRestart}, {"persisted-park-scope", "persisted-park-scope", "INV-9", "a committed move's staging lane sealed at the cut: its persisted bound is the seal's, deadline seal + lease + H; the target region's cleanup first runs 40 steps after that deadline and its agent restarts as it begins; the acknowledgement must follow at once, since the persisted deadline has passed; bound at cleanup's own clock (rev 7.15) the chore waits a fresh horizon (claim rev 6.23 §2, R15-1)", wStagingScopeDeadline}, {"scope-membership", "scope-membership", "INV-23", "incarnation 2 serves after incarnation 1 was deleted; a late object lands under instances//1/g-old/; the sweep must queue a chore scoped to instances//1 with archive incarnation 1 and park within it; rev 7.16's sweep scoped the whole prefix as instances/ under incarnation 2 and archived the child incarnation's object from there (claim rev 6.24 §2, R16-2)", wSweepScopeMembership}, {"holderless-park", "holderless-park", "INV-20", "a deleted host's region keeps late residue; the free host's sweep runs as a holderless parking op and a create requested meanwhile waits for FreeAfterPark; with bare chores on the free claim (rev 7.13) the create claims the host over the outstanding park (claim rev 6.15 §6.2a, R13-4)", wFreeSweepVsCreate}, {"covered-baseline-refused", "covered-baseline-refused", "INV-2", "an unfinished run whose link in this region is covered and whose generation was retired; the walk refuses the start and alerts; reading objects alone (rev 7.13) it passes over the empty link and restores the marker's retired generation as an empty database (claim rev 6.22 §6.2a, R13-1)", wCoveredLocalBaseline}, {"restore-selected-baseline", "restore-selected-baseline", "INV-3", "the marker names S; R issues its first upload and crashes while it is pending; an empty successor R2 is admitted and crashes before uploading; R's delayed upload lands; the next start selects R from R2 → R → S and must restore it rooted at [1, 1]; restoring through the marker, which names S, refuses it and the valid recovery stalls (R14-1)", wIntermediateBaseline}, {"unique-declarations", "unique-declarations", "INV-21", "the target is destroyed after the flip and before its first admission, src_covered is false and the source's cut session is uncertified; the return's admission must declare that session once; rev 7.14's separate source-cut path declared it twice, through writes_lost and again beside it (R14-2)", wNoDuplicateDeclarationEarly}, {"unique-declarations", "unique-declarations", "INV-21", "the same with the target lost after its probe was admitted: the predecessor is the target's probe session, the list carries the source's cut session once and no target session twice (R14-2)", wNoDuplicateDeclarationLate}, {"probe-window", "probe-window", "INV-19", "a landing probe's launch environment is ready exactly at the 30-step deadline; the deadline is checked before the start, so the attempt fails and a fresh admission follows; unchecked, the expired attempt starts, answers readiness and becomes the probed writer (R12-2)", wProbeWindowAt}, {"seal-return", "seal-return", "INV-15", "the source acknowledges a write whose upload is still in flight when the cut stops it: the seal carries the write, the source's replica does not; the landing is rolled back before its probe; the return must carry the seal, and treated as clean the source's cold admission declares the write lost while the landing's built generation holds it (rev 7.11 §7.8)", wSealReturn}, {"close-evidence", "close-evidence", "certificate while", "a fresh generation's first upload is held past the client's timeout and its retry lands; the session's clean stop must write no certificate (R10-7)", wFirstUploadRetry}, {"close-evidence", "close-evidence", "certificate while", "a warm admission's anchor PUT is held past the client's timeout and its retry lands; the session's clean stop must write no certificate (R10-7)", wAnchorRetry}, {"close-evidence", "close-evidence", "certificate while", "a compaction's level-1 PUT is held past the client's timeout; the next compaction pass retries and lands; the original completes afterwards; the session's clean stop must write no certificate, since a request of its lifetime was retried after a timeout; looking at the level-0 queue alone it certifies (R9-5)", wMaintenanceRetry}, {"close-evidence", "close-evidence", "certificate while", "a snapshot PUT completes on the server after the client gave up on it, a lost response; the client never observed success, so the session must stay uncertain and certify nothing; counting server completion it certifies (R9-5)", wLostResponse}, {"close-evidence", "close-evidence", "certificate while", "an upload times out and its retry succeeds while the original stays unresolved; the writer's clean close must write no certificate, because a request of its lifetime is unaccounted for; looking at the level-0 queue alone it certifies (claim rev 6.8 §6.4a, R8-5)", wRetryUnresolved}, {"build-completion", "build-completion", "INV-2", "a push's build with its snapshot, then its anchor, held, the agent crashing in between each; since rev 7.11 the marker is the admission's, so a build completed from its intent gives the probe nothing to restore from its pinned snapshot, and the next session restores an empty generation (INV-2); rev 7.10 caught it at the marker (INV-11)", wBuildCrashes}, // region HA, two boxes per region (L18; plan 2026-10-07-region-ha-hostlife-two-box rev 2) {"reloc-release-first", "reloc-release-first", "INV-1", "a drain: the target's worker pins while the source still runs the host, and the target's probe starts beside it", wRelocReleaseFirst}, {"reloc-install-receipt", "reloc-install-receipt,reloc-ensure-local", "INV-4", "the target is terminated at installed, after its receipt; its replacement inherits the receipt and skips its local install, and with EnsureLocal gone too (it restores the install otherwise: 1b-next rev 14's 'each covers the other') it starts over data sealed with the old key", wRelocInstallReceipt}, {"reloc-no-reinstall", "reloc-no-reinstall", "acknowledged timer", "the first probe admitted P and registered a timer; the agent restarts and re-applies the pinned wake state over it", wRelocNoReinstall}, {"reloc-released-coverage", "reloc-released-coverage", "INV-2", "a failover: the executor is terminated with an acknowledged write whose upload is still in flight; the first admission of P takes released coverage and the write is neither restored nor declared", wRelocReleasedCoverage}, {"reloc-source-loss", "reloc-source-loss", "INV-2", "a drain whose source is terminated in releasing before its release is journaled, with an unuploaded write; taken as released at what the remote holds, the write goes undeclared", wRelocSourceLoss}, {"reloc-row-cases", "reloc-row-cases,exec-admission,exec-writer", "INV-6", "a stale edges file: after the source's release a paused duplicate open makes its row ready again; reconcile holds it, and with the row case, the exec check and AdmitWriter's op.exec check gone a request admits the released source as a writer, and the stamp its admission issued is activated under the target (INV-6). Since L18 finding 2 no relocating phase admits a non-probe writer, so the admission lands just after the completion, and the target's cold first serving wake activates it (joint round 2 finding 1)", wRelocRowCases}, {"fence-discharge-qualified", "fence-discharge-qualified", "INV-26", "a terminated box with a volume that was not DeleteOnTermination has its park-local chores discharged automatically", wFenceDischargeQualified}, {"fence-declares-timers", "fence-declares-timers", "acknowledged timer", "the executor registers a timer whose manifest never lands and is terminated; the fence drops the timer silently", wFenceDeclaresTimers}, {"reloc-enrolled-only", "reloc-enrolled-only", "INV-27", "the only other box of the region holds no key and a replacement has launched unenrolled; the failover names the unenrolled reference", wRelocEnrolledOnly}, {"files-live-set", "files-live-set", "INV-30", "the chain's live manifest is the origin generation's, which a cold admission superseded without publishing (nothing changed: 1b-next rev 12's unchanged file); the origin's park-generation archives it, and the failover finds no manifest carrying instance.key: stuck, never served (rev 3: 1b-next ruling 25 makes the loss fail safe; with files-pin-needs-key also gone it is INV-4)", wFilesLiveSet}, {"reloc-pin-claim-gen", "reloc-pin-claim-gen", "INV-3", "a pinner observed the first round after the source's release and stalled; after the target wrote into P and died, its stale selection of generation_from is journaled for the nested pinning, and the build waits forever for objects generation_from's own park retired", wRelocPinClaimGen}, {"reloc-release-deadline", "reloc-release-deadline", "INV-3", "a drain whose source can never flush: with the deadline the operation is stuck and the operator's resolve returns the host to the source; without it the drain waits forever", wRelocReleaseDeadline}, {"reloc-ensure-local", "reloc-ensure-local", "INV-4", "the target freezes past its lease after its receipt; the scoped cleanup retires the unopened local install, and without EnsureLocal P's first admission starts over data sealed with a key no files directory carries", wRelocEnsureLocal}, {"reloc-verify-receipt", "reloc-verify-receipt", "INV-4", "after P opened the target's volume is replaced and its agent restarts; without VerifyReceipt the next attempt is admitted with no install and starts over data sealed with the old key", wRelocVerifyReceipt}, {"reloc-prepared-opened-journal", "reloc-prepared-opened-journal", "acknowledged timer", "P opened, a timer registered, a second attempt admitted, and P's admission trimmed from holder.admissions; read from the list alone, P looks unopened after the next restart and the local install is remade over the timer", wRelocPreparedOpenedJournal}, {"fence-reassigns-regional", "fence-reassigns-regional", "INV-3", "the terminated executor owns a park-generation chore in the legacy box: form; without the reassignment nothing ever runs it", wFenceReassignsRegional}, {"reloc-replace-not-owing", "reloc-replace-not-owing", "INV-3", "the only spare owes a park-local for the host when the target dies at installing; named anyway, its pending retirement retires the new installation's stamp under it, and the operation never converges", wRelocReplaceNotOwing}, {"reloc-exhausted-fence", "reloc-exhausted-fence", "INV-1", "three targets die while the live source is still op.exec in starting; with rev 8's exhausted fence op.exec goes to none, the operator's replay installs a spare, and it runs beside the source", wRelocExhaustedFence}, {"reloc-pin-evidenced-empty", "reloc-pin-evidenced-empty", "INV-2", "a failover whose listing finds nothing although the writes are durable: with the rule the operation is stuck until an operator resolves it on a listing that shows them; without it the pin is empty and the install loses the durable writes", wRelocPinEvidencedEmpty}, {"files-prepared-seq-zero", "files-prepared-seq-zero", "INV-28", "the source's manifests reach sequence 3; P's prepared manifest keeps 3, the probe session publishes its timer at 1, and the nested failover pins and declares from the stale prepared manifest", wFilesPreparedSeqZero}, // rev 3: 1b-next rev 17 to 19's fixes for the model's findings, and the L21 window // rev 4: Astra's round 1 and claim §11's additional witnesses {"files-objects-region-bound", "files-objects-region-bound", "INV-3", "claim §11: the host moves to region 1 with a file unchanged since region 0 published it, the source region is cleaned up, then the target dies; the failover pins an object in region 1's bucket, or, without the region binding, can never pin region 0's", wMoveUnchangedFile}, {"files-origins-referenced", "files-origins-referenced", "INV-3", "R11-1: a file unchanged through ten cold admissions, holder.admissions trimmed past its origin; the failover pins the origin's object, or, authorized from the trimmed list, is refused for ever", wOriginsAfterTrim}, {"reloc-clear-after-cleanup", "reloc-clear-after-cleanup", "INV-29", "claim §11: the former source's scoped cleanup fails after the drain; its controller record stays and root refuses an executable update until the cleanup succeeds; without the rule the update runs over the unfinished cleanup", wClearAfterCleanup}, {"fence-converts-committed-landing", "fence-converts-committed-landing", "INV-3", "claim §11, F5: the record commits a landing and its target dies before the claim follows; the fence makes it a failover in the target's region, or nothing ever finishes it", wCommittedLandingTargetLost}, {"files-live-set-moves-parks", "files-live-set-moves-parks", "INV-30", "F4: a push parks the whole location; the files live set survives, so the later failover pins the live object, or can never pin the host's files", wPushKeepsLiveFiles}, {"files-pin-needs-key", "files-pin-needs-key", "INV-4", "L21, explicit: the pre-start manifest copy landed without instance.key, the app minted the key after starting and replicated rows sealed with it, and the box died before the keyed manifest landed; with the rule recovery is stuck and installs nothing, without it the keyless pin installs a fresh key over the sealed rows", wL21Window}, {"reloc-no-spare-bound", "reloc-no-spare-bound", "INV-3", "F1: a drain's target fails its probe in a two-box region with no spare; with the bound the operation is stuck and the operator's resolve returns the host to the source, without it it waits for ever", wNoSpareBound}, {"reloc-dead-target-bound", "reloc-dead-target-bound", "INV-3", "rev 18 finding 2: the target dies at installing and no spare is launched; with the bound the fence is consumed into stuck and the operator's replay serves on the source, without it nothing moves", wDeadTargetBound}, // the final review's fixes {"park-evidence-every-box", "park-evidence-every-box", "freed with residue", "two-box seed 819: a delete's regional park-replica is run by the writer's sibling while the writer's replicator still runs; with the rule it waits for the writer's own stop evidence, without it the region is parked and the writer's next shipment is residue when the host is freed (INV-10)", wParkEvidenceEveryBox}, // joint round 1 {"files-live-region", "files-live-region", "residue never retired", "joint round 1 finding 1: the source's manifest PUT is held while the host moves to region 1 and region 0 is cleaned up, then lands in region 0; the files live set is region-qualified, so the at-rest sweep retires it there; read in every region, the chain's newest manifest protects itself and is never retired (INV-10)", wLateManifestAfterMove}, {"files-home-move-phases", "files-home-move-phases", "INV-30", "joint round 1 review I1: a park-generation the source's restart queues during a move runs in the move's stopped phase, op.exec none; region 0 is still authoritative (moves §5.1), so the live manifest survives and the failover the source's termination converts the move into pins it and serves; with the files home read from op.exec alone it is archived and the failover is stuck for ever (INV-3)", wMoveStoppedKeepsLiveFiles}, {"files-home-move-phases", "files-home-move-phases", "INV-30", "Astra joint round 2: the same park waits until the target's probe is admitted, runs before the commit, and the landing rolls back cleanly; the source region stays the files home until the commit, so the source's failover after the return pins the keyed manifest and serves; home only until the probe's admission, or never, it is archived and the failover is stuck for ever (INV-3)", wRollbackKeepsSourceFiles}, // L18 joint round findings 2 and 3 (regionha_completion_witness_test.go) {"reloc-probe-stop", "reloc-probe-stop", "INV-31", "a drain completes: the probe's session is stopped with root's receipt before the serving CAS, and the host wakes on the target afterwards; completed over the running probe, its session outlives the kind change on a box whose participation is not discharged", wProbeStopBeforeServing}, {"reloc-probe-fence-owner", "reloc-probe-fence-owner", "INV-32", "another operation fences the host on the target after its probe passed: the probe stop refuses with nothing stopped and ruling 67 makes the relocation stuck; installed over that fence, the stop later lifts it as its own and the serving wake starts the host under it", wProbeStopMeetsAnotherFence}, {"reloc-probe-fence-owner", "reloc-probe-fence-owner", "INV-32", "a crash: the target's agent restarts while the discharge fails, emptying the activator's fences, and another operation fences the host; the completion lifts only its own fence and the serving wake waits; lifting any fence opens the host under the other", wLiftAfterRestartMeetsAnotherFence}, {"reloc-completion-discharge-first", "reloc-completion-discharge-first", "INV-31", "C10's discharge fails for thirty steps: the hold and the fence stay and no wake moves the holder; then it succeeds, the agent crashes after the hold's release, and the next pass resumes and marks; with the hold released and the fence lifted first, a request admits a writer before the discharge", wDischargeFailsHoldsTheRow}, {"reloc-completion-mark-last", "reloc-completion-mark-last", "INV-31", "the discharge fails and a drain from the completion box is asked for: with the mark last the barrier refuses it until the discharge succeeds; marked first, the drain names the box while its participation is still the completed op's, and the discharge is never retried", wMarkLastAfterAFailedDischarge}, {"reloc-completion-from-claim", "reloc-completion-from-claim", "INV-3", "the mark fails once after the hold's release and the lift, and a second completion crashes after the lift: each next pass finds the unmarked completion from the claim and marks it; found from the row's hold, which the release removed, it is never marked and nothing starts from the host again", wFailedMarkRetriedFromTheClaim}, {"reloc-completion-barrier", "reloc-completion-barrier", "INV-31", "while the completion's discharge fails a drain, a move and a push from the completion box are refused; once marked the drain starts and completes; without the barrier the drain names the box while its participation is still the completed op's", wSuccessorWaitsForTheDischarge}, {"reloc-completion-claim-mode", "reloc-completion-claim-mode", "INV-3", "ruling 82: the discharge fails, region HA is turned off and the target's agent restarts; the completion-only pass still discharges, releases, lifts and marks, and the host serves; run with region HA on only, the completion never finishes", wCompletionWithRegionHAOff}, {"reloc-completed-handover", "reloc-completed-handover", "INV-3", "N6: the first serving wake after the completion hands over from the probe's receipt and the host runs; routed to main's stop, its serving-shaped fence replaces the probe's and the handover refuses for good", wServingWakeHandsOver}, {"reloc-completed-catchup-hold", "reloc-completed-catchup-hold", "INV-33", "finding 3, ruling 85: the source releases, its reconcile is delayed until the target completed, and its next reconcile holds its row for the completed op until its park-local retires it; without the catch-up hold the row its release left ready stays ready", wDelayedSourceHoldsItsRow}, {"reloc-probe-stop-flush", "reloc-probe-stop-flush", "INV-34", "ruling 87: the probe session acknowledges a write its replicator has not shipped; the probe stop flushes it before root's stop, so the first serving wake, cold, declares nothing the probe session acknowledged; stopped with nothing flushed, that wake declares the write lost", wProbeStopFlushes}, {"dirty-return-needs-admission", "dirty-return-needs-admission", "INV-30", "Astra joint round 4: the source's unreplicated write makes the seal src_covered false and the target stalls before its probe, so the landing rolls back dirty with no target admission; the source keeps the files home and its install parks nothing; without the admission check the install park retires the manifest the source's next install would pin", wDirtyReturnWithoutAdmission}, {"reloc-completion-fenced-exempt", "reloc-completion-fenced-exempt", "INV-3", "ruling 86, seed 2224: a purge closes the app's admission and the completion box is terminated before its discharge; once its fence record exists the purge verifies it, starts over the unmarked completion and frees the host; without the exemption the barrier refuses the purge and the closed admission the failover, for ever", wPurgeOverAFencedCompletionBox}, } // TestWitnesses is the deterministic half of the mutation evidence. // // With no mutation (the gate) it proves every witness's claim in full: // the scenario holds with every rule in place, holds under every proper // subset of its stated mutation set (so a rule a combination names is // shown necessary, not assumed), and under the whole set violates the // failure the scenario names, not merely some invariant. // // Under HOSTLIFE_MUTATE=m (the harness) it runs the witnesses of the // rules in m and reports each as violated or held; a witness whose set is // within m must violate with its named failure, or the test fails (the // witness is broken, not the rule). HOSTLIFE_WITNESS=rule runs one rule's // witnesses with their trace. func TestWitnesses(t *testing.T) { only := os.Getenv("HOSTLIFE_WITNESS") if mutated == "" { ran := 0 for _, x := range witnesses { if only != "" && x.rule != only { continue } ran++ check(t, x, "", false, only != "") for _, s := range properSubsets(x.needs) { check(t, x, s, false, only != "") } check(t, x, x.needs, true, only != "") } if only != "" && ran == 0 { t.Fatalf("no witness for rule %q", only) } return } set := mutationSet(mutated) for _, x := range witnesses { if only != "" && x.rule != only { continue } if !set[x.rule] { continue } needs := true for _, m := range strings.Split(x.needs, ",") { if !set[m] { needs = false } } if needs { check(t, x, mutated, true, only != "") continue } // the mutation set is not the witness's: report, enforce nothing. // A wider combination may well violate it (the whole start check // in place of its generation clause, either registration-check // partner); the proper-subset proofs live in the gate report(t, x, mutated, only != "") } } func report(t *testing.T, x witness, m string, trace bool) { saved := mutated mutated = m defer func() { mutated = saved }() w := newWitness() x.run(t, w) tag := "held" if len(w.violations) > 0 { tag = "violated: " + w.violations[0] } t.Logf("witness %s under %q (needs %q): %s", x.rule, m, x.needs, tag) if trace { dump(t, w) } } // check runs one witness under mutation m, reports it, and fails the // test if the outcome is not the stated one: held when no violation is // expected, the named failure when one is. func check(t *testing.T, x witness, m string, expectViolation bool, trace bool) { saved := mutated mutated = m defer func() { mutated = saved }() w := newWitness() x.run(t, w) violated := len(w.violations) > 0 tag := "held" if violated { tag = "violated: " + w.violations[0] } t.Logf("witness %s under %q (needs %q): %s", x.rule, m, x.needs, tag) switch { case expectViolation && !violated: t.Errorf("witness %s held under %q, which it must violate", x.rule, m) dump(t, w) case expectViolation && !namedFailure(w.violations[0], x.want): t.Errorf("witness %s under %q violated, but not its named failure %q", x.rule, m, x.want) dump(t, w) case !expectViolation && violated: t.Errorf("witness %s violated under %q, where it must hold", x.rule, m) dump(t, w) } if trace { dump(t, w) } } // namedFailure: the violation names the witness's failure. want is one // failure or several separated by "|" (any of them); a failure that ends // in a digit must not run on into another (INV-3 is not INV-30). func namedFailure(v, want string) bool { for _, f := range strings.Split(want, "|") { for i := 0; ; { j := strings.Index(v[i:], f) if j < 0 { break } end := i + j + len(f) last := f[len(f)-1] if !(last >= '0' && last <= '9') || end == len(v) || v[end] < '0' || v[end] > '9' { return true } i = i + j + 1 } } return false } func mutationSet(m string) map[string]bool { set := map[string]bool{} for _, x := range strings.Split(m, ",") { if x != "" { set[x] = true } } return set } // properSubsets: every non-empty proper subset of a comma-separated set. func properSubsets(needs string) []string { xs := strings.Split(needs, ",") var out []string for mask := 1; mask < (1< w.nextInc { w.nextInc = inc } w.serial++ n := &claim{Ver: 1} if w.claim != nil { n = w.claim.clone() n.Ver++ } n.Holder = &holder{Inc: inc, App: app, Serial: w.serial, Location: loc, Stamp: n.Ver, Session: n.Ver, WriterBox: b.ID} // the serving CAS wrote holder.stamp; one writer session so far n.Op = opState{Kind: "serving", Exec: b.ID, Parts: []int{b.ID}} n.Regions, n.Boxes, n.Complete, n.Obl = []int{b.Region}, []int{b.ID}, true, nil w.claim = n for i := range w.acks { if w.acks[i].Session == -1 { w.acks[i].Session = n.Holder.Session // the one writer session so far acknowledged them } } db.Session = n.Holder.Session w.rec = &record{Ver: w.newVer(), Inc: inc, App: app, Region: b.Region} b.Row = &row{Inc: inc, App: app, Status: "ready"} b.DB = db b.Files = &filesDir{Inc: inc, Key: key, Env: key, Done: true} b.Config, b.CfgVer, b.Live, b.LiveInc = inc, w.cfgVer[app], app, inc b.install(inc, n.Ver) // the create's installation stamp, initialized from holder.stamp db.Stamp = n.Ver bl := w.deltaOf(db, inc) db.Pos, db.Pending = 1, nil k := ltxKey(loc, "", 0, bl.Min, bl.Max) w.buckets[b.Region].objs[k] = append(w.buckets[b.Region].objs[k], &version{ID: w.newVer(), B: bl}) w.markDurable(k, bl) // the generation is intact: its last writer session closed cleanly at // position 1 on this box (claim rev 6.8 §6.4a) w.buckets[b.Region].objs[closedKey(loc, "", n.Ver)] = []*version{{ID: w.newVer(), B: &blob{Kind: "closed", Inc: inc, Stamp: n.Ver, Seq: b.ID, Session: n.Ver, TX: 1}}} w.logf("witness: inc %d of app %s serving on box %d", inc, app, b.ID) } // legacy installs a pre-release host: an untagged replica in region r0 // where it serves with no claim, and a replica an earlier move left in r1. func (w *world) legacy(b *box, other int) { w.nextInc++ inc := w.nextInc w.rec = &record{Ver: w.newVer(), Inc: inc, App: app0, Region: b.Region} w.legacyIncs[inc] = true key := 7 b.Row = &row{Inc: inc, App: app0, Status: "ready"} b.DB = &localDB{Inc: inc, Loc: locationFor(inc, true), Key: key, State: map[string]int{}, Epoch: b.Epoch} for i := 0; i < 2; i++ { w.nextW++ w.acks = append(w.acks, ack{W: w.nextW, Inc: inc, Box: b.ID, Session: 0, At: w.now, Kind: "write"}) // the pre-release writer: the legacy identity, session 0 (claim rev 6.24) w.writeInc[w.nextW] = inc w.commit(b.DB, w.nextW) } b.DB.Session = 0 b.Files = &filesDir{Inc: inc, Key: key, Env: 1, Done: true} b.Config, b.CfgVer, b.Live, b.LiveInc = inc, 1, app0, inc full := w.deltaOf(b.DB, 0) b.DB.Pos, b.DB.Pending = 1, nil k := ltxKey(b.DB.Loc, "", 0, 1, 1) w.buckets[b.Region].objs[k] = []*version{{ID: w.newVer(), B: full}} w.markDurable(k, full) // the pre-release writer closed cleanly on this box (a fixture for a // warm first wake; the real pre-release writer leaves no certificate, // so a real first wake is cold); adoption's stamp is 1 and the legacy // identity's session 0 (claim rev 6.24) w.buckets[b.Region].objs[closedKey(b.DB.Loc, "", 0)] = []*version{{ID: w.newVer(), B: &blob{Kind: "closed", Inc: inc, Stamp: 1, Seq: b.ID, Session: 0, TX: 1}}} first := w.txs[b.DB.Log[0]] part := &blob{Kind: "ltx", Level: 0, Min: 1, Max: 1, Inc: 0, SealKey: key, Pages: map[string]int{first.Key: first.Val}, TXs: []int{first.W}} w.buckets[other].objs[ltxKey(b.DB.Loc, "", 0, 1, 1)] = []*version{{ID: w.newVer(), B: part}} } // ---------- the schedule ---------- // tick is one step of the witness's own schedule: time, S3 completions, // paused goroutines, then the actors the witness names, then the per-step // invariants. func (w *world) tick(actors ...func()) { w.now++ w.completeDue(false) if p := w.recPend; p != nil && p.at <= w.now { w.recPend = nil if w.rec == nil { w.rec = p.rec } } w.runStalled() if w.perRegion > 1 { w.twoBoxStep() // replacements launch and enroll, the publisher runs; the quiet source terminates and drains nothing } for _, a := range actors { a() } w.checkStep() } // drive ticks until done, a violation, or max steps. func (w *world) drive(max int, done func() bool, actors ...func()) bool { for i := 0; i < max; i++ { if done() { return true } w.tick(actors...) if len(w.violations) > 0 { return false } } return done() } // reach drives to a milestone the scenario needs. Not reaching it, with no // violation to explain why, is a liveness failure and is recorded as one // (INV-3), so a mutation that leaves the protocol stuck counts as caught // and an unmutated scenario that stalls fails the test. func (w *world) reach(t *testing.T, max int, what string, done func() bool, actors ...func()) bool { if w.drive(max, done, actors...) { w.logf("witness: reached %s", what) return true } if len(w.violations) == 0 { w.violate("INV-3 (witness): %s not reached within %d steps: %s", what, max, w.state()) } return false } // finish drives to quiescence and runs the final oracle, as runSeed does. func (w *world) finish(t *testing.T) { w.drive(2000, w.quiescent, w.actAll(), w.runConsole, w.recoveryPass, w.operator) if len(w.violations) > 0 { return } w.completeDue(true) w.final() } func (w *world) act(bs ...*box) func() { return func() { for _, b := range bs { w.worker(b) w.obligationRunner(b) w.reconcile(b) } } } // actAll runs every live box, replacements included: its worker, // obligation runner and reconcile, and the config-sync and adoption // passes a serving row needs before the host is at rest. func (w *world) actAll() func() { return func() { for _, b := range w.liveBoxes() { w.worker(b) w.obligationRunner(b) w.reconcile(b) if len(b.plans) == 0 { w.passPlan(b, "config") w.passPlan(b, "adopt") } w.passExec(b) } } } // runConsole runs one step of every console plan, in order: a // deterministic consoleStep. func (w *world) runConsole() { w.runPlans(nil) } // runPlans runs one step of every console plan but skip. A plan may add // another (a create's orphan cleanup); the new one is kept for the next // step. func (w *world) runPlans(skip *consolePlan) { plans := append([]*consolePlan(nil), w.console...) done := map[*consolePlan]bool{} for _, p := range plans { if p == skip || p.Stall > w.now { continue } if w.runPlan(p) { done[p] = true } } var keep []*consolePlan for _, p := range w.console { if !done[p] { keep = append(keep, p) } } w.console = keep } // stop is the cloud stopping a box: destroyed, nothing on it runs. func (w *world) stop(b *box) { b.Destroyed, b.Procs = true, nil w.logf("witness: box %d stopped", b.ID) } // appWrite is one acknowledged application write by b's main process. func (w *world) appWrite(b *box) int { if !hasMain(b) { panic("appWrite: no main process") } p := b.Procs[0] w.nextW++ wr := w.nextW if b.DB != nil && b.DB.Inc == p.Inc { w.commit(b.DB, wr) } else { w.txs[wr] = tx{W: wr} } sess, gen := w.sessionOf(b) w.acks = append(w.acks, ack{W: wr, Inc: p.Inc, Box: b.ID, Session: sess, Gen: gen, At: w.now, Kind: "write"}) w.writeInc[wr] = p.Inc w.logf("witness: box %d wrote %d", b.ID, wr) return wr } // holdKey makes the witness hold every request for key, or under a prefix // ending in "/", until completeHeld. func (w *world) holdKey(key string) { w.hold = func(r *request) bool { return r.key == key || strings.HasSuffix(key, "/") && strings.HasPrefix(r.key, key) } } // completeHeld completes the requests the witness held for key (or // prefix), now. func (w *world) completeHeld(key string) int { n := 0 var keep []*request for _, r := range w.pending { if (r.key == key || strings.HasSuffix(key, "/") && strings.HasPrefix(r.key, key)) && r.doneAt == 1<<30 { r.doneAt = w.now // the response arrives now (the close's evidence reads the completion time, R9-5) if w.now-r.at > horizonH { r.beyond = true // a completion past the horizon: the sweep's, as the biased schedule's are (§6.4) } w.complete(r) w.logf("witness: held %v %s r%d completes now", r.kind, r.key, r.region) n++ continue } keep = append(keep, r) } w.pending = keep return n } func (w *world) oblOpen(region int, prefix string) bool { if w.claim == nil { return false } for _, o := range w.claim.Obl { if o.Region == region && o.Prefix == prefix { return true } } return false } // landProbed drives a move of the serving host to tgt until the landing's // probe has passed and the instance runs on tgt, before the settle window // ends. func (w *world) landProbed(t *testing.T, src, tgt *box) { w.moveTo(tgt.Region) if w.claim.Op.Kind != "moving" { t.Fatalf("witness: move not started: %s", w.state()) } w.reach(t, 600, "landing probed", func() bool { c := w.claim return c.Op.Kind == "landing" && c.Op.LandPhase == "probed" && hasMain(tgt) }, w.act(src, tgt), w.recoveryPass) } // ---------- the scenarios ---------- // wGenerationConditional (model 29, §5.1): push p1's first generation.json // PUT is accepted but its response is lost; the agent publishes again and // p1 completes. Push p2 completes. Then the stale PUT lands. Conditional on // the marker it superseded, it is refused (412); unconditional, the marker // names p1 while the claim names p2, and the serving box cannot start. func wGenerationConditional(t *testing.T, w *world) { e := w.boxes[0] w.serve(e, 1, app0) loc := w.claim.Holder.Location push := func(holdMarker bool) { // the previous push's publication queued the predecessor's // park-generation chore (claim rev 6.14 item 5: a prepared // generation publishes too); an obligation in the region blocks a // new operation until it runs (rule obligations-block-ops) w.reach(t, 400, "obligations clear", func() bool { return len(w.claim.Obl) == 0 }, w.act(e)) w.userPush() id := w.claim.Op.ID if !w.reach(t, 400, "push "+id+" probing", func() bool { return w.claim.Op.ID == id && w.claim.Op.Phase == "probing" }, w.act(e)) { return } if holdMarker { // the probe's cold admission publishes generation.json for the // prepared generation (rev 7.10): accepted, response lost; the // writer does not start, and the next attempt publishes again w.holdKey(genMarkerKey(loc)) w.tick(w.act(e)) w.hold = nil } w.reach(t, 400, "push "+id+" released", func() bool { return w.claim.Op.Kind == "serving" }, w.act(e)) w.idleStop(e) } push(true) push(false) if len(w.violations) > 0 { return } if w.completeHeld(genMarkerKey(loc)) != 1 { t.Fatalf("witness: no held marker PUT") } w.finish(t) } // wLostReturnPark (model 27, §7.10). func wLostReturnPark(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) w.appWrite(tgt) // real work in the settle window w.rollback(w.claim, "settle check failed") w.reach(t, 50, "target released dirty", func() bool { c := w.claim return c.Op.Kind == "restoring" && c.Op.Phase == "released" && c.Op.Dirty }, w.act(src, tgt), w.recoveryPass) w.tick(w.act(tgt)) // the first return PUT: moves///db in the source region if w.claim.Op.ReturnDB.Ver == 0 { t.Fatalf("witness: the return did not begin: %s", w.state()) } w.stop(tgt) // the cloud stops the target mid-return w.reach(t, 20, "declared lost", func() bool { return contains(w.claim.Lost, tgt.ID) }, w.operator) w.replaceDestroyed() w.finish(t) } // wFenceConvertsMoving (moves rev 7.20 §7.10, claim rev 6.28 §4): the // source of a move that has not flipped is terminated, in a one-box // region. The termination fence converts the move to relocating at // pinning: exec none, the stamp and generation kept, the lane's park owed // to the target region. No box exists in the source region, so the // relocation holds there, safely (no writer, the data pinned), the // operator is told once, and the claim does not churn. Once region HA // enrolls a replacement box (the model's replacement mechanism), the // relocation completes on it and the host serves again in its region. func wFenceConvertsMoving(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.moveTo(tgt.Region) w.reach(t, 100, "staging begins", func() bool { c := w.claim return c.Op.Kind == "moving" && c.Op.Phase == "preparing" && contains(c.Regions, tgt.Region) }, w.act(src, tgt)) w.stop(src) // the cloud terminates the source; the regional worker's read is the fence if !w.reach(t, 50, "converted to relocating at pinning", func() bool { c := w.claim return c.Op.Kind == "relocating" && c.Op.Phase == "pinning" && c.Op.Exec == -1 }, w.act(tgt), w.recoveryPass) { return // under the mutation the move never converges: reach recorded INV-3 } c := w.claim if !contains(c.Lost, src.ID) || c.Op.FenceBox != src.ID || c.oblFor(c.Op.ID) == 0 { t.Fatalf("witness: the conversion did not record the fence and the lane's park: %s", w.state()) } // it waits: no box in region 0. Nothing runs, nothing loops; the only // claim writes are the lane park's own steps and the one alert ver, alerts := c.Ver, w.alerts w.drive(200, func() bool { return false }, w.act(tgt), w.recoveryPass, w.operator) c = w.claim if c.Op.Kind != "relocating" || c.Op.Phase != "pinning" || c.Op.Exec != -1 { t.Fatalf("witness: the relocation did not hold at pinning: %s", w.state()) } if w.alerts <= alerts { t.Fatalf("witness: no alert for a relocation with no box in its region") } if c.Ver-ver > 8 { t.Fatalf("witness: the claim churned %d times while waiting: %s", c.Ver-ver, w.state()) } for _, b := range w.liveBoxes() { if len(b.Procs) > 0 { t.Fatalf("witness: box %d runs the host while the relocation waits", b.ID) } } w.replaceDestroyed() // region HA enrolls a replacement box (H16, H17) w.finish(t) if len(w.violations) > 0 { return } if w.stats["relocation"] != 1 { t.Fatalf("witness: the relocation did not complete: %s", w.state()) } nb := w.regionBox(src.Region) if e := w.execBox(w.claim); e == nil || nb == nil || e.ID != nb.ID || w.claim.Op.Kind != "serving" { t.Fatalf("witness: the host does not serve on the replacement box: %s", w.state()) } } // wDeclareLostCompute (model 5, §7.10): the target is frozen (a whole-VM // pause) in its settle window; its execution lease expires. func wDeclareLostCompute(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) tgt.Frozen = true exp := w.execLease[tgt.ID].Expires w.reach(t, 100, "lease expired", func() bool { return w.now > exp+lostMargin }, w.act(src), w.recoveryPass) // the operator: refused with compute fencing (the box is not stopped); // on expiry alone, the rollback and the loss go through and the source // recovers w.drive(100, func() bool { return hasMain(src) }, w.act(src), w.recoveryPass, w.operator) tgt.Frozen = false // the VM resumes: its application runs before its agent does w.tick() w.finish(t) } // wWatchdogIndependent (§7.1): as wDeclareLostCompute, with the agent // alone paused, so the application keeps running and only a watchdog // outside the agent can fence it. func wWatchdogIndependent(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) tgt.AgentPaused = true exp := w.execLease[tgt.ID].Expires dog := func() { w.watchdog(tgt) } w.reach(t, 100, "lease expired", func() bool { return w.now > exp+lostMargin }, w.act(src), w.recoveryPass, dog) w.drive(100, func() bool { return hasMain(src) }, w.act(src), w.recoveryPass, w.operator, dog) tgt.AgentPaused = false w.finish(t) } // wLostQuarantine (claim §7.2, CC12): the target is stopped while landing, // declared lost, and later started again with its old disk. func wLostQuarantine(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.moveTo(tgt.Region) w.reach(t, 600, "landing installed", func() bool { c := w.claim return c.Op.Kind == "landing" && c.Op.LandPhase == "probing" }, w.act(src, tgt), w.recoveryPass) w.stop(tgt) w.reach(t, 60, "declared lost", func() bool { return contains(w.claim.Lost, tgt.ID) }, w.act(src), w.recoveryPass, w.operator) tgt.Destroyed = false // started again, with its old disk tgt.forget() w.logf("witness: box %d started again", tgt.ID) w.finish(t) } // wMarkersLast (R2-6): the source has a registered timer; the target's // agent crashes between extracting the files and writing the marker. func wMarkersLast(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.nextW++ src.Timers = []int{w.nextW} w.acks = append(w.acks, ack{W: w.nextW, Inc: 1, Box: src.ID, Session: src.DB.Session, Gen: src.DB.Gen, At: w.now, Kind: "timer"}) w.moveTo(tgt.Region) id := w.claim.Op.ID w.reach(t, 600, "files extracted", func() bool { return tgt.Files != nil && tgt.Files.Gen == id }, w.act(src, tgt), w.recoveryPass) tgt.Procs = nil tgt.forget() // the agent crashes and restarts: its memory, the pending timers included, is gone w.logf("witness: box %d agent crashed between the extraction and the marker", tgt.ID) w.finish(t) } // wRollbackJournal (R2-3): a dirty rollback; the source's agent restarts // after its probe spawned the instance, which wrote and replicated. func wRollbackJournal(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) w.appWrite(tgt) w.rollback(w.claim, "settle check failed") w.reach(t, 2000, "source probed on the return", func() bool { c := w.claim return c.Op.Kind == "restoring" && c.Op.SrcPhase == "probed" && hasMain(src) }, w.act(src, tgt), w.recoveryPass) if !hasMain(src) { w.violate("INV-3 (witness): the source's probe did not run on the return: %s%s", w.state(), w.boxesState()) return } w.appWrite(src) w.replicate(src) // into the return generation: durable there src.Procs = nil src.forget() // the agent crashes and restarts w.logf("witness: box %d agent crashed during the rollback's probe", src.ID) w.finish(t) } // heldRound drives a move to its first staging round and holds that // round's db PUT. It returns the staging key. func (w *world) heldRound(t *testing.T, src, tgt *box) string { w.moveTo(tgt.Region) id := w.claim.Op.ID key := fmt.Sprintf("moves/%s/%s/db", host, id) w.reach(t, 100, "staging begins", func() bool { c := w.claim return c.Op.Phase == "preparing" && contains(c.Regions, tgt.Region) }, w.act(src, tgt)) w.holdKey(key) w.tick(w.act(src)) // this round's db PUT is accepted and completes late w.hold = nil return key } // wSealByVersion (J-N2): the held round completes after the seal, so the // staging key's current version is older than the sealed one. func wSealByVersion(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) key := w.heldRound(t, src, tgt) w.wake(src) // the source serves during the move if !hasMain(src) { t.Fatalf("witness: source did not wake: %s", w.state()) } w.appWrite(src) w.replicate(src) w.reach(t, 600, "sealed", func() bool { return w.claim.Op.Phase == "sealed" || w.claim.Op.Kind == "landing" }, w.act(src, tgt), w.recoveryPass) w.completeHeld(key) w.finish(t) } // wStagingQuiet (J-N2): the held round completes after the commit, once // the landing's staging park has acknowledged (if it retired at the seal // time) and before the release. func wStagingQuiet(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) key := w.heldRound(t, src, tgt) prefix := key[:strings.LastIndex(key, "/")+1] w.reach(t, 600, "committed", func() bool { return w.claim.Op.Committed }, w.act(src, tgt), w.recoveryPass) w.drive(30, func() bool { return !w.oblOpen(tgt.Region, prefix) }, w.act(src, tgt), w.recoveryPass) w.completeHeld(key) w.finish(t) } // wClaimCasOpID (claim C2): a clean rollback; the source's close writes the // record (record first, rev 7.23) and its goroutine stalls before the // release, holding the claim it read; the recovery pass releases from // last_move, a purge claims the host, and the goroutine resumes into its // release. func wClaimCasOpID(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) w.rollback(w.claim, "cut deadline") w.reach(t, 1500, "source about to close", func() bool { c := w.claim return c.Op.Kind == "restoring" && c.Op.SrcPhase == "opened" && c.oblFor(c.Op.ID) == 0 }, w.act(src, tgt), w.recoveryPass) old := w.claim.clone() // the stalled goroutine's read if !w.closeRecord(old, src.ID) { t.Fatalf("witness: the record did not close: %s", w.state()) } w.reach(t, 50, "released from last_move", func() bool { return w.claim.Op.Kind == "serving" }, w.recoveryPass) pg := &consolePlan{Kind: "purge", App: app0} w.reach(t, 20, "purge claimed the host", func() bool { return w.claim.Op.Kind == "purging" }, func() { w.runPlan(pg) }) w.resumeStaleRelease(src, old) // the goroutine wakes into its release w.tick() w.tick(func() { w.runPlan(pg) }) // the purge tears the store down w.tick(func() { w.runPlan(pg) }) } // resumeStaleRelease is a close's goroutine that stalled between the // record's close and the claim's release, resuming with the claim it read: // it revalidates (claim C3), then writes the release half. func (w *world) resumeStaleRelease(b *box, old *claim) { c, ok := w.readClaim(b) if !ok { return } if on("revalidate-before-effect") && !sameStep(old, c) { return } w.release(old, closeExec(old.Op)) } // wDirtyReturn (INV-2; also commit-before-open's witness): the target // writes during its probe and is rolled back. func wDirtyReturn(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) w.appWrite(tgt) w.replicate(tgt) // durable in the target's generation: no writes_lost declaration can cover it (rev 7.10) w.rollback(w.claim, "settle check failed") w.finish(t) } // wAdmissionTriple (J2-R2-8): an open from an earlier operation paused on // the source; it lands after the commit, while the source's row is still // held and before its park-local has run. func wAdmissionTriple(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) d := &localWrite{kind: "open", holdOp: "p0", epoch: src.Epoch, at: 1 << 30} src.deferred = append(src.deferred, d) w.moveTo(tgt.Region) w.reach(t, 600, "committed", func() bool { return w.claim.Op.Committed }, func() { w.worker(src); w.worker(tgt) }, w.recoveryPass) d.at = w.now // the paused open lands now w.tick() w.wake(src) // a request reaches the old source w.checkStep() w.finish(t) } // wStrictSpawn (§6.1): the source runs a main process and a descendant // placed as its parent was. func wStrictSpawn(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) if !hasMain(src) { t.Fatalf("witness: source did not wake: %s", w.state()) } main := src.Procs[0] src.Procs = append(src.Procs, &proc{Main: false, Strict: main.Strict, Inc: 1, Gen: main.Gen, Session: main.Session, Box: src.ID}) w.moveTo(tgt.Region) w.finish(t) } // wTouchedIncomplete (claim §9, CC4): a legacy host with a pre-release // replica in another region is adopted, then deleted. func wTouchedIncomplete(t *testing.T, w *world) { b0 := w.boxes[0] w.legacy(b0, 1) w.tick(func() { w.reconcile(b0) }) // adoption if w.claim == nil { t.Fatalf("witness: not adopted") } w.reach(t, 400, "adoption settled", func() bool { return w.claim.oblFor("adopt") == 0 }, w.actAll(), w.recoveryPass) w.userDelete() w.finish(t) } // recreate deletes and frees the serving host, creates incarnation inc in // region r, and has it run and replicate. func (w *world) recreate(t *testing.T, r, inc int) { w.userDelete() w.reach(t, 600, "freed", func() bool { c := w.claim return c != nil && c.Holder == nil && c.Op.Kind == "" }, w.actAll(), w.runConsole, w.recoveryPass) w.console = append(w.console, &consolePlan{Kind: "create", Host: "h", App: app0, OpID: w.newID("cr"), Inc: inc, Region: r}) b := w.regionBox(r) w.reach(t, 200, "recreated", func() bool { c := w.claim return c.Holder != nil && c.Holder.Inc == inc && c.Op.Kind == "serving" && b.Row != nil }, w.runConsole, w.actAll(), w.recoveryPass) b.Config, b.CfgVer, b.Live, b.LiveInc = inc, w.cfgVer[app0], app0, inc // config sync and adoption have run // the first wake of the new incarnation's empty generation is a cold // recovery (claim rev 6.6 §6.4a): the box's role runs it, then the wake // admits the writer into the recovered generation if !w.reach(t, 400, "new incarnation running", func() bool { return hasMain(b) }, w.actAll(), func() { w.wake(b) }) { t.Fatalf("witness: the new incarnation did not run: %s", w.state()) } w.appWrite(b) w.appWrite(b) // two transactions: its first LTX file has the same key as the fixture's w.replicate(b) } // wDoorReread (claim §6.5 O2): a listing authorized before the delete // selects after the recreate. Retired from the table in rev 7.8: under // claim rev 6.6's writer epochs a recreated incarnation's first wake is a // cold recovery into a fresh generation, which a listing scoped to the // generation it was authorized for never selects, so the scenario holds // with C3a dropped too; C3a stays as defence in depth (§14.2.5). func wDoorReread(t *testing.T, w *world) { b0 := w.boxes[0] w.serve(b0, 1, app0) w.doorAuthorize() // O1 w.recreate(t, 0, 2) w.doorOpen() // select and O2 w.doorOpen() // open } // wDoorByVersion (claim §6.5): a listing selects and signs before the // delete, and the file request opens after the recreate. func wDoorByVersion(t *testing.T, w *world) { b0 := w.boxes[0] w.serve(b0, 1, app0) w.doorAuthorize() // O1 w.tick() w.tick() w.doorOpen() // select, O2, sign if len(w.doorReads) != 1 || !w.doorReads[0].Signed { t.Fatalf("witness: listing not signed") } w.recreate(t, 0, 2) w.doorOpen() // open } // wRegistrationCheck (CC21, claim §5.3): the first create of a host // registers and its console pauses; a purge of the app drains the expired // registration, tears the store down and finishes; the creator resumes. func wRegistrationCheck(t *testing.T, w *world) { p := &consolePlan{Kind: "create", Host: "h", App: app0, OpID: w.newID("cr"), Inc: 1, Region: 0} w.runPlan(p) // registered; the claim is absent for i := 0; i < 61; i++ { w.tick() } pg := &consolePlan{Kind: "purge", App: app0} done := false w.reach(t, 30, "purge done", func() bool { return done }, func() { if w.runPlan(pg) { done = true } }) for i := 0; i < 6; i++ { w.tick(func() { w.runPlan(p) }) // the creator resumes } } // ---------- rev 7.4 ---------- // wRoundTrip (claim rev 6 §6.4, R3-3): UK→US, then US→UK. The first // move's retirement wrote UK's local marker for the incarnation; the // second landing must replace it. Unmutated, the instance must serve on // UK again, running. func wRoundTrip(t *testing.T, w *world) { uk, us := w.boxes[0], w.boxes[1] w.serve(uk, 1, app0) w.moveTo(us.Region) w.reach(t, 1500, "serving on box 1 after the first move", func() bool { c := w.claim return c.Op.Kind == "serving" && c.Op.Exec == us.ID && w.rec != nil && w.rec.MoveID == "" && len(c.Obl) == 0 }, w.act(uk, us), w.recoveryPass) if st := uk.Stamps[1]; st == nil || st.Active != 0 || len(st.Retired) == 0 { t.Fatalf("witness: box 0 did not retire its installation: %+v %s%s", st, w.state(), w.boxesState()) } w.moveTo(uk.Region) if w.claim.Op.Kind != "moving" { t.Fatalf("witness: the move back did not start: %s", w.state()) } w.reach(t, 1500, "instance back on box 0, running", func() bool { c := w.claim return c.Op.Kind == "serving" && c.Op.Exec == uk.ID && hasMain(uk) }, w.act(uk, us), w.recoveryPass, w.operator) w.finish(t) } // runOthers runs every console plan but skip, one step each, removing // the finished ones. func (w *world) runOthers(skip *consolePlan) func() { return func() { w.runPlans(skip) } } // wOrphanOrder (claim rev 6 §5.1 step 5, R3-2): a cancelled create's // record lands late; the recovery pass starts its cleanup and pauses // after its first observation; a create of the next incarnation removes // the orphan itself, claims and publishes; the paused cleanup resumes. func wOrphanOrder(t *testing.T, w *world) { w.claim = &claim{Ver: w.newVer(), Retired: []int{1}, Cancelled: []cancelledCreate{{Inc: 1, Until: w.now + 1000}}} w.nextInc = 1 w.rec = &record{Ver: w.newVer(), Inc: 1, App: app0, Region: 0} w.logf("witness: the record of cancelled incarnation 1 landed") w.recoveryPass() var p1 *consolePlan for _, p := range w.console { if p.Kind == "orphan" { p1 = p } } if p1 == nil { t.Fatalf("witness: the recovery pass started no cleanup: %s", w.state()) } w.tick(func() { w.runPlan(p1) }) // the first observation; then the console pauses cr := &consolePlan{Kind: "create", Host: "h", App: app0, OpID: w.newID("cr"), Inc: 2, Region: 0} w.console = append(w.console, cr) w.reach(t, 50, "incarnation 2 claimed and published", func() bool { return w.rec != nil && w.rec.Inc == 2 }, w.runOthers(p1)) w.tick(func() { w.runPlan(p1) }) // the paused cleanup resumes w.tick(func() { w.runPlan(p1) }) w.finish(t) } // wSweepNamespace (claim rev 6 §6.2a, R3-4): a replication PUT of // incarnation 1 is accepted and completes after 33 delete-and-recreate // cycles, by which time retired_incarnations no longer lists 1. func wSweepNamespace(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) if !hasMain(b) { t.Fatalf("witness: the host did not wake: %s", w.state()) } w.appWrite(b) key := dataKey(w.claim.Holder.Location, "", "") + "0000/" w.holdKey(key) w.replicate(b) w.hold = nil for inc := 2; inc <= retiredCap+2; inc++ { w.recreate(t, 0, inc) if len(w.violations) > 0 { return } } if contains(w.claim.Retired, 1) { t.Fatalf("witness: incarnation 1 is still in retired_incarnations after %d recreates", retiredCap+1) } if w.completeHeld(key) != 1 { t.Fatalf("witness: no held replication PUT") } w.finish(t) } // wCommitBeforeOpen (INV-5, R3-5): a public request reaches the target's // edge while its probe runs. The edge routes on the row. func wCommitBeforeOpen(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) w.wake(tgt) w.checkStep() w.finish(t) } // wRecoveryInputs (§7.8, R2-5): a config bundle is published after the // move was admitted; the target does real work and the rollback is // dirty; the source's recovery install must render current inputs, not // the inputs the move pinned. func wRecoveryInputs(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) w.cfgVer[app0]++ w.logf("witness: config bundle %s v%d published during the settle window", app0, w.cfgVer[app0]) w.appWrite(tgt) w.rollback(w.claim, "settle check failed") w.finish(t) } // ---------- rev 7.5 ---------- // roundTrip moves the host UK→US→UK and requires it to serve on UK again, // running. func (w *world) roundTrip(t *testing.T, uk, us *box) { w.moveTo(us.Region) w.reach(t, 1500, "serving on box 1 after the first move", func() bool { c := w.claim return c.Op.Kind == "serving" && c.Op.Exec == us.ID && w.rec != nil && w.rec.MoveID == "" && len(c.Obl) == 0 }, w.act(uk, us), w.recoveryPass) w.moveTo(uk.Region) if w.claim.Op.Kind != "moving" { t.Fatalf("witness: the move back did not start: %s", w.state()) } w.reach(t, 1500, "instance back on box 0, running", func() bool { c := w.claim return c.Op.Kind == "serving" && c.Op.Exec == uk.ID && hasMain(uk) }, w.act(uk, us), w.recoveryPass, w.operator) } // wStaleWriter (claim rev 6.5 §6.4, R4-2): a config-sync pass selects the // row under the first installation and pauses; the host moves away and // back; a new bundle is published; the pass takes the guard. func wStaleWriter(t *testing.T, w *world) { uk, us := w.boxes[0], w.boxes[1] w.serve(uk, 1, app0) w.passPlan(uk, "config") if len(uk.plans) != 1 { t.Fatalf("witness: no plan") } p := uk.plans[0] p.At = 1 << 30 // paused w.roundTrip(t, uk, us) if len(w.violations) > 0 { return } w.cfgVer[app0]++ p.At = w.now // the pass resumes and takes the guard w.tick(func() { w.passExec(uk) }) w.finish(t) } // wLiveSetRegion (claim rev 6.5 §6.2a, R4-3): a legacy host serves in UK // (box 0) with a pre-release replica in US (box 1). Adoption's discovery // parks US. A replication PUT the old US executor issued before the // retirement completes after it. func wLiveSetRegion(t *testing.T, w *world) { uk, us := w.boxes[0], w.boxes[1] w.legacy(uk, us.Region) // the old US executor's last replication PUT, accepted, completing late late := &blob{Kind: "ltx", Level: 0, Min: 2, Max: 2, Inc: 0, SealKey: 7, Pages: cloneState(uk.DB.State)} w.pending = append(w.pending, &request{kind: rPut, region: us.Region, key: ltxKey("instances/"+host+"/", "", 0, 2, 2), b: late, doneAt: 1 << 30, by: "box:1"}) w.tick(func() { w.reconcile(uk) }) // adoption if w.claim == nil { t.Fatalf("witness: not adopted") } w.reach(t, 400, "discovery settled", func() bool { return w.claim.oblFor("adopt") == 0 }, w.actAll(), w.recoveryPass) if w.completeHeld(ltxKey("instances/"+host+"/", "", 0, 2, 2)) != 1 { t.Fatalf("witness: no held PUT") } w.finish(t) } // pushed installs a push generation on b: the host serves from a snapshot // at its current TXID, then runs again, so the witness can shape the // generation's LTX files by hand. func (w *world) pushed(t *testing.T, b *box) (loc, gen string) { w.userPush() gen = w.claim.Op.ID w.reach(t, 400, "push released", func() bool { return w.claim.Op.Kind == "serving" }, w.act(b)) w.idleStop(b) // the wake after the push: under a mutation it may be a cold recovery // first (claim rev 6.6 §6.4a), which the box's role runs if !w.reach(t, 60, "woken after the push", func() bool { return hasMain(b) }, w.act(b), func() { w.wake(b) }) { t.Fatalf("witness: the host did not wake after the push: %s%s", w.state(), w.boxesState()) } return w.claim.Holder.Location, gen } // compactedPending builds the level-1 file [min, max], in replication // numbering, that compaction would have left for b's pending writes: the // final image of every key they touched. The witness places it where // compaction would and advances the position past it. func (w *world) compactedPending(b *box, min, max int) *blob { db := b.DB out := &blob{Kind: "ltx", Level: 1, Min: min, Max: max, Inc: db.Inc, Gen: db.Gen, SealKey: db.Key, Pages: map[string]int{}} for _, wr := range db.Pending { t := w.txs[wr] out.Pages[t.Key] = db.State[t.Key] out.TXs = append(out.TXs, wr) } db.Pos, db.Pending = max, nil return out } // wRestoreOverlap (R4-1): after a push the generation's snapshot ends at // TXID 11 (two writes, eight more, the push's mark). The host writes four // more; compaction has left one current file [10,15] and no level-0 // files. The disk is lost and the host wakes cold. func wRestoreOverlap(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) for i := 0; i < 8; i++ { w.appWrite(b) } w.replicate(b) loc, gen := w.pushed(t, b) if len(w.violations) > 0 { return } n := b.DB.Pos // the snapshot's TXID after the push, in replication numbering for i := 0; i < 4; i++ { w.appWrite(b) } // compaction has left one file [n-1, n+2] overlapping the snapshot f := w.compactedPending(b, n-1, n+2) w.buckets[b.Region].objs[ltxKey(loc, gen, 1, n-1, n+2)] = []*version{{ID: w.newVer(), B: f}} w.markDurable(ltxKey(loc, gen, 1, n-1, n+2), f) w.idleStop(b) b.DB = nil // the disk is lost; the next wake restores cold w.logf("witness: box %d lost its database; the generation holds the snapshot at %d and [%d,%d]", b.ID, n, n-1, n+2) w.reach(t, 60, "woken cold", func() bool { return hasMain(b) }, w.act(b), func() { w.wake(b) }) w.finish(t) } // wRestoreGap (R4-1): the same generation with a genuine gap: the file // [12,12] never landed and [13,13] is current. The restore must refuse. func wRestoreGap(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) for i := 0; i < 8; i++ { w.appWrite(b) } w.replicate(b) loc, gen := w.pushed(t, b) if len(w.violations) > 0 { return } n := b.DB.Pos w.appWrite(b) // its file, [n+1, n+1], never lands b.DB.Pos, b.DB.Pending = n+1, nil w.appWrite(b) f := w.compactedPending(b, n+2, n+2) // [n+2, n+2] is current w.buckets[b.Region].objs[ltxKey(loc, gen, 0, n+2, n+2)] = []*version{{ID: w.newVer(), B: f}} w.idleStop(b) db := w.restoreCalc(b.Region, 1, loc, gen) if db != nil { w.violate("INV-2 (cold restore): a restore across the gap after TXID %d returned a database at position %d", n, db.Pos) } } // ---------- rev 7.6 ---------- // wSnapshotOnlyInstall (R5-1): the push installs a snapshot; the host // wakes, writes, replicates, loses its disk and wakes cold. func wSnapshotOnlyInstall(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) for i := 0; i < 3; i++ { w.appWrite(b) } w.replicate(b) // the push's probe process goes on serving after the release (no // clean close in between: a clean close would write a marker whose // max_txid betrays the missing anchor and force a recovery first) w.userPush() w.reach(t, 400, "push released", func() bool { return w.claim.Op.Kind == "serving" }, w.act(b)) if len(w.violations) > 0 || !hasMain(b) { return } for i := 0; i < 2; i++ { w.appWrite(b) w.replicate(b) } // the writer dies with its disk (a clean close would write a marker // whose max_txid, 2, is behind the snapshot's 3 and force a cold // recovery from the warm database, which hides the missing anchor) w.crash(b) w.loseDisk(b) w.logf("witness: box %d lost its database after replicating past the push's snapshot", b.ID) w.reach(t, 60, "woken cold", func() bool { return hasMain(b) }, w.act(b), func() { w.wake(b) }) w.finish(t) } // wRootAdvance (R5-3): after the push, enough writes and replication for // compaction to rotate snapshots four times, retention expiring the files // that continued from the pinned snapshot; then the disk is lost. func wRootAdvance(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) w.appWrite(b) w.replicate(b) loc, gen := w.pushed(t, b) if len(w.violations) > 0 { return } for round := 0; round < 4; round++ { for i := 0; i < 3; i++ { w.appWrite(b) w.replicate(b) } } snaps := w.currentLTX(w.buckets[b.Region], dataKey(loc, gen, ""), 9) if len(snaps) == 0 || snaps[len(snaps)-1].B.Max <= w.buckets[b.Region].current(genMarkerKey(loc)).B.TX { t.Fatalf("witness: no successor snapshot rotated in: %d snapshots", len(snaps)) } w.idleStop(b) b.DB = nil // the disk is lost w.logf("witness: box %d lost its database after four rotations", b.ID) w.reach(t, 60, "woken cold", func() bool { return hasMain(b) }, w.act(b), func() { w.wake(b) }) w.finish(t) } // ---------- rev 7.7 ---------- // wAnchorHeld (R6-1): the push's install writes its anchor and the PUT is // slow. Until it is acknowledged the host must not open replication: the // position litestream would read from the listing is 0. func wAnchorHeld(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) for i := 0; i < 3; i++ { w.appWrite(b) } w.replicate(b) w.userPush() gen := w.claim.Op.ID loc := w.claim.Holder.Location // the build (R7-4): the snapshot is acknowledged, the anchor is next; // the witness holds the anchor PUT there w.reach(t, 400, "push building its anchor", func() bool { return w.claim.Op.Kind == "pushing" && w.claim.Op.Phase == "install-anchor" }, w.act(b)) n := w.claim.Op.BaseTX anchor := ltxKey(loc, gen, 0, n, n) w.holdKey(anchor) prefix := dataKey(loc, gen, "") for i := 0; i < 40; i++ { w.tick(w.act(b)) if len(w.violations) > 0 { return // INV-11: published before the anchor landed } for _, f := range w.currentLTX(w.buckets[b.Region], prefix, 0) { if f.B.Min != n { w.violate("INV-2 (witness): box %d replicated [%d,%d] before its anchor [%d,%d] was acknowledged", b.ID, f.B.Min, f.B.Max, n, n) return } } if hasMain(b) { w.violate("INV-2 (witness): box %d opened replication before its anchor [%d,%d] was acknowledged; litestream's position would be %d", b.ID, n, n, w.maxL0(w.buckets[b.Region], prefix)) return } } w.hold = nil if w.completeHeld(anchor) == 0 { t.Fatalf("witness: no anchor PUT was held: %s", w.state()) } w.reach(t, 400, "push released", func() bool { return w.claim.Op.Kind == "serving" }, w.act(b)) w.idleStop(b) w.reach(t, 60, "woken after the push", func() bool { return hasMain(b) }, w.act(b), func() { w.wake(b) }) for i := 0; i < 2; i++ { w.appWrite(b) w.replicate(b) } w.idleStop(b) b.DB = nil // the disk is lost w.reach(t, 60, "woken cold", func() bool { return hasMain(b) }, w.act(b), func() { w.wake(b) }) w.finish(t) } // wReturnLostRecord (claim rev 6.5, R6-4): a dirty rollback; the source's // local stamp record is lost before the return. The return CAS writes the // source installation's stamp back into holder.stamp, the source // re-initializes from it, installs the return generation under it, and its // probe CAS issues the new stamp, which retires it. func wReturnLostRecord(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) s := src.stampOf(1) w.landProbed(t, src, tgt) w.appWrite(tgt) w.rollback(w.claim, "settle check failed") w.reach(t, 400, "target returned", func() bool { return w.claim.Op.Phase == "returned" }, w.act(tgt)) src.Stamps = nil w.logf("witness: box %d lost its local stamp record", src.ID) w.finish(t) if len(w.violations) > 0 { return } c := w.claim if c == nil || c.Holder == nil || c.Op.Exec != src.ID { t.Fatalf("witness: the source does not serve after the rollback: %s", w.state()) } act := src.stampOf(1) switch { case act != c.Holder.Stamp: w.violate("INV-6 (witness): box %d active stamp %d, holder.stamp %d", src.ID, act, c.Holder.Stamp) case src.DB == nil || src.DB.Stamp != act: w.violate("INV-6 (witness): box %d database tagged %d, active %d", src.ID, dbStamp(src.DB), act) case act == s || !contains(src.Stamps[1].Retired, s): w.violate("INV-6 (witness): the pre-move stamp %d did not retire when %d activated on box %d", s, act, src.ID) } } // ---------- rev 7.8 ---------- // crash is the agent dying with its processes (an OOM kill, a crash): what // it had in flight is unaccounted for, and the restarted agent knows // nothing of it (forget). Nothing cleans up, so no closed.json. func (w *world) crash(b *box) { b.Procs = nil b.forget() w.logf("witness: box %d's agent crashed", b.ID) } // loseDisk is the disk-loss fault: the database file is gone, and every // acknowledged write not yet durable anywhere is declared lost (exempt). func (w *world) loseDisk(b *box) { if b.DB == nil { return } // physical loss only (R10-6): the next admission declares the writes b.DB = nil w.logf("witness: box %d lost its database file", b.ID) } // appWriteKey is one acknowledged application write of key = val (0 is a // delete) by b's main process. func (w *world) appWriteKey(b *box, key string, val int) int { if !hasMain(b) { panic("appWriteKey: no main process") } p := b.Procs[0] w.nextW++ wr := w.nextW db := b.DB t := tx{W: wr, Key: key, Val: val} if val == 0 { delete(db.State, key) } else { db.State[key] = val } db.TX++ t.TX = db.TX db.Pending = append(db.Pending, wr) db.Log = append(db.Log, wr) w.txs[wr] = t sess, gen := w.sessionOf(b) w.acks = append(w.acks, ack{W: wr, Inc: p.Inc, Box: b.ID, Session: sess, Gen: gen, At: w.now, Kind: "write"}) w.writeInc[wr] = p.Inc w.logf("witness: box %d wrote %d: %s = %d", b.ID, wr, key, val) return wr } // recovered drives the box until it runs again: a cold recovery first, // when its replication state was lost, then the wake. // sessionOf is the writer session and generation b's database was admitted // under: what its acknowledgements carry (rev 7.13, R12-1). func (w *world) sessionOf(b *box) (int, string) { if b.DB == nil { return 0, "" } return b.DB.Session, b.DB.Gen } func (w *world) recovered(t *testing.T, b *box, what string) { if !w.reach(t, 120, what, func() bool { return hasMain(b) }, w.act(b), w.recoveryPass, func() { w.wake(b) }) { t.Fatalf("witness: %s: the host did not run again: %s%s", what, w.state(), w.boxesState()) } } // deadWriter is the common opening of the R7-1 witnesses: the serving box // writes once more, its level-0 upload for that write is held in flight, // and the box dies with its disk. It returns the held key. func (w *world) deadWriter(t *testing.T, b *box) string { w.serve(b, 1, app0) w.wake(b) loc := w.claim.Holder.Location w.appWrite(b) key := ltxKey(loc, "", 0, b.DB.Pos+1, b.DB.Pos+1) w.holdKey(key) w.replicate(b) // A's upload: accepted, outstanding w.hold = nil w.crash(b) w.loseDisk(b) return key } // wLateUploadAfter (R7-1): A's outstanding upload lands after B uploaded // its own file for the same TXID. func wLateUploadAfter(t *testing.T, w *world) { b := w.boxes[0] key := w.deadWriter(t, b) w.recovered(t, b, "B running after A's death") w.appWrite(b) w.replicate(b) // B's upload if w.completeHeld(key) == 0 { t.Fatalf("witness: A's upload was not held") } w.checkDurable(w.claim, "after A's late upload landed") // before any snapshot of the warm database repairs the replica w.finish(t) } // wLateUploadRace (R7-1): A's outstanding upload lands after B // initialized its position and before B's own upload for that TXID. func wLateUploadRace(t *testing.T, w *world) { b := w.boxes[0] key := w.deadWriter(t, b) w.recovered(t, b, "B running after A's death") if w.completeHeld(key) == 0 { t.Fatalf("witness: A's upload was not held") } w.appWrite(b) w.replicate(b) // B's upload, or litestream's skip at the remote position w.checkDurable(w.claim, "after B's upload") w.finish(t) } // wExemptKeyRestored (R7-2): A's in-flight write updated K; B durably // updates K; A's stale upload lands and restores A's value. func wExemptKeyRestored(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) loc := w.claim.Holder.Location k := fmt.Sprintf("k%d", b.DB.Log[0]) // a key the fixture wrote w.appWriteKey(b, k, 99) key := ltxKey(loc, "", 0, b.DB.Pos+1, b.DB.Pos+1) w.holdKey(key) w.replicate(b) w.hold = nil w.crash(b) w.loseDisk(b) // A's update of K is declared lost w.recovered(t, b, "B running after A's death") w.appWriteKey(b, k, 77) // B's durable update of K w.replicate(b) if w.completeHeld(key) == 0 { t.Fatalf("witness: A's upload was not held") } w.checkDurable(w.claim, "after A's stale upload landed") w.finish(t) } // wCrashBeforeMarker (claim rev 6.6 §6.4a): a clean stop drains its // uploads, then the agent crashes before closed.json is written; the next // wake must be a cold recovery. func wCrashBeforeMarker(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) gen := w.claim.Holder.Gen w.appWrite(b) key := ltxKey(w.claim.Holder.Location, "", 0, b.DB.Pos+1, b.DB.Pos+1) w.holdKey(key) w.idleStop(b) // closing: the upload is outstanding, no marker yet w.hold = nil w.completeHeld(key) // the upload returns w.crash(b) // before closeStep ran again: no closed.json if on("recovery-generation") && w.buckets[b.Region].current(closedKey(w.claim.Holder.Location, gen, w.claim.Holder.Session)) != nil { t.Fatalf("witness: a certificate exists after the crash") } w.recovered(t, b, "running after the crash") if w.claim.Holder.Gen == gen { w.violate("INV-2 (witness): no cold recovery after a crash left generation %q without closed.json; box %d continued it", gen, b.ID) return } w.finish(t) } // wStaleMarker (claim rev 6.6 §6.4a): a closed.json whose max_txid is // behind the remote maximum, beside a dead writer's outstanding upload. func wStaleMarker(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) // consumes the fixture's marker as it opens loc := w.claim.Holder.Location key := w.deadWriterContinues(b, loc) // [2,2] in flight; the remote maximum is 1 // a stale certificate for the current session: a late PUT of a close // that said 0, behind the remote maximum, beside the dead writer's // outstanding upload sk := closedKey(loc, "", w.claim.Holder.Session) w.buckets[b.Region].objs[sk] = append(w.buckets[b.Region].objs[sk], &version{ID: w.newVer(), B: &blob{Kind: "closed", Inc: 1, Stamp: b.stampOf(1), Seq: b.ID, Session: w.claim.Holder.Session, TX: 0}}) w.recovered(t, b, "B running after A's death") w.appWrite(b) w.replicate(b) if w.completeHeld(key) == 0 { t.Fatalf("witness: A's upload was not held") } w.checkDurable(w.claim, "after A's late upload landed") w.finish(t) } // deadWriterContinues: the running writer writes once more with its // upload held, then dies with its disk; the held key is returned. func (w *world) deadWriterContinues(b *box, loc string) string { w.appWrite(b) key := ltxKey(loc, b.DB.Gen, 0, b.DB.Pos+1, b.DB.Pos+1) w.holdKey(key) w.replicate(b) w.hold = nil w.crash(b) w.loseDisk(b) return key } // wCloseWaits (claim rev 6.6 §6.4a): a clean stop with an upload in // flight writes no closed.json until the upload returned. func wCloseWaits(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) loc := w.claim.Holder.Location w.appWrite(b) key := ltxKey(loc, "", 0, b.DB.Pos+1, b.DB.Pos+1) w.holdKey(key) w.idleStop(b) sk := closedKey(loc, "", b.DB.Session) for i := 0; i < uploadTimeout-2; i++ { // short of the client's timeout: a retry would make this session uncertain for good (R8-5) w.tick(func() { w.replicate(b) }) if w.buckets[b.Region].current(sk) != nil { w.violate("INV-2 (witness): box %d wrote its certificate before every upload returned (%s is in flight)", b.ID, key) return } } w.hold = nil if w.completeHeld(key) == 0 { t.Fatalf("witness: the upload was not held") } w.tick(func() { w.replicate(b) }) if w.buckets[b.Region].current(sk) == nil { t.Fatalf("witness: no certificate after the uploads returned") } // the writer continues the generation: no upload of its previous run // can be outstanding, every one returned before the marker w.recovered(t, b, "continued after the clean close") if w.claim.Holder.Gen != "" { t.Fatalf("witness: a cold recovery after a clean close") } w.appWrite(b) w.replicate(b) w.finish(t) } // wNewestL0 (R7-3): the local position runs ahead of the uploads across // two compactions and snapshot rotations. func wNewestL0(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) loc := w.claim.Holder.Location prefix := dataKey(loc, "", "") held := map[string]bool{} w.hold = func(r *request) bool { return held[r.key] } k := func(n int) string { return ltxKey(loc, "", 0, n, n) } // position 2 is already uploaded (the fixture at 1, one write at 2) w.appWrite(b) w.replicate(b) // uploads from 3 on are held; the writer reaches position 10 held[k(3)] = true for i := 3; i <= 10; i++ { w.appWrite(b) w.replicate(b) } // 3 lands; 4 and 5 ship; 6 is held: compaction sees {2,3,4,5}, keeps 5, // rotates a snapshot at the local position 10 held[k(6)] = true delete(held, k(3)) w.completeHeld(k(3)) w.replicate(b) if got := w.maxL0(w.buckets[b.Region], prefix); got == 0 { w.violate("INV-2 (witness): compaction removed the newest level-0 file of %s; litestream keeps it, and a fresh box reads its position there (%s)", prefix, w.ltxShape(b.Region, prefix)) return } else if got != 5 { t.Fatalf("witness: newest uploaded level-0 file is %d, want 5 (%s)", got, w.ltxShape(b.Region, prefix)) } // the writer goes on to 11; 6 lands and 7 to 11 ship but 12 is held: // compaction sees {5,6,...}, rotates a snapshot at 11 and expires // below the previous snapshot, 10 w.appWrite(b) w.replicate(b) held[k(12)] = true delete(held, k(6)) w.completeHeld(k(6)) w.replicate(b) w.appWrite(b) w.replicate(b) w.hold = nil newest := w.maxL0(w.buckets[b.Region], prefix) snaps := w.currentLTX(w.buckets[b.Region], prefix, 9) if len(snaps) == 0 { t.Fatalf("witness: no snapshot rotated: %s", w.ltxShape(b.Region, prefix)) } if newest == 0 { w.violate("INV-2 (witness): retention removed the newest level-0 file of %s; litestream keeps it, and a fresh box reads its position there (%s)", prefix, w.ltxShape(b.Region, prefix)) return } w.completeHeld(k(12)) w.finish(t) } // wBuildCrashes (R7-4): a push's build with its snapshot PUT, then its // anchor PUT, held, the agent crashing in between each. func wBuildCrashes(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) for i := 0; i < 2; i++ { w.appWrite(b) } w.replicate(b) w.userPush() gen := w.claim.Op.ID loc := w.claim.Holder.Location w.reach(t, 400, "push installing", func() bool { return w.claim.Op.Kind == "pushing" && w.claim.Op.Phase == "install" }, w.act(b)) n := w.claim.Op.PushSnap.Max snap := snapKey(loc, gen, n) anchor := ltxKey(loc, gen, 0, n, n) published := func() bool { m := w.buckets[b.Region].current(genMarkerKey(loc)) return m != nil && m.B.Gen == gen } w.holdKey(snap) for i := 0; i < 12; i++ { w.tick(w.act(b)) if len(w.violations) > 0 { return // INV-11 } if i == 5 { w.crash(b) // between the intent and the snapshot's acknowledgement } if published() { w.violate("INV-11 (witness): generation.json names %s before its snapshot %s landed", gen, snap) return } } w.hold = nil w.completeHeld(snap) w.reach(t, 100, "push building its anchor", func() bool { return w.claim.Op.Phase == "install-anchor" }, w.act(b)) w.holdKey(anchor) for i := 0; i < 12; i++ { w.tick(w.act(b)) if len(w.violations) > 0 { return } if i == 5 { w.crash(b) // between the snapshot's and the anchor's acknowledgement } if published() { w.violate("INV-11 (witness): generation.json names %s before its anchor %s landed", gen, anchor) return } } w.hold = nil w.completeHeld(anchor) w.reach(t, 400, "push released", func() bool { return w.claim.Op.Kind == "serving" }, w.act(b)) w.crash(b) // after completion: the marker stands, the generation is complete w.recovered(t, b, "running after the push") w.appWrite(b) w.replicate(b) w.finish(t) } // wEvidenceWholeTree (§6.1): a legacy host adopted with a descendant that // escaped the cgroup; the move cuts. func wEvidenceWholeTree(t *testing.T, w *world) { b0, b1 := w.boxes[0], w.boxes[1] w.legacy(b0, 1) w.tick(func() { w.reconcile(b0) }) // adoption if w.claim == nil { t.Fatalf("witness: not adopted") } w.reach(t, 400, "adoption settled", func() bool { return w.claim.oblFor("adopt") == 0 }, w.actAll(), w.recoveryPass) if !hasMain(b0) { w.recovered(t, b0, "running after adoption") } b0.Procs = append(b0.Procs, &proc{Main: false, Strict: false, Inc: 1, Gen: b0.Procs[0].Gen, Session: b0.Procs[0].Session, Box: b0.ID}) // an escaped descendant w.moveTo(b1.Region) w.finish(t) } // wTimerFreeze (J-N14): a timer registered on the source, a move that // holds the row, refused deliveries, then a clean rollback whose verify // compares the timer digest with the one recorded at the stop. func wTimerFreeze(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.nextW++ src.Timers = []int{w.nextW} w.acks = append(w.acks, ack{W: w.nextW, Inc: 1, Box: src.ID, Session: src.DB.Session, Gen: src.DB.Gen, At: w.now, Kind: "timer"}) w.landProbed(t, src, tgt) // the source is stopped and its row held for i := 0; i < 3; i++ { w.runner(src) // deliveries refused while the row is held } w.rollback(w.claim, "settle check failed") // clean: the target wrote nothing w.finish(t) } // ---------- rev 7.9 ---------- // wDeadSessionCertificate (claim rev 6.8 §6.4a, R8-1): a certificate of a // dead session whose max_txid still matches the remote maximum. func wDeadSessionCertificate(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) // warm: session 2 loc := w.claim.Holder.Location w.idleStop(b) // session 2 certifies {max 1}, the generation's position w.recovered(t, b, "warm continuation") // session 3; the certificates of 1 and 2 are dead key := w.deadWriterContinues(b, loc) // [2,2] in flight; A dies with its disk // the dead certificates are still there, never deleted, and session 2's // max_txid 1 equals the remote maximum, since [2,2] has not landed; // holder.session is 3, for which no certificate exists w.recovered(t, b, "B running after A's death") w.appWrite(b) w.replicate(b) // B's [2,2] if w.completeHeld(key) == 0 { t.Fatalf("witness: A's upload was not held") } w.checkDurable(w.claim, "after A's late upload landed") // two level-0 files: nothing compacted or snapshotted over A's w.finish(t) } // wCommittedLandingCrash (R8-2): the committed move's target dies with its // disk and an upload in flight while the claim is still landing. func wCommittedLandingCrash(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.moveTo(tgt.Region) w.reach(t, 600, "committed and serving on the target", func() bool { return w.claim.Op.Kind == "landing" && w.claim.Op.Committed && hasMain(tgt) }, w.act(src, tgt), w.recoveryPass) if w.claim.Op.Kind != "landing" { t.Fatalf("witness: the move finalized before the target could crash: %s", w.state()) } loc := w.claim.Holder.Location key := w.deadWriterContinues(tgt, loc) // the target's upload in flight; it dies with its disk w.recovered(t, tgt, "target running again while the claim is still landing") w.appWrite(tgt) w.replicate(tgt) if w.completeHeld(key) == 0 { t.Fatalf("witness: the target's upload was not held") } w.checkDurable(w.claim, "after the dead target's late upload landed") w.finish(t) } // wProbeRestart (R8-2): the landing's probe dies with its disk and an // upload in flight; the landing restarts its probe. func wProbeRestart(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) loc := w.claim.Holder.Location w.appWrite(tgt) // the probe writes key := ltxKey(loc, tgt.DB.Gen, 0, tgt.DB.Pos+1, tgt.DB.Pos+1) w.holdKey(key) w.replicate(tgt) w.hold = nil w.crash(tgt) w.loseDisk(tgt) w.reach(t, 400, "probe restarted", func() bool { return hasMain(tgt) }, w.act(src, tgt), w.recoveryPass) if !hasMain(tgt) { t.Fatalf("witness: the probe did not restart: %s", w.state()) } wr := w.appWrite(tgt) w.replicate(tgt) if w.completeHeld(key) == 0 { t.Fatalf("witness: the dead probe's upload was not held") } // the landing's generation, holder.generation since the probe's cold // admission (claim rev 6.9), as its planner would restore it now gen := w.claim.Holder.Gen db := w.restoreCalc(tgt.Region, 1, loc, gen) if db == nil || !contains(db.Log, wr) { w.violate("INV-2 (witness): the landing's generation %q lost the restarted probe's write %d after the dead probe's upload landed", gen, wr) return } w.finish(t) } // wEmptyBootstrap (R8-3): a created incarnation's first wake. func wEmptyBootstrap(t *testing.T, w *world) { w.console = append(w.console, &consolePlan{Kind: "create", Host: "h", App: app0, OpID: w.newID("cr"), Inc: 1, Region: 0}) b := w.regionBox(0) w.reach(t, 200, "created", func() bool { c := w.claim return c != nil && c.Holder != nil && c.Holder.Inc == 1 && c.Op.Kind == "serving" && b.Row != nil }, w.runConsole, w.actAll(), w.recoveryPass) b.Config, b.CfgVer, b.Live, b.LiveInc = 1, w.cfgVer[app0], app0, 1 // the first wake: a cold admission into an empty generation (claim rev // 6.9), no LTX file at all w.reach(t, 120, "first wake", func() bool { return hasMain(b) }, w.act(b), w.recoveryPass, func() { w.wake(b) }) if len(w.violations) > 0 { return } if !hasMain(b) { t.Fatalf("witness: the created incarnation did not run: %s", w.state()) } loc := w.claim.Holder.Location gen := w.claim.Holder.Gen if n := len(w.currentLTX(w.buckets[b.Region], dataKey(loc, gen, ""), 0)) + len(w.currentLTX(w.buckets[b.Region], dataKey(loc, gen, ""), 9)); n != 0 { t.Fatalf("witness: an empty generation has %d LTX files before the first transaction", n) } // a move of the empty incarnation: its seal at the cut is at position 0 // with no transaction, and the landing installs nothing; the mutation // installs a snapshot [1,0] and an anchor [0,0], which the encoder // refuses (INV-12 at the PUT). A push cannot be empty: its seal carries // the push's own mark w.idleStop(b) w.reach(t, 400, "the first wake's chores done", func() bool { return len(w.claim.Obl) == 0 }, w.act(b), w.recoveryPass) tgt := w.regionBox(1) w.moveTo(tgt.Region) if w.claim.Op.Kind != "moving" { t.Fatalf("witness: the move of the empty incarnation did not start: %s", w.state()) } w.reach(t, 800, "move of the empty incarnation finalized", func() bool { return w.claim.Op.Kind == "serving" && w.claim.Op.Exec == tgt.ID }, w.act(b, tgt), w.recoveryPass) if len(w.violations) > 0 { return } w.recovered(t, tgt, "woken after the move") w.appWrite(tgt) w.replicate(tgt) // the first transaction is the first upload, [1,1] w.idleStop(tgt) w.loseDisk(tgt) w.recovered(t, tgt, "woken cold") w.finish(t) } // wRetryUnresolved (R8-5): an upload times out, its retry succeeds, the // original stays unresolved. func wRetryUnresolved(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) loc := w.claim.Holder.Location w.appWrite(b) key := ltxKey(loc, "", 0, b.DB.Pos+1, b.DB.Pos+1) var original *request w.hold = func(r *request) bool { if r.key == key && original == nil { original = r return true // the first attempt alone is held } return r == original } w.replicate(b) for i := 0; i <= uploadTimeout; i++ { w.tick(func() { w.replicate(b) }) // the client times out and retries the same bytes; the retry lands } if original == nil || w.buckets[b.Region].current(key) == nil { t.Fatalf("witness: the retry did not land: %s", w.ltxShape(b.Region, dataKey(loc, "", ""))) } w.idleStop(b) sk := closedKey(loc, "", b.DB.Session) for i := 0; i < 10; i++ { w.tick(func() { w.replicate(b) }) if w.buckets[b.Region].current(sk) != nil { w.violate("INV-2 (witness): box %d wrote its certificate while its original upload %s was unresolved (R8-5)", b.ID, key) return } } w.hold = nil w.completeHeld(key) w.finish(t) } // ---------- rev 7.10 ---------- // wStaleLocalAfterClose (claim rev 6.9, R9-1): a valid certificate and a // stale local database. func wStaleLocalAfterClose(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) stale := b.DB.clone() // a cached copy through N w.appWrite(b) w.replicate(b) // N+1, durable w.idleStop(b) // the certificate names N+1 as the remote maximum loc := w.claim.Holder.Location if w.buckets[b.Region].current(closedKey(loc, w.claim.Holder.Gen, b.DB.Session)) == nil { t.Fatalf("witness: no certificate after the clean close") } b.DB = stale w.logf("witness: box %d's local database is a cached copy without the last acknowledged write", b.ID) w.recovered(t, b, "woken on the certificate") w.appWrite(b) w.replicate(b) // the next upload: skipped at the remote position if the stale copy was kept w.checkLocal(w.claim, b, b.DB) w.checkDurable(w.claim, "after the wake on the stale copy") w.finish(t) } // wSilentLoss (claim rev 6.9, R9-2): an acknowledged, unuploaded write and // a crash; the next admission declares the loss. func wSilentLoss(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) w.appWrite(b) // acknowledged, never uploaded w.crash(b) w.recovered(t, b, "woken after the crash") if w.stats["writes_lost declared"] == 0 && on("writes-lost") { t.Fatalf("witness: no writes_lost record after the crash") } w.checkLocal(w.claim, b, b.DB) w.finish(t) } // wStaleClosureDelete (claim rev 6.9, R9-4): an admission closure computed // under serving resumes after a delete began. func wStaleClosureDelete(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) w.idleStop(b) stale := w.claim.clone() // the wake's read, under serving w.userDelete() if w.claim.Op.Kind != "deleting" { t.Fatalf("witness: the delete did not begin: %s", w.state()) } // the claim library's BeginDelete preserves session, generation and the // executor (R9-4); this model's delete names no executor, so the // witness keeps the serving box as op.exec, as the library does w.cas(w.claim, func(n *claim) bool { n.Op.Exec = b.ID; return true }) w.logf("witness: a stalled wake resumes with its serving-time read of the claim") if w.spawn(b, stale, stale.Holder.Gen, false) { w.logf("witness: the stale closure admitted a writer during the delete") } w.finish(t) } // wMaintenanceRetry (R9-5): a compaction PUT retried after a timeout. func wMaintenanceRetry(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) loc := w.claim.Holder.Location gen := w.claim.Holder.Gen var original *request w.hold = func(r *request) bool { if r.kind == rPut && r.b != nil && r.b.Level == 1 && original == nil { original = r return true // the first compaction attempt alone is held } return r == original } for i := 0; i < 3; i++ { w.appWrite(b) w.replicate(b) // three level-0 files: compaction issues its level-1 PUT, held } if original == nil { t.Fatalf("witness: no compaction PUT was issued: %s", w.ltxShape(b.Region, dataKey(loc, gen, ""))) } for i := 0; i <= uploadTimeout; i++ { w.tick(func() { w.replicate(b) }) // the client times out; the next compaction pass retries and lands } if len(w.currentLTX(w.buckets[b.Region], dataKey(loc, gen, ""), 1)) == 0 { // the retry may compact a wider range than the original, under its own key t.Fatalf("witness: the compaction retry did not land: %s", w.ltxShape(b.Region, dataKey(loc, gen, ""))) } w.idleStop(b) sk := closedKey(loc, gen, b.DB.Session) for i := 0; i < 10; i++ { w.tick(func() { w.replicate(b) }) if w.buckets[b.Region].current(sk) != nil { w.violate("INV-2 (witness): box %d wrote its certificate while its original compaction PUT %s was unresolved (R9-5)", b.ID, original.key) return } } w.hold = nil w.completeHeld(original.key) w.finish(t) } // wLostResponse (R9-5): a snapshot PUT whose response is lost. func wLostResponse(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) loc := w.claim.Holder.Location gen := w.claim.Holder.Gen var original *request w.hold = func(r *request) bool { if r.kind == rPut && r.b != nil && r.b.Level == 9 && original == nil { original = r return true // the snapshot PUT alone is held } return r == original } for i := 0; i < 3; i++ { w.appWrite(b) w.replicate(b) // compaction rotates a snapshot, whose PUT is held } if original == nil { t.Fatalf("witness: no snapshot PUT was issued: %s", w.ltxShape(b.Region, dataKey(loc, gen, ""))) } for i := 0; i <= uploadTimeout; i++ { w.tick(func() { w.replicate(b) }) // the client gives up on it } w.hold = nil w.completeHeld(original.key) // the server completes it after the client gave up: a lost response w.idleStop(b) sk := closedKey(loc, gen, b.DB.Session) for i := 0; i < 10; i++ { w.tick(func() { w.replicate(b) }) if w.buckets[b.Region].current(sk) != nil { w.violate("INV-2 (witness): box %d wrote its certificate while the response to its snapshot PUT %s was lost (R9-5)", b.ID, original.key) return } } w.finish(t) } // ---------- rev 7.11 ---------- // ackInto acknowledges one write into b's database without a main process: // a background worker's work (R10-1). func (w *world) ackInto(b *box, inc int) int { db := b.DB w.nextW++ wr := w.nextW w.commit(db, wr) sess, gen := w.sessionOf(b) w.acks = append(w.acks, ack{W: wr, Inc: inc, Box: b.ID, Session: sess, Gen: gen, At: w.now, Kind: "write"}) w.writeInc[wr] = inc w.logf("witness: a background worker on box %d acknowledged %d", b.ID, wr) return wr } // wAckBeforeAdmission (claim rev 6.10, R10-1): a background acknowledgement // right after the app starts, then a crash before replication opens. func wAckBeforeAdmission(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) w.idleStop(b) // a certified close: the next admission is warm armed := true w.startHook = func(x *box) bool { if x != b || !armed || x.DB == nil { return false } armed = false w.ackInto(x, 1) w.crash(x) return true } w.wake(b) w.startHook = nil w.recovered(t, b, "woken after the crash") w.checkLocal(w.claim, b, b.DB) w.finish(t) } // wBaselineParked (claim rev 6.10, R10-2): a crash between the admitting // CAS and the first upload, then the predecessor's retirement. func wBaselineParked(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) w.appWrite(b) w.replicate(b) w.crash(b) // no certificate: the next admission is cold, into a fresh generation armed := true w.startHook = func(x *box) bool { if x != b || !armed { return false } armed = false w.crash(x) // before the first upload: the new generation stays empty return true } w.wake(b) w.startHook = nil if g := w.claim.Holder.Gen; g == "" || len(w.buckets[b.Region].keys(dataKey(w.claim.Holder.Location, g, ""))) != 0 { t.Fatalf("witness: expected an empty fresh generation, have %q: %s", g, w.state()) } // the predecessor's retirement, queued at the CAS under the mutation, // runs out its quiet time w.reach(t, 200, "chores settled", func() bool { return len(w.claim.Obl) == 0 }, w.act(b), w.recoveryPass) w.recovered(t, b, "woken after the crash") w.checkLocal(w.claim, b, b.DB) w.checkDurable(w.claim, "after the recovery") w.finish(t) } // wFirstUploadRetry (R10-7): the fresh generation's first upload retried. func wFirstUploadRetry(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) w.wake(b) w.appWrite(b) w.replicate(b) w.crash(b) var original *request w.hold = func(r *request) bool { if r.kind == rPut && r.b != nil && r.b.Level == 0 && r.b.Min == 1 && r.b.Max == 1 && r.b.Gen != "" && original == nil { original = r return true // the first upload's first attempt alone is held } return r == original } w.wake(b) for i := 0; i <= uploadTimeout+1; i++ { w.tick(w.act(b)) // the client times out; the retry lands and the start completes } if original == nil { t.Fatalf("witness: no first upload was issued: %s", w.state()) } if !hasMain(b) { t.Fatalf("witness: the writer did not start after the retry: %s", w.state()) } loc, gen := w.claim.Holder.Location, w.claim.Holder.Gen w.idleStop(b) sk := closedKey(loc, gen, b.DB.Session) for i := 0; i < 10; i++ { w.tick(func() { w.replicate(b) }) if w.buckets[b.Region].current(sk) != nil { w.violate("INV-2 (witness): box %d wrote its certificate while its first upload %s was unresolved (R10-7)", b.ID, original.key) return } } w.hold = nil w.completeHeld(original.key) w.finish(t) } // wAnchorRetry (R10-7): a warm admission's anchor retried. func wAnchorRetry(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) loc := w.claim.Holder.Location // the generation's newest snapshot stands above its level-0 maximum // (retention expired the files above it): a warm restore lands at the // snapshot's position and needs the anchor there snap := snapshotOf(b.DB, 1) snap.Max = 2 w.nextW++ wr := w.nextW sess, gen := w.sessionOf(b) w.acks = append(w.acks, ack{W: wr, Inc: 1, Box: b.ID, Session: sess, Gen: gen, At: w.now, Kind: "write"}) w.writeInc[wr] = 1 w.txs[wr] = tx{W: wr, TX: 3, Key: fmt.Sprintf("k%d", wr), Val: wr} snap.Pages[fmt.Sprintf("k%d", wr)] = wr snap.TXs = append(snap.TXs, wr) k := snapKey(loc, "", 2) w.buckets[b.Region].objs[k] = append(w.buckets[b.Region].objs[k], &version{ID: w.newVer(), B: snap}) w.markDurable(k, snap) w.buckets[b.Region].objs[closedKey(loc, "", w.claim.Holder.Session)][0].B.TX = 2 // the certificate names the snapshot's position (the serving fixture's session, not the legacy identity) var original *request w.hold = func(r *request) bool { if r.kind == rPut && r.b != nil && r.b.Level == 0 && r.b.Min == 2 && r.b.Max == 2 && original == nil { original = r return true // the anchor's first attempt alone is held } return r == original } w.wake(b) for i := 0; i <= uploadTimeout+1; i++ { w.tick(w.act(b)) } if original == nil { t.Fatalf("witness: no anchor PUT was issued: %s%s", w.state(), w.boxesState()) } if !hasMain(b) { t.Fatalf("witness: the writer did not start after the anchor retry: %s", w.state()) } w.idleStop(b) sk := closedKey(loc, "", b.DB.Session) for i := 0; i < 10; i++ { w.tick(func() { w.replicate(b) }) if w.buckets[b.Region].current(sk) != nil { w.violate("INV-2 (witness): box %d wrote its certificate while its anchor %s was unresolved (R10-7)", b.ID, original.key) return } } w.hold = nil w.completeHeld(original.key) w.finish(t) } // wSealReturn (rev 7.11 §7.8): the source's last upload is in flight at // the cut; the rollback's return must carry the seal. func wSealReturn(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) loc, gen0 := w.claim.Holder.Location, w.claim.Holder.Gen w.hold = func(r *request) bool { // every level-0 upload of the source's own generation is held: its // replica stops short of the stopped database return r.kind == rPut && r.region == src.Region && r.b != nil && r.b.Level == 0 && genOf(loc, r.key) == gen0 } w.appWrite(src) w.replicate(src) w.moveTo(tgt.Region) if !w.reach(t, 600, "landing built", func() bool { c := w.claim return c.Op.Kind == "landing" && (c.Op.LandPhase == "local" || c.Op.LandPhase == "config" || c.Op.LandPhase == "probing") }, w.act(src, tgt), w.recoveryPass) { return } if w.claim.Op.SrcCovered { t.Fatalf("witness: the seal found the source's replica complete; the held upload was not held: %s", w.state()) } w.rollback(w.claim, "configuration changed during the move") // the source's recovery admission decides with the replica still short w.reach(t, 800, "source admitted after the rollback", func() bool { c := w.claim return len(w.violations) > 0 || c.Op.Kind == "serving" || c.Op.Kind == "restoring" && (c.Op.SrcPhase == "probed" || c.Op.SrcPhase == "opened") }, w.act(src, tgt), w.recoveryPass, w.runConsole) w.hold = nil w.completeHeld(dataKey(loc, gen0, "")) w.finish(t) } // ---------- rev 7.12 ---------- // wCleanReturnIdentity (claim rev 6.12, R11-4): a clean rollback's return // and the identity the source's re-admission journals. func wCleanReturnIdentity(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) w.appWrite(src) w.replicate(src) // the source's replica covers everything it acknowledged: src_covered at the seal w.landProbed(t, src, tgt) tl := lastAdmission(w.claim.Holder) if tl == nil || tl.Box != tgt.ID { t.Fatalf("witness: the target's probe is not the last admission: %s", w.state()) } tgtSession, tgtGen := tl.Session, tl.Gen if !w.claim.Op.SrcCovered { t.Fatalf("witness: the seal did not record src_covered: %s", w.state()) } w.rollback(w.claim, "settle check failed") // the target wrote nothing: a clean rollback before := w.stats["writes_lost declared"] w.reach(t, 800, "source re-admitted", func() bool { c := w.claim return len(w.violations) > 0 || c.Op.Kind == "serving" || c.Op.Kind == "restoring" && (c.Op.SrcPhase == "probed" || c.Op.SrcPhase == "opened") }, w.act(src, tgt), w.recoveryPass, w.runConsole) if len(w.violations) > 0 { return } e := lastAdmission(w.claim.Holder) if e == nil || e.Box != src.ID { t.Fatalf("witness: the source's re-admission is not the last admission: %s", w.state()) } if e.Predecessor.Session != tgtSession || e.Predecessor.Box != tgt.ID || e.Predecessor.Gen != tgtGen { w.violate("INV-16 (witness): the source journalled predecessor {session %d, box %d, generation %q}; the target's writer was {session %d, box %d, generation %q}", e.Predecessor.Session, e.Predecessor.Box, e.Predecessor.Gen, tgtSession, tgt.ID, tgtGen) return } if e.Coverage != "clean-return" || w.stats["writes_lost declared"] != before { w.violate("INV-16 (witness): a clean return with src_covered declared a loss (coverage %q, %d records)", e.Coverage, w.stats["writes_lost declared"]-before) return } w.finish(t) } // wOriginSwept (R11-1): origin, an unfinished admission, the ordinary // sweep, then the recovery. func wOriginSwept(t *testing.T, w *world) { b0 := w.boxes[0] w.legacy(b0, 1) w.tick(func() { w.reconcile(b0) }) // adoption if w.claim == nil { t.Fatalf("witness: not adopted") } w.reach(t, 400, "adoption settled", func() bool { return w.claim.oblFor("adopt") == 0 }, w.actAll(), w.recoveryPass) if len(w.violations) > 0 { return } // the pre-release writer left no certificate (the helper's is for a // warm first wake): the first wake is cold, from the origin delete(w.buckets[b0.Region].objs, closedKey(w.claim.Holder.Location, "", 0)) armed := true w.startHook = func(x *box) bool { if x != b0 || !armed { return false } armed = false w.crash(x) // before the first upload: the new generation is empty, the marker absent, the origin the baseline return true } w.wake(b0) // the first cold admission from the origin w.startHook = nil if g := w.claim.Holder.Gen; g == "" { t.Fatalf("witness: no cold admission happened: %s", w.state()) } // the ordinary sweep runs before any recovery: every box's obligation // runner, no wakes for i := 0; i < 3*horizonH; i++ { w.tick(func() { for _, b := range w.liveBoxes() { w.obligationRunner(b) } }) if len(w.violations) > 0 { return } } // the recovery: under the mutation the swept origin is a covered local // baseline since rev 7.14 (claim rev 6.22 §6.2a), and the start refuses // with an alert rather than restoring nothing; either way the data is // unreachable, which is the failure the witness names if !w.drive(120, func() bool { return hasMain(b0) }, w.act(b0), w.recoveryPass, func() { w.wake(b0) }) { if len(w.violations) == 0 { w.violate("INV-2 (witness): the recovery cannot start, its origin baseline was retired under the unfinished admission (%d starts refused as a covered local baseline)", w.stats["start refused: covered local baseline"]) } return } w.checkLocal(w.claim, b0, b0.DB) w.checkDurable(w.claim, "after the recovery") w.finish(t) } // ---------- rev 7.14 ---------- // wParkScopeSurvivesRestart (claim rev 6.15 §2, R13-4): a committed move's // source-region park binds its scope, with the evidence time, in the // claim; the region's agent restarts mid-park; the acknowledgement comes // at the original evidence time plus the horizon, not the restart's. func wParkScopeSurvivesRestart(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) w.appWrite(src) w.commitLanding(t, src, tgt) if len(w.violations) > 0 { return } t0 := w.now var id string deadline := w.claim.Op.StopAt + horizonH // the cut's stop evidence plus H (claim rev 6.23: the persisted original bound) for _, o := range w.claim.Obl { if o.Kind == "park-superseded" && o.Region == src.Region { id = o.ID if o.Scope != nil { deadline = o.Scope.deadline() } } } if id == "" { t.Fatalf("witness: no park-superseded for the source region after the commit: %s", w.state()) } // the park runs for a while, then the source region's agent restarts // before the deadline restart := deadline - 20 if restart < t0+5 { restart = t0 + 5 } for w.now < restart { w.tick(w.act(src, tgt), w.runConsole, w.recoveryPass) if len(w.violations) > 0 { return } } if !hasObl(w.claim.Obl, id) { t.Fatalf("witness: the park %s acknowledged before the restart, at %d (commit at %d, deadline %d): the horizon did not hold", id, w.now, t0, deadline) } w.crash(src) // a new agent process: the box-local evidence map is gone w.reach(t, 400, "the source region's park acknowledged", func() bool { return !hasObl(w.claim.Obl, id) }, w.act(src, tgt), w.runConsole, w.recoveryPass) if len(w.violations) > 0 { return } if w.now > deadline+30 { w.violate("INV-9 (witness): the park %s was acknowledged at %d, after its persisted deadline %d and slack: the restart at %d started the horizon again from the restart's clock", id, w.now, deadline, restart) return } w.finish(t) } // wStagingScopeDeadline (claim rev 6.23 §2, R15-1): a staging lane's scope // persists the seal bound, and its deadline is that bound plus H; a // cleanup that first runs after the deadline, through an agent restart, // acknowledges at once rather than waiting a fresh horizon from its own // clock (the round's example: sealed at 100, deadline 560, cleanup at 600 // must not wait until 660). func wStagingScopeDeadline(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) w.appWrite(src) w.commitLanding(t, src, tgt) if len(w.violations) > 0 { return } var id string deadline := w.claim.Op.SealQuiet for _, o := range w.claim.Obl { if o.Kind == "park-staging" && o.Region == tgt.Region { id = o.ID if o.Scope != nil { deadline = o.Scope.deadline() } } } if id == "" { t.Fatalf("witness: no staging park for the target region after the commit: %s", w.state()) } // the target region's cleanup is delayed: its obligation runner does // not run until 40 steps past the deadline (the target's worker and // the source run as usual) for w.now < deadline+40 { w.tick(func() { w.worker(src); w.obligationRunner(src); w.worker(tgt) }, w.runConsole, w.recoveryPass) if len(w.violations) > 0 { return } } if !hasObl(w.claim.Obl, id) { t.Fatalf("witness: the staging park %s was acknowledged before its cleanup ran: %s", id, w.state()) } w.crash(tgt) // the cleanup begins under a new agent process start := w.now w.reach(t, 200, "the staging lane parked", func() bool { return !hasObl(w.claim.Obl, id) }, w.act(src, tgt), w.runConsole, w.recoveryPass) if len(w.violations) > 0 { return } if w.now < deadline { w.violate("INV-9 (witness): the staging park %s was acknowledged at %d, before its persisted deadline %d", id, w.now, deadline) return } if w.now > start+20 { w.violate("INV-9 (witness): the staging park %s was acknowledged at %d; its persisted deadline %d had passed when the cleanup began at %d, yet it waited a fresh horizon (bound at the cleanup's clock, until %d)", id, w.now, deadline, start, start+horizonH) return } w.finish(t) } // ---------- rev 7.17 ---------- // recreated drives a delete of the serving host and a create of the next // incarnation in region r, and returns once it serves. func (w *world) recreated(t *testing.T, r int) { w.userDelete() w.reach(t, 800, "host deleted and free", func() bool { c := w.claim return c != nil && c.Holder == nil && c.Op.Kind == "" && len(c.Obl) == 0 && w.rec == nil }, w.actAll(), w.runConsole, w.recoveryPass) if len(w.violations) > 0 { return } w.nextInc++ w.console = append(w.console, &consolePlan{Kind: "create", Host: "h", App: app0, OpID: w.newID("cr"), Inc: w.nextInc, Region: r}) w.reach(t, 800, "the next incarnation serves", func() bool { c := w.claim return len(w.violations) > 0 || c != nil && c.Holder != nil && c.Op.Kind == "serving" && c.Holder.Inc == w.nextInc }, w.actAll(), w.runConsole, w.recoveryPass) } // wSweepScopeMembership (claim rev 6.24 §2, R16-2): the serving // incarnation's sweep finds a late object of a deleted incarnation; the // chore that parks it is scoped to that incarnation's own location and // archives under its incarnation, never under the serving one's legacy // scope. func wSweepScopeMembership(t *testing.T, w *world) { b0 := w.boxes[0] w.serve(b0, 1, app0) w.wake(b0) w.appWrite(b0) w.recreated(t, b0.Region) if len(w.violations) > 0 { return } if w.claim.Holder.Inc != 2 { t.Fatalf("witness: incarnation %d serves, want 2: %s", w.claim.Holder.Inc, w.state()) } // a late object of incarnation 1 lands under its own location old := locationFor(1, false) k := ltxKey(old, "old", 0, 3, 3) w.buckets[b0.Region].objs[k] = append(w.buckets[b0.Region].objs[k], &version{ID: w.newVer(), B: &blob{Kind: "ltx", Level: 0, Min: 3, Max: 3, Inc: 1, Pages: map[string]int{}}}) var scope *parkScope w.reach(t, 600, "the late object parked", func() bool { for _, o := range w.claim.Obl { if o.Kind == "park-sweep" && o.Region == b0.Region && o.Scope != nil && strings.HasPrefix(k, o.Prefix) { cp := *o.Scope scope = &cp } } return len(w.violations) > 0 || w.buckets[b0.Region].current(k) == nil }, w.actAll(), w.recoveryPass) if len(w.violations) > 0 { return } if scope == nil { t.Fatalf("witness: no scoped sweep chore covered %s: %s", k, w.state()) } if scope.Location != scopeLocation(old) || scope.Inc != 1 { w.violate("INV-23 (witness): the sweep parked %s under scope %s (incarnation %d); the object's own location is %s, incarnation 1", k, scope.Location, scope.Inc, scopeLocation(old)) return } w.finish(t) } // TestLegacyLostTargetReturn (claim rev 6.24, R16-3) is the legacy // identity through a lost-target return: an adopted host whose pre-claim // writer (session 0, generation "") left a write its replica never got; // no wake before the move, so the cut session is 0 and src_covered is // false; the target is admitted cold and declared lost; the source's // return declares the target's session and the source's cut session 0, in // additional_writes_lost, and INV-24 accepts the legacy identity. func TestLegacyLostTargetReturn(t *testing.T) { w := newWitness() defer func() { if t.Failed() { dump(t, w) } }() b0, b1 := w.boxes[0], w.boxes[1] w.legacy(b0, 1) w.tick(func() { w.reconcile(b0) }) // adoption if w.claim == nil || w.claim.Holder.Session != 0 { t.Fatalf("not adopted with the legacy identity: %s", w.state()) } w.reach(t, 400, "adoption settled", func() bool { return w.claim.oblFor("adopt") == 0 }, w.actAll(), w.recoveryPass) // the pre-claim writer's last write, acknowledged, never uploaded: the // origin's level-0 uploads are held, so the cut's flush cannot land it loc := w.claim.Holder.Location w.hold = func(r *request) bool { return r.kind == rPut && r.region == b0.Region && r.b != nil && r.b.Level == 0 && genOf(loc, r.key) == "" } w.nextW++ w.commit(b0.DB, w.nextW) w.acks = append(w.acks, ack{W: w.nextW, Inc: 1, Box: b0.ID, Session: 0, Gen: "", At: w.now, Kind: "write"}) w.writeInc[w.nextW] = 1 w.moveTo(b1.Region) w.reach(t, 600, "landing probed", func() bool { c := w.claim return len(w.violations) > 0 || c.Op.Kind == "landing" && c.Op.LandPhase == "probed" && hasMain(b1) }, w.act(b0, b1), w.recoveryPass) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } if w.claim.Op.SrcCovered || w.claim.Op.CutSession != 0 { t.Fatalf("the cut must be session 0 with src_covered false: covered=%v cut=%d", w.claim.Op.SrcCovered, w.claim.Op.CutSession) } tgtSession := lastAdmission(w.claim.Holder).Session w.stop(b1) w.reach(t, 400, "declared lost", func() bool { return contains(w.claim.Lost, b1.ID) }, w.act(b0), w.recoveryPass, w.operator) w.replaceDestroyed() w.reach(t, 800, "the source's return admitted", func() bool { c := w.claim l := lastAdmission(c.Holder) return len(w.violations) > 0 || c.Op.Kind == "serving" || c.Op.Kind == "restoring" && l != nil && l.Box == b0.ID && l.Session > tgtSession }, w.act(b0), w.recoveryPass, w.runConsole, w.operator) w.hold = nil w.completeHeld(dataKey(loc, "", "")) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } e := lastAdmission(w.claim.Holder) seen := map[[2]int]int{} for _, x := range declarationsOf(e) { seen[[2]int{x.Box, x.Session}]++ } if seen[[2]int{b1.ID, tgtSession}] != 1 || seen[[2]int{b0.ID, 0}] != 1 { t.Fatalf("the return must declare the target's session %d and the source's cut session 0 once each: %v (record %+v)", tgtSession, seen, *e) } t.Logf("declared %v at %s; legacy declarations %d", seen, loc, w.stats["writes_lost: the legacy identity (session 0)"]) w.finish(t) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } } // TestForeignManifestReplayRefused (R17-1): a persisted manifest naming // another incarnation's keys, replayed under a valid scope, is refused by // INV-23 and nothing it names is deleted. The state is constructed: no // schedule of the model produces such a manifest. func TestForeignManifestReplayRefused(t *testing.T) { w := newWitness() defer func() { if t.Failed() { dump(t, w) } }() b0 := w.boxes[0] w.serve(b0, 1, app0) w.wake(b0) w.appWrite(b0) w.recreated(t, b0.Region) if len(w.violations) > 0 || w.claim.Holder == nil || w.claim.Holder.Inc != 2 { t.Fatalf("incarnation 2 does not serve: %s", w.state()) } // a late object of incarnation 1, and a sweep chore of incarnation 2's // own location whose persisted manifest wrongly names it foreign := ltxKey(locationFor(1, false), "old", 0, 3, 3) w.buckets[b0.Region].objs[foreign] = append(w.buckets[b0.Region].objs[foreign], &version{ID: w.newVer(), B: &blob{Kind: "ltx", Level: 0, Min: 3, Max: 3, Inc: 1, Pages: map[string]int{}}}) fv := w.buckets[b0.Region].current(foreign).ID o := obligation{ID: "obx", Op: fmt.Sprintf("session:%d", w.claim.Holder.Session), Kind: "park-sweep", Region: b0.Region, Box: -1, Prefix: locationFor(2, false), Ret: "sweep", Scope: &parkScope{Location: scopeLocation(locationFor(2, false)), Inc: 2, EvidenceAt: w.now - horizonH, RequestLimit: requestLimitH}} man := &blob{Kind: "manifest", Refs: []ref{{Region: b0.Region, Key: foreign, Ver: fv}}, Dels: []ref{{Region: b0.Region, Key: foreign, Ver: fv}}} w.buckets[b0.Region].objs[o.Dest()+"manifest"] = []*version{{ID: w.newVer(), B: man}} w.cas(w.claim, func(n *claim) bool { n.Obl = append(n.Obl, o); return true }) // one step of the chore: the replay of its persisted manifest (a later // at-rest sweep may park the object legitimately under incarnation 1's // own scope, which is not in question here) w.tick(func() { w.obligationRunner(b0) }) found := false for _, v := range w.violations { if strings.Contains(v, "INV-23") && strings.Contains(v, foreign) { found = true } } if !found { t.Fatalf("the replayed foreign manifest was not refused by INV-23: %v", w.violations) } w.completeDue(true) if w.buckets[b0.Region].byID(foreign, fv) == nil { t.Fatalf("the foreign object %s@%d was deleted by the replay", foreign, fv) } t.Logf("refused: %s", w.violations[0]) } // TestStagingSurvivesLegacyPark (claim rev 6.24 §2, R16-1): a legacy host's // earlier stay in the target region is parked by the landing's install // phase while the move's sealed staging sits beside it under moves/; the // park is scoped to the legacy instance location and the staging survives // for the build. func TestStagingSurvivesLegacyPark(t *testing.T) { w := newWitness() defer func() { if t.Failed() { dump(t, w) } }() b0, b1 := w.boxes[0], w.boxes[1] w.legacy(b0, 1) // the fixture leaves an earlier stay's replica part in region 1 w.tick(func() { w.reconcile(b0) }) w.reach(t, 400, "adoption settled", func() bool { return w.claim.oblFor("adopt") == 0 }, w.actAll(), w.recoveryPass) w.recovered(t, b0, "running after adoption") w.appWrite(b0) w.moveTo(b1.Region) w.reach(t, 600, "landing probed", func() bool { c := w.claim return len(w.violations) > 0 || c.Op.Kind == "landing" && c.Op.LandPhase == "probed" && hasMain(b1) }, w.act(b0, b1), w.recoveryPass) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } op := w.claim.Op for _, r := range []ref{op.SealDB, op.SealFiles} { if w.buckets[r.Region].byID(r.Key, r.Ver) == nil || w.buckets[r.Region].current(r.Key) == nil { t.Fatalf("the sealed staging %s@%d is gone from region %d after the install park", r.Key, r.Ver, r.Region) } } t.Logf("staging %s and %s survived the legacy instance park; landing probed", op.SealDB.Key, op.SealFiles.Key) w.finish(t) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } } // wFreeSweepVsCreate (claim rev 6.15 §6.2a, R13-4): a deleted host's // region keeps late residue; the free host's sweep runs as a holderless // parking op, and a create requested meanwhile waits for FreeAfterPark. // Without the op the create claims the host over the outstanding park // (INV-20). func wFreeSweepVsCreate(t *testing.T, w *world) { b0 := w.boxes[0] w.serve(b0, 1, app0) w.wake(b0) w.appWrite(b0) loc := w.claim.Holder.Location w.userDelete() w.reach(t, 800, "host deleted and free", func() bool { c := w.claim return c != nil && c.Holder == nil && c.Op.Kind == "" && len(c.Obl) == 0 && w.rec == nil }, w.actAll(), w.runConsole, w.recoveryPass) if len(w.violations) > 0 { return } // a replica PUT accepted before the delete's park lands now k := ltxKey(loc, "", 0, 7, 7) w.buckets[b0.Region].objs[k] = append(w.buckets[b0.Region].objs[k], &version{ID: w.newVer(), B: &blob{Kind: "ltx", Level: 0, Min: 7, Max: 7, Inc: 1, Pages: map[string]int{}}}) // the create is requested at once; the sweep finds the residue on its // next pass w.nextInc++ w.console = append(w.console, &consolePlan{Kind: "create", Host: "h", App: app0, OpID: w.newID("cr"), Inc: w.nextInc, Region: 1}) w.reach(t, 800, "the create completed", func() bool { c := w.claim return len(w.violations) > 0 || c != nil && c.Holder != nil && c.Op.Kind == "serving" }, w.actAll(), w.runConsole, w.recoveryPass) if len(w.violations) > 0 { return } if w.stats["holderless sweeps"] == 0 && on("holderless-park") { t.Fatalf("witness: no holderless sweep ran before the create: %s", w.state()) } w.finish(t) } // wCoveredLocalBaseline (claim rev 6.22 §6.2a, R13-1): an unfinished run // whose link in this region is covered, its generation retired. The walk // must refuse the start and alert; reading objects alone, as rev 7.13 // did, it passes over the empty link and restores the marker's generation, // retired too, as an empty database (INV-2). func wCoveredLocalBaseline(t *testing.T, w *world) { b0 := w.boxes[0] w.serve(b0, 1, app0) w.wake(b0) w.appWrite(b0) w.replicate(b0) loc := w.claim.Holder.Location // a cold admission into a fresh generation g1 that runs and publishes: // the serving session closes cleanly, its certificate is removed, the // next wake is cold w.idleStop(b0) w.reach(t, 200, "closed", func() bool { return !hasMain(b0) && (b0.DB == nil || !b0.DB.Closing) }, w.act(b0)) delete(w.buckets[b0.Region].objs, closedKey(loc, "", w.claim.Holder.Session)) w.wake(b0) g1 := w.claim.Holder.Gen if g1 == "" { t.Fatalf("witness: no cold admission after the certificate was removed: %s", w.state()) } w.reach(t, 200, "g1 published", func() bool { bg, _ := w.bucketGen(b0, loc); return bg == g1 }, w.act(b0)) w.idleStop(b0) w.reach(t, 200, "g1 closed", func() bool { return !hasMain(b0) && (b0.DB == nil || !b0.DB.Closing) }, w.act(b0)) // a second cold admission, g2, that dies before its first upload: the // marker still names g1, the run is g2 -> g1 delete(w.buckets[b0.Region].objs, closedKey(loc, g1, w.claim.Holder.Session)) armed := true w.startHook = func(x *box) bool { if x != b0 || !armed { return false } armed = false w.crash(x) return true } w.wake(b0) w.startHook = nil g2 := w.claim.Holder.Gen if g2 == g1 || g2 == "" { t.Fatalf("witness: no second cold admission: %s", w.state()) } // the constructed state: g2's record is covered and g1 is retired in // this region (an operator parked it, or a chore it should not have had) w.cas(w.claim, func(n *claim) bool { for i := range n.Holder.Admissions { if n.Holder.Admissions[i].Gen == g2 { n.Holder.Admissions[i].Covered = true } } return true }) bk := w.buckets[b0.Region] for _, k := range bk.keys(dataKey(loc, g1, "")) { if genOf(loc, k) == g1 { bk.objs[k] = nil // parked: the key keeps its entry with no version } } for i := 0; i < 80; i++ { w.tick(w.act(b0), w.recoveryPass, func() { w.wake(b0) }) if len(w.violations) > 0 || hasMain(b0) { break } } if hasMain(b0) { w.checkLocal(w.claim, b0, b0.DB) // started on nothing: INV-2 return } if w.stats["start refused: covered local baseline"] == 0 { t.Fatalf("witness: the host neither started nor refused a covered local baseline: %s", w.state()) } } // ---------- rev 7.15 ---------- // wIntermediateBaseline (R14-1): the run walk selects a generation of the // run that holds an object while the marker still names the run's // baseline; the start must restore what the walk selected, rooted at // [1, 1], as the oracle does. func wIntermediateBaseline(t *testing.T, w *world) { b0 := w.boxes[0] w.serve(b0, 1, app0) w.wake(b0) w.appWrite(b0) w.replicate(b0) loc := w.claim.Holder.Location w.idleStop(b0) w.reach(t, 200, "closed", func() bool { return !hasMain(b0) && (b0.DB == nil || !b0.DB.Closing) }, w.act(b0)) delete(w.buckets[b0.Region].objs, closedKey(loc, "", w.claim.Holder.Session)) // R: a cold admission whose first upload is held in flight w.hold = func(r *request) bool { g := genOf(loc, r.key) return r.kind == rPut && r.region == b0.Region && r.b != nil && r.b.Level == 0 && g != "" && g != "-" } w.wake(b0) gR := w.claim.Holder.Gen if gR == "" { t.Fatalf("witness: no cold admission R: %s", w.state()) } w.reach(t, 30, "R's first upload issued", func() bool { return b0.open != nil && b0.open.req != nil }, w.act(b0)) w.crash(b0) // R dies with its upload pending; the marker still names S w.hold = nil // R2: admitted over the empty R, dies before uploading armed := true w.startHook = func(x *box) bool { if x != b0 || !armed { return false } armed = false w.crash(x) return true } w.wake(b0) w.startHook = nil gR2 := w.claim.Holder.Gen if gR2 == gR || gR2 == "" { t.Fatalf("witness: no second cold admission R2: %s", w.state()) } // R's delayed upload lands: R holds an object, R2 none, the marker names S if w.completeHeld(dataKey(loc, gR, "")) == 0 { t.Fatalf("witness: R's upload was not held: %s", w.state()) } // the next start: R2 -> R -> S selects R if !w.drive(120, func() bool { return hasMain(b0) }, w.act(b0), w.recoveryPass, func() { w.wake(b0) }) { if len(w.violations) == 0 { w.violate("INV-3 (witness): the start cannot restore %q, the baseline the run walk selected, while the marker names %q (%d restores refused)", gR, "", w.stats["restore refused"]) } return } if w.stats["restore: run generation rooted"] == 0 { t.Fatalf("witness: the start did not restore the selected run generation: %v", w.stats) } w.checkLocal(w.claim, b0, b0.DB) w.checkDurable(w.claim, "after the recovery") w.finish(t) } // lostTargetReturn is the common opening of the R14-2 witnesses: the // source's level-0 uploads are held so src_covered is false and its cut // session is uncertified; the landing proceeds to the given point; the // target is destroyed and declared lost; the source's return is admitted. // It returns the source's return record. func (w *world) lostTargetReturn(t *testing.T, probed bool) *admissionRecord { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) loc, gen0 := w.claim.Holder.Location, w.claim.Holder.Gen w.hold = func(r *request) bool { return r.kind == rPut && r.region == src.Region && r.b != nil && r.b.Level == 0 && genOf(loc, r.key) == gen0 } w.appWrite(src) w.replicate(src) w.moveTo(tgt.Region) if probed { w.reach(t, 600, "landing probed", func() bool { c := w.claim return c.Op.Kind == "landing" && c.Op.LandPhase == "probed" && hasMain(tgt) }, w.act(src, tgt), w.recoveryPass) } else { w.reach(t, 600, "landing built, no admission yet", func() bool { c := w.claim return c.Op.Kind == "landing" && (c.Op.LandPhase == "local" || c.Op.LandPhase == "config" || c.Op.LandPhase == "probing") && tgt.open == nil }, w.act(src, tgt), w.recoveryPass) } if len(w.violations) > 0 { return nil } if w.claim.Op.SrcCovered { t.Fatalf("witness: the seal found the source's replica complete; the held upload was not held: %s", w.state()) } w.stop(tgt) // the cloud destroys the target w.reach(t, 400, "declared lost", func() bool { return contains(w.claim.Lost, tgt.ID) }, w.act(src), w.recoveryPass, w.operator) w.replaceDestroyed() w.reach(t, 800, "the source's return admitted", func() bool { c := w.claim if len(w.violations) > 0 || c.Op.Kind == "serving" { return true } l := lastAdmission(c.Holder) return c.Op.Kind == "restoring" && l != nil && l.Box == src.ID && l.Session > c.Op.CutSession }, w.act(src), w.recoveryPass, w.runConsole, w.operator) w.hold = nil w.completeHeld(dataKey(loc, gen0, "")) if len(w.violations) > 0 { return nil } l := lastAdmission(w.claim.Holder) if l == nil || l.Box != src.ID { t.Fatalf("witness: the source's return is not the last admission: %s", w.state()) } return l } // declarationsOf is a record's declarations, the ordinary one and the list. func declarationsOf(e *admissionRecord) []*writesLost { var out []*writesLost if e.Lost != nil { out = append(out, e.Lost) } return append(out, e.AdditionalWritesLost...) } // wNoDuplicateDeclarationEarly (R14-2): the target is destroyed before its // first admission, so the source's cut session is the predecessor itself; // it is declared once, as writes_lost, and never again in the list. func wNoDuplicateDeclarationEarly(t *testing.T, w *world) { e := w.lostTargetReturn(t, false) if e == nil { return } cut := w.claim.Op.CutSession n := 0 for _, x := range declarationsOf(e) { if x.Box == w.boxes[0].ID && x.Session == cut { n++ } } if n != 1 && len(w.violations) == 0 { w.violate("INV-21 (witness): the source's cut session %d was declared %d times by its return admission", cut, n) return } w.finish(t) } // wNoDuplicateDeclarationLate (R14-2): the target was admitted (its probe // session is the predecessor); the list carries the source's cut session // once and no target session twice. func wNoDuplicateDeclarationLate(t *testing.T, w *world) { e := w.lostTargetReturn(t, true) if e == nil { return } cut := w.claim.Op.CutSession seen := map[[2]int]int{} for _, x := range declarationsOf(e) { seen[[2]int{x.Box, x.Session}]++ } if seen[[2]int{w.boxes[0].ID, cut}] != 1 && len(w.violations) == 0 { w.violate("INV-21 (witness): the source's cut session %d was declared %d times behind the lost target", cut, seen[[2]int{w.boxes[0].ID, cut}]) return } for k, c := range seen { if c > 1 && len(w.violations) == 0 { w.violate("INV-21 (witness): {box %d, session %d} declared %d times", k[0], k[1], c) return } } if e.Predecessor.Box != w.boxes[1].ID { t.Fatalf("witness: the predecessor is not the target's probe session: %s", w.state()) } w.finish(t) } // TestJoinHolderlessSweep (R14-4) is the positive case of rev 7.14 note 1: // a deleted host keeps late residue in two regions; the first region's // sweep starts the holderless parking op and the second region's joins // it with its own scoped chores under the same op id. func TestJoinHolderlessSweep(t *testing.T) { w := newWitness() defer func() { if t.Failed() { dump(t, w) } }() b0 := w.boxes[0] w.serve(b0, 1, app0) w.wake(b0) w.appWrite(b0) loc := w.claim.Holder.Location w.userDelete() w.reach(t, 800, "host deleted and free", func() bool { c := w.claim return c != nil && c.Holder == nil && c.Op.Kind == "" && len(c.Obl) == 0 && w.rec == nil }, w.actAll(), w.runConsole, w.recoveryPass) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } for _, r := range []int{0, 1} { k := ltxKey(loc, "", 0, 7, 7) w.buckets[r].objs[k] = append(w.buckets[r].objs[k], &version{ID: w.newVer(), B: &blob{Kind: "ltx", Level: 0, Min: 7, Max: 7, Inc: 1, Pages: map[string]int{}}}) } // region 0's box sweeps first, then region 1's joins the running op joined := false w.tick(w.act(w.boxes[0])) if c := w.claim; c.Op.Kind != "parking" || c.Op.ParkSweep == "" { t.Fatalf("no holderless sweep started: %s", w.state()) } id := w.claim.Op.ID w.tick(w.act(w.boxes[1])) regions := map[int]bool{} for _, o := range w.claim.Obl { if o.Kind == "park-sweep" && o.Op == id { regions[o.Region] = true } } joined = regions[0] && regions[1] && w.claim.Op.ID == id if !joined { t.Fatalf("region 1 did not join op %s: %s", id, w.state()) } w.reach(t, 800, "freed after the park", func() bool { c := w.claim; return c != nil && c.Holder == nil && c.Op.Kind == "" && len(c.Obl) == 0 }, w.actAll(), w.recoveryPass) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } if w.stats["holderless sweeps"] != 1 || w.stats["sweep joined a running holderless op"] < 1 || w.stats["free after park"] != 1 { t.Fatalf("one op, one join, one free expected: %v", w.stats) } t.Logf("op %s: regions %v joined, freed once", id, regions) w.finish(t) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } } // TestInterruptedCleanReturn (R13-1) is the positive case of claim rev // 6.22's run walk across regions: a clean rollback's fresh source // admission dies before its first upload, so the run is R -> T -> S with T, // the target's generation, in the other region and covered under its park; // the walk passes T over and restores S; then one more interrupted // admission afterward, R2 -> R -> T -> S. func TestInterruptedCleanReturn(t *testing.T) { w := newWitness() defer func() { if t.Failed() { dump(t, w) } }() src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) w.appWrite(src) w.replicate(src) w.landProbed(t, src, tgt) loc, gen0 := w.claim.Holder.Location, w.claim.Op.SrcGen w.rollback(w.claim, "settle check failed") // the target wrote nothing: a clean rollback crashes := 0 w.startHook = func(x *box) bool { if x != src || crashes >= 2 || w.claim.Op.Kind != "restoring" && w.claim.Op.Kind != "serving" { return false } crashes++ w.crash(x) // before the first upload: the fresh generation is empty return true } w.reach(t, 800, "the source's return admission crashed", func() bool { return crashes >= 1 }, w.act(src, tgt), w.recoveryPass, w.runConsole) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } // the recovery: R is empty, T is the other region's, S holds the data w.recovered(t, src, "source recovered across the interrupted return") if w.stats["abandoned empty generation skipped"] < 1 { t.Fatalf("the recovery did not walk the run: %v", w.stats) } w.checkLocal(w.claim, src, src.DB) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } // one more interrupted admission afterward: R2 -> R -> T -> S w.reach(t, 1500, "the rollback finished", func() bool { return w.claim.Op.Kind == "serving" }, w.act(src, tgt), w.recoveryPass, w.runConsole) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } w.idleStop(src) w.reach(t, 200, "closed", func() bool { return !hasMain(src) }, w.act(src)) delete(w.buckets[src.Region].objs, closedKey(loc, w.claim.Holder.Gen, w.claim.Holder.Session)) w.wake(src) // cold, and the hook crashes it before its upload w.startHook = nil if crashes != 2 { t.Fatalf("the second admission did not crash (%d crashes): %s", crashes, w.state()) } w.recovered(t, src, "source recovered across two interrupted admissions") w.checkLocal(w.claim, src, src.DB) w.checkDurable(w.claim, "after the second recovery") if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } t.Logf("run walked twice from %q: %d empty generations skipped, %d starts refused", gen0, w.stats["abandoned empty generation skipped"], w.stats["start refused: covered local baseline"]) w.finish(t) if len(w.violations) > 0 { t.Fatalf("%s", w.violations[0]) } } // wTwoSessionDeclaration (R12-1) is a constructed-state oracle test: the // loss oracle's exemption, applied to acknowledgements of two sessions. // A box's first session acknowledged a write that never uploaded; so did // its second. A writes_lost record naming the second session exempts the // second write only (INV-18): the first stays an undeclared loss for the // oracles to report. Rev 7.12's match by box and incarnation absolved it. func wTwoSessionDeclaration(t *testing.T, w *world) { b := w.boxes[0] w.serve(b, 1, app0) h := w.claim.Holder s1 := h.Session w1 := w.ackInto(b, 1) // session 1's write, never uploaded s2 := s1 + 1 b.DB.Session = s2 // the constructed second session on the same box, same generation w2 := w.ackInto(b, 1) rec := &writesLost{Box: b.ID, Gen: h.Gen, Session: s2} n := w.exemptDeclared(b, rec, h, h.Gen, false) var x1, x2 *ack for i := range w.acks { switch w.acks[i].W { case w1: x1 = &w.acks[i] case w2: x2 = &w.acks[i] } } if x2 == nil || !x2.Exempt { t.Fatalf("witness: the declared session's write %d was not exempted", w2) } if x1 != nil && x1.Exempt { w.violate("INV-18 (witness): the writes_lost record for session %d exempted write %d, which session %d acknowledged and no record declares (%d exempted)", s2, w1, s1, n) } } // wRollbackBaselinePreserved (claim rev 6.14 item 5, R12-3): the target's // publication leaves the source's generation uncovered, with no chore, in // the source's region. Under the mutation a park-generation chore for it // is queued into the source's region from the target's publication; the // witness brings the chore's quiet time forward to now (the schedule // seeds 1036 and 1296 / rev 7.12 found with a landing open past the // horizon), lets the source's obligation runner work within the settle // window, then rolls the landing back cleanly: the return restores from // the source's generation. func wRollbackBaselinePreserved(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) w.appWrite(src) w.replicate(src) w.landProbed(t, src, tgt) loc, gen0 := w.claim.Holder.Location, w.claim.Op.SrcGen chores := 0 w.cas(w.claim, func(n *claim) bool { for i := range n.Obl { if n.Obl[i].Kind == "park-generation" && n.Obl[i].Region == src.Region { n.Obl[i].Quiet = w.now // the horizon has passed chores++ } } return true }) w.logf("witness: %d park-generation chores in the source's region after the target's publication", chores) // within the settle window, before the target's commit: the source // region's runner works the chore, if any w.drive(12, func() bool { return !w.hasFilesIn(src.Region, loc, gen0) }, w.act(src, tgt)) if len(w.violations) > 0 { return } if !w.hasFilesIn(src.Region, loc, gen0) { w.logf("witness: the source's generation %q is gone from region %d before the rollback", gen0, src.Region) } w.rollback(w.claim, "settle check failed") // the target wrote nothing: a clean rollback w.reach(t, 800, "source re-admitted after the rollback", func() bool { c := w.claim return len(w.violations) > 0 || c.Op.Kind == "serving" || c.Op.Kind == "restoring" && (c.Op.SrcPhase == "probed" || c.Op.SrcPhase == "opened" || c.Op.SrcPhase == "stuck") }, w.act(src, tgt), w.recoveryPass, w.runConsole) if len(w.violations) > 0 { return } if w.claim.Op.Kind == "restoring" && w.claim.Op.SrcPhase == "stuck" { w.violate("stuck: source could not recover %s: its generation %q was parked while the landing was still open", w.claim.Op.ID, gen0) return } w.recovered(t, src, "source serving again") w.checkLocal(w.claim, src, src.DB) w.checkDurable(w.claim, "after the rollback") w.finish(t) } // commitLanding drives a probed landing through its commit: the record // flips first, then whoever reads both follows it with the claim's CAS. // It returns the target's admission record, whose predecessor is the // source's generation in the source's region. func (w *world) commitLanding(t *testing.T, src, tgt *box) *admissionRecord { w.landProbed(t, src, tgt) var target *admissionRecord for i := range w.claim.Holder.Admissions { e := &w.claim.Holder.Admissions[i] if e.Box == tgt.ID && e.Mode == "cold" { target = e } } if target == nil || target.PredRegion != src.Region || target.Predecessor.Gen != w.claim.Op.SrcGen { t.Fatalf("witness: the target's record does not name the source's generation in the source's region: %s", w.state()) } if target.Covered { t.Fatalf("witness: the target's record was covered by its own publication, with its predecessor in another region: %s", w.state()) } w.reach(t, 400, "landing committed", func() bool { return w.claim.Op.Kind == "landing" && w.claim.Op.Committed }, w.act(src, tgt), w.recoveryPass, w.runConsole) return target } // targetRecord finds the target's cold admission record in the claim now. func (w *world) targetRecord(tgt *box) *admissionRecord { var out *admissionRecord for i := range w.claim.Holder.Admissions { e := &w.claim.Holder.Admissions[i] if e.Box == tgt.ID && e.Mode == "cold" { out = e } } return out } // wCommitCoverage (claim rev 6.14 item 6, R12-3): the commit's CAS queues // the source region's whole-location park and covers the target's record // in the same CAS. func wCommitCoverage(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) w.appWrite(src) w.commitLanding(t, src, tgt) if len(w.violations) > 0 { return } e := w.targetRecord(tgt) if e == nil { t.Fatalf("witness: the target's record is gone after the commit: %s", w.state()) } parks := 0 for _, o := range w.claim.Obl { if o.Kind == "park-superseded" && o.Region == src.Region { parks++ } } if parks != 1 { t.Fatalf("witness: %d park-superseded obligations for the source region after the commit: %s", parks, w.state()) } if !e.Covered { w.logf("witness: the target's record is uncovered after the commit's CAS queued the source region's park") } w.finish(t) // INV-17 at the end: an uncovered record whose predecessor's objects the park retired } // wCommitInterrupted (R12-3, interruption): the record flips to committed // and nothing follows it for longer than the horizon; the claim's CAS, // parks and coverage in one, is performed by whoever reads both later. func wCommitInterrupted(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) w.appWrite(src) w.landProbed(t, src, tgt) // the record commits (the target's settle check passed) with no claim CAS following w.reach(t, 400, "record committed", func() bool { return w.rec != nil && w.rec.MoveState == "committed" }, func() { w.worker(tgt) }) if w.claim.Op.Committed { t.Fatalf("witness: the claim followed the record in the same step; the interruption needs a gap: %s", w.state()) } for i := 0; i < horizonH+10; i++ { w.tick() // every actor paused: nobody follows the record } if w.claim.Op.Committed { t.Fatalf("witness: the claim committed while every actor was paused: %s", w.state()) } w.reach(t, 400, "landing committed after the interruption", func() bool { return w.claim.Op.Kind == "landing" && w.claim.Op.Committed }, w.act(src, tgt), w.recoveryPass, w.runConsole) if len(w.violations) > 0 { return } if e := w.targetRecord(tgt); e != nil && !e.Covered { w.logf("witness: the target's record is uncovered after the replayed commit") } w.finish(t) } // wCommitReplayed (R12-3, replay): after the commit's CAS another reader // follows the record again; the replay is refused, the source region's // park is queued once and the coverage stands. func wCommitReplayed(t *testing.T, w *world) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) w.appWrite(src) w.commitLanding(t, src, tgt) if len(w.violations) > 0 { return } before := w.claim.Ver if w.followRecord(w.claim) || w.claim.Ver != before { w.violate("INV-17 (witness): the commit's CAS was replayed after it committed (claim %d, now %d)", before, w.claim.Ver) return } parks := 0 for _, o := range w.claim.Obl { if o.Kind == "park-superseded" && o.Region == src.Region { parks++ } } if parks != 1 { w.violate("INV-17 (witness): %d park-superseded obligations for the source region after the replay", parks) return } w.finish(t) } // wProbeWindowAt (R12-2): the landing probe's environment is ready exactly // at the deadline. Under the rule the attempt fails before the start and // the next admission's probe is accepted; without the check before the // start, the expired attempt starts and is accepted (INV-19). func wProbeWindowAt(t *testing.T, w *world) { w.probeWindow(t, probeStartWindow) if len(w.violations) > 0 { return } w.finish(t) } // probeWindow runs a landing whose target's launch environment is ready k // steps after the probe attempt's app stage first runs, and reports how // the first attempt ended. The knob is released once the first attempt // has been counted, so the next attempt proceeds at once. func (w *world) probeWindow(t *testing.T, k int) (accepted bool) { src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.wake(src) tgt.envUnreadyFor = k w.moveTo(tgt.Region) id := w.claim.Op.ID w.reach(t, 800, "landing probed", func() bool { c := w.claim if c.Op.ID == id && c.Op.ProbeTries > 0 { tgt.envUnreadyFor = 0 } return len(w.violations) > 0 || c.Op.ID != id || c.Op.Kind == "landing" && c.Op.LandPhase == "probed" && hasMain(tgt) }, w.act(src, tgt), w.recoveryPass) if w.claim.Op.ID != id { t.Fatalf("witness: the move %s ended before its probe: %s", id, w.state()) } return w.claim.Op.ProbeTries == 0 } // TestProbeWindow (R12-2) walks the boundary: readiness k steps after the // attempt's first app stage, for k just before, at and after the window. func TestProbeWindow(t *testing.T) { for _, k := range []int{probeStartWindow - 1, probeStartWindow, probeStartWindow + 1} { w := newWitness() accepted := w.probeWindow(t, k) if len(w.violations) > 0 { t.Fatalf("k=%d: %s", k, w.violations[0]) } p := w.boxes[1].lastProbe tries := w.claim.Op.ProbeTries beforeStart, atEnv := w.stats["probe attempt failed: deadline before the start"], w.stats["probe attempt failed: environment"] switch { case k < probeStartWindow && !accepted: t.Errorf("k=%d: the attempt within the window was not accepted (tries %d)", k, tries) case k < probeStartWindow && p.readyAt-p.startedAt != k: t.Errorf("k=%d: the accepted attempt answered %d steps after its first start", k, p.readyAt-p.startedAt) case k >= probeStartWindow && accepted: t.Errorf("k=%d: an attempt at or beyond the deadline was accepted", k) case k == probeStartWindow && beforeStart != 1: // ready exactly at the deadline: the check before the start t.Errorf("k=%d: the deadline check before the start did not fail the attempt (stats %v)", k, w.stats) case k > probeStartWindow && atEnv != 1: // still unready at the deadline: the attempt fails there t.Errorf("k=%d: the deadline did not fail the attempt while the environment was unready (stats %v)", k, w.stats) case k >= probeStartWindow && tries != 1: t.Errorf("k=%d: %d probe tries counted, want 1", k, tries) } w.finish(t) if len(w.violations) > 0 { t.Fatalf("k=%d: %s", k, w.violations[0]) } t.Logf("k=%d: accepted=%v tries=%d probe start %d ready %d (failed before the start %d, at the deadline unready %d)", k, accepted, tries, p.startedAt, p.readyAt, beforeStart, atEnv) } } // TestK8JudgesOnlyASucceededRelease (Task 7 fix round 2): the K8 oracle // judges a release CAS that succeeded, never one the op-id guard refused. // The source closes a clean rollback's record and its goroutine stalls // before the release; the recovery pass releases from last_move; a purge // runs to the end and removes the record; the stalled release resumes with // only revalidate-before-effect dropped. Its CAS is conditional on the // rollback's op, which the claim no longer holds: refused, the claim is // untouched, and nothing is violated. func TestK8JudgesOnlyASucceededRelease(t *testing.T) { saved := mutated mutated = "revalidate-before-effect" defer func() { mutated = saved }() w := newWitness() src, tgt := w.boxes[0], w.boxes[1] w.serve(src, 1, app0) w.landProbed(t, src, tgt) w.rollback(w.claim, "cut deadline") w.reach(t, 1500, "source about to close", func() bool { c := w.claim return c.Op.Kind == "restoring" && c.Op.SrcPhase == "opened" && c.oblFor(c.Op.ID) == 0 }, w.act(src, tgt), w.recoveryPass) old := w.claim.clone() // the stalled goroutine's read if !w.closeRecord(old, src.ID) { t.Fatalf("the record did not close: %s", w.state()) } w.reach(t, 50, "released from last_move", func() bool { return w.claim.Op.Kind == "serving" }, w.recoveryPass) pg := &consolePlan{Kind: "purge", App: app0} w.reach(t, 2000, "the purge removed the record", func() bool { return w.rec == nil }, func() { w.runPlan(pg) }, w.actAll(), w.recoveryPass) before := w.claim.clone() w.resumeStaleRelease(src, old) if len(w.violations) > 0 { dump(t, w) t.Fatalf("a refused stale release was judged: %v", w.violations) } if w.claim.Ver != before.Ver || w.claim.Op.Kind == "serving" && w.claim.Op.Exec == src.ID && w.claim.Holder != nil { t.Fatalf("the stale release was not refused: before %s after %s", before.Op.Kind, w.state()) } }