computer_systems

CSAPP：一封献给所有CSE学子的情书

本文是对Kcxain大佬的拙劣模仿

第1章 概述

1.1 Hello简介

hello 程序的生命周期是从一个高级 C 语言程序开始的。为了在系统上运行 hello.c 程序，每条 C 语句都必须被其他程序转化为一系列的低级机器语言指令。这样的转化成为编译，最后得以作为进程在计算机系统中运行，也就是 P2P 过程。

hello 的 P2P 过程是 gcc 调用 cpp(预处理器)/cc1(编译器)/as(汇编器)/ld(连接器)，将 C 语言源文件预处理、编译、汇编、链接，最终生成可执行文件保存在磁盘中。

编译系统

hello 的 020 是 hello 可执行目标程序从运行到最后被回收的过程。在 Shell 中运行该程序时，Shell 调用 fork 函数创建子进程，创建完毕后，操作系统内核提供的 execve 函数会创建虚拟内存的映射，即 mmp，然后开始加载物理内存，进入到 main 函数当中执行相关的代码，打印出信息。在进程中，TLB、4级页表、3级 Cache，Pagefile等等设计会加快程序的运行。程序运行完成后，Shell 回收子进程，操作系统内核删除相关数据结构，释放其占据的资源。至此，hello 的一生就结束了。

1.2 环境与工具

1.2.1 操作系统

Windows 11 21H2、Windows Subsystem for Linux2(Ubuntu 18.04 LTS)

1.2.2 开发工具

vscode、gcc、gdb

1.3中间结果

文件 作用
hello.c 源代码
hello.i 预处理后的代码
hello.s 汇编代码
hello.o 可重定位目标文件
hello.o.elf.txt hello.o的ELF
hello.o.s hello.o反汇编后的代码
hello 链接后的可执行目标文件
hello.elf.txt hello的ELF
obj_hello.s hello的反汇编代码

1.4 本章小结

本章介绍了hello的P2P和020过程，描述了使用的环境与工具，并列出了生成的中间结果文件以及它们的作用

第2章 预处理

2.1 预处理的概念与作用

2.1.1 What

对源文件进行一些文本方面的操作，比如文本替换、文件包含、删除部分代码等，

2.1.2 预处理的作用

预处理根据以字符 # 开头的命令，修改原始的 C 程序。比如我们初学 C 语言时记忆最深刻的代码：

1
#include<stdio.h>

它就利用了预处理：引用头文件。它告诉预处理器读取系统头文件 stdio.h 的内容，预处理器把它插入程序文本中。

2.2 linux下的预处理

linux下使用gcc预处理的命令为：

1
gcc –E hello.c –o hello.i

-E 表示只激活预处理过程

2.3 Hello的与处理结果解析

2.3.1 生成文件对比

hello.c 源码

hello.c

打开生成的 hello.i 文件，发现有 3060 行，并且我们原始的main代码部分被放在最后

hello.i

2.3.2 hello.i文件解析

  1. 外部库文件
  2. 首先。开始部分有一系列外部库.h文件路径
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
# 1 "hello.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 31 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 32 "<command-line>" 2
# 1 "hello.c"

# 1 "/usr/include/stdio.h" 1 3 4
# 27 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/x86_64-linux-gnu/bits/libc-header-start.h" 1 3 4
# 33 "/usr/include/x86_64-linux-gnu/bits/libc-header-start.h" 3 4
# 1 "/usr/include/features.h" 1 3 4
# 424 "/usr/include/features.h" 3 4
# 1 "/usr/include/x86_64-linux-gnu/sys/cdefs.h" 1 3 4
# 427 "/usr/include/x86_64-linux-gnu/sys/cdefs.h" 3 4
# 1 "/usr/include/x86_64-linux-gnu/bits/wordsize.h" 1 3 4
# 428 "/usr/include/x86_64-linux-gnu/sys/cdefs.h" 2 3 4
# 1 "/usr/include/x86_64-linux-gnu/bits/long-double.h" 1 3 4
# 429 "/usr/include/x86_64-linux-gnu/sys/cdefs.h" 2 3 4
# 425 "/usr/include/features.h" 2 3 4
# 448 "/usr/include/features.h" 3 4
# 1 "/usr/include/x86_64-linux-gnu/gnu/stubs.h" 1 3 4
# 10 "/usr/include/x86_64-linux-gnu/gnu/stubs.h" 3 4
# 1 "/usr/include/x86_64-linux-gnu/gnu/stubs-64.h" 1 3 4
# 11 "/usr/include/x86_64-linux-gnu/gnu/stubs.h" 2 3 4
# 449 "/usr/include/features.h" 2 3 4
# 34 "/usr/include/x86_64-linux-gnu/bits/libc-header-start.h" 2 3 4
# 28 "/usr/include/stdio.h" 2 3 4


# 1 "/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h" 1 3 4
# 216 "/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h" 3 4

# 216 "/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h" 3 4
typedef long unsigned int size_t;
# 34 "/usr/include/stdio.h" 2 3 4

# 1 "/usr/include/x86_64-linux-gnu/bits/types.h" 1 3 4
# 27 "/usr/include/x86_64-linux-gnu/bits/types.h" 3 4
# 1 "/usr/include/x86_64-linux-gnu/bits/wordsize.h" 1 3 4
# 28 "/usr/include/x86_64-linux-gnu/bits/types.h" 2 3 4
  1. 数据类型名称替换

接下来是一堆 typedef，前面是我们编写代码时使用的标准数据类型，而后面的那些别名就是上述讲到的引入的头文件中使用的类型定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef unsigned char __u_char;
typedef unsigned short int __u_short;
typedef unsigned int __u_int;
typedef unsigned long int __u_long;


typedef signed char __int8_t;
typedef unsigned char __uint8_t;
typedef signed short int __int16_t;
typedef unsigned short int __uint16_t;
typedef signed int __int32_t;
typedef unsigned int __uint32_t;

typedef signed long int __int64_t;
typedef unsigned long int __uint64_t;

打开一个头文件，其也有类似的行为

  1. 内部函数声明

中间部分是很多内部函数的声明，包括系统内核提供的接口的封装：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
extern int vscanf (const char *__restrict __format, __gnuc_va_list __arg)
     __attribute__ ((__format__ (__scanf__, 1, 0))) ;


