winston 发表于 2012-2-7 10:15:05

Ulrich Drepper大作之How To Write Shared Libraries

读大牛Ulrich Drepper关于如何写动态库的大作心得。

一些术语
DSO, Dynamic Shared Objects
PLT,Procedure Linkage Table


关键点

[*]section 1
回顾a.out的历史,阐述它的优缺点, 引入COFF, 再到ELF. 相关描述也可以参照有一定年头的Linker and Loader一书. 其中有更多不同平台上的文件格式的发展的介绍:)


简述ELF的结构及组织:

[*]系统中同时存在static linker和dynamic linker, DSO要依靠dynamic linker来相互合作. 经由dynamic linker的一些动作, 如reloaction之后, 控制流才会转到相应的可执行文件.
[*]ELF header提供了所有ELF section的相关信息, 它的结构可以参照Dwarf3.pdf, 本章简单的介绍了一下ELF header中的各个结构成员的用途. 它会指向各个program header.
[*]program header中有一个关键的PT INTERP tag, 它表示了应该用什么样的dynamic linker, 利用它来指定具体的dynamic linker. 当它被kernel 映射到进程空间之后, 还需要为它准备auxiliary vector的数据结构(以便绕过一些不必要的系统调用, 使得dynamic linker更易工作, AT_开头的tag,都是与auxiliary vector相关的), 之后才能把控制权转交到dynamic linker.
[*]dynamic linker的三个任务:确认并加载相关依赖, 重定位应用程序和所有的依赖, 正确的初始化应用程序和其依赖.
最繁重的任务就是重定位, 它的时间复杂度是O(R +nr), 其中R是相关重地位的个数, r是命名重地位的个数, n是主程序所用到的DSO的个数
有不少针对上诉任务的优化方案, 其中有的能使得时间复杂度变为O(R + rn log s), 其中s是符号的个数. 从中可见,最终要的就是尽可能的减少重定位和符号的个数.
而重地位中最复杂的就是symbol relocation.
[*]禁止lazy relocation: 对linker 使用-z now参数. 但是, 这依赖于重新link DSO或者更改binary, 所以, 慎用.
有两种方式来搜寻一个给定的symbol, 其中对于lookup scope的定义和选择相当复杂, 文中在1.5.4中详细介绍了

[*]传统的ELF方式

[*]计算symbol name的hash值
[*]在lookup scope内,对各个object进行以下操作
2.1 使用该object的hash值和hash table的大小来决定hash bucket
2.2 获得该symbol名称的offset, 并用它作为一个以NUL结尾的名称
2.3 拿该symbol name与relocation name比较
2.4 如果名称相符, 再比较它们的version name, 两者都相同, 则找到所要的.
2.5 如果名称不相符, 在hash bucket中选取下一个
2.6 如果当前的object所包含的链中都没有找到, 就选取下一个lookup scope
[*]如果在所有的lookup scope中都没有找到, 则搜寻失败
      从中可以看出, 关键的效率考量在如何选取lookup scope中的object数及hash chain的长度. GNU 通过优化这两者提供了另外一种更有效的方式.

[*]GNU 方式, 优化symbol name comparison, symbol entry link list更好的利用了CPU cache

[*]计算symbol name的hash值
[*]在lookup scope内,对各个object进行以下操作
2.1 该hash值用来判断是否该当前的object中已经有该值了. 这是通过2-bit的Bloom filter来完成的(它使得比较操作被显著减少了). 如果没有, 就在该scope中选取下一个object进行查找.
2.2 使用该object的hash值和hash table的大小来决定hash bucket. 该值是一个symbol index
2.3 从object chain中拿到这个symbol index所对应的entry, 用该entry中的值与1中的值比较. 忽略bit 0
2.4 如果两者相等, 获得该symbol名称的offset, 并用它作为一个以NUL结尾的名称
2.5 比较symbol name和reloaction name
2.6 如果名称相符, 再比较它们的version name, 两者都相同, 则找到所要的.
2.7 如果名称不相符, 并且从hash bucket中读取的值的bit 0 没有设置, 那么就在hash bucket中选取下一个
2.8 如果bit 0被设置了, 并且在当前的object的hash chain中没有元素了, 则我们继续对下一个object搜索
[*]如果在所有的lookup scope中都没有找到, 则搜寻失败
使用dlopen方式的shared library, 不能使用prelink的机制来优化!!!
改变以下任意一点都有助于效率的提高:
    number of exported symbols
    length of the symbol strings
    number and length of common prefixes
    number of DSOs
    hash table size optimization

