程序人生P2P

• 整数 程序中涉及的整数有：

1. int sleepsecs：sleepsecs在C程序中被声明为全局变量，且已经被赋值，编译器处理时在.data节声明该变量，.data节存放已经初始化的全局和静态C变量。在图3.3中，可以看到，编译器首先将sleepsecs在.text代码段中声明为全局变量，其次在.data段中，设置对齐方式为4、设置类型为对象、设置大小为4字节、设置为long类型其值为2（long类型在linux下与int相同为4B，将int声明为long应该是编译器偏好）。

   图3.3 hello.s中sleepsecs的声明

2. int i：编译器将局部变量存储在寄存器或者栈空间中，在hello.s中编译器将i存储在栈上空间-4(%rbp)中，可以看出i占据了栈中的4B。

3. int argc：作为第一个参数传入。

4. 立即数：其他整形数据的出现都是以立即数的形式出现的，直接硬编码在汇编代码中。

• 数组 程序中涉及数组的是：char argv[] main，函数执行时输入的命令行，argv作为存放char指针的数组同时是第二个参数传入。 argv单个元素char大小为8B，argv指针指向已经分配好的、一片存放着字符指针的连续空间，起始地址为argv，main函数中访问数组元素argv[1],argv[2]时，按照起始地址argv大小8B计算数据地址取数据，在hello.s中，使用两次(%rax)（两次rax分别为argv[1]和argv[2]的地址）取出其值。如图3.4。

图3.4 计算地址取出数组值 3.3.2 赋值 程序中涉及的赋值操作有：

1. int sleepsecs=2.5 ：因为sleepsecs是全局变量，所以直接在.data节中将sleepsecs声明为值2的long类型数据。
2. i=0：整型数据的赋值使用mov指令完成，根据数据的大小不同使用不同后缀，分别为： 指令 b w l q 大小 8b (1B) 16b (2B) 32b (4B) 64b (8B) 因为i是4B的int类型，所以使用movl进行赋值，汇编代码如图3.5。

图3.5 hello.s中变量i的赋值 3.3.3 类型转换 程序中涉及隐式类型转换的是：int sleepsecs=2.5，将浮点数类型的2.5转换为int类型。 当在double或float向int进行类型转换的时候，程序改变数值和位模式的原则是：值会向零舍入。例如1.999将被转换成1，-1.999将被转换成-1。进一步来讲，可能会产生值溢出的情况，与Intel兼容的微处理器指定位模式[10…000]为整数不确定值，一个浮点数到整数的转换，如果不能为该浮点数找到一个合适的整数近似值，就会产生一个整数不确定值。 浮点数默认类型为double，所以上述强制转化是double强制转化为int类型。遵从向零舍入的原则，将2.5舍入为2。 3.3.4算数操作 进行数据算数操作的汇编指令有：

指令 效果 leaq S,D D=&S INC D D+=1 DEC D D-=1 NEG D D=-D ADD S,D D=D+S SUB S,D D=D-S IMULQ S R[%rdx]:R[%rax]=SR[%rax]（有符号） MULQ S R[%rdx]:R[%rax]=SR[%rax]（无符号） IDIVQ S R[%rdx]=R[%rdx]:R[%rax] mod S（有符号） R[%rax]=R[%rdx]:R[%rax] div S DIVQ S R[%rdx]=R[%rdx]:R[%rax] mod S（无符号） R[%rax]=R[%rdx]:R[%rax] div S

   程序中涉及的算数操作有：

1. i++，对计数器i自增，使用程序指令addl，后缀l代表操作数是一个4B大小的数据。

2. 汇编中使用leaq .LC1(%rip),%rdi，使用了加载有效地址指令leaq计算LC1的段地址%rip+.LC1并传递给%rdi。 3.3.5 关系操作 进行关系操作的汇编指令有： 指令 效果 描述 CMP S1,S2 S2-S1 比较-设置条件码 TEST S1,S2 S1&S2 测试-设置条件码 SET** D D=** 按照将条件码设置D J —— 根据**与条件码进行跳转

   程序中涉及的关系运算为：

3. argc!=3：判断argc不等于3。hello.s中使用cmpl $3,-20(%rbp)，计算argc-3然后设置条件码，为下一步je利用条件码进行跳转作准备。

4. i<10：判断i小于10。hello.s中使用cmpl $9,-4(%rbp)，计算i-9然后设置条件码，为下一步jle利用条件码进行跳转做准备。 3.3.6 控制转移 程序中涉及的控制转移有：

5. if (argv!=3)：当argv不等于3的时候执行程序段中的代码。如图3.6，对于if判断，编译器使用跳转指令实现，首先cmpl比较argv和3，设置条件码，使用je判断ZF标志位，如果为0，说明argv-3=0 argv==3，则不执行if中的代码直接跳转到.L2，否则顺序执行下一条语句，即执行if中的代码。

   图3.6 if语句的编译

6. for(i=0;i<10;i++)：使用计数变量i循环10次。如图3.7，编译器的编译逻辑是，首先无条件跳转到位于循环体.L4之后的比较代码，使用cmpl进行比较，如果i<=9，则跳入.L4 for循环体执行，否则说明循环结束，顺序执行for之后的逻辑。

   图3.7 for循环的编译 3.3.7 函数操作 函数是一种过程，过程提供了一种封装代码的方式，用一组指定的参数和可选的返回值实现某种功能。P中调用函数Q包含以下动作：

7. 传递控制：进行过程Q的时候，程序计数器必须设置为Q的代码的起始地址，然后在返回时，要把程序计数器设置为P中调用Q后面那条指令的地址。

8. 传递数据：P必须能够向Q提供一个或多个参数，Q必须能够向P中返回一个值。

9. 分配和释放内存：在开始时，Q可能需要为局部变量分配空间，而在返回前，又必须释放这些空间。

64位程序参数存储顺序（浮点数使用xmm，不包含）： 1 2 3 4 5 6 7 %rdi %rsi %rdx %rcx %r8 %r9 栈空间

程序中涉及函数操作的有：

