联创团队 Lab 组 2025 春季招新入门指南

如果你感觉你对计算机科学很感兴趣，又不完全是其他组的范畴，请来 Lab 组！

本指南为针对面试和熬测的大致学习方向。资料仅作参考，可自行选择合适的书籍、文档、课程资源等。

注意：本页面后半段含有往年熬测样题，包括熬测要求和4道题目，可能对于你准备熬测有一定程度的帮助。

Lab 组是做什么的？

在 Lab 组，你可以学以致用，对计算机科学的各个具体的方向进行学习和研究。系统和网络编程、高性能计算、服务器运维、分布式系统、算法开发、数据库及存储，校园周边餐饮都是我们乐于研究的领域。

对这些方向不甚了解？下面提供了研究这些方向可以做的事情，你可以根据自己的兴趣和能力去选择。

计算机偏向底层的系统设计和编程需要大量知识支撑，这也是为什么我们的指南包含各个方向的计算机理论知识，其中不乏 CSAPP、算法导论这样的大部头。

当然，如果你在这些具体方向已有涉猎，了解这些特定领域的知识。我们也很欢迎你在简历和面试中向我们展示你的学习成果、介绍你的开发经验。

Basic（一个月？足够了！）

建议你在面试之前对以下内容有基本的了解

Advanced（More and Better）

计算机系统基础

Linux进阶

常见数据结构和算法实现和应用

编程语言

Hardcore（学好一两项就来快速通道吧）

以下内容可以作为较为长期、具体的学习方向，并不做出要求。熬测主要考察学习能力和热情，而不是知识的积累。这里的内容主要针对优势很大，可以直接 A 过去的同学。对于快速通道的同学，我们会安排一场时间更长的面试，更加深入的了解你的能力。如果通过了快通面试，即可跳过熬测。

网络

操作系统

安全

编译原理

存储

高性能计算

算法

关于熬测

熬测需要你在一天内（熬测指的是熬日测试，一般是从下午到晚上，熬夜测试已经进入历史的垃圾堆了），从给定的若干个方向（Shell 脚本，操作系统，网络，算法 & 数据结构，……）的题组中，在完成必做部分的基础上，解决若干个你感兴趣的选做题目。我们最终会根据你的完成情况来决定你是否能进入最终的群面（群面就是和联创各组同学聊聊天）。

Tips

  1. 简历和笔试问卷会很大程度地影响我们对你的评价，面试的过程也会围绕你的简历和笔试问卷中的内容来展开，所以请在二者中尽可能地展示自己的亮点。

  2. 为了保证你能有舒适的熬测体验，我们希望你在熬测前， C 语言水平足够解决以下问题：

  1. 如果你学有余力，还可以尝试以下内容：

样题：联创团队 2023 春招 Lab 组熬日测试

欢迎来到联创团队 Lab 组熬测！熬测时间：13:00~22:00。

熬测地点：线上或启明学院亮胜楼810，外面有热水饮水器、垃圾桶和厕所，1 楼有自动售货机。

在后面的小桌子自行倒冷水和取用零食，不要不好意思。不过注意悠着点吃，不要把一个品种的零食都吃光了，因为后面还有其他组的同学熬测。饭点（17:00~19:00）可以自行进餐，包括离开熬测现场去食堂、饭店，或者点外卖到这里吃。麦当劳、泡面什么的都可以吃，但是希望你不要吃螺狮粉等气味大的食物。

保持 810 干净整洁，离开熬测现场时带走产生的垃圾。如果把什么饮料洒到地面上，也要使用纸巾、抹布及时清理。熬测时可以做任何不打扰其他人的事情，包括上网查找资料，戴耳机听歌，水群聊跟熬测无关的天，睡觉。但是严禁和其他人线下或者线上交流熬测题目，这是非常严重的作弊行为，一旦发现，你的熬测成绩将会被取消，作弊行为也会向其他团队通报！熬测结束后，熬测题目也不要向外透露。

熬测必须在 Linux 下进行，包括虚拟机、物理机、WSL等（不含Windows下的Git Bash）。若有题目不在 Linux 下完成，你的整个熬测成绩将会被取消！

提交完毕请联系工作人员，确保答案被正确接收以后再离开考场。可以提前离场，但是要注意保留熬测答卷至熬测结果出来。熬测答卷压缩包最好是 tar.gz 格式，严禁使用 rar。

我们为你准备了 4 道题目。

除了必做部分，其他题目你可以自由选做。在做题的同时，你需要每小时记录自己的进度，供现场的监考同学检查（线上的同学则需将进度记录和答案一并上传）。不要忽视这一条要求。不要攒一两个小时再写进度，你应当在每个整点后几分钟就记录下来自己的进度。

如果你对题目有任何问题，请联系现场的同学或者QQ提问各题目负责人。

再次提醒，所有任务都需要在 Linux 系统下完成。祝你玩得愉快！

一些提示

