hit csapp大作业 程序人生-Hello’s P2P
计算机系统
大作业
题 目 程序人生-Hello’s P2P
专 业 计算机科学与技术
学 号 2021112810
班 级 2103103
学 生 肖芩芩
指 导 教 师 刘宏伟
计算机科学与技术学院
2022年5月
本文遍历了hello.c在Linux下生命周期,借助Linux下系列开发工具,通过对其预处理、编译、汇编等过程的分步解读及对比来学习各个过程在Linux下实现机制及原因。并由操作系统进行进程管理、存储管理和I/O管理的全过程。以此将CSAPP课程中的内容进行全面地总结和梳理,加深对计算机系统的理解。
关键词:1.编译系统;2.Hello程序;3.进程;4.信号与异常;5.虚拟内存;6.I/O管理。
目 录
第1章 概述
1.1 Hello简介
根据Hello的自白,利用计算机系统的术语,简述Hello的P2P,020的整个过程。
P2P:From Program to Process。编辑完成的hello.c程序先经过cpp预处理器的预处理得hello.i文件,ccl编译器将其编译获得hello.s文件,as汇编器再将其翻译为机器语言指令获得hello.o文件,再经过ld链接器进行链接得可执行文件hello。shell输入执行命令后,进程管理为其fork()一个子进程。即完成了P2P的过程。
020:From Zero to Zero。进程管理给hello进行execve操作,进行mmap操作将其映射到内存中,接着给运行的hello分配时间片来执行逻辑控制流。当程序运行结束后,父进程会回收hello进程,内核删除相关的数据。即完成了020的过程。
1.2 环境与工具
硬件环境:X64 CPU;2GHz;2G RAM;256GHD Disk 以上
软件环境:Windows7 64位以上;VirtualBox/Vmware 11以上;Ubuntu 16.04 LTS 64位/优麒麟 64位
开发与调试工具:gcc,gdb,vim,edb,readelf,HexEdi,objdump,ldd等
1.3 中间结果
文件名称 |
文件作用 |
hello.i |
预处理之后文本文件 |
hello.s |
编译之后的汇编文件 |
hello.o |
汇编之后的可重定位目标执行 |
hello |
链接之后的可执行目标文件 |
helloo_objdmp |
Hello.o 的反汇编代码 |
helloo.elf |
Hello.o 的 ELF 格式 |
hello_objdmp |
Hello 的反汇编代码 |
hello.elf |
Hellode ELF 格式 |
1.4 本章小结
本章对hello做了总体的介绍,简述了hello的p2p和020过程,列出并介绍了本次实验的环境和工具,阐明了这次实验中产生了中间产物,是本次实验的总领部分,后文将依据本章做详细展开。
第2章 预处理
2.1 预处理的概念与作用
概念:C语言的预处理器在源代码编译之前对其进行一些文本性质的操作。它的主要任务包括删除注释、插入被#include指令包含的文件内容、定义和替换由#define指令定义的符号,同时确定代码的部分内容是否应该根据一些条件编译指令进行编译。
作用:预处理可以在在将c程序转化为s的汇编程序之前对于宏定义处理,方便后续的代码转化,并且对于在汇编中无用的注释进行处理,删去无用部分对后续操作做准备。
- 宏定义:#define 指令定义一个宏,#undef指令删除一个宏定义。
- 文件包含:#include指令导致一个指定文件的内容被包含到程序中。
- 条件编译:#if,#ifdef,#ifndef,#elif,#else和#dendif指令可以根据编译器可以测试的条件来将一段文本包含到程序中或排除在程序之外。
2.2在Ubuntu下预处理的命令
预处理命令:gcc -E hello.c -o hello.i
图1.预处理结果
2.3 Hello的预处理结果解析
图2.hello.i的代码截图
预处理后,文件变成3062行的文本文件,前面为头文件<stdio.h> <unistd.h> <stdlib.h> 的内容被复制插入进代码中,消除include宏,随后是原本的代码。可以看到,预处理后的文件更加完整和清晰,也没有了多余的注释等无用的部分。
2.4 本章小结
本章说明了P2P过程中的预处理部分,深入了解预处理器(cpp)将hello.c进行预处理,生成hello.i文件的过程,并分析其i文件的内容。了解了预处理的大致过程,也分析明确了预处理的重要性。
第3章 编译
3.1 编译的概念与作用
概念:编译就是将源语言经过词法分析、语法分析、语义分析以及经过一系列优化后生成汇编代码的过程。其以高级程序设计语言书写的源程序作为输入,而以汇编语言或机器语言表示的目标程序作为输出。编译器将文本文件 hello.i 翻译成文本文件 hello.s,它包含一个汇编语言程序。
作用:
1.语法分析:编译程序的语法分析器以单词符号作为输入,分析单词符号串是否形成符合语法规则的语法单位,方法分为两种:自上而下分析法和自下而上分析法。
2.中间代码:源程序的一种内部表示,或称中间语言。中间代码的作用是可使编译程序的结构在逻辑上更为简单明确,特别是可使目标代码的优化比较容易实现中间代码。
3.代码优化:指对程序进行多种等价变换,使得从变换后的程序出发,能生成更有效的目标代码。
4.目标代码:生成是编译的最后一个阶段。目标代码生成器把语法分析后或优化后的中间代码变换成目标代码。此处指汇编语言代码,须经过汇编程序汇编后,成为可执行的机器语言代码。编译出的目标程序通常还要经历运行阶段,以便在运行程序的支持下运行,加工初始数据,算出所需的计算结果。
3.2 在Ubuntu下编译的命令
编译命令:gcc -S hello.i -o hello.s
图3.编译过程
3.3 Hello的编译结果解析
3.3.1 hello.s文件中的伪指令
伪指令用于指导汇编器和链接器的工作。
内容 |
含义 |
.file |
源文件声明 |
.text |
代码节 |
.section .rodata |
只读代码段 |
.align |
指令或者数据的存放地址进行对齐的方式 |
.global |
声明全局符号 |
.type |
声明符号是数据类型或函数类型 |
3.3.2 rodata节数据
图4.rodata节数据
在.rodata段,我们有两个数据。.LC0存储的是第一条printf语句打印的字符串"用法: Hello 学号 姓名 秒数!n"。.LC1存储的是第二条printf语句所打印的字符串,其中的%s是占位符。
3.3.3局部变量
在hello.c程序main函数中定义了局部变量i,用于进行遍历操作。
编译处理会将它存储到用户栈中,可见i被赋予初值0存储在栈中-4(%rbp)的位置。
3.3.4数组
数组char *argv[]是main函数的第二个形式参数,来源于命令行输入的数据,argv是存放char指针的数组。argv数组中一个元素大小为8个字节,我们可以看到在hello.s中2次指令movq (%rax), %rdx与movq (%rax), %rax,是为了解析终端输入的命令参数。
3.3.5 赋值操作
使用数据传送命令,我们可以进行赋值操作。最简单形式的数据传输类型是MOV类,MOV有movb,movw,movl,movq。分别操作1、2、4、8字节的数据。mov操作的源操作数可以是:立即数、寄存器、内存。目的操作数可以是:寄存器、内存。x86-64规定两个操作数不能都指向内存。
3.3.6 算术运算
在循环操作中,使用了++操作符。对应的汇编代码为,对i自加,栈上存储变量i的值加1。
3.3.7 控制转移
在hello.c中,两次输出中包含常量字符串。编译处理时,由于常量字符串被提前声明,在这里输出时使用了控制转移。
图10(1)为argc与4的比较,如果相等则跳转到L2,在原程序里体现为不进入if语句,如果不相等,不跳转继续执行,体现为进入if语句。
图10(2)为for的循环条件,当i小于等于8时,跳转到L4,L4实现的时输出语句的相关操作。
3.3.8 循环
汇编中没有相应的指令存在,可以用条件测试和跳转组合起来实现循环的效果。
图11.循环控制条件
初始时,i为0,存放在栈中-4
3.3.9 类型转换
在语句sleep(atoi(argv[3]));中存在隐式类型转换。atoi函数的返回值是int型,而sleep函数的参数类型是unsigned long,存在着数据由int型向unsigned long型的转换。
3.3.10函数操作
main函数:
参数传递:传入参数argc和argv[],分别用寄存器%rdi和%rsi存储。
函数返回:设置%eax为0并且返回,对应return 0 。
main函数中调用其他函数
图12.函数调用
call表示函数调用,如上图所示,main函数调用了puts函数,exit函数,printf函数,atoi函数,sleep函数。其中exit参数是1,atoi函数的参数是argv[3],sleep函数的参数是atoi(argv[3])的返回值。
3.4 本章小结
本章说明了P2P过程中的编译部分,通过hello.s分析了c语言如何转换成为汇编代码。并对生成的汇编程序中涉及到的C语言各种数据类型和各类操作做了说明。
第4章 汇编
4.1 汇编的概念与作用
汇编概念:驱动程序运行汇编器as,将汇编语言的ascii码文件(这里是hello.s)翻译成机器语言的可重定位目标文件(hello.o)的过程称为汇编。hello.o是二进制文件。
汇编的作用:将汇编代码转变为机器指令,生成目标文件。
4.2 在Ubuntu下汇编的命令
gcc -c hello.s -o hello.o
图13.汇编过程
4.3 可重定位目标elf格式
1.ELF头
命令行输入:$ readelf -h hello.o
readelf可以显示ELF文件的相关内容,-h选项表示只显示header信息。
图14.elf头信息
ELF头以一个16字节的序列开始,这个序列描述了生成该文件的系统的字的大小和字节顺序。ELF头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。其中包括ELF头的大小、目标文件的类型(如可重定位、可执行或者共享的)、机器类型(如x86-64)、节头部表(section header table) 的文件偏移,以及节头部表中条目的大小和数量。在上述表中,可以看出关于ELF header的长度这里也给出了,一共是64个字节。
2.section表
命令行输入:$ readelf -S hello.o 其中-S选项表示打印整个section表的信息
图15.section表信息
.text 已编译程序的机器代码。
.rodata 只读数据,比如printf语句中的格式串和开关语句的跳转表。
.data 已初始化的全局和静态C变量。局部C变量在运行时被保存在栈中,既不出现在.data节中,也不出现在.bss节中。
.bss 未初始化的全局和静态C变量,以及所有被初始化为0的全局或静态变量。在目标文件中这个节不占据实际的空间,它仅仅是一个占位符。目标文件格式区分已初始化和未初始化变量是为了空间效率,在目标文件中,未初始化变量不需要占据任何实际的磁盘空间。运行时,在内存中分配这些变量,初始值为0。
.symtab: 一个符号表,它存放在程序中定义和引用的函数和全局变量的信息。一些程序员错误地认为必须通过-g选项来编译一个程序,才能得到符号表信息。实际上,每个可重定位目标文件在.symtab中都有一张符号表(除非程序员特意用STRIP命令去掉它)。然而,和编译器中的符号表不同,symtab符号表不包含局部变量的条目。
.rel.text 一个.text节中位置的列表,当链接器把这个目标文件和其他文件组合时,需要修改这些位置。一般而言,任何调用外部函数或者引用全局变量的指令都需要修改。另一方面,调用本地函数的指令则不需要修改。注意,可执行目标文件中并不需要重定位信息,因此通常省略,除非用户显式地指示链接器包含这些信息。
.rel.data 被模块引用或定义的所有全局变量的重定位信息。一般而言,任何已初始化的全局变量,如果它的初始值是一个全局变量地址或者外部定义函数的地址,都需要被修改。
.debug 一个调试符号表,其条目是程序中定义的局部变量和类型定义,程序中定义和引用的全局变量,以及原始的C源文件。只有以-g选项调用编译器驱动程序时,才会得到这张表。
.line 原始C源函数程序中的行号和.text节中机器指令之间的映射。只有以-g选项调用编译器驱动程序时,才会得到这张表。
.strtab 一个字符串标,其内容包括.symtab和.debug节中的符号表,以及节头部中的节名字。字符串表就是以NULL结尾的字符串的序列。
描述目标文件的节 节头部表 不同节的位置和大小是由节头部表描述的,其中目标文件中每个节都有一个固定大小的条目(entry)。
3.符号表
命令行输入$ readelf -s hello.o
符号表(.symtab)存放程序中定义和引用的函数和全局变量的信息。name是符号名称,对于可冲定位目标模块,value是符号相对于目标节的起始位置偏移,对于可执行目标文件,该值是一个绝对运行的地址。size是目标的大小,type要么是数据要么是函数。Bind字段表明符号是本地的还是全局的
图16.符号表信息
。
4.重定位节
命令行输入$ readelf -r --relocs hello.o
图17.重定位节信息
重定位节(.rela.text): .text 节中位置的列表,包含.text节中需要进行重定位的信息,当链接器把目标文件和其他文件组合时,需要修改这些位置。
重定位节中各项符号的信息:
- Offset偏移量:需要被修改的引用节的偏移
- Info信息:包括符号和类型两个部分,符号在前面四个字节,类型在后面四个字节
- Sym.Value符号值:标识被修改引用应该指向的符号,
- Type类型:重定位的类型
- Addend加数:一个有符号常数,一些重定位要使用它对被修改引用的值做偏移调整
- Sym.Name符号名称:重定向到的目标的名称。
4.4 Hello.o的结果解析
反汇编命令:objdump -d -r hello.o
图18.反汇编代码(左)和汇编代码(右)部分内容
可以观察到,二者十分相似。但是许多地方不相同。
- 反汇编代码中不再有汇编代码中的伪节。
- 反汇编代码省去了汇编代码中标志操作数的字节大小的符号
- 在跳转时,汇编代码直接访问了.rodata节的数据,直接按函数名调用了函数,而反汇编代码中二者均是相对偏移地址,需要进行重定位得到绝对地址。
图19.反汇编部分代码
机器语言指的是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。图19中的左侧数字序列就是每一条指令的机器代码。上图所示的机器代码是十六进制的。
4.5 本章小结
本章利用汇编操作将汇编语言转化为机器语言,可重定位目标文件已经完成,为下一步链接生成可执行文件做好准备。
第5章 链接
5.1 链接的概念与作用
链接的概念:hello程序调用了printf函数,它存在于一个名为printf.o的单独的预编译好了的目标文件中,而这个文件必须以某种方式合并到我们的hello.o程序中。连接器(ld)就负责处理这种合并。结果就得到了hello文件,它是一个可执行目标文件 (或者称为 可执行文件 ),可以被加载到内存中,由系统执行。链接程序运行需要的一大堆目标文件,以及所依赖的其它库文件,最后生成可执行文件。
作用:链接时会将可重定位目标文件实现重定位,生成最终的可执行文件。
5.2 在Ubuntu下链接的命令
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
图20.链接过程
5.3 可执行目标文件hello的格式
输入命令:readelf -a hello查看可执行文件中的信息内容
1.ELF 头部表
图21.ELF Header
hello与hello.o的ELF头大致相同,不同之处在于hello的类型为EXEC可执行文件,表明hello是一个可执行目标文件,有25个字节。
2.节头部表
图22.Section Header
节头部表是描述目标文件的节,各节的基本信息均在其中进行了声明,包括名称,大小,类型,全体大小,地址,旗标,偏移量,对齐等信息等。
3.重定位节
图23.重定位节
4.符号表
图24.符号表
5.4 hello的虚拟地址空间
命令行输入:edb --run hello
观察edb的Data Dump窗口。窗口显示虚拟地址由0x401000开始,到0x402000结束
图25.edb .Data Dump窗口
5.5 链接的重定位过程分析
hello反汇编代码中跳转地址是虚拟地址,完成了重定位(如图26),而hello.o反汇编代码中的是相对偏移地址,未完成重定位的过程。(如图27)
链接的重定位的过程:
重定位节和符号定义链接器将相同类型的节合并,生成ELF节。链接器将运行时的内存地址分配给生成的节,此时程序中每条指令和全局变量都有唯一的运行时地址。要合并相同的节,确定新节中所有定义符号在虚拟地址空间中的地址,还要对引用符号进行重定位,修改.text节和.data节中对每个符号的引用,需要用到在.rel_data和.rel_text节中保存的重定位信息。
首先,我们观察hello.o的反汇编代码。可以观察到,有许多地方并没有填入正确的地址,正等待进行链接。R_X86_64_PLT32表示puts函数需要通过共享库进行动态链接。在hello文件的反汇编代码中,我们发现之前的重定位地址已经被填入了正常的地址。观察elf文件信息,而401090.plt节。
hello是如何进行重定位的:
①首先计算需要被重定位的位置
refptr = .text + r.offset
②然后链接器计算出运行时需要重定位的位置:
refaddr = ADDR(.text) + r.offset
③然后更新该位置
*refptr = (unsigned) (ADDR(r.symbol) + r.addend-refaddr)
5.6 hello的执行流程
0x00007ffff7e16e20 <_init>
0x0000000000401090<_start>
0x0000000000401150<in __libc_csu_init>
0x0000000000401000<_init>
0x00000000004010c5<main>
0x0000000000401030<puts>
0x0000000000401070<exit>
5.7 Hello的动态链接分析
分析hello程序的动态链接项目,通过edb调试,分析在dl_init前后,这些项目的内容变化。要截图标识说明。
动态链接的基本思想是把程序按照模块拆分成各个相对独立部分,在程序运行时才将它们链接在一起形成一个完整的程序,而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。
对于动态共享链接库中PIC函数,编译器没有办法预测函数的运行时地址,所以需要为其添加重定位记录,并等待动态链接器处理。为避免运行时修改调用模块的代码段,链接器采用延迟绑定的策略。动态链接器使用过程链接表PLT和全局偏移量表GOT实现函数的动态链接。其中GOT 中存放函数目标地址,PLT使用 GO T中地址跳转到目标函数。
dl_init函数调用前后GOT信息变化截图,经动态链接,GOT条目已经改变:
5.8 本章小结
本章介绍了链接的概念及作用,对hello的elf格式进行了详细的分析,介绍了hello的虚拟地址,分析了hello的重定位过程、执行流程、动态链接过程,详细阐述了hello.o链接成为一个可执行目标文件的过程
第6章 hello进程管理
6.1 进程的概念与作用
概念:进程是一个执行中程序的实例。是系统进行资源分配和调度的基本单位,是操作系统结构的基础。
作用:进程的概念为我们提供这样一种假象,就好像我们的程序是系统中当前运行的唯一程序一样,我们的程序好像是独占地使用处理器和内存,处理器好像是无间断地一条接一条地执行我们程序中的指令,我们程序中的代码和数据好像是系统内存中唯一的对象。
6.2 简述壳Shell-bash的作用与处理流程
Shell俗称壳,是指"为使用者提供操作界面"的软件。同时它又是一种程序设计语言。作为命令语言,它交互式解释和执行用户输入的命令或者自动地解释和执行预先设定好的一连串的命令。它作为用户操作系统与调用其他软件的工具。
处理流程:
(1)从终端读入输入的命令。
(2)将输入字符串切分,分析输入内容,解析命令和参数。
(3)如果命令为内置命令则立即执行,如果不是内置命令则创建新的进程调用相应的程序执行。
(4)在程序执行期间始终接受键盘输入信号,并对输入信号做相应处理
6.3 Hello的fork进程创建过程
在终端输入命令./hello运行hello程序,由于hello不是一个内置命令,故解析后执行当前目录下的可执行目标文件hello,shell作为父进程通过fork函数为hello创建一个新的进程作为子进程。通过fork函数,子进程得到与父进程用户级虚拟地址空间相同但独立的一份副本,包括代码和数据段、堆、共享库、用户栈。hello进程还获得与父进程任何打开文件描述符相同的副本,这就意味着当父进程调用fork时,子进程还可以读写父进程中打开的任何文件。父进程和新创建的子进程之间最大的区别在于它们有不同的PID。
6.4 Hello的execve过程
子进程创建后,shell调用execve函数加载并运行可执行目标文件hello,且带参数列表argv和环境变量列表envp。之后当出现错误时,例如找不到hello,execve才会返回到调用程序。
在execve加载了hello后,它调用启动代码,启动代码设置栈,并将控制转移给新程序的主函数main,此时用户栈已经包含了命令行参数和环境变量,进入main函数后开始逐步运行程序。
6.5 Hello的进程执行
1.逻辑控制流:
一系列程序计数器 PC 的值的序列叫做逻辑控制流。由于进程是轮流使用处理器的,同一个处理器每个进程执行它的流的一部分后被抢占,然后轮到其他进程。
2.用户模式和内核模式:
处理器使用一个寄存器提供两种模式的区分。用户模式的进程不允许执行特殊指令,不允许直接引用地址空间中内核区的代码和数据;内核模式进程可以执行指令集中的任何命令,并且可以访问系统中的任何内存位置。
3.上下文:
上下文就是内核重新启动一个被抢占的进程所需要恢复的原来的状态,由寄存器、程序计数器、用户栈、内核栈和内核数据结构等对象的值构成。初始时,控制流再hello内,处于用户模式。调用系统函数sleep后,进入内核态,此时间片停止。2s后,发送中断信号,转回用户模式,继续执行指令。
4.调度的过程:
在进程执行的某些时刻,内核可以决定抢占当前进程,并重新开始一个先前被抢占了的进程,这种决策就叫做调度,是由内核中称为调度器的代码处理的。当内核选择一个新的进程运行,我们说内核调度了这个进程。在内核调度了一个新的进程运行了之后,它就抢占了当前进程,并使用上下文切换机制来将控制转移到新的进程。
以执行sleep函数为例,sleep函数请求调用休眠进程,sleep将内核抢占,进入倒计时,当倒计时结束后,hello程序重新抢占内核,继续执行。
5.用户模式与内核模式转换:
为了能让处理器安全运行,不至于损坏操作系统,必然需要先知应用程序可执行指令所能访问的地址空间范围。因此,就存在了用户态与核心态的划分,核心态拥有最高的访问权限,处理器以一个寄存器当做模式位来描述当前进程的特权。进程只有故障、中断或陷入系统调用时才会得到内核访问权限,其他情况下始终处于用户权限之中,保证了系统的安全性。
6.6 hello的异常与信号处理
hello执行过程中会出现哪几类异常,会产生哪些信号,又怎么处理的。
按下Ctrl+Z:进程收到 SIGSTP 信号, hello 进程挂起。用ps查看其进程PID,可以发现hello的PID是6649;再用jobs查看此时hello的后台 job号是1,调用 fg 1将其调回前台。
Ctrl+C:进程收到 SIGINT 信号,结束 hello。在ps中查询不到其PID,在job中也没有显示,hello已经被彻底结束。
中途乱按:将屏幕的输入缓存到缓冲区,乱码被认为是命令。
Kill命令:挂起的进程被终止,在ps中无法查到到其PID。
6.7本章小结
本章简述了进程、shell的概念与作用,分析了hello程序使用fork创建子进程的过程以及使用execve加载并运行用户程序的过程,运用上下文切换、用户模式、内核模式、内核调度等知识,分析了hello进程的执行过程,最后分析了hello对于异常以及信号的处理并进行了实际操作
第7章 hello的存储管理
7.1 hello的存储器地址空间
1.物理地址(physical address)
用于内存芯片级的单元寻址,与处理器和CPU连接的地址总线相对应。
2.逻辑地址(logical address)
逻辑地址指的是机器语言指令中,用来指定一个操作数或者是一条指令的地址。如Hello中sleepsecs这个操作数的地址。
3.线性地址(linear address)或也叫虚拟地址(virtual address)
跟逻辑地址类似,它也是一个不真实的地址,如果逻辑地址是对应的硬件平台段式管理转换前地址的话,那么线性地址则对应了硬件页式内存的转换前地址。
7.2 Intel逻辑地址到线性地址的变换-段式管理
段式内存管理方式就是直接将逻辑地址转换成物理地址,也就是CPU不支持分页机制。其地址的基本组成方式是段号+段内偏移地址。
在x86保护模式下,段的信息(段基线性地址、长度、权限等)即段描述符占8个字节,段信息无法直接存放在段寄存器中(段寄存器只有2字节)。Intel的设计是段描述符集中存放在GDT或LDT中,而段寄存器存放的是段描述符在GDT或LDT内的索引值(index)。
首先给定一个完整的逻辑地址[段选择符:段内偏移地址],
1.看段选择描述符中的T1字段是0还是1,可以知道当前要转换的是GDT中的段,还是LDT中的段,再根据指定的相应的寄存器,得到其地址和大小,我们就有了一个数组了。
2.拿出段选择符中的前13位,可以在这个数组中查找到对应的段描述符,这样就有了Base,即基地址就知道了。
3.把基地址Base+Offset,就是要转换的下一个阶段的地址。
7.3 Hello的线性地址到物理地址的变换-页式管理
1.基本原理
将程序的逻辑地址空间划分为固定大小的页(page),而物理内存划分为同样大小的页框(page frame)。程序加载时,可将任意一页放入内存中任意一个页框,这些页框不必连续,从而实现了离散分配。该方法需要CPU的硬件支持,来实现逻辑地址和物理地址之间的映射。在页式存储管理方式中地址结构由两部构成,前一部分是虚拟页号(VPN),后一部分为虚拟页偏移量(VPO):
页式管理方式的优点是:
1)没有外碎片
2)一个程序不必连续存放。
3)便于改变程序占用空间的大小(主要指随着程序运行,动态生成的数据增多, 所要求的地址空间相应增长)。
缺点是:要求程序全部装入内存,没有足够的内存,程序就不能执行。
2.页式管理的数据结构
在页式系统中进程建立时,操作系统为进程中所有的页分配页框。当进程撤销时收回所有分配给它的页框。在程序的运行期间,如果允许进程动态地申请空间,操作系统还要为进程申请的空间分配物理页框。操作系统为了完成这些功能,必须记录系统内存中实际的页框使用情况。操作系统还要在进程切换时,正确地切换两个不同的进程地址空间到物理内存空间的映射。这就要求操作系统要记录每个进程页表的相关信息。为了完成上述的功能,—个页式系统中,一般要采用如下的数据结构。
页表:页表将虚拟内存映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时,都会读取页表。页表是一个页表条目(PTE)的数组。虚拟地址空间的每个页在页表中一个固定偏移量处都有一个PTE。假设每个PTE是由一个有效位和一个n位地址字段组成的。有效位表明了该虚拟页当前是否被缓存在DRAM中。如果设置了有效位,那么地址字段就表示DRAM中相应的物理页的起始位置,这个物理页中缓存了该虚拟页。如果没有设置有效位,那么一个空地址表示这个虚拟页还未被分配。否则,这个地址就指向该虚拟页在磁盘上的起始位置。
3.页式管理地址变换
MMU利用VPN来选择适当的PTE,将列表条目中PPN和虚拟地址中的VPO串联起来,就得到相应的物理地址。
7.4 TLB与四级页表支持下的VA到PA的变换
n位的虚拟地址包含两个部分:一个p位的虚拟页面偏移(VPO),一个n-p位的虚拟页号(VPN),MMU利用VPN选择适当的PTE,例如VPN 0选择PTE 0。根据PTE,我们知道虚拟页的信息,如果虚拟页是已缓存的,那直接将页表条目的物理页号和虚拟地址的VPO串联起来就得到一个相应的物理地址。这里的VPO和PPO是相同的。如果虚拟页是未缓存的,会触发一个缺页故障。调用一个缺页处理子程序将磁盘的虚拟页重新加载到内存中,然后再执行这个导致缺页的指令。
7.5 三级Cache支持下的物理内存访问
Cashe的物理访存大致过程如下:
1.组选择取出虚拟地址的组索引位,将二进制组索引转化为一个无符号整数,找到相应的组
2.行匹配把虚拟地址的标记为拿去和相应的组中所有行的标记位进行比较,当虚拟地址的标记位和高速缓存行的标记位匹配时,而且高速缓存行的有效位是1,则高速缓存命中。
3.字选择一旦高速缓存命中,我们就知道我们要找的字节在这个块的某个地方。因此块偏移位提供了第一个字节的偏移。把这个字节的内容取出返回给CPU
4.不命中如果高速缓存不命中,那么需要从存储层次结构中的下一层取出被请求的块,然后将新的块存储在组索引位所指示的组中的一个高速缓存行中。一种简单的 放置策略如下:如果映射到的组内有空闲块,则直接放置,否则组内都是有效块,产生冲突(evict),则采用最近最少使用策略 LFU 进行替换。
7.6 hello进程fork时的内存映射
当fork函数被当前进程调用时,内核为新进程创建各种数据结构,并分配给它一个唯一的PID,同时为这个新进程创建虚拟内存。它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记位只读,并将两个进程中的每个区域结构都标记为私有的写时复制。当fork在新进程中返回时,新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时,写时复制机制就会创建新页面。因此,也就为每个进程保持了私有空间地址的抽象概念。
7.7 hello进程execve时的内存映射
execve 函数调用驻留在内核区域的启动加载器代码,在当前进程中加载并运 行包含在可执行目标文件 hello 中的程序,加载并运行 hello 需要以下几个步骤:
1.删除已存在的用户区域,删除当前进程虚拟地址的用户部分中的已存 在的区域结构。
2.映射私有区域,为新程序的代码、数据、bss 和栈区域创建新的区域结 构,所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为 hello 文件中的.text 和.data 区,bss 区域是请求二进制零的,映射到匿名 文件,其大小包含在 hello 中,栈和堆地址也是请求二进制零的,初始长 度为零。
3.映射共享区域, hello 程序与共享对象 libc.so 链接,libc.so 是动态链 接到这个程序中的,然后再映射到用户虚拟地址空间中的共享区域内。
4.设置程序计数器(PC),execve 做的最后一件事情就是设置当前进程 上下文的程序计数器,使之指向代码区域的入口点。
7.8 缺页故障与缺页中断处理
页面命中完全是由硬件完成的,而处理缺页是由硬件和操作系统内核协作完成的。
处理流程:
- 处理器生成一个虚拟地址,并将它传送给MMU
- MMU生成PTE地址,并从高速缓存/主存请求得到它
- 高速缓存/主存向MMU返回PTE
- PTE中的有效位是0,所以MMU出发了一次异常,传递CPU中的控制到操作系统内核中的缺页异常处理程序。
- 缺页处理程序确认出物理内存中的牺牲页,如果这个页已经被修改了,则把它换到磁盘。
- 缺页处理程序页面调入新的页面,并更新内存中的PTE
- 缺页处理程序返回到原来的进程,再次执行导致缺页的命令。CPU将引起缺页的虚拟地址重新发送给MMU。因为虚拟页面已经换存在物理内存中,所以就会命中。
7.9动态存储分配管理
带边界标记的隐式空闲链表的每个块是由一个字的头部、有效载荷、可能的额外填充以及一个字的尾部组成的。
在隐式空闲链表中,因为空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中所有的块,从而间接地遍历整个空闲块的集合。其中,一个设置了已分配的位而大小为零的终止头部将作为特殊标记的结束块。
当一个应用请求一个k字节的块时,分配器搜索空闲链表,查找一个足够大的可以放置所请求块的空闲块。分配器有三种放置策略:首次适配、下一次适配合最佳适配。分配完后可以分割空闲块减少内部碎片。同时分配器在面对释放一个已分配块时,可以合并空闲块,其中便利用隐式空闲链表的边界标记来进行合并。
显示空闲链表:
显式空闲链表是将空闲块组织为某种形式的显式数据结构。因为根据定义,程序不需要一个空闲块的主体,所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。如,堆可以组织成一个双向链表,在每个空闲块中,都包含一个前驱与一个后继指针。
在显式空闲链表中。可以采用后进先出的顺序维护链表,将最新释放的块放置在链表的开始处,也可以采用按照地址顺序来维护链表,其中链表中每个块的地址都小于它的后继地址,在这种情况下,释放一个块需要线性时间的搜索来定位合适的前驱。
7.10本章小结
本章主要介绍了hello存储器的地址空间;虚拟地址到物理地址的转换;cache的物理内存访问;进程 fork、execve 时的内存映射、缺页故障与缺页中断处理;动态存储分配管理。
第8章 hello的IO管理
8.1 Linux的IO设备管理方法
一个Linux文件就是一个m字节的序列。所有的IO设备都被模型化为文件,所有的输入输出都被当做对相应文件的读和写来执行。这允许Linux内核引出一个简单、低级的应用结构,使得所有的输入输出能够以一种统一且一致的方式来执行。
设备的模型化:文件
设备管理:unix io接口
8.2 简述Unix IO接口及其函数
8.2.1 接口
打开文件:通过内核代开文件,内核返回非负整数,成为描述符。描述符表示这个文件。内核记录有关文件的所有信息。
文件位置。每个打开的文件,内核保持一个文件位置k,表示从文件开头起始的字节偏移量。
读写文件。进行复制操作并改变文件位置k的值。
关闭文件。内核释放相应数据结构,将描述符恢复到可用的描述符池中。
8.2.2 函数
int open(char *filename, int flags, mode_t mode)
将filename转换为文件描述符,返回描述符数字,总返回进程中没有打开的最小描述符。
int close(fd)
关闭一个打开的文件。
ssize_t read(int fd, void *buf, size_t n);
从fd复制至多n个字节到buf
ssize_t write(int fd, const void *buf, size_t n);
从buf复制至多n个字节到fd
8.3 printf的实现分析
观察printf的源码:
int printf(const char *fmt, ...)
{
int i;
char buf[256];
va_list arg = (va_list)((char*)(&fmt) + 4);
i = vsprintf(buf, fmt, arg);
write(buf, i);
return i;
}
其中vsprintf(buf, fmt, arg)函数能够返回我们想要打印的字符串的长度并对我们的格式化字符串进行解析。当获取到字符串的长度后,我们便能够将字符串打印出来。
从vsprintf生成显示信息,到write系统函数,到陷阱-系统调用 int 0x80或syscall等.
字符显示驱动子程序:从ASCII到字模库到显示vram(存储每一个点的RGB颜色信息)。
显示芯片按照刷新频率逐行读取vram,并通过信号线向液晶显示器传输每一个点(RGB分量)。
8.4 getchar的实现分析
getchar能够读取stdin,然后获取输入的字符。
异步异常-键盘中断的处理:键盘中断处理子程序。接受按键扫描码转成ascii码,保存到系统的键盘缓冲区。
getchar等调用read系统函数,通过系统调用读取按键ascii码,直到接受到回车键才返回
8.5本章小结
本章简述了Linux的IO设备管理方法以及UNIX IO接口及其函数,简单解释了printf以及getchar函数实现的基本原理。
结论
hello 程序终于完成了它“艰辛”的一生。hello 的一生大事记如下:
1.经过预处理器 cpp 的预处理,处理以#开头的行,得到 hello.i。
2.编译器 ccl 将得到的 hello.i 编译成汇编文件 hello.s。
3.汇编器 as 又将 hello.s 翻译成机器语言指令得到可重定位目标文件 hello.o
4. 链接器 ld 将 hello.o 与动态链接库链接生成可执行目标文件 hello,至 此,hello 自己已经脱胎换骨成了一个可以运行的程序。然而它的运行还要靠操作系统提供帮助。
5. 在 shell 中输入./hello 2021112810 肖芩芩 2000,shell 为 hello fork 一个子进程,并在子进程中调用 execve,加载运行 hello。
6. CPU 为 hello 分配内存空间,hello 从磁盘被加载到内存。
7. 当 CPU 访问 hello 时,请求一个虚拟地址,MMU 把虚拟地址转换成物理地址并通过三级 cache 访存。
8. hello 运行过程中可能遇到各种信号,shell 为其提供了各种信号处理程序。
9. Unix I/O 帮助 hello 实现了输出到屏幕和从键盘输入的功能。
10. 最后 hello 执行 return 0;结束了自己的一生。
我的感想:
计算机系统真的是一个庞大而又精细的组织,即使是一个简单的 hello.c也需要操作系统提供如此多的支持,并且每一步都经过了设计者的深思熟虑,在有限的 硬件水平下把程序的时间和空间性能都做到了近乎完美,比如存储器的层次结构,比如虚拟内存的多级页表和 TLB……
附件
文件名称 |
文件作用 |
hello.i |
预处理之后文本文件 |
hello.s |
编译之后的汇编文件 |
hello.o |
汇编之后的可重定位目标执行 |
hello |
链接之后的可执行目标文件 |
helloo_objdmp |
Hello.o 的反汇编代码 |
helloo.elf |
Hello.o 的 ELF 格式 |
hello_objdmp |
Hello 的反汇编代码 |
hello.elf |
Hellode ELF 格式 |
参考文献
[1] 兰德尔·E·布莱恩特,大卫·R·奥哈拉伦著;深入理解计算机系统[M].北京:机械工业出版社,2016.7.
[2] C library – C++ Reference: [http://www.cplusplus.com/reference].
[3] printf函数实现的深入剖析 :[http://www.cnblogs.com/pianist/p/3315801.html].
[4] ELF 构造:https://www.cs.stevens.edu/~jschauma/631/elf.html
[5] argc argv:argc argv_百度百科
[6] printf 函数实现的深入剖析:https://www.cnblogs.com/pianist/p/3315801.html