qualia_core_db/net/peer/replication/
crash.rs1use crate::net::peer::replication::receipts::{self, ReceiptClass, ReceiptTable, MAX_RECEIPTS};
12use crate::net::peer::replication::tombstone::{Tombstone, TombstoneTable};
13use crate::net::qdnf::errors::QdnfError;
14use crate::net::qdnf::session::datagrams::DeliveryStage;
15use crate::net::qdnf::types::StrongDigest;
16
17#[repr(u8)]
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub enum CrashBoundary {
21 Identity = 1,
22 Effect = 2,
23 DurableReceipt = 3,
24}
25
26#[derive(Clone, Copy)]
27struct Slot {
28 occupied: bool,
29 deleted: bool,
30 apply_count: u8,
31 boundary: CrashBoundary,
32 id: StrongDigest,
33}
34
35const EMPTY_SLOT: Slot = Slot {
36 occupied: false,
37 deleted: false,
38 apply_count: 0,
39 boundary: CrashBoundary::Identity,
40 id: StrongDigest::ZERO,
41};
42
43#[derive(Clone, Copy)]
45pub struct CrashLog {
46 slots: [Slot; MAX_RECEIPTS],
47}
48
49impl CrashLog {
50 pub const fn new() -> Self {
52 Self {
53 slots: [EMPTY_SLOT; MAX_RECEIPTS],
54 }
55 }
56
57 pub const fn snapshot(&self) -> Self {
59 *self
60 }
61
62 fn find_id(&self, id: &StrongDigest) -> Option<usize> {
63 let mut i = 0usize;
64 while i < MAX_RECEIPTS {
65 if self.slots[i].occupied && self.slots[i].id == *id {
66 return Some(i);
67 }
68 i += 1;
69 }
70 None
71 }
72
73 fn find_free(&self) -> Option<usize> {
74 let mut i = 0usize;
75 while i < MAX_RECEIPTS {
76 if !self.slots[i].occupied {
77 return Some(i);
78 }
79 i += 1;
80 }
81 None
82 }
83
84 pub fn occupied_count(&self) -> usize {
86 let mut n = 0usize;
87 let mut i = 0usize;
88 while i < MAX_RECEIPTS {
89 if self.slots[i].occupied {
90 n += 1;
91 }
92 i += 1;
93 }
94 n
95 }
96}
97
98pub struct CrashHarness {
100 receipts: ReceiptTable,
101 tombstones: TombstoneTable,
102 live: CrashLog,
103 saved: CrashLog,
104 pending: Option<CrashBoundary>,
105}
106
107impl CrashHarness {
108 pub const fn new() -> Self {
110 Self {
111 receipts: ReceiptTable::new(),
112 tombstones: TombstoneTable::new(),
113 live: CrashLog::new(),
114 saved: CrashLog::new(),
115 pending: None,
116 }
117 }
118
119 pub fn inject_crash_after(&mut self, boundary: CrashBoundary) {
121 self.pending = Some(boundary);
122 }
123
124 pub fn restore(&mut self) {
126 self.live = self.saved.snapshot();
127 self.pending = None;
128 self.rebuild_tables();
129 }
130
131 pub fn occupied_count(&self) -> usize {
133 self.live.occupied_count()
134 }
135
136 pub fn identity_present(&self, id: StrongDigest) -> bool {
138 self.live.find_id(&id).is_some()
139 }
140
141 pub fn effect_present(&self, id: StrongDigest) -> bool {
143 match self.live.find_id(&id) {
144 Some(i) => {
145 let b = self.live.slots[i].boundary;
146 b == CrashBoundary::Effect || b == CrashBoundary::DurableReceipt
147 }
148 None => false,
149 }
150 }
151
152 pub fn durable_present(&self, id: StrongDigest) -> bool {
154 match self.live.find_id(&id) {
155 Some(i) => self.live.slots[i].boundary == CrashBoundary::DurableReceipt,
156 None => false,
157 }
158 }
159
160 pub fn apply_count(&self, id: StrongDigest) -> u8 {
162 match self.live.find_id(&id) {
163 Some(i) => self.live.slots[i].apply_count,
164 None => 0,
165 }
166 }
167
168 pub fn bind_identity(&mut self, id: StrongDigest) -> Result<(), QdnfError> {
170 reject_zero(id)?;
171 if self.live.find_id(&id).is_some() {
172 receipts::bind_identity(&mut self.receipts, id)?;
173 self.commit_crash(CrashBoundary::Identity);
174 return Ok(());
175 }
176 if self.live.find_free().is_none() {
177 return Err(QdnfError::Capacity);
178 }
179 receipts::bind_identity(&mut self.receipts, id)?;
180 let idx = self.live.find_free().ok_or(QdnfError::Capacity)?;
181 self.live.slots[idx] = Slot {
182 occupied: true,
183 deleted: false,
184 apply_count: 0,
185 boundary: CrashBoundary::Identity,
186 id,
187 };
188 self.commit_crash(CrashBoundary::Identity);
189 Ok(())
190 }
191
192 pub fn apply_effect(&mut self, id: StrongDigest) -> Result<(), QdnfError> {
194 reject_zero(id)?;
195 if self.is_deleted(id) {
196 return Err(QdnfError::Revoked);
197 }
198 let idx = self.live.find_id(&id).ok_or(QdnfError::Unauthorized)?;
199 receipts::apply_effect(&mut self.receipts, id)?;
200 let slot = &mut self.live.slots[idx];
201 if slot.apply_count < 1 {
202 slot.apply_count = 1;
203 }
204 if slot.boundary != CrashBoundary::DurableReceipt {
205 slot.boundary = CrashBoundary::Effect;
206 }
207 self.commit_crash(CrashBoundary::Effect);
208 Ok(())
209 }
210
211 pub fn acknowledge(
213 &mut self,
214 id: StrongDigest,
215 stage: DeliveryStage,
216 ) -> Result<ReceiptClass, QdnfError> {
217 reject_zero(id)?;
218 if self.is_deleted(id)
219 && matches!(
220 stage,
221 DeliveryStage::DurableApplied | DeliveryStage::EconomicReceipt
222 )
223 {
224 return Err(QdnfError::Revoked);
225 }
226 let idx = self.live.find_id(&id).ok_or(QdnfError::Unauthorized)?;
227 let class = receipts::acknowledge(&mut self.receipts, id, stage)?;
228 if stage == DeliveryStage::DurableApplied && class == ReceiptClass::DurableReceipt {
229 self.live.slots[idx].boundary = CrashBoundary::DurableReceipt;
230 self.commit_crash(CrashBoundary::DurableReceipt);
231 }
232 Ok(class)
233 }
234
235 pub fn advertised_durability(
237 &mut self,
238 id: StrongDigest,
239 stage: DeliveryStage,
240 ) -> Result<ReceiptClass, QdnfError> {
241 self.acknowledge(id, stage)
242 }
243
244 pub fn tombstone(&mut self, id: StrongDigest) -> Result<(), QdnfError> {
246 reject_zero(id)?;
247 self.tombstones.retain(Tombstone {
248 op_id: id,
249 epoch: 1,
250 sequence: 1,
251 })?;
252 if let Some(idx) = self.live.find_id(&id) {
253 self.live.slots[idx].deleted = true;
254 } else {
255 let idx = self.live.find_free().ok_or(QdnfError::Capacity)?;
256 self.live.slots[idx] = Slot {
257 occupied: true,
258 deleted: true,
259 apply_count: 0,
260 boundary: CrashBoundary::Identity,
261 id,
262 };
263 }
264 Ok(())
265 }
266
267 fn is_deleted(&self, id: StrongDigest) -> bool {
268 if self.tombstones.contains(&id) {
269 return true;
270 }
271 match self.live.find_id(&id) {
272 Some(i) => self.live.slots[i].deleted,
273 None => false,
274 }
275 }
276
277 fn commit_crash(&mut self, reached: CrashBoundary) {
278 if self.pending == Some(reached) {
279 self.saved = self.live.snapshot();
280 self.pending = None;
281 }
282 }
283
284 fn rebuild_tables(&mut self) {
285 self.receipts = ReceiptTable::new();
286 self.tombstones = TombstoneTable::new();
287 let mut i = 0usize;
288 while i < MAX_RECEIPTS {
289 let slot = self.live.slots[i];
290 if slot.occupied {
291 let _ = receipts::bind_identity(&mut self.receipts, slot.id);
292 if slot.boundary == CrashBoundary::Effect
293 || slot.boundary == CrashBoundary::DurableReceipt
294 {
295 let _ = receipts::apply_effect(&mut self.receipts, slot.id);
296 }
297 if slot.boundary == CrashBoundary::DurableReceipt {
298 let _ = receipts::acknowledge(
299 &mut self.receipts,
300 slot.id,
301 DeliveryStage::DurableApplied,
302 );
303 }
304 if slot.deleted {
305 let _ = self.tombstones.retain(Tombstone {
306 op_id: slot.id,
307 epoch: 1,
308 sequence: 1,
309 });
310 }
311 }
312 i += 1;
313 }
314 }
315}
316
317fn reject_zero(id: StrongDigest) -> Result<(), QdnfError> {
318 if id == StrongDigest::ZERO {
319 Err(QdnfError::Malformed)
320 } else {
321 Ok(())
322 }
323}
324
325pub fn advertised_durability(
327 table: &mut ReceiptTable,
328 id: StrongDigest,
329 stage: DeliveryStage,
330) -> Result<ReceiptClass, QdnfError> {
331 receipts::acknowledge(table, id, stage)
332}
333
334pub fn disk_backend_crash_injected() -> bool {
336 false
337}
338
339pub fn at_most_once_local_effect() -> bool {
341 true
342}
343
344#[cfg(test)]
345mod tests {
346 use super::*;
347 use crate::net::peer::replication::checkpoint::{build_checkpoint, verify_checkpoint};
348 use crate::net::peer::replication::operation::{operation_id, OperationDesc, MAX_PARENTS};
349
350 fn digest(tag: u8) -> StrongDigest {
351 StrongDigest([tag; 48])
352 }
353
354 fn desc_with_payload(payload: u8) -> OperationDesc {
355 OperationDesc {
356 author: StrongDigest([0x11; 48]),
357 epoch: 1,
358 sequence: 1,
359 scope: 7,
360 contract: StrongDigest([0x22; 48]),
361 purpose: StrongDigest([0x33; 48]),
362 payload_digest: StrongDigest([payload; 48]),
363 parents: [StrongDigest::ZERO; MAX_PARENTS],
364 parent_count: 0,
365 }
366 }
367
368 #[test]
369 fn crash_after_identity_before_effect_restore_allows_one_apply() {
370 let mut h = CrashHarness::new();
371 let id = digest(1);
372 h.inject_crash_after(CrashBoundary::Identity);
373 h.bind_identity(id).unwrap();
374 h.apply_effect(id).unwrap();
375 h.restore();
376 assert!(h.identity_present(id));
377 assert!(!h.effect_present(id));
378 assert_eq!(h.apply_count(id), 0);
379 h.apply_effect(id).unwrap();
380 assert_eq!(h.apply_count(id), 1);
381 assert!(at_most_once_local_effect());
382 }
383
384 #[test]
385 fn crash_after_effect_before_durable_restore_allows_durable_applied() {
386 let mut h = CrashHarness::new();
387 let id = digest(2);
388 h.inject_crash_after(CrashBoundary::Effect);
389 h.bind_identity(id).unwrap();
390 h.apply_effect(id).unwrap();
391 h.acknowledge(id, DeliveryStage::DurableApplied).unwrap();
392 h.restore();
393 assert!(h.effect_present(id));
394 assert!(!h.durable_present(id));
395 let durable = h.acknowledge(id, DeliveryStage::DurableApplied).unwrap();
396 assert_eq!(durable, ReceiptClass::DurableReceipt);
397 let ack = h
398 .advertised_durability(id, DeliveryStage::TransportAck)
399 .unwrap();
400 assert_eq!(ack, ReceiptClass::Effect);
401 assert_ne!(ack, ReceiptClass::DurableReceipt);
402 }
403
404 #[test]
405 fn crash_after_durable_applied_retry_is_idempotent() {
406 let mut h = CrashHarness::new();
407 let id = digest(3);
408 h.inject_crash_after(CrashBoundary::DurableReceipt);
409 h.bind_identity(id).unwrap();
410 h.apply_effect(id).unwrap();
411 h.acknowledge(id, DeliveryStage::DurableApplied).unwrap();
412 h.restore();
413 assert!(h.durable_present(id));
414 assert_eq!(h.apply_count(id), 1);
415 let again = h.acknowledge(id, DeliveryStage::DurableApplied).unwrap();
416 assert_eq!(again, ReceiptClass::DurableReceipt);
417 h.apply_effect(id).unwrap();
418 assert_eq!(h.apply_count(id), 1);
419 assert!(at_most_once_local_effect());
420 }
421
422 #[test]
423 fn concurrent_identical_identity_is_one_slot_seventeenth_is_capacity() {
424 let mut h = CrashHarness::new();
425 let id = digest(1);
426 h.bind_identity(id).unwrap();
427 h.bind_identity(id).unwrap();
428 assert_eq!(h.occupied_count(), 1);
429 let mut n = 2u8;
430 while n <= MAX_RECEIPTS as u8 {
431 h.bind_identity(digest(n)).unwrap();
432 n += 1;
433 }
434 assert_eq!(h.occupied_count(), MAX_RECEIPTS);
435 assert_eq!(h.bind_identity(digest(0x20)), Err(QdnfError::Capacity));
436 }
437
438 #[test]
439 fn dishonest_checkpoint_is_malformed() {
440 let id_a = operation_id(&desc_with_payload(1));
441 let id_b = operation_id(&desc_with_payload(2));
442 let committed = [id_a];
443 let cp = build_checkpoint(7, &committed).unwrap();
444 assert_eq!(
445 verify_checkpoint(&cp, &[id_a, id_b]),
446 Err(QdnfError::Malformed)
447 );
448 let mut wrong = cp;
449 wrong.digest = StrongDigest([0xab; 48]);
450 assert_eq!(
451 verify_checkpoint(&wrong, &committed),
452 Err(QdnfError::Malformed)
453 );
454 }
455
456 #[test]
457 fn conflicting_payload_ids_bind_forged_duplicate_checkpoint_is_conflict() {
458 let mut h = CrashHarness::new();
459 let id_a = operation_id(&desc_with_payload(1));
460 let id_b = operation_id(&desc_with_payload(2));
461 assert_ne!(id_a, id_b);
462 h.bind_identity(id_a).unwrap();
463 h.bind_identity(id_b).unwrap();
464 assert_eq!(h.occupied_count(), 2);
465 assert_eq!(build_checkpoint(7, &[id_a, id_a]), Err(QdnfError::Conflict));
466 build_checkpoint(7, &[id_a, id_b]).unwrap();
467 }
468
469 #[test]
470 fn tombstoned_id_rejects_effect() {
471 let mut h = CrashHarness::new();
472 let id = digest(9);
473 h.bind_identity(id).unwrap();
474 h.tombstone(id).unwrap();
475 assert_eq!(h.apply_effect(id), Err(QdnfError::Revoked));
476 assert!(!h.effect_present(id));
477 assert_eq!(
478 h.acknowledge(id, DeliveryStage::DurableApplied),
479 Err(QdnfError::Revoked)
480 );
481 assert_eq!(h.apply_count(id), 0);
482 }
483
484 #[test]
485 fn zero_digest_is_malformed() {
486 let mut h = CrashHarness::new();
487 assert_eq!(
488 h.bind_identity(StrongDigest::ZERO),
489 Err(QdnfError::Malformed)
490 );
491 assert_eq!(
492 h.apply_effect(StrongDigest::ZERO),
493 Err(QdnfError::Malformed)
494 );
495 assert_eq!(
496 h.acknowledge(StrongDigest::ZERO, DeliveryStage::TransportAck),
497 Err(QdnfError::Malformed)
498 );
499 let mut table = ReceiptTable::new();
500 assert_eq!(
501 advertised_durability(&mut table, StrongDigest::ZERO, DeliveryStage::TransportAck),
502 Err(QdnfError::Malformed)
503 );
504 }
505
506 #[test]
507 fn disk_backend_crash_injected_is_false() {
508 assert!(!disk_backend_crash_injected());
509 }
510}