CSAPP

Computer-Systems

2020-03-27 10:00:00 +0800

Computer Systems A Programmer’s Perspective

CSAPP

从程序员的角度学习计算机系统如何工作

学习的方法： do it，在真正的系统上解决具体的问题

文中代码GCC编译的C程序并在Linux系统上测试

概述

第一章，研究简单的程序的声明周期；介绍计算机系统的主要概念和主题；

第二章，计算机算数运算、补码、数学属性；

第三章，

第四章，

第五章，

第六章，

第七章

第一章，计算机系统漫游

如何优化C代码，以充分利用现代处理器和存储器系统的设计

编译器如何实现过程调用

如何避免缓冲区溢出

如何识别和避免链接时的错误

编写自己的Unix shell、自己的动态存储分配包

自己的web服务器

并非的希望和陷阱

#include <stdio.h>

int main() {
    printf("hello world\n");
    return 0;
}

• hello程序的声明周期，从被创建，在系统上运行，输出简单信息，终止；

1.1 信息就是位 + 上下文

• 源文件：编辑器创建并保存的文本文件
• 源程序：实际上就是一个比特序列，8bit位1byte
• ASCII, 每个字符有唯一的整数值，97a，65A
• 程序以字节序列的方式存储在文件中，每个字节有一个整数值，对应ASCII中的字符，代码中换行符\n，hello.c由ASCII字符构成的文件为文本文件，其他文件为二进制文件；

系统中的所有信息，磁盘文件，内存文件，用户数据，网络报文数据，都是一串比特表示；

区分数据对象的方式就是 “上下文”， 根据上下文确定当前的“字节序列”表示的时整数还是浮点还是机器指令

• 数字的机器表示方式，是对真值的有限近似值；

C 起源：C和C标准库，为Unix而设计，小而简单，为实践设计；

1.2 程序被其他程序翻译成不用格式 - 编译

• 每条C语句都需要被“其他程序”转化为一系列“机器语言”指令

• 指令按照一种称为“可执行目标程序”的格式打包，以二进制的形式存放，可执行目标文件

• Unix上的C “编译器驱动程序” gcc

  • 编译系统的编译过程简介

    hello.c	预处理器	hello.i	编译器	hello.s	汇编器	hello.o	链接器	hello
    源程序文本	cpp	修改了的源程序文本	ccl	汇编程序文本	as	可重定位目标程序二进制	ld	可执行目标程序二进制

  • 编译系统（compilation system）

    • 预处理器
    • 编译器
    • 汇编器
    • 链接器

  • 预处理阶段

    • 预处理器（cpp，c Preprocessor）
    • 从#include开始修改C程序，例如include导入系统头文件，预处理器会将头文件内容插到当前文本中；
    • 输出 .i 文件扩展名的文本文件

  • 编译阶段

    • 编译器（ccl, c compiler)

    • 将 .i 文本文件翻译为 .s 文本文件，包含汇编语言程序；

    • hello.s 包含mian函数的汇编语言，main以外的每条都以一种文本格式描述了一条低级机器语言指令

      汇编语言为不同的高级语言的不同的编译器提供了通用的输出语言；

  • 汇编阶段

    • 汇编器 Assembler （as）
    • 将hello.s 翻译成机器语言指令
    • 打包为“可重定位目标程序 （relocatable object program）的格式，将结果保存在hello.o中
    • hello.o 为二进制文件，包含main的指令编码

  • 连接阶段

    • 链接器 ld
    • C编译器提供了标准C库的预编译的文件，例如 printf函数，预编译目标文件为 printf.o
    • 链接器负责处理目标预编译文件 和 源程序 的合并；
    • 最终的得到的结果就是一个可执行文件，被加载到内存中，由系统执行

  GNU项目， GUN’s Not Unix

  GNU包含：EMACS编辑器，GCC编译器，GDB调试器，汇编器，链接器，处理二进制文件的工具和其他部件；

  支持C/C++/Java/Objective-C

1.3 编译系统何如工作

编译系统如何工作，带来的帮助

• 优化程序性能
  • 第三章，第五章，第六章
  • switch语句和一系列的if-else语句那个高效
  • 函数调用的开销多大
  • while循环和for循环哪个更有效
  • 指针引用和数据索引哪个更有效
  • 循环求和结果放在本地变量中比放在引用传参高效
  • 用括号优化算数表达式
• 理解链接时出现的错误
  • 第七章
  • 链接器导致的错误
  • 链接器无法解析一个引用
  • 静态变量和全局变量的区别
  • 不同C文件中定义同名的全局变量会发生什么
  • 静态库和动态库的区别
  • 命令行上排列库的顺序
• 避免安全漏洞
  • 缓冲区溢出
  • 第三章，堆栈原理，缓冲区溢出错误

1.4 处理器读取和解释存储在内存中的指令

• 在Unix系统中执行目标程序，在shell中输入名称执行
• shell会对不是内置命令的命令，当作可执行文件，并加载运行这个文件；等待程序终止将结果回显输出；

1.4.1 系统的硬件组成

典型系统的硬件组成

1. 总线

• 贯穿整个系统的一组电子管道，称为总线；

• 携带”信息字节“ 并负责在各个部件之间传递；

• 被设计为”定长的字节快“，字 word；

• 字中的字节数（字长）是一个基本的系统参数

  32位机器，字长4个字节

  64位机器，字长8个字节

2. I/O device

• 每个I/O设备都通过一个”硬件芯片组 控制器” 或者 “主板插槽卡 适配器” 与I/O总线相连；
• 功能都是用于I/O总线和I/O设备之间的信息传递；

3. 主存

• DRAM，动态随机存取存储器芯片组成的临时存储设备；用来存放程序和程序处理的数据
• 逻辑上是“一维线性的字节数组”
• 每个字节都有唯一的“地址” （逻辑上是数组索引）
• 每个字节有连续且唯一的物理地址 Physical Address，CPU访问内存最自然的方式就是物理寻址（physical addressing）

4. 处理器

• 中央处理单元 CPU
• 解释或执行存储在主存中的执行的引擎
• 核心是“一个字”的寄存器，程序计数器PC，永远都指向主存中的机器语言指令（保存执行的内存地址)
  • 处理器不断执行着指令，在更新程序计数器；
• 处理器的指令执行模型，由指令集架构决定，INTEL和ARM
  • 指令集架构的执行模型，按照严格的顺序执行
  • 执行一条指令的步骤：
    1. 处理器从程序计数器指向的内存处读取指令
    2. 处理器解释指令中的位
    3. 处理器执行指令指示的操作
    4. 更新PC，让程序计数器指向下一条指令（寻址）
  • 寄存器文件 register file
    • 小的存储设备，由多个单个字长的寄存器组成，每个寄存器有唯一的名字
  • 算数/逻辑单元 ALU
    • ALU计算新的数据和地址值
    • 例子
      • 加载，从主存复制一个字节过着一个字到寄存器，覆盖寄存器原来的内容
      • 存储，从寄存器复制一个字节或者一个字到主存的某个地址，覆盖原来的值
      • 操作，把两个寄存器的内容复制到ALU，ALU对两个字进行算数运算，并将结果存放到一个寄存器中，以覆盖寄存器中原来的内容
      • 跳转，从指令本身抽取一个字，并将这个字复制到程序计数器（PC），以覆盖PC中原来的值
  • 处理的的指令集架构
    • 描述每条指令（机器代码）的效果，指令集架构提供的抽象（第四章）
  • 处理器的微体系机构
    • 处理器的实践实现

1.4.2 运行hello

• 初始时，shell执行自己的指令，等待输入，键盘输入./hello之后，shell程序将字符注意读入“寄存器”，在把字符放入内存；

• 输入回车后，shell获取了程序输入结束的命令，并执行”一系列的指令来加载可执行文件hellio“

  • 指令将 hello 目标文件中的代码和数据从磁盘复制到主存

    • 利用“直接存取器存器（DMA）”，数据可以不通过处理器直接从磁盘到达主存

  • 加载到主存后，处理器开始执行hello程序中的main程序中的机器语言指令

    • 这些指令将 输出字符串 从主存复制到寄存器文件，再从寄存器文件中复制到显示设备，最终显示在屏幕上

    

1.5 高速缓存

系统花费大量的开销（时间）把信息从一个地方复制到令一个地方，从磁盘复制到主存，从主存到寄存器，从寄存器到处理单元；

高速缓存存储器（cache memory）/ cache/ 高速缓存

• 作为在那时的集结区域，存放处理器近期会需要的信息
• L1 高速缓存，容量达到 ”数万字节“，访问速度和寄存器文件一样快
• L2 高速缓存，容量位”数十万到数百万“，通过一条特殊的总线连接到处理器；访问速度比L1 cache慢5倍（进程对其访问时间比L1长5倍），依然比访问主存快 5到10倍；

L1 和 L2 高速缓存使用 静态随机访问存储器（SRAM）的硬件技术实现

• 1级，2级，3级别高速缓存： L1， L2 ，L3
• 系统利用高速缓存和局部性原理，获取一个很大的存储器，访问速度也很快；
  • 局部性：程序具有访问局部区域里的数据和代码的趋势；
• 通过让高速缓存存放可能经常访问的数据，大部分的内存操作都在快速的高速缓存中完成；
• 使用高速缓存将程序性能提高一个数量级

1.6 存储设备形成的层次结构

	存储结构，自上而下，访问速度变慢，容量变大
L0	寄存器	CPU寄存器保存来自高速缓存存储器的字
L1	L1高级缓存（一级缓存）（SRAM)	L1高速缓存保存取自L2高速缓存的高速缓存行
L2	L2高速缓存（二级缓存）(SRAM)	L2高速缓存保存取自L3高速缓存的高速缓存行
L3	L3高速缓存（三级缓存）（SRAM）	L3高速缓存保存取自主存的高速缓存行
L4	主存（DRAM）	主存保存取自本地硬盘的磁盘块
L5	本地二级存储（本地永久存储，硬盘，磁盘）	本地磁盘保存远程网络服务器的文件
L6	原创二级存储（分布式文件系统，Web服务器）

• 主要思想
  • 上一层的存储器作为第一层的存储器的高速缓存

1.7 操作系统管理硬件

操作系统

