elfpak_core/resolver/

cache.rs

//! Direct `/etc/ld.so.cache` reading and writing.
//!
//! `ldconfig` is never invoked. Both the historical `ld.so-1.7.0` layout and the
//! current `glibc-ld.so.cache1.1` layout are understood on the way in, including
//! the common case where a new-format cache is appended after an old-format one.
//!
//! On the way out, [`build`] emits a `glibc-ld.so.cache1.1` image for the
//! bundle. Without one, a packaged application cannot find a library outside
//! the directories the loader searches by default: the rootfs carries no
//! `ldconfig`, and the build host's cache describes the host's filesystem.

use crate::elf::{Architecture, ElfClass, Endianness, Machine};
use std::{
    cmp::Ordering,
    collections::HashMap,
    path::{Path, PathBuf},
};

const OLD_MAGIC: &[u8] = b"ld.so-1.7.0";
const NEW_MAGIC: &[u8] = b"glibc-ld.so.cache";
const NEW_VERSION: &[u8] = b"1.1";

/// Header size of `struct cache_file` including alignment padding.
const OLD_HEADER_LEN: usize = 16;
const OLD_ENTRY_LEN: usize = 12;
/// Header size of `struct cache_file_new`.
const NEW_HEADER_LEN: usize = 48;
const NEW_ENTRY_LEN: usize = 24;

/// Upper bound on the entries taken from a cache image.
///
/// A distribution cache holds a few thousand libraries. `nlibs` comes out of
/// the file and is never trusted, so this bounds what is read.
const CACHE_ENTRIES_MAX: usize = 65_536;
/// A cache is a small index, not an arbitrary data container. This prevents a
/// hostile sysroot from making planning allocate or repeatedly scan huge data.
const CACHE_BYTES_MAX: u64 = 16 * 1024 * 1024;
/// Both ELF sonames and filesystem components are far shorter in practice;
/// this also bounds malformed unterminated-string scans.
const CACHE_STRING_LEN_MAX: usize = 4096;
/// A loader lookup should not turn one malicious soname into tens of thousands
/// of filesystem probes. Normal caches have only a handful of alternatives.
const CACHE_CANDIDATES_PER_SONAME_MAX: usize = 256;

#[derive(Debug, Clone, Default)]
pub struct LdCache {
    /// soname -> candidate absolute paths, in cache order.
    entries: HashMap<String, Vec<PathBuf>>,
    /// Same candidates with loader-selection metadata retained.
    records: HashMap<String, Vec<CacheRecord>>,
    /// Candidates kept, i.e. the total length of the lists above. Relative and
    /// duplicate entries are dropped on the way in and are not counted.
    len: usize,
}

/// One raw cache entry. The loader checks its ABI and hardware requirements
/// before considering the pathname, so preserving this metadata is essential
/// when planning from a foreign sysroot.
#[derive(Debug, Clone)]
struct CacheRecord {
    soname: String,
    path: PathBuf,
    flags: u32,
    osversion: u32,
    hwcap: u64,
}

impl LdCache {
    /// Parse a cache image. A malformed cache yields no entries instead of
    /// failing the build; the cache is a hint and the search paths remain.
    pub fn parse(bytes: &[u8]) -> LdCache {
        let mut cache = LdCache::default();
        if u64::try_from(bytes.len())
            .ok()
            .is_none_or(|len| len > CACHE_BYTES_MAX)
        {
            return cache;
        }
        let pairs = if starts_with(bytes, 0, NEW_MAGIC) {
            parse_new(bytes, 0)
        } else if starts_with(bytes, 0, OLD_MAGIC) {
            let nlibs = match read_u32(bytes, 12) {
                Some(n) => n as usize,
                None => return cache,
            };
            let new_offset = align8(
                nlibs
                    .saturating_mul(OLD_ENTRY_LEN)
                    .saturating_add(OLD_HEADER_LEN),
            );
            if starts_with(bytes, new_offset, NEW_MAGIC) {
                parse_new(bytes, new_offset)
            } else {
                parse_old(bytes, nlibs)
            }
        } else {
            Vec::new()
        };

        for record in pairs {
            // ldconfig only records absolute paths. A relative one would be
            // resolved against this process's working directory downstream.
            if !record.path.is_absolute() {
                continue;
            }
            let list = cache.entries.entry(record.soname.clone()).or_default();
            if list.len() < CACHE_CANDIDATES_PER_SONAME_MAX && !list.contains(&record.path) {
                list.push(record.path.clone());
                cache
                    .records
                    .entry(record.soname.clone())
                    .or_default()
                    .push(record);
                cache.len += 1;
            }
        }
        cache
    }

