《程序员的自我修养》读书笔记

一. 从源码到程序

程序最初的存在形式是源代码,也就是若干个** .c **文件,它想要变成一个可执行程序,需要以下几个步骤:

** 1. 预编译(P39): **

负责这一步工作的叫“预编译器”。它主要负责处理所有的 #define 宏定义 ;所有的预编译指令, 比如 #if#endif 等。接下来会递归处理 #include指令,用被包含的文件替换这个预编译指令。 .c文件 经过预编译,变成 .i文件。

主要处理规则:

  • 将所有的 #define删除, 并且展开所有的宏定义;
  • 处理所有条件预编译指令,比如 #if#ifdef#elif#else#endif
  • 处理#include预编译指令,将包含的文件插入到该预编译指令的位置。注意,这个过程是递归进行的,也就是说被包含的文件可能还包含其他文件。
  • 删除所有的注释 ///* */
  • 添加行号和文件名标识,比如#2 hello.c 2,以便于编译时编译器产生调试用行号信息及用于编译时产生编译错误或警告能够显示行号。
  • 保留所有的#pragma编译器指令,因为编译器需要使用它们。

** 2. 编译(p42): **

这一步由编译器负责,主要又有词法分析、语法分析、语义分析,优化和生成汇编代码五个部分。

  • ** 词法分析:** 源代码程序被输入到 ** 扫描器 ,扫描器运用一种类似于有限状态机**的算法将源代码的字符序列分割成一系列记号。 简单说就是,识别源代码中的各种括号,数字,标点等。比如有左括号 ** “(“ ** 但没有 右括号 ** “)” **, 这一步就能发现错误。 比如:

    array[index] = (index + 4 ) * (2 + 6);
    

分析器进行标记:

image-20190213022949727

  • **语法分析: **

** 语法分析器 ** 将由 ** 扫描器 ** 产生的记号进行语法分析, 从而产生 语法树, 整个分析过程采用 **上下文语法无关 **的分析手段。比如 2+6 就是一颗根节点为 +,左右叶子节点分别为 26的语法树,如果你只写2+,在这一步就会报错。

image-20190213023008988

  • **语义分析: **

语义分析器来完成,这一步主要考虑类型声明、匹配和转换,比如当一个浮点型的表达式赋值给一个整型的表达式时,其中隐含了一个浮点型到整型转换的过程,这些都属于静态语义分析。动态语义一般指在运行期出现的语义相关的问题,比如将0作为除数是一个运行期语义错误。

image-20190213023051229

  • ** 中间语言生成 :** ** 源代码优化器 ** 将整个语法树转换成中间代码,比较常见的中间代码有: 三地址码,比如 2 + 3 会写成 t1 = 2 + 3,同时也会把编译器就可以确定的表达式进行优化。

image-20190213023112261

  • ** 目标代码生成与优化: ** 代码生成器根据三地址码生成依赖于目标机器的代码,也就是汇编语言。

image-20190213023223268

目标代码优化器对目标代码进行优化:

image-20190213023210334

**.i 经过编译,得到汇编文件,后缀是.s **

** 3.汇编(P40): ** 这一步由汇编器负责,将汇编语言转换成机器 可以执行的语言(完全由01组成)。汇编文件经过汇编,变成目标文件后缀 .o

** 4.链接(P41): ** 这一步是重点。之前的步骤,都是以 .c文件为基本单位,一个.c 源文件最终被汇编,生成目标文件。这一步就是将多个目标文件链接起来,生成可执行文件。

考虑一个 .c文件中,用到了另一个 .c 文件中的变量或函数。 在编译这个文件时,我们无法再编译期确定这个变量或函数的地址。只能把所有目标文件链接起来以后,才能确定。因此链接主要负责地址重分配,符号名称绑定和重定位。

二. 软件调用层次

image-20190213023252836

**1. 应用层: ** 不管是浏览器、游戏,还是我们使用的各种开发工具,如XcodeVS,汇编器自身等,都属于这一范畴。

** 2.操作系统运行库: ** 我们在程序里调用系统API,比如文件读写,就是调用了第二层提供的相应服务。这种调用通过操作系统的API完成,它沟通了应用层和操作系统的运行库。这也就是为什么不管是在Mac还是Windows上编程,我们都可以调用 printf()fread()等函数。因为不同的操作系统的运行库提供了不同底层的实现,但对应用层提供的API总是一样的。