熬测中可能会涉及到大量你从未接触过的内容，但是我们已经将任务拆解成了若干个易于解决的小问题。我们希望你能通过完成这些题目，来理解计算机科学的不同领域。

Trouble Shooting

一切顺利？一般都不会太顺利的。如果你第一次接触这些知识，一定会遇到一些困难。给大家的建议：

在完成这些题目的过程中，你可能会遇到很多问题，请善用两个工具：“RTFM” 和 “STFW”。其中的 “F” 让它们更具有传奇色彩。再次强调要看清楚网上的解决方案是否适合你的系统环境，以及是否说明了出问题的原因。

RTFM(Read The F**king Manual)

不要盲目相信网上的博客, 二手知识远没有手册可靠, 更何况手册并不难以理解.

如何阅读手册? 你可能会认为”看手册”就是”把手册全看一遍”, 因而觉得”不可能在短时间内看完”. 因此去选择网上的博客. 首先, 你应该学会使用目录, 了解一本书都有哪些内容的最快方法就是查看目录, 尤其是当你第一次看一本新书的时候. 查看目录之后并不代表你知道它们具体在说什么, 但你会对这些内容有一个初步的印象, 提到某一个概念的时候, 你可以大概知道这个概念会在手册中的哪些章节出现. 这对查阅手册来说是极其重要的, 因为我们每次查阅手册的时候总是关注某一个问题, 如果每次都需要把手册从头到尾都看一遍才能确定关注的问题在哪里, 效率是十分低下的. 事实上也没有人会这么做, 阅读目录的重要性可见一斑.

更多的手册阅读技巧请参考: NJU ICS PA1 如何阅读手册

STFW(Search The F**king Web)

如果你遇到了玄学的问题, 请使用英文, 在 Google 上搜索, 这样可以帮你快速找到答案.

关于 ChatGPT 和 New Bing

为什么不呢？能从 ChatGPT 和 New Bing 中获取到知识当然是好事，你当然可以使用语言对话模型进行查询和辅助代码编写。

为什么是英文?

以下文段来自 NJU ICS PA0.

随着科学技术的发展, 在国际学术交流中使用英语已经成为常态: 顶尖的论文无一不使用英文来书写, 在国际上公认的计算机领域经典书籍也是使用英文编著. 顶尖的论文没有中文翻译版; 如果需要获取信息, 也应该主动去阅读英文材料, 而不是等翻译版出版. “我是中国人, 我只看中文”这类观点已经不符合时代发展的潮流, 要站在时代的最前沿, 阅读英文材料的能力是不可或缺的.

阅读英文材料, 无非就是”不会的单词查字典, 不懂的句子反复读”. 如今网上有各种词霸可解燃眉之急, 但英文阅读能力的提高贵在坚持. “刚开始觉得阅读英文效率低”, 是所有中国人都无法避免的经历. 如果你发现身边的大神可以很轻松地阅读英文材料, 那是因为他们早就克服了这些困难. 引用陈道蓄老师的话: 坚持一年, 你就会发现有不同; 坚持两年, 你就会发现大有不同.

撇开这些高大上的话题不说, 阅读英文材料和你有什么关系呢? 有! 因为在PA中陪伴你的, 就是没有中文版的各种手册(例如i386手册), 当然还有man: 如果你不愿意阅读英文材料, 你是注定无法独立完成PA的.

作为过渡, 我们为大家准备了全英文的PA0. PA0的目的是配置实验环境, 同时熟悉GNU/Linux下的工作方式. 其中涉及的都是一些操作性的步骤, 你不必为了完成PA0而思考深奥的问题.

你需要独立完成PA0, 请你认真阅读讲义中的每一个字符, 并按照讲义中的内容进行操作: 当讲义提到要在互联网上搜索某个内容时, 你就去互联网上搜索这个内容. 如果遇到了错误, 请认真反复阅读讲义内容, 机器永远是对的. 如果你是第一次使用GNU/Linux, 你还需要查阅大量资料或教程来学习一些新工具的使用方法, 这需要花费大量的时间(例如你可能需要花费一个下午的时间, 仅仅是为了使用vim在文件中键入两行内容). 这就像阅读英文材料一样, 一开始你会觉得效率很低, 但随着时间的推移, 你对这些工具的使用会越来越熟练. 相反, 如果你通过”投机取巧”的方式来完成PA0, 你将会马上在PA1中遇到麻烦. 正如etone所说, 你在专业上的技不如人, 迟早有一天会找上来.

Basic Calculator

实现一个简单的整数计算器

Warm Up

你是否听说过一门名叫 Lisp 的语言，它的一大特色就是波兰表达式(Polish notation)，它一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。它的优势在于，如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析。

例如中缀表达式 (5 - 6) * 7 可以转换为波兰式 - 5 * 6 7 。

而我们今天的 Basic 、 Advanced 和 Hard 实现需要用到的是逆波兰表达式。逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法、后序表示法。逆波兰记法也不需要括号来标识操作符的优先级。