    pub fn load(path: &Path) -> Option<LdCache> {
        if std::fs::metadata(path).ok()?.len() > CACHE_BYTES_MAX {
            return None;
        }
        let bytes = std::fs::read(path).ok()?;
        let cache = LdCache::parse(&bytes);
        if cache.entries.is_empty() {
            None
        } else {
            Some(cache)
        }
    }

    pub fn lookup(&self, soname: &str) -> &[PathBuf] {
        self.entries.get(soname).map(Vec::as_slice).unwrap_or(&[])
    }

    /// Candidates usable by a portable bundle for `architecture`.
    ///
    /// Cache flags encode the ELF ABI. Entries requiring an OS version or CPU
    /// hwcap are intentionally skipped because a sysroot does not establish a
    /// deployment kernel or CPU baseline.
    pub fn lookup_compatible(&self, soname: &str, architecture: &Architecture) -> Vec<PathBuf> {
        let Some(expected_flags) =
            entry_flags(architecture).and_then(|flags| u32::try_from(flags).ok())
        else {
            return Vec::new();
        };
        self.records
            .get(soname)
            .into_iter()
            .flatten()
            .filter(|entry| {
                entry.flags == expected_flags && entry.osversion == 0 && entry.hwcap == 0
            })
            .map(|entry| entry.path.clone())
            .collect()
    }

    /// Candidates the cache holds, counting a soname once per distinct path.
    pub fn entry_count(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }
}

fn align8(value: usize) -> usize {
    value.saturating_add(7) & !7
}

/// `offset` comes out of the file by way of [`align8`], so the addition is
/// checked rather than assumed to fit.
fn starts_with(bytes: &[u8], offset: usize, magic: &[u8]) -> bool {
    let Some(end) = offset.checked_add(magic.len()) else {
        return false;
    };
    bytes.get(offset..end) == Some(magic)
}

fn read_u32(bytes: &[u8], offset: usize) -> Option<u32> {
    let slice = bytes.get(offset..offset.checked_add(4)?)?;
    Some(u32::from_le_bytes(slice.try_into().ok()?))
}

/// Strings are NUL terminated and addressed relative to `base`.
fn read_string(bytes: &[u8], base: usize, offset: u32) -> Option<String> {
    let start = base.checked_add(offset as usize)?;
    let rest = bytes.get(start..)?;
    let end = rest
        .iter()
        .take(CACHE_STRING_LEN_MAX + 1)
        .position(|&b| b == 0)?;
    if end > CACHE_STRING_LEN_MAX {
        return None;
    }
    std::str::from_utf8(&rest[..end]).ok().map(str::to_string)
}

/// How many entries `bytes` can actually hold from `base` on.
///
/// `nlibs` comes straight out of the file, so it is never trusted for sizing;
/// the size of the image is the only bound worth allocating against.
fn entry_capacity(bytes: &[u8], base: usize, header: usize, entry: usize) -> usize {
    bytes
        .len()
        .saturating_sub(base.saturating_add(header))
        .saturating_div(entry)
}

/// `struct cache_file`: a header followed by `nlibs` fixed-size entries, then
/// the string table.
///
/// Unlike the new format, whose offsets are relative to the start of the image,
/// these are relative to the string table itself — glibc reads them through
/// `cache_data = (const char *) &cache->libs[cache->nlibs]`. The declared
/// `nlibs` is what fixes that base, so it is used even where the entry loop
/// reads fewer entries than the header claims.
fn parse_old(bytes: &[u8], nlibs: usize) -> Vec<CacheRecord> {
    let capacity = entry_capacity(bytes, 0, OLD_HEADER_LEN, OLD_ENTRY_LEN);
    let count = nlibs.min(capacity).min(CACHE_ENTRIES_MAX);
    let Some(strings) = nlibs
        .checked_mul(OLD_ENTRY_LEN)
        .and_then(|entries| entries.checked_add(OLD_HEADER_LEN))
        .filter(|&base| base <= bytes.len())
    else {
        return Vec::new();
    };
    let mut out = Vec::with_capacity(count);
    for index in 0..count {
        let Some(offset) = index
            .checked_mul(OLD_ENTRY_LEN)
            .and_then(|at| at.checked_add(OLD_HEADER_LEN))
        else {
            break;
        };
        let (Some(flags), Some(key), Some(value)) = (
            read_u32(bytes, offset),
            read_u32(bytes, offset + 4),
            read_u32(bytes, offset + 8),
        ) else {
            break;
        };
        if let (Some(soname), Some(path)) = (
            read_string(bytes, strings, key),
            read_string(bytes, strings, value),
        ) {
            out.push(CacheRecord {
                soname,
                path: PathBuf::from(path),
                flags,
                osversion: 0,
                hwcap: 0,
            });
        }
    }
    out
}