** 3. 操作系统内核: ** 操作系统的运行库通过系统调用(System Call)调用系统内核提供的函数。比如fread属于API,它在Linux下会调用read()这个系统调用,而在Windows下会调用ReadFile()这个系统调用。应用程序可以直接调用系统调用,但是这样一来,我们需要考虑各个操作系统下系统调用的不同,而且系统调用由于更加底层,实现起来也就更加困难。最关键的是,系统调用是通过中断来完成的,涉及到堆栈的保存与恢复,频繁的系统调用会影响性能。

** 4.硬件层: ** 程序无法直接访问这一层,只有操作系统的内核,通过硬件厂商提供的接口才能访问。

三. 虚拟地址空间

在程序运行的过程中,最重要的概念就是虚拟地址空间。所谓的虚拟地址空间,是指应用程序自己认为,自己所处的地址空间。它区别于物理地址空间。后者是真实存在的,比如电脑有一根8G的内存条,物理地址空间就是0~8Gb。CPUMMU负责把虚拟地址转换成物理地址。

引入虚拟地址的第一个好处是,程序员不再关心真实的物理内存空间是什么样的,理论上来说,程序员有几乎无限大的虚拟内存空间可用,最后只要建立虚拟地址和物理地址的对应关系即可。另一方面,操作系统屏蔽了物理内存空间的细节,进程无法访问到操作系统禁止访问的物理地址,也不能访问到别的进程的地址空间,这大大增强了程序安全性。

由虚拟地址空间引申出来的分页(Paging)技术,大大提高了内存的使用效率。要想运行一个程序,不再需要把整个程序都放入内存中执行,我们只要保证将要执行的页在内存中即可,如果不存在则导致页错误。

关于地址空间的理解非常重要,书中有很多关于内存、和地址的描述,需要我们自己分析这是虚拟地址还是物理地址。如果分析错了,理解问题会比较麻烦。

四. 链接与重定位

我们把foo函数定义在另一个文件中,然后在main.c中调用这个函数,单独编译main.c后代码如下:

……
0000000000000024    callq    0x29
0000000000000029    xorl    %ecx, %ecx
……

可以看到,本该调用foo函数的地方,我们直接调用了下一条命令,但是当main.o和foo.o链接起来后,就变成了:

0000000100000f30    pushq    %rbp
0000000100000f31    movq    %rsp, %rbp
0000000100000f34    movl    $0x7b, %eax
0000000100000f39    movl    %edi, -0x4(%rbp)
0000000100000f3c    movl    %esi, -0x8(%rbp)
0000000100000f3f    popq    %rbp
//以上为foo函数实现
……
0000000100000f74    callq    0x100000f30
0000000100000f79    xorl    %ecx, %ecx
……

这时候foo函数的位置就正确设置了。原因在于在main.c这个编译模块单独编译时,编译器无法确定foo的位置,只好临时用下一条指令的位置代替一下。

链接器在链接过程中,就是要对这样的符号进行重定位。在重定位时,main.o中有foo函数经过修饰的符号名,同样的符号名在foo.o中也有,于是两者一拍即合,就这样被链接器连在了一起。0x29这个临时的调用地址被更新成了0x100000f30。这个过程类似于拼图游戏,程序在链接时就是处理各种各样类似的问题,当所有编译模块都按照符号名完整的链接起来时,程序也就可以开始运行了。

五. 知识概要

目标文件结构 (P58) :

image-20190213023323820

程序与目标文件.png

  • ** 文件头:** 描述了整个文件的文件属性,包括文件是否可执行,是静态连接还是动态链接及入口地址(如果是可执行文件)、目标硬件、目标操作系统等信息。同时文件头还包含段表
  • ** 段表:** 一个描述文件中各个段的数组。段表描述了文件中各个段在文件中的偏移位置及段的属性等,从段表中可以得到每个段的所有信息。
  • **.text段: **一般C语言编译后的执行语句都编译成机器代码 ,保存在.text
  • **.data段: ** 已经初始化的全局变量和局部变量都保存在.data端。
  • .bss段: 未初始化的全局变量和局部静态变量一般都放在.bss端里面,.bss端只是为未初始化的全局变量和局部变量预留位置而已,它并没有内容,所以它在文件中也不占据空间。

文件头 (P70) :

image-20190213023346707

ELF的文件头定义了 ELF魔数文件机器字节长度数据存储方式版本运行平台 **、ABI版本 ELF重定位类型 硬件平台 硬件平台版本 入口地址 程序头入口和长度 段表的位置和长度 段的数量``等。

**ELF文件头结构: **

image-20190213023412198

ELF文件头结构成员含义:

image-20190213023429160

image-20190213023520143

重定位表 (P79) :

链接器在处理目标文件时,须要对目标文件中某些部位进行重定位,即代码段和数据段中那些对绝对地址的引用位置,这些重定位信息记录在ELF文件的重定位表里面。