1. main函数：
2. 传递控制，main函数因为被调用call才能执行（被系统启动函数__libc_start_main调用），call指令将下一条指令的地址dest压栈，然后跳转到main函数。
3. 传递数据，外部调用过程向main函数传递参数argc和argv，分别使用%rdi和%rsi存储，函数正常出口为return 0，将%eax设置0返回。
4. 分配和释放内存，使用%rbp记录栈帧的底，函数分配栈帧空间在%rbp之上，程序结束时，调用leave指令，leave相当于mov %rbp,%rsp,pop %rbp，恢复栈空间为调用之前的状态，然后ret返回，ret相当pop IP，将下一条要执行指令的地址设置为dest。
5. printf函数：
6. 传递数据：第一次printf将%rdi设置为“Usage: Hello 学号 姓名！\n”字符串的首地址。第二次printf设置%rdi为“Hello %s %s\n”的首地址，设置%rsi为argv[1]，%rdx为argv[2]。
7. 控制传递：第一次printf因为只有一个字符串参数，所以call puts@PLT；第二次printf使用call printf@PLT。
8. exit函数：
9. 传递数据：将%edi设置为1。
10. 控制传递：call exit@PLT。
11. sleep函数：
12. 传递数据：将%edi设置为sleepsecs。
13. 控制传递：call sleep@PLT。
14. getchar函数：
15. 控制传递：call gethcar@PLT

3.4 本章小结 本章主要讲述了编译器的工作，以及我们怎样在linux下将一个与处理文件变为一个汇编代码文件，以及解释了在汇编代码中是如何实现c语言中的各项数据和指令的。 （第3章2分）

第4章 汇编 4.1 汇编的概念与作用 概念：汇编代码文件（由汇编指令构成）称为汇编语言源程序，汇编程序（汇编器）用来将汇编语言源程序转换为机器指令序列（机器语言程序） 作用：汇编器（as）将.s汇编程序翻译成机器语言指令，把这些指令打包成可重定位目标程序的格式，并将结果保存在.o目标文件中，.o文件是一个二进制文件，它包含程序的指令编码。这个过程称为汇编，亦即汇编的作用。 4.2 在Ubuntu下汇编的命令 $gcc –c hello.s –o hello.o – $gcc –c hello.c –o hello.o – $as hello.s -o hello.o （as是一个汇编程序）

4.3 可重定位目标elf格式 利用readelf -a hello.o > hello.elf生成hello.o的全部信息

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

图4.2 ELF Header

1. Section Headers：节头部表，包含了文件中出现的各个节的语义，包括节的类型、位置和大小等信息。

   图4.3 节头部表Section Headers

2. 重定位节.rela.text ,一个.text节中位置的列表，包含.text节中需要进行重定位的信息，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。如图4.4，图中8条重定位信息分别是对.L0（第一个printf中的字符串）、puts函数、exit函数、.L1（第二个printf中的字符串）、printf函数、sleepsecs、sleep函数、getchar函数进行重定位声明。

   图4.4 重定位节.rela.text

.rela节的包含的信息有（readelf显示与hello.o中的编码不同，以hello.o为准）：

offset 需要进行重定向的代码在.text或.data节中的偏移位置，8个字节。 Info 包括symbol和type两部分，其中symbol占前4个字节，type占后4个字节，symbol代表重定位到的目标在.symtab中的偏移量，type代表重定位的类型 Addend 计算重定位位置的辅助信息，共占8个字节 Type 重定位到的目标的类型 Name 重定向到的目标的名称

          下面以.L1的重定位为例阐述之后的重定位过程：链接器根据info信息向.symtab节中查询链接目标的符号，由info.symbol=0x05，可以发现重定位目标链接到.rodata的.L1，设重定位条目为r，根据图4.5知r的构造为：

r.offset=0x18, r.symbol=.rodata, r.type=R_X86_64_PC32, r.addend=-4， 重定位一个使用32位PC相对地址的引用。计算重定位目标地址的算法如下（设需要重定位的.text节中的位置为src,设重定位的目的位置dst）： refptr = s +r.offset （1） refaddr = ADDR(s) + r.offset （2） refptr = (unsigned) (ADDR(r.symbol) + r.addend-refaddr)（3） 其中（1）指向src的指针（2）计算src的运行时地址，（3）中，ADDR(r.symbol)计算dst的运行时地址，在本例中，ADDR(r.symbol)获得的是dst的运行时地址，因为需要设置的是绝对地址，即dst与下一条指令之间的地址之差，所以需要加上r.addend=-4。 之后将src处设置为运行时值refptr，完成该处重定位。

                 图4.5 通过HexEdit查看hello.o中的.rela.text节

对于其他符号的重定位过程，情况类似。 3）.rela.eh_frame ： eh_frame节的重定位信息。 4）.symtab：符号表，用来存放程序中定义和引用的函数和全局变量的信息。重定位需要引用的符号都在其中声明。

4.4 Hello.o的结果解析 使用 objdump -d -r hello.o > hello.objdump获得反汇编代码。

   总体观察图4.6后发现，除去显示格式之外两者差别不大，主要差别如下：

1. 分支转移：反汇编代码跳转指令的操作数使用的不是段名称如.L3，因为段名称只是在汇编语言中便于编写的助记符，所以在汇编成机器语言之后显然不存在，而是确定的地址。

2. 函数调用：在.s文件中，函数调用之后直接跟着函数名称，而在反汇编程序中，call的目标地址是当前下一条指令。这是因为hello.c中调用的函数都是共享库中的函数，最终需要通过动态链接器才能确定函数的运行时执行地址，在汇编成为机器语言的时候，对于这些不确定地址的函数调用，将其call指令后的相对地址设置为全0（目标地址正是下一条指令），然后在.rela.text节中为其添加重定位条目，等待静态链接的进一步确定。

3. 全局变量访问：在.s文件中，访问rodata（printf中的字符串），使用段名称+%rip，在反汇编代码中0+%rip，因为rodata中数据地址也是在运行时确定，故访问也需要重定位。所以在汇编成为机器语言时，将操作数设置为全0并添加重定位条目。

   图4.6 hello.s与反汇编代码main函数对照 4.5 本章小结 本章介绍了从汇编代码到可重定位目标文件的过程，以及手段（gcc，as汇编器），将汇编文件的汇编代码转化为了机器代码ELF形式，也同时查看了ELF中的内容有些什么，作用是什么（怎么为之后的链接过程提供信息），以及反汇编代码和汇编代码的异同 （第4章1分）

第5章 链接 5.1 链接的概念与作用 链接过程将多个可重定位目标文件合并以生成可执行目标文件 5.2 在Ubuntu下链接的命令 – $gcc –static –o myproc main.o test.o – $ld –static –o myproc main.o test.o –static 表示静态链接，如果不指定-o选项，则可执行文件名 为“a.out”

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

