use tracing::debug;
use super::bucket::Bucket;
use super::bucket_tree::{
BucketTreeNode, enumerate_buckets, find_bucket_for, find_bucket_for_mut, find_closest_k_nodes,
find_tree_node_for_mut,
};
use super::node::DhtNode;
pub struct RoutingTable {
root: BucketTreeNode,
self_id: [u8; 20],
num_buckets: usize,
}
impl RoutingTable {
pub fn new(self_id: [u8; 20]) -> Self {
let local_node = DhtNode::new(self_id, "0.0.0.0:0".parse().unwrap());
let bucket = Bucket::new(&local_node);
let root = BucketTreeNode::new_leaf(bucket);
Self {
root,
self_id,
num_buckets: 1,
}
}
pub fn insert(&mut self, node: DhtNode) {
if node.id == self.self_id {
return;
}
let node_id = node.id;
let mut node = node;
loop {
let leaf = find_tree_node_for_mut(&mut self.root, &node_id);
node = match leaf {
BucketTreeNode::Leaf { bucket } => match bucket.try_add_node(node) {
Ok(()) => {
debug!(
id = %hex::encode(node_id),
"Added DHT node to routing table"
);
return;
}
Err(node) => node,
},
BucketTreeNode::Internal { .. } => {
debug!(
id = %hex::encode(node_id),
"Unexpected internal node in insert()"
);
return;
}
};
let split_allowed = match leaf {
BucketTreeNode::Leaf { bucket } => bucket.split_allowed(),
BucketTreeNode::Internal { .. } => unreachable!("leaf lookup returned a branch"),
};
if split_allowed {
let prefix_length = match leaf {
BucketTreeNode::Leaf { bucket } => bucket.prefix_length(),
BucketTreeNode::Internal { .. } => {
unreachable!("leaf lookup returned a branch")
}
};
debug!(
"Splitting bucket (prefix={}) to add node {}",
prefix_length,
hex::encode(node_id),
);
leaf.split(&self.self_id);
self.num_buckets += 1;
continue;
}
if let BucketTreeNode::Leaf { bucket } = leaf
&& node.is_good()
{
bucket.cache_node(node);
}
debug!(
id = %hex::encode(node_id),
"Cached DHT node (bucket full, split not allowed)"
);
return;
}
}
pub fn remove(&mut self, node_id: &[u8; 20]) -> bool {
let bucket = find_bucket_for_mut(&mut self.root, node_id);
bucket.drop_node(node_id)
}
pub fn replace_node(&mut self, node_id: &[u8; 20], replacement: DhtNode) -> bool {
let bucket = find_bucket_for_mut(&mut self.root, node_id);
if !bucket.nodes().iter().any(|node| &node.id == node_id)
|| !bucket
.cached_nodes()
.iter()
.any(|node| node.id == replacement.id)
{
return false;
}
bucket.remove_cached_node(&replacement.id);
bucket.replace_node(node_id, replacement)
}
pub(crate) fn replace_node_identity(
&mut self,
old_node_id: &[u8; 20],
replacement: DhtNode,
) -> bool {
let old_bucket = find_bucket_for(&self.root, old_node_id);
if !old_bucket
.nodes()
.iter()
.any(|node| &node.id == old_node_id)
|| !replacement.is_good()
{
return false;
}
if old_node_id == replacement.id() {
return self.mark_good(old_node_id);
}
let replacement_id = *replacement.id();
self.remove(old_node_id);
self.root.for_each_bucket_mut(&mut |bucket| {
bucket.remove_cached_node(&replacement_id);
});
self.insert(replacement);
true
}
pub fn find_closest(&self, target: &[u8; 20], count: usize) -> Vec<DhtNode> {
let mut nodes = find_closest_k_nodes(&self.root, target);
nodes.truncate(count);
nodes
}
pub fn get_bucket_for(&self, node_id: &[u8; 20]) -> &Bucket {
find_bucket_for(&self.root, node_id)
}
pub fn get_all_buckets(&self) -> Vec<&Bucket> {
let mut buckets = Vec::new();
enumerate_buckets(&self.root, &mut buckets);
buckets
}
pub fn total_node_count(&self) -> usize {
self.get_all_buckets().iter().map(|b| b.count_node()).sum()
}
pub fn good_node_count(&self) -> usize {
self.get_all_buckets()
.iter()
.map(|b| b.good_node_count())
.sum()
}
pub fn num_buckets(&self) -> usize {
self.num_buckets
}
pub fn evict_bad_nodes(&mut self) -> usize {
let mut total = 0;
self.root.for_each_bucket_mut(&mut |bucket| {
total += bucket.evict_bad();
});
total
}
pub fn mark_good(&mut self, node_id: &[u8; 20]) -> bool {
let bucket = find_bucket_for_mut(&mut self.root, node_id);
bucket.mark_good(node_id)
}
pub fn mark_bad(&mut self, node_id: &[u8; 20]) -> bool {
let bucket = find_bucket_for_mut(&mut self.root, node_id);
bucket.mark_bad(node_id)
}
pub fn get_random_node(&self) -> Option<&DhtNode> {
use rand::Rng;
use rand::seq::SliceRandom;
let buckets = self.get_all_buckets();
let non_empty: Vec<_> = buckets.iter().filter(|b| b.count_node() > 0).collect();
if non_empty.is_empty() {
return None;
}
let mut rng = rand::thread_rng();
let bucket = non_empty.choose(&mut rng)?;
let nodes = bucket.nodes();
if nodes.is_empty() {
return None;
}
let idx = rng.gen_range(0..nodes.len());
Some(&nodes[idx])
}
pub fn questionable_node_count(&self) -> usize {
self.get_all_buckets()
.iter()
.map(|b| b.questionable_count())
.sum()
}
pub fn bad_node_count(&self) -> usize {
self.get_all_buckets().iter().map(|b| b.bad_count()).sum()
}
pub fn refresh_buckets(&self) -> Vec<[u8; 20]> {
self.get_all_buckets()
.iter()
.filter(|b| b.needs_refresh())
.map(|b| b.get_random_node_id())
.collect()
}
pub fn collect_good_nodes(&self) -> Vec<DhtNode> {
let mut nodes = Vec::new();
for bucket in self.get_all_buckets() {
for node in bucket.nodes() {
if node.is_good() {
nodes.push(node.clone());
}
}
}
nodes
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::SocketAddr;
fn make_addr(port: u16) -> SocketAddr {
format!("127.0.0.1:{}", port).parse().unwrap()
}
#[test]
fn test_routing_table_creation() {
let table = RoutingTable::new([0u8; 20]);
assert_eq!(table.total_node_count(), 0);
assert_eq!(table.num_buckets(), 1);
}
#[test]
fn test_insert_and_find() {
let mut table = RoutingTable::new([0x80u8; 20]);
let node = DhtNode::new([0xFFu8; 20], make_addr(6881));
table.insert(node);
assert_eq!(table.total_node_count(), 1);
let target = [0xFFu8; 20];
let closest = table.find_closest(&target, 5);
assert_eq!(closest.len(), 1);
}
#[test]
fn bucket_lookup_returns_a_covering_leaf_for_any_id_range() {
let mut table = RoutingTable::new([0u8; 20]);
for i in 1..=super::super::bucket::K as u8 {
table.insert(DhtNode::new([i; 20], make_addr(6881 + i as u16)));
}
table.insert(DhtNode::new([0x80; 20], make_addr(6999)));
let low_id = [0u8; 20];
let high_id = [0xFF; 20];
assert!(table.get_bucket_for(&low_id).is_in_range(&low_id));
assert!(table.get_bucket_for(&high_id).is_in_range(&high_id));
}
#[test]
fn test_remove_node() {
let mut table = RoutingTable::new([0u8; 20]);
let id = [1u8; 20];
table.insert(DhtNode::new(id, make_addr(6881)));
assert_eq!(table.total_node_count(), 1);
assert!(table.remove(&id));
assert_eq!(table.total_node_count(), 0);
}
#[test]
fn test_bucket_split_on_insert() {
let mut table = RoutingTable::new([0u8; 20]);
for i in 1..=super::super::bucket::K as u8 {
let node = DhtNode::new([i; 20], make_addr(6881 + i as u16));
table.insert(node);
}
assert_eq!(table.total_node_count(), super::super::bucket::K);
let extra = DhtNode::new([0x80u8; 20], make_addr(9999));
table.insert(extra);
assert!(table.total_node_count() >= super::super::bucket::K);
}
#[test]
fn bucket_split_preserves_discovered_node_verification_state() {
let mut table = RoutingTable::new([0u8; 20]);
for i in 1..=super::super::bucket::K as u8 {
table.insert(DhtNode::new([i; 20], make_addr(6881 + i as u16)));
}
table.insert(DhtNode::unverified([0x80u8; 20], make_addr(9999)));
assert_eq!(table.total_node_count(), super::super::bucket::K + 1);
assert_eq!(
table.good_node_count(),
super::super::bucket::K,
"inserting across a bucket split must not promote an unverified node"
);
}
#[test]
fn test_mark_good() {
let mut table = RoutingTable::new([0u8; 20]);
let id = [1u8; 20];
let mut node = DhtNode::new(id, make_addr(6881));
node.record_failure();
node.record_failure();
table.insert(node);
assert!(table.mark_good(&id));
}
#[test]
fn test_mark_bad() {
let mut table = RoutingTable::new([0u8; 20]);
let id = [2u8; 20];
table.insert(DhtNode::new(id, make_addr(6881)));
for _ in 0..5 {
assert!(table.mark_bad(&id));
}
}
#[test]
fn test_get_random_node() {
let mut table = RoutingTable::new([0u8; 20]);
for i in 0..5u8 {
table.insert(DhtNode::new([i; 20], make_addr(6881 + i as u16)));
}
let node = table.get_random_node();
assert!(node.is_some());
}
#[test]
fn test_get_random_node_empty_table() {
let table = RoutingTable::new([0u8; 20]);
let node = table.get_random_node();
assert!(node.is_none());
}
#[test]
fn test_collect_good_nodes() {
let mut table = RoutingTable::new([0u8; 20]);
table.insert(DhtNode::new([1u8; 20], make_addr(6881)));
let good = table.collect_good_nodes();
assert_eq!(good.len(), 1);
}
#[test]
fn test_no_self_insert() {
let self_id = [0x42u8; 20];
let mut table = RoutingTable::new(self_id);
table.insert(DhtNode::new(self_id, make_addr(6881)));
assert_eq!(table.total_node_count(), 0);
}
#[test]
fn test_cache_node_on_full_bucket() {
let self_id = [0xFFu8; 20];
let mut table = RoutingTable::new(self_id);
for i in 1..=super::super::bucket::K as u8 {
let mut id = [0u8; 20];
id[0] = i; table.insert(DhtNode::new(id, make_addr(6881 + i as u16)));
}
for i in 9..=20u8 {
let mut id = [0u8; 20];
id[0] = i; table.insert(DhtNode::new(id, make_addr(7000 + i as u16)));
}
let buckets = table.get_all_buckets();
let has_cached = buckets.iter().any(|b| !b.cached_nodes().is_empty());
assert!(
has_cached,
"Expected at least one bucket to have cached nodes"
);
}
#[test]
fn full_non_local_bucket_caches_only_verified_replacements() {
let self_id = [0xFF; 20];
let mut table = RoutingTable::new(self_id);
for i in 1..=super::super::bucket::K as u8 {
table.insert(DhtNode::new([i; 20], make_addr(6881 + i as u16)));
}
let candidate_id = [0x40; 20];
table.insert(DhtNode::unverified(candidate_id, make_addr(6990)));
assert_eq!(table.num_buckets(), 2);
let bucket = table.get_bucket_for(&candidate_id);
assert!(
!bucket.is_in_range(&self_id),
"candidate must be in a non-local bucket"
);
assert_eq!(bucket.count_node(), super::super::bucket::K);
assert!(bucket.nodes().iter().all(|node| node.id() != &candidate_id));
assert!(
bucket
.cached_nodes()
.iter()
.all(|node| node.id() != &candidate_id),
"unverified candidates must not enter the replacement cache"
);
let verified_id = [0x41; 20];
table.insert(DhtNode::new(verified_id, make_addr(6991)));
assert!(
table
.get_bucket_for(&verified_id)
.cached_nodes()
.iter()
.any(|node| node.id() == &verified_id),
"verified candidates must enter the replacement cache"
);
}
#[test]
fn unverified_candidate_cannot_replace_bad_lru_in_full_non_local_bucket() {
let self_id = [0xFF; 20];
let mut table = RoutingTable::new(self_id);
for i in 1..=super::super::bucket::K as u8 {
table.insert(DhtNode::new([i; 20], make_addr(6881 + i as u16)));
}
let failed_id = [1; 20];
for _ in 0..5 {
assert!(table.mark_bad(&failed_id));
}
let unverified_id = [0x40; 20];
table.insert(DhtNode::unverified(unverified_id, make_addr(6990)));
let bucket = table.get_bucket_for(&unverified_id);
assert_eq!(bucket.count_node(), super::super::bucket::K);
assert!(
bucket.nodes().iter().any(|node| node.id() == &failed_id),
"insertion must not evict a bad node in favor of an unverified candidate"
);
assert!(
bucket
.nodes()
.iter()
.all(|node| node.id() != &unverified_id),
"an unverified candidate must not enter a full non-local bucket"
);
assert!(
bucket
.cached_nodes()
.iter()
.all(|node| node.id() != &unverified_id),
"an unverified candidate must not enter the replacement cache"
);
assert_eq!(table.evict_bad_nodes(), 1);
let bucket = table.get_bucket_for(&unverified_id);
assert_eq!(bucket.count_node(), super::super::bucket::K - 1);
assert!(
bucket
.nodes()
.iter()
.all(|node| node.id() != &unverified_id),
"bad-node eviction must not promote the rejected unverified candidate"
);
}
#[test]
fn test_evict_bad_nodes() {
let mut table = RoutingTable::new([0u8; 20]);
for i in 1..=super::super::bucket::K as u8 {
table.insert(DhtNode::new([i; 20], make_addr(6881 + i as u16)));
}
let lower_bad_id = [1; 20];
let upper_bad_id = [0x80; 20];
table.insert(DhtNode::new(upper_bad_id, make_addr(6999)));
assert_eq!(table.num_buckets(), 2);
for _ in 0..5 {
assert!(table.mark_bad(&lower_bad_id));
assert!(table.mark_bad(&upper_bad_id));
}
assert_eq!(table.evict_bad_nodes(), 2);
assert_eq!(table.total_node_count(), super::super::bucket::K - 1);
}
#[test]
fn evicting_bad_node_promotes_the_newest_verified_cached_replacement() {
let mut table = RoutingTable::new([0xFF; 20]);
for i in 1..=super::super::bucket::K as u8 {
table.insert(DhtNode::new([i; 20], make_addr(6881 + i as u16)));
}
let older_candidate = [0x40; 20];
let replacement_id = [0x41; 20];
table.insert(DhtNode::new(older_candidate, make_addr(6990)));
table.insert(DhtNode::new(replacement_id, make_addr(6991)));
let unverified_id = [0x3F; 20];
table.insert(DhtNode::unverified(unverified_id, make_addr(6989)));
let failed_id = [1; 20];
for _ in 0..5 {
assert!(table.mark_bad(&failed_id));
}
assert_eq!(table.evict_bad_nodes(), 1);
let bucket = table.get_bucket_for(&replacement_id);
assert_eq!(bucket.count_node(), super::super::bucket::K);
assert!(
bucket
.nodes()
.iter()
.any(|node| node.id() == &replacement_id)
);
assert!(
bucket
.cached_nodes()
.iter()
.any(|node| node.id() == &older_candidate),
"remaining replacement cache: {:?}",
bucket
.cached_nodes()
.iter()
.map(DhtNode::id)
.collect::<Vec<_>>()
);
assert!(
bucket
.nodes()
.iter()
.chain(bucket.cached_nodes())
.all(|node| node.id() != &unverified_id),
"unverified candidate must not be promoted or retained in the replacement cache"
);
}
}