Skip to main content

qualia_core_db/net/peer/replication/
crash.rs

1//! Crash injection at identity / effect / durable-receipt boundaries (SVC-01.15).
2//!
3//! The crash model is a [`Copy`] in-memory [`CrashLog`] of stages, not an OS
4//! process kill and not CORE-03 WAL torn-write. [`disk_backend_crash_injected`]
5//! is therefore false; this library does not claim CORE-03 disk durability.
6//!
7//! Advertised durability is only the [`ReceiptClass`] actually achieved by
8//! [`receipts::acknowledge`]. [`DeliveryStage::TransportAck`] is never
9//! [`ReceiptClass::DurableReceipt`]. Packages remain open.
10
11use 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/// Rolled-back stage: later stages never happened after [`CrashHarness::restore`].
18#[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/// Copy snapshot of bound identities, local-effect bits, and durable receipts.
44#[derive(Clone, Copy)]
45pub struct CrashLog {
46    slots: [Slot; MAX_RECEIPTS],
47}
48
49impl CrashLog {
50    /// Creates a default `CrashLog`.
51    pub const fn new() -> Self {
52        Self {
53            slots: [EMPTY_SLOT; MAX_RECEIPTS],
54        }
55    }
56
57    /// Takes a state snapshot.
58    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    /// Live entries in the crash log.
85    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
98/// Live [`ReceiptTable`] plus a parallel Copy log used to restore after a crash.
99pub struct CrashHarness {
100    receipts: ReceiptTable,
101    tombstones: TombstoneTable,
102    live: CrashLog,
103    saved: CrashLog,
104    pending: Option<CrashBoundary>,
105}
106
107impl CrashHarness {
108    /// Creates a default `CrashHarness`.
109    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    /// Snapshot after the next successful transition past `boundary`.
120    pub fn inject_crash_after(&mut self, boundary: CrashBoundary) {
121        self.pending = Some(boundary);
122    }
123
124    /// Restores the harness state from the crash log (crash-recovery path).
125    pub fn restore(&mut self) {
126        self.live = self.saved.snapshot();
127        self.pending = None;
128        self.rebuild_tables();
129    }
130
131    /// Occupied log slots.
132    pub fn occupied_count(&self) -> usize {
133        self.live.occupied_count()
134    }
135
136    /// `true` when identity `id` is bound in the log.
137    pub fn identity_present(&self, id: StrongDigest) -> bool {
138        self.live.find_id(&id).is_some()
139    }
140
141    /// `true` when effect `id` is recorded.
142    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    /// `true` when `id` is marked durable.
153    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    /// Number of recorded applications of `id` (u8 saturating).
161    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    /// Binds `id` as an identity in the crash log; `QdnfError` on failure.
169    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    /// Records application of effect `id`.
193    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    /// Acknowledges `id` — marks it durably received.
212    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    /// The durability level advertised for `id`.
236    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    /// Tombstones `id` in the crash log.
245    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
325/// Advertised class is the class [`receipts::acknowledge`] actually returns.
326pub 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
334/// Not CORE-03.13 WAL torn-write. Disk durability is not claimed here.
335pub fn disk_backend_crash_injected() -> bool {
336    false
337}
338
339/// Local effect apply_count saturates at 1 across crash-restore retries.
340pub 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}