___ ___ ________ ___ __ ___ ________ ________
|\ \ |\ \|\ ___ \|\ \|\ \ |\ \ |\ __ \|\ __ \
\ \ \ \ \ \ \ \\ \ \ \ \/ /|\ \ \ \ \ \|\ \ \ \|\ /_
\ \ \ \ \ \ \ \\ \ \ \ ___ \ \ \ \ \ __ \ \ __ \
\ \ \____\ \ \ \ \\ \ \ \ \\ \ \ \ \____\ \ \ \ \ \ \|\ \
\ \_______\ \__\ \__\\ \__\ \__\\ \__\ \_______\ \__\ \__\ \_______\
\|_______|\|__|\|__| \|__|\|__| \|__|\|_______|\|__|\|__|\|_______|
每个程序员都用过链接器，但很少有人真正理解它。
在这个实验中，你将亲手实现一个链接器，揭开程序是如何被「拼接」在一起的秘密。我们设计了一个友好的目标文件格式（FLE），让你可以专注于理解链接的核心概念。
Note
本实验预计耗时 10 - 20 个小时，具体情况因个体差异可能有所区别。
链接是将多个目标文件组合成一个可执行程序的过程。在现代软件开发中，我们不会把所有代码都写在一个文件里——这样既不利于代码复用，也不便于团队协作。相反，我们会将程序分解成多个源文件，分别编译成目标文件，再通过链接器将它们「拼接」在一起。
问题在于，编译器在处理每个文件时，只能看到当前文件的内容。当代码调用另一个文件中定义的函数，或者访问另一个文件中的全局变量时，编译器并不知道那个函数或变量最终会在内存的什么位置。它只能在目标文件中留下一个"占位符"，标记这里需要一个地址，等待链接器来填充。
这就是链接器的工作。它接收多个目标文件作为输入，每个目标文件都包含一些代码和数据，以及关于符号定义和引用的信息。链接器需要把这些信息综合起来，解决所有的依赖关系，确定每个符号的最终位置，然后将正确的地址填入那些占位符中。
具体来说，链接器需要完成三项核心工作：
- 符号解析。程序中的每个函数、每个全局变量都有一个名字，这个名字就是符号。链接器需要建立一个全局的视图，知道每个符号在哪里定义，确保每个被引用的符号都能找到它的定义。当两个文件定义了同名符号时，链接器还需要按照一定的规则决定使用哪一个，或者判断这是一个错误并报告给程序员。
- 重定位。确定了符号的位置后，链接器需要回到代码中，将那些占位符替换成实际的地址。这个过程叫做重定位。不同类型的引用需要不同的处理方式——函数调用可能使用相对地址，访问全局变量可能使用绝对地址，指针赋值可能需要完整的64位地址。链接器需要理解这些差异，并正确计算和填充每个位置。
- 内存布局规划。现代程序不仅需要正确运行，还需要安全运行。链接器需要决定程序的各个部分在内存中如何排列，为代码和数据分配合适的位置，设置访问权限以防止意外或恶意的修改。代码应该是可执行但不可写的，数据应该是可读写但不可执行的，常量应该是只读的。这些约束共同构成了程序的安全边界。
在这个实验中，你将逐步实现这些功能。从最基本的符号表查看开始，到能够处理简单程序的链接器，再到支持各种重定位类型、符号决议规则、内存保护机制的完整链接器，最终深入理解现代程序是如何被组装起来的。
- 操作系统：x86-64 架构的任意 Linux 发行版（推荐 Ubuntu 22.04 或更高版本）
- Windows 用户可使用 WSL 2
- macOS 用户可使用 OrbStack 虚拟机或使用我们提供的服务器环境
- 编译器：至少支持到 C++ 17 的 g++ 或 clang
- Python 3.8+ (需安装 python3-venv 包)
- Make, Git
请使用 Git 管理你的代码，并养成经常提交的好习惯。
本实验的框架代码使用了C++的一些便利特性来简化内存管理和数据操作。如果你对C++不太熟悉，建议先阅读 C程序员的C++实用指南。这份指南会解释实验中会用到的C++特性，帮助你快速上手，无需学习整个C++语言。
如果你已经熟悉C++，可以直接跳过这一节。
# 克隆仓库（请将 your-assignment-repo-url 替换为你的仓库地址）
git clone your-assignment-repo-url
cd your-assignment-repo-name
# 构建项目
make
# 运行测试（此时应该会失败，这是正常的）
make test_1 # 运行任务一的测试
make test # 运行所有测试Tip
可选：配置C++标准版本
实验默认使用C++17标准，这已经足够完成所有任务。如果你的编译器支持更高版本的C++标准（如C++20或C++23），并且希望使用其中的新特性，可以运行：
make config这个配置工具会检测你的编译器支持哪些标准，让你选择想要使用的版本。配置完成后，记得将生成的配置文件加入版本控制：
git add cxx_compiler cxx_std
git commit -m "Configure C++ standard"使用更高版本的C++标准可以让某些代码写得更简洁（比如C++20的结构化绑定、C++23的std::print），但这完全是可选的。实验文档中涉及Modern C++特性的地方都会用提示框标注。
LinkLab-2025/
├── include/ # 头文件
│ └── fle.hpp # FLE 格式定义（请仔细阅读）
├── src/
│ ├── base/ # 基础框架（助教提供）
│ │ ├── cc.cpp # 编译器前端，生成 FLE 文件
│ │ └── exec.cpp # 程序加载器，运行生成的程序
│ │ └── ar.cpp # 归档器，生成目标文件
│ └── student/ # 你需要完成的代码
│ ├── nm.cpp # 任务一：符号表查看器
│ └── ld.cpp # 任务二~八：链接器主程序
└── tests/ # 测试用例
└── cases/ # 按任务分类的测试
├── 1-nm-test/ # 任务一：符号表显示
├── 2-single-file/ # 任务二：基础链接
└── ... # 更多测试用例
└── common/ # 测试用例的公共库
└── minilibc.c # 迷你 libc 的实现
每个任务都配有完整的测试用例，包括源代码、期望输出和配置文件。你可以阅读测试代码了解具体要求，运行测试检查实现是否正确，也可以编写新的测试用例来探索更多可能性。
在开始编写代码之前，你需要理解链接器处理的数据格式。本实验使用FLE（Friendly Linking Executable）格式——一个简化的、人类可读的目标文件格式。这个任务会介绍FLE文件的结构、表情符号标记的含义、以及文件表示与内存结构之间的对应关系。特别重要的是理解符号、重定位、节与段等核心概念。
📖 详细指导
实现nm命令的功能，显示目标文件中的符号表。这个工具需要遍历符号列表，判断每个符号的类型（全局/局部/弱符号）和位置（代码段/数据段/BSS段等），然后按照标准格式输出。
你需要实现：src/student/nm.cpp中的FLE_nm函数
测试命令：make test_1
📖 详细指导
实现一个能够处理简单场景的链接器。给定若干目标文件，将它们的节内容合并，建立全局符号表，处理绝对重定位（R_X86_64_32和R_X86_64_32S），最后生成可执行文件。这个阶段可以将所有内容放在一个内存段中，不需要考虑权限分离。
你需要实现：src/student/ld.cpp中的FLE_ld函数的基础框架
测试命令：make test_2
📖 详细指导
扩展链接器以支持PC相对寻址（R_X86_64_PC32，用于函数调用）和64位绝对寻址（R_X86_64_64，用于指针）。相对寻址的计算涉及当前位置和目标位置的偏移，需要理解x86-64指令格式的细节。
你需要实现：在任务二的基础上，增加对新重定位类型的处理
测试命令：make test_3
📖 详细指导
实现符号决议规则。当多个目标文件定义同名符号时，链接器需要判断这是否合法，以及应该使用哪个定义。规则包括：强符号必须唯一，强符号覆盖弱符号，多个弱符号可以共存。此外还需要正确处理局部符号，确保不同文件的同名局部符号不会混淆。
你需要实现：扩展符号解析逻辑，增加冲突检测和决议
测试命令：make test_4
📖 详细指导
引入多段布局，将不同性质的节分开存放。你可以选择将节按前缀合并（如所有.text*合并成.text，所有.rodata*合并成.rodata），也可以保持每个节独立。无论哪种方式，都需要为每个输出节生成对应的程序头。这个任务暂时不设置权限，所有段都是rwx，重点是建立多段布局的框架。
你需要实现：节的分类与合并逻辑，多个程序头的生成
测试命令：make test_5
📖 详细指导
为每个段设置正确的访问权限：代码段只读可执行（r-x），只读数据段只读（r--），可读写数据段可读写但不可执行（rw-）。实现段对齐以满足操作系统的页管理要求（4KB边界）。正确处理.bss节，使其在文件中不占用空间，但在运行时分配相应的内存。
你需要实现：设置程序头的权限标志，实现段对齐，特殊处理BSS节
测试命令：make test_6
📖 详细指导
实现对静态库（归档文件）的支持。静态库包含多个目标文件，链接器应该只提取程序实际使用的那些目标文件，而不是全部包含。这需要实现按需链接算法：迭代地解析符号引用，从库中提取相关的目标文件，直到所有符号都被解析或确认为未定义。
你需要实现：扩展FLE_ld以识别和处理归档文件输入
测试命令：make test_7
📖 详细指导
实现生成共享库的能力。与静态链接不同，共享库中对外部符号的引用需要保留到运行时解析。这个任务采用加载时代码修正（text relocation）的简化方案，生成动态符号表导出库中的符号，并保留未解析的重定位信息供加载器在加载时修正。
你需要实现：修改链接流程以生成.so类型的输出，处理动态符号和运行时重定位
测试命令：make test_bonus1
📖 详细指导
实现链接到共享库的可执行文件。程序通过全局偏移表（GOT）和过程链接表（PLT）间接调用共享库中的函数。链接器需要创建GOT和PLT，将对外部符号的函数调用重定向到PLT桩代码，并生成动态重定位表告诉加载器如何填充GOT。
你需要实现：创建和管理GOT与PLT，生成动态重定位表，记录依赖的共享库
测试命令：make test_bonus2
📖 详细指导
使用 GitHub Classroom 进行提交。请你确保所有代码已提交到你的对应仓库，GitHub Actions 会自动运行测试，其输出作为我们的评分依据。
分数由正确性评分和质量评分两部分组成，正确性评分占 60%，质量评分占 40%，即：
如果你完成了选做任务，那么总分可能会超过 100 分。超出的部分会正常按比例折算到你的平时分中。
其中，正确性评分由 GitHub Classroom 自动计算，质量评分由助教根据代码风格和实验报告综合评估，具体衡量因素为：
- 代码风格
- 代码表达能力强，逻辑清晰，代码简洁，仅在必要时添加注释
- 防御性编程，进行多层次的错误检查
- 如果你使用 C++ 风格进行编码，请积极使用 C++ 标准库，而非重复造轮子
- 实验报告
- 实验报告内容完整、格式规范、结构清晰
- 实验报告内容与代码一致，无明显矛盾，体现出对实验考察知识的基本了解
- 有思考，有总结，有反思，有创新
- 对实验提供有价值的反馈和建议，积极参与开源协作
你可以阅读调试指南，了解如何使用评测脚本和 VSCode 调试。
这个实验的核心价值在于你自己动手实现链接器的过程，并以此祛除对底层系统的恐惧感。参考资料、讨论问题、寻求思路上的启发都是正常的学习方式，但直接复制他人的代码——无论是从同学、网络还是其他任何来源——都违背了实验的初衷。
为了维护课程的公平性，我们会使用基于 AST（抽象语法树）的代码查重系统。该系统能识别代码逻辑结构的相似性，变量重命名或格式调整无法避开检测。一旦确认存在实质性的抄袭，我们将不得不根据学校相关规定进行严肃处理。
如果你在实验中遇到了持续的、真正的困难，请及时在讨论区提问或联系助教。我们在设计实验时已经考虑了难度的渐进性，但如果某个地方确实存在理解上的断层，我们非常乐意为你提供思路上的引导，帮助你跨越障碍。
大语言模型和编程助手正在改变软件开发的方式，我们鼓励你明智地使用它们。
AI 工具最有价值的用法是帮助你理解概念、解释错误信息、提供调试思路。比如，当你在文档中看到晦涩的术语，或者面对编译器报出的复杂错误不知所措时，AI 是极好的解释者。当你对某个模块的设计犹豫不决时，与 AI 探讨不同方案的优劣也是很好的思维训练。
但如果你直接让 AI 生成整个函数或大段代码，然后不加理解地使用它，这会产生两个严重的问题：
- 链接器是一个高度耦合的系统，各个模块之间存在紧密的依赖。如果关键逻辑不是由你亲自构建，你很难建立起完整的心理模型，导致在后续调试或扩展功能时寸步难行。
- 如果你对代码的实现细节不够理解，这会体现在实验报告中——你可能无法清晰地解释自己的设计决策，或者报告的内容与代码实现不一致。
实验报告是展示你理解程度的重要途径。报告应该用你自己的语言，描述你的实现思路、遇到的问题和解决方案、对实验的反思。相比于四平八稳但缺乏个人见解的技术文档，我们更看重带有个人印记的真实记录。
最终的评分由代码正确性、代码质量和实验报告共同决定。我们看重的是“真实”。如果我们发现你的代码表现与你的理解深度存在显著落差，这将直接反映在你的质量评分中。
Tip
前面的区域以后再来探索吧！
完成所有任务后，你已经实现了一个功能完整的链接器，能够处理静态链接、库文件，甚至基础的动态链接。但现代生产级链接器的能力远不止于此。如果你对系统软件设计感兴趣，以下是一些值得探索的方向。
这些方向不会被计入评分，但它们代表了链接器设计中的实际工程挑战。如果你愿意尝试并有所收获，欢迎通过Pull Request分享你的实现或改进实验框架。
延迟绑定与过程链接表。在Bonus 2中，你实现的动态链接在程序启动时就解析所有外部符号。但对于只使用库中少数函数的程序，这会造成不必要的启动延迟。延迟绑定通过PLT（Procedure Linkage Table）机制，让符号在第一次被调用时才解析。这需要为每个外部函数生成一小段桩代码，理解x86-64的调用约定，以及实现首次调用时的动态解析逻辑。PLT是动态链接性能优化的关键，但它的实现涉及较多的ABI细节。
符号版本管理。想象你维护着一个被广泛使用的库。你想添加新功能，但又不能破坏使用旧版本的程序。符号版本机制允许同一个库导出多个版本的符号，让新旧程序都能正确工作。这需要设计版本定义语法，在符号表中记录版本信息，以及在符号解析时考虑版本匹配。Linux的glibc就大量使用了符号版本来维护二进制兼容性，这是长期维护系统库的必备技术。
链接时优化。传统的编译流程是"编译优化，然后链接"。但很多优化机会只有在看到整个程序时才能发现——比如跨文件的函数内联、无用代码消除、全局的寄存器分配。链接时优化（LTO）让编译器在链接阶段重新审视整个程序，进行全局优化。实现LTO需要目标文件存储中间表示而不只是机器码，以及在链接器中集成优化器。这模糊了编译和链接的界限，是提升程序性能的有力手段。
增量链接。大型项目的完整链接可能需要几分钟甚至更长时间。增量链接通过追踪哪些目标文件发生了变化，只重新链接必要的部分，可以大幅缩短开发周期中的构建时间。这需要设计一个依赖图来记录符号间的引用关系，判断哪些变化会影响哪些部分，以及如何在不破坏地址稳定性的前提下插入或替换代码。增量链接的实现需要在速度和正确性之间做出细致的权衡。
调试信息的处理。你可能注意到我们的实验没有涉及调试信息——那些让你在GDB中能够看到源代码位置、变量名、类型信息的数据。真实的链接器需要处理DWARF格式的调试信息，在链接过程中正确地重定位和合并这些数据。调试信息的体积往往比代码本身还大，如何高效处理它们是一个工程挑战。更进一步，你还可以实现对GDB的支持，编写Python脚本让调试器能够理解FLE格式，使你生成的程序可以被标准调试工具分析。
安全特性的强化。现代链接器不仅要生成正确的程序，还要帮助防御各种攻击。除了基本的数据执行保护，还有栈保护（stack canary）、地址空间随机化的增强版（ASLR with full PIE）、控制流完整性（CFI）、重定位表的只读保护（RELRO）等。这些机制需要链接器、编译器和操作系统的配合。理解它们不仅能让你写出更安全的链接器，也能让你成为更好的安全研究者。
跨平台支持。我们的实验专注于x86-64/Linux平台。但真实世界有ARM、RISC-V、MIPS等多种架构，以及Windows、macOS等不同的操作系统。每个平台有自己的ABI、重定位类型、文件格式。实现一个跨平台的链接器需要设计好抽象层，把平台相关的细节隔离开来。观察LLVM的lld链接器是如何做到这一点的，会很有启发。
这些方向各自都能发展成一个完整的项目。选择其中感兴趣的一个深入研究，不仅能加深对链接过程的理解，也能让你体会到系统软件设计中的工程权衡——性能与简洁性、灵活性与复杂度、通用性与优化之间的张力。这些思考方式会在你未来设计任何系统时都有价值。
本实验由 22 级图灵班的李知非同学和彭文博同学共同提出并设计完成，2025 年的迭代更新由彭文博同学完成。
实验的完善是一个接力的过程，感谢所有助教和同学的反馈和帮助，让本实验一届一届地变得更好。21 级的潘俊达同学为初版文档提供了诸多建设性建议；23 级的李甘同学审阅了本年度的实验文档并提出改进意见；23 级的孙浩翔同学和路宸同学在实验中发现并反馈了框架中的问题。还有许多同学在实验报告中留下了真诚的反馈，在此一并感谢。
特别感谢柴云鹏教授和王晶教授对本实验的悉心指导与大力支持。他们的专业见解和宝贵建议对实验的完善起到了重要的推动作用。