mold源码阅读 其三 符号决议
Homura 我摸到了!

Untitled

pixiv:72272420

前面两期将读取输入的部分全部讲完了,本期开始涉及链接过程中的处理。在讲主要的符号决议之前,先讲一下mold在符号决议执行之前做的一些其他处理。

dso uniquely

在读取完输入后首先做的是将shared object根据soname进行去重,因此我们可以在链接的过程中链接多个相同soname的库而不会产生冲突。

elf/main.cc

1
2
3
4
5
6
{
std::unordered_set<std::string_view> seen;
std::erase_if(ctx.dsos, [&](SharedFile<E> *file) {
return !seen.insert(file->soname).second;
});
}

apply_exclude_libs

elf/passes.cc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename E>
void apply_exclude_libs(Context<E> &ctx) {
Timer t(ctx, "apply_exclude_libs");

if (ctx.arg.exclude_libs.empty())
return;

std::unordered_set<std::string_view> set(ctx.arg.exclude_libs.begin(),
ctx.arg.exclude_libs.end());

for (ObjectFile<E> *file : ctx.objs) {
if (!file->archive_name.empty())
if (set.contains("ALL") ||
set.contains(filepath(file->archive_name).filename().string()))
file->exclude_libs = true;
}
}

这里就是简单将所有包含在exclude-libs里的lib名字对应的exclude_libs设置为true,而这个设置在后面符号决议的过程会用到。

exclude_libs是命令行中获取的

1
2
3
else if (read_arg("exclude-libs")) {
append(ctx.arg.exclude_libs, split_by_comma_or_colon(arg));
}

create_internal_file

internal file是什么

内部的文件,用来保存linker-synthesized符号。linker-synthesized符号或许也可以理解为编译产物中不存在的符号。作为一个并不实际存在的文件,依然会作为一个普通的ObjFile加入到obj_pool中,主要用途是在create_output_sections以后来add_synthetic_symbol,与之相关联的有一个internal_esyms,里面都是具体相关的符号。

实现

在main函数中调用是这样的

1
2
if (!ctx.arg.relocatable)
create_internal_file(ctx);

