系统调用错误处理

由于之后会用到大量的系统调用函数，我们需要做好错误处理，以便于查找问题。Uinx系统中的系统级函数遇到错误时会返回-1，并设置全局整数变量errno来表示错误类型。这个时候我们可以通过strerror()函数来返回和errno值相关联的错误。我们以处理fork()的错误为例：

1
2
3
4

if((pid = fork()) < 0){
    fprintf(stderr,"fork error: %s\n",strerror(errno));
    exit(0);
}

我们可以进一步的封装这个错误：

1
2
3
4
5
6
7
8

void unix_error(char *msg){
    fprintf(stderr,"%s: %s\n",msg,strerror(errno));
    exit(0)
}

if((pid = fork()) < 0){
    unix_error("fork error");
}

通过错误处理包装函数，我们可以进一步的优化代码。对于错误处理包装函数，有一个约定成俗的规矩，对于基本函数foo，我们定义一个具有相同参数的包装函数Foo。包装函数调用基本函数，检查错误，如果有问题就终止。比如下面对fork的包装：

1
2
3
4
5
6

pid_t Fork(){
    pid_t pid;
    if((pid = fork()) < 0)
        unix_error("fork error");
    return pid;
}

我们之后的包装函数也会按照相同的处理模式，来进行编写。

进程调用

Unix提供了大量从C程序中操作进程的系统调用，我们来详细了解他们：

获取进程ID

每个进程都有一个唯一的正数非零进程PID

1
2
3
4
5

#include <sys/types.h>
#include <unistd.h>

pid_t getpid();		//返回调用进程的PID
pid_t getppid();	//返回调用进程的父进程的PID

这两个函数返回的类型为pid_t，在Linux中它们被types.h定义为int

创建和终止进程

我们可以认为进程总是处于下面三种状态：

• 运行 进程要么在CPU上执行，要么在等待被执行且最终会被调度
• 停止 进程的执行被挂起，且不会被调度。当收到SIGSTOP SIGTSTP SIGTTIN SIGTTOU信号时，进程就保持停止，直到它收到一个SIGCONT信号，这个时候，进程在次开始运行
• 终止 进程永远地停止了。三种原因:1)收到终止进程信号，2)从主程序返回，3)调用exit()函数

下面我们了解进程的创建和终止过程：

1
2

#include <stdlib.h>
void exit(int status);	//exit函数以status退出状态来终止进程

1
2
3

#include <sys/types.h>
#include <unistd.h>
pid_t fork();	//子进程返回0,父进程返回子进程的PID,如果出错返回-1

新创建的子进程会得到父进程用户级虚拟地址空间相同的一份副本，包括代码、数据、用户栈、堆、共享库。子进程也会得到与父进程任何打开文件描述符相同的副本，这意味着当父进程调用fork时，子进程可以读取父进程中打开的所有文件。父子进程最大的区别就在于他们的PID不同

fork函数被调用一次，却会返回两次，这是因为调用之后创建了一个新的进程。然而，在两个进程中的返回值会有所不同，因此我们根据fork()的返回值来判断父子进程

我们可以用下面这个程序来展示一个进程的创建：

1
2
3
4
5
6
7
8
9
10
11

int main(){
	pid_t pid;
	int x = 1;
	pid = Fork();
	if(pid == 0){	//子进程
		printf("child: x = %d\n",x+1);
		exit(0);
	}
	printf("parent: x = %d\n",x-1);	//父进程
	exit(0);
}

我们可以看到执行的结果：

1
2
3

ylin@Ylin:~/Program/test$ ./a.out
parent: x = 0
child: x = 2

实际的运行过程我们可以简化成流程图：

对于整个过程我们可以从中注意到一些关键点：

