qld 0.1.0

//! The output symbol table (`.symtab`, `.strtab`).
//!
//! [`plan`] decides, before layout, which symbols are written and where
//! their names go, so both sizes are known. [`write_symtab`] and
//! [`write_strtab`] fill the tables after layout, in parallel.
//!
//! Local symbols of live sections come first, file by file, each file's
//! after a `STT_FILE` symbol (GNU ld adds one named after the input when
//! the input has none). Global symbols GNU ld hides itself follow as
//! locals (without visibility), after an unnamed `STT_FILE` symbol: the
//! linker's and linker scripts' hidden symbols, and in shared objects every
//! hidden symbol; other hidden symbols stay global. The other globals come
//! last, by symbol ID. Section symbols and assembler temporaries (`.L*`)
//! are dropped; `-x` drops every local and `-s` the whole table.

#![deny(clippy::arithmetic_side_effects)]

use rayon::prelude::*;

use crate::args::{DiscardMode, LinkOptions, StripMode};
use crate::elf::read::consts::{
    SHN_ABS, SHN_UNDEF, STB_GLOBAL, STB_LOCAL, STB_WEAK, STT_FILE, STT_NOTYPE, STT_OBJECT,
    STT_SECTION, STT_TLS, STV_DEFAULT, STV_HIDDEN, STV_INTERNAL,
};
use crate::elf::read::{ElfFormat, ElfKind, RawRecord, RawSymbol, SectionIndex};
use crate::ids::SymbolId;
use crate::symbols::{DefinitionKind, SymbolFlags};

use super::defined::{LinkerSymbols, is_hidden};
use super::dso::{REF_REGULAR, REF_REGULAR_STRONG};
use super::dynsym::shndx_of_address;
use super::export::PREEMPTIBLE;
use super::refs::{Def, Refs};
use super::values::Addresses;

/// Which symbols the output table holds.
#[derive(Debug, Default)]
pub struct SymtabPlan {
    /// Per file: local symbol indices kept.
    pub locals: Vec<Vec<u32>>,
    /// Per file: the name of the `STT_FILE` symbol written before its
    /// locals because the input has none (GNU ld's `elf_link_input_bfd`).
    file_names: Vec<Option<Vec<u8>>>,
    /// Whether an unnamed `STT_FILE` symbol precedes the hidden globals.
    hidden_file: bool,
    /// Globals written as locals (hidden visibility).
    pub hidden: Vec<SymbolId>,
    /// Globals.
    pub globals: Vec<SymbolId>,
    /// String table offset of each name of `hidden`.
    hidden_offsets: Vec<usize>,
    /// String table offset of each name of `globals`.
    global_offsets: Vec<usize>,
    /// First entry index of each file's locals (after the null symbol).
    local_base: Vec<usize>,
    /// String table offset where each file's local names start.
    local_names: Vec<usize>,
    /// Index of the first entry after file locals.
    hidden_base: usize,
    /// String table offset where hidden global names start.
    hidden_names: usize,
    /// Index of the first global entry.
    pub first_global: usize,
    /// String table offset where global names start.
    global_names: usize,
    /// Total number of entries, including the null symbol.
    pub count: usize,
    /// String table size.
    pub strtab_size: usize,
    /// Section symbols at the start of the table (`--emit-relocs`).
    pub section_symbols: usize,
    /// The ELF class and byte order entries are written in.
    pub kind: ElfKind,
}

fn keep_local(name: &[u8], raw: &RawSymbol, discard: DiscardMode) -> bool {
    if raw.kind() == STT_SECTION || name.is_empty() {
        return false;
    }
    match discard {
        DiscardMode::All => false,
        DiscardMode::None => true,
        DiscardMode::Default | DiscardMode::Locals => !name.starts_with(b".L"),
    }
}

fn global_visibility<F: crate::elf::read::ElfFormat>(
    refs: &Refs<'_, '_, F>,
    linker: &LinkerSymbols,
    id: SymbolId,
) -> u8 {
    let target = refs.global_target(id, true);
    if let Def::Linker(_) = target.def {
        return match linker.entries.iter().find(|(i, _)| *i == id) {
            Some((_, value)) if is_hidden(*value) => STV_HIDDEN,
            _ => STV_DEFAULT,
        };
    }
    target.raw.map_or(STV_DEFAULT, |raw| raw.visibility())
}