在ELF格式文件中，Section Headers对hello中所有的节信息进行了声明，其中包括大小Size以及在程序中的偏移量Offset，因此根据Section Headers中的信息我们就可以用HexEdit定位各个节所占的区间（起始位置，大小）。其中Address是程序被载入到虚拟地址的起始地址。

   图5.2 hello ELF格式中的Section Headers Table

5.4 hello的虚拟地址空间 序头表描述可执行文件中的节与虚拟空间中的存储段之间的映射关系一个表（32B）说明虚拟地址空间中一个连续的段或一个特殊的节以下是某可执行目标文件程序头表信息有8个表项，其中两个为可装入段（即Type=LOAD） 1.PHDR保存程序头表。 2.INTERP指定在程序已经从可执行文件映射到内存之后，必须调用的解释器（如动态链接器）。 3.LOAD表示一个需要从二进制文件映射到虚拟地址空间的段。其中保存了常量数据（如字符串）、程序的目标代码等。 4.DYNAMIC保存了由动态链接器使用的信息。 5.NOTE保存辅助信息。 6.GNU_STACK：权限标志，标志栈是否是可执行的。 7.GNU_RELRO：指定在重定位结束之后那些内存区域是需要设置只读。

5.5 链接的重定位过程分析 1.不同情况下的重定位： （1）.同一模块下的函数重定位 调用或跳转源与目的地都在同一个模块，相对位置固定，只要用相对偏移寻址即可 无需动态链接器进行重定位 refaddr = ADDR(s) + r.offset （1） *refptr = (unsigned) (ADDR(r.symbol) + r.addend-refaddr)（2）

(2) 模块内部数据引用 • .data节与.text节之间的相对位置确定，任何引用局 部符号的指令与该符号之间的距离是一个常数

变量a与引用a的指令之间的距离为常数，调用__get_pc后，call指令的返回地 址被置ECX。若模块被加载到0x9000000，则a的访问地址为： 0x9000000+0x34c+0x118c(指令与.data间距离)+0x28(a在.data节中偏移) refptr = s +r.offset （1） (3) 模块外数据的引用 • 引用其他模块的全局变量，无法确定相对距离 • 在.data节开始处设置一个指针数组（全局偏移表， GOT），指针可指向一个全局变量 • GOT与引用数据的指令之间相对距离固定

(4) 模块间调用、跳转 • 方法一：类似于(3)，在GOT中加一个项(指针)，用 于指向目标函数的首地址（如&ext） • 动态加载时，填入目标函数的首地址

2.通过比较hello.objdump和helloo.objdump了解链接器。 1）函数个数：在使用ld命令链接的时候，指定了动态链接器为64的/lib64/ld-linux-x86-64.so.2，crt1.o、crti.o、crtn.o中主要定义了程序入口_start、初始化函数_init，_start程序调用hello.c中的main函数，libc.so是动态链接共享库，其中定义了hello.c中用到的printf、sleep、getchar、exit函数和_start中调用的__libc_csu_init，__libc_csu_fini，__libc_start_main。链接器将上述函数加入。 2）函数调用：链接器解析重定条目时发现对外部函数调用的类型为R_X86_64_PLT32的重定位，此时动态链接库中的函数已经加入到了PLT中，.text与.plt节相对距离已经确定，链接器计算相对距离，将对动态链接库中函数的调用值改为PLT中相应函数与下条指令的相对地址，指向对应函数。对于此类重定位链接器为其构造.plt与.got.plt。 3）.rodata引用：链接器解析重定条目时发现两个类型为R_X86_64_PC32的对.rodata的重定位（printf中的两个字符串），.rodata与.text节之间的相对距离确定，因此链接器直接修改call之后的值为目标地址与下一条指令的地址之差，指向相应的字符串。这里以计算第一条字符串相对地址为例说明计算相对地址的算法（算法说明同4.3节）：

5.6 hello的执行流程 使用edb执行hello，说明从加载hello到_start，到call main,以及程序终止的所有过程。请列出其调用与跳转的各个子程序名或程序地址。 程序名称 程序地址 ld-2.27.so!_dl_start 0x7fc5 60f02ea0 ld-2.27.so!_dl_init 0x7fc5 60f11630 hello!_start 0x400500 libc-2.27.so!__libc_start_main 0x7fce 8c867ab0 -libc-2.27.so!__cxa_atexit 0x7fce 8c889430 -libc-2.27.so!__libc_csu_init 0x4005c0 hello!_init 0x400488 libc-2.27.so!_setjmp 0x7fce 8c884c10 -libc-2.27.so!_sigsetjmp 0x7fce 8c884b70 –libc-2.27.so!__sigjmp_save 0x7fce 8c884bd0 hello!main 0x400532 hello!puts@plt 0x4004b0 hello!exit@plt 0x4004e0 *hello!printf@plt – *hello!sleep@plt – *hello!getchar@plt – ld-2.27.so!_dl_runtime_resolve_xsave 0x7fce 8cc4e680 -ld-2.27.so!_dl_fixup 0x7fce 8cc46df0 –ld-2.27.so!_dl_lookup_symbol_x 0x7fce 8cc420b0 libc-2.27.so!exit 0x7fce 8c889128

5.7 Hello的动态链接分析 为了能让动态链接能在程序运行或者加载时链接，就要实现位置无关代码，其做法就是利用在程序执行过程之中已知该条指令在.text节中偏移量以及.text与.data节之间的距离这一事实，来构造GOT这么一个在.data节之中的全局偏移量表，记录所需的代码或者时数据的地址。 为了加快程序的启动时间，我们采用PLT（过程连接表）和GOT结合的这么一个手段来在延迟绑定（也就是在第一次使用函数时绑定在相应的GOT中） PLT：

1.前言：

当在程序运行过程中需要调用动态链接器来为某一个第一次调用的外部函数进行地址绑定时，需要提供给动态链接器的内容有：发生地址绑定需求的地方（文件名）以及需要绑定的函数名，也即是说，假设动态链接器使用某一个函数来进行地址绑定工作，那它的函数原型应该为： lookup(module,function)。

Eg：假设文件 liba.so 中需要调用 libb.so 中的函数bar()，那在第一次调用时，将调用动态链接器中的 lookup 函数，其参数为 lookup(liba.so,bar)。

事实上，在Glibc 中，该 lookup函数的真实名字是：_dl_runtime_resolve()

2.PLT 的简单实现：

原来的做法：调用某一个外部函数时，通过GOT中的相应项进行间接跳转

PLT 的加入：调用函数时，通过一个 PLT项的结构来进行跳转，每一个外部函数在 PLT 中都有一个相应的项

