#![cfg_attr(windows, allow(dead_code))]
use std::hash::Hash;
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use std::sync::{Arc, Mutex};
use snare_interpose::RaceCell;
use crate::readiness::{WakeKey, WakeKeys};
use crate::{HashMap, HashSet};
const SHARDS: usize = 64;
type Shard = Mutex<HashMap<WakeKey, Vec<Arc<ReadyList>>>>;
struct Board {
shards: [Shard; SHARDS],
}
static SUBSCRIPTIONS: AtomicUsize = AtomicUsize::new(0);
static BROADCASTS: AtomicU64 = AtomicU64::new(0);
fn board() -> &'static Board {
static BOARD: RaceCell<Board> = RaceCell::new();
BOARD
.get_or_init(|| Board {
shards: std::array::from_fn(|_| Mutex::default()),
})
.0
}
fn shard(key: WakeKey) -> &'static Shard {
let (kind, id) = match key {
WakeKey::Socket(id) => (1u64, id),
#[cfg(unix)]
WakeKey::Descriptor(id) => (2, id),
#[cfg(windows)]
WakeKey::CompletionPort(id) => (2, id),
WakeKey::Thread(id) => (3, id),
#[cfg(unix)]
WakeKey::Real(id) => (4, id),
};
let mixed = (id ^ kind.rotate_right(8)).wrapping_mul(0x9e37_79b9_7f4a_7c15);
&board().shards[(mixed >> 58) as usize % SHARDS]
}
pub(crate) fn post<'a>(
domain: usize,
event: snare_interpose::ReadinessWake<'a>,
reached: &'a mut WakeKeys,
) -> snare_interpose::ReadinessWake<'a> {
use snare_interpose::ReadinessWake;
match event {
ReadinessWake::All => {
BROADCASTS.fetch_add(1, Ordering::AcqRel);
event
}
ReadinessWake::Keys(keys) if SUBSCRIPTIONS.load(Ordering::Acquire) > 0 => {
let mut any = false;
for &key in keys {
any |= mark(domain, key, |list| {
if !any {
any = true;
keys.iter().for_each(|&key| reached.push(key));
}
reached.push(list);
});
}
if any {
ReadinessWake::Keys(reached.as_slice())
} else {
event
}
}
_ => event,
}
}
pub(crate) fn notice(domain: usize, key: WakeKey) {
if SUBSCRIPTIONS.load(Ordering::Acquire) > 0 {
mark(domain, key, |_| {});
}
}
fn mark(domain: usize, key: WakeKey, mut reached: impl FnMut(WakeKey)) -> bool {
let shard = shard(key).lock().unwrap_or_else(|e| e.into_inner());
let Some(lists) = shard.get(&key) else {
return false;
};
let mut marked = false;
for list in lists {
let theirs = list.domain.load(Ordering::Acquire);
if domain != 0 && theirs != 0 && theirs != domain {
continue;
}
list.marks
.lock()
.unwrap_or_else(|e| e.into_inner())
.insert(key);
reached(list.key());
marked = true;
}
marked
}
pub(crate) struct ReadyList {
id: AtomicU64,
domain: AtomicUsize,
marks: Mutex<HashSet<WakeKey>>,
}
impl ReadyList {
pub(crate) fn key(&self) -> WakeKey {
let id = self.id.load(Ordering::Acquire);
#[cfg(unix)]
return WakeKey::Descriptor(id);
#[cfg(windows)]
return WakeKey::CompletionPort(id);
}
pub(crate) fn place(&self, id: u64, domain: usize) {
self.id.store(id, Ordering::Release);
self.domain.store(domain, Ordering::Release);
}
fn subscribe(self: &Arc<Self>, key: WakeKey) {
shard(key)
.lock()
.unwrap_or_else(|e| e.into_inner())
.entry(key)
.or_default()
.push(self.clone());
SUBSCRIPTIONS.fetch_add(1, Ordering::AcqRel);
}
fn unsubscribe(self: &Arc<Self>, key: WakeKey) {
let mut shard = shard(key).lock().unwrap_or_else(|e| e.into_inner());
let Some(lists) = shard.get_mut(&key) else {
return;
};
let Some(at) = lists.iter().position(|list| Arc::ptr_eq(list, self)) else {
return;
};
lists.swap_remove(at);
if lists.is_empty() {
shard.remove(&key);
}
SUBSCRIPTIONS.fetch_sub(1, Ordering::AcqRel);
}
fn take(&self, mut marked: impl FnMut(WakeKey)) {
let mut marks = self.marks.lock().unwrap_or_else(|e| e.into_inner());
if !marks.is_empty() {
marks.drain().for_each(&mut marked);
}
}
}
#[derive(Clone, Copy, Default, PartialEq)]
pub(crate) struct Keys([Option<WakeKey>; 2]);
impl Keys {
pub(crate) fn of(first: Option<WakeKey>, second: Option<WakeKey>) -> Self {
if first == second {
Keys([first, None])
} else {
Keys([first, second])
}
}
pub(crate) fn iter(self) -> impl Iterator<Item = WakeKey> {
self.0.into_iter().flatten()
}
}
#[derive(Clone, Copy, PartialEq)]
pub(crate) enum Settled {
Idle,
Due,
Timed,
}
#[derive(Clone, Copy)]
pub(crate) struct Ticket {
slot: u32,
generation: u32,
}
struct Slot<R, T> {
held: Option<(R, T)>,
keys: Keys,
generation: u32,
listed: bool,
timed: bool,
scanned: u64,
}
pub(crate) struct PollSet<R: Copy + Eq + Hash, T> {
list: Arc<ReadyList>,
slots: Vec<Slot<R, T>>,
free: Vec<u32>,
index: HashMap<R, u32>,
watched: HashMap<WakeKey, Vec<u32>>,
due: Vec<u32>,
timed: usize,
scans: u64,
broadcasts: u64,
everything: bool,
}
impl<R: Copy + Eq + Hash, T> PollSet<R, T> {
pub(crate) fn new() -> Self {
PollSet {
list: Arc::new(ReadyList {
id: AtomicU64::new(0),
domain: AtomicUsize::new(0),
marks: Mutex::default(),
}),
slots: Vec::new(),
free: Vec::new(),
index: HashMap::default(),
watched: HashMap::default(),
due: Vec::new(),
timed: 0,
scans: 0,
broadcasts: BROADCASTS.load(Ordering::Acquire),
everything: false,
}
}
pub(crate) fn list(&self) -> &Arc<ReadyList> {
&self.list
}
#[cfg_attr(not(target_os = "macos"), allow(dead_code))]
pub(crate) fn get(&self, r: &R) -> Option<&T> {
let slot = *self.index.get(r)?;
self.slots[slot as usize]
.held
.as_ref()
.map(|(_, value)| value)
}
#[cfg_attr(not(target_os = "macos"), allow(dead_code))]
pub(crate) fn get_mut(&mut self, r: &R) -> Option<&mut T> {
let slot = *self.index.get(r)?;
self.slots[slot as usize]
.held
.as_mut()
.map(|(_, value)| value)
}
pub(crate) fn contains_key(&self, r: &R) -> bool {
self.index.contains_key(r)
}
pub(crate) fn iter(&self) -> impl Iterator<Item = (&R, &T)> {
self.slots
.iter()
.filter_map(|slot| slot.held.as_ref().map(|(r, value)| (r, value)))
}
pub(crate) fn insert(&mut self, r: R, value: T, keys: Keys) -> Option<T> {
let (slot, old) = match self.index.get(&r) {
Some(&slot) => {
let held = self.slots[slot as usize].held.as_mut().unwrap();
(slot, Some(std::mem::replace(&mut held.1, value)))
}
None => {
let slot = self.free.pop().unwrap_or_else(|| {
self.slots.push(Slot {
held: None,
keys: Keys::default(),
generation: 0,
listed: false,
timed: false,
scanned: 0,
});
(self.slots.len() - 1) as u32
});
self.slots[slot as usize].held = Some((r, value));
self.index.insert(r, slot);
(slot, None)
}
};
self.set_keys(slot, keys);
self.relist_slot(slot);
old
}
pub(crate) fn remove(&mut self, r: &R) -> Option<T> {
let slot = self.index.remove(r)?;
self.set_keys(slot, Keys::default());
self.set_timed(slot, false);
let entry = &mut self.slots[slot as usize];
entry.listed = false;
entry.generation = entry.generation.wrapping_add(1);
let (_, value) = entry.held.take()?;
self.free.push(slot);
Some(value)
}
pub(crate) fn retain(&mut self, mut keep: impl FnMut(&R, &mut T) -> bool) {
let gone: Vec<R> = self
.slots
.iter_mut()
.filter_map(|slot| {
let (r, value) = slot.held.as_mut()?;
(!keep(r, value)).then_some(*r)
})
.collect();
for r in gone {
self.remove(&r);
}
}
fn relist_slot(&mut self, slot: u32) {
let entry = &mut self.slots[slot as usize];
entry.generation = entry.generation.wrapping_add(1);
Self::list_slot(&mut self.slots, &mut self.due, slot);
}
fn list_slot(slots: &mut [Slot<R, T>], due: &mut Vec<u32>, slot: u32) {
let entry = &mut slots[slot as usize];
if entry.held.is_some() && !entry.listed {
entry.listed = true;
due.push(slot);
}
}
fn set_keys(&mut self, slot: u32, keys: Keys) {
let old = std::mem::replace(&mut self.slots[slot as usize].keys, keys);
if old == keys {
return;
}
for key in old.iter() {
let Some(held) = self.watched.get_mut(&key) else {
continue;
};
held.retain(|&other| other != slot);
if held.is_empty() {
self.watched.remove(&key);
self.list.unsubscribe(key);
}
}
for key in keys.iter() {
let held = self.watched.entry(key).or_default();
if held.is_empty() {
self.list.subscribe(key);
}
if !held.contains(&slot) {
held.push(slot);
}
}
}
fn set_timed(&mut self, slot: u32, timed: bool) {
let entry = &mut self.slots[slot as usize];
if entry.timed != timed {
entry.timed = timed;
if timed {
self.timed += 1;
} else {
self.timed -= 1;
}
}
}
pub(crate) fn everything(&mut self) {
self.everything = true;
}
pub(crate) fn due(&mut self) -> Vec<Ticket> {
let (watched, slots, due) = (&self.watched, &mut self.slots, &mut self.due);
self.list.take(|key| {
for &slot in watched.get(&key).into_iter().flatten() {
Self::list_slot(slots, due, slot);
}
});
let broadcasts = BROADCASTS.load(Ordering::Acquire);
if broadcasts != self.broadcasts {
self.broadcasts = broadcasts;
self.everything = true;
}
if std::mem::take(&mut self.everything) {
for slot in 0..self.slots.len() as u32 {
Self::list_slot(&mut self.slots, &mut self.due, slot);
}
}
if self.due.is_empty() {
return Vec::new();
}
self.scans += 1;
let scan = self.scans;
let slots = &mut self.slots;
self.due.retain(|&slot| {
let entry = &mut slots[slot as usize];
let keep = entry.held.is_some() && entry.listed && entry.scanned != scan;
if keep {
entry.scanned = scan;
}
keep
});
self.due
.iter()
.map(|&slot| Ticket {
slot,
generation: self.slots[slot as usize].generation,
})
.collect()
}
#[cfg_attr(not(target_os = "linux"), allow(dead_code))]
pub(crate) fn current(&self, ticket: Ticket) -> Ticket {
Ticket {
generation: self.slots[ticket.slot as usize].generation,
..ticket
}
}
pub(crate) fn at(&self, ticket: Ticket) -> Option<(R, &T)> {
let entry = &self.slots[ticket.slot as usize];
if entry.generation != ticket.generation {
return None;
}
entry.held.as_ref().map(|(r, value)| (*r, value))
}
pub(crate) fn at_mut(&mut self, ticket: Ticket) -> Option<(R, &mut T)> {
let entry = &mut self.slots[ticket.slot as usize];
if entry.generation != ticket.generation {
return None;
}
entry.held.as_mut().map(|(r, value)| (*r, value))
}
pub(crate) fn settle(&mut self, ticket: Ticket, settled: Settled, keys: Option<Keys>) {
if self.at(ticket).is_none() {
return;
}
if let Some(keys) = keys {
self.set_keys(ticket.slot, keys);
}
self.set_timed(ticket.slot, settled == Settled::Timed);
if settled == Settled::Idle {
self.slots[ticket.slot as usize].listed = false;
} else {
Self::list_slot(&mut self.slots, &mut self.due, ticket.slot);
}
}
#[cfg_attr(not(target_os = "macos"), allow(dead_code))]
pub(crate) fn unlist(&mut self, r: &R) {
if let Some(&slot) = self.index.get(r) {
self.set_timed(slot, false);
self.slots[slot as usize].listed = false;
}
}
pub(crate) fn timed(&self) -> bool {
self.timed > 0
}
}
impl<R: Copy + Eq + Hash, T> Default for PollSet<R, T> {
fn default() -> Self {
Self::new()
}
}
impl<R: Copy + Eq + Hash, T> Drop for PollSet<R, T> {
fn drop(&mut self) {
for key in self.watched.keys() {
self.list.unsubscribe(*key);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn due<R: Copy + Eq + Hash, T>(set: &mut PollSet<R, T>) -> Vec<R> {
let tickets = set.due();
tickets
.into_iter()
.filter_map(|ticket| set.at(ticket).map(|(r, _)| r))
.collect()
}
#[test]
fn notices_list_only_the_registrations_they_name() {
let (a, b) = (WakeKey::Socket(u64::MAX - 1), WakeKey::Socket(u64::MAX - 2));
let mut set: PollSet<u32, ()> = PollSet::new();
set.list().place(u64::MAX - 3, 7);
set.insert(1, (), Keys::of(Some(a), None));
set.insert(2, (), Keys::of(Some(b), None));
let tickets = set.due();
assert_eq!(tickets.len(), 2);
for ticket in tickets {
set.settle(ticket, Settled::Idle, None);
}
assert!(due(&mut set).is_empty());
notice(8, a);
assert!(due(&mut set).is_empty(), "another sim's notice");
let named = [a];
let mut reached = WakeKeys::default();
let event = post(
7,
snare_interpose::ReadinessWake::Keys(&named),
&mut reached,
);
let snare_interpose::ReadinessWake::Keys(keys) = event else {
panic!("a keyed bump stays keyed");
};
assert_eq!(keys, &[a, set.list().key()]);
assert_eq!(due(&mut set), vec![1]);
assert_eq!(due(&mut set), vec![1], "listed until settled");
}
#[test]
fn settling_keeps_fired_and_timed_registrations_and_skips_stale_tickets() {
let key = WakeKey::Socket(u64::MAX - 4);
let mut set: PollSet<u32, u8> = PollSet::new();
set.insert(1, 0, Keys::of(Some(key), None));
set.insert(2, 0, Keys::default());
let tickets = set.due();
set.settle(tickets[0], Settled::Timed, None);
set.settle(tickets[1], Settled::Due, None);
assert!(set.timed());
assert_eq!(due(&mut set), vec![1, 2]);
let tickets = set.due();
set.insert(1, 9, Keys::of(Some(key), None));
for ticket in tickets {
set.settle(ticket, Settled::Idle, None);
}
assert_eq!(due(&mut set), vec![1], "replaced during the scan");
assert_eq!(set.get(&1), Some(&9));
set.remove(&1);
notice(0, key);
assert!(due(&mut set).is_empty());
}
}