commit b2ebc0984197454989a89dea2ea161ae00896d4f
parent 42cdf5839f7c52fe506cb1a3d459f7609c8c4ef8
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Tue, 16 Jun 2026 11:22:21 -0700
Speed up linker DSO undef resolution
Diffstat:
2 files changed, 62 insertions(+), 42 deletions(-)
diff --git a/src/link/link_reloc_layout.c b/src/link/link_reloc_layout.c
@@ -919,21 +919,25 @@ void link_emit_relocations(Linker* l, LinkImage* img, const LinkSymId* got_map,
const LinkSymId* stub_map) {
u32 ii;
for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) {
- ObjBuilder* ob = LinkInputs_at(&l->inputs, ii)->obj;
+ LinkInput* in = LinkInputs_at(&l->inputs, ii);
+ ObjBuilder* ob = in->obj;
InputMap* m = &img->input_maps[ii];
u32 total = obj_reloc_total(ob);
u32 k;
if (total == 0) continue;
for (k = 0; k < total; ++k) {
const Reloc* r = obj_reloc_at(ob, k);
+ RelocKind kind = (RelocKind)r->kind;
const Section* s = obj_section_get(ob, r->section_id);
LinkSymId target;
+ LinkSectionId src_lsid;
LinkSection* ls;
LinkRelocApply rec;
if (!s || (!link_section_kept(s) && !link_section_kept_fileonly(s)))
continue;
- if (link_input_reloc_section(m, r, k) == LINK_SEC_NONE) continue;
- if (reloc_kind_is_marker(l->c, (RelocKind)r->kind)) continue;
+ src_lsid = link_input_reloc_section(m, r, k);
+ if (src_lsid == LINK_SEC_NONE) continue;
+ if (reloc_kind_is_marker(l->c, kind)) continue;
if (r->sym == OBJ_SYM_NONE || r->sym >= m->nsym)
compiler_panic(l->c, SRCLOC_NONE,
"link: reloc references unknown symbol");
@@ -951,31 +955,27 @@ void link_emit_relocations(Linker* l, LinkImage* img, const LinkSymId* got_map,
compiler_panic(l->c, SRCLOC_NONE,
"link: reloc references unmapped symbol");
}
- if (got_map && reloc_kind_uses_got(l->c, r->kind)) {
+ if (got_map && reloc_kind_uses_got(l->c, kind)) {
LinkSymId slot = got_map[target];
if (slot == LINK_SYM_NONE)
compiler_panic(l->c, SRCLOC_NONE,
"link: GOT slot missing for symbol");
target = slot;
}
- if (stub_map && reloc_kind_is_branch(l->c, r->kind)) {
+ if (stub_map && reloc_kind_is_branch(l->c, kind)) {
LinkSymId stub = stub_map[target];
if (stub != LINK_SYM_NONE) target = stub;
}
- {
- LinkSectionId src_lsid = link_input_reloc_section(m, r, k);
- if (src_lsid == LINK_SEC_NONE) continue;
- ls = &img->sections[src_lsid - 1];
- }
+ ls = &img->sections[src_lsid - 1];
memset(&rec, 0, sizeof(rec));
- rec.input_id = LinkInputs_at(&l->inputs, ii)->id;
+ rec.input_id = in->id;
rec.section_id = r->section_id;
rec.link_section_id = ls->id;
rec.offset = r->offset - (u32)ls->obj_offset;
- rec.width = reloc_kind_width(l->c, (RelocKind)r->kind);
+ rec.width = reloc_kind_width(l->c, kind);
rec.write_vaddr = ls->vaddr + rec.offset;
rec.write_file_offset = ls->file_offset + rec.offset;
- rec.kind = (RelocKind)r->kind;
+ rec.kind = kind;
rec.target = target;
rec.addend = r->addend;
if (rec.width == 0)
diff --git a/src/link/link_resolve.c b/src/link/link_resolve.c
@@ -349,27 +349,41 @@ void link_resolve_symbols(Linker* l, LinkImage* img) {
}
}
-/* Search DSO inputs for an exported symbol matching `name`. */
-static LinkInputId find_dso_export(Linker* l, Sym name) {
+static int obj_sym_is_dso_export(const ObjSym* s) {
+ return s && s->name != 0 && s->kind != SK_UNDEF && s->bind != SB_LOCAL;
+}
+
+static void dso_exports_build(Linker* l, SymHash* exports) {
u32 ii;
- ObjSymIter* it;
- ObjSymEntry e;
- if (name == 0) return LINK_INPUT_NONE;
+ u32 nexports = 0;
+ symhash_init(exports, l->heap);
for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) {
LinkInput* in = LinkInputs_at(&l->inputs, ii);
+ ObjSymIter* it;
+ ObjSymEntry e;
if (in->kind != LINK_INPUT_DSO_BYTES) continue;
it = obj_symiter_new(in->obj);
while (obj_symiter_next(it, &e)) {
- const ObjSym* s = e.sym;
- if (s->name != name) continue;
- if (s->kind == SK_UNDEF) continue;
- if (s->bind == SB_LOCAL) continue;
- obj_symiter_free(it);
- return in->id;
+ if (obj_sym_is_dso_export(e.sym)) ++nexports;
+ }
+ obj_symiter_free(it);
+ }
+ symhash_reserve(exports, nexports);
+ for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) {
+ LinkInput* in = LinkInputs_at(&l->inputs, ii);
+ ObjSymIter* it;
+ ObjSymEntry e;
+ if (in->kind != LINK_INPUT_DSO_BYTES) continue;
+ it = obj_symiter_new(in->obj);
+ while (obj_symiter_next(it, &e)) {
+ LinkSymId existing;
+ if (!obj_sym_is_dso_export(e.sym)) continue;
+ /* Preserve command-line order: the old lookup returned the first DSO
+ * exporting a name, so duplicate exports keep the earliest provider. */
+ (void)symhash_insert(exports, e.sym->name, in->id, &existing);
}
obj_symiter_free(it);
}
- return LINK_INPUT_NONE;
}
static int elf_split_versioned_undef(Compiler* c, Sym full, Sym* base_out,
@@ -449,8 +463,8 @@ static int resolve_elf_versioned_dso_undef(Linker* l, LinkSymbol* s) {
/* Resolve undefined symbol `s` to the symbol named `alias` (a defined image
* global or a DSO export), copying the target's binding into `s`. Returns 1 on
* success. Shared by the recorded-alias path and the underscore heuristic. */
-static int resolve_to_alias(Linker* l, LinkImage* img, LinkSymbol* s,
- Sym alias) {
+static int resolve_to_alias(LinkImage* img, const SymHash* dso_exports,
+ LinkSymbol* s, Sym alias) {
if (alias == 0) return 0;
LinkSymId hit = symhash_get(&img->globals, alias);
if (hit != LINK_SYM_NONE) {
@@ -473,7 +487,7 @@ static int resolve_to_alias(Linker* l, LinkImage* img, LinkSymbol* s,
return 1;
}
}
- LinkInputId dso = find_dso_export(l, alias);
+ LinkInputId dso = symhash_get(dso_exports, alias);
if (dso != LINK_INPUT_NONE) {
s->name = alias;
s->imported = 1;
@@ -517,19 +531,23 @@ void link_resolve_undefs(Linker* l, LinkImage* img) {
* input the reference vs. the declarator came from. Empty for non-COFF. */
SymHash alias_map;
symhash_init(&alias_map, l->heap);
- for (u32 ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) {
- LinkInput* in = LinkInputs_at(&l->inputs, ii);
- if (!in->obj || in->kind == LINK_INPUT_DSO_BYTES) continue;
- u32 na = obj_weak_alias_count(in->obj);
- for (u32 ai = 0; ai < na; ++ai) {
- ObjSymId asym = OBJ_SYM_NONE;
- Sym target = 0;
- if (!obj_weak_alias_at(in->obj, ai, &asym, &target) || target == 0)
- continue;
- const ObjSym* os = obj_symbol_get(in->obj, asym);
- if (os && os->name != 0) symhash_set(&alias_map, os->name, target);
+ if (l->c->target.obj == KIT_OBJ_COFF) {
+ for (u32 ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) {
+ LinkInput* in = LinkInputs_at(&l->inputs, ii);
+ if (!in->obj || in->kind == LINK_INPUT_DSO_BYTES) continue;
+ u32 na = obj_weak_alias_count(in->obj);
+ for (u32 ai = 0; ai < na; ++ai) {
+ ObjSymId asym = OBJ_SYM_NONE;
+ Sym target = 0;
+ if (!obj_weak_alias_at(in->obj, ai, &asym, &target) || target == 0)
+ continue;
+ const ObjSym* os = obj_symbol_get(in->obj, asym);
+ if (os && os->name != 0) symhash_set(&alias_map, os->name, target);
+ }
}
}
+ SymHash dso_exports;
+ dso_exports_build(l, &dso_exports);
for (i = 0; i < LinkSyms_count(&img->syms); ++i) {
LinkSymbol* s = LinkSyms_at(&img->syms, i);
@@ -553,7 +571,7 @@ void link_resolve_undefs(Linker* l, LinkImage* img) {
if (resolve_elf_versioned_dso_undef(l, s)) {
continue;
}
- LinkInputId dso = find_dso_export(l, s->name);
+ LinkInputId dso = symhash_get(&dso_exports, s->name);
if (dso != LINK_INPUT_NONE) {
s->imported = 1;
s->dso_input_id = dso;
@@ -590,7 +608,7 @@ void link_resolve_undefs(Linker* l, LinkImage* img) {
for (u32 hop = 0; hop < 8u; ++hop) {
Sym target = symhash_get(&alias_map, cur);
if (target == 0) break;
- if (resolve_to_alias(l, img, s, target)) {
+ if (resolve_to_alias(img, &dso_exports, s, target)) {
resolved = 1;
break;
}
@@ -623,7 +641,8 @@ void link_resolve_undefs(Linker* l, LinkImage* img) {
}
int resolved = 0;
for (u32 ci = 0; !resolved && ci < ncand; ++ci) {
- if (resolve_to_alias(l, img, s, candidates[ci])) resolved = 1;
+ if (resolve_to_alias(img, &dso_exports, s, candidates[ci]))
+ resolved = 1;
}
if (resolved) continue;
}
@@ -658,6 +677,7 @@ void link_resolve_undefs(Linker* l, LinkImage* img) {
(int)namelen, nm);
}
}
+ symhash_fini(&dso_exports);
symhash_fini(&alias_map);
}
