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 | |
| 5 | use oxedyne_fe2o3_core::{ |
| 6 | prelude::*, |
| 7 | time::hlc::{ |
| 8 | DELTA_MS_DEFAULT, |
| 9 | Hlc, |
| 10 | HlcClock, |
| 11 | WallClock, |
| 12 | }, |
| 13 | }; |
| 14 | |
| 15 | use std::sync::{ |
| 16 | Arc, |
| 17 | atomic::{ |
| 18 | AtomicU64, |
| 19 | Ordering, |
| 20 | }, |
| 21 | }; |
| 22 | |
| 23 | |
| 24 | const T0: u64 = 1_760_659_200_000; // 17 Oct 2025, ms |
| 25 | const MIN: i64 = 60_000; |
| 26 | const DAY: u64 = 86_400_000; |
| 27 | |
| 28 | // A node's view of a shared true time, off by `skew` ms. |
| 29 | #[derive(Debug)] |
| 30 | struct Skewed { |
| 31 | t: Arc<AtomicU64>, |
| 32 | skew: i64, |
| 33 | } |
| 34 | |
| 35 | impl 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)] |
| 43 | struct Manual(AtomicU64); |
| 44 | |
| 45 | impl Manual { |
| 46 | fn set(&self, ms: u64) { self.0.store(ms, Ordering::SeqCst) } |
| 47 | } |
| 48 | |
| 49 | impl 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. |
| 56 | struct Lcg(u64); |
| 57 | |
| 58 | impl 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. |
| 67 | fn 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 | |
| 102 | fn 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] |
| 109 | fn 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] |
| 123 | fn 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] |
| 131 | fn 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] |
| 143 | fn 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] |
| 177 | fn 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] |
| 193 | fn 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] |
| 221 | fn 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] |
| 244 | fn 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] |
| 275 | fn 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 | } |