CSAPP读书笔记

计算机系统漫游


信息就是位+上下文

编写的任何一个程序源代码都是文本文件,文本文件以ASCII码或Unicode编码的形式存在硬盘上。本质上来说,这些文件都是二进制 0 1 序列。这些 0 1 能够表示信息,是通过上下文关系来体现的。

程序被其他程序翻译成不同的格式

C语言的源程序要变成可执行程序,要经过一系列的步骤。在linux上通过gcc提供的各种工具将其翻译:
gcc -o hello hello.c
这就能将hello.c源代码翻译成hello可执行程序,具体经过了 预处理 编译 汇编 链接,如下图

  • 预处理
    调用预处理器。根据以字符#开头的命令,修改原始C程序。将所有的头文件展开,将所有的宏定义替换,将所有的注释删除,将所有的条件编译不成立的部分删除。
  • 编译
    调用编译器。将文本文件hello.i翻译成文本文件hello.s,它包含一个汇编语言程序。
    -汇编
    将汇编程序的文本文件翻译成机器语言指令,也就是二进制文件的01序列,把这些指令打包成可重定位目标程序的格式,即hello.o。
  • 链接
    分析各个目标文件之间的依赖关系,将所有用到的目标文件链接起来,重定位各个目标文件中的全局引用。

系统的硬件组成

一个典型的系统硬件组成如下图:

主要有总线,I/O设备,主存,处理器,

高速缓存

现代计算机的运行时间很大一部分是用在数据传递上,所以在各个部分之间增加缓存很重要,缓存用于存储最近被访问的数据,由于程序的局部性原理,这大大提高的程序的速度。

操作系统管理硬件

计算机系统的抽象表示:

  • 进程
    进程是现代操作系统的一个抽象概念,是对一个正在运行的程序的一种抽象。它让程序看起来独占整个系统资源,包括CPU,内存,IO等。多个进程同时运行在系统上时,操作系统要对进程进行调度,当一个进程切换到另一个进程时,要进行上下文切换。
  • 线程
    线程是进程中的一个执行控制流。
  • 虚拟内存
    虚拟内存是一个抽象概念,它为每个进程提供了一个假象,即每个进程都在独占的使用内存。每个进程看到的内存都是一致的,称为虚拟地址空间,下图是Linux进程的虚拟地址空间
  • 文件
    在Linux系统上,所有的东西都被抽象为文件,包括普通文件,存储设备,IO,网络套件字等,对这些东西的读写都能通过统一的接口实现,即文件的读写。

    计算机系统中抽象的重要性

    所有的问题,都能通过添加一个抽象的中间层解决。

第二章 信息的表示和处理


字节顺序

计算机的字节顺序体现在当一个数据需要多个字节存储的时候,这些字节以何种顺序存储。字节顺序分为大端和小端。大端是将高位放在低地址,低位放在高地址,小端相反。大部分系统采用的是小端法,

移位运算

当移位的数量k大于数据自身的位数w时,则移动(k%w)位。
左移,在右端补0
右移,分为算术移位和逻辑移位。对于无符号数都一样,在左端补0。对于有符号数,算术移位补最高位,逻辑移位补0。

整数的表示

那些数据类型的长度,都没有记忆的必要,只要记住计算机如何表示有符号数和无符号数就可以了。

  • 无符号数表示
    就按照二进制的正常位级表示。

    1111 -> 8+4+2+1

  • 有符号数
    最高位表示负的权值,其他的一样。

    1111 -> -8+4+2+1
    1000 -> -8
    0101 -> 4+1

  • 有符号数和无符号数的转换
    相同的长度,保持在位级表示上的一致性。

  • 扩展一个数字的位表示
    无符号数用 0 扩展,有符合数用符号位扩展。
    当不同长度的有符号数和无符号数转换时,先转成相同的长度,再进行类型转换。如:

    short -> unsigned==short -> int -> unsigned

  • 截断数字
    无符号数,直接截断高位
    有符号数,先按无符号数直接截断,然后将最高位转为符号位。

  • 无符号数和有符号数加减法
    记住一条,都按照二进制表示的加法运算,超出表示范围的截断。然后表示对应的无符号数和有符号数。
    减法转成加法做。
    主要有符号数是补码表示。

  • 补码的非
    和正常的数学一样,唯一例外是负数的最大值,非是其本身。

    0X80 -> 0X80

  • 乘除法
    计算机的乘除法都尽量转成加法和移位。

  • IEEE浮点数表示

