系统级编程（CSAPP）

Ch1 程序执行

原目录：系统级编程（CSAPP）

查看语雀原文

以Linux下hello.c为例

//hello.c
#include <stdio.h>
int main()
 {
	printf("hello, world\n");
}

编译系统

1. 预处理(preprocess)阶段:cpp把.h头文件直接插入程序文本,得到hello.i文件,并且移除注释(comments)
2. 编译(compile)阶段:ccl把hello.i翻译成hello.s,其中包含汇编程序
3. 汇编(assemble)阶段:as把hello.s翻译成机器指令打包成目标文件hello.o
4. 链接(link)阶段:ld把需要的外部函数所在.o文件合并进当前hello.o,得到可执行文件,能加载到内存

中间文件顺序:ciso

程序执行

在linux下完成编译后用户输入./hello可执行程序,实际上有下列三步

1. 接收用户输入: 从键盘接收输入后shell程序把字符读入寄存器,再放入主存,当敲下回车,shell判断输入完毕,执行指令加载可执行文件hello

2. 加载hello到主存: Shell指令把磁盘中的hello复制到主存,其中包含要输出的”hello,world\n”

3. 输入至显示器:当程序加载到主存后,CPU开始执行机器指令,将”hello,world\n”对应字节复制到寄存器,再从寄存器输出至显示器

选择题知识点

1. VC++Project中包含Files
2. VC++中win32 console程序是:VC++可生成的最简单程序
3. 计算的抽象级别排序: C++ code > C code > 机器码 > 逻辑门
4. 以下代码

unsigned int x; int y; 
cin >> x >> y; 
cout << x + y;

当x,y都是正数,打印结果不一定为正数,unsigned int和int运算无显式说明时进行无符号加法,得到无符号数

举例:
令x=1,y=-4,此时执行无符号加法,结果fffffffd全被当作数据位,得到4294967293

当x定义为int时

此时执行补码加法,结果fffffffd的补码00000003,符号位f,答案-3

5. IDE使得很难混合和匹配来自不同来源的工具:不好，因为没有一个供应商可能是所有最好工具源
6. C代码和机器码可以描述相同的算法
7. 关于debugger(调试程序)
   作用:①编译compiler生成的机器指令②中断程序的执行,但debugger本身不能发现error
   使用:可能需要重复执行多次代码才能定位错误behavior

Ch2 信息表示与处理

原目录：系统级编程（CSAPP）

查看语雀原文

化二进制

• 整数:除2取余(自下而上,直到商为0)
• 小数:乘2取整(自上到下,直到小数部分为0)

C位运算

• 反码ONES’ COMPLEMENT ( ~ ),
• 位移SHIFT ( << and >> )

• 左移时丢弃高位,低位补0
• 右移有符号数,算术右移,丢弃低位,高位补符号位
• 右移无符号数,逻辑右移,丢弃低位,高位补0

• 与AND ( & ),
• 或OR ( | ),
• 异或EXCLUSIVE OR ( ^ ):同假异真
• 注意!为逻辑非,C中对除0以为任何数使用!都得到0

​

CSAPP datalab⭐

参考链接: 实验二 datalab-handout

实现按位&,|,^操作

/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 */
int bitAnd(int x, int y) {
  // ~(~A∪~B)=A∩B
  return ~(~x|~y);
}
/*

bitOr - x|y using only ~ and &
Example: bitOr(6, 5) = 7
Legal ops: ~ &
*/
int bitOr(int x, int y) {
// ~(~A∩~B)=A∪B
return ~(~x&~y);

}
/*

bitXor - x^y using only ~ and &
Example: bitXor(4, 5) = 1
Legal ops: ~ &
*/
int bitXor(int x, int y) {
return (x & ~y) | (~x & y);
}

求-1

1表示为32bits二进制000...001,数据位补码111...111,加符号位后转换为16进制,0xffffffff

/* 
 * minusOne - return a value of -1 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 */
int minusOne(void) {
  return ~0;
}

求2s补码下最大整数

正常int的最大整数为0111.....1111,对齐取反1000...0000,那么通过0000...0001左移即可

/* 
 * TMax - return maximum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 */
int tmax(void) {
  return ~(1 << 31);
}

字节提取

/* 
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 */
int getByte(int x, int n) {
  return (x >> (n << 3)) & 0x000000ff;
}

求相反数

即求2s补码

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 */
int negate(int x) {
  return (~x)+1;
}

判断相等/等于0

/* 
 * isEqual - return 1 if x == y, and 0 otherwise 
 *   Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
 *   Legal ops: ! ~ & ^ | + << >>
 */
int isEqual(int x, int y) {
  return !(x^y);
}
/*

isZero - returns 1 if x == 0, and 0 otherwise
Examples: isZero(5) = 0, isZero(0) = 1
Legal ops: ! ~ & ^ | + << >>
*/
int isZero(int x) {
return ! (0^x);
}

判断为正数,判断非负数

• 为正数:符号位为0,且非0
• 非负数:符号位为0,或为0

/* 
 * isPositive - return 1 if x > 0, return 0 otherwise 
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 */
int isPositive(int x) {
    return !((x >> 31) | (!x));
}
/* * isNonNegative - return 1 if x >= 0, return 0 otherwise

Example: isNonNegative(-1) = 0. isNonNegative(0) = 1.
Legal ops: ! ~ & ^ | + << >>
*/
int isNonNegative(int x) {
return !(x >> 31);
}

浮点数

IEEE Standard 754浮点数格式

浮点数加法

浮点数加法需要经过"对阶",容易丢失精度:十进制下10.375 + 6.34375 = 16.71875

\(\\\frac{\begin{align} 1.0100110×2^3\\ +\quad0.1100110×2^3 \end{align}}{10.0001100×2^3}\Longrightarrow16.75\quad precision\ loss\)

选择题知识点

1. 在4byte为一个word的计算机中,下列哪一个表达式测试指针ptr是否包含某个word的地址

(ptr & 3) == 0
(ptr | 3) == 0
(ptr % 4) == 0

选Ⅰ和Ⅲ(指针不可以做%或&运算,需要强转)

• Ⅰ计算机4bytes为一个word,见指针,每个字节有一个地址,所以每个word的地址都以4对齐,下图为VS调试时内存窗口4字节显示结果,明显看到16进制表示时最后字节以0,4,8,c变化,对应0000 0000, 0000 0100, 0000 1000, 0000 1100

最后2bit始终为00与0011按位与的结果永远是0

• Ⅲ把最后字节化为int类型:0,4,8,12对4取余恒为0

2. 关于溢出

• C程序对整型加法中的溢出不会产生提醒,会得到错误结果;
• 对浮点数溢出,即阶码部分超过其能表示的最大值时报错#INF:infinity

3. 以下结果是false的是:0x00 ^ 0x00

#include <stdio.h>
#include <stdbool.h>
void main()
{
	bool a = !(0);
	bool b = ~(0xFF);
	bool c = ~(0x00);
	bool d = 0x00 ^ 0x00;
}

Ch3 指令

原目录：系统级编程（CSAPP）

查看语雀原文

