use rrkernel::ring;
use rrkernel::tcb::{TaskControlBlock, TaskState};
use std::ptr;
struct Node {
tcb: Box<TaskControlBlock>,
}
impl Node {
fn new(id: u32) -> Self {
let mut tcb = Box::new(TaskControlBlock {
sp: ptr::null_mut(),
stack_base: ptr::null_mut(),
stack_size: 0,
closure_block: ptr::null_mut(),
state: TaskState::Ready,
flags: 0,
next: ptr::null_mut(),
prev: ptr::null_mut(),
id,
slice_cycles: 0,
slices_run: 0,
switches: 0,
backend: ptr::null_mut(),
blocked_on: 0,
block_deadline: 0,
held_locks: [0; rrkernel::tcb::MAX_HELD_LOCKS],
held_count: 0,
});
let raw: *mut TaskControlBlock = &mut *tcb;
tcb.sp = raw as *mut u8;
Node { tcb }
}
fn ptr(&self) -> *mut TaskControlBlock {
&*self.tcb as *const TaskControlBlock as *mut TaskControlBlock
}
}
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
let mut x = self.0;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.0 = x;
x.wrapping_mul(0x2545_F491_4F6C_DD1D)
}
fn below(&mut self, n: usize) -> usize {
(self.next() % n as u64) as usize
}
}
fn runnable(state: TaskState) -> bool {
!matches!(state, TaskState::Dead | TaskState::Blocked)
}
fn model_next_runnable(order: &[usize], states: &[TaskState], from_pos: usize) -> Option<usize> {
let k = order.len();
for step in 1..=k {
let idx = (from_pos + step) % k;
if idx == from_pos {
break;
}
if runnable(states[order[idx]]) {
return Some(order[idx]);
}
}
if runnable(states[order[from_pos]]) {
Some(order[from_pos])
} else {
None
}
}
struct Model {
pool: Vec<Node>,
order: Vec<usize>,
states: Vec<TaskState>,
linked: Vec<bool>,
}
impl Model {
fn new(n: usize) -> Self {
Model {
pool: (0..n).map(|i| Node::new(i as u32 + 1)).collect(),
order: Vec::new(),
states: vec![TaskState::Ready; n],
linked: vec![false; n],
}
}
fn pos(&self, node: usize) -> Option<usize> {
self.order.iter().position(|&n| n == node)
}
fn verify(&self, seed: u64, step: usize, op: &str) -> Result<(), String> {
let ctx = format!("seed {seed:#x}, step {step}, after {op}");
if self.order.is_empty() {
for (i, n) in self.pool.iter().enumerate() {
if unsafe { (*n.ptr()).is_linked() } {
return Err(format!(
"{ctx}: node {i} is linked but the model says empty"
));
}
}
return Ok(());
}
let head = self.pool[self.order[0]].ptr();
let n = unsafe { ring::check(head) }.map_err(|e| format!("{ctx}: ring::check: {e}"))?;
if n != self.order.len() {
return Err(format!(
"{ctx}: ring::check says {n} nodes, model says {}",
self.order.len()
));
}
if unsafe { ring::len(head) } != self.order.len() {
return Err(format!("{ctx}: ring::len disagrees with ring::check"));
}
let mut walked = Vec::with_capacity(self.order.len());
let mut p = head;
loop {
let idx = unsafe { (*p).id } as usize - 1;
walked.push(idx);
p = unsafe { (*p).next };
if p.is_null() || p == head {
break;
}
}
if walked != self.order {
return Err(format!(
"{ctx}: ring order {walked:?} != model {:?}",
self.order
));
}
for (i, node) in self.pool.iter().enumerate() {
if unsafe { (*node.ptr()).is_linked() } != self.linked[i] {
return Err(format!(
"{ctx}: node {i} membership disagrees with the model"
));
}
}
for from_pos in 0..self.order.len() {
let from = self.pool[self.order[from_pos]].ptr();
let got = unsafe { ring::next_runnable(from) };
let got_id: Option<usize> = if got.is_null() {
None
} else {
Some(unsafe { (*got).id } as usize)
};
let want_id: Option<usize> =
model_next_runnable(&self.order, &self.states, from_pos).map(|idx| idx + 1);
if got_id != want_id {
return Err(format!(
"{ctx}: next_runnable from pos {from_pos}: got {got_id:?}, model says \
{want_id:?} (task ids; None means null)"
));
}
}
Ok(())
}
}
fn one_run(seed: u64, nodes: usize, steps: usize) -> Result<(), String> {
let mut rng = Rng(seed);
let mut m = Model::new(nodes);
for step in 0..steps {
if rng.below(10) < 7 {
let unlinked: Vec<usize> = (0..nodes).filter(|&i| !m.linked[i]).collect();
let linked: Vec<usize> = (0..nodes).filter(|&i| m.linked[i]).collect();
let do_insert = !unlinked.is_empty() && (linked.is_empty() || rng.below(2) == 0);
if do_insert {
let node = unlinked[rng.below(unlinked.len())];
let after = if linked.is_empty() {
None
} else {
Some(linked[rng.below(linked.len())])
};
let after_ptr = match after {
None => ptr::null_mut(),
Some(a) => m.pool[a].ptr(),
};
unsafe { ring::insert_after(after_ptr, m.pool[node].ptr()) };
match after {
None => m.order = vec![node],
Some(a) => {
let at = m.pos(a).unwrap();
m.order.insert(at + 1, node);
}
}
m.linked[node] = true;
m.verify(seed, step, &format!("insert node {node} after {after:?}"))?;
} else if !linked.is_empty() {
let node = linked[rng.below(linked.len())];
let at = m.pos(node).unwrap();
let successor = unsafe { ring::unlink(m.pool[node].ptr()) };
m.order.remove(at);
m.linked[node] = false;
let want = if m.order.is_empty() {
None
} else {
Some(m.order[at % m.order.len()])
};
let returned_ok = match want {
None => successor.is_null(),
Some(w) => successor == m.pool[w].ptr(),
};
if !returned_ok {
return Err(format!(
"seed {seed:#x}, step {step}, unlink node {node}: wrong successor returned"
));
}
m.verify(seed, step, &format!("unlink node {node}"))?;
}
} else {
let node = rng.below(nodes);
let state = match rng.below(4) {
0 => TaskState::Ready,
1 => TaskState::Running,
2 => TaskState::Blocked,
_ => TaskState::Dead,
};
m.states[node] = state;
unsafe { (*m.pool[node].ptr()).state = state };
m.verify(seed, step, &format!("set node {node} {state:?}"))?;
}
}
while !m.order.is_empty() {
let node = m.order[rng.below(m.order.len())];
unsafe { ring::unlink(m.pool[node].ptr()) };
let at = m.pos(node).unwrap();
m.order.remove(at);
m.linked[node] = false;
}
m.verify(seed, steps, "drain to empty")?;
Ok(())
}
#[test]
fn random_insert_unlink_state_sequences_keep_the_ring_consistent() {
let seeds = [
1u64,
0xDEAD_BEEF,
0x1234_5678_9ABC_DEF0,
0x5EED,
0xF00D,
42,
7919,
1_048_576,
];
for seed in seeds {
for nodes in [1usize, 2, 3, 7, 16] {
one_run(seed, nodes, 400).unwrap_or_else(|e| panic!("{e}"));
}
}
}
#[test]
fn first_runnable_from_skips_a_blocked_head() {
unsafe {
let a = Node::new(1); let b = Node::new(2);
ring::insert_after(ptr::null_mut(), a.ptr());
ring::insert_after(a.ptr(), b.ptr());
assert_eq!(ring::first_runnable_from(a.ptr()), a.ptr());
(*a.ptr()).state = TaskState::Blocked;
assert_eq!(ring::first_runnable_from(a.ptr()), b.ptr());
(*b.ptr()).state = TaskState::Blocked;
assert!(ring::first_runnable_from(a.ptr()).is_null());
(*a.ptr()).state = TaskState::Dead;
(*b.ptr()).state = TaskState::Ready;
assert_eq!(ring::first_runnable_from(a.ptr()), b.ptr());
assert!(ring::first_runnable_from(ptr::null_mut()).is_null());
}
}
#[test]
fn a_single_node_ring_is_its_own_successor_and_unlinks_to_nothing() {
unsafe {
let a = Node::new(1);
ring::insert_after(ptr::null_mut(), a.ptr());
assert_eq!((*a.ptr()).next, a.ptr(), "sole member points at itself");
assert_eq!((*a.ptr()).prev, a.ptr());
assert_eq!(ring::check(a.ptr()), Ok(1));
assert_eq!(ring::next_runnable(a.ptr()), a.ptr());
(*a.ptr()).state = TaskState::Blocked;
assert!(ring::next_runnable(a.ptr()).is_null());
(*a.ptr()).state = TaskState::Running;
assert_eq!(ring::unlink(a.ptr()), ptr::null_mut());
assert!(
!(*a.ptr()).is_linked(),
"unlinked node must not look linked"
);
}
}
#[test]
fn an_all_blocked_ring_reports_no_runnable_task() {
unsafe {
let a = Node::new(1);
let b = Node::new(2);
let c = Node::new(3);
ring::insert_after(ptr::null_mut(), a.ptr());
ring::insert_after(a.ptr(), b.ptr());
ring::insert_after(b.ptr(), c.ptr());
for p in [a.ptr(), b.ptr(), c.ptr()] {
(*p).state = TaskState::Blocked;
}
for p in [a.ptr(), b.ptr(), c.ptr()] {
assert!(
ring::next_runnable(p).is_null(),
"an all-blocked ring must report no runnable task"
);
}
assert_eq!(ring::check(a.ptr()), Ok(3));
}
}