• 防止硬件被控制应用程序滥用
• 向应用程序提供简单一致的机制来控制复杂而又通常不同的低级硬件设备；
• 抽象
  • 文件 是对I/O设备的抽象
  • 虚拟内存 是对主存和磁盘I/O设备的抽象
  • 进程 是对处理器，主存，I/O设备的抽象表示

进程	进程	进程
	虚拟内存	虚拟内存
		文件
处理器	主存	I/O设备

Unix 标准化 Posix，C语言接口，shell程序和工具，线程及网络编程

标准Unix规范

1.7.1 进程

• 进程时操作系统对一个正在运行的程序的一种抽象
• 并发运行
  • 一个进程的指令和另一个进程的指令交错执行
  • 多核心处理器，可以同时执行多个程序
  • 上下文切换： 单个CPU并发执行多个进程，时通过处理器在进程间切换来实现的
  • 操作系统保持跟踪进程运行所需要的所有状态信息，这种状态就是 上下文，如PC和寄存器文件的当前值，主存内容
  • 操作系统决定要把控制权从当前进程转移到新进程时，进行上下文切换，新进程从上次停止的地方开始
    • 保存当前进程的上下文，恢复新进程的上下文
  • 系统调用
    • shell通过系统调用（用户态进程和内核态进程唯一的入口），来执行命令请求，系统调用会将控制权传递给操作系统，操作系统保存shell进程的上下文，创建新进程的上下文，然后再将控制权传给新的进程，新进程终止后，操作系统恢复shell进程的上下文，并将控制权传回给它；
  • 内核
    • 常驻内存的操作系统代码
    • 管理进程间的切换（进程控制块）
    • 系统调用 system call
      • 应用程序需要操作系统的某些操作，会执行一条特殊的系统调用指令，将控制权传递给内核，然后内核执行被请求的操作并返回应用程序；
    • 内核是系统管理全部进程所用代码和数据结构的集合

1.7.2 线程

• 一个进程由多个线程执行单元组成
• 每个线程都运行在进程的上下文中
• 共享同样的代码和全局数据，并发和线程，第12章

1.7.3 虚拟内存

• 虚拟内存 - 抽象概念
• 为每个进程提供了独立占用主存的抽象，每个进程看到的内存都是一直的，虚拟地址空间
• 虚拟地址空间
  • 最上面的区域保留给操作系统中的代码和数据
  • 底部区域存放用户进程定义的代码和数据
  • 高地址段到低地址段是从上往下增大的
• 简单模型

虚拟内存模型
内核虚拟内存	用户代码不可见的内存
用户栈 （运行时创建的）
共享库的内存映射区域	printf函数
运行时堆 （在运行时由malloc创建）
读/写数据	从hello可执行文件加载进来
只读的代码和数据	从hello可执行文件加载进来
{程序开始}

• 每个进程开到的虚拟地址空间由大量准确定义的区构成，每个区都有专门的功能
• 简单介绍内存区域的功能
  • 程序代码和数据
    • 对所有进程来说，代码从同一固定地址开始，紧接着C全局变量和相对应的数据位置；
    • 代码和数据区是直接按照可执行文件的内存初始化的
  • 堆
    • 代码和数据区在进程一开始运行时就被指定了大小
    • 堆，调用malloc和free这样的C标准库函数时，堆可以在运行时动态的扩展和收缩；
  • 共享库
    • 在地址空间的中间部分是一块用来存放C标准库和数学库的共享代码和数据的区；
  • 栈
    • 位于用户虚拟地址空间的顶部，用户栈
    • 编译器用栈来实现函数调用，用户栈可以在执行期间动态的扩展和收缩
    • 每次调用一个函数是，栈就会增长；从一个函数返回时，栈就会收缩；
  • 内核虚拟内存
    • 地址空间顶部的区域是为内核保留的
    • 不允许应用程序读写这个区域，不允许直接调用内核代码定义的函数
    • 通过系统调用，调用内核来执行函数和操作

1.7.4 文件

• 文件 就是字节序列
• Unix思想中，一切皆文件
  • 每个I/O设备，磁盘、键盘、输出设备、网络
• 所有的输入输出都通过使用一小组为 Unix I/O 的系统函数调用读写文件来实现的；
• 一切皆文件的思想，为应用程序提供了统一的试图，来处理系统中的各种I/O

Linux：完整的符合Posix标准的Unix操作系统版本

1.8 系统之间的网络通信

• 从单独的系统来看，网络可以看作一个I/O设备；
• 系统从主存复制一串字节到网络适配器中，数据流经过网络到达另一台机器，系统读取从其他机器发送来的数据，并把数据复制到主存；

1.9 主题

• 系统是由硬件和软件互相交织的集合体；共同协作达到运行应用程序的目的；

1.9.1 Amdahl 定律

• 思想

  • 当对系统的某个部分加速时，其对系统整体性能的影响取决于该部分的重要性和加速程度；
  • 想要显著加速整个系统，必须提升全系统中相当大的部分的速度；

  S = 1/ (1-a) + a/k

  详细公式：Page16

1.9.2 并发和并行

• concurrency 并发 ：指一个同时具有多个活动的系统
• parallelism 并行： 用并发来使一个系统运行的更快；并行可以在计算机系统的多个抽象层次上运行；

1. 线程级并发

• 构建在进程这个抽象之上

• 使用线程，在一个进程中执行多个控制流

• 单个处理器的并发：通过计算机在执行的进程间快速的上下文切换来实现；

• 典型多核处理器的机构

  • 每个核心由自己的L1 cache和L2 cache，L1 高速缓存分为两部分，1保存最近拉取的指令，2存放数据
  • 所有核心共享更高层次的高速缓存，到主存的接口

  结构图：

  

• 超线程，同时多线程（simultaneous multi-threading）

  • 允许CPU执行多个控制流
  • CPU某些硬件有多个备份
    • 程序计数器
    • 寄存器文件
  • 其他硬件只有一份
    • 浮点算术运算单元
  • 常规的处理器需要大约20 000个时钟周期做不同线程间的转换，超线程的处理器可以在单个时钟周期内决定要执行哪个线程；
  • 超线程使CPU能更好的利用它处理资源
  • 例
    • 在线程等待数据被装载到 高速缓存时，CPU切换执行线程去执行另一个线程；
  • 8核，可以并行的执行16个线程；

2. 指令级别并行

• 底层抽象，现代处理器可以同时执行多条指令 指令级并行
• 流水线
  • 将执行一条指令需要的活动分成不同的步骤
  • 将处理器的硬件组成一系列的阶段，每个阶段执行一个步骤，这些阶段可以并行的操作，用来处理不同指令的不同部分；
  • 达到近一个时钟周期一条指令的执行速率；
• 超标量处理器，比一个时钟周期更快的执行一条指令的速率；
  • 超标量处理器高级模型；

3. 单指令、多数据并行

• 允许一条指令产生多个可以并行执行的操作
  • 单指令、多数据， SIMD并行
  • 例：对8对单精度浮点数做加法的指令，一个指令包含8对单精度浮点数的相加
  • 使用编译器支持的特殊向量数据类型来写程序 GCC 支持向量数据类型

1.9.3 计算机系统的抽象

• 抽象

  • 例如一组函数规定一个简单的API，无需了解内部的实现就可以使用

  • 抽象

    虚拟机	虚拟机	虚拟机	虚拟机
    	进程	进程	进程
    	指令集架构	虚拟内存	虚拟内存
    			文件
    操作系统	处理器	主存	I/O设备

第二章，信息的表示和处理

###### 数字表示

把比特位组合在一起，加上某种解释 （interpretation）

• 无符号，unsigned 编码基于传统的二进制表示法
• 补码，two’s-complement 编码表示有符号整数，可以为正或者为负的实数

• 浮点数，floating-point 编码是表示实数的科学记数法的以2为基数的版本

• 计算机用有限数量的位对一个数字编码，当结果太大时不能表示，会导致某些运算溢出（ovaerflow）
• 浮点数的一组整数的乘积总是正的，由于表示的精度有限，浮点运算不可结合
• 整数运算和浮点数运算会有不同的数学属性
  • 处理数字表示有限性的方式不同
  • 整数表示一个相对较小的数值范围，是精确的
  • 浮点数编码一个较大的数值范围，表示是近似的
• 可表示的值的范围和不同算术运算的属性

C/C++/Java 数字表示

• C/C++一致

• Java创造了一套新的语言和运算标准

  C/C++ 数字类型

  • char 1 byte -128 到 127 或 0 到 255
  • unsigned char 1 byte 0 到 255 无负值的字符型
  • signed char 1 byte -128 到 127
  • int 2 或 4 byte -32,768 到 32,767 或 -2,147,483,648 到 2,147,483,647 32比特位整型和64比特位整型
  • unsigned int 2 或 4 byte 0 到 65,535 或 0 到 4,294,967,295 无负值的整型
  • short 2 byte -32,768 到 32,767 32比特位整型
  • unsigned short 2 byte 0 到 65,535 无负值的短整型
  • long 4 byte -2,147,483,648 到 2,147,483,647 64比特位整型
  • unsigned long 4 byte 0 到 4,294,967,295 无负值的长整型

2.1 信息存储

• 1 byte = 8 bit
• 一个字节作为最小寻址的内存单位
• 程序将内存视为一个非常大的字节数组，虚拟内存 virtual memory
• 内存中每个字节有唯一标识，地址 address
• 所有可能的地址的集合：虚拟地址空间 virtual address space
• 编译器和运行时系统将存储器空间划分位更可管理的单元，来存放不同的程序对象 program object、
• 将**程序数据、指令、控制信息、可以用各种机制来分配和管理程序不同部分的存储；
  • C中的指针的值，无论指向整型还是结构，都是某个存储块的第一个字节的虚拟地址；
  • C编译器将每个指针和类型信息联系起来，根据指针类型生成不同的机器代码来访问存储在执行所指向地址的值；
  • C编译器维护类型信息，但是生成的实际机器级程序并不会包含有关类型的信息；
  • 每个程序对象可以简单的视为一个字节块，程序本身就是一个字节序列；

2.1.1 十六进制

• 一个字节
  • 二进制 00000000 ~ 11111111
  • 十进制 0 ~ 255
  • 16进制 hexadecimal （hex） 0~9 A~F： 0 ~ FF
