use std::collections::VecDeque;
use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
use std::sync::{Arc, OnceLock};
use dashmap::DashMap;
use parking_lot::{Mutex, MutexGuard};
use tokio_tungstenite::tungstenite::Message;
use super::state::{ConnectionHandle, SharedState};
pub(crate) const KEPT_FOR_MS: u64 = 24 * 60 * 60 * 1000;
const MAX_IDLE: usize = 1 << 18;
pub(super) fn idle_limit(max_connections: usize) -> usize {
MAX_IDLE.max(max_connections.saturating_mul(2))
}
const ASK_WITHIN: std::time::Duration = std::time::Duration::from_secs(2);
const MAX_ID_LEN: usize = 64;
pub(crate) const MAX_HOLES: usize = 1024;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Refusal {
Busy,
RateLimited,
Missing,
NotReady,
}
impl Refusal {
pub(crate) fn as_str(self) -> &'static str {
match self {
Self::Busy => "busy",
Self::RateLimited => "rate_limited",
Self::Missing => "missing",
Self::NotReady => "not_ready",
}
}
pub(crate) fn code(self) -> u8 {
match self {
Self::Busy => 1,
Self::RateLimited => 2,
Self::Missing => 3,
Self::NotReady => 4,
}
}
pub(crate) fn from_code(code: u8) -> Option<Self> {
match code {
1 => Some(Self::Busy),
2 => Some(Self::RateLimited),
3 => Some(Self::Missing),
4 => Some(Self::NotReady),
_ => None,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Hole {
pub(crate) from: u64,
pub(crate) to: u64,
pub(crate) why: Refusal,
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct Decided {
pub(crate) mark: u64,
pub(crate) holes: Vec<Hole>,
pub(crate) forgot: u64,
pub(crate) undecided: Option<u64>,
pub(crate) unsure: u64,
}
pub(crate) struct Slot {
state: Mutex<SlotState>,
seen: AtomicU64,
moved: AtomicBool,
}
pub(crate) struct SlotState {
mark: u64,
moved: bool,
holes: VecDeque<Hole>,
forgot: u64,
deciding: Option<u64>,
unsure: u64,
owner: u64,
}
#[derive(Debug, PartialEq, Eq)]
pub(crate) enum Claim {
First {
gap: Option<(u64, u64)>,
unsure: bool,
},
Repeat,
Refused(Refusal),
Unsure,
Moved,
Left,
}
impl SlotState {
pub(crate) fn claim(&mut self, s: u64, skipped: Refusal) -> Claim {
if self.moved {
return Claim::Moved;
}
if s <= self.mark {
if let Some(why) = self.refusal_of(s) {
return Claim::Refused(why);
}
if self.deciding == Some(s) || s <= self.forgot {
return Claim::Unsure;
}
return Claim::Repeat;
}
let gap = (s > self.mark + 1).then(|| (self.mark + 1, s - 1));
if let Some((from, to)) = gap {
self.refuse(from, to, skipped);
}
self.mark = s;
Claim::First {
gap,
unsure: s <= self.unsure,
}
}
pub(crate) fn claim_by(&mut self, owner: u64, s: u64, skipped: Refusal) -> Claim {
if owner != self.owner {
return Claim::Left;
}
self.claim(s, skipped)
}
fn take(&mut self) -> u64 {
self.owner += 1;
self.owner
}
fn unsure_up_to(&mut self, s: u64) {
self.unsure = self.unsure.max(s);
}
pub(crate) fn refuse(&mut self, from: u64, to: u64, why: Refusal) {
if let Some(last) = self.holes.back_mut()
&& last.why == why
&& last.to + 1 == from
{
last.to = to;
return;
}
if self.holes.len() == MAX_HOLES
&& let Some(gone) = self.holes.pop_front()
{
self.forgot = self.forgot.max(gone.to);
}
let at = self.holes.partition_point(|h| h.to < from);
self.holes.insert(at, Hole { from, to, why });
}
pub(crate) fn deciding(&mut self, s: u64) {
self.deciding = Some(s);
}
pub(crate) fn decided(&mut self, s: u64) {
if self.deciding == Some(s) {
self.deciding = None;
}
}
pub(crate) fn acked(&self) -> u64 {
self.deciding
.map_or(self.mark, |s| self.mark.min(s.saturating_sub(1)))
}
fn decided_for(&self, from: u64) -> u64 {
let from = from.max(1);
if from <= self.forgot {
self.acked().min(from - 1)
} else {
self.acked()
}
}
fn refusal_of(&self, s: u64) -> Option<Refusal> {
let at = self.holes.partition_point(|h| h.to < s);
self.holes.get(at).filter(|h| h.from <= s).map(|h| h.why)
}
fn cannot_tell(&self, from: u64) -> u64 {
let forgot = if from.max(1) <= self.forgot {
self.forgot
} else {
0
};
self.unsure.max(forgot).max(self.deciding.unwrap_or(0))
}
fn told_from(&mut self, from: u64) -> Vec<Hole> {
let heard = self.holes.partition_point(|h| h.to < from);
self.holes.drain(..heard);
self.holes.iter().copied().collect()
}
fn advance(&mut self, decided: &Decided) {
let to = decided.mark;
if self.moved {
return;
}
self.unsure_up_to(decided.unsure);
if to <= self.mark {
return;
}
let mark = self.mark;
for hole in decided.holes.iter().filter(|h| h.from > mark && h.to <= to) {
self.refuse(hole.from, hole.to, hole.why);
}
self.forgot = self.forgot.max(decided.forgot.min(to));
if let Some(s) = decided.undecided.filter(|s| *s > mark && *s <= to) {
self.deciding = Some(s);
}
self.mark = to;
}
fn hand_over(&mut self) -> Decided {
self.moved = true;
Decided {
mark: self.mark,
holes: self.holes.iter().copied().collect(),
forgot: self.forgot,
undecided: self.deciding,
unsure: self.unsure,
}
}
#[cfg(test)]
fn mark(&self) -> u64 {
self.mark
}
}
impl Slot {
fn new(now: u64) -> Self {
Self {
state: Mutex::new(SlotState {
mark: 0,
moved: false,
holes: VecDeque::new(),
forgot: 0,
deciding: None,
unsure: 0,
owner: 0,
}),
seen: AtomicU64::new(now),
moved: AtomicBool::new(false),
}
}
pub(crate) fn lock(&self) -> MutexGuard<'_, SlotState> {
self.state.lock()
}
fn touch(&self, now: u64) {
self.seen.store(now, Ordering::Relaxed);
}
fn seen(&self) -> u64 {
self.seen.load(Ordering::Relaxed)
}
}
type Key = (Option<Box<str>>, Box<str>);
fn held(slot: &Arc<Slot>) -> bool {
Arc::strong_count(slot) > 1
}
pub(crate) struct Producers {
slots: DashMap<Key, Arc<Slot>>,
limit: usize,
}
impl Default for Producers {
fn default() -> Self {
Self::with_limit(MAX_IDLE)
}
}
impl Producers {
pub(super) fn with_limit(limit: usize) -> Self {
Self {
slots: DashMap::new(),
limit,
}
}
fn attach(&self, user: Option<&str>, producer: &str, now: u64) -> (Arc<Slot>, bool) {
use dashmap::mapref::entry::Entry;
let key = (user.map(Box::from), Box::from(producer));
match self.slots.entry(key) {
Entry::Occupied(mut entry) => {
let current = entry.get();
let stale = current.moved.load(Ordering::Acquire)
|| (!held(current) && now.saturating_sub(current.seen()) >= KEPT_FOR_MS);
if !stale {
current.touch(now);
return (Arc::clone(current), true);
}
let slot = Arc::new(Slot::new(now));
entry.insert(Arc::clone(&slot));
(slot, false)
}
Entry::Vacant(entry) => {
let slot = Arc::new(Slot::new(now));
entry.insert(Arc::clone(&slot));
(slot, false)
}
}
}
pub(crate) fn hand_over(&self, user: Option<&str>, producer: &str) -> Option<Decided> {
let key = (user.map(Box::from), Box::from(producer));
loop {
let slot = self.slots.get(&key).map(|slot| Arc::clone(&slot))?;
let mut state = slot.lock();
match self.slots.get(&key) {
None => return None,
Some(current) if !Arc::ptr_eq(¤t, &slot) => continue,
Some(_) => {}
}
slot.moved.store(true, Ordering::Release);
return Some(state.hand_over());
}
}
fn link(
&self,
user: Option<&str>,
hello: &Hello,
last: LastNode<'_>,
now: u64,
) -> (Link, Vec<Hole>) {
loop {
let (slot, known) = self.attach(user, &hello.producer, now);
let mut state = slot.lock();
if state.moved {
continue;
}
let remembered = match last {
LastNode::Here => known,
LastNode::Peer(Some(decided)) => {
state.advance(decided);
true
}
LastNode::Peer(None) => false,
};
let (start, unsure, told) = if remembered {
(
state.decided_for(hello.from),
state.cannot_tell(hello.from),
state.told_from(hello.from),
)
} else {
state.unsure_up_to(hello.written);
(0, hello.written, Vec::new())
};
let owner = state.take();
drop(state);
return (
Link {
slot,
start,
unsure,
owner,
},
told,
);
}
}
pub(crate) fn sweep(&self, now: u64) {
self.slots
.retain(|_, slot| held(slot) || now.saturating_sub(slot.seen()) < KEPT_FOR_MS);
}
pub(crate) fn over(&self, connections: usize) -> bool {
self.slots.len() > self.limit.saturating_add(connections)
}
pub(crate) fn bound(&self, connections: usize) {
if !self.over(connections) {
return;
}
let mut idle: Vec<u64> = self
.slots
.iter()
.filter(|entry| !held(entry.value()))
.map(|entry| entry.value().seen())
.collect();
if idle.len() > self.limit {
let over = idle.len() - self.limit;
let (_, &mut cutoff, _) = idle.select_nth_unstable(over - 1);
self.slots
.retain(|_, slot| held(slot) || slot.seen() > cutoff);
}
}
}
enum LastNode<'a> {
Here,
Peer(Option<&'a Decided>),
}
#[derive(Debug, PartialEq, Eq)]
pub(crate) struct Hello {
pub(crate) producer: Box<str>,
pub(crate) node: Option<Box<str>>,
pub(crate) written: u64,
pub(crate) from: u64,
}
impl Hello {
pub(crate) fn parse(p: Option<&serde_json::Value>) -> Option<Self> {
let outbox = p?.get("outbox")?;
let producer = outbox.get("producer")?.as_str()?;
if producer.is_empty() || producer.len() > MAX_ID_LEN {
return None;
}
let number = |name: &str| {
outbox
.get(name)
.and_then(serde_json::Value::as_u64)
.unwrap_or(0)
};
Some(Self {
producer: producer.into(),
node: outbox
.get("node")
.and_then(serde_json::Value::as_str)
.filter(|n| !n.is_empty() && n.len() <= MAX_ID_LEN)
.map(Box::from),
written: number("written"),
from: number("from"),
})
}
}
pub(crate) struct Link {
pub(crate) slot: Arc<Slot>,
pub(crate) start: u64,
pub(crate) unsure: u64,
pub(crate) owner: u64,
}
impl Drop for Link {
fn drop(&mut self) {
self.slot.touch(now_ms());
}
}
#[derive(Default)]
pub(crate) struct Holder {
pub(crate) hello: OnceLock<Hello>,
pub(crate) link: OnceLock<Link>,
started: AtomicBool,
}
impl Holder {
pub(crate) fn hello(&self, p: Option<&serde_json::Value>) {
if self.hello.get().is_none()
&& let Some(hello) = Hello::parse(p)
{
let _ = self.hello.set(hello);
}
}
fn begin(&self) -> Option<&Hello> {
let hello = self.hello.get()?;
(!self.started.swap(true, Ordering::AcqRel)).then_some(hello)
}
}
pub(crate) fn now_ms() -> u64 {
std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.map_or(0, |d| u64::try_from(d.as_millis()).unwrap_or(u64::MAX))
}
pub(crate) fn start(state: &Arc<SharedState>, handle: &ConnectionHandle, user: Option<&str>) {
let Some(hello) = handle.out.acks.begin() else {
return;
};
let last = hello
.node
.as_deref()
.filter(|last| *last != &*state.node_id);
if let Some(last) = last
&& hello.written > 0
&& state.producer_links.reaches(last)
{
let (state, handle) = (Arc::clone(state), handle.clone());
let (user, last) = (user.map(str::to_owned), last.to_owned());
tokio::spawn(async move {
let Some(hello) = handle.out.acks.hello.get() else {
return;
};
let decided = state
.producer_links
.ask(&last, user.as_deref(), &hello.producer, ASK_WITHIN)
.await;
let (link, told) = state.producers.link(
user.as_deref(),
hello,
LastNode::Peer(decided.as_ref()),
now_ms(),
);
finish(&state, &handle, link, &told);
});
return;
}
let last = if last.is_none() {
LastNode::Here
} else {
LastNode::Peer(None)
};
let (link, told) = state.producers.link(user, hello, last, now_ms());
finish(state, handle, link, &told);
}
fn finish(state: &SharedState, handle: &ConnectionHandle, link: Link, told: &[Hole]) {
let reply = outbox_reply(link.start, &state.node_id, told, link.unsure);
let _ = handle.out.acks.link.set(link);
handle.send_control(Message::Text(reply.into()));
}
fn outbox_reply(acked: u64, node: &str, refused: &[Hole], unsure: u64) -> String {
let mut p = serde_json::json!({"acked": acked, "node": node});
if unsure > acked {
p["unsure"] = unsure.into();
}
if !refused.is_empty() {
p["refused"] = refused
.iter()
.map(|hole| {
let mut refusal = serde_json::json!({"s": hole.to, "code": hole.why.as_str()});
if hole.from != hole.to {
refusal["from"] = hole.from.into();
}
refusal
})
.collect();
}
serde_json::json!({"c": "WSE", "t": "outbox", "p": p, "v": 1}).to_string()
}
pub(crate) fn seq_of(val: &serde_json::Value) -> Option<u64> {
val.get("s")
.and_then(serde_json::Value::as_u64)
.filter(|s| *s > 0 && *s < u64::MAX)
}
pub(crate) fn number_in(frame: &[u8]) -> Option<u64> {
if let Some(packed) = frame.strip_prefix(b"M:") {
return number_in_msgpack(packed);
}
let frame = frame
.strip_prefix(b"WSE")
.or_else(|| frame.strip_prefix(b"S"))
.or_else(|| frame.strip_prefix(b"U"))
.unwrap_or(frame);
let digits = frame.strip_prefix(b"{\"s\":")?;
let end = digits.iter().position(|b| !b.is_ascii_digit())?;
if end == 0 || end > 19 || !matches!(digits[end], b',' | b'}') {
return None;
}
let s: u64 = std::str::from_utf8(&digits[..end]).ok()?.parse().ok()?;
(s > 0).then_some(s)
}
fn number_in_msgpack(map: &[u8]) -> Option<u64> {
let (&head, rest) = map.split_first()?;
let rest = match head {
0x81..=0x8f => rest,
0xde => rest.get(2..)?,
0xdf => rest.get(4..)?,
_ => return None,
};
let rest = rest.strip_prefix(&[0xa1, b's'])?;
let (&tag, value) = rest.split_first()?;
let s = match tag {
0x00..=0x7f => u64::from(tag),
0xcc => u64::from(*value.first()?),
0xcd => u64::from(u16::from_be_bytes(value.get(..2)?.try_into().ok()?)),
0xce => u64::from(u32::from_be_bytes(value.get(..4)?.try_into().ok()?)),
0xcf => u64::from_be_bytes(value.get(..8)?.try_into().ok()?),
_ => return None,
};
(s > 0).then_some(s)
}
#[derive(Default)]
pub(crate) struct Pending {
ack: u64,
nacks: Vec<(u64, u64, Refusal)>,
dropped: bool,
}
impl Pending {
pub(crate) fn due(&self) -> bool {
self.ack > 0 || !self.nacks.is_empty()
}
pub(crate) fn dropped(&mut self) {
self.dropped = true;
}
pub(crate) fn skipped(&mut self) -> Refusal {
if std::mem::take(&mut self.dropped) {
Refusal::RateLimited
} else {
Refusal::Missing
}
}
pub(crate) fn taken(&mut self, s: u64) {
self.ack = self.ack.max(s);
}
pub(crate) fn refuse(&mut self, from: u64, to: u64, why: Refusal) {
if let Some(last) = self.nacks.last_mut()
&& last.2 == why
&& last.1 + 1 == from
{
last.1 = to;
return;
}
self.nacks.push((from, to, why));
}
pub(crate) fn answers(&mut self) -> impl Iterator<Item = String> + '_ {
let ack = std::mem::take(&mut self.ack);
self.nacks
.drain(..)
.map(|(from, to, why)| nack(from, to, why.as_str()))
.chain((ack > 0).then(|| format!(r#"{{"c":"WSE","t":"ack","p":{{"s":{ack}}},"v":1}}"#)))
}
}
fn nack(from: u64, to: u64, why: &str) -> String {
if from == to {
format!(r#"{{"c":"WSE","t":"nack","p":{{"s":{to},"code":"{why}"}},"v":1}}"#)
} else {
format!(r#"{{"c":"WSE","t":"nack","p":{{"from":{from},"s":{to},"code":"{why}"}},"v":1}}"#)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn claim(slot: &Slot, s: u64) -> Claim {
slot.lock().claim(s, Refusal::Missing)
}
#[test]
fn a_message_is_handed_on_once() {
let slot = Slot::new(0);
assert_eq!(
claim(&slot, 1),
Claim::First {
gap: None,
unsure: false
}
);
assert_eq!(claim(&slot, 1), Claim::Repeat);
assert_eq!(
claim(&slot, 3),
Claim::First {
gap: Some((2, 2)),
unsure: false
}
);
assert_eq!(
claim(&slot, 2),
Claim::Refused(Refusal::Missing),
"skipped: refused again"
);
assert_eq!(
slot.lock().hand_over(),
Decided {
mark: 3,
holes: vec![Hole {
from: 2,
to: 2,
why: Refusal::Missing
}],
..Decided::default()
}
);
assert_eq!(claim(&slot, 4), Claim::Moved);
assert_eq!(slot.lock().mark(), 3);
}
#[test]
fn a_refused_message_stays_refused_until_the_client_heard() {
let slot = Slot::new(0);
let mut state = slot.lock();
assert_eq!(
state.claim(1, Refusal::Missing),
Claim::First {
gap: None,
unsure: false
}
);
state.refuse(1, 1, Refusal::Busy);
assert_eq!(
state.claim(2, Refusal::Missing),
Claim::First {
gap: None,
unsure: false
}
);
state.refuse(2, 2, Refusal::Busy);
assert_eq!(
state.claim(3, Refusal::Missing),
Claim::First {
gap: None,
unsure: false
}
);
assert_eq!(
state.claim(1, Refusal::Missing),
Claim::Refused(Refusal::Busy)
);
assert_eq!(state.claim(3, Refusal::Missing), Claim::Repeat);
assert_eq!(
state.told_from(0),
[Hole {
from: 1,
to: 2,
why: Refusal::Busy
}],
"one run"
);
assert!(state.told_from(3).is_empty());
assert_eq!(state.claim(1, Refusal::Missing), Claim::Repeat);
}
#[test]
fn a_refusal_forgotten_past_the_bound_is_never_taken_for_a_take() {
let slot = Slot::new(0);
let mut state = slot.lock();
for n in 0..(MAX_HOLES as u64 + 1) {
let refused = 2 * n + 1;
state.claim(refused, Refusal::Missing);
state.refuse(refused, refused, Refusal::Busy);
state.claim(refused + 1, Refusal::Missing);
}
assert_eq!(state.holes.len(), MAX_HOLES);
assert_eq!(state.claim(1, Refusal::Missing), Claim::Unsure);
assert_eq!(
state.claim(3, Refusal::Missing),
Claim::Refused(Refusal::Busy)
);
assert_eq!(state.claim(2, Refusal::Missing), Claim::Repeat);
let last = 2 * MAX_HOLES as u64 + 2;
assert_eq!(state.claim(last, Refusal::Missing), Claim::Repeat);
}
#[test]
fn a_decision_whose_handler_never_ended_is_not_said_taken() {
let slot = Slot::new(0);
let mut state = slot.lock();
assert_eq!(
state.claim(1, Refusal::Missing),
Claim::First {
gap: None,
unsure: false
}
);
state.deciding(1);
state.decided(1);
assert_eq!(
state.claim(2, Refusal::Missing),
Claim::First {
gap: None,
unsure: false
}
);
state.deciding(2);
assert_eq!(state.acked(), 1, "a client that comes back is told 1");
assert_eq!(state.claim(2, Refusal::Missing), Claim::Unsure);
state.deciding(2);
state.decided(2);
assert_eq!(state.acked(), 2);
assert_eq!(state.claim(2, Refusal::Missing), Claim::Repeat);
}
#[test]
fn a_refusal_of_one_the_server_could_not_tell_keeps_its_place() {
let slot = Slot::new(0);
let mut state = slot.lock();
for n in 0..(MAX_HOLES as u64 + 1) {
let refused = 2 * n + 1;
state.claim(refused, Refusal::Missing);
state.refuse(refused, refused, Refusal::Busy);
state.claim(refused + 1, Refusal::Missing);
}
assert_eq!(state.claim(1, Refusal::Missing), Claim::Unsure);
state.refuse(1, 1, Refusal::NotReady);
assert_eq!(
state.claim(1, Refusal::Missing),
Claim::Refused(Refusal::NotReady)
);
assert_eq!(
state.claim(5, Refusal::Missing),
Claim::Refused(Refusal::Busy)
);
let last = 2 * MAX_HOLES as u64 + 1;
assert_eq!(
state.claim(last, Refusal::Missing),
Claim::Refused(Refusal::Busy)
);
}
#[test]
fn a_client_that_makes_numbers_up_is_kept_within_bounds() {
let slot = Slot::new(0);
let mut state = slot.lock();
for n in 0..(MAX_HOLES as u64 + 10) {
state.claim(2 * n + 2, Refusal::Missing);
}
assert_eq!(state.holes.len(), MAX_HOLES);
}
#[test]
fn a_producer_is_one_users() {
let producers = Producers::default();
let (ann, known) = producers.attach(Some("ann"), "p1", 0);
assert!(!known);
claim(&ann, 5);
let (again, known) = producers.attach(Some("ann"), "p1", 0);
assert!(known);
assert_eq!(again.lock().mark(), 5);
let (bob, known) = producers.attach(Some("bob"), "p1", 0);
assert!(!known, "another user's producer of the same name");
assert_eq!(bob.lock().mark(), 0);
let handed = producers.hand_over(Some("ann"), "p1").unwrap();
assert_eq!(handed.mark, 5);
assert_eq!(
handed.holes,
[Hole {
from: 1,
to: 4,
why: Refusal::Missing
}]
);
assert_eq!(producers.hand_over(Some("cy"), "p1"), None);
let (back, known) = producers.attach(Some("ann"), "p1", 0);
assert!(!known);
assert_eq!(back.lock().mark(), 0);
}
#[test]
fn a_message_on_a_connection_the_client_left_is_not_taken() {
let producers = Producers::default();
let hello = |written| Hello {
producer: Box::from("p"),
node: None,
written,
from: 1,
};
let (old, _) = producers.link(None, &hello(0), LastNode::Here, 0);
assert!(matches!(
old.slot.lock().claim_by(old.owner, 1, Refusal::Missing),
Claim::First { .. }
));
let (new, _) = producers.link(None, &hello(2), LastNode::Here, 0);
assert_eq!(new.start, 1);
assert_eq!(
old.slot.lock().claim_by(old.owner, 2, Refusal::Missing),
Claim::Left
);
assert!(matches!(
new.slot.lock().claim_by(new.owner, 2, Refusal::Missing),
Claim::First { .. }
));
}
#[test]
fn a_producer_whose_connection_is_open_is_kept_however_long_it_is_silent() {
let producers = Producers::default();
let (link, _) = producers.link(None, &hello("here", 0), LastNode::Here, 0);
producers.sweep(3 * KEPT_FOR_MS);
let (again, known) = producers.attach(None, "p", 3 * KEPT_FOR_MS);
assert!(known);
assert!(Arc::ptr_eq(&link.slot, &again));
drop(again);
let before = now_ms();
drop(link);
producers.sweep(before + KEPT_FOR_MS - 1);
assert!(producers.hand_over(None, "p").is_some());
}
#[test]
fn a_silent_producer_is_forgotten_after_a_day() {
let producers = Producers::default();
drop(producers.attach(None, "p", 0));
producers.sweep(KEPT_FOR_MS - 1);
assert_eq!(producers.slots.len(), 1);
producers.sweep(KEPT_FOR_MS);
assert_eq!(producers.slots.len(), 0);
}
#[test]
fn a_producer_past_its_day_is_not_resumed_before_the_next_sweep() {
let producers = Producers::default();
drop(producers.attach(None, "p", 0));
assert!(!producers.attach(None, "p", KEPT_FOR_MS).1);
}
#[test]
fn past_the_bound_the_longest_disconnected_are_forgotten() {
let producers = Producers::with_limit(2);
let (held, _) = producers.attach(Some("held"), "p", 0);
for (at, user) in [(10, "ann"), (11, "bob"), (12, "cy")] {
drop(producers.attach(Some(user), "p", at));
}
producers.bound(0);
assert!(producers.hand_over(Some("ann"), "p").is_none());
for user in ["held", "bob", "cy"] {
assert!(producers.hand_over(Some(user), "p").is_some(), "{user}");
}
drop(held);
}
#[test]
fn a_producer_is_held_until_its_last_connection_ends() {
let producers = Producers::with_limit(1);
let (first, _) = producers.link(Some("ann"), &hello("here", 0), LastNode::Here, 1);
let (second, _) = producers.link(Some("ann"), &hello("here", 0), LastNode::Here, 1);
drop(first);
for (at, user) in [(2, "bob"), (3, "cy")] {
drop(producers.attach(Some(user), "p", at));
}
producers.bound(0);
assert!(producers.hand_over(Some("bob"), "p").is_none());
assert!(producers.hand_over(Some("ann"), "p").is_some(), "held");
drop(second);
}
#[test]
fn the_pass_counts_the_connections_out() {
let producers = Producers::with_limit(2);
let held: Vec<_> = (0..3)
.map(|n| producers.attach(None, &format!("h{n}"), 0).0)
.collect();
for (at, name) in [(1, "i0"), (2, "i1")] {
drop(producers.attach(None, name, at));
}
producers.bound(3);
assert_eq!(producers.slots.len(), 5);
drop(producers.attach(None, "i2", 3));
producers.bound(3);
assert_eq!(producers.slots.len(), 5);
assert!(producers.hand_over(None, "i0").is_none());
drop(held);
}
#[test]
fn a_node_keeps_twice_its_connections_when_that_is_more() {
assert_eq!(idle_limit(1_000), MAX_IDLE);
assert_eq!(idle_limit(500_000), 1_000_000);
assert_eq!(idle_limit(usize::MAX), usize::MAX);
}
#[test]
fn a_query_waiting_on_a_replaced_slot_hands_over_the_current_one() {
use std::time::{Duration, Instant};
let producers = Producers::default();
let (old, _) = producers.attach(None, "p", 0);
let deciding = old.lock();
std::thread::scope(|scope| {
let query = scope.spawn(|| producers.hand_over(None, "p").unwrap());
let deadline = Instant::now() + Duration::from_secs(5);
while Arc::strong_count(&old) < 3 {
assert!(Instant::now() < deadline);
std::thread::yield_now();
}
old.moved.store(true, Ordering::Release);
let (current, known) = producers.attach(None, "p", 0);
assert!(!known);
claim(¤t, 2);
drop(deciding);
assert_eq!(query.join().unwrap().mark, 2);
assert_eq!(claim(¤t, 3), Claim::Moved);
});
}
#[test]
fn a_reconnect_waiting_on_a_handover_takes_the_replacement_slot() {
use std::time::{Duration, Instant};
let producers = Producers::default();
let (old, _) = producers.attach(None, "p", 0);
let mut decision = old.lock();
std::thread::scope(|scope| {
let back = scope.spawn(|| producers.link(None, &hello("here", 1), LastNode::Here, 0).0);
let deadline = Instant::now() + Duration::from_secs(5);
while Arc::strong_count(&old) < 3 {
assert!(Instant::now() < deadline);
std::thread::yield_now();
}
old.moved.store(true, Ordering::Release);
decision.hand_over();
drop(decision);
let back = back.join().unwrap();
assert_eq!(
claim(&back.slot, 1),
Claim::First {
gap: None,
unsure: true
}
);
});
}
#[test]
fn the_hello_names_the_producer_and_what_was_written() {
let p = serde_json::json!({"outbox": {"producer": "abc", "node": "n1", "written": 7, "from": 5}});
assert_eq!(
Hello::parse(Some(&p)),
Some(Hello {
producer: "abc".into(),
node: Some("n1".into()),
written: 7,
from: 5,
})
);
let long = "x".repeat(MAX_ID_LEN + 1);
let p = serde_json::json!({"outbox": {"producer": long}});
assert_eq!(Hello::parse(Some(&p)), None);
assert_eq!(Hello::parse(Some(&serde_json::json!({}))), None);
}
fn hello(node: &str, written: u64) -> Hello {
Hello {
producer: "p".into(),
node: Some(node.into()),
written,
from: 0,
}
}
#[test]
fn a_client_from_another_node_is_unsure_up_to_what_it_wrote() {
let producers = Arc::new(Producers::default());
let (link, _) = producers.link(Some("ann"), &hello("other", 4), LastNode::Peer(None), 0);
assert_eq!((link.start, link.slot.lock().unsure), (0, 4));
{
let mut state = link.slot.lock();
state.claim(9, Refusal::Missing);
state.refuse(9, 9, Refusal::Busy);
}
let (link, told) = producers.link(Some("ann"), &hello("here", 11), LastNode::Here, 0);
assert_eq!((link.start, link.slot.lock().unsure), (9, 4));
assert_eq!(
told,
[
Hole {
from: 1,
to: 8,
why: Refusal::Missing
},
Hole {
from: 9,
to: 9,
why: Refusal::Busy
},
]
);
}
#[test]
fn what_the_last_node_decided_counts_here() {
let producers = Arc::new(Producers::default());
let holes = vec![Hole {
from: 7,
to: 7,
why: Refusal::Busy,
}];
let decided = Decided {
mark: 10,
holes: holes.clone(),
..Decided::default()
};
let (link, told) = producers.link(
Some("ann"),
&hello("other", 12),
LastNode::Peer(Some(&decided)),
0,
);
assert_eq!((link.start, link.slot.lock().unsure), (10, 0));
assert_eq!(told, holes);
assert_eq!(claim(&link.slot, 10), Claim::Repeat);
assert_eq!(claim(&link.slot, 7), Claim::Refused(Refusal::Busy));
assert_eq!(
claim(&link.slot, 11),
Claim::First {
gap: None,
unsure: false
}
);
let (link, told) =
producers.link(Some("bob"), &hello("other", 12), LastNode::Peer(None), 0);
assert_eq!((link.start, link.slot.lock().unsure), (0, 12));
assert!(told.is_empty());
}
#[test]
fn a_client_back_is_told_how_far_the_server_cannot_tell() {
let producers = Arc::new(Producers::default());
let (link, _) = producers.link(Some("ann"), &hello("here", 0), LastNode::Here, 0);
link.slot.lock().claim(1, Refusal::Missing);
let (link, _) = producers.link(Some("ann"), &hello("here", 3), LastNode::Here, 0);
assert_eq!((link.start, link.unsure), (1, 0));
let reply: serde_json::Value =
serde_json::from_str(&outbox_reply(link.start, "n", &[], link.unsure)).unwrap();
assert_eq!(reply["p"], serde_json::json!({"acked": 1, "node": "n"}));
let (link, _) = producers.link(Some("bob"), &hello("other", 3), LastNode::Peer(None), 0);
assert_eq!((link.start, link.unsure), (0, 3));
let reply: serde_json::Value =
serde_json::from_str(&outbox_reply(link.start, "n", &[], link.unsure)).unwrap();
assert_eq!(reply["p"]["unsure"], 3);
let (link, _) = producers.link(Some("cid"), &hello("here", 0), LastNode::Here, 0);
{
let mut state = link.slot.lock();
state.claim(1, Refusal::Missing);
state.deciding(1);
}
let (link, _) = producers.link(Some("cid"), &hello("here", 2), LastNode::Here, 0);
assert_eq!((link.start, link.unsure), (0, 1));
}
fn past_the_bound(state: &mut SlotState) -> u64 {
for n in 0..(MAX_HOLES as u64 + 1) {
let refused = 2 * n + 1;
state.claim(refused, Refusal::Missing);
state.refuse(refused, refused, Refusal::Busy);
state.claim(refused + 1, Refusal::Missing);
}
2 * MAX_HOLES as u64 + 2
}
#[test]
fn a_client_waiting_for_a_refusal_let_go_is_not_told_it_was_taken() {
let producers = Arc::new(Producers::default());
let (link, _) = producers.link(Some("ann"), &hello("here", 0), LastNode::Here, 0);
let last = past_the_bound(&mut link.slot.lock());
let comes_back = |from| Hello {
from,
..hello("here", last)
};
let (link, told) = producers.link(Some("ann"), &comes_back(1), LastNode::Here, 0);
assert_eq!(link.start, 0);
assert_eq!(told.len(), MAX_HOLES);
assert_eq!(claim(&link.slot, 1), Claim::Unsure);
let (link, _) = producers.link(Some("ann"), &comes_back(2), LastNode::Here, 0);
assert_eq!(link.start, last);
}
#[test]
fn what_the_last_node_could_not_tell_it_cannot_tell_here_either() {
let a = Arc::new(Producers::default());
let (link, _) = a.link(Some("ann"), &hello("a", 0), LastNode::Here, 0);
let last = {
let mut state = link.slot.lock();
let last = past_the_bound(&mut state);
state.claim(last + 1, Refusal::Missing);
state.deciding(last + 1);
last
};
let decided = a.hand_over(Some("ann"), "p").unwrap();
assert_eq!((decided.forgot, decided.undecided), (1, Some(last + 1)));
let b = Arc::new(Producers::default());
let comes = Hello {
from: 1,
..hello("a", last + 1)
};
let (link, told) = b.link(Some("ann"), &comes, LastNode::Peer(Some(&decided)), 0);
assert_eq!(link.start, 0, "1 may have been refused");
assert_eq!(told.len(), MAX_HOLES);
assert_eq!(claim(&link.slot, 1), Claim::Unsure);
assert_eq!(claim(&link.slot, 2), Claim::Repeat);
assert_eq!(
claim(&link.slot, last + 1),
Claim::Unsure,
"may have done its work"
);
let c = Arc::new(Producers::default());
let comes = Hello {
from: last + 1,
..hello("a", last + 1)
};
let (link, _) = c.link(Some("ann"), &comes, LastNode::Peer(Some(&decided)), 0);
assert_eq!(link.start, last);
assert_eq!(claim(&link.slot, last + 1), Claim::Unsure);
}
#[test]
fn the_hello_starts_the_producer_once() {
let holder = Holder::default();
assert!(holder.begin().is_none(), "no hello yet");
holder.hello(Some(&serde_json::json!({"outbox": {"producer": "p"}})));
assert!(holder.begin().is_some());
assert!(holder.begin().is_none(), "once");
}
#[test]
fn the_answer_tells_the_refusals_the_client_may_not_have_heard_of() {
let reply: serde_json::Value = serde_json::from_str(&outbox_reply(5, "n", &[], 0)).unwrap();
assert_eq!(
reply,
serde_json::json!({"c": "WSE", "t": "outbox", "p": {"acked": 5, "node": "n"}, "v": 1})
);
let refused = [
Hole {
from: 2,
to: 3,
why: Refusal::RateLimited,
},
Hole {
from: 5,
to: 5,
why: Refusal::Busy,
},
];
let reply: serde_json::Value =
serde_json::from_str(&outbox_reply(5, "n", &refused, 0)).unwrap();
assert_eq!(
reply["p"]["refused"],
serde_json::json!([
{"from": 2, "s": 3, "code": "rate_limited"},
{"s": 5, "code": "busy"},
])
);
}
#[test]
fn the_number_is_read_from_the_first_bytes() {
assert_eq!(number_in(br#"{"s":17,"t":"m"}"#), Some(17));
assert_eq!(number_in(br#"{"s":3}"#), Some(3));
assert_eq!(number_in(br#"WSE{"s":4,"t":"m"}"#), Some(4));
assert_eq!(number_in(br#"{"t":"m","s":17}"#), None, "not first");
assert_eq!(number_in(br#"{"s":0,"t":"m"}"#), None);
assert_eq!(number_in(br#"{"s":17"#), None, "cut short");
assert_eq!(number_in(br#"{"s":99999999999999999999,"t":"m"}"#), None);
assert_eq!(number_in(b""), None);
assert_eq!(number_in(b"M:\x82\xa1s\x11\xa1t\xa1m"), Some(17));
assert_eq!(number_in(b"M:\x81\xa1s\xcc\xc8"), Some(200));
assert_eq!(number_in(b"M:\x81\xa1s\xcd\x01\x00"), Some(256));
assert_eq!(number_in(b"M:\x81\xa1s\xce\x00\x01\x00\x00"), Some(65_536));
let mut wide = b"M:\x81\xa1s\xcf".to_vec();
wide.extend_from_slice(&(1u64 << 40).to_be_bytes());
assert_eq!(number_in(&wide), Some(1 << 40));
assert_eq!(number_in(b"M:\xde\x00\x01\xa1s\x05"), Some(5));
assert_eq!(number_in(b"M:\x82\xa1t\xa1m\xa1s\x11"), None, "not first");
assert_eq!(number_in(b"M:\x81\xa1s\x00"), None);
assert_eq!(number_in(b"M:\x81\xa1s\xce\x00\x01"), None, "cut short");
assert_eq!(number_in(b"M:\x81\xa1s\xa1x"), None, "not a number");
assert_eq!(number_in(b"M:\x80"), None);
}
#[test]
fn answers_put_refusals_before_the_ack() {
let mut pending = Pending::default();
pending.taken(1);
pending.dropped();
let why = pending.skipped();
pending.refuse(2, 3, why);
pending.taken(4);
pending.refuse(5, 5, Refusal::Busy);
let answers: Vec<String> = pending.answers().collect();
assert_eq!(
answers,
[
r#"{"c":"WSE","t":"nack","p":{"from":2,"s":3,"code":"rate_limited"},"v":1}"#,
r#"{"c":"WSE","t":"nack","p":{"s":5,"code":"busy"},"v":1}"#,
r#"{"c":"WSE","t":"ack","p":{"s":4},"v":1}"#,
]
);
assert!(!pending.due());
assert_eq!(pending.skipped(), Refusal::Missing);
}
}