Lunatic 中可能需要转而使用其他的方法。因此：

如果你顺序做题，当你完成 Hard 后，你应该转而尝试其他的题目，其他题目完成或完全没有思路时，你才应该开始思考 Lunatic 。

如果你对自己的实力足够自信，可以跳过 Basic 、 Advanced 和 Hard 直接实现 Lunatic 。

例如中缀表达式 5 + ((1 + 2) * 4) - 3 可以转换为逆波兰式 5 1 2 + 4 * + 3 - 。

Basic

请你实现一个程序，可以读入运算表达式，输出它的结果。

需要支持：

  1. + , - , * , / 及其正确的运算顺序
  2. 括号表达式
  3. 基本的对负数的支持（例如，能计算 1 + -3）

提示：

Advanced

请你在 Basic 的基础上增加对变量的支持。

实现后的效果：

> x = 10
> x = x + 1
> x

一些建议：

  1. 你可以假设变量只有 [a-z] ，而且都是全局的。当它们没有被初始化时，其值为 0 。

Hard

请你在 Advanced 的基础上增加对函数声明与调用的支持（支持如下形式即可）。

为了简化难度：

  1. 函数只需要支持单个参数
  2. 函数定义在一行内完成
  3. 函数调用时可以传入一个表达式

实现后的效果：

> function parabola(x) return x*x + 2x + 1 end

> parabola(1)
> parabola(1+2)

Lunatic

都已经到这里了，我们为什么不给函数加更多的功能呢？

What you need to implement

请你在 Hard 的基础上增加函数的流程控制功能，你的函数应该可以递归调用。

为了简化实现：

  1. 只需要实现 if-else 和 while 语句
  2. 交互式中只能定义函数或者执行单行表达式

What you need to learn

以下知识点并不是正交的，你无需按顺序了解

语法分析

没有优化的编译器（解释器）结构可能是这样的：

词法分析 -> 语法分析 -> 语义分析 -> 代码生成/解释执行

为了实现流程控制和递归调用函数，你可能需要放弃之前使用过的方法，采用实现解释器的思路来解决问题。由于 BC 的语法以及实现功能较为简单，你主要精力应该放在语法分析上。

文法/巴科斯范式（BNF）

你无需深入了解文法，只需要能够看懂巴科斯范式即可

你需要实现的语法将会以 BNF 的形式给出

BNF 规定是推导规则(产生式)的集合，写为：

<符号> ::= <使用符号的表达式>

这里的 <符号> 是非终结符，而表达式由一个符号序列，或用指示选择的竖杠 | 分隔的多个符号序列构成，每个符号序列整体都是左端的符号的一种可能的替代。从未在左端出现的符号叫做终结符。

如下是 GPA 的 BNF ：

<gpa> ::= "4.0" | <leading> "." <trailing>
<leading> ::= [0-3]
<trailing> ::= [0-9]

LL parser

语法分析一般有 LL（自顶向下）和 LR（自底向上）两种分析方法，这里介绍的是 LL 分析器。

LL 分析器是一种处理某些上下文无关文法的自顶向下分析器。因为它从左（Left）到右处理输入，再对句型执行最左推导出语法树，所以被称为 LL 。

一个 LL 分析器若被称为 LL(k) 分析器，表示它使用 k 个词法单元作向前探查。对于某个文法，若存在一个分析器可以在不用回溯法进行回溯的情况下处理该文法，则称该文法为 LL(k) 文法。这些文法中，较严格的 LL(1) 文法相当受欢迎，因为它的分析器只需多看一个词法单元就可以产生分析结果。那些需要很大的 k 才能产生分析结果的编程语言，在分析时的要求也比较高。

在本题中，你可以使用 LL 分析法来处理，因为本题的文法简单，而且几乎是上下文无关的。当出现部分特殊情况时，特殊对待即可。

你也可以使用 yacc 等工具（这些工具可能采用 LR 分析法）来生成你的语法分析器。

抽象语法树（AST）

是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。

之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于 if-condition-then 这样的条件跳转语句，可以使用带有三个分支的节点来表示。

The BNF for BC

<onelinecomm> ::= <exp>

<funcdecl> ::= "function" <funcname> <funcbody>

<block> ::= <stat_list> <last_stat>
          | <last_stat>

<stat_list> ::= <stat>
              | <stat> <stat_list>

<stat> ::= <functioncall>
         | "while" <exp> "do" <block> "end"
         | "if" <exp> "then" <block> "end"
         | "if" <exp> "then" <block> "else" <block> "end"

<last_stat> ::= "return" <exp>
              | "break"

<number> ::= "[1-9][0-9]*" | "0"

<name> ::= "[a-z]+"

<var> ::= <name>

<funcname> ::= <name>

<namelist> ::= <name>
             | <name> "," <namelist>

<exp> ::= <add_exp>

