xold 0.0.5

A maintainable multi-threaded linker for ELF, Mach-O and COFF.
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
//! Library search: resolves `-l NAME` to a concrete file by scanning the
//! directories named with `-L` followed by the host's default search paths.
//!
//! Within a directory the order is `libNAME.so`, then the highest versioned
//! `libNAME.so.M`, then `libNAME.a`. The bare name leads because that is the
//! one the developer package installs and the one every reference linker
//! resolves: a tree with a `libfoo.so` symlink to `libfoo.so.1` beside a
//! runtime `libfoo.so.2` must link against 1, as it does everywhere else,
//! rather than silently against a different ABI.
//!
//! A candidate is accepted as an ELF object, an archive, or a GNU ld script
//! ([`crate::script`]) -- on GNU systems the bare name is frequently the last
//! of those, `libc.so` being text that `GROUP`s `libc.so.6`. What a candidate
//! is, is read out of its bytes rather than assumed from its name, the
//! versioned pick included, and the versioned scan stays as the fallback for a
//! bare name that is none of the three.
//!
//! `-l:filename` names a file outright, with no `lib` prefix or suffix added,
//! and is searched for by that name alone.
//!
//! # Cross links
//!
//! [`DEFAULT_PATHS`] describes the host. A link that targets another
//! architecture must not resolve `-l` against the host's libraries, so
//! `--sysroot` re-roots those defaults at another tree. It does not move the
//! `-L` directories, which name themselves; a `-L` path that is meant to be
//! sysroot-relative says so by leading with `=`, as it does for GNU `ld`.

use std::{
    io::Read as _,
    path::{Path, PathBuf},
};

/// Default directories searched after any `-L` paths, matching a native
/// x86-64 glibc layout. `/usr/local/lib64` leads so locally installed
/// libraries win, as with the system linker. Under `--sysroot` each is taken
/// relative to that tree instead.
const DEFAULT_PATHS: [&str; 5] = [
    "/usr/local/lib64",
    "/usr/lib64",
    "/lib64",
    "/usr/local/lib",
    "/usr/lib",
];

/// The marker that makes a `-L` path sysroot-relative, following GNU `ld`.
const SYSROOT_PREFIX: char = '=';

/// Resolves `-l name` to a concrete file path, scanning `search` then the
/// default directories in order. Returns the first directory that yields a
/// candidate.
///
/// `sysroot` re-roots the default directories, and any `-L` path written as
/// `=/usr/lib`. Pass `None` for a native link.
pub fn find_library(
    name: &str,
    search: &[PathBuf],
    sysroot: Option<&Path>,
) -> Option<PathBuf> {
    find_library_kind(name, search, sysroot, LibKind::Any)
}

/// Resolves a Darwin `-l name`, preferring the SDK's text-based API stub,
/// then a real dylib, then a static archive.
///
/// ld64's `-syslibroot` re-roots `/usr/lib`, where Apple SDKs publish
/// `libSystem.tbd`, `libc.tbd` and `libm.tbd`. Explicit `-L` paths keep their
/// ordinary meaning, matching the ELF search path handling in this module.
pub fn find_macho_library(
    name: &str,
    search: &[PathBuf],
    sysroot: Option<&Path>,
) -> Option<PathBuf> {
    let exact = name.strip_prefix(':');
    let look = |dir: &Path| {
        if let Some(file) = exact {
            let path = dir.join(file);
            return path.exists().then_some(path);
        }
        for suffix in [".tbd", ".dylib", ".a"] {
            let path = dir.join(format!("lib{name}{suffix}"));
            if path.exists() {
                return Some(path);
            }
        }
        None
    };
    for dir in search.iter().map(|dir| rooted_search(sysroot, dir)) {
        if let Some(found) = look(&dir) {
            return Some(found);
        }
    }
    for dir in DEFAULT_PATHS {
        if let Some(found) = look(&rooted(sysroot, dir)) {
            return Some(found);
        }
    }
    None
}

