use core::cell::{Cell, RefCell};
use core::future::{Future, poll_fn};
use core::task::Poll;
use heapless::Deque;
use super::{Clock, Duration, Granularity, Instant, KvStore, PeerAddr, Rng, Timer, Udp};
use crate::error::{Error, ErrorCode, Result};
const QUEUE: usize = 32;
const MTU: usize = crate::config::MAX_UDP_MESSAGE;
const NODES: usize = 8;
const KV_ENTRIES: usize = 32;
const KV_VALUE: usize = 1024;
#[derive(Debug)]
pub struct SimRng {
state: Cell<u64>,
}
impl SimRng {
#[must_use]
pub const fn new(seed: u64) -> Self {
Self {
state: Cell::new(if seed == 0 {
0x9E37_79B9_7F4A_7C15
} else {
seed
}),
}
}
pub fn next(&self) -> u64 {
let mut x = self.state.get();
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.state.set(x);
x.wrapping_mul(0x2545_F491_4F6C_DD1D)
}
pub fn below(&self, bound: u32) -> u32 {
self.next()
.checked_rem(u64::from(bound))
.and_then(|v| u32::try_from(v).ok())
.unwrap_or(0)
}
pub fn chance(&self, percent: u8) -> bool {
self.below(100) < u32::from(percent)
}
}
impl Rng for SimRng {
fn fill(&self, out: &mut [u8]) -> Result<()> {
for chunk in out.chunks_mut(8) {
let bytes = self.next().to_le_bytes();
for (dst, src) in chunk.iter_mut().zip(bytes.iter()) {
*dst = *src;
}
}
Ok(())
}
}
#[derive(Debug, Clone, Copy, Default)]
pub struct Impairment {
pub loss_percent: u8,
pub duplicate_percent: u8,
pub latency: Duration,
pub jitter: Duration,
}
impl Impairment {
#[must_use]
pub const fn lossy(loss_percent: u8) -> Self {
Self {
loss_percent,
duplicate_percent: 0,
latency: Duration::ZERO,
jitter: Duration::ZERO,
}
}
#[must_use]
pub const fn jittery(latency: Duration, jitter: Duration) -> Self {
Self {
loss_percent: 0,
duplicate_percent: 0,
latency,
jitter,
}
}
}
#[derive(Debug)]
struct InFlight {
from: PeerAddr,
to_node: u8,
at: Instant,
len: usize,
data: [u8; MTU],
}
#[derive(Debug)]
pub struct SimNet {
now: Cell<Instant>,
rng: SimRng,
impairment: Cell<Impairment>,
flight: RefCell<Deque<InFlight, QUEUE>>,
deadlines: RefCell<Deque<Instant, QUEUE>>,
sent: Cell<u32>,
delivered: Cell<u32>,
dropped: Cell<u32>,
duplicated: Cell<u32>,
}
impl SimNet {
#[must_use]
pub fn new(seed: u64) -> Self {
Self {
now: Cell::new(Instant::ZERO),
rng: SimRng::new(seed),
impairment: Cell::new(Impairment::default()),
flight: RefCell::new(Deque::new()),
deadlines: RefCell::new(Deque::new()),
sent: Cell::new(0),
delivered: Cell::new(0),
dropped: Cell::new(0),
duplicated: Cell::new(0),
}
}
pub fn impair(&self, impairment: Impairment) {
self.impairment.set(impairment);
}
#[must_use]
pub fn node(&self, index: u8) -> SimNode<'_> {
SimNode { net: self, index }
}
#[must_use]
pub const fn rng(&self) -> &SimRng {
&self.rng
}
#[must_use]
pub fn sent(&self) -> u32 {
self.sent.get()
}
#[must_use]
pub fn delivered(&self) -> u32 {
self.delivered.get()
}
#[must_use]
pub fn dropped(&self) -> u32 {
self.dropped.get()
}
#[must_use]
pub fn duplicated(&self) -> u32 {
self.duplicated.get()
}
#[must_use]
pub fn now(&self) -> Instant {
self.now.get()
}
pub fn advance_to_next_event(&self) -> bool {
let mut next = Instant::MAX;
for d in self.deadlines.borrow().iter() {
if *d < next {
next = *d;
}
}
for f in self.flight.borrow().iter() {
if f.at < next {
next = f.at;
}
}
if next == Instant::MAX {
return false;
}
if next > self.now.get() {
self.now.set(next);
}
let mut kept: Deque<Instant, QUEUE> = Deque::new();
let now = self.now.get();
for d in self.deadlines.borrow().iter() {
if *d > now {
let _ = kept.push_back(*d);
}
}
*self.deadlines.borrow_mut() = kept;
true
}
pub fn advance(&self, d: Duration) {
let target = self.now.get().saturating_add(d);
while self.now.get() < target {
let before = self.now.get();
if !self.advance_to_next_event() || self.now.get() > target {
self.now.set(target);
return;
}
if self.now.get() == before {
self.now.set(target);
return;
}
}
}
fn register_deadline(&self, at: Instant) {
let mut d = self.deadlines.borrow_mut();
if d.iter().any(|x| *x == at) {
return;
}
let _ = d.push_back(at);
}
fn enqueue(&self, from: PeerAddr, to_node: u8, data: &[u8]) -> Result<()> {
self.sent.set(self.sent.get().saturating_add(1));
let imp = self.impairment.get();
if imp.loss_percent > 0 && self.rng.chance(imp.loss_percent) {
self.dropped.set(self.dropped.get().saturating_add(1));
return Ok(());
}
let copies = if imp.duplicate_percent > 0 && self.rng.chance(imp.duplicate_percent) {
self.duplicated.set(self.duplicated.get().saturating_add(1));
2
} else {
1
};
for _ in 0..copies {
let jitter = if imp.jitter == Duration::ZERO {
Duration::ZERO
} else {
let max = u32::try_from(imp.jitter.as_micros()).unwrap_or(u32::MAX);
Duration::from_micros(u64::from(self.rng.below(max)))
};
let at = self
.now
.get()
.saturating_add(imp.latency)
.saturating_add(jitter);
let Some(src) = data.get(..data.len().min(MTU)) else {
return Err(Error::new(ErrorCode::BufferTooSmall));
};
let mut buf = [0u8; MTU];
let Some(dst) = buf.get_mut(..src.len()) else {
return Err(Error::new(ErrorCode::BufferTooSmall));
};
dst.copy_from_slice(src);
let entry = InFlight {
from,
to_node,
at,
len: src.len(),
data: buf,
};
if self.flight.borrow_mut().push_back(entry).is_err() {
self.dropped.set(self.dropped.get().saturating_add(1));
return Ok(());
}
self.register_deadline(at);
}
Ok(())
}
fn dequeue(&self, node: u8, out: &mut [u8]) -> Option<(usize, PeerAddr)> {
let now = self.now.get();
let mut flight = self.flight.borrow_mut();
let mut best: Option<(usize, Instant)> = None;
for (i, f) in flight.iter().enumerate() {
if f.to_node == node && f.at <= now && best.is_none_or(|(_, at)| f.at < at) {
best = Some((i, f.at));
}
}
let (index, _) = best?;
let mut taken = None;
let len = flight.len();
for i in 0..len {
let Some(entry) = flight.pop_front() else {
break;
};
if i == index {
taken = Some(entry);
} else {
let _ = flight.push_back(entry);
}
}
let entry = taken?;
let n = entry.len.min(out.len());
let (Some(dst), Some(src)) = (out.get_mut(..n), entry.data.get(..n)) else {
return None;
};
dst.copy_from_slice(src);
self.delivered.set(self.delivered.get().saturating_add(1));
Some((n, entry.from))
}
}
impl Timer for SimNet {
fn now(&self) -> Instant {
self.now.get()
}
fn sleep_until(&self, deadline: Instant) -> impl Future<Output = ()> {
self.register_deadline(deadline);
poll_fn(move |_| {
if deadline.is_elapsed_at(self.now.get()) {
Poll::Ready(())
} else {
self.register_deadline(deadline);
Poll::Pending
}
})
}
}
impl Clock for SimNet {
fn utc(&self) -> Option<u64> {
const Y2024: u64 = 757_382_400_000_000;
Some(Y2024.saturating_add(self.now.get().as_micros()))
}
fn granularity(&self) -> Granularity {
Granularity::MicrosecondsGranularity
}
}
impl Rng for SimNet {
fn fill(&self, out: &mut [u8]) -> Result<()> {
self.rng.fill(out)
}
}
#[derive(Debug, Clone, Copy)]
pub struct SimNode<'a> {
net: &'a SimNet,
index: u8,
}
impl SimNode<'_> {
#[must_use]
pub fn addr(&self) -> PeerAddr {
let mut a = [0u8; 16];
a[0] = 0xfd;
a[15] = self.index;
PeerAddr::new(a)
}
#[must_use]
pub const fn net(&self) -> &SimNet {
self.net
}
fn node_of(addr: PeerAddr) -> Option<u8> {
if addr.addr[0] != 0xfd {
return None;
}
addr.addr.last().copied()
}
}
impl Udp for SimNode<'_> {
fn recv_from(&self, buf: &mut [u8]) -> impl Future<Output = Result<(usize, PeerAddr)>> {
poll_fn(move |_| match self.net.dequeue(self.index, buf) {
Some(v) => Poll::Ready(Ok(v)),
None => Poll::Pending,
})
}
fn send_to(&self, buf: &[u8], addr: PeerAddr) -> impl Future<Output = Result<()>> {
let result = match Self::node_of(addr) {
Some(to) if usize::from(to) < NODES => self.net.enqueue(self.addr(), to, buf),
_ => Ok(()),
};
core::future::ready(result)
}
}
#[derive(Debug, Default)]
pub struct SimKv {
entries:
RefCell<heapless::Vec<(heapless::String<64>, heapless::Vec<u8, KV_VALUE>), KV_ENTRIES>>,
}
impl SimKv {
#[must_use]
pub fn new() -> Self {
Self::default()
}
#[must_use]
pub fn len(&self) -> usize {
self.entries.borrow().len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.entries.borrow().is_empty()
}
}
impl KvStore for SimKv {
fn get(&self, key: &str, out: &mut [u8]) -> impl Future<Output = Result<Option<usize>>> {
let result = (|| {
let entries = self.entries.borrow();
let Some((_, value)) = entries.iter().find(|(k, _)| k.as_str() == key) else {
return Ok(None);
};
let Some(dst) = out.get_mut(..value.len()) else {
return Err(Error::new(ErrorCode::BufferTooSmall));
};
dst.copy_from_slice(value);
Ok(Some(value.len()))
})();
core::future::ready(result)
}
fn set(&self, key: &str, value: &[u8]) -> impl Future<Output = Result<()>> {
let result = (|| {
let mut entries = self.entries.borrow_mut();
let stored =
heapless::Vec::from_slice(value).map_err(|_| Error::new(ErrorCode::NoSpace))?;
if let Some((_, slot)) = entries.iter_mut().find(|(k, _)| k.as_str() == key) {
*slot = stored;
return Ok(());
}
let name =
heapless::String::try_from(key).map_err(|_| Error::new(ErrorCode::NoSpace))?;
entries
.push((name, stored))
.map_err(|_| Error::new(ErrorCode::NoSpace))
})();
core::future::ready(result)
}
fn remove(&self, key: &str) -> impl Future<Output = Result<()>> {
let mut entries = self.entries.borrow_mut();
if let Some(i) = entries.iter().position(|(k, _)| k.as_str() == key) {
entries.swap_remove(i);
}
core::future::ready(Ok(()))
}
fn remove_prefix(&self, prefix: &str) -> impl Future<Output = Result<()>> {
let mut entries = self.entries.borrow_mut();
entries.retain(|(k, _)| !k.as_str().starts_with(prefix));
core::future::ready(Ok(()))
}
}
#[allow(clippy::panic)]
pub fn block_on<F: Future>(net: &SimNet, fut: F) -> F::Output {
let waker = core::task::Waker::noop();
let mut cx = core::task::Context::from_waker(waker);
let mut fut = core::pin::pin!(fut);
loop {
match fut.as_mut().poll(&mut cx) {
Poll::Ready(v) => return v,
Poll::Pending => {
assert!(
net.advance_to_next_event(),
"simulated deadlock: the future is pending and nothing is scheduled"
);
}
}
}
}
#[cfg(test)]
#[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)]
mod tests {
use super::*;
#[test]
fn a_datagram_arrives() {
let net = SimNet::new(1);
let a = net.node(1);
let b = net.node(2);
block_on(&net, async {
a.send_to(b"hello", b.addr()).await.unwrap();
let mut buf = [0u8; 32];
let (n, from) = b.recv_from(&mut buf).await.unwrap();
assert_eq!(&buf[..n], b"hello");
assert_eq!(from, a.addr());
});
assert_eq!(net.delivered(), 1);
}
#[test]
fn virtual_time_costs_nothing() {
let net = SimNet::new(1);
let start = Timer::now(&net);
block_on(&net, async {
net.sleep(Duration::from_secs(3600)).await;
});
assert_eq!(
Timer::now(&net).saturating_duration_since(start),
Duration::from_secs(3600)
);
}
#[test]
fn loss_is_deterministic_for_a_seed() {
fn run(seed: u64) -> u32 {
let net = SimNet::new(seed);
net.impair(Impairment::lossy(50));
let a = net.node(1);
let b = net.node(2);
for _ in 0..100 {
let _ = block_on(&net, a.send_to(b"x", b.addr()));
}
net.dropped()
}
let first = run(7);
assert_eq!(first, run(7), "same seed, same drops");
assert!(first > 20 && first < 80, "about half of 100, got {first}");
}
#[test]
fn jitter_reorders() {
let net = SimNet::new(3);
net.impair(Impairment::jittery(
Duration::from_millis(10),
Duration::from_millis(50),
));
let a = net.node(1);
let b = net.node(2);
block_on(&net, async {
for i in 0u8..8 {
a.send_to(&[i], b.addr()).await.unwrap();
}
});
let mut order = heapless::Vec::<u8, 8>::new();
block_on(&net, async {
for _ in 0..8 {
let mut buf = [0u8; 4];
let (n, _) = b.recv_from(&mut buf).await.unwrap();
assert_eq!(n, 1);
let _ = order.push(buf[0]);
}
});
assert_eq!(order.len(), 8, "everything arrives");
assert_ne!(&order[..], &[0, 1, 2, 3, 4, 5, 6, 7], "but not in order");
}
#[test]
fn duplicates_are_delivered_twice() {
let net = SimNet::new(5);
net.impair(Impairment {
duplicate_percent: 100,
..Impairment::default()
});
let a = net.node(1);
let b = net.node(2);
block_on(&net, async {
a.send_to(b"x", b.addr()).await.unwrap();
let mut buf = [0u8; 4];
b.recv_from(&mut buf).await.unwrap();
b.recv_from(&mut buf).await.unwrap();
});
assert_eq!(net.delivered(), 2);
}
#[test]
fn the_key_value_store_round_trips() {
let net = SimNet::new(1);
let kv = SimKv::new();
block_on(&net, async {
let mut buf = [0u8; 32];
assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), None);
kv.set("fabrics", b"abc").await.unwrap();
assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), Some(3));
assert_eq!(&buf[..3], b"abc");
kv.set("fabrics", b"de").await.unwrap();
assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), Some(2));
kv.set("app/x", b"1").await.unwrap();
kv.remove_prefix("app/").await.unwrap();
assert_eq!(kv.get("app/x", &mut buf).await.unwrap(), None);
assert_eq!(kv.len(), 1);
kv.remove("fabrics").await.unwrap();
assert!(kv.is_empty());
});
}
#[test]
fn a_too_small_buffer_is_an_error() {
let net = SimNet::new(1);
let kv = SimKv::new();
block_on(&net, async {
kv.set("k", b"0123456789").await.unwrap();
let mut small = [0u8; 4];
assert_eq!(
kv.get("k", &mut small).await.unwrap_err().code(),
ErrorCode::BufferTooSmall
);
});
}
}