fn parse_new(bytes: &[u8], base: usize) -> Vec<CacheRecord> {
    if !starts_with(bytes, base + NEW_MAGIC.len(), NEW_VERSION) {
        return Vec::new();
    }
    // The planner supports only little-endian target cache records. Refuse a
    // different byte order rather than decoding fields incorrectly.
    let Some(header_flags) = bytes.get(base + 28).copied() else {
        return Vec::new();
    };
    // Old writers left this field zero. Otherwise, the low two bits encode
    // byte order and must name little-endian for supported targets.
    if header_flags != 0 && header_flags & 0x03 != FLAGS_ENDIAN_LITTLE {
        return Vec::new();
    }
    let nlibs = match read_u32(bytes, base + 20) {
        Some(n) => n as usize,
        None => return Vec::new(),
    };
    let capacity = entry_capacity(bytes, base, NEW_HEADER_LEN, NEW_ENTRY_LEN);
    let count = nlibs.min(capacity).min(CACHE_ENTRIES_MAX);
    let mut out = Vec::with_capacity(count);
    for index in 0..count {
        let Some(offset) = base
            .checked_add(NEW_HEADER_LEN)
            .and_then(|start| index.checked_mul(NEW_ENTRY_LEN)?.checked_add(start))
        else {
            break;
        };
        let (Some(flags), Some(key), Some(value), Some(osversion)) = (
            read_u32(bytes, offset),
            read_u32(bytes, offset + 4),
            read_u32(bytes, offset + 8),
            read_u32(bytes, offset + 12),
        ) else {
            break;
        };
        let hwcap = bytes
            .get(offset + 16..offset + NEW_ENTRY_LEN)
            .and_then(|value| value.try_into().ok())
            .map(u64::from_le_bytes);
        if let (Some(soname), Some(path), Some(hwcap)) = (
            read_string(bytes, base, key),
            read_string(bytes, base, value),
            hwcap,
        ) {
            out.push(CacheRecord {
                soname,
                path: PathBuf::from(path),
                flags,
                osversion,
                hwcap,
            });
        }
    }
    out
}

/// One `soname -> path` mapping, as the loader inside the bundle will see it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CacheEntry {
    pub soname: String,
    /// Absolute path *inside the generated rootfs*.
    pub path: PathBuf,
}

/// glibc's `_DL_CACHE_DEFAULT_ID` for the target.
///
/// `_dl_cache_check_flags` compares the entry flags against this value exactly,
/// so an entry carrying anything else is silently ignored by the loader.
fn entry_flags(architecture: &Architecture) -> Option<i32> {
    const FLAG_ELF_LIBC6: i32 = 0x0003;
    const FLAG_X8664_LIB64: i32 = 0x0300;
    const FLAG_AARCH64_LIB64: i32 = 0x0a00;
    match (architecture.machine, architecture.class) {
        (Machine::X86_64, ElfClass::Elf64) => Some(FLAG_X8664_LIB64 | FLAG_ELF_LIBC6),
        (Machine::Aarch64, ElfClass::Elf64) => Some(FLAG_AARCH64_LIB64 | FLAG_ELF_LIBC6),
        _ => None,
    }
}

/// `cache_file_new_flags_endian_little`. The header records the byte order the
/// entries were written in, and glibc refuses a cache that disagrees with the
/// architecture it is running on.
const FLAGS_ENDIAN_LITTLE: u8 = 2;

/// The string table of a cache image, and the `(soname, path)` offset pair each
/// entry record points at.
struct StringTable {
    bytes: Vec<u8>,
    offsets: Vec<(u32, u32)>,
}

/// Encode the strings of `entries`. Offsets are absolute within the image,
/// hence `base`.
///
/// `None` for anything that cannot be encoded faithfully: a path that is not
/// UTF-8, a NUL that would truncate a string, or an image too large to address
/// with the `u32` offsets the format uses.
fn encode_strings(entries: &[&CacheEntry], base: usize) -> Option<StringTable> {
    let mut strings: Vec<u8> = Vec::new();
    let mut offsets: Vec<(u32, u32)> = Vec::with_capacity(entries.len());

    for entry in entries {
        // A NUL in either string would truncate it; such a name cannot come
        // from an ELF string table, but the file names could in principle.
        let path = entry.path.to_str()?;
        if entry.soname.contains('\0') || path.contains('\0') {
            return None;
        }
        let key = u32::try_from(base + strings.len()).ok()?;
        strings.extend_from_slice(entry.soname.as_bytes());
        strings.push(0);
        let value = u32::try_from(base + strings.len()).ok()?;
        strings.extend_from_slice(path.as_bytes());
        strings.push(0);
        offsets.push((key, value));
    }
    Some(StringTable {
        bytes: strings,
        offsets,
    })
}

