path: root/src/swarm/links.rs

//! How members are linked, for a map of the swarm (the dashboard, `api::dashboard`): a
//! node asks a member with LINKS, and the member answers with a LINKS_REPLY listing its
//! neighbours, each with the transport its messages go over, whether only through a
//! relay, the round trip and whether the neighbour is dormant: as the member measures
//! them, which no other node can.
//!
//! Every node answers, whatever its build: one with a dashboard asks any member, which
//! may have none. Only members (in the member list) are answered, as the links name
//! members and where they're reached; and each at most every `ANSWER_EVERY`. Nothing
//! is written to the document: asked for while someone looks, forgotten after.
//!
//! A LINKS may subscribe (`subscribe_secs`): the member then sends a LINKS_REPLY again
//! whenever its links change (`changed`: a peer, a transport, relayed, dormant, or a
//! round trip that moved by a fifth), looked at every `WATCH_EVERY`, until the
//! subscription runs out (the asker renews it with its next LINKS, so one that is gone
//! stops it by not renewing) or a LINKS with 0 ends it.

use std::collections::HashMap;
use std::sync::Mutex;
use std::time::Duration;

use tokio::time::Instant;
use tracing::debug;

use crate::locks::MutexExt;
use crate::state::AppState;
use crate::swarm::{members, topology};
use crate::transport::{
    Connection, Destination, Link, LinksReply, LinksRequest, OtherPath, ParsedMessage,
};

/// Links one reply lists at most (a member has about `--neighbours`, more if others
/// prefer it).
pub(crate) const MAX_LINKS: usize = 256;
/// Other transports in a link at most.
pub(crate) const MAX_OTHERS: usize = 8;
/// A member answers each other one at most this often.
const ANSWER_EVERY: Duration = Duration::from_secs(5);
/// Replies kept from members at most (one each), and requests out.
const MAX_KEPT: usize = 4096;
/// Subscriptions a member keeps at most, and how long one lasts at most.
const MAX_SUBSCRIBERS: usize = 64;
const MAX_SUBSCRIPTION: Duration = Duration::from_secs(300);
/// How often a member with subscribers looks whether its links changed.
const WATCH_EVERY: Duration = Duration::from_secs(2);
/// A reply to a LINKS that doesn't subscribe is taken for this long.
const REPLY_WITHIN: Duration = Duration::from_secs(30);

/// The requests out and the replies in, and when each asker was last answered.
#[derive(Default)]
pub(crate) struct Links {
    inner: Mutex<Inner>,
}

#[derive(Default)]
struct Inner {
    /// Our LINKS out, by member: its nonce, and until when replies to it are taken (its
    /// subscription's end, or `REPLY_WITHIN`).
    asked: HashMap<String, (u64, Instant)>,
    /// The latest LINKS_REPLY of each member: when, and its links.
    replies: HashMap<String, (Instant, Vec<Link>)>,
    /// When we last answered each member.
    answered: HashMap<String, Instant>,
    /// Who subscribed to our links: the nonce to answer with, and until when.
    subscribers: HashMap<String, (u64, Instant)>,
    /// The links subscribers were last sent (`watch`).
    published: Option<Vec<Link>>,
}

impl Links {
    /// The latest links each member replied with, and how long ago.
    #[cfg_attr(not(feature = "dashboard"), allow(dead_code))]
    pub(crate) fn replies(&self) -> Vec<(String, Duration, Vec<Link>)> {
        let now = Instant::now();
        self.inner
            .lock_or_recover()
            .replies
            .iter()
            .map(|(member, (at, links))| {
                (
                    member.clone(),
                    now.saturating_duration_since(*at),
                    links.clone(),
                )
            })
            .collect()
    }

    /// The members our subscriptions are with (not run out).
    #[cfg_attr(not(feature = "dashboard"), allow(dead_code))]
    pub(crate) fn subscribed(&self) -> Vec<String> {
        let now = Instant::now();
        self.inner
            .lock_or_recover()
            .asked
            .iter()
            .filter(|(_, (_, until))| now < *until)
            .map(|(member, _)| member.clone())
            .collect()
    }
}

/// This node's links: its neighbours, as it measures them.
pub(crate) async fn own_links(state: &AppState) -> Vec<Link> {
    let mut links = Vec::new();
    for (peer, peer_state) in state.peers_snapshot().await {
        if !topology::is_neighbour(state, &peer) {
            continue;
        }
        let dormant = peer_state.lock().await.liveness.is_dormant();
        let destination = state.transport.destination(&peer);
        let transport = destination
            .as_ref()
            .and_then(|destination| scheme_of(&destination.address));
        links.push(Link {
            others: others(destination.as_ref(), transport.as_deref()),
            transport,
            relayed: destination
                .as_ref()
                .is_some_and(|destination| destination.connection == Some(Connection::Relayed)),
            // The path in use's (`Transport::rtt`, the first of `destination.paths`).
            rtt_us: state
                .transport
                .rtt(&peer)
                .map(|rtt| u32::try_from(rtt.as_micros()).unwrap_or(u32::MAX)),
            dormant,
            peer,
        });
    }
    links.sort_by(|a, b| a.peer.cmp(&b.peer));
    links.truncate(MAX_LINKS);
    links
}

