异常

从处理器加电一直到断电，程序计数器始终执行着一个序列的指令。每次从一个指令到下一条指令的过渡被称为控制转移。而这个控制转移序列则被称为处理器的控制流。最简单的控制流是一个平滑的序列，由诸如跳转，调用，返回一类的指令造成的。这些指令都是必要的，使程序能根据程序内部状态做出反映。

但是系统也应该能对系统状态的变化做出反应，这些系统状态不会被内部程序变量捕获，也不一定和程序的执行相关。可能是某个硬件向系统发出的信号或是请求。这个时候原本的控制流是难以处理这些情况的，所以现代的系统通过使控制流发生突变，从而对这些情况做出反应。一般而言，我们将这些突变称作异常控制流(ECF)

异常则是异常控制流的一种形式，指的是控制流中的突变，用来响应处理器的某些变化，下图就反映了这个过程：

当处理器状态发生一个重要的变化时，这个状态的变化我们称之为事件。事件和当前执行的指令相关，比如以0作为除数，算数溢出……

当处理器检测到事件发生时，它就会通过一张叫异常表的跳转表，进行一个间接过程的调用（异常），到一个专门设计用来处理这些事件的操作系统子程序（异常处理程序）。事件经过处理后，根据事件类型，程序会进入其中一种状态：

• 控制返回给当前指令I_curr，即事件发生时的指令
• 控制返回给I_next，如果没有发生异常将会执行的下一条指令
• 终止该程序

异常处理

我们进一步的了解一下，异常处理的过程中都发生了什么。

系统为每种类型的异常都分配了一个唯一的非负整数的异常号。号码的分配也有所区别，处理器设计者分配的异常号码通常是零除，内存访问违例，算数溢出一类的。另一部分是，操作系统的内核的设计者分配的，如系统调用和来自外部I/O设备的信号.

在系统启动时，操作系统会分配和初始化一张称为异常表的跳转表，使得表目k包含异常k的处理程序的地址：

当运行时，处理器检测到发生了一个事件，且确定了其异常号k时。处理器会触发异常，执行间接过程调用，通过异常表的表目k，跳转到相应的处理程序，其过程如下 ：

异常表基址寄存器是用来存放异常表地址的特殊寄存器，在异常表中，异常号是到异常表的索引。

异常类似于过程调用，但是有些区别：

• 过程调用时，会把返回地址压入栈中（确定的）。但是，根据异常类型，返回的地址会有所不同，返回地址要么是当前指令（事件发生时的执行的指令），要么是下一条指令
• 由于要切换到异常处理程序，所以我们需要保存额外的处理器状态（通用寄存器，PC，条件寄存器…）以保存上下文。
• 如果控制从用户程序转移到内核，所有这些项目都被压到内核栈中，而不是用户栈。
• 异常处理程序运行在内核模式下，它们对所有系统资源都有访问权

当硬件触发了异常，剩下的工作就是由异常处理程序在软件中完成。在处理程序处理完毕之后，通过“从终端返回”指令，可选的返回到被中断的程序，该指令将保存的状态弹回寄存器中。并恢复用户模式，将控制返回给呗中断的程序。

异常的类别

异常可以分为四类：中断(interrupt)、陷阱(trap)、故障(fault)、终止(abort)

中断

中断时异步发生的，时来自处理器外部的I/O设备的信号的结果。硬件中断不是由指令造成的，且不可预测，所以我们说它是异步的。硬件中断的异常处理程序称之为中断处理程序

设备会将异常号放到系统总线上，并且向处理器的中断引脚发送信号。当处理器发现中断引脚电压升高，就会读取异常号，调用中断处理程序。当处理程序返回时，就将控制返回给下一条指令。这样从外界看，就好像没有发生过中断一样。

剩下的异常类型都是同步发生的，他们是执行当前指令的结果。我们把这类指令叫做故障指令。

陷阱和系统调用

陷阱是有意的异常，是一条指令执行的结果。它可以在用户程序和内核之间提供一个像过程一样的接口，即系统调用。

用户程序经常需要像内核请求服务。如读取文件(read)、创建一个新的进程(fork)、加载一个新的程序(exec)、终止当前进程(exit)。为了支持对这些内核服务的访问，处理器支持syscall n指令，当用户想要请求服务n时，可以执行这个指令。执行syscall会导致一个到异常处理程序的陷阱，这个处理程序会解析参数，调用合适的内核程序。

看起来系统调用和函数调用是一样的，但是实际上函数调用是在用户模式下进行，用户模式限制了函数可执行的指令的类型，而且他们只能访问于调用函数相同的栈。系统调用则是运行在内核模式中，内核模式允许指令调用特权指令，并访问内核中的栈。

故障

故障是由错误情况导致的，它可能会被故障处理程序修正。当故障发生，处理器会将控制传递给故障处理程序。如果故障被修读，就将控制传递会引起故障的程序，重新执行。否则，船里程序会返回abort历程例程，从而终止引起故障的应用程序。

终止

终止是不可恢复的错误造成的结果 。终止处理程序不会将控制返回给应用程序，而是但会给一个abort例程，从而终止这个应用。

Linux/x86-64系统中的异常

为了认识的更加具体，我们可以看看x86_64系统定义的一些异常。其中0~31的号码对应Intel架构定义的异常。32~255的号码对应的是操作系统定义的中断和陷阱。

这是一些比较常见的：

故障和终止

• 除法错误：当试图除0时，或者一个除法指令的结果对于目标操作数而言太大的时候，就会导致除法错误。在LinuxShell里面，执行一个有除法错误的程序会报告Floating point exception
• 一般保护故障：这个故障比较容易触发，通常是因为程序引用了一个未定义的虚拟内存区域，或者是尝试写一个只读文本段。Linux不会恢复这类故障，会报告为段故障Segmentation fault
• 缺页：这是一个会重新执行产生故障的指令的一个异常示例。处理程序会将适当的磁盘上的虚拟内存的一个页面映射到物理内存的一个页面，然后重新执行这个产生故障的指令。
• 机器检查：机器检查是在导致故障的指令执行中检测到致命的硬件错误时发生的。

系统调用

下面展示一些常用的系统调用

C语言中可以用syscall来进行系统调用。不过没必要，因为在<unistd.h>头文件中，封装了许多对操作系统底层服务的访问接口。我们将这些系统调用和包装函数称为系统级函数。

在Linux系统中，我们使用syscall陷阱指令来实现系统调用。它的调用过程如下：

使用寄存器%rax包含系统调用号，使用寄存器%rdi %rsi %rdx %r10 %r8 %r9来依次传递参数。从系统调用返回时，%r11 %rcx会被破坏（因为rcx用来存放返回地址，r11存放标志寄存器），%rax存放返回值。如果返回值是负数则说明发生错误。

可以通过查看系统级函数的编译来看到这个参数传递的过程:

进程

在系统上运行一个程序时，我们会得到一个假象，我们的程序似乎是系统中的唯一一个程序，独占着内存和处理器的使用。但事实并非如此。

系统中的每个程序都运行在某个进程的上下文中。上下文由程序正确运行所需的状态组成。这个状态包括许多，如存放在内存中的数据和代码，它的栈、通用寄存器的内容、程序计数器、环境变量、和打开文件描述符的集合。

每次运行一个新的程序时，shell就会创建一个新的进程，然后再这个新进程的上下文中运行这个程序。应用程序也是如此，创建新进程，并且再新进程的上下文中运行自己的代码和其他应用程序。不过我们只需要关注进程提供给应用程序的关键抽象：

• 一个独立的逻辑控制流：提供一个假象，让我们认为程序独占处理器
• 一个私有的地址空间：提供一个假象，让我们以为程序独占内存系统

逻辑控制流

通常系统中同时有很多程序在进行，进程可以向程序提供一个假象，自以为独占处理器与内存。但实际上并非如此。

我们将一个程序的顺序执行的PC值的序列称为逻辑控制流。将处理器执行的PC值的序列称为物理控制流。那么，在处理器的视角中控制流的转移实际上是这样的：

进程实际上是轮流使用处理器的。每个进程执行它的流的一部分，然后被抢占（暂时挂起），然后轮到其他进程。再次运行这个进程时，由于进程的上下文信息不变，所以运行在这些进程之一的上下文中的程序，它自认为是始终独占处理器的。

并发流

如果一个逻辑流得执行在时间上和另一个流重叠，称为并发流，这两个流称为并发的运行。多个流并发的执行的一般现象称为并发。一个进程和其他进程轮流运行的概念称为多任务。一个进程执行它的控制流的一部分的每一时间段就叫做时间片。因此多任务也叫时间分片。例如上图的进程A就是由两个时间片组成的。

这里我们还要提到一下并行和并发的区别。并行是并发的一个真子集，只不过并行是并发的运行在不同的处理器核或计算机上的。现代计算机的并行能力，是基于计算机数或处理器核数上的，单一的处理器核无法实现并行。这一点要加以区分。

私有地址空间

进程也为每个程序提供一个假象，好像它独占了系统地址空间。这是因为进程为每个程序提供了自己的私有地址空间（进程地址空间）。一般而言，和这个空间中某个地址相关联的内存字节，是不能被其他进程读或写的。这个意义上来说，这个地址空间是私有的。

尽管和每个私有地址空间相关联的内存的内容一般是不同的，但是每个这样的空间都有相同的通用结构：

地址空间的底部是留给用户程序的，地址空间的顶部总是留给内核。这里需要注意，代码段总是从地址0x0040000开始的。这个进程的地址空间是进程上下文的一部分。

用户模式和内核模式

为了进一步提供进程的抽象能力，操作系统需要一种机制，限制一个应用可以执行的指令以及它可以访问的地址空间范围。

处理器通过控制某个控制寄存器中的一个模式位来提供这种功能，这个寄存器会描述当前的进程所享有的特权。当设置了模式位时，进程就运行在内核模式下。在内核模式下的进程可以执行指令集中的所有指令，访问系统中的任何内存地址。

没有设置模式位时，在用户模式下的进程，不允许执行特权指令，比如停止处理器，改变模式位，发起IO操作…….。也不允许进程直接引用地址空间中内核区的代码和数据。否则会引起故障保护，用户程序只能通过系统调用接口间接的访问内核的代码和数据。

初始时，应用程序代码的进程是在用户模式中的，当发生异常时。控制传递到异常处理程序，处理器从用户模式切换到内核模式。处理程序在内核模式中运行，当它返回到应用程序时，处理器将内核模式切换回用户模式

当然除此之外，Linux提供了一系列的机制可以让用户进程访问内核的数据结构的内容。在/proc下我们可以访问进程的属性还有一般的系统属性。/sys中则可以查看关于系统总线和设备的底层信息…….

上下文切换

操作系统内核通过上下文切换的机制来实现多任务。这个机制是基于底层的异常机制之上的。

内核为每个进程维护一个上下文。上下文就是内核重新启动一个进程所需要的状态。它由一系列的对象的值组成。这些对象有通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和一系列内核数据结构（例如描述地址空间的页表、包含有关当前进程信息的进程表，以及包含进程已打开文件的信息的文件表……）组成的。

在进程执行的某些时刻，内核可以挂起当前进程转而执行恢复执行其他被挂起的进程。这个决策被称为调度，由内核中的调度器处理。当内核选择一个新的进程时，我们就称内核调度了这个进程。内核调度了一个新的进程后，就抢占当前进程。使用上下文切换的机制来控制转移新的进程。

上下文切换主要分为三个过程：

• 保存当前进程的上下文
• 恢复某个先前被挂起的进程的上下文
• 将控制传递给新恢复的进程

了解了上下文切换，我们再来看看上下文切换的场景：

• 执行系统调用sleep
• 系统调用因为等待某个事件而阻塞时
• 中断发生（有的系统会有周期性的定时中断器，以免处理器在单个进程运行太长时间）
• ……..

总而言之就是尽可能安排任务，不要让处理器空转。下面这个图片就很好的体现了这个过程：

最近很流行这些，出于好奇，我也想知道这些技术背后的原理是什么。而且我感觉很多知识可能之后会用到，所以我打算浅浅的了解一下。最终的目标是实现一个手写数字识别的神经网络吧。试试看吧。

神经网络简介

基础构件：神经元

神经元是神经网络的基本单元。它接受输入，对数据进行计算从而产生一个输出。比如下面的一个二元输入神经元样例：

这个神经元进行了以下操作：

• 输入乘以权重w：

  x₁ –> x₁ * w₁ x₂ –> x₂ * w₂

• 加权输入与偏置b相加：

  ( x₁ * w₁) + (x₂ * w₂) + b

• 最后将总和传递给激活函数：(其中f是激活函数)

  y = f(x₁ * w₁ + x₂ * w₂ + b)