• 二进制 十六进制 相互转换
  • 每四位一组进行转换，位数不是4的倍数情况，最左边一组少于4位，前面补0
  • x = 2 ^n ，x位2的n次幂，将n转化位 i + 4j 的形式，0<= i <= 3，x就可以写为开头16进制数字为2^i，后面跟随j个0；
    • 2048 = 2^11 则 11= 3 + 2*4， i =3， j=2，则 2048的16进制表示为 0x800；
• 十进制 十六进制 相互转换
  • 将十进制的数字，反复的除以16，得到的商和余数，余数为当前的最低位，商继续除以16；
  • 十六进制转换十进制就直接用乘法

2.1.2 字数据大小

• 每台计算机都有 字长 word size： 用来指明数据的标称大小（nomianl size）
• 虚拟地址以一个字来编码，字长决定了虚拟地址空间大小
• 对一个字长为 ω位的机器，虚拟地址的范围是0~2^ ω -1，程序最多访问2 ^ ω个字节
• 32位字长限制虚拟地址空间位4GB
• 64位字长，虚拟地址空间位16EB

应为字长 用来指定数据标称的大小，所以32位字长内容纳的最大值就是2的32次方

64位的机器可以运行32位编译的程序，向后兼容；

所谓的32位程序和64程序，区别在于该程序的编译，而不是运行的机器类型；

• 数据类型的确切字节数依赖于程序如何被编译
• char 用来存储文本串中的一个字符，也可以用来存储整数值；
• 新数据类型，数据大小固定不变，不随着编译器和机器的设置发生变化
  • int32_t 4byte
  • int64_t 8byte
  • 使用确定大小的整数类型是控制数据表示的最佳途径
• 大部分数据类型都编码为有符号数值
• 无符号声明：unsigned
• C标准中char不能保证一定是有符号的
• 关键词的顺序包括和省略，C中存在多种形式
  • 表示一个意思
    • unsigned long
    • unsigned long int
    • long unsigned
    • long unsigned int
• char * 使用程序的全字长
• 单精度：4
• 双精度：8

2.1.3 寻址和字节顺序

• 多字节的对象

  • 被存储位连续的字节序列
  • 对象的地址为所使用字节中最小的地址
  • 如
    • int变量的x地址0x100，&x为0x100，它的4个字节存储在 0x100，0x101，0x102，0x103 位置

  ω位整数，最高有效字节包括[x ω -1, x ω -2, … , x ω -8]，最低有效字节包括[x7, x6, x5 … x0]

  • 小端法 little endian：

    • 最低有效字节在最前面的方式
    • 选择在内存中按照从低有效字节到最高有效自己顺序的存储对象

  • 大端法 big endian：

    • 最高有效字节在最前面的方式

  • 位于地址0x100处的整数，十六进制的值为0x01234567，占用32个bit

    • 小端法

      • …	0x100	0x101	0x102	0x103	…
        …	67	45	23	01	…

    • 大端法

      • …	0x100	0x101	0x102	0x103	…
        …	01	23	45	67	…

  • Intel兼容机使用“小端模式”

  • 微处理器还会支持双端法，操作系统配置

• 网络应用需要遵守关于字节顺序的规则，以确保发送方机器将内部表示转换成网络标准；

• 反汇编器

  • 确定可执行程序文件所表示的指令的工具
  • 4004d3: 01 05 43 0b 20 00 add %eax,0x200b43(%rip)
  • 十六进制 01 05 43 0b 20 00 是一条指令的字节级别表示，该指令是：把一个字长的数据加到一个值上
  • 该存储地址：0x200b43 + 程序计数器的值，程序计数器的值就是下一条要执行的指令的地址
  • 按照小端法读取当前值： 0x200b340501
    • 阅读小端的方法，按照相反的顺序

• C中通过使用强制类型转换 cast 或者 联合 union，来允许一种数据类型引用一个对象，这种类型与创建对象时定义的类型不同；

  • 
  • 通过 (byte_pointer) &x , (指针类型) 变量地址，强制将变量转化为了当前的指针类型
  • sizeof 通过返回不同机器类型的上的对象类型的长度，来适配
  • 这种强制类型转换告诉编译器：程序应该将这个指针当作一个指向字节序列的指针，而不是指向任何一个原始定义的数据类型的对象，指针保存了对象使用的最低字节地址

  

• 不同的操作系统或机器使用不同的存储分配规则；

C中typeof声明提供了一种给数据类型命名的方式

• 浮点和整型使用不同的编码方法；

查看 ascii ：man ascii

2.1.4 表示字符串

• C中的字符串是一个以null(值为0)字符结尾的字符数组；
• 每个字符都用ASCII标准来编码表示
  • 十进制的ascii表示就是0x3x，终止字节的十六进制表示为0x00
• 使用ASCII码的任何系统上得到的字符都是相同的结果，与字节顺序和字大小无关；
• 文本数据并二进制数据有更强的平台独立性

Unicode 统一字符集，用32位来表示字符；用来表示多种语言和文字的标准

UTF-8 表示将每个字符编码位一个字节序列，UTF-8中的ASCII码表示的和ASCII一样

2.1.5 代表代码

• 对于C代码，不同的机器类型使用不同且不兼容的指令和编码方式
• 完全一样的进程在不同的操作系统上也有会不同的编码规则
• 二进制代码是不兼容的，很少人在不同类型的机器和操作系统中移植
• 从机器的角度，程序仅仅只是字节序列；

2.1.6 布尔代数简介

• 二进制值是计算机编码、存储和操作信息的核心；
• 布尔运算
  • ~ 表示逻辑运算的NOT
  • & 表示逻辑运算的AND

  • 表示逻辑运算的OR

  • ^表示逻辑运算的异或 XOR Exclusive-OR
• 布尔代数在数字逻辑电路有重要的角色
• 位向量运算
  • 位向量； 固定长度位 ω，由0和1组成的串
  • 位向量的运算可以定义为参数的每个对应元素之间的运算
    • 例如a位向量和b位向量长度都为 ω， 则a&b也是一个 ω的位向量，其中每个元素位 a&b

    • 类似可以使用

      ^ ~

布尔运算&对

和

对&有分配律

布尔环 PAGE36

• 位向量的编码集合
  • 以位向量的形式做两个集合的并和交、补
  • &对应交集

  • 对应并集

  • ~对应补集
  • 位向量对集合编码
    • 如：信号中断程序执行，通过指定一个位向量掩码，有选择的使能或者屏蔽一些信号
      • 1表示信号i的使能
      • 0表示信号i的屏蔽
    • 掩码表示的就是设置位有效信号的集合

2.1.7 C语言中的位级运算

• C支持按位的布尔运算
  • ~ 表示逻辑运算的NOT
  • & 表示逻辑运算的AND

  • 表示逻辑运算的OR

  • ^表示逻辑运算的异或 XOR Exclusive-OR
• 能用到任何”整型“的数据类型上
• 手动确定结果的方式：将16进制转化为2进制，然后做相应的位运算，再将结果转化为16进制
• 掩码运算
  • 掩码表示从一个字中选出的位的集合
  • 例如
    1. 0xFF，表示一个字的最低位字节，x&0xFF的结果为：x的最低为有效字节
    2. ~0 将生成一个全1的掩码

2.1.8 C中的逻辑运算

• 代表代码逻辑中的OR

• && 代表代码逻辑中的AND
• ! 代表代码逻辑中的NOT
• 按位运算只有参数被限制在1个位时，才会和逻辑运算有相同的行为；

2.1.9 C中的移位运算

• 移位运算，向左向右移动位模式

• 左移

  • x«k, x向左移动k位，丢弃最高的k位，并在右端补k个0

• 右移

• 逻辑右移
  • 在左端补k个0，k个低位丢弃
• 算数右移
  • 在左端补k个最高有效位的值
  • 最高有效位为1时，则全部补1
  • 最高有效位为0时，则全部补0

• 编译器/机器 都对有符号树使用算数右移，无符号数，右移必须为逻辑右移

  Java

  x»k 算数右移

  x»>k 逻辑右移

  移动的k位大于字长 ω，则真正要做的移动位 k mod ω

2.2 整数表示

• 用位编码整数的两种不同方式
• 只能表示非负数
• 表示正数、负数、0

计算机对整数的编码和操作，算数操作语句

2.2.1 整数数据类型

• C支持多种整数类型，表示有限范围的整数；

• 64位程序的C整型数据类型的典型取值范围

  C整型数据类型	最小值	最大值
  [signed] char	- 2^7	2^7 - 1
  unsigned char	0	2^8 -1
  short	- 2 ^ 15	2^15 -1
  unsigned short	0	2^16 -1
  int	- 2^31	2^31 -1
  unsigned	0	2^32 -1
  long	- 2^ 63	2^63 - 1
  unsigned long	0	2 ^ 64 -1
  int32_t	- 2^31	2^31 -1
  uint32_t	0	2^31 - 1
  int64_t	- 2^63	2^63 - 1
  uint64_t	0	2^64 -1

  • 上图的取值范围不是对称的 – 负数的范围比整数的范围大1；因为负数的表示

C/C++都支持有符号（默认）和无符号数；Java只支持有符号数；

2.2.2 无符号数的编码

• 位向量带入 B2U 函数 Binary to Unsigned
• 最小值为0
• 最大值为2^ω - 1

• 介于0 ~ 2^ω - 1 之间的数都有一个唯一的ω位的编码值
• 函数B2U是一个双射函数，每个长度位 ω 的位向量都映射为0 ~ 2^ω - 1 之间的一个唯一值，反过来，在于0 ~ 2^ω - 1 之间的数都有一个唯一的 ω位 的编码值

2.2.3 补码编码

• 有符号数的计算机表示方式 ”补码 two’s-complement”
• 定义：将字的最高有效位解释为负权（negative weight）
  • 函数 B2T Binary to Two’s-complement
  • 
  • 最高有效位x ω -1 为符号位，权重 - 2^ ω -1 ；
  • 符号位为0表示非负
  • 符号位为1表示负数
• 表示的最小值为[100….0]，值为 - 2^ (ω -1)
• 表示的最大值为[011….1]，2^(ω -1) - 1
• 例如当长度为4的位向量，补码能表示的最小值为- 8，最大值为7
• 补码编码的唯一性
  • 取值范围内的每个数字都有唯一的 ω 位的补码编码
  • B2T是一个双射函数
    • 对于每个 ω 位的位向量，其中每个向量都有唯一的x，且TMin ω <= x <= TMax ω