• 调用一次，返回两次 fork函数被父进程调用一次，但是却返回两次——一次返回到父进程，一次返回到子进程。对于多个fork函数的情况我们之后会涉及
• 并发执行 父子进程都是并发运行的独立进程。内核可能以任意方式交替执行它们的逻辑控制流的指令。因此我们不能对不同进程中指令的交替执行做出假设。不存在执行的先后关系
• 相同但是独立的空间 通过观察局部变量x，我们可以看出，父子进程对x所作的改变都是独立的。说明它们之间的空间是独立的。根据数值可以判断，x的值是相同的。因此我们说父子进程的空间相同且独立。
• 共享文件 printf将输出输入到stdout文件中，结果表明在子进程中的stdout也是打开的。子进程继承了这个文件，所以说父子进程中的文件描述符也是相同的

理解了这些我们就可以理解更复杂的情况，我们可以通过流程图来更好的分析复杂的嵌套情况：

1
2
3
4
5
6

int main(){
    Fork();
    Fork();
    printf("hello");
    exit(0);
}

回收子进程

当一个进程被终止时，内核不会立即将其清除。而是进程会处于一个终止的状态下，直到它的父进程将其回收。当父进程将终止的子进程回收时，内核将子进程的推出状态传递给了父进程，然后抛弃终止的进程。直到现在，这个进程才不存在了。对于处于终止状态，但没有被回收的进程，我们称之为僵死进程。

如果一个父进程终止了，内核会安排init进程作为它们的孤儿进程的养父。init进程的PID为1，是在系统启动时就由内核创建的，它不会终止，是所有内核的祖先，如果父进程没有回收它的僵死子进程就终止了。内核会安排init进程去回收它们。因为即使僵死子进程没有运行，也会消耗系统的内存资源

进程可以通过调用waitpid函数来等待它的子进程终止或停止。

1
2
3
4

#include <sys/types.h>
#include <sys/wait.h>
pid_t waitpid(pid_t pid, int* statusp, int options);
// 如果成功终止就返回子进程的PID;如果WNOHANG,则为0;其他错误,则为-1

waitpid函数比较复杂，我们需要仔细讨论一下。

默认情况下(options=0),waitpid挂起调用进程的执行，直到它的等待集合中的一个子进程终止。如果等待集合中的一个进程在刚调用的时候就已经终止了，那么waitpid就立即返回。在这两种情况中，waitpid会返回导致waitpid返回的已终止进程的PID。此时，已终止的子进程会被回收，内核会清理它的痕迹。

这个过程非常的抽象，我们需要深入去理解waitpid:

判定等待集合的成员

等待集合的成员由参数pid确定：

• 如果pid>0，那么等待集合就是一个单独的子进程，它的进程ID等于pid
• 如果pid=-1，那么等待集合就是由父进程所有的子进程组成的

修改默认行为

可以通过修改options为各个常量从而实现修改默认行为：

• WNOHANG

  如果等待集合中的任何子进程都没有终止，那么就立即返回。而默认的行为是挂起调用进程，直到有子进程终止。默认行为是等待的，会阻塞之后的操作。如果想要在等待子进程终止的同时，想要进行别的工作，我们就可以启用这个选项

• WUNTRACED

  挂起调用进程的执行，直到等待集合中的一个进程变成已终止或者被停止。返回的PID为导致返回的已终止或者被停止的子进程的PID。默认是返回导致返回的已终止的子进程。如果想要检查已终止和被停止的子进程时，可以启用这个选项。

• WCONTINUED

  挂起调用进程的执行，直到等待集合中一个正在运行的进程变成已终止或等待集合中一个被停止的进程收到SIGCONT信号重新开始执行

这些常量可以通过”|“来连接，从而更改行为

检查已回收子进程的退出状态

status是statusp指向的值，如果这个值不为NULL。waitpid就会在status中放上关于导致返回的子进程的状态信息。我们可以通过<wait.h>中定义的宏来解释status参数：

• WIFEXITED() 如果子进程通过exit或return正常终止则返回真
• WEXITSTATUS() 返回一个正常终止的子进程的退出状态。只有WIFEXITED()返回为真时，才有这个状态
• WIFSIGNALED() 如果子进程是因为一个未被捕获的信号终止的，那么返回真
• WTERMSIG() 返回导致子进程终止的信号的编号。只有WIFSIGNALED()返回为真时，才有这个状态
• WIFSTOPPED() 如果子进程是停止的，就返回真
• WSTOPSIG() 返回引起子进程停止的信号的编号。只有WITSTOPPED()返回为真时，才有这个状态
• WIFCONTINUED() 如果子进程收到SIGCONT信号重新启动，则返回真