对于任意输入的神经元，我们的输出是：

$$ y = f\left(\sum_{i=1}^{n} w_i x_i + b\right) $$

对于激活函数f我们需要额外了解到，在不引入激活函数的情况下，我们的输出和下一个输入的结果之间总是线性的关系。我们使用激活函数则可以将无界的输入转换成良好的、可以预测形式的输出。这里我们使用的激活函数是sigmoid函数：

$$ \begin{aligned} f(x)=\frac{1}{1+e^{-x}} \end{aligned} $$

sigmoid函数只输出（0，1）范围内的数值，它将(−∞, +∞)的数值压缩到了（0，1）.

简单的举例

假设我们现在有一个使用sigmoid激活函数的二元输入神经元，其w=[0,1] b=4

若我们想神经元输入x = [2,3]，我们可以得到

1
2
3

(w * x) + b = 0*2 + 1*3 + 4
		   = 7
y = f(w*x+b) = f(7) = 0.999

我们向前传递输入以获取输出，这个过程我们称之为前馈(feedforward)

神经元的代码实现

我们使用Python中的numpy来实现这个功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import numpy as np

def sigmoid(x: float) -> float:
    return 1/(1+np.exp(-x))

class Neuron:
    def __init__(self, weights, bias):
        self.weights = weights
        self.bias = bias

    def feedforward(self, inputs):
        total = np.dot(self.weights, inputs) + self.bias
        return sigmoid(total)


weights = np.array([0,1])
bias = 4
n = Neuron(weights,bias)

x = np.array([2,3])
print(n.feedforward(x))
# 0.9990889488055994

可以看到我们的输出和我们的计算是吻合的

将神经元组合成神经网络

神经网络实际上是许多相互连接的神经元，一个简单的神经元长这样：

这个网络有两个输入组成的输入层，还有两个神经元(h₁，h₂)组成的隐藏层，以及一个神经元(o₁)组成的输出层。其中隐藏层指的是位于输入层和输出层之间的任何层，可以有多个隐藏层。

简单的举例：前馈计算

我们使用上述的网络，令每个神经元都是使用sigmoid激活函数且w=[0,1] b=0，用h1 h2 o1来表示神经元的输出，则有：

1
2
3
4
5
6
7

h1 = h2 = f(w*x+b)
		=f((0*2)+(1*3)+0)
		=f(3)
		=0.9526
o1 = f(w*x+b)
	= f(0.9526)
	= 0.7216

此时我们的神经网络的前馈就是0.7216，整个过程简而言之就是，将输入信息通过网络中的神经元向前传递，最终得到输出信息，作为整个神经网络的前馈

神经网络的代码实现

现在我们为这个简单的神经网络实现前向传播

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class NeuralNetwork:
    def __init__(self):
        weights = np.array([0,1])
        bias = 0
        self.h1 = Neuron(weights,bias)
        self.h2 = Neuron(weights,bias)
        self.o1 = Neuron(weights,bias)

    def feedforword(self,x):
        out_h1 = self.h1.feedforward(x)
        out_h2 = self.h2.feedforward(x)
        out_o1 = self.o1.feedforward(np.array([out_h1,out_h2]))
        return out_o1


network = NeuralNetwork()
x = np.array([2,3])
print(network.feedforword(x))
# 0.7216325609518421

和我预期的答案是吻合的

训练神经网络

损失

训练神经网络意味着，有预测的答案和实际的答案。训练的过程就是让网络预测的结果贴合真实的答案。那么首先我们就需要知道，预测的答案和真实的答案差距有多大，我们需要将它量化。

假设有以下测量值：

我们用0表示男性，用1表示女性。我们要训练我们的网络，根据体重和身高预测某人的性别。我们通过对数据设置偏移，让它更容易被处理：

现在我们需要找到一个方法量化它的”好坏”，以训练它做的更好。这里我们使用均方误差损失(MSE)来衡量它的好坏： $$ MSE = \frac{1}{n}\sum_{i=1}^{n}(y_{true} - y_{pred})^2 $$ 其中：

• n是样本数量，这里是4
• y代表被预测的变量，这里是性别
• y_true是变量的真实值（“正确答案”）
• y_pred是网络输出的结果，即预测值

我们可以用代码实现MSE的计算：

1
2

def mse_loss(y_true,y_pred):
    return ((y_true - y_pred)**2).mean()

反向传播

我们现在已经量化了我们的损失，我们现在需要通过调整网络的权重和偏差从而使得预测更加准确。我们该怎么做呢?

我们从下面这个最简单的情况开始，一点一点反推整个训练的过程

在这次训练中，正确答案为1，预测结果为y_pred。此时有： $$ \begin{align*} MSE = \frac{1}{1}\sum_{i=1}^{n}(1-y_{pread})^2 = (1-y_{pred})^2 \end{align*} $$ 有了量化的偏差，接下来我们给网络中的每个权重和偏差都标记出来，此时我们可以写出一个多变量函数： L(w₁, w₂, w₃, w₄, w₅, w₆, b₁, b₂, b₃)

假如我们调整w1，那么损失L会怎么变化呢？也就是说我们需要求出$\frac{\partial L}{\partial w_1}$，从而进一步调整w1以减少L

我们可以用下列过程来求出它： $$ \begin{align*} \frac{\partial L}{\partial w_1} &= \frac{\partial L}{\partial y_{pred}}*\frac{\partial y_{pred}}{\partial w_1} \\ \frac{\partial L}{\partial y_{pred}} &= \frac{\partial (1-y_{pred})^2}{\partial y_{pred}} = -2(1-y_{pred}) \end{align*} $$ 我们想处理$\frac{\partial y_{pred}}{\partial w_1}$，需要用h1 h2 o1 来代表神经元的输出，然后得到： $$ \begin{align*} \frac{\partial y_{pred}}{\partial w_1} &= \frac{\partial y_{pred}}{\partial h_1}*\frac{\partial h_1}{\partial w_1} \\ \\ y_{pred} &= o_1 = f(w_5h_1 + w_6h_2 + b_3) \\ \frac{\partial y_{pred}}{\partial h_1} &= w_5*f'(w_5h_1 + w_6h_2 + b_3) \\ \\ h_1 &= f(w_1x_1+w_2x_2+b_1) \\ \frac{\partial h_1}{\partial w_1} &= x_1*f'(w_1x_1+w_2x_2+b_1) \end{align*} $$ 这里我们要用到激活函数的导数，所以对其进行求导： $$ \begin{align*} f(x)&=\frac{1}{1+e^{-x}} \\ f'(x)&=\frac{e^{-x}}{(1+e^{-x})^2}=f(x)*(1-f(x)) \end{align*} $$ 现在我们可以合并计算出 $$ \frac{\partial L}{\partial w_1} = \frac{\partial L}{\partial y_{pred}}*\frac{\partial y_{pred}}{\partial h_1}*\frac{\partial h_1}{\partial w_1} $$ 这个反向计算偏导数的系统被称之为反向传播。现在我们可以带入数值计算出$\frac{\partial L}{\partial w_1}=0.0214$，我们可以根据这个值来训练我们的权重。

训练

于是我们可以制定我们的训练过程了。在这里我们使用一种名为随机梯度下降的算法，它将告诉我们如何调整权重和偏差以最小化损失。它实际上就是这么个更新公式： $$ w_1 \gets w_1 - \eta*\frac{\partial L}{\partial w_1} $$ 这里的η指的是学习率，用来控制我们训练的速度和精度。我们对网络中的每个权重和偏差都这么做，我们的损失将慢慢减少，我们的网络将越来越准确。

我们的徐连过程将如下：

• 从数据集中选择一个样本（随机梯度下降的原理就是一次只操作一个样本）
• 计算损失相对于权重或偏差的所有偏导数
• 使用更新方程来更新每个权重和偏差
• 重复

实现一个完整的神经网络

现在我们可以实现一个完整的神经网络来实现这个训练过程了

这是我们的数据集和网络结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

import numpy as np

def sigmoid(x):
    return 1/(1+np.exp(-x))

def deriv_sigmoid(x):
    return sigmoid(x)*(1-sigmoid(x))

def mse_loss(y_true,y_pred):
    return ((y_true - y_pred)**2).mean()

class Neuron:
    def __init__(self, weights, bias):
        self.weights = weights
        self.bias = bias

    def feedforward(self, inputs):
        total = np.dot(self.weights, inputs) + self.bias
        return sigmoid(total)


class NeuralNetwork:
    def __init__(self):
        self.w1 = np.random.normal()
        self.w2 = np.random.normal()
        self.w3 = np.random.normal()
        self.w4 = np.random.normal()
        self.w5 = np.random.normal()
        self.w6 = np.random.normal()

        self.b1 = np.random.normal()
        self.b2 = np.random.normal()
        self.b3 = np.random.normal()

    def feedforward(self,x):
        h1 = sigmoid(self.w1 * x[0] + self.w2 * x[1] + self.b1)
        h2 = sigmoid(self.w3 * x[0] + self.w4 * x[1] + self.b2)
        o1 = sigmoid(self.w5 * h1 + self.w6 * h2 + self.b3)
        return o1

    def train(self,data,all_y_trues):
        learn_rate = 0.05
        epochs = 5000
        for epoch in range(epochs):
            for x,y_true in zip(data,all_y_trues):
                sum_h1 = self.w1 * x[0] + self.w2 * x[1] + self.b1
                h1 = sigmoid(sum_h1)
                sum_h2 = self.w3 * x[0] + self.w4 * x[1] + self.b2
                h2 = sigmoid(sum_h2)
                sum_o1 = self.w5 * h1 + self.w6 * h2 + self.b3
                o1 = sigmoid(sum_o1)
                y_pred = o1

                d_L_d_ypred = -2*(y_true-y_pred)

                # o1
                d_ypred_d_w5 = h1 * deriv_sigmoid(sum_o1)
                d_ypred_d_w6 = h2 * deriv_sigmoid(sum_o1)
                d_ypred_d_b3 = deriv_sigmoid(sum_o1)
                d_ypred_d_h1 = self.w5 * deriv_sigmoid(sum_o1)
                d_ypred_d_h2 = self.w6 * deriv_sigmoid(sum_o1)

                # h1
                d_h1_d_w1 = x[0] * deriv_sigmoid(sum_h1)
                d_h1_d_w2 = x[1] * deriv_sigmoid(sum_h1)
                d_h1_d_b1 = deriv_sigmoid(sum_h1)

                # h2
                d_h2_d_w3 = x[0] * deriv_sigmoid(sum_h2)
                d_h2_d_w4 = x[1] * deriv_sigmoid(sum_h2)
                d_h2_d_b2 = deriv_sigmoid(sum_h2)

                # h1 train
                self.w1 -= d_L_d_ypred * d_ypred_d_h1 * d_h1_d_w1 * learn_rate
                self.w2 -= d_L_d_ypred * d_ypred_d_h1 * d_h1_d_w2 * learn_rate
                self.b1 -= d_L_d_ypred * d_ypred_d_h1 * d_h1_d_b1 * learn_rate

                # h2 train
                self.w3 -= learn_rate * d_L_d_ypred * d_ypred_d_h2 * d_h2_d_w3
                self.w4 -= learn_rate * d_L_d_ypred * d_ypred_d_h2 * d_h2_d_w4
                self.b2 -= learn_rate * d_L_d_ypred * d_ypred_d_h2 * d_h2_d_b2

                # o1 train
                self.w5 -= learn_rate * d_L_d_ypred * d_ypred_d_w5
                self.w6 -= learn_rate * d_L_d_ypred * d_ypred_d_w6
                self.b3 -= learn_rate * d_L_d_ypred * d_ypred_d_b3

            if epoch % 10 == 0:
                y_preds =np.apply_along_axis(self.feedforward,1,data)
                loss = mse_loss(all_y_trues,y_preds)
                print("Epoch %d loss: %.3f" % (epoch,loss))


# 来源：国家体育总局《第五次国民体质监测公报》2022[^44^]
# cm-150 kg-50
data = np.array([
    [10.6, 5.7],   # 女 20-24 岁
    [9.8, 6.7],   # 女 25-29 岁
    [9.1, 8.0],   # 女 30-34 岁
    [8.6, 9.1],   # 女 35-39 岁
    [8.0, 9.7],   # 女 40-44 岁
    [7.5, 10.1],   # 女 45-49 岁
    [7.2, 10.8],   # 女 50-54 岁
    [7.0, 10.7],   # 女 55-59 岁
    [22.6, 20.4],   # 男 20-24 岁
    [22.1, 22.8],   # 男 25-29 岁
    [21.4, 24.3],   # 男 30-34 岁
    [20.4, 24.0],   # 男 35-39 岁
    [19.4, 23.2],   # 男 40-44 岁
    [18.7, 22.5],   # 男 45-49 岁
    [17.9, 21.6],   # 男 50-54 岁
    [17.5, 21.0]    # 男 55-59 岁
])