要理解指令和汇编部分,必须先掌握C语言内存分配和X86寄存器与栈帧知识

C语言内存分配

参考链接: C语言的内存分配

1. stack-栈： 由编译器自动分配释放
2. heap-堆： 一般由程序员分配释放，若程序员不释放 - 程序结束时可能由OS回收
3. 全局区（静态区）:全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域 - 程序结束释放。
4. 另外还有一个专门放常量的地方 - 程序结束释放

X86寄存器和栈帧

Stack Frame

参考链接: X86-64寄存器和栈帧

寄存器

指令

参考链接: 16位汇编程序设计

指令格式

• 操作符:表示CPU支持的操作
• 操作数/操作数地址:访问操作数的模式

不同的指令长度\可携带操作数个数\操作数访问模式都可能不同

指令循环

每一条指令的执行都经过"取址-译码-执行"的指令循环

示例代码分析

#include <stdio.h>
int x;
void main()
{
	int y;
	int z = 0;
	unsigned char* cptr;  	
	x = 5;
}

VS下以x86-32调试(x64下采用%r开头的寄存器)反汇编结果与逐行分析

参考链接: 函数参数压栈，栈帧ebp,esp怎样移动的？

--- D:\ProjectSet\CProject\slp\slp.cpp -----------------------------------------
#include <stdio.h>
int x;
void main()
{
55                   push        ebp	          //保存当前栈帧 
8B EC                mov         ebp,esp        //改变栈帧，以后访问参数通过ebp([ebp±k])
																								,访问局部变量通过esp
81 EC E4 00 00 00    sub         esp,0E4h       //跳过0E4大小地址块用于当前栈帧保存局部变量
56                   push        esi  
57                   push        edi            //将ebx,esi,edi压入栈
8D BD 1C FF FF FF    lea         edi,[ebp+FFFFFF1Ch]  
                                                //加载有效地址,把[ebp+FFFFFF1Ch]
																						    读取到edi作为参数1,根据补码运算即为[ebp-0E4]
                                           	    即当前帧局部变量保存区域基址   
B9 39 00 00 00       mov         ecx,39h        //令ecx等于0x39,作为下面rep指令重复次数  
B8 CC CC CC CC       mov         eax,0CCCCCCCCh //令eax等于CCCCCCCC
F3 AB                rep stos    dword ptr es:[edi] 
																								//es为辅助段寄存器,es:[edi]即辅助段基址+偏移
    																						//循环使用eax中的值CCCCCCCC初始化es:[edi]指
																								向空间(该串表示未初始化),步长为一个双字指针大
																								小8字节(2*32b),恰好为CCCCCCCC长度,循环0x39
																								(57)次----总结:循环使用cc初始化辅助段
B9 03 C0 7A 00       mov         ecx,7AC003h    //将7AC003存入ecx

E8 E0 FA FF FF       call        007A1208       //调用地址007A1208处子程序,这里为debugger
相关的程序,无需深究
int y;
int z = 0;
C7 45 EC 00 00 00 00 mov         dword ptr [ebp-14h],0  //将0放入到双字指针ptr指向的位置,
即地址ebp-14的内存空间

unsigned char* cptr;  
x = 5;
C7 05 38 A1 7A 00 05 00 00 00 mov         dword ptr ds:[007AA138h],5

//x是全局变量,位于整个程序数据端,非栈内数据
区域,寄存器ds存放数据段基址,偏移量为007AA138,
把imm 5放入007AA138指向的内存空间
}

• ⭐movdword ptr ds:[007AA138h],5直接对应C7 0538 A1 7A 0005 00 00 00
• ⭐寄存器再认识:通过上述分析,可以看出来寄存器本身可存放一个32/64bits数,即一个地址,所以寄存器就是指针
• ⭐内存分配再认识:分析中可以看出

int z = 0对应movdword ptr [ebp-14h],0局部变量通过ebp±k访问,调试验证

x = 5对应movdword ptr ds:[007AA138h],5全局变量通过程序数据段基址+偏移访问

• mov和lea类似,但[]之于二者作用恰好相反: 参考链接: 汇编中mov,lea指令的区别

• rep stos: 参考链接 rep stos 指令(Intel汇编)

operand寻址模式

(Operand-addressing Mode)操作数寻址模式决定了指令循环中会被取到哪个数据项

选择题知识点

1. program counter程序计数器:存储下条指令地址

instruction register指令寄存器:存储下条指令

2. 为CPU设计少量fast memory(cache)的目的①使得指令更短②使得指令更快,与compiler无关
3. debugger停止的原因:不确定,可能由于断点,可能由于异常
4. 指令集:sparc:RISC,x86: CISC
5. 如何再断点调试时查看变量值①鼠标指针放在变量上②添加监视,不能使用printf
6. 当程序执行完一个非分支\跳转语句后,PC指向下条指令
7. CPU 寄存器:是1word大小的CPU memory,可显式地加载/卸载编译器生成的指令
8. 当一组连续的内存位置包含整数0xC605CD623A8365000000时,该区域可能有

①整数0xC605CD623A8365000000②字符串③一条指令

9. 分支语句:把PC设为两个可能值中一个

跳转语句:无条件地把PC设为其操作数

10. 机器码并没有保存源码所有信息
11. 经过compiler对优化后的机器码①更短,运行更快②更难以调试,但不能说更clearer
12. 汇编程序不可能同时使用AX和AL:如图,AL会影响AX

Ch4 结构化数据表示

原目录：系统级编程（CSAPP）

查看语雀原文

指针&指针变量

指针

计算机中所有的数据都必须放在内存中，不同类型的数据占用的字节数不一样，例如 int 占用 4 个字节，char 占用 1 个字节。为了正确地访问这些数据，必须为每个字节都编上号码，就像门牌号、身份证号一样，每个字节的编号是唯一的，根据编号可以准确地找到某个字节

我们将内存中字节的编号称为地址(Address) / 指针（Pointer）

地址从 0 开始依次增加,对于 32 位环境,程序能够使用的内存(可寻址空间)为 2³²Bytes=4GB，最小的地址为 0，最大的地址为 0XFFFFFFFF

指针变量

程序分析1--取地址和解引用

#include <stdio.h>
void main()
{
	int x = 0, y = 1;
	int* ptr = &y;
	*ptr = x;
	printf_s("x = %d, y = %d\n", x, y);
	// 结果x = 0, y = 0
}

反汇编中重要部分分析

  int* ptr = &y;
 lea         eax,[y]  						//lea eax,[y],把&y写入eax中
 mov         dword ptr [ptr],eax  //把eax值放在ptr指向空间,即写入&y
	*ptr = x;
 mov         eax,dword ptr [ptr]  //把ptr指向空间的数据写入eax,即写入&y
 mov         ecx,dword ptr [x]  	//把&x指向空间的数据写入ecx,即写入x
 mov         dword ptr [eax],ecx  //把ecx中数据写入对eax取址指向的地址空间,即y=[%y]=ecx=x

程序分析2--指针类型转换

#include <stdio.h>
void main()
{
	int x = 0x8041;
	char* ptr = (char*)&x;
	printf_s("%c", *ptr);
	// 结果A(A的ASCII编码65即41h)
}

