动态链接进阶及在 Python 环境的应用

01 Aug 2019

引言
linker subtlety recap
dlopen
- RTLD flags
回到 Python
References

引言

承接上文指出的 Numpy 存在的大矩阵对角化时不可避免的 int crash 的问题，我最近写了 numkl 这个库，用来直接利用 MKL ilp64 interface 的 lapack routine 来求解本征值问题，同时支持 numpy array 的输入，使得在 Python 里可以没有时间和空间 overhead 来做超大矩阵的对角化问题。这其中我也进一步学习了很多 Cython，conda 打包与 conda-forge 生态系统的知识。不过本文则将讲述关于动态链接和动态库使用的那些事，通过这些知识和实验，最后用来分析 Python 中同时导入 numpy 和 numkl 之后的一些不符合预期的行为。

linker subtlety recap

本文假设读者已经具有了相当的 Linux 下 C 程序的开发经验和关于编译链接工具链，静态库动态库制作和使用的基础知识。因此不会老调重弹去聊一些非常基础的内容，比如静态库和动态库的优劣比较，静态库和动态库的编译生成，动态库的编译时路径和运行时路径，这些路径的搜索顺序，调整和设置，编译时 linker 和运行时 linker 的区别等等。以上这些内容，有着丰富的网络资源和参考资料，如若还不了解可先行阅读¹²³。这一部分则只会对绝大部分资料甚至 gcc，linux manual 也有些语焉不详的微妙之处做一个猜想和验证。注意到不同操作系统不同平台甚至不同版本之间，编译链接工具链的行为也会有微妙的变化，下面列举的事实很可能是仅限于较新版 Linux kernel 上 gcc 工具链的行为。

## information on OS and compiler toolchains, facts below may be unique feature in these setups instead of general feature of compilers
$ uname -r
4.15.0-54-generic
$ lsb_release -d
Description:	Ubuntu 18.04.2 LTS
$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/7/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 7.4.0-1ubuntu1~18.04.1' --with-bugurl=file:///usr/share/doc/gcc-7/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++ --prefix=/usr --with-gcc-major-version-only --program-suffix=-7 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-libmpx --enable-plugin --enable-default-pie --with-system-zlib --with-target-system-zlib --enable-objc-gc=auto --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1)
$ gcc -Wl,-v
collect2 version 7.4.0
/usr/bin/ld -plugin /usr/lib/gcc/x86_64-linux-gnu/7/liblto_plugin.so -plugin-opt=/usr/lib/gcc/x86_64-linux-gnu/7/lto-wrapper -plugin-opt=-fresolution=/tmp/ccwguVSB.res -plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lgcc_s -plugin-opt=-pass-through=-lc -plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lgcc_s --sysroot=/ --build-id --eh-frame-hdr -m elf_x86_64 --hash-style=gnu --as-needed -dynamic-linker /lib64/ld-linux-x86-64.so.2 -pie -z now -z relro /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/Scrt1.o /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/crti.o /usr/lib/gcc/x86_64-linux-gnu/7/crtbeginS.o -L/usr/lib/gcc/x86_64-linux-gnu/7 -L/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu -L/usr/lib/gcc/x86_64-linux-gnu/7/../../../../lib -L/lib/x86_64-linux-gnu -L/lib/../lib -L/usr/lib/x86_64-linux-gnu -L/usr/lib/../lib -L/usr/lib/gcc/x86_64-linux-gnu/7/../../.. -v -lgcc --push-state --as-needed -lgcc_s --pop-state -lc -lgcc --push-state --as-needed -lgcc_s --pop-state /usr/lib/gcc/x86_64-linux-gnu/7/crtendS.o /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/crtn.o
GNU ld (GNU Binutils for Ubuntu) 2.30
/usr/bin/ld: cannot open output file a.out: Permission denied
collect2: error: ld returned 1 exit status

