tox_core/net_crypto/
packets_array.rs

1/*! The implementation of packets buffer
2*/
3
4use std::iter;
5
6use crate::net_crypto::errors::*;
7
8/// Maximum size of receiving and sending packet buffers.
9///
10/// Must be a power of 2. The reason of this requirement is that `buffer_start`
11/// and `buffer_end` indexes are unsigned 32 integers and might be overflowed.
12/// When overflow happens the buffer should be used from the beginning but it's
13/// possible only if `u32::MAX` is divided by buffer size, i.e. buffer size is a
14/// power of 2.
15pub const CRYPTO_PACKET_BUFFER_SIZE: u32 = 32768;
16
17/// Calculate real index in the buffer by the packet index
18fn real_index(index: u32) -> usize {
19    (index % CRYPTO_PACKET_BUFFER_SIZE) as usize
20}
21
22/// Deque-like struct for packets queue that allows random writings by the
23/// packet index
24#[derive(Clone, Debug, Eq, PartialEq)]
25pub struct PacketsArray<T> {
26    /// Packets buffer of `CRYPTO_PACKET_BUFFER_SIZE` length
27    pub buffer: Vec<Option<Box<T>>>,
28    /// Start packet index.
29    ///
30    /// Can be any `u32` value regardless of the buffer size. Real index is
31    /// calculated via `real_index` function.
32    pub buffer_start: u32,
33    /// End packet index.
34    ///
35    /// Can be any `u32` value regardless of the buffer size. Real index is
36    /// calculated via `real_index` function.
37    pub buffer_end: u32,
38}
39
40impl<T: Clone> Default for PacketsArray<T> {
41    fn default() -> Self {
42        PacketsArray::new()
43    }
44}
45
46impl<T: Clone> PacketsArray<T> {
47    /// Create new `PacketsArray`
48    pub fn new() -> PacketsArray<T> {
49        PacketsArray {
50            buffer: iter::repeat(None).take(CRYPTO_PACKET_BUFFER_SIZE as usize).collect(),
51            buffer_start: 0,
52            buffer_end: 0,
53        }
54    }
55}
56
57impl<T> PacketsArray<T> {
58    /// Get difference between end and start indices of stored packets in this
59    /// array.
60    ///
61    /// This value is equal to known gap between sent by one side and received
62    /// by other side packets. Also note that this value is not necessary equal
63    /// to count of packets that are stored in this array because packets are
64    /// not necessary stored sequentially.
65    pub fn len(&self) -> u32 {
66        self.buffer_end.overflowing_sub(self.buffer_start).0
67    }
68
69    /// Insert packet to the array by its index
70    ///
71    /// Returns an error when index is too far and buffer can't hold it or when
72    /// packet with this index already exists
73    pub fn insert(&mut self, index: u32, packet: T) -> Result<(), PacketsArrayError> {
74        if index.overflowing_sub(self.buffer_start).0 >= CRYPTO_PACKET_BUFFER_SIZE {
75            return Err(PacketsArrayError::too_big(index))
76        }
77
78        let i = real_index(index);
79
80        if self.buffer[i].is_some() {
81            return Err(PacketsArrayError::already_exist(index))
82        }
83
84        self.buffer[i] = Some(Box::new(packet));
85        if index.overflowing_sub(self.buffer_start).0 >= self.len() {
86            self.buffer_end = index.overflowing_add(1).0;
87        }
88
89        Ok(())
90    }
91
92    /// Write packet at the end index and increment this index
93    ///
94    /// Returns an error when the buffer is full
95    pub fn push_back(&mut self, packet: T) -> Result<(), PacketsArrayError> {
96        if self.len() == CRYPTO_PACKET_BUFFER_SIZE {
97            return Err(PacketsArrayError::from(PacketsArrayErrorKind::ArrayFull))
98        }
99
100        self.buffer[real_index(self.buffer_end)] = Some(Box::new(packet));
101        self.buffer_end = self.buffer_end.overflowing_add(1).0;
102
103        Ok(())
104    }
105
106    /// Get packet at the start index and increment index if the packet exists
107    pub fn pop_front(&mut self) -> Option<T> {
108        if self.buffer_start == self.buffer_end {
109            return None
110        }
111
112        let i = real_index(self.buffer_start);
113        let result = self.buffer[i].take();
114        if result.is_some() {
115            self.buffer_start = self.buffer_start.overflowing_add(1).0;
116        };
117        result.map(|packet| *packet)
118    }
119
120    /// Check if packet the index exists
121    pub fn contains(&self, index: u32) -> bool {
122        let len = self.len();
123
124        if self.buffer_end.overflowing_sub(index).0 > len || index.overflowing_sub(self.buffer_start).0 >= len {
125            return false
126        }
127
128        self.buffer[real_index(index)].is_some()
129    }
130
131    /// Get reference to the packet by its index
132    pub fn get(&self, index: u32) -> Option<&T> {
133        let len = self.len();
134
135        if self.buffer_end.overflowing_sub(index).0 > len || index.overflowing_sub(self.buffer_start).0 >= len {
136            return None
137        }
138
139        self.buffer[real_index(index)].as_deref()
140    }
141
142    /// Get mutable reference to the packet by its index
143    pub fn get_mut(&mut self, index: u32) -> Option<&mut T> {
144        let len = self.len();
145
146        if self.buffer_end.overflowing_sub(index).0 > len || index.overflowing_sub(self.buffer_start).0 >= len {
147            return None
148        }
149
150        self.buffer[real_index(index)].as_deref_mut()
151    }
152
153    /// Remove packet by its index and return it if it was previously in the
154    /// array
155    pub fn remove(&mut self, index: u32) -> Option<T> {
156        let len = self.len();
157
158        if self.buffer_end.overflowing_sub(index).0 > len || index.overflowing_sub(self.buffer_start).0 >= len {
159            return None
160        }
161
162        self.buffer[real_index(index)].take().map(|packet| *packet)
163    }
164
165    /// Set end index when it gets known
166    ///
167    /// Returns an error when index is too far and buffer can't hold it or when
168    /// index is lower then end index
169    pub fn set_buffer_end(&mut self, index: u32) -> Result<(), PacketsArrayError> {
170        if index.overflowing_sub(self.buffer_start).0 > CRYPTO_PACKET_BUFFER_SIZE {
171            return Err(PacketsArrayError::too_big(index))
172        }
173
174        if index.overflowing_sub(self.buffer_end).0 > CRYPTO_PACKET_BUFFER_SIZE {
175            return Err(PacketsArrayError::lower_index(index))
176        }
177
178        self.buffer_end = index;
179
180        Ok(())
181    }
182
183    /// Set start index removing all packet before this index
184    ///
185    /// Returns an error when index is outside of buffer bounds
186    pub fn set_buffer_start(&mut self, index: u32) -> Result<(), PacketsArrayError> {
187        let len = self.len();
188
189        if self.buffer_end.overflowing_sub(index).0 > len || index.overflowing_sub(self.buffer_start).0 > len {
190            return Err(PacketsArrayError::outside_index(index))
191        }
192
193        for packet in &mut self.buffer[real_index(self.buffer_start) .. real_index(index)] {
194            *packet = None;
195        }
196
197        self.buffer_start = index;
198
199        Ok(())
200    }
201
202    /// Get mutable iterator over all stored packets with their index.
203    pub fn iter_mut(&mut self) -> impl Iterator<Item = (u32, &mut T)> {
204        let buffer_start = self.buffer_start;
205        let start = real_index(buffer_start);
206        let end = real_index(self.buffer_end);
207        let iter = if start > end {
208            let (first, second) = self.buffer.split_at_mut(start);
209            second.iter_mut().chain(first.iter_mut().take(end))
210        } else {
211            [].iter_mut().chain(self.buffer[start ..].iter_mut().take(end - start))
212        };
213        iter.enumerate().flat_map(move |(i, packet)|
214            packet.iter_mut().map(move |packet|
215                (buffer_start.overflowing_add(i as u32).0, &mut **packet)
216            )
217        )
218    }
219}
220
221#[cfg(test)]
222mod tests {
223    use super::*;
224
225    #[test]
226    fn len() {
227        let mut array = PacketsArray::<()>::new();
228        assert_eq!(array.len(), 0);
229        array.buffer_end = 1;
230        assert_eq!(array.len(), 1);
231        array.buffer_start = u32::max_value();
232        assert_eq!(array.len(), 2);
233    }
234
235    #[test]
236    fn insert() {
237        let mut array = PacketsArray::<()>::new();
238        assert!(array.insert(0, ()).is_ok());
239        assert_eq!(array.buffer_start, 0);
240        assert_eq!(array.buffer_end, 1);
241        assert!(array.get(0).is_some());
242        assert!(array.get(1).is_none());
243        assert!(array.insert(7, ()).is_ok());
244        assert_eq!(array.buffer_start, 0);
245        assert_eq!(array.buffer_end, 8);
246        assert!(array.get(7).is_some());
247        assert!(array.get(6).is_none());
248        assert!(array.get(8).is_none());
249    }
250
251    #[test]
252    fn insert_exists() {
253        let mut array = PacketsArray::<()>::new();
254        assert!(array.insert(7, ()).is_ok());
255        let res = array.insert(7, ());
256        assert!(res.is_err());
257        assert_eq!(*res.err().unwrap().kind(), PacketsArrayErrorKind::AlreadyExist { index: 7 });
258        assert!(array.insert(6, ()).is_ok());
259        assert!(array.insert(8, ()).is_ok());
260    }
261
262    #[test]
263    fn insert_too_big_index() {
264        let mut array = PacketsArray::<()>::new();
265        let res = array.insert(CRYPTO_PACKET_BUFFER_SIZE, ());
266        assert!(res.is_err());
267        assert_eq!(*res.err().unwrap().kind(), PacketsArrayErrorKind::TooBig { index: CRYPTO_PACKET_BUFFER_SIZE });
268        assert_eq!(array.buffer_start, 0);
269        assert_eq!(array.buffer_end, 0);
270        array.buffer_start = u32::max_value();
271        let res = array.insert(CRYPTO_PACKET_BUFFER_SIZE - 1, ());
272        assert!(res.is_err());
273        assert_eq!(*res.err().unwrap().kind(), PacketsArrayErrorKind::TooBig { index: CRYPTO_PACKET_BUFFER_SIZE - 1 });
274        assert_eq!(array.buffer_start, u32::max_value());
275        assert_eq!(array.buffer_end, 0);
276    }
277
278    #[test]
279    fn push_back() {
280        let mut array = PacketsArray::<()>::new();
281        assert!(array.push_back(()).is_ok());
282        assert_eq!(array.buffer_start, 0);
283        assert_eq!(array.buffer_end, 1);
284        assert!(array.get(0).is_some());
285    }
286
287    #[test]
288    fn push_back_overflow() {
289        let mut array = PacketsArray::<()>::new();
290        array.buffer_start = u32::max_value();
291        array.buffer_end = u32::max_value();
292        assert!(array.push_back(()).is_ok());
293        assert_eq!(array.buffer_start, u32::max_value());
294        assert_eq!(array.buffer_end, 0);
295        assert!(array.get(u32::max_value()).is_some());
296    }
297
298    #[test]
299    fn push_back_full() {
300        let mut array = PacketsArray::<()>::new();
301        array.buffer_end = CRYPTO_PACKET_BUFFER_SIZE;
302        let res = array.push_back(());
303        assert!(res.is_err());
304        assert_eq!(*res.err().unwrap().kind(), PacketsArrayErrorKind::ArrayFull);
305        assert_eq!(array.buffer_start, 0);
306        assert_eq!(array.buffer_end, CRYPTO_PACKET_BUFFER_SIZE);
307    }
308
309    #[test]
310    fn pop_front_some() {
311        let mut array = PacketsArray::<()>::new();
312        assert!(array.push_back(()).is_ok());
313        assert!(array.pop_front().is_some());
314        assert_eq!(array.buffer_start, 1);
315        assert_eq!(array.buffer_end, 1);
316        assert!(array.get(0).is_none());
317    }
318
319    #[test]
320    fn pop_front_none() {
321        let mut array = PacketsArray::<()>::new();
322        array.buffer_end = 1;
323        assert!(array.pop_front().is_none());
324        assert_eq!(array.buffer_start, 0);
325        assert_eq!(array.buffer_end, 1);
326    }
327
328    #[test]
329    fn pop_front_empty() {
330        let mut array = PacketsArray::<()>::new();
331        assert!(array.pop_front().is_none());
332        assert_eq!(array.buffer_start, 0);
333        assert_eq!(array.buffer_end, 0);
334    }
335
336    #[test]
337    fn contains() {
338        let mut array = PacketsArray::<()>::new();
339        assert!(array.push_back(()).is_ok());
340        assert!(array.contains(0));
341        assert!(!array.contains(1));
342        assert!(!array.contains(2));
343    }
344
345    #[test]
346    fn get() {
347        let mut array = PacketsArray::<()>::new();
348        assert!(array.push_back(()).is_ok());
349        assert!(array.get(0).is_some());
350        assert!(array.get(1).is_none());
351        assert!(array.get(2).is_none());
352    }
353
354    #[test]
355    fn get_mut() {
356        let mut array = PacketsArray::<()>::new();
357        assert!(array.push_back(()).is_ok());
358        assert!(array.get_mut(0).is_some());
359        assert!(array.get_mut(1).is_none());
360        assert!(array.get_mut(2).is_none());
361    }
362
363    #[test]
364    fn remove() {
365        let mut array = PacketsArray::<()>::new();
366        assert!(array.push_back(()).is_ok());
367        assert!(array.remove(0).is_some());
368        assert!(array.remove(0).is_none());
369        assert!(array.remove(1).is_none());
370        assert!(array.remove(2).is_none());
371        assert!(array.get(0).is_none());
372        assert_eq!(array.buffer_start, 0);
373        assert_eq!(array.buffer_end, 1);
374    }
375
376    #[test]
377    fn set_buffer_end() {
378        let mut array = PacketsArray::<()>::new();
379        assert!(array.set_buffer_end(7).is_ok());
380        assert_eq!(array.buffer_start, 0);
381        assert_eq!(array.buffer_end, 7);
382        assert!(array.set_buffer_end(CRYPTO_PACKET_BUFFER_SIZE).is_ok());
383        assert_eq!(array.buffer_start, 0);
384        assert_eq!(array.buffer_end, CRYPTO_PACKET_BUFFER_SIZE);
385    }
386
387    #[test]
388    fn set_buffer_end_too_big_index() {
389        let mut array = PacketsArray::<()>::new();
390        let res = array.set_buffer_end(CRYPTO_PACKET_BUFFER_SIZE + 1);
391        assert!(res.is_err());
392        assert_eq!(*res.err().unwrap().kind(), PacketsArrayErrorKind::TooBig { index: CRYPTO_PACKET_BUFFER_SIZE + 1 });
393        assert_eq!(array.buffer_start, 0);
394        assert_eq!(array.buffer_end, 0);
395    }
396
397    #[test]
398    fn set_buffer_end_lower_than_end_index() {
399        let mut array = PacketsArray::<()>::new();
400        array.buffer_end = 7;
401        let res = array.set_buffer_end(6);
402        assert!(res.is_err());
403        assert_eq!(*res.err().unwrap().kind(), PacketsArrayErrorKind::LowerIndex { index: 6 });
404        assert_eq!(array.buffer_start, 0);
405        assert_eq!(array.buffer_end, 7);
406    }
407
408    #[test]
409    fn set_buffer_start() {
410        let mut array = PacketsArray::<()>::new();
411        assert!(array.push_back(()).is_ok());
412        assert!(array.push_back(()).is_ok());
413        assert!(array.set_buffer_start(1).is_ok());
414        assert!(array.set_buffer_start(1).is_ok());
415        assert!(array.get(0).is_none());
416        assert!(array.get(1).is_some());
417        assert_eq!(array.buffer_start, 1);
418        assert_eq!(array.buffer_end, 2);
419        assert!(array.set_buffer_start(2).is_ok());
420        assert!(array.set_buffer_start(2).is_ok());
421        assert!(array.get(0).is_none());
422        assert!(array.get(1).is_none());
423        assert_eq!(array.buffer_start, 2);
424        assert_eq!(array.buffer_end, 2);
425    }
426
427    #[test]
428    fn set_buffer_start_too_big_index() {
429        let mut array = PacketsArray::<()>::new();
430        let res = array.set_buffer_start(1);
431        assert!(res.is_err());
432        assert_eq!(*res.err().unwrap().kind(), PacketsArrayErrorKind::OutsideIndex { index: 1 });
433        assert_eq!(array.buffer_start, 0);
434        assert_eq!(array.buffer_end, 0);
435    }
436
437    #[test]
438    fn set_buffer_start_lower_than_start_index() {
439        let mut array = PacketsArray::<()>::new();
440        array.buffer_start = 7;
441        array.buffer_end = 7;
442        let res = array.set_buffer_start(1);
443        assert!(res.is_err());
444        assert_eq!(*res.err().unwrap().kind(), PacketsArrayErrorKind::OutsideIndex { index: 1 });
445        assert_eq!(array.buffer_start, 7);
446        assert_eq!(array.buffer_end, 7);
447    }
448
449    #[test]
450    fn iter_mut_empty() {
451        let mut array = PacketsArray::<()>::new();
452        assert!(array.iter_mut().next().is_none());
453    }
454
455    #[test]
456    fn iter_mut_single_part() {
457        let mut array = PacketsArray::<()>::new();
458        assert!(array.insert(0, ()).is_ok());
459        assert!(array.insert(2, ()).is_ok());
460        assert!(array.insert(5, ()).is_ok());
461        assert_eq!(
462            array.iter_mut().map(|(i, _)| i).collect::<Vec<_>>(),
463            vec![0, 2, 5]
464        );
465    }
466
467    #[test]
468    fn iter_mut_two_parts() {
469        let mut array = PacketsArray::<()>::new();
470        array.buffer_start = CRYPTO_PACKET_BUFFER_SIZE - 1;
471        array.buffer_end = CRYPTO_PACKET_BUFFER_SIZE + 3;
472        assert!(array.insert(CRYPTO_PACKET_BUFFER_SIZE - 1, ()).is_ok());
473        assert!(array.insert(CRYPTO_PACKET_BUFFER_SIZE, ()).is_ok());
474        assert!(array.insert(CRYPTO_PACKET_BUFFER_SIZE + 2, ()).is_ok());
475        assert_eq!(
476            array.iter_mut().map(|(i, _)| i).collect::<Vec<_>>(),
477            vec![
478                CRYPTO_PACKET_BUFFER_SIZE - 1,
479                CRYPTO_PACKET_BUFFER_SIZE,
480                CRYPTO_PACKET_BUFFER_SIZE + 2,
481            ]
482        );
483    }
484}
tox_core/net_crypto/packets_array.rs

tox_core/net_crypto/
packets_array.rs