• 注意：
  • 1. 补码范围时不对称的，TMin没有与之对应的正数，导致了补码运算的特殊属性；
       • 一半的位模式符号位为1，表示负数，另一半表示非负数，但是正数不包含0，所以导致不对称；
    2. 最大的无符号数值，比补码的最大值的两倍大一：UMax ω = 2TMax ω + 1；
• 所有的机器都用补码来表示有符号整数
• C的标准库中定义了一组常数，来限定编译器运行的机器不同类型数据的取值范围；INT_MAX INT_MIN UINT_MAX

Java: 采用补码表示整数数据类型的取值范围，取值与64情况一致，单字节位byte类型；保证Java程序在任何机器都能表现一致；

求补码

正数：最高有效位位0，将正数转为2进制数，输出16位或者32位或者64位

0：补码为 所有位都为0

负数：将负数的值部分转为16位/32位/64位二进制，每位取反，并+1；

反码 （Ones‘ complement）：对数字0有两种表示方式，[00..0]为+0，[11…1]为-0，反码已经被淘汰

原码：浮点数中使用

2.2.4 有符号数和无符号数之间的转换

• C允许不同数字数据之间做“强制”类型转换；

  • int x; unsigned u; (unsigned)x; (int)u;
    unsigned u = 4294967295u;
    int tu = (int)u; // tu的最终值为-1，因为无符号编码的4294967295u和补码编码的-1的二进制表示完全一样；
    

  • 强制类型转换保持结果的位值不变，但是解释位值的编码方式不同，如将无符号编码的整型转化为补码编码的有符号的整型，虽然数值在位的表示上一样，但是系统对位的解释方式就不同了；

  • C中的有符号和无符号之间的相互转换，规则

    • 数值可能会改变，但是位模式不变；

  • T2U

    • 补码和无符号数之间的关系：

    • 

    • T2U 16(-12345) = -12345 + 2^16 = 53191

    • 补码表示的负数转化成无符号数，最高位的权重从-2^ω变成了2^ω，对于整个数来说大小增加了2*2^ω；

      • 例如对于一个4位位向量[1,0,1,1]来说，它的补码表示-5，它的无符号表示位2^4 + (-5) == 11;

    • 对于T2U来说，将一个有符号数映射成它相应的无符号数时，负数就被转化为了大的正数，而非负数会保持不变；

      补码的符号位，1表示负数，0表示非负；

  • U2T

    • 无符号数和补码之间的关系；
    • 
    • 对于小数（<= TMaxω），从无符号数到有符号的转换将保留数字的原值；
    • 对于大数（> TMaxω)，从无符号到有符号的转换将转换为一个负数值；

  • 总结

    • 对于无符号和补码之间的转换
    • 对于范围在 0 <= x <= TMaxω之内的值而言，无符号和补码之间的数字相同；T2Uω(x) = x, U2Tω(x) = x;
    • 对与这个范围之外的数，需要加上或者减去2^ω

2.2.5 C中的有符号数和无符号数

• C支持所有的整型数据类型的有符号和无符号运算
• 几乎所有的机器都是用补码
• 大多数数字都认为是有符号的，对于要创建的无符号型常量，需要明确在字符后缀加上字符‘U’或者‘u’；
• C中的有符号和无符号数之间的转换原则是保持位表示保持不变
  • 无符号转有符号：U2Tω
  • 有符号转无符号：T2Uω
    • ω表示数据类型的位数
  • 显示的方式是用(type)进行强制转换
  • 隐式的方式是将一种类型的表达式被赋值给另一种变量
  • %d 有符号十进制
  • %u 无符号十进制
  • %x 十六进制
  • printf输出也会隐式的对 有符号和无符号做类型转换
  • C语言会在一个有符号和一个无符号数运算时，会隐式的将有符号参数强制类型转换为无符号数，并假设两个数都是非负的，再执行运算；
    • -1 < 0U 这个表达式的第一个数为有符号，但是第二数为无符号，所以C会将第一个数转换成无符号的32位整型，所以最终的结果为0（否）；
    • C中对INT_MIN的表示为 -INT_MAX - 1， 所以再表示32位有符号最小值的时候，用-2147483647 - 1；这个细节的原因是因为，补码表示的不对称性和C语言的转换规则之间的交互，详细需要研究C语言标准的一些比较隐晦的角落

2.2.6 扩展一个数字的位表示

• 无符号数的零扩展

  • 
  • B2Uω(x) = B2Uω’(x’)
  • 将一个无符号的数转换成一个更大的数据类型，只需要简单的再表示的开头加0
  • 零扩展 zero extension

• 补码数的符号扩展

  • 
  • B2Tω(x) = B2Tω’(x’)
  • 将一个补码数字转换位一个更大的数据类型，再表示中添加最高位的有效值
  • 符号扩展 sign extension

  大端法：最高位有效字节在内存地址的最前面，按内存地址的增长可以直接读取

  小端法：最高位有效字节在内存地址的最前面，按内存地址的增长反向读取

  2进制存储，16进制表示

• 推到见PAGE55

2.2.7 截断数字

• 将一个ω位的数截断位一个k位的数字，将会丢弃高位ω-k位，截断一个数可能会改变它的值，溢出；

• 截断无符号数
  • 
  • 所有被截去的位其权重都是2^i，其中i >= k，每一个权在取模操作下的结果都为0：2^i mod 2^k = 0；
  • 如：
    • 对8位2进制数： 10010001 将其截断位4位二进制数：结果位 10010001 mod 2^4
      • 因为2^7 mod 2^4 为0，就是被截取的每一位的权和2^k取模都为0，所有只需要将原值与2^k取模就可以得到截断后的结果；
• 截断补码数值
  • 
  • x mod 2^k 的结果是一个0~2^k -1之间的一个数，然后对这个数应用函数 U2T 产生的效果是将最高位有效位x k-1 的权重从2^(k -1)转变为-2^(k -1)；
  • 如：
    • x=53191 从int转化为short，x mod 2^16 = 53191，U2T(x)= 53191 - 65536 = - 12345
    • 1001 0001为-119的补码表示，将它截断为4位补码的结果因为 1001，-119 mod 2^4 = -7， -7的补码表示位1001；
• 证明见 PAGE 58

2.2.8 有符号数和无符号数的建议

• 有符号和无符号数的隐式强制转换导致了非常直观的行为；这些行为会导致程序错误；

• 隐式强制类型转换的差别错误，较难被发现；

• 有符号和无符号导致的运算错误，见PAGE58；

  • 有符号数到无符号数的隐式转换，会将一个负值转换成一个非常大的正数，如果是对内存空间的访问，会导致访问到某些程序并无权限能去访问的数据，导致错误和漏洞；

  • 避免的方式

    • 绝不是用无符号数

    • 例如Java本身只支持有符号整数，并且要求全部使用补码运算；»位算数右移 »>逻辑右移

      • 在左端补k个最高有效位的值
      • 最高有效位为1时，则全部补1
      • 最高有效位为0时，则全部补0

  • 需要把字当作位的集合不考虑任何数字意义的时候，无符号数值非常有用；例如：bit-flag，bitmap

2.3 整数运算

计算机的运算有限性

2.3.1 无符号加法

• 字长膨胀，如果要对算术运算进行完整的标识，就不能对运算字长做任何限制；

  例如，编程语言Lisp，支持无限精度的运算，允许任意的整数运算（需要在机器的内存限制之内）

• 编程语言支持固定精度的运算；

• 

  • x+y映射到右边的无符号ω位的x + y；
    • 正常情况下x+y的值保持不变
    • 益处情况则：x+y - 2^ω
  • 例如：
    • x=9 y=12 用4位标识位1001，1100；
    • x + y = 21 表示为 10101
    • 丢弃最高位的1后，得到0101，结果为5
    • 21 mod 16 结果为5

• 算术运算溢出

  • 指完整的整数结果不能放到数据类型的字长限制中

• C程序中，不会将溢出座位错误而发送信号

  • 判断是否会发生溢出
    • 
    • 相加的结果小于任何一个相加的数，则表示相加溢出；

• 加法逆操作

  • 阿贝尔群 Abelian group，每个元素都有一个加法逆元
  • 对于每个值x，必然由一个 -x满足，-x + x = 0
  • 无符号数求反
    • 
    • x为0时，加法逆元为0
    • x > 0 时，（x + 2^ω - x ）mod 2^ω = 0

2.3.2 补码加法

• 补码加法
  • 
    • 正溢出：
      • 当x+y超过TMaxω
      • 截断的结果为从数中减去2^ω
      • 正溢出的截断等于是对 2^ω 取模mod
    • 负溢出：
      • 当x+y小于TMinω
      • 截断的结果为从数中加上2^ω
      • 负溢出的截断，将符号位截断了，此时表示的结果为 x +y + 2^ω，因为补码表示的负数的大小为 - 2^ω + sum(i*2^i)
      • 如两个4位数，1000，1000，补码表示都为-8，x+y = - 16 + 2^4 = 0，位相加为 10000，截断前面的1，结果就是0000
  • 两个数的ω位补码和 与 无符号和 有完全相同的位级表示
  • 大多数计算机使用同样的机器指令来执行无符号加法或者有符号加法
• 检测补码加法中的溢出
  • 
  • 发生正溢出条件：
    • x > 0, y > 0, 但是结果 <= 0
  • 发生负溢出的条件：
    • x < 0, y < 0, 但是结果 >= 0

2.3.3 补码的非

• 对于在范围 TMinω <= x <= TMaxω 中的每个数字x都有加法逆元；
• 补码的非
  • 
  • 对于ω位的补码来说，TMinω是其加法的逆；
  • 对于任何其他数值，其逆为-x；

    • 对于一个x > TMinω，数值-x表示为ω位的补码，那么x就是其正数的补码表示，则-x+x = 0，

      -x

      +

      x

      = 2^ω

      • 例如：1001为-7，0111为7，1001 & 0111 = 10000
  • 补码的位级表示 PAGE66

2.3.4 无符号的乘法