/// Resolves ld64's `-framework name` to the SDK TAPI stub.
///
/// Explicit `-F` directories lead, followed by the two conventional framework
/// roots.  A syslibroot re-roots the conventional absolute paths, while an
/// explicit framework path keeps the spelling the driver supplied.
pub fn find_macho_framework(
    name: &str,
    search: &[PathBuf],
    sysroot: Option<&Path>,
) -> Option<PathBuf> {
    let look = |dir: &Path| {
        let path = dir
            .join(format!("{name}.framework"))
            .join(format!("{name}.tbd"));
        path.exists().then_some(path)
    };
    for dir in search {
        if let Some(found) = look(dir) {
            return Some(found);
        }
    }
    for dir in ["/System/Library/Frameworks", "/Library/Frameworks"] {
        if let Some(found) = look(&rooted(sysroot, dir)) {
            return Some(found);
        }
    }
    None
}

/// Which files a `-l` search will accept.
///
/// A command line switches between the two with `-Bstatic` and `-Bdynamic`,
/// so which one applies is a property of the position `-l` was written at,
/// not of the link. A driver uses it to pin one library to its archive while
/// the rest of the line stays dynamic: `gcc` wraps `-lgcc` that way, and
/// `rustc` wraps the Rust standard library.
#[derive(Clone, Copy, PartialEq, Eq, Default)]
pub enum LibKind {
    /// `libNAME.so`, then the highest versioned `libNAME.so.M`, then
    /// `libNAME.a`. The default, and what `-Bdynamic` restores.
    #[default]
    Any,
    /// `libNAME.a` only, as `-Bstatic` asks. A shared object of the same name
    /// beside it is passed over rather than preferred.
    ArchiveOnly,
}

/// Resolves `-l name` under an explicit [`LibKind`].
pub fn find_library_kind(
    name: &str,
    search: &[PathBuf],
    sysroot: Option<&Path>,
    kind: LibKind,
) -> Option<PathBuf> {
    // `-l:filename` names the file itself. No prefix and no suffix are added,
    // and no versioned scan runs: the caller already said which file.
    let exact = name.strip_prefix(':');
    let look = |dir: &Path| match (exact, kind) {
        (Some(file), LibKind::Any) => find_exact(file, dir),
        (Some(file), LibKind::ArchiveOnly) => {
            let path = dir.join(file);
            is_archive(&path).then_some(path)
        }
        (None, LibKind::Any) => find_in(name, dir),
        (None, LibKind::ArchiveOnly) => find_archive(name, dir),
    };
    for dir in search.iter().map(|dir| rooted_search(sysroot, dir)) {
        if let Some(found) = look(&dir) {
            return Some(found);
        }
    }
    for dir in DEFAULT_PATHS {
        if let Some(found) = look(&rooted(sysroot, dir)) {
            return Some(found);
        }
    }
    None
}

/// Finds `file` by that exact name in the `-L` directories and then the
/// defaults, which is how a linker script's `INPUT` and `GROUP` lists resolve
/// a relative name that is not beside the script.
///
/// Existence is the whole test, as it is in lld's `findFromSearchPaths`
/// (`lld/ELF/DriverUtils.cpp`): the script said which file it
/// wants, so a candidate that turns out to be the wrong kind is an error to
/// report against that file rather than a reason to keep looking.
pub fn find_in_paths(
    file: &str,
    search: &[PathBuf],
    sysroot: Option<&Path>,
) -> Option<PathBuf> {
    let named = |dir: &Path| {
        let path = dir.join(file);
        path.exists().then_some(path)
    };
    for dir in search.iter().map(|dir| rooted_search(sysroot, dir)) {
        if let Some(found) = named(&dir) {
            return Some(found);
        }
    }
    for dir in DEFAULT_PATHS {
        if let Some(found) = named(&rooted(sysroot, dir)) {
            return Some(found);
        }
    }
    None
}

/// A `-L` directory as it should be searched: unchanged, unless it leads with
/// `=`, which asks for the remainder to be taken relative to the sysroot.
fn rooted_search(sysroot: Option<&Path>, dir: &Path) -> PathBuf {
    let Some(rest) = dir.to_str().and_then(|d| d.strip_prefix(SYSROOT_PREFIX))
    else {
        return dir.to_path_buf();
    };
    rooted(sysroot, rest)
}