<or_exp> ::= <and_exp>
           | <or_exp> '||' <and_exp>

<and_exp> ::= <eq_exp>
            | <and_exp> '&&' <eq_exp>

<eq_exp> ::= <rel_exp>
           | eq_exp> '==' <rel_exp>
           | eq_exp> '!=' <rel_exp>

<rel_exp> ::= <add_exp>
            | <rel_exp> '<' <add_exp>
            | <rel_exp> '>' <add_exp>
            | <rel_exp> '<=' <add_exp>
            | <rel_exp> '>=' <add_exp>

<primary_exp> ::= '(' <exp> ')'
                | "false"
                | "true"
                | <number>
                | <var>
                | <functioncall>

<add_exp> ::= <mul_exp>
            | <add_exp> '+' <mul_exp>
            | <add_exp> '-' <mul_exp>

<mul_exp> ::= <unary_exp>
            | <mul_exp> '*' <unary_exp>
            | <mul_exp> '/' <unary_exp>
            | <mul_exp> '%' <unary_exp>

<unary_exp> ::= <primary_exp>
              | '+' <primary_exp>
              | '-' <primary_exp>
              | "not" <primary_exp>

<functioncall> ::= <funcname> <args>

<args> ::= "(" ")"
         | "(" <exp_list> ")"

<exp_list> ::= <exp>
             | <exp> "," <exp_list>

<funcbody> ::= "(" ")" <block> "end"
             | "(" <namelist> ")" <block> "end"

Examples

实现后的效果：

> function fibonacci(x)
>> if x <= 2 then
>>> return x
>> else
>>> return fibonacci(x-1) + fibonacci(x-2)
>> end
> end

> fibonacci(5)

> 缩进只是为了显示清晰，不必实现

What you need to pay attention to

代码要求：

  1. 除构建脚本外必须使用 C/C++/Rust 语言。
  2. 不能调用其他程序或使用类似 eval() 函数来辅助计算。
  3. 允许使用 yacc 和 lex 或其他类似工具。

提交要求：

  1. 一些 C 源码文件，可以编译成一个可执行程序。
  2. 证明你的程序可以正确运行（比如截图）

加分项：

  1. 使用makefile、cmake、ninja等任意一种工具构建你的代码（如果是 Rust 则不用）。
  2. 更好的 CLI （例如使用了 readline 库 ）。

References

序言

嘉逸是华科知名的 Linux 用户，也喜欢做私房菜。他是一个材料学院的学生，自学了 Linux，并在网上分享了很多有关 Linux 的知识和技巧。因为他喜欢看菜鸟教程，所以被人叫做鸟哥。鸟哥是丁真珍珠的粉丝，为了致敬偶像，他学习了珍珠（Perl）语言。作为材料学院的学生，鸟哥需要做许多有关材料的实验。鸟哥在处理实验数据时发现，仅仅用手机上基础功能的计算器，非常不方便，有许多中间数据、方程、函数无法表达。他选择在终端输入 perl，再输入一些表达式，进行数据处理。基于 “解释执行” 的程序设计语言（包括 Shell 本身） 天生就具有这种交互式的工作模式。

C 这种编译型的语言，同样也可以实现 “交互式” 的 Shell ——支持即时定义函数，而且能计算 C 表达式的数值。如果你输入一行代码，比如strlen("Hello World")，这段代码会经历 gcc 编译、动态加载、调用执行，最终把代码执行得到的数值 11 打印到屏幕上。

在这个题中，你需要帮助鸟哥，实现 C-REPL，让他能够完成实验数据处理。

编程要求

这道题目需要用 C 语言完成。

我们希望你：

我们不会给出时空限制，但是请写出时空复杂度尽量优秀的程序。

背景

很多编程语言都提供了交互式的 read-eval-print-loop (REPL)，更俗一点的名字就是 “交互式的shell”。比如你在命令行输入 python，就可以和 Python shell 交互了。比如你想知道 $2^{100}$ 是多少，直接输入 $2**100$ 回车就可以了。现代程序设计语言都提供类似的设施，即便是非解释型的程序设计语言也提供类似的设施，例如 Scala REPL、go-eval 等。

在这个实验中，我们实现非常简单的 C 交互式 shell.

这个技术和现代虚拟机中的即时编译 (just-in-time) 技术是非常相关的：在程序运行时 (而非程序执行前) 进行编译，并将编译得到的二进制代码 (指令/数据) 动态加载。

题目描述

crepl - 逐行从 stdin 中输入，根据内容进行处理：

描述

解释执行每一行标准输入中的 C “单行” 代码 (假设我们只使用 int 类型，即所有输入的表达式都是整数；定义函数的返回值也永远是整数)，分如下两种情况：

    int fib(int n) { if (n<=1) return 1; return fib(n-1) + fib(n-2); }

