CSAPP学习笔记（整数与浮点数的表示与运算）

我的机器现在是32-bits的，因此如果移位数量大于32位会出现

[-Wshift-count-overflow]

的错误。

要注意的是移位运算符的优先级很低，甚至比加减法还低。

奇怪的是，我的机器在移位运算时得出的推断是32-bits的，但是在表示整数的最大值时确实以64-bits来进行的，在我的机器上一个long 型数据能够表示的最大整数是 9223372036854775807

C默认数字是有符号的。

This picture show how to convert a set of binary data to

Unsigned data(Nonnegative)

Example:

位数为W的二进制数的最值

从零到一串二进制数的最值之间，该值是和二进制数一一对应的。eg: 15 = [1,1,1,1]

Binary to two’complement 二进制转换为补码运算公式

Eg:

关于权重的解释与公式的简单应用

有一个不可避免的疑问：如何知道一串二进制码表示的究竟是Unsigned还是Tow’Complement？？？

下图展示了针对不同字长，几个重要数字的位模式。

几组重要公式

补码的最小值的绝对值要比补码的最大值大1

这是因为补码的最小值一定是一个负数，而补码的最大值是一个非负数，零是非负数比如：
一串长度为4的二进制数[1 1 1 1]，我们求它补码的最小值：

我们接着来求补码的最大值

求得补码的最大值是 7.

二进制与十六进制快速转换公式

n = i + 4j
其中n为指数，0 <= i <= 3,j为十六进制0的个数。当i = 0是x开头为1，i = 1时，x开头为2，i = 2时，x开头为4。i = 3时，x开头为8。
例子：x = 2048 = 2^11,11 = 3 + 4*2,因此十六进制数字为0x800

让我们来直接的观察

[1 1 1 1 ] 无符号数：[0 1 1 1 ]UMax
1 + 2 + 4-----------------------Sum == 7
[1 1 1 1 ]补码（有符号数）：[1 0 0 0 0 ]TMin
-8 + 0 + 0 + 0= -8------------Sum = -8

对于一串二进制数[1 1 1 1 ]它的无符号最大值是[ 0 1 1 1 ] 它的补码的最小值是[ 1 0 0 0 ]。

此处仍需细心研究……

在C中，无符号的乘法运算和补码的乘法运算虽然得到的二进制数不同，截断后的乘积的位级表示都是相同的，见下表：

其实也很简单，看完了课，读完了书，做一些题，看看自己那些做的很好，哪些做的不行，慢慢修正，这就是进步。

几组重要公式：

1. 二进制转换为补码
1

2. 二进制转换为无符号数

3.Unsigned 最大值

4.补码的最小值

5.补码的最大值

6.二进制转换为反码

7. 二进制转换为原码

如何扩展一个数字的位的表示，见下图：

C不同数据类型在32-bits机器和64-bits机器上范围：

补码、无符号数在各种字长的机器上的取值范围

浮点数的加减法溢出实例

// 浮点数不支持结合律
//
#include "stdio.h"

