open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  1. Stanford-CS107

编译的链接过程

第十三课

Previous编译的预处理过程Next函数的活动记录续、并发

Last updated 6 years ago

本节用多个例子来介绍链接过程:

例1

// mem.c
#include <stdlib.h>    // (1)
#include <stdio.h>     // (2)
#include <assert.h>    // (3)

int main() {
    void *mem = malloc(400);
    assert(mem != NULL);
    printf("Yay! \n");
    free(mem);
    return 0;
}

以上 mem.c 文件经过预处理、编译阶段后,会生成 mem.o 文件,这时候所有用户自定的常数、宏被预处理器替换,用户编写的代码被编译成机器码,但还缺少标准库的实现,即 stdio.h, stdlib.h 中定义的函数实现。这时候就需要链接过程来完成标准库 .o 文件与 mem.o 文件的打包工作,如下图所示:

执行以下命令即可编译 mem.c

$ gcc mem.c

接下来我们通过分别注释掉 mem.c 前三个 #include 语句来窥探编译的链接过程。

注释 #include <stdio.h>

我们发现 mem.c 编译成功,原因在于 gcc 会自动猜测 printf 的参数类型和返回值类型。如上面的代码中,main 函数调用 printf 并传入参数 "Yay! \n",因此 gcc 猜测 printf 的参数为 char* 类型,返回值为 int 型 (默认),而经过链接阶段,printf 函数有了相应的实现代码,并且类型符合,因此整个编译过程没有出现问题。

值得一提的是,头文件 *.h 对于编译器来说仅仅提供验证函数、结构体等个体在使用过程中的合法性,与最终的实现毫无关系,最终的实现取决于链接过程中打包进来的具体实现,而每个编译器的工具箱中都有标准库实现,因此上述编译过程能够顺利完成。

注释 #include <stdlib.h>

与上一例同理,mem.c 可以编译成功。不同的是,malloc 的函数原型返回值是指针,而这里在编译的过程中默认返回值是整数,这时候同样会出现警告 (由于原课程是在 08 年发布的,因此 gcc 的输出可能不一样,我们这里以理解编译的链接过程为目的),但依然可以编译通过,因为在链接过程中,打包进来的标准库函数 malloc, free 的实现与代码中的使用方式是相符的,它们与编译器的猜测不符,但最终代码仍然可以编译成功。

注释 #include <assert.h>

在上一课,我们提到 assert 并不是函数,而是宏,它在预处理阶段将被对应的文本替换,如果我们将 assert.h 注释,assert 不会被替换成对应的宏;编译过程虽然会提出警告,但仍然可以进入下一步;最终的链接过程,连接器找不到 assert 对应的实现,因此抛错拒绝编译通过。

函数原型声明

实际上,函数原型 (prototype) 是函数的调用者 (caller) 与执行者 (callee) 之间的协议,函数的调用者在正式调用函数前,会把参数放在函数栈相应的位置;函数的执行者会默认函数的调用者已经把规定好的参数放在相应的位置来执行函数体。

例2

// int strlen(char *s, int len);

int main() {
    int num = 65;
    int length = strlen((char *) &num, num);
    printf("length = %d\n", length);
    return 0;
}

编译过程中,当编译器遇到 strlen 时,自动猜测 strlen 的类型为 int strlen(char *, int),只会发出警告,编译可以顺利通过 (注:在新的 clang 和 gcc 上,编译会抛错,但如果 uncomment 第一行的 strlen 原型声明,则编译通过)。编译器中的标准库实现 (.o 文件) ,因为本身已经是汇编语言,操作对象都是无类型的内存块,因此在这个阶段它们无法判断调用者传进来的参数是否符合要求,只能完全信任它。这时候,函数栈的部分示意图如下所示:

从图中可以看出,虽然调用者放了两个参数在内存中,但是函数执行者 strlen 实际只用一个 char* 参数,因此它的实际使用范围在虚线一下。在 little-endian 机器中,代码执行后会打印 1;在 big-endian 机器中,代码执行后会打印 0。

例3

// memcmp 实际的函数原型
// int memcmp(void *v1, void *v2, int size);

int memcmp(void *v1);

int main() {
    int n = 17;
    int m = memcmp(&n);
}

代码中的 memcmp 原型声明虽然和实现不一致,但这不影响编译的顺利进行,但运行时,memcmp 的 caller --- main 函数只为 memcmp 准备了一个参数,也就是 &n,而 memcmp 本身的实现却需要三个参数,因此它会认为 saved pc 往上 12 字节都是自己的参数,这时候运行就可能出现严重的问题。具体的函数栈如下图所示:

例4

进入例4之前,先了解两种代码崩溃时抛出的错误

Segmentation Fault

运行时,在内存中有 4 个 segments, data segment、stack segment、heap segment and code segment。这些 segments 在内存中都被分配到某一段内存地址范围,当你的代码尝试 dereference 一个不属于这 4 个 segments 的地址时,就会出现 segmentation fault。比如 *(NULL)。

Bus Error

运行时,为了简单硬件会将 short、int 等数值类型永远放在指定地址 (2 或 4 的倍数),一旦它发现代码中存在从非指定地址去读取这些数值类型,就会抛出 Bus Error。

接下来看例子

int main() {
    int i;
    int array[4];
    for (i=0; i<=4; i++) {
        array[i] = 0;
    }
    return 0;
}

可以看出代码中的 for 循环多了一次,而这多了的一次可以造成程序陷入死循环 (在 clang-8000.0.42.1 上没有重现 ),具体内存模型如下图所示:

另外两个例子与此类似,这里只给出相关代码段

// 可能造成死循环也可能不,看系统的 endian
int main() {
    int i;
    short array[4];
    for (i=0; i<=4; i++) {
        array[i] = 0;
    }
    return 0;
}
// 造成死循环,修改了 saved pc
int main() {
    int array[4];
    int i;
    for (i=0; i<=4; i++) {
        array[i] -= 4;
    }
    return 0;
}

参考

Stanford CS107: lecture 12