all_y_trues = np.array([
    1,1,1,1,1,1,1,1,   # 8 位女性
    0,0,0,0,0,0,0,0    # 8 位男性
])
network = NeuralNetwork()
network.train(data,all_y_trues)

print(network.feedforward([161-150,65-50]))

找了下几个热心嘉宾试了一下还是很准确滴

和好兄弟出去玩，谈到上大学。我觉得很遗憾，遗憾自己没能去想去的学校。他说，感觉人生就是因为有遗憾的事情所以才值得去回忆。我想想也是，我看历史书也是这样的，就是因为有遗憾的部分我才总是记得很清楚。就像是三国演义的诸葛之死，我每次想到都很难过，王者荣耀这个赛季也是三国主题。我看别人都是选的魏国吴国的阵营，我就选蜀国，我就是单纯的比较喜欢。

感觉人生也是小小的历史，从小到大也有很多遗憾的瞬间。某场惜败，某个街头匆匆错过的音乐，或者是未曾意识到的错误。我总是会想，要是……就好了，我每次这么想着都觉得很有趣，人生有好多可能，像是好多部电影。我有时候就是喜欢什么也不干躺在床上想这些，很多偶然记下的细节在脑子里循环播放，我想从每件事情里面都总结出什么，吸取经验教训。像历史那样，避免前人的错误，但我就是做不到。或者说是不太喜欢各种道理，我比较喜欢想到什么做什么，但是即使是这样我也有一直想做的事情。

我想做点有意义的事情，就是那种别人一听就能想起我的事情。不是违法犯罪那种，也不是今日头条那种。就是比较有意思的事情有价值的东西，比如牛顿定律那种，一听就能想起牛顿。或者是相对论，想起爱因斯坦。不过我就打个比方，总之就是想留下点有个人价值的事情吧。比如做个好玩的游戏，有个好玩的发明发现啥的，但我感觉还是挺难的。

我学东西感觉还是太慢了，技术也比较落后吧。我总是喜欢刨根问底，我现在在学的计算机在这一点上就让我好痛苦。计算机里我最讨厌的就是封装，它屏蔽了我对原理的认识；最喜欢的东西也是封装，因为把自己的归纳和设计封装起来很有成就感。导致我每次看到一个技术或者一个功能，我总是喜欢自己动手实现一下。我感觉这是一个好的品质，我看网上书上都说这样好，但我又感觉这样不好。我是不是在做没有意义的事，我这样是不是不适合当下的快节奏的社会。短短的大学四年我应该将时间和精力去浪费在这些事情上嘛。

什么是浪费，什么是有价值的。我的做法是正确的嘛。我只是想试试想看看，就是感觉很神奇。我平时看课外书也是这样，总喜欢看些没用的东西，好多人多我说，这些没用的知识早晚都会帮到你，我也想这样想，但我更清楚，我可能这辈子也不会用到他们。但我就是想知道，我也有时候会突然想到一些内容想要对别人说，一些好玩的科普，一些好玩的典故。但是感觉大多数人都不太感兴趣，或者有的人觉得是在炫耀。所以我就不想说了。

感觉这么一想都是从好功利的角度出发，因为换个角度将，这些想法都是可以被反驳的。我感觉打出来的字都是好意识流的哦，这么一看感觉人的思绪也是好凌乱的，也是很矛盾的。今天突然想随便写一些东西，因为我想暑假把我的博客数量争取破80，所以随便水一水。今天和同学聊天，我说想试试不用库写一个深度学习的模型，emm用C++吧。但是他说不太可能，我感觉还是挺可能的，我打算接下来试一试。刚好找点事情做。之后再是学下图像加密什么的，最近听学长聊天，我感觉科研好重要哦。不过我对这个也挺感兴趣的。不过我想先学掉链接之后再说。不知道怎么下手哦好烦。也不知道怎么跟导师联系，我好怕问些好蠢的问题。

我感觉打游戏还是挺好玩的，玩我的世界，总有要干的事情，不过最好玩的还是向懂行的展示自己的成果，很好玩。就是下矿不太好玩，火把总是不够，怪物总是到处出来。我现在还开了困难模式，所以更难玩了。我想之后把怪物猎人和艾尔登法环通关。暑假好短呀。

太晚了，我先不写了。躺在床上玩一会儿手机就可睡觉了。

在上一章中的加载过程中，我们大致了解了动态链接的过程，接下来我们要进一步认知其背后的原理。

位置无关代码

共享库的主要目的就是让多个正在运行的进程共享内存中相同的库代码，从而节约内存空间。可是多个进程是怎么共享同样一个副本的呢？

给每个共享库分配有一个事先预备的专用的地址空间，然后有要求加载器总是在这个地址加载共享库。这样虽然很简单，但是对内存空间的使用效率差。即使进程不适用这个库，这部分空间也会被分配出来。而且难以管理，每当我们又有一个新的库们就需要重新分配一篇空间。久而久之，这会导致地址空间分裂成各种各样的内存碎片

为了避免这个问题，现代操作系统令共享模块的代码段可以加载到内存的任何位置，而无需链接器修改。这样就可以实现无限多个进程共享一个共享模块的代码段的单一副本。这种可以加载而无需重定位的代码称为位置无关代码（PIC）。可以通过-fpic选项指示GNU编译系统生成PIC代码。

对于在前面已经链接好了的目标模块，我们并不需要特殊的处理，因为他们的相对位置已经固定。我们可以用PC相对寻址来编译这些引用。然而对于共享模块定义的外部过程和全局变量的引用，我们需要进行处理：

PIC数据引用

下面我们要用到的方法是基于一个事实的，链接阶段之后，程序的代码段和数据段的距离（代码段首->数据段首）总是不变的。所以我们说代码段中任何指令和数据段中任何变量间的距离都是一个运行时的常量。与绝对内存的位置是无关的。

因此我们可以利用这个事实，在数据段的开始位置创建一个GOT表（全局偏移量表）。每个被目标模块引用的全局数据目标（过程或全局变量）都有一个8字节条目。编译器会为每个条目创建一个重定位记录。在加载时，动态链接器会将GOT中的每个条目包含其目标正确的绝对地址以供跳转。每个全局目标的目标模块都有自己的GOT。

我们以下图为例：

我们想要知道addcnt的地址，我们实际上只需要知道PC指向的地址和GOT表的起始位置，以及指定全局目标在GOT表中的索引，然后我们可以计算出固定距离 = （GOT基址-下一条指令的地址）+ GOT索引*8。之后我们就可以实现位置无关的数据引用了。

PIC函数调用

假设一个程序调用一个共享库定义的函数。编译器不知道这个函数的运行时地址，因为共享模块可能会被加载到任意内存位置。理想的方法时为它创建一个重定位记录，然后再动态链接器加载时解析它，可这也意味着在链接之后运行前，调用模块的代码段会被修改，可是我们又需要确保代码段只是可读的。因此我们使用延迟绑定技术+位置无关

使用延迟绑定技术，我们将函数调用的加载延迟到被调用的地方，这样可以避免长时间的加载过程。同时只有第一次过程调用的运行时开销比较大，之后的每次的调用只需要支付一次跳转指令和一个间接的地址引用。

通过延迟绑定实现函数调用的位置无关，是通过两个数据结构实现的：GOT 和 PLT(过程链接表)。如果一个目标模块调用定义在共享库中的任何函数，那么它都会生成自己的GOT和PLT。GOT是数据段的一部分。PLT是代码段的一部分。我们可以详细了解下他们的作用：

• 过程链接表(PLT)

  PLT是一个数组，其中每个条目都是一个十六字节的代码。PLT[0]是一个特殊条目，它跳转到动态链接器延迟绑定函数的入口，来修改GOT表指定符号的内容。每个被调用的库函数都有自己的PLT条目，每个条目负责调用一个具体的函数。PLT[1]调用系统启动函数(__libc_start_main)，它初始化执行环境，调用main函数并返回值。从PLT[2]开始条目调用用户代码调用的函数。

• 全局偏移量表(GOT)

  GOT是一个数组，每个条目都是8字节地址。和PLT联合使用时，GOT[0]和GOT[1]包含动态链接器在解析函数地址时需要的信息。GOT[2]是动态链接器ld-linux.so的模块的入口。其余每个每个条目对应一个被调用的函数，其地址在运行时被解析。每个条目都有一个相匹配的PLT条目。且初始时每个GOT条目都指向指定PLT条目的第二条指令。

下面我们将会演示一个延迟绑定的过程：

对于第一次调用：

• 我们会直接程序调用到addvec的PLT条目PLT[2]
• 第一条PLT指令通过间接跳转将控制传递到了第二条PLT指令（因为GOT表初始指向第二条指令）
• 然后将符号addvec的ID(0x1)压入栈中，将控制转移到PLT[0]中
• PLT[0]将存储在GOT[1]中的动态链接信息也压入栈中，然后将控制转移到动态链接器的入口。动态链接器将根据动态链接的符号信息和调用函数的符号ID来确定此时调用函数的绝对内存地址。并重写GOT[4]的存储地址，并将控制转移到addvec

后续调用：

• 控制传递到PLT[2]
• 不过这一次通过GOT[4]的间接跳转回将控制直接转移到addvec

库打桩机制

LInux链接器支持库打桩，它允许你截获对共享库的调用，取而代之执行自己的代码。使用过打桩机制，我们就可以追踪库函数的调用次数，验证和追踪它的输入和输出值，甚至将它替换为一个完全不同的实现。这样可以为开发者提供详细的调试信息。

它的核心思想是：给定一个需要打桩的目标函数，创建一个包装函数，它的原型和目标函数一样。使用某种特殊的打桩机制，你就可以欺骗系统调用包装函数而不是目标函数了。包装函数通常会执行它自己的逻辑，然后调用目标函数，再将目标函数返回值传递给调用者。

打桩可以发生在编译时，链接时，或当前程序被加载和执行的运行时。

编译时打桩

我们用下面这个程序作为例子，我们的目标时用打桩来追踪对malloc和free的调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// int.c
#include <stdio.h>
#include <malloc.h>
int main(){
    int* p = malloc(32);
    free(p);
    return 0;
}

// malloc.h
#define malloc(size) mymalloc(size)
#define free(ptr) myfree(ptr)

void* mymalloc(size_t size);
void* myfree(void* ptr);

//mymalloc.c
#ifdef COMPILETIME
#include <stdio.h>
#include <malloc.h>

void* mymalloc(size_t size){
    void* ptr = malloc(size);
    printf("malloc(%d) = %p\n",(int)size,ptr);
    return ptr;
}
void myfree(void* ptr){
    free(ptr);
    printf("free(%p)\n",ptr);
}
#endif

我们可以通过头文件中指示预处理器用对相应包装函数的调用替换对目标函数的调用：

1
2
3
4
5

ylin@Ylin:~/Program/test$ gcc -DCOMPILETIME -c mymalloc.c
ylin@Ylin:~/Program/test$ gcc -I . -o intc int.c mymalloc.o
ylin@Ylin:~/Program/test$ ./intc
malloc(32) = 0x5a54efd432a0
free(0x5a54efd432a0)

其中-DCOMPILETIME是条件编译的开关，当我们启用它时，相当于对所有编译文件#define COMPILETIME，这个时候我们的包装函数就是生效的，它会替换我们的目标函数，从而实现编译时的库打桩。

链接时打桩

Linux的静态链接器支持使用--wrap f的标志来进行链接时的打桩。这个标志链接器，将对符号f的引用解析为__wrap_f，把对符号__real_f的引用解析为f。因此我们可以写出我们用于链接时打桩的包装函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//mymalloc.c
#ifdef LINKTIME
#include <stdio.h>
void* __real_malloc(size_t size);
void __real_free(void* ptr);

void* __wrap_malloc(size_t size){
    void* ptr = __real_malloc(size);
    printf("malloc(%d) = %p\n",size,ptr);
    return ptr;
}
void __wrap_free(void* ptr){
    __real_free(ptr);
    printf("free(%p)\n",ptr);
}
#endif

然后我们将源文件编译成可重定位的目标文件：

1
2

ylin@Ylin:~/Program/test$ gcc -DLINKTIME mymalloc.c -c
ylin@Ylin:~/Program/test$ gcc -c int.c

然后再将其链接为可执行文件：

1
2
3
4

ylin@Ylin:~/Program/test$ gcc -Wl,--wrap,malloc -Wl,--wrap,free -o intc int.o mymalloc.o
ylin@Ylin:~/Program/test$ ./intc
malloc(32) = 0x57af4d75b2a0
free(0x57af4d75b2a0)

