参考博客：https://zhuanlan.zhihu.com/p/653809910

前言

操作系统漫游

  • 这一章没啥重点，就随便写了写笔记
操作系统概述

计算机系统概述

计算机系统的组成

  • 计算机系统是由硬件和软件所组成的，而操作系统是一个软件，是直接与硬件交互的，在操作系统之上运行的软件，才是我们一般说的软件

硬件

  • 中央处理器（CPU）：
    • 早期CPU包括：执行程序指令的核心组件，包括算术逻辑单元（ALU）、控制单元（CU）和寄存器
    • 后来CPU里面又加入了：缓存（Cache）、中断处理单元

  • 内存（Memory）：存储数据和程序的区域，包括RAM（随机存取内存）和缓存
  • 存储设备（storage）：持久性存储数据的设备，如硬盘驱动器（HDD）、固态硬盘（SSD）。注：很多初学者都会将存储设备和内存混为一谈
  • 输入输出设备（I/O Devices）：用于与计算机交互的设备，如键盘、鼠标、显示器、打印机，甚至还有网络等。

image-20240719233340264

软件

  • 软件包括以下几种类型：操作系统、应用程序、编译器、库等。

计算机系统的工作原理

程序的基本概念

  • 程序：存储在磁盘上的静态代码文件
  • 进程：程序在运行时的动态实例，包括程序代码、数据、堆栈和寄存器等。

内存布局

  • 代码段：存放程序代码的区域。
  • 数据段：存放静态数据（如全局变量）的区域。
  • 堆：动态分配的内存区域，由程序运行时管理。
  • 栈：存储局部变量、函数调用信息的区域。

image-20240721184617663

程序计数器

  • 程序计数器（Program Counter,PC）：位于CPU的内部
    • 作用：指示下一条要执行的指令地址。
    • 变化：每次指令执行后，PC会更新到下一条指令的地址。

image-20240721184942627

机器级程序

机器语言和汇编语言

  • 机器语言：计算机能够直接执行的二进制代码。
  • 汇编语言：与机器语言对应的低级编程语言，用助记符代替二进制代码。

指令集架构(ISA)

  • 作用：定义了CPU支持的指令集及语法。（具体了解还需要细读计算机组成原理）
  • 示例：常见的ISA包括x86、ARM等

C语言的机器表示

C语言与机器语言的关系

  • 编译过程：C语言源代码通过编译器转换成机器码，在不同系统上根据不同的编译器进行编译。编译的过程如下图

image-20240721185706857

  • 变量存储：C语言中的变量在内存中如何表示，包括整型、浮点型。

函数调用与返回

  • 调用约定：函数调用时，参数如何传递，返回值如何处理。常见的有Linux的32位传参 64位传参 和Windows下的参数调用

  • 调用栈：函数调用时栈帧的创建和销毁。

  • 详细过程了解：PWN基础 | iyheart的博客2.5函数调用规则

计算机系统中的抽象

抽象层次

  • 硬件抽象：计算机硬件的抽象层次，通过操作系统对硬件进行管理和控制。如：设备驱动程序、虚拟内存、文件系统等
  • 软件抽象：应用程序如何通过操作系统提供的接口进行操作。如：系统调用、进程和线程、库和框架

常见抽象

  • 文件系统：提供对文件的抽象，允许程序以文件的形式存取数据。文件系统是一个计算机中程序数据交互的方式，文件系统是Linux系统的一个核心。
  • 网络协议：网络通信的抽象，允许不同计算机之间进行数据交换。网络协议是计算机与计算机之间数据之间的交互。

计算机系统中的数据表示

数据表示的基本概念

  • 整数表示：
    • 补码表示：用于表示正数和负数，计算机通过补码进行算术运算
    • 溢出：整数运算超出表示范围时发生
  • 浮点数表示：
    • IEEE 754标准：定义浮点数的格式和运算
    • 组成部分：符号位、指数位和尾数（有效数字）
  • 字符编码：
    • ASCII：7位字符编码，支持英文和基本符号
    • Unicode：支持多语言字符集，包括非英文字符。

