All about symbol versioning

1995年Solaris的link editor和ld.so引入了symbol versioning机制。
Ulrich Drepper和Eric Youngdale在1997年借鉴Solaris symbol versioning,设计了用于glibc的GNU风格symbol versioning。

一个shared object更新,某个符号的行为变更(ABI改变(如变更参数或返回值的类型)或行为变化)时,传统上可以bump DT_SONAME:依赖的shared objects必须重新编译、链接才能继续使用;如果不改变DT_SONAME,依赖的shared objects可能悄悄地产生异常行为。
使用symbol versioning可以提供不改变DT_SONAME的backward compatibility。

Read More

解析GNU风味的linker options

(首先庆祝一下LLVM 2000 commits达成!)

编译器driver options

在描述链接器选项前先介绍一下driver options。通常使用gccclang,指定的都是driver options。一些driver options会影响传递给链接器的选项。
有些driver options和链接器重名,它们往往在传递给链接器同名选项之外还有额外功效,比如:

Read More

模块内函数调用和libc符号重命名

Translation unit外的函数调用

在一个libc实现中,有时会调用自身其他translation unit定义的函数,如:

1
2
3
4
5
#include <string.h>

void foo(void *src, const void *dst) {
memcpy(dst, src, 90);
}

这个translation unit用-fPIC编译成.o时会生成一个memcpy函数调用。在部分架构上有少量PIC设置的开销(见下文)。

在一个ELF文件格式的shared object中,一个定义的non-local STB_DEFAULT符号默认为preemptible(interposable),即运行时可被替换。
对于一个preemptible符号,对其的引用不可绑定到模块内部的定义。

这个.o用-shared方式链接时,即使memcpy定义在该shared object的另一个translation unit中,链接器也会假设memcpy在运行时可能被可执行文件或其他shared object在替换,看到表示函数调用的relocation types时得生成PLT。

1
2
3
4
5
# Although memcpy is within the module, the linker cannot resolve the relocation to the address of memcpy (direct call).
# It has to resolve the relocation to the PLT entry (symbolized as memcpy@plt in objdump).
f: call memcpy@PLT # R_X86_64_PLT32

memcpy: ...

运行时替换提供了灵活性,但也牺牲了性能。一个函数调用需要执行PLT entry中几条指令,从.got.plt(多数架构)读取一个函数指针执行间接跳转。
还要算上ld.so解析这个符号的一次性开销。

在99.9%的情况下Procedure Linkage Table (PLT)的作用是调用一个定义在其他shared object或可执行文件中的函数。
(什么?你要问我剩下的0.1%是什么?是GNU indirect function中一种接近失传、晦涩的技巧。今天binutils添加了RISC-V的ifunc支持,我就在之前的邮件中提到了LLD使用的方法)

Translation unit内的函数调用和-fno-semantic-interposition

GCC 5引入了-fno-semantic-interposition。如果调用的函数定义在同一个translation unit,

1
2
3
// f is global STV_DEFAULT.
void f() {}
void g() { f(); }

编译器有两种选择:

  • -fsemantic-interposition (GCC默认行为): 保守地假设可能发生运行时preemption,阻止一切相关的inter-procedural optimizations(如inlining)。
    1
    2
    3
    4
    5
    f:
    ...
    g:
    # Inlining f into g may change semantics if f is preempted at runtime.
    call f@PLT
  • -fno-semantic-interposition: 乐观地假设不发生preemption,允许inter-procedural optimizations。这其实是Clang长期以来的行为。(我的贡献)Clang 11若指定该选项,会在LLVM IR层面设置dso_local。在x86上,如果函数最终没有被inline,编译器会生成对local alias .Lfoo$local的调用。Local symbols是non-preeemptible的,可以阻止链接器生成PLT。
    1
    2
    3
    4
    5
    f: # STB_GLOBAL
    .Lf$local: # STB_LOCAL
    ...
    g:
    call .Lf$local
    如果f定义在另一个translation unit,这个选项仍然不能阻止PLT。