/// Joins a default path onto the sysroot, or returns it unchanged when there
/// is none. The leading separator is trimmed so the join does not discard the
/// root.
pub fn rooted(sysroot: Option<&Path>, path: &str) -> PathBuf {
    sysroot.map_or_else(
        || PathBuf::from(path),
        |root| root.join(path.trim_start_matches('/')),
    )
}

/// Looks for a `-l:filename` candidate: that exact name, accepted as a shared
/// object, an archive or a linker script according to its own contents.
fn find_exact(file: &str, dir: &Path) -> Option<PathBuf> {
    let path = dir.join(file);
    (is_archive(&path) || is_linkable(&path)).then_some(path)
}

/// Looks for `name`'s library inside one directory: a real-ELF
/// `libNAME.so`, else the highest versioned `libNAME.so.M`, else a real
/// `libNAME.a`.
///
/// The bare name leads because it is the one every reference linker resolves,
/// and picking a versioned file over it silently swaps the ABI: a developer
/// symlink `libfoo.so -> libfoo.so.1` beside a runtime `libfoo.so.2` must
/// still mean 1. A bare name that is a linker script leads just the same,
/// since that script is how the system spells which files the library is made
/// of; the versioned scan is the fallback for a bare name that is neither.
///
/// One `read_dir` serves both shared-object spellings: the versioned names can
/// only be found by scanning, and the bare one is recognised on the way past.
/// The scan is reached only when the bare name is not there: on a development
/// system it nearly always is, and one direct lookup is far cheaper than
/// walking a library directory of several thousand entries per `-l`.
fn find_in(name: &str, dir: &Path) -> Option<PathBuf> {
    let prefix = format!("lib{name}.so.");
    let bare = format!("lib{name}.so");
    let lead = dir.join(&bare);
    if is_linkable(&lead) {
        return Some(lead);
    }
    let entries = std::fs::read_dir(dir).ok()?;
    let mut best: Option<(PathBuf, Vec<u64>, String)> = None;
    let mut bare_so: Option<PathBuf> = None;
    for entry in entries.flatten() {
        let file_name = entry.file_name();
        let Some(fname) = file_name.to_str() else {
            continue;
        };
        if fname == bare {
            bare_so = Some(entry.path());
        } else if let Some(rest) = fname.strip_prefix(&prefix) {
            let key = version_key(rest);
            // The name breaks a tie in the numeric key. Without it the winner
            // between `libfoo.so.1.0` and `libfoo.so.1.x` is whichever
            // `read_dir` handed over first, which is the filesystem's
            // business and not an ordering.
            let better =
                best.as_ref().is_none_or(|(_, prev_key, prev_name)| {
                    (&key, fname) > (prev_key, prev_name.as_str())
                });
            if better {
                best = Some((entry.path(), key, fname.to_owned()));
            }
        }
    }
    // Every candidate is read before it is accepted: nothing about a name
    // makes a file an object, and on GNU systems `libNAME.so` and `libNAME.a`
    // are both names a linker script takes.
    if let Some(path) = bare_so.filter(|p| is_linkable(p)) {
        return Some(path);
    }
    if let Some(path) = best.map(|(p, _, _)| p).filter(|p| is_linkable(p)) {
        return Some(path);
    }
    let archive = dir.join(format!("lib{name}.a"));
    (is_archive(&archive) || is_script(&archive)).then_some(archive)
}

/// Looks for `name`'s archive inside one directory, which is all a `-Bstatic`
/// `-l` will take.
///
/// A linker script under the archive name is accepted for the same reason the
/// shared search accepts one: on GNU systems that text is how a library says
/// which files it is made of.
fn find_archive(name: &str, dir: &Path) -> Option<PathBuf> {
    let archive = dir.join(format!("lib{name}.a"));
    (is_archive(&archive) || is_script(&archive)).then_some(archive)
}

/// Whether the shared-object candidate at `path` is one the link can consume:
/// a real ELF object, or a linker script naming the files that are.
fn is_linkable(path: &Path) -> bool {
    has_magic(path, ELF_MAGIC) || is_script(path)
}