线程和并发

线程

  • 定义：线程是进程中的一个执行单元，每个线程都有自己的执行栈和程序计数器，但线程间共享进程的资源（如内存）。
  • 多线程编程：
    • 创建线程：使用系统调用或语言提供的线程库创建新线程
    • 同步机制：用于线程间的协调和数据共享，防止数据竞争和同步问题，包括互斥锁、条件变量
    • 线程的生命周期：包括创建、就绪、运行、阻塞、终止转态。

并发

  • 定义：并发是指系统能够同时处理多个任务或线程。通过上下文切换实现伪并行。
  • 上下文切换：操作系统在多个线程间切换执行，为用户程序提供并行处理的感觉。
  • 线程安全：编写正确的并发程序需要确保对共享数据的访问是安全的，防止竞态条件和死锁。

文件

  • 定义：文件系统是操作系统用于管理文件和目录的机制，提供对文件的抽象
  • 文件操作：打开文件：通过系统调用如open打开文件，并获得文件描述符

Amdahl定律

  • 定义：Amdahl定律用于预测通过并行计算提升系统性能的潜力
  • 公式：

image-20240721195226983

image-20240721195703716

  • α：程序中可并行化的部分所占比例。
  • k：并行部分的加速倍数（即处理器数量）。
  • 含义：
    • 非并行部分限制：即使并行化部分加速无限大，整体加速仍受限于串行部分
    • 并行化收益递减：随着处理器数量增加，收益逐渐减少
  • 应用：
    • 设计系统：帮助确定投资并行化是否有效。
    • 性能评估：分析并行化对特定程序的影响。

信息的表示和处理

位运算

整数

  • C语言支持多种整型数据类型——表示有限范围的整数。每种类型都能用关键字来指定大小，这些关键字包括char、short、long，同时还可以指示被表示的数字是非负数或者可能是负数
  • 有符号整型的取值具有不对称性：负数的范围比正数的范围大1
  • 以下为32位机器和64位机器C语言整型数据类型的典型取值范围：
image-20240906172844746 image-20240906172919347

无符号数编码

  • 对于一串二进制的0、1串，都有一个与之对应的无符号10进制数。
  • 对于二进制转换成无符号数的10进制具有如下过程：（都只使用4位二进制进行讲解）
1
2
对于无符号整数最小值0，可以使用二进制：0000表示
对于无符号整数最大值15，可以使用二进制：1111表示

$$
对于二进制转换成10进制的无符号整数
$$

$$
二进制的每一位都可以与等比数列a_n = 2^{n-1}一一对应
$$

$$
（然后在每一位前面加个系数，将加上系数的每一位相加即可得到无符号整数）
$$

  • 例如（默认左边高位右边低位）：
1
2
3
4
5
6
7
8
1111：      1          1           1          1 
		1×2的3次方  1×2的2次方   1×2的1次方    1×2的0次方
则转换成无符号10进制数：1*8+1*4+1*2+1*1=15

再例如：
0101：        0                1                 0             1
		  0×2的3次方         1×2的2次方         0×2的1次方      1×2的0次方
转换成无符号10进制数：0*8+1*4+0*2+1*1=5

image-20240906174728070

有符号数编码

  • 二进制转换成有符号数使用的是补码。之前都是简单的说最高位做为符号位，这种表述感觉会不好理解。

$$
最高位应该理解成-2^{n-1}
$$

  • 这样在计算的时候就可以直接计算了，就不要什么取反+1绕来绕去的

    • 所以有符号整数最小值的二进制表示为1000
    • 最大值表示为0111
    • 如果给你一个二进制求他的补码二进制（取反加一就更容易）
    • 但是一个补码表示的负数（给你二进制）让你转换成10进制就没必要先求补，在转换成10进制正数，再加负号

  • 剩下的也就和无符号数的编码大差不差了

  • 下面是几个二进制转换成有符号整数的例子：