/// Whether an input has a `STT_FILE` symbol.
pub(crate) fn has_file_symbol<F: crate::elf::read::ElfFormat>(
    object: &super::object::ObjectInput<'_, F>,
) -> bool {
    let symbols = object.elf.symbols();
    (1..object.first_global).any(|index| {
        symbols
            .get_raw(index)
            .is_some_and(|raw| raw.kind() == STT_FILE)
    })
}

/// The name GNU ld gives the `STT_FILE` symbol it adds for an input without
/// one: the file name without directories (for an archive member, the
/// member's).
pub(crate) fn file_symbol_name<F: crate::elf::read::ElfFormat>(
    file: &super::inputs::ElfInput<'_, F>,
) -> Option<Vec<u8>> {
    let input = file.file?;
    let name: &[u8] = match input.member() {
        Some(member) => member.as_bytes(),
        None => input.path().as_os_str().as_encoded_bytes(),
    };
    let base = name.rsplit(|&b| b == b'/').next().unwrap_or(name);
    (!base.is_empty()).then(|| base.to_vec())
}

/// Which local symbols of `file` the relocations of its live sections
/// name, by symbol index.
fn referenced_locals<F: crate::elf::read::ElfFormat>(
    refs: &Refs<'_, '_, F>,
    file_index: usize,
    object: &super::object::ObjectInput<'_, F>,
) -> Vec<bool> {
    let mut referenced = vec![false; object.first_global];
    for (index, section) in object.sections.iter().enumerate() {
        let Ok(index) = u32::try_from(index) else {
            break;
        };
        if section.relocs == 0 || !refs.sections.is_live_in(file_index, index) {
            continue;
        }
        let Some(Ok(Some(relocations))) = object
            .section(section.relocs)
            .map(|r| object.elf.relocation_section(section.relocs, &r.header))
        else {
            continue;
        };
        let mut mark = |symbol: u32| {
            if let Some(slot) = referenced.get_mut(symbol as usize) {
                *slot = true;
            }
        };
        // One loop per kind: the decoding stays out of the inner loop.
        match relocations.relocations {
            crate::elf::read::Relocations::Rela(relas) => {
                for rel in relas.iter() {
                    mark(rel.symbol);
                }
            }
            crate::elf::read::Relocations::Rel(rels) => {
                for rel in rels.iter() {
                    mark(rel.symbol);
                }
            }
        }
    }
    referenced
}

/// Whether an import survives `--gc-sections`: live code refers to it, or
/// it needs a GOT, PLT or copy (from a relocation of live code).
fn live_import(flags: SymbolFlags) -> bool {
    flags.contains(super::scan::REF_LIVE)
        || flags.intersects(
            SymbolFlags::NEEDS_GOT
                | SymbolFlags::NEEDS_PLT
                | SymbolFlags::NEEDS_COPY_RELOC
                | SymbolFlags::NEEDS_DYNSYM,
        )
}

