qld 0.1.0

A fast, parallel linker compatible with GNU ld, gold, lld and mold
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

//! Common symbol allocation.
//!
//! A common symbol that wins resolution gets space at the end of `.bss`,
//! with the size of the largest tentative definition (resolution already
//! picked it) and the alignment its `st_value` gives. Symbols are laid out
//! in input order of their winning definitions, so the layout does not
//! depend on symbol IDs or threads.

#![deny(clippy::arithmetic_side_effects)]

use rayon::prelude::*;

use crate::ids::SymbolId;
use crate::symbols::DefinitionKind;

use super::refs::Refs;
use super::resolve::AUX_COMDAT;

/// Allocated common symbols.
#[derive(Debug, Default)]
pub struct Commons {
    /// `(symbol, offset in the common block)`, sorted by symbol.
    pub entries: Vec<(SymbolId, u64)>,
    /// Total size.
    pub size: u64,
    /// Largest alignment.
    pub align: u64,
}

impl Commons {
    /// Offset of `id` in the common block.
    #[must_use]
    pub fn offset(&self, id: SymbolId) -> Option<u64> {
        let at = self.entries.binary_search_by_key(&id, |(i, _)| *i).ok()?;
        self.entries.get(at).map(|(_, offset)| *offset)
    }
}

/// Lays out the common symbols that won resolution.
#[must_use]
pub fn allocate<F: crate::elf::read::ElfFormat>(refs: &Refs<'_, '_, F>) -> Commons {
    let symbols = refs.symbols;
    let mut winners: Vec<(u64, u32, SymbolId, u64, u64)> = symbols
        .ids()
        .collect::<Vec<_>>()
        .into_par_iter()
        .filter_map(|id| {
            let def = symbols.definition(id);
            if def.kind != DefinitionKind::Common {
                return None;
            }
            let object = refs.files.get(def.file.index())?.object.as_ref()?;
            let index = (def.index as usize).checked_add(object.first_global)?;
            let raw = object.elf.symbols().get_raw(index)?;
            let align = raw.st_value.max(1);
            let align = if align.is_power_of_two() { align } else { 1 };
            Some((
                def.position.raw(),
                def.index,
                id,
                def.aux & !AUX_COMDAT,
                align,
            ))
        })
        .collect();
    winners.sort_unstable();
    let mut commons = Commons {
        entries: Vec::with_capacity(winners.len()),
        size: 0,
        align: 1,
    };
    for (_, _, id, size, align) in winners {
        let Some(offset) = commons
            .size
            .checked_add(align.wrapping_sub(1))
            .map(|v| v & !align.wrapping_sub(1))
        else {
            continue;
        };
        commons.size = offset.saturating_add(size);
        commons.align = commons.align.max(align);
        commons.entries.push((id, offset));
    }
    commons.entries.sort_unstable();
    commons
}