torrentdht 0.1.1

DHT discovery with mTLS handshake handoff; optional BitTorrent when the host opts in
Documentation
use std::collections::VecDeque;
use std::net::SocketAddr;
use std::time::{Duration, Instant};

use crate::dht::{distance, NodeId};

const K: usize = 8;

#[derive(Debug, Clone)]
pub struct NodeEntry {
    pub id: NodeId,
    pub addr: SocketAddr,
    pub last_seen: Instant,
}

impl NodeEntry {
    pub fn new(id: NodeId, addr: SocketAddr) -> Self {
        Self {
            id,
            addr,
            last_seen: Instant::now(),
        }
    }

    pub fn touch(&mut self) {
        self.last_seen = Instant::now();
    }
}

#[derive(Debug)]
struct KBucket {
    live: Vec<NodeEntry>,
    replacements: VecDeque<NodeEntry>,
    last_changed: Instant,
}

impl KBucket {
    fn new() -> Self {
        Self {
            live: Vec::new(),
            replacements: VecDeque::new(),
            last_changed: Instant::now(),
        }
    }

    fn touch_bucket(&mut self) {
        self.last_changed = Instant::now();
    }
}

#[derive(Debug)]
pub struct RoutingTable {
    local_id: NodeId,
    buckets: Vec<KBucket>,
}

impl RoutingTable {
    pub fn new(local_id: NodeId) -> Self {
        Self {
            local_id,
            buckets: (0..160).map(|_| KBucket::new()).collect(),
        }
    }

    pub fn local_id(&self) -> NodeId {
        self.local_id
    }

    pub fn upsert(&mut self, entry: NodeEntry) {
        let bucket_idx = bucket_index(&self.local_id, &entry.id);
        let bucket = &mut self.buckets[bucket_idx];

        if let Some(existing) = bucket.live.iter_mut().find(|node| node.id == entry.id) {
            existing.addr = entry.addr;
            existing.touch();
            bucket.touch_bucket();
            return;
        }
        if let Some(existing) = bucket
            .replacements
            .iter_mut()
            .find(|node| node.id == entry.id)
        {
            existing.addr = entry.addr;
            existing.touch();
            return;
        }

        if bucket.live.len() < K {
            bucket.live.push(entry);
            bucket.touch_bucket();
            return;
        }

        // Full live set: keep candidate in replacement cache (MRU at back).
        bucket.replacements.retain(|node| node.id != entry.id);
        bucket.replacements.push_back(entry);
        while bucket.replacements.len() > K {
            bucket.replacements.pop_front();
        }
    }

    pub fn all_entries(&self) -> Vec<NodeEntry> {
        self.buckets
            .iter()
            .flat_map(|bucket| bucket.live.iter().cloned())
            .collect()
    }

    /// Total live contacts across all buckets.
    pub fn live_node_count(&self) -> usize {
        self.buckets.iter().map(|bucket| bucket.live.len()).sum()
    }

    /// Contacts not seen for longer than `older_than`, oldest first, capped at `limit`.
    pub fn stale_contacts(&self, older_than: Duration, limit: usize) -> Vec<NodeEntry> {
        let mut nodes: Vec<_> = self
            .buckets
            .iter()
            .flat_map(|bucket| bucket.live.iter())
            .filter(|node| node.last_seen.elapsed() > older_than)
            .cloned()
            .collect();
        nodes.sort_by_key(|node| node.last_seen);
        nodes.truncate(limit);
        nodes
    }

    pub fn remove_id(&mut self, id: &NodeId) {
        let bucket_idx = bucket_index(&self.local_id, id);
        let bucket = &mut self.buckets[bucket_idx];
        let before = bucket.live.len();
        bucket.live.retain(|node| node.id != *id);
        bucket.replacements.retain(|node| node.id != *id);
        if bucket.live.len() < before {
            if let Some(promoted) = bucket.replacements.pop_back() {
                bucket.live.push(promoted);
            }
            bucket.touch_bucket();
        }
    }

    /// Bucket indexes idle longer than `idle_for`, preferring emptier / older buckets.
    pub fn buckets_needing_refresh(&self, idle_for: Duration, limit: usize) -> Vec<usize> {
        let mut idxs: Vec<_> = self
            .buckets
            .iter()
            .enumerate()
            .filter(|(_, bucket)| bucket.last_changed.elapsed() > idle_for)
            .map(|(idx, bucket)| (idx, bucket.last_changed, bucket.live.len()))
            .collect();
        idxs.sort_by(|a, b| a.1.cmp(&b.1).then(a.2.cmp(&b.2)));
        idxs.into_iter().map(|(idx, _, _)| idx).take(limit).collect()
    }

