ouisync/protocol/
summary.rs

1use super::{InnerNodes, LeafNodes};
2use serde::{Deserialize, Serialize};
3use sqlx::{
4    encode::IsNull,
5    error::BoxDynError,
6    sqlite::{SqliteArgumentValue, SqliteTypeInfo, SqliteValueRef},
7    Decode, Encode, Sqlite, Type,
8};
9use std::fmt;
10use xxhash_rust::xxh3::Xxh3Default;
11
12/// Summary info of a snapshot subtree. Contains whether the subtree has been completely downloaded
13/// and the number of missing blocks in the subtree.
14#[derive(Copy, Clone, Eq, PartialEq, Debug, Serialize, Deserialize)]
15pub struct Summary {
16    // TODO: The `state` field is not used by the peer after deserialization. Consider using
17    // `#[serde(skip)]` on it.
18    pub state: NodeState,
19    pub block_presence: MultiBlockPresence,
20}
21
22impl Summary {
23    /// Summary indicating the subtree hasn't been completely downloaded yet.
24    pub const INCOMPLETE: Self = Self {
25        state: NodeState::Incomplete,
26        block_presence: MultiBlockPresence::None,
27    };
28
29    pub fn from_leaves(nodes: &LeafNodes) -> Self {
30        let mut block_presence_builder = MultiBlockPresenceBuilder::new();
31
32        for node in nodes {
33            match node.block_presence {
34                SingleBlockPresence::Missing => {
35                    block_presence_builder.update(MultiBlockPresence::None)
36                }
37                SingleBlockPresence::Expired => {
38                    // If a _peer_ asks if we have a block, we tell them we do even if it's been
39                    // expired.  If they ask for the block we flip its status from `Expired` to
40                    // `Missing` and will try to download it again.
41                    //
42                    // On the other hand, if _we_ want to find out which blocks we need to
43                    // download, `Expired` blocks should not make it into the list.
44                    block_presence_builder.update(MultiBlockPresence::Full)
45                }
46                SingleBlockPresence::Present => {
47                    block_presence_builder.update(MultiBlockPresence::Full)
48                }
49            }
50        }
51
52        Self {
53            state: NodeState::Complete,
54            block_presence: block_presence_builder.build(),
55        }
56    }
57
58    pub fn from_inners(nodes: &InnerNodes) -> Self {
59        let mut block_presence_builder = MultiBlockPresenceBuilder::new();
60        let mut state = NodeState::Complete;
61
62        for (_, node) in nodes {
63            // We should never store empty nodes, but in case someone sends us one anyway, ignore
64            // it.
65            if node.is_empty() {
66                continue;
67            }
68
69            block_presence_builder.update(node.summary.block_presence);
70            state.update(node.summary.state);
71        }
72
73        Self {
74            state,
75            block_presence: block_presence_builder.build(),
76        }
77    }
78
79    /// Checks whether the subtree at `self` is outdated compared to the subtree at `other` in terms
80    /// of completeness and block presence. That is, `self` is considered outdated if it's
81    /// incomplete (regardless of what `other` is) or if `other` has some blocks present that
82    /// `self` is missing.
83    ///
84    /// NOTE: This function is NOT antisymetric, that is, `is_outdated(A, B)` does not imply
85    /// !is_outdated(B, A)` (and vice-versa).
86    pub fn is_outdated(&self, other: &Self) -> bool {
87        self.state == NodeState::Incomplete
88            || self.block_presence.is_outdated(&other.block_presence)
89    }
90
91    pub fn with_state(self, state: NodeState) -> Self {
92        Self { state, ..self }
93    }
94}
95
96#[derive(Copy, Clone, Eq, PartialEq, Debug, Serialize, Deserialize, sqlx::Type)]
97#[repr(u8)]
98pub enum NodeState {
99    Incomplete = 0, // Some nodes are missing
100    Complete = 1,   // All nodes are present, but the quota check wasn't performed yet
101    Approved = 2,   // Quota check passed
102    Rejected = 3,   // Quota check failed
103}
104
105impl NodeState {
106    pub fn is_approved(self) -> bool {
107        matches!(self, Self::Approved)
108    }
109
110    pub fn update(&mut self, other: Self) {
111        *self = match (*self, other) {
112            (Self::Incomplete, _) | (_, Self::Incomplete) => Self::Incomplete,
113            (Self::Complete, _) | (_, Self::Complete) => Self::Complete,
114            (Self::Approved, Self::Approved) => Self::Approved,
115            (Self::Rejected, Self::Rejected) => Self::Rejected,
116            (Self::Approved, Self::Rejected) | (Self::Rejected, Self::Approved) => unreachable!(),
117        }
118    }
119}
120
121#[cfg(test)]
122mod test_utils {
123    use super::NodeState;
124    use proptest::{
125        arbitrary::Arbitrary,
126        strategy::{Just, Union},
127    };
128
129    impl Arbitrary for NodeState {
130        type Parameters = ();
131        type Strategy = Union<Just<Self>>;
132
133        fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
134            Union::new([
135                Just(NodeState::Incomplete),
136                Just(NodeState::Complete),
137                Just(NodeState::Approved),
138                Just(NodeState::Rejected),
139            ])
140        }
141    }
142}
143
144/// Information about the presence of a single block.
145#[derive(Copy, Clone, Eq, PartialEq, Serialize, Deserialize, sqlx::Type)]
146#[repr(u8)]
147pub enum SingleBlockPresence {
148    Missing = 0,
149    Present = 1,
150    Expired = 2,
151}
152
153impl SingleBlockPresence {
154    pub fn is_missing(self) -> bool {
155        match self {
156            Self::Missing => true,
157            Self::Present => false,
158            Self::Expired => false,
159        }
160    }
161}
162
163impl fmt::Debug for SingleBlockPresence {
164    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
165        match self {
166            Self::Missing => write!(f, "Missing"),
167            Self::Present => write!(f, "Present"),
168            Self::Expired => write!(f, "Expired"),
169        }
170    }
171}
172
173/// Summary information about the presence of multiple blocks belonging to a subtree.
174#[derive(Copy, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
175pub enum MultiBlockPresence {
176    /// All blocks missing
177    None,
178    /// Some blocks present. The contained checksum is used to determine whether two subtrees have
179    /// the same set of present blocks.
180    Some(Checksum),
181    /// All blocks present.
182    Full,
183}
184
185type Checksum = [u8; 16];
186
187const NONE: Checksum = [
188    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
189];
190const FULL: Checksum = [
191    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
192];
193
194impl MultiBlockPresence {
195    pub fn is_outdated(&self, other: &Self) -> bool {
196        match (self, other) {
197            (Self::Some(lhs), Self::Some(rhs)) => lhs != rhs,
198            (Self::Full, _) | (_, Self::None) => false,
199            (Self::None, _) | (_, Self::Full) => true,
200        }
201    }
202
203    pub fn checksum(&self) -> &[u8] {
204        match self {
205            Self::None => NONE.as_slice(),
206            Self::Some(checksum) => checksum.as_slice(),
207            Self::Full => FULL.as_slice(),
208        }
209    }
210}
211
212impl Type<Sqlite> for MultiBlockPresence {
213    fn type_info() -> SqliteTypeInfo {
214        <&[u8] as Type<Sqlite>>::type_info()
215    }
216}
217
218impl<'q> Encode<'q, Sqlite> for &'q MultiBlockPresence {
219    fn encode_by_ref(
220        &self,
221        args: &mut Vec<SqliteArgumentValue<'q>>,
222    ) -> Result<IsNull, BoxDynError> {
223        Encode::<Sqlite>::encode(self.checksum(), args)
224    }
225}
226
227impl<'r> Decode<'r, Sqlite> for MultiBlockPresence {
228    fn decode(value: SqliteValueRef<'r>) -> Result<Self, BoxDynError> {
229        let slice = <&[u8] as Decode<Sqlite>>::decode(value)?;
230        let array = slice.try_into()?;
231
232        match array {
233            NONE => Ok(Self::None),
234            FULL => Ok(Self::Full),
235            _ => Ok(Self::Some(array)),
236        }
237    }
238}
239
240impl fmt::Debug for MultiBlockPresence {
241    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
242        match self {
243            Self::None => write!(f, "None"),
244            Self::Some(checksum) => write!(f, "Some({:<8})", hex_fmt::HexFmt(checksum)),
245            Self::Full => write!(f, "Full"),
246        }
247    }
248}
249
250struct MultiBlockPresenceBuilder {
251    state: BuilderState,
252    hasher: Xxh3Default,
253}
254
255#[derive(Copy, Clone, Debug)]
256enum BuilderState {
257    Init,
258    None,
259    Some,
260    Full,
261}
262
263impl MultiBlockPresenceBuilder {
264    fn new() -> Self {
265        Self {
266            state: BuilderState::Init,
267            hasher: Xxh3Default::default(),
268        }
269    }
270
271    fn update(&mut self, p: MultiBlockPresence) {
272        self.hasher.update(p.checksum());
273
274        self.state = match (self.state, p) {
275            (BuilderState::Init, MultiBlockPresence::None) => BuilderState::None,
276            (BuilderState::Init, MultiBlockPresence::Some(_)) => BuilderState::Some,
277            (BuilderState::Init, MultiBlockPresence::Full) => BuilderState::Full,
278            (BuilderState::None, MultiBlockPresence::None) => BuilderState::None,
279            (BuilderState::None, MultiBlockPresence::Some(_))
280            | (BuilderState::None, MultiBlockPresence::Full)
281            | (BuilderState::Some, _)
282            | (BuilderState::Full, MultiBlockPresence::None)
283            | (BuilderState::Full, MultiBlockPresence::Some(_)) => BuilderState::Some,
284            (BuilderState::Full, MultiBlockPresence::Full) => BuilderState::Full,
285        }
286    }
287
288    fn build(self) -> MultiBlockPresence {
289        match self.state {
290            BuilderState::Init | BuilderState::None => MultiBlockPresence::None,
291            BuilderState::Some => {
292                MultiBlockPresence::Some(clamp(self.hasher.digest128()).to_le_bytes())
293            }
294            BuilderState::Full => MultiBlockPresence::Full,
295        }
296    }
297}
298
299// Make sure the checksum is never 0 or u128::MAX as those are special values that indicate None or
300// Full respectively.
301const fn clamp(s: u128) -> u128 {
302    if s == 0 {
303        1
304    } else if s == u128::MAX {
305        u128::MAX - 1
306    } else {
307        s
308    }
309}
ouisync/protocol/summary.rs

ouisync/protocol/
summary.rs
