elfpak-core 0.5.2

//! The dynamic linker resolver.
//!
//! This models the glibc loader's search algorithm rather than looking for
//! matching filenames. The target binary is never executed and `ldd` is never
//! called.

pub mod cache;
pub mod search;
pub mod tokens;

use crate::{
    elf::{Architecture, ElfMetadata, ObjectType},
    error::{Error, Result},
    graph::{DependencyGraph, DependencyReason, Node, NodeId, NodeKind},
    hash::DigestCache,
    paths::{logical_parent, normalize_absolute},
    source::{ElfCache, EntryKind, Resolved, SourceRoot},
};
pub use cache::LdCache;
use std::path::{Path, PathBuf};
pub use tokens::TokenContext;

/// A single `DT_NEEDED` lookup, with all loader state it depends on.
#[derive(Debug, Clone)]
pub struct LibraryRequest {
    pub soname: String,
    /// Logical path of the object that needs the library.
    pub requester: PathBuf,
    /// Expanded `DT_RPATH` lists of the requester and its loaders, nearest
    /// first. Entries are expanded when their owning object is visited: an
    /// inherited `$ORIGIN` refers to that owner, not the current requester.
    pub rpath_chain: Vec<Vec<PathBuf>>,
    /// `DT_RUNPATH` of the requester (never inherited).
    pub runpath: Vec<String>,
    pub nodeflib: bool,
    pub architecture: Architecture,
}

#[derive(Debug, Clone)]
pub struct ResolvedLibrary {
    pub resolved: Resolved,
    pub metadata: ElfMetadata,
}

/// Where a lookup succeeded. Only some of these survive into the bundle:
/// `--library-path` is a hint to `elfpak` and the packaged application never
/// sees it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SearchOrigin {
    /// `DT_RPATH`/`DT_RUNPATH` of the requesting object, or an absolute soname.
    ObjectPath,
    /// `--library-path`, the `LD_LIBRARY_PATH` equivalent.
    LibraryPath,
    /// `/etc/ld.so.cache`.
    Cache,
    /// A directory the loader searches without being told to.
    DefaultDirectory,
    /// A directory that only `/etc/ld.so.conf` named.
    ConfiguredDirectory,
}

/// A library the loader inside the bundle would not find on its own.
///
/// `elfpak` never runs `ldconfig`, so a bundle carries no `ld.so.cache`; a
/// library that was only reachable through the build host's cache, its
/// `ld.so.conf` or `--library-path` keeps its original path but nothing points
/// the loader at it any more.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolutionNote {
    pub soname: String,
    pub directory: PathBuf,
    pub origin: SearchOrigin,
}

impl SearchOrigin {
    pub fn as_str(&self) -> &'static str {
        match self {
            SearchOrigin::ObjectPath => "DT_RPATH/DT_RUNPATH",
            SearchOrigin::LibraryPath => "--library-path",
            SearchOrigin::Cache => "/etc/ld.so.cache",
            SearchOrigin::DefaultDirectory => "a default directory",
            SearchOrigin::ConfiguredDirectory => "/etc/ld.so.conf",
        }
    }

    /// Whether the packaged application can still find a library that was
    /// located this way.
    fn survives_packaging(&self) -> bool {
        matches!(
            self,
            SearchOrigin::ObjectPath | SearchOrigin::DefaultDirectory
        )
    }
}

/// Loader-specific resolution, kept behind a trait so the implementation can be
/// replaced (or wrapped for tracing) without touching the planner.
pub trait DynamicLinkerResolver {
    fn resolve(&mut self, request: &LibraryRequest) -> Result<ResolvedLibrary>;
}

/// Upper bound on the directories one lookup may probe.
///
/// A request consults the object's own search paths, `--library-path`, the
/// cache and the default directories; hundreds would mean a pathological
/// `DT_RPATH`, and an unbounded list would mean an unbounded lookup.
pub(crate) const SEARCH_DIRECTORIES_MAX: usize = 256;

#[derive(Debug)]
pub struct Resolver {
    root: SourceRoot,
    /// Explicit search paths, equivalent to `LD_LIBRARY_PATH`.
    library_paths: Vec<PathBuf>,
    /// Paths configured through `/etc/ld.so.conf`.
    conf_paths: Vec<PathBuf>,
    cache: Option<LdCache>,
    elf: ElfCache,
    digests: DigestCache,
    notes: Vec<ResolutionNote>,
}

