Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_core/tests/hlc.rs

9.9 KiB, 1 run

created by r1870400018:74439, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The hybrid logical clock: causal order across skewed nodes, the guard against a peer far ahead,
2//! monotonicity under a wall that steps back, the counter's wall bump, and an encoding whose byte
3//! order is the stamps' order.
4
5use oxedyne_fe2o3_core::{
6 prelude::*,
7 time::hlc::{
8 DELTA_MS_DEFAULT,
9 Hlc,
10 HlcClock,
11 WallClock,
12 },
13};
14
15use std::sync::{
16 Arc,
17 atomic::{
18 AtomicU64,
19 Ordering,
20 },
21};
22
23
24const T0: u64 = 1_760_659_200_000; // 17 Oct 2025, ms
25const MIN: i64 = 60_000;
26const DAY: u64 = 86_400_000;
27
28// A node's view of a shared true time, off by `skew` ms.
29#[derive(Debug)]
30struct Skewed {
31 t: Arc<AtomicU64>,
32 skew: i64,
33}
34
35impl WallClock for Skewed {
36 fn wall_ms(&self) -> Outcome<u64> {
37 Ok((self.t.load(Ordering::SeqCst) as i64 + self.skew) as u64)
38 }
39}
40
41// A wall the test sets directly, free to step back.
42#[derive(Debug, Default)]
43struct Manual(AtomicU64);
44
45impl Manual {
46 fn set(&self, ms: u64) { self.0.store(ms, Ordering::SeqCst) }
47}
48
49impl WallClock for Manual {
50 fn wall_ms(&self) -> Outcome<u64> {
51 Ok(self.0.load(Ordering::SeqCst))
52 }
53}
54
55// Deterministic, so a failure repeats.
56struct Lcg(u64);
57
58impl Lcg {
59 fn next(&mut self, n: u64) -> u64 {
60 self.0 = self.0.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1_442_695_040_888_963_407);
61 (self.0 >> 33) % n
62 }
63}
64
65// Messages pass at random between the nodes while true time advances. Every receipt must stamp
66// above what was sent, every stamp above the node's previous one, and no receipt may fault.
67fn chain(clocks: &mut [HlcClock<Skewed>], t: &Arc<AtomicU64>, steps: usize, seed: u64) -> Outcome<()> {
68 let mut rng = Lcg(seed);
69 let mut last: Vec<Hlc> = clocks.iter().map(|c| c.last()).collect();
70 for i in 0..steps {
71 t.fetch_add(rng.next(40), Ordering::SeqCst);
72 let n = clocks.len() as u64;
73 let a = rng.next(n) as usize;
74 let b = (a + 1 + rng.next(n - 1) as usize) % clocks.len();
75 let sent = res!(clocks[a].now());
76 if sent <= last[a] {
77 return Err(err!("Step {}: node {} stamped {} after {}.", i, a, sent, last[a]; Test, Order));
78 }
79 last[a] = sent;
80 let got = res!(clocks[b].recv(&sent));
81 if let Some(f) = got.fault {
82 return Err(err!("Step {}: node {} faulted on {}: {}.", i, b, sent, f; Test, Unexpected));
83 }
84 if got.stamp <= sent || got.stamp <= last[b] {
85 return Err(err!(
86 "Step {}: node {} received {} and stamped {} (its previous {}).",
87 i, b, sent, got.stamp, last[b];
88 Test, Order));
89 }
90 last[b] = got.stamp;
91 // A local event after the receipt follows it too.
92 let after = res!(clocks[b].now());
93 if after <= got.stamp {
94 return Err(err!("Step {}: node {} stamped {} after receiving into {}.", i, b, after, got.stamp;
95 Test, Order));
96 }
97 last[b] = after;
98 }
99 Ok(())
100}
101
102fn nodes(t: &Arc<AtomicU64>, skews: &[i64]) -> Vec<HlcClock<Skewed>> {
103 skews.iter().enumerate().map(|(i, s)| {
104 HlcClock::new(Skewed { t: t.clone(), skew: *s }, 0xa0 + i as u64)
105 }).collect()
106}
107
108#[test]
109fn skewed_nodes_order_causally_once_offset_corrected() -> Outcome<()> {
110 let t = Arc::new(AtomicU64::new(T0));
111 let skews = [5 * MIN, -5 * MIN, 0, 3 * MIN];
112 let mut clocks = nodes(&t, &skews);
113 // Offsets measured against the reference, each off by up to a few hundred ms.
114 let errs = [250, -300, 0, 120];
115 for (c, (s, e)) in clocks.iter_mut().zip(skews.iter().zip(errs.iter())) {
116 c.set_offset_ms(-*s + *e);
117 }
118 res!(chain(&mut clocks, &t, 5_000, 7));
119 Ok(())
120}
121
122#[test]
123fn nodes_within_delta_order_causally_with_no_offset() -> Outcome<()> {
124 let t = Arc::new(AtomicU64::new(T0));
125 let mut clocks = nodes(&t, &[25_000, -25_000, 0]);
126 res!(chain(&mut clocks, &t, 5_000, 11));
127 Ok(())
128}
129
130#[test]
131fn uncorrected_five_minute_skew_is_a_fault() -> Outcome<()> {
132 let t = Arc::new(AtomicU64::new(T0));
133 let mut clocks = nodes(&t, &[5 * MIN, -5 * MIN]);
134 let sent = res!(clocks[0].now());
135 let got = res!(clocks[1].recv(&sent));
136 match got.fault {
137 Some(f) if f.ahead_ms == 10 * MIN as u64 => Ok(()),
138 other => Err(err!("A peer 10 min ahead answered fault {:?}.", other; Test, Mismatch)),
139 }
140}
141
142#[test]
143fn a_peer_two_days_ahead_is_ignored_and_reported() -> Outcome<()> {
144 let wall = Arc::new(Manual::default());
145 wall.set(T0);
146 let mut c = HlcClock::new(wall.clone(), 1);
147 let before = res!(c.now());
148 let remote = Hlc::new(T0 + 2 * DAY, 9, 2);
149 let got = res!(c.recv(&remote));
150 let f = match got.fault {
151 Some(f) => f,
152 None => return Err(err!("A stamp two days ahead was merged into {}.", got.stamp; Test, Missing)),
153 };
154 if f.remote != remote || f.local_ms != T0 || f.ahead_ms != 2 * DAY || f.delta_ms != DELTA_MS_DEFAULT {
155 return Err(err!("The fault reads {:?}.", f; Test, Mismatch));
156 }
157 // Only the counter stepped.
158 if got.stamp != Hlc::new(T0, before.ctr + 1, 1) {
159 return Err(err!("The receipt stamped {} after {}.", got.stamp, before; Test, Mismatch));
160 }
161 for _ in 0..100 {
162 let s = res!(c.now());
163 if s.wall_ms > T0 + DELTA_MS_DEFAULT {
164 return Err(err!("now() reached {} past local + delta.", s; Test, Excessive));
165 }
166 }
167 // A peer exactly delta ahead is believed.
168 let near = Hlc::new(T0 + DELTA_MS_DEFAULT, 0, 3);
169 let got = res!(c.recv(&near));
170 if got.fault.is_some() || got.stamp <= near {
171 return Err(err!("A peer at the bound gave {:?}.", got; Test, Mismatch));
172 }
173 Ok(())
174}
175
176#[test]
177fn delta_is_configurable() -> Outcome<()> {
178 let wall = Manual::default();
179 wall.set(T0);
180 let mut c = HlcClock::new(&wall, 1).with_delta_ms(1_000);
181 let got = res!(c.recv(&Hlc::new(T0 + 1_001, 0, 2)));
182 if got.fault.is_none() {
183 return Err(err!("1001 ms ahead under a 1000 ms bound was merged."; Test, Missing));
184 }
185 let got = res!(c.recv(&Hlc::new(T0 + 1_000, 0, 2)));
186 if got.fault.is_some() {
187 return Err(err!("1000 ms ahead under a 1000 ms bound faulted."; Test, Unexpected));
188 }
189 Ok(())
190}
191
192#[test]
193fn monotone_under_a_wall_that_steps_back() -> Outcome<()> {
194 let wall = Manual::default();
195 wall.set(T0);
196 let mut c = HlcClock::new(&wall, 1);
197 let mut prev = res!(c.now());
198 let walls = [T0 + 50, T0 - 10_000, T0 - 10_000, T0 + 20, T0 + 51, T0 + 100];
199 for w in walls {
200 wall.set(w);
201 let s = res!(c.now());
202 if s <= prev {
203 return Err(err!("At wall {} the clock stamped {} after {}.", w, s, prev; Test, Order));
204 }
205 prev = s;
206 }
207 // A re-measured offset that moves the corrected wall back a minute changes nothing either.
208 c.set_offset_ms(-MIN);
209 for _ in 0..10 {
210 let s = res!(c.now());
211 if s <= prev || s.wall_ms != T0 + 100 {
212 return Err(err!("After the offset stepped back the clock stamped {} after {}.", s, prev;
213 Test, Order));
214 }
215 prev = s;
216 }
217 Ok(())
218}
219
220#[test]
221fn a_spent_counter_bumps_the_wall() -> Outcome<()> {
222 let wall = Manual::default();
223 wall.set(T0);
224 let mut c = HlcClock::new(&wall, 1).with_last(Hlc::new(T0, u32::MAX - 1, 0));
225 let a = res!(c.now());
226 let b = res!(c.now());
227 if a != Hlc::new(T0, u32::MAX, 1) || b != Hlc::new(T0 + 1, 0, 1) {
228 return Err(err!("The counter's end gave {} then {}.", a, b; Test, Mismatch));
229 }
230 // A merge at the counter's end bumps the same way.
231 let got = res!(c.recv(&Hlc::new(T0 + 1, u32::MAX, 2)));
232 if got.stamp != Hlc::new(T0 + 2, 0, 1) {
233 return Err(err!("A merge at the counter's end gave {}.", got.stamp; Test, Mismatch));
234 }
235 // Only a wall with nowhere to go is an error.
236 let mut c = HlcClock::new(&wall, 1).with_last(Hlc::new(u64::MAX, u32::MAX, 0));
237 match c.now() {
238 Err(_) => Ok(()),
239 Ok(s) => Err(err!("A spent wall and counter stamped {}.", s; Test, Unexpected)),
240 }
241}
242
243#[test]
244fn encoding_order_is_stamp_order() -> Outcome<()> {
245 let mut rng = Lcg(3);
246 let pick = |r: &mut Lcg| -> Hlc {
247 // Few distinct values per field, so ties at each level are common.
248 Hlc::new(T0 + r.next(4), r.next(3) as u32 * 0x0100_0001, r.next(3) * 0x0100_0000_0000_0001)
249 };
250 for _ in 0..5_000 {
251 let a = pick(&mut rng);
252 let b = pick(&mut rng);
253 if a.to_bytes().cmp(&b.to_bytes()) != a.cmp(&b) {
254 return Err(err!("{} and {} order differently as bytes.", a, b; Test, Order));
255 }
256 if res!(Hlc::from_bytes(&a.to_bytes())) != a {
257 return Err(err!("{} does not survive its encoding.", a; Test, Mismatch));
258 }
259 let shown = a.to_string();
260 if res!(shown.parse::<Hlc>()) != a {
261 return Err(err!("{} does not parse back from '{}'.", a, shown; Test, Mismatch));
262 }
263 }
264 if Hlc::from_bytes(&[0u8; 19]).is_ok() || "12.3".parse::<Hlc>().is_ok() || "x.1@0".parse::<Hlc>().is_ok() {
265 return Err(err!("A malformed stamp was accepted."; Test, Unexpected));
266 }
267 if Hlc::new(1, 2, 0xa1).to_string() != "1.2@00000000000000a1" {
268 return Err(err!("The shown form is {}.", Hlc::new(1, 2, 0xa1); Test, Mismatch));
269 }
270 Ok(())
271}
272
273#[cfg(not(target_arch = "wasm32"))]
274#[test]
275fn a_driven_clock_source_drives_the_stamp() -> Outcome<()> {
276 use oxedyne_fe2o3_core::time::{
277 ClockSource,
278 Driven,
279 };
280 let dir = std::env::temp_dir().join(fmt!("fe2o3_hlc_{}", std::process::id()));
281 res!(std::fs::create_dir_all(&dir));
282 let path = dir.join("clock");
283 res!(std::fs::write(&path, (T0 + 777).to_le_bytes()));
284 let mut c = HlcClock::new(ClockSource::Driven(Driven::new(&path)), 1);
285 c.set_offset_ms(23);
286 let s = res!(c.now());
287 let _ = std::fs::remove_dir_all(&dir);
288 if s != Hlc::new(T0 + 800, 0, 1) {
289 return Err(err!("A driven wall of {} with offset 23 stamped {}.", T0 + 777, s; Test, Mismatch));
290 }
291 Ok(())
292}