qualia_core_db/net/peer/replication/
tombstone.rs1use crate::net::qdnf::errors::QdnfError;
8use crate::net::qdnf::types::StrongDigest;
9
10pub const MAX_TOMBSTONES: usize = 16;
11
12#[repr(C)]
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub struct Tombstone {
15 pub op_id: StrongDigest,
16 pub epoch: u64,
17 pub sequence: u32,
18}
19
20#[derive(Clone, Copy)]
21struct Slot {
22 occupied: bool,
23 ts: Tombstone,
24}
25
26#[repr(u8)]
28#[derive(Clone, Copy, Debug, PartialEq, Eq)]
29pub enum ReplicaStatus {
30 Authorized = 1,
31 Stale = 2,
32}
33
34pub struct TombstoneTable {
35 slots: [Slot; MAX_TOMBSTONES],
36 has_frontier: bool,
39 frontier_epoch: u64,
40 frontier_seq: u32,
41 excluded_before: u64,
42}
43
44pub struct ReplicaGate {
45 status: ReplicaStatus,
46}
47
48impl TombstoneTable {
49 pub const fn new() -> Self {
51 Self {
52 slots: [Slot {
53 occupied: false,
54 ts: Tombstone {
55 op_id: StrongDigest::ZERO,
56 epoch: 0,
57 sequence: 0,
58 },
59 }; MAX_TOMBSTONES],
60 has_frontier: false,
61 frontier_epoch: 0,
62 frontier_seq: 0,
63 excluded_before: 0,
64 }
65 }
66
67 pub fn retain(&mut self, ts: Tombstone) -> Result<(), QdnfError> {
69 if ts.op_id == StrongDigest::ZERO {
70 return Err(QdnfError::Malformed);
71 }
72 if self.find_id(&ts.op_id).is_some() {
73 return Ok(());
74 }
75 let idx = self.find_free().ok_or(QdnfError::Capacity)?;
76 self.slots[idx] = Slot { occupied: true, ts };
77 Ok(())
78 }
79
80 pub fn occupied_count(&self) -> usize {
82 let mut n = 0usize;
83 let mut i = 0usize;
84 while i < MAX_TOMBSTONES {
85 if self.slots[i].occupied {
86 n += 1;
87 }
88 i += 1;
89 }
90 n
91 }
92
93 pub fn apply_transport_ack(&mut self, _op_id: StrongDigest) -> Result<(), QdnfError> {
95 Err(QdnfError::Unauthorized)
96 }
97
98 pub fn apply_authorized_frontier(
100 &mut self,
101 epoch: u64,
102 sequence: u32,
103 ) -> Result<usize, QdnfError> {
104 self.has_frontier = true;
105 self.frontier_epoch = epoch;
106 self.frontier_seq = sequence;
107 Ok(self.compact())
108 }
109
110 pub fn apply_epoch_exclusion(&mut self, excluded_before: u64) -> Result<usize, QdnfError> {
112 self.excluded_before = excluded_before;
113 Ok(self.compact())
114 }
115
116 pub fn contains(&self, op_id: &StrongDigest) -> bool {
118 self.find_id(op_id).is_some()
119 }
120
121 fn compact(&mut self) -> usize {
122 let mut released = 0usize;
123 let mut i = 0usize;
124 while i < MAX_TOMBSTONES {
125 if self.slots[i].occupied && self.may_compact(&self.slots[i].ts) {
126 self.slots[i].occupied = false;
127 released += 1;
128 }
129 i += 1;
130 }
131 released
132 }
133
134 fn may_compact(&self, ts: &Tombstone) -> bool {
135 if ts.epoch < self.excluded_before {
136 return true;
137 }
138 self.has_frontier && ts.epoch == self.frontier_epoch && ts.sequence < self.frontier_seq
139 }
140
141 fn find_id(&self, id: &StrongDigest) -> Option<usize> {
142 let mut i = 0usize;
143 while i < MAX_TOMBSTONES {
144 if self.slots[i].occupied && self.slots[i].ts.op_id == *id {
145 return Some(i);
146 }
147 i += 1;
148 }
149 None
150 }
151
152 fn find_free(&self) -> Option<usize> {
153 let mut i = 0usize;
154 while i < MAX_TOMBSTONES {
155 if !self.slots[i].occupied {
156 return Some(i);
157 }
158 i += 1;
159 }
160 None
161 }
162}
163
164impl Default for TombstoneTable {
165 fn default() -> Self {
166 Self::new()
167 }
168}
169
170impl ReplicaGate {
171 pub const fn authorized() -> Self {
173 Self {
174 status: ReplicaStatus::Authorized,
175 }
176 }
177
178 pub const fn stale() -> Self {
180 Self {
181 status: ReplicaStatus::Stale,
182 }
183 }
184
185 pub fn contribute(&self) -> Result<(), QdnfError> {
187 match self.status {
188 ReplicaStatus::Authorized => Ok(()),
189 ReplicaStatus::Stale => Err(QdnfError::Unauthorized),
190 }
191 }
192
193 pub fn mark_stale(&mut self) {
195 self.status = ReplicaStatus::Stale;
196 }
197
198 pub fn reauthorize(&mut self) {
200 self.status = ReplicaStatus::Authorized;
201 }
202}
203
204pub fn tombstone_implies_global_completeness() -> bool {
206 false
207}
208
209pub fn transport_ack_is_compaction_frontier() -> bool {
211 false
212}
213
214#[cfg(test)]
215mod tests {
216 use super::*;
217
218 fn ts(seq: u32) -> Tombstone {
219 let mut id = StrongDigest::ZERO;
220 id.0[0] = seq as u8;
221 id.0[1] = 0x7a;
222 Tombstone {
223 op_id: id,
224 epoch: 1,
225 sequence: seq,
226 }
227 }
228
229 #[test]
230 fn retain_until_authorized_frontier() {
231 let mut table = TombstoneTable::new();
232 table.retain(ts(1)).unwrap();
233 table.retain(ts(2)).unwrap();
234 assert_eq!(table.occupied_count(), 2);
235 assert_eq!(
236 table.apply_transport_ack(ts(1).op_id),
237 Err(QdnfError::Unauthorized)
238 );
239 assert_eq!(table.occupied_count(), 2);
240 let released = table.apply_authorized_frontier(1, 2).unwrap();
241 assert_eq!(released, 1);
242 assert!(table.contains(&ts(2).op_id));
243 assert!(!table.contains(&ts(1).op_id));
244 }
245
246 #[test]
247 fn epoch_exclusion_compacts_older_epoch() {
248 let mut table = TombstoneTable::new();
249 let mut old = ts(1);
250 old.epoch = 3;
251 let mut keep = ts(9);
252 keep.epoch = 5;
253 table.retain(old).unwrap();
254 table.retain(keep).unwrap();
255 let n = table.apply_epoch_exclusion(4).unwrap();
256 assert_eq!(n, 1);
257 assert!(table.contains(&keep.op_id));
258 assert!(!table.contains(&old.op_id));
259 }
260
261 #[test]
262 fn seventeenth_retain_is_capacity() {
263 let mut table = TombstoneTable::new();
264 let mut i = 1u32;
265 while i <= MAX_TOMBSTONES as u32 {
266 table.retain(ts(i)).unwrap();
267 i += 1;
268 }
269 assert_eq!(table.retain(ts(99)), Err(QdnfError::Capacity));
270 }
271
272 #[test]
273 fn stale_replica_cannot_contribute_until_reauthorize() {
274 let mut gate = ReplicaGate::stale();
275 assert_eq!(gate.contribute(), Err(QdnfError::Unauthorized));
276 gate.reauthorize();
277 gate.contribute().unwrap();
278 gate.mark_stale();
279 assert_eq!(gate.contribute(), Err(QdnfError::Unauthorized));
280 }
281
282 #[test]
283 fn completeness_and_transport_ack_are_not_frontiers() {
284 assert!(!tombstone_implies_global_completeness());
285 assert!(!transport_ack_is_compaction_frontier());
286 }
287}