在Clang 11,Serge Guelton添加了-fsemantic-interposition

libc中有大量库函数会被其他库函数调用。放任它们产生PLT会有可观的性能损失。链接器提供了-Bsymbolic, -Bsymbolic-functions, version script和--dynamic-list等几种机制使部分符号non-preemptible。

musl采用的方法是用--dynamic-list精细指定libc.so中preemptible的符号列表:

1
2
3
4
{
environ; __environ; stdin; stdout; stderr; timezone; daylight; tzname; ...
malloc; calloc; realloc; free; ...
}

在可执行文件和shared object中,--dynamic-list的语义不同。这里取shared object语义:

  • executable: Put matched non-local defined symbols to the dynamic symbol table
  • shared object: Matched defined non-local STV_DEFAULT symbols are non-preemptible, and others are preemptible. (Implies -Bsymbolic but does not set DF_SYMBOLIC.)
    (References to preemtible symbols cannot be bound to the definitions within the shared object.)

大多数函数都不在这个列表中,因为大多数程序都不能被用户程序重定义。C标准规定在程序中定义任何标准库函数都是undefined behavior,但在实际中很多实现会放宽要求以允许可替代的malloc实现(最著名的是通过LD_PRELOAD使用的jemalloc和tcmalloc)。另外sanitizers也会preempt大量库函数。

musl 1.1.20起支持用户程序替换少量malloc相关函数,因此这些这些函数在dynamic list中。

在1.1.20之前,musl的malloc实现不可被替换。musl使用功能比--dynamic-list弱的-Bsymbolic-functions:所有的STT_FUNC符号non-preemptible,而所有STT_OBJECT符号仍是preemptible的。

-fno-PIC方式编译的translation unit只能用于可执行文件。
传统上,很多架构的-fno-PIC会用absolute relocation或PC-relative relocation访问外部STT_OBJECT符号,不用Global Offset Table (GOT)。
当访问的符号定义在一个shared object中时,就会在链接时产生copy relocation (an ugly hack):可执行文件把shared object的若干字节复制过来,让shared object对该符号的解析重定向到可执行文件。

对于copy relocation,只有使符号preemptible才能维持程序的一致性。倘若non-preemptible,就会产生可执行文件和shared object操作不同拷贝的情形。

1
2
3
4
5
// On x86, direct access is generated in both -fno-PIC and -fPIE.
// stdout requires a copy relocation.
// If libc.so is linked with -Bsymbolic, modifying stdout in the executable will not be observed by libc.so, vice versa.
#include <stdio.h>
int main() { fprintf(stdout, "%d", 42); }

PLT设置的开销

使用链接选项的方案很优雅。对于具有PC relative访问数据的指令的架构,这种方案是完美的。
在其他架构上,一个需要PLT的外部函数调用会有额外开销(链接选项不影响编译期)。下面展示编译这段C程序得到的汇编指令:

1
2
3
4
5
6
#ifdef HIDDEN
void ext() __attribute__((visibility("hidden")));
#else
void ext();
#endif
void f() { ext(); ext(); }

在具有PC relative访问数据的指令的架构上,ext是否hidden,生成的指令序列没有变化。

i386

在i386上,ABI要求访问PLT时ebx指向GOT base,因为PLT entry会用基于ebx的寻址加载.got.plt(或罕见的.plt.got)的函数指针。外部函数前需要设置ebx。
因为ebx是call-saved的,如果一个函数修改了ebx,需要保证返回时ebx被还原,因此还有额外的save/restore。

1
2
3
4
5
6
7
8
9
10
11
# ext is STV_DEFAULT
f:
pushl %ebx
call __x86.get_pc_thunk.bx
addl $_GLOBAL_OFFSET_TABLE_, %ebx
subl $8, %esp
call ext@PLT
call ext@PLT
addl $8, %esp
popl %ebx
ret
1
2
3
4
5
6
# ext is STV_HIDDEN
f:
subl $12, %esp
call ext
addl $12, %esp
jmp ext