/// Plans the symbol table. Returns an empty plan for `-s`.
#[must_use]
pub fn plan<F: crate::elf::read::ElfFormat>(
    refs: &Refs<'_, '_, F>,
    linker: &LinkerSymbols,
    options: &LinkOptions,
    kind: ElfKind,
) -> SymtabPlan {
    if options.strip == StripMode::All {
        return SymtabPlan {
            kind,
            ..SymtabPlan::default()
        };
    }
    let discard = options.discard;
    let shared = options.kind == crate::args::OutputKind::Shared;
    let per_file: Vec<(Vec<u32>, usize, Option<Vec<u8>>)> = refs
        .files
        .par_iter()
        .enumerate()
        .map(|(file_index, file)| {
            let mut kept = Vec::new();
            let mut names = 0usize;
            let Some(object) = &file.object else {
                return (kept, names, None);
            };
            if refs
                .sections
                .base
                .get(file_index)
                .is_none_or(|&b| b == super::sections::NONE)
            {
                return (kept, names, None);
            }
            let symbols = object.elf.symbols();
            // With --emit-relocs, locals that relocations name stay symbols.
            let referenced = if options.emit_relocs {
                referenced_locals(refs, file_index, object)
            } else {
                Vec::new()
            };
            for index in 1..object.first_global {
                let Some(raw) = symbols.get_raw(index) else {
                    break;
                };
                let Ok(name) = symbols.name(index, &raw) else {
                    continue;
                };
                let wanted = keep_local(name, &raw, discard)
                    || (referenced.get(index).copied().unwrap_or(false)
                        && raw.kind() != STT_SECTION
                        && !name.is_empty());
                if !wanted {
                    continue;
                }
                let live = match symbols.section(index, &raw) {
                    Ok(SectionIndex::Section(section)) => {
                        refs.sections.is_present_in(file_index, section)
                    }
                    Ok(SectionIndex::Absolute) => true,
                    _ => false,
                };
                if !live && raw.kind() != STT_FILE {
                    continue;
                }
                kept.push(u32::try_from(index).unwrap_or(u32::MAX));
                names = names.saturating_add(name.len()).saturating_add(1);
            }
            let file_name = (!kept.is_empty() && !has_file_symbol(object))
                .then(|| file_symbol_name(file))
                .flatten();
            if let Some(name) = &file_name {
                names = names.saturating_add(name.len()).saturating_add(1);
            }
            (kept, names, file_name)
        })
        .collect();

    let symbols = refs.symbols;
    let mut selected: Vec<(SymbolId, bool, usize)> = (0..symbols.len())
        .into_par_iter()
        .filter_map(|index| {
            let id = SymbolId::new(index);
            let kind = symbols.definition_kind(id);
            let emit = match kind {
                DefinitionKind::Regular | DefinitionKind::Weak | DefinitionKind::Common => {
                    let target = refs.global_target(id, true);
                    match target.def {
                        Def::Section { file, section, .. } => {
                            refs.sections.is_present_in(file, section)
                        }
                        _ => true,
                    }
                }
                DefinitionKind::Shared => {
                    let flags = symbols.flags(id);
                    flags.contains(REF_REGULAR) && (!options.gc_sections || live_import(flags))
                }
                DefinitionKind::Undefined | DefinitionKind::Lazy => {
                    let flags = symbols.flags(id);
                    ((flags.contains(SymbolFlags::WEAK_REFERENCED)
                        && !flags.contains(SymbolFlags::REFERENCED))
                        || (flags.contains(REF_REGULAR) && flags.contains(PREEMPTIBLE)))
                        && (!options.gc_sections || live_import(flags))
                }
            };
            if !emit {
                return None;
            }
            let visibility = global_visibility(refs, linker, id);
            // GNU ld makes a hidden symbol local when it hides it itself:
            // the linker's and scripts' hidden symbols always, and every
            // hidden symbol of a shared object output. (In a PIE it also
            // localizes the hidden functions that PLT32 relocations call,
            // which qld does not track: they stay global and hidden.)
            // Symbols a version script's `local:` or `--exclude-libs` hides
            // are local too.
            let defined = kind != DefinitionKind::Undefined && kind != DefinitionKind::Lazy;
            let hidden = defined
                && ((matches!(visibility, STV_HIDDEN | STV_INTERNAL)
                    && (shared || matches!(refs.global_target(id, true).def, Def::Linker(_))))
                    || symbols.flags(id).contains(super::export::FORCED_LOCAL));
            if hidden && discard == DiscardMode::All {
                return None;
            }
            let len = global_name_len(refs, id).saturating_add(1);
            Some((id, hidden, len))
        })
        .collect();
    selected.sort_unstable_by_key(|(id, ..)| *id);

    let mut plan = SymtabPlan {
        kind,
        ..SymtabPlan::default()
    };
    let mut index = 1usize;
    let mut offset = 1usize;
    for (kept, names, file_name) in per_file {
        plan.local_base.push(index);
        plan.local_names.push(offset);
        index = index
            .saturating_add(kept.len())
            .saturating_add(usize::from(file_name.is_some()));
        offset = offset.saturating_add(names);
        plan.locals.push(kept);
        plan.file_names.push(file_name);
    }
    plan.hidden_base = index;
    plan.hidden_names = offset;
    plan.hidden_file = selected.iter().any(|&(_, hidden, _)| hidden);
    if plan.hidden_file {
        index = index.saturating_add(1);
    }
    for &(id, hidden, len) in &selected {
        if hidden {
            plan.hidden.push(id);
            plan.hidden_offsets.push(offset);
            index = index.saturating_add(1);
            offset = offset.saturating_add(len);
        }
    }
    plan.first_global = index;
    plan.global_names = offset;
    for &(id, hidden, len) in &selected {
        if !hidden {
            plan.globals.push(id);
            plan.global_offsets.push(offset);
            index = index.saturating_add(1);
            offset = offset.saturating_add(len);
        }
    }
    plan.count = index;
    plan.strtab_size = offset;
    plan
}