/// Whether both of an entry's strings survive a round trip through the reader,
/// which bounds every string it accepts.
fn is_encodable(entry: &CacheEntry) -> bool {
    entry.soname.len() <= CACHE_STRING_LEN_MAX
        && entry
            .path
            .to_str()
            .is_some_and(|path| path.len() <= CACHE_STRING_LEN_MAX)
}

/// Whether any soname has more alternatives than the reader keeps.
///
/// Counted by exact name over the whole set, which is how the reader groups
/// them. Adjacency in the written order would not do: entries are sorted by
/// [`libcmp`], which compares digit runs numerically, so `libx.so.1` and
/// `libx.so.01` are `Equal` there and a run of one name can be split by the
/// other while the reader still sees them as one oversized group.
fn candidates_per_soname_exceeded(entries: &[&CacheEntry]) -> bool {
    let mut counts: HashMap<&str, usize> = HashMap::new();
    for entry in entries {
        let count = counts.entry(entry.soname.as_str()).or_insert(0);
        *count += 1;
        if *count > CACHE_CANDIDATES_PER_SONAME_MAX {
            return true;
        }
    }
    false
}

/// Build a `glibc-ld.so.cache1.1` image for `entries`.
///
/// Returns `None` for a target this function cannot encode faithfully, so the
/// caller can fall back to reporting the problem instead of writing a cache the
/// loader would reject.
pub fn build(architecture: &Architecture, entries: &[CacheEntry]) -> Option<Vec<u8>> {
    if entries.iter().any(|entry| !entry.path.is_absolute()) {
        return None;
    }
    // Sonames and paths come out of ELF files and the source filesystem, so
    // they can be longer than the reader — and therefore the loader's own
    // lookup — will accept. An image whose entries would be dropped on the way
    // back in is not a cache this bundle can use.
    if !entries.iter().all(is_encodable) {
        return None;
    }

    let flags = entry_flags(architecture)?;
    if architecture.endianness != Endianness::Little {
        // The header records one byte order and glibc refuses a cache that
        // disagrees with the architecture reading it.
        return None;
    }

    let mut entries: Vec<&CacheEntry> = entries.iter().collect();
    // glibc looks entries up with a binary search that walks *down* the table,
    // so it has to be sorted in descending `_dl_cache_libcmp` order. Ascending
    // order parses fine and then fails to resolve. The path breaks ties, purely
    // so that the same plan always produces the same bytes.
    entries.sort_by(|a, b| libcmp(&b.soname, &a.soname).then_with(|| a.path.cmp(&b.path)));
    entries.dedup_by(|a, b| a.soname == b.soname && a.path == b.path);
    assert!(
        entries
            .windows(2)
            .all(|pair| libcmp(&pair[0].soname, &pair[1].soname) != Ordering::Less),
        "the loader binary-searches downwards and needs descending order"
    );

    if entries.len() > CACHE_ENTRIES_MAX || candidates_per_soname_exceeded(&entries) {
        return None;
    }

    let base = NEW_HEADER_LEN + entries.len() * NEW_ENTRY_LEN;
    let StringTable {
        bytes: strings,
        offsets,
    } = encode_strings(&entries, base)?;
    let mut out = Vec::with_capacity(base + strings.len());
    out.extend_from_slice(NEW_MAGIC);
    out.extend_from_slice(NEW_VERSION);
    out.extend_from_slice(&u32::try_from(entries.len()).ok()?.to_le_bytes());
    out.extend_from_slice(&u32::try_from(strings.len()).ok()?.to_le_bytes());
    out.push(FLAGS_ENDIAN_LITTLE);
    out.extend_from_slice(&[0, 0, 0]); // `padding_unsed` (sic), reserved
    out.extend_from_slice(&0u32.to_le_bytes()); // extension_offset: none
    out.extend_from_slice(&[0u8; 12]); // `unused`, reserved
    assert_eq!(out.len(), NEW_HEADER_LEN);

    for (key, value) in offsets {
        out.extend_from_slice(&flags.to_le_bytes());
        out.extend_from_slice(&key.to_le_bytes());
        out.extend_from_slice(&value.to_le_bytes());
        out.extend_from_slice(&0u32.to_le_bytes()); // osversion, unused
        out.extend_from_slice(&0u64.to_le_bytes()); // hwcap: none required
    }
    assert_eq!(out.len(), base);
    out.extend_from_slice(&strings);
    assert_eq!(out.len(), base + strings.len());
    if u64::try_from(out.len()).is_ok_and(|len| len > CACHE_BYTES_MAX) {
        return None;
    }

    // Read the image back with the same reader the loader's format is modelled
    // on. A cache the bundle cannot use would be worse than none.
    let written = LdCache::parse(&out);
    assert_eq!(written.entry_count(), entries.len());
    assert!(
        entries
            .iter()
            .all(|entry| written.lookup(&entry.soname).contains(&entry.path))
    );
    Some(out)
}

