2021 CS144 实验笔记

因为目前 CS 144 的实验项目没有全部放出,本笔记会随着课程的更新而更新。

如果需要代码,可以邮件联系我。

环境搭建

这个实验是在虚拟机进行,我们不可能使用 vim 敲代码,更不可能在虚拟机里面装一个图形化界面,然后在里面开发(套娃?)

这里给出两种方法:

VS Code 远程开发

使用 VS Code 的远程开发,通过 ssh 连接进入虚拟机,然后直接远程开发。适合懂得 C++ 语法的人操作,因为说实在的 VS Code 的代码提示真不如正规 IDE。

CLion 远程开发

因为本人对 C++ 语法不熟悉,如果没有 ide 辅助,估计一行代码都写不出来了,所以这里我使用的是 Clion。

方法也很简单,在自己电脑里面创建项目,然后用 clion 打开。在 clion 的 Preference->Toolchains 里面添加 Remote Host,然后在 Deployment 中添加目录映射(如果不映射,Clion 会自动映射到虚拟机里面的 tmp 目录下,不方便手动 make 运行测试用例)。

具体大家可以百度。

调试技巧

解决 Debug 时莫名其妙跳过断点以及 Optimized Out

其实之前就有这个问题,不过一直这样将就的调试,但是到了 lab 4 真的顶不住了。出现这个问题主要就是编译器直接对代码进行了优化,我们设置为不要优化即可。

找到项目目录下的 etc/cflags.cmake ,第 18 行,将
set (CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb3 -Og") 改为 set (CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb3 -O0")

调试 lab 4 txrx.sh 的小技巧

在 lab 4 的测试用例中,fsm 开头的测试用例我们能直接进行跑,并且进行 debug,但是有相当大的一部分实验是通过 txrx.sh 脚本跑,这里给大家一点调试方案。

  • 代码中所有的 std::cout 的调试信息输出全部换成 cerr,因为 ctest 中是不会显示标准输出的内容。
  • ctest 每次运行一个测试脚本,命令如下: ctest --output-on-failure -V -R 't_icS_16_1'-V 能显示你的调试内容,同时使用 tshark 进行监听。tshark 是监听 tun144 还是 tun145 看具体的测试用例,你稍微看下 shell 脚本就知道了(不懂 shell 也没事,看看名字就能猜到了,因为我也不会 shell)。

Lab 0 Networking Warmup

第一部分是让我们利用系统的 tcp 实现一个 webget,这个没啥难点,调用 C++ 的包即可。

第二部分是让我们实现一个 ByteStream,这个代码注释也挺详细的,总之不难。

Lab 1 Stitching Substrings Into a Byte Stream

Lab 1 比较头疼,选用合适的数据结构是关键。这里我使用的是 deque() ,因为它能方便的从两端插入和删除数据,且具有和数组一样的随机访问能力。

注意理解 capacity,我的理解就是 capacity = unassembler + output ByteStream 中未被取走的部分。

有一点要注意:如果 push_substring() 数据有一部分因为放不下被舍弃掉的话,那么传进来的 eof 是无效的,不过并不代表放弃整个 substring,在 capacity 容量里面的字符串还是需要保存。

这里可以参考:https://zhuanlan.zhihu.com/p/384335636 ,它写的不错。

Lab 2 the TCP Receiver

这一节是要求实现 TCP receiver,实验一开始让我们先实现 WrappingInt32 里面 buffer index 和 tcp sequence number 之间的转换,建议开始搞之前,把负数的二进制表示,32 位无符号整形,C++ 从 long 转为 int 等等搞清楚,不然莫名其妙的溢出会让人摸不到头脑。

这里主要讲讲 unwrap() 里面的一个细节:

1
2
3
4
5
6
uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
WrappingInt32 c = wrap(checkpoint, isn);
int32_t offset = n.raw_value() - c.raw_value();
int64_t ans = checkpoint+offset;
return ans >= 0 ? ans : ans + (1ul << 32);
}