/// The scheme of `address` (`mycelium:…`): its transport.
fn scheme_of(address: &str) -> Option<String> {
    address.split_once(':').map(|(scheme, _)| scheme.to_owned())
}

/// The transports besides `used` the peer proved itself at, with a path up: each with
/// the round trip of its fastest path, if any is measured, and whether all of them go
/// through a relay.
fn others(destination: Option<&Destination>, used: Option<&str>) -> Vec<OtherPath> {
    let mut others: Vec<OtherPath> = Vec::new();
    for path in destination.map_or(&[][..], |destination| &destination.paths[..]) {
        let Some(transport) = scheme_of(&path.address) else {
            continue;
        };
        if path.down || used == Some(transport.as_str()) {
            continue;
        }
        let rtt_us = path
            .rtt_ms
            .filter(|ms| ms.is_finite() && *ms >= 0.0)
            .map(|ms| (ms * 1000.0).min(f64::from(u32::MAX)) as u32);
        let relayed = path.connection == Some(Connection::Relayed);
        match others.iter_mut().find(|other| other.transport == transport) {
            Some(other) => {
                other.rtt_us = match (other.rtt_us, rtt_us) {
                    (Some(a), Some(b)) => Some(a.min(b)),
                    (a, b) => a.or(b),
                };
                other.relayed &= relayed;
            }
            None => others.push(OtherPath {
                transport,
                rtt_us,
                relayed,
            }),
        }
    }
    others.sort_by(|a, b| a.transport.cmp(&b.transport));
    others.truncate(MAX_OTHERS);
    others
}

/// Asks `member` for its links (a LINKS), and with `subscribe` for its changes for
/// that long; its replies land in `AppState::links`.
#[cfg_attr(not(feature = "dashboard"), allow(dead_code))]
pub(crate) async fn ask(state: &AppState, member: &str, subscribe: Duration) {
    let nonce = crate::transport::paths::random_nonce();
    {
        let mut inner = state.links.inner.lock_or_recover();
        if inner.asked.len() >= MAX_KEPT && !inner.asked.contains_key(member) {
            inner.asked.clear();
        }
        let until = Instant::now() + subscribe.max(REPLY_WITHIN);
        inner.asked.insert(member.to_owned(), (nonce, until));
    }
    let (epoch, epoch_seq) = state.epoch_stamp();
    let request = ParsedMessage::Links(LinksRequest {
        epoch,
        epoch_seq,
        nonce,
        subscribe_secs: u32::try_from(subscribe.as_secs()).unwrap_or(u32::MAX),
    });
    if let Err(error) = state.transport.send_message(member, &request).await {
        debug!(member = %member, error = %format!("{error:#}"), "LINKS failed");
    }
}

/// Ends our subscription with `member` (a LINKS with 0); its replies aren't taken any
/// more.
#[cfg_attr(not(feature = "dashboard"), allow(dead_code))]
pub(crate) async fn unsubscribe(state: &AppState, member: &str) {
    let nonce = {
        let mut inner = state.links.inner.lock_or_recover();
        match inner.asked.remove(member) {
            Some((nonce, _)) => nonce,
            None => return,
        }
    };
    let (epoch, epoch_seq) = state.epoch_stamp();
    let request = ParsedMessage::Links(LinksRequest {
        epoch,
        epoch_seq,
        nonce,
        subscribe_secs: 0,
    });
    if let Err(error) = state.transport.send_message(member, &request).await {
        debug!(member = %member, error = %format!("{error:#}"), "LINKS failed");
    }
}

/// A LINKS from `peer`: answered if it's a member, and not answered lately.
pub(crate) async fn answer(state: &AppState, peer: &str, request: LinksRequest) {
    let member = {
        let replica = state.doc.read().await;
        members::members(&replica.doc)
            .iter()
            .any(|member| member == peer)
    };
    if !member {
        debug!(peer = %peer, "Not answering LINKS from a peer that isn't a member");
        return;
    }
    {
        let now = Instant::now();
        let mut inner = state.links.inner.lock_or_recover();
        // A subscription is taken, renewed or ended even when the reply is due later.
        if request.subscribe_secs == 0 {
            inner.subscribers.remove(peer);
        } else if inner.subscribers.len() < MAX_SUBSCRIBERS || inner.subscribers.contains_key(peer)
        {
            let lasts =
                Duration::from_secs(u64::from(request.subscribe_secs)).min(MAX_SUBSCRIPTION);
            inner
                .subscribers
                .insert(peer.to_owned(), (request.nonce, now + lasts));
        }
        if inner
            .answered
            .get(peer)
            .is_some_and(|at| now.saturating_duration_since(*at) < ANSWER_EVERY)
        {
            return;
        }
        if inner.answered.len() >= MAX_KEPT {
            inner
                .answered
                .retain(|_, at| now.saturating_duration_since(*at) < ANSWER_EVERY);
        }
        inner.answered.insert(peer.to_owned(), now);
    }
    let (epoch, epoch_seq) = state.epoch_stamp();
    let reply = ParsedMessage::LinksReply(LinksReply {
        epoch,
        epoch_seq,
        nonce: request.nonce,
        links: own_links(state).await,
    });
    if let Err(error) = state.transport.send_message(peer, &reply).await {
        debug!(peer = %peer, error = %format!("{error:#}"), "LINKS_REPLY failed");
    }
}