PowerPC64

POWER10有PC-relative访问数据的指令。之前,ELFv2用TOC (Table Of Contents)降低缺乏PC-relative指令带来的性能开销。
ABI要求r2指向当前module (可执行文件或shared object)的TOC base。一个外部函数调用会修改r2,因此一个bl指令后需要恢复r2。
编译器会在每一条外部bl指令后放置一个nop(他们一定是受到了Mips delay slot的启发),链接时按需patch成ld指令。
除了多余的nop开销外,还导致了tail call失效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# ext is STV_DEFAULT
f:
.Lfunc_begin0:
.Lfunc_gep0:
addis 2, 12, .TOC.-.Lfunc_gep0@ha
addi 2, 2, .TOC.-.Lfunc_gep0@l
.Lfunc_lep0:
.localentry f, .Lfunc_lep0-.Lfunc_gep0
mflr 0
std 0, 16(1)
stdu 1, -32(1)
bl ext
nop
bl ext
nop
addi 1, 1, 32
ld 0, 16(1)
mtlr 0
blr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# ext is STV_HIDDEN
f:
.Lfunc_begin0:
.Lfunc_gep0:
addis 2, 12, .TOC.-.Lfunc_gep0@ha
addi 2, 2, .TOC.-.Lfunc_gep0@l
.Lfunc_lep0:
.localentry f, .Lfunc_lep0-.Lfunc_gep0
mflr 0
std 0, 16(1)
stdu 1, -32(1)
bl ext
addi 1, 1, 32
ld 0, 16(1)
mtlr 0
b ext

意外地,两种函数调用方式在Mips上没有差别,可能是因为它们的指令序列已经很长了吧……

Compile-time solution: hidden aliases

glibc采取的方式是

  • 定义STV_DEFAULT的memcpy和一个hidden alias __GI_memcpy
  • 内部header声明memcpy时asm label指向hidden的__GI_memcpy
  • 不使用-fno-builtin-memcpy,允许memcpy函数调用被内联
  • 引用memcpy处include内部header。memcpy或者被内联,或者生成对__GI_memcpy的调用

因为__GI_memcpy是hidden的,编译器/链接器知道它的定义在模块内部,且不能由其他模块提供,因此能避免PLT设置开销。

1
2
3
4
5
6
extern void *memcpy(void *__restrict, const void *__restrict, unsigned long);
extern __typeof(memcpy) memcpy __asm__("__GI_memcpy") __attribute__((visibility("hidden")));

void f() {
memcpy(...);
}

所以,为什么不直接调用__GI_memcpy呢?因为这样mangle函数名用户体验不好……

其实musl在很多地方也用了__开头的hidden aliases,需要避免PLT设置开销时就会调用这些函数,如:

1
2
3
4
5
6
7
8
9
10
// src/include/sys/mman.h
__attribute__((__visibility__("hidden"))) void *__mmap(void *, size_t, int, int, int, off_t);

// src/mman/mmap.c
void *__mmap(void *start, size_t len, int prot, int flags, int fd, off_t off)
{
...
}

extern __typeof(__mmap) mmap __attribute__((__weak__, __alias__("__mmap")));

STV_PROTECTED

其实,除了STV_DEFAULTSTV_HIDDEN外,还有另一种在这种场景下更适合的visibility:STV_PROTECTED
有一个缺点是历史上STV_PROTECTED使用非常少,缺乏测试。但缺乏测试在最近若干年应该不是问题了。

STV_PROTECTED在ELF specification中的定义如下,暴露给外界,且non-preemptible,看上去是完美解决方案。

A symbol defined in the current component is protected if it is visible in other components but not preemptable, meaning that any reference to such a symbol from within the defining component must be resolved to the definition in that component, even if there is a definition in another component that would preempt by the default rules.

那么为什么libc不用STV_PROTECTED呢?