extern int vsscanf (const char *__restrict __s,
      const char *__restrict __format, __gnuc_va_list __arg)
     __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__format__ (__scanf__, 2, 0)));
# 443 "/usr/include/stdio.h" 3 4
extern int vfscanf (FILE *__restrict __s, const char *__restrict __format, __gnuc_va_list __arg) __asm__ ("" "__isoc99_vfscanf")



     __attribute__ ((__format__ (__scanf__, 2, 0))) ;
extern int vscanf (const char *__restrict __format, __gnuc_va_list __arg) __asm__ ("" "__isoc99_vscanf")

     __attribute__ ((__format__ (__scanf__, 1, 0))) ;
extern int vsscanf (const char *__restrict __s, const char *__restrict __format, __gnuc_va_list __arg) __asm__ ("" "__isoc99_vsscanf") __attribute__ ((__nothrow__ , __leaf__))



     __attribute__ ((__format__ (__scanf__, 2, 0)));
# 477 "/usr/include/stdio.h" 3 4
extern int fgetc (FILE *__stream);
extern int getc (FILE *__stream);
  1. 主体代码
1
2
3
4
5
6
7
8
9
10
11
12
13
int main(int argc,char *argv[]){
    int i;
    if(argc!=4){
        printf("用法： Hello 学号 姓名 秒数！\n");
        exit(1);
    }
    for(i=0;i<8;i++){
        printf("Hello %s %s \n",argv[1],argv[2]);
        sleep(atoi(argv[3]));
    }
    getchar();
    return 0;
}

2.4 本章小结

本章介绍了 hello.c 的预处理过程，并分析了预处理的结果文件 hello.i。

从程序员的角度来说，利用宏定义指令可以让我们轻松写出可读性更好的代码，利用条件编译指令可以让我们更加方便快捷的调试代码。

从hello程序的角度来说，hello.c 是残缺的，不完整的，预处理阶段使它健全了四肢，得以最终运行在操作系统的上下文中。

第3章 编译

3.1 编译的概念与作用

3.1.1 什么是编译

汇编语言是对硬件的抽象，而 C 语言又是对汇编语言的抽象，C 语言对人友好，但对机器并不友好。编译阶段正是把完整的代码 hello.i 翻译成对应的汇编语言程序 hello.s

3.2 Ubuntu下编译的命令

Linux下使用 gcc 编译的命令为：

1
gcc -S hello.i -o hello.s

-S 表示只激活到编译过程

3.3 Hello的编译结果解析

hello.i 编译生成了对应的汇编代码，在这一节中，我将对 C 语言中数据类型及各式操作如何编译到汇编代码中逐个解析

3.3.1 常量

1.字符型常量

1
2
3
4
if(argc!=4){
       printf("用法： Hello 学号 姓名 秒数！\n");
       exit(1);
   }

printf打印了一个字符串，这个字符串常量存在.LC0中：

1
2
.LC0:
	.string	"\347\224\250\346\263\225\357\274\232 Hello \345\255\246\345\217\267 \345\247\223\345\220\215 \347\247\222\346\225\260\357\274\201"
  1. 其他常量

还有一些其它常量直接在汇编代码中以立即数的身份出现，例如这段代码，有一个整型常量4

1
2
3
4
if(argc!=4){
       printf("用法： Hello 学号 姓名 秒数！\n");
       exit(1);
   }

它对应的汇编代码如下：

1
2
3
4
cmpl	$4, -20(%rbp)
je	.L2
leaq	.LC0(%rip), %rdi
call	puts@PLT

cmpl 比较 argc 与 4 是否相等，如果不相等，才把上述的字符串常量加载到寄存器

3.3.2 变量与运算

  1. 局部变量

局部变量存储在寄存器或栈中。

hello.c中有一个局部变量：

局部变量

i 是在一个 for 循环语句中作为循环变量，这段代码如下：

1
2
3
4
5
.L3:
	cmpl	$7, -4(%rbp)
	jle	.L4
	call	getchar@PLT
	movl	$0, %eax

可以看到，i 存储在栈中。

  1. 算数操作

同时在上述的 for 循环中，局部变量 i 的值每次加1，这个运算就由 addl 指令来完成：

1
addl	$1, -4(%rbp)

3.3.3 数组/指针操作

main 函数的参数中，有一个字符串数组：

