链接的通俗概念

链接就是将各种代码和数据片段收集并组合为一个单一文件的过程。

因为链接器的存在，它使得分离式编译成为可能。

静态链接

静态链接的输入通常是一组可重定位的目标文件，输出是一个完全链接、可以加载和运行的可执行目标文件。

链接的两个主要任务：

• 符号解析
• 重定位

符号解析的过程是将符号引用和定义关联的过程。这里符号解析单纯连接符号定义和符号引用，而不是编译原理中的解析语法符号。

符号可以指：函数、全局变量、静态变量

重定位是将符号定义与内存地址关联的过程，并且每个符号引用也要替换为相应的地址（重新定位符号的地址）。

可重定位目标文件

首先了解一下典型的ELF可执行可链接文件的格式，因为链接器的输入就是它。

ELF 全称 “Executable and Linkable Format”，即可执行可链接文件格式，目前常见的Linux、 Android可执行文件、共享库（.so）、目标文件（ .o）以及Core 文件（吐核）均为此格式。

典型的ELF文件由一个ELF header、若干个节以及Section Header Table（节头部表）组成。

ELF header主要是一些文件的元信息，而Section Header Table节头部表描述了不同节的大小和位置。

ELF其中重要的是若干个节，我们现在需要了解的是symtab符号表，它存放了程序中定义和引用的函数和全局变量的信息。

符号和符号表

每个ELF文件（模块m）都有一个符号表，它包含了当前文件定义和应用的符号信息，这些符号可以分为：

• 全局符号：在m中定义，能被其他模块引用的符号。

  比如非静态的C函数和全局变量。

• 外部符号：由其他模块定义，但是被m使用的符号。

  比如其他模块定义的非静态的C函数和全局变量。

• 局部符号：只被m定义和使用的符号。

  比如带static的C函数的全局变量。

需要注意到函数内部的局部变量不归符号表管辖，因为它们由运行时的栈管理。

而静态的局部变量还是会被符号表记录。

符号解析

解析的过程就是将符号引用和符号表中的定义相关联（具体怎么关联母鸡）。

局部符号的解析简单明了，全局符号和外部符号的解析比较麻烦。

在编译器生成目标文件的过程中，如果它遇到一个不再当前模块定义的符号（变量/函数名），那么它就会生成一个链接器符号条目（编译器会假设这个符号由其他模块定义，并生成了一个填空让链接器来填）。

链接器解析多重定义符号

链接器的输入是一组可重定位目标模块。每个模块定义一组符号，有些是局部的（只对定义该符号的模块可见），有些是全局的（对其他模块也可见）。

如果多个模块定义同名的全局符号，会发生什么呢？下面是 Linux编译系统采用的方法。

在编译时，编译器向汇编器输出每个全局符号，或者是强（ strong）或者是弱（weak），而汇编器把这个信息隐含地编码在可重定位目标文件的符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。 根据强弱符号的定义， Linux链接器使用下面的规则来处理多重定义的符号名

规则1：不允许有多个同名的强符号。

规则2：如果有一个强符号和多个弱符号同名，那么选择强符号。

规则3：如果有多个弱符号同名，那么从这些弱符号中任意选择一个。

一强一弱的符号会产生意想不到的错误，建议编译时带上GCC-fno-common表示来使得任何遇见多重定义的符号时，编译器能发出警告信息。

静态库

静态库概念是指将所有的目标文件打包成一个共享文件，它可以作为链接器的输入。

它的概念起源于一些标准函数的调用，用户希望能直接使用。一种方式是让编译器认出标准函数，但这么做的代价就是库函数的开发和编译器的开发耦合。另一种方式，是将所有的标准C函数都放在一个可重定位的目标模块中。但这么做有两个缺点：1、牵一发而动全身（对单个函数的改动需要重新编译整个文件）2、冗余复制（每个可执行文件将不需要的目标函数也一起链接了）。

所以，静态库的概念就是将每个标准函数单独编译为目标模块，然后再将这些目标模块再次打包成一个静态库文件。链接器链接时，只复制被程序引用的目标模块。

链接器使用静态库解析引用

在符号解析阶段，链接器会从左往右按照它们在编译器驱动程序命令行上的出现顺序来扫描文件。

在命令行中，如果定义一个符号的库出现在引用这个符号的目标文件之前，那么引用就不能被解析，链接就会失败。

链接准则：符号定义的库要放在符号引用的文件之后。

所以将静态库放在命令行最尾部。还有一方面，如果库函数互相引用，可以在命令行上重复库来满足依赖关系。

重定位

在重定位中，将合并输入模块，并为每个符号分配运行时地址。具体来说，有两个步骤：

• 重定位节和符号定义

  链接器将所有相同类型的节合并为同一类型的节。然后将运行时地址赋给每个聚合节以及符号定义。

• 重定位节中的符号引用

  在这一步中，链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址（这主要依靠重定位条目）。

重定位条目

在符号解析的过程中，在编译器生成目标文件的过程中，如果它遇到一个不再当前模块定义的符号（变量/函数名），那么它就会生成一个链接器符号条目，这里其实就是重定位条目。

