| 1 | package hostlife |
| 2 | |
| 3 | import ( |
| 4 | "strings" |
| 5 | "testing" |
| 6 | ) |
| 7 | |
| 8 | // twoBoxWitness is newWitness with a second enrolled box in every region. |
| 9 | func twoBoxWitness() *world { |
| 10 | w := newWitness() |
| 11 | w.perRegion = 2 |
| 12 | for r := 0; r < nRegions; r++ { |
| 13 | w.addBox(r) |
| 14 | } |
| 15 | return w |
| 16 | } |
| 17 | |
| 18 | // TestDrainEndToEnd: a serving host is drained from box 0 to box 3 in |
| 19 | // region 0 through every phase of §5.8's table; the host serves on box 3 |
| 20 | // with every acknowledged write and timer, box 0's installation is |
| 21 | // retired by its park-local, and the first probe admission's coverage is |
| 22 | // released (L9): no write is declared lost; the first serving wake on box |
| 23 | // 3 is cold and records a writes_lost for the stopped probe session, which |
| 24 | // acknowledged nothing here (L18 joint round 2 finding 1). |
| 25 | func TestDrainEndToEnd(t *testing.T) { |
| 26 | w := twoBoxWitness() |
| 27 | from, to := w.boxes[0], w.boxes[3] |
| 28 | w.serve(from, 1, app0) |
| 29 | w.reach(t, 50, "the host runs on box 0", func() bool { return hasMain(from) }, w.actAll(), func() { w.wake(from) }) |
| 30 | w.appWrite(from) |
| 31 | w.nextW++ |
| 32 | from.Timers = append(from.Timers, w.nextW) |
| 33 | w.acks = append(w.acks, ack{W: w.nextW, Inc: 1, Box: from.ID, Session: w.claim.Holder.Session, At: w.now, Kind: "timer"}) |
| 34 | w.userRelocate() |
| 35 | if c := w.claim; c.Op.Kind != "relocating" || c.Op.Src != from.ID || c.Op.Tgt != to.ID || c.Op.Phase != "starting" { |
| 36 | t.Fatalf("the drain did not start: %s", w.state()) |
| 37 | } |
| 38 | seen := map[string]bool{} |
| 39 | w.reach(t, 1500, "serving on box 3", func() bool { |
| 40 | seen[w.claim.Op.Phase] = true |
| 41 | return w.claim.Op.Kind == "serving" && w.claim.Op.Exec == to.ID |
| 42 | }, w.actAll(), w.recoveryPass, func() { w.wake(to) }) |
| 43 | for _, p := range []string{"starting", "releasing", "pinning", "installing", "installed", "probing", "probed"} { |
| 44 | if !seen[p] { |
| 45 | t.Errorf("phase %s never observed", p) |
| 46 | } |
| 47 | } |
| 48 | if w.stats["admissions covered: released"] != 1 || w.stats["writes_lost declared"] > 1 || w.stats["writes declared lost"] != 0 { |
| 49 | t.Errorf("released coverage: %d released, %d writes_lost covering %d writes (want 1, at most the first serving wake's, and 0)", w.stats["admissions covered: released"], w.stats["writes_lost declared"], w.stats["writes declared lost"]) |
| 50 | } |
| 51 | w.finish(t) |
| 52 | if len(w.violations) > 0 { |
| 53 | t.Fatalf("%s", w.violations[0]) |
| 54 | } |
| 55 | if from.DB != nil || from.Files != nil || from.Row != nil { |
| 56 | t.Errorf("box 0 still holds local state after its park-local: db=%v files=%v row=%v", from.DB != nil, from.Files != nil, from.Row) |
| 57 | } |
| 58 | } |
| 59 | |
| 60 | // TestUnenrolledReferenceNeverChosen (§2, HA7; Review Focus 4): the |
| 61 | // executor is terminated; the region's other enrolled box holds no |
| 62 | // secrets key, so it may work but cannot take the host (R9); the |
| 63 | // replacement that launched is not yet enrolled. The failover must wait |
| 64 | // at pinning with no target until the replacement enrolls, never name |
| 65 | // the unenrolled reference (which could not be fenced if it died). |
| 66 | func TestUnenrolledReferenceNeverChosen(t *testing.T) { |
| 67 | w := twoBoxWitness() |
| 68 | from, peer := w.boxes[0], w.boxes[3] |
| 69 | w.serve(from, 1, app0) |
| 70 | w.reach(t, 50, "the host runs on box 0", func() bool { return hasMain(from) }, w.actAll(), func() { w.wake(from) }) |
| 71 | w.published(t, from) |
| 72 | peer.HasKey = false |
| 73 | w.terminate(from) |
| 74 | w.now += replaceDelay |
| 75 | w.launchReplacements() |
| 76 | nb := w.boxes[len(w.boxes)-1] |
| 77 | if nb.Region != 0 || nb.Enrolled { |
| 78 | t.Fatalf("no unenrolled replacement in region 0: %+v", nb) |
| 79 | } |
| 80 | nb.EnrollAt = w.now + 10*enrollDelay // its confirmation is slow |
| 81 | // nb stays unenrolled and the peer has no key: no box is eligible, so |
| 82 | // the failover does not start (Worker.Start's Eligible, rev 7) and no |
| 83 | // unenrolled box is named |
| 84 | w.drive(enrollDelay, func() bool { return false }, w.actAll(), w.recoveryPass) |
| 85 | if c := w.claim; c.Op.Kind != "serving" || c.Op.Exec != from.ID || c.Op.Tgt == nb.ID { |
| 86 | t.Fatalf("an unenrolled box was named, or the failover started with no eligible target: %s", w.state()) |
| 87 | } |
| 88 | nb.EnrollAt = w.now - enrollDelay |
| 89 | w.enrollStep() |
| 90 | if !nb.Enrolled { |
| 91 | t.Fatalf("the replacement did not enroll") |
| 92 | } |
| 93 | w.reach(t, 1500, "serving on the replacement", func() bool { |
| 94 | c := w.claim |
| 95 | return c.Op.Kind == "serving" && c.Op.Exec == nb.ID |
| 96 | }, w.actAll(), w.recoveryPass, w.operator, func() { w.wake(nb) }) |
| 97 | w.finish(t) |
| 98 | if len(w.violations) > 0 { |
| 99 | t.Fatalf("%s", w.violations[0]) |
| 100 | } |
| 101 | } |
| 102 | |
| 103 | // TestTwoWorkersOneChore (claim P6-D5; Review Focus 1): a push leaves a |
| 104 | // dead generation; both boxes of the region run its park-generation at |
| 105 | // once. The chore converges with no residue and no double declaration. |
| 106 | func TestTwoWorkersOneChore(t *testing.T) { |
| 107 | w := twoBoxWitness() |
| 108 | b := w.boxes[0] |
| 109 | w.serve(b, 1, app0) |
| 110 | w.userPush() |
| 111 | w.reach(t, 800, "the push served and its predecessor's chore queued", func() bool { |
| 112 | c := w.claim |
| 113 | return c.Op.Kind == "serving" && len(c.Obl) > 0 |
| 114 | }, w.actAll(), w.recoveryPass, func() { w.wake(b) }) |
| 115 | w.finish(t) |
| 116 | if len(w.violations) > 0 { |
| 117 | t.Fatalf("%s", w.violations[0]) |
| 118 | } |
| 119 | if r := w.residue(); len(r) > 0 { |
| 120 | t.Fatalf("residue after both workers ran the chore: %v", r) |
| 121 | } |
| 122 | } |
| 123 | |
| 124 | // TestLateFileUploads (§5.6, §5.8; Review Focus 5): the executor |
| 125 | // registers a timer, its manifest PUT is held by the witness, and it is |
| 126 | // terminated. The failover pins the previous manifest, the install |
| 127 | // applies exactly that version, the held PUT lands after the pin, and |
| 128 | // the timer it carried is declared, never silently dropped; the late |
| 129 | // manifest is parked with generation_from. |
| 130 | func TestLateFileUploads(t *testing.T) { |
| 131 | w := twoBoxWitness() |
| 132 | w.perRegion = 2 |
| 133 | from, to := w.boxes[0], w.boxes[3] |
| 134 | w.serve(from, 1, app0) |
| 135 | w.reach(t, 50, "the host runs on box 0", func() bool { return hasMain(from) }, w.actAll(), func() { w.wake(from) }) |
| 136 | w.publishFiles(from) // the first manifest lands |
| 137 | w.completeDue(true) |
| 138 | w.nextW++ |
| 139 | late := w.nextW |
| 140 | from.Timers = append(from.Timers, late) |
| 141 | w.acks = append(w.acks, ack{W: late, Inc: 1, Box: from.ID, Session: w.claim.Holder.Session, At: w.now, Kind: "timer"}) |
| 142 | w.holdKey(w.claim.Holder.Location + "files/") |
| 143 | w.publishFiles(from) // the second manifest, held |
| 144 | w.hold = nil |
| 145 | w.terminate(from) |
| 146 | w.reach(t, 1500, "serving on box 3", func() bool { |
| 147 | c := w.claim |
| 148 | return c.Op.Kind == "serving" && c.Op.Exec == to.ID |
| 149 | }, w.actAll(), w.recoveryPass, w.operator, func() { w.wake(to) }) |
| 150 | if contains(to.Timers, late) { |
| 151 | t.Fatalf("the install applied a manifest that had not landed at the pin") |
| 152 | } |
| 153 | declared := false |
| 154 | for _, a := range w.acks { |
| 155 | if a.W == late && a.Exempt { |
| 156 | declared = true |
| 157 | } |
| 158 | } |
| 159 | if !declared { |
| 160 | t.Fatalf("the timer the late manifest carried was not declared with the fence") |
| 161 | } |
| 162 | if n := w.completeHeld(w.claim.Holder.Location + "files/"); n != 1 { |
| 163 | t.Fatalf("held manifest PUTs completed: %d, want 1", n) |
| 164 | } |
| 165 | w.finish(t) |
| 166 | if len(w.violations) > 0 { |
| 167 | t.Fatalf("%s", w.violations[0]) |
| 168 | } |
| 169 | if r := w.residue(); len(r) > 0 { |
| 170 | t.Fatalf("the late manifest was never parked: %v", r) |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | // ---------- Task 5: the scenarios ---------- |
| 175 | |
| 176 | // twoBox turns a witness world into the two-box shape. |
| 177 | func (w *world) twoBox() { |
| 178 | w.perRegion = 2 |
| 179 | for r := 0; r < nRegions; r++ { |
| 180 | w.addBox(r) |
| 181 | } |
| 182 | } |
| 183 | |
| 184 | // regionWorld is a witness world with region HA on (the two-box shape's |
| 185 | // rules, its publisher and its group) whose region 0 holds boxes boxes: |
| 186 | // 2 is a two-box region (boxes 0 and 3); 1 is a one-box region (box 0 |
| 187 | // alone, kept at one box by its group, H5's minimum being per region). |
| 188 | // Regions 1 and 2 have two boxes either way. |
| 189 | func regionWorld(boxes int) *world { |
| 190 | w := newWitness() |
| 191 | w.perRegion = 2 |
| 192 | for r := 0; r < nRegions; r++ { |
| 193 | if r == 0 && boxes == 1 { |
| 194 | w.oneBoxRegion[0] = true |
| 195 | continue |
| 196 | } |
| 197 | w.addBox(r) |
| 198 | } |
| 199 | return w |
| 200 | } |
| 201 | |
| 202 | // bothShapes runs an L18 case in a one-box and in a two-box region. |
| 203 | func bothShapes(t *testing.T, f func(t *testing.T, w *world, boxes int)) { |
| 204 | for _, n := range []int{1, 2} { |
| 205 | n := n |
| 206 | t.Run(map[int]string{1: "one-box region", 2: "two-box region"}[n], func(t *testing.T) { |
| 207 | w := regionWorld(n) |
| 208 | f(t, w, n) |
| 209 | if len(w.violations) > 0 { |
| 210 | dump(t, w) |
| 211 | t.Fatalf("%s", w.violations[0]) |
| 212 | } |
| 213 | }) |
| 214 | } |
| 215 | } |
| 216 | |
| 217 | // peer is region 0's second box, nil in a one-box region. |
| 218 | func (w *world) peer() *box { |
| 219 | for _, b := range w.boxes { |
| 220 | if b.ID == nRegions && !b.Destroyed { |
| 221 | return b |
| 222 | } |
| 223 | } |
| 224 | return nil |
| 225 | } |
| 226 | |
| 227 | // extraBox enrolls another box in region r with the given id (a spare |
| 228 | // for the nested scenarios). |
| 229 | func (w *world) extraBox(r, id int) *box { |
| 230 | b := &box{ID: id, Region: r, HasKey: true, Enrolled: true, DeleteOnTermination: true} |
| 231 | b.forget() |
| 232 | w.boxes = append(w.boxes, b) |
| 233 | return b |
| 234 | } |
| 235 | |
| 236 | // running drives the serving host until it runs on b. |
| 237 | func (w *world) running(t *testing.T, b *box) { |
| 238 | w.reach(t, 60, "the host runs", func() bool { return hasMain(b) }, w.actAll(), func() { w.wake(b) }) |
| 239 | } |
| 240 | |
| 241 | // drainTo starts a drain of the serving host and fails the test unless |
| 242 | // it named to (any target when to is nil). |
| 243 | func (w *world) drainTo(t *testing.T, to *box) { |
| 244 | w.userRelocate() |
| 245 | if c := w.claim; c.Op.Kind != "relocating" || to != nil && c.Op.Tgt != to.ID { |
| 246 | t.Fatalf("witness: the drain did not start (to %v): %s", to, w.state()) |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | // relocPhase drives until the relocation is in phase p (or beyond it, by |
| 251 | // the table's order), with the actors given. |
| 252 | func (w *world) relocPhase(t *testing.T, p string, actors ...func()) bool { |
| 253 | order := []string{"starting", "releasing", "pinning", "installing", "installed", "probing", "probed", "opened"} |
| 254 | at := func(x string) int { |
| 255 | for i, o := range order { |
| 256 | if o == x { |
| 257 | return i |
| 258 | } |
| 259 | } |
| 260 | return -1 |
| 261 | } |
| 262 | return w.reach(t, 1500, "relocation at "+p, func() bool { |
| 263 | c := w.claim |
| 264 | return c.Op.Kind == "relocating" && at(c.Op.Phase) >= at(p) || c.Op.Kind == "serving" && p == "serving" |
| 265 | }, actors...) |
| 266 | } |
| 267 | |
| 268 | // servingOn drives until the host serves on b (on any box, when b is |
| 269 | // nil), with every actor the at-rest model has. |
| 270 | func (w *world) servingOn(t *testing.T, b *box) bool { |
| 271 | return w.reach(t, 3000, "serving on the new executor", func() bool { |
| 272 | c := w.claim |
| 273 | return c.Op.Kind == "serving" && (b == nil && c.Op.Exec >= 0 || b != nil && c.Op.Exec == b.ID) |
| 274 | }, w.actAll(), w.recoveryPass, w.operator, w.wakeExec) |
| 275 | } |
| 276 | |
| 277 | // wakeExec wakes the executor, whichever box it is. |
| 278 | func (w *world) wakeExec() { |
| 279 | if e := w.execBox(w.claim); e != nil { |
| 280 | w.wake(e) |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | // timerOn registers an acknowledged timer on b's running host. |
| 285 | func (w *world) timerOn(b *box) int { |
| 286 | w.nextW++ |
| 287 | b.Timers = append(b.Timers, w.nextW) |
| 288 | sess, gen := w.sessionOf(b) |
| 289 | w.acks = append(w.acks, ack{W: w.nextW, Inc: w.claim.Holder.Inc, Box: b.ID, Session: sess, Gen: gen, At: w.now, Kind: "timer"}) |
| 290 | return w.nextW |
| 291 | } |
| 292 | |
| 293 | // spareID is an id for an extra box of region 0 whose tieHash beats box |
| 294 | // 0's, so choose() prefers it to the source. |
| 295 | func spareID() int { |
| 296 | for id := 40; ; id++ { |
| 297 | if tieHash(id) > tieHash(0) { |
| 298 | return id |
| 299 | } |
| 300 | } |
| 301 | } |
| 302 | |
| 303 | func never() bool { return false } |
| 304 | |
| 305 | // published drives until a manifest of b's host has landed (the files |
| 306 | // publisher runs in every two-box tick): a failover of a host none of |
| 307 | // whose manifests landed is finding F2's, not the scenario's. |
| 308 | func (w *world) published(t *testing.T, b *box) bool { |
| 309 | return w.reach(t, 60, "the host's first manifest landed", func() bool { |
| 310 | _, _, _, _, m := w.newestManifest(b.Region, w.claim.Holder.Location, w.claim.Holder.Gen) |
| 311 | return m != nil |
| 312 | }, w.act(b), func() { w.completeDue(true) }) |
| 313 | } |
| 314 | |
| 315 | // ---------- the witnesses (one per safety guard) ---------- |
| 316 | |
| 317 | func wRelocReleaseFirst(t *testing.T, w *world) { |
| 318 | w.twoBox() |
| 319 | from, to := w.boxes[0], w.boxes[3] |
| 320 | w.serve(from, 1, app0) |
| 321 | w.running(t, from) |
| 322 | w.drainTo(t, to) |
| 323 | // only the target's worker runs while the source should be releasing: |
| 324 | // with the rule it waits for the release; without it, it pins and |
| 325 | // installs while the source still runs the host |
| 326 | w.drive(12, never, w.act(to)) |
| 327 | w.servingOn(t, to) |
| 328 | w.finish(t) |
| 329 | } |
| 330 | |
| 331 | func wRelocInstallReceipt(t *testing.T, w *world) { |
| 332 | w.twoBox() |
| 333 | from, to := w.boxes[0], w.boxes[3] |
| 334 | w.serve(from, 1, app0) |
| 335 | w.running(t, from) |
| 336 | w.drainTo(t, to) |
| 337 | third := w.extraBox(0, 30) |
| 338 | if !w.reach(t, 1500, "the target's receipt", func() bool { |
| 339 | c := w.claim |
| 340 | return c.Op.Kind == "relocating" && c.Op.Phase == "installed" && c.Op.Receipt != nil && c.Op.Receipt.Box == to.ID |
| 341 | }, w.act(from, to), w.recoveryPass) { |
| 342 | return |
| 343 | } |
| 344 | w.terminate(to) |
| 345 | w.servingOn(t, third) |
| 346 | w.finish(t) |
| 347 | } |
| 348 | |
| 349 | // probeOpened drives until the target's first attempt has opened P and |
| 350 | // is still starting (L18 finding 2: once its app answers, the probe has |
| 351 | // passed and is stopped, never restarted). |
| 352 | func (w *world) probeOpened(t *testing.T, from, to *box) bool { |
| 353 | w.openYield = func(b *box) bool { return b == to } // the attempt pauses after its admission, before replication opens |
| 354 | defer func() { w.openYield = nil }() |
| 355 | return w.reach(t, 1500, "P opened by an attempt still starting", func() bool { |
| 356 | c := w.claim |
| 357 | return c.Op.Kind == "relocating" && c.Op.Phase == "probing" && preparedOpened(c) && to.open != nil |
| 358 | }, w.act(from, to), w.recoveryPass) |
| 359 | } |
| 360 | |
| 361 | // wRelocNoReinstall, wRelocVerifyReceipt and wRelocPreparedOpenedJournal |
| 362 | // make a later attempt after P's opening, which root cannot launch while |
| 363 | // claim ask C11 is open (finding 4): they show the rules C11 makes live. |
| 364 | func wRelocNoReinstall(t *testing.T, w *world) { |
| 365 | w.twoBox() |
| 366 | w.claimC11 = true |
| 367 | from, to := w.boxes[0], w.boxes[3] |
| 368 | w.serve(from, 1, app0) |
| 369 | w.running(t, from) |
| 370 | w.drainTo(t, to) |
| 371 | if !w.probeOpened(t, from, to) { |
| 372 | return |
| 373 | } |
| 374 | w.timerOn(to) |
| 375 | w.crash(to) |
| 376 | w.servingOn(t, to) |
| 377 | w.finish(t) |
| 378 | } |
| 379 | |
| 380 | func wRelocReleasedCoverage(t *testing.T, w *world) { |
| 381 | w.twoBox() |
| 382 | from, to := w.boxes[0], w.boxes[3] |
| 383 | w.serve(from, 1, app0) |
| 384 | w.running(t, from) |
| 385 | w.published(t, from) |
| 386 | w.appWrite(from) |
| 387 | loc := w.claim.Holder.Location |
| 388 | w.holdKey(loc) // every upload of the executor is held |
| 389 | w.replicate(from) |
| 390 | w.hold = nil |
| 391 | w.terminate(from) |
| 392 | w.servingOn(t, to) |
| 393 | w.completeHeld(loc) // the dead box's upload lands late, after the pin |
| 394 | w.finish(t) |
| 395 | } |
| 396 | |
| 397 | func wRelocSourceLoss(t *testing.T, w *world) { |
| 398 | w.twoBox() |
| 399 | from, to := w.boxes[0], w.boxes[3] |
| 400 | w.serve(from, 1, app0) |
| 401 | w.running(t, from) |
| 402 | w.appWrite(from) |
| 403 | loc := w.claim.Holder.Location |
| 404 | w.holdKey(loc) // the flush and the final manifest are held: no release |
| 405 | w.drainTo(t, to) |
| 406 | w.relocPhase(t, "releasing", w.act(from, to), w.recoveryPass) |
| 407 | w.drive(20, never, w.act(from, to)) |
| 408 | if w.claim.Op.Release != nil { |
| 409 | t.Fatalf("witness: the release was journaled while its uploads were held") |
| 410 | } |
| 411 | w.hold = nil |
| 412 | w.terminate(from) |
| 413 | w.servingOn(t, to) |
| 414 | w.completeHeld(loc) |
| 415 | w.finish(t) |
| 416 | } |
| 417 | |
| 418 | func wRelocRowCases(t *testing.T, w *world) { |
| 419 | w.twoBox() |
| 420 | from, to := w.boxes[0], w.boxes[3] |
| 421 | w.serve(from, 1, app0) |
| 422 | w.running(t, from) |
| 423 | w.drainTo(t, to) |
| 424 | if !w.reach(t, 1500, "the source released", func() bool { |
| 425 | c := w.claim |
| 426 | return c.Op.Kind == "relocating" && c.Op.Release != nil && c.Op.Release.Box == from.ID && !hasMain(from) |
| 427 | }, w.act(from, to), w.recoveryPass) { |
| 428 | return |
| 429 | } |
| 430 | // a paused duplicate of the source's earlier open lands now: its row |
| 431 | // is ready again while its admission fence is closed. A request |
| 432 | // reaches the box through its stale edges file, then reconcile decides |
| 433 | // the row (in that order each step, so the request also meets the row |
| 434 | // in the step after the completion, before the catch-up hold) |
| 435 | from.Row.Status, from.Row.HoldOp = "ready", "" |
| 436 | w.drive(80, never, func() { |
| 437 | w.wake(from) |
| 438 | w.reconcile(from) |
| 439 | }, w.act(to), w.recoveryPass, func() { w.wake(to) }) |
| 440 | w.servingOn(t, to) |
| 441 | w.finish(t) |
| 442 | } |
| 443 | |
| 444 | func wFenceDischargeQualified(t *testing.T, w *world) { |
| 445 | w.twoBox() |
| 446 | from, to := w.boxes[0], w.boxes[3] |
| 447 | from.DeleteOnTermination = false |
| 448 | w.serve(from, 1, app0) |
| 449 | w.running(t, from) |
| 450 | w.drainTo(t, to) |
| 451 | w.servingOn(t, to) |
| 452 | if !w.owesLocal(w.claim, from) { |
| 453 | t.Fatalf("witness: the former executor owes no park-local: %s", w.state()) |
| 454 | } |
| 455 | w.terminate(from) |
| 456 | w.reach(t, 60, "the former executor fenced", func() bool { return contains(w.claim.Lost, from.ID) }, w.act(to)) |
| 457 | w.finish(t) |
| 458 | } |
| 459 | |
| 460 | func wFenceDeclaresTimers(t *testing.T, w *world) { |
| 461 | w.twoBox() |
| 462 | from, to := w.boxes[0], w.boxes[3] |
| 463 | w.serve(from, 1, app0) |
| 464 | w.running(t, from) |
| 465 | w.publishFiles(from) |
| 466 | w.completeDue(true) |
| 467 | w.holdKey(w.claim.Holder.Location + "files/") // the manifest that would carry the timer never lands |
| 468 | w.timerOn(from) |
| 469 | w.publishFiles(from) |
| 470 | w.hold = nil |
| 471 | w.terminate(from) |
| 472 | w.servingOn(t, to) |
| 473 | w.completeHeld(w.claim.Holder.Location + "files/") // it lands after the pin: a version nothing reads |
| 474 | w.finish(t) |
| 475 | } |
| 476 | |
| 477 | func wRelocEnrolledOnly(t *testing.T, w *world) { |
| 478 | w.twoBox() |
| 479 | from, peer := w.boxes[0], w.boxes[3] |
| 480 | w.serve(from, 1, app0) |
| 481 | w.published(t, from) |
| 482 | peer.HasKey = false |
| 483 | w.terminate(from) |
| 484 | w.reach(t, 100, "the executor fenced", func() bool { return contains(w.claim.Lost, from.ID) }, w.act(peer), w.recoveryPass) |
| 485 | // the replacement launches unenrolled; under the mutation it is named |
| 486 | // before it enrolls (INV-27) |
| 487 | w.servingOn(t, nil) |
| 488 | w.finish(t) |
| 489 | } |
| 490 | |
| 491 | func wFilesLiveSet(t *testing.T, w *world) { |
| 492 | w.twoBox() |
| 493 | from, to := w.boxes[0], w.boxes[3] |
| 494 | w.serve(from, 1, app0) |
| 495 | w.running(t, from) |
| 496 | w.timerOn(from) |
| 497 | if !w.reach(t, 30, "the origin's manifest landed", func() bool { |
| 498 | _, _, _, _, m := w.newestManifest(0, w.claim.Holder.Location, w.claim.Holder.Gen) |
| 499 | return m != nil |
| 500 | }, w.actAll(), func() { w.completeDue(true) }) { |
| 501 | return |
| 502 | } |
| 503 | // the agent restarts: the next wake is a cold admission into a fresh |
| 504 | // generation, which publishes nothing (nothing changed), and the |
| 505 | // origin's park-generation runs once the new marker lands |
| 506 | w.crash(from) |
| 507 | if !w.reach(t, 600, "a fresh generation serving and the origin parked", func() bool { |
| 508 | c := w.claim |
| 509 | if c.Holder.Gen == "" || !hasMain(from) || from.open != nil { |
| 510 | return false |
| 511 | } |
| 512 | for _, o := range c.Obl { |
| 513 | if o.Kind == "park-generation" { |
| 514 | return false |
| 515 | } |
| 516 | } |
| 517 | return true |
| 518 | }, w.actAll(), w.recoveryPass, func() { w.wake(from) }) { |
| 519 | return |
| 520 | } |
| 521 | w.terminate(from) |
| 522 | w.servingOn(t, to) |
| 523 | w.finish(t) |
| 524 | } |
| 525 | |
| 526 | // rev 2: 1b-next rev 16's guards |
| 527 | |
| 528 | func wRelocPinClaimGen(t *testing.T, w *world) { |
| 529 | w.twoBox() |
| 530 | from, to := w.boxes[0], w.boxes[3] |
| 531 | w.serve(from, 1, app0) |
| 532 | w.running(t, from) |
| 533 | w.drainTo(t, to) |
| 534 | third := w.extraBox(0, 30) |
| 535 | // the first round, observed by a pinner after the source's release and |
| 536 | // before any pin; it stalls before its journal CAS |
| 537 | if !w.reach(t, 1500, "the source's release journaled", func() bool { |
| 538 | c := w.claim |
| 539 | return c.Op.Kind == "relocating" && c.Op.Release != nil && c.Op.Pin == nil |
| 540 | }, w.act(from, to)) { |
| 541 | return |
| 542 | } |
| 543 | stale := w.claim.clone() |
| 544 | if !w.reach(t, 1500, "the target's probe writes into P", func() bool { return preparedOpened(w.claim) && hasMain(to) }, w.act(from, to), w.recoveryPass, func() { w.wake(to) }) { |
| 545 | return |
| 546 | } |
| 547 | w.appWrite(to) |
| 548 | w.replicate(to) |
| 549 | w.completeDue(true) // the target's write is in P's remote before it dies |
| 550 | w.terminate(to) |
| 551 | if !w.reach(t, 100, "the nested pinning", func() bool { |
| 552 | c := w.claim |
| 553 | return c.Op.Kind == "relocating" && c.Op.Phase == "pinning" && c.Op.Pin == nil && contains(c.Lost, to.ID) |
| 554 | }, w.act(third)) { |
| 555 | return |
| 556 | } |
| 557 | w.now += failoverPinDelay |
| 558 | w.relocPinning(third, stale) // the stalled pinner resumes with the first round's selection |
| 559 | w.servingOn(t, third) |
| 560 | w.finish(t) |
| 561 | } |
| 562 | |
| 563 | func wRelocReleaseDeadline(t *testing.T, w *world) { |
| 564 | w.twoBox() |
| 565 | from, to := w.boxes[0], w.boxes[3] |
| 566 | w.serve(from, 1, app0) |
| 567 | w.running(t, from) |
| 568 | w.appWrite(from) |
| 569 | loc := w.claim.Holder.Location |
| 570 | w.holdKey(loc) // the source's flush never completes |
| 571 | w.drainTo(t, to) |
| 572 | w.reach(t, 3*releaseDeadline+200, "the host serving again", func() bool { |
| 573 | c := w.claim |
| 574 | return c.Op.Kind == "serving" |
| 575 | }, w.actAll(), w.recoveryPass, w.operator) |
| 576 | w.hold = nil |
| 577 | w.completeHeld(loc) |
| 578 | w.finish(t) |
| 579 | } |
| 580 | |
| 581 | func wRelocEnsureLocal(t *testing.T, w *world) { |
| 582 | w.twoBox() |
| 583 | from, to := w.boxes[0], w.boxes[3] |
| 584 | w.serve(from, 1, app0) |
| 585 | w.running(t, from) |
| 586 | w.drainTo(t, to) |
| 587 | if !w.reach(t, 1500, "the target's receipt journaled", func() bool { |
| 588 | c := w.claim |
| 589 | return c.Op.Kind == "relocating" && c.Op.Receipt != nil && c.Op.Receipt.Box == to.ID |
| 590 | }, w.act(from, to), w.recoveryPass) { |
| 591 | return |
| 592 | } |
| 593 | // the target freezes past its execution lease: its relocation |
| 594 | // controller is lost, and the scoped cleanup retires the unopened |
| 595 | // local install when it runs again |
| 596 | to.Frozen = true |
| 597 | w.drive(execTTL+2, never, w.act(from)) |
| 598 | to.Frozen = false |
| 599 | w.servingOn(t, to) |
| 600 | w.finish(t) |
| 601 | } |
| 602 | |
| 603 | func wRelocVerifyReceipt(t *testing.T, w *world) { |
| 604 | w.twoBox() |
| 605 | w.claimC11 = true |
| 606 | from, to := w.boxes[0], w.boxes[3] |
| 607 | w.serve(from, 1, app0) |
| 608 | w.running(t, from) |
| 609 | w.drainTo(t, to) |
| 610 | third := w.extraBox(0, 30) |
| 611 | if !w.probeOpened(t, from, to) { |
| 612 | return |
| 613 | } |
| 614 | // the volume holding the host's directory is replaced and the agent |
| 615 | // restarts: the files, the database and the install journal are gone |
| 616 | w.crash(to) |
| 617 | to.Files, to.DB, to.receipt = nil, nil, nil |
| 618 | w.servingOn(t, nil) |
| 619 | _ = third |
| 620 | w.finish(t) |
| 621 | } |
| 622 | |
| 623 | func wRelocPreparedOpenedJournal(t *testing.T, w *world) { |
| 624 | w.twoBox() |
| 625 | w.claimC11 = true |
| 626 | from, to := w.boxes[0], w.boxes[3] |
| 627 | w.serve(from, 1, app0) |
| 628 | w.running(t, from) |
| 629 | w.drainTo(t, to) |
| 630 | if !w.probeOpened(t, from, to) { |
| 631 | return |
| 632 | } |
| 633 | w.timerOn(to) |
| 634 | w.crash(to) // the next attempt admits a fresh generation from P's |
| 635 | w.openYield = func(b *box) bool { return b == to } |
| 636 | reached := w.reach(t, 400, "the second attempt admitted and still starting", func() bool { |
| 637 | c := w.claim |
| 638 | return c.Op.Phase == "probing" && c.Holder.Gen != c.Op.Prepared && to.open != nil |
| 639 | }, w.act(from, to), w.recoveryPass) |
| 640 | w.openYield = nil |
| 641 | if !reached { |
| 642 | return |
| 643 | } |
| 644 | // holder.admissions is trimmed as AdmitWriter trims it past eight: |
| 645 | // P's admission is no longer listed |
| 646 | w.cas(w.claim, func(n *claim) bool { |
| 647 | var keep []admissionRecord |
| 648 | for _, e := range n.Holder.Admissions { |
| 649 | if e.Gen != n.Op.Prepared { |
| 650 | keep = append(keep, e) |
| 651 | } |
| 652 | } |
| 653 | n.Holder.Admissions = keep |
| 654 | return true |
| 655 | }) |
| 656 | w.crash(to) |
| 657 | w.servingOn(t, to) |
| 658 | w.finish(t) |
| 659 | } |
| 660 | |
| 661 | func wFenceReassignsRegional(t *testing.T, w *world) { |
| 662 | w.twoBox() |
| 663 | from, to := w.boxes[0], w.boxes[3] |
| 664 | w.serve(from, 1, app0) |
| 665 | w.running(t, from) |
| 666 | // a dead generation of the location, with an object in region 0, whose |
| 667 | // park-generation chore carries the legacy owner form box:0 |
| 668 | loc := w.claim.Holder.Location |
| 669 | k := ltxKey(loc, "old", 0, 1, 1) |
| 670 | w.buckets[0].objs[k] = []*version{{ID: w.newVer(), B: &blob{Kind: "ltx", Level: 0, Min: 1, Max: 1, Inc: 1}}} |
| 671 | id := w.newID("ob") |
| 672 | w.cas(w.claim, func(n *claim) bool { |
| 673 | n.Obl = append(n.Obl, w.scoped(obligation{ID: id, Op: "old-op", Kind: "park-generation", Region: 0, Box: -1, Prefix: loc, Ret: "old", Quiet: w.now, Owner: boxOwner(from.ID)}, w.now, 1)) |
| 674 | return true |
| 675 | }) |
| 676 | w.terminate(from) |
| 677 | w.servingOn(t, to) |
| 678 | w.reach(t, 600, "the dead box's regional chore done", func() bool { return !hasObl(w.claim.Obl, id) }, w.actAll(), w.recoveryPass) |
| 679 | w.finish(t) |
| 680 | } |
| 681 | |
| 682 | func wRelocReplaceNotOwing(t *testing.T, w *world) { |
| 683 | w.twoBox() |
| 684 | from, to := w.boxes[0], w.boxes[3] |
| 685 | w.serve(from, 1, app0) |
| 686 | w.running(t, from) |
| 687 | w.drainTo(t, to) |
| 688 | // box 30 owes a park-local for the host: stale artifacts of an earlier |
| 689 | // stay under stamp 7 |
| 690 | spare := w.extraBox(0, 30) |
| 691 | spare.DB = &localDB{Inc: 1, Loc: w.claim.Holder.Location, State: map[string]int{}, Stamp: 7, Epoch: spare.Epoch} |
| 692 | spare.install(1, 7) |
| 693 | w.cas(w.claim, func(n *claim) bool { |
| 694 | n.Obl = append(n.Obl, obligation{ID: w.newID("ob"), Op: "stay", Kind: "park-local", Box: spare.ID, Region: -1, Ret: "stay"}) |
| 695 | return true |
| 696 | }) |
| 697 | if !w.relocPhase(t, "installing", w.act(from, to), w.recoveryPass) { |
| 698 | return |
| 699 | } |
| 700 | w.terminate(to) |
| 701 | w.servingOn(t, nil) |
| 702 | w.finish(t) |
| 703 | } |
| 704 | |
| 705 | func wRelocExhaustedFence(t *testing.T, w *world) { |
| 706 | w.twoBox() |
| 707 | from, to := w.boxes[0], w.boxes[3] |
| 708 | w.serve(from, 1, app0) |
| 709 | w.running(t, from) |
| 710 | b30, b31 := w.extraBox(0, 30), w.extraBox(0, 31) |
| 711 | w.userRelocate() |
| 712 | if w.claim.Op.Kind != "relocating" { |
| 713 | t.Fatalf("witness: no drain") |
| 714 | } |
| 715 | // three targets die in starting, the live source op.exec throughout |
| 716 | for _, x := range []*box{w.boxByID(w.claim.Op.Tgt), b30, b31, to} { |
| 717 | if x == nil || x.Destroyed || x.ID != w.claim.Op.Tgt { |
| 718 | continue |
| 719 | } |
| 720 | w.terminate(x) |
| 721 | w.reach(t, 60, "the dead target fenced", func() bool { return contains(w.claim.Lost, x.ID) }, w.act(from)) |
| 722 | } |
| 723 | if w.claim.Op.Stuck == "" { |
| 724 | t.Fatalf("witness: the exhausted target did not make the operation stuck: %s", w.state()) |
| 725 | } |
| 726 | w.extraBox(0, spareID()) // a spare the operator's replay may choose |
| 727 | w.servingOn(t, nil) |
| 728 | w.finish(t) |
| 729 | } |
| 730 | |
| 731 | func wFilesPreparedSeqZero(t *testing.T, w *world) { |
| 732 | w.twoBox() |
| 733 | from, to := w.boxes[0], w.boxes[3] |
| 734 | w.serve(from, 1, app0) |
| 735 | w.running(t, from) |
| 736 | for i := 0; i < 3; i++ { // the source publishes three manifests: its sequence reaches 3 |
| 737 | w.timerOn(from) |
| 738 | w.publishFiles(from) |
| 739 | w.completeDue(true) |
| 740 | } |
| 741 | w.drainTo(t, to) |
| 742 | third := w.extraBox(0, 30) |
| 743 | if !w.reach(t, 1500, "the probe runs on the target", func() bool { return preparedOpened(w.claim) && hasMain(to) }, w.act(from, to), w.recoveryPass, func() { w.wake(to) }) { |
| 744 | return |
| 745 | } |
| 746 | w.timerOn(to) // the probe session's timer, published at P's next sequence |
| 747 | w.publishFiles(to) |
| 748 | w.completeDue(true) |
| 749 | w.terminate(to) |
| 750 | w.servingOn(t, third) |
| 751 | w.finish(t) |
| 752 | } |
| 753 | |
| 754 | func wRelocPinEvidencedEmpty(t *testing.T, w *world) { |
| 755 | w.twoBox() |
| 756 | from, to := w.boxes[0], w.boxes[3] |
| 757 | _ = to |
| 758 | w.serve(from, 1, app0) |
| 759 | w.running(t, from) |
| 760 | w.published(t, from) |
| 761 | // the listing finds nothing although the writes are durable (ruling |
| 762 | // 15: a listing that finds nothing is no evidence); the model hides |
| 763 | // the objects for a while, then the listing shows them again |
| 764 | bk := w.buckets[0] |
| 765 | hidden := map[string][]*version{} |
| 766 | for _, k := range bk.keys(w.claim.Holder.Location) { |
| 767 | if isDataKey(k) { |
| 768 | hidden[k] = bk.objs[k] |
| 769 | delete(bk.objs, k) |
| 770 | } |
| 771 | } |
| 772 | w.terminate(from) |
| 773 | w.drive(60, never, w.act(to), w.recoveryPass) |
| 774 | for k, vs := range hidden { |
| 775 | bk.objs[k] = vs |
| 776 | } |
| 777 | w.servingOn(t, nil) |
| 778 | w.finish(t) |
| 779 | } |
| 780 | |
| 781 | // rev 3: 1b-next rev 17 to 19's fixes for findings F1 to F3, and L21 |
| 782 | |
| 783 | // wL21Window (files-pin-needs-key): the L21 window, explicit. The cold |
| 784 | // admission's pre-start manifest copy has landed without instance.key |
| 785 | // (§5.6 copies the manifest before the app starts); the app minted the |
| 786 | // key after it started, wrote rows sealed with it and replicated them; |
| 787 | // the publisher's manifest carrying the key has not landed when the box |
| 788 | // is terminated. Recovery fails safe: the pin refuses, the operation is |
| 789 | // stuck, and no database is installed without its key. Without the rule |
| 790 | // the keyless manifest is pinned and the install mints a fresh key over |
| 791 | // the sealed rows (INV-4). |
| 792 | func wL21Window(t *testing.T, w *world) { |
| 793 | w.twoBox() |
| 794 | from := w.boxes[0] |
| 795 | w.serve(from, 1, app0) |
| 796 | h := w.claim.Holder |
| 797 | w.issued++ |
| 798 | pre := &blob{Kind: "files", Inc: h.Inc, Gen: h.Gen, Seq: 1, Base: w.issued} // the pre-start copy: no files, no key |
| 799 | k := manifestKey(h.Location, h.Gen, 1) |
| 800 | w.buckets[0].objs[k] = []*version{{ID: w.newVer(), B: pre}} |
| 801 | from.pubGen, from.pubSeq = h.Gen, 1 |
| 802 | w.holdKey(h.Location + "files/") // the manifest with the key never lands |
| 803 | w.running(t, from) |
| 804 | w.appWrite(from) |
| 805 | w.replicate(from) |
| 806 | w.drive(30, never, w.act(from)) // the rows' uploads land; the manifest stays held |
| 807 | w.terminate(from) |
| 808 | w.drive(400, func() bool { return len(w.violations) > 0 || w.claim.Op.Stuck != "" }, w.actAll(), w.recoveryPass, w.wakeExec) |
| 809 | if len(w.violations) == 0 { |
| 810 | if c := w.claim; c.Op.Stuck == "" || c.Op.Prepared != "" { |
| 811 | w.violate("INV-3 (witness): the L21 failover neither stopped nor installed: %s", w.state()) |
| 812 | } |
| 813 | } |
| 814 | } |
| 815 | |
| 816 | // wNoSpareBound (reloc-no-spare-bound, F1): a drain's target fails its |
| 817 | // probe in a two-box region; with the bound the operation is stuck and |
| 818 | // the operator returns the host to the source; without it, it waits. |
| 819 | func wNoSpareBound(t *testing.T, w *world) { |
| 820 | w.twoBox() |
| 821 | w.claimC1 = true // the failed target's release (claim ask C1, finding 4) |
| 822 | from, to := w.boxes[0], w.boxes[3] |
| 823 | to.FailApp = true |
| 824 | w.serve(from, 1, app0) |
| 825 | w.running(t, from) |
| 826 | w.drainTo(t, to) |
| 827 | w.servingOn(t, from) |
| 828 | w.finish(t) |
| 829 | } |
| 830 | |
| 831 | // wDeadTargetBound (reloc-dead-target-bound, rev 18 finding 2): the |
| 832 | // drain's target is terminated at installing and the group launches no |
| 833 | // replacement (region 0 kept at one box: a capacity shortage), so no |
| 834 | // spare exists. With the bound the fence is consumed ReleaseDeadline |
| 835 | // later, the operation is stuck, and the operator's replay serves the |
| 836 | // host on the source; without it nothing moves. |
| 837 | func wDeadTargetBound(t *testing.T, w *world) { |
| 838 | w.twoBox() |
| 839 | from, to := w.boxes[0], w.boxes[3] |
| 840 | w.serve(from, 1, app0) |
| 841 | w.running(t, from) |
| 842 | w.published(t, from) |
| 843 | w.drainTo(t, to) |
| 844 | w.oneBoxRegion[0] = true |
| 845 | if !w.relocPhase(t, "installing", w.act(from, to), w.recoveryPass) { |
| 846 | return |
| 847 | } |
| 848 | w.terminate(to) |
| 849 | w.servingOn(t, from) |
| 850 | w.finish(t) |
| 851 | } |
| 852 | |
| 853 | // rev 4: Astra's round 1, claim §11's witnesses |
| 854 | |
| 855 | // wMoveUnchangedFile (files-objects-region-bound; claim §11 "move |
| 856 | // landing, source cleanup, then target failure with an unchanged file"): |
| 857 | // the host moves to region 1 carrying a file unchanged since region 0 |
| 858 | // published it; the landing's prepared manifest and the target's |
| 859 | // publications name an object in region 1's bucket; the source region is |
| 860 | // cleaned up; the target is terminated and the failover in region 1 pins |
| 861 | // that object. Without the region binding the manifests keep naming |
| 862 | // region 0's object, which no failover in region 1 can pin (INV-3). |
| 863 | func wMoveUnchangedFile(t *testing.T, w *world) { |
| 864 | w.twoBox() |
| 865 | src := w.boxes[0] |
| 866 | w.serve(src, 1, app0) |
| 867 | w.running(t, src) |
| 868 | w.published(t, src) |
| 869 | w.moveTo(1) |
| 870 | if !w.servingOn(t, nil) { |
| 871 | return |
| 872 | } |
| 873 | e := w.execBox(w.claim) |
| 874 | if e.Region != 1 { |
| 875 | w.violate("witness: the move did not land in region 1: %s", w.state()) |
| 876 | return |
| 877 | } |
| 878 | w.reach(t, 1200, "the source region cleaned up", func() bool { return len(w.claim.Obl) == 0 }, w.actAll(), w.recoveryPass) |
| 879 | w.published(t, e) |
| 880 | w.terminate(e) |
| 881 | w.reach(t, 3000, "serving again after the target's failover", func() bool { |
| 882 | c := w.claim |
| 883 | return c.Op.Kind == "serving" && c.Op.Exec >= 0 && c.Op.Exec != e.ID |
| 884 | }, w.actAll(), w.recoveryPass, w.operator, w.wakeExec) |
| 885 | w.finish(t) |
| 886 | } |
| 887 | |
| 888 | // wOriginsAfterTrim (files-origins-referenced; 1b-next rev 12 finding 1, |
| 889 | // R11-1): a file published in the origin generation never changes while |
| 890 | // ten cold admissions follow, so holder.admissions is trimmed past it |
| 891 | // while the live manifest still names the origin's object. The failover |
| 892 | // pins that object; authorized from the trimmed admissions alone, the pin |
| 893 | // is refused for ever (INV-3). |
| 894 | func wOriginsAfterTrim(t *testing.T, w *world) { |
| 895 | w.twoBox() |
| 896 | from := w.boxes[0] |
| 897 | w.serve(from, 1, app0) |
| 898 | w.running(t, from) |
| 899 | w.published(t, from) |
| 900 | for i := 0; i < 10; i++ { |
| 901 | w.crash(from) |
| 902 | if !w.reach(t, 400, "a fresh cold admission serving", func() bool { |
| 903 | return hasMain(from) && from.open == nil && len(w.claim.Obl) == 0 |
| 904 | }, w.actAll(), w.recoveryPass, func() { w.wake(from) }) { |
| 905 | return |
| 906 | } |
| 907 | } |
| 908 | for _, e := range w.claim.Holder.Admissions { |
| 909 | if e.Gen == "" || e.Predecessor.Gen == "" { |
| 910 | w.violate("witness: the origin generation is still in holder.admissions: %s", w.state()) |
| 911 | return |
| 912 | } |
| 913 | } |
| 914 | w.terminate(from) |
| 915 | w.servingOn(t, w.boxes[3]) |
| 916 | w.finish(t) |
| 917 | } |
| 918 | |
| 919 | // wClearAfterCleanup (reloc-clear-after-cleanup; claim §11 "a failed |
| 920 | // cleanup leaving a controller record that blocks executable updates"): |
| 921 | // the drain completes; the former source's participation is over, but its |
| 922 | // scoped cleanup fails, so its controller record stays and root refuses |
| 923 | // an executable update; once the cleanup succeeds the record is cleared |
| 924 | // and the update runs. Without the rule the record is cleared after the |
| 925 | // failed cleanup and the update runs over it (INV-29). |
| 926 | func wClearAfterCleanup(t *testing.T, w *world) { |
| 927 | w.twoBox() |
| 928 | from, to := w.boxes[0], w.boxes[3] |
| 929 | w.serve(from, 1, app0) |
| 930 | w.running(t, from) |
| 931 | w.published(t, from) |
| 932 | w.drainTo(t, to) |
| 933 | from.cleanupFails = true |
| 934 | if !w.servingOn(t, to) { |
| 935 | return |
| 936 | } |
| 937 | w.drive(20, never, w.act(from)) |
| 938 | if w.updateExecutable(from) { |
| 939 | if on("reloc-clear-after-cleanup") { |
| 940 | w.violate("witness: an update ran while the controller record existed") |
| 941 | } |
| 942 | return |
| 943 | } |
| 944 | from.cleanupFails = false |
| 945 | w.reach(t, 100, "the record cleared", func() bool { return from.execRecord == "" }, w.act(from)) |
| 946 | if !w.updateExecutable(from) { |
| 947 | w.violate("INV-3 (witness): the update stayed refused after a successful cleanup") |
| 948 | } |
| 949 | w.finish(t) |
| 950 | } |
| 951 | |
| 952 | // wCommittedLandingTargetLost (fence-converts-committed-landing; claim |
| 953 | // §11 "automatic target loss racing the record commit CAS", finding F5): |
| 954 | // the record commits the landing, and the target is terminated before |
| 955 | // the claim follows; the fence makes the committed landing a failover in |
| 956 | // region 1, which serves; without it nothing ever finishes it (INV-3). |
| 957 | func wCommittedLandingTargetLost(t *testing.T, w *world) { |
| 958 | w.twoBox() |
| 959 | src := w.boxes[0] |
| 960 | w.serve(src, 1, app0) |
| 961 | w.running(t, src) |
| 962 | w.published(t, src) |
| 963 | w.moveTo(1) |
| 964 | tgt := w.boxByID(w.claim.Op.Tgt) |
| 965 | if !w.stepUntil(t, 1500, "the record committed, the claim not yet", func() bool { |
| 966 | c := w.claim |
| 967 | return w.rec != nil && w.rec.MoveState == "committed" && c.Op.Kind == "landing" && !c.Op.Committed |
| 968 | }) { |
| 969 | return |
| 970 | } |
| 971 | w.terminate(tgt) |
| 972 | w.servingOn(t, nil) |
| 973 | w.finish(t) |
| 974 | } |
| 975 | |
| 976 | // wPushKeepsLiveFiles (files-live-set-moves-parks; finding F4): a push |
| 977 | // parks the whole location before installing its generation; the files |
| 978 | // live set survives it, so a later failover pins the live manifest's |
| 979 | // object. Without the rule the push archives them, and the failover can |
| 980 | // never pin the host's files (INV-3). |
| 981 | func wPushKeepsLiveFiles(t *testing.T, w *world) { |
| 982 | w.twoBox() |
| 983 | from := w.boxes[0] |
| 984 | w.serve(from, 1, app0) |
| 985 | w.running(t, from) |
| 986 | w.published(t, from) |
| 987 | w.userPush() |
| 988 | if !w.reach(t, 800, "the push served", func() bool { c := w.claim; return c.Op.Kind == "serving" && c.Holder.Gen != "" && len(c.Obl) == 0 }, w.actAll(), w.recoveryPass, func() { w.wake(from) }) { |
| 989 | return |
| 990 | } |
| 991 | w.drive(10, never, w.act(from)) |
| 992 | w.completeDue(true) |
| 993 | w.terminate(from) |
| 994 | w.servingOn(t, w.boxes[3]) |
| 995 | w.finish(t) |
| 996 | } |
| 997 | |
| 998 | // wLateManifestAfterMove (files-live-region; joint round 1 finding 1, |
| 999 | // claim §6.2a): the source in region 0 changes a file; the first PUT of |
| 1000 | // its new object is held, the publisher's retry lands, and the manifest |
| 1001 | // naming that object is held too. The host moves to region 1, which |
| 1002 | // admits a generation whose chain (genParent) leads back to the |
| 1003 | // source's; the source region is cleaned up, and only then do both held |
| 1004 | // PUTs land in region 0. Region 0 is no longer authoritative, so the late |
| 1005 | // manifest and the late object are residue there, and the at-rest sweep |
| 1006 | // retires both. Read without its region, the files live set finds the |
| 1007 | // late manifest as the chain's newest in region 0 and the object as the |
| 1008 | // one it names; they protect each other, and the sweep never retires |
| 1009 | // them (INV-10). |
| 1010 | func wLateManifestAfterMove(t *testing.T, w *world) { |
| 1011 | w.twoBox() |
| 1012 | src := w.boxes[0] |
| 1013 | w.serve(src, 1, app0) |
| 1014 | w.running(t, src) |
| 1015 | w.published(t, src) |
| 1016 | loc := w.claim.Holder.Location |
| 1017 | src.Files.Env++ // a changed file: its object first, then the manifest naming it |
| 1018 | obj := objectKey(loc, w.claim.Holder.Gen, src.Files) |
| 1019 | objHeld := false |
| 1020 | w.hold = func(r *request) bool { |
| 1021 | if r.key == obj && !objHeld { |
| 1022 | objHeld = true // the object's first PUT; the publisher's retry lands |
| 1023 | return true |
| 1024 | } |
| 1025 | return r.region == src.Region && isManifestKey(r.key) && strings.HasPrefix(r.key, loc) |
| 1026 | } |
| 1027 | held := func() (objs, mans int) { |
| 1028 | for _, r := range w.pending { |
| 1029 | if r.region == src.Region && r.doneAt == 1<<30 { |
| 1030 | if r.key == obj { |
| 1031 | objs++ |
| 1032 | } else if isManifestKey(r.key) { |
| 1033 | mans++ |
| 1034 | } |
| 1035 | } |
| 1036 | } |
| 1037 | return objs, mans |
| 1038 | } |
| 1039 | if !w.reach(t, 3*uploadTimeout, "the object's first PUT and the manifest naming it held", func() bool { |
| 1040 | o, m := held() |
| 1041 | return o == 1 && m == 1 |
| 1042 | }) { |
| 1043 | return |
| 1044 | } |
| 1045 | w.hold = nil |
| 1046 | if src.Files.Obj != obj { |
| 1047 | t.Fatalf("witness: the held manifest does not name the held object %s: %+v", obj, src.Files) |
| 1048 | } |
| 1049 | w.moveTo(1) |
| 1050 | if w.claim.Op.Kind != "moving" { |
| 1051 | t.Fatalf("witness: the move did not start: %s", w.state()) |
| 1052 | } |
| 1053 | if !w.servingOn(t, nil) { |
| 1054 | return |
| 1055 | } |
| 1056 | if e := w.execBox(w.claim); e == nil || e.Region != 1 { |
| 1057 | w.violate("witness: the move did not land in region 1: %s", w.state()) |
| 1058 | return |
| 1059 | } |
| 1060 | if !w.reach(t, 1200, "the source region cleaned up", func() bool { return len(w.claim.Obl) == 0 }, w.actAll(), w.recoveryPass) { |
| 1061 | return |
| 1062 | } |
| 1063 | if n := w.completeHeld(loc + "files/"); n != 2 { |
| 1064 | t.Fatalf("witness: held object and manifest PUTs completed: %d, want 2", n) |
| 1065 | } |
| 1066 | w.finish(t) |
| 1067 | } |
| 1068 | |
| 1069 | // wMoveStoppedKeepsLiveFiles (files-home-move-phases; joint round 1 |
| 1070 | // review I1, moves §5.1's authoritative-region table): the source in |
| 1071 | // region 0 serves with a keyed manifest in the origin generation. A move |
| 1072 | // to region 1 starts, and the source's agent restarts inside it: its cold |
| 1073 | // admission into a fresh generation publishes the marker, which queues |
| 1074 | // the origin's park-generation in region 0 (PublishGeneration, legal |
| 1075 | // inside an operation a writer runs in), and publishes no manifest of its |
| 1076 | // own (nothing changed), so the origin's manifest stays the chain's |
| 1077 | // newest. The source stops (op.exec none) and only then does the |
| 1078 | // sibling, box 3, run the park-generation. The source is terminated and |
| 1079 | // the fence converts the move to a failover in region 0. Region 0 is the |
| 1080 | // authoritative region before the flip, so the files live set kept the |
| 1081 | // manifest and the failover pins it and serves; with the files home read |
| 1082 | // from op.exec alone it was archived, and the failover finds no manifest |
| 1083 | // carrying instance.key: stuck for ever (INV-3). |
| 1084 | func wMoveStoppedKeepsLiveFiles(t *testing.T, w *world) { |
| 1085 | w.twoBox() |
| 1086 | src, sib := w.boxes[0], w.boxes[3] |
| 1087 | w.serve(src, 1, app0) |
| 1088 | w.running(t, src) |
| 1089 | w.published(t, src) |
| 1090 | loc := w.claim.Holder.Location |
| 1091 | if _, _, _, _, m := w.newestManifest(0, loc, w.claim.Holder.Gen); !manifestHasKey(m) { |
| 1092 | t.Fatalf("witness: the origin's manifest carries no instance.key: %s", w.state()) |
| 1093 | } |
| 1094 | w.moveTo(1) |
| 1095 | if w.claim.Op.Kind != "moving" { |
| 1096 | t.Fatalf("witness: the move did not start: %s", w.state()) |
| 1097 | } |
| 1098 | tgt := w.boxByID(w.claim.Op.Tgt) |
| 1099 | w.crash(src) |
| 1100 | parkQueued := func() bool { |
| 1101 | for _, o := range w.claim.Obl { |
| 1102 | if o.Kind == "park-generation" && o.Region == src.Region && o.Ret == "@root" { |
| 1103 | return true |
| 1104 | } |
| 1105 | } |
| 1106 | return false |
| 1107 | } |
| 1108 | if !w.reach(t, 200, "a fresh generation inside the move and the origin's park-generation queued", func() bool { |
| 1109 | return w.claim.Holder.Gen != "" && parkQueued() |
| 1110 | }, func() { w.worker(src); w.reconcile(src); w.wake(src) }) { |
| 1111 | return |
| 1112 | } |
| 1113 | if !w.reach(t, 400, "the source stopped", func() bool { |
| 1114 | c := w.claim |
| 1115 | return c.Op.Kind == "moving" && c.Op.Exec == -1 |
| 1116 | }, func() { w.worker(src); w.reconcile(src); w.worker(tgt); w.reconcile(tgt) }) { |
| 1117 | return |
| 1118 | } |
| 1119 | if !w.reach(t, 400, "the sibling ran the origin's park-generation while the move was stopped", func() bool { return !parkQueued() }, w.act(sib)) { |
| 1120 | return |
| 1121 | } |
| 1122 | if c := w.claim; c.Op.Kind != "moving" { |
| 1123 | t.Fatalf("witness: the move left its pre-flip phases before the park: %s", w.state()) |
| 1124 | } |
| 1125 | w.terminate(src) |
| 1126 | w.servingOn(t, nil) |
| 1127 | w.finish(t) |
| 1128 | } |
| 1129 | |
| 1130 | // wRollbackKeepsSourceFiles (files-home-move-phases; Astra joint round |
| 1131 | // 2): the stopped-move witness's setup, the source's restart inside a move |
| 1132 | // to region 1 queuing the origin's park-generation in region 0 while the |
| 1133 | // origin holds the keyed manifest, but the park waits until the move has |
| 1134 | // flipped and the target's probe is admitted (holder.generation is the |
| 1135 | // target's), before the commit. The sibling runs it then. The landing |
| 1136 | // misses its cut deadline and rolls back cleanly: the return names the |
| 1137 | // source's generation again in region 0, and the source serves there with |
| 1138 | // its files unchanged, so the publisher has nothing to republish. The |
| 1139 | // source is then terminated. Until the commit a rollback is possible, so |
| 1140 | // region 0 stayed the files home and the failover there pins the keyed |
| 1141 | // manifest and serves; with region 0 home only until the probe's |
| 1142 | // admission (dfab457c) or never (the mutation) the park archived it, and |
| 1143 | // the failover finds no manifest carrying instance.key: stuck for ever |
| 1144 | // (INV-3). |
| 1145 | func wRollbackKeepsSourceFiles(t *testing.T, w *world) { |
| 1146 | w.twoBox() |
| 1147 | src, sib := w.boxes[0], w.boxes[3] |
| 1148 | w.serve(src, 1, app0) |
| 1149 | w.running(t, src) |
| 1150 | w.published(t, src) |
| 1151 | loc := w.claim.Holder.Location |
| 1152 | published := w.stats["files manifests published"] |
| 1153 | if _, _, _, _, m := w.newestManifest(0, loc, w.claim.Holder.Gen); !manifestHasKey(m) { |
| 1154 | t.Fatalf("witness: the origin's manifest carries no instance.key: %s", w.state()) |
| 1155 | } |
| 1156 | w.moveTo(1) |
| 1157 | if w.claim.Op.Kind != "moving" { |
| 1158 | t.Fatalf("witness: the move did not start: %s", w.state()) |
| 1159 | } |
| 1160 | tgt := w.boxByID(w.claim.Op.Tgt) |
| 1161 | w.crash(src) |
| 1162 | parkQueued := func() bool { |
| 1163 | for _, o := range w.claim.Obl { |
| 1164 | if o.Kind == "park-generation" && o.Region == src.Region && o.Ret == "@root" { |
| 1165 | return true |
| 1166 | } |
| 1167 | } |
| 1168 | return false |
| 1169 | } |
| 1170 | if !w.reach(t, 200, "a fresh generation inside the move and the origin's park-generation queued", func() bool { |
| 1171 | return w.claim.Holder.Gen != "" && parkQueued() |
| 1172 | }, func() { w.worker(src); w.reconcile(src); w.wake(src) }) { |
| 1173 | return |
| 1174 | } |
| 1175 | srcGen := w.claim.Holder.Gen |
| 1176 | if !w.reach(t, 400, "the target's probe admitted, before the commit", func() bool { |
| 1177 | c := w.claim |
| 1178 | return c.Op.Kind == "landing" && !c.Op.Committed && c.Holder.Gen != srcGen && w.rec.MoveState == "landing" |
| 1179 | }, func() { w.worker(src); w.reconcile(src); w.worker(tgt); w.reconcile(tgt); w.runConsole() }) { |
| 1180 | return |
| 1181 | } |
| 1182 | if !w.reach(t, 400, "the sibling ran the origin's park-generation before the commit", func() bool { return !parkQueued() }, w.act(sib)) { |
| 1183 | return |
| 1184 | } |
| 1185 | if c := w.claim; c.Op.Kind != "landing" || c.Op.Committed { |
| 1186 | t.Fatalf("witness: the landing committed before the park: %s", w.state()) |
| 1187 | } |
| 1188 | // the target's agent stalls past the cut deadline; it rolls back when it |
| 1189 | // next acts, having written nothing |
| 1190 | deadline := w.claim.Op.CutDeadline |
| 1191 | w.drive(deadline+1-w.now, never, w.act(sib)) |
| 1192 | if !w.reach(t, 1500, "the clean return serving on the source", func() bool { |
| 1193 | c := w.claim |
| 1194 | return c.Op.Kind == "serving" && c.Op.Exec == src.ID // the return named srcGen; the re-admission moved to a fresh generation from it |
| 1195 | }, w.actAll(), w.recoveryPass, w.runConsole, func() { w.wake(src) }) { |
| 1196 | return |
| 1197 | } |
| 1198 | if w.stats["rollback-clean"] == 0 { |
| 1199 | t.Fatalf("witness: the rollback was not clean: %s", w.state()) |
| 1200 | } |
| 1201 | w.drive(20, never, w.act(src)) |
| 1202 | w.completeDue(true) |
| 1203 | if n := w.stats["files manifests published"]; n != published { |
| 1204 | t.Fatalf("witness: the publisher republished (%d manifests, %d before the move): the files are unchanged", n, published) |
| 1205 | } |
| 1206 | if _, _, _, _, m := w.newestManifest(src.Region, loc, w.claim.Holder.Gen); m == nil && on("files-home-move-phases") { |
| 1207 | t.Fatalf("witness: no manifest in the source region after the return: %s", w.state()) |
| 1208 | } |
| 1209 | w.terminate(src) |
| 1210 | w.reach(t, 3000, "serving again after the source's failover", func() bool { |
| 1211 | c := w.claim |
| 1212 | return c.Op.Kind == "serving" && c.Op.Exec >= 0 && c.Op.Exec != src.ID |
| 1213 | }, w.actAll(), w.recoveryPass, w.operator, w.wakeExec) |
| 1214 | w.finish(t) |
| 1215 | } |
| 1216 | |
| 1217 | // wParkEvidenceEveryBox (park-evidence-every-box; final review Important |
| 1218 | // 2, the shape of two-box seed 819): the host serves on box 0 with an |
| 1219 | // acknowledged write its replicator has not shipped, and a delete |
| 1220 | // begins. Region 0's park-replica is a regional chore, and box 3, the |
| 1221 | // sibling, runs it while box 0's agent does nothing (its replicator, a |
| 1222 | // process of its own, still runs). With the rule box 3 waits for box 0's |
| 1223 | // stop evidence, which comes only when box 0's agent acts, and the park |
| 1224 | // covers the write; without it box 3 parks region 0 on its own evidence, |
| 1225 | // box 0's replicator then ships the write into the parked region, and the |
| 1226 | // host is freed with it as residue (INV-10). |
| 1227 | func wParkEvidenceEveryBox(t *testing.T, w *world) { |
| 1228 | w.twoBox() |
| 1229 | writer, sib := w.boxes[0], w.boxes[3] |
| 1230 | w.serve(writer, 1, app0) |
| 1231 | w.running(t, writer) |
| 1232 | w.appWrite(writer) |
| 1233 | w.userDelete() |
| 1234 | if w.claim.Op.Kind != "deleting" { |
| 1235 | t.Fatalf("witness: the delete did not begin: %s", w.state()) |
| 1236 | } |
| 1237 | owed := func() bool { |
| 1238 | for _, o := range w.claim.Obl { |
| 1239 | if o.Kind == "park-replica" && o.Region == writer.Region && o.Prefix == w.claim.Holder.Location { |
| 1240 | return true |
| 1241 | } |
| 1242 | } |
| 1243 | return false |
| 1244 | } |
| 1245 | if !w.reach(t, 50, "region 0's park-replica queued", owed, w.runConsole) { |
| 1246 | return |
| 1247 | } |
| 1248 | w.drive(6*horizonH, func() bool { return !owed() }, w.runConsole, w.act(sib), w.recoveryPass) |
| 1249 | w.logf("witness: box 0's replicator ships its queue") |
| 1250 | w.replicate(writer) |
| 1251 | w.finish(t) |
| 1252 | } |
| 1253 | |
| 1254 | // TestFilesWitnessesStuckWithoutINV30 keeps the liveness half of the files |
| 1255 | // witnesses (joint round 2). INV-30 now catches each of their mutations |
| 1256 | // at the archive, so TestWitnesses names INV-30; with INV-30 off, the |
| 1257 | // same scenario under the same mutation must still end in the failure it |
| 1258 | // was written for, the failover that can never pin the host's files |
| 1259 | // (INV-3), and must hold with the rule in place. |
| 1260 | func TestFilesWitnessesStuckWithoutINV30(t *testing.T) { |
| 1261 | saved := mutated |
| 1262 | defer func() { mutated = saved }() |
| 1263 | n := 0 |
| 1264 | for _, x := range witnesses { |
| 1265 | if x.want != "INV-30" || x.rule == "dirty-return-needs-admission" { |
| 1266 | // dirty-return-needs-admission's loss has no liveness consequence |
| 1267 | // in its scenario (the dirty return serves from the returned |
| 1268 | // seal): INV-30, the independent preservation invariant, is its |
| 1269 | // only oracle (Astra joint round 4) |
| 1270 | continue |
| 1271 | } |
| 1272 | n++ |
| 1273 | for _, m := range []string{"", x.needs} { |
| 1274 | mutated = m |
| 1275 | w := newWitness() |
| 1276 | w.noPinWatch = true |
| 1277 | x.run(t, w) |
| 1278 | switch { |
| 1279 | case m == "" && len(w.violations) > 0: |
| 1280 | t.Errorf("witness %s (INV-30 off) violated with its rule in place: %s", x.rule, w.violations[0]) |
| 1281 | case m != "" && (len(w.violations) == 0 || !namedFailure(w.violations[0], "INV-3")): |
| 1282 | dump(t, w) |
| 1283 | t.Errorf("witness %s under %q with INV-30 off: want INV-3, got %v", x.rule, m, w.violations) |
| 1284 | } |
| 1285 | } |
| 1286 | } |
| 1287 | if n != 4 { |
| 1288 | t.Fatalf("files witnesses naming INV-30: %d, want 4 (files-live-set, files-live-set-moves-parks, files-home-move-phases twice)", n) |
| 1289 | } |
| 1290 | } |
| 1291 | |
amadan