什么是lookup scope (文中1.5.4), 相当复杂, 关系到很多自己不明白的linker参数, :(((, 还需要加深认识
分为3个部分:
    global lookup scope, 包含可执行文件自身和所有的依赖(所有的依赖由宽度优先算法来初始化)
    dlopen所加载的dynamically loaded object, 它是比较复杂的
    local lookup scope
这三部分造成了错综复杂的初始化顺序及查找问题!!!

介绍了GOT和PLT
总结了三点:
    任何使用由GOT exported的全局变量及加载它的值的动作都是indirectly
    如果被调用的函数没有在调用处定义, 那么就需要一个PLT. 通过PLT调用这种函数是indirectly, 这是因为security的原因(directly会使得恶意程序能够影响PLT的作用).
    一些体系结构要求每个PLT元素都至少要有一个GOT元素

[*]如何为DSO注册合适的constructor和destructor
void
__attribute ((constructor))
init_function (void)
{
...
}
void
__attribute ((destructor))
fini_function (void)
{
...
}
这样的做法使得gnu的ld在runtime时,能够在正确的时候调用它们, 而不会扰乱系统其它正确的初始化及销毁动作.
[*]关于ELF 代价
Code Size, 越小效率越高
Number of Objects, 越少约好, 文中有这些objects的一个罗列
Number of Symbols, 导出的和未定义的symbols越少越好
Length of Symbol Strings, 越短越好
Number of Relocations, 越少越好
Kind of Relocations, relative relocation好于normal relocation
Placement of Code and Data, 注意自己创建的数据元素, 尽量保证它能被放入read-only的segment, 其次, 最好能把它们初始化为0.
[*]如何对ld进行benchmarks
LD_DEBUG的环境变量会影响ld的动作, 可以产生debug数据
另外, 本文章的appendix A提供了一个relinfo
[*]section 2 Optimizations for DSOs

对与DSO, 请一定使用-fpic or -fPIC作为最后一个编译参数. 这样可以使得最后的library中不会产生text relocation. 没有text relocation为性能带来了一定的提升.
请注意, 这里的-fpic和-fPIC在一些RISC的处理器上是有所区别的, 比如,SPARC, 它对GOT的大小有限制. 详情参见文档中的描述. 尽量使用-fpic, 除非有特别情况, 才考虑使用-fPIC
使用如下命令可以很方便的检查一个library是否包含text relocation
    readelf -d binary | grep TEXTREL

对于数据对象的初始化的优化
    尽量不初始化变量或初始化为0. 而不是初始化为非0值.
export symbol的优化, 有些会依赖特定的平台,使用时请注意参考个平台的一些特性. (同时, 请注意, 如果开发者决定需要生成的binary ELF是包含非标准的成份, 那么以下的优化措施, 需要重新考虑)
    尽可能把相互引用的变量, 函数定义放在一个文件中, 并定义为static, 这会使得编译器优化生成的代码, 不用太过依赖GOT和PLT, 减少了生成不必要的寄存器操作指令
    GCC 4.0之后提供了4种可见性的定义, -fvisibility=default/-fvisibility=hidden/-fvisibility=internal/-fvisibility=protected. 程序员可以考虑合适的场合使用合适的可见性.
      __attribute__ ((visibility ("default"))) /__attribute__ ((visibility ("hidden"))) /......
      #pragma GCC visibility push(hidden)/......
    针对上述两者(static和visibility), 有如下建议:
合并尽可能多的文件并尽可能的把合适的变量/函数表示为static. 特别是那些包含能够被inline的函数的文件尽可能的merge它们. 其它的文件中的那些不会被exported出去的函数定义, 需要被标识为hidden的visibility. 文中描述了对于不要使用protect的visibility的原因.
如何为C++的class定义合适的visibility
应用上述的visibility于c++的variable, function,因为有关于class的一些访问权限关系(private, public, protect), 需要编译器与连接器共同动作, 以保证这些visibility能够在C++中工作正常.(尤其是考虑到inline函数导致的违反DSO之间访问权限的情况)
同时,对于template的class, function又与普通的class有所区别. 详细参照文档中的相关描述

总体来说, gcc 4.0之后引入了-fvisibility-inlines-hidden来帮助处理inline 函数的问题, 它会使得所有inline函数的visibility都生成为"hide"的, 从而不违反DSO的一些访问权限. 也提供了对真个class应用visibility的方法, 如下:

#pragma GCC visibility push(hidden)
class foo {
    ...
};
#pragma GCC visibility pop

class __attribute ((visibility ("hidden")))
foo {
...
};
对于exception handle的处理也需要额外注意

综上所述, 对于C++的DSO代码来说, 尽可能的应用最restrictive visibility有很大的好处!!!
使用Export Maps (gcc, llvm都支持)

主要思想是由它显示的告诉链接器哪些symbols需要从生成的object中export.通过--version-script来使用export map(export list).
限制: 因为是在编译结束之后由linker引入, 所以会丧失一些优化的可能(比如,生成一些不够有效的relocation指令).
总结,
    对于variable, 会生成大而不太有效率的代码(引入不必要的GOT, 导致多余的relocation)
    对于function, 有可能导致引入不必要的PIC.
所以, 推荐还是使用visibility的方式进行优化

使用libtools的-export-symbols
由GNU Libtool程序提供.
$ libtool --mode=link gcc -o libfoo.la \foo.lo -export-symbols=foo.sym主要关注与,使用Libtools生成能与上述Export Maps合作的文件
是否使用上述的那些优化, 需要仔细参考文中的例子,加深理解才能更好的取舍

Wrapper function, 如何使用wrapper, 权衡利弊
Using Aliases, 区分各种使用场景
DF SYMBOLIC, 不要使用它

尽可能缩短symbol string的长度, 尤其C++这样的语言. 但是没有合适的工具和成熟的方法, 需要在设计时加以考虑, 统一编码规则.

选择合适的类型
Pointers vs. Arrays
char *str = "some string"; vs char str[] = "some string";
通过后者, 使得我们省去了一个不必要的指针变量--它坐落在 non-sharable data segment. 编译器可以更好的知道str的值是不会被改变的.

Forever const
无论何时, 对于不会被改变的str[], 使用const. 对于此种优化, gcc还会做更多的事情, 如SHF MERGE and SHF STRINGS. 简单的描述参照文档中的描述. 简单来说如果发现有两个str1[], str2[], 有相同的字段, 会用其中一个的suffix/postfix来实现另外一个.

Arrays of Data Pointers
有些数据结构在普通的application代码里工作的很好, 但是用在DSO中就会带来很高花费. 特别是指针数组!!!
例如,

static const char *msgs[] = {
    = "message for err1",
    = "message for err2",
    = "message for err3"
};
const char *errstr (int nr) {
   return msgs;
}
这里, msgs的定义,在DSO中会由compile在writable memory中放置三个变量的同时,需要3个relocation modify来操作对应的三个字符串.
请记住, 无论什么时候, 一个变量,数组,结构体或者是union包含有一个指针, 定义一个初始化的这些变量都需要一个对应的relocation操作, 这又需要把该变量放在writable memory中. 这就导致降低了启动速度. 对该问题的解决方法是,不要使用指针数组, 而是使用在compile就能确定的结构.如

static const char msgs[] = {
    = "message for err1",
    = "message for err2",
    = "message for err3"
};
static const char msgstr[] =
    "message for err1\0"
    "message for err2\0"
    "message for err3";
static const size_t msgidx[] = {
    0,
    sizeof ("message for err1"),
    sizeof ("message for err1")
    + sizeof ("message for err2")
};
const char *errstr (int nr) {
    eturn msgstr + msgidx;
}

Arrays of function pointers
类似与arrays of pointers, 但是面临着其它问题, 具体的避免方法参看文中详细描述. 使用switch结构帮助生成PIC的代码

C++ Virtual Function Tables
通过文中的分析, 只能通过给linker以指定的script的方法,能够优化该情况下的relocation.
由于virtual function从文中的分析可以看出, 它可以通过不同的途径所调用, 所以优化的时候需要分清场合.
总的来说, virtual function tables的个数及大小要尽可能小, 它直接影响startup的时间. 同时, 如果不能避免使用virtual function, 那么请尽可能把virutal function的实现和定义分开, 并且尽可能不要把该函数的实现给export出去.
改进生成的代码

文中举了IA-32和IA-64两个体系结构下对一段代码产生的汇编码的不同. 特别关注的是GOT,PIC使用的解释.
提供了两个建议:
完全避免使用PIC register, 当然这也会带来一些负面作用
重新组织代码, 具体的情况参见文中描述. 但是,在IA-32下, 是可以考虑的, 对于IA-64则就不必了.

增加安全性

GOT, PLT变为readonly可以带来很好的安全性, 但是在IA-32平台下, GOT还不能是read only的.
引入mprotect可以帮助提高安全性, 但是会带来很大的性能损耗.
由于GOT的relocation可以有两种途径:
    dynamic linker开始工作时(针对那些non lazy relocation),
      对于它可以在首次加载并relocation之后,使得它们变为非可写的. 这可以通过-z relro的linkage选项来完成.
      通过-z now的linkage选项可以禁止所有的non lazy relocation, 当然, 这会带来很多的性能损失.
      比如, 所有的GNU中的DSO都是打开这两者来编译的
      再者, 尽量用const来修饰,
      如,const char *msgs1[] = {    "one", "two", "three"
};
const char *const msgs2[] = {
    "one", "two", "three"
};
       msgs1 会被放在.data段, 而msgs2会放在.data.rel段, 后者在动态链接时,会由连接器在relocation完成之后把它的write access的属性给去掉.

    总之, 文中建议使用
      尽可能多的const + -z relro的组合来编译

    由dlopen之类的动态relocation, 对于这类, 关注text relocation的安全性(它在首次初始化完成, 但是还没有被执行时会引入受攻击的可能), 从文中的描述可知, 没有好的方法防止. 只能按照SELinux的做法来办.(要么以付出安全性为代价来提升权限,要么就在所有的DSO和PIE去除text relocation)
关于如何Profile DSO
通过设定LD PROFILE的环境变量, 就可以在不重新编译DSO的情况下, 打开profile的功能.
使用sprof来进行profile

对于使用dlsym之类的动态程序, 需要使用DL CALL FCT 宏来帮组我们进行profile(请不要在发布的版本中使用它, 会带来性能损失)foo = (*fctp) (arg1, arg2);-->
foo = DL CALL FCT ((*fctp) (arg1, arg2));



section 3, 维护APIs和ABIs


[*]详细介绍了linux, solaris, GNU所采取的一些维护DSO的API/ABI的方法及优点/缺点
以及一些发生ABIs不匹配的情况
各种方法都依赖与对DSO进行合适的version化.
这个章节没有仔细阅读, 以后遇到ABIs的相关问题时,需要加深认识.
附录A,

提供了一个perl脚本,来帮助分析有关Relocation信息
附录B,
提供了一个用来削除2.4.3(Arrays of String Pointers)问题的方便使用的宏!!





作者:Melody_lu123 发表于2012-2-6 17:52:36 原文链接

页: [1]
查看完整版本: Ulrich Drepper大作之How To Write Shared Libraries