elf/passes.cc

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename E>
void create_internal_file(Context<E> &ctx) {
ObjectFile<E> *obj = new ObjectFile<E>;
ctx.obj_pool.emplace_back(obj);
ctx.internal_obj = obj;
ctx.objs.push_back(obj);

ctx.internal_esyms.resize(1);

obj->symbols.push_back(new Symbol<E>);
obj->first_global = 1;
obj->is_alive = true;
obj->priority = 1;

首先创建了基本的ObjectFile对象并且进行了一些初始化的处理。

之后添加从命令行参数中读取的–defsym里的所有的defsym

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (i64 i = 0; i < ctx.arg.defsyms.size(); i++) {
std::pair<Symbol<E> *, std::variant<Symbol<E> *, u64>> &defsym = ctx.arg.defsyms[i];
add(defsym.first);

if (std::holds_alternative<Symbol<E> *>(defsym.second)) {
// Add an undefined symbol to keep a reference to the defsym target.
// This prevents elimination by e.g. LTO or gc-sections.
// The undefined symbol will never make to the final object file; we
// double-check that the defsym target is not undefined in
// fix_synthetic_symbols.
auto sym = std::get<Symbol<E> *>(defsym.second);
add_undef(sym);
}
}

处理完defsym后再从命令行参数中读取的SectionOrder的符号

1
2
3
for (SectionOrder &ord : ctx.arg.section_order)
if (ord.type == SectionOrder::SYMBOL)
add(get_symbol(ctx, ord.name));

关于SectionOrder的定义

1
2
3
4
5
struct SectionOrder {
enum { NONE, SECTION, GROUP, ADDR, ALIGN, SYMBOL } type = NONE;
std::string name;
u64 value = 0;
};

最后设置obj类的一些参数

1
2
obj->elf_syms = ctx.internal_esyms;
obj->symvers.resize(ctx.internal_esyms.size() - 1);

defsym

关于前面提到的defsym,我们来看一下mold的测试代码一部分来理解其作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cat <<EOF | $CC -fPIC -o $t/a.o -c -xc -
#include <stdio.h>
extern char foo;
extern char bar;
void baz();

void print() {
printf("Hello %p %p\n", &foo, &bar);
}

int main() {
baz();
}
EOF

$CC -B. -o $t/exe $t/a.o -pie -Wl,-defsym=foo=16 \
-Wl,-defsym=bar=0x2000 -Wl,-defsym=baz=print

$QEMU $t/exe | grep -q '^Hello 0x10 0x2000$'

通过defsym指定了符号名以及其实现的位置,尽管对应的符号在代码中并没有实现。

关于这里的add和add_undef的实现

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
auto add = [&](Symbol<E> *sym) {
obj->symbols.push_back(sym);

// An actual value will be set to a linker-synthesized symbol by
// fix_synthetic_symbols(). Until then, `value` doesn't have a valid
// value. 0xdeadbeef is a unique dummy value to make debugging easier
// if the field is accidentally used before it gets a valid one.
sym->value = 0xdeadbeef;

ElfSym<E> esym;
memset(&esym, 0, sizeof(esym));
esym.st_type = STT_NOTYPE;
esym.st_shndx = SHN_ABS;
esym.st_bind = STB_GLOBAL;
esym.st_visibility = STV_DEFAULT;
ctx.internal_esyms.push_back(esym);
};

auto add_undef = [&](Symbol<E> *sym) {
obj->symbols.push_back(sym);
sym->value = 0xdeadbeef;

ElfSym<E> esym;
memset(&esym, 0, sizeof(esym));
esym.st_type = STT_NOTYPE;
esym.st_shndx = SHN_UNDEF;
esym.st_bind = STB_GLOBAL;
esym.st_visibility = STV_DEFAULT;
ctx.internal_esyms.push_back(esym);
};

通过add和add_undef函数把defsym指定的符号添加到symbols中,并且设定为了特殊值,关联到了一个esym里。主要的差别就在于st_shndx被设置为了不同的值。

符号决议

接下来是链接过程中比较重要的一个环节,符号决议(symbol resolve)

在mold中,这个部分做了四件事情

  1. 检测所有需要使用的objet files
  2. 移除重复的COMDAT段
  3. 进行符号决议的过程。在多个不同的esym中选择出一个更高priority的关联到sym中
  4. LTO的处理,处理后再次执行决议

resolve_symbols

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename E>
void resolve_symbols(Context<E> &ctx) {
Timer t(ctx, "resolve_symbols");

std::vector<ObjectFile<E> *> objs = ctx.objs;
std::vector<SharedFile<E> *> dsos = ctx.dsos;

do_resolve_symbols(ctx);

if (ctx.has_lto_object) {
...
do_resolve_symbols(ctx);
}
}

这里先省略lto相关的具体处理,很多处理和do_resolve_symbols中是类似的,因此放到后面再说。

1
2
3
4
5
6
7
8
9
10
template <typename E>
void do_resolve_symbols(Context<E> &ctx) {
auto for_each_file = [&](std::function<void(InputFile<E> *)> fn) {
tbb::parallel_for_each(ctx.objs, fn);
tbb::parallel_for_each(ctx.dsos, fn);
};
// 1. 检测object files
// 2. 消除重复COMDAT
// 3. 符号决议
}

1. 检测object files

archive extraction: .a成员只会在满足非archive object文件未定义符号之一的情况下才会被包含在最终的二进制文件中

链接时为了满足archive extraction的规则,mold采取的策略是:

  1. 初步resolve:假设全部include,match undef符号
  2. mark sweep消除无需使用的archive成员
  3. 删除掉非archive成员

下面是具体的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
{
Timer t(ctx, "extract_archive_members");

// Register symbols
for_each_file([&](InputFile<E> *file) { file->resolve_symbols(ctx); });

// Mark reachable objects to decide which files to include into an output.
// This also merges symbol visibility.
mark_live_objects(ctx);

// Cleanup. The rule used for archive extraction isn't accurate for the
// general case of symbol extraction, so reset the resolution to be redone
// later.
for_each_file([](InputFile<E> *file) { file->clear_symbols(); });

// Now that the symbol references are gone, remove the eliminated files from
// the file list.
std::erase_if(ctx.objs, [](InputFile<E> *file) { return !file->is_alive; });
std::erase_if(ctx.dsos, [](InputFile<E> *file) { return !file->is_alive; });
}
  1. for_each_file针对objs和dsos处理resolve,mark live,clear,erase file
  2. 标记所有可访问的输出到文件的object,之后合并可见性
  3. 清除file的symbols
  4. 最后清除掉objs和dsos中非alive的file
1
2
3
4
5
6
7
template <typename E>
__attribute__((no_sanitize("thread")))
void InputFile<E>::clear_symbols() {
for (Symbol<E> *sym : get_global_syms())
if (sym->file == this)
sym->clear();
}

mark_live_objects

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
template <typename E>
static void mark_live_objects(Context<E> &ctx) {
auto mark_symbol = [&](std::string_view name) {
if (InputFile<E> *file = get_symbol(ctx, name)->file)
file->is_alive = true;
};

for (std::string_view name : ctx.arg.undefined)
mark_symbol(name);
for (std::string_view name : ctx.arg.require_defined)
mark_symbol(name);

std::vector<InputFile<E> *> roots;

for (InputFile<E> *file : ctx.objs)
if (file->is_alive)
roots.push_back(file);

for (InputFile<E> *file : ctx.dsos)
if (file->is_alive)
roots.push_back(file);

tbb::parallel_for_each(roots, [&](InputFile<E> *file,
tbb::feeder<InputFile<E> *> &feeder) {
if (file->is_alive)
file->mark_live_objects(ctx, [&](InputFile<E> *obj) { feeder.add(obj); });
});
}

首先对所有参数中传入的undef以及require_define的符号所关联的文件进行mark,之后遍历所有alive的obj和dso,加入到root中,之后再进行mark_live_objects。部分文件会因为特殊的链接选项,比如说whole-archive会影响是否设置为is_alive,这部分会之后再以这个为主题单独讲一篇。

对于ObjectFile和SharedFile的mark方式也是不同的。

ObjectFile::mark_live_objects

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
template <typename E>
void
ObjectFile<E>::mark_live_objects(Context<E> &ctx,
std::function<void(InputFile<E> *)> feeder) {
assert(this->is_alive);

for (i64 i = this->first_global; i < this->elf_syms.size(); i++) {
const ElfSym<E> &esym = this->elf_syms[i];
Symbol<E> &sym = *this->symbols[i];

if (!esym.is_undef() && exclude_libs)
merge_visibility(ctx, sym, STV_HIDDEN);
else
merge_visibility(ctx, sym, esym.st_visibility);

if (sym.traced)
print_trace_symbol(ctx, *this, esym, sym);

if (esym.is_weak())
continue;

if (!sym.file)
continue;

bool keep = esym.is_undef() || (esym.is_common() && !sym.esym().is_common());
if (keep && fast_mark(sym.file->is_alive)) {
feeder(sym.file);

if (sym.traced)
SyncOut(ctx) << "trace-symbol: " << *this << " keeps " << *sym.file
<< " for " << sym;
}
}
}

针对所有global的符号进行处理。

  1. 首先对esym进行merge_visibility,对于存在定义的exclude_libs的符号来说是HIDDEN的,关于这一点在命令行参数处有说明。

    -exclude-libs LIB,LIB,.. Mark all symbols in given libraries hidden

  2. 跳过弱符号以及文件不存在的符号。

  3. keep并且fast_mark成功的符号加入到root中。

keep这里需要是undef的情况,我认为是因为如果esym存在定义,那么定义就是存在于当前的ObjectFile中,也就不需要再重复加入到root中了。common我想同样是因为这种情况下所在的文件已经加入到root中了。

关于merge_visibility

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename E>
void ObjectFile<E>::merge_visibility(Context<E> &ctx, Symbol<E> &sym,
u8 visibility) {
// Canonicalize visibility
if (visibility == STV_INTERNAL)
visibility = STV_HIDDEN;

auto priority = [&](u8 visibility) {
switch (visibility) {
case STV_HIDDEN:
return 1;
case STV_PROTECTED:
return 2;
case STV_DEFAULT:
return 3;
}
Fatal(ctx) << *this << ": unknown symbol visibility: " << sym;
};

update_minimum(sym.visibility, visibility, [&](u8 a, u8 b) {
return priority(a) < priority(b);
});
}

这里首先将INTERNAL转换为HIDDEN,之后按照最小的priority来更新visibility。

update_minimum只是一个针对多线程的封装,本质上是一个compare and exchange操作。

1
2
3
4
5
6
7
template <typename T, typename Compare = std::less<T>>
void update_minimum(std::atomic<T> &atomic, u64 new_val, Compare cmp = {}) {
T old_val = atomic.load(std::memory_order_relaxed);
while (cmp(new_val, old_val) &&
!atomic.compare_exchange_weak(old_val, new_val,
std::memory_order_relaxed));
}

fast_mark也是针对多线程的一个封装,如果是false则更新为true。

1
2
3
4
5
6
7
8
9
10
// An optimized "mark" operation for parallel mark-and-sweep algorithms.
// Returns true if `visited` was false and updated to true.
inline bool fast_mark(std::atomic<bool> &visited) {
// A relaxed load + branch (assuming miss) takes only around 20 cycles,
// while an atomic RMW can easily take hundreds on x86. We note that it's
// common that another thread beat us in marking, so doing an optimistic
// early test tends to improve performance in the ~20% ballpark.
return !visited.load(std::memory_order_relaxed) &&
!visited.exchange(true, std::memory_order_relaxed);
}

SharedFile::mark_live_objects

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename E>
void
SharedFile<E>::mark_live_objects(Context<E> &ctx,
std::function<void(InputFile<E> *)> feeder) {
for (i64 i = 0; i < this->elf_syms.size(); i++) {
const ElfSym<E> &esym = this->elf_syms[i];
Symbol<E> &sym = *this->symbols[i];

if (sym.traced)
print_trace_symbol(ctx, *this, esym, sym);

if (esym.is_undef() && sym.file && !sym.file->is_dso &&
fast_mark(sym.file->is_alive)) {
feeder(sym.file);

if (sym.traced)
SyncOut(ctx) << "trace-symbol: " << *this << " keeps " << *sym.file
<< " for " << sym;
}
}
}

这里要说的唯一一点是因为mark的是object而不是shared file,因此dso的情况下不会进行mark

2. 移除重复的COMDAT段

1
2
3
4
5
6
7
8
9
10
11
{
Timer t(ctx, "eliminate_comdats");

tbb::parallel_for_each(ctx.objs, [](ObjectFile<E> *file) {
file->resolve_comdat_groups();
});

tbb::parallel_for_each(ctx.objs, [](ObjectFile<E> *file) {
file->eliminate_duplicate_comdat_groups();
});
}
1
2
3
4
5
template <typename E>
void ObjectFile<E>::resolve_comdat_groups() {
for (ComdatGroupRef<E> &ref : comdat_groups)
update_minimum(ref.group->owner, this->priority);
}

更新所有comdat_groups的priority

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename E>
void ObjectFile<E>::eliminate_duplicate_comdat_groups() {
for (ComdatGroupRef<E> &ref : comdat_groups)
if (ref.group->owner != this->priority)
for (u32 i : ref.members)
if (sections[i])
sections[i]->kill();
}

template <typename E>
inline void InputSection<E>::kill() {
if (is_alive.exchange(false))
for (FdeRecord<E> &fde : get_fdes())
fde.is_alive = false;
}

eliminate重复的section。将section和fde的is_alive都设置为false。

这里将fde设置为false正对应了上期提到单独解析eh_frame的原因之一:消除重复的fde。

3. 实际进行符号决议的过程

1
for_each_file([&](InputFile<E> *file) { file->resolve_symbols(ctx); });

resolve_symbols的实现对于ObjectFile和SharedFile是不同的

ObjectFile

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
template <typename E>
void ObjectFile<E>::resolve_symbols(Context<E> &ctx) {
for (i64 i = this->first_global; i < this->elf_syms.size(); i++) {
Symbol<E> &sym = *this->symbols[i];
const ElfSym<E> &esym = this->elf_syms[i];

if (esym.is_undef())
continue;

InputSection<E> *isec = nullptr;
if (!esym.is_abs() && !esym.is_common()) {
isec = get_section(esym);
if (!isec || !isec->is_alive)
continue;
}

std::scoped_lock lock(sym.mu);
if (get_rank(this, esym, !this->is_alive) < get_rank(sym)) {
sym.file = this;
sym.set_input_section(isec);
sym.value = esym.st_value;
sym.sym_idx = i;
sym.ver_idx = ctx.default_version;
sym.is_weak = esym.is_weak();
sym.is_imported = false;
sym.is_exported = false;
}
}
}

符号决议是针对global symbol的elf_sym的。未定义的esym都跳过了,它们都不需要参与resolve的过程,因为resolve本质是找到需要加入到生成产物的符号实现,但是注意在前面mark的时候还是需要的。

也就是说Symbol类的sym其实是保留的最终唯一定义。而在决议的过程,不断的将esym和对应的sym进行比较。如果esym的rank小,也就是更加优先,那么就将sym中的信息更新为对应的esym的信息,这就是实际决议过程中做的事情。而这里也是实际初始化symbols成员里global的值的地方,local的部分初始化在parse的阶段就做好了,因为local的符号并不需要进行resolve。

get_rank

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
template <typename E>
static u64 get_rank(const Symbol<E> &sym) {
if (!sym.file)
return 7 << 24;
return get_rank(sym.file, sym.esym(), !sym.file->is_alive);
}

// Symbols with higher priorities overwrites symbols with lower priorities.
// Here is the list of priorities, from the highest to the lowest.
//
// 1. Strong defined symbol
// 2. Weak defined symbol
// 3. Strong defined symbol in a DSO/archive
// 4. Weak Defined symbol in a DSO/archive
// 5. Common symbol
// 6. Common symbol in an archive
// 7. Unclaimed (nonexistent) symbol
//
// Ties are broken by file priority.
template <typename E>
static u64 get_rank(InputFile<E> *file, const ElfSym<E> &esym, bool is_lazy) {
if (esym.is_common()) {
assert(!file->is_dso);
if (is_lazy)
return (6 << 24) + file->priority;
return (5 << 24) + file->priority;
}

if (file->is_dso || is_lazy) {
if (esym.st_bind == STB_WEAK)
return (4 << 24) + file->priority;
return (3 << 24) + file->priority;
}
if (esym.st_bind == STB_WEAK)
return (2 << 24) + file->priority;
return (1 << 24) + file->priority;
}

get_rank的实现,根据注释我们可以看到不同类别符号的优先级。

SharedFile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename E>
void SharedFile<E>::resolve_symbols(Context<E> &ctx) {
for (i64 i = 0; i < this->symbols.size(); i++) {
Symbol<E> &sym = *this->symbols[i];
const ElfSym<E> &esym = this->elf_syms[i];
if (esym.is_undef())
continue;

std::scoped_lock lock(sym.mu);

if (get_rank(this, esym, false) < get_rank(sym)) {
sym.file = this;
sym.origin = 0;
sym.value = esym.st_value;
sym.sym_idx = i;
sym.ver_idx = versyms[i];
sym.is_weak = false;
sym.is_imported = false;
sym.is_exported = false;
}
}
}

对于SharedFile中的符号中不需要考虑是否是global的问题,上期解析SharedFile的部分也有提到,对应的first_global就是0。相对于

4. LTO的处理

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
if (ctx.has_lto_object) {
// Do link-time optimization. We pass all IR object files to the
// compiler backend to compile them into a few ELF object files.
//
// The compiler backend needs to know how symbols are resolved,
// so compute symbol visibility, import/export bits, etc early.
mark_live_objects(ctx);
apply_version_script(ctx);
parse_symbol_version(ctx);
compute_import_export(ctx);

// Do LTO. It compiles IR object files into a few big ELF files.
std::vector<ObjectFile<E> *> lto_objs = do_lto(ctx);

// do_resolve_symbols() have removed unreferenced files. Restore the
// original files here because some of them may have to be resurrected
// because they are referenced by the ELF files returned from do_lto().
ctx.objs = objs;
ctx.dsos = dsos;

append(ctx.objs, lto_objs);

// Redo name resolution from scratch.
tbb::parallel_for_each(ctx.objs, [&](ObjectFile<E> *file) {
file->clear_symbols();
file->is_alive = !file->is_in_lib;
});

tbb::parallel_for_each(ctx.dsos, [&](SharedFile<E> *file) {
file->clear_symbols();
file->is_alive = !file->is_needed;
});

// Remove IR object files.
for (ObjectFile<E> *file : ctx.objs)
if (file->is_lto_obj)
file->is_alive = false;

std::erase_if(ctx.objs, [](ObjectFile<E> *file) { return file->is_lto_obj; });

do_resolve_symbols(ctx);
}

关于apply_version_script, parse_symbol_version, compute_import_export这三个过程,会在之后的过程中讲解。这里简单来讲就是获取符号对应的版本信息以及对应import/export的属性。

这个部分做了这么几件事情

  1. 计算出符号所需的基本信息
  2. 实际执行lto
  3. 将lto结果的object加入到全局
  4. 清理旧的lto文件
  5. 再次执行do_resolve_symbols整个过程
  • 本文标题:mold源码阅读 其三 符号决议
  • 本文作者:Homura
  • 创建时间:2023-04-09 16:06:20
  • 本文链接:https://homura.live/2023/04/09/mold/mold-3-symbol-resolve/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!