elfpak_core/
graph.rs

1//! The dependency graph records both *what* is included and *why*.
2
3use crate::{
4    elf::Architecture,
5    error::{Error, Result},
6    policy::RuntimeFeature,
7    source::SymlinkEntry,
8};
9use serde::{Deserialize, Serialize};
10use std::{
11    collections::{HashMap, HashSet},
12    path::{Path, PathBuf},
13};
14
15/// Index of a node in [`DependencyGraph::nodes`].
16pub type NodeId = u32;
17
18/// Upper bound on the objects in one runtime closure.
19///
20/// A real closure is tens of objects; a thousand would already be remarkable.
21/// The limit bounds work requested by a synthetic or malformed ELF graph.
22pub const NODES_MAX: usize = 4096;
23
24/// Upper bound on edges. Every edge is one `DT_NEEDED`, `PT_INTERP` or policy
25/// reason, so this allows an average of 64 dependencies per object.
26pub const EDGES_MAX: usize = NODES_MAX * 64;
27
28#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
29#[serde(transparent)]
30pub struct Digest(pub String);
31
32/// Length of a SHA-256 digest in lowercase hexadecimal.
33pub const DIGEST_LEN_HEX: usize = 64;
34
35impl Digest {
36    /// Whether this is a well-formed SHA-256 digest: 64 lowercase hex digits,
37    /// which is exactly what [`crate::paths::hex`] produces.
38    pub fn is_well_formed(&self) -> bool {
39        self.0.len() == DIGEST_LEN_HEX
40            && self
41                .0
42                .bytes()
43                .all(|byte| byte.is_ascii_digit() || (b'a'..=b'f').contains(&byte))
44    }
45}
46
47impl std::fmt::Display for Digest {
48    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
49        f.write_str(&self.0)
50    }
51}
52
53#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
54#[serde(rename_all = "snake_case")]
55pub enum NodeKind {
56    Executable,
57    Interpreter,
58    SharedObject,
59}
60
61#[derive(Debug, Clone)]
62pub struct Node {
63    /// Host path the bytes are read from.
64    pub source: PathBuf,
65    /// Logical path inside the source root.
66    pub logical: PathBuf,
67    /// Logical path inside the generated rootfs.
68    pub destination: PathBuf,
69    pub kind: NodeKind,
70    pub soname: Option<String>,
71    pub architecture: Architecture,
72    pub sha256: Digest,
73    pub size: u64,
74    /// Symlinks traversed to reach this object, preserved in the output.
75    pub links: Vec<SymlinkEntry>,
76    /// `dlopen`-family references found in this object.
77    pub dlopen_references: Vec<String>,
78}
79
80#[derive(Debug, Clone, PartialEq, Eq)]
81pub enum DependencyReason {
82    Interpreter,
83    Needed { soname: String },
84    RuntimePolicy { feature: RuntimeFeature },
85}
86
87#[derive(Debug, Clone)]
88pub struct Edge {
89    pub from: NodeId,
90    pub to: NodeId,
91    pub reason: DependencyReason,
92}
93
94#[derive(Debug, Clone, Default)]
95pub struct DependencyGraph {
96    pub root: NodeId,
97    pub nodes: Vec<Node>,
98    /// Every edge, in insertion order.
99    pub edges: Vec<Edge>,
100    /// `PT_INTERP` exactly as declared by the executable, before symlinks are
101    /// followed. This is the path the kernel will use at runtime.
102    pub declared_interpreter: Option<PathBuf>,
103    /// `DT_RPATH` and `DT_RUNPATH` of the executable, verbatim and unexpanded.
104    /// They travel with the binary, so they matter when it is installed
105    /// somewhere other than where it was built.
106    pub executable_search_paths: Vec<String>,
107    by_logical: HashMap<PathBuf, NodeId>,
108    /// Indices into `edges` leaving each node, in insertion order. Without it
109    /// every lookup scans the whole edge list, and the planner asks one
110    /// question per node; that is quadratic in a graph the limits above allow.
111    outgoing: HashMap<NodeId, Vec<usize>>,
112    /// Index into `edges` of the first edge that reaches each node.
113    first_incoming: HashMap<NodeId, usize>,
114}
115
116impl DependencyGraph {
117    pub fn new() -> DependencyGraph {
118        DependencyGraph::default()
119    }
120
121    pub fn node_count(&self) -> usize {
122        self.nodes.len()
123    }
124
125    /// Insert a node, deduplicating on the logical source path.
126    ///
127    /// Re-inserting a known object merges its symlink chain: the same library
128    /// is often reached through several link paths (`/lib64/ld-linux…` and
129    /// `/lib/<tuple>/ld-linux…`), and every one of them must be preserved.
130    pub fn insert(&mut self, node: Node) -> Result<NodeId> {
131        assert!(node.logical.is_absolute());
132        assert!(node.destination.is_absolute());
133        assert!(node.sha256.is_well_formed());
134
135        if let Some(&id) = self.by_logical.get(&node.logical) {
136            let existing = &mut self.nodes[id as usize];
137            for link in node.links {
138                if !existing.links.contains(&link) {
139                    existing.links.push(link);
140                }
141            }
142            return Ok(id);
143        }
144
145        if self.nodes.len() >= NODES_MAX {
146            return Err(Error::LimitExceeded {
147                resource: "runtime closure",
148                limit: NODES_MAX,
149            });
150        }
151        let id = NodeId::try_from(self.nodes.len()).expect("node count is bounded by NODES_MAX");
152        self.by_logical.insert(node.logical.clone(), id);
153        self.nodes.push(node);
154        assert_eq!(self.nodes.len(), self.by_logical.len());
155        Ok(id)
156    }
157
158    pub fn find(&self, logical: &Path) -> Option<NodeId> {
159        assert!(logical.is_absolute());
160        self.by_logical.get(logical).copied()
161    }
162
163    pub fn connect(&mut self, from: NodeId, to: NodeId, reason: DependencyReason) -> Result<()> {
164        assert!(self.contains(from));
165        assert!(self.contains(to));
166        if from == to {
167            // The loader considers an object that is already mapped to satisfy
168            // a self-reference; it adds no useful edge to the closure.
169            return Ok(());
170        }
171
172        let known = self
173            .edges_from(from)
174            .any(|e| e.to == to && e.reason == reason);
175        if known {
176            return Ok(());
177        }
178        if self.edges.len() >= EDGES_MAX {
179            return Err(Error::LimitExceeded {
180                resource: "runtime dependency graph",
181                limit: EDGES_MAX,
182            });
183        }
184        let index = self.edges.len();
185        self.edges.push(Edge { from, to, reason });
186        self.outgoing.entry(from).or_default().push(index);
187        // Only the first dependent is recorded; later ones never displace it.
188        self.first_incoming.entry(to).or_insert(index);
189        Ok(())
190    }
191
192    pub fn contains(&self, id: NodeId) -> bool {
193        (id as usize) < self.nodes.len()
194    }
195
196    pub fn node(&self, id: NodeId) -> &Node {
197        assert!(self.contains(id));
198        &self.nodes[id as usize]
199    }
200
201    pub fn root_node(&self) -> &Node {
202        let root = self.node(self.root);
203        assert_eq!(root.kind, NodeKind::Executable);
204        root
205    }
206
207    /// Edges leaving a node, in insertion order.
208    pub fn edges_from(&self, id: NodeId) -> impl Iterator<Item = &Edge> {
209        self.outgoing
210            .get(&id)
211            .map(Vec::as_slice)
212            .unwrap_or_default()
213            .iter()
214            .map(|&index| &self.edges[index])
215    }
216
217    /// Direct dependencies of a node, in insertion order.
218    pub fn dependencies(&self, id: NodeId) -> Vec<(&Edge, &Node)> {
219        assert!(self.contains(id));
220        self.edges_from(id).map(|e| (e, self.node(e.to))).collect()
221    }
222
223    /// First object that pulled in `id`, used for diagnostics and manifests.
224    pub fn first_dependent(&self, id: NodeId) -> Option<(&Edge, &Node)> {
225        assert!(self.contains(id));
226        let edge = &self.edges[*self.first_incoming.get(&id)?];
227        Some((edge, self.node(edge.from)))
228    }
229
230    /// Nodes paired with their ids, in insertion order. The only way to obtain
231    /// a [`NodeId`] for a node short of looking it up by its logical path.
232    pub fn iter(&self) -> impl Iterator<Item = (NodeId, &Node)> {
233        self.nodes.iter().enumerate().map(|(index, node)| {
234            let id = NodeId::try_from(index).expect("node count is bounded by NODES_MAX");
235            (id, node)
236        })
237    }
238
239    pub fn shared_objects(&self) -> impl Iterator<Item = &Node> {
240        self.nodes
241            .iter()
242            .filter(|n| n.kind == NodeKind::SharedObject)
243    }
244
245    pub fn total_size(&self) -> u64 {
246        self.nodes.iter().map(|n| n.size).sum()
247    }
248
249    /// Nodes reachable from the executable through its own ELF dependencies.
250    ///
251    /// Objects that only runtime policy asked for (NSS modules and their own
252    /// dependencies) stay out of this set. They are in the image, but the
253    /// application never declared them.
254    pub fn application_closure(&self) -> HashSet<NodeId> {
255        assert!(self.contains(self.root));
256
257        let mut reached = HashSet::from([self.root]);
258        let mut queue = vec![self.root];
259        // A node is queued only when it is first reached, so the walk is
260        // bounded by the size of the graph.
261        while let Some(id) = queue.pop() {
262            for edge in self.edges_from(id) {
263                if matches!(edge.reason, DependencyReason::RuntimePolicy { .. }) {
264                    continue;
265                }
266                if reached.insert(edge.to) {
267                    queue.push(edge.to);
268                }
269            }
270        }
271        reached
272    }
273}
274
275#[cfg(test)]
276mod tests {
277    use super::*;
278    use crate::{
279        elf::{ElfClass, Endianness, Machine},
280        hash::sha256_bytes,
281    };
282
283    fn node(path: PathBuf) -> Node {
284        Node {
285            source: path.clone(),
286            logical: path.clone(),
287            destination: path,
288            kind: NodeKind::SharedObject,
289            soname: None,
290            architecture: Architecture {
291                machine: Machine::X86_64,
292                class: ElfClass::Elf64,
293                endianness: Endianness::Little,
294            },
295            sha256: sha256_bytes(b"test"),
296            size: 0,
297            links: Vec::new(),
298            dlopen_references: Vec::new(),
299        }
300    }
301
302    #[test]
303    fn an_oversized_closure_is_an_error() {
304        let mut graph = DependencyGraph::new();
305        for index in 0..NODES_MAX {
306            graph
307                .insert(node(PathBuf::from(format!("/lib/{index}"))))
308                .unwrap();
309        }
310
311        let error = graph
312            .insert(node(PathBuf::from("/lib/overflow")))
313            .unwrap_err();
314        assert!(matches!(
315            &error,
316            Error::LimitExceeded {
317                resource: "runtime closure",
318                limit: NODES_MAX,
319            }
320        ));
321        assert_eq!(error.code(), "E1005");
322    }
323
324    #[test]
325    fn a_digest_is_sixty_four_lowercase_hex_digits() {
326        assert!(sha256_bytes(b"test").is_well_formed());
327        // `z` is a lowercase letter but not a hex digit.
328        assert!(!Digest("z".repeat(DIGEST_LEN_HEX)).is_well_formed());
329        assert!(!Digest("A".repeat(DIGEST_LEN_HEX)).is_well_formed());
330        assert!(!Digest("ab".to_string()).is_well_formed());
331    }
332
333    /// `edges` stays the record of what happened; the indices are only a way
334    /// to reach it without scanning, so both have to give the same answer.
335    #[test]
336    fn the_edge_indices_agree_with_the_edge_list() {
337        let mut graph = DependencyGraph::new();
338        let ids: Vec<NodeId> = (0..4)
339            .map(|index| {
340                graph
341                    .insert(node(PathBuf::from(format!("/lib/lib{index}.so"))))
342                    .unwrap()
343            })
344            .collect();
345
346        let needed = |name: &str| DependencyReason::Needed {
347            soname: name.to_string(),
348        };
349        graph.connect(ids[0], ids[1], needed("one")).unwrap();
350        graph.connect(ids[0], ids[2], needed("two")).unwrap();
351        graph.connect(ids[3], ids[1], needed("one")).unwrap();
352        // Same edge twice, and the same pair under a second reason.
353        graph.connect(ids[0], ids[1], needed("one")).unwrap();
354        graph
355            .connect(ids[0], ids[1], DependencyReason::Interpreter)
356            .unwrap();
357        assert_eq!(graph.edges.len(), 4, "only the repeat was dropped");
358
359        for (id, _) in graph.iter() {
360            let indexed: Vec<NodeId> = graph.edges_from(id).map(|e| e.to).collect();
361            let scanned: Vec<NodeId> = graph
362                .edges
363                .iter()
364                .filter(|e| e.from == id)
365                .map(|e| e.to)
366                .collect();
367            assert_eq!(indexed, scanned, "outgoing edges of {id}");
368
369            let indexed = graph
370                .first_dependent(id)
371                .map(|(_, parent)| parent.logical.clone());
372            let scanned = graph
373                .edges
374                .iter()
375                .find(|e| e.to == id)
376                .map(|e| graph.node(e.from).logical.clone());
377            assert_eq!(indexed, scanned, "first dependent of {id}");
378        }
379    }
380
381    #[test]
382    fn a_self_dependency_does_not_add_an_edge() {
383        let mut graph = DependencyGraph::new();
384        let id = graph.insert(node(PathBuf::from("/lib/self.so"))).unwrap();
385        graph
386            .connect(
387                id,
388                id,
389                DependencyReason::Needed {
390                    soname: "self.so".to_string(),
391                },
392            )
393            .unwrap();
394        assert!(graph.edges.is_empty());
395    }
396}
elfpak_core/graph.rs

elfpak_core/
graph.rs
