一、计算机系统漫游

1.1 信息就是位+上下文

C程序的生命从一个源程序（源文件）开始，程序通过编辑器创建保存为文本文件，本质上由0/1序列组成，8个一组（字节），每个字节表示一个文本字符。大部分都用ASCII字符。
系统中所有的信息都是一串bit，区分不同数据对象的唯一方法是读到这些数据时的上下文。不同上下文，相同序列可能表示一个整数、浮点、字符串或者机器指令。

1.2 编译

程序被其他程序翻译成不同的的格式。
C程序开始是一个高级C程序，能够被人读懂。然后为了程序运行，每条C语句会被其他程序转化为低级机器语言指令。然后按照可执行目标程序（executable object program）的格式打包。
在Unix上，这个工作由编译器驱动程序（compiler driver）完成：
gcc -o hello hello.c
过程：
点击查看【processon】
预处理阶段：预处理器根据字符#开头的命令，修改程序，如#include插入系统头文件代码，得到另一个C程序，.i扩展名。
编译阶段：hello.i翻译成hello.s，源程序翻译成汇编程序，此时还是文本程序，也就是说懂汇编的程序可以看懂。汇编语言程序每条语句以文本格式描述一条机器指令。不同高级语言由不同的编译器可以生成相同的汇编程序。
汇编阶段：hello.s翻译成hello.o，汇编程序翻译成机器指令，这些指令打包成为一种可重定位目标程序的格式，此时是二进制格式了。
链接阶段：链接源程序的.o文件和会被引用到的.o文件合并，得到一个可执行文件（可执行目标文件），executable object program。比如源程序用到printf函数，这个函数在编译器中的printf.o文件，已经编译好了的。

GNU项目
点击查看【processon】

1.4 系统硬件组成

总线bus

贯穿整个系统的电子管道，负责在各个部件之间传输字节信息。通常设计成传输定长的字节块（word，简称字），这个word的字节数就是常见系统参数，你的电脑是32位的还是64位的啊？

I/O设备

input/output输入输出设备，系统和外界联系的通道。上图系统4个I/O设备：
键盘、鼠标：用户输入
显示器：用户输出
磁盘驱动：长期存储数据和程序。
I/O设备都是一个控制器/适配器与IO总线相连，这两种的区别在于封装方式。
控制器：设备本身或者主板的芯片组，如键盘、鼠标，磁盘。
适配器：插在主板插槽上的卡，如网卡、显卡。

主存

临时存储设备，处理器执行程序时，存放程序和程序处理的数据。
物理上，是一个动态随机存取存储器（DRAM，dynamic random access memory）
逻辑上，是一个线性字节数组，每个字节有唯一地址，地址从0开始。

处理器

中央处理单元（CPU，central process unit），解析（执行）存储在主存中的指令。

PC（program counter）程序计数器，一个字大小的存储器，保存下一个指令的主存地址。处理每执行完一条指令后会更新PC，指向下一条指令。这个过程由指令集架构决定，

ALU，算数/逻辑单元，计算数据和地址值。
Register寄存器，小的存储设备。
加载：复制主存数据到寄存器中，一个字节或者一个字。
存储：与存储相反。
操作：把两个寄存器的内容复制给ALU，计算器后存储到另一个寄存器中。
跳转：从指令本身抽取一个字，复制到PC中。

hello程序执行过程
shell中输入hello，hello通过键盘IO，bus总线，存储到寄存器中，再由寄存器保存到主存中。
输入回车键，shell开始执行hello，通过DMA技术不经过CPU把磁盘中的hello程序直接加载到主存中。
处理器执行hello程序，将hello word复制到寄存器中，再从寄存器复制到显示设备，最终显示。

1.5 cache高速缓存

在主存上和磁盘上发生的数据复制，减慢程序执行。

cache有利于减少这些操作的发生。
特性一，局部性原理，存储局部区域的代码和数据。
特性二，容量不小，几万到几百万字节，相比较下，寄存器只有几百字节。
特性三，访问速度快，比寄存器慢一点，但是比主存快的多。

程序有访问局部区域代码和数据的趋势。cache通过局部性原理的特性保存近期可能处理的数据，这样就可以避免一些复制主存数据的操作，取而代之的是直接复制cache中的数据，大大提高了速度。