/// glibc's `_dl_cache_libcmp`: like `strcmp`, except that runs of digits compare
/// numerically, so `libfoo.so.9` sorts before `libfoo.so.10`.
///
/// Bytes are compared unsigned. glibc compares them as `char`, whose signedness
/// is architecture-dependent, so the two can only disagree about non-ASCII
/// sonames.
fn libcmp(left: &str, right: &str) -> Ordering {
    let (p1, p2) = (left.as_bytes(), right.as_bytes());
    let (mut i, mut j) = (0usize, 0usize);
    let at = |s: &[u8], k: usize| s.get(k).copied().unwrap_or(0);

    while at(p1, i) != 0 {
        let (c1, c2) = (at(p1, i), at(p2, j));
        if c1.is_ascii_digit() {
            if !c2.is_ascii_digit() {
                return Ordering::Greater;
            }
            let mut v1 = 0u64;
            while at(p1, i).is_ascii_digit() {
                v1 = v1
                    .saturating_mul(10)
                    .saturating_add(u64::from(at(p1, i) - b'0'));
                i += 1;
            }
            let mut v2 = 0u64;
            while at(p2, j).is_ascii_digit() {
                v2 = v2
                    .saturating_mul(10)
                    .saturating_add(u64::from(at(p2, j) - b'0'));
                j += 1;
            }
            if v1 != v2 {
                return v1.cmp(&v2);
            }
        } else if c2.is_ascii_digit() {
            return Ordering::Less;
        } else if c1 != c2 {
            return c1.cmp(&c2);
        } else {
            i += 1;
            j += 1;
        }
    }
    at(p1, i).cmp(&at(p2, j))
}

#[cfg(test)]
mod tests {
    use super::*;

    fn little_endian_x86_64() -> Architecture {
        Architecture {
            machine: Machine::X86_64,
            class: ElfClass::Elf64,
            endianness: Endianness::Little,
        }
    }

    /// `libcmp` compares digit runs numerically, so two spellings of one
    /// version sort as equals while the reader still groups them by exact
    /// name. Counting adjacent runs would miss the group that overflows.
    #[test]
    fn candidate_counting_uses_the_readers_grouping_not_the_written_order() {
        let architecture = little_endian_x86_64();
        let mut entries: Vec<CacheEntry> = (0..=CACHE_CANDIDATES_PER_SONAME_MAX)
            .map(|index| CacheEntry {
                soname: "libx.so.1".to_string(),
                path: PathBuf::from(format!("/usr/lib/{index:04}/libx.so.1")),
            })
            .collect();
        // Sorts as an equal of `libx.so.1`, into the middle of the run above.
        entries.push(CacheEntry {
            soname: "libx.so.01".to_string(),
            path: PathBuf::from("/usr/lib/0128a/libx.so.01"),
        });
        assert!(build(&architecture, &entries).is_none());
    }

    /// Sonames come out of ELF string tables, so `build` is handed input it
    /// cannot always encode. It has to answer `None`, never abort.
    #[test]
    fn unencodable_entries_are_refused_rather_than_asserted() {
        let architecture = little_endian_x86_64();

        let long_soname = CacheEntry {
            soname: "a".repeat(CACHE_STRING_LEN_MAX + 1),
            path: PathBuf::from("/usr/lib/libx.so.1"),
        };
        assert!(build(&architecture, std::slice::from_ref(&long_soname)).is_none());

        let long_path = CacheEntry {
            soname: "libx.so.1".to_string(),
            path: PathBuf::from(format!("/usr/lib/{}", "b".repeat(CACHE_STRING_LEN_MAX))),
        };
        assert!(build(&architecture, &[long_path]).is_none());

        // More alternatives for one soname than the reader keeps.
        let crowded: Vec<CacheEntry> = (0..=CACHE_CANDIDATES_PER_SONAME_MAX)
            .map(|index| CacheEntry {
                soname: "libx.so.1".to_string(),
                path: PathBuf::from(format!("/usr/lib/{index}/libx.so.1")),
            })
            .collect();
        assert!(build(&architecture, &crowded).is_none());

        // One below the cap still builds, so the bound is the only thing
        // separating the two answers.
        assert!(build(&architecture, &crowded[..CACHE_CANDIDATES_PER_SONAME_MAX]).is_some());
    }

    fn offset(value: usize) -> u32 {
        u32::try_from(value).expect("fixture offsets fit in u32")
    }