impl Resolver {
    pub fn new(root: SourceRoot) -> Resolver {
        let cache = root
            .probe(Path::new("/etc/ld.so.cache"))
            .ok()
            .flatten()
            .filter(|r| r.kind == EntryKind::File)
            .and_then(|r| LdCache::load(&r.host));
        let conf_paths = search::parse_ld_so_conf(&root);
        Resolver {
            root,
            library_paths: Vec::new(),
            conf_paths,
            cache,
            elf: ElfCache::new(),
            digests: DigestCache::new(),
            notes: Vec::new(),
        }
    }

    pub fn with_library_paths(mut self, paths: Vec<PathBuf>) -> Resolver {
        self.library_paths = paths.iter().map(|p| normalize_absolute(p)).collect();
        self
    }

    pub fn root(&self) -> &SourceRoot {
        &self.root
    }

    pub fn ld_cache(&self) -> Option<&LdCache> {
        self.cache.as_ref()
    }

    /// Libraries that resolved through something the bundle does not reproduce.
    pub fn notes(&self) -> &[ResolutionNote] {
        &self.notes
    }

    fn note(&mut self, request: &LibraryRequest, directory: &Path, origin: SearchOrigin) {
        assert!(directory.is_absolute());

        if origin.survives_packaging() {
            return;
        }
        // How a library was found stops mattering once it sits somewhere the
        // packaged loader searches on its own.
        //
        // `search::default_library_paths` is a union of distro conventions,
        // which is right for *finding* a candidate but only approximates any
        // one loader's built-in list: glibc fixes that list when it is built,
        // and nothing in a source filesystem states it. A sysroot that places a
        // loader somewhere other than its own `slibdir` — assembled by hand
        // rather than by a package manager — can therefore be exempted here for
        // a directory its loader will not actually search. Reading the list out
        // of the loader binary is the only way to close that gap, and it cannot
        // be done portably; `--ld-so-cache=true` is the answer meanwhile.
        let is_default = search::default_library_paths(&request.architecture)
            .iter()
            .any(|default| default == directory);
        if is_default {
            return;
        }
        let note = ResolutionNote {
            soname: request.soname.clone(),
            directory: directory.to_path_buf(),
            origin,
        };
        if !self.notes.contains(&note) {
            self.notes.push(note);
        }
    }

    /// Map a host path to its logical path inside the source root.
    pub fn logical_of_host(&self, host: &Path) -> PathBuf {
        let host = std::path::absolute(host).unwrap_or_else(|_| host.to_path_buf());
        let root = self.root.path();
        let root = root.canonicalize().unwrap_or_else(|_| root.to_path_buf());
        let host = host.canonicalize().unwrap_or(host);
        match host.strip_prefix(&root) {
            Ok(rest) => normalize_absolute(&Path::new("/").join(rest)),
            Err(_) => normalize_absolute(&host),
        }
    }

    /// Build the full runtime closure of an executable.
    ///
    /// `binary` is a host path; `install` is where the executable will live in
    /// the generated rootfs. Every other object keeps its original location.
    pub fn closure(&mut self, binary: &Path, install: &Path) -> Result<DependencyGraph> {
        let metadata = ElfMetadata::parse_file(binary)?;
        if !metadata.architecture.machine.is_supported_target() {
            return Err(Error::UnsupportedArchitecture {
                path: binary.to_path_buf(),
                architecture: metadata.architecture.to_string(),
                machine: metadata.e_machine,
            });
        }
        let architecture = metadata.architecture;
        let logical = self.logical_of_host(binary);
        let mut graph = DependencyGraph::new();
        graph.declared_interpreter = metadata.interpreter.as_deref().map(normalize_absolute);
        graph.executable_search_paths = metadata
            .rpath
            .iter()
            .chain(metadata.runpath.iter())
            .cloned()
            .collect();

        let (digest, size) = self.digests.get(binary)?;
        let root_id = graph.insert(Node {
            source: binary.to_path_buf(),
            logical: logical.clone(),
            destination: normalize_absolute(install),
            kind: NodeKind::Executable,
            soname: metadata.soname.clone(),
            architecture,
            sha256: digest,
            size,
            links: Vec::new(),
            dlopen_references: metadata.dlopen_references.clone(),
        })?;
        graph.root = root_id;

        if metadata.interpreter.is_some() {
            self.attach_interpreter(&mut graph, &metadata, root_id)?;
        }

        self.walk_needed(&mut graph, root_id, metadata, Vec::new())?;

        Ok(graph)
    }