第三章 程序的机器级表示

前言

这一章主要就是讲在汇编层面看程序,介绍了最新的x86-64架构下的指令集,重点是条件,循环,分支的汇编实现,以及函数调用过程。

零碎的点

  • 重要的寄存器

    • PC寄存器。在x86-64中用%rip表示,给出将要执行的下一条指令在内存中的地址。
    • 16个整数寄存器。分别存储64位的值,这些寄存器可以存储地址或整数数据。
    • 条件码寄存器。都是位存储的标志位,保存最近执行的算术或逻辑指令的状态信息,在条件判断的时候用到。
  • 数据格式
    汇编中以字(WORD)为单位,1,2,4,8字节分别用字节(b),字(w),双字(l),四字(q)表示。

  • 寄存器表示
    为了向后兼容,同一个寄存器都有多个名称,分别支持1, 2, 4, 8个字节操作,如%al, %ax, %eax, %rax分别表示%rax寄存器的1, 2, 4, 8字节。

    • 指令族
      为了对应不同数据长度的操作,每种指令都有一个指令集,用于操作不同大小的数据,如MOV有movb, movw, movl, movq表示对1,2,4,8字节的移动。
      

控制

C语言中的if-else, do-while, while, for, switch,本质上都是用jump跳转实现的,当然switch还涉及到跳转表,稍微复杂一点。

  • 基础
    CPU中维护着一组单个位的条件码寄存器,他们描述了最近的算术或逻辑操作的属性。常用的条件码有:

    1. CF:进位标志。最近的操作使最高位产生了进位。可用来检测无符号数的溢出。
    2. ZF:零标志。最近的操作得出的结果为0.
    3. SF:符号标志。最近的操作得到的结果为负数。
    4. OF:溢出标志。最近的操作导致一个补码溢出。
  • 跳转

  1. 直接跳转
    jmp .L1
    程序会直接跳转到标记为 .L1 的代码段

  2. 间接跳转
    jmp %rax
    用寄存器%rax中的值作为跳转目标
    jmp
    (%rax)
    用%rax中的值作为读地址,从内存中读出跳转目标。

  3. 条件跳转
    指令集中有很多条件跳转指令,通过判断条件码寄存器中的值进行跳转。跳转地址通常为间接地址,也就是相对于当前PC的偏移,这样程序在链接的时候就不需要改。

  4. if - else 实现
    简单的实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // C++
    if (test-expr)
    then-statement
    else
    else-statement
    // 仿汇编形式
    t=test-expr;
    if(!t)
    goto fasle;
    then-statement
    goto done;
    false:
    else-statement
    doen:
  • do-while 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    // C++
    long fact_do(long n)
    {
    long result=1;
    do {
    result *= n;
    n = n -1;
    } while (n > 1);
    return result;

    // 仿汇编
    long fact_do_goto(long n)
    {
    long result = 1;
    loop:
    result *= n;
    n = n - 1;
    if (n > 1)
    goto loop;
    return result;
    }

    // 汇编
    fact_do:
    movl $1, %eax
    .L2:
    imulq %rdi, %rax
    subq $1, %rdi
    cmpq $1, %rdi
    jg .L2
    rep; ret
  • while 实现
    while 的实现和 do-while类似,只不过要在loop前加一次test。

  • for 实现
    for 可以直接翻译成 while
    如:

    1
    2
    for(init-expr; test-expr; update-expr)
    body-statement

翻译成:

1
2
3
4
5
init-expr;
while(test-expr) {
body-statement
update-expr;
}

翻译成伪汇编:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
	init-expr;
goto test;
loop:
body-statement
update-expr;
test:
t=test-expr;
if(t)
goto loop;
// 或者
init-expr;
t=test-expr;
if(!t)
goto done;
loop:
body-statment
update-expr;
t=test-expr;
if(t)
goto loop;
done:

  • switch
    switch 才是重点
    switch通过生成一个跳转表,存放各个代码段的入口地址。首先,条件表达式的负数会自动转为对应的无符号数,并减去所有case 的最小值,也就是这张表维护的是从索引 0 到 max-min 之间的所有地址,空的地址是 default(有) 或 switch-case(没有) 的下一句。执行的时候计算条件表达式的值,先判断是否大于索引最大值,是直接跳到最后,不是就加上跳转表的首地址,直接取出对应的代码段的地址(跳转表放在 .rodata 段,目测在目标文件中在 .text 段)。注意,由于跳转只是跳到代码的入口地址,所以代码段中没有break(goto),程序会顺序运行下去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// C 源码
void switch_eg(long x, long n, long *dest)
{
long val = x;
switch(n) {
case 100:
val *= 13;
break;
case 102:
val += 10;
case 103:
val += 11;
break;
case 104:
case 106:
val *= val;
break;
default:
val = 0;
}
*dest = val;
}

// C 仿汇编
void switch_eg_impl(long x, long n, long *dest)
{
// gcc 提供了引用代码段指针的功能
static void *jt[7] = {
&&loc_A, &&loc_def, &&loc_B,&&loc_C, &&loc_D, &&loc_def, &&loc_D
};
unsigned long index = n -100;
long val;
if(index>6)
goto loc_def;
goto *jt[index];
loc_A:
val = x * 13;
goto done;
loc_B:
x = x+10;
loc_C:
val = x + 11;
goto done;
loc_D:
val = x * x;
goto done;
loc_def:
val = 0;
done:
*dest = val;
}

// 汇编
// void switch_eg(long x, long n, long *dest)
x in %rdi, n in %rsi, dest in %rdx
switch_eg:
subq $100, %rsi
cmpq $6, %rsi
ja .L8
jmp *.L4(, %rsi, 8)
.L3:
leaq (%rdi, %rdi, 2), %rax
leaq (%rdi, %rax, 4), %rdi
jmp .L2
.L5:
addq $10, %rdi
.L6:
addq $11, %rdi
jmp .L2
.L7:
imulq %rdi, %rdi
jmp .L2
.L8:
movl $0, %edi
.L2:
movq %rdi, (%rdx)
ret

// 跳转表
.section .rodata
.align 8
.L4:
.quad .L3
.quad .L8
.quad .L5
.quad .L6
.quad .L7
.quad .L8
.quad .L7
subq

过程

  • 概括
    过程也就是函数调用。过程主要是通过栈帧来实现的。下图是一张栈帧的示意图。

    过程调用要实现数据的传递,控制的传递。函数传参首先使用的是寄存器,x86-64下寄存其最多可以保存6个参数,超过6个要用栈来传递。过程中使用的局部变量也会首先选择寄存器。在函数调用中,要保持调用者的上下文,包括寄存器值,PC等。

  • 控制传递
    调用的时候先把调用语句的下一句的地址入栈,然后跳转到被调用者的入口,执行结束以后,将之前保存的地址出栈,赋值给PC。

  • 数据传递
    传参数首先是用寄存器,最多可以传6个,多于6个的用栈来传。
    返回值用一个寄存器保存,如果返回值很大,那么传参的时候会多传一个指针,且在栈上多开一块空间保存这个返回值,指针指向这个空间,在被调函数里面构造这块空间,并且将指针保持在寄存器中。

  • 栈上的局部存储
    局部变量必须存储在栈上的有几种情况:
    1 寄存器不足够存放所有的本地数据
    2 对一个局部变量使用地址运算符‘&’,
    3 数组或结构
    在栈上分配空间也就是减少栈顶指针的值。

  • 寄存器上的局部存储
    寄存器是对所有过程共享的。但是过程调用的时候要保证返回时能恢复。所以在过程调用时,寄存器的值要保存起来,一部分是调用者保存的,一部分是被调用者保存的,在过程返回时,要恢复原来的值。

数组

对数组元素的引用,就是用指向数组开头的指针加上元素的长度乘以索引。
如有数组 int A[N],访问第 i 个元素,假设A 的地址存在寄存器 a,要取出元素放在寄存器 b,mov (a,i,4) b。

异质的数据结构

  • 结构体
    和数组的访问类似,用结构的头指针加上各个字段的偏移。这个过程在编译期间完成,所以在汇编中就不保持任何数据结构信息了。

  • 数据对齐
    在结构体中,任何字段的起始地址都是自己长度的整数倍,数组按单个元素算,且最终的结构体长度要是结构中最大长度的整数倍。

浮点运算

浮点数用另外一组有别与整数寄存器的寄存器来保存,传递参数的时候也是用另外的一组寄存器,它的操作类似于整数操作,不过用别的指令。

第七章 链接


编译器驱动程序

大多数编译系统提供编译器驱动程序,它代表用户在需要时调用语言预处理器、编译器、汇编器和链接器。

过程:预处理 -> 编译 -> 汇编 -> 链接
相应的文件变化:源文件.c -> 中间文件.i -> 可重定位目标文件.o -> 可执行文件

静态链接

静态链接将多个目标文件组合起来,形成一个可执行文件,主要完成两个任务:

  • 符号解析
    将每个符号引用正好和一个符号定义关联起来。
  • 重定位
    链接其通过把每个符号定义与一个内存位置关联起来,从而重定位这些节,然后修改所有对这些符号的引用,使得它们指向这个内存位置。

可重定位目标文件

典型的ELF格式:

其中几个节的内容:

  • .text:机器代码
  • .rodata:只读数据,比如字面常量字符串和switch语句的跳转表。
  • .data:已初始化的全局和静态C变量
  • .bss:未初始化的全局和静态C变量,以及所有被初始化为0的全局或静态变量。在目标文件中这个节不占据实际的空间,仅仅是一个占位符。
  • .symtab:一个符号表,它存放在程序中定义和引用的函数和全局变量的信息。
  • .rel.text:一个.text节中位置的列表。
  • .rel.data:被模块引用或定义的所有全局变量的重定位信息。

符号和符号表

每个可重定位目标模块 m 都有一个符号表,它包含了 m 定义和引用的符号信息。包括文件内的所有函数,全局变量,带有static的变量,以及引用的外部符号。
符号表中的每一项都是一个结构体,表示一个符号的信息。

符号解析

编译器在遇到一个不再当前模块定义的引用时,会假设在其他模块定义,会生成一个链接器符号表条目,交给链接器处理,如果链接器在各个模块中没有找到定义,就会报出一条错误,终止。

  • 符号多重定义
    在编译时,编译器向汇编器输出每个全局符号,或者是强或者是弱,函数和已初始化的全局变量是强,未初始化的全局变量是弱。Linux根据下面的规则处理符号多重定义:

    不允许有多个同名的强符号;
    如果有一个强符合和多个弱符号同名,选择强符号;
    如果多个弱符号同名,任意选一个。

  • 静态库
    Linux的静态库是一些 .o 目标文件的集合,文件后缀 .a,在文件中有一个头部来描述每个目标文件的大小和位置。

重定位

目标文件合并成可执行文件时,会把各个目标文件的相同的段合并到一起,然后重新定位符号的位置,对于符号的引用,通过编译时产生的重定位表条目来确定。

可执行那个目标文件

格式:

加载

当在shell中运行一个可执行程序,首先调用fork复制一个子进程,然后调用execve将虚拟内存空间中的东西删除,创建新的内存段,做好内存映射,然后将控制转移到_start地址执行。

动态链接(这部分没看懂)

直接看这个吧:http://ybin.cc/compiler/position-independent-code-in-shared-library/

动态链接库后缀为 .so ,使用了位置无关代码技术(PIC)。

  • PIC数据引用
    数据和代码的相对位置是一定的,所以可以通过代码的偏移量来确定数据的位置。

  • PIC函数调用
    延迟绑定。用一个表保持各个函数的地址,出

打桩

感觉有点像windows的钩子。
改变程序中调用的入口,从而改变程序应有的执行流。

异常控制流


异常

异常就是控制流中的突变,用来响应处理器中的某写变化。
事件就是处理器的状态发生了变化。当处理器检测到有事件发生,就会通过一张叫做异常表的跳转表,进行一个间接过程调用,到一个专门设计用来处理这类事件的操作系统子程序(异常处理程序)。
操作系统启动的时候,会产生一张异常表,里面的每个条目对应一个异常处理程序的地址。
异常处理工作在内核模式下。

  • 异常类别
    异常可分为:中断、陷阱、故障、终止。

中断
中断是异步发生的,来自处理器外部的I/O设备的信号的结果。I/O设备向处理器芯片的一个引脚发信号,并将异常号放到系统总线上,来触发中断。其他的异常类型是同步发生的,是执行当前指令的结果。

陷阱和系统调用
陷阱是有意的异常,是执行一条指令的结果,典型应用是 系统调用。比如读一个文件,首先产生系统调用,进入异常处理程序,在这个程序中再查询系统调用表,调用对应的内核函数。

故障
故障由错误引起,从异常处理返回时,回到原指令继续执行(或退出),典型的就是缺页。

终止
是不可恢复的致命错误造成的。

进程

一个逻辑流的执行在时间上与另一个流重叠,称为并发流。

操作系统分为用户模式和内核模式。内核模式享有特权,能执行访问所有的数据和代码。模式是用一个控制寄存器保存的,只有内核态的代码能够修改。用户态可以通过系统调用、故障、中断等进入内核态。

进程控制

从程序员的角度,进程总是处于三种状态:运行,停止,终止。
fork函数调用一次,返回两次,在父进程中返回子进程id,在子进程中返回0。fork建立的子进程几乎但不完全与父进程相同,他们拥有相同的虚拟地址空间,除了部分内核态的东西不同。通过写时复制,直到要改变内存的时候才进行复制。

子进程由于某种原因终止时,内核并不会立即清除它,而是保持成僵死进程,必须要有父进程回收。若父进程已死,则统一变成init进程的子进程。

execve函数在当前进程的上下文中加载并运行一个新进程,execve调用一次,返回0 次。它把当前进程的环境删除,映射新的进程。

信号

信号允许进程和内核中断其他进程
内核会检测进程的未被阻塞的待处理信号的集合,如果是空,继续执行,非空,选择一个信号,内核强制进程接受信号。

第九章 虚拟内存


页表

进程启动时,操作系统都会为进程建立一个页表,主要是虚拟内存到硬盘对应位置的映射关系。下图是页表示意图:

有效位为1表示已分配,0表示未分配。
地址要么表示物理页号,要么表示磁盘地址。

当CPU需要的地址不再页表中,会触发缺页异常,调用异常处理程序,通过系统的调度,把需要的页映射到内存,然后重新来一次。

这几章的内容都不是很理解,所有就简单的记一下

共享文件

内核用三个相关的数据结构来表示打开的文件:描述符表、文件表、v-node表。

  • 每个进程都有它独立的描述符表,它的表项由进程打开的文件描述符来索引,每个打开的描述符表项指向文件表中的一个表项。如标准输入、输出、错误分别是0,1,2.
  • 打开文件的集合是由一张文件表来表示的,所有的进程共享这张表。每个文件表的表项组成包括当前的文件位置、引用计数,以及一个指向v-node表中对应表项的指针。关闭一个描述符会减少相应的文件表表项中的引用计数。当引用计数变为0,内核会删除这个表项。
  • 所有的进程共享这张v-node表。每个表项包含stat结构中的大多数信息。

  • I/O重定向,假如将标准输出定向到一个打开的文件4,那么就是将描述符表中索引为4的内容复制到索引为1的内容。

网络编程