char的大小为1byte但char*依旧为指针,大小4byte,用ptr保存&x

对ptr解引用,即改变&x指向空间的值,但经过强转后不再是对int*解引用而是对char*,所以结果只会看到&x指向空间的第一个字节,即8041中的41

程序分析3--指针运算

#include <stdio.h>
void main()
{
	int x = 0x8041;
	char* ptr = (char*)&x;
	int* intptr = &x;
}

调试

函数指针(变量)

#include <stdio.h>
int add(int a, int b) {
	return a + b;
}
void main()
{
int x = 0, y = 1;
int (*func)(int,int) = &add;
//或者int (*func)(int,int) = add;
printf_s("%d", func(x, y));
//或者printf_s("%d", (*func)(x, y));
}

数组

C中数组名和指向数组首元素指针是同义的,当ptr指向数组后:

• 元素地址:  ptr == a    ptr + k == &a[k]
• 元素值:  *(ptr+k) ==*(a+k) == a[k]  

#include <stdio.h>
void main()
{
	int a[5] = {0,1,2,3,4};
	int* ptr = a;
	printf_s("ptr = %p\n", ptr);
	printf_s("a = %p\n", a);
	printf_s("ptr + 2 = %p\n", ptr + 2);
	printf_s("&a[2] = %p\n", &a[2]);
	printf_s("*(ptr+2) = %d\n", *(ptr + 2));
	printf_s("*(a+2) = %d\n", *(a + 2));
	printf_s("*(ptr+2) = %d\n", *(ptr+2));
	printf_s("*(a+2) = %d\n", *(a+2));
	printf_s("a[2] = %d\n", a[2]);
}

结果:

二维数组

参考链接: C语言二维数组指针

示例代码

#include <stdio.h>
void main()
{
	//为了方便统一使用&p打印,使用16进制数
	int a[2][3] = {0x00,0x01,0x02,
				   0x10,0x11,0x12};
int(*ptr)[3]  = a;
printf_s(&quot;a = %p\n&quot;, a);
printf_s(&quot;*a = %p\n&quot;, *a);
printf_s(&quot;**a = %p\n\n&quot;, **a);

printf_s(&quot;a+1 = %p\n&quot;, a + 1);
printf_s(&quot;*(a+1) = %p\n&quot;, *(a + 1));
printf_s(&quot;**(a+1) = %p\n&quot;, **(a + 1));
printf_s(&quot;*(*a+1) = %p\n\n&quot;, *(*a + 1));

printf_s(&quot;a[1] = %p\n&quot;, a[1]);
printf_s(&quot;*a[1] = %p\n&quot;, *a[1]);
printf_s(&quot;a[1][1] = %p\n&quot;, a[1][1]);
printf_s(&quot;*(*(a+1)+1) = %p\n&quot;, *(*(a + 1) + 1));
printf_s(&quot;*(a[1] + 1) = %p\n&quot;, *(a[1] + 1));
}

结果:

• 观察内存,得到结论:二维数组在概念上是二维的,但在内存中所有元素都是连续排列的

• 数组名a是int[2][3]起始地址

• 一次解引用*a:依旧为地址,概念上第一个int[3]起始地址
• 二次解引用**a:取到第一个int[3]起始元素值,可监视验证

• ⭐二维数组a[2][3]获取元素值的方法

• ①两次解引用**
• ②int[j][k]
• ③*(a[j]+k)
• ④*((int*)a+4*j+k):如果没有int*强转,直接运算,变化以int[3]大小为单位

个人理解

• 数组b[3]={0,1,2},*b可得到0,但二维数组a[2][3]必须两次解引用,可以看作二维数组对一维数组额外做了一层封装从而*a=b,**a=*b,可通过监视验证,

• 结合👆指针运算,a+1使地址+sizeof(int[3])即12(0xA)字节,而*a+1使地址+sizeof(int)即4(0x04)字节

数组指针&指针数组

参考链接: C语言数组指针和指针数组

#include <stdio.h>
void main()
{
	int a[2][3] = { 0x00,0x01,0x02,0x10,0x11,0x12 };
	int(*aptr)[3] = a;
	int b[3] = { 0,1,2 };
	int* bptr = b;
}

如上,可以创建指向数组的指针对数组访问,对于二维数组同样适用,但极易和指针数组搞混

字符串

C中没有string这一基本类型,实际上是一个以"\0"结尾的char[],并且char[]每个元素声明后会初始化为'\0'(0x00)

结构体&联合体

Structure

参考链接: C 结构体

定义:C 数组允许定义可存储相同类型数据项的变量,结构是 C 编程中另一种用户自定义的可用的数据类型

声明:结构体声明有三种形式,其中使用typedef可以创建自定义的新类型,并通过该类型声明新的结构体变量,见👇

存储空间:结构的大小取决于其对齐的结果

Union

参考链接: C 共用体

定义:union是一种特殊的数据类型,允许在相同的内存位置存储不同的数据类型,但是任何时候只能有一个成员带有值

声明:见示例

存储空间:Union的大小只需满足最大成员即可

示例(vs默认8字节对齐,开头主动声明为4字节)

#include <stdio.h>
#pragma pack(4)
typedef struct
{
    int a[7];
    char b;
    double c;
} Stru;
union Data
{
int i;
float f;
char  str[20];
} data;
void main()
{
Stru s;
Data u;
printf_s("%d\n", sizeof(s));
printf_s("%d\n", sizeof(u));
}

结果为40,20,structure分析见👇,union的最大成员为char[20],故为20字节

结构成员对齐

参考链接: C语言内存对齐和结构补齐

为了优化CPU从内存中取数据的效率,compiler会对结构体对齐

对齐原则

1. 第一个成员的首地址为0
2. 每个成员的首地址是size的整数倍,当size大于基准时,按照基准对齐
3. 最后以结构总体对齐:结构体结束地址要是基准的整数倍

#pragma pack(4)  //以4字节对齐
typedef struct
{
    int a[7];
    char b;
    double c;
} Stru;

1. int[]: 从0开始,占据7*4=28bytes
2. b: sizeof(char)=1,任何位置都是1的倍数,则直接放入
3. sizeof(double)=8>4,按4字节对齐,当前地址29不是4的整数倍,则29+3=32,补3字节
4. 结束地址28+1+3+8=40,满足4的整数倍
5. 最终结构的size为40bytes

32位机以双字(dword)进行传输,一次读8bytes(2*32bits),经过对齐,40bytes内容需要CPU从内存中读取5次

选择题知识点

1. ⭐给定代码

#include <stdio.h>
void main()
{
    char a[100] = { "Hello World!" };
    a[99] = *((char*)(((int)&a[0]) + 4));
int b[100] = { 1,2,3,4,5,6,7 };
b[99] = *((int*)(((int)&amp;b[0]) + 4));
}

①a[99]的值等于?a[4]

(int)&a[0]获取&a[0],转化为数字,直接+4后地址前进4字节,即为&a[4],对其解引用,获取a[4]

②b[99]等于?b[1]

(int)&b[0]获取&b[0],转化为数字,直接+4后地址前进4字节,即为&b[1],解引用,获取b[1]