    /// `PT_INTERP`: the loader is a hard runtime dependency of the image, and
    /// the one dependency the kernel resolves rather than the loader.
    fn attach_interpreter(
        &mut self,
        graph: &mut DependencyGraph,
        metadata: &ElfMetadata,
        root_id: NodeId,
    ) -> Result<()> {
        let interp = metadata
            .interpreter
            .as_ref()
            .expect("only called for an object that declares PT_INTERP");
        let architecture = metadata.architecture;

        let resolved = self
            .root
            .resolve(interp)?
            .filter(|r| r.kind == EntryKind::File);
        let Some(resolved) = resolved else {
            return Err(Error::UnresolvedLibrary {
                soname: interp.to_string_lossy().into_owned(),
                required_by: graph.node(root_id).logical.clone(),
                searched: vec![self.root.host_path(interp)],
            });
        };

        let interp_meta = self.elf.require(&resolved.host)?;
        self.check_architecture(&interp_meta, &architecture, interp, &resolved)?;
        let id = self.insert_object(graph, &resolved, &interp_meta, NodeKind::Interpreter)?;
        graph.connect(root_id, id, DependencyReason::Interpreter)?;
        Ok(())
    }

    /// Add everything reachable from `start` through `DT_NEEDED`, depth first.
    ///
    /// `inherited` is the `DT_RPATH` chain of the objects that loaded `start`,
    /// nearest first; the loader consults it for every lookup further down the
    /// chain, which is the whole difference between `DT_RPATH` and `DT_RUNPATH`.
    fn walk_needed(
        &mut self,
        graph: &mut DependencyGraph,
        start: NodeId,
        metadata: ElfMetadata,
        inherited: Vec<Vec<PathBuf>>,
    ) -> Result<()> {
        assert!(graph.contains(start));

        let architecture = metadata.architecture;
        let mut queue = vec![(start, metadata, inherited)];
        // Only an object that was not already in the graph is queued, so the
        // walk visits each object once and is bounded by the graph's own limit.
        while let Some((id, meta, inherited)) = queue.pop() {
            assert_eq!(meta.architecture, architecture);

            let requester = graph.node(id).logical.clone();
            let mut chain: Vec<Vec<PathBuf>> = Vec::new();
            if !meta.runpath_is_authoritative() && !meta.rpath.is_empty() {
                let ctx = self.token_context(&requester, &architecture);
                chain.push(
                    meta.rpath
                        .iter()
                        .map(|entry| tokens::expand_search_path(entry, &ctx))
                        .collect(),
                );
            }
            chain.extend(inherited);
            // glibc guards the whole RPATH phase on the *requesting* object:
            // `if (loader->l_info[DT_RUNPATH] == NULL)` wraps the walk up the
            // loader chain, not just that object's own RPATH. An object with
            // DT_RUNPATH therefore sees no RPATH at all, its loaders' included,
            // while its children still inherit the chain unchanged.
            let search_chain = if meta.runpath_is_authoritative() {
                Vec::new()
            } else {
                chain.clone()
            };
            for soname in &meta.needed {
                let request = LibraryRequest {
                    soname: soname.clone(),
                    requester: requester.clone(),
                    rpath_chain: search_chain.clone(),
                    runpath: meta.runpath.clone(),
                    nodeflib: meta.nodeflib,
                    architecture,
                };
                let library = self.resolve(&request)?;
                let known = graph.find(&library.resolved.logical);
                let child = self.insert_object(
                    graph,
                    &library.resolved,
                    &library.metadata,
                    NodeKind::SharedObject,
                )?;
                graph.connect(
                    id,
                    child,
                    DependencyReason::Needed {
                        soname: soname.clone(),
                    },
                )?;
                if known.is_none() {
                    queue.push((child, library.metadata, chain.clone()));
                }
            }
        }
        Ok(())
    }

