2013/11.html

<head>
<meta http-equiv=Content-Type content="text/html; charset=utf-8">
</head>

<div>■ 4. CSAPP：第7章第0节：<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 链接（linking）：将不同部分的代码和数据组合和成为一个单一文件的过程，这个文件可以被加载到存储器并被执行。linking可以发生在compile time、load time、run time<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ linking使得分离编译（separate compilation）成为可能。于是，大型程序可以被拆分成小文件，从而独立的修改和编译，最终只需要再linking<br>■ 4. CSAPP：第7章第1节：编译器驱动程序<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 大多数编译系统提供一个编译器驱动程序（compiler dirver，如gcc），它根据需要调用预处理器（cpp）、编译器（cc1）、汇编器（as）、链接器（ld）为用户服务<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ cpp将c源码翻译成*.i的中间文件；cc1将*.i翻译成汇编语言文件*.s；as将汇编代码翻译成可重定位目标文件(relocatable object file)；ld最后linking各文件得到可执行目标文件（executable object file）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 最后在shell上输入a.out的时候，加载器（loader）拷贝elf中的代码和数据到存储器，并将控制交给开始函数<br>■ 4. CSAPP：第7章第2节：静态链接<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ ld是一个静态链接器（static linker），它将输入的一票可重定位目标文件链接为一个可加载和运行的可执行目标文件<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ linker主要干两件事：符号解析（symbol resolution）、重定位（relocation）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ symbol resolution：将每个符号引用和一个符号定义联系起来<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ relocation：relocatable object file中的section都是从地址0开始的，linker将每个符号定义和一个存储位置联系起来，再修改每个符号引用<br>■ 4. CSAPP：第7章第3节：目标文件<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 目标文件有三种：可重定位目标文件，可在编译时被linking得到一个可执行目标文件，如*.o和*.a（静态库，*.o的包）；可执行目标文件，可以被加载和运行，如*.exe；共享目标文件，可以在加载/运行时，被动态的加载和链接，如*.dll、*.so、*.dynlib<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 各个系统的目标文件格式不同：（1）第一个从贝尔实验室诞生的unix使用a.out格式（2）system v unix的早期版本使用coff（common object file format）（3）windows使用pe（portable executable）（4）现代unix系统，如linux、各种bsd unix、sun solaris，都是用unix elf（executable linkable format）<br>■ 4. CSAPP：第7章第4节：可重定位目标文件<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ elf文件头：描述了字长、字节顺序、机器类型（isa，如ia32）、目标文件类型（relocatable、executrable、dynamic linking）、seciton表（每个entry由offset、size构成）的尺寸/位置<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 常见section简介：<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .text：已编译的机器码<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .rodata：只读数据，如string literal和jmp table<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .data：已初始化的全局变量。注意，如果一个全局指针由其他全局变量地址或外部函数指针初始化，这个.data段内容需要被relocate<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .bss：未初始化的全局变量，在目标文件中不占空间，直到被加载进存储器。沿自ibm的block storage start的首字母（仅仅是惯例，而非语义），可以用better save space助记<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .symtab：符号表。记录各种函数和全局变量、静态局部变量（当然static的symbol有private标记）。*.o文件都有，哪怕没有指定-g。和编译器中的符号表概念不同，这里的symbol不包含局部变量<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .debug：调试符号表，包含局部变量及其类型，有些entry是全局变理和c源文件。-g生成<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .line：.text中的机器码和行号之间的映射。-g生成<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .strtab：为.symtab、.debug提供字符串池<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .rel.text：.text段中的需要relocate的引用。包括对全局变量的引用，调用其他模块的函数（调用本模块函数时，ia32可以用pc relative的call）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .rel.data：.data中需要被relocate的内容。比如初始值为另一个全局变量地址或函数指针的global variable<br>■ 4. CSAPP：第7章第5节：符号和符号表<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 符号表包含三种symbol：（1）能被其他模块引用的全局符号（2）只能被本模块引用的本地符号（3）引用其他模块的external symbol<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ .symtab中的一个entry大概有以下内容：name，.strtab中的offset，表示symbol name；value，section中的offset；size，尺寸；type，可以使data、func、section或者source file name；binding，local或者global；section，特定的section，或者是undef（表external）、abs、common等特殊段<br>■ 4. CSAPP：第7章第6节：符号解析<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ c++和java中的函数重载，其实是进行了mangling和demangling<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ symbol resolution：由linker将一个符号引用和输入relocatable object file中的符号定义联系起来<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 引用解析时，如果能在当前模块找到一个本地符号（static symbol），则直接完成解析<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 在非static全局符号中，全局函数和已初始化全局变量是strong symbol，而未初始化全局变量是weak symbol。linking的时候，strong symbol最多只允许一个，而weak symbol个数不限；如果存在强符号，则选择强符号，否则随机选择一个弱符号<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 如果标准函数由编译器直接定位，则，升级标准函数需要同时发布新版编译器，不可取；如果将标准函数打包成一个大的.o文件，则所有库函数总是被linking，很浪费；于是，static library诞生了，它由ar工具打包*.o文件而成，linking的时候，总是只链接需要的*.o文件，来提供linking过程中未解析的符号定义<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ libc.a其实是由一堆*.o打包而成，每个.o文件实现一个函数，比如printf、scanf，这样，链接的时候以函数为最小单位；类似的libm.a提供了数学标准库函数，也以函数为单位<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ static linking过程：总是链接每个.o文件，但遇到静态库.a，只链接其中需要的.o文件，因此可能什么都不链接；所谓需要，是指，linker从左到右依次分析目标文件中的每个引用，如果遇到.a文件，此时未定位集合U中存在能在.a中的.o中定位的符号，则链接该.o，重复该过程直到最后。<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 静态库的推荐命令行链接顺序：（1）尽量将.a文件放在项目.o文件列表之后链接，即先提出引用，再给出定义（2）对于环形引用，同一个.a文件可能需要多次出现在shell上，其中每次出现被linking的目标文件不同<br>■ 4. CSAPP：第7章第7节：重定位<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 一旦完成了symbol resolution，linker就确定了每个section的大小、位置（确定了.a中的哪些.o需要被linking），于是可以开始relocation。分为两步：（1）合并section，fixup对应的symbol entry（2）relocate在.rel.data和.rel.text中出现的每个符号引用<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ elf有11中不同的引用类型，常见的：（1）pc relative的引用，relocate的时候，将其值增加一个(ADDR(ref.symbol) - ADDR(section))（2）absolute引用，直接修改其值<br>■ 5. CSAPP：第7章第8节：可执行目标文件<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ executable object file的头文件和relocatable目标文件头相类似，除了还包含入口函数的地址<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 可执行目标文件：没有了.rel.xxx段；文件头后面紧跟代码段，包括.init（一段额外的初始化代码）、.text、.rodata；再后面是数据段，包括.data、.bss；最后是.symtab、.debug、.line、strtab，但是这些段只会在目标文件中，不会被加载到存储器<br>■ 5. CSAPP：第7章第9节：加载可执行目标文件<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ linux进程的存储器映像（从低地址到高地址）：只读段（.init、.text、.rodata）、读写段（.data、.bss）、运行时堆、动态库、栈、内核区（往往是0xc000000以上）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ linux创建进程时，并不会直接拷贝所有目标文件段内容到存储器，而是直到cpu引用相应段时，段页才被操作系统的页面调度机制加载到存储器<br>■ 5. CSAPP：第7章第10节：动态链接共享库<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 使用静态链接库的多个程序存在共享内容的冗余拷贝，共享库为解决这个问题而生。shared library可以在运行时被加载到任何位置，由dynamic linker来执行dynamic linking<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 共享库的“share”有两个层面的含义：（1）在目标文件层面，它被共享，从而节省了磁盘空间（2）在被加载到存储器后，它被多个进程共享（哪怕是映射到不同的虚拟地址）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 在静态链接程序时，提供共享库，从而生成包含可重定位信息的部分链接可执行目标文件（parital linked executable object file），最后在load time或run time加载时才进行dynamic linking来relocate剩余的symbol引用<br>■ 5. CSAPP：第7章第11节：从应用程序中加载和链接共享库<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 共享库可以被用于：发布软件更新包；动态生成代码并被编译和加载<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ unix系统的运行时加载共享库的接口：dlopen、dlclose、dlsym、dlerror<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ java的JNI是通过运行时加载（dlopen）共享库来访问c代码的<br>■ 5. CSAPP：第7章第12节：位置无关代码（PIC）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ ia32下，"call L1; L1: pop eax；"这个序列可以取得当前的eip，所以，这样实现pc relative的访存方法后，可以拿到模块内任意地址<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 多个进程共享动态库有两种可能的方案：（1）每个进程为特定的动态库都保留固定的空间，显然，由于各进程加载的库不同，库的版本也不同，所以不太现实；windows为每个dll生成首选地址，当加载到首选地址失败时，重新relocate该dll，当然这会造成该进程中的dll发生copy on write的拷贝，从而该dll实例不再共享（2）共享库生成PIC（position independent code，比如ia32中pc relative的call调用就是一种）的代码，从而无论被加载到任何虚拟地址都能正常使用<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ PIC的数据引用：（1）模块内的symbol引用，可以直接用pc relative的手法拿到函数指针或者全局变量地址（2）模块外的symbol引用，先通过pc relative的访存定位到GOT（global offset table）中的一个slot，其值是一个外部函数的地址或者全局变量地址。这里GOT的slot会有对应的relocate entry，该动态库被loading进来的时候GOT会被relocate，所以即使发生copy on write也只会拷贝GOT所在的page<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ PIC的函数调用：（1）调用模块内函数，ia32的call指令（包括jmp指令）支持pc relative的寻址（2）调用模块外函数，一则，可以用PIC数据引用的方式，访问GOT得到外部函数指针再调用；也可以，通过lazy binding的方式，call本地地址再间接jmp，这里的本地地址是PLT（procedure linkable table）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ lazy binding（延迟绑定）：第一次调用付出额外的开销来relocate，之后则只需要很少的指令就能调用外部函数。方法：先pc relative的call本地代码（PLT），jmp到GOT所指向的位置，最初该位置仍然是PLT代码，然后这第一次调用的PLT代码会传入索引让dynamic linker去relocate那GOT中的值到外部地址，从而第二次进行pc relative调用时，会jmp到GOT所指向的外部函数，开销很小。<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 另一种可能的lazy binding方式？：先间接寻址的方式call pc relative的GOT中的指针，最初GOT中指向PLT，会让linker去relocate GOT的值，之后再进行pc relative的间接call时会直接跳转到GOT所指向的目标函数。为不失性能，这要求isa支持间接寻址的call<br>■ 5. CSAPP：第7章第13节：处理目标文件的工具<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ ar：管理和查看静态库的内容<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ strip：从目标文件中删除符号信息<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ strings、nm、size、readelf：查看目标文件的内容。分别是“查看所有可打印字符串”、“列出object file中的.symtab中的符号”、“查看各个section的size”、“查看elf的完整内容，包括elf头，和nm、size的完整功能”<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ objdump：包括反汇编.text段等所有查看目标文件的功能<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ ldd：列出一个可执行目标文件所需要链接的所有共享库<br>■ 5. 程序员修炼之道：第6章<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 传统智慧认为，项目一旦进入编码阶段，工作主要就是机械的将设计转换为可执行语句，但这种态度正是程序丑陋、低效、结构糟糕、不可维护和完全错误的最大原因<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 编码不是机械工作，否则20世纪80年代的CASE工具早就取代了程序员。事实上，编码的每一分钟都要做出决策，如果要让程序长久、无误和富有生产力，就必须对这些决策进行仔细的思考和判断<br>■ 5. 程序员修炼之道：31. 靠巧合编程<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 电影中的士兵，常识性的刺刀试探地面有无地雷，最后当他确定安全并走过去的时候，地雷爆炸了。起初的探测没有发现地雷仅仅是侥幸，他在此之上得出的结论是灾难性的<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 作为开发者，我们也工作在雷区，每天都有成百上千的陷阱在等待我们，我们必须避开靠巧合编程（依靠运气和偶然的成功），而要深思熟虑的编程<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 不要依赖没有记入文档的库行为，因为依赖于实现而不是接口的代码可能会因为库升级而失效<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ don't program by coincidence<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 不要让已有的代码约束将来的代码，如果不适用，都应该被替换；同样，不要让已经完成的事情约束下一步要做的事情。需要的时候就重构，当然，这可能影响进度，但只要重构的影响小于放任的影响<br>■ 7. 程序员修炼之道：32. 算法效率<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ estimate the order of your algorithm（评估你算法的阶，O(x^y)中的y），test your estimate（用不同的输入测试时间、空间效率）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 如果你有一个算法是O(n^2)的，设法用分治算法将其降到O(n*log(n))<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 如果不能评估时间、内存用量，就用不同的输入测试并绘制曲线<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 或许小输入下线性，但输入一旦增大到百万，就开始退化；或许输入是随机的时候没问题，但输入一旦有序，也开始退化；可能平时算法很快，一旦内存用量达到一定数值，开始使用交换区，性能也开始退化<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 如果你的曲线不平滑，看看是否有其他用户在和你共享系统资源；看看是否有后台进程在占用系统资源；看看进程是否开始使用交换区<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 开启激进优化（aggressive optimization），可能快很多；用专用编译器，可能快很多（比如RISC上的某些制造商专用的编译器，往往比可移植的GCC快很多）<br>■ 15. 程序员修炼之道：33. 重构<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 就软件开发而言，与其用修筑建筑来比喻，还不如比作园艺，后者更接近现实，没有按照计划完成的事情需要被清除或修剪<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 重写、重做和重新架构代码合起来，称为重构<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 何时重构？（1）重复，违背DRY（2）非正交设计（3）过时的知识，在维护的过程中已经废弃（4）性能<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ Refactor early, refactor often。时间压力常常被用作不进行重构的借口，但这个借口不成立，因为维护的过程中你会耗费更多的额外时间在上面，而且，“我们会有更多的时间吗？根据我们的经验，没有”<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 需要重构的代码就像“肿瘤”，你现在手术，还可以趁他小取出来，而等它扩散，那时再切除会更昂贵、危险，最终甚至会丧命。<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 关于重构的小提示：（1）不要在重构的同时增加功能（2）在重构之前确保有良好的测试，然后经常运行他们，于是，一旦某次改动破坏了程序，可以立刻发现（3）确保你的步骤保持短小并紧接着测试，良好的回归测试是自信重构的关键<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 如果做出了剧烈改动，尽量利用静态分析等特性，让库用户尽快发现不兼容<br>■ 26. 程序员修炼之道：34. 易于测试的代码<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 软件IC（integrated circuit，集成电路），意思是软件组件应该就像集成电路芯片一样组合<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 芯片在设计时就考虑了测试，不止在工厂、在安装时，也包括部署现场的测试。软件也可以做同样的事，在一开始就把可测试性构建进软件，并且在把各个部分连接在一起之前对每个部分进行彻底的测试<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 硬件芯片级测试等价于软件中的单元测试——在隔离状态下对每个模块进行测试，目的是检验其行为。一旦我们在受控条件下对模块进行了彻底的测试，就能更好的了解模块在广阔世界中的反应<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 可以把单元测试视为针对合约的测试（contract），编写测试用例，确保给定的单元遵守合约<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 应该确保先测试依赖链上游的组件，从而避免出现downstream disaster（下游的灾难）<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ design to test。为测试而设计<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 单元测试：单元测试代码不应该被扔到源码树偏远的角落，如果不容易找到它，就不会使用它。<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 单元测试提供了两种无价资源：（1）演示模块功能的例子（2）提供回归测试、重构的基础<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 单元测试框架应该有以下特征：（1）指定设置和清理（setup、cleanup） 的标准途径（2）选择测试个别或全部方法（3）分析输出是否符合预期的手段（4）标准化的故障报告形式<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 将调试过程中的即兴print、debuger表达式给正式化，加入已有单元测试中<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ 测试窗口：log文件、热键序列激活调试控制窗口、内嵌的http服务器以提供状态<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ Test your software, or your users will<br>■ 26. 程序员修炼之道：35. 邪恶的向导<br>&nbsp; &nbsp; &nbsp; &nbsp; ■ Don't use wizard code you don't understand<br></div>