注意上边的最后一个命令，所有以 -Wl, 为开头的 flag 传给 gcc 后，该 flag 后边的内容会被 gcc 转发给 linker，因此可以查看 linker 的信息。

编译时 linker vs. 运行时 linker

在讨论 linker 在具体情况的处理前，需要分清 compiling time linker 和 runtime linker 的业务范围。compiling time linker 在 gcc main.c -L. -la -lb 这种编译时被调用，其大体上相当于做 ld main.o liba.so libb.so 这么件事。其具体的操作基本上可以概括为检查，和写入依赖信息。检查是指对于每个对象文件中的 undefined symbol，要在之后出现链接的动态库中寻找，直到找到名字对上的有定义的 symbol 为止。同时不断将引入的新的库中 undefined symbol 加入待查找确认的队列。当所有动态库都考虑完之后，还有 undefined symbol 时，ld 就会报错，编译失败。每个库文件中 undefined symbol 可以通过 nm liba.so|grep U 来查看。编译时 linker 确认所有 undefined symbol 都可以在其他链接的库文件中找到 defined symbol 配对之后，第二个要做的事情，就是把需要的动态库依赖信息，一般也即是动态库的名字，写进生成的可执行二进制文件中，这一内容可由 objdump -p test.out|grep NEEDED 来查看。注意这一步 ld 做的只是单纯的把命令行提供的直接依赖动态库的名字写入 elf 文件，而没有包括任何真实的动态库的内容。这一点可以通过 nm test.out|grep U 来查看，可以发现，该 undefined 的 symbol 还是 undefined。所以编译时 linker 做的仅仅是检查，尝试把所有 undefined symbol 都找到归宿，如果不行就报错；如果可行，也并不会保留这些 symbol 的配对信息。换句话说，如果不在乎把 undefined symbol 的错留到 runtime 去报，那么事实上 compiling time 的 linker 可以唯一做的就是写一下依赖库名称到最后的二进制即可（如果考虑细节，compiling time linker 还会创建一个 procedure-linking table（PLT），其中列出 undefined symbol 留待 runtime 通过 runtime linker 填充各表项的跳转地址，不过该细节不改变实质上 static linker “几乎”什么都没做的事实）。

至于 runtime linker，则在程序进入 main 之前就会通过 ld 自己的动态库先行调用，负责按照文件头中 NEEDED 的内容，把所有动态库的 symbol load 到执行环境中。如果 NEEDED 列出的所有动态库，无法按照一系列规则指定的路径找到，那么 runtime 就会报错，而不管这些动态库是否真的在 runtime 有 symbol resolve 需要。当 runtime 遇到 undefined symbol 时，runtime linker 会即时的开始 resolve，去寻找该 symbol 的定义。resolve 的顺序与动态库 loaded 进来的顺序一致，当遇到第一个该 symbol 的定义时，即完成匹配，因此后续的同名 symbol 定义将被 mask，而无法发生作用。

BFS 与 one pass

当然，每个动态库在编译生成时，还可以依赖于另外一些动态库，因此 NEEDED 的动态库，不是需要的全部，这会带来更多的微妙之处。首先 objdump -p <file>|grep NEEDED 只显示直接依赖的动态库，如果想查看所有直接和间接依赖的动态库需要 ldd <file>。ldd 命令还有额外的好处，首先是直接根据现有的环境变量和运行环境，将所有的动态库名字尽量解析出对应的动态库实际路径。其次是 ldd recursively 寻找所有的动态库依赖时，依照的顺序和实际 linker 相同，因此也体现了 runtime linker 在文件执行开头 load 动态库的顺序。这一顺序实际上是 BFS，广度优先，因此总是先列出所有的直接依赖。compiling time linker 其实也有这个效果。比如 gcc main.c -L. -la -lb，假如说 liba.so 是依赖于 libd.so 的（不要作死把自己的库起名叫 libc.so，谢谢），那么上一行命令实际上大体相当于 gcc -o main.o -c main.c, ld main.o liba.so libb.so libd.so。也即 compiling linker 实际上会按照 BFS 把所有的依赖库列出，然后开始检查 undefined symbol 的匹配情况。注意到上述的顺序是 a b d 而不是 a d b （虽然 a 依赖于 d），这一 BFS 的顺序，对于各种符号的覆盖和冲突的理解非常重要。这一顺序对于 compiling time linker 的检查和 runtime linker 的真实链接都是一致的，全部依赖看，都是 BFS；直接依赖看，都与编译时命令行给定的动态库顺序一致。除非在 runtime 又用了 LD_PRELOAD 这种环境变量，在 runtime 最早的时候载入了其他未定义在 NEEDED 的动态库⁴。