    /// Resolve a soname that is already known to be a library the policy wants,
    /// e.g. NSS modules pulled in by runtime policy rather than by `DT_NEEDED`.
    pub fn resolve_extra_library(
        &mut self,
        soname: &str,
        architecture: Architecture,
        requester: &Path,
    ) -> Result<Option<ResolvedLibrary>> {
        let request = LibraryRequest {
            soname: soname.to_string(),
            requester: requester.to_path_buf(),
            rpath_chain: Vec::new(),
            runpath: Vec::new(),
            nodeflib: false,
            architecture,
        };
        match self.resolve(&request) {
            Ok(library) => Ok(Some(library)),
            Err(Error::UnresolvedLibrary { .. }) => Ok(None),
            Err(e) => Err(e),
        }
    }

    /// Add an already-resolved object (and its own `DT_NEEDED` closure) to a graph.
    pub fn attach_library(
        &mut self,
        graph: &mut DependencyGraph,
        library: &ResolvedLibrary,
        from: NodeId,
        reason: DependencyReason,
    ) -> Result<NodeId> {
        let existing = graph.find(&library.resolved.logical);
        let id = self.insert_object(
            graph,
            &library.resolved,
            &library.metadata,
            NodeKind::SharedObject,
        )?;
        graph.connect(from, id, reason)?;
        if existing.is_none() {
            // A policy-loaded module is opened by `dlopen` from libc, not by the
            // application, so it inherits no RPATH from the loading chain.
            self.walk_needed(graph, id, library.metadata.clone(), Vec::new())?;
        }
        Ok(id)
    }

    fn insert_object(
        &mut self,
        graph: &mut DependencyGraph,
        resolved: &Resolved,
        metadata: &ElfMetadata,
        kind: NodeKind,
    ) -> Result<NodeId> {
        assert!(resolved.logical.is_absolute());
        assert_eq!(resolved.kind, EntryKind::File);

        let (digest, size) = self.digests.get(&resolved.host)?;
        graph.insert(Node {
            source: resolved.host.clone(),
            logical: resolved.logical.clone(),
            destination: resolved.logical.clone(),
            kind,
            soname: metadata.soname.clone(),
            architecture: metadata.architecture,
            sha256: digest,
            size,
            links: resolved.links.clone(),
            dlopen_references: metadata.dlopen_references.clone(),
        })
    }

    fn check_architecture(
        &self,
        metadata: &ElfMetadata,
        expected: &Architecture,
        soname: &Path,
        resolved: &Resolved,
    ) -> Result<()> {
        assert_eq!(metadata.path, resolved.host);

        if metadata.architecture.is_compatible_with(expected) {
            return Ok(());
        }
        Err(Error::IncompatibleArchitecture {
            soname: soname.to_string_lossy().into_owned(),
            expected: expected.to_string(),
            found: resolved.logical.clone(),
            found_architecture: metadata.architecture.to_string(),
        })
    }

    fn token_context(&self, requester: &Path, architecture: &Architecture) -> TokenContext {
        TokenContext {
            origin: logical_parent(requester),
            lib: architecture.lib_token().to_string(),
            platform: architecture.machine.platform_token().map(str::to_string),
        }
    }

    /// Candidate directories in glibc's documented order, each tagged with
    /// where it came from so the planner can tell what survives packaging.
    fn search_directories(&self, request: &LibraryRequest) -> Result<Vec<(PathBuf, SearchOrigin)>> {
        let ctx = self.token_context(&request.requester, &request.architecture);
        let mut dirs: Vec<(PathBuf, SearchOrigin)> = Vec::new();

        // 1. DT_RPATH of the object and, transitively, of its loaders.
        for level in &request.rpath_chain {
            for dir in level {
                push_directory(&mut dirs, dir.clone(), SearchOrigin::ObjectPath)?;
            }
        }
        // 2. LD_LIBRARY_PATH equivalent.
        for dir in &self.library_paths {
            push_directory(&mut dirs, dir.clone(), SearchOrigin::LibraryPath)?;
        }
        // 3. DT_RUNPATH of the requesting object only.
        for entry in &request.runpath {
            let dir = tokens::expand_search_path(entry, &ctx);
            push_directory(&mut dirs, dir, SearchOrigin::ObjectPath)?;
        }

        Ok(dirs)
    }

