use std::time::Instant;
use super::node::DhtNode;
pub const K: usize = 8;
pub const CACHE_SIZE: usize = 2;
const ID_LENGTH: usize = 20;
const BUCKET_REFRESH_INTERVAL_SECS: u64 = 15 * 60;
fn flip_bit(id: &mut [u8; 20], bit_index: usize) {
let byte_index = bit_index / 8;
let bit_offset = 7 - (bit_index % 8);
if byte_index < 20 {
id[byte_index] ^= 1 << bit_offset;
}
}
#[derive(Debug)]
pub struct Bucket {
prefix_length: usize,
min_id: [u8; 20],
max_id: [u8; 20],
local_id: [u8; 20],
nodes: Vec<DhtNode>,
cached_nodes: Vec<DhtNode>,
last_updated: Instant,
}
impl Bucket {
pub fn new(local_node: &DhtNode) -> Self {
Self {
prefix_length: 0,
min_id: [0u8; 20],
max_id: [0xFFu8; 20],
local_id: local_node.id,
nodes: Vec::with_capacity(K),
cached_nodes: Vec::with_capacity(CACHE_SIZE),
last_updated: Instant::now(),
}
}
pub fn new_for_range(
prefix_length: usize,
min_id: [u8; 20],
max_id: [u8; 20],
local_id: [u8; 20],
) -> Self {
Self {
prefix_length,
min_id,
max_id,
local_id,
nodes: Vec::with_capacity(K),
cached_nodes: Vec::with_capacity(CACHE_SIZE),
last_updated: Instant::now(),
}
}
pub fn prefix_length(&self) -> usize {
self.prefix_length
}
pub fn min_id(&self) -> &[u8; 20] {
&self.min_id
}
pub fn max_id(&self) -> &[u8; 20] {
&self.max_id
}
pub fn count_node(&self) -> usize {
self.nodes.len()
}
pub fn is_full(&self) -> bool {
self.nodes.len() >= K
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
pub fn nodes(&self) -> &[DhtNode] {
&self.nodes
}
pub fn cached_nodes(&self) -> &[DhtNode] {
&self.cached_nodes
}
pub fn good_node_count(&self) -> usize {
self.nodes.iter().filter(|n| !n.is_bad()).count()
}
pub fn is_in_range(&self, node_id: &[u8; 20]) -> bool {
node_id.as_slice() >= self.min_id.as_slice() && node_id.as_slice() <= self.max_id.as_slice()
}
pub fn add_node(&mut self, node: DhtNode) -> bool {
self.notify_update();
if let Some(pos) = self.nodes.iter().position(|n| n.id == node.id) {
self.nodes.remove(pos);
self.nodes.push(node);
return true;
}
if self.nodes.len() < K {
self.nodes.push(node);
return true;
}
if let Some(front) = self.nodes.first()
&& front.is_bad()
{
self.nodes.remove(0);
self.nodes.push(node);
return true;
}
false
}
pub fn cache_node(&mut self, node: DhtNode) {
self.cached_nodes.insert(0, node);
if self.cached_nodes.len() > CACHE_SIZE {
self.cached_nodes.truncate(CACHE_SIZE);
}
}
pub fn drop_node(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
self.nodes.remove(pos);
if !self.cached_nodes.is_empty() {
let replacement = self.cached_nodes.remove(0);
self.nodes.push(replacement);
}
true
} else {
false
}
}
pub fn remove_node(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
self.nodes.remove(pos);
true
} else {
false
}
}
pub fn move_to_head(&mut self, node_id: &[u8; 20]) {
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
let node = self.nodes.remove(pos);
self.nodes.insert(0, node);
}
}
pub fn move_to_tail(&mut self, node_id: &[u8; 20]) {
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
let node = self.nodes.remove(pos);
self.nodes.push(node);
}
}
pub fn split_allowed(&self) -> bool {
self.prefix_length < ID_LENGTH * 8 - 1 && self.is_in_range(&self.local_id)
}
pub fn split(&mut self) -> Bucket {
assert!(
self.split_allowed(),
"split() called on non-splittable bucket"
);
let r_max = self.max_id;
let mut r_min = self.min_id;
flip_bit(&mut r_min, self.prefix_length);
flip_bit(&mut self.max_id, self.prefix_length);
self.prefix_length += 1;
let new_prefix_length = self.prefix_length;
let mut right_bucket =
Bucket::new_for_range(new_prefix_length, r_min, r_max, self.local_id);
let mut remaining = Vec::with_capacity(K);
for node in self.nodes.drain(..) {
if right_bucket.is_in_range(&node.id) {
right_bucket.nodes.push(node);
} else {
remaining.push(node);
}
}
self.nodes = remaining;
tracing::debug!(
"Bucket split: left prefix={} range={}-{}, right prefix={} range={}-{}",
self.prefix_length,
hex::encode(self.min_id),
hex::encode(self.max_id),
right_bucket.prefix_length,
hex::encode(right_bucket.min_id),
hex::encode(right_bucket.max_id),
);
right_bucket
}
pub fn needs_refresh(&self) -> bool {
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 get_lru_questionable_node(&self) -> Option<&DhtNode> {
self.nodes.iter().find(|n| n.is_questionable())
}
pub fn get_node(&self, node_id: &[u8; 20], ip_addr: &str, port: u16) -> Option<&DhtNode> {
self.nodes.iter().find(|n| {
&n.id == node_id && n.addr.ip().to_string() == ip_addr && n.addr.port() == port
})
}
pub fn get_random_node_id(&self) -> [u8; 20] {
use rand::Rng;
let mut id = [0u8; 20];
let mut rng = rand::thread_rng();
if self.prefix_length == 0 {
rng.fill(&mut id);
} else {
let last_byte_index = (self.prefix_length - 1) / 8;
rng.fill(&mut id);
id[..=last_byte_index].copy_from_slice(&self.min_id[..=last_byte_index]);
}
id
}
pub fn mark_good(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(node) = self.nodes.iter_mut().find(|n| &n.id == node_id) {
node.touch();
true
} else {
false
}
}
pub fn mark_bad(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(node) = self.nodes.iter_mut().find(|n| &n.id == node_id) {
node.record_failure();
true
} else {
false
}
}
pub fn evict_bad(&mut self) -> usize {
let before = self.nodes.len();
self.nodes.retain(|n| !n.is_bad());
before - self.nodes.len()
}
fn notify_update(&mut self) {
self.last_updated = Instant::now();
}
pub fn get_good_nodes(&self) -> Vec<DhtNode> {
self.nodes.iter().filter(|n| !n.is_bad()).cloned().collect()
}
pub fn questionable_count(&self) -> usize {
self.nodes.iter().filter(|n| n.is_questionable()).count()
}
pub fn bad_count(&self) -> usize {
self.nodes.iter().filter(|n| n.is_bad()).count()
}
}
impl Clone for Bucket {
fn clone(&self) -> Self {
Self {
prefix_length: self.prefix_length,
min_id: self.min_id,
max_id: self.max_id,
local_id: self.local_id,
nodes: self.nodes.clone(),
cached_nodes: self.cached_nodes.clone(),
last_updated: self.last_updated,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::SocketAddr;
fn make_local_node() -> DhtNode {
DhtNode::new([0u8; 20], "127.0.0.1:6881".parse::<SocketAddr>().unwrap())
}
#[test]
fn test_bucket_creation_full_range() {
let local = make_local_node();
let bucket = Bucket::new(&local);
assert_eq!(bucket.prefix_length(), 0);
assert_eq!(bucket.min_id(), &[0u8; 20]);
assert_eq!(bucket.max_id(), &[0xFFu8; 20]);
assert_eq!(bucket.count_node(), 0);
assert!(!bucket.is_full());
}
#[test]
fn test_bucket_is_in_range() {
let local = make_local_node();
let bucket = Bucket::new(&local);
assert!(bucket.is_in_range(&[0u8; 20]));
assert!(bucket.is_in_range(&[0xFFu8; 20]));
assert!(bucket.is_in_range(&[0x80u8; 20]));
}
#[test]
fn test_add_node() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
let node = DhtNode::new([1u8; 20], "127.0.0.1:6882".parse().unwrap());
assert!(bucket.add_node(node));
assert_eq!(bucket.count_node(), 1);
}
#[test]
fn test_add_node_full_bucket_replaces_bad() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
for i in 0..K {
let mut node = DhtNode::new(
[i as u8; 20],
format!("127.0.0.1:{}", 6882 + i).parse().unwrap(),
);
for _ in 0..3 {
node.record_failure();
}
bucket.add_node(node);
}
assert!(bucket.is_full());
let new_node = DhtNode::new([0xFFu8; 20], "127.0.0.1:9999".parse().unwrap());
assert!(bucket.add_node(new_node));
assert_eq!(bucket.count_node(), K);
}
#[test]
fn test_add_node_full_bucket_rejects() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
for i in 0..K {
let node = DhtNode::new(
[(i + 1) as u8; 20],
format!("127.0.0.1:{}", 6882 + i).parse().unwrap(),
);
bucket.add_node(node);
}
assert!(bucket.is_full());
let new_node = DhtNode::new([0xFFu8; 20], "127.0.0.1:9999".parse().unwrap());
assert!(!bucket.add_node(new_node));
}
#[test]
fn test_split_allowed() {
let local = make_local_node();
let bucket = Bucket::new(&local);
assert!(bucket.split_allowed());
}
#[test]
fn test_split_not_allowed_if_local_id_out_of_range() {
let local = DhtNode::new([0xFFu8; 20], "127.0.0.1:6881".parse().unwrap());
let bucket = Bucket::new_for_range(
1,
[0u8; 20], [0x7Fu8; 20], local.id,
);
assert!(!bucket.split_allowed());
}
#[test]
fn test_split() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
for i in 0..4u8 {
let node = DhtNode::new(
[i; 20],
format!("127.0.0.1:{}", 6882 + i as u16).parse().unwrap(),
);
bucket.add_node(node);
}
for i in 0..4u8 {
let mut id = [0u8; 20];
id[0] = 0x80 | i;
let node = DhtNode::new(
id,
format!("127.0.0.2:{}", 6882 + i as u16).parse().unwrap(),
);
bucket.add_node(node);
}
assert_eq!(bucket.count_node(), 8);
let right_bucket = bucket.split();
assert_eq!(bucket.prefix_length(), 1);
assert_eq!(bucket.count_node(), 4);
assert_eq!(right_bucket.prefix_length(), 1);
assert_eq!(right_bucket.count_node(), 4);
}
#[test]
fn test_cache_node() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
let node = DhtNode::new([1u8; 20], "127.0.0.1:6882".parse().unwrap());
bucket.cache_node(node);
assert_eq!(bucket.cached_nodes().len(), 1);
}
#[test]
fn test_cache_node_limit() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
for i in 0..5u8 {
let node = DhtNode::new(
[i; 20],
format!("127.0.0.1:{}", 6882 + i as u16).parse().unwrap(),
);
bucket.cache_node(node);
}
assert_eq!(bucket.cached_nodes().len(), CACHE_SIZE);
}
#[test]
fn test_drop_node_promotes_cached() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
let node_id = [1u8; 20];
let node = DhtNode::new(node_id, "127.0.0.1:6882".parse().unwrap());
bucket.add_node(node);
let replacement = DhtNode::new([2u8; 20], "127.0.0.1:6883".parse().unwrap());
bucket.cache_node(replacement);
assert!(bucket.drop_node(&node_id));
assert_eq!(bucket.count_node(), 1);
assert!(bucket.nodes().iter().any(|n| n.id == [2u8; 20]));
}
#[test]
fn test_get_random_node_id() {
let local = make_local_node();
let bucket = Bucket::new(&local);
let id = bucket.get_random_node_id();
assert!(bucket.is_in_range(&id));
}
#[test]
fn test_needs_refresh_empty() {
let local = make_local_node();
let bucket = Bucket::new(&local);
assert!(bucket.needs_refresh());
}
#[test]
fn test_contains_questionable_node() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
let node = DhtNode::new([1u8; 20], "127.0.0.1:6882".parse().unwrap());
bucket.add_node(node);
assert!(!bucket.contains_questionable_node());
}
#[test]
fn test_move_to_tail() {
let local = make_local_node();
let mut bucket = Bucket::new(&local);
let n1 = DhtNode::new([1u8; 20], "127.0.0.1:6882".parse().unwrap());
let n2 = DhtNode::new([2u8; 20], "127.0.0.1:6883".parse().unwrap());
bucket.add_node(n1);
bucket.add_node(n2);
bucket.move_to_tail(&[1u8; 20]);
assert_eq!(bucket.nodes()[1].id, [1u8; 20]);
}
}