1.6 存储设备的层次结构

主要思想，上一层的存储器作为低一层存储器的高速缓存。

1.7 操作系统管理硬件

操作系统可以看成是应用程序和硬件之间的一层软件。
两个功能：对硬件的使用
方便用硬件，提供简单一致的机制来访问复杂且各异的硬件。
规范用硬件，提供规范机制防止硬件被应用程序滥用。
三个抽象：对硬件的抽象
文件：I/O设备的抽象。
虚拟内存：主存、磁盘等I/O设备的抽象。
进程：处理器、主存、磁盘等I/O设备的抽象，或者理解为对一个正在运行程序的抽象。

1.7.1进程

进程是操作系统对一个正在运行程序的抽象，计算机科学中最重要最成功的的概念。

并发运行，不同进程的指令交错执行。

大多数系统中，进程数一般多于运行它们的CPU个数。

一个CPU“同时执行”多个进程是通过CPU在进程间快速切换实现的，这种机制称为上下文切换。
**
上下文（context），操作系统保持跟踪进程运行的所有状态信息，包括PC、寄存器、主存内容。

上下文切换，即保存当前进程上下文，恢复新进程上下文，控制权转移给新进程，新进程从上次停止的地方开始。

上下文切换由操作系统内核（kernel）完成，内核是操作系统代码常驻内存的部分，它不是进程，是系统管理全部进程所用的代码和数据结构的集合，可以简单理解为常驻内存的数据。

应用程序执行system call指令，让内核执行被请求的操作，返回数据给应用程序。
如图：

1.7.2 线程

一个进程由多个成为线程的执行单元组成，这些线程运行在进程的上下文。

1.7.3 虚拟内存

为每个进程提供主存的抽象，让所有进程都访问一个相同主存（让它们都认为自己独占主存），这样的话，大大简化并统一了所有进程对主存的访问。
虚拟内存的地址空间叫虚拟地址空间，下面是Linux的虚拟地址空间：
请注意蓝色空间的意义。

代码和数据区（code and data）：所有进程的代码都是从同一固定地址开始，紧接着是C全局变量，直接按照源代码内容初始化，开始运行时就被指定了大小，顶部没有蓝色区域。
运行时堆heap：malloc、free标准库函数动态开辟内存
共享库：存放C标准库和数学库的代码和数据。
用户栈：位于地址空间顶部，编译器用它实现函数调用，可以动态扩展和收缩，每调用一个函数，栈就增长，函数返回，栈减少。
内核：存储内核代码和数据，程序不可以读写或直接调用。
虚拟内存基本思想：把一个进程虚拟内存的内容存储在磁盘上，然后用主存作为高速缓存。

1.7.4 文件

字节序列，仅此而已。它是对I/O设备的抽象，即每个I/O设备，包括键盘，鼠标、显示器都是文件。

1.8 系统间利用网络通信

网络就是一个I/O设备，所以也就那样。

1.9 并发和并行

要计算机做的更多，要计算机做的更快。
并发concurrency，一个同时具有多个活动的系统。
并行parallelism，用并发来使用一个系统更快。
线程级并发

1.10 计算机中的抽象

虚拟机是对计算机的抽象，由IBM在1960年代提出，太牛逼了。
指令集架构是对处理器的抽象
虚拟内存是对正在运行的应用程序的存储器的抽象，包括内存和I/O

二、信息的表示和处理

2.1 信息的存储

大部分计算机，以字节作为可寻址的最小内存单位。
C语言中的指针指向的是虚拟地址。
每个程序对象可以视为一个字节块，每个程序是一个字节序列。

2.1.1 十六进制表示法

一个字节的值域为00~FF。
0xABCDEF，0XABCDEF，ABCDEF，abcdef都是合法的。

2.1.2 字数据大小

word的大小在前面讲过，由bus总线决定。假设字长为2bit则：
指针的数值大小是在0~2-1之间，虚拟地址空间大小为2个字节。
32位系统的虚拟地址空间为4G，64位的为16EB，非常巨大。