    fn default_directories(
        &self,
        architecture: &Architecture,
    ) -> Result<Vec<(PathBuf, SearchOrigin)>> {
        let mut dirs: Vec<(PathBuf, SearchOrigin)> = Vec::new();
        let configured = self
            .conf_paths
            .iter()
            .cloned()
            .map(|dir| (dir, SearchOrigin::ConfiguredDirectory));
        let builtin = search::default_library_paths(architecture)
            .into_iter()
            .map(|dir| (dir, SearchOrigin::DefaultDirectory));
        for (dir, origin) in configured.chain(builtin) {
            push_directory(&mut dirs, dir, origin)?;
        }

        Ok(dirs)
    }

    /// One directory of the search list.
    ///
    /// glibc would first look in this directory's `glibc-hwcaps` subdirectories.
    /// `elfpak` deliberately does not: which of them the loader accepts is a
    /// property of the CPU the image ends up on, not of the ELF target or the
    /// source filesystem, so selecting the best variant while planning can make
    /// an otherwise portable bundle fault on an older machine.
    fn try_directory(
        &mut self,
        dir: &Path,
        request: &LibraryRequest,
        searched: &mut Vec<PathBuf>,
        mismatch: &mut Option<(PathBuf, Architecture)>,
    ) -> Result<Option<ResolvedLibrary>> {
        self.try_path(&dir.join(&request.soname), request, searched, mismatch)
    }

    fn try_path(
        &mut self,
        logical: &Path,
        request: &LibraryRequest,
        searched: &mut Vec<PathBuf>,
        mismatch: &mut Option<(PathBuf, Architecture)>,
    ) -> Result<Option<ResolvedLibrary>> {
        let dir = logical_parent(logical);
        if !searched.contains(&dir) {
            searched.push(dir);
        }
        // A candidate, not a path anyone named: every failure to stat it just
        // means the loader would try the next directory.
        let Some(resolved) = self.root.probe(logical)? else {
            return Ok(None);
        };
        if resolved.kind != EntryKind::File {
            return Ok(None);
        }
        let Some(metadata) = self.elf.get(&resolved.host)? else {
            return Ok(None);
        };
        if metadata.object_type != ObjectType::SharedObject {
            return Ok(None);
        }
        if !metadata
            .architecture
            .is_compatible_with(&request.architecture)
        {
            if mismatch.is_none() {
                *mismatch = Some((resolved.logical.clone(), metadata.architecture));
            }
            return Ok(None);
        }
        Ok(Some(ResolvedLibrary { resolved, metadata }))
    }
}

/// Append a directory unless it is already listed. The loader probes each
/// directory once, in first-seen order, and so does this.
fn push_directory(
    dirs: &mut Vec<(PathBuf, SearchOrigin)>,
    dir: PathBuf,
    origin: SearchOrigin,
) -> Result<()> {
    assert!(dir.is_absolute());

    if dirs.iter().any(|(known, _)| known == &dir) {
        return Ok(());
    }
    if dirs.len() >= SEARCH_DIRECTORIES_MAX {
        return Err(Error::LimitExceeded {
            resource: "library search path",
            limit: SEARCH_DIRECTORIES_MAX,
        });
    }
    dirs.push((dir, origin));
    Ok(())
}

