use super::*;
use std::sync::Condvar;
impl Module {
pub(super) fn interest(&self, pids: &mut BTreeSet<u32>) {
pids.extend(self.pid);
for (root, command) in &self.roots {
pids.insert(root.pid);
pids.extend(command.members.iter().map(|(pid, _)| *pid));
pids.extend(command.previous_inside.iter().map(|(pid, _)| *pid));
pids.extend(command.cpu_floor.identities().map(|(pid, _)| pid));
#[cfg(windows)]
{
pids.extend(command.fixed_inside.iter().map(|(pid, _)| *pid));
pids.extend(command.fixed_outside.iter().map(|(pid, _)| *pid));
pids.extend(command.member_handles.keys().map(|(pid, _)| *pid));
pids.extend(command.pinned_cpu.iter().map(|((pid, _), _)| *pid));
pids.extend(command.exited_at.keys().map(|(pid, _)| *pid));
}
}
self.pending_pids(pids);
pids.extend(self.omitted.keys().map(|root| root.pid));
pids.extend(self.finished_live.keys().map(|root| root.pid));
pids.extend(self.cpu_floor.identities().map(|(pid, _)| pid));
pids.extend(self.cpu_model.identities().map(|(pid, _)| pid));
pids.extend(self.group_credit.identities().map(|(pid, _)| pid));
self.declaration_loss.root_pids(pids);
}
}
impl Tracker {
pub(super) fn interest(&self) -> Option<BTreeSet<u32>> {
let state = self.state.try_lock().ok()?;
let pids = self.state_interest(&state);
Some(pids)
}
pub(super) fn state_interest(&self, state: &State) -> BTreeSet<u32> {
let mut pids = BTreeSet::new();
for module in state.modules.values() {
module.interest(&mut pids);
}
for losses in self
.declaration_losses
.lock()
.unwrap_or_else(|p| p.into_inner())
.values()
{
losses.root_pids(&mut pids);
}
pids
}
}
pub(super) fn container_pids(target: &crate::subtree_resources::Target, pids: &mut BTreeSet<u32>) {
if target.has_container() {
pids.extend(target.process_ids().into_iter().flatten());
}
}
pub(super) fn declaration_pids(module_pid: u32, batch: &Declaration, pids: &mut BTreeSet<u32>) {
pids.insert(module_pid);
pids.extend(batch.started.iter().map(|root| root.pid));
pids.extend(batch.known.iter().flatten().map(|root| root.pid));
pids.extend(batch.finished.iter().map(|root| root.pid));
}
pub(super) fn covers(table: &ProcessTable, pids: &BTreeSet<u32>) -> bool {
pids.iter().all(|pid| table.covers(*pid))
}
pub(super) struct SharedReads<T> {
queue: Mutex<ReadQueue<T>>,
done: Condvar,
}
struct ReadQueue<T> {
reading: bool,
next: u64,
wanted: Option<BTreeSet<u32>>,
waiting: BTreeMap<u64, usize>,
results: BTreeMap<u64, T>,
}
impl<T> Default for SharedReads<T> {
fn default() -> Self {
Self {
queue: Mutex::new(ReadQueue {
reading: false,
next: 0,
wanted: Some(BTreeSet::new()),
waiting: BTreeMap::new(),
results: BTreeMap::new(),
}),
done: Condvar::new(),
}
}
}
impl<T> std::fmt::Debug for SharedReads<T> {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
formatter
.debug_struct("SharedReads")
.finish_non_exhaustive()
}
}
impl<T: Clone + Default> SharedReads<T> {
pub(super) fn read(
&self,
interest: Option<BTreeSet<u32>>,
read: impl FnOnce(Option<BTreeSet<u32>>) -> T,
) -> T {
let mut queue = self.queue.lock().unwrap_or_else(|p| p.into_inner());
let id = queue.next;
match (&mut queue.wanted, interest) {
(Some(wanted), Some(interest)) => wanted.extend(interest),
(wanted, _) => *wanted = None,
}
*queue.waiting.entry(id).or_default() += 1;
let mut read = Some(read);
loop {
if let Some(result) = queue.results.get(&id).cloned() {
let waiting = queue.waiting.entry(id).or_default();
*waiting -= 1;
if *waiting == 0 {
queue.waiting.remove(&id);
queue.results.remove(&id);
}
return result;
}
if !queue.reading && queue.next == id {
queue.reading = true;
queue.next += 1;
let wanted = queue.wanted.replace(BTreeSet::new());
drop(queue);
let mut finish = Finish {
reads: self,
id,
result: None,
};
let walk = read.take().expect("a caller starts at most one walk");
finish.result = Some(walk(wanted));
drop(finish);
queue = self.queue.lock().unwrap_or_else(|p| p.into_inner());
continue;
}
queue = self.done.wait(queue).unwrap_or_else(|p| p.into_inner());
}
}
}
struct Finish<'a, T: Default> {
reads: &'a SharedReads<T>,
id: u64,
result: Option<T>,
}
impl<T: Default> Drop for Finish<'_, T> {
fn drop(&mut self) {
let mut queue = self.reads.queue.lock().unwrap_or_else(|p| p.into_inner());
queue.reading = false;
match self.result.take() {
Some(result) => {
queue.results.insert(self.id, result);
}
None => {
let waiting = queue.waiting.entry(self.id).or_default();
*waiting = waiting.saturating_sub(1);
if *waiting == 0 {
queue.waiting.remove(&self.id);
} else {
queue.results.insert(self.id, T::default());
}
}
}
drop(queue);
self.reads.done.notify_all();
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::mpsc;
fn held(
started: mpsc::Sender<Option<BTreeSet<u32>>>,
release: Arc<Mutex<mpsc::Receiver<()>>>,
result: u32,
) -> impl FnOnce(Option<BTreeSet<u32>>) -> u32 {
move |interest| {
started.send(interest).unwrap();
release.lock().unwrap().recv().unwrap();
result
}
}
#[test]
fn a_retry_after_busy_state_reuses_the_walk_and_a_retry_after_a_prepared_attempt_reads_again() {
let tracker = Tracker::default();
let reads = tracker.inject_validation_table_for_test(
ProcessTable::from_test_members(3, 60_000, Vec::new(), Vec::new()),
Duration::ZERO,
);
let mut receipt = Receipt::default();
let prepare = |receipt: &mut Receipt| {
tracker.prepare(
"busy",
1,
std::process::id(),
crate::subtree_resources::Target::Unavailable("no_container"),
Declaration::default(),
receipt,
)
};
{
let _busy = tracker.state.lock().unwrap();
assert!(prepare(&mut receipt).is_none());
}
assert_eq!(reads.load(Ordering::SeqCst), 1);
assert!(prepare(&mut receipt).is_some());
assert_eq!(
reads.load(Ordering::SeqCst),
1,
"the attempt after busy state reused the first walk"
);
assert!(prepare(&mut receipt).is_some());
assert_eq!(
reads.load(Ordering::SeqCst),
2,
"an attempt after a prepared one, as after a commit conflict, walks again"
);
assert_eq!(receipt.finish_until, Some(3));
}
#[test]
fn arrivals_during_a_walk_share_the_next_walk_and_never_the_running_one() {
let reads = Arc::new(SharedReads::<u32>::default());
let (started, starts) = mpsc::channel();
let (release, wait) = mpsc::channel();
let wait = Arc::new(Mutex::new(wait));
let first = {
let reads = Arc::clone(&reads);
let walk = held(started.clone(), Arc::clone(&wait), 1);
std::thread::spawn(move || reads.read(Some(BTreeSet::from([1])), walk))
};
assert_eq!(starts.recv().unwrap(), Some(BTreeSet::from([1])));
let late: Vec<_> = [2, 3, 4]
.into_iter()
.map(|pid| {
let reads = Arc::clone(&reads);
let walk = held(started.clone(), Arc::clone(&wait), 2);
std::thread::spawn(move || reads.read(Some(BTreeSet::from([pid])), walk))
})
.collect();
while reads.queue.lock().unwrap().waiting.get(&1).copied() != Some(3) {
std::thread::yield_now();
}
release.send(()).unwrap();
assert_eq!(first.join().unwrap(), 1);
assert_eq!(
starts.recv().unwrap(),
Some(BTreeSet::from([2, 3, 4])),
"one walk reads the union of every waiting caller's interest"
);
release.send(()).unwrap();
for caller in late {
assert_eq!(
caller.join().unwrap(),
2,
"no caller used the walk that began before it arrived"
);
}
assert!(
starts.try_recv().is_err(),
"the waiting callers started only one more walk"
);
let queue = reads.queue.lock().unwrap();
assert!(queue.results.is_empty() && queue.waiting.is_empty());
}
#[test]
fn a_full_walk_request_widens_the_shared_walk_and_a_panic_releases_waiters() {
let reads = Arc::new(SharedReads::<Option<u32>>::default());
let (started, starts) = mpsc::channel();
let (release, wait) = mpsc::channel::<()>();
let wait = Arc::new(Mutex::new(wait));
let first = {
let reads = Arc::clone(&reads);
let started = started.clone();
let wait = Arc::clone(&wait);
std::thread::spawn(move || {
reads.read(Some(BTreeSet::from([1])), move |interest| {
started.send(interest).unwrap();
wait.lock().unwrap().recv().unwrap();
Some(1)
})
})
};
starts.recv().unwrap();
let callers: Vec<_> = [Some(BTreeSet::from([2])), None]
.into_iter()
.map(|interest| {
let reads = Arc::clone(&reads);
let started = started.clone();
std::thread::spawn(move || {
reads.read(interest, move |interest| {
started.send(interest).unwrap();
panic!("walk failed");
})
})
})
.collect();
while reads.queue.lock().unwrap().waiting.get(&1).copied() != Some(2) {
std::thread::yield_now();
}
release.send(()).unwrap();
assert_eq!(first.join().unwrap(), Some(1));
assert_eq!(starts.recv().unwrap(), None, "a full walk covers everyone");
let outcomes: Vec<_> = callers.into_iter().map(|caller| caller.join()).collect();
assert_eq!(
outcomes.iter().filter(|outcome| outcome.is_err()).count(),
1,
"only the caller whose walk panicked unwinds"
);
assert!(outcomes
.into_iter()
.flatten()
.all(|result| result.is_none()));
let queue = reads.queue.lock().unwrap();
assert!(queue.results.is_empty() && queue.waiting.is_empty() && !queue.reading);
}
}