impl SymtabPlan {
    /// Puts `count` section symbols (one per output section, in header
    /// order) after the null symbol, moving every other symbol up.
    pub fn add_section_symbols(&mut self, count: usize) {
        if self.is_empty() || count == 0 {
            return;
        }
        for base in &mut self.local_base {
            *base = base.saturating_add(count);
        }
        self.hidden_base = self.hidden_base.saturating_add(count);
        self.first_global = self.first_global.saturating_add(count);
        self.count = self.count.saturating_add(count);
        self.section_symbols = self.section_symbols.saturating_add(count);
    }

    /// The table index of local symbol `symbol` of `file`, if it is kept.
    #[must_use]
    pub fn local_index(&self, file: usize, symbol: u32) -> Option<usize> {
        let kept = self.locals.get(file)?;
        let at = kept.binary_search(&symbol).ok()?;
        let file_symbol = usize::from(self.file_names.get(file).is_some_and(Option::is_some));
        self.local_base
            .get(file)?
            .checked_add(at)?
            .checked_add(file_symbol)
    }

    /// The table index of global symbol `id`, if it is in the table.
    #[must_use]
    pub fn global_index(&self, id: SymbolId) -> Option<usize> {
        if let Ok(at) = self.hidden.binary_search(&id) {
            return self
                .hidden_base
                .checked_add(usize::from(self.hidden_file))?
                .checked_add(at);
        }
        let at = self.globals.binary_search(&id).ok()?;
        self.first_global.checked_add(at)
    }

    /// `.symtab` size in bytes.
    #[must_use]
    pub fn symtab_size(&self) -> u64 {
        u64::try_from(self.count)
            .unwrap_or(u64::MAX)
            .saturating_mul(self.kind.sym_size())
    }

    /// Whether the table is written at all.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.count == 0
    }
}

/// The length of a symbol's name in `.strtab`: `name@version` for
/// versioned symbols.
/// The version a symbol imported from a shared library is written with
/// (`name@VERSION`, as GNU ld does), unless its name already has one.
fn import_suffix<'a, F: crate::elf::read::ElfFormat>(
    refs: &Refs<'_, 'a, F>,
    id: SymbolId,
) -> Option<&'a [u8]> {
    if refs.symbols.definition_kind(id) != DefinitionKind::Shared
        || refs.symbols.name(id).version().is_some()
    {
        return None;
    }
    super::dynsym::import_version(refs, id).map(|(_, version)| version)
}

/// The length of a global symbol's name in `.strtab`.
fn global_name_len<F: crate::elf::read::ElfFormat>(refs: &Refs<'_, '_, F>, id: SymbolId) -> usize {
    let len = name_len(refs.symbols.name(id));
    match import_suffix(refs, id) {
        Some(version) => len.saturating_add(1).saturating_add(version.len()),
        None => len,
    }
}

fn name_len(name: crate::symbols::SymbolName<'_>) -> usize {
    match name.version() {
        Some(version) => name
            .bytes()
            .len()
            .saturating_add(1)
            .saturating_add(version.len()),
        None => name.bytes().len(),
    }
}

/// In executables and shared objects, a TLS symbol's value is its offset in
/// the TLS template.
fn tls_relative<F: crate::elf::read::ElfFormat>(
    addresses: &Addresses<'_, '_, F>,
    kind: u8,
    value: u64,
    shndx: u16,
) -> u64 {
    if kind != STT_TLS || shndx == SHN_ABS || shndx == SHN_UNDEF {
        return value;
    }
    value.wrapping_sub(addresses.layout.tls.map_or(0, |t| t.start))
}

fn put_sym<F: ElfFormat>(
    out: &mut [u8],
    name: usize,
    info: u8,
    other: u8,
    shndx: u16,
    value: u64,
    size: u64,
) {
    let Some(entry) = out.get_mut(..<F::Sym as RawRecord>::SIZE) else {
        return;
    };
    let symbol = RawSymbol {
        st_name: u32::try_from(name).unwrap_or(0),
        st_info: info,
        st_other: other,
        st_shndx: shndx,
        st_value: value,
        st_size: size,
    };
    entry.copy_from_slice(F::encode_sym(&symbol).as_bytes());
}

