一、What is Prelink？
1.1 Prelink 简介
Prelink 是 Red Hat 开发者 Jakub Jelinek 所设计的工具。正如其名字所示，Prelink 利用事先链接代替运行时链接的方法来加速共享库的加载。它不仅可以加快起动速度，还可以减少部分内存开销，是各种 Linux 架构上用于减少程序加载时间、缩短系统启动时间和加快应用程序启动的很受欢迎的一个工具。
Linux 系统运行时的动态链接尤其是重定位 （Relocation） 的开销，对于大型系统来说是很大的。相比之下，早期 UNIX 下的 a.out 格式的老式链接方法在速度和占用内存方面有明显的优势（但不如ELF格式更灵活，能方便的构建动态共享库）。Prelink 工具是试图在保持一部分灵活性的基础上，借鉴 a.out 格式在速度和占用内存方面的优点，对 ELF 文件进行一些改进。
Prelink 工具的原理主要基于这样一个事实：动态链接和加载的过程开销很大，并且在大多数的系统上，函数库并不会常常被更动，每次程序被执行时所进行的链接动作都是完全相同的，对于嵌入式系统来说尤其如此。因此，这一过程可以改在运行时之前就可以预先处理好，即花一些时间利用 Prelink 工具对动态共享库和可执行文件进行处理，修改这些二进制文件并加入相应的重定位等信息，节约了本来在程序启动时的比较耗时的查询函数地址等工作，这样可以减少程序启动的时间，同时也减少了内存的耗用。
Prelink 的这种做法当然也有代价：每次更新动态共享库时，相关的可执行文件都需要重新执行一遍 Prelink 才能保证有效，因为新的共享库中的符号信息、地址等很可能与原来的已经不同了。这种代价对于嵌入式系统的开发者来说可能稍微带来一些复杂度，不过好在对用户来说几乎是可以忽略的。
很多 Linux 发行版上已经预装了或者已经使用了 Prelink 工具，不过我们需要适用于嵌入式平台，比如 ARM 的版本，这样我们需要到下载 Prelink 的源代码并重新编译。
1.2 Prelink 机理
从我们最熟悉的 hello world 程序开始分析：
#include 《stdio.h》
int main（int argc， const char* argv［］） {
printf（“Hello， World！\n”）;
return 0;
}
我们知道，printf 是在 c语言运行库 libc 中定义的。如果不使用动态库，也就是使用glibc 的静态库版本，链接到 a.out 中的话，那么 printf 函数的地址在运行之前就是已知的，很简单的一句地址转移就可以完成了。
可是使用动态库的话，在程序编译阶段，我们是无法得知 printf 的函数地址，因为动态库的加载的内存地址是随机的。那么对于动态库的情况，针对 printf 是如何寻址的呢？
在程序启动时，当调用 printf 的时候，程序会将处理权交给 loader，由其负责在进程以及其链接的动态库中查找 printf 的函数地址。由于 loader 不知道 printf 是在哪个动态库，所以它将在整个进程和动态库的范围内查找。更糟糕的是在 C++++ 程序中，符号的命名是类名+函数名，这导致在做字符串比较时，往往直到字符串的结尾才能获得结果。
这就导致了，在进程启动过程中，符号查找往往占据了大部分时间。据统计，在 Linux 的 KDE 进程中启动过程中，符号查找表竟占据了进程启动 80% 的时间。有没有办法来改进呢？
如果进程在运行前，就能获知动态库的加载地址，那么函数调用的地址就应该是已知的，我们就可以通过修改执行程序，来避免符号的查找。从而节省进程启动的时间。
实际上 Prelink 正是这么做的。Prelink 最早是在 Redhat 中引用的，用来加速 KDE 的启动速度。那时侯 Prelink 作为系统的一个进程，不定期的启动，对系统中的进程和动态库进行优化，这在系统中进程和动态库不怎么变化的情况下非常有用。
在做 Prelink 时，需要为其指定需要做 Prelink 的进程和动态库的目录。Prelink 需要做以下几件事情：
分析所有的进程和动态库，为每个动态库指定一块唯一的（虚拟）内存地址；
分析进程和动态库中，所有需要重定位的函数、全局变量等，用 loader 进行符号查找，对齐地址进行解析；
修改进程中和动态库的二进制文件；
众所周知，在 32 位 Linux 操作系统上有 4G 的地址空间，3G 以上为操作系统使用，0000000~4000000 归进程的代码段、数据段和堆段使用，从 3G 往下归栈段使用。基本上我们可以认为从 1G～3G 的地址空间可以用来指定动态库的加载地址，地址空间还是很丰富的。
凡事总有万一，如果地址空间不够怎么办呢？Prelink 关于这个问题，做了两个约定：
总是一同出现的动态库，其动态库的加载地址一定不能重叠；
总是不同时间段出现的动态库，其动态库的加载地址可以重叠；
有了这两个约定之后，基本上就可以保证，为每个动态库指定加载地址，从而在运行前就能获知函数和全局变量等符号的地址。