1
int main(int argc,char *argv[]){

其中，argc 是输入的参数的个数，也就是字符串数组 argv 中的元素个数。

根据下面这行代码：

1
sleep(atoi(argv[3]));

其对应汇编代码

1
2
3
4
5
6
7
movq	-32(%rbp), %rax
addq	$24, %rax
movq	(%rax), %rax
movq	%rax, %rdi
call	atoi@PLT
movl	%eax, %edi
call	sleep@PLT

%rdi 是第一个参数寄存器，也就是存储函数 atoi 调用的参数，所以栈中 %rbp-8 指向的栈空间存的内容就是 argv[3] 的地址

同理，观察以下代码：

1
2
3
4
5
6
7
8
9
10
11
.L4:
	movq	-32(%rbp), %rax
	addq	$16, %rax
	movq	(%rax), %rdx
	movq	-32(%rbp), %rax
	addq	$8, %rax
	movq	(%rax), %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rdi
	movl	$0, %eax
	call	printf@PLT

经过分析，分别找到 argv[1] 的地址存放在 %rbp-16 指向的栈空间中，argv[2] 的地址存放在 %rbp-24 存放的栈空间中。

3.3.4 控制转移

同样还是以上述那段 for 循环的代码为例，循环变量 i 从 0 开始，每次循环都要加 1，并在循环开始判断 i<8，对应的汇编代码就是用 cmpl 指令，判断 i 是否小于等于 7，如果是，则继续执行循环体中的内容，如果不是则跳出循环。

3.3.5 函数调用与返回

  1. main函数

传入参数为 argc，和 argv，为系统调用，且参数从 Shell 中传入，返回值设置为 0

  1. printf函数

通过设置寄存器 %rdi 和 %rsi 的值来传入参数并调用

1
2
3
4
5
6
7
8
9
10
11
.L4:
	movq	-32(%rbp), %rax
	addq	$16, %rax
	movq	(%rax), %rdx
	movq	-32(%rbp), %rax
	addq	$8, %rax
	movq	(%rax), %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rdi
	movl	$0, %eax
	call	printf@PLT
  1. exit函数

通过设置寄存器 %rdi 和 %rsi 的值来传入参数并调用

1
2
3
4
leaq	.LC0(%rip), %rdi
call	puts@PLT
movl	$1, %edi
call	exit@PLT
  1. atoi函数

将一个字符串的首地址赋给 %rdi 调用，函数返回这个字符串转成的整数值，存放在字符串 %eax

1
2
3
4
5
6
7
8
movq	-32(%rbp), %rax
addq	$24, %rax
movq	(%rax), %rax
movq	%rax, %rdi
call	atoi@PLT
movl	%eax, %edi
call	sleep@PLT
addl	$1, -4(%rbp)

3.4 本章小结

本章介绍了从 hello.i 文件编译成 hello.s 文件的过程，以及原始的 .c 文件中各部分变量、常量、控制转移以及函数调用在汇编语言中是什么样子。

接下来，只需要将 hello.s 稍加改造（汇编），就能让操作系统、让机器读懂它！

第4章 汇编

4.1 汇编的概念与作用

所谓汇编，就是汇编器 (as) 将 hello.s 翻译成机器语言指令，把这些指令打包成可重定位目标程序的格式，并将结果保存在文件 hello.o 中，hello.o 是一个二进制文件。

4.2 Ubuntu下的汇编命令

Linux 下使用 gcc 汇编的命令为：

1
gcc -C hello.s -o hello.o

-C 表示只激活到汇编过程

4.3 可重定位目标elf格式

hello.o 文件在 x86-64 Linux 和 Unix 系统中使用可执行可链接格式即 (ELF)，典型的 elf 可重定位目标文件格式如下：

elf格式

4.3.1 ELF头

使用 readelf -h hello.o 查看 ELF 头，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
voidsolar@admin:~/test$ readelf -h hello.o
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Shared object file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x6a0
  Start of program headers:          64 (bytes into file)
  Start of section headers:          6664 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         9
  Size of section headers:           64 (bytes)
  Number of section headers:         29
  Section header string table index: 28

EFL 头以 16 字节的序列 Magic 开始，这个序列描述了生成该文件的系统的字的大小和字节顺序，ELF 头剩下的部分包含帮助链接器语法分析和解释目标文件的信息，其中包括 ELF 头的大小、目标文件的类型、机器类型、字节头部表（section header table）的文件偏移，以及节头部表中条目的大小和数量等信息。

EFL头中还包括程序的入口点 (entry point)，也就是程序运行时要执行的第一条指令的地址为 0x6a0，可以查看hello.o 的反汇编代码，程序运行时的第一条指令的地址确实为 0x6a0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
00000000000006a0 <_start>:
 6a0:	31 ed                	xor    %ebp,%ebp
 6a2:	49 89 d1             	mov    %rdx,%r9
 6a5:	5e                   	pop    %rsi
 6a6:	48 89 e2             	mov    %rsp,%rdx
 6a9:	48 83 e4 f0          	and    $0xfffffffffffffff0,%rsp
 6ad:	50                   	push   %rax
 6ae:	54                   	push   %rsp
 6af:	4c 8d 05 fa 01 00 00 	lea    0x1fa(%rip),%r8        # 8b0 <__libc_csu_fini>
 6b6:	48 8d 0d 83 01 00 00 	lea    0x183(%rip),%rcx        # 840 <__libc_csu_init>
 6bd:	48 8d 3d e6 00 00 00 	lea    0xe6(%rip),%rdi        # 7aa <main>
 6c4:	ff 15 16 09 20 00    	callq  *0x200916(%rip)        # 200fe0 <__libc_start_main@GLIBC_2.2.5>
 6ca:	f4                   	hlt    
 6cb:	0f 1f 44 00 00       	nopl   0x0(%rax,%rax,1)

4.3.2 节头部表

使用 readelf -S hello.o 命令查看节头部表，如下：

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
There are 29 section headers, starting at offset 0x1a08:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .interp           PROGBITS         0000000000000238  00000238
       000000000000001c  0000000000000000   A       0     0     1
  [ 2] .note.ABI-tag     NOTE             0000000000000254  00000254
       0000000000000020  0000000000000000   A       0     0     4
  [ 3] .note.gnu.build-i NOTE             0000000000000274  00000274
       0000000000000024  0000000000000000   A       0     0     4
  [ 4] .gnu.hash         GNU_HASH         0000000000000298  00000298
       000000000000001c  0000000000000000   A       5     0     8
  [ 5] .dynsym           DYNSYM           00000000000002b8  000002b8
       0000000000000120  0000000000000018   A       6     1     8
  [ 6] .dynstr           STRTAB           00000000000003d8  000003d8
       00000000000000a1  0000000000000000   A       0     0     1
  [ 7] .gnu.version      VERSYM           000000000000047a  0000047a
       0000000000000018  0000000000000002   A       5     0     2
  [ 8] .gnu.version_r    VERNEED          0000000000000498  00000498
       0000000000000020  0000000000000000   A       6     1     8
  [ 9] .rela.dyn         RELA             00000000000004b8  000004b8
       00000000000000c0  0000000000000018   A       5     0     8
  [10] .rela.plt         RELA             0000000000000578  00000578
       0000000000000090  0000000000000018  AI       5    22     8
  [11] .init             PROGBITS         0000000000000608  00000608
       0000000000000017  0000000000000000  AX       0     0     4
  [12] .plt              PROGBITS         0000000000000620  00000620
       0000000000000070  0000000000000010  AX       0     0     16
  [13] .plt.got          PROGBITS         0000000000000690  00000690
       0000000000000008  0000000000000008  AX       0     0     8
  [14] .text             PROGBITS         00000000000006a0  000006a0
       0000000000000212  0000000000000000  AX       0     0     16
  [15] .fini             PROGBITS         00000000000008b4  000008b4
       0000000000000009  0000000000000000  AX       0     0     4
  [16] .rodata           PROGBITS         00000000000008c0  000008c0
       000000000000003e  0000000000000000   A       0     0     8
  [17] .eh_frame_hdr     PROGBITS         0000000000000900  00000900
       000000000000003c  0000000000000000   A       0     0     4
  [18] .eh_frame         PROGBITS         0000000000000940  00000940
       0000000000000108  0000000000000000   A       0     0     8
  [19] .init_array       INIT_ARRAY       0000000000200d90  00000d90
       0000000000000008  0000000000000008  WA       0     0     8
  [20] .fini_array       FINI_ARRAY       0000000000200d98  00000d98
       0000000000000008  0000000000000008  WA       0     0     8
  [21] .dynamic          DYNAMIC          0000000000200da0  00000da0
       00000000000001f0  0000000000000010  WA       6     0     8
  [22] .got              PROGBITS         0000000000200f90  00000f90
       0000000000000070  0000000000000008  WA       0     0     8
  [23] .data             PROGBITS         0000000000201000  00001000
       0000000000000010  0000000000000000  WA       0     0     8
  [24] .bss              NOBITS           0000000000201010  00001010
       0000000000000008  0000000000000000  WA       0     0     1
  [25] .comment          PROGBITS         0000000000000000  00001010
       0000000000000029  0000000000000001  MS       0     0     1
  [26] .symtab           SYMTAB           0000000000000000  00001040
       0000000000000660  0000000000000018          27    43     8
  [27] .strtab           STRTAB           0000000000000000  000016a0
       0000000000000263  0000000000000000           0     0     1
  [28] .shstrtab         STRTAB           0000000000000000  00001903
       00000000000000fe  0000000000000000           0     0     1

节头部表描述了 hello.o 中文件中各个节的语义，包括节的类型、位置和大小等信息。由于这是可重定位目标文件，所以每个节的地址都从 0 开始。

它还利用 Flags 描述各个节的读写权限：

1
2
3
4
5
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

4.3.3 符号表

使用 命令查看 .symtab 节中的 ELF 符号表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Symbol table '.dynsym' contains 12 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_deregisterTMCloneTab
     2: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND puts@GLIBC_2.2.5 (2)
     3: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND printf@GLIBC_2.2.5 (2)
     4: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.2.5 (2)
     5: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND getchar@GLIBC_2.2.5 (2)
     6: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND __gmon_start__
     7: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND atoi@GLIBC_2.2.5 (2)
     8: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND exit@GLIBC_2.2.5 (2)
     9: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND _ITM_registerTMCloneTable
    10: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND sleep@GLIBC_2.2.5 (2)
    11: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@GLIBC_2.2.5 (2)

它存放在程序中定义和引用的函数和全局变量的信息。

如图，前面谈到的 main 函数、atoi 函数、exit 函数、sleep 函数的信息：

4.3.4 重定位条目

使用 readelf -r hello.o 命令查看 hello.o 的重定位条目：

1
2
3
4
5
6
7
8
9
10
Relocation section '.rela.dyn' at offset 0x4b8 contains 8 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000200d90  000000000008 R_X86_64_RELATIVE                    7a0
000000200d98  000000000008 R_X86_64_RELATIVE                    760
000000201008  000000000008 R_X86_64_RELATIVE                    201008
000000200fd8  000100000006 R_X86_64_GLOB_DAT 0000000000000000 _ITM_deregisterTMClone + 0
000000200fe0  000400000006 R_X86_64_GLOB_DAT 0000000000000000 __libc_start_main@GLIBC_2.2.5 + 0
000000200fe8  000600000006 R_X86_64_GLOB_DAT 0000000000000000 __gmon_start__ + 0
000000200ff0  000900000006 R_X86_64_GLOB_DAT 0000000000000000 _ITM_registerTMCloneTa + 0
000000200ff8  000b00000006 R_X86_64_GLOB_DAT 0000000000000000 __cxa_finalize@GLIBC_2.2.5 + 0

当汇编器生成 hello.o 后，它并不知道数据和代码最终将放在内存中的什么位置。它也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。所以，无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。代码重定位条目放在 .rela.plt 中，已初始化数据的重定位条目放在 .rela.dyn中。

4.4 Hello.o结果解析

使用 objdump -d -r hello.o 命令反汇编 hello.o，查看反汇编后的汇编代码与 hello.s 有何不同：

反汇编结果

不同点：

分支跳转：在 hello.s 中，分支跳转的目标位置是通过 .L1、.L2 这样的助记符来实现的，而 hello.o中，跳转的目标位置是指令的地址。

函数调用：在 hello.s 中，call 后面的目标函数是它的函数名，而在 hello.o 中，call 的是目标函数的相对偏移地址。

4.5 本章小结

本章分析了汇编的过程，并分析了 ELF 头、节头部表、重定位节以及符号表。比较了 hello.s 和 hello.o 反汇编之后的代码的不同。

第5章 链接

5.1 链接的概念与作用

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载到内存并执行。

链接器在软件开发中扮演着一个关键的角色，因为它使得分离编译成为可能。我们不用将一个大型应用程序组织为一个巨大的源文件，而是可以把它分解为更小、更好管理的模块，可以独立地修改和编译这些模块。当我们改变这些模块中地一个时，只需简单地重新编译它，并重新链接应用，而不必重新编译其他文件。即使对hello这样一个非常简单的小程序，链接的作用也是巨大的。

5.2 在Ubuntu下链接的命令

Linux下使用链接器 (ld) 链接的命令为：

1
ld -o hello -dynamic-linker /lib64/ld-linux-x86-64.so.2 /usr/lib/x86_64-linux-gnu/crt1.o /usr/lib/x86_64-linux-gnu/crti.o hello.o /usr/lib/x86_64-linux-gnu/libc.so /usr/lib/x86_64-linux-gnu/crtn.o

5.3 可执行目标文件hello的格式

5.3.1 ELF头

查看hello的ELF头

hello

可以看到，程序的 Type 变成了 EXEC (Executable file)，程序入口也分配了地址，为 0x4010f0

5.3.2 节头部表

节头部表

各个节的地址也从 0 开始进行了分配。可以看到 .text 节的起始地址为 0x4010f0，这刚好就是前面 ELF 头中的程序入口地址，与 .text 中存放程序的机器代码符合。

5.4 hello的虚拟地址空间

使用 edb 打开 hello，可以看到 hello 的虚拟地址起始为 0x401000

img

5.5 链接的重定位过程分析

使用 objdump -d -r hello 命令反汇编代码，查看两者之间的不同

5.5.1 新增函数

如图，链接后，加入了很多需要用到的库函数，puts, pintf, getchar, atoi, exit, sleep 等

新增函数

5.5.2 新增节

如图，新增了 .init 节和 .plt 节

新增节

5.5.3 新增代码endbr64

可以观察到，由 hello 反汇编生成的代码中有一句出现的频率非常高，那就是 endbr64，几乎在每一个函数或者代码片段的开头都是这句代码，非常有意思。

endbr64

其实这是 Intel 的 CET 技术，这个机制主要是用来对抗 ROP 攻击。我们在第 3 章学到，黑客可以利用缓冲区溢出来进行攻击，使程序执行黑客想要执行的程序，增加系统风险。而 CPU 和操作系统也采用了相应措施来避免这个风险：

  • 栈随机化。这段程序分配的栈的位置在每次运行时都是随机的，这就使我们无法确定在哪里插入代码
  • 限制可执行代码区域。它限制栈上存放的代码是不可执行的。

但是这些措施却无法阻挡 ROP 攻击。什么是 ROP 攻击呢？ROP：面向返回的程序设计，所谓 ROP 攻击就是黑客在已经存在的程序中找到特定的以 ret 结尾的指令序列为我们所用，称这样的代码段为 gadget，把要用到部分的地址压入栈中，每次 ret 后又会取出一个新的 gadget，于是这样就能形成一个程序链，从而实现黑客的目的。我喜欢将这种攻击方式称作“就地取材，拼凑代码”，如图：

ROP

对于 ROP 攻击也能找到解决办法，就是每次在跳转后，检查这段代码是不是程序想要的代码，也就是 CET 技术。CET 通过编译器在合理的间接跳转 (call/jmp) 中用新的指令做标记，新指令包含 endbr32 和 endbr64。程序每次执行跳转时，CPU 都会判断下一条指令是不是 endbr32/endbr64 指令，如果是则正常执行，如果不是，则会触发 #CP 异常。

这也就是每个代码段和函数开头都有一句 endbr64的原因了。

关于 ROP，在 Attack Lab 中有更深入的讲解，并进行了攻击实践。

5.5.4 函数调用与跳转

由于hello文件已经是重定位后的可执行目标文件，所以每一个 call/jmp 语句的目标地址就是确切的虚拟地址。

调用

5.6 hello的执行过程

当在 Shell 中运行 hello 时，Shell 会调用驻留在存储器中的加载器来运行它。当加载器运行时，它创建如图的内存映像：

内存映像

在 ELF 头部表的引导下，加载器将可执行文件的片复制到代码段和数据段。接下来加载器跳转到程序的入口点，也就是 _start 函数的地址。这个函数是在系统目标文件 ctrl.o 中定义的。_start 函数调用系统启动函数 __libc_start_main，该函数定义在 libc.so 中。它初始化执行环境，调用用户层的 main 函数，处理 main 函数的返回值，并且在需要的时候把控制返回给内核。

下面我使用 gdb 进行调试，逐步查看程序的执行过程：

函数入口为 0x4010f0，所以执行 hello 后，程序先从 _start 开始执行，所以我将断点打在 _start 处：

断点1

接下来单步调试运行：

调试

接下来会调用 main 函数，程序并不是直接调用 main 函数，而是先来到 __libc_start_main，用来向 main 函数传递参数，如图：

__libc_start_main

接下来，分别跳转至 GI_cxa_atexit，lll_cas_lock，new_exitfn

分别跳转

结束后，又回到了 __libc_start_main，随后来到 __libc_csu_init 部分，这部分代码在 hello 反汇编生成的汇编代码中也能看到。

随后，来到 init，再返回 __libc_csu_init，然后再返回 __libc_start_main，然后来到 _setjmp 和 __sigsetjmp 以及 __sigjmp_save，最后又返回 __libc_start_main

然后才来到 main，根据输入的不同，main 可能会调用 puts，printf，getchar，atoi，exit，sleep 函数

然后调用 __GI__IO_puts，__strlen_avx2，回到 __GI__IO_puts

然后调用 __lll_cas_lock，然后又回到 __GI__IO_puts，然后调用 IO_validate_vtable，又回到 __GI__IO_puts，然后调用 _IO_new_file_xsputn，然后调用 IO_validate_vtable

又回到 _IO_new_file_xsputn，又调用 _IO_new_file_overflow，再调用 __GI__IO_doallocbuf，再调用 IO_validate_vtable，又调用 __GI__IO_doallocbuf，再调用 __GI__IO_file_doallocate，调用 __GI__IO_file_stat，__GI___fxstat

回到 __GI__IO_file_doallocate，调用 malloc@plt，调用 __GI___libc_malloc，再调用 malloc_hook_ini，又调用 _dl_find_dso_for_object 随后调用 __GI__dl_addr

然后回到 _IO_new_file_overflow 又回到 _IO_new_file_xsputn

然后又回到 __GI__IO_puts，回到 main

最后调用 exit，调用 __GI_exit 再调用 __run_exit_handlers，__GI___call_tls_dtors

回到 __run_exit_handlers，调用 __GI___call_tls_dtors，再回到 __run_exit_handlers，然后调用 _IO_cleanup，再调用 _IO_flush_all_lockp

回到 __run_exit_handlers，调用 __GI__exit，再回到 main

调用关系如图：

调用关系

5.7 Hello的动态链接分析

在进行动态链接前，首先进行静态链接，生成部分链接的可执行目标文件 hello。此时共享库中的代码和数据没有被合并到 hello 中。只有在加载 hello 时，动态链接器才对共享目标文件中的相应模块内的代码和数据进行重定位，加载共享库，生成完全链接的可执行目标文件。

比如查看 _GLOBAL_OFFSET_TABLE 的内容：

GLOBAL_OFFSET_TABLE

5.8 本章小结

本章详细介绍了 hello 的链接过程，比对链接后的 hello 与 hello.o 的不同，并拓展讲解了 endbr64 的作用，最后使用 gdb 工具逐行查看 hello 的运行过程。

至此，我们的 hello 就成为了一个具有完整躯体与精神的青年了，也是时候让他进入社会，成为操作系统中运行的进程！

第6章 hello进程管理

6.1 进程的概念与作用

6.1.1 进程的概念

进程(process)，是操作系统对一个正在运行的程序的一种抽象。进程是程序的基本执行实体；在面向线程设计的系统（如当代多数操作系统、Linux 2.6及更新的版本）中，进程本身不是基本执行单位，而是线程的容器。程序本身只是指令、数据及其组织形式的描述，相当于一个名词，进程才是程序（那些指令和数据）的真正执行实例，

6.1.2 进程的作用

hello 在运行时，操作系统会提供一种假象，就好像系统上只有这个程序在运行。程序看上去是独占地使用处理器、主存和 I/O 设备。处理器看上去就像在不间断地一条接一条地执行程序中的指令，即该程序的代码和数据是系统内存中唯一的对象。这些假象就是通过进程来实现的。

6.2 简述Shell-bash 的作用与处理流程

Shell 是一种交互型的应用级程序，用户能够通过 Shell 与操作系统内核进行交互，如图：

shell

Shell 处理流程：

  1. 在 Shell 中输入 hello 程序的路径
  2. Shell 判断用户输入的是否为内置命令，如果不是，就认为它是一个可执行目标文件
  3. Shell 构造 argv 和 envp
  4. Shell 使用 fork() 创建子进程，调用 execve() 函数在新创建的子基础南横的上下文中加载并运行 hello 程序。将 hello 中的 .text 节、.data 节、.bss 节等内容加载到当前进程的虚拟地址空间
  5. execve() 函数调用加载器，跳转到程序的入口点，开始执行 _start 函数，我们的 hello 程序便正式开始执行了

6.3 Hellode fork进程创建过程

Linux 通过 clone() 系统调用来实现 fork()，由于 clone() 可以自主选择需要复制的资源，所以这个系统调用需要传入很多的参数标志用于指明父子进程需要共享的资源。fork()，vfork()，__clone() 函数都需要根据各自传入的参数去底层调用 clone() 系统调用，然后再由 clone() 去调用 do_fork()。do_fork() 完成了创建的大部分工作，该函数调用 copy_process() 函数,然后让进程开始运行。

copy_process() 函数是核心，他的工作分为这几步：

  1. 调用 dup_task_struct() 为新进程创建一个内核栈，thread_info 结构和 task_struct，这些值和当前进程的值相同。也就是说，当前子进程和父进程的进程描述符是一致的。
  2. 检查一次，确保创建新进程后，拥有的进程数目没有超过给它分配的资源和限制。所有进程的 task_struct 结构中都有一个数组 rlim，这个数组中记载了该进程对占用各种资源的数目限制，所以如果该用户当前拥有的进程数目已经达到了峰值，则不允许继续 fork()。这个值为 PID_MAX，大小为 0x8000，也就是说进程号的最大值为 0x7fff，即短整型变量 short 的大小 32767，其中 0~299 是为系统进程（包括内核线程）保留的，主要用于各种“保护神进程”。
  3. 子进程为了将自己与父进程区分开来，将进程描述符中的许多成员全部清零或者设为初始值。不过大多数数据都未修改。
  4. 将子进程的状态设置为 TASK_UNINTERRUPTIBLE 深度睡眠，不可被信号唤醒，以保证子进程不会投入运行。
  5. copy_process() 函数调用 copy_flags() 以更新 task_struct 中的 flags 成员。其中表示进程是否拥有超级用户管理权限的 PF_SUPERPRIV 标志被清零，表示进程还没有调用 exec() 函数的 PF_FORKNOEXEC 标志也被清零。
  6. 调用 alloc_pid 为子进程分配一个有效的 PID
  7. 根据传递给 clone() 的参数标志，调用 do_fork()->copy_process() 拷贝或共享父进程打开的文件，信号处理函数，进程地址空间和命名空间等。一般情况下，这些资源会给进程下的所有线程共享。
  8. 最后，copy_process() 做扫尾工作并返回一个指向子进程的指针。

6.4 Hello的execve过程

execve() 函数加载并运行可执行目标文件，且带参数列表 argv 和环境变量列表 envp，execve() 函数调用一次从不返回。它的执行过程如下：

  1. 删除已存在的用户区域
  2. 映射私有区：为 hello 的代码、数据、.bss 和栈区域创建新的区域结构，所有这些区域都是私有的、写时才复制的
  3. 映射共享区：比如 hello 程序与共享库 libc.so 链接
  4. 设置 PC：exceve() 做的最后一件事就是设置当前进程的上下文中的程序计数器，使之指向代码区域的入口点
  5. execve() 在调用成功的情况下不会返回，只有当出现错误时，例如找不到需要执行的程序时，execve() 才会返回到调用程序

6.5 Hello的进程执行

6.5.1 逻辑控制流

操作系统将一个 CPU 物理控制流，分成多个逻辑控制流，每个进程独占一个逻辑控制流。当一个逻辑控制流执行的时候，其他的逻辑控制流可能会临时暂停执行。一般来说，每个逻辑控制流都是独立的。当两个逻辑控制流在时间上发生重叠，我们说是并行的。如图：

逻辑控制流

处理器在多个进程中来回切换称为多任务，每个时间当处理器执行一段控制流称为时间片。因此多任务也指时间分片。

6.5.2 用户模式和内核模式

为了限制一个应用可以执行的指令以及它可以访问的地址空间范围，处理器用一个控制寄存器中的一个模式位来描述进程当前的特权。如图是 x86 CPU 提供的环保护机制：

环保护机制

内核工作在 0 环，用户工作在 3 环，中间环留给中间软件用。Linux 仅用第 0 和第 3 环，即用户模式和内核模式。

用户模式：用户模式中的进程不允许执行特权指令，比如停止处理器、改变模式位，或者发起一个 I/O 操作。也不允许用户模式的进程直接引用地址空间中内核区内的代码和数据。用户程序必须通过系统调用接口间接地访问内核代码和数据。

进程从用户模式变为内核模式的唯一方法是通过诸如中断、故障或者陷入系统调用这样的异常。当异常发生时，控制传递到异常处理程序，处理器将模式从用户模式变为内核模式。处理程序运行在内核模式中，当它返回到应用程序代码时，处理器就把模式从内核模式改回到用户模式。

6.5.3 上下文切换

操作系统内核为每个进程维护一个上下文。所谓上下文就是内核重新启动一个被抢占的进程所需的状态。它由一些对象的值组成，这些对象包括通用寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构，比如描述地址空间的页表，包含有关当前进程信息的进程表，以及包含进程已打开文件的信息的文件表。

6.5.3 Hello的执行

从 Shell 中运行 hello 时，它运行在用户模式，运行过程中，内核不断切换上下文，使运行过程被切分成时间片，与其他进程交替占用执行，实现进程的调度。如果在运行过程中收到信号等，那么就会进入内核模式，运行信号处理程序，之后再返回用户模式。

6.6 Hello的异常与信号处理

异常可以分为四类：中断、陷阱、故障和终止。它们的性质如图：

异常的性质

中断：比如在 hello 运行过程中，我们敲击键盘，那么就会触发中断，系统调用内核中的中断处理程序执行，然后返回，hello 继续执行，如图：

中断

陷阱：陷阱就是系统调用，我们的 hello 运行在用户模式下，无法直接运行内核中的程序，比如像 fork，exit 这样的系统调用。于是就通过陷阱的方式，执行 systemcall 指令，内核调用陷阱处理程序来执行系统调用，如图：

陷阱

故障：当我们的 hello 运行时，当某一条指令引用一个虚拟地址，而地址相对应的物理页面不在内存中，就会发生故障。内核调用故障处理程序（这里是缺页处理程序），缺页处理程序从磁盘中加载适当的页面，然后将控制返回给引起故障的指令，该指令就能顺畅地执行了。

当然，也有一些故障会使程序直接终止。

故障

终止：hello 在运行时，也有可能遇到硬件错误，那就只能自认倒霉，终止 hello 的运行。

6.6.2 信号

使用 man 7 signal 查看 Linux 信号如图：

信号

我在hello运行过程中，测试其中部分信号。

SIGSTP：当 hello 在前台运行时，按下 Ctrl+z 会向它发送 SIGSTP 信号，这个进程就会暂时挂起，可以使用 fg % 命令，让它在前台继续执行：

SIGSTP

SIGINT：当 hello 在前台运行时，按下 Ctrl+c 会向它发送 SIGINT 信号，这个进程就会被终止：

SIGINT

也可以在执行 hello 程序的命令后面加上 &，这样它就会在后台运行，分别使用 ps 和 jobs 来查看 hello 进程。

执行

ps 和 jobs 的区别在于，ps 会打印系统中的所有进程，包括我正在使用的终端 Shell，而 job 只会打印 Shell 正在维护的进程，它不会包括自己。

当进程在后台运行时，我们用键盘发送的信号是无法发送给它，这时可以用 kill 命令来终止它：

kill

6.7本章小结

这章讲解了 hello 如何运行在操作系统的上下文中，以及它如何受到信号的控制。

第7章 hello的存储管理

7.1 hello的存储器地址空间

我们的 hello 进程是与其它进程共享 CPU 和主存资源的，为了更加有效地管理内存并且少出错，现代操作系统提供了一种对主存的抽象概念，叫做虚拟内存。虚拟内存时硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。首先确定一些概念

  1. 逻辑地址：格式为“段地址:偏移地址”，是 CPU 生成的地址，在内部和编程使用，并不唯一。
  2. 线性地址：逻逻辑地址到物理地址变换之间的中间层，逻辑地址经过段机制后转化为线性地址。
  3. 虚拟地址：保护模式下，hello 运行在虚拟地址空间中，它访问存储器所用的逻辑地址。
  4. 物理地址：加载到内存地址寄存器中的地址，内存单元的真正地址。CPU 通过地址总线的寻址，找到真实的物理内存对应地址。

7.2 Intel逻辑地址到线性地址的变换-段式管理

在 Intel 平台下的实模式中，逻辑地址为：CS：EA，CS 是段寄存器，将 CS 里的值左移四位，再加上 EA 就是线性地址。

而保护模式下，要用段描述符作为下标，到 GDT（全局描述符表）/LAT（局部描述符表）中查表获得段地址，段地址+偏移地址就是线性地址。

段描述符是一个 16 位字长的字段，如图：

段描述符

TI 位指示选择 GDT 还是 LDT，前 13 位作为索引来确定段描述符在描述符表中的位置。从段描述符和偏移地址得到线性地址的过程如图：

线性地址

7.3 Hello的线性地址到物理地址的变换-页式管理

VM 系统将虚拟内存分割为成为虚拟页的大小固定的快，物理内存也被分割为物理页，成为页帧。虚拟页面就可以作为缓存的工具，被分为三个部分：

  • 未分配的：VM 系统还未分配的页
  • 已缓存的：当前已缓存在物理内存中的已分配页
  • 未缓存的：未缓存在物理内存的已分配页

如图：

磁盘分配

7.4 TLB与四级页表支持下的VA到PA的变换

页表是 PTE（页表条目）的数组，它将虚拟页映射到物理页，每个 PTE 都有一个有效位和一个 n 位地址字段，有效位表明该虚拟页是否被缓存在 DRAM 中，地址字段表明 DRAM 中相应物理页的起始位置，它分为两个部分：VPO（虚拟页面偏移）和 VPN（虚拟页号），如图：

四级页表

7.4.1 TLB加速地址翻译

为了优化 CPU 产生一个虚拟地址后，MMU 查阅 PTE的过程，在 MMU 中设置一个关于 PTE 的小缓存，称为 TLB（翻译后备缓冲器）。像普通的缓存一样，TLB 的索引和标记是从 PTE 中的 VPN 提取出来的，如图：

img

7.4.2 四级页表翻译

Core i7 采用四级页表层次结构，如图：

四级

每次 CPU 产生一个虚拟地址后，通过它的 VPN 部分看 TLB 中是否缓存，如果命中，直接得到 PPN，将虚拟地址中的 VPO 作为物理页偏移，这样就能得到物理地址；如果 TLB 不命中，则经过四级页表的查找得到最终的PTE，从而得到 PPN，进而得到物理地址。

7.5 三级Cache支持下的物理内存访问

得到物理地址后，将物理地址分为 CT（标记位）、CI(组索引) 和 CO（块偏移）。根据 CI 查找 L1 缓存中的组，依次与组中每一行的数据比较，有效位有效且标记位一致则命中。如果命中，直接返回想要的数据。如果不命中，就依次去 L2、L3 缓存判断是否命中，命中时将数据传给 CPU 同时更新各级缓存。

7.6 hello进程fork时的内存映射

在 Shell 输入命令行后，内核调用fork创建子进程，为 hello 程序的运行创建上下文，并分配一个与父进程不同的PID。通过 fork 创建的子进程拥有父进程相同的区域结构、页表等的一份副本，同时子进程也可以访问任何父进程已经打开的文件。当 fork 在新进程中返回时，新进程现在的虚拟内存刚好和调用 fork 时存在的虚拟内存相同，当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间。

7.7 hello进程execve时的内存映射

execve() 函数调用驻留在内核区域的启动加载器代码，在当前进程中加载并运行包含在可执行目标文件 hello 中的程序，用 hello 程序有效地替代了当前程序。加载并运行 hello 需要以下几个步骤：

  1. 删除已存在的用户区域，删除当前进程虚拟地址的用户部分中的已存在的区域结构。
  2. 映射私有区域，为新程序的代码、数据、bss 和栈区域创建新的区域结构，所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为 hello 文件中的 .text 和 .data 区，bss 区域是请求二进制零的，映射到匿名文件，其大小包含在 hello 中，栈和堆地址也是请求二进制零的，初始长度为零。
  3. 映射共享区域， hello 程序与共享对象 libc.so 链接，libc.so 是动态链接到这个程序中的，然后再映射到用户虚拟地址空间中的共享区域内。
  4. 设置程序计数器（PC），execv() 做的最后一件事情就是设置当前进程上下文的程序计数器，使之指向代码区域的入口点。

img

7.8 缺页故障与缺页中断处理

正如前面讲到的，hello 在运行时，很有可能会发生缺页故障，大致流程已经在 6.6.1 中做了阐述。当 CPU 产生的一个虚拟地址并不在 DRAM 缓存中时，缺页异常处理程序会选择一个牺牲页，用要读取的地址的内容替换它，然后内核重新启动导致缺页的指令。

7.9 动态存储分配管理

hello 在运行时，它调用的 printf 函数会调用malloc函数，动态存储分配管理又是操作系统的一个伟大设计！

7.9.1 堆

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。如图：

堆

分配器将堆视为一组大小不同的块的集合来维护，且它们的地址是连续的。将块标记为两种，已分配的块供应用程序使用，空闲块用来分配

7.9.2 隐式空闲链表管理

想要设计好的数据结构维护空闲块需要考虑以下方面：

  1. 空闲块组织：利用隐式空闲链表记录空闲块
  2. 放置策略：如何选择合适的空闲块分配？
    1. 首次适配：从头开始搜索空闲链表，选择第一个合适的空闲块
    2. 下一次适配：从上一次查询结束的地方开始搜索选择第一个合适的空闲块
    3. 最佳适配：搜索能放下请求大小的最小空闲块
  3. 分割：在将一个新分配的块放置到某个空闲块后，剩余的部分要进行处理
  4. 合并：释放某个块后，要让它与相邻的空闲块合并

每个空闲块的结构如下：

空闲块结构

  • 脚部与头部是相同的，均为 4 个字节，用来存储块的大小，以及表明这个块是已分配还是空闲块
  • 由于要求块双字对齐，所以块大小就总是 8 的倍数，低 3 位总是为 0，因而，我们只需要利用头部和脚部的高29 位存储块的大小，剩下 3 位的最低位来指明这个块是否空闲，000 为空闲，001 为已分配

为什么既设置头部又设置尾部呢？这是为了能够以常数时间来进行块的合并。无论是与下一块还是与上一块合并，都可以通过他们的头部或尾部得知块大小，从而定位整个块，避免了从头遍历链表。空闲块怎么组织呢？如图：

空闲块

堆有两个特殊的标记：

  • 序言块：8 个字节，由一个头部和一个脚部组成
  • 结尾块：大小为 0 的头部

为了消除合并空闲块时边界的考虑，将序言块和结尾块的分配位均设置为已分配。为了保证双字对齐，在序言块的前面还设置了 4 个字节作为填充。

7.9.3 显式空闲链表管理

真实的操作系统实际上使用的是显示空闲链表管理。它的思路是维护多个空闲链表，每个链表中的块有大致相等的大小，分配器维护着一个空闲链表数组，每个大小类一个空闲链表，当需要分配块时只需要在对应的空闲链表中搜索就好了，有两种分离存储的方法

简单分离存储：从不合并与分离，每个块的大小就是大小类中最大元素的大小。例如大小类为 {17~32}，则需要分配块的大小在这个区间时均在此对应链表进行分配，并且都是分配大小为 32 的块。这样做，显然分配和释放都是常数级的，但是空间利用率较低

分离适配：每个大小类的空闲链表包含大小不同的块，分配完一个块后，将这个块进行分割，并根据剩下的块的大小将其插入到适当大小类的空闲链表中。这个做法平衡了搜索时间与空间利用率，C 标准库提供的 GNU malloc 包就是采用的这种方法。

7.10本章小结

本章介绍了现代操作系统的灵魂：存储器地址空间、段式管理、页式管理，VA 到 PA 的变换、物理内存访问， hello 进程 fork 时和 execve 时的内存映射、缺页故障与缺页中断处理、包括隐式空闲链表和显式空闲链表的动态存储分配管理。这些巧妙的设计使得我们的 hello 最终得以运行。

结论

至此，hello 终于走完了它的一生，让我们为它的一生做个小结：

  • 程序设计者编写出它的基因——hello.c
  • 预处理器完善它的基因——hello.i
  • 编译器为它注入的灵魂——hello.s
  • 汇编器为它的诞生做最后的准备——hello.o
  • 链接器让它长出完整的躯体——hello
  • Shell 为它创建子进程，让它真正成为系统中的个体
  • 加载器映射虚拟内存，给予它成长的条件
  • CPU 的逻辑控制流让它驰骋在硬件与操作系统之上
  • 虚拟地址这一计算机系统最伟大的抽象为它的驰骋导航
  • malloc 的高效管理让它的驰骋拥有更广阔的天地
  • 信号与异常约束它的行为，让它总是走在康庄大道之上
  • 当 hello 垂垂老矣，运行完最后一行代码，__libc_start_main 将控制转移给内核，Shell 回收子进程，内核删除与它相关的所有数据结构，它在这个世界的所有痕迹至此被抹去。

回首它的一生，惊心动魄，千难万险。其中的每个阶段无不凝结着人类最伟大的智慧！

CSAPP
#computer
computer_systems
http://htwzxwj.github.io/2024/02/03/csapp/
作者
End0rph1n
发布于
2024年2月3日
许可协议