use std::collections::HashSet;
use std::future::Future;
use std::net::SocketAddr;
use std::pin::Pin;
use std::sync::Arc;
use std::time::Duration;
use futures::StreamExt;
use futures::stream::FuturesUnordered;
use tracing::{debug, warn};
use super::client::extract_compact_nodes_from_response;
use super::client::extract_compact_peers_from_response;
use super::message::{DhtMessage, DhtMessageBuilder};
use super::node::DhtNode;
use super::routing_table::RoutingTable;
use super::socket::DhtSocket;
use super::tracker::{QueryType, TrackedResponse, TransactionTracker};
const K: usize = 8;
const ALPHA: usize = 3;
const MAX_ROUNDS: usize = 20;
struct LookupResponse {
response: Option<TrackedResponse>,
node_id: [u8; 20],
}
type LookupPendingResponse = Pin<Box<dyn Future<Output = LookupResponse> + Send>>;
#[derive(Debug, Clone)]
struct LookupEntry {
node_id: [u8; 20],
addr: SocketAddr,
used: bool,
}
struct LookupRequest<'a> {
target: &'a [u8; 20],
self_id: &'a [u8; 20],
info_hash: Option<[u8; 20]>,
socket: &'a DhtSocket,
tracker: &'a Arc<TransactionTracker>,
query_type: QueryType,
query_timeout: Duration,
}
impl LookupEntry {
#[allow(dead_code)]
fn distance_to(&self, target: &[u8; 20]) -> [u8; 20] {
let mut dist = [0u8; 20];
for i in 0..20 {
dist[i] = self.node_id[i] ^ target[i];
}
dist
}
}
#[derive(Debug, Clone)]
pub struct NodeLookupResult {
pub closest_nodes: Vec<DhtNode>,
pub nodes_contacted: usize,
}
#[derive(Debug, Clone)]
pub struct PeerLookupResult {
pub peers: Vec<SocketAddr>,
pub token_nodes: Vec<(SocketAddr, [u8; 20], Vec<u8>)>,
pub nodes_contacted: usize,
}
pub async fn iterative_find_node(
target: &[u8; 20],
self_id: &[u8; 20],
routing_table: &Arc<tokio::sync::RwLock<RoutingTable>>,
socket: &DhtSocket,
tracker: &Arc<TransactionTracker>,
query_timeout: Duration,
) -> NodeLookupResult {
let mut entries = initialize_entries(target, routing_table).await;
let mut pending = FuturesUnordered::<LookupPendingResponse>::new();
let mut nodes_contacted = 0usize;
let mut rounds = 0usize;
let request = LookupRequest {
target,
self_id,
info_hash: None,
socket,
tracker,
query_type: QueryType::FindNode,
query_timeout,
};
send_batch(&request, &mut entries, &mut pending).await;
while !pending.is_empty() && rounds < MAX_ROUNDS {
rounds += 1;
if let Some(result) = pending.next().await {
if let Some(response) = result.response {
let from = response.from;
let message = response.message;
nodes_contacted += 1;
mark_node_good(&from, &message, routing_table).await;
let new_nodes = extract_compact_nodes_from_response(&message);
for (addr, nid) in new_nodes {
let new_node = DhtNode::new(nid, addr);
add_node_to_table(routing_table, new_node).await;
insert_entry(&mut entries, nid, addr, target);
}
sort_and_dedup(&mut entries, target);
} else {
mark_node_bad(&result.node_id, routing_table).await;
}
}
send_batch(&request, &mut entries, &mut pending).await;
}
let closest_nodes: Vec<DhtNode> = entries
.iter()
.take(K)
.map(|e| DhtNode::new(e.node_id, e.addr))
.collect();
NodeLookupResult {
closest_nodes,
nodes_contacted,
}
}
pub async fn iterative_get_peers(
info_hash: &[u8; 20],
self_id: &[u8; 20],
routing_table: &Arc<tokio::sync::RwLock<RoutingTable>>,
socket: &DhtSocket,
tracker: &Arc<TransactionTracker>,
query_timeout: Duration,
) -> PeerLookupResult {
let mut entries = initialize_entries(info_hash, routing_table).await;
let mut pending = FuturesUnordered::<LookupPendingResponse>::new();
let mut nodes_contacted = 0usize;
let mut all_peers: Vec<SocketAddr> = Vec::new();
let mut token_nodes: Vec<(SocketAddr, [u8; 20], Vec<u8>)> = Vec::new();
let mut rounds = 0usize;
let request = LookupRequest {
target: info_hash,
self_id,
info_hash: Some(*info_hash),
socket,
tracker,
query_type: QueryType::GetPeers,
query_timeout,
};
send_batch(&request, &mut entries, &mut pending).await;
while !pending.is_empty() && rounds < MAX_ROUNDS {
rounds += 1;
if let Some(result) = pending.next().await {
if let Some(response) = result.response {
let from = response.from;
let message = response.message;
nodes_contacted += 1;
mark_node_good(&from, &message, routing_table).await;
let peers = extract_compact_peers_from_response(&message);
if !peers.is_empty() {
all_peers.extend(peers);
}
if let Some(r) = &message.r
&& let Some(token_val) = r.dict_get(b"token").and_then(|v| v.as_bytes())
{
let node_id = entries
.iter()
.find(|e| e.addr == from)
.map(|e| e.node_id)
.unwrap_or([0u8; 20]);
token_nodes.push((from, node_id, token_val.to_vec()));
}
let new_nodes = extract_compact_nodes_from_response(&message);
for (addr, nid) in new_nodes {
let new_node = DhtNode::new(nid, addr);
add_node_to_table(routing_table, new_node).await;
insert_entry(&mut entries, nid, addr, info_hash);
}
sort_and_dedup(&mut entries, info_hash);
} else {
mark_node_bad(&result.node_id, routing_table).await;
}
}
send_batch(&request, &mut entries, &mut pending).await;
}
all_peers.sort();
all_peers.dedup();
token_nodes.sort_by(|a, b| {
let dist_a = xor_distance(&a.1, info_hash);
let dist_b = xor_distance(&b.1, info_hash);
dist_a.cmp(&dist_b)
});
token_nodes.truncate(K);
PeerLookupResult {
peers: all_peers,
token_nodes,
nodes_contacted,
}
}
pub async fn announce_to_token_nodes(
info_hash: &[u8; 20],
self_id: &[u8; 20],
port: u16,
token_nodes: &[(SocketAddr, [u8; 20], Vec<u8>)],
socket: &DhtSocket,
tracker: &Arc<TransactionTracker>,
query_timeout: Duration,
) -> usize {
let mut sends = FuturesUnordered::new();
for (addr, node_id, token) in token_nodes.iter().take(K) {
let token_str = match std::str::from_utf8(token) {
Ok(s) => s.to_string(),
Err(_) => hex::encode(token),
};
let (transaction_id, response_wait) = tracker.allocate_wait(
QueryType::AnnouncePeer,
*addr,
Some(*node_id),
Some(*info_hash),
query_timeout,
);
let msg =
DhtMessageBuilder::announce_peer(transaction_id, self_id, info_hash, port, &token_str);
let encoded = match msg.encode() {
Ok(e) => e,
Err(e) => {
warn!("Failed to encode announce_peer: {}", e);
continue;
}
};
let socket = socket.clone();
let addr = *addr;
sends.push(async move {
if let Err(e) = socket.send_to(addr, &encoded).await {
debug!(addr = %addr, "Failed to send announce_peer: {}", e);
return false;
}
let _ = response_wait.wait(query_timeout).await;
true
});
}
let mut announced = 0usize;
while let Some(sent) = sends.next().await {
if sent {
announced += 1;
}
}
announced
}
async fn initialize_entries(
target: &[u8; 20],
routing_table: &Arc<tokio::sync::RwLock<RoutingTable>>,
) -> Vec<LookupEntry> {
let rt = routing_table.read().await;
rt.find_closest(target, K)
.into_iter()
.map(|n| LookupEntry {
node_id: n.id,
addr: n.addr,
used: false,
})
.collect()
}
async fn send_batch(
request: &LookupRequest<'_>,
entries: &mut [LookupEntry],
pending: &mut FuturesUnordered<LookupPendingResponse>,
) {
let to_send = ALPHA.saturating_sub(pending.len());
if to_send == 0 {
return;
}
let mut sends = FuturesUnordered::new();
for (entry_index, entry) in entries.iter().enumerate() {
if entry.used {
continue;
}
if sends.len() >= to_send {
break;
}
let (transaction_id, response_wait) = request.tracker.allocate_wait(
request.query_type,
entry.addr,
Some(entry.node_id),
request.info_hash,
request.query_timeout,
);
let query_timeout = request.query_timeout;
let node_id = entry.node_id;
let wait_for_response = Box::pin(async move {
LookupResponse {
response: response_wait.wait(query_timeout).await,
node_id,
}
});
let msg = match request.query_type {
QueryType::FindNode => {
DhtMessageBuilder::find_node(transaction_id, request.self_id, request.target)
}
QueryType::GetPeers => {
DhtMessageBuilder::get_peers(transaction_id, request.self_id, request.target)
}
_ => unreachable!("lookup batches only contain find_node or get_peers"),
};
let encoded = match msg.encode() {
Ok(e) => e,
Err(_) => {
continue;
}
};
let socket = request.socket.clone();
let addr = entry.addr;
sends.push(async move {
if socket.send_to(addr, &encoded).await.is_ok() {
Some((entry_index, wait_for_response))
} else {
None
}
});
}
while let Some(result) = sends.next().await {
if let Some((entry_index, wait_for_response)) = result {
entries[entry_index].used = true;
pending.push(wait_for_response);
}
}
}
fn insert_entry(
entries: &mut Vec<LookupEntry>,
node_id: [u8; 20],
addr: SocketAddr,
target: &[u8; 20],
) {
if entries.iter().any(|e| e.node_id == node_id) {
return;
}
entries.push(LookupEntry {
node_id,
addr,
used: false,
});
if entries.len() > K * 2 {
sort_and_dedup(entries, target);
entries.truncate(K * 2);
}
}
fn sort_and_dedup(entries: &mut Vec<LookupEntry>, target: &[u8; 20]) {
entries.sort_by(|a, b| {
let da = xor_distance(&a.node_id, target);
let db = xor_distance(&b.node_id, target);
da.cmp(&db)
});
let mut seen = HashSet::new();
entries.retain(|e| seen.insert(e.node_id));
}
fn xor_distance(a: &[u8; 20], b: &[u8; 20]) -> [u8; 20] {
let mut dist = [0u8; 20];
for i in 0..20 {
dist[i] = a[i] ^ b[i];
}
dist
}
async fn mark_node_good(
addr: &SocketAddr,
message: &DhtMessage,
routing_table: &Arc<tokio::sync::RwLock<RoutingTable>>,
) {
let Some(node_id) = message
.r
.as_ref()
.and_then(|result| result.dict_get(b"id"))
.and_then(|id| id.as_bytes())
.filter(|id| id.len() == 20)
.map(|id| {
let mut node_id = [0u8; 20];
node_id.copy_from_slice(id);
node_id
})
else {
return;
};
let mut rt = routing_table.write().await;
rt.mark_good(&node_id);
rt.insert(DhtNode::new(node_id, *addr));
}
async fn mark_node_bad(node_id: &[u8; 20], routing_table: &Arc<tokio::sync::RwLock<RoutingTable>>) {
let mut rt = routing_table.write().await;
rt.mark_bad(node_id);
}
async fn add_node_to_table(routing_table: &Arc<tokio::sync::RwLock<RoutingTable>>, node: DhtNode) {
let mut rt = routing_table.write().await;
rt.insert(node);
}