==> tests/election.c <==1/* fleet.rs's election tests over the simulated network: a leader is elected and commits (n = 3, 4,
2 * 5), a minority refuses changes, a 2 + 2 split has no leader, the pair's fixed coordinator, terms and
3 * votes survive restarts, and the randomised run over 300 seeds (partitions, crashes, restarts,
4 * message loss, disks that fill up). */
5#include "sim.h"
6
7static uint64_t committed_version(sim_t *s, uint32_t k) { return mfc_committed(s->cores[k])->version; }
8
9/* fleet.rs a_leader_is_elected_and_commits */
10static void elected_and_commits(void) {
11 for (uint32_t n = 3; n <= 5; n++) {
12 sim_t s;
13 sim_init(&s, n, 7 + n, 0);
14 sim_step(&s, 5000);
15 int l = sim_leader(&s);
16 CHECK(l >= 0);
17 char *err = NULL;
18 uint64_t v = sim_propose(&s, (uint32_t)l, "a", &err);
19 CHECK(v > 0);
20 sim_step(&s, 1000);
21 for (uint32_t k = 0; k < n; k++) CHECK_U(committed_version(&s, k), v);
22 /* The leader dies: another leads within ~3.6 s (its link closed: sooner). */
23 sim_crash(&s, (uint32_t)l);
24 uint64_t t0 = s.now;
25 while (sim_leader(&s) < 0 && s.now - t0 < 4000) sim_step(&s, 25);
26 int l2 = sim_leader(&s);
27 CHECK(l2 >= 0 && l2 != l);
28 sim_step(&s, 500);
29 uint64_t v2 = sim_propose(&s, (uint32_t)l2, "b", &err);
30 CHECK(v2 > 0);
31 sim_step(&s, 1000);
32 /* It comes back: catches up, and does not disturb the new leader (pre-vote). */
33 uint64_t term = mfc_term(s.cores[l2]);
34 sim_restart(&s, (uint32_t)l);
35 sim_step(&s, 3000);
36 CHECK_I(sim_leader(&s), l2);
37 CHECK_U(mfc_term(s.cores[l2]), term);
38 uint64_t want = v2 > committed_version(&s, (uint32_t)l2) ? v2 : committed_version(&s, (uint32_t)l2);
39 CHECK_U(committed_version(&s, (uint32_t)l), want);
40 CHECK_I(s.failed, 0);
41 sim_free(&s);
42 }
43}
44
45/* fleet.rs a_minority_refuses_changes */
46static void minority_refuses(void) {
47 sim_t s;
48 sim_init(&s, 5, 11, 0);
49 sim_step(&s, 5000);
50 int l = sim_leader(&s);
51 CHECK(l >= 0);
52 uint32_t mate = ((uint32_t)l + 1) % 5;
53 for (uint32_t k = 0; k < 5; k++) s.side[k] = (k == (uint32_t)l || k == mate) ? 1 : 0;
54 sim_relink(&s);
55 sim_step(&s, 4000);
56 CHECK(mfc_role_of(s.cores[l]) != MFC_LEADER);
57 uint64_t v;
58 mfc_outs out;
59 char *err = NULL;
60 CHECK(!mfc_propose(s.cores[l], (mfd_doc){0}, 0, &v, &out, &err));
61 CHECK(mt_contains(err, "leader"));
62 free(err);
63 int l2 = sim_leader(&s);
64 CHECK(l2 >= 0 && l2 != l && (uint32_t)l2 != mate);
65 uint64_t vm = sim_propose(&s, (uint32_t)l2, "majority", &err);
66 CHECK(vm > 0);
67 sim_step(&s, 500);
68 for (uint32_t k = 0; k < 5; k++) s.side[k] = 0;
69 sim_relink(&s);
70 sim_step(&s, 4000);
71 for (uint32_t k = 0; k < 5; k++) CHECK(committed_version(&s, k) >= vm);
72 CHECK(sim_leader(&s) >= 0);
73 CHECK_I(s.failed, 0);
74 sim_free(&s);
75}
76
77/* fleet.rs two_two_split_has_no_leader */
78static void two_two_split(void) {
79 sim_t s;
80 sim_init(&s, 4, 3, 0);
81 sim_step(&s, 5000);
82 for (uint32_t k = 0; k < 4; k++) s.side[k] = k / 2;
83 sim_relink(&s);
84 sim_step(&s, 6000);
85 for (uint32_t k = 0; k < 4; k++) CHECK(mfc_role_of(s.cores[k]) != MFC_LEADER);
86 for (uint32_t k = 0; k < 4; k++) s.side[k] = 0;
87 sim_relink(&s);
88 sim_step(&s, 6000);
89 CHECK(sim_leader(&s) >= 0);
90 sim_free(&s);
91}
92
93/* fleet.rs no_two_leaders_in_a_term_randomised (and its #[ignore]d long run: `election N`) */
94static void randomised(uint64_t from, uint64_t to) {
95 uint64_t terms = 0, versions = 0, stops = 0, count = to - from;
96 for (uint64_t seed = from; seed < to; seed++) {
97 uint32_t n = 3 + (uint32_t)(seed % 3);
98 sim_t s;
99 sim_init(&s, n, seed * 7919, seed % 4 * 5);
100 char *err = NULL;
101 for (int round = 0; round < 40; round++) {
102 uint64_t r = sim_rand(&s, 10);
103 if (r == 0 || r == 1) {
104 for (uint32_t k = 0; k < n; k++) s.side[k] = (uint32_t)sim_rand(&s, 2);
105 sim_relink(&s);
106 } else if (r == 2) {
107 for (uint32_t k = 0; k < n; k++) s.side[k] = 0;
108 sim_relink(&s);
109 } else if (r == 9 && sim_rand(&s, 3) == 0) {
110 /* A disk that fills up: the member stops at its next write (fail-stop). */
111 uint32_t k = (uint32_t)sim_rand(&s, n);
112 s.bad_disk[k] = true;
113 } else if (r == 3) {
114 uint32_t k = (uint32_t)sim_rand(&s, n);
115 uint32_t live = 0;
116 for (uint32_t j = 0; j < n; j++) live += s.cores[j] != NULL;
117 if (s.cores[k] && live > 1) sim_crash(&s, k);
118 } else if (r == 4) {
119 uint32_t k = (uint32_t)sim_rand(&s, n);
120 if (!s.cores[k]) sim_restart(&s, k);
121 } else {
122 int l = sim_leader(&s);
123 if (l >= 0) {
124 char tag[16];
125 snprintf(tag, sizeof tag, "r%d", round);
126 if (!sim_propose(&s, (uint32_t)l, tag, &err)) free(err);
127 }
128 }
129 uint64_t ms = 200 + sim_rand(&s, 3000);
130 sim_step(&s, ms);
131 }
132 /* Heal everything: a leader, and every member on one committed document. */
133 for (uint32_t k = 0; k < n; k++) {
134 s.side[k] = 0;
135 s.bad_disk[k] = false;
136 if (!s.cores[k]) sim_restart(&s, k);
137 }
138 sim_relink(&s);
139 s.loss = 0;
140 sim_step(&s, 8000);
141 int l = sim_leader(&s);
142 if (!CHECK(l >= 0)) fprintf(stderr, "seed %llu: no leader after healing\n", (unsigned long long)seed);
143 if (l >= 0) {
144 uint64_t v = sim_propose(&s, (uint32_t)l, "final", &err);
145 CHECK(v > 0);
146 sim_step(&s, 2000);
147 for (uint32_t k = 0; k < n; k++)
148 if (!CHECK_U(committed_version(&s, k), v)) fprintf(stderr, "seed %llu member %u\n", (unsigned long long)seed, k);
149 }
150 if (!CHECK_I(s.failed, 0)) fprintf(stderr, "seed %llu broke an invariant\n", (unsigned long long)seed);
151 terms += s.nleaders;
152 versions += s.ncommitted;
153 stops += s.fail_stops;
154 sim_free(&s);
155 }
156 CHECK(stops > count / 10);
157 CHECK(terms > 3 * count && versions > 5 * count);
158 fprintf(stderr, "randomised: %llu seeds, %llu leaderships, %llu committed versions, %llu fail-stops\n", (unsigned long long)count,
159 (unsigned long long)terms, (unsigned long long)versions, (unsigned long long)stops);
160}
161
162/* fleet.rs a_pair_has_a_fixed_coordinator */
163static void pair_fixed(void) {
164 sim_t s;
165 sim_init(&s, 2, 5, 0);
166 sim_step(&s, 100);
167 CHECK_I(sim_leader(&s), 0);
168 char *err = NULL;
169 uint64_t v = sim_propose(&s, 0, "x", &err);
170 sim_step(&s, 500);
171 CHECK_U(committed_version(&s, 1), v);
172 /* System 1 never leads; system 0 commits alone while 1 is away, and 1 catches up on return. */
173 sim_crash(&s, 1);
174 uint64_t v2 = sim_propose(&s, 0, "y", &err);
175 sim_step(&s, 100);
176 CHECK_U(committed_version(&s, 0), v2);
177 sim_restart(&s, 1);
178 sim_step(&s, 2000);
179 CHECK_U(committed_version(&s, 1), v2);
180 sim_crash(&s, 0);
181 sim_step(&s, 10000);
182 CHECK_I(sim_leader(&s), -1);
183 uint64_t x;
184 mfc_outs out;
185 CHECK(!mfc_propose(s.cores[1], (mfd_doc){0}, s.now, &x, &out, &err));
186 free(err);
187 sim_free(&s);
188}
189
190/* fleet.rs terms_and_votes_survive_restarts */
191static void terms_and_votes_survive(void) {
192 sim_t s;
193 sim_init(&s, 3, 99, 0);
194 sim_step(&s, 5000);
195 int l = sim_leader(&s);
196 CHECK(l >= 0);
197 uint64_t t = mfc_term(s.cores[l]);
198 /* Every member restarts from its disk: the term is never lower, and the vote of the term is kept. */
199 for (uint32_t k = 0; k < 3; k++) {
200 mfp_persist before = mfp_clone(&s.disk[k]);
201 sim_crash(&s, k);
202 sim_restart(&s, k);
203 uint32_t voted = 0;
204 bool hv = mfc_voted(s.cores[k], &voted);
205 CHECK(mfc_term(s.cores[k]) == before.term && hv == before.has_voted && (!hv || voted == before.voted));
206 CHECK(mfc_term(s.cores[k]) >= t || k != (uint32_t)l);
207 mfp_free(&before);
208 }
209 sim_step(&s, 8000);
210 CHECK(sim_leader(&s) >= 0);
211 sim_free(&s);
212}
213
214int main(int argc, char **argv) {
215 elected_and_commits();
216 minority_refuses();
217 two_two_split();
218 pair_fixed();
219 terms_and_votes_survive();
220 /* `election 2000`: the Rust's ignored 2000-seed run. */
221 randomised(1, argc > 1 ? (uint64_t)atoi(argv[1]) + 1 : 300);
222 return mesh_check_done();
223}