第 4 章 存储空间分配 $Revision: 2.3 $ $Date: 1999/06/15 03:30:36 $ 链接器或加载器的首要任务是存储分配.一旦分配了存储空间后,链接器就可以继续 进行符号绑定和代码调整.在一个可链接目标文件中定义的多数符号都是相对于文件内的存 储区域定义的,所以只有存储区域确定了才能够进行符号解析. 与链接的其它方面情况相似,存储分配的基本问题是很简单的,但处理计算机体系结 构和编程语言语义特性的细节让问题复杂起来.存储分配的大多数工作都可以通过优雅和相 对架构无关的方法来处理,但总有一些细节需要特定机器的专门技巧来解决. 段和地址 每个目标或可执行文件都会采用目标地址空间的某种模式.通常这里的目标是目标计 算机的应用程序地址空间,但某些情况下(例如共享库)也会是其它东西.在一个重定位链 接器或加载器中的基本问题是要确保程序中的所有段都被定义并具有地址,并且这些地址不 能发生重叠(除非有意这样). 每一个链接器输入文件都包含一系列各种类型的段.不同类型的段以不同的方式来处 理.通常,所有相同类型的段,诸如可执行代码段,会在输出文件中被合并为一个段.有时 候段是在其它段的基础上合并得到的(如 Fortran 的公共块),以及在越来越多的情况下 (如共享库和 C+专有特性),链接器本身会创建一些段并将其放置在输出中. 存储布局是一个“两遍“的过程,这是因为每个段的地址在所有其它段的大小未确定 前是无法分配的. 简单的存储布局 在一种简单而不现实的情形下,链接器的输入文件包含一系列的模块,将它们称为 M1, M2, . Mn,每一个模块都包含一个单独的段,从位置 0 开始长度依次为 L1, L2, . Ln,并 且目标地址空间也是从 0 开始.如图 1 所示. - 图 4-1:单独段的存储空间分配 从位置 0 开始的多个段按照一个跟着另一个的方式重定位 - 链接器或加载器依次检查各个模块,按顺序分配存储空间.模块 Mi 的起始地址为从 L1 到 Li-1 相加的总和,链接得到的程序长度为从 L1 到 Ln 相加的总和. 多数体系结构要求数据必须对齐于字边界,或至少在对齐时运行速度会更快些.因此 链接器通常会将 Li 扩充到目标体系结构最严格的对齐边界(通常是 4 或 8 个字节)的倍数. 例 1:假定一个称为 main 的主程序要与三个分别称为 calif,mass 和 newyork 的子例程 链接(按照地理位置划分风险投资).每个例程的大小为(16 进制数字): 名称尺寸 - ain1017 calif 920 ass 615 newyork1390 假定从 16 进制的地址 1000 处开始分配存储空间,并且要求 4 字节对齐,那么存储分配 的结果可能是: 名称位置 -ain1000 - 2016 calif2018 - 2937 ass2938 - 2f4c newyork2f50 - 42df 由于对齐的原因,2017 处的一个字节和 2f4d 处的三个字节被浪费了,但无须忧虑. 多种段类型 除最简单格式外所有的目标格式,都具有多种段的类型,链接器需要将所有输入模块 中相应的段组合在一起.在具有文本和数据段的 UNIX 系统上,被链接的文件需要将所有的 文本段都集中在一起,然后跟着的是所有的数据,在后面是逻辑上的 BSS(即使 BSS 在输出 文件中不占空间,它仍然需要分配空间来解析 BSS 符号,并指明当输出文件被加载时要分配 的 BSS 空间尺寸).这就需要两级存储分配策略. 现在每一个模块 Mi 具有大小为 Ti 的文本段,大小为 Di 的数据段,以及大小为 Bi 的 BSS 段,如图 2 所示. - 图 4-2:多种段的存储分配 按类型将文本,数据和 BSS 段分别归并 - 在读入每个输入模块时,链接器为每个 Ti,Di,Bi 按照(就像是)每个段都各自从位置 0 处开始的方式分配空间.在读入了所有的输入文件后,链接器就可以知道这三种段各自总 的大小 Ttot,Dtot 和 Btot.由于数据段跟在文本段之后,链接器将 Ttot 加到每一个数据段所分 配的地址上,接着,由于 BSS 跟在文本和数据段之后,所以链接器会将 Ttot,Dtot 的和加到每 一个 BSS 段分配的地址上. 同样,链接器通常会将分配的大小按照对齐要求扩充补齐. 段与页面的对齐 如果文本和数据被加载到独立的内存页中,这也是通常的情况,文本段的大小必须扩 充为一个整页,相应的数据和 BSS 段的位置也要进行调整.很多 UNIX 系统都使用一种技巧 来节省文件空间,即在目标文件中数据紧跟在文本的后面,并将那个(文本和数据共存的) 页在虚拟内存中映射两次,一次是只读的文本段,一次是写时复制(copy-on-write)的数 据段.这种情况下,数据段在逻辑上起始于文本段末尾紧接着的下一页,这样就不需扩充文 本段,数据段也可对齐于紧接着文本段后的 4K(或者其它的页尺寸)页边界. 例 2:我们将例 1 扩展,使得每个例程都有文本,数据和 BSS 段.字对齐要求还是 4 个 字节,但页大小为 0x1000 字节. 名称文本段数据段 BSS 段 - ain1017 32050 calif 920 217100 ass 615 300840 newyork139012131400 (均为 16 进制数字) 链接器首先分配文本段,然后是数据段,接着是 BSS.注意这里数据段起始于页边界 0x 5000,但 BSS 紧跟在数据的后面,这是因为在运行时数据和 BSS 在逻辑上是一个段. 名称文本段数据段 BSS 段 - ain1000-20165000-531f695c-69abcalif2018-29375320-544669ac-6aab ass2938-2f4c5448-57476aac-72eb newyork2f50-42df5748-695a72ec-86eb 在 0x42e0 到 0x5000 之间的页结尾处浪费了一些空间.虽然 BSS 段的结束位置在页面中 部的 0x86eb 处,但程序们普遍都会紧跟其后分配“堆“空间. 公共块和其它特殊段 上面这种简单的段分配策略在链接器处理的 80%的存储分配中都工作的很好,但剩下的 那些情况就需要用特殊的技巧来处理了.这里我们来看看比较常见的几个. 公共块 公共块存储是一个可以追溯到 50 年代 Fortran I 时的特性.在最初的 Fortran 系统中, 每一个子程序(主程序,函数或者子例程)都有各自局部声明和分配的标量和数组变量.同 时还有一个各例程都可以使用的存储标量和数组的公共区域.公共块存储被证明是非常有用 的,并且在后续 Fortran 中单一的公共块(就是我们现在知道的空白公共块,即它的名称是 空白的)已经普及为多个可命名的公共块,每一个子程序都可以声明它们所用的公共块. 在最初的 40 年中,Fortran 不支持动态存储分配,公共块是 Fortran 程序用来绕开这个 限制的首要工具.标准 Fortran 允许在不同例程中声明不同大小的空白公共块,其中最大的 尺寸最终生效.Fortran 系统们无一例外的都将它扩展为允许以不同的大小来声明所有类型 的公共块,同样还是最大的尺寸最终生效. 大型的 Fortran 系统经常会超过它们所运行系统的内存容量限制,在没有动态内存分配 时,程序员不得不频繁的重新创建软件包,压缩尺寸来解决软件包遇到的此类问题.在一个 软件包中除一个之外的其它子程序都将公共块声明为只有一个元素的数组.剩下的那个子程 序声明所有公共块的实际大小,并在程序启动时将这些尺寸都保存在其余软件包可以使用的 (在另一个公共块中的)变量中.这样就可以通过修改和重新编译定义这些公共块的一个例 程,来调整公共块的尺寸,然后再重新链接. 从 60 年代开始 Fortran 增加了 BLOCK DATA 数据类型来为任意公共块(空白公共块除外, 这是为数不多的限制)的部分或全部来指明局部初始数据值,这在某种程度上更复杂了.通 常用来初始化公共块的在 BLOCK DATA 中的公共块尺寸,也在链接时被用来当作该公共块 的 实际大小. 在处理公共块时,链接器会将输入文件中声明的每个公共块当作一个段来处理,但并 不会将这些段串联起来,而是将相同名称的公共块重叠在一起.这里会将声明的最大的尺寸 作为段的大小,除非在某一个输入文件中存在该段的已初始化的版本.在某些系统上,已初 始化的公共块是一个单独的段类型,而在另一些系统上它可能只是数据段的一部分. UNIX 链接器总是一贯支持公共块,甚至从最早版本的 UNIX 都具有一个 Fortran 子集的 编译器,并且 UNIX 版本的 C 语言传统上会将未初始化的全局变量作为公共块对待.但在 ELF 之前的 UNIX 目标文件只有文本,数据和 BSS 段,没有办法直接声明一个公共块.作为一个 特殊技巧,链接器将未定义但具有非零初值的符号当作是公共块,而该值就是公共块的尺寸. 链接器将遇到的此类符号中最大的数值作为该公共块的尺寸.对于每一个公共块,它在输出 文件的 BSS 段中定义了相应的符号,在每一个符号的后面分配所需要的空间. - 图 4-3:Unix 公共块 在 BSS 末尾的公共块 -C+重复代码消除 在某些编译系统中,C+编译器会由于虚函数表,模板和外部 inline 函数而产生大量的 重复代码.这些特性的设计是隐含的期望那种程序所有部分都可以被运行的环境.一个虚函 数表(通常简称为 vtbl)包含一个类的所有虚函数(可以被子类覆盖的例程)的地址.每 个带有任何虚函数的类都需要一个 vtbl.模板本质上就是以数据类型为参数的宏,并能够 根据特定的类型参数集可以扩展为特定的例程.确保是否存在一个对普通例程的引用可供调 用是程序员的责任,就是说对如 hash(int)和 hash(char *)每一类 hash 函数都有确定的定义, hash(T)模板可以根据程序中使用 hash 函数时不同的参数数据类型创建对应的 hash 函数. 在每个源代码文件都被单独编译的环境中,最简单的方法就是将所有的 vtbl 都放入到 每一个目标文件中,扩展所有该文件用到的模板例程和外部 inline 函数,这样做的结果就 是产生大量的冗余代码. 最简单的方法就是在链接时仍然将那些重复代码保留着.那么得到的程序肯定可以正 确的工作,但代码会膨胀的比理想尺寸大三倍或者更多. 在那些使用简单链接器的系统上,某些 C+系统