其中-Wl,option1,option2,...则是将option作为参数传递给静态链接器。从而实现链接时的库打桩。

运行时库打桩

编译时打桩我们需要能够访问程序的源代码，链接时打桩我们需要能够访问程序的可重定位对象文件。不过，我们可以通过一种机制实现在运行时打桩，它只需要能够访问可执行文件。这个机制的原理基于动态链接器的LD_PRElOAD环境变量

如果LD_PRELOAD环境变量被设置为一个共享库路径名的列表（以空格或符号分隔），那么当你加载和执行一个程序，需要解析未定义的引用时，动态链接器会先搜索LD_PRELOAD库，然后再搜索其他的库。基于这个机制可以实现对任意共享库的任何函数进行打桩。

我们重写一份对malloc和free的包装函数(我们使用dlsym来返回指向libc函数的目标函数)，并将其打包为共享库，通过修改LD_PRELOAD来劫持目标函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#ifdef RUNTIME
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>

void* malloc(size_t size){
    void* (*mallocp)(size_t size);
    char* error;
    //注意这里的RTLD_NEXT是GNU拓展的功能，用于忽略当前符号查找下一个符号（在此即查找标准函数）
    mallocp = dlsym(RTLD_NEXT,"malloc");	
    if((error=dlerror())!=NULL){
        fputs(error,stderr);
        exit(1);
    }
    void* ptr = mallocp(size);
    printf("malloc(%d) = %p\n",(int)size,ptr);
    return ptr;
}

void free(void* ptr){
    void (*freep)(void* ptr) = NULL;
    char* error;
    
    freep = dlsym(RTLD_NEXT,"free");
    if((error=dlerror())!=NULL){
        fputs(error,stderr);
        exit(1);
    }
    free(ptr);
    printf("free(%p)\n",ptr);
}
#endif

然后我们将其编译成共享库用于接下来的调用：

1

ylin@Ylin:~/Program/test$ gcc -DRUNTIME -shared -fpic -o mymalloc.so mymalloc.c -ldl

我们正常编译并运行主程序，会发现没有打桩行为：

1
2

ylin@Ylin:~/Program/test$ gcc -o intc int.c
ylin@Ylin:~/Program/test$ ./intc

可是我们可以通过修改动态链接的LD_PRELOAD实现运行时的打桩：

1
2
3

ylin@Ylin:~/Program/test$ LD_PRELOAD="./mymalloc.so" ./intc
malloc(32) = 0x62a4031192a0
free(0x62a4031192a0)

不过实际上这里遇到了问题，我们修改了printf，改用了系统调用write从而避免printf内部实现用到malloc从而导致无限递归。这样我们实现了运行时的库打桩，我们甚至可以利用它去对任何程序的库函数进行调用打桩：

介绍完了目标文件是怎么链接到可执行程序的，我们不妨进一步学习可执行程序是怎么被加载到内存中并运行的。以及动态链接库是怎么和程序一起被加载的。

可执行目标文件

我们已经学习了链接器是怎么将多个目标文件合并成一个可执行目标文件的。我们的C程序，从一开始的一组ASCII文本文件，被转换成了一个二进制文件。这个二进制文件包含加载程序到内存并运行它所需的所有信息。一个典型的ELF可执行文件有以下内容：

和可重定位目标文件还是有较大的区别。ELF头描述文件的总体格式。它还包括程序的入口点（entryPoint），也就是当程序运行时要执行的第一条指令的地址。.text .rodata .data节和可重定位目标文件中的节是相似的。此外，还有一个.init节，这个节中定义了一个小函数，叫做_init，程序初始化代码时会调用它。同时，因为可执行文件是完全链接的，所以不再需要rel节

ELF可执行文件被设计的很容易加载到内存中，可执行文件的连续的片被映射到连续的内存段。程序头部表则描述了这种映射关系。我们使用objdump -p来查看：

1
2
3
4
5
6

# 只读代码段
LOAD off    0x0000000000001000 vaddr 0x0000000000401000 paddr 0x0000000000401000 align 2**12
     filesz 0x000000000007d80d memsz 0x000000000007d80d flags r-x
# 读/写数据段
LOAD off    0x00000000000a4f50 vaddr 0x00000000004a5f50 paddr 0x00000000004a5f50 align 2**12
     filesz 0x0000000000005b60 memsz 0x000000000000b2d8 flags rw-

其中：

• off：目标文件中的段的第一个节的偏移
• vaddr/paddr：虚拟地址/物理地址（物理地址在现代操作系统中无意义）
• align：指定的对齐要求，使得段能够有效率的传送到内存中
• filesz：目标文件中的段大小
• memsz：内存中的段大小
• flags：运行时的访问权限

我们以读写数据段的加载为例。开始于内存地址0xa4f50处，总的内存大小为0xb2d8，于是从目标文件中偏移0xa4f50处开始的.data节中的0x5b60个字节初始化。该段剩下的字节对应于运行时将被初始化为0的.bss数据。

对于任何段s，链接器必须选择一个起始地址vaddr，使得：

1

vaddr mod align = off mod align

off是段在可执行文件本身的起始位置。根据对齐要求对齐，是为了更好的优化加载的效率。会在虚拟内存中进一步学习。

加载可执行文件

当我们运行一个程序时:

1

ylin@Ylin:~/Program/test$ ./prog

由于prog不是一个内置的shell命令，所以shell会将它视作一个可执行目标文件，通过调用驻留在存储器中称为加载器的操作系统代码来运行它。任何Linux程序，都可以通过调用exevce函数来调用加载器。

记载其将可执行目标文件中的代码和数据从磁盘复制到内存中，然后通过跳转到程序的第一条指令或入口点来运行该程序。这个将程序到内存并运行的过程叫加载

为了解释加载器的运行，我们还需要认识以下每个Linux程序的内存映像：

在LInux x86_64中，代码段总是从0x400000处开始的，后面是数据段。运行时堆在数据段之后，通过调用用malloc库向上增长。堆之后的区域则是为共享库模块保留的。用户栈是从最大合法与用户地址(2⁴⁸-1)开始的，向低地址处生长。栈上的地址，从2⁴⁸处开始，是为内核中的代码和数据保留的。

不过这只是简图，实际上的内存空间分布略有不同，由于对齐有要求，段之间会有一定的间隙。而且现代编译器使用地址空间布局随机化，使得每次程序运行时这些区域的地址都会改变，但他们的相对位置是不会改变的

当加载器运行时，它会一个内存映像。在程序头部表的引导下，加载器将可执行文件的片复制到代码段和数据毒啊。接下来加载器跳转到程序的入口，也就是_start函数的地址。这个函数在系统目标问及那ctrl.o中定义。_start函数调用系统启动函数__libc_start_main，该函数定义在libc.so中。它负责初始化执行环境，调用用户层的main函数，处理main函数的返回值，并在需要时将控制返回给内核。

加载器的具体工作原理实际上涉及到多个方面：进程、虚拟内存、内存映射。我们之后会回头重新理解分析这个过程。

动态链接共享库

静态库仍然面临着几个问题：

• 需要要更新和维护：这导致一个程序员如果想更新它的程序使用的库的最新版本。那他需要重新显式的链接一遍。
• 占用较多的空间资源：我们需要明确计算机中的空间资源始终是稀缺的，我们要尽可能的利用好计算机中的磁盘空间。但是静态链接则不符合这个问题。静态链接将目标模块复制到每一个使用它的目标文件，这就导致一个系统里可能有上百个这个目标模块。

为了解决这个问题，我们就要引入共享库的概念。共享库是一个目标模块，在运行或加载时，可以加载到任意的内存地址，并和一个在内存中的程序链接起来。这个过程称为动态链接，由一个叫做动态链接器的程序来执行，共享库也被称为共享目标，在LInux中以.so表示，在Windows中以.dll来表示

我们可以尝试构建一个动态链接库并使用它：

1
2
3

ylin@Ylin:~/Program/test$ gcc -o libtest.so -fpic -shared addvec.c multvec.c
# -fpic指示编译器生成位置无关代码	-shared指示链接器创建一个共享的目标文件
ylin@Ylin:~/Program/test$ gcc -o prog main.c ./libtest.so

共享库的共享方式和静态库不同。在任何给定的文件系统中，对于一个库只有一个.so文件，所有引用这个库的可执行程序，共享这个文件中的数据和代码。在内存中，一个共享库的.text节的副本，可以被不同的正在要运行的进程共享。我们会在之后详细的研究这个过程。动态链接的过程如下:

当加载器加载和运行可执行文件prog时，加载器注意到prog中包含一个.interp节，这一节包含动态链接器的路径名，动态链接器本身就是有一个共享目标（ld-linux.so）。加载器不会直接将控制传递给应用程序，而是加载和运行这个动态链接器。然后动态链接器通过执行下面的重定位完成链接任务：

• 重定位libc.so的文本和数据到某个内存段
• 重定位libtest.so的文本和数据到另一个内存段
• 重定位prog中所有堆由libc.so和libtest.so定义的符号的引用

最后动态链接器将控制传递给应用程序。此时共享库的位置就固定了，在程序执行的过程中不再改变。

从应用程序中加载和链接共享库

正常情况下，我们的动态链接是在程序加载之后，执行之前进行的。可是在一些特殊的情况下，我们需要在运行的过程中（比如热更新、插件拓展…）动态链接共享库。此时我们可以用到LInux系统为动态链接器提供的接口——允许应用程序在运行是加载和链接共享库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include<dlfnc.h>

void* dlopen(const char* filename, int flag);	
// 成功则返回指向句柄的指针，失败则返回NULL
// dlopen函数用来将共享库映射到内存，如果在编译时设置了 -rdynamic 那么当前可执行文件里的全局符号也可以被共享库使用。此外，RTLD_GLOBAL 设置可以让此次打开的库里的符号能被后续加载的库使用。RTLD_NOW和RTLD_LAZY分别时立即解析和延迟解析。他们可以通过|和RTLD_GLOBAL拼接

void* dlsym(void* handle, char* symbol);
// 若成功则返回指向符号的指针，失败则返回NULL
// dlsym的输入是一个指向前面已经打开了的共享库的句柄和一个symbol的名字

int dlclose(void* handle);
// 如果成功返回0，失败则返回-1
// 如果没有其他共享库还在使用这个共享库，就关闭它

const char* dlerror(void);
// 如果前面的几个函数的调用失败，则为错误信息。如果调用成功，则为NULL
// dlerror会返回有一个字符串，它描述调用时发生的最近的错误

我们可与尝试编写一个程序来在运行过程中加载我们的共享库，然后调用它的addvec例程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<stdio.h>
#include<stdlib.h>
#include<dlfcn.h>

int x[] = {1,2,3,4,5};
int y[] = {1,2,3,4,5};
int z[5];

int main(){
	void* handle;
	void (*addvec)(int*,int*,int*,int);
	char* error;

	handle = dlopen("./libtest.so",RTLD_LAZY);
	if(handle==NULL){
		fprintf(stderr,"%s\n",dlerror());
		exit(1);
	}

	addvec = dlsym(handle,"addvec");
	if((error=dlerror())!=NULL){
		fprintf(stderr,"%s\n",error);
		exit(1);
	}

	addvec(x,y,z,5);
	printf("z = [%d %d %d %d %d]",z[0],z[1],z[2],z[3],z[4]);

	if(dlclose(handle)<0){
		fprintf(stderr,"%s\n",dlerror());
		exit(1);
	}
	return 0;
}

编译后可以正常运行！我们简单的实现了运行过程中动态库的加载和更新。

接下来我们要探讨学习一下符号解析和重定位实现的原理。

符号解析

连接器解析符号引用，实际上就是将每个引用，和它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。当局部符号的引用和引用定义在相同模块的时候，符号解析简单明了。编译器只允许每个模块中每个局部符号只有一个定义，因此编译器要确保它们又唯一的名字。

不过，对于全局符号的引用解析就十分难以处理。当编译器遇到一个不是在当前模块定义的符号时，会假设这个符号已经被其他模块定义了，生成一个链接器符号表条目，将它交给链接器处理。如果链接器在它的任何输入模块中都找不到这个被引用的符号的定义，就会报错。比如我们尝试编译这个程序:

1
2
3
4
5

void foo();
int main(){
	foo();
	return 0;
}

编译器会毫无障碍的编译，但是链接器却无法解析对foo的引用：

1
2
3

ylin@Ylin:~/Program/test$ gcc test.c -o test -Wall -Og
/usr/bin/ld: /tmp/ccKOmx5V.o: in function `main':
test.c:(.text+0xe): undefined reference to `foo'

因此对于全局符号的处理比较困难，而且可能会出现多个目标文件定义相同名字的全局符号。此时，链接器要么选出一个定义抛弃其他定义，要么就给出一个错误。