结论:地址化为int类型后+1表示地址前进1字节

2. 不是所有现代处理器都需要对齐
3. ⭐计算机中地址A,A+1,A+2,A+3保存int 256,令int* aptr=A在另一台设备上B,B+1,B+2,B+3保存int 256,令int* bptr = B,不同设备int都是4字节长度,则

4. VS中的内存窗口:以多种方式显示内存情况,但是不出现变量名称(见👆结构对齐配图)
5. 给定代码

int a[10];
int *ptr = a;

则语句①*(ary+3)=10②pary[4]=10③pary++④ary++中,错误的是ary++,数组名(起始地址)不可直接运算

6.给定代码,结果为10 5,sizeof计算分配空间的长度,strlen只计算字符串有效长度(无\0)

#include <stdio.h>
#include <string.h>
void main()
{
char s[10] = "hello";
printf("%d %d", sizeof(s), strlen(s));
}

7. 给定代码

#include <stdio.h>
#include <string.h>
void main()
{
char str1[] = "abc";
const char* str2 = "abc";
const char* str3 = "abc";
int i = (str2 == str3);
}

则调试结果如下

• 对比6,当没有指定char[]大小时,sizeof计算"字符+\0"空间
• 由于char在C中存放在专门的段中,对于相同字符串,不同指针实际指向一个地址

8. C语言在数组越界访问时不会报错       

Ch5 函数调用与返回

原目录：系统级编程（CSAPP）

查看语雀原文

参数

C语言函数调用中参数分为形参(formal parameter)和实参(actual parameter)

• 形参:定义函数时候使用的参数,用来接收调用该函数时传入的参数
• 实参:调用者调用时传递给函数的参数

传参

C中主要有三种传参方式值传递地址传递引用传递,其中引用传递再C++中引入

值传递

传递的为实参的拷贝,二者值相同,但在内存中地址不同

地址传递

传递的为实参地址的拷贝,一定要清楚:本质依旧是值传递,只不过实参是地址

引用传递

传递的为实参地址,与地址传递区分,引用传递的实参就是变量本身,非其地址,但在函数中的操作都针对原始实参

对比Java

C中值传递和地址传递可对应Java中的基本数据类型传参与对象引用传参,Java本身按值传参:

• 对于int,float等基本类型传递值即可
• 每个对象引用都是一个指针/地址,指向堆上同一个对象,传递引用即传递地址

示例代码

#include <stdio.h>
int first;
void callee(int value_first, int* addr_first, int& refe_first) {
    value_first = 2;
    *addr_first = 2;
    refe_first = 3;
}
void main() {
first = 1;
callee(first, &first, first);
}

分析

• value_first=first但是&value_first≠&first =>值传递
• addr_first=&first且&addr_first单独存在 =>地址传递,且说明该地址本身作为拷贝又存储在别的区域(int**)
• refe_first=first且&refe_first=&first => 引用传递

活动记录

示例代码

#include <stdio.h>
int first;
int callee(int value_first, int* addr_first) {
    value_first = 2;
    *addr_first = 2;
    return value_first;
}
void main() {
first = 1;
callee(first, &first);
}

函数call过程

当发生函数调用时,编译器和硬件(寄存器)会进行下列动作:

1. 将参数入栈
2. 返回地址入栈
3. 进入callee,旧的帧指针入栈保存(push ebp)
4. 让帧指针等于当前栈顶指针(mov ebp,esp),成为新帧指针
5. 帧指针偏移一定数值,预留用于保存局部变量的地址空间(sub ebp xxxxh)

部分反汇编结果

参考链接: 汇编语言OFFSET运算符

//-------------1. 函数调用部分----------
    callee(first, &first);
 push        offset first (020A17Ch)  		//全局变量first位于数据段偏移020A17Ch处,&first入栈
 mov         eax,dword ptr [first (020A17Ch)] //取&first处数据放入eax
 push        eax  												//eax入栈
 																					//对应步骤1,&first和first先后入栈
 call        callee (02013BBh)  					//call地址02013BBh处指令,当前地址入栈,
 																					对应步骤2,进入子函数
 add         esp,8
 }
//————-2. 子函数部分———-
void callee(int value_first, int* addr_first) {
push        ebp  												//对应步骤3,保存上一栈帧
mov         ebp,esp  										//对应步骤4,移动当前帧到栈顶,为子函数开辟新帧
sub         esp,0C0h  										//对应步骤5,预留局部变量地址空间
push        ebx

push        esi

push        edi  												//保存原来的寄存器值
lea         edi,[ebp-0C0h]

mov         ecx,30h

mov         eax,0CCCCCCCCh

rep stos    dword ptr es:[edi]  					//初始化辅助段,见Ch3汇编分析

函数ret过程

函数返回时

1. 如果有返回值,先保存返回值到eax
2. esp add,释放预留给局部变量的空间
3. 令帧指针ebp等于栈指针esp,从栈中弹出上一个帧指针
4. 从栈中弹出返回地址,使用eip保存
5. 回到caller,esp add,释放参数占据的空间

//------------3.从callee return----------
return value_first;
 mov         eax,dword ptr [value_first]  //步骤1,返回值保存在eax,mov中对数值操作数加[]还是数值
}
 pop         edi  												
 pop         esi  
 pop         ebx  												//弹出保存的寄存器,恢复之前的状态
 add         esp,0C0h  										//步骤2,esp加上之前的偏移,释放预留给局部变量的空间
 cmp         ebp,esp  										
 call        __RTC_CheckEsp (0241212h)    //debugger相关,可忽略
 mov         esp,ebp  										//步骤3,令帧指针等于栈指针
 pop         ebp  												//步骤3,弹出旧的帧指针给ebp
 ret   																		//步骤4,栈中弹出返回地址,EIP接收
//————4.回到caller———-
call        callee (02413C0h)

add         esp,8  											//步骤5,栈指针递增,释放被参数占用空间
}

选择题知识点

1. 活动记录什么时候产生:①程序开始执行(可理解为main()的栈帧)②调用子函数
2. 全局变量,静态变量,函数的地址在编译时被compiler确定,但函数内局部变量地址无法被compiler获得
3. 当执行函数callee()后,帧指针的值是①caller()帧的top②callee()帧的底部,可以对比活动记录图示
4. 递归函数,深入n次即产生n个活动记录,递归返回时最终要从栈中弹出n个活动记录,如下当调用factorial(4),最终弹出4个活动记录

int factorial(int n) {
    if (n == 1) return n; 
    return n * factorial(n - 1);
}

Ch6 内存布局和分配

原目录：系统级编程（CSAPP）

查看语雀原文

内存布局

静态分配

参考链接: C语言中内存分配

定义: compiler在处理程序源代码时分配内存空间,在程序执行之前进行,效率比较高

stack分配

下图代码中int n=1

• 变量a在编译阶段已分配在stack中[ebp-8]处空间,执行时将1放入即可

**stack有静态和动态分配两种方式;而heap只有动态分配

静态变量

• 局部静态变量: 作用域不变,生命周期延长
• 全局静态变量: 作用域缩小,生命周期不变

字符串常量

