use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::fmt;
use std::str::FromStr;
use reverie_syscalls::Sysno;
use serde::Deserialize;
use serde::Serialize;
use crate::pid::DetTid;
use crate::schedule::SyscallPhase;
pub const HAPPENS_BEFORE_VERSION: u32 = 2;
pub const HAPPENS_BEFORE_VERSION_1: u32 = 1;
pub const DEFAULT_MAX_HOLD_NS: u64 = 10_000_000_000;
#[derive(PartialEq, Eq, Debug, Clone, Serialize, Deserialize)]
pub struct HappensBeforeSpec {
pub version: u32,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub max_hold_ns: Option<u64>,
#[serde(default)]
pub threads: BTreeMap<String, ThreadSpec>,
#[serde(default)]
pub events: BTreeMap<String, EventSpec>,
#[serde(default)]
pub edges: Vec<EdgeSpec>,
}
#[derive(PartialEq, Eq, Debug, Clone, Default, Serialize, Deserialize)]
pub struct ThreadSpec {
#[serde(default, skip_serializing_if = "Option::is_none")]
pub label: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub dettid: Option<i32>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub spawn_ordinal: Option<u32>,
}
#[derive(PartialEq, Eq, Debug, Clone, Default, Serialize, Deserialize)]
pub struct EventSpec {
pub thread: String,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub syscalls: Option<u64>,
#[serde(default, alias = "rcb", skip_serializing_if = "Option::is_none")]
pub rcbs: Option<u64>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub func: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub file: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub line: Option<u32>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub syscall: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub phase: Option<PhaseSpec>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub fd: Option<i32>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub futex_op: Option<i64>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub from: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub rip: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub mark: Option<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub nth: Option<u64>,
}
#[derive(PartialEq, Eq, Debug, Clone, Copy, Serialize, Deserialize)]
#[serde(rename_all = "lowercase")]
pub enum PhaseSpec {
#[serde(alias = "pre")]
Prehook,
Polling,
#[serde(alias = "post")]
Posthook,
}
impl From<PhaseSpec> for SyscallPhase {
fn from(p: PhaseSpec) -> Self {
match p {
PhaseSpec::Prehook => SyscallPhase::Prehook,
PhaseSpec::Polling => SyscallPhase::Polling,
PhaseSpec::Posthook => SyscallPhase::Posthook,
}
}
}
#[derive(PartialEq, Eq, Debug, Clone, Serialize, Deserialize)]
pub struct EdgeSpec {
pub before: String,
pub after: String,
#[serde(default)]
pub strength: Strength,
}
#[derive(PartialEq, Eq, Debug, Clone, Copy, Default, Serialize, Deserialize)]
#[serde(rename_all = "lowercase")]
pub enum Strength {
#[default]
Hard,
Soft,
}
#[derive(PartialEq, Eq, Debug, Clone, PartialOrd, Ord)]
pub struct ThreadRef {
pub label: String,
pub dettid: Option<DetTid>,
pub spawn_ordinal: Option<u32>,
}
#[derive(PartialEq, Eq, Debug, Clone, Default)]
pub struct CodeLocation {
pub function: Option<String>,
pub file: Option<String>,
pub line: Option<u32>,
}
impl CodeLocation {
pub fn is_empty(&self) -> bool {
self.function.is_none() && self.file.is_none() && self.line.is_none()
}
}
impl fmt::Display for CodeLocation {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match (&self.function, &self.file, self.line) {
(Some(func), _, Some(line)) => write!(f, "{}:{}", func, line),
(Some(func), _, None) => write!(f, "{}", func),
(None, Some(file), Some(line)) => write!(f, "{}:{}", file, line),
(None, Some(file), None) => write!(f, "{}", file),
(None, None, Some(line)) => write!(f, "line {}", line),
(None, None, None) => write!(f, "<unlocated>"),
}
}
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub enum Position {
SyscallCount(u64),
Rcb(u64),
Syscall {
sysno: Sysno,
phase: Option<SyscallPhase>,
nth: u64,
fd: Option<i32>,
futex_op: Option<i32>,
},
Rip {
addr: Option<u64>,
nth: u64,
},
Marker {
name: String,
nth: u64,
},
}
impl fmt::Display for Position {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Position::SyscallCount(n) => write!(f, "after {} syscalls", n),
Position::Rcb(m) => write!(f, "at RCB {}", m),
Position::Syscall {
sysno,
phase,
nth,
fd,
futex_op,
} => {
write!(f, "{}", sysno.name())?;
if let Some(fd) = fd {
write!(f, "(fd={})", fd)?;
}
if let Some(op) = futex_op {
write!(f, "(op={})", op)?;
}
if let Some(p) = phase {
write!(f, "@{:?}", p)?;
}
write!(f, "#{}", nth)
}
Position::Rip { addr, nth } => match addr {
Some(a) => write!(f, "@{:#x}#{}", a, nth),
None => write!(f, "@<unresolved>#{}", nth),
},
Position::Marker { name, nth } => write!(f, "mark:{}#{}", name, nth),
}
}
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub struct Anchor {
pub name: String,
pub thread: ThreadRef,
pub position: Position,
pub location: CodeLocation,
pub from: Option<String>,
}
impl fmt::Display for Anchor {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}[{}: {}", self.name, self.thread.label, self.position)?;
if let Some(base) = &self.from {
write!(f, " after {}", base)?;
}
if !self.location.is_empty() {
write!(f, " ({})", self.location)?;
}
write!(f, "]")
}
}
impl Anchor {
pub fn is_syscall_occurrence(&self) -> bool {
matches!(
self.position,
Position::Syscall {
phase: None | Some(SyscallPhase::Prehook) | Some(SyscallPhase::Posthook),
..
}
)
}
pub fn fires_at_posthook(&self) -> bool {
matches!(
self.position,
Position::Syscall {
phase: Some(SyscallPhase::Posthook),
..
}
)
}
pub fn occurrence_key(&self) -> Option<OccurrenceKey> {
match &self.position {
Position::Syscall {
sysno,
fd,
futex_op,
..
} if self.is_syscall_occurrence() => Some((*sysno as usize, *fd, *futex_op)),
_ => None,
}
}
pub fn syscall_occurrence_matches(&self, sysno: Sysno, args: [usize; 2]) -> bool {
match &self.position {
Position::Syscall {
sysno: want,
fd,
futex_op,
..
} if self.is_syscall_occurrence() && *want == sysno => {
fd.is_none_or(|fd| args[0] as u32 as i32 == fd)
&& futex_op.is_none_or(|op| args[1] as u32 as i32 == op)
}
_ => false,
}
}
}
pub fn syscall_never_returns_on_success(sysno: Sysno) -> bool {
matches!(
sysno,
Sysno::execve | Sysno::execveat | Sysno::exit | Sysno::exit_group | Sysno::rt_sigreturn
)
}
pub fn syscall_never_reaches_tracer(sysno: Sysno) -> bool {
sysno == Sysno::rt_sigreturn
}
pub type OccurrenceKey = (usize, Option<i32>, Option<i32>);
pub type OccurrenceCounters = BTreeMap<OccurrenceKey, u64>;
#[derive(PartialEq, Eq, Debug, Clone, Default, Serialize, Deserialize)]
pub struct HbThreadCounters {
pub counts: OccurrenceCounters,
pub origins: BTreeMap<String, u64>,
}
pub fn syscall_takes_fd_first(sysno: Sysno) -> bool {
match sysno {
Sysno::read
| Sysno::write
| Sysno::readv
| Sysno::writev
| Sysno::pread64
| Sysno::pwrite64
| Sysno::preadv
| Sysno::pwritev
| Sysno::preadv2
| Sysno::pwritev2
| Sysno::close
| Sysno::fsync
| Sysno::fdatasync
| Sysno::ioctl
| Sysno::fcntl
| Sysno::lseek
| Sysno::fstat
| Sysno::ftruncate
| Sysno::fallocate
| Sysno::flock
| Sysno::getdents64
| Sysno::sendto
| Sysno::recvfrom
| Sysno::sendmsg
| Sysno::recvmsg
| Sysno::sendmmsg
| Sysno::recvmmsg
| Sysno::accept
| Sysno::accept4
| Sysno::connect
| Sysno::bind
| Sysno::listen
| Sysno::shutdown
| Sysno::epoll_pwait
| Sysno::epoll_ctl
| Sysno::dup
| Sysno::dup3 => true,
#[cfg(target_arch = "x86_64")]
Sysno::epoll_wait | Sysno::dup2 => true,
_ => false,
}
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub struct HappensBeforeEdge {
pub before: String,
pub after: String,
pub strength: Strength,
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub struct HappensBeforeProgram {
pub version: u32,
pub anchors: BTreeMap<String, Anchor>,
pub edges: Vec<HappensBeforeEdge>,
pub max_hold_ns: Option<u64>,
}
impl HappensBeforeProgram {
pub fn unresolved_locations(&self) -> impl Iterator<Item = &Anchor> {
self.anchors.values().filter(|a| {
matches!(a.position, Position::Rip { addr: None, .. }) && !a.location.is_empty()
})
}
pub fn may_have_syscall_count_anchor_at(&self, dettid: DetTid, count: u64) -> bool {
self.anchors.values().any(|a| {
matches!(a.position, Position::SyscallCount(n) if n == count)
&& a.thread.dettid.is_none_or(|d| d == dettid)
})
}
pub fn has_syscall_occurrence_anchors(&self) -> bool {
self.anchors.values().any(Anchor::is_syscall_occurrence)
}
pub fn count_syscall_occurrences(
&self,
counters: &mut HbThreadCounters,
dettid: DetTid,
sysno: Sysno,
args: [usize; 2],
entry_count: u64,
) -> Vec<String> {
let on_thread = |a: &&Anchor| a.thread.dettid.is_none_or(|d| d == dettid);
let keys: BTreeSet<OccurrenceKey> = self
.anchors
.values()
.filter(|a| a.syscall_occurrence_matches(sysno, args))
.filter_map(Anchor::occurrence_key)
.collect();
for key in &keys {
*counters.counts.entry(*key).or_insert(0) += 1;
}
for relative in self.anchors.values().filter(on_thread) {
let Some(base) = relative.from.as_ref().and_then(|b| self.anchors.get(b)) else {
continue;
};
if counters.origins.contains_key(&relative.name) {
continue;
}
let reached = match &base.position {
Position::SyscallCount(n) => *n == entry_count,
Position::Syscall { nth, .. } => {
base.syscall_occurrence_matches(sysno, args)
&& base
.occurrence_key()
.is_some_and(|key| counters.counts.get(&key) == Some(nth))
}
_ => false,
};
if reached {
let origin = relative
.occurrence_key()
.and_then(|key| counters.counts.get(&key).copied())
.unwrap_or(0);
counters.origins.insert(relative.name.clone(), origin);
}
}
if keys.is_empty() {
return Vec::new();
}
self.anchors
.values()
.filter(on_thread)
.filter(|a| a.syscall_occurrence_matches(sysno, args))
.filter(|a| match (&a.position, a.occurrence_key()) {
(Position::Syscall { nth, .. }, Some(key)) => {
let count = counters.counts.get(&key).copied().unwrap_or(0);
match &a.from {
None => count == *nth,
Some(_) => counters
.origins
.get(&a.name)
.is_some_and(|origin| count - origin == *nth),
}
}
_ => false,
})
.map(|a| a.name.clone())
.collect()
}
pub fn is_version_2(&self) -> bool {
self.version == HAPPENS_BEFORE_VERSION
}
pub fn relative_anchors(&self) -> impl Iterator<Item = (&Anchor, &Anchor)> {
self.anchors.values().filter_map(|a| {
a.from
.as_ref()
.and_then(|b| self.anchors.get(b))
.map(|base| (a, base))
})
}
pub fn unenforced_positions(&self) -> impl Iterator<Item = &Anchor> {
self.anchors.values().filter(|a| {
!matches!(a.position, Position::SyscallCount(_)) && !a.is_syscall_occurrence()
})
}
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub enum HappensBeforeError {
UnsupportedVersion(u32),
AmbiguousPosition {
event: String,
found: Vec<String>,
},
UnknownSyscall {
event: String,
name: String,
},
NthZero {
event: String,
},
FdWithoutSyscall {
event: String,
},
FdNotFirstArgument {
event: String,
syscall: String,
},
BadRip {
event: String,
text: String,
},
UnknownEvent {
which: String,
name: String,
},
UnknownThread {
event: String,
thread: String,
},
Cycle(Vec<String>),
NewFieldInVersion1 {
event: Option<String>,
field: String,
},
UnknownField {
place: String,
field: String,
},
FutexOpWithoutFutex {
event: String,
},
FutexOpOutOfRange {
event: String,
value: i64,
},
FromUnknownEvent {
event: String,
base: String,
},
FromOnNonOccurrence {
event: String,
},
FromOtherThread {
event: String,
base: String,
},
FromUnenforcedPosition {
event: String,
base: String,
},
FromRelativeBase {
event: String,
base: String,
},
FromCycle(Vec<String>),
PosthookOnNoReturnSyscall {
event: String,
syscall: String,
},
DslSyntax {
line: usize,
message: String,
},
}
impl fmt::Display for HappensBeforeError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
HappensBeforeError::UnsupportedVersion(v) => write!(
f,
"unsupported happens-before schema version {} (this build understands {} and {})",
v, HAPPENS_BEFORE_VERSION_1, HAPPENS_BEFORE_VERSION
),
HappensBeforeError::AmbiguousPosition { event, found } => {
if found.is_empty() {
write!(
f,
"event '{}' must specify a position: a count (syscalls/rcbs), a syscall, a \
rip, a mark, or a code location (func/file/line)",
event
)
} else {
write!(
f,
"event '{}' names conflicting positions {:?}; use at most one explicit \
position selector (a code location may accompany it)",
event, found
)
}
}
HappensBeforeError::UnknownSyscall { event, name } => {
write!(f, "event '{}' names unknown syscall '{}'", event, name)
}
HappensBeforeError::NthZero { event } => write!(
f,
"event '{}' sets 'nth' to 0; occurrences are counted from 1",
event
),
HappensBeforeError::FdWithoutSyscall { event } => write!(
f,
"event '{}' sets 'fd' without 'syscall'; 'fd' restricts a named syscall",
event
),
HappensBeforeError::FdNotFirstArgument { event, syscall } => write!(
f,
"event '{}' sets 'fd' on syscall '{}', whose first argument is not a file \
descriptor",
event, syscall
),
HappensBeforeError::BadRip { event, text } => {
write!(f, "event '{}' has unparseable rip '{}'", event, text)
}
HappensBeforeError::UnknownEvent { which, name } => {
write!(f, "edge '{}' references unknown event '{}'", which, name)
}
HappensBeforeError::UnknownThread { event, thread } => write!(
f,
"event '{}' references unknown thread '{}'",
event, thread
),
HappensBeforeError::Cycle(names) => {
write!(
f,
"happens-before edges contain a cycle: {}",
names.join(" -> ")
)
}
HappensBeforeError::DslSyntax { line, message } => {
write!(f, "DSL parse error on line {}: {}", line, message)
}
HappensBeforeError::NewFieldInVersion1 { event, field } => match event {
Some(event) => write!(
f,
"event '{}' sets '{}', which needs \"version\": 2",
event, field
),
None => write!(f, "the spec sets '{}', which needs \"version\": 2", field),
},
HappensBeforeError::UnknownField { place, field } => write!(
f,
"{} has unknown field '{}' (version 2 refuses unknown fields)",
place, field
),
HappensBeforeError::FutexOpWithoutFutex { event } => write!(
f,
"event '{}' sets 'futex_op', which applies only to \"syscall\": \"futex\"",
event
),
HappensBeforeError::FutexOpOutOfRange { event, value } => write!(
f,
"event '{}' sets 'futex_op' to {}, which does not fit the kernel's int",
event, value
),
HappensBeforeError::FromUnknownEvent { event, base } => {
write!(f, "event '{}' counts from unknown event '{}'", event, base)
}
HappensBeforeError::FromOnNonOccurrence { event } => write!(
f,
"event '{}' sets 'from', which applies only to a syscall anchor at the prehook",
event
),
HappensBeforeError::FromOtherThread { event, base } => write!(
f,
"event '{}' counts from '{}', which cannot be shown to be on the same thread; a \
base must name the same dettid, or the same spawn ordinal",
event, base
),
HappensBeforeError::FromUnenforcedPosition { event, base } => write!(
f,
"event '{}' counts from '{}', which is neither a count anchor nor a syscall anchor \
at the prehook, so it is never reached",
event, base
),
HappensBeforeError::FromRelativeBase { event, base } => write!(
f,
"event '{}' counts from '{}', which itself uses 'from'; relative chains are not \
supported",
event, base
),
HappensBeforeError::PosthookOnNoReturnSyscall { event, syscall } => write!(
f,
"event '{}' fires at the posthook of {}, which does not return to its caller when \
it succeeds, so the anchor could only fire on a failed call",
event, syscall
),
HappensBeforeError::FromCycle(names) => write!(
f,
"relative bases and hard edges together contain a cycle: {}",
names.join(" -> ")
),
}
}
}
impl std::error::Error for HappensBeforeError {}
impl HappensBeforeSpec {
pub fn from_json(s: &str) -> anyhow::Result<HappensBeforeSpec> {
let value: serde_json::Value = serde_json::from_str(s)?;
if value.get("version").and_then(serde_json::Value::as_u64)
== Some(u64::from(HAPPENS_BEFORE_VERSION))
{
check_known_fields(&value)?;
}
Ok(serde_json::from_str(s)?)
}
pub fn to_json(&self) -> anyhow::Result<String> {
Ok(serde_json::to_string_pretty(self)?)
}
pub fn normalize(&self) -> Result<HappensBeforeProgram, HappensBeforeError> {
if self.version != HAPPENS_BEFORE_VERSION && self.version != HAPPENS_BEFORE_VERSION_1 {
return Err(HappensBeforeError::UnsupportedVersion(self.version));
}
if self.version == HAPPENS_BEFORE_VERSION_1 {
self.refuse_version_2_fields()?;
}
let mut anchors = BTreeMap::new();
for (name, ev) in &self.events {
anchors.insert(name.clone(), self.normalize_event(name, ev)?);
}
check_relative_bases(&anchors)?;
let mut edges = Vec::with_capacity(self.edges.len());
for e in &self.edges {
if !anchors.contains_key(&e.before) {
return Err(HappensBeforeError::UnknownEvent {
which: "before".to_string(),
name: e.before.clone(),
});
}
if !anchors.contains_key(&e.after) {
return Err(HappensBeforeError::UnknownEvent {
which: "after".to_string(),
name: e.after.clone(),
});
}
edges.push(HappensBeforeEdge {
before: e.before.clone(),
after: e.after.clone(),
strength: e.strength,
});
}
detect_cycle(&anchors, &edges)?;
let mut with_activation = edges.clone();
with_activation.extend(
anchors
.values()
.filter_map(|a| a.from.as_ref().map(|base| (base, a)))
.map(|(base, a)| HappensBeforeEdge {
before: base.clone(),
after: a.name.clone(),
strength: Strength::Hard,
}),
);
with_activation.retain(|e| e.strength == Strength::Hard);
if let Err(HappensBeforeError::Cycle(names)) = detect_cycle(&anchors, &with_activation) {
return Err(HappensBeforeError::FromCycle(names));
}
let max_hold_ns = (self.version == HAPPENS_BEFORE_VERSION)
.then(|| self.max_hold_ns.unwrap_or(DEFAULT_MAX_HOLD_NS));
Ok(HappensBeforeProgram {
version: self.version,
anchors,
edges,
max_hold_ns,
})
}
fn refuse_version_2_fields(&self) -> Result<(), HappensBeforeError> {
if self.max_hold_ns.is_some() {
return Err(HappensBeforeError::NewFieldInVersion1 {
event: None,
field: "max_hold_ns".to_owned(),
});
}
for (name, ev) in &self.events {
for (field, set) in [
("from", ev.from.is_some()),
("futex_op", ev.futex_op.is_some()),
] {
if set {
return Err(HappensBeforeError::NewFieldInVersion1 {
event: Some(name.clone()),
field: field.to_owned(),
});
}
}
}
Ok(())
}
fn normalize_event(&self, name: &str, ev: &EventSpec) -> Result<Anchor, HappensBeforeError> {
let thread = self.resolve_thread(name, &ev.thread)?;
let location = CodeLocation {
function: ev.func.clone(),
file: ev.file.clone(),
line: ev.line,
};
let mut found: Vec<&str> = Vec::new();
if ev.syscalls.is_some() {
found.push("syscalls");
}
if ev.rcbs.is_some() {
found.push("rcbs");
}
if ev.syscall.is_some() {
found.push("syscall");
}
if ev.rip.is_some() {
found.push("rip");
}
if ev.mark.is_some() {
found.push("mark");
}
let has_code_location = !location.is_empty();
if found.len() > 1 {
return Err(HappensBeforeError::AmbiguousPosition {
event: name.to_string(),
found: found.iter().map(|s| s.to_string()).collect(),
});
}
if found.is_empty() && !has_code_location {
return Err(HappensBeforeError::AmbiguousPosition {
event: name.to_string(),
found: Vec::new(),
});
}
if ev.fd.is_some() && ev.syscall.is_none() {
return Err(HappensBeforeError::FdWithoutSyscall {
event: name.to_string(),
});
}
if ev.futex_op.is_some() && ev.syscall.is_none() {
return Err(HappensBeforeError::FutexOpWithoutFutex {
event: name.to_string(),
});
}
if ev.nth == Some(0) && ev.syscalls.is_none() && ev.rcbs.is_none() {
return Err(HappensBeforeError::NthZero {
event: name.to_string(),
});
}
let nth = ev.nth.unwrap_or(1);
let position = if let Some(n) = ev.syscalls {
Position::SyscallCount(n)
} else if let Some(m) = ev.rcbs {
Position::Rcb(m)
} else if let Some(sc) = &ev.syscall {
let sysno = Sysno::from_str(sc).map_err(|_| HappensBeforeError::UnknownSyscall {
event: name.to_string(),
name: sc.clone(),
})?;
if ev.fd.is_some() && !syscall_takes_fd_first(sysno) {
return Err(HappensBeforeError::FdNotFirstArgument {
event: name.to_string(),
syscall: sc.clone(),
});
}
let futex_op = match ev.futex_op {
None => None,
Some(_) if sysno != Sysno::futex => {
return Err(HappensBeforeError::FutexOpWithoutFutex {
event: name.to_string(),
});
}
Some(value) => Some(i32::try_from(value).map_err(|_| {
HappensBeforeError::FutexOpOutOfRange {
event: name.to_string(),
value,
}
})?),
};
if ev.phase == Some(PhaseSpec::Posthook) && syscall_never_returns_on_success(sysno) {
return Err(HappensBeforeError::PosthookOnNoReturnSyscall {
event: name.to_string(),
syscall: sc.clone(),
});
}
Position::Syscall {
sysno,
phase: ev.phase.map(Into::into),
nth,
fd: ev.fd,
futex_op,
}
} else if let Some(rip) = &ev.rip {
let addr = parse_rip(rip).ok_or_else(|| HappensBeforeError::BadRip {
event: name.to_string(),
text: rip.clone(),
})?;
Position::Rip {
addr: Some(addr),
nth,
}
} else if let Some(mark) = &ev.mark {
Position::Marker {
name: mark.clone(),
nth,
}
} else {
debug_assert!(has_code_location);
Position::Rip { addr: None, nth }
};
Ok(Anchor {
name: name.to_string(),
thread,
position,
location,
from: ev.from.clone(),
})
}
fn resolve_thread(&self, event: &str, thread: &str) -> Result<ThreadRef, HappensBeforeError> {
if let Some(spec) = self.threads.get(thread) {
Ok(ThreadRef {
label: spec.label.clone().unwrap_or_else(|| thread.to_string()),
dettid: spec.dettid.map(DetTid::from_raw),
spawn_ordinal: spec.spawn_ordinal,
})
} else if let Ok(raw) = thread.parse::<i32>() {
Ok(ThreadRef {
label: thread.to_string(),
dettid: Some(DetTid::from_raw(raw)),
spawn_ordinal: None,
})
} else {
Err(HappensBeforeError::UnknownThread {
event: event.to_string(),
thread: thread.to_string(),
})
}
}
}
fn check_relative_bases(anchors: &BTreeMap<String, Anchor>) -> Result<(), HappensBeforeError> {
for anchor in anchors.values() {
let Some(base_name) = &anchor.from else {
continue;
};
let event = anchor.name.clone();
let base = base_name.clone();
let Some(base_anchor) = anchors.get(base_name) else {
return Err(HappensBeforeError::FromUnknownEvent { event, base });
};
if !anchor.is_syscall_occurrence() {
return Err(HappensBeforeError::FromOnNonOccurrence { event });
}
if !same_thread(&base_anchor.thread, &anchor.thread) {
return Err(HappensBeforeError::FromOtherThread { event, base });
}
if base_anchor.from.is_some() {
return Err(HappensBeforeError::FromRelativeBase { event, base });
}
if !matches!(base_anchor.position, Position::SyscallCount(_))
&& !base_anchor.is_syscall_occurrence()
{
return Err(HappensBeforeError::FromUnenforcedPosition { event, base });
}
}
Ok(())
}
fn same_thread(a: &ThreadRef, b: &ThreadRef) -> bool {
match (a.dettid, b.dettid) {
(Some(x), Some(y)) => x == y,
(None, None) => a.spawn_ordinal.is_some() && a.spawn_ordinal == b.spawn_ordinal,
_ => false,
}
}
fn check_known_fields(value: &serde_json::Value) -> Result<(), HappensBeforeError> {
const SPEC: &[&str] = &["version", "max_hold_ns", "threads", "events", "edges"];
const THREAD: &[&str] = &["label", "dettid", "spawn_ordinal"];
const EVENT: &[&str] = &[
"thread", "syscalls", "rcbs", "rcb", "func", "file", "line", "syscall", "phase", "fd",
"futex_op", "from", "rip", "mark", "nth",
];
const EDGE: &[&str] = &["before", "after", "strength"];
fn check(
object: Option<&serde_json::Map<String, serde_json::Value>>,
known: &[&str],
place: impl Fn() -> String,
) -> Result<(), HappensBeforeError> {
for field in object.into_iter().flat_map(|o| o.keys()) {
if !known.contains(&field.as_str()) {
return Err(HappensBeforeError::UnknownField {
place: place(),
field: field.clone(),
});
}
}
Ok(())
}
check(value.as_object(), SPEC, || "the spec".to_owned())?;
for (name, thread) in value
.get("threads")
.and_then(serde_json::Value::as_object)
.into_iter()
.flatten()
{
check(thread.as_object(), THREAD, || format!("thread '{name}'"))?;
}
for (name, event) in value
.get("events")
.and_then(serde_json::Value::as_object)
.into_iter()
.flatten()
{
check(event.as_object(), EVENT, || format!("event '{name}'"))?;
}
for (index, edge) in value
.get("edges")
.and_then(serde_json::Value::as_array)
.into_iter()
.flatten()
.enumerate()
{
check(edge.as_object(), EDGE, || format!("edge {index}"))?;
}
Ok(())
}
fn parse_rip(s: &str) -> Option<u64> {
let s = s.trim();
if let Some(hex) = s.strip_prefix("0x").or_else(|| s.strip_prefix("0X")) {
u64::from_str_radix(hex, 16).ok()
} else {
s.parse::<u64>().ok()
}
}
fn detect_cycle(
anchors: &BTreeMap<String, Anchor>,
edges: &[HappensBeforeEdge],
) -> Result<(), HappensBeforeError> {
let mut adj: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
for name in anchors.keys() {
adj.entry(name.as_str()).or_default();
}
for e in edges {
adj.entry(e.before.as_str())
.or_default()
.push(e.after.as_str());
}
#[derive(Clone, Copy, PartialEq)]
enum Mark {
Visiting,
Done,
}
let mut state: BTreeMap<&str, Mark> = BTreeMap::new();
for root in adj.keys().copied() {
if state.contains_key(root) {
continue;
}
let mut stack: Vec<(&str, usize)> = vec![(root, 0)];
let mut path: Vec<&str> = vec![root];
state.insert(root, Mark::Visiting);
while let Some(&mut (node, ref mut idx)) = stack.last_mut() {
let neighbors = &adj[node];
if *idx < neighbors.len() {
let next = neighbors[*idx];
*idx += 1;
match state.get(next) {
Some(Mark::Visiting) => {
let start = path.iter().position(|&n| n == next).unwrap_or(0);
let mut cycle: Vec<String> =
path[start..].iter().map(|s| s.to_string()).collect();
cycle.push(next.to_string());
return Err(HappensBeforeError::Cycle(cycle));
}
Some(Mark::Done) => {}
None => {
state.insert(next, Mark::Visiting);
path.push(next);
stack.push((next, 0));
}
}
} else {
state.insert(node, Mark::Done);
stack.pop();
path.pop();
}
}
}
Ok(())
}
impl HappensBeforeSpec {
pub fn from_dsl(input: &str) -> Result<HappensBeforeSpec, HappensBeforeError> {
let mut spec = HappensBeforeSpec {
version: HAPPENS_BEFORE_VERSION_1,
max_hold_ns: None,
threads: BTreeMap::new(),
events: BTreeMap::new(),
edges: Vec::new(),
};
let mut seen_names: BTreeSet<String> = BTreeSet::new();
for (i, raw_line) in input.lines().enumerate() {
let lineno = i + 1;
let line = strip_comment(raw_line).trim();
if line.is_empty() {
continue;
}
let (body, strength) = if let Some(b) = line.strip_suffix("!soft") {
(b.trim(), Strength::Soft)
} else if let Some(b) = line.strip_suffix("!hard") {
(b.trim(), Strength::Hard)
} else {
(line, Strength::Hard)
};
let (lhs, rhs) = body
.split_once('<')
.ok_or_else(|| HappensBeforeError::DslSyntax {
line: lineno,
message: "expected '<' separating two events".to_string(),
})?;
let before = parse_dsl_side(lhs.trim(), lineno, &mut spec, &mut seen_names)?;
let after = parse_dsl_side(rhs.trim(), lineno, &mut spec, &mut seen_names)?;
spec.edges.push(EdgeSpec {
before,
after,
strength,
});
}
Ok(spec)
}
}
fn strip_comment(line: &str) -> &str {
match line.find("//") {
Some(idx) => &line[..idx],
None => line,
}
}
fn parse_dsl_side(
token: &str,
lineno: usize,
spec: &mut HappensBeforeSpec,
seen_names: &mut BTreeSet<String>,
) -> Result<String, HappensBeforeError> {
let (thread, anchor) = token
.split_once(':')
.ok_or_else(|| HappensBeforeError::DslSyntax {
line: lineno,
message: format!("expected 'thread:anchor' in '{}'", token),
})?;
let thread = thread.trim();
let anchor = anchor.trim();
if thread.is_empty() || anchor.is_empty() {
return Err(HappensBeforeError::DslSyntax {
line: lineno,
message: format!("empty thread or anchor in '{}'", token),
});
}
let (anchor_body, nth) = match anchor.split_once('#') {
Some((a, n)) => {
let parsed = n
.parse::<u64>()
.map_err(|_| HappensBeforeError::DslSyntax {
line: lineno,
message: format!("bad ordinal '#{}'", n),
})?;
(a.trim(), Some(parsed))
}
None => (anchor, None),
};
let mut ev = EventSpec {
thread: thread.to_string(),
nth,
..Default::default()
};
if let Some(rest) = anchor_body.strip_prefix('@') {
ev.rip = Some(rest.to_string());
} else if let Some(m) = anchor_body.strip_prefix("rcb=") {
ev.rcbs = Some(
m.parse::<u64>()
.map_err(|_| HappensBeforeError::DslSyntax {
line: lineno,
message: format!("bad rcb count '{}'", m),
})?,
);
ev.nth = None;
} else if let Some(n) = anchor_body.strip_prefix("sc=") {
ev.syscalls = Some(
n.parse::<u64>()
.map_err(|_| HappensBeforeError::DslSyntax {
line: lineno,
message: format!("bad syscall count '{}'", n),
})?,
);
ev.nth = None;
} else if let Some((sc, phase)) = anchor_body.split_once('@') {
ev.syscall = Some(sc.to_string());
ev.phase = Some(parse_dsl_phase(phase, lineno)?);
} else if is_syscall_name(anchor_body) {
ev.syscall = Some(anchor_body.to_string());
} else {
ev.func = Some(anchor_body.to_string());
}
let base = sanitize_name(token);
let mut ev_name = base.clone();
let mut suffix = 1;
while seen_names.contains(&ev_name) && spec.events.get(&ev_name) != Some(&ev) {
suffix += 1;
ev_name = format!("{}_{}", base, suffix);
}
seen_names.insert(ev_name.clone());
spec.events.entry(ev_name.clone()).or_insert(ev);
if thread.parse::<i32>().is_err() {
spec.threads
.entry(thread.to_string())
.or_insert(ThreadSpec {
label: Some(thread.to_string()),
dettid: None,
spawn_ordinal: None,
});
}
Ok(ev_name)
}
fn parse_dsl_phase(phase: &str, lineno: usize) -> Result<PhaseSpec, HappensBeforeError> {
match phase.trim().to_ascii_lowercase().as_str() {
"pre" | "prehook" => Ok(PhaseSpec::Prehook),
"post" | "posthook" => Ok(PhaseSpec::Posthook),
"poll" | "polling" => Ok(PhaseSpec::Polling),
other => Err(HappensBeforeError::DslSyntax {
line: lineno,
message: format!("unknown syscall phase '{}'", other),
}),
}
}
fn is_syscall_name(s: &str) -> bool {
Sysno::from_str(s).is_ok()
}
fn sanitize_name(token: &str) -> String {
let mut out = String::with_capacity(token.len());
for ch in token.chars() {
if ch.is_ascii_alphanumeric() || ch == '_' {
out.push(ch);
} else {
out.push('_');
}
}
if out.is_empty() {
out.push('e');
}
out
}
#[cfg(test)]
mod tests {
use super::*;
fn spec_json() -> &'static str {
r#"{
"version": 1,
"threads": { "writer": {"label": "writer"}, "reader": {"label": "reader"} },
"events": {
"X_342": {"thread": "writer", "func": "free_buffer", "line": 120, "nth": 342},
"Y_97": {"thread": "reader", "func": "read_buffer", "nth": 97},
"lockA": {"thread": "writer", "syscall": "futex", "phase": "posthook", "nth": 5},
"storeB": {"thread": "reader", "rip": "0x401f3c", "nth": 1},
"scA": {"thread": "writer", "syscalls": 10},
"rcbB": {"thread": "reader", "rcbs": 123456}
},
"edges": [
{"before": "X_342", "after": "Y_97", "strength": "hard"},
{"before": "lockA", "after": "storeB"},
{"before": "scA", "after": "rcbB", "strength": "soft"}
]
}"#
}
#[test]
fn may_have_syscall_count_anchor_at_is_exact_per_thread() {
let prog = HappensBeforeSpec::from_json(
r#"{"version": 1,
"threads": {"T7": {"dettid": 7}, "S2": {"spawn_ordinal": 2}},
"events": {"a": {"thread": "T7", "syscalls": 10},
"b": {"thread": "S2", "syscalls": 20},
"c": {"thread": "T7", "rcbs": 30},
"d": {"thread": "T7", "syscall": "futex", "phase": "pre", "nth": 40}},
"edges": [{"before": "a", "after": "b"}]}"#,
)
.unwrap()
.normalize()
.unwrap();
assert!(prog.may_have_syscall_count_anchor_at(DetTid::from_raw(7), 10));
assert!(!prog.may_have_syscall_count_anchor_at(DetTid::from_raw(8), 10));
assert!(!prog.may_have_syscall_count_anchor_at(DetTid::from_raw(7), 9));
assert!(!prog.may_have_syscall_count_anchor_at(DetTid::from_raw(7), 11));
assert!(prog.may_have_syscall_count_anchor_at(DetTid::from_raw(7), 20));
assert!(prog.may_have_syscall_count_anchor_at(DetTid::from_raw(8), 20));
assert!(!prog.may_have_syscall_count_anchor_at(DetTid::from_raw(8), 21));
assert!(!prog.may_have_syscall_count_anchor_at(DetTid::from_raw(7), 30));
assert!(!prog.may_have_syscall_count_anchor_at(DetTid::from_raw(7), 0));
assert!(matches!(
prog.anchors["d"].position,
Position::Syscall { nth: 40, .. }
));
assert!(!prog.may_have_syscall_count_anchor_at(DetTid::from_raw(7), 40));
}
#[test]
fn syscall_fd_anchor_normalizes_and_displays() {
let prog = HappensBeforeSpec::from_json(
r#"{"version": 1,
"events": {"m": {"thread": "7", "syscall": "writev", "fd": 9, "nth": 3}}}"#,
)
.unwrap()
.normalize()
.unwrap();
let anchor = &prog.anchors["m"];
assert_eq!(
anchor.position,
Position::Syscall {
sysno: Sysno::writev,
phase: None,
nth: 3,
fd: Some(9),
futex_op: None,
}
);
assert_eq!(anchor.position.to_string(), "writev(fd=9)#3");
assert!(anchor.is_syscall_occurrence());
assert_eq!(prog.unenforced_positions().count(), 0);
}
#[test]
fn syscall_fd_anchor_is_refused_where_it_cannot_apply() {
let err = HappensBeforeSpec::from_json(
r#"{"version": 1, "events": {"x": {"thread": "7", "syscalls": 5, "fd": 9}}}"#,
)
.unwrap()
.normalize()
.unwrap_err();
assert_eq!(
err,
HappensBeforeError::FdWithoutSyscall {
event: "x".to_string()
}
);
let err = HappensBeforeSpec::from_json(
r#"{"version": 1, "events": {"y": {"thread": "7", "syscall": "getpid", "fd": 9}}}"#,
)
.unwrap()
.normalize()
.unwrap_err();
assert_eq!(
err,
HappensBeforeError::FdNotFirstArgument {
event: "y".to_string(),
syscall: "getpid".to_string()
}
);
assert!(err.to_string().contains("'y'"), "{err}");
let err = HappensBeforeSpec::from_json(
r#"{"version": 1, "events": {"z": {"thread": "7", "syscall": "write", "fd": 1, "nth": 0}}}"#,
)
.unwrap()
.normalize()
.unwrap_err();
assert_eq!(
err,
HappensBeforeError::NthZero {
event: "z".to_string()
}
);
}
#[test]
fn count_syscall_occurrences_is_exact_per_thread() {
let prog = HappensBeforeSpec::from_json(
r#"{"version": 1,
"threads": {"S1": {"spawn_ordinal": 1}},
"events": {"fd9": {"thread": "7", "syscall": "writev", "fd": 9, "nth": 2},
"anyfd": {"thread": "7", "syscall": "writev", "nth": 3},
"spawned": {"thread": "S1", "syscall": "write", "fd": 1},
"polling": {"thread": "7", "syscall": "close", "phase": "polling"}}}"#,
)
.unwrap()
.normalize()
.unwrap();
assert!(prog.has_syscall_occurrence_anchors());
let t7 = DetTid::from_raw(7);
let t8 = DetTid::from_raw(8);
let mut c7 = HbThreadCounters::default();
let count = |c: &mut HbThreadCounters, t, sysno, arg0: usize| {
prog.count_syscall_occurrences(c, t, sysno, [arg0, 0], 1)
};
assert!(count(&mut c7, t7, Sysno::writev, 9).is_empty());
assert!(count(&mut c7, t7, Sysno::writev, 8).is_empty());
assert!(count(&mut c7, t7, Sysno::write, 9).is_empty());
assert_eq!(
count(&mut c7, t7, Sysno::writev, 0x1_0000_0009),
["anyfd", "fd9"]
);
assert!(count(&mut c7, t7, Sysno::writev, 9).is_empty());
let mut c8 = HbThreadCounters::default();
assert!(count(&mut c8, t8, Sysno::writev, 9).is_empty());
assert!(count(&mut c8, t8, Sysno::writev, 9).is_empty());
assert_eq!(count(&mut c8, t8, Sysno::write, 1), ["spawned"]);
assert!(count(&mut c8, t8, Sysno::write, 2).is_empty());
assert!(count(&mut c7, t7, Sysno::close, 3).is_empty());
assert!(!c7.counts.contains_key(&(Sysno::close as usize, None, None)));
let unenforced: Vec<&str> = prog
.unenforced_positions()
.map(|a| a.name.as_str())
.collect();
assert_eq!(unenforced, ["polling"]);
assert!(!prog.may_have_syscall_count_anchor_at(t7, 2));
let count_only = HappensBeforeSpec::from_json(
r#"{"version": 1, "events": {"a": {"thread": "7", "syscalls": 2}}}"#,
)
.unwrap()
.normalize()
.unwrap();
assert!(!count_only.has_syscall_occurrence_anchors());
}
#[test]
fn parse_and_normalize_rfc_example() {
let spec = HappensBeforeSpec::from_json(spec_json()).unwrap();
let prog = spec.normalize().unwrap();
assert_eq!(prog.anchors.len(), 6);
assert_eq!(prog.edges.len(), 3);
assert_eq!(prog.anchors["scA"].position, Position::SyscallCount(10));
assert_eq!(prog.anchors["rcbB"].position, Position::Rcb(123456));
match &prog.anchors["X_342"].position {
Position::Rip { addr: None, nth } => assert_eq!(*nth, 342),
other => panic!("expected unresolved RIP, got {:?}", other),
}
assert_eq!(
prog.anchors["X_342"].location.function.as_deref(),
Some("free_buffer")
);
assert_eq!(prog.anchors["X_342"].location.line, Some(120));
match &prog.anchors["lockA"].position {
Position::Syscall {
sysno,
phase,
nth,
fd: None,
futex_op: None,
} => {
assert_eq!(*sysno, Sysno::futex);
assert_eq!(*phase, Some(SyscallPhase::Posthook));
assert_eq!(*nth, 5);
}
other => panic!("expected syscall, got {:?}", other),
}
assert_eq!(
prog.anchors["storeB"].position,
Position::Rip {
addr: Some(0x401f3c),
nth: 1
}
);
assert_eq!(prog.edges[2].strength, Strength::Soft);
assert_eq!(prog.edges[1].strength, Strength::Hard);
assert_eq!(prog.unresolved_locations().count(), 2);
}
#[test]
fn round_trip_json() {
let spec = HappensBeforeSpec::from_json(spec_json()).unwrap();
let json = spec.to_json().unwrap();
let spec2 = HappensBeforeSpec::from_json(&json).unwrap();
assert_eq!(spec, spec2);
}
#[test]
fn rejects_wrong_version() {
let spec = HappensBeforeSpec {
version: 999,
..HappensBeforeSpec::from_json(spec_json()).unwrap()
};
assert_eq!(
spec.normalize().unwrap_err(),
HappensBeforeError::UnsupportedVersion(999)
);
}
#[test]
fn rejects_ambiguous_position() {
let json = r#"{
"version": 1,
"events": { "bad": {"thread": "1", "syscalls": 3, "rcbs": 5} },
"edges": []
}"#;
let spec = HappensBeforeSpec::from_json(json).unwrap();
match spec.normalize().unwrap_err() {
HappensBeforeError::AmbiguousPosition { event, found } => {
assert_eq!(event, "bad");
assert_eq!(found.len(), 2);
}
other => panic!("expected AmbiguousPosition, got {:?}", other),
}
}
#[test]
fn rejects_no_position() {
let json = r#"{
"version": 1,
"events": { "bad": {"thread": "1"} },
"edges": []
}"#;
let spec = HappensBeforeSpec::from_json(json).unwrap();
assert!(matches!(
spec.normalize().unwrap_err(),
HappensBeforeError::AmbiguousPosition { .. }
));
}
#[test]
fn code_location_accompanies_count() {
let json = r#"{
"version": 1,
"events": {
"w": {"thread": "1", "func": "free_buffer", "line": 342, "syscalls": 7},
"r": {"thread": "1", "func": "read_buffer", "rcbs": 900}
},
"edges": [ {"before": "w", "after": "r"} ]
}"#;
let prog = HappensBeforeSpec::from_json(json)
.unwrap()
.normalize()
.unwrap();
assert_eq!(prog.anchors["w"].position, Position::SyscallCount(7));
assert_eq!(
prog.anchors["w"].location.function.as_deref(),
Some("free_buffer")
);
assert_eq!(prog.anchors["w"].location.line, Some(342));
assert_eq!(prog.anchors["r"].position, Position::Rcb(900));
assert_eq!(
prog.anchors["r"].location.function.as_deref(),
Some("read_buffer")
);
assert_eq!(prog.unresolved_locations().count(), 0);
}
#[test]
fn raw_dettid_thread() {
let json = r#"{
"version": 1,
"events": { "e": {"thread": "42", "rcbs": 7} },
"edges": []
}"#;
let prog = HappensBeforeSpec::from_json(json)
.unwrap()
.normalize()
.unwrap();
assert_eq!(prog.anchors["e"].thread.dettid, Some(DetTid::from_raw(42)));
}
#[test]
fn rejects_unknown_thread() {
let json = r#"{
"version": 1,
"events": { "e": {"thread": "ghost", "rcbs": 7} },
"edges": []
}"#;
let spec = HappensBeforeSpec::from_json(json).unwrap();
assert!(matches!(
spec.normalize().unwrap_err(),
HappensBeforeError::UnknownThread { .. }
));
}
#[test]
fn rejects_unknown_event_in_edge() {
let json = r#"{
"version": 1,
"events": { "a": {"thread": "1", "rcbs": 7} },
"edges": [ {"before": "a", "after": "missing"} ]
}"#;
let spec = HappensBeforeSpec::from_json(json).unwrap();
assert!(matches!(
spec.normalize().unwrap_err(),
HappensBeforeError::UnknownEvent { .. }
));
}
#[test]
fn rejects_unknown_syscall() {
let json = r#"{
"version": 1,
"events": { "a": {"thread": "1", "syscall": "not_a_syscall"} },
"edges": []
}"#;
let spec = HappensBeforeSpec::from_json(json).unwrap();
assert!(matches!(
spec.normalize().unwrap_err(),
HappensBeforeError::UnknownSyscall { .. }
));
}
#[test]
fn detects_cycle() {
let json = r#"{
"version": 1,
"events": {
"a": {"thread": "1", "rcbs": 1},
"b": {"thread": "1", "rcbs": 2},
"c": {"thread": "1", "rcbs": 3}
},
"edges": [
{"before": "a", "after": "b"},
{"before": "b", "after": "c"},
{"before": "c", "after": "a"}
]
}"#;
let spec = HappensBeforeSpec::from_json(json).unwrap();
match spec.normalize().unwrap_err() {
HappensBeforeError::Cycle(path) => {
assert_eq!(path.first(), path.last());
assert!(path.len() >= 4);
}
other => panic!("expected Cycle, got {:?}", other),
}
}
#[test]
fn accepts_dag() {
let json = r#"{
"version": 1,
"events": {
"a": {"thread": "1", "rcbs": 1},
"b": {"thread": "1", "rcbs": 2},
"c": {"thread": "1", "rcbs": 3}
},
"edges": [
{"before": "a", "after": "c"},
{"before": "b", "after": "c"}
]
}"#;
let spec = HappensBeforeSpec::from_json(json).unwrap();
assert!(spec.normalize().is_ok());
}
#[test]
fn dsl_desugars() {
let dsl = "\
// btrfs race: erase-by-key must precede the re-insert
writer:free_buffer#342 < reader:read_buffer#97
writer:futex@post#5 < reader:@0x401f3c#1
A:rcb=123456 < B:sc=97 !soft
";
let spec = HappensBeforeSpec::from_dsl(dsl).unwrap();
let prog = spec.normalize().unwrap();
assert_eq!(prog.edges.len(), 3);
assert_eq!(prog.anchors.len(), 6);
let soft = &prog.edges[2];
assert_eq!(soft.strength, Strength::Soft);
assert_eq!(prog.anchors[&soft.before].position, Position::Rcb(123456));
assert_eq!(
prog.anchors[&soft.after].position,
Position::SyscallCount(97)
);
let futex = prog
.anchors
.values()
.find(
|a| matches!(a.position, Position::Syscall { sysno, .. } if sysno == Sysno::futex),
)
.unwrap();
match &futex.position {
Position::Syscall { phase, nth, .. } => {
assert_eq!(*phase, Some(SyscallPhase::Posthook));
assert_eq!(*nth, 5);
}
_ => unreachable!(),
}
}
#[test]
fn dsl_rejects_missing_arrow() {
let err = HappensBeforeSpec::from_dsl("writer:foo reader:bar").unwrap_err();
assert!(matches!(err, HappensBeforeError::DslSyntax { line: 1, .. }));
}
#[test]
fn parse_rip_forms() {
assert_eq!(parse_rip("0x401f3c"), Some(0x401f3c));
assert_eq!(parse_rip("4201276"), Some(4201276));
assert_eq!(parse_rip("nonsense"), None);
}
fn normalize_json(json: &str) -> Result<HappensBeforeProgram, HappensBeforeError> {
HappensBeforeSpec::from_json(json).unwrap().normalize()
}
#[test]
fn version_2_fields_need_version_2() {
let v1 = normalize_json(
r#"{"version": 1, "events": {"w": {"thread": "7", "syscall": "write", "fd": 1}}}"#,
)
.unwrap();
assert_eq!((v1.version, v1.max_hold_ns), (1, None));
assert!(!v1.is_version_2());
let v2 = normalize_json(
r#"{"version": 2, "events": {"w": {"thread": "7", "syscall": "write", "fd": 1}}}"#,
)
.unwrap();
assert_eq!(v2.max_hold_ns, Some(DEFAULT_MAX_HOLD_NS));
assert!(v2.is_version_2());
let budget = normalize_json(
r#"{"version": 2, "max_hold_ns": 5000,
"events": {"w": {"thread": "7", "syscall": "write", "fd": 1}}}"#,
)
.unwrap();
assert_eq!(budget.max_hold_ns, Some(5000));
for (json, event, field) in [
(
r#"{"version": 1, "events": {
"a": {"thread": "7", "syscall": "write", "fd": 1},
"r": {"thread": "7", "syscall": "getppid", "from": "a"}}}"#,
Some("r"),
"from",
),
(
r#"{"version": 1, "events": {
"f": {"thread": "7", "syscall": "futex", "futex_op": 393}}}"#,
Some("f"),
"futex_op",
),
(
r#"{"version": 1, "max_hold_ns": 5,
"events": {"w": {"thread": "7", "syscall": "write"}}}"#,
None,
"max_hold_ns",
),
] {
assert_eq!(
normalize_json(json).unwrap_err(),
HappensBeforeError::NewFieldInVersion1 {
event: event.map(str::to_owned),
field: field.to_owned(),
}
);
}
assert_eq!(
normalize_json(r#"{"version": 3, "events": {}}"#).unwrap_err(),
HappensBeforeError::UnsupportedVersion(3)
);
let dsl = HappensBeforeSpec::from_dsl("A:sc=3 < B:sc=4").unwrap();
assert_eq!(dsl.version, HAPPENS_BEFORE_VERSION_1);
}
#[test]
fn version_2_refuses_unknown_fields() {
for (json, place, field) in [
(r#"{"version": 2, "evnets": {}}"#, "the spec", "evnets"),
(
r#"{"version": 2, "events": {"w": {"thread": "7", "syscal": "write"}}}"#,
"event 'w'",
"syscal",
),
(
r#"{"version": 2, "threads": {"t": {"dettid": 7, "tid": 7}}}"#,
"thread 't'",
"tid",
),
(
r#"{"version": 2, "events": {}, "edges": [{"before": "a", "after": "b", "kind": 1}]}"#,
"edge 0",
"kind",
),
] {
let error = HappensBeforeSpec::from_json(json).unwrap_err();
assert_eq!(
error.downcast_ref::<HappensBeforeError>(),
Some(&HappensBeforeError::UnknownField {
place: place.to_owned(),
field: field.to_owned(),
}),
"{json}"
);
}
normalize_json(r#"{"version": 2, "events": {"r": {"thread": "7", "rcb": 5}}}"#).unwrap();
normalize_json(r#"{"version": 1, "events": {}, "evnets": {}}"#).unwrap();
}
#[test]
fn a_duplicated_field_is_refused() {
for json in [
r#"{"version": 1, "events": {"w": {"thread": "7", "syscall": "write", "nth": 1, "nth": 2}}}"#,
r#"{"version": 2, "events": {"w": {"thread": "7", "syscall": "write", "nth": 1, "nth": 2}}}"#,
r#"{"version": 2, "max_hold_ns": 5, "max_hold_ns": 6, "events": {}}"#,
] {
let error = HappensBeforeSpec::from_json(json).unwrap_err().to_string();
assert!(error.contains("duplicate field"), "{json}: {error}");
}
}
#[test]
fn a_posthook_anchor_is_counted_at_entry_and_refused_on_no_return_syscalls() {
let prog = normalize_json(
r#"{"version": 1, "events": {
"w": {"thread": "7", "syscall": "write", "fd": 1, "phase": "posthook", "nth": 2}}}"#,
)
.unwrap();
let w = &prog.anchors["w"];
assert!(w.is_syscall_occurrence() && w.fires_at_posthook());
assert_eq!(prog.unenforced_positions().count(), 0);
let t7 = DetTid::from_raw(7);
let mut c = HbThreadCounters::default();
assert!(
prog.count_syscall_occurrences(&mut c, t7, Sysno::write, [1, 0], 1)
.is_empty()
);
assert_eq!(
prog.count_syscall_occurrences(&mut c, t7, Sysno::write, [1, 0], 2),
["w"]
);
for syscall in ["execve", "execveat", "exit", "exit_group", "rt_sigreturn"] {
assert_eq!(
normalize_json(&format!(
r#"{{"version": 1, "events": {{"x": {{"thread": "7", "syscall": "{syscall}", "phase": "posthook"}}}}}}"#
))
.unwrap_err(),
HappensBeforeError::PosthookOnNoReturnSyscall {
event: "x".to_owned(),
syscall: syscall.to_owned()
}
);
}
normalize_json(r#"{"version": 1, "events": {"x": {"thread": "7", "syscall": "execve"}}}"#)
.unwrap();
}
#[test]
fn futex_op_matches_the_low_32_bits_of_the_operation() {
let prog = normalize_json(
r#"{"version": 2, "events": {
"halt": {"thread": "7", "syscall": "futex", "futex_op": 393, "nth": 2},
"wait": {"thread": "7", "syscall": "futex", "futex_op": 0}}}"#,
)
.unwrap();
assert_eq!(prog.anchors["halt"].position.to_string(), "futex(op=393)#2");
let t7 = DetTid::from_raw(7);
let mut c = HbThreadCounters::default();
let mut entry = 0;
let mut call = |c: &mut HbThreadCounters, op: usize| {
entry += 1;
prog.count_syscall_occurrences(c, t7, Sysno::futex, [0x1000, op], entry)
};
assert_eq!(call(&mut c, 393), Vec::<String>::new());
assert_eq!(call(&mut c, 0), ["wait"]);
assert_eq!(call(&mut c, 0xdead_0000_0000_0189), ["halt"]);
assert_eq!(c.counts[&(Sysno::futex as usize, None, Some(393))], 2);
assert_eq!(c.counts[&(Sysno::futex as usize, None, Some(0))], 1);
assert_eq!(
normalize_json(
r#"{"version": 2, "events": {"w": {"thread": "7", "syscall": "write", "futex_op": 1}}}"#,
)
.unwrap_err(),
HappensBeforeError::FutexOpWithoutFutex {
event: "w".to_owned()
}
);
assert_eq!(
normalize_json(
r#"{"version": 2, "events": {"w": {"thread": "7", "futex_op": 1, "syscalls": 3}}}"#
)
.unwrap_err(),
HappensBeforeError::FutexOpWithoutFutex {
event: "w".to_owned()
}
);
assert_eq!(
normalize_json(
r#"{"version": 2, "events": {"f": {"thread": "7", "syscall": "futex", "futex_op": 2147483648}}}"#,
)
.unwrap_err(),
HappensBeforeError::FutexOpOutOfRange {
event: "f".to_owned(),
value: 2147483648
}
);
}
#[test]
fn from_refusals_name_the_event() {
let refused = |events: &str, edges: &str| {
normalize_json(&format!(
r#"{{"version": 2, "events": {{{events}}}, "edges": [{edges}]}}"#
))
.unwrap_err()
};
let names = |e: &str, b: &str| (e.to_owned(), b.to_owned());
let (event, base) = names("r", "nope");
assert_eq!(
refused(
r#""r": {"thread": "7", "syscall": "getppid", "from": "nope"}"#,
""
),
HappensBeforeError::FromUnknownEvent { event, base }
);
let (event, base) = names("r", "a");
assert_eq!(
refused(
r#""a": {"thread": "8", "syscall": "write", "fd": 1},
"r": {"thread": "7", "syscall": "getppid", "from": "a"}"#,
""
),
HappensBeforeError::FromOtherThread { event, base }
);
let (event, base) = names("r", "a");
assert_eq!(
refused(
r#""a": {"thread": "7", "rcbs": 100},
"r": {"thread": "7", "syscall": "getppid", "from": "a"}"#,
""
),
HappensBeforeError::FromUnenforcedPosition { event, base }
);
let (event, base) = names("r", "a");
assert_eq!(
refused(
r#""a": {"thread": "7", "syscall": "write", "phase": "polling"},
"r": {"thread": "7", "syscall": "getppid", "from": "a"}"#,
""
),
HappensBeforeError::FromUnenforcedPosition { event, base }
);
let (event, base) = names("r2", "r1");
assert_eq!(
refused(
r#""a": {"thread": "7", "syscalls": 3},
"r1": {"thread": "7", "syscall": "getppid", "from": "a"},
"r2": {"thread": "7", "syscall": "getppid", "from": "r1"}"#,
""
),
HappensBeforeError::FromRelativeBase { event, base }
);
assert_eq!(
refused(
r#""a": {"thread": "7", "syscalls": 3},
"r": {"thread": "7", "syscalls": 9, "from": "a"}"#,
""
),
HappensBeforeError::FromOnNonOccurrence {
event: "r".to_owned()
}
);
assert_eq!(
refused(
r#""a": {"thread": "7", "syscalls": 3},
"r": {"thread": "7", "syscall": "getppid", "from": "a"}"#,
r#"{"before": "r", "after": "a"}"#
),
HappensBeforeError::FromCycle(vec!["a".to_owned(), "r".to_owned(), "a".to_owned()])
);
normalize_json(
r#"{"version": 2, "threads": {"main": {"dettid": 3}, "s1": {"spawn_ordinal": 1}},
"events": {"a": {"thread": "main", "syscall": "write", "fd": 1},
"r": {"thread": "3", "syscall": "getppid", "from": "a"},
"b": {"thread": "s1", "syscalls": 4},
"q": {"thread": "s1", "syscall": "getppid", "from": "b"}}}"#,
)
.unwrap();
let (event, base) = names("r", "a");
assert_eq!(
normalize_json(
r#"{"version": 2, "threads": {"s1": {"spawn_ordinal": 1}},
"events": {"a": {"thread": "7", "syscall": "write", "fd": 1},
"r": {"thread": "s1", "syscall": "getppid", "from": "a"}}}"#,
)
.unwrap_err(),
HappensBeforeError::FromOtherThread { event, base }
);
normalize_json(
r#"{"version": 2, "events": {
"a": {"thread": "7", "syscalls": 3},
"r": {"thread": "7", "syscall": "getppid", "from": "a"}},
"edges": [{"before": "r", "after": "a", "strength": "soft"}]}"#,
)
.unwrap();
}
#[test]
fn relative_anchors_count_strictly_after_their_base() {
let prog = normalize_json(
r#"{"version": 2, "events": {
"m2": {"thread": "7", "syscall": "write", "fd": 1, "nth": 2},
"abs3": {"thread": "7", "syscall": "getppid", "nth": 3},
"after_m2": {"thread": "7", "syscall": "getppid", "from": "m2", "nth": 1},
"c4": {"thread": "7", "syscalls": 4},
"after_c4": {"thread": "7", "syscall": "getppid", "from": "c4", "nth": 2},
"gp1": {"thread": "7", "syscall": "getppid", "nth": 1},
"after_gp1": {"thread": "7", "syscall": "getppid", "from": "gp1", "nth": 1}}}"#,
)
.unwrap();
assert_eq!(
prog.anchors["after_m2"].to_string(),
"after_m2[7: getppid#1 after m2]"
);
let relative: Vec<(&str, &str)> = prog
.relative_anchors()
.map(|(r, b)| (r.name.as_str(), b.name.as_str()))
.collect();
assert_eq!(
relative,
[("after_c4", "c4"), ("after_gp1", "gp1"), ("after_m2", "m2")]
);
let t7 = DetTid::from_raw(7);
let mut c = HbThreadCounters::default();
let mut entry = 0;
let mut call = |c: &mut HbThreadCounters, sysno: Sysno, arg0: usize| {
entry += 1;
prog.count_syscall_occurrences(c, t7, sysno, [arg0, 0], entry)
};
assert_eq!(call(&mut c, Sysno::getppid, 0), ["gp1"]);
assert_eq!(c.origins["after_gp1"], 1);
assert!(call(&mut c, Sysno::write, 1).is_empty());
assert_eq!(call(&mut c, Sysno::getppid, 0), ["after_gp1"]);
assert!(call(&mut c, Sysno::getpid, 0).is_empty());
assert_eq!(c.origins["after_c4"], 2);
assert_eq!(call(&mut c, Sysno::write, 1), ["m2"]);
assert_eq!(c.origins["after_m2"], 2);
assert_eq!(call(&mut c, Sysno::getppid, 0), ["abs3", "after_m2"]);
assert_eq!(call(&mut c, Sysno::getppid, 0), ["after_c4"]);
assert!(call(&mut c, Sysno::getppid, 0).is_empty());
assert_eq!(c.counts[&(Sysno::getppid as usize, None, None)], 5);
let mut c8 = HbThreadCounters::default();
assert!(
prog.count_syscall_occurrences(&mut c8, DetTid::from_raw(8), Sysno::getppid, [0, 0], 1)
.is_empty()
);
assert!(c8.origins.is_empty());
}
#[test]
fn a_posthook_anchor_shares_its_counter_and_starts_windows_at_its_entry() {
let prog = normalize_json(
r#"{"version": 2, "events": {
"pre2": {"thread": "7", "syscall": "write", "fd": 1, "nth": 2},
"post2": {"thread": "7", "syscall": "write", "fd": 1, "nth": 2,
"phase": "posthook"},
"post3": {"thread": "7", "syscall": "write", "fd": 1, "nth": 3,
"phase": "posthook"},
"base": {"thread": "7", "syscall": "getpid", "phase": "posthook"},
"after_base": {"thread": "7", "syscall": "write", "fd": 1, "from": "base",
"nth": 1}}}"#,
)
.unwrap();
let t7 = DetTid::from_raw(7);
let mut c = HbThreadCounters::default();
let mut entry = 0;
let mut call = |c: &mut HbThreadCounters, sysno: Sysno, arg0: usize| {
entry += 1;
prog.count_syscall_occurrences(c, t7, sysno, [arg0, 0], entry)
};
assert!(call(&mut c, Sysno::write, 1).is_empty());
assert_eq!(call(&mut c, Sysno::write, 1), ["post2", "pre2"]);
assert_eq!(call(&mut c, Sysno::getpid, 0), ["base"]);
assert_eq!(c.origins["after_base"], 2);
assert_eq!(call(&mut c, Sysno::write, 1), ["after_base", "post3"]);
assert_eq!(c.counts[&(Sysno::write as usize, Some(1), None)], 3);
}
}