/// The output section header index of input section `section` of `file`
/// (after ICF folding): `SHN_ABS` when its output section was dropped as
/// empty, `SHN_UNDEF` when it is not in the output.
pub(crate) fn shndx_for<F: crate::elf::read::ElfFormat>(
    addresses: &Addresses<'_, '_, F>,
    file: usize,
    section: u32,
) -> u16 {
    let Some(id) = addresses
        .refs
        .sections
        .id(file, section)
        .and_then(|id| addresses.refs.sections.resolve(id))
    else {
        return SHN_UNDEF;
    };
    let index = addresses
        .layout
        .section_shndx
        .get(id.index())
        .copied()
        .unwrap_or(0);
    if index == super::layout::EMPTY_SHNDX {
        return SHN_ABS;
    }
    u16::try_from(index).unwrap_or(crate::elf::read::consts::SHN_XINDEX)
}

/// Writes `.symtab` into `out`.
pub fn write_symtab<F: crate::elf::read::ElfFormat>(
    plan: &SymtabPlan,
    addresses: &Addresses<'_, '_, F>,
    linker: &LinkerSymbols,
    out: &mut [u8],
) {
    // The link's input format is its output format.
    write_symtab_as::<F>(plan, addresses, linker, out);
}

fn write_symtab_as<F: ElfFormat>(
    plan: &SymtabPlan,
    addresses: &Addresses<'_, '_, F>,
    linker: &LinkerSymbols,
    out: &mut [u8],
) {
    /// Splits `out` after `count` entries, clamped to what it holds.
    fn split<F: ElfFormat>(out: &mut [u8], count: usize) -> (&mut [u8], &mut [u8]) {
        let bytes = count
            .saturating_mul(<F::Sym as RawRecord>::SIZE)
            .min(out.len());
        out.split_at_mut(bytes)
    }
    let entry_size = <F::Sym as RawRecord>::SIZE;
    let refs = &addresses.refs;
    let (head, rest) = split::<F>(out, plan.section_symbols.saturating_add(1));
    for (position, (entry, section)) in head
        .chunks_exact_mut(entry_size)
        .skip(1)
        .zip(&addresses.layout.sections)
        .enumerate()
    {
        let shndx = u16::try_from(position.saturating_add(1))
            .unwrap_or(crate::elf::read::consts::SHN_XINDEX);
        put_sym::<F>(
            entry,
            0,
            (STB_LOCAL << 4) | STT_SECTION,
            0,
            shndx,
            section.addr,
            0,
        );
    }
    let local_count = plan
        .hidden_base
        .saturating_sub(1)
        .saturating_sub(plan.section_symbols);
    let (locals, rest) = split::<F>(rest, local_count);
    let (hidden_file, rest) = split::<F>(rest, usize::from(plan.hidden_file));
    for entry in hidden_file.chunks_exact_mut(entry_size) {
        put_sym::<F>(entry, 0, (STB_LOCAL << 4) | STT_FILE, 0, SHN_ABS, 0, 0);
    }
    let (hidden, globals) = split::<F>(rest, plan.hidden.len());

    // File locals, per file in parallel.
    let mut slices = Vec::with_capacity(plan.locals.len());
    let mut remaining = locals;
    for (file, kept) in plan.locals.iter().enumerate() {
        let file_symbol = usize::from(plan.file_names.get(file).is_some_and(Option::is_some));
        let n = kept.len().saturating_add(file_symbol);
        let (head, tail) = split::<F>(std::mem::take(&mut remaining), n);
        slices.push(head);
        remaining = tail;
    }
    slices
        .into_par_iter()
        .enumerate()
        .for_each(|(file_index, slice)| {
            let Some(object) = refs.files.get(file_index).and_then(|f| f.object.as_ref()) else {
                return;
            };
            let symbols = object.elf.symbols();
            let mut name_offset = plan.local_names.get(file_index).copied().unwrap_or(0);
            let kept = plan.locals.get(file_index).map_or(&[][..], Vec::as_slice);
            let mut slice = slice;
            if let Some(Some(name)) = plan.file_names.get(file_index)
                && slice.len() >= entry_size
            {
                let (entry, rest) = std::mem::take(&mut slice).split_at_mut(entry_size);
                put_sym::<F>(
                    entry,
                    name_offset,
                    (STB_LOCAL << 4) | STT_FILE,
                    0,
                    SHN_ABS,
                    0,
                    0,
                );
                name_offset = name_offset.saturating_add(name.len()).saturating_add(1);
                slice = rest;
            }
            for (entry, &index) in slice.chunks_exact_mut(entry_size).zip(kept) {
                let index = index as usize;
                let Some(raw) = symbols.get_raw(index) else {
                    continue;
                };
                let name_len = symbols.name(index, &raw).map_or(0, <[u8]>::len);
                let (shndx, value, size) = match symbols.section(index, &raw) {
                    Ok(SectionIndex::Section(section)) => (
                        shndx_for(addresses, file_index, section),
                        addresses
                            .section_offset_address(file_index, section, raw.st_value)
                            .unwrap_or(0),
                        addresses.symbol_size(file_index, section, raw.st_value, raw.st_size),
                    ),
                    _ => (SHN_ABS, raw.st_value, raw.st_size),
                };
                let value = tls_relative(addresses, raw.kind(), value, shndx);
                put_sym::<F>(
                    entry,
                    name_offset,
                    raw.st_info,
                    raw.st_other,
                    shndx,
                    value,
                    size,
                );
                name_offset = name_offset.saturating_add(name_len).saturating_add(1);
            }
        });

    let global_entry = |id: SymbolId, local: bool, name_offset: usize, entry: &mut [u8]| {
        let target = refs.global_target(id, true);
        let value = addresses.globals.get(id.index()).copied().unwrap_or(0);
        let (binding, kind, other, shndx, size) = match target.def {
            Def::Section {
                file,
                section,
                value,
            } => {
                let raw = target.raw.unwrap_or_default();
                (
                    raw.binding(),
                    raw.kind(),
                    raw.st_other,
                    shndx_for(addresses, file, section),
                    addresses.symbol_size(file, section, value, raw.st_size),
                )
            }
            Def::Absolute(_) => {
                let raw = target.raw.unwrap_or_default();
                (
                    raw.binding(),
                    raw.kind(),
                    raw.st_other,
                    SHN_ABS,
                    raw.st_size,
                )
            }
            Def::Common(_) => {
                let def = refs.symbols.definition(id);
                (
                    STB_GLOBAL,
                    STT_OBJECT,
                    STV_DEFAULT,
                    shndx_of_address(addresses, value),
                    def.aux & !super::resolve::AUX_COMDAT,
                )
            }
            Def::Linker(_) => {
                let visibility = global_visibility(refs, linker, id);
                let absolute = refs.symbols.flags(id).contains(super::defined::ABSOLUTE);
                (
                    STB_GLOBAL,
                    super::defined::linker_type(refs, linker, id),
                    visibility,
                    if absolute {
                        SHN_ABS
                    } else {
                        super::defined::linker_shndx(addresses, linker, id)
                            .unwrap_or_else(|| shndx_of_address(addresses, value))
                    },
                    0,
                )
            }
            Def::Shared(_) => {
                let raw = target.raw.unwrap_or_default();
                if addresses.synth.copy_of(id).is_some() {
                    (
                        STB_GLOBAL,
                        raw.kind(),
                        STV_DEFAULT,
                        shndx_of_address(addresses, value),
                        raw.st_size,
                    )
                } else {
                    (
                        import_binding(refs, id),
                        raw.kind(),
                        STV_DEFAULT,
                        SHN_UNDEF,
                        0,
                    )
                }
            }
            Def::Undefined { .. } => (
                import_binding(refs, id),
                STT_NOTYPE,
                STV_DEFAULT,
                SHN_UNDEF,
                0,
            ),
        };
        // Globals made local lose their visibility, as in GNU ld.
        let (binding, other) = if local {
            (STB_LOCAL, other & !3)
        } else {
            (binding, other)
        };
        let value = tls_relative(addresses, kind, value, shndx);
        put_sym::<F>(
            entry,
            name_offset,
            (binding << 4) | (kind & 0xf),
            other,
            shndx,
            value,
            size,
        );
    };

    // Name offsets were computed by the plan, from the same lengths.
    hidden
        .par_chunks_exact_mut(entry_size)
        .zip(plan.hidden.par_iter())
        .zip(plan.hidden_offsets.par_iter())
        .for_each(|((entry, &id), &name)| global_entry(id, true, name, entry));
    globals
        .par_chunks_exact_mut(entry_size)
        .zip(plan.globals.par_iter())
        .zip(plan.global_offsets.par_iter())
        .for_each(|((entry, &id), &name)| global_entry(id, false, name, entry));
}