#include <stdio.h> 
void main(void) {
    char s[] = "cat";
    const char *p = "rat";
    printf("%s chases %s\n", s, p);
s[0] = 'C';
char* sp = s;
*(sp + 1) = 'A';
printf(&quot;%s chases %s\n&quot;, s, p);
//最终输出:
//cat chases rat
//CAt chases rat
}

C中对于字符串初始化通常有两种方式(不考虑string.h)

• char s[] = "..."
• char *p = "..."(C11后规定只能const char*s = "...")

前者易理解,对于后者:相当于将一个字符内容为 "rat\0" 的字符数组首地址赋值给字符指针p,不允许使用字符指针修改字符串中数值即*p = 'R'是不被允许的,因此C11后强制要求使用const char *初始化字符串,表示指针指向数据对指针来说是不可变的(const char* p等价于char const *p,区别于char * const p)

静态分配的缺点

1. 命名可能产生冲突
2. 不灵活,因为是在编译前就分配了空间,程序运行中无法调整空间大小
3. 生命周期直到程序结束,因此对于暂时使用的变量产生空间浪费
4. 无法实现递归,因为递归本身是动态过程,随着递归深入,当前帧必须进行"入栈-出栈"

动态分配

定义:程序在执行时进行内存分配,heap只能动态分配,stack也能进行动态分配

stack分配

• 变长数组即为栈上动态分配的代表,使用alloca向stack申请空间

heap分配

• 堆是由malloc()函数(C++ new)分配的内存块(chunk),内存释放由程序员手动控制,在C语言为free函数完成(C++ delete)

对比

选择题知识点

1. 当某个compiler静态存储所有的变量,返回地址,寄存器等,则理论上①局部变量②函数调用③递归中的①②可以继续实现:在数据段保存变量,地址即可
2. ⭐阻碍C语言自动释放heap空间的原因是(即自动free)

①指针不一定都被初始化:未考虑该问题的编译器可能为未初始化指针随机分配地址,一旦随机到被占用的地址,随意free会产生问题

②强转(casting)使得指针身份无法确定:free的时候,依靠的只有malloc时的地址和分配内存的大小-->当指针被强转其他类型,对应区域将无法被free

3. ⭐要在堆上分配100个long的空间是,语句是 long* a = (long*)malloc(100*sizeof(long))
4. ⭐void* malloc()返回值

• 分配成功:返回分配空间的地址/指针
• 分配失败; 返回空指针NULL

Ch7-8 堆内存管理

原目录：系统级编程（CSAPP）

查看语雀原文

参考链接: melloc堆区的动态内存分配(该部分对应CSAPP第九章)

空闲块管理

堆被分成许多不同的blocks,只有记录空闲块位置才能进行空间分配

分配器原则

• 处理任意请求序列
• 立即响应请求
• 只使用heap
• 对齐块
• 不修改已分配块

隐式空闲链表

显式空闲链表

放置策略⭐

当需要把数据放入free block时,需要考虑选择哪一块,即放置策略(placement policy)

最先适配(First Fit)

从链表head开始,选择最先满足需求的块

• 优点:把较大空闲块留在了链表后
• 缺点:容易在链表起始处产生碎片,使得速度速度降低

下次适配(Next FIt)

和FF类似,但每次从上次结束处开始搜索

• 优点:比FF速度快
• 缺点:空间利用率低

最佳适配(Best Fit)

从链表head开始,选择满足且最接近需求大小的块

• 优点:空间利用率高于FF和NF
• 缺点:需要彻底对heap进行搜索

最坏适配(Worst Fit)

从链表head开始,选择满足且最大的块

分离适配(Segregated Fit)

分离适配下分配器维护着空闲链表数组,每条链表维护大小不同的块

• 优先进行first fit

• 适配后,对当前块分割,提高利用率
• 未适配,则考虑合并(coalesce)空闲块,如果依旧不满足,则请求额外空间,从数组中更大一级的链表中适配

垃圾收集器

定义:垃圾收集器是一种动态内存分配器,自动释放程序不再需要的分配块,即垃圾

思想:

• 垃圾收集器把内存视为可达图,图中可分为root node和heap node,堆节点都位于堆中的已分配块,而根节点都不在堆中,需要无论何时都可达,可以是寄存器,栈中变量,全局变量等.p->q表示p中某个位置指向q中某处,此时q可达,而不可达节点即为垃圾,表示程序不会再去访问它
• 垃圾收集器需要维护一张可达图,回收不可达节点,返回块给空闲链表

实际:

• Java等对指针使用严格的语言可精确维护可达图,进行垃圾回收
• C/C++等对指针使用更灵活的语言无法精确维护(Ch6选择第2题),保险起见,只能认为某些"垃圾"也是可达的--保守垃圾收集器

常用算法⭐

参考链接: 常见GC算法介绍

Reference counting-引用计数算法

思路:给每个对象一个引用计数器,每当对象被引用,counter就会加1；当引用失效时，counter的值就会减1.任何时刻计数器的值为0的对象就是不再被使用的,可被清除

优点:

• 回收空间随时进行,回收时不会引发中断挂起程序
• 简单高效,可利用全部heap空间

缺点:

• counter增加任务繁重
• 实现复杂
• 循环结构无法回收:即两个对象相互引用,计数永远是1,因此被JVM放弃

Mark and Sweep-标记清除算法

思路:分为标记和清除两阶段.

• 标记:从根结点出发遍历对象,对访问过的对象打上标记,表示该对象可达
• 清除:标记完成后对那些没有标记的对象进行回收(不可达对象)

缺点:

• 效率低:两阶段效率都不高
• 堆空间碎片化:算法结束后会产生大量不连续的堆空间碎片
• 周期性中断:用于回收空间

Copying-复制算法

思路:将内存空间按容量分成两块,当一块内存用完的时候,就将还存活着的对象复制到另外一块上,然后把已经使用过的一块一次性全部清除.这样使得每次都是对半块内存进行内存回收,分配时就不存在内存碎片等复杂情况,只要移动堆顶的指针,按顺序分配内存即可,通常简单高效

优点:

• 分配时只要移动堆顶的指针即可,通常更高效

缺点:

• 堆使用效率低下
• 周期性中断:用于回收空间

小结

内存相关Bug

间接引用坏指针

某些指针指向内存空洞或只读区域,无意中引用/写入会产生后果

如下代码,如果写成错误形式,scanf把val的值视为内存地址写入数据,结果难料

//正确
scanf("%d",&val);
//错误
scanf("%d",val);

未初始化指针

函数中未初始化的指针值是未定义(0xcccccccc),实测如下:

⭐读取未初始化的存储器

bss存储器位置总是被加载器初始化为0，但堆存储器不是这样,此时可以:

• 显式的初始化新得到区域为0
• 使用void* calloc()代替void* malloc(),malloc()不初始化分配的内存,calloc()初始化已分配的内存为0

栈溢出

栈大小优先,如果不检查串的大小就写入栈中的目标缓冲区可能会有缓冲区溢出错误

内存泄漏

未free()heap上申请的空间

⭐错误的引用指针,而非对象

long a[10];  
ptr = a + 5;  
*ptr++ = x; //实际效果a[5]=x; ptr=ptr+1