• C中无符号乘法被定义为产生ω位的值
• 
  • 将一个无符号的数截断为ω位等价于 计算该值模2^ω，对2^ω取模后，模的值正好就是ω位前的每一位的值；

2.3.5 补码乘法

• C中对有符号乘法通过将2ω位的乘积截断为ω位来实现的；
• 将一个补码数截断为ω位
  1. 先计算该值模2^ω
  2. 再将无符号数转换为补码
• 
• 无符号和补码的乘法，运算的位级表示都是一样的；
  • 
  • 例如：
    • 对两个不同的3位二进制数的乘法，得到6位乘积；
    • 无符号的截断 x * y mod 2^3
    • 补码将无符号的截断结果再转换成补码表示
    • 虽然无符号和补码两种乘法的6位表示不同，但是截断后的乘积位级表示都相同
      • 无符号：101，011，表示5和3，乘积为 001111，截断后111，表示7
      • 补码：101，011，表示-3和3，乘积为-9，110111，截断后111，补码为-1
• XDR库中的安全漏洞PAGE69

2.3.6 乘以常数

理论上，乘法需要比 加法 减法 位级运算 移位 等需要更多的时钟周期来完成运算指令；

编译器使用一项重要的优化：

​ 用位移和加法运算的组合来代替乘以常数因子的乘法；

• 乘以2的幂

  

  • 如：
    • ω为4时，11的表示为 1011
    • 当k=2时，利用以上的位移原理：4*2^2可以用4+2位来表示，且再右边补充0
    • 结果为6位的向量 101100， 11*4 = 44；

• 与2的幂相乘

  • 
  • 
  • 固定大小的补码 算术运算和位级操作 与其无符号运算等价；
  • 所有可以使用左移运算进行对**补码运算的2的幂的乘法

• 对于无符号运算或是补码运算，乘以2的幂都有可能导致溢出

  • 溢出的结果，再位移运算后的结果上进行截断

• 常数乘法

  • C编译器使用移位、加法、减法的组合来消除整数乘以常数的情况；
  • 如：
    • x * 14
    • x * (x^3 + 2^2 + 2^1)
    • 编译器对于这个乘法操作：(x«3) + (x«2) + (x<1) 将这个乘法替换为三个移位操作和两个加法操作
    • 或者利用 14 = 2^4 - 2^1 这样的属性，来用两个移位和一个减法

• 对于使用移位、加法、减法的组合指令，还是一条乘法指令，取决于指令的相对速度；

  • 大多数编译器再需要少量移位、加法、减法的情况下才会使用这种优化；

2.3.7 除以2的幂

大多数机器上，整数除法要比整数乘法更慢，需要30个或者更多的时钟周期

• 除以2的幂用右移来实现
  • 无符号使用逻辑移位
  • 补码使用算术移位
• 无符号的除法 除以2的幂
  • 
  • 逻辑右移，从左端移入0；
• 补码除法 除以2的幂
  • 
  • 为了保证负数仍然是负数，移位需要执行算术右移；
  • 对于非负数，右移效果和无符号的除以2的幂的右移效果一致
  • 当需要进行舍入时，移位导致结果向下舍入；
    • -12340/4 表示为16位 1100111111001100
    • 算术位移的结果为1111110011111100
    • 计算结果为 -771.25 但是位移结果为 -772，所以舍入的方式是向下舍入
• 通过移位之前偏置 biasing这个值，来修正这种不合适的舍入
  • 
  • 在执行算术右移之前加上一个适当的偏置导致正确的舍入结果；
    • -12340/4 表示为16位 1100111111001100
    • 增加偏置 **后，偏量为将1右移k位再-1，也就是1右移4位再-1**，结果为1100111111011011
    • 算术位移的结果为1111110011111101
    • 计算结果为 -771.25 但是位移结果为 -771，所以舍入的方式是向零舍入
• 对于使用算术右移的补码机器
  • C表达式： (x<0 ? x+(1<<k) -1 : x) >> k
• 除以2的幂，可以通过逻辑运算和算术运算来实现；大多数机器上同时提供这两种类型的右移；
• 这种方法不能推广到除以任意常数；除以2的幂的除法无法用来表示除以任意常数K的除法

2.3.8 总结思考

• 计算机执行的 整数 运算实际上是一种模运算的形式；
• 表述数字的有限字长限制类可能的值的取值范围，运算结果可能溢出；
• 补码：
  • 提供了，正数和负数的表示方法
• 无符号和补码都使用来位级来实现算术运算，包括加法、减法、乘法、除法
• C中需要特别注意对unsigned类型的数据的隐式的强制类型转换

2.4 浮点数

所有计算机所支持的浮点数标准：IEEE

• 浮点数的表示
• 舍入问题（rounding）

2.4.1 二进制小数

• bmbm-1bm-2...b1b0.b-1b-2b-3...b-m-1b-m
• 点好左边的位的权是2的正幂，殿后右边的位的权是2的负幂；
  • 二进制小数点向左移动一位，相当于该数除2
    • 例如：101.11位5又3/4
    • 10.111表示2又7/8
    • 1011.1表示11又1/2
  • 二进制小数点向右移动一位，相当于该数乘2
• 对于有限长度的编码，类似十进制无法精确的表达1/3这样的数
  • 2进制只能精确表示能被写成 x * 2^y 的数
  • 其他值只能被近似的表示
  • 增加二进制表示的长度，可以提高表示的精度；
• 练习：2.46

2.4.2 IEEE浮点表示

• V = (-1)^s X M X 2^E

• **s ** 用来决定是负数还是、正数

• M 是一个二进制小数，范围是1~2-ε或者是0~1-ε

• E 作用是对浮点数加权，权重位2的E次幂（可能是负数）

• 单独符号位s用来直接编码符号s

• k位的阶码字段E，exp

• n位的小数字段M，frac

• 单精度浮点格式

  • 31	30-23	22-0
    s	exp	frac

  • s为1位，exp位k=8位，frac为n=23位，得到一个32位的表示

• 双精度浮点数

  • 63	62-52	51-0
    s	exp	frac

  • s位1位，exp为段k=11位，frac段k=52位；得到一个64位的表示；

• 根据exp的值，被编码值的情况：

  1. 规格化的值，最普遍的情况
     • 当exp的模式不全为0，不全为1(float155，double2047)，属于这种情况；
     • 阶码字段被解释为以偏置（biased）形式表示的有符号整数；
     • 阶码的值位 E = e - Bias
       • e是无符号数，位向量 ek-1ek-2…e3e2e1
       • Bias 为2^(k-1) -1
         • 单精度位127
         • 双精度为1023
       • 由此产生的指数的取值范围
         • 单精度 -126 ~ +127
         • 双精度 -1022 ~ +1023
     • 小数字段frac，用来描述小数值f，其中0<= f < 1，二进制表示位0.fn-1…f1f0;
       • 二进制小数点就在最高有效位的左边
       • 尾数 M 定义为1+f
  2. 非规划化的值
     • 阶码的域全为0时
       • 阶码值E = 1 - Bias 尾数值位M=f；
     • 提供来表示数值0的方法
     • 逐渐溢出 gradual underflow，表示数值分布均匀接近0.0的数
  3. 特殊值
     • 阶码全为1
       • 小数域全为0，得到的表示无穷大
         • s=0，表示+♾️
         • s=1，表示-♾️
         • 无穷能够表示算术运算的溢出结果，如使用一个数除以0
       • 小数域位非0时，结果位NaN
         • 表示 Not a Number
         • 对于一个无法实现的运算，将会返回NaN值
         • 如对-1开根号

2.4.3 数字示例

• 上图6位格式表示的浮点，k=3的阶码E，n=2的尾数M；

  • 偏置为 2^(3 - 1) -1= 3
  • 两个正负无穷大再左右两端
  • 最大的规格化数值位-14和+14
    • e最大值为110，为6，则E=3，2^E = 8
    • 小数最大值为11，最大值为1/2 + 1/4，f=3/4，M= 1+ 3/4 = 7/4
    • 最大数的表示为 2^E X M = 14
    • M = 1 + f，f=fn-1 + fn-2 + … f2 + f1
    • E = ek1ek-2k-3…e2e1 - 2^(k-1) -1(Bias)
    • 表示的结果位2^E X M
  • 非规格化的数聚集在0附近
    • 并不是均匀分布，越靠近原点越稠密

• 对于使用IEEE表示的浮点数

  • 八位浮点格式

    

  • 详细 PAGE 81
  • 位表达式按照升序排列，是为了让浮点数能够使用整数的排序算法来排序；

  

  • 属性
    • 

2.4.4 舍入

• 表示方法限制了浮点数的范围和精度，所以浮点运算只能近似的表示实数的运算；

• 舍入运算（rounding）

  • 对于一个值x，找到最接近值的x‘，并使用浮点形式表示

  • IEEE提供四种舍入方式

    • 默认的方法是找到最接近的匹配

    • 其他三种方法用来计算上界和下界

    • 向偶数舍入 round-to-even，最接近值的舍入 round-to-nearest，为默认方式

    • 

      偶数舍入，大多数现实情况下避免统计偏差；

2.4.5 浮点运算

• 浮点值x和y看作实数，运算 . 定义在实数上，对浮点的运算将产生Round(x . y);
• IEEE对浮点运算的参数中出现的 -0， -♾️，TeddyynadyyteddyynaN是，给出了合理的规则；
  • 1/-0 产生 -♾️
  • 1/ +0 产生 +♾️
• 浮点数的运算是可交换的
• 浮点数的运算是不可结合的
• 浮点加法的不可结合，再编译器层面可能会导致计算值与原始值的差异，编译器偏向保守，避免任何对功能产生的影响；
• 浮点数的加法满足单调性
  • a>=b 除了NaN外 x +a >= x + b
  • 无符号和补码不具有这个实数加法属性
• 浮点数乘法
  • 定义 x * y 为Round(x X y)
  • 运算再乘法中封闭，可交换，可能发生溢出，可能产生无穷大或者NaN
  • 乘法不可结合
  • 乘法单调性
    • a >= b , c>=0 => a * c >= b * c
    • a >= b , c<=0 => a * c <= b * c
    • a!=NaN, a * a >= 0
  • 无符号或者补码的乘法没有这些单调属性

2.4.6 C中的浮点数

• float

• double

• 再支持IEEE浮点格式的机器上，float对应单精度，double对应双精度