image-20240906191151732

  • 对于补码编码以下几点需要注意一下：
    • 补码的范围是不对称的：|Tmin| = |Tmax| + 1，即Tmin没有与之对应的正数
    • 最大的无符号数值刚好比补码的最大值的两倍多1，Umax = 2Tmax+1
    • -1与Umax有同样的表示，是全1串
    • 数值0在两种表示方式中都是全0串
  • C语言标准并没有要求用补码表示有符号整数，但是所有机器都这么做。
  • 有符号数还有另外两种编码，但是这两种编码都出现了正负0，所以使用补码才避免了出现两个0

image-20240907122902442

无符号与有符号数之间的转换

  • 有符号数和无符号数的转换需要从内存中看，即从位的角度进行分析和解释

    • 当我们定义一个有符号整数（32位）int tu = -1这时我们的内存中tu的位级表示为0XFFFF FFFF
    • 但是当将其转换为无符号数unsigned u = tu，此时u的位级表示仍为0XFFFF FFFF
    • 而tu的值为-1，u的值为4294967295
    • 所以相同位数的有符号数和无符号数的转换，内存是不会变化的，只是编码方式该变了

  • 这里给出有符号数与无符号数之间转换的公式

image-20240909115117904

image-20240909115145542

整数的位扩展

  • 有时需要将整数扩展（增大存储整数的位数，即增大取值范围），但是要保证原来的整数值不变，这就要进行位扩展。
  • 位扩展有：零扩展、符号扩展

零扩展

  • 零扩展比较简单，即扩展位都是0，原来的位保持不变，这里给出书上公式
    • 即将扩展的高位全部置为0，然后原来的低位保持不变
    • 例如：将原来16位无符号数2，位扩展到32位
      • 16位的无符号数这样表示0x0002，扩展到32位后这样表示0x0000 0002

image-20240909115616062

符号扩展

  • 符号扩展，先了解其过程：在汇编里面的算术位移运算就与符号扩展很类似
    • 要扩展的数符号位是0，则扩展的位使用0，原来的位不变
    • 要扩展的数符号位是1，则扩展的位全部置1，原来的位保持不变
    • 例1：扩展4位有符号数-8为8位
      • 4位有符号数-8补码表示为1000，由于符号位是1，扩展的高位全部置1，即1111 1000
    • 例2：扩展4位有符号数2为8位
      • 4位有符号数2补码表示为0010，由于符号位是0，扩展的高位全部置0，即0000 0010
  • 这里给出公式

image-20240909120101101

  • 下面给出数学证明（需要理解一下）

整数的位截断

  • 整数的位截断与整数的位扩展，都要以位的角度来看。

无符号整数的截断

  • 当一个m位的无符号数x被截断为n位（m>n），得到的结果为x mod 2^n。使用模运算即可得到相关结果。
  • 例如：先从位的角度进行分析，再从模的角度进行分析
1
2
3
4
5
6
7
8
9
10
// 当一个8位的无符号整数254，它的位级表示如下
1111 1110
// 当其被截断，高4位被除去，结果的位级表示如下
1110 
// 无符号整数的截断比较容易(无论是从数学角度还是位的角度来看)
// 下面从模的角度看
x = 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1  
// 当x mod 2^4时，高位的能被2^4整除，但是低位的2^4是除不尽的
// 所以就会有如下等式
(2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1) mod 2^4  = (2^3 + 2^2 + 2^1) mod 2^4
  • 书上给了具体的公式

image-20240912092125729

有符号数的截断

  • 有符号数的截断，从位级角度上看是比较容易的，但是在从数学角度上看就比较抽象(主要是很绕)。
  • 这里先通过具体的例子对无符号数进行简单的分析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int x = 53191;		  /*int类型32位*/
short sx = (short) x; /*-12345*/
int y = sx;			  /*-12345*/

// 位级角度先进行分析，53191的32位补码表示为
0000 0000 0000 0000 1100 1111 1100 0111
// 然后进行截断，由32位变成16位
1100 1111 1100 0111
// 由于是补码表示，最高位是1，所以转化为十进制就为
-12345