回到编译时 linker 检查的行为，这里有一个 one time scan 的微妙之处。也就是说，对于命令行列出的（包括按照 BFS 展开的）所有动态库，linker 的行为是按照顺序只检查一遍。如果对于一个动态库，其没有解决任何之前出现的 undefined symbol，那么该动态库将会被 compiling time linker 直接抛弃⁵，也不会被写入最终执行文件的 NEEDED 里。那么如果后边的动态库里有 undefined 符号依赖该动态库，compiling time linker 则会报错，因为compiling time linker 根本没把前边的动态库的 symbol 信息记下来。比如 gcc -la -lb main.c 本身就是错的（和平台与编译器行为有关），因为这大体相当于 ld liba.so libb.so main.o，那么 compiling time linker 会先读入 liba 的 symbol，但此时并没有任何 undefined symbol，因此 a 和 b 两库会直接舍弃，这之后才读入 main.o ，其中的 undefined symbol 没有地方去 resolve 了，因此会编译时报错。因此实践上，一定要把动态库链接的 -l flag 都放在 gcc 语句的最后。同时不同的 -l 的顺序也有讲究，如果 a 库依赖 b 库，那么命令行的顺序需要时 -la -lb，反之则会报错。如果 a 和 b 存在循环依赖（windows 上动态库此种依赖的处理与 linux 完全不同⁶），那么则需要编译时指定为 -la -lb -la，或者利用 gcc 的 --start-group flag（使用方式自行 google）。

对于编译时的按顺序检查库依赖，还有更微妙的地方。那就是对于检查的库，如果完全不提供之前 undefined symbol 的定义，则该库是直接舍弃的，既不会 compiling time 记着该库的 symbol 留待之后比对，也不会将该库的名称写入生成二进制的 NEEDED，从而 runtime linker 也不用。但如果该库有 symbol 提供了现有 undefined symbol 的定义呢？这时究竟是怎么处理的，只保留该有用的 symbol，并且 compiling linker 舍弃其他未提及的 symbol，还是一旦该库存在有用的 symbol，就由 compiling linker 记下该库所有的 symbol，留作扫描接下来的库中 undefined symbol 的匹配用？经过反复的实验，答案大致是这样的。对于动态库链接，.so 文件，其中没有更细致的对象文件的区别（so 文件不能多个合并为一个；即使以 ` -Wl,–whole-archive liba.a liba2.a -Wl,–no-whole-archive` 的形式包含了多个静态库⁷，so 文件本身仍不具有这种精细结构），此时一旦发现存在有用的 symbol，则整个 so 动态库的全部 global symbol 都会被 compiling time linker 记住，并可以提供之后的库中 undefined symbol 的 resolve。对于静态库 .a 文件，其中具有多个 .o 的精细结构，此时，compiling time linker 只会记住对应的存在有用 symbol 的 .o 文件中的所有 symbol 用于后续比对，而同一 .a 库中其他的 .o 文件将被直接舍弃，其中的 symbol 无法提供后续库 undefined symbol 的 resolve。

LD_DEBUG 与 scopes