• 这类支持IEEE的机器使用向偶数舍入的方式

• C不要求机器使用IEEE浮点格式

• 大多数系统提供，头文件或者过程库，来提供-0，-♾️，+♾️，NaN这些特殊值

  • #define _GNU_SOURCE 1
    #include <math.h>
    // 表示GNU编译器GCC 会定义程序常数 INFINITY和NAN
    

• 浮点数的强制类型转换

  • 

2.5 本章小结

######

第三章，程序的机器级表示

「第一部分」

第六章，存储器层次结构

简单的计算系统模型：

CPU执行指令，存储系统为CPU存放指令和数据，这个简单模型中，存储系统为线性字节数组，CPU能够在一个常数时间内访问每个存储器的位置；

• 存储器系统 memory system 具有不同容量、成本和访问时间的存储设备层次结构；
  • CPU寄存器保存着最常用的数据
  • 靠近CPU的小的、快速的高速缓存存储器（cache memory）作为一部分存储在相对较慢的住存储器（main memory）中数据和指令的缓冲区域；
  • 主存缓存磁盘上的数据；
• 存储访问数据的时钟周期的数量级
  • CPU的寄存器中，指令执行期间，0个周期就能访问到
  • 存储在高速缓存中，4 ~ 75个周期
  • 访问主存中存储的数据需要上百个周期
  • 访问磁盘中的数据，需要大约几千万个周期
• 思想
  • 局部性（locality）
    • 具有良好局部性的程序，倾向于一次又一次的访问相同能够的数据项集合，或者倾向于访问领近的数据向集合；
    • 良好的局部性的程序比较差局部性的程序更多倾向于从存储器结构层次较高的层次访问数据项；

6.1 存储技术

6.1.1 随机访问存储器

• Random-Access Memory
  • 静态 SRAM
    • 作为高速缓存存储器
    • 不超过几兆字节
  • 动态 DRAM
    • 作为主存或者图形芯片的帧缓冲存储器
    • DRAM上百上千兆字节

TODO

6.2 局部性

• 局部性原理
  • 程序倾向于引用邻近于其他最近引用过的数据项的数据向，或者最近引用过的数据本身；
• 时间局部性（temporal locality）
  • 被引用过一次的内存位置很可能在不久的时间内再次被多次引用；
• 空间局部性（spatial locality）
  • 一个内存位置被引用过一次，程序可能会在不久的时间内引用其附近的一个内存位置；

6.2.1 对程序数据引用的局部性

6.3 存储器层次结构

• 存储器层次结构 （memory hierarchy）

  • L0	寄存器	CPU寄存器保存着从高速缓存存储器取出的字
    L1	L1高速缓存(SRAM)	L1高速缓存保存着从L2高速缓存取出的缓存行
    L2	L2高速缓存(SRAM)	L2高速缓存保存着从L3高速缓存取出的缓存行
    L3	L3高速缓存(SRAM)	L3高速缓存保存着从主存取出的缓存行
    L4	主存(DRAM)	保存着从本地磁盘取出的磁盘块
    L5	本地二级存储（本地磁盘）	保存从远程网络服务器磁盘上取出的文件
    L6	远程二级存储 （分布式文件系统、Web服务器）

  • 一个时钟周期内访问寄存器中的字

  • 几个时钟周期内访问SRAM中的缓存

  • 几十到几百个时钟周期内访问DRAM中的字

6.3.1 存储器层次结构中的缓存

• 高速缓存 cache
• 使用高速缓存的过程为缓存 caching
• 中心思想
  • k层的更快更小的存储设备作为位于k+1层更大更慢的存储设备的缓存；
  • 存储结构中的每一层缓存都来自较低的一层的数据对象
• 块（block）
  • k+1层的存储器被划分成为了连续的**数据对象组块（chunk），块；
  • 每个块都有一个唯一的地址或名字，使其区别于其他的块；
  • 块可以是固定大小（通过的存储器），也可以是可变大小（web服务器上的HTML）；
• 基本缓存原理
  • 
  • k层和k+1层都被划分为大小相等的块
  • k层的块数量更少，更快
  • 任何时刻，k层的缓存包含第k+1层块的一个子集的副本
• 传送单元（transfer unit）
  • 数据总是以块大小在k和k+1层之间来回复制
  • 以块为传送单元（transfer unit)
  • L1 和 L0之间通常1个字节大小的块来做传送单元
  • L2和L1之间、L3和L2之间、L2和L1之间通常几十个字节
  • L5和L4之间传送用几百或几千字节的块
  • 层次结构中较低的也是离CPU较远的设备访问时间较长，为了补偿这些时间，倾向于使用较大的块；

1. 缓存命中 cache hit

• 程序在第k层中找到了，其需要的处于k+1层的数据对象d
• 因为d刚好就在缓存在k层中，这个过程为缓存命中

2. 缓存不命中 cache miss

• 第k层没有缓存数据d，就是缓存不命中
• 缓存不命中时，k层会从k+1层取出包含d的块，如果k层缓存已满，可能会发生覆盖；
  • 替换 replacing / 驱逐 evicting
    • 被驱逐的块称为 牺牲块 victim block
    • 决定该替换哪个块，由缓存的替换策略 replacement policy来控制
      • 随机替换策略
      • LRU 最近最少被使用策略
  • 不命中后，从k+1层取出d，复制到k层之后，等待访问；

3. 缓存不命中的种类

虚拟内存

• Linux为每个进程维护了一个单独的虚拟空间地址
• 地址段包括
  • 代码段
  • 数据段
  • 堆
  • 共享库
  • 栈

Greek alphabet

Letter	Name
Α α	alpha, άλφα
Β β	beta, βήτα
Γ γ	gamma, γάμμα
Δ δ	delta, δέλτα
Ε ε	epsilon, έψιλον
Ζ ζ	zeta, ζήτα
Η η	eta, ήτα
Θ θ	theta, θήτα
Ι ι	iota, ιώτα
Κ κ	kappa, κάππα
Λ λ	la(m)bda, λά(μ)βδα[note 3]
Μ μ	mu, μυ
Ν ν	nu, νυ
Ξ ξ	xi, ξι
Ο ο	omicron, όμικρον
Π π	pi, πι
Ρ ρ	rho, ρώ
[Σ σ/ς, Ϲ ϲnote 4]	sigma, σίγμα
Τ τ	tau, ταυ
Υ υ	upsilon, ύψιλον
Φ φ	phi, φι
Χ χ	chi, χι
Ψ ψ	psi, ψι
Ω ω	omega, ωμέγα

CSAPP <2020第三阶段>

SUB： 2020年4月-2020年5月，当前规划第三阶段

问题描述

\1. 程序生命周期的全部过程 （内存、编译、链接、指令、运行时、并发）

\2. 程序内存管理和存储结构访问的全部过程

\3. 程序网络交互的全部过程、并发的全部过程

当前解决问题的方法：

对重点内容做笔记

暂时不再做太过于详细的笔记内容

当前阶段性问题（2020第三阶段）完全解决后，再次完全详细的复习和回溯本笔记中涉及的章节和内容，本笔记的目的是，在对CSAPP的阅读过程中，将黑盒部分进行打开，并且进行对上述问题的结构性知识总结，以补充现阶急需的底层知识；

存储器结构-重点笔记：

存储器结构模型

时间局部性

空间局部性

存储器结构中每一层缓存访问的成本：时间延迟、管理者、缓存内容

缓存命中、缓存不命中

高速缓存结构模型

S= 2^s ,表示S个高速缓存组（cache set）

E，每个组包含E个高速缓存行

B = 2^b 为没一行的B个数据块

有效位：valid bit

标记位：tag bit t = m - （b+s）

s为组索引 索引有2^s个索引

使用一个（S,E,B,m）的元组来描述

高速缓存是一个高速缓存的数组

每行：1个有效位、1个标记位、2个字节的缓存数据块

高速缓存的结构将m个地址位，划分为了t个标记位、s个组索引位，b个块偏移位

高速缓存器的大小C，是所有块大小的和，标记位和有效位不包括在内，C = S x E x B

指令读取：

当一条CPU执行指令是从地址A中读取一个字，CPU将地址A发送给高速缓存，如果高速缓存保存着A的副本，则直接将副本返回给CPU；

高速缓存通过检查地址位，找到所请求的字，类似使用了于哈希函数的哈希表；

工作方式：

参数S和B将m个地址位分为了三段

地址A，s个组索引位是一个到s个组的数组的索引，从0到2^s -1，通过索引位s找到目标字所在组

A中t个标记位，用来定位字所在的行

当且仅当设置了有效位且改行的标记位与A中的标记位相匹配时，组中存在该字，通过b块偏移，定位B个字节的数据块的字偏移；

字偏移？

每个高速缓存组只有一个高速缓存行：

直接映射高速缓存； direct-mapped cache

高速缓存的工作示例：

第七章：

链接（快速阅读，记录核心知识点）

链接 linking

将各种代码和数据片段收集并组合成一个单一文件的过程，然后文件被加载（load）到内存并执行；

链接的执行发生

\1. 编译时（compile time）（源代码到机器码的过程）

\2. 加载时（load time）（程序被加载器 loader 加载到内存并执行时）

\3. 运行时（run time）（由应用程序来执行）

链接由连接器 linker程序自动执行

• 链接器导致了分离编译（separate compilation）

○ 将一个大型的应用程序分解为更小的更好管理的模块

○ 可以独立的修改和编译这些模块

○ 改变一个模块，只需要重新编译，并重新链接

编译驱动程序

Complier driver

用户在需要时调用 语言预处理器、编译器、汇编器、链接器；

gcc驱动程序调用后执行的步骤，gcc驱动程序运行其他处理程序，运行gcc驱动程序时在shell命令中添加-v，可以看到verbose详情

\1. 运行C预处理器 cpp，将C的源程序的ASCII码翻译成中间文件main.i

\2. 运行C编译器 ccl，将main.i翻译成一个ASCII汇编语言文件main.s

\3. 运行汇编器as，将main.s 翻译成一个可重定位的目标文件 （ relocatable object file） main.o

\4. 对于多个C文件，驱动程序经过相同的过程生成xxx.o 可重定位目标文件

