CS144 Spirng 2023
概述
通关了CS144 Spring 2023.如果不算搭建环境的话，一共是用了十天.
基本上全是自己完成的，没有参考任何别人的代码和实现，也没有让人帮忙debug. 只是在环境搭建和debugger配置上借鉴了其他人的方案。
开发环境是 Win11(后文会提到,被坑了一小下)上用 VSCode SSH 链接 Virtualbox(使用官方提供的镜像)
2023 Spring 版本移除了之前的 lab4(但是我决定挑战一下，过几天去试试往年的lab4),难度整体上是下降的。但是很多时候手册仍然说的不清楚，很多时候还要看测试用例才知道应该如何写，才知道这些函数的调用逻辑是什么.
而世之奇伟、瑰怪，非常之观，常在于险远，而人之所罕至焉，故非有志者不能至也。有志矣，不随以止也，然力不足者，亦不能至也。有志与力，而又不随以怠，至于幽暗昏惑而无物以相之，亦不能至也。然力足以至焉，于人为可讥，而在己为有悔；尽吾志也而不能至者，可以无悔矣，其孰能讥之乎？此余之所得也！
————《游褒禅山记》
工具的区别能决定效率的区别，而效率的区别大到一定程度，就决定了你能不能做完这个实验。这个实验很好，但是有些地方真的算是"幽暗昏惑"的地方，如果有同学被卡住了，却因为找不到合适的工具而被迫放弃，实在是太可惜了.希望这个文章能帮到未来做这个实验的同学。不过锻炼自己的各种方面的能力也是很重要的,一定要自己努力过仍然不会的情况下再参考别人的.
当然这个教程也不会太事无巨细，也尽量不涉及实现，只是指出一些可能的坑点,以及写一些我遇到的困难和心路历程。
实验准备
参考资料
夜游宫记梦-实验记录(2023)
haha-实验记录(2023)
斯坦福 gdb 使用指南
CS144 Debugging(cs144 官方？)
官方推荐的代码规范
环境搭建
我的环境是 Win11，通过 VSCode SSH 链接到 虚拟机.VSCode本身的配置因人而异，这里就不说了，反正有 Remote-SSH 插件就行了,我还安装了C/C++,IntelliCode，但是这两个插件本身还是要在连接虚拟机之后远程安装的.
宿主机
记得开启 windows 的防火墙，否则主机和虚拟机无法互相 ping 通.
VirtualBox 桥接模式，虚拟机 ping 不通宿主机
打开 windows defener 中的 防火墙和网络保护，点开里面的高级设置， 在入站规则中有两行 核心网络诊断 - ICMP 回显请求(ICMPv4-In) ，一个是域，一个是"专用，公用" ，都打开。这一步必须要做，否则主机宿主机无法联通，之后的代理也没法弄。
虚拟机
主要参考刚才放的那个 虚拟机有关事项的链接.
下载 virtualbox,将官网上给的镜像下载后解压，然后导入到 virtualbox. 解压后说是文件末端损坏，我重新下了还是损坏，就凑合着用了，也没问题。
启动虚拟机，初始用户和密码都是cs144,登进去之后会让你修改密码，新密码短了还会被拒绝。
然后可以将宿主机的 ssh 公钥放到虚拟机的~/.ssh/authorized_keys中。之后SSH登录就不用反复输入密码了。
然后虚拟机的公钥也可以绑定到你github账号上,之后就可以上传了.
网络
虚拟机的网络设置成桥接模式。桥接模式是说，主机有一张真正的网卡，桥接模式就是通过这个真正的网卡进行上网。它和宿主机在同一个网段，有不同的 ip。
在虚拟机上使用 ifconfig(一开始没这个命令，需要自己sudo apt-get install net-tools) ,可以看到自己的 ip,记下来。比如下文的 192.168.11.25.
enp0s3: flags=4163<UP,BROADCAST,RUNNING,MULTICAST> mtu 1500
inet 192.168.11.25 netmask 255.255.255.0 broadcast 192.168.11.255
在宿主机上使用 ipconfig ,可以看到宿主机的 ip,记下来。我的是 192.168.11.36
Windows IP 配置
以太网适配器 以太网:
连接特定的 DNS 后缀 . . . . . . . :
本地链接 IPv6 地址. . . . . . . . : fe80::3a6c:c7cf:307:cc1c%10
IPv4 地址 . . . . . . . . . . . . : 192.168.11.36
子网掩码 . . . . . . . . . . . . : 255.255.255.0
默认网关. . . . . . . . . . . . . : 192.168.11.1
以太网适配器 以太网 2:
连接特定的 DNS 后缀 . . . . . . . :
本地链接 IPv6 地址. . . . . . . . : fe80::180d:a08e:7628:d8a%14
IPv4 地址 . . . . . . . . . . . . : 192.168.56.1
子网掩码 . . . . . . . . . . . . : 255.255.255.0
默认网关. . . . . . . . . . . . . :
千万不要记反了！千万不要记反了！千万不要记反了！
首先要看两者可不可以互相 ping 通，一般开了防火墙都可以 ping 通。不能ping通的再检查检查上面的步骤，比如这两个ip啊，其实看这个掩码，255.255.255.0,也能猜到他俩是一个网段的，因为前三个数字都一样，都是192.168.11.
在虚拟机中可以通过 curl www.baidu.com 来看看能不能上网。
由于某些众所周知的原因，我们还需要设置代理,当然不设置也没什么问题，无非github可能慢一些或者偶尔链接不上。宿主机的Clash上记得开启 Allow Lan，其他软件再找别的办法吧。
最后在~/.bashrc中设置代理
_ip=192.168.11.36 # 一定要是宿主机的ip，一定不要写错了
_port=7890 # 你的 clash 端口
export http_proxy=http://$_ip:$_port
export https_proxy=https://$_ip:$_port
设置 git 的默认编辑器为vim,默认是nano，看个人喜好了.
git config --global core.editor "vim"
扩容
这个 10G 其实有点小，做实验的中途可能需要扩容。
使用 df 命令能够展示所有的分区空间使用情况。
# 这是我扩容后的,重点是 /dev/sda2 这一行，可以看到是25G
cs144@vm:~$ df -h
Filesystem Size Used Avail Use% Mounted on
tmpfs 795M 1.1M 794M 1% /run
/dev/sda2 25G 9.2G 15G 40% /
tmpfs 3.9G 0 3.9G 0% /dev/shm
tmpfs 5.0M 0 5.0M 0% /run/lock
tmpfs 795M 4.0K 795M 1% /run/user/1000
可以看到，官方给出的镜像，其实只有一个盘(/dev/sda2),然后挂了一个分区(/)。
扩容的方案其实就是增大 /dev/sda2 的大小。
首先要把虚拟机关机，然后在 virtualbox 里启动虚拟介质管理器(ctrl+D),然后选中磁盘。
注意，注意，注意
一定要选中最下面的分支的，也就是把树展开到底，把最深层的给扩容.这个树本身是快照形成的，如果没有快照就一层，然后越往下的越新(这一点可以通过查看属性里面的明细里面的 "分配到"来验证，比如我的虚拟机叫 cs144,然后 cs144-intel 开头的是分配到 cs144(init)，也就是我的第一个快照，然后 057 开头的那个就分配到 cs144,没有后缀，也就是最新的版本)。
cs144-intel-2023-disk001.vdi
|- {05789766-4869-46b3-b02a-56f754ff586d}.vdi
比如这种情况就选中 057 开头的那个，在属性界面把容量拉大，比如我拉到了 25GB.
然后从网上下载一个 gparted 的 live iso 镜像，或者是 ubuntu 的 desktop 启动盘也可以，里面也有 gparted。
这一步做完之后可以参考下列视频，之后的步骤和他是一样的，他下好了镜像。视频没声音 Resize Ubuntu 20.04 Virtual Box VM with GParted
在 cs144 虚拟机的设置的启动顺序里设置启用光驱启动，并且顺序在硬盘前面。然后在存储设置里配置好刚才下载的镜像。
启动虚拟机，就进入了 iso 镜像(假设是 gparted 那个，ubuntu Live 那个启动后选择 try ubuntu,然后在应用里面选择 gparted 也一样)，所有的全部默认选项。
进入后启动 gparted,然后能看到 /dev/sda2 的右侧有空闲的 15G，然后右键 sda2，点击Resize/Move ，然后拉满，确定，保存,退出,关机。 然后移除光驱，然后启动。
再进入虚拟机(注意，以上的操作中不要改其他的设置。我就下意识启动了 UEFI，结果镜像进不去了)，再使用df -h ，就可以看到扩容成功了。
Win11 的大小调度
我的cpu是 i9-12900，是有大小核之分的.在后续的开发过程中，我观察到有时候性能会突然降低很多，不仅仅是代码运行效率变慢，甚至编译都慢了。摸索了很久，发现，win11的大小核调度很粗暴，如果你把一个软件给最小化了(摁右上角的最小化按钮),那么就会把他调度到小核里面执行！
解决办法也很简单，就不要把virtualbox最小化，可以打开之后然后再切换到vscode，永远不要把它最小化，就可以了。如果被调度到小核也不要紧，就再切到virtualbox，再切回来就行了。
开发配置
在lab0里面拉下来代码后，可以在工作区根目录新建 .vscode/c_cpp_properties.json,输入以下内容,vscode 的 IntelliCode 插件就可以正确解析了。
{
"configurations": [
{
"name": "Linux",
"includePath": ["${workspaceFolder}/**"],
"defines": [],
"compilerPath": "/usr/bin/c++",
"cStandard": "gnu11",
"cppStandard": "gnu++20",
"intelliSenseMode": "linux-gcc-x64"
}
],
"version": 4
}
为了满足格式化要求， 可以在 .git/hooks 下新建文件 pre-commit ，并且加上可执行权限.
这样在每次 commit 时，就会格式化所有文件。对于原来就在暂存区里的，就把格式化后的修改一起提交。原来不在暂存区里的，也会格式化，但是不会提交。
#!/bin/bash
# Redirect output to stderr.
exec 1>&2
# Get the list of files that are staged for add
files=$(git diff --cached --name-only --diff-filter=ACM)
cmake --build build --target format
# Check the exit status of the previous command
if [ $? -ne 0 ]; then
echo "CMake format failed, please fix the errors and try again."
exit 1
fi
echo "CMake format success."
# Otherwise, add the formatted file to the staging area
git add $files
# Exit with zero status
exit 0
debug
{
"version": "0.2.0",
"configurations": [
{
"name": "cs144_debug", //!挑个容易识别的名字
"type": "cppdbg",
"request": "launch",
"program": "${workspaceFolder}/build/tests/${fileBasenameNoExtension}", //!设置为测试程序源码相对应的目标程序路径
"args": [],
"stopAtEntry": false,
"cwd": "${workspaceFolder}",
"environment": [],
"externalConsole": false,
"MIMode": "gdb",
"setupCommands": [
{
"description": "为 gdb 启用整齐打印",
"text": "-enable-pretty-printing",
"ignoreFailures": true
}
],
//"preLaunchTask": "C/C++: g++-8 build active file", //!不需要前置任务
"miDebuggerPath": "/usr/bin/gdb"
}
]
}
lab0
telnet
telnet 这个跟着做就是了，似乎打字太慢会超时，而且要注意不能打错字。
发送邮件
这个有点折腾，因为没有斯坦福的邮箱。我使用的是163邮箱给qq邮箱发邮件。
利用 telnet 实现发送 163 邮件（SMTP）
base64 加解密工具
第一步要去 163 里面开启 SMTP 服务，我只开启了IMAP/SMTP服务,然后里面要发送短信申请一个授权码，一定要保存好。
然后命令行输入 telnet smtp.163.com 25，就可以链接了，
注意，基本上除了输入邮箱的格式不一样之外，剩下的和教程是一样的。
cs144@vm:~$ telnet smtp.163.com 25
Trying 123.126.97.113...
Connected to smtp.163.com.
Escape character is '^]'.
220 163.com Anti-spam GT for Coremail System (163com[20141201])
HELO dawnk
250 OK
AUTH LOGIN
334 dXNlcm5hbWU6
XXXXXX # 这一行输入你邮箱的 base64 编码
334 UGFzc3dvcmQ6
XXXXXX # 这一行输入你授权码的 base64 编码
235 Authentication successful
MAIL FROM: <my_account@163.com> # 注意，这个 <> 不能省略，下同
250 Mail OK
RCPT TO: <my_qq@qq.com>
250 Mail OK
DATA
354 End data with <CR><LF>.<CR><LF>
FROM: <my_account@163.com>
TO: <my_qq@qq.com>
Subject: Hello from CS144 Lab 0!
This is body.
.
250 Mail OK queued as blabla(一堆字母)
QUIT
221 Bye
Connection closed by foreign host.
byteStream
比较简单，没啥好说.用队列也行，手写一个环形队列也行,稍微快点。整个项目会计算性能的只有 lab0 和 lab1。还是以完成任务为主，优化为辅。
Premature optimization is the root of all evil. -- Donald Knuth
lab1
从这个实验开始，就需要写一定的代码量了，而且也出现了复杂的逻辑.
我的建议是编写大量的 assert ,哪怕是对于一些显而易见的事情.
我举几个例子
- 中间会有大量的无符号数的减法，比如c = a-b最好在每次减之间，即使你认为肯定
a>=b也要进行assert(a>=b).否则遇到问题很难排查(因为会溢出). - 比如你的数据结构维护了某个性质(比如我用的set,里面各个段应当完全不相交，并且每次插入时候的段都是非空的段),这个性质看似显然，但是最好也要在插入后进行 assert .这里或许会感觉，每次都判断重不重复非常浪费性能，实际上可以用条件编译，设置一个宏，只在宏设置的时候进行检查。这样能在第一个异常的段插入的时候就能快速发现问题.
- 另外这个lab本身还有一些性质要维护。比如文档中就提到了关于容量的几个,比如
byte_pending() <= output.available_capacity,等等。
我是采用的 set，但是使用别的应该也可以，我改成list反而变慢了.
lab2
这里就发现 lab 的文档有一些情况没有说明了，对于自己拿不定，而预先假设的部分，一定要先写 assert(),比如我认为不会出现在收到SYN之前，先收到了某个非SYN段的情况。就先写个assert，然后假设没有这种情况，然后写剩下的逻辑，这样就会有很多个assert，运行测试用例的时候，就发现确实是有这种情况的，然后观察用例，就知道这时候要舍弃了.
但是还有一种情况，比如已经收到过了SYN，又来一个SYN，怎么办，这个也是先assert，然后再测试，发现这种情况也有，也是要舍弃。
还有一个技巧，比如你有一大段处理的逻辑，处理完之后，你认为"走到这一步，必然已经接受过SYN了",这种也可以加一个 assert，这样一是能检验前半部分的处理逻辑对不对，二是能让后面的代码不需要再考虑没接收到的情况，否则一旦前面逻辑有问题，后面也没有检查，就可能引起影响很深远的bug。
这些 assert 在你编写代码结束时，能让你保持警觉，因为有些是官方保证的，有些只是你的假想，可以配合todo注释，来增强你对代码的信心和了解.
说回到lab本身,lab2一开始让写的Wrap32着实让我摸不着头脑。这个还需要对他给出的表格反复品味。sequnce_number,absolute_number,str_index三者之间的关系。这一点会在后面的 tcp_receiver 和 tcp_sender 中都会用到。
比如这个 reassembler 的 first_index, 它本质上就是 str_index,因为 reassembler 本来就是接受从一个字符串不同位置切下的切片。但是 message中携带的是 sequnce_number,所以不仅要先切换成 absolute_number,还要再切换成str_index。
这就涉及到一个问题， checkpoint 怎么计算？当时我也很迷惑，就感觉checkpoint的功能太灵活了，以至于不知道怎么用为好。
其实没必要想的那么复杂，可以仔细分析一下。比如，absolute_number是uint64_t,文档中也提到了，完全没有用光的可能。然后 sequnce_number 是循环使用的,这个循环就是 checkpoint 的关键，文档上说的unwrap求的值是最接近 checkpoint的值，实际上我们只需要用后一半的特性就行。
我们假设sequence_number完美对应的值是abs,如果我们保证checkpoint<=abs,且它俩距离不会超过2^32，那么求出的abs肯定是对的.为什么呢？因为对于同一个seq，他们对应的相邻abs之间的距离就是2^32,如果他左侧的那个checkpoint和他的距离小于这个值，那么就一定可以通过这个checkpoint算出正确的 abs.
而 reassembler 本身就是维护一个长度不超过 2^16的滑动窗口，滑动窗口的第一个值是理所当然满足换这个条件的，放眼整个 absolute_number 的序列，滑动窗口左边的值都已经被确定了，而新来的信息也是存在在这个滑动窗口里面的(如果不在滑动窗口里面，算出abs后也会被 reassembler 筛掉)，所以滑动窗口的左边界是满足以上条件的，换言之，checkpoint 其实就是 inbound_stream.bytes_pushed() + 1，这个式子的含义是已经写入流的字符个数再加上 SYN本身占用的一个字节。在 absolute_number 中，已经接受了这些字节，然后由于从零开始，所以下一个期望接受的编号也是这个值。
这个lab还有个难点就是何时关闭流。关闭流的两个条件是已经(不一定是当前的数据报，可能是之前发的)给reassembler 发送了最后一个包，并且，reassembler.bytes_pending()==0，换言之，你已经给 reassembler 发送过来最后一条，并且它现在没有排队的了,就说明所有的字节都已经写入接受的流中了，就可以把 inbound_stream 给关掉了，因为不会再读取了.
还有个问题是计算 ackno, ackno 的值从 ISN 开始，然后看传给了多少字节。这个字节里面就包括实际的字符串字节和SYN和FIN。其实SYN根据上面的分析，已经可以认为走到这一步就肯定发送过了SYN了，重点是FIN。
FIN并不是和 insert时is_last_substring=true 同步的，那里只是发送了字符串，也就是从这个实验中来看，你永远不用真实的向 reassembler 发送SYN和FIN，说白了ackno只是通知发送端，我有没有接受罢了。因为测试用例中就有一个例子SYN _oodbye CS144 FIN ,那个下划线我是来表示那里还有个G没发送。这种情况下，实际上我们把oodbye CS144给接受了，SYN也接受了，但是FIN其实没有接受。
这种情况下的ack仍然是 ISN+1，然后补发了 G 之后，ackno 就立刻变成了相当于把SYN+字符串+FIN都接受的样子,并且关闭了 inbound_stream。
所以 ackno = ackno = this->initial_seq_number + inbound_stream.bytes_pushed() + recved_SYN + inbound_stream.is_closed();
lab3
这里就开始出现了一些说的不清晰的逻辑。所有要发送的包，都不要立刻发，而是存储在内部的一个队列里，maybe_send 每被调用一次发一个，没有就留空。
而且这个 tick 的时间也是很魔幻，可以认为在不执行tick的时候，无论执行多少操作，时间的流逝也不到1ms。
receive
这里有个小坑，就是，每次接受到的 receive 的 msg,里面的ack可能为空，空就当ack没收到。但是不管ack是不是空，这个windows_size都要更新。
另外也要忽略不合法的 ackno ，比如ackno已经是之前接收过的范围了，或者是超过了期望收到的范围.
并且，还不能简单粗暴的将 max(msg.windows_size,1)作为当前的 windows，而是需要特判一下，如果是0的话，当成1看，但是也要使用一个bool变量记录一下这种假设,比如我使用recv_windows_size_is_zero来记录。
这是因为在tick中遇到计时器超时的情况时， RTO * 2 的条件是 当前真正的窗口大小不是0,也就是recv_windows_size_is_zero=true时才对 RTO*2.但是维护 continuousive_retransmissions_number 和重置计时器的时候不需要考虑这个，直接重置计时器为 RTO 就行。
push
在push中，可以使用 多个 assert,比如assert(need_send_msg.sequence_length() <= recv_window_size );,assert( need_send_msg.payload.size() <= TCPConfig::MAX_PAYLOAD_SIZE );,来保证发送的没有问题。并且push函数还要保证一直发送，直到无法发送为止.比如 sequence_numbers_in_flight_ >= 接收窗口, 或者是能发送，但是发送的信息长度是0(这个应该和前面条件等价).
还有一个耐人寻味的点是FIN何时发送，这里又涉及到和 receive 的时候的类似问题了。并不是读取到最后就一定要发送FIN的，发送FIN有若干条件是
- 流已经finished了，它的数据全部被读取完并且被关闭了。
- 接收方能接受的数据大小除了本次要发送的其他内容(SYN和payload)之外还能塞下一个FIN
- 从未发送过 FIN
第三条可能看起来很奇怪，实际上这是因为push是一个循环，如果接收窗口很大，但是数据内容很少，那么读取过buffer之后的每一轮循环都会发送FIN,直到填满接收窗口.所以只需要发送一次就够了，到时候超时了自动就重传了.
lab4
注意，这里文档中并没有说 parse 返回 false 的时候应该怎么处理，这里可以加一个 assert()，先认为它是一定成功的，方便在 lab5 中 debug.
这里 arp ，最好在发生更新的情况时(就是已经知道了这个ip，但是还发来了同样的ip的arp回复)的时候加assert，确保前后的mac是一样的.
一定要小心处理对于ip到mac映射过期时候的逻辑，不要删除错误，或者多次删除，可能引发段错误.
另外就是 parse 和 serialize 的用法，看着挺绕，实际上就是
// 省略了很多细节，只是说大概是这么个意思，如果是ipv4同理
ARPMessage arp_reply_msg;
EthernetFrame ethe_frame;
ethe_frame.payload = serialize( arp_reply_msg );
lab5
这里有个巨坑！就是更新ttl之后一定要立刻计算 compute_checksum(), 否则就会有bad ipv4 datagram，本质上是 parse 报错了，这时候lab4的assert就发挥作用了。
dgram.header.ttl--;
dgram.header.compute_checksum();
然后再说一个我调了很久很久的坑
void Router::route()
这个函数里面自然是遍历 interface_ ,遍历的时候一定注意，它是一个数组直接存的这些接口，遍历的时候千万要注意，不要复制
// ok
for ( size_t i = 0; i < interfaces_.size(); ++i ) {
auto dgram = interfaces_[i].maybe_receive();
}
// bug, 实际上 inter 会将 interfaces_[i] 进行复制
// 导致后续的一直没有消费真实的数据
for (auto inter : interfaces_) {
auto dgram = inter.maybe_receive();
}
这实验本身不难，难在你难以确定lab4里面没有bug，而且调试很困难，即使用了我前面说的vscode自带的调试方法，仍然有些困难。
我的建议是，多打日志，因为mac和ip在debugger里面显示的很差，然后就很难调试和分析，所以我建议多打日志，日志中要输出，xxx号接口,本身的ip和mac，收到了数据，数据的源ip，目标ip,源mac，目标mac.这样我认为才有调试出来的希望。
lab6
按照例子试试就好，先测试交互式的，然后看看能不能正常退出(两边各输入一个ctrl+d),然后等待几秒钟，就会退出了。
如果不能退出，可以看看有没有段错误之类的，如果段错误了，那就启动sever的调试，运行起来后，在命令行里启动 client，具体的debug配置可能要参考上面的改改，end2end代码是有的，不会改配置可以往后看，待会会说。
然后如果上面交互式的没bug并且安全退出(最好连接成功后静置大概几十秒，等ip到mac映射过期了看看删除逻辑有没有bug)，那就尝试发送文件。
不知道为什么，发送文件很慢，大家可以不发1M的文件，发一个1K的文件试试。
然后也不要非得按照文档中的 client那样，可以只修改server的执行命令，client还是照常的命令，也就是直接打印到终端(看起来像是乱码),最终仍然在 client端手动执行ctrl+d,看能否正常退出，通过打印也大概能知道这个程序的运行速度。
如果到这里都没bug，那就按照文档上说的命令执行(还是用1K)的文件，然后查看校验码。
如果校验码也正确了，那就正确了，1M的需要很长时间才能发过去。
lab7
根据要求做做就好.不再赘述.