可以看到我 ans 用的是有符号的 int64,那是因为 ans 可能为负数(比如 isn 为 5,然后 n 从 isn 开始绕了一圈后 seqno 是 4,计算出来的 offset 为 -1,假设此时的 checkpoint 还没有更新,等于 0),显然 buffer index 不可能为负数(因为其要求从 0 开始),所以这里我们人为加上 $2^{32}$ 就行了。

后面写 receiver 时我给几点建议,大家仅供参考:

  • 关于计算 ackno 的值,大家没必要在内部维护一个 ackno 的变量。可以直接通过 stream_out().bytes_written() 进行计算,不过注意的是,记得 +1,因为 SYN 占用一个序号。如果输出流已经结束,则要再 +1,因为 FIN 也占用一个序号。
  • _reassembler.push_substring() 时我们需要计算 buffer index,这里我推荐使用 int64 来处理 buffer index,因为支持负数的话,好处理很多。比如当计算出来的 buffer index < 0 时,直接抛弃即可,这说明了传入的 seqno 小于当前的 isn。
  • 注意通过 unwrap 计算而来的 buffer index 需要 -1,因为你需要去掉 SYN 占得那一个坑位。而如果当前这个 TCPSegment 正好是 SYN 包,那么则不需要 -1。可能说起来有些拗口,等你测试用例报错时就明白了。

Lab 3 the TCP Sender

这一节实验难度相比于上一节一下子提升了很多,有很多的琐碎地方。我一次写的时候是面向测试用例编程,后面实在改不动了,拆东墙补西墙,直接重构了,然后就光速 PASS 了。最好写之前自己内心就要有一个总体的方案,不然代码就会很乱。

这里我简单的介绍下思路和注意点,当然不可能把代码放出来。

我自己定义了如下变量,大家经供参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 每一个 TCPSegment 发送后,就放在这里进行追踪,只有当对应的 TCPSegment 被 ack 后,才从这里移除。
std::queue<TCPSegment> segments_wait_{};
// 标记 TCP 是否建立了 SYN
bool has_SYN_ = false;
// 标记 TCP 是否已经结束
bool has_FIN_ = false;
// 最近一次接收的(最新的)ack number
uint64_t receive_ackno{0};
// 接收的 window size
uint16_t window_size_ = 0;
uint64_t bytes_in_flight_ = 0;
unsigned int consecutive_retransmissions_ = 0;
// 是否开启超时重传计时器
bool timer_running_ = false;
// 相比于上一次接收 tick(),现在已经过去了多久
size_t pass_time_ = 0;
unsigned int retransmission_timeout_ = 0;

我的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
uint64_t TCPSender::bytes_in_flight() const { return bytes_in_flight_; }

void TCPSender::fill_window() {
if (has_FIN_) {
return;
}

TCPSegment tcpSegment;
if (!has_SYN_) {
// 建立初次连接,开始三次握手
// ....
has_SYN_ = true;
return;
}

// 注意实验说明里面的,如果接收的 window_size 为 0,那我们要把它当做 1.
uint16_t tmp_window_size = window_size_ == 0 ? 1 : window_size_;

if (_stream.eof() && (receive_ackno + tmp_window_size > _next_seqno)) {
// 发送 FIN
// ....
has_FIN_ = true;
return;
}

// 注意此处使用 while,循环发送,直到 window size 被填满或 _stream 没数据为止
while (!_stream.buffer_empty()) {
if (_next_seqno > receive_ackno + tmp_window_size - 1) {
break;
}

size_t max_length = ...; // 根据边界计算能发送的最大 max_length
if (max_length == 0) {
break;
}

tcpSegment.payload() = _stream.read(max_length);
// 如果发送当前的数据后,且仍有空间携带 FIN,那么直接带上 FIN。 piggyback data in FIN
if (_stream.eof() && tcpSegment.length_in_sequence_space() < tmp_window_size) {
// ...
}
send_tcp_segment(tcpSegment);
}
}