函数接收若干 int 类型的参数，返回一个 int 数值。如果一行是一个函数，我们希望它将会经过 gcc 编译，并被加载到当前进程的地址空间中。函数可以引用之前定义过的函数。

    1 + 2 || (fib(3) * fib(4))

函数和表达式均可以调用之前定义过的函数，但不允许访问全局的状态 (变量) 或调用标准 C 中的函数。如果一行既不是合法的函数 (例如调用了不允许调用的函数)，也不是合法的表达式，crepl 可以不保证它们执行的结果 (不一定要报告错误，例如你的程序依然可以照常编译或执行，但你的程序要尽量不会 crash)；重复定义重名函数你也可以当做 undefined behavior 不必做出过多处理——我们的测试用例中没有这样的情况。

我们并不严格限制你的输出格式，你只要你为每一个函数或表达式输出一行即可，例如以下程序实现也是完全没问题的：

    $ ./crepl-64
    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
    OK.
    gcd(256, 144) * gcd(56, 84)
    = 448.

正确性标准

你只要能正确解析单行的函数 (以 int 开头)，并且默认其他输入都是表达式即可。我们可能会输入不合法的 C 代码 (例如不合法的表达式)；你的程序应该给出错误提示而不应该 crash。你可以做出比较友好的假设，没有刁难你的测试用例，都和 demo 中的差不多。

禁止使用 system() 和 popen()

好消息是这个题目我们不禁止 exec family 的系统调用：execl, execlp, execle, execv, execvp, execvpe 都是允许的。

完成路径与帮助

完成这项任务，大概需要以下的知识：

无法完整地完成这项任务是非常正常的，请不必过于担心，你可以从这几个角度尝试部分完成，我们会根据你的完成情况合理地给出评价。

这也提示你，应当合理将任务代码解耦。给出对自己代码的测试将会得到加分。

解析读入的命令

框架代码里已经包含了读入命令的循环 (看起来像是一个小 Shell)，它打印出一个提示符，然后接受输入并解析：

    int main(int argc, char *argv[]) {
        static char line[4096];
        while (1) {
            printf("crepl> ");
            fflush(stdout);
            if (!fgets(line, sizeof(line), stdin)) {
                break;
            }
            printf("Got %zu chars.\n", strlen(line)); // WTF?
        }
    }

当你在终端里按下 Ctrl-d，会结束 stdin 输入流，fgets 会得到 NULL。

这段代码里一个有趣的小细节是对 fflush 的调用：你会发现把它去掉对程序的运行并没有什么影响。但如果你在 fgets 之前插入一些延迟，例如 sleep(1)，你会发现 fgets 会 flush stdout 的缓冲区。但 C 标准并没有规定这个行为，glibc 只是因为大家用错得太多，为大家贴心地兜了底——其实 System 领域这种 “事实行为” 并不少见，大家错得多了，我们的库函数、编译器等不得不做出防御性的行为容忍大家犯错。一个例子是某一时期本的 gcc 会非常激进地对能证明的 undefined behavior 进行优化，但却导致不少以前 “正确” 工作的代码的崩溃，到新版本里反而不再做这些激进的优化了。

回到题目，在上面的代码里，如果读入的字符串以 int 开头，你就可以假设是一个函数；否则就可以假设是一个表达式。

把函数编译成共享库

对于一个一行的函数，比如

    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

如何把它编译成共享库？我们只需要把这个文件保存到临时文件里，例如 a.c 中，这涉及到文件读写相关的操作，希望你使用规范的文件操作。

然后，使用正确的选项调用 gcc 即可，再次强调，使用 gcc 进行编译。但是 gcc 是一个程序，而非可以当作过程调用的函数，那么应该怎样使用呢？我想你注意到了可以使用 exec family 的系统调用，如果你不太了解这方面的内容，请查阅手册。

除了编译和命名的问题，大家可能会感到困惑是，如果我的函数调用了其他函数怎么办？

    int foo() { return bar() + baz(); }

你不妨试着编译这个程序……它竟然可以被编译！所以忽略所有的 warnings 就好了！你不能使用 libc 中的 system 和 popen——它们会让题目变得有些过于简单。

把表达式编译成共享库

把函数编译成共享库是常规操作——库函数主要就是为我们提供函数的。但表达式怎么办？可以做一个 wrapper 呀！每当我们收到一个表达式，例如 gcd(256, 144) 的时候，我们都可以 “人工生成” 一段 C 代码

    int  __expr_wrapper_4() {
        return gcd(256, 144);
    }

注意到函数名里的数字——我们通过加上数字为表达式生成不一样的名字。我们的表达式变成一个函数，我们就可以把它编译成共享库了。把动态库加载到地址空间并得到 __expr_wrapper_4 的地址，直接进行函数调用就能得到表达式的值了。

共享库的加载

我们可以使用 dlopen 加载共享库，这个系统调用可以完成共享库的加载。