    /// Build a `glibc-ld.so.cache1.1` image with the given (soname, path) pairs.
    fn new_format(entries: &[(&str, &str)]) -> Vec<u8> {
        let mut strings = Vec::new();
        let mut offsets = Vec::new();
        for (soname, path) in entries {
            let key = offset(strings.len());
            strings.extend_from_slice(soname.as_bytes());
            strings.push(0);
            let value = offset(strings.len());
            strings.extend_from_slice(path.as_bytes());
            strings.push(0);
            offsets.push((key, value));
        }
        let header_len = NEW_HEADER_LEN + entries.len() * NEW_ENTRY_LEN;

        let mut out = Vec::new();
        out.extend_from_slice(NEW_MAGIC);
        out.extend_from_slice(NEW_VERSION);
        out.extend_from_slice(&offset(entries.len()).to_le_bytes());
        out.extend_from_slice(&offset(strings.len()).to_le_bytes());
        out.push(FLAGS_ENDIAN_LITTLE);
        out.extend_from_slice(&[0, 0, 0]);
        out.extend_from_slice(&0u32.to_le_bytes());
        out.extend_from_slice(&[0u8; 12]);
        assert_eq!(out.len(), NEW_HEADER_LEN);

        for (key, value) in &offsets {
            out.extend_from_slice(&0x0300_0003u32.to_le_bytes());
            out.extend_from_slice(&(key + offset(header_len)).to_le_bytes());
            out.extend_from_slice(&(value + offset(header_len)).to_le_bytes());
            out.extend_from_slice(&0u32.to_le_bytes());
            out.extend_from_slice(&0u64.to_le_bytes());
        }
        out.extend_from_slice(&strings);
        out
    }

    #[test]
    fn parses_the_new_format() {
        let bytes = new_format(&[
            ("libc.so.6", "/lib/x86_64-linux-gnu/libc.so.6"),
            ("libm.so.6", "/lib/x86_64-linux-gnu/libm.so.6"),
        ]);
        let cache = LdCache::parse(&bytes);
        assert_eq!(cache.entry_count(), 2);
        assert_eq!(
            cache.lookup("libc.so.6"),
            [PathBuf::from("/lib/x86_64-linux-gnu/libc.so.6")]
        );
        assert!(cache.lookup("libnope.so.1").is_empty());
    }

    /// glibc reads an old-format cache's strings through
    /// `&cache->libs[cache->nlibs]`, so its offsets are relative to the string
    /// table, not to the start of the image like the new format's.
    #[test]
    fn old_format_string_offsets_are_relative_to_the_string_table() {
        let entries = [
            ("libz.so.1", "/usr/lib/libz.so.1"),
            ("libc.so.6", "/lib/libc.so.6"),
        ];
        let nlibs = entries.len();
        let mut strings: Vec<u8> = Vec::new();
        let mut offsets = Vec::new();
        for (soname, path) in entries {
            let key = offset(strings.len());
            strings.extend_from_slice(soname.as_bytes());
            strings.push(0);
            let value = offset(strings.len());
            strings.extend_from_slice(path.as_bytes());
            strings.push(0);
            offsets.push((key, value));
        }

        let mut bytes = Vec::new();
        bytes.extend_from_slice(OLD_MAGIC);
        bytes.push(0); // padding to the u32 boundary
        bytes.extend_from_slice(&offset(nlibs).to_le_bytes());
        for (key, value) in &offsets {
            bytes.extend_from_slice(&0u32.to_le_bytes()); // flags
            bytes.extend_from_slice(&key.to_le_bytes());
            bytes.extend_from_slice(&value.to_le_bytes());
        }
        assert_eq!(bytes.len(), OLD_HEADER_LEN + nlibs * OLD_ENTRY_LEN);
        bytes.extend_from_slice(&strings);

        let cache = LdCache::parse(&bytes);
        assert_eq!(
            cache.lookup("libz.so.1"),
            [PathBuf::from("/usr/lib/libz.so.1")]
        );
        assert_eq!(cache.lookup("libc.so.6"), [PathBuf::from("/lib/libc.so.6")]);
    }

    #[test]
    fn parses_an_old_format_header_with_an_appended_new_cache() {
        let new = new_format(&[("libz.so.1", "/usr/lib/libz.so.1")]);
        let nlibs = 1usize;
        let mut bytes = Vec::new();
        bytes.extend_from_slice(OLD_MAGIC);
        bytes.push(0); // padding to the u32 boundary
        bytes.extend_from_slice(&offset(nlibs).to_le_bytes());
        // One old entry pointing at strings we never read.
        bytes.extend_from_slice(&[0u8; OLD_ENTRY_LEN]);
        while bytes.len() < align8(OLD_HEADER_LEN + nlibs * OLD_ENTRY_LEN) {
            bytes.push(0);
        }
        bytes.extend_from_slice(&new);

        let cache = LdCache::parse(&bytes);
        assert_eq!(
            cache.lookup("libz.so.1"),
            [PathBuf::from("/usr/lib/libz.so.1")]
        );
    }