/// A LINKS_REPLY from `peer`: kept if it answers our latest LINKS to it, while its
/// replies are taken (a subscription's go on).
pub(crate) fn received(state: &AppState, peer: &str, mut reply: LinksReply) {
    let mut inner = state.links.inner.lock_or_recover();
    let taken = inner
        .asked
        .get(peer)
        .is_some_and(|(nonce, until)| *nonce == reply.nonce && Instant::now() < *until);
    if !taken {
        return;
    }
    reply.links.truncate(MAX_LINKS);
    for link in &mut reply.links {
        link.others.truncate(MAX_OTHERS);
    }
    if inner.replies.len() >= MAX_KEPT && !inner.replies.contains_key(peer) {
        inner.replies.clear();
    }
    inner
        .replies
        .insert(peer.to_owned(), (Instant::now(), reply.links));
}

/// For subscribers (`answer`): every `WATCH_EVERY`, while there are any, this node's
/// links; sent to each of them when they changed since they were last sent. Runs for
/// the node's life.
pub(crate) async fn watch(state: AppState) {
    let mut every = tokio::time::interval(WATCH_EVERY);
    every.set_missed_tick_behavior(tokio::time::MissedTickBehavior::Delay);
    loop {
        every.tick().await;
        let subscribers: Vec<(String, u64)> = {
            let now = Instant::now();
            let mut inner = state.links.inner.lock_or_recover();
            inner.subscribers.retain(|_, (_, until)| now < *until);
            if inner.subscribers.is_empty() {
                inner.published = None;
                continue;
            }
            inner
                .subscribers
                .iter()
                .map(|(peer, (nonce, _))| (peer.clone(), *nonce))
                .collect()
        };
        let links = own_links(&state).await;
        {
            let mut inner = state.links.inner.lock_or_recover();
            if inner
                .published
                .as_ref()
                .is_some_and(|published| !changed(published, &links))
            {
                continue;
            }
            inner.published = Some(links.clone());
        }
        let (epoch, epoch_seq) = state.epoch_stamp();
        for (peer, nonce) in subscribers {
            let reply = ParsedMessage::LinksReply(LinksReply {
                epoch,
                epoch_seq,
                nonce,
                links: links.clone(),
            });
            if let Err(error) = state.transport.send_message(&peer, &reply).await {
                debug!(peer = %peer, error = %format!("{error:#}"), "LINKS_REPLY failed");
            }
        }
    }
}

/// Whether `new` says something `old` didn't: another peer, transport, relay or
/// dormancy, or a round trip measured or moved by more than a fifth (and 1 ms). Round
/// trips wobble; small moves aren't news.
fn changed(old: &[Link], new: &[Link]) -> bool {
    let moved = |a: Option<u32>, b: Option<u32>| match (a, b) {
        (Some(a), Some(b)) => {
            let by = a.abs_diff(b);
            by > 1000 && by > a.max(b) / 5
        }
        (a, b) => a.is_some() != b.is_some(),
    };
    old.len() != new.len()
        || old.iter().zip(new).any(|(a, b)| {
            a.peer != b.peer
                || a.transport != b.transport
                || a.relayed != b.relayed
                || a.dormant != b.dormant
                || moved(a.rtt_us, b.rtt_us)
                || a.others.len() != b.others.len()
                || a.others.iter().zip(&b.others).any(|(x, y)| {
                    x.transport != y.transport
                        || x.relayed != y.relayed
                        || moved(x.rtt_us, y.rtt_us)
                })
        })
}

#[cfg(test)]
mod tests {
    use super::*;

    fn link(peer: &str, rtt_us: Option<u32>) -> Link {
        Link {
            peer: peer.into(),
            transport: Some("libp2p".into()),
            relayed: false,
            rtt_us,
            dormant: false,
            others: Vec::new(),
        }
    }

    #[test]
    fn only_news_is_a_change() {
        let old = [link("a", Some(10_000))];
        assert!(!changed(&old, &[link("a", Some(11_000))]));
        assert!(changed(&old, &[link("a", Some(13_000))]));
        assert!(changed(&old, &[link("a", None)]));
        assert!(changed(&old, &[link("b", Some(10_000))]));
        assert!(changed(&old, &[]));
        let mut dormant = link("a", Some(10_000));
        dormant.dormant = true;
        assert!(changed(&old, &[dormant]));
        // Small round trips: a millisecond's wobble isn't news.
        assert!(!changed(&[link("a", Some(400))], &[link("a", Some(1_300))]));
    }
}