链接器如何解析多重定义的全局符号

链接器的输入是一组可重定位目标模块。每个模块定义一组符号，有的是局部的（只对本地模块可见），有的是全局的（对其他模块也可见）。但是如果多个模块的定义了同名的全局符号，Linux编译系统会怎么做？

在编译时，编译器向汇编器输出每个全局符号，或是强或是弱，而汇编器把这个信息隐含地编码在可重定位的目标文件的符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。

Linux链接器会根据以下规则来处理多重定义的符号名：

• 不允许有多个同名的强符号
• 如果有一个强符号和多个弱符号同名，那么选择强符号。
• 如果有多个弱符号同名，那么从这些弱符号中任意选择一个

我们可以看下各个规则的具体表现：

• 规则一

1
2
3
4
5
6
7
8

//1.c
int main(){
	return 0;
}
//2.c
int main(){
	return 0;
}

1
2
3
4

ylin@Ylin:~/Program/test$ gcc -o prog 1.c 2.c
/usr/bin/ld: /tmp/ccYSd6rb.o: in function `main':
2.c:(.text+0x0): multiple definition of `main'; /tmp/ccogxBxO.o:1.c:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status

这是因为强符号main被定义了多次，造成了冲突。下面也是

1
2
3
4
5
6
7
8
9
10

//1.c
int x=114;
int main(){
	return 0;
}
//2.c
int x=514;
int f(){
	return 0;
}

1
2
3