当你查询文档的时候，会知道返回值是一个 void * 类型的指针，这是我们刚刚编译得到的函数的函数指针吗？并不是，因为共享库并不是只能有一个符号（Symbol）。我们得到的地址是整个共享库的句柄，通过它，我们可以再利用 dlsym 找到对应的符号（Symbol，你的函数），进而完成调用。

另一个很不错的手册是 elf (5)。

其他资料

你可以在这里找到一些可能有用的资料。

REPL from wiki

Shared-Libraries in Linux

dlopen

dlsym

提交

除了提交你的代码，你还需要提交一份简要的文档，包含你是怎么测试你的代码的，以及大致的开发流程，在没有完全做完题目的情况下，文档将是能否获取部分得分的关键之一。

抄袭网上程序，后果自负！

passwd 文件系统

前言

传统上，这道题目应该是一个 shell 题。

但是出题人和他的小伙伴们深刻的认识到，即使不会 shell 编程大家也能管好 Linux 系统。比如，现在很多系统使用了 systemd，它使我们可以用规范的 service 文件来描述一个系统服务如何启动、何时启动、何时停止（它取代的是古老的 SysVinit，这个过时的 init 使用一些 shell 脚本来完成服务的启动停止等操作）。再比如，越来越多的系统默认安装了 python 等脚本语言，你可以用它们来完成一些自动化的工作。你可能很多年都不会亲手编写一个 shell 脚本——除非你在神秘路由器上与 busybox 协作，或者是在给软件打包写钩子，或者是在写一些脚本准备放到另一个未知的系统上使用……

所以这个题现在变成了，和 Linux 紧密相关的脚本语言编程题！

限制

安全教育

如果你试图完成本题的 Lunatic 难度部分，那么你的脚本可能会对自己的系统做一些敏感的修改，这可能会破坏你的系统。为了保护你的系统，同时避免出题人遭到投诉，故在此进行安全教育。

著名的开源软件 bumblebee 曾经出过事故。它在自己的安装脚本里面写了这个：

rm -rf /usr /lib/nvidia-current/xorg/xorg

这个脚本把 /usr/lib/nvidia-current/xorg/xorg 写成了 /usr /lib/nvidia-current/xorg/xorg，多了一个空格，导致脚本会尝试删掉系统上的 /usr 目录。同时这是个安装脚本，大家总是以 root 权限执行……

这仅仅是不小心的脚本造成的众多错误中的一例。为了保护你的系统，保护你的名誉，在用脚本执行敏感命令时，请提高警惕。

背景

我早就受够了 Linux 下那一坨奇怪的用户管理命令了，什么 useradd adduser usermod，还有什么 chsh passwd chpasswd，还有什么 groups groupadd addgroup。这一坨玩意完全不正交，功能相互重叠，又各自有一套不兼容的、unix 风格的、如果能用一个字母绝对不用两个的、奇形怪状的参数。感觉只有从计算机史前时代出来的老古董才会喜欢这堆东西。

我想要的是一个什么 passwdctl 之类的，能直接完全控制 /etc/passwd 的万能小工具；或者是一个类似 /sys 的虚拟文件系统，通过文件系统来提供查询和修改 /etc/passwd 的接口。

我决定让你来实现我的梦想。你来写一个文件系统，来提供查询修改 /etc/passwd 的接口，此即， passwd 文件系统 。 :)

题面

虽然说是个文件系统，但是它也是由一个个小组件构成的。出题人把整个任务拆成了好几个子任务，所以不必担心题目过难的问题。

本题分为 Easy Normal Hard Lunatic 共四个部分。你必须要完成的是 Easy 部分。一旦 Easy 部分完成，你可以先去做其他题，在其他题都做不出来的情况下再来做这道题。

Easy

这里我会手把手教你应该做些什么。你可能会有些迷惑，为什么这个程序要这样输出、为什么它要用这样的命令行参数。当你做到 Normal 部分时，你会发现这些格式的意义。不过在 Normal 及之后，就不会有出题人来手把手教你了。

首先，你要知道 /etc/passwd 是什么东西。简而言之，这是个数据库，存放了系统上所有用户的信息。你必须知道它的格式是什么样的，但是不必深究具体细节。比如，你要知道，第 X 个字段是 password。但是你不必知道 password 字段到底是怎么加密的，它的格式是什么……这些深究起来就没完了。

你可以使用 man 5 passwd 来获得一份较为详细的文档，也可以去 CSDN 找些三流博客来看些二手知识。

接下来，你要开始编写你的脚本。假设你的脚本名叫 passwd.sh，那么你的脚本需要处理两种参数，分别是描述如下。

你的脚本需要对 /etc/passwd 中保存的所有用户，用一种特定的格式输出他们的信息。这种格式规定如下：

-rw-r--r-- 1 XXX YYY 4096 Jan 1 2023 00:00 ZZZ

其中，XXX 是用户的 uid，YYY 是用户的 gid，ZZZ 是用户的名字。每个用户输出一行。一种输出样例如下：