一元运算符++和*优先级相同,则从右向左结合,即*(ptr++),则指针值+1,同时后缀++的特性表示先使用当前值进行下一步计算,即a[5] = x,然后再进行ptr++(极易错写为a[6]=x)

⭐重复free()

#include <stdio.h> 
#include <malloc.h>
void main(void) {
    int* p = (int*)malloc(100);
    int* q = p;
    free(p);
}

实际上free(p)和free(q)结果一样,因为二者保存的地址是相同的(再次说明free及其依赖malloc时的地址),free后二者指向相同的被freed heap空间

• 当重复free(q)时,会报关于无效heap指针的错误

选择题知识点

1. 当C中变量被声明为static是①变量被静态分配空间②变量只对当前文件内函数可见(无论全局,局部),static声明不代表变量值不经常改变
2. 静态变量都会自动初始化为0,见bss区
3. ⭐关于结构体free():当free()一个使用malloc()动态分配空间创建的结构对象时,只会释放结构指针指向的堆空间,当结构体内也还有指针时,该内部指针指向空间不会被释放,可见free()释放struct结构体,尤其对于结构体中含有char* ptr时应当注意
4. 避免重复free()的办法:为没一块设置free flag,free()前检查标记
5. 垃圾收集器回收无法通过解引用指针访问的空间
6. 提高内存池性能的方法是"一次性free()池中所有block"
7. 垃圾回收器的"引用计数": 指向当前block的指针个数
8. 对于常用数据类型,为了提高malloc()/free()效率,可以维护一条对应数据类型大小的空闲块链表
9. 内部碎片:被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间,比如被malloc后却从未free的空间;

外部碎片:没有被分配出去（不属于任何进程),但由于太小无法分配给新进程的内存空闲区域,比如标记清除后的块

10. 关于分配器的说法,错误的为B,分离空闲链表优先FF

A. 最理想情况,带标记边界的合并使用常数时间

B. 分离空闲链表优先BF

C. 负载必须和边界对齐

D. 显式空闲链表更快

Ch9 性能度量

原目录：系统级编程（CSAPP）

查看语雀原文

法则

80/20 Rule

即Pareto Principle, 80%的CPU时间被20%的程序占用,要想提高性能需要关注这20%

Amdahl's Law

阿姆达尔法则:系统优化某部件获得的总提升率取决于该部件使用的频率(占总执行时间的比例)

\(总加速比=\frac{1}{(1-升级比例)+\frac{升级比例}{升级加速比}}\\ \scriptsize\color{Red}*升级加速比=\frac{原用时}{现用时}>1\)

举例:

计时器

衡量性能的两种常用方法:timer(计时器) & profiler(探查器) tools

Time in CS

CS中的时间分为两种: wall time和cpu time

Timer

要使用time,需要借助timer

性能探查器

统计抽样

Statistical Sampling(统计抽样)是profiler的一种工作模式:通过在程序运行过程中暂停程序,记录堆栈中的信息,然后恢复程序来分析程序.暂停、记录、恢复的速度是非常迅速的,相对于程序的执行时间可以忽略不计

• 优点:①代码可自动执行; ②性能探测的影响可被最小化

选择题知识点

1. 阿姆达尔定律用于程序优化意味着:连续(successive)的优化带来的回报是递减的(diminishing)
2. 可以有效探查程序性能的方法:

①使用C/C++中的stopwatch类

②Statistical Sampling(统计抽样)

③使用系统监控工具(System Monitors)

3. 进行优化的最合理阶段是:函数written&debug结束
4. 优化的第一步是:找到Hotspots
5. 80/20原则程序运行中指:80%的运行时间被20%的代码占用
6. 关于探查器,下列正确说法是: 全部

①GPROF是Linux下的探查器②探查器可估计程序花费时间③探查器可获得不同部分执行时间

Ch10 程序性能优化

原目录：系统级编程（CSAPP）

查看语雀原文

时间复杂度

时间复杂度(Asymptotic Complexity)被用来估算程序运行的开销,常见复杂度如下

常见复杂度和场景

优化编译器的局限

内存别名

程序中两个不同名指针变量可指向相同地址,被称为内存别名(memory aliasing),此时某些优化会带来不同的结果

• (GCC为例)编译器在优化时会假设存在内存别名的情况

示例程序

//优化前,需4读2写
void fun() {
    int a = 1;
    int* p = &a;
    int* q = &a;
    *p += *q;
    *p += *q;
    //结果a = 4
}
//优化后,需2读1写
void fun() {
    int a = 1;
    int* p = &a;
    int* q = &a;
    *p += 2 * *q;
    //结果a = 3
}

上述程序中当p和q同时指向a的空间,此时合并运算会产生完全不同的结果,编译器必须假设存在这种情况

函数副作用

某些时候调用函数会产生一些意料之外的效果

• 编译器需假设每次调用函数都会有副作用(side-effects)

示例程序

//全局变量
int counter = 0;
int f(int x){
    return counter++;
}
//优化前
int func1(x){
return f(x) + f(x) + f(x) + f(x);
}
//优化后
int func2(x){
return 4*f(x);
}

func1若被优化为func2,看似合理,但如果每次调用f()会改变一次全局变量,则优化后产生副作用

CPE

举例,下列为一个向量计算程序,psum1()每次计算一个元素,psum2()每次计算两个元素

分析:

• 起始值368:说明函数的准备,初始化,完成阶段需368周期
• 斜率:即CPE

psum1()计算每个元素周期开销为9

psum2()计算每个元素周期开销为6

常用优化

代码移动(code motion)

把把循环中每次都计算但值都不变的操作移出循环

减少过程调用

比如caller直接使用数组元素,而非通过callee获取元素值后返回给caller

减少不必要引用

在某些循环中,把当前结果保存在临时变量中最后写入,比每次都更新目标内存要高效

循环展开

循环展开(Loop Unrolling),通过增加每次迭代计算的元素数量减少总共所需的循环次数.

如上psum2()使用了2×1循环展开

提高并行性, 常量折叠 ... ...

选择题知识点

1. 对于大部分时候都在比较字符串的程序,使用什么方法可以最大提高性能?

对每个字符串使用独立的指针,这样直接使用指针比较即可

2. 下列函数可进行"减少过程调用"优化:使用temp变量保存s[i],而非每次访问数组