    fn x86_64() -> Architecture {
        Architecture {
            machine: Machine::X86_64,
            class: ElfClass::Elf64,
            endianness: Endianness::Little,
        }
    }

    fn entry(soname: &str, path: &str) -> CacheEntry {
        CacheEntry {
            soname: soname.to_string(),
            path: PathBuf::from(path),
        }
    }

    /// Read a generated image back the way glibc does: header fields at their
    /// fixed offsets, entries in file order.
    fn header(bytes: &[u8]) -> (u32, u32, u8, u32) {
        (
            read_u32(bytes, 20).unwrap(),
            read_u32(bytes, 24).unwrap(),
            bytes[28],
            read_u32(bytes, 32).unwrap(),
        )
    }

    fn keys_in_file_order(bytes: &[u8]) -> Vec<String> {
        let nlibs = read_u32(bytes, 20).unwrap() as usize;
        (0..nlibs)
            .map(|index| {
                let offset = NEW_HEADER_LEN + index * NEW_ENTRY_LEN;
                read_string(bytes, 0, read_u32(bytes, offset + 4).unwrap()).unwrap()
            })
            .collect()
    }

    #[test]
    fn a_generated_cache_round_trips_through_the_parser() {
        let bytes = build(
            &x86_64(),
            &[
                entry("libcached.so.1", "/opt/cached/libcached.so.1"),
                entry("libc.so.6", "/usr/lib/x86_64-linux-gnu/libc.so.6"),
            ],
        )
        .unwrap();

        let (nlibs, len_strings, flags, extension_offset) = header(&bytes);
        assert_eq!(nlibs, 2);
        assert_eq!(flags, FLAGS_ENDIAN_LITTLE, "glibc checks the byte order");
        assert_eq!(extension_offset, 0, "no extension section is written");
        assert_eq!(
            bytes.len(),
            NEW_HEADER_LEN + 2 * NEW_ENTRY_LEN + len_strings as usize
        );

        let cache = LdCache::parse(&bytes);
        assert_eq!(cache.entry_count(), 2);
        assert_eq!(
            cache.lookup("libcached.so.1"),
            [PathBuf::from("/opt/cached/libcached.so.1")]
        );
        assert!(cache.lookup("libnope.so.1").is_empty());
    }

    /// The loader binary-searches downwards, so the table has to descend.
    #[test]
    fn entries_are_written_in_descending_libcmp_order() {
        let bytes = build(
            &x86_64(),
            &[
                entry("libaaa.so.1", "/a"),
                entry("libzzz.so.1", "/z"),
                entry("libmmm.so.9", "/m9"),
                entry("libmmm.so.10", "/m10"),
            ],
        )
        .unwrap();
        assert_eq!(
            keys_in_file_order(&bytes),
            [
                "libzzz.so.1",
                // 10 is numerically greater than 9, which plain strcmp gets wrong.
                "libmmm.so.10",
                "libmmm.so.9",
                "libaaa.so.1",
            ]
        );
    }

    #[test]
    fn digit_runs_compare_numerically() {
        assert_eq!(libcmp("libfoo.so.9", "libfoo.so.10"), Ordering::Less);
        assert_eq!(libcmp("libfoo.so.10", "libfoo.so.9"), Ordering::Greater);
        assert_eq!(libcmp("libfoo.so.1", "libfoo.so.1"), Ordering::Equal);
        // A prefix is smaller than what extends it.
        assert_eq!(libcmp("libfoo.so", "libfoo.so.1"), Ordering::Less);
        // Digits sort after anything that is not a digit, as in glibc.
        assert_eq!(libcmp("lib1", "liba"), Ordering::Greater);
        assert_eq!(libcmp("liba", "lib1"), Ordering::Less);
        // Absurd digit runs saturate rather than overflow.
        let huge = format!("lib{}", "9".repeat(40));
        assert_eq!(libcmp(&huge, &huge), Ordering::Equal);
    }

    #[test]
    fn identical_entries_collapse_and_output_is_stable() {
        let entries = [
            entry("libc.so.6", "/lib/libc.so.6"),
            entry("libc.so.6", "/lib/libc.so.6"),
            entry("libc.so.6", "/other/libc.so.6"),
        ];
        let bytes = build(&x86_64(), &entries).unwrap();
        assert_eq!(read_u32(&bytes, 20).unwrap(), 2, "duplicates collapse");

        let mut shuffled = entries.to_vec();
        shuffled.reverse();
        assert_eq!(
            build(&x86_64(), &shuffled).unwrap(),
            bytes,
            "input order must not change the image"
        );
    }