Eg：PLT的简单实现，假设对上面例子中的 bar() 函数，在PLT中存在与其对应的一项 bar@plt。其实现如下：

bar@plt: jmp *(bar@GOT) //如果是第一次链接，该语句的效果只是跳转到下一句指令。否则，将会跳转到 bar()函数对应的位置 push n //压栈 n，n 是 bar 这个符号在重定位表 .rel.plt 中的下标 push moduleID // 压栈当前模块的模块ID，上述例子中的 liba.so jump _dl_runtime_resolve() //跳转到动态链接器中的地址绑定处理函数

3.PLT的真正实现：

ELF将GOT拆为了两个表叫做“.got”,".got.plt"。其中 .got 用来保存全局变量的引用地址，.got.plt 用来保存函数引用的地址，也就是说，所有对于外部函数的引用被分离到了 .got.plt 表中，该表的前三项分别是：

1. .dynamic 段的地址

2. 本模块的 ID

3. _dl_runtime_resolve()的地址

对于上述例子中的bar()函数，真正实现为：

PLT0: push *(GOT + 4) //压入模块名 jmp *(GOT + 8) //跳转到 _dl_runtime_resolve()函数

…

bar@plt: jmp *(bar@GOT) //仍然首先进行GOT跳转，尝试是否是第一次链接 push n //压入需要地址绑定的符号在重定位表中的下标 jmp PLT0 //跳转到 PLT0

PLT在ELF文件中以独立的段存放，段名叫 .plt。它本身是与地址无关的代码（PIC），因此可以和代码段等一起合并成一个可读可执行的节，并装载入内存中。 在dl_init调用之前，对于每一条PIC函数调用，调用的目标地址都实际指向PLT中的代码逻辑，GOT存放的是PLT中函数调用指令的下一条指令地址。如在图5.4 (a)。 在dl_init调用之后，如图5.4 (b)，0x601008和0x601010处的两个8B数据分别发生改变为0x7fd9 d3925170和0x7fd9 d3713680，如图5.4（c）其中GOT[1]指向重定位表（依次为.plt节需要重定位的函数的运行时地址）用来确定调用的函数地址，如图5.4（d）GOT[2]指向动态链接器ld-linux.so运行时地址。 GOT.PLT节所在地址由elf中的节头指出起始地址。

   图5.4 (a) 没有调用dl_init之前的全局偏移量表.got.plt

(根据.plt中exit@plt jmp的引用地址0x601030可以得到其.got.plt条目为0x4004e6，正是其下条指令地址)

   图5.4（b）调用dl_init之后的全局偏移量表.got.plt


   图5.3（c）0x7fd9 d3925170指向的重定位表


   图5.4（d） 0x7fd9 d3713680目标程序-动态链接器
  
   在之后的函数调用时，首先跳转到PLT执行.plt中逻辑，第一次访问跳转时GOT地址为下一条指令，将函数序号压栈，然后跳转到PLT[0]，在PLT[0]中将重定位表地址压栈，然后访问动态链接器，在动态链接器中使用函数序号和重定位表确定函数运行时地址，重写GOT，再将控制传递给目标函数。之后如果对同样函数调用，第一次访问跳转直接跳转到目标函数。
   因为在PLT中使用的jmp，所以执行完目标函数之后的返回地址为最近call指令下一条指令地址，即在main中的调用完成地址。

5.8 本章小结 本章注重实践了课本第七章的链接这一过程，讲述了是怎么将一群可重定位目标文件链接到一起以及手段（ld链接器），同时拓展了上课时所没有着重强调的动态链接的具体细节（GOT，PLT之间的相互配合），以及在执行可执行文件的时候是根据什么将可执行文件的各项映射到虚拟内存的。 （以下格式自行编排，编辑时删除） （第5章1分）

第6章 hello进程管理 6.1 进程的概念与作用 进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在早期面向进程设计的计算机结构中，进程是程序的基本执行实体；在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。 6.2 简述壳Shell-bash的作用与处理流程 作用： 一、历史命令：

history 选项 历史命令保存文件

-c 清空历史命令

      -w    立刻把缓存中的历史命令写入保存文件  ~/.bash_history

二、别名

alias cp = 'cp -I’

永久生效：vi root/.bashrc

三、快捷键

ctrl+C 强制终止

ctrl+L 清屏

ctrl+U 删除或者剪切光标之前的内容

ctrl+K 删除或者剪切光标之后的内容

ctrl+Y 粘帖删除或剪切的内容

ctrl+R 从历史命令中搜素

四、 输入输出

    输入重定向

wc < 文件

相当于统计出 几行 几个单词 几个字符

[root@huixuanjiasupenqishi /]# wc <aaa

3 5 16

    输出重定向

    例如可以把半夜维护系统信息先放到一个文件，第二天再看

命令 &> 文件 >>追加

将命令的结果输出到同一个文件

       命令 > 文件一  2> 文件二     

将命令的结果，正确的输出到文件一，错误输出到文件二

特殊的文件写入写出

[root@amusitelangpao data]# ls 1.txt

1.txt

/dev/null 黑洞文件 /dev/zero 零输出器

[root@amusitelangpao data]# ls 1.txt > /dev/null 将结果扔垃圾箱，则不会再显示输出结果

[root@amusitelangpao data]# dd if=/dev/zero of=1.txt bs=1 count=1M 向文件写入1M大小内容

记录了1048576+0 的读入

记录了1048576+0 的写出

1048576字节(1.0 MB)已复制，0.98121 秒，1.1 MB/秒

[root@amusitelangpao data]# ll -h 1.txt

-rw-r–r--. 1 root root 1.0M 8月 9 00:03 1.txt

五、多命令顺序执行

六、管道符

   管道命令符“｜”的作用是将前一个命令的标准输出作为后一个命令的标准输入

   格式为“命令A | 命令B”

[root@localhost ~]# grep “/sbin/nologin” /etc/passwd

bin❌1:1:bin:/bin:/sbin/nologin

daemon❌2:2:daemon:/sbin:/sbin/nologin

adm❌3:4:adm:/var/adm:/sbin/nologin

lp❌4:7:lp:/var/spool/lpd:/sbin/nologin

[root@localhost ~]#wc –l

4

现在用管道｜合并执行计算符合条件的行数： [root@localhost ~]# grep “/sbin/nologin” /etc/passwd | wc -l 处理流程： 1）从终端读入输入的命令。 2）将输入字符串切分获得所有的参数 3）如果是内置命令则立即执行 4）否则调用相应的程序为其分配子进程并运行 5）shell应该接受键盘输入信号，并对这些信号进行相应处理