至于 runtime linker 的工作行为，前边已经简要概述过了，这里提一下可以通过 export LD_DEBUG=all，来观察 runtime linker 的工作细节，包括库的载入顺序，搜索顺序，确定的库的位置，每个符号的搜索顺序，和确定的 undefined 符号绑定到哪个库的定义，等等。注意到这些信息往往很多，建议 LD_DEBUG=all a.out>ld.log 2>&1 将这些标准错误流导入文件，方便后续的对比搜索等。如果不想让 terminal 输入个什么，都满屏幕 log 的话，要记得及时 export LD_DEBUG= 来取消 debug 输出。LD_DEBUG 的选项，也不只有all，其他选项可以通过令该变量等于 help 查看，输出都是 all 的子集。常用的有 libs 查看具体导入库的位置，scopes 观察不同库 undefined symbol 的搜索范围，symbols 查看每个 symbol 最终 binding 的定义对应的库等等。这里提到了 scope⁸⁹ 的概念，也即每个库中的 undefined symbol 都有一个搜索范围，去哪些库找这些 symbol 的定义。这些库被组织成 scope，每个 scope 中有一些库按顺序排列，然后不同的 scope 也按顺序排列，由此从头到尾来搜索这些库，从而 resolve 该库的 undefined symbol。对于动态库，runtime 的 scope 通常只有一个 scope0，包括全部的依赖库，按照 BFS 排布。如果设定了 LD_PRELOAD ，则对应的动态库的位置在 main 程序后，在其他载入的动态库之前。想要增加 scope，主要的方式就是 dlopen API，不过关于 dlopen 这种动态调用动态库（彻底绕过 compiling linking）的方式，我们放在下节讨论。至于gcc linker 的各种花式 flag，包括 rdynamic（使得 main 中的 symbol 可以被 dlopen 的 so 内的 undefined symbol match，否则非动态库文件默认不 export symbol 供其他文件使用）¹⁰，fvisibility （隐藏动态库内部符号）, Bsymbolic（动态库内部 symbol resolve 优先自给自足，--dynamic-list 可以更精细的控制）等等，都是用来某种程度上控制符号的可见性和搜索顺序的，这里不多讲，结合本节描述的 linker 行为，很容易理解这些 flag 的含义。

dlopen

动态库除了编译时链接，还有一种运行时动态加载的方案，这就利用了 dlopen 的API。这一 API 对于脚本语言，比如 python 则更加重要。本质上 CPython 就是个 C 程序，而 import 一些动态库时，其实际上做的就是 dlopen 这些动态库，在 python 层面利用该库中的函数时，其 C 层面实际上是通过 dlsym 的 API 拿到了对应的二进制函数的入口地址。关于 dlopen 和 dlsym 的 API，可以参阅 manual¹¹。 dlopen 的运行方式，大致是这样的，按照和 runtime linker 一样的规则，根据动态库的名称 char* 找到具体的动态库并加载，同时按 BFS 的顺序加载该动态库的全部依赖库，所有库合成一个 scope，该 scope 根据 dlopen 输入的 flag，合并到或者独立于本来的 global scope。之后 resolve 该动态库中 undefined symbol 地址时，则按照先 global scope 再 local scope 的方式（某些 dlopen 的 flag，也可以将两者反序），resolve 需要的所有 undefined symbol。即使这些 dlopen 关联的 scope 并入 global scope 其位置也在根据 NEEDED loading shared library 之后。注意这里的 dlsym 找给定 symbol 和 dlopen 加载的库寻找 undefined symbol 的定义是两件事情。前者限制在了对应的动态库及其依赖库中，按 BFS 的顺序搜索；而后者则是默认从 global scope 开始，来 resolve 加载库中的 undefined symbol。

RTLD flags

由上面的简述可以看出，dlopen 这组 API 的行为非常依赖于相应的 flag，这组 flag 也即一组以 RTLD 开头的 macro，这里我们稍微论述一下这些 flag 的作用。注意到 dlopen 的 flag 是 int 型，多个 flag 时，需用 bitwise or，其实就是对应二进制不同位的 1 意义不同。

