1use 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#[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 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 let timer_poll = if this.incomplete_frames.len() > 0 {
121 this.timer.as_mut().poll(cx)
122 } else {
123 Poll::Pending
124 };
125
126 let inner_poll = if this.incomplete_frames.len() < *this.capacity {
128 this.inner.as_mut().poll_next(cx)
129 } else {
130 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 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 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 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 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
223pub trait ReassemblerExt: futures::Stream<Item = Segment> {
225 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 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 Reassembler::new(
247 self,
248 FrameHashMap::with_capacity(FrameInspector::INCOMPLETE_FRAME_RATIO * capacity + 1),
249 timeout,
250 capacity,
251 reorder,
252 )
253 }
254
255 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 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 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 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 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 segments[1].clone(),
462 segments[2].clone(),
464 segments[5].clone(),
466 ];
467
468 let start = Instant::now();
469
470 r_sink.send_all(&mut futures::stream::iter(to_send).map(Ok)).await?;
472
473 assert!(
475 r_stream
476 .next()
477 .timeout(futures_time::time::Duration::from_millis(20))
478 .await
479 .is_err()
480 );
481
482 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}