link_relocatable.c (16331B)
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 if (s->atom_subordinate) obj_symbol_set_atom_subordinate(out, id, 1); 187 obj_sym_mark_referenced(out, id); 188 return id; 189 } 190 191 static ObjSymId rel_global_out(Linker* l, ObjBuilder* out, RelInputMap* maps, 192 RelGlobal* g) { 193 const ObjSym* s; 194 if (g->out_sym != OBJ_SYM_NONE) return g->out_sym; 195 if (g->has_def) { 196 s = rel_input_sym(l, g->def_input_idx, g->def_sym); 197 if (!s) compiler_panic(l->c, SRCLOC_NONE, "link -r: bad global symbol map"); 198 g->out_sym = 199 rel_copy_symbol(l, out, maps, g->def_input_idx, s, s->kind == SK_COMMON, 200 g->common_size, g->common_align); 201 } else { 202 ObjSymId id; 203 id = obj_symbol(out, g->name, 204 g->has_undef ? (SymBind)g->undef_bind : SB_GLOBAL, SK_UNDEF, 205 OBJ_SEC_NONE, 0, 0); 206 if (id == OBJ_SYM_NONE) 207 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom creating undef symbol"); 208 obj_sym_mark_referenced(out, id); 209 g->out_sym = id; 210 } 211 return g->out_sym; 212 } 213 214 static int rel_sections_compatible(const Section* a, const Section* b) { 215 if (!a || !b) return 0; 216 if (a->group_id != OBJ_GROUP_NONE || b->group_id != OBJ_GROUP_NONE) return 0; 217 if (a->link != OBJ_SEC_NONE || b->link != OBJ_SEC_NONE) return 0; 218 if (a->info || b->info) return 0; 219 return a->name == b->name && a->kind == b->kind && a->sem == b->sem && 220 a->flags == b->flags && a->ext_kind == b->ext_kind && 221 a->ext_type == b->ext_type && a->ext_flags == b->ext_flags && 222 a->entsize == b->entsize; 223 } 224 225 static ObjSecId rel_find_compatible_section(ObjBuilder* out, 226 const Section* src) { 227 u32 nsec = obj_section_count(out); 228 for (u32 i = 1; i < nsec; ++i) { 229 const Section* dst = obj_section_get(out, (ObjSecId)i); 230 if (rel_sections_compatible(dst, src)) return (ObjSecId)i; 231 } 232 return OBJ_SEC_NONE; 233 } 234 235 static void rel_copy_sections(Linker* l, ObjBuilder* out, RelInputMap* maps, 236 u32 ninputs) { 237 u32 ii, j; 238 for (ii = 0; ii < ninputs; ++ii) { 239 LinkInput* in = LinkInputs_at(&l->inputs, ii); 240 ObjBuilder* ob = in->obj; 241 u32 nsec; 242 if (in->kind == LINK_INPUT_DSO_BYTES) 243 compiler_panic(l->c, SRCLOC_NONE, 244 "link -r: DSO inputs are not supported"); 245 if (!ob) continue; 246 nsec = obj_section_count(ob); 247 maps[ii].nsection = nsec; 248 maps[ii].section = (RelObjSecMap*)l->heap->alloc( 249 l->heap, sizeof(*maps[ii].section) * nsec, _Alignof(RelObjSecMap)); 250 if (!maps[ii].section) 251 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom on section map"); 252 memset(maps[ii].section, 0, sizeof(*maps[ii].section) * nsec); 253 for (j = 1; j < nsec; ++j) { 254 const Section* s = obj_section_get(ob, (ObjSecId)j); 255 ObjSecId out_sec; 256 u32 delta; 257 if (!s) continue; 258 out_sec = rel_find_compatible_section(out, s); 259 if (out_sec == OBJ_SEC_NONE) { 260 out_sec = obj_section_ex(out, s->name, (SecKind)s->kind, (SecSem)s->sem, 261 s->flags, s->align, s->entsize, OBJ_SEC_NONE, 262 s->info); 263 if (out_sec == OBJ_SEC_NONE) 264 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom copying section"); 265 if (s->ext_kind != OBJ_EXT_NONE || s->ext_type || s->ext_flags) 266 obj_section_set_ext(out, out_sec, (ObjExtKind)s->ext_kind, 267 s->ext_type, s->ext_flags); 268 } 269 delta = obj_align_to(out, out_sec, s->align); 270 if (s->sem == SSEM_NOBITS || s->kind == SEC_BSS) { 271 obj_reserve_bss(out, out_sec, delta + s->bss_size, s->align); 272 } else if (s->bytes.total) { 273 u8* flat = (u8*)l->heap->alloc(l->heap, s->bytes.total, 1u); 274 if (!flat) 275 compiler_panic(l->c, SRCLOC_NONE, 276 "link -r: oom copying section bytes"); 277 buf_flatten(&s->bytes, flat); 278 obj_write(out, out_sec, flat, s->bytes.total); 279 l->heap->free(l->heap, flat, s->bytes.total); 280 } 281 maps[ii].section[j].out_sec = out_sec; 282 maps[ii].section[j].delta = delta; 283 } 284 } 285 if (l->have_elf_e_flags) obj_set_elf_e_flags(out, l->elf_e_flags); 286 287 for (ii = 0; ii < ninputs; ++ii) { 288 LinkInput* in = LinkInputs_at(&l->inputs, ii); 289 ObjBuilder* ob = in->obj; 290 if (!ob) continue; 291 for (j = 1; j < maps[ii].nsection; ++j) { 292 const Section* s = obj_section_get(ob, (ObjSecId)j); 293 ObjSecId link = OBJ_SEC_NONE; 294 ObjSecId out_sec = maps[ii].section[j].out_sec; 295 if (!s || out_sec == OBJ_SEC_NONE) continue; 296 if (s->link != OBJ_SEC_NONE && s->link < maps[ii].nsection) 297 link = maps[ii].section[s->link].out_sec; 298 obj_section_set_link_info(out, out_sec, link, s->info); 299 } 300 } 301 } 302 303 static void rel_scan_globals(Linker* l, RelGlobal** globals, u32* nglobals, 304 u32* cap, SymHash* by_name) { 305 u32 ii; 306 for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) { 307 LinkInput* in = LinkInputs_at(&l->inputs, ii); 308 ObjSymIter* it; 309 ObjSymEntry e; 310 if (!in->obj || in->kind == LINK_INPUT_DSO_BYTES) continue; 311 it = obj_symiter_new(in->obj); 312 while (obj_symiter_next(it, &e)) 313 rel_record_global(l, globals, nglobals, cap, by_name, ii, e.id, e.sym); 314 obj_symiter_free(it); 315 } 316 } 317 318 static void rel_copy_symbols(Linker* l, ObjBuilder* out, RelInputMap* maps, 319 SymHash* globals_by_name, RelGlobal* globals) { 320 u32 ii; 321 for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) { 322 LinkInput* in = LinkInputs_at(&l->inputs, ii); 323 ObjSymIter* it; 324 ObjSymEntry e; 325 u32 nsym; 326 if (!in->obj || in->kind == LINK_INPUT_DSO_BYTES) continue; 327 nsym = rel_symbol_count(in->obj) + 1u; 328 maps[ii].nsym = nsym; 329 maps[ii].sym = (ObjSymId*)l->heap->alloc( 330 l->heap, sizeof(*maps[ii].sym) * nsym, _Alignof(ObjSymId)); 331 if (!maps[ii].sym) 332 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom on symbol map"); 333 memset(maps[ii].sym, 0, sizeof(*maps[ii].sym) * nsym); 334 it = obj_symiter_new(in->obj); 335 while (obj_symiter_next(it, &e)) { 336 const ObjSym* s = e.sym; 337 if (e.id >= nsym) continue; 338 if (link_sym_is_spurious_undef(s)) continue; 339 if (s->name != 0 && s->bind != SB_LOCAL) { 340 LinkSymId rec_idx = symhash_get(globals_by_name, s->name); 341 if (rec_idx != LINK_SYM_NONE) 342 maps[ii].sym[e.id] = 343 rel_global_out(l, out, maps, &globals[rec_idx - 1u]); 344 } else { 345 maps[ii].sym[e.id] = rel_copy_symbol(l, out, maps, ii, s, 0, 0, 0); 346 } 347 } 348 obj_symiter_free(it); 349 } 350 } 351 352 static void rel_copy_groups(Linker* l, ObjBuilder* out, RelInputMap* maps) { 353 u32 ii, gi, j; 354 for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) { 355 LinkInput* in = LinkInputs_at(&l->inputs, ii); 356 ObjBuilder* ob = in->obj; 357 if (!ob || in->kind == LINK_INPUT_DSO_BYTES) continue; 358 for (gi = 1; gi < obj_group_count(ob); ++gi) { 359 const ObjGroup* g = obj_group_get(ob, (ObjGroupId)gi); 360 ObjSymId sig = OBJ_SYM_NONE; 361 ObjGroupId out_gid; 362 if (!g) continue; 363 if (g->signature != OBJ_SYM_NONE && g->signature < maps[ii].nsym) 364 sig = maps[ii].sym[g->signature]; 365 out_gid = obj_group(out, g->name, sig, g->flags); 366 if (out_gid == OBJ_GROUP_NONE) 367 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom copying group"); 368 for (j = 0; j < g->nsections; ++j) { 369 ObjSecId in_sec = g->sections[j]; 370 ObjSecId out_sec = OBJ_SEC_NONE; 371 if (in_sec != OBJ_SEC_NONE && in_sec < maps[ii].nsection) 372 out_sec = maps[ii].section[in_sec].out_sec; 373 if (out_sec != OBJ_SEC_NONE) { 374 obj_group_add_section(out, out_gid, out_sec); 375 obj_section_set_group(out, out_sec, out_gid); 376 } 377 } 378 } 379 } 380 } 381 382 static void rel_copy_relocs(Linker* l, ObjBuilder* out, RelInputMap* maps) { 383 u32 ii, ri; 384 for (ii = 0; ii < LinkInputs_count(&l->inputs); ++ii) { 385 LinkInput* in = LinkInputs_at(&l->inputs, ii); 386 ObjBuilder* ob = in->obj; 387 u32 total; 388 if (!ob || in->kind == LINK_INPUT_DSO_BYTES) continue; 389 total = obj_reloc_total(ob); 390 for (ri = 0; ri < total; ++ri) { 391 const Reloc* r = obj_reloc_at(ob, ri); 392 ObjSecId out_sec; 393 ObjSymId out_sym = OBJ_SYM_NONE; 394 u32 out_off; 395 if (!r || r->section_id == OBJ_SEC_NONE || 396 r->section_id >= maps[ii].nsection) 397 continue; 398 out_sec = maps[ii].section[r->section_id].out_sec; 399 if (out_sec == OBJ_SEC_NONE) continue; 400 if (r->sym != OBJ_SYM_NONE && r->sym < maps[ii].nsym) 401 out_sym = maps[ii].sym[r->sym]; 402 out_off = r->offset + maps[ii].section[r->section_id].delta; 403 obj_reloc_ex(out, out_sec, out_off, (RelocKind)r->kind, out_sym, 404 r->addend, r->has_explicit_addend, r->pair); 405 } 406 } 407 } 408 409 static void rel_obj_cleanup(void* arg) { obj_free((ObjBuilder*)arg); } 410 411 void link_emit_relocatable_writer(Linker* l, Writer* w) { 412 Heap* h; 413 ObjBuilder* out; 414 CompilerCleanup* cleanup; 415 RelInputMap* maps; 416 u32 ninputs; 417 RelGlobal* globals = NULL; 418 u32 nglobals = 0, globals_cap = 0; 419 SymHash globals_by_name; 420 421 if (!l || !w) return; 422 h = l->heap; 423 424 if (l->script) 425 compiler_panic(l->c, SRCLOC_NONE, 426 "link -r: linker scripts are not supported"); 427 428 link_ingest_archives(l); 429 ninputs = LinkInputs_count(&l->inputs); 430 maps = ninputs ? (RelInputMap*)h->alloc(h, sizeof(*maps) * ninputs, 431 _Alignof(RelInputMap)) 432 : NULL; 433 if (ninputs && !maps) 434 compiler_panic(l->c, SRCLOC_NONE, "link -r: oom on input maps"); 435 if (ninputs) memset(maps, 0, sizeof(*maps) * ninputs); 436 437 out = obj_new(l->c); 438 if (!out) compiler_panic(l->c, SRCLOC_NONE, "link -r: obj_new failed"); 439 cleanup = compiler_defer(l->c, rel_obj_cleanup, out); 440 441 symhash_init(&globals_by_name, h); 442 rel_copy_sections(l, out, maps, ninputs); 443 rel_scan_globals(l, &globals, &nglobals, &globals_cap, &globals_by_name); 444 rel_copy_symbols(l, out, maps, &globals_by_name, globals); 445 rel_copy_groups(l, out, maps); 446 rel_copy_relocs(l, out, maps); 447 448 obj_finalize(out); 449 kit_obj_builder_emit(out, w); 450 451 if (cleanup) compiler_undefer(l->c, cleanup); 452 obj_free(out); 453 rel_globals_free(h, globals, globals_cap, &globals_by_name); 454 rel_maps_free(h, maps, ninputs); 455 }