C标准本身对数据类型大小只确定了下界，没有确定上界，因为那个时候刚好是32位机器占主流，但64位机器开始不断出现的时候。
在ISO C99引入了一类数据类型，其数据大小是固定的，int32_t和int64_t，分别为4个字节和8个字节。
C标准不保证char是否是有符号。
程序对不同数据类型的确切大小不敏感是程序可移植性的体现。

2.1.3 寻址和字节顺序

大端法和小端法

内存高地址保存数据的高位值就是大端，反之小端。
助记，高对高则大，否则小。

关于大小端的争辩

带来的问题

大小端不同的机器之间网络数据交换，会导致字节顺序颠倒。

2.1.5 表示代码

不同机器上，相同代码编译后的二进制代码是不一样的。

2.1.6 布尔代数简介

把TRUE和FALSE编码为1和0，设计出的一种代数

2.1.7 C语言中的位级运算

C语言支持按位布尔运算，作用任何整形数据，
|、&、~、^

//交换x、y指针指向的值
void inplace_swap(int *x, int *y){
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}
//翻转数组
void reverse_array(int a[],int cnt){
    int first,last;
    for(first=0,last=cnt-1;first<last;first++,last--)
        inplace(&a[first],&a[last])
}

2.1.8 C中的逻辑运算

||、&&、！。
输出结果True或False
非0True，0False
逻辑运算符与位级运算符的区别，如果第一表达式可以确定结果则逻辑运算符不会计算后续表达式。

!(x ^ y) 等价于 x == y

2.1.9 C的位移运算

左移<<、右移>>

右移，最高位补位规则：
逻辑右移：最高位补0。
算术右移：最高位补位移前最高有效为的值。这有利于有符号整数的运算，保留最高位的符号位嘛。

C默认基本都是有符号算术右移，无符号逻辑右移。

Java规定，>>>算术右移，>>逻辑右移。

位移量超出范围的情况：
x>>k，k大于x的位数，也就是k>=logx时。
实际的位移量=k mod (logx)。
C中一般是这种情况，Java明确规定是这种情况。

2.2 整数表示

2.2.1 C整数数据类型

取值范围

int的标准是2字节非4字节：C标准制定那会儿主流机是16位，也就导致了int设置的最低标准是和short一样的。现在的机器，int都是4字节了。
32位的long是4字节，64位置是8字节，其他都一样。

2.2.2 无符号编码

2.2.3 补码编码

2.2.5 有符号数和无符号数

2.2.6 扩展一个数字的位表示

三、程序的机器级表示

汇编代码是机器代码的文本表示。

3.1 历史观点

Inter处理器，俗称x86。
8086：1978年，29K个晶体管，第一代单芯片，16bit处理器，
8088：8086变种，增加了8bit外部总线。IBM个人计算机心脏。
8087：1980年，浮点协处理器，45K个晶体管。建立了x86浮点模型，俗称x87。
80286：1982年，134K个晶体管，windows最初使用平台。
i386：1985年，275个晶体管，32位，全面支持Unix。
i486：1989，1.2M个晶体管，浮点单元集成到处理器芯片。
Pentium：1993年，3.1M个晶体管。
PentiumPro：1995年，5.5M个晶体管。
……

3.2程序编码

1 机器级代码

机器级编程两个重要抽象：指令集架构（ISA）和虚拟内存地址（VMA）。
前面已经学习了，ISA是对处理器的抽象，让程序认为处理器是一条一条按顺序执行程序的。VMA是对正在运行程序的存储器的抽象包括主存、磁盘I/O。

程序计数器

Program Counter，PC，x86-64中用%rip表示，表示下一条指令在内存中的地址。
gcc版本不同，产生的代码不同，GCC社区一直在跟进微处理器制造商，试图让GCC产生更有效的代码。

整数寄存器

16个命名的位置，每个存储64bit的值，存储地址或整数，一些用来保存临时数据如过程参数、局部变量，函数返回值。
1byte寄存器：al、bl、cl、dl，2位l结尾的
2byte寄存器：ax，bx，cx，dx，2位x结尾的
4byte寄存器：eax，ebx，ecx，edx，3位e开头的
8byte寄存器：rax，rbx，rcx，rdx，3位r开头的。

条件码寄存器

最近执行的算术/逻辑指令的状态信息，if/else语句。

向量寄存器

存放一个或多个整数/浮点值。

