1use futures::{Stream, StreamExt};
13use hopr_api::types::internal::routing::{DestinationRouting, ResolvedTransportRouting};
14use hopr_crypto_packet::prelude::{HoprSurb, PacketSignal};
15use hopr_protocol_app::prelude::ApplicationDataOut;
16use tracing::{Instrument, error, trace, warn};
17
18use super::errors::Result as PathResult;
19
20const SURB_RETRY_INTERVAL: std::time::Duration = std::time::Duration::from_millis(5);
22
23pub(crate) const DEFAULT_SURB_RESOLUTION_WAIT: std::time::Duration = std::time::Duration::from_secs(6);
41
42pub(crate) fn surb_resolution_wait(configured: Option<std::time::Duration>) -> std::time::Duration {
48 configured.unwrap_or(DEFAULT_SURB_RESOLUTION_WAIT)
49}
50
51pub(crate) fn resolve_routing_stage_with_context<St, F, Fut>(
67 input: St,
68 resolve: F,
69 distress_threshold: usize,
70 concurrency: usize,
71 surb_wait: std::time::Duration,
72) -> impl Stream<Item = crate::trace_context::WithContext<(ResolvedTransportRouting<HoprSurb>, ApplicationDataOut)>>
73where
74 St: Stream<Item = crate::trace_context::WithContext<(DestinationRouting, ApplicationDataOut)>>,
75 F: Fn(usize, usize, DestinationRouting) -> Fut + Clone,
76 Fut: Future<Output = PathResult<(ResolvedTransportRouting<HoprSurb>, Option<usize>, Option<u8>)>>,
77{
78 input
79 .map(move |message| {
80 let ((unresolved, mut data), span) = message.into_parts();
81 let request_span = tracing::debug_span!(
82 parent: &span,
83 "transport.send",
84 packet_id = crate::trace_context::next_packet_id()
85 );
86 let span = if request_span.is_disabled() { span } else { request_span };
87 let output_span = span.clone();
88 let resolve = resolve.clone();
89 async move {
90 let deadline = std::time::Instant::now() + surb_wait;
96 loop {
97 hopr_transport_session::counters::ROUTING_RESOLUTION_ATTEMPTS
98 .fetch_add(1, std::sync::atomic::Ordering::Relaxed);
99 trace!(?unresolved, "resolving routing for packet");
100 match resolve(
101 data.data.total_len(),
102 data.estimate_surbs_with_msg(),
103 unresolved.clone(),
104 )
105 .await
106 {
107 Ok((resolved, rem_surbs, generation)) => {
108 let mut signals_to_dst = data
112 .packet_info
113 .as_ref()
114 .map(|info| info.signals_to_destination)
115 .unwrap_or_default();
116
117 if resolved.is_return() {
118 signals_to_dst = match rem_surbs {
119 Some(rem) if (1..distress_threshold.max(2)).contains(&rem) => {
120 signals_to_dst | PacketSignal::SurbDistress
121 }
122 Some(0) => signals_to_dst | PacketSignal::OutOfSurbs,
123 _ => signals_to_dst - (PacketSignal::OutOfSurbs | PacketSignal::SurbDistress),
124 };
125 } else {
126 signals_to_dst -= PacketSignal::SurbDistress | PacketSignal::OutOfSurbs;
128 }
129
130 let info = data.packet_info.get_or_insert_default();
131 info.signals_to_destination = signals_to_dst;
132 info.surb_generation = generation;
136 trace!(?resolved, "resolved routing for packet");
137 return Some(crate::trace_context::WithContext::new((resolved, data), output_span));
138 }
139 Err(error) if error.is_surb() && std::time::Instant::now() >= deadline => {
140 hopr_transport_session::counters::ROUTING_RESOLUTION_SURB_TIMEOUTS
141 .fetch_add(1, std::sync::atomic::Ordering::Relaxed);
142 warn!(
146 ?unresolved,
147 ?surb_wait,
148 %error,
149 "dropping an outgoing packet: no SURB for its return path within the wait"
150 );
151 data.surb_refund.give_back();
154 return None;
155 }
156 Err(error) if error.is_surb() => {
157 futures_timer::Delay::new(SURB_RETRY_INTERVAL).await;
160 }
161 Err(error) => {
162 hopr_transport_session::counters::ROUTING_RESOLUTION_FAILURES
163 .fetch_add(1, std::sync::atomic::Ordering::Relaxed);
164 error!(%error, "failed to resolve routing");
165 return None;
166 }
167 }
168 }
169 }
170 .instrument(tracing::debug_span!(parent: &span, "routing.resolve"))
171 .instrument(span)
172 })
173 .buffered(concurrency)
174 .filter_map(futures::future::ready)
175}
176
177#[cfg(test)]
178pub(crate) fn resolve_routing_stage<St, F, Fut>(
179 input: St,
180 resolve: F,
181 distress_threshold: usize,
182 concurrency: usize,
183 surb_wait: std::time::Duration,
184) -> impl Stream<Item = (ResolvedTransportRouting<HoprSurb>, ApplicationDataOut)>
185where
186 St: Stream<Item = (DestinationRouting, ApplicationDataOut)>,
187 F: Fn(usize, usize, DestinationRouting) -> Fut + Clone,
188 Fut: Future<Output = PathResult<(ResolvedTransportRouting<HoprSurb>, Option<usize>, Option<u8>)>>,
189{
190 resolve_routing_stage_with_context(
191 input.map(Into::into),
192 resolve,
193 distress_threshold,
194 concurrency,
195 surb_wait,
196 )
197 .map(|message| message.value)
198}
199
200#[cfg(test)]
201mod tests {
202 use std::sync::{
203 Arc,
204 atomic::{AtomicU64, AtomicUsize, Ordering},
205 };
206
207 use futures_time::future::FutureExt as _;
208 use hopr_api::types::{
209 crypto::{crypto_traits::Randomizable, prelude::*},
210 internal::{
211 path::ValidatedPath,
212 prelude::HoprPseudonym,
213 routing::{RoutingOptions, SurbMatcher},
214 },
215 };
216 use hopr_protocol_app::prelude::{ApplicationData, SurbRefund, Tag};
217
218 use super::*;
219 use crate::path::errors::PathPlannerError;
220
221 #[rstest::rstest]
222 #[case(hopr_transport_session::Capabilities::default())]
223 #[case(hopr_transport_session::Capability::Segmentation.into())]
224 #[case(hopr_transport_session::Capability::Segmentation | hopr_transport_session::Capability::RetransmissionAck)]
225 #[cfg(feature = "tracing-context")]
226 #[tokio::test(flavor = "multi_thread", worker_threads = 2)]
227 #[serial_test::serial(routing_logs)]
228 async fn queued_sessions_should_keep_their_context_through_routing_and_encoding(
229 #[case] capabilities: hopr_transport_session::Capabilities,
230 ) -> anyhow::Result<()> {
231 use anyhow::Context as _;
232 use futures::AsyncWriteExt;
233
234 use crate::{tests::support::Logs, trace_context::ContextSender};
235
236 let logs = Logs::default();
237 let subscriber = logs.subscriber(tracing::Level::DEBUG);
238 logs.with_cpu_subscriber(subscriber, async {
239 let (tx, rx) = hopr_utils::network_types::crossfire_sink::bounded_sink_channel(4);
240 let tx = ContextSender::new(tx);
241 let ids = [HoprPseudonym::random(), HoprPseudonym::random()];
242 for (index, id) in ids.iter().enumerate() {
243 let mut session = hopr_transport_session::HoprSession::new(
245 *id,
246 forward_routing(),
247 hopr_transport_session::HoprSessionConfig {
248 capabilities,
249 ..Default::default()
250 },
251 (tx.clone(), futures::stream::pending()),
252 None,
253 )?;
254 session.write_all(&[index as u8]).await?;
255 session.flush().await?;
256 }
257 drop(tx);
258 let resolved_messages = resolve_routing_stage_with_context(
259 rx.take(2),
260 |_, _, _| async {
261 tokio::task::yield_now().await;
263 tracing::debug!("session route resolved");
264 Ok((resolved(), None, None))
265 },
266 TEST_DISTRESS_THRESHOLD,
267 2,
268 TEST_SURB_WAIT,
269 )
270 .collect::<Vec<_>>()
271 .await;
272 assert_eq!(resolved_messages.len(), 2);
273 for message in resolved_messages {
276 let marker = *message
277 .value
278 .1
279 .data
280 .plain_text
281 .last()
282 .context("missing session payload")?;
283 let dispatch = tracing::dispatcher::get_default(Clone::clone);
284 async move {
285 hopr_utils::parallelize::cpu::spawn_encode_blocking(
286 move || {
287 tracing::dispatcher::with_default(&dispatch, || {
289 tracing::debug!(marker, "session CPU encoding");
290 });
291 },
292 "session_context_test",
293 )
294 .await?;
295 anyhow::Ok(())
296 }
297 .instrument(message.into_parts().1)
298 .await?;
299 }
300 for event in logs
301 .records("session route resolved")
302 .into_iter()
303 .chain(logs.records("session CPU encoding"))
304 {
305 assert!(event.ancestry.contains(&"session"), "missing session ancestor");
306 assert!(event.ancestry.contains(&"transport.send"), "missing packet ancestor");
307 assert!(!event.fields.contains_key("session_id"));
308 assert!(!event.fields.contains_key("packet_id"));
309 }
310 assert_eq!(logs.records("session route resolved").len(), 2);
311 assert_eq!(logs.records("session CPU encoding").len(), 2);
312 let output = logs.output();
313 for (marker, id) in ids.iter().enumerate() {
314 let route = output
315 .lines()
316 .find(|line| line.contains("session route resolved") && line.contains(&id.to_string()))
317 .context("missing routed session")?;
318 let packet_id = route
319 .split("packet_id=")
320 .nth(1)
321 .context("routing must expose its packet identifier")?
322 .chars()
323 .take_while(char::is_ascii_digit)
324 .collect::<String>();
325 let line = output
326 .lines()
327 .find(|line| line.contains("session CPU encoding") && line.contains(&format!("marker={marker}")))
328 .context("missing encoded session")?;
329 assert!(line.contains(&id.to_string()), "encoder lost its session: {line}");
330 assert!(
331 line.contains(&format!("packet_id={packet_id}}}")),
332 "encoder changed its packet: {line}"
333 );
334 assert!(
335 !line.contains(&ids[1 - marker].to_string()),
336 "session context leaked: {line}"
337 );
338 }
339 anyhow::Ok(())
340 })?
341 }
342
343 const TEST_TIMEOUT: std::time::Duration = std::time::Duration::from_secs(5);
346
347 const TEST_SURB_WAIT: std::time::Duration = std::time::Duration::from_millis(200);
352
353 const TEST_TAG: u64 = 1234;
354
355 const TEST_CONCURRENCY: usize = 8;
358
359 const TEST_DISTRESS_THRESHOLD: usize = 2;
360
361 fn stage<St, F, Fut>(
364 input: St,
365 resolve: F,
366 ) -> impl Stream<Item = (ResolvedTransportRouting<HoprSurb>, ApplicationDataOut)>
367 where
368 St: Stream<Item = (DestinationRouting, ApplicationDataOut)>,
369 F: Fn(usize, usize, DestinationRouting) -> Fut + Clone,
370 Fut: Future<Output = PathResult<(ResolvedTransportRouting<HoprSurb>, Option<usize>, Option<u8>)>>,
371 {
372 resolve_routing_stage(
373 input,
374 resolve,
375 TEST_DISTRESS_THRESHOLD,
376 TEST_CONCURRENCY,
377 TEST_SURB_WAIT,
378 )
379 }
380
381 fn resolved() -> ResolvedTransportRouting<HoprSurb> {
385 ResolvedTransportRouting::Forward {
386 pseudonym: HoprPseudonym::random(),
387 forward_path: ValidatedPath::direct(
388 *OffchainKeypair::random().public(),
389 ChainKeypair::random().public().to_address(),
390 ),
391 return_paths: vec![],
392 }
393 }
394
395 fn forward_routing() -> DestinationRouting {
396 DestinationRouting::forward_only(
397 *OffchainKeypair::random().public(),
398 RoutingOptions::Hops(1.try_into().expect("1 is a valid hop count")),
399 )
400 }
401
402 fn return_routing(pseudonym: HoprPseudonym) -> DestinationRouting {
403 DestinationRouting::Return(SurbMatcher::Pseudonym(pseudonym))
404 }
405
406 fn packet(marker: u8) -> ApplicationDataOut {
408 ApplicationDataOut::with_no_packet_info(
409 ApplicationData::new(Tag::from(TEST_TAG), &[marker]).expect("a one-byte payload is valid"),
410 )
411 }
412
413 fn marker_of(data: &ApplicationDataOut) -> u8 {
414 data.data.plain_text[0]
415 }
416
417 fn no_surb(routing: &DestinationRouting) -> PathPlannerError {
423 let pseudonym = match routing {
424 DestinationRouting::Return(matcher) => matcher.pseudonym().to_string(),
425 DestinationRouting::Forward { .. } => unreachable!("only return routing can starve for SURBs"),
426 };
427 PathPlannerError::Surb(format!("no surb for pseudonym {pseudonym}"))
428 }
429
430 #[test_log::test(tokio::test)]
443 async fn a_starved_return_packet_should_not_withhold_the_packets_behind_it() -> anyhow::Result<()> {
444 let starved = HoprPseudonym::random();
445 let dropped_before = hopr_transport_session::counters::routing_resolution_surb_timeout_count();
446
447 let input = futures::stream::iter(vec![
448 (return_routing(starved), packet(0)),
449 (forward_routing(), packet(1)),
450 (forward_routing(), packet(2)),
451 ]);
452
453 let emitted = stage(
454 input,
455 |_size_hint, _max_surbs, routing: DestinationRouting| async move {
456 match routing {
457 DestinationRouting::Return(_) => Err(no_surb(&routing)),
458 DestinationRouting::Forward { .. } => Ok((resolved(), None, None)),
459 }
460 },
461 )
462 .take(2)
463 .collect::<Vec<_>>()
464 .timeout(futures_time::time::Duration::from(TEST_TIMEOUT))
465 .await;
466
467 let emitted = emitted.map_err(|_| {
468 anyhow::anyhow!(
469 "origination stalled: the two forward packets queued behind a return packet whose pseudonym has no \
470 SURBs were never emitted within {TEST_TIMEOUT:?}. Every packet this node originates passes through \
471 this stage, so this is a node-wide origination outage."
472 )
473 })?;
474
475 assert_eq!(
476 emitted.iter().map(|(_, data)| marker_of(data)).collect::<Vec<_>>(),
477 vec![1, 2],
478 "the packets behind the starved one must be emitted, in order"
479 );
480
481 assert!(
485 hopr_transport_session::counters::routing_resolution_surb_timeout_count() > dropped_before,
486 "the starved packet was dropped without being counted, so the condition stays invisible"
487 );
488
489 Ok(())
490 }
491
492 #[test]
493 fn an_unset_wait_should_fall_back_to_the_default() {
494 assert_eq!(DEFAULT_SURB_RESOLUTION_WAIT, surb_resolution_wait(None));
495 }
496
497 #[test]
498 fn a_configured_wait_should_be_honoured() {
499 let configured = std::time::Duration::from_millis(2_500);
500 assert_eq!(configured, surb_resolution_wait(Some(configured)));
501 }
502
503 #[test]
508 fn a_zero_wait_should_mean_no_wait_rather_than_the_default() {
509 assert_eq!(
510 std::time::Duration::ZERO,
511 surb_resolution_wait(Some(std::time::Duration::ZERO))
512 );
513 }
514
515 #[test_log::test(tokio::test)]
521 async fn a_zero_wait_should_drop_a_starved_return_packet_without_retrying() -> anyhow::Result<()> {
522 let attempts = Arc::new(AtomicUsize::new(0));
523 let input = futures::stream::iter(vec![(return_routing(HoprPseudonym::random()), packet(0))]);
524
525 let emitted = {
526 let attempts = attempts.clone();
527 resolve_routing_stage(
528 input,
529 move |_size_hint, _max_surbs, routing: DestinationRouting| {
530 let attempts = attempts.clone();
531 async move {
532 attempts.fetch_add(1, Ordering::Relaxed);
533 Err(no_surb(&routing))
534 }
535 },
536 TEST_DISTRESS_THRESHOLD,
537 TEST_CONCURRENCY,
538 surb_resolution_wait(Some(std::time::Duration::ZERO)),
539 )
540 .collect::<Vec<_>>()
541 .timeout(futures_time::time::Duration::from(TEST_TIMEOUT))
542 .await
543 .map_err(|_| anyhow::anyhow!("a zero wait still stalled instead of dropping immediately"))?
544 };
545
546 assert!(emitted.is_empty(), "the starved packet must not be emitted");
547 assert_eq!(
548 1,
549 attempts.load(Ordering::Relaxed),
550 "a zero wait must resolve once and give up, not retry"
551 );
552
553 Ok(())
554 }
555
556 #[test_log::test(tokio::test)]
559 async fn a_starved_return_packet_should_give_back_the_surb_its_sender_counted() -> anyhow::Result<()> {
560 let refunds = Arc::new(AtomicU64::new(0));
561 let counted = |marker| {
562 let mut data = packet(marker);
563 data.surb_refund = SurbRefund::to(refunds.clone());
564 data
565 };
566 let (starved, served) = (HoprPseudonym::random(), HoprPseudonym::random());
567 let input = futures::stream::iter(vec![
568 (return_routing(starved), counted(0)),
569 (return_routing(starved), packet(1)),
570 (return_routing(served), counted(2)),
571 ]);
572
573 let emitted = resolve_routing_stage(
574 input,
575 move |_size_hint, _max_surbs, routing: DestinationRouting| async move {
576 match &routing {
577 DestinationRouting::Return(matcher) if matcher.pseudonym() == served => {
578 Ok((resolved(), Some(5), None))
579 }
580 _ => Err(no_surb(&routing)),
581 }
582 },
583 TEST_DISTRESS_THRESHOLD,
584 TEST_CONCURRENCY,
585 surb_resolution_wait(Some(std::time::Duration::ZERO)),
586 )
587 .collect::<Vec<_>>()
588 .timeout(futures_time::time::Duration::from(TEST_TIMEOUT))
589 .await
590 .map_err(|_| anyhow::anyhow!("the stage stalled instead of dropping the starved packets"))?;
591
592 assert_eq!(
593 vec![2],
594 emitted.iter().map(|(_, data)| marker_of(data)).collect::<Vec<_>>(),
595 "only the packet that found its SURB goes on"
596 );
597 assert_eq!(
598 1,
599 refunds.load(Ordering::Relaxed),
600 "only the counted packet that starved gives its SURB back"
601 );
602
603 Ok(())
604 }
605
606 #[test_log::test(tokio::test)]
613 async fn a_return_packet_should_be_emitted_once_its_surbs_arrive() -> anyhow::Result<()> {
614 const FAILURES_BEFORE_SUCCESS: usize = 3;
615
616 let attempts = Arc::new(AtomicUsize::new(0));
617 let input = futures::stream::iter(vec![(return_routing(HoprPseudonym::random()), packet(7))]);
618
619 let emitted = {
620 let attempts = attempts.clone();
621 stage(input, move |_size_hint, _max_surbs, routing: DestinationRouting| {
622 let attempts = attempts.clone();
623 async move {
624 if attempts.fetch_add(1, Ordering::Relaxed) < FAILURES_BEFORE_SUCCESS {
625 Err(no_surb(&routing))
626 } else {
627 Ok((resolved(), Some(0), None))
628 }
629 }
630 })
631 .take(1)
632 .collect::<Vec<_>>()
633 .timeout(futures_time::time::Duration::from(TEST_TIMEOUT))
634 .await
635 .map_err(|_| {
636 anyhow::anyhow!(
637 "a return packet whose SURBs arrived after {FAILURES_BEFORE_SUCCESS} retries was never emitted"
638 )
639 })?
640 };
641
642 assert_eq!(
643 emitted.len(),
644 1,
645 "the return packet must be emitted once its SURBs arrive"
646 );
647 assert_eq!(marker_of(&emitted[0].1), 7);
648 assert!(
649 attempts.load(Ordering::Relaxed) > FAILURES_BEFORE_SUCCESS,
650 "the stage must retry rather than drop on the first SURB error"
651 );
652
653 Ok(())
654 }
655
656 #[test_log::test(tokio::test)]
661 async fn a_hard_resolution_failure_should_drop_only_its_own_packet() -> anyhow::Result<()> {
662 let input = futures::stream::iter(vec![
663 (forward_routing(), packet(0)),
664 (forward_routing(), packet(1)),
665 (forward_routing(), packet(2)),
666 ]);
667
668 let emitted = stage(
669 input,
670 |_size_hint, _max_surbs, _routing: DestinationRouting| async move {
671 static SEEN: AtomicUsize = AtomicUsize::new(0);
672 if SEEN.fetch_add(1, Ordering::Relaxed) == 0 {
673 Err(PathPlannerError::Api("no path".into()))
674 } else {
675 Ok((resolved(), None, None))
676 }
677 },
678 )
679 .collect::<Vec<_>>()
680 .timeout(futures_time::time::Duration::from(TEST_TIMEOUT))
681 .await
682 .map_err(|_| anyhow::anyhow!("a hard resolution failure stalled the stage instead of dropping its packet"))?;
683
684 assert_eq!(
685 emitted.iter().map(|(_, data)| marker_of(data)).collect::<Vec<_>>(),
686 vec![1, 2],
687 "only the unroutable packet is dropped; the rest keep their order"
688 );
689
690 Ok(())
691 }
692
693 #[test_log::test(tokio::test)]
697 async fn resolved_packet_should_carry_the_captured_surb_generation() -> anyhow::Result<()> {
698 const CAPTURED: u8 = 7;
699
700 let input = futures::stream::iter(vec![(forward_routing(), packet(0))]);
701
702 let emitted = stage(input, |_size_hint, _max_surbs, _routing| async move {
703 Ok((resolved(), None, Some(CAPTURED)))
704 })
705 .take(1)
706 .collect::<Vec<_>>()
707 .timeout(futures_time::time::Duration::from(TEST_TIMEOUT))
708 .await
709 .map_err(|_| anyhow::anyhow!("the stage did not emit the packet within {TEST_TIMEOUT:?}"))?;
710
711 let (_, data) = emitted
712 .into_iter()
713 .next()
714 .ok_or_else(|| anyhow::anyhow!("no packet emitted"))?;
715 assert_eq!(
716 data.packet_info.and_then(|info| info.surb_generation),
717 Some(CAPTURED),
718 "the generation captured at resolution must ride on packet_info to the encode stage"
719 );
720
721 Ok(())
722 }
723}