use std::collections::BTreeMap;
use std::collections::VecDeque;
use serde::Deserialize;
use serde::Serialize;
use super::discarded_at_send::QueueId;
use crate::types::DetPid;
pub(crate) const KERNEL_SIGINFO_SIZE: usize = 48;
pub(crate) const SI_TIMER: i32 = -2;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub(crate) enum Entry {
Plain {
siginfo: KernelSiginfo,
forged_si_timer: bool,
},
Timer(TimerEntry),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub(crate) struct TimerEntry {
pub(crate) process: DetPid,
pub(crate) timer: i32,
pub(crate) gen_at_send: u64,
pub(crate) periodic_at_send: bool,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub(crate) enum FrontClass {
Own,
Proxy,
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub(crate) struct SignalList {
entries: VecDeque<Entry>,
front_class: FrontClass,
physical_si_timer: bool,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum TimerAppend {
SendFront,
ProxyFront,
Behind,
AlreadyPending,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Popped {
pub(crate) entry: Entry,
pub(crate) class: FrontClass,
pub(crate) physical_si_timer: bool,
pub(crate) next: Option<Entry>,
}
#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub(crate) struct ExecOutcome {
pub(crate) resend: Vec<(QueueId, i32, KernelSiginfo)>,
pub(crate) take_back: Vec<(QueueId, i32)>,
}
#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub(crate) struct SignalLists {
lists: BTreeMap<(QueueId, i32), SignalList>,
}
impl SignalLists {
pub(crate) fn is_listed(&self, queue: QueueId, signal: i32) -> bool {
self.lists.contains_key(&(queue, signal))
}
pub(crate) fn entries(&self, queue: QueueId, signal: i32) -> Vec<Entry> {
self.lists
.get(&(queue, signal))
.map(|list| list.entries.iter().copied().collect())
.unwrap_or_default()
}
pub(crate) fn front(&self, queue: QueueId, signal: i32) -> Option<(Entry, FrontClass, bool)> {
let list = self.lists.get(&(queue, signal))?;
Some((
*list.entries.front()?,
list.front_class,
list.physical_si_timer,
))
}
pub(crate) fn append_plain(
&mut self,
queue: QueueId,
signal: i32,
siginfo: KernelSiginfo,
discarded_physical: Option<bool>,
timer_pair: bool,
) -> bool {
if self.is_listed(queue, signal) {
return false;
}
let own_si_timer = siginfo_code(&siginfo) == SI_TIMER;
let front_class = if discarded_physical.is_some() && timer_pair {
FrontClass::Proxy
} else {
FrontClass::Own
};
self.lists.insert(
(queue, signal),
SignalList {
entries: VecDeque::from([Entry::Plain {
siginfo,
forged_si_timer: own_si_timer,
}]),
front_class,
physical_si_timer: discarded_physical.unwrap_or(own_si_timer),
},
);
true
}
pub(crate) fn append_timer(
&mut self,
queue: QueueId,
signal: i32,
entry: TimerEntry,
discarded_pending: Option<bool>,
) -> TimerAppend {
if self.refresh_timer(entry) {
return TimerAppend::AlreadyPending;
}
if let Some(list) = self.lists.get_mut(&(queue, signal)) {
list.entries.push_back(Entry::Timer(entry));
return TimerAppend::Behind;
}
let (front_class, physical_si_timer, append) = match discarded_pending {
Some(physical_si_timer) => (
FrontClass::Proxy,
physical_si_timer,
TimerAppend::ProxyFront,
),
None => (FrontClass::Own, true, TimerAppend::SendFront),
};
self.lists.insert(
(queue, signal),
SignalList {
entries: VecDeque::from([Entry::Timer(entry)]),
front_class,
physical_si_timer,
},
);
append
}
pub(crate) fn refresh_timer(&mut self, current: TimerEntry) -> bool {
for list in self.lists.values_mut() {
for entry in list.entries.iter_mut() {
if let Entry::Timer(timer) = entry
&& timer.process == current.process
&& timer.timer == current.timer
{
*timer = current;
return true;
}
}
}
false
}
#[cfg(test)]
pub(crate) fn timer_entry(
&self,
process: DetPid,
timer: i32,
) -> Option<(QueueId, i32, TimerEntry)> {
self.lists.iter().find_map(|(&(queue, signal), list)| {
list.entries.iter().find_map(|entry| match entry {
Entry::Timer(t) if t.process == process && t.timer == timer => {
Some((queue, signal, *t))
}
_ => None,
})
})
}
pub(crate) fn pop(&mut self, queue: QueueId, signal: i32) -> Option<Popped> {
let list = self.lists.get_mut(&(queue, signal))?;
let entry = list.entries.pop_front()?;
let popped = Popped {
entry,
class: list.front_class,
physical_si_timer: list.physical_si_timer,
next: list.entries.front().copied(),
};
match popped.next {
None => {
self.lists.remove(&(queue, signal));
}
Some(next) => {
list.front_class = FrontClass::Own;
list.physical_si_timer = matches!(next, Entry::Timer(_));
}
}
Some(popped)
}
pub(crate) fn take_all(&mut self, queue: QueueId, signal: i32) -> Vec<Entry> {
self.lists
.remove(&(queue, signal))
.map(|list| list.entries.into_iter().collect())
.unwrap_or_default()
}
pub(crate) fn deliverable(
&self,
queue: QueueId,
signal: i32,
current_gen: impl Fn(DetPid, i32) -> u64,
) -> bool {
self.lists.get(&(queue, signal)).is_some_and(|list| {
list.entries
.iter()
.enumerate()
.any(|(index, entry)| match entry {
Entry::Plain { .. } => index == 0,
Entry::Timer(t) => t.gen_at_send == current_gen(t.process, t.timer),
})
})
}
pub(crate) fn exec(&mut self, queues: &[QueueId]) -> ExecOutcome {
let mut outcome = ExecOutcome::default();
let keys: Vec<(QueueId, i32)> = self
.lists
.keys()
.copied()
.filter(|(queue, _)| queues.contains(queue))
.collect();
for key in keys {
let list = self.lists.get_mut(&key).unwrap();
let flushed = list.physical_si_timer;
list.entries.retain(|entry| {
matches!(
entry,
Entry::Plain {
forged_si_timer: false,
..
}
)
});
let survivor = list.entries.front().copied();
match (flushed, survivor) {
(true, Some(Entry::Plain { siginfo, .. }))
if list.front_class == FrontClass::Proxy =>
{
list.physical_si_timer = false;
outcome.resend.push((key.0, key.1, siginfo));
}
(true, Some(_)) | (true, None) => {
self.lists.remove(&key);
}
(false, Some(_)) => {}
(false, None) => {
self.lists.remove(&key);
outcome.take_back.push(key);
}
}
}
outcome
}
pub(crate) fn rekey_thread(&mut self, from: QueueId, to: QueueId) {
if from == to {
return;
}
self.retire(to);
let moved: Vec<(i32, SignalList)> = self
.lists
.keys()
.filter(|(queue, _)| *queue == from)
.copied()
.collect::<Vec<_>>()
.into_iter()
.map(|key| (key.1, self.lists.remove(&key).unwrap()))
.collect();
for (signal, list) in moved {
self.lists.insert((to, signal), list);
}
}
pub(crate) fn retire(&mut self, queue: QueueId) -> Vec<Entry> {
let keys: Vec<(QueueId, i32)> = self
.lists
.keys()
.filter(|(owner, _)| *owner == queue)
.copied()
.collect();
keys.into_iter()
.flat_map(|key| self.lists.remove(&key).unwrap().entries)
.collect()
}
pub(crate) fn listed(&self) -> Vec<(QueueId, i32)> {
self.lists.keys().copied().collect()
}
pub(crate) fn invariants_hold(&self) -> bool {
let mut timers = std::collections::BTreeSet::new();
self.lists.values().all(|list| {
!list.entries.is_empty()
&& list
.entries
.iter()
.skip(1)
.all(|entry| matches!(entry, Entry::Timer(_)))
&& list.entries.iter().all(|entry| match entry {
Entry::Timer(t) => timers.insert((t.process, t.timer)),
Entry::Plain { .. } => true,
})
})
}
}
pub(crate) fn siginfo_code(siginfo: &KernelSiginfo) -> i32 {
i32::from_ne_bytes(siginfo.0[8..12].try_into().unwrap())
}
pub(crate) fn signalfd_record(info: &KernelSiginfo) -> [u8; 128] {
let si = &info.0;
let mut record = [0u8; 128];
record[0..12].copy_from_slice(&si[0..12]);
let code = siginfo_code(info);
if code == SI_TIMER {
record[24..28].copy_from_slice(&si[16..20]);
record[32..36].copy_from_slice(&si[20..24]);
record[44..48].copy_from_slice(&si[24..28]);
record[48..56].copy_from_slice(&si[24..32]);
} else {
record[12..20].copy_from_slice(&si[16..24]);
if code < 0 {
record[44..48].copy_from_slice(&si[24..28]);
record[48..56].copy_from_slice(&si[24..32]);
}
}
record
}
pub(crate) fn ordinary_siginfo(signal: i32, code: i32, pid: i32, uid: u32) -> KernelSiginfo {
let mut info = [0u8; KERNEL_SIGINFO_SIZE];
info[0..4].copy_from_slice(&signal.to_ne_bytes());
info[8..12].copy_from_slice(&code.to_ne_bytes());
info[16..20].copy_from_slice(&pid.to_ne_bytes());
info[20..24].copy_from_slice(&uid.to_ne_bytes());
KernelSiginfo(info)
}
pub(crate) fn timer_siginfo(signal: i32, timer: i32, overrun: i32, value: u64) -> KernelSiginfo {
let mut info = [0u8; KERNEL_SIGINFO_SIZE];
info[0..4].copy_from_slice(&signal.to_ne_bytes());
info[8..12].copy_from_slice(&SI_TIMER.to_ne_bytes());
info[16..20].copy_from_slice(&timer.to_ne_bytes());
info[20..24].copy_from_slice(&overrun.to_ne_bytes());
info[24..32].copy_from_slice(&value.to_ne_bytes());
KernelSiginfo(info)
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct KernelSiginfo(pub [u8; KERNEL_SIGINFO_SIZE]);
impl KernelSiginfo {
pub(crate) fn to_user(self) -> [u8; 128] {
let mut user = [0u8; 128];
user[..KERNEL_SIGINFO_SIZE].copy_from_slice(&self.0);
user
}
pub(crate) fn from_user(user: &[u8; 128]) -> Self {
Self(user[..KERNEL_SIGINFO_SIZE].try_into().unwrap())
}
}
impl std::fmt::Debug for KernelSiginfo {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "KernelSiginfo(code {})", siginfo_code(self))
}
}
impl Serialize for KernelSiginfo {
fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
serializer.serialize_bytes(&self.0)
}
}
impl<'de> Deserialize<'de> for KernelSiginfo {
fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
let bytes = Vec::<u8>::deserialize(deserializer)?;
bytes
.try_into()
.map(KernelSiginfo)
.map_err(|_| serde::de::Error::custom("a siginfo must be 48 bytes"))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::types::DetTid;
const P: DetPid = DetPid::from_raw(10);
const USR1: i32 = libc::SIGUSR1;
fn shared() -> QueueId {
QueueId::Process(P)
}
fn timer(id: i32, generation: u64) -> TimerEntry {
TimerEntry {
process: P,
timer: id,
gen_at_send: generation,
periodic_at_send: true,
}
}
fn kill_info() -> KernelSiginfo {
let mut info = [0u8; KERNEL_SIGINFO_SIZE];
info[0..4].copy_from_slice(&USR1.to_ne_bytes());
KernelSiginfo(info)
}
fn queue_info() -> KernelSiginfo {
let mut info = kill_info();
info.0[8..12].copy_from_slice(&(-1i32).to_ne_bytes());
info.0[24..32].copy_from_slice(&0x1122334455667788u64.to_ne_bytes());
info
}
fn private() -> QueueId {
QueueId::Thread(DetTid::from_raw(10))
}
#[test]
fn an_ordinary_send_into_a_non_empty_list_adds_nothing() {
let mut lists = SignalLists::default();
assert_eq!(
lists.append_timer(shared(), USR1, timer(1, 1), None),
TimerAppend::SendFront
);
assert!(!lists.append_plain(shared(), USR1, kill_info(), None, true));
assert_eq!(
lists.entries(shared(), USR1),
vec![Entry::Timer(timer(1, 1))]
);
assert!(lists.invariants_hold());
}
#[test]
fn a_timer_goes_behind_an_ordinary_front_and_is_promoted_at_its_dequeue() {
let mut lists = SignalLists::default();
assert!(lists.append_plain(shared(), USR1, kill_info(), None, true));
assert_eq!(
lists.append_timer(shared(), USR1, timer(1, 1), None),
TimerAppend::Behind
);
let popped = lists.pop(shared(), USR1).unwrap();
assert!(matches!(popped.entry, Entry::Plain { .. }));
assert_eq!(popped.next, Some(Entry::Timer(timer(1, 1))));
let (front, class, physical_si_timer) = lists.front(shared(), USR1).unwrap();
assert_eq!(front, Entry::Timer(timer(1, 1)));
assert_eq!(class, FrontClass::Own);
assert!(physical_si_timer);
assert!(lists.pop(shared(), USR1).unwrap().next.is_none());
assert!(!lists.is_listed(shared(), USR1));
}
#[test]
fn an_expiry_with_its_entry_queued_refreshes_it_in_place() {
let mut lists = SignalLists::default();
lists.append_timer(shared(), USR1, timer(1, 1), None);
let refreshed = TimerEntry {
gen_at_send: 2,
periodic_at_send: false,
..timer(1, 1)
};
assert_eq!(
lists.append_timer(shared(), USR1, refreshed, None),
TimerAppend::AlreadyPending
);
assert_eq!(lists.entries(shared(), USR1), vec![Entry::Timer(refreshed)]);
assert!(lists.invariants_hold());
}
#[test]
fn a_timer_onto_a_discarded_copy_is_a_proxy_front() {
let mut lists = SignalLists::default();
assert_eq!(
lists.append_timer(shared(), USR1, timer(1, 1), Some(false)),
TimerAppend::ProxyFront
);
let (_, class, physical_si_timer) = lists.front(shared(), USR1).unwrap();
assert_eq!(class, FrontClass::Proxy);
assert!(!physical_si_timer);
}
#[test]
fn a_forged_si_timer_send_is_marked_forged() {
let mut lists = SignalLists::default();
let mut info = kill_info();
info.0[8..12].copy_from_slice(&SI_TIMER.to_ne_bytes());
assert!(lists.append_plain(shared(), USR1, info, None, true));
assert!(matches!(
lists.entries(shared(), USR1)[0],
Entry::Plain {
forged_si_timer: true,
..
}
));
assert!(lists.front(shared(), USR1).unwrap().2);
}
#[test]
fn deliverable_sees_a_valid_timer_behind_a_stale_head() {
let mut lists = SignalLists::default();
lists.append_timer(shared(), USR1, timer(1, 1), None);
lists.append_timer(shared(), USR1, timer(2, 1), None);
let gens = |_: DetPid, id: i32| if id == 1 { 2 } else { 1 };
assert!(lists.deliverable(shared(), USR1, gens));
let all_stale = |_: DetPid, _: i32| 9;
assert!(!lists.deliverable(shared(), USR1, all_stale));
}
#[test]
fn a_thread_queue_and_the_shared_queue_are_separate_lists() {
let mut lists = SignalLists::default();
let private = QueueId::Thread(DetTid::from_raw(11));
lists.append_timer(private, USR1, timer(1, 1), None);
lists.append_timer(shared(), USR1, timer(2, 1), None);
assert_eq!(lists.listed().len(), 2);
assert_eq!(lists.timer_entry(P, 1).map(|(q, ..)| q), Some(private));
assert!(lists.invariants_hold());
}
#[test]
fn a_signalfd_record_lays_out_each_kind_as_signalfd_copyinfo_does() {
let timer = signalfd_record(&timer_siginfo(USR1, 3, 4, 0x1122334455667788));
assert_eq!(
i32::from_ne_bytes(timer[8..12].try_into().unwrap()),
SI_TIMER
);
assert_eq!(u32::from_ne_bytes(timer[24..28].try_into().unwrap()), 3);
assert_eq!(u32::from_ne_bytes(timer[32..36].try_into().unwrap()), 4);
assert_eq!(
i32::from_ne_bytes(timer[44..48].try_into().unwrap()),
0x55667788
);
assert_eq!(
u64::from_ne_bytes(timer[48..56].try_into().unwrap()),
0x1122334455667788
);
assert!(timer[12..24].iter().all(|&byte| byte == 0));
let queued = signalfd_record(&queue_info());
assert_eq!(
u64::from_ne_bytes(queued[48..56].try_into().unwrap()),
0x1122334455667788
);
let killed = signalfd_record(&ordinary_siginfo(USR1, 0, 77, 1000));
assert_eq!(u32::from_ne_bytes(killed[12..16].try_into().unwrap()), 77);
assert_eq!(u32::from_ne_bytes(killed[16..20].try_into().unwrap()), 1000);
assert!(killed[20..].iter().all(|&byte| byte == 0));
}
#[test]
fn the_timer_siginfo_matches_the_kernel_layout() {
let info = timer_siginfo(USR1, 3, 4, 0x1122334455667788);
assert_eq!(siginfo_code(&info), SI_TIMER);
let info = info.0;
assert_eq!(i32::from_ne_bytes(info[0..4].try_into().unwrap()), USR1);
assert_eq!(i32::from_ne_bytes(info[16..20].try_into().unwrap()), 3);
assert_eq!(i32::from_ne_bytes(info[20..24].try_into().unwrap()), 4);
assert_eq!(
u64::from_ne_bytes(info[24..32].try_into().unwrap()),
0x1122334455667788
);
assert!(info[32..].iter().all(|&byte| byte == 0));
}
#[test]
fn exec_resends_a_proxy_plain_whose_si_timer_record_the_kernel_flushed() {
let mut lists = SignalLists::default();
assert!(lists.append_plain(private(), USR1, queue_info(), Some(true), true));
let outcome = lists.exec(&[private(), shared()]);
assert_eq!(outcome.resend, vec![(private(), USR1, queue_info())]);
assert!(outcome.take_back.is_empty());
let (front, class, physical_si_timer) = lists.front(private(), USR1).unwrap();
assert!(matches!(front, Entry::Plain { siginfo, .. } if siginfo == queue_info()));
assert_eq!(
class,
FrontClass::Proxy,
"the stop and take rewrite still apply"
);
assert!(
!physical_si_timer,
"the physical record is now Hermit's re-send"
);
assert!(lists.invariants_hold());
}
#[test]
fn exec_pops_a_timer_free_plain_over_a_flushed_record() {
let mut lists = SignalLists::default();
assert!(lists.append_plain(private(), USR1, queue_info(), Some(true), false));
assert_eq!(lists.front(private(), USR1).unwrap().1, FrontClass::Own);
let outcome = lists.exec(&[private(), shared()]);
assert_eq!(outcome, ExecOutcome::default());
assert!(!lists.is_listed(private(), USR1));
}
#[test]
fn exec_removes_a_forged_plain_in_either_kind_of_pair() {
for timer_pair in [false, true] {
let mut lists = SignalLists::default();
let mut forged = kill_info();
forged.0[8..12].copy_from_slice(&SI_TIMER.to_ne_bytes());
assert!(lists.append_plain(shared(), USR1, forged, None, timer_pair));
let outcome = lists.exec(&[private(), shared()]);
assert_eq!(outcome, ExecOutcome::default());
assert!(!lists.is_listed(shared(), USR1));
}
}
#[test]
fn exec_pops_a_plain_appended_before_the_first_timer() {
let mut lists = SignalLists::default();
assert!(lists.append_plain(shared(), USR1, queue_info(), Some(true), false));
let outcome = lists.exec(&[shared()]);
assert!(outcome.resend.is_empty());
assert!(!lists.is_listed(shared(), USR1));
}
#[test]
fn exec_takes_back_a_kept_record_whose_timer_entry_it_removed() {
let mut lists = SignalLists::default();
lists.append_timer(shared(), USR1, timer(1, 1), Some(false));
let outcome = lists.exec(&[shared()]);
assert_eq!(outcome.take_back, vec![(shared(), USR1)]);
assert!(!lists.is_listed(shared(), USR1));
}
#[test]
fn exec_leaves_nothing_of_an_own_timer_entry() {
let mut lists = SignalLists::default();
lists.append_timer(shared(), USR1, timer(1, 1), None);
lists.append_timer(shared(), USR1, timer(2, 1), None);
assert_eq!(lists.exec(&[shared()]), ExecOutcome::default());
assert!(lists.listed().is_empty());
}
#[test]
fn exec_keeps_a_plain_front_and_drops_the_timers_behind_it() {
let mut lists = SignalLists::default();
assert!(lists.append_plain(shared(), USR1, kill_info(), None, true));
lists.append_timer(shared(), USR1, timer(1, 1), None);
assert_eq!(lists.exec(&[shared()]), ExecOutcome::default());
assert_eq!(lists.entries(shared(), USR1).len(), 1);
assert!(lists.invariants_hold());
}
#[test]
fn exec_touches_only_the_named_queues() {
let mut lists = SignalLists::default();
let sibling = QueueId::Thread(DetTid::from_raw(12));
lists.append_timer(sibling, USR1, timer(1, 1), None);
assert_eq!(lists.exec(&[private(), shared()]), ExecOutcome::default());
assert!(lists.is_listed(sibling, USR1));
}
#[test]
fn rekey_moves_private_lists_and_drops_the_old_leaders() {
let mut lists = SignalLists::default();
let (from, to) = (QueueId::Thread(DetTid::from_raw(12)), private());
lists.append_timer(to, USR1, timer(1, 1), None);
assert!(lists.append_plain(from, USR1, queue_info(), Some(true), true));
lists.rekey_thread(from, to);
assert!(!lists.is_listed(from, USR1));
assert_eq!(lists.front(to, USR1).unwrap().1, FrontClass::Proxy);
assert!(lists.timer_entry(P, 1).is_none());
}
#[test]
fn retire_drops_the_lists_and_frees_their_timers() {
let mut lists = SignalLists::default();
lists.append_timer(private(), USR1, timer(1, 1), None);
let dropped = lists.retire(private());
assert_eq!(dropped, vec![Entry::Timer(timer(1, 1))]);
assert!(lists.timer_entry(P, 1).is_none());
assert!(!lists.refresh_timer(timer(1, 2)));
}
}