// 如果从数学角度上看
1. 先将这个数转换成无符号整数
2. 对这个无符号整数进行取模运算，得到结果
3. 将模运算的结果转换成有符号整数
// 分析好这个过程后再来看下面的抽象的数学公式，就会变得比较容易了
// 其实从位级角度上看也经历了这几步骤，只是有些步骤直接被我们忽略了
  • 这里给出书上的有符号整数的截断

image-20240912095001249

整数运算

  • 整数运算大致结构如下

整数运算

无符号数加法

  • 无符号加法较为简单与溢出都是比较简单的运算

  • 这里直接给出公式

image-20240917170742566

  • 这里再附上解释，稍微理解一下即可

image-20240917170841416

  • 所以在检查是否有溢出，我们可以从俩个角度判断：
    • 第一个角度是从flag寄存器中判断，该寄存器被称为标志寄存器，其中有一位就是专门用来判断整数是否有溢出
    • 第二个角度比较结果与俩个加数中的其中一个，如果结果大就没溢出，反之就溢出。

无符号数求反

浮点数

  • 浮点数的表示形式基本上是使用V = x*2^y，这种形如2进制的科学计数法来表示。所以浮点数可以表示很大的数字，也可以表示很接近零的数字，但是使用浮点数表示精度可能会缺失
  • 目前一般计算机都采用IEEE754这个浮点数标准

二进制小数

  • 我们用十进制小数类比二进制小数
  • 十进制小数：123456.78912，这个表示的就是

$$
110^5+210^4+310^3+410^2+510^1+610^0+710^{-1}+810^{-2}+910^{-3}+110^{-4}+2*10^{-5}
$$

  • 所以10进制小数可以表示为：其中d_i的取值可以在0-9

$$
d_nd_{n-1}…d_1d_0.d_{-1}d_{-2}…d_{-n}
$$

$$
d_n10^n+d_{n-1}10^{n-1}+…+d_110^{1}+d_010^{0}+…+d_{-1}*10^{-1}+…+d_{-n}*10^{-m}
$$

  • 所以2进制表示也和10进制表示类似，其中b_i的取值只能是1或者0，点左边用2的非负幂表示，点右边的使用2的负幂表示

$$
d_n, d_{n-1}, …, d_1, d_0, d_{-1}, …, d_{-m}
$$

$$
d_n * 2^n + d_{n-1} * 2^{n-1} + … + d_1 * 2^1 + d_0 * 2^0 + d_{-1} * 2^{-1} + … + d_{-m} * 2^{-m}
$$

  • 其中二进制小数也满足左移和右移，向左移动1位就表示乘2，向右移动1位就表示除以2,例如：
十进制 二进制
23/4 101.11
23/8 10.111
23/16 1.0111
  • 这种2进制表示存在着缺陷，它只能表示形如下图这样的有理数：

$$
\frac{x}{2^k}
$$

  • 不满足下述形式的数需要循环重复位才能被准确表示（即就行10进制表示的无限循环小数那样循环）。形如：0.1111111...111的数表示的是刚好小于1的数。例如：0.11111表示63/64,我们将这样的形式简写成1.0-ε

浮点数

  • 浮点数以类似于科学计数法的表示方法在计算机中来表示数，浮点数的形式如下：其中S为符号位

$$
(-1)^SM2^E
$$

  • 在内存中，S、M（frac）、E（exp）的表示如下图所示：
    • S表示的是符号位
    • exp编码了E，注意是编码了E。具体编码之后再说明
    • frac编码了尾数，注意这里也只是编码。具体实现之后再说

image-20241017211227882

  • 一般来说IEEE提供了两种不同的浮点数，单精度浮点数32位和双精度浮点数64位，其他的还有一个Intel扩展精度