6.3 Hello的fork进程创建过程 当我们从键盘键入一个不是shell程序的内置命令时，shell就会利用fork函数里创建一个新的进程，该子进程拥有和父进程几乎一样的系统信息，包括相同的写时复制的虚拟内存，相同的文件描述符表，所以此时的子进程几乎和父进程一致，不过他们活在不同的上写文中。 6.4 Hello的execve过程 再利用int execve（const char *filename, const char *argv[],const char *envp[]）函数来在原进程中加载新可执行目标文件时，内核会做出一下几步 1.删除已存在的用户区域：删除当前进程虚拟地址的用户部分中已存在的存于结构 2.映射私有区域：为新进程的代码，数据，bss和栈区域创建新的区域结构 3.映射共享区域：如果a.out程序与共享对象链接，比如说标准C库的libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址中间中的共享区域内。 4.设置程序计数器：execve最后做的一件事就是设置当前进程上下文的程序计数器，使之指向代码区域的入口点（_start地址）

6.5 Hello的进程执行 逻辑控制流：一系列程序计数器PC的值的序列叫做逻辑控制流，进程是轮流使用处理器的，在同一个处理器核心中，每个进程执行它的流的一部分后被抢占（暂时挂起），然后轮到其他进程。 时间片：一个进程执行它的控制流的一部分的每一时间段叫做时间片。 用户模式和内核模式：处理器通常使用一个寄存器提供两种模式的区分，该寄存器描述了进程当前享有的特权，当没有设置模式位时，进程就处于用户模式中，用户模式的进程不允许执行特权指令，也不允许直接引用地址空间中内核区内的代码和数据；设置模式位时，进程处于内核模式，该进程可以执行指令集中的任何命令，并且可以访问系统中的任何内存位置。 上下文信息：上下文就是内核重新启动一个被抢占的进程所需要的状态，它由通用寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构等对象的值构成。 Hello程序中的s运行到sleep函数时，该进程会向内核发送信号之后会使hello所在的进程陷入内核模式，内核会

1. 将hello所在进程的上下文信息保存
2. 恢复将要执行的进程的上下文信息
3. 将控制传递给新的进程，从而实现上下文切换

当hello调用getchar的时候，实际就是再从I/O设备加载数据，此时进程会向处理器芯片上的一个引脚发信号，并将异常号放到系统总线上，来触发中断，这个异常号标识了触发中断的设备。再从I/O设备中读取完数据之后，处理器注意到终端引脚的电压变高了，就从系统总线读取异常号，然后适当调用中断处理程序，当处理完成之后，就将控制返回给原程序的下一条指令。 6.6 hello的异常与信号处理 如图6.4（a），是正常执行hello程序的结果，当程序执行完成之后，进程被回收。 如图6.4（b），是在程序输出2条info之后按下ctrl-z的结果，当按下ctrl-z之后，shell父进程收到SIGSTP信号，信号处理函数的逻辑是打印屏幕回显、将hello进程挂起，通过ps命令我们可以看出hello进程没有被回收，此时他的后台job号是1，调用fg 1将其调到前台，此时shell程序首先打印hello的命令行命令，hello继续运行打印剩下的8条info，之后输入字串，程序结束，同时进程被回收。 如图6.4（c）是在程序输出3条info之后按下ctrl-c的结果，当按下ctrl-c之后，shell父进程收到SIGINT信号，信号处理函数的逻辑是结束hello，并回收hello进程。 如图6.4（d）是在程序运行中途乱按的结果，可以发现，乱按只是将屏幕的输入缓存到stdin，当getchar的时候读出一个’\n’结尾的字串（作为一次输入），其他字串会当做shell命令行输入。

   图6.4 (a) 正常运行hello程序

   图6.4（b）运行中途按下ctrl-z

   图6.4（c）运行中途按下ctrl-c



   图6.4（d）运行中途乱

6.7本章小结 本章主要讲述了hello程序再从可执行文件到能真正再系统中执行的一个过程，以及是怎么再程序之中处理异常的方法，其中涉及中断和陷阱的两种的异常情况。并实践了再程序中测试不同的shell程序对于hello程序的影响。 （第6章1分）

第7章 hello的存储管理 7.1 hello的存储器地址空间 物理地址(physical address) 用于内存芯片级的单元寻址，与处理器和CPU连接的地址总线相对应。 ——这个概念应该是这几个概念中最好理解的一个，但是值得一提的是，虽然可以直接把物理地址理解成插在机器上那根内存本身，把内存看成一个从0字节一直到最大空量逐字节的编号的大数组，然后把这个数组叫做物理地址，但是事实上，这只是一个硬件提供给软件的抽像，内存的寻址方式并不是这样。所以，说它是“与地址总线相对应”，是更贴切一些，不过抛开对物理内存寻址方式的考虑，直接把物理地址与物理的内存一一对应，也是可以接受的。也许错误的理解更利于形而上的抽像。

虚拟内存(virtual memory) 这是对整个内存（不要与机器上插那条对上号）的抽像描述。它是相对于物理内存来讲的，可以直接理解成“不直实的”，“假的”内存，例如，一个0x08000000内存地址，它并不对就物理地址上那个大数组中0x08000000 - 1那个地址元素； 之所以是这样，是因为现代操作系统都提供了一种内存管理的抽像，即虚拟内存（virtual memory）。进程使用虚拟内存中的地址，由操作系统协助相关硬件，把它“转换”成真正的物理地址。这个“转换”，是所有问题讨论的关键。 有了这样的抽像，一个程序，就可以使用比真实物理地址大得多的地址空间。（拆东墙，补西墙，银行也是这样子做的），甚至多个进程可以使用相同的地址。不奇怪，因为转换后的物理地址并非相同的。 ——可以把连接后的程序反编译看一下，发现连接器已经为程序分配了一个地址，例如，要调用某个函数A，代码不是call A，而是call 0x0811111111 ，也就是说，函数A的地址已经被定下来了。没有这样的“转换”，没有虚拟地址的概念，这样做是根本行不通的。 打住了，这个问题再说下去，就收不住了。

逻辑地址(logical address) Intel为了兼容，将远古时代的段式内存管理方式保留了下来。逻辑地址指的是机器语言指令中，用来指定一个操作数或者是一条指令的地址。以上例，我们说的连接器为A分配的0x08111111这个地址就是逻辑地址。 ——不过不好意思，这样说，好像又违背了Intel中段式管理中，对逻辑地址要求，“一个逻辑地址，是由一个段标识符加上一个指定段内相对地址的偏移量，表示为 [段标识符：段内偏移量]，也就是说，上例中那个0x08111111，应该表示为[A的代码段标识符: 0x08111111]，这样，才完整一些”