dlopen 必选 flag，RTLD_LAZY 或 RTLD_NOW，分别对应用到的 undefined 符号再去匹配，和 dlopen 时就完成所有 undefined 符号的匹配。可选 flag，RTLD_GLOBAL， RTLD_LOCAL，分别对应是否将 dlopen 的该动态库及其依赖的 scope 并入 global scope 之中。如果并入，那么后续 dlopen 的库中 undefined symbol resolve 时相当于也能利用之前导入动态库的 symbol。还有一个比较有用的是 RTLD_DEEPBIND，这一选项会改变该动态库 symbol resolve 时默认的搜索顺序为先 local scope 再 global scope。

dlsym 的动态库 handler 输入，也有两个特别的 macro 作为 pseduo handler，分别是 RTLD_DEFAULT 和 RTLD_NEXT，其分别代表在默认的 global scope 中，按顺序查找到的第一个和第二个同名符号。这一行为，为 hack 系统原来的函数，提供了很强的扩展性。

回到 Python

有了以上这些关于动态库链接加载和使用的进一步的知识，我们回来解释原来的现象。numkl 这个库是通过链接 mkl_ilp64.so 这个动态库，来实现了 lapack 8byte int 的 API。但与此同时，numpy 的 so 是动态链接的 mkl_rt.so 并转到 mkl_lp64.so，因此其 lapack interface 是 4byte int。那么当我们将两个库都导入 python 时（这总是不可避免的，因为我们需要 numpy 提供的 ndarray 类型作为 numkl 对角化函数的输入），会出现什么问题呢。

import numpy as np
from numkl import eig
n = 32767
a = np.ones((n,n))
eig.eighx(a)

运行以上脚本，我们知道当 \(n\geq 32767\) 时，numpy 提供的 eigh 会由于 4byte int lapack API 的限制而崩溃，这也是我写 numkl 库的出发点。然而运行上面的 python 脚本，还是会报内存不足而退出，这一错误明显是又用了 lp64 的 mkl interface。当我们将两行 import 的顺序颠倒，也即先 import numkl 的话，同样的脚本则没有问题，并给出了正确的结果。

为了解释这一行为，我们可以 export LD_DEBUG=all 再运行两段程序，对比其动态载入的区别。正如之前所说，脚本语言 import so，都是通过 dlopen 这一 API 实现的。只不过通过对比 log 发现，intelpython 所带的 numpy，dlopen 是具有 RTLD_GLOBAL 和 RTLD_NOW 的 flag，因此所有numpy依赖的动态库，都会 “ add *.so.1 [0] to global scope”。那么在 numpy 之后导入的 numkl，resolve 对角化需用的 dsyevd 这一函数 symbol 时，按照从 global scope 开始的匹配顺序，自然在达到 local scope 的 mkl_ilp64.so 之前，就遇到了 numpy 并进 global scope 的 mkl_lp64.so，因此即使用 numkl 的对角化 wrapper，还是把 long 压成了 int，然后调用的 4byte int 的 lapack routine，从而依旧无法对角化大矩阵。

反过来，如果先 import numkl 的话，其采用 python 默认的 dlopenflags，这一数值可通过 sys.getdlopenflags() 查看，数值内容可参考 os module 中提供的相应 flag，默认值应该是 2，也即 RTLD_LOCAL 加 RTLD_NOW。因为是 NOW，所有 undefined symbol 都在下一个 dlopen（import numpy）之前做好了链接，此时的 global scope 并没有 MKL 相关的动态库，因此 dsyevd 很自然的链接到了 local scope 中的 ilp64 的动态库。之后再 import numpy 的时候，由于之前的 numkl 所有的是 RTLD_LOCAL，因此 numpy 中的所有 undefined symbol 匹配，并不会被 numkl 影响。也就是说，先 import numkl，再 import numpy，所有内容都是正常的。以上这些 symbol 的 binding，都可以通过 LD_DEBUG 的输出信息一一验证。