//! \param ackno The remote receiver's ackno (acknowledgment number)
//! \param window_size The remote receiver's advertised window size
void TCPSender::ack_received(const WrappingInt32 ackno, const uint16_t window_size) {
uint64_t abs_ack = unwrap(ackno, _isn, _next_seqno);

if (abs_ack > _next_seqno) {
return;
}

if (abs_ack >= receive_ackno) {
receive_ackno = abs_ack;
window_size_ = window_size;
}

while (!segments_wait_.empty()) {
// 弹出 ack 确认过的 TCPSegment
// ...

// 重置超时重传的相关信息
retransmission_timeout_ = _initial_retransmission_timeout;
consecutive_retransmissions_ = 0;
pass_time_ = 0;
}

if (segments_wait_.empty()) {
timer_running_ = false;
} else {
timer_running_ = true;
}
}

//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void TCPSender::tick(const size_t ms_since_last_tick) {
if (!timer_running_) {
return;
}

pass_time_ += ms_since_last_tick;
if (pass_time_ >= retransmission_timeout_ && !segments_wait_.empty()) {
// 超时重传
// ...
pass_time_ = 0;

// 此处需要考虑如果是 SYN 包的超时重传,因为 SYN 包你没有接收到过 window size,但是你仍然需要 时间x2
if (window_size_ > 0 || tcpSegment.header().syn) {
consecutive_retransmissions_++;
retransmission_timeout_ *= 2;
}
}
}

unsigned int TCPSender::consecutive_retransmissions() const { return consecutive_retransmissions_; }

void TCPSender::send_empty_segment() {// 没写,测试用例没有测试到,等下一个实验补上}

void TCPSender::send_tcp_segment(TCPSegment &tcpSegment) {
tcpSegment.header().seqno = wrap(_next_seqno, _isn);
_next_seqno += tcpSegment.length_in_sequence_space();
_segments_out.push(tcpSegment);
segments_wait_.push(tcpSegment);
bytes_in_flight_ += tcpSegment.length_in_sequence_space();
if (!timer_running_) {
timer_running_ = true;
pass_time_ = 0;
}
}

Lab 4 the TCP connection

Lab 4 相比之前确实很难,网上很多人说做 lab 4 时会发现自己之前写的代码有很多 bug,然后要去改之前的代码,或者修改之前代码结构。还有些人说有些测试用例是访问国外的网站,国内网络不行,所以即使出现 timeout 也就不管了。

这里我说说我的感受:

  • 难度确实大,但是没有那么离谱,我做花了大约 4 天吧。
  • 我就改了之前的一行 bug,并没有其他地方需要修改。
  • 我并没有修改之前代码的结构。
  • 测试用例那个 169 开头的 IP 并不是国外的,而是它在你自己机子上面模拟的一个本地 ip,所以如果出现 timeout,并不是访问超时,而是你的 tcp 没有正常关闭,建议使用 tshark 抓包分析下。

关于代码的实现,我的操作是通过各种 if-else 操作,确定当前的状态,然后根据状态机的图,从哪切换到哪里,确定好路径。不过代码并不完美,比如我无法通过状态区分 CLOSE_WAIT 和 FIN_WAIT_2 的区别。

放出来一段 segment_received 的代码仅供参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
void TCPConnection::segment_received(const TCPSegment &seg) {
if (!is_active_) {
return;
}

time_since_last_segment_received_ = 0;

if (seg.header().rst) {
immediate_shutdown(false);
return;
}

// closed
if (_sender.next_seqno_absolute() == 0) {
// passive open
if (seg.header().syn) {
// todo Don't have ack no, so sender don't need ack
_receiver.segment_received(seg);
connect();
log_print("closed -> syn-rcvd");
}
return;
}

// syn-sent
if (_sender.next_seqno_absolute() == _sender.bytes_in_flight() && !_receiver.ackno().has_value()) {
if (seg.header().syn && seg.header().ack) {
// active open
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
// send ack
_sender.send_empty_segment();
send_internet();
// become established
log_print("syn-sent -> established");
} else if (seg.header().syn && !seg.header().ack) {
// simultaneous open
_receiver.segment_received(seg);
// already send syn, need a ack
_sender.send_empty_segment();
send_internet();
// become syn_rcvd
log_print("syn-sent -> syn_rcvd");
}
return;
}

// syn-rcvd
if (_receiver.ackno().has_value() && !_receiver.stream_out().input_ended() &&
_sender.next_seqno_absolute() == _sender.bytes_in_flight()) {
// receive ack
// todo need ack
_receiver.segment_received(seg);
_sender.ack_received(seg.header().ackno, seg.header().win);
log_print("syn-rcvd -> established");
return;
}

// established, aka stream ongoing
if (_sender.next_seqno_absolute() > _sender.bytes_in_flight() && !_sender.stream_in().eof()) {
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
if (seg.length_in_sequence_space() > 0) {
_sender.send_empty_segment();
}
_sender.fill_window();
send_internet();
if (seg.header().fin) {
log_print("established -> close wait");
}
return;
}

// close wait
if (!_sender.stream_in().eof() && _receiver.stream_out().input_ended()) {
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
// try to send remain data
_sender.fill_window();
send_internet();
log_print("close wait -> (send remain data) or (last ack)");
return;
}

// FIN_WAIT_1
if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
_sender.bytes_in_flight() > 0 && !_receiver.stream_out().input_ended()) {
if (seg.header().fin && seg.header().ack) {
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
_sender.send_empty_segment();
send_internet();
log_print("fin_wait_1 -> time_wait");
} else if (seg.header().fin && !seg.header().ack) {
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
_sender.send_empty_segment();
send_internet();
log_print("fin_wait_1 -> closing");
} else if (!seg.header().fin && seg.header().ack) {
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
send_internet();
log_print("fin_wait_1 -> fin_wait_2");
}

return;
}

// CLOSING
if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
_sender.bytes_in_flight() > 0 && _receiver.stream_out().input_ended()) {
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
send_internet();
log_print("closing -> time_wait");
return;
}