重定位这块跳过

加载可执行目标文件

加载的过程其实就是搭建进程的内存映像。

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

动态链接

静态库的缺点

• 更新麻烦，需要显式的下载最新库，然后再与更新的库链接
• 内存浪费（几乎每个C程序都用标准库函数，这些代码会被复制到每个运行进程的文本段中，这会造成内存资源的极大浪费）

动态链接是怎么解决静态库缺点的

动态库的思想就是共享，而不是复制和嵌入。明白这一点需要理解虚拟内存以及内存映射。

在链接时，链接器只复制一些重定位和符号表信息，在运行时解析这些对于代码和数据的引用。

具体的工作由动态链接器执行，可执行文件包含一个.interp节，这个节包含了动态链接器的路径名。当加载程序时，这个动态链接器就会执行，它来重定位动态库的文本和数据。

这八章讲述了xv6的文件系统，这个文件系统的实现很简单，有许多可以优化的地方，但也有很多复杂的地方。从磁盘组织、缓存、日志、Inode、目录、文件名与文件描述符。其实可以简单分为三部分：

• 底层存储（磁盘组织、磁盘缓存、Inode、Directory）
• 持久层（日志事务）
• 用户层（文件名、文件描述符）

本节融合了lec14和lec15的内容，收获颇丰。

lab9以提高并行度的方式熟悉并行编程，第一个实验是多核并行，第二个实验是key级别的哈希表锁编程。

这个实验主要是熟悉多线程编程，比较容易。

第一个实验线程切换，这个只要理解xv6的线程调度就能解决，甚至代码都可以直接抄。

第二个实验哈希表加锁。关键代码量不到两行，甚至分桶加锁也是。

第三个实验同步屏障，这个还有意思一点。

第七章讲述了xv6中线程调度的机制，核心就是swtch函数以及调度器内核线程。在线程调度的基础上，讲述了线程同步的一个机制：sleep&wakeup（其实就是条件变量）。有了同步机制后，继续展开讲进程退出、资源回收等知识。fork+exec+wait 一套流程。

融合了lec11和lec13的内容，两节课的内容，收获颇丰。

第六章主要是讲并发编程，为什么要用锁、什么时候使用锁、锁范围、加锁顺序、死锁、可重入锁等知识，还介绍了xv6中自旋锁的实现。

特别要注意xv6中持有锁就不允许中断；内存屏障用于避免指令重排，这些都是锁实现的细节。

本节融合了lec13的内容，总体上属于并发编程入门，信号量、条件变量等多进程同步机制没有介绍，后续章节会涉及。

lab5是关于懒分配的实验。前言讲得很好，One of the many neat tricks an O/S can play with page table hardware is lazy allocation of user-space heap memory. LA是用户堆空间上的Trick。

Xv6 applications ask the kernel for heap memory using the sbrk() system call. 利用sbrk系统调用来增长或减少堆空间。

LA的原因，程序角度：

• some programs allocate more memory than they actually use
• some programs allocate memory well in advance of use

内核角度：

• It can take a long time for a kernel to allocate and map memory for a large request

因此更好的做法是 That is, sbrk() doesn’t allocate physical memory, but just remembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily-allocated memory, the CPU generates a page fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it

第五章主要讲述的是外部设备的中断，不同于软件中断，外部设备中断可以与CPU处理并行。

这里要特别理解外设的驱动，驱动的top部分一般是驱动提供给用户的接口服务，驱动的bottom部分则是interrupt handler。top部分和bottom部分通过buffer解藕，top部分往设备的缓冲区读写完事儿，待设备处理完成发送一个中断，bottom部分则处理中断，bottom亦能读写缓冲区。

值得注意的是：一个中断是如何产生，又如何被CPU处理的（这里会有多个CPU）；设备与CPU的并行。

这节融合了lec09的内容，通过追踪以下两个场景来分析中断过程：

• console中的提示符“$ ” 是如何显示出来的；

• 如果你在键盘输入“ls”，这些字符是怎么最终在console中显示出来的。

第四章的主题是陷阱与系统调用。关键问题：系统调用是怎么从用户态切换到内核态的？

从中断角度看，系统调用是一软中断，发生中断后由中断向量处理，其中中断向量的地址又在寄存器stvec上。

这里融合了lec06的内容 和lec08的内容，lec08讲述了page fault中断处理的妙用，核心思想都是懒分配：给你虚拟页但不实际分配物理页，等到实际要用时再分配。

第三章的主题是页表，单看页表会很抽象，但页表背后的思想是地址空间的隔离。让每个进程都有自己的地址空间，保护地址空间不受他人侵犯。同时，页表管理的“页”，页内地址连续，以页为单位，避免页表过于庞大（多级页表也是为了实现这个目标）。同时，虚拟空间到物理空间的映射，多了几分实用trick，比如内核采用直接映射、内核页表下的guard page（未映射）、内核和用户相同的映射（trampoline page，多对一映射）。

本节融合了课程lec04的内容。虚拟地址的抽象是为了程序的隔离性，理解这点后就很容易了。