link_relocatable.c (16498B)
1 /* Relocatable partial linking (`ld -r`). 2 * 3 * This path deliberately builds a fresh ObjBuilder instead of routing through 4 * LinkImage. LinkImage is an executable/JIT image model: it drops non-alloc 5 * sections, resolves strong undefs, synthesizes boundary/GOT/IPLT state, and 6 * assigns final vaddrs. A relocatable output must preserve object-file 7 * structure and leave unresolved externals as relocatable symbol references. 8 */ 9 10 #include <string.h> 11 12 #include "core/buf.h" 13 #include "core/heap.h" 14 #include "core/pool.h" 15 #include "core/slice.h" 16 #include "core/vec.h" 17 #include "link/link.h" 18 #include "link/link_internal.h" 19 20 typedef struct RelObjSecMap { 21 ObjSecId out_sec; 22 u32 delta; 23 } RelObjSecMap; 24 25 typedef struct RelInputMap { 26 ObjSymId* sym; 27 u32 nsym; 28 RelObjSecMap* section; 29 u32 nsection; 30 } RelInputMap; 31 32 typedef struct RelGlobal { 33 Sym name; 34 u8 has_def; 35 u8 has_undef; 36 u8 undef_bind; 37 u8 pad0; 38 u32 def_input_idx; 39 ObjSymId def_sym; 40 u64 common_size; 41 u64 common_align; 42 ObjSymId out_sym; 43 } RelGlobal; 44 45 static u32 rel_symbol_count(ObjBuilder* ob) { 46 ObjSymIter* it; 47 ObjSymEntry e; 48 u32 n = 0; 49 it = obj_symiter_new(ob); 50 while (obj_symiter_next(it, &e)) ++n; 51 obj_symiter_free(it); 52 return n; 53 } 54 55 static const ObjSym* rel_input_sym(Linker* l, u32 input_idx, ObjSymId id) { 56 LinkInput* in; 57 if (input_idx >= LinkInputs_count(&l->inputs)) return NULL; 58 in = LinkInputs_at(&l->inputs, input_idx); 59 return in && in->obj ? obj_symbol_get(in->obj, id) : NULL; 60 } 61 62 static void rel_maps_free(Heap* h, RelInputMap* maps, u32 ninputs) { 63 u32 i; 64 if (!maps) return; 65 for (i = 0; i < ninputs; ++i) { 66 if (maps[i].sym) 67 h->free(h, maps[i].sym, sizeof(*maps[i].sym) * maps[i].nsym); 68 if (maps[i].section) 69 h->free(h, maps[i].section, sizeof(*maps[i].section) * maps[i].nsection); 70 } 71 h->free(h, maps, sizeof(*maps) * ninputs); 72 } 73 74 static void rel_globals_free(Heap* h, RelGlobal* globals, u32 cap, 75 SymHash* by_name) { 76 if (by_name) symhash_fini(by_name); 77 if (globals) h->free(h, globals, sizeof(*globals) * cap); 78 } 79 80 static RelGlobal* rel_global_for(Linker* l, RelGlobal** globals, u32* nglobals, 81 u32* cap, SymHash* by_name, Sym name) { 82 LinkSymId hit = symhash_get(by_name, name); 83 RelGlobal* g; 84 if (hit != LINK_SYM_NONE) return &(*globals)[hit - 1u]; 85 if (VEC_GROW(l->heap, *globals, *cap, *nglobals + 1u)) 86 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom on global symbols"); 87 g = &(*globals)[*nglobals]; 88 memset(g, 0, sizeof(*g)); 89 g->name = name; 90 (*nglobals)++; 91 symhash_set(by_name, name, (LinkSymId)*nglobals); 92 return g; 93 } 94 95 static void rel_record_global(Linker* l, RelGlobal** globals, u32* nglobals, 96 u32* cap, SymHash* by_name, u32 input_idx, 97 ObjSymId id, const ObjSym* s) { 98 RelGlobal* g; 99 if (!s || s->name == 0 || s->bind == SB_LOCAL) return; 100 if (link_sym_is_spurious_undef(s)) return; 101 g = rel_global_for(l, globals, nglobals, cap, by_name, s->name); 102 if (!link_sym_is_def(s)) { 103 if (!g->has_undef || 104 link_bind_strength(s->bind) > link_bind_strength(g->undef_bind)) { 105 g->undef_bind = (u8)s->bind; 106 } 107 g->has_undef = 1u; 108 return; 109 } 110 111 if (!g->has_def) { 112 g->has_def = 1u; 113 g->def_input_idx = input_idx; 114 g->def_sym = id; 115 if (s->kind == SK_COMMON) { 116 g->common_size = s->size; 117 g->common_align = s->common_align; 118 } 119 return; 120 } 121 122 { 123 const ObjSym* prev = rel_input_sym(l, g->def_input_idx, g->def_sym); 124 int old_strength = prev ? link_bind_strength(prev->bind) : 0; 125 int new_strength = link_bind_strength(s->bind); 126 if (prev && prev->kind == SK_COMMON && s->kind == SK_COMMON) { 127 if (s->size > g->common_size) g->common_size = s->size; 128 if (s->common_align > g->common_align) g->common_align = s->common_align; 129 if (new_strength > old_strength) { 130 g->def_input_idx = input_idx; 131 g->def_sym = id; 132 } 133 } else if (s->kind == SK_COMMON) { 134 return; 135 } else if (prev && prev->kind == SK_COMMON) { 136 g->def_input_idx = input_idx; 137 g->def_sym = id; 138 g->common_size = 0; 139 g->common_align = 0; 140 } else if (new_strength > old_strength) { 141 g->def_input_idx = input_idx; 142 g->def_sym = id; 143 } else if (new_strength == old_strength && 144 new_strength == link_bind_strength(SB_GLOBAL)) { 145 Slice nm_s = pool_slice(l->c->global, s->name); 146 const char* nm = nm_s.s; 147 size_t namelen = nm_s.len; 148 obj_format_demangle_c(l->c, &nm, &namelen); 149 compiler_panic(l->c, SRCLOC_NONE, 150 "link -r: duplicate definition of global symbol '%.*s'", 151 (int)namelen, nm); 152 } 153 } 154 } 155 156 static ObjSymId rel_copy_symbol(Linker* l, ObjBuilder* out, 157 const RelInputMap* maps, u32 input_idx, 158 const ObjSym* s, int force_common, 159 u64 common_size, u64 common_align) { 160 ObjSecId sec = OBJ_SEC_NONE; 161 u64 value = s->value; 162 u64 align = s->common_align; 163 SymBind bind = (SymBind)s->bind; 164 SymVis vis = (SymVis)s->vis; 165 ObjSymId id; 166 if (!force_common && s->section_id != OBJ_SEC_NONE && 167 s->section_id < maps[input_idx].nsection) { 168 const RelObjSecMap* sm = &maps[input_idx].section[s->section_id]; 169 sec = sm->out_sec; 170 value += sm->delta; 171 } 172 if (force_common) { 173 value = 0; 174 align = common_align; 175 } 176 if (link_sym_is_def(s) && (s->vis == SV_HIDDEN || s->vis == SV_INTERNAL)) { 177 bind = SB_LOCAL; 178 vis = SV_DEFAULT; 179 } 180 id = obj_symbol_ex(out, s->name, bind, vis, 181 force_common ? SK_COMMON : (SymKind)s->kind, sec, value, 182 force_common ? common_size : s->size, align); 183 if (id == OBJ_SYM_NONE) 184 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom copying symbol"); 185 if (s->flags) obj_symbol_set_flags(out, id, s->flags); 186 obj_sym_mark_referenced(out, id); 187 return id; 188 } 189 190 static ObjSymId rel_global_out(Linker* l, ObjBuilder* out, RelInputMap* maps, 191 RelGlobal* g) { 192 const ObjSym* s; 193 if (g->out_sym != OBJ_SYM_NONE) return g->out_sym; 194 if (g->has_def) { 195 s = rel_input_sym(l, g->def_input_idx, g->def_sym); 196 if (!s) compiler_panic(l->c, SRCLOC_NONE, "link -r: bad global symbol map"); 197 g->out_sym = 198 rel_copy_symbol(l, out, maps, g->def_input_idx, s, s->kind == SK_COMMON, 199 g->common_size, g->common_align); 200 } else { 201 ObjSymId id; 202 id = obj_symbol(out, g->name, 203 g->has_undef ? (SymBind)g->undef_bind : SB_GLOBAL, SK_UNDEF, 204 OBJ_SEC_NONE, 0, 0); 205 if (id == OBJ_SYM_NONE) 206 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom creating undef symbol"); 207 obj_sym_mark_referenced(out, id); 208 g->out_sym = id; 209 } 210 return g->out_sym; 211 } 212 213 static int rel_sections_compatible(const Section* a, const Section* b) { 214 if (!a || !b) return 0; 215 if (a->group_id != OBJ_GROUP_NONE || b->group_id != OBJ_GROUP_NONE) return 0; 216 if (a->link != OBJ_SEC_NONE || b->link != OBJ_SEC_NONE) return 0; 217 if (a->info || b->info) return 0; 218 return a->name == b->name && a->kind == b->kind && a->sem == b->sem && 219 a->flags == b->flags && a->ext_kind == b->ext_kind && 220 a->ext_type == b->ext_type && a->ext_flags == b->ext_flags && 221 a->entsize == b->entsize; 222 } 223 224 static ObjSecId rel_find_compatible_section(ObjBuilder* out, 225 const Section* src) { 226 u32 nsec = obj_section_count(out); 227 for (u32 i = 1; i < nsec; ++i) { 228 const Section* dst = obj_section_get(out, (ObjSecId)i); 229 if (rel_sections_compatible(dst, src)) return (ObjSecId)i; 230 } 231 return OBJ_SEC_NONE; 232 } 233 234 static void rel_copy_sections(Linker* l, ObjBuilder* out, RelInputMap* maps, 235 u32 ninputs) { 236 u32 ii, j; 237 int have_eflags = 0; 238 u32 eflags = 0; 239 for (ii = 0; ii < ninputs; ++ii) { 240 LinkInput* in = LinkInputs_at(&l->inputs, ii); 241 ObjBuilder* ob = in->obj; 242 u32 nsec; 243 u32 in_eflags; 244 if (in->kind == LINK_INPUT_DSO_BYTES) 245 compiler_panic(l->c, SRCLOC_NONE, "link -r: DSO inputs are not supported"); 246 if (!ob) continue; 247 if (obj_get_elf_e_flags(ob, &in_eflags)) { 248 if (!have_eflags) { 249 eflags = in_eflags; 250 have_eflags = 1; 251 } else if (eflags != in_eflags) { 252 compiler_panic(l->c, SRCLOC_NONE, "link -r: incompatible ELF e_flags"); 253 } 254 } 255 nsec = obj_section_count(ob); 256 maps[ii].nsection = nsec; 257 maps[ii].section = (RelObjSecMap*)l->heap->alloc( 258 l->heap, sizeof(*maps[ii].section) * nsec, _Alignof(RelObjSecMap)); 259 if (!maps[ii].section) 260 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom on section map"); 261 memset(maps[ii].section, 0, sizeof(*maps[ii].section) * nsec); 262 for (j = 1; j < nsec; ++j) { 263 const Section* s = obj_section_get(ob, (ObjSecId)j); 264 ObjSecId out_sec; 265 u32 delta; 266 if (!s) continue; 267 out_sec = rel_find_compatible_section(out, s); 268 if (out_sec == OBJ_SEC_NONE) { 269 out_sec = obj_section_ex(out, s->name, (SecKind)s->kind, (SecSem)s->sem, 270 s->flags, s->align, s->entsize, OBJ_SEC_NONE, 271 s->info); 272 if (out_sec == OBJ_SEC_NONE) 273 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom copying section"); 274 if (s->ext_kind != OBJ_EXT_NONE || s->ext_type || s->ext_flags) 275 obj_section_set_ext(out, out_sec, (ObjExtKind)s->ext_kind, 276 s->ext_type, s->ext_flags); 277 } 278 delta = obj_align_to(out, out_sec, s->align); 279 if (s->sem == SSEM_NOBITS || s->kind == SEC_BSS) { 280 obj_reserve_bss(out, out_sec, delta + s->bss_size, s->align); 281 } else if (s->bytes.total) { 282 u8* flat = (u8*)l->heap->alloc(l->heap, s->bytes.total, 1u); 283 if (!flat) 284 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom copying section bytes"); 285 buf_flatten(&s->bytes, flat); 286 obj_write(out, out_sec, flat, s->bytes.total); 287 l->heap->free(l->heap, flat, s->bytes.total); 288 } 289 maps[ii].section[j].out_sec = out_sec; 290 maps[ii].section[j].delta = delta; 291 } 292 } 293 if (have_eflags) obj_set_elf_e_flags(out, eflags); 294 295 for (ii = 0; ii < ninputs; ++ii) { 296 LinkInput* in = LinkInputs_at(&l->inputs, ii); 297 ObjBuilder* ob = in->obj; 298 if (!ob) continue; 299 for (j = 1; j < maps[ii].nsection; ++j) { 300 const Section* s = obj_section_get(ob, (ObjSecId)j); 301 ObjSecId link = OBJ_SEC_NONE; 302 ObjSecId out_sec = maps[ii].section[j].out_sec; 303 if (!s || out_sec == OBJ_SEC_NONE) continue; 304 if (s->link != OBJ_SEC_NONE && s->link < maps[ii].nsection) 305 link = maps[ii].section[s->link].out_sec; 306 obj_section_set_link_info(out, out_sec, link, s->info); 307 } 308 } 309 } 310 311 static void rel_scan_globals(Linker* l, RelGlobal** globals, u32* nglobals, 312 u32* cap, SymHash* by_name) { 313 u32 ii; 314 for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) { 315 LinkInput* in = LinkInputs_at(&l->inputs, ii); 316 ObjSymIter* it; 317 ObjSymEntry e; 318 if (!in->obj || in->kind == LINK_INPUT_DSO_BYTES) continue; 319 it = obj_symiter_new(in->obj); 320 while (obj_symiter_next(it, &e)) 321 rel_record_global(l, globals, nglobals, cap, by_name, ii, e.id, e.sym); 322 obj_symiter_free(it); 323 } 324 } 325 326 static void rel_copy_symbols(Linker* l, ObjBuilder* out, RelInputMap* maps, 327 SymHash* globals_by_name, RelGlobal* globals) { 328 u32 ii; 329 for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) { 330 LinkInput* in = LinkInputs_at(&l->inputs, ii); 331 ObjSymIter* it; 332 ObjSymEntry e; 333 u32 nsym; 334 if (!in->obj || in->kind == LINK_INPUT_DSO_BYTES) continue; 335 nsym = rel_symbol_count(in->obj) + 1u; 336 maps[ii].nsym = nsym; 337 maps[ii].sym = (ObjSymId*)l->heap->alloc( 338 l->heap, sizeof(*maps[ii].sym) * nsym, _Alignof(ObjSymId)); 339 if (!maps[ii].sym) 340 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom on symbol map"); 341 memset(maps[ii].sym, 0, sizeof(*maps[ii].sym) * nsym); 342 it = obj_symiter_new(in->obj); 343 while (obj_symiter_next(it, &e)) { 344 const ObjSym* s = e.sym; 345 if (e.id >= nsym) continue; 346 if (link_sym_is_spurious_undef(s)) continue; 347 if (s->name != 0 && s->bind != SB_LOCAL) { 348 LinkSymId rec_idx = symhash_get(globals_by_name, s->name); 349 if (rec_idx != LINK_SYM_NONE) 350 maps[ii].sym[e.id] = 351 rel_global_out(l, out, maps, &globals[rec_idx - 1u]); 352 } else { 353 maps[ii].sym[e.id] = rel_copy_symbol(l, out, maps, ii, s, 0, 0, 0); 354 } 355 } 356 obj_symiter_free(it); 357 } 358 } 359 360 static void rel_copy_groups(Linker* l, ObjBuilder* out, RelInputMap* maps) { 361 u32 ii, gi, j; 362 for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) { 363 LinkInput* in = LinkInputs_at(&l->inputs, ii); 364 ObjBuilder* ob = in->obj; 365 if (!ob || in->kind == LINK_INPUT_DSO_BYTES) continue; 366 for (gi = 1; gi < obj_group_count(ob); ++gi) { 367 const ObjGroup* g = obj_group_get(ob, (ObjGroupId)gi); 368 ObjSymId sig = OBJ_SYM_NONE; 369 ObjGroupId out_gid; 370 if (!g) continue; 371 if (g->signature != OBJ_SYM_NONE && g->signature < maps[ii].nsym) 372 sig = maps[ii].sym[g->signature]; 373 out_gid = obj_group(out, g->name, sig, g->flags); 374 if (out_gid == OBJ_GROUP_NONE) 375 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom copying group"); 376 for (j = 0; j < g->nsections; ++j) { 377 ObjSecId in_sec = g->sections[j]; 378 ObjSecId out_sec = OBJ_SEC_NONE; 379 if (in_sec != OBJ_SEC_NONE && in_sec < maps[ii].nsection) 380 out_sec = maps[ii].section[in_sec].out_sec; 381 if (out_sec != OBJ_SEC_NONE) { 382 obj_group_add_section(out, out_gid, out_sec); 383 obj_section_set_group(out, out_sec, out_gid); 384 } 385 } 386 } 387 } 388 } 389 390 static void rel_copy_relocs(Linker* l, ObjBuilder* out, RelInputMap* maps) { 391 u32 ii, ri; 392 for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) { 393 LinkInput* in = LinkInputs_at(&l->inputs, ii); 394 ObjBuilder* ob = in->obj; 395 u32 total; 396 if (!ob || in->kind == LINK_INPUT_DSO_BYTES) continue; 397 total = obj_reloc_total(ob); 398 for (ri = 0; ri < total; ++ri) { 399 const Reloc* r = obj_reloc_at(ob, ri); 400 ObjSecId out_sec; 401 ObjSymId out_sym = OBJ_SYM_NONE; 402 u32 out_off; 403 if (!r || r->section_id == OBJ_SEC_NONE || 404 r->section_id >= maps[ii].nsection) 405 continue; 406 out_sec = maps[ii].section[r->section_id].out_sec; 407 if (out_sec == OBJ_SEC_NONE) continue; 408 if (r->sym != OBJ_SYM_NONE && r->sym < maps[ii].nsym) 409 out_sym = maps[ii].sym[r->sym]; 410 out_off = r->offset + maps[ii].section[r->section_id].delta; 411 obj_reloc_ex(out, out_sec, out_off, (RelocKind)r->kind, out_sym, 412 r->addend, r->has_explicit_addend, r->pair); 413 } 414 } 415 } 416 417 static void rel_obj_cleanup(void* arg) { obj_free((ObjBuilder*)arg); } 418 419 void link_emit_relocatable_writer(Linker* l, Writer* w) { 420 Heap* h; 421 ObjBuilder* out; 422 CompilerCleanup* cleanup; 423 RelInputMap* maps; 424 u32 ninputs; 425 RelGlobal* globals = NULL; 426 u32 nglobals = 0, globals_cap = 0; 427 SymHash globals_by_name; 428 429 if (!l || !w) return; 430 h = l->heap; 431 432 if (l->script) 433 compiler_panic(l->c, SRCLOC_NONE, "link -r: linker scripts are not supported"); 434 435 link_ingest_archives(l); 436 ninputs = LinkInputs_count(&l->inputs); 437 maps = ninputs ? (RelInputMap*)h->alloc(h, sizeof(*maps) * ninputs, 438 _Alignof(RelInputMap)) 439 : NULL; 440 if (ninputs && !maps) 441 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom on input maps"); 442 if (ninputs) memset(maps, 0, sizeof(*maps) * ninputs); 443 444 out = obj_new(l->c); 445 if (!out) compiler_panic(l->c, SRCLOC_NONE, "link -r: obj_new failed"); 446 cleanup = compiler_defer(l->c, rel_obj_cleanup, out); 447 448 symhash_init(&globals_by_name, h); 449 rel_copy_sections(l, out, maps, ninputs); 450 rel_scan_globals(l, &globals, &nglobals, &globals_cap, &globals_by_name); 451 rel_copy_symbols(l, out, maps, &globals_by_name, globals); 452 rel_copy_groups(l, out, maps); 453 rel_copy_relocs(l, out, maps); 454 455 obj_finalize(out); 456 kit_obj_builder_emit(out, w); 457 458 if (cleanup) compiler_undefer(l->c, cleanup); 459 obj_free(out); 460 rel_globals_free(h, globals, globals_cap, &globals_by_name); 461 rel_maps_free(h, maps, ninputs); 462 }