| 1 | #!/bin/bash |
| 2 | # Mutation checks for the scheduler's invariants (zero-downtime plan 5, task |
| 3 | # 16). Each mutant rewrites one marked line (// rolloutsim:Mn) in a scratch |
| 4 | # copy of the committed tree (git archive HEAD), never in the checkout, and |
| 5 | # runs TestSimInvariants against it. A clean baseline run of the unmutated |
| 6 | # copy comes first: a kill means nothing if the simulation fails anyway. |
| 7 | # |
| 8 | # A mutant whose invariant the simulation cannot reach names a unit test |
| 9 | # instead (its third field "test:TestName"; zero-downtime flag readiness, |
| 10 | # task 16 rule 2). Its run is that one test (-run '^TestName$'), and the |
| 11 | # test gets a clean baseline run of its own on the unmutated copy too. Such |
| 12 | # a mutant is the exception: each says in the list below why the simulation |
| 13 | # cannot catch it. |
| 14 | # |
| 15 | # internal/rollout/testdata/rolloutsim/mutate.sh # 200 seeds |
| 16 | # internal/rollout/testdata/rolloutsim/mutate.sh 300 # 300 seeds |
| 17 | # internal/rollout/testdata/rolloutsim/mutate.sh 200 M3 # only M3 |
| 18 | # |
| 19 | # The script runs at nice 19 (it re-executes itself under nice if it has to, |
| 20 | # and warns if it cannot) and one run at a time with GOMAXPROCS=2 (the CPU |
| 21 | # budget on shared boxes). Each go test run's timeout grows with the seeds, |
| 22 | # SEEDS * 3 / 100 + 20 minutes (3000 seeds: 110 minutes); the header prints |
| 23 | # it. A fixed 20 minutes was too short for 3000 seeds (round 1). |
| 24 | # |
| 25 | # The simulation's invariants are I1 to I10 (TestSimInvariants' doc). I9 |
| 26 | # and I10 run only on the seeds whose failure book is on disk, which the |
| 27 | # simulation turns off when it runs as root (root writes into a read-only |
| 28 | # directory, so it cannot fail a save): as root, M13 to M17 read MISSED. |
| 29 | # |
| 30 | # Execution integrity is recorded apart from detection. A run must build, |
| 31 | # start, and end in its own --- PASS or --- FAIL line for the test it ran |
| 32 | # (TestSimInvariants, or a unit-test mutant's own test), with no panic, no |
| 33 | # timeout and no "rolloutsim: crash at seed" line (a panic of the simulation |
| 34 | # or of the code under test, which the test recovers and reports apart from |
| 35 | # violations). A run that breaks integrity fails the mutant's gate even when |
| 36 | # it also reported the expected violation; that kill is still printed, as a |
| 37 | # diagnostic. |
| 38 | # |
| 39 | # Verdicts: |
| 40 | # CAUGHT the run executed intact and reported a violation of the |
| 41 | # mutant's own invariant ("rolloutsim: I2 violated at seed", |
| 42 | # any of I1 to I10), or, for a unit-test mutant, its own test |
| 43 | # ended in --- FAIL |
| 44 | # BROKEN the run panicked, timed out, crashed or never ran |
| 45 | # MISSED the run passed, or reported only other invariants' violations |
| 46 | # ERROR the marker is not on exactly one line, the substitution did not |
| 47 | # apply, or the copy did not build |
| 48 | # Each baseline (the simulation's, and one per unit test a selected mutant |
| 49 | # names) is PASSED or, like a mutant, BROKEN or FAILED. The simulation's |
| 50 | # baseline runs only when a selected mutant runs the simulation. Exit 1 on |
| 51 | # anything but a PASSED baseline and CAUGHT for every mutant. |
| 52 | # |
| 53 | # A mutant named on the command line that is not in the list below is an |
| 54 | # ERROR, reported before anything runs, and the script exits 1: a typo must |
| 55 | # never pass as a selection that checked nothing. |
| 56 | # |
| 57 | # Scratch: one fresh directory per run, made with mktemp -d under $TMPDIR |
| 58 | # (named zdd5-mut.XXXXXX) and printed first. When the run ends with a PASSED |
| 59 | # baseline and every selected mutant CAUGHT, the whole directory is removed |
| 60 | # on exit. On any other outcome (a failure, an interrupted run) only its tree |
| 61 | # copy is removed, and its path is printed again: the logs stay there to be |
| 62 | # read, and removed by hand after. The script never touches any other path. |
| 63 | set -u |
| 64 | if [ "$(nice)" -lt 19 ] && [ -z "${ROLLOUTSIM_RENICED:-}" ]; then |
| 65 | ROLLOUTSIM_RENICED=1 exec nice -n 19 "$0" "$@" |
| 66 | fi |
| 67 | if [ "$(nice)" -lt 19 ]; then |
| 68 | echo "warning: running at niceness $(nice), not 19" >&2 |
| 69 | fi |
| 70 | SEEDS=${1:-200} |
| 71 | shift $(($# > 0 ? 1 : 0)) |
| 72 | ONLY=" $* " |
| 73 | # Each go test run's timeout, scaled with the seeds (3000 seeds: 110m). |
| 74 | TIMEOUT_MIN=$((SEEDS * 3 / 100 + 20)) |
| 75 | |
| 76 | # name|file|check|perl substitution applied to the marked line only. check |
| 77 | # is the simulation invariant that must catch the mutant (I1 to I10), or |
| 78 | # test:TestName for a unit-test mutant. The marker match is anchored (\b), |
| 79 | # so rolloutsim:M1 never matches rolloutsim:M10. The substitution is the |
| 80 | # last field, so it may contain "|". |
| 81 | # |
| 82 | # M7 to M12 are zero-downtime flag readiness task 16's: |
| 83 | # M7 decideHoldRan's Blocks check on the marked build (Astra R3 N7): I1. |
| 84 | # M8 ClearHoldRanBefore's sequence test (Astra R3 N6): I5, at a good |
| 85 | # write delivered late, after a hold adoption failed on the host. |
| 86 | # M9 preRetryLocked never reports a failure stale (ruling 191): I7. |
| 87 | # M10 a Begin whose save failed runs the attempt anyway (F5): I8, on a |
| 88 | # seed whose book is on disk, across a read-only window. |
| 89 | # M11 failCohort halts the cohort on a PreRetry failure (plan review |
| 90 | # finding 3): I7's cohort check. |
| 91 | # M12 markLocked keeps the marker's Seq for another execution of the |
| 92 | # same build (plan review finding 4). A unit test, by rule 2: the |
| 93 | # simulation cannot reach it. The kill needs a good write whose |
| 94 | # execution began while a marker of build X stood, then a second |
| 95 | # execution of X marking the host before that write lands. A wake |
| 96 | # planned under X's marker boots X as a first wake, whose intent |
| 97 | # refuses every adoption of the host until it settles, so no second |
| 98 | # run of X can start inside that window; only an ordinary wake of a |
| 99 | # build the host served before, under another build's marker, leaves |
| 100 | # it open, and that needs X installed again and adopted on a hold. |
| 101 | # |
| 102 | # M13 to M17 are zero-downtime flag readiness round 2 task 2's (the |
| 103 | # crash-epoch hard limit), each on a seed whose book is on disk: |
| 104 | # M13 PublishedEpoch ignores its dirty check: I10. A change made while |
| 105 | # saves fail moves the generation in memory only; status publishes |
| 106 | # it, and the last landed file holds another. |
| 107 | # M14 markLocked's marker set, renewed or replaced moves no generation: |
| 108 | # I9. A grant issued under X's hold-ran marker, then another hold run |
| 109 | # of X on the host (a first wake under the marker, stopped before it |
| 110 | # settles: the simulation's rewakeArm and rewakeRun) renews the marker |
| 111 | # at the same generation, and the grant, delivered after, clears the |
| 112 | # newer run's marker. (The plan's witness, X's marker replaced by a |
| 113 | # failed hold run of Y and Y's marker then cleared by a pointer, |
| 114 | # catches nothing: the pointer's clear, ClearHoldRanOnPointer, moves |
| 115 | # the generation on its own line.) |
| 116 | # M15 the reopen's seq keeps only the file's own seq, halved: I9. The |
| 117 | # max over the saved generations and markers (highestSaved), which |
| 118 | # would repair a lowered seq, is not taken, so the reopened book |
| 119 | # hands out again generations it had published (each restart halves |
| 120 | # it again), and a grant issued before a restart, still pending, |
| 121 | # matches a restriction that a failure after it made, typically an |
| 122 | # intent the restart reconciled. |
| 123 | # M16 RetryHostAt skips the book-identity comparison: I9. A box rebuild |
| 124 | # opens a new book whose generations start again from one, so a |
| 125 | # grant for the old book, still pending, matches a restriction the |
| 126 | # new one made. One of the two rarest kills (with M17): at 300 seeds |
| 127 | # it rests on a few seeds (rebuilds are drawn 1 step in 150). So a |
| 128 | # MISSED for M16 at 300 seeds or fewer is not yet a regression: run |
| 129 | # it again at 3000 seeds (mutate.sh 3000 M16) before reading it as |
| 130 | # one. |
| 131 | # M17 a new record moves the app's generation only from zero (the |
| 132 | # sequence still advances, so nothing else changes): I9. A new |
| 133 | # record holds every host of the app (spec §8.4), so a grant issued |
| 134 | # under X's hold-ran marker on h, then a failure of X on another |
| 135 | # host that writes X's new record, then the grant delivered: it |
| 136 | # clears the marker and exempts h from the new record. I9 counts a |
| 137 | # new record as a fact of every host. The random schedule seldom |
| 138 | # lines this up (a build with a marker and no record has seldom |
| 139 | # failed anywhere), so the simulation's rewakeArm makes it: when X |
| 140 | # has no record, the wake after the Retry is another instance's |
| 141 | # first wake of X, made to fail. Like M16 it rests on |
| 142 | # few seeds at 300, and the same rule holds: a MISSED at 300 seeds |
| 143 | # or fewer is re-run at 3000 before it is read as a regression. |
| 144 | # (Removing the touch outright leaves the generation zero when the |
| 145 | # new record is the app's first restriction, so every retry is |
| 146 | # refused and I7 catches it first, which is not the hole this |
| 147 | # mutant is for.) |
| 148 | MUTANTS='M1|queue.go|I2|s/if q\.running >= q\.concurrency \{/if false \&\& q.running >= q.concurrency {/ |
| 149 | M2|queue.go|I3|s/class := classRecover/class := classAdopt/ |
| 150 | M3|queue.go|I1|s/res, err = book\.Record\(rec\)/res, err = Recorded, nil/ |
| 151 | M4|queue.go|I4|s/h\.buildRev = q\.nextRev\(\)/_ = q.nextRev()/ |
| 152 | M5|wakeplan.go|I1|s/if hasGood \&\& in\.Book\.Blocks\(/if false \&\& in.Book.Blocks(/ |
| 153 | M6|wakeplan.go|I1|s/plan\.Fallback = \&good/plan.Fallback = nil/ |
| 154 | M7|wakeplan.go|I1|s/if hasGood \&\& in\.Book\.Blocks\(/if false \&\& hasGood \&\& in.Book.Blocks(/ |
| 155 | M8|failures.go|I5|s/cur\.Seq >= snap \{/cur.Seq > ^uint64(0) {/ |
| 156 | M9|failures.go|I7|s/if r\.Seq == 0 \{/if true {/ |
| 157 | M10|scheduler.go|I8|s/; err != nil \{/; errors.Is(err, ErrIntentStands) {/ |
| 158 | M11|queue.go|I7|s/if res == PreRetry \{/if false \&\& res == PreRetry {/ |
| 159 | M12|failures.go|test:TestAnotherExecutionOfTheMarkedBuildRenewsTheMarker|s/h\.Seq = b\.bumpLocked\(\)/if ok \&\& cur.Build == h.Build { h.Seq = cur.Seq } else { h.Seq = b.bumpLocked() }/ |
| 160 | M13|failures.go|I10|s/if b\.dirty \{/if false \&\& b.dirty {/ |
| 161 | M14|failures.go|I9|s/b\.touchLocked\(h\.Account, h\.App\)// |
| 162 | M15|failures.go|I9|s/b\.seq = f\.highestSaved\(\)/b.seq = f.Seq \/ 2/ |
| 163 | M16|failures.go|I9|s/ \|\| book != b\.idLocked\(\)// |
| 164 | M17|failures.go|I9|s/b\.touchLocked\(r\.Account, r\.App\)/if b.gens[genKey(r.Account, r.App)] == 0 { b.touchLocked(r.Account, r.App) } else { b.bumpLocked() }/' |
| 165 | |
| 166 | # Every name selected must be a mutant in the list, checked before any work. |
| 167 | KNOWN=" $(printf '%s\n' "$MUTANTS" | cut -d'|' -f1 | tr '\n' ' ')" |
| 168 | unknown=0 |
| 169 | for name in "$@"; do |
| 170 | if [[ "$KNOWN" != *" $name "* ]]; then |
| 171 | echo "ERROR $name: no such mutant (known:${KNOWN% })" |
| 172 | unknown=1 |
| 173 | fi |
| 174 | done |
| 175 | [ $unknown -eq 0 ] || exit 1 |
| 176 | |
| 177 | export GOMAXPROCS=2 |
| 178 | ROOT=$(git -C "$(dirname "$0")" rev-parse --show-toplevel) || exit 2 |
| 179 | SCRATCH=$(mktemp -d "${TMPDIR:?}/zdd5-mut.XXXXXX") || exit 2 |
| 180 | echo "scratch: $SCRATCH" |
| 181 | # fail is the run's verdict so far; complete is set only once every |
| 182 | # selected mutant has a verdict. The exit trap removes the scratch |
| 183 | # directory whole only when both say the run passed. |
| 184 | fail=0 |
| 185 | complete=0 |
| 186 | cleanup() { |
| 187 | if [ $complete -eq 1 ] && [ $fail -eq 0 ]; then |
| 188 | rm -rf "$SCRATCH" |
| 189 | else |
| 190 | rm -rf "$SCRATCH/tree" "$SCRATCH/orig" "$SCRATCH/gowork" |
| 191 | echo "scratch kept: $SCRATCH (logs in $SCRATCH/logs; remove it after reading)" |
| 192 | fi |
| 193 | } |
| 194 | trap cleanup EXIT |
| 195 | P=internal/rollout |
| 196 | # The default build cache is read-only inside a sandbox. |
| 197 | if [ -z "${GOCACHE:-}" ] && [ ! -w "$(go env GOCACHE)" ]; then |
| 198 | export GOCACHE=$TMPDIR/gocache |
| 199 | fi |
| 200 | # An archive has no .git, so VCS stamping must be off. |
| 201 | export GOFLAGS="${GOFLAGS:-} -buildvcs=false" |
| 202 | mkdir -p "$SCRATCH/tree" "$SCRATCH/orig" "$SCRATCH/logs" "$SCRATCH/gowork" || exit 2 |
| 203 | export GOTMPDIR=$SCRATCH/gowork |
| 204 | git -C "$ROOT" archive HEAD | tar -x -C "$SCRATCH/tree" || exit 2 |
| 205 | echo "tree: $(git -C "$ROOT" rev-parse --short HEAD)" |
| 206 | echo "seeds: $SEEDS; timeout per run: ${TIMEOUT_MIN}m" |
| 207 | cp -a "$SCRATCH/tree/$P/." "$SCRATCH/orig/" || exit 2 |
| 208 | |
| 209 | # testOf CHECK: the test a mutant's run executes. |
| 210 | testOf() { |
| 211 | case "$1" in |
| 212 | test:*) echo "${1#test:}" ;; |
| 213 | *) echo TestSimInvariants ;; |
| 214 | esac |
| 215 | } |
| 216 | |
| 217 | # run LOG TEST: one go test call of TEST against the scratch tree, verbose |
| 218 | # so that the test prints its --- PASS or --- FAIL line. |
| 219 | run() { |
| 220 | (cd "$SCRATCH/tree" && ROLLOUT_SIM_SEEDS="$SEEDS" go test -v -p 1 -count=1 -timeout "${TIMEOUT_MIN}m" \ |
| 221 | -run "^$2\$" ./$P/) >"$1" 2>&1 |
| 222 | } |
| 223 | |
| 224 | # integrity LOG TEST: empty when the run of TEST executed intact, else what |
| 225 | # broke it. |
| 226 | integrity() { |
| 227 | if grep -q '\[build failed\]\|\[setup failed\]' "$1"; then |
| 228 | echo BUILD |
| 229 | elif grep -q '^panic: test timed out' "$1"; then |
| 230 | echo TIMEOUT |
| 231 | elif grep -qE '^(panic: |fatal error: )' "$1"; then |
| 232 | echo PANIC |
| 233 | elif grep -q 'rolloutsim: crash at seed' "$1"; then |
| 234 | echo CRASH |
| 235 | elif ! grep -qE -- "--- (PASS|FAIL): $2 \(" "$1"; then |
| 236 | echo NOT-RUN |
| 237 | fi |
| 238 | } |
| 239 | |
| 240 | # found LOG: the invariants the run reported violated, e.g. "I1 I3". |
| 241 | found() { |
| 242 | grep -oE 'rolloutsim: I[0-9]+ violated at seed' "$1" | awk '{print $2}' | sort -u | tr '\n' ' ' | sed 's/ $//' |
| 243 | } |
| 244 | |
| 245 | selected() { |
| 246 | [ "$ONLY" = " " ] || [[ "$ONLY" == *" $1 "* ]] |
| 247 | } |
| 248 | |
| 249 | # The baselines: the simulation's when a selected mutant runs it, and each |
| 250 | # unit test a selected mutant names, once. |
| 251 | tests=$(while IFS='|' read -r name _ check _; do |
| 252 | selected "$name" && testOf "$check" |
| 253 | done <<<"$MUTANTS" | awk '!seen[$0]++') |
| 254 | for t in $tests; do |
| 255 | blog="$SCRATCH/logs/baseline-$t.log" |
| 256 | what="$t" |
| 257 | [ "$t" = TestSimInvariants ] && what="$SEEDS seeds" |
| 258 | run "$blog" "$t" |
| 259 | broke=$(integrity "$blog" "$t") |
| 260 | if [ -n "$broke" ]; then |
| 261 | echo "BROKEN baseline: $t: $broke; see $blog" |
| 262 | fail=1 |
| 263 | elif grep -qF -- "--- FAIL: $t (" "$blog"; then |
| 264 | echo "FAILED baseline: $t failed on the unmutated tree (violations: $(found "$blog")); see $blog" |
| 265 | fail=1 |
| 266 | else |
| 267 | echo "PASSED baseline: $what" |
| 268 | fi |
| 269 | done |
| 270 | |
| 271 | while IFS='|' read -r name file inv sub; do |
| 272 | if ! selected "$name"; then |
| 273 | continue |
| 274 | fi |
| 275 | test=$(testOf "$inv") |
| 276 | marker="rolloutsim:$name" |
| 277 | src="$SCRATCH/tree/$P/$file" |
| 278 | # Each marker sits on exactly one line of the package's Go sources. |
| 279 | lines=$(cat "$SCRATCH/orig"/*.go | grep -cE "$marker\\b") |
| 280 | if [ "$lines" -ne 1 ]; then |
| 281 | echo "ERROR $name: $marker is on $lines lines of $P/*.go, not one" |
| 282 | fail=1 |
| 283 | continue |
| 284 | fi |
| 285 | cp "$SCRATCH/orig/$file" "$src" |
| 286 | perl -pi -e "if (/\\Q$marker\\E\\b/) { $sub }" "$src" |
| 287 | if cmp -s "$SCRATCH/orig/$file" "$src"; then |
| 288 | echo "ERROR $name: the substitution did not apply to $file" |
| 289 | fail=1 |
| 290 | continue |
| 291 | fi |
| 292 | mutated=$(grep -E "$marker\\b" "$src" | sed 's/^[[:space:]]*//') |
| 293 | log="$SCRATCH/logs/$name.log" |
| 294 | run "$log" "$test" |
| 295 | cp "$SCRATCH/orig/$file" "$src" |
| 296 | broke=$(integrity "$log" "$test") |
| 297 | caught=0 |
| 298 | if [ "$test" = TestSimInvariants ]; then |
| 299 | got=$(found "$log") |
| 300 | [[ " $got " == *" $inv "* ]] && caught=1 |
| 301 | detail="expects $inv; reported: ${got:-none}; line: $mutated" |
| 302 | else |
| 303 | got=passed |
| 304 | grep -qF -- "--- FAIL: $test (" "$log" && got=failed caught=1 |
| 305 | detail="expects $test to fail; it $got; line: $mutated" |
| 306 | fi |
| 307 | if [ "$broke" = BUILD ]; then |
| 308 | echo "ERROR $name: the mutant did not build; $detail; see $log" |
| 309 | fail=1 |
| 310 | elif [ -n "$broke" ]; then |
| 311 | kill="not caught" |
| 312 | [ $caught -eq 1 ] && kill="caught (diagnostic only)" |
| 313 | echo "BROKEN $name: execution integrity failed: $broke; $kill; $detail; see $log" |
| 314 | fail=1 |
| 315 | elif [ $caught -eq 1 ]; then |
| 316 | echo "CAUGHT $name: $detail" |
| 317 | else |
| 318 | echo "MISSED $name: $detail" |
| 319 | fail=1 |
| 320 | fi |
| 321 | done <<<"$MUTANTS" |
| 322 | complete=1 |
| 323 | exit $fail |
| 324 | |
amadan