    #[test]
    fn an_architecture_without_a_known_cache_id_is_refused() {
        let unsupported = Architecture {
            machine: Machine::RiscV64,
            ..x86_64()
        };
        assert!(build(&unsupported, &[entry("libc.so.6", "/lib/libc.so.6")]).is_none());
        let big_endian = Architecture {
            endianness: Endianness::Big,
            ..x86_64()
        };
        assert!(build(&big_endian, &[entry("libc.so.6", "/lib/libc.so.6")]).is_none());
        // An empty cache is still a valid cache.
        assert!(build(&x86_64(), &[]).is_some());
    }

    #[test]
    fn dropped_entries_are_not_counted() {
        // A relative path is not something ldconfig writes, and resolving one
        // would depend on this process's working directory, so it is dropped.
        let bytes = new_format(&[
            ("libc.so.6", "/lib/libc.so.6"),
            ("librel.so.1", "relative/librel.so.1"),
            ("libc.so.6", "/lib/libc.so.6"),
        ]);
        let cache = LdCache::parse(&bytes);
        assert!(cache.lookup("librel.so.1").is_empty());
        assert_eq!(
            cache.entry_count(),
            1,
            "only what the cache kept is counted"
        );
    }

    #[test]
    fn candidates_per_soname_are_bounded_in_cache_order() {
        let owned: Vec<(String, String)> = (0..=CACHE_CANDIDATES_PER_SONAME_MAX)
            .map(|index| ("libmany.so".to_string(), format!("/lib/libmany-{index}.so")))
            .collect();
        let entries: Vec<(&str, &str)> = owned
            .iter()
            .map(|(soname, path)| (soname.as_str(), path.as_str()))
            .collect();

        let cache = LdCache::parse(&new_format(&entries));
        let found = cache.lookup("libmany.so");
        assert_eq!(found.len(), CACHE_CANDIDATES_PER_SONAME_MAX);
        assert_eq!(found[0], Path::new("/lib/libmany-0.so"));
        assert_eq!(
            found.last(),
            Some(&PathBuf::from(format!(
                "/lib/libmany-{}.so",
                CACHE_CANDIDATES_PER_SONAME_MAX - 1
            )))
        );
    }

    #[test]
    fn compatible_lookup_rejects_foreign_abi_and_cpu_specific_entries() {
        let mut bytes = new_format(&[("libpick.so", "/lib/libpick.so")]);
        // First entry begins straight after the new-format header.
        bytes[NEW_HEADER_LEN..NEW_HEADER_LEN + 4].copy_from_slice(&0x0000_0a03u32.to_le_bytes()); // aarch64 libc6
        let cache = LdCache::parse(&bytes);
        let x86 = Architecture {
            machine: Machine::X86_64,
            class: ElfClass::Elf64,
            endianness: Endianness::Little,
        };
        assert!(cache.lookup_compatible("libpick.so", &x86).is_empty());

        bytes[NEW_HEADER_LEN..NEW_HEADER_LEN + 4].copy_from_slice(&0x0000_0303u32.to_le_bytes());
        bytes[NEW_HEADER_LEN + 16..NEW_HEADER_LEN + 24].copy_from_slice(&1u64.to_le_bytes());
        let cache = LdCache::parse(&bytes);
        assert!(cache.lookup_compatible("libpick.so", &x86).is_empty());
    }

    #[test]
    fn garbage_degrades_to_an_empty_cache() {
        assert!(LdCache::parse(b"not a cache at all").is_empty());
        assert!(LdCache::parse(&[]).is_empty());
    }

    #[test]
    fn an_absurd_entry_count_allocates_nothing() {
        assert_eq!(
            entry_capacity(&[0u8; 48], 0, NEW_HEADER_LEN, NEW_ENTRY_LEN),
            0
        );
        assert_eq!(
            entry_capacity(&[0u8; 48 + 24], 0, NEW_HEADER_LEN, NEW_ENTRY_LEN),
            1
        );
        assert_eq!(entry_capacity(&[], 4096, NEW_HEADER_LEN, NEW_ENTRY_LEN), 0);

        let mut bytes = new_format(&[("libc.so.6", "/lib/libc.so.6")]);
        bytes[20..24].copy_from_slice(&u32::MAX.to_le_bytes());
        let cache = LdCache::parse(&bytes);
        assert_eq!(cache.lookup("libc.so.6"), [PathBuf::from("/lib/libc.so.6")]);
        assert_eq!(
            cache.entry_count(),
            1,
            "parsing stops at the end of the file"
        );
    }

    #[test]
    fn truncated_entries_do_not_panic() {
        let mut bytes = new_format(&[("libc.so.6", "/lib/libc.so.6")]);
        bytes.truncate(NEW_HEADER_LEN + 4);
        assert!(LdCache::parse(&bytes).is_empty());
    }
}