\5. 驱动程序最终运行链接器 ld，将main.o和xxx.o文件以及一些必要的系统目标文件组合起来；创建可执行目标程序

\6. Executable object file

\7. 运行该文件，在shell中输入文件名称，shell调用操作系统中的 “加载器” 函数，加载器将可执行文件中的代码和数据复制到内存，然后将控制转移到该程序的开始（main）；

可重定向目标文件中，包括各种不同的代码和数据节（section），每一个section中都是连续的字节序列

\1. 指令

\2. 初始化的全局变量

\3. 未初始化得变量

Linux LD 程序 静态链接器 static linker

链接器LD的任务:

• 符号解析 symbol resolution

○ 目标文件定义和引用符号，每个符号对应一个函数、一个全局变量、一个静态变量（C中任何static属性声明的变量）

○ 符号解析的目的是：将每个符号引用和一个符号定义关联起来

• 重定位 relocation

○ 编译器和汇编器生成从地址0开始的代码和数据节

○ 链接器通过把每个符号定义与一个内存位置关联起来，来重定位这些节；

○ 修改对所有符号的引用，使得他们指向定义的内存位置；

○ 链接器使用汇编器产生的重定位条目 relocation entry 的详细指令，来执行重定位；

• 目标文件是纯粹的字节块的集合

○ 程序代码

○ 程序数据

○ 引导链接器和加载器的数据结构；

• 链接器将字节块链接起来，确定被链接的块的运行位置，并修改代码和数据块中的各种位置；

目标文件

• 可重定位目标文件

  • 由编译器和汇编器生成

• 可执行目标文件

  • 链接器生成

• 共享目标文件

  • 特数的可重定位目标文件，可以在加载或运行时被动态加载入内存；

• 目标模块 object module

  • 一个字节序列

• 目标文件 object file

  • 以文件形式存放在磁盘中的目标模块

    目标文件都是按照目标文件格式组织的

    不同操作系统目标文件格式都不相同

    格式

    Unix a.out

    Windows Portable Executable PE

    MacOS Mach-O

    x86-46 Linux和Unix 可执行链接格式 Executable and Linkable Format ELF

7.4 可重定位目标文件

• ELF

• ELF header

  • 以16字节的序列开始，描述系统字的大小和字节顺序
  • 其余部分为帮助语法分析和解释目标文件的信息

• ELF头和节头部表之间的内容

  • .text
  • 以编译程序的机器代码
  • .rodata
    • 只读数据，例如printf语句中的格式串，开关语句跳转表
  • .data
    • 已经初始化的全局和静态C变量（局部C变量在运行时，保存在栈中，不出现在.data和.bss节中）
  • .bss
    • 为初始化的全局变量和静态C变量
    • 被初始化为0的全局变量和C变量
    • 在目标文件中这个节不占据实际的空间，仅为一个占位符
    • 运行时，在内存中分配这些变量，初始值为0
  • .symtab
    • 符号表
    • 存放程序中定义和引用的函数和全局变量的信息；
    • 可重定向目标文件中都存在 .symtab 符号表
    • 和编译器的符号表不用，.symtab符号表不包含局部变量的条目
  • .rel.text
    • 一个.text节中位置的列表，用来修改调用外外部函数或引用全局变量的指令的位置；
    • 可执行文件中不需要重定位信息；
  • .rel.data
    • 被模块引用或定义的所有全局变量的重定位信息；
      • 已经初始化的全局变量，初始值为一个全局变量地址活着外部定义函数的地址
  • .debug
    • 调试符号表，条目是程序中定义的局部变量和类型定义，定义和引用的全局变量；
      • C中，编译器驱动程序 -g才会得到
  • .line
    • C中行号和.text机器指令之间的映射
      • C中，编译器驱动程序 -g才会得到
  • .strtab
    • 字符串表，包括.symtab和.debug节中的符号表，节头的名字；
    • 字符串表就是以null结尾的字符串序列

  未初始化的数据 .bss

  Block Storage Start 沿用

  Better Save Space 理解记忆

7.5 符号和符号表

• 每个可重定位的符号m都有一个符号表，它包含m定义和引用的符号的信息：
  • 由模块m定义，并能被其他模块引用的全局符号
    • 全局链接器符号对应于非静态的C函数和全局变量
  • 由其他模块定义，并被m引用的全局符号
    • 外部符号
    • 对应于其他模块中定义的非静态C函数和全局变量
  • 只被m定义和引用的局部符号
    • static属性的C函数的全局变量，static 存储类修饰的全局变量或者函数，只能在当前文件中被调用和使用；
• 链接器不管理 .symtab不包含 “本地非静态程序变量的任何符号，这些符号在运行时在栈中被管理；
• static属性的本地过程变量（局部变量）不在栈中管理，编译器在.data和.bss中为每个定义分配空间；
  • 并在符号表中，创建一个有唯一名字的本地链接器符号；
  • 在同一个文件中或者说模块中，出现了同名的静态局部变量
    • 编译器会向汇编器输出两个不同名字的局部链接器符号

C中使用static用来**隐藏模块中的内部全局变量和函数声明；

提供了和C++、Java中public private 属性声明一样的功能；

static 的全局变量和函数 = 表示私有

符号表

• 由汇编器构造
• 使用编译器输出到汇编语言.s文件中的符号，汇编器构造ELF符号表；

7.6.2 与静态库链接

• 编译系统提供机制
• 将所有目标模块打包成为一个单独的文件，静态库static library
• 作为链接器的输入，链接器复制被应用程序引用的目标模块，构造一个可执行文件
• 静态库
  • 相关的函数被编译为独立的目标模块，然后封装为一个单独的静态库文件
  • 通过命令，应用可以指定单独的文件名来使用库中定义的函数
  • 链接时，链接器只复制被程序引用的目标模块
• Linux中的静态库
  • Linux中的静态库以存档 archive的特殊文件格式存放在磁盘中
  • 存档文件 archive files，是一组连接起来的可重定向目标文件的集合
  • 有一个头部用来描述每个成员目标文件的大小和位置
  • 存档以.a标识

链接的引用解析：PAGE 476-477

7.6.3 使用静态库来解析引用

7.7 重定位

• 将代码中的每个符号引用和符号定义（输入目标模块的一个符号表条目）关联起来；
• 链接器知道输入目标模块中的代码节和数据节的确切大小；
• 重定向
  • 合并输入模块，并为每个符号分配运行时地址
    • 重定位节和符号定义
      • 合并所有模块中同一类型的节到聚合节
      • 链接器将运行时地址赋给新的聚合节；
      • 赋值给输入模块定义的每个节；
      • 赋值给输入模块定义的每个符号；
      • 完成后，程序中每条指令和全局变量都有唯一的运行时内存地址-物理地址；
    • 重定位节中的符号引用
      • 链接器修改代码节和数据节中对每个符号的引用，使其指向正确的运行时地址；
      • 依赖 ：重定位条目relocation entry

重定位节和符号定义

重定位节中的符号引用

7.7.1 重定位条目

• 汇编器对最终位置未知的目标引用，就会生成一个重定位条目
• 重定位条目用来告诉链接器，就目标文件合成并生成可执行文件时如何修改这个引用
• 代码的重定位条目放在.rel.text
• 已经初始化数据的重定位条目.rel.data中

1. 重定位PC相对引用（程序计数器）：PC当前运行地址的偏移量
2. 重定位绝对引用：绝对地址引用，通过绝对寻址，CPU直接使用再指令中编码的32位值作为有效地址，无需进一步修改；

7.8 可执行目标文件

• 链接器将多个目标文件合并为一个可执行目标文件
• 最终的可执行文件由最初的 一组ASCII 文本文件，转化为了一个二进制文件
• 该二进制文件包含加载程序到内存并运行它所需要的所有信息；

可执行目标文件的格式

	ELF头	1只读内存段
将连续的文件节映射到运行时内存段	段头部分	1只读内存段
	.init	1只读内存段
	.text	1只读内存段 （代码段）
	.rodata	1只读内存段（代码段）
	.data	2读写内存段（数据段）
	.bss	2读写内存段（数据段）
	.symtab	3不加载到内存的符号表和调试信息
	.debug	3不加载到内存的符号表和调试信息
	.line	3不加载到内存的符号表和调试信息
	.strtab	3不加载到内存的符号表和调试信息
描述目标文件的节	节头部表	3不加载到内存的符号表和调试信息

可执行目标文件的格式 类似于 可重定位目标文件的格式

• 可执行文件格式的各节内容

ELF	作为ELF头部，描述文件的总体格式，包括程序的入口点 entry point（程序执行的第一条指令的地址）
.init	.init节定义了一个函数，_init函数，程序的初始化代码会调用_init函数
.text	已编译程序的机器代码
.rodata	只读数据，例如printf语句中的格式串，开关语句跳转表
.data	已经初始化的全局和静态C变量（局部C变量在运行时，保存在栈中，不出现在.data和.bss节中）
.bss	为初始化的全局变量和静态C变量 被初始化为0的全局变量和C变量 在目标文件中这个节不占据实际的空间，仅为一个占位符 运行时，在内存中分配这些变量，初始值为0

• 可执行文件已经**完全链接，且已经完成了重定位，所有.rel节中的重定位条目已经不再需要
• ELF可执行文件被设计的很容易加载到内存
  • 可执行文件的连续的片 （chunk） 被映射到连续的内存段
  • **程序头部表 program header table ** 描述了连续的chunk映射到内存段的映射关系；
    • 分为两部分
      1. 第一段，代码段，有 读/执行 访问权限
         • 指定内存开始地址，和总占用内存的大小n个字节，可执行文件的头的n个字节，包含：ELF头，程序头部表，.init, .text, .rodata节
      2. 第二段，数据段，有 读/写 访问权限
         • 指定内存开始地址，总大小，从目标文件的偏移m处开始的.data节中的mx个字节初始化，该段剩下的字节对应需要被初始化位0的.bss数据节
    • 对于任何段s，链接器必须选择一个起始地址
      • off位目标文件中的段的第一个字节偏移量
      • align为程序头部中指定的对齐
        • 对齐是一种优化，因为虚拟内存的组织方式，为大小位2的幂次的字节片；

7.9 加载可执行目标文件

• shell调用驻留在内存中的加载器 loader 的操作系统代码来运行可执行文件

  涉及到shell和操作系统的交互以及交互方式 「system call」