// FIN_WAIT_2
if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
_sender.bytes_in_flight() == 0 && !_receiver.stream_out().input_ended()) {
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
_sender.send_empty_segment();
send_internet();
log_print("fin_wait_2 -> time_wait");
return;
}

// TIME_WAIT
if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
_sender.bytes_in_flight() == 0 && _receiver.stream_out().input_ended()) {
if (seg.header().fin) {
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
_sender.send_empty_segment();
send_internet();
log_print("time_wait -> time_wait (Still reply FIN)");
}

return;
}
// 有些状态没有预判到,这里统一处理下。
_sender.ack_received(seg.header().ackno, seg.header().win);
_receiver.segment_received(seg);
_sender.fill_window();
send_internet();
}

image-20211112003931243

image-20211112003938355

本来是想把代码贴出来的,后来想想算了,因为感觉写的不是很好。有些地方也是稀里糊涂莫名其妙的过了(就是自己都不知道当前 TCP 处于什么状态)。

Lab 5 the network interface

额,Lab 5 确实很简单,毕竟 ARP 的逻辑就是那么简单,也不需要啥奇淫巧技,个人花了 1 天完成(当然可能真的代码时间也就 2 小时吧)。

注意如下几点:

  • 发送 IP 报文时,如果当前没有目标主机的 ARP 信息,那么先发送 ARP 信息,得到 ARP 回复后,再把该 IP 报文发送(这意味着你不能丢弃 IP 报文,拿一个 queue 存储)。
  • 发送 ARP 请求时,frame 的 dst 是广播 mac 地址,但是 ARPMessage 里面的 target_ethernet_address 应该为空。
  • ARP 请求 5s 内不能重复发送,可以用一个 map 记录下。

Lab 6

comming soon..