错误条件

如果调用进程没有子进程，则返回-1，设置errno=ECHILD

如果waitpid被信号中断，返回-1，设置errno=EINTR

wait函数

wait()是waitpid()的简化版

1
2
3
4
5

#include <sys/types.h>
#include <sys/wait.h>

pid_t wait(int* statusp);
//如果成功，返回子进程PID;否则返回-1

wait(&status)等价于waitpid(-1,&status,0)

让进程休眠

sleep函数可以将一个进程挂起指定的时间

1
2

#include <unistd.h>
unsigned int sleep(unsigned int secs);	//返回还要休眠的秒数

如果请求的时间到了，就返回0；否则返回还要休眠的秒数，这种情况是因为sleep可能会被信号中断而过早返回。

另一个函数是puase，该函数让进程休眠，直到收到信号。

1
2

#include <unistd.h>
int pause();	//总是返回-1

加载并运行程序

execve函数用于在当前进程的上下文中加载并运行一个新的程序。

1
2
3
4
5

#include <unistd.h>
int execve(const char* filename,
           const char* argv[],
           const char* envp[]);
//如果成功，则不返回；否则返回-1

execve函数加载并运行可执行目标文件filename，且待参数列表argv和环境变量列表envp。只有出现错误时，execve才会返回到调用程序。正常情况下调用一次不返回。

在execve加载了filename之哦胡。它会调用启动代码__libc_start_main。启动代码设置栈，并将控制传递给新程序的主函数：

1

int main(int argc,char* argv[],char*envp[]);

当main开始执行时，用户栈的组织结构如下：

我们从高地址往下看，先是存放了参数和环境的字符串。然后是以NULL结尾的指针数组，其中每个指针都指向栈中的一个字符串。其中全局变量environ指向这些指针中的第一个envp[0]。在栈的顶部是系统启动函数__libc_start_main的栈帧。

main的三个参数：

• argc 给出argv[]数组中非空指针的数量
• argv 指向argv[]数组中的第一个条目
• envp 指向envp[]数组中的第一个条目

同时LInux还提供了几个函数用来操作环境数组：

1
2
3
4

#include <stdlib.h>
char* getenv(const char* name);	//若存在则返回指向name的指针；否则返回NULL
int setenv(const char* name,const char* newvalue,int overwrite); //成功则返回0；否则返回-1
void unsetenv(const char* name); //不返回

• getenv函数在环境数组中搜索字符串“name=value”。如果找到了，就返回指向value的指针。
• unsetenv函数查找字符串”name=value”，并删除
• setenv函数找到环境变量”name=value”后，会用新的value替换；否则则创建一个”name=new_value”的环境变量。overwrite用来控制是否覆盖已存在的同名环境变量，0则不覆盖。

使用fork和execve

我们写一个shell。shell打印一个命令行提示符，我们在stdin上输入命令行，然后对这个命令执行。于是我们可以搭建出一个简单的框架:

1
2
3
4
5
6
7
8
9
10
11

#include "shell.h"
int main(){
        char cmdline[MAXLINE];
        while(1){
                printf(">>>");
                Fgets(cmdline,MAXLINE,stdin);
                if(feof(stdin))
                        exit(0);
                eval(cmdline);
        }
}

我们首先需要解析命令行参数，我们以空格作为分隔符，同时返回一个参数列表argv。如果命令的参数以&结尾，我们就把这个程序放在后台运行。

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

int parseline(char* buf,char** argv){
        char* delim;    // 指向分隔符的指针
        int argc;               // 参数数量
        int bg;                 // 是否为后台程序

        buf[strlen(buf)-1]=' '; // \0替换为空格
        while(*buf && (*buf==' ')) // 忽略多余的空格
                buf++;

        //解析参数
        argc=0;
        while((delim = strchr(buf,' '))){
                argv[argc++] = buf;
                *delim = '\0';
                buf = delim+1;
                while(*buf && (*buf==' '))
                        buf++;
        }
        argv[argc] = NULL;

        if(argc==0)
                return 1;

        //是否应该在后台运行
        if((bg = (*argv[argc-1] == '&')) != 0)
                argv[argc-1] = NULL;

        return bg;
}