/// Whether the file at `path` is a GNU ld script.
///
/// Decided by content like every other candidate here. `libNAME.so` being a
/// script is a convention rather than a rule, so the bytes are what answer;
/// see [`crate::script::looks_like`], which the driver applies to the same
/// leading bytes when it expands the file.
fn is_script(path: &Path) -> bool {
    let Ok(mut file) = std::fs::File::open(path) else {
        return false;
    };
    let mut head = [0u8; SCRIPT_PROBE];
    let mut filled = 0usize;
    while filled < head.len() {
        // A short read is the end of the file, not a failure: a script may be
        // shorter than the probe.
        let Ok(n @ 1..) = file.read(&mut head[filled..]) else {
            break;
        };
        filled = filled.saturating_add(n);
    }
    crate::script::looks_like(head.get(..filled).unwrap_or(&head))
}

/// How much of a candidate is read to tell script text from an object. Long
/// enough that a binary whose first bytes happen to be printable is still
/// caught, short enough to stay one page.
const SCRIPT_PROBE: usize = 64;

/// Parses the dotted suffix after `libNAME.so.` (for example `6` or `6.0.1`)
/// into a vector of numeric components, dropping any non-numeric trailing
/// parts. Non-numeric segments compare as zero, which is correct for the
/// common all-numeric glibc versions. Comparing component by component is
/// what puts `.10` above `.9` rather than below it.
fn version_key(suffix: &str) -> Vec<u64> {
    suffix
        .split('.')
        .map(|part| part.parse::<u64>().unwrap_or(0))
        .collect()
}

/// The bytes an ELF object opens with.
const ELF_MAGIC: &[u8] = b"\x7fELF";

/// The bytes an `ar` archive opens with.
const ARCHIVE_MAGIC: &[u8] = b"!<arch>\n";

/// The bytes a thin `ar` archive opens with.
///
/// A thin archive stores the paths of its members instead of their bytes.
/// `archive::Archive` reads both flavours, so a search that probed only
/// `!<arch>\n` reported a valid `libNAME.a` as missing.
const THIN_ARCHIVE_MAGIC: &[u8] = b"!<thin>\n";

/// The longest magic this module probes for, which fixes the read buffer.
const MAGIC_MAX: usize = 8;

/// Whether the file at `path` opens with `magic`.
///
/// Only the leading bytes are read, into the stack: this runs once per
/// candidate directory, and the files it probes are whole shared libraries,
/// so reading one to look at four bytes would be megabytes of pure waste.
fn has_magic(path: &Path, magic: &[u8]) -> bool {
    has_any_magic(path, &[magic])
}

/// Whether the file at `path` opens with any of `magics`.
///
/// The head is read once and compared against each candidate, so probing for
/// both archive flavours costs one open rather than two.
fn has_any_magic(path: &Path, magics: &[&[u8]]) -> bool {
    let want = magics.iter().map(|m| m.len()).max().unwrap_or(0);
    debug_assert!(want <= MAGIC_MAX, "magic fits the probe buffer");
    let Ok(mut file) = std::fs::File::open(path) else {
        return false;
    };
    let mut head = [0u8; MAGIC_MAX];
    let Some(slot) = head.get_mut(..want) else {
        return false;
    };
    // `read` may stop short of the buffer even when the file is longer, so
    // the head is filled in a loop rather than in one call. A zero-length
    // read is end of file: the candidate is shorter than the longest magic,
    // which still leaves it able to match a shorter one.
    let mut filled = 0usize;
    while filled < slot.len() {
        let Ok(n @ 1..) = file.read(&mut slot[filled..]) else {
            break;
        };
        filled = filled.saturating_add(n);
    }
    let read = slot.get(..filled).unwrap_or(&[]);
    magics.iter().any(|m| read.get(..m.len()) == Some(*m))
}

/// Whether the file at `path` is an `ar` archive of either flavour.
fn is_archive(path: &Path) -> bool {
    has_any_magic(path, &[ARCHIVE_MAGIC, THIN_ARCHIVE_MAGIC])
}