连接器和加载器::第2章 架构问题
原著：John R. Levine
原文：收藏
翻译：lover_P
连接器和加载器，连同编译器和汇编器，都能够敏锐地感觉到架构的细节，既包括硬件架构也包括其目标计算机上的操作系统的架构转换需求。在这一章中我们涵盖了足够多的计算机架构以理解连接器所必须完成的工作。这里所有对于计算机
架构的描述都故意作得不完整，而且省略了并不影响连接器的部分，如浮点运算和I/O。
硬件架构的两个方面影响着连接器：程序地址和指令格式。连接器要做的一件事是修改数据存储器和指令中的地址和偏移量。无论是修改数据还是指令，连接器都必须确保它的修正能够匹配计算机所使用的地址方案；在修正指令时它还必须进一步确保其修正不会导致无效指令。
在这一章的结束，我们还关注了地址空间架构，也就是说，一个程序必须工作在哪些地址的集合上。
[内容]
每个操作系统都为运行在它上面的程序提供了一个应用程序二进制接口（ABI,
Application Binary Interface）。ABI由应用程序在操作系统上必须遵守的编程约定（programming convertion）构成。ABI总是包含一组系统调用（system
call）和调用（invoke）系统调用的技巧，以及一些关于程序能够使用哪些存储器的规则和使用机器寄存器的规则。从应用程序的观点看，ABI和部分的系统架构以及底层的硬件架构同样重要，因为一个程序无论违反哪一方的约束都会同样引起失败。
在很多情况下，连接器都要完成有关遵从ABI的工作中的重要部分。例如，如果ABI要求每个程序都包含一个罗列了程序中所有例程所用到的静态数据的地址的表，连接器通常就要通过收集连接到程序中的所有例程中的地址信息来建立这个表。ABI最能影响连接器的方面就是对标准程序调用的定义，我们将在这一章稍后的部分回到这一主题。
每台计算机都包含一个主存储器。主存储器总是以一个存储位置的排列出现，其中每个存储位置都有一个数值地址。
这个地址从零开始，增长到由一个地址中的位数所决定的一个较大的数值。
每个存储位置都由数量固定的位（bit）所构成。在过去的50年里，计算机被设计为每个存储位置由多至64位少至1位构成，但是现在几乎所有的计算机成品每个地址字节都有8位。由于很多计算机要处理的很多数据，尤其是程序地址，都比8位要多，因此计算机还可以通过将邻近的字节分组来处理16、32甚至64或128位的数据。在一些计算机上，特别是来自IBM和Motorola的计算机，其多字节数据中的第一个（地址数值较小的）字节是最重要的字节；而其他的，特别是DEC和Intel，这一位是最不重要的，如图1所示。《Gulliver's
Travels》中将IBM/Motorola字节顺序称为大尾数的（big-endian），而将DEC/Intel架构称为小尾数的（little-endian）。
图2-1：字节可寻址存储器
通常的存储地址描述
多年以来对这两种架构的优点的比较引起了激烈的争论。实际上，如何选择字节顺序最大的问题在于与旧系统的兼容性，因为在字节顺序相同的机器之间移植程序和数据要比在字节顺序不同的机器之间容易得多。目前很多芯片的设计都能够支持各种数据，可以通过芯片
跳线、系统启动程序，或者少部分情况下甚至可以由每个应用程序来作出选择。（在这些双掷开关芯片上，字节顺序是通过加载和存储指令的变化来处理的，但字节顺序具有固定编码的指令却不能。这种细节使得连接器作者的生活丰富多彩。）
多字节数据通常必须被对齐（align）到自然的边界
（boundary）上。也就是说，四字节数据应该被对齐到一个四字节的边界，双字节应该对齐到双字节，以此类推。还可以这样想：一个N字节的数据应该至少有log2N个为零的低位。在一些系统（Intel
x86、DEC
VAX、IBM370/390）上，未对齐的数据引用会导致工作效率降低的代价，而在其他一些系统（很多RISC芯片）上，未对齐的数据会导致一个程序的失败。即使在未对齐数据不会导致程序失败的系统上，性能的损失也通常足够值得我们在可能的时候去努力管理对齐。
很多处理器还对程序指令有对齐要求。大部分RISC芯片要求指令必须被对齐到四字节边界。
每个架构还都定义了寄存器（register）——一小组长度固定的高速存储器，其地址可以由程序指令直接引用。一种架构和另一种架构的寄存器数量是不同的，从Intel架构（IA,
Intel
Architecture）中的至少8个到一些RISC设计中的32个不等。寄存器通常总是和程序地址具有相同的大小，也就是说，在一个32位地址的系统上，寄存器是32位的，而在64位地址的系统上，寄存器是64位的。
当程序运行的时候，它从存储器中读取或向存储器写入数据，这些存储器由程序中的指令来检测。指令自身也存放在存储器中，通常是放在一个和程序数据不同的部分中。指令理论上是按照
它们所存储的顺序执行，除了跳转（jump）指令指定一个的新的地址并开始执行（那里的）指令。（一些架构使用术语分支（branch）来表示部分或所有的跳转，但我们在这里将它们全部
称为跳转。）每条指令都引用了数据存储器，而且每个跳转都或者指定了数据加载或存储的地址、或者指定了指令要跳转的位置。所有的计算机都有很多指令格式和地址格式规则，连接器必须能够像在指令中处理重定位地址那样处理这些规则。
尽管在过去的数年中计算机设计者们提出了很多不同的复杂的地址架构，但目前的成品计算机都有一个相对简单的地址架构。（设计者们发现很难为复杂的架构建立一个快速的版本，而且编译器极少能对复杂的地址特性作出很好的利用。）我们以三种架构为例：
IBM
360/370/390（我们仅提到370）。尽管这是现在仍在使用的最古老的架构之一，尽管35年来新特性的修修补补使它破旧不堪，它在芯片上实现后
（译注：IBM最早的实现可不是芯片哦）的效率依然可以与现代的RISC相媲美。
SPARC
V8和V9。一个流行的RISC架构，拥有相当简单的地址。V8使用32位寄存器和地址，V9加入了64位寄存器和地址。SPARC的设计和其他RISC架构如MIPS和Alpha类似。
Intel 386/486/Pentium（后来的x86）。仍然在使用的一种不可思议的和不规则的架构，但不可否认是最流行的。
每种架构都有很多不同的指令格式。我们只讲解与程序和数据地址相关的格式细节，因为这是影响到连接器的主要细节。370使用一些格式的数据引用和跳转，而SPARC使用不同的格式，x86既有公共的格式又有不同的格式。
每条指令都由一个检测应该完成什么指令的操作码和一个或多个操作数构成。操作数可能被编码到指令本身中（立即数）或者定位到存储器中。存储器中的每个操作数的地址都必须以某种方式进行计算。有的时候这个地址被包含在指令中（直接寻址）。更常见的是这个地址可以在某一个寄存器中找到（寄存器间接寻址），或者通过为寄存器中的内容加上一个常数来计算。如果寄存器中的值是一个存储器区域的地址，而指令中的常数是想得到的数据在这段存储器区域中的偏移量，则这种机制
称为基址寻址。基址和索引地址之间的差别不是定义良好的，很多架构合并了它们，例如，370中有一种寻址方式是在指令中将两个寄存器和一个常数相加，可以随意地称这两个寄存器中的一个为基址寄存器而另一个为索引寄存器，尽管它们表示相同的地址。
其他一些更为复杂的地址计算架构仍在使用，但它们中的大部分都不需要连接器来操心，因为它们不包含任何需要连接器来调整的域。
一些架构使用长度固定的指令，而另一些使用长度可变的指令。所有的SPARC指令都是四个字节长，对齐到四字节边界。IBM
370指令可以是2、4或6个字节长，其中第一个字节的前两位用于检测指令的长度和格式。Intel
x86指令可以是1字节到14字节之间的任意长度。其编码非常复杂，部分原因是由于x86最初被设计用于存储器有限的环境，因此要采用一个密集的指令编码；另一部分原因是286、386中添加了新的指令，并且以后的芯片还必须要用到现存的指令集中没有用到的位模式。幸运的是，从连接器作者的角度看，连接器必须进行调整的地址和偏移量域都出现在字节边界，因此连接器通常不必关心指令编码。
在最早的计算机中，存储器非常小，而且指令包含的地址域足够大，能够包含计算机中所有存储位置的地址，这种方式现在称为直接寻址。到了20世纪六十年代早期，可定址存储器变得大到如果一个指令集在每条指令中包含完整的地址，将会占用过多的仍然珍贵的存储器。为了解决这一问题，计算机架构在一些或所有存储器引用指令中抛弃了直接寻址，而是使用索引和基址寄存器来提供地址中使用的大部分或所有的位。这允许指令变得更短，但要以更为复杂的程序为代价。
在没有直接寻址的架构上，包括IBM
370和SPARC，程序在对待数据地址时会有一种“自举（bootstrapping）”问题。一个例程使用寄存器中的基址来计算数据地址，而将这个基址放入寄存器的标准方法是把它从某个存储器位置加载到寄存器，但这又需要寄存器中有另外一个基址。自举问题就是要在程序的开始
将低一个基址值放入寄存器，以及接下来保证每个例程都拥有其所使用数据的地址的基址值。
每个ABI都使用硬件定义的调用指令和寄存器/存储器使用约定的组合来定义一个标准的程序调用序列。一个硬件调用指令保存返回地址（调用指令之后的一条指令的地址）并跳转到调用程序。在具有硬件堆栈的架构如x86上，返回地址被压入堆栈；而在其他架构上，返回地址被保存在寄存器中，由软件负责在必要的时候将它存放到存储器中。具有堆栈的架构通常有一个硬件返回指令用来从堆栈中弹出返回地址并跳转到这个地址，而其他架构使用一个“寄存器内地址分支（branch
to address in register）”指令来返回。
在一个程序中，数据地址有四种类型：
调用者可以传递参数（argument）给程序。
局部变量（local variable）在程序中分配并在程序返回前释放。
局部静态变量（local static
variable）数据存放在存储器中的一个固定区域并属于该程序私有。
全局静态（global
static）数据存放在存储器中的一个固定区域并可以由任何不同的程序引用。
堆栈存储器中分配给一个单独的程序调用的块称为堆栈帧（stack
frame）。图2展示了一个典型的堆栈帧。
图2-2：堆栈帧存储器布局
堆栈帧的图式
参数和局部变量通常分配在堆栈上。某一个寄存器作为堆栈指针，这个寄存器可以用作一个基址寄存器。在由SPARC和x86所使用的这种架构的一个通用的变体中，会在程序开始的时候从堆栈指针处加载一个分立的帧指针或基址指针。这使得将一个可变大小的对象压入堆栈——将堆栈指针寄存器中的值改变为一个难以预知的值，但仍然保证程序地址参数和局部变量相对帧指针有固定的偏移量而不会在程序运行的过程中改变——成为可能。（译注：这句话很难理解，英文原文也很难：This
makes it possible to push variable sized objects on the stack, changing the
value in the stack pointer register to a hard-to-predict value, but still lets
the procedure address argument and locals at fixed offsets from the frame
pointer which doesn't change during a procedure's
execution. 请多读几遍，试着理解其中的意思。如果您有更好的翻译方法，请告诉我！深表感谢！）假设堆栈从高地址向低地址生长，并且帧指针指向存放返回地址的存储器地址，则参数相对帧指针具有较小的绝对偏移量，而局部变量具有负的偏移量。操作系统通常在一个程序开始之前设置初始的堆栈指针寄存器，因此程序只需要在其弹出和压入数据所必要的时候才更新该寄存器。
对于局部和全局静态数据，编译器可以生成一个表，这个表包含了一个例程所引用的所有静态对象的指针。如果某一个寄存器中包含了这个表的一个指针，该例程就可以通过将表指针寄存器（中的内容）加载到另一个寄存器中，并将这个寄存器作为基址寄存器来获得对象指针，从而定位任何一个所期望的静态对象。这里所需的技巧就是如何将表的地址放到第一个寄存器中。在SPARC上，程序可以使用一系列带有立即数的指令来将这个表地址加载到寄存器中，而在SPARC或370上，程序可以使用子例程调用指令的一个变体来
将程序计数器（存放了当前指令地址的寄存器）加载到一个基址寄存器中，但由于我们后面将要讨论到的原因，这些技术在库代码中会引起一些问题。一个更好的解决方案是强制将加载表指针的工作交给例程调用者，因为调用者自己的表指针已经加载，而且它可以通过自己的表来获得被调用例程的表的地址。
图3展示了一个典型的例程调用序列。Rf是帧指针，Rt是表指针，而Rx是一个临时使用的寄存器。调用者在它自己的堆栈帧中保存它自己的表指针，然后既加载被调用例程的地址也要将被调用例程的指针表的地址加载到寄存器，然后完成调用。接下来，被调用例程可以通过Rt中的表指针找到所有它所需的数据，包括它运行中调用的所有例程的地址和表指针。
图2-3：理想的调用序列
... 将参数压到堆栈上 ...
store Rt → xxx(Rf) ; 在调用者的堆栈帧上保存调用者的表指针
load Rx ← MMM(Rt) ; 将被调用例程的地址加载到临时寄存器中
load Rt ← NNN(Rt) ; 加载被调用例程的表指针
call (Rx) ;
调用Rx中的地址处的例程
load Rt ← xxx(Rf) ; 恢复调用者的表指针
很多优化通常是可行的。在很多情况下，一个模块中的所有例程共享一个单独的指针表，在这种情况下模块内（intra-module）的调用就无需改变表指针。SPARC约定一个整个的库共享一个单独的表，这个表由连接器创建，因此表指针寄存器在模块内调用中能够保持不变。来自相同模块的调用通常可以由“调用”指令的某一个版本来完成，该版本将被调用例程的偏移量编码到指令中，这可以避免将例程的地址加载到一个寄存器中。有了这两种优化，对相同模块内的一个例程的调用序列将减少到只有一条单独的指令。
现在我们回到地址的自举问题，这个表指针链该如何开始？如果每个例程都需要前面的例程来完成其表指针的加载，那么，初始的例程如何获取其指针？答案有很多，但都包括特殊代码。主程序的表可能存放在一个固定的地址，或者初始的指针值可能指向可执行文件以使得操作系统可以在程序运行之前加载它（的表指针）。无论采用什么技巧，这总是需要连接器的帮助。
我们现在来更具体地看看我们（介绍）的三种架构上的程序定址数据值的方法。
二十世纪60年代（IBM）生产的System/360具有一个非常简易的数据定址机制，在从360进化到370和390的几年间它却变得越来越复杂。每条引用了数据存储器的指令都需要通过将指令中的一个12位的无符号偏移量加到一个基址寄存器和一个可能的索引寄存器上。它有16条常规指令，每条都是32位，编号从0到15，它们中除了一个之外都可以用作索引寄存器。如果在一次地址计算中指定了寄存器0，则使用数值0而不是该寄存器中的内容。（寄存器0的存在用于算术运算而不是地址运算。）在使用某一寄存器中的值作为跳转目标的那些指令中，使用寄存器0表示不要跳转。
图4显示了主要的指令格式。一条RX指令包含一个寄存器操作数和一个单独的内存操作数，其地址通过将指令中的偏移量加上一个基址寄存器（中的内容）和一个索引寄存器（中的内容）来计算。通常索引寄存器是0，因此地址只是基址加偏移量。在RS、SI和SS格式中，12位的偏移量被加到一个基址寄存器。一条RS指令
带有一个内存操作数，以及一个或两个存在于寄存器中的其他操作数。一条SI指令具有一个内存操作数，另一个操作数是指令中的一个8位立即数。一条SS指令有两个内存操作数，这是一个存储器到存储器的操作。RR格式具有两个寄存器操作数而没有任何内存操作数，尽管有些RR指令将其中的一个或全部寄存器作为内存指针。370和390仅在这些格式
的值上作了一些较小的改动，而没有引入不同的数据地址格式。
图2-4：IBM370指令格式
IBM指令格式RX、RS、SI、SS
（图中所有的字母-数字对中的数字都应该是下标，如R2）
指令可通过将基址寄存器设置为0来直接定址内存中最低的4096个位置。这一能力基本上只有低级系统程序才具有，而应用程序都不会用到，它们总是使用基址寄存器来寻址。
注意在所有三种指令格式中，12位的地址偏移量总是存放在16位对齐的半个字中的低12位中。这使得在目标文件中指定固定的地址偏移量而无须引用指令格式成为可能，因为偏移量格式总是相同的。
原始的360具有24位地址，一个这样的地址在内存或寄存器中存放在32位字中的低24位中，而忽略高8位。370将地址扩展到31位。不幸的是，很多程序——包括OS/360——最流行的操作系统——在内存中的32位地址字的高位字节中存放了标志或其他数据，因此无法以一种明显的方式将地址扩展到32位还能支持现有的目标代码。取而代之，该系统具有24位和32位模式，CPU随时将地址解释为24位或32位。硬件和软件的联合构成一种约定，如果地址字的最高位被置位则包含31位地址，而最高位被清空则包含24位地址。结果，一个连接器必须能够处理24位和31位地址，因为那些依赖于很久以前写就的例程的程序需要在两种模式之间作出转换。出于历史原因，370连接器还能够处理16位地址，因为早期的360系列通常具有64K或更小的主存储器，并且程序使用半个字长的指令来维护地址值。
稍后的370和390模型添加了段地址空间，这有些类似于x86系列。这些特性使得操作系统可以定义多个可由程序定址的31位地址空间，这需要极其复杂的访问控制定义规则和地址空间转换。就我所知，没有支持这些特性的编译器或连接器，这些特性主要应用于高性能的数据库系统，因此我们也不深入地讨论它。
370上的指令定址也是相对简单的。在原始的360上，跳转（一直被称为分支指令）都是RR或RX格式的。在RR跳转中，第二个寄存器操作数包含了跳转目标，寄存器0表示没有跳转。在RX跳转中，内存操作数是跳转目标。程序调用即分支和连接（被31位地址中的分支和存储所取代），它将返回地址存放在一个特定的寄存器中并跳转到RR形式中第二个寄存器中的地址，或跳转到RX格式中的第二个操作数所表示的地址。
为了能够跳转到一个例程内部，该例程必须建立“可定址性”，也就是说，RX指令所使用的基址寄存器必须指向（或至少是接近）该例程的开始处。通过约定，寄存器15包含了一个例程的入口点地址，并可用作一个基址寄存器。另一种可选的方法是，使用0寄存器的RR分支和连接或分支和存储指令会将后续指令放到第一个操作数寄存器但不跳转，而且当前面的寄存器内容未知的时候还可以用来设置基址寄存器。由于RX指令含有一个12位的偏移量域，因此一个单独的基址寄存器可以“覆盖”一个4K的代码块。如果一个例程比4K大，则需要多个基址寄存器来覆盖该例程的所有代码。
390为所有的跳转引入了相关的形式。在这些新的形式中，所有的指令都包含一个单独的16位偏移量，在查找跳转目标时这个偏移量被逻辑地左移一位（因为指令要对其到每一个字节）并加上指令的地址。这些新格式不需要任何寄存器来计算地址，并且允许在+/-64K字节内进行跳转，除了一些巨大的例程外，这足够进行例程内（intra-routine）跳转了。
SPARC作为一个精简指令集（Reduced Instruction
Set）处理器越来越接近其名字了，尽管其架构已经经历了九个版本，原来简单的设计也变得越来与复杂。SPARC版本一直到V8都是32位架构，V9扩展为64位架构。
SPARC有四个主要的指令格式和31个次要的指令格式。图5给出了四个跳转格式和两个数据地址模式。
在SPARC V8种，有31个通用寄存器，每个32位，编号从1到31。寄存器0是一个伪寄存器，它总是包含0值。
一种不同寻常的寄存器窗（Register
Window）方案尝试将程序调用和返回时保存和恢复的寄存器数量减至最小。这些“窗”对连接器的作用很小，因此我们不准备深入地讨论它们。（寄存器窗起源于SPARC的祖先——伯克利RISC的设计。）
数据引用使用两种地址模式中的一个。一种模式是通过将两个寄存器（中的内容）相加来计算地址。（如果其中一个寄存器中已经包含了目标地址，则可以将另一个寄存器设置为R0。）另一种模式是将指令中的一个13位的带符号偏移量加到一个基址寄存器（中的内容）上。
SPARC汇编器和连接器支持一个使用两条指令序列的伪指令地址方案。这两条指令是SETHI——将22位立即数装入一个寄存器的高22位并将低10位置零——后面紧跟一个OR指令——将13位立即数或到该寄存器的低位部分。汇编器和连接器会将32位的目标地址安排到这两条指令中。
图2-5：SPARC
30位调用、22位分支和SETHI、19位分支、16位分支（仅V9），op R+R、opR+I13
程序调用指令和大多数跳转指令（SPARC术语中称作分支）都使用长度范围在16至30位之间的变长分支偏移量相关地址。无论偏移量大小如何，跳转指令都会将其向左移两位，由于所有指令都必须位于四字节字（four-byte
word）地址，因此要用符号位将结果扩展到32位或64位，并将这个值加到跳转或调用指令的地址上来取得目标地址。调用指令使用一个30位的偏移量，这意味着它可以到达32位V8地址空间的任何一个地址。调用指令将返回地址存放在寄存器15中。各种跳转指令使用一个16、19或22位的偏移量
，这足够跳转到任何一个具有合理大小的例程中的任何地址。其中16位格式将偏移量划分为一个2位的高位部分和一个14位的低位部分分别放在指令字中的不同部分，但这不会给连接器带来太大的麻烦。
SPARC还具有一种“跳转并连接（Jump and
Link）”机制，它以和数据引用指令完全相同的方式来计算目标地址——或者将两个源寄存器相加，或者将一个源寄存器和一个常数偏移量相加。它也可以将返回地址存储到一个目标寄存器中。
程序调用使用调用指令或“跳转并连接”，将返回地址存放在寄存器15并跳转到目标地址。程序的返回使用JMP8[R15]，返回到调用指令之后的两个指令处。（SPARC调用和跳转是“延迟的（delayed）”并且可以选择地执行跳转指令后面的指令或在跳转之前调用。）
SPARC
V9将所有的指令扩展至64位，为老的32位程序使用每个寄存器中的低32位。所有现存的指令继续和以前一样工作，除了寄存器操作数现在是64位而不是32位。现在的加载和存储指令处理64位数据，并且新的分支指令可以测试前一条指令的结果是32位还是64位。SPARC
V9没有添加新指令来合成完整的64位地址，也没有添加新的调用指令。完整地址可以通过冗长序列（lengthy
sequences）来建立，将地址划分为两个32位部分放在单独的寄存器中，并使用SETHI和OR，将高32位向左移，再将两部分或到一起。实际上，64位地址可以通过一个指针表来加载，模块间调用可以从这个表中将目标例程的地址加载到寄存器，再使用“跳转并连接”来完成调用。
Intel
x86架构是至今为止我们所讨论的三种架构中最复杂的。它特色化了不均匀指令集和分段地址。它拥有六个32位通用寄存器，称为EAX、EBX、ECX、EDX、ESI和EDI，以及两个主要用于地址的寄存器EBP和ESP，还有六个16位专用寄存器CS、DS、ES、FS、GS和SS。每个32位寄存器的低一半可以用作16位寄存器，称作AX、BX、CX、DX、SI、DI、BP和SP。而从AX到DX寄存器中的低字节和高字节又可以作为8位寄存器，称为AL、AH、BL、BH、CL、CH、DL和DH。在8086、186和286中，很多指令要求它们的操作数位于特定的寄存器中，但在386和以后的芯片中，很多但不是所有需要特定寄存器的功能被一般化为可以使用任何寄存器。ESP是硬件堆栈指针，并且总是包含当前堆栈的地址。EBP指针通常被用作一个帧寄存器，它指向当前堆栈帧的基址。（该指令集值得表扬但不一定非要这样。）
任何时候x86都可以在三种模式之一下运行：实模式——模仿原始的16位8086，16位保护模式——在286时加入，或32位保护模式——在386时加入。这里我们主要讨论32位保护模式。保护模式带来了令x86声名狼藉的内存分段，但我们将暂时忽略它。
很多需要对数据在内存中的地址进行寻址的指令都使用一个通用指令格式，如图6所示。（
它们都不能使用该架构进行了特殊定义的寄存器，如ESP，它总是被PUSH和POP指令用于堆栈地址。）地址的计算是通过将这些值加在一起：指令中的一个1、2或4字节的带符号位移（displacement）值、一个可以是任何32位寄存器的基址寄存器和一个可选的可以是任何32位寄存器的索引寄存器但除了ESP。索引可以被逻辑地左移0、1、2或3位，以使得对多字节址进行索引变得容易。
图2-6：通用x86指令格式
一或两字节的操作码、可选的mod R/M字节、可选的s-i-b字节、可选的1、2或4字节位移
尽管一条单独的指令可以将位移、基址和索引都包含在内，但大部分指令只使用一个能够提供直接寻址的32位位移，或一个能够提供堆栈寻址和指针引用的基址加一或两字节的位移。从连接器的观点看，直接寻址允许一条指令或一个数据地址被嵌入到程序中任何地址边界的任何部位。
条件跳转和无条件跳转以及子程序调用都使用相对地址。任何跳转指令都可以具有一个1、2或4字节的偏移量，将它们加到当前指令的地址上就可以获得目标地址。调用指令既可以包含一个4字节的绝对地址，也可以使用任何寻址模式来引用一个包含有目标地址的位置。这允许跳转和调用能够访问到当前32位地址空间中的任何位置。无条件跳转和调用还可以通过使用上面描述过的完整数据地址的计算方法来计算目标地址，最常用的是跳转或调用一个存放在寄存器中的地址。调用指令将依照ESP指向的位置将返回地址压入堆栈。
无条件跳转和调用指令还可以在指令中包含一个完整的六字节段/偏移量（segment/offset）地址，或计算存放地址值的地址的段/偏移量。这样的调用指令将返回地址和调用者的段号一起压入堆栈，以允许跨段的调用和返回。
在现代计算机上，每个程序都可以潜在地寻址一块巨大的内存，在典型的32位机器上可达4G。很少的机器实际能有这么大的内存，甚至在有的机器上需要多个程序共享内存。硬件分页将一个程序的地址空间划分为固定大小的页（page），典型的尺寸为2K到4K，而整个机器的物理内存
被划分为具有相同大小的页帧（page
frame）。硬件中，在每个页的入口处的地址空间中都包含有页表（page table），如图7所示。
图2-7：页面映射
从一个大的页表到实际的页帧的映射图示
一个页表入口点可以包含一个页的实际页帧，或者可以包含一个标记位表示该页“不存在”。当一个应用程序试图使用一个不存在的页时，硬件将产生一个可以由操作系统处理的“页面错误（page
fault）”。操作系统可以将页中内容的一个副本从磁盘装入一个空闲的页帧，然后让程序继续运行。通过在必要的时候将页放回磁盘或从磁盘加载到主存，操作系统可以为应用程序提供一个看起来比实际用到的内存大很多的虚拟内存（virtual
memory）。
然而，虚拟存储会带来开销。一条单独指令的执行只需要一微秒的一小部分，但一个页面错误和接踵而来的换页（page
in和page out，从磁盘向主存传送数据或反之）将由于磁盘的数据传递花去数个微秒。一个程序所产生的页面错误越多，它运行得越慢，最坏的情况将是崩溃（thrashing），在所有有用的工作还没做完时所有的页都发生了错误。一个程序需要的页越少，产生的页面错误就越少。如果连接器能够将相关的例程打包到一个单独的页或很少几个页中，分页的效率就会改善。
如果页面可以被标记为只读，性能也会改善。只读页可以重新加载到相对于其原始位置之外的任何地方而无需换出（page
out）。当同时运行一个程序的多个副本时，经常会出现一个完全相同的页逻辑地出现在多个地址空间的情况，对于这些地址空间，一个单独的物理页就足够了。
一个具有32位地址和4K分页的x86架构将需要一个具有220个入口的页表来将入口映射到地址空间。
由于每个页表入口通常都是4字节，这将导致页表达到4M字节这样一个不切实际的长度。结果，分页架构需要对页表进行分页，顶层页表指向底层页表，底层页表再指向对应于虚拟内存的实际页帧。在370中，顶层页表（称为段表，segment
table）映射1MB的地址空间，因此一个31位地址模式下的段表可能包含2048个入口。段表中的每一个入口都可以为空，这种情况称该段不存在；或者也可以指向一个底层页表，该底层页表映射了段中的页。每个底层页表都可以包含256个入口，每个入口（指向）段中的一个4K的内存块。x86以类似的方式划分页表，只不过边界不同。每个顶层页表（称作页目录，page
directory）映射4K的地址空间，因此顶层页表包含1024个入口。每个底层页表也包含1024个入口，可以映射到与页表对应的4MB地址空间中的1024个4K的页。SPARC架构定义页面大小为4K，而且具有三级页表而不是两级。
两级或三级的页表对于应用程序都是透明的，但除了一个例外：操作系统可以通过改变高一层页表中的一个单独的入口来改变对一大块地址空间的分页（在370上是1MB，在x86上是4MB，而在SPARC上是256K或16MB），其效果是可以通过替换单独的几个高层页表入口来大块大块地管理地址空间，而不必
在进程转换的过程中重新加载整个页面。
每个应用程序都运行在一个由硬件和操作系统共同定义的一个地址空间中。连接器或加载器需要建立一个匹配这种地址空间的可运行程序。
最简单的地址空间由Unix的PDP-11版提供。其地址空间为从0开始的64K字节。程序中的只读代码放到位置0，可读写数据紧跟着代码。PDP-11拥有8K页面，因此数据开始于代码之后的8K边界。堆栈向下增长，开始于64K-1，随着堆栈和数据的增长，它们各自的区域都在膨胀，当它们相遇的时候，程序就耗尽了地址空间。VAX上的Unix——PDP-11的延续——使用了一种类似的方案。每个VAX
Unix程序的前两个字节都是0（一个寄存器保护标记要求它们不能存放任何东西）。结果，一个无效的全为0的指针总是允许的，而且如果一个C程序使用了一个null值作为字符串指针，这个0地址处的0字节将被视为一个空字符串。结果，这一代的Unix程序总是包含由于空指针所引起的难以查找的BUG，而且很多年以后，移植到其他架构上的Unix都在位置0处提供一个0字节，因为这样可以很容易找到并修复所有由于空指针所引发的BUG。（译注：这是一个笑话哦~~就是说以前因为这个0字节总是出现BUG，后来大家习惯了，反而要加上这个0字节用来查找BUG，呵呵~~）
Unix将每个应用程序都放到分离的地址空间中，而且操作系统也放在一个和其他应用程序逻辑上分离的地址空间中。其他操作系统把多个程序放到相同的地址空间，导致了连接器和特定的加载器
的工作更加复杂，因为程序的实际加载地址直到程序即将被运行时还不知道。
x86架构上的MS-DOS不使用硬件保护，因此系统和正在运行的应用程序共享相同的地址空间。当操作系统运行一个程序的时候，它会寻找最大块的空闲内存，这可能是地址空间中的任何部分，将程序加载到那里，并开始运行它。IBM主机操作系统粗鲁地做着同样的事情，将程序加载到一大块可用的地址空间中。在这两种情况下，程序加载器甚至有的时候是程序本身都需要调整程序加载的位置。
MS
Windows拥有不同寻常的加载机制。每个被连接的程序都加载到一个标准的启动地址，但可执行程序文件包含重定位信息。当Windows加载程序的时候，如果可能的话它将程序放到启动地址，但如果这个首选地址不可用，它会将程序放到别的地方。
当数据分页无法放入实际内存中时，虚拟存储系统会将数据在实际存储器和磁盘之间来回移动。最初，分页都放到“匿名”的磁盘空间中，这独立于文件系统中的有名文件。然而，分页机制发明后不久，设计者注意到应该统一分页系统，并且分页系统应该通过使用文件系统来读写有名磁盘文件。
当一个程序将一个文件映射到该程序的一部分地址空间中时，操作系统会将该部分地址空间中的所有页标记为不存在，并使用磁盘文件作为这部分地址空间的分页，如图8所示。程序只能通过引用这部分地址空间来读取这个文件，这时分页系统会将必要的页从磁盘加载进来。
图2-8：映射文件
引用一组映射到磁盘文件或本地内存的页帧的程序
有三种不同的途径可以管理对映射文件的写入。最简单的方法是将文件映射为只读（RO，Read
Only）的，因此所有向映射区域的存储都会失败，通常会导致程序终止。第二种方法是将文件映射为可读写（RW，Read-Write）的，这样对于文件在内存中的副本的修改在文件不再被映射时回写到磁盘中。第三种方法是将文件映射为可写副本（COW，Copy-On-Write，这并不是一个恰当的缩写[译注：Copy-On-Write的意思我并不知道，根据下面的描述我将它翻译为“可写副本”]）。这将页映射为只读的，直到程序试图向该页中存储时。这时[译注：指“程序试图向该页中存储时”]，操作系统将该页视为一个并不是从文件映射而成的私有页，为该页制作一份副本。从程序的角度来看，将一个文件映射为COW就好像分配了一块干净的匿名内存区域，并将文件的内容读入了这块区域，因为该程序对于这块区域的修改对该程序是可见的，但对于任何其它映射自同一个文件的程序都是不可见的。
[译注：上面这一段理解起来可能很困难，我也是思考了很久才翻译出来的。我认为，可以这样理解：首先，我们可以把映射文件看作一个非缓冲文件，这样，所有对该文件的读取和写入都直接发生在该文件上。那么，当一个（页面）文件被映射为只读的的时候，自然就不能向其中写入，因此“所有向映射区域的存储都会失败”。而当一个页面文件被映射为可读写的的时候，自然可以随意地向该文件写入数据，而由于映射文件相当于非缓冲的，所以所有的修改都会立刻反映在页面文件上，因此其它映射了该文件的程序都将看到这种改变。最后，当一个文件被映射为COW时，好像建立了一个缓冲文件，缓冲区的大小等于文件大小，所有的修改都发生在缓冲区中，因此，其它程序尽管映射了同样的文件，也看不到当前程序所作的修改；当页面需要换出的时候，可以决定是放弃所有修改还是将修改保存到磁盘。这种理解不一定正确，还望高手们指教。]
几乎所有的系统都能并发地处理多个程序，每个程序都有一个独立的页表、一块逻辑上独立的地址空间。这使得一个系统需要考虑很多的事情，因为要保证发生故障的或怀有恶意的程序不能破坏或侦查其它程序，但这又可能潜在地导致性能问题。如果在不止一个地址空间中用到了一个单独的程序或单独的程序库，如果所有的地址空间可以共享该程序或库的一份单独的副本，则系统就能省下很多内存。相当明显，这需要操作系统来实现——向地址空间映射（译注：区别于创建一个副本）可执行文件即可。非重定位代码和只读数据映射为RO，可写数据映射为COW。操作系统还可以为所有映射了该文件的进程的RO和非写入的COW数据使用相同的物理页帧。（如果在加载时必须重定位代码，则这些代码要被视为COW而不是RO。）
要让这种共享能够工作起来，需要连接器提供很多支持。在可执行程序中，连接器需要将所有的可执行代码集中到一个可以映射为RO的部分中，而将数据集中到另一个可以映射为COW的部分中。每一节（Section）都必须开始于一个页边界，这既包括逻辑地址空间中的位置也包括在文件中的物理位置。当多个不同的程序使用了一个共享库时，连接器需要标记每一个程序，使得它们开始运行的时候该库能够被映射到该程序的地址空间。
当多个不同的地址空间使用了同一个程序时，操作系统通常可以将这段程序加载到它们所出现的地址空间中的相同位置上。这使得连接器的工作变得更加简单，因为它可以将程序中的所有地址绑定到固定的位置，而且当程序加载的时候无需进行重定位。
共享库将这一情况变得相当复杂。在一些简单的共享库设计中，当系统引导的时候或库被创建的时候，每个库都被赋予一个全局唯一的内存地址。这将每个库都放到了一个固定的地址，但这是以增加了一系列共享库管理瓶颈为代价的，因为系统管理器要维护存放了库的内存地址的全局列表。此外，如果一个库出现了一个新版本，它比原来版本的要大，以至于无法放入已经分配的地址空间，则整个一组库和可能所有引用了它们的程序都必须要重新连接。
另一种可选的方法是允许不同的程序将一个库映射到地址空间中的不同位置。这简化了库管理，但这需要编译器、连接器和程序加载器的共同合作来保证库能够工作，而不管它在地址空间中出现的位置。
一种简单的方法是在库中包含标准重定位信息，而当库被映射到每个地址空间中时，加载器可以修正程序中的每一个可重定位地址来反映加载地址。不幸的是，修正的过程引起了对库代码和数据的写入动作，这意味着这些页不再是共享的，它们将被映射为COW，或者当这些页被映射到RO时程序会崩溃。
为了避免这一问题，共享库使用了位置无关代码（Position
Independent Code，PIC），这些代码不管被加载到内存中的什么位置都可以工作。共享库中的所有代码通常都是PIC，因此这些代码可以被映射为只读的。数据页通常包含需要重定位的指针，但数据页总是被映射到COW，它们不用共享。
很大程度上，PIC是很容易创建的。这一章中所讨论的所有三种架构都使用相对跳转，因此例程内跳转无需重定位。对堆栈上的局部数据的引用使用基于基址寄存器的相对地址，这也不需要任何重定位。唯一的挑战是调用不在共享库之中的例程和引用全局数据。直接数据寻址和SPARC的高/低寄存器加载技巧将不会工作，因为它们都需要运行时重定位。幸运的是，有多种技巧可以用于让PIC代码处理库间调用和全局数据。我们将在第9章和第10章详细讨论了共享库的细节后再来讨论这些问题。
这一章中的最后一个主题就是声名狼藉的Intel架构的分段系统。x86系列是至今仍在广泛使用的唯一一种分段的架构——除了祖传的ex-Burroughts
Unisys主机——但这已经不再流行了，因此我们不得不涉及到它。不过，我们只是简短地讨论一下，32位操作系统已经不再对分段作任何重要的应用了，只有老式的系统尤其是流行的x86系列16位嵌入式版本还在广泛地使用它。
原始的8086打算作为Intel非常流行的8位8080和8085位处理的的一个延续。8080具有一个16位的地址空间，而且8086的设计者们在保留16位地址空间——这可以使得
移植8085（的程序）变得容易并且允许更加精简的代码，和提供一个更大的地址空间以给以后更大的应用程序以“自由空间（headroom）”之间争论着。他们互相妥协了，决定提供多个16位地址空间。每个16位地址空间就是著名的段（Segment）。
一个运行着的x86程序有四个活动的段，由四个段寄存器定义。CS寄存器定义了代码段（Code
Segment），在这里可以提取指令。DS寄存器定义了数据段（Data Segment），在这里可以加载和存储数据。SS寄存器定义了堆栈段（Stack
Segment），用于push和pop指令、调用和返回指令压入和弹出程序地址值、以及任何使用EBP或ESP作为基址寄存器的数据引用。ES寄存器定义了扩展段（Extra
Segment），由一些字符串操作指令使用。386和以后的芯片还定义了另外两个段寄存器FS和GS。通过使用段覆盖可以将任何数据引用指向一个特定的段。例如，指令MOV
EAX, CS:TEMP可以从代码段而不是数据段的TEMP位置处提取一个数据。FS和GS段只能通过段覆盖来使用。
段的值不一定不同。很多程序将DS和SS设置为相同的值，因此指向堆栈变量的指针和全局变量和以互换使用。一些小程序将所有四个段寄存器设置为相同的值，提供一个单独的地址空间，这就是所谓的微型模式（Tiny
Mode）。
在8086和186上，架构为段号到内存地址定义了一个固定的映射：将段号向左移4位。如段号为0x123的段开始于内存地址0x1230。这种简单的寻址址方式就是所谓的实模式（Real
Mode）。程序员通常非正式地称之为“段儿（paragraphs）”[译注：我也不知道是不是这么称呼]，一个段号可以寻址16字节的内存单元。
286新添了一种保护模式（Protected
Mode），在这种模式下，操作系统可以将段映射到实际内存中的任何位置并且可以将段标记为不存在、提供基于段的虚拟存储。每个段都可以标记为可执行（Executable）、可读（Readable）或读/写，
以提供段级（segment-level）保护。386将保护模式扩展到32位地址，因此每一段可以长达4GB而不是区区64K。
在16位寻址中，除了最小的程序外，所有的程序都不得不处理分段地址。改变一个段寄存器中的内容非常之慢，打个比方，如果在486上需要1个时钟周期来改变通用寄存器的内容，就要花9个时钟周期来改变段寄存器。结果，程序和程序员要绞尽脑汁将代码和数据放在尽可能少的段中。连接器通过提供“分组（Group）”来协助完成这一过程，它可以将相关的代码和数据放到一个单独的段中。代码和数据指针既可以非常接近——相差一个没有段号的偏移量，也可以非常远——既需要段号也需要偏移量。
编译器可以通过检测代码和数据地址是近还是远来默认产生多种存储模式的代码。小模式（Small
Model）代码使所有指针都很接近，且拥有一个代码段和一个数据段。中模式（Medium Model）具有多个代码段（每个程序源文件一个），使用远端调用（far
call），但只有一个默认的数据段。大模式（Large
Model）代码具有多个代码和数据段，而且所有的指针默认都是远端的。编写高效的分段代码是非常要技巧的，而且要在其他地方有良好的文档。
分段地址给连接器提出了重要的需求。程序中的每个地址都具有一个段和一个偏移量。由多块代码构成的目标文件需要连接器来将这些代码包装到段中。在实模式下运行的可执行程序必须标记程序中出现的所有段号，以使得它们可以被重定位到程序加载位置的实际段。在保护模式下运行的可执行程序还必须标记什么数据将要被加载到什么段中以及对每个段的保护（代码、只读数据还是可读写数据）。
尽管386支持286中所有的16位段特性，以及所有段特性的32位版本，很多32位程序是根本不使用任何段的。386还引入了分页，既提供了分段的很多实用的优点，又避免了性能损失和书写段管理代码时过多的复杂性。很多386操作系统在微模式下运行程序，
由于386上的一个段不再“微”了，因此这种模式更多地被称做平面模式（Flat
Model）。它们创建一个单独的代码段和一个单独的数据段，每个都是4GB长，而且都映射到完整的32位分页的地址空间中。甚至如果程序只使用一个单独的段，这个段可以具有整个地址空间的大小。
386使得在同一个程序中可以同时使用16位和32位段，而一些操作系统，尤其是Windows
95和98，充分利用了这一特性。Windows 95和98在共享的地址空间中的16位段上运行了很多古老的Windows
3.1代码，而每个新的32位程序则运行在它们自己的微模式地址空间中，
而16位程序的地址空间被映射为可以向后和向前调用。[译注：这句话不知到什么意思，还望高手指教。]
嵌入式系统中的连接引发了大量在其他环境中罕有的问题。嵌入式芯片具有有限数量的存储器和有限的性能，尽管在很多设备上一个嵌入式程序可能被内建到芯片中，但我们仍然希望它能在尽可能少的存储器中尽可能快地运行。一些嵌入式系统使用通用芯片的低功耗（low-cost）版本，如80186；而其他一些则使用特制的处理器，如Motorola
56000系列数字信号处理器（DSPs，Digital Signal Processors）。
嵌入式系统具有很小的地址空间，它们带有槽布局（quirky
layout）。一个64K的地址空间可以包含快速片上（on-chip）ROM和RAM、慢速片外（off-chip）ROM和RAM、片上周边和片外周边的组合。其中还可能包含很多ROM或RAM的非连续区域。56000有三个64K、24位字的地址空间，每个都由RAM、ROM和周边联合构成。
嵌入式芯片的开发使用包含了处理器芯片和支持它的逻辑电路和芯片的系统板。通常，相同处理器的不同开发板具有不同的存储器布局。不同模式的芯片具有不同数量的RAM和ROM，因此程序员不得不不惜一切代价地将一个程序塞进更少的存储器，否则就要付出额外的开销来使用一款更加昂贵的、具有更多存储器的芯片。
用于嵌入式系统的连接器需要一种途径来非常详细地指定被连接程序的布局、特殊种类的代码或数据的分配布局，甚至是每个单独的例程和变量的布局——以指定地址。
引用片上存储器比引用片外存储器要快（得多），因此在一个同时拥有这两种存储器的系统中，对时间很苛求的例程应该放到快速存储器中。有的时候，可以在连接时将程序中所有苛求时间的代码塞进快速存储器中。而有的时候，需要在必要时将代码或数据从慢速存储器中复制到快速存储器中，因此多个例程可以在不同时间共享相同的快速存储器。对于这一技巧，能够告诉连接器“将这段代码放到XXXX位置但将它连接到YYYY位置”是非常有必要的，这样在运行时这段代码就能被正确地从慢速存储器中的XXXX位置复制到快速存储器的YYYY位置。
DSPs通常对于某种数据指令有着苛刻的存储对齐要求。例如56000系列具有一种寻址模式用于有效地处理环状缓冲器（circular
buffer），该缓冲器的基址必须要对齐到一个至少和缓冲器大小相等的2的幂边界上（例如，一个50个字的缓冲器要对齐到64字边界）。快速傅里叶变换（FFT，Fast
Fourier Transform）——信号处理过程中的一种极其重要的计算——依赖地址位操作（address bit
manipulation）——也要求执行一个FFT运算的数据对齐到2的幂边界。和通常的架构不同，这种对齐需求依赖于数据数组的大小，因此将它们有效地放入可用的存储器是一项既要求技巧又乏味的工作。
1. 一个SPARC程序包含了这些指令。（这并不是一个有用的程序，只是作为一些指令格式的示例。）
Loc Hex Symbolic
1000 40 00 03 00 CALL X
1004 01 00 00 00 NOP
; no operation, for delay
1008 7F FF FE ED CALL Y
100C 01 00 00 00 NOP
1010 40 00 00 02 CALL Z
1014 01 00 00 00 NOP
1018 03 37 AB 6F SETHI r1, 3648367 ; set high 22 bits of r1
101C 82 10 62 EF ORI r1, r1, 751 ; OR in low 10 bits of r1
1a.
在一个CALL指令中，最高两位是指令代码，而低30位是一个带符号字（不是字节）偏移量。X、Y和Z的十六进士地址是多少？
1b. 位置1010处对Z的调用如何完成？
1c.
1018和101C处的两条指令向寄存器1加载了一个32位地址。SETHI将指令中的低22位加载到该寄存器的高22位，而ORI将指令中的低13位逻辑地或到寄存器中。寄存器1种将包含的地址是什么？
1d.
如果连接器将X移动到位置2504（十六进制）处，而没有改变例子中代码的位置，那么它将如何修改位置1000处的指令以使它仍然可以引用X？
2. 一个Pentium上的程序包含了这些指令。不要忘了x86是小尾数的。
Loc Hex Symbolic
1000 E8 12 34 00 00 CALL A
1005 E8 ?? ?? ?? ?? CALL B
100A A1 12 34 00 00 MOV %EAX, P
100F 03 05 ?? ?? ?? ??ADD %EAX, Q
2a. 例程A和数据字P被定位到什么地方？（提示：在x86上，相对地址的计算是相对于当前指令后面的一个位置。）
2b. 如果例程B定位在地址0F00而数据字Q定位在地址3456，例子中??处的字节应该是什么？
3.
一个连接器或加载器需要“理解”目标架构的指令集中的每一条指令么？如果目标架构的一个新的模式添加了新的指令，需要修改连接器以支持它们么？如果它为一个现存的指令增加了新的寻址模式呢，如386相对于286？
4.
回到计算的的黄金时代，当时的程序员要在深夜工作，因为这是他们唯一能够使用计算机的时间，而不是因为他们那时才醒来，很多的计算机还在使用字寻址而不是字节寻址。如PDP-6和10，具有36位字和18位寻址（能力），每条指令都是一个字长，其中低半字中是操作数的地址。（程序也可以在高半字中存放地址，不过没有能够直接支持这样做的指令集。）如何比较字寻址架构和字节寻址架构？
5.
建立一个可重定目标（retargetable）的连接器有多难？——也就是说，通过改变连接器源代码中很少的特殊部分就能够处理不同的目标架构。建立一个可以处理大量不同架构的代码的多目标连接器呢？（不一定要在同一个连接器任务中完成）。
[回顶端]