• 任何Linux程序都可以通过调用execve函数来调用加载器loader

• 加载 (加载器把程序复制到内存并运行的过程)

  • 加载器 loader将可执行目标文件中的代码和数据从磁盘复制到内存中，再通过跳转到程序的第一条指令或者entry point来运行该程序；

• 运行时内存映像

  • 代码段总是从 0x400000 处开始
  • 接着是数据段
  • 运行时堆再数据段之后，通过调用malloc库往上增长
  • 堆后面的区域为共享模块保留
  • 用户栈总是以最大的合法用户地址 2^48 -1 开始，向较小的内存地址增长
  • 栈上的区域，从地址 2^48 - 1 开始，是内核（kernel）中的代码和数据保留；

• 下面内存模型的问题：

  • 栈顶放在64位字长的机器的最大合法用户地址处
  • 堆、数据、代码在下面模型中相邻，实际上.data段有对齐的要求，所有代码段和数据段之间有间隙；
  • 分配栈、共享库、堆段运行时地址的时候，链接器会使用地址空间布局随机化 ASLR
    • ASLR
      • 地址空间布局随机化 （Address-Space Layout Randomization）
      • ASLR技术能够增加攻击一个系统的难度，保证了一定程度的安全；
      • 程序开始时，在栈上分配一段0~n字节之间随机大小的空间；
        • 使用alloca在栈上肥胖指定字节数量的空间
        • 这个空间会导致程序执行时，后续的栈位置发生变化；
        • linux系统的栈随机化
          • 32位系统的随机地址范围为2^23
          • 64位系统的随机地址范围为位2^32
  • 每次程序运行时区域地址都会改变，但是相对位置不变；

高地址	2^48 -1 处开始	内核内存	对用户代码不可见的内存
		用户栈，运行时创建	%rsp 栈指针
		共享库的内存映射区域
		运行时堆 （由程序调用的某个版本的 malloc函数创建）	brk
		读/写段 「.data, .bss」 (已初始化全局变量、静态变量，未初始化全局变量和静态变量) 此处的静态变量：包含1. 全局静态变量，此类变量使用static存储类修饰符修饰后之内在当前所在的模块中使用，或者说只能再所在的c文件中使用，C中的static修饰全局变量相当于声明private属性 2. 本地过程变量的static，也就是函数或者块中声明的静态局部变量，为了舍得所有的函数调用不再分配新的堆空间，并且保持一个值的变量，此变量和auto的局部变量不同，此变量依然在堆中，编译器再.data和.bss中为每个定义分配空间 static属性的本地过程变量（局部变量）不在栈中管理，编译器在.data和.bss中为每个定义分配空间； 并在符号表中，创建一个有唯一名字的本地链接器符号； 在同一个文件中或者说模块中，出现了同名的静态局部变量 编译器会向汇编器输出两个不同名字的局部链接器符号
	0x400000	只读代码段 「.init, .text, .rodata」初始化函数，代码段机器指令代码，格式串和开关语句跳转表
低地址	0

• 详细学习 - 第九章 虚拟内存

Linux系统中的每个程序都运行在一个进程上下文中，有自己的虚拟地址空间；

当shell运行一个程序时，父shell进程生成一个子进程，他是父进程的一个复制；

子进程通过 execve 系统调用启动加载器；

加载器删除子进程现有的虚拟内存段，并创建一组新的代码、数据、堆和栈段；

新的栈和堆段被初始化为0；

通过将虚拟地址空间中的页映射到可执行文件的页大小的片（chunk）；

新的代码和数据段被书痴华为可执行文件的内容；

加载器跳转到_start地址，最终会调用相应的程序的main函数；

加载过程中，只会将“头部信息“从磁盘复制到内存；

CPU引用一个被映射的虚拟内存页时才会进行复制，此时，操作系统利用页面调度机制自动将页面从磁盘传送到内存；

7.10 动态链接共享库

• 共享库 shared library
  • 一个目标模块，运行和加载时，可以加载到任意的内存地址，并和一个在内存中的程序链接起来；这个过程位动态链接 dynamic linking
  • 动态链接器 dynamic linker
  • 共享目标 shared object
  • 在linux系统中通常用.so后缀来表示
• ”共享“方式
  • 给定的文件系统中，一个库只有一个.so文件，所有引用该库的可执行目标文件共享.so文件中的代码和数据；
  • 不会像静态库一样被复制和嵌入到引用的可执行文件中；
  • 在内存中，一个共享库的.text节的一个副本可以被不同的正在运行的进程共享；

第八章，异常流控制

• 控制流
  • 程序计数器中指令地址的过度称为控制转移 control transfer
  • 程序计数器指令地址的过度的序列为处理器的控制流（control flow）
    • 平滑的控制流序列，其中每个指令的地址都是相邻的；
    • 平滑流的突变，通常由跳转， 调用、返回等指令造成
  • 控制流突变
    • 异常控制流 Exceptional Control Flow ECF
    • 发生在计算机系统的各个层次
      • 硬件事件触发控制突然转移到异常处理程序
      • 内核通过上下文切换将控制从一个用户进程转移到另一个用户进程
      • 应用层，进程之间使用信号通信，接受者会将控制转移到信号处理程序；
      • 程序通过回避通常的栈规则，执行到其他函数任意位置的非本地跳转来对错误作出反应；
  • ECF
    • ECF是OS用来实现I/O，进程、虚拟内存的基本机制；
    • 应用程序使用系统调用 （system call）的ECF形式，向系统请求服务；
      • 磁盘写入数据
      • 网络读取数据
      • 创建新进程
      • 终止当前进程
      • 通过系统调用实现
    • ECF是计算机系统实现并发的基本机制；
      • 中断应用程序执行的异常处理程序
      • 时间上重叠执行的进程和线程
      • 中断应用程序执行的信号处理程序；
    • ECF软件异常
      • C++ try catch throw
      • 软件异常允许程序进行非本地跳转，来响应错误；
        • 非本地跳转是一种应用层ECF，C中通过setjmp和longjmp函数提供
    • 各种形式的ECF

8.1 异常

• 异常 exception 就是控制流中的突变，用来响应处理器状态中的某些变化；
  • 状态被编码为不同的位和信号
  • 状态变化称为事件event
  • 与当前指令直接相关
    • 虚拟内存缺页
    • 算术溢出
  • 与当前指令无关
    • 系统定时器信号
    • 一个I/O请求完成
• 事件发生 – 处理器通过异常表 exception table 跳转表，进行一个间接的过程调用 – 异常处理程序 exception handler – 处理完成后
  1. 处理程序将控制返回给当前指令，事件发生时正在执行的指令
  2. 处理程序将控制返回给当前指令的下一条指令，没有发生异常就会执行下一条指令
  3. 处理程序终止被中断的程序

8.1.1 异常处理

• 系统中每一个异常都有一个唯一的非负整数的异常好 exception number
• 处理器相关
  • 被零除
  • 缺页
  • 内存访问违例
  • 断点
  • 算术运算溢出
• 操作系统内核相关
  • I/O设备的信号
• 异常处理表
  • 间接过程调用
• 陷阱
  • 有意的异常，执行一条指令的结果，像中断处理程序一样；
  • 用途
    • 用户程序和内核之间提供一个像过程一样的接口，系统调用
    • 用户程序向系统内核请求服务：
      • read
      • fork （创建新进程）
      • execve
      • exit
    • 为了允许对内核服务的受控的访问，处理器提供一条特殊的“syscall n”指令；
    • 用户程序想要请求服务n时，执行指令 syscall n，就会导致一个异常处理程序的陷阱；
      • 这个处理程序解析参数，并调用适当的内核程序；

完全详细的描述

1. gcc hello.c -o hello.out
2. ./hello.out
3. 过程

设计知识： 编译 -> 汇编 -> 连接 -> 加载 -> 系统调用

过程

运行时栈

栈帧

• 用户栈	-
  参数
  返回地址
  被保存的寄存器
  局部变量
  参数构造区	<-%rsp

• 过程是一种软件中的抽象
• 提供一种封装代码的方式，用一组指定的参数和一个可选的返回值来实现某种功能
• 不同的语言中过程有多重形式
  • 函数 function
  • 方法 method
  • 子例程 subroutine
  • 处理函数 handler
  • 块/闭包 block
• 过程的共同属性包括
  • 传递控制
    • 程序开始阶段，运行时栈的rip（程序计数器指针）指针指向入口函数，然后开始执行，例如执行主函数Q的指令，该指令指向主函数内的过程调用的函数P，这是新的函数P在栈中分配了新的栈帧，该栈帧中的过程返回后，rip指针又指向Q中调用P的那条指令，此时这条指令指向P函数的返回值；
  • 传递数据
  • 分配和释放内存
• C过程调用的关键特性 -> 使用栈数据结构的提供的先进后出的内存管理原则
• 过程在被调用时候，才会在栈中为局部变量分配空间，而过程结束后分配的局部存储空间都会被释放掉；

• 栈和程序寄存器存放着传递控制和数据、分配内存所需要的信息；

• X86_64 栈向底地址增长
• 栈指针%rsp指向栈顶元素
• pushq指令入栈
• popq指令出栈
• 将指针减小一个适当的量可以为没有指定初始值的数据在栈上分配空间 （指针偏移量，变长数组）

• 增加栈指针来释放空间

• 栈帧 （stack frame）：X86_64 过程所需要的存储空间超出寄存器能够存放的大小，就会在栈上分配空间
• 栈通过增加和减小%rsp的大小来释放空间和分配栈帧；
• 当前正在执行的过程的栈总是在栈顶
• 定长栈帧
• 变长栈帧

• 栈帧的实质就是过程因为所需要的寄存器空间不足而在栈顶分配的新的内存空间；内存中一个过程所包含的过程调用和数据及返回；

• 6个或者更少的参数可以直接通过寄存器传递 （6个参数：可以通过寄存器最多传递6个参数，例如整数和指针参数，寄存器只用有特殊的顺序，名字取决于传递的参数的大小）
• 叶子过程：所有局部变量都保存在寄存器中，而且不会调用其他函数的过程
• X86_64 只分配自己所需要的栈帧部分

---

去

csapp.cs.cmu.edu

C中的指针的机器级表示

• 3.10.1