每个须要重定位的代码段或数据段都会有一个相应的重定位表。比如.rel.text就是针对.text段的重定位表。

一个重定位表同时也是ELF的一个段,这个段的类型就是"SHT_REL类型, 它的 sh_link表示符号表的下标, 它的sh_info表示它作用于哪个段。比如.rel.text 作用于 .text"段,而.text"段的下标为1 那么rel.text.sh_info为1.

链接的接口 – 符号(P81) :

在链接中,我们将函数和变量统称为符号,函数名或变量名统称为符号名。

整个链接过程正是基于符号才能够正确完成。链接过程中很关键的一部分就是符号的管理,每一个目标文件都会有一个相应的符号表,这个表里面记录了目标文件中所用到的所有符号。每个订阅的符号都有对个对应的值,叫做符号值,对于变量和函数来说,符号值就是它们的地址。

**符号的分类 : **

image-20190213023547436

链接过程中之关系全局符号的相互 “粘合”,局部符号、段名、行号等都是次要的。

image-20190213023605875

符号修饰和函数签名(P86) :

** C++符号修饰 :** 函数签名包含一个函数的信息,包括函数名、它的参数类型、它所在的类和名称空间及其他信息。 如例子所示:

image-20190213023624434

这段代码中有6个同名函数func,只是返回类型和参数及所在的名称空间不同。在编译器和链接器处理函数符号时,它们使用某种名称修饰的方法,使得每个函数签名对应一个修饰后的名称。也就是说C++编译器编译后的目标文件中所使用的符号名是相应函数和变量修饰后的名称。

以上6个函数签名在GCC编译器下,相对应的修饰后名称如表所示:

image-20190213030420109

签名生成规则:

image-20190213030407939

由于不同的编译器采用不同的名字修饰方法,必然会导致不同编译器编译产生的目标文件无法正常相互连接,这是导致不同编译器之间不能互相操作的主要原因之一。

强弱符号与强弱引用(P92) :

对于C/C++语言来说,编译器默认函数和初始化了的全局变量为强符号,未初始化的全局变量为弱符号。

我们可以通过GCC的_attribute_((weak))来定义任何一个强符号为弱符号。

注意:强符号和弱符号都是针对定义来说的,不是针对符号的引用

比如如下程序:

extern int ext;

int weak;
int strong = 1;
_attribute_((weak)) weak2 = 2;

int main() {
    return 0;
}

这里,weakweak2 是弱符号, strongmain 是强符号,而ext 既非强符号也非弱符号,因为它只是一个外部变量的引用。

针对强弱符号的概念,链接器会按如下规则处理和选择被多次定义的全局不好:

  • ** 规则1:**不允许强符号被多次定义(即不同的目标文件不能有同名的强符号);如果有多个强符号定义,则链接器包符号重复定义错误。
  • ** 规则2:** 如果一个符号在某个目标文件中是强符号,在其他文件中都是弱符号,那么选择强符号。
  • ** 规则3:** 如果一个符号在所有目标文件中都是弱符号,那么选择其中占用空间最大的一个。

同样对于符号名的引用也分为强引用和弱引用,强引用表示如果找不到符号定义会报错,弱引用不报错,默认为0或某个特殊值。

空间与地址分配(P99) :

现在链接器空间分配的策略基本上都是采用两步链接的方法。

  • ** 第一步: 空间与地址分配 ** 扫描所有的输入目标文件,并且获得它们各个段的长度、属性和位置,并且将输入目标文件中的符号定义和符号引用收集起来,统一放到一个全局符号表。这一步,链接器将能够获得所有输入目标文件的段长度,并且将它们合并,计算并输出文件中各个端合并后的长度和位置,并建立映射关系。
  • 第二步 符号解析与重定位 使用上一步收集到的所有信息,读取输入文件中段的数据、重定位信息、并且进行符号解析与重定位、调整代码中的地址等。链接完成后,我们就得到静态库。

静态库链接(P118) :

静态库可以看做一组目标文件的集合,同一个静态库中的不同目标文件可能相互依赖,不同的静态库也可以相互依赖。

链接控制脚本(P127) :

链接控制脚本控制链接器的运行,将目标文件和库文件转换为可执行文件。链接控制脚本由链接脚本语言写成,可以人为的控制程序入口、某几个段合并、某几个段舍弃等。

动态链接

这一部分主要讨论经过链接后,可执行文件如何装载到内存。

装载的方式(P153) :