线性地址(linear address)或也叫虚拟地址(virtual address) 跟逻辑地址类似，它也是一个不真实的地址，如果逻辑地址是对应的硬件平台段式管理转换前地址的话，那么线性地址则对应了硬件页式内存的转换前地址。 7.2 Intel逻辑地址到线性地址的变换-段式管理 CPU段式内存管理，逻辑地址如何转换为线性地址 一个逻辑地址由两部份组成，段标识符: 段内偏移量。段标识符是由一个16位长的字段组成，称为段选择符。其中前13位是一个索引号。后面3位包含一些硬件细节，如图：

索引号，或者直接理解成数组下标——那它总要对应一个数组吧，它又是什么东东的索引呢？这个东东就是“段描述符(segment descriptor)”，呵呵，段描述符具体地址描述了一个段（对于“段”这个字眼的理解，我是把它想像成，拿了一把刀，把虚拟内存，砍成若干的截——段）。这样，很多个段描述符，就组了一个数组，叫“段描述符表”，这样，可以通过段标识符的前13位，直接在段描述符表中找到一个具体的段描述符，这个描述符就描述了一个段，我刚才对段的抽像不太准确，因为看看描述符里面究竟有什么东东——也就是它究竟是如何描述的，就理解段究竟有什么东东了，每一个段描述符由8个字节组成，如下图：

这些东东很复杂，虽然可以利用一个数据结构来定义它，不过，我这里只关心一样，就是Base字段，它描述了一个段的开始位置的线性地址。

Intel设计的本意是，一些全局的段描述符，就放在“全局段描述符表(GDT)”中，一些局部的，例如每个进程自己的，就放在所谓的“局部段描述符表(LDT)”中。那究竟什么时候该用GDT，什么时候该用LDT呢？这是由段选择符中的T1字段表示的，=0，表示用GDT，=1表示用LDT。

GDT在内存中的地址和大小存放在CPU的gdtr控制寄存器中，而LDT则在ldtr寄存器中。

好多概念，像绕口令一样。这张图看起来要直观些：

首先，给定一个完整的逻辑地址[段选择符：段内偏移地址]， 1、看段选择符的T1=0还是1，知道当前要转换是GDT中的段，还是LDT中的段，再根据相应寄存器，得到其地址和大小。我们就有了一个数组了。 2、拿出段选择符中前13位，可以在这个数组中，查找到对应的段描述符，这样，它了Base，即基地址就知道了。 3、把Base + offset，就是要转换的线性地址了。

还是挺简单的，对于软件来讲，原则上就需要把硬件转换所需的信息准备好，就可以让硬件来完成这个转换了。OK，来看看Linux怎么做的。 Linux的段式管理 Intel要求两次转换，这样虽说是兼容了，但是却是很冗余，呵呵，没办法，硬件要求这样做了，软件就只能照办，怎么着也得形式主义一样。 另一方面，其它某些硬件平台，没有二次转换的概念，Linux也需要提供一个高层抽像，来提供一个统一的界面。所以，Linux的段式管理，事实上只是“哄骗”了一下硬件而已。

按照Intel的本意，全局的用GDT，每个进程自己的用LDT——不过Linux则对所有的进程都使用了相同的段来对指令和数据寻址。即用户数据段，用户代码段，对应的，内核中的是内核数据段和内核代码段。这样做没有什么奇怪的，本来就是走形式嘛，像我们写年终总结一样。 include/asm-i386/segment.h #define GDT_ENTRY_DEFAULT_USER_CS 14 #define __USER_CS (GDT_ENTRY_DEFAULT_USER_CS * 8 + 3)

#define GDT_ENTRY_DEFAULT_USER_DS 15 #define __USER_DS (GDT_ENTRY_DEFAULT_USER_DS * 8 + 3)

#define GDT_ENTRY_KERNEL_BASE 12

#define GDT_ENTRY_KERNEL_CS (GDT_ENTRY_KERNEL_BASE + 0) #define __KERNEL_CS (GDT_ENTRY_KERNEL_CS * 8)

#define GDT_ENTRY_KERNEL_DS (GDT_ENTRY_KERNEL_BASE + 1) #define __KERNEL_DS (GDT_ENTRY_KERNEL_DS * 8) 复制代码

把其中的宏替换成数值，则为： #define __USER_CS 115 [00000000 1110 0 11] #define __USER_DS 123 [00000000 1111 0 11] #define __KERNEL_CS 96 [00000000 1100 0 00] #define __KERNEL_DS 104 [00000000 1101 0 00] 复制代码

方括号后是这四个段选择符的16位二制表示，它们的索引号和T1字段值也可以算出来了 __USER_CS index= 14 T1=0 __USER_DS index= 15 T1=0 __KERNEL_CS index= 12 T1=0 __KERNEL_DS index= 13 T1=0 复制代码

T1均为0，则表示都使用了GDT，再来看初始化GDT的内容中相应的12-15项(arch/i386/head.S)： .quad 0x00cf9a000000ffff /* 0x60 kernel 4GB code at 0x00000000 / .quad 0x00cf92000000ffff / 0x68 kernel 4GB data at 0x00000000 / .quad 0x00cffa000000ffff / 0x73 user 4GB code at 0x00000000 / .quad 0x00cff2000000ffff / 0x7b user 4GB data at 0x00000000 */ 复制代码

按照前面段描述符表中的描述，可以把它们展开，发现其16-31位全为0，即四个段的基地址全为0。

这样，给定一个段内偏移地址，按照前面转换公式，0 + 段内偏移，转换为线性地址，可以得出重要的结论，“在Linux下，逻辑地址与线性地址总是一致（是一致，不是有些人说的相同）的，即逻辑地址的偏移量字段的值与线性地址的值总是相同的。！！！”

忽略了太多的细节，例如段的权限检查。呵呵。

Linux中，绝大部份进程并不例用LDT，除非使用Wine ，仿真Windows程序的时候。

7.3 Hello的线性地址到物理地址的变换-页式管理 4.CPU的页式内存管理

CPU的页式内存管理单元，负责把一个线性地址，最终翻译为一个物理地址。从管理和效率的角度出发，线性地址被分为以固定长度为单位的组，称为页(page)，例如一个32位的机器，线性地址最大可为4G，可以用4KB为一个页来划分，这页，整个线性地址就被划分为一个tatol_page[2^20]的大数组，共有2的20个次方个页。这个大数组我们称之为页目录。目录中的每一个目录项，就是一个地址——对应的页的地址。

