Skip to main content

hopr_protocol_session/processing/
reassembly.rs

1//! Contains the frame [`Reassembler`]:
2//! an inverse component to the `Segmenter`.
3
4use std::{
5    future::Future,
6    pin::Pin,
7    task::{Context, Poll},
8    time::{Duration, Instant},
9};
10
11use futures_time::future::Timer;
12use tracing::instrument;
13
14use crate::{
15    errors::SessionError,
16    processing::{
17        reorder::SharedReorder,
18        types::{
19            FrameBuilder, FrameDashMap, FrameHashMap, FrameInspector, FrameMap, FrameMapEntry, FrameMapOccupiedEntry,
20            FrameMapVacantEntry,
21        },
22    },
23    protocol::{Frame, FrameId, Segment},
24};
25
26#[cfg(all(not(test), feature = "telemetry"))]
27lazy_static::lazy_static! {
28    static ref METRIC_TIME_TO_FRAME_FINISH: hopr_types::telemetry::SimpleHistogram =
29        hopr_types::telemetry::SimpleHistogram::new(
30            "hopr_session_time_to_finish_frame",
31            "Measures time in milliseconds it takes a frame to be reassembled",
32            vec![1.0, 2.0, 5.0, 10.0, 25.0, 50.0, 75.0, 100.0, 150.0, 200.0, 250.0, 300.0, 400.0, 500.0],
33        ).unwrap();
34}
35
36/// Reassembler is a stream adaptor that reads [`Segments`](Segment) from the underlying
37/// stream and tries to put them into correct order so they form a [`Frame`].
38///
39/// This is essentially the inverse of the `Segmenter`.
40///
41/// Reassembler takes two parameters: `max_age` and `capacity`:
42///
43/// The `max_age` specifies how long an incomplete Frame (with a missing segment(s)) is to be kept
44/// in the internal buffer until it is considered definitely lost.
45/// In other words, it specifies how long the reassembler is allowed to wait for all segments
46/// of a Frame to arrive from the underlying stream.
47///
48/// The `capacity` specifies the maximum number of incomplete frames to keep in
49/// the internal buffer. If the reassembler is at maximum capacity, the underlying stream is not
50/// polled for new segments, leaving the oldest incomplete frames in the reassembler to expire and
51/// be definitely lost.
52///
53/// By definition, Reassembler is a fallible stream, yielding either `Ok(Some(`[`Frame`]`))`,
54/// `Err(`[`SessionError::FrameDiscarded`]`)` when a frame is lost due to expiry, or `Ok(None)` when
55/// there are no more elements in the underlying stream.
56///
57/// The reassemblers internal buffer is stored in a [`FrameMap`] and can be constructed using
58/// different implementations of it, suitable for different use-cases.
59///
60/// Use [`ReassemblerExt`] methods to turn a ` Segment ` stream into a fallible `Frame` stream using the `Reassembler`.
61#[must_use = "streams do nothing unless polled"]
62#[pin_project::pin_project]
63pub struct Reassembler<S, M> {
64    #[pin]
65    inner: S,
66    #[pin]
67    timer: futures_time::task::Sleep,
68    incomplete_frames: M,
69    expired_frames: Vec<FrameId>,
70    max_age: Duration,
71    capacity: usize,
72    last_expiration: Option<Instant>,
73    /// Where the time a frame of several segments took to arrive whole is recorded, if anywhere.
74    reorder: Option<SharedReorder>,
75}
76
77impl<S: futures::Stream<Item = Segment>, M: FrameMap> Reassembler<S, M> {
78    fn new(inner: S, incomplete_frames: M, max_age: Duration, capacity: usize, reorder: Option<SharedReorder>) -> Self {
79        Self {
80            inner,
81            timer: futures_time::task::sleep(
82                (max_age + Duration::from_millis(1))
83                    .max(Duration::from_millis(1))
84                    .into(),
85            ),
86            incomplete_frames,
87            expired_frames: Vec::with_capacity(capacity),
88            last_expiration: None,
89            max_age,
90            capacity,
91            reorder,
92        }
93    }
94
95    fn expire_frames(incomplete_frames: &mut M, expired_frames: &mut Vec<FrameId>, max_age: Duration) {
96        incomplete_frames.retain(|id, builder| {
97            if builder.last_recv.elapsed() >= max_age {
98                expired_frames.push(*id);
99                false
100            } else {
101                true
102            }
103        });
104    }
105}
106
107impl<S: futures::Stream<Item = Segment>, M: FrameMap> futures::Stream for Reassembler<S, M> {
108    type Item = Result<Frame, SessionError>;
109
110    #[instrument(name = "Reassembler::poll_next", level = "trace", skip(self, cx), fields(num_incomplete = self.incomplete_frames.len()), ret)]
111    fn poll_next(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<Self::Item>> {
112        let mut this = self.project();
113        loop {
114            if let Some(frame_id) = this.expired_frames.pop() {
115                tracing::trace!(frame_id, "emit discarded frame");
116                return Poll::Ready(Some(Err(SessionError::FrameDiscarded(frame_id))));
117            }
118
119            // Poll the timer only if there are incomplete frames
120            let timer_poll = if this.incomplete_frames.len() > 0 {
121                this.timer.as_mut().poll(cx)
122            } else {
123                Poll::Pending
124            };
125
126            // Poll the inner stream only if there's space in the reassembler
127            let inner_poll = if this.incomplete_frames.len() < *this.capacity {
128                this.inner.as_mut().poll_next(cx)
129            } else {
130                // This essentially forces the incomplete frames to be expired
131                tracing::warn!("reassembler has reached its capacity");
132                Poll::Pending
133            };
134
135            tracing::trace!("polling next");
136            match (inner_poll, timer_poll) {
137                (Poll::Ready(Some(item)), timer) => {
138                    if timer.is_ready() {
139                        this.timer.as_mut().reset_timer();
140                    }
141
142                    tracing::trace!(
143                        frame_id = item.frame_id,
144                        seq_idx = item.seq_idx,
145                        seq_len = %item.seq_flags,
146                        "received segment"
147                    );
148
149                    match this.incomplete_frames.entry(item.frame_id) {
150                        FrameMapEntry::Occupied(mut e) => {
151                            let builder = e.get_builder_mut();
152                            let seg_id = item.id();
153                            match builder.add_segment(item) {
154                                Ok(_) => {
155                                    tracing::trace!(frame_id = builder.frame_id(), %seg_id, "added segment");
156                                    if builder.is_complete() {
157                                        #[cfg(all(not(test), feature = "telemetry"))]
158                                        METRIC_TIME_TO_FRAME_FINISH
159                                            .observe(builder.created.elapsed().as_millis() as f64);
160
161                                        tracing::trace!(frame_id = builder.frame_id(), "frame is complete");
162                                        // Its segments were sent together and took different paths:
163                                        // how far apart they arrived is the spread of those paths.
164                                        if let Some(reorder) = this.reorder.as_ref() {
165                                            let now = Instant::now();
166                                            reorder.record(now, now.duration_since(builder.created));
167                                        }
168                                        return Poll::Ready(Some(e.finalize().try_into()));
169                                    }
170                                }
171                                Err(error) => {
172                                    tracing::error!(%error, %seg_id, "encountered invalid segment");
173                                }
174                            }
175                        }
176                        FrameMapEntry::Vacant(e) => {
177                            let builder = FrameBuilder::from(item);
178                            if builder.is_complete() {
179                                #[cfg(all(not(test), feature = "telemetry"))]
180                                METRIC_TIME_TO_FRAME_FINISH.observe(builder.created.elapsed().as_millis() as f64);
181
182                                tracing::trace!(frame_id = builder.frame_id(), "segment frame is complete");
183                                return Poll::Ready(Some(builder.try_into()));
184                            } else {
185                                tracing::trace!(frame_id = builder.frame_id(), "added segment for new frame");
186                                e.insert_builder(builder);
187                            }
188                        }
189                    };
190
191                    // Since the retaining operation is potentially expensive,
192                    // we do it actually only if there's a real chance that a frame is expired
193                    if this.last_expiration.is_none_or(|e| e.elapsed() >= *this.max_age) {
194                        Self::expire_frames(this.incomplete_frames, this.expired_frames, *this.max_age);
195                        *this.last_expiration = Some(Instant::now());
196                    }
197                }
198                (Poll::Ready(None), _) => {
199                    // Inner stream closed, dump all incomplete frames
200                    tracing::trace!("inner stream closed, dumping incomplete frames");
201                    if this.incomplete_frames.len() > 0 {
202                        this.incomplete_frames.retain(|id, _| {
203                            this.expired_frames.push(*id);
204                            false
205                        });
206                    } else {
207                        tracing::trace!("done");
208                        return Poll::Ready(None);
209                    }
210                }
211                (Poll::Pending, Poll::Ready(_)) => {
212                    // Check if some frames are expired
213                    Self::expire_frames(this.incomplete_frames, this.expired_frames, *this.max_age);
214                    *this.last_expiration = Some(Instant::now());
215                    this.timer.as_mut().reset_timer();
216                }
217                (Poll::Pending, Poll::Pending) => return Poll::Pending,
218            }
219        }
220    }
221}
222
223/// Stream extension methods for frame reassembly.
224pub trait ReassemblerExt: futures::Stream<Item = Segment> {
225    /// Attaches a [`Reassembler`] with the given `timeout` for frame completion and `capacity`
226    /// to this stream.
227    fn reassembler(self, timeout: Duration, capacity: usize) -> Reassembler<Self, FrameHashMap>
228    where
229        Self: Sized,
230    {
231        self.reassembler_sharing(timeout, capacity, None)
232    }
233
234    /// As [`ReassemblerExt::reassembler`], recording into `reorder` how long each frame of several
235    /// segments took from its first segment to its last.
236    fn reassembler_sharing(
237        self,
238        timeout: Duration,
239        capacity: usize,
240        reorder: Option<SharedReorder>,
241    ) -> Reassembler<Self, FrameHashMap>
242    where
243        Self: Sized,
244    {
245        // FrameHashMap is much faster than a FrameDashMap used in a FrameInspector
246        Reassembler::new(
247            self,
248            FrameHashMap::with_capacity(FrameInspector::INCOMPLETE_FRAME_RATIO * capacity + 1),
249            timeout,
250            capacity,
251            reorder,
252        )
253    }
254
255    /// Attaches a [`Reassembler`] with the given `timeout` for frame completion, `capacity`
256    /// to this stream and [`FrameInspector`].
257    ///
258    /// Use only in situations where the [`FrameInspector`] is really needed, as such Reassembler
259    /// is slower than a Reassembler without a `FrameInspector`.
260    fn reassembler_with_inspector(
261        self,
262        timeout: Duration,
263        capacity: usize,
264        inspector: FrameInspector,
265    ) -> Reassembler<Self, FrameDashMap>
266    where
267        Self: Sized,
268    {
269        Reassembler::new(self, inspector.0.clone(), timeout, capacity, None)
270    }
271}
272
273impl<T: ?Sized> ReassemblerExt for T where T: futures::Stream<Item = Segment> {}
274
275#[cfg(test)]
276mod tests {
277    use std::cmp::Ordering;
278
279    use anyhow::anyhow;
280    use futures::{SinkExt, StreamExt, TryStreamExt, pin_mut};
281    use futures_time::future::FutureExt;
282    use hex_literal::hex;
283    use rand::{SeedableRng, prelude::SliceRandom, rngs::StdRng};
284
285    use super::*;
286    use crate::utils::segment;
287
288    const RNG_SEED: [u8; 32] = hex!("d8a471f1c20490a3442b96fdde9d1807428096e1601b0cef0eea7e6d44a24c01");
289
290    fn result_comparator(a: &Result<Frame, SessionError>, b: &Result<Frame, SessionError>) -> Ordering {
291        match (a, b) {
292            (Ok(a), Ok(b)) => a.frame_id.cmp(&b.frame_id),
293            (Err(SessionError::FrameDiscarded(a)), Ok(b)) => a.cmp(&b.frame_id),
294            (Ok(a), Err(SessionError::FrameDiscarded(b))) => a.frame_id.cmp(b),
295            (Err(SessionError::FrameDiscarded(a)), Err(SessionError::FrameDiscarded(b))) => a.cmp(b),
296            _ => panic!("unexpected result"),
297        }
298    }
299
300    #[test_log::test(tokio::test)]
301    pub async fn reassembler_should_reassemble_frames() -> anyhow::Result<()> {
302        let expected = (1u32..=10)
303            .map(|frame_id| Frame {
304                frame_id,
305                data: hopr_types::crypto_random::random_bytes::<100>().into(),
306                is_terminating: false,
307            })
308            .collect::<Vec<_>>();
309
310        let (r_sink, r_stream) = futures::channel::mpsc::unbounded();
311        let r_stream = r_stream.reassembler(Duration::from_secs(5), 1024);
312
313        let mut segments = expected
314            .iter()
315            .cloned()
316            .flat_map(|f| segment(f.data, 22, f.frame_id).unwrap())
317            .collect::<Vec<_>>();
318
319        let mut rng = StdRng::from_seed(RNG_SEED);
320        segments.shuffle(&mut rng);
321
322        let jh = hopr_utils::runtime::prelude::spawn(futures::stream::iter(segments).map(Ok).forward(r_sink));
323
324        let mut actual = r_stream
325            .try_collect::<Vec<_>>()
326            .timeout(futures_time::time::Duration::from_secs(5))
327            .await??;
328
329        assert_eq!(actual.len(), expected.len());
330
331        actual.sort_by_key(|a| a.frame_id);
332        assert_eq!(actual, expected);
333
334        let _ = jh.await?;
335        Ok(())
336    }
337
338    #[test_log::test(tokio::test)]
339    pub async fn reassembler_should_discard_incomplete_frames_on_expiration() -> anyhow::Result<()> {
340        let expected = (1u32..=10)
341            .map(|frame_id| Frame {
342                frame_id,
343                data: hopr_types::crypto_random::random_bytes::<100>().into(),
344                is_terminating: false,
345            })
346            .collect::<Vec<_>>();
347
348        let (r_sink, r_stream) = futures::channel::mpsc::unbounded();
349        let r_stream = r_stream.reassembler(Duration::from_millis(45), 1024);
350
351        let mut segments = expected
352            .iter()
353            .cloned()
354            .flat_map(|f| segment(f.data, 22, f.frame_id).unwrap())
355            .filter(|s| s.frame_id != 2 || s.seq_idx != 1)
356            .collect::<Vec<_>>();
357
358        let mut rng = StdRng::from_seed(RNG_SEED);
359        segments.shuffle(&mut rng);
360
361        pin_mut!(r_sink);
362        r_sink.send_all(&mut futures::stream::iter(segments).map(Ok)).await?;
363
364        let mut actual = Vec::new();
365        pin_mut!(r_stream);
366        for _ in 0..expected.len() {
367            actual.push(r_stream.next().await.ok_or(anyhow!("missing frame"))?);
368        }
369        r_sink.close().await?;
370        assert_eq!(None, r_stream.try_next().await?);
371
372        actual.sort_by(result_comparator);
373
374        assert_eq!(actual.len(), expected.len());
375
376        for i in 0..expected.len() {
377            if i != 1 {
378                assert!(matches!(&actual[i], Ok(f) if *f == expected[i]));
379            } else {
380                // Frame 2 had a missing segment; therefore, there should be an error
381                assert!(matches!(actual[i], Err(SessionError::FrameDiscarded(2))));
382            }
383        }
384
385        Ok(())
386    }
387
388    #[test_log::test(tokio::test)]
389    pub async fn reassembler_should_discard_incomplete_frames_on_close() -> anyhow::Result<()> {
390        let expected = (1u32..=10)
391            .map(|frame_id| Frame {
392                frame_id,
393                data: hopr_types::crypto_random::random_bytes::<100>().into(),
394                is_terminating: false,
395            })
396            .collect::<Vec<_>>();
397
398        let (r_sink, r_stream) = futures::channel::mpsc::unbounded();
399        let r_stream = r_stream.reassembler(Duration::from_millis(100), 1024);
400
401        let mut segments = expected
402            .iter()
403            .cloned()
404            .flat_map(|f| segment(f.data, 22, f.frame_id).unwrap())
405            .filter(|s| s.frame_id != 5 || s.seq_idx != 2)
406            .collect::<Vec<_>>();
407
408        let mut rng = StdRng::from_seed(RNG_SEED);
409        segments.shuffle(&mut rng);
410
411        let jh = hopr_utils::runtime::prelude::spawn(futures::stream::iter(segments).map(Ok).forward(r_sink));
412
413        let mut actual = r_stream
414            .collect::<Vec<_>>()
415            .timeout(futures_time::time::Duration::from_secs(5))
416            .await?;
417
418        // Since `forward` closed the sink, even the incomplete Frame 5 should be yielded as error
419        assert_eq!(actual.len(), expected.len());
420
421        actual.sort_by(result_comparator);
422
423        for i in 0..expected.len() {
424            if i != 4 {
425                assert!(matches!(&actual[i], Ok(f) if *f == expected[i]));
426            } else {
427                // Frame 5 had a missing segment, therefore there should be an error
428                assert!(matches!(actual[i], Err(SessionError::FrameDiscarded(5))));
429            }
430        }
431
432        let _ = jh.await?;
433        Ok(())
434    }
435
436    #[test_log::test(tokio::test)]
437    pub async fn reassembler_should_wait_and_discard_if_full() -> anyhow::Result<()> {
438        let expected = (1u32..=5)
439            .map(|frame_id| Frame {
440                frame_id,
441                data: hopr_types::crypto_random::random_bytes::<30>().into(),
442                is_terminating: false,
443            })
444            .collect::<Vec<_>>();
445
446        let (r_sink, r_stream) = futures::channel::mpsc::unbounded();
447        let r_stream = r_stream.reassembler(Duration::from_millis(200), 3);
448
449        pin_mut!(r_sink);
450        pin_mut!(r_stream);
451
452        // This creates 5 frames with 2 segments each
453        let segments = expected
454            .iter()
455            .cloned()
456            .flat_map(|f| segment(f.data, 20, f.frame_id).unwrap())
457            .collect::<Vec<_>>();
458
459        let to_send = [
460            // Frame 1: Segment 2, Segment 1 missing
461            segments[1].clone(),
462            // Frame 2: Segment 1, Segment 2 missing
463            segments[2].clone(),
464            // Frame 3: Segment 2, Segment 1 missing
465            segments[5].clone(),
466        ];
467
468        let start = Instant::now();
469
470        // Reassembler now contains 3 incomplete frames
471        r_sink.send_all(&mut futures::stream::iter(to_send).map(Ok)).await?;
472
473        // It must not yield anything
474        assert!(
475            r_stream
476                .next()
477                .timeout(futures_time::time::Duration::from_millis(20))
478                .await
479                .is_err()
480        );
481
482        // Entire Frames 4 & 5
483        r_sink
484            .send_all(
485                &mut futures::stream::iter([
486                    segments[6].clone(),
487                    segments[7].clone(),
488                    segments[8].clone(),
489                    segments[9].clone(),
490                ])
491                .map(Ok),
492            )
493            .await?;
494
495        let mut reassembled = Vec::new();
496        for _ in 0..5 {
497            reassembled.push(r_stream.next().await.ok_or(anyhow!("missing frame"))?);
498        }
499        reassembled.sort_by(result_comparator);
500
501        assert!(
502            matches!(reassembled[0], Err(SessionError::FrameDiscarded(1))),
503            "{:?} must be discarded ID 1",
504            reassembled[0]
505        );
506        assert!(
507            matches!(reassembled[1], Err(SessionError::FrameDiscarded(2))),
508            "{:?} must be discarded ID 2",
509            reassembled[1]
510        );
511        assert!(
512            matches!(reassembled[2], Err(SessionError::FrameDiscarded(3))),
513            "{:?} must be discarded ID 3",
514            reassembled[2]
515        );
516        assert!(
517            matches!(&reassembled[3], Ok(f) if f == &expected[3].clone()),
518            "{:?} (idx 3) must be {:?}",
519            reassembled[3],
520            expected[3]
521        );
522        assert!(
523            matches!(&reassembled[4], Ok(f) if f == &expected[4].clone()),
524            "{:?} (idx 3) must be {:?}",
525            reassembled[4],
526            expected[4]
527        );
528
529        r_sink.close().await?;
530        assert_eq!(None, r_stream.try_next().await?);
531
532        assert!(start.elapsed() >= Duration::from_millis(200));
533
534        Ok(())
535    }
536}