ylin@Ylin:~/Program/test$ gcc -o prog 1.c 2.c
/usr/bin/ld: /tmp/cc9GFQfr.o:(.data+0x0): multiple definition of `x'; /tmp/ccljmBRr.o:(.data+0x0): first defined here
collect2: error: ld returned 1 exit status

这里是因为被初始化的全局变量（强符号）x出现了多次，造成冲突。

• 规则二

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//1.c
#include <stdio.h>
int x=114;
int main(){
    f();
    printf("%d\n",x);
	return 0;
}
//2.c
int x;
int f(){
    x = 514;
	return 0;
}

1
2
3

ylin@Ylin:~/Program/test$ gcc -o prog 1.c 2.c
ylin@Ylin:~/Program/test$ ./prog
514

这里虽然没有造成冲突，但是可以看到另一个模块对x的使用，修改了它的值。

• 规则三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//1.c
#include <stdio.h>
int x;
int main(){
    x = 114;
    f();
    printf("%d\n",x);
	return 0;
}
//2.c
int x;
int f(){
    x = 514;
	return 0;
}

1
2
3

ylin@Ylin:~/Program/test$ gcc -o prog 1.c 2.c
ylin@Ylin:~/Program/test$ ./prog
514

结果和上面基本一致，但是我们并不知道最终使用了哪个符号，因为它们都是弱符号，是随机的。

当然现代的编译器为了避免多重定义的全局符号给我们带来的错误，往往在编译时，会开启GCC-fno-common选项，以保证遇到多重定义的全局符号时，会发生错误，无法通过链接。

在上一篇中我们提到了编译器会按规则将符号分配到COMMON或.bss，但是我们并不清楚为什么要这样做。现在我们知道了，在编译器翻译一个模块时，对于一个弱全局符号，它并不知道其他模块是否也定义了相同的符号。如果是的话，它无法预测链接器会使用多重定义中的哪一个，所以编译器将它这个弱全局符号放入COMMON中，交给链接器来决定。如果这个符号被初始化为0的话，那么它就是一个强符号，编译器就可以直接将它分配为.bss。相似的，对于静态变量(不用考虑多重定义)，也是如此放入.bss或.data。

与静态库链接

到目前为止，我们都是假设链接器会读取一组可重定位目标文件，并将其链接起来，形成一个输出的可执行文件。实际上，所有的编译系统都支持一种机制——把所有相关的目标模块打包成为一个单独的文件，被称为静态库。当链接器要构造一个输出的可执行文件时，它只会复制静态库中被程序引用的目标模块。这么做有以下好处：

• 如果将模块合并到一个可重定位目标文件中，会导致程序每次链接都会包含一份完整的标准库。其中大部分的模块并不会被使用，这导致程序占用的磁盘空间会更大。
• 如果将标准函数内联至编译器，这虽然很便捷。但是会导致编译器开发的难度更大。且每次标准库的更新都需要修改编译器
• 如果为每个标准函数都创建一个独立的可重定位文件，将他们放在一个目录下。这会导致链接时需要大量的显式链接合适模块到可执行文件中。

所以链接库的概念被提出来。相关的函数可以被编译为独立的目标模块然后封装在一个单独的静态库文件。然后应用程序可以在命令行中指定单独的文件名字来使用这些在库中定义的函数。

在链接时，链接器将只复制被程序引用的模块，这就减少了可执行文件在磁盘和内存中的大小。且减少了程序员对库文件引用次数。

在Linux中，静态库以一种称为存档的特殊文件格式存放在磁盘中。存档文件时一组连接起来的可重定位目标文件集合，它的头部来描述每个成员目标文件的大小和为止。存档文件的后缀为.a

我们可以简单的实现一下这个过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//addvec.c
int addcnt=0;
void addvec(int*x,int*y,int*z,int n){
    int i;
    addcnt++;
    for(i=0;i<n;i++)
        z[i] = x[i] + y[i];
}
//multvec.c
int multcnt = 0;
void multvec(int*x,int*y,int*z,int n){
    int i;
    multvec++;
    for(i=0;i<n;i++)
        z[i] = x[i]*y[i];
}

然后我们用这两个函数创建一个静态库：

1
2
3
4

ylin@Ylin:~/Program/test$ gcc -c addvec.c multvec.c
ylin@Ylin:~/Program/test$ ls
addvec.c  addvec.o  multvec.c  multvec.o
ylin@Ylin:~/Program/test$ ar rcs libtest.a addvec.o multvec.o

然后我们可以利用这个静态库来编写我们的程序，来验证是否只调用了我们需要的目标模块：

1
2
3
4
5
6
7
8
9
10
11
12

#include <stdio.h>
#include "test.h"	//包含两个函数的原型

int main(){
        int x[4] = {1,2,3,4};
        int y[4] = {1,2,3,4};
        int z[4];

        multvec(x,y,z,4);
        printf("z = [%d %d %d %d]",z[0],z[1],z[2],z[3]);
        return 0;
}

使用gcc -static -o prog main.o -L . -ltest编译（其中-static是静态链接，-L指定静态库的查询目录，-ltest是./libtest.a的缩写），我们使用：

1

ylin@Ylin:~/Program/test$ objdump -d prog | grep "addvec"

发现程序中并没有addvec目标模块，静态库的链接很好的完成了工作。整个过程我们可以用这个图来大致的表现。

链接器如何使用静态库来解析引用

解释一下静态库使用的原理和可能遇到的一些问题。

Linux链接器在解析外部引用的时候，是从左往右按照编译器驱动程序命令行上的顺序来扫描，可重定位目标文件和存档文件（驱动程序会自动将源程序文件翻译成可重定位目标文件）。在扫描中，链接器会维护一个可重定位目标文件中的集合E(该集合文件中的目标文件会被链接成可执行文件)，一个未解析的符号集合U（引用了但是尚未定义的符号），一个在前面的输入文件中已定义的符号集合D。初始时，E、U、D均为空：

• 对于命令行上的每个输入文件f，链接器会判断它的类型，是目标文件还是存档文件。如果是目标文件，则将其放入E中，然后修改U和D来反映f中符号定义和引用，并继续下一个输入文件。
• 如果f是一个存档文件，那么链接器就尝试匹配U中未解析的符号和由存档文件成员定义的符号。如果某个存档文件成员定义了一个符号来解析U中的一个引用，那么就将m加到E中，并且修改U和D来反映m的符号定义和引用。对存档文件中的每一个程序进行这个尝试，知道U和D都不再变化。此时不包含在E中的目标文件被丢弃。开始处理下一个输入文件。
• 如果链接器处理完所有的输入文件之后，U是非空的，链接器就会输出一个错误并停止。反之，则合并重定位E中的目标文件，构建输出的可执行文件。

不过因此，命令行上的库和目标文件的顺序也很重要。在命令行中，如果定义一个符号的库出现在引用这个符号的目标文件之前，那么引用就不会被解析，链接会失败。对于存档文件之间的顺序也是如此。如果一个库a中的引用在另一个库b中被定义，那么要先a后b。反之，如果库直接都是相互独立的，就可以不在乎输入顺序。

重定位

当链接器完成了符号解析，代码中的每个符号引用和它的符号定义（即目标模块中的符号表条目）就会被关联起来。此时，链接器就知道它的输入目标模块中的代码节和数据节的确切大小。现在就可以重定位操作了，在这个步骤中，将合并输入模块，并为每个符号分配运行时的地址。

• 重定位节和符号定义:

  在这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。然后链接器将运行时内存地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给每个节的每个符号。当这一步完成时。程序中的每条指令和全局变量都有唯一的运行时内存地址。

• 重定位节中的符号引用：

  在这一步中，链接器修改代码节和数据节中对每个符号的引用，使得他们指向正确的运行时的地址。要执行这一步，链接器依赖于可重定位目标模块中称为重定位条目的数据结构，我们接下来将会描述这种数据结构。

重定位条目

当汇编器生成一个目标模块时，它并不知道数据和代码在运行时会被存放在内存中的哪个位置。也不知道模块引用的外部定义的函数或全局变量的位置在哪里。所以，当汇编器遇到最终位置未知的目标引用，他就会生成一个重定位条目（用来为链接器修正未知提供“导航”），用来告诉链接器，在合并目标模块时如何修改这个引用。代码的重定位条目存放在.rel.text，数据的重定位条目存放在.rel.data

下面是一个典型的重定位条目格式：

1
2
3
4
5
6

typedef struct{
    long offset;
    long type:32,
    	symbol:32;
    long addend;
}Elf64_Rela;

• offset：需要被修改的引用的节偏移
• type：如何修改新的引用
• symbol：被修改的引用应该指向的符号
• addend：一个有符号常数，个别类型的重定位需要使用它对被修改引用的值做偏移调整

ELF定义了32中不同的重定位类型，但是我们需要考虑两种最常见的类型：

• R_X86_64_PC32：

  重定位一个使用32位PC相对地址的引用。一个PC相对地址就是据PC当前运行时值的偏移量。当CPU执行一条使用PC相对寻址的指令时，他就将在指令中编码的32位值加上当前的PC值，得到有效地址，PC值通常是下一条指令在内存中的地址

• R_X86_64_32:

  重定位一个使用32位绝对地址的引用。通过绝对寻址，CPU直接使用在指令中编码的32位值作为有效地址

重定位符号引用

根据重定位算法，来分析一下重定位的过程。下面展示重定位算法的伪代码，为了方便表示，假设每个节s是一个字节数组，每个重定位条目r都是一个类型为Elf64_Rela的结构。用ADDR()来获取对应的运行时的地址：

1
2
3
4
5
6
7
8
9
10
11
12
13

for (section:s){
    for (relocation_entry:r){
        refptr = s + r.offset;	//重定位编码的地址
        //相对PC地址引用
        if(r.type == R_X86_64_PC32){
            refaddr = ADDR(s) + r.offset;	//运行时的待重定位地址
            *refptr = (unsigned)(ADDR(r.symbol) + r.addend - refaddr);
        }
		//绝对PC地址引用        
        if(r.type == R_X86_64_32)
            *refptr = (unsigned)(ADDR(r.symbol) + r.addend);
    }
}

以下面这个反汇编代码为例，我们来分析一下链接器是怎么重定位这些引用的：

重定位PC相对引用

第6行，call开始于节偏移值为0xe的地方，包括1字节的操作码0xe8，还有四个字节的占位符。其中sum的重定位条目r为：

1
2
3
4

r.offset = 0xf
r.symbol = sum
r.type = R_X86_64_PC32
r.addend = -4

这些字段告诉链接器修改开始于偏移量0xf的32位PC相对引用，在运行时它会指向sum例程。此时链接器已知：

1
2

ADDR(s) = ADDR(.text) = 0x4004d0
ADDR(r.symbol) = ADDR(sum) = 0x4004e8

我们重定位的过程应该是这样的：

1
2
3
4
5
6

refaddr = ADDR(s) + r.offset
    	= 0x4004d0 + 0xf
    	= 0x4004df
*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr)
    	= (unsigned) (0x4004e8 + (-4) - 0x4004df)
    	= (unsigned) (0x5)

最终得到4004de: e8 05 00 00 00 callq 4004e8 <sum>

重定位绝对引用

第4行，mov开始于节偏移值位0x4的地方，包括1字节的操作码0xbf，还有四个字节的arrary地址的占位符。其中array的重定位条目r为：

1
2
3
4

r.offset = 0xa
r.symbol = array
r.type = R_X86_64_32
r.addend = 0

这些字段告诉链接器要修改从偏移量0xa开始的绝对引用，这样在运行时它会指向arrary的第一个字节。此时链接器已知：

1

ADDR(r.symbol) = ADDR(array) = 0x601018

我们重定位的过程为是这样的：

1
2
3

*refptr = (unsigned) (ADDR(r.symbol) + r.addend)
     	= (unsigned) (0x601018 + 0)
    	= (unsigned) (0x601018)

最终得到4004d9: bf 18 10 60 00 mov $0x601018,%edi。最终的效果如下：

开始学习新的章节——链接。我们现在要研究在gcc调用的过程中，到底有哪些过程是被我们所忽略的，在编译的过程中它们又有着什么作用呢？

编译器驱动程序

我们以下面的这段代码为例，将以此来分析整个编译的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//file 1
int sum(int *a,int n);

int array[2] = {1,2};

int main(){
    int val = sum(array,2);
    return val;
}
//file 2
int sum(int *a,int n){
    int i,s = 0;
    
    for(int i=0;i<n;i++){
        s += a[i];
    }
    return s;
}

大多数编译系统都会提供一个编译驱动程序，在用户需要时调用语言处理器，编译器，汇编器，链接器。比如我们要用GNU编译系统进行编译时，我们就需要使用gcc编译驱动：

1

ylin@Ylin:~/Program/test$ gcc -Og -o test main.c sum.c

但是实际上省略了很多中间过程并没有让我们看到，我们可以通过加入-v参数来观察这个过程：

红色框出来的分别时ccl as ld的调用，我们之后会分析这几个程序的作用。现在我们可以将从ASCIII源码到执行文件的编译驱动的过程总结一下：

首先预处理器cpp(预处理器实际上和编译器是集成在一起的)将ASCII源文件翻译成一个ASCII码的中间文件

1

ylin@Ylin:~/Program/test$ cpp main.c -o main.i

然后驱动程序运行C编译器ccl（这里我们使用gcc实现），将中间文件翻译成汇编语言：

1

ylin@Ylin:~/Program/test$ gcc -S main.i

接着驱动程序运行汇编器as，将main.s翻译成一个可重定位目标文件main.o:

1

ylin@Ylin:~/Program/test$ as main.s -o main.o

然后对sum.c进行同样的操作，得到sum.o。然后驱动程序运行链接器程序ld（在gcc -v的过程中可以看到链接过程使用的是collect2，实际上是ld的封装用法），将main.o和sum.o以及一些必要的系统目标文件编译起来，创建一个可执行的目标文件：

1

ylin@Ylin:~/Program/test$ ld -o test sum.o main.o

最后当我们执行编译出来的test程序时，shell会调用一个名为加载器loader的函数，将可执行文件中的代码和数据复制到内存，然后将控制转移到这个程序的开头：

1

ylin@Ylin:~/Program/test$ ./test

不过实际上，这些中间过程是被什么略的，其中生成的中间文件会被存放在\tmp下，待编译结束后被清理。

静态链接

像ld这样的静态连接器以一组可重定位目标文件个命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。输出的可重定位目标文件由各种不同的代码和数据节section组成，每一节都是一个连续的字节序列。指令在一个节中，初始化了的全局变量在另一个节中，而未初始化的变量又在另一个节中…

为了构建一个可重定位文件，链接器要实现一下的功能：

• 符号解析：

  目标文件会定义和引用符号。每个符号可能对应一个全局变量、一个函数或一个静态变量（static声明的变量），符号解析则是将每个符号的引用和它的定义联系起来。

• 重定位：

  编译器和汇编器会生成从地址0开始的代码和数据节。链接器通过把每个符号的定义和一个内存位置关联起来，从而重定位这些节，然后修改这些符号的引用，使得它们指向这个内存位置。链接器使用汇编器产生的重定位信息条目的详细指令给，进行这些重定位操作

之后我们会详细的分析这几个过程。实际上我们只需要清除，目标文件实际上就是字节块的集合。这些块中，有的包含程序代码，有的包含程序数据，其他的则包含引到链接器和加载器的数据结构。链接器负责将这些块连接起来，确定被连接块的运行时的位置，并且修改代码和数据块中的各种位置。

目标文件

目标文件有三种形式：

• 可重定位目标文件：

  主要包含二进制代码和数据，其形式可以在链接时与其他的可重定位目标文件合并起来，创建一个可执行目标文件。

• 可执行目标文件：

  包含二进制代码和数据，其形式可以直接被复制到内存中并执行。

• 共享目标文件：

  一种特殊类型的可重定位目标文件，可以在加载或者运行时，被动态地加载进内存并链接。

编译器和汇编器生成可重定位目标文件（包括共享目标文件）。链接器生成可执行目标文件。

从技术上来说，一个目标模块就是一个字节序列，而一个目标文件就是一个以文件形式存储在磁盘中的目标模块。本质上它们是一样的。

不同的系统有不同的目标文件格式，如：

• Unix ：a.out格式
• Windows ：可移植可执行格式（PE）
• Mac ：Mach-O格式
• 现代Linux/Unix ：可执行可链接格式（ELF）

可重定位目标文件

这是一个典型的ELF可重定位目标文件的格式。我们从ELF头开始说起，我们可以使用readelf -h来获取一个程序的ELF头信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

ylin@Ylin:~/Program/test$ readelf -h test
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Position-Independent Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x1040
  Start of program headers:          64 (bytes into file)
  Start of section headers:          14016 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         13
  Size of section headers:           64 (bytes)
  Number of section headers:         29
  Section header string table index: 28

以一个16字节长的字节序列Magic开始，这个序列用于系统判断是否为ELF文件格式（字节序和位宽），ELF头的其他部分则包含了帮链接器语法分析和解释目标文件的信息。其中包括

• ELF头的大小 –> Size of this header
• 目标文件的类型 –> Type
• 机器类型 –> Machine
• 节头部表的文件偏移 –> Start of section headers
• 节头部表条目的大小和数量 –> Number of section headers + Size of section headers

不同节的位置和大小是由节头部表描述的，其中目标文件中的每个节都有一个固定的条目（entry）。夹在ELF头和节头部表中间的都是节。一个典型的ELF可重定位目标文件包含以下的节：

• .text

  已编译程序的机器代码

• .rodata

  只读数据(常量数据，运行期间不可更改)

• .data

  已初始化的全局和静态C变量。局部C变量在运行时被保存在栈中，不被保存在节

• .bss

  未初始化的全局和静态C变量，以及所有被初始化为0的全局或静态变量。在目标文件中这个节不占据任何实际的空间，仅仅是一个占位符。区分已初始化和未初始化是为了空间效率，未初始化变量不需要占据任何实际的磁盘空间。运行时，在内存中分配这些变量，初始化为0

• .symtab

  一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。和使用-g编译出的程序得到的符号表信息不同，.symtab中不包含局部变量的条目

• .rel.text

  重定位节。一个.text节中位置的列表，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。这个时候.text中有哪些地址/符号需要在链接或加载时被修正的内容，就记录在.rel.text中。

• .rel.data

  数据的重定位节。记录.data中哪些变量/指针需要链接器修改地址

• .debug

  调试符号表，其条目是程序中定义的局部变量和类型定义，程序中定义和引用的全局变量，以及原始的C源文件。只有在使用gcc时加上-g选项，才可以得到这张表

• .line

  原始C源程序中的行号和.text节中机器指令之间的映射。只有使用-g时得到。

• .strtab

  一个字符串表，内容包括其他节中的字符串信息。它自己不包含逻辑结构，只是被其他节按索引引用，用来存放符号名，段名，动态库名等文本。因此其他节只需要存放对应字符串的偏移索引就行了，真正的字符内容放在.strtab.

符号和符号表

符号

每个可重定位模块m都有一个符号表，它包含m定义和引用的符号的信息。在连接器的上下文中，有三种不同的符号：

• 由模块m定义并能被其他模块引用的全局符号。全局符号对应于非静态的C函数和全局变量。
• 由其他模块定义并被模块m引用的全局符号，称之为外部符号，对应于在其他模块中定义的非静态C函数和全局变量
• 只被模块m定义和引用的局部符号。它们对应于带static属性的C函数和全局变量。这些符号在模块m中任何位置可见但是，不能被其他模块引用。

链接器不关心本地局部变量。同样的.symtab中的符号表也不包含对应于本地非静态程序变量的任何符号。这些符号在运行时由栈管理。不被链接器考虑。

不过定义为带有Cstatic属性的本地过程变量时不在栈中管理的（使用static属性可以隐藏模块内部的变量和函数声明，就像class中使用private，来保护变量和函数只能被本地模块使用）。相反，编译器在.data或.bss中会为每个定义分配空间，并在符号表中创建一个有唯一名字的本地连接符号。比如：

1
2
3
4
5
6
7
8

int f(){
    static int x=0;
    return x;
}
int g(){
    static int x=0;
    return x;
}

此时编译器会向汇编器输出两个不同名字的局部链接符号。比如，可以用x.1表示函数f中的定义，用x.2表示函数g中的定义。

符号表

符号表是由汇编器构造的，使用的是编译器给出的符号。ELF符号表被存放在.symtab中。这个符号表包含着一个条目的数组，其条目结构如下：

1
2
3
4
5
6
7
8
9

typedef struct{
    int name;			
    char type:4;		
    	 binding:4;		
    char reversed;		
    short section;		
    long value;			
    long size;			
}ELF64_symbol;

它们的作用分别是：

• name：字符串表中的字节偏移，指向符号的字符串名字
• type：表示符号的种类（数据/函数）
• binding：表示符号的可见性（本地/全局）
• reverse：暂时无用，留作数据对齐。
• section：节头部表的索引，用于定位节
• value：指定节中的偏移，相当于一个绝对运行时的地址
• size：目标的大小（字节大小）

每个符号都会被分配到目标文件的某个节中。由section字段表示，该字段也是一个到节头部表的索引。有三个特殊的伪节，它们在节头部表中并没有条目：

• ABS，表示符号值是绝对的，不应该被重定位
• UNDEF，表示符号未定义，就是在本模块中使用，但是在其他地方定义的符号。
• COMMON，表示未被分配位置的未初始化的数据目标 > 只有在可重定位目标文件中才有伪节，可执行目标文件中没有

对于COMMON符号，value给出的是对齐要求，size给出的是最小的大小。

这么一看COMMON和.bss似乎差不多。现代的汇编器根据以下规则来将符号分配到COMMON和.bss中：

1
2

COMMON  未初始化的全局变量
.bss	未初始化的静态变量，以及初始化为0的全局变量和静态变量

之后我们会详细解释这个设置的原因。

我们学习一下现代计算机中的存储器架构，以及它的一些具体实现。我们该如何利用存储器的性能来实现对局部性的高效利用？它背后的原理又是什么呢？

存储器存储结构

不同的存储器有着不同的存储技术和存储性能，可喜的是，它们的属性很好的互相补齐各自的不足，利用这个性质，出现了一种组织存储器系统的方法，称之为存储器层次结构。

从高层往底层走，存储器的容量、成本、速度都越来越慢。所以我们以下面为基础，不断的向上层提供数据。其中我们就不得不提到存储器结构中最为关键的 缓存

缓存

存储器之间的属性有着较大的差异，通常我们需要在其之间设置一个缓冲，以更好的实现数据的读取和转移。其中，高速缓存就是一种小而迅速的存储设备，它作为更大、更慢的存储器设备的数据的缓存区域。而使用高速缓存的过程我们就称之为缓存。缓存的基本原理如下：

对于缓存，我们还要理解它的各个状态：

缓存命中

当程序需要k+1层的某个数据对象d时，它首先到k层中去查找，如果找到了，则此时数据d缓存命中。

缓存不命中

相反，如果k层没有找到数据d时，我们则发生缓存不命中。此时k层的缓存从第k+1层中取出包含d的块。如果此时k层的缓冲已经满了，就会覆盖其中的一个块，这个过程叫做替换/牺牲。具体替换哪个块由替换策略所决定。

缓存不命中的状态：

• 强制不命中（冷不命中）：此时缓存为空，无论什么数据都不会命中。
• 容量不命中：当前的工作集的大小大于缓存的大小。
• 冲突不命中：有些替换策略会将符合同一规则的块指定替换到上层换从中的指定块，这种策略比较简洁容易实现。此时就可能会出现同组的块互相冲突。类似于哈希表中的哈希冲突。

存储器层次结构的本质是，每一层存储设备都是较低一层的缓存。所以在每一层中，都需要有某种形式的逻辑来管理缓存（将缓存分块，在不同层之间传送块，判定是否命中，并处理它们），不论是硬件还是软件。下面有一张表，大致的说明了各个缓存的管理实现：

高速缓存存储器

为了更好的理解存储器缓存的原理，我们需要介绍一下高速缓存存储器的组织架构。

计算机的地址数量通常由存储器的位数所决定，当存储器的位数为m时，计算机的内存空间就有2^m个地址。而高速缓存存储器的结构如下：

一个高速缓存存储器被分作S(2^s)个高速缓存组，每个高速缓存组有E个高速缓存行，每个高速缓存行中有B(2^b)个数据块。我们通过对地址字段进行划分，从而实现对高速缓存的定位。

当我们拿到一个地址，想要尝试从高速缓存存储器中取出一个数据块时，都要经历以下过程：

• 读组索引：根据地址中的s位的数据来确定数据所在的缓存组
• 标记比对：当数据行有效时，与其比较t位标记值，如果标记相同则确定数据存储行。
• 读块索引：根据地址中的b位数据确定数据在缓存块中的偏移地址。
• 缓存不命中：则重复上述的步骤向下取需要的数据。

你可能会好奇，为什么使用中间的几位作为组索引，而不是高位呢？这是为了避免高位的一致性从而导致连续的内存空间被分配到一个组，从而引发冲突不命中，下图很好的说明了这一点：

同时，根据每个组的高速缓存行的数量，也可以分成以下高速缓存存储器类型：

• 直接映射高速缓存

  E=1，每组高速缓存行只有一行，所以不需要再组中查找对应的缓存行，且实现起来比较简单。但是对于冲突不命中的应对上效果很差，因为每个组只能取一条数据。

• 全相联高速缓存

  S = 0，E = C/B。所有的缓存行都存储在一个组中，由于没有固定的映射关系，所以任何主存块可以存储在缓存的任何位置。灵活性很高，很好的避免了冲突的关系。但是由于结构复杂，且每次访问时，需要匹配缓存行，消耗了大量的时间，访问速度慢。

• 组相联高速缓存

  相当于直接映射和全相联的中和版本。每个组有一定的缓存行。

高速缓存层次结构分析

我们给出一个真实的高速缓存层次结构

实际上高速缓存存储器不仅存储数据，同时存储着指令，只不过指令是只读的，数据则可读可写。芯片上的每个核有着自己的高速缓存，同时共享一个高速缓存和主存。在复杂的资源共享管理下，实现工作

高速缓存参数的性能影响

定性的分析高速缓存的影响参数：

• 高速缓存大小

  较大的高速缓存可以提高缓存的命中率，但也意味着会造成更大的运行开销，这也是为什么越上层的存储器越小，这可以减少访问的时间。

• 块大小

  大的块可以更好的利用程序中的空间局部性。但是在缓存空间给定的情况下，较大的块会导致较少的缓存内存行，会加剧数据冲突。从而导致时间局部性所受到的损耗大于空间局部性带来的好处。

• 相联度

  即高速缓存行数E的选择，较高的相联度可以减少冲突不命中导致的不命中处罚，但是访问速度低，而且较大的块也会导致更严重的不命中处罚。而较低的相联度虽然访问速度快，但是也会导致更多的不命中处罚。所以需要根据不同的情况选择不同的相联度。

  在L1中，通常使用相联度低的存储方式，因为不命中的处罚较小（数据较少）。但是对于底层的主存等区域，每次不命中的处罚很严重，所以要提高相联度，尽可能的减少不命中。

• 写策略

  直写（立即将高速缓存块写入第一层的存储器中）比较容易实现，而且可以使用写缓冲区进行内存更新，但是会导致总线的流量增大。写回（尽可能的推迟更新，只有该块被替换的时候才将数据块更新到第一层的存储器中）引起的传送会更少。此外，越往底层走，传送的时间更长。所以在下层，会尽可能的使用写回。

局部性

一个具有良好局部性的程序，通常会有着更好的效率。它们倾向于使用离它们较近的数据项，或是最近引用过的数据项，这被称为局部性原理。

局部性别分为空间局部性和时间局部性。对于一个良好的时间局部性程序，被引用过一次的内存位置会在不久后再次被引用。对于一个良好的空间局部性程序，如果一个内存位置被使用，那么它领近的内存位置也会被使用。

对程序数据引用的局部性

我们以一个简单的程序为例：

1
2
3
4
5
6
7

int sumvec(int v[N]){
    int i,sum=0;
    for(i=0;i<N;i++){
        sum += v[i];
    }
    return sum;
}

对于sum，由于它在每次迭代中都被使用，所以我们称它有良好的时间局部性，但是它是一个标量，所以不存在空间局部性。对于向量v，它是被顺序读取的，所以我们称它有良好的空间局部性，但是由于每个位置只访问一次，所以我们说v的时间局部性很差。

我们说像sumvec这样顺序访问一个向量每个元素的函数，是具有步长为1的引用模式（相对于元素的大小）。有时我们称步长为1的引用模式为顺序引用模式。一个连续向量中，每隔k个元素进行访问，就称为步长为k的引用模式，步长越长，空间局部性就越差。

取指令的局部性

程序指令存放在内存中，CPU需要取出这些指令，所以我们也可以评价一个程序关于取指令的局部性。对于循环，通常是在连续的空间中进行的，所以它有良好的空间局部性，由于它会被反复调用，所以也有着良好的时间局部性。举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// clang-format off
hotblock1:
    Stmts; // <-- 热！
    if (/* 边界条件不成立 */ true)
        goto hotblock2; // 经常发生！ ------+
coldblock:                           /*   |   */
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |  跨越了大量指令，代价高昂！
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
hotblock2:                          /*    |   */
    Stmts; // <- 热！           <----------+

1
2
3
4
5
6
7
8
9
10
11
12
13

// clang-format off
hotblock1:
    Stmts; // <-- 热！
    if (/* 边界条件 */ false)
        goto coldblock; // 很少发生
hotblock2:                         /*   |  低代价！  */
    Stmts; // <- 热！  <-----------------+
coldblock:
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷

代码区别于程序数据的一点在于，在运行时它是不能被修改的，CPU只从内存中读取指令，并不修改它。

编写高速缓存友好的代码

明白了高速缓存的工作原理之后，我们可以更准确的描述局部性了，局部性较好的程序通常意味着较高的命中率，不命中率较低的程序往往运行的会更快。所以编写局部性好的程序实际上是编写对高速缓存友好的程序。

下面就是我们用来确保代码高速缓存友好的基本方法：

• 让常见的情况运行得快，程序通常把大部分时间花在少量的核心函数上，而这些函数通常把大部分时间花在了少量的循环上，所以要把注意力击中在核心函数的循环上，忽略其他部分。
• 尽量减少每个循环内部的缓存不命中数量，在其他条件相同的情况下（加载存储操作次数），不命中率低的程序通常循环运行的更快。

同时还有几个重要问题：

• 对局部变量的反复引用是好的，因为编译器能够将它们缓存在寄存器中（时间局部性）
• 步长为1的顺序引用是好的，因为存储器层次结构中所有层次上的缓存都是讲数据存储为连续的块（空间局部性）

我们这里以n*n矩阵相乘为例：

让 C = A x B，我们通常会写出以下代码：

1
2
3
4
5
6
7

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
            C[i][j] = A[i][k]*B[k][j];
        }
    }
}

根据i,j,k不同的循环顺序，实际上我们可以写出六个版本的矩阵乘法，但是它们是否互相等价呢？

我们可以分析，对于循环的过程中，我们总是希望步长是尽可能小的。所以我们优先考虑B矩阵的数据，对于B[k][j]的迭代，我们希望是kj顺序的，此时是顺序执行，空间局部性良好。对于左边的A[i][k]，我们应该优先考虑对k的迭代，以保证步长尽可能的小，所以使用ik顺序迭代。综上所述，ikj循环才是性能最好的，其他的就不过多赘述。反向分析即可。

在对程序空间局部性的分析过程中，我们要考虑到缓存时是行缓存存储的，所以应该尽可能的让要使用的数据在空间上是连续接近的。同时将目光聚焦于内循环（程序中迭代次数最多的代码块）中，以获得最好的局部性。对于新引入的数据对象，我们也应该多使用它，利用好时间局部性。

螺旋矩阵题型总结。我刷了几道螺旋矩阵相关的题目，这里我们介绍一下一些常见的解法。

螺旋矩阵

方形矩阵

当我们遇到n*n的方形矩阵时，可以用一种特殊的解法来遍历实现，以下面这道题为例：

59. 螺旋矩阵 II

我们可以定义几个变量用来控制遍历的行为：

• startX：每次循环的起点的行数
• startY：每次循环的起点的列数
• offset：每循环一圈，用偏移量表现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,0));
        int offset = 1 , startX = 0 , startY = 0;
        int val = 1;
        int i,j;
        for(int k=0;k<n/2;k++){		//循环次数就是圈数
            for(j=startY;j<n-offset;j++)	//左上->右上（从此以下都是左闭右开）
                ans[startX][j] = val++;
            for(i=startX;i<n-offset;i++)	//右上->右下
                ans[i][j] = val++;
            for(;j>startY;j--)				//右下->左下	
                ans[i][j] = val++;
            for(;i>startX;i--)				//左下->右上
                ans[i][j] = val++;
            startX++;
            startY++;
            offset++;	//实际上更新offset就是在更新每次循环的边界（缩小）
        }
        if (n&1){	//如果矩阵的边长为奇数，最中间的值会没法遍历到
            ans[offset-1][offset-1] = val;
        }
        return ans;
    }
};

同时还可以将方形矩阵视作一种特殊的矩形矩阵，以下对矩形矩阵的所有解法对方形都适用。

矩形矩阵

有时候我们会发现矩阵是矩形的，或者只有一层，这个时候就需要用几个通用的方法，来实现。例题：

LCR 146. 螺旋遍历二维数组

54. 螺旋矩阵

2326. 螺旋矩阵 IV

模拟路径法

我们先分析我们的转向条件：（1）当前进的方向上碰到了边界（2）当前进的方向上是已经走过的路径

第一个条件比较好解决，第二条件我们需要维护一个和数组相同大小的矩阵，走过的路线我们设置为true，没走过的设置为false.

由于我们的转向动作是有序的，是顺时针，所以我们可以使用一个数组来存储我们的方向。当到达转向条件时，设置成下一个转向动作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

vector<int> spiralArray(vector<vector<int>>& array) {
        if(array.empty()||array[0].empty())	//判断数组是否为空，注意先后顺序，array[0]在array为空时是不能访问的
            return {};
        int row = array.size();
        int col = array[0].size();
        int total = row*col;
        vector<vector<bool>> use(row,vector<bool>(col,0));	//路径表
        vector<int> ans(total,0);
        vector<vector<int>> direction{{0,1},{1,0},{0,-1},{-1,0}};	//方向表（顺时针）
        int directionIdx = 0;	//方向表索引
        int i=0,j=0;
        for(int k=0;k<total;k++){
            ans[k] = array[i][j];
            use[i][j] = true;
            int ni = i + direction[directionIdx][0];	//预更新i
            int nj = j + direction[directionIdx][1];	//预更新j
            if(ni<0||ni>=row||nj<0||nj>=col||use[ni][nj]==true){	//根据预更新状态判断转向条件
                directionIdx = (directionIdx+1)%4;	//转向则把方向索引设置到下一位
            }
            //实际更新
            i = i + direction[directionIdx][0];
            j = j + direction[directionIdx][1];
        }
        return ans;
    }

层级遍历法（边界收缩）

这个和刚刚用来解决方形矩阵的方法是相同的，只不过更新方式和更新条件要更加复杂。

一开始先设定好边界，当移动到边界的时候就转向，然后收缩边界。这样的好处在于我们不用再特意维护一个数组来判断路径是否被走过 了。因为走过的路径被我们收缩了，所以就不用在考虑。只需要在边界做检测就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m,vector<int>(n,-1));
        int top = 0;	
        int bottom = m-1;	//-1是因为索引和实际位置的差值
        int left = 0;
        int right = n-1;
        while(left<=right&&top<=bottom){	//如果相等就说明，边界收缩了，遍历结束了
            for(int i=left;i<=right;i++)	
                ans[top][i] = val;
            top++;							//左上->右上 top边界收缩
            for(int i=top;i<=bottom;i++)
                ans[i][right] = val;
            right--;						//右上->右下 right边界收缩
            for(int i=right;i>=left;i--)
                ans[bottom][i] = val;
            bottom--;						//右下->左下 bottom边界收缩
            for(int i=bottom;i>=top;i--)
                ans[i][left] = val;
            left++;							//左下->右上 left边界收缩
        }
        return ans;
    }

螺旋生成矩阵

这个算是一个小特例，大多数题目是给你一个矩阵让你去螺旋遍历，但是有的题目需要你自己螺旋生成一个矩阵。我们看到下面的例题：

885. 螺旋矩阵 III

这道题需要我们形成一个螺旋的路径，然后返回矩形内的位置的坐标。难点在于这个螺旋路径的生成，因为转向的条件和每次前进的步长综合考虑起来条件会非常的复杂。下面的话给出两种方法。

边界扩展法

和我们之前所做的边界收缩相反，我们先界定好边界，然后每次转向时宽展这个方向上的边界。通过这种方式来动态的生成一个螺旋的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

const int DIR[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> ans;
        int total = rows*cols;
        int num = 1;
        int i = rStart,j = cStart;	//令i,j记录路径的实时位置
        int left = cStart - 1,right = cStart + 1,top = rStart - 1,bottom = rStart + 1;	//确定边界
        int dir=0;	//记录方向
        while(num <= total){
            if(i>=0&&i<rows&&j>=0&&j<cols){	//当路径到达矩阵内部时，记录当前位置
                ans.push_back({i,j});
                num++;
            }
            if(dir==0&&j==right){	//如果向右移动触碰右边界
                dir+=1;				//则转向
                right++;			//并拓展右边界
            }else if(dir==1&&i==bottom){	//如果向下移动触碰下边界
                dir+=1;						//则转向
                bottom++;					//并拓展下边界
            }else if(dir==2&&j==left){		//...
                dir+=1;
                left--;
            }else if(dir==3&&i==top){		//...
                dir=0;
                top--;
            }
            i += DIR[dir][0];		//根据方向来更新位置
            j += DIR[dir][1];
        }
        return ans;
    }

规律法

我们可以观察螺线路径的一个显著规律：每转向两次会更新一次前进的步长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

const int DIR[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
    	int num=0;
    	int dir=0;
    	int run=2;	//步长计数器
        vector<vector<int>> ans;

        while(num < R * C){
            for(int i = 0; i < run / 2; i ++){   //遍历步长，每转两下就会增加一步
                if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
                    ans.push_back({r0, c0}), ++ num;
                r0 += DIR[dir][0];
                c0 += DIR[dir][1];
            }
            pos = (pos + 1) % 4;	//每遍历一次步长，就转向
            run++;		//利用取整的性质，每转向两次才会增加一次步长
        }
        return ans;
    }

总结

螺旋矩阵的关键在于边界的检测和变换，还有转向条件的判断。比较简单。

我们已经尽可能的实现各种程度的优化了，但所谓知己知彼，百战不殆。我们不仅要了解程序的性能怎么去优化，同时也要了解制约程序进一步优化的因素是什么。

限制因素

关键路径指明了执行程序所需时间的基本下界。如果程序中有某条数据相关链，这条链上的所有的延迟之和等于T，那么程序至少需要T个周期才能执行完。我们还看到功能单元的吞吐量界限也是程序执行的一个下界。也就是说，假设一个程序一共需要N个某种运算的计算，而微处理器只有C个能执行这个操纵的功能单元，并且这些单元的发射时间为I，那么这个程序的执行至少需要N*I/C个周期。

不过以上是理想状态，实际过程中，我们仍然需要考虑其他的制约因素。

寄存器溢出

循环并行性的好处受汇编代码描述计算的能力限制（如果代码描述不出来，说明寄存器不够用了）。如果并行度p超过了可用的寄存器数量，那么编译器就会溢出。将某些临时值放到内存中，在堆栈上分配空间。比如下面的例子：

为啥20*20的循环展开反而不如10*10呢？现代x86-64处理器可以使用16个YMM寄存器来保存浮点数。一旦数量超过了可用的寄存器的数量，程序就必须在栈上分配变量。内存写入读取的过程会造成不必要的开销。不过大多数循环会在出现寄存器溢出之前就会达到吞吐量的极限。

分支预测和预测错误处罚

指令在进行分支预测时，往往会使用投机执行的机制，但是预测错误意味着很大的代价。虽然代价是无法避免的，但是我们是否可以减少这个代价呢？在x86-64的程序处理中有条件传送的指令。我们可以在进行分支跳转的时候，通过将条件转移编译成条件传送来，减少这个代价。我们直接结算出两个方向上的可能的值，然后根据条件传送选择期望的值。这样，我们就不用考虑条件是否满足了，因为没有代价。

抛开编译器的优化，我们又该如何编写能够减少分支预测处罚的代码呢?

不要过分关心可以预测的分支

错误的分支预测影响可能很大，但是并不意味着所有的程序分支都会减缓程序的运行。现代处理器的分支预测逻辑十分先进，对于循环语句的分支，往往会被预测为选择分支，这样只有最后一次才会导致预测错误。

所以在程序性能优化（1）中的这个现象可以解释：

我们为了减少get_vec_element中的边界检测的延迟，改进成了combine3，发现程序性能几乎没什么改变，这是因为对于i的边界检测，是高度可预测的，对于计算机而言影响微乎其微。这些检测并不会影响程序的关键路径，或是起不到决定性作用。

书写适合用条件传送实现的代码

分支预测对于循环这种有规律的模式还行，但是程序中的大多数测试时完全不可预测的，依赖于数据的任意性，分支预测逻辑会表现得很糟糕。我们无法保证编译器会在编译中使用条件数据传送而不是条件控制转移，但是我们可以引导编译器进行我们想要的编译。

以一个程序为例，给定两个整数数组a和b，对于每个位置i，我们想要将a[i]设置为a[i]和b[i]中较小的那个，将b[i]设置成较大的那个。

首先是我们常用的风格：

1
2
3
4
5
6
7
8
9
10

void minmax1(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        if(a[i]>b[i]){
            long t = a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
}

在这里可以看到，我们是在分支预测之后才执行交换的过程。这会扩大分支预测的代价。可是我们尝试另一种写法：

1
2
3
4
5
6
7
8
9

void minmax2(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        long min = a[i] < b[i] ? a[i] : b[i];
        long max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

这里的话相当于去除了条件分支，先把每个位置的最大值和最小值计算出来，然后分别赋值给a[i]和b[i]。通过合理的安排代码，我们也可以更好的帮助编译器优化代码。

理解内存性能

内存性能实际上也是很重要的决定性因素，在之前的测试中，实际上访问的内存都十分少量。所有的现代处理器都包含一个或多个高速缓存存储器，以对少量的存储器提供快速的访问。接下来我们要进一步讨论加载和存储操作的程序的性能印象。不过我们默认所有的数据都是存放在高速缓存中的情况。

加载的性能

一个包含加载操作的程序性能既依赖于流水线的能力，也依赖于加载单元的延迟。在之前的合并函数中，无论什么数据类型和合并操作都无法让CPE下降到0.5以下。这是因为，每一个被计算的元素，所有的示例都需要熊内存中独一个值，对于两个加载单元而言，其每个时钟周期都只能启动一条加载操作，所以CPE不可能小于0.5

到目前为止我们并没有在示例中看到加载操作的延迟产生的影响。加载操作的地址只依赖于循环索引i，所以加载操作不会称为限制性能的关键路径的一部分。

但是我们可以手动构造一个由一系列加载操作构成的计算，一个加载操作的结果决定下一条操作的地址：

1
2
3
4
5
6
7
8
9
10
11
12
13

typedef struct ELE{
    struct ELE* next;
    long data;
}list_ele,*list_ptr;

long list_len(list_ptr ls){
 	long len = 0;
    while (ls){
        len ++;
        ls = ls->next;
    }
    return;
}

在这里变量ls的每个后续只依赖于指针引用ls->next读出的值。我们可以关键部分的汇编代码：

1
2
3
4
5

.L3:
	addq $1,%rax
	movq (%rdi),%rdi	;ls = ls->next
	testq %rdi,%rdi
	jne .L3

我们可以可以看到movq是整个循环中关键的瓶颈，且每次循环都会依赖加载出来的%rdi的值，此时的程序的CPE是由加载操作的延迟决定的。我们之后在存储器部分会详细讨论。

存储的性能

和其他的操作不一样，存储操作不会影响任何寄存器的值。一系列的存储操作并不会产生数据相关。只有加载操作会受存储操作结果的影响，因为只有加载操作才能从由存储操作写的那个位置读回值。

我们可以做一个实验来体现这种影响：

1
2
3
4
5
6
7
8
9

void write_read(long* src,long* dst,long n){
    long cnt = n;
    long val = 0;
    while (cnt){
        *dst = val;
        val = (*src)+1;
        cnt--;
    }
}

然后我们分别使用两种不同的调用方式：

最终的结果是示例A的CPE=1.3远快于示例B的CPE = 7.3。这背后的原因就是因为在调用write_read时，参数src和dst指向了同一个内存位置，导致产生了写/读相关——一个内存读的结果依赖于一个最近的内存写。

为了理解这背后具体的原理，我们需要更加仔细的看看加载和存储执行单元：

存储单元实际上会包含一个存储缓冲区，它包含已经被发射到存储单元而又还没完成的存储操作（这里的完成包括更新数据高速缓存）的地址和数据。提供这么一个缓冲区，使得一系列存储操作不必等待每个操作都更新高速缓存就能执行。当一个加载操作发生时，它必须检查存储缓存区中的条目，看看有没有地址匹配。如果有就取出相应的数据条目作为加载操作的结果。

其机器代码形式如下：

1
2
3
4
5
6
7

; src in %rdi , dst in %rsi , val in %rax
.L3:				; loop:
	movq %rax,(%rsi)	;write val to dst
	movq (%rdi),%rax	;t = *src
	addq $1,%rax		; val = t+1
	subq $1,%rdx		;cnt--
	jne .L3				;if != 0,goto loop

这里的movq (%rdi),%rax在实际的过程中被翻译成了两个操作：

• s_addr指令计算存储操作的地址，在存储缓冲区创建一个条目，并设置该条目的地址字段
• s_data操作设置该条目的数据字段。

这两个计算时独立执行的，不过它们之间有隐含的相关，实际上s_addr的操作必须在s_data之前。同时由于load操作需要检查所有未完成的存储操作的地址，所以s_addr到load之间也会存在数据相关。还有一个有条件的数据相关，存在于s_data和load之间（当%rsi和%rdi相等，即读写的地址相同），此时load操作必须等待直到s_data将它的结果存放到存储缓冲区中。反之，则继续进行。

我们依旧可以图形化抽象write_read的操作，来分析它的关键路径：

右边是最简情况，只保留了使用一次迭代中的值为下一次迭代产生的值的操作。

现在我们可以理解函数write_read的性能特征了，下面是内循环多次迭代形成的数据相关：

在示例A的情况下，有不同的源和目的地址，加载和存储操作都可以独立进行，因此唯一的关键路径是减少变量造成的，因此这个程序的CPE为1.0。对于示例B的情况下，源地址和目的地址相同，导致s_data和load指令之间的数据相关使得关键路径形成。其中包括了存储，加载，增加数据等操作，导致程序的CPE为7.0。

这个例子说明了，内存操作的细微之处。对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会影响那些指令了。但是对于内存操作，只有到计算出加载和存储的地址被计算出来后，处理器才能确定那些指令会影响哪些。

我们可以通过设置中间变量的方式来避免写/读相关。例如：

我们有a，p两个数组，令p[0] = a[0]，p[i] = p[i-1] + a[i]，我们正常写出来的程序会是这样：

1
2
3
4
5
6

void psum1(long a[],long p[],long n){
    long i;
    p[0] = a[0];
    for (i=1;i<n;i++)
        p[i] = p[i-1] + a[i];
}

但是这里的p[i]=p[i-1] + a[i]存在着读/写相关。我们可以引入一个中间的存储变量，来避免这种数据上的依赖：

1
2
3
4
5
6
7
8
9
10

void psum1(long a[],long p[],long n){
    long i;
    long last_val,val;
    last_val = p[0] = a[0];
    for (i=1;i<n;i++){
        val = last_val + a[i];
        p[i] = val;
        last_val = val;
    }
}

总结：性能提高技术

• 高效设计：为遇到问题选择适当的算法和数据结构，避免使用会渐进的产生糟糕性能的算法或编码技术。
• 基本编码原则：避免限制优化的因素，这样编译器就能产生高效的代码。
  • 消除连续的函数引用：必要时，将计算移到循环外面。
  • 消除不必要的内存引用：引入临时变量来保存中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中
• 低级优化：结构化代码以利用硬件功能。
  • 展开循环，降低开销，并且使得进一步的优化称为可能
  • 通过使用例如多个累计变量和重新结合等技术，提高指令的并行性
  • 用功能性的风格重写条件操作，使得编译采用条件数据传送