另一类“页”，我们称之为物理页，或者是页框、页桢的。是分页单元把所有的物理内存也划分为固定长度的管理单位，它的长度一般与内存页是一一对应的。

这里注意到，这个total_page数组有2^20个成员，每个成员是一个地址（32位机，一个地址也就是4字节），那么要单单要表示这么一个数组，就要占去4MB的内存空间。为了节省空间，引入了一个二级管理模式的机器来组织分页单元。文字描述太累，看图直观一些：

如上图， 1、分页单元中，页目录是唯一的，它的地址放在CPU的cr3寄存器中，是进行地址转换的开始点。万里长征就从此长始了。 2、每一个活动的进程，因为都有其独立的对应的虚似内存（页目录也是唯一的），那么它也对应了一个独立的页目录地址。——运行一个进程，需要将它的页目录地址放到cr3寄存器中，将别个的保存下来。 3、每一个32位的线性地址被划分为三部份，面目录索引(10位)：页表索引(10位)：偏移(12位) 依据以下步骤进行转换： 1、从cr3中取出进程的页目录地址（操作系统负责在调度进程的时候，把这个地址装入对应寄存器）； 2、根据线性地址前十位，在数组中，找到对应的索引项，因为引入了二级管理模式，页目录中的项，不再是页的地址，而是一个页表的地址。（又引入了一个数组），页的地址被放到页表中去了。 3、根据线性地址的中间十位，在页表（也是数组）中找到页的起始地址； 4、将页的起始地址与线性地址中最后12位相加，得到最终我们想要的葫芦；

这个转换过程，应该说还是非常简单地。全部由硬件完成，虽然多了一道手续，但是节约了大量的内存，还是值得的。那么再简单地验证一下： 1、这样的二级模式是否仍能够表示4G的地址； 页目录共有：2^10项，也就是说有这么多个页表 每个目表对应了：2^10页； 每个页中可寻址：2^12个字节。 还是2^32 = 4GB

2、这样的二级模式是否真的节约了空间； 也就是算一下页目录项和页表项共占空间 (2^10 * 4 + 2 ^10 *4) = 8KB。哎，……怎么说呢！！！ 红色错误，标注一下，后文贴中有此讨论。。。。。。 按<深入理解计算机系统>中的解释,二级模式空间的节约是从两个方面实现的: A、如果一级页表中的一个页表条目为空，那么那所指的二级页表就根本不会存在。这表现出一种巨大的潜在节约，因为对于一个典型的程序，4GB虚拟地址空间的大部份都会是未分配的； B、只有一级页表才需要总是在主存中。虚拟存储器系统可以在需要时创建，并页面调入或调出二级页表，这就减少了主存的压力。只有最经常使用的二级页表才需要缓存在主存中。——不过Linux并没有完全享受这种福利，它的页表目录和与已分配页面相关的页表都是常驻内存的。

值得一提的是，虽然页目录和页表中的项，都是4个字节，32位，但是它们都只用高20位，低12位屏蔽为0——把页表的低12屏蔽为0，是很好理解的，因为这样，它刚好和一个页面大小对应起来，大家都成整数增加。计算起来就方便多了。但是，为什么同时也要把页目录低12位屏蔽掉呢？因为按同样的道理，只要屏蔽其低10位就可以了，不过我想，因为12>10，这样，可以让页目录和页表使用相同的数据结构，方便。

本贴只介绍一般性转换的原理，扩展分页、页的保护机制、PAE模式的分页这些麻烦点的东东就不啰嗦了……可以参考其它专业书籍。

5.Linux的页式内存管理 原理上来讲，Linux只需要为每个进程分配好所需数据结构，放到内存中，然后在调度进程的时候，切换寄存器cr3，剩下的就交给硬件来完成了（呵呵，事实上要复杂得多，不过偶只分析最基本的流程）。

前面说了i386的二级页管理架构，不过有些CPU，还有三级，甚至四级架构，Linux为了在更高层次提供抽像，为每个CPU提供统一的界面。提供了一个四层页管理架构，来兼容这些二级、三级、四级管理架构的CPU。这四级分别为：

页全局目录PGD（对应刚才的页目录） 页上级目录PUD（新引进的） 页中间目录PMD（也就新引进的） 页表PT（对应刚才的页表）。

整个转换依据硬件转换原理，只是多了二次数组的索引罢了，如下图：

那么，对于使用二级管理架构32位的硬件，现在又是四级转换了，它们怎么能够协调地工作起来呢？嗯，来看这种情况下，怎么来划分线性地址吧！ 从硬件的角度，32位地址被分成了三部份——也就是说，不管理软件怎么做，最终落实到硬件，也只认识这三位老大。 从软件的角度，由于多引入了两部份，，也就是说，共有五部份。——要让二层架构的硬件认识五部份也很容易，在地址划分的时候，将页上级目录和页中间目录的长度设置为0就可以了。 这样，操作系统见到的是五部份，硬件还是按它死板的三部份划分，也不会出错，也就是说大家共建了和谐计算机系统。

这样，虽说是多此一举，但是考虑到64位地址，使用四层转换架构的CPU，我们就不再把中间两个设为0了，这样，软件与硬件再次和谐——抽像就是强大呀！！！

例如，一个逻辑地址已经被转换成了线性地址，0x08147258，换成二制进，也就是： 0000100000 0101000111 001001011000 内核对这个地址进行划分 PGD = 0000100000 PUD = 0 PMD = 0 PT = 0101000111 offset = 001001011000

现在来理解Linux针对硬件的花招，因为硬件根本看不到所谓PUD,PMD，所以，本质上要求PGD索引，直接就对应了PT的地址。而不是再到PUD和PMD中去查数组（虽然它们两个在线性地址中，长度为0，2^0 =1，也就是说，它们都是有一个数组元素的数组），那么，内核如何合理安排地址呢？ 从软件的角度上来讲，因为它的项只有一个，32位，刚好可以存放与PGD中长度一样的地址指针。那么所谓先到PUD，到到PMD中做映射转换，就变成了保持原值不变，一一转手就可以了。这样，就实现了“逻辑上指向一个PUD，再指向一个PDM，但在物理上是直接指向相应的PT的这个抽像，因为硬件根本不知道有PUD、PMD这个东西”。

