crates/mimir-ingest/src/boundary/btf.rs
//! The kernel's types and functions from BTF (`/sys/kernel/btf/vmlinux`, or
//! a vmlinux BTF file) — read, never compiled.
//!
//! BTF (Documentation/bpf/btf.rst): a header, a type section of
//! `struct btf_type` records (ids from 1; 0 is `void`) each followed by its
//! kind's extra data, and a string section. This reader keeps what the
//! graph needs:
//!
//! * a NODE per named `struct` / `union` / `enum` (+`enum64`) / `typedef` /
//! `func` (and per named forward declaration no definition answers);
//! * USES_TYPE from an aggregate to the named types of its members, from a
//! typedef to the type it names, from a function to the named types of
//! its parameters and return. Pointers, `const` / `volatile` / `restrict`,
//! arrays and type tags are looked through to the named type; an
//! ANONYMOUS struct / union (a member's inline aggregate) and a function
//! prototype (a function-pointer member) are flattened into their named
//! container — C names them nowhere else.
use std::collections::{BTreeSet, HashMap};
use anyhow::{Context, Result, bail};
const MAGIC: u16 = 0xeb9f;
/// BTF kinds (`BTF_KIND_*`).
pub mod k {
pub const UNKN: u8 = 0;
pub const INT: u8 = 1;
pub const PTR: u8 = 2;
pub const ARRAY: u8 = 3;
pub const STRUCT: u8 = 4;
pub const UNION: u8 = 5;
pub const ENUM: u8 = 6;
pub const FWD: u8 = 7;
pub const TYPEDEF: u8 = 8;
pub const VOLATILE: u8 = 9;
pub const CONST: u8 = 10;
pub const RESTRICT: u8 = 11;
pub const FUNC: u8 = 12;
pub const FUNC_PROTO: u8 = 13;
pub const VAR: u8 = 14;
pub const DATASEC: u8 = 15;
pub const FLOAT: u8 = 16;
pub const DECL_TAG: u8 = 17;
pub const TYPE_TAG: u8 = 18;
pub const ENUM64: u8 = 19;
}
/// One BTF type record.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Ty {
pub kind: u8,
pub name_off: u32,
pub vlen: u16,
pub kind_flag: bool,
/// `size` (int, struct, union, enum, float, datasec) or `type` (the rest).
pub size_or_type: u32,
/// Index into [`Btf::refs`] of the first member / param; arrays keep
/// their element type at `refs[first].1`.
pub first: u32,
}
/// A parsed BTF blob.
pub struct Btf {
/// Index = type id; `types[0]` is `void`.
pub types: Vec<Ty>,
/// `(name_off, type id)` of every member / param / enum value (type 0) /
/// array element.
pub refs: Vec<(u32, u32)>,
strings: Vec<u8>,
}
fn u16_at(b: &[u8], o: usize) -> Result<u16> {
Ok(u16::from_le_bytes(b.get(o..o + 2).context("BTF truncated")?.try_into()?))
}
fn u32_at(b: &[u8], o: usize) -> Result<u32> {
Ok(u32::from_le_bytes(b.get(o..o + 4).context("BTF truncated")?.try_into()?))
}
impl Btf {
/// Parse a little-endian BTF blob (raw `.BTF` section contents, the form
/// `/sys/kernel/btf/vmlinux` serves).
pub fn parse(b: &[u8]) -> Result<Btf> {
if u16_at(b, 0)? != MAGIC {
bail!("not BTF (magic {:#06x}; a big-endian or non-BTF file)", u16_at(b, 0)?);
}
let hdr_len = u32_at(b, 4)? as usize;
let (type_off, type_len) = (u32_at(b, 8)? as usize, u32_at(b, 12)? as usize);
let (str_off, str_len) = (u32_at(b, 16)? as usize, u32_at(b, 20)? as usize);
let types_at = hdr_len + type_off;
let strs_at = hdr_len + str_off;
let tsec = b.get(types_at..types_at + type_len).context("BTF type section past the end")?;
let strings = b.get(strs_at..strs_at + str_len).context("BTF string section past the end")?.to_vec();
let mut types = vec![Ty { kind: k::UNKN, name_off: 0, vlen: 0, kind_flag: false, size_or_type: 0, first: 0 }];
let mut refs: Vec<(u32, u32)> = Vec::new();
let mut o = 0usize;
while o < tsec.len() {
let name_off = u32_at(tsec, o)?;
let info = u32_at(tsec, o + 4)?;
let size_or_type = u32_at(tsec, o + 8)?;
o += 12;
let vlen = (info & 0xffff) as u16;
let kind = ((info >> 24) & 0x1f) as u8;
let kind_flag = info >> 31 == 1;
let first = refs.len() as u32;
match kind {
k::INT => o += 4,
k::ARRAY => {
refs.push((0, u32_at(tsec, o)?));
o += 12;
}
k::STRUCT | k::UNION => {
for _ in 0..vlen {
refs.push((u32_at(tsec, o)?, u32_at(tsec, o + 4)?));
o += 12;
}
}
k::ENUM => {
for _ in 0..vlen {
refs.push((u32_at(tsec, o)?, 0));
o += 8;
}
}
k::ENUM64 => {
for _ in 0..vlen {
refs.push((u32_at(tsec, o)?, 0));
o += 12;
}
}
k::FUNC_PROTO => {
for _ in 0..vlen {
refs.push((u32_at(tsec, o)?, u32_at(tsec, o + 4)?));
o += 8;
}
}
k::VAR => o += 4,
k::DATASEC => o += 12 * vlen as usize,
k::DECL_TAG => o += 4,
k::PTR | k::FWD | k::TYPEDEF | k::VOLATILE | k::CONST | k::RESTRICT | k::FUNC | k::FLOAT | k::TYPE_TAG => {}
other => bail!("BTF kind {other} at type {} is not known to this reader", types.len()),
}
types.push(Ty { kind, name_off, vlen, kind_flag, size_or_type, first });
}
if o != tsec.len() {
bail!("BTF type section: records overrun the section ({o} of {})", tsec.len());
}
Ok(Btf { types, refs, strings })
}
/// The string at `off` of the string section (`""` past it).
pub fn str(&self, off: u32) -> &str {
let s = self.strings.get(off as usize..).unwrap_or(&[]);
let end = s.iter().position(|c| *c == 0).unwrap_or(s.len());
std::str::from_utf8(&s[..end]).unwrap_or("")
}
pub fn name(&self, id: u32) -> &str {
self.types.get(id as usize).map_or("", |t| self.str(t.name_off))
}
/// The members / params / values of type `id`.
pub fn refs_of(&self, id: u32) -> &[(u32, u32)] {
let t = &self.types[id as usize];
let n = match t.kind {
k::ARRAY => 1,
k::STRUCT | k::UNION | k::ENUM | k::ENUM64 | k::FUNC_PROTO => t.vlen as usize,
_ => 0,
};
&self.refs[t.first as usize..t.first as usize + n]
}
/// The type a modifier / pointer / typedef / func / array looks at.
fn inner(&self, id: u32) -> Option<u32> {
let t = self.types.get(id as usize)?;
match t.kind {
k::PTR | k::TYPEDEF | k::VOLATILE | k::CONST | k::RESTRICT | k::FUNC | k::TYPE_TAG | k::DECL_TAG | k::VAR => Some(t.size_or_type),
k::ARRAY => self.refs_of(id).first().map(|r| r.1),
_ => None,
}
}
/// C spelling of type `id` (bounded depth).
pub fn c_type(&self, id: u32) -> String {
self.c_type_d(id, 0)
}
fn c_type_d(&self, id: u32, depth: u32) -> String {
if depth > 12 {
return "…".into();
}
let Some(t) = self.types.get(id as usize) else { return format!("<type {id}>") };
let name = self.str(t.name_off);
let anon = |w: &str| if name.is_empty() { format!("{w} {{…}}") } else { format!("{w} {name}") };
match t.kind {
k::UNKN => "void".into(),
k::INT | k::FLOAT | k::TYPEDEF => name.to_string(),
k::STRUCT => anon("struct"),
k::UNION => anon("union"),
k::ENUM | k::ENUM64 => anon("enum"),
k::FWD => format!("{} {name}", if t.kind_flag { "union" } else { "struct" }),
k::PTR => format!("{} *", self.c_type_d(t.size_or_type, depth + 1)),
k::CONST => format!("const {}", self.c_type_d(t.size_or_type, depth + 1)),
k::VOLATILE => format!("volatile {}", self.c_type_d(t.size_or_type, depth + 1)),
k::RESTRICT => format!("{} restrict", self.c_type_d(t.size_or_type, depth + 1)),
k::TYPE_TAG | k::DECL_TAG => self.c_type_d(t.size_or_type, depth + 1),
k::ARRAY => format!("{}[]", self.c_type_d(self.inner(id).unwrap_or(0), depth + 1)),
k::FUNC_PROTO => {
let params: Vec<String> = self.refs_of(id).iter().map(|p| if p.1 == 0 { "...".to_string() } else { self.c_type_d(p.1, depth + 1) }).collect();
format!("{} (*)({})", self.c_type_d(t.size_or_type, depth + 1), params.join(", "))
}
k::FUNC => name.to_string(),
_ => format!("<kind {}>", t.kind),
}
}
/// The function's prototype as C prints it: `long __x64_sys_read(const struct pt_regs * regs)`.
pub fn func_signature(&self, func: u32) -> String {
let t = self.types[func as usize];
let proto = t.size_or_type;
let Some(p) = self.types.get(proto as usize).filter(|p| p.kind == k::FUNC_PROTO) else { return self.str(t.name_off).to_string() };
let params: Vec<String> = self
.refs_of(proto)
.iter()
.map(|(n, ty)| if *ty == 0 { "...".to_string() } else { format!("{} {}", self.c_type(*ty), self.str(*n)).trim_end().to_string() })
.collect();
format!("{} {}({})", self.c_type(p.size_or_type), self.str(t.name_off), params.join(", "))
}
}
/// The C name space a named BTF type lives in (`None` = not a node).
pub fn namespace(t: &Ty) -> Option<&'static str> {
Some(match t.kind {
k::STRUCT => "struct",
k::UNION => "union",
k::ENUM | k::ENUM64 => "enum",
k::TYPEDEF => "typedef",
k::FUNC => "func",
k::FWD if t.kind_flag => "union",
k::FWD => "struct",
_ => return None,
})
}
/// The named node types (`(namespace, name)` → type id) and, per type id, the
/// node it is: a forward declaration answered by a definition is that
/// definition; a second definition of one name gets its own (dup) node.
pub struct Names {
/// type id → (namespace, name, dup: Some(type id) for a second definition)
pub node_of: HashMap<u32, (&'static str, String, Option<u32>)>,
}
impl Names {
pub fn of(btf: &Btf) -> Names {
let mut first: HashMap<(&'static str, &str), u32> = HashMap::new();
let mut node_of = HashMap::new();
// definitions first (forward declarations then fold into them)
for (id, t) in btf.types.iter().enumerate().skip(1) {
let Some(ns) = namespace(t) else { continue };
let name = btf.str(t.name_off);
if name.is_empty() || t.kind == k::FWD {
continue;
}
let id = id as u32;
let dup = match first.get(&(ns, name)) {
None => {
first.insert((ns, name), id);
None
}
Some(_) => Some(id),
};
node_of.insert(id, (ns, name.to_string(), dup));
}
for (id, t) in btf.types.iter().enumerate().skip(1) {
if t.kind != k::FWD {
continue;
}
let (Some(ns), name) = (namespace(t), btf.str(t.name_off)) else { continue };
if name.is_empty() {
continue;
}
node_of.insert(id as u32, (ns, name.to_string(), None));
}
Names { node_of }
}
}
/// The named node types `id` uses: through modifiers, pointers, arrays,
/// type tags; anonymous aggregates and function prototypes are flattened.
pub fn named_uses(btf: &Btf, names: &Names, id: u32, out: &mut BTreeSet<u32>, seen: &mut BTreeSet<u32>) {
let mut cur = id;
for _ in 0..64 {
if cur == 0 || !seen.insert(cur) {
return;
}
if names.node_of.contains_key(&cur) {
out.insert(cur);
return;
}
let t = btf.types[cur as usize];
match t.kind {
// an anonymous aggregate / a prototype: what IT uses
k::STRUCT | k::UNION | k::FUNC_PROTO => {
for &(_, ty) in btf.refs_of(cur) {
named_uses(btf, names, ty, out, seen);
}
if t.kind == k::FUNC_PROTO {
named_uses(btf, names, t.size_or_type, out, seen);
}
return;
}
_ => match btf.inner(cur) {
Some(n) => cur = n,
None => return,
},
}
}
}
/// A small BTF WRITER: builds a blob with chosen types — the test kernels
/// (a few types under real kernel names; generated, so no kernel's BTF is
/// copied into a repository).
#[derive(Default)]
pub struct Writer {
types: Vec<u8>,
strings: Vec<u8>,
next: u32,
}
impl Writer {
pub fn new() -> Writer {
Writer { types: Vec::new(), strings: vec![0], next: 1 }
}
fn s(&mut self, name: &str) -> u32 {
if name.is_empty() {
return 0;
}
let off = self.strings.len() as u32;
self.strings.extend_from_slice(name.as_bytes());
self.strings.push(0);
off
}
fn head(&mut self, name: &str, kind: u8, vlen: u16, kflag: bool, size_or_type: u32) -> u32 {
let n = self.s(name);
let info = (vlen as u32) | ((kind as u32) << 24) | if kflag { 1 << 31 } else { 0 };
for v in [n, info, size_or_type] {
self.types.extend_from_slice(&v.to_le_bytes());
}
let id = self.next;
self.next += 1;
id
}
fn u32s(&mut self, vs: &[u32]) {
for v in vs {
self.types.extend_from_slice(&v.to_le_bytes());
}
}
pub fn int(&mut self, name: &str, size: u32) -> u32 {
let id = self.head(name, k::INT, 0, false, size);
self.u32s(&[size * 8]);
id
}
pub fn ptr(&mut self, to: u32) -> u32 {
self.head("", k::PTR, 0, false, to)
}
pub fn konst(&mut self, to: u32) -> u32 {
self.head("", k::CONST, 0, false, to)
}
pub fn array(&mut self, elem: u32, index: u32, n: u32) -> u32 {
let id = self.head("", k::ARRAY, 0, false, 0);
self.u32s(&[elem, index, n]);
id
}
/// A struct (`union` = false) or union with `(name, type)` members.
pub fn aggregate(&mut self, name: &str, union: bool, size: u32, members: &[(&str, u32)]) -> u32 {
let id = self.head(name, if union { k::UNION } else { k::STRUCT }, members.len() as u16, false, size);
for (i, (m, t)) in members.iter().enumerate() {
let n = self.s(m);
self.u32s(&[n, *t, (i as u32) * 64]);
}
id
}
pub fn fwd(&mut self, name: &str, union: bool) -> u32 {
self.head(name, k::FWD, 0, union, 0)
}
pub fn typedef(&mut self, name: &str, to: u32) -> u32 {
self.head(name, k::TYPEDEF, 0, false, to)
}
pub fn enumeration(&mut self, name: &str, values: &[(&str, i32)]) -> u32 {
let id = self.head(name, k::ENUM, values.len() as u16, false, 4);
for (v, x) in values {
let n = self.s(v);
self.u32s(&[n, *x as u32]);
}
id
}
pub fn func_proto(&mut self, ret: u32, params: &[(&str, u32)]) -> u32 {
let id = self.head("", k::FUNC_PROTO, params.len() as u16, false, ret);
for (p, t) in params {
let n = self.s(p);
self.u32s(&[n, *t]);
}
id
}
/// A function (linkage 0 static, 1 global).
pub fn func(&mut self, name: &str, proto: u32, linkage: u16) -> u32 {
self.head(name, k::FUNC, linkage, false, proto)
}
pub fn finish(&self) -> Vec<u8> {
let mut out = Vec::new();
out.extend_from_slice(&MAGIC.to_le_bytes());
out.extend_from_slice(&[1, 0]);
for v in [24u32, 0, self.types.len() as u32, self.types.len() as u32, self.strings.len() as u32] {
out.extend_from_slice(&v.to_le_bytes());
}
out.extend_from_slice(&self.types);
out.extend_from_slice(&self.strings);
out
}
}
/// A tiny kernel under real names: `task_struct` (a `pid_t pid`, an
/// anonymous union holding a `struct mm_struct *` — only declared — and a
/// `struct list_head`), `pt_regs`, `__x64_sys_read(const struct pt_regs *)`,
/// `__do_sys_getpid(void)` (a SYSCALL_DEFINE0 call keeps only `__do_sys_*`),
/// `__x64_sys_connect`, `enum pid_type`.
pub fn sample_kernel() -> Vec<u8> {
let mut w = Writer::new();
let int = w.int("int", 4);
let long = w.int("long", 8);
let pid_t = w.typedef("pid_t", int);
let mm = w.fwd("mm_struct", false);
let mm_p = w.ptr(mm);
let list_head = w.aggregate("list_head", false, 16, &[]);
let anon = w.aggregate("", true, 8, &[("mm", mm_p), ("active_mm", mm_p)]);
let _task = w.aggregate("task_struct", false, 9920, &[("pid", pid_t), ("", anon), ("tasks", list_head)]);
let regs = w.aggregate("pt_regs", false, 168, &[("ax", long), ("di", long)]);
let cregs = w.konst(regs);
let pregs = w.ptr(cregs);
let proto = w.func_proto(long, &[("regs", pregs)]);
w.func("__x64_sys_read", proto, 1);
w.func("__x64_sys_connect", proto, 1);
let proto0 = w.func_proto(long, &[]);
w.func("__do_sys_getpid", proto0, 0);
w.enumeration("pid_type", &[("PIDTYPE_PID", 0), ("PIDTYPE_TGID", 1)]);
w.finish()
}