image-20241017211811620

  • 这种浮点数的表示书上被分为三种规格化的表示、非规格化的表示、特殊值，``规格化的表示其实就是一般情况，接下来会具体的讲解，非规格化的表示和特殊值`其实就是浮点表示的一些特殊情况。（下面都以单精度32位浮点数表示，这里注意：下面讲的E和exp、M和frac代表的含义是不一样的）

    • 规格化表示：
      • exp的位模式即不全为0，也不全为1。我们将exp的那一块可以看做无符号数编码，由于无符号编码没办法表示负指数，所以就设置了一个偏置值(Bias)。偏置值一般为2的k-1次幂-1，单精度为127,双精度为1023。
        • 这样我们exp中如果编码结果为1,那么E就为1-127=-126。所以就可以表示-126次幂，即表示负次幂，同时也保证了E=0是这个次幂范围的中位数
      • frac的位模式，表示的是小数点右边的数。即：frac为100000001，则表示0.100000001，但是实际的M这边默认了小数点左边的数为1，即M表示为1.100000001，这样就可以节省存储一个1的空间

    示例：将F=15213.0进行规格化的单精度表示

    image-20241017223649565

    • 非规格化表示：功能1：可以表示0 功能2：可以表示非常接近0的数
      • exp为全0，但是E=1-bais，这里是为了让非规格化能平滑的转换为规格化，才会这样定义E的，原因自己去了解
      • M的位表示与frac相同，去除了隐含的1
      • 在浮点表示中+0.0和-0.0表示的是不一样的
      • 特殊情况：
        • 符号位为0，exp全0，frac全0，则值为0，这个表示的是+0.0
        • 符号位为1，exp全0，frac全0，则值也为0，这个表示的是-0.0
    • 特殊值：
      • exp全为1的情况
      • 特殊情况有以下
        • exp全为1，frac全为0，表示无穷大的值
        • exp全为1，frac为非0，代表非数字，使用NaN来表示，打印在屏幕是的结果也是NaN，这个值代表了没有答案

image-20241017223720641

image-20241017223736422

  • 书上举例了一个8精度的浮点数可以认真看看，这里也展现了平滑过渡的情况，有助于我们理解exp全0的情况下，为什么E=1-bias

image-20241017224607914

浮点数的舍入*

  • 向偶舍入，这是IEEE制定的默认舍入规则，通过一张图来对比一下向偶数舍入、向零舍入、向下舍入、向上舍入
  • 向偶舍入的中文概括就是，四舍六入，五留双

image-20241017232538672

浮点运算

  • 浮点数的乘法规则如下：
    • 符号位将是两个浮点数符号位异或值
    • 尾数就是m1和m2
    • 指数就为俩个指数e1和e2的和
    • 当结果m＞2时，我们就需要将m的结果向右位移（即除以2），同时增加一个指数位，从而达到让尾数在1和2的范围内
    • 指数E超出范围将溢出到无穷大
    • M太多位就要使用向偶舍入
  • 浮点数加法规则如下：（浮点数不满足结合律）
    • 浮点运算需要对齐小数点，在这种情况下可能会造成一些精度是损失

单、双精度与整数的转换

其他知识

Lab

程序的机器级表示

导读

  • 机器级编程包含了两种含义，一个是可以直接在机器上运行的二进制指令，另一个是汇编语言。
  • 历史上出现很多知名的指令集架构，Alpha、SPARC、PowerPC、Mips等，但是今天最流行的指令架构是x86(-64)、ARM、RISC-V，本章主要聚焦在x86(-64)上，指令集架构(ISA)的地位非常重要，就在这里，软件遇见了硬件
  • x86汇编语言，两种格式的汇编形式，汇编寄存器。
  • 32位和64位的函数调用，递归函数的调用过程
  • C语言的数据在机器级别中如何表示，结构体、数组、指针，内存对齐等
  • 内存布局，栈、堆、数据段、代码段（虚拟内存），缓冲区溢出问题
  • Linux下的栈保护机制
  • 本章实验对于pwn手来说太熟悉了，栈溢出rop编程，进阶版的就是ret2libc

基本概念

  • Instructure Set Architecture(ISA):指令集架构（包括指令规格，寄存器等），简称ISA，它是软硬件之间的“合同”
  • Mircoarchitecture:指令集架构的具体实现方式（比如流水线级数、缓存大小等），它是可变的
  • Machine Code：机器码，也就是机器可以直接执行的二进制指令
  • Assembly Code：汇编码，也就是机器码的文本形式（主要给人类阅读）

C程序汇编

  • C程序的汇编角度，就是将C语言和汇编语言对照着看，更有助于理解C语言和汇编语言（原来以为是单纯的介绍汇编和我们汇编课一样，但是听了视频和看书之后才发现还是有点区别的），这些汇编代码一般都是我们写好的C语言程序，然后使用gcc编译器编译出来的

  • x86-64的汇编任何计算，如果结果是32位的结果，它会把寄存器的其余32位设置为0

  • CSAPP都是使用AT&T格式，与之前汇编课使用Intel格式不同，刚好我也熟悉一下AT&T格式

关系运算

  • 有如下的c语言代码
1
2
3
4
int gt(long x, long y)
{
	return x > y;
}
  • 该语句的汇编表示为
1
2
3
4
cmp %rsi, %rdi           #compare x:y
	setg  %al			 #Set when >
	movzbl %al,%eax 	 #Zero rest of %rax
	ret

分支结构

  • 下面是C语言中实现两数差的绝对值的函数
1
2
3
4
5
6
7
8
9
long absdiff(long x,long y)
{
	long result;
	if (x > y)
		result = x - y;
	else
		result = y - x;
	return result;
}
  • 该函数对应的汇编如下：
1
2
3
4
5
6
7
8
9
10
absdiff:
	cmpq	%rsi, %rdi # x:y
	jle		.L4
	movq	%rdi,%rax
	subq	%rsi,%rax
	ret
.L4:				   # x <= y
	movq 	%rsi,%rax
	subq	%rdi,%rax
	ret
  • gcc编译时，条件语句还有一种写法，先将结果计算好再进行比较，没有了跳转语句
1
2
3
4
5
6
7
8
absdiff:
	movq %rdi,%rax   #x
	subq %rsi,%rax   #result = x-y
	movq %rsi,%rdx   
	subq %rdi,%rdx   #eval = y - x
	cmpq %rsi,%rdi   #x:y
	cmovle %rdx,%rax #if <=, result = eval
	ret

循环语句

  • 该语句的c代码有三种形式，分别是while形式，goto形式和for形式

  • while形式如下：

1
2
3
4
5
6
7
8
9
10
long pcount_do(unsigned long x)
{
	long result = 0;
	do
	{
		result += x & 0x1;
		x >>=1;
	} while(x);
	return result;
}
  • 对应汇编形式：
1
2
3
4
5
6
7
8
movl $0,%eax		 # result = 0
.L2:				 # loop:
	movq %rdi,%rdx	 
	andl $1,%edx	 # t = x & 0x1
	addq %rdx,%rax	 # result += t
	shrq %rdi		 # x>>1
	jne .L2			 # if(x) goto loop
	ret
  • goto形式：
1
2
3
4
5
6
7
8
9
10
long pcount_goto(unsigned long x)
{
    long result = 0;
loop:
    result += x & 0x1;
    x >>= 1;
    if(x)
        goto loop;
    return result;
}
  • for形式：
1
2
3
4
5
6
7
8
9
10
11
12
#define WSIZE 8*sizeof(int)
long pcount_for(unsigned long x)
{
	size_t i;
	long result = 0;
	for(i=0; i<WSIZE;i++)
	{
		unsigned bit = (x >> i) & 0x1;
		result += bit;
	}
	return result;
}

switch汇编

  • 这里给出个switch的C语言程序
1
2
3
4
5
6
7
8
9
long switch_eg(long x,long y,long z)
{
    long w = 1;
    switch(x)
    {
            ...
    }
    return w;
}
  • 汇编形式：汇编形式的switch语句，gcc会编译出一个跳表，指定所跳到的位置
    • 如果只有case 0和case 1000000，存在这中间所有值都要建表
1
2
3
4
5
switch_eg:
	movq %rdx,%rcx
	cmpq $6,%rdi  # x:6
	ja .L8		  # use default
	jmp *.L4(,%rdi,8) # goto *JTab[x]

image-20241022221127552

image-20241022221314682