    /// Synthesize a target NodeId that falls in `bucket_idx` relative to the local id.
    pub fn refresh_target(&self, bucket_idx: usize) -> NodeId {
        random_id_in_bucket(&self.local_id, bucket_idx.min(159))
    }

    #[cfg(test)]
    pub fn replacement_count(&self, bucket_idx: usize) -> usize {
        self.buckets[bucket_idx].replacements.len()
    }

    #[cfg(test)]
    pub fn live_count(&self, bucket_idx: usize) -> usize {
        self.buckets[bucket_idx].live.len()
    }

    pub fn closest(&self, target: &NodeId, count: usize) -> Vec<NodeEntry> {
        let mut nodes = self.all_entries();
        nodes.sort_by(|a, b| {
            distance(&a.id, target)
                .cmp(&distance(&b.id, target))
                .then_with(|| a.id.cmp(&b.id))
        });
        nodes.truncate(count);
        nodes
    }
}

fn bucket_index(local: &NodeId, node: &NodeId) -> usize {
    let xor = distance(local, node);
    leading_zero_bits(&xor).min(159)
}

fn leading_zero_bits(x: &[u8; 20]) -> usize {
    let mut zeros = 0usize;
    for byte in x {
        if *byte == 0 {
            zeros += 8;
        } else {
            zeros += byte.leading_zeros() as usize;
            break;
        }
    }
    zeros
}

fn random_id_in_bucket(local: &NodeId, bucket_idx: usize) -> NodeId {
    let mut id = *local.as_bytes();
    let byte_idx = bucket_idx / 8;
    let bit_in_byte = 7 - (bucket_idx % 8);
    // Differ at the bucket's distinguishing bit so XOR leading zeros == bucket_idx.
    id[byte_idx] ^= 1 << bit_in_byte;
    // Randomize less-significant bits when entropy is available.
    if let Ok(rand) = crate::net::random_bytes::<20>() {
        for (idx, byte) in id.iter_mut().enumerate().skip(byte_idx) {
            if idx == byte_idx {
                let keep_mask = !((1u8 << bit_in_byte) - 1);
                *byte = (*byte & keep_mask) | (rand[idx] & !keep_mask);
            } else {
                *byte = rand[idx];
            }
        }
    }
    NodeId::from_bytes(id)
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::net::{Ipv4Addr, SocketAddrV4};

    fn addr() -> SocketAddr {
        SocketAddr::V4(SocketAddrV4::new(Ipv4Addr::LOCALHOST, 6881))
    }

    #[test]
    fn keeps_closest_nodes() {
        let local = NodeId::from_bytes([0; 20]);
        let mut table = RoutingTable::new(local);
        for idx in 1..=4u8 {
            let mut id = [0u8; 20];
            id[19] = idx;
            table.upsert(NodeEntry::new(NodeId::from_bytes(id), addr()));
        }
        let target = NodeId::from_bytes([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]);
        let closest = table.closest(&target, 2);
        assert_eq!(closest.len(), 2);
    }

    #[test]
    fn full_bucket_keeps_replacements_and_promotes() {
        let local = NodeId::from_bytes([0; 20]);
        let mut table = RoutingTable::new(local);
        // All these share the same high-distance bucket relative to zero local id
        // when only the last byte differs among small values — they land in bucket 152+.
        // Force same bucket by using ids that only differ in low bits after a shared prefix.
        let mut ids = Vec::new();
        for i in 0..(K + 3) {
            let mut id = [0u8; 20];
            id[0] = 0x80; // MSB set → XOR leading zeros = 0 → bucket 0
            id[19] = i as u8;
            ids.push(NodeId::from_bytes(id));
            table.upsert(NodeEntry::new(NodeId::from_bytes(id), addr()));
        }
        assert_eq!(table.live_count(0), K);
        assert_eq!(table.replacement_count(0), 3);

        let evict = ids[0];
        table.remove_id(&evict);
        assert_eq!(table.live_count(0), K);
        assert_eq!(table.replacement_count(0), 2);
        assert!(!table.all_entries().iter().any(|e| e.id == evict));
    }

    #[test]
    fn refresh_target_lands_in_bucket() {
        let local = NodeId::from_bytes([0; 20]);
        let table = RoutingTable::new(local);
        for bucket in [0usize, 7, 40, 159] {
            let target = table.refresh_target(bucket);
            assert_eq!(bucket_index(&local, &target), bucket);
        }
    }
}