然后交给硬件，硬件对这个地址进行划分，看到的是： 页目录 = 0000100000 PT = 0101000111 offset = 001001011000 嗯，先根据0000100000(32)，在页目录数组中索引，找到其元素中的地址，取其高20位，找到页表的地址，页表的地址是由内核动态分配的，接着，再加一个offset，就是最终的物理地址了。 7.4 TLB与四级页表支持下的VA到PA的变换

如图所示，在core i7下虚拟地址空间48位，物理地址空间52位，页表大小4KB，4级页表。TLB 4路16组相联。CR3指向第一级页表的起始位置（上下文一部分）。 解析前提条件：由一个页表大小4KB，一个PTE条目8B，共512个条目，使用9位二进制索引，一共4个页表共使用36位二进制索引，所以VPN共36位，因为VA 48位，所以VPO 12位；因为TLB共16组，所以TLBI需4位，因为VPN 36位，所以TLBT 32位。 则在该处理器下，从虚拟地址到物理地址遵循一下步骤 1.在mmu中将虚拟地址的前36位值取出(48位的后12位为块偏移) 2.将这36送至TLB（翻译后备缓冲器）中根据后4位来选取组并根据前32位作为标记来搜寻该组中是否有符合要求的PPN，若有则取出，并和VPO组合成为物理地址 3.没有在TLB中找到，则将36位VPN分割为四份，每份9位，作为分级页表的偏移量，之后首先从CR3寄存器中取出一级页表的首地址，加上前9位VPN的值（左移3位之后的），得到这个地址下8字节的物理地址，取出前40位作为作为二级页表的基地址，此后反复这一过程，直到从四级页表取出前40PPN和VPO相组合成为物理地址

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

如图所示，在我们的到了52位的物理地址之后，由于L1缓存中每块有64字节，则CO=6，由于总共有64组则CI=6剩余的40位作为标记位CT 那么我们在得到物理地址之后，就先将这个地址分割为三个部分CT，CI，CO 依据CI在L1高速缓存行的对应组中搜索有效位为1同时CT与物理地址相同的行，若找到则从这一高速缓存行中第CO个字节开始取出相应大小字，将值返回给处理器 7.6 hello进程fork时的内存映射

如图，在fork子进程之后，子进程在上下文中会将父进程的mm_struct复制一遍之后父子进程同时在区域结构同修改vm_prot的权限为只读，之后若其中一方要修改物理内存中的私有部分，则内核会在物理内存中将这个部分设置一个副本，让修改的进程最后一级页表的PPN值修改至此处，并在这个副本上进行修改 7.7 hello进程execve时的内存映射 execve函数调用驻留在内核区域的启动加载器代码，在当前进程中加载并运行包含在可执行目标文件hello中的程序，用hello程序有效地替代了当前程序。加载并运行hello需要以下几个步骤： 1.删除已存在的用户区域，删除当前进程虚拟地址的用户部分中的已存在的区域结构。 2.映射私有区域，为新程序的代码、数据、bss和栈区域创建新的区域结构，所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为hello文件中的.text和.data区，bss区域是请求二进制零的，映射到匿名文件，其大小包含在hello中，栈和堆地址也是请求二进制零的，初始长度为零。 3.映射共享区域， hello程序与共享对象libc.so链接，libc.so是动态链接到这个程序中的，然后再映射到用户虚拟地址空间中的共享区域内。 4.设置程序计数器（PC），execve做的最后一件事情就是设置当前进程上下文的程序计数器，使之指向代码区域的入口点。

图 加载器是如何映射用户地址空间区域的

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

缺页故障：当mmu翻译虚拟地址时发现在页表项中，该页表项的有效位为0（这个数据还在磁盘中，未被加载到内存中），此时会触发缺页中断，进程陷入内核模式，进入异常处理程序，异常处理程序将一个页块大小的数据加载到内存中，之后将控制返还给源程序。如果选择的内存页被修改过，则要先将这个块交换会磁盘之后再将目标数据加载到内存页 7.9动态存储分配管理 Printf会调用malloc，请简述动态内存管理的基本方法与策略。 动态分配器就是我们平时在C语言上用的malloc和free,realloc，通过分配堆上的内存给程序，我们通过向堆申请一块连续的内存，然后将堆中连续的内存按malloc所需要的块来分配，不够了，就继续向堆申请新的内存，也就是扩展堆，这里设定，堆顶指针想上伸展（堆的大小变大），不能向下增长（虽然，sbrk函数也可以让指针想下伸展），以下是堆的一些说明：

管理这个堆，主要有这几步操作：找到合适的块，分割块，合并块。 (1).首次适配：就是在搜索整个堆或者空闲链表的时候，只要找到一个比needsize就直接申请出去。（优点：速度快。缺点：不一定找到空间最合适的块，空间利用率降低（但是利用分离适配的方法可以让首次适配的空间利用率也提升）） (2).最佳适配：在搜索的时候，找到一个needsize<=size && min(size-needsize) 的块。（优点：能找到最合适的块，空间利用率高。缺点：对于大的空闲块搜索效率低（因为经常都是把小的空闲块安插在链表前）） (3).下一次适配：下一次适配和首次适配很类似，首次适配是从空闲链表头开始寻找，下一次适配是从上一次分配的地方开始搜索。但有些研究表明，下一次适配比首次适配的效率更快，但空间利用率更低。所以我们的实验中一般采用首次适配和最佳适配。 空间利用率： 2. 效率：就是我们执行这些操作的时间复杂度，我们的目标就是让上面提到的每一步操作都能达到常数时间。 但其实很多时候，空间利用率和效率是相互矛盾的，我们只能通过我们的设计取到最优解。 一. 隐式空闲链表+首次适配+普通的realloc 这部分的代码CSAPP的书上都提供了，我就不赘述，要注意的是，我们下面所有的优化设计都基于这个最基本的设计。所以，你只有将这个最简单的设计理解下了，才能继续下去。这个方法的缺点很明显：find_fit是整个堆的常数时间，这是相当慢的。但是好处就是，这个算法的空间利用率挺理想的。 二.显式空闲链表+首次适配 OR 按地址进行放置空闲链表 针对于显式空闲链表，一个空闲块中就多了前继和后继结点，构成双向链表，如下图所示：

3.分离适配+改进的realloc： 分离适配的基本思想就是将所有空闲块分成大小类，分别分成0_8,916,17_32,3364,65~128…… 2049_4096,4097正无穷，这么几个大小类的空闲链表，然后我们想要进行malloc的时候，就将空闲块进行筛选，将