两种典型的动态装载方法:覆盖装入和页映射。覆盖装入允许互不依赖的两个模块共同享有同一块内存,在使用中互相替换。速度较慢,用时间换空间。我们常用的方案是页映射,把程序虚拟的内存空间分成多个页,由专门的页装载管理器负责管理虚拟页和物理内存中页的对应关系。

image-20190213030342728

image-20190213030329502

进程的建立(P157) :

创建一个进程,然后装载相应的可执行文件并且执行,在有虚拟存储情况下,上述过程最开始只需要三件事:

  • 创建一个独立的虚拟地址空间
  • 读取可执行文件头,并且建立虚拟空间与可执行文件的映射关系
  • CPU的指令寄存器设置成可执行文件的入口地址,启动运行。

Linux下,目标文件的每个段都有自己在虚拟内存中的位置,这叫做虚拟内存区域(VMA),表示它装载在虚拟内存中的位置。

页错误(P159) :

进程创建后,只有物理页与虚拟页的对应关系,但是真正的指令和数据还没有放入物理页中,物理页的内存处于未分配状态。一旦访问到这个物理页,就会发生页错误。

发生页错误时,操作系统立刻根据物理内存的页与虚拟内存的页的对应关系,找到这个页对应的虚拟内存,然后再查询每个段的VMA,就可以找这个页面在可执行文件中的偏移量。这时候操作系统先为物理页分配内存空间,然后把可执行文件中的数据和指令写入物理页,最后建立物理页和虚拟页联系即可。然后进程从发生页错误的地方重新执行。

image-20190213030307055

进程虚存空间分布(P160) :

ELF文件被映射时,是以系统的页长度作为单位,每个段在映射时不可能都是系统页长度的整数倍,所以多余部分也将占用一个页。因此造成大量浪费。

由于操作系统不关心可执行文件每个section的具体作用,但是关心它们的读写权限(是否可读、可写、可执行),所以往往把具有权限的Section合并成一个Segment.

比如两个段分别叫.text.init ,它们分别包含程序的可执行代码和初始化代码,并且它们的权限相同都是可读可执行,假设.text为4097字节,.init为512字节,这两个段分别映射的话要占用3个页面,但是合并就只须占用两个页面。

image-20190213030250748

进程栈初始化(P172) :

进程运行后,操作系统会初始化进程的堆栈,其中存放了环境变量和命令行参数。这些参数被传给main函数(argcargv两个参数对应参数数量和参数数组)

动态链接

动态链接(P181) :

静态链接存在空间浪费和更新困难等问题,而动态链接的基本思想是把程序按模块拆分成各个相对独立的部分,在程序运行时才将它们链接在一起形成一个完整的程序,而不是像静态连接一样把所有的程序模块都链接成一个单独的可执行文件。

在Linux系统中,ELF的动态链接文件成为动态共享对象(DSO),后缀一般为为.so;而在Windows系统中,动态链接文件被称为动态链接库,后缀一般为.dll。动态链接的过程由动态链接器完成。动态链接可以节约内存(多个进程共享内存中的某一个模块)、方便升级(静态链接的每一个模块都会影响整个可执行文件)。

装载时重定位(P188) :

由于动态共享对象会被多个程序使用,导致它在虚拟地址空间中的位置难以确定。不同模块的目标装载地址如果有相同的,那么同时导入这两个模块就会出问题。如果都不一样也不行,因为可能存在的模块太多了。没有那么多内存。所以动态共享对象需要在装载时重定位。

装载时重定位就是:在链接时,对所有绝对地址的引用不做重定位,而把这一步推迟到装载时再完成。一旦模块装在地址确定,即目标地址确定,那么系统就对程序中所有的绝对地址进行重定位。

地址无关代码(P191) :

由于装载时重定位使得指令部分无法在多个进程之间共享,目前采用的方案是地址无关代码技术。

基本相符就是把指令中那些需要被修改的部分分离出来,跟数据部分放在一起,这样指令部分就可以保持不变,而数据部分可以再每个进程都拥有一个副本。

动态对象中的地址引用分为模块内部引用和外部引用,指令引用和数据引用,两两组合成四种。对于模块内部的指令或数据引用,采用相对偏移调用的方法。

全局偏移表(P195) :

把地址相关需要重定位的部分放到数据段中,而对于其他模块的全局变量地址、模块间的调用和跳转,则通过在数据段里面建立一个指向这些变量的指针数组,即全局偏移表(GOT),来间接指向。 用.got.got.plt表来分别处理数据和函数引用。

延迟绑定(P200) :

