use std::collections::VecDeque;
use std::time::Instant;
use tracing::trace;
use super::constants::{CACHE_SIZE, ID_LENGTH, K};
use super::node::DhtNode;
use super::node_id::NodeId;
pub struct DhtBucket {
prefix_length: usize,
min_id: NodeId,
max_id: NodeId,
local_node_id: NodeId,
nodes: VecDeque<Box<DhtNode>>,
cached_nodes: VecDeque<Box<DhtNode>>,
last_updated: Instant,
}
impl DhtBucket {
pub fn new(local_node_id: NodeId) -> Self {
DhtBucket {
prefix_length: 0,
min_id: NodeId::ZERO,
max_id: NodeId::MAX,
local_node_id,
nodes: VecDeque::with_capacity(K),
cached_nodes: VecDeque::with_capacity(CACHE_SIZE),
last_updated: Instant::now(),
}
}
pub fn with_range(
prefix_length: usize,
max_id: NodeId,
min_id: NodeId,
local_node_id: NodeId,
) -> Self {
DhtBucket {
prefix_length,
min_id,
max_id,
local_node_id,
nodes: VecDeque::with_capacity(K),
cached_nodes: VecDeque::with_capacity(CACHE_SIZE),
last_updated: Instant::now(),
}
}
pub fn random_node_id(&self) -> NodeId {
if self.prefix_length == 0 {
return NodeId::random();
}
let mut id = NodeId::random();
let last_byte_index = (self.prefix_length - 1) / 8;
id.0[..=last_byte_index].copy_from_slice(&self.min_id.0[..=last_byte_index]);
id
}
pub fn is_in_range(&self, id: &NodeId) -> bool {
id.is_in_range(&self.min_id, &self.max_id)
}
pub fn contains_local_node(&self) -> bool {
self.is_in_range(&self.local_node_id)
}
pub fn add_node(&mut self, node: DhtNode) -> bool {
self.notify_update();
let node_id = *node.id();
if let Some(pos) = self.nodes.iter().position(|n| n.id() == &node_id) {
self.nodes.remove(pos);
self.nodes.push_back(Box::new(node));
return true;
}
if self.nodes.len() < K {
self.nodes.push_back(Box::new(node));
return true;
}
if self.nodes.front().is_some_and(|n| n.is_bad()) {
self.nodes.pop_front();
self.nodes.push_back(Box::new(node));
return true;
}
false
}
pub fn cache_node(&mut self, node: DhtNode) {
self.cached_nodes.push_front(Box::new(node));
if self.cached_nodes.len() > CACHE_SIZE {
self.cached_nodes.truncate(CACHE_SIZE);
}
trace!(
prefix = self.prefix_length,
cache_len = self.cached_nodes.len(),
"Cached DHT node"
);
}
pub fn drop_node(&mut self, node_id: &NodeId) {
if self.cached_nodes.is_empty() {
return;
}
if let Some(pos) = self.nodes.iter().position(|n| n.id() == node_id) {
self.nodes.remove(pos);
if let Some(replacement) = self.cached_nodes.pop_front() {
self.nodes.push_back(replacement);
}
}
}
pub fn move_to_head(&mut self, node_id: &NodeId) {
if let Some(pos) = self.nodes.iter().position(|n| n.id() == node_id) {
let node = self.nodes.remove(pos).unwrap();
self.nodes.push_front(node);
}
}
pub fn move_to_tail(&mut self, node_id: &NodeId) {
if let Some(pos) = self.nodes.iter().position(|n| n.id() == node_id) {
let node = self.nodes.remove(pos).unwrap();
self.nodes.push_back(node);
}
}
pub fn get_node(
&self,
node_id: &NodeId,
addr_check: impl Fn(&DhtNode) -> bool,
) -> Option<&DhtNode> {
self.nodes
.iter()
.find(|n| n.id() == node_id && addr_check(n))
.map(|b| b.as_ref())
}
pub fn get_node_mut(&mut self, node_id: &NodeId) -> Option<&mut DhtNode> {
self.nodes
.iter_mut()
.find(|n| n.id() == node_id)
.map(|b| b.as_mut())
}
pub fn split_allowed(&self) -> bool {
self.prefix_length < ID_LENGTH * 8 - 1 && self.contains_local_node()
}
pub fn split(&mut self) -> Self {
assert!(self.split_allowed(), "Bucket split not allowed");
let mut r_max = self.max_id;
let r_min = self.min_id;
r_max.flip_bit(self.prefix_length);
self.min_id.flip_bit(self.prefix_length);
self.prefix_length += 1;
let mut r_bucket =
DhtBucket::with_range(self.prefix_length, r_max, r_min, self.local_node_id);
let mut remaining = VecDeque::with_capacity(K);
for node in self.nodes.drain(..) {
if r_bucket.is_in_range(node.id()) {
r_bucket.nodes.push_back(node);
} else {
remaining.push_back(node);
}
}
self.nodes = remaining;
trace!(
left_prefix = self.prefix_length,
left_min = %self.min_id,
left_max = %self.max_id,
left_nodes = self.nodes.len(),
right_prefix = r_bucket.prefix_length,
right_nodes = r_bucket.nodes.len(),
"Bucket split completed"
);
r_bucket
}
pub fn good_nodes(&self) -> impl Iterator<Item = &DhtNode> {
self.nodes
.iter()
.filter(|n| !n.is_bad())
.map(|b| b.as_ref())
}
pub fn count(&self) -> usize {
self.nodes.len()
}
pub fn contains(&self, node_id: &NodeId) -> bool {
self.nodes.iter().any(|n| n.id() == node_id)
}
pub fn needs_refresh(&self) -> bool {
use super::constants::BUCKET_REFRESH_INTERVAL_SECS;
self.nodes.len() < K
|| self.last_updated.elapsed().as_secs() >= BUCKET_REFRESH_INTERVAL_SECS
}
pub fn contains_questionable_node(&self) -> bool {
self.nodes.iter().any(|n| n.is_questionable())
}
pub fn lru_questionable_node(&self) -> Option<&DhtNode> {
self.nodes
.iter()
.find(|n| n.is_questionable())
.map(|b| b.as_ref())
}
pub fn notify_update(&mut self) {
self.last_updated = Instant::now();
}
pub fn prefix_length(&self) -> usize {
self.prefix_length
}
pub fn common_prefix_len(&self) -> usize {
self.prefix_length
}
pub fn time_since_last_update(&self) -> std::time::Duration {
self.last_updated.elapsed()
}
pub fn random_id_in_range(&self) -> NodeId {
let mut id = *self.min_id.as_bytes();
for byte in &mut id[self.prefix_length / 8..ID_LENGTH] {
*byte = rand::random::<u8>();
}
if !self.prefix_length.is_multiple_of(8) {
let byte_idx = self.prefix_length / 8;
let mask = 0xFFu8 >> (self.prefix_length % 8);
id[byte_idx] = (id[byte_idx] & !mask) | (rand::random::<u8>() & mask);
}
NodeId(id)
}
pub fn min_id(&self) -> &NodeId {
&self.min_id
}
pub fn max_id(&self) -> &NodeId {
&self.max_id
}
pub fn nodes(&self) -> &VecDeque<Box<DhtNode>> {
&self.nodes
}
pub fn cached_nodes(&self) -> &VecDeque<Box<DhtNode>> {
&self.cached_nodes
}
}
impl std::fmt::Debug for DhtBucket {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("DhtBucket")
.field("prefix_length", &self.prefix_length)
.field("min_id", &self.min_id)
.field("max_id", &self.max_id)
.field("node_count", &self.nodes.len())
.field("cache_count", &self.cached_nodes.len())
.finish()
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::{IpAddr, Ipv4Addr, SocketAddr};
fn test_addr() -> SocketAddr {
SocketAddr::new(IpAddr::V4(Ipv4Addr::new(127, 0, 0, 1)), 6881)
}
fn make_node(id_byte: u8) -> DhtNode {
let id = NodeId::from_slice(&[id_byte; ID_LENGTH]);
DhtNode::new(id, test_addr())
}
#[test]
fn new_bucket_covers_full_range() {
let bucket = DhtBucket::new(NodeId::ZERO);
assert_eq!(bucket.prefix_length(), 0);
assert_eq!(bucket.min_id(), &NodeId::ZERO);
assert_eq!(bucket.max_id(), &NodeId::MAX);
assert_eq!(bucket.count(), 0);
}
#[test]
fn add_node_within_capacity() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
for i in 0..K {
let node = make_node(i as u8);
assert!(bucket.add_node(node));
}
assert_eq!(bucket.count(), K);
}
#[test]
fn add_node_when_full_returns_false() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
for i in 0..K {
let mut node = make_node(i as u8);
node.mark_good();
node.update_last_contact();
bucket.add_node(node);
}
let extra = make_node(0xFF);
assert!(!bucket.add_node(extra));
}
#[test]
fn add_node_evicts_bad_node_when_full() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
for i in 0..K {
let mut node = make_node(i as u8);
if i == 0 {
node.mark_bad();
}
bucket.add_node(node);
}
assert_eq!(bucket.count(), K);
let new_node = make_node(0xFF);
assert!(bucket.add_node(new_node));
assert_eq!(bucket.count(), K);
assert!(!bucket.contains(&NodeId::from_slice(&[0u8; ID_LENGTH])));
assert!(bucket.contains(&NodeId::from_slice(&[0xFFu8; ID_LENGTH])));
}
#[test]
fn add_existing_node_moves_to_tail() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
let mut node = make_node(0x42);
node.mark_good();
node.update_last_contact();
bucket.add_node(node);
let mut node2 = make_node(0x43);
node2.mark_good();
bucket.add_node(node2);
let node3 = make_node(0x42);
bucket.add_node(node3);
assert_eq!(bucket.count(), 2);
assert_eq!(
bucket.nodes().back().unwrap().id(),
&NodeId::from_slice(&[0x42u8; ID_LENGTH])
);
}
#[test]
fn cache_node_respects_cache_size() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
for i in 0..CACHE_SIZE + 2 {
let node = make_node(i as u8);
bucket.cache_node(node);
}
assert!(bucket.cached_nodes().len() <= CACHE_SIZE);
}
#[test]
fn drop_node_replaces_from_cache() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
let node = make_node(0x01);
bucket.add_node(node);
let cached = make_node(0x02);
bucket.cache_node(cached);
bucket.drop_node(&NodeId::from_slice(&[0x01u8; ID_LENGTH]));
assert!(!bucket.contains(&NodeId::from_slice(&[0x01u8; ID_LENGTH])));
assert!(bucket.contains(&NodeId::from_slice(&[0x02u8; ID_LENGTH])));
}
#[test]
fn split_produces_two_halves() {
let mut bucket = DhtBucket::new(NodeId::from_slice(&[0x80u8; ID_LENGTH]));
let upper_node = make_node(0xFF); let lower_node = make_node(0x01); bucket.add_node(upper_node);
bucket.add_node(lower_node);
let r_bucket = bucket.split();
assert_eq!(bucket.prefix_length(), 1);
assert!(bucket.min_id().get_bit(0)); assert_eq!(bucket.count(), 1);
assert!(bucket.contains(&NodeId::from_slice(&[0xFFu8; ID_LENGTH])));
assert_eq!(r_bucket.prefix_length(), 1);
assert!(!r_bucket.min_id().get_bit(0)); assert_eq!(r_bucket.count(), 1);
assert!(r_bucket.contains(&NodeId::from_slice(&[0x01u8; ID_LENGTH])));
}
#[test]
fn split_allowed_only_when_local_in_range() {
let bucket = DhtBucket::new(NodeId::from_slice(&[0x80u8; ID_LENGTH]));
assert!(bucket.split_allowed());
}
#[test]
fn split_not_allowed_at_max_prefix() {
let bucket = DhtBucket::with_range(
ID_LENGTH * 8 - 1,
NodeId::MAX,
NodeId::ZERO,
NodeId::from_slice(&[0x80u8; ID_LENGTH]),
);
assert!(!bucket.split_allowed());
}
#[test]
fn is_in_range() {
let bucket = DhtBucket::new(NodeId::ZERO);
assert!(bucket.is_in_range(&NodeId::ZERO));
assert!(bucket.is_in_range(&NodeId::MAX));
assert!(bucket.is_in_range(&NodeId::from_slice(&[0x80u8; ID_LENGTH])));
}
#[test]
fn needs_refresh_when_under_full() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
assert!(bucket.needs_refresh());
let node = make_node(0x01);
bucket.add_node(node);
assert!(bucket.needs_refresh());
}
#[test]
fn contains_questionable_node() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
let mut node = make_node(0x01);
node.mark_good();
assert!(node.is_questionable());
bucket.add_node(node);
assert!(bucket.contains_questionable_node());
}
#[test]
fn move_to_head_and_tail() {
let mut bucket = DhtBucket::new(NodeId::ZERO);
let n1 = make_node(0x01);
let n2 = make_node(0x02);
bucket.add_node(n1);
bucket.add_node(n2);
assert_eq!(
bucket.nodes().front().unwrap().id(),
&NodeId::from_slice(&[0x01u8; ID_LENGTH])
);
bucket.move_to_head(&NodeId::from_slice(&[0x02u8; ID_LENGTH]));
assert_eq!(
bucket.nodes().front().unwrap().id(),
&NodeId::from_slice(&[0x02u8; ID_LENGTH])
);
bucket.move_to_tail(&NodeId::from_slice(&[0x02u8; ID_LENGTH]));
assert_eq!(
bucket.nodes().back().unwrap().id(),
&NodeId::from_slice(&[0x02u8; ID_LENGTH])
);
}
}