我们可以进一步 hack dlopen flags 来验证我们的上述分析。我们还是保持先 import numkl，再 import numpy 的顺序，如果 import 之前设定了 sys.setdlopenflags(os.RTLD_LAZY|os.RTLD_LOCAL)，那么可以发现 numkl 对角化大矩阵还是会崩，原因很简单，虽然是先 import 的 numkl，但其实 lazy binding，也就是说 resolve dsyevd 的时候在对角化那句命令，此时 numpy 早就被导入并污染了 global scope 了。如果设定 sys.setdlopenflags(os.RTLD_LAZY|os.RTLD_GLOBAL)，那么 numkl 对角化大矩阵就正常了，但是此时 numpy 对角化所有矩阵，不论大小就都崩了。原因同样简单，由于 RTLD_GLOBAL， numkl 链接的 ilp64 动态库进入了 global scope，因此 numpy 调用 dsyevd 时，会直接使用 ilp64 中的 routine，但是该 routine 和 numpy lp64 的界面并不 match，因此无论矩阵大小都会出现错误。

总结上述实验可以看出，使用numkl的最佳姿势就是使用 python 默认的 dlopenflags，也即 RTLD_NOW 加 RTLD_LOCAL。此外先导入 numkl，再导入 numpy，这样才能使得 numkl 和 numpy 都正常运行。

最后一环：上面的分析，我们都默认了 dlopen numpy 的动态库时，flag 总是 RTLD_NOW 加 RTLD_GLOBAL。为何其不受 python 的系统 API sys.setdlopenflags() 所控制呢？通过比对 pip installed numpy 和 numpy shipped with intelpython，我发现只有后者使用了 GLOBAL 的 flag，默认的 numpy 并不会（通过 LD_DEBUG=scopes 查看）。因此问题出在 intel numpy 上，事实上，问题就在 intel numpy 的 _distributor_init.py 文件中（脚本语言大法好，闭源不能）。

import sys

class RTLD_for_MKL():
    def __init__(self):
        self.saved_rtld = None

    def __enter__(self):
        import ctypes
        try:
            self.saved_rtld = sys.getdlopenflags()
            # python loads libraries with RTLD_LOCAL, but MKL requires RTLD_GLOBAL
            # pre-load MKL with RTLD_GLOBAL before loading the native extension
            sys.setdlopenflags(self.saved_rtld | ctypes.RTLD_GLOBAL)
        except AttributeError:
            pass
        del ctypes

    def __exit__(self, *args):
        if self.saved_rtld:
            sys.setdlopenflags(self.saved_rtld)
            self.saved_rtld = None

with RTLD_for_MKL():
    from . import _mklinit

del RTLD_for_MKL
del sys

比对该文件和 numpy 原版的该文件（空文件），可以发现 intel numpy 手动加入了 RTLD_GLOBAL 的 flag。当然我一直觉得一个动态库要求 python 通过 GLOBAL flag 来加载是不太负责任，也是很容易出问题的。我并不理解 intel 注释给出的理由 “python loads libraries with RTLD_LOCAL, but MKL requires RTLD_GLOBAL” 的具体根据是什么。不过，总之这就是问题的所在。也就是说先 import numpy，再 import numkl 导致 numkl 无法对角化大矩阵这一问题，只出现在 intel numpy 上。

一个注脚：上述行为通过 export MKL_VERBOSE=1 来观察究竟是使用的 lp64 还是 ilp64 interface 是没有意义的，原因和上面的符号竞争冲突是类似的。输出 debug 信息的函数 symbol，被 resolve 到了 numpy 带进来的 mkl lp64 动态库上，因此输出的总是 lp64 MKL。但根据上面的分析，dsyevd symbol 某些情况可以正确的 assign 到 ilp64 动态库内的函数，因此对角化大矩阵还是正常的。

References