impl DynamicLinkerResolver for Resolver {
    /// One `DT_NEEDED` lookup: a soname is either a path or a search, and a
    /// search finds a compatible object, an incompatible one, or nothing.
    fn resolve(&mut self, request: &LibraryRequest) -> Result<ResolvedLibrary> {
        if request.soname.is_empty() {
            return Err(Error::Config {
                message: "library name cannot be empty".to_string(),
            });
        }
        if !request.requester.is_absolute() {
            return Err(Error::Config {
                message: format!(
                    "library requester `{}` is not an absolute logical path",
                    request.requester.display()
                ),
            });
        }

        let mut searched = Vec::new();
        let mut mismatch = None;

        // A soname containing a slash is a path, not a search request.
        let found = if request.soname.contains('/') {
            let ctx = self.token_context(&request.requester, &request.architecture);
            let expanded = tokens::expand(&request.soname, &ctx);
            let path = Path::new(&expanded);
            if !path.is_absolute() {
                return Err(Error::Config {
                    message: format!(
                        "relative DT_NEEDED path `{}` depends on the runtime working directory",
                        request.soname
                    ),
                });
            }
            let path = normalize_absolute(path);
            self.try_path(&path, request, &mut searched, &mut mismatch)?
        } else {
            self.search(request, &mut searched, &mut mismatch)?
        };

        if let Some(library) = found {
            return Ok(library);
        }

        // Nothing was found. An incompatible candidate is worth reporting over
        // the plain absence, because it names what went wrong.
        if let Some((found, architecture)) = mismatch {
            return Err(Error::IncompatibleArchitecture {
                soname: request.soname.clone(),
                expected: request.architecture.to_string(),
                found,
                found_architecture: architecture.to_string(),
            });
        }
        Err(Error::UnresolvedLibrary {
            soname: request.soname.clone(),
            required_by: request.requester.clone(),
            searched,
        })
    }
}

impl Resolver {
    /// glibc's search order for a bare soname: the object's own paths, then the
    /// cache, then the default directories.
    fn search(
        &mut self,
        request: &LibraryRequest,
        searched: &mut Vec<PathBuf>,
        mismatch: &mut Option<(PathBuf, Architecture)>,
    ) -> Result<Option<ResolvedLibrary>> {
        assert!(!request.soname.contains('/'));

        // 1-3. DT_RPATH, --library-path, DT_RUNPATH.
        for (dir, origin) in self.search_directories(request)? {
            if let Some(found) = self.try_directory(&dir, request, searched, mismatch)? {
                self.note(request, &dir, origin);
                return Ok(Some(found));
            }
        }

        // 4. /etc/ld.so.cache, which names absolute paths rather than directories.
        let cached: Vec<PathBuf> = self
            .cache
            .as_ref()
            .map(|c| c.lookup_compatible(&request.soname, &request.architecture))
            .unwrap_or_default();
        let default_dirs = if request.nodeflib {
            // `DF_1_NODEFLIB` suppresses glibc's built-in trusted directories,
            // not directories that `/etc/ld.so.conf` added to the cache.
            search::default_library_paths(&request.architecture)
        } else {
            Vec::new()
        };
        for candidate in cached {
            if default_dirs.iter().any(|dir| candidate.starts_with(dir)) {
                continue;
            }
            if let Some(found) = self.try_path(&candidate, request, searched, mismatch)? {
                self.note(request, &logical_parent(&candidate), SearchOrigin::Cache);
                return Ok(Some(found));
            }
        }

        // 5. Default directories, unless DF_1_NODEFLIB opted the object out.
        if request.nodeflib {
            return Ok(None);
        }
        for (dir, origin) in self.default_directories(&request.architecture)? {
            if let Some(found) = self.try_directory(&dir, request, searched, mismatch)? {
                self.note(request, &dir, origin);
                return Ok(Some(found));
            }
        }
        Ok(None)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::elf::{ElfClass, Endianness, Machine};

    #[test]
    fn an_oversized_search_path_is_an_error() {
        let temp = tempfile::tempdir().unwrap();
        let paths = (0..=SEARCH_DIRECTORIES_MAX)
            .map(|index| PathBuf::from(format!("/search/{index}")))
            .collect();
        let resolver = Resolver::new(SourceRoot::new(temp.path())).with_library_paths(paths);
        let request = LibraryRequest {
            soname: "libexample.so.1".to_string(),
            requester: PathBuf::from("/app/server"),
            rpath_chain: Vec::new(),
            runpath: Vec::new(),
            nodeflib: false,
            architecture: Architecture {
                machine: Machine::X86_64,
                class: ElfClass::Elf64,
                endianness: Endianness::Little,
            },
        };

        let error = resolver.search_directories(&request).unwrap_err();
        assert!(matches!(
            error,
            Error::LimitExceeded {
                resource: "library search path",
                limit: SEARCH_DIRECTORIES_MAX,
            }
        ));
    }
}