qualia_core_db/net/peer/cells/
spsc.rs1use crate::net::qdnf::errors::QdnfError;
8use crate::net::qdnf::types::Generation;
9
10pub const SPSC_CAP: usize = 32;
12
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
16pub struct OwnershipReceipt {
17 pub generation: Generation,
18 pub bytes: u32,
19 pub slot: u8,
20}
21
22struct RingSlot {
23 receipt: OwnershipReceipt,
24 filled: bool,
25}
26
27pub struct SpscQueue {
29 slots: [RingSlot; SPSC_CAP],
30 head: usize,
31 tail: usize,
32 len: usize,
33 transferred_gen: [u64; 256],
35}
36
37impl SpscQueue {
38 pub const fn new() -> Self {
40 const EMPTY: RingSlot = RingSlot {
41 receipt: OwnershipReceipt {
42 generation: Generation::ZERO,
43 bytes: 0,
44 slot: 0,
45 },
46 filled: false,
47 };
48 Self {
49 slots: [EMPTY; SPSC_CAP],
50 head: 0,
51 tail: 0,
52 len: 0,
53 transferred_gen: [0; 256],
54 }
55 }
56
57 #[inline]
58 fn is_transferred(&self, receipt: OwnershipReceipt) -> bool {
59 let g = receipt.generation.0;
60 g != 0 && g <= self.transferred_gen[receipt.slot as usize]
61 }
62
63 fn mark_transferred(&mut self, receipt: OwnershipReceipt) {
64 self.transferred_gen[receipt.slot as usize] = receipt.generation.0;
65 }
66
67 pub fn push(&mut self, receipt: OwnershipReceipt) -> Result<(), QdnfError> {
70 if receipt.generation == Generation::ZERO {
71 return Err(QdnfError::Malformed);
72 }
73 if self.is_transferred(receipt) {
74 return Err(QdnfError::Unauthorized);
75 }
76 if self.len == SPSC_CAP {
77 return Err(QdnfError::Capacity);
78 }
79 let i = self.tail;
80 self.slots[i] = RingSlot {
81 receipt,
82 filled: true,
83 };
84 self.tail = (self.tail + 1) % SPSC_CAP;
85 self.len += 1;
86 Ok(())
87 }
88
89 pub fn pop(&mut self) -> Result<OwnershipReceipt, QdnfError> {
91 if self.len == 0 {
92 return Err(QdnfError::WouldBlock);
93 }
94 let i = self.head;
95 if !self.slots[i].filled {
96 return Err(QdnfError::Incomplete);
97 }
98 let receipt = self.slots[i].receipt;
99 if self.is_transferred(receipt) {
100 return Err(QdnfError::Unauthorized);
101 }
102 self.slots[i].filled = false;
103 self.head = (self.head + 1) % SPSC_CAP;
104 self.len -= 1;
105 self.mark_transferred(receipt);
106 Ok(receipt)
107 }
108
109 pub fn take(&mut self, receipt: OwnershipReceipt) -> Result<OwnershipReceipt, QdnfError> {
111 if self.is_transferred(receipt) {
112 return Err(QdnfError::Unauthorized);
113 }
114 let got = self.pop()?;
115 if got != receipt {
116 return Err(QdnfError::Conflict);
117 }
118 Ok(got)
119 }
120}
121
122impl Default for SpscQueue {
123 fn default() -> Self {
124 Self::new()
125 }
126}
127
128#[cfg(test)]
129mod tests {
130 use super::*;
131 use crate::net::qdnf::errors::QdnfError;
132
133 fn rec(slot: u8, gen: u64) -> OwnershipReceipt {
134 OwnershipReceipt {
135 generation: Generation(gen),
136 bytes: 8,
137 slot,
138 }
139 }
140
141 #[test]
142 fn thirty_two_ok_thirty_third_capacity() {
143 let mut q = SpscQueue::new();
144 let mut i = 0u8;
145 while i < SPSC_CAP as u8 {
146 q.push(rec(i, 1)).expect("32 live receipts");
147 i = i.saturating_add(1);
148 }
149 assert_eq!(q.push(rec(200, 1)), Err(QdnfError::Capacity));
150 let mut n = 0usize;
151 while n < SPSC_CAP {
152 q.pop().expect("drain");
153 n += 1;
154 }
155 assert_eq!(q.pop(), Err(QdnfError::WouldBlock));
156 }
157
158 #[test]
159 fn pop_empty_would_block() {
160 let mut q = SpscQueue::new();
161 assert_eq!(q.pop(), Err(QdnfError::WouldBlock));
162 }
163
164 #[test]
165 fn pop_transfers_ownership_double_take_unauthorized() {
166 let mut q = SpscQueue::new();
167 let r = rec(3, 7);
168 q.push(r).unwrap();
169 assert_eq!(q.pop().unwrap(), r);
170 assert_eq!(q.take(r), Err(QdnfError::Unauthorized));
171 assert_eq!(q.push(r), Err(QdnfError::Unauthorized));
172 assert_eq!(q.pop(), Err(QdnfError::WouldBlock));
173 }
174
175 #[test]
176 fn new_generation_on_same_slot_is_ok() {
177 let mut q = SpscQueue::new();
178 let a = rec(1, 1);
179 let b = rec(1, 2);
180 q.push(a).unwrap();
181 assert_eq!(q.pop().unwrap(), a);
182 q.push(b).unwrap();
183 assert_eq!(q.pop().unwrap(), b);
184 assert_eq!(q.take(a), Err(QdnfError::Unauthorized));
185 assert_eq!(q.take(b), Err(QdnfError::Unauthorized));
186 }
187}