当函数第一次被用到时才进行绑定(符号查找、重定位等),如果没用到则不进行绑定。所以程序开始执行时,模块间的函数调用都没有进行绑定,而是需要用到时才由动态链接器来负责绑定,这种做法可以加快程序的启动速度。这种方法叫做延迟绑定。

Linux维护一个PLT表来保存符号和真实地址之间的对应关系。

动态链接重定位表(P208) :

动态链接中有两个重定位表.rel.dyn.rel.plt分别对应.rel.text.rel.data。前者对数据引用(.got)进行修正,它所修正的位置位于.got以及数据段,后者对函数引用(.got.plt)进行修正,修正位置位于.got.plt

动态链接器的实现和步骤(P214) :

动态链接器本身不可以依赖于其他任何共享对象;其次是动态链接器本身所需要的全局和静态变量的重定位工作由它本身完成。对于第二个条件,动态链接器必须在启动时有一段非常精巧的代码可以完成这项艰巨的工作而同时又不可以使用到全局变量和静态变量,这种具有一定限制条件的启动代码往往被称为自举。

内存与库

动态链接器的实现和步骤(P214) :

栈(P286):

栈是遵循先入栈的数据后出栈的一个特殊容器。

i386处理器下,栈顶有esp寄存器定位,由于栈向下生长,压栈使得栈顶地址减小,出栈是的栈顶地址增大。

image-20190213030230135

活动记录(P287):

栈保存了函数调用所需要的维护信息,被称为堆栈帧(Stack Frame)或活动记录,主要包含:

  • 函数的返回地址和函数;
  • 临时变量:包括函数的非静态局部变量以及编译器自动生成的其他临时变量
  • 保存的上下文: 包括在函数调用前后需要保持不变的寄存器。

在i386中,一个函数的活动记录用edpesp这两个寄存器划定范围。esp寄存器始终指向栈的顶部,同时也就指向了当前函数的活动记录的顶部。而相对的,edp寄存器指向了函数活动记录的一个固定位置,edp寄存器又被称为帧指针。

image-20190213030212701

P294:

函数的调用方和被调用方要遵守同一个“调用惯例”。默认的cdecl惯例要求函数参数以从右到左的顺序入栈,由函数调用方负责参数的出栈。

P301:

函数返回值的获取:如果是四个字节,放在eax中。4-8字节的返回值通过eax(低位)和edx(高位)联合存储。超过8字节的返回值,把返回值在栈中存放的地址放到eax中。

堆(P306):

栈上的数据在函数返回时就会被释放,全局地、动态的申请内存的方式是利用堆。如果由操作系统管理堆,由于总是进行系统调用,性能开销比较大,所以一般由应用程序“批发”一大块内存空间,然后自己进行内存管理,具体来讲,管理着堆空间分配的往往是程序的运行库。

堆管理 (P307):

堆并不总是向上生长(如WindowsHeapCreate系列),调用malloc有可能产生系统调用(取决于进程预申请的空间是否足够),堆内存在进程结束后被操作系统回收,堆内存在虚拟地址空间中连续,在物理空间中可能不连续。

堆分配算法(P312):

堆分配三种算法:

  • 空闲链表:把堆中各个空闲的块按照链表的方式连接起来,当用户请求一块空间时,可以遍历整个列表,直到找到合适大小的块并且将它拆分,当用户释放空间时将它合并到空闲链表中。

特点:实现简单、但记录长度的字节容易被数组越界破坏

  • 位图: 将整个堆划分为大量的块,每个快的大小相同。当用户请求内存的时候,总是分配整数个块的空间给用户,第一个快我们称为已分配区域的头,其余的称为已分配区域的主体。我们可以使用一个整数数组来记录块的使用情况,由于每个块只有头、主体、空闲三种状态,因此只需两位即可标识一个块。

特点: 速度快、 稳定性好、块不需要额外信息,易于管理、分配内存的时候容易产生碎片、位图可能过大

  • 对象池: 如果每一次分配的空间大小都一样,那么就可以按照这个每次请求分配大小作为一个单位,把整个堆空间划分为大量的小块,每次请求的时候,只需要找到一个小块就可以了。

特点: 针对固定大小的分配空间

入口函数和程序初始化(P319):

程序运行步骤:

  • 操作系统在创建进程后,把控制权交到程序的入口,这个入口往往是运行库中的某个入口函数
  • 入口函数对运行库和程序运行环境进行初始化,包括堆、 I/O、线程、全局变量构造等等
  • 入口函数在完成初始化之后,调用main函数,正式开始执行程序主题部分。
  • main 函数执行完毕后,返回到入口函数,入口函数进行清理工作,包括全局变量析构、堆销毁、关闭I/O等,然后进行系统调用结束进程。