int main()
{
	long long value = 1e10;
	long long int value1 = 3.14;
	printf("%lld",(value1 + value)-value);
	return 0;

// result: -9223372036854775808 == 64-bits 最小long long int 
1
2
3
4
5
6
7
8
9
10
11
12

//
#include "stdio.h"
// float 为小数分配23 bits而，int 占据32bits，因此转换会导致精度丢失
int main()
{
	int value = 2147483647;
	value = (int)(float)value;
	printf("%d",value);
	printf("\nHello,world");
	return 0;
// result:-2147483648
1
2
3
4
5
6
7
8
9
10
11

#include "stdio.h"
// double 为小数分配53bits 而int 占据32bits因此不会导致精度丢失
int main()
{
	int value = 2147483647;
	value = (int)(double)value;
	printf("%d",value);
	printf("\nHello,world");
	return 0;
// result:2147483647
1
2
3
4
5
6
7
8
9
10

————————————————————————————————————————————————————————————————————————————————————

关于浮点数非常重要的是：浮点数的符号是单独存储的，因此符号具有单调性，不存在负负得正，浮点数的溢出会往无穷方向发展而不是负极得正。浮点数运算可以交换运算顺序，但是并不能按照数学原理随意添加括号。

浮点数的存储方式

单精度浮点数存储

双精度浮点数存储

Intel 扩展精度存储（仅限Intel处理器）

浮点数的几组重要公式

求指数

求偏移量

参数说明

value 为十进制下的数值，S单独存储符号的位，M尾数介于1.0-2.0之间，E指数，bias偏移量，即小数点后有多少位。Exp是Exponent 指数。frac 尾数，即小数位的二进制串。k为Exp位的数量，具体使用方法见下图。

有一个重要问题：e= 1 - bias, 而Bias = 2^k - 1 ，也就是说知道e和Bias的前提是知道存储指数的位数，那怎么确定这个位数呢？下图给的例子也只是4-bits的例子

猜测上述问题答案是：下图中的例子只是为了方便理解，在实际中exp的位数是固定的，8bits或者是11bits(单精度与双精度)

浮点数公式运用实例

浮点数值的分布图

几组“有趣”的数(doge)

精通细节是理解更深和更基本改变的先决条件。“我理解了一般规格，不愿意劳神去学习细节！”这实际上实在自欺欺人。花时间去研究示例，并对照答案来进行检验，是非常关键的。

关于溢出

溢出是整数、浮点数的常见话题。溢出的底层原理是：有限数量的位不能满足无限膨胀的数字的要求，多出来的不能够被表示的数字就是发生了溢出现象。

reading question：

计算机有哪几种不同的二进制表示形式？？
char* 使用全字长
什么是掩码运算？？
整数字符扩充和字符截断还需要重点关注
第二章节的习题需要做完。

用Exclusive-Or 实现变量值的交换,挺有意的……

int swap(int x, int y)
{
	x = x^y;
	y = x^y;
	x = x^y;
	return 1;
}
// this program has no performance advantage to this of swapping
1
2
3
4
5
6
7
8

gdb是一个非常强大的调试程序。你可以单步检查程序并对其中的程序进行一些操作。如果这个程序有对应的源代码，那么gdb会调用源代码来进行调试，不过没有也行。在gdb中可以进行反汇编。

objdump是一个重要的反汇编器。

Function swap:C code && Assembly code

小伙伴们大家好呀!!今天是 2022.8.28 今天继续深入理解计算机系统！！，今天学习的是：Machine level program, 主要学的是 基本的Intel x86系列汇编指令，但是并不要求会写汇编，只需要能够理解汇编就行啦！！ 虽然可能理解都费劲吧

Intel x86 指令 leaq

猜测： Src 是地址，也就是括号里可进行值的计算。 Dst 是最终要赋值的寄存器。搭配上移位运算简直简直了！！

long m12(long x)
{
return x*12;
}
1
2
3
4

汇编代码：

leaq (%rdi, %rdi, 2) , %rdx                           #%rdx = 3%rdi
salq $2, %rax                                         #%rax = 4%rax = 4*3%rdi = 12%rdi
1
2

---

---

C数据类型在IA32中的大小

C各数据类型：IA32与x86-64的比较

控制

条件码

CF: 用于检查无符号操作数的溢出
ZF: 最近得出的结果为0
SF: 最近的操作得出的结果为负数
OF: 补码溢出
LeaL指令分明只是用于简单的算术操作。这段话挺让人困惑：
加载有效地址 （load effective address）指令leal 实际上是movl指令的变形。他的指令形式是从存储器读取数据到寄存器，但实际上他根本就没有引用存储器。它的第一个操作数看上去是一个存储器引用，但该指令并不是从指定的位置读入数据，而是将有效地址写入到目的操作数。另外它还可以简洁地描述普通的算数操作。编译器经常发现一些Leal的灵活用法，根本与有效地址计算无关。目的操作数必须是一个寄存器。

什么是有效地址

从运行实体（指进程/线程/中断处理器/内核组件/）的角度来说，有效地址就是一个可以用于指定那个内存位置可以用来执行存取操作的值。·
个人理解：有效地址始终是地址，这就说明了Leal始终进行的是取址运算，而不是从指定的内存位置读取数据的运算，Leal的最终结果是将计算得到的地址交给某个寄存器也可以说leal用于生成一个指针。

以下内容亟待整理

Machine-Level Programming : Procedures

基于x86 硬件，
ABI：Application Binary Interface,应用程序二进制接口，用于规定寄存器的惯常用法。

在一个函数内部如何将控制递给另一个函数？

通过使用call指令，call指令会首先把返回地址入栈，并跳转到被调用过程的起始处。当callee进程被处理完之后，%rip 会从栈中弹出原先的返回地址，这样便完成了从主进程到父进程的一个完整流程。

Stack 不是什么特殊的内存，它只不过是普通内存的一个区域。

对于汇编层面的程序员而言，内存只是一个巨大的字节数组。

在这个巨大数组的某个地方，我们发现了stack程序用栈来管理过程调用与返回的状态，在栈中，程序传递潜在信息、控制信息和数据，并分配本地数据。栈能够实现这些功能的原因在于栈符合过程调用和返回的整个想法的本质：先进后出原则。

需要注意的是：幻灯片中的栈是反方向的，栈顶和栈底的方向反了

利用pop弹出数据后，数据并没有被魔法般的抹去，而是继续存留在内存中，只不过被栈所忽视了。

小技巧

在汇编中看不到指令所在的地址，所以有时必须使用反汇编来查看指令所在地址。

call
ret
these tow just do the control part of a procedure.

%rip 程序计数器， Instruction pointer

函数的参数如何传递？
按照使用惯例，一个函数的前留个参数会使用寄存器，从第七个开始将使用栈来传递。

如何确保被调用的函数返回到正确的位置上？

call指令在启动时会把返回地址入栈到栈帧的上面，这样当进程结束后，栈定便会回到返回地址，并将这个地址传个 %rip，这样便能保证程序会到正确的位置上。

passing data

编译器是怎么知道如何将栈恢复到原来的位置的？

%rax 用于函数的返回值。

前6个参数要求使用特定的寄存器。此处的参数必须是整数或者是指针类型。浮点型参数室友另外一组单独的寄存器来传递的。

如果函数的参数超过了6个，那么多于的参数将会被放入栈上的内存中。

基本上代码能运行是基于这样的假设：无论什么参数都按列出的顺序被传递给这一系列寄存器。

在64-bits机器上，汇编指令的push 、pop、ret、等都是基于8字节的，所以movl等双字操作会出错。

stack frame：用于辅助理解本地变量。为单个过程分配的那部分栈称为栈帧。栈的思想和过程调用以及返回的思想完全吻合。

stack frame 栈帧结构图。一个栈帧以%ebp开头，以%esp结尾。%esp作为栈顶常常变动，但是%ebp却不经常运动。有时%ebp不是必须存在的，它也可以作为Callee-saved 寄存器。

控制转移指令

控制指令

call 指令和ret 指令使用示意图

解释：

1. 执行 call 时有两个动作：1入栈call指令的下一个指令的地址用于返回。2跳转到call指令所指内容
2. 执行 call 后有两个动作：1pop栈顶用于返回到主程序 2把栈恢复原貌

我们把栈上用于特定call 的每个内存块称为栈帧

so each block we use for a particular call then is called the stack frame

%rbp ： base pointer，有时用于开启一个栈帧

栈与递归

All the sort of infrastructure required to support recursion is built into this whole stack discipline

递归所需要的所有基础结构都由栈的原则所保证。

下面是一个对照例子

递归部分的内容亟待整理（haha）

当一个寄存器以 e开头时，它会将 高32位设置为0

leaq 的本职工作是创建指针。

leaq 不会内存引用处读取数据，而是直接将地址存储给目标寄寄存器

sub 是为栈分配空间，add 是为栈减小空间。

ret指令将始终采用栈指针指向的地址并将它作为返回地址。

术语： caller调用函数的人、 callee被调用的人

caller saves temporary values in its frame befor the call

callee saves temporary values in its frame before using
caller resotres them before returning to caller

寄存器使用惯例

如果特定函数想要更改某寄存器的值，他需要做的是先将值存储起来，然后将它放入栈中，在该函数被终结前把它恢复到初始状态。如果你不适用帧指针，则可以把%rbp视为 callee 保存的寄存器。 每个程序都会以这种原则处理%rbx， 即修改它之前先把它的值暂时存储在栈上，之后在从栈中恢复。

x86系列寄存器用法：

注：在以上寄存器中，有6个 argument 寄存器专门用来存储函数参数，但是当函数参数多于6个时，从第7个开始的参数会被入栈。

x86-64 的栈

Machine-Level programming : Data

在机器代码里是没有数组这一概念的，而是将其视为字节的集合。这些字节的集合是在连续位置上存储的。结构也是如此。它也是作为字节集合来分配的。

C编译器的工作就是生成适当的代码来分配该内存。（应该是根据方括号中的数字）

数组：数组的大小等于元素个数乘以元素类型大小

对于单目运算符，——或者++来说是不能直接操纵数组的头指针的。因为根据声明，头指针是一个常量。

C语言没有数组下标越界检查机制，因此你可以为数组提供负值，但是得出的是未定义的值。

针对指针的加法运算，只能是一个指针加上一个常规的整数。

两个指针可以相减，但是不能相加。

相加会出错

test.c:9:5: error: invalid operands to binary + (have ‘int *’ and ‘int *’)
    9 |  p1 += p2;
      |     ^~

相减会警告

test.c:9:5: warning: assignment to ‘int *’ from ‘long int’ makes pointer from integer without a cast [-Wint-conversion]
    9 |  p1 -= p2;
      |     ^~

Val + i 会被缩放成 x + 4i (需要结合ppt来看此处)

不要在程序里任意洒放任意常数值

使用#define 来定义常值，并给出一些有意的名称和一些文档说明。

如果你要创建复杂的数据结构，那么使用typedef是一个非常好的想法，我强烈建议你把它分解为类型定义，因为C中的声明符号很快就会变得相当费解。

#include ZLEN 5
typedef int zip_dig[ZLEN];
zip_dig cmu = {1,5,2,1,3};
zip_dig mit = {0,2,1,3,9};
zip_dig ucb = {9,4,7,2,0};
zip_dig set = {cmu, mit, ucb};
1
2
3
4
5
6

在上面的代码中，首先使用了typedef定义了包含五个元素的数组，等同于封装了一个数据类型。它说明了被定义的数据必须有包含5个元素。

#include ZLEN 5
#include LEN 4
typedef int zip_dig[ZLEN];
zip_dig pgh[LEN] = {
	{1,2,3,4,5},
	{1,2,3,4,5},
	{1,2,3,4,5},
	{1,2,3,4,5},
}
// 定义了一个二维数组
1
2
3
4
5
6
7
8
9
10

你会在C语言中看到指令，机器代码和构造之间相当密切的关系。

指针运算和C语言的全部想法是C语言真的是那些长期从事汇编代码的人所构思的，他们在想：我如何让它看起来像一种高级语言。但又在一种变成语言里保持所有的灵活性以及我所学会的在汇编代码里玩的所有技巧。使指针运算使得C语言“看起来像”一种高级语言。

在C语言里你会看到指令，机器代码，和构造之间相当密切的联系。

整个++和+= 其实就是 INC 运算和 各种 mov sub add lea mul 等运算的表现

C语言中数组和指针之间的真正区别是什么？

当你在C中声明一个数组时，你既在分配空间，正在为它分配某个位置的空间，同时你也正在创建一个允许在指针运算使用的数组名称。

而当你只是声明一个指针时，你所分配的只是指针本身的空间，而没有给他指向的任何东西分配空间。
阅读K&R中关于如何读C语言中的指针和声明的那一章节

是不是把二位数组的行看成了一个指针，而把列的成为被指针指向的内容。

Nested array row access : 嵌套数组行访问

嵌套数组行开始地址 A + i*(C*K) 即数组首地址加上行数乘以每行所占字节数。

嵌套数组元素地址：A + i*(CK) + jK = A + (i*C + j)*K.A是数组首地址，i是行号，C是类型大小，K是每行元素个数，j 是列号比如phg[1][2], A = phg, i = 1, C = sizeof(int), K = 5, j = 2

Nested Array- C

#include "stdio.h"
#define ZLEN 5
#define LEN 4
typedef int zip_dig[ZLEN];
zip_dig phg[LEN] = {
	{1,2,3,4,5},
	{6,7,8,9,10},
	{11,12,13,14,15},
	{16,17,18,19,20}
};
int main()
{
	return phg[2][1] + phg[1][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Nested Array- Assembly

main:
.LFB23:
	.cfi_startproc
	endbr64
	movl	24+phg(%rip), %eax # %rip + 4*5*1 + 4*i = phg(%rip) + 24, phg[1][1]
	addl	44+phg(%rip), %eax # %rip + 4*5*2 + 4*1 = phg(%rip) + 48, phg[2][1]
	ret
	.cfi_endproc
1
2
3
4
5
6
7
8

结构体

如果我为struct 的所有不同数组元素字段引入其中一个结构，然后编译器将跟踪每个字段的起始位置，然后生成适当的相对结构体地址的字节偏移。所以说对结构本身的内存引用将是结构的起始地址。

Data align

实际上，当一个结构体被分配内存，编译器实际上会在分配空间时，在数据结构中插入一些空白的不被使用的字节。这么做只是为了对其 alignment.基本数据类型需要K个字节时，地址必须时K的倍数。

对齐的原则

实际上现在的大多数机器，一次读取大约64个字节，或者这取决于硬件中的各种宽度。一般来说，如果因为没有个对齐的地址，一个特定的数据跨越了两个块之间的边界，可能会让一些硬件甚至有可能让操作系统采取一些额外的步骤来处理。因此，数据对齐时处于效率原因。其实就是让一类的数据独立开始一个块，而不是这一块一点，那一块一点。

对齐的方式取决于结构中长度最大的元素吗？

是的，取决于元素原始数据类型的最大值，比如一个结构体中有一个int,一个long,一个short,那么对齐应该按照long大小即8个字节来进行。

对齐会额外消耗内存，有什么办法尽量节省内存的使用吗？

有的，例子在ppt上，把最大的case 放在开头，在一次放更小的元素可以减小内存的浪费。

是任何数据类型都要求对齐吗？

不是的，对齐仅仅指的是最原始的数据类型，不包括聚合数据类型（即你自己创造的类型）

一些练习题（已解决）

(注：相同的数据类型如果不够对齐要求应该放到一起，当然前提是他们本身就临近。第一个字符总是不偏移。)

Advanced Topics+

1.当运行x86-64 的程序时内存时如何组织的。

2.安全漏洞，即缓冲区溢出

3.Unions

现在64位机器会限制只使用47位地址，地址范围会随着科技进步而越来越大

Limit: 栈被限制大小为8192kb

通过gdb调试工具我们可以同时执行代码和查看反汇编语句

看到7和很多f就知道这是栈的地址

看到很多零后面是4就知道这是代码运行的地方。

重要任务：学习使用gdb

字符串结尾部分会被加上一个字节的 00 表示字符串结束。

代码注入攻击

使用scanf 时要注意 %s, 此时最好在%前面加上数字来限定读取的字节数量。

提高系统安全性的措施

ASLR：栈随机化，地址空间布局随机化

Malloc 分配的地址具有随机性

Canary：金丝雀

Stack Canaries can help

矿井工人使用金丝雀来检测矿井下的甲烷含量。

一般来说，我们使用GCC的时候都会启动栈保护机制

黑客一般攻击手段

1.面向返回编程

2.Gadget

3.注入式攻击

结构体为所有的域分配足够的空间，而联合体会使用占用空间最大的域的大小来分配内存。

##它假设你只会同时使用一个域，如果你同时使用多个域，那么就会出问题。他不是用来处理多个值的，或者说他只是一种通过别名来引用不同的内存的方式。

程序性能优化

本文用于简要记录CSAPP课程

在你选择了合适的算法并且没有错误的前提下：

影响函数性能的主要是：1.内存别名 2.对同一函数的多次调用

#define int data_t
#define int size_t
typedef struct 
{
	int len;
	data_t data[len];
}val;
int get_element(*val v,size_t idx,data_t* rtn)
{
	if(idx >= v->len) return 0;
	*rtn = v->data[idx];
	return 1;
}
// 使用这种方式可以避免数组溢出

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

#define OP +
#define IDENT 0
or
#define OP *
#define IDENT 1
// 本函数用于计算一个数组中所有元素的和或者是积
void combine(val v,data_t* dest)
{
	long int i;
	*dest = IDENT;
	int len = get_length(v);
	for(i = 0; i < len;i++)
	{
	data_t val;
	get_element(&v,i, &val);
	*dest = *dest OP val;
}
}
//使用这种方式可以轻松获得更多运算：加，乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Optimize version
data_t = IDENT;
int len= get_length(v);
data_t * d = get_array_start(v);
for (i = 0; i < len; i++)
{
	t = t OP d[i];
}
*dest = t;
1
2
3
4
5
6
7
8
9

我们不能控制CPU以怎样的频率运行，但是我们可以控制程序总不同的计算部分使用了多少个时钟周期

超标量乱序执行技术，以加快CPU运行速度

指令级并行

一个寄存器相当于一个内存符号

你的机器有足够多的资源同时进行多项操作，但这需要你以某种方式建构你的程序，才能同时使用这些资源。

超标量指令处理器

流水线操作思想，把程序的执行划分为多个独立的阶段。（充分利用有限的CPU资源）

FP：浮点数
latency：

对于那些存在紧密资源联系的代码，流水线处理器无法做到加速处理。

loop unrolling 循环展开

循环展开的基本思想是在循环中同时计算多个值而非一个。

延迟界限是指：在一系列操作必须严格顺序执行时，执行一条指令所要花费的全部时间。

吞吐量限制：由于硬件的数量和性能，基于功能单元的原始计算能力。

CPE: Cycle per Elememt
%xmm寄存器

使用寄存器的低4位或者低8位

矢量加法指令，其中一条矢量加法指令具有执行八次单精度浮点加法的效果或者四次双精度浮点加法。你可以在三个始终周期内并行进行八次浮点流水线乘法。我们最多能接近矢量吞吐量界限。

充分利用csapp网页上提供的资源

1. 注意隐藏的低效率算法
2. 编写编译器友好型代码：注意块的优化：函数调用和内存引用
3. 仔细检查最深层次的代码
   4.开发指令级并行程序
   5.避免不可预测的分支
   6.使代码缓存更加友好。

存储器层次结构

存储器只分为：RAM（随机访问存储器） 和 ROM（只读存储器） 两大类。

内存名词定义：

RAM：Random-Access Memory (RAM)

1.所谓“随机存取”，指的是当存储器中的数据被读取或写入时，所需要的时间与这段信息所在的位置或所写入的位置无关。相对的，读取或写入顺序访问（Sequential Access）存储设备中的信息时，其所需要的时间与位置就会有关系。它主要用来存放操作系统、各种应用程序、数据等。

2.当电源关闭时，RAM不能保留数据。如果需要保存数据，就必须把它们写入一个长期的存储设备中（例如硬盘）。 [3]
RAM的工作特点是通电后，随时可在任意位置单元存取数据信息，断电后内部信息也随之消失。

DRAM：Dynamic Random Access Memory,主存储器和与图形卡相关的帧缓冲区中使用的主力,其实就是内存条。按照自己预算可以拆卸、更新。

我的机器现在是32-bits的，因此如果移位数量大于32位会出现

[-Wshift-count-overflow]

的错误。

要注意的是移位运算符的优先级很低，甚至比加减法还低。

奇怪的是，我的机器在移位运算时得出的推断是32-bits的，但是在表示整数的最大值时确实以64-bits来进行的，在我的机器上一个long 型数据能够表示的最大整数是 9223372036854775807

C默认数字是有符号的。

This picture show how to convert a set of binary data to

Unsigned data(Nonnegative)

Example:

位数为W的二进制数的最值

从零到一串二进制数的最值之间，该值是和二进制数一一对应的。eg: 15 = [1,1,1,1]

Binary to two’complement 二进制转换为补码运算公式

Eg:

关于权重的解释与公式的简单应用

有一个不可避免的疑问：如何知道一串二进制码表示的究竟是Unsigned还是Tow’Complement？？？

下图展示了针对不同字长，几个重要数字的位模式。

几组重要公式

补码的最小值的绝对值要比补码的最大值大1

这是因为补码的最小值一定是一个负数，而补码的最大值是一个非负数，零是非负数比如：
一串长度为4的二进制数[1 1 1 1]，我们求它补码的最小值：

我们接着来求补码的最大值

求得补码的最大值是 7.

二进制与十六进制快速转换公式

n = i + 4j
其中n为指数，0 <= i <= 3,j为十六进制0的个数。当i = 0是x开头为1，i = 1时，x开头为2，i = 2时，x开头为4。i = 3时，x开头为8。
例子：x = 2048 = 2^11,11 = 3 + 4*2,因此十六进制数字为0x800

让我们来直接的观察

[1 1 1 1 ] 无符号数：[0 1 1 1 ]UMax
1 + 2 + 4-----------------------Sum == 7
[1 1 1 1 ]补码（有符号数）：[1 0 0 0 0 ]TMin
-8 + 0 + 0 + 0= -8------------Sum = -8

对于一串二进制数[1 1 1 1 ]它的无符号最大值是[ 0 1 1 1 ] 它的补码的最小值是[ 1 0 0 0 ]。

此处仍需细心研究……

在C中，无符号的乘法运算和补码的乘法运算虽然得到的二进制数不同，截断后的乘积的位级表示都是相同的，见下表：

其实也很简单，看完了课，读完了书，做一些题，看看自己那些做的很好，哪些做的不行，慢慢修正，这就是进步。

几组重要公式：

1. 二进制转换为补码
1

2. 二进制转换为无符号数

3.Unsigned 最大值

4.补码的最小值

5.补码的最大值

6.二进制转换为反码

7. 二进制转换为原码

如何扩展一个数字的位的表示，见下图：

C不同数据类型在32-bits机器和64-bits机器上范围：

补码、无符号数在各种字长的机器上的取值范围

浮点数的加减法溢出实例

// 浮点数不支持结合律
//
#include "stdio.h"

int main()
{
	long long value = 1e10;
	long long int value1 = 3.14;
	printf("%lld",(value1 + value)-value);
	return 0;

// result: -9223372036854775808 == 64-bits 最小long long int 
1
2
3
4
5
6
7
8
9
10
11
12

//
#include "stdio.h"
// float 为小数分配23 bits而，int 占据32bits，因此转换会导致精度丢失
int main()
{
	int value = 2147483647;
	value = (int)(float)value;
	printf("%d",value);
	printf("\nHello,world");
	return 0;
// result:-2147483648
1
2
3
4
5
6
7
8
9
10
11

#include "stdio.h"
// double 为小数分配53bits 而int 占据32bits因此不会导致精度丢失
int main()
{
	int value = 2147483647;
	value = (int)(double)value;
	printf("%d",value);
	printf("\nHello,world");
	return 0;
// result:2147483647
1
2
3
4
5
6
7
8
9
10

————————————————————————————————————————————————————————————————————————————————————

关于浮点数非常重要的是：浮点数的符号是单独存储的，因此符号具有单调性，不存在负负得正，浮点数的溢出会往无穷方向发展而不是负极得正。浮点数运算可以交换运算顺序，但是并不能按照数学原理随意添加括号。

浮点数的存储方式

单精度浮点数存储

双精度浮点数存储

Intel 扩展精度存储（仅限Intel处理器）

浮点数的几组重要公式

求指数

求偏移量

参数说明

value 为十进制下的数值，S单独存储符号的位，M尾数介于1.0-2.0之间，E指数，bias偏移量，即小数点后有多少位。Exp是Exponent 指数。frac 尾数，即小数位的二进制串。k为Exp位的数量，具体使用方法见下图。

有一个重要问题：e= 1 - bias, 而Bias = 2^k - 1 ，也就是说知道e和Bias的前提是知道存储指数的位数，那怎么确定这个位数呢？下图给的例子也只是4-bits的例子

猜测上述问题答案是：下图中的例子只是为了方便理解，在实际中exp的位数是固定的，8bits或者是11bits(单精度与双精度)

浮点数公式运用实例

浮点数值的分布图

几组“有趣”的数(doge)

精通细节是理解更深和更基本改变的先决条件。“我理解了一般规格，不愿意劳神去学习细节！”这实际上实在自欺欺人。花时间去研究示例，并对照答案来进行检验，是非常关键的。

关于溢出

溢出是整数、浮点数的常见话题。溢出的底层原理是：有限数量的位不能满足无限膨胀的数字的要求，多出来的不能够被表示的数字就是发生了溢出现象。

reading question：

计算机有哪几种不同的二进制表示形式？？
char* 使用全字长
什么是掩码运算？？
整数字符扩充和字符截断还需要重点关注
第二章节的习题需要做完。

用Exclusive-Or 实现变量值的交换,挺有意的……

int swap(int x, int y)
{
	x = x^y;
	y = x^y;
	x = x^y;
	return 1;
}
// this program has no performance advantage to this of swapping
1
2
3
4
5
6
7
8

gdb是一个非常强大的调试程序。你可以单步检查程序并对其中的程序进行一些操作。如果这个程序有对应的源代码，那么gdb会调用源代码来进行调试，不过没有也行。在gdb中可以进行反汇编。

objdump是一个重要的反汇编器。

Function swap:C code && Assembly code

小伙伴们大家好呀!!今天是 2022.8.28 今天继续深入理解计算机系统！！，今天学习的是：Machine level program, 主要学的是 基本的Intel x86系列汇编指令，但是并不要求会写汇编，只需要能够理解汇编就行啦！！ 虽然可能理解都费劲吧

Intel x86 指令 leaq

猜测： Src 是地址，也就是括号里可进行值的计算。 Dst 是最终要赋值的寄存器。搭配上移位运算简直简直了！！

long m12(long x)
{
return x*12;
}
1
2
3
4

汇编代码：

leaq (%rdi, %rdi, 2) , %rdx                           #%rdx = 3%rdi
salq $2, %rax                                         #%rax = 4%rax = 4*3%rdi = 12%rdi
1
2

---

---

C数据类型在IA32中的大小

C各数据类型：IA32与x86-64的比较

控制

条件码

CF: 用于检查无符号操作数的溢出
ZF: 最近得出的结果为0
SF: 最近的操作得出的结果为负数
OF: 补码溢出
LeaL指令分明只是用于简单的算术操作。这段话挺让人困惑：
加载有效地址 （load effective address）指令leal 实际上是movl指令的变形。他的指令形式是从存储器读取数据到寄存器，但实际上他根本就没有引用存储器。它的第一个操作数看上去是一个存储器引用，但该指令并不是从指定的位置读入数据，而是将有效地址写入到目的操作数。另外它还可以简洁地描述普通的算数操作。编译器经常发现一些Leal的灵活用法，根本与有效地址计算无关。目的操作数必须是一个寄存器。

什么是有效地址

从运行实体（指进程/线程/中断处理器/内核组件/）的角度来说，有效地址就是一个可以用于指定那个内存位置可以用来执行存取操作的值。·
个人理解：有效地址始终是地址，这就说明了Leal始终进行的是取址运算，而不是从指定的内存位置读取数据的运算，Leal的最终结果是将计算得到的地址交给某个寄存器也可以说leal用于生成一个指针。

以下内容亟待整理

Machine-Level Programming : Procedures

基于x86 硬件，
ABI：Application Binary Interface,应用程序二进制接口，用于规定寄存器的惯常用法。

在一个函数内部如何将控制递给另一个函数？

通过使用call指令，call指令会首先把返回地址入栈，并跳转到被调用过程的起始处。当callee进程被处理完之后，%rip 会从栈中弹出原先的返回地址，这样便完成了从主进程到父进程的一个完整流程。

Stack 不是什么特殊的内存，它只不过是普通内存的一个区域。

对于汇编层面的程序员而言，内存只是一个巨大的字节数组。

在这个巨大数组的某个地方，我们发现了stack程序用栈来管理过程调用与返回的状态，在栈中，程序传递潜在信息、控制信息和数据，并分配本地数据。栈能够实现这些功能的原因在于栈符合过程调用和返回的整个想法的本质：先进后出原则。

需要注意的是：幻灯片中的栈是反方向的，栈顶和栈底的方向反了

利用pop弹出数据后，数据并没有被魔法般的抹去，而是继续存留在内存中，只不过被栈所忽视了。

小技巧

在汇编中看不到指令所在的地址，所以有时必须使用反汇编来查看指令所在地址。

call
ret
these tow just do the control part of a procedure.

%rip 程序计数器， Instruction pointer

函数的参数如何传递？
按照使用惯例，一个函数的前留个参数会使用寄存器，从第七个开始将使用栈来传递。

如何确保被调用的函数返回到正确的位置上？

call指令在启动时会把返回地址入栈到栈帧的上面，这样当进程结束后，栈定便会回到返回地址，并将这个地址传个 %rip，这样便能保证程序会到正确的位置上。

passing data

编译器是怎么知道如何将栈恢复到原来的位置的？

%rax 用于函数的返回值。

前6个参数要求使用特定的寄存器。此处的参数必须是整数或者是指针类型。浮点型参数室友另外一组单独的寄存器来传递的。

如果函数的参数超过了6个，那么多于的参数将会被放入栈上的内存中。

基本上代码能运行是基于这样的假设：无论什么参数都按列出的顺序被传递给这一系列寄存器。

在64-bits机器上，汇编指令的push 、pop、ret、等都是基于8字节的，所以movl等双字操作会出错。

stack frame：用于辅助理解本地变量。为单个过程分配的那部分栈称为栈帧。栈的思想和过程调用以及返回的思想完全吻合。

stack frame 栈帧结构图。一个栈帧以%ebp开头，以%esp结尾。%esp作为栈顶常常变动，但是%ebp却不经常运动。有时%ebp不是必须存在的，它也可以作为Callee-saved 寄存器。

控制转移指令

控制指令

call 指令和ret 指令使用示意图

解释：

1. 执行 call 时有两个动作：1入栈call指令的下一个指令的地址用于返回。2跳转到call指令所指内容
2. 执行 call 后有两个动作：1pop栈顶用于返回到主程序 2把栈恢复原貌

我们把栈上用于特定call 的每个内存块称为栈帧

so each block we use for a particular call then is called the stack frame

%rbp ： base pointer，有时用于开启一个栈帧

栈与递归

All the sort of infrastructure required to support recursion is built into this whole stack discipline

递归所需要的所有基础结构都由栈的原则所保证。

下面是一个对照例子

递归部分的内容亟待整理（haha）

当一个寄存器以 e开头时，它会将 高32位设置为0

leaq 的本职工作是创建指针。

leaq 不会内存引用处读取数据，而是直接将地址存储给目标寄寄存器

sub 是为栈分配空间，add 是为栈减小空间。

ret指令将始终采用栈指针指向的地址并将它作为返回地址。

术语： caller调用函数的人、 callee被调用的人

caller saves temporary values in its frame befor the call

callee saves temporary values in its frame before using
caller resotres them before returning to caller

寄存器使用惯例

如果特定函数想要更改某寄存器的值，他需要做的是先将值存储起来，然后将它放入栈中，在该函数被终结前把它恢复到初始状态。如果你不适用帧指针，则可以把%rbp视为 callee 保存的寄存器。 每个程序都会以这种原则处理%rbx， 即修改它之前先把它的值暂时存储在栈上，之后在从栈中恢复。

x86系列寄存器用法：

注：在以上寄存器中，有6个 argument 寄存器专门用来存储函数参数，但是当函数参数多于6个时，从第7个开始的参数会被入栈。

x86-64 的栈

Machine-Level programming : Data

在机器代码里是没有数组这一概念的，而是将其视为字节的集合。这些字节的集合是在连续位置上存储的。结构也是如此。它也是作为字节集合来分配的。

C编译器的工作就是生成适当的代码来分配该内存。（应该是根据方括号中的数字）

数组：数组的大小等于元素个数乘以元素类型大小

对于单目运算符，——或者++来说是不能直接操纵数组的头指针的。因为根据声明，头指针是一个常量。

C语言没有数组下标越界检查机制，因此你可以为数组提供负值，但是得出的是未定义的值。

针对指针的加法运算，只能是一个指针加上一个常规的整数。

两个指针可以相减，但是不能相加。

相加会出错

test.c:9:5: error: invalid operands to binary + (have ‘int *’ and ‘int *’)
    9 |  p1 += p2;
      |     ^~

相减会警告

test.c:9:5: warning: assignment to ‘int *’ from ‘long int’ makes pointer from integer without a cast [-Wint-conversion]
    9 |  p1 -= p2;
      |     ^~

Val + i 会被缩放成 x + 4i (需要结合ppt来看此处)

不要在程序里任意洒放任意常数值

使用#define 来定义常值，并给出一些有意的名称和一些文档说明。

如果你要创建复杂的数据结构，那么使用typedef是一个非常好的想法，我强烈建议你把它分解为类型定义，因为C中的声明符号很快就会变得相当费解。

#include ZLEN 5
typedef int zip_dig[ZLEN];
zip_dig cmu = {1,5,2,1,3};
zip_dig mit = {0,2,1,3,9};
zip_dig ucb = {9,4,7,2,0};
zip_dig set = {cmu, mit, ucb};
1
2
3
4
5
6

在上面的代码中，首先使用了typedef定义了包含五个元素的数组，等同于封装了一个数据类型。它说明了被定义的数据必须有包含5个元素。

#include ZLEN 5
#include LEN 4
typedef int zip_dig[ZLEN];
zip_dig pgh[LEN] = {
	{1,2,3,4,5},
	{1,2,3,4,5},
	{1,2,3,4,5},
	{1,2,3,4,5},
}
// 定义了一个二维数组
1
2
3
4
5
6
7
8
9
10

你会在C语言中看到指令，机器代码和构造之间相当密切的关系。

指针运算和C语言的全部想法是C语言真的是那些长期从事汇编代码的人所构思的，他们在想：我如何让它看起来像一种高级语言。但又在一种变成语言里保持所有的灵活性以及我所学会的在汇编代码里玩的所有技巧。使指针运算使得C语言“看起来像”一种高级语言。

在C语言里你会看到指令，机器代码，和构造之间相当密切的联系。

整个++和+= 其实就是 INC 运算和 各种 mov sub add lea mul 等运算的表现

C语言中数组和指针之间的真正区别是什么？

当你在C中声明一个数组时，你既在分配空间，正在为它分配某个位置的空间，同时你也正在创建一个允许在指针运算使用的数组名称。

而当你只是声明一个指针时，你所分配的只是指针本身的空间，而没有给他指向的任何东西分配空间。
阅读K&R中关于如何读C语言中的指针和声明的那一章节

是不是把二位数组的行看成了一个指针，而把列的成为被指针指向的内容。

Nested array row access : 嵌套数组行访问

嵌套数组行开始地址 A + i*(C*K) 即数组首地址加上行数乘以每行所占字节数。

嵌套数组元素地址：A + i*(CK) + jK = A + (i*C + j)*K.A是数组首地址，i是行号，C是类型大小，K是每行元素个数，j 是列号比如phg[1][2], A = phg, i = 1, C = sizeof(int), K = 5, j = 2

Nested Array- C

#include "stdio.h"
#define ZLEN 5
#define LEN 4
typedef int zip_dig[ZLEN];
zip_dig phg[LEN] = {
	{1,2,3,4,5},
	{6,7,8,9,10},
	{11,12,13,14,15},
	{16,17,18,19,20}
};
int main()
{
	return phg[2][1] + phg[1][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Nested Array- Assembly

main:
.LFB23:
	.cfi_startproc
	endbr64
	movl	24+phg(%rip), %eax # %rip + 4*5*1 + 4*i = phg(%rip) + 24, phg[1][1]
	addl	44+phg(%rip), %eax # %rip + 4*5*2 + 4*1 = phg(%rip) + 48, phg[2][1]
	ret
	.cfi_endproc
1
2
3
4
5
6
7
8

结构体

如果我为struct 的所有不同数组元素字段引入其中一个结构，然后编译器将跟踪每个字段的起始位置，然后生成适当的相对结构体地址的字节偏移。所以说对结构本身的内存引用将是结构的起始地址。

Data align

实际上，当一个结构体被分配内存，编译器实际上会在分配空间时，在数据结构中插入一些空白的不被使用的字节。这么做只是为了对其 alignment.基本数据类型需要K个字节时，地址必须时K的倍数。

对齐的原则

实际上现在的大多数机器，一次读取大约64个字节，或者这取决于硬件中的各种宽度。一般来说，如果因为没有个对齐的地址，一个特定的数据跨越了两个块之间的边界，可能会让一些硬件甚至有可能让操作系统采取一些额外的步骤来处理。因此，数据对齐时处于效率原因。其实就是让一类的数据独立开始一个块，而不是这一块一点，那一块一点。

对齐的方式取决于结构中长度最大的元素吗？

是的，取决于元素原始数据类型的最大值，比如一个结构体中有一个int,一个long,一个short,那么对齐应该按照long大小即8个字节来进行。

对齐会额外消耗内存，有什么办法尽量节省内存的使用吗？

有的，例子在ppt上，把最大的case 放在开头，在一次放更小的元素可以减小内存的浪费。

是任何数据类型都要求对齐吗？

不是的，对齐仅仅指的是最原始的数据类型，不包括聚合数据类型（即你自己创造的类型）

一些练习题（已解决）

(注：相同的数据类型如果不够对齐要求应该放到一起，当然前提是他们本身就临近。第一个字符总是不偏移。)

Advanced Topics+

1.当运行x86-64 的程序时内存时如何组织的。

2.安全漏洞，即缓冲区溢出

3.Unions

现在64位机器会限制只使用47位地址，地址范围会随着科技进步而越来越大

Limit: 栈被限制大小为8192kb

通过gdb调试工具我们可以同时执行代码和查看反汇编语句

看到7和很多f就知道这是栈的地址

看到很多零后面是4就知道这是代码运行的地方。

重要任务：学习使用gdb

字符串结尾部分会被加上一个字节的 00 表示字符串结束。

代码注入攻击

使用scanf 时要注意 %s, 此时最好在%前面加上数字来限定读取的字节数量。

提高系统安全性的措施

ASLR：栈随机化，地址空间布局随机化

Malloc 分配的地址具有随机性

Canary：金丝雀

Stack Canaries can help

矿井工人使用金丝雀来检测矿井下的甲烷含量。

一般来说，我们使用GCC的时候都会启动栈保护机制

黑客一般攻击手段

1.面向返回编程

2.Gadget

3.注入式攻击

结构体为所有的域分配足够的空间，而联合体会使用占用空间最大的域的大小来分配内存。

##它假设你只会同时使用一个域，如果你同时使用多个域，那么就会出问题。他不是用来处理多个值的，或者说他只是一种通过别名来引用不同的内存的方式。

程序性能优化

本文用于简要记录CSAPP课程

在你选择了合适的算法并且没有错误的前提下：

影响函数性能的主要是：1.内存别名 2.对同一函数的多次调用

#define int data_t
#define int size_t
typedef struct 
{
	int len;
	data_t data[len];
}val;
int get_element(*val v,size_t idx,data_t* rtn)
{
	if(idx >= v->len) return 0;
	*rtn = v->data[idx];
	return 1;
}
// 使用这种方式可以避免数组溢出

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

#define OP +
#define IDENT 0
or
#define OP *
#define IDENT 1
// 本函数用于计算一个数组中所有元素的和或者是积
void combine(val v,data_t* dest)
{
	long int i;
	*dest = IDENT;
	int len = get_length(v);
	for(i = 0; i < len;i++)
	{
	data_t val;
	get_element(&v,i, &val);
	*dest = *dest OP val;
}
}
//使用这种方式可以轻松获得更多运算：加，乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Optimize version
data_t = IDENT;
int len= get_length(v);
data_t * d = get_array_start(v);
for (i = 0; i < len; i++)
{
	t = t OP d[i];
}
*dest = t;
1
2
3
4
5
6
7
8
9

我们不能控制CPU以怎样的频率运行，但是我们可以控制程序总不同的计算部分使用了多少个时钟周期

超标量乱序执行技术，以加快CPU运行速度

指令级并行

一个寄存器相当于一个内存符号

你的机器有足够多的资源同时进行多项操作，但这需要你以某种方式建构你的程序，才能同时使用这些资源。

超标量指令处理器

流水线操作思想，把程序的执行划分为多个独立的阶段。（充分利用有限的CPU资源）

FP：浮点数
latency：

对于那些存在紧密资源联系的代码，流水线处理器无法做到加速处理。

loop unrolling 循环展开

循环展开的基本思想是在循环中同时计算多个值而非一个。

延迟界限是指：在一系列操作必须严格顺序执行时，执行一条指令所要花费的全部时间。

吞吐量限制：由于硬件的数量和性能，基于功能单元的原始计算能力。

CPE: Cycle per Elememt
%xmm寄存器

使用寄存器的低4位或者低8位

矢量加法指令，其中一条矢量加法指令具有执行八次单精度浮点加法的效果或者四次双精度浮点加法。你可以在三个始终周期内并行进行八次浮点流水线乘法。我们最多能接近矢量吞吐量界限。

充分利用csapp网页上提供的资源

1. 注意隐藏的低效率算法
2. 编写编译器友好型代码：注意块的优化：函数调用和内存引用
3. 仔细检查最深层次的代码
   4.开发指令级并行程序
   5.避免不可预测的分支
   6.使代码缓存更加友好。

存储器层次结构

存储器只分为：RAM（随机访问存储器） 和 ROM（只读存储器） 两大类。

内存名词定义：

RAM：Random-Access Memory (RAM)

1.所谓“随机存取”，指的是当存储器中的数据被读取或写入时，所需要的时间与这段信息所在的位置或所写入的位置无关。相对的，读取或写入顺序访问（Sequential Access）存储设备中的信息时，其所需要的时间与位置就会有关系。它主要用来存放操作系统、各种应用程序、数据等。

2.当电源关闭时，RAM不能保留数据。如果需要保存数据，就必须把它们写入一个长期的存储设备中（例如硬盘）。 [3]
RAM的工作特点是通电后，随时可在任意位置单元存取数据信息，断电后内部信息也随之消失。

DRAM：Dynamic Random Access Memory,主存储器和与图形卡相关的帧缓冲区中使用的主力,其实就是内存条。按照自己预算可以拆卸、更新。

ROM:Read Only memory，一般用作BIOS的载体，用于实现基本的I/O，是系统中非常重要的部分，焊接在主板中不可拆卸。

BIOS:Basic Input Output System

随机存取存储器（英语：Random Access Memory，缩写：RAM），也叫主存，是与CPU直接交换数据的内部存储器。它可以随时读写（刷新时除外），而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储介质。RAM工作时可以随时从任何一个指定的地址写入（存入）或读出（取出）信息。它与ROM的最大区别是数据的易失性，即一旦断电所存储的数据将随之丢失。RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果。

SSD: Solid state disks。固态硬盘

pages:512 KB to 4 KB, Blocks: 32 to 128 pages

内存单位换算

1GB = 10^9Bytes

磁带记录密度：recording density

read/write heads move in unison from cylinder to cylinder:读/写头从一个柱面移动到另一个柱面。

数据从CPU到磁盘要经历的步骤：

seek time：搜索时间，在磁盘中从找到目标数据所在位置所需时间。

Rotational latency：旋转延迟，读/写头移动到对应区域所需时间。

transfer time： 数据从磁盘移动到上级存储设备所需时间。

磁盘控制器：磁盘控制器保持这磁盘中的扇区和逻辑块的映射。

备用空间：当磁盘中某一部分不能正常工作的时候，可以将数据写入备用空间，然后磁盘就可以正常运行了。这就是为什么我们购买磁盘时实际空间没有那么大的原因。

Cpu通过将命令、逻辑块号和目标内存地址写入与磁盘控制器关联的端口（地址）来启动isk读取

why? interrupt (zhongduanjizhi)

CPU可能正在执行数百万条指令，如果CPU等待数据从磁盘中出来，这将是一种可怕的浪费所以它所做的是，它向磁盘控制器发出请求，然后，当这个非常缓慢而费力的过程正在进行时CPU可以执行其他指令并做其他有用的工作。

固态硬盘是介于DRAM和旋转磁盘之间的一种存储介质。

闪存相当于DRAM的控制器。

but a page can only be written after the entire block has been erased

If you want to write to a page you have to find a block somewhere that’s been erased.
SSD : Solid State Disk

Qualitative Estimates of Locality

局部代码质量评估

int sum_array_cols( int a[M][N])
{
 int i, j, sum = 0;
  for (j = 0; j < N; j++)
      for (i = 0; i < M; i++)
          sum += a[i][j];
   return sum;
}
// 非常糟糕的例子，跳跃式访问空间
1
2
3
4
5
6
7
8
9

int sum_array_cols( int a[M][N])
{
 int i, j, sum = 0;
  for (j = 0; j < M; j++)
      for (i = 0; i < N; i++)
          sum += a[i][j];
   return sum;
}
// 最优累加数组元素的方法
1
2
3
4
5
6
7
8
9

你最好使步长为1的访问模式

int sum_array_3d(int a [M][N][N])
{
    int i,j,k, sum = 0;
    
    for (i = 0;i < M; i++)
        for(j = 0; j < N; j++)
            for(k = 0; k < N; k++)
                sum += a[i][j][k];
    return sum;
}
/// 最优访问三位数组的方式
1
2
3
4
5
6
7
8
9
10
11

内存的层级结构

存储器层次结构中的每一层都包含下一个较低级别层次所检索的额数据。

缓存是一个更小更快的存储设备，充当更慢的设备中的数据的暂存区域。一旦访问数据，就不会再在磁盘上访问他，而是在缓存中，这样速度可以快很多。

缓存系统非常强大，它出现在现代计算机系统的所有部分中。

由于局部性原理，程序倾向于访问存储在较高层的数据。由于我们不经常访问第K+1层数据，因此我们可以使用更便宜且更慢的存储设备。

层次结构创建了一个大型存储池。

区分缓存命中和缓存脱靶

缓存脱靶的几种类型：1. cold miss 2. compulsory-miss,出现这种情况是因为告诉缓存是空的，因此当我们读取数据时，自然会脱靶。

把缓存慢慢填满，增加命中概率。这称为缓存的热身。

3.Capacity miss,出现这种情况的原因是告诉缓存的大小有限，如果索取过多的数据会导致脱靶

明白了过小的内存条会导致 Capcacity miss 经常出现，这加重啦CPU的负担。程序的时间局部性是核心。

高速缓存中不断被程序访问的块称之为 工作集 working set, 工作集是会改变的，当你的程序冲一个循环执行到另一个循环，从一个函数到另一个函数时。当你的工作集超过你的缓存大小时就会出现Capacity miss

4. conflict miss冲突未命中，出现这种情况的原因是对于块号为i的块，我们只能把它放在缓存的I mod 4 处。

注意：每次拷贝新的块到缓存时都会导致其他的块被驱逐。
TLB : translation lookaside buffer是一个在虚拟内存中使用的缓存

CPU 和 存储器设备之间存在着访问速度的巨大差异，而且在不断扩大。

*The Speed gap between CPU, memory, and mass storage continues to widen.

高速缓存存储器

ROM:Read Only memory，一般用作BIOS的载体，用于实现基本的I/O，是系统中非常重要的部分，焊接在主板中不可拆卸。

BIOS:Basic Input Output System

随机存取存储器（英语：Random Access Memory，缩写：RAM），也叫主存，是与CPU直接交换数据的内部存储器。它可以随时读写（刷新时除外），而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储介质。RAM工作时可以随时从任何一个指定的地址写入（存入）或读出（取出）信息。它与ROM的最大区别是数据的易失性，即一旦断电所存储的数据将随之丢失。RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果。

SSD: Solid state disks。固态硬盘

pages:512 KB to 4 KB, Blocks: 32 to 128 pages

内存单位换算

1GB = 10^9Bytes

磁带记录密度：recording density

read/write heads move in unison from cylinder to cylinder:读/写头从一个柱面移动到另一个柱面。

数据从CPU到磁盘要经历的步骤：

seek time：搜索时间，在磁盘中从找到目标数据所在位置所需时间。

Rotational latency：旋转延迟，读/写头移动到对应区域所需时间。

transfer time： 数据从磁盘移动到上级存储设备所需时间。

磁盘控制器：磁盘控制器保持这磁盘中的扇区和逻辑块的映射。

备用空间：当磁盘中某一部分不能正常工作的时候，可以将数据写入备用空间，然后磁盘就可以正常运行了。这就是为什么我们购买磁盘时实际空间没有那么大的原因。

Cpu通过将命令、逻辑块号和目标内存地址写入与磁盘控制器关联的端口（地址）来启动isk读取

why? interrupt (zhongduanjizhi)

CPU可能正在执行数百万条指令，如果CPU等待数据从磁盘中出来，这将是一种可怕的浪费所以它所做的是，它向磁盘控制器发出请求，然后，当这个非常缓慢而费力的过程正在进行时CPU可以执行其他指令并做其他有用的工作。

固态硬盘是介于DRAM和旋转磁盘之间的一种存储介质。

闪存相当于DRAM的控制器。

but a page can only be written after the entire block has been erased

If you want to write to a page you have to find a block somewhere that’s been erased.
SSD : Solid State Disk

Qualitative Estimates of Locality

局部代码质量评估

int sum_array_cols( int a[M][N])
{
 int i, j, sum = 0;
  for (j = 0; j < N; j++)
      for (i = 0; i < M; i++)
          sum += a[i][j];
   return sum;
}
// 非常糟糕的例子，跳跃式访问空间
1
2
3
4
5
6
7
8
9

int sum_array_cols( int a[M][N])
{
 int i, j, sum = 0;
  for (j = 0; j < M; j++)
      for (i = 0; i < N; i++)
          sum += a[i][j];
   return sum;
}
// 最优累加数组元素的方法
1
2
3
4
5
6
7
8
9

你最好使步长为1的访问模式

int sum_array_3d(int a [M][N][N])
{
    int i,j,k, sum = 0;
    
    for (i = 0;i < M; i++)
        for(j = 0; j < N; j++)
            for(k = 0; k < N; k++)
                sum += a[i][j][k];
    return sum;
}
/// 最优访问三位数组的方式
1
2
3
4
5
6
7
8
9
10
11

内存的层级结构

截图：内存层级结构金字塔图

存储器层次结构中的每一层都包含下一个较低级别层次所检索的额数据。

缓存是一个更小更快的存储设备，充当更慢的设备中的数据的暂存区域。一旦访问数据，就不会再在磁盘上访问他，而是在缓存中，这样速度可以快很多。

缓存系统非常强大，它出现在现代计算机系统的所有部分中。

由于局部性原理，程序倾向于访问存储在较高层的数据。由于我们不经常访问第K+1层数据，因此我们可以使用更便宜且更慢的存储设备。

层次结构创建了一个大型存储池。

区分缓存命中和缓存脱靶

缓存脱靶的几种类型：1. cold miss 2. compulsory-miss,出现这种情况是因为告诉缓存是空的，因此当我们读取数据时，自然会脱靶。

把缓存慢慢填满，增加命中概率。这称为缓存的热身。

3.Capacity miss,出现这种情况的原因是告诉缓存的大小有限，如果索取过多的数据会导致脱靶

明白了过小的内存条会导致 Capcacity miss 经常出现，这加重啦CPU的负担。程序的时间局部性是核心。

高速缓存中不断被程序访问的块称之为 工作集 working set, 工作集是会改变的，当你的程序冲一个循环执行到另一个循环，从一个函数到另一个函数时。当你的工作集超过你的缓存大小时就会出现Capacity miss我的机器现在是32-bits的，因此如果移位数量大于32位会出现

[-Wshift-count-overflow]

的错误。

要注意的是移位运算符的优先级很低，甚至比加减法还低。

奇怪的是，我的机器在移位运算时得出的推断是32-bits的，但是在表示整数的最大值时确实以64-bits来进行的，在我的机器上一个long 型数据能够表示的最大整数是 9223372036854775807

C默认数字是有符号的。

This picture show how to convert a set of binary data to

Unsigned data(Nonnegative)

Example:

位数为W的二进制数的最值

从零到一串二进制数的最值之间，该值是和二进制数一一对应的。eg: 15 = [1,1,1,1]

Binary to two’complement 二进制转换为补码运算公式

Eg:

关于权重的解释与公式的简单应用

有一个不可避免的疑问：如何知道一串二进制码表示的究竟是Unsigned还是Tow’Complement？？？

下图展示了针对不同字长，几个重要数字的位模式。

几组重要公式

补码的最小值的绝对值要比补码的最大值大1

这是因为补码的最小值一定是一个负数，而补码的最大值是一个非负数，零是非负数比如：
一串长度为4的二进制数[1 1 1 1]，我们求它补码的最小值：

我们接着来求补码的最大值

求得补码的最大值是 7.

二进制与十六进制快速转换公式

n = i + 4j
其中n为指数，0 <= i <= 3,j为十六进制0的个数。当i = 0是x开头为1，i = 1时，x开头为2，i = 2时，x开头为4。i = 3时，x开头为8。
例子：x = 2048 = 2^11,11 = 3 + 4*2,因此十六进制数字为0x800

让我们来直接的观察

[1 1 1 1 ] 无符号数：[0 1 1 1 ]UMax
1 + 2 + 4-----------------------Sum == 7
[1 1 1 1 ]补码（有符号数）：[1 0 0 0 0 ]TMin
-8 + 0 + 0 + 0= -8------------Sum = -8

对于一串二进制数[1 1 1 1 ]它的无符号最大值是[ 0 1 1 1 ] 它的补码的最小值是[ 1 0 0 0 ]。

此处仍需细心研究……

在C中，无符号的乘法运算和补码的乘法运算虽然得到的二进制数不同，截断后的乘积的位级表示都是相同的，见下表：

其实也很简单，看完了课，读完了书，做一些题，看看自己那些做的很好，哪些做的不行，慢慢修正，这就是进步。

几组重要公式：

1. 二进制转换为补码
1

2. 二进制转换为无符号数

3.Unsigned 最大值

4.补码的最小值

5.补码的最大值

6.二进制转换为反码

7. 二进制转换为原码

如何扩展一个数字的位的表示，见下图：

C不同数据类型在32-bits机器和64-bits机器上范围：

补码、无符号数在各种字长的机器上的取值范围

浮点数的加减法溢出实例

// 浮点数不支持结合律
//
#include "stdio.h"

int main()
{
	long long value = 1e10;
	long long int value1 = 3.14;
	printf("%lld",(value1 + value)-value);
	return 0;

// result: -9223372036854775808 == 64-bits 最小long long int 
1
2
3
4
5
6
7
8
9
10
11
12

//
#include "stdio.h"
// float 为小数分配23 bits而，int 占据32bits，因此转换会导致精度丢失
int main()
{
	int value = 2147483647;
	value = (int)(float)value;
	printf("%d",value);
	printf("\nHello,world");
	return 0;
// result:-2147483648
1
2
3
4
5
6
7
8
9
10
11

#include "stdio.h"
// double 为小数分配53bits 而int 占据32bits因此不会导致精度丢失
int main()
{
	int value = 2147483647;
	value = (int)(double)value;
	printf("%d",value);
	printf("\nHello,world");
	return 0;
// result:2147483647
1
2
3
4
5
6
7
8
9
10

————————————————————————————————————————————————————————————————————————————————————

关于浮点数非常重要的是：浮点数的符号是单独存储的，因此符号具有单调性，不存在负负得正，浮点数的溢出会往无穷方向发展而不是负极得正。浮点数运算可以交换运算顺序，但是并不能按照数学原理随意添加括号。

浮点数的存储方式

单精度浮点数存储

双精度浮点数存储

Intel 扩展精度存储（仅限Intel处理器）

浮点数的几组重要公式

求指数

求偏移量

参数说明

value 为十进制下的数值，S单独存储符号的位，M尾数介于1.0-2.0之间，E指数，bias偏移量，即小数点后有多少位。Exp是Exponent 指数。frac 尾数，即小数位的二进制串。k为Exp位的数量，具体使用方法见下图。

有一个重要问题：e= 1 - bias, 而Bias = 2^k - 1 ，也就是说知道e和Bias的前提是知道存储指数的位数，那怎么确定这个位数呢？下图给的例子也只是4-bits的例子

猜测上述问题答案是：下图中的例子只是为了方便理解，在实际中exp的位数是固定的，8bits或者是11bits(单精度与双精度)

浮点数公式运用实例

浮点数值的分布图

几组“有趣”的数(doge)

精通细节是理解更深和更基本改变的先决条件。“我理解了一般规格，不愿意劳神去学习细节！”这实际上实在自欺欺人。花时间去研究示例，并对照答案来进行检验，是非常关键的。

关于溢出

溢出是整数、浮点数的常见话题。溢出的底层原理是：有限数量的位不能满足无限膨胀的数字的要求，多出来的不能够被表示的数字就是发生了溢出现象。

reading question：

计算机有哪几种不同的二进制表示形式？？
char* 使用全字长
什么是掩码运算？？
整数字符扩充和字符截断还需要重点关注
第二章节的习题需要做完。

用Exclusive-Or 实现变量值的交换,挺有意的……

int swap(int x, int y)
{
	x = x^y;
	y = x^y;
	x = x^y;
	return 1;
}
// this program has no performance advantage to this of swapping
1
2
3
4
5
6
7
8

gdb是一个非常强大的调试程序。你可以单步检查程序并对其中的程序进行一些操作。如果这个程序有对应的源代码，那么gdb会调用源代码来进行调试，不过没有也行。在gdb中可以进行反汇编。

objdump是一个重要的反汇编器。

Function swap:C code && Assembly code

小伙伴们大家好呀!!今天是 2022.8.28 今天继续深入理解计算机系统！！，今天学习的是：Machine level program, 主要学的是 基本的Intel x86系列汇编指令，但是并不要求会写汇编，只需要能够理解汇编就行啦！！ 虽然可能理解都费劲吧

Intel x86 指令 leaq

猜测： Src 是地址，也就是括号里可进行值的计算。 Dst 是最终要赋值的寄存器。搭配上移位运算简直简直了！！

long m12(long x)
{
return x*12;
}
1
2
3
4

汇编代码：

leaq (%rdi, %rdi, 2) , %rdx                           #%rdx = 3%rdi
salq $2, %rax                                         #%rax = 4%rax = 4*3%rdi = 12%rdi
1
2

---

---

C数据类型在IA32中的大小

C各数据类型：IA32与x86-64的比较

控制

条件码

CF: 用于检查无符号操作数的溢出
ZF: 最近得出的结果为0
SF: 最近的操作得出的结果为负数
OF: 补码溢出
LeaL指令分明只是用于简单的算术操作。这段话挺让人困惑：
加载有效地址 （load effective address）指令leal 实际上是movl指令的变形。他的指令形式是从存储器读取数据到寄存器，但实际上他根本就没有引用存储器。它的第一个操作数看上去是一个存储器引用，但该指令并不是从指定的位置读入数据，而是将有效地址写入到目的操作数。另外它还可以简洁地描述普通的算数操作。编译器经常发现一些Leal的灵活用法，根本与有效地址计算无关。目的操作数必须是一个寄存器。

什么是有效地址

从运行实体（指进程/线程/中断处理器/内核组件/）的角度来说，有效地址就是一个可以用于指定那个内存位置可以用来执行存取操作的值。·
个人理解：有效地址始终是地址，这就说明了Leal始终进行的是取址运算，而不是从指定的内存位置读取数据的运算，Leal的最终结果是将计算得到的地址交给某个寄存器也可以说leal用于生成一个指针。

以下内容亟待整理

Machine-Level Programming : Procedures

基于x86 硬件，
ABI：Application Binary Interface,应用程序二进制接口，用于规定寄存器的惯常用法。

在一个函数内部如何将控制递给另一个函数？

通过使用call指令，call指令会首先把返回地址入栈，并跳转到被调用过程的起始处。当callee进程被处理完之后，%rip 会从栈中弹出原先的返回地址，这样便完成了从主进程到父进程的一个完整流程。

Stack 不是什么特殊的内存，它只不过是普通内存的一个区域。

对于汇编层面的程序员而言，内存只是一个巨大的字节数组。

在这个巨大数组的某个地方，我们发现了stack程序用栈来管理过程调用与返回的状态，在栈中，程序传递潜在信息、控制信息和数据，并分配本地数据。栈能够实现这些功能的原因在于栈符合过程调用和返回的整个想法的本质：先进后出原则。

需要注意的是：幻灯片中的栈是反方向的，栈顶和栈底的方向反了

利用pop弹出数据后，数据并没有被魔法般的抹去，而是继续存留在内存中，只不过被栈所忽视了。

小技巧

在汇编中看不到指令所在的地址，所以有时必须使用反汇编来查看指令所在地址。

call
ret
these tow just do the control part of a procedure.

%rip 程序计数器， Instruction pointer

函数的参数如何传递？
按照使用惯例，一个函数的前留个参数会使用寄存器，从第七个开始将使用栈来传递。

如何确保被调用的函数返回到正确的位置上？

call指令在启动时会把返回地址入栈到栈帧的上面，这样当进程结束后，栈定便会回到返回地址，并将这个地址传个 %rip，这样便能保证程序会到正确的位置上。

passing data

编译器是怎么知道如何将栈恢复到原来的位置的？

%rax 用于函数的返回值。

前6个参数要求使用特定的寄存器。此处的参数必须是整数或者是指针类型。浮点型参数室友另外一组单独的寄存器来传递的。

如果函数的参数超过了6个，那么多于的参数将会被放入栈上的内存中。

基本上代码能运行是基于这样的假设：无论什么参数都按列出的顺序被传递给这一系列寄存器。

在64-bits机器上，汇编指令的push 、pop、ret、等都是基于8字节的，所以movl等双字操作会出错。

stack frame：用于辅助理解本地变量。为单个过程分配的那部分栈称为栈帧。栈的思想和过程调用以及返回的思想完全吻合。

stack frame 栈帧结构图。一个栈帧以%ebp开头，以%esp结尾。%esp作为栈顶常常变动，但是%ebp却不经常运动。有时%ebp不是必须存在的，它也可以作为Callee-saved 寄存器。

控制转移指令

控制指令

call 指令和ret 指令使用示意图

解释：

1. 执行 call 时有两个动作：1入栈call指令的下一个指令的地址用于返回。2跳转到call指令所指内容
2. 执行 call 后有两个动作：1pop栈顶用于返回到主程序 2把栈恢复原貌

我们把栈上用于特定call 的每个内存块称为栈帧

so each block we use for a particular call then is called the stack frame

%rbp ： base pointer，有时用于开启一个栈帧

栈与递归

All the sort of infrastructure required to support recursion is built into this whole stack discipline

递归所需要的所有基础结构都由栈的原则所保证。

下面是一个对照例子

递归部分的内容亟待整理（haha）

当一个寄存器以 e开头时，它会将 高32位设置为0

leaq 的本职工作是创建指针。

leaq 不会内存引用处读取数据，而是直接将地址存储给目标寄寄存器

sub 是为栈分配空间，add 是为栈减小空间。

ret指令将始终采用栈指针指向的地址并将它作为返回地址。

术语： caller调用函数的人、 callee被调用的人

caller saves temporary values in its frame befor the call

callee saves temporary values in its frame before using
caller resotres them before returning to caller

寄存器使用惯例

如果特定函数想要更改某寄存器的值，他需要做的是先将值存储起来，然后将它放入栈中，在该函数被终结前把它恢复到初始状态。如果你不适用帧指针，则可以把%rbp视为 callee 保存的寄存器。 每个程序都会以这种原则处理%rbx， 即修改它之前先把它的值暂时存储在栈上，之后在从栈中恢复。

x86系列寄存器用法：

注：在以上寄存器中，有6个 argument 寄存器专门用来存储函数参数，但是当函数参数多于6个时，从第7个开始的参数会被入栈。

x86-64 的栈

Machine-Level programming : Data

在机器代码里是没有数组这一概念的，而是将其视为字节的集合。这些字节的集合是在连续位置上存储的。结构也是如此。它也是作为字节集合来分配的。

C编译器的工作就是生成适当的代码来分配该内存。（应该是根据方括号中的数字）

数组：数组的大小等于元素个数乘以元素类型大小

对于单目运算符，——或者++来说是不能直接操纵数组的头指针的。因为根据声明，头指针是一个常量。

C语言没有数组下标越界检查机制，因此你可以为数组提供负值，但是得出的是未定义的值。

针对指针的加法运算，只能是一个指针加上一个常规的整数。

两个指针可以相减，但是不能相加。

相加会出错

test.c:9:5: error: invalid operands to binary + (have ‘int *’ and ‘int *’)
    9 |  p1 += p2;
      |     ^~

相减会警告

test.c:9:5: warning: assignment to ‘int *’ from ‘long int’ makes pointer from integer without a cast [-Wint-conversion]
    9 |  p1 -= p2;
      |     ^~

Val + i 会被缩放成 x + 4i (需要结合ppt来看此处)

不要在程序里任意洒放任意常数值

使用#define 来定义常值，并给出一些有意的名称和一些文档说明。

如果你要创建复杂的数据结构，那么使用typedef是一个非常好的想法，我强烈建议你把它分解为类型定义，因为C中的声明符号很快就会变得相当费解。

#include ZLEN 5
typedef int zip_dig[ZLEN];
zip_dig cmu = {1,5,2,1,3};
zip_dig mit = {0,2,1,3,9};
zip_dig ucb = {9,4,7,2,0};
zip_dig set = {cmu, mit, ucb};
1
2
3
4
5
6

在上面的代码中，首先使用了typedef定义了包含五个元素的数组，等同于封装了一个数据类型。它说明了被定义的数据必须有包含5个元素。

#include ZLEN 5
#include LEN 4
typedef int zip_dig[ZLEN];
zip_dig pgh[LEN] = {
	{1,2,3,4,5},
	{1,2,3,4,5},
	{1,2,3,4,5},
	{1,2,3,4,5},
}
// 定义了一个二维数组
1
2
3
4
5
6
7
8
9
10

你会在C语言中看到指令，机器代码和构造之间相当密切的关系。

指针运算和C语言的全部想法是C语言真的是那些长期从事汇编代码的人所构思的，他们在想：我如何让它看起来像一种高级语言。但又在一种变成语言里保持所有的灵活性以及我所学会的在汇编代码里玩的所有技巧。使指针运算使得C语言“看起来像”一种高级语言。

在C语言里你会看到指令，机器代码，和构造之间相当密切的联系。

整个++和+= 其实就是 INC 运算和 各种 mov sub add lea mul 等运算的表现

C语言中数组和指针之间的真正区别是什么？

当你在C中声明一个数组时，你既在分配空间，正在为它分配某个位置的空间，同时你也正在创建一个允许在指针运算使用的数组名称。

而当你只是声明一个指针时，你所分配的只是指针本身的空间，而没有给他指向的任何东西分配空间。
阅读K&R中关于如何读C语言中的指针和声明的那一章节

是不是把二位数组的行看成了一个指针，而把列的成为被指针指向的内容。

Nested array row access : 嵌套数组行访问

嵌套数组行开始地址 A + i*(C*K) 即数组首地址加上行数乘以每行所占字节数。

嵌套数组元素地址：A + i*(CK) + jK = A + (i*C + j)*K.A是数组首地址，i是行号，C是类型大小，K是每行元素个数，j 是列号比如phg[1][2], A = phg, i = 1, C = sizeof(int), K = 5, j = 2

Nested Array- C

#include "stdio.h"
#define ZLEN 5
#define LEN 4
typedef int zip_dig[ZLEN];
zip_dig phg[LEN] = {
	{1,2,3,4,5},
	{6,7,8,9,10},
	{11,12,13,14,15},
	{16,17,18,19,20}
};
int main()
{
	return phg[2][1] + phg[1][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Nested Array- Assembly

main:
.LFB23:
	.cfi_startproc
	endbr64
	movl	24+phg(%rip), %eax # %rip + 4*5*1 + 4*i = phg(%rip) + 24, phg[1][1]
	addl	44+phg(%rip), %eax # %rip + 4*5*2 + 4*1 = phg(%rip) + 48, phg[2][1]
	ret
	.cfi_endproc
1
2
3
4
5
6
7
8

结构体

如果我为struct 的所有不同数组元素字段引入其中一个结构，然后编译器将跟踪每个字段的起始位置，然后生成适当的相对结构体地址的字节偏移。所以说对结构本身的内存引用将是结构的起始地址。

Data align

实际上，当一个结构体被分配内存，编译器实际上会在分配空间时，在数据结构中插入一些空白的不被使用的字节。这么做只是为了对其 alignment.基本数据类型需要K个字节时，地址必须时K的倍数。

对齐的原则

实际上现在的大多数机器，一次读取大约64个字节，或者这取决于硬件中的各种宽度。一般来说，如果因为没有个对齐的地址，一个特定的数据跨越了两个块之间的边界，可能会让一些硬件甚至有可能让操作系统采取一些额外的步骤来处理。因此，数据对齐时处于效率原因。其实就是让一类的数据独立开始一个块，而不是这一块一点，那一块一点。

对齐的方式取决于结构中长度最大的元素吗？

是的，取决于元素原始数据类型的最大值，比如一个结构体中有一个int,一个long,一个short,那么对齐应该按照long大小即8个字节来进行。

对齐会额外消耗内存，有什么办法尽量节省内存的使用吗？

有的，例子在ppt上，把最大的case 放在开头，在一次放更小的元素可以减小内存的浪费。

是任何数据类型都要求对齐吗？

不是的，对齐仅仅指的是最原始的数据类型，不包括聚合数据类型（即你自己创造的类型）

一些练习题（已解决）

(注：相同的数据类型如果不够对齐要求应该放到一起，当然前提是他们本身就临近。第一个字符总是不偏移。)

Advanced Topics+

1.当运行x86-64 的程序时内存时如何组织的。

2.安全漏洞，即缓冲区溢出

3.Unions

现在64位机器会限制只使用47位地址，地址范围会随着科技进步而越来越大

Limit: 栈被限制大小为8192kb

通过gdb调试工具我们可以同时执行代码和查看反汇编语句

看到7和很多f就知道这是栈的地址

看到很多零后面是4就知道这是代码运行的地方。

重要任务：学习使用gdb

字符串结尾部分会被加上一个字节的 00 表示字符串结束。

代码注入攻击

使用scanf 时要注意 %s, 此时最好在%前面加上数字来限定读取的字节数量。

提高系统安全性的措施

ASLR：栈随机化，地址空间布局随机化

Malloc 分配的地址具有随机性

Canary：金丝雀

Stack Canaries can help

矿井工人使用金丝雀来检测矿井下的甲烷含量。

一般来说，我们使用GCC的时候都会启动栈保护机制

黑客一般攻击手段

1.面向返回编程

2.Gadget

3.注入式攻击

结构体为所有的域分配足够的空间，而联合体会使用占用空间最大的域的大小来分配内存。

##它假设你只会同时使用一个域，如果你同时使用多个域，那么就会出问题。他不是用来处理多个值的，或者说他只是一种通过别名来引用不同的内存的方式。

程序性能优化

本文用于简要记录CSAPP课程

在你选择了合适的算法并且没有错误的前提下：

影响函数性能的主要是：1.内存别名 2.对同一函数的多次调用

#define int data_t
#define int size_t
typedef struct 
{
	int len;
	data_t data[len];
}val;
int get_element(*val v,size_t idx,data_t* rtn)
{
	if(idx >= v->len) return 0;
	*rtn = v->data[idx];
	return 1;
}
// 使用这种方式可以避免数组溢出

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

#define OP +
#define IDENT 0
or
#define OP *
#define IDENT 1
// 本函数用于计算一个数组中所有元素的和或者是积
void combine(val v,data_t* dest)
{
	long int i;
	*dest = IDENT;
	int len = get_length(v);
	for(i = 0; i < len;i++)
	{
	data_t val;
	get_element(&v,i, &val);
	*dest = *dest OP val;
}
}
//使用这种方式可以轻松获得更多运算：加，乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Optimize version
data_t = IDENT;
int len= get_length(v);
data_t * d = get_array_start(v);
for (i = 0; i < len; i++)
{
	t = t OP d[i];
}
*dest = t;
1
2
3
4
5
6
7
8
9

我们不能控制CPU以怎样的频率运行，但是我们可以控制程序总不同的计算部分使用了多少个时钟周期

超标量乱序执行技术，以加快CPU运行速度

指令级并行

一个寄存器相当于一个内存符号

你的机器有足够多的资源同时进行多项操作，但这需要你以某种方式建构你的程序，才能同时使用这些资源。

超标量指令处理器

流水线操作思想，把程序的执行划分为多个独立的阶段。（充分利用有限的CPU资源）

FP：浮点数
latency：

对于那些存在紧密资源联系的代码，流水线处理器无法做到加速处理。

loop unrolling 循环展开

循环展开的基本思想是在循环中同时计算多个值而非一个。

延迟界限是指：在一系列操作必须严格顺序执行时，执行一条指令所要花费的全部时间。

吞吐量限制：由于硬件的数量和性能，基于功能单元的原始计算能力。

CPE: Cycle per Elememt
%xmm寄存器

使用寄存器的低4位或者低8位

矢量加法指令，其中一条矢量加法指令具有执行八次单精度浮点加法的效果或者四次双精度浮点加法。你可以在三个始终周期内并行进行八次浮点流水线乘法。我们最多能接近矢量吞吐量界限。

充分利用csapp网页上提供的资源

1. 注意隐藏的低效率算法
2. 编写编译器友好型代码：注意块的优化：函数调用和内存引用
3. 仔细检查最深层次的代码
   4.开发指令级并行程序
   5.避免不可预测的分支
   6.使代码缓存更加友好。

存储器层次结构

存储器只分为：RAM（随机访问存储器） 和 ROM（只读存储器） 两大类。

内存名词定义：

RAM：Random-Access Memory (RAM)

1.所谓“随机存取”，指的是当存储器中的数据被读取或写入时，所需要的时间与这段信息所在的位置或所写入的位置无关。相对的，读取或写入顺序访问（Sequential Access）存储设备中的信息时，其所需要的时间与位置就会有关系。它主要用来存放操作系统、各种应用程序、数据等。

2.当电源关闭时，RAM不能保留数据。如果需要保存数据，就必须把它们写入一个长期的存储设备中（例如硬盘）。 [3]
RAM的工作特点是通电后，随时可在任意位置单元存取数据信息，断电后内部信息也随之消失。

DRAM：Dynamic Random Access Memory,主存储器和与图形卡相关的帧缓冲区中使用的主力,其实就是内存条。按照自己预算可以拆卸、更新。

ROM:Read Only memory，一般用作BIOS的载体，用于实现基本的I/O，是系统中非常重要的部分，焊接在主板中不可拆卸。

BIOS:Basic Input Output System

随机存取存储器（英语：Random Access Memory，缩写：RAM），也叫主存，是与CPU直接交换数据的内部存储器。它可以随时读写（刷新时除外），而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储介质。RAM工作时可以随时从任何一个指定的地址写入（存入）或读出（取出）信息。它与ROM的最大区别是数据的易失性，即一旦断电所存储的数据将随之丢失。RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果。

SSD: Solid state disks。固态硬盘

pages:512 KB to 4 KB, Blocks: 32 to 128 pages

内存单位换算

1GB = 10^9Bytes

磁带记录密度：recording density

read/write heads move in unison from cylinder to cylinder:读/写头从一个柱面移动到另一个柱面。

数据从CPU到磁盘要经历的步骤：

seek time：搜索时间，在磁盘中从找到目标数据所在位置所需时间。

Rotational latency：旋转延迟，读/写头移动到对应区域所需时间。

transfer time： 数据从磁盘移动到上级存储设备所需时间。

磁盘控制器：磁盘控制器保持这磁盘中的扇区和逻辑块的映射。

备用空间：当磁盘中某一部分不能正常工作的时候，可以将数据写入备用空间，然后磁盘就可以正常运行了。这就是为什么我们购买磁盘时实际空间没有那么大的原因。

Cpu通过将命令、逻辑块号和目标内存地址写入与磁盘控制器关联的端口（地址）来启动isk读取

why? interrupt (zhongduanjizhi)

CPU可能正在执行数百万条指令，如果CPU等待数据从磁盘中出来，这将是一种可怕的浪费所以它所做的是，它向磁盘控制器发出请求，然后，当这个非常缓慢而费力的过程正在进行时CPU可以执行其他指令并做其他有用的工作。

固态硬盘是介于DRAM和旋转磁盘之间的一种存储介质。

闪存相当于DRAM的控制器。

but a page can only be written after the entire block has been erased

If you want to write to a page you have to find a block somewhere that’s been erased.
SSD : Solid State Disk

Qualitative Estimates of Locality

局部代码质量评估

int sum_array_cols( int a[M][N])
{
 int i, j, sum = 0;
  for (j = 0; j < N; j++)
      for (i = 0; i < M; i++)
          sum += a[i][j];
   return sum;
}
// 非常糟糕的例子，跳跃式访问空间
1
2
3
4
5
6
7
8
9

int sum_array_cols( int a[M][N])
{
 int i, j, sum = 0;
  for (j = 0; j < M; j++)
      for (i = 0; i < N; i++)
          sum += a[i][j];
   return sum;
}
// 最优累加数组元素的方法
1
2
3
4
5
6
7
8
9

你最好使步长为1的访问模式

int sum_array_3d(int a [M][N][N])
{
    int i,j,k, sum = 0;
    
    for (i = 0;i < M; i++)
        for(j = 0; j < N; j++)
            for(k = 0; k < N; k++)
                sum += a[i][j][k];
    return sum;
}
/// 最优访问三位数组的方式
1
2
3
4
5
6
7
8
9
10
11

内存的层级结构

截图：内存层级结构金字塔图

存储器层次结构中的每一层都包含下一个较低级别层次所检索的额数据。

缓存是一个更小更快的存储设备，充当更慢的设备中的数据的暂存区域。一旦访问数据，就不会再在磁盘上访问他，而是在缓存中，这样速度可以快很多。

缓存系统非常强大，它出现在现代计算机系统的所有部分中。

由于局部性原理，程序倾向于访问存储在较高层的数据。由于我们不经常访问第K+1层数据，因此我们可以使用更便宜且更慢的存储设备。

层次结构创建了一个大型存储池。

区分缓存命中和缓存脱靶

缓存脱靶的几种类型：1. cold miss 2. compulsory-miss,出现这种情况是因为告诉缓存是空的，因此当我们读取数据时，自然会脱靶。

把缓存慢慢填满，增加命中概率。这称为缓存的热身。

3.Capacity miss,出现这种情况的原因是告诉缓存的大小有限，如果索取过多的数据会导致脱靶

明白了过小的内存条会导致 Capcacity miss 经常出现，这加重啦CPU的负担。程序的时间局部性是核心。

高速缓存中不断被程序访问的块称之为 工作集 working set, 工作集是会改变的，当你的程序冲一个循环执行到另一个循环，从一个函数到另一个函数时。当你的工作集超过你的缓存大小时就会出现Capacity miss

4. conflict miss冲突未命中，出现这种情况的原因是对于块号为i的块，我们只能把它放在缓存的I mod 4 处。

注意：每次拷贝新的块到缓存时都会导致其他的块被驱逐。
TLB : translation lookaside buffer是一个在虚拟内存中使用的缓存

CPU 和 存储器设备之间存在着访问速度的巨大差异，而且在不断扩大。

*The Speed gap between CPU, memory, and mass storage continues to widen.

高速缓存存储器

4. conflict miss冲突未命中，出现这种情况的原因是对于块号为i的块，我们只能把它放在缓存的I mod 4 处。

注意：每次拷贝新的块到缓存时都会导致其他的块被驱逐。
TLB : translation lookaside buffer是一个在虚拟内存中使用的缓存

CPU 和 存储器设备之间存在着访问速度的巨大差异，而且在不断扩大。

*The Speed gap between CPU, memory, and mass storage continues to widen.

高速缓存存储器