void lower1(char *s) { 
int i;
 for (i = 0; i < strlen(s); i++) 
   if (s[i] >= 'A' && s[i] <= 'Z') 
      s[i] -= ('A' - 'a'); 
}(

3. 从程序运行速度上优化程序可以:使用更快的算法,与占用空间和指针无关
4. 为了优化程序,需要①找到hot spot②理解程序运行时的处理器特性,无需了解所有系统调用
5. 下列有关C程序优化的说法,正确的是: 全错

①只需要配置优化模式即可②无需理解CPU特性③无需关注汇编代码

Ch11 存储与性能

原目录：系统级编程（CSAPP）

查看语雀原文

存储技术

随机访问存储器

非易失存储器

非易失存储器(Nonvolatile Memories),即read-only memory, ROM

存储访问

数据流通过总线在CPU和DRAM主存之间来回

• 总线:一组并行导线,可携带地址,数据,控制信号,多个设备可共享总线

下方图示说明指令mov A,%rax的内存读事务

硬盘

组成结构

性能参数

存储器层次结构

cache

高速缓存原理:对于k,每个位于k层的存储设备(小,快)作为k+1层(大,慢)的cache

• 缓存命中(cache hit):当程序需要k+1层数据d时,它刚好被缓存在第k层中
• 缓存不命中(cache miss):

• 冷缓存/强制不命中/冷不命中(cold cache/compulsory miss/cold miss):第k层是空时导致
• 冲突不命中(conflict miss):由于算法/放置策略导致
• 容量不满足(capacity miss):当程序work set大于缓存大小

局部性原理

时间局部性

被引用过的存储器位置在未来可能会被多次引用（通常在循环中）

• 重复引用会带来时间局部性

空间局部性

一个数据对象附近的块更可能会被使用

• k-步长引用会带来空间局部性,当步长越小,空间局部性越高

对于循环:更小的循环体和更多的循环迭代次数会产生更好的时间+空间局部性

分析以下伪代码的局部性

for (i = 0; i < M; i=i+1) { 
    for (j = 0 ; j < N; j=j+1) { 
        sum += data[i][j];
    } 
}

• sum具有时间局部性,每次循环都会被访问一次;作为标量没有空间局部性
• 对于循环,data[][]有较好的空间局部性,内层循环步长为1;但时间局部性较差,每个元素在函数中只会访问一次

存储器山

读吞吐量(read throughput):程序从存储系统中读数据的速率,当在s秒内读取n字节,则读吞吐量为n/s(B/s),单位通常为MB/s

存储器山:编写程序,使用循环发出一系列读请求测试读吞吐量,程序中size表示工作集大小,stride为步长,以不同的size和stride测试读吞吐量,得到吞吐量与时间和空间局部性的二维函数--存储器山

• ⭐size越小,工作集越小,时间局部性越高
• ⭐stride越小,跨度越小,空间局部性越高

下图为奔腾处理器的存储器山

解读:

1. 山脊(ridges):

• 图中三条山脊,实际上可见凸起为两条,对应size=16k和512k附近,表示工作集完全在L1和L2缓存中的吞吐量
• 当吞吐量恰好和L1或L2吻合,达到最大吞吐量
• 当>512k时,工作集开始存储在主存中,此时吞吐性能大幅下降

2. 斜坡(slopes):

• 随着步长的增加,不同山脊的吞吐量下降,体现了空间局部性变差的影响
• 注意到即便在主存山脊中,吞吐量最高点也是最低点数倍,说明在时间局部性很差时,空间局部性也很重要

选择题知识点

1. 关于引用局部性,下列正确的是②

①在compiler帮助下可精确预测未来的引用位置②是典型的程序特性③有数学证明

2. 在存储器分层中,对应传输最大和最小数据块的层次为:

最大块:主存<->磁盘 最小块:CPU寄存器<->cache

3. 未来的存储器分层发展趋势为:不会消失
4. 给定代码

a = b;
c = d;
if (e == 1) return;

无论变量a,b,c,d,e的位置,都体现了引用(时间)局部性(重复引用)

5. ⭐管理cache<->主存数据传输:OS

    管理register<->cache:compiler

6. 存储分级:利用了SRAM的快速和disk的大容量

Ch12 Cache深入

原目录：系统级编程（CSAPP）

查看语雀原文

之前在计组和操作系统都学过Cache映射问题,每本书的定义都不太一样,这里统一总结为CSAPP的描述

场景

指令指示CPU从主存地址A处读取内存字w,此时CPU把A发送给cache:

• 当L1中有w的缓存副本,cache hit
• 当L1无w的缓存副本,cache miss

• L1向main memory请求w的副本,放入自己的cache line后提取出w返回给CPU

关注的点:

cache如何确定请求是否命中,然后提取请求的字--分为三步"组(set)选择,行(block)匹配,字(word)抽取",在了解过程之前需要认识cache的组织结构

cache结构和分类

结构

分类

根据set和line的不同组织方式,cache和main memory之间的映射有三种方式:

• 直接映射:S组,每组一行,E=1
• 组关联映射:E路组关联,分为S组.每组E行
• 全关联映射:1组,S=1,包含所有行

直接映射

组关联映射

全关联映射

写策略

当cache中的字w被更新后需要保证主存中的对应块也被更新,有两种策略:write back和write through

write through

即当cache更新后,立即把block写回到下一级的cache或主存中

write back

当cache更新后,推迟下一级block更新,直到当前block需要被换出时才写回

选择题知识点

1. 编写cache友好程序使得命中率提升,可以减少wall time
2. ⭐给定以下代码,当使用32字节cache line的全关联映射时,数组a需要从主存中取多少字节数据

int a[100];
for (i = 0; i < 17; sum += a[i], i++);

最多96次,首先未说明cache是否为空,假设最坏情况,初始为空,每次循环时取一行,即32字节,其中可包含8个int,循环需要读取数组a[0]~a[16],此时未命中情况为a[0],a[8],a[16]总共读取了a[0]~a[23],对应4*24=96字节

3. LRU是最有效的cache替换策略,是因为考虑了"引用局部性"
4. ⭐给定代码

int data[1 << 20]; 
void callee(int x) { 
    int i, result;
    for (i = 0; i < (1 << 20); i += x) { 
        result += data[i]; 
    } 
}

通过以上函数可确定的是:cache line大小

需要明确,循环执行时间长短由数组的内存访问次数决定,通过给定不同的步长x进行时间统计,当x大于cache line时,每次循环都miss,此时时间会明显变长,x即为cache line大小

5. 当需要行替换时,最实际的实现是:随机替换(LRU实现困难)
6. 计算机中cache级别各不相同,且不一定有data cache和instruction cache
7. 一个code+data<256k字节的程序在cache空间512k字节的全关联映射下:无法确定fetch情况,信息太少
8. ⭐在32位机上,当cache有128行32字节cache line时,给定下方代码,假设a[],b[]起始地址位0x800000和0x801000,则执行结束时cache需要从主存中取多少字节

int b[1024]; 
int a[1024];
for (i = 0; i < 17; sum += a[i] + b[i], i++);

1088字节,由已知,内存地址32位,128=2⁷,中7位作为set,每个block8个字,需3位offset,则tag有22位.补全ab起始地址,为0x00800000和0x00801000

开始循环时a[0]和b[0]的set都相同,占据同一行,a[0]发生冷不命中,b[0]发生冲突不命中

a[1]对应0x00800001,b[1]对应0x00801001,还是占据开始的set,a[1],b[1]都发生冲突不命中

...以此类推,17次循环每次都发生两次cache miss,每次都读取2*32字节的数据,总共读取2*32*17=1088字节数据

Ch13 链接

原目录：系统级编程（CSAPP）

查看语雀原文

概述

链接(Linking)是把各种代码和数据片段组合成一个单一文件的过程,此文件可被加载到内存中执行,链接可发送于各种时刻:

• 编译时(compile time):源码被翻译为机器码时
• 加载时(load time):程序被loader加载到内存时
• 运行时(run time):由程序来执行(动态链接)

静态链接

示例

以下两个.c文件说明链接的过程

在linux下使用gcc -Og -o prog main.c sum,c命令,调用GCC驱动程序在适当时候使用预处理器,编译器等对源码进行编译,过程如下

最后一步中,链接器(linker,ld)把main.o和sum.o以及一些必要的系统文件组可起来创建可执行目标文件prog

静态链接:以一组可重定位目标文件和命令行参数位输入,生成一个完全链接的,可加载和运行的可执行目标文件作为输出的过程

⭐链接器在其中的主要任务:符号解析(symbol resolution) & 合并同类型模块 & 重定位(relocate)

目标文件

目标文件有三种形式:

• 可重定位目标文件(Linux下.o,Win下.obj):二进制代码和数据,编译时可于其他可重定位目标文件组合
• 可执行目标文件(.exe):二进制代码和数据,可直接被加载到内存执行
• 共享目标文件:特殊可重定位目标文件

可重定位目标文件

符号解析⭐

目标文件定义和引用了符号,其中每个符号对应函数/全局变量/静态变量,符号解析就是把引用和定义关联,具体实现依靠把引用和可重定位目标文件符号表中确定的符号定义关联

符号&符号表

可重定位模块m都有符号表,其中包含m定义和引用的符号信息,符号有以下三种:

• 由m定义可被其他模块引用的全局符号:非static函数和全局变量
• 由其他模块定义但被m引用的全局符号:称为外部(external)符号,对应其他模块的非static函数和全局变量
• 只在m中定义和引用的局部符号:对应m中的static函数和static全局变量

ELF符号表格式
下图为一个Linux下ELF符号表的格式:

符号表生成

给定以下两个.c文件,填表说明swap.o符号表情况

*注意定义和声明不同swap()虽然声明在m.o但定义在swap.o

符号解析

有了符号表后,linker可以把每个引用和其定义关联起来,对于局部静态变量的关联很简单,但全局符号的引用较复杂,linker需要在所有输入模块中找到其定义,如果定义不存在或定义不明确都会报错

编译时,compiler向as输出所有全局符号,其中强符号:函数和已初始化全局变量;弱符号:未初始化全局变量

1. 不允许有多个同名强符号
2. 一个强符号和多个弱符号同名,选择强符号
3. 多个弱符号同名,从中任选一个

合并&重定位⭐

完成符号解析后,ld得到目标模块中.text和.data的大小,此时可以开始重定位,将合并输入模块,并为每个符号分配运行时地址,分为两步:

1. 重定位节和符号定义:ld把所有相同类型的节合并,如把所有模块的.data合并成为输出exe的.data节,之后ld把运行时内存地址赋给新的节/输入模块节/输入模块符号==>最终程序每条指令和全局变量都有唯一运行时地址
2. 重定位节中符号引用:ld修改.text和.data中每个符号的引用,使其指向正确的运行时地址,依赖于可重定位目标文件的rel节(重定位条目)

重定位条目

as生成.o/.object模块时,不知道数据或代码最终在内存的什么位置,as在遇到任何一个最终位置未知的目标引用时就会生成一个重定位条目,告诉ld在合并生成exe时如何修改,对代码和数据的重定位条目在.rel.text和.rel.data中

ELF重定位条目格式

⭐两类最基本重定位类型

• EFL-R_X86_64_32/PE-DIR32:重定位一个使用32bits绝对地址的引用.

通过绝对寻址,指令中编码的32btis值=有效地址,无需修改

• EFL-R_X86_64_PC32/PE-REL32:重定位一个使用32bitsPC相对地址的引用.

PC相对地址是距离PC的当前运行时值的偏移量.

通过PC相对寻址指令,指令中编码的32bits值+PC当前运行时值=得到有效地址

算法如下:

可执行文件

加载

loader把可执行文件中代码和数据从磁盘放入内存中,然后跳转到程序的入口执行,此过程为加载

选择题知识点

1. loader可以完成:从磁盘中加载&映射exe到内存中
2. linker可以完成:符号解析(resolution),重定位(relocation),合并同类型section
3. 说明可重定位目标文件使用大端/小端的域为ELF header
4. link可发生在compile,load,run time
5. 与解析有关的section:只有symtab
6. 与重定位有关的section:只有.rel.text和.rel.data
7. 当没有特别强调时,所有未初始化全局/静态变量都在.bss中,不考虑COMMON伪节
8. ⭐可执行目标文件的格式有:PE,COFF,ELF,a.out

Ch14 异常与线程/进程

原目录：系统级编程（CSAPP）

查看语雀原文

异常

控制流

从给处理器加电开始到断电,PC假设一个值序列a₀,a₁...a_n-1,其中每个a_i就是指令I_i的地址,每次从a_i到a_i+1的过渡即为控制转移(control transfer),控制转移序列即为处理器的控制流(control flow),而异常就是控制流中的突变,用来响应处理器状态中的某些变化,其基本思想如下

四类异常⭐

异常处理

异常处理是软硬件一起协作的过程:

• 操作系统在内存中分配并初始化异常表
• 运行时CPU检测到事件,明确异常号k,使用其索引异常表,找到适当的异常处理程序地址
• 开始处理异常

线程与进程

进程(process)具有两大特点:

• 资源所有权: 进程包含存放进程映像的虚拟地址空间
• 调度/执行: 进程具有执行状态和优先级,是可被系统调度与分派的实体

通常把调度/执行的基本单位称为线程,拥有资源所有权的基本单位称为进程

多线程

操作系统在单个进程中支持多个并发执行路径的能力叫做多线程(multithreading)

线程与进程的区别

选择题知识点

1. 异常是①需要硬件&软件协作处理③依赖硬件:event的发现需要timer一类的硬件
2. 对于异常处理程序(exception handle),它可能不会返回,也可能返回到异常发生处
3. X86中system call的实现需要:trap;

demand paging的实现需要:fault;

hard disk interrupt的实现需要interrupt

4. ⭐进程是资源所有权的单位;线程是调度/执行的单位
5. ⭐以下关于进程的说法正确的是:all

①通过进程,可使程序独占CPU和memory

②进程是一个运行的程序

③进程可由异常实现

6. MessageLoop的相关函数有GetMessage(),TranslateMessage(),DispatchMessage()
7. WIndows程序的起点都是WinMain()
8. WIndows系统内核态线程同步的实现依靠:信号量(semaphore)
9. 优先级倒置(Priority inversion)指高优先级线程间接等待低优先级线程
10. 在时间共享操作系统中，轮询(polling)是不可取的,因为会导致时间浪费
11. 下列适合线程的情况有:all

背景进程:数据比较,拼写检查;

页面呈现:在整个web page到达前;

预先加载:在用户还未浏览到下方界面时

12. 可重入函数(reentrant function)可并行的被不止一个线程调用
13. 锁(lock)指限制临界区(critical section)的访问
14. win下线程①由内核级线程实现②有多种同步机制,而linux下是用户级线程
15. 一个进程的多个线程共享一个虚拟地址空间