/// Writes `.strtab` into `out`: each file's local names, then the hidden
/// and global names, from the offsets the plan computed, in parallel.
pub fn write_strtab<F: crate::elf::read::ElfFormat>(
    plan: &SymtabPlan,
    refs: &Refs<'_, '_, F>,
    out: &mut [u8],
) {
    /// Globals whose names one task writes.
    const NAMES_PER_TASK: usize = 4096;
    enum Task<'p> {
        /// Local names of a file.
        Locals(usize),
        /// Consecutive hidden or global names.
        Globals(&'p [SymbolId]),
    }
    // Every task writes into its own slice of `out`, which starts at its
    // first name's offset; the plan's offsets increase in this order.
    let mut starts: Vec<(usize, Task<'_>)> = Vec::new();
    for (file_index, &start) in plan.local_names.iter().enumerate() {
        starts.push((start, Task::Locals(file_index)));
    }
    for (ids, offsets) in [
        (&plan.hidden, &plan.hidden_offsets),
        (&plan.globals, &plan.global_offsets),
    ] {
        for (chunk, chunk_offsets) in ids
            .chunks(NAMES_PER_TASK)
            .zip(offsets.chunks(NAMES_PER_TASK))
        {
            if let Some(&start) = chunk_offsets.first() {
                starts.push((start, Task::Globals(chunk)));
            }
        }
    }
    let mut tasks: Vec<(Task<'_>, &mut [u8])> = Vec::with_capacity(starts.len());
    let mut rest: &mut [u8] = out;
    let mut consumed = 0usize;
    let mut starts = starts.into_iter().peekable();
    while let Some((start, task)) = starts.next() {
        let end = starts
            .peek()
            .map_or(consumed.saturating_add(rest.len()), |&(next, _)| next);
        // Skip up to `start` (the null byte, or nothing), then take this
        // task's bytes; out-of-range offsets give empty slices.
        let skip = start.saturating_sub(consumed).min(rest.len());
        let (_, tail) = std::mem::take(&mut rest).split_at_mut(skip);
        let take = end.saturating_sub(start).min(tail.len());
        let (slice, tail) = tail.split_at_mut(take);
        tasks.push((task, slice));
        rest = tail;
        consumed = consumed.saturating_add(skip).saturating_add(take);
    }
    tasks.into_par_iter().for_each(|(task, slice)| match task {
        Task::Locals(file_index) => {
            let (Some(object), Some(kept)) = (
                refs.files.get(file_index).and_then(|f| f.object.as_ref()),
                plan.locals.get(file_index),
            ) else {
                return;
            };
            let symbols = object.elf.symbols();
            let mut cursor = 0usize;
            if let Some(Some(name)) = plan.file_names.get(file_index) {
                cursor = put_name(slice, cursor, name);
            }
            for &index in kept {
                let name = symbols
                    .get_raw(index as usize)
                    .and_then(|raw| symbols.name(index as usize, &raw).ok())
                    .unwrap_or_default();
                cursor = put_name(slice, cursor, name);
            }
        }
        Task::Globals(ids) => {
            let mut cursor = 0usize;
            for &id in ids {
                let name = refs.symbols.name(id);
                let version = name.version().or_else(|| import_suffix(refs, id));
                cursor = match version {
                    Some(version) => {
                        let end = cursor.saturating_add(name.bytes().len());
                        if let Some(dest) = slice.get_mut(cursor..end) {
                            dest.copy_from_slice(name.bytes());
                        }
                        if let Some(at) = slice.get_mut(end) {
                            *at = b'@';
                        }
                        put_name(slice, end.saturating_add(1), version)
                    }
                    None => put_name(slice, cursor, name.bytes()),
                };
            }
        }
    });
}

/// The binding of an undefined or imported symbol: weak when every
/// reference from a regular object is weak.
fn import_binding<F: crate::elf::read::ElfFormat>(refs: &Refs<'_, '_, F>, id: SymbolId) -> u8 {
    if refs.symbols.flags(id).contains(REF_REGULAR_STRONG) {
        STB_GLOBAL
    } else {
        STB_WEAK
    }
}

fn put_name(out: &mut [u8], at: usize, name: &[u8]) -> usize {
    let end = at.saturating_add(name.len());
    if let Some(dest) = out.get_mut(at..end) {
        dest.copy_from_slice(name);
    }
    end.saturating_add(1)
}