-rw-r--r-- 1 0 0 4096 Jan 1 2023 00:00 root
-rw-r--r-- 1 1 1 4096 Jan 1 2023 00:00 daemon
-rw-r--r-- 1 8 8 4096 Jan 1 2023 00:00 mail
-rw-r--r-- 1 39 39 4096 Jan 1 2023 00:00 irc
-rw-r--r-- 1 105 65534 4096 Jan 1 2023 00:00 sshd
-rw-r--r-- 1 1000 1000 4096 Jan 1 2023 00:00 jyi
...

你的脚本需要忽略 XXX 参数。并且将用户名为 YYY 的用户的信息输出到文件 ZZZ 中。输出信息格式是自由的，但是要保证你解析了该用户在 /etc/passwd 的全部的七个字段。

一种输出样例如下：

$ passwd.sh copyout asdfasdfoaisd root ~/test.out
$ cat ~/test.out
Name:      root
Password:  x
UID:       0
GID:       0
Comment:   root
Home:      /root
Shell:     /bin/bash

Normal

AVFS 是一个神奇的东西，它允许我们用命令行程序来创建一个文件系统。在这一个部分里，你要把你编写的脚本接入到 AVFS 中。你需要做的内容如下：

如果你的一切步骤正确（如果不正确的话……自己查文档），那么你应该会实现下面这些好玩的东西：

$ mountavfs
Mounting AVFS on /home/jyi/.avfs...
$ cd .avfs/#passwd
$ ls
_apt     list        sshd
avahi    lp          sync
backup   mail        sys
bin      man         systemd-coredump
carrota  messagebus  systemd-network
daemon   news        systemd-resolve
games    nobody      systemd-timesync
gnats    polkitd     uucp
irc      proxy       www-data
jyi      root        zerotier-one
$ cat jyi
Name:      jyi
Password:  x
UID:       1000
GID:       1000
Comment:   jyi,,,
Home:      /home/jyi
Shell:     /bin/bash

你会发现，你拥有了一个神奇的文件系统。在这个文件系统里执行 ls，相当于列出所有用户。读取某个文件，则相当于读取某个用户的信息。

这可比那一堆破烂用户管理命令好用多了！！

注：这部分本质上不会有任何代码实现，主要是安装并且解决 AVFS 可能出现的种种问题。我们并没有什么好的方法来确定你完成了这项工作。所以，只要你提交了一些命令运行的结果（截图、文本皆可）并且声称自己完成了这项任务，我们便认为你已完成这项任务（即使有坏蛋可能会想着伪造结果，但我们认为你不是）。

Hard

现在，你需要支持目录。你可能会查很多很多 AVFS 的文档，祝你好运。

在 Normal 部分，你在 AVFS 中实现的目录结构大概如此：

├── daemon
├── jyi
└── root

其中，daemon jyi root 等都是文件，对其进行读操作便会获得相关用户信息。

而在 Hard 中，你需要把这个东西扩展，实现如下的目录结构：

├── daemon
│   ├── comment
│   ├── gid
│   ├── home
│   ├── name
│   ├── password
│   ├── shell
│   └── uid
├── jyi
│   ├── comment
│   ├── gid
│   ├── home
│   ├── name
│   ├── password
│   ├── shell
│   └── uid
└── root
    ├── comment
    ├── gid
    ├── home
    ├── name
    ├── password
    ├── shell
    └── uid

其中，daemon jyi root 都变成了目录。而对目录下面的文件读则代表获得相关的信息。比如，读取 jyi/shell 文件，结果是用户 jyi 的 login shell（我这里结果是 /bin/bash。你的机器上很可能没有 jyi 这个用户，没关系）。

Lunatic

在 Hard 的基础上，你需要支持写操作。为此，你可能需要查更多的 AVFS 文档。

Lunatic 中需要实现的目录结构与 Hard 相同。不同的是，支持了文件写操作。对文件写入，则对应着对相应字段的修改。例如，echo /bin/zsh > jyi/shell 的效果与 chsh -s /bin/sh jyi 是相同的！

简直和 /sys 虚拟文件系统一模一样！通过简单的文件读写就能代替复杂的系统管理命令，完全符合我对新时代用户管理的想象，科技并带有趣味。

你需要大量的 Linux 用户管理知识来完成这项工作，祝你好运。

实现这个功能的过程中，请保护好你的 /etc/passwd。一旦搞坏了，可能会出现很可怕的后果。

参考资料

如果你一个脚本语言也不会，可以去 Runoob 上速成一下。记住我们的可选语言只有 awk/shell/perl/python！

关于 AVFS 的资料很少。它的官网上空空如也，并且软件包里也没有 man page。不过善良的出题人决定帮你一把：