程序内存包含：
1、代码：可执行机器代码。
2、操作系统需要的信息。
3、用户分配的内存：malloc
4、管理过程调用和返回的运行时栈

示例：生成汇编代码

long mult2(long,long);
void multistore(long x, long y, long *dest){
    long t = mult2(x, y);
    *dest = t;
}
//linux> gcc -Og -S mstore.c    //-S 生成汇编代码，
//汇编代码如下：
multstore:
    pushq    %rbx    //将寄存器%rbx内容压栈
    movq    %rdx, %rbx
    call     mult2
    movq    %rax,(%rbx)
    popq    %rbx
    ret
linux> gcc -Og -c mstore.c    //编译并汇编，生成机器代码。
//其中有一段14字节的序列，十六进制表示如下：
//53 48 89 d3 e8 00 00 00 00 48 89 03 5b c3
//就是汇编代码对应的机器代码。

反汇编器可以通过机器代码生成汇编代码的文本。

linux> objdump -d mstore.o

下面是输出结果：

常用指令的Bytes（机器代码）字节数都比较小，不常用的就比较大。
指令设计规则：从某个给定位置开始，将字节解码成机器指令，如53，只有指令push %rbx的机器码是53值开头。
下面左边是代码文件，右边是反编译出的对应代码序列：

2 操作数指示符

操作数operand，三种类型：
立即数（immediate），$Imm，常数值，$后面接C格式整数，如$-577、$0x1F，
寄存器（register），r：寄存器a，R[r]：寄存器内容，R：寄存器数组，r：寄存器标识符。
内存引用，M[addr]：内存中addr起始b个字节值的引用。

3 数据传送指令：mov指令

mov S, D：S内容复制到D，
S：立即数，内存地址，寄存器地址；
D：内存地址，r开头的寄存器地址即64位的。
S <= D，**S和D不能同是内存地址。有的同学会想为啥不能S>D，比如把一个long复制给int，涉及到截断的时候，那该怎么办？这里用到了。高低位寄存器机制如下：
**
%al的内容就是%rax的低八位内容，即可实现截断。
b：byte，w：word，l：2 word，q：quad word，4word。

例子

int *i;
long *l;
*i = (int)*i;    //
int *i;
long *l;
*i = (int)*i;    //

mov b把%rax低1byte置为FF，movw把%rax低2byte位置为FFFF，movl同理同时高4byte位置为0。

错误案例

movb $0xF, (%ebx)：传送1byte，需是1byte寄存器，如%al、%bl。
movl %rax, (%rsp)：传送4byte，需要4byte寄存器，如%eax、%ebx，%rsp是64bit寄存器。
movw (%rax), 4(%rsp)：不能同是内存地址。
movb %al, %sl：没有寄存器%sl。
movq %rax, $0x123：D不能是立即数，需要是地址。
movl %eax, %rdx：传送4byte，需是32bit寄存器，如%ebx、%ecx，
movb %si, 8(%rbp)：%si是2byte寄存器，应该使用movw指令。

4 数据传送指令：movs

使用场景，比如char的整形复制给int，到了高位bit的扩展。

例子

5 汇编代码解读实战

//src_t、dest_t是typedef声明的数据类型
src_t *sp;    //sp 存储在 %rdi 64bit寄存器
dest_t *dp;    //dp 存储在 %rsi 64bit寄存器
*dp = (dest_t) *sp;    //对应的汇编代码应该是？

6 数据传送指令：pushq和popq

push %rbp等价于如下汇编代码：
subq $8, %rsp：%rsp值 - 8。
movq %rbp, (%rsp) ：8字节的%rbp的内容压栈。

popq %rax 等价于如下汇编代码：
movq (%rsp), %rax
addq $8, %rsp

下图是pushq %rax，popq %rdx的效果。

7 算术逻辑操作

例子

%rdx的值为x，leaq 7(%rdx , %rdx, 4), %rax，则%rax = 5x + 7。

leaq例子

移位操作例子

%cl = 0xFF时。
salb %cl, %rax：<< 7
salw %cl, %rax：<< 15
sall %cl, %rax：<< 31
salq %cl, %rax：<< 63

特殊算术操作

2个64bit数字的全128bit乘积以及整数除法的指令。
imulq、mulq、clto、idivq、divq。