解析好命令参数后，我们也需要判断第一个参数是否为程序名，或者是shell的内置函数。如果是内置函数我们就执行该函数，并返回1；如果不是就返回0。

1
2
3
4
5
6
7
8
9
10
11

int builtin_command(char **argv){
        if(!strcmp(argv[0],"quit"))
                exit(0);
        if(!strcmp(argv[0],"cd")){
                if(argv[1]==NULL)
                        chdir("~");
                chdir(argv[1]);
                return 1;
        }
        return 0;
}

最后我们就可以写出我们的执行函数了，如果builtin_comand返回0，我们就需要创建一个新的子进程并加载程序运行。然后根据是否后台运行的需求，使用waitpid进行对前台程序的等待。当作业结束后，再进行一次迭代。我们的Shell就粗略的完成了。但是现在有一个问题，我们的shell不能回收已经结束的子进程，我们会在之后加以改进。程序的完整代码如下：

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
123
124
125
126
127
128
129

// csapp.h	
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/wait.h>

void unix_error(const char *msg){
    fprintf(stderr,"%s: %s\n",msg,strerror(errno));
    exit(0);
}

pid_t Fork(){
    pid_t pid;
    if((pid = fork()) < 0)
        unix_error("fork error");
    return pid;
}

char* Fgets(char* str,int n,FILE* stream){
        char* p = fgets(str,n,stream);
        if(p == NULL)
                unix_error("fgets error");
        return p;
}


// shell.h
#include "csapp.h"

#define MAXARGS 32
#define MAXLINE 256

//执行命令行任务
void eval(char* cmdline);
//解析参数
int parseline(char* buf, char** argv);
//判断Shell内联函数
int builtin_command(char** argv);


int parseline(char* buf,char** argv){
        char* delim;    // 指向分隔符的指针
        int argc;               // 参数数量
        int bg;                 // 是否为后台程序

        buf[strlen(buf)-1]=' '; // \0替换为空格
        while(*buf && (*buf==' ')) // 忽略多余的空格
                buf++;

        //解析参数
        argc=0;
        while((delim = strchr(buf,' '))){
                argv[argc++] = buf;
                *delim = '\0';
                buf = delim+1;
                while(*buf && (*buf==' '))
                        buf++;
        }
        argv[argc] = NULL;

        if(argc==0)
                return 1;

        //是否应该在后台运行
        if((bg = (*argv[argc-1] == '&')) != 0)
                argv[argc-1] = NULL;

        return bg;
}


int builtin_command(char **argv){
        if(!strcmp(argv[0],"quit"))
                exit(0);
        if(!strcmp(argv[0],"cd")){
                if(argv[1]==NULL)
                        chdir("~");
                chdir(argv[1]);
                return 1;
        }
        return 0;
}

void eval(char* cmdline){
        char* argv[MAXARGS];    //参数列表
        char buf[MAXLINE];      //命令存储区
        int bg;                 //是否后台调用
        pid_t pid;

        strcpy(buf,cmdline);
        bg = parseline(buf,argv);
        if(argv[0]==NULL)
                return;

        if(!builtin_command(argv)){
                if((pid = Fork()) == 0){
                        // printf("%s",argv[0]);
                        if(execvp(argv[0],argv)<0){
                                printf("Command not found\n");
                                exit(0);
                        }
                }

                if(!bg){
                        int status;
                        if(waitpid(pid,&status,0) < 0)
                                unix_error("waitpid error");
                }
                else
                        printf("%d %s\n",pid,cmdline);
        }
        return;
}

// main.c
#include "shell.h"
int main(){
    char cmdline[MAXLINE];
    while(1){
        printf(">>>");
        Fgets(cmdline,MAXLINE,stdin);
        if(feof(stdin))
            exit(0);
        eval(cmdline);
    }
}

异常

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

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

总结

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