AVFS 的文档在 /usr/share/doc/avfs 下面。里面的东西详细地介绍了 AVFS 的工作原理、工作过程以及接口等等。实现 passwd 文件系统时，你只需要和它的 extfs 这一部分打交道，描述这一部分的文档应该是 /usr/share/doc/avfs/README.extfs.gz。这个文档只有 129 行，并且有很多示例，看懂也不会用到很多生僻英语。

此外，如果你陷入了困境，也可以去 /usr/share/avfs/extfs/ 下面。里面都是基于 AVFS 的脚本，你看看别人是怎么做的。

Termbin

前置知识

描述

网上有一类网站叫做 pastebin, 用来临时粘代码发给别人。比如 ubuntu pastebin。你可以体验一下。

但是有时候我们想从终端直接粘贴文件，不想打开浏览器（程序员总是懒的）。

所以还有一类 pastebin 是通过命令行访问的，比如 termbin 。你应该体验一下。这个网站在国外，所以访问有可能很慢（十几秒）。

下面是从终端复制的一段文字，展示了使用时的场景。

$ echo just testing! | nc termbin.com 9999
https://termbin.com/vw95

打开 https://termbin.com/vw95 我们发现就是我们刚刚 echo 的文字。

你的任务

用 C 语言实现 termbin 的粘贴功能，并且能够支持用浏览器访问粘贴的内容。

要求程序运行在 Linux 环境下。

提示

你可能感到非常困惑或者无从下手。实际上这是一个简单的任务，包含了若干简单的环节。

根据你实现路线的不同，我们会有不同的评估。但是一个正常运行、功能完善的 Easy 程度的程序，比 Hard 程度的不能运行的程序，得到的评价要高。

在此将描述你需要的知识并给出参考资料。

我们重视快速学习和应用的能力。

工作原理

概览

我们需要实现的是一个 C 语言服务器程序，它包含两部分。

  1. 监听在 9999 端口，负责接受和保存客户粘贴文本的服务器程序。
  2. 监听在 80 端口，提供 HTTP 服务，负责处理浏览器 HTTP 请求并返回对应文本的服务器程序。

实现这两个功能有三种路线：

部分 1：接受和保存用户输入

  1. 监听 9999 端口 [C Socket]
  2. 接受用户连接，读取用户输入 [C Socket]
  3. 将用户输入写入文件 [C 文件读写]
  4. 用某种方式起一个合适的文件名 [C 文件读写]
  5. 向用户返回一个 URL，域名可以用 localhost 代替。比如 http://localhost/some_random_filename [C Socket]

所以你只需要学会 Socket 就行了！

思考题：并发处理多个用户

如果你之前会使用 Socket, 那么上面的内容对你来说过于简单了，来试试不一样的东西吧！

如果我们不使用多进程/多线程的并发技术，那么用户必须在我们的服务器上排队接受处理。对于这个任务来说，这是可以接受的。不过如果你能使用并发技术实现，当然会为你加分。

思考题没有参考资料，请自行搜索。

参考资料

部分 2：提供 HTTP 服务

Easy

体验和学习 python3 -m http.server。它可以直接帮你实现这个功能。你需要描述使用步骤并截图结果。

Medium/Hard

HTTP 是在 socket 中按一定格式传输 ASCII 字符串的协议。通过 curl -v 命令可以看到请求头和响应头。其中形如 Host: baidu.com 这样的属性基本都不是必须的。下面是一个例子。

$ curl -v http://baidu.com
*   Trying 39.156.69.79:80...
* Connected to baidu.com (39.156.69.79) port 80 (#0)
> GET / HTTP/1.1
> Host: baidu.com
> User-Agent: curl/7.75.0
> Accept: */*
> 
* Mark bundle as not supporting multiuse
< HTTP/1.1 200 OK
< Date: Thu, 18 Mar 2021 06:00:24 GMT
< Server: Apache
< Last-Modified: Tue, 12 Jan 2010 13:48:00 GMT
< ETag: "51-47cf7e6ee8400"
< Accept-Ranges: bytes
< Content-Length: 81
< Cache-Control: max-age=86400
< Expires: Fri, 19 Mar 2021 06:00:24 GMT
< Connection: Keep-Alive
< Content-Type: text/html
< 
<html>
<meta http-equiv="refresh" content="0;url=http://www.baidu.com/">
</html>
* Connection #0 to host baidu.com left intact

连接处理部分和部分 1 一样。在处理客户端的消息时，你需要

  1. 从 HTTP 请求头中解析出客户端想要请求的文件
  2. 找到对应的文件并将其内容作为响应的数据
  3. 将数据和 HTTP 响应头组合，返回给客户

其中必要的一些行是

请求：

GET / HTTP/1.1

响应：

HTTP/1.1 200 OK
Content-Length: 81

传输数据...

你至少需要理解必要行的含义。

提交要求

  1. 一些 C 源码文件，可以编译成一个或两个可执行程序。加分项：提交Makefile,实现make all编译, make run运行服务器，make test运行服务器并测试
  2. 证明你的程序可以正确运行（比如截图）