传统上,很多结构上-fno-PIC取外部函数地址就像访问外部STT_OBJECT符号那样,会用absolute relocation或PC-relative relocation,不用Global Offset Table (GOT)。
链接器会在可执行文件里创建一个st_value!=0的PLT entry(相当于STT_FUNC的copy relocation)。可执行文件中该函数的地址就是这个PLT entry的运行时地址。
为了pointer equality,链接器会试图让该PLT entry preempt shared object中的定义。然而,STV_PROTECTED是不允许preemption的,冲突导致报错。

1
2
3
4
5
6
7
8
// b.c - b.so
__attribute__((visibility("protected"))) void foo() {}
void *addr_foo() { return (void *)foo; }

// a.c - exe
#include <stdio.h>
void foo();
int main() { printf("%p\n", foo); }

链接时会报错:

1
2
3
4
5
# ld.lld
error: cannot preempt symbol: foo

# ld.bfd
relocation R_X86_64_32 against protected symbol `foo' can not be used when making a PIE object; recompile with -fPIE

假如链接器允许可执行文件中的absolute relocation或PC-relative relocation,运行时可执行文件中foo的地址会和shared object中foo的地址不一致。

asm label in Clang

对于大多数编译器不认识的函数(没有内建知识,不能内联(expand memcpy)或替换成其他实现(printf->puts),不能生成lower成该函数的intrinsics),asm label的实现方式都是挺直接的。
然而,在今天之前的Clang里,有不少库函数(包括最重要的memset/memcpy)的asm label没有效果。我今天修复了这个问题D88712

这里的主要难点是如果C函数foo含有内建语义X,且符号foo含有内建语义X,那么拒绝编译C函数foo为符号foo是不合逻辑的。
换言之,下述三条不可同时成立。

  • 如果frontend函数foo含有内建语义X
  • 符号foo含有内建语义X
  • C函数foo不能编译为符号foo

在glibc的场合下,第一条是需要的。如果编译器假装不认识memcpy,那么就无法展开n为常数的memcpy,可能会影响性能。这也表明-fno-builtin-memcpy(或更强的-fno-builtin-ffreestanding)不可接受。
第三条也是需要的,因为使用asm label的目的就是重命名啊……

这样我们就得驳斥第二条。换言之,Clang生成LLVM IR后,IR优化不可假设符号foo具有内建语义X。然而这在GCC和Clang中都无法做到。
Clang若想实现,得引入LLVM IR特性支持重命名。倘若不支持重命名,得知道会lower成符号foo的intrinsics不可生成。
这个功能目前是缺失的。

不能驳斥第二条给整个系统带来了一点不一致性。glibc的处理方式是加第二层重命名,给每个translation unit加一条asm("memcpy = __GI_memcpy;")

1
2
3
4
memcpy = __GI_memcpy;

# If __GI_memcpy is undefined, this produces a relocation referencing __GI_memcpy.
call memcpy@PLT
  • 对于不#include <string.h>的translation unit,asm label不可替代这个重命名。
  • 对于GCC优化过程中合成的memcpy,这行asm保证了GNU as会实施重命名。

我有另一个patch实现GNU as的这个逻辑。

另外,Clang支持继承自Sun Studio的另一种重命名语法:#pragma redefine_extname oldname newname。内部这一功能是用asm label实现的。
GCC文档中提到了这个功能https://gcc.gnu.org/onlinedocs/gcc/Symbol-Renaming-Pragmas.html,但我测试不可用……

LLVM命令行选项的处理

题外话:不知不觉,达成了llvm-project 1900 commits的成就。

LLVM中命令行选项的处理有两个库。

llvm/Support/ComandLine.h

文档参见https://llvm.org/docs/CommandLine.html

简单来说,用全局变量(llvm::cl::opt<type> var最常见,也有llvm::cl::list等)表示命令行选项。opt的构造函数会在一个全局的registry中注册这个命令行选项。
main中调用llvm::cl::ParseCommandLineOptions(argc, argv, ...)解析命令行。
opt支持很多类型,如各种integer types、bool、std::string等,还支持自定义enum类型。

Read More